Android (sistema operativo): ¿Cuántas combinaciones tiene el desbloqueo de puntos de Android 9?

( EDITAR : Gracias a Yoyo Zhou por señalar una falla en este modelo: Anders tiene el resultado final de la discusión en la nueva versión de su respuesta).

Me gustó la respuesta de Haskell en Anders, pero la pantalla de desbloqueo de Android (al menos en mi teléfono con Froyo) es aún más permisiva de lo que él suponía. De hecho, también es posible seguir un punto con un punto alejado de un caballero, sin haber tocado ningún otro punto. El número de patrones disponibles se convierte en 766752.

Es fácil demostrar el movimiento del caballero si lo hace lentamente, solo manténgase alejado del disco oscuro alrededor de cada punto cercano.

Por otro lado, si hago un movimiento de torre o de alfil de longitud 2, se llena en el punto intermedio como si lo hubiera tocado. (Con la retroalimentación táctil, está claro que en realidad no toqué el punto, por lo que no creo que un toque más hábil haga posible evitar esto). Así que esos son los únicos movimientos no disponibles.

Esta variante del código de Anders calcula el resultado:

 import qualified Data.Set as S import Control.Monad(guard) points = [(row, col) | row <- [0..2], col <- [0..2]] adjacentButtons (x, y) = do (x', y') <- points guard $ 1 `elem` [abs $ x' - x, abs $ y' - y] return (x', y') extensions pattern = map (: pattern) . S.toList $ S.difference (S.fromList $ adjacentButtons =<< pattern) (S.fromList pattern) search pattern found = foldr search (pattern : found) $ extensions pattern valid pattern = length pattern >= 4 main = print . length . filter valid . foldr search [] $ map (:[]) points 

Esto se compara con el número de patrones de longitud> = 4 que puede hacer desde 9 puntos sin restricciones a las que puede llegar desde donde:

  > suma.  soltar 4 $ scanl (*) 1 [9,8..1]
 985824

de hecho, exactamente 2/9 de esa clase de patrones no están disponibles.

Sin embargo, la respuesta de Anders es un mejor límite superior sobre cuántos patrones podrían ser prácticos de usar: encuentro que el movimiento del caballero toma demasiada atención cuando solo quiero desbloquear mi teléfono.