## 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:

`#!/usr/bin/env python ones = {'1': 'one', '2': 'two', '3': 'three', '4': 'four', '5': 'five',        '6': 'six', '7': 'seven', '8': 'eight', '9': 'nine', '0': ''} tens = {'2': 'twenty', '3': 'thirty', '4': 'forty', '5': 'fifty',        '6': 'sixty', '7': 'seventy', '8': 'eighty', '9': 'ninety'} teens = {'10': 'ten', '11': 'eleven', '12': 'twelve', '13': 'thriteen',         '14': 'fourteen', '15': 'fifteen', '16': 'sixteen', '17': 'seventeen',         '18': 'eighteen', '19': 'nineteen'} hundreds = {0: 0, 1: "onehundredand", 2: "twohundredand",            3: "threehundredand", 4: "fourhundredand",            5: "fivehundredand", 6: "sixhundredand",            7: "sevenhundredand", 8: "eighthundredand",            9: "ninehundredand" } if __name__ == "__main__":    tot = 0    for h in xrange(10):        for y in xrange(1,100):            try:                t,o = tuple(str(y))                if t is '1':                    tot += len("{h}{t}".format(h=hundreds[h], t=teens[t + o]))                else:                    tot += len("{h}{t}{o}".format(h=hundreds[h], t=tens[t],                                                  o=ones[o]))            except ValueError:                    tot += len("{h}{o}".format(h=hundreds[h], o=ones[str(y)]))    tot += len('onethousand')    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: \$ curl -s 'http://127.0.0.1:8080/fib/13'{"response": 233} \$ curl -s 'http://127.0.0.1:8080/fib/12'{"response": 144} An endpoint that fetches the Google homepage and returns the sha1 of the response message-body (HTTP body data).example: \$ curl -s 'http://127.0.0.1:8080/google-body'{"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: \$ curl -d 'value=something' 'http://127.0.0.1:8080/store'\$ curl 'http://127.0.0.1:8080/store'{"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:

`handleFibR :: Int -> Handler RepJsonhandleFibR num = jsonToRepJson \$ object ["response" .= show_fib]  where    show_fib = show \$ fib num    fib :: Int -> Int    fib 0 = 0    fib 1 = 1    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:
`{"response":"46368"}`

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

`gGoogR :: Handler RepJson\$                   getGoogR = do\$                                      body <- try (simpleHttp "http://www.google.com”)      case body of\$                                       Left (SomeException ex) -> jsonToRepJson \$ object [“response” .= (“ERROR:  “ ++ (show ex))]         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:

`{"response":"ddd27a244477532f7be5207582afca72b9f74224"}`

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:

`share [mkPersist sqlSettings, mkMigrate "migrateAll"] [persist|Stuff    value Text    deriving Show|] runDB action = do        Challenge pool <- getYesod        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:

`postStoreR :: Handler ()postStoreR = do    mvalue <- runInputPost \$ ireq textField "value"    runDB \$ insert \$ Stuff mvalue    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:

`getStoreR :: Handler RepJsongetStoreR = do    mvalue <- runDB \$ selectFirst [] [Desc StuffValue, LimitTo 1]    case mvalue of        Nothing -> jsonToRepJson \$ object ["response" .= (show "NO DATA IN DATABASE")]        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:

`SELECT * FROM Stuff GROUP BY VALUE DESC LIMIT 1;`

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.

`{-# LANGUAGE TypeFamilies, QuasiQuotes, MultiParamTypeClasses, TemplateHaskell #-}{-# LANGUAGE GADTs,OverloadedStrings,FlexibleContexts, FlexibleInstances #-} import Yesod as Yimport Data.Text (pack, Text)import Network.HTTP.Conduit (simpleHttp)import Network.HTTP.Types (status200)import Data.Digest.Pure.SHA (showDigest, sha1)import Database.Persist.Sqliteimport Data.Maybeimport Control.Exception.Lifted hiding (Handler) import Data.ByteString.Lazy.Internal (ByteString) share [mkPersist sqlSettings, mkMigrate "migrateAll"] [persist|Stuff    value Text    deriving Show|] data Challenge = Challenge ConnectionPool mkYesod "Challenge" [parseRoutes|/fib/#Int FibR/google-body GoogR GET/store StoreR POST GET|] instance Yesod Challenge instance RenderMessage Challenge FormMessage where     renderMessage _ _ = defaultFormMessage  instance YesodPersist Challenge where    type YesodPersistBackend Challenge = SqlPersist     runDB action = do        Challenge pool <- getYesod        runSqlPool action pool handleFibR :: Int -> Handler RepJsonhandleFibR num = jsonToRepJson \$ object ["response" .= show_fib]  where    show_fib = show \$ fib num    fib :: Int -> Int    fib 0 = 0    fib 1 = 1    fib n = fib (n - 1) + fib (n - 2) getGoogR :: Handler RepJsongetGoogR = do    body <- try (simpleHttp "http://www.google.com")    case body of        Left (SomeException ex) -> jsonToRepJson \$ object ["response" .= ("ERROR: " ++ (show ex))]        Right val -> jsonToRepJson \$ object ["response" .= (showDigest \$ sha1 val)] postStoreR :: Handler ()postStoreR = do    mvalue <- runInputPost \$ ireq textField "value"    runDB \$ Y.insert \$ Stuff mvalue    sendResponseStatus status200 () getStoreR :: Handler RepJsongetStoreR = do    mvalue <- runDB \$ Y.selectFirst [] [Y.Desc StuffValue, Y.LimitTo 1]    case mvalue of        Nothing -> jsonToRepJson \$ object ["response" .= (show "NO DATA IN DATABASE")]        Just mvalue' -> jsonToRepJson \$ object ["response" .= (show . stuffValue \$ Y.entityVal mvalue')] main = withSqlitePool ":memory:" 10 \$ \pool -> do    runSqlPool (runMigration migrateAll) pool    warpDebug 3000 \$ Challenge pool`

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: \$ curl -s 'http://127.0.0.1:8080/fib/13'{"response": 233} \$ curl -s 'http://127.0.0.1:8080/fib/12'{"response": 144} An endpoint that fetches the Google homepage and returns the sha1 of the response message-body (HTTP body data).example: \$ curl -s 'http://127.0.0.1:8080/google-body'{"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: \$ curl -d 'value=something' 'http://127.0.0.1:8080/store'\$ curl 'http://127.0.0.1:8080/store'{"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 run.py script, which will also be included below. Ready … BREAK!

Let's tackle the google-body endpoint first:

`@app.route('/google-body')def google_body():    try:        sh = sha.new(urlopen('http://www.google.com').read())        return jsonify({'response' : sh.hexdigest()})    except Exception as e:        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:

`@app.route('/fib/<number>')def fib(number):    try:        return jsonify({'response' : real_fib(int(number))})    except ValueError:        return jsonify({'response' : 'ERROR: Input not a number'}) @lru_cache()def real_fib(n):    """        This code was modified from the fib code in the python3 functools         documentation.    """    if n < 2:        return n    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.

`drop table if exists entries;create table entries (    id integer primary key autoincrement,    value string not null);`

`@app.route('/store', methods=['GET', 'POST'])def store():    if request.method == 'POST':        try:            g.db.execute('insert into entries (value) values (?)',                         [request.form['value']])            g.db.commit()            resp = jsonify()            resp.status_code = 200            return resp        except Exception as e:            return jsonify({"response" : "ERROR: %s" % str(e)})    else:        try:            cur = g.db.execute('select value from entries order by id desc')            #fetchone returns a list. To better meet the requirements,            #just slicing the head of the list and output that.            return jsonify({'response' : cur.fetchone()[0]})        except IndexError:            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):

`def try_block(f):    @wraps    def wrapper(*args, **kwds):        try:            return f(*args,**kwds)       except ValueError:            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.

`@app.route('/fib/<number>')@try_blockdef fib(number):    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.

run.py

`from gevent.wsgi import WSGIServerfrom playhaven import app, init_db init_db()http_server = WSGIServer(('0.0.0.0', 8080), app)http_server.serve_forever()`

challenge.py

`from __future__ import with_statementfrom urllib2 import urlopenfrom contextlib import closingfrom flask import Flask, request, g, jsonifyfrom lru_cache import lru_cacheimport sqlite3import sha DATABASE = '/tmp/challenge.db'DEBUG = TrueSECRET_KEY = 'c29tZXRoaW5nY2xldmVyaGVyZQ==\n'USERNAME = 'challenge'PASSWORD = 'chang3m3' app = Flask(__name__)app.config.from_object(__name__) app.config.from_envvar('CHALLENGE_SETTINGS', silent=True) def connect_db():    return sqlite3.connect(app.config['DATABASE']) def init_db():    with closing(connect_db()) as db:        with app.open_resource('schema.sql') as f:            db.cursor().executescript(f.read())        db.commit() @app.before_requestdef before_request():    g.db = connect_db() @app.teardown_requestdef teardown_request(exception):    g.db.close() @app.route('/fib/<number>')def fib(number):    try:        return jsonify({'response' : real_fib(int(number))})    except ValueError:        return jsonify({'response' : 'ERROR: Input not a number'}) @lru_cache()def real_fib(n):    """        This code was modified from the fib code in the python3 functools         documentation.    """    if n < 2:        return n    return real_fib(n-1) + real_fib(n-2) @app.route('/google-body')def google_body():    try:        sh = sha.new(urlopen('http://www.google.com').read())        return jsonify({'response' : sh.hexdigest()})    except Exception as e:        return jsonify({'response' : 'ERROR: %s' % str(e)}) @app.route('/store', methods=['GET', 'POST'])def store():    if request.method == 'POST':        try:            g.db.execute('insert into entries (value) values (?)',                         [request.form['value']])            g.db.commit()            resp = jsonify()            resp.status_code = 200            return resp        except Exception as e:            return jsonify({"response" : "ERROR: %s" % str(e)})    else:        try:            cur = g.db.execute('select value from entries order by id desc')            #fetchone returns a list. To better meet the requirements,            #just slicing the head of the list and output that.            return jsonify({'response' : cur.fetchone()[0]})        except IndexError:            return jsonify({'response' : 'NOTHING IN THE DATABASE'}) if __name__ == '__main__':    app.run()`

## 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?

`#!/usr/bin/python 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:

`>>> import timeit>>> timeit.timeit("sum(int(x) for x in str(2 ** 1000))", number=1000)0.11109958100132644>>> timeit.timeit("sum([int(x) for x in str(2 ** 1000)])", number=1000)0.09597363900684286>>> timeit.timeit("sum(int(x) for x in str(2 ** 1000))", number=10000)1.051396899012616>>> timeit.timeit("sum([int(x) for x in str(2 ** 1000)])", number=10000)0.9054670640034601>>> timeit.timeit("sum(int(x) for x in str(2 ** 1000))", number=100000)10.498383879996254>>> timeit.timeit("sum([int(x) for x in str(2 ** 1000)])", number=100000)8.992312036993098`

`module Main where import Data.Char main :: IO ()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)

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

Times:
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.