{"id":8271,"date":"2023-08-29T06:00:10","date_gmt":"2023-08-29T04:00:10","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8271"},"modified":"2023-10-01T12:34:15","modified_gmt":"2023-10-01T10:34:15","slug":"29-ago-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/29-ago-23\/","title":{"rendered":"El problema del domin\u00f3 (con espacios de estados)"},"content":{"rendered":"

Las fichas del domin\u00f3 se pueden representar por pares de enteros. El problema del domin\u00f3 consiste en colocar todas las fichas de una lista dada de forma que el segundo n\u00famero de cada ficha coincida con el primero de la siguiente.<\/p>\n

Usando el procedimiento de b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n

\n   domino :: [(Int,Int)] -> [[(Int,Int)]]\n<\/pre>\n
tal que domino fs<\/code> es la lista de las soluciones del problema del domin\u00f3 correspondiente a las fichas fs<\/code>. Por ejemplo,<\/p>\n
\n   \u03bb> domino [(1,2),(2,3),(1,4)]\n   [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]\n   \u03bb> domino [(1,2),(1,1),(1,4)]\n   [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]\n   \u03bb> domino [(1,2),(3,4),(2,3)]\n   [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]]\n   \u03bb> domino [(1,2),(2,3),(5,4)]\n   []\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule El_problema_del_domino where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.List (delete)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Las fichas son pares de n\u00fameros enteros.\ntype Ficha  = (Int,Int)\n\n-- Un problema est\u00e1 definido por la lista de fichas que hay que colocar\ntype Problema = [Ficha]\n\n-- Los estados son los pares formados por la listas sin colocar y las\n-- colocadas.\ntype Estado = ([Ficha],[Ficha])\n\n-- (inicial p) es el estado inicial del problema p. Por ejemplo,\n--    \u03bb> inicial [(1,2),(2,3),(1,4)]\n--    ([(1,2),(2,3),(1,4)],[])\ninicial :: Problema -> Estado\ninicial p = (p,[])\n\n-- (esFinal e) se verifica si e es un estado final. Por ejemplo,\n--    \u03bb> esFinal ([], [(4,1),(1,2),(2,3)])\n--    True\n--    \u03bb> esFinal ([(2,3)], [(4,1),(1,2)])\n--    False\nesFinal :: Estado -> Bool\nesFinal = null . fst\n\n-- (sucesores e) es la lista de los sucesores del estado e. Por ejemplo,\n--    \u03bb> sucesores ([(1,2),(2,3),(1,4)],[])\n--    [([(2,3),(1,4)],[(1,2)]),\n--     ([(1,2),(1,4)],[(2,3)]),\n--     ([(1,2),(2,3)],[(1,4)]),\n--     ([(2,3),(1,4)],[(2,1)]),\n--     ([(1,2),(1,4)],[(3,2)]),\n--     ([(1,2),(2,3)],[(4,1)])]\n--    \u03bb> sucesores ([(2,3),(1,4)],[(1,2)])\n--    [([(2,3)],[(4,1),(1,2)])]\n--    \u03bb> sucesores ([(2,3),(1,4)],[(2,1)])\n--    [([(1,4)],[(3,2),(2,1)])]\nsucesores :: Estado -> [Estado]\nsucesores (fs,[]) =\n  [(delete (a,b) fs, [(a,b)]) | (a,b) <- fs, a \/= b] ++\n  [(delete (a,b) fs, [(b,a)]) | (a,b) <- fs]\nsucesores (fs,e@((x,_):_)) =\n  [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u \/= v, v == x] ++\n  [(delete (u,v) fs,(v,u):e) | (u,v) <- fs, u \/= v, u == x] ++\n  [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u == v, u == x]\n\n-- (soluciones p) es la lista de las soluciones del problema p. Por\n-- ejemplo,\n--    \u03bb> soluciones [(1,2),(2,3),(1,4)]\n--    [([],[(4,1),(1,2),(2,3)]),([],[(3,2),(2,1),(1,4)])]\nsoluciones :: Problema -> [Estado]\nsoluciones p = buscaProfundidad sucesores esFinal (inicial p)\n\ndomino :: Problema -> [[Ficha]]\ndomino p = map snd (soluciones p)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    domino [(1,2),(2,3),(1,4)] `shouldBe`\n    [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]\n  it \"e2\" $\n    domino [(1,2),(1,1),(1,4)] `shouldBe`\n    [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]\n  it \"e3\" $\n    domino [(1,2),(3,4),(2,3)] `shouldBe`\n    [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]]\n  it \"e4\" $\n    domino [(1,2),(2,3),(5,4)] `shouldBe`\n    []\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--    e4\n--\n--    Finished in 0.0013 seconds\n--    4 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\n# Las fichas son pares de n\u00fameros enteros.\nFicha  = tuple[int, int]\n\n# Un problema est\u00e1 definido por la lista de fichas que hay que colocar\nProblema = list[Ficha]\n\n# Los estados son los pares formados por la listas sin colocar y las\n# colocadas.\nEstado = tuple[list[Ficha], list[Ficha]]\n\n# inicial(p) es el estado inicial del problema p. Por ejemplo,\n#    >>> inicial([(1,2),(2,3),(1,4)])\n#    ([(1, 2), (2, 3), (1, 4)], [])\ndef inicial(p: Problema) -> Estado:\n    return (p, [])\n\n# esFinal(e) se verifica si e es un estado final. Por ejemplo,\n#    >>> esFinal(([], [(4,1),(1,2),(2,3)]))\n#    True\n#    >>> esFinal(([(2,3)], [(4,1),(1,2)]))\n#    False\ndef esFinal(e: Estado) -> bool:\n    return not e[0]\n\n# elimina(f, fs) es la lista obtenida eliminando la ficha f de la lista\n# fs. Por ejemplo,\n#    >>> elimina((1,2),[(4,1),(1,2),(2,3)])\n#    [(4, 1), (2, 3)]\ndef elimina(f: Ficha, fs: list[Ficha]) -> list[Ficha]:\n    return [g for g in fs if g != f]\n\n# sucesores(e) es la lista de los sucesores del estado e. Por ejemplo,\n#    >>> sucesores(([(1,2),(2,3),(1,4)],[]))\n#    [([(2,3),(1,4)],[(1,2)]),\n#     ([(1,2),(1,4)],[(2,3)]),\n#     ([(1,2),(2,3)],[(1,4)]),\n#     ([(2,3),(1,4)],[(2,1)]),\n#     ([(1,2),(1,4)],[(3,2)]),\n#     ([(1,2),(2,3)],[(4,1)])]\n#    >>> sucesores(([(2,3),(1,4)],[(1,2)]))\n#    [([(2,3)],[(4,1),(1,2)])]\n#    >>> sucesores(([(2,3),(1,4)],[(2,1)]))\n#    [([(1,4)],[(3,2),(2,1)])]\ndef sucesores(e: Estado) -> list[Estado]:\n    if not e[1]:\n        return [(elimina((a,b), e[0]), [(a,b)]) for (a,b) in e[0] if a != b] + \\\n               [(elimina((a,b), e[0]), [(b,a)]) for (a,b) in e[0]]\n    return [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u != v and v == e[1][0][0]] +\\\n           [(elimina((u,v),e[0]),[(v,u)]+e[1]) for (u,v) in e[0] if u != v and u == e[1][0][0]] +\\\n           [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u == v and u == e[1][0][0]]\n\n# soluciones(p) es la lista de las soluciones del problema p. Por\n# ejemplo,\n#    >>> soluciones([(1,2),(2,3),(1,4)])\n#    [([], [(3, 2), (2, 1), (1, 4)]), ([], [(4, 1), (1, 2), (2, 3)])]\ndef soluciones(p: Problema) -> list[Estado]:\n    return buscaProfundidad(sucesores, esFinal, inicial(p))\n\ndef domino(p: Problema) -> list[list[Ficha]]:\n    return [s[1] for s in soluciones(p)]\n\n# # Verificaci\u00f3n\n# # ============\n\ndef test_domino() -> None:\n    assert domino([(1,2),(2,3),(1,4)]) == \\\n        [[(3, 2), (2, 1), (1, 4)], [(4, 1), (1, 2), (2, 3)]]\n    assert domino([(1,2),(1,1),(1,4)]) == \\\n        [[(2, 1), (1, 1), (1, 4)], [(4, 1), (1, 1), (1, 2)]]\n    assert domino([(1,2),(3,4),(2,3)]) == \\\n        [[(4, 3), (3, 2), (2, 1)], [(1, 2), (2, 3), (3, 4)]]\n    assert domino([(1,2),(2,3),(5,4)]) == \\\n        []\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_domino()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Las fichas del domin\u00f3 se pueden representar por pares de enteros. El problema del domin\u00f3 consiste en colocar todas las fichas de una lista dada de forma que el segundo n\u00famero de cada ficha coincida con el primero de la siguiente. Usando el procedimiento de b\u00fasqueda en profundidad, definir la funci\u00f3n domino :: [(Int,Int)] ->…<\/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":[581],"tags":[456],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8271"}],"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=8271"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8271\/revisions"}],"predecessor-version":[{"id":8306,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8271\/revisions\/8306"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8271"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8271"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8271"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}