Jump to content

Sky Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate
Photo

Project Euler with ahk


  • Please log in to reply
17 replies to this topic
System Monitor
  • Members
  • 508 posts
  • Last active: Mar 26 2012 05:13 AM
  • Joined: 09 Mar 2007
I have solved 17 of 264 Project Euler programming problems.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.


I thought you guys might like this site and we could share the methods you used to achieve the answer. Do not post the answers though. Have fun!

Problem 1
three = 3
five = 5
sum = 0
x=1
Loop,999
{
isnatt := x/three
isnatf := x/five
Stringright,iszerot,isnatt,1
StringReplace,isnatf,isnatf,00000
Stringright,iszerof,isnatf,1

if iszerot = 0
{
sum := x + sum
x++
continue
}

if iszerof = 0
{
sum := x + sum
x++
continue
}
x++
}
msgbox %sum%

Problem 9
n = 1
m = 1
loop 1000 ;n loop
{
	loop 1000 ;m looop
	{
		if (m > n)
			break
		a :=  (n*n) - (m*m)
		b := 2*m*n
		c := (n*n) + (m*m)
		total := a+b+c
		if total = 1000
		{
			product := a*b*c
			msgbox product=%product% a=%a% b=%b% c=%c%
		}
		m++
	}
	m := 1
	n++
}

I will post more answers later.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Good start! These can make AHK more popular.
However, you can write more compact code, like these for Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.
Loop 999
   sum += mod(A_Index,3) && mod(A_Index,5) ? 0 : A_Index
MsgBox %sum%
Or:
Loop 999
   sum += (!mod(A_Index,3) || !mod(A_Index,5)) * A_Index
MsgBox %sum%


Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
Your solution to Problem 9 (Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000) is clever! You can make it still faster, with the observation that n,m < 32, otherwise c would be over 1000. Instead of checking if n>m, you can enforce this with adding indices to m to generate n:
Loop 31 { ; m**2 < c < 1000
   m := A_Index
   Loop % 31-m {
      n := m+A_Index ; n > m
      a := n*n - m*m
      b := 2*m*n
      c := n*n + m*m
      if (a+b+c = 1000)
         MsgBox % "product=" a*b*c " a=" a " b=" b " c=" c
   }
}
We don't even need a computer. Add the expressions for a, b and c, which should be 1000. Solving it for m we get m = 500/n - n, so n must be a divisor of 500. It allows only prime factors of 2 and 5 in n, leaving n = 1, 2, 4; 5, 10, 20; 25. The condition m<32 (which translates to n**2+32n > 500) precludes small n values, leaving only 20 and 25 to try. The condition m>0 rules out n=25, so the only solution is:
n = 20
m = 500/20-20 = 5
a = 20*20-5*5 = 375
b = 2*20*5 = 200
c = 20*20+5*5 = 425

System Monitor
  • Members
  • 508 posts
  • Last active: Mar 26 2012 05:13 AM
  • Joined: 09 Mar 2007
Thanks Laszlo!
I have created a wiki page so that everyone can edit an add their code.
http://www.autohotke...e=Project_Euler
If you add the answer to a problem please also post it on the forum.
I don't know how to make the code not go into the "boxes" without removing the tabbing. Could any body familiar with wiki markup help with that?

trik
  • Members
  • 1317 posts
  • Last active: Jun 11 2010 11:48 PM
  • Joined: 15 Jul 2007
Has anyone had any success on problem 5? I wrote a script that /should/ work, but it is too slow. I rewrote the script in Python, but it is still too slow for me :/

Code I am using:

; AutoHotkey
SetBatchLines, -1

Loop {
	t := A_Index, d := 0
	Loop 19 {
		If (Mod(t, A_Index + 1) == 0)
			d++
		If (d == 19) {
			Answer := t
			Break := True
		}
	}
	IfEqual, Break, True, Break
}

MsgBox %Answer%

# Python
while (True):
    t += 1
    d = 0
    for i in xrange(19):
        if t % (i + 1) == 0:
            d += 1
        if d == 19:
            b = True
    if b == True:
        break
print t

Religion is false. >_>

BoBo³
  • Guests
  • Last active:
  • Joined: --

I don't know how to make the code not go into the "boxes" without removing the tabbing. Could any body familiar with wiki markup help with that?

:arrow:

Leading spaces are another way to preserve formatting.

:arrow: [Help]

BoBo³
  • Guests
  • Last active:
  • Joined: --
[Help] Hope this one won't get redirected to the homepage too :roll:

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005

Has anyone had any success on problem 5?

Problem 5 (What is the smallest number divisible by each of the numbers 1 to 20?) is another example where you don't need a computer. The answer is the product of all primes less than 20, each on the maximum power, which is still less than 20: 2^4*3^2*5*7*11*13*17*19 = 232,792,560. (Here ^ denotes "power-to".)

Finding it with testing all integers is slow. You can speed up the search by testing only multiples of 16, or 16*9, or 16*9*5 etc., but taking it to the extreme leads to the direct solution above.

Here is a shorter blind search script. You can speed it up with setting d to larger than 1 as commented, or dropping superfluous mod tests:
d := 1, n := d ; or d:= 16, 16*9, 16*9*5...
While (mod(n,2) || mod(n,3) || mod(n,4) || mod(n,5) || mod(n,6) || mod(n,7) || mod(n,8) || mod(n,9) || mod(n,10) || mod(n,11)
    || mod(n,12) || mod(n,13) || mod(n,14) || mod(n,15) || mod(n,16) || mod(n,17) || mod(n,18) || mod(n,19) || mod(n,20))
   n += d
MsgBox %n%
It is enough to test if n is divisible by all integers 11...20, because the numbers in 1..10 divide at least one of 11..20. This gives a factor of 2 speedup.

System Monitor
  • Members
  • 508 posts
  • Last active: Mar 26 2012 05:13 AM
  • Joined: 09 Mar 2007
Problem 6
x=1
answer = 0
loop, 100
{
    answers += x*x
    answera += x
    x++
}
answera := answera*answera
total := answera - answers
msgbox %total%


Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
To verify the result: the sum of the integers from 1 to n is n*(n+1)/2. The sum of the squares of these integers is n*(n+1)*(2n+1)/6. Problem 6 is the difference of the square of the first expression and the second one, which can be simplified to n*(n-1)*(n+1)*(3n+2)/12. Substitute n=10: 10*9*11*32/12 = 2640; or n=100: 100*99*101*302/12 = 25,164,150.

System Monitor
  • Members
  • 508 posts
  • Last active: Mar 26 2012 05:13 AM
  • Joined: 09 Mar 2007
Btw if you create an account you can submit the answers and it will tell you if you are correct.

Laszlo
  • Moderators
  • 4713 posts
  • Last active: Mar 31 2012 03:17 AM
  • Joined: 14 Feb 2005
I meant with the exact formula YOU can verify your code yourself.

System Monitor
  • Members
  • 508 posts
  • Last active: Mar 26 2012 05:13 AM
  • Joined: 09 Mar 2007
Problem 8
; [color=red]IMPORTANT[/color]
; Set the variable digits equal to the number you are supposed to parse
digits := 
x = 1
high = 0
Loop, 995
{
    fivenumbers := SubStr(digits,x,5)
    StringSplit,num,fivenumbers
    ishigh := num1*num2*num3*num4*num5
    if (high < ishigh)
    {
        high := ishigh
    }
    x++
}
Msgbox, %high%


  • Guests
  • Last active:
  • Joined: --
Well, while we are posting code.. Here is the solution for problem two. One I had a little trouble with before I realized my mistakes.

Answer := 0, Num1 := 0, Num2 := 1
While (Num1 < 4000000) {
	Num3 := Num1 + Num2
	If (Mod(Num1, 2) == 0)
		Answer += Num1
	Num1 := Num2, Num2 := Num3
}

MsgBox %Answer%


tonne
  • Members
  • 1654 posts
  • Last active: May 06 2014 06:22 PM
  • Joined: 06 Jun 2006
; to solve problem 1 without loop 

; #    3   5  15

; 1    

; 2

; 3    3 

; 4 

; 5        5

; 6    6

; 7

; 8

; 9    9

; 10      10

; 11

; 12  12

; 13

; 14

; 15  15  15  15

; to calculate the sum of multiples of 3

; numbers: n = floor(15/3) = 5 

; average: a = 3*(n+1)/2 = 9

; sum_3 = n*a = 45

; for multiples of 5

; numbers: n = floor(15/5) = 3

; average: a = 5*(n+1)/2 = 10

; sum_5 = n*a = 30

; for multiples of 15 (which must be subtracted)

; numbers: n = floor(15/15) = 1

; average: a = 15*(n+1)/2 = 15

; sum_15 = n*a = 15

; sum=sum_3+sum_5-sum_15

; thus

; msgbox % 3.0*3.0*(floor(999.0/3.0)+1.0)/2.0

SetFormat,Float,.0

sum := calc(999.0,3.0) + calc(999.0,5.0) - calc(999.0,15.0)

msgbox %sum%



calc(n,m)

{

  c := floor(n/m)

  return (c * m *(c+1.0)/2.0)

}