Trapped Knight

trapped_knight.jl

# ulam spiral
using Crayons.Box

knight_deltas = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
function main()
    width, height = 5,5
    for y in height:-1:-height
        for x in -width:width
            #print("(", x, ",", y, ")")
            quarter = ulam_quarter(x, y)
            color = BLACK_FG

            if quarter == -1
                color = GREEN_FG
            elseif quarter == -2
                color = BLUE_FG
            elseif quarter == -3
                color = RED_FG
            elseif quarter == -4
                color = YELLOW_FG
            end

            print(color, lpad(ulam_map(x, y), 3, " "), " ")
        end
        println()
    end

    println(WHITE_FG)

    visited = Set(1)
    ordered = Int16[]
    push!(ordered, 1)
    pos = (0,0)
    val = 1

    while val > 0
        pos, val = next_move(pos, visited)
        push!(visited, val)
        push!(ordered, val)
    end

    println(ordered[end-1])
end


function next_move(pos, visited)
    moves = Dict()
    for delta in knight_deltas
        move = pos .+ delta
        val = ulam_map(move...)
        if !in(val, visited)
            moves[val] = move
        end
    end

    if length(moves) > 0
        min_val = reduce((x, y) -> x ≤ y ? x : y, keys(moves))
        min_move = moves[min_val]
        return (min_move, min_val)
    else
        return ((0,0), -1)
    end
end

function ulam_map(x, y)
    if x == y == 0
        # Center, sorry it's an outlier :/
        return 1
    elseif -x < y <= x
        # Q1 -> NE
        n = abs(x)
        return 4n^2 - 2n + 1 - n + y
    elseif -y <= x < y
        # Q2 -> NW
        n = abs(y)
        return 4n^2 + 1 - n - x
    elseif x <= y < -x
        # Q3 -> SW
        n = abs(x)
        return 4n^2 + n + 1 - y
    elseif y < x <= -y
        # Q4 -> SE
        n = abs(y)
        return 4n^2 + 3n + 1 + x
    end
end


function ulam_quarter(x, y)
    if x == y == 0
        return 0
    end

    if -x < y <= x
        return -1

    elseif -y <= x < y
        return -2

    elseif x <= y < -x
        return -3

    elseif y < x <= -y
        return -4
    end
end


main()