Add day-10 solution

3 files changed, 445 insertions, 0 deletions

diff --git a/2020/day-10/README.org b/2020/day-10/README.org
new file mode 100644
index 0000000..429e06f
--- /dev/null
+++ b/2020/day-10/README.org
@@ -0,0 +1,303 @@
+#+SETUPFILE: ~/.emacs.d/org-templates/level-3.org
+#+HTML_LINK_UP: ../../index.html#2020
+#+OPTIONS: toc:1
+#+EXPORT_FILE_NAME: index
+#+TITLE: Day 10 - Adapter Array
+
+* Puzzle
+- This puzzle is taken from: https://adventofcode.com/2020/day/10
+
+Patched into the aircraft's data port, you discover weather forecasts of
+a massive tropical storm. Before you can figure out whether it will
+impact your vacation plans, however, your device suddenly turns off!
+
+Its battery is dead.
+
+You'll need to plug it in. There's only one problem: the charging outlet
+near your seat produces the wrong number of jolts. Always prepared, you
+make a list of all of the joltage adapters in your bag.
+
+Each of your joltage adapters is rated for a specific output joltage
+(your puzzle input). Any given adapter can take an input 1, 2, or 3
+jolts lower than its rating and still produce its rated output joltage.
+
+In addition, your device has a built-in joltage adapter rated for 3
+jolts higher than the highest-rated adapter in your bag. (If your
+adapter list were 3, 9, and 6, your device's built-in adapter would be
+rated for 12 jolts.)
+
+Treat the charging outlet near your seat as having an effective joltage
+rating of 0.
+
+Since you have some time to kill, you might as well test all of your
+adapters. Wouldn't want to get to your resort and realize you can't even
+charge your device!
+
+If you use every adapter in your bag at once, what is the distribution
+of joltage differences between the charging outlet, the adapters, and
+your device?
+
+For example, suppose that in your bag, you have adapters with the
+following joltage ratings:
+#+BEGIN_SRC
+16
+10
+15
+5
+1
+11
+7
+19
+6
+12
+4
+#+END_SRC
+
+With these adapters, your device's built-in joltage adapter would be
+rated for 19 + 3 = 22 jolts, 3 higher than the highest-rated adapter.
+
+Because adapters can only connect to a source 1-3 jolts lower than its
+rating, in order to use every adapter, you'd need to choose them like
+this:
+
+- The charging outlet has an effective rating of 0 jolts, so the only
+  adapters that could connect to it directly would need to have a
+  joltage rating of 1, 2, or 3 jolts. Of these, only one you have is an
+  adapter rated 1 jolt (difference of 1).
+- From your 1-jolt rated adapter, the only choice is your 4-jolt rated
+  adapter (difference of 3).
+- From the 4-jolt rated adapter, the adapters rated 5, 6, or 7 are valid
+  choices. However, in order to not skip any adapters, you have to pick
+  the adapter rated 5 jolts (difference of 1).
+- Similarly, the next choices would need to be the adapter rated 6 and
+  then the adapter rated 7 (with difference of 1 and 1).
+- The only adapter that works with the 7-jolt rated adapter is the one
+  rated 10 jolts (difference of 3).
+- From 10, the choices are 11 or 12; choose 11 (difference of 1) and
+  then 12 (difference of 1).
+- After 12, only valid adapter has a rating of 15 (difference of 3),
+  then 16 (difference of 1), then 19 (difference of 3).
+- Finally, your device's built-in adapter is always 3 higher than the
+  highest adapter, so its rating is 22 jolts (always a difference of 3).
+
+In this example, when using every adapter, there are 7 differences of 1
+jolt and 5 differences of 3 jolts.
+
+Here is a larger example:
+#+BEGIN_SRC
+28
+33
+18
+42
+31
+14
+46
+20
+48
+47
+24
+23
+49
+45
+19
+38
+39
+11
+1
+32
+25
+35
+8
+17
+7
+9
+4
+2
+34
+10
+3
+#+END_SRC
+
+In this larger example, in a chain that uses all of the adapters, there
+are 22 differences of 1 jolt and 10 differences of 3 jolts.
+
+Find a chain that uses all of your adapters to connect the charging
+outlet to your device's built-in adapter and count the joltage
+differences between the charging outlet, the adapters, and your device.
+What is the number of 1-jolt differences multiplied by the number of
+3-jolt differences?
+** Part 2
+To completely determine whether you have enough adapters, you'll need to
+figure out how many different ways they can be arranged. Every
+arrangement needs to connect the charging outlet to your device. The
+previous rules about when adapters can successfully connect still apply.
+
+The first example above (the one that starts with 16, 10, 15) supports
+the following arrangements:
+#+BEGIN_SRC
+(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22)
+(0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22)
+(0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22)
+(0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22)
+(0), 1, 4, 7, 10, 12, 15, 16, 19, (22)
+#+END_SRC
+
+(The charging outlet and your device's built-in adapter are shown in
+parentheses.) Given the adapters from the first example, the total
+number of arrangements that connect the charging outlet to your device
+is 8.
+
+The second example above (the one that starts with 28, 33, 18) has many
+arrangements. Here are a few:
+#+BEGIN_SRC
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 48, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 48, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 46, 49, (52)
+
+(0), 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31,
+32, 33, 34, 35, 38, 39, 42, 45, 47, 48, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+46, 48, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+46, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+47, 48, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+47, 49, (52)
+
+(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
+48, 49, (52)
+#+END_SRC
+
+In total, this set of adapters can connect the charging outlet to your
+device in 19208 distinct arrangements.
+
+You glance back down at your bag and try to remember why you brought so
+many adapters; there must be more than a trillion valid ways to arrange
+them! Surely, there must be an efficient way to count the arrangements.
+
+What is the total number of distinct ways you can arrange the adapters
+to connect the charging outlet to your device?
+* Solution
+=@adapters= will hold all the joltages.
+#+BEGIN_SRC raku
+sub MAIN (
+    Int $part where * == 1|2 = 1 #= part to run (1 or 2)
+) {
+    my $solution;
+
+    # Initialize @adapters with charging outlet joltage. @adapters
+    # will hold joltages of each adapter.
+    my @adapters = 0;
+    append @adapters, "input".IO.lines>>.Int.sort;
+    push @adapters, @adapters[*-1] + 3; # push the built in joltage.
+
+    if $part == 1 {
+        ...
+    } elsif $part == 2 {
+        ...
+    }
+
+    say "Part $part: ", $solution;
+}
+#+END_SRC
+
+FOr part 1 we just loop over =@adapters= & note down the number of
+difference of 3's & 1's. Then we just multiply them to get the solution.
+#+BEGIN_SRC raku
+my Int ($diff_1, $diff_3);
+
+for 0 .. @adapters.end - 1 -> $idx {
+    # joltage difference.
+    my $diff = @adapters[$idx + 1] - @adapters[$idx];
+    $diff_1++ if $diff == 1;
+    $diff_3++ if $diff == 3;
+}
+$solution = $diff_1 * $diff_3;
+#+END_SRC
+** Part 2
+For part 2, we need to use the concept of memoization otherwise the code
+will take forever to run. I got to know of this from [[https://youtube.com/watch?t=1&v=cE88K2kFZn0][Johnathan's video]].
+This sub =complete-chain= is direct translation from his solution.
+=complete-chain= returns the number of ways to complete a chain given the
+index.
+
+To find the number of ways we can complete an adapter chain, we just
+loop over =$idx + 1= to all adapters. Then we check if the adapter
+difference is less than or equal to 3, if true then we add the number of
+ways to complete the next adapter to =$ways= & return =$ways=.
+
+#+BEGIN_SRC raku
+my @memoize;
+# complete-chain returns the number of ways to complete the
+# chain given that you're currently at @adapters[$idx]. This
+# is taken from Jonathan Paulson's solution.
+sub complete-chain (
+    Int $idx
+) {
+    return 1 if $idx == @adapters.end;
+    return @memoize[$idx] if @memoize[$idx];
+
+    my Int $ways;
+    for $idx + 1 .. @adapters.end {
+        if @adapters[$_] - @adapters[$idx] <= 3 {
+            $ways += complete-chain($_);
+        }
+    }
+    @memoize[$idx] = $ways;
+    return $ways;
+}
+$solution = complete-chain(0);
+#+END_SRC
+
+So this will start at 0 & then go on until it reaches the last adapter,
+which just returns 1 as seen from first statement in the sub
+=complete-chain=.
+
+Without memoization this would take much longer to complete because we
+would be doing a lot of repeated calculation. Say the length of
+=@adapters= is 3 (0, 1, 2). This is how things will work if we pass 0
+to =complete-chain=:
+#+BEGIN_SRC
+# without memoization
+
+complete-chain(0)           # 1, 2 will satisfy the if condition
+- find complete-chain(1)    # 2 will satisfy the if condition
+  - find complete-chain(2)
+- find complete-chain(2)
+#+END_SRC
+
+Look at how we had to compute =complete-chain(2)= twice. =@adapters= was too
+small memoization is not required here but as =@adapters= grow, we will be
+computing a lot of things multiple times. And wasted computation will
+grow exponentially with growth in =@adapters=.
+
+So we introduce =@memoize=, it'll hold the values for things we've already
+computed. With memoization the example shown above will become:
+#+BEGIN_SRC
+# without memoization
+
+complete-chain(0) and store in @memoize[0]           # 1, 2 will satisfy the if condition
+- find complete-chain(1) and store in @memoize[1]    # 2 will satisfy the if condition
+  - find complete-chain(2) and store in @memoize[2]
+- no need to find complete-chain(2), get it from @memoize[2]
+#+END_SRC
+
+We didn't have to compute =complete-chain(2)= twice, we just get the value
+from =@memoize[2]=. This is called top-down approach with memoization.
+These things are covered under "Dynamic Programming".
diff --git a/2020/day-10/day-10.raku b/2020/day-10/day-10.raku
new file mode 100755
index 0000000..803de0a
--- /dev/null
+++ b/2020/day-10/day-10.raku
@@ -0,0 +1,48 @@
+#!/usr/bin/env raku
+
+sub MAIN (
+    Int $part where * == 1|2 = 1 #= part to run (1 or 2)
+) {
+    my $solution;
+
+    # Initialize @adapters with charging outlet joltage. @adapters
+    # will hold joltages of each adapter.
+    my @adapters = 0;
+    append @adapters, "input".IO.lines>>.Int.sort;
+    push @adapters, @adapters[*-1] + 3; # push the built in joltage.
+
+    if $part == 1 {
+        my Int ($diff_1, $diff_3);
+
+        for 0 .. @adapters.end - 1 -> $idx {
+            # joltage difference.
+            my $diff = @adapters[$idx + 1] - @adapters[$idx];
+            $diff_1++ if $diff == 1;
+            $diff_3++ if $diff == 3;
+        }
+        $solution = $diff_1 * $diff_3;
+    } elsif $part == 2 {
+        my @memoize;
+        # complete-chain returns the number of ways to complete the
+        # chain given that you're currently at @adapters[$idx]. This
+        # is taken from Jonathan Paulson's solution.
+        sub complete-chain (
+            Int $idx
+        ) {
+            return 1 if $idx == @adapters.end;
+            return @memoize[$idx] if @memoize[$idx];
+
+            my Int $ways;
+            for $idx + 1 .. @adapters.end {
+                if @adapters[$_] - @adapters[$idx] <= 3 {
+                    $ways += complete-chain($_);
+                }
+            }
+            @memoize[$idx] = $ways;
+            return $ways;
+        }
+        $solution = complete-chain(0);
+    }
+
+    say "Part $part: ", $solution;
+}
diff --git a/2020/day-10/input b/2020/day-10/input
new file mode 100644
index 0000000..f8eeb97
--- /dev/null
+++ b/2020/day-10/input
@@ -0,0 +1,94 @@
+38
+23
+31
+16
+141
+2
+124
+25
+37
+147
+86
+150
+99
+75
+81
+121
+93
+120
+96
+55
+48
+58
+108
+22
+132
+62
+107
+54
+69
+51
+7
+134
+143
+122
+28
+60
+123
+82
+95
+14
+6
+106
+41
+131
+109
+90
+112
+1
+103
+44
+127
+9
+83
+59
+117
+8
+140
+151
+89
+35
+148
+76
+100
+114
+130
+19
+72
+36
+133
+12
+34
+46
+15
+45
+87
+144
+80
+13
+142
+149
+88
+94
+61
+154
+24
+66
+113
+5
+73
+79
+74
+65
+137
+47