Two roads diverged in a yellow wood (part 3)

10

1

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!

programmer5000

Posted 2017-03-29T17:22:44.027

Reputation: 7 828

Will the # always be in the center horizontally? – David Archibald – 2017-03-29T17:52:34.940

@David no, I added a example map to show that. – programmer5000 – 2017-03-29T17:54:08.420

I don't think I'm gonna make a javascript one under 100 bytes. The rotation just kills it all. – David Archibald – 2017-03-29T17:56:10.043

@David This question is different from the others, even a 1000 byte answer would be winning (so far) – programmer5000 – 2017-03-29T17:57:22.717

12

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.

– mbomb007 – 2017-03-29T18:13:12.643

4Look. 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. – David Archibald – 2017-03-29T18:26:07.010

Could you add a test case where the paths have "bends, turns, etc."? – DLosc – 2017-03-29T20:17:12.003

2It 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? – dnep – 2017-03-30T12:22:50.087

Possibly new tag for series like these: [tag:neverending-series]? – Matthew Roh – 2017-03-30T13:34:57.890

1@dnep Yes you are right. – programmer5000 – 2017-03-30T17:19:50.400

@SIGSEV I promise this is the last one. – programmer5000 – 2017-03-30T17:20:05.967

Shouldn't the traveler turn right in the fourth example? If they're on the 2244 road, heading towards the fork, then the 22 path is on their right. – Ray – 2017-03-31T01:47:03.820

@Ray Yes, you are correct. I fixed that. – programmer5000 – 2017-03-31T12:13:10.753

There´s a mistake in the second example too: Traveller should be on the 88888 road (score: 40). However, "left" is the correct reslut (84+7=39, 94=36). Or do "most traveled by" imply the average value? Then, you should mention averages in your explanations, not sums. – Titus – 2017-03-31T12:38:55.687

@Titus Fixed that. – programmer5000 – 2017-03-31T12:40:41.087

... and the third example should be 44 -> left. ;) – Titus – 2017-03-31T12:42:08.060

@Titus what do you mean? The example with 44, 22, and 4422? – programmer5000 – 2017-03-31T12:44:47.733

Answers

4

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!

Ray

Posted 2017-03-29T17:22:44.027

Reputation: 1 488

Congratulations on being the first answerer! You might win this one... Can you link to D? – programmer5000 – 2017-03-31T12:13:56.590

2

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.

Dead Possum

Posted 2017-03-29T17:22:44.027

Reputation: 3 256

Beaten by 2 bytes! Talk about frustrating! – caird coinheringaahing – 2017-05-17T00:03:47.823

@user00001 that's why I cry alot – Dead Possum – 2017-05-17T08:26:07.887