presentation-notes.org

Solving Rubik’s Cube with Group Theory and Functional Programming

(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

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
}

Group Typeclass

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
}

Permutations

Perm (Demo)

val id = Perm()

val a = Perm(1, 2)

val b = Perm(1, 3, 2)

Recap

Perms

• are functions
• have an identity
• can be (de)composed
• can be inverted (bijections)
• form a group!

Group[Perm]

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

S3 Diagram

(See drawing)

Bijection Diagram

(See drawing)

Cayley’s Theorem

// for any A with Group[A]

val a: A

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

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

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

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

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

CubeState Group

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)
}

• 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

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
  )
}

• This is called the inner “semidirect product” of two groups
• It’s a tad more complicated (see appendix)

Orientation

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))
}

• uhhh… ask me about this later
• But hey! Groups all the way down!

Representing Face Turns

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

• 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

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 twitch.tv/stewSquared
• See my code at github.com/stewSquared/twisty-groups
• Contact me via twitter: @stewSqrd or [email protected]

Future Work

Resources

Reading on Rubik’s Cubes

Programming Libraries

Other references

Tools Used