diff options
Diffstat (limited to '2020/day-13/README.org')
| -rw-r--r-- | 2020/day-13/README.org | 253 |
1 files changed, 253 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 |