{"id":8269,"date":"2023-08-24T06:00:25","date_gmt":"2023-08-24T04:00:25","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8269"},"modified":"2023-08-09T13:40:27","modified_gmt":"2023-08-09T11:40:27","slug":"24-ago-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/24-ago-23\/","title":{"rendered":"El problema del calendario mediante b\u00fasqueda en espacio de estado"},"content":{"rendered":"<p>El problema del calendario, para una competici\u00f3n deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que:<\/p>\n<ul>\n<li>el campeonato dure n-1 d\u00edas,<\/li>\n<li>cada participante juegue exactamente un partido diario y<\/li>\n<li>cada participante juegue exactamente una vez con cada adversario.<\/li>\n<\/ul>\n<p>Por ejemplo, con 8 participantes una posible soluci\u00f3n es<\/p>\n<pre lang=\"text\">\n     | 1 2 3 4 5 6 7\n   --+--------------\n   1 | 2 3 4 5 6 7 8\n   2 | 1 4 3 6 5 8 7\n   3 | 4 1 2 7 8 5 6\n   4 | 3 2 1 8 7 6 5\n   5 | 6 7 8 1 2 3 4\n   6 | 5 8 7 2 1 4 3\n   7 | 8 5 6 3 4 1 2\n   8 | 7 6 5 4 3 2 1\n<\/pre>\n<p>donde las filas indican los jugadores y las columnas los d\u00edas; es decir, el elemento (i,j) indica el adversario del jugador i el d\u00eda j; por ejemplo, el adversario del jugador 2 el 4\u00aa d\u00eda es el jugador 6.<\/p>\n<p>Para representar el problema se define el tipo Calendario como matrices de enteros,<\/p>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3NPI4qV\">procedimiento de b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   calendario :: Int -> [Calendario]\n<\/pre>\n<p>tal que <code>calendario n<\/code> son las soluciones del problema del calendario, con n participantes, mediante el patr\u00f3n de b\u00fasqueda em profundidad. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> head (calendario 6)\n   \u250c           \u2510\n   \u2502 2 3 4 5 6 \u2502\n   \u2502 1 4 5 6 3 \u2502\n   \u2502 5 1 6 4 2 \u2502\n   \u2502 6 2 1 3 5 \u2502\n   \u2502 3 6 2 1 4 \u2502\n   \u2502 4 5 3 2 1 \u2502\n   \u2514           \u2518\n\n   \u03bb> length (calendario 6)\n   720\n   \u03bb> length (calendario 5)\n   0\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule El_problema_del_calendario_mediante_busqueda_en_espacio_de_estado where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.Matrix (Matrix, (!), nrows, zero, setElem, toLists)\nimport Data.List ((\\\\))\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ntype Calendario = Matrix Int\n\n-- (inicial n) es el estado inicial para el problema del calendario con\n-- n participantes; es decir, una matriz de n fila y n-1 columnas con\n-- todos sus elementos iguales a 0. Por ejemplo,\n--    \u03bb> inicial 4\n--    \u250c       \u2510\n--    \u2502 0 0 0 \u2502\n--    \u2502 0 0 0 \u2502\n--    \u2502 0 0 0 \u2502\n--    \u2502 0 0 0 \u2502\n--    \u2514       \u2518\ninicial :: Int -> Calendario\ninicial n = zero n (n-1)\n\n-- (huecos c) es la lista de las posiciones de c cuyo valor es 0.\nhuecos :: Calendario -> [(Int, Int)]\nhuecos c = [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0]\n  where n = nrows c\n\n-- (sucesores c) es la lista de calendarios obtenidos poniendo en el\n-- lugar del primer elemento nulo de c uno de los posibles jugadores de\n-- forma que se cumplan las condiciones del problema. Por ejemplo,\n--    \u03bb> sucesores (inicial 4)\n--    [\u250c       \u2510  \u250c       \u2510  \u250c       \u2510\n--     \u2502 2 0 0 \u2502  \u2502 3 0 0 \u2502  \u2502 4 0 0 \u2502\n--     \u2502 1 0 0 \u2502  \u2502 0 0 0 \u2502  \u2502 0 0 0 \u2502\n--     \u2502 0 0 0 \u2502  \u2502 1 0 0 \u2502  \u2502 0 0 0 \u2502\n--     \u2502 0 0 0 \u2502  \u2502 0 0 0 \u2502  \u2502 1 0 0 \u2502\n--     \u2514       \u2518, \u2514       \u2518, \u2514       \u2518]\n--    \u03bb> sucesores (fromLists [[2,3,0],[1,0,0],[0,1,0],[0,0,0]])\n--    [\u250c       \u2510\n--     \u2502 2 3 4 \u2502\n--     \u2502 1 0 0 \u2502\n--     \u2502 0 1 0 \u2502\n--     \u2502 0 0 1 \u2502\n--     \u2514       \u2518]\n--    \u03bb> sucesores (fromLists [[2,3,4],[1,0,0],[0,1,0],[0,0,1]])\n--    [\u250c       \u2510\n--     \u2502 2 3 4 \u2502\n--     \u2502 1 4 0 \u2502\n--     \u2502 0 1 0 \u2502\n--     \u2502 0 2 1 \u2502\n--     \u2514       \u2518]\nsucesores :: Calendario -> [Calendario]\nsucesores c =\n  [setElem i (k,j) (setElem k (i,j) c) |\n   k <- [1..n] \\\\ (i : [c!(k,j) | k <- [1..i-1]] ++\n                       [c!(i,k) | k <- [1..j-1]]),\n   c!(k,j) == 0]\n  where\n    n = nrows c\n    (i,j) = head (huecos c)\n\n-- (esFinal c) se verifica si c un estado final para el problema\n-- del calendario con n participantes; es decir, no queda en c ning\u00fan\n-- elemento igual a 0. Por ejemplo,\n--    \u03bb> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]])\n--    True\n--    \u03bb> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]])\n--    False\nesFinal :: Calendario -> Bool\nesFinal c = null (huecos c)\n\ncalendario :: Int -> [Calendario]\ncalendario n = buscaProfundidad sucesores esFinal (inicial n)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    toLists (head (calendario 6)) `shouldBe`\n    [[2,3,4,5,6],[1,4,5,6,3],[5,1,6,4,2],[6,2,1,3,5],[3,6,2,1,4],[4,5,3,2,1]]\n  it \"e2\" $\n    length (calendario 6) `shouldBe` 720\n  it \"e3\" $\n    length (calendario 5) `shouldBe` 0\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.2580 seconds\n--    3 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import Optional\n\nimport numpy as np\nimport numpy.typing as npt\n\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\nCalendario = npt.NDArray[np.complex64]\n\n# inicial(n) es el estado inicial para el problema del calendario con\n# n participantes; es decir, una matriz de n fila y n-1 columnas con\n# todos sus elementos iguales a 0. Por ejemplo,\n#    >>> inicial(4)\n#    array([[0, 0, 0],\n#           [0, 0, 0],\n#           [0, 0, 0],\n#           [0, 0, 0]])\ndef inicial(n: int) -> Calendario:\n    return np.zeros((n, n - 1), dtype=int)\n\n# primerHueco(c) es la posici\u00f3n del primer elemento cuyo valor es 0. Si\n# todos los valores son distintos de 0, devuelve (-1,-1). Por ejemplo,\n#    primerHueco(np.array([[1,2,3],[4,5,0],[7,0,0]])) == (1, 2)\n#    primerHueco(np.array([[1,2,3],[4,5,6],[7,8,0]])) == (2, 2)\n#    primerHueco(np.array([[1,2,3],[4,5,6],[7,8,9]])) == (-1, -1)\ndef primerHueco(c: Calendario) -> tuple[int, int]:\n    (n, m) = c.shape\n    for i in range(0, n):\n        for j in range(0, m):\n            if c[i,j] == 0:\n                return (i, j)\n    return (-1, -1)\n\n# libres(c, i, j) es la lista de valores que que pueden poner en la\n# posici\u00f3n (i,j) del calendario c. Por ejemplo,\n#    libres(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]),0,0) == [2, 3, 4]\n#    libres(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]),0,1) == [3, 4]\n#    libres(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]),0,2) == [4]\n#    libres(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]),1,1) == [4]\n#    libres(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]),1,2) == [3]\ndef libres(c: Calendario, i: int, j: int) -> list[int]:\n    n = c.shape[0]\n    return list(set(range(1, n + 1))\n                - {i + 1}\n                - set(c[i])\n                - set(c[:,j]))\n\n# setElem(k, i, j, c) es el calendario obtenido colocando en c el valor\n# k en la posici\u00f3n (i,j).\n#    >>> setElem(7,1,2,np.array([[1,2,3],[4,5,0],[0,0,0]]))\n#    array([[1, 2, 3],\n#           [4, 5, 7],\n#           [0, 0, 0]])\ndef setElem(k: int, i: int, j: int, c: Calendario) -> Calendario:\n    _c = deepcopy(c)\n    _c[i, j] = k\n    return _c\n\n# sucesores(c) es la lista de calendarios obtenidos poniendo en el\n# lugar del primer elemento nulo de c uno de los posibles jugadores de\n# forma que se cumplan las condiciones del problema. Por ejemplo,\n#    >>> sucesores(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]))\n#    [array([[2,0,0], [1,0,0], [0,0,0], [0,0,0]]),\n#     array([[3,0,0], [0,0,0], [1,0,0], [0,0,0]]),\n#     array([[4,0,0], [0,0,0], [0,0,0], [1,0,0]])]\n#    >>> sucesores(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]))\n#    [array([[2,3,0], [1,0,0], [0,1,0], [0,0,0]]),\n#     array([[2,4,0], [1,0,0], [0,0,0], [0,1,0]])]\n#    >>> sucesores(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]))\n#    [array([[2,3,4], [1,0,0], [0,1,0], [0,0,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]))\n#    [array([[2,3,4], [1,4,0], [0,1,0], [0,2,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]))\n#    [array([[2,3,4], [1,4,3], [0,1,2], [0,2,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,4,3],[0,1,2],[0,2,1]]))\n#    [array([[2,3,4], [1,4,3], [4,1,2], [3,2,1]])]\n#    >>> sucesores(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]]))\n#    []\ndef sucesores(c: Calendario) -> list[Calendario]:\n    n = c.shape[0]\n    (i, j) = primerHueco(c)\n    return [setElem(i+1, k-1, j, setElem(k, i, j, c))\n            for k in libres(c, i, j)]\n\n# esFinal(c) se verifica si c un estado final para el problema\n# del calendario con n participantes; es decir, no queda en c ning\u00fan\n# elemento igual a 0. Por ejemplo,\n#    >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]]))\n#    True\n#    >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,0]]))\n#    False\ndef esFinal(c: Calendario) -> bool:\n    return primerHueco(c) == (-1, -1)\n\ndef calendario(n: int) -> list[Calendario]:\n    return buscaProfundidad(sucesores, esFinal, inicial(n))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_calendario() -> None:\n    def filas(p: Calendario) -> list[list[int]]:\n        return p.tolist()\n\n    assert filas(calendario(6)[0]) == \\\n        [[6, 5, 4, 3, 2],\n         [5, 4, 3, 6, 1],\n         [4, 6, 2, 1, 5],\n         [3, 2, 1, 5, 6],\n         [2, 1, 6, 4, 3],\n         [1, 3, 5, 2, 4]]\n    assert len(calendario(6)) == 720\n    assert len(calendario(5)) == 0\n    print(\"Verificado\")\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El problema del calendario, para una competici\u00f3n deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que: el campeonato dure n-1 d\u00edas, cada participante juegue exactamente un partido diario y cada participante juegue exactamente una vez con cada adversario. Por ejemplo, con 8 participantes una posible soluci\u00f3n es |&#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":[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\/8269"}],"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=8269"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8269\/revisions"}],"predecessor-version":[{"id":8270,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8269\/revisions\/8270"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8269"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8269"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8269"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}