# Eye test - How many squares are in this picture?

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

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.

• Are you guys interested in a fastest-code version of it? – Domenico Modica Dec 29 '20 at 16:26
• I've added this to the OEIS. Right now it is a draft, but it will be here once published. – Peter Kagey Jan 5 at 20:17
• I'd love to see a fastest-code version! – Peter Kagey Jan 5 at 20:17
• @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 – Domenico Modica Jan 6 at 16:05

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

Ｆυ«Ｊ⊟ι⊟ι


≔¹η


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.

# 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