ilyakooo0 · January 20, 2018 19:39
diff --git a/turing2Post.swift b/turing2Post.swift
 import Foundation
 #if os(Linux)
    import SwiftGlibc
    
    SwiftGlibc.srandom(UInt32(time(nil)))

    public func arc4random_uniform(_ max: UInt32) -> Int32 {
        return (SwiftGlibc.rand() % Int32(max-1))
    }
 #endif

 func stringFromBytes(bytes: UnsafeMutablePointer<UInt8>, count: Int) -> String {
    return String((0..<count).map ({Character(UnicodeScalar(bytes[$0]))}))
 }
 func readStringFromFile(path: String) -> String {
    let fp = fopen(path, "r"); defer {fclose(fp)}
    var outputString = ""
    let chunkSize = 1024
    let buffer: UnsafeMutablePointer<UInt8> = UnsafeMutablePointer.allocate(capacity: chunkSize); defer {buffer.deallocate(capacity: chunkSize)}
    repeat {
        let count: Int = fread(buffer, 1, chunkSize, fp)
        guard ferror(fp) == 0 else {break}
        if count > 0 {
            outputString += stringFromBytes(bytes: buffer, count: count)
        }
    } while feof(fp) == 0
    
    return outputString
 }

 extension String {
    func write(toFile path: String) -> Bool {
        let fp = fopen(path, "w"); defer {fclose(fp)}
        var byteArray: [UInt8] = self.utf8.map {$0}
        let count = fwrite(&byteArray, 1, byteArray.count, fp)
        return count == self.utf8.count
    }
 }

 protocol Descriptable {
    func description() -> String
 }
 extension Int {
    var toArray: [Bool] {
        if self == 0 {
            return [false]
        } else {
            var outp: [Bool] = []
            var temp = self
            while temp > 0 {
                outp.append(temp & 1 == 1)
                temp = temp >> 1
            }
            return Array(outp.reversed())
        }
    }
    func toArray(paddingTo: Int) -> [Bool] {
        let out = self.toArray
        let foo = paddingTo - out.count
        let count = foo > 0 ? foo : 0
        return Array(repeatElement(false, count: count)) + out
    }
 }

 extension Array {
    var permuatations: [[Element]] {
        var out: [[Element]] = []
        for (i, c) in self.enumerated() {
            var b = self
            b.remove(at: i)
            out += b.permuatations.map {[c] + $0}
        }
        return out.count == 0 ? [[]] : out
    }
 }

 class PostMachine {
    var alphabet: [String: String] = [:]
    var states: [PostState] = []
    func description() -> String {
        var outp = ""
        for (i, state) in states.enumerated() {
            outp.append("\(i + 1). ")
            switch state {
            case .clear(let next, let s):
                outp.append("[X][\(next)][\(s ?? "")]")
            case .condition(let zero, let one, let s):
                outp.append("[?][\(zero),\(one)][\(s ?? "")]")
            case .left(let next, let s):
                outp.append("[<][\(next)][\(s ?? "")]")
            case .mark(let next, let s):
                outp.append("[V][\(next)][\(s ?? "")]")
            case .right(let next, let s):
                outp.append("[>][\(next)][\(s ?? "")]")
            case .stop(let s):
                outp.append("[S][][\(s ?? "")]")
            }
            outp.append("\n")
        }
        return outp
    }
    
    func optimize() {
        var didChange = true
        large: while didChange {
            didChange = false
            for (var i, state) in states.enumerated() {
                switch state {
                case .condition(var l, let r, _):
                    if l == r {
                        didChange = true
                        states.remove(at: i)
                        i += 1
                        if l > i {
                            l -= 1
                        }
                        for (j, lstate) in states.enumerated() {
                            switch lstate {
                            case .clear(let m, let s2):
                                if m == i {
                                    states[j] = .clear(l, s2)
                                } else if m > i {
                                    states[j] = .clear(m - 1, s2)
                                }
                            case .condition(var m1, var m2, let s2):
                                if m1 == i {
                                    m1 = l
                                } else if m1 > i {
                                    m1 -= 1
                                }
                                if m2 == i {
                                    m2 = l
                                } else if m2 > i {
                                    m2 -= 1
                                }
                                states[j] = .condition(m1, m2, s2)
                            case .left(let m, let s2):
                                if m == i {
                                    states[j] = .left(l, s2)
                                } else if m > i {
                                    states[j] = .left(m - 1, s2)
                                }
                            case .mark(let m, let s2):
                                if m == i {
                                    states[j] = .mark(l, s2)
                                } else if m > i {
                                    states[j] = .mark(m - 1, s2)
                                }
                            case .right(let m, let s2):
                                if m == i {
                                    states[j] = .right(l, s2)
                                } else if m > i {
                                    states[j] = .right(m - 1, s2)
                                }
                            case .stop(_):
                                break
                            }
                        }
                        continue large
                    }
                default:
                    break
                }
                for (var n, nstate) in states.enumerated().dropFirst(i + 1) {
                    if state == nstate {
 //                        print("match\t\(state)\t\(nstate)")
                        didChange = true
                        states.remove(at: n)
                        n += 1
                        i += 1
                        for (j, lstate) in states.enumerated() {
                            switch lstate {
                            case .clear(let m, let s):
                                if m == n {
                                    states[j] = .clear(i, s)
                                } else if m > n {
                                    states[j] = .clear(m - 1, s)
                                }
                            case .condition(var m1, var m2, let s):
                                if m1 == n {
                                    m1 = i
                                } else if m1 > n {
                                    m1 -= 1
                                }
                                if m2 == n {
                                    m2 = i
                                } else if m2 > n {
                                    m2 -= 1
                                }
                                states[j] = .condition(m1, m2, s)
                            case .left(let m, let s):
                                if m == n {
                                    states[j] = .left(i, s)
                                } else if m > n {
                                    states[j] = .left(m - 1, s)
                                }
                            case .mark(let m, let s):
                                if m == n {
                                    states[j] = .mark(i, s)
                                } else if m > n {
                                    states[j] = .mark(m - 1, s)
                                }
                            case .right(let m, let s):
                                if m == n {
                                    states[j] = .right(i, s)
                                } else if m > n {
                                    states[j] = .right(m - 1, s)
                                }
                            case .stop:
                                break
                            }
                        }
                        continue large
                    }
                }
            }
        }
    }
    
    private enum Placeholder {
        case normal(PostState)
        case left(String, comment: String?)
        case right(String, comment: String?)
        case mark(String, comment: String?)
        case clear(String, comment: String?)
        case condition(String, String, comment: String?)
        mutating func move(to state: Int) {
            switch self {
            case .normal(let s):
                switch s {
                case .clear(_, let s):
                    self = .normal(.clear(state, s))
                case .condition(_, _, _):
                    fatalError()
                case .left(_, let s):
                    self = .normal(.left(state, s))
                case .mark(_, let s):
                    self = .normal(.mark(state, s))
                case .right(_, let s):
                    self = .normal(.right(state, s))
                case .stop(let s):
                    self = .normal(.stop(s))
                }
            default:
                fatalError("This shouldn't be")
            }
        }
        mutating func move(to state: String) {
            switch self {
            case .normal(let s):
                switch s {
                case .clear(_, let s):
                    self = .clear(state, comment: s)
                case .condition(_, _, _):
                    fatalError("This really shouyldn't happen either")
                case .left(_, let s):
                    self = .left(state, comment: s)
                case .mark(_, let s):
                    self = .mark(state, comment: s)
                case .right(_, let s):
                    self = .right(state, comment: s)
                case .stop(let s):
                    self = .normal(.stop(s))
                }
            default:
                fatalError("This really shouldn't happen")
            }
        }
        func dePlacehold(replacements: [String: Int]) -> PostState {
            switch self {
            case .normal(let ps):
                return ps
            case .clear(let s, let c):
                return .clear(replacements[s]!, c)
            case .condition(let s1, let s2, let c):
                return .condition(replacements[s1]!, replacements[s2]!, c)
            case .left(let s, let c):
                return .left(replacements[s]!, c)
            case .mark(let s, let c):
                return .mark(replacements[s]!, c)
            case .right(let s, let c):
                return .right(replacements[s]!, c)
            }
        }
    }
    private struct Binary {
        private let value: Int
        init(value: Int) {
            self.value = value
        }
        /// true if 1
        /// false if 0
        subscript(place: Int) -> Bool {
            return value & (1 << place) != 0
        }
    }
    
    init<A>(from turing: TuringMachine<A>) {
 //        let states = Array(0..<5).permuatations.map {PostMachine.init(from: turing, with: $0).states}
 //        let state = states.sorted(by: {$0.count < $1.count}).map {$0.count}
 //        print(state)
        let foo = PostMachine.init(from: turing, with: Array(1..<8))
        self.states = foo.states
        self.alphabet = foo.alphabet
    }
    
    private init<A>(from turing: TuringMachine<A>, with bins: [Int]) {
        var alphabet: [A: [Bool]] = [:]
        var backAlphabet: [Int: A] = [:]
        zip(bins, Set(turing.states.reduce([]) {$0 + $1.operations.keys}).shuffled().filter({$0 as! String != "_"})).forEach { (i, n) in
            alphabet[n] = i.toArray(paddingTo: 3) //Binary(value: i)
            backAlphabet[i] = n
        }
        alphabet["_" as! A] = 0.toArray(paddingTo: 3)
        backAlphabet[0] = "_" as? A
        for (k, v)  in alphabet {
            self.alphabet[k.description()] = v.reduce("") {$0 + ($1 ? "1" : "0")}
        }
 //        print(bins.map {$0.toArray(paddingTo: 3)})
        var i = 1
        var futureStates: [Placeholder] = []
        var replacements: [String: Int] = [:]
        
        
        
        for state in turing.states {
 //            print(state)
            let operations = state.operations
 //            print(operations)
            var j = 0
            let order = backAlphabet.keys.lazy.filter({state.operations[backAlphabet[$0]!] != nil}).sorted().map {(bin: $0.toArray(paddingTo: 3), value: backAlphabet[$0]!)}
            replacements[state.name] = i
 //            print(order)
 //            print(state)
            func step(order: [(bin: [Bool], value: A)], movedSoFar: Int) {
                
 //                print(order)
                if order.count == 0 {
                    print("Something has gone terribly wrong...\nI am going to continue, but I will likely hang, crash or the result will be wrong...\nMost likely cause: you replaced tabs with spaces in the input file")
                }
                if order.count == 1 {
                    let char = order.first!.value
 //                    print(char)
                    let op = operations[char]!
                    if op.move == .stay && op.nextState == .self && op.place == char {
                        for _ in 0..<movedSoFar {/// added later see if works
                            futureStates.append(.normal(.left(i + j + 1, state.name)))
                            j += 1
                        }
                        futureStates.append(.normal(.stop(state.name)))
                        j += 1
                        return
                    }
                    var isOnTheLeft = false
                    if op.place != char {
                        for _ in movedSoFar..<2 {
                            futureStates.append(.normal(.right(i + j + 1, state.name)))
                            j += 1
                        }
                        for bit in zip(alphabet[char]!, alphabet[op.place]!).map({$0 == $1 ? nil : $1}).reversed() {
                            //                        for bit in alphabet[char]!.reversed() {
                            if let bit = bit {
                                if bit {
                                    futureStates.append(.normal(.mark(i + j + 1, state.name)))
                                } else {
                                    futureStates.append(.normal(.clear(i + j + 1, state.name)))
                                }
                                j += 1
                            }
                            futureStates.append(.normal(.left(i + j + 1, state.name)))
                            j += 1
                        }
                        isOnTheLeft = true
                        j -= 1
                        futureStates.removeLast()
                    }
                    switch op.move {
                    case .stay:
                        if !isOnTheLeft {
                            for _ in 0..<movedSoFar {
                                futureStates.append(.normal(.left(i + j + 1, state.name)))
                                j += 1
                            }
                        }
                    case .left:
                        if !isOnTheLeft {
                            for _ in 0..<movedSoFar {
                                futureStates.append(.normal(.left(i + j + 1, state.name)))
                                j += 1
                            }
                        }
                        for _ in 0..<3 {
                            futureStates.append(.normal(.left(i + j + 1, state.name)))
                            j += 1
                        }
                    case .right:
                        if isOnTheLeft {
                            for _ in 0..<3 {
                                futureStates.append(.normal(.right(i + j + 1, state.name)))
                                j += 1
                            }
                        } else {
                            for _ in movedSoFar..<3 {
                                futureStates.append(.normal(.right(i + j + 1, state.name)))
                                j += 1
                            }
                        }
                    }
                    switch op.nextState {
                    case .self:
                        futureStates[futureStates.count - 1].move(to: state.name)
                    case .other(let ns):
                        futureStates[futureStates.count - 1].move(to: turing.names[ns])
                    }
                } else {
                    
                    
                    let fs = order.filter {$0.bin.first == false}
                    let ts = order.filter {$0.bin.first == true}
                    
                    if fs.count == 0 {
                        futureStates.append(.normal(.right(i + j + 1, state.name)))
                        j += 1
                        step(order: ts.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))
                    } else if ts.count == 0 {
                        futureStates.append(.normal(.right(i + j + 1, state.name)))
                        j += 1
 //                        print("FS\t\t\(fs)")
                        step(order: fs.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))
                    } else {
                        let sj = j
                        futureStates.append(.normal(.stop(state.name))) // Will change later on in code
                        
                        j += 1
                        
                        // Dealing with fs
                        let fsj = j
                        if movedSoFar < 2 {
                            futureStates.append(.normal(.right(i + j + 1, state.name)))
                            j += 1
                        }
 //                        print(order, movedSoFar)
                        
                        step(order: fs.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))
                        
                        // Dealing with ts
                        let tsj = j
                        if movedSoFar < 2 {
                            futureStates.append(.normal(.right(i + j + 1, state.name)))
                            j += 1
                        }

                        step(order: ts.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))

                        // Changing
                        
                        futureStates[i + sj - 1] = .normal(.condition(i + fsj, i + tsj, state.name))
                        
                    }
                }
            }
            
            step(order: order, movedSoFar: 0)

            i += j
        }
        
        self.states = futureStates.map {$0.dePlacehold(replacements: replacements)}
        
    }
 }

 enum PostState: Equatable {
    static func ==(lhs: PostState, rhs: PostState) -> Bool {
        switch lhs {
        case .clear(let i, _):
            switch rhs {
            case .clear(let j, _):
                return i == j
            default:
                return false
            }
        case .condition(let i1, let i2, _):
            switch rhs {
            case .condition(let j1, let j2, _):
                return i1 == j1 && i2 == j2
            default:
                return false
            }
        case .left(let i, _):
            switch rhs {
            case .left(let j, _):
                return i == j
            default:
                return false
            }
        case .mark(let i, _):
            switch rhs {
            case .mark(let j, _):
                return i == j
            default:
                return false
            }
        case .right(let i, _):
            switch rhs {
            case .right(let j, _):
                return i == j
            default:
                return false
            }
        case .stop(_):
            switch rhs {
            case .stop(_):
                return true
            default:
                return false
            }
        }
    }
    
    case left(Int, String?)
    case right(Int, String?)
    case mark(Int, String?)
    case clear(Int, String?)
    case condition(Int, Int, String?)
    case stop(String?)
 }

 extension String: Descriptable {
    func description() -> String {
        return self
    }
 }

 class TuringMachine<A: Hashable & Descriptable> {
    let names: [String]
    var states: [State<A>] = []
    init(names: [String]) {
        self.names = names
    }
    init(from s: String) {
        let ss = String(s.map({$0 == "\r\n" ? "\n" : $0})).split(separator: "\n").map {$0.split(separator: "\t", omittingEmptySubsequences: false)}
        let alphabet = ss.first!.dropFirst().map {String($0)}
        let alphabetIndexesToDrop = Set(alphabet.lazy.enumerated().map({(count: $0.element.count, index: $0.offset)}).filter({$0.count > 1}).map({$0.index}))
        self.names = ss.dropFirst().map {String($0.first!)}
        let mstates = ss.lazy.dropFirst().map({$0.dropFirst()}).enumerated().flatMap({ (arg) -> State<String> in
            let (j, inp) = arg
            var sss: [String: Operation<String>] = [:]
            for (i, cs) in inp.lazy.enumerated().filter({$0.element != ""}).filter({!alphabetIndexesToDrop.contains($0.offset)}) {
                if cs == "halt" {
                    sss[alphabet[i]] = Operation(place: alphabet[i], move: Direction.stay, next: .self)
                    continue
                }
                let opp = cs.split(separator: " ")
                let foo = String(opp[2]) == names[j]
                let nnext: NextState = foo ? .self : .other(names.index(of: String(opp[2]))!)
                sss[alphabet[i]] = Operation(place: String(opp[0]), move: Direction(rawValue: Character.init(String(opp[1])))!, next: nnext)
            }
            return State(name: names[j], operations: sss)
        })
        self.states = mstates as! [State<A>]
    }
    func consume(states inStates: [[A: Operation<A>]?]) {
        states = inStates.enumerated().flatMap({ (i, s) in
            if let s = s{
                return State.init(name: self.names[i], operations: s)
            }
            return nil
        })
    }
    
    func description(`for` alphabet: [A]) -> String {
        let alphabet = Array(alphabet.shuffled())
        var out = [alphabet.map {$0.description()}.reduce("Q/A") {$0 + "\t\($1)"}]
        out.append((states.first?.description(alphabet: alphabet, names: self.names))!)
        out += states.dropFirst().shuffled().map {$0.description(alphabet: alphabet, names: self.names)}
        return out.reduce("") {$0 + "\n" + $1}
    }
    
    enum TuringResult {
        case loop
        case result([A])
    }
 }

 struct State<A: Hashable & Descriptable> {
    let name: String
    let operations: [A:Operation<A>]
    func description(alphabet: [A], names: [String]) -> String {
        return alphabet.lazy.map {self.operations[$0]?.description(selfName: self.name, names: names) ?? ""}
            .reduce(name) {"\($0)\t\($1)"}
    }
 }

 enum Direction: Character {
    case left = "l"
    case right = "r"
    case stay = "n"
 }

 class Operation<A: Hashable & Descriptable & Equatable>: Equatable {
    static func ==(lhs: Operation<A>, rhs: Operation<A>) -> Bool {
        return lhs.place == rhs.place && lhs.move == rhs.move && lhs.nextState == rhs.nextState
    }
    
    func replace(_ i: Int, with j: Int) {
        if nextState == .other(i) {
            nextState = .other(j)
        }
    }
    
    let place: A
    let move: Direction
    var nextState: NextState
    func description(selfName: String, names: [String]) -> String {
        return "\(place.description()) \(move.rawValue) \(nextState.description(selfName: selfName, names: names))"
    }
    
    init(place: A, move: Direction, next: NextState) {
        self.place = place
        self.move = move
        self.nextState = next
    }
 }

 enum NextState: Equatable {
    static func ==(lhs: NextState, rhs: NextState) -> Bool {
        switch lhs {
        case .self:
            switch rhs {
            case .self:
                return true
            default:
                return false
            }
        case .other(let n):
            switch rhs {
            case .other(let m):
                return m == n
            default:
                return false
            }
        }
    }
    
    case `self`
    case other(Int)
    func description(selfName: String, names: [String]) -> String {
        switch self {
        case .self:
            return selfName
        case .other(let s):
            return names[s]
        }
    }
 }

 enum Alphabet: Descriptable {
    static var aChar: Character = "a"
    
    func description() -> String {
        switch self {
        case .zero:
            return "0"
        case .one:
            return "1"
        case .a:
            return String(Alphabet.aChar)
        case .none:
            return "_"
        case .star:
            return "*"
        }
    }
    
    case zero
    case one
    case a
    case star
    case none
 }

 extension MutableCollection {
    /// Shuffles the contents of this collection.
    mutating func shuffle() {
        let c = count
        guard c > 1 else { return }
        
        for (firstUnshuffled, unshuffledCount) in zip(indices, stride(from: c, to: 1, by: -1)) {
            let d: IndexDistance = numericCast(arc4random_uniform(numericCast(unshuffledCount)))
            let i = index(firstUnshuffled, offsetBy: d)
            swapAt(firstUnshuffled, i)
        }
    }
 }
 extension Sequence {
    /// Returns an array with the contents of this sequence, shuffled.
    func shuffled() -> [Element] {
        var result = Array(self)
        result.shuffle()
        return result
    }
 }


 var input: String?
 var output = "output.txt"

 let args = Array(CommandLine.arguments.dropFirst())

 var i = 0
 while i < args.count {
    switch args[i] {
    case "-i":
        if i + 1 < args.count {
            i += 1
            input = args[i]
        }
    case "-o":
        if i + 1 < args.count {
            i += 1
            output = args[i]
        }
    default:
        print("I don't know what you are trying to do...\nBut I am still going to try my best.")
    }
    i += 1
 }

 if input == nil {
    print("You did not provide an input path")
    exit(0)
 }

 #if os(Linux)
    let inp = readStringFromFile(path: input!)
    #else

 guard let inp = try? String.init(contentsOf: URL.init(fileURLWithPath: input!)) else {
    print("Something is wrong with the input path")
    exit(0)
 }
    #endif
    
 let turing = TuringMachine<String>(from: inp)


 let post = PostMachine.init(from: turing)
 post.optimize()

 #if os(Linux)
 if !(post.alphabet.reduce("") {$0 + "\($1.key) - \($1.value)\n"} + "\n---\n\n" + post.description()).write(toFile: output) {
    print("Wasn't able to write file...")
    exit(0)
 }
 #else
 do {
    try (post.alphabet.reduce("") {$0 + "\($1.key) - \($1.value)\n"} + "\n---\n\n" + post.description()).write(to: URL.init(fileURLWithPath: output), atomically: true, encoding: .utf8)
 } catch {
    print("Wasn't able to write file...")
    exit(0)
 }
 #endif
	import Foundation
	#if os(Linux)
	import SwiftGlibc

	SwiftGlibc.srandom(UInt32(time(nil)))

	public func arc4random_uniform(_ max: UInt32) -> Int32 {
	return (SwiftGlibc.rand() % Int32(max-1))
	}
	#endif

	func stringFromBytes(bytes: UnsafeMutablePointer<UInt8>, count: Int) -> String {
	return String((0..<count).map ({Character(UnicodeScalar(bytes[$0]))}))
	}
	func readStringFromFile(path: String) -> String {
	let fp = fopen(path, "r"); defer {fclose(fp)}
	var outputString = ""
	let chunkSize = 1024
	let buffer: UnsafeMutablePointer<UInt8> = UnsafeMutablePointer.allocate(capacity: chunkSize); defer {buffer.deallocate(capacity: chunkSize)}
	repeat {
	let count: Int = fread(buffer, 1, chunkSize, fp)
	guard ferror(fp) == 0 else {break}
	if count > 0 {
	outputString += stringFromBytes(bytes: buffer, count: count)
	}
	} while feof(fp) == 0

	return outputString
	}

	extension String {
	func write(toFile path: String) -> Bool {
	let fp = fopen(path, "w"); defer {fclose(fp)}
	var byteArray: [UInt8] = self.utf8.map {$0}
	let count = fwrite(&byteArray, 1, byteArray.count, fp)
	return count == self.utf8.count
	}
	}

	protocol Descriptable {
	func description() -> String
	}
	extension Int {
	var toArray: [Bool] {
	if self == 0 {
	return [false]
	} else {
	var outp: [Bool] = []
	var temp = self
	while temp > 0 {
	outp.append(temp & 1 == 1)
	temp = temp >> 1
	}
	return Array(outp.reversed())
	}
	}
	func toArray(paddingTo: Int) -> [Bool] {
	let out = self.toArray
	let foo = paddingTo - out.count
	let count = foo > 0 ? foo : 0
	return Array(repeatElement(false, count: count)) + out
	}
	}

	extension Array {
	var permuatations: [[Element]] {
	var out: [[Element]] = []
	for (i, c) in self.enumerated() {
	var b = self
	b.remove(at: i)
	out += b.permuatations.map {[c] + $0}
	}
	return out.count == 0 ? [[]] : out
	}
	}

	class PostMachine {
	var alphabet: [String: String] = [:]
	var states: [PostState] = []
	func description() -> String {
	var outp = ""
	for (i, state) in states.enumerated() {
	outp.append("\(i + 1). ")
	switch state {
	case .clear(let next, let s):
	outp.append("[X][\(next)][\(s ?? "")]")
	case .condition(let zero, let one, let s):
	outp.append("[?][\(zero),\(one)][\(s ?? "")]")
	case .left(let next, let s):
	outp.append("[<][\(next)][\(s ?? "")]")
	case .mark(let next, let s):
	outp.append("[V][\(next)][\(s ?? "")]")
	case .right(let next, let s):
	outp.append("[>][\(next)][\(s ?? "")]")
	case .stop(let s):
	outp.append("[S][][\(s ?? "")]")
	}
	outp.append("\n")
	}
	return outp
	}

	func optimize() {
	var didChange = true
	large: while didChange {
	didChange = false
	for (var i, state) in states.enumerated() {
	switch state {
	case .condition(var l, let r, _):
	if l == r {
	didChange = true
	states.remove(at: i)
	i += 1
	if l > i {
	l -= 1
	}
	for (j, lstate) in states.enumerated() {
	switch lstate {
	case .clear(let m, let s2):
	if m == i {
	states[j] = .clear(l, s2)
	} else if m > i {
	states[j] = .clear(m - 1, s2)
	}
	case .condition(var m1, var m2, let s2):
	if m1 == i {
	m1 = l
	} else if m1 > i {
	m1 -= 1
	}
	if m2 == i {
	m2 = l
	} else if m2 > i {
	m2 -= 1
	}
	states[j] = .condition(m1, m2, s2)
	case .left(let m, let s2):
	if m == i {
	states[j] = .left(l, s2)
	} else if m > i {
	states[j] = .left(m - 1, s2)
	}
	case .mark(let m, let s2):
	if m == i {
	states[j] = .mark(l, s2)
	} else if m > i {
	states[j] = .mark(m - 1, s2)
	}
	case .right(let m, let s2):
	if m == i {
	states[j] = .right(l, s2)
	} else if m > i {
	states[j] = .right(m - 1, s2)
	}
	case .stop(_):
	break
	}
	}
	continue large
	}
	default:
	break
	}
	for (var n, nstate) in states.enumerated().dropFirst(i + 1) {
	if state == nstate {
	// print("match\t\(state)\t\(nstate)")
	didChange = true
	states.remove(at: n)
	n += 1
	i += 1
	for (j, lstate) in states.enumerated() {
	switch lstate {
	case .clear(let m, let s):
	if m == n {
	states[j] = .clear(i, s)
	} else if m > n {
	states[j] = .clear(m - 1, s)
	}
	case .condition(var m1, var m2, let s):
	if m1 == n {
	m1 = i
	} else if m1 > n {
	m1 -= 1
	}
	if m2 == n {
	m2 = i
	} else if m2 > n {
	m2 -= 1
	}
	states[j] = .condition(m1, m2, s)
	case .left(let m, let s):
	if m == n {
	states[j] = .left(i, s)
	} else if m > n {
	states[j] = .left(m - 1, s)
	}
	case .mark(let m, let s):
	if m == n {
	states[j] = .mark(i, s)
	} else if m > n {
	states[j] = .mark(m - 1, s)
	}
	case .right(let m, let s):
	if m == n {
	states[j] = .right(i, s)
	} else if m > n {
	states[j] = .right(m - 1, s)
	}
	case .stop:
	break
	}
	}
	continue large
	}
	}
	}
	}
	}

	private enum Placeholder {
	case normal(PostState)
	case left(String, comment: String?)
	case right(String, comment: String?)
	case mark(String, comment: String?)
	case clear(String, comment: String?)
	case condition(String, String, comment: String?)
	mutating func move(to state: Int) {
	switch self {
	case .normal(let s):
	switch s {
	case .clear(_, let s):
	self = .normal(.clear(state, s))
	case .condition(_, _, _):
	fatalError()
	case .left(_, let s):
	self = .normal(.left(state, s))
	case .mark(_, let s):
	self = .normal(.mark(state, s))
	case .right(_, let s):
	self = .normal(.right(state, s))
	case .stop(let s):
	self = .normal(.stop(s))
	}
	default:
	fatalError("This shouldn't be")
	}
	}
	mutating func move(to state: String) {
	switch self {
	case .normal(let s):
	switch s {
	case .clear(_, let s):
	self = .clear(state, comment: s)
	case .condition(_, _, _):
	fatalError("This really shouyldn't happen either")
	case .left(_, let s):
	self = .left(state, comment: s)
	case .mark(_, let s):
	self = .mark(state, comment: s)
	case .right(_, let s):
	self = .right(state, comment: s)
	case .stop(let s):
	self = .normal(.stop(s))
	}
	default:
	fatalError("This really shouldn't happen")
	}
	}
	func dePlacehold(replacements: [String: Int]) -> PostState {
	switch self {
	case .normal(let ps):
	return ps
	case .clear(let s, let c):
	return .clear(replacements[s]!, c)
	case .condition(let s1, let s2, let c):
	return .condition(replacements[s1]!, replacements[s2]!, c)
	case .left(let s, let c):
	return .left(replacements[s]!, c)
	case .mark(let s, let c):
	return .mark(replacements[s]!, c)
	case .right(let s, let c):
	return .right(replacements[s]!, c)
	}
	}
	}
	private struct Binary {
	private let value: Int
	init(value: Int) {
	self.value = value
	}
	/// true if 1
	/// false if 0
	subscript(place: Int) -> Bool {
	return value & (1 << place) != 0
	}
	}

	init<A>(from turing: TuringMachine<A>) {
	// let states = Array(0..<5).permuatations.map {PostMachine.init(from: turing, with: $0).states}
	// let state = states.sorted(by: {$0.count < $1.count}).map {$0.count}
	// print(state)
	let foo = PostMachine.init(from: turing, with: Array(1..<8))
	self.states = foo.states
	self.alphabet = foo.alphabet
	}

	private init<A>(from turing: TuringMachine<A>, with bins: [Int]) {
	var alphabet: [A: [Bool]] = [:]
	var backAlphabet: [Int: A] = [:]
	zip(bins, Set(turing.states.reduce([]) {$0 + $1.operations.keys}).shuffled().filter({$0 as! String != "_"})).forEach { (i, n) in
	alphabet[n] = i.toArray(paddingTo: 3) //Binary(value: i)
	backAlphabet[i] = n
	}
	alphabet["_" as! A] = 0.toArray(paddingTo: 3)
	backAlphabet[0] = "_" as? A
	for (k, v) in alphabet {
	self.alphabet[k.description()] = v.reduce("") {$0 + ($1 ? "1" : "0")}
	}
	// print(bins.map {$0.toArray(paddingTo: 3)})
	var i = 1
	var futureStates: [Placeholder] = []
	var replacements: [String: Int] = [:]



	for state in turing.states {
	// print(state)
	let operations = state.operations
	// print(operations)
	var j = 0
	let order = backAlphabet.keys.lazy.filter({state.operations[backAlphabet[$0]!] != nil}).sorted().map {(bin: $0.toArray(paddingTo: 3), value: backAlphabet[$0]!)}
	replacements[state.name] = i
	// print(order)
	// print(state)
	func step(order: [(bin: [Bool], value: A)], movedSoFar: Int) {

	// print(order)
	if order.count == 0 {
	print("Something has gone terribly wrong...\nI am going to continue, but I will likely hang, crash or the result will be wrong...\nMost likely cause: you replaced tabs with spaces in the input file")
	}
	if order.count == 1 {
	let char = order.first!.value
	// print(char)
	let op = operations[char]!
	if op.move == .stay && op.nextState == .self && op.place == char {
	for _ in 0..<movedSoFar {/// added later see if works
	futureStates.append(.normal(.left(i + j + 1, state.name)))
	j += 1
	}
	futureStates.append(.normal(.stop(state.name)))
	j += 1
	return
	}
	var isOnTheLeft = false
	if op.place != char {
	for _ in movedSoFar..<2 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	}
	for bit in zip(alphabet[char]!, alphabet[op.place]!).map({$0 == $1 ? nil : $1}).reversed() {
	// for bit in alphabet[char]!.reversed() {
	if let bit = bit {
	if bit {
	futureStates.append(.normal(.mark(i + j + 1, state.name)))
	} else {
	futureStates.append(.normal(.clear(i + j + 1, state.name)))
	}
	j += 1
	}
	futureStates.append(.normal(.left(i + j + 1, state.name)))
	j += 1
	}
	isOnTheLeft = true
	j -= 1
	futureStates.removeLast()
	}
	switch op.move {
	case .stay:
	if !isOnTheLeft {
	for _ in 0..<movedSoFar {
	futureStates.append(.normal(.left(i + j + 1, state.name)))
	j += 1
	}
	}
	case .left:
	if !isOnTheLeft {
	for _ in 0..<movedSoFar {
	futureStates.append(.normal(.left(i + j + 1, state.name)))
	j += 1
	}
	}
	for _ in 0..<3 {
	futureStates.append(.normal(.left(i + j + 1, state.name)))
	j += 1
	}
	case .right:
	if isOnTheLeft {
	for _ in 0..<3 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	}
	} else {
	for _ in movedSoFar..<3 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	}
	}
	}
	switch op.nextState {
	case .self:
	futureStates[futureStates.count - 1].move(to: state.name)
	case .other(let ns):
	futureStates[futureStates.count - 1].move(to: turing.names[ns])
	}
	} else {


	let fs = order.filter {$0.bin.first == false}
	let ts = order.filter {$0.bin.first == true}

	if fs.count == 0 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	step(order: ts.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))
	} else if ts.count == 0 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	// print("FS\t\t\(fs)")
	step(order: fs.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))
	} else {
	let sj = j
	futureStates.append(.normal(.stop(state.name))) // Will change later on in code

	j += 1

	// Dealing with fs
	let fsj = j
	if movedSoFar < 2 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	}
	// print(order, movedSoFar)

	step(order: fs.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))

	// Dealing with ts
	let tsj = j
	if movedSoFar < 2 {
	futureStates.append(.normal(.right(i + j + 1, state.name)))
	j += 1
	}

	step(order: ts.map {(bin: Array($0.bin.dropFirst()), value: $0.value)}, movedSoFar: min(2, movedSoFar + 1))

	// Changing

	futureStates[i + sj - 1] = .normal(.condition(i + fsj, i + tsj, state.name))

	}
	}
	}

	step(order: order, movedSoFar: 0)

	i += j
	}

	self.states = futureStates.map {$0.dePlacehold(replacements: replacements)}

	}
	}

	enum PostState: Equatable {
	static func ==(lhs: PostState, rhs: PostState) -> Bool {
	switch lhs {
	case .clear(let i, _):
	switch rhs {
	case .clear(let j, _):
	return i == j
	default:
	return false
	}
	case .condition(let i1, let i2, _):
	switch rhs {
	case .condition(let j1, let j2, _):
	return i1 == j1 && i2 == j2
	default:
	return false
	}
	case .left(let i, _):
	switch rhs {
	case .left(let j, _):
	return i == j
	default:
	return false
	}
	case .mark(let i, _):
	switch rhs {
	case .mark(let j, _):
	return i == j
	default:
	return false
	}
	case .right(let i, _):
	switch rhs {
	case .right(let j, _):
	return i == j
	default:
	return false
	}
	case .stop(_):
	switch rhs {
	case .stop(_):
	return true
	default:
	return false
	}
	}
	}

	case left(Int, String?)
	case right(Int, String?)
	case mark(Int, String?)
	case clear(Int, String?)
	case condition(Int, Int, String?)
	case stop(String?)
	}

	extension String: Descriptable {
	func description() -> String {
	return self
	}
	}

	class TuringMachine<A: Hashable & Descriptable> {
	let names: [String]
	var states: [State<A>] = []
	init(names: [String]) {
	self.names = names
	}
	init(from s: String) {
	let ss = String(s.map({$0 == "\r\n" ? "\n" : $0})).split(separator: "\n").map {$0.split(separator: "\t", omittingEmptySubsequences: false)}
	let alphabet = ss.first!.dropFirst().map {String($0)}
	let alphabetIndexesToDrop = Set(alphabet.lazy.enumerated().map({(count: $0.element.count, index: $0.offset)}).filter({$0.count > 1}).map({$0.index}))
	self.names = ss.dropFirst().map {String($0.first!)}
	let mstates = ss.lazy.dropFirst().map({$0.dropFirst()}).enumerated().flatMap({ (arg) -> State<String> in
	let (j, inp) = arg
	var sss: [String: Operation<String>] = [:]
	for (i, cs) in inp.lazy.enumerated().filter({$0.element != ""}).filter({!alphabetIndexesToDrop.contains($0.offset)}) {
	if cs == "halt" {
	sss[alphabet[i]] = Operation(place: alphabet[i], move: Direction.stay, next: .self)
	continue
	}
	let opp = cs.split(separator: " ")
	let foo = String(opp[2]) == names[j]
	let nnext: NextState = foo ? .self : .other(names.index(of: String(opp[2]))!)
	sss[alphabet[i]] = Operation(place: String(opp[0]), move: Direction(rawValue: Character.init(String(opp[1])))!, next: nnext)
	}
	return State(name: names[j], operations: sss)
	})
	self.states = mstates as! [State<A>]
	}
	func consume(states inStates: [[A: Operation<A>]?]) {
	states = inStates.enumerated().flatMap({ (i, s) in
	if let s = s{
	return State.init(name: self.names[i], operations: s)
	}
	return nil
	})
	}

	func description(`for` alphabet: [A]) -> String {
	let alphabet = Array(alphabet.shuffled())
	var out = [alphabet.map {$0.description()}.reduce("Q/A") {$0 + "\t\($1)"}]
	out.append((states.first?.description(alphabet: alphabet, names: self.names))!)
	out += states.dropFirst().shuffled().map {$0.description(alphabet: alphabet, names: self.names)}
	return out.reduce("") {$0 + "\n" + $1}
	}

	enum TuringResult {
	case loop
	case result([A])
	}
	}

	struct State<A: Hashable & Descriptable> {
	let name: String
	let operations: [A:Operation<A>]
	func description(alphabet: [A], names: [String]) -> String {
	return alphabet.lazy.map {self.operations[$0]?.description(selfName: self.name, names: names) ?? ""}
	.reduce(name) {"\($0)\t\($1)"}
	}
	}

	enum Direction: Character {
	case left = "l"
	case right = "r"
	case stay = "n"
	}

	class Operation<A: Hashable & Descriptable & Equatable>: Equatable {
	static func ==(lhs: Operation<A>, rhs: Operation<A>) -> Bool {
	return lhs.place == rhs.place && lhs.move == rhs.move && lhs.nextState == rhs.nextState
	}

	func replace(_ i: Int, with j: Int) {
	if nextState == .other(i) {
	nextState = .other(j)
	}
	}

	let place: A
	let move: Direction
	var nextState: NextState
	func description(selfName: String, names: [String]) -> String {
	return "\(place.description()) \(move.rawValue) \(nextState.description(selfName: selfName, names: names))"
	}

	init(place: A, move: Direction, next: NextState) {
	self.place = place
	self.move = move
	self.nextState = next
	}
	}

	enum NextState: Equatable {
	static func ==(lhs: NextState, rhs: NextState) -> Bool {
	switch lhs {
	case .self:
	switch rhs {
	case .self:
	return true
	default:
	return false
	}
	case .other(let n):
	switch rhs {
	case .other(let m):
	return m == n
	default:
	return false
	}
	}
	}

	case `self`
	case other(Int)
	func description(selfName: String, names: [String]) -> String {
	switch self {
	case .self:
	return selfName
	case .other(let s):
	return names[s]
	}
	}
	}

	enum Alphabet: Descriptable {
	static var aChar: Character = "a"

	func description() -> String {
	switch self {
	case .zero:
	return "0"
	case .one:
	return "1"
	case .a:
	return String(Alphabet.aChar)
	case .none:
	return "_"
	case .star:
	return "*"
	}
	}

	case zero
	case one
	case a
	case star
	case none
	}

	extension MutableCollection {
	/// Shuffles the contents of this collection.
	mutating func shuffle() {
	let c = count
	guard c > 1 else { return }

	for (firstUnshuffled, unshuffledCount) in zip(indices, stride(from: c, to: 1, by: -1)) {
	let d: IndexDistance = numericCast(arc4random_uniform(numericCast(unshuffledCount)))
	let i = index(firstUnshuffled, offsetBy: d)
	swapAt(firstUnshuffled, i)
	}
	}
	}
	extension Sequence {
	/// Returns an array with the contents of this sequence, shuffled.
	func shuffled() -> [Element] {
	var result = Array(self)
	result.shuffle()
	return result
	}
	}


	var input: String?
	var output = "output.txt"

	let args = Array(CommandLine.arguments.dropFirst())

	var i = 0
	while i < args.count {
	switch args[i] {
	case "-i":
	if i + 1 < args.count {
	i += 1
	input = args[i]
	}
	case "-o":
	if i + 1 < args.count {
	i += 1
	output = args[i]
	}
	default:
	print("I don't know what you are trying to do...\nBut I am still going to try my best.")
	}
	i += 1
	}

	if input == nil {
	print("You did not provide an input path")
	exit(0)
	}

	#if os(Linux)
	let inp = readStringFromFile(path: input!)
	#else

	guard let inp = try? String.init(contentsOf: URL.init(fileURLWithPath: input!)) else {
	print("Something is wrong with the input path")
	exit(0)
	}
	#endif

	let turing = TuringMachine<String>(from: inp)


	let post = PostMachine.init(from: turing)
	post.optimize()

	#if os(Linux)
	if !(post.alphabet.reduce("") {$0 + "\($1.key) - \($1.value)\n"} + "\n---\n\n" + post.description()).write(toFile: output) {
	print("Wasn't able to write file...")
	exit(0)
	}
	#else
	do {
	try (post.alphabet.reduce("") {$0 + "\($1.key) - \($1.value)\n"} + "\n---\n\n" + post.description()).write(to: URL.init(fileURLWithPath: output), atomically: true, encoding: .utf8)
	} catch {
	print("Wasn't able to write file...")
	exit(0)
	}
	#endif