[Haskell-cafe] Re: Hints for Euler Problem 11
Kim-Ee Yeoh <[EMAIL PROTECTED]> writes: > Aaron Denney wrote: > > I find the first far more readable. The compiler should be able to > > assemble it all at compile time, right? > > > > 'Course not. The (++) function like all Haskell functions is only a > /promise/ to do its job. I find this comment rather strange. One of the beauties of a pure language (especially a lazy one) is that there is no requirement for evaluation to take place at at any particular time as long as it's done before it's needed. So the compile-time/run-time dichotomy is only relevant when a value depends on data only available at run-time. Given that "foo "++"bar" can be evaluated at compile time and there are advantages and no disadvantages, it should be evaluated at compile time. In general, I don't think we should clutter the language with syntax for things for which there has to be a more general mechanism; including string breaks in the language was a mistake. Compare "thing1\n\ \thing2\n\ \thing3\n"++ otherThing++ "penultimate thing\n\ \last thing\n" with "thing1\n"++ "thing2\n"++ "thing3\n"++ otherThing++ "penultimate thing\n"++ "last thing\n" What /is/ the advantage of the former? -- Jón Fairbairn [EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hints for Euler Problem 11
On 2007-08-16, Kim-Ee Yeoh <[EMAIL PROTECTED]> wrote: > > > Aaron Denney wrote: >> >> On 2007-08-15, Pekka Karjalainen <[EMAIL PROTECTED]> wrote: >>> A little style issue here on the side, if I may. You don't need to use >>> (++) to join multiline string literals. >>> >>> text = "If you want to have multiline string literals \ >>>\in your source code, you can break them up with \ >>>\backslashes. Any whitespace characters between \ >>>\two backslashes will be ignored." >> >> I find the first far more readable. The compiler should be able to >> assemble it all at compile time, right? >> > > 'Course not. The (++) function like all Haskell functions is only a > /promise/ to do its job. What does "assembling at compile time" > mean here: > > s = "I will not write infinite loops " ++ s It's a circular list of characters. Quite feasible to do at compile time. -- Aaron Denney -><- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hints for Euler Problem 11
On 2007-08-15, Pekka Karjalainen <[EMAIL PROTECTED]> wrote: > On 8/15/07, Mathias Biilmann Christensen <[EMAIL PROTECTED]> wrote: >> Spotted this thread as I was working on a Haskell solution for this >> one myself - here's the solution I came up with: >> [ ... ] >> raw_matrix = >> "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 " ++ >> "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 " ++ >> "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 " ++ > [ ... ] > > A little style issue here on the side, if I may. You don't need to use > (++) to join multiline string literals. > > text = "If you want to have multiline string literals \ >\in your source code, you can break them up with \ >\backslashes. Any whitespace characters between \ >\two backslashes will be ignored." I find the first far more readable. The compiler should be able to assemble it all at compile time, right? -- Aaron Denney -><- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hints for Euler Problem 11
On 8/15/07, Mathias Biilmann Christensen <[EMAIL PROTECTED]> wrote: > Spotted this thread as I was working on a Haskell solution for this > one myself - here's the solution I came up with: > [ ... ] > raw_matrix = > "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 " ++ > "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 " ++ > "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 " ++ [ ... ] A little style issue here on the side, if I may. You don't need to use (++) to join multiline string literals. text = "If you want to have multiline string literals \ \in your source code, you can break them up with \ \backslashes. Any whitespace characters between \ \two backslashes will be ignored." (The Haskell 98 Report calls them backslants.) Pekka ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Hints for Euler Problem 11
Spotted this thread as I was working on a Haskell solution for this one myself - here's the solution I came up with: module Main where import List raw_matrix = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 " ++ "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 " ++ "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 " ++ "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 " ++ "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 " ++ "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 " ++ "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 " ++ "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 " ++ "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 " ++ "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 " ++ "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 " ++ "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 " ++ "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 " ++ "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 " ++ "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 " ++ "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 " ++ "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 " ++ "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 " ++ "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 " ++ "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 " matrix :: [Int] matrix = map read (words raw_matrix) rows = map (\i -> take 20 (drop (i * 20) matrix)) [0..19] cols = transpose rows diag m = (map (\i -> map (\p -> m !! p !! (i+p)) [0..(19-i)]) [0..19]) ++ (map (\i -> map (\p -> m !! (i+p) !! p) [0..(19-i)]) [0..19]) all_matrix_combinations = rows ++ cols ++ (diag rows) ++ (diag $ reverse rows) -- This function finds the maximum sequence of 4 in a given list find_max_product_of_4 l = find_max_4' 0 l where find_max_4' m [] = m find_max_4' m l = find_max_4' (max m (product $ take 4 l)) (tail l) all_maximums = map find_max_product_of_4 all_combinations max_product = maximum all_maximums main = putStrLn $ show max_product ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hints for Euler Problem 11
Thank you for all the hints. Here's how I ended up solving it: > module Main > where > > import Data.List > import Data.Maybe > > gridText = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\ > \49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\ > \81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\ > \52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\ > \22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\ > \24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\ > \32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\ > \67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\ > \24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\ > \21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\ > \78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\ > \16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\ > \86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\ > \19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\ > \04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\ > \88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\ > \04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\ > \20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\ > \20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\ > \01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" > type Grid a = [[a]] > readGrid :: (Read a) => String -> Grid a > readGrid = (map ((map read) . words)) . lines > grid :: Grid Integer > grid = readGrid gridText takeExactly - extract the first "n" elements of a list; there must be at least "n" elements, n > 0 > takeExactly :: (Monad m) => Int -> [a] -> m [a] > takeExactly n xs | n > 0 = > let ys = take n xs in >if length ys == n > then return ys > else fail "takeExactly: list is too short" > | otherwise = fail "takeExactly: empty list" > extractGroups :: Int -> [[a]] -> [[a]] > extractGroups n = catMaybes . map (takeExactly n) > gridExtractGroups :: Int -> Grid [a] -> Grid [a] > gridExtractGroups n = filter (not . null) . map (extractGroups n) gridTails - generate a list of grids with sequential starting places Parameters a and b determine the offset bewteen successive grids, as follows: (note that a, b may not be negative) Grid x_{0,1.., 0,1..} -> [ Grid x_{ 0, 1 .., 0, 1 ..} , Grid x_{ a, a+1 .., b, b+1 ..} , Grid x_{2*a, 2*a+1 .., 2*b, 2*b+1 ..} etc. ] > gridTails :: (Int, Int) -> Grid a -> [Grid a] > gridTails (a,b) xs = > if not $ null $ concat xs > then xs : gridTails (a,b) ((drop a) $ map (drop b) xs) > else [] transpose3d - converts x_{i,j,k} to x_{j,k,i} using sequence is x_{i,j,k} -> x_{j,i,k} -> x_{j,k,i} > transpose3d :: [Grid a] -> Grid [a] > transpose3d = map transpose . transpose reorient - transform a direction vector so that both components are non-negative > reorient :: (Int, Int) -> (Grid a -> Grid a, (Int, Int), Grid b -> Grid b) > reorient (a,b) > | a>=0 && b>=0 = (id , ( a, b), id) > | a< 0 && b>=0 = (reverse , (-a, b), reverse) > | a>=0 && b< 0 = (map reverse , ( a,-b), map reverse) > | a< 0 && b< 0 = (reverse . map reverse, (-a,-b), reverse . map reverse) makeEls - convert a grid to grid of Equidistant Letter Sequences > makeEls :: (Int, Int) -> Grid a -> Grid [a] > makeEls vec = let (reflect2, rvec, reflect1) = reorient vec in > reflect2 . transpose3d . gridTails rvec . reflect1 > getGroups :: Int -> (Int, Int) -> Grid a -> [[a]] > getGroups n (a,b) = concat . gridExtractGroups n . makeEls (a,b) > findMaxProduct :: (Ord a, Num a) => Int -> (Int, Int) -> Grid a -> a > findMaxProduct n (a,b) = maximum . map product . getGroups n (a,b) > main :: IO() > main = do > print $ findMaxProduct 4 (1,0) grid > print $ findMaxProduct 4 (0,1) grid > print $ findMaxProduct 4 (1,1) grid > print $ findMaxProduct 4 (1,-1) grid -- Ron ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Hints for Euler Problem 11
Ronald Guida mindspring.com> writes: > I started looking at the Euler problems [1]. I had no trouble with > problems 1 through 10, but I'm stuck on problem 11. I am aware that > the solutions are available ([2]), but I would rather not look just > yet. I am the author of that solution http://www.haskell.org/haskellwiki/Euler_problems/11_to_20 My solution has a word count of 191 words, which might amuse you considering that there are 400 entries to the table. Hint: "zipWith4" is your friend; see Data.List. Feed it four lists of different lengths, and it stops gracefully when any list runs out. So one can use skew (w,x,y,z) = (w, drop 1 x, drop 2 y, drop 3 z) to stagger four lists before multiplying corresponding elements. I was using the Euler problems to learn Haskell, as you're doing, so I don't know if my solution is the most readable one. I built up a vocabulary of short functions to compose. I remember finding it odd at the time that I had to use tuples to handle multiple return values. C annoyed me for being mostly peanut shells and few peanuts: one seems to spend all of one's time tossing arguments back and forth onto the stack for nested function calls, when it seemed that the real work could be done in place with less effort. Sure, optimizing compilers do exactly that, with registers, but then why was I explicitly worrying about passing around all of these arguments, in order to code in C? Haskell is much more concise, but the tupling and untupling in my code seems a distraction, even looking back at it now. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe