icyrock.com

Home

PureScript solution to Project Euler problem 19

2019-Apr-27 20:13
purescriptproject-euler

Problem details at Project Euler problem 19 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
module Euler019Test (euler19suite) where
 
import Prelude
 
import Euler019 (euler19)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler19suite :: TestSuite
euler19suite =
  suite "Euler 19" do
    test "Warmup" do
      Assert.equal 2 (euler19 1900 1900)
      Assert.equal 3 (euler19 2000 2001)
      Assert.equal 4 (euler19 2015 2016)
      Assert.equal 4 (euler19 2018 2019)
    test "Real" do
      Assert.equal 171 (euler19 1901 2000)

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