[bw]

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.

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.

Max would u mind posting the python script for me?

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.
_______________________________________________________________________________________________________________________________________________________

This is good enough. Thanks.

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

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 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.

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 - 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.

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 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.