Notes.txt

Notes about my attempts at Project Euler in Haskell
By Regan Sarwas (rsarwas@gmail.com) August 2013 to ...

* Although some of these problems can be simplified by loading a standard or third party module,
  I am limiting myself to just the functions available in the Prelude module loaded by GHCi.

* It is intended that most code be run with the Haskell interpreter (GHCi)
  1. Download the Haskell platform from http://www.haskell.org/platform/
  2. Launch ghci in a terminal window
  3. From the ghci prompt, load this file with ':l pe'
  4. To get the solution to the first problem, just enter pe1 at the ghci prompt

* files are broken into groups of 20 pe1 = 1..20, pe2 = 21..40, etc.

* Files that require IO are broken into individual files, prefixed with the base file
  i.e. pe4_67 for problem #67

* input data files are named for the problem, and is usually piped into the executable
  i.e. $ time cat pe4_67triangle.txt | runhaskell pe3_67.hs

* The file ProjectEuler.hs has multi-use functions, and is imported into all other files

* Summary of fold/scan:
  foldl  f acc [a1, a2,     ... an]  = f (... (f (f acc a1) a2) ...) an
  foldl1 f acc [a1, a2, a3, ... an]  = f (... (f (f  a1 a2) a3) ...) an
  foldr  f acc [a1, ...       an-1, an] = f a1 (... (f an-1 (f an  acc)) ...)
  foldr1 f acc [a1, ... an-2, an-1, an] = f a1 (... (f an-2 (f an-1 an)) ...)
  scan[l|r|l1|r1] are similar to the fold functions, except they return a list with the value of the accumulator at each step

* RE-SOLVED:
  14, implemented the same algorithm as pe14'' in swift, and got a solution in
      less than 1 second, compared to 420 seconds in Haskell.
      It is interesting that Haskell was faster at building the lists and then
      taking the length, than just calculating a length.  The problem seems to be
      with memory, checking sequences below 20,000 took over 1GB of memory.
      Compiling the code instead of running in ghci, yielded results that were
      <24 seconds for the chain calculation and <30 seconds to just calculate the
      length.
      Swift was much faster at just calculating the list length; building the
      lists involved a lot of array allocation and copying (which slowed things down).
  23, compiled with ghc -O, and it was fast enough < 10s
  72, compiled with ghc -O, and it was fast enough < 1s
  92, compiled with ghc -O, and it was fast enough ~ 10s
 210, compiled with ghc -O, and it was fast enough ~ 3.5s

* RE-SOLVE:
  60, Prime pairs: solution is too slow, unsolved in ghci, 110.874 with ghc -O
  76, I stumbled onto some help with this problem, but I would like to resolve it myself.
  79, solved manually, find computer solution
  86, last step is manual, find complete computer solution
 112, lots of manual work; find complete computer solution
 387, Harshad Numbers: WAAAAAAY too slow: 2173.39 in ghci, rewrite in swift
 500, solved in python, find haskell solution
 504, Square on the Inside: Waaaay too slow in ghci, almost 3 minutes with ghc -O (see tc2 for possible faster solution)
 587, manually converged to solution; write a converger (See 607)

* IN-PROGRESS
 107 Minimal network (35% #1, 63)
 162 Hexadecimal numbers (45% #12,138)
 169 Exploring the number of different ways a number can be expressed as a sum of powers of 2 (50% ,~175, Last Unlucky Squares Problem)
 233 Lattice points on a circle (70%, last Fibonacci Fever Problem)
 345 Matrix Sum (15% #1, 4)
 357 Prime generating integers (10% #1, 1)
 493 Under the rainbow (10% #2, 2)
 577 Counting Hexagons (20% #9, 16)
 607 Marsh Crossing