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
1 2 3 4 5 6 7 8 9 10 |
bn RSHIFT 2 -> bo lf RSHIFT 1 -> ly fo RSHIFT 3 -> fq cj OR cp -> cq fo OR fz -> ga t OR s -> u lx -> a NOT ax -> ay he RSHIFT 2 -> hf ... |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
require "parse.ang" import # create a non-zero integer parser "[0-9]+" regexparser (toint) moditem `number label !NumberParser # create a parser for parsing "->" "->" strparser `arrow label !ArrowParser # create a parser for parsing lowercase IDs "[a-z]+" regexparser `ident label !IdentParser # an rvalue can be either a number of a character (rvalues appear on # the left hand side in this weird syntax, but I'm using the C++ # nomenclature. [?IdentParser, ?NumberParser] choice `rvalue label !RValueParser |
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:
1 |
"[0-9]+" regexparser |
creates a parser which consumes the regular expression “[0-9]+”. The next bit,
1 |
(toint) moditem |
takes that parser, and modifies it to change its item into an integer.
The last bit
1 |
`number label !NumberParser |
modifies it further to label its results items with the symbol `number
, before saving it to the variable NumberParser
.
We also have choice parsers:
1 |
[?IdentParser, ?NumberParser] choice `rvalue label !RValueParser |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
[ [?RValueParser,?ArrowParser,?IdentParser] seq (|t:| ?t itemdehash dehashlist !t [`eq, ?t fst] ?t third ?Wires set) action, ["NOT" strparser,?RValueParser,?ArrowParser,?IdentParser] seq (|t:| ?t itemdehash dehashlist !t [`not, ?t snd] ?t fourth ?Wires set) action, [?RValueParser, ["LSHIFT","RSHIFT","AND","OR"] (strparser) map choice, ?RValueParser,?ArrowParser,?IdentParser] seq (|t:| ?t itemdehash dehashlist !t [`binop, ?t snd, ?t fst, ?t third] 4 ?t get ?Wires set ) action, ("Unknown command".) anything ] choice !CmdParser |
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:
1 2 3 |
a -> [`not, "a"] b -> [`binop, `and, "a", "c"] c -> [`eq, "d"] |
Let’s take a closer look at the binary operation parser:
1 2 3 4 5 |
[?RValueParser, ["LSHIFT","RSHIFT","AND","OR"] (strparser) map choice, ?RValueParser,?ArrowParser,?IdentParser] seq (|t:| ?t itemdehash dehashlist !t [`binop, ?t snd, ?t fst, ?t third] 4 ?t get ?Wires set ) action, |
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
1 |
[`binop, operation name, first value, second value] |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
[%]!Vars [%]!Wires # set a value in the variable store, limiting to 16bit unsigned :setval|val,key:|?val 65536+ 65535 band ?key ?Vars set; # get a value from the variable store or none :getval |key:val| ?key ?Vars get; # get known value or integer :getknown |v:| ?v type `integer = if ?v else ?v ?Vars get then ; # return true if item is a known variable or integer :known |v:| ?v type `integer = ?v ?Vars get isnone not or ; # return true if all items are known (are in Vars, or are ints) :allknown |lst:| 1 ?lst (known and) reduce; # go through the system, attempting to resolve simple integers # and operations whose operands are both known :resolveeq |lst:| ?lst snd known if ?lst snd getknown else none then ; :resolvenot |lst:| ?lst snd known if ?lst snd getknown bnot else none then ; [% "LSHIFT" (shiftleft), "RSHIFT" (shiftright), "AND" (band), "OR" (bor)] !Binops :resolvebinop |lst:op,args| ?lst snd !op 2 -1 ?lst slice !args ?args allknown if ?args "," intercalate. ?args fst getknown ?args snd getknown ?op ?Binops get @ else none then ; :resolve |:t,done| { 0!done ?Wires each { i ?Vars get isnone if ival fst << [% `eq (ival resolveeq), `not (ival resolvenot), `binop (ival resolvebinop) ]>> get@ !t ?t isnone not if ?t i setval [i,i getval] "Setting %s to %d" format. then 1!done then } ?done not ifleave } ; |
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:
1 2 3 4 5 6 7 8 |
:parse |s:t| ?s. ?s <<"\\s+" regex$compile>> regex$split ?CmdParser @ drop ; "day7in2" "r" io$open each {i parse} resolve "Result : a="p "a" ?Vars get. |