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.
Una matriz cíclica está completamente especificada por su primera fila r
. Las filas restantes son permutaciones cíclicas de la fila r
con un desplazamiento igual al índice de la fila. Permitiremos matrices cíclicas que no sean cuadradas para que simplemente falten algunas de sus últimas filas. 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 cíclica de 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 dos columnas es simplemente una suma de elementos de las dos columnas. Esa es la suma de dos columnas que contienen x
elementos, cada una es otra columna que contiene x
elementos.
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 cíclica de mayor puntuación cuyas entradas son todas 0 o 1 y que no tiene la propiedad X.
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
Obtener un puntaje de 12/8 no es demasiado difícil.
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.
Entradas principales
- 36/19 por Peter Taylor (Java)
- 32/17 por Suboptimus Prime (C #)
- 21/12 por justhalf (Python 2)
fuente
01
tiene la propiedad X porque el conjunto de la primera columna tiene la misma suma de vectores que el conjunto vacío. ¿Quizás quiso decir conjuntos de columnas no vacíos? Sin embargo, creo que es más limpio no cambiarlo.01
tiene la propiedad X:(1) = (0) + (1)
. Si desea excluir eso, debe decir que los dos conjuntos de columnas deben ser disjuntos.2^m
combinaciones de columnas a verificar la propiedad X. Si de alguna manera pudiéramos idear un esquema de "encuentro en el medio" (ver el problema de "suma de subconjuntos") esto probablemente podría reducir eso am * 2^(m/2)
...Respuestas:
16/9 20/11 22/12 28/15 30/16 32/1734/18 36/19 (Java)Esto utiliza una serie de ideas para reducir el espacio de búsqueda y el costo. Vea el historial de revisiones para obtener más detalles sobre versiones anteriores del código.
0
y1
) y trabajando; Utilizo el algoritmo descrito en el código A Gray para collares de densidad fija y palabras de Lyndon en tiempo amortizado constante , Sawada y Williams, Theoretical Computer Science 502 (2013): 46-54.BigInteger
para dar una prueba exacta. Obtengo una mejora significativa de la velocidad, a riesgo de falsos negativos, al operar el módulo un gran primo y mantener todo en primitivos. El primer que he elegido es el más grande más pequeño que 2 57 , ya que eso permite multiplicar por la base de mi representación vectorial nocional sin desbordar.{-1,0,1}^m
tiene su negación también{-1,0,1}^m
, solo es necesario almacenar uno de los dos.2n/(n+1)
, estoy acelerando las cosas simplemente probando eso.El primero encontrado es
y ese es el único éxito en 15 horas.
Ganadores más pequeños:
fuente
n
lugar de hacerlorows
, aunque es a prueba de fallas en el sentido de que descartaría soluciones válidas en lugar de aceptar soluciones inválidas. Tampoco afecta los resultados.Python 2 - 21/12
En el proceso de probar que
2-(3/n)
siempre existe un para cualquiern
Inspirado por esta pregunta , utilicé la secuencia de De Bruijn para forzar con fuerza bruta las posibles matrices. Y después de la fuerza bruta
n=6,7,8,9,10
, encontré un patrón que la solución más alta siempre tiene forma(n, 2n-3)
.Así que creé otro método para aplicar fuerza bruta solo a esa forma de matriz, y utilizo el multiprocesamiento para acelerar las cosas, ya que esta tarea es altamente distribuible. En ubuntu de 16 núcleos, puede encontrar una solución
n=12
en aproximadamente 4 minutos:La mayor parte del cálculo va a verificar la propiedad X, que requiere verificar todos los subconjuntos (hay
2^(2n-3)
subconjuntos)Tenga en cuenta que giro la primera fila hacia la izquierda, no hacia la derecha como en la pregunta. Pero estos son equivalentes, ya que puede revertir toda la matriz. =)
El código:
Antigua respuesta, para referencia
La solución óptima hasta ahora (
n=10
):Para
n=7
:Una solución con la forma descrita por OP (
n=8
):Pero uno mejor (
n=8
):También encontró otra solución óptima en
n=9
:El código es el siguiente. Es solo fuerza bruta, pero al menos puede encontrar algo mejor que la afirmación de OP =)
fuente
n >= 31
, lo que implica que necesitaría verificar hasta2^(2n-3) = 2^59
combinaciones de vectores de 31 dimensiones. No terminará en nuestra vida = Dn*(2n-3)
24/13 26/14 28/15 30/1632/17 (C #)Editar: información obsoleta eliminada de mi respuesta. Estoy usando principalmente el mismo algoritmo que Peter Taylor ( Editar: parece que ahora está usando un algoritmo mejor), aunque he agregado algunas de mis propias optimizaciones:
HasPropertyXFast
función, que comprueba rápidamente si hay un conjunto pequeño con sumas iguales antes de usar el enfoque "cumplir en el medio".HasPropertyXFast
función, empiezo comprobando conjuntos de columnas con 1 columna, luego con 2, 3 y así sucesivamente. La función vuelve tan pronto como se encuentra la primera colisión de sumas de columna. En la práctica, significa que generalmente tengo que verificar unos pocos cientos o miles de conjuntos de columnas en lugar de millones.long
variables para almacenar y comparar columnas enteras y sus sumas vectoriales. Este enfoque es al menos un orden de magnitud más rápido que comparar columnas como matrices.long
el tipo de datos y para mis patrones de uso.Salida del programa:
Código:
Archivo de configuración:
fuente
ulong
y dejar que el cambio se ajuste en lugar de usarBigInteger
.GetSumOfColumns
agrega un ciclo adicional que esperaría costar más que ese factor de 2. La clasificación de la máscara suena interesante: tal vez podría editar la respuesta para hablar un poco al respecto? (Y en algún momento experimentaré con una forma alternativa de abortar temprano: la razón por la que no puedo hacerlo es que HashSet no admite la iteración y modificación concurrentes, pero tengo ideas para evitar la necesidad de un iterador) .