Two roads diverged in a yellow wood (part 2)

Question

This is the second in a series, the third is Two roads diverged in a yellow wood (part 3)

This is based on Two roads diverged in a yellow wood (part 1), a previous challenge of mine. It was fairly well received, but it was also fairly trivial (a Java answer in 52 bytes!) 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,. Your goal is to find the road least travelled by in your string input. You must output one of 2 values that are distinct from each other that signal which way you should turn to take the road less traveled by. Once the road forks (the trail of hexagons changes to numbers) you are at the intersection. From there, there will be 2 paths made up of digits. The path whose digits has the lowest sum will be the road not taken. Note that the road not taken may have a larger path but a lower path sum. Here are some examples / test cases from a program that prints "left" or "right" for the path not taken:

 1     2
  1   2
   1 2
    #
    #
    #
left (3 < 6)


 1     2
  2   2
   1 1
    #
    #
    #
left (4 < 5)


 12    2
  11  2
   1 1
    #
    #
    #
right (6 > 5)


 99   989
  99  89
  99 99
  99 99
    #
    #
    #
   # 
left (72 < 79)


1111 1110
 001 111
  11 11
  11 11
    #
   ##
  ##
 ##  
left (9 < 10) (Note: 1111 is interpreted as 1+1+1+1=4, not 1111=1111)


1       1
 0     1
  1   1
  1   1
  1   1
  1   1
   1 1 
    #
    #
    #
     #
      #
left (6 < 7)


1   1 
 0   1  
  1   1
  1   1
  1   1
  1   1
   1 1 
    #
    #
    #
     #
      #
left (6 < 7)

Things to assume & remember

• There will always be 2 paths. No more, no less.
• You can take input from STDIN one line at a time, a string containing LF characters, or a string containing a literal backslash and a n. If you need input in any other way, ask for approval in the comments.
• You don't have to worry about invalid input or tied paths. Those will never be inputted to your program / function.
• The input can be of any length in width or height, less than the string limit of your language.
• There will never be a # and a number in the same line.
• All digits in the path are positive integers 0 to 9.
• Input or output with a trailing newline is allowed.
• See my JS ES6 answer below for an example.
• There will always be at least 1 space between the 2 paths.
• The 2 paths will always have the same height for each map, but may be different on other maps.
• If you are confused about a specific test case, please tell me.
• 1111 is interpreted as 1+1+1+1=4, not 1111=1111. The map is a series of one-digit numbers, not numbers of arbitrary length.
• This is code-golf, so the shortest answer in bytes wins!
• Standard loopholes forbidden

If you have any questions about this challenge, ask me in the comments, and good luck!

Answer 1

Retina, 28 bytes

\d
$*
%r`1\G
-
Os`.
+`-1

1+

Try it online!

Prints 0 for left and 1 for right. Assumes that there are not trailing spaces on any lines.

Explanation

\d
$*

Convert each digit N to a run of N ones.

%r`1\G
-

One each line (%), match consecutive (\G) ones from the end (r) and replace each of them with - (i.e. turn the right branch into -s).

Os`.

Sort all characters, so that all -s are directly in front of all 1s.

+`-1

Repeatedly cancel a pair of - and 1.

1+

Try to match at least one 1 (if so, there were more weights in the left path).

Answer 2

Chip, 216 bytes

 EZ,Z~.
E~]x-.|
F].>vm'
Ax]}#----------------.
Bx]}#---------------.|z.
Cx]}#------------.,Z|##' E
Dx]}#---------.,Z|`@@('A~^~t
 E.>#------.,Z|`@@-('
A~S`#v--.,Z|`@@-('
*f,--<,Z|`@@-('
e |,Z|`@@-('
,Z|`@@-('
>@@-('
a

Try it online!

A little bigger than the answer for part 1...

Overview

Chip is a 2D language inspired by actual circuitry, and it deals with the component bits of each byte in a byte stream.

This solution keeps a running sum of the digits it sees, flipping the sign of the input each time it encounters a stretch of whitespace, then terminating upon the first #. So, for input

 11   12
  2   2
   1 1
    #
    #
    #

We get 1 + 1 - 1 - 2 + 2 - 2 + 1 - 1 = -1. The sign of the result is given as the output, a negative number produces the result 1, and positive is 0.

Therefore, output of 1 means that the left path is less taken, and 0 means right.

Explanation

At a high level, this is how it works:

The main diagonal with the @ elements is the accumulator, output is decided by the a at the bottom. (Eight pairs of @ means eight bits, but the highest bit is the sign, so this solution can handle a maximum difference of +127 or -128. Overflowing partway through is okay, as long as we come back before terminating.)

The four lines that start like Ax]}#--... are reading the input, and in the case of a digit, negating it (if necessary) and passing the value into the adders.

The first three lines decide if we are looking at a digit, or a sequence of whitespace, and keep track of whether the digits need to be negated.

The remaining elements wedged in under the inputs and the elements at far right handle the termination condition, and map the output to ASCII (so that we get characters '0' or '1' instead of values 0x0 or 0x1. This ASCII mapping required no extra bytes, otherwise I wouldn't have included it.)

Answer 3

Python 2, 95 89 88 87 bytes

Here is my first go at this in python. Definitely not optimal but a decent start.

f=lambda x,i:sum(sum(map(int,y))for y in x.split()[i::2]if"#"<y)
lambda x:f(x,1)>f(x,0)

Try it online!

Answer 4

JavaScript (ES6), 55 bytes

x=>x.replace(/\d(?=.*( )|)/g,(d,s)=>t-=s?d:-d,t=0)&&t<0

Assumes there are no trailing spaces on each line, and outputs true for right, false for left. The trick is to match each digit in the input, and if there is a space after it on the same line, subtract it from the total; otherwise, add it to the total. If the final total is less than 0, the right road is the one less traveled by, and vice versa.

Try it out:

f=x=>x.replace(/\d(?=.*( )|)/g,(d,s)=>t-=s?d:-d,t=0)&&t<0

<textarea placeholder = "paste in a map here..." oninput = "document.querySelector('div').innerText = f(this.value)"></textarea>
<div></div>

Answer 5

Python 3, 85 94 bytes

import re
g=lambda s,i:sum(map(int,''.join(re.findall('\d+',s)[i::2])))
lambda s:g(s,0)>g(s,1)

Try it online!

Curses! Didn't read the problem close enough. Added a the fix (''.join()), but at the cost of 9 bytes.

Answer 6

Python 2, 78 bytes

-1 byte thanks to @math_junkie

Try it online

def F(S,r=0):
 for c in S.split():
    if'#'<c:r+=sum(map(int,c));r=-r
 print r>0

Prints False for left path and True for right

Answer 7

05AB1E, 21 15 bytes

Outputs 0 for left and 1 for right.

|vy#õK€SO})øO`›

Try it online!

Explanation

|v                # for each line in input
  y#              # split on spaces
    õK            # remove empty strings
      €S          # split each string into a list of chars
        O         # sum each sublist
         }        # end loop
          )ø      # wrap stack in a list and zip
            O     # sum each sublist (side of the tree)
             `›   # compare left to right

Answer 8

Retina, 180 bytes

Byte count assumes ISO 8859-1 encoding.

^(?=( *(0|(1|(?<3>2|(?<3>3|(?<3>4|(?<3>5|(?<3>6|(?<3>7|(?<3>8|(?<3>9))))))))))+.+¶)+)(.+ (0|(?<-3>1|(?<-3>2|(?<-3>3|(?<-3>4|(?<-3>5|(?<-3>6|(?<-3>7|(?<-3>8|(?<-3>9))))))))))+¶)+ *#

Try it online!

I thought I'd also try a regex-only solution (the above is a plain .NET regex which matches only inputs where the right path should be taken, except for using ¶ as a shorthand for \n).

It's annoyingly repetitive, but that's what happens when you have to treat each possible digit individually.

The solution is a fairly straight-forward application of balancing groups: first we sum the digits in the left branch by pushing N captures onto stack 3 for each digit N. Then we try to reach the #, while popping from stack 3 N times for each digit N in the right branch. This is only possible if the sum of digits in the left branch is greater than that in the right branch (since you can't pop from an empty stack).

Answer 9

JavaScript (ES6), 106 104 bytes

s=b=>(b=b.split`\n`,c=0,d=0,b.forEach(a=>{a=a.match(/\d+/g)||[],c+=+(a[0]?a[0]:0),d+=+(a[1]?a[1]:0)}),c<d)

s=b=>(b=b.split("\n"),c=0,d=0,b.forEach(a=>{a=a.match(/\d+/g)||[],c+=+(a[0]?a[0]:0),d+=+(a[1]?a[1]:0)}),c<d)

s is a function that returns true if the road not taken is on the left. Ungolfed:

var proc = function(str){
    str = str.split("\n");
    var left = 0;
    var right = 0;
    str.forEach(item=>{
        var match = item.match(/\d+/g) || [];
        console.log(match);
        left += +(match[0] ? match[0] : 0);
        right += +(match[1] ? match[1] : 0);
    });
    return left < right;
};

s=b=>(b=b.split`\n`,c=0,d=0,b.forEach(a=>{a=a.match(/\d+/g)||[],c+=+(a[0]?a[0]:0),d+=+(a[1]?a[1]:0)}),c<d)

<textarea placeholder = "paste in a map here..." oninput = "document.querySelector('div').innerText = s(this.value)"></textarea>
<div></div>

Answer 10

CJam, 19 18 bytes

qN/Sf%z{'1*:~:+}/>

Try it online!

Prints 0 for left and 1 for right.

Explanation

q      e# Read all input.
N/     e# Split into lines.
Sf%    e# Split each line around runs of spaces.
z      e# Transpose to group each branch.
       e# Note that each branch will have the same number of digit segments
       e# now but the first branch will also have all the #s at the end in
       e# separate segments.
{      e# For each branch...
  '1*  e#   Join the segments into a single string with 1s as separators.
       e#   This will add the same number of 1s between digit segments in
       e#   both branches (which won't affect their relative sum) and it 
       e#   will also insert a 1 before each # in the first branch.
  :~   e#   Evaluate each character. The digit characters are simply turned
       e#   into their values, but # is the exponentiation operator in CJam.
       e#   This is why we inserted those additional 1s, because 1# is a no-op.
  :+   e#   Sum the digits in the branch.
}/
>      e# Check whether the left branch's sum is greater than the right one's.

Answer 11

PowerShell, 80 bytes

$args-split'\s|#'-ne''|%{$a+=(($i=[char[]]$_-join'+'|iex),-$i)[($x=!$x)]};$a-gt0

Try it online!

(Just squeaking under the Python answers. :D)

Outputs True for the left path and False for the right path.

Takes input as a string delineated with `n, which is the PowerShell equivalent of "a string containing a literal backslash and a n", or as a literal multiline string. We then -split that input on \s (whitespace including newlines) or # and filter out all the empty results -ne'', so we're left with just an array of the digits. Those are fed into a loop |%{...}.

Each iteration, we first take the current element $_, cast it as a char array, -join it together with a plus sign +, and pipe it to iex (short for Invoke-Expression and similar to eval). That's stored into $i so we properly sum up the digits on this particular chunk of the path. We then use that and its negative as the two elements of an array ($i, -$i), indexed into by flipping a Boolean value back and forth. Meaning, the first iteration through this loop, the first left path chunk, we'll index into -$i; the next time, we'll take $i; and so on. Those are accumulated into $a with +=.

Finally, we evaluate whether $a is -greaterthan 0. If it is, then the right path had a larger sum, otherwise the left path had a larger sum. That Boolean result is left on the pipeline, and output is implicit.

Answer 12

Python 3, 84 bytes

Since all the current Python submissions are functions, I thought I'd contribute a full program.

x=0
try:
 while 1:
  for n in input().split():x=-x+sum(map(int,n))
except:print(x>0)

Prints True if the left path is less traveled, False otherwise. Try it online!

For each line of input, this splits on whitespace, sums the digits of each resulting element, and adds it to a tally while flipping the sign of the tally at each step. It continues reading lines of input until it hits one with a #, at which point map(int,n) raises an exception and we exit the loop, printing True if the tally is positive and False otherwise.

Answer 13

Mathematica, 80 77 bytes

Thanks to Martin Ender for saving 3 bytes!

#<#2&@@Total@Partition[Tr/@ToExpression[Characters@StringSplit@#/."#"->0],2]&

Pure function taking a newline-delimited string as input, and returning True to take the left path, False to take the right path. Damn those long Mathematica command names; this is like 10 tokens.

Answer 14

Java 10, 219 216 208 162 146 bytes

s->{int l=0,i;for(var x:s.split("\n"))for(i=2;!x.contains("#")&i-->0;)for(int c:x.trim().split("\\s+")[i].getBytes())l+=i>0?48-c:c-48;return l>0;}

Bit longer than 52 21 bytes this time. ;)
Returns false for right and true for left.

-24 bytes thanks to @ceilingcat.

Try it online.

Explanation:

s->{                              // Method with String parameter & boolean return-type
  int l=0,                        //  Counter, starting at 0
      i;                          //  Temp integer `i`
  for(var x:s.split("\n"))        //  Loop over the lines:
      for(i=2;!x.contains("#")&   //   Skip lines that doesn't contain "#":
              i-->0;)             //    Inner loop `i` in the range (2,0]:
        for(int c:x.trim()        //     Remove the leading/trailing whitespaces from
                                  //     the current line
                   .split("\\s+") //     Then split it on whitespaces
                     [i]          //     Get the `i`'th part
                   .getBytes())   //     And inner loop over the bytes of this part:
          l+=i>0?                 //      If `i` is 1:
              48-c                //       Decrease the counter by this digit
             :                    //      Else (`i` is 0):
              c-48;               //       Increase the counter by this digit
  return l>0;}                    //  Return whether the counter is positive

Answer 15

Pip, 19 18 bytes

LR+XDax:-x+$+$0SGx

Takes input as a single string on the command line (which will need quoting and escaping of newlines if run on an actual command line). Outputs -1 for left, 1 for right. Try it online!

Explanation

Loops over runs of digits, adding the digit sums to a tally. The sign of the tally is swapped each time, with the end result that the left-hand values are negative and the right-hand values are positive. Then we print the sign of the final tally (-1 or 1).

                    a is 1st cmdline arg; XD is regex `\d`; x is "" (implicit)
                    Note that "" in a math context is treated as 0
  +XD               Apply regex + to XD (resulting in `\d+`)
LR   a              Loop over matches of that regex in a:
             $0      Regex match variable containing the full match
           $+        Sum digits by folding on +
      x:-x+          Swap the sign of the tally and add this sum
               SGx  After the loop, print the sign of the tally

Answer 16

Haskell, 64 bytes

g=sum.map fromEnum
f(a:b:r)|a>"#"=g a-g b+f r|1<3=0
(>0).f.words

Try it online! Usage: The anonymous function (>0).f.words takes a newline separated string as argument and returns False for left and True for right.

Explanation:

Given an input

 99   989
  99  89
  99 99
    #
    #
   # 

that is the string " 99 989\n 99 89\n 99 99\n #\n #\n #", then words strips all newlines and spaces and returns a list of the remaining strings: ["99","989","99","89","99","99","#","#","#"]. The function f takes the first two elements a and b from this list and checks whether a is a string of digits by comparing it to the string "#". (Because the char '#' is smaller than all the digit chars '0', '1', ... every string starting with a digit will be lexicographically larger than "#".) The function g maps each char in a string to its ascii character code and returns their sum. In f we apply g to a and b and compute g a - g b, that is the value of the left path minus the value of the right one, and add it to a recursive call to f to handle the following lines. If the left path is more travelled the result from f will be negative and otherwise positive for the right path, so (>0) checks if the result is larger than zero.

Answer 17

Batch, 169 bytes

@echo off
set/as=0
:l
set/pr=
if not %r: =%==# call:c - %r%&goto l
cmd/cset/a"s>>9
exit/b
:c
call:r + %3
:r
set/as%1=%2%%10,d=%2/10
if %d% gtr 0 call:r %1 %d%

Prints 0 for left, -1 for right. Note: Reads lines until it finds one with a #, then stops reading. The difference in path sums is limited to 511 (add 1 byte to support larger differences). No more than 9 digits in each row of each path (supports any number of rows). Explanation: The d subroutine takes two parameters: whether to add or subtract and the digit(s). It extracts the last digit by modulo by 10 and the remaining digits by dividing by 10 and calls itself recursively while there are still digits remaining. The c subroutine takes three parameters: whether to add or subtract, the digits to add or subtract, and further digits to add. It calls the d subroutine to handle the digits to add and then falls through to handle the first two parameters. This means that calling the c subroutine with the parameters of - and the left and right digits will add the right digits and subtract the left digits. Finally the result is shifted to extract the sign.

Answer 18

Octave, 46 bytes

@(a)diff((a(:)-48)'*(bwlabel(a>35)(:)==1:2))<0

Try it online! A function that takes a 2D character array a as input.

Explanation:

a=

    1   1  
     0   1 
      1   1
      1   1
      1   1
      1   1
       1 1 
        #  
        #  
        #  
         # 
          #

a > 35                   %convert the matrix to a binary matrix
                         %where there is a number corresponing
                         %element of the binary matrix is 1.
         
*   *  
 *   * 
  *   *
  *   *
  *   *
  *   *
   * * 

bwlabel(a>35)            %label each connected component. 


1   2  
 1   2 
  1   2
  1   2
  1   2
  1   2
   1 2 
  
B=bwlabel(a>35)(:)==1:2  % a binary `[n ,2]` matrix created 
                         % each column related to one of labels
                    
A=(a(:)-48)'             % convert array of characters to array of numbers 
                     
A * B                    % matrix multiplication that computes 
                         % the sum of numbers under each label

diff(A*B)<0              % check if the left is grater than the right

Answer 19

Batch 104 223 bytes

• missed the fact that numbers must be counted on a per charcater basis. Answer updated

@Echo off&Set/aa=0&For /f "tokens=1,2" %%1 in (%1)Do (Set c=%%1&Set d=%%2
For %%n in (c d)Do For /l %%i in (0 1 9)Do Call Set %%n=%%%%n:%%i=%%i+%%%%
2>nul Call Set/Aa+=%%c%%0,a-=%%d%%0)
IF %A% GTR 0 (Echo(R)Else echo(L

• Input is from file passed as argument - %1

• splits each line into two tokens

• inserts a + character between each number [building a sum]

• Increments a with sum of left token, decrements with sum of right token

• Outputs L or R

---

Sidenote: the test cases in this question dont fail if taking the path of just summing the 1st and 2nd column of each line.

I made use of the follwing test case:

 034  060
  1  1
  2 0
   0 2
    #
    #
    #
   #