1 of 6
Aiden Chow
  • 4.7k
  • 6
  • 9

Create Bernard from Desmos

Background

In the online graphing calculator Desmos, there is a certain shape that appears in the lower left portion of the graph in many high detail graphs, which the Desmos community has dubbed "Bernard". You can see an example of it in this graph and an isolated version of it in this graph. This shape is a consequence of the quadtree algorithm which Desmos utilizes to actually graph equations. I barely comprehend how it all works, but by descending into "deeper", or more detailed, quadrants, a more detailed Bernard can be created.

(Don't take my word for how Bernard is formed, I barely understand how it works myself.)

In this challenge, you will write code that will print out a 2d array version of a depth-n Bernard.

How to create Bernard?

Given a positive integer n, return a \$2^n\times2^n\$ matrix which follows the rules below:

Start with a matrix filled with 0's.

For any \$n\$, the resulting matrix should have \$\left\lceil\frac23\cdot4^n\right\rceil\$ 1's.

If n=1:

  1. Fill in the \$2\times2\$ matrix with 1's in a counterclockwise direction, starting from the bottom-left corner.
  2. After \$\left\lceil\frac23\cdot4^n\right\rceil=3\$ 1's have been filled, stop. The resulting matrix is your output. So for n=1, the output should be:
0 1
1 1

If n>1:

  1. Imagine splitting each element in the depth-n-1 array into 2-by-2 subarrays (like descending to deeper quadrants in the quadtree). So an array shaped like this:

(numbers added for clarity)

1 2
3 4

Becomes this:

1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
  1. Each 2-by-2 subarray should be "visited" in the same order that the elements in the depth-n-1 Bernard were filled in. For example, the depth-1 Bernard is filled in this order:
4 3
1 2

So the 2-by-2 subarrays in the depth-2 Bernard should be "visited" in the following order:

4 4 3 3
4 4 3 3
1 1 2 2
1 1 2 2
  1. A visited 2-by-2 subarray should be filled with 1's in the opposite direction that each 2-by-2 subarray in depth-n-1 Bernard was filled. For example, in the depth-1 Bernard, each 2-by-2 subarray (which, in this case, is the entire array), is filled in a counterclockwise direction. As a result, each 2-by-2 subarray in the depth-2 Bernard should be filled in a clockwise direction, starting from the top-right corner of the 2-by-2 subarray.

Using all the above rules, the depth-2 Bernard should be filled in the following order:

(with A being 10th, B being 11th, and so on)

D E 9 A
G F C B
1 2 5 6
4 3 8 7

Then, because \$\left\lceil\frac23\cdot4^n\right\rceil=11\$, the matrix should be filled in until B (which represents 11):

0 0 1 1
0 0 0 1
1 1 1 1
1 1 1 1

Task

Given a positive integer n as input, return a \$2^n\times2^n\$ 2d array which represents the depth-n Bernard.

Test Cases

n=1
0 1
1 1

n=2
0 0 1 1
0 0 0 1
1 1 1 1
1 1 1 1

n=3
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

n=4
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

This is , so shortest code in bytes wins!

Aiden Chow
  • 4.7k
  • 6
  • 9