Mercurial > hg > aoc

comparison 2017/day18/problem @ 34:049fb8e56025

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add problem statements and inputs
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 09 Jan 2018 21:51:44 -0500
parents
children
comparison
equal deleted inserted replaced
33:bc652fa0a645 34:049fb8e56025
1 --- Day 18: Duet ---
2
3 You discover a tablet containing some strange assembly code labeled
4 simply "Duet". Rather than bother the sound card with it, you decide
5 to run the code yourself. Unfortunately, you don't see any
6 documentation, so you're left to figure out what the instructions mean
7 on your own.
8
9 It seems like the assembly is meant to operate on a set of registers
10 that are each named with a single letter and that can each hold a
11 single integer. You suppose each register should start with a value of
12 0.
13
14 There aren't that many instructions, so it shouldn't be hard to figure
15 out what they do. Here's what you determine:
16
17 snd X plays a sound with a frequency equal to the value of X.
18
19 set X Y sets register X to the value of Y.
20
21 add X Y increases register X by the value of Y.
22
23 mul X Y sets register X to the result of multiplying the value
24 contained in register X by the value of Y.
25
26 mod X Y sets register X to the remainder of dividing the value
27 contained in register X by the value of Y (that is, it sets X to
28 the result of X modulo Y).
29
30 rcv X recovers the frequency of the last sound played, but only
31 when the value of X is not zero. (If it is zero, the command does
32 nothing.)
33
34 jgz X Y jumps with an offset of the value of Y, but only if the
35 value of X is greater than zero. (An offset of 2 skips the next
36 instruction, an offset of -1 jumps to the previous instruction,
37 and so on.)
38
39
40 Many of the instructions can take either a register (a single letter)
41 or a number. The value of a register is the integer it contains; the
42 value of a number is that number.
43
44 After each jump instruction, the program continues with the
45 instruction to which the jump jumped. After any other instruction, the
46 program continues with the next instruction. Continuing (or jumping)
47 off either end of the program terminates it.
48
49 For example:
50
51 set a 1
52 add a 2
53 mul a a
54 mod a 5
55 snd a
56 set a 0
57 rcv a
58 jgz a -1
59 set a 1
60 jgz a -2
61
62 The first four instructions set a to 1, add 2 to it, square it,
63 and then set it to itself modulo 5, resulting in a value of 4.
64
65 Then, a sound with frequency 4 (the value of a) is played.
66
67 After that, a is set to 0, causing the subsequent rcv and jgz
68 instructions to both be skipped (rcv because a is 0, and jgz
69 because a is not greater than 0).
70
71 Finally, a is set to 1, causing the next jgz instruction to
72 activate, jumping back two instructions to another jump, which
73 jumps again to the rcv, which ultimately triggers the recover
74 operation.
75
76
77 At the time the recover operation is executed, the frequency of the
78 last sound played is 4.
79
80 What is the value of the recovered frequency (the value of the most
81 recently played sound) the first time a rcv instruction is executed
82 with a non-zero value?
83
84 Your puzzle answer was 7071.
85
86 --- Part Two ---
87
88 As you congratulate yourself for a job well done, you notice that the
89 documentation has been on the back of the tablet this entire time.
90 While you actually got most of the instructions correct, there are a
91 few key differences. This assembly code isn't about sound at all -
92 it's meant to be run twice at the same time.
93
94 Each running copy of the program has its own set of registers and
95 follows the code independently - in fact, the programs don't even
96 necessarily run at the same speed. To coordinate, they use the send
97 (snd) and receive (rcv) instructions:
98
99 snd X sends the value of X to the other program. These values wait
100 in a queue until that program is ready to receive them. Each
101 program has its own message queue, so a program can never receive
102 a message it sent.
103
104 rcv X receives the next value and stores it in register X. If no
105 values are in the queue, the program waits for a value to be sent
106 to it. Programs do not continue to the next instruction until they
107 have received a value. Values are received in the order they are
108 sent.
109
110
111 Each program also has its own program ID (one 0 and the other 1); the
112 register p should begin with this value.
113
114 For example:
115
116 snd 1
117 snd 2
118 snd p
119 rcv a
120 rcv b
121 rcv c
122 rcv d
123
124 Both programs begin by sending three values to the other. Program 0
125 sends 1, 2, 0; program 1 sends 1, 2, 1. Then, each program receives a
126 value (both 1) and stores it in a, receives another value (both 2) and
127 stores it in b, and then each receives the program ID of the other
128 program (program 0 receives 1; program 1 receives 0) and stores it in
129 c. Each program now sees a different value in its own copy of register
130 c.
131
132 Finally, both programs try to rcv a fourth time, but no data is
133 waiting for either of them, and they reach a deadlock. When this
134 happens, both programs terminate.
135
136 It should be noted that it would be equally valid for the programs to
137 run at different speeds; for example, program 0 might have sent all
138 three values and then stopped at the first rcv before program 1
139 executed even its first instruction.
140
141 Once both of your programs have terminated (regardless of what caused
142 them to do so), how many times did program 1 send a value?
143
144 Your puzzle answer was 8001.
145
146 Both parts of this puzzle are complete! They provide two gold stars: **