# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Saturday, November 28, 2009

### Hamming Numbers (and Perl: Why I just ignored it)

I had read the following post: "Perl: Love it, or hate it, but don’t ignore
it."
, by Phillip Smith, in which the author wishes Perl
solutions were credited as much as solutions in other languages such as
Python and Ruby.

I agreed that Perl wasn't mentioned as much as it was, and a day or so
later I came across an example of why....

I monitor whats happening in Python, and came across a new recipe added
to Activestate code called: "Recipe 576961: Technique for cyclical
iteration"
, by Raymond Hettinger. On first, second, and third
readings, i just couldn't understand the need for the deferred_output
function; the whole recipe remained opaque:

Raymond's
code:

`from itertools import tee, chain, islicefrom heapq import mergedef hamming_numbers():   # Generate "5-smooth" numbers, also called "Hamming numbers"   # or "Regular numbers". See: http://en.wikipedia.org/wiki/Regular_number   # Finds solutions to 2**i * 3**j * 5**k for some integers i, j, and k.   def no_repeats(it):       last = None       for i in it:           if i is not last:                yield i                last = i    def deferred_output():       for i in output:           yield i   result, p2, p3, p5 = tee(deferred_output(), 4)   m2 = (2*x for x in p2) # multiples of 2   m3 = (3*x for x in p3) # multiples of 3   m5 = (5*x for x in p5) # multiples of 5   merged = merge(m2, m3, m5)   combined = chain([1], merged) # prepend a starting point   output = no_repeats(combined) # eliminate duplicates   return resultif __name__ == '__main__':   print(list(islice(hamming_numbers(), 1000))) # Show first 1000 hamming numbers`

I was hooked by the series however and so went looking for more
information.

### Perl

I came across a mention to the following page: "Infinite
lists in Perl"
by Mark Dominus which is copyright 1997 by the
Perl Journal. Normally I wouldn't mention the article, as it spends
more time creating an implementation of generators in Perl as it does
on addressing the computation of Hamming numbers. It also uses the term
"stream" instead of generators. but maybe this is down to the age of
the article, i.e. 1997?

Looking a bit further, I found this Dr Dobbs Article, and this
solution
:

`hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming    where merge (x:xs) (y:ys)           | x < y = x : xs `merge` (y:ys)           | x > y = y : (x:xs) `merge` ys           | otherwise = x : xs `merge` ys`

The Haskell solution lead me to think that maybe Python has an issue
with defining recursive generators, and some experimentation lead me to
believe that yep, maybe that was why Raymond has the deferred_output
function.

### My Python

Since I have trouble understanding Raymond s I went away and wrote my
own solution. It works. It can generate very large values of the
sequence quite quickly. But it does need memory to store
multiples:

`from itertools import islicefrom pprint import pprint as ppdef regularnumbergen(start = 1, multipliers=(2, 3, 5)):   '''\    Generates the Regular Number sequence defined here:        http://en.wikipedia.org/wiki/Regular_number    The sequence starts with 1 and consists of all multiples by 2, 3, or 5    of any number in the sequence in non-repeating, increasing  order.    '''   multiples = [[] for i in multipliers]   this = start   while True:       yield this       # get multiples       for multiple, multiplier in zip(multiples, multipliers):           multiple.append(this * multiplier)       # get next       this = min(m[0] for m in multiples)       # remove this from multiples       for multiple in multiples:           if multiple[0] == this:               del multiple[0]if __name__ == '__main__':   print(list(islice(regularnumbergen(), 10)))`

Generating the following large values of the sequence took only seconds:

`>>> print(list(islice(regularnumbergen(), 99999, 100001)))[290142196707511001929482240000000000000, 290237644800000000000000000000000000000]>>> `

### Wrapup

Well, I've learnt a bit more about generators, the limitatins in their
Python implementation w.r.t. Haskel, and I've put more meat on why I
tend to not quote much Perl In this case, i couldn't see the wood for
the trees! (But I do quote Perl).

## Thursday, November 12, 2009

Verilog is to SytemVerilog as C is to C++ .
Verilog is to __________ as C is to Go ?

My main criticism of SytemVerilog was the size of the language compared to Verilog. Maybe we'll get SystemGo in five years time. (Or maybe Go itself will warp into some monstrosity; my crystal ball needs a new backlight).

## Wednesday, November 04, 2009

### More Words From Hex Letters (with extra zero's)

STOP PRESS! Someone commented that zeros could be used as ones so an update is at the bottom.

It was pointed out to me that I needn't restrict myself to four character words, and could use the number '1' as letter 'l', and the number '5' as the letter 'S'.

So here is the program and output of words of four or more characters that can be made from hexadecimal characters.
`import urllibwords = urllib.urlopen('http://www.puzzlers.org/pub/wordlists/unixdict.txt'                  ).read().split()#len(words) == 25104def findwords(hexchars):hexchars = set(hexchars)hexwords = [w for w in words if 4 <= len(w) and all(ch in hexchars for ch in w)]return hexwordsdef printwords(hexwords):for i in range(0, len(hexwords), 5):   print ('  ' + ' '.join("%-8s" % w for w in hexwords[i:i+5]))hexchars = 'abcdef'#hexwords = findwords(hexchars)#print "\nHEXWORDS"#printwords(hexwords)# Now to use one: 1 as ell: l; and five: 5 as ess: shexwords = findwords(hexchars + 'ls')hexwords = [word.replace('s','5').replace('l','1') for word in hexwords]print "\nHEXWORDS USING one: 1 AS ell: l; AND five: 5 AS ess: s"printwords(hexwords)`

The list of words found have some gems, such as babble, for when you know your generating data that no one will read; baffle, baseball, blab, bleed, bless, (and blessed if it were in the dictionary), cabal, cascade, cease, debacle, decade, decease, (and should have deceased), false, flee, label, ...

(Someone at work suggested we use 1abe1 or label to prefix a section of writes to a peripheral in an assembler prog which got me going).

The words:

`HEXWORDS USING one: 1 AS ell: l; AND five: 5 AS ess: saaa5     ababa    aba5e    abba5    abbeabed     abe1     ab1e     ab5ce55  accedeacce55   added    add1e    ade1e    affab1ea1ba     a1ec     a1fa1fa  a11e1e   a55e55babb1e   babe     babe1    bade     baff1eba1d     ba1e     ba11     ba11ad   ba11edba15a    ba5a1    ba5e     ba5eba11 ba5e1ba55     bead     bead1e   beebe    beefbefa11   befe11   be1a     be11     be11abe11e    be55     be55e1   b1ab     b1adeb1ed     b1eed    b1e55    caba1    cab1ecafe     ca1eb    ca1f     ca11     ca11aca5cade  ca5e     cea5e    cede     ce1ebe5ce11     c1ad     c1a55    dabb1e   daccadada     dade     da1e     da11a5   deaddeaf     dea1     debac1e  deba5e   decadedeca1    decca    decea5e  deed     defacede11     de11a    ea5e     ea5e1    ecc1e5efface   effaceab1e e1ba     e11a     e15efab1e    facade   face     fade     fa11fa15e    feeb1e   feed     fee1     fe11f1ea     f1ed     f1ee     f1eece   1abe11ace     1ad1e    1a5e     1a55     1ead1eaf     1ea5e    1eed5    1e55     1e55ee5ab1e    5accade  5add1e   5afe     5a1ad5a1e     5a11e    5cab     5ca1a    5ca1d5ca1e    5ea1     5ecede   5eeab1e  5eed5eedbed  5e1f     5e11     51ab     51ed`

Without Michaels comment I would have skipped all words that use zero for an o, so I made the following two changes:

`hexwords = findwords(hexchars + 'lso')hexwords = [word.replace('s','5').replace('l','1').replace('o', '0') for word in hexwords]`

And created the following extra words:

`  ab0de    acc01ade ad0be    a1c0a    a110cab1ea10e     a100f    a150     ba1b0a   ba550 b10b     b10c     b100d    b0bb1e   b0ca  b0de     b01d     b01dface b01e     b010  b05e     b055     caca0    c10d     c105e c0a1     c0a1e5ce c0bb     c0bb1e   c0b01 c0ca     c0c0     c0c0a    c0da     c0dd1ec0de     c0ed     c0ffee   c01a     c01d  c01e     c01055a1 c001     c05ec    dec0ded0bb5    d0dd     d0d0     d0ff     d01ce d01e     d011     d00d1e   d05e     ec01e ee0c     fa110ff  f10c     f10e     f100d f0a1     f0ca1    f01d     f00d     f001  f055     1a05     1a550    10ad     10af  10be     10b0     10ca1    10ca1e   10eb  10e55    101a     1011     1005e    1005e1eaf105ab1e  105e     1055     0a5e5    0be5e 0b0e     0b5e55   0de55a   0ffa1    0ff10ad0ff5add1e 01af     00d1e5   0510     5caff01d5c0ff    5c01d    5eaf00d  510b     510e  50da     50fa     501ace   501d     501e  5010 `

## Sunday, November 01, 2009

### The 24 game

I've just created a new task over on Rosetta Code for the 24 game, and a separate task to create a solver for the game.

It's a brute -force solver, but I find the game to be playable, so will get my sprogs to test their arithmetic skills with it later.

I've just realised that the solver could be easily modified to solve "The numbers game" from the UK Channel 4 program Countdown. (Although their could be an issue with division as, when given the digits 3 3 7 7, the solver finds the solution: ( 3 + 3 / 7 ) * 7 which may not be allowed by the countdown rules which state that "only whole numbers may be used").