--[[
A Rubik's Cube simulator in Lua.
By Andrew Trevorrow (andrew@trevorrow.com), July 2020.

Credits:
The code in SolveCube is by Tom Rokicki -- thanks Tom!
http://cube20.org/

The code in RotateCube and RotatePoint is based on code in
"Macintosh Graphics in Modula-2" by Russell L. Schnapp.

Some of the code is from Daniel Shiffman's excellent video:
Coding Challenge #112: 3D Rendering with Rotation and Projection
https://youtu.be/p4Iz0XJY-Qk

The code in FillTriangle is based on this:
http://www-users.mat.uni.torun.pl/~wrona/3d_tutor/tri_fillers.html

The code in RotateFace is based on the info here:
https://en.wikipedia.org/wiki/Transformation_matrix#Rotation_2
--]]

local glu = glu()
local cv = canvas()
local gp = require "gplus"
local cp = require "cplus"
local cos = math.cos
local sin = math.sin
local min = math.min
local max = math.max
local rand = math.random
local unpack = table.unpack

local cvwd, cvht = 660, 500
local minwd, minht = 530, 400
local xo, yo                    -- center of cube
local scale                     -- used to adjust size of cube
local showtime = false          -- show frame time in status bar?
local autorotate = false        -- automatically rotate cube?
local animate = true            -- animate face rotations?
local disableprint = true       -- disable print calls in SolveCube?
local bg_color = cp.gray        -- viewport *and* canvas background
local leftgap = 150             -- space for buttons

-- buttons (see CreateButtons):
local exit_button
local help_button
local scramble_button
local solve_button
local reset_button
local undo_button
local redo_button
local fc_button, fa_button
local bc_button, ba_button
local uc_button, ua_button
local dc_button, da_button
local rc_button, ra_button
local lc_button, la_button

-- for undo/redo:
local undostack = {}    -- stack of moves that can be undone
local redostack = {}    -- stack of moves that can be redone
local savemove = true   -- save face rotation in undostack?

-- face colors:
local front_color = {255,128,0,255} -- orange
local back_color  = cp.red
local up_color    = cp.yellow
local down_color  = cp.white
local left_color  = cp.green
local right_color = cp.blue

-- sets for determining which vertex belongs to which face:
local front_vertex = {1,2,3,4}
local back_vertex  = {nil,nil,nil,nil,5,6,7,8}
local up_vertex    = {1,2,nil,nil,5,6}
local down_vertex  = {nil,nil,3,4,nil,nil,7,8}
local left_vertex  = {1,nil,nil,4,5,nil,nil,8}
local right_vertex = {nil,2,3,nil,nil,6,7}

-- info for each face will be stored in these tables:
local front_face = {}
local back_face  = {}
local up_face    = {}
local down_face  = {}
local left_face  = {}
local right_face = {}

local vertices = {}     -- array with vertices of cube
local rotx = {}         -- array with x coords of rotated vertices
local roty = {}         -- array with y coords of rotated vertices
local rotz = {}         -- array with z coords of rotated vertices
local prox = {}         -- array with x cooords of projected vertices
local proy = {}         -- array with y cooords of projected vertices

--------------------------------------------------------------------------------

function CreateCube()
    -- create 8 vertices of a 3x3x3 cube with center at 0,0,0
    -- (using a side length of 3 just makes it a bit easier to
    -- calculate the positions of lattice lines on each face)
    vertices[1] = {-1.5,  1.5,  1.5}
    vertices[2] = { 1.5,  1.5,  1.5}
    vertices[3] = { 1.5, -1.5,  1.5}
    vertices[4] = {-1.5, -1.5,  1.5}
    vertices[5] = {-1.5,  1.5, -1.5}
    vertices[6] = { 1.5,  1.5, -1.5}
    vertices[7] = { 1.5, -1.5, -1.5}
    vertices[8] = {-1.5, -1.5, -1.5}
    --[[
    WARNING: lots of other code assumes this cyclic vertex order:
    1,2,3,4 and 5,6,7,8 are front and back faces,
    1,5,6,2 and 4,8,7,3 are up and down faces,
    1,5,8,4 and 2,6,7,3 are left and right faces

                       +y
                        |
                  v5_________v6
                 /|         /|
                / |        / |
              v1_________v2  |
              |   |      |   |    -- +x
              |   v8_____|___v7
              |  /       |  /
              | /        | /
              v4_________v3

                   /
                 +z
    --]]
end

--------------------------------------------------------------------------------

function CreateFaces()
    front_face = CreateFace("f", 1,2,3,4, front_color)
    back_face  = CreateFace("b", 5,6,7,8, back_color)
    up_face    = CreateFace("u", 1,5,6,2, up_color)
    down_face  = CreateFace("d", 4,8,7,3, down_color)
    left_face  = CreateFace("l", 1,5,8,4, left_color)
    right_face = CreateFace("r", 2,6,7,3, right_color)
end

--------------------------------------------------------------------------------

function CreateFace(id, v1, v2, v3, v4, color)
    local face = {}
    face.corners = {v1, v2, v3, v4}

    -- colors will change when this face, or an adjacent face, is rotated
    face.colors = {
        {color, color, color},
        {color, color, color},
        {color, color, color}
    }
    
    -- calculate lattice points using vertices v1, v2 and v4
    -- (see the diagram in DrawFace)
    face.lattice = {}
    local x1, y1, z1 = vertices[v1][1], vertices[v1][2], vertices[v1][3]
    local x2, y2, z2 = vertices[v2][1], vertices[v2][2], vertices[v2][3]
    local x4, y4, z4 = vertices[v4][1], vertices[v4][2], vertices[v4][3]
    if id == "f" or id == "b" then
        -- all points have same z coord (front or back face)
        face.lattice[1] = {x1+1, y1, z1}
        face.lattice[2] = {x1+1, y4, z1}
        face.lattice[3] = {x1+2, y1, z1}
        face.lattice[4] = {x1+2, y4, z1}

        face.lattice[5] = {x1, y1-1, z1}
        face.lattice[6] = {x2, y1-1, z1}
        face.lattice[7] = {x1, y1-2, z1}
        face.lattice[8] = {x2, y1-2, z1}
        -- middle facelet:
        face.lattice[9 ] = {x1+1, y1-1, z1}
        face.lattice[10] = {x1+2, y1-1, z1}
        face.lattice[11] = {x1+2, y1-2, z1}
        face.lattice[12] = {x1+1, y1-2, z1}
    
    elseif id == "u" or id == "d" then
        -- all points have same y coord (up or down face)
        face.lattice[1] = {x1, y1, z1-1}
        face.lattice[2] = {x4, y1, z1-1}
        face.lattice[3] = {x1, y1, z1-2}
        face.lattice[4] = {x4, y1, z1-2}
        
        face.lattice[5] = {x1+1, y1, z1}
        face.lattice[6] = {x1+1, y1, z2}
        face.lattice[7] = {x1+2, y1, z1}
        face.lattice[8] = {x1+2, y1, z2}
        -- middle facelet:
        face.lattice[9 ] = {x1+1, y1, z1-1}
        face.lattice[10] = {x1+1, y1, z1-2}
        face.lattice[11] = {x1+2, y1, z1-2}
        face.lattice[12] = {x1+2, y1, z1-1}
    
    elseif id == "l" or id == "r" then
        -- all points have same x coord (left or right face)
        face.lattice[1] = {x1, y1, z1-1}
        face.lattice[2] = {x1, y4, z1-1}
        face.lattice[3] = {x1, y1, z1-2}
        face.lattice[4] = {x1, y4, z1-2}
        
        face.lattice[5] = {x1, y1-1, z1}
        face.lattice[6] = {x1, y1-1, z2}
        face.lattice[7] = {x1, y1-2, z1}
        face.lattice[8] = {x1, y1-2, z2}
        -- middle facelet:
        face.lattice[9 ] = {x1, y1-1, z1-1}
        face.lattice[10] = {x1, y1-1, z1-2}
        face.lattice[11] = {x1, y1-2, z1-2}
        face.lattice[12] = {x1, y1-2, z1-1}
    end

    return face
end

--------------------------------------------------------------------------------

-- current rotation angles (in degrees and kept within [0,360))
local xangle, yangle, zangle

-- current rotation matrix
local xixo, yixo, zixo
local xiyo, yiyo, ziyo
local xizo, yizo, zizo

function InitialView()
    xixo = 1; yixo = 0; zixo = 0
    xiyo = 0; yiyo = 1; ziyo = 0
    xizo = 0; yizo = 0; zizo = 1
    xangle, yangle, zangle = 0, 0, 0
    RotateCube(-30, 45, 0)
    -- front, top and right faces are all visible
end

--------------------------------------------------------------------------------

function RotateCube(xa, ya, za)
    -- don't really need to keep track of current angles but might come in handy
    xangle = (xangle + xa) % 360
    yangle = (yangle + ya) % 360
    zangle = (zangle + za) % 360
    -- glu.show(string.format("xa=%.2f ya=%.2f za=%.2f", xangle, yangle, zangle))

    local x = math.rad(xa)
    local y = math.rad(ya)
    local z = math.rad(za)
    local cosrx = cos(x)
    local sinrx = sin(x)
    local cosry = cos(y)
    local sinry = sin(y)
    local cosrz = cos(z)
    local sinrz = sin(z)

    -- calculate new transformation matrix for rotation about screen axes
    local a = cosry*cosrz
    local b = cosry*sinrz
    local c = -sinry
    local d = sinrx*sinry*cosrz - cosrx*sinrz
    local e = sinrx*sinry*sinrz + cosrx*cosrz
    local f = sinrx*cosry
    local g = cosrx*sinry*cosrz + sinrx*sinrz
    local h = cosrx*sinry*sinrz - sinrx*cosrz
    local i = cosrx*cosry

    local anew = a*xixo + b*yixo + c*zixo
    local bnew = a*xiyo + b*yiyo + c*ziyo
    local cnew = a*xizo + b*yizo + c*zizo
    local dnew = d*xixo + e*yixo + f*zixo
    local enew = d*xiyo + e*yiyo + f*ziyo
    local fnew = d*xizo + e*yizo + f*zizo
    local gnew = g*xixo + h*yixo + i*zixo
    local hnew = g*xiyo + h*yiyo + i*ziyo
    local inew = g*xizo + h*yizo + i*zizo

    -- update the rotation matrix for RotatePoint calls
    xixo = anew
    xiyo = bnew
    xizo = cnew
    yixo = dnew
    yiyo = enew
    yizo = fnew
    zixo = gnew
    ziyo = hnew
    zizo = inew
end

--------------------------------------------------------------------------------

local axismatrix = {} -- set in RotateFace and used in RotatePointInFace

function RotateFace(angle, l, m, n)
    -- create matrix to rotate points about axis defined by unit vector (l,m,n)
    local theta = math.rad(angle)
    local sinth = sin(theta)
    local costh = cos(theta)
    local onemc = 1 - costh
    local ll = l*l
    local mm = m*m
    local nn = n*n
    local lm = l*m
    local ln = l*n
    local mn = m*n
    axismatrix = {
        { ll*onemc+costh,   lm*onemc-n*sinth, ln*onemc+m*sinth },
        { lm*onemc+n*sinth, mm*onemc+costh,   mn*onemc-l*sinth },
        { ln*onemc-m*sinth, mn*onemc+l*sinth, nn*onemc+costh }
    }
end

--------------------------------------------------------------------------------

function MatrixMul(a, b)
    local colsA = #a[1]
    local rowsA = #a
    local colsB = #b[1]
    local rowsB = #b
    if colsA ~= rowsB then
        glu.exit("Bug in MatrixMul: columns of A must match rows of B!")
    end
    local result = {}
    for i = 1, rowsA do
        result[i] = {}
        for j = 1, colsB do
            local sum = 0.0
            for k = 1, colsA do
                sum = sum + a[i][k] * b[k][j]
            end
            result[i][j] = sum
        end
    end
    return result
end

--------------------------------------------------------------------------------

function RotatePoint(point)
    -- return rotated position of given 3D point
    local x, y, z = point[1], point[2], point[3]
    return x*xixo + y*xiyo + z*xizo,
           x*yixo + y*yiyo + z*yizo,
           x*zixo + y*ziyo + z*zizo
end

--------------------------------------------------------------------------------

function RotatePointInFace(point)
    -- return rotated position of given 3D point in a rotating face

    -- first need to get point into current cube position
    local x, y, z = point[1], point[2], point[3]
    local rotated = {
        { x*xixo + y*xiyo + z*xizo },
        { x*yixo + y*yiyo + z*yizo },
        { x*zixo + y*ziyo + z*zizo }
    }

    -- now rotate around axis
    rotated = MatrixMul(axismatrix, rotated)
    return rotated[1][1], rotated[2][1], rotated[3][1]
end

--------------------------------------------------------------------------------

function ProjectPoint(rx, ry, rz)
    -- return projected x,y position in canvas of given rotated 3D point
    local rotmatrix = {
        {rx},
        {ry},
        {rz}
    }
    -- use perspective projection:
    local z = 1 / (12 - rz)
    local projection = {
        {z, 0, 0},
        {0, z, 0}
    }
    local m = MatrixMul(projection, rotmatrix)
    local x = ( m[1][1] * scale)//1 + xo
    local y = (-m[2][1] * scale)//1 + yo
    -- y is negated because CreateCube assumes y values increase upwards
    return x, y
end

--------------------------------------------------------------------------------

function FillTriangle(ax,ay, bx,by, cx,cy)
    -- first relabel vertices so that ay <= by <= cy
    if ay > by then
        -- swap a and b
        ax, bx = bx, ax
        ay, by = by, ay
    end
    if ay > cy then
        -- swap a and c
        ax, cx = cx, ax
        ay, cy = cy, ay
    end
    if by > cy then
        -- swap b and c
        bx, cx = cx, bx
        by, cy = cy, by
    end

    -- calculate deltas for interpolation
    local delta1 = 0.0
    local delta2 = 0.0
    local delta3 = 0.0
    if by-ay > 0 then delta1 = (bx-ax) / (by-ay) end
    if cy-ay > 0 then delta2 = (cx-ax) / (cy-ay) end
    if cy-by > 0 then delta3 = (cx-bx) / (cy-by) end

    -- draw horizontal segments from sx to ex (start and end x coords)
    local sx = ax
    local sy = ay
    local ex = sx
    while sy < by do
        cv.line(sx//1, sy, ex//1, sy)
        sy = sy + 1
        sx = sx + delta1
        ex = ex + delta2
    end
    sx = bx
    while sy < cy do
        cv.line(sx//1, sy, ex//1, sy)
        sy = sy + 1
        sx = sx + delta3
        ex = ex + delta2
    end
end

--------------------------------------------------------------------------------

function DrawLines(face)
    local oldrgba = cv.rgba(cp.black)

    -- join vertices of given face
    local v1, v2, v3, v4 = unpack(face.corners)
    cv.line(prox[v1], proy[v1],
            prox[v2], proy[v2],
            prox[v3], proy[v3],
            prox[v4], proy[v4],
            prox[v1], proy[v1])

    -- draw lattice lines
    for i = 1, 7, 2 do
        local x1, y1 = ProjectPoint( RotatePoint(face.lattice[i]) )
        local x2, y2 = ProjectPoint( RotatePoint(face.lattice[i+1]) )
        cv.line(x1, y1, x2, y2)
    end

    cv.rgba(oldrgba)
end

--------------------------------------------------------------------------------

function DrawFace(face)
    local v1, v2, v3, v4 = unpack(face.corners)

    -- don't use antialiased lines for FillTriangle
    local oldblend = cv.blend(0)
    local oldwidth = cv.linewidth(1)
    local oldrgba = cv.rgba(cp.black)
    
--[[ we need to fill the 9 facelets with face.colors[1][1] to [3][3];
     note that the corner points (v1, v2, v3, v4) have been rotated and projected
     but the face.lattice points (l1 to l12) have not

    v1    l1     l3      v2
    *------*------*------*
    | c1,1 | c1,2 | c1,3 |
    |      |      |      |
  l5*-----l9-----l10-----*l6
    | c2,1 | c2,2 | c2,3 |
    |      |      |      |
  l7*-----l12----l11-----*l8
    | c3,1 | c3,2 | c3,3 |
    |      |      |      |
    *------*------*------*
    v4    l2     l4      v3
--]]

    -- these will be the 4 projected corners of a facelet
    local ax,ay, bx,by, cx,cy, dx,dy
    
    cv.rgba(face.colors[1][1])
    ax, ay = prox[v1], proy[v1]
    bx, by = ProjectPoint( RotatePoint(face.lattice[1]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[9]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[5]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)
    
    cv.rgba(face.colors[1][2])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[1]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[3]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[10]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[9]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)

    cv.rgba(face.colors[1][3])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[3]) )
    bx, by = prox[v2], proy[v2]
    cx, cy = ProjectPoint( RotatePoint(face.lattice[6]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[10]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)

    cv.rgba(face.colors[2][1])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[5]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[9]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[12]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[7]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)

    cv.rgba(face.colors[2][2])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[9]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[10]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[11]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[12]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)

    cv.rgba(face.colors[2][3])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[10]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[6]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[8]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[11]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)
    
    cv.rgba(face.colors[3][1])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[7]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[12]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[2]) )
    dx, dy = prox[v4], proy[v4]
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)

    cv.rgba(face.colors[3][2])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[12]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[11]) )
    cx, cy = ProjectPoint( RotatePoint(face.lattice[4]) )
    dx, dy = ProjectPoint( RotatePoint(face.lattice[2]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)
    
    cv.rgba(face.colors[3][3])
    ax, ay = ProjectPoint( RotatePoint(face.lattice[11]) )
    bx, by = ProjectPoint( RotatePoint(face.lattice[8]) )
    cx, cy = prox[v3], proy[v3]
    dx, dy = ProjectPoint( RotatePoint(face.lattice[4]) )
    FillTriangle(ax,ay, bx,by, cx,cy)
    FillTriangle(cx,cy, dx,dy, ax,ay)
    
    cv.linewidth(oldwidth)
    cv.blend(oldblend)
    cv.rgba(oldrgba)
    
    -- draw the edges and lattice lines on this face
    DrawLines(face)
end

--------------------------------------------------------------------------------

function DrawVisibleFaces()
    -- find the 3 closest vertices
    local max1, max2, max3
    local maxz = math.mininteger
    for i = 1, 8 do
        if rotz[i] > maxz then maxz = rotz[i] max1 = i end
    end
    maxz = math.mininteger
    for i = 1, 8 do
        if i ~= max1 and rotz[i] > maxz then maxz = rotz[i]; max2 = i end
    end
    maxz = math.mininteger
    for i = 1, 8 do
        if i ~= max1 and i ~= max2 and rotz[i] > maxz then maxz = rotz[i]; max3 = i end
    end
    
    local function CheckOrder(v1,v4,v2, o1,o2,o3,o4)
        -- ensure rearmost adjacent face is drawn first
        -- (this avoids seeing the facelets of a hidden adjacent face)
        if rotz[v1] > rotz[v4] then
            if rotz[v1] > rotz[v2] then
                return rotz[o4] > rotz[o2]
            else
                return rotz[o3] > rotz[o1]
            end 
        else
            if rotz[v1] > rotz[v2] then
                return rotz[o1] > rotz[o3]
            else
                return rotz[o2] > rotz[o4]
            end 
        end
    end

    local function DrawAdjacentFace(a1,a2, v1,v2)
        if rotz[v1] > rotz[v2] then
            DrawFace(a1)
        else
            DrawFace(a2)
        end
    end

    -- find the closest face and draw it after drawing 2 adjacent faces
    if front_vertex[max1] and front_vertex[max2] and front_vertex[max3] then
        -- front_face is closest (1,2,3,4)
        if CheckOrder(1,4,2, 5,6,7,8) then
            DrawAdjacentFace(up_face, down_face,    1,4)
            DrawAdjacentFace(left_face, right_face, 1,2)
        else
            DrawAdjacentFace(left_face, right_face, 1,2)
            DrawAdjacentFace(up_face, down_face,    1,4)
        end
        DrawFace(front_face)

    elseif back_vertex[max1] and back_vertex[max2] and back_vertex[max3] then
        -- back_face is closest (5,6,7,8)
        if CheckOrder(5,8,6, 1,2,3,4) then
            DrawAdjacentFace(up_face, down_face,    5,8)
            DrawAdjacentFace(left_face, right_face, 5,6)
        else
            DrawAdjacentFace(left_face, right_face, 5,6)
            DrawAdjacentFace(up_face, down_face,    5,8)
        end
        DrawFace(back_face)

    elseif up_vertex[max1] and up_vertex[max2] and up_vertex[max3] then
        -- up_face is closest (1,5,6,2)
        if CheckOrder(1,2,5, 4,8,7,3) then
            DrawAdjacentFace(left_face, right_face, 1,2)
            DrawAdjacentFace(front_face, back_face, 1,5)
        else
            DrawAdjacentFace(front_face, back_face, 1,5)
            DrawAdjacentFace(left_face, right_face, 1,2)
        end
        DrawFace(up_face)

    elseif down_vertex[max1] and down_vertex[max2] and down_vertex[max3] then
        -- down_face is closest (4,8,7,3)
        if CheckOrder(4,3,8, 1,5,6,2) then
            DrawAdjacentFace(left_face, right_face, 4,3)
            DrawAdjacentFace(front_face, back_face, 4,8)
        else
            DrawAdjacentFace(front_face, back_face, 4,8)
            DrawAdjacentFace(left_face, right_face, 4,3)
        end
        DrawFace(down_face)

    elseif left_vertex[max1] and left_vertex[max2] and left_vertex[max3] then
        -- left_face is closest (1,5,8,4)
        if CheckOrder(1,4,5, 2,6,7,3) then
            DrawAdjacentFace(up_face, down_face,    1,4)
            DrawAdjacentFace(front_face, back_face, 1,5)
        else
            DrawAdjacentFace(front_face, back_face, 1,5)
            DrawAdjacentFace(up_face, down_face,    1,4)
        end
        DrawFace(left_face)

    elseif right_vertex[max1] and right_vertex[max2] and right_vertex[max3] then
        -- right_face is closest (2,6,7,3)
        if CheckOrder(2,3,6, 1,5,8,4) then
            DrawAdjacentFace(up_face, down_face,    2,3)
            DrawAdjacentFace(front_face, back_face, 2,6)
        else
            DrawAdjacentFace(front_face, back_face, 2,6)
            DrawAdjacentFace(up_face, down_face,    2,3)
        end
        DrawFace(right_face)
    else
        glu.warn("Bug in DrawVisibleFaces!")
    end
end

--------------------------------------------------------------------------------

function DrawBackground()
    local oldblend = cv.blend(0)
    cv.rgba(bg_color)
    cv.fill()
    
    local y = 20
    local x = 20
    local hgap = 10
    local vgap = 20

    exit_button.show(x, y)
    help_button.show(x + exit_button.wd + hgap, y)
    
    local buttht = help_button.ht
    y = y + buttht + vgap
    fc_button.show(x, y)
    fa_button.show(x + fc_button.wd + hgap, y); y = y + buttht + 10
    bc_button.show(x, y)
    ba_button.show(x + bc_button.wd + hgap, y); y = y + buttht + 10
    uc_button.show(x, y)
    ua_button.show(x + uc_button.wd + hgap, y); y = y + buttht + 10
    dc_button.show(x, y)
    da_button.show(x + dc_button.wd + hgap, y); y = y + buttht + 10
    rc_button.show(x, y)
    ra_button.show(x + rc_button.wd + hgap, y); y = y + buttht + 10
    lc_button.show(x, y)
    la_button.show(x + lc_button.wd + hgap, y); y = y + buttht + 10

    undo_button.enable(#undostack > 0)
    redo_button.enable(#redostack > 0)
    undo_button.show(x, y)
    redo_button.show(x + undo_button.wd + hgap, y)
    
    y = y + buttht + vgap
    scramble_button.show(x, y); y = y + buttht + 10
    solve_button.show(x, y); y = y + buttht + 10
    reset_button.show(x, y)
    
    cv.blend(oldblend)
end

--------------------------------------------------------------------------------

function DrawCube()
    -- calculate the cube's rotated vertices in 3D space
    -- and their projected positions in the canvas
    for i = 1, 8 do
        rotx[i], roty[i], rotz[i] = RotatePoint(vertices[i])
        prox[i], proy[i] = ProjectPoint(rotx[i], roty[i], rotz[i])
    end
    DrawVisibleFaces()
end

--------------------------------------------------------------------------------

function Refresh()
    glu.check(false)    -- avoid partial updates of canvas
    
    local framestart = glu.millisecs()

    DrawBackground()
    
    local btime = glu.millisecs() - framestart
    
    cv.blend(2)         -- use faster antialiasing on opaque background
    DrawCube()
    
    local ctime = glu.millisecs() - framestart - btime

    cv.update()         -- canvas covers viewport
    
    local utime = glu.millisecs() - framestart - (btime + ctime)

    if showtime then
        local ftime = glu.millisecs() - framestart
        glu.show(string.format("frame time = %.2fms (bg = %.2fms, cube = %.2fms, update = %.2fms)",
                 ftime, btime, ctime, utime))
    end

    -- pause to get 60 frames per second
    while glu.millisecs() - framestart < 1000/60 do end

    glu.check(true)     -- restore event checking
end

--------------------------------------------------------------------------------

function SetScale()
    -- set scale depending on canvas size
    scale = min(cvwd-leftgap,cvht) * 2.0
    
    -- also set line width
    if scale < 600 then
        cv.linewidth(3)
    elseif scale < 1200 then
        cv.linewidth(4)
    elseif scale < 1600 then
        cv.linewidth(5)
    else
        cv.linewidth(6)
    end
end

--------------------------------------------------------------------------------

function ViewSizeChanged()
    local viewwd, viewht = glu.getview()
    if cvwd ~= viewwd or cvht ~= viewht then
        if viewwd < minwd then viewwd = minwd end
        if viewht < minht then viewht = minht end
        glu.setview(viewwd, viewht)
        cvwd = viewwd
        cvht = viewht
        xo = leftgap + (cvwd-leftgap)//2
        yo = cvht//2
        SetScale()
        cv.resize()
        return true     -- refresh needed
    else
        return false
    end
end

--------------------------------------------------------------------------------

function TruncateCube(face, xyz, newval, a1, a2, a3, a4)
    -- chop off given face by temporarily truncating its vertices
    -- (xyz is 1, 2 or 3 and newval is 0.5 or -0.5)
    local v1, v2, v3, v4 = unpack(face.corners)
    vertices[v1][xyz] = newval
    vertices[v2][xyz] = newval
    vertices[v3][xyz] = newval
    vertices[v4][xyz] = newval

    -- truncate the lattice points for this face and its adjacent faces (a1, a2, a3, a4)
    local save1, save2, save3, save4 = {},{},{},{}
    for i = 1, 12 do
        face.lattice[i][xyz] = newval
        save1[i] = a1.lattice[i][xyz]
        save2[i] = a2.lattice[i][xyz]
        save3[i] = a3.lattice[i][xyz]
        save4[i] = a4.lattice[i][xyz]
        if newval > 0 then
            -- newval is 0.5
            if a1.lattice[i][xyz] > newval then a1.lattice[i][xyz] = newval end
            if a2.lattice[i][xyz] > newval then a2.lattice[i][xyz] = newval end
            if a3.lattice[i][xyz] > newval then a3.lattice[i][xyz] = newval end
            if a4.lattice[i][xyz] > newval then a4.lattice[i][xyz] = newval end
        else
            -- newval is -0.5
            if a1.lattice[i][xyz] < newval then a1.lattice[i][xyz] = newval end
            if a2.lattice[i][xyz] < newval then a2.lattice[i][xyz] = newval end
            if a3.lattice[i][xyz] < newval then a3.lattice[i][xyz] = newval end
            if a4.lattice[i][xyz] < newval then a4.lattice[i][xyz] = newval end
        end
    end
    
    -- change the face colors to black
    local savecolors = { {1,2,3}, {4,5,6}, {7,8,9} }
    for row = 1, 3 do
        for col = 1, 3 do
            savecolors[row][col] = face.colors[row][col]
            face.colors[row][col] = cp.black
        end
    end
    
    -- create a clip and draw truncated cube in it
    local clipname = "truncated cube"
    cv.create(cvwd, cvht, clipname)
    cv.target(clipname)
    DrawCube()
    cv.target()
    
    -- restore cube
    local oldval = 1.5
    if newval < 0 then oldval = -1.5 end
    vertices[v1][xyz] = oldval
    vertices[v2][xyz] = oldval
    vertices[v3][xyz] = oldval
    vertices[v4][xyz] = oldval
    for i = 1, 12 do
        face.lattice[i][xyz] = oldval
        a1.lattice[i][xyz] = save1[i]
        a2.lattice[i][xyz] = save2[i]
        a3.lattice[i][xyz] = save3[i]
        a4.lattice[i][xyz] = save4[i]
    end
    for row = 1, 3 do
        for col = 1, 3 do
            face.colors[row][col] = savecolors[row][col]
        end
    end
    
    return clipname
end

--------------------------------------------------------------------------------

function TruncateFace(face, oppface, xyz, newval, a1, a2, a3, a4)
    -- chop off cube beyond face by adjusting vertices of opposite face
    -- (xyz is 1, 2 or 3 and newval is 0.5 or -0.5)
    local saved = {}
    local allfaces = {front_face, back_face, up_face, down_face, left_face, right_face}
    
    -- save all vertices and lattice points for ALL faces
    saved.savevertices = {}
    for i = 1, 8 do
        saved.savevertices[i] = {unpack(vertices[i])}
    end
    saved.savelattices = {}
    for findex, f in ipairs(allfaces) do
        saved.savelattices[findex] = {}
        for i = 1, 12 do
            saved.savelattices[findex][i] = {unpack(f.lattice[i])}
        end
    end
    
    local o1, o2, o3, o4 = unpack(oppface.corners)
    vertices[o1][xyz] = newval
    vertices[o2][xyz] = newval
    vertices[o3][xyz] = newval
    vertices[o4][xyz] = newval

    -- truncate the lattice points for opposite face and the adjacent faces (a1, a2, a3, a4)
    for i = 1, 12 do
        oppface.lattice[i][xyz] = newval
        if newval > 0 then
            -- newval is 0.5
            if a1.lattice[i][xyz] < newval then a1.lattice[i][xyz] = newval end
            if a2.lattice[i][xyz] < newval then a2.lattice[i][xyz] = newval end
            if a3.lattice[i][xyz] < newval then a3.lattice[i][xyz] = newval end
            if a4.lattice[i][xyz] < newval then a4.lattice[i][xyz] = newval end
        else
            -- newval is -0.5
            if a1.lattice[i][xyz] > newval then a1.lattice[i][xyz] = newval end
            if a2.lattice[i][xyz] > newval then a2.lattice[i][xyz] = newval end
            if a3.lattice[i][xyz] > newval then a3.lattice[i][xyz] = newval end
            if a4.lattice[i][xyz] > newval then a4.lattice[i][xyz] = newval end
        end
    end
    
    -- change the opposite face colors to black
    saved.savecolors = { {1,2,3}, {4,5,6}, {7,8,9} }
    for row = 1, 3 do
        for col = 1, 3 do
            saved.savecolors[row][col] = oppface.colors[row][col]
            oppface.colors[row][col] = cp.black
        end
    end
    
    return saved
end

--------------------------------------------------------------------------------

function RestoreCube(saved, oppface)
    -- restore cube
    local allfaces = {front_face, back_face, up_face, down_face, left_face, right_face}
    for i = 1, 8 do
        vertices[i] = {unpack(saved.savevertices[i])}
    end
    for findex, f in ipairs(allfaces) do
        for i = 1, 12 do
            f.lattice[i] = {unpack(saved.savelattices[findex][i])}
        end
    end
    for row = 1, 3 do
        for col = 1, 3 do
            oppface.colors[row][col] = saved.savecolors[row][col]
        end
    end
end

--------------------------------------------------------------------------------

function CreateRotatedFace(face, angle, clockwise, ux, uy, uz)
    if clockwise then
        angle = -angle
    end

    local saveRotatePoint = RotatePoint
    RotatePoint = RotatePointInFace
    RotateFace(angle, ux, uy, uz)

    -- create a clip and draw the rotated face inside it
    local clipname = "face"
    cv.create(cvwd, cvht, clipname)
    cv.target(clipname)
    DrawCube() -- lots of calls to RotatePoint
    cv.target()

    RotatePoint = saveRotatePoint
    return clipname
end

--------------------------------------------------------------------------------

function DoAnimation(face, clockwise, xyz, newval, oppface, a1, a2, a3, a4)
    glu.check(false)
    local oldblend = cv.blend(1)
    
    local face_in_front = rotz[face.corners[1]] > rotz[oppface.corners[1]]
    
    -- create a clip with given face removed from cube
    local cubeclip = TruncateCube(face, xyz, newval, a1, a2, a3, a4)

    local savedinfo = TruncateFace(face, oppface, xyz, newval, a1, a2, a3, a4)
    
    -- find the rotated midpoint of this face
    local v1, v2, v3, v4 = unpack(face.corners)
    local rx1, ry1, rz1 = RotatePoint(vertices[v1])
    local rx3, ry3, rz3 = RotatePoint(vertices[v3]) -- diagonally opposite vertex
    local midx = (rx1 + rx3)/2
    local midy = (ry1 + ry3)/2
    local midz = (rz1 + rz3)/2

    -- find the unit vector for (0,0,0) to (midx,midy,midz)
    local mag = math.sqrt(midx*midx + midy*midy + midz*midz)
    local ux = midx/mag
    local uy = midy/mag
    local uz = midz/mag

    -- do the animation loop (18 rotations at 60fps is ~ 0.3 secs)
    for angle = 5, 90, 5 do
        local t = glu.millisecs()
        glu.getevent() -- avoid any user events accumulating in queue
        
        -- create a clip with the next rotated face
        local faceclip = CreateRotatedFace(face, angle, clockwise, ux, uy, uz)

        DrawBackground()
        if face_in_front then
            cv.paste(cubeclip, 0, 0)
            cv.paste(faceclip, 0, 0)
        else
            cv.paste(faceclip, 0, 0)
            cv.paste(cubeclip, 0, 0)
        end
        cv.delete(faceclip)
                
        cv.update()
        -- animate at approx 60 frames per second
        while glu.millisecs() - t < 1000/60 do end
    end

    RestoreCube(savedinfo, oppface)
    
    cv.delete(cubeclip)
    cv.blend(oldblend)
    glu.check(true)
end

--------------------------------------------------------------------------------

function AnimateRotation(face, clockwise)
    if not animate then return end
    -- the numbers passed into DoAnimation are the x/y/z index and the
    -- truncated vertex value for that index (see diagram in CreateCube)
    if face == front_face then
        DoAnimation(face, clockwise, 3,  0.5, back_face, up_face, down_face, left_face, right_face)
    elseif face == back_face then
        DoAnimation(face, clockwise, 3, -0.5, front_face, up_face, down_face, left_face, right_face)
    elseif face == up_face then
        DoAnimation(face, clockwise, 2,  0.5, down_face, front_face, back_face, left_face, right_face)
    elseif face == down_face then
        DoAnimation(face, clockwise, 2, -0.5, up_face, front_face, back_face, left_face, right_face)
    elseif face == right_face then
        DoAnimation(face, clockwise, 1,  0.5, left_face, front_face, back_face, up_face, down_face)
    elseif face == left_face then
        DoAnimation(face, clockwise, 1, -0.5, right_face, front_face, back_face, up_face, down_face)
    end
end

--------------------------------------------------------------------------------

function RotateColorsOnFace(face, clockwise)
    -- do 8 color changes on given face
    local savecolor1 = face.colors[1][1]
    local savecolor2 = face.colors[1][2]
    if clockwise then
        face.colors[1][1] = face.colors[3][1]
        face.colors[1][2] = face.colors[2][1]
        
        face.colors[3][1] = face.colors[3][3]
        face.colors[2][1] = face.colors[3][2]
        
        face.colors[3][3] = face.colors[1][3]
        face.colors[3][2] = face.colors[2][3]
        
        face.colors[1][3] = savecolor1
        face.colors[2][3] = savecolor2
    else
        face.colors[1][1] = face.colors[1][3]
        face.colors[1][2] = face.colors[2][3]
        
        face.colors[1][3] = face.colors[3][3]
        face.colors[2][3] = face.colors[3][2]
        
        face.colors[3][3] = face.colors[3][1]
        face.colors[3][2] = face.colors[2][1]

        face.colors[3][1] = savecolor1
        face.colors[2][1] = savecolor2
    end
end

--------------------------------------------------------------------------------

function RotateFrontFace(clockwise)
    if savemove then
        redostack = {}
        undostack[#undostack+1] = {rotatecall=RotateFrontFace, arg=clockwise}
    end
    
    AnimateRotation(front_face, clockwise)
    RotateColorsOnFace(front_face, clockwise)

    -- do 12 color changes on adjacent faces
    local savecolor1 = right_face.colors[1][1]
    local savecolor2 = right_face.colors[2][1]
    local savecolor3 = right_face.colors[3][1]
    if clockwise then
        right_face.colors[1][1] = up_face.colors[1][1]
        right_face.colors[2][1] = up_face.colors[2][1]
        right_face.colors[3][1] = up_face.colors[3][1]
        
        up_face.colors[1][1] = left_face.colors[3][1]
        up_face.colors[2][1] = left_face.colors[2][1]
        up_face.colors[3][1] = left_face.colors[1][1]
        
        left_face.colors[1][1] = down_face.colors[1][1]
        left_face.colors[2][1] = down_face.colors[2][1]
        left_face.colors[3][1] = down_face.colors[3][1]
        
        down_face.colors[1][1] = savecolor3
        down_face.colors[2][1] = savecolor2
        down_face.colors[3][1] = savecolor1
    else
        right_face.colors[1][1] = down_face.colors[3][1]
        right_face.colors[2][1] = down_face.colors[2][1]
        right_face.colors[3][1] = down_face.colors[1][1]
        
        down_face.colors[1][1] = left_face.colors[1][1]
        down_face.colors[2][1] = left_face.colors[2][1]
        down_face.colors[3][1] = left_face.colors[3][1]

        left_face.colors[1][1] = up_face.colors[3][1]
        left_face.colors[2][1] = up_face.colors[2][1]
        left_face.colors[3][1] = up_face.colors[1][1]

        up_face.colors[1][1] = savecolor1
        up_face.colors[2][1] = savecolor2
        up_face.colors[3][1] = savecolor3
    end
end

--------------------------------------------------------------------------------

function RotateBackFace(clockwise)
    if savemove then
        redostack = {}
        undostack[#undostack+1] = {rotatecall=RotateBackFace, arg=clockwise}
    end
    
    AnimateRotation(back_face, clockwise)
    clockwise = not clockwise
    RotateColorsOnFace(back_face, clockwise)

    -- do 12 color changes on adjacent faces
    local savecolor1 = right_face.colors[1][3]
    local savecolor2 = right_face.colors[2][3]
    local savecolor3 = right_face.colors[3][3]
    if clockwise then
        right_face.colors[1][3] = up_face.colors[1][3]
        right_face.colors[2][3] = up_face.colors[2][3]
        right_face.colors[3][3] = up_face.colors[3][3]

        up_face.colors[1][3] = left_face.colors[3][3]
        up_face.colors[2][3] = left_face.colors[2][3]
        up_face.colors[3][3] = left_face.colors[1][3]

        left_face.colors[1][3] = down_face.colors[1][3]
        left_face.colors[2][3] = down_face.colors[2][3]
        left_face.colors[3][3] = down_face.colors[3][3]

        down_face.colors[1][3] = savecolor3
        down_face.colors[2][3] = savecolor2
        down_face.colors[3][3] = savecolor1
    else
        right_face.colors[1][3] = down_face.colors[3][3]
        right_face.colors[2][3] = down_face.colors[2][3]
        right_face.colors[3][3] = down_face.colors[1][3]
        
        down_face.colors[1][3] = left_face.colors[1][3]
        down_face.colors[2][3] = left_face.colors[2][3]
        down_face.colors[3][3] = left_face.colors[3][3]

        left_face.colors[1][3] = up_face.colors[3][3]
        left_face.colors[2][3] = up_face.colors[2][3]
        left_face.colors[3][3] = up_face.colors[1][3]

        up_face.colors[1][3] = savecolor1
        up_face.colors[2][3] = savecolor2
        up_face.colors[3][3] = savecolor3
    end
end

--------------------------------------------------------------------------------

function RotateUpFace(clockwise)
    if savemove then
        redostack = {}
        undostack[#undostack+1] = {rotatecall=RotateUpFace, arg=clockwise}
    end
    
    AnimateRotation(up_face, clockwise)
    RotateColorsOnFace(up_face, clockwise)

    -- do 12 color changes on adjacent faces
    local savecolor1 = front_face.colors[1][1]
    local savecolor2 = front_face.colors[1][2]
    local savecolor3 = front_face.colors[1][3]
    if clockwise then
        front_face.colors[1][1] = right_face.colors[1][1]
        front_face.colors[1][2] = right_face.colors[1][2]
        front_face.colors[1][3] = right_face.colors[1][3]
        
        right_face.colors[1][1] = back_face.colors[1][3]
        right_face.colors[1][2] = back_face.colors[1][2]
        right_face.colors[1][3] = back_face.colors[1][1]
        
        back_face.colors[1][1] = left_face.colors[1][1]
        back_face.colors[1][2] = left_face.colors[1][2]
        back_face.colors[1][3] = left_face.colors[1][3]
        
        left_face.colors[1][1] = savecolor3
        left_face.colors[1][2] = savecolor2
        left_face.colors[1][3] = savecolor1
    else
        front_face.colors[1][1] = left_face.colors[1][3]
        front_face.colors[1][2] = left_face.colors[1][2]
        front_face.colors[1][3] = left_face.colors[1][1]
        
        left_face.colors[1][1] = back_face.colors[1][1]
        left_face.colors[1][2] = back_face.colors[1][2]
        left_face.colors[1][3] = back_face.colors[1][3]

        back_face.colors[1][1] = right_face.colors[1][3]
        back_face.colors[1][2] = right_face.colors[1][2]
        back_face.colors[1][3] = right_face.colors[1][1]

        right_face.colors[1][1] = savecolor1
        right_face.colors[1][2] = savecolor2
        right_face.colors[1][3] = savecolor3
    end
end

--------------------------------------------------------------------------------

function RotateDownFace(clockwise)
    if savemove then
        redostack = {}
        undostack[#undostack+1] = {rotatecall=RotateDownFace, arg=clockwise}
    end
    
    AnimateRotation(down_face, clockwise)
    clockwise = not clockwise
    RotateColorsOnFace(down_face, clockwise)

    -- do 12 color changes on adjacent faces
    local savecolor1 = front_face.colors[3][1]
    local savecolor2 = front_face.colors[3][2]
    local savecolor3 = front_face.colors[3][3]
    if clockwise then
        front_face.colors[3][1] = right_face.colors[3][1]
        front_face.colors[3][2] = right_face.colors[3][2]
        front_face.colors[3][3] = right_face.colors[3][3]
        
        right_face.colors[3][1] = back_face.colors[3][3]
        right_face.colors[3][2] = back_face.colors[3][2]
        right_face.colors[3][3] = back_face.colors[3][1]
        
        back_face.colors[3][1] = left_face.colors[3][1]
        back_face.colors[3][2] = left_face.colors[3][2]
        back_face.colors[3][3] = left_face.colors[3][3]
        
        left_face.colors[3][1] = savecolor3
        left_face.colors[3][2] = savecolor2
        left_face.colors[3][3] = savecolor1
    else
        front_face.colors[3][1] = left_face.colors[3][3]
        front_face.colors[3][2] = left_face.colors[3][2]
        front_face.colors[3][3] = left_face.colors[3][1]
        
        left_face.colors[3][1] = back_face.colors[3][1]
        left_face.colors[3][2] = back_face.colors[3][2]
        left_face.colors[3][3] = back_face.colors[3][3]

        back_face.colors[3][1] = right_face.colors[3][3]
        back_face.colors[3][2] = right_face.colors[3][2]
        back_face.colors[3][3] = right_face.colors[3][1]

        right_face.colors[3][1] = savecolor1
        right_face.colors[3][2] = savecolor2
        right_face.colors[3][3] = savecolor3
    end
end

--------------------------------------------------------------------------------

function RotateRightFace(clockwise)
    if savemove then
        redostack = {}
        undostack[#undostack+1] = {rotatecall=RotateRightFace, arg=clockwise}
    end
    
    AnimateRotation(right_face, clockwise)
    RotateColorsOnFace(right_face, clockwise)

    -- do 12 color changes on adjacent faces
    local savecolor1 = up_face.colors[3][1]
    local savecolor2 = up_face.colors[3][2]
    local savecolor3 = up_face.colors[3][3]
    if clockwise then
        up_face.colors[3][1] = front_face.colors[3][3]
        up_face.colors[3][2] = front_face.colors[2][3]
        up_face.colors[3][3] = front_face.colors[1][3]
        
        front_face.colors[1][3] = down_face.colors[3][1]
        front_face.colors[2][3] = down_face.colors[3][2]
        front_face.colors[3][3] = down_face.colors[3][3]
        
        down_face.colors[3][1] = back_face.colors[3][3]
        down_face.colors[3][2] = back_face.colors[2][3]
        down_face.colors[3][3] = back_face.colors[1][3]
        
        back_face.colors[1][3] = savecolor1
        back_face.colors[2][3] = savecolor2
        back_face.colors[3][3] = savecolor3
    else
        up_face.colors[3][1] = back_face.colors[1][3]
        up_face.colors[3][2] = back_face.colors[2][3]
        up_face.colors[3][3] = back_face.colors[3][3]
        
        back_face.colors[1][3] = down_face.colors[3][3]
        back_face.colors[2][3] = down_face.colors[3][2]
        back_face.colors[3][3] = down_face.colors[3][1]
        
        down_face.colors[3][1] = front_face.colors[1][3]
        down_face.colors[3][2] = front_face.colors[2][3]
        down_face.colors[3][3] = front_face.colors[3][3]
        
        front_face.colors[1][3] = savecolor3
        front_face.colors[2][3] = savecolor2
        front_face.colors[3][3] = savecolor1
    end
end

--------------------------------------------------------------------------------

function RotateLeftFace(clockwise)
    if savemove then
        redostack = {}
        undostack[#undostack+1] = {rotatecall=RotateLeftFace, arg=clockwise}
    end
    
    AnimateRotation(left_face, clockwise)
    clockwise = not clockwise
    RotateColorsOnFace(left_face, clockwise)

    -- do 12 color changes on adjacent faces
    local savecolor1 = up_face.colors[1][1]
    local savecolor2 = up_face.colors[1][2]
    local savecolor3 = up_face.colors[1][3]
    if clockwise then
        up_face.colors[1][1] = front_face.colors[3][1]
        up_face.colors[1][2] = front_face.colors[2][1]
        up_face.colors[1][3] = front_face.colors[1][1]
        
        front_face.colors[1][1] = down_face.colors[1][1]
        front_face.colors[2][1] = down_face.colors[1][2]
        front_face.colors[3][1] = down_face.colors[1][3]
        
        down_face.colors[1][1] = back_face.colors[3][1]
        down_face.colors[1][2] = back_face.colors[2][1]
        down_face.colors[1][3] = back_face.colors[1][1]
        
        back_face.colors[1][1] = savecolor1
        back_face.colors[2][1] = savecolor2
        back_face.colors[3][1] = savecolor3
    else
        up_face.colors[1][1] = back_face.colors[1][1]
        up_face.colors[1][2] = back_face.colors[2][1]
        up_face.colors[1][3] = back_face.colors[3][1]
        
        back_face.colors[1][1] = down_face.colors[1][3]
        back_face.colors[2][1] = down_face.colors[1][2]
        back_face.colors[3][1] = down_face.colors[1][1]
        
        down_face.colors[1][1] = front_face.colors[1][1]
        down_face.colors[1][2] = front_face.colors[2][1]
        down_face.colors[1][3] = front_face.colors[3][1]
        
        front_face.colors[1][1] = savecolor3
        front_face.colors[2][1] = savecolor2
        front_face.colors[3][1] = savecolor1
    end
end

--------------------------------------------------------------------------------

function ResetCube(initview)
    undostack = {}
    redostack = {}
    for row = 1, 3 do
        for col = 1, 3 do
            front_face.colors[row][col] = front_color
            back_face.colors[row][col]  = back_color
            up_face.colors[row][col]    = up_color
            down_face.colors[row][col]  = down_color
            left_face.colors[row][col]  = left_color
            right_face.colors[row][col] = right_color
        end
    end
    if initview then InitialView() end
    autorotate = false
end

--------------------------------------------------------------------------------

function ScrambleCube()
    animate = false     -- better if we don't animate rotations
    savemove = false    -- and don't save moves in undostack

    ResetCube(false)
    -- do a number of random face rotations
    local rotfuncs = {RotateFrontFace, RotateBackFace,
                      RotateUpFace, RotateDownFace,
                      RotateRightFace, RotateLeftFace}
    local prevfunc = 0
    local prevarg = 0
    local opparg = {2,1}
    for i = 1, 30 do
        local func = rand(1,6)
        local arg = rand(1,2)
        if func == prevfunc and arg == opparg[prevarg] then
            -- don't do a move that would undo previous move
        else
            rotfuncs[func](arg == 1)
            Refresh()
            prevfunc = func
            prevarg = arg
        end
    end
    
    --[[ enable this code to do a super-flip:
    -- R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U
    -- (see https://ruwix.com/the-rubiks-cube/gods-number/)
    ResetCube(false)
    RotateRightFace(true)
    RotateLeftFace(true)
    RotateUpFace(true) RotateUpFace(true)
    RotateFrontFace(true)
    RotateUpFace(false)
    RotateDownFace(true)
    RotateFrontFace(true) RotateFrontFace(true)
    RotateRightFace(true) RotateRightFace(true)
    RotateBackFace(true) RotateBackFace(true)
    RotateLeftFace(true)
    RotateUpFace(true) RotateUpFace(true)
    RotateFrontFace(false)
    RotateBackFace(false)
    RotateUpFace(true)
    RotateRightFace(true) RotateRightFace(true)
    RotateDownFace(true)
    RotateFrontFace(true) RotateFrontFace(true)
    RotateUpFace(true)
    RotateRightFace(true) RotateRightFace(true)
    RotateUpFace(true)
    --]]

    animate = true
    savemove = true
end

--------------------------------------------------------------------------------

function CubeSolved()
    -- return true if each face has only one color
    local f,b,u,d,l,r = 0,0,0,0,0,0
    for _,face in ipairs{front_face, back_face, up_face, down_face, left_face, right_face} do
        local color1 = face.colors[1][1]
        for row = 1, 3 do
            for col = 1, 3 do
                if face.colors[row][col] ~= color1 then
                    return false
                end
                if color1 == front_color then f = f+1 end
                if color1 == back_color  then b = b+1 end
                if color1 == up_color    then u = u+1 end
                if color1 == down_color  then d = d+1 end
                if color1 == left_color  then l = l+1 end
                if color1 == right_color then r = r+1 end
            end
        end
    end
    if f ~= 9 or b ~= 9 or u ~= 9 or d ~= 9 or l ~= 9 or r ~= 9 then
        -- should never happen
        glu.warn("Bug: color counts are not all 9!")
        return false
    end
    return true
end

--------------------------------------------------------------------------------

-- Data and functions for SolveCube (thanks to Tom Rokicki):

--[[

Glue routine between solver and above code.  Enables us to interpret a
returned sequence of integers as moves.

--]]

local ufrdblfuncs = {RotateUpFace, RotateFrontFace,
                     RotateRightFace, RotateDownFace,
                     RotateBackFace, RotateLeftFace}
local function domove(face, twist)
   if twist == 1 then
      ufrdblfuncs[face](true)
   elseif twist == 2 then
      ufrdblfuncs[face](true)
      ufrdblfuncs[face](true)
   elseif twist == 3 then
      ufrdblfuncs[face](false)
   else
      print("Bad twist in domove", twist)
   end
end

--[[

This is a simple implementation of Kociemba's algorithm based on the
representation of the cube embodied above.  It attempts to strike a
reasonable balance between speed and simplicity.  The current code
should initialize in about 1.6s, find solutions in an average of
about 0.2s with an average length of about 21.3 moves and use about
100MB of memory.

Call this function to get a solver ready to go with pruning tables
built.  It might take a second or two to return.

--]]

function getSolver()

--[[
Tunables.  The first two are the sizes of the hash tables; we pack
16 values per Lua array entry but each entry takes a couple dozen
bytes so the sizes are *very* roughly the amount of memory used.
You probably don't want to adjust these values as they have been
tuned for this particular usage (quick solutions of reasonable but
not optimal length).  For limited memory environments, the phase 1
and phase 2 table sizes can be reduced to 7000003 and 15000017,
respectively, with only about a 36% slowdown in solution time, so
still well under a second.

--]]

 local phase1tabsize, phase2tabsize = 32000011, 72000007 -- must be primes
 local maxp1prune, maxp2prune, maxp2searchdepth, maxp1solvecount = 7, 8, 12, 2

--[[

We would like to refer to faces and moves by an index from 1 to 6.
We use the order U F R D B L.  We initialize these in a function,
because we may need to reinitialize them for a new position.  Note
here that we are using color tables directly as table entries; this
is a lua thing.

]]--

 local facenamelist = {"U", "F", "R", "D", "B", "L"}
 local facelist, colorlist, colorindex, p1index = {}, {}, {}, {}
 local suffixes = {"","2","'"}
 local function symbolicmove(i)
    return facenamelist[i//3] .. suffixes[1+i%3]
 end

 local function make_facelist()
    facelist = {up_face.colors, front_face.colors, right_face.colors,
                down_face.colors, back_face.colors, left_face.colors}
    for i=1,6 do
       colorlist[i] = facelist[i][2][2]
       colorindex[facelist[i][2][2]] = i
       if i==1 or i==4 then
          p1index[facelist[i][2][2]] = 0
       elseif i==2 or i==5 then
          p1index[facelist[i][2][2]] = 1
       else
          p1index[facelist[i][2][2]] = 3
       end
    end
 end

--[[

We don't care too much about the cube representation, except that we need
to be able to match up stickers that belong to the same cubie, so we can
check the orientations.  This table gives the indices of
edges based on ufrdbl/index/index.  This requires careful examination of
the move routines to determine which edges match up.  Corners are given
zeros.  The ordering of these edges doesn't matter.  Here's a key:

 1 UF 2 UR 3 UB 4 UL 5 DF 6 DR 7 DB 8 DL 9 FR 10 BR 11 FL 12 BL
 13 UFL 14 ULB 15 UBR 16 URF 17 DFL 18 DRF 19 DBR 20 DLB

--]]

 local cubieindex = {{{13,4,14},{ 1,0, 3},{16,2,15}},  -- U (L is up)
                     {{13,1,16},{11,0, 9},{17,5,18}},  -- F (U is up)
                     {{16,2,15},{ 9,0,10},{18,6,19}},  -- R (U is up)
                     {{17,8,20},{ 5,0, 7},{18,6,19}},  -- D (L is up)
                     {{14,3,15},{12,0,10},{20,7,19}},  -- B (U is up)
                     {{13,4,14},{11,0,12},{17,8,20}}}; -- L (U is up)

--[[

We do solves along three different axes (though not on inverses).
To support this all we really need is a routine that conjugates a
position by a twist on an axis through the corners.

--]]

 local function rotate4(a)
    local t = a[1][1]
    a[1][1] = a[3][1]
    a[3][1] = a[3][3]
    a[3][3] = a[1][3]
    a[1][3] = t
    t = a[1][2]
    a[1][2] = a[2][1]
    a[2][1] = a[3][2]
    a[3][2] = a[2][3]
    a[2][3] = t
 end
 local function rotate3(a, b, c)
    rotate4(facelist[a])
    rotate4(facelist[a])
    rotate4(facelist[b])
    rotate4(facelist[c])
    for i=1,3 do
       for j=1,3 do
          local t = facelist[a][i][j]
          facelist[a][i][j] = facelist[b][i][j]
          facelist[b][i][j] = facelist[c][i][j]
          facelist[c][i][j] = t
       end
    end
 end
 local colorrotate = {3, 1, 2, 6, 4, 5}
 local function conjugate3()
    local recolor = {}
    rotate3(2, 3, 1)
    rotate3(5, 6, 4)
    for c=1,6 do recolor[colorlist[c]] = colorlist[colorrotate[c]] end
    for f=1,6 do
       for i=1,3 do
          for j=1,3 do facelist[f][i][j] = recolor[facelist[f][i][j]] end
       end
    end
 end

--[[

From the cubie information and the ordering of the colors we can derive
Kociemba-style symcoords from the representation of the cube.  This
symcoord representation is important for speed.

--]]

 local faceorder = {1,4,2,5,3,6}
 local pack12c4, pack8p4, pack12p4 = {}, {}, {}
 local unpack12c4, unpack8p4, unpack12p4 = {}, {}, {}
 local color2cubie, cubieeg, cubiepg, cubielocg = {}, {}, {}, {}
 local function getsymcoords()
    local cubiee, cubiep = cubieeg, cubiepg
    for i=1,20 do cubiee[i] = 0 cubiep[i] = 0 end
    for fii=1,6 do
       local fi = faceorder[fii]
       local f = facelist[fi]
       for i=1,3 do
          local cifii = cubieindex[fi][i]
          local fsi = f[i]
          for j=1,3 do
             local e = cifii[j]
             if e ~= 0 then
                cubiee[e] = cubiee[e] * 4 + p1index[fsi[j]]
                cubiep[e] = cubiep[e] + (1<<(colorindex[fsi[j]]-1))
             end
          end
       end
    end
    local eo, val, mi, co = 0, 1, 0, 1
    for ci=1,12 do
       local cci = cubiee[ci]
       if (cci >> 2) < (cci & 3) then eo = eo + val end
       if (cci & 5) == 5 then mi = mi + val end
       val = 2 * val
    end
    eo = 1 + 18*(eo & 2047)
    val = 18
    for ci=13,19 do
       if (cubiee[ci] & 3) == 0 then
          co = co + val
       elseif ((cubiee[ci] >> 2) & 3) == 0 then
          co = co + 2*val
       end
       val = val * 3
    end
    local tope, mide, bote, topc, botc, cubieloc = 0, 0, 0, 0, 0, cubielocg
    for i=1,20 do cubieloc[color2cubie[cubiep[i]]] = i end
    for i=1,4 do
       tope = tope * 12 + cubieloc[i]-1
       bote = bote * 12 + cubieloc[i+4]-1
       mide = mide * 12 + cubieloc[i+8]-1
       topc = topc * 8 + cubieloc[i+12]-13
       botc = botc * 8 + cubieloc[i+16]-13
    end
    return {eo,co,pack12c4[mi], pack12p4[tope], pack12p4[bote], pack12p4[mide],
            pack8p4[topc], pack8p4[botc]}
 end

--[[

The main idea behind symcoords is to simplify both the move routines and
the hash routines.  For the move routines, symcoords turn moves into a
few lookups in small tables, and hashing into combining a few values.
For the Kociemba algorithm, further speed is gained by focusing on the
phase we are in.  We keep the eight symcoords separated into their own
variables so we don't need to do a table lookup.

--]]

 local curpos1, curpos2, curpos3, curpos4, curpos5, curpos6, curpos7, curpos8
 local sceo, scco, sccp, scep, scmp = {}, {}, {}, {}, {}
 local function coordmove1(face, twist)
    local mv = face * 3 + twist - 4
    curpos1 = sceo[curpos1+mv]
    curpos2 = scco[curpos2+mv]
    curpos3 = scmp[curpos3+mv]
 end
 local function coordmove2(face, twist)
    local mv = face * 3 + twist - 4
    curpos4 = scep[curpos4+mv]
    curpos5 = scep[curpos5+mv]
    curpos6 = scep[curpos6+mv]
    curpos7 = sccp[curpos7+mv]
    curpos8 = sccp[curpos8+mv]
 end

--[[

Sometimes we need to save the cube state to restore it later.  This does
not happen often.

--]]

 local function encodecube()
    local r = {}
    local at = 1
    for fi=1,6 do
       local f = facelist[fi]
       for i=1,3 do
          for j=1,3 do
             r[at] = f[i][j]
             at = at + 1
          end
       end
    end
    return r
 end
 local function restorecube(r)
    local at = 1
    for fi=1,6 do
       local f = facelist[fi]
       for i=1,3 do
          for j=1,3 do
             f[i][j] = r[at]
             at = at + 1
          end
       end
    end
 end

--[[

We initialize our hash tables by setting all values to infinity.
Each 64-bit integer slot in the Lua table holds 16 4-bit values.
We use the value 15 for infinity.  When actually doing a lookup,
we treat infinity as one plus the highest value we've populated
the hash table with, so far.

--]]

 local phase1table, phase2table = {}, {}

--[[

We create a number of tables here to pack and unpack permutations
and combinations from a sparse to a dense representation.

--]]

 local function bc(i)
    local r = 0
    while i > 0 do
       r = r + 1
       i = i & (i - 1)
    end
    return r
 end
 local function initpack()
    local at, ind = 1, 1
    for i=1,4096 do
       if bc(i) == 4 then
          pack12c4[i] = at
          unpack12c4[1 + at // 18] = i
          at = at + 18
       else
          pack12c4[i] = 0 -- this is just to get a dense array
       end
    end
    at = 0
    for a=1,12 do
       for b=1,12 do
          for c=1,12 do
             for d=1,12 do
                if a~=b and a~=c and a~=d and b~=c and b~=d and c~=d then
                   pack12p4[at] = ind
                   unpack12p4[1 + ind // 18] = at
                   ind = ind + 18
                elseif at ~= 0 then
                   pack12p4[at] = -1
                end
                at = at + 1
             end
          end
       end
    end
    at = 0
    ind = 1
    for a=1,8 do
       for b=1,8 do
          for c=1,8 do
             for d=1,8 do
                if a~=b and a~=c and a~=d and b~=c and b~=d and c~=d then
                   pack8p4[at] = ind
                   unpack8p4[1 + ind // 18] = at
                   ind = ind + 18
                elseif at ~= 0 then
                   pack8p4[at] = -1
                end
                at = at + 1
             end
          end
       end
    end
    for i=1,64 do color2cubie[i] = -1 end
    local cubiecolors = {}
    for i=1,20 do cubiecolors[i] = 0 end
    for fi=1,6 do
       for i=1,3 do
          for j=1,3 do
             local ci = cubieindex[fi][i][j]
             if ci ~= 0 then
                cubiecolors[ci] = cubiecolors[ci] + (1<<(fi-1))
             end
          end
       end
    end
    for i=1,20 do color2cubie[cubiecolors[i]] = i end
 end

 local startcoords
 local function savecoords()
    local o = {curpos1, curpos2, curpos3, curpos4,
               curpos5, curpos6, curpos7, curpos8}
    curpos1 = startcoords[1]
    curpos2 = startcoords[2]
    curpos3 = startcoords[3]
    curpos4 = startcoords[4]
    curpos5 = startcoords[5]
    curpos6 = startcoords[6]
    curpos7 = startcoords[7]
    curpos8 = startcoords[8]
    return o
 end
 local function restorecoords(o)
    curpos1 = o[1] 
    curpos2 = o[2] 
    curpos3 = o[3] 
    curpos4 = o[4] 
    curpos5 = o[5] 
    curpos6 = o[6] 
    curpos7 = o[7] 
    curpos8 = o[8] 
 end
 local function p1solved()
    return startcoords[1] == curpos1 and startcoords[2] == curpos2 and
           startcoords[3] == curpos3
 end
 local function coordsolved()
    return startcoords[1] == curpos1 and startcoords[2] == curpos2 and
           startcoords[3] == curpos3 and startcoords[4] == curpos4 and
           startcoords[5] == curpos5 and startcoords[6] == curpos6 and
           startcoords[7] == curpos7 and startcoords[8] == curpos8
 end

--[[

This recursive routine populates the phase 1 table at a particular
depth.

--]]

 local p1depth, p2depth = 0, 0
 local function phase1pop(togo, lastface)
    if togo == 0 then
       local h = (curpos1 * 6231697 + curpos2 * 16627661 +
                  curpos3 * 9367781) % phase1tabsize
       local hhi = 1 + (h >> 4)
       local hlo = 4*(h&15)
       if (phase1table[hhi]>>hlo)&15 > p1depth then
          phase1table[hhi] = phase1table[hhi] - ((maxp1prune-p1depth)<<hlo)
       end
    else
       for f=1,6 do
          if f ~= lastface and f+3 ~= lastface and
             (lastface > 0 or (f ~= 1 and f ~= 4)) then
             for twist=1,3 do
                coordmove1(f, 1)
                if lastface > 0 or twist==1 then
                   phase1pop(togo-1, f)
                end
             end
             coordmove1(f, 1)
          end
       end
    end
 end
 local function extendp1()
    local o = savecoords()
    phase1pop(p1depth, -1)
    p1depth = p1depth + 1
    restorecoords(o)
 end

--[[

Similar, but for phase 2, and skipping moves that are not part of
phase 2.

--]]

 local function phase2pop(togo, lastface)
    if togo == 0 then
       local h = (curpos4 * 6231697 + curpos5 * 16627661 +
                  curpos6 * 9367781 + curpos7 * 10049393 +
                  curpos8 * 646979) % phase2tabsize
       local hhi = 1 + (h >> 4)
       local hlo = 4*(h&15)
       if (phase2table[hhi]>>hlo)&15 > p2depth then
          phase2table[hhi] = phase2table[hhi] - ((maxp2prune-p2depth)<<hlo)
       end
    else
       for f=1,6 do
          if f ~= lastface and f+3 ~= lastface then
             if f==1 or f==4 then
                for twist=1,3 do
                   coordmove2(f, 1)
                   phase2pop(togo-1, f)
                end
                coordmove2(f, 1)
             else
                coordmove2(f, 2)
                phase2pop(togo-1, f)
                coordmove2(f, 2)
             end
          end
       end
    end
 end
 local function extendp2()
    local o = savecoords()
    phase2pop(p2depth, -1)
    p2depth = p2depth + 1
    restorecoords(o)
 end

 local function inithash()
    local oneval = ((1<<62)//15*4+1)*maxp1prune
    for i=1,(phase1tabsize>>4)+1 do phase1table[i] = oneval end
    local oneval = ((1<<62)//15*4+1)*maxp2prune
    for i=1,(phase2tabsize>>4)+1 do phase2table[i] = oneval end
    for i=1,maxp1prune do extendp1() end
    for i=1,maxp2prune do extendp2() end
 end

--[[

Here's our phase2 solver.

--]]

 local bestsollen, p1len, moveptr, globalaxis
 local movelist, bestsollist, bestsol, p1solvecount = {}, {}, "", 0
 local function recurp2(togo, lastface)
    local h = (curpos4 * 6231697 + curpos5 * 16627661 +
               curpos6 * 9367781 + curpos7 * 10049393 +
               curpos8 * 646979) % phase2tabsize
    local d = (phase2table[1+(h>>4)]>>(4*(h&15)))&15
    if d > togo then return end
    if togo == 0 then
       if coordsolved() then
          bestsollist = {}
          bestsollen = moveptr-1
          bestsol = ""
          for i=1,moveptr-1 do
             local corr = (movelist[i]-3)//3%3 -- correct for axis choice
             corr = (corr+globalaxis-1)%3 - corr
             bestsollist[i] = movelist[i] + 3 * corr
             bestsol = bestsol .. " " .. symbolicmove(bestsollist[i])
          end
          print("Found new solution at length", bestsollen, p1len)
          print(bestsol)
          return true
       else
          return false
       end
    else
       local solved = false
       for f=1,6 do
          if f ~= lastface and f+3 ~= lastface then
             if f==1 or f==4 then
                for twist=1,3 do
                   coordmove2(f, 1)
                   if not solved then
                      movelist[moveptr] = f*3+twist-1
                      moveptr = moveptr + 1
                      solved = recurp2(togo-1, f)
                      moveptr = moveptr - 1
                   end
                end
                coordmove2(f, 1)
             else
                coordmove2(f, 2)
                movelist[moveptr] = f*3+1
                moveptr = moveptr + 1
                solved = recurp2(togo-1, f)
                moveptr = moveptr - 1
                coordmove2(f, 2)
             end
          end
          if solved then return true end
       end
       return false
    end
 end
 local function solvep2(lastface)
    for i=1,moveptr-1 do coordmove2(movelist[i]//3, movelist[i]%3+1) end
    for togo=0,bestsollen-1-p1len do
       if togo <= maxp2searchdepth and recurp2(togo, lastface) then
          for i=moveptr-1,1,-1 do
             coordmove2(movelist[i]//3, 3-movelist[i]%3)
          end
          return
       end
    end
    for i=moveptr-1,1,-1 do coordmove2(movelist[i]//3, 3-movelist[i]%3) end
 end
 local function recurp1(togo, lastface)
    local h = (curpos1 * 6231697 + curpos2 * 16627661 +
               curpos3 * 9367781) % phase1tabsize
    local d = (phase1table[1+(h>>4)]>>(4*(h&15)))&15
    if d > togo or (p1solvecount >= maxp1solvecount and bestsollen < 40) then
       return
    end
    if togo == 0 then
       if p1solved() then
          solvep2(lastface)
          p1solvecount = p1solvecount + 1
       end
    elseif false and d == 1 and togo == 1 then
       local s3, mv = startcoords[3], -1
       if scmp[curpos3+3] == s3 then
          mv = 2
       elseif scmp[curpos3+6] == s3 then
          mv = 3
       elseif scmp[curpos3+12] == s3 then
          mv = 5
       elseif scmp[curpos3+15] == s3 then
          mv = 6
       else
          print("***   Failed in recurp1   ***")
       end
       coordmove1(mv, 1)
       movelist[moveptr] = mv*3
       moveptr = moveptr + 1
       if p1solved() and p1solvecount < maxp1solvecount then
          solvep2(lastface)
       end
       p1solvecount = p1solvecount + 1
       coordmove1(mv, 2)
       if p1solved() and p1solvecount < maxp1solvecount then
          movelist[moveptr-1] = mv*3+2
          solvep2(lastface)
          p1solvecount = p1solvecount + 1
       end
       moveptr = moveptr - 1
       coordmove1(mv, 1)
    else
       for f=1,6 do
          if f ~= lastface and f+3 ~= lastface then
             for twist=1,3 do
                coordmove1(f, 1)
                movelist[moveptr] = f*3+twist-1
                moveptr = moveptr + 1
                recurp1(togo-1, f)
                moveptr = moveptr - 1
             end
             coordmove1(f, 1)
          end
       end
    end
 end
 local axes = {}
 local function presolve()
    for i=1,3 do
       axes[i] = getsymcoords()
       conjugate3()
    end
 end
 local function solvep1()
    moveptr, bestsollen, p1solvecount = 1, 40, 0
    for togo=0,bestsollen do
       for a=1,3 do
          globalaxis = a
          if togo > bestsollen then return end
          restorecoords(axes[a])
          p1len = togo
          recurp1(togo, -1)
       end
    end
 end
 local function gensymperms()
    local startpos, edgemoves, cornermoves = encodecube(), {}, {}
    startcoords = getsymcoords()
    for mv=0,17 do
       restorecube(startpos)
       domove(1+mv//3, 1+mv%3)
       local dst = getsymcoords()
       for i=4,6 do
          local src4 = unpack12p4[1 + startcoords[i] // 18]
          local dst4 = unpack12p4[1 + dst[i] // 18]
          for j=1,4 do
             local srcp = src4 % 12
             local dstp = dst4 % 12
             edgemoves[1+srcp*18+mv] = dstp
             src4 = src4 // 12
             dst4 = dst4 // 12
          end
       end
       for i=7,8 do
          local src4 = unpack8p4[1 + startcoords[i] // 18]
          local dst4 = unpack8p4[1 + dst[i] // 18]
          for j=1,4 do
             local srcp = src4 % 8
             local dstp = dst4 % 8
             cornermoves[1+srcp*18+mv] = dstp
             src4 = src4 // 8
             dst4 = dst4 // 8
          end
       end
    end
    for i=1,18*11881 do scep[i] = 0 end
    for i=1,18*496 do scmp[i] = 0 end
    for i=0,11879 do
       local srcp = unpack12p4[1+i]
       for mv=0,15,3 do
          local t, mul, dstp, srcbits, dstbits = srcp, 1, 0, 0, 0
          for j=1,4 do
             local pos = t % 12
             t = t // 12
             srcbits = srcbits | (1<<pos)
             local dpos = edgemoves[1+18*pos+mv]
             dstbits = dstbits | (1<<dpos)
             dstp = dstp + mul * dpos
             mul = mul * 12
          end
          scep[1+18*i+mv] = pack12p4[dstp]
          scmp[pack12c4[srcbits]+mv] = pack12c4[dstbits]
       end
    end
    for i=1,18*1681 do sccp[i] = 0 end
    for i=0,1679 do
       local srcp = unpack8p4[1+i]
       for mv=0,15,3 do
          local t, mul, dstp = srcp, 1, 0
          for j=1,4 do
             local pos = t % 8
             dstp = dstp + mul * cornermoves[1+18*(t%8)+mv]
             t = t // 8
             mul = mul * 8 
          end
          sccp[1+18*i+mv] = pack8p4[dstp]
       end
    end
 end
 local function gensymcoord()
    local outer = encodecube()
    ResetCube()
    gensymperms()
    ResetCube()
    local q, qg = {}, 2
    q[1] = encodecube()
    local src = startcoords
    q[2] = src
    for i=1,18*2049 do sceo[i] = 0 end
    for i=1,18*2188 do scco[i] = 0 end
    sceo[src[1]] = -1
    scco[src[2]] = -1
    while qg > 0 do
       src = q[qg]
       qg = qg - 1
       local srco = q[qg]
       qg = qg - 1
       restorecube(srco)
       if sceo[src[1]] < 0 or scco[src[2]] < 0 then
          for mv=0,15,3 do
             restorecube(srco)
             domove(1+mv//3, 1+mv%3)
             local dst, need = getsymcoords(), false
             if sceo[dst[1]] == 0 then
                need = true
                sceo[dst[1]] = -1
             end
             sceo[src[1]+mv] = dst[1]
             if scco[dst[2]] == 0 then
                need = true
                scco[dst[2]] = -1
             end
             scco[src[2]+mv] = dst[2]
             if need then
                qg = qg + 1
                q[qg] = encodecube()
                qg = qg + 1
                q[qg] = dst
             end
          end
       end
    end
    restorecube(outer)
    for mv=0,15,3 do
       for mp=0,494 do
          local b = 1 + 18 * mp + mv
          scmp[b+1] = scmp[scmp[b]+mv]
          scmp[b+2] = scmp[scmp[scmp[b]+mv]+mv]
       end
       for cp=0,1679 do
          local b = 1 + 18 * cp + mv
          sccp[b+1] = sccp[sccp[b]+mv]
          sccp[b+2] = sccp[sccp[sccp[b]+mv]+mv]
       end
       for ep=0,11879 do
          local b = 1 + 18 * ep + mv
          scep[b+1] = scep[scep[b]+mv]
          scep[b+2] = scep[scep[scep[b]+mv]+mv]
       end
       for eo=0,2047 do
          local b = 1 + 18 * eo + mv
          sceo[b+1] = sceo[sceo[b]+mv]
          sceo[b+2] = sceo[sceo[sceo[b]+mv]+mv]
       end
       for co=0,2186 do
          local b = 1 + 18 * co + mv
          scco[b+1] = scco[scco[b]+mv]
          scco[b+2] = scco[scco[scco[b]+mv]+mv]
       end
    end
 end
 local function solveCube()
    local safesavemove = savemove
    savemove = false
    presolve()
    solvep1()
    savemove = safesavemove
    return bestsollist
 end
 make_facelist()
 initpack()
 gensymcoord()
 inithash()
 return solveCube
end

local cubeSolver = nil

--------------------------------------------------------------------------------

function SolveCube()
    if CubeSolved() then return end
    
    cv.cursor("wait")
    savemove = false    -- so domove calls won't change undostack
    animate = false     -- and don't animate moves

    if cubeSolver == nil then
        -- display a pop-up window (only needs to be shown once)
        cv.rgba(cp.black)
        local wd, ht = cv.text("msg", [[
Initializing tables for cube solver.
This only needs to be done once...]])
        wd = wd+40
        ht = ht+40
        local x = (cvwd-wd)//2
        local y = (cvht-ht)//2
        cp.round_rect(x, y, wd, ht, 6, 1, cp.white)
        cv.paste("msg", x+20, y+20)
        cv.delete("msg")
        cv.update()
    end

    local saveprint = print
    if disableprint then print = function()end end
    local t0 = os.clock()
    if cubeSolver == nil then cubeSolver = getSolver() end
    local t1 = os.clock()
    local bestsollist = cubeSolver()
    local t2 = os.clock()

    print(string.format("Initialization time: %.2f secs", t1-t0))
    print(string.format("Solve time: %.2f secs", t2-t1))
    
    -- clear msg and do the best solution (saving and animating moves)
    Refresh()
    savemove = true
    animate = true
    -- temporarily stop gc to avoid pauses mid-animation
    collectgarbage("stop")
    for i=1,#bestsollist do
        domove(bestsollist[i]//3, bestsollist[i]%3+1)
        Refresh()
    end
    collectgarbage("restart")
    collectgarbage("collect")
    if not CubeSolved() then
        glu.warn("*** FAILED SOLUTION! ***")
    end
    print = saveprint
    cv.cursor("arrow")
end

--------------------------------------------------------------------------------

function UndoRotation()
    if #undostack > 0 then
        -- pop move off undostack
        local move = table.remove(undostack)
        -- push move onto redostack
        redostack[#redostack+1] = move
        -- undo move (ie. rotate face in oppsite direction)
        savemove = false
        move.rotatecall(not move.arg)
        savemove = true
    end
end

--------------------------------------------------------------------------------

function RedoRotation()
    if #redostack > 0 then
        -- pop move off redostack
        local move = table.remove(redostack)
        -- push move onto undostack
        undostack[#undostack+1] = move
        -- redo move
        savemove = false
        move.rotatecall(move.arg)
        savemove = true
    end
end

--------------------------------------------------------------------------------

function ShowHelp()
    glu.note([[
Keyboard commands:

Hit F/B/U/D/R/L to rotate faces clockwise.
Hit shift-F/B/U/D/R/L to rotate anti-clockwise.
Hit Z to undo a face rotation.
Hit shift-Z to redo a face rotation.

Hit left/right arrows to rotate cube about Y axis.
Hit up/down arrows to rotate cube about X axis.
Hit alt-left/right arrows to rotate about Z axis.
Hit enter/return to restore initial viewpoint.

Hit space bar to toggle auto-rotation.
Hit P to toggle print function.
Hit T to toggle timing data.
Hit H to see this help.
Hit escape to exit.
]])
end

--------------------------------------------------------------------------------

function CreateButtons()
    cp.textshadowx = 2
    cp.textshadowy = 2
    cp.border = 1
    cp.buttonrgba = {0,100,255,255}
    
    cp.buttonwd = 60
    exit_button = cp.button("Exit", glu.exit)
    exit_button.setbackcolor(cp.red)
    help_button = cp.button("Help", ShowHelp)
    undo_button = cp.button("Undo", UndoRotation)
    redo_button = cp.button("Redo", RedoRotation)

    cp.buttonwd = 130
    scramble_button = cp.button("Scramble", ScrambleCube)
    solve_button = cp.button("Solve", SolveCube)
    reset_button = cp.button("Reset", ResetCube, {true}) -- also calls InitialView

    cp.buttonwd = 60
    fc_button = cp.button("F",  RotateFrontFace, {true})
    fa_button = cp.button("F'", RotateFrontFace, {false})
    bc_button = cp.button("B",  RotateBackFace, {true})
    ba_button = cp.button("B'", RotateBackFace, {false})
    uc_button = cp.button("U",  RotateUpFace, {true})
    ua_button = cp.button("U'", RotateUpFace, {false})
    dc_button = cp.button("D",  RotateDownFace, {true})
    da_button = cp.button("D'", RotateDownFace, {false})
    rc_button = cp.button("R",  RotateRightFace, {true})
    ra_button = cp.button("R'", RotateRightFace, {false})
    lc_button = cp.button("L",  RotateLeftFace, {true})
    la_button = cp.button("L'", RotateLeftFace, {false})
end

--------------------------------------------------------------------------------

function HandleKey(event)
    if event == "key return none" then
        InitialView()
        autorotate = false
    elseif event == "key space none" then
        autorotate = not autorotate
    elseif event == "key t none" then
        showtime = not showtime
        if not showtime then glu.setoption("showstatusbar", 0) end
    elseif event == "key p none" then
        disableprint = not disableprint
    elseif event == "key h none" then
        ShowHelp()
    elseif event == "key f none" then  RotateFrontFace(true)
    elseif event == "key f shift" then RotateFrontFace(false)
    elseif event == "key b none" then  RotateBackFace(true)
    elseif event == "key b shift" then RotateBackFace(false)
    elseif event == "key u none" then  RotateUpFace(true)
    elseif event == "key u shift" then RotateUpFace(false)
    elseif event == "key d none" then  RotateDownFace(true)
    elseif event == "key d shift" then RotateDownFace(false)
    elseif event == "key l none" then  RotateLeftFace(true)
    elseif event == "key l shift" then RotateLeftFace(false)
    elseif event == "key r none" then  RotateRightFace(true)
    elseif event == "key r shift" then RotateRightFace(false)
    elseif event == "key z none" then  UndoRotation()
    elseif event == "key z shift" then RedoRotation()
    elseif event == "key left none" then  RotateCube( 0,  5,  0)
    elseif event == "key right none" then RotateCube( 0, -5,  0)
    elseif event == "key up none" then    RotateCube( 5,  0,  0)
    elseif event == "key down none" then  RotateCube(-5,  0,  0)
    elseif event == "key right alt" then  RotateCube( 0,  0,  5)
    elseif event == "key left alt" then   RotateCube( 0,  0, -5)
    end
end

--------------------------------------------------------------------------------

function EventLoop()
    local mousedown = false -- mouse button is down?
    local prevx, prevy      -- previous mouse position

    while true do
        local event = glu.getevent()
        local refresh = #event > 0  -- most events require a refresh
        if #event == 0 then
            -- don't hog cpu if idle
            if not mousedown then glu.sleep(5) end
            -- check if user resized window
            if ViewSizeChanged() then refresh = true end
        else
            -- handle click in a button
            event = cp.process(event)
        end
        if event:find("^cclick") then
            local _, x, y, button, mods = gp.split(event)
            x, y = tonumber(x), tonumber(y)
            local color = {cv.getpixel(x,y)}
            if x > leftgap and (not gp.equal(color,bg_color)) and
                button == "left" and mods == "none" then
                mousedown = true
                cv.cursor("hand")
                autorotate = false
                prevx, prevy = x, y
            end
        elseif event == "mup left" then
            mousedown = false
            cv.cursor("arrow")
        elseif event:find("^key") then
            HandleKey(event)
        end

        local x, y = cv.getxy()
        if x >= 0 and y >= 0 and mousedown then
            if x ~= prevx or y ~= prevy then
                -- mouse has moved so rotate the cube
                RotateCube(prevy-y, prevx-x, 0)
                prevx, prevy = x, y
                refresh = true
            end
        end
        
        if autorotate then
            RotateCube(0.3, 0.5, 0.7)
            refresh = true
        end

        if refresh then Refresh() end
    end
end

--------------------------------------------------------------------------------

function Main()
    glu.settitle("Rubik's Cube")
    glu.setcolor("viewport", unpack(bg_color))
    glu.setview(cvwd, cvht)
    cv.create()
    xo = leftgap + (cvwd-leftgap)//2
    yo = cvht//2
    CreateButtons()
    CreateCube()
    CreateFaces()
    SetScale()
    InitialView()
    Refresh()
    EventLoop()
end

--------------------------------------------------------------------------------

status, err = xpcall(Main, gp.trace)
if err then glu.continue(err) end
-- the following code is always executed
cv.delete()
