Project Euler

Talk about anything
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

Project Euler

02 Nov 2013, 11:32

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
Why Encrypt Solutions?:
[url=http://projecteuler.net/about]About Project Euler[/url] <- You must be logged in to see this page. wrote: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.:idea:
Last edited by kon on 22 Jan 2014, 01:48, edited 5 times in total.
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

02 Nov 2013, 20:22

Thanks @k0n
may be just my view we post solutions if any in spoiler tags?
John ... you working ?
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Project Euler

03 Nov 2013, 01:22

No they have to be encrypted with the correct awnswers.
I just did the first 5 and think its quite interesting.
Recommends AHK Studio
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

03 Nov 2013, 01:54

@nnnik
Show an example please
:)
John ... you working ?
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Project Euler

03 Nov 2013, 03:19

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
}
Recommends AHK Studio
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

03 Nov 2013, 03:32

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.
Last edited by smorgasbord on 03 Nov 2013, 03:56, edited 2 times in total.
John ... you working ?
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Project Euler

03 Nov 2013, 03:50

How long did it take ?
Recommends AHK Studio
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

03 Nov 2013, 03:52

0 nnnik
:)
John ... you working ?
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

03 Nov 2013, 03:53

got another idea nnnik
i.e. we could use the LCM function for factorial it would be very fast.
but may be later.
:)
John ... you working ?
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Project Euler

03 Nov 2013, 05:45

Thats pretty much the thing my code does.
Recommends AHK Studio
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

03 Nov 2013, 05:50

great! :):)
John ... you working ?
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

Re: Project Euler

03 Nov 2013, 10:05

smorgasbord wrote: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.
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

03 Nov 2013, 11:32

Deleted already
:)
John ... you working ?
User avatar
Avi
Posts: 193
Joined: 30 Sep 2013, 09:51
Facebook: avi.aryan.ap
Google: +AviAryan
GitHub: aviaryan
Location: India
Contact:

Re: Project Euler

04 Nov 2013, 04:34

great project. Thanks for the link
Writes at Dev Letters

Clipjump Clipboard Manager : More Scripts (updated 2019)

Image
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

04 Nov 2013, 11:15

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

works fine!!
why reinvent the wheel
problem 17
:)
John ... you working ?
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Project Euler

04 Nov 2013, 14:23

I think its Problem 20 or something ?
Recommends AHK Studio
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

04 Nov 2013, 21:23

i mentioned, should i not?
John ... you working ?
User avatar
smorgasbord
Posts: 490
Joined: 30 Sep 2013, 09:34

Re: Project Euler

05 Nov 2013, 00:25

Spammer!!
please admin how could i delete these spams :(
John ... you working ?
kon
Posts: 1756
Joined: 29 Sep 2013, 17:11

Re: Project Euler

05 Nov 2013, 16:09

smorgasbord wrote:works fine!!
why reinvent the wheel
problem 17
:)
I decided to reinvent the wheel when I did it :lol:

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
Posts: 125
Joined: 30 Sep 2013, 15:24

Re: Project Euler

06 Nov 2013, 04:41

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.

Return to “Offtopic”

Who is online

Users browsing this forum: No registered users and 9 guests