Вдохновленный вызовом коэффициента передачи Lego Китом Рэндаллом.

Я также планирую построить гигантского робота Lego, который в конечном итоге сможет уничтожить других роботов в ранее не упоминавшемся соревновании. * В процессе создания робота я буду использовать множество зубчатых передач для соединения разные части робота. Я хочу, чтобы вы написали мне самую короткую программу, которая поможет мне построить сложные зубчатые передачи, необходимые для такой сложной задачи. Я, конечно, буду использовать только шестерни с радиусами 1, 2, 3 и 5 произвольных лего.

Каждое зубчатое колесо в зубчатой ​​передаче имеет определенную целочисленную координату на двумерной сетке. Первая передача расположена в точке (0,0), а последняя - в неотрицательных координатах. Местоположение и размер первой и последней шестерен будут предоставлены в качестве входных данных, ваша программа должна указать, какие шестерни идут, где заполнить пробелы.

Кроме того, ваша программа должна использовать минимально возможное количество передач в передаче. Меньше передач / поезд = больше поездов ** = больший и лучший робот разрушения.

Ввод будет состоять из одной строки:

X,Y,B,A

X и Y - координаты конечной передачи. Первая передача всегда находится в точке (0,0). B и A - радиусы конечной и начальной шестерен соответственно. Чтобы добавить некоторые трудности, вы должны убедиться, что выходное зубчатое колесо вращается в правильном направлении. Если A и B имеют одинаковый знак, то выходное зубчатое колесо должно вращаться в одном и том же направлении, и должно использоваться нечетное количество зубчатых колес. Если они имеют противоположные знаки, то необходимо использовать четное количество передач.

Выходными данными должен быть список местоположения X, местоположения Y и радиусов каждого дополнительного зубчатого колеса, по одному зубчатому колесу на линию. Если существует несколько решений с минимальной передачей, напечатайте только одно на ваш выбор. Порядок передач на выходе не имеет значения.

Примеры (возможны более эквивалентные решения):

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!

Вот решения приведенных выше примеров, визуализированные:

Насколько я знаю, никакие проблемы невозможны, если две входные шестерни не перекрываются или не соединяются напрямую. Вам не придется иметь дело с этим.

Это код гольф, самый короткий ответ выигрывает.

* Будущий кот, кто-нибудь?

** Чу Чу !!

C #, 660 байт

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}));}}}

Попробуйте онлайн

Это было очень весело! Завершить программу, принимает ввод из STDIN, вывод в STDOUT. Вывод шестерен в порядке от конца к началу. Использование:

Выполняет простой поиск в ширину, который решает проблему с 4 передачами менее чем за секунду. Фактор ветвления на самом деле не так уж велик, поэтому он должен быть полезен для значительно большего (на самом деле это не проверялось). К сожалению, он использует Linq.

QСтрока представляет собой таблицу всех разрешенных зубчатых соединений (т.е.r=3 и подключение к r=1если dx=4и dy=0) в одном квадранте, который затем поворачивается , чтобы найти другие. Каждый набор из 3 -х байт является dx, dyи информация радиус правовой связи. Выбор (смещения был очень осознанным: на этот раз было забавно выбрать символ ASCII для хороших свойств, а не отчаянно пытаться найти хорошие свойства для навязанных символов ASCII.

Возможно, я лучше справлюсь с чтением входных данных, но мне пока не повезло, не в последнюю очередь потому, что Linq оплачивается необходимостью в списке. Я также очень разочарован кодом поворота, я чувствую, что это можно сделать за значительно меньшее количество байтов.

Отформатированный и закомментированный код с Q генератором:

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
                        }));
        }
    }
}