Chutes and Ladders Infinite Loop

I play Chutes and Ladders with my kids sometimes. It isn’t a game of skill. Many months ago I was involved in a game that went on and on and on. As soon as someone would get close to the end he or she would land on a chute and be shunted nearly back to start.

I was left wondering just how long a game would last. So this week my son and I implemented a simulator in Python to calculate how long any one person’s game would last. Each person’s play is independent in Chutes and Ladders, the characters do not interact. Therefore, simulating an entire game is almost as easy as simulating a single player’s experience.

First, the board is 100 cells long and the spinner gives you a value between 1 and 6, just like rolling a die. A fair die will have an average roll of 3.5, so on average it would take about 100/3.5 = 28.6 turns to finish a game if there were no chutes or ladders. The histogram of game length without chutes and ladders is below. The longest plausible game is about 35 turns in this scenario and the average is 28.6 turns, estimated from 10,000 random trials.

chuteshist_nochutes

The addition of chutes and ladders stretches the histogram radically. Instead of the longest single-person game being about 35 turns, it is now over 200 turns. Fortunately, a 200-turn game is not very likely. Surprisingly the average is not a hundred million years. At 30.8 turns the average game with chutes and ladders is only a little longer than the average game without.

chuteshist

Pretty cool.

[sourcecode language=”python” wraplines=”false” collapse=”false”]
import random
import pylab as plt
import numpy as np
d = {}
for i in range(1, 101):
d[i] = i

cl = {1: 38,
4: 14,
9: 31,
16: 6,
21: 42,
28: 84,
36: 44,
48: 26,
49: 11,
51: 67,
56: 53,
62: 19,
64: 60,
71: 91,
80: 100,
87: 24,
93: 73,
95: 75,
98: 78}
d.update(cl)
numturnsa = []
for t in range(10000):
numturns = 0
pos = 0

while True:
numturns += 1
pos += random.randint(1,7)
if pos > 100:
break
# To "play" without chutes and ladders, comment out the next line.
pos = d[pos]
numturnsa.append(numturns)

plt.figure(figsize=(5,3))
plt.subplots_adjust( .13, .15, .95, .97)
plt.hist(numturnsa, 60)
plt.xlabel("Number of turns")
plt.ylabel("Count")
plt.savefig("chuteshist_nochutes.png", dpi=200)
numturnsa = np.array(numturnsa, dtype="f")
print "The average number of turns is",np.mean(numturnsa)
[/sourcecode]

Revised Raspberry Pi TrueCrypt Benchmark

Revised March 31, 2013 with updated benchmarking approach that uses actual access to the mounted volume. New results show no appreciable sensitivity to hash, which is as expected. The numbers are for encryption only (write). I have not pursued read.

Hash
Algorithm
Encryption
Algorithm
Rate
(MB/s)
SHA-512 Twofish 2.8
Whirlpool Twofish 2.8
RIPEMD-160 Twofish 2.8
SHA-512 Serpent 2.6
Whirlpool Serpent 2.6
RIPEMD-160 Serpent 2.6
Whirlpool AES 2.1
RIPEMD-160 AES 2.1
SHA-512 AES 2.1
SHA-512 Twofish-Serpent 2.0
Whirlpool Twofish-Serpent 2.0
RIPEMD-160 Twofish-Serpent 1.9
SHA-512 AES-Twofish 1.6
RIPEMD-160 AES-Twofish 1.6
Whirlpool AES-Twofish 1.6
Whirlpool Serpent-AES 1.6
SHA-512 Serpent-AES 1.6
RIPEMD-160 Serpent-AES 1.6
Whirlpool AES-Twofish-Serpent 1.3
Whirlpool Serpent-Twofish-AES 1.3
SHA-512 Serpent-Twofish-AES 1.3
SHA-512 AES-Twofish-Serpent 1.3
RIPEMD-160 Serpent-Twofish-AES 1.3
RIPEMD-160 AES-Twofish-Serpent 1.3

Shell Script for Timing

[code language=”bash”]

#!/bin/bash

# Create a file of random elements, needs to be at least 300 bytes
dd if=/dev/random of=random bs=512 count=1

# Iterate over the hash hash funnctions
for HASH in RIPEMD-160 SHA-512 Whirlpool
do
# Iterate over the available encryption algorithms
for ENCALG in AES Serpent Twofish AES-Twofish AES-Twofish-Serpent Serpent-AES Serpent-Twofish-AES Twofish-Serpent
do
# Write the algorithms to the log
echo "Algorithms: $HASH $ENCALG" >> log
# TrueCrypt will report the performance in the output
truecrypt -c /home/pi/test.tc –filesystem=fat –size=10485760
–encryption=$ENCALG -p ppp –random-source=random
–hash=$HASH –volume-type=normal –non-interactive
# Mount the partition
truecrypt –non-interactive -p ppp -m nokernelcrypto test.tc /home/pi/tcvol
(time  ./timeit) 2>> log
truecrypt -d /home/pi/tcvol
# Erase the created file
rm test.tc
done
done

[/code]

Timed Routine

[code language=”bash”]

dd if=/dev/zero of=tcvol/test bs=5242880 count=1 &> /dev/null

sync

[/code]

Python Reprocessor

[code language=”python”]

import sys
fid = open( sys.argv[1], ‘r’)
lines = fid.readlines()
fid.close()

tsecs = None
while len( lines) > 0:
line = lines.pop(0)
lls = line.strip()

if lls.startswith( ‘Algo’):
# If we already have a tsecs, then print
# the last elements
toks = lls.split()
if tsecs == None: # first record
algo = ",".join( toks[1:3])
else:
print algo,",",tsecs
algo = ",".join( toks[1:3])
elif lls.startswith( ‘real’):
toks = lls.split()
toks = toks[-1].split(‘m’)
tsecs = float( toks[0])*60 + float( toks[1].replace(‘s’, ”))

print algo,",",tsecs

[/code]