Project Euler

[kon]

Project Euler Discussion Thread
Do not post unencrypted solutions.

General:
This thread is for general discussion, hints, tips, or anything related to solving Project Euler problems using AHK. Solutions posted here should be encrypted using the correct answer as the password.

Topics of Discussion:

• Problems you have recently solved.
• Problems you are stuck on.
• Ask for a hint.
• The Project Euler website.
• AHK's ranking.
• Share your Project Euler username or your Friend Code.
• Share links to solutions you have posted on the Project Euler forum.
  Note: "Only the first one hundred posts are automatically made permanent. After this only the most recent one hundred posts are kept; older posts will be automatically deleted."
• Anything related to Project Euler as long as it does not spoil anything for other users.
  Use spoiler tags for hints and encrypt full solutions.

Hints - Suggested Format:
Hints should always be posted in spoiler tags. Try not to give too much away. Examples of hints are links to AHK commands, Wikipedia articles, or descriptions of general ideas. Include a title so the subject is evident before clicking the spoiler button.

Hint for problem #1:

Spoiler

A suggestion for how to go about solving problem #1.

Why Encrypt Solutions?:

Q: I learned so much solving problem XXX so is it okay to publish my solution elsewhere?
A: It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

Encrypting / Decrypting Solutions:
A how-to for encrypting and decrypting solutions posted in this thread. This method will use nnnik's encryption functions from here: http://ahkscript.org/boards/viewtopic.p ... =493#p4175

Encryption:

1. Create a new AHK scrip. Copy and paste this code into it, or click the Download button:

   Code: Select all

   ;Encrypt text from the clipboard
   InputBox, Pass, Password Required, Enter a Password,, 300, 140
   Loop, % (StrLen(Clipboard) // 50)  + 1 {
      String .= A_Index = 1 ? "" : "`t`t. "
      String .= """" StrEncrypt(SubStr(Clipboard, ((A_Index - 1) * 50) + 1, 50), Pass, 5) "``n""`r`n"
   }
   MsgBox, % Clipboard := String
   return
   
   ;nnnik's functions or #Include go here.

2. Copy nnnk's encryption functions, available here. Paste them into the new script or #Include them. The encryption functions should go at the end of the script.
3. Copy the text that will be encrypted onto the clipboard.
4. Run the script that was just created (above).
5. Enter a password when prompted. This will be the same password used for decryption later.
6. Click OK. The encrypted text should be shown in a message box and placed on the clipboard.

Posting Encrypted Text:

1. Create a new AHK script. Copy and paste this code into it, or just click the Download button:

   Code: Select all

   String := "B88CA3190215DAF7D17C16CB2CF5FEEF3DEF19949447B629F3ED501BBFED941A0713E77F5A10B70561CA554C42D48826C25C192301F4`n"
           . "0E2DFF29B62A12F6CCF4A337382AEA272C7F6F0EFB4B4B82535B091E1008EC0DC6522DAC24746A5CA244DC09DAE534CD9FA78ADB01F4`n"
   
   InputBox, Pass, Password Required, Enter the answer to problem XX.,, 300, 140
   Loop, Parse, String, `n, `n
       result .= StrDecrypt(A_LoopField, pass)
   MsgBox, % Clipboard := result
   return
   
   ;nnnik's functions or #Include go here.

2. Replace the encrypted text "B88CA3190215DAF7D17C16CB2CF5FEEF3DEF199... with the text you have encrypted (see previous steps).
3. Change the text in the input box InputBox, Pass, Password Required, Enter the answer to problem XX.,, 300, 140
4. Post your code. You don't need to post nnnik's functions when you post your code. Just mention that those were the functions you used, and where to get them. People can copy and paste or #Include the functions themselves, no need to repost them in every script.

Decrypting Solutions:
(Assuming they were encrypted with nnnik's functions and a method similar to the one described above.)

1. Create a new script. Copy and paste the code you wish to decrypt into it. Or just click the Download button.
2. Copy and paste nnnik's functions into the new script and place them at the end, or #Include.
3. Run the script and enter the password when prompted. The unencrypted text should then be shown in a message box and placed on the clipboard.

Thanks to @smorgasbord for suggesting this thread.

[smorgasbord]

Thanks @k0n
may be just my view we post solutions if any in spoiler tags?

[nnnik]

No they have to be encrypted with the correct awnswers.
I just did the first 5 and think its quite interesting.

[smorgasbord]

@nnnik
Show an example please

[nnnik]

Code: Select all

String:="F91EDA156FE904C08FF2064E2DAA287DB6173277FBC478A29125A32D58F2206B75DBE308CFB42C4D7D854FF109E5C984626AD33280841FB1B703F9FF977B43B2795186CDB569CDD9631C9AC2CB5A4D92A0DF28A0D322E0BC37DF8CF7A006E2BBF042BA2BA34E88B74679C76FC8D4C965A0EAEB165B093318EE124652926218B92B95AD01D67C2F8D9117A99F8A9481B60005"

InputBox,Pass,PassRequired,Type in the correct value of problem 5.
Msgbox % StrDecrypt(string,pass)

StrEncrypt(Str,Pass="",Quality=1)
{
Strarr:=[]
PWARR:=[]
Loop,Parse,str
    Strarr.Insert(asc(A_LoopField))
Loop,Parse,Pass
    PWARR.Insert(asc(A_LoopField))
StrArr:=FilterAlgid(StrArr,PwArr,Quality)
s:=""
For each,val in StrArr
    s.=UShortToHex(val)
return s
}

StrDecrypt(Str,Pass="")
{
Strarr:=[]
PWARR:=[]
Loop, % strlen(str)//4
    Strarr.Insert(HexToUShort(SubStr(Str,(A_Index-1)*4+1,4)))
Loop,Parse,Pass
    PWARR.Insert(asc(A_LoopField))
StrArr:=FilterRemoveAlgid(StrArr,PwArr)
s:=""
For each,val in StrArr
   s.=chr(val)
return s
}


FilterAlgid(StrArr,PwArr,Quality=1,modvar=0x10000)
{
Strarr:=strarr.Clone()
PwArr:=Pwarr.Clone()
Strarr:=Filter3(StrArr,modvar)
Loop, % Quality+1
{
PWArr:=Filter1(PWArr,0,modvar)
PWArr:=Filter2(PWarr,0)
buf:=Calcbuf(PWarr,modvar)
strarr:=Filter1(strarr,buf,modvar)
strarr:=Filter2(strarr,buf)
}
strarr.insert(Quality)
return strarr
}

FilterRemoveAlgid(StrArr,PwArr,modvar=0x10000)
{
bufarr:=[]
Strarr:=strarr.Clone()
PwArr:=Pwarr.Clone()
Quality:=strarr[strarr.maxindex()]
strarr.remove()
Loop % Quality+1
{
PWArr:=Filter1(PWArr,0,modvar)
PWArr:=Filter2(PWarr,0)
bufarr.insert(Calcbuf(PWarr,modvar))
}
Loop, % Quality+1
{
strarr:=Filter2Remove(strarr,bufarr[Quality+2-A_Index])
strarr:=Filter1Remove(strarr,bufarr[Quality+2-A_Index],modvar)
}
Strarr:=Filter3Remove(StrArr,modvar)
return strarr
}

Calcbuf(arr,modvar=0x100000000)
{
    buf:=0
    lastnum:=0
    Loop, % arr.Maxindex()
    {
      For each,val in arr
        buf:=mod((val*(buf+1))+val,modvar)
    }
return buf
}

Filter1(arr,buf,modvar=0x100000000)
{
    lastnum:=0
    arr:=arr.Clone()
    Loop, % arr.Maxindex()
    {
      buf:=mod(mod(buf+lastnum+A_Index,modvar)*(buf+1)*(lastnum+1)*mod(A_Index,modvar)*255,modvar)
	  arr[A_Index]:=mod(buf+(lastnum:=arr[A_Index]),modvar)
    }
return arr
}
 
Filter1Remove(arr,buf,modvar=0x100000000)
{
    lastnum:=0
    arr:=arr.Clone()
    Loop, % arr.MaxIndex()
    {
      buf:=mod(mod(buf+lastnum+A_Index,modvar)*(buf+1)*(lastnum+1)*mod(A_Index,modvar)*255,modvar)
       arr[A_Index]:=lastnum:=min(mod(arr[A_Index]-buf,modvar),modvar)
    }
return arr
} 
 
Filter2(arr,PWVar=0)
{
v2:=[],s:=[],buf:=0
x:=arr.Maxindex()
Loop, % x
    s[A_Index]:=A_Index
Loop, % x
    n:=Floor(mod(buf+PWVar,s.Maxindex())+1),w:=s[n],buf:=(v2[w]:=arr[x-A_Index+1]),s.Remove(n,n)
return v2
}
 
Filter2Remove(arr,PWVar=0)
{
v2:=[],s:=[],buf:=0
x:=arr.Maxindex()
Loop, % x
    s[A_Index]:=A_Index
Loop, % x
    n:=Floor(mod(buf+PWVar,s.Maxindex())+1),w:=s[n],buf:=(v2[x-A_Index+1]:=arr[w]),s.Remove(n,n)
return v2
}

Filter3(arr,modvar)
{
cmin:=modvar
cmax:=0
spclmodvar:=1
vmod:=0
strl:=arr.Maxindex()
For each, val in arr
	cmin:=val<cmin?val:cmin,cmax:=val>cmax?val:cmax
while ((cmax-cmin)>spclmodvar-1)
	spclmodvar*=2,vmod:=A_Index
cmin-=(cmin+spclmodvar-1)>(modvar-1)?(cmin+spclmodvar-1)-(modvar-1):0
if (cmax-cmin)<(spclmodvar-1)
	Random,var,0,% (spclmodvar-1)-(cmax-cmin)
cmin-=var
cmin:=cmin<0?cmin:=0:cmin
If (vmod=0)
	return [strl>>16,strl-((strl>>16)<<16),cmin,0]
For each, val in arr
	arr[each]-=cmin
spclmodvar:=1
cmax:=""
vmod2:=""
while ((modvar-1)>spclmodvar-1)
	spclmodvar*=2,vmod2:=A_Index
arr2:=[]
rest:=0
For each, val in arr
{
    w:=ceil((A_Index*vmod)/vmod2)
	rest:=rest+vmod
	If (rest<=vmod2)
	{
		arr2[w]:=(arr2[w]?arr2[w]:0)+(val<<(vmod2-rest))
	}
	else
	{	
		rest:=(rest-vmod2)
		arr2[w-1]:=arr2[w-1]+(val>>rest)
		v:=val-((val>>rest)<<rest)
		arr2[w]:=(v<<(vmod2-rest))
	}
}
arr2.Insert(strl>>16)
arr2.Insert(strl-((strl>>16)<<16))
arr2.Insert(cmin)
arr2.Insert(vmod)
return arr2
}


Filter3Remove(arr,modvar)
{
arr2:=[]
cmin:=arr[arr.maxindex()-1]
vmod:=arr[arr.maxindex()]
strl:=arr[arr.maxindex()-2]+(arr[arr.maxindex()-3]<<16)
arr.remove()
arr.remove()
arr.remove()
arr.remove()
if !vmod
{
	if strl<0x5FFFFF
	Loop, % StrL
		arr2.Insert(cmin)
	return arr2
}
spclmodvar:=1
while ((modvar-1)>spclmodvar-1)
	spclmodvar*=2,vmod2:=A_Index
rest:=0
Loop % strl
{
    w:=ceil((A_Index*vmod)/vmod2)
	rest:=rest+vmod
	if ((rest)<=vmod2)
	{
		arr2[A_Index]:=arr[w]>>(vmod2-rest)
		arr[w]-=arr2[A_Index]<<(vmod2-rest)
	}
	else
	{
		rest:=(rest-vmod2)
		arr2[A_Index]:=arr[w-1]<<(rest)
		arr2[A_index]+=arr[w]>>(vmod2-rest)
		arr[w]-=((arr[w]>>(vmod2-rest))<<(vmod2-rest))
	}
}
For each, v in arr2
	arr2[each]+=cmin
return arr2
}
 
min(val,modvar=0xFFFFFFFF)
{
while val<0
    val+=modvar
return val
}

showarr(arr)
{
str2:="["
For each,key in	arr
	str2.=key "`,"
StringTrimright,str2,str2,1
str2.="]"
return str2
}

HexToUShort(str)
{
static d:={0:"0",1:"1",2:"2",3:"3",4:"4",5:"5",6:"6",7:"7",8:"8",9:"9","A":10,"B":11,"C":12,"D":13,"E":14,"F":15}
val:=0
Loop,Parse,str
	val:=(val<<4)+d[A_Loopfield]
return val
}

UShortToHex(val)
{
static d:={0:"0",1:"1",2:"2",3:"3",4:"4",5:"5",6:"6",7:"7",8:"8",9:"9",10:"A",11:"B",12:"C",13:"D",14:"E",15:"F"}
s:=""
var:=val
Loop, % 4
	val:=var>>(4*(4-A_index)),s.=d[val],var-=val<<(4*(4-A_index))
return s
}

[smorgasbord]

mm..
how to compare codes for efficiency ?
problem 5 is i guess related to LCM and the same script can be used for the same purpose.
so posting it.. will delete it if you or k0n dont like sharing codes
here is the noob's version

Mod note:
Not.

[nnnik]

How long did it take ?

[smorgasbord]

0 nnnik

[smorgasbord]

got another idea nnnik
i.e. we could use the LCM function for factorial it would be very fast.
but may be later.

[nnnik]

Thats pretty much the thing my code does.

[smorgasbord]

great! :)

[kon]

so posting it.. will delete it if you or k0n dont like sharing codes

Yes, please delete it (or encrypt it). I have made myself pretty clear that I don't want this to be a thread for posting solutions. I really like the idea of encrypting answers, because it allows us to compare our codes without ruining it for someone who hasn't solved the problem yet.

[smorgasbord]

Deleted already

[Avi]

great project. Thanks for the link

[smorgasbord]

http://www.autohotkey.com/board/topic/9 ... ice-versa/

works fine!!
why reinvent the wheel
problem 17

[nnnik]

I think its Problem 20 or something ?

[smorgasbord]

i mentioned, should i not?

[smorgasbord]

Spammer!!
please admin how could i delete these spams

[kon]

works fine!!
why reinvent the wheel
problem 17

I decided to reinvent the wheel when I did it

Code: Select all

String := "97,88,95,85,88,87,17,11,15,20,73,0,11,1,24,0,11,2,30,7,8,4,29,6,14,6,29,4,8,0,30,7,11,1"
		. ",24,5,11,4,30,12,8,4,29,11,14,6,29,1,8,4,79,60,59,118,91,71,83,93,87,20,8,12,17,73,5,8,"
		. "2,29,0,14,4,29,2,8,2,30,5,11,7,24,7,11,4,30,2,8,4,29,5,14,5,29,9,8,2,30,8,11,4,24,2,11,"
		. "1,30,5,2,11,2,30,5,3,11,7,30,5,0,11,7,30,5,1,11,9,30,5,6,11,9,30,5,7,11,6,30,5,4,11,6,3"
		. "0,5,5,11,8,30,5,10,11,9,30,5,11,11,9,79,57,56,125,94,93,68,30,17,8,11,13,18,74,60,56,61"
		. ",91,87,17,26,103,70,67,125,87,90,26,112,110,123,90,86,84,73,27,20,15,17,0,27,57,56,56,5"
		. "6,102,91,70,80,93,18,14,15,17,98,91,90,85,93,84,105,117,109,120,95,86,81,74,108,60,56,6"
		. "1,91,87,17,26,103,70,67,125,87,90,26,112,110,123,90,86,84,73,27,20,15,17,3,27,20,73,60,"
		. "59,59,61,97,69,67,91,90,85,98,65,94,93,70,29,17,124,65,95,29,17,115,107,123,95,85,87,76"
		. ",63,59,56,59,93,84,17,25,124,65,95,0,17,15,20,3,24,60,56,61,59,56,101,93,64,83,93,17,8,"
		. "9,18,117,94,71,86,94,84,106,124,65,95,0,17,124,65,95,3,108,63,62,59,56,84,94,71,87,60,5"
		. "9,59,61,59,101,94,70,85,94,17,11,15,20,118,94,68,80,88,87,106,127,71,89,3,108,17,25,20,"
		. "97,88,95,85,88,87,106,127,71,89,0,108,60,56,61,79,60,59,59,93,84,17,25,97,64,64,125,84,"
		. "92,28,115,110,120,92,80,87,73,24,18,9,18,2,24,18,79,63,59,56,59,103,70,67,88,92,83,97,6"
		. "5,93,91,64,30,17,127,71,89,30,17,112,109,125,92,85,84,74,57,56,56,56,91,82,18,25,127,71"
		. ",89,0,17,12,18,4,18,80,95,86,20,124,68,92,1,20,15,17,1,27,57,56,56,56,59,96,93,69,80,94"
		. ",20,8,12,17,97,93,92,86,93,87,111,124,68,92,3,105,18,26,17,5,57,56,56,56,87,88,65,84,17"
		. ",73,57,56,56,56,59,93,84,17,25,124,65,95,3,17,15,20,3,24,60,56,61,59,56,56,102,91,70,80"
		. ",93,18,14,15,17,98,91,90,85,93,84,105,122,71,92,0,111,20,25,17,0,2,20,25,17,117,93,65,8"
		. "0,93,84,105,122,71,92,3,18,122,71,92,2,111,57,56,56,56,59,81,94,66,84,63,62,59,56,56,59"
		. ",96,93,69,80,94,20,8,12,17,97,93,92,86,93,87,111,124,68,92,3,105,18,26,17,3,4,18,26,17,"
		. "118,91,71,83,93,87,111,124,68,92,0,105,18,26,17,97,93,92,86,93,87,111,124,68,92,1,105,6"
		. "3,59,56,59,73,63,59,56,79,57,56,56,118,102,20,25,12,17,102,91,70,80,93,63,62,79,60,59,1"
		. "17,96,18,26,12,18,5,3,60,59,127,71,85,115,94,74,61,23,56,118,102,57,56,67,84,70,65,64,95"


InputBox, Pass, Password Required, Enter the correct answer to problem 17.,, 300, 140
Clipboard := EnDeCrypt(String, Pass, 0)		;0 = decrypt
MsgBox, % "Decrypted:`n`n"Clipboard
return

Clipboard := EnDeCrypt(String, Pass)		;encrypt
MsgBox, % "Encrypted:`n`n" Clipboard
return

EnDeCrypt(text, key, ed=1) {
	StringSplit, key, key
	Loop, Parse, text, % ed ? "" : "`,"
	{
		i := A_Index <= key0 ? A_Index : !Mod(A_Index, key0) ? key0 : Mod(A_Index, key0)
		result .= ed ? Asc(A_LoopField) ^ Asc(key%i%) "," : Chr(A_LoopField ^ Asc(key%i%))
	}
	return, result
}

[strobo]

Thanks for Problem 17b, "crack the encoding by brute force."
It should be the first match of "[iI]f", "\{.*}", "\(.*\)", "[lL]oop" and "[aA]_[iI]ndex". (increasing key)

Anyway, encryption is a nice way to share solutions in this topic. A slower decrypt algo, say, a few seconds per call, would make trivial brute force less attractive. I donnu but nnniks crypt with a high quality-parameter could be slow enough.