#+title: Solving Rubik's Cube with Group Theory and Functional Programming
#+author: Stewart Stewart (t: @stewSqrd, gh: @stewSquared)
# /email: stewinsalot@gmail.com

* (GT |+| FP).solve(RC)
** Introduction
*** Agenda
- Learn about the Group typeclass and permutations
- See how theory informs our Model and DSL design
- Solve a Rubik's Cube using these insights

*** COMMENT
- Theory helps us understand and solve problems
- When you interpret your words as data, that data can be tweaked
- FP lets us leverage theory to express solutions
- `Group` and `Perm` implementations exist!
- but they don't get much mention
- interested in DSL design
- generally interested in group theory
- The group theorist J. L. Alperin has written that "The typical example of a finite group is the general linear group of n dimensions over the field with q elements. The student who is introduced to the subject with other examples is being completely misled." ^^;

See spire.optional.Perm and cats.kernel.Group

*** Say hello to my cube

** An Intution for Groups
*** Definition of Group
**** Recap: Monoid Typeclass
#+BEGIN_SRC scala
trait Monoid[A] {
  def empty: A // identity
  def combine(a: A, b: A): A
}

implicit val monoidInt: Group[Int] = new Group[Int] {
  def empty: Int = 0
  def combine(a: Int, b: Int): Int = a + b
}
#+END_SRC

**** Group Typeclass
#+BEGIN_SRC scala
trait Group[A] extends Monoid[A] {
  def inverse(a: A): A
}

implicit val groupInt: Group[Int] = new Group[Int] {
  def empty: Int = 0
  def inverse(a: Int): Int = -a
  def combine(a: Int, b: Int): Int = a + b
}
#+END_SRC

**** COMMENT Group Typeclass (full)

#+BEGIN_SRC scala
trait Group[A] {
  def empty: A // identity
  def inverse(a: A): A
  def combine(a: A, b: A): A
}

implicit val groupInt: Group[Int] = new Group[Int] {
  def empty: Int = 0
  def inverse(a: Int): Int = -a
  def combine(a: Int, b: Int): Int = a + b
}
#+END_SRC

**** COMMENT Talking Points

- Groups are everywhere
- This definition is abstract
- It's not obvious why inverse is interesting
- It's not obvious how this helps us solve the cube
- Is the cube a group? Squint your eyes?
- Instead, we'll develop an intution for groups

*** Permutations
**** Perm (Demo)

#+BEGIN_SRC scala

val id = Perm()

val a = Perm(1, 2)

val b = Perm(1, 3, 2)

#+END_SRC

**** COMMENT Demo Points
- show traditional permutations
- introduce action on Int
- introduce composition/comparison
  - notably, non-commutative
  - also, building from pairs
  - save parity for later
- multi-cycle permutations
- introduce inverse

**** COMMENT S3: Symmetric group on three elements

#+BEGIN_SRC scala

a * a == Perm() // == b * b * b
a     == Perm(1, 2)
a * b == Perm(1, 3)
b * a == Perm(2, 3)
b     == Perm(1, 3, 2)
b * b == Perm(1, 2, 3) // a * b * a

#+END_SRC

- this is all the permutations of three elements
- this is also the symmetries of a triangle (D3)

**** COMMENT Cayley Table

|---------+---------+---------+---------+---------+---------+---------|
|         | ()      | (1 2)   | (1 3)   | (2 3)   | (1 3 2) | (1 2 3) |
|---------+---------+---------+---------+---------+---------+---------|
| ()      | ()      | (1 2)   | (1 3)   | (2 3)   | (1 3 2) | (1 2 3) |
| (1 2)   | (1 2)   | ()      | (1 3 2) | (1 2 3) | (1 3)   | (2 3)   |
| (1 3)   | (1 3)   | (1 2 3) | ()      | (1 3 2) | (2 3)   | (1 2)   |
| (2 3)   | (2 3)   | (1 3 2) | (1 2 3) | ()      | (1 2)   | (1 3)   |
| (1 3 2) | (1 3 2) | (2 3)   | (1 2)   | (1 3)   | (1 2 3) | ()      |
| (1 2 3) | (1 2 3) | (1 3)   | (2 3)   | (1 2)   | ()      | (1 3 2) |
|---------+---------+---------+---------+---------+---------+---------|

**** COMMENT Expanded (de)composition example
#+BEGIN_SRC scala
Perm(1, 2)(3, 1) == Perm(1, 2, 3)

Perm(1, 2, 3)(4, 1) == Perm(1, 2, 3, 4)

Perm(1, 2, 3, 4)(4, 3) == Perm(1, 2, 3)

Perm(1, 2, 3)(3, 2) == Perm(1, 2)


Perm(1, 2)(2, 3, 4) == Perm(1, 2, 3, 4)

Perm(1, 2)(1, 2, 3, 4) == Perm(2, 3, 4)


Perm(1, 2)(1, 3)(1, 4) == Perm(1, 2, 3, 4)
Perm(1, 2, 3, 4) * Perm(4, 3)(3, 2)(2, 1) == Perm()
#+END_SRC

**** COMMENT Generic Code template
#+BEGIN_SRC scala

#+END_SRC

**** Recap
Perms
- are functions
- have an identity
- can be (de)composed
- can be inverted (bijections)
- form a group!

**** Group[Perm]

#+BEGIN_SRC scala
implicit val PermGroup extends Group[Perm] {

  def empty = Perm()

  def inverse(a: Perm) = a.inverse

  def combine(a: Perm, b: Perm) = x.compose(y)
}

// Total (closed under combine)
// Associative: (a * b) * c == a * (b * c)
// Identity: a * id = a
// Inverse: a * a.inverse == a
// Not necessarily commutative!
//   a * b != b * a

#+END_SRC

**** S3 Diagram
(See drawing)
**** Bijection Diagram
(See drawing)
**** COMMENT Demo Points

- introduce order
- these six elements form a finite group
- they are generated by two elements
  - (much like all cube states are generated by six face turns)
- show pictures
  - S3
  - Bijection
- Any bijection defines a permutation
- Bijections <-> Permutations

- Why show this group?
  1. Permutations of stickers?
  2. History, less abstract
  3. Example of non-commutative w/ generators
  4. Cayley's Theorem, which we'll show next

**** Cayley's Theorem

#+BEGIN_SRC scala

// for any A with Group[A]

val a: A

val f: A => A = (a * _)

val g: A => A = (a.inverse * _)

#+END_SRC

**** COMMENT Demo points

- given a Group of elements
- we can use an element to define a function
- inverting the function is trivial
- this means any element defines a bijection
- Every Group is isomorphic to a permutation group!
- This result is known as Cayley's theorem
- (Side note: This is also the Yoneda Lemma)

**** COMMENT Alternative intution for Cayley's Theorem

- Think of a multiplication table for a group
- Each row gives a function definition
- Each row contains all the elements
- If not, unique, can't have inverses
- Each element then defines a permutation!
- Every group is a permutation group!!!

**** Recap
- Permutations form a group
- Permutations <-> Bijections
- Every group <-> Permutation group

** Rubik's Cube
*** Mechanical Structure
**** Structure (On-screen demo)
- Permutation of 20 pieces
- Two types of pieces
- Pieces have orientations (small cycles)
- Corner/Edge have distinct permutations
- Corresponds to two "sub-puzzles"

**** Operations (On-screen demo)
- A face turn as cycles
- turns sometimes affect orientation
- face turns are associative and have inverse
- is that enough to know it's a group?

*** The Rubik's Cube Group
**** Case Classes
#+BEGIN_SRC scala

case class CubeState(corners: Corners, edges: Edges)

case class Corners(permutation: Perm8, orientation: CO)

case class Edges(permutation: Perm12, orientation: EO)

type CO = Vector[Cycle3] // generated by three-cycle

type EO = Vector[Cycle2] // generated by two-cycle

#+END_SRC

- Corners and Edges are themselves groups
- Even individual orientations are groups
- Groups all the way down!
- (I'm lying about type safety)

**** CubeState Group
#+BEGIN_SRC scala
object CubeStateGroup extends Group[CubeState] {
def combine(x: CubeState, y: CubeState) = CubeState(
   x.corners * y.corners,
   x.edges * y.edges
 )
 def empty = CubeState.id
 def inverse(a: CubeState) = CubeState(a.corners.inv, a.edges.inv)
}
#+END_SRC

- This is exactly the "direct product" of two groups
- CubeStateGroup = CornersGroup X EdgesGroup
- order(cube states) = order(corners) * order(edges)
- (technically, we overcount -- addressed later)

**** Corners Group
#+BEGIN_SRC scala
object CornersGroup extends Group[Corners] {

  def combine(x: CornersState, y: CornersState) = Corners(
    y.perm * x.perm,
    y.ori * y.perm.act(x.ori)
  )
  def empty = CornersState.id
  def inverse(a: CornersState) = CornersState(
    a.perm.inv,
    a.perm.inv.act(a.ori).inv
  )
}
#+END_SRC

- This is called the inner "semidirect product" of two groups
- It's a tad more complicated (see appendix)

**** Orientation
#+BEGIN_SRC scala
implicit object COGroup extends Group[CO] {
  def empty = CO(Vector.fill(8)(Cycle8.id))
  def inverse(a: CO) = CO(a.os.map(o => -o))
  def combine(a: CO, b: CO) = CO(a.os.zip(b.os).map(_ + _))
}

implicit object PermCOGroupAction extends GroupAction[CO, Perm] {
  def act(perm: Perm, co: CO): CO =
    CO(perm.permute(co.os))
}
#+END_SRC

- uhhh... ask me about this later
- But hey! Groups all the way down!

**** Representing Face Turns
#+BEGIN_SRC scala
val up    = Corners(Perm(1,2,3,4), CO(0,0,0,0,0,0,0,0))
val down  = Corners(Perm(5,6,7,8), CO(0,0,0,0,0,0,0,0))
val right = Corners(Perm(1,4,5,8), CO(2,0,0,1,2,0,0,1))
val left  = Corners(Perm(2,7,6,3), CO(0,1,2,0,0,1,2,0))
val front = Corners(Perm(1,8,7,2), CO(1,2,0,0,0,0,1,2))
val back  = Corners(Perm(3,6,5,4), CO(0,0,1,2,1,2,0,0))
#+END_SRC
- See source code for full state with edges

** Developing a Solution
*** A note about parity
- Perms composed of even/odd swaps
- If we have an even perm, compose from 3-cycles
- Edges and corners share parity

*** Commutators
- A * B * A' * B'
- When two cycles overlap at a single point
- Their commutator is a three cycle
- Demo (repl and cube)

*** Conjugates
- A * B * A'
- We can re-use simple algorithms by conjugating
- If B is on a normal subgroup, our choice of A is limitless
- Corner/Edge Orientation/Permutation are all subgroups
- Demo (repl and cube)

*** We can quickly generate commutators
- Create conjugate variations of a commutator
- Reflect across axis
- Find commutators by looking for 

*** COMMENT Steps
Approach One:
- Notice our state is permutations
- These subgroup perms are independent
- Can we decompose these into more manageable chunks?
- Remember we can decompose into transpositions
- We can pair transpositions for three-cycles
- We can develop algorithms for three-cycles
- Introduce commutators

Approach Two:
- Try to do a minimal useful thing
- Introduce commutators
- Show single intersection
- Demonstrate on a cube
- How can we use that?

Maybe add:
- How to spot a subgroup?
- Caveat -- groups are also used to find a minimial solution, but not in this way

** Demonstration

Live code time!

** Summary
*** Key takeaways
- Groups are about space transformations
- We can turn actions into data
- We can rely on theory when intuition fails

*** Thank you
- I'll be streaming more with this library at [[https://www.twitch.tv/stewSquared][twitch.tv/stewSquared]]
- See my code at [[https://github.com/stewSquared/twisty-groups][github.com/stewSquared/twisty-groups]]
- Contact me via twitter: [[twitter.com/stewSqrd][@stewSqrd]] or [[mailto:stewinsalot@gmail.com][stewinsalot@gmail.com]]

*** TODO Future Work

*** Resources
**** TODO Reading on Rubik's Cubes
**** TODO Programming Libraries
**** TODO Other references
**** TODO Tools Used