6 min read

Eric Wastl created the website Advent of Code, a website that published a new programming exercise from the first of December until Christmas. I came across this website somewhere in the first few days of December and as I participated in the ACM ICPC in the past, I expected I should be able to solve these problems. I decided it would be a good idea to use Swift to write these solutions. While solving the problems, I came across one problem that I was able to do really well in Swift and I’d like to explain that one in this post.

Introduction

After reading the problem, I immediately noticed some interesting points:

  • We can model the input as a graph, where each wire is a vertex and each connection in the circuit connects some vertices to another vertex. For example x AND y -> z connect both x and y to vertex z.
  • The example input is ordered in such a way that you can just iterate over the lines from top to bottom and apply the changes. However, the real input does not have this ordering.

To get the real input in the correct ordering, one should note that the input is basically a DAG. Or at least it should be, otherwise it cannot be solved.

This means we can use topological sorting to sort the vertices of the graph in the order we should walk them.

Although in the example input, it seems that AND, OR, NOT, LSHIFT and RSHFT always operated on a wire, this is not the case. They can also operate on a constant value.

Implementation

Note that I replaced some guard lines with forced unwrapping here. The source code linked at the end contains the original code.

First off, we define a Source, which is an element of an operation, i.e. in x AND y both x and y are a Source:

enum Source {
   case Vertex(String)
   case Constant(UInt16)

   func valueForGraph(graph: Graph) -> UInt16 {
       switch self {
       case let .Vertex(vertex):
           return graph.vertices[vertex]!.value!
       case let .Constant(val):
           return val
       }
   }

   var vertex: String? {
       switch self {
       case let .Vertex(v):
           return v
       case .Constant(_):
           return nil
       }
   }

   static func parse(s: String) -> Source {
       if let i = UInt16(s) {
           return .Constant(i)
       } else {
           return .Vertex(s)
       }
   }
}

A Source is either a Vertex (i.e. a wire) and then it has a corresponding string as identifier, or it is a constant and then it contains some value. We define a function that will return the value for this Source given a Graph (more on this later). For a constant source the whole graph does not matter, but for a wire we should look up the value in the graph. The second function is used to extract the identifier of the vertex of the source, if any. Finally we also have a function that helps us parse a string or integer into a Source.

Next up we have an Operation enumeration, which holds all information about one line of input:

enum Operation {
   case Assign(Source)
   case And(Source, Source)
   case Or(Source, Source)
   case Not(Source)
   case LeftShift(Source, UInt16)
   case RightShift(Source, UInt16)
  
   func applytoGraph(graph: Graph, vertex: String) {
       let v = graph.vertices[vertex]!
       switch self {
       case let .Assign(source1):
           v.value = source1.valueForGraph(graph)
       case let .And(source1, source2):
           v.value = source1.valueForGraph(graph) & source2.valueForGraph(graph)
       /* etc for other cases */
       case let .RightShift(source1, bits):
           v.value = source1.valueForGraph(graph) >> bits
       }
   }

   static func parseOperation(input: String) -> Operation {
       if let and = input.rangeOfString(" AND ") {
           let before = input.substringToIndex(and.startIndex)
           let after = input.substringFromIndex(and.endIndex)
           return .And(Source.parse(before), Source.parse(after))
       } /* etc for other options */
      
   var sourceVertices: [String] {
         /* code that switches on self and extracts vertex from each source */
   }

The operation enum has a static function that allows us to parse a line from the input into an Operation and a function that will allow us to apply it to a graph. Furthermore, it has a computed variable that returns all source vertices for the operation.

Now a Vertex is an easy class:

class Vertex {
   var idx: String
   var outgoing: Set<String>
   var incoming: Set<String>
   var operations: [Operation]
   var value: UInt16?

   init(idx: String) {
       self.idx = idx
       self.outgoing = []
       self.incoming = []
       self.operations = []
   }
}

It has an ID and keeps track of a set of incoming and outgoing edges (we need both for topological sorting). Furthermore, it has a value (which is initially not set) and a list of operations that has this vertex as target.

Because we want to store vertices in a set, we need to let it conform to Equatable and Hashable. Because we have a unique string identifier for each vertex, this is easy:

extension Vertex: Equatable {}

func ==(lhs: Vertex, rhs: Vertex) -> Bool {
   return lhs.idx == rhs.idx
}

extension Vertex: Hashable {
   var hashValue: Int {
        return self.idx.hashValue
   }
}

The last structure we need is a graph, which basically hold a list of all vertices:

class Graph {
   var vertices: [String: Vertex]

   init() {
       self.vertices = [:]
   }

   func addVertexIfNotExists(idx: String) {
       if let _ = self.vertices[idx] {
           return
       }

       self.vertices[idx] = Vertex(idx: idx)
   }

   func addOperation(operation: Operation, target: String) {
         // Add an operation for a given target to this graph
  
       self.addVertexIfNotExists(target)
       self.vertices[target]?.operations.append(operation)
       let sourceVertices = operation.sourceVertices
       for v in sourceVertices {
           self.addVertexIfNotExists(v)
           self.vertices[target]?.incoming.insert(v)
           self.vertices[v]?.outgoing.insert(target)
       }
   }  
}

We define a helper function that ads a vertex if not already added. We then use this function to define a function that can add operation to the graph, together with all required vertices and edges.

Now we need to be able to topologically sort the vertices of the graph, which can be done using Kahn’s Algorithm[MA6] . This[MA7]  can be done in Swift almost exactly using the pseudo-code explained there:

extension Graph {
   func topologicalOrder() -> [Vertex] {
       var L: [Vertex] = []
       var S: Set<Vertex> = Set(vertices.values.filter { $0.incoming.count == 0 })

       while S.count > 0 {
           guard let n = S.first else { fatalError("No more nodes in S") }
           S.remove(n)
           L.append(n)

           for midx in n.outgoing {
               guard let m = self.vertices[midx] else { fatalError("Can not find vertex") }
               n.outgoing.remove(m.idx)
               m.incoming.remove(n.idx)

               if m.incoming.count == 0 {
                   S.insert(m)
               }
           }
       }
      
       return L
   }
}

Now we are basically done, as we can now write up a function that calculates the value of a given wire in a graph:

func getFinalValueInGraph(graph: Graph, vertex: String) -> UInt16? {
   let topo = graph.topologicalOrder()

   for vertex in topo {
       for op in v.operations {
           op.applytoGraph(graph, vertex: vertex.idx)
       }
   }

   return graph.vertices[vertex]?.value
}

Conclusions

This post (hopefully) gave you some insight intohow I solved one of the bigger Advent of Code problems. As you can see Swift has some really nice features that help in this case, like enums with types and functional methods like filter. If you like these kinds of problems I suggest you go to the Advent of Code website and start solving the problems. There are quite a few that are really easy to get started.

The complete code for this blogpost can be found at my GitHub account.

About the author

Nicky Gerritsen is currently a Software Architect at StreamOne, a small Dutch company specialized in video streaming and storage. In his spare time he loves to code on Swift projects and learn about new things Swift. He can be found on Twitter @nickygerritsen and on GitHub: https://github.com/nickygerritsen/.

LEAVE A REPLY

Please enter your comment!
Please enter your name here