ScrollingText

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.

PyCon

Bryce — Thu, 08 Mar 2012 04:52:19 +0000

Hey Everybody, I will be attending the US PyCon starting tomorrow. If anyone of my readers are in town for the convention and are interested, I would happily meet up with you for drinks, food, or whatever. Send me a tweet.

Project Euler: Problem 12

Bryce — Mon, 05 Mar 2012 17:57:49 +0000

It’s time once again for a favorite blog theme, The Project Euler post. This time around I am answering problem twelve. The website states the problem as:
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

o spice things up I decided to use a language I haven't used for these in a while, Perl. I also included the usual suspects: Python and Haskell. So, here's the Perl code:

#!/usr/bin/perl
 
use strict;
use warnings;
 
my $index = 7;
my $total = 28;
my $divisors = 0;
 
sub divisors
{
    my ($number) = @_;
    my $sq_n = sqrt($number);
    my $i = 1;
    my $t = 0;
 
    while ($i <= $sq_n)
    {
        $t += 2 unless ($number % $i);
 
        $i += 1;
    }
 
    return $t;
}
 
while( divisors($total) <= 500)
{
    $index += 1;
    $total += $index;
}
 
print "$total\n";

Nothing really new or interesting to mention in this code. Here is the Python code:

#!/usr/bin/python
 
"""
solution for problem 12 in python.
"""
import math
 
def get_divisors(number):
    tlist = []
    for x in xrange(2, int(math.sqrt(number))):
        d,r = divmod(number,x)
        if r == 0:
            tlist.append(x)
            tlist.append(d)
 
    return len([1, number] + tlist)
 
def triangle_nums():
    iterator = 7
    num = 28
 
    while True:
        yield num
        iterator += 1
        num += iterator
 
if __name__ == "__main__":
    tn = triangle_nums()
    for t in tn:
        tl = get_divisors(t)
        if tl > 500:
            print "num: %d\ncount: %d" % (t,tl)
            break

Pretty standard stuff for the most part. I think the only non-standard thing worth mentioning is the infinite triangle number generator. This took a little finangling, but I got it to work in the end.

Here is the Haskell code:

module Main where
 
get_div_len number = foldl1 (+) [2 | x <- [1..x], number `mod` x == 0]
    where x = round . sqrt $ fromInteger number
 
main :: IO()
main = do
  print . head $ dropWhile (\x -> fst x <= 499) (map (\x -> (get_div_len x ,x)) xs)
  where xs = map (\y -> sum [1..y]) [7..]

After creating these solutions, I did my usual, highly accurate, testing method to determine the speed of the computation. I was surprised by my results:

Perl: 12.462s
Python: 17.783s
Haskell (compiled): 13.877s

Normally the Haskell solution would be significantly faster, and I have a theory as to why the Haskell times are so close. In Perl and Python I’m doing two additions – one for the increase of the index number and another to increase the total number. In Haskell I’m doing 1 + n additions; the first is to increase the index, and the remaining additions (n) are those used to calculate the sum of all the numbers between (and including) 1 and the index. As the index variable gets larger, that calculation takes more and more time to perform. I would write this up as suboptimal. After spending some time traveling “the tubes,” I discovered the State Monad, which is the reason why this blog post took me so long. I had to spend a week going through random blogs, skimming books, and beating my head against a wall (more than usual) to figure this out.

Quick diversion, for those of you who do not know what the State Monad is, let me take a moment to to try and explain what it is and why it’s important in this context. Those of us that come from an imperative language (I am one of you in this regard) are used to being able to do a simple addition such as (in pseudo code):

Variable = 2
Variable = variable + 3 or Variable += 3

We can’t do this in Haskell; instead we have to create a new variable name for each new variable assignment. We could also create a function that recursively goes forward, generating the next number in the sequence and bringing our needed variables with us before going deeper down the recursion rabbit hole. With the State Monad, however, we can write our function in such a way that the necessary variables are implicitly passed. Take a look at the new solution to see what I mean:

{-# LANGUAGE BangPatterns, UnboxedTuples #-}
module Main where
 
import Control.Monad
import Control.Monad.State
 
type MyState = (Int, Int)
s0 = (7, 28)
 
tick = do
    (n,o) <- get
    let divs = getDivLen (n,o)
    if divs <= 500
        then do
            let n' = n + 1
            let o' = o + n'
            put (n', o')
            tick
        else
            return o
 
getDivLen :: MyState -> Int
getDivLen (!n, !o) = foldl1 (+) [2 | x <- [1..x], o `mod` x == 0]
    where x = round . sqrt $ fromIntegral o
 
main :: IO ()
main = print $ evalState tick s0

The tick function does not have any input parameters. All the information that the function needs comes from the “get” function call, which grabs the current state from the State Monad. If the tick function does not find a number of divisors greater than five hundred, it inserts new values back into the State Monad, and goes down to the next level of recursion.

It took me a long time to figure this out, mostly because of the lack of examples on the internet concerning the State Monad. If I wanted to create a random number generator I would have been set, but sadly I just wanted to create something that would hold a tuple of numbers and increment them accordingly. So I highly modified one of the “random number generator” examples.

My “highly accurate” speed test results for the new version is:
Haskell (compiled): 2.664s

which is a vast improvement (> 11s) over the previous implementation.

While a Project Euler problem may not have been the best way to learn about using the State Monad, I'm glad I stumbled upon it. I hope that it can be used as an example for others if they want to learn how to use the this particular monad to create things other than pseudo-random number generators.

One last thing – some of the brighter crayons in the box (which is most of you, based on the level of comments that I receive) might have noticed that I skipped problem 11. There is a simple response to that. I still haven’t solved it.

De Morgan’s and (un)Pythonic code

Bryce — Tue, 17 Jan 2012 22:54:06 +0000

The term “Pythonic” is a subjective and ambiguous one. There are plenty of sites on the internet that try to explain what it means. Some of the better sties will even tell you why one way of doing something is better than another. I am adding my scrollingtext to the latter list.

I believe that one of the key requirements for writing pythonic code is readability, as briefly mentioned in “The Zen of Python” by Tim Peters. I also believe that this little poem (I use that term loosely here) gives some pretty good hints on how to write pythonic code. (This is for more of the thought process outside the general coding style stuff defined in PEP-8). Here is the Zen of Python:

“Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!”

Since this post is about pythonic code, I want to take a quick moment to show you what I mean, saving you a google search or two in the process. Here is a class method that I would consider non-pythonic code:

def inNodeExistInPool(self, poolName, nodeName):
    try:
        currentNodes = self.__getNodesInPool(poolName)
        if currentNodes:
            for n in currentNodes:
        	if n == nodeName:
        	    return True
            return False
    except Exception, e:
        raise Exception('Exception in isNodeExistInPool: ' + poolName +
                        ', Node: ' + nodeName + ', Error: ' + str(e))

Now here is a more pythonic version of the same code:

def isNodeExistInPool(self, poolName, nodeName):
    try:
        if nodeName in self.__getNodesInPool(poolName):
            return True
        else:
            return False
    except Exception, e:
        raise Exception('Exception in isNodeExistInPool: %s, Node: %s, Error: ' %
                       (poolName, nodeName, str(e)))

While the first version of the code above is not wrong and would probably be the correct way to do this in other programming languages, it’s not the best way to do it in python. (I also expect to see quite a few comments on how other python programmers might improve the first or second versions of these functions.)

Now that we have that little example out of the way, let me share with you the motivation for this blog post. At work one day I saw some code that looked like this:

# ‘a’ being an instance of a class
if  not a.att1 and not a.att2 and not a.att3 and not a.att4:
    # more code down here

oddly enough, I remembered De Morgan’s Law from my formal logic courses, so I used it to simplify the expression. Here is the proof (in formal logic notation because it’s quicker):

~P ^ ~Q ^ ~R ^ ~S
(~P ^ ~Q) ^ (~R ^ ~S)
~(P v Q) ^ ~(R v S)
(~(P v Q) ^ ~(R v S))
~((P v Q) v (R v S))
~(P v Q v R v S)

After the logic juggling above I renamed the variables and then modified the code to resemble the ending result:

if not (a.att1 or a.att2 or a.att3 or a.att4):
    # still more code down here

After the change we can immediately see that I’ve reduced number of not calls. While I’m sure there is some performance improvement, I seriously doubt that it’s something that might be noticed by a human being, so we’ll just discount this as any form of optimization. I believe I’ve also made the code easier to read. The line itself is smaller, so a maintainer would have less “things” to juggle in their head to verify that the expression should pass or fail. Thus this code change has fulfilled some of the ideas in the “Zen of Python,” particularly the parts about “Simple is better than complex,” and “Readability counts.” However, in the final product I’ve had to add some parentheses in order for the logic to be correct, and this is where my ultimate question lies. In a lot of “pythonic” code examples on the web, one doesn’t really see “if” statements written like this one. So a somewhat self-conscious part of me thinks that I even though I have gone through the trouble of trying to make the code cleaner, I still haven’t gotten the code to be “pythonic”.

After thinking about it a little more, I decided that my version is pythonic. While I did add some clutter by adding parentheses, I also removed 3 “not calls” and made the line easier to understand. I believe this follows the spirit of pythonic code, even if it does not follow the the code to the letter.

Top photo credit goes to: mromtz

Pangrams

Bryce — Thu, 29 Dec 2011 17:30:30 +0000

If you haven’t figured it out by now, I enjoy solving problems. And over the course of the last year or two, I’ve learned that interview questions make for great problems to work on. Actual interview problems are nice because they are usually quick, but have a quirk or two in there that makes them challenging, unlike simple questions like the Fizz Buzz problem that just checks if you have the most basic coding skills. (Has anyone actually been asked that question in an interview?)

The most recent problem I got to sink my teeth into (found it on a recruiting site, but not going to share where I got it; wouldn’t be fair to the company posting the problem) is for finding pangrams in sentences. If you don’t know what a pangram is Wikipedia defines them as, “a sentence using every letter of the alphabet at least once.” Yeah, I didn’t know what they were either until I started programming this little puzzle. Here is the code:

module Main (main) where
 
import System (getArgs)
import qualified Data.Set as S
import qualified Data.Text as T
import qualified Data.Text.IO as TI (readFile)
 
buildList :: FilePath -> IO [T.Text]
buildList filename = TI.readFile filename >>=
    return . map (T.toLower . T.filter (/=' ')) . T.lines 
 
compareAndPrint :: S.Set Char -> String
compareAndPrint sset = if S.null result
                       then "NULL"
                       else S.toList result
  where result = S.difference (S.fromList ['a'..'z']) sset
 
main = do
  args <- getArgs
  sentences <- buildList $ head args
  mapM_  (putStrLn . compareAndPrint) $ map( S.fromList . T.unpack) sentences

I came up with the solution pretty quickly by using Sets. Having a set of the alphabet and finding the difference of the letters used in the sentence makes the problem almost trivial. The hard part for me was figuring out how to filter out the spaces and change all characters to lower case in the buildList function. I eventually figured it out, but it took some head against wall action to get it right.

This is going to be my last post for this year. I would like to wish you all Happy Holidays and a Happy New Year. Thank for reading and see you again in 2012. I would also like to thank everyone from planet.haskell.org who decided to read this. Welcome!

99 bottles

Bryce — Tue, 06 Dec 2011 01:33:14 +0000

It’s been a while since I put up one of these simple code posts. Let me fix that. :P

Quiet a while ago, this code needed to have the dust blown off of it. Programming Praxis had its readers program out the song for “Nintey-Nine Bottles of Beer on the Wall".

Here is my version of it:

#!/usr/bin/env python
 
from __future__ import print_function
 
def output(in_int):
    if in_int != 1:
        return "%d bottles of beer on the wall, %d bottles of beer." \
                "You take one down, pass it around, %d bottles of beer" \
                "on the wall." % (in_int,in_int, in_int - 1)
    else:
        return "%d bottle of beer on the wall, %d bottle of beer." \
                "You take one down, pass it around, %d bottles of beer" \
                "on the wall." % (in_int,in_int, in_int - 1)
 
if __name__ == "__main__":
    [ print(output(x)) for x in reversed(xrange(1,99)) ]

That’s all there is to it really. The only enlightening thing about this I can say is that this algorithm reminds me a lot of my Code to lyrics post I wrote a little over a year ago. It’s amazing how simple songs are when they’re broken down to their basic elements. Anyone feel like setting up an “automatic song generation” business with me?

Git Churn

Bryce — Tue, 01 Nov 2011 16:36:10 +0000

I’m still really on the fence regarding the flame war between Git and Mercurial; they both have their strengths and weaknesses. (In case you’re wondering, the reason I haven’t been forced to make a decision yet is because $WORK uses Perforce .) When I learn about one trick in one of these tools, I try to see if that trick is possible in the other. So far this search has been pretty limited, and both applications seem to be equally capable.

My buddy OJ pointed me out to a Mercurial extension called churn, which is a pretty nifty tool. It allows you to quickly see who made how many changes to either a particular file or an entire repo (emails removed to avoid these people being spammed).

guido 1970354 *******************************************************************
jack.jansen 1665771 *********************************************************
solipsis 1588311 ******************************************************
georg 1331332 *********************************************
martin 1005541 **********************************
benjamin 697038 ************************
thomas 460885 ****************
christian 445461 ***************
fdrake 437229 ***************
tools 418957 **************

After finding out about this cool little feature I decided to see if Git had something similar. After a little digging around I came across this thread on StackOverflow(2) which talked about the Git shortlog command. Running this command with the “-sne” argument (as given from the StackOverflow page) on my Project Euler git repo returned these results:

129 Bryce Verdier
42 Bryce Verdier
4 Bryce
1 bryce

While there are mentions of the gitstats project, I didn’t want to bring that into the equation. I just want to compare the core applications. Using a third party application, like gitstats, wouldn’t be fair to Mercurial.

Seeing how both of these tools seemed to have similar capabilities, I decided to investigate a little more. I started off by trying to see if there might have been a flag to remove the stars from the Mercurial churn output; while the stars are cool, I think the Git output looks cleaner without them. Sadly, there isn’t a flag in churn to remove the stars.

One thing I did like about churn over Git shortlog was the ability to see either the number of lines changed or the number of change sets. I think that having more options for how you want information presented is a good thing. I also liked the output of churn over that of shortlog. I want to see the user information before I see the number of changes they made; I think it’s easier to process information that way than the other way around. Sadly, even though there is a quite a lot of documentation regarding formatting within the git log man page, there doesn’t seem to be a print variable for summarizing one’s commits. Or for changing the formatting if one uses the “-s” flag in the shortlog command.

As hard as I tried to break the tie between Git and Mercurial, these two particular extensions each have their own advantages and disadvantages. While it might be ideal to attempt to combine churn and shortlog into the ULTIMATE CHANGE TRACKING EXTENSION, that is a task for another day (and probably another programmer.) I guess the flame war between these two tools is just going to have to continue for a little while longer.

Programming Praxis: The Sum of Two Integers

Bryce — Wed, 05 Oct 2011 16:12:28 +0000

A couple of months ago the Programming Praxis website put up a challenge to find a sum inside an array of integers (the direct wording of the challenge can be found here) and since I’ve come up with my own solution, this little challenge has provided me with a lot of feedback.

Just to get some of the geeky stuff out of the way, here is the code I wrote for the problem:

import Data.List
import Data.Maybe
 
sumCheck :: Int -> [Int] -> [Int] -> Maybe (Int, Int)
sumCheck _ [] _ = Nothing
sumCheck total (x:xs) ys = if total' == Nothing 
                                then sumCheck total xs ys
                                else return (x, (ys !! ( fromJust total')))
                           where total' = (total - x) `elemIndex` ys

In thinking about the problem a little bit I came up with this subtraction approach. My first approach was to use addition and add every item in the array against all the other items. But this method didn’t sit well with me. After a little bike ride I came up with the code you see above.

After I wrote it, I submitted my code to the Haskell-beginners email list asking for critiques and possible enhancements. Arlen Cuss contributed a slight improvement of my code:

sumCheck total (x:xs) ys =
let diff = total - x
               in  if diff `elem` ys
                              then Just (x, diff)
                              else sumCheck total xs ys

And Adityz Siram contributed his version. Which is basically the first algorithm that I came up with and wanted to improve upon. His code is here:

sums i as bs = [(x,y) | x <- as, y <- bs, x + y == i]

Finally, Gary Klindt took all of our code snippets, used some performance analysis tools inside GHC and came up with some run times that are (hopefully) more accurate than running time on an application. Here are those stats:
print $ sumCheck 500 [1..1000] [1..1000]
sumCheck1: 58,648
sumCheck2: 58,484
sumCheck3: 70,016

print $ sumCheck 5000 [1..10000] [1..10000]
sumCheck1: 238,668
sumCheck2: 238,504
sumCheck3: 358,016
(unit: byte)

Out of the three code snippets, my function was in the middle, speed-wise. But I think that it’s also really nice to see how much better it is than the regular addition method. It’s also nice to see how the little change made to my code can improve the overall speed of the function.

At the end of the day I take a little bit of pride in myself for coming up with an improved algorithm for this task on my own. I know that on a hardware level, subtraction takes more time than addition. But I get the improvements I get because I reduce the number of additions and comparisons I have to make in order for the function to be complete. I also estimate the worst case speed for my algorithm to be O(n), which isn’t too shabby.

When I started learning Haskell, one of the things I read on the internet was how the people who programmed it were helpful to one another. I was skeptical when I first read that, but I have to say that all of my doubt has been removed. And it is interactions like this that make me glad to participate in a community as helpful as this one.