Skip to content

Instantly share code, notes, and snippets.

@dragosboca
Last active August 29, 2015 14:15

Revisions

  1. dragosboca revised this gist Feb 12, 2015. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion coins.rb
    Original file line number Diff line number Diff line change
    @@ -36,7 +36,7 @@ def move(depth=1, c=@coins, m=[])
    end
    end
    end
    (@maxlen-3).downto(2) do |i|
    (@maxlen-3).downto(4) do |i|
    if c[i] != ' ' and c[i+1] != ' '
    (i-2).downto(0) do |j|
    if valid? c, i, j
  2. dragosboca created this gist Feb 12, 2015.
    98 changes: 98 additions & 0 deletions coins.rb
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,98 @@
    #!/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(2) 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