Cluck cluck. Nadie sabe por qué el pollo cruzó la calle, tal vez había un gallo atractivo al otro lado. Pero podemos averiguar cómo. Escriba un programa que, de izquierda a derecha, cruce este (o cualquier) "camino".

1356 | 1738
3822 | 1424
3527   3718
9809 | 5926
0261 | 1947
7188   4717
6624 | 9836
4055 | 9164
2636   4927
5926 | 1964
3144 | 8254

Su programa lo "cruza", moviéndose de izquierda a derecha. Empiezas en cualquier número en la columna de la izquierda que quieras. Desde allí, puedes moverte a cualquier personaje adyacente a la derecha. Si comenzó en la esquina superior izquierda, 1, puede ir a 3 u 8. Cada número al que va, incluido el número inicial, se agrega a una suma. Los espacios no se suman a su suma. "|" te obliga a moverte hacia arriba o hacia abajo, en lugar de hacia la derecha. (NO PUEDES avanzar en este personaje) Tu objetivo es llegar al otro lado con la suma más pequeña posible. Su programa debe imprimir la suma al final y debe poder resolver cualquier camino. Preferiblemente, también podría tener entrada para un camino, pero no es obligatorio. Su programa debe imprimir tanto la ruta como la suma. Pocos bytes de código gana.

Para aclarar, puede moverse con diagnóstico a menos que esté en una barra vertical. Solo puedes moverte hacia arriba y hacia abajo cuando estás en una barra vertical.

Para una especificación más clara de las carreteras, es básicamente una cadena de texto (o una matriz de columnas o filas, si prefiere pensar de esa manera) que sigue las reglas de los caracteres, y no puede haber nada PERO esos caracteres en El camino. Puede haber cualquier número, un espacio, una barra ("|") o una nueva línea. Si un borracho pavimentó un camino, como en la respuesta de ProgrammerDan, sigue siendo un camino válido y su programa debe ser capaz de resolverlo. No se considera un camino si es imposible llegar al otro lado (por ejemplo, no hay salida de una línea recta de barras).

Su programa no está obligado a determinar si una carretera no es válida.

Clave:
Cualquier número: agrega el número a su suma, avance.
Espacio: avance, no se agrega nada a su suma.
"|" - Mover hacia arriba o hacia abajo, no se agrega nada a su suma.

EDITAR: una solución de ejemplo, como se sugiere. No puedo hacer uno terriblemente grande, no puedo obtener un IDE para resolverlo en mi cajero automático.

Toma este pequeño camino:

9191 | 8282
1919 | 2727
5555   5555

La solución sería una ruta de 1, 1, 1, 1, espacio, divisor, divisor, espacio, espacio, 2, 2, 2, 2 para un total de 12.

EDITAR # 2: La solución al primer camino en esta pregunta, según lo determinado por Geobits y los programas de la gente, es 0,2,0,1,,,, 1,4,1,4 por un total de 13.

code-golf path-finding CaffeineToCode
fuente

¿Podría incluir al menos un caso de prueba con una solución correcta? Además, ¿podría haber más de tres |seguidos?

Martin Ender

@timmy puedes moverte en diagonal, siempre que esté avanzando. Se puede tocar con un par de movimientos diagonales.

CaffeineToCode

@ mbomb007 Si comienza en la esquina superior. Como puede comenzar en cualquiera de la columna de la izquierda, puede obtener0,2,0,1, , , ,1,4,1,4 -> 13

Geobits

Si lo hace. Solo puede moverse hacia arriba o hacia abajo en las barras, por lo que solo puede salir de ellas a través de un espacio.

CaffeineToCode

Para el resultado, simplemente el costo es suficiente, o ¿se necesita dar salida al camino completo?

ProgramadorDan

Java, 955 bytes

Obviamente no voy a ganar ningún premio, siendo Java y todo, pero me encanta este problema y quería incluir mi propia entrada.

Características y límites:

Puede soportar carreteras irregulares (¡súper borracho!) Incluyendo anchos variables, líneas complejas, etc.
Espera que el camino se ingrese como parámetros en la ejecución la versión sin golf también admite la lectura de stdin, pero como no se especificó el método de entrada, ¡la versión con golf espera la más pequeña!
Utiliza alguna técnica de programación dinámica que no he usado en, oh, 6 años más o menos para resolver eficientemente en el tiempo O (n * m), donde n es filas ym son columnas.
- Resuelve de derecha a izquierda, marcando la mejor dirección para tomar del índice actual al siguiente índice.
- Las "líneas" se manejan resolviendo su columna y luego dirigiéndolas si se puede acceder en la siguiente columna. Se resuelven almacenando la dirección hacia arriba o hacia abajo, con el costo de la no línea eventualmente accesible.
Sigue, pero no imprime (en la versión de golf) el índice inicial de la mejor solución.

Ok, suficiente jibba jabba. Versión de golf:

class C{public static void main(String[]a){int n=a.length,m=0,i=0,j=0,h=0,p=0,q=0,s=0,t=0,b=-1,c=2147483647,x=0,y=0;char[][]r=new char[n][];char u;for(String k:a){j=k.length();m=(j>m)?j:m;}for(String k:a)r[i++]=java.util.Arrays.copyOf(k.toCharArray(),m);int[][][]d=new int[n][m][2];for(j=m-1;j>=0;j--){for(i=0;i<n;i++){u=r[i][j];p=(u=='\0'||u==' '||u=='|'?0:u-'0');if(j==m-1)d[i][j][1]=p;else{if(u=='|')d[i][j][0]=-1;else{for(h=-1;h<2;h++){x=i+h;y=j+1;if(x>=0&&x<n){if(d[x][y][0]==-1){s=x-1;while(s>=0&&r[s][y]=='|')s--;t=x+1;while(t<n&&r[t][y]=='|')t++;if((s>=0&&t<n&&d[s][y][1]<d[t][y][1])||(s>=0&&t>=n)){t=d[s][y][1];s=4;}else{s=6;t=d[t][y][1];}d[x][y][0]=s;d[x][y][1]=t;}q=d[x][y][1]+p;if(d[i][j][0]==0||q<d[i][j][1]){d[i][j][0]=h+2;d[i][j][1]=q;}}}}}if(j==0&&(b<0||d[i][j][1]<c)){b=i;c=d[i][j][1];}}}String o="";i=b;j=0;while(j<m){u=r[i][j];if(u=='\0')j=m;else{o+=u+",";h=d[i][j][0]-2;if(h>1)i+=h-3;else{i+=h;j++;}}}System.out.println(o+"\b:"+c);}}

Según mi costumbre, github con el código no golfista .

Solución para el "primer" camino:

$ java C "1356 | 1738" "3822 | 1424" "3527   3718" "9809 | 5926" "0261 | 1947" "7188   4717" "6624 | 9836" "4055 | 9164" "2636   4927" "5926 | 1964" "3144 | 8254"
0,2,0,1, , , ,1,4,1,4:13

Segundo ejemplo

$ java C "9191 | 8282" "1919 | 2727" "5555   5555"
1,1,1,1, ,|,|, , ,2,2,2,2:12

Muestra de Brian Tuck:

$ java C "6417443208|153287613" "8540978161|726772300" "7294922506 263609552" "0341937695 498453099" "9417989188 370992778" "2952186385|750207767" "7049868670 756968872" "1961508589|379453595" "0670474005 070712970" "4817414691|670379248" "0297779413|980515509" "6637598208 090265179" "6872950638 767270459" "7375626432 439957105" "1387683792|544956696" "6974831376 545603884" "0949220671|632555651" "3952970630|379291361" "0456363431|275612955" "2973230054|830527885" "5328382365|989887310" "4034587060 614168216" "4487052014|969272974" "5015479667 744253705" "5756698090|621187161" "9444814561|169429694" "7697999461|477558331" "3822442188 206942845" "2787118311|141642208" "2669534759 308252645" "6121516963|554616321" "5509428225|681372307" "6619817314|310054531" "1759758306 453053985" "9356970729|868811209" "4208830142 806643228" "0898841529|102183632" "9692682718|103744380" "5839709581|790845206" "7264919369|982096148"
2,1,0,1,5,1,2,1,1,1, ,1,0,1,2,1,2,3,0,1:26

El ejemplo de Brian "borracho":

6417443208 | 153287613
8540978161 | 726772300
7294922506 263609552
0341937695 498453099
9417989188 370992778
2952186385 | 750207767
7049868670 756968872
1961508589 | 379453595
0670474005 070712970
4817414691 | 670379248
0297779413 | 980515509
6637598208 090265179
6872950638 767270459
7375626432 439957105
1387683792 | 544956
697483176 5456034
09492201 | 6325551
395297030 | 3792913
 456363431 | 275612
  73230054 | 830527885
    8382365 | 989887310
    4587060 614168216
  87052014 | 96927297
 50479667 7442537
57566980 | 621187161
944481456 | 169429694
7697999461 | 477558331
3822442188 206942845
2787118311 | 141642208
2669534759 308252645
6121516963 | 554616321
5509428225 | 681372307
6619817314 | 310054531
1759758306 453053985
9356970729 | 868811209
4208830142 806643228
0898841529 | 102183632
9692682718 | 103744380
5839709581 | 790845206
7264919369 | 982096148

$ java C "6417443208|153287613" "8540978161|726772300" "7294922506 263609552" "0341937695 498453099" "9417989188 370992778" "2952186385|750207767" "7049868670 756968872" "1961508589|379453595" "0670474005 070712970" "4817414691|670379248" "0297779413|980515509" "6637598208 090265179" "6872950638 767270459" "7375626432 439957105" "1387683792|544956" "697483176 5456034" "09492201|6325551" "395297030|3792913" " 456363431|275612" "  73230054|830527885" "    8382365|989887310" "    4587060 614168216" "  87052014|96927297" " 50479667 7442537" "57566980 | 621187161" "944481456 | 169429694" "7697999461|477558331" "3822442188 206942845" "2787118311|141642208" "2669534759 308252645" "6121516963|554616321" "5509428225|681372307" "6619817314|310054531" "1759758306 453053985" "9356970729|868811209" "4208830142 806643228" "0898841529|102183632" "9692682718|103744380" "5839709581|790845206" "7264919369|982096148"
 , , , ,0,5,2,0,1, , , ,1,1,1,3,2:16

Solución visualizada:

09492201 | 6325551
395297030 | 3792913
\ 456363431 | 275612
 \ 73230054 | 830527885
  \ 8382365 | 989887310
   \ 4 \ 87060 614168216
  87/5 - \ 4 | 96927 \ 97
 50479667 \ 74425/7
57566980 | \ 62- / 87161
944481456 | \ / 69429694
7697999461 | 477558331

¡Disfrutar!

Editar: Ahora solo estoy presumiendo (¡dos caminos se fusionan! ¿Puede hacerlo?)

948384 | 4288324 324324 | 121323
120390 | 1232133 598732 | 123844
 293009 | 2394023 432099 | 230943
 234882 | 2340909 843893 | 849728
  238984 | 328498984328 | 230949
  509093 | 904389823787 | 439898
   438989 | 3489889344 | 438984
   989789 | 7568945968 | 989455
    568956 | 56985869 | 568956
    988596 | 98569887 | 769865
     769879 | 769078 | 678977
     679856 | 568967 | 658957
      988798 | 8776 | 987979
      987878 | 9899 | 989899
       999889 | El | 989899
       989999 | El | 989999
        989898 | El | 998999
        989999 | El | 999999
         989998 || 899999
         989998 || 998999

Solución:

$ java C "948384 | 4288324   324324 | 121323" "120390 | 1232133   598732 | 123844" " 293009 | 2394023 432099 | 230943" " 234882 | 2340909 843893 | 849728" "  238984 | 328498984328 | 230949" "  509093 | 904389823787 | 439898" "   438989 | 3489889344 | 438984" "   989789 | 7568945968 | 989455" "    568956 | 56985869 | 568956" "    988596 | 98569887 | 769865" "     769879 | 769078 | 678977" "     679856 | 568967 | 658957" "      988798 | 8776 | 987979" "      987878 | 9899 | 989899" "       999889 |    | 989899" "       989999 |    | 989999" "        989898 |  | 998999" "        989999 |  | 999999" "         989998 || 899999" "         989998 || 998999"
 ,2,0,3,0,0, ,|,|, ,|,|, ,|,|, ,|,|, ,|,|, ,|,|, ,|,|, , , , , , , ,|, ,|, ,|, ,|, ,|, ,|, ,|,|, , ,1,0,7,2:15

(bonificación: camino desde ungolfed):

$ java Chicken < test5.txt
best start: 3 cost: 15
  -> 2 -> 0 -> 3 -> 0 -> 0 ->   -> | -> | ->   -> | -> | ->   -> | -> | ->   -> | -> | ->   -> | -> | ->   -> | -> | ->
  -> | -> | ->   ->   ->   ->   ->   ->   ->   -> | ->   -> | ->   -> | ->   -> | ->   -> | ->   -> | ->   -> | -> | ->
  ->   -> 1 -> 0 -> 7 -> 2 -> 15
/ -> - -> - -> \ -> / -> / -> - -> , -> , -> - -> , -> , -> - -> , -> , -> - -> , -> , -> - -> , -> , -> - -> , -> , ->
- -> , -> , -> / -> \ -> - -> - -> - -> / -> / -> ^ -> / -> ^ -> / -> ^ -> / -> ^ -> / -> ^ -> / -> ^ -> / -> , -> , ->
/ -> - -> \ -> \ -> - -> \ -> across

Detalles sobre el algoritmo

Se solicitó una explicación más completa de la técnica de programación dinámica que empleé, así que aquí va:

Estoy usando un método de solución de marcar y precomputar. Tiene un nombre propio, pero hace tiempo que lo he olvidado; quizás alguien más pueda ofrecerlo?

Algoritmo:

Comenzando en la columna más a la derecha y progresando a la izquierda, calcule lo siguiente acerca de cada celda en la columna:
- La suma del movimiento de costo más bajo, definido como costo de celda actual + celda de costo más bajo accesible en la siguiente columna
- La acción de movimiento a tomar para lograr este costo más bajo, simplemente como un movimiento válido de esta celda a otra celda.
Las tuberías son diferidas. Para resolver una tubería, debe calcular la columna completa, de modo que no calculemos tuberías hasta la siguiente columna.
- Al determinar el costo más bajo de una celda a la izquierda de una tubería, primero calculamos la mejor dirección para viajar a lo largo de la tubería: siempre se resolverá hacia arriba o hacia abajo, por lo que la calculamos una vez.
- Luego almacenamos, como con todas las otras celdas, el mejor costo (definido como el costo de la celda que alcanzamos viajando hacia arriba o hacia abajo en la tubería) y la dirección para viajar para llegar a ella.

Notas:

Eso es. Escaneamos de arriba a abajo, de derecha a izquierda, una vez; las únicas celdas tocadas (potencialmente) más de una vez son tuberías, sin embargo, cada tubería solo se "resuelve" una vez, manteniéndonos dentro de nuestra ventana O (m * n).

Para manejar tamaños de mapa "extraños", elegí simplemente preescanear y normalizar longitudes de filas rellenando con caracteres nulos. Los caracteres nulos cuentan como movimientos de "costo cero" igual que las tuberías y los espacios. Luego, al imprimir la solución, detengo los costos de impresión o los movimientos cuando se alcanza el borde de la carretera normalizada o se alcanza un carácter nulo.

La belleza de este algoritmo es que es muy simple, aplica las mismas reglas a cada celda, produce una solución completa al resolver subproblemas O (m * n), y en términos de velocidad es bastante rápido. Cambia la memoria, creando efectivamente dos copias en la memoria del mapa de carreteras, la primera para almacenar datos de "mejor costo" y la segunda para almacenar datos de "mejor movimiento" por celda; Esto es típico de la programación dinámica.

ProgramadorDan
fuente

¿Podría explicar un poco más su enfoque de las líneas? También intenté un enfoque de programación dinámica (algo diferente), pero me quedé atascado descubriendo eso. También he considerado un enfoque incremental (fila por fila) para tratar con caminos extremadamente largos que no son demasiado anchos sin usar demasiada memoria; ¿Sabes si hay una manera de hacerlo en menos de O (m ^ 2 * n) tiempo?

dfeuer

@dfeuer Se trata de las compensaciones, para estar seguro. Ninguno de los enfoques fila por fila que consideré fue capaz de manejar todas las permutaciones de entrada sin sucumbir al tiempo O (m ^ n) en algún momento; Este es un problema columna por columna por construcción (el movimiento, en gran medida, va de izquierda a derecha; la solución DP eficiente va de derecha a izquierda). Es posible que pueda hacer un enfoque O (m * n) resolviendo fila por fila con una simple retrospectiva y una vista diferida hacia adelante, pero está aumentando considerablemente la complejidad sin probablemente ahorrar mucha memoria.

ProgramadorDan

Lo que estaba pensando era que si no me equivoco, solo necesita hacer un seguimiento de la mejor ruta hasta el momento y, para cada cuadrado en la fila procesada más recientemente, las rutas más conocidas desde el borde izquierdo, hasta el borde derecho, y a cada cuadrado a su derecha en la misma fila. ¿Es eso incorrecto?

dfeuer

¡Gracias! Puede acortar su código una gota definiéndolo ccomo -1>>>1.

dfeuer

Estoy apuntando a Haskell, lo que hará que sea difícil competir por la longitud, pero es lo que mejor sé con diferencia.

dfeuer

¿Cómo cruzó el pollo la calle?

Respuestas:

Pyth, 168 143 141 bytes [ahora borracho camino compatibles]

Java, 955 bytes

Detalles sobre el algoritmo

Algoritmo:

Notas: