1votos

Jail Cracker en Haskell

por josejuan hace 6 meses

Búsqueda dicotómica acotada y no acotada. Se puede desconocer completamente el nº secreto (ej. no saber si es menor de X cota). Sirve igualmente para números negativos y puede generalizarse a cualquier métrica (ej. acotar el mapa del tesoro en un plano).

Desarrolle un programa que le permita romper el código de una cárcel ficticia.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import System.Random 
 
data JAIL = HIGHER | LOWED | OPEN 
 
-- Si se sabe la cota máxima del número secreto: 
jailBoundedCracker :: ℤ → ℤ → (ℤ → JAIL) → [ℤ] 
jailBoundedCracker a b e = case e c of 
                             LOWED  → c: jailBoundedCracker a (c - 1) e 
                             HIGHER → c: jailBoundedCracker (c + 1) b e 
                             OPEN   → [c] 
  where c = (a + b) ÷ 2 
 
-- Si se desconoce la cota máxima del número secreto: 
jailUnboundedCracker :: ℤ → (ℤ → JAIL) → [ℤ] 
jailUnboundedCracker b e = case e b of 
                             LOWED  → b: jailBoundedCracker 0 (b - 1) e 
                             HIGHER → b: jailUnboundedCracker (2 × b) e 
                             OPEN   → [b] 
 
-- Ya está. 
 
 
 
-- Simula el evaluador de "MTA: San Andreas" 
jailEvaluator :: ℤ → ℤ → JAIL 
jailEvaluator secretNumber taintNumber 
  | taintNumber < secretNumber = HIGHER 
  | taintNumber > secretNumber = LOWED 
  | taintNumber ≡ secretNumber = OPEN 
 
-- Simula el interface que hay en "MTA: San Andreas" 
jailInteractiveInterface :: IO (ℤ → JAIL) 
jailInteractiveInterface = do 
  putStrLn "Enter the secret number:\n" 
  jailEvaluator ↥ readLn 
 
-- Genera automáticamente simulaciones aleatorias: 
jailRandomGenerator :: ℤ → IO (ℤ → JAIL) 
jailRandomGenerator z = jailEvaluator ↥ randomRIO (0, 2ᶻ) 
 
 
{- 
 
-- El nº de intentos máximos para un número de `n` bits 
-- si no nos dicen la cota máxima es de `2n+1` intentos. 
 
> jailUnboundedCracker 1 <$> jailRandomGenerator 10 
[1,2,4,8,16,32,64,128,256,512,1024,511,767,639,575,607,591,583,587] 
 
> jailUnboundedCracker 1 <$> jailRandomGenerator 10 
[1,2,4,8,16,32,64,128,256,512,1024,511,767,639,575,543,559,567,571,573,574] 
 
> jailUnboundedCracker 1 <$> jailRandomGenerator 10 
[1,2,4,8,16,32,64,128,256,127,191,223,207,199,203,201] 
 
 
 
 
-- Si nos dicen la cota máxima para un número de `n` bits 
-- no necesitaremos más de `n` intentos. 
 
> jailBoundedCracker 0 (2^10-1) <$> jailRandomGenerator 10 
[511,255,127,191,223,207,199] 
 
> jailBoundedCracker 0 (2^10-1) <$> jailRandomGenerator 10 
[511,767,895,959,991,975,983,987] 
 
> jailBoundedCracker 0 (2^10-1) <$> jailRandomGenerator 10 
[511,255,127,63,95,79,71,75,77,78] 
 
 
 
 
> jailUnboundedCracker 1 <$> jailInteractiveInterface 
Enter the secret number: 
 
1234567890123456 
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536, 
131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432, 
67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296, 
8589934592,17179869184,34359738368,68719476736,137438953472,274877906944, 
549755813888,1099511627776,2199023255552,4398046511104,8796093022208, 
17592186044416,35184372088832,70368744177664,140737488355328,281474976710656, 
562949953421312,1125899906842624,2251799813685248,1125899906842623, 
1688849860263935,1407374883553279,1266637395197951,1196268651020287, 
1231453023109119,1249045209153535,1240249116131327,1235851069620223, 
1233652046364671,1234751557992447,1234201802178559,1234476680085503, 
1234614119038975,1234545399562239,1234579759300607,1234562579431423, 
1234571169366015,1234566874398719,1234569021882367,1234567948140543, 
1234567411269631,1234567679705087,1234567813922815,1234567881031679, 
1234567914586111,1234567897808895,1234567889420287,1234567893614591, 
1234567891517439,1234567890468863,1234567889944575,1234567890206719, 
1234567890075647,1234567890141183,1234567890108415,1234567890124799, 
1234567890116607,1234567890120703,1234567890122751,1234567890123775, 
1234567890123263,1234567890123519,1234567890123391,1234567890123455, 
1234567890123487,1234567890123471,1234567890123463,1234567890123459, 
1234567890123457,1234567890123456] 
 
 
-} 
3 comentarios
0votos

Escrito por KYKEX hace 6 meses

hola jose, en este caso el programa acierta automáticamente el código? es algo abstracto el aspecto de haskell o mejor dicho creo que yo soy muy novato, saludos.
1votos

Escrito por josejuan hace 6 meses

Hola @KYKEX, si, te dice el número por el que debes preguntar, supongo que te refieres a dónde está la entrada del resultado que "MTA: San Andreas" te dice cuando metes un número. Es la función `jailEvaluator` preparada para no tener que ir diciendo yo si es menor o mayor. Si realmente quieres usarla para el juego, por no modificar el desafío podrías escribir la siguiente no recomendada función:
run = s `seq` putStrLn ("\nSOLUTION: " ⧺ show s)
  where s = last $ jailUnboundedCracker 1 (λz → unsafePerformIO (putStr (" " ⧺ show z ⧺ " ") » readLn))

Así, supón que "MTA: San Andreas" ha seleccionado el número 34567 y nosotros no lo sabemos, entonces ejecutamos (las "h", "l" y "o" es lo que escribimos nosotros en el programa, el resto lo escribe la función `run`):
> run
 1 h
 2 h
 4 h
 8 h
 16 h
 32 h
 64 h
 128 h
 256 h
 512 h
 1024 h
 2048 h
 4096 h
 8192 h
 16384 h
 32768 h
 65536 l
 32767 h
 49151 l
 40959 l
 36863 l
 34815 l
 33791 h
 34303 h
 34559 h
 34687 l
 34623 l
 34591 l
 34575 l
 34567 o

SOLUTION: 34567
> 
0votos

Escrito por KYKEX hace 6 meses

gracias por la explicación, 1+

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.