programming puzzles?

[John Salerno]

Similar to the Python Challenge, does anyone know of any other websites
or books that have programming puzzles to solve? I found a book called
"Puzzles for Hackers", but it seems like it might be a little advanced
for me, and I've also read that it focuses too much on encryption and
security issues and doesn't really have coding problems, exactly. But
something like that book would be fun to have.

 

[mensanator]

Similar to the Python Challenge, does anyone know of any other websites
or books that have programming puzzles to solve? I found a book called
"Puzzles for Hackers", but it seems like it might be a little advanced
for me, and I've also read that it focuses too much on encryption and
security issues and doesn't really have coding problems, exactly. But
something like that book would be fun to have.

Personally, I am an avid reader of rec.puzzles. Not because
I like doing stupid puzzles per se, but I look at them from the
viewpoint "how would I write a program to solve this?"
Even simple word problems sometimes involves more trouble than
the puzzle is worth, but it teaches you how to write algorithms to
generate permutations, combinations, partitions, etc. that can be
handy for other applications. And it's one thing to generate letter
patterns, determining if they are English words is something else,
which can teach you about database and such.

Many puzzle purists bristle at this attitude, but I do this for
myself, not for them.

 

[John Salerno]

Personally, I am an avid reader of rec.puzzles. Not because
I like doing stupid puzzles per se, but I look at them from the
viewpoint "how would I write a program to solve this?"
Even simple word problems sometimes involves more trouble than
the puzzle is worth, but it teaches you how to write algorithms to
generate permutations, combinations, partitions, etc.

Sounds like what I'm interested in. I'll check it out!

 

[Michael Tobis]

The first piece of code that I ever voluntarily wrote was intended to
solve this puzzle:

Assign the number 2 to 'a', 3 to 'b' ... 27 to 'z'. To each word assign
the value of the product of its characters. Find the English (or
language of your choice) word whose product is closest to a million (or
number of your choice).

I didn't have a lexicon handy. So I just printed out the letter
combinations closest to a million and manually played Jumble with them.
This was on a PDP-11 using Fortran, so you should have no problem doing
this in Python.

The prize was a VCR, which was a big deal in those days, but I didn't
have a Green Card yet, so I didn't submit my answer, for (probably
unfounded) fear the immigration authorities would give me a hard time
for unauthorized income. My answer returned
<hack hack type> 999856 for its product. Can you do better?

You can go further. If you have a unix-like system you already have a
lexicon, probably at /usr/share/dict/words .

Compare various ways to solve this problem for performance, for
arbitrary ciphers, which you can pass in as a dictionary like
{'a':2,'b':4,'c':5 .... etc.

To get you started here's the calculation, which may be interesting in
itself. I don't have the Fortran, but I'm sure it was MUCH longer than
this!

#####
cipher0= {}

for i in range(ord('a'),ord('z')+1):
cipher0[chr(i)] = i - ord('a') + 2

from operator import mul

def numify(word,cipher=cipher0):
return reduce(mul,[cipher[c] for c in word])

if __name__ == "__main__":
print numify("hello")

# prints 146016

####

mt

 

[mensanator]

The first piece of code that I ever voluntarily wrote was intended to
solve this puzzle:

Assign the number 2 to 'a', 3 to 'b' ... 27 to 'z'. To each word assign
the value of the product of its characters. Find the English (or
language of your choice) word whose product is closest to a million (or
number of your choice).

I didn't have a lexicon handy. So I just printed out the letter
combinations closest to a million and manually played Jumble with them.
This was on a PDP-11 using Fortran, so you should have no problem doing
this in Python.

The prize was a VCR, which was a big deal in those days, but I didn't
have a Green Card yet, so I didn't submit my answer, for (probably
unfounded) fear the immigration authorities would give me a hard time
for unauthorized income. My answer returned
<hack hack type> 999856 for its product. Can you do better?

dioxid = 1000000
ixodid = 1000000

You can go further. If you have a unix-like system you already have a
lexicon, probably at /usr/share/dict/words .

Also check out www.puzzlers.org. There, and other places, you
can find word lists, such as the one I used above to find words
that numify to exactly 1000000.

Compare various ways to solve this problem for performance, for
arbitrary ciphers, which you can pass in as a dictionary like
{'a':2,'b':4,'c':5 .... etc.

To get you started here's the calculation, which may be interesting in
itself. I don't have the Fortran, but I'm sure it was MUCH longer than
this!

#####
cipher0= {}

for i in range(ord('a'),ord('z')+1):
cipher0[chr(i)] = i - ord('a') + 2

from operator import mul

def numify(word,cipher=cipher0):
return reduce(mul,[cipher[c] for c in word])

if __name__ == "__main__":
print numify("hello")

# prints 146016

####

mt

 

[Michael Tobis]

Yeah, this was *much* easier than I expected.

My candidate was in second place according to /usr/share/dict/words
which has ixodid but not dioxid; I'm really not confident that dioxid
is a word.

I recall that I had also found the third place word now that I look at
it.

What I had to do was print out all combinations of letters that could
make between 999,000 and 1,001,000 and then eyeball them. The
factorization was a trick because I had only 16 bit ints if I recall
right; I think hacked it in floats.

I am amazed at how fast the Python ran and how easy it was to solve.

I found "ixodid" in two reasonable lines of Python or one over-long
ugly one, (in addition to what I already posted). It runs in about 15
seconds on a G4 powerbook. All in memory!

I once spent three whole days on this. Hundreds of lines of Fortran,
pages and pages of fanfold paper. Argh.

mt

 

[Michael Tobis]

Yeah, this was *much* easier than I expected.

My candidate was in second place according to /usr/share/dict/words
which has ixodid but not dioxid; I'm really not confident that dioxid
is a word.

I recall that I had also found the third place word now that I look at
it.

What I had to do was print out all combinations of letters that could
make between 999,000 and 1,001,000 and then eyeball them. The
factorization was a trick because I had only 16 bit ints if I recall
right; I think hacked it in floats.

I am amazed at how fast the Python ran and how easy it was to solve.

I found "ixodid" in two reasonable lines of Python or one over-long
ugly one, (in addition to what I already posted). It runs in about 15
seconds on a G4 powerbook. All in memory!

I once spent three whole days on this. Hundreds of lines of Fortran,
pages and pages of fanfold paper. Argh.

mt

 

[Paul Rubin]

The first piece of code that I ever voluntarily wrote was intended to
solve this puzzle:

Assign the number 2 to 'a', 3 to 'b' ... 27 to 'z'. To each word assign
the value of the product of its characters. Find the English (or
language of your choice) word whose product is closest to a million (or
number of your choice).

Hey, that was a contest in Games Magazine in the 1980's. A co-worker
and I used a PDP-10 BASIC program to search for numbers near 1 million
with no prime factors higher than 27. The factorizations of those
numbers told us which letters to try to use, and after a while of
fooling around rearranging letters on a whiteboard, we came up with
"curvy", a very recognizable word that multiplies out to 999,856.

That's the closest number to 1 million (other than 1 million itself)
which doesn't have any prime factors that are too large. We convinced
ourselves that there was no word that multiplied to exactly 1 million,
so we felt we were likely to win the contest. However, somebody
apparently with a computerized word list won with "ixodid". It was
fun to remember this.

 

[mensanator]

Hey, that was a contest in Games Magazine in the 1980's. A co-worker
and I used a PDP-10 BASIC program to search for numbers near 1 million
with no prime factors higher than 27. The factorizations of those
numbers told us which letters to try to use, and after a while of
fooling around rearranging letters on a whiteboard, we came up with
"curvy", a very recognizable word that multiplies out to 999,856.

That's the closest number to 1 million (other than 1 million itself)
which doesn't have any prime factors that are too large. We convinced
ourselves that there was no word that multiplied to exactly 1 million,
so we felt we were likely to win the contest. However, somebody
apparently with a computerized word list won with "ixodid". It was
fun to remember this.

The trouble with word lists is when you run across something
you don't recognize, like "ixodid", you can't tell if it's a word or
an acronym or an abbreviation. Being in the environmental
remediation business, I thought "dioxid" (which I assume is
related to "dioxin") to be more plausible as a word.

And it would seem that Games no longer has contests that
simply find words, they add a twist to prevent those like me
from having an advantage. See

<http://members.aol.com/mensanator/pig_ignorance.htm>

I still used my word list database to find valid words to use
in my contest entries, but entries are judged, not simply scored.

 

[Paul Rubin]

The trouble with word lists is when you run across something
you don't recognize, like "ixodid", you can't tell if it's a word or
an acronym or an abbreviation.

Well, once they told us the winner was "ixodid", we found that word
quickly in a dictionary. But we'd certainly never heard it before.

 

[Fredrik Lundh]

The trouble with word lists is when you run across something
you don't recognize, like "ixodid", you can't tell if it's a word or
an acronym or an abbreviation. Being in the environmental
remediation business, I thought "dioxid" (which I assume is
related to "dioxin") to be more plausible as a word.

isn't that spelled "dioxide" in english ?

googling for "dioxid" brings up band homepages, obviously misspelled
pages, and non-english pages (it's spelled dioxid in swedish, for example)
-- and this page:

http://www.morewords.com/word/dioxid/

which says that dioxid is a valid word, and tells me to click on a number
of dictionary links to verify that. those links all lead to "not found; per-
haps you meant dioxide?" pages...

</F>

 

[mensanator]

isn't that spelled "dioxide" in english ?

googling for "dioxid" brings up band homepages, obviously misspelled
pages, and non-english pages (it's spelled dioxid in swedish, for example)
-- and this page:

http://www.morewords.com/word/dioxid/

which says that dioxid is a valid word, and tells me to click on a number
of dictionary links to verify that. those links all lead to "not found; per-
haps you meant dioxide?" pages...

www.chemfinder.com is probably better place to look for chemistry
spellings than dictionaries and they don't list it either. But don't
ask
me how it made it's way onto the consolidated word list from
www.puzzlers.org.