Tag adventofcode

Advent of Code, Day 7

Did this yesterday but didn’t write it up. This was a complete pig, because the test data set had all the dependencies in order: when read line by line, there were no data which relied on the output of data which hadn’t been read yet. Naturally I assumed the real data would be like that, but no. Which involved rewriting the whole damn thing.

The data is in the form

and the problem is to find the ultimate value of a variable, in this case a.

Naturally, we need to parse the input. I’ve written parsers for Angort before, but I thought I’d have a go at writing a combinatorial parser framework (for the lulz, as the young people said a few years ago). I’ll gloss over the framework for now, but the code to parse the basic elements looked like this:

Each parser is a function, and there are functions to wrap parsers inside other parsers and combine them in various ways to produce new parsers (hence “combinatorial”). For example:

creates a parser which consumes the regular expression “[0-9]+”. The next bit,

takes that parser, and modifies it to change its item into an integer.
The last bit

modifies it further to label its results items with the symbol `number, before saving it to the variable NumberParser.
We also have choice parsers:

generates a parser which accepts either identifiers or numbers, and labels the result as an “rvalue” – C jargon for a value which cannot be assigned to (essentially).

Now we create the command parser. This takes the elements above, using seq to make parsers which accept sequences of those elements, and uses choice to make a parser which can accept one of those. Each sequence corresponds to a command. We’re parsing line-by-line rather than the whole file, to make life easier, and so we want to do something when a command is accepted. To this end, each command sequence parser is modified with action, which takes a function to be performed on acceptance:

Finally, if no other thing matches in the choice, anything will always match, consume all remaining tokens and perform an action.

So what are the actions? These set values in a hash called Wires. Each entry is keyed by the name of the variable it assigns, and the value is a list consisting of an operation and the names of the variables it is to be performed on. Possible values are:

Let’s take a closer look at the binary operation parser:

The parser accepts a sequence consisting of an rvalue, a choice of some strings (the binary operation names), another rvalue, an arrow, and a variable name. Its action is to set the variable name to

in the hash. First, the action takes the incoming parsed item and runs itemdehash, which turns it into a considerably simpler kind of hash/list combination. It then runs dehashlist to simplify the result still further, so all we get is a list of the values read in. This process is necessary because everything the parser generates is in the form of parser items, which are hashes containing the item label and its content, and which are messy to work with directly. Now this is done, the action can simply assemble a list out of the new data, and then set that value into the Wires hash with the key also obtained from the list.

Now we need to use this hash to solve the problem. I elected to use the dumb method. A function called resolve repeatedly scans the hash, running an appropriate function for every variable it finds whose value is not known. Known values are stored in the Vars hash. Each subfunction looks to see if the variables it requires are known, and if so calculates and stores the result. This resolve function repeats until no more passes are required – all variables had known values.

Here is the relevant code:

Finally, we need to read the file in line-by-line, tokenising each line (splitting on white space) and parsing it. We then need to resolve the variables, and print the one we want:

Advent of Code, Day 6

Considerably more hairy. I could have used the same trick as Day 3, faking up a 2D array with a hash, but it would have been ludicrously slow. Instead, I added a C++ class for a 2D int array to the library I started in Day 4.

First, we need to write the class. This needs to be tracked for garbage collection, so we make it a subclass of GarbageCollected. This code goes after the %shared line, so we’re in the library’s namespace:

Very simple, mapping a 2D array onto a 1D one. I’m not even doing any bounds checking (yes, this is bad and wrong of me).

Now we need to define a type object, which will be a singleton to handle the interface between Angort and C++ for this type. This is a simple one, with no iterators because it’s not a container (well, it is, and I could have added an iterator, but I didn’t):

The constructor adds the type to the type system. The get() method takes an Angort value, typechecks it, and returns the underlying pointer to the Int2DArray if it’s correct. Otherwise it throws an Angort runtime error. The set() method is used to create a new array and set an Angort value to it. It clears any previous value (decrementing any refcount and perhaps deallocating data), sets the value’s type, creates and sets the array, and finally increments the reference count on the value.

Finally, we create the type object singleton on the heap, and use a directive to tell the preprocessor about the new type so we can use it in word definitions:

That second line says that the typecode int2d is associated with the type object tInt2D and wraps objects of the type IntArray2D.
Having done this, the preprocessor can automatically unpack parameters of our new type in words we define. The first word we can write is that to create a new array:

This takes to integer arguments (unwrapped to p0 and p1), and uses them to create a new array using our type object. This array is set into a new value pushed onto the top of the stack.

We can now write words to access the array:

In both these words, the definition uses the marker A – this means the first typecode after the bar, which is the int2d we set up in the %type directive. Thus, in int2dget, the arguments are two integers and a 2D int array. Parameters p0 and p1 are integers, and p2 will be an Int2DArray.

That’s all the new C++ code, and when this library is loaded in we’ll have our new garbage-collected 2D integer array.

The Angort code for part 1 is fairly simple. We start with loading the libraries, and creating our new array (storing it in the global B):

Now some words to access our global array, making life easier:

The first word, s, sets a value in the global, taking coordinates and a value to set. The next word looks odd because we’re not explicitly using a parameter list – the x,y coordinates are assumed to be on the stack so all the word needs to do is push the array and call the C++ getter word.

Now to write a more involved function (the terms ‘function’ and ‘word’ are interchangeable in Angort – ‘word’ comes from Forth). This function op will take a range of coordinates and run another function on all of them:

The called function f is assumed to take x,y on the stack.

Now we can write a function to take a line of text and process it:

Ugly. We split the line by spaces and/or colons using a pre-compiled regex, and then look at the first one or two elements to determine the command. Each case sets the function to one of three anonymous functions, and sets the split point from which to to get the numeric arguments (different for “toggle” and “turn on/off”). After the cases, we slice the string using the split point we stacked, convert and push the numeric arguments, and call op with the function we set. There are far better ways to do it.

We now run this function on all lines in the file, and count the number of non-zero elements in the array afterwards:

Part two involves modifying the anonymous functions in the cases, and adding a new function to clip to zero (just for ease of reading):

Runtimes aren’t great, 1m8s for part 1 and 1m47s for part 2. Angort is a silly language to do this sort of thing in. I could have made it a lot faster by writing the rectangle set/get/toggle operations in C++, of course.

Advent of Code, Day 5

This was pretty quick – Angort has POSIX regular expressions, so it was just a matter of working out the right ones (and counting the resulting matches). Here’s the code for both parts:

The only vaguely interesting bit is in part 1, where I map over a list of strings at compile time (that’s what << >> does) to produce a list of regexes to match, which I then iterate over.

Advent of Code, Day 4

This one’s a bit hairier in Angort, because I don’t have an MD5 facility. I could either reimplement MD5 in Angort, or use someone else’s C/C++ code and make a library. I decided to do the latter (because I’m not completely insane).

Writing a library in Angort is easy. First, I downloaded a C implementation of MD5 from here. I modified the include file so that I’d be able to use the code from C++:

Note the new extern "C" {} blocks, guarded by #ifdef. When included from C++, this will tell the compiler these are C functions.

Now the library code. Angort has a handy Perl script called makewords.pl to preprocess special directives in C++, making libraries easy. We write a file called advent.cpp using these directives. Here’s the first part:

Include a few files, specify we’re going to use the angort namespace, and then two directives: one giving the Angort namespace the library functions will be loaded into, and another saying we’re making a shared library plugin. Then the actual code for a new Angort function, advent$md5:

The first line specifies a word (Angort function) with arguments. The word is md5, and it has a single string argument (the “s”). Anything following that is a text description, and these typically start with a “stack picture” in brackets. Here, the stack picture specifies that before the word runs there should be a string on the stack, and afterwards there will also be a string on the stack (the result).

The code generated by the directive will pop the arguments into parameter variables p0,p1… and so on. In this case, we have a single string parameter, p0, declared as a const char *. We get its length and declare an output buffer out. Next comes the code which generates the hash into the output buffer. Then, we build a hex string using the ugly and evil sprintf(buf+strlen(buf),...) thing, which you should never do, but it’s OK here because looking at the code I can guarantee it’s always going to be exactly 32 hex digits. Finally, we push that string onto the Angort stack, which will return the value from our new word.

One last thing is an initialisation function, which in this case doesn’t do much – just prints a string giving the build date and time:

This isn’t required, but I always add one of these just to make sure I’m running a recent version of a library.

We need to compile this code. I’ve got a simple build script which looks like this:

It generates advent.plugin.cpp using the makewords.pl script, and then compiles both this and the MD5 file, specifying -fPIC. This tells the compiler to generate position independent code, which is required for shared libraries. Finally it links the files into a shared library called advent.angso, where .angso is the standard extension for an Angort plugin.

We can test the plugin with a simple one-liner on the Angort command line (assuming we build the library in a lib subdirectory:

Looking at the output from a web-based MD5 generator, this is fine.

Finally we can write our program. This is a simple one liner, which keeps a count on top of the stack. The value is concatenated to our key string (which produces a string) and MD5’d, and the first five characters of the result are compared with “00000”. The infinite loop exits when the the result is true, and then we print the count, on top of the stack:

We have to remember to include the library, either by invoking Angort with angort -llib/advent or putting this line in a script with "lib/advent" library drop at the top.
The only difficult thing about this is the use of over. This is an occasionally useful stack manipulation word, stolen from Forth, which has the stack picture “(a b — a b a)” : that is, it takes the value underneath the stack top and pushes a copy of it onto the stack.

Part two is just as easy, just changing the program to

On my pretty slow laptop, the 5-digit run takes 2.6 seconds, and the 6-digit run takes 76 seconds. MD5 isn’t quick.

Advent of Code, Day 3

Slightly tricker, but still easy. Here, I keep a hash of visited houses – for my own amusement, the “mark” function increments the count so I can see how often a house was visited. I convert the input into a list of chars using identical code to before, and map over this list with a hash get to produce a list of [deltax,deltay] tuples. I then just iterate over this, updating x and y and marking the hash accordingly (the hash keys are strings of the form “x/y”; ugly, but Angort can’t key a hash on a list).

The second part is a little more complex, because it involves using alternate entries in the list to update different pairs of coordinates, marking both. I could have done this with a boolean toggle, but instead used an explicit iterator object.

Advent of code

I don’t know whether I’m going to have time to do all these, but I thought I’d try at least the first few puzzles of Advent of Code in my pet language, Angort.

Here’s day 1, which involves counting parentheses. I do the first part by making a list of the characters in the input, mapping that list to get -1 or 1 from a hash of characters to integers, then summing the list. The second part is done by going through that same -1,1 list and keeping a running count.

Day 2 is a bit more involved. First I have a couple of functions – one finds the minimum of a list of numbers, the other finds the minimum of a list of lists [a,b] such that the result has the minimum a*b (i.e. if we pass in the sides of faces of a cube, we get the smallest face out). I then make a list of inputs, each of which is a list of 3 integer elements (length,width,height). Then I go through the list of lists, accumulating the first result; and then again accumulating the second result.

Copyright © Found
Jim Finnis' personal blog

Built on Notes Blog Core
Powered by WordPress