Project Euler - Problem 17

It's been to long since I posted a solution to one of these challenges. How time flies when you're having fun.

Here's the problem:
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

Here is the python code:

  1. #!/usr/bin/env python
  3. ones = {'1': 'one', '2': 'two', '3': 'three', '4': 'four', '5': 'five',
  4. '6': 'six', '7': 'seven', '8': 'eight', '9': 'nine', '0': ''}
  6. tens = {'2': 'twenty', '3': 'thirty', '4': 'forty', '5': 'fifty',
  7. '6': 'sixty', '7': 'seventy', '8': 'eighty', '9': 'ninety'}
  9. teens = {'10': 'ten', '11': 'eleven', '12': 'twelve', '13': 'thriteen',
  10. '14': 'fourteen', '15': 'fifteen', '16': 'sixteen', '17': 'seventeen',
  11. '18': 'eighteen', '19': 'nineteen'}
  13. hundreds = {0: 0, 1: "onehundredand", 2: "twohundredand",
  14. 3: "threehundredand", 4: "fourhundredand",
  15. 5: "fivehundredand", 6: "sixhundredand",
  16. 7: "sevenhundredand", 8: "eighthundredand",
  17. 9: "ninehundredand" }
  19. if __name__ == "__main__":
  20. tot = 0
  21. for h in xrange(10):
  22. for y in xrange(1,100):
  23. try:
  24. t,o = tuple(str(y))
  25. if t is '1':
  26. tot += len("{h}{t}".format(h=hundreds[h], t=teens[t + o]))
  27. else:
  28. tot += len("{h}{t}{o}".format(h=hundreds[h], t=tens[t],
  29. o=ones[o]))
  30. except ValueError:
  31. tot += len("{h}{o}".format(h=hundreds[h], o=ones[str(y)]))
  32. tot += len('onethousand')
  33. print tot

Even though I wrote it, I still look at it and think "that's not mine." It's been a long time since I wrote a for loop within a for loop. There isn't anything wrong with it, it's just not my style. This time however I wasn't really able to come up with a solution that would allow me to break out of the two for loops.

The one part of the code that I was surprised "worked" war breaking up the digits by turning the number to a string then a tuple. This allowed me to easily test an exception. This exception will only be thrown 10% of the time. While exceptions might be expensive, the other 90% of the time the code hums along without using a conditional. Everything has costs, but I think that the cost of throwing an exception 10% of the time as opposed to testing a conditional 100% of the time is a cost I'm willing to accept.

I will admit that I did not code up another solution in a different programming language. While part of that is due to being lazy - it's good for the soul once and a while - I'm also not sure how I can code this up in a functional language. I'm sure it can be done, I just don't know how (If anyone has a link or idea please share it.) But because I do like to compare things I tweaked the code to run within python 3.3.0. The differences in time are so minimal that I'm not even going to post it. If you're really inspired you can read the python 3 code here.

Questions and comments welcomed. One quick side note to my readers: I'm getting married this year (Yay!) and a lot of my free time is spent juggling and planning. So I might not be blogging as frequently as usual. Thanks for your patience.

My First Yesod App

First off, I just wanted to say that I hope everyone had a relaxing and enjoyable holiday season and that you enjoyed your New Year's celebration. Whatever you did that day or night, don't name it after me.

In my last post, I showed you how to create a simple web service that responded to three different URLs and interacted with a database using Python and the Flask framework. Now I'm going to show you how to program the same thing in Haskell using the Yesod framework. For those of you too “efficient” to look them up on the previous page HERE, I'm going to repost the requirements:
Using python with gevent 0.13.x and your choice of additional libraries and/or frameworks, implement a single HTTP server with API endpoints that provide the following functionalities:

      A Fibonacci endpoint that accepts a number and returns the Fibonacci calculation for that number, and returns result in JSON format. example:

      1. $ curl -s ''
      2. {"response": 233}
      1. $ curl -s ''
      2. {"response": 144}
      An endpoint that fetches the Google homepage and returns the sha1 of the response message-body (HTTP body data).example:

      1. $ curl -s ''
      2. {"response": "272cca559ffe719d20ac90adb9fc4e5716479e96"}
      Using some external storage of your choice (can be redis, memcache, sqlite, mysql, etc), provide a means to store and then retrieve a value.Example:

      1. $ curl -d 'value=something' ''
      2. $ curl ''
      3. {"response": "something"}</li>

Like the last post, I'm going to talk about the individual functions first, then post the whole code at the end. Let's start with the first requirement, creating a good old Fibonacci sequence:

  1. handleFibR :: Int -> Handler RepJson
  2. handleFibR num = jsonToRepJson $ object ["response" .= show_fib]
  3. where
  4. show_fib = show $ fib num
  5. fib :: Int -> Int
  6. fib 0 = 0
  7. fib 1 = 1
  8. fib n = fib (n - 1) + fib (n – 2)

I'm going to go ahead and describe the code from the bottom up - it's a little weird but it's a lot easier to explain that way, trust me. The show_fib function is just a simple function to sum the values created from the Fibonacci sequence. The result of that function is used as the “value” component of a Pair type that is created with the “.=” operator and the “response” string, and is contained within a list. The object function takes a list of Pairs as its input and creates a Value type, which is described in the documentation as “A JSON value represented as a Haskell value.” This Value is then passed as the input into the jsonToRepJson function. All of these functions come together beautifully so that when you point your browser to http://localhost:3000/fib/24, you get this response:

For my next trick, I'm going to pull a SHA1 hash out from the Google homepage source code.

  1. gGoogR :: Handler RepJson$
  2. getGoogR = do$
  3. body <- try (simpleHttp "”)
  4. case body of$
  5. Left (SomeException ex) -> jsonToRepJson $ object [“response” .= (“ERROR: “ ++ (show ex))]
  6. Right val -> jsonToRepJson $ object [“response” .= (showDigest $ sha1 val)]

Much like the last function, this function will return a Handler containing a RepJson . First I use the simpleHttp function to travel to the interwebs and pull the Google homepage. Because simpleHttp will throw an HttpException with any non 200 status code, I have the function called within a try function, putting the result into “body”. Body is of the Either type, which means it can have one of two possible values (like Schrodinger's cat). If something went wrong, the value would be in the “Left” side of the Either type. If that's what happened, I don't really care what went wrong so I just return a generic error message. If everything flowed smoothly like all code does (snicker), the data would be on the “Right” side of Either, allowing me to pull the data out using the Right function and named val. The code after this point is extremely similar to the previous example, the difference being the output. The website source code is used as input for the sha1 function, creating a Digest type, then I carry that over to showDigest, which returns a string 160 characters long. All of this is bubbled up to the handler and the user sees:


Your results will differ! For dealing with the database, we need functions that can handle both GET and POST requests. Before I explain those functions, I want to take a quick moment to share the database schema and the “runDB” function:

  1. share [mkPersist sqlSettings, mkMigrate "migrateAll"] [persist|
  2. Stuff
  3. value Text
  4. deriving Show
  5. |]
  7. runDB action = do
  8. Challenge pool <- getYesod
  9. runSqlPool action pool

If you are a little confused by these two things, don't fear. I will do my best to describe them in a moment. If that still doesn't help then maybe viewing the entire code base below will. The first code block above is responsible for creating the Stuff database which holds a single column, called “value”. It reminds me of user defined datatypes created with the “data” Haskell keyword.

The second block is really me cargo cult programming. I've seen this technique used in a lot of the examples of the Yesod book, so I copied it while I was writing this project. The best way I can describe it is as a wrapper function for using an item from a pool of database connectors, and using some of those connectors to to run the query.

Now that you know what the database looks like and how we access it, we can move onto the functions that interact with it. Here is the code for the POST request:

  1. postStoreR :: Handler ()
  2. postStoreR = do
  3. mvalue <- runInputPost $ ireq textField "value"
  4. runDB $ insert $ Stuff mvalue
  5. sendResponseStatus status200 ()

This function just returns a Handler unit. Using the ireq function, we look through the POST request for the expected input keyed as “value”. The output of that function goes through the runInputPost, and deposits the contents into mvalue. We take mvalue, change it to become a Stuff type, pass that to the insert function which, when it runs, returns an automatically created key. and then moving that along to runDB, which inserts our data into the database. The last line returns the 200 status back to the client, using the sendResponseStatus.

Finally, for the GET request we have:

  1. getStoreR :: Handler RepJson
  2. getStoreR = do
  3. mvalue <- runDB $ selectFirst [] [Desc StuffValue, LimitTo 1]
  4. case mvalue of
  5. Nothing -> jsonToRepJson $ object ["response" .= (show "NO DATA IN DATABASE")]
  6. Just mvalue' -> jsonToRepJson $ object ["response" .= (show . stuffValue $ entityVal mvalue')]

The result of the selectFirst function provides the input for runDB. The first argument for selectFirst is an empty list, this argument is for filtering on some kind of value( greater than, less than, not equal to, etc). I have left it blank because I really don't care what the value of “value” is; I just want it. The second list is telling the database to put the column values in descending order. The first line is the Haskell equivalent of the following SQL code:


The results of which are named mvalue. Since it's possible to have nothing in the response, I use the case statement to dig inside mvalue and look around. If “Nothing” was returned, I send back a little json blurb letting the user know that nothing was found, most likely because there isn't data in the database. If something was returned, pull that value out, and mix it all in the with json recipe you've seen me using thus far, and then send the data on its way.

As the title says, this was my first Yesod web app. I know that I have only scratched the surface of what this framework can do and I'm really interested in creating more with it. I will admit that I initially found the interaction with the database a little cumbersome when compared to Django or Flask. That doesn't mean I don't like it, it's just a little awkward when I was first trying to understand how to work with it. Once I got over those differences, I realized that it mentally translates to SQL better than the other frameworks. Again, I really like Yesod and look forward to using it in the future.

As always, I and my code welcome questions, comments, and the occasional funny and creative insult.

  1. {-# LANGUAGE TypeFamilies, QuasiQuotes, MultiParamTypeClasses, TemplateHaskell #-}
  2. {-# LANGUAGE GADTs,OverloadedStrings,FlexibleContexts, FlexibleInstances #-}
  4. import Yesod as Y
  5. import Data.Text (pack, Text)
  6. import Network.HTTP.Conduit (simpleHttp)
  7. import Network.HTTP.Types (status200)
  8. import Data.Digest.Pure.SHA (showDigest, sha1)
  9. import Database.Persist.Sqlite
  10. import Data.Maybe
  11. import Control.Exception.Lifted hiding (Handler)
  12. import Data.ByteString.Lazy.Internal (ByteString)
  14. share [mkPersist sqlSettings, mkMigrate "migrateAll"] [persist|
  15. Stuff
  16. value Text
  17. deriving Show
  18. |]
  20. data Challenge = Challenge ConnectionPool
  22. mkYesod "Challenge" [parseRoutes|
  23. /fib/#Int FibR
  24. /google-body GoogR GET
  25. /store StoreR POST GET
  26. |]
  28. instance Yesod Challenge
  30. instance RenderMessage Challenge FormMessage where
  31. renderMessage _ _ = defaultFormMessage
  33. instance YesodPersist Challenge where
  34. type YesodPersistBackend Challenge = SqlPersist
  36. runDB action = do
  37. Challenge pool <- getYesod
  38. runSqlPool action pool
  40. handleFibR :: Int -> Handler RepJson
  41. handleFibR num = jsonToRepJson $ object ["response" .= show_fib]
  42. where
  43. show_fib = show $ fib num
  44. fib :: Int -> Int
  45. fib 0 = 0
  46. fib 1 = 1
  47. fib n = fib (n - 1) + fib (n - 2)
  49. getGoogR :: Handler RepJson
  50. getGoogR = do
  51. body <- try (simpleHttp "")
  52. case body of
  53. Left (SomeException ex) -> jsonToRepJson $ object ["response" .= ("ERROR: " ++ (show ex))]
  54. Right val -> jsonToRepJson $ object ["response" .= (showDigest $ sha1 val)]
  56. postStoreR :: Handler ()
  57. postStoreR = do
  58. mvalue <- runInputPost $ ireq textField "value"
  59. runDB $ Y.insert $ Stuff mvalue
  60. sendResponseStatus status200 ()
  62. getStoreR :: Handler RepJson
  63. getStoreR = do
  64. mvalue <- runDB $ Y.selectFirst [] [Y.Desc StuffValue, Y.LimitTo 1]
  65. case mvalue of
  66. Nothing -> jsonToRepJson $ object ["response" .= (show "NO DATA IN DATABASE")]
  67. Just mvalue' -> jsonToRepJson $ object ["response" .= (show . stuffValue $ Y.entityVal mvalue')]
  69. main = withSqlitePool ":memory:" 10 $ \pool -> do
  70. runSqlPool (runMigration migrateAll) pool
  71. warpDebug 3000 $ Challenge pool

First Flask web app

As everyone should know by now, I love coding challenges. A while ago I came across this one, which is rather long:
Using python with gevent 0.13.x and your choice of additional libraries and/or frameworks, implement a single HTTP server with API endpoints that provide the following functionalities:

      A Fibonacci endpoint that accepts a number and returns the Fibonacci calculation for that number, and returns result in JSON format. example:

      1. $ curl -s ''
      2. {"response": 233}
      1. $ curl -s ''
      2. {"response": 144}
      An endpoint that fetches the Google homepage and returns the sha1 of the response message-body (HTTP body data).example:

      1. $ curl -s ''
      2. {"response": "272cca559ffe719d20ac90adb9fc4e5716479e96"}
      Using some external storage of your choice (can be redis, memcache, sqlite, mysql, etc), provide a means to store and then retrieve a value.Example:

      1. $ curl -d 'value=something' ''
      2. $ curl ''
      3. {"response": "something"}</li>

At one point in my past a coworker talked about his love of the Flask micro framework. Since this is just a simple web API, I figured I'd give it a shot. This is a bit of a complicated task with many pieces, so let's set a game plan for the rest of this post. I'm going to share the specific functions related to each piece of functionality, then at the very end I will share the entire code base so everyone can see how it all fits together. One last note - to test out the run, you need to call the script, which will also be included below. Ready … BREAK!

Let's tackle the google-body endpoint first:

  1. @app.route('/google-body')
  2. def google_body():
  3. try:
  4. sh ='').read())
  5. return jsonify({'response' : sh.hexdigest()})
  6. except Exception as e:
  7. return jsonify({'response' : 'ERROR: %s' % str(e)})

While this code block is very compact, it's not difficult to understand. Go out to the internet, get the source code for google's home page and insert that into the sha object. Wrap up the hexdigest results into a dictionary object, throw that into the jsonify function, and send it on its way. Don't forget to package it all in a nice try/except block for safety.

Onto the Fibonacci API call:

  1. @app.route('/fib/<number>')
  2. def fib(number):
  3. try:
  4. return jsonify({'response' : real_fib(int(number))})
  5. except ValueError:
  6. return jsonify({'response' : 'ERROR: Input not a number'})
  8. @lru_cache()
  9. def real_fib(n):
  10. """
  11. This code was modified from the fib code in the python3 functools
  12. documentation.
  13. """
  14. if n < 2:
  15. return n
  16. return real_fib(n-1) + real_fib(n-2)

During PyCon US 2012, I became aware of the lru_cache decorator in python3.3. I also learned that Raymond Hettinger wrote code that would allow it work in python2, which allowed me to copy the code from the python3 documentation with little modification. Knowing about the lru_cache allowed me to write a nice and concise Fibonacci function reminiscent of something I might write in Haskell or some other functional language.

Now the last part of this challenge, and the longest. Before we get to the python, I feel that it might help your understanding if you know what kind of database schema we're working with. So I'm going to post that first, then the python code.

  1. drop table if exists entries;
  2. create table entries (
  3. id integer primary key autoincrement,
  4. value string not null
  5. );

  1. @app.route('/store', methods=['GET', 'POST'])
  2. def store():
  3. if request.method == 'POST':
  4. try:
  5. g.db.execute('insert into entries (value) values (?)',
  6. [request.form['value']])
  7. g.db.commit()
  8. resp = jsonify()
  9. resp.status_code = 200
  10. return resp
  11. except Exception as e:
  12. return jsonify({"response" : "ERROR: %s" % str(e)})
  13. else:
  14. try:
  15. cur = g.db.execute('select value from entries order by id desc')
  16. #fetchone returns a list. To better meet the requirements,
  17. #just slicing the head of the list and output that.
  18. return jsonify({'response' : cur.fetchone()[0]})
  19. except IndexError:
  20. return jsonify({'response' : 'NOTHING IN THE DATABASE'})

This step is obviously a little more complex - the function has to process both the GET and the POST HTTP methods, while using an outside database to store and retrieve the information. I believe the code here is simple enough for you to understand, so I won't explain every line. For the POST method I had to do some juggling to get the desired return results. In the example above a POST method works, but does not receive an actual response. I was able to create this by using the jsonify object to create an empty Flask.Response object, and then set the status code of that response.

At the end of the day I'm pretty happy with this. It wasn't a hard challenge, but certainly allowed me to learn a bit about Flask. If I did over again, I might improve things by creating my own decorator to abstract all the try/except blocks. The errors would have to become more generic and maybe less helpful, but that is a worthwhile cost for being able to live the “Don't Repeat Yourself” mentality. The decorator would look something like this (the code below has not been tested - caveat emptor):

  1. def try_block(f):
  2. @wraps
  3. def wrapper(*args, **kwds):
  4. try:
  5. return f(*args,**kwds)
  6. except ValueError:
  7. return jsonify({'response' : 'ERROR: Input not a number'})

As more functions start to use this decorator it'll most likely get uglier as it has to juggle more and more exceptions. While that is certainly a cost of having all of the error checking wrapped up in one location, the benefit that I can see is if another programmer were to add a new piece of functionality, he would know exactly where to go to add in the exceptions if it wasn't there already.

  1. @app.route('/fib/<number>')
  2. @try_block
  3. def fib(number):
  4. return jsonify({'response' : real_fib(int(number))})

I think this would clean up the function quite a bit.

Next time I'm going to show how to do this in Haskell using the Yesod web framework. As always, questions, and comments are welcomed.

  1. from gevent.wsgi import WSGIServer
  2. from playhaven import app, init_db
  4. init_db()
  5. http_server = WSGIServer(('', 8080), app)
  6. http_server.serve_forever()

  1. from __future__ import with_statement
  2. from urllib2 import urlopen
  3. from contextlib import closing
  4. from flask import Flask, request, g, jsonify
  5. from lru_cache import lru_cache
  6. import sqlite3
  7. import sha
  9. DATABASE = '/tmp/challenge.db'
  10. DEBUG = True
  11. SECRET_KEY = 'c29tZXRoaW5nY2xldmVyaGVyZQ==\n'
  12. USERNAME = 'challenge'
  13. PASSWORD = 'chang3m3'
  15. app = Flask(__name__)
  16. app.config.from_object(__name__)
  18. app.config.from_envvar('CHALLENGE_SETTINGS', silent=True)
  20. def connect_db():
  21. return sqlite3.connect(app.config['DATABASE'])
  23. def init_db():
  24. with closing(connect_db()) as db:
  25. with app.open_resource('schema.sql') as f:
  26. db.cursor().executescript(
  27. db.commit()
  29. @app.before_request
  30. def before_request():
  31. g.db = connect_db()
  33. @app.teardown_request
  34. def teardown_request(exception):
  35. g.db.close()
  37. @app.route('/fib/<number>')
  38. def fib(number):
  39. try:
  40. return jsonify({'response' : real_fib(int(number))})
  41. except ValueError:
  42. return jsonify({'response' : 'ERROR: Input not a number'})
  44. @lru_cache()
  45. def real_fib(n):
  46. """
  47. This code was modified from the fib code in the python3 functools
  48. documentation.
  49. """
  50. if n < 2:
  51. return n
  52. return real_fib(n-1) + real_fib(n-2)
  54. @app.route('/google-body')
  55. def google_body():
  56. try:
  57. sh ='').read())
  58. return jsonify({'response' : sh.hexdigest()})
  59. except Exception as e:
  60. return jsonify({'response' : 'ERROR: %s' % str(e)})
  62. @app.route('/store', methods=['GET', 'POST'])
  63. def store():
  64. if request.method == 'POST':
  65. try:
  66. g.db.execute('insert into entries (value) values (?)',
  67. [request.form['value']])
  68. g.db.commit()
  69. resp = jsonify()
  70. resp.status_code = 200
  71. return resp
  72. except Exception as e:
  73. return jsonify({"response" : "ERROR: %s" % str(e)})
  74. else:
  75. try:
  76. cur = g.db.execute('select value from entries order by id desc')
  77. #fetchone returns a list. To better meet the requirements,
  78. #just slicing the head of the list and output that.
  79. return jsonify({'response' : cur.fetchone()[0]})
  80. except IndexError:
  81. return jsonify({'response' : 'NOTHING IN THE DATABASE'})
  83. if __name__ == '__main__':

Project Euler: Problem 16

I'm not dead yet! I've just been insanely busy the last month or two with changing jobs and preparing my first programming presentation for BayPiggies and Silicon Valley Code Camp (which is a post for the near future). Both of these have kept me away from my blog. Let me make it up to you with a solution to project Euler problem #16.

The challenge is:

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?

Let's start with some Python code:

  1. #!/usr/bin/python
  3. print sum([int(i) for i in str(2 ** 1000)])

For this solution, using a more functional approach definitely reduced the code base. But one thing I was a little surprised about is that having a list comprehension within the sum function is actually faster than a generator expression. Usually one hears how generator expressions are preferred over list comprehensions because they are more efficient with memory, among other reasons. However, it's actually faster to give sum a list. One quick caveat, this whole sum and list comprehension thing applies to Python 2. The same seems to be also be true for Python 3, at least from the interpreter:

  1. >>> import timeit
  2. >>> timeit.timeit("sum(int(x) for x in str(2 ** 1000))", number=1000)
  3. 0.11109958100132644
  4. >>> timeit.timeit("sum([int(x) for x in str(2 ** 1000)])", number=1000)
  5. 0.09597363900684286
  6. >>> timeit.timeit("sum(int(x) for x in str(2 ** 1000))", number=10000)
  7. 1.051396899012616
  8. >>> timeit.timeit("sum([int(x) for x in str(2 ** 1000)])", number=10000)
  9. 0.9054670640034601
  10. >>> timeit.timeit("sum(int(x) for x in str(2 ** 1000))", number=100000)
  11. 10.498383879996254
  12. >>> timeit.timeit("sum([int(x) for x in str(2 ** 1000)])", number=100000)
  13. 8.992312036993098

On to the Haskell code:

  1. module Main where
  3. import Data.Char
  5. main :: IO ()
  6. main = print . sum . map digitToInt . show $ 2 ^ 1000

Maybe it's just me and my Haskell/Python-centric brain, but I think the algorithm is simple enough to easily see the similarities and differences between the two languages. If I wanted to write the Haskell code to better match the Python code (syntactic differences aside), it would look like this: (inside the Haskell interpreter)

  1. Prelude Data.Char> print . sum $ [ digitToInt x | x <- show (2 ^ 1000)]

Even though this code may be easier to read for a Python programmer, it's not “good” Haskell code. It'll get the job done, but the map is obfuscated by the list comprehension. We can also adjust the Python code to make it resemble Haskell by using map:

print sum(map(int, str(2 ** 1000)))

But that might get you “dinged” because some people think that using map is “too functional” or “not Pythonic”, even if the code might be faster. I don't subscribe to that line of thinking...but that's a discussion for another time.

python – list comprehension : .032s
python – map : .030s
haskell – list ( interpreted) : .155s
haskell – map (interpreted) : .155s
haskell – list (compiled) : .006s
haskell – map (compiled) : .006s

As always, questions, comments, and complaints are encouraged. I hope everyone will forgive me for not posting for so long... sometimes life happens.

Syndicate content