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. Advertising

  2. John Salerno

    Guest

    John Salerno wrote:
    > 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.
     
    , Apr 8, 2006
    #2
    1. Advertising

  3. John Salerno

    John Salerno Guest

    wrote:

    > 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!
     
    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

    Guest

    Michael Tobis wrote:
    > 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
     
    , 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

    "Michael Tobis" <> writes:
    > 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.
     
    Paul Rubin, Apr 9, 2006
    #8
  9. John Salerno

    Guest

    Paul Rubin wrote:
    > "Michael Tobis" <> writes:
    > > 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.


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

    Paul Rubin Guest

    "" <> writes:
    > 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.
     
    Paul Rubin, Apr 9, 2006
    #10
  11. wrote:

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

    Guest

    Fredrik Lundh wrote:
    > wrote:
    >
    > > 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...


    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.

    >
    > </F>
     
    , Apr 9, 2006
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. hezhang
    Replies:
    5
    Views:
    680
    hezhang
    Feb 16, 2006
  2. Roedy Green

    More anti-aliasing puzzles

    Roedy Green, Aug 10, 2005, in forum: Java
    Replies:
    25
    Views:
    2,212
    Roedy Green
    Aug 16, 2005
  3. xPy

    puzzles...puzzles...

    xPy, Feb 14, 2006, in forum: C++
    Replies:
    2
    Views:
    404
    Neil Cerutti
    Feb 14, 2006
  4. deepak

    Link for C puzzles and programming

    deepak, Oct 28, 2009, in forum: C Programming
    Replies:
    2
    Views:
    535
    deepak
    Oct 29, 2009
  5. Surya
    Replies:
    10
    Views:
    229
    Tim Rentsch
    Dec 20, 2013
Loading...

Share This Page