Foreword
I’ve started to play Lego Video games with my daughter, and since it’s one of her first games, it can be a little frustrating.
Even though there are no high stakes (you can’t lose in those games), I thought maybe playing with the cheats might make a better experience.
If you are not familiar with the games, you enter cheats via an interface like this:
Despite playing on a computer and with a perfectly usable keyboard, I cannot type the input directly.
Instead, I must use this six-position combination lock that uses letters and numbers.
It’s cyclic and goes from A to Z, 0 to 9 and back to A again.
Up goes forwards; Down goes backwards.
I thought about finding an efficient way of input because it’s not enough to enter and unlock the cheat once.
You have to reenter the cheat for every new game session.
The plan
- I’ll create a table representing one dial with letters and numbers in sequence.
- Then I’ll generate all possible combinations and calculate the shortest distance. Is it faster to change from M to 5 going up or down?
- Now that I can calculate the distance for letters, I’ll create a function that does the same but for the whole cheat codes.
- I’ll generate all code combinations.
- Finally, I will use a greedy algorithm to find a short path.
The code
Create the LetterSequence
First, we’ll create the database and table to hold our sequence.
CREATE DATABASE LegoCheats
GO
USE LegoCheats
CREATE TABLE dbo.LetterSequence
(
SequenceNo tinyint IDENTITY NOT NULL INDEX IX_SequenceNo UNIQUE
, Letter char(1) NOT NULL CONSTRAINT PK_LetterOrder PRIMARY KEY
)
I wish I had the STRING_SPLIT parameter enable_ordinal, but at the time of writing, it’s available only on Azure SQL and is planned for SQL Server 2022.
So I’ll have to use the target table Identity to simulate that.
To get the string, I wrote abcdefghijklmnopqrstuvwxyz0123456789 and then used RegEx to add a separator.
Find B, Replace ,
INSERT INTO dbo.LetterSequence (Letter)
SELECT UPPER(value)
FROM STRING_SPLIT('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,0,1,2,3,4,5,6,7,8,9', ',')
Create the LetterDistance
Now we calculate the shortest distance for each combination.
After creating the table, I’ll grab the maximum sequence number (36).
When I cross the boundary between the start and end of the sequence, I’ll add the @maxLetterSeqno and use the modulo operator (%) to wrap around.
When the distance is the same both ways (like 0 or 18), I’ll pick the direction as DOWN because it doesn’t matter.
CREATE TABLE dbo.LetterDistance
(
LetterFrom char(1) NOT NULL
, LetterTo char(1) NOT NULL
, Distance tinyint NOT NULL
, Direction varchar(10) NULL
, CONSTRAINT PK_LetterDistance PRIMARY KEY (LetterFrom, LetterTo)
)
DECLARE @maxLetterSeqno tinyint = (SELECT MAX(SequenceNo) FROM dbo.LetterSequence)
INSERT INTO dbo.LetterDistance
(LetterFrom, LetterTo, Distance, Direction)
SELECT
f.Letter AS FromLetter
, t.Letter AS ToLetter
, md.minDist
, md.direction
FROM dbo.LetterSequence AS f
CROSS JOIN dbo.LetterSequence AS t
CROSS APPLY
(
VALUES
(
CASE
WHEN f.SequenceNo >= t.SequenceNo
THEN f.SequenceNo - t.SequenceNo
ELSE ((@maxLetterSeqno + f.SequenceNo - t.SequenceNo) % @maxLetterSeqno)
END,
CASE
WHEN t.SequenceNo >= f.SequenceNo
THEN t.SequenceNo - f.SequenceNo
ELSE ((@maxLetterSeqno + t.SequenceNo - f.SequenceNo) % @maxLetterSeqno)
END
)
) AS distance (MoveMinus, MovePlus)
CROSS APPLY
(
VALUES
(
CASE WHEN distance.MoveMinus <= distance.MovePlus
THEN distance.MoveMinus
ELSE distance.MovePlus
END
,
CASE WHEN distance.MoveMinus <= distance.MovePlus
THEN 'DOWN'
ELSE 'UP'
END
)
) AS md(minDist, direction)
Here’s the answer to the earlier question (shortest path from M to 5)
SELECT *
FROM dbo.LetterDistance AS ld
WHERE
ld.LetterFrom = 'M'
AND ld.LetterTo = '5'
Calculate word distance
Now that I can calculate the individual letter distance, I’ll move on to the whole words.
I’ll create an Inlinable Table-Valued Function (ITVF) where there are two words as an input and a total distance + instructions as an output. I’m not counting the movement required to switch between the dials.
CREATE OR ALTER FUNCTION dbo.WordDistance
(
@wordFrom char(6)
, @wordTo char(6)
)
RETURNS table
AS
RETURN
WITH unpivotLetters AS
(
SELECT
SUBSTRING(@wordFrom, cj.Position, 1) AS letterFrom
, SUBSTRING(@wordTo, cj.Position, 1) AS letterTo
, cj.Position
FROM (VALUES (1), (2), (3), (4), (5), (6)) AS cj(Position)
)
SELECT
SUM(ca.Distance) AS WordDistance
, MAX(IIF(ul.Position = 1, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter1
, MAX(IIF(ul.Position = 2, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter2
, MAX(IIF(ul.Position = 3, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter3
, MAX(IIF(ul.Position = 4, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter4
, MAX(IIF(ul.Position = 5, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter5
, MAX(IIF(ul.Position = 6, CONCAT_WS(' ', ca.Distance, ca.Direction), NULL)) AS Letter6
FROM unpivotLetters AS ul
CROSS APPLY
(
SELECT ld.Distance, ld.Direction
FROM dbo.LetterDistance AS ld
WHERE
ld.LetterFrom = ul.letterFrom
AND ld.LetterTo = ul.LetterTo
) AS ca
Score word combinations
To test this out, I have prepared a list of cheats for the Lego Batman: The Videogame that I want to apply.
I will generate all combinations (except with itself), calculate the word distance and save them into a WordCombination table.
/* Prepare the tables */
CREATE TABLE dbo.WordCombination
(
IdFrom tinyint NOT NULL
, WordFrom char(6) NOT NULL
, WordFromDescription varchar(70) NULL
, IdTo tinyint NOT NULL
, WordTo char(6) NOT NULL
, WordToDescription varchar(70) NULL
, TotalDistance int NOT NULL
, CONSTRAINT PK_WordCombination PRIMARY KEY (IdFrom, IdTo)
)
CREATE TABLE #CheatCodes
(
Id tinyint NOT NULL
, Word char(6) NOT NULL
, CheatDescription varchar(70) NULL
)
/* Insert the cheat codes, I include the starting point as well */
INSERT INTO #CheatCodes (Id, Word, CheatDescription)
VALUES
(01, 'AAAAAA', 'Initial position')
,(02, 'ML3KHP', 'Extra Hearts')
,(03, 'JRBDCB', 'Faster Batarangs')
,(04, 'EVG26J', 'Faster Piece Assembly')
,(05, 'ZOLM6N', 'Faster Walking')
,(06, 'D8NYWH', 'Flaming Batarangs')
,(07, 'XPN4NG', 'Frozen Batarangs')
,(08, 'HJH7HJ', 'Heart Regeneration')
,(09, 'JXUDY6', 'Immunity to Freeze')
,(10, 'WYD5CP', 'Invincibility')
,(11, 'ZXGH9J', 'Minikit Detector')
,(12, '9LRGNB', 'Multiply Score')
,(13, 'KHJ544', 'Piece Detector')
,(14, 'MMN786', 'Power Brick Detector')
,(15, 'N4NR3E', 'Score Multiplier x2')
,(16, 'CX9MAT', 'Score Multiplier x4')
,(17, 'MLVNF2', 'Score Multiplier x6')
,(18, 'WCCDB9', 'Score Multiplier x8')
,(19, '18HW07', 'Score Multiplier x10')
INSERT INTO dbo.WordCombination
(
IdFrom
, WordFrom
, WordFromDescription
, IdTo
, WordTo
, WordToDescription
, TotalDistance
)
SELECT
f.Id
, f.Word
, f.CheatDescription
, t.Id
, t.Word
, t.CheatDescription
, wd.WordDistance
FROM #CheatCodes AS f/* from */
CROSS JOIN #CheatCodes AS t/* to */
CROSS APPLY dbo.WordDistance(f.Word, t.Word) AS wd
WHERE f.Id <> t.Id /* all combinations except itself */
/* Check the result */
SELECT *
FROM dbo.WordCombination AS wc
ORDER BY wc.IdFrom, wc.TotalDistance
Finding efficient path
Ideally, I want to enter every cheat from my #CheatCodes temp table with as few moves as possible. That’s 18 entries (the first row is the initial state).
I’ve chosen to use a greedy algorithm that uses a loop, for simplicity.
I will start on the AAAAAA position and pick the first word with the lowest distance until all words have been visited.
CREATE TABLE #FinalPath
(
SeqNo tinyint IDENTITY NOT NULL
, IdFrom tinyint NOT NULL
, IdTo tinyint NOT NULL
)
DECLARE @LoopCounter tinyint = 1
DECLARE @IdFrom tinyint = 1 /* AAAAAA */
DECLARE @IdTo tinyint
DECLARE @maxId tinyint = (SELECT MAX(cc.Id) FROM #CheatCodes AS cc)
WHILE @LoopCounter <= @maxId
BEGIN
SELECT TOP (1)
@IdTo = wc.IdTo
FROM dbo.WordCombination AS wc
WHERE
wc.IdFrom = @IdFrom
AND NOT EXISTS
(
SELECT *
FROM #FinalPath AS fp
WHERE fp.IdFrom = wc.IdTo
)
ORDER BY wc.TotalDistance
INSERT INTO #FinalPath (IdFrom, IdTo)
SELECT @IdFrom, @IdTo
SET @IdFrom = @IdTo
SET @LoopCounter += 1
END
SELECT
wc.WordFrom
, wc.WordTo
, wc.WordToDescription
, SUM(wd.WordDistance) OVER () AS TotalDistanceSum
, wd.WordDistance
, wd.Letter1
, wd.Letter2
, wd.Letter3
, wd.Letter4
, wd.Letter5
, wd.Letter6
FROM #FinalPath AS fp
JOIN dbo.WordCombination AS wc
ON fp.IdFrom = wc.IdFrom
AND fp.IdTo = wc.IdTo
CROSS APPLY dbo.WordDistance(wc.WordFrom, wc.WordTo) AS wd
ORDER BY fp.SeqNo
I have to test it on the real thing, of course.
Optimal path
I’ve used the word “efficient” instead of “optimal” on purpose. That’s because this is a famous computer science problem called
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?
And finding the optimal path would significantly increase the scope of this blog post.
There is always a brute force solution, but the number of combinations ramps up quickly.
I’ve tried brute-forcing the solution for the first 12 rows (1 starting position + 11 cheats), and it took my pc 1 hour and 6 minutes to come up with the best path
1-3-9-12-7-10-11-5-2-8-4-6 for the total distance of 409.
The greedy algorithm came up with 1-3-8-4-11-5-10-7-12-9-6-2 (total distance = 456), which is good enough for me.
It is an interesting problem, so I might revisit it in a future blog post.