Surprisingly, the first (real) messages I got from my web log are from
people wanting me to help them… with The Sims Online (TSO). One
person wanted my key (see comments section). Of course, if I had
given this person my key, my ability to play would be sporadic (as
would the other person’s) if my account wasn’t canceled for having
too many duplicate sign-on attempts — or because the person gave my
key to some of his friends on alt.2600.cracks or something.
I did play a bunch of TSO yesterday. I like the maze game. I got
interested in the code game, as well, even though I have yet to play
it. I thought it was an interesting problem to solve.
Premise: you’re given three slots that can each contain one of the
three letters A, B, or C. The code machine picks a code, and you have
to guess it. Each time you make a guess, it tells you how many of the
letters you picked were the correct letter in the correct place.
My solution was the same as most people’s solution: try AAA then BBB.
This tells you how many A’s, B’s, and C’s are present in the puzzle.
I then proceeded to try every combination of those letters. For
example, if AAA = 1 and BBB = 2, that means there is 1 A and 2 B’s.
I’d try ABB, BAB, and BBA. My only optimization was in the case where
AAA = 1 and BBB = 1, meaning there is 1 of each letter in the puzzle.
In this case, I’d call “BBC” and “ACA” and use the following table to
determine the answer:
BBC matches
|
ACA matches
|
Solution
|
0
|
0
|
CAB
|
0
|
2
|
ACB
|
1
|
1
|
CBA
|
1
|
2
|
BCA
|
2
|
0
|
BAC
|
2
|
1
|
ABC
|
Note that this method was more or less conceived experimentally. I
basically happened upon BBC and ACA for use above, and I’m sure there
are other combinations that would work. With the addition of the
above table, this method ensures that any code can be guessed within 5
guesses. Its average lies around 4 guesses (this determined
experimentally; see below).
Then someone went and beat me. I suspect they used more math and
logic, whereas randomness and experimentation were my friends. They
came up with this “flow chart” reproduced as best I can here:
=> AAA
0 => BBB
0 => CCC
1 => ABC
0 => CCB
1 => BCC
2 => CBC
2 => ABC
0 => BCB
1 => CBB
2 => BBC
1 => ABB
0 => BAC
0 => CCA
1 => BCA
2 => CAC
1 => BAB
0 => ACC, CBA
1 => BBA
2 => CAB
2 => ABC, ACB
2 => ABB
0 => BAA, CAA
1 => AAC, ACA
2 => AAB, ABA
How to read this: start with AAA. Then based on the number of matches
you’d go down to the line that starts with that number and follow the
next guess. Repeat this until puzzle is solved. Lines with two
solutions separated by columns mean you have to try both solutions.
For example, lets say I’m working with the puzzle CBA. I’d first
guess AAA and get 1 matches. I’d go to the 1 under AAA and see “=>
ABB”. So I’d guess ABB and get 1 matches. Then I’d go to the 1 under
ABB and see “=> BAB”. So I’d guess BAB and get 0 matches. Then I see
“=> ACC, CBA”. So first I’d guess ACC which wouldn’t solve it, then
I’d guess CBA which is the solution. Note that this example shows the
longest case, which is five guesses. Using the same methods as above,
I’ve found this method to be closer to 3.5 or 3.6 average turns.
Someone made a nice graphic flow chart for this, but I’m too lazy to
pull out the URL. If you have TSO, just check the forums, in the
“Game Hints” topic or something I believe.
In the process of experimenting with all this, I created
tso.py. This
allowed me to code up solutions and check them easily, debug them, run
them against each other, and make a simple interactive mode. Here’s
an example session with tso.py:
[darkness@darktop-2 tso]$ python2
Python 2.2 (#1, Apr 12 2002, 15:29:57)
[GCC 2.96 20000731 (Red Hat Linux 7.2 2.96-109)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from tso import *
>>> runSolvers (simpleSolver2, tableSolver, randomSolver2)
Ran 1000 tests
Solver # 0: 4.024000 average tries, 5 maximum tries, 100.00% solved
Solver # 1: 3.506000 average tries, 5 maximum tries, 100.00% solved
Solver # 2: 6.231000 average tries, 13 maximum tries, 100.00% solved
>>> debugSolver (simpleSolver2, puzzleInstance = Puzzle ("cba"))
Solving puzzle 'cba'
DEBUG: numA=1 numB=1 numC=1
DEBUG: [simple] Got abc
DEBUG: [simple] matchACA=1 matchBBC=1
Puzzle solved in 5 tries
>>> debugSolver (tableSolver, puzzleClass = InteractivePuzzle)
Solving puzzle ''
Match request: aaa
Number of matches? 1
Match request: abb
Number of matches? 1
Match request: bab
Number of matches? 0
Match request: acc
Number of matches? 0
Match request: cba
Number of matches? 3
Puzzle solved in 5 tries
You’ll note the output of runSolvers in the above output.
simpleSolver2 is the first algorithm I described above, and
tableSolver is the second algorithm. randomSolver2 randomly
tries combinations in a semi-intelligent manner by eliminating
solutions that aren’t possible based on past guesses. (See
randomSolver for a straight and simple random guesser.) Note that
tso.py does require a 2.x Python IIRC, and quite possibly requires
at least 2.2.
By now, it should be clear that I’m insane. I spent a long time,
working on a simple puzzle, without applying some sensible practices
(like LOGIC and MATH), working on the optimal solution for a game
within a game that I haven’t even played yet. Yeah.
In other news, I successfully rebooted a client’s machine remotely
three times in a row including a kernel update. Shocking, I know.
They have a Seagate ATAPI (IDE? What?) tape drive. I originally
thought it was running with IDE SCSI emulation, and thought it was
dying because I couldn’t do mt -f /dev/nst0 fss 1. As it turns
out I was either playing with a non-existent drive or sending mt
commands to the CD-ROM drive. The tape drive is fine and probably
just doesn’t support fss. This all started when the client’s
backup wasn’t running at night. They switched out a tape today and I
rebooted it, so between the two I guess (hope) it fixed the problem.
Now if I can just avoid being woken up tomorrow with any problems that
occurred as a result of the reboot.
Did some coding tonight. Finished DarkWiki::SQLWikiPageContainer
sort of, and most of DarkWiki::SQLWikiPage. Will probably work on
other things for the next couple days.
I’ve been listening to songs from “Donnie Darko” repeatedly today and
yesterday. Actually, I caught the movie again Saturday night and
totally loved it again. Totally loved it. Awesome movie. You must
see this. The next day I ordered the soundtrack (from
http://www.cdbaby.com/) and the DVD (not from Amazon, Buy.com,
or Best Buy… though I have trouble remembering who the enlightened
Internet community is boycotting this week). I’ve collected the songs
from the movie that apparently aren’t on the soundtrack (it’s actually
the original score, IIRC) and hope to graft them onto a CD-R. Watch
the damn CD be copy protected. You can bet I’ll be motivated to do
some DMCA violations then.
Seriously. See this movie.
Oh, I almost forgot since I missed a few entries.
ardent has asked me to be best man (or Best
Man?) in his wedding and I have accepted. Very kind of him, really.
I think. I have a bunch of stuff to do now, I believe, like making a
Bachelor party and some speeches and shit. I should probably Google
for the duties of a best man, since I have no clue. Highest I ever
got within my family was “Junior Usher.” As I talk to people about
this position in the wedding party, no one has heard of it, which
makes me believe they fabricated this position so I didn’t have to be
Ring Bear (or Ring Bearer? or ring bear[er]? Yeesh) again. I was
too old and way too sexy for running down the aisle with that pillow
or whatever, anyway. Too sexy for your church, so sexy it hurrrrrts.
Right Said
Fred
have forever made their mark upon history, I think.