(EDIT: Grazie a Yoyo Zhou per aver sottolineato un difetto in questo modello -- Anders ha il risultato finale della discussione nella nuova versione della sua risposta.)
Mi è piaciuto l'Haskell nella risposta di Anders' ma la schermata di sblocco di Android (almeno sul mio telefono con Froyo) è ancora più permissiva di quanto lui abbia supposto. Infatti, è anche possibile seguire un punto con un punto ad una mossa a cavaliere, senza aver toccato nessun altro punto. Il numero di schemi disponibili diventa 766752.
E' facile dimostrare la mossa del cavaliere se lo si fa lentamente -- basta stare lontani dal disco scuro intorno ad ogni punto vicino.
D'altra parte, se faccio una mossa della torre o dell'alfiere di lunghezza 2, si riempie il punto intermedio come se lo avessi toccato. (Con il feedback tattile, è chiaro che non ho effettivamente toccato il punto, quindi non credo che un tocco più abile permetterebbe di 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.