aoc2021/Sources/12/12.swift

//
//  File.swift
//
//
//  Created by Max Nuding on 12.12.21.
//

import Foundation
import Runner
import Collections

class Cave: Hashable, CustomStringConvertible, CustomDebugStringConvertible {
    static func == (lhs: Cave, rhs: Cave) -> Bool { lhs.name == rhs.name }
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(name)
    }
    
    var description: String { name }
    var debugDescription: String { name }
    
    let name: String
    var connectedCaves = [Cave]()
    var isBigCave: Bool
    var isEnd: Bool
    var isStart: Bool
    
    required init(name: String) {
        self.name = name
        self.isBigCave = name.first!.isUppercase
        self.isEnd = name == "end"
        self.isStart = name == "start"
    }
}

struct Path: Hashable, CustomStringConvertible {
    var parts: [Cave]
    var visitedSmallCaveTwice = false
    var description: String
    
    func contains(cave: Cave) -> Bool { parts.contains(cave) }
    
    func appending(cave: Cave) -> Path {
        var newParts = parts
        newParts.append(cave)
        return Path(
            parts: newParts,
            visitedSmallCaveTwice: visitedSmallCaveTwice || !cave.isBigCave && contains(cave: cave))
    }
    
    static func == (lhs: Path, rhs: Path) -> Bool { lhs.description == rhs.description }
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(description)
    }
    
    init(parts: [Cave], visitedSmallCaveTwice: Bool = false) {
        self.parts = parts
        self.visitedSmallCaveTwice = visitedSmallCaveTwice
        self.description = (visitedSmallCaveTwice ? "*" : "") + parts.map {$0.description}.joined(separator: "->")
    }
}

class Day12: Runnable {
    let inputPath: String
    var caves = [String:Cave]()
    
    required init(inputPath: String) {
        self.inputPath = inputPath
    }
    
    public func run() {
        let input = try! String(contentsOfFile: inputPath)
        caves = input
            .trimmingCharacters(in: .newlines)
            .components(separatedBy: .newlines)
            .reduce(into: [String:Cave](), { caves, line in
                let caveConnection = line.components(separatedBy: "-")
                let caveFromName = caveConnection.first!
                let caveToName = caveConnection.last!
                let from = caves[caveFromName] ?? Cave(name: caveFromName)
                let to = caves[caveToName] ?? Cave(name: caveToName)
                from.connectedCaves.append(to)
                to.connectedCaves.append(from)
                caves[caveFromName] = from
                caves[caveToName] = to
                
            })
        runA()
        runB()
        
    }
    
    func runA() {
        var queue = Deque<Path>(minimumCapacity: 10000)
        var visited = Set<Path>(minimumCapacity: 10000)
        var numFinished = 0
        
        var cave: Path? = Path(parts: [caves["start"]!])
        queue.append(cave!)
        
        while !queue.isEmpty {
            cave = queue.popFirst()
            if visited.contains(cave!) {
                continue
            }
            visited.insert(cave!)
            
            cave!.parts.last!.connectedCaves
                .filter { $0.isBigCave || !cave!.contains(cave: $0) }
                .forEach {
                    if $0.isEnd {
                        numFinished += 1
                        //print("Finished: \(cave!.parts)->end")
                        return
                    }
                    var newParts = cave!.parts
                    newParts.append($0)
                    queue.append(Path(parts: newParts))
                }
        }
        print(numFinished)
    }
    
    func runB() {
        var queue = Deque<Path>(minimumCapacity: 1000000)
        var visited = Set<Path>(minimumCapacity: 1000000)
        var numFinished = 0
        
        var cave: Path? = Path(parts: [caves["start"]!])
        queue.append(cave!)
        
        while !queue.isEmpty {
            cave = queue.popFirst()
            if visited.contains(cave!) {
                continue
            }
            visited.insert(cave!)
            cave!.parts.last!.connectedCaves
                .forEach {
                    if $0.isStart || (cave!.visitedSmallCaveTwice && !$0.isBigCave && cave!.contains(cave: $0)) {
                        return
                    }
                    if $0.isEnd {
                        numFinished += 1
                        return
                    }
                    var newParts = cave!.parts
                    newParts.append($0)
                    queue.append(cave!.appending(cave: $0))
                }
        }
        print(numFinished)
    }
}