Project Euler: Problem 13

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:

1
2
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):

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
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:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#!/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))

Scala:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
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.

Comments !

social