Note: If you’re attempting to read this as a Fediverse post, you might find it rather confusing. I recommend using a web browser to read it properly, following this link.
The challenge
As often, we have a field. On the top, we have a beam pointing downwards. Whenever a beam hits a splitter, marked by a ^ symbol, it gets split in 2 and continues its path downwards as 2 beams, just left and right of its original position, where it might get split again.
How many times the original beam gets split?
The idea
The algorithm is straight forward: As we follow the beam(s) downwards, we check for every position if there is a splitter and if a beam is pointing at this position. If so, we increase our counter by 1. We also need to remove the beam and to add 1 just to the left and 1 just to the right of the current beam.
The updated challenge
Now assume that a splitter doesn’t actually split the beam in two, but that it might actually go left or right. How many possible paths are there leading from top to bottom?
The updated idea
With hundreds of splitters, there are going to be a lot of paths. Fortunately, we don’t have to remember all the paths! For every splitter in a given line, we only need to know, how many paths led to this position. We just have to add this number to the left and right positions of the next line.
Leave a Reply