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, islice
from heapq import merge

def 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 result

if __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?



Haskell


Looking a bit further, I found this Dr Dobbs Article, and this
commented Haskell
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 islice
from pprint import pprint as pp


def 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

Curious about Go.

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 urllib

words = urllib.urlopen('http://www.puzzlers.org/pub/wordlists/unixdict.txt'
).read().split()
#len(words) == 25104

def 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 hexwords

def 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: s
hexwords = 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: s
aaa5 ababa aba5e abba5 abbe
abed abe1 ab1e ab5ce55 accede
acce55 added add1e ade1e affab1e
a1ba a1ec a1fa1fa a11e1e a55e55
babb1e babe babe1 bade baff1e
ba1d ba1e ba11 ba11ad ba11ed
ba15a ba5a1 ba5e ba5eba11 ba5e1
ba55 bead bead1e beebe beef
befa11 befe11 be1a be11 be11a
be11e be55 be55e1 b1ab b1ade
b1ed b1eed b1e55 caba1 cab1e
cafe ca1eb ca1f ca11 ca11a
ca5cade ca5e cea5e cede ce1ebe5
ce11 c1ad c1a55 dabb1e dacca
dada dade da1e da11a5 dead
deaf dea1 debac1e deba5e decade
deca1 decca decea5e deed deface
de11 de11a ea5e ea5e1 ecc1e5
efface effaceab1e e1ba e11a e15e
fab1e facade face fade fa11
fa15e feeb1e feed fee1 fe11
f1ea f1ed f1ee f1eece 1abe1
1ace 1ad1e 1a5e 1a55 1ead
1eaf 1ea5e 1eed5 1e55 1e55ee
5ab1e 5accade 5add1e 5afe 5a1ad
5a1e 5a11e 5cab 5ca1a 5ca1d
5ca1e 5ea1 5ecede 5eeab1e 5eed
5eedbed 5e1f 5e11 51ab 51ed


Additional Words with an 'o'

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    a110cab1e
a10e 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 c0dd1e
c0de c0ed c0ffee c01a c01d
c01e c01055a1 c001 c05ec dec0de
d0bb5 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 1005e1eaf
105ab1e 105e 1055 0a5e5 0be5e
0b0e 0b5e55 0de55a 0ffa1 0ff10ad
0ff5add1e 01af 00d1e5 0510 5caff01d
5c0ff 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").