-- Solitaire player, v2 --

--[[ Trying a little optimisation : call do_what_you_can only when we actually brought
--	a new card on the board. Not when only drawing and trashing.
--]]


---------------------
-- Stack functions --
---------------------

--[[ Our stacks have a last card (index of the top), and a master, the index of 
--	the lowest visible card. And we know that all cards from the master to 
--	the top are visible.
--]]

newstack = function ()
	return {last = 0, master = 0}
end

push = function (s,n)
	s.last = s.last + 1
	s[s.last] = n
end

pop = function (s)
	local t = s[s.last]
	if s.last == 0 then error("Pile vide") end
	s[s.last] = nil
	s.last = s.last - 1
	return t
end

top = function (s)
	return s[s.last]
end

master = function (s)
	return s[s.master]
end
	
staprint = function (s)
	for i = 1,s.last do
		if i == s.master then io.write("|") else io.write(" ") end
		io.write(string.format("%2d%s", s[i].num, s[i].family))
	end
	io.write("\n")
end

move = function(o, d, n)
	n = n or 1	-- default argument
	
	if n <= o.last then						-- always avoid stressing a pop function, so check we have enough cards to move
		local t = newstack()
	
		for i=1,n do push(t, pop(o)) end
		for i=1,n do push(d, pop(t)) end

		if o.master > o.last then o.master = o.last end		-- flip the remaining top card
		
		if d.master == 0 then d.master = 1 end			-- be careful when putting a king in an empty space, it becomes the master
		
		if verbose and drawmove then stateprint() end
		return true
	else
		return false
	end
end

-- Initialisation

math.randomseed(os.time())
verbose = false
drawmove = true

-- Cards definition
do
	cards = newstack()

	for i = 1,13 do
		cards[i] = { num = i , family = "P" , red = false }
		cards[i+13] = { num = i , family = "C" , red = true }
		cards[i+2*13] = { num = i , family = "K" , red = true }
		cards[i+3*13] = { num = i , family = "T" , red = false }
	end
	cards.last = 52
end

-- newscrambled returns a scrambled stack of 52 cards

newscrambled = function()
	local stack = newstack()
	local nums = {}

	for i=1,52 do nums[i] = i end

	for i=1,52 do
		local temp = math.random(#nums)
		push(stack, cards[nums[temp]])
		table.remove(nums, temp)
	end
	return stack
end

-- reset allows to set up a game

reset = function()
	
	draw = newscrambled()		-- master is not used in draw and trash piles, and usually have irrelevant values,
	trash = newstack()		-- due to the use of the move, push and pop functions.
	
	piles = {}
	endpiles = {}

	endpiles.P = newstack()
	endpiles.C = newstack()
	endpiles.K = newstack()
	endpiles.T = newstack()

	for i=1,7 do
		piles[i] = newstack()
	
		for j=1,i do
			push(piles[i], pop(draw))
		end

		piles[i].master = piles[i].last
	end
	
	if verbose then print("Reseting done. Ready to go.") end
end

-- prints the current state, to see something readable on screen

stateprint = function()

	print("-----------------")

	io.write("Draw : ") ; staprint(draw)
	io.write("Trash : ") ; staprint(trash)
	
	io.write("P : ") ; staprint(endpiles.P)
	io.write("C : ") ; staprint(endpiles.C)
	io.write("K : ") ; staprint(endpiles.K)
	io.write("T : ") ; staprint(endpiles.T)

	for i = 1,7 do
		io.write(i .. "°) ")
		staprint(piles[i])
	end

end

----------------------------------------------
-- Here come the actual "playing" functions --
----------------------------------------------

-- trypile tries to do something with the given pile, return true if manages to, false if did nothing

trypile = function(i)
	if piles[i].last > 0 then
		
		local ptop = top(piles[i])
		local pmaster = master(piles[i])
		
		-- if top card is an ace, put it on the end stack
		
		if ptop.num == 1 then
			move(piles[i], endpiles[ptop.family])
			return true
		end
		
		-- ditto for something else than an ace
			
		if endpiles[ptop.family].last > 0 and ptop.num == top(endpiles[ptop.family]).num + 1 then
			move(piles[i], endpiles[ptop.family])
			return true
		end
		
		-- then, check any possibility to move the master some place else
		
		for p = 1,7 do if p ~= i then
			
			-- first try a king in a hole (except if the king is already the bottom of the pile, to avoid looping indefinitely between holes)
			if pmaster.num == 13 and piles[p].last == 0 and piles[i].master > 1 then
				move(piles[i], piles[p], piles[i].last - piles[i].master + 1)
				return true
			end
			
			-- then a master on a higher and different color
			if piles[p].last > 0 and pmaster.num == top(piles[p]).num - 1 and pmaster.red ~= top(piles[p]).red then
				move(piles[i], piles[p], piles[i].last - piles[i].master + 1)
				return true
			end
		end end
	
	end
	
	return false
end

-- try_draw tries to play with the top card of the drawing stack

PLAYED, DISCARDED, CANTDRAW = {}, {}, {}	-- using unique adresses as constants

try_draw = function()
	if draw.last > 0 then
		
		local ptop = top(draw)
		
		-- if it is an ace, put it on the end stack
		
		if ptop.num == 1 then
			move(draw, endpiles[ptop.family])
			return PLAYED
		end
		
		-- ditto for something else than an ace
			
		if endpiles[ptop.family].last > 0 and ptop.num == top(endpiles[ptop.family]).num + 1 then
			move(draw, endpiles[ptop.family])
			return PLAYED
		end
		
		-- check any possibility to move the card some other place
		
		for p = 1,7 do
			
			-- first try a king in a hole
			if ptop.num == 13 and piles[p].last == 0 then
				move(draw, piles[p])
				return PLAYED
			end
			
			-- then the card on a higher and different color
			if piles[p].last > 0 and ptop.num == top(piles[p]).num - 1 and ptop.red ~= top(piles[p]).red then
				move(draw, piles[p])
				return PLAYED
			end
		end
		
		-- if we could do nothing, just trash the stupid card
		move(draw, trash)
		return DISCARDED
	end
	
	return CANTDRAW
end

-- move_what_you_can plays only with the cards on the board, not the drawing pile

move_what_you_can = function()
	local totalmodifs = 0		-- to know if we's done anything at all in the whole function
	local modifs = 321		-- anything but zero, to enter the loop at least once

	while modifs ~= 0 do		-- if we have done nothing this round, exit
	
		modifs = 0
		for i = 1,7 do
			if trypile(i) then modifs = modifs + 1
			totalmodifs = totalmodifs + 1 end
		end
	end
	
	return totalmodifs ~= 0
end

-- restore the trash into the draw pile

restore_trash = function()
	drawmove = false
	while trash.last > 0 do
		move(trash, draw)
	end
	drawmove = true
	if verbose then stateprint() end
end

-- check ending

win = function()
	return endpiles.P.last == 13 and endpiles.C.last == 13 and endpiles.K.last == 13 and endpiles.T.last == 13	
end

--------------------------------------------
-- Here come the different possible rules --
--------------------------------------------

-- play as long as you can without reusing the trash
-- Call move_what_you_can only the first time, and when try_draw actually changed something on the board

play = function()
	local realmodifs = 0		-- to know if we's done anything except drawing and discarding cards
	local did_anything = true	-- true, to enter the loop at least once
	local drawn_and_played = true	-- true, to call move_what_you_can at least once

	while did_anything do		-- if we have done nothing last round round (couldn't play and couldn't draw), exit
		did_anything = false	-- we'll set it true if anything happens
	
		if drawn_and_played then 
			if move_what_you_can() then
				did_anything = true
				realmodifs = realmodifs + 1
			end
		end
		
		local res = try_draw()
		if res == PLAYED then
			did_anything = true
			drawn_and_played = true
		elseif res == DISCARDED then
			did_anything = true
			drawn_and_played = false
		else					-- (res == CANTDRAW)
			-- did_anything isn't set to true
			drawn_and_played = false
		end
	end

	return realmodifs ~= 0
end

-- play with a maximum of "max" reuses of the trash. Negative value of "max" means no reuse limit

play_reuse = function(max)
	local iter = 0
	local res = true
	local prevres = true

	while true do
		prevres = res
		res = play()
		
		if not res and not prevres then return end	-- if we did nothing twice, despite restoring the trash,
								-- it's time to find a more interesting activity
		iter = iter + 1
		if max >= 0 and iter > max then return end					
		
		restore_trash()
	end
end
-------------------------------------
-- Where we actually have some fun --
-------------------------------------

make_stats = function(num, maxreuse)
	count = 0
	
	for i = 1,num do
		reset()
		play_reuse(maxreuse)
		if win() then count = count + 1 end
		
		if i % 1000 == 0 then print(i .. " tries, " .. count .. " wins.") end
	end

	print(num .. " tries, " .. count .. " wins.")
end

print("Yahoo, da Solitaire player...")
reset()

-- one example of starting state
stateprint()

-- play many games and count
make_stats(100000, -1)