Post date: Oct 09, 2016 1:8:0 PM
"Find the three most often hit squares on a monopoly board if two d4 were used instead of d6. If the squares are numbered 00 to 39, starting at GO, give a string containing the codes for the three squares in order of probability."
I really didn't want to build a SQL monopoly Monte Carlo simulation. There are problems that aren't made for SQL but which are interesting, and then there's this... It's a stupid SQL trick, but it's also incredibly boring. It's not even a fun game.
What makes it worse is that SQL's random generator is terrible. Just how terrible? Run this ten times and you'll get the same number every time: SELECT RAND(42). I don't know if that even qualifies as pseudo-random. Normally I'd use a C# function here, but that would be cheating.
In case you didn't guess, this problem is a Monte Carlo simulation so it's supposed to be random, so it might not generate the right answer every time. It's all about chance, which means the chance of a wrong answer exists even when the code is correct. It's fairly consistent, if you look at it broadly, but freak occurrences happen, and some of the probability differences from one square to another are tiny and probably easy to throw off. I'm doing 1 million turns. It takes a long time. 10 million provides a clearer answer, but naturally it takes 10x as long and I have better things to do with my weekend.
It's been a long tedious slog and I'm basically sick of Project Euler at the moment.
SET NOCOUNT ON
GO
CREATE PROCEDURE dbo.GetUglyFakeRandomNumber(@result float OUTPUT)
AS
BEGIN
/* This can't be a function because you can't use the BS 'RAND' in a function. */
-- This ugly hackwork is probably the only interesting part of this problem.
-- It has some randomness although it's based on server properties.
-- Newid is a semi-random-seeming string of hex values. We use that as a seed.
-- When we call this function again, give it the previous answer, do some floating point math, and combine
DECLARE @c char(1), @seed int, @newid varchar(50) = newid()
-- Get rid of non-numbers in a RBAR way
WHILE @newid LIKE '%[^0-9]%'
BEGIN
SET @c = SUBSTRING(@newid, PATINDEX('%[^0-9]%', @newid),1)
SET @newid = REPLACE(@newid, @c, '')
END -- cleaning newid
IF LEN(@newid) % 2 = 0
SET @seed = LEFT(@newid,6)
ELSE
SET @seed = RIGHT(@newid,6)
-- The result value frequently holds the last value received. It might add a little more randomness.
IF @result IS NOT NULL
SET @seed = @seed + COS(SQUARE(@result))
SET @result = RAND(@seed)
END
GO
CREATE PROCEDURE dbo.PickChest
@next int OUTPUT
AS
BEGIN
SET @next = NULL
DECLARE @id int
SELECT @next = nextSquare, @id = id
FROM #Chest
WHERE player = 1
UPDATE #Chest
SET player = 0
WHERE player = 1
IF @id = 15 SET @id = -1
UPDATE #Chest
SET player = 1
WHERE id = @id + 1
END
GO
CREATE PROCEDURE dbo.PickChance
@current int,
@next int OUTPUT
AS
BEGIN
SET @next = NULL
DECLARE @id int, @G2R bit, @G2U bit, @GB3 bit
SELECT @next = nextSquare
, @G2R = G2R
, @G2U = G2U
, @GB3 = GB3
, @id = id
FROM #Chance
WHERE player = 1
UPDATE #Chance
SET player = 0
WHERE player = 1
IF @id = 15 SET @id = -1
UPDATE #Chance
SET player = 1
WHERE id = @id + 1
IF @next IS NOT NULL
RETURN
-- Next rail
IF @G2R = 1
BEGIN
SELECT @next = id
FROM #Board
WHERE R = 1 AND id > @current
IF @next IS NULL
SET @next = 5
RETURN
END -- Next railroad
-- Next util
IF @G2U = 1
BEGIN
SELECT @next = id
FROM #Board
WHERE U = 1 AND id > @current
IF @next IS NULL
SET @next = 12
RETURN
END -- Next utility
-- Go back 3 or not anywhere at all
IF @GB3 = 1
SET @next = @current - 3
END
GO
CREATE PROCEDURE dbo.PlayTurn
@pos int OUTPUT
AS
BEGIN
DECLARE @random float, @next int, @doubles int = 0, @d1 int = -1, @d2 int = -1
WHILE @d1 = @d2
BEGIN
-- Roll D1
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
SET @d1 = CEILING(@random * 4)
-- Roll D2
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
SET @d2 = CEILING(@random * 4)
-- Check for doubles
IF @d1 = @d2
BEGIN
IF @doubles = 2
BEGIN
SET @pos = 10 -- 3 doubles = go to jail
RETURN
END
ELSE
SET @doubles = @doubles + 1
END -- Doubles
-- Move on the board
SET @pos = @pos + @d1 + @d2
IF @pos > 39 SET @pos = @pos - 40
-- Chance
IF @pos IN (7, 22, 36)
BEGIN
EXEC dbo.PickChance @pos, @next OUTPUT
IF @next IS NOT NULL
SET @pos = @next
-- Go directly to jail
IF @pos = 10 RETURN
END -- Chance
-- Community chest
IF @pos IN (2, 17, 33)
BEGIN
EXEC dbo.PickChest @next OUTPUT
IF @next IS NOT NULL
SET @pos = @next
-- Go directly to jail
IF @pos = 10 RETURN
END -- Chest
-- Go directly to jail
IF @pos = 30
BEGIN
SET @pos = 10
RETURN
END
END -- Loop until the user is done.
END
GO
/* Let's set up the game. */
DECLARE @random float
/* Game board. */
CREATE TABLE #Board (
id int PRIMARY KEY NOT NULL,
R bit NOT NULL DEFAULT 0,
U bit NOT NULL DEFAULT 0
)
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 39
)
INSERT INTO #Board (id)
SELECT i
FROM Integers
UPDATE #Board SET R = 1 WHERE id IN (5, 15, 25, 35)
UPDATE #Board SET U = 1 WHERE id IN (12, 28)
/* Community chest. */
CREATE TABLE #Chest (
id int PRIMARY KEY NOT NULL,
player bit NOT NULL DEFAULT 0,
nextSquare int NULL
)
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 15
)
INSERT INTO #Chest (id)
SELECT i
FROM Integers
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
UPDATE #Chest
SET nextSquare = 0 -- GO
WHERE id = FLOOR(@random * 16)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS ( SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chest WHERE nextSquare IS NULL)
UPDATE c
SET nextSquare = 10 -- Jail
FROM #Chest c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 15)
UPDATE #Chest SET player = 1 WHERE id = 0
/* Chance */
CREATE TABLE #Chance (
id int PRIMARY KEY NOT NULL,
player bit NOT NULL DEFAULT 0,
G2R bit NOT NULL DEFAULT 0,
G2U bit NOT NULL DEFAULT 0,
GB3 bit NOT NULL DEFAULT 0,
nextSquare int NULL
)
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 15
)
INSERT INTO #Chance (id)
SELECT i
FROM Integers
-- This is going to be ugly, because there's no super clean way to shuffle a table.
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
UPDATE #Chance
SET nextSquare = 0 -- GO
WHERE id = FLOOR(@random * 16)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL)
UPDATE c
SET nextSquare = 10 -- Jail
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 15)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL)
UPDATE c
SET nextSquare = 11 -- C1
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 14)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL)
UPDATE c
SET nextSquare = 24 -- E3
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 13)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL)
UPDATE c
SET nextSquare = 39 -- H2
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 12)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL)
UPDATE c
SET nextSquare = 5 -- R1
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 11)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL)
UPDATE c
SET G2R = 1
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 10)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL AND G2R = 0)
UPDATE c
SET G2R = 1
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 9)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL AND G2R = 0)
UPDATE c
SET G2U = 1
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 8)
EXEC dbo.GetUglyFakeRandomNumber @random OUTPUT
; WITH UnSetCards (id, rn) AS (SELECT id, ROW_NUMBER() OVER (ORDER BY id) FROM #Chance WHERE nextSquare IS NULL AND G2R = 0 AND G2U = 0)
UPDATE c
SET GB3 = 1
FROM #Chance c
INNER JOIN UnSetCards u ON u.id = c.id
WHERE u.rn = FLOOR(@random * 7)
UPDATE #Chance SET player = 1 WHERE id = 0
CREATE TABLE #Turns (
id int PRIMARY KEY NOT NULL,
c int NOT NULL
)
INSERT INTO #Turns
SELECT id, 0
FROM #Board
/* Let's play this garbage. */
BEGIN TRY
-- Play 1 million turns
DECLARE @ctr int = 0, @pos int = 0
WHILE @ctr <= 1000000
BEGIN
EXEC dbo.PlayTurn @pos OUTPUT
UPDATE #Turns
SET c = c + 1
WHERE id = @pos
SET @ctr = @ctr + 1
END
END TRY
BEGIN CATCH
THROW;
END CATCH
DROP TABLE #Board
DROP TABLE #Chest
DROP TABLE #Chance
-- Get the three squares hit most often.
; WITH Answers (id, c, rn) AS
(
SELECT id, c, ROW_NUMBER() OVER (ORDER BY c DESC)
FROM #Turns
)
SELECT CONCAT(a1.id, a2.id, a3.id)
FROM Answers a1
INNER JOIN Answers a2
ON a2.rn = a1.rn + 1
INNER JOIN Answers a3
ON a3.rn = a2.rn + 1
WHERE a1.rn = 1
DROP TABLE #Turns
GO
DROP PROCEDURE dbo.GetUglyFakeRandomNumber
GO
DROP PROCEDURE dbo.PickChest
GO
DROP PROCEDURE dbo.PickChance
GO
DROP PROCEDURE dbo.PlayTurn
GO