Simulate Rubik's Cubes using the two-cycle method.

.gitignore

.*.sw[op]

*.pdf
*.json
*.csv

README.md

To run this simulation run these following shell commands:

$ git clone https://gist.github.com/929241297c138964bc90.git cube-stats
$ cd cube-stats
$ gem install rubiks_cube
$ ruby cube-stats.rb 100

cube-stats.rb

#!/usr/bin/env ruby

require "json"
require "rubiks_cube"
require "./scramble.rb"

# usage help
if ARGV.length != 1 && ARGV.length != 2 then
    puts "Usage: cube-stats <trials> [scramble_moves]"
    puts
    puts "        <trials> : number of times to run the simulation"
    puts "[scramble_moves] : number of preliminary random moves prior to each simulation"
    exit 1
end

# number of trials to do
trials = ARGV[0].to_i
abort "error: trials must be >= 1" if trials < 1

# moves to scramble within each trial (default 100)
if not ARGV[1] then
    scramble_moves = 100
else
    scramble_moves = ARGV[1].to_i
end

# create a new cube and a data hash
data = {
    :trials => trials,
    :scramble_moves => scramble_moves,
    :moves => Array.new
}

puts "Running #{trials} trials with #{scramble_moves} scramble moves per trial."

# run the trials
trials.times do |i|
    # Scramble cube
    cube = RubiksCube::Cube.new
    seq = Scramble.get_random_moves(scramble_moves)
    cube.perform! seq

    # How many moves does it take?
    solution = RubiksCube::TwoCycleSolution.new(cube)

    puts "Trial ##{(i+1).to_s.rjust(3, "0")} - #{solution.length} moves"

    data[:moves] << solution.length
end

# dump data to JSON
File.open("data.json", "w") do |f|
    f.write JSON.pretty_generate(data) + "\n"
end

###
puts "## scramble_moves vs. std dev correlation test"
sd_test = []

module Enumerable
    def sum
        self.inject(0){|accum, i| accum + i }
    end

    def mean
        self.sum/self.length.to_f
    end

    def sample_variance
        m = self.mean
        sum = self.inject(0){|accum, i| accum +(i-m)**2 }
        sum/(self.length - 1).to_f
    end

    def standard_deviation
        return Math.sqrt(self.sample_variance)
    end
end

# test scramble moves from 0 to 100
(0..100).step(1) do |scramble_moves|
    100.times do |i|
        # Scramble cube
        cube = RubiksCube::Cube.new
        seq = Scramble.get_random_moves(scramble_moves)
        cube.perform! seq

        # How many moves does it take?
        solution = RubiksCube::TwoCycleSolution.new(cube)

        puts "sm=#{scramble_moves} : Trial ##{(i+1).to_s.rjust(3, "0")} - #{solution.length} moves"

        # indice = scramble moves tested
        sd_test[scramble_moves] = [] if not sd_test[scramble_moves]
        sd_test[scramble_moves] << solution.length
    end
end

# calculate and write standard deviations to a CSV
File.open("sd_data.csv", "w") do |f|
    f.write("scramble_moves,std_dev\n")

    sd_test.each_with_index do |val, index|
        next if not val

        sd = val.standard_deviation
        puts "val = #{val}, sd = #{sd}, i = #{index}"
        f.write("#{index},#{sd}\n")
    end
end

graph.r

#!/usr/bin/env Rscript

library("rjson")

pdf(file="Rplots.pdf", width=7.5, height=7)

data <- fromJSON(file="data.json")

print("Summary of Data:")
summary(data$moves)

hist(data$moves,
     main="Distrubution of Moves to Solve Rubiks Cube",
     sub="(using the two-cycle solution method)",
     xlab="Number of Moves to Solve Cube", ylab="Frequency",
     col="gray"
)

sd_data <- read.csv("sd_data.csv")
plot(sd_data,
     main="Preliminary Scramble Moves VS. Standard Deviation",
     xlab="Number of Preliminary Scramble Moves",
     ylab="Standard Deviation (of moves to solve)",
     pch=19
)

scramble.rb

module Scramble
    extend self

    @move_types = [
        "F", "F'", "B", "B'", "L", "L'",
        "R", "R'", "U", "U'", "D", "D'"
    ]

    # To prevent unnecessary moves, e.g. sequential F and F',
    # each move has only some possible successors. The easy way
    # is to use only movements that will permute the previous.
    @successors = {
        "F"  => ["L", "L'", "R", "R'", "U", "U'", "D", "D'"],
        "F'" => ["L", "L'", "R", "R'", "U", "U'", "D", "D'"],
        "B"  => ["L", "L'", "R", "R'", "U", "U'", "D", "D'"],
        "B'" => ["L", "L'", "R", "R'", "U", "U'", "D", "D'"],
        "L"  => ["F", "F'", "B", "B'", "U", "U'", "D", "D'"],
        "L'" => ["F", "F'", "B", "B'", "U", "U'", "D", "D'"],
        "R"  => ["F", "F'", "B", "B'", "U", "U'", "D", "D'"],
        "R'" => ["F", "F'", "B", "B'", "U", "U'", "D", "D'"],
        "U"  => ["F", "F'", "B", "B'", "L", "L'", "R", "R'"],
        "U'" => ["F", "F'", "B", "B'", "L", "L'", "R", "R'"],
        "D"  => ["F", "F'", "B", "B'", "L", "L'", "R", "R'"],
        "D'" => ["F", "F'", "B", "B'", "L", "L'", "R", "R'"]
    }

    def random_move
        mi = rand(0..11)
        return @move_types[mi]
    end

    def random_successor(move_type)
        mi = rand(0..7)
        return @successors[move_type][mi]
    end

    def get_random_moves(count)
        move  = random_move
        moves = []
       
        # Generate the moves
        count.times do
            moves << move
            move = random_successor(move)
        end

        # Convert to string
        str = ""
        moves.each do |move|
            str << "#{move} "
        end
        
        return str
    end
end