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.

 
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)

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


#!/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

Timed Routine


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

sync

Python Reprocessor


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