Mercurial > hg > aoc

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