FazeCT Day 7: Laboratories
Part 1
You thank the cephalopods for the help and exit the trash compactor, finding yourself in the familiar halls of a North Pole research wing.
Based on the large sign that says "teleporter hub", they seem to be researching teleportation; you can't help but try it for yourself and step onto the large yellow teleporter pad.
Suddenly, you find yourself in an unfamiliar room! The room has no doors; the only way out is the teleporter. Unfortunately, the teleporter seems to be leaking magic smoke.
Since this is a teleporter lab, there are lots of spare parts, manuals, and diagnostic equipment lying around. After connecting one of the diagnostic tools, it helpfully displays error code 0H-N0, which apparently means that there's an issue with one of the tachyon manifolds.
You quickly locate a diagram of the tachyon manifold (your puzzle input). A tachyon beam enters the manifold at the location marked S; tachyon beams always move downward. Tachyon beams pass freely through empty space (.). However, if a tachyon beam encounters a splitter (^), the beam is stopped; instead, a new tachyon beam continues from the immediate left and from the immediate right of the splitter.
For example:
.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
In this example, the incoming tachyon beam (|) extends downward from S until it reaches the first splitter:
.......S.......
.......|.......
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
At that point, the original beam stops, and two new beams are emitted from the splitter:
.......S.......
.......|.......
......|^|......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
Those beams continue downward until they reach more splitters:
.......S.......
.......|.......
......|^|......
......|.|......
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
At this point, the two splitters create a total of only three tachyon beams, since they are both dumping tachyons into the same place between them:
.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............
This process continues until all of the tachyon beams reach a splitter or exit the manifold:
.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
.....|.|.|.....
....|^|^|^|....
....|.|.|.|....
...|^|^|||^|...
...|.|.|||.|...
..|^|^|||^|^|..
..|.|.|||.|.|..
.|^|||^||.||^|.
.|.|||.||.||.|.
|^|^|^|^|^|||^|
|.|.|.|.|.|||.|
To repair the teleporter, you first need to understand the beam-splitting properties of the tachyon manifold. In this example, a tachyon beam is split a total of 21 times.
Analyze your manifold diagram. How many times will the beam be split?......................................................................S......................................................................
.............................................................................................................................................
......................................................................^......................................................................
.............................................................................................................................................
.....................................................................^.^.....................................................................
.............................................................................................................................................
....................................................................^.^.^....................................................................
.............................................................................................................................................
...................................................................^.^.^.^...................................................................
.............................................................................................................................................
..................................................................^.^.^...^..................................................................
.............................................................................................................................................
.................................................................^...^.^.^.^.................................................................
.............................................................................................................................................
................................................................^.^.^...^.^.^................................................................
.............................................................................................................................................
...............................................................^.^...........^...............................................................
.............................................................................................................................................
..............................................................^.^.^.^.^.^.^...^..............................................................
.............................................................................................................................................
.............................................................^...^.^.^.^.^.^.^.^.............................................................
.............................................................................................................................................
............................................................^.^.^...^.^...^.^...^............................................................
.............................................................................................................................................
...........................................................^.^.^.^.^...^.^...^...^...........................................................
.............................................................................................................................................
..........................................................^...^.^.^.^.^...^.^.....^..........................................................
.............................................................................................................................................
.........................................................^...^.^.^...^...^.^.^.^.^.^.........................................................
.............................................................................................................................................
........................................................^.^.^...^.....^.^.^.^.^.....^........................................................
.............................................................................................................................................
.......................................................^.^.^.^.^.^.^.......^.^.^.....^.......................................................
.............................................................................................................................................
......................................................^...^.^...^...^.^.^.^.^.^.^...^.^......................................................
.............................................................................................................................................
.....................................................^.^...^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.....................................................
.............................................................................................................................................
....................................................^.^.^...^.^.....^.^.^.^.^.^.^.^...^.^....................................................
.............................................................................................................................................
...................................................^.^.^.^.^.^...^.^...^.^.^...^...^...^.^...................................................
.............................................................................................................................................
..................................................^.....^...^.^...^.^.........^.^.^.....^.^..................................................
.............................................................................................................................................
.................................................^.......^.^.^...^.^.^...^.^...^.^.^...^.^.^.................................................
.............................................................................................................................................
................................................^.^.^.^.^.^.^.^.....^...^.^...^.^.....^.^.^.^................................................
.............................................................................................................................................
...............................................^.....^.^.^...^.^.^.^.^.^.^.^.^.^.^...^.^.^.^.^...............................................
.............................................................................................................................................
..............................................^...^...^...^...^.....^.^.^.....^.^...^.^.^.^.^.^..............................................
.............................................................................................................................................
.............................................^.^.^.^.^.^...^...^.^.^.....^.^.^.^.^.^.^...^.^...^.............................................
.............................................................................................................................................
............................................^.^.^.^.^.^.....^.^.^...^.^.....^.^...^.^.^.....^.^.^............................................
.............................................................................................................................................
...........................................^.^...^.^.^...^.^.^.^.^.^.^.^...^.^...^.^.^.^.....^.^.^...........................................
.............................................................................................................................................
..........................................^.^.^.^.^.^.^.^...^.^.^.^...^.^.^...^.^.^.^.^.^.........^..........................................
.............................................................................................................................................
.........................................^.^.^.^.^.^.^...^.^.....^...^.^...^.^...^.^.^.^.^.^.^.^.^.^.........................................
.............................................................................................................................................
........................................^...^.......^.....^.^.^...^.^.^.^...^.^.^.^.^...^.^.^.....^.^........................................
.............................................................................................................................................
.......................................^.^.^...^.^...^.^.^.^.^.^.^.^.^.^.....^...^.^.^.^.^.^.^.^...^.^.......................................
.............................................................................................................................................
......................................^...^.^.^...^.^.^.^...^...^.^...^.^.^.^.^.^...^.^.....^.^.^.^.^.^......................................
.............................................................................................................................................
.....................................^.^.^.^.^...^...^.^...^...^.^.^.^.^.^.....^...^...^...^.^.^...^.^.^.....................................
.............................................................................................................................................
....................................^...^.^.^.^.^.^...^.^.^.^.^.^.^.^.^.^...^.^.^.^...^.^.^...^...^.....^....................................
.............................................................................................................................................
...................................^.^...^.^...^...^.^.....^.....^.....^.^.^.^.^.^.^.....^.^.^.^...^...^.^...................................
.............................................................................................................................................
..................................^.^...^.^.^...^.......^.^...^.^.^.^.^...^.^.^...^.^.^.....^.^.^.^.^.^.^.^..................................
.............................................................................................................................................
.................................^...^.^.....^.^.^.^.^.....^.^...^.^.^...^...^.^.^.^.^.^.^.^...^.^...^.^...^.................................
.............................................................................................................................................
................................^.^.^.^.^...^.^...^.^.^.^.^.^.^.......^.....^...^.^.^.^.^.^.^.^.^.....^.^.^.^................................
.............................................................................................................................................
...............................^...^.^...^...^...^.^.^.^.....^.....^.^.^.^.....^...^.^...^.^...^.^.^.^.^.^...^...............................
.............................................................................................................................................
..............................^.^.^.^...........^.^.^.^.^.^.^.^.^.^.^.^.^...^...^.^.^...^.^.^.^.^.^...^.^.^.^.^..............................
.............................................................................................................................................
.............................^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^...^...^...^...^.^.....^...^.^.^.^...^.^.^.............................
.............................................................................................................................................
............................^.^...^.^.^.^.^.^.^.....^.........^.^.^.^.^...^.^...^.^...^.^.^.^.^.^...^.^.^...^.^.^............................
.............................................................................................................................................
...........................^.^...^.^.^.^.^.....^.........^.^.^.^.^.....^.^.^.^.^.^.^.^.^.^.^.^...^.^.^.^...^.^.^.^...........................
.............................................................................................................................................
..........................^.^...^.^...^...^.^.^.^...^.^...^.^...^.^.^.^.^.^.......^.^.^.^.^.^.^.^.^.^.^.....^...^.^..........................
.............................................................................................................................................
.........................^.....^.^.^.^.....^.^.^...^...^...^.^...^.^...^.^...^.^.....^.^.^...^.^.^.^.^...^.^.^.^...^.........................
.............................................................................................................................................
........................^.^.^...^.^.^...^.^...^.^...^.^.^.....^.^.^.^.^.^.^...^.^.^.^.^.^.^.^.....^.^.^.^.^...^...^.^........................
.............................................................................................................................................
.......................^.^...^.^.^.^.^.^.^.^.......^...^.^.^.^.^.^.^.^.^.^.^.^...^.^.^.^.^.^...^.^.^...^.^.^.^...^.^.^.......................
.............................................................................................................................................
......................^.^.^.^.^.^.^.^.^.^.^...^.^.^.^.^...^.^.^.^.....^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.......^.^.^.^.^......................
.............................................................................................................................................
.....................^.^...^.^.^.^.^.....^.^.^.^.^...^.^.^.^.^.^...^.....^.^.^.^.^.^...^.^.....^...^.^.^.....^.^...^.^.^.....................
.............................................................................................................................................
....................^.^...^...^...^.....^.^.^.^.^...^...^.^.^.^.....^...^.^.^.^.^.^.^.^...^.^.^.^...^.^...^.....^.^.^.^.^....................
.............................................................................................................................................
...................^.^.^.^.^.^.^.^.^.^.^.^.^.^...^.^.^.^...^...^.^...^...^.^.^.^.^.^...^.....^.^...^.^.^.^.^.^.^.^.......^...................
.............................................................................................................................................
..................^.^.^.^...^.^.^.^.....^.^.^...^.^.^.^...^...^.^.^.^.^...^.^.^.....^.^.^.^.^.^...^...^.^.......^.^.^...^.^..................
.............................................................................................................................................
.................^.^.^.^.^.....^.^.^.^.^.^...^.^.^.^.^.^.^...^.......^.^.^.^.^...^.^.^.^...^.....^.^.^.^.^...^.^.^.^.....^.^.................
.............................................................................................................................................
................^.^.^...^.^.^.^.^.^.^.^.^.^.^.^...^.^...^.....^.^...^.^.^.^.........^.^.^...^.....^.^.^.....^.^...^.^.......^................
.............................................................................................................................................
...............^.^.^.^.^.^...^.^.^.....^.^.^...^.^.^.^.^.^.^...^.^.^.^.^.^.^.^.^.......^...^...^...^.^...^.^.^...^.^.^.^.^.^.^...............
.............................................................................................................................................
..............^.^.^.^.......^...^...^.^.^.^...^...^.^.^...^.^.^.......^.^.^...^...^.^.^...^...^.^.^.^.^...^.^.^.^.^.^...^...^.^..............
.............................................................................................................................................
.............^.^...^.^.^...^.^.^.^.^...^.^.^.^.....^.....^.^...^...^.^.^.^.^.^.^.^.^.^...^.....^.^.^.^.^.^.^.^...^.^...^...^...^.............
.............................................................................................................................................
............^.^.^...^.^.....^.^.^.....^...^.^...^...^.^.^.^...^.^...^.....^.......^.^.^.......^.^.^.^.^.^...^.^.....^.^.^.^.^.^.^............
.............................................................................................................................................
...........^.^.^...^.^.^.....^.^.^...^.^.^.....^.^...^...^.^.....^.^.^.^.^.^.^.^.....^.^.^.^.^...^.^...^.^.^.^.^.^.^.^...^.......^...........
.............................................................................................................................................
..........^.^.....^...^.^.^.......^.^.^.^.^.^.^.....^.^.^.^.^.^...^.^.^.^...^.^...^.^.....^.^.^.^.^...^...^.....^...^.^.^.^.^.^.^.^..........
.............................................................................................................................................
.........^.^.......^.^.^...^.^...^.^...^.^.^.^.^.^.^.^.^.....^...^.^.^.^...^.....^...^.^.^...^.^.^.^.^.^.^.^.^...^.^.^...^.^...^.^.^.........
.............................................................................................................................................
........^.^.^.^.^.......^.....^.^.^.^.^.^.....^.^.^.^.^...^.^.^.^.^...^.^...^.^...^.^.^...^.^.^.^.^.^.^.....^.^.^.^...^...^.....^.^.^........
.............................................................................................................................................
.......^...^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^...^.^.^.....^.^.^.^.^...^.^...^.^.^.^.^...^.^.^.....^.^.^.^...^.^.^.....^...^.^...^.^...^.^.......
.............................................................................................................................................
......^.^.^.^.^.^.^.....^...^.^.^.....^...^...^...^.^.^.^.^.^.^.^.^.^.^.^.^.^...^.^.^.^.^.....^.....^.^.^.^.^...^.^.^.^.^...^.^...^.^.^......
.............................................................................................................................................
.....^.^.^.......^.^.^.....^.....^.^.^.^.....^.......^.^.^.^...^.^.^.^.^.^...^.^.^.^.^.....^.^...^.^...^.^.^.^.....^.^.^.....^...^...^.^.....
.............................................................................................................................................
....^...^...^.^...^...^.^.^.^.....^.^...^.^.^.^.^.^.......^.^...^.^...^.....^.^.^.^.^.^.^.^.^.^...^.^.^.....^...^.^...^.^.^.^...^...^...^....
.............................................................................................................................................
...^.^.^.^.^.^...^.^.^...^.^.^.......^.^.^.^.^.^.^.^.^...^.^.^.^.^.^.^.^.^.^.^.....^...^.^.^.^.^.^.^.............^.^.^...^...^.^.......^.^...
.............................................................................................................................................
..^...^.^.^.^.^.^.^.^.^.......^.^.^.^...^...^.^.^.^.^.^.^.^.^.^.....^.^.^...^.....^.^.^.^.^.^.^.......^.^...^.^.^.^.^...^...^.^.^.......^.^..
.............................................................................................................................................
.^.^...^.^.^.^.^.^...^.^.^.^.^.^.^.^.....^...^.^.^...^.^.^.^.^...^.^.^.^...^.^.^.^.^.^.^...^.^.^...^.....^...^.......^.^.^...^.^...^...^.^.^.
.............................................................................................................................................In this problem, we are prompted to count how many splitters ^ can be reached from the tachyon starting position S.
In a nutshell, for each type of tiles, these are the corresponding actions:
- If the current tile is
Sor|, shoot a beam|straight down if the tile directly below is.- empty. - And if the current tile is
^, plus the tile directly above is|, the two horizontally adjacent tiles will be changed to|if they are empty.
Following the described actions, we implement a component that:
- Scan the grid from left to right, top down.
- If the current character is
Sor|, replace the character below it with|if it is.initially. - If the current character is
^and the character above it is|, we increment the result by 1 and change the two characters to the left and to the right of the current character to|if they are empty. Then, we replace the^with.and shift the scanning pointer two steps to the left to rescan from the left-splitted beam.
; ----------------------------------------------------------------------
; Component: Solver
; Args: None
solver:
push r11
push r12
push r13
push r14
mov rax, qword [width]
mul qword [height]
mov r14, rax
xor r13, r13
.read_loop:
cmp r13, r14
je .exit_loop
movzx rax, byte [matrix + r13]
cmp rax, 'S'
je .beam_down
cmp rax, '|'
je .beam_down
cmp rax, '^'
jne .continue_read_loop
mov rax, r13
xor rdx, rdx
div qword [width]
push rax
push rdx
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x + 3]
add r11, rax
movsx rax, byte [dir_y + 3]
add r12, rax
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
pop rdx
pop rax
cmp rbx, '|'
jne .continue_read_loop
add qword [result], 1
mov byte [matrix + r13], '.'
push rax
push rdx
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x + 1]
add r11, rax
movsx rax, byte [dir_y + 1]
add r12, rax
mov rdi, r11
mov rsi, r12
call position_checker
cmp rax, 1
jne .split_right
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
cmp rbx, '.'
jne .split_right
mov byte [matrix + rax], '|'
sub r13, 2
.split_right:
pop rdx
pop rax
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x + 2]
add r11, rax
movsx rax, byte [dir_y + 2]
add r12, rax
mov rdi, r11
mov rsi, r12
call position_checker
cmp rax, 1
jne .continue_read_loop
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
cmp rbx, '.'
jne .continue_read_loop
mov byte [matrix + rax], '|'
jmp .continue_read_loop
.beam_down:
mov rax, r13
xor rdx, rdx
div qword [width]
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x]
add r11, rax
movsx rax, byte [dir_y]
add r12, rax
mov rdi, r11
mov rsi, r12
call position_checker
cmp rax, 1
jne .continue_read_loop
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
cmp rbx, '.'
jne .continue_read_loop
mov byte [matrix + rax], '|'
.continue_read_loop:
inc r13
jmp .read_loop
.exit_loop:
pop r14
pop r13
pop r12
pop r11
retWith everything placed together, here is the full solution.
section .data
filename db "../problem/input.txt", 0
dir_x db 0, -1, 1, 0
dir_y db 1, 0, 0, -1
section .bss
input resb 100000
matrix resb 50000
output resb 20
result resq 1
width resq 1
height resq 1
section .text
global _start
_start:
; Open input file
mov rax, 2
mov rdi, filename
xor rsi, rsi
xor rdx, rdx
syscall
mov rbx, rax
; Read input file
xor rax, rax
mov rdi, rbx
mov rsi, input
mov rdx, 100000
syscall
; Close the file
mov rax, 3
mov rdi, rbx
syscall
; Split the lines and process them one by one
mov r8, input
xor r9, r9
mov qword [result], 0
xor r10, r10
mov r15, matrix
reader:
movzx rax, byte [r8]
test rax, rax
je solve_part
cmp rax, 10
jne continue_reader
inc r8
inc r9
inc r10
jmp reader
continue_reader:
mov [r15], rax
inc r8
inc r15
jmp reader
solve_part:
inc r10
mov qword [width], r9
mov qword [height], r10
call solver
; Print result to stdout
mov rdi, qword [result]
call print_int
; Exit the program
mov rax, 60
xor rdi, rdi
syscall
; ----------------------------------------------------------------------
; Component: Print Integer
; Args: rdi
print_int:
mov rax, rdi
mov rcx, output
add rcx, 19
mov byte [rcx], 10
mov rbx, 10
.loop:
dec rcx
xor rdx, rdx
div rbx
add dl, '0'
mov [rcx], dl
test rax, rax
jnz .loop
; Calculate length
mov rdx, output
add rdx, 20
sub rdx, rcx
; Print
mov rax, 1
mov rdi, 1
mov rsi, rcx
syscall
ret
; ----------------------------------------------------------------------
; Component: Valid position checker
; Args: rdi, rsi
position_checker:
cmp rdi, qword [width]
jae .invalid
cmp rsi, qword [height]
jae .invalid
mov rax, 1
ret
.invalid:
xor rax, rax
ret
; ----------------------------------------------------------------------
; Component: Solver
; Args: None
solver:
push r11
push r12
push r13
push r14
mov rax, qword [width]
mul qword [height]
mov r14, rax
xor r13, r13
.read_loop:
cmp r13, r14
je .exit_loop
movzx rax, byte [matrix + r13]
cmp rax, 'S'
je .beam_down
cmp rax, '|'
je .beam_down
cmp rax, '^'
jne .continue_read_loop
mov rax, r13
xor rdx, rdx
div qword [width]
push rax
push rdx
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x + 3]
add r11, rax
movsx rax, byte [dir_y + 3]
add r12, rax
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
pop rdx
pop rax
cmp rbx, '|'
jne .continue_read_loop
add qword [result], 1
mov byte [matrix + r13], '.'
push rax
push rdx
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x + 1]
add r11, rax
movsx rax, byte [dir_y + 1]
add r12, rax
mov rdi, r11
mov rsi, r12
call position_checker
cmp rax, 1
jne .split_right
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
cmp rbx, '.'
jne .split_right
mov byte [matrix + rax], '|'
sub r13, 2
.split_right:
pop rdx
pop rax
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x + 2]
add r11, rax
movsx rax, byte [dir_y + 2]
add r12, rax
mov rdi, r11
mov rsi, r12
call position_checker
cmp rax, 1
jne .continue_read_loop
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
cmp rbx, '.'
jne .continue_read_loop
mov byte [matrix + rax], '|'
jmp .continue_read_loop
.beam_down:
mov rax, r13
xor rdx, rdx
div qword [width]
mov r11, rdx
mov r12, rax
movsx rax, byte [dir_x]
add r11, rax
movsx rax, byte [dir_y]
add r12, rax
mov rdi, r11
mov rsi, r12
call position_checker
cmp rax, 1
jne .continue_read_loop
mov rax, r12
mul qword [width]
add rax, r11
movzx rbx, byte [matrix + rax]
cmp rbx, '.'
jne .continue_read_loop
mov byte [matrix + rax], '|'
.continue_read_loop:
inc r13
jmp .read_loop
.exit_loop:
pop r14
pop r13
pop r12
pop r11
retThe beam will be splitted 1703 times in total.
Part 2
With your analysis of the manifold complete, you begin fixing the teleporter. However, as you open the side of the teleporter to replace the broken manifold, you are surprised to discover that it isn't a classical tachyon manifold - it's a quantum tachyon manifold.
With a quantum tachyon manifold, only a single tachyon particle is sent through the manifold. A tachyon particle takes both the left and right path of each splitter encountered.
Since this is impossible, the manual recommends the many-worlds interpretation of quantum tachyon splitting: each time a particle reaches a splitter, it's actually time itself which splits. In one timeline, the particle went left, and in the other timeline, the particle went right.
To fix the manifold, what you really need to know is the number of timelines active after a single particle completes all of its possible journeys through the manifold.
In the above example, there are many timelines. For instance, there's the timeline where the particle always went left:
.......S.......
.......|.......
......|^.......
......|........
.....|^.^......
.....|.........
....|^.^.^.....
....|..........
...|^.^...^....
...|...........
..|^.^...^.^...
..|............
.|^...^.....^..
.|.............
|^.^.^.^.^...^.
|..............
Or, there's the timeline where the particle alternated going left and right at each splitter:
.......S.......
.......|.......
......|^.......
......|........
......^|^......
.......|.......
.....^|^.^.....
......|........
....^.^|..^....
.......|.......
...^.^.|.^.^...
.......|.......
..^...^|....^..
.......|.......
.^.^.^|^.^...^.
......|........
Or, there's the timeline where the particle ends up at the same point as the alternating timeline, but takes a totally different path to get there:
.......S.......
.......|.......
......|^.......
......|........
.....|^.^......
.....|.........
....|^.^.^.....
....|..........
....^|^...^....
.....|.........
...^.^|..^.^...
......|........
..^..|^.....^..
.....|.........
.^.^.^|^.^...^.
......|........
In this example, in total, the particle ends up on 40 different timelines.
Apply the many-worlds interpretation of quantum tachyon splitting to your manifold diagram. In total, how many different timelines would a single tachyon particle end up on?In the second part, we have to calculate how many possible paths for a tachyon beam starting from S to reach the bottom edge of the grid.
The two approaches I can think of to solve this second part is:
- Depth-first Search (DFS): Starting from
S, we recursively traverse all possible paths and just sum up the total amount of them. - Dynamic Programming (DP): We iterate the grid from left to right, top down. For each tile, we calculate how many possible ways that the current tile can be reached from any previous tiles.
For easier setup, I chose to work with the second approach.
In the DP/Memoization approach, we first find the starting position S. Let’s say the coordinate of it is (i, j), then we set dp[i][j] to 1.
Then, during iteration, for every tile at (x, y), if:
- The tile is a splitter
^, we adddp[x][y]to the counters for bottom-left and bottom-right neighbors, which means those two tiles can be reached from the current tile usingdp[x][y]ways. - The tile is either the starting position
Sor empty space., we adddp[x][y]to the counter of the tile directly below the current position, implies that from the current tile, there aredp[x][y]ways to reach the tile below.
For the result, we add the currently being accessed dp[x][y] to the final result every time a path tries to go out of bounds (either the bottom edge or the two sides).
Considering all possible cases for our DP implementation, here is the code for solver component.
; ----------------------------------------------------------------------
; Component: DP Solver
; Args: None
dp_solver:
push r8
push r12
push r13
push r14
push r15
xor r14, r14
mov rax, qword [width]
mul qword [height]
mov r15, rax
.dp_loop:
cmp r14, r15
je .done_dp_solver
mov rax, r14
xor rdx, rdx
div qword [width]
mov r12, rdx
mov r13, rax
movzx rax, byte [matrix + r14]
cmp rax, 'S'
jne .check_positive_dp
mov qword [dp + r14 * 8], 1
.check_positive_dp:
cmp qword [dp + r14 * 8], 0
je .continue_dp_loop
cmp rax, '^'
jne .else
mov rdi, r12
dec rdi
mov rsi, r13
inc rsi
call position_checker
cmp rax, 1
je .dp_down_left
mov r8, qword [dp + r14 * 8]
add qword [result], r8
jmp .check_down_right
.dp_down_left:
mov rax, rsi
mul qword [width]
add rax, rdi
mov r8, qword [dp + r14 * 8]
add qword [dp + rax * 8], r8
.check_down_right:
mov rdi, r12
inc rdi
mov rsi, r13
inc rsi
call position_checker
cmp rax, 1
je .dp_down_right
mov r8, qword [dp + r14 * 8]
add qword [result], r8
jmp .continue_dp_loop
.dp_down_right:
mov rax, rsi
mul qword [width]
add rax, rdi
mov r8, qword [dp + r14 * 8]
add qword [dp + rax * 8], r8
jmp .continue_dp_loop
.else:
mov rdi, r12
mov rsi, r13
inc rsi
call position_checker
cmp rax, 1
je .dp_down
mov r8, qword [dp + r14 * 8]
add qword [result], r8
jmp .continue_dp_loop
.dp_down:
mov rax, rsi
mul qword [width]
add rax, rdi
mov r8, qword [dp + r14 * 8]
add qword [dp + rax * 8], r8
.continue_dp_loop:
inc r14
jmp .dp_loop
.done_dp_solver:
pop r15
pop r14
pop r13
pop r12
pop r8
retIntegrate the solver into our solve.asm file, here is the final solution.
section .data
filename db "../problem/input.txt", 0
section .bss
input resb 100000
matrix resb 50000
dp resq 50000
output resb 20
result resq 1
width resq 1
height resq 1
section .text
global _start
_start:
; Open input file
mov rax, 2
mov rdi, filename
xor rsi, rsi
xor rdx, rdx
syscall
mov rbx, rax
; Read input file
xor rax, rax
mov rdi, rbx
mov rsi, input
mov rdx, 100000
syscall
; Close the file
mov rax, 3
mov rdi, rbx
syscall
; Split the lines and process them one by one
mov r8, input
xor r9, r9
mov qword [result], 0
xor r10, r10
mov r15, matrix
reader:
movzx rax, byte [r8]
test rax, rax
je solve_part
cmp rax, 10
jne continue_reader
inc r8
inc r9
inc r10
jmp reader
continue_reader:
mov [r15], rax
inc r8
inc r15
jmp reader
solve_part:
inc r10
mov qword [width], r9
mov qword [height], r10
call dp_solver
; Print result to stdout
mov rdi, qword [result]
call print_int
; Exit the program
mov rax, 60
xor rdi, rdi
syscall
; ----------------------------------------------------------------------
; Component: Print Integer
; Args: rdi
print_int:
mov rax, rdi
mov rcx, output
add rcx, 19
mov byte [rcx], 10
mov rbx, 10
.loop:
dec rcx
xor rdx, rdx
div rbx
add dl, '0'
mov [rcx], dl
test rax, rax
jnz .loop
; Calculate length
mov rdx, output
add rdx, 20
sub rdx, rcx
; Print
mov rax, 1
mov rdi, 1
mov rsi, rcx
syscall
ret
; ----------------------------------------------------------------------
; Component: Valid position checker
; Args: rdi, rsi
position_checker:
cmp rdi, qword [width]
jae .invalid
cmp rsi, qword [height]
jae .invalid
mov rax, 1
ret
.invalid:
xor rax, rax
ret
; ----------------------------------------------------------------------
; Component: DP Solver
; Args: None
dp_solver:
push r8
push r12
push r13
push r14
push r15
xor r14, r14
mov rax, qword [width]
mul qword [height]
mov r15, rax
.dp_loop:
cmp r14, r15
je .done_dp_solver
mov rax, r14
xor rdx, rdx
div qword [width]
mov r12, rdx
mov r13, rax
movzx rax, byte [matrix + r14]
cmp rax, 'S'
jne .check_positive_dp
mov qword [dp + r14 * 8], 1
.check_positive_dp:
cmp qword [dp + r14 * 8], 0
je .continue_dp_loop
cmp rax, '^'
jne .else
mov rdi, r12
dec rdi
mov rsi, r13
inc rsi
call position_checker
cmp rax, 1
je .dp_down_left
mov r8, qword [dp + r14 * 8]
add qword [result], r8
jmp .check_down_right
.dp_down_left:
mov rax, rsi
mul qword [width]
add rax, rdi
mov r8, qword [dp + r14 * 8]
add qword [dp + rax * 8], r8
.check_down_right:
mov rdi, r12
inc rdi
mov rsi, r13
inc rsi
call position_checker
cmp rax, 1
je .dp_down_right
mov r8, qword [dp + r14 * 8]
add qword [result], r8
jmp .continue_dp_loop
.dp_down_right:
mov rax, rsi
mul qword [width]
add rax, rdi
mov r8, qword [dp + r14 * 8]
add qword [dp + rax * 8], r8
jmp .continue_dp_loop
.else:
mov rdi, r12
mov rsi, r13
inc rsi
call position_checker
cmp rax, 1
je .dp_down
mov r8, qword [dp + r14 * 8]
add qword [result], r8
jmp .continue_dp_loop
.dp_down:
mov rax, rsi
mul qword [width]
add rax, rdi
mov r8, qword [dp + r14 * 8]
add qword [dp + rax * 8], r8
.continue_dp_loop:
inc r14
jmp .dp_loop
.done_dp_solver:
pop r15
pop r14
pop r13
pop r12
pop r8
retThere are 171692855075500 timelines that a single tachyon beam can end up on.
Appendix
In case the previous breakdown of the DP implementation for part two confuses you, here is the solution written in Python.
with open("../problem/input.txt", 'r') as f:
grid = f.read().splitlines()
dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
dp[0][grid[0].index("S")] = 1
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if dp[i][j] > 0:
if grid[i][j] == '^':
if i + 1 < len(grid) and j - 1 >= 0:
dp[i + 1][j - 1] += dp[i][j]
else:
res += dp[i][j]
if i + 1 < len(grid) and j + 1 < len(grid[0]):
dp[i + 1][j + 1] += dp[i][j]
else:
res += dp[i][j]
if grid[i][j] == '.' or grid[i][j] == 'S':
if i + 1 < len(grid):
dp[i + 1][j] += dp[i][j]
else:
res += dp[i][j]
print(res)