How did the chicken cross the road?

Question

Cluck cluck. No one knows why the chicken crossed the road, maybe there was a good looking rooster on the other side. But we can figure out how. Write a program, that, left to right, crosses this (or any) "road".

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

Your program "crosses" it, moving left to right. You start on any number on the leftmost column you like. From there, you can move to any adjacent character to the right. If you started at the top left corner, 1, you could go to either 3 or 8. Every number you go to, including the starting number, is added to a sum. Spaces do not add to your sum. "|" forces you to move up or down, rather than somewhere to the right. (You CAN'T move forward on this character) Your goal is to get to the other side with the smallest possible sum. Your program must print out the sum at the end, and it must be able to solve any road. Preferably, it could also have input for a road, but it's not required. Your program must print both the path and the sum. Fewest bytes of code wins.

To clarify, you can move diagnally unless you are on a vertical bar. You can only move up and down when you are on a vertical bar.

For a clearer specification of roads, it is basically a string of text (Or an array of columns or rows, should you prefer to think that way) that follows the rules of the characters, and there can't be anything BUT those characters in the road. There can be any number, a space, a bar ("|"), or a newline. If a road was paved by a drunk guy, as in ProgrammerDan's answer, it is still a valid road, and your program must be able to solve such a road. It is not considered a road if it is impossible to get to the other side (For example, there is no way out of a straight line of bars).

Your program is not required to determine if a road is invalid.

Key:
Any number - adds the number to your sum, move forward.
Space - Move forward, nothing is added to your sum.
"|" - Move up or down, nothing is added to your sum.

EDIT: An example solution, as suggested. I can't make a horribly big one, I can't get on an IDE to solve it for me ATM.

Take this small road:

9191 | 8282
1919 | 2727
5555   5555

The solution would be a path of 1, 1, 1, 1, space, divider, divider, space, space, 2, 2, 2, 2 for a total of 12.

EDIT #2: The solution to the first road on this question, as determined by Geobits and peoples programs, is 0,2,0,1, , , ,1,4,1,4 for a sum of 13.

Answer 1

Pyth, 168 143 141 bytes [now Drunken Road compatible]

My test case works, but because of a misunderstanding on my part, it won't work properly with the initial example. I'm working on fixing it.

Now working for original example and drunken roads

Some REALLY slightly less ugly 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

Test it Here

I tested it on a 10+9 x 40 road.

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

Answer 2

Java, 955 bytes

Obviously not going to win any awards, being Java and all, but I love this problem and wanted to throw in my own entry.

Features and limits:

• Can support irregular roads (super drunk!) including variable widths, complex lines, etc.
• Expects road to be input as parameters on execution; the ungolfed version also supports reading from stdin, but since input method wasn't specified the golfed version expects smallest!
• Uses some dynamic programming technique I haven't used in, oh, 6 years or so to efficiently solve in O(n*m) time, where n is rows and m is columns.
  • Solves from right to left, marking the best direction to take from the current index to the next index.
  • "lines" are handled by resolving their column, then addressing them if reachable on the next column over. They resolve by storing direction up or down, with the cost of the eventually reachable non-line.
• Tracks, but doesn't print (in golf'd version) the starting index of the best solution.

Ok, enough jibba jabba. Golfed version:

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

As per my habit, github with the ungolfed code.

Solution for "first" road:

$ 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

Second example:

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

Brian Tuck's sample:

$ 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

"Drunkified" Brian's example:

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 visualized:

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

Enjoy!

Edit: Now I'm just showing off (two roadways merge! Can he make it?)

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: path from ungolfed):

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

Details on Algorithm

A more complete explanation of the Dynamic Programming technique I employed was requested, so here goes:

I'm using a mark-and-precompute method of solution. It has a proper name, but I've long since forgotten it; perhaps someone else can offer it?

Algorithm:

• Starting at the right-most column and progressing to the left, compute the following about each cell in the column:
  • The summation of lowest cost movement, defined as current cell cost + lowest cost cell reachable in the next column
  • The movement action to take to achieve this lowest cost, as simply a valid move from this cell to another single cell.
• Pipes are deferred. To resolve a pipe, you need to have the full column computed, so we don't compute pipes until the next column.
  • When determining the lowest cost of a cell to the left of a pipe, we first compute the best direction to travel along the pipe -- it will always resolve to either up, or down, so we compute it once.
  • We then store, as with all other cells, the best cost (defined as the cost of the cell we reach by travelling either up or down on the pipe) and the direction to travel to reach it.

Notes:

That's it. We scan from top to bottom, right to left, once; the only cells touched (potentially) more then once are pipes, however, each pipe is only "solved" once, keeping us within our O(m*n) window.

To handle "odd" map sizes, I chose to simply pre-scan and normalize lengths of rows by padding with null characters. Null characters count as "zero cost" moves same as pipes and spaces. Then, in printing the solution, I stop printing costs or moves when either the edge of the normalized road is reached, or a null character is reached.

The beauty of this algorithm is it's very simple, applies the same rules to every cell, producing a full solution by solving O(m*n) sub-problems, and in terms of speed is rather fast. It does trade off memory, creating effectively two copies in memory of the roadway map, the first to store "best cost" data and the second to store "best move" data per cell; this is typical for dynamic programming.