Cluck cluck. Personne ne sait pourquoi le poulet a traversé la route, peut-être qu'il y avait un beau coq de l'autre côté. Mais nous pouvons comprendre comment. Écrivez un programme qui, de gauche à droite, traverse cette (ou n'importe quelle) "route".

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

Votre programme le "traverse", se déplaçant de gauche à droite. Vous commencez sur n'importe quel nombre dans la colonne de gauche que vous aimez. De là, vous pouvez vous déplacer vers n'importe quel personnage adjacent à droite. Si vous avez commencé dans le coin supérieur gauche, 1, vous pouvez passer à 3 ou 8. Chaque numéro auquel vous allez, y compris le numéro de départ, est ajouté à une somme. Les espaces ne s'ajoutent pas à votre somme. "|" vous oblige à vous déplacer vers le haut ou vers le bas, plutôt que quelque part vers la droite. (Vous NE POUVEZ PAS avancer sur ce personnage) Votre objectif est d'arriver de l'autre côté avec la plus petite somme possible. Votre programme doit imprimer la somme à la fin, et il doit être capable de résoudre n'importe quelle route. De préférence, il pourrait également avoir une entrée pour une route, mais ce n'est pas obligatoire. Votre programme doit imprimer à la fois le chemin et la somme. Le moins d'octets de code gagne.

Pour clarifier, vous pouvez vous déplacer de diagnostic à moins que vous ne soyez sur une barre verticale. Vous ne pouvez vous déplacer de haut en bas que lorsque vous êtes sur une barre verticale.

Pour une spécification plus claire des routes, c'est essentiellement une chaîne de texte (ou un tableau de colonnes ou de lignes, si vous préférez penser de cette façon) qui suit les règles des caractères, et il ne peut rien y avoir MAIS ces caractères dans la route. Il peut y avoir n'importe quel nombre, un espace, une barre ("|") ou une nouvelle ligne. Si une route a été pavée par un ivrogne, comme dans la réponse de ProgrammerDan, c'est toujours une route valide, et votre programme doit être capable de résoudre une telle route. Elle n'est pas considérée comme une route s'il est impossible de se rendre de l'autre côté (par exemple, il n'y a aucun moyen de sortir d'une ligne droite de barres).

Votre programme n'est pas requis pour déterminer si une route n'est pas valide.

Clé:
N'importe quel nombre - ajoute le nombre à votre somme, avancez.
Espace - Avancez, rien n'est ajouté à votre somme.
"|" - Montez ou descendez, rien n'est ajouté à votre somme.

EDIT: Un exemple de solution, comme suggéré. Je ne peux pas en faire un horriblement gros, je ne peux pas monter sur un IDE pour le résoudre pour moi ATM.

Prenez cette petite route:

9191 | 8282
1919 | 2727
5555   5555

La solution serait un chemin de 1, 1, 1, 1, espace, diviseur, diviseur, espace, espace, 2, 2, 2, 2 pour un total de 12.

EDIT # 2: La solution à la première route sur cette question, telle que déterminée par les programmes Geobits et peuples, est 0,2,0,1,,,, 1,4,1,4 pour une somme de 13.

Pyth, 168 143 141 octets [désormais compatible Drunken Road]

Mon cas de test fonctionne, mais en raison d'un malentendu de ma part, il ne fonctionnera pas correctement avec l'exemple initial. Je travaille à le réparer.

Travaille maintenant pour l'exemple original et les routes ivres

Certains vraiment un peu moins laid code:

=Z.dC,++\ `MUT\|++0UT=^T5Ltu+G]?&qeeG\|<heGhH+eGeHHtb,0hbKhohNum++hed@ZhhdtedC,H_y_y.b+N]YmhohNd.:++TGT3HCm.[d\ lh.MlZ.z.z*hl.z]]0j\,t.sK\ hK

Testez-le ici

Je l'ai testé sur une route 10 + 9 x 40.

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

Java, 955 octets

Évidemment, je ne gagnerai aucun prix, étant Java et tout, mais j'aime ce problème et je voulais ajouter ma propre candidature.

Caractéristiques et limites:

• Peut supporter des routes irrégulières (super ivres!) Y compris des largeurs variables, des lignes complexes, etc.
• Attend que la route soit entrée comme paramètres lors de l'exécution; la version non golfée prend également en charge la lecture depuis stdin, mais comme la méthode d'entrée n'a pas été spécifiée, la version golfée attend la plus petite!
• Utilise une technique de programmation dynamique que je n'ai pas utilisée depuis, oh, environ 6 ans pour résoudre efficacement en temps O (n * m), où n est des lignes et m des colonnes.
  • Résout de droite à gauche, marquant la meilleure direction à prendre de l'index actuel au prochain index.
  • les "lignes" sont gérées en résolvant leur colonne, puis en les adressant si elles sont accessibles sur la colonne suivante. Ils résolvent en stockant la direction vers le haut ou vers le bas, avec le coût de la non-ligne éventuellement accessible.
• Suit, mais n'imprime pas (en version golf) l' index de départ de la meilleure solution.

Ok, assez de jibba jabba. Version golfée:

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

Selon mon habitude, github avec le code non golfé .

Solution pour la "première" route:

$ 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

Deuxième exemple:

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

Échantillon 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

Exemple de "Drunkified" de Brian:

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

Solution visualisée:

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

Prendre plaisir!

Edit: Maintenant, je montre juste (deux routes fusionnent! Peut-il y arriver?)

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

Solution:

$ 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

(bonus: chemin de non-golfé):

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

Détails sur l'algorithme

Une explication plus complète de la technique de programmation dynamique que j'ai employée a été demandée, alors voici:

J'utilise une méthode de solution de marquage et précalcul. Il a un nom propre, mais je l'ai depuis longtemps oublié; peut-être que quelqu'un d'autre peut l'offrir?

Algorithme:

• En commençant par la colonne la plus à droite et en progressant vers la gauche, calculez ce qui suit pour chaque cellule de la colonne:
  • La somme des mouvements au coût le plus bas, définie comme le coût actuel de la cellule + la cellule la moins chère accessible dans la colonne suivante
  • L'action de mouvement à entreprendre pour atteindre ce coût le plus bas, comme un simple mouvement valide de cette cellule vers une autre cellule unique.
• Les tuyaux sont différés. Pour résoudre un canal, vous devez avoir la colonne complète calculée, donc nous ne calculons pas les canaux jusqu'à la colonne suivante.
  • Lors de la détermination du coût le plus bas d'une cellule à gauche d'un tuyau, nous calculons d'abord la meilleure direction à parcourir le long du tuyau - elle sera toujours résolue soit vers le haut, soit vers le bas, donc nous la calculons une fois.
  • Nous stockons ensuite, comme pour toutes les autres cellules, le meilleur coût (défini comme le coût de la cellule que nous atteignons en remontant ou en descendant sur le tuyau) et la direction à parcourir pour l'atteindre.

Remarques:

C'est ça. Nous balayons de haut en bas, de droite à gauche, une fois; les seules cellules touchées (potentiellement) plus d'une fois sont des tuyaux, cependant, chaque tuyau n'est "résolu" qu'une seule fois, ce qui nous maintient dans notre fenêtre O (m * n).

Pour gérer les tailles de carte "impaires", j'ai choisi de simplement pré-scanner et normaliser les longueurs de lignes en remplissant les caractères par des valeurs nulles. Les caractères nuls comptent comme un "coût nul" comme les tuyaux et les espaces. Ensuite, lors de l'impression de la solution, j'arrête l'impression des coûts ou des déplacements lorsque le bord de la route normalisée est atteint ou qu'un caractère nul est atteint.

La beauté de cet algorithme est qu'il est très simple, applique les mêmes règles à chaque cellule, produisant une solution complète en résolvant les sous-problèmes O (m * n), et en termes de vitesse est assez rapide. Il échange la mémoire, créant effectivement deux copies en mémoire de la carte routière, la première pour stocker les données "au meilleur coût" et la seconde pour stocker les données "le meilleur mouvement" par cellule; c'est typique de la programmation dynamique.