Add day-13 solution

4 files changed, 292 insertions, 0 deletions

diff --git a/2020/day-13/README.org b/2020/day-13/README.org
new file mode 100644
index 0000000..50da16c
--- /dev/null
+++ b/2020/day-13/README.org
@@ -0,0 +1,253 @@
+#+title: Day 13 - Shuttle Search
+#+options: toc:1
+#+export_file_name: index
+#+html_link_up: ../../index.html#2020
+#+setupfile: ~/.emacs.d/org-templates/level-3.org
+
+* Puzzle
+
+- This puzzle is taken from: https://adventofcode.com/2020/day/13
+
+Your ferry can make it safely to a nearby port, but it won't get much
+further. When you call to book another ship, you discover that no ships
+embark from that port to your vacation island. You'll need to get from
+the port to the nearest airport.
+
+Fortunately, a shuttle bus service is available to bring you from the
+sea port to the airport! Each bus has an ID number that also indicates
+how often the bus leaves for the airport.
+
+Bus schedules are defined based on a timestamp that measures the number
+of minutes since some fixed reference point in the past. At timestamp 0,
+every bus simultaneously departed from the sea port. After that, each
+bus travels to the airport, then various other locations, and finally
+returns to the sea port to repeat its journey forever.
+
+The time this loop takes a particular bus is also its ID number: the bus
+with ID 5 departs from the sea port at timestamps 0, 5, 10, 15, and so
+on. The bus with ID 11 departs at 0, 11, 22, 33, and so on. If you are
+there when the bus departs, you can ride that bus to the airport!
+
+Your notes (your puzzle input) consist of two lines. The first line is
+your estimate of the earliest timestamp you could depart on a bus. The
+second line lists the bus IDs that are in service according to the
+shuttle company; entries that show x must be out of service, so you
+decide to ignore them.
+
+To save time once you arrive, your goal is to figure out the earliest
+bus you can take to the airport. (There will be exactly one such bus.)
+
+For example, suppose you have the following notes:
+
+#+begin_src
+939
+7,13,x,x,59,x,31,19
+#+end_src
+
+Here, the earliest timestamp you could depart is 939, and the bus IDs in
+service are 7, 13, 59, 31, and 19. Near timestamp 939, these bus IDs
+depart at the times marked D:
+
+#+begin_src
+time   bus 7   bus 13  bus 59  bus 31  bus 19
+929      .       .       .       .       .
+930      .       .       .       D       .
+931      D       .       .       .       D
+932      .       .       .       .       .
+933      .       .       .       .       .
+934      .       .       .       .       .
+935      .       .       .       .       .
+936      .       D       .       .       .
+937      .       .       .       .       .
+938      D       .       .       .       .
+939      .       .       .       .       .
+940      .       .       .       .       .
+941      .       .       .       .       .
+942      .       .       .       .       .
+943      .       .       .       .       .
+944      .       .       D       .       .
+945      D       .       .       .       .
+946      .       .       .       .       .
+947      .       .       .       .       .
+948      .       .       .       .       .
+949      .       D       .       .       .
+#+end_src
+
+The earliest bus you could take is bus ID 59. It doesn't depart until
+timestamp 944, so you would need to wait 944 - 939 = 5 minutes before it
+departs. Multiplying the bus ID by the number of minutes you'd need to
+wait gives 295.
+
+What is the ID of the earliest bus you can take to the airport
+multiplied by the number of minutes you'll need to wait for that bus?
+
+** Part 2
+
+The shuttle company is running a contest: one gold coin for anyone that
+can find the earliest timestamp such that the first bus ID departs at
+that time and each subsequent listed bus ID departs at that subsequent
+minute. (The first line in your input is no longer relevant.)
+
+For example, suppose you have the same list of bus IDs as above:
+
+#+begin_src
+7,13,x,x,59,x,31,19
+#+end_src
+
+An x in the schedule means there are no constraints on what bus IDs must
+depart at that time.
+
+This means you are looking for the earliest timestamp (called t) such that:
+
+- Bus ID 7 departs at timestamp t.
+- Bus ID 13 departs one minute after timestamp t.
+- There are no requirements or restrictions on departures at two or
+  three minutes after timestamp t.
+- Bus ID 59 departs four minutes after timestamp t.
+- There are no requirements or restrictions on departures at five
+  minutes after timestamp t.
+- Bus ID 31 departs six minutes after timestamp t.
+- Bus ID 19 departs seven minutes after timestamp t.
+
+The only bus departures that matter are the listed bus IDs at their
+specific offsets from t. Those bus IDs can depart at other times, and
+other bus IDs can depart at those times. For example, in the list above,
+because bus ID 19 must depart seven minutes after the timestamp at which
+bus ID 7 departs, bus ID 7 will always also be departing with bus ID 19
+at seven minutes after timestamp t.
+
+In this example, the earliest timestamp at which this occurs is 1068781:
+
+#+begin_src
+time     bus 7   bus 13  bus 59  bus 31  bus 19
+1068773    .       .       .       .       .
+1068774    D       .       .       .       .
+1068775    .       .       .       .       .
+1068776    .       .       .       .       .
+1068777    .       .       .       .       .
+1068778    .       .       .       .       .
+1068779    .       .       .       .       .
+1068780    .       .       .       .       .
+1068781    D       .       .       .       .
+1068782    .       D       .       .       .
+1068783    .       .       .       .       .
+1068784    .       .       .       .       .
+1068785    .       .       D       .       .
+1068786    .       .       .       .       .
+1068787    .       .       .       D       .
+1068788    D       .       .       .       D
+1068789    .       .       .       .       .
+1068790    .       .       .       .       .
+1068791    .       .       .       .       .
+1068792    .       .       .       .       .
+1068793    .       .       .       .       .
+1068794    .       .       .       .       .
+1068795    D       D       .       .       .
+1068796    .       .       .       .       .
+1068797    .       .       .       .       .
+#+end_src
+
+In the above example, bus ID 7 departs at timestamp 1068788 (seven
+minutes after t). This is fine; the only requirement on that minute is
+that bus ID 19 departs then, and it does.
+
+Here are some other examples:
+
+- The earliest timestamp that matches the list 17,x,13,19 is 3417.
+- 67,7,59,61 first occurs at timestamp 754018.
+- 67,x,7,59,61 first occurs at timestamp 779210.
+- 67,7,x,59,61 first occurs at timestamp 1261476.
+- 1789,37,47,1889 first occurs at timestamp 1202161486.
+
+However, with so many bus IDs in your list, surely the actual earliest
+timestamp will be larger than 100000000000000!
+
+What is the earliest timestamp such that all of the listed bus IDs
+depart at offsets matching their positions in the list?
+
+* Solution
+
+~$file~ holds the input file. ~@input~ holds the lines of the file.
+
+#+begin_src raku
+unit sub MAIN(
+    IO() $file = "input" #= input file
+);
+
+my @input = $file.IO.lines;
+#+end_src
+
+~$start~ is the earliest timestamp we could depart at. ~@bus_ids~ holds all
+the bus ids, since we don't need "x", we just take the integers.
+
+#+begin_src raku
+my Int $start = @input[0].Int;
+my Int @bus_ids = @input[1].split(",").grep(/\d+/)>>.Int;
+#+end_src
+
+Looping over the timestamps, starting from ~$start~: We check if each bus
+~$id~ is divisible by the current timestamp. If the current ~$id~ is
+divisible by ~$stamp~, print the solution.
+
+#+begin_src raku
+stamp: for $start .. Inf -> $stamp {
+    for @bus_ids -> $id {
+        next unless $stamp %% $id;
+        say "Part 1: " ~ $id * ($stamp - $start);
+        last stamp;
+    }
+}
+#+end_src
+
+** Part 2
+
+For part 2, we don't need ~$start~ but just the ids & in this case the
+index of ids matter so we keep the "x" ids.
+
+#+begin_src raku
+my @bus_ids = @input[1].split(",");
+#+end_src
+
+~$stamp~ holds the timestamp & ~$step~ holds the number of minutes we can
+skip over. ~$step~ initially is set to first entry of ~@bus_ids~ because the
+final ~$stamp~ has to be a multiple of this. If the first entry is "x"
+then this will fail.
+
+#+begin_src raku
+my Int $stamp = 0;
+my Int $step = @bus_ids.first.Int;
+#+end_src
+
+- [X] ~$stamp~ must be multiple of first entry.
+
+Now we loop over all the entries except the first one, we've already
+cleared that condition. Entries with "x" are skipped.
+
+I believe going through the code with an example will make it easier to
+understand. So we'll go through this code with the sample input:
+
+#+begin_src
+7,13,x,x,59,x,31,19
+#+end_src
+
+~@bus_ids.kv[2..*]~ returns the key, value entries of ~13,x,x,59,x,31,19~.
+~$idx~ holds the index & ~$id~ holds the bus id. Let's start from ~$idx~ being
+1 & ~$id~ being 13.
+
+We'll go through the code line by line. The first line in the loop
+checks if the entry is "x", if so then it skips the entry. In our case
+~$id~ is 13 so it doesn't skip.
+
+Line 2 in the loop keeps on increasing ~$stamp~ by skipping over ~$step~
+stamps until ~$stamp + $idx~ is divisible by ~$id~, which is the required
+condition. Then we once again increase ~$step~.
+
+#+begin_src raku
+id: for @bus_ids.kv[2..*] -> $idx, $id {
+    next id if $id eq "x";
+    $stamp += $step until ($stamp + $idx) %% $id;
+    $step lcm= $id;
+}
+
+say "Part 2: " ~ $stamp;
+#+end_src
diff --git a/2020/day-13/day-13.raku b/2020/day-13/day-13.raku
new file mode 100755
index 0000000..e870af6
--- /dev/null
+++ b/2020/day-13/day-13.raku
@@ -0,0 +1,35 @@
+#!/usr/bin/env raku
+
+unit sub MAIN(
+    IO() $file = "input" #= input file
+);
+
+my @input = $file.IO.lines;
+
+{
+    my Int $start = @input[0].Int;
+    my Int @bus_ids = @input[1].split(",").grep(/\d+/)>>.Int;
+
+    stamp: for $start .. Inf -> $stamp {
+        for @bus_ids -> $id {
+            next unless $stamp %% $id;
+            say "Part 1: " ~ $id * ($stamp - $start);
+            last stamp;
+        }
+    }
+}
+
+{
+    my @bus_ids = @input[1].split(",");
+
+    my Int $stamp = 0;
+    my Int $step = @bus_ids.first.Int;
+
+    id: for @bus_ids.kv[2..*] -> $idx, $id {
+        next id if $id eq "x";
+        $stamp += $step until ($stamp + $idx) %% $id;
+        $step lcm= $id;
+    }
+
+    say "Part 2: " ~ $stamp;
+}
diff --git a/2020/day-13/input b/2020/day-13/input
new file mode 100644
index 0000000..4a527f3
--- /dev/null
+++ b/2020/day-13/input
@@ -0,0 +1,2 @@
+1002460
+29,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,601,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,17,x,19,x,x,x,x,x,x,x,x,x,x,x,463,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37
diff --git a/2020/day-13/sample_input b/2020/day-13/sample_input
new file mode 100644
index 0000000..d76f619
--- /dev/null
+++ b/2020/day-13/sample_input
@@ -0,0 +1,2 @@
+939
+7,13,x,x,59,x,31,19