programming puzzles?

Discussion in 'Python' started by John Salerno, Apr 8, 2006.

  1. John Salerno

    John Salerno Guest

    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.
     
    John Salerno, Apr 8, 2006
    #1
    1. Advertisements

  2. John Salerno

    mensanator Guest

    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.
     
    mensanator, Apr 8, 2006
    #2
    1. Advertisements

  3. John Salerno

    John Salerno Guest

    Sounds like what I'm interested in. I'll check it out!
     
    John Salerno, Apr 9, 2006
    #3
  4. 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
     
    Michael Tobis, Apr 9, 2006
    #4
  5. John Salerno

    mensanator Guest

    dioxid = 1000000
    ixodid = 1000000
    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.
     
    mensanator, Apr 9, 2006
    #5
  6. 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, Apr 9, 2006
    #6
  7. 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, Apr 9, 2006
    #7
  8. John Salerno

    Paul Rubin Guest

    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.
     
    Paul Rubin, Apr 9, 2006
    #8
  9. John Salerno

    mensanator Guest

    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.
     
    mensanator, Apr 9, 2006
    #9
  10. John Salerno

    Paul Rubin Guest

    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.
     
    Paul Rubin, Apr 9, 2006
    #10
  11. 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>
     
    Fredrik Lundh, Apr 9, 2006
    #11
  12. John Salerno

    mensanator Guest

    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.
     
    mensanator, Apr 9, 2006
    #12
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.