Anyone else busy with Euler challenges or something similar or better?

[[)roi(]]

Until recently I would fill my free time with a few crossword and / or sudoku puzzles, but for quite a while I've felt they don't either keep me engaged or offer enough of a challenge; so I started looking for a replacement.

During this process I for decided to also consider small programming oriented puzzles, so no surprise when Euler appeared in the search results. Probably like many of you I've in the past tried a few of the Euler challenges and ended up thinking meh? but that was because I rarely looked beyond the first ten or so challenges. So lacking any clear or better alternatives I decided to give Euler another try....

I'm 96 puzzles in, and busy with a Sudoku inspired challenge, which inspired this post -- wondering how many of you also are busy with Euler challenges or something you consider more challenging (or applicable) than Euler.

My Approach
In order to make Euler a bit more challenging (as if it wasn't already); I decided to give myself an extra challenge; that is to make sure every solution was tackled with a Functional Programming style.

Solutions
Btw I'm not going to just post solutions -- because I don't want to spoil the fun of anyone else wanting to tackle Euler problems, but if you need help (or a working solution), you need only send me a PM -- happy to provide pointers, explanations or even coded solution. FYI I written all the solutions in Swift, but all of these can be quite easily translated to other FP enabled languages, e.g. C#, F#, Python, Perl, PHP, Java, ... I'll be happy to help you translate a few (if you need it). Ps. most problems can be solved by brute force or technique -- naturally technique is vital if you want to sub-second times.

Your thoughts
Let me know your thoughts on this? If you've found something you think is a better than Euler, naturally with a focus on programming, then please share it. Also as many if these challenges typically find their way into interviews, it's probably also a good idea to look at challenges that usually pitch up there.

Links:
https://projecteuler.net

Note:
Euler Problems are graded by difficulty e.g. Problem1 is rated as 5% (similarly most of 1st twenty or so)

Whereas problem 96 (my current one) is rated as 25%.

... and that's not where it stops i.e. you'll even find a few of 95 to 100% difficulty problems.

 

[XennoX]

I've seen a site called TopCoder that hosts challenges. Their challenges usually revolve around the efficiency of your algorithm. For example:

Calculate the modulus of the n[sup]th[/sup] Fibonacci number, denoted as F[sub]n[/sub], modulo m. Where n is an integer value between 2 and 10[sup]8[/sup] and m is an integer value between 2 and 10[sup]5[/sup].

Your algorithm may not run longer than 1.5 seconds.

Note:

The Fibonacci sequence is calculated as follows: 

Given F[sub]0[/sub] = 1 and F[sub]1[/sub] = 1 then
F[sub]2[/sub] = F[sub]0[/sub] + F[sub]1[/sub]
F[sub]3[/sub] = F[sub]1[/sub] + F[sub]2[/sub]
etc.

 

[[)roi(]]

I've seen a site called TopCoder that hosts challenges. Their challenges usually revolve around the efficiency of your algorithm. For example:

Calculate the modulus of the n[sup]th[/sup] Fibonacci number, denoted as F[sub]n[/sub], modulo m. Where n is an integer value between 2 and 10[sup]8[/sup] and m is an integer value between 2 and 10[sup]5[/sup].

Your algorithm may not run longer than 1.5 seconds.

Note:

The Fibonacci sequence is calculated as follows: 

Given F[sub]0[/sub] = 1 and F[sub]1[/sub] = 1 then
F[sub]2[/sub] = F[sub]0[/sub] + F[sub]1[/sub]
F[sub]3[/sub] = F[sub]1[/sub] + F[sub]2[/sub]
etc.

Your example is a nice, but relatively easy once you've done the leg work to build a BigInt type; Quite a few of Euler challenges require a BigInt type; e.g. problem 13 requires you to sum 100 x 50 digit numbers and problem 16 requires you add the digits of a BigInt number 2[sup]1000[/sup] -- meaning modulus of a large Int is fairly easy once you've built a BigInt type (one supporting ~unlimited digits). Similarly for the Fibonacci sequence; problem 2 is the first time you need code to generate Fibonacci numbers, once you've built a Sequence Generator these types of challenges become simple.

Here's an example of Fibonacci Generator below a ceiling (in Swift):

fileprivate struct FibonacciSequence: IteratorProtocol, Sequence
{
  private var fibonacci = (current: 1, prior: 1)
  private let ceiling: Int
  
  init(_ ceiling: Int)
  {
    self.ceiling = ceiling
  }
  
  mutating func next() -> Int?
  {
    guard fibonacci.current <= ceiling else { return nil }
    defer { fibonacci = (fibonacci.current + fibonacci.prior, fibonacci.current)}
    return fibonacci.current
  }
}

i.e. it would be simple to alter this to return nth value. I won't copy in the code of the BigInt type (it's quite a bit of code); but I'm happy to share if someone needs a copy.

I probably have the wrong TopCoder site? re this looks a lot like work disguised as challenges?

 

[cguy]

I suspect that the n used in their advanced test cases is large enough that if you generate the sequence you're dead in the water. There's an O(1) way to generate the number, but it's accuracy depends on how much of an irrational number you're able to compute and store (would have to use GMP or such). There is also an O(logn) approach that would probably work nicely with a big int type.

 

[XennoX]

Sure, you could do all that crazy amount of work to create a BigInt type, you could also use the naive method for computing the Fibonacci sequence, but there are far more efficient (sometimes elegant) ways of doing so.

Let's examine Modulus Arithmetic a bit.

Believe it or not, but we actually use Modulus Arithmetic every single day. How so? The clock. What happens to the number when the hour hand goes past 12h00? Effectively, it resets back to zero. So it can be said that to tell the time on the clock, we are doing the number we see modulo 12.

Example: What is 13 modulo 12? It is 1! What is 18 modulo 12? It is 6! What is 24 modulo 12? It is 0! See the reset? The maximum number you will ever get is (m - 1). The same concepts can be applied to the measures of seconds and minutes, the modulo just changes to 60.

So how does this apply to the Fibonacci sequence? Well, it has a unique property, called the Pisano period. Let's observe:

	F[sub]0[/sub]	F[sub]1[/sub]	F[sub]2[/sub]	F[sub]3[/sub]	F[sub]4[/sub]	F[sub]5[/sub]	F[sub]6[/sub]	F[sub]7[/sub]	F[sub]8[/sub]	F[sub]9[/sub]	F[sub]10[/sub]
F[sub]n[/sub]	0	1	1	2	3	5	8	13	21	34	55
F[sub]n[/sub] mod 2	0	1	1	0	1	1	0	1	1	0	1
F[sub]n[/sub] mod 3	0	1	1	2	0	2	2	1	0	1	1

Do you see the pattern? Every so often the triplet of 0, 1, 1 appears, signalling the start of a new cycle. This is called the Pisano period.

F[sub]n[/sub] mod 2 is said to have a Pisano length of 3!
F[sub]n[/sub] mod 3 is said to have a Pisano length of 8!

What this means is that all we need to do is find the Pisano length for a specific modulo, and we are well on our way to finding F[sub]n[/sub] modulo m without the need for a BigInt.

Even this solution is sub-optimal. As there is something far quicker. See below.

Let's take a look at binary exponentiation, shall we?

Let's assume we have a number, θ. We want to multiply θ by itself, such that the result is θ[sup]32[/sup]. We could implement the naive way, which is simply:

θ * θ * ... 28 times later ... * θ * θ

Or we could observe the following:

θ * θ = θ[sup]2[/sup]
θ[sup]2[/sup] * θ[sup]2[/sup] = θ[sup]4[/sup]
θ[sup]4[/sup] * θ[sup]4[/sup] = θ[sup]8[/sup]
θ[sup]8[/sup] * θ[sup]8[/sup] = θ[sup]16[/sup]
θ[sup]16[/sup] * θ[sup]16[/sup] = θ[sup]32[/sup]

So we have reduced 31 multiplication operations down to 5 multiplication operations. Best of all, we can do this recursively, yay stack overflows!

So now you might ask, "What the hell does binary exponentiation have to do with the Fibonacci sequence?"

Answer: We borrow concepts from binary exponentiation, and we evolve it into Matrix Exponentiation!

From above, we have seen that the Fibonacci sequence is a linearly recursive relationship (it turns out matrix exponentiation works on sequences that are linearly recursive). Just to refresh:

Given F[sub]0[/sub] = 0 and F[sub]1[/sub] = 1 then
F[sub]2[/sub] = F[sub]1[/sub] + F[sub]0[/sub] = 1 + 0 = 1
F[sub]3[/sub] = F[sub]2[/sub] + F[sub]1[/sub] = 1 + 1 = 2
etc.

OK, so what now? Do you see that we have a set of linear equations there? Remember from linear algebra that equations can be represented in matrix form? Good!

|f[sub]n[/sub] | = | w x | * | f[sub]n - 1[/sub] |
| f[sub]n - 1[/sub] | | y z | | f[sub]n - 2[/sub] |

If we solve for w, x, y, and z we get them equal to 1, 1, 1 and 0 respectively. So the above system becomes like so:

| f[sub]n[/sub] | = | 1 1 | * | f[sub]n - 1[/sub] |
| f[sub]n - 1[/sub] | | 1 0 | | f[sub]n - 2[/sub] |

As it so happens, because that middle matrix stays constant no matter what Fibonacci number we are attempting to calculate we can make use of the binary exponentiation (or repeated squaring).

You can then make use of the property of modulus arithmetic to say:

f[sub]n[/sub] modulo m = (f[sub]n - 1[/sub] + f[sub]n - 2[/sub]) modulo m

This will solve the problem in roughly O(log(n)) time, without the need for an arbitrary sized integer to store the actual number(s).

 

[[)roi(]]

I suspect that the n used in their advanced test cases is large enough that if you generate the sequence you're dead in the water. There's an O(1) way to generate the number, but it's accuracy depends on how much of an irrational number you're able to compute and store (would have to use GMP or such). There is also an O(logn) approach that would probably work nicely with a big int type.

Yeah silly me, you're right... this is a case where formulas are absolute e.g. Binet's formula is a fast way to calculate nth Fibonacci number, the only real remaining complexity is tagging on something like Goldschmidt’s algorithm to the BigInt type to calculate the square root (but that's also relatively easy re it's primarily a division formulation)

Btw GMP is an easy way out, but it kind of defeats the purpose of these challenges, similarly e.g. In Euler problem 19 you are asked to calculate "How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?" -- this isn't even a challenge if you resort to using Date libraries.

 

[[)roi(]]

...You can then make use of the property of modulus arithmetic to say:

f[sub]n[/sub] modulo m = (f[sub]n - 1[/sub] + f[sub]n - 2[/sub]) modulo m

This will solve the problem in roughly O(log(n)) time, without the need for an arbitrary sized integer to store the actual number(s).

That's a really interesting approach; but personally I'm far less enthused about problems that hinge on formulation and/or research methods; but granted there are always going to be problems that have to fallback on research, especially when traditional iterative methods are impractical e.g. Cryptography

In my case though, quite a few of the Euler problems weren't simply resolved by formulation, and with Swift still lacking a native BigInt type in it's standard library, I chose to build one; naturally I could have written a simple wrapper around something lke GMP; but that's definetly not as much fun or as much of a challenge as building your own.

Anyway thanks re the problem; I think when I have a moment I'll try to resolve it using a combination of BigInt, Binet's and Goldschmidt formulas; at least that way I would have added implementations for a sqrt method and modulus operator to my BigInt type.

 

[XennoX]

That's a really interesting approach; but personally I'm far less enthused about problems that hinge on formulation and/or research methods; but granted there are always going to be problems that have to fallback on research, especially when traditional iterative methods are impractical e.g. Cryptography

In my case though, quite a few of the Euler problems weren't simply resolved by formulation, and with Swift still lacking a native BigInt type in it's standard library, I chose to build one; naturally I could have written a simple wrapper around something lke GMP; but that's definetly not as much fun or as much of a challenge as building your own.

Anyway thanks re the problem; I think when I have a moment I'll try to resolve it using a combination of BigInt, Binet's and Goldschmidt formulas; at least that way I would have added implementations for a sqrt method and modulus operator to my BigInt type.

No problem. In my current line of work, I'm forced to read academic papers to find optimal algorithms for computational geometry problems, path optimisation problems, and geometry data compression techniques - hence the questions I sent you a while regarding parallel computing.

 

[cguy]

No problem. In my current line of work, I'm forced to read academic papers to find optimal algorithms for computational geometry problems, path optimisation problems, and geometry data compression techniques - hence the questions I sent you a while regarding parallel computing.

Interesting! What kind of work do you do if I may ask?