Euler Problems

Andrew Mathenge mathenge at gmail.com
Sun Jul 13 21:44:08 BST 2008 

I knocked off number 18. It was a brute force effort. I followed your
advice and created a two-dimensional array to hold the triangle.

I then created a second list that held the various permutations from:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
to
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

The basic idea is to create all the combinations/permutations from 1
to 15, the only restriction being that the number to the right can
only be one larger than the number on the left.

Here's a slice of the first few permutations:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 2 2 3
1 1 1 1 1 1 1 1 1 1 1 1 2 3 3
1 1 1 1 1 1 1 1 1 1 1 1 2 3 4
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 2 2 2 3
1 1 1 1 1 1 1 1 1 1 1 2 2 3 3
1 1 1 1 1 1 1 1 1 1 1 2 2 3 4
1 1 1 1 1 1 1 1 1 1 1 2 3 3 3
1 1 1 1 1 1 1 1 1 1 1 2 3 3 4
1 1 1 1 1 1 1 1 1 1 1 2 3 4 4
1 1 1 1 1 1 1 1 1 1 1 2 3 4 5
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2

After that, it was a matter of travelling through the 2-D array.

The note at the bottom of the problem warns that #67 is similar but
with 100 rows that can't be done using brute force. I suspect that the
key to a solution here might be to save calculations as you try
different paths so that you actually don't have to work out the answer
to the bottom.

Or maybe, after calculating the paths, finding for each row in the 2-D
array the highest number, which gives you a path, that may or may not
work, but from which perhaps you can approximate one in the list?

Who knows, #67 is far away for me. For now, on to #19.

Andrew.

On Sun, Jul 13, 2008 at 12:31 AM, kinuthiA muchanE <muchanek at gmail.com> wrote:
> Andrew,
> I tried doing it manually and I can assure you it was not pretty, there
> are just too many places you can go wrong...or you could be lucky, you
> never know :-/. I am trying number 80 it is too easy, but apparently I
> can not get my decimals right!:-(
>
>
> Kinuthia...
> On Sat, 2008-07-12 at 19:16 -0400, Andrew Mathenge wrote:
>> I switched to C/C++ when I realised that perl was going to make me
>> grey before anything came out.
>>
>> I might do what you did with #18 but right now I have a pad full of
>> numbers, notes, lines and many other scribbles. I'm looking for some
>> sort of logic. If I don't have an "eureka" moment, then I'll create
>> that multi-dimensional array and brute force my way through it.
>>
>> Alternatively, I can do it manually, but that will make me feel less of a man.
>>
>> Andrew.
>>
>> On Sat, Jul 12, 2008 at 4:53 PM, kinuthiA muchanE <muchanek at gmail.com> wrote:
>> > Habari,
>> > ... and what language are you using Mathenge? Perl? #18 proved to be too
>> > demanding for me, actually I skipped it all together with #15, I only
>> > solved them yesterday!! The best way, IMHO, to solve #18 is to have a
>> > multi-dimensional array, or in Python a list of lists, and then realise
>> > that you are either at the end or at the beginning of the array...Oh
>> > my... that sounds obscure!
>> > :-/
>> > Kinuthia...
>> > On Sat, 2008-07-12 at 15:13 -0400, Andrew Mathenge wrote:
>> >> Until you posed question #26 I didn't even know project euler existed
>> >> Bwana Kinuthia, but I'm trying my best.
>> >>
>> >> Right now #18 is killing me trying to solve it without brute force.
>> >> And I agree. Zacharia did a great job with #12. Mine took forever.
>> >>
>> >> Zacharia, sign up.
>> >>
>> >> The dance continues....
>> >>
>> >> On Sat, Jul 12, 2008 at 1:15 PM, kinuthiA muchanE <muchanek at gmail.com> wrote:
>> >> > Habari wote,
>> >> >
>> >> > Now, this is getting lively, and I think Zacharia is the teacher all of
>> >> > us have been longing for :-) Step by step, you elucidate all the
>> >> > underling principles. I thought nobody ever reads this, I am mistaken.
>> >> > Zacharia, why dont you subscribe to project Euler
>> >> > (http://projecteuler.net ) and at least I will not be leading in the
>> >> > list Kenyans who have solved the most problems, only 52, the last time I
>> >> > looked.
>> >> > And to Andrew (ha... you are at 17 ),  you ask a question and then
>> >> > disappear!! Hmmmm, and where is Miano??
>> >> >
>> >> > Cheers!!
>> >> > Kinuthia...
>> >> >
>> >> >
>> >> >
>> >> > On Sat, 2008-07-12 at 07:16 -0700, Zacharia M. Rugongo wrote:
>> >> >> This email is from a ubuntu-ke subscriber to other subscribers inluding you:)
>> >> >> My solution to Euler #12 runs in less than 1 minute.
>> >> >>
>> >> >>
>> >> >> Let us list the factors of the first eight triangle numbers:
>> >> >>  1: 1
>> >> >>  3: 1,3
>> >> >>  6: 1,2,3,6
>> >> >> 10: 1,2,5,10
>> >> >> 15: 1,3,5,15
>> >> >> 21: 1,3,7,21
>> >> >> 28: 1,2,4,7,14,28
>> >> >> 36: 1,2,3,4,6,8,9,12,18,36
>> >> >> Note the numbers that are underlined in each sequence. This is the half way point.
>> >> >> a)  If you divide the triangle number by the first number that is underlined the result will be greater than the divisor.
>> >> >> b)
>> >> >> On the other hand if you divide the triangle number by the second
>> >> >> number that is underlined the result will be less than the divisor.
>> >> >> c)
>> >> >> The triangle number 36 has only one number at the centre of the
>> >> >> sequence, because that centre number is the square root of the triangle
>> >> >> number 36.
>> >> >>
>> >> >> In
>> >> >> cases a) and b) if you wanted to know the total number of divisors, you
>> >> >> look for the position of the number underlined as described in b), then
>> >> >> subtract 1 from it, then multiply it by 2. For example, for triangle
>> >> >> number 28, value 7 is in position 4. So (4-1) * 2 = 6
>> >> >>
>> >> >> In
>> >> >> cases c) if you wanted to know the total number of divisors, you look
>> >> >> for the position of the center number underlined, then multiply it by
>> >> >> 2. For example, for triangle number 36, value 6 is in position 5.
>> >> >> So 5 * 2 = 10
>> >> >>
>> >> >> Here is the program.
>> >> >>
>> >> >>
>> >> >> Dim triagNo As Integer              ' Triangle number
>> >> >> Dim counter As Integer              ' for calculating the next triangle number
>> >> >> Dim varValue As Integer            ' Incremented in search for a Divisor
>> >> >> Dim NoDivisors As Integer        ' number of Divisors found
>> >> >> Dim Divisor As Integer              ' Value of found Divisor
>> >> >>
>> >> >> Do
>> >> >>    counter += 1
>> >> >>    triagNo = triagNo + counter
>> >> >>    varValue = 0
>> >> >>    Divisor = 0
>> >> >>    NoDivisors = 0
>> >> >>
>> >> >>       Do
>> >> >>          varValue += 1
>> >> >>          If triagNo Mod varValue = 0 Then                    ' is varValue a Divisor
>> >> >>          Divisor = varValue
>> >> >>          NoDivisors += 1
>> >> >>         End If
>> >> >>      Loop Until (triagNo / Divisor) <= Divisor               ' Find when you reach the second centre value
>> >> >>
>> >> >>      If (triagNo / Divisor) = Divisor Then
>> >> >>         NoDivisors = (NoDivisors - 1) * 2 + 1                  ' cases a) and b)
>> >> >>     Else
>> >> >>         NoDivisors = (NoDivisors - 1) * 2                        ' case c)
>> >> >>     End If
>> >> >>
>> >> >> Loop Until (NoDivisors > 500)
>> >> >>
>> >> >> TextBox1.Text = triagNo
>> >> >>
>> >> >>
>> >> >> Z. Mwangi
>> >> >>
>> >> >>
>> >> >>
>> >> >> ----- Original Message ----
>> >> >> From: Andrew Mathenge <mathenge at gmail.com>
>> >> >> To: ubuntu Kenya <ubuntu-ke at lists.ubuntu.com>
>> >> >> Sent: Friday, July 11, 2008 3:24:23 AM
>> >> >> Subject: Re: Euler Problems
>> >> >>
>> >> >> This email is from a ubuntu-ke subscriber to other subscribers inluding you:)
>> >> >> I've been working on #12 and the performance is simply not acceptable.
>> >> >> Has anyone been able to get this running as fast as some of the posts
>> >> >> on the site claim?
>> >> >>
>> >> >> Andrew.
>> >> >>
>> >> >> On Tue, Jul 8, 2008 at 12:40 PM, kinuthiA muchanE <muchanek at gmail.com> wrote:
>> >> >> > Andrew,
>> >> >> > For #10, if you do not use a sieve to find the primes, it will run
>> >> >> > forever!
>> >> >> > There is one called the Sieve of Erastothenes. Check it out on
>> >> >> > Wikipedia.
>> >> >> >
>> >> >> > Good luck :-)
>> >> >> > Kinuthia...
>> >> >> > On Tue, 2008-07-08 at 10:47 -0400, Andrew Mathenge wrote:
>> >> >> >> I'm still trying them. I started at #1 after the one you proposed
>> >> >> >> (#26) and I'm at #10 now. This one should be very simple but I don't
>> >> >> >> know why it's taking so long to run.
>> >> >> >>
>> >> >> >> Andrew.
>> >> >> >>
>> >> >> >> On Tue, Jul 8, 2008 at 6:52 AM, kinuthiA muchanE <muchanek at gmail.com> wrote:
>> >> >> >> > Habari,
>> >> >> >> > Anybody still trying these problems, you are all so, so silent...
>> >> >> >> >
>> >> >> >> > Kinuthia...
>> >> >> >> >
>> >> >> >> >
>> >> >> >
>> >> >> >
>> >> >>
>> >> >> --
>> >> >> Ubuntu-ke mailing list
>> >> >> Ubuntu-ke at lists.ubuntu.com
>> >> >> https://lists.ubuntu.com/mailman/listinfo/ubuntu-ke
>> >> >>
>> >> >>
>> >> >>
>> >> >>
>> >> >> -------------- next part --------------
>> >> >> An HTML attachment was scrubbed...
>> >> >> URL: https://lists.ubuntu.com/archives/ubuntu-ke/attachments/20080712/e8965b59/attachment.htm
>> >> >
>> >> >
>> >
>> >
>
>

More information about the Ubuntu-ke mailing list