Project Euler...

Michael Vogel · Post by **Michael Vogel** » Thu Jul 12, 2007 10:55 pm

mike74 wrote:A question that occurred to me while thinking about Problem 88: What is the best way to get a number's unique factorizations

Hmm, 88 is a heavy one - I solved it with putting all factors of a number into an array (hint: 15 factors are enough) and starting a recursive procedure which 'mixes' all factors to check all resulting product-sum lengths.

So, for 32 (=2x2x2x2x2) there are a lot of possibilities:
- 32
- 16 x 2
- 8 x 4
- 8 x 2 x 2
- 4 x 4 x 2
- 4 x 2 x 2 x 2
- 2 x 2 x 2 x 2 x 2

My idea to get these variations was to assign 'group numbers' to each factor. The first line above (32) means, that all factors have been assigned to a single group, the second (16 x 2) that 4 factors have been given into group 1 and the last factor into group 2 and so on...

Michael

*** EDIT *** once again, I was too late - mike solved it already

mike74 · Post by **mike74** » Thu Jul 12, 2007 11:22 pm

Michael,

That was my understanding of what your code was doing although I did find it difficult to understand exactly how it was doing it. When I looked at the way it was factorizing I realized that it was doing some redundant evaluations. For example, it factors 16 as both 2x8 and 8x2. I would think you could speed up your program by incorporating a method like the one in my previous post (which I just corrected so it will work with an odd input).

I see that you have seen it....

Mike

Michael Vogel · Post by **Michael Vogel** » Thu Jul 12, 2007 11:29 pm

mike74 wrote:I see that you have seen it....

Yep, and your code is really cool

small, powerful and fast

michaeled314 · Post by **michaeled314** » Thu Jul 12, 2007 11:41 pm

I tried to optimize my code all I could. I even enabled inline asm and changed a few commands to ASM, but I cannot get the answer to Problem 12 without having to wait hours

Dreamland Fantasy · Post by **Dreamland Fantasy** » Thu Jul 12, 2007 11:51 pm

michaeled314 wrote:I tried to optimize my code all I could. I even enabled inline asm and changed a few commands to ASM, but I cannot get the answer to Problem 12 without having to wait hours

Try this:

Code: Select all

Procedure Divisors(n.q)
  
  Protected i = 1, Result = 2
  
  Repeat
    i + 1
    If i >= n / i
      Break
    EndIf
    If n % i = 0
      Result + 2
    EndIf
  ForEver
  
  ProcedureReturn Result
  
EndProcedure

a = 1
b = 2

Repeat
  a + b
  b + 1
Until Divisors(a) > 500

MessageRequester("Project Euler", "Answer to problem 12: " + Str(a))

This completes in about 1.5 seconds on my system.

Kind regards,

Francis.

michaeled314 · Post by **michaeled314** » Fri Jul 13, 2007 12:47 am

Excuse me for my ignorance by what does the value a + b mean when it is by itself

Dreamland Fantasy · Post by **Dreamland Fantasy** » Fri Jul 13, 2007 12:57 am

michaeled314 wrote:Excuse me for my ignorance by what does the value a + b mean when it is by itself

It's a shorthand way of saying:

Code: Select all

a = a + b

Kind regards,

Francis

blueznl · Post by **blueznl** » Fri Jul 13, 2007 8:25 am

I've just started with this stuff but darn, it's sometimes difficult. I couldn't help though but notice that some people really take 'the long way' to solve a problem, whilst others go for a pure mathematical solution (I envy those minds).

I also find some of those problems to be more time consuming then I expected, and I don't mean the computational time but actually thinking up a solution

Code: Select all

; euler 4
;
max = 0
;
a = 999
While a > 1
  b = 999
  While b > 1
    ;
    q = a*b
    If q > max
      s.s = Str(q)
      l = Len(s)
      r = 1
      f = #True
      While l >= r
        If Mid(s,l,1) <> Mid(s,r,1)
          f = #False
        EndIf
        l = l-1
        r = r+1
      Wend
      If f = #True
        max = q
      EndIf
    Else
      b = 0
    EndIf
    b = b-1
  Wend
  a = a-1
Wend
;
Debug max

Michael Vogel · Post by **Michael Vogel** » Fri Jul 13, 2007 10:08 am

blueznl wrote: I also find some of those problems to be more time consuming then I expected, and I don't mean the computational time but actually thinking up a solution

Hi blueznl, good code!

Finding a tricky way to reduce computing time is really hard sometimes! (and with some problems, I still have no idea how to do it, even when I would have a pc running 1000 times faster than mine

)

Hope you've fun with these puzzles - I've solved 130 for now and give tiny hints if needed...

Michael

Michael Vogel · Post by **Michael Vogel** » Fri Jul 13, 2007 10:22 am

Dreamland Fantasy wrote:

Code: Select all

Procedure Divisors(n.q)
  
  :  
  Repeat
   :
   If i >= n / i
      Break
    EndIf
   :
  ForEver

Hi, Francis

I think your code can be tuned (only a little bit), if you try to get rid of the division within the loop...

Michael

Dreamland Fantasy · Post by **Dreamland Fantasy** » Fri Jul 13, 2007 4:37 pm

Michael Vogel wrote:
Dreamland Fantasy wrote:
Code: Select all
Procedure Divisors(n.q)
  
  :  
  Repeat
   :
   If i >= n / i
      Break
    EndIf
   :
  ForEver
  
 
Hi, Francis

I think your code can be tuned (only a little bit), if you try to get rid of the division within the loop...

Michael

I think that must have been during one of my late night coding sessions as I'm not too sure why I did it that way. I've changed it to the following code which is faster:

Code: Select all

Procedure Divisors(n.q)
  
  Protected i, Result = 2
  
  For i = 2 To n / i - 1
    If n % i = 0
      Result + 2
    EndIf
  Next
  
  ProcedureReturn Result
  
EndProcedure

Thanks for pointing that out!

Kind regards,

Francis.

Michael Vogel · Post by **Michael Vogel** » Fri Jul 13, 2007 10:44 pm

Dreamland Fantasy wrote:

Code: Select all

Procedure Divisors(n.q)
  
  Protected i, Result = 2
  
  For i = 2 To n / i - 1
    If n % i = 0
      Result + 2
    EndIf
  Next
  
  ProcedureReturn Result
  
EndProcedure

Confusing

- the local variable i should be initialized with 0 at the beginning of the procedure, so the for statement would include the term "n / 0" which is undefined.

But in fact, there is no error, so it seems, that Purebasic does not initalize the end condition of the for loop at the start but calculates it every loop (and so also n / i)

-- I didn't knew that...

So maybe (especially with bigger numbers) it will be faster to use one floating point function to calculate the square root than doing a lot of divisions (but now it seems that I start to split hairs

)...

Code: Select all

	x.q=1
	s.q=1
	d.q=0
	r.q=0

	Repeat
		x+1
		s+x
		n=0
		d=0
		r=Sqr(s)
		While d<=r
			d+1
			If s%d=0
				n+2
			EndIf
		Wend
	Until n>500

Dreamland Fantasy · Post by **Dreamland Fantasy** » Fri Jul 13, 2007 11:23 pm

Michael Vogel wrote:Confusing - the local variable i should be initialized with 0 at the beginning of the procedure, so the for statement would include the term "n / 0" which is undefined. But in fact, there is no error, so it seems, that Purebasic does not initalize the end condition of the for loop at the start but calculates it every loop (and so also n / i) -- I didn't knew that...

Actually that was quite unintentional.

I had rewrote the routine quickly during my teabreak at work and for some reason I hadn't noticed or thought about the implications of the i variable. The way I've written it is quite bad programming practice in my opinion. :roll:

I guess I'll need to rewrite it again, but not just now because I am far far too tired (I've been burning the candle at both ends all week!

).

Kind regards,

Francis.

Michael Vogel · Post by **Michael Vogel** » Fri Jul 13, 2007 11:39 pm

Dreamland Fantasy wrote:...I am far far too tired (I've been burning the candle at both ends all week! )

Relax! And have a nice (lazy) weekend

Michael

Michael Vogel · Post by **Michael Vogel** » Thu Jul 26, 2007 7:24 pm

Pffh!

only one additional solved: #144 - one of the few puzzles not to solve with integer math (I advice to use variables with double precision - .d)

Michael
____

http://projecteuler.net/index.php?secti ... file=11160[/u]