Day 5
Day 5 Part 1
--- Day 5: A Maze of Twisty Trampolines, All Alike ---
An urgent interrupt arrives from the CPU: it's trapped in a maze of jump instructions, and it would like assistance from any programs with spare cycles to help find the exit.
The message includes a list of the offsets for each jump. Jumps are relative: -1 moves to the previous instruction, and 2 skips the next one. 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. So, if you come across an offset of 3, you would move three instructions forward, but change it to a 4 for the next time it is encountered.
For example, consider the following list of jump offsets:
0
3
0
1
-3
Positive jumps ("forward") move downward; negative jumps move upward. For legibility in this example, these offset values will be written all on one line, with the current instruction marked in parentheses. The following steps would be taken before an exit is found:
(0) 3 0 1 -3 - before we have taken any steps.
(1) 3 0 1 -3 - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1.
2 (3) 0 1 -3 - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2.
2 4 0 1 (-3) - jump all the way to the end; leave a 4 behind.
2 (4) 0 1 -2 - go back to where we just were; increment -3 to -2.
2 5 0 1 -2 - jump 4 steps forward, escaping the maze.
In this example, the exit is reached in 5 steps.
How many steps does it take to reach the exit?
Solution
I lost some time debugging because I was printing i at the end and counting the steps.
import sys
def main():
ans = 0
i = 0
temp = []
for line in sys.stdin:
temp.append(int(line))
while True:
ans += 1
j = i
i = j + temp[j]
temp[j] = temp[j] + 1
if (i < 0 or i >= len(temp)):
break
print i
print ans
main()
Finished debugging and entered my solution at 11 minutes and 37 seconds which was rank 878, my worst finish in terms of ranking to date.
Day 5 Part 2
--- Part Two ---
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.
Using this rule with the above example, the process now takes 10 steps, and the offset values after finding the exit are left as 2 3 2 3 -1.
How many steps does it now take to reach the exit?
Solution
import sys
def main():
ans = 0
i = 0
temp = []
for line in sys.stdin:
temp.append(int(line))
while True:
ans += 1
j = i
i = j + temp[j]
if temp[j] > 2:
temp[j] -= 1
else:
temp[j] += 1
if (i < 0 or i >= len(temp)):
break
print ans
main()
Part 2 was much easier although it was much slower, taking around 7 seconds to complete. My total rank was 12 minutes and 50 seconds which an overall rank of 707.
Benchmarking
I had been using Python 2 but I wanted to benchmark part 2 with Python 3 and PyPy (which is a more performant version of Python which is supposed to be faster due to a Just-in-Time compiler. I just had to modify the print statement for Python 3 compatibility to print(ans)
$ time pypy 5_2.py < 5.in
27763113
real 0m0.212s
user 0m0.183s
sys 0m0.026s
$ time python 5_2.py < 5.in
27763113
real 0m6.974s
user 0m6.950s
sys 0m0.016s
$ time python3 5_2.py < 5.in
27763113
real 0m10.834s
user 0m10.736s
sys 0m0.048s
Wow, PyPy was over an order of magnitude faster than Python 2 and Python 3 performed the worst! In the future, I’ll be using pypy which is also fewer keystrokes.
Another minor optimization I discovered was that I could turn off the Vim Syntastic Python warnings using this Vim command: :let g:syntastic_quiet_messages = { "level": "warnings" }. This allows me to focus on the actual errors rather than all the warnings about missing docstrings and invalid module names. However, this needs to be run every time a new file is open unless it is added to your vimrc.
We had a Elm LA meetup at work today so I had to take a break to do the Advent of Code challenge for the day. Unfortunately, I didn’t give myself enough time to setup and was slightly distracted by my surroundings.
Day 6
Day 6 Part 1
--- Day 6: Memory Reallocation ---
A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.
In this area, there are sixteen memory banks; each memory bank can hold any number of blocks. The goal of the reallocation routine is to balance the blocks between the memory banks.
The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.
The debugger would like to know how many redistributions can be done before a blocks-in-banks configuration is produced that has been seen before.
For example, imagine a scenario with only four memory banks:
- The banks start with 0, 2, 7, and 0 blocks. The third bank has the most blocks, so it is chosen for redistribution.
- Starting with the next bank (the fourth bank) and then continuing to the first bank, the second bank, and so on, the 7 blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: 2 4 1 2.
- Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: 3 1 2 3.
- Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: 0 2 3 4.
- The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: 1 3 4 1.
- The third bank is chosen, and the same thing happens: 2 4 1 2.
At this point, we've reached a state we've seen before: 2 4 1 2 was already seen. The infinite loop is detected after the fifth block redistribution cycle, and so the answer in this example is 5.
Given the initial block counts in your puzzle input, how many redistribution cycles must be completed before a configuration is produced that has been seen before?
Solution
I first attempted to use while not a in seen but I couldn’t seem to get that to work so I just used the for loop at the end of the while loop to check for list equality instead. The actual bug that I had was that I was doing seen.append(a) instead ofseen.append(a[:])soa` was always in seen after one iteration of the loop. It took me a little bit of time to debug this and I wasted time adding the for loop.
import sys
def main():
ans = 0
seen = []
for line in sys.stdin:
a = list(map(int, line.strip().split()))
print a
while True:
seen.append(a[:])
max_idx = a.index(max(a))
count = max(a)
a[max_idx] = 0
i = (max_idx + 1) % len(a)
while count > 0:
count -= 1
a[i] += 1
i = (i + 1) % len(a)
ans += 1
for l in seen:
if a == l:
print ans
return
main()
Here is the slightly shorter original solution:
import sys
def main():
ans = 0
seen = []
for line in sys.stdin:
a = list(map(int, line.strip().split()))
print a
while not a in seen:
seen.append(a[:])
max_idx = a.index(max(a))
count = max(a)
a[max_idx] = 0
i = (max_idx + 1) % len(a)
while count > 0:
count -= 1
a[i] += 1
i = (i + 1) % len(a)
ans += 1
main()
Day 6 Part 2
--- Part Two ---
Out of curiosity, the debugger would also like to know the size of the loop: starting from a state that has already been seen, how many block redistribution cycles must be performed before that same state is seen again?
In the example above, 2 4 1 2 is seen again after four cycles, and so the answer in that example would be 4.
How many cycles are in the infinite loop that arises from the configuration in your puzzle input?
Solution
The first two strategies that came to mind were either to get the output from the previous run and just run it again or just add a second loop that did the same thing. This is terrible software engineering and doesn’t follow the DRY (don’t repeat yourself) principle. Short term speed makes us do terrible things.
import sys
def main():
ans = 0
seen = []
for line in sys.stdin:
a = list(map(int, line.strip().split()))
print a
done = False
while not done:
seen.append(a[:])
max_idx = a.index(max(a))
count = max(a)
a[max_idx] = 0
i = (max_idx + 1) % len(a)
while count > 0:
count -= 1
a[i] += 1
i = (i + 1) % len(a)
ans += 1
for l in seen:
if a == l:
print ans
done = True
seen = []
done = False
ans = 0
while not done:
seen.append(a[:])
max_idx = a.index(max(a))
count = max(a)
a[max_idx] = 0
i = (max_idx + 1) % len(a)
while count > 0:
count -= 1
a[i] += 1
i = (i + 1) % len(a)
ans += 1
for l in seen:
if a == l:
print ans
done = True
main()
I actually forgot to ans = 0 line between the two loops but when the result was larger, I realized my mistake right away and just subtracted it before inputting my answer. I could have saved even more time by just using the index of the final list in the seen array in which case I would just have had to add one line of code.
import sys
def main():
ans = 0
seen = []
for line in sys.stdin:
a = list(map(int, line.strip().split()))
print a
while not a in seen:
seen.append(a[:])
max_idx = a.index(max(a))
count = max(a)
a[max_idx] = 0
i = (max_idx + 1) % len(a)
while count > 0:
count -= 1
a[i] += 1
i = (i + 1) % len(a)
ans += 1
print ans - seen.index(a)
main()
Surprisingly PyPy was actually slower than Python 2 for today’s problems by about a factor of 2.
$ time python 6_2.py < 6.in
2392
real 0m0.701s
user 0m0.674s
sys 0m0.016s
$ time pypy 6_2.py < 6.in
2392
real 0m1.544s
user 0m1.417s
sys 0m0.050s
Results
My drought continues but at least I’m learning from my mistakes. I will also go back and try to understand the difference between PyPy and Python and the use cases in which each is stronger.
You have 37 points.
-------Part 1-------- -------Part 2--------
Day Time Rank Score Time Rank Score
6 00:10:22 225 0 00:12:16 183 0
5 00:11:37 878 0 00:12:50 707 0
4 00:03:14 265 0 00:06:50 283 0
3 00:11:39 162 0 00:39:18 258 0
2 00:06:21 450 0 00:13:29 393 0
1 00:03:32 86 15 00:05:32 79 22
I still haven’t scored any points since Day 1 but it’s been a fun experiment.