Euler #2

Just saw a nice post with solutions to Euler problem #2 in several different languages.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

This one is so easy in Perl 6 it’s not worth writing a script, I just did it as a one-liner in the REPL:

> say [+] (1, 1, *+* ... 4000000).grep(* !% 2)
4613732

Breaking it down: 1, 1, *+* ... * is the standard way to generate the infinite Fibonacci sequence in p6. It creates a list of numbers using the ... “series” operator. The list starts with 1, 1, and each additional number is created by adding the two previous numbers (that’s the *+* bit). The final * means the series has no limit. By switching the limit to 4000000 instead, we explicitly say “stop the series as soon as the number 4000000 is exceeded.”

> say ~(1, 1, *+* ... 4000000)
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578

Then grep filters on the test * !% 2. !% is the “divisible by” operator; * !% 2 generates a closure that checks its one input for divisibility by 2.

> say ~(1, 1, *+* ... 4000000).grep(* !% 2)
2 8 34 144 610 2584 10946 46368 196418 832040 3524578

Finally [+] is the reduce metaop for addition; it sums the list that follows.

I know that when people see one-liners, frequently they think the result has been golfed down. But this is really the natural way to express this problem in Perl 6.

Update: Very shortly after I wrote this, the “is divisible by” operator was changed to %%. At the moment, both versions of the operator work in Rakudo, but I would expect !% to go away eventually.

About these ads

Tags:

7 Responses to “Euler #2”

  1. zloyrusskiy Says:

    It’s wonderful! I really liked your solution!

  2. Eddward Says:

    I’ve been waiting for perl6 for a while and I’ve been playing with rakudo a bit lately. The (1,1, *+* .. *) thing is new to me. Was that invented specifically for fibonacci or does it have some other more practical use that’s eluding me?

    Edd

    • colomon Says:

      It is much more generally useful — and the pieces of it even more so — but I just asked Larry, and he says that Fibonacci was one of the first usages he thought of. :)

      The series operator (here and down a bit) is very useful in general. And the WhateverClosure trick that turns * + * into a anonymous sub is very handy. The combination can be very handy.

      • Eddward Says:

        OK. get it. there was one more feature at work than I thought. The whatever closure looked like a meta op on +. It will take me a while to get my head around the series operator.

        Edd

  3. Aaron Sherman Says:

    Minor nit: the puzzle as you quoted it asks for a solution using a variation sequence which begins with 1,2, not 1,1. Of course, since 1,2,*+*…$n and 1,1,*+*…$n only differ in their first term, and the puzzle only cares about even elements, you get the same answer in both cases.

    Eddward: the series op is pretty straight forward. I find this particular example more easily understood as 1,1,{$^a + $^b} … * though I will admit that it’s a lot longer. Whatever-currying is just a bit too magical for me just yet, but I’m sure I’ll get used to it.

  4. Pm Says:

    BTW, note that on the day after YAPC::NA the !% operator was changed to %%. :-)

    Pm

  5. Bryce Says:

    Hey, Thanks for linkiing to my site on this.

    Also, I really liked your solution to the problem in perl6. One of the best things about doing this blog series is getting to see everyone else’s solutions to these problems as well as their preferred languages. Its truly amazing what one can learn looking and studying other people’s code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: