{"id":1501,"date":"2015-06-01T06:00:27","date_gmt":"2015-06-01T04:00:27","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1501"},"modified":"2015-06-13T16:20:51","modified_gmt":"2015-06-13T14:20:51","slug":"problema-de-las-bolas-de-dikjstra","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/problema-de-las-bolas-de-dikjstra\/","title":{"rendered":"Problema de las bolas de Dijkstra"},"content":{"rendered":"<p>En el juego de las bolas de Dijkstra se dispone de una bolsa con bolas blancas y negras. El juego consiste en elegir al azar dos bolas de la bolsa y a\u00f1adir una bola negra si las dos bolas elegidas son del mismo color o una bola blanca en caso contrario. El juego termina cuando queda s\u00f3lo una bola en la bolsa.<\/p>\n<p>Vamos a representar las bolas blancas por 0, las negras por 1 y la bolsa la representaremos por una lista cuyos elementos son 0 \u00f3 1.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   juego  :: [Int] -> [[Int]]\n   ultima :: [Int] -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(juego xs) es la lista de los pasos aleatorios de un juego de Dijkstra a partir de la lista xs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]\n     juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]\n     juego [1,0,0,0,1]  ==  [[1,0,0,0,1],[0,0,0,1],[0,1,1],[1,0],[0]]\n     juego [1,0,1,1,1]  ==  [[1,0,1,1,1],[1,1,0,1],[1,0,1],[0,1],[0]]\n<\/pre>\n<ul>\n<li>(ultima xs) es la bola que queda en la bolsa al final del juego de Dijkstra a partir de xs. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     ultima [1,1,0,0,1]  ==  1\n     ultima [1,0,0,0,1]  ==  0\n     ultima [1,0,1,1,1]  ==  0\n<\/pre>\n<p>Comprobar con QuickCheck que la bola que queda en la bolsa al final del juego de Dijkstra es blanca si, y s\u00f3lo si, el n\u00famero de bolas blancas en la bolsa inicial es impar.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport System.IO.Unsafe\nimport System.Random\nimport Test.QuickCheck\n\n-- (aleatorio a b) es un n\u00famero aleatorio entre a y b. Por ejemplo, \n--    ghci> aleatorio 0 1000\n--    681\n--    ghci> aleatorio 0 1000\n--    66\naleatorio :: Random t => t -> t -> t\naleatorio a b = unsafePerformIO $ \n                getStdRandom (randomR (a,b))\n\n-- (aleatorios m n) es una lista infinita de n\u00fameros aleatorios entre m y\n-- n. Por ejemplo, \n--    ghci> take 20 (aleatorios 2 9)\n--    [6,5,3,9,6,3,6,6,2,7,9,6,8,6,2,4,2,6,9,4]\n--    ghci> take 20 (aleatorios 2 9)\n--    [3,7,7,5,7,7,5,8,6,4,7,2,8,8,2,8,7,6,5,5]\naleatorios :: Random t => t -> t -> [t]\naleatorios m n = aleatorio m n : aleatorios m n\n\n-- (selecciona n x) es el par formado por el n-\u00e9simo elemento de xs y\n-- los restantes elementos. Por ejemplo,\n--    selecciona 0 \"abc\"  ==  ('a',\"bc\")\n--    selecciona 1 \"abc\"  ==  ('b',\"ac\")\n--    selecciona 2 \"abc\"  ==  ('c',\"ab\")\nselecciona :: Int -> [a] -> (a,[a])\nselecciona n xs = (z,ys++zs)\n    where (ys,z:zs) = splitAt n xs\n\n-- (extraeAleatorio xs) es el par formado aleatoriamente por un elemento\n-- de xs y las restantes. Por ejemplo, \n--    extraeAleatorio [1,0,0,1,1]  ==  (0,[1,0,1,1])\n--    extraeAleatorio [1,0,0,1,1]  ==  (1,[0,0,1,1])\n--    extraeAleatorio [1,0,0,1,1]  ==  (0,[1,0,1,1])\n--    extraeAleatorio [1,0,0,1,1]  ==  (1,[1,0,0,1])\nextraeAleatorio :: [a] -> (a,[a])\nextraeAleatorio xs = selecciona n xs\n    where n = aleatorio 0 (length xs - 1)\n\n-- (inserta n x xs) inserta, en la posici\u00f3n n, el elemento x en la lista\n-- xs. Por ejemplo,  \n--    inserta 0 'a' \"bcd\"  ==  \"abcd\"\n--    inserta 1 'a' \"bcd\"  ==  \"bacd\"\n--    inserta 2 'a' \"bcd\"  ==  \"bcad\"\n--    inserta 3 'a' \"bcd\"  ==  \"bcda\"\ninserta :: Int -> a -> [a] -> [a]\ninserta n x xs = us ++ (x:vs)\n    where (us,vs) = splitAt n xs\n\n-- (insertaAleatorio x xs) inserta aleatoriamente el elemento x en la\n-- lista xs. Por ejemplo,\n--    insertaAleatorio 9 [0..8]  ==  [0,1,2,3,4,9,5,6,7,8]\n--    insertaAleatorio 9 [0..8]  ==  [0,1,9,2,3,4,5,6,7,8]\n--    insertaAleatorio 9 [0..8]  ==  [0,1,2,3,4,5,6,9,7,8]\ninsertaAleatorio :: a -> [a] -> [a]\ninsertaAleatorio x xs = inserta n x xs\n    where n = aleatorio 0 (length xs - 1)\n\n-- (paso xs) elige aleatoriamente dos bolas de xs e inserta\n-- aleatoriamente una bola negra si las dos extra\u00eddas son del mismo\n-- color o una blanca, en caso contrario. Por ejemplo, \n--    paso [1,0,1,1,0,0,1,1,1,0,0,0]  ==  [0,1,1,0,0,1,1,0,1,0,0]\n--    paso [1,0,1,1,0,0,1,1,1,0,0,0]  ==  [1,0,0,0,1,1,1,0,0,1,0]\npaso :: [Int] -> [Int]\npaso [x] = []\npaso xs | x == y    = insertaAleatorio 1 zs\n        | otherwise = insertaAleatorio 0 zs \n    where (x,ys) = extraeAleatorio xs\n          (y,zs) = extraeAleatorio ys\n\n-- (juego xs) es la lista de los pasos aleatorios de un juego a partir\n-- de la lista xs. Por ejemplo,\n--    juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]\n--    juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]\n--    juego [1,1,0,0,0]  ==  [[1,1,0,0,0],[0,1,0,0],[1,1,0],[0,1],[0]]\njuego :: [Int] -> [[Int]]\njuego xs = takeWhile (not . null) (iterate paso xs)\n\n-- (ultima xs) es la bola que queda en la bolsa al final del juego de\n-- Dijkstra. Por ejemplo, \n--    ultima [1,0,0,1]  ==  1\nultima :: [Int] -> Int\nultima = head . last . juego\n\n-- (numeroDeCeros xs) es el n\u00famero de ceros en xs. Por ejemplo,\n--    numeroDeCeros [1,0,0,1,0]  ==  3\nnumeroDeCeros :: [Int] -> Int\nnumeroDeCeros xs = length (filter (==0) xs)\n\n-- Propiedad. La bola que queda en la bolsa al final del juego de\n-- Dijkstra es blanca si, y s\u00f3lo si, el n\u00famero de bolas blancas en la\n-- bolsa inicial es impar. \nprop_Dijkstra :: [Int] -> Property\nprop_Dijkstra xs = \n    not (null xs) ==> (ultima ys == 0) == odd (numeroDeCeros ys)\n    where ys = [x `mod` 2 | x <- xs]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_Dijkstra\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En el juego de las bolas de Dijkstra se dispone de una bolsa con bolas blancas y negras. El juego consiste en elegir al azar dos bolas de la bolsa y a\u00f1adir una bola negra si las dos bolas elegidas son del mismo color o una bola blanca en caso contrario. El juego termina cuando&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1501"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=1501"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1501\/revisions"}],"predecessor-version":[{"id":1558,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1501\/revisions\/1558"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1501"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1501"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1501"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}