calculate the order of a Rubik's cube sequence

rubik.rb

class Rubik
  attr_reader :edges, :corners

  def initialize
    @edges = {
      :position => (1..12).to_a,
      :orientation => [0] * 12
    }
    @corners = {
      :position => (1..8).to_a,
      :orientation => [0] * 8
    }
  end

  def corner_cycles
    cycles_of(@corners)
  end

  def edge_cycles
    cycles_of(@edges)
  end

  def u
    permute_edges!   1, 2, 3, 4
    permute_corners! 1, 2, 3, 4
    self
  end

  def u2
    u.u
  end

  def ui
    u.u.u
  end

  def r
    permute_edges!   4, 7, 12, 8
    permute_corners! 4, 3,  8, 7
    twist_corners_cw!  3, 7
    twist_corners_ccw! 4, 8
    self
  end

  def r2
    r.r
  end

  def ri
    r.r.r
  end

  def f
    permute_edges!   1, 8, 9, 5
    flip_edges! 1, 8, 9, 5
    permute_corners! 1, 4, 7, 6
    twist_corners_cw!  4, 6
    twist_corners_ccw! 1, 7
    self
  end

  def f2
    f.f
  end

  def fi
    f.f.f
  end

  def d
    permute_edges!   9, 12, 11, 10
    permute_corners! 5, 6, 7, 8
    self
  end

  def d2
    d.d
  end

  def di
    d.d.d
  end

  def l
    permute_edges!   2, 5, 10, 6
    permute_corners! 1, 6,  5, 2
    twist_corners_cw!  1, 5
    twist_corners_ccw! 2, 6
    self
  end

  def l2
    l.l
  end

  def li
    l.l.l
  end

  def b
    permute_edges!   3, 6, 11, 7
    flip_edges! 3, 6, 11, 7
    permute_corners! 3, 2, 5, 8
    twist_corners_cw!  2, 8
    twist_corners_ccw! 3, 5
    self
  end

  def b2
    b.b
  end

  def bi
    b.b.b
  end

  def solved?
    self == Rubik.new
  end

  def ==(other)
    @edges == other.edges and @corners == other.corners
  end

  private

  def cycles_of(pieces)
    pieces_left = (1..pieces[:position].size).to_a
    cycles = []
    until pieces_left.empty?
      cycle = cycle_from(pieces, pieces_left.first)
      pieces_left -= cycle
      cycles << cycle
    end
    cycles
  end

  def cycle_from(pieces, index)
    cycle = [index]
    until pieces[:position][index-1] == cycle.first
      index = pieces[:position][index-1]
      cycle << index
    end
    cycle
  end

  def permute_array!(array, *indexes)
    tmp = array[indexes.last-1]
    indexes.reverse.each_cons(2) do |i, j|
      array[i-1] = array[j-1]
    end
    array[indexes.first-1] = tmp
  end

  def permute_edges!(*indexes)
    permute_array! @edges[:position]   , *indexes
    permute_array! @edges[:orientation], *indexes
  end

  def permute_corners!(*indexes)
    permute_array! @corners[:position]   , *indexes
    permute_array! @corners[:orientation], *indexes
  end

  def twist_corners_cw!(*indexes)
    twist_corners! 1, *indexes
  end

  def twist_corners_ccw!(*indexes)
    twist_corners! -1, *indexes
  end

  def twist_corners!(direction, *indexes)
    indexes.each do |i|
      o = @corners[:orientation][i-1] + direction
      @corners[:orientation][i-1] = o / (o.abs > 1 ? -2 : 1)
    end
  end

  def flip_edges!(*indexes)
    indexes.each do |i|
      @edges[:orientation][i-1] = (@edges[:orientation][i-1] - 1).abs
    end
  end
end

rubik_spec.rb

require File.join(File.dirname(__FILE__), 'rubik')

describe Rubik do
  before { @rubik = Rubik.new }
  subject { @rubik }
  it { should be_solved }

  describe "Cube twists" do
    describe "U" do
      before { @rubik.u }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [4, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]
      } }
      its(:corners) { should == {
        :position    => [4, 1, 2, 3, 5, 6, 7, 8],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0]
      } }
    end

    describe "U2" do
      before { @rubik.u2 }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [3, 4, 1, 2, 5, 6, 7, 8, 9, 10, 11, 12],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]
      } }
      its(:corners) { should == {
        :position    => [3, 4, 1, 2, 5, 6, 7, 8],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0]
      } }
    end

    describe "U'" do
      before { @rubik.ui }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [2, 3, 4, 1, 5, 6, 7, 8, 9, 10, 11, 12],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]
      } }
      its(:corners) { should == {
        :position    => [2, 3, 4, 1, 5, 6, 7, 8],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0]
      } }
    end

    describe "U4" do
      before { @rubik.u.u.u.u }

      it { should be_solved }
    end

    describe "R" do
      before { @rubik.r }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [1, 2, 3, 8, 5, 6, 4, 12, 9, 10, 11, 7],
        :orientation => [0, 0, 0, 0, 0, 0, 0,  0, 0,  0,  0, 0]
      } }
      its(:corners) { should == {
        :position    => [1, 2, 4,  7, 5, 6, 8,  3],
        :orientation => [0, 0, 1, -1, 0, 0, 1, -1]
      } }
    end

    describe "R2" do
      before { @rubik.r2 }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [1, 2, 3, 12, 5, 6, 8, 7, 9, 10, 11, 4],
        :orientation => [0, 0, 0,  0, 0, 0, 0, 0, 0,  0,  0, 0]
      } }
      its(:corners) { should == {
        :position    => [1, 2, 7, 8, 5, 6, 3, 4],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0]
      } }
    end

    describe "R'" do
      before { @rubik.ri }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [1, 2, 3, 7, 5, 6, 12, 4, 9, 10, 11, 8],
        :orientation => [0, 0, 0, 0, 0, 0,  0, 0, 0,  0,  0, 0]
      } }
      its(:corners) { should == {
        :position    => [1, 2, 8,  3, 5, 6, 4,  7],
        :orientation => [0, 0, 1, -1, 0, 0, 1, -1]
      } }
    end

    describe "R4" do
      before { @rubik.r.r.r.r }

      it { should be_solved }
    end

    describe "R U R' U'" do
      before { @rubik.r.u.ri.ui }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [1, 2, 4, 8, 5, 6, 7, 3, 9, 10, 11, 12],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]
      } }
      its(:corners) { should == {
        :position    => [1, 3,  2,  7, 5, 6,  4, 8],
        :orientation => [0, 0, -1, -1, 0, 0, -1, 0]
      } }
    end

    describe "(R U R' U')6" do
      before { 6.times { @rubik.r.u.ri.ui } }

      it { should be_solved }
    end

    describe "T perm" do
      before { @rubik.r.u.ri.ui.ri.f.r2.ui.ri.ui.r.u.ri.fi }

      it { should_not be_solved }
      its(:edges)   { should == {
        :position    => [1, 4, 3, 2, 5, 6, 7, 8, 9, 10, 11, 12],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0]
      } }
      its(:corners) { should == {
        :position    => [1, 2, 4, 3, 5, 6, 7, 8],
        :orientation => [0, 0, 0, 0, 0, 0, 0, 0]
      } }
    end
  end

  describe "#corner_cycles" do
    subject { @rubik.corner_cycles }

    context "when solved" do
      it { should == [[1], [2], [3], [4], [5], [6], [7], [8]] }
    end

    context "with a 2-cycle" do
      before { @rubik.r.u.ri.ui.ri.f.r2.ui.ri.ui.r.u.ri.fi }
      it { should == [[1], [2], [3, 4], [5], [6], [7], [8]] }
    end

    context "with a 4-cycle" do
      before { @rubik.u }
      it { should == [[1, 4, 3, 2], [5], [6], [7], [8]] }
    end

    context "with a 6-cycle" do
      before { @rubik.r.u.r }
      it { should == [[1, 7, 3, 4, 8, 2], [5], [6]] }
    end

    context "with two 2-cycles" do
      before { @rubik.u2 }
      it { should == [[1, 3], [2, 4], [5], [6], [7], [8]] }
    end
  end

  describe "#edge_cycles" do
    subject { @rubik.edge_cycles }

    context "when solved" do
      it { should == [[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12]] }
    end

    context "with a 2-cycle" do
      before { @rubik.r.u.ri.ui.ri.f.r2.ui.ri.ui.r.u.ri.fi }
      it { should == [[1], [2, 4], [3], [5], [6], [7], [8], [9], [10], [11], [12]] }
    end

    context "with a 4-cycle" do
      before { @rubik.u }
      it { should == [[1, 4, 3, 2], [5], [6], [7], [8], [9], [10], [11], [12]] }
    end

    context "with a 5-cycle" do
      before { @rubik.r.u.ri.ui.li.ui.l.u }
      it { should == [[1], [2, 5, 4, 8, 3], [6], [7], [9], [10], [11], [12]] }
    end

    context "with two 2-cycles" do
      before { @rubik.u2 }
      it { should == [[1, 3], [2, 4], [5], [6], [7], [8], [9], [10], [11], [12]] }
    end
  end
end

sequence.rb

#!/usr/bin/env ruby

require File.join(File.dirname(__FILE__), "rubik")

class Sequence
  MOVEMENT_RE = /[UFRDBL][2']?/
  SEQUENCE_RE = /^#{MOVEMENT_RE}( #{MOVEMENT_RE})*$/

  def initialize(sequence)
    @sequence = sequence
  end

  def order
    rubik = Rubik.new
    apply_to(rubik)

    (
      rubik.edge_cycles.map do |cycle|
        orientations = cycle.map { |i| rubik.edges[:orientation][i-1] }
        cycle.size * (orientations.inject(0, &:+) % 2 == 0 ? 1 : 2)
      end +
      rubik.corner_cycles.map do |cycle|
        orientations = cycle.map { |i| rubik.corners[:orientation][i-1] }
        cycle.size * (orientations.inject(0, &:+) % 3 == 0 ? 1 : 3)
      end
    ).uniq.inject(1) { |lcm, n| n.lcm(lcm) }
  end

  def apply_to(rubik)
    raise "The sequence you entered is not valid" unless valid?

    @sequence.scan(MOVEMENT_RE).inject(rubik) do |rubik, mov|
      rubik.send(mov.downcase.sub(/'$/, "i"))
    end
  end

  private

  def valid?
    @sequence =~ SEQUENCE_RE
  end
end

if $0 == __FILE__
  print "Enter a sequence: "
  until (s = gets.chomp).empty?
    sequence = Sequence.new(s)

    begin
      puts "I should have repeated the sequence #{sequence.order} times"
    rescue => e
      puts e.message
    end

    puts
    print "Enter a sequence: "
  end
end

sequence_spec.rb

require File.join(File.dirname(__FILE__), 'sequence')

describe Sequence do
  describe "#apply_to" do
    before { @rubik = mock("Rubik") }

    context "with an invalid sequence" do
      before { @sequence = Sequence.new("hello world!") }

      it "should raise an exception" do
        lambda { @sequence.apply_to(@rubik) }.should raise_error("The sequence you entered is not valid")
      end
    end

    context "with a valid sequence" do
      before { @sequence = Sequence.new("R2 L2 F2 B2 U2 D2 R2 L2 F2 B2 U2 D2") }

      it "should parse sequence and apply movements to the given cube" do
        [:r2, :l2, :f2, :b2, :u2, :d2, :r2, :l2, :f2, :b2, :u2, :d2].each do |mov|
          @rubik.should_receive(mov).ordered.and_return(@rubik)
        end
        @sequence.apply_to(@rubik)
      end
    end
  end

  describe "#order" do
    subject { @sequence.order }

    context "with R2 R2" do
      before { @sequence = Sequence.new("R2 R2") }
      it { should == 1 }
    end

    context "with R2" do
      before { @sequence = Sequence.new("R2") }
      it { should == 2 }
    end

    context "with R U' R U R U R U' R' U' R2" do
      before { @sequence = Sequence.new("R U' R U R U R U' R' U' R2") }
      it { should == 3 }
    end

    context "with R U" do
      before { @sequence = Sequence.new("R U") }
      it { should == 105 }
    end

    context "with F U F2 U' R' F' B' L' R' F' D2 F B' R U R2 F2 R2 F2 R2 F2 U' R' B" do
      before { @sequence = Sequence.new("F U F2 U' R' F' B' L' R' F' D2 F B' R U R2 F2 R2 F2 R2 F2 U' R' B") }
      it { should == 1260 }
    end
  end
end