Project Euler...

[pdwyer]

How would you solve #48

Here's my solution:

Code: Select all

#Title = "Problem 48"

#Mod = 10000000000
  
Result.q = 1
  
For i = 2 To 999
  If i % 10
    a.q = i
    For j = 1 To i - 1
      a = (a * i) % #Mod
    Next
    Result = (Result + a) % #Mod
  EndIf
Next

MessageRequester(#Title, "Result = "+StrQ(Result))

Kind regards,

Francis.

I don't understand this. I was trying to do this any my PC was taking 1min to do 400, 4mins to do 500, 1000 didn't finish in 20mins so I killed it.

Whats the code above doing? I'm not even sure what a,j & i are supposed to mean

[pdwyer]

Not giving up. Going back to my own code using huge numbers, I have found an optimisation that adds about 25x the speed to generating powers.

Previously I had this: (but 20mins didn't finish problem 48 so I killed it)

Code: Select all

Procedure.s BigPowOld(Num.s, pow.l)

    Answer.s = Num
 
    If pow = 1 ;
        Answer = num
    Else
        For i = 1 To pow - 1
            Answer = BigMultiply(Num, Answer )   
        Next
    EndIf
    
    ProcedureReturn Answer

EndProcedure

Now I have a recursive version that completes in 100secs, a little more and I'm there.

The best thing about this is that I understand it

Code: Select all

Procedure.s BigPow(Num.s, pow.l)

    If pow = 1 ;
        ProcedureReturn num
    ElseIf pow = 2
        ProcedureReturn BigMultiply(Num, Num)
    ElseIf pow = 3
        ProcedureReturn BigMultiply(Num, BigPow(Num,2))
    Else  
        If pow % 2 = 0
            ProcedureReturn BigMultiply(BigPow(Num,pow / 2), BigPow(Num,pow / 2))  
        Else
            ProcedureReturn BigMultiply(BigMultiply(BigPow(Num,pow / 2), BigPow(Num,pow / 2)),num)  
        EndIf
    EndIf
    
EndProcedure

[Dreamland Fantasy]

How would you solve #48

Here's my solution:

Code: Select all

#Title = "Problem 48"

#Mod = 10000000000
  
Result.q = 1
  
For i = 2 To 999
  If i % 10
    a.q = i
    For j = 1 To i - 1
      a = (a * i) % #Mod
    Next
    Result = (Result + a) % #Mod
  EndIf
Next

MessageRequester(#Title, "Result = "+StrQ(Result))

Kind regards,

Francis.

I don't understand this. I was trying to do this any my PC was taking 1min to do 400, 4mins to do 500, 1000 didn't finish in 20mins so I killed it.

Whats the code above doing? I'm not even sure what a,j & i are supposed to mean

That's strange that it should take so long to complete. On any of the computer's I've tried it completes almost instantaneously (even with the debugger on).

Variables i and j have always been standard notation for doing loops in programming. This is a throw back to the days when you could only have a single letter for variable names and letters a-h were already used for something else. Anyway, I digress.

In this instance I have used i as the number counter of 2 to 999 (1 is catered for already in Result). j I have used as the loop for calculating i^i rather than using the Pow() command. The '% #Mod' at the end of two of the lines ensures that we only deal with the last 10 digits (since this is the only part we are interested in) for reasons of speed and to ensure that there is no numerical overflow.

The variable a you can take as being the answer of i^i which is then added to Result.

I have also added an optimisation in the form of 'If i % 10' since if i is a multiple of 10 then any number that you obtain from i^i under this circumstance will produce a number where the last 10 digits will be zeroes.

I hope that sheds some light onto what my code is doing.

Kind regards,

Francis.

[pdwyer]

badly worded on my part.

I meant just doing it the raw way

1^1 + 2^2 ... 1000^1000

your way is very fast but I don't undertand how it works.

In the end I got my huge number functions to crack this out in 80sec, then put it into two threads with one doing 1-800 and the other doing 801-1000 and adding the result which I got out in 47secs in the end

no where near is good as yours but I understand it and it helped my optimise my huge number functions for add, multiply and pow()

The answer is 3000+ digits long so it was good exercise for my functions found a lot of bugs

[pdwyer]

ahhhhh

now I understand your code. I didn't think of that. clever.

I was thinking it was some complex math idea about mods and pows that I didn't know. but it's not.

[Dreamland Fantasy]

ahhhhh

now I understand your code. I didn't think of that. clever.

I was thinking it was some complex math idea about mods and pows that I didn't know. but it's not.

Glad I could help!

Kind regards,

Francis.

[Michael Vogel]

In the end I got my huge number functions to crack this out in 80sec, then put it into two threads with one doing 1-800 and the other doing 801-1000 and adding the result which I got out in 47secs in the end

Just is someone like to compare with own solutions, I did also a "long version" of the code - because there was not a lot to modify the simple way (except a single MOD ...

It uses my VNF routines (by the way, I still had no time to write a nice DIV routine, so maybe someone like to...)

Code: Select all

; Define VNF - Vogels Number Format

	#VNFDim=10000; ~90000 Ciphers ;)

	Structure VNF
		len.w
		sign.w
		num.l[#VNFDim]
	EndStructure

	; Signs
	#VNFNegative=-1
	#VNFPositive=0

	; Dimensions
	#VNFLen=9
	#VNFMod=1000000000

	Declare.s Number(*num.VNF);					String
	Declare PutNumber(*s.s,*num.VNF);			s -> num
	Declare VNFMuW(*a.VNF,b.l,*c.VNF);			c = a*b, |b|<10^10
	Declare VNFAdd(*a.VNF,*b.VNF,*c.VNF);  	c = a+b

; EndDefine

Procedure.s Number(*num.VNF)

	Protected n
	Protected t.s

	If *num\sign
		t="-"
	EndIf

	n=*num\len
	t+Str(*num\num[n])

	While n>0
		n-1
		t+RSet(Str(*num\num[n]),#VNFLen,"0")
	Wend


	ProcedureReturn t

EndProcedure
Procedure GetNumber(*s.String,*num.VNF)

	; ACHTUNG! s ist bei dieser Routine vom Typ String!
	; (bei x.string bedeutet dies den Aufruf "GetNumber(x,number)" und die Ausgabe "Debug x\s")

	Protected n
	Protected t.s

	If *num\sign
		t="-"
	EndIf

	n=*num\len
	t+Str(*num\num[n])

	While n>0
		n-1
		t+RSet(Str(*num\num[n]),#VNFLen,"0")
	Wend

	*s\s=t

EndProcedure
Procedure PutNumber(*s.s,*num.VNF)

	Protected n,p
	Protected t.s

	*num\sign=0

	t=PeekS(@*s)
	n=Len(t)-#VNFLen

	While n>0
		*num\num[p]=Val(PeekS(@t+n,#VNFLen))
		p+1
		n-#VNFLen
	Wend

	n=Val(PeekS(@t,9+n))
	If n<0
		*num\sign=#VNFNegative
		n=-n
	EndIf

	*num\num[p]=n

	*num\len=p

EndProcedure

Procedure VNFMuW(*a.VNF,b,*c.VNF)

	Protected n
	Protected m.q

	n=*a\len

	If b=0
		*c\len=0
		*c\sign=#VNFPositive
		*c\num[0]=0
	Else

		If b<0
			b=-b
			*c\sign=#VNFNegative-*a\sign
		Else
			*c\sign=*a\sign
		EndIf

		n=0
		Repeat
			m+*a\num[n] * b
			*c\num[n]=m%#VNFMod
			m/#VNFMod

			n+1
		Until n>*a\len

		If m
			*c\num[n]=m
		Else
			n-1
		EndIf
		*c\len=n

	EndIf

EndProcedure
Procedure VNFAdd(*a.VNF,*b.VNF,*c.VNF)

	Protected n
	Protected s

	*c\sign=*a\sign

	If *a\len<*b\len
		Swap *a,*b
	EndIf

	While n<=*a\len
		s+*a\num[n]
		If n<=*b\len
			s+*b\num[n]
		EndIf
		*c\num[n]=s%#VNFMod
		s/#VNFMod
		n+1
	Wend
	If s
		*c\num[n]=s
	Else
		n-1
	EndIf

	*c\len=n

EndProcedure


an.VNF
sn.VNF
s.s="0"
PutNumber(@s,sn)

For i=1 To 1000
	PutNumber(@"1",an)
	For j=1 To i
		VNFMuW(an,i,an)
	Next j
	VNFAdd(an,sn,sn)
Next i

s=Number(sn)

MessageRequester(Right(s,10),s)

[michaeled314]

Anyone have tips about manipulating permutations?

Example:

123
321
231
132

or

1234
1243
1324
1342
1423
1432
4321
3124
Something like that

[Dreamland Fantasy]

Anyone have tips about manipulating permutations?

Try this:

Code: Select all

Procedure.s Permutation(String$, n)
  
  Protected i, Factorial = 1, Temp
  
  For i = 2 To Len(String$)
    Factorial * (i - 1)
    Temp = PeekB(@String$ + (i - ((n / Factorial) % i) - 1))
    PokeB(@String$ + (i - ((n / Factorial) % i) - 1), PeekB(@String$ + i - 1))
    PokeB(@String$ + i - 1, Temp)
  Next
  
  ProcedureReturn String$
  
EndProcedure

MyString$ = "ABC"

i = 1
Repeat
  Permutation$ = Permutation(MyString$, i)
  Debug Permutation$
  i + 1
Until Permutation$ = MyString$

Kind regards,

Francis.

[pdwyer]

Very nice, I've been looking for something like this for a while as I've just always drawn a blank on a good way to code it

Cheers

[Dreamland Fantasy]

Very nice, I've been looking for something like this for a while as I've just always drawn a blank on a good way to code it

Cheers

Glad you like it!

It took me a few weeks to work out how to do those permutation problems and it caused me a few headaches in the process! :roll:

Kind regards,

Francis.

[Michael Vogel]

...I'm still lost with #110 and #118 (and some other problems), so I'll started with 154:

Code: Select all

Procedure Problem_154(n)

	#size=2000
	#mid=#size>>1
	minx=#mid
	miny=#mid
	maxx=#mid
	maxy=#mid

	#modulo=1000000000000

	Dim A.q(#size,#size);	(x+y+z)^n | n=0, 3, 6, ...
	Dim B.q(#size,#size);	(x+y+z)^n | n=1, 4, 7, ...
	Dim C.q(#size,#size);	(x+y+z)^n | n=2, 5, 8, ...

	#maxwerte=#size*#mid
	Dim werte.q(#maxwerte)
	Dim anzahl(#maxwerte)

	level=1
	B(#mid,#mid)=1

	Repeat

		level+1
		Select level%3

		Case 0
			maxx+1
			miny-1
			For x=minx To maxx
				For y=miny To maxy
					A(x,y)=(C(x-1,y+1)+C(x,y)+C(x,y+1));%#modulo
			
				Next y
			Next x

		Case 1
			minx-1
			miny+1
			maxy+2
			
			For x=minx To maxx
				For y=miny To maxy
					B(x,y)=(A(x,y-1)+A(x+1,y-2)+A(x+1,y-1));%#modulo
				Next y
			Next x

		Case 2
			maxx+1
			miny-1
			
			For x=minx To maxx
				For y=miny To maxy
					C(x,y)=(B(x,y+1)+B(x,y)+B(x-1,y+1));%#modulo
				Next y
			Next x
		EndSelect

	Until level=n


	found=0
	For i=0 To #maxwerte
		werte(i)=0
		anzahl(i)=0
	Next i

	l=level%3
	For x=minx To maxx
		For y=miny To maxy
			Select l
			Case 0
				d=A(x,y)
			Case 1
				d=B(x,y)
			Case 2
				d=C(x,y)
			EndSelect
			If d

				i=found
				While i
					If werte(i)=d
						Break
					Else
						i-1
					EndIf
				Wend
				If i
					anzahl(i)+1
				Else
					found+1
					werte(found)=d
					anzahl(found)+1
				EndIf

			EndIf

		Next y
	Next x

	For i=1 To found
		Debug StrQ(werte(i))+" x "+Str(anzahl(i))
	Next i
EndProcedure

Problem_154(5)

But also here I've some problems as well:

1) the modulo function return negative numbers (to check that, just remove the semicolon before the %#modulo statements)
2) the dim does not allow to build up such a huge array needed to calc the results

Does anyone know, what is the workaround for 1)?

Thanks,
Michael

[michaeled314]

Problem 160 was just released. Can you do it Michael Vogel? If you can then you'll be the guru (not that you aren't already ).

[Michael Vogel]

Problem 160 was just released. Can you do it Michael Vogel? If you can then you'll be the guru (not that you aren't already ).

Easy to see, that I'm definitely not a guru

A fast look at the problem brought me to the idea, that there will be no change between 100000!, 200000! etc. (but this is wrong )

Code: Select all

#modulo=100000

f=1
n=10
n=20
n=100000

While n
	a=n%#modulo
	If a
		f*a
		While f%10=0
			f=f/10
		Wend
		f%#modulo
	EndIf
	n-1
Wend

MessageRequester("...",Str(f))

But it's also not completely wrong (got it meanwhile.... http://projecteuler.net/index.php?secti ... file=11160)

Try to compare results for 10.000, 20.000 and so on, maybe you'll find a pattern
Michael

[Dreamland Fantasy]

...I'm still lost with #110 and #118 (and some other problems), so I'll started with 154:

Code: Select all

SNIP!

But also here I've some problems as well:

1) the modulo function return negative numbers (to check that, just remove the semicolon before the %#modulo statements)
2) the dim does not allow to build up such a huge array needed to calc the results

Does anyone know, what is the workaround for 1)?

Thanks,
Michael

I've had a quick look and one thing I noticed is that variable d should probably be declared as a quad. It still doesn't help you though, but it does get rid of the negative results.

I'll have a more thorough look when I get a chance.

Kind regards,

Francis.