Day 5: A Maze of Twisty Trampolines, All Alike

Read through today’s challenge text. As usual, I’ve quoted the crux of the challenge below and highlighted the key words.

Start at the first instruction in the list. The goal is to follow the jumps until one leads outside the list. In addition, these instructions are a little strange; after each jump, the offset of that instruction increases by 1.

Our input file contains the list of jumps. We need to look at the current position so we know where to jump to next, increase the value of the current position, and then jump to the new position. We will keep doing this until we jump off the end of the list. We also need to keep a count of how many jumps we have done.

Solving Part 1

As always, let’s start with our example input, 0 3 0 1 -3, save this as variable l (that’s a lowercase L not a number 1).

q)l:0 3 0 1 -3

We need a variable to keep track of our current position, let’s call that variable p

q)p:0 / we start at the first instruction, which is at position zero

We could also do with a variable to keep track of how far we are jumping, variable j

q)j:0 / we have nowhere to jump yet

.. and we need a variable to keep track of how many jumps we have done, lets use c

q)c:0 / we haven't jumped anywhere yet

We need to perform the following steps:

get the jump offset for the current position
increase the jump offset for the current position by one
increase our jump counter by one
jump to the new position

To break that down into code, we need to:

update j with the value of l at position (index) p
increase the value of l at position (index) p by 1
increase the counter c by 1
add the jump j to position p

To put that into Q code:

j:l[p]  / set j to l at index p
l[p]+:1 / update the value of l at index p by 1
c+:1    / update the value of c by one
p+:j    / add the jump offset to position p

We need to keep doing this until we jump past the end of our list. If you try to index into a list past it’s end (or before it’s start) you will get a null of the type of the first item in the list. For example:

q)(1 2 3 4) 4      / this will return a null long
0N
q)"abcd" 4         / this will return a null character (empty space)
" "
q)`a`b`c`d 4       / this will return the null symbol (backtick)
`
q)(`a;1;1.5;"h") 4 / this will return a null symbol (type of first item in the list)
`

We can confirm that ON is null with the null operator

q)null (1 2 3 4) 4
1b

Let’s do all the steps one-by-one and look at how our list variable l compares against the example:

q)j:l[p]
q)l[p]+:1
q)c+:1
q)p+:j
q)l
1 3 0 1 -3

This looks good. Let’s see whether l[p] would be null:

q)null l[p]
0b

Nope, it’s not null, so we run through these steps again:

q)j:l[p]
q)l[p]+:1
q)c+:1
q)p+:j
q)l / check that this matches the example
2 3 0 1 -3

Let’s see whether l[p] would be null now…

q)null l[p]
0b

Nope. So let’s go again, but in order to save time note that we can run all commands on a single line by separating them with a semicolon (;)

q)j:l[p]; l[p]+:1; c+:1; p+:j / note that we don't need the spaces, that's just for clarity

Let’s check to see our list matches the example, and see whether we’ve jumped off the end of the list:

q)l
2 4 0 1 -3
q)null l[p]
0b

We are still within our list, and our list l is still matching the examples; looking good. Let’s go once again:

q)j:l[p]; l[p]+:1; c+:1; p+:j
q)l
2 4 0 1 -2
q)null l[p]
0b

Ok, this next one should push us over the end:

q)j:l[p]; l[p]+:1; c+:1; p+:j
q)l
2 5 0 1 -2
q)null l[p] / now we would fall off the end of the list!
1b

If you lost track of how many times we did that, let’s check our counter, c

q)c
5

Perfect. Well almost… It’s pretty tedious typing that all in manually… there ought to be a better way - and there is. We can use the while operator to keep performing the same step (or steps) while a particular condition is true.

The structure for a while loop is shown below:

while[ / condition that will evaluate to true or false;
  / do these operations;
  / separated each one by semicolons;
  / we don't need a semicolon after the last statement
  ]

In this case we want to keep doing the jumping until l[p] is null. Flipping this on it’s head we want to do the jumping while l[p] is not null.

If we were using a text editor we could write it across multiple lines like so:

while[not null l[p];
  j:l[p];  / set j to l at index p
  l[p]+:1; / update the value of l at index p by 1
  c+:1;    / update the value of c by one
  p+:j]    / add the jump offset to position p

… but if we want to run at the Q prompt, we need to join everything together into a single line:

while[not null l[p];j:l[p];l[p]+:1;c+:1;p+:j]

To make sure this works, we can reset our list l, our position p, jump j, and jump counter c, perform the while loop, and then check that variable c contains 5 as expected:

q)l:0 3 0 1 -3
q)c:0
q)p:0
q)j:0
q)while[not null l[p];j:l[p];l[p]+:1;c+:1;p+:j]
q)c
5

Great. Now we need to run against our puzzle input.

As usual we want to use read0 to read the file into our session:

q)read0 `:input/05.txt
,"2"
,"2"
,"0"
,"0"
"-2"

We’ve been given each offset as a new line in the file, we need to convert these characters into longs, so let’s use the big-J cast and see how that looks

q)"J"$read0 `:input/05.txt
2 2 0 0 -2 -1 -3 0 0 -3 -5 -5 1 -10 -8 -1 -8 -5 -12 -5 1 -6 -18 -17 -9 -12 -24 -16 -6 -12 -14 -15 -28 -1 -10 -2 -2 0 -16 -4 -22 -33 -34 -28 -41 -11 -16 -12 -25 -13 -12 -14 -17 -24 -48 -54 -7 -10 -8 -49 -24 -49 -39 -8 -53 2 -65 -55 -52 1 ..

This looks like a list of longs, but let’s double-check the type to be sure

q)type "J"$read0 `:input/05.txt
7h

Great. Let’s call this l like before.

q)l:"J"$read0 `:input/05.txt

Now reset our jump, counter and position variables back to 0:

q)p:c:j:0 / this is a shortcut method of setting all three to zero!

Then run our while-loop code, and check c to get today’s first star!

q)while[not null l[p];j:l[p];l[p]+:1;c+:1;p+:j]
q)c
343467

Solving Part 2

Now, the jumps are even stranger: after each jump, if the offset was three or more, instead decrease it by 1. Otherwise, increase it by 1 as before.

Part 2 is very similar to Part 1 with one small change; rather than always increasing the value in the current position by 1, we need to check whether the jump was 3 or more (greater-or-equal to three) and if so, decrease the value by one (or increase by -1) instead.

We could write an if-else statement in Python as follows:

if jump >= 3:
  current_value += 1
else:
  current_value += -1

We have the equivalent of an if-else conditional statement in Q too in the form of cond which looks like this:

$[condition to check;execute this if true;execute this if false]

The condition we want to check is whether j >= 3, and if true we want to do l[p]+:-1, and if false we want to do l[p]+:1. Putting this together gives us

$[j >= 3;l[p]+:-1;l[p]+:1]

We can simplify this further by setting the value of l[p] based on the outcome of the condition:

l[p]+:$[j >= 3;-1;1]

Greater-or-equal to 3 (>=3) is the same as greater than 2 (>2), so let’s simplify further:

l[p]+:$[j>2;-1;1]

We therefore need to switch out our old statement l[p]+:1 for the new l[p]+:$[j>2;-1;1] in our while loop:

while[not null l[p];
  j:l[p];
  l[p]+:$[j>2;-1;1]; / this is the only change between parts 1 and 2!
  c+:1;
  p+:j]

Or as a single line:

while[not null l[p];j:l[p];l[p]+:$[j>2;-1;1];c+:1;p+:j]

Before we let loose on our input file, we should double-check against the example:

q)l:0 3 0 1 -3 / reset the list
q)p:j:c:0 / reset position, jump and count
q)while[not null l[p];j:l[p];l[p]+:$[j>2;-1;1];c+:1;p+:j] / run our while loop
q)c / this should be 10...
10

Great. So, reset p, j and c again and run against the input file to get our second star

q)l:"J"$read0 `:input/05.txt
q)p:j:c:0 / reset position, jump and count
q)while[not null l[p];j:l[p];l[p]+:$[j>2;-1;1];c+:1;p+:j] / note it will take around 30 seconds to run!
q)c
24774780

Complete Solution To Day 5

We don’t need to initialise the jump variable j outside of the loop, we can initialise it as part of the while condition itself.

This means that my solution to Day 5 looks like this: