Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

Sunday, August 10, 2008

Monty Hall Problem Simulations

I
topic on Rosetta Code on the Monty Hall problem, using an
example I had laying around that I had written in Python to simulate
the effects of different player strategies. The game goes like this:
• The
contestant in in front of three  doors that he cannot see
behind..
• The three doors conceal one
prize and the rest being booby prizes, arranged randomly.
• The
Host asks the contestant to choose a door.
• The host
then goes behind the doors where only he can see what is concealed,
then always
opens one
door, out of the other s not chosen  by the contestant, that
must reveal a booby prize to the contestant.
• The
host then asks the contestant if he would like either to stick with his
previous choice, or switch and choose the other remaining closed door.
It
turns out that if the contestant follows a strategy of always switching
when asked, then he will maximise his chances of winning..

I
then re-wrote the simulator in AWK  (gawk), so there are now
at least two implementations of the simulator on Rosetta Code.,

The
simulator results show that:
• A strategy of
never switching wins 1/3rd of the time.
• A strategy
of randomly switching wins 1/2 of the time.
• A
strategy of always switching wins 2/3rds of the time.
style="margin-left: 40px;">

Tuesday, August 05, 2008

Spiral

This
exercise I thought up myself after doing href="http://paddy3118.blogspot.com/2008/08/zig-zag.html">ZigZag.
"
Produce a spiral array.. A spiral array is a square arrangement of the
first N2 integers, where the numbers increase
sequentially as you go around  the edges of the array
spiralling inwards.

For example, given 5, produce
this array:
style="font-family: monospace;"> 0
1  2  3  4 style="font-family: monospace;"> style="font-family: monospace;">15 16 17 18  5 style="font-family: monospace;"> style="font-family: monospace;">14 23 24 19  6 style="font-family: monospace;"> style="font-family: monospace;">13 22 21 20  7 style="font-family: monospace;"> style="font-family: monospace;">12 11 10
9  8

TheAlgorithm

Again I choose to define the x axis as the column
numbers increasing linearly left to right; and the y axis being the row
numbers increasing linearly top to bottom; and with the top left corner
being (0,0).
If you think of the outer part of the spiral, it
can be defined as how x and y change, i.e. deltas. First along the top
row dx,dy =
(1,0)
meaning that for successive places x changes by 1
and y does not.
Similarly
for the next straight run , down the RHS: style="font-family: monospace;"> dx,dy = (0,1).
Along
the bottom: dx,dy =
(-1,0)
.
And back to the top along the LHS: style="font-family: monospace;">dx,dy = (0,-1).
The
next time around the loop, dx,dy take on those same values.

When
to stop going in a straight line and change direction?
style="margin-left: 40px;">
• When you
would go off the edge of the array
to 'step' on a position that is already filled.
When
to stop?
• When
you have placed the last integer.

The Program

I have two ways of generating successive dx,dy
values; a formula in lines 19 and 34, and a commented out use of
itertools.cycle in lines 14,17,18 and 33 which could be used instead.
They generate the same sequence.
When to change direction is
done by initializing myarray with None values in line 22 and the
conditional statement at line 29
When to stop is handled by
the outer while loop at line 24.

line 15 that allows you to trace the calculation

` 1 ''' color="#804040"> 2 Author: Donald 'Paddy' McCarthy color="#804040"> 3 Email: paddy3118@gmail.com color="#804040"> 4 File: spiral.py color="#804040"> 5  color="#804040"> 6 Routine creates a square array filled with numbers that increase color="#804040"> 7 in a spiral pattern into the center. color="#804040"> 8  color="#804040"> 9 Note: for spiralling out just swap array[x,y] for n**2-1-array[x,y] color="#804040">10 Note: Vim colourizing plus  color="#804040">11        :%s/\(&nbsp;&nbsp;\)\?  / color="#6a5acd">\1\&nbsp;\&nbsp;/g color="#804040">12 ''' color="#804040">13  color="#804040">14 #from itertools import cycle color="#804040">15 explain = True color="#804040">16 def  color="#008080">spiral(n): color="#804040">17      color="#0000ff">#deltas = cycle( ((1,0),(0,1),(-1,0),(0,-1)) ) color="#804040">18      color="#0000ff">#dx,dy = deltas.next() # Starting increments color="#804040">19     dx,dy = 1,0             color="#0000ff"># Starting increments color="#804040">20     x,y = 0,0               color="#0000ff"># Starting location color="#804040">21     i = 0                   color="#0000ff"># starting value color="#804040">22     myarray = [[None]* n  color="#804040">for j  color="#804040">in range(n)] color="#804040">23      color="#804040">if explain:  color="#804040">print " color="#ff00ff">dx,dy ->", dx,dy color="#804040">24      color="#804040">while i < n**2: color="#804040">25         myarray[x][y] = i color="#804040">26          color="#804040">if explain:  color="#804040">print " color="#ff00ff">x,y->[x,y]", x,y, myarray[x][y] color="#804040">27         i += 1 color="#804040">28         nx,ny = x+dx, y+dy color="#804040">29          color="#804040">if 0<=nx<n  color="#804040">and 0<=ny<n  color="#804040">and myarray[nx][ny] == None: color="#804040">30             x,y = nx,ny color="#804040">31              color="#804040">continue color="#804040">32          color="#804040">else: color="#804040">33              color="#0000ff">#dx,dy = deltas.next() color="#804040">34             dx,dy = (-dy,dx)  color="#804040">if dy  color="#804040">else (dy,dx) color="#804040">35              color="#804040">if explain:  color="#804040">print " color="#ff00ff">dx,dy ->", dx,dy color="#804040">36             x,y = x+dx, y+dy color="#804040">37      color="#804040">return myarray color="#804040">38 def  color="#008080">printspiral(myarray): color="#804040">39     n = range(len(myarray)) color="#804040">40      color="#804040">for y  color="#804040">in n: color="#804040">41          color="#804040">for x  color="#804040">in n: color="#804040">42              color="#804040">print " color="#ff00ff">%2i" % myarray[x][y], color="#804040">43          color="#804040">print color="#804040">44  color="#804040">45 printspiral(spiral(6))`

Sampleoutput:

style="font-family: monospace;">>>>
printspiral(spiral(4)) style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 0 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 0 2 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 0 3 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 1 4 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 2 5 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 3 3 6 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> -1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 3 7 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 3 8 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 3 9 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 -1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 2 10 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 0 1 11 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 1 12 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 1 13 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 1 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 2 2 14 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> -1 0 style="font-family: monospace;"> style="font-family: monospace;">x,y->[x,y] 1 2 15 style="font-family: monospace;"> style="font-family: monospace;">dx,dy -> 0 -1 style="font-family: monospace;"> style="font-family: monospace;"> 0
1  2  3 style="font-family: monospace;"> style="font-family: monospace;">11 12 13  4 style="font-family: monospace;"> style="font-family: monospace;">10 15 14  5 style="font-family: monospace;"> style="font-family: monospace;"> 9
8  7  6 style="font-family: monospace;"> style="font-family: monospace;">>>>

Monday, August 04, 2008

Zig Zag

Yet another problem from Rosetta Code.
The problem statement is:
"
Produce a zig-zag array. A zig-zag array is a square arrangement of the first N2 integers, where the numbers increase sequentially as you zig-zag along the anti-diagonals of the array. For example:
0  1  5  6
2  4  7 12
3  8 11 13
9 10 14 15
Or take a look at this.
"
I read all the other answers and saw a very short  example in the J language, which looked like line noise to me, as well as a fairly short example in Haskel a programming language I don't know, but I got a hint as to how it is done by the mention of sorting indeces.

I printed a sheet of graph paper, drew a 6 by 6  grid and put in the zig-zag numbers, after a few false starts I realised that what distinguishes a diagonal is if the top left is coordinate 0,0; x increases to the right, and y increases  going down the rows, then the sum of the induces is constant for a diagonal.

If we are going to do some sorting then we need to sort first on the sum of the indeces.

Next, you find that when the sum is odd you are 'going' down the diagonal so increasing y gives the sort order and vice versa, so secondly sort on  -y if the sum of the coordinates is even, otherwise +y.

The sort will give the order of the coordinates enumerate the order and you get what integer goes in which location et voila!.

The code:

The sort is split between the iterable which simply generates the coordinate pairs and the key function  which returns a tuple of the tho elements highlighted above for sorting the coordinates (Its equivalent to the decorate-sort-undecorate or Schwartzian sort method for any non-Pythoneers).  It is the main part of the program:

```'''
zigzag algorithm
Description from: http://www.rosettacode.org/wiki/Zig_Zag
'''
def zigzag(n):
indexorder = sorted(((x,y) for x in range(n) for y in range(n)),
key = lambda p: (p[0]+p[1], -p[1] if (p[0]+p[1]) % 2 else p[1]) )
return dict((index,n) for n,index in enumerate(indexorder))
def printzz(myarray):
n = int(len(myarray)** 0.5 +0.5)
for x in range(n):
for y in range(n):
print "%2i" % myarray[(x,y)],
print
printzz(zigzag(6)) ```
Running the code produces:
0  1  5  6 14 15
2  4  7 13 16 25
3  8 12 17 24 26
9 11 18 23 27 32
10 19 22 28 31 33
20 21 29 30 34 35

Now to add it to Rosetta Code.

Sunday, August 03, 2008

SEDOL

Whilst browsing Rosetta Code, I came across a good algorithm for training students, SEDOL, so coded up a version in what I would call a very litteral translation of  itsexplanation.
I changed the Python example on Wikipedia, as it did not have a validation function as other examples have, and added my code to the Rosetta page.
```'''
From: http://en.wikipedia.org/wiki/SEDOL
SEDOLs are seven characters in length, consisting of two parts:
a six-place alphanumeric code and a trailing check digit.
'''
import string
# constants
sedolchars = string.digits + string.ascii_uppercase
sedol2value = dict((ch, n) for n,ch in enumerate(sedolchars))
for ch in 'AEIOU':
del sedol2value[ch]
sedolchars = sorted(sedol2value.keys())
sedolweight = [1,3,1,7,3,9,1]
def check(sedol):
return len(sedol) == 7 and \
&nbspall(ch in sedolchars for ch in sedol) and \
&nbspsum(sedol2value[ch] * sedolweight[n]
for n,ch in enumerate(sedol)
) % 10 == 0
def checksum(sedol):
&nbsptmp = sum(sedol2value[ch] * sedolweight[n]
for n,ch in enumerate(sedol[:6])
)
return sedolchars[ (10 - (tmp % 10)) % 10]

sedol = '0263494'
print sedol, checksum(sedol)
print
# From: http://www.rosettacode.org/wiki/SEDOL
for sedol in '''
710889
B0YBKJ
406566
B0YBLH
228276
B0YBKL
557910
B0YBKR
585284
B0YBKT
'''.split():
print sedol + checksum(sedol)```
Note:
I came back to the code after a few hours of sleep and thought initially that I would have trouble in the return statement of  checksum() as I thought I would need a dictionary doing the full reverse matching of what sedol2value, from ints to characters. sedolchars nolonger includes the vowels so using that method for a value over 9 will not work.
Luckily, the result of the calculation is always in the range 0<= n >=9, and within that range, sedolchars[n] works.