Task

Write a player of the Bulls and Cows game, rather than a scorer. The player should give intermediate answers that respect the scores to previous attempts.

One method is to generate a list of all possible numbers that could be the answer, then to prune the list by keeping only those numbers that would give an equivalent score to how your last guess was scored. Your next guess can be any number from the pruned list.

Either you guess correctly or run out of numbers to guess, which indicates a problem with the scoring.



Related tasks

   Bulls and cows
   Guess the number
   Guess the number/With Feedback (Player)


local line = "---------+----------------------------------+-------+-------+"
local digits = {1,2,3,4,5,6,7,8,9}
 
function and_bits (a, b)
--	print (a, b)
	return a & b -- Lua 5.3
end
 
function or_bits (a, b)
	return a | b -- Lua 5.3
end
 
 
function get_digits (n)
	local tDigits = {}
	for i = 1, #digits do tDigits[i] = digits[i] end
	local ret = {}
 
	math.randomseed(os.time())
	for i = 1, n do
		local d = table.remove (tDigits, math.random(#tDigits))
		table.insert (ret, d)
	end
	return ret
end
 
function mask (x)
	return 3*x-1 -- any function
end
 
function score (guess, goal)
	local bits, bulls, cows = 0, 0, 0
 
	for i = 1, #guess do
		if (guess[i] == goal[i]) then
			bulls = bulls + 1
		else
			bits = bits + mask (goal[i])
		end
	end
	for i = 1, #guess do
		if not (guess[i] == goal[i]) then
			local nCow = (and_bits (bits, mask(guess[i])) == 0) and 0 or 1
			cows = cows + nCow
		end
	end
	return bulls, cows
end
 
function iCopy (list)
	local nList = {}
	for i = 1, #list do nList[i] = list[i] end
	return nList
end
 
function pick (list, n, got, marker, buf)
--	print ('pick', #list, n)
	local bits = 1
	if got >= n then
		table.insert (list, buf)
	else
		local bits = 1
		for i = 1, #digits do
			if and_bits(marker,bits) == 0 then
				buf[got+1] = i
				pick (list, n, got+1, or_bits (marker, bits), iCopy(buf))
			end
			bits = bits * 2
		end
	end
end
 
function filter_list (list, guess, bulls, cows)
	local index = 1
	for i = 1, #list do
--		print ('filter_list i: ' .. i)
		local scoreBulls, scoreCows = score (guess, list[i])
		if bulls == scoreBulls and cows == scoreCows then
			list[index] = list[i]
			index = index + 1
		end
	end
	for i = #list, index+1, -1 do
		table.remove (list, i)
	end
end
 
function game (goal)
	local n = #goal
	local attempt = 1
	local guess = {} -- n-length guess numbers array
	for i = 1, n do table.insert (guess, 0) end -- empty buffer
	local list = {}
	pick (list, n, 0, 0, guess)
 
	local bulls, cows = 0, 0
	while true do
		guess = list[1]
		bulls, cows = score (guess, goal)
		print (' Guess ' .. attempt .. ' |	' ..table.concat(guess), '('..#list..' variants)    ', bulls, cows)
		if bulls == n then return end
		filter_list (list, guess, bulls, cows)
		attempt = attempt + 1
	end
end
 
local n = 4
local secret = get_digits (n)
print (line..'\nSecret '.. #secret.. ' |      '..table.concat(secret) .. '			    | Bulls | Cows  |' .. '\n' .. line)
 
game (secret)