Reverse Game of Life (Julia Version)

life.jl

b_north = 1<<0 + 1<<1 + 1<<2
b_south = 1<<6 + 1<<7 + 1<<8
b_ew = 1<<3 + 1<<4 + 1<<5  # line east-west
b_west = 1<<0 + 1<<3 + 1<<6
b_east = 1<<2 + 1<<5 + 1<<8
b_ns = 1<<1 + 1<<4 + 1<<7 # line north-south

neighbors(G, r, c) = G[r-1, c] + G[r-1, c-1] + G[r-1, c+1] + G[r+1, c] + G[r+1, c-1] + G[r+1, c+1] + G[r, c-1] + G[r, c+1]

function sim(G)
    H, W = size(G)
    F = fill(0, H, W)
    for r in 2:(H-1)
        for c in 2:(W-1)
            n = neighbors(G, r, c)
            F[r,c] = n == 3 || G[r,c] + n == 3
        end
    end
    return F
end

function disp(A::Matrix{Int}; border=true)
    H,W = size(A)
    if border
        println("."^W)
    end
    for r in 2:(H-1)
        if border
            print(".")
        end
        for c in 2:(W-1)
            print(" #"[A[r, c] + 1])
        end
        if border
            println(".")
        else
            println()
        end
    end
    if border
        println("."^W)
    end
end

function disp(A::Int; w=3)
    println("_"^(w+2))
    for r in 1:w
        print("|")
        for c in 1:w
            print(" #"[(A >> ((r-1)*3 + c - 1))&1 + 1])
        end
        println("|")
    end
    println("^"^(w+2))
end

function load_input(filename::String, pad=0)
    f = open(filename, "r")
    lines = readlines(f)
    H = length(lines) + 2 + 2*pad
    W = max(map(x->length(x), lines)...) + 2 + 2*pad

    G = fill(0, H, W)
    for r in 1:length(lines)
        for c in 1:length(lines[r])
            if lines[r][c] == '#'
                G[r+1+pad,c+1+pad] = 1
            end
        end
    end
    return G
end

function forward(filename::String)
    G = load_input(filename, 5)

    ccall(:jl_exit_on_sigint, Cvoid, (Cint,), 0)
    print("\033[2J\033[H") # Clear and home
    try
    for it in 1:20
        print("\033[H") # Move to home position
        disp(G)
        println("step = $it")
        sleep(0.5)
        G = sim(G)
    end
    catch ex
        if !(ex isa InterruptException)
            throw(ex)
        end
    end
end

function find_ancestors()
    global live, dead
    G = fill(0, 5, 5)
    live = Set{Int}()
    dead = Set{Int}()
    for i in 0:(1<<9-1)
        for r in 0:2
            for c in 0:2
                G[r+2, c+2] = (i >> (r*3 + c)) & 1
            end
        end
        F = sim(G)
        if F[3,3] == 1
            push!(live, i)
        else
            push!(dead, i)
        end
        # disp(G)
    end
end

function search(P)
    H, W = size(P)
    L = []
    for c in 2:(W-1)
        for r in 2:(H-1)
            push!(L, (r,c))
        end
    end
    S = fill(1, length(L))
    Q = fill(0, length(L))
    i = 1
    while i <= length(L)
        r,c = L[i]
        mask = value = 0
        if r > 2
            value = Q[i-1] >> 3
            mask = b_north | b_ew
        end
        if c > 2
            value |= (Q[i-H+2] >> 1) & (b_west | b_ns)
            mask |= b_west | b_ns
        end
        value &= mask
        while S[i] <= length(P[r,c])
            p = P[r,c][S[i]]
            if (p & mask) == value
                Q[i] = p
                break
            end
            S[i] += 1
        end
        if S[i] <= length(P[r,c])
            i += 1
        else
            S[i] = 1
            i -= 1
            if i == 0
                return nothing
            end
            S[i] += 1
        end
    end
    F = fill(0, H, W)
    for i in 1:length(L)
        F[L[i]...] = (Q[i] >> 4) & 1
    end
    return F
end

function bitmask(u, v)
    c = 0
    for x in -1:1
        for y in -1:1
            if -1 <= y+u  <= 1 && -1 <= x+v <= 1
                c += 1 << ((y+u+1)*3 + x+v+1)
            end
        end
    end
    return c
end

function cull(G::Matrix{Int}, P, H, W)
    mask = fill(0, 3, 3)
    for x in -1:1
        for y in -1:1
            mask[y+2, x+2] = bitmask(y, x)
        end
    end
    culled = 0
    for r in 2:(H-1)
        for c in 2:(W-1)
            if G[r,c] == 1
                continue
            end
            diff = Set{Int}()
            for p in P[r,c]
                for (u,v) in [(1,0), (-1,0), (0,1), (0,-1)]
                    if 2 <= r+u <= H-1 && 2 <= c+v <= W-1
                        if G[r+u, c+v] == 1 && count_ones(mask[u+2, v+2] & p) > 4
                            push!(diff, p)
                        end
                    end
                end
            end
            culled += length(diff)
            setdiff!(P[r,c], diff)
        end
    end
end

function reverse(filename::String)
    find_ancestors()
    # println("#live = $(length(live)) #dead = $(length(dead))")

    G = load_input(filename)
    H,W = size(G)
    # println("Board size: $H x $W")
    possible = fill(Set{Int}(), H, W)
    global live, dead
    for r in 2:(H-1)
        for c in 2:(W-1)
            if G[r,c] == 1
                possible[r,c] = copy(live)
            else
                possible[r,c] = copy(dead)
            end
        end
    end

    for r in 2:(H-1)
        diff = Set{Int}()
        for p in possible[r,2]
            if (p & b_west) != 0 || count_ones(p & b_ns) == 3
                push!(diff, p)
            end
        end
        setdiff!(possible[r,2], diff)
        diff = Set{Int}()
        for p in possible[r,W-1]
            if (p & b_east) != 0 || count_ones(p & b_ns) == 3
                push!(diff, p)
            end
        end
        setdiff!(possible[r,W-1], diff)
    end
    for c in 2:(W-1)
        diff = Set{Int}()
        for p in possible[2,c]
            if (p & b_north) != 0 || count_ones(p & b_ew) == 3
                push!(diff, p)
            end
        end
        setdiff!(possible[2,c], diff)
        diff = Set{Int}()
        for p in possible[H-1,c]
            if (p & b_south) != 0 || count_ones(p & b_ew) == 3
                push!(diff, p)
            end
        end
        setdiff!(possible[H-1,c], diff)
    end

    # NOTE: culling is buggy and leads to false positives
    # cull(G, possible, H, W)

    # display(map(x->length(x), possible))

    P = possible
    possible = fill([], size(P))
    for r in 1:H
        for c in 1:W
            possible[r,c] = sort(collect(P[r,c]), by=count_ones)
        end
    end

    F = search(possible)
    if !(F isa Nothing)
        disp(F)
    else
        println("No solution found!")
    end
end

function enum_big()
    G = fill(0, 6, 6)
    state = []
    for i in 1:1<<4
        push!(state, Set{Int}())
    end
    for i in 0:(1<<16-1)
        for r in 0:3
            for c in 0:3
                G[r+2, c+2] = (i >> (r*4 + c)) & 1
            end
        end
        F = sim(G)
        key = 1 + F[3,3] + (F[3,4] << 1) + (F[4,3] << 2) + (F[4,4] <<3)
        push!(state[key], i)
    end
    for key in 1:(1<<4)
        disp(key-1, w=2)
        println("state[$(key-1)] = $(length(state[key]))")
    end
end

mode = "forward"
filename = "forward.txt"
if length(ARGS) > 0
    mode = ARGS[1]
    filename = "reverse.txt"
end
if length(ARGS) > 1
    filename = ARGS[2]
end

if mode == "forward" || mode == "f"
    forward(filename)
elseif mode == "reverse" || mode == "r"
    @time reverse(filename)
else
    println("Unknown mode: $mode")
    enum_big()
end