2

I am doing project euler question 136, and came up with the following to test the example given:

module Main where
import Data.List

unsum x y z n = (y > 0) && (z > 0) && (((x*x)  - (y*y)- (z*z)) == n) && ((x - y) == (y - z))
answer = snub $ takeWhile (<100) [n|x<-[1..],d<-[1..x`div`2],n<-[x..100],y<-[x-d],z<-[y-d], unsum x y z n ]
    where 
      snub [] = []
      snub (x:xs) | elem x xs = snub (filter (/=x) xs)
                  | otherwise = x : snub xs

snub will remove any numbers that are duplicates from a list.

The example is supposed to give 25 solutions for n where x^2 - y^2 - z^2 == n and all numbers are positive (or so I gather from the question) and are an arithmetic progression such that x-y == y-z. But when I use the code, a list of 11 solutions for n are returned.

What have I done wrong in my list comprehension and are there any optimisations I have missed out?

Jonno_FTW
  • 8,601
  • 7
  • 58
  • 90
  • I made my own `nub` so it would return a list with both duplicates removed, as the question wants solutions for `n` which are unique – Jonno_FTW Nov 30 '09 at 06:14
  • so that explains your comment here http://stackoverflow.com/questions/1801459/algorithm-how-to-delete-duplicate-elements-in-a-list-efficiently/1801575#1801575 :) – barkmadley Nov 30 '09 at 08:18

1 Answers1

2

point 1

I made an attempt at this question and found that this was the sequence of ns that I came up with

[4,3,16,12,7,20,11,48,28,19,80,44,23,52,112,31,68,76,1156,43,176,559...

which potentially means that your takeWhile (<100) is the wrong filtering function to use to determine when to stop. On a related note, I tried running this:

answer = snub $ filter (<=100) $ takeWhile (<200) [...listcomprehension...]

But i gave up because it was taking too long. Which leads me to point 2.

point 2

In terms of optimisations, look at what your list comprehension produces in terms of raw output.

Main> take 30 [(x,y,z,n) | x<-[1..], d<-[1..x`div`2], n<-[x..100], y<-[x-d], z<-[y-d]]
[(2,1,0,2),(2,1,0,3),(2,1,0,4),(2,1,0,5),(2,1,0,6),(2,1,0,7),(2,1,0,8),(2,1,0,9),
(2,1,0,10),(2,1,0,11),(2,1,0,12),(2,1,0,13),(2,1,0,14),(2,1,0,15),(2,1,0,16),(2,1,0,17),
(2,1,0,18),(2,1,0,19),(2,1,0,20),(2,1,0,21),(2,1,0,22),(2,1,0,23),(2,1,0,24),(2,1,0,25),
(2,1,0,26),(2,1,0,27),(2,1,0,28),(2,1,0,29),(2,1,0,30),(2,1,0,31)]

This means that unsum is being called on each combination of x y z and n, which is a little bit redundant since we know that 2^2 - 1^2 - 0^2 = 3.

It is also much simpler and much less redundant to move the calculation of n from the list comprehension (slow because of above) to a function and merely list comprehend the (x,y,z) combinations that are valid.

ns = map nsum [(x, x-d, x-d-d) | x <- [1..], d <- [1..x`div`2]]
nsum (x,y,z) = x^2 - y^2 - z^2

Then it is possible to calculate the answer from this infinite list, but beware of using takewhile.

Community
  • 1
  • 1
barkmadley
  • 5,207
  • 1
  • 28
  • 31
  • Thanks for the help, I see why `takeWhile` was incorrect because the solutions for `n` jumped back to below 0 after n had exceeded 100. – Jonno_FTW Nov 30 '09 at 10:27
  • Ok, after trying: `answer = length $ snub $ filter (> 0) $ map nsum [(x, x-d, x-d-d) | x <- [3..5000], d <- [1..x`div`2]]` it completely sucked up all my RAM. I think there is some crucial optimisation I have yet to figure out, likely in which `x,y,z` triples are candidates for a unique solution (probably involving primes) – Jonno_FTW Nov 30 '09 at 10:55