Ir al contenido principal

Caminos en un triángulo

Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo

      3
     7 4
    2 4 6
   8 5 9 3

se representa por

   [[3],[7,4],[2,4,6],[8,5,9,3]]

Definir la función

   caminos :: [[a]] -> [[a]]

tal que (caminos xss) es la lista de los caminos en el triángulo, donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,

   λ> caminos [[3],[7,4]]
   [[3,7],[3,4]]
   λ> caminos [[3],[7,4],[2,4,6]]
   [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
   λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]]
   [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],
    [3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]

1. Soluciones en Haskell

module Caminos_en_un_triangulo where

import Test.Hspec (Spec, hspec, it, shouldBe)

caminos :: [[a]] -> [[a]]
caminos []    = [[]]
caminos [[x]] = [[x]]
caminos ([x]:[y1,y2]:zs) =
  [x:y1:us | (_:us) <- caminos ([y1] : map init zs)] ++
  [x:y2:vs | (_:vs) <- caminos ([y2] : map tail zs)]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    caminos [[3],[7,4]] `shouldBe`
    [[3,7],[3,4]]
  it "e2" $
    caminos [[3],[7,4],[2,4,6]] `shouldBe`
    [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
  it "e3" $
    caminos [[3],[7,4],[2,4,6],[8,5,9,3]] `shouldBe`
    [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],
     [3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]

-- La verificación es
--    λ> verifica
--
--    3 examples, 0 failures

2. Soluciones en Python

from typing import TypeVar

A = TypeVar('A')

def caminos(xss: list[list[A]]) -> list[list[A]]:
    if not xss:
        return [[]]
    if len(xss) == 1:
        return xss
    x = xss[0][0]
    y1 = xss[1][0]
    y2 = xss[1][1]
    zss = xss[2:]
    return [[x, y1] + us
            for _, *us in caminos([[y1]] + [zs[:-1] for zs in zss])] + \
           [[x, y2] + us
            for _, *us in caminos([[y2]] + [zs[1:] for zs in zss])]

# Verificación
# ============

def test_caminos() -> None:
    assert caminos([[3],[7,4]]) == \
        [[3,7],[3,4]]
    assert caminos([[3],[7,4],[2,4,6]]) == \
        [[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
    assert caminos([[3],[7,4],[2,4,6],[8,5,9,3]]) == \
        [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],
         [3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]
    print("Verificado")

# La verificación es
#    >>> test_caminos()
#    Verificado