Ir al contenido principal

TAD de las colas - Intercalado de dos colas

Utilizando el tipo abstracto de datos de las colas, definir las funciones

   intercalaColas :: Cola a -> Cola a -> Cola a

tal que intercalaColas c1 c2 es la cola formada por los elementos de c1 y c2 colocados en una cola, de forma alternativa, empezando por los elementos de c1. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacia)
   λ> ej2 = inserta 0 (inserta 7 (inserta 4 (inserta 9 vacia)))
   λ> intercalaColas ej1 ej2
   5 | 9 | 3 | 4 | 7 | 0
   λ> intercalaColas ej2 ej1
   9 | 5 | 4 | 3 | 7 | 0

Soluciones

Se usarán las funciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)
import Transformaciones_colas_listas (colaAlista, listaAcola)
import ExtiendeCola (extiendeCola)
import Test.QuickCheck

-- 1ª solución
-- ===========

intercalaColas :: Cola a -> Cola a -> Cola a
intercalaColas c1 c2
  | esVacia c1 = c2
  | esVacia c2 = c1
  | otherwise  = extiendeCola (inserta pc2 (inserta pc1 vacia))
                              (intercalaColas rc1 rc2)
  where pc1 = primero c1
        rc1 = resto c1
        pc2 = primero c2
        rc2 = resto c2

-- 2ª solución
-- ===========

intercalaColas2 :: Cola a -> Cola a -> Cola a
intercalaColas2 c1 c2 = aux c1 c2 vacia
  where
    aux d1 d2 c
      | esVacia d1 = extiendeCola c d2
      | esVacia d2 = extiendeCola c d1
      | otherwise  = aux rd1 rd2 (inserta pd2 (inserta pd1 c))
      where pd1 = primero d1
            rd1 = resto d1
            pd2 = primero d2
            rd2 = resto d2

-- 3ª solución
-- ===========

intercalaColas3 :: Cola a -> Cola a -> Cola a
intercalaColas3 c1 c2 =
  listaAcola (intercalaListas (colaAlista c1) (colaAlista c2))

-- (intercalaListas xs ys) es la lista obtenida intercalando los
-- elementos de xs e ys. Por ejemplo,
intercalaListas :: [a] -> [a] -> [a]
intercalaListas []     ys     = ys
intercalaListas xs     []     = xs
intercalaListas (x:xs) (y:ys) = x : y : intercalaListas xs ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_intercalaColas :: Cola Int -> Cola Int -> Bool
prop_intercalaColas c1 c2 =
  all (== intercalaColas c1 c2)
      [intercalaColas2 c1 c2,
       intercalaColas2 c1 c2]

-- La comprobación es
--    λ> quickCheck prop_intercalaColas
--    +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.extiendeCola import extiendeCola
from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista, listaAcola

A = TypeVar('A')

# 1ª solución
# ===========

def intercalaColas(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    if esVacia(c1):
        return c2
    if esVacia(c2):
        return c1
    pc1 = primero(c1)
    rc1 = resto(c1)
    pc2 = primero(c2)
    rc2 = resto(c2)
    return extiendeCola(inserta(pc2, inserta(pc1, vacia())),
                        intercalaColas(rc1, rc2))

# 2ª solución
# ===========

def intercalaColas2(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    def aux(d1: Cola[A], d2: Cola[A], d3: Cola[A]) -> Cola[A]:
        if esVacia(d1):
            return extiendeCola(d3, d2)
        if esVacia(d2):
            return extiendeCola(d3, d1)
        pd1 = primero(d1)
        rd1 = resto(d1)
        pd2 = primero(d2)
        rd2 = resto(d2)
        return aux(rd1, rd2, inserta(pd2, inserta(pd1, d3)))

    return aux(c1, c2, vacia())

# 3ª solución
# ===========

# intercalaListas(xs, ys) es la lista obtenida intercalando los
# elementos de xs e ys. Por ejemplo,
def intercalaListas(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return ys
    if not ys:
        return xs
    return [xs[0], ys[0]] + intercalaListas(xs[1:], ys[1:])

def intercalaColas3(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    return listaAcola(intercalaListas(colaAlista(c1), colaAlista(c2)))

# 4ª solución
# ===========

def intercalaColas4Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    if c1.esVacia():
        return c2
    if c2.esVacia():
        return c1
    pc1 = c1.primero()
    c1.resto()
    pc2 = c2.primero()
    c2.resto()
    return extiendeCola(inserta(pc2, inserta(pc1, vacia())),
                        intercalaColas4Aux(c1, c2))

def intercalaColas4(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return intercalaColas4Aux(_c1, _c2)

# 5ª solución
# ===========

def intercalaColas5Aux(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    r: Cola[A] = vacia()
    while not esVacia(c1) and not esVacia(c2):
        pc1 = primero(c1)
        c1.resto()
        pc2 = primero(c2)
        c2.resto()
        r = inserta(pc2, inserta(pc1, r))
    if esVacia(c1):
        return extiendeCola(r, c2)
    return extiendeCola(r, c1)

def intercalaColas5(c1: Cola[A], c2: Cola[A]) -> Cola[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return intercalaColas5Aux(_c1, _c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_extiendeCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = intercalaColas(c1, c2)
    assert intercalaColas2(c1, c2) == r
    assert intercalaColas3(c1, c2) == r
    assert intercalaColas4(c1, c2) == r
    assert intercalaColas5(c1, c2) == r

# La comprobación es
#    src> poetry run pytest -q intercalaColas.py
#    1 passed in 0.47s