local T = require('table')

-- All possible permutations of 4 points while keeping the last point constant
local perms = {
    {1,2,3,4},
    {2,1,3,4},
    {3,2,1,4},
    {2,3,1,4},
    {3,1,2,4},
    {1,3,2,4}
}

function sq_dist(pt1, pt2)
    -- Calculate the square distance between two points
    return ((pt1[1] - pt2[1]) ^ 2) + ((pt1[2] - pt2[2]) ^ 2);
end

function serialize_pt(pt)
    -- String representation of one point
    return '(' .. pt[1] .. ', ' .. pt[2] .. ')'
end

function serialize_pts(pts)
    -- String representation of the points
    local a, b, c, d = serialize_pt(pts[1]), serialize_pt(pts[2]), serialize_pt(pts[3]), serialize_pt(pts[4])
    return '[' .. a .. ', ' .. b .. ', ' .. c .. ', ' .. d .. ']'
end

function cmp_pt(pt1, pt2)
    -- Compare two points by first comparing their x and then y coordinates
    if pt1[1] < pt2[1] then
        return true
    elseif pt1[1] > pt2[1] then
        return false
    elseif pt1[2] < pt2[2] then
        return true
    elseif pt1[2] > pt2[2] then
        return false
    else
        return false
    end
end

function normalize_pts(pts)
    -- Converts the points such that the lower most point is the origin
    -- TODO: If the scaling is also controlled here, then we may end up with
    -- a finite set of permutations only? Unlikely.
    T.sort(pts, cmp_pt)

    local origin_x = pts[1][1]
    local origin_y = pts[1][2]

    for i = 1, #pts do
        pts[i][1] = pts[i][1] - origin_x
        pts[i][2] = pts[i][2] - origin_y
    end
end

function is_square(pts)
    -- Calculates if looking at the points in any order makes them a square
    for ii = 1, #perms do
        local perm = perms[ii]
        if sq_dist(pts[perm[1]], pts[perm[2]]) == sq_dist(pts[perm[2]], pts[perm[3]]) and
           sq_dist(pts[perm[2]], pts[perm[3]]) == sq_dist(pts[perm[3]], pts[perm[4]]) and
           sq_dist(pts[perm[3]], pts[perm[4]]) == sq_dist(pts[perm[4]], pts[perm[1]]) then
           return true
       end
    end

    return false
end

function copy_pts(pts)
    -- Copy points into a new table
    return {
        {pts[1][1], pts[1][2]},
        {pts[2][1], pts[2][2]},
        {pts[3][1], pts[3][2]},
        {pts[4][1], pts[4][2]}
    }
end

function reflect_all(pts)
    -- Creates all representations of pts created by mirroring them by 
    local all_results = {}

    for i = 1, #pts do
        for j = 1, #pts do
            if i ~= j then
                -- Mirror pts[i] through pts[j]
                local new_pts = copy_pts(pts)
                new_pts[i][1] = new_pts[j][1] + (new_pts[j][1] - new_pts[i][1])
                new_pts[i][2] = new_pts[j][2] + (new_pts[j][2] - new_pts[i][2])
                -- normalize the new point before returning it
                normalize_pts(new_pts)
                T.insert(all_results, {moves={source=i, mirror=j}, pts=new_pts})
            end
        end
    end

    return all_results
end

function serialize_moves(moves)
    -- Serializes moves as a sequence of mirrorings
    local moves_str = ''
    for i = 1, #moves do
        moves_str = moves_str .. '(' .. moves[i].source .. ' -> ' .. moves[i].mirror .. ') '
    end

    return moves_str
end


pts_seen = {}
pts_queue = {{moves={}, pts={{0, 0}, {0, 1}, {1, 0}, {1, 1}}}} -- The initial points are sorted.
iters = 0
square_found = nil

-- [[
while iters < 100000 and square_found == nil do
    iters = iters + 1
    state = pts_queue[iters]
    pts = state.pts
    pts_seen[serialize_pts(pts)] = true
    reflected_pts = reflect_all(pts)

    for i = 1, #reflected_pts do
        if pts_seen[serialize_pts(reflected_pts[i].pts)] == nil then
            -- If we haven't seen this reflected point before
            pts_seen[serialize_pts(reflected_pts[i].pts)] = true 
            
            -- Perform a BFS.
            local new_moves = {}
            for j = 1, #state.moves do
                T.insert(new_moves, state.moves[j])
            end
            T.insert(new_moves, reflected_pts[i].moves)

            if is_square(reflected_pts[i].pts) then
                square_found = {moves=new_moves, pts=reflected_pts[i].pts}
                print('Found another square: ' .. serialize_pts(square_found.pts))
                print('Moves needed: ' .. serialize_moves(square_found.moves))
                break
            else

                T.insert(pts_queue, {moves=new_moves, pts=reflected_pts[i].pts})
            end
        end

        if square_found ~= nil then
            break
        end
    end
end
--]]