La espiral de multiplicación única

13

Este está inspirado en el reciente desafío de la tabla de multiplicar de Hobbies de Calvin .

Escriba una función o programa que tome un número entero Ncomo entrada e imprima o devuelva una espiral de multiplicación única N-por-N. El código debe (en teoría) funcionar para N entre 0 y 1000 (sin embargo, generar esto puede ser difícil). El resultado debe ser equivalente a la tabla producida por el siguiente procedimiento:

  1. Completa una tabla de multiplicación N-por-N. Por ejemplo, para N = 3:

    1 2 3
    2 4 6
    3 6 9
    
  2. Siga una espiral en el sentido de las agujas del reloj desde la esquina superior izquierda, anotando los números que visita. Cuando visite un número que ya ha visitado, reemplácelo por 0.

Algunos ejemplos pueden dejarlo más claro:

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

Los números se encuentran así:

ingrese la descripción de la imagen aquí

Se acepta cualquier formato de salida razonable, pero debe ser una matriz N por N, no puede ser solo una lista. Se aceptan formatos como los siguientes, ya que hay N columnas fácilmente distinguibles de 1 por N o filas de N por 1:

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

El código más corto en bytes gana.

Stewie Griffin
fuente
¡Espío con mi pequeño ojo un tamiz modificado de eratóstenes! Estoy bastante seguro de que hay un patrón que puedes usar aquí que he visto en algún lugar u otro.
Addison Crump
2
¿Por qué habría una salida para n=0donde no hay cero en las tablas de multiplicar? Puedo entender que n=1saldría 1, pero ¿por qué incluir cero?
Tom Carpenter
@TomCarpenter, podría haber sido una mala decisión, pero sabía que habría una pregunta "¿Qué pasa con N = 0?", Así que hice la regla N = 0 -> 0. En retrospectiva, podría haber sido mejor decir que N> 0, pero ahora es demasiado tarde, me temo = /
Stewie Griffin
2
@StewieGriffin Usted dijo que la salida debe ser una matriz N por N, por lo que la salida n=0debe ser una matriz 0 por 0 o la pregunta sería inconsistente.
alephalpha

Respuestas:

3

J, 22 bytes

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

Produce una matriz de 0 por 0 para n=0.

alephalpha
fuente
8

Mathematica 123122117 98 92 73 bytes

¡Con 24 bytes guardados gracias a LegionMammal978 y otros 19 de alephalpha!


Sorprendentemente, en esta tabla, varias instancias de cualquier número entero ntendrán el mismo orden relativo en la espiral que en la tabla misma. La primera aparición de un número se nencuentra en la celda donde ese número aparece primero en la tabla (cuando se llena la tabla fila por fila). Esto significa que el enfoque puede ignorar por completo la restricción espiral, ya que no tiene ninguna relación con el resultado. (Consulte la explicación a continuación).

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

Ejemplo

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


Explicación

Explotamos el hecho de que el orden en espiral de las posiciones de cualquier dígito, n, es el mismo que el orden de las posiciones fila-col devuelto por la función, Positions ,!

La ubicación de la primera aparición de cada número (ya sea que se ordene por la espiral o por la posición de la tabla) será el primer elemento devuelto por Position . Esa celda de primera aparición se dejará como está. Las instancias restantes del número se reemplazan por 0.

Veamos cómo funciona esto, examinando el caso de n==18. La idea es comenzar con la tabla de multiplicar:

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

y ubique las posiciones fila-columna de cada número. Por ejemplo, 18 está ubicado en la Fila 2, Col 9 (la primera instancia); Fila 3, columna 6; Fila 6, Col 3; y Fila 9, Col 2. Tienen las respectivas posiciones de orden en espiral {44, 58, 68, 82}.

Position[t, 18]

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

como muestra la siguiente tabla.

Tabla 2

Las últimas 3 instancias de 18 deben reemplazarse por 0. (Utilizaremos unos ceros azules en negrita grandes para que se puedan ver fácilmente).

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

Tabla 3

DavidC
fuente
¿Hay alguna razón para no escribir un Function?
LegionMammal978
1
Estaba teniendo problemas con las funciones puras anidadas, pero esta iteración no requiere eso. Gracias.
DavidC
Cuento 117 bytes excluyendo la nueva línea.
LegionMammal978
Además, algunos campos de golf más
LegionMammal978
Algunos campos de golf más:ReplacePart[t=1##&~Array~{#,#},Join@@(Rest[t~Position~#]&/@Union@@t)->0]&
alephalpha
2

Python, 99 95 90 89 87 81 bytes

Código de golf:

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

Sin golf:

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

Salida:

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]
CSᵠ
fuente
gracias @valuah por entrada de bytes de afeitado
CSᵠ
2

MATLAB, 96 88 87 86 79 bytes

Este es el código de 79 bytes, que sigue las salidas de ejemplo (para n = 0 específicamente)

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

Este es de 75 bytes, tiene el mismo comportamiento, excepto para n = 0 que producirá una matriz vacía según la implicación de la pregunta (N por N matriz = 0 por 0 = matriz vacía).

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

Esto también funciona con Octave . Puedes probarlo en línea aquí . El código ya se agregó como un archivo llamado 'multspiral.m'. Entonces, en el indicador de octava, escriba multspiraly presione Intro. Luego debe ingresar el tamaño de la tabla (por ejemplo, 4). La salida se imprimirá.


¿Como funciona?

Primero, toma un número de entrada según sea necesario (por ejemplo, 6, 4, etc.)

n=input('');

Luego manejamos casos para n=0y n=1, a estos se les da un tratamiento especial, ya que son dos que no siguen la regla que estoy usando para generar las matrices, de hecho, esto podría ser 5 bytes más corto si no fuera por el n=0caso oscuro .

m=+(n>0);

Luego, para todos los valores de n>2, hacemos algunos bucles hasta que la matriz crezca hasta el tamaño correcto.

for i=2:n;

En realidad, solo hay tres diferencias simples entre ny n+1para todos n>=2. Estos son:

  1. Se agrega una nueva columna en el extremo derecho de la matriz que contiene los números n(1:n). Esto se calcula fácilmente con:

     a=i*(1:i);
    
  2. Cualquier elemento que se agregará en esa nueva columna debe eliminarse de la matriz existente (establecer en cero) ya que siempre vendrá más tarde en la espiral que la nueva columna. Esto se elimina mediante un bucle anidado para establecer todos los elementos en la matriz actual que están en la nueva columna para que sean cero.

    for j=a;
        m(m==j)=0;
    end;
    
  3. Hay una nueva fila en la parte inferior para la cual todos los elementos, excepto el que está en la nueva columna, serán cero. Cuando se agrega la nueva columna, debido a los índices fuera de los límites que se han creado intencionalmente, se rellenan automáticamente con 0. Una de las características sólidas de MATLAB es que puede aumentar las matrices sin ningún manejo especial, por lo que podemos agregar la nueva fila y columna simplemente con:

    m(1:i,i)=a;
    

Finalmente tenemos el final del ciclo for, que una vez alcanzado, la matriz mcontiene nuestra salida. Como es flexible con su formato de salida, la matriz se muestra simplemente teniendo mcomo una nueva línea sin punto y coma

end;
m

Como ejemplo, si ejecutamos el programa, ingresamos el número 10, obtenemos el siguiente resultado:

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
Tom Carpenter
fuente
1

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

Ejemplo de uso: f 4-> [[1,2,3,4],[0,0,6,8],[0,0,9,12],[0,0,0,16]].

Acabo de descubrir el Data.Listsmódulo que tiene buenas funciones en listas (como replace) y reexportaciones Data.List, Data.List.Splity Data.List.Extras.

nimi
fuente
1

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

Uso:

->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]]
Vasu Adari
fuente