35
\$\begingroup\$

Nichomachus's Theorem relates the square of a sum to the sum of cubes:

Nichomachus's Theorem

and has a beautiful geometric visualization:

Visualization

Challenge: Create the 2d part of this visualization in ascii.

You will need to ensure that all visual demarcations are upheld by your diagram. This is simplest to do with four "colors," though it's possible to achieve with only three (see last example below for how). With four colors, you use two to distinguish between regions within a "strip" (ie, the different parts that make up a single cube), and two to distinguish between adjacent strips. You may also use more than four colors if you like. If any of this is confusing, the example output below should clarify.

Input / Output

Input is a single integer greater than 0. Output is an ascii grid similar to the examples below, corresponding to the flattened grid for that input number in the image above. Leading and trailing whitespace are ok.

This is code golf, with standard rules.

Sample outputs

N = 1

#

N = 2

#oo   
o@@   
o@@   

N = 3

#oo+++
o@@+++
o@@+++
+++###
+++###
+++###

N = 4

#oo+++oooo
o@@+++oooo
o@@+++@@@@
+++###@@@@
+++###@@@@
+++###@@@@
oo@@@@oooo
oo@@@@oooo
oo@@@@oooo
oo@@@@oooo

N = 5

#oo+++oooo+++++
o@@+++oooo+++++
o@@+++@@@@+++++
+++###@@@@+++++
+++###@@@@+++++
+++###@@@@#####
oo@@@@oooo#####
oo@@@@oooo#####
oo@@@@oooo#####
oo@@@@oooo#####
+++++#####+++++
+++++#####+++++
+++++#####+++++
+++++#####+++++
+++++#####+++++

Three color version for N = 4, thanks to @BruceForte:

#oo+++oooo
o##+++oooo
o##+++####
+++ooo####
+++ooo####
+++ooo####
oo####++++
oo####++++
oo####++++
oo####++++
\$\endgroup\$
  • 6
    \$\begingroup\$ Four-colour theorem :D \$\endgroup\$ – Leaky Nun Sep 19 '17 at 18:16
  • 1
    \$\begingroup\$ Can you add the output for N=5 please? \$\endgroup\$ – Uriel Sep 19 '17 at 19:31
  • 1
    \$\begingroup\$ @Uriel Done. See my edit. \$\endgroup\$ – Jonah Sep 19 '17 at 19:35
  • \$\begingroup\$ Thanks! Also, can I switch the @ and o s only in the outer strip in N=4? Or must the output be a strict substitution of these texts with another charset? \$\endgroup\$ – Uriel Sep 19 '17 at 19:37
  • \$\begingroup\$ @Uriel switching is fine. All that matters is that adjacent colors don't conflict, so that the pattern is visible. \$\endgroup\$ – Jonah Sep 19 '17 at 19:37
17
\$\begingroup\$

MATL, 30 28 27 bytes

t:P"@:s:@/Xk&+@+8MPt&(]30+c

Try it online!

Bonus features:

  • For 26 bytes, the following modified version produces graphical output:

    t:P"@:s:@/Xk&+@+8MPt&(]1YG
    

    Try it at MATL Online!

  • The image is begging for some colour, and it only costs 7 bytes:

    t:P"@:s:@/Xk&+@+8MPt&(]1YG59Y02ZG
    

    Try it at MATL Online!

  • Or use a longer version (37 bytes) to see how the character matrix is gradually built:

    t:P"@:s:@/Xk&+@+8MPt&(t30+cD9&Xx]30+c
    

    Try it at MATL Online!

Example outputs

For input is 8, the following shows the basic version, graphical output, and colour graphical output.

enter image description here

enter image description here

enter image description here

Explanation

General procedure

A numeric matrix is built from outer to inner layers in N steps, where N is the input. Each step overwrittes an inner (upper-left) part of the previous matrix. At the end, the numbers in the obtained matrix are changed to characters.

Example

For input 4 the first matrix is

10 10  9  9  9  9  8  8  8  8
10 10  9  9  9  9  8  8  8  8
 9  9  8  8  8  8  7  7  7  7
 9  9  8  8  8  8  7  7  7  7
 9  9  8  8  8  8  7  7  7  7
 9  9  8  8  8  8  7  7  7  7
 8  8  7  7  7  7  6  6  6  6
 8  8  7  7  7  7  6  6  6  6
 8  8  7  7  7  7  6  6  6  6
 8  8  7  7  7  7  6  6  6  6

As a second step, the matrix

7 7 7 6 6 6
7 7 7 6 6 6
7 7 7 6 6 6
6 6 6 5 5 5
6 6 6 5 5 5
6 6 6 5 5 5

is overwritten into the upper half of the latter. Then the same is done with

6 5 5
5 4 4
5 4 4

and finally with

3

The resulting matrix is

3 5 5 6 6 6 8 8 8 8
5 4 4 6 6 6 8 8 8 8
5 4 4 6 6 6 7 7 7 7
6 6 6 5 5 5 7 7 7 7
6 6 6 5 5 5 7 7 7 7
6 6 6 5 5 5 7 7 7 7
8 8 7 7 7 7 6 6 6 6
8 8 7 7 7 7 6 6 6 6
8 8 7 7 7 7 6 6 6 6
8 8 7 7 7 7 6 6 6 6

Lastly, 30 is added to each entry and the resulting numbers are interpreted as codepoints and converted to characters (thus starting at 33, corresponding to !).

Construction of the intermediate matrices

For input N, consider decreasing values of k from N to 1. For each k, a vector of integers from 1 to k*(k+1) is generated, and then each entry is divided by k and rounded up. As an example, for k=4 this gives (all blocks have size k except the last):

1 1 1 1 2 2 2 2 3 3

whereas for k=3 the result would be (all blocks have size k):

1 1 1 2 2 2

This vector is added, element-wise with broadcast, to a transposed copy of itself; and then k is added to each entry. For k=4 this gives

6  6  6  6  7  7  7  7  8  8
6  6  6  6  7  7  7  7  8  8
6  6  6  6  7  7  7  7  8  8
6  6  6  6  7  7  7  7  8  8
7  7  7  7  8  8  8  8  9  9
7  7  7  7  8  8  8  8  9  9
7  7  7  7  8  8  8  8  9  9
7  7  7  7  8  8  8  8  9  9
8  8  8  8  9  9  9  9 10 10
8  8  8  8  9  9  9  9 10 10

This is one of the intermediate matrices shown above, except that it is flipped horizontally and vertically. So all that remains is to flip this matrix and write it into the upper-left corner of the "accumulated" matrix so far, initiallized to an empty matrix for the first (k=N) step.

Code

t       % Implicitly input N. Duplicate. The first copy of N serves as the
        % initial state of the "accumulated" matrix (size 1×1). This will be 
        % extended to size N*(N+1)/2 × N*(N+1)/2 in the first iteration
 :P     % Range and flip: generates vector [N, N-1, ..., 1]
"       % For each k in that vector
  @:    %   Push vector [1, 2, ..., k]
  s     %   Sum of this vector. This gives 1+2+···+k = k*(k+1)/2
  :     %   Range: gives vector [1, 2, ..., k*(k+1)/2]
  @/    %   Divide each entry by k
  Xk    %   Round up
  &+    %   Add vector to itself transposed, element-wise with broadcast. Gives
        %   a square matrix of size k*(k+1)/2 × k*(k+1)/2
  @+    %   Add k to each entry of the this matrix. This is the flipped
        %   intermediate matrix
  8M    %   Push vector [1, 2, ..., k*(k+1)/2] again
  Pt    %   Flip and duplicate. The two resulting, equal vectors are the row and
        %   column indices where the generated matrix will be written. Note that
        %   flipping the indices has the same effect as flipping the matrix
        %   horizontally and vertically (but it's shorter)
  &(    %   Write the (flipped) intermediate matrix into the upper-left
        %   corner of the accumulated matrix, as given by the two (flipped)
        %   index vectors 
]       % End
30+     % Add 30 to each entry of the final accumulated matrix
c       % Convert to char. Implicitly display
\$\endgroup\$
  • \$\begingroup\$ I don't know MATL at all, but could you save any bytes by taking mod10 rather than adding 30 and converting to character? \$\endgroup\$ – user2390246 Sep 20 '17 at 10:13
  • \$\begingroup\$ Or even mod4... \$\endgroup\$ – user2390246 Sep 20 '17 at 10:19
  • \$\begingroup\$ @user2390246 Do you mean to keep them as numbers with a single digit and avoid converting to char? That wouldn't work, because the numeric matrix would be printed with spaces between the numbers. But thanks for the idea anyway :-) \$\endgroup\$ – Luis Mendo Sep 20 '17 at 13:42
  • \$\begingroup\$ Fair enough. What happens with n > 226? Won't that go outside the range of valid characters? (Unsurprisingly, times out on TIO, so I couldn't check) \$\endgroup\$ – user2390246 Sep 20 '17 at 16:03
  • \$\begingroup\$ @user2390246 Yes, for high input numbers it goes outside. And if we consider ASCII chars the maximum code point is 127, so it goes outside even sooner. But as you noticed it runs out of memory before that happens (the resulting char matrix is too large). Anyway, working up to a given input size only due to memory or data type limitations is usually allowed \$\endgroup\$ – Luis Mendo Sep 20 '17 at 20:33
7
\$\begingroup\$

Python 2, 187 178 164 162 152 bytes

-8 bytes thanks to Mr.Xcoder
-1 byte thanks to Stephen
-10 bytes thanks to Jonathan Frech

g=lambda y:y>1and[l+y*f(y,i)for i,l in enumerate(g(y-1))]+y*[''.join(f(y,i)for i in range(y*-~y/2))]or['#']
f=lambda y,i:'0@+#'[(y*~-y/2%y+i)/y%2+y%2*2]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ For when you get home, 179 bytes. \$\endgroup\$ – Mr. Xcoder Sep 19 '17 at 20:01
  • \$\begingroup\$ @Mr.Xcoder 178 bytes \$\endgroup\$ – Stephen Sep 19 '17 at 21:09
  • 1
    \$\begingroup\$ Is it allowed to not include your lambda function's name byte count when you are using it recursively, i.e. using its name in the rest of the code? \$\endgroup\$ – Jonathan Frech Sep 20 '17 at 1:36
  • \$\begingroup\$ sum(range(y))%y -> y*~-y/2%y \$\endgroup\$ – Jonathan Frech Sep 20 '17 at 1:41
  • \$\begingroup\$ @JonathanFrech yeah, when it's recursive it must be there. \$\endgroup\$ – Rod Sep 20 '17 at 3:11
7
\$\begingroup\$

Charcoal, 50 46 bytes

F⮌…·¹N«≔⊘×ι⊕ιθF⊕⊘ι«F§#+@⁺ικ«UO⁻θ×ικθλUOθ⁻θ×ικλ

Try it online! Link is to verbose version of code. Previous 50-byte version with explanation: Try it online!

F⮌…·¹N«≔÷×ι⁺¹ι²θF⁺¹÷鲫F§#+@⁺ικ«UO⁻θ×ικθλUOθ⁻θ×ικλ

F     «     Loop over
  …·¹       Inclusive range from 1 to
     N      Input as a number
 ⮌          Reversed

   ι⁺¹        Add 1 to current index
  ×   ι       Multiply by current index
 ÷     ²      Divide by 2
≔       θ     Assign to q

F     «      Loop over
             Implicit range from 0 to
   ÷ι²       Half the current index
 ⁺¹          Plus 1

F       «    Loop over
  #+@        Literal string
 §           Circularly indexed by
     ⁺ικ     Sum of outer and inner index

    ×ικ     Multiply outer and inner index
  ⁻θ        Subtract from q
UO     θλ   Draw an oblong (q-ik, q) using that character

UOθ⁻θ×ικλ   Draw an oblong (q, q-ik) using that character

Note: I loop over the character rather than trying to assign the character directly to l because you can't directly assign the result of indexing a string to a variable as it's an ambiguous construct in Charcoal. Fortunately the byte count is the same.

\$\endgroup\$
  • \$\begingroup\$ Technically you can, with an ASCII variable since its argument order is reversed (note that it needs an operator to access so it's still less golfy) \$\endgroup\$ – ASCII-only Sep 20 '17 at 7:02
5
\$\begingroup\$

C (gcc), 135 128 120 bytes

f(n,m,i,x,y,k){for(m=n*-~n/2,i=m*m;i--;printf("\n%d"+!!(~i%m),(x/k+y/k+k)%3))for(x=i%m,y=i/m,k=n;x>=k&y>=k;x-=k--)y-=k;}

Try it online!

Uses only three colors.

Conceptually, works on a grid rotated by 180 degrees:

000111
000111
000111
111220
111220
111001

And computes colors according to the formula:

c(x,y,n) = c(x-n,y-n,n-1)                   if x >= n and y >= n
         = (x div n + y div n + n) mod 3    otherwise
\$\endgroup\$
  • 1
    \$\begingroup\$ 123 bytes. \$\endgroup\$ – Jonathan Frech Sep 20 '17 at 1:30
  • \$\begingroup\$ @JonathanFrech This isn't valid C and breaks with gcc -O2. \$\endgroup\$ – nwellnhof Sep 20 '17 at 1:53
  • \$\begingroup\$ Fair enough; is it possible that the second code only works for three colors because of the modulus three (g(i%m,i/m,n)%3)? \$\endgroup\$ – Jonathan Frech Sep 20 '17 at 2:11
  • \$\begingroup\$ Suggest x/k&&y/k instead of x>=k&y>=k \$\endgroup\$ – ceilingcat Jun 19 '18 at 1:39
2
\$\begingroup\$

R, 131 126 123 bytes

3 bytes saved thanks to @Giuseppe

function(n){l=w=sum(1:n)
m=matrix(,l,l)
for(i in n:1){m[l:1,l:1]=outer(x<-(1:l-1)%/%i,x,`+`)+i
l=l-i}
write(m%%4,"",w,,"")}

Try it online!

This uses the same algorithm as @LuisMendo 's MATL answer. The only difference is that rather than converting to characters, the matrix is output with all of the values mod4 to ensure that each element is a single ascii character.

\$\endgroup\$
  • 1
    \$\begingroup\$ 123 bytes! I brought the for loop back for -1 byte :) \$\endgroup\$ – Giuseppe Sep 20 '17 at 13:51
1
\$\begingroup\$

Python 2, 176 175 bytes

n=input()
R,J=range,''.join;r=[]
for i in R(n+1):
 S=sum(R(i));c='AxBo'[i%2::2]
 for j in R(S):r[~j]+=c[j/i%2]*i
 r+=[J(c[-j/i%2]for j in R(S+i,0,-1))]*i
for l in r:print J(l)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ If you define J="".join; (+10 bytes) and replace both "".joins (-2*7=-14 bytes) with J (+2 bytes), you can save a byte (as there has to be an additional space after the print; +1 byte). \$\endgroup\$ – Jonathan Frech Sep 20 '17 at 13:32

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.