Inspirado en el desafío de relaciones de engranajes de Lego de Keith Randall.

Yo también planeo construir un robot gigante de lego que eventualmente pueda destruir a los otros robots en la competencia nunca antes mencionada. * En el proceso de construcción del robot, usaré muchos trenes de engranajes para conectar diferentes partes del robot Quiero que me escribas el programa más corto que me ayudará a construir los trenes de engranajes complejos que se requieren para una tarea tan compleja. Por supuesto, solo usaré engranajes con radios 1, 2, 3 y 5 unidades arbitrarias de lego.

Cada engranaje en el tren de engranajes tiene una coordenada entera específica en una cuadrícula 2D. La primera marcha se encuentra en (0,0) y la marcha final se ubicará en coordenadas no negativas. La ubicación y el tamaño del primer y último engranaje se proporcionarán como entrada, su programa debe indicar qué engranajes van a dónde rellenar los huecos.

Además, su programa debe usar el mínimo número posible de engranajes en el tren de engranajes. Menos engranajes / tren = más trenes ** = robot de destrucción más grande y mejor.

La entrada consistirá en una línea:

X,Y,B,A

X e Y son las coordenadas de la marcha final. La primera marcha siempre se encuentra en (0,0). B y A son los radios de los engranajes final e inicial, respectivamente. Para agregar alguna dificultad, debe asegurarse de que el engranaje de salida gire en la dirección correcta. Si A y B tienen el mismo signo, entonces el engranaje de salida debe girar en la misma dirección, y se debe usar un número impar de engranajes. Si tienen signos opuestos, entonces se debe usar un número par de engranajes.

La salida debe ser una lista de la ubicación X, la ubicación Y y los radios de cada marcha adicional, una marcha por línea. Si hay varias soluciones de engranaje mínimo, imprima solo una de su elección. El orden de los engranajes en la salida no importa.

Ejemplos (pueden ser posibles soluciones más equivalentes):

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!

Aquí están las soluciones a los ejemplos anteriores, visualizadas:

Hasta donde yo sé, ningún problema es imposible a menos que los dos engranajes de entrada se superpongan o se conecten directamente. No tendrás que lidiar con esto.

Este es el código de golf, gana la respuesta más corta.

* Un futuro KOTH, alguien?

**¡¡CHÚ CHÚ!!

C #, 660 bytes

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

Pruébalo en línea

¡Esto fue muy divertido! Programa completo, acepta entrada de STDIN, salida a STDOUT. La salida son los engranajes en orden desde el final hasta el comienzo. Uso:

Realiza una simple búsqueda de Breadth First, que resuelve un problema de 4 velocidades en menos de un segundo. El factor de ramificación no es realmente tan grande, por lo que debería ser bueno para considerablemente más (no lo probé realmente). Lamentablemente utiliza Linq.

La Qcadena es una tabla de todas las conexiones de engranajes permitidas (es decir, an r=3y se conectan a un r=1if dx=4y dy=0) en un cuadrante, que luego se gira para encontrar los otros. Cada conjunto de 3 bytes es el dx, dyy la información de radio para una conexión legal. La elección de (un desplazamiento fue muy deliberada: por una vez fue divertido elegir un personaje ASCII para buenas propiedades, en lugar de tratar desesperadamente de encontrar buenas propiedades para los caracteres ASCII impuestos.

Probablemente pueda leer mejor la entrada, pero todavía no he tenido suerte, sobre todo porque el Linq se paga por la necesidad de una lista. También estoy muy decepcionado por el código de rotación, siento que eso podría hacerse en una cantidad considerablemente menor de bytes.

Código formateado y comentado con Qgenerador:

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