Created
January 20, 2018 19:55
-
-
Save ilyakooo0/8a8e80cb182457c2d953b441e327eb87 to your computer and use it in GitHub Desktop.
iko.soy/diskra/DZ2
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 | |
#if os(Linux) | |
import SwiftGlibc | |
SwiftGlibc.srandom(UInt32(time(nil))) | |
public func arc4random_uniform(_ max: UInt32) -> Int32 { | |
return (SwiftGlibc.rand() % Int32(max-1)) | |
} | |
#endif | |
extension String { | |
var binInt: Int { | |
return self == "0" ? 0 : 1 | |
} | |
} | |
class Tester { | |
private let turing: TuringMachine<String> | |
private var function: [Int: String] = [:] | |
init(turing: TuringMachine<String>, function: [String]) { | |
self.turing = turing | |
for (k, v) in function.enumerated() { | |
self.function[k] = v | |
} | |
} | |
enum TestResult { | |
case passed | |
case loop | |
case failed(expected: [String], got: [String]) | |
} | |
func test(input: [String],a inA: [String], b inB: [String], c inC: [String]) -> TestResult { | |
var expected: [String] = [] | |
var a = inA | |
var b = inB | |
var c = inC | |
while a.count > 0 || b.count > 0 || c.count > 0 { | |
let aa = a.popLast()?.binInt ?? 0 | |
let bb = b.popLast()?.binInt ?? 0 | |
let cc = c.popLast()?.binInt ?? 0 | |
let i = (aa << 2) + (bb << 1) + cc | |
expected.append(function[i]!) | |
} | |
expected = Array(expected.reversed()) | |
switch turing.run(with: input) { | |
case .loop: | |
return .loop | |
case .result(let res): | |
if res == expected { | |
// print(expected.joined()) | |
return .passed | |
} else { | |
return .failed(expected: expected, got: res) | |
} | |
} | |
} | |
} | |
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 | |
} | |
} | |
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 | |
} | |
class TuringMachine<A: Hashable & Descriptable & Alphabet> { | |
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]) | |
} | |
var maxNumberOfIterations = 10000000 | |
func run(with input: [A]) -> TuringResult { | |
var tape = Tape(with: input) | |
var currentState = 0 | |
for _ in 0...maxNumberOfIterations { | |
let state = states[currentState] | |
let operation = state.operations[tape.value]! | |
if operation.move == .stay && operation.nextState == .self && operation.place == tape.value { | |
return .result(tape.result) | |
} | |
tape.value = operation.place | |
tape.move(operation.move) | |
switch operation.nextState { | |
case .other(let i): | |
currentState = i | |
case .self: | |
break | |
} | |
} | |
return .loop | |
} | |
} | |
protocol Alphabet { | |
static var empty: Self {get} | |
var isEmpty: Bool {get} | |
} | |
extension String: Alphabet { | |
static var empty: String { | |
return "_" | |
} | |
var isEmpty: Bool { | |
return self == String.empty | |
} | |
} | |
extension Character: Alphabet { | |
static var empty: Character { | |
return "_" | |
} | |
var isEmpty: Bool { | |
return self == Character.empty | |
} | |
} | |
struct Tape<A> where A: Alphabet { | |
var line: [A] = [] | |
init(with input: [A]) { | |
self.line = input | |
} | |
private var index = 0 | |
mutating func move(_ direction: Direction) { | |
switch direction { | |
case .left: | |
index -= 1 | |
case .right: | |
index += 1 | |
case .stay: | |
break | |
} | |
} | |
var value: A { | |
get { | |
if index < 0 || index >= line.count { | |
return A.empty | |
} else { | |
return line[index] | |
} | |
} | |
set { | |
if index < 0 { | |
line = [newValue] + (1..<(-index)).map {_ in A.empty} + line | |
index = 0 | |
} else if index >= line.count { | |
line += (0..<(index - line.count)).map {_ in A.empty} + [newValue] | |
index = line.count - 1 | |
} else { | |
line[index] = newValue | |
} | |
} | |
} | |
var result: [A] { | |
return Array(line.lazy.drop(while: {$0.isEmpty}).reversed().drop(while: {$0.isEmpty}).reversed()) | |
} | |
} | |
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" | |
} | |
extension String: Descriptable { | |
func description() -> String { | |
return self | |
} | |
} | |
protocol Descriptable { | |
func description() -> String | |
} | |
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] | |
} | |
} | |
} | |
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 | |
} | |
} | |
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? | |
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] | |
} | |
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) | |
print("Please enter your function values F(0,0,0) F(0,0,1) ... F(1,1,1): ", separator: "", terminator: "") | |
if let input = readLine(strippingNewline: true) { | |
let onesAndZeros = input.filter({$0 == "0" || $0 == "1"}) | |
if onesAndZeros.count != 8 { | |
print("Honestly, I was expecting 8 values...") | |
exit(0) | |
} | |
let tester = Tester(turing: turing, function: onesAndZeros.map {String($0)}) | |
let maxNumberOfBits = 9 | |
let maxNumber = 1 << (maxNumberOfBits * 3) | |
func process(result: Tester.TestResult, with input: [String]) { | |
switch result { | |
case .passed: | |
// print("\(input.joined())\t ok") | |
break | |
case .loop: | |
print("Looped on input:\t \(input.joined())") | |
exit(0) | |
case .failed(expected: let expexted, got: let got): | |
print("Failed on:\t \(input.joined())\t Expected:\t \(expexted.joined())\t Got:\t \(got.joined())") | |
exit(0) | |
} | |
} | |
let max = Double(maxNumber) | |
process(result: tester.test(input: ["*", "*"], a: ["0"], b: ["0"], c: ["0"]), with: ["*", "*"]) | |
for i in 0..<maxNumber { | |
let a = i & ((1 << maxNumberOfBits) - 1) | |
let b = (i >> maxNumberOfBits) & ((1 << maxNumberOfBits) - 1) | |
let c = (i >> (maxNumberOfBits * 2)) & ((1 << maxNumberOfBits) - 1) | |
let aa = a.toArray.map({$0 ? "1" : "0"}) | |
let bb = b.toArray.map({$0 ? "1" : "0"}) | |
let cc = c.toArray.map({$0 ? "1" : "0"}) | |
for ai in 0...2 { | |
for bi in 0...2 { | |
for ci in 0...2 { | |
let az = Array(repeatElement("0", count: ai)) + aa | |
let bz = Array(repeatElement("0", count: bi)) + bb | |
let cz = Array(repeatElement("0", count: ci)) + cc | |
let input = az + ["*"] + bz + ["*"] + cz | |
process(result: tester.test(input: input, a: az, b: bz, c: cz), with: input) | |
} | |
} | |
} | |
if i % 10000 == 0 { | |
print(Double(i) * 100 / max, "%") | |
} | |
} | |
print("You seem to be fine...") | |
} else { | |
print("¯\\_(ツ)_/¯") | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment