Cluck cluck. Ninguém sabe por que a galinha atravessou a rua, talvez houvesse um galo bonito do outro lado. Mas podemos descobrir como. Escreva um programa que, da esquerda para a direita, atravesse esta (ou qualquer) "estrada".

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

Seu programa "atravessa", movendo-se da esquerda para a direita. Você inicia com qualquer número na coluna da esquerda que desejar. A partir daí, você pode mover para qualquer caractere adjacente à direita. Se você começou no canto superior esquerdo, 1, pode ir para 3 ou 8. Todos os números que você acessa, incluindo o número inicial, são adicionados a uma soma. Os espaços não são adicionados à sua soma. "|" força você a subir ou descer, em vez de algum lugar à direita. (Você NÃO PODE avançar nesse personagem) Seu objetivo é chegar ao outro lado com a menor soma possível. Seu programa deve imprimir a soma no final e deve poder resolver qualquer estrada. De preferência, ele também pode ter entrada para uma estrada, mas não é necessário. Seu programa deve imprimir o caminho e a soma. Menos bytes de código vencidos.

Para esclarecer, você pode mover o diagnóstico, a menos que esteja em uma barra vertical. Você só pode mover para cima e para baixo quando estiver em uma barra vertical.

Para uma especificação mais clara das estradas, é basicamente uma sequência de texto (ou uma matriz de colunas ou linhas, se você preferir pensar dessa maneira) que segue as regras dos caracteres e não pode haver nada além desses caracteres. a estrada. Pode haver qualquer número, um espaço, uma barra ("|") ou uma nova linha. Se uma estrada foi pavimentada por um cara bêbado, como na resposta do ProgrammerDan, ainda é uma estrada válida e seu programa deve ser capaz de resolvê-la. Não é considerada uma estrada se for impossível chegar ao outro lado (por exemplo, não há como sair de uma linha reta de barras).

Seu programa não é necessário para determinar se uma estrada é inválida.

Tecla:
Qualquer número - adiciona o número à sua soma, avança.
Espaço - Avançar, nada é adicionado à sua soma.
"|" - Mover para cima ou para baixo, nada é adicionado à sua soma.

EDIT: Um exemplo de solução, conforme sugerido. Não posso fazer uma coisa horrivelmente grande, não consigo entrar em um IDE para resolvê-lo para mim ATM.

Pegue esta pequena estrada:

9191 | 8282
1919 | 2727
5555   5555

A solução seria um caminho de 1, 1, 1, 1, espaço, divisor, divisor, espaço, espaço, 2, 2, 2, 2 para um total de 12.

EDIT # 2: A solução para o primeiro caminho nesta questão, conforme determinado pelos programas Geobits e povos, é 0,2,0,1,,,, 1,4,1,4 para uma soma de 13.

Pyth, 168 143 141 bytes [agora compatível com Drunken Road]

Meu caso de teste funciona, mas devido a um mal-entendido da minha parte, ele não funcionará corretamente com o exemplo inicial. Estou trabalhando para consertá-lo.

Agora trabalhando para o exemplo original e estradas bêbadas

Algum código REALMENTE um pouco menos feio :

=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

Teste aqui

Eu testei em uma estrada 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 bytes

Obviamente, não vou ganhar nenhum prêmio, sendo Java e tudo, mas eu amo esse problema e queria lançar minha própria entrada.

Recursos e limites:

• Pode suportar estradas irregulares (super bêbadas!), Incluindo larguras variáveis, linhas complexas, etc.
• Espera que a estrada seja inserida como parâmetros na execução; a versão ungolfed também suporta a leitura do stdin, mas como o método de entrada não foi especificado, a versão golfed espera a menor!
• Utiliza alguma técnica de programação dinâmica que não uso há, oh, 6 anos ou mais, para resolver com eficiência em O (n * m), onde n é linhas e m são colunas.
  • Resolve da direita para a esquerda, marcando a melhor direção a seguir do índice atual para o próximo índice.
  • "linhas" são tratadas através da resolução de suas colunas e, em seguida, abordando-as se possível na próxima coluna. Eles resolvem armazenando a direção para cima ou para baixo, com o custo da não-linha eventualmente alcançável.
• Rastreia, mas não imprime (na versão golf) o índice inicial da melhor solução.

Ok, chega de jibba jabba. Versão Golfed:

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

De acordo com meu hábito, o github com o código não destruído .

Solução para a "primeira" estrada:

$ 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 exemplo:

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

Amostra 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

Exemplo "bêbado" 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

Solução 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

Desfrutar!

Edit: Agora estou apenas exibindo (duas estradas se fundem! Ele consegue?)

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

Solução:

$ 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

(bônus: caminho do não-destruído):

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

Detalhes sobre o algoritmo

Foi solicitada uma explicação mais completa da técnica de Programação Dinâmica que empreguei, então aqui vai:

Estou usando um método de solução de marcação e pré-cálculo. Tem um nome próprio, mas há muito que o esqueci; talvez alguém possa oferecer isso?

Algoritmo:

• Começando na coluna mais à direita e progredindo para a esquerda, calcule o seguinte sobre cada célula da coluna:
  • A soma do menor custo de movimento, definido como custo atual da célula + menor custo da célula alcançável na próxima coluna
  • A ação de movimento a ser realizada para atingir esse custo mais baixo, como simplesmente uma movimentação válida dessa célula para outra célula única.
• Tubos são adiados. Para resolver um canal, você precisa computar a coluna completa, para que não computemos os canais até a próxima coluna.
  • Ao determinar o menor custo de uma célula à esquerda de um tubo, primeiro calculamos a melhor direção para viajar ao longo do tubo - ele sempre resolverá subir ou descer, e então calculamos uma vez.
  • Em seguida, armazenamos, como em todas as outras células, o melhor custo (definido como o custo da célula que alcançamos ao viajar para cima ou para baixo no cano) e a direção para viajar para alcançá-lo.

Notas:

É isso aí. Digitalizamos de cima para baixo, da direita para a esquerda, uma vez; as únicas células tocadas (potencialmente) mais de uma vez são tubos, no entanto, cada tubo é "resolvido" apenas uma vez, mantendo-nos dentro da nossa janela O (m * n).

Para lidar com tamanhos de mapa "ímpares", optei por pré-digitalizar e normalizar comprimentos de linhas preenchendo caracteres nulos. Caracteres nulos contam como "custo zero" se move da mesma maneira que tubulações e espaços. Em seguida, ao imprimir a solução, paro de imprimir os custos ou os movimentos quando a borda da estrada normalizada é atingida ou um caractere nulo é atingido.

A beleza desse algoritmo é que é muito simples, aplica as mesmas regras a todas as células, produzindo uma solução completa resolvendo subproblemas de O (m * n) e, em termos de velocidade, é bastante rápido. Ele troca memória, criando efetivamente duas cópias na memória do roteiro, a primeira a armazenar dados de "melhor custo" e a segunda a armazenar dados de "melhor movimentação" por célula; isso é típico para programação dinâmica.