diff options
Diffstat (limited to 'racket/aoc2022')
32 files changed, 4855 insertions, 0 deletions
diff --git a/racket/aoc2022/commentary.md b/racket/aoc2022/commentary.md new file mode 100644 index 0000000..8616464 --- /dev/null +++ b/racket/aoc2022/commentary.md @@ -0,0 +1,35 @@ +# Reflections on Advent of Code 2022 from a guy who kinda knows Racket + +I've gotten into the habit of doing [Advent of Code](https://adventofcode.com/), the annual puzzle-a-day programming challenge. There's a competitive aspect to it, but I'm mostly interested in it as a way to challenge myself and get exposed to algorithms and concepts I haven't seen before. I'm not a programmer by trade; I learned the basics of C in college and a little bit of numerical methods in grad school, but most of what I've learned since then is self-taught as a hobby, so structured programming challenges like this are a good way for me to gauge my skill level and see how CS theory is put into practice. + +The language I'm most comfortable with is [Racket](https://racket-lang.org/), a general-purpose high-level language in the Scheme family, so it's what I used this year for Advent of Code. In my experience, Racket is pretty well-suited for the kinds of problems you find in programming challenges; there hasn't been any problem yet where I've felt like trying to solve it in Racket has been a handicap. For the first few days I used [Jupyter Notebook with the IRacket kernel](https://docs.racket-lang.org/iracket/index.html) to annotate my answers, but I eventually gave up on that because it ended up being harder to debug. + +So, here's my day-by-day opinion on how this year went for me. + +* **[Day 1](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-01/day-01.rkt)**. *Parse a list of lists and return the top three sums.* This is the kind of problem Racket feels made for -- the code is basically a direct declarative translation of the problem statement. +* **[Day 2](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-02/day-02.ipynb)**. *Rock-paper-scissors strategy.* Lots of pattern-matching; the hardest part was probably figuring out the rules of the tournament. +* **[Day 3](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-03/day-03.ipynb)**. *Find common items in rucksacks.* Another problem well-suited to declarative style. +* **[Day 4](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-04/day-04.ipynb)**. *Find overlapping and redundant ranges.* I used the [`rebellion`](https://docs.racket-lang.org/rebellion/index.html) library here for its [range](https://docs.racket-lang.org/rebellion/Ranges.html) data type, which takes care of most of the problem by itself. AoC is a good opportunity to explore a language's ecosystem. +* **[Day 5](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-05/day-05.ipynb)**. *Move stacks of boxes around.* Linked lists make first-in, last-out stack problems like this pretty easy. The major difficulty here was actually parsing the input (and it was probably the hardest input to parse out of all the problems), but once that was resolved it was smooth sailing. +* **[Day 6](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-06/day-06.rkt)**. *Find chunks of unique characters in a string.* Another one that Racket handles without difficulty -- the entire problem statement can be represented as one `for` comprehension. +* **[Day 7](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-07/day-07.rkt)**. *Parse terminal output and calculate directory sizes.* The first speedbump of the year, and probably the first day where there's a rift between "do it right" and "just get the answer". I saw a lot of solutions that properly built the file hierarchy and walked the tree to calculate directory sizes, while I just made a hashtable of absolute paths and the sizes of everything within them. +* **[Day 8](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-08/day-08.rkt)**. *Scout a forest for the treehouse site with the best visibility.* A traditional AoC "search a grid of integers for something" problem, and the first one of the year where I represented a grid as a hashtable of coordinates. Racket doesn't have great multidimensional data structures built in, but rolling my own sparse matrix representation is pretty painless. +* **[Day 9](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-09/day-09.rkt)**. *Simulate a rope.* Simulation problems are my favorite kind of AoC problem (probably because they're the most similar to the kind of stuff I did in school). The solution I wrote for a one-segment rope in part 1 just needed to be folded over a list to give me a solution for the ten-segment rope in part 2. Higher-order functions are nice. +* **[Day 10](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-10/day-10.rkt)**. *The traditional fake-ASM parsing problem*, and another problem that's just largely just folding a function over an accumulator. I feel like if you get comfortable with `for/fold` you can get about 25 AoC stars right off the bat. +* **[Day 11](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-11/day-11.rkt)**. *Monkeys take your stuff.* This problem features my least favorite AoC trope, which is a Part 2 that requires you to know a particular fact about modular arithmetic to solve it in a reasonable amount of time. It also had a data file I found less annoying to retype by hand than to parse. Probably the worst one of the set. +* **[Day 12](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-12/day-12.rkt)**. *Find a hiking route up a spiral mountain.* I leaned pretty hard on the [`graph`](https://docs.racket-lang.org/graph/index.html) package for this one. Eventually I'd like to learn how to implement Dijkstra and A* and other graph traversal algorithms myself, but for now I'm satisfied with just figuring out how to use the prepackaged versions. +* **[Day 13](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-13/day-13.rkt)**. *Sort a recursive data type.* I'm really glad for two features of Racket for this one. First, the ability to read data as code, which meant I could read the nested lists directly with just one tweak to the readtable and without doing any string parsing at all. Second, structural pattern matching. Racket's matching syntax isn't as elegant as some languages (I miss the `[x | xs]` form from Elixir compared to `(list* x xs)`, for example), but it's powerful. +* **[Day 14](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-14/day-14.rkt)**. *Simulate falling sand.* A fun simulation problem, and one that both has a naive solution that solves in a reasonable amount of time and an optimized backtracking solution that's easy to reason out. This was my favorite puzzle of the set. +* **[Day 15](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-15/day-15.rkt)**. *Find the only possible place for a missing beacon.* The fundamental problem here is finding out a way to represent a range of integers sparsely (or [using a library that does that for you](https://docs.racket-lang.org/data/integer-set.html)). Lots of opportunities for optimization. +* **[Day 16](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-16/day-16.rkt)**. *Teach an elephant to open valves*. The first of a few heuristic search problems with enormous solution spaces. Part 1 (one person opening valves) is OK, but I only eventually solved Part 2 (two people simultaneously opening valves) a week later by watching console output and making a reasonable guess. [Nearly half of the remaining participants in AoC quit at this point](https://adventofcode.com/aoc2022/stats) and I don't really blame them. +* **Day 17** (no solution). *Find the period in the pattern of falling rocks.* I'm sure this one isn't too bad, but I was feeling too burnt out by Day 16 to give it more than a token try. +* **[Day 18](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-18/day-18.rkt)**. *Find the surface area of an irregular rock.* A nice straightforward volume-scanning problem, and another opportunity to use my sparse matrix data type. +* **Day 19** (no solution). *Pick the best plan for building mining robots.* Another heuristic search problem, so I skipped this one since I was still failing at day 16 part 2. Picking out an optimized robot building strategy had more moving parts than I knew how to deal with. +* **[Day 20](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-20/day-20.rkt)**. *Repeatedly shift elements around in a circular array.* Singly-linked lists are terrible for repeated arbitrary access, but I don't care. I figured out an algorithm that worked and I was happy enough with that to accept it and move on. After the previous streak of problems, I was just happy to figure out Part 2 on my own. (There was a modulo math trick element to Part 2 here as well, but this one was a lot more obvious to spot.) +* **[Day 21](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-21/day-21.rkt)**. *Figure out what to shout in the monkeys' math game.* I have a feeling the intended solution for Part 2 of this one was to build the expression tree and backtrack through the operations to calculate the unknown value. However, I just blindly started evaluating the result for various guesses and discovered through trial and error that the relationship between the guess and the result is linear, so all you need for part 2 is two guesses, their corresponding results, and some algebra. It's fun to accidentally discover simple solutions to complex-looking problems. +* **Day 22** (no solution). *Something involving walking around on a map.* I skipped this one because of the flu. C'est la vie. +* **[Day 23](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-23/day-23.rkt)**. *Cellular elfomata.* Another AoC staple, though later than usual. I think the story got in the way of the problem description a little bit here, but once I talked through the rules with someone else it was a straight shot to the solution. +* **Day 24** (no solution). *Walk through a blizzard.* I had to skip this one because of holiday travel (ironically made more difficult by a blizzard) and family obligations. It looks interesting, though, so I'm hoping to have some time to come back to it before January. +* **[Day 25](https://github.com/hunkyjimpjorps/AdventOfCode/blob/main/aoc2022/day-25/day-25.rkt)**. *Figure out balanced penternary.* The final AoC problem is always a clever little math brain teaser with one part, and this one was fun to puzzle out with pencil and paper. + +I think Days 16 and 19 could've used a second pass to narrow the possible solution space, or at least make the best heuristic a little more straightforward to reason out, but on the balance, I enjoyed myself this year, and I'm generally happy with my solutions and implementations.
\ No newline at end of file diff --git a/racket/aoc2022/day-01/day-01.ipynb b/racket/aoc2022/day-01/day-01.ipynb new file mode 100644 index 0000000..c79a3f6 --- /dev/null +++ b/racket/aoc2022/day-01/day-01.ipynb @@ -0,0 +1,139 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 1: Calorie Counting\n", + "\n", + "Elves carry various amounts of food with various caloric contents.\n", + "\n", + "**Part 1.** How many calories is the elf with the most calories of food carrying?\n", + "\n", + "**Part 2.** How many calories are the three elves with the most calories of food carrying?" + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "(require racket\n", + " advent-of-code\n", + " threading)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 1\n", + "\n", + "The data file is a list of integers, one on each line, with an empty line separating the inventory of each elf.\n", + "\n", + "1. Fetch the input file,\n", + "2. split it on double newlines to find each elf's inventory,\n", + "3. split each inventory on single newlines,\n", + "4. convert each inventory member to a number,\n", + "5. sum up each list, and\n", + "6. find the maximum one. \n", + "\n", + "This is straightforward to do with threading/piping:" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<code>70374</code>" + ], + "text/plain": [ + "70374" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define calorie-data (fetch-aoc-input (find-session) 2022 1))\n", + "\n", + "(~>> calorie-data\n", + " (string-split _ \"\\n\\n\")\n", + " (map (λ~>> string-split (map string->number) (apply +)))\n", + " (apply max))\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 2\n", + "\n", + "Similarly, to find the top three calorie holders,\n", + "\n", + "1. fetch the input file,\n", + "2. split it on double newlines,\n", + "3. split each list member on single newlines,\n", + "4. convert each sublist member to a number,\n", + "5. sum up each list, \n", + "6. sort the list from high to low,\n", + "7. take the first three members,\n", + "8. and sum them." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<code>204610</code>" + ], + "text/plain": [ + "204610" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(~>> calorie-data\n", + " (string-split _ \"\\n\\n\")\n", + " (map (λ~>> string-split (map string->number) (apply +)))\n", + " (sort _ >)\n", + " (take _ 3)\n", + " (apply +))\n" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4 + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-01/day-01.rkt b/racket/aoc2022/day-01/day-01.rkt new file mode 100644 index 0000000..5215014 --- /dev/null +++ b/racket/aoc2022/day-01/day-01.rkt @@ -0,0 +1,20 @@ +#lang racket + +(require advent-of-code + threading) + +(define calorie-data (fetch-aoc-input (find-session) 2022 1)) + +;; part 1 +(~>> calorie-data + (string-split _ "\n\n") + (map (λ~>> string-split (map string->number) (apply +))) + (apply max)) + +;; part 2 +(~>> calorie-data + (string-split _ "\n\n") + (map (λ~>> string-split (map string->number) (apply +))) + (sort _ >) + (take _ 3) + (apply +)) diff --git a/racket/aoc2022/day-02/day-02.ipynb b/racket/aoc2022/day-02/day-02.ipynb new file mode 100644 index 0000000..13b9986 --- /dev/null +++ b/racket/aoc2022/day-02/day-02.ipynb @@ -0,0 +1,193 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 2: Rock Paper Scissors\n", + "\n", + "You've given a strategy guide for how to win at a Rock Paper Scissors tournament. The first column is what your opponent will throw. Your score is determined by the result (win, lose, draw) of each round and what you played (rock, paper, scissors).\n", + "\n", + "**Part 1.** What's your tournament score if the second column represents what you should play in each round?\n", + "\n", + "**Part 2.** What's your tournament score if the second column represents the result of each round?\n", + "\n", + "For this solution, I'm using `rackjure` since I'm planning on using a bunch of dictionaries, and `rackjure`'s shorthand makes them easier to work with." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "#lang iracket/lang #:require rackjure\n", + "(require advent-of-code)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "The input for this problem is a list with two columns; the first column is one of the characters `A`, `B` or `C` (corresponding to the opponent's throw of rock, paper or scissors) and the second column is `X`, `Y` or `Z`, whose meaning is currently unknown." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(define strategy-guide (~> (fetch-aoc-input (find-session) 2022 2) (string-split \"\\n\")))\n", + "(define opponent-throw {\"A\" 'rock \"B\" 'paper \"C\" 'scissors})" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "We're also given the score for a round result and the bonus for the selected throw, and we write a function that determines the result for a given round." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(define score-bonus {'rock 1 'paper 2 'scissors 3 'win 6 'draw 3 'lose 0})\n", + "\n", + "(define winning-rounds {'rock 'paper 'paper 'scissors 'scissors 'rock})\n", + "(define losing-rounds {'rock 'scissors 'paper 'rock 'scissors 'paper})\n", + "\n", + "(define (outcome them me)\n", + " (match* (them me)\n", + " [(x x) 'draw]\n", + " [(x y) #:when (eq? y (winning-rounds x)) 'win]\n", + " [(_ _) 'lose]))" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 1\n", + "\n", + "In part 1, we assume that the second column refers to the throw we should select in each round. We add that to our existing dictionary and write a `for` comprehension to calculate each round result." + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>13809</code>" + ], + "text/plain": [ + "13809" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define assume-throw (dict-merge opponent-throw {\"X\" 'rock \"Y\" 'paper \"Z\" 'scissors}))\n", + "\n", + "(for/sum ([play (in-list strategy-guide)])\n", + " (match-define (list them me) (string-split play))\n", + " (+ (score-bonus (outcome (assume-throw them) (assume-throw me)))\n", + " (score-bonus (assume-throw me))))" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 2\n", + "Now we're told that the second column actually represents the round result: `X` is lose, `Y` is draw, `Z` is win. We can look up what we should throw in response for each round, and then calculate the score from that." + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>12316</code>" + ], + "text/plain": [ + "12316" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define assume-result (dict-merge opponent-throw {\"X\" 'lose \"Y\" 'draw \"Z\" 'win}))\n", + "(define (pick-throw them result)\n", + " (match* (them result)\n", + " [(x 'draw) x]\n", + " [(x 'win) (winning-rounds x)]\n", + " [(x 'lose) (losing-rounds x)]))\n", + "\n", + "(for/sum ([play (in-list strategy-guide)])\n", + " (match-define (list them result) (string-split play))\n", + " (+ (score-bonus (assume-result result))\n", + " (score-bonus (pick-throw (assume-result them) (assume-result result)))))" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "Racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4, + "vscode": { + "interpreter": { + "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1" + } + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-02/day-02.pl b/racket/aoc2022/day-02/day-02.pl new file mode 100644 index 0000000..707da41 --- /dev/null +++ b/racket/aoc2022/day-02/day-02.pl @@ -0,0 +1,72 @@ +:- use_module(library(yall)). +:- use_module(library(apply)). + +output_solutions :- + get_data(Games), + part1_total(Games, Part1), + write(Part1), nl, !, + part2_total(Games, Part2), + write(Part2), nl. + +% Facts + +game(X, X, draw). +game(rock, scissors, win). +game(scissors, paper, win). +game(paper, rock, win). +game(rock, paper, lose). +game(scissors, rock, lose). +game(paper, scissors, lose). + +opponent_move("A", rock). +opponent_move("B", paper). +opponent_move("C", scissors). + +assume_move("X", rock). +assume_move("Y", paper). +assume_move("Z", scissors). + +assume_outcome("X", lose). +assume_outcome("Y", draw). +assume_outcome("Z", win). + +bonus(rock, 1). +bonus(paper, 2). +bonus(scissors, 3). +bonus(lose, 0). +bonus(draw, 3). +bonus(win, 6). + +% Rules + +get_data(Result) :- + setup_call_cleanup(open("2022/day-02/prolog-input.txt", read, In), + (read_string(In, _, Str), + split_string(Str, "\n", "\s\t\n", Lines), + maplist([In, Out] >> split_string(In, "\s", "", Out), Lines, Result)), + close(In)). + +score_game(MyMove, Result, Score) :- + bonus(Result, X), + bonus(MyMove, Y), + Score is X + Y. + +part1_score([Them, Me], Score) :- + opponent_move(Them, TheirMove), + assume_move(Me, MyMove), + game(MyMove, TheirMove, Result), + score_game(MyMove, Result, Score). + +part1_total(Games, Total) :- + maplist(part1_score, Games, Scores), + sum_list(Scores, Total). + +part2_score([Them, Outcome], Score) :- + opponent_move(Them, TheirMove), + assume_outcome(Outcome, Result), + game(MyMove, TheirMove, Result), + score_game(MyMove, Result, Score). + +part2_total(Games, Total) :- + maplist(part2_score, Games, Scores), + sum_list(Scores, Total).
\ No newline at end of file diff --git a/racket/aoc2022/day-02/prolog-input.txt b/racket/aoc2022/day-02/prolog-input.txt new file mode 100644 index 0000000..95a2b2a --- /dev/null +++ b/racket/aoc2022/day-02/prolog-input.txt @@ -0,0 +1,2500 @@ +C X +C X +A Y +C X +B Y +A X +A Z +B Y +C Z +C Z +B X +C Z +B Y +C Z +B Y +A Z +B Y +C X +C X +C X +B X +C Z +C X +C Z +C X +A Y +B Y +B Z +A X +C X +C Z +C Z +A Z +B Y +C Z +C X +C X +C Z +B Y +C Z +C Z +C X +B X +B X +A Y +C Z +C Z +B Y +B Y +C Z +C X +A Z +C X +C Z +C Z +B X +C Z +C Z +B Y +A Y +B X +C X +C X +C Z +C X +A Y +C X +C Z +A Z +B Y +C Z +C X +C X +C Z +C Z +C Z +A Z +C Z +A Z +A Z +C X +B Y +C X +C X +A Z +C X +A Y +C Z +C Z +A Y +A Z +C Z +C Z +A Y +C Z +C Y +B Y +B Y +A Z +A Y +C Z +C Z +A Z +C Z +A Y +B Z +C X +C Z +C X +B Y +C Z +C X +B Y +B X +A Y +C Z +C Z +C Z +B Z +A Y +C Z +C Z +C X +C Z +C X +A Y +C Z +C Z +C X +B Y +B X +B Y +C Z +C X +B X +C Z +C Z +A Y +C Z +A Z +A Y +C Z +A Y +C X +A Y +C Y +A Z +C X +C X +B Y +B Y +A Y +A Z +C Z +C X +C Z +A Y +B Y +A Y +B X +C Z +C Z +A Z +A Y +C X +C X +C X +A Z +B Y +C Z +C Z +C Z +C X +B Z +C Z +C Z +B Z +C Z +A Z +B Y +A Y +C Z +B Y +B X +B X +C X +C Z +A X +C Z +C X +C X +C X +C X +C X +B Y +C X +C X +A Y +A Y +C Z +C Z +B X +C Z +C Z +C Z +C Z +A Z +C Z +A Z +B Y +B Y +C Z +B Y +C Z +C Z +C Z +C X +B Y +B Y +C Z +A Z +C Z +C X +B Y +C Z +A Z +C Z +C X +C Z +C Z +C X +C X +B Z +A Y +B X +C Z +B Y +C X +C X +C Z +C Z +B X +B X +B Y +A X +C X +A Z +A Z +C Z +B Y +C Z +A Z +B X +C X +B Y +A Z +C X +A X +A Z +B Y +B X +B Y +A Y +C Z +C Z +B X +C Z +C X +B Y +C Z +C Z +A Y +B Y +A Z +A Y +C X +C X +C Z +A Z +C Z +B Z +A Z +A Y +C X +C Z +C X +B Z +C Z +B Y +A Y +B X +A Y +C Z +A Y +C Z +C X +B Y +C X +A Y +A Z +C Z +B Y +C X +A Y +C X +C Z +C X +B Y +C X +C Z +C Z +A Z +B Y +C X +B X +A Z +C X +C X +A Y +B X +C X +A Z +C Z +C Z +C Z +B Y +A Y +C X +C Z +C Z +A Z +C Z +A Y +C X +C X +C X +A Z +B Y +C Z +A Y +C Z +C Z +C X +C Z +A Z +C Z +B Y +C X +C X +C Z +B Z +B Y +C X +C X +A Y +A Z +A Z +A X +C X +A Y +B Y +A Y +A Z +B Y +B Y +A Y +B Y +C X +A Z +B X +C Z +A Z +B X +A Y +B X +B Y +A Y +A X +C Z +B Z +B X +B Z +C Z +C X +B X +B Y +A Y +B Y +B Y +B Y +A Z +A Y +B X +A Y +C X +B Y +B X +B Y +C X +A Y +C X +A Y +C Z +C Z +A Z +C Z +C X +C X +A Z +C X +C X +C X +A Y +A Z +A Z +C Z +B X +C X +C X +C Z +A Y +C X +C X +B X +C Z +C Z +C X +B Z +C X +C X +C Z +A Y +C X +A Z +C Z +C X +B X +B Y +C X +C Z +C X +C Z +A Z +C Z +C X +C Z +C Z +A Z +B X +C X +C Z +C X +C X +C Z +C X +C Z +A Z +A Z +A Z +C Z +C X +A Z +C Z +C Z +C Z +A Z +B Y +C X +B Y +C X +C Z +B Y +C X +C X +A Z +A Z +C X +C Z +C X +C Z +A Z +A Y +C Z +C Z +A Y +B Y +B Y +C Z +B Y +B X +B Z +A Y +A Z +C X +B Y +B Z +B Y +B Z +C Z +B Y +C Z +C Z +B Y +B X +B Z +C X +A Z +C X +C X +C X +A Z +C Z +A Z +C Z +A Y +C Y +B Y +A Z +B Y +C Z +A Z +A Y +B X +C X +C X +C X +C Z +C X +B X +C Z +A Y +C Z +A X +B Y +B Z +C Z +B Y +C Z +B X +B Y +C Z +B X +A Z +B X +B Y +A Y +B Z +C X +C Z +A Z +A Y +A Z +C X +C Z +B Z +A Z +A Z +C X +C Z +C X +C X +A Z +C X +C X +C X +B X +A Y +B Y +B X +B Y +C Z +B Y +B Z +C Z +C X +B Y +C Z +C Z +C Z +C Z +C Z +C Z +A Z +A Z +A Z +C X +C Z +B Y +C Z +C Z +C Z +C Z +C X +C X +A Z +B Y +A Z +B Z +C X +C X +C Z +C Z +C X +A Y +C X +A Y +C Z +A Z +C Z +B X +C Z +C Z +C X +C X +C Z +B Z +A Y +B X +A Y +B Y +A Y +A Z +A Z +C Z +B X +C Z +C X +C Z +C Z +A Z +C X +A Y +C X +A Z +C Z +C X +C Z +A Z +C X +C X +C X +C X +B X +B Y +C X +C Z +C Z +C Z +C Z +A Z +A Z +A Y +C Z +C X +C Z +C Z +C Z +A Y +C X +A Z +C Y +A Z +C Z +C X +A Y +C Z +C X +C X +A Z +B Y +C Z +A Z +C Z +C Z +C Z +B Y +C X +C X +A X +A Y +C Z +A Z +C Z +B Y +C X +B X +C X +C X +A Y +C Z +C Z +C Z +C X +A Z +B Y +A Y +B Z +B Z +B X +A Z +B X +B X +A Z +A Z +C Y +B Y +C Z +A X +C Z +B X +C Z +A Y +A Y +C Z +C Z +A Z +B Y +C Z +C Z +C Z +C X +A Y +C X +B Y +B Y +C X +C Z +C X +B X +A Y +A Y +C Z +C Z +C Z +C Z +C Z +B X +C Z +A Y +B X +A Y +A Z +C Z +C X +B Y +B Y +C Z +C Z +C Z +B Y +C X +B Y +A Y +B X +C Z +C Z +A Y +C X +C Z +A Y +C X +C X +A Z +C Z +B X +A Z +B Y +C Z +A Z +B X +C Z +B Y +C Z +B Y +C X +C Z +B X +C X +B Y +C X +A Y +C Z +C Z +C X +B Y +C X +C Z +C X +C Z +A Z +A Y +C X +C Z +C Z +A Z +C X +B Z +A Z +B Y +C X +A Z +C Z +B Y +C X +C X +C Z +C Z +B Y +A Z +C Z +C X +C Z +A Z +C X +A Z +C Z +C X +C X +C Z +B X +C Z +C Z +C Z +B Y +A X +B Y +C X +A Z +B X +A Z +C Z +C X +C Z +C Z +B Y +B X +C Z +B Z +B Y +B X +C X +C X +C X +C Z +B Y +C Z +C Z +C Z +C Z +C Z +C Z +C X +C Z +A Y +C X +B X +A Y +C X +C X +C Z +C Z +C X +B X +B Y +B Y +C Z +B X +C X +C X +C Z +C Z +A Y +C Z +A Y +C Z +C Z +B Y +A Z +B X +B X +C Z +C Z +A Y +A Y +C Z +C Z +C X +A Y +A Y +C Z +A Z +C X +B Z +A Y +C X +B Z +A Y +C X +B Y +C X +C X +C Z +A X +C Y +A Y +B Z +B Y +A X +B Y +A Z +C Z +C X +C X +C X +C Y +B Y +C Z +A Z +C X +C X +C Z +C Z +C X +C Z +B Y +C Z +C X +B Y +A Z +C X +B Y +C Z +C X +B Y +A Z +B X +C Z +B X +B X +C Z +C Z +C X +B Y +A Y +B X +B X +A Y +B Y +B Y +B X +A Z +A Y +C Z +B Y +C Z +A Z +C Z +C X +A Z +C X +C Z +C X +B Y +C X +A Z +B X +C Z +C X +C X +B Y +A Y +C Z +C X +A Y +A X +C Z +B Y +B X +C X +C X +C X +C Z +A Z +B Y +A Y +B Y +B X +B Y +B Y +A Z +B Y +B Y +B Y +C Z +C X +A Z +A X +B Z +C X +C X +C X +C X +C Z +A Z +B Y +A Z +B Y +C X +A Z +A Y +C Z +C X +B X +A Z +B Y +C Z +A Z +C X +A Z +A Y +B Y +C Z +B Y +C X +A Z +A Z +A X +C Z +C X +A Y +B Y +B X +C Z +A Z +C X +B X +B Y +A Z +C X +B Y +C X +C Z +C Z +B Y +A Z +A Y +C X +B Y +C X +C X +C Z +C Z +C X +A X +C X +A Z +C Z +B X +B X +C X +B X +B Y +C X +C X +A Y +B Y +C Z +C Z +C Z +C Z +C Z +C Z +A Z +B X +C X +B Y +B Y +C X +C Z +A Z +C X +C Z +C Z +C X +A Z +C Z +A Z +C Z +A Y +C X +C X +B Y +C X +C Z +B X +A Y +C Z +C X +B Y +B X +A Y +C X +A Z +C Z +C X +C X +A Y +B Y +C Z +B Z +C Z +C X +B Y +C Z +C X +A Y +C X +C Z +C X +C X +B X +C X +B Y +C X +C Z +C X +B X +B X +C Z +A Y +C Z +C Y +B X +A Z +C X +A Z +B Z +A Y +C Z +C Z +A Z +B Z +A Z +C X +C Z +C Z +A Z +A Y +C Z +C X +A Y +B Y +B X +A Z +A Y +C X +B X +A Y +C Z +B Y +C X +C X +C X +B X +A Z +B Y +B Y +A Z +C X +B X +B X +A Y +C Z +C X +C X +A Y +C X +C X +C Z +C X +A Y +B Y +C Z +A Z +C Z +A Z +A Z +A Y +C X +C X +C X +A Y +A Y +B Y +B Z +A Z +C X +C Z +C X +C Z +B X +C X +C X +B X +C Z +C X +B Y +B X +C Z +A Z +C Z +B Y +C Z +C Z +B X +A Y +B Y +A Z +B Y +C X +C X +A Z +C Z +C X +C Z +C X +A Z +C X +A Z +C X +A Y +A Z +C X +C Z +B Y +C Z +A Z +C Y +B Z +B Y +A Z +C Z +A X +A Z +C Z +C X +C X +A Y +C Z +C X +C Z +C Z +C Z +B Y +C Z +C X +C Z +B Y +C Z +B Y +C Z +C Z +C Z +C Z +C Z +B Y +C Z +B Y +A Y +C X +B Y +A Y +C X +A Z +A Y +C Z +B Y +C Z +C X +A Y +B Y +C X +C X +C X +A Y +A Z +B X +B X +B X +B Y +C Z +B Y +C Z +C Z +B Y +A X +C X +A Y +C Z +B Y +B Y +C Z +C Z +C X +C Z +C Z +B Y +C Z +C X +A Y +A Z +C X +B Z +C X +B Y +C Z +C X +A Y +A Z +C Z +C X +C Z +C X +C X +C X +C X +C Z +C X +B Y +A Y +C X +C Z +A Z +B Y +C Z +C X +C Z +B Y +A Z +A Y +A Y +B Y +B Y +A Z +B X +A Y +C X +C X +A Y +C X +A Y +B Y +C Z +A X +B X +A Y +A Z +C Z +B X +C Z +B Y +C X +B Y +C Z +A Z +A Y +C X +C Z +B X +B Y +C Z +C Z +A Z +C Z +B Z +C X +C X +C Z +C Z +C Z +C X +C X +C Z +B Y +C Z +B Z +C X +A Y +C Z +B Y +C X +A Y +C Z +B X +C Z +A Z +C Z +C X +A Y +A Y +A Y +C Z +C Z +A Y +A X +C Z +C Z +C X +C Z +A Z +A Z +C Z +C X +C Z +B Y +A Y +B Z +B Y +C X +C Z +C X +B X +B Y +C X +C X +C X +A Z +A Y +C X +C Z +C X +B Y +C Z +B X +C Z +B Y +A Z +C X +B Y +C X +B X +A Z +C X +B Y +A Y +C Z +C X +A Y +C X +B Y +B X +C Z +C X +C X +C Z +C X +C X +A Y +A X +C Z +C Z +C Z +B Y +C Z +A Z +B X +C Z +C X +C X +A Y +A Z +B Y +B Y +C Z +C Z +A Y +A Z +A Z +C Z +B Y +B Y +C Z +B Y +C X +C X +C Z +A Z +C X +C X +B Y +B Y +C Z +B Y +C Z +C Z +C Z +C Z +C X +C Z +B Y +C Z +C Z +B X +C Z +C Z +C X +B Y +C Z +A Z +A Z +A Z +C X +B Y +C Z +A Y +B X +C X +C X +A X +A Y +B X +C Z +C X +C Z +C Z +B Y +C Z +C Z +B Z +C Z +C Z +B X +A Y +C X +A Z +B Y +A Z +C X +B X +B X +C Z +A X +B Z +A Z +B Y +C X +C Z +B Z +C X +B X +C Z +A Z +B X +C Z +C Z +A Z +A Y +C Z +C Z +B X +A Z +C Z +B Y +B Y +C Z +B Y +C Z +C Z +C Z +C Z +C Z +C Z +C Z +C X +A Y +C Z +C Z +C X +C Z +B Y +B X +B Y +A Z +C Z +B Y +B X +C Z +B X +C Y +C X +B Y +C Z +B Y +A Z +B Y +C X +C Z +B X +C Z +A Y +C Z +B X +A Z +A Y +B Y +C Z +A Y +B Y +C X +A Z +A Y +C Z +C Z +A Y +B X +C X +B Y +A Y +C X +B X +C X +C Z +C Z +B Y +A Z +B Y +A Z +A Y +A Z +B X +A Y +C X +B Y +C Z +C Z +A Z +C Z +C Z +C X +C Z +C Z +B Y +A Z +C X +A Y +C Z +A X +A Z +C Z +B Y +C X +C Y +A Y +B X +B Y +C Z +C Z +B X +B X +C Y +B Y +B X +C X +C Z +A Z +C Z +A Z +C Z +C Z +A Z +B X +C Z +C X +C Z +B Y +B X +A Z +C Z +B X +C Z +B Z +C Z +B Y +B Y +C Z +B Y +A Y +A Z +A Z +C X +A X +C X +C Z +C Z +A Y +C Z +C Z +C Z +A Y +B X +C Z +C X +B X +C X +C X +B Y +C Z +B X +C X +B Y +A Y +C Z +C X +C X +A Z +B Y +C Z +B Y +C Z +B Z +B Y +B Y +A Y +B Y +B Y +A X +A Y +C Z +C X +B X +C Z +C X +C X +B Y +C Z +C Z +B Y +A Y +B Y +C Z +C X +C Z +C Z +C X +A Y +A Y +C Z +A Y +C X +C Z +A Z +A Z +C Z +B Y +A X +A X +B X +A Z +C X +C X +C X +C X +A Z +A Z +C X +B X +B Y +C X +B Y +B Z +A Z +A Y +C X +B Y +B Y +C Z +B X +B X +C Z +B Y +C Z +C Z +B Y +C Z +C X +C Z +B Y +C X +C Z +C Z +C X +B X +C Z +C X +C X +C Y +C Z +B Y +C X +C X +A Y +C X +C X +C Z +C X +C Z +C Z +C Z +A X +C Z +C Y +C Z +C Z +C Z +C Z +A X +C Z +B X +C Z +C X +B Y +C X +A Z +C Z +C X +B Y +B Y +A Z +A Y +C X +A Z +C Z +C Z +A Y +A Z +A X +C Z +A Z +C Z +C Z +C Z +A Z +A Y +A Z +A Z +A Y +A Y +C X +A Y +A Y +C Z +C Z +C Z +B X +C X +C Z +B X +C Z +C Z +C Z +C Z +C Z +B Y +C Z +B Y +C Z +C X +A Z +C Z +B X +B Y +C X +B Y +C X +C X +A Y +C Z +C X +C X +C Z +C X +C X +C Z +B Y +B X +C X +B X +B Y +C X +A Z +B Y +A Z +B Y +A Z +A Y +C Z +C Z +C X +B Y +A Y +A Y +C X +B Y +C X +A Z +A Z +C X +A X +C X +A Z +C X +C Z +C X +A Y +C X +B Y +B Y +C X +A Z +C Z +C Z +B X +C Z +C Z +A Y +C Z +B Y +A Z +A X +C Z +C X +B Y +A Z +C X +B X +A Z +A Z +C Z +A Z +C Z +C Z +A X +C X +A Z +C X +A Y +B Y +C Z +B Y +B X +C Z +A X +B Z +A Z +A Z +C Z +A Z +C Z +A Z +C X +C X +C X +C X +A Z +C Z +C X +B Y +A Z +B Y +A Y +C Z +A Z +C X +C Z +B Y +C X +A Y +B X +A Y +B X +B Y +C Z +A Y +B Y +A Y +B Y +C Z +C X +C X +C X +C Z +B Y +C Z +B X +C X +A Y +A X +B Y +A Z +C Z +A Y +A Z +C X +B Y +A Z +C Z +C X +C Y +C X +A Z +A Y +C X +A Y +C X +C X +A Z +B Y +C Z +C X +B X +B Y +A Z +A Z +B X +B Y +C X +B Y +C Z +B Y +C Y +B Y +B X +B Y +A Y +B Y +C Z +B X +B Y +C Z +A Z +C Z +B X +A Y +B X +C Z +B Y +A Y +C Z +C Z +C Y +C Z +A Y +C X +A Y +C Z +C Z +C Z +C Z +C Z +C X +C Z +C Z +B Y +C X +C Z +B X +C X +C Z +C X +A Z +C X +C X +C Z +C X +C X +C Z +A Z +B X +B Y +C Z +A Z +C X +B X +B Y +C Z +C Z +A Y +C X +C Z +C X +C Z +B Y +C X +C Z +C X +C X +C Z +C X +B X +C X +C Z +A Y +A Y +A Y +C Z +C Z +B X +C X +A Z +C Z +C X +C Z +B X +C Z +B Z +C X +A Y +C Z +A Y +C X +B Y +B Y +A Z +C Z +C Z +C Z +A Z +C X +A Y +C Z +A Y +C Z +A Z +A Z +B Y +C Z +A Z +C X +A Y +C Z +C Z +C X +C X +C X +A X +B Z +C Z +C X +A Y +A Z +C Z +B X +B Y +C X +C Z +B X +B Y +C X +B X +C Z +C X +C X +C X +C X +A Y +A Z +A Y +B Y +C Z +B Y +B Y +C Z +A X +C Z +B X +C Z +C Z +A Z +B Y +C Z +C Z +A Y +A Z +A Z +A Z +B X +C X +C X +B Y +C Z +C X +B Y +A Y +C X +C Z +C Z +C X +C Y +A Y +A Z +C X +C X +A Z +B X +C Z +A X +C Z +C X +C Z +A X +A Z +C X +B Y +C Z +C Z +B X +A Y +B Y +C Z +C Z +A Z +A Y +C Z +C Z +A X +B Y +C Z +C Z +B Y +C X +C Z +B X +B Y +A Z +C Z +C X +C X +C Z +B Z +B Y +C Z +C X +A Y +C X +A Y +A Z +B Y +B X +C Z +A Z +C Z +C Z +C Z +A Y +B Y +A Z +B Y +C Z +C X +B Y +C Z +A Y +C Z +A Z +C Z +C Z +C Z +A Z +C X +B Y +C Z +A Z +C Z +C Z +A Z +C Z +C X +B Z +C Z +C Z +A Z +C Z +C Z +B Y +B X +C Z +C Z +B Y +A Y +C Z +A Z +A Z +C Z +C X +C X +B X +C X +A Y +B X +A Y +C Z +C X +B Y +C Z +C X +C X +C X +B X +B Z +C Z +B Y +C X +A Z +C Z +C Z +A Z +A Z +C Z +C Z +A Z +A Z +A Z +C Z +A Z +C Y +A Z +C Z +C Z +C X +C X +C Z +C Z +A Z +C Z +A Z +C X +C X +C X +A Y +A Z +A Z +A Y +B X +C Z +C Z +B X +C Z +C X +B Y +C Z +C X +C X +B Y +B Y +A Y +A Z +B X +C X +B Y +B Y +B Y +C Z +C X +C X +A Y +B Z +A Z +A Z +B X +C X +A Y +C X +C Z +C X +A Y +A Z +C Z +A Z +C Z +C X +C X +A Z +B X +B X +B Y +C Z +C Z +C X +C X +C X +B Y +C Z +C X +B X +C Z +C X +B X +A Y +B Y +C Z +A Z +A Y +C Z +A Y +A Y +C Z +B Y +C Z +B Z +C Z +A Z +C X +C X +C Z +B X +C X +B Y +C Z +B X +C Z +C X +B X +B Y +B Z +B X +A Y +C X +C Z +C Z +A Y +B X +A Y +C X +C Z +B Y +C Z +C Z +C Z +A Z +A Z +A Y +C Z +B Y +C Z +C X +B Y +C Z +C Z +A X +C X +B Y +A Z +C Z +C X +A Z +A Y +C Z +C Z +B X +C Z +A Z +A Y +C X +A Y +C Z +C X +C X +C X +B Y +C X +A Y +C X +B Y +B X +A Y +B X +A Y +B Z +C Z +A Z +B Y +B X +C Z +C Z +C X +B Y +A Z +A Z +A Y +A Y +C Z +A Z +A Z +B Y +C X +C Z +C Z +C Z +A Y +A Z diff --git a/racket/aoc2022/day-03/day-03.ipynb b/racket/aoc2022/day-03/day-03.ipynb new file mode 100644 index 0000000..27b8086 --- /dev/null +++ b/racket/aoc2022/day-03/day-03.ipynb @@ -0,0 +1,168 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 3: Rucksack Reorganization\n", + "\n", + "**Part 1.** Every elf has a rucksack with two compartments. What's the total priority value of the items that appear in both compartments of each sack?\n", + "\n", + "**Part 2.** Each group of three elves is carrying exactly one item in common. What's the total priority value of those common items?\n", + "\n", + "To ease the conversion between strings, lists and sets I bring in some utility functions from `relation`. " + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(require racket\n", + " advent-of-code\n", + " threading\n", + " (only-in relation ->list ->set ->char))\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "The items in each elf's inventory are represented by a string of alphabetic (case-sensitive) characters, each with a \"priority value\":\n", + "* Lowercase item types `a` through `z` have priorities 1 through 26.\n", + "* Uppercase item types `A` through `Z` have priorities 27 through 52." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(define priority\n", + " (for/hash ([i (in-naturals 1)]\n", + " [c (in-sequences (inclusive-range 97 122) (inclusive-range 65 90))])\n", + " (values (->char c) i)))" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 1\n", + "\n", + "The front half and back half of the rucksack have one item in common we need to identify. For each rucksack in the inventory, we apply the following steps:\n", + "\n", + "1. Split the bag into the two halves,\n", + "2. find the common item in both halves (the intersection of the sets),\n", + "3. then look up that common item's value. " + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>7845</code>" + ], + "text/plain": [ + "7845" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define raw-inventory (~> (fetch-aoc-input (find-session) 2022 3) string-split))\n", + "\n", + "(for/sum ([bag (in-list raw-inventory)])\n", + " (define len (/ (string-length bag) 2))\n", + " (~>> bag\n", + " ->list\n", + " ((λ (xs) (list (take xs len) (drop xs len)))) ; step 1\n", + " (apply set-intersect _) ; step 2\n", + " set-first\n", + " (hash-ref priority))) ; step 3\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 2\n", + "\n", + "Now we need to take three rucksacks at a time and find the common item they all share. The procedure is simpler than Part 1's, especially with the `in-slice` function that automatically forms groups of three." + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>2790</code>" + ], + "text/plain": [ + "2790" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(for/sum ([bags (in-slice 3 raw-inventory)])\n", + " (~>> bags (map ->set) (apply set-intersect) set-first (hash-ref priority)))\n" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (Trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "Racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4, + "vscode": { + "interpreter": { + "hash": "7454d72389401259f8ab87ac90deac92d19baedf4a52e60301852b1f4c653c5c" + } + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-04/day-04.ipynb b/racket/aoc2022/day-04/day-04.ipynb new file mode 100644 index 0000000..44c8980 --- /dev/null +++ b/racket/aoc2022/day-04/day-04.ipynb @@ -0,0 +1,148 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 4: Camp Cleanup\n", + "\n", + "Each elf in a pair of elves is assigned a range of ID numbers.\n", + "\n", + "**Part 1.** How many pairs have one elf assigned to a range completely contained by the other's?\n", + "\n", + "**Part 2.** How many pairs have overlapping assignments?\n", + "\n", + "Since this problem heavily uses ranges, I'm using `rebellion/base/range` to do the heavy lifting." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "#lang iracket/lang #:require rackjure\n", + "(require advent-of-code\n", + " relation\n", + " rebellion/base/range)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 1\n", + "\n", + "All the assignments look like `\"11-22,33-44\"`, so we write a function to extract the numbers from the string with a regex, decompose the values with structural matching, and construct a pair of [`rebellion` ranges](https://docs.racket-lang.org/rebellion/Ranges.html).\n", + "\n", + "Once we have the two ranges, we can use a predicate that tests if one completely contains the other or vice versa to count the corresponding assignments." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>550</code>" + ], + "text/plain": [ + "550" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define assignments (~> (fetch-aoc-input (find-session) 2022 4) string-split))\n", + "\n", + "(define (parse-range str)\n", + " (match str\n", + " [(regexp #px\"(\\\\d+)-(\\\\d+),(\\\\d+)-(\\\\d+)\" (list _ a b c d))\n", + " (values (closed-range (->number a) (->number b)) (closed-range (->number c) (->number d)))]))\n", + "\n", + "(define (one-encloses-the-other? str)\n", + " (define-values (range1 range2) (parse-range str))\n", + " (or (range-encloses? range1 range2) (range-encloses? range2 range1)))\n", + "\n", + "(count one-encloses-the-other? assignments)\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 2\n", + "\n", + "The procedure for part 2 is the same, just using the predicate for overlapping ranges instead." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>931</code>" + ], + "text/plain": [ + "931" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define (one-overlaps-the-other? str)\n", + " (define-values (range1 range2) (parse-range str))\n", + " (range-overlaps? range1 range2))\n", + "\n", + "(count one-overlaps-the-other? assignments)\n" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (Trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "Racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4, + "vscode": { + "interpreter": { + "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1" + } + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-05/day-05.ipynb b/racket/aoc2022/day-05/day-05.ipynb new file mode 100644 index 0000000..34cf4e4 --- /dev/null +++ b/racket/aoc2022/day-05/day-05.ipynb @@ -0,0 +1,187 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 5: Supply Stacks\n", + "\n", + "You're operating a crane, following a set of instructions telling you how many boxes to move from one stack to another. After you follow the instructions, the top boxes in the stacks spell out a message.\n", + "\n", + "**Part 1.** What's the message if the crane moves one box at a time?\n", + "\n", + "**Part 2.** What's the message if the crane moves all of the boxes at once?\n", + "\n", + "I'm bringing in my usual utility functions." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "(require racket\n", + " advent-of-code\n", + " threading\n", + " (only-in relation ->string ->list ->number)\n", + " (only-in algorithms chunks-of))\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "The data file in this one is unusual: the first 10 lines are a pictorial representation of the stacks of boxes, and the remaining lines are instructions in the form `move X from Y to Z`.\n", + "\n", + "Tackling the boxes first, I can get the contents of each stack if I treat the picture as an array and transpose it, drop the first row that contains only brackets, then only take rows 1, 5, 9..., which are the rows with letters in them and trim the leading spaces from each row. I then use this list to create a hashtable." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [], + "source": [ + "(define assignments (~> (fetch-aoc-input (find-session) 2022 5) (string-split \"\\n\")))\n", + "\n", + "(define crates-list\n", + " (~>> assignments\n", + " (take _ 8)\n", + " (map ->list)\n", + " (apply map list _)\n", + " rest\n", + " (chunks-of _ 4)\n", + " (map (λ~> first ->string string-trim ->list) _)))\n", + "\n", + "(define crates\n", + " (for/hash ([c (in-list crates-list)] [i (in-naturals 1)])\n", + " (values i c)))\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "The instructions are a little easier; this is just a regex and destructuring like in Day 4." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [], + "source": [ + "(struct instruction (n from to))\n", + "\n", + "(define (parse-instruction str)\n", + " (match str\n", + " [(regexp #px\"move (\\\\d+) from (\\\\d) to (\\\\d)\" (list _ n from to))\n", + " (instruction (->number n) (->number from) (->number to))]))\n", + "\n", + "(define instructions (~>> assignments (drop _ 10) (map parse-instruction)))\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 1\n", + "\n", + "The main function to iterate over the list of instructions is the same for both parts, except for whether the boxes taken off of the origin stack are reversed or not when they end up on the destination stack. They end up reversed if they're taken off one at a time, and don't reverse if the whole stack is picked up at once.\n", + "\n", + "Once I've iterated through all the instructions, the `#:result` clause parses the final crate state." + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<code>\"WHTLRMZRC\"</code>" + ], + "text/plain": [ + "\"WHTLRMZRC\"" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define (find-crate-message cs [reverse? #true])\n", + " (define direction (if reverse? reverse identity))\n", + " (for/fold ([current-crates cs]\n", + " #:result (~>> (hash-values current-crates) (map first) (apply string)))\n", + " ([i (in-list instructions)])\n", + " (match-define (instruction n from to) i)\n", + " (define taken (~> (hash-ref current-crates from) (take _ n) direction))\n", + " (~> current-crates\n", + " (hash-update _ from (λ (v) (drop v n)))\n", + " (hash-update _ to (λ (v) (append taken v))))))\n", + "\n", + "(find-crate-message crates)" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 2\n", + "\n", + "The result, if the moved boxes don't get flipped:" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<code>\"GMPMLWNMG\"</code>" + ], + "text/plain": [ + "\"GMPMLWNMG\"" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(find-crate-message crates #false)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (Trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4, + "vscode": { + "interpreter": { + "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1" + } + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-05/day-05.rkt b/racket/aoc2022/day-05/day-05.rkt new file mode 100644 index 0000000..76d4ca6 --- /dev/null +++ b/racket/aoc2022/day-05/day-05.rkt @@ -0,0 +1,46 @@ +#lang racket + +(require advent-of-code + threading + (only-in relation ->string ->list ->number) + (only-in algorithms chunks-of)) + +(define data (~> (fetch-aoc-input (find-session) 2022 5) (string-split "\n"))) + +(struct instruction (n from to)) + +(define crates-list + (~>> data + (take _ 8) + (map (λ~>> ->list)) + (apply map list _) + rest + (chunks-of _ 4) + (map (λ~> first ->string string-trim ->list) _))) + +(define crates + (for/hash ([c (in-list crates-list)] [i (in-naturals 1)]) + (values i c))) + +(define (parse-instruction str) + (match str + [(regexp #px"move (\\d+) from (\\d) to (\\d)" (list _ n from to)) + (instruction (->number n) (->number from) (->number to))])) + +(define instructions (~>> data (drop _ 10) (map parse-instruction))) + +(define (find-crate-message cs [reverse-function reverse]) + (for/fold ([current-crates cs] + #:result (~>> (hash-values current-crates) (map first) (apply string))) + ([i (in-list instructions)]) + (match-define (instruction n from to) i) + (define taken (~> (hash-ref current-crates from) (take _ n) reverse-function)) + (~> current-crates + (hash-update _ from (λ (v) (drop v n))) + (hash-update _ to (λ (v) (append taken v)))))) + +;; part 1 +(find-crate-message crates) + +;; part 2 +(find-crate-message crates identity) diff --git a/racket/aoc2022/day-06/day-06.ipynb b/racket/aoc2022/day-06/day-06.ipynb new file mode 100644 index 0000000..0c89fa1 --- /dev/null +++ b/racket/aoc2022/day-06/day-06.ipynb @@ -0,0 +1,122 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 6: Tuning Trouble\n", + "\n", + "You're parsing a buffer of characters, looking for a \"marker\": the index of the first character where the previous $n$ characters are all unique.\n", + "\n", + "**Part 1.** What if $n = 4$, for the \"start of packet\" marker?\n", + "\n", + "**Part 2.** What if $n = 14$, for the \"start of message\" marker?" + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": {}, + "outputs": [], + "source": [ + "(require racket\n", + " advent-of-code\n", + " (only-in algorithms sliding))\n" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Parts 1 and 2\n", + "\n", + "`(sliding xs n)` returns all the overlapping sublists of `xs` that are `n` elements wide. This turns this problem into a simple `for` comprehension, just looking for the first sublist with no duplicates (which means its length after deduplication doesn't change).\n", + "\n", + "The solution to part 1 and part 2 is the same, just differing in how wide the window is." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<code>1042</code>" + ], + "text/plain": [ + "1042" + ] + }, + "execution_count": 2, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define buffer (fetch-aoc-input (find-session) 2022 6))\n", + "\n", + "(define (find-marker data type)\n", + " (define n\n", + " (match type\n", + " ['start-of-packet 4]\n", + " ['start-of-message 14]))\n", + " (for/first ([chunk (in-list (sliding (string->list data) n))]\n", + " [i (in-naturals n)]\n", + " #:when (= n (~> chunk remove-duplicates length)))\n", + " i))\n", + "\n", + "(find-marker buffer 'start-of-packet)\n", + "\n" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": {}, + "outputs": [ + { + "data": { + "text/html": [ + "<code>2980</code>" + ], + "text/plain": [ + "2980" + ] + }, + "execution_count": 3, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(find-marker buffer 'start-of-message)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4, + "vscode": { + "interpreter": { + "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1" + } + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-06/day-06.rkt b/racket/aoc2022/day-06/day-06.rkt new file mode 100644 index 0000000..1c167a6 --- /dev/null +++ b/racket/aoc2022/day-06/day-06.rkt @@ -0,0 +1,22 @@ +#lang racket + +(require advent-of-code + (only-in algorithms sliding)) + +(define buffer (fetch-aoc-input (find-session) 2022 6)) + +(define (find-marker data type) + (define n + (case type + [(start-of-packet) 4] + [(start-of-message) 14])) + (for/first ([chunk (in-list (sliding (string->list data) n))] + [i (in-naturals n)] + #:unless (check-duplicates chunk)) + i)) + +;; part 1 +(find-marker buffer 'start-of-packet) + +;; part 2 +(find-marker buffer 'start-of-message) diff --git a/racket/aoc2022/day-07/day-07.rkt b/racket/aoc2022/day-07/day-07.rkt new file mode 100644 index 0000000..3826cc4 --- /dev/null +++ b/racket/aoc2022/day-07/day-07.rkt @@ -0,0 +1,36 @@ +#lang racket + +(require advent-of-code + fancy-app + threading + (only-in relation ->number)) + +(define command-output (~> (fetch-aoc-input (find-session) 2022 7) (string-split "\n"))) + +(define (parse-commands cmds) + (define (update-sizes h path size) + (match path + ['() h] + [(list* _ fs) (update-sizes (hash-update h path (+ _ size) 0) fs size)])) + + (for/fold ([folders (hash)] [current-path '()] [previously-seen? #false] #:result folders) + ([cmd (in-list cmds)]) + (match (string-split cmd) + [(list "$" "ls") (values folders current-path (hash-has-key? folders current-path))] + [(list "$" "cd" "/") (values folders '("/") #false)] + [(list "$" "cd" "..") (values folders (rest current-path) #false)] + [(list "$" "cd" folder) (values folders (cons folder current-path) #false)] + [(list "dir" _) (values folders current-path previously-seen?)] + [(list (app ->number size) _) + (cond + [previously-seen? (values folders current-path previously-seen?)] + [else (values (update-sizes folders current-path size) current-path previously-seen?)])]))) + +(define folders (parse-commands command-output)) + +;; part 1 +(for/sum ([(_ v) (in-hash folders)] #:when (<= v 100000)) v) + +;; part 2 +(define required-to-delete (- 30000000 (- 70000000 (hash-ref folders '("/"))))) +(~>> folders hash-values (filter (> _ required-to-delete)) (apply min)) diff --git a/racket/aoc2022/day-08/day-08.ipynb b/racket/aoc2022/day-08/day-08.ipynb new file mode 100644 index 0000000..890a9bb --- /dev/null +++ b/racket/aoc2022/day-08/day-08.ipynb @@ -0,0 +1,257 @@ +{ + "cells": [ + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "### Advent of Code 2022\n", + "#### Day 8: Treetop Tree House\n", + "\n", + "For a rectangular grid of trees of varying heights,\n", + "\n", + "**Part 1.** How many trees are visible (not blocked by same-height or taller trees in their row or column) from outside the patch?\n", + "\n", + "**Part 2.** What's the tree with the best \"scenic score\" (the product of the number of trees it can see in each cardinal direction)?\n", + "\n", + "For this solution, I didn't use any packages besides the standard distribution and `advent-of-code`." + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(require racket\n", + " advent-of-code)" + ] + }, + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 1\n", + "\n", + "I built this array as a hashtable with a coordinate struct as the key and the tree height as the value, which makes it easy to check if a particular location falls outside the grid." + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(struct posn (r c) #:transparent)\n", + "\n", + "(define (make-tree-grid data)\n", + " (for*/hash ([(row r) (in-indexed data)] [(col c) (in-indexed (in-string row))])\n", + " (values (posn r c) (string->number (string col)))))\n", + "\n", + "(define tree-grid (make-tree-grid (in-lines (open-aoc-input (find-session) 2022 8))))" + ] + }, + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "A tree is visible if there aren't any other trees as tall as it or taller blocking the visibility in at least one of the cardinal directions. We check in a particular direction by repeatedly stepping outwards from the original coordinate and checking if we've found a blocking tree yet.\n", + "\n", + "The `for/first` returns `#true` if it finds a blocking tree and `#false` if it runs out of trees to check, and the result is negated to turn it into a predicate about whether the tree can see (and be seen from) outside." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(define (can-see-to-outside? p height dr dc h)\n", + " (match-define (posn r c) p)\n", + " (not (for/first ([n (in-naturals 1)]\n", + " #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]\n", + " #:break (not (hash-has-key? h p*))\n", + " #:when (<= height (hash-ref h p*)))\n", + " #true)))" + ] + }, + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "Now we need a function to check the four cardinal directions and see if at least one of them is unblocked." + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(define (visible-in-any-direction? p height h)\n", + " (for*/or ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))\n", + " (can-see-to-outside? p height dr dc h)))" + ] + }, + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "Finally, add 1 to the count for every tree that's visible:" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>1733</code>" + ], + "text/plain": [ + "1733" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define (count-visible-trees trees)\n", + " (for/sum ([(tree-posn height) (in-hash trees)])\n", + " (cond\n", + " [(visible-in-any-direction? tree-posn height trees) 1]\n", + " [else 0])))\n", + "\n", + "(count-visible-trees tree-grid)" + ] + }, + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "##### Part 2\n", + "\n", + "Now we're searching for the tree with the most interior visibility, which is the product of how far we can look in each cardinal direction before running out of visible trees. \n", + "\n", + "The search is similar, except now we're calculating a score instead of just checking a predicate. We walk one step at a time, increment the counter and check each tree; if we find a blocking tree, we return the counter, and if we run out of trees to check we break and return the previous counter value. If there aren't any trees in a direction and the `for` body is never evaluated, `for/last` returns `#false`, which is equivalent to a visibility of 0." + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [], + "source": [ + "(define (scenic-score-in-direction p height dr dc h)\n", + " (match-define (posn r c) p)\n", + " (define score\n", + " (for/last ([n (in-naturals 1)]\n", + " #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]\n", + " #:break (not (hash-has-key? h p*))\n", + " #:final (<= height (hash-ref h p*)))\n", + " n))\n", + " (if (not score) 0 score))\n", + "\n", + "(define (scenic-score p height h)\n", + " (for*/product ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))\n", + " (scenic-score-in-direction p height dr dc h)))" + ] + }, + { + "attachments": {}, + "cell_type": "markdown", + "metadata": {}, + "source": [ + "With these functions written, calculate each tree's score and find the maximum:" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "vscode": { + "languageId": "racket" + } + }, + "outputs": [ + { + "data": { + "text/html": [ + "<code>284648</code>" + ], + "text/plain": [ + "284648" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "(define (find-best-scenic-score trees)\n", + " (apply max\n", + " (for/list ([(tree-posn height) (in-hash trees)])\n", + " (scenic-score tree-posn height trees))))\n", + "\n", + "(find-best-scenic-score tree-grid)" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Racket (Trusted)", + "language": "racket", + "name": "racket-trusted" + }, + "language_info": { + "codemirror_mode": "scheme", + "file_extension": ".rkt", + "mimetype": "text/x-racket", + "name": "Racket", + "pygments_lexer": "racket", + "version": "8.7" + }, + "orig_nbformat": 4, + "vscode": { + "interpreter": { + "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1" + } + } + }, + "nbformat": 4, + "nbformat_minor": 2 +} diff --git a/racket/aoc2022/day-08/day-08.rkt b/racket/aoc2022/day-08/day-08.rkt new file mode 100644 index 0000000..6b60eca --- /dev/null +++ b/racket/aoc2022/day-08/day-08.rkt @@ -0,0 +1,56 @@ +#lang racket + +(require advent-of-code) + +(struct posn (r c) #:transparent) + +(define (make-tree-grid data) + (for*/hash ([(row r) (in-indexed data)] [(col c) (in-indexed (in-string row))]) + (values (posn r c) (string->number (string col))))) + +(define tree-grid (make-tree-grid (in-lines (open-aoc-input (find-session) 2022 8)))) + +;; part 1 + +(define (can-see-to-outside? p height dr dc h) + (match-define (posn r c) p) + (not (for/first ([n (in-naturals 1)] + #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))] + #:break (not (hash-has-key? h p*)) + #:when (<= height (hash-ref h p*))) + #true))) + +(define (visible-in-any-direction? p height h) + (for*/or ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc)))) + (can-see-to-outside? p height dr dc h))) + +(define (count-visible-trees trees) + (for/sum ([(tree-posn height) (in-hash trees)]) + (cond + [(visible-in-any-direction? tree-posn height trees) 1] + [else 0]))) + +(count-visible-trees tree-grid) + +;; part 2 + +(define (scenic-score-in-direction p height dr dc h) + (match-define (posn r c) p) + (define score + (for/last ([n (in-naturals 1)] + #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))] + #:break (not (hash-has-key? h p*)) + #:final (<= height (hash-ref h p*))) + n)) + (if (not score) 0 score)) + +(define (scenic-score p height h) + (for*/product ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc)))) + (scenic-score-in-direction p height dr dc h))) + +(define (find-best-scenic-score trees) + (apply max + (for/list ([(tree-posn height) (in-hash trees)]) + (scenic-score tree-posn height trees)))) + +(find-best-scenic-score tree-grid) diff --git a/racket/aoc2022/day-09/day-09.rkt b/racket/aoc2022/day-09/day-09.rkt new file mode 100644 index 0000000..0390d2e --- /dev/null +++ b/racket/aoc2022/day-09/day-09.rkt @@ -0,0 +1,76 @@ +#lang racket +(require advent-of-code + threading) + +(struct cmd (dir amt)) +(struct posn (x y) #:transparent) + +(define moves + (~> (fetch-aoc-input (find-session) 2022 9) + (string-split "\n") + (map (λ~> (string-split _) + (match _ + [(list dir amt) (cmd (string->symbol dir) (string->number amt))])) + _))) + +(define (move-head p dir) + (match-define (posn x y) p) + (match dir + ['U (posn x (add1 y))] + ['D (posn x (sub1 y))] + ['R (posn (add1 x) y)] + ['L (posn (sub1 x) y)])) + +(define (avg n m) + (/ (+ n m) 2)) + +(define (manhattan-distance p1 p2) + (match-define (posn x1 y1) p1) + (match-define (posn x2 y2) p2) + (+ (abs (- x2 x1)) (abs (- y2 y1)))) + +(define (follow-head head tail) + (match-define (posn hx hy) head) + (match-define (posn tx ty) tail) + + (case (manhattan-distance head tail) + [(0 1) tail] + [(2 4) + (cond + [(and (= 1 (abs (- hx tx)) (abs (- hy ty)))) tail] + [else (posn (avg hx tx) (avg hy ty))])] + [(3) + (cond + [(= 2 (abs (- hx tx))) (posn (avg hx tx) hy)] + [(= 2 (abs (- hy ty))) (posn hx (avg hy ty))])])) + +;; part 1 +(for*/fold ([head (posn 0 0)] [tail (posn 0 0)] [tail-posns (set)] #:result (set-count tail-posns)) + ([move (in-list moves)] #:do [(match-define (cmd dir amt) move)] [_ (in-range amt)]) + (define new-head (move-head head dir)) + (define new-tail (follow-head new-head tail)) + (values new-head new-tail (set-add tail-posns new-tail))) + +;; part 2 +(for*/fold ([knots (make-list 10 (posn 0 0))] [tail-posns (set)] #:result (set-count tail-posns)) + ([move (in-list moves)] #:do [(match-define (cmd dir amt) move)] [_ (in-range amt)]) + (define updated-knots + (for/fold ([knots-list (list (move-head (first knots) dir))]) + ([following-knot (in-list (rest knots))]) + (cons (follow-head (car knots-list) following-knot) knots-list))) + (values (reverse updated-knots) (set-add tail-posns (first updated-knots)))) + +;; refactor: part 1 and 2 combined +(define (follow-tail move-list rope-length) + (for*/fold ([knots (make-list rope-length (posn 0 0))] + [tail-posns (set)] + #:result (set-count tail-posns)) + ([move (in-list move-list)] #:do [(match-define (cmd dir amt) move)] [_ (in-range amt)]) + (define updated-knots + (for/fold ([knots-list (list (move-head (first knots) dir))]) + ([following-knot (in-list (rest knots))]) + (cons (follow-head (car knots-list) following-knot) knots-list))) + (values (reverse updated-knots) (set-add tail-posns (first updated-knots))))) + +(time (follow-tail moves 2)) +(time (follow-tail moves 10)) diff --git a/racket/aoc2022/day-10/day-10.rkt b/racket/aoc2022/day-10/day-10.rkt new file mode 100644 index 0000000..70c80d3 --- /dev/null +++ b/racket/aoc2022/day-10/day-10.rkt @@ -0,0 +1,43 @@ +#lang racket + +(require advent-of-code + threading + fancy-app + (only-in algorithms chunks-of)) + +(define/match (process-instruction _) + [((list "noop")) (list 'noop)] + [((list "addx" (app string->number val))) (list 'noop (cons 'addx val))]) + +(define instructions + (~> (fetch-aoc-input (find-session) 2022 10) + (string-split "\n") + (map (λ~> string-split process-instruction) _) + (apply append _))) + +;; part 1 +(define interesting-times (inclusive-range 20 220 40)) + +(define/match (evaluate-instruction _op acc) + [('noop _) acc] + [((cons 'addx n) _) (+ acc n)]) + +(for/fold ([acc 1] [interesting-strengths 0] #:result interesting-strengths) + ([inst (in-list instructions)] [i (in-naturals 1)]) + (define new-interesting + (if (member i interesting-times) (+ interesting-strengths (* i acc)) interesting-strengths)) + (values (evaluate-instruction inst acc) new-interesting)) + +;; part 2 +(for/fold ([acc 1] [pixels '()] #:result (~> pixels reverse (chunks-of 40) (map (apply string _) _))) + ([inst (in-list instructions)] [i (in-naturals)]) + (define new-pixel (if (member (modulo i 40) (list (sub1 acc) acc (add1 acc))) #\█ #\space)) + (values (evaluate-instruction inst acc) (cons new-pixel pixels))) + +; for my data set, +; '("███ ████ ████ █ █ ████ ████ █ █ ██ " +; "█ █ █ █ █ █ █ █ █ █ █ █ " +; "█ █ █ ███ ██ ███ ███ ████ █ █ " +; "███ █ █ █ █ █ █ █ █ ████ " +; "█ █ █ █ █ █ █ █ █ █ █ █ " +; "█ █ ████ ████ █ █ ████ █ █ █ █ █ ") diff --git a/racket/aoc2022/day-11/day-11.rkt b/racket/aoc2022/day-11/day-11.rkt new file mode 100644 index 0000000..af7b4ee --- /dev/null +++ b/racket/aoc2022/day-11/day-11.rkt @@ -0,0 +1,85 @@ +#lang racket +(require threading) + +(struct monkey ([items #:mutable] operation modulus yes no)) + +;; really don't feel like parsing the input today +(define monkeys-list + (list (cons 0 (monkey '(97 81 57 57 91 61) + (λ (n) (* n 7)) + 11 5 6)) + (cons 1 (monkey '(88 62 68 90) + (λ (n) (* n 17)) + 19 4 2)) + (cons 2 (monkey '(74 87) + (λ (n) (+ n 2)) + 5 7 4)) + (cons 3 (monkey '(53 81 60 87 90 99 75) + (λ (n) (+ n 1)) + 2 2 1)) + (cons 4 (monkey '(57) + (λ (n) (+ n 6)) + 13 7 0)) + (cons 5 (monkey '(54 84 91 55 59 72 75 70) + (λ (n) (* n n)) + 7 6 3)) + (cons 6 (monkey '(95 79 79 68 78) + (λ (n) (+ n 3)) + 3 1 3)) + (cons 7 (monkey '(61 97 67) + (λ (n) (+ n 4)) + 17 0 5)))) + +(define monkey-lcm (~> monkeys-list (map (λ~> cdr monkey-modulus) _) (apply lcm _))) + +;; part 1 +(define monkeys-count-pt1 (make-hash)) +(define monkeys-hash-pt1 (make-hash monkeys-list)) + +(for + ([rnd (in-range 20)]) + (for + ([turn (inclusive-range 0 7)]) + (match-define (monkey items op modulus yes no) (hash-ref monkeys-hash-pt1 turn)) + (for ([i (in-list items)]) + (define i* (quotient (op i) 3)) + (define m (if (= 0 (modulo i* modulus)) yes no)) + (match-define (monkey items* op* modulus* yes* no*) (hash-ref monkeys-hash-pt1 m)) + (hash-update! monkeys-count-pt1 turn add1 0) + (hash-set! monkeys-hash-pt1 + m + (monkey (append items* (list i*)) op* modulus* yes* no*))) + (hash-set! monkeys-hash-pt1 turn (monkey '() op modulus yes no)))) + +(~> monkeys-count-pt1 + hash->list + (sort _ > #:key cdr) + (take _ 2) + (map cdr _) + (apply * _)) + +;; part 2 +(define monkeys-count-pt2 (make-hash)) +(define monkeys-hash-pt2 (make-hash monkeys-list)) + +(for + ([rnd (in-range 10000)]) + (for + ([turn (inclusive-range 0 7)]) + (match-define (monkey items op modulus yes no) (hash-ref monkeys-hash-pt2 turn)) + (for ([i (in-list items)]) + (define i* (op i)) + (define m (if (= 0 (modulo i* modulus)) yes no)) + (match-define (monkey items* op* modulus* yes* no*) (hash-ref monkeys-hash-pt2 m)) + (hash-update! monkeys-count-pt2 turn add1 0) + (hash-set! monkeys-hash-pt2 + m + (monkey (append items* (list (remainder i* monkey-lcm))) op* modulus* yes* no*))) + (hash-set! monkeys-hash-pt2 turn (monkey '() op modulus yes no)))) + +(~> monkeys-count-pt2 + hash->list + (sort _ > #:key cdr) + (take _ 2) + (map cdr _) + (apply * _))
\ No newline at end of file diff --git a/racket/aoc2022/day-12/day-12.rkt b/racket/aoc2022/day-12/day-12.rkt new file mode 100644 index 0000000..c3f01ac --- /dev/null +++ b/racket/aoc2022/day-12/day-12.rkt @@ -0,0 +1,46 @@ +#lang racket + +(require advent-of-code + graph) + +(define raw-terrain (fetch-aoc-input (find-session) 2022 12 #:cache #true)) +(define special-points (make-hash)) + +(define terrain-mesh + (for*/hash ([(row x) (in-indexed (string-split raw-terrain))] [(col y) (in-indexed row)]) + (define p (cons x y)) + (case col + [(#\S) + (hash-set! special-points 'start p) + (values p 0)] + [(#\E) + (hash-set! special-points 'end p) + (values p 25)] + [else (values p (- (char->integer col) (char->integer #\a)))]))) + +(define (neighbors p) + (match-define (cons x y) p) + (for*/list ([dx (in-list '(-1 0 1))] + [dy (in-list '(-1 0 1))] + #:when (= 1 (abs (+ dx dy))) + #:do [(define p* (cons (+ x dx) (+ y dy)))] + #:when (hash-has-key? terrain-mesh p*)) + p*)) + +(define paths + (directed-graph (for*/list ([p (in-list (hash-keys terrain-mesh))] + [p* (in-list (neighbors p))] + #:unless (> (sub1 (hash-ref terrain-mesh p*)) + (hash-ref terrain-mesh p))) + (list p p*)))) + +;; part 1 +(time (match-define-values (distances _) (bfs paths (hash-ref special-points 'start))) + (hash-ref distances (hash-ref special-points 'end))) + +;; part 2 +(time (for/lists + (lengths #:result (apply min lengths)) + ([start (in-list (hash-keys terrain-mesh))] #:when (= 0 (hash-ref terrain-mesh start))) + (match-define-values (distances _) (bfs paths start)) + (hash-ref distances (hash-ref special-points 'end)))) diff --git a/racket/aoc2022/day-13/day-13.rkt b/racket/aoc2022/day-13/day-13.rkt new file mode 100644 index 0000000..39435e9 --- /dev/null +++ b/racket/aoc2022/day-13/day-13.rkt @@ -0,0 +1,28 @@ +#lang racket + +(require advent-of-code) + +(define raw-packets + (parameterize ([current-readtable (make-readtable #f #\, #\space #f)]) + (port->list read (open-aoc-input (find-session) 2022 13 #:cache #true)))) + +(define (compare xs ys) + (match* (xs ys) + [('() (list* _)) #true] + [((list* _) '()) #false] + [((list* _same x-rest) (list* _same y-rest)) (compare x-rest y-rest)] + [((list* (? integer? x) _) (list* (? integer? y) _)) (< x y)] + [((list* (? list? xs*) _) (list* (? list? ys*) _)) (compare xs* ys*)] + [(xs (list* (? integer? y) y-rest)) (compare xs (cons (list y) y-rest))] + [((list* (? integer? x) x-rest) ys) (compare (cons (list x) x-rest) ys)])) + +;; part 1 +(for/sum ([i (in-naturals 1)] [packet (in-slice 2 raw-packets)] #:when (apply compare packet)) i) + +;; part 2 +(define divider-packets (list '((2)) '((6)))) +(define amended-packets (append divider-packets raw-packets)) + +(for/product ([i (in-naturals 1)] [packet (in-list (sort amended-packets compare))] + #:when (member packet divider-packets)) + i) diff --git a/racket/aoc2022/day-14/day-14.rkt b/racket/aoc2022/day-14/day-14.rkt new file mode 100644 index 0000000..88ba297 --- /dev/null +++ b/racket/aoc2022/day-14/day-14.rkt @@ -0,0 +1,51 @@ +#lang racket + +(require advent-of-code + threading + algorithms) + +(define data (fetch-aoc-input (find-session) 2022 14 #:cache #true)) + +(define (trace-line-between-points p1 p2) + (match* (p1 p2) + [((list x y1) (list x y2)) (map (λ (y) (cons x y)) (inclusive-range (min y1 y2) (max y1 y2)))] + [((list x1 y) (list x2 y)) (map (λ (x) (cons x y)) (inclusive-range (min x1 x2) (max x1 x2)))])) + +(define (find-points-in-structure str) + (define endpoints + (for/list ([coord-pair (in-list (string-split str " -> "))]) + (for/list ([coord (in-list (string-split coord-pair ","))]) + (string->number coord)))) + (~>> endpoints (adjacent-map trace-line-between-points) (apply append) (list->set))) + +(define blocked-locations + (~> data (string-split "\n") (map find-points-in-structure _) (apply set-union _))) + +(define max-vertical-distance (~>> blocked-locations (set->list) (argmax cdr) cdr add1)) + +(define (open? pts p) + (not (set-member? pts p))) + +;; part 1 +(define (trace-grain pts path #:at-limit do-at-limit) + (match-define (list* (and p (cons x y)) _) path) + (match-define (list dest-1 dest-2 dest-3) (map (λ (d) (cons (+ x d) (add1 y))) '(0 -1 1))) + (cond + [(>= y max-vertical-distance) (values (do-at-limit pts p) path)] + [(open? pts dest-1) (trace-grain pts (cons dest-1 path) #:at-limit do-at-limit)] + [(open? pts dest-2) (trace-grain pts (cons dest-2 path) #:at-limit do-at-limit)] + [(open? pts dest-3) (trace-grain pts (cons dest-3 path) #:at-limit do-at-limit)] + [else (values (set-add pts (car path)) path)])) + +(time (for/fold ([pts blocked-locations] [path (list (cons 500 0))] [grains 0] #:result grains) + ([_ (in-naturals 1)]) + (define-values (pts* path*) (trace-grain pts path #:at-limit (const 'break))) + #:break (equal? pts* 'break) + (values pts* (cdr path*) (add1 grains)))) + +;; part 2 +(time (for/fold ([pts blocked-locations] [path (list (cons 500 0))] [grains 0] #:result grains) + ([_ (in-naturals 1)]) + #:break (not (open? pts (cons 500 0))) + (define-values (pts* path*) (trace-grain pts path #:at-limit set-add)) + (values pts* (cdr path*) (add1 grains)))) diff --git a/racket/aoc2022/day-15/day-15.rkt b/racket/aoc2022/day-15/day-15.rkt new file mode 100644 index 0000000..b050807 --- /dev/null +++ b/racket/aoc2022/day-15/day-15.rkt @@ -0,0 +1,54 @@ +#lang racket + +(require advent-of-code + threading + fancy-app + algorithms + (prefix-in iset- data/integer-set)) + +(struct beacon-record (sensor beacon)) +(struct posn (x y)) + +(define beacon-records + (~> (fetch-aoc-input (find-session) 2022 15 #:cache #true) + (string-split "\n") + (map (λ~> (string-replace #px"[^\\d\\s-]" "") + string-split + (map string->number _) + (chunks-of 2) + (map (apply posn _) _) + (apply beacon-record _)) + _))) + +(define (manhattan-distance-to-beacon record) + (match-define (beacon-record (posn sx sy) (posn bx by)) record) + (+ (abs (- sx bx)) (abs (- sy by)))) + +(define (coverage-at-row record row) + (match-define (beacon-record (posn sx sy) _) record) + (define x-distance (- (manhattan-distance-to-beacon record) (abs (- row sy)))) + (cond + [(negative? x-distance) (iset-make-range)] + [else (iset-make-range (- sx x-distance) (+ sx x-distance))])) + +(define (total-coverage-at-row records row) + (for/fold ([coverage (iset-make-range)]) ([r (in-list records)]) + (iset-union coverage (coverage-at-row r row)))) + +;; part 1 +(define (coverage-without-beacons records row) + (~> (total-coverage-at-row records row) + iset-count + (- (count (λ (b) (= row (posn-y b))) + (~> beacon-records (map beacon-record-beacon _) remove-duplicates))))) + +(coverage-without-beacons beacon-records 2000000) + +;; part 2 +(define (find-only-beacon beacon-records size) + (for/first ([y (in-range 0 size)] + #:do [(define xs (iset-complement (total-coverage-at-row beacon-records y) 0 size))] + #:when (= 1 (iset-count xs))) + (+ (* 4000000 (iset-get-integer xs)) y))) + +(find-only-beacon beacon-records 4000000) diff --git a/racket/aoc2022/day-16/day-16.rkt b/racket/aoc2022/day-16/day-16.rkt new file mode 100644 index 0000000..5ec56d6 --- /dev/null +++ b/racket/aoc2022/day-16/day-16.rkt @@ -0,0 +1,107 @@ +#lang racket + +(require advent-of-code + fancy-app + graph + threading) + +(define (process-line str) + (match str + [(regexp #px"Valve (\\w\\w) has flow rate=(\\d+); tunnels? leads? to valves? (.+)" + (list _ name (app string->number rate) (app (string-split _ ", ") valves))) + (list name rate valves)])) + +(define cave-data + (~> (fetch-aoc-input (find-session) 2022 16 #:cache #true) + (string-split "\n") + (map process-line _))) + +(define cave-map + (for*/lists (tunnels #:result (directed-graph tunnels)) + ([valve (in-list cave-data)] #:do [(match-define (list name _ valves) valve)] + [destination (in-list valves)]) + (list name destination))) + +(define valve-flows + (for/hash ([valve (in-list cave-data)] + #:do [(match-define (list name flow _) valve)] + #:when (> flow 0)) + (values name flow))) + +(define shortest-path-lengths (johnson cave-map)) + +(define (reachable-destinations start dests minutes-left) + (for/list ([(dest _) (in-hash dests)] + #:do [(define travel-time + (hash-ref shortest-path-lengths (list start dest) minutes-left))] + #:when (<= 1 travel-time minutes-left)) + (cons dest travel-time))) + +;; part 1 +(define (find-best-single-route start + [minutes-left 30] + [current-pressure 0] + [available-valves valve-flows]) + (cond + [(>= minutes-left 1) + (for/fold ([running-pressure current-pressure] + [remaining-valves available-valves] + #:result (cons running-pressure remaining-valves)) + ([candidate (reachable-destinations start available-valves minutes-left)]) + (match-define (cons dest travel-time) candidate) + (define minutes-left* (- minutes-left (add1 travel-time))) + (match-define (cons candidate-pressure remaining-valves*) + (find-best-single-route dest + minutes-left* + (+ current-pressure (* (hash-ref valve-flows dest) minutes-left*)) + (hash-remove available-valves dest))) + (if (> candidate-pressure running-pressure) + (values candidate-pressure remaining-valves*) + (values running-pressure remaining-valves*)))] + [else (cons current-pressure available-valves)])) + +(car (find-best-single-route "AA")) + +;; part 2 + +(define (possible-paths start dests minutes-left) + (cond + [(or (hash-empty? dests) (< minutes-left 3)) '()] + [else + (for/fold ([path '()]) ([dest (in-list (reachable-destinations start dests minutes-left))]) + (match-define (cons valve minutes) dest) + (define dests* (hash-remove dests valve)) + (define next-valves (possible-paths valve dests* (- minutes-left minutes))) + (append (list (list dest)) (map (cons dest _) next-valves) path))])) + +(define (flow-for-path path minutes [sum 0]) + (match path + ['() sum] + [(list* (cons valve dist) tail) + (define valve-open-for (- minutes dist 1)) + (flow-for-path tail valve-open-for (+ sum (* (hash-ref valve-flows valve) valve-open-for)))])) + +(define minutes-left 26) + +(define human-paths + (~>> (possible-paths "AA" valve-flows minutes-left) + (map (λ (path) (cons (flow-for-path path minutes-left) (map car path)))) + (sort _ > #:key car))) + +(define (best-possible-elephant-path human-path) + (define remaining-dests + (for/hash ([(dest flow) (in-hash valve-flows)] #:unless (member dest (cdr human-path))) + (values dest flow))) + (~>> (possible-paths "AA" remaining-dests minutes-left) + (map (λ (path) (cons (flow-for-path path minutes-left) (map car path)))) + (sort _ > #:key car) + car)) + +;; this takes a long time to run but I stuck a displayln in for debugging +;; and just took the highest max-flow after letting it run for a while and waiting until +;; it stopped printing new bests to console +(for*/fold ([max-flow 0]) + ([human-path (in-list human-paths)] + #:do [(define elephant-path (best-possible-elephant-path human-path))]) + (define combined-flow (+ (car human-path) (car elephant-path))) + (if (< max-flow combined-flow) combined-flow max-flow)) diff --git a/racket/aoc2022/day-17/day-17.rkt b/racket/aoc2022/day-17/day-17.rkt new file mode 100644 index 0000000..28e8763 --- /dev/null +++ b/racket/aoc2022/day-17/day-17.rkt @@ -0,0 +1,53 @@ +#lang racket + +(require advent-of-code + threading + fancy-app + data/collection) + +(define (relative-rock-coordinates rock) + (for*/hash ([(row y) (in-indexed (reverse rock))] [(_col x) (in-indexed row)]) + (values (cons x y) #true))) + +(define rock-shapes + (~> (open-input-file "./2022/day-17/rock-shapes") + port->string + (string-split "\n\n") + (map (λ~> (string-split _ "\n") (map string->list _) relative-rock-coordinates) _))) + +(define gusts + (~> (fetch-aoc-input (find-session) 2022 17 #:cache #true) + string-trim + string->list + (map (match-lambda + [#\> 1] + [#\< -1]) + _))) + +(define (place-new-rock rock elevation) + (for/hash ([(posn _) (in-hash rock)]) + (match-define (cons x y) posn) + (values (cons (+ x 3) (+ y elevation 4)) #true))) + +(define (gust-move rock wind cave) + (define moved-rock + (for/hash ([(posn _) (in-hash rock)]) + (match-define (cons x y) posn) + (define posn* (cons (+ x wind) y)) + (if (hash-has-key? cave posn) (values 'collision #t) (values posn* #t)))) + (if (hash-has-key? moved-rock 'collision) rock moved-rock)) + +(for/fold ([cave (hash)] + [falling-rock #f] + [top-of-rocks 0] + [rock-cycle (cycle rock-shapes)] + [rock-number 0] + #:result top-of-rocks) + (#:break (> rock-number 2022) [gust (in-cycle gusts)]) + (cond + [(not falling-rock) + (values cave + (~> (first rock-cycle) (place-new-rock top-of-rocks) (gust-move gust cave)) + top-of-rocks + (rest rock-cycle) + (add1 rock-number))])) diff --git a/racket/aoc2022/day-17/rock-shapes b/racket/aoc2022/day-17/rock-shapes new file mode 100644 index 0000000..fbcc382 --- /dev/null +++ b/racket/aoc2022/day-17/rock-shapes @@ -0,0 +1,17 @@ +#### + +.#. +### +.#. + +..# +..# +### + +# +# +# +# + +## +##
\ No newline at end of file diff --git a/racket/aoc2022/day-18/day-18.rkt b/racket/aoc2022/day-18/day-18.rkt new file mode 100644 index 0000000..157784d --- /dev/null +++ b/racket/aoc2022/day-18/day-18.rkt @@ -0,0 +1,57 @@ +#lang racket + +(require advent-of-code + relation + threading + graph) + +(define positions (~> (fetch-aoc-input (find-session) 2022 18 #:cache #true) (string-split "\n"))) + +(struct posn (x y z) #:transparent) + +(define cubes + (for/list ([cube (in-list positions)]) + (match (string-split cube ",") + [(list (app ->number x) (app ->number y) (app ->number z)) (posn x y z)]))) + +(define cubes-set (list->set cubes)) + +(define (neighbors p) + (match-define (posn x y z) p) + (for*/list ([dx '(-1 0 1)] + [dy '(-1 0 1)] + [dz '(-1 0 1)] + #:when (= 1 (+ (abs dx) (abs dy) (abs dz)))) + (posn (+ x dx) (+ y dy) (+ z dz)))) + +;; part 1 + +(for*/sum ([cube (in-set cubes-set)] + [neighbor (in-list (neighbors cube))] + #:unless (set-member? cubes-set neighbor)) + 1) + +;; part 2 +(define max-x (~> cubes (apply max _ #:key posn-x) posn-x (+ 2))) +(define max-y (~> cubes (apply max _ #:key posn-y) posn-y (+ 2))) +(define max-z (~> cubes (apply max _ #:key posn-z) posn-z (+ 2))) + +(define air-set + (for*/set ([x (in-inclusive-range -1 max-x)] + [y (in-inclusive-range -1 max-y)] + [z (in-inclusive-range -1 max-z)] + #:do [(define p (posn x y z))] + #:unless (set-member? cubes-set p)) + p)) + +(define air-graph + (for*/lists (ps #:result (undirected-graph ps)) + ([a (in-set air-set)] + [neighbor (in-list (neighbors a))] + #:when (set-member? air-set neighbor)) + (list a neighbor))) + +(for*/sum ([air (in-set (~> air-graph cc (sort > #:key length _) car))] + [neighbor (in-list (neighbors air))] + #:when (set-member? cubes-set neighbor)) + 1) diff --git a/racket/aoc2022/day-19/day-19.rkt b/racket/aoc2022/day-19/day-19.rkt new file mode 100644 index 0000000..1400bf2 --- /dev/null +++ b/racket/aoc2022/day-19/day-19.rkt @@ -0,0 +1,11 @@ +#lang racket + +(require advent-of-code + threading) + +(struct blueprint (id ore clay obsidian geode)) + +(define (parse-line str) + (match (~> str (string-replace #px"[^\\d\\s]" "") string-split) + [(list id ore clay obsidian-ore obsidian-clay geode-ore geode-obsidian) + (blueprint id ore clay (cons obsidian-ore obsidian-clay) (cons geode-ore geode-obsidian))])) diff --git a/racket/aoc2022/day-20/day-20.rkt b/racket/aoc2022/day-20/day-20.rkt new file mode 100644 index 0000000..6dd1070 --- /dev/null +++ b/racket/aoc2022/day-20/day-20.rkt @@ -0,0 +1,48 @@ +#lang racket +(require advent-of-code + threading) + +(define data (port->list read (open-aoc-input (find-session) 2022 20 #:cache #true))) + +(define gps-lst data) +(define gps-len (length gps-lst)) +(define gps-indexed (map cons (inclusive-range 1 gps-len) gps-lst)) + +(define (mix pt data) + (match-define (list left ... (== pt) right ...) data) + (define start (index-of data pt)) + (define move-by (modulo (cdr pt) (sub1 gps-len))) + (cond + [(= 0 move-by) data] + [(<= move-by (length right)) + (match-define-values (new-left new-right) + (split-at (append left right) (modulo (+ move-by start) (sub1 gps-len)))) + (append new-left (list pt) new-right)] + [else + (match-define-values (new-left new-right) + (split-at (append left right) (modulo (+ move-by start) (sub1 gps-len)))) + (append new-left (list pt) new-right)])) + +(define (mix-gps data original) + (for/fold ([pts data]) ([pt original]) + (mix pt pts))) + +(define (cycle-mixed-gps mixed) + (define lst (map cdr mixed)) + (in-sequences (drop lst (index-of lst 0)) (in-cycle lst))) + +(define (calculate-answer seq) + (for/sum ([id '(1000 2000 3000)]) (sequence-ref seq id))) + +;; part 1 +(~> gps-indexed (mix-gps _ gps-indexed) cycle-mixed-gps calculate-answer) + +;; part 2 +(define encrypted-gps-indexed + (for/list ([pt (in-list gps-indexed)] #:do [(match-define (cons i v) pt)]) + (cons i (* 811589153 v)))) + +(~>> encrypted-gps-indexed + ((λ (data) (foldr (λ (_ pts) (mix-gps pts data)) data (range 10)))) + cycle-mixed-gps + calculate-answer) diff --git a/racket/aoc2022/day-21/day-21.rkt b/racket/aoc2022/day-21/day-21.rkt new file mode 100644 index 0000000..fccd6ad --- /dev/null +++ b/racket/aoc2022/day-21/day-21.rkt @@ -0,0 +1,43 @@ +#lang racket + +(require advent-of-code + (only-in relation ->number ->symbol)) + +(struct monkey (name op) #:transparent) +(struct op (f first second) #:transparent) + +(define (parse-monkey str) + (match (string-split str " ") + [(list (app (curryr string-trim ":") name) name1 (app ->symbol f) name2) + (monkey name (op f name1 name2))] + [(list (app (curryr string-trim ":") name) (app ->number int)) + (monkey name (op 'constant int #f))])) + +(define raw-monkeys (port->lines (open-aoc-input (find-session) 2022 21 #:cache #true))) + +(define monkey-table + (for/hash ([m raw-monkeys] #:do [(match-define (monkey name op) (parse-monkey m))]) + (values name op))) + +;; part 1 +(define (evaluate-monkey m-name [guess #f]) + (match-define (op f name1 name2) + (if (and guess (equal? m-name "humn")) (op 'constant guess #f) (hash-ref monkey-table m-name))) + (match f + ['constant name1] + ['+ (+ (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] + ['- (- (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] + ['* (* (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))] + ['/ (/ (evaluate-monkey name1 guess) (evaluate-monkey name2 guess))])) + +(evaluate-monkey "root") + +;; part 2 +;; since humn only ever appears once, and it's never the divisor in a division operation, +;; the difference of the branches is linearly proportional to humn +;; therefore, if we find two points we can calculate the root directly +(match-define (op _ branch-1 branch-2) (hash-ref monkey-table "root")) +(define known-side (evaluate-monkey branch-2)) +(define humn-zero (- known-side (evaluate-monkey branch-1 0))) +(define humn-one (- known-side (evaluate-monkey branch-1 1))) +(- (/ humn-zero (- humn-one humn-zero))) diff --git a/racket/aoc2022/day-22/day-22.rkt b/racket/aoc2022/day-22/day-22.rkt new file mode 100644 index 0000000..bcce5f8 --- /dev/null +++ b/racket/aoc2022/day-22/day-22.rkt @@ -0,0 +1,35 @@ +#lang racket + +(require advent-of-code + threading) + +(struct posn (x y) #:transparent) + +(match-define (list raw-map raw-instructions) + (string-split (fetch-aoc-input (find-session) 2022 22 #:cache #true) "\n\n")) + +(define board-map + (for*/hash ([(row y) (in-indexed (string-split raw-map "\n"))] + [(col x) (in-indexed row)] + #:unless (equal? col #\space)) + (define tile + (match col + [#\. 'open] + [#\# 'wall])) + (values (posn x y) tile))) + +(define instructions + (~>> raw-instructions + (regexp-match* #px"(\\d+)|R|L") + (map (match-lambda + [(? string->number n) (string->number n)] + ["R" 'clockwise] + ["L" 'counterclockwise])))) + +(define start-tile + (~>> board-map + hash-keys + (filter (match-lambda + [(posn _ 0) #true] + [_ #false])) + (argmin posn-x)))
\ No newline at end of file diff --git a/racket/aoc2022/day-23/day-23.rkt b/racket/aoc2022/day-23/day-23.rkt new file mode 100644 index 0000000..6069859 --- /dev/null +++ b/racket/aoc2022/day-23/day-23.rkt @@ -0,0 +1,76 @@ +#lang racket + +(require advent-of-code + fancy-app + threading) + +(struct posn (x y) #:transparent) + +(define initial-map + (for*/hash ([(row y) (in-indexed (in-lines (open-aoc-input (find-session) 2022 23 #:cache #true)))] + [(col x) (in-indexed row)] + #:when (equal? col #\#)) + (values (posn x y) #t))) + +(define/match (neighbors-in direction p) + [('north (posn x (app sub1 y*))) (list (posn (sub1 x) y*) (posn x y*) (posn (add1 x) y*))] + [('south (posn x (app add1 y*))) (list (posn (sub1 x) y*) (posn x y*) (posn (add1 x) y*))] + [('east (posn (app add1 x*) y)) (list (posn x* (add1 y)) (posn x* y) (posn x* (sub1 y)))] + [('west (posn (app sub1 x*) y)) (list (posn x* (add1 y)) (posn x* y) (posn x* (sub1 y)))]) + +(define/match (move-to direction p) + [('stay p) p] + [('north (posn x y)) (posn x (sub1 y))] + [('south (posn x y)) (posn x (add1 y))] + [('east (posn x y)) (posn (add1 x) y)] + [('west (posn x y)) (posn (sub1 x) y)]) + +(define (propose-movements elves dirs) + (for/hash ([(elf _) (in-hash elves)]) + (define dir-candidates + (for/list ([dir dirs] + #:do [(define neighbors (neighbors-in dir elf))] + #:unless (ormap (curry hash-has-key? elves) neighbors)) + dir)) + (define chosen-dir + (match dir-candidates + ['() 'stay] + [(== dirs) 'stay] + [(cons dir _) dir])) + (values elf chosen-dir))) + +(define (try-proposed-movements elves) + (define moved-elves (make-hash)) + (for ([(elf dir) (in-hash elves)]) + (hash-update! moved-elves (move-to dir elf) (cons elf _) '())) + (define reconciled-elves (make-hash)) + (for ([(posn elves) (in-hash moved-elves)]) + (match elves + ; if there's only one elf at a coordinate, leave it there + [(list _) (hash-set! reconciled-elves posn #t)] + ; if there's many elves at one coordinate, back them up to their previous spot + [many-elves + (for ([elf (in-list many-elves)]) + (hash-set! reconciled-elves elf #t))])) + reconciled-elves) + +;; part 1 +(define (count-empty-spots elves) + (define elf-posns (hash-keys elves)) + (match-define (list x-min _ ... x-max) (sort (map posn-x elf-posns) <)) + (match-define (list y-min _ ... y-max) (sort (map posn-y elf-posns) <)) + (for*/sum ([y (inclusive-range y-min y-max)] [x (inclusive-range x-min x-max)]) + (if (hash-has-key? elves (posn x y)) 0 1))) + +(for/fold ([elves initial-map] [dirs '(north south west east)] #:result (count-empty-spots elves)) + ([_rnd (in-range 10)]) + (values (~> elves (propose-movements dirs) try-proposed-movements) + (append (cdr dirs) (list (car dirs))))) + +;; part 2 +(for/fold ([elves initial-map] [dirs '(north south west east)] [rnd 1] #:result rnd) + ([_rnd (in-naturals)]) + (define elves-proposed (propose-movements elves dirs)) + ; elves have stopped moving if they all conclude they want to stay put + #:break (~> elves-proposed hash-values remove-duplicates (equal? '(stay))) + (values (try-proposed-movements elves-proposed) (append (cdr dirs) (list (car dirs))) (add1 rnd))) diff --git a/racket/aoc2022/day-25/day-25.rkt b/racket/aoc2022/day-25/day-25.rkt new file mode 100644 index 0000000..078cef4 --- /dev/null +++ b/racket/aoc2022/day-25/day-25.rkt @@ -0,0 +1,24 @@ +#lang racket +(require advent-of-code + threading) + +(define fuel-requirements (port->lines (open-aoc-input (find-session) 2022 25 #:cache #true))) + +(define (snafu->decimal snafu) + (for/sum ([digit (in-list (~> snafu string->list reverse))] [place (in-naturals)]) + (define value + (match digit + [#\= -2] + [#\- -1] + [c (~> c string string->number)])) + (* value (expt 5 place)))) + +(define (decimal->snafu n [acc '()]) + (match n + [0 (list->string acc)] + [n (decimal->snafu (quotient (+ n 2) 5) (cons (string-ref "012=-" (modulo n 5)) acc))])) + +;; part 1 +(~> (for/sum ([fuel (in-list fuel-requirements)]) (snafu->decimal fuel)) decimal->snafu) + +;; no part 2 メリークリスマス
\ No newline at end of file |