Dos filas de una matriz son ortogonales si su producto interno es igual a cero. Llame a una matriz con todas las filas ortogonales por pares una matriz ortogonal . Una matriz circulante es aquella en la que cada vector de fila gira un elemento a la derecha en relación con el vector de fila anterior. Solo nos interesarán las matrices donde las entradas son -1
o 1
.
Tarea
Escribir código que cuente como muchos diferentes n/2
de n
matrices ortogonales, circulantes como sea posible en 2 minutos (incluso n
).
Entrada
El código no tiene entrada. Puede probar cualquier valor par de n
me gusta. Por ejemplo, el código podría intentar todo lo n
que son múltiplos de 4
comenzar desde el más pequeño y también intentarlo n = 2
.
Salida
El número de matrices circulantes ortogonales que ha encontrado. También debería haber un simple cambio en su código para permitirle generar las propias matrices.
Puntuación
El número de matrices circulantes que has encontrado.
Consejos
Las matrices ortogonales n/2
por n
circulantes solo existen cuando n
es un múltiplo de 4
o n
es menor que 4
.
Un ejemplo de matriz circulante ortogonal es:
-1 1 -1 -1
-1 -1 1 -1
Consejos para un enfoque ingenuo
El enfoque más ingenuo es simplemente iterar sobre todas las matrices posibles. Esto se puede acelerar usando las siguientes dos observaciones.
Para probar la ortogonalidad de una matriz circulante solo necesitamos comparar cada fila con la primera. Esto se implementa en el código de muestra.
Podemos iterar sobre las palabras de Lyndon y luego, si encontramos una matriz ortogonal, multiplique por el número de rotaciones posibles. Esta idea aún no se ha probado, por lo que puede tener errores.
Código de muestra
Esta es una respuesta python muy simple e ingenua. Lo ejecuté usando timeout 120
.
import itertools
def check_orthogonal(row):
for i in xrange(1,int(n/2)):
if (sum(row[j]*row[(j+i) % n] for j in xrange(n)) != 0):
return False
return True
counter = 0
for n in xrange(4,33,4):
for row in itertools.product([-1,1],repeat = n):
if check_orthogonal(row):
counter +=1
print "Counter is ", counter, ". n = ", n
Pruebas de corrección
Para n = 4,8,12,16,20,24,28
, el número de matrices distintas que debe obtener es 12,40,144,128,80,192,560
, respectivamente.
Niveles de genialidad
A juzgar por el código de muestra, por la presente presento dos niveles de genialidad que cualquier respuesta puede aspirar a lograr.
La genialidad del nivel de plata se logra al obtener una puntuación o 1156 .
El nivel de oro de la genialidad es llegar más alto que eso.
Idiomas y bibliotecas
Puede usar cualquier idioma o biblioteca que desee (que no fue diseñada para este desafío). Sin embargo, para fines de puntuación, ejecutaré su código en mi máquina, así que proporcione instrucciones claras sobre cómo ejecutarlo en Ubuntu.
Mi máquina Los tiempos se ejecutarán en mi máquina. Esta es una instalación estándar de Ubuntu en un procesador AMD FX-8350 de ocho núcleos de 8GB. Esto también significa que necesito poder ejecutar su código.
Respuestas principales
332 por flawr en octava
404 por RT en Python
744 por solución de muestra usando pypy
1156 por Thomas Kwa usando Java . ¡Increíble nivel de plata!
1588 por Reimer Behrends en OCaml . ¡Nivel de oro genialidad!
n
que sea múltiplo de cuatro?Respuestas:
OCaml, 1588 (n = 36)
Esta solución utiliza el enfoque de patrón de bits habitual para representar vectores de -1s y 1s. El producto escalar se calcula como de costumbre tomando el xor de los vectores de dos bits y restando n / 2. Los vectores son ortogonales si su xor tiene exactamente n / 2 bits establecidos.
Las palabras de Lyndon no son per se útiles como representación normalizada para esto, ya que excluyen cualquier patrón que sea una rotación de sí mismo. También son relativamente caros de calcular. Por lo tanto, este código utiliza una forma normal algo más simple, que requiere que la secuencia consecutiva más larga de ceros después de la rotación (o uno de ellos, si hay múltiplos) debe ocupar los bits más significativos. Se deduce que el bit menos significativo siempre es 1.
Observe también que cualquier vector candidato debe tener al menos n / 4 unos (y como máximo 3n / 4). Por lo tanto, solo consideramos vectores con n / 4 ... n / 2 bits establecidos, ya que podemos derivar otros a través del complemento y la rotación (en la práctica, todos estos vectores parecen tener entre n / 2-2 y n / 2 + 2 unos , pero eso también parece ser difícil de probar).
Construimos estas formas normales desde el bit hacia arriba menos significativo, observando la restricción de que cualquier ejecución restante de ceros (llamados "espacios" en el código) debe seguir nuestro requisito de forma normal. En particular, mientras haya que colocar al menos un 1 bit más, debe haber espacio para el espacio actual y otro que sea al menos tan grande como el espacio actual o cualquier otro espacio observado hasta ahora.
También observamos que la lista de resultados es pequeña. Por lo tanto, no intentamos evitar duplicados durante el proceso de descubrimiento, sino simplemente registrar los resultados en conjuntos por trabajador y calcular la unión de estos conjuntos al final.
Vale la pena señalar que el costo de tiempo de ejecución del algoritmo aún crece exponencialmente y a un ritmo comparable al de la versión de fuerza bruta; lo que esto nos compra es esencialmente una reducción por un factor constante, y tiene el costo de un algoritmo que es más difícil de paralelizar que la versión de fuerza bruta.
Salida para n hasta 40:
El programa está escrito en OCaml, para ser compilado con:
Ejecute
./orthcirc -help
para ver qué opciones admite el programa.En las arquitecturas que lo admiten,
-fno-PIC
puede ofrecer una pequeña ganancia de rendimiento adicional.Esto está escrito para OCaml 4.02.3, pero también puede funcionar con versiones anteriores (siempre que no sean demasiado antiguas).
ACTUALIZACIÓN: Esta nueva versión ofrece una mejor paralelización. Tenga en cuenta que utiliza
p * (n/4 + 1)
subprocesos de trabajo por instancia del problema, y algunos de ellos aún se ejecutarán considerablemente más cortos que otros. El valor dep
debe ser una potencia de 2. La aceleración en 4-8 núcleos es mínima (quizás alrededor del 10%), pero se escala mejor a una gran cantidad de núcleos para grandesn
.fuente
Java, 1156 matrices
Utiliza una máscara de bits bastante ingenua, y toma menos de 15 segundos para n = 28 en mi máquina.
Las matrices circulantes están determinadas por sus primeras filas. Por lo tanto, represento las primeras filas de las matrices como vectores de bits: 1 y 0 representan -1 y 1. Dos filas son ortogonales cuando el número de bits configurados cuando se juntan es n / 2.
No puedo hacer que Eclipse funcione en este momento, así que esto se probó en repl.it.
Aquí está el número de primeras filas que son ortogonales a las primeras r filas posteriores para n = 28:
Optimizaciones:
long
y luego uso unoand
con los N bits más bajos para extraer los necesarios.Posibles optimizaciones adicionales:
00
y usar sus rotaciones (y las rotaciones del NOT) cuando encontramos una matriz ortogonal. Podemos hacer esto porque0101...01
y1010...10
no son posibles las primeras filas, y todas las demás contienen a00
o a11
.fuente
n=36
.Python (matrices 404 en i5-5300U)
Publicando esto principalmente como un punto de partida para que otros mejoren, esto se puede limpiar mucho, paralelizar, etc.
fuente
Matlab / Octave, 381/328 matrices
También solo el enfoque ingenuo, probando todas las combinaciones posibles.
fuente
n
y unaz
, estas dos se pueden comentar con una sola%
. Y luego puede agregar un;
después decounter = counter+1
y elk/N
que suprimirá la salida.