Category programming

Advent of Code, Day 18

This one is just Conway’s Game of Life, so it’s pretty straightforward. Angort’s not the fastest language to do this in, and I’ve written it pretty naively. It runs in around 20 seconds. The grid is a list of lists of 0 or 1, and is actually two grids – like a double-buffered display. Part 2, in which you have to count the cells after a number of generations with the corner lights being hardwired on, was done by turning them on again before and after each generation.

Advent of Code, Day 17

Another fairly easy one – essentially a knapsack problem, with few enough items to solve with a brute force walk through the power set.. To generate that power set I used a binary mask to filter the list repeatedly.

Advent of Code, Day 16

Well that was easy. I just progressively filtered the list with each datum from the target (the analyser’s output). Again, Angort is good for this sort of thing, as is any language with decent functional and collection capabilities:

Advent of Code, Day 15

A bit hairier, this one. There are smart ways of generating the possible combinations (finding the partitions of 100 and then permuting them) but I went for brute force with some ugly code.

Advent of Code, Day 14

Another straightforward one. Here, I’ve used the “closure object trick”. Reindeer are stored as a hash of reindeer hashes, keyed by name. Each of these hashes is created by the addreindeer function, which creates a closure. The hash contains code elements, which access data in this closure. This data is effectively private to the hash. Other elements of the hash contain data, which the code in the hash can access via the this variable, also stored in the closure, which references the hash itself. Thus, we have private members, methods, and we could have inheritance if we ever wrote code to take the hash and change some of its members. There’s also some moderately clever list processing and functional stuff.

Angort is good for this sort of thing.

Advent of Code, Day 13

Trivial, this one, using the permutation algorithm from Knuth (see Day 9) to do a brute force search.

Advent of Code, Days 11 and 12

Getting down to marking, so these may get sparse.

Day 11

Easy. Convert the passwords to integer lists and write code to increment them, then write some more code to test each password for validity (sometimes converting back to strings and doing a regex, but leaving that as the last case for speed). The only irritating part was having to write a function to test the equality of three values:

Day 12

The first part of this was easy, once I realised that strings never contained numbers. I could just parse all the numbers and add them up:

For second part there was no way around actually parsing the JSON, so I wrote a JSON parser. This is really pushing the limit of what it’s sensible to do in a language like Angort, which, while a full functional language, has no clever optimisation tricks to make it faster. I had to considerably increase the size of the both the return stack and the variable stack, and it runs like a dog. But it does work:

This certainly pushed the language to its limits, and helped me find an awful lot of bugs!

Advent of Code, Day 10

This problem involves finding the length of an element of Conway’s “Look-and-Say” sequence, after a number of iterations on a seed.

The basic solution is easy in Angort:

The function getrun takes a string, and returns a tuple of the digit found, how many repetitions, and the remaining string. The function process repeatedly applies this function. We then just run this function N times, printing the result each time.

This is extremely slow, because Angort’s strings are immutable – there’s an awful amount of copying going on. Angort is not the best language for this kind of problem! However, we can simply write a C++ function to replace process using a large, static buffer. We add this to the library:

and replace our solution with the one-liner

Even the second part, 50 iterations, runs in less than half a second in C++! Immutable strings are a pretty poor solution to many problems, even through they’re nice and safe.

Advent of Code, Day 9

This is a Travelling Salesman Problem with 8 cities, a small enough number to brute-force. The input is in the form

No prizes for the sources of the city names. Again, the parser framework gets used, and we build up both a list of cities and a hash of city distances. We then use an algorithm from Knuth to permute the list (lexicographically ordered, but it doesn’t really matter) and just go through it until we find the shortest path. Part 2 asks for the longest path, which is a simple enough matter. Here’s the code:

Advent of Code, Day 8

This tale of dancing regexps was fairly straightforward, once I’d figured out what they meant in the second part (yes, it’s obvious now). Anyway, we just iterate through a set of regexps each time making sure the ordering is sensible, and count the difference (highlighting off because Crayon is getting confused):

Copyright © Found
Jim Finnis' personal blog

Built on Notes Blog Core
Powered by WordPress