Skip to content

Instantly share code, notes, and snippets.

@ilyakooo0
Created January 20, 2018 19:55
Show Gist options
  • Save ilyakooo0/8a8e80cb182457c2d953b441e327eb87 to your computer and use it in GitHub Desktop.
Save ilyakooo0/8a8e80cb182457c2d953b441e327eb87 to your computer and use it in GitHub Desktop.
iko.soy/diskra/DZ2
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