Created
May 26, 2010 09:31
-
-
Save NicolasT/414278 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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)) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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