Eye test - How many squares are in this picture?

Question

The picture:

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 code-golf

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.

Answer 1

Charcoal, 96 bytes

Ｆ…¹Ｘ²Ｎ«Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧##¿＆ι⊗＆ι±ι↷↶»↷≔⁰ζＦυ«Ｊ⊟ι⊟ι≔¹ηＷ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕ηＦη¿κ«↗↗≧⁺⬤dl⁼№ＫＤ⊗κ✳λ#⊗κζ»»⎚Ｉζ

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

Ｆ…¹Ｘ²Ｎ«

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

Ｆ¬⁼ＫＫ#⊞υ⟦ⅉⅈ⟧

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.

Ｆυ«Ｊ⊟ι⊟ι

Loop over and jump to each visited cell.

≔¹η

Start searching for squares.

Ｗ⬤ur⁼№ＫＤ⊗η✳λ#⊗η≦⊕η

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

Ｆη¿κ«

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

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

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.

»»⎚Ｉζ

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

Answer 2

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