1 files changed, 179 insertions, 0 deletions
diff --git a/2020/day-09/README.org b/2020/day-09/README.org
new file mode 100644
index 0000000..db1eeab
--- /dev/null
+++ b/2020/day-09/README.org
@@ -0,0 +1,179 @@
+#+SETUPFILE: ~/.emacs.d/org-templates/level-3.org
+#+HTML_LINK_UP: ../../index.html#2020
+#+OPTIONS: toc:1
+#+EXPORT_FILE_NAME: index
+#+TITLE: Day 09 - Encoding Error
+
+* Puzzle
+- This puzzle is taken from: https://adventofcode.com/2020/day/9
+
+With your neighbor happily enjoying their video game, you turn your
+attention to an open data port on the little screen in the seat in front
+of you.
+
+Though the port is non-standard, you manage to connect it to your
+computer through the clever use of several paperclips. Upon connection,
+the port outputs a series of numbers (your puzzle input).
+
+The data appears to be encrypted with the eXchange-Masking Addition
+System (XMAS) which, conveniently for you, is an old cypher with an
+important weakness.
+
+XMAS starts by transmitting a preamble of 25 numbers. After that, each
+number you receive should be the sum of any two of the 25 immediately
+previous numbers. The two numbers will have different values, and there
+might be more than one such pair.
+
+For example, suppose your preamble consists of the numbers 1 through 25
+in a random order. To be valid, the next number must be the sum of two
+of those numbers:
+
+- 26 would be a valid next number, as it could be 1 plus 25 (or many
+  other pairs, like 2 and 24).
+- 49 would be a valid next number, as it is the sum of 24 and 25.
+- 100 would not be valid; no two of the previous 25 numbers sum to 100.
+- 50 would also not be valid; although 25 appears in the previous 25
+  numbers, the two numbers in the pair must be different.
+
+Suppose the 26th number is 45, and the first number (no longer an
+option, as it is more than 25 numbers ago) was 20. Now, for the next
+number to be valid, there needs to be some pair of numbers among 1-19,
+21-25, or 45 that add up to it:
+
+- 26 would still be a valid next number, as 1 and 25 are still within
+  the previous 25 numbers.
+- 65 would not be valid, as no two of the available numbers sum to it.
+- 64 and 66 would both be valid, as they are the result of 19+45 and
+  21+45 respectively.
+
+Here is a larger example which only considers the previous 5 numbers
+(and has a preamble of length 5):
+#+BEGIN_SRC
+35
+20
+15
+25
+47
+40
+62
+55
+65
+95
+102
+117
+150
+182
+127
+219
+299
+277
+309
+576
+#+END_SRC
+
+In this example, after the 5-number preamble, almost every number is the
+sum of two of the previous 5 numbers; the only number that does not
+follow this rule is 127.
+
+The first step of attacking the weakness in the XMAS data is to find the
+first number in the list (after the preamble) which is not the sum of
+two of the 25 numbers before it. What is the first number that does not
+have this property?
+** Part 2
+The final step in breaking the XMAS encryption relies on the invalid
+number you just found: you must find a contiguous set of at least two
+numbers in your list which sum to the invalid number from step 1.
+
+Again consider the above example:
+#+BEGIN_SRC
+35
+20
+15
+25
+47
+40
+62
+55
+65
+95
+102
+117
+150
+182
+127
+219
+299
+277
+309
+576
+#+END_SRC
+
+In this list, adding up all of the numbers from 15 through 40 produces
+the invalid number from step 1, 127. (Of course, the contiguous set of
+numbers in your actual list might be much longer.)
+
+To find the encryption weakness, add together the smallest and largest
+number in this contiguous range; in this example, these are 15 and 47,
+producing 62.
+
+What is the encryption weakness in your XMAS-encrypted list of numbers?
+* Solution
+Second part is dependent on the first part so we find the invalid number
+in all cases. =%invalid= stores the invalid number along with it's index.
+We check all possible combinations.
+
+I'm too tired to explain this in detail, maybe I'll add explanation
+later. Also, the solution isn't good.
+#+BEGIN_SRC raku
+my @numbers = "input".IO.lines>>.Int;
+my Int $solution;
+
+my Int $preamble_length = 25;
+my Int %invalid;
+
+MAIN: for @numbers.kv -> $idx, $num {
+    next if $idx < $preamble_length;
+
+    my @preamble = @numbers[$idx - $preamble_length..$idx - 1].sort;
+
+    my Bool $valid;
+    while pop @preamble -> $num_1 {
+        my $diff = $num - $num_1;
+        for @preamble -> $num_2 {
+            if $num_2 == $diff {
+                $valid = True;
+                next MAIN;
+            }
+        }
+    }
+
+    unless $valid {
+        %invalid<num> = $num;
+        %invalid<idx> = $idx;
+        $solution = %invalid<num> if $part == 1;
+        last MAIN;
+    }
+}
+
+if $part == 2 {
+    ...
+}
+
+say "Part $part: ", $solution;
+#+END_SRC
+** Part 2
+We brute force the second part too.
+#+BEGIN_SRC raku
+my @set = @numbers[0..%invalid<idx> - $preamble_length - 1];
+
+PART2: for @set.elems - 1 ... 0 -> $idx_1 {
+    for @set.elems - 1 ... 0 -> $idx_2 {
+        my $sum = [+] @set[$idx_1..$idx_2];
+        if $sum == %invalid<num> {
+            my @tmp = @set[$idx_1..$idx_2].sort;
+            $solution = @tmp[0] + @tmp[*-1];
+            last PART2;
+        }
+    }
+}
+#+END_SRC