Ruby Code Example: Letter Beads Solver

The October 2007 meeting of the Southeast Michigan Ruby Users' Group posed a Letter Bead Solver as the monthly challenge. Here is the challenge.

letter_beads.rb

Here is my solution.

#!/usr/bin/env ruby

# a few constants
LeftTurn = 'L'
RightTurn = 'R'

# parse command-line argument
beads = ARGV[0].split(//)
bead_count = beads.size

# create bead_positions hash, allowing position to be retrieved by
# bead
bead_positions = Hash.new
beads.each_with_index { |b, i| bead_positions[b] = i }

# set up initial values
last_position = 0
last_turn = RightTurn  # default direction in case first move is tie

# create a list of moves, where each move is an array of three
# elements, containing the turn direction, the number of positions to
# move, and the bead being turned to
moves = beads.sort.map do |b|
  position = bead_positions[b]

  # calculate how many turns it would be for both left and right
  left_turns = (position - last_position + bead_count) % bead_count
  right_turns = bead_count - left_turns

  # choose the direction with the lesser number of turns (or, for a
  # tie, the direction of the most recent turn)
  if left_turns < right_turns
    turn = LeftTurn
    count = left_turns
  elsif right_turns < left_turns
    turn = RightTurn
    count = right_turns
  else
    turn = last_turn
    count = left_turns
  end

  # save position and turn for next time around
  last_position, last_turn = position, turn

  # return the move representation
  [turn, count, b]  
end

avg_turn_count = moves.inject(0) { |s, m| s + m[1] } / moves.size.to_f
puts "Average number of turns: %0.4f" % avg_turn_count

# display moves
puts moves.map { |m| "%s%d:%s" % m }.join(' ')

random_beads.rb

To aid in testing of my solution, I also wrote a very small script that generated random bead patterns that could be used as input the solver.

letters = ('A'..'Z').sort_by { |ignored| rand }
puts letters.join('')