Pantalla de bloqueo de Android

25

Introducción

Estás sentado en una sala de juntas al final de una larga mesa. Miras a tu alrededor y ves a Tim Cook, la Junta Directiva de Apple, el fantasma de Steve Jobs y Jack Donaghy. Apple ha convocado esta reunión porque se han dado cuenta de lo genial que es la pantalla de bloqueo de Android y quieren ponerla 1-UP. Todos en la sala te miran mientras Ghost Steve llora: "¡Ayúdame, CodeGolf Man! ¡Eres mi única esperanza!"

El problema

La pantalla de bloqueo de Android es una cuadrícula de puntos de 3 x 3 que se puede conectar deslizando un dedo de un punto al siguiente, creando una ruta. Una contraseña se considera cualquier ruta posible que incluya cualquier número de puntos y excluya cualquier número de puntos. (En un teléfono real, la ruta debe tener al menos 4 puntos de largo. Para este desafío, ignore esa restricción). Apple planea reemplazar la cuadrícula 3 x 3 con una cuadrícula M x N, que es (M * N) / 9 veces mejor!

Reglas:

  • Una ruta de punto cero no es una contraseña, pero una ruta de 1 punto es
  • Un camino puede cruzarse
  • Una ruta no puede cruzar directamente sobre un punto sin incluir ese punto
  • Un punto solo se puede usar una vez
  • Las rutas que son idénticas por rotación no son la misma contraseña
  • Las rutas que son idénticas pero ordenadas al revés no son la misma contraseña

    • Por ejemplo, en una cuadrícula de 3x3 con puntos numerados del 1 al 9:

    1 2 3
4 5 6
7 8 9

    Algunas rutas válidas son:

    1
3
7,2,3
1,5,9,2
1,8,6,5,4
4,2,3,5,6,7,8,9
5,9,6,4

    Y algunas rutas inválidas son:

    1,3
1,9,5
7,5,4,7
4,6

    Su entrada será de tres números:

    (M,N,d)

    Donde la cuadrícula es M x N, y d es la longitud de la ruta

    1 <= M <= 16
1 <= N <= 16
1 <= d <= M * N

    Su programa o función recibirá la entrada como una cadena separada por comas, y debe devolver el número de posibles contraseñas de esa longitud. Por ejemplo:

    Input:  2,2,1 
Output: 4
Input:  2,2,2
Output: 12
Input:  7,4,1
Output: 28

    Se aplican las reglas estándar del código de golf, ¡el código más corto gana!

    //If I've made a mistake or the rules are unclear, please correct me!
    code-golf number combinatorics Platatat
    fuente
    2
    ¿Es la entrada una cadena separada por comas o tres parámetros separados?
    user80551
    1
    @ user80551 Según el contexto, creo que será una cadena si se ingresa a un programa, o parámetros separados si se usa para llamar a la función.
    user12205
    1
    @Platatat, ¿puede responder a la pregunta del usuario 80551, ya que esto es realmente importante para diseñar el código?
    RononDex
    3
    Debe decidir si habrá un límite de tiempo para el tiempo de compilación y ejecución de una solución dada. Sin dicho límite, es fácil escribir un programa que, en teoría, verifique cuál de todas las 256!permutaciones de los puntos en la cuadrícula de 16 x 16 representa un patrón de desbloqueo válido. En la práctica, dicho programa nunca terminaría.
    Dennis
    3
    Pero dije que el problema se basaba en el sistema de bloqueo de Android ... Entonces, ¿por qué no debería usar las mismas reglas que el sistema de bloqueo de Android?
    Platatat

    Respuestas:

    14

    Python - 170 bytes

    from fractions import*
p=lambda m,n,d,l=0,s=set():d<1or sum([p(m,n,d-1,i,s|{i})for i in range(m*n)if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))])

    Me doy cuenta de que los corchetes internos sum([...])no son estrictamente necesarios, pero hay una gran penalización de rendimiento por no incluirlos.

    Salida para todos los 3x3:

    for i in range(4, 10):
  print p(3, 3, i)

    Produce:

    1624
7152
26016
72912
140704
140704

    Para fines de prueba / confirmación, los primeros 6 valores para una placa 4x5:

    20
262
3280
39644
459764
5101232

    4x5 es un caso interesante para verificar, porque tiene saltos de clavija 2x2, 3x3 y 2x4.

    Breve explicacion

    En general, esta es una búsqueda exhaustiva, con poda acumulativa. Por ejemplo, dado que p(3, 3, 4)es 1624, p(3, 3, 5)solo verificará 8120 posibilidades, en lugar de verificar ingenuamente todas las 15120. La mayor parte de la lógica está contenida en la condición:

    if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))

    En inglés simple, esto se puede entender como:

    If no pegs have been used yet
     OR
   the target peg has not yet been used
     AND
   each of the pegs directly between the target peg and the
   current peg (a.k.a. "jumped over") have already been used
    primo
    fuente
    2
    ¿Podría explicar qué demonios está pasando aquí?
    Aprıʇǝɥʇuʎs
    1
    Puede guardar algunos bytes si tiene sun conjunto en lugar de una lista. No veo la gran penalización de rendimiento de perder los corchetes; ¿Por qué habría tal pena?
    user2357112 es compatible con Monica el
    1
    @ user2357112 uno está sumando sobre un Generador, el otro sobre una Lista. Con CPython, tienes razón, no hay mucha diferencia (solo un 20% más lento). Con PyPy, es más de 5 veces más lento.
    primo
    1
    @ user2357112 Finalmente veo lo que quisiste decir al definir scomo un conjunto. Mi lección de Python para hoy: {i}evalúa como set([i]). Hubiera esperado un error de sintaxis. Agregar un elemento a un conjunto se convierte en s|{i}, y también permite i in sser reemplazado por s&{i}.
    primo