Coffeehouse for desis
Would you like to react to this message? Create an account in a few clicks or log in to continue.

[bw]

2 posters

Go down

[bw] Empty [bw]

Post by MaxEntropy_Man Thu Jul 17, 2014 8:48 pm

has the offspring solved this one?
http://projecteuler.net/problem=220

since my recent foray into refreshing my programming skills by taking a MOOC course on python, i've been entertaining myself in my spare time by cracking problems from projecteuler using python scripts. i've had much success, but this one is stumping me.  i've made some progress verifying some of the information given in the problem, but got stuck. i am happy to post the python script i have written, and describe what i've done so far, but before i do that, i'd like to know if he has already looked at it. let me know.
MaxEntropy_Man
MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

Back to top Go down

[bw] Empty Re: [bw]

Post by bw Thu Jul 17, 2014 9:52 pm

no, my kids haven't looked at this - they haven't gone beyond problem 100 so far. i will throw this at them and shall get back to you if they make any progress.

bw

Posts : 2922
Join date : 2012-11-15

Back to top Go down

[bw] Empty Re: [bw]

Post by Guest Thu Jul 17, 2014 10:09 pm

Max would u mind posting the python script for me?

Guest
Guest


Back to top Go down

[bw] Empty Re: [bw]

Post by MaxEntropy_Man Thu Jul 17, 2014 10:43 pm

ok here you go. i didn't bother putting too many comment statements since i wrote it for my own benefit. so it may not be super readable. also the indentations might be screwed up a bit. are we able to send attachments on PM on this board? if so i could PM this to you.

_____________________________________________________________________________________________________________________________________________________________

def evalD_n(n):
   '''
   this function takes in an integer n, and returns the corresponding string representation of the "heighway dragon",
   by making the transformation "a" → "aRbFR" and "b" → "LFaLb" through a recursive computation. if n = 0, it returns
   D0 and if n = 1 it returns D1 and so on.
   '''
   if n == 0:
       return "Fa" # this returns D0
   if n >= 1:
       ans =''
       for char in evalD_n(n-1): # this recursively computes Dn for n greater than 0.
           if char not in ['a','b']:
               ans += char
           elif char == 'a':
               ans += 'aRbFR'
           elif char == 'b':
               ans += "LFaLb"
   return ans #returns Dn

   
def keepEssential(string):
   '''
   this function strips away the 'a's and 'b's from the string representation of Dn
   which serve no purpose in the actual drawing, and are only useful in recursive
   computation of the string representation of Dn.
   '''
   newstring = ''
   for elem in string:
       if elem not in ['a','b']:
           newstring += elem
   return newstring # strips 'a's and 'b's and returns the essential portion of the string

       
def LocatePos(HD_string, xhead, yhead, xtail, ytail):
   '''
   this function locates the position of the cursor after n moves. the inputs to the
   function are the string representation of Dn, and the initial position of the cursor, i.e.
   xhead, yhead & xtail, ytail.
   '''
   
   move = 0
   for char in HD_string:
       
       if char == 'F': # moves the cursor forward if an 'F' is encountered.
           move += 1
           if ((yhead == ytail) and (xtail > xhead)):
               xhead += 1
               xtail += 1
           elif ((yhead == ytail) and (xtail < xhead)):
               xhead += -1
               xtail += -1
           elif  ((xhead == xtail) and (ytail > yhead)):
               yhead += 1
               ytail += 1
           elif ((xhead == xtail) and (ytail < yhead)):
               yhead += -1
               ytail += -1
               

       
       elif char == 'L': # rotates cursor left by a right angle if an 'L' is encountered
           
           xhead_old = xhead
           yhead_old = yhead
           xtail_old = xtail
           ytail_old = ytail
           xtail = -(ytail_old-yhead_old) + xhead_old
           ytail = (xtail_old-xhead_old) + yhead_old
       
       elif char == 'R': #  rotates cursor left by a right angle if an 'R' is encountered
           
           xhead_old = xhead
           yhead_old = yhead
           xtail_old = xtail
           ytail_old = ytail
           xtail = (ytail_old-yhead_old) + xhead_old
           ytail = -(xtail_old-xhead_old) + yhead_old
   
   head = (xhead, yhead)
   tail = (xtail, ytail)
   finalpos = [head, tail]
   return finalpos   # returns final position of cursor after being acted upon by Dn.
_______________________________________________________________________________________________________________________________________________________
MaxEntropy_Man
MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

Back to top Go down

[bw] Empty Re: [bw]

Post by Guest Thu Jul 17, 2014 10:50 pm

This is good enough. Thanks.

Guest
Guest


Back to top Go down

[bw] Empty Re: [bw]

Post by bw Thu Jul 17, 2014 11:10 pm

just noticed that the way your code is written, it will take forever to run and no computer can handle this.


bw

Posts : 2922
Join date : 2012-11-15

Back to top Go down

[bw] Empty Re: [bw]

Post by MaxEntropy_Man Thu Jul 17, 2014 11:18 pm

bw wrote:just noticed that the way your code is written, it will take forever to run and no computer can handle this.


i realize that which is why i was only using it to do some simple experiments with short strings and see if i notice any patterns which can be generalized to higher n's. i wasn't necessarily trying to solve the problem completely using my rather inefficient script.
MaxEntropy_Man
MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

Back to top Go down

[bw] Empty Re: [bw]

Post by bw Thu Jul 17, 2014 11:28 pm

MaxEntropy_Man wrote:
bw wrote:just noticed that the way your code is written, it will take forever to run and no computer can handle this.


i realize that which is why i was only using it to do some simple experiments with short strings and see if i notice any patterns which can be generalized to higher n's. i wasn't necessarily trying to solve the problem completely using my rather inefficient script.

got it.

bw

Posts : 2922
Join date : 2012-11-15

Back to top Go down

[bw] Empty Re: [bw]

Post by bw Fri Jul 18, 2014 8:00 pm

my son is looking at this and has some ideas on how to proceed. there are some interesting material on dragon curves on wiki which may help solve this.

here's a numberphile video.

https://www.youtube.com/watch?v=wCyC-K_PnRY

have you encountered any easier variants of this problem on projecteuler since their questions are in increasing levels of difficulty, with each often building on the previous ones?

bw

Posts : 2922
Join date : 2012-11-15

Back to top Go down

[bw] Empty Re: [bw]

Post by MaxEntropy_Man Fri Jul 18, 2014 10:36 pm

bw - thanks for the video. i must confess i haven't been making a sequential progression through projecteuler. i jump around and pick whichever problem seems susceptible to attack by python lately.
MaxEntropy_Man
MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

Back to top Go down

[bw] Empty Re: [bw]

Post by bw Sat Jul 19, 2014 8:24 am

max, he has solved the problem. what helped was to look at the pictures of the various dragon curves on the wiki page and explore their connections. if you want further details/program, let me know.

bw

Posts : 2922
Join date : 2012-11-15

Back to top Go down

[bw] Empty Re: [bw]

Post by MaxEntropy_Man Sat Jul 19, 2014 8:49 am

bw wrote:max, he has solved the problem. what helped was to look at the pictures of the various dragon curves on the wiki page and explore their connections. if you want further details/program, let me know.

i'm going to try some more, but thanks for the suggestion of looking at pictures. if i can't do it in another week, i'll come back to you and ask for help. congrats to your boy! nice work.
MaxEntropy_Man
MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

Back to top Go down

[bw] Empty Re: [bw]

Post by Sponsored content


Sponsored content


Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum