0votos

Wythoff's Game en Haskell

por josejuan hace 1 año

Se calcula de dos formas, una con coste tirando a lineal (revisando todas las posibilidades y usando memoización) y la otra con coste tirando a constante (el uso de constructible no creo sea constante). En todo caso es curioso que la sucesión de posiciones de pérdida contengan estrictamente todos los números naturales.

Decidir si una posición determinada de un juego de Wythoff es o no Ganadora!!!

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
import Data.Function.Memoize 
import Data.Maybe 
import Data.Real.Constructible 
import qualified Data.Map as M 
import Data.List (nub) 
 
-- Revisando todas las posibilidades (por recursión y memoización) 
partida :: (Int, Int) ->Bool 
partida = rec True 
  where rec = memoize2 rec' 
        rec' p (0, 0) = not p 
        rec' p (x, y) = let rs = map (rec (not p)) $ [(x - i, y    ) | i <-[1..    x  ]] 
                                                ++ [(x    , y - i) | i <-[1..      y]] 
                                                ++ [(x - i, y - i) | i <-[1..min x y]] 
                        in  if any (p ==) rs then p else not p 
 
-- Coste O(1) calculando directamente si pertenece a una posición de pérdida 
partida' :: (Int, Int) ->Bool 
partida' (a, b) | a == 0     = b /= 0 
                | a > b     = partida' (b, a) 
                | otherwise = maybe True (\k ->(a, b) /= (floor $ k * g, floor $ k * g * g)) h 
                              where z = fromIntegral (floor (fromIntegral a / g)) 
                                    h = listToMaybe $ filter (\k ->a == floor (k * g)) [z, z + 1] 
 
-- Aureo 
g :: Construct 
g = (1 + sqrt 5) / 2 
 
 
-- Es curioso que las posiciones de pérdida contengan estrictamente todos 
-- los naturales 
posiciones_malas :: [(Int, Int)] 
posiciones_malas = concat [[(x, y) | x <-[1..y], partida' (x, y) == False] | y <-[1..]] 
 
{- 
 
> mapM_ print posiciones_malas 
(1,2) 
(3,5) 
(4,7) 
(6,10) 
(8,13) 
(9,15) 
(11,18) 
(12,20) 
(14,23) 
(16,26) 
(17,28) 
(19,31) 
(21,34) 
(22,36) 
(24,39) 
(25,41) 
(27,44) 
(29,47) 
(30,49) 
(32,52) 
... 
 
-} 
12 comentarios
0votos

Escrito por AverageUser hace 1 año

Buena solución, aun que existe una forma más económica, que es de echo eficiente (no como la recursiva). La dejare como solución pronto
0votos

Escrito por josejuan hace 1 año

¿Más eficiente que "Coste O(1) calculando directamente si pertenece a una posición de pérdida"?

"Se calcula de dos formas, ..."
0votos

Escrito por AverageUser hace 1 año

Disculpa, no había visto la segunda solución. Pero no veo como puede ser constante debido a que la codificación de un numero es logarítmica. Por lo cual tu algoritmo no podría depender del largo de los números de cierta posición por lo cual ... debería depender de alguna otra cosa, y como las posiciones están dadas por 2 números ... en fin no entiendo
0votos

Escrito por AverageUser hace 1 año

de echo estuve haciendo tests, y mi solución es más rápida para números grandes y se que la mía no es constante
0votos

Escrito por AverageUser hace 1 año

main = getArgs >>= print . last . (\x -> take x posiciones_malas) . read . head

añadí esto a la tuya y a la mía y lo compile. (ghc -O)
y esto resulto: (a la tuya le puse 2wythoff.hs

computador:~/Dropbox/Haskell$ time ./2wythoff 150
(242,392)

real	0m6.348s
user	0m6.308s
sys	0m0.028s

-----------------------------------------------------
computador:~/Dropbox/Haskell$ time ./wythoff 150
(242,392)

real	0m0.005s
user	0m0.000s
sys	0m0.000s
0votos

Escrito por josejuan hace 1 año

Eso no tiene nada que ver, ambas soluciones son consideradas con coste O(1), obviamente en ambos casos, una vez que la representación de número no cabe en la máquina, las operaciones ya no tienen coste O(1), por ejemplo tu multiplicación para enteros grandes usará Karatsuba que tiene coste ~O(n^1.5) y mi reducción a constructible supongo le pasará algo similar.

En todo caso +1 por tu solución, mucho más elegante.
0votos

Escrito por AverageUser hace 1 año

pero por ejemplo generar las primeras 100 demora 2 segundos y las primeras 200 10 segundos, y no son numeros de màs de 3 digitos. Nose aun creo que es O(log n)
0votos

Escrito por AverageUser hace 1 año

Pero entiendo que en la practica es casi como constante. Pero teoricamente hablando no diria O(1) . Bueno supongo que es cuestion de ponerse de acuerdo nomas
0votos

Escrito por josejuan hace 1 año

AverageUser, ten en cuenta que `posiciones_malas` no hace ninguna asunción sobre la distribución de las posiciones malas, y está revisando (n + 1) * n / 2 parejas donde además una proporción cada vez más pequeña son posiciones perdedoras, en concreto, tomando los primeros 1000, los primeros 2000, ... tenemos:
57.8235294117647
82.33333333333333
102.44827586206897
116.6470588235294
130.57894736842104
141.85714285714286
154.55555555555554
165.66666666666666

Veces más de posiciones ganadoras que perdedoras, así, el cálculo de si una posición es ganadora o perdedora sigue siendo O(1), pero no la búsqueda que haces para compararlo.

Es decir, cuando pides las primeras n posiciones perdedoras, debe calcular muchísimas más resultados de posición, lógicamente puede enumerarse, pero `posiciones_malas` precisamente hace uso de la función solicitada en el desafío.

Por ejemplo, para sacar las primeras 100 posiciones perdedoras, hacen falta revisar 34.091 pares con la función `posiciones_malas` y para las primeras 200 hacen falta revisar 136.826, es decir, si hacemos 136.826 / 34.091 = 4 que no se alejará mucho si en lugar de redondear los tiempos (pillín) haces la proporción con los tiempos exactos.

Tirando a lineal, vamos ;)

Voy a calcularlo por curiosidad:
> :l ../palillos.hs 
[1 of 1] Compiling Main             ( ../palillos.hs, interpreted )
Ok, modules loaded: Main.
(0.06 secs,)
> let malas = filter (not . snd) posiciones_malas
(0.01 secs, 706,728 bytes)
> last $ take 200 malas
((323,523),False)
(11.64 secs, 5,500,329,224 bytes)
> :l ../palillos.hs 
[1 of 1] Compiling Main             ( ../palillos.hs, interpreted )
Ok, modules loaded: Main.
(0.06 secs,)
> let malas = filter (not . snd) posiciones_malas
(0.01 secs, 710,040 bytes)
> last $ take 100 malas
((161,261),False)
(2.65 secs, 1,226,033,432 bytes)
> 

Eso hacen 11.64 / 2.65 = 4.39 ¿bastante cerca del valor teórico calculado no? (de hecho mejor!)
0votos

Escrito por josejuan hace 1 año

Realmente he cambiado la definición de `posiciones_malas` para que no ha el filtrado (por eso ves el `filter (not . snd)`:
posiciones_malas :: [((Int, Int), Bool)]
posiciones_malas = concat [[((x, y), partida' (x, y)) | x <-[1..y]] | y <-[1..]]
0votos

Escrito por josejuan hace 1 año

(perdón por tanto spam, no es mejor, excede 390 milisegundos, pero vamos, está bien ajustado al valor esperado)
0votos

Escrito por AverageUser hace 1 año

Jaja, yo también hice harto spam. Y estoy de acuerdo contigo (mi error lo de los tests), pero sigue sin ser estrictamente O(1) :). aun que gracias por la aclaración.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.