Two roads diverged in a yellow wood (part 2)
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 1
s.
+`-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).
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!
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.)