You are viewing extempore

Feb. 25th, 2008 @ 07:52 am do not neglect mr. euler
My friend is doing project euler in scala and he's up to #32. He's ten times the programmer I am so I had better get back to work. I did the first 46 in erlang but as of problem 47 I switched to haskell. That should mean I'd have to re-implement many of the utility functions I already wrote in erlang, except that I'm "borrowing" anything I already wrote in erlang so the language jump doesn't hurt too badly.

I'm just starting to wrap my head around haskell so if you must ridicule my code at least suggest improvements.
-- #47
p47 = p47try (map compress_factors factorizations)

p47try list = 
	if all (\x -> length x >= 4) seq &&				-- each has 4+ factors
		sum (map length seq) == length (nub $ concat seq)	-- all factors distinct
		then map unfactorize seq
		else p47try $ tail list
	where seq = take 4 list

Note that factorizations is an infinite list:
factorizations  = map factorise [2..]

compress_factors [] = []
compress_factors xs =
        (head(xs), length top) : compress_factors (drop (length top) xs)
        where top = [x | x <- xs, x == head(xs) ]

unfactorize xs =
        product [a^b | (a,b) <- xs]

That's my favorite part of haskell, that you can have data structures that represent infinite lists. Since everything is evaluated lazily, it's happy to let you work with infinite structures - but if you ask for the last element of the list you may have to wait a bit. Grab some coffee.

Sorry that some of the syntax coloring is hard to read - this is the default HsColour html output. I'll see if I can find something more readable.

Update: problem 48. One liners are nice.
-- #48
p48 = sum [x^x | x <- [1..1000] ] `mod` 10^10
About this Entry
[User Picture Icon]
From:walterzuey
Date:February 25th, 2008 05:42 pm (UTC)
(Permanent Link)
I see a pond-sidedness mismatch with

factorise
unfactorize

This should cause a SOWPODS memory dump.
[User Picture Icon]
From:herooftheage
Date:February 25th, 2008 06:30 pm (UTC)
(Permanent Link)
Your link to haskell appears to be broken. When I click it, the page I'm on just reloads.

Fortunately, google is up to the task of letting me figure out what you're talking about.

[User Picture Icon]
From:extempore
Date:February 25th, 2008 06:55 pm (UTC)
(Permanent Link)
I guess I has the dumb. Now it works.
[User Picture Icon]
From:olaugh
Date:February 25th, 2008 06:48 pm (UTC)
(Permanent Link)
[User Picture Icon]
From:shunny
Date:February 25th, 2008 11:26 pm (UTC)
(Permanent Link)
I started learning Java and like Computer Science, so I might have to give that a try sometime.

Thanks.
From:kvom01
Date:February 26th, 2008 02:23 pm (UTC)
(Permanent Link)
I found the Euler website a while back from reading your blog.

Now have solved 115 out of 183 using Java (solved a few using Excel). Good entertainment.

I was a programmer my whole career, so the algorithms are not a big problem. However, understanding some of the math principles can be a challenge. Mathworld site is definitely a help.