Este desafío es en parte un desafío de algoritmos, en parte un desafío de optimización y en parte simplemente un desafío de código más rápido.
La matriz AT está completamente especificada por su primera fila r
y primera columna c
. Cada elemento restante de la matriz es solo una copia del elemento que está diagonalmente hacia arriba y hacia la izquierda. Es decir M[i,j] = M[i-1,j-1]
. Permitiremos matrices T que no sean cuadradas. Sin embargo, siempre suponemos que el número de filas no es mayor que el número de columnas. Por ejemplo, considere la siguiente matriz T 3 por 5.
10111
11011
11101
Decimos que una matriz tiene la propiedad X si contiene dos conjuntos de columnas no vacías con índices no idénticos que tienen la misma suma (vector). La suma vectorial de una o más columnas es simplemente una suma de elementos de sus columnas. Esa es la suma de dos o más columnas que contienen x
elementos, cada una es otra columna que contiene x
elementos. La suma de una columna es trivialmente la columna misma.
La matriz anterior trivialmente tiene la propiedad X ya que la primera y la última columna son las mismas. La matriz de identidad nunca tiene la propiedad X.
Si solo eliminamos la última columna de la matriz anterior, obtenemos un ejemplo que no tiene la propiedad X y daría una puntuación de 4/3.
1011
1101
1110
La tarea
La tarea es escribir código para encontrar la matriz T de mayor puntuación con entradas binarias y que no tiene la propiedad X. Para mayor claridad, una matriz con entradas binarias tiene la propiedad de que cada una de sus entradas es 0 o 1.
Puntuación
Su puntaje será el número de columnas dividido por el número de filas en su mejor matriz de puntaje.
Desempate
Si dos respuestas tienen el mismo puntaje, gana la que presentó primero.
En el caso (muy) improbable de que alguien encuentre un método para obtener puntajes ilimitados, se aceptará la primera prueba válida de tal solución. En el caso aún más improbable de que pueda encontrar una prueba de la optimización de una matriz finita, por supuesto, también otorgaré la victoria.
Insinuación
Todas las respuestas en Buscar matriz de puntuación más alta sin propiedad X son válidas aquí, pero no son óptimas. Hay matrices T sin propiedad X que no son cíclicas.
Por ejemplo, hay una matriz T de 7 por 12 sin propiedad X, pero no existe dicha matriz cíclica.
El 21/11 superaría todas las respuestas actuales de este y el desafío anterior.
Idiomas y bibliotecas
Puede usar cualquier idioma que tenga un compilador / intérprete / etc. para Linux y cualquier biblioteca que también esté disponible gratuitamente para Linux.
Bonificación La primera respuesta con una puntuación superior a 2 obtiene un premio de recompensa inmediato de 200 puntos . ¡Ton Hospel ahora ha logrado esto!
Tabla de líderes actual
- C ++ . Puntuación 31/15 por Ton Hospel
- Java . Puntuación 36/19 por Peter Taylor
- Haskell . Puntuación 14/8 por alexander-brett
fuente
Respuestas:
C ++, puntaje
23/1225/1327/1428/1431/15Finalmente un resultado con relación> 2:
Exploré por completo de 1 a 14 filas. 15 tomaría demasiado tiempo para explorar por completo. Los resultados son:
El código que figura a continuación es una versión anterior del programa. La versión más reciente está en https://github.com/thospel/personal-propertyX .
fuente
Haskell 14/8 = 1.75
Anteriormente 9/6 = 1.5
Escribí esto, luego miré las respuestas a la otra pregunta y me ... desanimé.
fuente
main
, el número (en este caso8
) es la altura de la matriz, y el programa itera a través de los anchos[1..]
. Para cada combinación de alto / ancho, imprime una matriz de columnas de una matriz válida.C
Aquí hay una respuesta que funciona y es significativamente más eficiente en memoria que Haskell. Desafortunadamente, mi computadora aún es demasiado lenta para alcanzar un rendimiento superior a 14/8 en un período de tiempo razonable.
Intente compilar
gcc -std=c99 -O2 -fopenmp -o matrices.exe matrices.c
y ejecutar conmatrices.exe width height
o similar. La salida es un número entero, cuyos bits forman la base de la matriz en cuestión, por ejemplo:Entonces, desde entonces
1650223 = 0b110010010111000101111
, la matriz en cuestión es:Si alguien con 8 núcleos y tiempo en sus manos quiere ejecutar esto por un tiempo, creo que podrían resultar algunas cosas buenas :)
fuente
valid i: 7481
. En python bin (7481) es 0b1110100111001 que no es lo suficientemente largo. ¿Alguna idea de lo que está pasando?