11253 - Fractal

[baodog]

First I generated a bunch of values, and tried to
fit iterated linear/quadratic functions over consecutive
coordinates. The logic been that we can apply
the Q matrix method if a relation is found. But, it didn't
work out. Then, I searched on google
and found that the Dragon fractal is somehow related
to base i-1 representations .... but I still fail to make the connection
and cannot decipher the tcl/tk code on this page ...

http://wiki.tcl.tk/10761

What is it trying to do here? Is there some iterated function
system which generates consecutive coordinates ? Or does
conversion of n into base i-1 give the bits of the turns?

Code: Select all

set y [list 1 0]
 set powers {}
 for { set i 0 } { $i < 32 } { incr i } {
     lappend powers $y
     foreach { a b } $y break
     set y [list [expr { -$a - $b }] \
                [expr { $a - $b }]]
 }
proc penney { from to color } {
     variable powers
     set cmd [list .c create line]
     for { set i $from } { $i <= $to } { incr i } {
         set b 1
         set re 0
         set im 0
         foreach bit $powers {
             if { $i & $b } {
                 foreach { br bi } $bit break
                 incr re $br
                 incr im $bi
             }
             if { $b >= $i } {
                 break
             }
             incr b $b
         }
         lappend cmd [expr {128+3*$re}] [expr {108-3*$im}]
     }
     lappend cmd -fill $color
     eval $cmd
 }

[mf]

I think you're making the problem much more complex than it really is this way...
I basically just simulated the whole thing. There's a lot of regularity in the command sequence, so if you memoize by how much the robot shifts and rotates during a few certain sequences, you'd be able to simulate it in O(log n) time.

[sclo]

I did use complex number because multiplying a complex number by i basically turns the position 90 degrees counterclockwise about the origin.
Notice that the endposition for s[0] is 1+0i or simply 1.
Let f(n) denote the end position for s[n], then the recursion is f(n)=(1+i)*f(n-1), so it's clear where the base i+1 stuff comes from.

In other words f(n) = (i+1)^n

[baodog]

Thanks! I get it now !!!
ic, the one above uses 1-i instead of 1+i because it's a
rotated form of the one in this problem .... now the
problem is really trivial ....

[sclo]

We can actually derive a stronger recurrence that give the recursive solution.

Let g(k) be the position after the kth step on any curve s[n]. (the answer is always the same for any curve as long as k<=2^n)

Then g(k) = (i+1)^n - i*g(2^n-k) for any 2^(n-1)<=k<=2^n.

[Robert Gerbicz]

you'd be able to simulate it in O(log n) time.

By O(sqrt(N)) precomputation it is possible to answer for each question up to n<=N in O(1) time.