{
  "$type": "site.standard.document",
  "canonicalUrl": "https://unnecessary.tech/posts/aoc2024-final",
  "path": "/posts/aoc2024-final",
  "publishedAt": "2025-01-02T21:57:17.000Z",
  "site": "at://did:plc:jx54v4rmscfwzit7fmgz24ba/site.standard.publication/3mnrsqmzz3w2e",
  "tags": [
    "gleam",
    "programming"
  ],
  "textContent": "As usual the holidays really started to take off and I didn't take time to\nwork on updates. The upshot is I did finish Advent of Code 2024, but I didn't\nfinish Day 24 until the new year. However, before we get to that, let's talk\nabout some of the more interesting problems.\n\nDay 14: Picture of a Christmas Tree?\n\nPart 1 of day 14 was pretty straightforward. Essentially we follow the location\nof a number of robots with initial positions and velocities over a number of time\nsteps, however part 2 threw in a significant wrinkle. Find the timestep when\nthe robots form a picture of a Chritmas tree. Since we have no sample of what\nthis should look like, it is tricky. I figured the image might have fairly sharp\nvertical and horizontal boundaries, so I decided to look for timesteps where\nthe robots formed vertical and horizontal structures what were not randomly\ndistributed. To do this I used an edge detector which scans 4 rows or columns\nat a time and then compares the number of robots in the two rows or columns on\none side with the two columns on the other. Generally, if the robots are randomly\ndistributed this should be a small number, however if there are vertical or\nhorizontal structures there would be a few regions with very high numbers. \n\nAfter some tuning I was able to find the instant where the robots formed a tree.\nMy solution is available on github.\n\nDay 17: Analysis of Code\n\nThis problem involved creating an interpreter to run programs for a three-bit\ncomputer with 8 instructions and 3 registers.\nThe first part involved just running the program provided, but the second part\nrequired finding a register value that would result in the program outputting\na copy of itself. There are too many possible register values to test each one,\nso some code analysis was required. \n\nI noticed that my code took the value from the lowest three bits of the A\nregister, manipulated it, mixed it with some other bits from the A register, \nshifted A right 3 bits, and output the result. The manipulations were hard to\nfollow, but it would always depend on the lowest three bits of A and some other\nbits, if there were any, in register A. \n\nI realized that the first byte of the program would depend only on the first\nbyte of A. Then the second byte of the program would depend on the first two\nbytes of A, and so on. I could solve for A one byte at a time, moving to\nlower order bits as I matched more and more of the program. Since each byte in\nthis computer is three bits, there are only 8 possibilities for each byte, and\nI just check each one to see which will provide the next match. The routines\nthat do this matching are on github.\n\nDay 19: Unnecessary Search Trie\n\nThis problem involved searching for the number of ways a sequence of colors\ncould be made from a set of towels. The towels had various length subsequences\non them. This reminded me of a search trie, so I implemented one to use as\nthe basis of the search. A search trie combines sequences into a single\nstucture. Searching was done using the\nfollowing steps:\n\n1. Find any subsequences that match the beginning of the sequence returning a\n  list of tuples of the matching subsequence and the remaining sequence to be\n  matched.\n2. Recursively count up the number of subsequences that match the start of that\n  new list of remaining sequences until the remaining sequence length goes to\n  zero.\n3. Add up all the recursive subcounts and total them up.\n4. Accelerate the process by memoizing the count for sequences, as sequences will\n  often repeat.\n\nI think my code\nis a little hard to follow here. I have the function find_possible_heads which\nmatches any subsequences in the Trie to the head of the sequence. The\nfunction recurse_counter which combines the count of a list of sequences and\ncalls the function cached_count on each of those sequences in turn to actually\ndo the counting for individual sequences. All these functions end up recursively\ncalling one another.\n\nDay 21: I Need to Think About This\n\nThis problem was very tricky. The idea is that you must find the motions a\nrobot finger has to make above a keypad in order to enter a code. Those motions\nare controlled by another robot with a directional keypad, which is controlled\nby another robot with a directional keypad, and so on. At each stage the number\nof button pushes increases exponentially, and there are multiple paths to get\nfrom one position to another. For example to move from the A key to the left key\ncan be done by going down, then left two times, or by going left, down, and left.\nThere are two rules to minimize the amount of motion required to order a robot\nto click a button. They are:\n\n1. If there are multiple steps in one direction, do them as a group. This means\n  don't split up two left moves with a down move.\n2. Start with motions that are furthest from the A key.\n  - Left takes three moves to get to from the A key.\n  - Down takes two moves to get to from the A key.\n  - Right and Up take one move.\n\nThis had me believing that Right and Up were equivalent, however it turns out\nthat Right should be done before Up! The reason for this is that ordering a\nrobot to take one step to the right key requires using the Left key, which is\nfarther from the A than the down key. So the optimal ordering to move across\nthe keypad is:\n\n- Up then Right\n- Left then Up\n- Down then Right\n- Left then Down\n\nThis is complicated by the fact that there is one square with no button and the\nrobot is not allowed to move its finger into this square. If this is the case\nthen you cannot choose the optimal ordering for that move. \n\nMy code\nis available on github for review. \n\nDay 23: Growing from a Seed\n\nThis problem had a list of connections between nodes, and for the first part\nyou had to find sets of three nodes all connected to one another. In order to\ndo this, I just found cycles of length three that passed from a starting node\nback to the starting node hitting two other nodes on the way. \n\nThe second part was to find the largest set of nodes all connected to one\nanother. It turns out that this could be done starting with the seeds of\ngroups of three. For each node I found the set of all connected nodes. I then\nfound the intersection of these sets for all the nodes in my group and removed\nthe nodes currently within the group from the set. That left nodes which were\nconnected to all the nodes currently in the group. I picked one of these nodes\nto add to the group and then did the process again until the intersection of\nconnected nodes for all the nodes in the group only contained those nodes\nalready within the group.\n\nThe next step is to purge from the starting seeds any group of three nodes that\nare a subset of the group. These seeds would grow to find the same group already\nfound. I kept track of the largest group I found as I ran through all the seed\ngroups and when I was done with the seed groups I had the largest set of nodes.\n\nMy code\nshows how I made extensive use of the set library for this problem, but using\nthat library made the problem very easy.\n\nDay 24: Days Without Progress\n\nThe first part of this problem is to simulate the outputs of a collection of\nlogic gates, but the second part reveals this is a miswired circuit which is\nsupposed to add two 44 bit integers to get a 45 bit integer. Some examination\nreveals that the circuit is made up of a half adder#Half_adder)\nand 43 full adders#Full_adder), however\nfour outputs are miswired and swapped with one another.\n\nThe half adder should contain two gates:\n- \\\\(x_{0}\\ \\mathrm{XOR}\\ y_{0} \\rightarrow z_{0}\\\\)\n- \\\\(x_{0}\\ \\mathrm{AND}\\ y_{0} \\rightarrow c_{0}\\\\) (carry bit)\n\nThe full adders should be a set of 5 logic gates:\n- \\\\(x_{N}\\ \\mathrm{XOR}\\ y_{N} \\rightarrow a_{N}\\\\)\n- \\\\(x_{N}\\ \\mathrm{AND}\\ y_{N} \\rightarrow b_{N}\\\\)\n- \\\\(a_{N}\\ \\mathrm{XOR}\\ c_{N-1} \\rightarrow z_{N}\\\\)\n- \\\\(a_{N}\\ \\mathrm{AND}\\ c_{N-1} \\rightarrow d_{N}\\\\)\n- \\\\(b_{N}\\ \\mathrm{OR}\\ d_{N} \\rightarrow c_{N}\\\\) (carry bit)\n\nwhich depend on the carry bit of the previous group (\\\\(c_{N-1}\\\\)). The last\ncarry bit will go to the output \\\\(z_{45}\\\\). \n\nI spent a few days thinking about how to do this, but in the end I decided to\njust use some editor macros to sort and rearrange the gates into groups and\nlook for incorrect outputs. One thing I noticed was that all the swapped output\ngroups are from the same full adder. Therefore it is sufficient to look for any\noutput which is not going into the correct gate within that group. \n\nI actually used this reddit post\nand a tremendous example from the Gleam discord\nto create my own solution\nwhich highlights how flexible pattern matching is with Gleam, allowing me to\neven match for partial strings within custom types.\n\nOn Gleam\nI really like Gleam, and it is a good language for tackling Advent of Code. I\nstill have trouble getting away from procedural thinking, but it is pretty\namazing what you can do with this functional language. I thought some of the\nsolutions looked very good and were easy to follow, but I also had a number of\nsolutions whose implementation looks fairly tortured and hard to follow. There\nare some solutions I wrote which involve recursion over two lists which gave\nme a lot of trouble, and I am sure there are probably better ways to express\nthose problems. \n\nAs I became more familiar with the language, I think I did get better at writing\nit. I think I would still reach for Go if I were writing a\nCLI tool as it compiles to a single binary and I like the templating system it\noffers, however I am interested in seeing how Gleam evolves.",
  "title": "Advent of Code: Summary"
}