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

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

MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

## Re: [bw]

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

## Re: [bw]

Max would u mind posting the python script for me?

Guest
Guest

## Re: [bw]

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

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

move = 0
for char in HD_string:

if char == 'F': # moves the cursor forward if an 'F' is encountered.
move += 1
xtail += 1
xtail += -1
ytail += 1
ytail += -1

elif char == 'L': # rotates cursor left by a right angle if an 'L' is encountered

xtail_old = xtail
ytail_old = ytail

elif char == 'R': #  rotates cursor left by a right angle if an 'R' is encountered

xtail_old = xtail
ytail_old = ytail

tail = (xtail, ytail)
return finalpos   # returns final position of cursor after being acted upon by Dn.
_______________________________________________________________________________________________________________________________________________________

MaxEntropy_Man

Posts : 14701
Join date : 2011-04-28

## Re: [bw]

This is good enough. Thanks.

Guest
Guest

## Re: [bw]

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

## Re: [bw]

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

Posts : 14701
Join date : 2011-04-28

## Re: [bw]

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

## Re: [bw]

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.

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

## Re: [bw]

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

Posts : 14701
Join date : 2011-04-28

## Re: [bw]

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

## Re: [bw]

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

Posts : 14701
Join date : 2011-04-28