summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2020-12-12 20:02:30 +0530
committerAndinus <andinus@nand.sh>2020-12-12 20:02:30 +0530
commit75c4e3cbcd4b2f7f47ebbebcc125d86c5b7e783b (patch)
treed4d7e5a3b6946512f27a553bfc40790919393415
parent7a7077baa8ee25449c249dc1adaef9a5b273cfb9 (diff)
downloadaoc-75c4e3cbcd4b2f7f47ebbebcc125d86c5b7e783b.tar.gz
Add day-10 solution
-rw-r--r--2020/day-10/README.org303
-rwxr-xr-x2020/day-10/day-10.raku48
-rw-r--r--2020/day-10/input94
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