Skip to content

Latest commit

 

History

History
248 lines (195 loc) · 6.07 KB

presentation-sbtb-2021.org

File metadata and controls

248 lines (195 loc) · 6.07 KB

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

Say hello to my cube

An Intution for Groups

Definition

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

Permutations

  • 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

A finite permutation group

  • `a` and `b` generate a group with six elements (S3)
  • much like how all cube state is generate by six face turns
  • Bijections and permutations are one and the same thing

Cayley’s Theorem

// for any A with Group[A]
val a: A

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

val g: A => A = (a.inverse * _)
  • all group elements are bijections
  • every group is an isomorphism group
  • (side note: Yoneda)

Recap

  • Groups are about transformations
  • Every group <-> Permutation group
  • Permutations computations are useful
  • Represent functions as data
  • We can leverage centuries of group theory

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”
  • (eg., Corners are the 2x2x2 cube)

Operations (On-screen demo)

  • Face turns are paired 4-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

Commutators

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

Parity

  • Perms composed of even/odd swaps
  • Even perms can be composed from 3-cycles
  • Edges and corners share parity

Conjugates

  • A * B * A’
  • We can re-use simple algorithms by conjugating
  • If B is in a normal subgroup, so is its conjugation
  • Corner/Edge Orientation/Permutation are all subgroups
  • Demo (repl and cube)

Generating Algorithms

  • Create conjugate variations of a commutator
  • Reflect across axis
  • Find commutators by looking for

Live Demonstration

Look at the other screen!

Summary

Key takeaways

  • Groups are about space transformations
  • We can turn actions into data
  • We can rely on theory when intuition fails

Thank you