coins.rb

#!/usr/bin/ruby

class Coins

  def initialize(maxcoins, maxdepth=maxcoins, maxlen=maxcoins+2)
    @maxcoins = maxcoins
    @maxdepth = maxdepth
    @maxlen = maxlen
    @solution = nil
    @coins = Array.new(@maxlen, ' ')
    0.upto(@maxcoins-1) do |c|
      @coins[c] = c%2 == 0 ? 'o' : 'O'
    end
    @final="#{'O'*(@maxcoins/2)}#{'o'*(@maxcoins/2)}"
    if @maxcoins % 2 == 1
      @final += 'o'
    end
  end

  def move(depth=1, c=@coins, m=[])
    return false if depth > @maxdepth+1
    if final? c
      @solution = m
      return true
    end
    0.upto(@maxlen-4) do |i|
      if c[i] != ' ' and c[i+1] != ' ' # a coin pair
        (i+2).upto(@maxlen-2) do |j|
          if valid? c, i, j
            return false if not m.empty? and [j, i] == m[-1]
            if move depth+1, swapcoins(c, i, j), m
               m.push [i, j]
               return true
            end
          end
        end
      end
    end
    (@maxlen-3).downto(4) do |i|
      if c[i] != ' ' and c[i+1] != ' '
        (i-2).downto(0) do |j|
          if valid? c, i, j
            return false if not m.empty? and [j, i] == m[-1]
            if move depth+1, swapcoins(c, i, j), m
               m.push [i, j]
               return true
            end
          end
        end
      end
    end
    false
  end

   def play
    puts "Solution with #{@solution.length} moves:"
    @coins = Array.new(@maxlen, ' ')
    0.upto(@maxcoins-1) do |c|
      @coins[c] = c%2 == 0 ? 'o' : 'O'
    end
       @solution.reverse.each do |mv|
         @coins=swapcoins @coins, mv[0], mv[1], true
      end
   end

  private
  def swapcoins(coins, start_coin, end_coin, print=false)
    c = Array.new(coins)
    c[start_coin], c[end_coin] = c[end_coin], c[start_coin]
    c[start_coin+1], c[end_coin+1] = c[end_coin+1], c[start_coin+1]
    puts "Swapping #{cstring coins} <-> #{cstring c}" if print
    c
  end

  def final?(coins)
    coins.join.strip.eql? @final or coins.join.strip.eql? @final.reverse
  end

  def valid?(coins, start_coin, end_coin)
     return false if coins[end_coin] != ' ' or coins[end_coin + 1] != ' ' # space
     return false if coins[end_coin - 1] == ' ' and coins[end_coin + 2] == ' ' # outside
     return false if (end_coin - start_coin).abs <= 2 # translation
     true
  end

  def cstring(coins)
    coins.join.gsub(' ', '_')
  end

end

number = ARGV[0].to_i
coins = Coins.new(number)
if coins.move
   coins.play
else
   puts "No solution"
end