flipflop-solver.rb

#!/bin/env ruby

require 'bundler/inline'

gemfile do
  source 'https://rubygems.org'
	gem 'bfs_brute_force', '~> 0.2.0'
end

require 'bfs_brute_force'
require 'set'

DEPTH_FIRST = false

if DEPTH_FIRST
	module BfsBruteForce
		class Solver
			# Depth-first search solver (non-optimal, but often faster with pruning)
			def solve(initial_state, status = [])
				status << "Looking for DFS solution for:\n#{initial_state}\n\n"
				already_seen = Set.new
				root = Context.new(initial_state, already_seen, [])
				if root.solved?
					status << "Good news, its already solved\n"
					return root
				end
				tries = 0
				best_context = nil
				best_moves_len = nil
				stack = [root] # LIFO => DFS
				until stack.empty?
					current = stack.pop
					if best_moves_len && current.moves.length >= best_moves_len
						next
					end
					current.next_contexts do |next_ctx|
						tries += 1
						if best_moves_len && next_ctx.moves.length >= best_moves_len
							next
						end
						if next_ctx.solved?
							moves_len = next_ctx.moves.length
							if best_moves_len.nil? || moves_len < best_moves_len
								best_context = next_ctx
								best_moves_len = moves_len
								status << "found solution (best so far) in #{tries} tries, #{best_moves_len} moves\n"
								next_ctx.moves.each { |m| status << "  #{m}\n" }
								status << "\nFinal state:\n #{next_ctx.state}\n"
							else
								status << "found solution in #{tries} tries, #{moves_len} moves (not better than #{best_moves_len})\n"
							end
							next
						end
						stack << next_ctx
					end
				end
				return best_context if best_context
				raise NoSolution.new(tries)
			end
		end
	end
end

MAX_COL_HEIGHT = 20

TEST1 = {
	done: [],
	cols: [
		%i{AS_ JS},
		%i{3S_ QS KS},
		%i{5S_ 6S},
		%i{7S_ 8S},
		%i{9S_ 0S}
	],
	reserves: %i{2S 4S},
	deck: [],
}

TEST2 = {
	done: [],
	cols: [
		%i{9S_ 7S},
		%i{0S_ 6S},
		%i{JS_ 8S_ 5S},
		%i{QS_ 4S},
		%i{KS_ 3S}
	],
	reserves: %i{AS 2S},
	deck: [],
}

TEST3 = {
	done: %i{QS},
	cols: [
		%i{KS},
	],
	reserves: [],
	deck: [],
}

TEST4 = {
	done: %i{JS},
	cols: [
		[],
		[],
		[],
		[],
		[],
	],
	reserves: %i{KS QS},
	deck: [],
}

TEST5 = {
	done: %i{QS},
	cols: [
		[],
		[],
		[],
		[],
		[],
	],
	reserves: %i{KS},
	deck: [],
}

TEST6 = {
	done: %i{8S},
	cols: [
		[],
		%i{9S 0S KS QS JS},
	],
	reserves: [],
	deck: [],
}

TEST7 = {
	done: %i{7S},
	cols: [
		[],
		%i{8S 9S KS QS JS},
	],
	reserves: %i{0S},
	deck: [],
}

TEST8 = {
	done: %i{3S},
	cols: [
		[],
		%i{8S 9S KS QS JS},
	],
	reserves: %i{0S},
	deck: [
		%i{7S 4S},
		%i{5S 6S},
	],
}

TEST9 = {
	done: %i{2S},
	cols: [
		%i{3S},
		%i{8S 9S KS QS JS},
	],
	reserves: %i{0S},
	deck: [
		%i{7S 4S},
		%i{5S 6S},
	],
}

TEST10 = {
	done: %i{AS},
	cols: [
		[],
		%i{8S 9S KS QS JS},
	],
	reserves: %i{0S},
	deck: [
		%i{7S 4S},
		%i{5S 6S},
		%i{3S 2S},
	],
}

EX_1SUIT_568 = {
	done: [],
	cols: [
		%i{QS_ 5S_ 3S_ 6S_ 7S_ JS},
		%i{0S_ QS_ AS_ 4S_ 9S_ 8S},
		%i{0S_ 6S_ AS_ 0S_ 5S_ 0S},
		%i{2S_ 4S_ 9S_ 7S_ KS},
		%i{5S_ 2S_ 6S_ 8S_ 8S}
	],
	reserves: %i{4S 3S},
	deck: [
		%i{7S 9S JS 7S QS},
		%i{9S 8S 4S AS 3S},
		%i{KS 2S 5S 6S 4S},
		%i{3S KS QS 9S AS},
		%i{5S 7S KS QS KS},
		%i{7S JS JS 0S JS},
	]
}

# Deep duplicator for hashes and arrays:
class Hash
	def deep_dup
		new_copy = self.dup
		each do |key, value|
			new_copy[key] = value.deep_dup if value.respond_to?(:deep_dup)
		end
		new_copy
	end
end
class Array
	def deep_dup
		new_copy = []
		self.each do |value|
			new_copy << if value.respond_to?(:deep_dup)
				value.deep_dup
			else
				value.dup
			end
		end
		new_copy
	end
end

class FlipFlopState < BfsBruteForce::State
	def initialize(value)
		@value = value
	end

	def ==(other)
		@value.to_s == other.to_s # Use string representation for equality comparison
	end

	# (see BfsBruteForce::State.solved?)
	def solved?
		#puts "Deciding if solved (#{@value[:reserves].length}, #{@value[:deck].length}, #{@value[:cols].inspect})"
		@value[:reserves].length == 0 &&
		@value[:deck].length == 0 &&
		@value[:cols].all?(&:empty?)
	end

	def to_s
		@value[:done].map{ |done| sprintf('[%2s]', done) }.join(' ') + "\n\n" +
		(@value[:cols].map(&:length).max + 1).times.map { |h|
			@value[:cols].length.times.map { |c|
			  card_s = @value[:cols][c][h].to_s
			  if card_s.empty? && h == 0
					' __ '
				elsif(card_s[-1] == '_')
					sprintf('(%2s)', card_s[0,2]) # face-down card
				else
					sprintf(' %2s ', card_s[0,2]) # face-up card
				end
			}.join(' ')
		}.join("\n") + "\n" +
		@value[:reserves].map{ |reserve| sprintf('[%2s]', reserve) }.join(' ') + "\n\n" +
		"Deck: " + @value[:deck].length.to_s + "\n\n---\n\n"
	end

	def interpret_card(card)
		return card if card.is_a?(Hash) && card[:suit] && card[:rank] && card[:face_up] && card[:description]
		return nil if card.to_s.empty?
		parts = card.to_s
		#puts "Interpreting card: #{card} (#{parts[0]})"
		result = {
			code: card,
			rank: parts[0],
			rank_value: {
				'A' => 1,
				'2' => 2,
				'3' => 3,
				'4' => 4,
				'5' => 5,
				'6' => 6,
				'7' => 7,
				'8' => 8,
				'9' => 9,
				'0' => 10,
				'J' => 11,
				'Q' => 12,
				'K' => 13,
			}[parts[0]],
			suit: parts[1],
			face_up: parts[2] != '_',
			description: {
				'A' => 'Ace',
				'2' => 'Two',
				'3' => 'Three',
				'4' => 'Four',
				'5' => 'Five',
				'6' => 'Six',
				'7' => 'Seven',
				'8' => 'Eight',
				'9' => 'Nine',
				'0' => 'Ten',
				'J' => 'Jack',
				'Q' => 'Queen',
				'K' => 'King',
			}[parts[0]] + ' of ' + {
				'S' => 'Spades',
				'H' => 'Hearts',
				'D' => 'Diamonds',
				'C' => 'Clubs',
			}[parts[1]] +
			(parts[2] == '_' ? '(face down)' : '')
 		}
		result
	end

	def one_off(card1, card2)
		card1 = interpret_card(card1)
		card2 = interpret_card(card2)
		(card1[:rank_value] - card2[:rank_value]) == 1 || (card1[:rank_value] - card2[:rank_value]) == -1
	end

	def one_above(on_top, below)
		on_top = interpret_card(on_top)
		below = interpret_card(below)
		on_top[:rank_value] - below[:rank_value] == 1
	end

	def same_suit(card1, card2)
		card1 = interpret_card(card1)
		card2 = interpret_card(card2)
		card1[:suit] == card2[:suit]
	end

	# Returns index of first valid done slot for this card to move to
	def can_move_to_done(card)
		card = interpret_card(card)
		return @value[:done].length if card[:rank_value] == 1 # Aces can always move to first empty done slot
		@value[:done].find_index{ |top| one_above(card, top) & same_suit(card, top) }
	end

	# Given a state, ensures all "top" cards flipped face-up
	def flip_exposed_in(value)
		value[:cols].map! do |col|
			top_of_col = col.last
			rest_of_col = col[...-1]
			rest_of_col << top_of_col.to_s[0,2].to_sym if top_of_col
			rest_of_col
		end
	end

	# Givem an array of cards, returns true if they're moveable "as a stack"
	def moveable_as_stack?(cards)
		return true if cards.length == 1 # Single card is always moveable as a stack
		return false if cards.any? { |card| card.to_s[-1] == '_' } # Face-down cards are not moveable
		return true if cards.each_cons(2).all? { |card1, card2| one_off(card1, card2) } # Every consecutive pair of cards must be one rank apart
		false
	end

	# Given an array of cards, returns a string description of the stack
	def describe_stack(cards)
		cards.map { |card| interpret_card(card)[:description] }.join(', ')
	end

	# Call yield for every next state in your puzzle
	# (see BfsBruteForce::State.next_states)
	def next_states(already_seen)
		# Deal from deck:
		if @value[:deck].length > 0
			new_state = @value.deep_dup
			new_state[:deck].shift.each_with_index do |card, index|
				new_state[:cols][index] << card
			end
			# (puts "7:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
			if already_seen.add?(new_state)
				yield "Deal from deck", FlipFlopState.new(new_state)
			end
		end

		# Move from reverses to done:
		@value[:reserves].each_with_index do |card, index|
			next unless card = interpret_card(card)
			if landing_spot = can_move_to_done(card)
				new_state = @value.deep_dup
				new_state[:done][landing_spot] = card[:code]
				new_state[:reserves].delete_at(index)
				flip_exposed_in(new_state)
				# (puts "2:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
				if already_seen.add?(new_state)
					yield "Move #{card[:description]} from reserves to done", FlipFlopState.new(new_state)
				end
			end
		end

		# Move from cols to done:
		@value[:cols].each_with_index do |col, index|
			next unless card = interpret_card(col.last)
			# puts "Considering moving #{card[:description]} from column #{index} to done"
			if landing_spot = can_move_to_done(card)
				new_state = @value.deep_dup
				# puts "- State: #{@value.inspect}\n- Duplicated state: #{new_state.inspect}"
				new_state[:done][landing_spot] = card[:code]
				# puts "- This would affect column #{index}: #{new_state[:cols][index].inspect}"
				new_state[:cols][index].delete_at(-1)
				flip_exposed_in(new_state)
				# (puts "1:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
				if already_seen.add?(new_state)
					yield "Move #{card[:description]} from column #{index} to done", FlipFlopState.new(new_state)
				end
			end
		end

		# Move from reserves to cols:
		@value[:reserves].each_with_index do |card, index|
			next unless card = interpret_card(card)
			@value[:cols].each_with_index do |col, index|
				if col.empty? # Can always move into an empty column (though moving from reserves to empties is PROBABLY pointless?):
					new_state = @value.deep_dup
					new_state[:reserves].delete_at(index)
					new_state[:cols][index] << card[:code]
					flip_exposed_in(new_state)
					# (puts "3:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
					if already_seen.add?(new_state)
						yield "Move #{card[:description]} from reserves into empty column #{index}", FlipFlopState.new(new_state)
					end
				else
					front_landing_card = col.last
					next unless one_off(card, front_landing_card)
					new_state = @value.deep_dup
					new_state[:reserves].delete_at(index)
					new_state[:cols][index] << card[:code]
					flip_exposed_in(new_state)
					# (puts "4:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
					if already_seen.add?(new_state)
						yield "Move #{card[:description]} from reserves onto #{interpret_card(front_landing_card)[:description]} (column #{index})", FlipFlopState.new(new_state)
					end
				end
			end
		end

		# Move betweem cols:
		@value[:cols].each_with_index do |col, index|
			number_of_faceup_cards = col.filter { |card| card.to_s[-1] != '_' }.length
			next unless number_of_faceup_cards >= 1
			# puts "Considering column-to-column move from column #{index}"
			for number_of_cards_to_consider_moving in (1..number_of_faceup_cards)
				possible_cards_to_move = col[-number_of_cards_to_consider_moving..-1]
				next unless moveable_as_stack?(possible_cards_to_move)
				back_moving_card = possible_cards_to_move.first
				# puts "Considering column-to-column move of #{possible_cards_to_move.inspect} from column #{index}"
				@value[:cols].each_with_index do |other_col, other_index|
					next if other_index == index # can't move cards to same column they came from
					if other_col.empty?
					  # Can always move into an empty column:
						new_state = @value.deep_dup
						new_state[:cols][other_index] = new_state[:cols][index].pop(number_of_cards_to_consider_moving)
						flip_exposed_in(new_state)
						# puts "Considering column-to-column move of #{possible_cards_to_move.inspect} from column #{index} into empty column #{other_index}\nOld: #{@value.inspect}\nNew: #{new_state.inspect}"
						# (puts "5:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
						if already_seen.add?(new_state)
							yield "Move #{describe_stack(possible_cards_to_move)} from column #{index} into empty column #{other_index}", FlipFlopState.new(new_state)
						end
					else
						front_landing_card = other_col.last
						next unless one_off(back_moving_card, front_landing_card)
						new_state = @value.deep_dup
						new_state[:cols][other_index] += new_state[:cols][index].pop(number_of_cards_to_consider_moving)
						# puts "Considering column-to-column move of #{possible_cards_to_move.inspect} from column #{index}\nonto #{front_landing_card} (column #{other_index})\nOld: #{@value.inspect}\nNew: #{new_state.inspect}"
						# investigating BUG -
						# Considering column-to-column move of [:"5S"] from column 0
						# onto 6S (column 1)
						# Old: {:done=>[:"3S"], :cols=>[[:"5S"], [:"8S", :"9S", :KS, :QS, :JS, :"6S"]], :reserves=>[:"0S"], :deck=>[]}
						# New: {:done=>[:"3S"], :cols=>[[:"5S", :"5S"], [:"8S", :"9S", :KS, :QS, :JS, :"6S", :"6S"]], :reserves=>[:"0S"], :deck=>[[:"5S", :"6S"]]}						new_state = @value.deep_dup
						flip_exposed_in(new_state)
						# (puts "6:#{new_state.inspect}"; exit) if new_state.inspect.to_s =~ /5S.*5S/ # bug 18 tester
						if already_seen.add?(new_state)
							yield "Move #{describe_stack(possible_cards_to_move)} from column #{index} onto #{interpret_card(front_landing_card)[:description]} (column #{other_index})", FlipFlopState.new(new_state)
						end
					end
				end
			end
		end
	end
	
	def self.run_tests
		instance = FlipFlopState.new({})
		raise 'Failed test 1' unless instance.one_above('2S', 'AS') & instance.same_suit('2S', 'AS')
	end
end

# Tests:
FlipFlopState.run_tests

solver = BfsBruteForce::Solver.new
initial_state = FlipFlopState.new(TEST10)

# initial_state.next_states(Set.new) do |move, state|
# 	puts "Option: #{move}"
# 	puts state.to_s
# end

puts "Solving:"

solution = solver.solve(initial_state, STDOUT)

if solution.solved?
	puts "\nSolved:"

	moves = solution.moves

	moves.each_with_index do |move, index|
		puts "%3d. %s" % [index + 1, move]
	end
else
	puts "Not solved!"
end