13
\$\begingroup\$

This one is inspired by Calvin's Hobbies recent multiplication table challenge.

Write a function or program that takes an integer N as input and prints or returns a N-by-N unique multiplication spiral. The code must (in theory) work for N between 0 and 1000 (outputting this can be hard though). The output should be equivalent to the table produced by the following procedure:

  1. Fill out an N-by-N multiplication table. E.g. for N = 3:

    1 2 3
    2 4 6
    3 6 9
    
  2. Follow a spiral clockwise from the upper left corner, noting the numbers that you visit. When you visit a number which you have already visited, replace it with 0.

A few examples might make it more clear:

n = 0:
0

n = 1:
1

n = 2:       //   Spiral order:
1  2         //   1  2
0  4         //   4  3

n = 3:
1  2  3      //   1  2  3
0  4  6      //   8  9  4
0  0  9      //   7  6  5

n = 4:
1  2  3  4   //   1   2   3   4
0  0  6  8   //  12  13  14   5
0  0  9 12   //  11  16  15   6
0  0  0 16   //  10   9   8   7

n = 5:
1   2   3   4   5
0   0   6   8  10
0   0   9  12  15
0   0   0  16  20
0   0   0   0  25

n = 10:
1   2   3   4   5   6   7   8   9  10
0   0   0   0   0  12  14  16  18  20
0   0   0   0  15   0  21  24  27  30
0   0   0   0   0   0  28  32  36  40
0   0   0   0  25   0  35   0  45  50
0   0   0   0   0   0  42  48  54  60
0   0   0   0   0   0  49  56  63  70
0   0   0   0   0   0   0  64  72  80
0   0   0   0   0   0   0   0  81  90
0   0   0   0   0   0   0   0   0 100

The numbers are found like this:

enter image description here

Any reasonable output format is accepted, but it must be an N-by-N matrix, it cannot be just a list. Formats such the ones below are accepted, as there are N easily distinguishable 1-by-N columns, or N-by-1 rows:

[[1 2 3][0 4 6][0 0 9]]   <-- OK

[[1 0 0][2 4 0][3 6 9]]   <-- OK

ans =                     <-- OK
    1  2  3
    0  4  6
    0  0  9   

Shortest code in bytes win.

\$\endgroup\$
  • \$\begingroup\$ I spy with my little eye a modified sieve of eratosthenes! I'm pretty sure there's a pattern you can use here that I've seen somewhere or another. \$\endgroup\$ – Addison Crump Nov 28 '15 at 14:30
  • 2
    \$\begingroup\$ Why would there be an output for n=0 where there is no zero in the multiplication tables. I can understand n=1 would output 1, but why include zero? \$\endgroup\$ – Tom Carpenter Nov 28 '15 at 16:10
  • \$\begingroup\$ @TomCarpenter, it might have been a bad decision, but I knew there would be a "What about N=0?"-question, so I made the N=0 -> 0 rule. In retrospect, it might have been better to say that N>0, but it's a bit too late now I'm afraid =/ \$\endgroup\$ – Stewie Griffin Nov 28 '15 at 17:31
  • 2
    \$\begingroup\$ @StewieGriffin You said that the output must be an N-by-N matrix, so the output for n=0 should be a 0-by-0 matrix, or the question would be inconsistent. \$\endgroup\$ – alephalpha Nov 29 '15 at 4:44
3
\$\begingroup\$

J, 22 bytes

,~$[:(*~:)[:,1*/~@:+i.

It output a 0-by-0 matrix for n=0.

\$\endgroup\$
8
\$\begingroup\$

Mathematica 123 122 117 98 92 73 bytes

With 24 bytes saved thanks to LegionMammal978 and another 19 by alephalpha !


Surprisingly, in this table, multiple instances of any whole number n will have the same relative ordering in the spiral as they do in the table itself! The first appearance of a number n lies at the very cell where that number appears first in the table (when one fills in the table row by row). This means that the approach can disregard the spiral constraint altogether, for it has no bearing on the outcome. (See explanation below.)

ReplacePart[t=1##&~Array~{#,#},Join@@(Rest[t~Position~#]&/@Union@@t)->0]&

Example

ReplacePart[t=1##&~Array~{#,#},Join@@(Rest[t~Position~#]&/@Union@@t)->0]&[10]

{{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {0, 0, 0, 0, 0, 12, 14, 16, 18, 20}, {0, 0, 0, 0, 15, 0, 21, 24, 27, 30}, {0, 0, 0, 0, 0, 0, 28, 32, 36, 40}, {0, 0, 0, 0, 25, 0, 35, 0, 45, 50}, {0, 0, 0, 0, 0, 0, 42, 48, 54, 60}, {0, 0, 0, 0, 0, 0, 49, 56, 63, 70}, {0, 0, 0, 0, 0, 0, 0, 64, 72, 80}, {0, 0, 0, 0, 0, 0, 0, 0, 81, 90}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 100}}


Grid[%]

tble


Explanation

We exploit the fact that the spiral-order of the positions of any digit, n, is the same as the the order of row-col positions returned by the function, Positions!

The location of the first occurrence of each number (whether one orders by the spiral or by the table position) will be the first element returned by Position. That first-occurrence cell will be left as it is. The remaining instances of the number are replaced by 0.

Let's look at how this works, examining for the case of n==18. The idea is to start with the multiplication table:

(t = Table[k Range@#, {k, #}] &[10]) // Grid

and locate the row-col positions of each number. For example, 18 is located at Row 2, Col 9 (the first instance); Row 3, Col 6; Row 6, Col 3; and Row 9, Col 2. These have the respective spiral-order positions {44, 58, 68, 82}.

Position[t, 18]

{{2, 9}, {3, 6}, {6, 3}, {9, 2}}

as the following table shows.

table2

The final 3 instances of 18 need to be replaced by 0. (We'll use a large bold blue zeros so they can be easily spotted.)

ReplacePart[%, {{3, 6}, {6, 3}, {9, 2}} -> Style[0, {Blue, Bold, 16}]]// Grid

table3

\$\endgroup\$
  • \$\begingroup\$ Is there a reason for not writing a Function? \$\endgroup\$ – LegionMammal978 Nov 28 '15 at 20:39
  • 1
    \$\begingroup\$ I was having trouble with nested pure functions, but this iteration doesn't require that. thanks. \$\endgroup\$ – DavidC Nov 28 '15 at 21:04
  • \$\begingroup\$ I count 117 bytes excluding the newline. \$\endgroup\$ – LegionMammal978 Nov 28 '15 at 21:11
  • \$\begingroup\$ Also, some more golfs \$\endgroup\$ – LegionMammal978 Nov 28 '15 at 21:22
  • \$\begingroup\$ Some more golfs: ReplacePart[t=1##&~Array~{#,#},Join@@(Rest[t~Position~#]&/@Union@@t)->0]& \$\endgroup\$ – alephalpha Nov 29 '15 at 3:44
2
\$\begingroup\$

Python, 99 95 90 89 87 81 bytes

Golfed code:

n=range(1,input()+1);m=[]
for x in n:l=[(x*y,0)[x*y in m]for y in n];m+=l;print l

Ungolfed:

n=range(1,input()+1);
m=[]
for x in n:
  l=[(x*y,0)[x*y in m]for y in n];
  m+=l;
  print l

Output:

10 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
[0, 0, 0, 0, 0, 12, 14, 16, 18, 20]
[0, 0, 0, 0, 15, 0, 21, 24, 27, 30] 
[0, 0, 0, 0, 0, 0, 28, 32, 36, 40]
[0, 0, 0, 0, 25, 0, 35, 0, 45, 50] 
[0, 0, 0, 0, 0, 0, 42, 48, 54, 60]
[0, 0, 0, 0, 0, 0, 49, 56, 63, 70] 
[0, 0, 0, 0, 0, 0, 0, 64, 72, 80]
[0, 0, 0, 0, 0, 0, 0, 0, 81, 90] 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 100]
\$\endgroup\$
  • \$\begingroup\$ thanx @valuah for input byte shave \$\endgroup\$ – CSᵠ Nov 29 '15 at 5:20
2
\$\begingroup\$

MATLAB, 96 88 87 86 79 bytes

This is the 79 byte code, which follows the example outputs (for n=0 specifically)

n=input('');m=+(n>0);for i=1:n;a=i*(1:i);for j=a;m(m==j)=0;end;m(1:i,i)=a;end;m

This one is 75 bytes, has the same behaviour except for n=0 which will produce an empty array as per the implication of the question (N by N array = 0 by 0 = empty array).

n=input('');m=[];for i=1:n;a=i*(1:i);for j=a;m(m==j)=0;end;m(1:i,i)=a;end;m

This also works with Octave. You can try it online here. The code is already added as a file named 'multspiral.m'. So at the Octave prompt, type multspiral and press enter. You should then enter the size of the table (e.g. 4). The output will then be printed.


How does it work?

First this takes an input number as required (e.g. 6, 4, etc.)

n=input('');

Then we handle cases for n=0 and n=1 - these are given special treatment as they are two that don't follow the rule I am using for generating the arrays - in fact this could be 5 bytes shorter if not for the obscure n=0 case.

m=+(n>0);

Then for all values of n>2, we do some looping until the matrix is grown to the correct size.

for i=2:n;

There are actually only three simple differences between n and n+1 for all n>=2. These are:

  1. A new column is added rightmost in the array which contains the numbers n(1:n). This is easily calculated with:

     a=i*(1:i);
    
  2. Any elements which will be added in that new column must be removed from the existing matrix (set to zero) as they will always come later in the spiral than the new column. This is removed using a nestled for loop to set all elements in the current matrix which are in the new column to be zero.

    for j=a;
        m(m==j)=0;
    end;
    
  3. There is a new row bottom most for which every element except that which is in the new column will be zero. When the new column added, because of the out of bounds indices that has been intentionally created are padded automatically with 0. One of MATLAB's strong features is that it can grow arrays without any special handling, so we can add the new row and column simply with:

    m(1:i,i)=a;
    

Finally we have the end of the for loop - which once reached, the matrix m contains our output. As you are flexible with your output format, the matrix is shown by simply having m as a new line without a semicolon

end;
m

As an example, if we run the program, enter the number 10, we get the following output:

m =
     1     2     3     4     5     6     7     8     9    10
     0     0     0     0     0    12    14    16    18    20
     0     0     0     0    15     0    21    24    27    30
     0     0     0     0     0     0    28    32    36    40
     0     0     0     0    25     0    35     0    45    50
     0     0     0     0     0     0    42    48    54    60
     0     0     0     0     0     0    49    56    63    70
     0     0     0     0     0     0     0    64    72    80
     0     0     0     0     0     0     0     0    81    90
     0     0     0     0     0     0     0     0     0   100
\$\endgroup\$
1
\$\begingroup\$

Haskell, 103 99 bytes

import Data.Lists
f 0=[[0]]
f n=chunksOf n$foldr(\c d->c:replace[c][0]d)[][a*b|a<-[1..n],b<-[1..n]]

Usage example: f 4-> [[1,2,3,4],[0,0,6,8],[0,0,9,12],[0,0,0,16]].

I've just discovered the Data.Lists module which has nice functions on lists (such as replace) and re-exports Data.List, Data.List.Split and Data.List.Extras.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 67 63 61 bytes

->n{s,x=1..n,{};s.map{|c|s.map{|r|x[v=c*r]==1?0:(x[v]=1;v)}}}

63 bytes

->n{s,x=1..n,{};s.map{|c|s.map{|r|e=x[v=c*r]==1?0:v;x[v]=1;e}}}

67 bytes

->n{s,x=1..n,[];s.map{|c|s.map{|r|e=x.include?(v=c*r)?0:v;x<<v;e}}}

Usage:

->n{s,x=1..n,{};s.map{|c|s.map{|r|x[v=c*r]==1?0:(x[v]=1;v)}}}[10]
=> [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [0, 0, 0, 0, 0, 12, 14, 16, 18, 20], [0, 0, 0, 0, 15, 0, 21, 24, 27, 30], [0, 0, 0, 0, 0, 0, 28, 32, 36, 40], [0, 0, 0, 0, 25, 0, 35, 0, 45, 50], [0, 0, 0, 0, 0, 0, 42, 48, 54, 60], [0, 0, 0, 0, 0, 0, 49, 56, 63, 70], [0, 0, 0, 0, 0, 0, 0, 64, 72, 80], [0, 0, 0, 0, 0, 0, 0, 0, 81, 90], [0, 0, 0, 0, 0, 0, 0, 0, 0, 100]]
\$\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.