Zainspirowany wyzwaniem przełożenia Lego autorstwa Keitha Randalla.

Ja także planuję zbudować gigantycznego robota Lego, który ostatecznie będzie w stanie zniszczyć inne roboty w nigdy wcześniej nie wspomnianej konkurencji. * W trakcie budowy robota będę używać wielu pociągów zębatych do połączenia różne części robota. Chcę, żebyś napisał mi najkrótszy program, który pomoże mi zbudować złożone przekładnie zębate, które są wymagane do tak złożonego zadania. Oczywiście będę używać tylko kół zębatych o promieniu 1, 2, 3 i 5 jednostek arbitralnych-lego.

Każdy bieg w przekładni ma określoną współrzędną całkowitą na siatce 2D. Pierwszy bieg znajduje się na (0,0), a ostatni bieg będzie na współrzędnych nieujemnych. Lokalizacja i rozmiar pierwszego i ostatniego biegu zostaną podane jako dane wejściowe, twój program musi powiedzieć, które biegi idą gdzie wypełnić luki.

Dodatkowo twój program musi wykorzystywać minimalną możliwą liczbę biegów w przekładni. Mniej biegów / pociągów = więcej pociągów ** = większy i lepszy robot zniszczenia.

Dane wejściowe będą składać się z jednego wiersza:

X,Y,B,A

X i Y są współrzędnymi ostatniego biegu. Pierwszy bieg jest zawsze ustawiony na (0,0). B i A są odpowiednio promieniami biegu końcowego i początkowego. Aby dodać trochę trudności, musisz upewnić się, że koło wyjściowe obraca się we właściwym kierunku. Jeśli A i B mają ten sam znak, to koło wyjściowe musi się obracać w tym samym kierunku i należy użyć nieparzystej liczby kół zębatych. Jeśli mają przeciwne znaki, należy użyć parzystej liczby biegów.

Wyjściem powinna być lista lokalizacji X, lokalizacji Y i promieni każdego dodatkowego biegu, jeden bieg na linię. Jeśli istnieje wiele rozwiązań z minimalnym sprzętem, wydrukuj tylko jedno z wybranych. Kolejność biegów na wyjściu nie ma znaczenia.

Przykłady (możliwe mogą być bardziej równoważne rozwiązania):

in
4,0,1,1
out
2,0,1

in
7,7,-2,-2
out
4,3,3
OR
0,7,5
OR
the above reflected over y=x line

in
7,8,-1,2
out
7,0,5
7,6,1
OR
7,0,5
1,8,5

in
7,7,2,-2
out
4,-3,3
7,1,2
12,1,3
12,7,3
OR
any permutation of the above, or reflected over y=x line
Now you're thinking with gear trains!

Oto rozwiązania powyższych przykładów, wizualizowane:

O ile mi wiadomo, żaden problem nie jest niemożliwy, chyba że dwa biegi wejściowe nachodzą na siebie lub się bezpośrednio łączą. Nie będziesz musiał sobie z tym poradzić.

To jest golf golfowy, wygrywa najkrótsza odpowiedź.

* Przyszły KOTH, ktoś?

** CHOO CHOO !!

C #, 660 bajtów

using System.Linq;using System;class P{int p=1,x,y,r;P l;static void Main(){var Q="$&.$'7$(@$*R$'/$(8$)A'(A('A$+S$(0$)9'(9('9$*B$,T$*2$+;$,D$.V*,V,*V";var I=Console.ReadLine().Split(',').Select(int.Parse).ToList();int i=0,t,s=7,u,v,w,p=I[3]*I[2];for(var D=new[]{new P{r=Math.Abs(I[3]),l=new P{r=Math.Abs(I[2]),x=I[0],y=I[1],p=3}}}.ToList();i>=0;){P c=D[i++],l=c.l;for(;(l=l?.l)!=null&&(s=(t=c.x-l.x)*t+(t=c.y-l.y)*t-(t=c.r+l.r)*t)>0;);if(s==0&&l.p>2&p*c.p<0)for(i=-1;c.l.p<3;c=c.l)Console.WriteLine(c.x+","+c.y+","+c.r);for(t=0;s>0&t<66;t++)for(u=Q[t++]-36,v=Q[t++]-36,s=1;s++<5&Q[t]%9==c.r;w=u,u=v,v=-w,D.Add(new P{l=c,r=Q[t]/9-4,x=c.x+u,y=c.y+v,p=-c.p}));}}}

Wypróbuj online

To była świetna zabawa !! Kompletny program, przyjmuje dane wejściowe z STDIN, dane wyjściowe do STDOUT. Wyjście to biegi w kolejności od końca do początku. Stosowanie:

Wykonuje proste wyszukiwanie szerokości, które rozwiązuje problem 4 biegów w mniej niż sekundę. Czynnik rozgałęzienia nie jest tak duży, więc powinien być dobry na znacznie więcej (naprawdę go nie testowałem). Niestety używa Linq.

QCiąg jest tabela wszystkich dozwolonych połączeń zębatych (czyli r=3i połączyć się r=1, jeśli dx=4i dy=0) w jednej ćwiartce, który jest następnie obracana na znalezienie innych. Każdy zestaw 3 bajtów jest dx, dyoraz informacje promień połączenia prawnego. Wybór (przesunięcia był bardzo przemyślany: raz fajnie było wybrać znak ASCII dla dobrych właściwości, zamiast desperacko próbować znaleźć ładne właściwości dla narzuconych znaków ASCII.

Prawdopodobnie potrafię lepiej odczytać dane wejściowe, ale nie miałem jeszcze szczęścia, zwłaszcza dlatego, że Linq jest opłacany potrzebą listy. Jestem również bardzo rozczarowany obrotowym kodem, wydaje mi się, że można to zrobić w znacznie mniejszej liczbie bajtów.

Sformatowany i skomentowany kod z Qgeneratorem:

using System.Linq; // seems to pay today
using System;

class P
{
    static void GenQ()
    {
        int t, k = 0, m = 0;
        Func<P, P, int> C = (P c, P l) => (t = c.x - l.x) * t + (t = c.y - l.y) * t - (t = c.r + l.r) * t; // ==0 -> touching, <0 -> not touching, >0 -> overlap

        string str = "";

        string T(int i) => "" + (char)('$' + i); // $ is zero, '$' == 36, so we can mod and div by 9, and greater than " so we don't have to escape it

        foreach (int r in new[] { 1, 2, 3, 5 }) // at 0,0 (current gear)
            foreach (int s in new[] { 1, 2, 3, 5 }) // gear to place
                for (int i = 0; i <= r + s; i++) // x
                    for (int j = 1; j <= r + s; j++, m++) // y
                        if (C(new P { r = r }, new P { r = s, x = i, y = j }) == 0) // 
                        {
                            str += T(i) + T(j) + T(r + s * 9);
                            k++;
                        }

        System.Console.WriteLine("K : " + k);
        System.Console.WriteLine("M : " + m);
        System.Console.WriteLine(str);
        System.Console.ReadKey(true);
        return;
    }

    int p=1, // parity
        x, // x
        y, // y
        r; // radias (TODO: store radias^2 ?)
    P l; // previous in search list

    static void Main()
    {
        //GenQ();

        // '$' == 36 (4*9)
        // 3char blocks: x,y,r+9*s
        var Q="$&.$'7$(@$*R$'/$(8$)A'(A('A$+S$(0$)9'(9('9$*B$,T$*2$+;$,D$.V*,V,*V"; // quarter table

        // primative read ints
        var I=Console.ReadLine().Split(',').Select(int.Parse).ToList();

        int i=0, // position in Due
            t, // check differential cache, position in Q
            s=7, // check cache, rotation counter (>0)
            u, // rotation x
            v, // rotation y
            w, // rotation x cache
            p=I[3]*I[2]; // parity (>0 -> same, even ; <0 -> different, odd)

        // due (not point using a queue, the search space grows exponentially)
        for(var D=new[]{
                new P{r=Math.Abs(I[3]), // start (p==1)
                    l=new P{r=Math.Abs(I[2]),x=I[0],y=I[1],p=3} // terminal (detect with p==3)
                }}.ToList();
            i>=0;) // infinite number of configurations, no bounds, i is escape term
        {
            P c=D[i++], // current
                l=c.l; // check, initially the one before the previous (we know we are touching last already)

            // 'checks' c against l
            //Func<int>C=()=>(t=c.x-l.x)*t+(t=c.y-l.y)*t-(t=c.r+l.r)*t; // ==0 -> touching, >0 -> not touching, <0 -> overlap

            // check we arn't touching any before us (last thing we check is terminal)
            for(;(l=l?.l)!=null&& // for each before us (skipping the first one)
                (s=(t=c.x-l.x)*t+(t=c.y-l.y)*t-(t=c.r+l.r)*t)>0;); // check c against l and cache in s, ==0 -> touching, >0 -> not touching, <0 -> overlap

            if(s==0&& // touching last checked?
                l.p>2& // stopped on terminal?
                p*c.p<0) // correct parity? -> win
                for(i=-1; // escape
                    c.l.p<3;c=c.l) // for each that wasn't the first
                    Console.WriteLine(c.x+","+c.y+","+c.r);

            // enumerate possible additions, and queue them in due
            for(t=0;
                s>0& // not touching or overlapping anything (including terminal)
                t<66;t++) // 66 = Q.Length
                for(
                    u=Q[t++]-36, // '$'
                    v=Q[t++]-36,
                    s=1;s++<5& // rotate 4 times
                    Q[t]%9==c.r; // our raidus matches
                        w=u, // chache y value
                        u=v, // rotate
                        v=-w,
                        D.Add(new P // add
                        {
                            l=c,
                            r=Q[t]/9-4, // radius
                            x=c.x+u,
                            y=c.y+v,
                            p=-c.p // flip parity
                        }));
        }
    }
}