Created
December 20, 2019 12:09
-
-
Save erikaderstedt/e133d93cb4990321c930e1ddd2a50971 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| struct Position: Hashable { | |
| let x: Int | |
| let y: Int | |
| let depth: Int | |
| var adjacent: [Position] { | |
| return [Position(x: x-1, y: y, depth: depth), | |
| Position(x: x+1, y: y, depth: depth), | |
| Position(x: x, y: y-1, depth: depth), | |
| Position(x: x, y: y+1, depth: depth)] | |
| } | |
| init(x: Int, y: Int, depth: Int = 0) { | |
| self.x = x | |
| self.y = y | |
| self.depth = depth | |
| } | |
| } | |
| enum Space: CustomStringConvertible { | |
| case wall | |
| case open | |
| case portal(String) | |
| case empty | |
| init(_ s: Character) { | |
| switch s { | |
| case "#": | |
| self = .wall | |
| case ".": | |
| self = .open | |
| case " ": | |
| self = .empty | |
| case let a: | |
| self = .portal(String(a)) | |
| } | |
| } | |
| var description: String { | |
| switch self { | |
| case .wall: return "#" | |
| case .empty: return " " | |
| case .open: return "." | |
| case .portal(let s): | |
| if s.count == 2 { | |
| return s | |
| } else { | |
| return "?" | |
| } | |
| } | |
| } | |
| } | |
| struct Grid { | |
| let spaces: [[Space]] | |
| let width: Int | |
| let height: Int | |
| let portals: [String: (Position, Position?)] | |
| init(string s: String) { | |
| let rows = s.components(separatedBy: .newlines) | |
| self.height = rows.count | |
| self.width = rows.reduce(0, { max($0, $1.count) }) | |
| let w = width | |
| var g = rows.map({ (s: String) -> [Space] in | |
| var a = Array<Space>(repeating: .empty, count: w) | |
| for i in s.enumerated() { | |
| a[i.offset] = Space(i.element) | |
| } | |
| return a | |
| }) | |
| var p1 = [String: (Position, Position?)]() | |
| // Outer portals | |
| for c in 0..<width { | |
| if case let Space.portal(s) = g[1][c], case let Space.portal(s2) = g[0][c] { | |
| g[1][c] = .portal(s2 + s) | |
| g[0][c] = .empty | |
| p1[s2+s] = (Position(x: c, y: 2), nil) | |
| } | |
| if case let Space.portal(s) = g[height-2][c], case let Space.portal(s2) = g[height-1][c] { | |
| g[height-2][c] = .portal(s + s2) | |
| g[height-1][c] = .empty | |
| p1[s+s2] = (Position(x: c, y: height-3), nil) | |
| } | |
| } | |
| for r in 0..<height { | |
| if case let Space.portal(s) = g[r][0], case let Space.portal(s2) = g[r][1] { | |
| g[r][1] = .portal(s + s2) | |
| g[r][0] = .empty | |
| p1[s+s2] = (Position(x: 2, y: r), nil) | |
| } | |
| if case let Space.portal(s) = g[r][width-2], case let Space.portal(s2) = g[r][width-1] { | |
| g[r][width-2] = .portal(s + s2) | |
| g[r][width-1] = .empty | |
| p1[s+s2] = (Position(x: width - 3, y: r), nil) | |
| } | |
| } | |
| // Iterate over grid positions | |
| for r in 4..<(height-4) { | |
| for c in 4..<(width-4) { | |
| if case let Space.portal(s) = g[r][c] { | |
| if case let Space.portal(s2) = g[r+1][c] { | |
| if r > height/2 { | |
| g[r+1][c] = .portal(s + s2) | |
| g[r][c] = .empty | |
| p1[s+s2] = (p1[s+s2]!.0, Position(x: c, y: r+2)) | |
| } else { | |
| g[r+1][c] = .empty | |
| g[r][c] = .portal(s + s2) | |
| p1[s+s2] = (p1[s+s2]!.0, Position(x: c, y: r-1)) | |
| } | |
| } else if case let Space.portal(s2) = g[r][c+1] { | |
| if c > width/2 { | |
| g[r][c+1] = .portal(s + s2) | |
| g[r][c] = .empty | |
| p1[s+s2] = (p1[s+s2]!.0, Position(x: c+2, y: r)) | |
| } else { | |
| g[r][c+1] = .empty | |
| g[r][c] = .portal(s + s2) | |
| p1[s+s2] = (p1[s+s2]!.0, Position(x: c-1, y: r)) | |
| } | |
| } | |
| } | |
| } | |
| } | |
| self.portals = p1 | |
| self.spaces = g | |
| } | |
| } | |
| func distance(to destination: Position, from source: Position, in grid: Grid, recursiveSpaces: Bool) -> Int { | |
| var steps = 0 | |
| var leafStates = [source] | |
| var oldStates = [Position]() | |
| while true { | |
| steps = steps + 1 | |
| var additionalStates = [Position]() | |
| for leaf in leafStates { | |
| let moves = leaf.adjacent.compactMap({ | |
| (p: Position) -> Position? in | |
| switch grid.spaces[p.y][p.x] { | |
| case .wall, .empty: return nil | |
| case .open: return p | |
| case .portal(let s): | |
| guard let z = grid.portals[s] else { return nil } | |
| if recursiveSpaces { | |
| // Are we at the outer ring? If so, entering this portal will decrease depth. | |
| if z.0.x == leaf.x && z.0.y == leaf.y { | |
| if leaf.depth > 0, let o = z.1 { | |
| return Position(x: o.x, y: o.y, depth: leaf.depth - 1) | |
| } else { | |
| return nil | |
| } | |
| } else { | |
| return Position(x: z.0.x, y: z.0.y, depth: leaf.depth + 1) | |
| } | |
| } else { | |
| return (z.0 == leaf) ? z.1 : z.0 | |
| } | |
| } | |
| }) | |
| for move in moves { | |
| if oldStates.contains(move) { continue } | |
| if move == destination { | |
| return steps | |
| } | |
| additionalStates.append(move) | |
| } | |
| } | |
| oldStates = leafStates | |
| leafStates = additionalStates | |
| } | |
| } | |
| let path = CommandLine.arguments[1] | |
| let i = try! String(contentsOf: URL(fileURLWithPath: path)) | |
| let g = Grid(string: i) | |
| let startPosition = g.portals["AA"]!.0 | |
| let endPosition = g.portals["ZZ"]!.0 | |
| print("Pt 1:", distance(to: endPosition, from: startPosition, in: g, recursiveSpaces: false)) | |
| print("Pt 2:", distance(to: endPosition, from: startPosition, in: g, recursiveSpaces: true)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment