Skip to content

Instantly share code, notes, and snippets.

@NicolasT
Created May 26, 2010 09:31
Show Gist options
  • Save NicolasT/414278 to your computer and use it in GitHub Desktop.
Save NicolasT/414278 to your computer and use it in GitHub Desktop.
(def triangle
[[75]
[95 64]
[17 47 82]
[18 35 87 10]
[20 4 82 47 65]
[19 1 23 75 3 34]
[88 2 77 73 7 63 67]
[99 65 4 28 6 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 4 68 89 53 67 30 73 16 69 87 40 31]
[ 4 62 98 27 23 9 70 98 73 93 38 53 60 4 23]])
(defn pairwise [a]
(map vector a (rest a)))
(defn step [a b]
(map + (map #(apply max %) (pairwise a)) b))
(defn solve [t]
(first (reduce step (reverse t))))
(println (solve triangle))
type Cell = Int
type Row = [Cell]
type Triangle = [Row]
t :: Triangle
t = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 4, 82, 47, 65],
[19, 1, 23, 75, 3, 34],
[88, 2, 77, 73, 7, 63, 67],
[99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
]
pairwise :: [a] -> [(a, a)]
pairwise i = zip i (tail i)
solve :: Triangle -> Int
solve n = head $ foldl1 step $ reverse n
where
step :: Row -> Row -> Row
step a b = map (uncurry (+)) (zip a' b)
where
a' = map (uncurry max) (pairwise a)
main :: IO ()
main = putStrLn $ show $ solve t
t = (
(75, ),
(95, 64, ),
(17, 47, 82, ),
(18, 35, 87, 10, ),
(20, 4, 82, 47, 65, ),
(19, 1, 23, 75, 3, 34, ),
(88, 2, 77, 73, 7, 63, 67, ),
(99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, ),
( 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23, )
)
# Helper functions
pairwise = lambda i: zip(i, i[1:])
uncurry = lambda f: lambda v: f(*v)
add = lambda a, b: a + b
# Algorithm
step = lambda a, b: map(uncurry(add), zip(map(uncurry(max), pairwise(a)), b))
solve = lambda t: reduce(step, reversed(t))[0]
print solve(t)
object Euler18 {
type Cell = Int
type Row = List[Cell]
type Triangle = List[Row]
val triangle : Triangle = List(
List(75),
List(95, 64),
List(17, 47, 82),
List(18, 35, 87, 10),
List(20, 4, 82, 47, 65),
List(19, 1, 23, 75, 3, 34),
List(88, 2, 77, 73, 7, 63, 67),
List(99, 65, 4, 28, 6, 16, 70, 92),
List(41, 41, 26, 56, 83, 40, 80, 70, 33),
List(41, 48, 72, 33, 47, 32, 37, 16, 94, 29),
List(53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14),
List(70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57),
List(91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48),
List(63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31),
List( 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23)
)
def pairwise[A](a: List[A]): List[(A, A)] = a zip (a tail)
def step(a: Row, b: Row): Row = {
val a2 = (pairwise(a)) map (p => Math.max(p._1, p._2))
(a2 zip b) map (p => p._1 + p._2)
}
def solve(t: Triangle): Cell = (t reverse).reduceLeft(step) head
def main(a: Array[String]): Unit = println(solve(triangle))
}
Euler18.main(args)
# Solution for Project Euler problem 18/67
# Solves problem 67 in 0.060s on my machine, of which 0.025s in sys,
# including interpreter startup
from __future__ import with_statement
import itertools
# Helper function
# Takes an iterable (a0, a1, a2, a3, ...)
# Returns an iterable ((a0, a1), (a1, a2), (a2, a3), ...)
pairwise = lambda i: \
(lambda (a, b): itertools.izip(a,
itertools.islice(b, 1, None)))(itertools.tee(i))
# Reduction step function
# This is where the magic happens
step = lambda a, b: itertools.imap(lambda x, y: x + y,
itertools.imap(lambda (x, y): max(x, y), pairwise(a)), b)
# Calculate the problem solution for a given triangle
# Triangles should be provided as a reversable iterable of iterables, e.g. a
# tuple of iterables.
# Use 'text_to_triangle' to convert a triangle in string-form into a correct
# structure.
f = lambda t: reduce(step, reversed(t)).next()
# Helper function
# Convert a triangle string into a useful datastructure as required by 'f'
# The argument should be an iterable of lines
text_to_triangle = lambda lines: tuple((int(j) for j in line.split())
for line in lines)
# A simple main function, for testing
def main(i):
with open(i, 'r') as fd:
return f(text_to_triangle(fd.xreadlines()))
if __name__ == '__main__':
print main('triangle.txt')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment