Mercurial > hg > aoc

comparison 2017/day10/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 10: Knot Hash ---
2
3 You come across some programs that are trying to implement a software
4 emulation of a hash based on knot-tying. The hash these programs are
5 implementing isn't very strong, but you decide to help them anyway.
6 You make a mental note to remind the Elves later not to invent their
7 own cryptographic functions.
8
9 This hash function simulates tying a knot in a circle of string with
10 256 marks on it. Based on the input to be hashed, the function
11 repeatedly selects a span of string, brings the ends together, and
12 gives the span a half-twist to reverse the order of the marks within
13 it. After doing this many times, the order of the marks is used to
14 build the resulting hash.
15
16 4--5 pinch 4 5 4 1
17 / \ 5,0,1 / \/ \ twist / \ / \
18 3 0 --> 3 0 --> 3 X 0
19 \ / \ /\ / \ / \ /
20 2--1 2 1 2 5
21
22 To achieve this, begin with a list of numbers from 0 to 255, a current
23 position which begins at 0 (the first element in the list), a skip
24 size (which starts at 0), and a sequence of lengths (your puzzle
25 input). Then, for each length:
26
27 Reverse the order of that length of elements in the list, starting
28 with the element at the current position.
29
30 Move the current position forward by that length plus the skip
31 size.
32
33
34 Increase the skip size by one.
35
36 The list is circular; if the current position and the length try to
37 reverse elements beyond the end of the list, the operation reverses
38 using as many extra elements as it needs from the front of the list.
39 If the current position moves past the end of the list, it wraps
40 around to the front. Lengths larger than the size of the list are
41 invalid.
42
43 Here's an example using a smaller list:
44
45 Suppose we instead only had a circular list containing five elements,
46 0, 1, 2, 3, 4, and were given input lengths of 3, 4, 1, 5.
47
48 The list begins as [0] 1 2 3 4 (where square brackets indicate the
49 current position).
50
51 The first length, 3, selects ([0] 1 2) 3 4 (where parentheses
52 indicate the sublist to be reversed).
53
54 After reversing that section (0 1 2 into 2 1 0), we get ([2] 1 0)
55 3 4.
56
57 Then, the current position moves forward by the length, 3, plus
58 the skip size, 0: 2 1 0 [3] 4. Finally, the skip size increases to
59 1.
60
61 The second length, 4, selects a section which wraps: 2 1) 0 ([3] 4.
62
63 The sublist 3 4 2 1 is reversed to form 1 2 4 3: 4 3) 0 ([1] 2.
64
65 The current position moves forward by the length plus the skip
66 size, a total of 5, causing it not to move because it wraps
67 around: 4 3 0 [1] 2. The skip size increases to 2.
68
69 The third length, 1, selects a sublist of a single element, and so
70 reversing it has no effect.
71
72 The current position moves forward by the length (1) plus the skip
73 size (2): 4 [3] 0 1 2. The skip size increases to 3.
74
75 The fourth length, 5, selects every element starting with the
76 second: 4) ([3] 0 1 2. Reversing this sublist (3 0 1 2 4 into 4 2
77 1 0 3) produces: 3) ([4] 2 1 0.
78
79 Finally, the current position moves forward by 8: 3 4 2 1 [0]. The
80 skip size increases to 4.
81
82
83 In this example, the first two numbers in the list end up being 3 and
84 4; to check the process, you can multiply them together to produce 12.
85
86 However, you should instead use the standard list size of 256 (with
87 values 0 to 255) and the sequence of lengths in your puzzle input.
88 Once this process is complete, what is the result of multiplying the
89 first two numbers in the list?
90
91 Your puzzle answer was 38628.
92
93 --- Part Two ---
94
95 The logic you've constructed forms a single round of the Knot Hash
96 algorithm; running the full thing requires many of these rounds. Some
97 input and output processing is also required.
98
99 First, from now on, your input should be taken not as a list of
100 numbers, but as a string of bytes instead. Unless otherwise specified,
101 convert characters to bytes using their ASCII codes. This will allow
102 you to handle arbitrary ASCII strings, and it also ensures that your
103 input lengths are never larger than 255. For example, if you are given
104 1,2,3, you should convert it to the ASCII codes for each character:
105 49,44,50,44,51.
106
107 Once you have determined the sequence of lengths to use, add the
108 following lengths to the end of the sequence: 17, 31, 73, 47, 23. For
109 example, if you are given 1,2,3, your final sequence of lengths should
110 be 49,44,50,44,51,17,31,73,47,23 (the ASCII codes from the input
111 string combined with the standard length suffix values).
112
113 Second, instead of merely running one round like you did above, run a
114 total of 64 rounds, using the same length sequence in each round. The
115 current position and skip size should be preserved between rounds. For
116 example, if the previous example was your first round, you would start
117 your second round with the same length sequence (3, 4, 1, 5, 17, 31,
118 73, 47, 23, now assuming they came from ASCII codes and include the
119 suffix), but start with the previous round's current position (4) and
120 skip size (4).
121
122 Once the rounds are complete, you will be left with the numbers from 0
123 to 255 in some order, called the sparse hash. Your next task is to
124 reduce these to a list of only 16 numbers called the dense hash. To do
125 this, use numeric bitwise XOR to combine each consecutive block of 16
126 numbers in the sparse hash (there are 16 such blocks in a list of 256
127 numbers). So, the first element in the dense hash is the first sixteen
128 elements of the sparse hash XOR'd together, the second element in the
129 dense hash is the second sixteen elements of the sparse hash XOR'd
130 together, etc.
131
132 For example, if the first sixteen elements of your sparse hash are as
133 shown below, and the XOR operator is ^, you would calculate the first
134 output number like this:
135
136 65 ^ 27 ^ 9 ^ 1 ^ 4 ^ 3 ^ 40 ^ 50 ^ 91 ^ 7 ^ 6 ^ 0 ^ 2 ^ 5 ^ 68 ^ 22 = 64
137
138 Perform this operation on each of the sixteen blocks of sixteen
139 numbers in your sparse hash to determine the sixteen numbers in your
140 dense hash.
141
142 Finally, the standard way to represent a Knot Hash is as a single
143 hexadecimal string; the final output is the dense hash in hexadecimal
144 notation. Because each number in your dense hash will be between 0 and
145 255 (inclusive), always represent each number as two hexadecimal
146 digits (including a leading zero as necessary). So, if your first
147 three numbers are 64, 7, 255, they correspond to the hexadecimal
148 numbers 40, 07, ff, and so the first six characters of the hash would
149 be 4007ff. Because every Knot Hash is sixteen such numbers, the
150 hexadecimal representation is always 32 hexadecimal digits (0-f) long.
151
152 Here are some example hashes:
153
154 The empty string becomes a2582a3a0e66e6e86e3812dcb672a272.
155
156 AoC 2017 becomes 33efeb34ea91902bb2f59c9920caa6cd.
157
158 1,2,3 becomes 3efbe78a8d82f29979031a4aa0b16a9d.
159
160 1,2,4 becomes 63960835bcdc130f0b66d7ff4f6a5a8e.
161
162 Treating your puzzle input as a string of ASCII characters, what is
163 the Knot Hash of your puzzle input? Ignore any leading or trailing
164 whitespace you might encounter.
165
166 Your puzzle answer was e1462100a34221a7f0906da15c1c979a.
167
168 Both parts of this puzzle are complete! They provide two gold stars: **