use "collections" use "files" use "format" // The cardinal directions primitive U primitive D primitive L primitive R type Dir is (U | D | L | R) // A basic two-dimensional point class class val Point is Hashable let _x: I64 let _y: I64 new val create(__x: I64, __y: I64) => _x = __x _y = __y fun x(): I64 => _x fun y(): I64 => _y // because we want to use this as a key in a hashmap fun hash(): USize => // hey this is probably bad, huh? _x.hash() + _y.hash() fun eq(other: Point): Bool => (x() == other.x()) and (y() == other.y()) fun ne(other: Point): Bool => not eq(other) // return the point that is `amt` squares awy from this one in `d` direction fun in_direction(d: Dir, amt: I64): Point => match d | U => Point(_x, _y-amt) | D => Point(_x, _y+amt) | L => Point(_x-amt, _y) | R => Point(_x+amt, _y) end // print prettily fun show(): String => "(" + Format.int[I64](_x) + ", " + Format.int[I64](_y) + ")" // An 'instruction': a direction and a distance to travel in that // direction class val Instr let _dir: Dir let _amt: I64 // parse from the string repr new val from_str(s: String) ? => _dir = match s(0)? | 'U' => U | 'D' => D | 'L' => L | 'R' => R else error end _amt = s.trim(1).i64()? // given a starting point, return the array of all the points that // would be covered by this instruction fun points(start: Point): Array[Point] => var p = Array[Point]() for i in Range[I64](0, _amt) do p.push(start.in_direction(_dir, i+1)) end p // A representation of the 'plan' for a line: nothing more than a //sequence of 'Instr's class val LinePlan let _plan: Array[Instr] new val from_str(s: String) ? => var p = Array[Instr]() for chunk in s.split(",").values() do p.push(Instr.from_str(chunk)?) end _plan = p // this just gives the rest of the world access to our plan // mwahahahaha fun plan(): this->Array[Instr] => _plan // The value we stores in the map: a list of which wires exist at that //grid square as well as their distance along the wire class Wires let wires: Array[(U8, U64)] // we always create this with no wires initialized new create() => wires = Array[(U8, U64)]() // this adds a new wire, and if a different wire already exists at // this spot then return the combined distance from their respective // roots, otherwise return None fun ref add_wire(wire: U8, dist: U64): (U64 | None) => wires.push((wire, dist)) var min_dist: (U64 | None) = None for (w, d) in wires.values() do if wire != w then let new_dist = d + dist match min_dist | None => min_dist = new_dist | let old_min: U64 if new_dist < old_min => min_dist = new_dist end end end min_dist // for pretty-printing, return a character represents this specific //wire, using '*' for intersections fun char(): String => var s = Set[U8]() for (w, _) in wires.values() do s.set(w) end if s.size() > 1 then "*" else try Format.int[U8](s.values().next()?) else "?" end end // the actual grid type that contains our grid logic class Grid // a map from point to wire content. we could use a 2d array or //something, but 1. this does not need to grow when we go off the //'sides' and 2. it is sparse var storage: Map[Point, Wires] // this lists the intersections, keyed by their distance var intersections: Array[(U64, Point)] new create() => storage = Map[Point, Wires]() intersections = Array[(U64, Point)]() // print prettily fun show(env: Env) => var min_x: I64 = 0 var min_y: I64 = 0 var max_x: I64 = 0 var max_y: I64 = 0 for p in storage.keys() do min_x = p.x().min(min_x) min_y = p.y().min(min_y) max_x = p.x().max(max_x) max_y = p.y().max(max_y) end var buf = recover String((((max_x - min_x) + 1) * (max_y - min_y)).usize()) end for y in Range[I64](min_y, max_y + 1) do for x in Range[I64](min_x, max_x + 1) do if (y == 0) and (x == 0) then env.out.write("O") else try env.out.write(storage(Point(x, y))?.char()) else env.out.write(".") end end end env.out.write("\n") end // set point `p` to include wire `l` at distance `dist` from its // origin. this will automatically record an intersection if point // `p` already includes a different wire fun ref set(p: Point, l: U8, dist: U64) => storage.insert_if_absent(p, Wires.create()) try let wire = storage(p)? match wire.add_wire(l, dist) | let n: U64 => intersections.push((n, p)) | None => None end end // follow each `LinePlan` and adds the description of the wires to the grid fun ref addLines(plans: Array[LinePlan]) => var line_number: U8 = 1 for plan in plans.values() do var start_point = Point(0, 0) var dist: U64 = 1 for instr in plan.plan().values() do for ps in instr.points(start_point).values() do set(ps, line_number, dist) start_point = ps dist = dist + 1 end end line_number = line_number + 1 end // print all the intersection values along with the point they map to. fun show_intersections(env: Env) => for (dist, p) in intersections.values() do env.out.print(Format.int[U64](dist) + ": " + p.show()) end actor Main new create(env: Env) => let caps = recover val FileCaps.>set(FileRead).>set(FileStat) end try with file = OpenFile(FilePath(env.root as AmbientAuth, "input.txt", caps)?) as File do var line_plans = Array[LinePlan]() for line in file.lines() do try line_plans.push(LinePlan.from_str(consume line)?) end end var grid = Grid.create() grid.addLines(line_plans) grid.show_intersections(env) end else env.err.print("Couldn't read expected file `input.txt'") env.exitcode(99) end