ScrollingText

Project Euler - Problem 17

Bryce — Tue, 19 Mar 2013 16:59:13 +0000

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

Bryce — Fri, 01 Feb 2013 05:54:36 +0000

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 RepJson
handleFibR 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 RepJson
getStoreR = 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 Y
import Data.Text (pack, Text)
import Network.HTTP.Conduit (simpleHttp)
import Network.HTTP.Types (status200)
import Data.Digest.Pure.SHA (showDigest, sha1)
import Database.Persist.Sqlite
import Data.Maybe
import 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 RepJson
handleFibR 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 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)]
 
postStoreR :: Handler ()
postStoreR = do
    mvalue <- runInputPost $ ireq textField "value"
    runDB $ Y.insert $ Stuff mvalue
    sendResponseStatus status200 ()
 
getStoreR :: Handler RepJson
getStoreR = 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

First Flask web app

Bryce — Wed, 28 Nov 2012 21:54:09 +0000

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_block
def 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 WSGIServer
from 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_statement
from urllib2 import urlopen
from contextlib import closing
from flask import Flask, request, g, jsonify
from lru_cache import lru_cache
import sqlite3
import sha
 
DATABASE = '/tmp/challenge.db'
DEBUG = True
SECRET_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_request
def before_request():
    g.db = connect_db()
 
@app.teardown_request
def 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

Bryce — Thu, 25 Oct 2012 16:12:48 +0000

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:

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

On to the Haskell code:

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.

Book Review - Coders At Work

Bryce — Tue, 28 Aug 2012 17:01:00 +0000

I just finished reading the book Coders at Work by Peter Seibel. This wonderful book is filled with interviews with prominent programmers: Joe Armstrong, Simon Peyton Jones, Donald Knuth, among others. My review isn't going to be the standard book review. Instead I'm going to talk about some of the specific ideas I picked up while reading the book and discuss those ideas, rather than the book itself. For those of you who are looking for more of a standard review, all I can really say is that Coders at Work is well worth the time for a programmer or a computer historian/hobbyist. Unfortunately for the casual non-computer-field reader, the interview topics (and the interviewees) assume a certain level of prior knowledge. What makes this book so good is that different people will be able to walk away from it with different ideas, depending on their areas of expertise and interest. As the industry grows and changes, we definitely do things based on what the people before us have already discovered - Seibel’s interview subjects are the fascinating programmers whose ideas and hard work make possible all the cool things we get to play with today.

Code Readings:

In the interview with Douglas Crockford there was a lot of talk about code readings. If you’re not sure what those are (I wasn’t), from the way Douglas describes it they are regular meetings where programmers read the code base together. In my mind it sounds like someone is giving a presentation but instead of it being PowerPoint slides, it’s code. I picture the presenter going line by line and describing what is going on and why he or she decided to do things a particular way. These sound like an excellent idea to me. In my experience so far, the code review process seems to have been relegated to using Reviewboard or other similar website-based tools. I'm not trying to insult these tools, but they remove the human factor of the code review and hinder the discussion that can happen over a particular piece of code. I understand that programmer time is expensive and managers should be careful how much of that time is spent in meetings. But I think these meetings could benefit everyone and will have a return on investment (that is the time spent) in ways that cannot be quickly seen. One benefit is that everyone who attends will come out with a basic idea of what the code looks like within a given project, even if they’re not working on that project directly. So if things shift around (as they inevitably do) and a new person is moved into that project, he or she won’t be starting from scratch. Even just a little bit of knowledge might help a programmer get over the initial shock of having to dive into a new project.

Programmers need Empathy:

In the interview with Joshua Bloch there was a quick chat about programmer personalities. There were a couple of choice quotes regarding programmer empathy for the users, like, “...intelligence is not a scalar quantity; it’s a vector quantity. And if you lack empathy or emotional intelligence, then you shouldn’t be designing APIs or GUIs or languages.” and “What we’re doing is an aesthetic pursuit. It involves craftsmanship as well as mathematics and it involves people skills and prose skills—all of these things that we don’t necessarily think of as engineering but without which I don’t think you’ll ever be a really good engineer.”

I bring these quotes up because I agree with them, and because they speak of issues that are largely ignored in the engineering community (again, in my experience). I've sure we’ve all run into programmers that only care about the technical aspects of the project or the correctness of their code and do not concern themselves for how the user might interact with the system. For example, the company I work for designed a web-app that included separate “Kill” and “Terminate” buttons. This was a complete UI fail that could have been avoided, had the programmer (we’ll call him/her “Terry”) had empathy for the user. As a programmer, I understand the difference between SIGKILL and SIGTERM, but those buttons would be confusing to even the more-advanced-than-average user (and go far beyond failing the grandmother test). When this was brought up as a ticket for “Terry” to fix, “Terry” argued that there was nothing technically incorrect about the problem and closed the ticket “Won't Fix.”

Hiring:

One thing I noticed in a lot of the interviews was that Peter asked the interviewee what he or she looked for in a potential new hire. What I found fascinating is that none of them said, “I like to ask really hard questions.” or “I ask really obscure questions about the programming language they use to see how well they know it.” They mostly talked about looking for someone who had passion for the craft.

As someone who is frequently on both sides of the hiring table, I know that the current hiring process in Silicon Valley doesn't normally ask questions about WHO is being hired. Questions about hobbies or interests are rare. It's mostly just technical questions, as if the person who is applying for the job is another computer whose sole purpose is to solve a company's problems. All the emphasis seems to be focused on the technical skills of the interviewee. While it's important to know if someone can “do the job,” tech skills alone do not make a person a great programmer - a good one, yes, but I don’t get the impression that companies are settling for “good” anymore. Passion is what gives someone the tenacity to work through the obstacles and become a great programmer, and if we as interviewers insist on focusing only on hard skills, we risk cheating ourselves out of the truly great engineers.

Donald Knuth:

Peter also asked every single interviewee about Donald Knuth's books and his “literate programming”
style of writing code. I will admit that I have not read his books, but I want to. I'm not sure what this literate programming style is, but I'm curious enough about it to learn, and see if there are some aspects of it I can incorporate into my own coding and documentation style. Next step, pick up an electronic version of the book, “Literate Programming” and give it a good read.

I fully enjoyed Coders at Work. I took away much more from the interviews than I talked about here, and I’m sure there’s even more to learn. I'm planning on rereading it again in a couple of years; as I grow as a programmer I will have a different perspective on the craft, and might find a whole new or different set of lessons from what I got this time. If not, at the very least I’ll have the pleasure of reading it again.

Project Euler: Problem 14

Bryce — Wed, 25 Jul 2012 16:45:37 +0000

“The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even) n → 3n + 1 (n is odd). Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? NOTE: Once the chain starts the terms are allowed to go above one million.”

Not many of you may be aware of this, but about a year ago I wrote up a blog post that discussed Collatz chains in Haskell. You can find that post here: . Having some of the code already written made coming up with the solution easier. However, just because I had one function doesn't mean I had the whole problem licked. I still had a fair amount of work in front of me. Below is my code from the first attempt at a solution:

module Main where
 
 import Data.List
 
chain' :: Integer -> [Integer]
chain' 1 = [1]
chain' n
    | n <= 0 = []
    | even n = n : chain' (n `div` 2)
    | odd n = n : chain' (n * 3 + 1)
 
 main :: IO ()
 main = do
     let seqx = map chain' [3..1000000]
     let lengthx = map length seqx
     print . maximum $ zip lengthx seqx

This code appears to be logically correct but was incredibly slow - so slow that after over 2 minutes it still hadn’t completed. I admit I can be a little impatient with these things from time to time, but in this case something was obviously wrong.

I devised two optimizations:

Reverse the order of the list. I will be more likely to find the number with the longest chain near 1,000,000 than 3.
Use odd numbers only. This is based on the fact that in the chain' function an odd number gets multiplied right off the bat, whereas an even number is instantly divided by 2, and also on the assumption that a higher number will be more likely to have a longer chain. (I admit this was a complete experiment - I had no proof that it would work ahead of time, and knew it gave me the right answer only after the fact.)

The code then morphed into:

module Main where
 
 import Data.List
 
chain' :: Integer -> [Integer]
chain' 1 = [1]
chain' n
    | n <= 0 = []
    | even n = n : chain' (n `div` 2)
    | odd n = n : chain' (n * 3 + 1)
 
 main :: IO ()
 main = do
     let seqx = map chain' [999999,999997..3]
     let lengthx = map length seqx
     print . maximum $ zip lengthx seqx

The problem I ran into with this code was that I received stack overflow errors; my list of tuples holding another long list of int’s was taking up to much memory. I fixed this problem by computing the length of the list immediately after generating it. The new code looked like this:

import Data.List
 
chain' :: Integer -> [Integer]
chain' 1 = [1]
chain' n
    | n <= 0 = []
    | even n = n : chain' (n `div` 2)
    | odd n = n : chain' (n * 3 + 1)
 
 main :: IO ()
 main = do
     let seqx = map (\x → (x, length $ chain' x) [999999,999997..3]
     print . maximum $ seqx

This got me a result within the one minute time frame, but it still wasn't the right answer. Can you figure out why? Using the great code Jedai posted in the comments of my Apache log post, I was able to get my answer and finally complete the problem:

module Main where                                                                             
  
  import Data.Tuple
  import Data.List (sortBy)
  import Data.Function (on)
  
  chain' :: Integer -> [Integer]
  chain' 1 = [1]
  chain' n
    | n <= 0 = []
    | even n = n : chain' (n `div` 2)
    | odd n = n : chain' (n * 3 + 1)
  
  main :: IO ()
  main = do
      let seqx = map (\x -> (x, length $ chain' x)) [999999,999997..3]
      print . fst . head $ sortBy (flip compare `on` snd) seqx

After figuring that out, getting the python answer was a breeze:

#!/usr/bin/python
"""Python solution for Project Euler problem #14."""
 
from itertools import imap
 
def sequence(number):
    t_num = number
    count = 1
 
    while(t_num > 1):
        if t_num % 2 == 0:
            t_num /= 2
        else:
            t_num = (t_num * 3) + 1
 
        count += 1
 
    return (count, number)
 
if __name__ == "__main__":
  print max(imap(sequence, xrange(999999,3,-2)))

Here are the speed numbers:
Haskell (complied) : 14.758s
Python : 18.537s
Haskell (runghc): 15.217s

I think the use of recursion in my Haskell code is affecting its speed of computation. As I learned from problem 12, I can use the State Monad again to speed things up. But I also learned from the comments of problem 12 that some people were able to substitute a scan or fold in the State Monad’s place. So I decided to shoot for one more solution. After studying up on scan and fold, and finding that neither was really what I wanted, I found iterate. Using iterate I was able to change the program to this:

module Main where
 
 import Data.Tuple
 import Data.List (sortBy, iterate)
 import Data.Function (on)
 
 chain' :: Integer -> Int
 chain' n  
     | n < 1 = 0
     | otherwise = 1 + (length $ (takeWhile ( > 1) $ iterate (\x -> if even x then x `div` 2 else x * 3 + 1) n))
 
 main :: IO ()
 main = do
     let seqx = map (\x -> (x, chain' x)) [999999,999997..3]
     print . fst . head $ sortBy (flip compare `on` snd) seqx

The new chain' function doesn't read as cleanly as the old one, but it does remove the recursion I was talking about earlier. The computer gods rewarded my efforts by reducing the run times to these:

Haskell (complied) : 10.933s
Haskell (runghc): 11.744s

From 14.758 to 10.933 - almost 4 seconds taken off the clock! I think a speed up like that calls for some celebrating. Which is exactly what I'm going to do before I start on problem 15.

More than 1095 days of existence!! Or...Happy third birthday to Scrollingtext!!!

Bryce — Fri, 29 Jun 2012 16:30:28 +0000

Another 365 have come and gone since the last time I've written one of these birthday posts, and like last time I'm still surprised and still proud that this blog and my creative juices have survived this long.

I will be the first to admit that I'm totally amazed over 17 THOUSAND people from all over the world have dropped by my site and read my writing. Who know what I had to say was that interesting? Knowing that interest is growing really makes me want to continue improving my writing and finding more interesting projects to explore. Last year Scrollingtext saw a little more than 10 thousand people - there’s been an amazing amount of growth over the last year, and I think I'm going to make it a personal goal to continue this trend.

The five most popular posts for the year are:

PXE Network Boot VirtualBox, PT 2 – This one has been up here for a long time. Seeing this in the top 5 makes me think I should think about doing follow-up posts on VirtualBox. Apparently people find this helpful.
Using curl and a user agent string for web scraping – I had no idea that web scraping would be so popular. Maybe I should write a follow-up article for this one too.
Project Euler: Problem 5 – The biggest thing for me about this post was learning about lcm's. As has been pointed out to me in the comments for Problem 12, and as a statement about programming in general, understanding the problem and knowing the right algorithm (or two) that solve it is more than half the battle.
Project Euler: Problem 4 – I think this one takes the cake for most comments on a single post. Oh and OJ, I was just reading over those comments and I think I picked up on your subtle optimization. Nice little trick!
Project Euler: Problem 12 – I was really proud of this post. I spent a lot of time and energy learning how to use the State Monad to get the problem to run and the result was totally worth the effort.

Things I've learned:
For the last year I've had an actual programming job, and within that job I've learned a lot of python programming tricks and idioms - some of which I know have carried over into my personal style. My playing around with Haskell as also affected my style of programming. My boss can identify my code on sight because I use fewer variables than my co-workers. So in a way I've learned that everything I do, both at work and on my own, are connected. The time spent thinking about Project Euler problems and writing that code may not directly translate to what I do at work, but it definitely has an effect on the code I end up writing at work (and the quality of that code).

No retrospective post would not be complete without the “Thank yous.” First, thank you to my girlfriend , Kelsey. If it wasn't for her I wouldn't be able to properly articulate my thoughts to the world. And secondly thank you to the 17 thousand people who visited the site last year, all the people who visited in the previous two, and everyone who keeps coming back. Having a place where I can post what I'm currently working on in my spare time is a nifty thing. But having people actually read it makes it so much cooler! So thank you to everyone who's ever read something on my site, where ever you are now.

On that note, Happy 3rd birthday Scrollingtext. Here’s to another year and hopefully many more.

** Photo copied from here: http://www.flickr.com/photos/ebelbeb/5244753318/

Project Euler: Problem 13

Bryce — Tue, 22 May 2012 16:48:04 +0000

Problem thirteen from Project Euler is one of those problems that's so simple, I don't understand why it's in the double digits section. The problem reads: “Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.”
It then proceeds to list 100 long numbers. I'm not going to paste them here because they are in the code solutions below and I don't want to clog up the “tubez” with more redundant information than I'm about to.

Enough of my jibber-jabber. Here is my Haskell solution first (trying to change things up here):

module Main where
 
main :: IO()
main = do
    print . take 10 . show $ sum big_number
    where big_number = [ 37107287533902102798797998220837590246510135740250
                       , 46376937677490009712648124896970078050417018260538
                       , 74324986199524741059474233309513058123726617309629
                       , 91942213363574161572522430563301811072406154908250
                       , 23067588207539346171171980310421047513778063246676
                       , 89261670696623633820136378418383684178734361726757
                       , 28112879812849979408065481931592621691275889832738
                       , 44274228917432520321923589422876796487670272189318
                       , 47451445736001306439091167216856844588711603153276
                       , 70386486105843025439939619828917593665686757934951
                       , 62176457141856560629502157223196586755079324193331
                       , 64906352462741904929101432445813822663347944758178
                       , 92575867718337217661963751590579239728245598838407
                       , 58203565325359399008402633568948830189458628227828
                       , 80181199384826282014278194139940567587151170094390
                       , 35398664372827112653829987240784473053190104293586
                       , 86515506006295864861532075273371959191420517255829
                       , 71693888707715466499115593487603532921714970056938
                       , 54370070576826684624621495650076471787294438377604
                       , 53282654108756828443191190634694037855217779295145
                       , 36123272525000296071075082563815656710885258350721
                       , 45876576172410976447339110607218265236877223636045
                       , 17423706905851860660448207621209813287860733969412
                       , 81142660418086830619328460811191061556940512689692
                       , 51934325451728388641918047049293215058642563049483
                       , 62467221648435076201727918039944693004732956340691
                       , 15732444386908125794514089057706229429197107928209
                       , 55037687525678773091862540744969844508330393682126
                       , 18336384825330154686196124348767681297534375946515
                       , 80386287592878490201521685554828717201219257766954
                       , 78182833757993103614740356856449095527097864797581
                       , 16726320100436897842553539920931837441497806860984
                       , 48403098129077791799088218795327364475675590848030
                       , 87086987551392711854517078544161852424320693150332
                       , 59959406895756536782107074926966537676326235447210
                       , 69793950679652694742597709739166693763042633987085
                       , 41052684708299085211399427365734116182760315001271
                       , 65378607361501080857009149939512557028198746004375
                       , 35829035317434717326932123578154982629742552737307
                       , 94953759765105305946966067683156574377167401875275
                       , 88902802571733229619176668713819931811048770190271
                       , 25267680276078003013678680992525463401061632866526
                       , 36270218540497705585629946580636237993140746255962
                       , 24074486908231174977792365466257246923322810917141
                       , 91430288197103288597806669760892938638285025333403
                       , 34413065578016127815921815005561868836468420090470
                       , 23053081172816430487623791969842487255036638784583
                       , 11487696932154902810424020138335124462181441773470
                       , 63783299490636259666498587618221225225512486764533
                       , 67720186971698544312419572409913959008952310058822
                       , 95548255300263520781532296796249481641953868218774
                       , 76085327132285723110424803456124867697064507995236
                       , 37774242535411291684276865538926205024910326572967
                       , 23701913275725675285653248258265463092207058596522
                       , 29798860272258331913126375147341994889534765745501
                       , 18495701454879288984856827726077713721403798879715
                       , 38298203783031473527721580348144513491373226651381
                       , 34829543829199918180278916522431027392251122869539
                       , 40957953066405232632538044100059654939159879593635
                       , 29746152185502371307642255121183693803580388584903
                       , 41698116222072977186158236678424689157993532961922
                       , 62467957194401269043877107275048102390895523597457
                       , 23189706772547915061505504953922979530901129967519
                       , 86188088225875314529584099251203829009407770775672
                       , 11306739708304724483816533873502340845647058077308
                       , 82959174767140363198008187129011875491310547126581
                       , 97623331044818386269515456334926366572897563400500
                       , 42846280183517070527831839425882145521227251250327
                       , 55121603546981200581762165212827652751691296897789
                       , 32238195734329339946437501907836945765883352399886
                       , 75506164965184775180738168837861091527357929701337
                       , 62177842752192623401942399639168044983993173312731
                       , 32924185707147349566916674687634660915035914677504
                       , 99518671430235219628894890102423325116913619626622
                       , 73267460800591547471830798392868535206946944540724
                       , 76841822524674417161514036427982273348055556214818
                       , 97142617910342598647204516893989422179826088076852
                       , 87783646182799346313767754307809363333018982642090
                       , 10848802521674670883215120185883543223812876952786
                       , 71329612474782464538636993009049310363619763878039
                       , 62184073572399794223406235393808339651327408011116
                       , 66627891981488087797941876876144230030984490851411
                       , 60661826293682836764744779239180335110989069790714
                       , 85786944089552990653640447425576083659976645795096
                       , 66024396409905389607120198219976047599490197230297
                       , 64913982680032973156037120041377903785566085089252
                       , 16730939319872750275468906903707539413042652315011
                       , 94809377245048795150954100921645863754710598436791
                       , 78639167021187492431995700641917969777599028300699
                       , 15368713711936614952811305876380278410754449733078
                       , 40789923115535562561142322423255033685442488917353
                       , 44889911501440648020369068063960672322193204149535
                       , 41503128880339536053299340368006977710650566631954
                       , 81234880673210146739058568557934581403627822703280
                       , 82616570773948327592232845941706525094512325230608
                       , 22918802058777319719839450180888072429661980811197
                       , 77158542502016545090413245809786882778948721859617
                       , 72107838435069186155435662884062257473692284509516
                       , 20849603980134001723930671666823555245252804609722
                       , 53503534226472524250874054075591789781264330331690]

followed by my Python solution:

#!/usr/bin/python
"""
code solution for project euler's problem #13 in python.
"""
from __future__ import print_function
 
def print_10(number):
    print(str(number)[0:10])
 
if __name__ == "__main__":
 
    big_number = [ 37107287533902102798797998220837590246510135740250,
                   46376937677490009712648124896970078050417018260538,
                   74324986199524741059474233309513058123726617309629,
                   91942213363574161572522430563301811072406154908250,
                   23067588207539346171171980310421047513778063246676,
                   89261670696623633820136378418383684178734361726757,
                   28112879812849979408065481931592621691275889832738,
                   44274228917432520321923589422876796487670272189318,
                   47451445736001306439091167216856844588711603153276,
                   70386486105843025439939619828917593665686757934951,
                   62176457141856560629502157223196586755079324193331,
                   64906352462741904929101432445813822663347944758178,
                   92575867718337217661963751590579239728245598838407,
                   58203565325359399008402633568948830189458628227828,
                   80181199384826282014278194139940567587151170094390,
                   35398664372827112653829987240784473053190104293586,
                   86515506006295864861532075273371959191420517255829,
                   71693888707715466499115593487603532921714970056938,
                   54370070576826684624621495650076471787294438377604,
                   53282654108756828443191190634694037855217779295145,
                   36123272525000296071075082563815656710885258350721,
                   45876576172410976447339110607218265236877223636045,
                   17423706905851860660448207621209813287860733969412,
                   81142660418086830619328460811191061556940512689692,
                   51934325451728388641918047049293215058642563049483,
                   62467221648435076201727918039944693004732956340691,
                   15732444386908125794514089057706229429197107928209,
                   55037687525678773091862540744969844508330393682126,
                   18336384825330154686196124348767681297534375946515,
                   80386287592878490201521685554828717201219257766954,
                   78182833757993103614740356856449095527097864797581,
                   16726320100436897842553539920931837441497806860984,
                   48403098129077791799088218795327364475675590848030,
                   87086987551392711854517078544161852424320693150332,
                   59959406895756536782107074926966537676326235447210,
                   69793950679652694742597709739166693763042633987085,
                   41052684708299085211399427365734116182760315001271,
                   65378607361501080857009149939512557028198746004375,
                   35829035317434717326932123578154982629742552737307,
                   94953759765105305946966067683156574377167401875275,
                   88902802571733229619176668713819931811048770190271,
                   25267680276078003013678680992525463401061632866526,
                   36270218540497705585629946580636237993140746255962,
                   24074486908231174977792365466257246923322810917141,
                   91430288197103288597806669760892938638285025333403,
                   34413065578016127815921815005561868836468420090470,
                   23053081172816430487623791969842487255036638784583,
                   11487696932154902810424020138335124462181441773470,
                   63783299490636259666498587618221225225512486764533,
                   67720186971698544312419572409913959008952310058822,
                   95548255300263520781532296796249481641953868218774,
                   76085327132285723110424803456124867697064507995236,
                   37774242535411291684276865538926205024910326572967,
                   23701913275725675285653248258265463092207058596522,
                   29798860272258331913126375147341994889534765745501,
                   18495701454879288984856827726077713721403798879715,
                   38298203783031473527721580348144513491373226651381,
                   34829543829199918180278916522431027392251122869539,
                   40957953066405232632538044100059654939159879593635,
                   29746152185502371307642255121183693803580388584903,
                   41698116222072977186158236678424689157993532961922,
                   62467957194401269043877107275048102390895523597457,
                   23189706772547915061505504953922979530901129967519,
                   86188088225875314529584099251203829009407770775672,
                   11306739708304724483816533873502340845647058077308,
                   82959174767140363198008187129011875491310547126581,
                   97623331044818386269515456334926366572897563400500,
                   42846280183517070527831839425882145521227251250327,
                   55121603546981200581762165212827652751691296897789,
                   32238195734329339946437501907836945765883352399886,
                   75506164965184775180738168837861091527357929701337,
                   62177842752192623401942399639168044983993173312731,
                   32924185707147349566916674687634660915035914677504,
                   99518671430235219628894890102423325116913619626622,
                   73267460800591547471830798392868535206946944540724,
                   76841822524674417161514036427982273348055556214818,
                   97142617910342598647204516893989422179826088076852,
                   87783646182799346313767754307809363333018982642090,
                   10848802521674670883215120185883543223812876952786,
                   71329612474782464538636993009049310363619763878039,
                   62184073572399794223406235393808339651327408011116,
                   66627891981488087797941876876144230030984490851411,
                   60661826293682836764744779239180335110989069790714,
                   85786944089552990653640447425576083659976645795096,
                   66024396409905389607120198219976047599490197230297,
                   64913982680032973156037120041377903785566085089252,
                   16730939319872750275468906903707539413042652315011,
                   94809377245048795150954100921645863754710598436791,
                   78639167021187492431995700641917969777599028300699,
                   15368713711936614952811305876380278410754449733078,
                   40789923115535562561142322423255033685442488917353,
                   44889911501440648020369068063960672322193204149535,
                   41503128880339536053299340368006977710650566631954,
                   81234880673210146739058568557934581403627822703280,
                   82616570773948327592232845941706525094512325230608,
                   22918802058777319719839450180888072429661980811197,
                   77158542502016545090413245809786882778948721859617,
                   72107838435069186155435662884062257473692284509516,
                   20849603980134001723930671666823555245252804609722,
                   53503534226472524250874054075591789781264330331690]
 
    print_10(sum(big_number))

and to continue adding in the spice, I have included a solution in Scala:

import BigInt._
 
object problem_13 {
    def main (args : Array[String]){
        val big_number = List("37107287533902102798797998220837590246510135740250",
                              "46376937677490009712648124896970078050417018260538",
                              "74324986199524741059474233309513058123726617309629",
                              "91942213363574161572522430563301811072406154908250",
                              "23067588207539346171171980310421047513778063246676",
                              "89261670696623633820136378418383684178734361726757",
                              "28112879812849979408065481931592621691275889832738",
                              "44274228917432520321923589422876796487670272189318",
                              "47451445736001306439091167216856844588711603153276",
                              "70386486105843025439939619828917593665686757934951",
                              "62176457141856560629502157223196586755079324193331",
                              "64906352462741904929101432445813822663347944758178",
                              "92575867718337217661963751590579239728245598838407",
                              "58203565325359399008402633568948830189458628227828",
                              "80181199384826282014278194139940567587151170094390",
                              "35398664372827112653829987240784473053190104293586",
                              "86515506006295864861532075273371959191420517255829",
                              "71693888707715466499115593487603532921714970056938",
                              "54370070576826684624621495650076471787294438377604",
                              "53282654108756828443191190634694037855217779295145",
                              "36123272525000296071075082563815656710885258350721",
                              "45876576172410976447339110607218265236877223636045",
                              "17423706905851860660448207621209813287860733969412",
                              "81142660418086830619328460811191061556940512689692",
                              "51934325451728388641918047049293215058642563049483",
                              "62467221648435076201727918039944693004732956340691",
                              "15732444386908125794514089057706229429197107928209",
                              "55037687525678773091862540744969844508330393682126",
                              "18336384825330154686196124348767681297534375946515",
                              "80386287592878490201521685554828717201219257766954",
                              "78182833757993103614740356856449095527097864797581",
                              "16726320100436897842553539920931837441497806860984",
                              "48403098129077791799088218795327364475675590848030",
                              "87086987551392711854517078544161852424320693150332",
                              "59959406895756536782107074926966537676326235447210",
                              "69793950679652694742597709739166693763042633987085",
                              "41052684708299085211399427365734116182760315001271",
                              "65378607361501080857009149939512557028198746004375",
                              "35829035317434717326932123578154982629742552737307",
                              "94953759765105305946966067683156574377167401875275",
                              "88902802571733229619176668713819931811048770190271",
                              "25267680276078003013678680992525463401061632866526",
                              "36270218540497705585629946580636237993140746255962",
                              "24074486908231174977792365466257246923322810917141",
                              "91430288197103288597806669760892938638285025333403",
                              "34413065578016127815921815005561868836468420090470",
                              "23053081172816430487623791969842487255036638784583",
                              "11487696932154902810424020138335124462181441773470",
                              "63783299490636259666498587618221225225512486764533",
                              "67720186971698544312419572409913959008952310058822",
                              "95548255300263520781532296796249481641953868218774",
                              "76085327132285723110424803456124867697064507995236",
                              "37774242535411291684276865538926205024910326572967",
                              "23701913275725675285653248258265463092207058596522",
                              "29798860272258331913126375147341994889534765745501",
                              "18495701454879288984856827726077713721403798879715",
                              "38298203783031473527721580348144513491373226651381",
                              "34829543829199918180278916522431027392251122869539",
                              "40957953066405232632538044100059654939159879593635",
                              "29746152185502371307642255121183693803580388584903",
                              "41698116222072977186158236678424689157993532961922",
                              "62467957194401269043877107275048102390895523597457",
                              "23189706772547915061505504953922979530901129967519",
                              "86188088225875314529584099251203829009407770775672",
                              "11306739708304724483816533873502340845647058077308",
                              "82959174767140363198008187129011875491310547126581",
                              "97623331044818386269515456334926366572897563400500",
                              "42846280183517070527831839425882145521227251250327",
                              "55121603546981200581762165212827652751691296897789",
                              "32238195734329339946437501907836945765883352399886",
                              "75506164965184775180738168837861091527357929701337",
                              "62177842752192623401942399639168044983993173312731",
                              "32924185707147349566916674687634660915035914677504",
                              "99518671430235219628894890102423325116913619626622",
                              "73267460800591547471830798392868535206946944540724",
                              "76841822524674417161514036427982273348055556214818",
                              "97142617910342598647204516893989422179826088076852",
                              "87783646182799346313767754307809363333018982642090",
                              "10848802521674670883215120185883543223812876952786",
                              "71329612474782464538636993009049310363619763878039",
                              "62184073572399794223406235393808339651327408011116",
                              "66627891981488087797941876876144230030984490851411",
                              "60661826293682836764744779239180335110989069790714",
                              "85786944089552990653640447425576083659976645795096",
                              "66024396409905389607120198219976047599490197230297",
                              "64913982680032973156037120041377903785566085089252",
                              "16730939319872750275468906903707539413042652315011",
                              "94809377245048795150954100921645863754710598436791",
                              "78639167021187492431995700641917969777599028300699",
                              "15368713711936614952811305876380278410754449733078",
                              "40789923115535562561142322423255033685442488917353",
                              "44889911501440648020369068063960672322193204149535",
                              "41503128880339536053299340368006977710650566631954",
                              "81234880673210146739058568557934581403627822703280",
                              "82616570773948327592232845941706525094512325230608",
                              "22918802058777319719839450180888072429661980811197",
                              "77158542502016545090413245809786882778948721859617",
                              "72107838435069186155435662884062257473692284509516",
                              "20849603980134001723930671666823555245252804609722",
                              "53503534226472524250874054075591789781264330331690") map {BigInt(_)}
        val sums = big_number sum
        val su = sums toString
        val su10 = su take 10
        println(su10)
    }
}

Some of you may be wondering, “Why a Scala solution?” To which I respond, “Why not?” Because that's a little short, I'll add that it has something to do with Scala starting to gain traction in the industry and me seeing if I would like to get paid to program in it.

The solution, in all three languages, is pretty simple. The recipe essentially says, “Put all numbers into a list. Get the sum of that list, turn that number into a string, and get the first 10 characters of that string.”

Times:
Haskell (compiled) : real 0m0.004s
Haskell (runghc) : real 0m0.314s
Python : real 0m0.059s
Scala (compiled) : real 0m0.757s

For the most part it's pretty standard in these tests to see performance times such that Haskell (compiled) < Python < Haskell (runghc). Java and Perl usually fall somewhere between the Haskell (compiled) and Python, in that order. To see Scala be 2x slower than Haskell (runghc) was a shocker. The only thing that makes sense to me for the slowdown is having to use the BigInt library. That is probably the biggest thing I took away from these time tests - if I want to do REALLY large number crunching and performance DOES matter, JVM-based languages might not be the best option.

A few thoughts on Scala:
If I haven't stated it already in this blog, I should now give the disclaimer that I'm not a Java fan. I know it still has its loyal followers, but I'm not one of them. Moving on. This was my first time working with Scala, and I'd like to finally welcome Java to the 21st century. While doing some research on the Scala language itself I read that “the industry” was moving to replace Java with Scala. I welcome that change. Does that mean I “like” Scala? The honest answer is, to butcher the quote the appliances from the Flintstones, “Eh, it's a language.” Scala is definitely an improvement over Java – not really that hard to do in my opinion – but, the language still feels unpolished. One quick way to kill the interpreter in Scala is to type “Int” then hit the enter key. Instead of error-ing out, the interpreter does a great job of interpreting a crash test car hitting a cement wall (I had to restart the whole thing.) When I tried the same “technique” in the Python interpreter, I got as a response and for Haskell's interpreter I received “Not in scope: data constructor `Int'”. I also found Scala's function composition to be a little lacking when compared to Haskell. I wasn't able to cleanly change the BigInt data type to String, and then only print out ten characters without requiring three separate val's. Yes, I could have used one var instead, but that's beside the point. I will admit it could be my inexperience with the language showing, so if anyone knows a smoother way to do this in Scala please share it in the comments.

All that being said, I do like the way Scala is trying to handle the reducing of Java's dot notation, and I think it's starting to make strides in the right direction in other areas. I'm open to working with Scala more, and look forward to seeing how it evolves over the next few years.

Apache Log IP Counting

Bryce — Tue, 08 May 2012 15:55:38 +0000

It all started with a simple question: “Which single IP shows up the most in an apache log file?” To which I ultimately came up with an answer using a string of Bash commands:

less apache_log | cut -d '-' -f 1 | sort -r | uniq -c

This produced some text displaying how many times various IP addresses made requests from an apache web server. After seeing the results and thinking for a moment, I remembered that there is a “new” data type – as of Python 2.7 and new to me at least – called “Counter” within the collections module in the standard library that would allow me to recreate this in Python. So I quickly whipped up the code below:

#!/usr/bin/env python
 
from sys import argv
from collections import Counter
 
if __name__ == "__main__":
    with open(argv[1]) as f:
        c = Counter(i.partition("-")[0] for i in f)
 
    for k,v in c.most_common():
        print '{:>4} {}'.format(v,k)

VIOLA! I get the same results as if I'd done it in Bash. Of course, like the madman I am, I wasn't happy to just stop at Python; I had to write this up in Haskell too. So I said “damn the torpedoes,” fired up my favorite text editor, and started to hack and slash my way toward a third version. After much documentation reading, internet searching, and trial and error I can proudly proclaim, “MISSION ACCOMPLISHED”:

module Main where
 
import System.Environment (getArgs)
import qualified Data.Text as T hiding (map, head, zip)
import qualified Data.Text.IO as TI (readFile)
import Data.Map hiding (map)
 
type Counter = (T.Text, Int)
 
mapUnpack :: Counter -> String
mapUnpack (k,v) = show v ++ " " ++ T.unpack k
 
sortMapByValue :: Map T.Text Int -> [Counter]
sortMapByValue = rqsort . toList
 
-- copied & modified by LYHGG in the recusion chapter
-- doing in reverse order as to better suit the output
rqsort :: [Counter] -> [Counter]
rqsort [] = []
rqsort ((k,v):xs) =
    let smallerSorted = rqsort [(k',v') | (k',v') <- xs, v' <= v]
        biggerSorted  = rqsort [(k',v') | (k',v') <- xs, v' > v]
    in biggerSorted ++ [(k,v)] ++ smallerSorted
 
main :: IO ()
main = do
    results <- getArgs >>= TI.readFile . head
    let results' = map (\x -> T.replace space nothing $ head $ T.splitOn dash x) $ T.lines results
    let results'' = fromListWith (+) . zip results' $ repeat (1 :: Int)
    mapM_ (print . mapUnpack) $ sortMapByValue results''
    where dash    = T.pack "-"
          space   = T.pack " "
          nothing = T.pack ""

The Haskell implementation took me longer than I expected as there were a couple of challenges to figure out:
1) Learning the Data.Map datatype and figuring out how to build that datatype from a list of IP addresses.
2) Sorting the Map by value and not by key.
3) Unpacking the Map to be printed.

The first problem was solved by a lucky internet search that showed me an example of how to use the 'fromListWith' function. This function performed the heavy lifting of sorting and counting the IP addresses in the log file. For the sorting by value instead of by key problem I was able to construct my own solution by tweaking the quicksort example from Learn You a Haskell. The changes I made expanded the tuple, allowing it to compare values and sort them in descending order. For the text holding and manipulation involved in Map unpacking, I've been told by other Haskellers that Data.Text is “the way to go” (as the default String implementation is a little slow and lacking features). While Data.Text did provide me an easy way to split the string and grab the IP addresses, it also required translating the IP addresses back into a String data type before Haskell would print it. Thus my need for a specific function to create a string based on each item in the Map. In the grand scheme of things having to write the mapUnpack function wasn't horrible...it was just one more hoop that I had to jump through before I could call this project complete. After these modifications I was able to put this program together without TOO much hassle, and in the end got the exact same results as both the Bash string and the Python program.

Would I recommend writing these scripts for work instead of using the string of Bash commands? No, especially if you're asked this question in a high-stress situation. However, these little personal challenges were a great way to expand my programming skills, particularly in learning about new libraries like the collections module in Python and the Data.Map module in Haskell. Having this random new knowledge might not seem worthwhile upfront, but might come in handy in the future if I ever encounter a problem that simple strings of Bash commands can't handle.

Connect 4

Bryce — Thu, 19 Apr 2012 23:58:45 +0000

A couple of weeks ago I was lucky enough to have my employer send me to PyCon. If you weren't at PyCon you missed out on a lot of things...like the invading squirrel hordes. Thankfully, all of the talks are viewable here. But PyCon is not the focus of this post, just a starting point. At PyCon, in the vendor area, there was the Thumbtack booth. The guys at this book weren't doing the “normal” conference thing (passing out schwag to every being, living or dead, that passed them); they actually made people work for their swag. Thumbtack had a programming challenge that you had to submit a solution to before they would give you either a large shot glass or a glass beer stein.
The challenge was to accept a list of lists from standard input, and parse it looking for a winner in a game of Connect 4. I believe this could be a great interview question, and will be using it for the upcoming interviews where I work. One of the reasons for this is that it's deceptively difficult. While we as humans have been conditioned to recognize patterns since birth, computers need to be taught every step from the beginning. How do I go about teaching something that I don't remember learning? But enough of my babbling - let's look at my solution:

#!/usr/bin/env python
 
from __future__ import print_function
import sys
 
def char_check(row, col, char, prev_row=0, prev_col=0, count=0, direction=0):
    direction_dict = {1: None,
                      2: None,
                      3: None,
                      4: lambda: char_check(row, col - 1, char, row, col, count + 1, 4),
                      5: None,
                      6: lambda: char_check(row, col + 1, char, row, col, count + 1, 6),
                      7: lambda: char_check(row + 1, col - 1, char, row, col, count + 1, 7),
                      8: lambda: char_check(row + 1, col, char, row, col, count + 1, 8),
                      9: lambda: char_check(row + 1, col + 1, char, row, col, count + 1, 9)}
 
    if count == 3:
        print("Winner: %s" % char)
        sys.exit(0)
 
    direction_list = []
    direction_list_append = direction_list.append
 
    try:
        if (four_list[row][col - 1] == char and 
            (row != prev_row or (col - 1) != prev_col) and 
            direction in (0,4)): 
            direction_list_append(4)
        elif (four_list[row][col + 1] == char and 
              (row != prev_row or (col + 1) != prev_col) and
              direction in (0,6)):
              direction_list_append(6)
        elif (four_list[row + 1][col - 1] == char and 
              ((row + 1) != prev_row or (col - 1) != prev_col) and
              direction in (0,7)):
              direction_list_append(7)
        elif (four_list[row + 1][col] == char and
              ((row + 1) != prev_row or col != prev_col) and
              direction in (0,8)):
              direction_list_append(8)
        elif (four_list[row + 1][col + 1] == char and
              ((row + 1) != prev_row or (col + 1) != prev_col) and
              direction in (0,9)):
              direction_list_append(9)
 
        for d in direction_list:
            direction_dict[d]()
 
    except IndexError:
        pass
 
if __name__ == "__main__":
    try:
        four_list = eval(sys.stdin.read())
    except SyntaxError:
        print("Error getting list from the web, using preprogrammed backup.")
        four_list = [
                        [".", ".", ".", ".", ".", ".", "."],
                        [".", ".", ".", ".", ".", ".", "."],
                        [".", ".", "O", ".", ".", ".", "."],
                        [".", ".", "X", "O", "X", "X", "."],
                        [".", ".", "X", "X", "O", "O", "X"],
                        [".", ".", "O", "X", "X", "O", "X"]
                    ]
    finally:
        for r,_ in enumerate(four_list):
            [char_check(r, col, four_list[r][col]) for col,_ in enumerate(four_list[r]) if four_list[r][col] != "."]
 
        print("No Winner")

Maybe it's my preference for functional programming coming out, but when I looked at this problem I thought “recursion,” remembering from college how much easier it is to solve the Tower of Hanoi problem with recursion than without. The problem became a little more complicated when I went from solving the original example to generating and testing a different board.

At the moment I'm trying to figure out a Haskell version of this solution. Hopefully I'll have one soon and I'll update this page when I do.

Before I posted this, I wrote a quick email to the person I spoke to at the Thumbtack booth and sent him my solution. He thanked me for the solution and requested my address to mail a mug to me, which showed up in the mail couple of days ago. (Below is a pic of the mug filled with a beautiful amber beer.) He also sent me a link to the company's blog post about their experiences using a coding challenge to earn schwag. Here is the link. There are also some pretty impressive solutions to the challenge there, including one done in regular expressions, which deserves a tip of the hat in my book.