Some More Nim

2024-06-06

I was kind of enjoying explaining some nim in my previous post, so I will do another one, this time of a project that is a bit more complex.

This time working on day 7 of 2015 in the adventofcode

I like starting out with defining my types, that way I know what I have to work with, and it’s good to have it all gathered in one place.

 1type
 2  Op = enum
 3    Assign
 4    And
 5    Or
 6    LShift
 7    RShift
 8    Not
 9  
10  Wire = string
11  
12  Pkind = enum
13    PWire
14    Puint16
15    PEmpty
16
17  Parameter = object
18    case kind: Pkind
19    of PWire: wire: string
20    of Puint16: val: uint16
21    of PEmpty: discard
22
23  Instruction = tuple[a: Parameter, b: Parameter, op: Op, dest: Wire]

I think the Op enum is pretty self explaining, we’re basically setting up the different operation types that we are having to deal with, it’s nice to have since it will help us later, nim case statements checks that we deal with all the versions we said we will, so it makes it harder to forget to deal with something that we really should.

The Wire type is basically just an alias of a string, so not strictly needed, it’s just nice to have, it makes the code read a bit better. I could have made it distinct, so that the code only accepts strings marked as Wire explicitly like Wire("a") for example, but for this little sript it’s not really needed.

The Pkind and Parameter types are a bit more interesting, The Parameter type here is a “variant object” bascially nim’s tagged union type, Pkind is the tag that we use here, it basically tells us if the Parameter is a Wire, a uint16 or if it’s not there, this makes it so that we can store different types in a sequence or Instruction, as long as we are okay with dealing with the syntactic noise of unpacking it all.

1func split2(str: string, sep: string): (string, string) =
2  let parts = str.split(sep, 1)
3  do_assert(parts.len == 2, &"Split2 {str} on {sep} did not return 2 parts")
4  (parts[0], parts[1])
5
6func split3(str: string, sep: string): (string, string, string) =
7  let parts = str.split(sep, 2)
8  do_assert(parts.len == 3, &"Split3 {str} on {sep} did not return 3 parts")
9  (parts[0], parts[1], parts[2])

These two functions are basically just utility functions to use dealing with string splitting a bit more comfortable for our parsing, they do the split and return a tuple of 2/3 strings, and also asserts that they are used correctly, so that we don’t get bitten by making assumptions about them.

I do kind of wish that nim had a split once function, but it’s decent enough to deal with it like this, it’s not that much hassle to write them, but I do think that it would be nice to write up a little utility library with snippets like these that I like having around.

1func to_param(str: string): Parameter =
2  if str[0].is_digit:
3    return Parameter(kind: Puint16, val: str.parse_uint.uint16)
4  else:
5    return Parameter(kind: PWire, wire: str)

to_param is another function that I use to save myself some repetition, here we take in a string, check if it is a string, or a string representation of a number, and return the Parameter with the correct tag.

 1proc parse(lines: seq[string]): seq[Instruction] =
 2  for line in lines:
 3    let (main, dest) = line.split2 " -> "
 4    if "AND" in main:
 5      let op = And
 6      let (a, _, b) = main.split3 " "
 7      result.add (a.to_param, b.to_param, op, dest)
 8    elif "OR" in main:
 9      let op = Or
10      let (a, _, b) = main.split3 " "
11      result.add (a.to_param, b.to_param, op, dest)
12    elif "LSHIFT" in main:
13      let op = LShift
14      let (a, _, b) = main.split3 " "
15      result.add (a.to_param, b.to_param, op, dest)
16    elif "RSHIFT" in main:
17      let op = RShift
18      let (a, _, b) = main.split3 " "
19      result.add (a.to_param, b.to_param, op, dest)
20    elif "NOT" in main:
21      let op = Not
22      let (_, a) = main.split2 " "
23      let b = Parameter(kind: PEmpty)
24      result.add (a.to_param, b, op, dest)
25    else:
26      let op = Assign
27      let b = Parameter(kind: PEmpty)
28      result.add (main.to_param, b, op, dest)

With that all set up we can go on with the real work of parsing. Since the format is very simple we don’t really have to do anything fancy here. We set up the split2 and split3 functions earlier, so that we here easily can assign 2 or 3 parameters in one go, this makes the code a lot nicer to write. We pick out the parts we want with our splits, and put them into our return list in the end.

Parsing is now done, and we have objects that are a lot nicer to work with than the plain text itself, so now we can start the real work in itself.

The list of different elements are not ordered in the correct order here, so we will have to set up a dependency chains so that we have the things we need when we need them. To make lookup a bit easier we create a hashtable of the instructions, to have a recipe for each piece, and use that later for the work we have to do.

1proc part1(insts: seq[Instruction]) =
2  let lookup = insts.to_lookup
3  let ans = lookup.get_wire "a"
4  echo "Part 1: ", ans

This of course is a very high level function, so we have to look into how we do this, to translate our list into a lookuptable we just invert the instructions and put them into a table:

1proc to_lookup(insts: seq[Instruction]): Table[Wire, Instruction] =
2  for inst in insts:
3    result[inst.dest] = inst

Now we can do fast lookups something we will really need when we start to figure out the dependencies for the signal that we really want to have.

 1proc get_wire(lookup: Table[Wire, Instruction], goal: Wire, override: bool = false, wire: Wire = "", val: uint16 = 0): uint16 =
 2  var signals: Table[Wire, uint16]
 3  var qu: Deque[Instruction]
 4
 5  if override:
 6    signals[wire] = val
 7
 8  qu.add_last lookup[goal]
 9  while qu.len > 0:
10    let cur = qu.popFirst
11    if not cur.can_do signals:
12      qu.add_first cur
13      if cur.a.kind == PWire and cur.a.wire not_in signals:
14        qu.add_first lookup[cur.a.wire]
15      if cur.b.kind == PWire and cur.b.wire not_in signals:
16        qu.add_first lookup[cur.b.wire]
17      continue
18    case cur.op
19    of Assign:
20      signals[cur.dest] = cur.a.get_val signals
21    of And:
22      let a = cur.a.get_val signals
23      let b = cur.b.get_val signals
24      signals[cur.dest] = a and b
25    of Or:
26      let a = cur.a.get_val signals
27      let b = cur.b.get_val signals
28      signals[cur.dest] = a or b
29    of Lshift:
30      let a = cur.a.get_val signals
31      let b = cur.b.get_val signals
32      signals[cur.dest] = a shl b
33    of Rshift:
34      let a = cur.a.get_val signals
35      let b = cur.b.get_val signals
36      signals[cur.dest] = a shr b
37    of Not:
38      let a = cur.a.get_val signals
39      signals[cur.dest] = bitnot a
40
41  return signals[goal]

This is where the majority of the work takes place. We here have some default arguements which are basically there so that I didn’t have to rewrite the function just to add support for the second part of the problem we will look at them a bit later.

We set up a hashtable of signal values, so that we don’t have to recompute them in case we come across them multiple times, so basically for memoisation.

We need the value of a specific signal here, and since the input is not in the order we need them, with the inputs on top, we will fetch stuff as we need them. So I set up a working queue a deque (Double ended queue) so that we can add stuff to the beginning or end. Looking at the code a second time, just using a seq as a stack would be enough in this case, but I didn’t think of that at the time, and it’s more fun showing off some more datastructures anyway.

Before we start working off the queue, we put the current value onto it, and we’re set to go.

We pop the top instruction off the stack and see if we can already compute the signal, and if we can’t yet calculate it because we’re missing values we put it back on the stack, and also add the prerequisits onto the stack if they haven’t already been computed.

When we can calculate an instruction we fetch the signals off the wires that we have, do the calculation, and we’re done with that task, and can go on with the next one.

Here we have one of those case statements where it’s really nice to have an enumeration, since it is exhaustive it means that we’ll always handle all the cases that we promised to. This way if we add another kind of operation, the compiler will yell at us until we also implement how to calculate it. This is one of the things that I really enjoy about statically typed languages, if I do something silly, the compiler will yell at me and tell me what I did wrong, instead of having to puzzle it out from some strange interaction that I did not expect.

We have two helper functions that helps us do this get_val and can_do and we’ll go through them.

1proc get_val(self: Parameter, wires: Table[Wire, uint16]): uint16 =
2  case self.kind
3  of Puint16:
4    self.val
5  of PWire:
6    wires[self.wire]
7  of PEmpty:
8    echo "Trying to get value of empty parameter"
9    quit 69

So get_val takes in a parameter, and the memoisation table, and basically unpacks the case object, if it’s an number we just return that, and if it’s a wire we look it up in the table and use that value. This means that the function will only work once the parameter is stored in the table, which is what our task queue that we set up does for us.

Empty values here are a special case, they should never be turned into a value since they are a placeholder, so this is basically just an Option[int|string] kind of type, so if we use this on a value that is empty we just write out a small reason and crash the program.

 1proc can_do(self: Instruction, wires: Table[Wire, uint16]): bool =
 2  if self.a.kind == PWire and self.b.kind == PWire and
 3     self.a.wire in wires and
 4     self.b.wire in wires:
 5       return true
 6  if self.a.kind == PWire and (self.b.kind == Puint16 or self.b.kind == PEmpty) and
 7     self.a.wire in wires:
 8       return true
 9  if self.b.kind == PWire and (self.a.kind == Puint16 or self.a.kind == PEmpty) and
10     self.b.wire in wires:
11       return true
12  if self.a.kind == Puint16 and self.b.kind == PEmpty:
13    return true
14  return false

can_do checks if we with our current state can actually calculate the value, it checks if parameters that are given as a reference and not a plain value actually exists, and if all of the needed ones are there we’re a’okay to continue on. This way we know if we can go on to calculate the value of the instruction, or if we will have to get some prerequisites first.

1proc part2(insts: seq[Instruction]) = 
2  let lookup = insts.to_lookup
3  let mid = lookup.get_wire "a"
4  let ans = lookup.get_wire("a", true, "b", mid)
5  echo "Part 2: ", ans

For the second part we have to go through once to get the value of wire “a” set value “b” and then rerun the calculation of the new “a”. This is where the optional parameters for the get_value procedure comes into play. All that I needed to add was the extra parameters, and this little thing in the function to preset our memoisation:

1  if override:
2    signals[wire] = val

As a nice sideffect this will also collapse the calculation of the “b” wire, which means that our second run through will be a bit faster.

Of course I could also reuse the value that we got from part 1 without recalculating it, but I like in these small programs just to have the two parts be completely independent.

And now at the end here is the complete listing of code where everything comes together, with imports and a little bit of plumbing to grab the lines of a file, here is the full listing of the program:

  1import 
  2  bitops,
  3  deques, 
  4  sequtils, 
  5  strformat, 
  6  strutils, 
  7  tables 
  8
  9type
 10  Op = enum
 11    Assign
 12    And
 13    Or
 14    LShift
 15    RShift
 16    Not
 17  
 18  Wire = string
 19  
 20  Pkind = enum
 21    PWire
 22    Puint16
 23    PEmpty
 24
 25  Parameter = object
 26    case kind: Pkind
 27    of PWire: wire: string
 28    of Puint16: val: uint16
 29    of PEmpty: discard
 30
 31  Instruction = tuple[a: Parameter, b: Parameter, op: Op, dest: Wire]
 32
 33func split2(str: string, sep: string): (string, string) =
 34  let parts = str.split(sep, 1)
 35  do_assert(parts.len == 2, &"Split2 {str} on {sep} did not return 2 parts")
 36  (parts[0], parts[1])
 37
 38func split3(str: string, sep: string): (string, string, string) =
 39  let parts = str.split(sep, 2)
 40  do_assert(parts.len == 3, &"Split3 {str} on {sep} did not return 3 parts")
 41  (parts[0], parts[1], parts[2])
 42
 43func to_param(str: string): Parameter =
 44  if str[0].is_digit:
 45    return Parameter(kind: Puint16, val: str.parse_uint.uint16)
 46  else:
 47    return Parameter(kind: PWire, wire: str)
 48
 49proc parse(lines: seq[string]): seq[Instruction] =
 50  for line in lines:
 51    let (main, dest) = line.split2 " -> "
 52    if "AND" in main:
 53      let op = And
 54      let (a, _, b) = main.split3 " "
 55      result.add (a.to_param, b.to_param, op, dest)
 56    elif "OR" in main:
 57      let op = Or
 58      let (a, _, b) = main.split3 " "
 59      result.add (a.to_param, b.to_param, op, dest)
 60    elif "LSHIFT" in main:
 61      let op = LShift
 62      let (a, _, b) = main.split3 " "
 63      result.add (a.to_param, b.to_param, op, dest)
 64    elif "RSHIFT" in main:
 65      let op = RShift
 66      let (a, _, b) = main.split3 " "
 67      result.add (a.to_param, b.to_param, op, dest)
 68    elif "NOT" in main:
 69      let op = Not
 70      let (_, a) = main.split2 " "
 71      let b = Parameter(kind: PEmpty)
 72      result.add (a.to_param, b, op, dest)
 73    else:
 74      let op = Assign
 75      let b = Parameter(kind: PEmpty)
 76      result.add (main.to_param, b, op, dest)
 77
 78proc can_do(self: Instruction, wires: Table[Wire, uint16]): bool =
 79  if self.a.kind == PWire and self.b.kind == PWire and
 80     self.a.wire in wires and
 81     self.b.wire in wires:
 82       return true
 83  if self.a.kind == PWire and (self.b.kind == Puint16 or self.b.kind == PEmpty) and
 84     self.a.wire in wires:
 85       return true
 86  if self.b.kind == PWire and (self.a.kind == Puint16 or self.a.kind == PEmpty) and
 87     self.b.wire in wires:
 88       return true
 89  if self.a.kind == Puint16 and self.b.kind == PEmpty:
 90    return true
 91  return false
 92
 93proc get_val(self: Parameter, wires: Table[Wire, uint16]): uint16 =
 94  case self.kind
 95  of Puint16:
 96    self.val
 97  of PWire:
 98    wires[self.wire]
 99  of PEmpty:
100    echo "Trying to get value of empty parameter"
101    quit 69
102
103proc get_wire(lookup: Table[Wire, Instruction], goal: Wire, override: bool = false, wire: Wire = "", val: uint16 = 0): uint16 =
104  var signals: Table[Wire, uint16]
105  var qu: Deque[Instruction]
106
107  if override:
108    signals[wire] = val
109
110  qu.add_last lookup[goal]
111  while qu.len > 0:
112    let cur = qu.popFirst
113    if not cur.can_do signals:
114      qu.add_first cur
115      if cur.a.kind == PWire and cur.a.wire not_in signals:
116        qu.add_first lookup[cur.a.wire]
117      if cur.b.kind == PWire and cur.b.wire not_in signals:
118        qu.add_first lookup[cur.b.wire]
119      continue
120    case cur.op
121    of Assign:
122      signals[cur.dest] = cur.a.get_val signals
123    of And:
124      let a = cur.a.get_val signals
125      let b = cur.b.get_val signals
126      signals[cur.dest] = a and b
127    of Or:
128      let a = cur.a.get_val signals
129      let b = cur.b.get_val signals
130      signals[cur.dest] = a or b
131    of Lshift:
132      let a = cur.a.get_val signals
133      let b = cur.b.get_val signals
134      signals[cur.dest] = a shl b
135    of Rshift:
136      let a = cur.a.get_val signals
137      let b = cur.b.get_val signals
138      signals[cur.dest] = a shr b
139    of Not:
140      let a = cur.a.get_val signals
141      signals[cur.dest] = bitnot a
142
143  return signals[goal]
144
145proc to_lookup(insts: seq[Instruction]): Table[Wire, Instruction] =
146  for inst in insts:
147    result[inst.dest] = inst
148
149proc part1(insts: seq[Instruction]) =
150  let lookup = insts.to_lookup
151  let ans = lookup.get_wire "a"
152  echo "Part 1: ", ans
153
154proc part2(insts: seq[Instruction]) = 
155  let lookup = insts.to_lookup
156  let mid = lookup.get_wire "a"
157  let ans = lookup.get_wire("a", true, "b", mid)
158  echo "Part 2: ", ans
159
160let input = toseq "day07.txt".lines
161let parsed = input.parse
162part1 parsed
163part2 parsed