22
\$\begingroup\$

The picture:


Dragon Curve 11th iteration (1455 squares)


Sick of the same old grid where the answer is simply a square pyramidal number?

Accept the challenge and write a program that given a positive integer \$n\$ counts how many squares are in the \$n^{\text{th}}\$ iteration of the Harter-Heighway dragon!

  • The sequence of squares of size 1 is A003230
  • Your code must count all the squares of any size (the first of size 2 show up in \$7^{\text{th}}\$ iteration)
  • This is

Here's the beginning of the resulting sequence:

0, 0, 0, 1, 4, 11, 30, 78, 205, 546, 1455, 4062, 11192, 31889, 88487, 254594

And my un-golfed reference program in Mathematica.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Are you guys interested in a fastest-code version of it? \$\endgroup\$ – Domenico Modica Dec 29 '20 at 16:26
  • 1
    \$\begingroup\$ I've added this to the OEIS. Right now it is a draft, but it will be here once published. \$\endgroup\$ – Peter Kagey Jan 5 at 20:17
  • \$\begingroup\$ I'd love to see a fastest-code version! \$\endgroup\$ – Peter Kagey Jan 5 at 20:17
  • \$\begingroup\$ @PeterKagey Thanks for submitting the sequence! :) Unfortunately my computer is currently full of stuff, not in the best shape to host the challenge. You can do it if you want \$\endgroup\$ – Domenico Modica Jan 6 at 16:05
8
\$\begingroup\$

Charcoal, 96 bytes

F…¹X²N«F¬⁼KK#⊞υ⟦ⅉⅈ⟧##¿&ι⊗&ι±ι↷↶»↷≔⁰ζFυ«J⊟ι⊟ι≔¹ηW⬤ur⁼№KD⊗η✳λ#⊗η≦⊕ηFη¿κ«↗↗≧⁺⬤dl⁼№KD⊗κ✳λ#⊗κζ»»⎚Iζ

Try it online! Link is to verbose version of code. Explaantion:

F…¹X²N«

Loop over all the turns of the nᵗʰ iteration of the dragon.

F¬⁼KK#⊞υ⟦ⅉⅈ⟧

If we haven't visited this cell yet then record its position.

##

Print a segment of the dragon.

¿&ι⊗&ι±ι↷↶

Rotate appropriately for the next segment.

»↷

At the end of the dragon, rotate back to horizontal. (Clear() doesn't do this; maybe it should?)

≔⁰ζ

Start counting squares.

Fυ«J⊟ι⊟ι

Loop over and jump to each visited cell.

≔¹η

Start searching for squares.

W⬤ur⁼№KD⊗η✳λ#⊗η≦⊕η

While there are enough #s in both the upwards and rightwards directions increase the size of square being searched for.

Fη¿κ«

Check all sizes of squares from 1 to the largest potential size found.

↗↗≧⁺⬤dl⁼№KD⊗κ✳λ#⊗κζ

Move diagonally up and right two cells, then check downwards and leftwards for the other two sides of the square of this size and keep a running total of squares found.

»»⎚Iζ

Once all potential squares have been checked clear the canvas and output the final number found.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6),  272 ... 244  239 bytes

This is quite slow for \$n>6\$ but was verified locally up to \$n=8\$.

k=>(b=[],k=1<<k,g=d=>k--?g(d+(g[b.push(n++,n++),x+=--d%2,y+=--d%2,[x-!d,y-(d>0)]]|=d&1||2,n&-n&n/2?1:3)&3):b.map(y=>b.map(x=>b.map(w=>o+=(h=d=>d--?g[[X=x-n/2+d,Y=y-n/2]]&g[[X,Y+w]]&2&&g[[X-=d,Y+=d]]&g[[X+w,Y]]&h(d):1)(++w))))|o)(n=x=y=o=0)

Try it online!

Commented

Step 1

We first build the grid.

k => (                             // k = input
  b = [],                          // initialize b[] to an empty array
  k = 1 << k,                      // turn k into 2 ** k
  g = d =>                         // g is a recursive function taking a direction d
    k-- ?                          //   decrement k; if it was not equal to 0:
      g(                           //     do a recursive call:
        d + (                      //       using the updated direction
          g[                       //
            b.push(n++, n++),      //       append n and n + 1 to b[]
            x += --d % 2,          //       add dx to x
            y += --d % 2,          //       add dy to y
            [x - !d, y - (d > 0)]  //       use either [x, y], [x-1, y] or [x, y-1]
          ] |=                     //       as a key to identify the cell
            d & 1                  //       that is updated with either a horizontal
            || 2,                  //       or a vertical border (using the two least
                                   //       significant bits as flags)
          n & -n & n / 2 ?         //       determine whether it's a left or right turn
            1                      //       and add either 1 or 3 to d
          :                        //
            3                      //
        ) & 3                      //       force d into [0 .. 3]
      )                            //     end of recursive call
    :                              //   else:
      ...                          //     stop the recursion and process step #2
)(n = x = y = o = 0)               // initial call to g

Step 2

The array b[] is now filled with [0, 1, ..., 2k-1] and the underlying object of g describes the horizontal and vertical borders that are set for each cell in the grid.

b.map(y =>                         // for y = 0 to y = 2k-1:
  b.map(x =>                       //   for x = 0 to x = 2k-1:
    b.map(w =>                     //     for w = 0 to w = 2k-1:
      o +=                         //       update the output counter o:
        ( h = d =>                 //         h is a function taking a distance d
          d-- ?                    //           decrement d; if it was not equal to 0:
            g[[ X = x - n / 2 + d, //             test the vertical border at
                Y = y - n / 2      //             (x - n/2 + d, y - n/2)
            ]] &                   //
            g[[ X,                 //             test the vertical border at
                Y + w              //             (x - n/2 + d, y - n/2 + w)
            ]] & 2                 //
            &&                     //
            g[[ X -= d,            //             test the horizontal border at
                Y += d             //             (x - n/2, y - n/2 + d)
            ]] &                   //
            g[[ X + w,             //             test the horizontal border at
                Y                  //             (x - n/2 + w, y - n/2 + d)
            ]] &                   //
            h(d)                   //             and do a recursive call
          :                        //           else:
            1                      //             stop the recursion
        )(++w)                     //         increment w; initial call to h with d = w
    )                              //     end of map()
  )                                //   end of map()
) | o                              // end of map(); return o
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.