|
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 |
|
--]] |
|
|