Programming Praxis – Feynman’s Puzzle

Today’s Programming Praxis problem is about a long division puzzle by Richard Feynman. The provided solution is 14 lines of code. Since both his and my solution are little more than a simple list comprehension, there is not going to be much room for improvement, but let’s see what we can do.

We need a way to refer to specific digits of numbers. The provided solution does so by converting the number to a list of digits. This function just returns the nth digit of a number, starting with the least significant one. For instance, digit 1 1234 equals 4.

digit :: Int -> Int -> Int
nth `digit` n = n `mod` 10 ^ nth `div` 10 ^ (nth - 1)

As mentioned, this problem is most naturally solved with a list comprehension, so that is what we will use as well. The actual conditions are of course nearly identical to the scheme version, with the exception that the condition that a * n1 has four digits is unnecessary, and therefore removed in this version.

feinman :: [(Int, Int)]
feinman = [ (n1, n2)
          | b <- [1..9], a <- [0..9], c <- [0..9],
            d <- [1..9], e <- [0..9], f <- [0..9],
            a /= b, a /= c, a /= d, a /= e, a /= f, e < d,
            let n1 = 100 * b + 10 * a + c,
            let n2 = 1000 * d + 100 * e + 10 * a + f,
            n1 * n2 > 999999, n1 * n2 < 10000000,
            digit 3 (n1 * n2) == a,
            digit 1 (d * n1) == a, digit 2 (d * n1) == a,
            digit 1 (e * n1) == a, digit 3 (a * n1) == a]

To test, we just print the list.

main :: IO ()
main = print feinman

As expected, we get the single result of (484, 7289). Runtime is about 8.5 seconds in ghci and 60 ms compiled (You’ve got to love compilers). The end result is 11 lines of code, so a slight improvement over the scheme version.

About these ads

Tags: , , , , , , ,

4 Responses to “Programming Praxis – Feynman’s Puzzle”

  1. kazuya Says:

    But Programming Praxis gives more than one solution, and all of them appear valid.

  2. Remco Niemeijer Says:

    If you read the text of the Programming Praxis post, you’ll see that the first solution, which provides multiple solutions, is his first attempt. It doesn’t give the correct answer. They may appear valid, but they aren’t. His second attempt, which produces a single answer, is the correct one.

  3. kazuya Says:

    Thank you for pointing me to PP’s commented solution page. I had skipped it and jumped directly to the code page.
    Now I got it.

  4. cvs268 Says:

    Here are a couple more programming puzzles to puzzle you…

    http://2600hertz.wordpress.com/2010/04/04/ipl-the-run-chase/

    http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/

    Good Luck!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: