(EDIT: Gracias a Yoyo Zhou por señalar un fallo en este modelo — Anders tiene el resultado final de la discusión en la nueva versión de su respuesta.)
Me ha gustado el Haskell de la respuesta de Anders, pero la pantalla de desbloqueo de Android (al menos en mi teléfono con Froyo) sigue siendo más permisiva de lo que él supone. De hecho, también es posible seguir un punto con un punto a un movimiento de caballo, sin haber tocado ningún otro punto. El número de patrones disponibles se convierte en 766752.
Es fácil demostrar el movimiento de caballo si lo hace lentamente – sólo tiene que alejarse del disco oscuro alrededor de cada punto cercano.
Por otro lado, si hago un movimiento de torre o de alfil de longitud 2, rellena el punto intermedio como si lo hubiera tocado. (Con la retroalimentación táctil, está claro que en realidad no he tocado el punto, así que no creo que un toque más hábil permita evitarlo). So those are the only unavailable moves.
This variant of Anders’s code computes the result:
- 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
This compares to the number of patterns of length >= 4 that you could make from 9 points with no restrictions on which you can reach from where:
- > sum . drop 4 $ scanl (*) 1 [9,8..1]
- 985824
so in fact exactly 2/9 of that class of patterns are unavailable.
Anders’ answer is a better upper bound on how many patterns could be practical to use, though — I find that the knight’s-move takes far too much care to execute when I just want to unlock my phone.