10
\$\begingroup\$

Note: This is based on Two roads diverged in a yellow wood (part 2), a previous challenge of mine. Because of the popularity of that question and Two roads diverged in a yellow wood (part 1), I wanted to make a third. But the first 2 were too easy (a 2-byte answer on the first, a 15-byte answer on the second.) So I made something more complex...

The inspiration

This challenge is inspired by Robert Frost's famous poem, The Road Not Taken:

Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;

...2 paragraphs trimmed...

I shall be telling this with a sigh
Somewhere ages and ages hence:
Two roads diverged in a wood, and I —
I took the one less traveled by,
And that has made all the difference.

Notice the second to last line, I took the one less traveled by,.

The backstory

You were assigned to help a blind adventurer who is walking on a road and was inspired by The Road Not Taken. The adventurer is approaching a fork in the road and would like to take the path less traveled by. You must find where the adventurer actually is and tell the adventurer where to turn.

The challenge

Your goal is to find the road least traveled by on your map where the road forks. Your map is a string containing newlines (or \n, if you prefer) and has an unknown width and height. In the map, roads are made up of digits 0 to 9, the intersection are made of #s. You must find the road you are currently on, and out of the other roads the road most traveled by, and the road less traveled by for your blind adventurer. Woods in you map is represented by a space. Here is a simple map:

2   2
 1 0 
  #  
  2  
  2  

This map is 5 wide and 5 tall. Notice how the road forks in a Y shape. The Y may be oriented any way, so you must be able to understand a "rotated" map.

What the # means

Where the map forks there will be a #. This does not impact the score of any path.

What the numbers actually mean

Each path (a line of numbers, may have a bend in it) has a score. A path's score is determined by adding up its digits, so for the first example, the first path (from upper-left, clockwise) has a score of 2+1=3, the second has 2+0=2, and the third has 2+2=4. Roads may contain numbers connected diagonally.

Finding where you are

You are on the path with the highest score. The other 2 paths are the road more traveled by, and the road less traveled by. You need to find the road with the lowest score.

Telling your traveler where to go

You must tell your traveler to go "left" or "right". Keep in mind that directions are from your traveler's point of view (he is facing the fork.)

Example maps

  14
9#  
  04

Output: "right" (traveler is at the 9 road, 0+4 < 1+4

  9  
  9  
  9  
  9  
  9  
  #  
 8 8 
 8 8 
88 88
8   7

Output: "left" (traveler is at the 99999 road, 8+8+8+8+8 > 8+8+8+8+7

02468      
     #98765
13579      

Output: "right" (traveler is at the 98765 road, 0+2+4+6+8 < 1+3+5+7+9)

4 2
4 2
 # 
 4 
 4 
 2 
 2 

Output: "right" (traveler is at the 4422 road, 4+4 > 2+2)

 9   
 9   
 9   
 #   
8 7  
8  7 
8   7

Output "left" (traveler is at the 999 road, 8+8+8 > 7+7+7

Stuff to know:

  • Maps will be padded with spaces to make each line the same length.
  • You must output to STDOUT / console / file the string left or right, optionally followed by a trailing newline.
  • You must take input as either a string containing newlines, \ns, or an array/list of lines (each line is a string). Where that input is put must be a function, command-line argument, file, or STDIN one line at a time or similar. A variable is not a acceptable input device (unless it is a function parameter.) Likewise, function expressions in JS and other languages must be assigned to a variable.
  • This is , so the shortest answer in bytes wins!
  • Standard loopholes forbidden

Things you can assume

  • Your input will be valid. Nothing like this will be tested for:
0 0 0
 0 0
  #
 0 0
  • Paths' scores will never be tied.
  • The input can be of any length in width or height, less than the string limit of your language.
  • There will always be at least 1 space between the 2 paths.
  • Paths may have bends, turns, etc. These are roads, not highways.

Have any questions? Ask me below in the comments and happy golfing!

\$\endgroup\$
  • \$\begingroup\$ Will the # always be in the center horizontally? \$\endgroup\$ – David Archibald Mar 29 '17 at 17:52
  • 12
    \$\begingroup\$ I think it's time for you to use the Sandbox. And maybe find some new inspiration. At this rate, it feels more like you're promoting a poem than creating an interesting challenge series. Especially since you post the poem except in every one. We've already seen it from the first one, that's enough. \$\endgroup\$ – mbomb007 Mar 29 '17 at 18:13
  • 4
    \$\begingroup\$ Look. I've liked your challenges, but simply adding some difficulty then posting 3 without even accepting one in the pt 2 is just too fast. An edit to 2 would be good enough for the slight change of rotation, absolute output and so on. \$\endgroup\$ – David Archibald Mar 29 '17 at 18:26
  • 2
    \$\begingroup\$ It is a very different challenge from the previous ones and I like it... We can take the Y shape as granted (one path always ends on one edge and the other two on the oposing edge), right? \$\endgroup\$ – dnep Mar 30 '17 at 12:22
  • 1
    \$\begingroup\$ @dnep Yes you are right. \$\endgroup\$ – programmer5000 Mar 30 '17 at 17:19
4
\$\begingroup\$

D, 348 321 312 302 bytes

import std.stdio,std.algorithm,std.regex,std.range;void h(R,U)(R s,U r){U[2]c;foreach(L;s.map!(a=>a.array.split)){U l=L.length-1;r>1?r=l^r-2:0;l?c[]+=l*L.map!sum.array[]:c;}write(c[r]>c[!r]?"right":"left");}void main(){auto s=stdin.byLineCopy.array;!s.join.match(`\d \d`)?h(s.transposed,2UL):h(s,3UL);}

Ungolfed

import std.stdio,std.algorithm,std.regex,std.range;

void h(R,U)(R s, U reverse) {
    U[2] counts;
    /* Now that all paths are up/down, every line we need to count up has
       precisely two space-delimited parts to sum up. */
    foreach (line; s.map!(a=>a.array.split)) {
        U len = line.length - 1;
        reverse > 1 ? reverse = len ^ reverse - 2 : 0;
        len ? counts[] += len * line.map!sum.array[] : counts;
    }

    /* Switch left/right as needed based on our orientation */
    write(counts[reverse] > counts[!reverse] ? "right" : "left");
}

void main() {
    /* Treat the input as a matrix of integers */
    auto s = stdin.byLineCopy.array;

    /* If moving left/right intead of up/down, transpose */
    !s.join.match(`\d \d`)?h(s.transposed,2UL):h(s,3UL);
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Congratulations on being the first answerer! You might win this one... Can you link to D? \$\endgroup\$ – programmer5000 Mar 31 '17 at 12:13
2
\$\begingroup\$

Python 2, 304 bytes

Try it online

A=input()
S=str(A)[2:-2].replace("', '",'')
i=S.index('#')
r=len(A[0])
w=1
a=i/r
if' '<S[i-r]:w=-w;A=A[::w];a=len(A)+~a
if' '<S[i+1]:A=zip(*A[::-1]);a=i%r
if' '<S[i-1]:A=zip(*A)[::-1];a=len(A)-i%r-1
s=0
for c in' '.join(map(''.join,A[0:a])).split():s+=sum(map(int,c));s=-s
print['left','right'][::w][s>0]

This program deduces direction of roads and rotates it facing up to use my solution from part 2 of this challenge.

\$\endgroup\$
  • \$\begingroup\$ Beaten by 2 bytes! Talk about frustrating! \$\endgroup\$ – caird coinheringaahing May 17 '17 at 0:03
  • \$\begingroup\$ @user00001 that's why I cry alot \$\endgroup\$ – Dead Possum May 17 '17 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.