Home

PureScript solution to Project Euler problem 18

2019-Mar-01 04:09
purescriptproject-euler

Problem details at Project Euler problem 18 page.

Test

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
module Euler018Test (euler18suite) where
 
import Prelude
 
import Data.BigInt (fromString)
import Data.Maybe (Maybe(..))
import Data.String (length)
import Euler018 (euler18)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
triangleWarmup :: String
triangleWarmup = """
  3
  7 4
  2 4 6
  8 5 9 3
  """
 
triangleReal :: String
triangleReal = """
  75
  95 64
  17 47 82
  18 35 87 10
  20 04 82 47 65
  19 01 23 75 03 34
  88 02 77 73 07 63 67
  99 65 04 28 06 16 70 92
  41 41 26 56 83 40 80 70 33
  41 48 72 33 47 32 37 16 94 29
  53 71 44 65 25 43 91 52 97 51 14
  70 11 33 28 77 73 17 78 39 68 17 57
  91 71 52 38 17 14 91 43 58 50 27 29 48
  63 66 04 68 89 53 67 30 73 16 69 87 40 31
  04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""
 
euler18suite :: TestSuite
euler18suite =
  suite "Euler 18" do
    test "Warmup" do
      Assert.equal (Just 23) (euler18 triangleWarmup)
    test "Real" do
      Assert.equal (Just 1074) (euler18 triangleReal)

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
module Euler018 where
 
import Prelude
 
import Data.Array (concat, dropEnd, filter, null, tail, takeEnd, zip, zipWith, (!!))
import Data.Int (fromString)
import Data.Maybe (Maybe, fromMaybe)
import Data.String (trim)
import Data.String.Utils (lines, words)
import Data.Traversable (sequence)
import Data.Tuple (Tuple(..))
 
parse :: String -> Maybe (Array (Array Int))
parse s = lines (trim s)
  # map trim
  # map words
  # filter (not null)
  # map (map fromString)
  # map sequence
  # sequence
 
combine :: Array (Array Int) -> Array (Array Int)
combine [] = []
combine [as] = [as]
combine aas = fromMaybe [] $ do
  a <- aas !! 0
  b <- aas !! 1
  bt <- tail b
  let bm = zipWith max b bt
  pure $ pure $ map (\(Tuple x y) -> x + y) (zip a bm)
 
collapse :: Array (Array Int) -> Int
collapse [] = 0
collapse [[i]] = i
collapse aas =
  let l = dropEnd 2 aas
      r = takeEnd 2 aas
      c = combine r
  in collapse $ concat [l, c]
 
euler18 :: String -> Maybe Int
euler18 = parse >>> map collapse