A simulation study for https://thefiddler.substack.com/p/can-you-shut-the-box

shut_the_box.jl

### A Pluto.jl notebook ###
# v0.19.46

using Markdown
using InteractiveUtils

# ╔═╡ de87c273-9da1-403f-b0c0-af180e67f743
using Chairmarks

# ╔═╡ 751fe577-314a-43fb-bf79-6d6444642390
using Random

# ╔═╡ bab17b68-a71f-4328-83d1-1953905764e2
using Test

# ╔═╡ d295baf4-795b-4da4-b494-ee528e16d24b
using Statistics

# ╔═╡ 75ee0160-71e1-11ef-247c-3d0be493bf6e
md"""
# [Shut the Box](https://thefiddler.substack.com/i/148794545/this-weeks-fiddler)

In a simplified version of [Shut the Box](https://en.wikipedia.org/wiki/Shut_the_box), there are six initially unflipped tiles, numbered 1-6, on the side of a box. You roll a fair, six-sided die, after which you can flip down any combination of unflipped tiles that add to the roll. For example, if you roll a 5, you could flip down the 5, the 1 and the 4, or the 2 and the 3. You proceed until no set of flips is possible (e.g., you rolled a 3 but your only remaining tiles are 2 and 6). To win, you must flip down all six tiles.

Assuming you play with an optimal strategy (i.e., maximizing your chances of winning after any given roll), what is the probability that you’ll win?

## Answer

Optimal strategy is to use the numbers that get the least possible use first.
"""

# ╔═╡ 9ff07128-d445-423e-9595-8d31ee1fe3c2
sum_to::Dict{Int, Vector{Vector{Int}}} = Dict(
    1 => [[1]],
    2 => [[2]],
    3 => [[1, 2], [3]],
    4 => [[1, 3], [4]],
    5 => [[1, 4], [2, 3], [5]],
    6 => [[1, 5], [2, 4], [1, 2, 3], [6]],
)

# ╔═╡ 882d31f9-fbce-4ef9-a254-2eb8fb8e59e0
md"""
Now create a lookup table of the frequency of occurence of each number
"""

# ╔═╡ 5f828626-647c-47bc-bdc3-0105301cf8ff
freqs::Dict{Int, Int} = let
	res = Dict()
	for vecs in values(sum_to), v in vecs, val in v
		res[val] = get(res, val, 0) + 1
	end
	res
end

# ╔═╡ c35a0850-1bd0-4ce5-b4cf-03ac0db41f74
md"""
Now we need to combine the two to calculate the relative frequency of any combination of numbers that might be chosen.
"""

# ╔═╡ 12c15dd6-d69a-4f13-a4b9-21258e5e72fc
struct Use
	die_roll::Int8
	combo::Vector{Int8}
	cost::Int8
end

# ╔═╡ b47f6a0e-9fcc-41c8-adc6-7cdd1434457d
begin
	import Base.min
	min(a::Use, b::Use) = ifelse(a.cost <= b.cost, a, b)
end

# ╔═╡ 2a2896d3-1f28-4ae3-992a-0bf7458c6562
begin
	a = Use(1, [1,2,3], 2)
	b = Use(1, [6], 1)
	c = Use(2, [4,2], 4)
	min(a, b)
end

# ╔═╡ 63cda099-d056-4070-af10-374fc3e98622
const lookup::Vector{Use} = let
	res = Use[]
	for (die_roll, options) in pairs(sum_to)
		for opt in options
			cost = sum(freqs[o] for o in opt)
			push!(res, Use(die_roll, opt, cost))
		end
	end
	res
end

# ╔═╡ 4a607b75-4bb0-44b4-a5d8-4f3bb20f1923
struct GameState
	shut::UInt8
end

# ╔═╡ 141405a5-f7e1-4eb4-a79d-c76be70112b2
new_game() = GameState(UInt8(0))

# ╔═╡ 97e14651-590d-45e3-b812-d6e0addfb596
function Base.show(io::IO, gs::GameState)
    # Get the UInt8 value
    value = gs.shut

    # Collect indices of set bits
    indices = []
    for i in 0:7
        if value & (1 << i) != 0
            push!(indices, i+1)
        end
    end

    # Print the indices in a readable format
    print(io, indices)
end

# ╔═╡ 35dbfbc6-3478-471a-bd11-e4ceabd7d518
"""
Add each index from `inds` by setting the bit at that index, using 1-based indexing
"""
function update(gs::GameState, inds::Vector{UInt8})::GameState
    # Initialize the new shut value
    new_shut = gs.shut

    # Iterate through each index
    for index in inds
        # Convert 1-based index to 0-based index
        bit_index = index - 1
        
        # Set the bit at the converted index
        new_shut |= (1 << bit_index)
    end

    # Return a new GameState instance with the updated shut value
    return GameState(new_shut)
end


# ╔═╡ cc14bc4a-4689-4e57-baac-a4f44c21483a
function update(gs::GameState, inds::Vector)::GameState
	# If empty, just return gs
	if isempty(inds)
		return gs
	end
	
	# Convert all the inds to Int, then call the regular version
	new_inds = [UInt8(i) for i in inds]
	update(gs, new_inds)
end

# ╔═╡ 523586e1-8b8b-45e1-92c9-e5047a19a337
@testset "update GameState" begin
	gs = GameState(0)

	# Test setting single bits
	@test GameState(UInt8(0b000_001)) == update(gs, [1])
    @test GameState(UInt8(0b000_010)) == update(gs, [2])
    @test GameState(UInt8(0b000_100)) == update(gs, [3])
    @test GameState(UInt8(0b001_000)) == update(gs, [4])
    @test GameState(UInt8(0b010_000)) == update(gs, [5])
    @test GameState(UInt8(0b100_000)) == update(gs, [6])

    # Test setting multiple bits
    @test GameState(UInt8(0b000_011)) == update(gs, [1, 2])
    @test GameState(UInt8(0b000_111)) == update(gs, [1, 2, 3])
    @test GameState(UInt8(0b001_111)) == update(gs, [1, 2, 3, 4])
    @test GameState(UInt8(0b011_111)) == update(gs, [1, 2, 3, 4, 5])
    @test GameState(UInt8(0b111_111)) == update(gs, [1, 2, 3, 4, 5, 6])

    # Test setting bits with some overlap
    gs = GameState(0)
    gs_updated = update(gs, [1, 3, 5])
    @test GameState(UInt8(0b010_101)) == gs_updated
    @test GameState(UInt8(0b111_111)) == update(gs_updated, [2, 4, 6])
    
    # Test no changes with an empty index vector
    @test gs == update(gs, [])
end

# ╔═╡ b27dc04d-5ad7-4690-afe1-322f818b3266
let
	gs = GameState(0)
	inds = [1, 2, 3, 4, 5, 6]
	@be update(gs, inds)
end

# ╔═╡ 26e0ca5e-5c0f-4287-901c-20fffbf3fd29
has_won(gs::GameState) = UInt8(0b111_111) == gs.shut

# ╔═╡ f1a96419-cecd-4a83-87bb-a8bdfb4d14f4
@testset "has_won GameState" begin
	@test has_won(GameState(UInt8(0b111_111)))
	@test !has_won(GameState(UInt8(0b101_111)))
	@test !has_won(GameState(UInt8(0b101_110)))
	@test !has_won(GameState(UInt8(0b100_110)))
	@test !has_won(GameState(UInt8(0b000_000)))
end

# ╔═╡ 8fb47948-7246-4e52-9a16-d8c84cfbab88
@be has_won($new_game())

# ╔═╡ 2a8366d9-5668-4902-9f11-65f746b766f2
"Are these spots empty in the board?"
function is_valid_option(gs::GameState, new_spots::Vector{Int8})::Bool
	# For each bit in gs.shut, check if that index (1-based) has already been set
	# Iterate through each index
    for index in new_spots
        # Convert 1-based index to 0-based index
        bit_index = index - 1
        
        # If that bit is already set, return false
		if (gs.shut | (1 << bit_index)) == gs.shut
			return false
		end
    end

	true
end

# ╔═╡ 9b195fb0-dfc3-4855-8cbf-101002d74a4b
function is_valid_option(gs::GameState, new_spots)::Bool
	isempty(new_spots) && return true
	
	is_valid_option(gs, [Int8(i) for i in new_spots])
end

# ╔═╡ a87bd7af-51bd-419b-9d92-b2f940a2f80b
@testset "is_valid_option" begin
    # Initial GameState with no bits set (all spots are empty)
    gs = GameState(UInt8(0b000000))  # All spots are empty

    # Test single empty spot
    @test is_valid_option(gs, [1]) == true
    @test is_valid_option(gs, [2]) == true
    @test is_valid_option(gs, [3]) == true

    # Test multiple empty spots
    @test is_valid_option(gs, [1, 2, 3]) == true
    @test is_valid_option(gs, [4, 5, 6]) == true

    # GameState where some bits are set (spots are filled)
    gs = GameState(UInt8(0b010011))  # Spots 1, 2, and 5 are filled (1-based index)

    # Test some filled spots
    @test is_valid_option(gs, [1]) == false  # Spot 1 is filled
    @test is_valid_option(gs, [2]) == false  # Spot 2 is filled
    @test is_valid_option(gs, [5]) == false  # Spot 5 is filled

    # Test some empty spots
    @test is_valid_option(gs, [3]) == true   # Spot 3 is empty
    @test is_valid_option(gs, [4]) == true   # Spot 4 is empty
    @test is_valid_option(gs, [6]) == true   # Spot 6 is empty

    # Test a combination of filled and empty spots
    @test is_valid_option(gs, [1, 3, 6]) == false  # Spot 1 is filled
    @test is_valid_option(gs, [3, 4, 6]) == true   # All are empty
    
    # Test an empty list of spots (should always be valid)
    @test is_valid_option(gs, []) == true
	@test is_valid_option(gs, Int8[]) == true
end


# ╔═╡ 2c5d6501-f411-437e-a6e7-951836f013c4
@be is_valid_option($new_game(), $[1])

# ╔═╡ c1dca031-a1a5-42e4-8793-5773b7b8528f
@enum Status begin
	StillGoing
	Lost
	Won
end

# ╔═╡ b79326a5-e0fa-41d0-bd17-127fe263462d
"""
For the current game state and die roll, get the option from the lookup table
with the lowest cost.

If there are no options remaining, return (false, gs)
"""
function get_next_move(
    gs::GameState,
    die_roll::Int,
    lookup::Vector{Use},
)::Tuple{Bool, GameState}
    # Initialize variables to track the best option
    best_option = nothing
    best_cost = typemax(Int8)  # Start with the maximum possible value for comparison

    # Iterate through the lookup table
    for entry in lookup
        # Check if the die_roll matches any entry's die_roll, and
		# if we can fit it in
        if (die_roll == entry.die_roll) && 
			is_valid_option(gs, entry.combo) &&
			(entry.cost < best_cost)

			# Update the best_option if this entry has a lower cost
			best_cost = entry.cost
			best_option = entry
        end
    end

    # If a valid option was found, apply it and return the updated state
    if best_option !== nothing
        updated_gs = update(gs, best_option.combo)
        return (true, updated_gs)
    else
        return (false, gs)
    end
end

# ╔═╡ 020e82ce-90ed-4d68-9a68-84e21c89611b
let
	gs = GameState(UInt8(0b000_000))
	die_roll = 4
	@be get_next_move(gs, die_roll, lookup)
end

# ╔═╡ 3edcdfd5-9654-43de-b935-8110e183c1de
@testset "get_next_move" begin
	# For the case of an empty board, and roll a 1, have to use a 1
	gs = GameState(UInt8(0b000_000))
	die_roll = 1
	@test get_next_move(gs, die_roll, lookup) == (true, GameState(UInt8(0b000_001)))

	# For 2, the only option is 2
	gs = GameState(UInt8(0b000_000))
	die_roll = 2
	@test get_next_move(gs, die_roll, lookup) == (true, GameState(UInt8(0b000_010)))

	# For 3, and an empty board, 3 is the best option
	gs = GameState(UInt8(0b000_000))
	die_roll = 3
	@test get_next_move(gs, die_roll, lookup) == (true, GameState(UInt8(0b000_100)))

	# For 3, and 3 spot is filled, must use 1 and 2
	gs = GameState(UInt8(0b000_100))
	die_roll = 3
	@test get_next_move(gs, die_roll, lookup) == (true, GameState(UInt8(0b000_111)))

	# If roll a 1, and 1 is filled, game over
	gs = GameState(UInt8(0b000_001))
	die_roll = 1
	@test get_next_move(gs, die_roll, lookup) == (false, gs)

	# Same for 2
	gs = GameState(UInt8(0b000_010))
	die_roll = 2
	@test get_next_move(gs, die_roll, lookup) == (false, gs)

	# For 6, and empty board, 6 is best option
	gs = GameState(UInt8(0b000_000))
	die_roll = 6
	@test get_next_move(gs, die_roll, lookup) == (true, GameState(UInt8(0b100_000)))

	# For 6, but 6 and 5 are already filled, 2 and 4 are best
	gs = GameState(UInt8(0b110_000))
	die_roll = 6
	@test get_next_move(gs, die_roll, lookup) == (true, GameState(UInt8(0b111_010)))

end

# ╔═╡ 42db343b-46fb-4e44-afdb-75a784f533de
"""
Play the next round. If won, return true
"""
function next(gs::GameState, lookup::Vector{Use}, rng::AbstractRNG)::Tuple{Status, GameState}
	# If over, return that we won
	if has_won(gs)
		return (Won::Status, gs)
	end

	# Roll die, and get options
	die_roll = rand(rng, 1:6)
	passed, gs = get_next_move(gs, die_roll, lookup)
	if !passed
		return (Lost::Status, gs)		
	end

	(StillGoing::Status, gs)
end

# ╔═╡ ca62aee5-d661-46f9-bd53-1d3f278980b5
function next(gs::GameState, lookup::Vector{Use})
	next(gs, lookup, Random.default_rng())
end

# ╔═╡ 93ccbc8b-f9b5-4fd5-ab83-a4f3f7c8d1bd
@testset "next" begin
	# Should always pass for an empty board
	gs = GameState(UInt8(0b000_000))
	for _ in 1:100
		(passed, new_gs) = next(gs, lookup)
		@test passed == StillGoing::Status
	end

	# For a full board, should win
	gs = GameState(UInt8(0b111_111))
	(status, new_gs) = next(gs, lookup)
	@test status == Won::Status
	@test new_gs == gs
end

# ╔═╡ 0ee5abc6-cedb-4151-8a3f-c53cce96c2d8
function play_game(lookup)
	# Create an empty board
	gs = new_game()

	# Iterate till we lose or win
	while true
		(status, gs) = next(gs, lookup)
		if status == Won::Status
			return (true, gs)
		elseif status == Lost::Status
			return (false, gs)
		end
	end
end

# ╔═╡ 6ef69769-066a-44d6-b5b6-7f815b431ea4
pct_win = mean(first(play_game(lookup)) for _ in 1:10_000_000)

# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
Chairmarks = "0ca39b1e-fe0b-4e98-acfc-b1656634c4de"
Random = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"
Statistics = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"
Test = "8dfed614-e22c-5e08-85e1-65c5234f0b40"

[compat]
Chairmarks = "~1.2.1"
"""

# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised

julia_version = "1.10.5"
manifest_format = "2.0"
project_hash = "4976748c1c8d63cfde5fd69b3834f14fc80e9ca8"

[[deps.Artifacts]]
uuid = "56f22d72-fd6d-98f1-02f0-08ddc0907c33"

[[deps.Base64]]
uuid = "2a0f44e3-6c83-55bd-87e4-b1978d98bd5f"

[[deps.Chairmarks]]
deps = ["Printf"]
git-tree-sha1 = "989bd3bb757ac0231fc77103e1b516e05c7d21f1"
uuid = "0ca39b1e-fe0b-4e98-acfc-b1656634c4de"
version = "1.2.1"
weakdeps = ["Statistics"]

    [deps.Chairmarks.extensions]
    StatisticsChairmarksExt = ["Statistics"]

[[deps.CompilerSupportLibraries_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "e66e0078-7015-5450-92f7-15fbd957f2ae"
version = "1.1.1+0"

[[deps.InteractiveUtils]]
deps = ["Markdown"]
uuid = "b77e0a4c-d291-57a0-90e8-8db25a27a240"

[[deps.Libdl]]
uuid = "8f399da3-3557-5675-b5ff-fb832c97cbdb"

[[deps.LinearAlgebra]]
deps = ["Libdl", "OpenBLAS_jll", "libblastrampoline_jll"]
uuid = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[[deps.Logging]]
uuid = "56ddb016-857b-54e1-b83d-db4d58db5568"

[[deps.Markdown]]
deps = ["Base64"]
uuid = "d6f4376e-aef5-505a-96c1-9c027394607a"

[[deps.OpenBLAS_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "Libdl"]
uuid = "4536629a-c528-5b80-bd46-f80d51c5b363"
version = "0.3.23+4"

[[deps.Printf]]
deps = ["Unicode"]
uuid = "de0858da-6303-5e67-8744-51eddeeeb8d7"

[[deps.Random]]
deps = ["SHA"]
uuid = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"

[[deps.SHA]]
uuid = "ea8e919c-243c-51af-8825-aaa63cd721ce"
version = "0.7.0"

[[deps.Serialization]]
uuid = "9e88b42a-f829-5b0c-bbe9-9e923198166b"

[[deps.SparseArrays]]
deps = ["Libdl", "LinearAlgebra", "Random", "Serialization", "SuiteSparse_jll"]
uuid = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"
version = "1.10.0"

[[deps.Statistics]]
deps = ["LinearAlgebra", "SparseArrays"]
uuid = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"
version = "1.10.0"

[[deps.SuiteSparse_jll]]
deps = ["Artifacts", "Libdl", "libblastrampoline_jll"]
uuid = "bea87d4a-7f5b-5778-9afe-8cc45184846c"
version = "7.2.1+1"

[[deps.Test]]
deps = ["InteractiveUtils", "Logging", "Random", "Serialization"]
uuid = "8dfed614-e22c-5e08-85e1-65c5234f0b40"

[[deps.Unicode]]
uuid = "4ec0a83e-493e-50e2-b9ac-8f72acf5a8f5"

[[deps.libblastrampoline_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "8e850b90-86db-534c-a0d3-1478176c7d93"
version = "5.11.0+0"
"""

# ╔═╡ Cell order:
# ╟─75ee0160-71e1-11ef-247c-3d0be493bf6e
# ╠═de87c273-9da1-403f-b0c0-af180e67f743
# ╠═751fe577-314a-43fb-bf79-6d6444642390
# ╠═9ff07128-d445-423e-9595-8d31ee1fe3c2
# ╠═882d31f9-fbce-4ef9-a254-2eb8fb8e59e0
# ╠═5f828626-647c-47bc-bdc3-0105301cf8ff
# ╠═c35a0850-1bd0-4ce5-b4cf-03ac0db41f74
# ╠═12c15dd6-d69a-4f13-a4b9-21258e5e72fc
# ╠═b47f6a0e-9fcc-41c8-adc6-7cdd1434457d
# ╠═2a2896d3-1f28-4ae3-992a-0bf7458c6562
# ╠═63cda099-d056-4070-af10-374fc3e98622
# ╠═bab17b68-a71f-4328-83d1-1953905764e2
# ╠═4a607b75-4bb0-44b4-a5d8-4f3bb20f1923
# ╠═141405a5-f7e1-4eb4-a79d-c76be70112b2
# ╠═97e14651-590d-45e3-b812-d6e0addfb596
# ╠═35dbfbc6-3478-471a-bd11-e4ceabd7d518
# ╠═cc14bc4a-4689-4e57-baac-a4f44c21483a
# ╠═523586e1-8b8b-45e1-92c9-e5047a19a337
# ╠═b27dc04d-5ad7-4690-afe1-322f818b3266
# ╠═26e0ca5e-5c0f-4287-901c-20fffbf3fd29
# ╠═f1a96419-cecd-4a83-87bb-a8bdfb4d14f4
# ╠═8fb47948-7246-4e52-9a16-d8c84cfbab88
# ╠═2a8366d9-5668-4902-9f11-65f746b766f2
# ╠═9b195fb0-dfc3-4855-8cbf-101002d74a4b
# ╠═a87bd7af-51bd-419b-9d92-b2f940a2f80b
# ╠═2c5d6501-f411-437e-a6e7-951836f013c4
# ╠═b79326a5-e0fa-41d0-bd17-127fe263462d
# ╠═020e82ce-90ed-4d68-9a68-84e21c89611b
# ╠═3edcdfd5-9654-43de-b935-8110e183c1de
# ╠═c1dca031-a1a5-42e4-8793-5773b7b8528f
# ╠═42db343b-46fb-4e44-afdb-75a784f533de
# ╠═ca62aee5-d661-46f9-bd53-1d3f278980b5
# ╠═93ccbc8b-f9b5-4fd5-ab83-a4f3f7c8d1bd
# ╠═0ee5abc6-cedb-4151-8a3f-c53cce96c2d8
# ╠═d295baf4-795b-4da4-b494-ee528e16d24b
# ╠═6ef69769-066a-44d6-b5b6-7f815b431ea4
# ╟─00000000-0000-0000-0000-000000000001
# ╟─00000000-0000-0000-0000-000000000002