Haskell

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: “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. module Main where
  2.  
  3. main :: IO()
  4. main = do
  5. print . take 10 . show $ sum big_number
  6. where big_number = [ 37107287533902102798797998220837590246510135740250
  7. , 46376937677490009712648124896970078050417018260538
  8. , 74324986199524741059474233309513058123726617309629
  9. , 91942213363574161572522430563301811072406154908250
  10. , 23067588207539346171171980310421047513778063246676
  11. , 89261670696623633820136378418383684178734361726757
  12. , 28112879812849979408065481931592621691275889832738
  13. , 44274228917432520321923589422876796487670272189318
  14. , 47451445736001306439091167216856844588711603153276
  15. , 70386486105843025439939619828917593665686757934951
  16. , 62176457141856560629502157223196586755079324193331
  17. , 64906352462741904929101432445813822663347944758178
  18. , 92575867718337217661963751590579239728245598838407
  19. , 58203565325359399008402633568948830189458628227828
  20. , 80181199384826282014278194139940567587151170094390
  21. , 35398664372827112653829987240784473053190104293586
  22. , 86515506006295864861532075273371959191420517255829
  23. , 71693888707715466499115593487603532921714970056938
  24. , 54370070576826684624621495650076471787294438377604
  25. , 53282654108756828443191190634694037855217779295145
  26. , 36123272525000296071075082563815656710885258350721
  27. , 45876576172410976447339110607218265236877223636045
  28. , 17423706905851860660448207621209813287860733969412
  29. , 81142660418086830619328460811191061556940512689692
  30. , 51934325451728388641918047049293215058642563049483
  31. , 62467221648435076201727918039944693004732956340691
  32. , 15732444386908125794514089057706229429197107928209
  33. , 55037687525678773091862540744969844508330393682126
  34. , 18336384825330154686196124348767681297534375946515
  35. , 80386287592878490201521685554828717201219257766954
  36. , 78182833757993103614740356856449095527097864797581
  37. , 16726320100436897842553539920931837441497806860984
  38. , 48403098129077791799088218795327364475675590848030
  39. , 87086987551392711854517078544161852424320693150332
  40. , 59959406895756536782107074926966537676326235447210
  41. , 69793950679652694742597709739166693763042633987085
  42. , 41052684708299085211399427365734116182760315001271
  43. , 65378607361501080857009149939512557028198746004375
  44. , 35829035317434717326932123578154982629742552737307
  45. , 94953759765105305946966067683156574377167401875275
  46. , 88902802571733229619176668713819931811048770190271
  47. , 25267680276078003013678680992525463401061632866526
  48. , 36270218540497705585629946580636237993140746255962
  49. , 24074486908231174977792365466257246923322810917141
  50. , 91430288197103288597806669760892938638285025333403
  51. , 34413065578016127815921815005561868836468420090470
  52. , 23053081172816430487623791969842487255036638784583
  53. , 11487696932154902810424020138335124462181441773470
  54. , 63783299490636259666498587618221225225512486764533
  55. , 67720186971698544312419572409913959008952310058822
  56. , 95548255300263520781532296796249481641953868218774
  57. , 76085327132285723110424803456124867697064507995236
  58. , 37774242535411291684276865538926205024910326572967
  59. , 23701913275725675285653248258265463092207058596522
  60. , 29798860272258331913126375147341994889534765745501
  61. , 18495701454879288984856827726077713721403798879715
  62. , 38298203783031473527721580348144513491373226651381
  63. , 34829543829199918180278916522431027392251122869539
  64. , 40957953066405232632538044100059654939159879593635
  65. , 29746152185502371307642255121183693803580388584903
  66. , 41698116222072977186158236678424689157993532961922
  67. , 62467957194401269043877107275048102390895523597457
  68. , 23189706772547915061505504953922979530901129967519
  69. , 86188088225875314529584099251203829009407770775672
  70. , 11306739708304724483816533873502340845647058077308
  71. , 82959174767140363198008187129011875491310547126581
  72. , 97623331044818386269515456334926366572897563400500
  73. , 42846280183517070527831839425882145521227251250327
  74. , 55121603546981200581762165212827652751691296897789
  75. , 32238195734329339946437501907836945765883352399886
  76. , 75506164965184775180738168837861091527357929701337
  77. , 62177842752192623401942399639168044983993173312731
  78. , 32924185707147349566916674687634660915035914677504
  79. , 99518671430235219628894890102423325116913619626622
  80. , 73267460800591547471830798392868535206946944540724
  81. , 76841822524674417161514036427982273348055556214818
  82. , 97142617910342598647204516893989422179826088076852
  83. , 87783646182799346313767754307809363333018982642090
  84. , 10848802521674670883215120185883543223812876952786
  85. , 71329612474782464538636993009049310363619763878039
  86. , 62184073572399794223406235393808339651327408011116
  87. , 66627891981488087797941876876144230030984490851411
  88. , 60661826293682836764744779239180335110989069790714
  89. , 85786944089552990653640447425576083659976645795096
  90. , 66024396409905389607120198219976047599490197230297
  91. , 64913982680032973156037120041377903785566085089252
  92. , 16730939319872750275468906903707539413042652315011
  93. , 94809377245048795150954100921645863754710598436791
  94. , 78639167021187492431995700641917969777599028300699
  95. , 15368713711936614952811305876380278410754449733078
  96. , 40789923115535562561142322423255033685442488917353
  97. , 44889911501440648020369068063960672322193204149535
  98. , 41503128880339536053299340368006977710650566631954
  99. , 81234880673210146739058568557934581403627822703280
  100. , 82616570773948327592232845941706525094512325230608
  101. , 22918802058777319719839450180888072429661980811197
  102. , 77158542502016545090413245809786882778948721859617
  103. , 72107838435069186155435662884062257473692284509516
  104. , 20849603980134001723930671666823555245252804609722
  105. , 53503534226472524250874054075591789781264330331690]

followed by my Python solution:

  1. #!/usr/bin/python
  2. """
  3. code solution for project euler's problem #13 in python.
  4. """
  5. from __future__ import print_function
  6.  
  7. def print_10(number):
  8. print(str(number)[0:10])
  9.  
  10. if __name__ == "__main__":
  11.  
  12. big_number = [ 37107287533902102798797998220837590246510135740250,
  13. 46376937677490009712648124896970078050417018260538,
  14. 74324986199524741059474233309513058123726617309629,
  15. 91942213363574161572522430563301811072406154908250,
  16. 23067588207539346171171980310421047513778063246676,
  17. 89261670696623633820136378418383684178734361726757,
  18. 28112879812849979408065481931592621691275889832738,
  19. 44274228917432520321923589422876796487670272189318,
  20. 47451445736001306439091167216856844588711603153276,
  21. 70386486105843025439939619828917593665686757934951,
  22. 62176457141856560629502157223196586755079324193331,
  23. 64906352462741904929101432445813822663347944758178,
  24. 92575867718337217661963751590579239728245598838407,
  25. 58203565325359399008402633568948830189458628227828,
  26. 80181199384826282014278194139940567587151170094390,
  27. 35398664372827112653829987240784473053190104293586,
  28. 86515506006295864861532075273371959191420517255829,
  29. 71693888707715466499115593487603532921714970056938,
  30. 54370070576826684624621495650076471787294438377604,
  31. 53282654108756828443191190634694037855217779295145,
  32. 36123272525000296071075082563815656710885258350721,
  33. 45876576172410976447339110607218265236877223636045,
  34. 17423706905851860660448207621209813287860733969412,
  35. 81142660418086830619328460811191061556940512689692,
  36. 51934325451728388641918047049293215058642563049483,
  37. 62467221648435076201727918039944693004732956340691,
  38. 15732444386908125794514089057706229429197107928209,
  39. 55037687525678773091862540744969844508330393682126,
  40. 18336384825330154686196124348767681297534375946515,
  41. 80386287592878490201521685554828717201219257766954,
  42. 78182833757993103614740356856449095527097864797581,
  43. 16726320100436897842553539920931837441497806860984,
  44. 48403098129077791799088218795327364475675590848030,
  45. 87086987551392711854517078544161852424320693150332,
  46. 59959406895756536782107074926966537676326235447210,
  47. 69793950679652694742597709739166693763042633987085,
  48. 41052684708299085211399427365734116182760315001271,
  49. 65378607361501080857009149939512557028198746004375,
  50. 35829035317434717326932123578154982629742552737307,
  51. 94953759765105305946966067683156574377167401875275,
  52. 88902802571733229619176668713819931811048770190271,
  53. 25267680276078003013678680992525463401061632866526,
  54. 36270218540497705585629946580636237993140746255962,
  55. 24074486908231174977792365466257246923322810917141,
  56. 91430288197103288597806669760892938638285025333403,
  57. 34413065578016127815921815005561868836468420090470,
  58. 23053081172816430487623791969842487255036638784583,
  59. 11487696932154902810424020138335124462181441773470,
  60. 63783299490636259666498587618221225225512486764533,
  61. 67720186971698544312419572409913959008952310058822,
  62. 95548255300263520781532296796249481641953868218774,
  63. 76085327132285723110424803456124867697064507995236,
  64. 37774242535411291684276865538926205024910326572967,
  65. 23701913275725675285653248258265463092207058596522,
  66. 29798860272258331913126375147341994889534765745501,
  67. 18495701454879288984856827726077713721403798879715,
  68. 38298203783031473527721580348144513491373226651381,
  69. 34829543829199918180278916522431027392251122869539,
  70. 40957953066405232632538044100059654939159879593635,
  71. 29746152185502371307642255121183693803580388584903,
  72. 41698116222072977186158236678424689157993532961922,
  73. 62467957194401269043877107275048102390895523597457,
  74. 23189706772547915061505504953922979530901129967519,
  75. 86188088225875314529584099251203829009407770775672,
  76. 11306739708304724483816533873502340845647058077308,
  77. 82959174767140363198008187129011875491310547126581,
  78. 97623331044818386269515456334926366572897563400500,
  79. 42846280183517070527831839425882145521227251250327,
  80. 55121603546981200581762165212827652751691296897789,
  81. 32238195734329339946437501907836945765883352399886,
  82. 75506164965184775180738168837861091527357929701337,
  83. 62177842752192623401942399639168044983993173312731,
  84. 32924185707147349566916674687634660915035914677504,
  85. 99518671430235219628894890102423325116913619626622,
  86. 73267460800591547471830798392868535206946944540724,
  87. 76841822524674417161514036427982273348055556214818,
  88. 97142617910342598647204516893989422179826088076852,
  89. 87783646182799346313767754307809363333018982642090,
  90. 10848802521674670883215120185883543223812876952786,
  91. 71329612474782464538636993009049310363619763878039,
  92. 62184073572399794223406235393808339651327408011116,
  93. 66627891981488087797941876876144230030984490851411,
  94. 60661826293682836764744779239180335110989069790714,
  95. 85786944089552990653640447425576083659976645795096,
  96. 66024396409905389607120198219976047599490197230297,
  97. 64913982680032973156037120041377903785566085089252,
  98. 16730939319872750275468906903707539413042652315011,
  99. 94809377245048795150954100921645863754710598436791,
  100. 78639167021187492431995700641917969777599028300699,
  101. 15368713711936614952811305876380278410754449733078,
  102. 40789923115535562561142322423255033685442488917353,
  103. 44889911501440648020369068063960672322193204149535,
  104. 41503128880339536053299340368006977710650566631954,
  105. 81234880673210146739058568557934581403627822703280,
  106. 82616570773948327592232845941706525094512325230608,
  107. 22918802058777319719839450180888072429661980811197,
  108. 77158542502016545090413245809786882778948721859617,
  109. 72107838435069186155435662884062257473692284509516,
  110. 20849603980134001723930671666823555245252804609722,
  111. 53503534226472524250874054075591789781264330331690]
  112.  
  113. print_10(sum(big_number))

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

  1. import BigInt._
  2.  
  3. object problem_13 {
  4. def main (args : Array[String]){
  5. val big_number = List("37107287533902102798797998220837590246510135740250",
  6. "46376937677490009712648124896970078050417018260538",
  7. "74324986199524741059474233309513058123726617309629",
  8. "91942213363574161572522430563301811072406154908250",
  9. "23067588207539346171171980310421047513778063246676",
  10. "89261670696623633820136378418383684178734361726757",
  11. "28112879812849979408065481931592621691275889832738",
  12. "44274228917432520321923589422876796487670272189318",
  13. "47451445736001306439091167216856844588711603153276",
  14. "70386486105843025439939619828917593665686757934951",
  15. "62176457141856560629502157223196586755079324193331",
  16. "64906352462741904929101432445813822663347944758178",
  17. "92575867718337217661963751590579239728245598838407",
  18. "58203565325359399008402633568948830189458628227828",
  19. "80181199384826282014278194139940567587151170094390",
  20. "35398664372827112653829987240784473053190104293586",
  21. "86515506006295864861532075273371959191420517255829",
  22. "71693888707715466499115593487603532921714970056938",
  23. "54370070576826684624621495650076471787294438377604",
  24. "53282654108756828443191190634694037855217779295145",
  25. "36123272525000296071075082563815656710885258350721",
  26. "45876576172410976447339110607218265236877223636045",
  27. "17423706905851860660448207621209813287860733969412",
  28. "81142660418086830619328460811191061556940512689692",
  29. "51934325451728388641918047049293215058642563049483",
  30. "62467221648435076201727918039944693004732956340691",
  31. "15732444386908125794514089057706229429197107928209",
  32. "55037687525678773091862540744969844508330393682126",
  33. "18336384825330154686196124348767681297534375946515",
  34. "80386287592878490201521685554828717201219257766954",
  35. "78182833757993103614740356856449095527097864797581",
  36. "16726320100436897842553539920931837441497806860984",
  37. "48403098129077791799088218795327364475675590848030",
  38. "87086987551392711854517078544161852424320693150332",
  39. "59959406895756536782107074926966537676326235447210",
  40. "69793950679652694742597709739166693763042633987085",
  41. "41052684708299085211399427365734116182760315001271",
  42. "65378607361501080857009149939512557028198746004375",
  43. "35829035317434717326932123578154982629742552737307",
  44. "94953759765105305946966067683156574377167401875275",
  45. "88902802571733229619176668713819931811048770190271",
  46. "25267680276078003013678680992525463401061632866526",
  47. "36270218540497705585629946580636237993140746255962",
  48. "24074486908231174977792365466257246923322810917141",
  49. "91430288197103288597806669760892938638285025333403",
  50. "34413065578016127815921815005561868836468420090470",
  51. "23053081172816430487623791969842487255036638784583",
  52. "11487696932154902810424020138335124462181441773470",
  53. "63783299490636259666498587618221225225512486764533",
  54. "67720186971698544312419572409913959008952310058822",
  55. "95548255300263520781532296796249481641953868218774",
  56. "76085327132285723110424803456124867697064507995236",
  57. "37774242535411291684276865538926205024910326572967",
  58. "23701913275725675285653248258265463092207058596522",
  59. "29798860272258331913126375147341994889534765745501",
  60. "18495701454879288984856827726077713721403798879715",
  61. "38298203783031473527721580348144513491373226651381",
  62. "34829543829199918180278916522431027392251122869539",
  63. "40957953066405232632538044100059654939159879593635",
  64. "29746152185502371307642255121183693803580388584903",
  65. "41698116222072977186158236678424689157993532961922",
  66. "62467957194401269043877107275048102390895523597457",
  67. "23189706772547915061505504953922979530901129967519",
  68. "86188088225875314529584099251203829009407770775672",
  69. "11306739708304724483816533873502340845647058077308",
  70. "82959174767140363198008187129011875491310547126581",
  71. "97623331044818386269515456334926366572897563400500",
  72. "42846280183517070527831839425882145521227251250327",
  73. "55121603546981200581762165212827652751691296897789",
  74. "32238195734329339946437501907836945765883352399886",
  75. "75506164965184775180738168837861091527357929701337",
  76. "62177842752192623401942399639168044983993173312731",
  77. "32924185707147349566916674687634660915035914677504",
  78. "99518671430235219628894890102423325116913619626622",
  79. "73267460800591547471830798392868535206946944540724",
  80. "76841822524674417161514036427982273348055556214818",
  81. "97142617910342598647204516893989422179826088076852",
  82. "87783646182799346313767754307809363333018982642090",
  83. "10848802521674670883215120185883543223812876952786",
  84. "71329612474782464538636993009049310363619763878039",
  85. "62184073572399794223406235393808339651327408011116",
  86. "66627891981488087797941876876144230030984490851411",
  87. "60661826293682836764744779239180335110989069790714",
  88. "85786944089552990653640447425576083659976645795096",
  89. "66024396409905389607120198219976047599490197230297",
  90. "64913982680032973156037120041377903785566085089252",
  91. "16730939319872750275468906903707539413042652315011",
  92. "94809377245048795150954100921645863754710598436791",
  93. "78639167021187492431995700641917969777599028300699",
  94. "15368713711936614952811305876380278410754449733078",
  95. "40789923115535562561142322423255033685442488917353",
  96. "44889911501440648020369068063960672322193204149535",
  97. "41503128880339536053299340368006977710650566631954",
  98. "81234880673210146739058568557934581403627822703280",
  99. "82616570773948327592232845941706525094512325230608",
  100. "22918802058777319719839450180888072429661980811197",
  101. "77158542502016545090413245809786882778948721859617",
  102. "72107838435069186155435662884062257473692284509516",
  103. "20849603980134001723930671666823555245252804609722",
  104. "53503534226472524250874054075591789781264330331690") map {BigInt(_)}
  105. val sums = big_number sum
  106. val su = sums toString
  107. val su10 = su take 10
  108. println(su10)
  109. }
  110. }

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

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:

  1. #!/usr/bin/env python
  2.  
  3. from sys import argv
  4. from collections import Counter
  5.  
  6. if __name__ == "__main__":
  7. with open(argv[1]) as f:
  8. c = Counter(i.partition("-")[0] for i in f)
  9.  
  10. for k,v in c.most_common():
  11. 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”:

  1. module Main where
  2.  
  3. import System.Environment (getArgs)
  4. import qualified Data.Text as T hiding (map, head, zip)
  5. import qualified Data.Text.IO as TI (readFile)
  6. import Data.Map hiding (map)
  7.  
  8. type Counter = (T.Text, Int)
  9.  
  10. mapUnpack :: Counter -> String
  11. mapUnpack (k,v) = show v ++ " " ++ T.unpack k
  12.  
  13. sortMapByValue :: Map T.Text Int -> [Counter]
  14. sortMapByValue = rqsort . toList
  15.  
  16. -- copied & modified by LYHGG in the recusion chapter
  17. -- doing in reverse order as to better suit the output
  18. rqsort :: [Counter] -> [Counter]
  19. rqsort [] = []
  20. rqsort ((k,v):xs) =
  21. let smallerSorted = rqsort [(k',v') | (k',v') <- xs, v' <= v]
  22. biggerSorted = rqsort [(k',v') | (k',v') <- xs, v' > v]
  23. in biggerSorted ++ [(k,v)] ++ smallerSorted
  24.  
  25. main :: IO ()
  26. main = do
  27. results <- getArgs >>= TI.readFile . head
  28. let results' = map (\x -> T.replace space nothing $ head $ T.splitOn dash x) $ T.lines results
  29. let results'' = fromListWith (+) . zip results' $ repeat (1 :: Int)
  30. mapM_ (print . mapUnpack) $ sortMapByValue results''
  31. where dash = T.pack "-"
  32. space = T.pack " "
  33. 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.

Project Euler: Problem 12

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:

  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. my $index = 7;
  7. my $total = 28;
  8. my $divisors = 0;
  9.  
  10. sub divisors
  11. {
  12. my ($number) = @_;
  13. my $sq_n = sqrt($number);
  14. my $i = 1;
  15. my $t = 0;
  16.  
  17. while ($i <= $sq_n)
  18. {
  19. $t += 2 unless ($number % $i);
  20.  
  21. $i += 1;
  22. }
  23.  
  24. return $t;
  25. }
  26.  
  27. while( divisors($total) <= 500)
  28. {
  29. $index += 1;
  30. $total += $index;
  31. }
  32.  
  33. print "$total\n";

Nothing really new or interesting to mention in this code. Here is the Python code:
  1. #!/usr/bin/python
  2.  
  3. """
  4. solution for problem 12 in python.
  5. """
  6. import math
  7.  
  8. def get_divisors(number):
  9. tlist = []
  10. for x in xrange(2, int(math.sqrt(number))):
  11. d,r = divmod(number,x)
  12. if r == 0:
  13. tlist.append(x)
  14. tlist.append(d)
  15.  
  16. return len([1, number] + tlist)
  17.  
  18. def triangle_nums():
  19. iterator = 7
  20. num = 28
  21.  
  22. while True:
  23. yield num
  24. iterator += 1
  25. num += iterator
  26.  
  27. if __name__ == "__main__":
  28. tn = triangle_nums()
  29. for t in tn:
  30. tl = get_divisors(t)
  31. if tl > 500:
  32. print "num: %d\ncount: %d" % (t,tl)
  33. 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:

  1. module Main where
  2.  
  3. get_div_len number = foldl1 (+) [2 | x <- [1..x], number `mod` x == 0]
  4. where x = round . sqrt $ fromInteger number
  5.  
  6. main :: IO()
  7. main = do
  8. print . head $ dropWhile (\x -> fst x <= 499) (map (\x -> (get_div_len x ,x)) xs)
  9. 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:

  1. {-# LANGUAGE BangPatterns, UnboxedTuples #-}
  2. module Main where
  3.  
  4. import Control.Monad
  5. import Control.Monad.State
  6.  
  7. type MyState = (Int, Int)
  8. s0 = (7, 28)
  9.  
  10. tick = do
  11. (n,o) <- get
  12. let divs = getDivLen (n,o)
  13. if divs <= 500
  14. then do
  15. let n' = n + 1
  16. let o' = o + n'
  17. put (n', o')
  18. tick
  19. else
  20.  
  21. getDivLen :: MyState -> Int
  22. getDivLen (!n, !o) = foldl1 (+) [2 | x <- [1..x], o `mod` x == 0]
  23. where x = round . sqrt $ fromIntegral o
  24.  
  25. main :: IO ()
  26. 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.

Pangrams


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:

  1. module Main (main) where
  2.  
  3. import System (getArgs)
  4. import qualified Data.Set as S
  5. import qualified Data.Text as T
  6. import qualified Data.Text.IO as TI (readFile)
  7.  
  8. buildList :: FilePath -> IO [T.Text]
  9. buildList filename = TI.readFile filename >>=
  10. return . map (T.toLower . T.filter (/=' ')) . T.lines
  11.  
  12. compareAndPrint :: S.Set Char -> String
  13. compareAndPrint sset = if S.null result
  14. then "NULL"
  15. else S.toList result
  16. where result = S.difference (S.fromList ['a'..'z']) sset
  17.  
  18. main = do
  19. args <- getArgs
  20. sentences <- buildList $ head args
  21. 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!

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share

Syndicate content