Introducción
Todos conocen el juego de tres en raya, pero en este desafío, vamos a introducir un pequeño giro. Solo vamos a usar cruces . La primera persona que coloca tres cruces seguidas pierde. Un hecho interesante es que la cantidad máxima de cruces antes de que alguien pierda, es igual a 6 :
X X -
X - X
- X X
Eso significa que para un tablero de 3 x 3, la cantidad máxima es 6 . Entonces, para N = 3, necesitamos generar 6.
Otro ejemplo, para N = 4, o un tablero de 4 x 4:
X X - X
X X - X
- - - -
X X - X
Esta es una solución óptima, puede ver que la cantidad máxima de cruces es igual a 9 . Una solución óptima para una placa de 12 x 12 es:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X
Esto da como resultado 74 .
La tarea
La tarea es simple, dado un número entero mayor que 0, genera la cantidad máxima de cruces que se pueden colocar sin tres X adyacentes en una línea a lo largo de una fila, columna o diagonalmente.
Casos de prueba
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
Se puede encontrar más información en https://oeis.org/A181018 .
Reglas
- Este es el código de golf , por lo que gana el envío con la menor cantidad de bytes.
- Puede proporcionar una función o un programa.
Respuestas:
Pyth,
575149 bytesAl igual que la solución CJam de @ PeterTaylor, esta es la fuerza bruta, por lo que se ejecuta en tiempo O (n 2 2 n 2 ). El intérprete en línea no termina en un minuto para n = 4.
Pruébelo aquí para N <4.
Prueba la función de diagonales .
fuente
CJam (
5856 bytes)Esto es increíblemente lento y usa mucha memoria, pero eso es código golf para ti.
Disección
fuente
O(n a^n)
dondea ~= 5.518
.DO,
460456410407362351318 bytesEsta es una muy mala respuesta. Es un enfoque de fuerza bruta increíblemente lento.
Estoy tratando de jugar un poco más al golf combinando losfor
bucles.Casos de prueba
Sin golf
Editar: declarar las variables int como parámetros no utilizados; elimina la coordenada y, solo usa index; mover variable a la lista de parámetros en lugar de global, corregir los parámetros innecesarios pasados a
s()
; combinar para bucles, eliminar paréntesis innecesarios; reemplazar&&
con*
,||
con+
; macro-ify la comprobación de 3 en una filafuente
#define d(x,y)b[x]*b[x+y]*b[x+y+y]
; cambiando el inicio des
as(i,m){for(m=n-2;
y sustitución de todos los casos den-2
; y cambiandob[x]++
ab[x++]++
y luego reemplazandox==n*n-1
conx==n*n
,x+1
conx
yx
conx-1
.C 263
264 283 309Editar Algunos bytes se guardaron gracias a Peter Taylor, menos de lo que esperaba. Luego, 2 bytes solían asignar más memoria, ahora puedo intentar un tamaño más grande, pero se está volviendo muy lento.
Nota Al agregar la explicación, descubrí que estoy desperdiciando bytes manteniendo la cuadrícula en la matriz R, para que pueda ver la solución encontrada ... ¡no se solicita para este desafío!
Lo eliminé en la versión de golf
Un programa de golf C que realmente puede encontrar la respuesta para n = 1..10 en un tiempo razonable.
Mi prueba:
Menos golf y tratando de explicar
fuente
buildRows
método; tal vez hasta 20 sifor(scanf("%d",&n);(v=2*V[i++])<1<<n;v%8<6&&V[++j]=v+1)v&&V[++j]=v;
es válido. (No tengo acceso a un compilador de C en este momento).999
significa que querrá ignorar esa parte. Aunque tal vez realmente debería hacerlo no codificado, de modo que, en principio, pueda abordar entradas más grandes que 11 o 12.Rubí, 263 bytes
Esta también es una solución de fuerza bruta y enfrenta los mismos problemas que la respuesta C de Cole Cameron, pero es aún más lenta ya que es rubí y no C. Pero bueno, es más corta.
Casos de prueba
Sin golf
fuente
Haskell, 143 bytes
De alguna manera esto no se hace, pero me divertí, así que aquí va:
Aquí está el código:
fuente