diff options
| -rw-r--r-- | 2020/day-10/README.org | 303 | ||||
| -rwxr-xr-x | 2020/day-10/day-10.raku | 48 | ||||
| -rw-r--r-- | 2020/day-10/input | 94 |
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 |