La bandera tricolor

José A. Alonso

03-02-2025

El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.

Definir el tipo de dato Color para representar los colores con los constructores R, A y M correspondientes al rojo, azul y morado y la función

banderaTricolor :: [Color] -> [Color]

tal que (banderaTricolor xs) es la bandera tricolor formada con los elementos de xs. Por ejemplo,

banderaTricolor [M,R,A,A,R,R,A,M,M]  ==  [R,R,R,A,A,A,M,M,M]
banderaTricolor [M,R,A,R,R,A]        ==  [R,R,R,A,A,M]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Soluciones

A continuación se muestran

las soluciones en Haskell,
las soluciones en Python y
las soluciones en Common Lisp

1. Soluciones en Haskell

import Data.List (sort)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

data Color = R | A | M
  deriving (Show, Eq, Ord, Enum)

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

banderaTricolor1 :: [Color] -> [Color]
banderaTricolor1 xs =
  [x | x <- xs, x == R] ++
  [x | x <- xs, x == A] ++
  [x | x <- xs, x == M]

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

banderaTricolor2 :: [Color] -> [Color]
banderaTricolor2 xs =
  colores R ++ colores A ++ colores M
  where colores c = filter (== c) xs

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

banderaTricolor3 :: [Color] -> [Color]
banderaTricolor3 xs =
  concat [[x | x <- xs, x == c] | c <- [R,A,M]]

-- 4ª solución
-- ===========

banderaTricolor4 :: [Color] -> [Color]
banderaTricolor4 xs = aux xs ([],[],[])
  where aux []     (rs,as,ms) = rs ++ as ++ ms
        aux (R:ys) (rs,as,ms) = aux ys (R:rs,   as,   ms)
        aux (A:ys) (rs,as,ms) = aux ys (  rs, A:as,   ms)
        aux (M:ys) (rs,as,ms) = aux ys (  rs,   as, M:ms)

-- 5ª solución
-- ===========

banderaTricolor5 :: [Color] -> [Color]
banderaTricolor5 = sort

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

verifica :: IO ()
verifica = hspec spec

specG :: ([Color] -> [Color]) -> Spec
specG banderaTricolor = do
  it "e1" $
    banderaTricolor [M,R,A,A,R,R,A,M,M]  `shouldBe`  [R,R,R,A,A,A,M,M,M]
  it "e2" $
    banderaTricolor [M,R,A,R,R,A]        `shouldBe`  [R,R,R,A,A,M]

spec :: Spec
spec = do
  describe "def. 1" $ specG banderaTricolor1
  describe "def. 2" $ specG banderaTricolor2
  describe "def. 3" $ specG banderaTricolor3
  describe "def. 4" $ specG banderaTricolor4
  describe "def. 5" $ specG banderaTricolor5

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

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

instance Arbitrary Color where
  arbitrary = elements [A,R,M]

-- La propiedad es
prop_banderaTricolor :: [Color] -> Bool
prop_banderaTricolor xs =
  all (== banderaTricolor1 xs)
      [banderaTricolor2 xs,
       banderaTricolor3 xs,
       banderaTricolor4 xs,
       banderaTricolor5 xs]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> bandera n = concat [replicate n c | c <- [M,R,A]]
--    λ> length (banderaTricolor1 (bandera (10^6)))
--    3000000
--    (1.51 secs, 1,024,454,768 bytes)
--    λ> length (banderaTricolor1 (bandera (2*10^6)))
--    6000000
--    (2.94 secs, 2,048,454,832 bytes)
--    λ> length (banderaTricolor2 (bandera (2*10^6)))
--    6000000
--    (2.35 secs, 1,232,454,920 bytes)
--    λ> length (banderaTricolor3 (bandera (2*10^6)))
--    6000000
--    (4.28 secs, 2,304,455,360 bytes)
--    λ> length (banderaTricolor4 (bandera (2*10^6)))
--    6000000
--    (3.01 secs, 1,904,454,672 bytes)
--    λ> length (banderaTricolor5 (bandera (2*10^6)))
--    6000000
--    (2.47 secs, 1,248,454,744 bytes)

2. Soluciones en Python

from enum import IntEnum
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis.strategies import lists, sampled_from

setrecursionlimit(10**6)

class Color(IntEnum):
    R = 0
    A = 1
    M = 2

    def __repr__(self) -> str:
        return self.name

R = Color.R
A = Color.A
M = Color.M

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

def banderaTricolor1(xs: list[Color]) -> list[Color]:
    return [x for x in xs if x == R] + \
           [x for x in xs if x == A] + \
           [x for x in xs if x == M]

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

def banderaTricolor2(xs: list[Color]) -> list[Color]:
    def colores(c: Color) -> list[Color]:
        return list(filter(lambda x: x == c, xs))
    return colores(R) + colores(A) + colores(M)

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

def banderaTricolor3(xs: list[Color]) -> list[Color]:
    return sum([[x for x in xs if x == c] for c in [R, A, M]], [])

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

def banderaTricolor4(xs: list[Color]) -> list[Color]:
    def aux(ys: list[Color],
            rs: list[Color] = [],
            as_: list[Color] = [],
            ms: list[Color] = []) -> list[Color]:
        if not ys:
            return rs + as_ + ms
        match ys[0]:
            case Color.R:
                return aux(ys[1:], [ys[0]] + rs, as_, ms)
            case Color.A:
                return aux(ys[1:], rs, [ys[0]] + as_, ms)
            case Color.M:
                return aux(ys[1:], rs, as_, [ys[0]] + ms)
    return aux(xs)

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

def banderaTricolor5(xs: list[Color]) -> list[Color]:
    rs: list[Color] = []
    as_: list[Color] = []
    ms: list[Color] = []
    for color in xs:
        match color:
            case Color.R:
                rs.append(color)
            case Color.A:
                as_.append(color)
            case Color.M:
                ms.append(color)
    return rs + as_ + ms

# 6ª solución
# ===========

def banderaTricolor6(xs: list[Color]) -> list[Color]:
    return sorted(xs)

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

def test_banderaTricolor() -> None:
    for banderaTricolor in [banderaTricolor1, banderaTricolor2,
                            banderaTricolor3, banderaTricolor4,
                            banderaTricolor5, banderaTricolor6]:
        assert banderaTricolor([M,R,A,A,R,R,A,M,M])  ==  [R,R,R,A,A,A,M,M,M]
        assert banderaTricolor([M,R,A,R,R,A])        ==  [R,R,R,A,A,M]
        print(f"Verificado {banderaTricolor.__name__}")

# La verificación es
#    >>> test_banderaTricolor()
#    Verificado banderaTricolor1
#    Verificado banderaTricolor2
#    Verificado banderaTricolor3
#    Verificado banderaTricolor4
#    Verificado banderaTricolor5
#    Verificado banderaTricolor6

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

@given(lists(sampled_from([R, A, M]), min_size=1))
def test_banderaTricolor_equiv(xs: list[Color]) -> None:
    r = banderaTricolor1(xs)
    assert r == banderaTricolor3(xs)
    assert r == banderaTricolor4(xs)
    assert r == banderaTricolor5(xs)
    assert r == banderaTricolor6(xs)

# La comprobación es
#    >>> test_banderaTricolor_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

def bandera(n: int) -> list[Color]:
    return [c for c in [M, R, A] for _ in range(n)]

# La comparación es
#    >>> tiempo('banderaTricolor1(bandera(6000))')
#    0.01 segundos
#    >>> tiempo('banderaTricolor2(bandera(6000))')
#    0.02 segundos
#    >>> tiempo('banderaTricolor3(bandera(6000))')
#    0.01 segundos
#    >>> tiempo('banderaTricolor4(bandera(6000))')
#    1.27 segundos
#    >>> tiempo('banderaTricolor5(bandera(6000))')
#    0.02 segundos
#    >>> tiempo('banderaTricolor6(bandera(6000))')
#    0.00 segundos
#
#    >>> tiempo('banderaTricolor1(bandera(10**7))')
#    3.97 segundos
#    >>> tiempo('banderaTricolor2(bandera(10**7))')
#    5.35 segundos
#    >>> tiempo('banderaTricolor3(bandera(10**7))')
#    3.25 segundos
#    >>> tiempo('banderaTricolor5(bandera(10**7))')
#    8.79 segundos
#    >>> tiempo('banderaTricolor6(bandera(10**7))')
#    1.17 segundos

2. Soluciones en Common Lisp

(ql:quickload "fiveam" :silent t)

(defpackage :bandera-tricolor
  (:use :cl
        :fiveam))

(in-package :bandera-tricolor)

(defconstant R 'R)
(defconstant A 'A)
(defconstant M 'M)

;;; 1ª solución
;;; ===========

(defun bandera-tricolor-1 (xs)
  (append (loop for x in xs when (eql x R) collect x)
          (loop for x in xs when (eql x A) collect x)
          (loop for x in xs when (eql x M) collect x)))

;;; 2ª solución
;;; ===========

;;; (colores c xs) es la lista de elementos de xs cuyo color es c. Por
;;; ejemplo,
;;;    > (colores R '(M R A A R R A M M))
;;;    (R R R)
(defun colores (c xs)
  (remove-if-not (lambda (x) (eql x c)) xs))

(defun bandera-tricolor-2 (xs)
  (append (colores R xs)
          (colores A xs)
          (colores M xs)))

;;; 3ª solución
;;; ===========

(defun bandera-tricolor-3 (xs)
  (apply #'append
         (mapcar (lambda (c) (colores c xs))
                 '(R A M))))

;;; 4ª solución
;;; ===========

(defun bandera-tricolor-4 (xs)
  (labels ((aux (ys rs as ms)
             (cond ((null ys)
                    (append (reverse rs) (reverse as) (reverse ms)))
                   ((eql (first ys) R)
                    (aux (rest ys) (cons (first ys) rs) as ms))
                   ((eql (first ys) A)
                    (aux (rest ys) rs (cons (first ys) as) ms))
                   ((eql (first ys) M)
                    (aux (rest ys) rs as (cons (first ys) ms))))))
    (aux xs '() '() '())))

;;; 5ª solución
;;; ===========

(defun bandera-tricolor-5 (xs)
  (let ((rs '())
        (as '())
        (ms '()))
    (dolist (x xs)
      (case x
        (R (push x rs))
        (A (push x as))
        (M (push x ms))))
    (append rs as ms)))

;;; 6ª solución
;;; ===========

(defun orden (c)
  (case c
    (R 0)
    (A 1)
    (M 2)))

(defun bandera-tricolor-6 (xs)
  (sort (copy-list xs) #'< :key #'orden))

;;; 7ª solución
;;; ===========

(defun menor (x y)
  (< (orden x) (orden y)))

(defun bandera-tricolor-7 (xs)
  (sort (copy-list xs) #'menor))

;;; Verificación
;;; ============

(test bandera-tricolor
  (mapc (lambda (func)
          (is (equal (funcall func '(M R A A R R A M M)) '(R R R A A A M M M)))
          (is (equal (funcall func '(M R A R R A)) '(R R R A A M))))
        '(bandera-tricolor-1 bandera-tricolor-2 bandera-tricolor-3
          bandera-tricolor-4 bandera-tricolor-5 bandera-tricolor-6
          bandera-tricolor-7)))

(defun verifica ()
  (run 'bandera-tricolor))

;;; La verificación es
;;;    > (bandera-tricolor::verifica)
;;;
;;;    Running test BANDERA-TRICOLOR .............

;;; Comprobación de equivalencia
;;; ============================

;;; (lista-de-colores-aleatoria) es una lista de colores aleatorias con
;;; 100 elementos como máximo. Por ejemplo,
;;;    > (lista-de-colores-aleatoria)
;;;    (M M A R A A M A R M R R A M)
;;;    > (lista-de-colores-aleatoria)
;;;    (A A A M A M R R M M M R A M M M R M M A)
(defun lista-de-colores-aleatoria ()
  (let ((length (random 100)))
    (loop repeat length collect (nth (random 3) '(R A M)))))

(test bandera-tricolor-equiv
  (let* ((xs (lista-de-colores-aleatoria))
         (r1 (bandera-tricolor-1 xs)))
    (is (equal r1 (bandera-tricolor-2 xs)))
    (is (equal r1 (bandera-tricolor-3 xs)))
    (is (equal r1 (bandera-tricolor-4 xs)))
    (is (equal r1 (bandera-tricolor-5 xs)))
    (is (equal r1 (bandera-tricolor-6 xs)))
    (is (equal r1 (bandera-tricolor-7 xs)))))

(defun comprueba ()
  (run 'bandera-tricolor-equiv))

;;; La comprobación es
;;;    > (bandera-tricolor::comprueba)
;;;    Running test BANDERA-TRICOLOR-EQUIV ......

;;; Comparación de eficiencia
;;; =========================

;;; (bandera n) una lista que repite cada color (M, R, A) n veces. Por
;;; ejemplo,
;;;    > (bandera 3)
;;;    (M M M R R R A A A)
(defun bandera (n)
  (loop for c in '(M R A)
        append (loop repeat n collect c)))

;;; La comparación es
;;;    > (time (length (bandera-tricolor-1 (bandera (expt 10 6)))))
;;;    0.252 seconds of real time
;;;    > (time (length (bandera-tricolor-2 (bandera (expt 10 6)))))
;;;    0.383 seconds of real time
;;;    > (time (length (bandera-tricolor-3 (bandera (expt 10 6)))))
;;;    0.371 seconds of real time
;;;    > (time (length (bandera-tricolor-4 (bandera (expt 10 6)))))
;;;    0.308 seconds of real time
;;;    > (time (length (bandera-tricolor-5 (bandera (expt 10 6)))))
;;;    0.301 seconds of real time
;;;    > (time (length (bandera-tricolor-6 (bandera (expt 10 6)))))
;;;    0.378 seconds of real time
;;;    > (time (length (bandera-tricolor-7 (bandera (expt 10 6)))))
;;;    Evaluation took:
;;;    0.276 seconds of real time