#!/usr/bin/ruby

# Rubik's cube solver
# (c) Yoann Guillot 2011
# Distributes under the terms of the WtfPLv2

# usage: start once (with optionnal the initial of the unfinished face), redirect output to a file
# edit the file to match your cube state
# run the script with the file as argument
# follow instructions: <face color initial: 'YWORGB'><rotation side: '+' = clockwise>

class Cube
	# white yellow red orange blue green
	Colors = [:w, :y, :r, :o, :b, :g]

	Opposite = { :w => :y, :r => :o, :b => :g }
	Opposite.update Opposite.invert

	# list of face color bordering a given face
	Borders = {}
	Colors.each { |c|
		Borders[c] = Colors - [c, Opposite[c]]
	}

	# [top, front] => right face color
	Right = { [:w, :r] => :b }
	Colors.each { |t|
		Borders[t].each { |f|
			if r = Right[[t, f]]
			elsif r = Right[[Opposite[t], Opposite[f]]]
			elsif r = Right[[t, Opposite[f]]]
				r = Opposite[r]
			elsif r = Right[[Opposite[t], f]]
				r = Opposite[r]
			elsif r = Right[[f, t]]
				r = Opposite[r]
			elsif a = Right.find { |(tt, ff), rr| t == tt and f == rr }
				r = Opposite[a[0][1]]	# Opposite(ff)
			else
				p Right, [t, f]
				raise
			end
			Right[[t, f]] = r
		}
	}



	# parse a template string, return a cube
	def self.load_template(tpl)
		c = new
		faces = parse_template(tpl)
		faces.each { |f| c.set_face(f) }
		c.check
		c.orient(faces[2][:color], faces[5][:color])
		c
	end

	def self.parse_template(tpl)
		tb = tpl.downcase.split("\n").map { |l| l.split.map { |c| c.to_sym } }
		tb.delete_if { |l| l.empty? }
		raise "bad template line count, #{tb.length} != 9" if tb.length != 9
		tb.zip([3,3,3,12,12,12,3,3,3]).each { |l, lc|
			raise "bad template line #{l}" if l.length != lc
		}
		bad = tb.flatten.uniq - Colors
		raise "bad template letter #{bad.inspect}" if not bad.empty?
		fcs = [tb[1][1], tb[4][1], tb[4][4], tb[4][7], tb[4][10], tb[7][1]]
		raise "missing face #{(Colors - fcs).inspect}" if fcs.uniq.length != 6
		faces = []
		back, left, top, right, bottom, front = fcs
		faces << { :color => back,
			bottom => tb[0], left => [tb[2][0], tb[1][0], tb[0][0]],
			top => tb[2].reverse, right => [tb[0][2], tb[1][2], tb[2][2]] }
		4.times { |i|
			pv = tb[4][3*((i-1) % 4)+1]
			nt = tb[4][3*((i+1) % 4)+1]
			faces << { :color => tb[4][3*i+1],
				back => tb[3][3*i, 3],
				pv => [tb[5][3*i], tb[4][3*i], tb[3][3*i]],
			       	front => tb[5][3*i, 3].reverse,
				nt => [tb[3][3*i+2], tb[4][3*i+2], tb[5][3*i+2]] }
		}
		faces << { :color => front,
			bottom => tb[8].reverse, left => [tb[8][0], tb[7][0], tb[6][0]],
			top => tb[6], right => [tb[6][2], tb[7][2], tb[8][2]] }
		faces
	end

	# hash color => { :color => col, side1col => [c1, c2, c3], side2col ... }
	# each array on a face is when the relevant side is up
	attr_accessor :face
	attr_accessor :top, :front, :right
	attr_accessor :reset_seq_adv

	def initialize
		@reset_seq_adv = false
		@face = {}
		Colors.each { |c|
			f = { :color => c }
			Borders[c].each { |bc| f[bc] = [c, c, c] }
			@face[c] = f
		}
		orient :w, :r
	end

	# set the top/front color
	def orient(top, front=nil)
		@top = top
		@front = front || Borders[top].first
		@right = Right[[@top, @front]]
	end

	def bottom; Opposite[top] end
	def back; Opposite[front] end
	def left; Opposite[right] end

	# randomize the cube by applying nr random moves
	def shuffle(nr=50)
		nr.times {
			face = Colors[rand(Colors.length)]
			rotate(face, rand(2) == 1 ? true : false)
		}
	end

	# arbitrary set a face
	def set_face(nf)
		@face[nf[:color]] = nf
	end

	# check that the cube is valid (after loading a template)
	# only checks that all corners/side exist, not that it is solvable
	def check
		sides = []
		corners = []
		Colors.each { |c1|
			Borders[c1].each { |c2|
				sides << [c1, c2]
				Borders[c1].each { |c3|
					next if c3 == c2 or c3 == Opposite[c2]
					corners << [c1, c2, c3]
				}
			}
		}

		Colors.each { |c1|
			raise "no #{c1} face" if not f = @face[c1]
			raise "bad face color #{c1}" if f[:color] != c1
			Borders[c1].each { |c2|
				raise "what ? #{c1} #{c2} #{f[c2].inspect}" if f[c2].length != 3 or (f[c2] - Colors).first
				cc1, cc2 = @face[c1][c2][1], @face[c2][c1][1]
				raise "duplicate side #{cc1} #{cc2}" if not sides.delete [cc1, cc2]
				Borders[c1].each { |c3|
					next if c3 == c2 or c3 == Opposite[c2]
					if Right[[c1, c2]] == c3
						cc1, cc2, cc3 = @face[c1][c2][0], @face[c2][c1][2], @face[c3][c1][0]
						raise "bad overlap on #{[c1, c2, c3].inspect}" if @face[c2][c1][2] != @face[c2][c3][0]
					else
						cc1, cc2, cc3 = @face[c1][c2][2], @face[c2][c1][0], @face[c3][c1][2]
					end
					raise "duplicate corter #{[cc1, cc2, cc3].inspect}" if not corners.delete [cc1, cc2, cc3]
				}
			}
		}
		raise "no side #{sides.inspect}" if not sides.empty?
		raise "no corner #{corners.inspect}" if not corners.empty?
	end

	# rotate the face whose center is color col
	# clockwise (dir=true) or counterclockwise (dir=false)
	def rotate(c, direction)
		s = borders_ordered(c)
		s.reverse! if direction

		# update face[c]
		@face[c][s[0]], @face[c][s[1]], @face[c][s[2]], @face[c][s[3]] =
		@face[c][s[3]], @face[c][s[0]], @face[c][s[1]], @face[c][s[2]]

		# update face[border][c]
		@face[s[0]][c], @face[s[1]][c], @face[s[2]][c], @face[s[3]][c] =
		@face[s[3]][c], @face[s[0]][c], @face[s[1]][c], @face[s[2]][c]

		# now update face[border][otherside with corner in common with c]
		s.reverse! if direction
		4.times { |i|
			f = @face[s[i]]
			f[s[i-1]][2] = f[c][0]
			f[s[i-3]][0] = f[c][2]
		}
	end

	# returns the list of adjacent borders to the top side by walking to the right side
	def borders_ordered(c)
		s = [Borders[c][0]]
		s << Right[[c, s.last]]
		s << Right[[c, s.last]]
		s << Right[[c, s.last]]
		s
	end

	# returns the location of the side (color for color)
	def find_side(c1, c2)
		Colors.each { |cc1|
			Borders[cc1].each { |cc2|
				if @face[cc1][cc2][1] == c1 and @face[cc2][cc1][1] == c2
					return [cc1, cc2]
				end
			}
		}
		raise
	end

	def find_corner(c1, c2, c3)
		Colors.each { |cc1|
			Borders[cc1].each { |cc2|
				if @face[cc1][cc2][0] == c1
					cc3 = Right[[cc1, cc2]]
					if @face[cc2][cc1][2] == c2 and @face[cc3][cc1][0] == c3
						return [cc1, cc2, cc3]
					elsif @face[cc2][cc1][2] == c3 and @face[cc3][cc1][0] == c2
						return [cc1, cc3, cc2]
					end
				end
			}
		}
		puts self
		raise [c1, c2, c3].inspect
	end

	# solve the cube
	# return a string containing the sequence of moves to make (r+ => rotate red face clockwise, etc)
	def solve
		solve_f12
		solve_f3
		seq_to_s simplify_sequence(@seq)
	end

	def rotate_log(col, dir)
		@seq << [col, dir]
		rotate(col, dir)
	end
	def r_T; rotate_log(top,    true); end;  def r_Ti; rotate_log(top,    false); end
	def r_B; rotate_log(bottom, true); end;  def r_Bi; rotate_log(bottom, false); end
	def r_F; rotate_log(front,  true); end;  def r_Fi; rotate_log(front,  false); end
	def r_K; rotate_log(back,   true); end;  def r_Ki; rotate_log(back,   false); end
	def r_R; rotate_log(right,  true); end;  def r_Ri; rotate_log(right,  false); end
	def r_L; rotate_log(left,   true); end;  def r_Li; rotate_log(left,   false); end

	# transform colors => relative side wrt current orientation
	def relative(cols)
		h = { top => 'T', bottom => 'B', front => 'F', back => 'K', right => 'R', left => 'L' }
		cols.map { |c| h[c] }
	end

	# run stuff in its block with a temporary @seq, return the generated @seq length (simplified full @seq len)
	def try_seq_len
		oseq = @seq
		@seq = []
		yield
		@seq.reverse_each { |sq| rotate(sq[0], !sq[1]) }
		ret = simplify_sequence(oseq + @seq).length
		@seq = oseq
		ret
	end

	def show_adv(always=false)
		@lastsq ||= []
		@seq = simplify_sequence(@seq)
		if @seq != @lastsq or always
			@lastsq = @seq.dup
			puts seq_to_s
			puts self
			@seq = [] if @reset_seq_adv
		end
	end

	# find the most favorable f1,
	# solve the 1st face + 2nd stage,
	# orient the cube with last face top
	def solve_f12
		@seq = []

		delta = solve_find_f1

		show_adv(true)

		# Top cross
		cd = Borders[top].dup
		4.times {
			c2 = cd.sort_by { |cc|
				try_seq_len { solve_f12_cross(cc, delta) }
			}.first
			cd.delete c2
			delta = solve_f12_cross(c2, delta)
		}
		show_adv

		# Top face minus 1corner
		cd = Borders[top].dup
		3.times {
			c2 = cd.sort_by { |cc|
				try_seq_len { solve_f12_corner(cc, delta) }
			}.first
			cd.delete c2
			solve_f12_corner(c2, delta)
		}
		show_adv

		freecn = cd.first

		# 2nd stage 3 corners
		cd = Borders[top].dup
		3.times {
			c2 = cd.sort_by { |cc|
				try_seq_len { solve_f12_side2(cc, freecn) }
			}.first
			cd.delete c2
			solve_f12_side2(c2, freecn)
		}
		lastsd = cd.first
		orient(top, lastsd)
		r_T until @face[front][top][1] == freecn
		show_adv

		# finish stages 1&2
		solve_f12_last(lastsd, freecn)

		orient(bottom)

		show_adv(true)
	end

	# find the most favorable f1, orient the cube accordingly
	# return the nr of r_T to do to have optimal alignment
	def solve_find_f1
		cl = Colors.map { |c1|
			sc = borders_ordered(c1)
			sd = sc.map { |c2| @face[c2][c1][1] if @face[c1][c2][1] == c1 }

			sides = 0
			corners = 0
			delta = 0

			if sd.compact.length > 0
				# filter non-ordered sides
				# find the longest correct sequence
				# at most we have 2 different sequence with one of length 1
				[sd.compact.first, sd.compact.last].uniq.each { |c_foo|
					i0 = sd.index(sd.compact.first)
					dt = sc.index(sd[i0]) - i0
					if (0..3).find_all { |i| @face[c1][sc[i]][1] == c1 and @face[sc[i]][c1][1] == sc[(i+dt)%4] }.length >
					   (0..3).find_all { |i| @face[c1][sc[i]][1] == c1 and @face[sc[i]][c1][1] == sc[(i+delta)%4] }.length
						delta = dt
					end
				}

				4.times { |i|
					c2 = sc[(i+delta) % 4]
					sides += 1   if @face[c1][sc[i]][1] == c1 and @face[sc[i]][c1][1] == c2
					corners += 1 if @face[c1][sc[i]][0] == c1 and @face[sc[i]][c1][2] == c2
				}
			end

			[c1, sides, corners, delta]
		}

		cm = cl.sort_by { |c1, sc, cc, dt| [sc, cc, (-dt%4)] }.last
		orient(cm[0])
		-cm[3]%4
	end

	# create the 1st face cross side [top, c2]
	def solve_f12_cross(c2, delta)
		ddelta = lambda { |d| delta = (delta + d) % 4  ; (d%4).times { orient(top, right) } }

		orient(top, c2)
		delta.times { orient(top, right) }

		loop do
			case pos = relative(find_side(top, c2))
			when ['T', 'F']; break
			when ['F', 'R']; r_Ti; r_R; ddelta[1]
			when ['R', 'K']; r_T; r_T; r_K; ddelta[2]
			when ['L', 'K']; r_T; r_T; r_Ki; ddelta[2]
			when ['K', 'R']; r_Ti; r_Ri; ddelta[1]
			when ['K', 'L']; r_T; r_L; ddelta[-1]
			else
				if pos[0] == 'F' or pos[1] == 'F'; r_F
				elsif pos[0] == 'B' or pos[1] == 'B'; r_B
				elsif pos[1] == 'T'; send "r_#{pos[0]}"
				elsif pos[0] == 'T'; send "r_#{pos[1]}"
				else raise
				end
			end
		end

		delta
	end

	# create the 1st face corner side [top, c2]
	def solve_f12_corner(c2, delta)
		orient(top, c2)
		c3 = right
		delta.times { orient(top, right) }

		loop do
			pos = relative(find_corner(top, c2, c3))
			case pos[0, 2]
			when ['T', 'F']; break
			when ['K', 'B']; r_Ri; r_B; r_B; r_R
			when ['L', 'K']; r_F; r_B; r_B; r_Fi
			when ['B', 'R']; r_F; r_Bi; r_Fi
			else
				if pos.include?('B'); r_B
				else
					case (pos - ['T']).sort
					when ['F', 'L']; r_L; r_B; r_Li
					when ['F', 'R']; r_Ri; r_B; r_B; r_R
					when ['K', 'L']; r_Li; r_B; r_L
					when ['K', 'R']; r_R; r_B; r_Ri
					else raise
					end
				end
			end
		end
	end

	# create the 2st stage side [c2, +right], free top corner [top, cf, +right]
	def solve_f12_side2(c2, cf)
		orient(top, c2)

		# bring free corner over target side
		pre_l = @seq.length
		r_T until @face[front][top][1] == cf
		nr_T_ini = @seq.length - pre_l

		loop do
			pos = relative(find_side(front, right))
			case pos
			when ['F', 'R']; break
			when ['R', 'B']; r_F; r_Bi; r_Fi
			when ['B', 'F']; r_Ri; r_B; r_R
			# optimized side switch
			when ['R', 'F']; r_Ri; r_Bi; r_R
			when ['F', 'L']; r_T; r_Fi; r_B; r_F; r_Ti
			when ['L', 'F']; r_T; r_L; r_B; r_Li; r_Ti
			when ['K', 'L']; r_T; r_T; r_K; r_Bi; r_Ki; r_T; r_T
			when ['L', 'K']; r_T; r_T; r_Li; r_B; r_L; r_T; r_T
			when ['K', 'R']; r_Ti; r_R; r_Bi; r_Ri; r_T
			when ['R', 'K']; r_Ti; r_Ki; r_Bi; r_K; r_T
			else r_B
			end
		end

		nr_T_ini.times { r_Ti }
	end

	# finish the last side+corner of side1+2
	def solve_f12_last(s1, c1)
		s2 = Right[[top, s1]]
		c2 = Right[[top, c1]]

		orient(top, s1)

		r_T until @face[front][top][1] == c1

		loop do
			pos_s = relative(find_side(s1, s2))
			pos_c = relative(find_corner(c1, c2, top))


			if pos_s == pos_c[0, 2]
				case pos_s
				when ['F', 'R']; break
				when ['R', 'F']; r_Ri; r_B; r_R
				when ['K', 'B']; r_F; r_B; r_B; r_Fi
				when ['B', 'L']; r_Li; r_B; r_B; r_L
				else r_B
				end
			elsif pos_c[2] == 'B'
				case pos_s
				when ['F', 'R']
					if pos_c == ['K', 'R', 'B']; r_B
					else r_Ri; r_B; r_B; r_R
					end
				when ['F', 'B']
					case pos_c
					when ['R', 'F', 'B']; r_Bi; r_F; r_Bi; r_Fi
					when ['F', 'L', 'B']; r_B; r_B; r_Ri; r_B; r_R
					else r_Ri; r_B; r_R
					end
				when ['B', 'R']
					case pos_c
					when ['R', 'F', 'B']; r_B; r_Ri; r_B; r_R
					when ['K', 'R', 'B']; r_B; r_B; r_F; r_Bi; r_Fi
					else r_F; r_Bi; r_Fi
					end
				else r_B	# s = RF too
				end
			else
				case pos_c
				when ['F', 'R', 'T']; r_Ri; r_B; r_R
				when ['R', 'T', 'F']; r_Ri; r_Bi; r_R
				when ['T', 'F', 'R']; r_F; r_B; r_Fi
				when ['F', 'B', 'R']; r_F; r_Bi; r_Fi
				when ['B', 'R', 'F']; r_Ri; r_B; r_R
				else r_B
				end
			end
		end

		r_T until @face[front][top][1] == front
	end

	def solve_f3
		solve_f3_crossset
		show_adv

		solve_f3_crossorder
		show_adv

		solve_f3_cornorder
		show_adv

		solve_f3_cornset
		show_adv
	end

	# solve the cross on top face
	def solve_f3_crossset
		while Borders[top].find { |c2| @face[top][c2][1] != top }
			if c = Borders[top].find { |c2| @face[top][c2][1] == top }
				# good @ back/left
				orient(top, c)
				orient(top, right)
				if @face[top][front][1] == top
					orient(top, right)
				end
			end
			r_Ri; r_Ti; r_Fi; r_T; r_F; r_R
		end
	end
	
	# orient the cross on top face
	def solve_f3_crossorder
		fc = lambda { |cc| @face[cc][top][1] }
		loop do
			if fc[front] == Opposite[fc[back]]
				if fc[right] == Right[[top, fc[front]]]
					break
				else
					r_K; r_T; r_Ki; r_T; r_K; r_T; r_T; r_Ki
				end
			else
				c = Borders[top].find { |cc| fc[Right[[top, cc]]] == Right[[top, fc[cc]]] }
				orient(top, Opposite[c])
				r_K; r_T; r_Ki; r_T; r_K; r_T; r_T; r_Ki
			end
		end

		r_T until @face[front][top][1] == front
	end

	# move the corners on last face
	def solve_f3_cornorder
		sort = lambda { |a| a.sort_by { |e| e.to_s } }
		loop do
			good = Borders[top].find_all { |c2|
				c3 = Right[[top, c2]]
				sort[find_corner(top, c2, c3)] == sort[[top, c2, c3]]
			}
			case good.length
			when 4; break
			when 1
				orient(top, Opposite[good.first])
				if sort[find_corner(top, front, right)] == sort[[top, front, left]]
					orient(top, right)
					r_L; r_Ri; r_Ti; r_R; r_T; r_Li; r_Ti; r_Ri; r_T; r_R
					next
				end
			end
			r_L; r_Ri; r_T; r_Li; r_Ti; r_R; r_T; r_L; r_Ti; r_Li
		end
	end

	# orient the corners on last face
	def solve_f3_cornset
		loop do
			good = Borders[top].find_all { |c2| @face[top][c2][0] == top }
			case good.length
			when 4; break
			when 3; raise "broken cube !"
			end

			if Borders[top].find { |c2|
				orient(top, c2)
				@face[left][top][2] == top and @face[right][top][0] == top
			}
			elsif good.first
				orient(top, Opposite[good.first])
				orient(top, right) if @face[top][left][0] == top or @face[back][top][0] == top
			end

			# top2front
			r_K; r_T; r_Ki; r_T; r_K; r_T; r_T; r_Ki
			r_Fi; r_Ti; r_F; r_Ti; r_Fi; r_T; r_T; r_F
			# TODO find front2top
		end
	end

	# compose movements; remove m1, -m1; compose m1, m1, m1 => -m1
	def simplify_sequence(seq)
		seq = seq.dup

		osq = []
		while osq != seq
			osq = seq.dup

			# bubblesort seq to group same color moves
			# only switch opposite face moves
			i = 0
			while i < seq.length - 1
				if seq[i][0] == Opposite[seq[i+1][0]] and seq[i][0].to_s > seq[i+1][0].to_s
					seq[i], seq[i+1] = seq[i+1], seq[i]
				end
				i += 1
			end

			i = 0
			while i < seq.length - 1
				if seq[i+1][0] == seq[i][0]
					if seq[i+1] == seq[i]
						if seq[i+2] == seq[i]
							# A A A == -A
							seq.delete_at(i)
							seq.delete_at(i)
							seq[i] = [seq[i][0], !seq[i][1]]
							next
						end
					else
						# A -A == nop
						seq.delete_at(i)
						seq.delete_at(i)
						next
					end
				end
				i += 1
			end
		end

		seq
	end

	def seq_to_s(seq=@seq)
		str = ["#{seq.length}:"]
		seq = seq.dup
		while seq.first
			str << seq[0, 30].map { |c| "#{c[0]}#{c[1] ? '+' : '-'}" }.join(' ').upcase
			seq[0, 30] = []
		end
		str.join("\n")
	end

	def to_s
		empty = [' ']*3

		# array of lines
		# each line is an array of arrays of colors (for the color sequence of one face)
		ret = []

		b = @face[back]
		ret << [empty, b[bottom]]
		ret << [empty, [b[left][1], b[:color], b[right][1]]]
		ret << [empty, b[top].reverse]

		ret << []
		
		fl = [left, top, right, bottom].map { |c| @face[c] }
		ret << fl.map { |f| f[back] }
		ret << fl.map { |f|
			i = fl.index(f)
			pv = fl[i-1][:color]
			nt = fl[i-fl.length+1][:color]
			[f[pv][1], f[:color], f[nt][1]]
		}
		ret << fl.map { |f| f[front].reverse }

		ret << []

		f = @face[front]
		ret << [empty, f[top]]
		ret << [empty, [f[left][1], f[:color], f[right][1]]]
		ret << [empty, f[bottom].reverse]

		ret.map { |ln|
			ln.map { |s| ' ' << s.join(' ') << ' ' }.join(' ')
		}.join("\n") + "\n\n"
	end
end

if $0 == __FILE__
	if ARGV.first and File.exist?(ARGV.first)
		c = Cube.load_template File.read(ARGV.first)
		c.reset_seq_adv = true if ARGV.delete '-i'
		puts c.solve
	else
		c = Cube.new
		case ARGV.first
		when 'random', 'shuffle'
			c.shuffle
		when /^[rwgyob]/i
			c.orient ARGV.first.downcase[0, 1].to_sym
		end
		puts c
	end
end