listaCuadrada :: Int -> a -> [a] -> [[a]]

listaCuadrada 3 7 [0,3,5,2,4]  ==  [[0,3,5],[2,4,7],[7,7,7]]
listaCuadrada 3 7 [0..]        ==  [[0,1,2],[3,4,5],[6,7,8]]
listaCuadrada 2 'p' "eva"      ==  ["ev","ap"]
listaCuadrada 2 'p' ['a'..]    ==  ["ab","cd"]

module Lista_cuadrada where

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

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

listaCuadrada1 :: Int -> a -> [a] -> [[a]]
listaCuadrada1 n x xs =
  take n (grupos n (xs ++ repeat x))

-- (grupos n xs) es la lista obtenida agrupando los elementos de xs en
-- grupos de n elementos, salvo el último que puede tener menos. Por
-- ejemplo,
--    grupos 2 [4,2,5,7,6]     ==  [[4,2],[5,7],[6]]
--    take 3 (grupos 3 [1..])  ==  [[1,2,3],[4,5,6],[7,8,9]]
grupos :: Int -> [a] -> [[a]]
grupos _ [] = []
grupos n xs = take n xs : grupos n (drop n xs)

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

listaCuadrada2 :: Int -> a -> [a] -> [[a]]
listaCuadrada2 n x xs =
  take n (grupos2 n (xs ++ repeat x))

grupos2 :: Int -> [a] -> [[a]]
grupos2 _ [] = []
grupos2 n xs = ys : grupos n zs
  where (ys,zs) = splitAt n xs

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

listaCuadrada3 :: Int -> a -> [a] -> [[a]]
listaCuadrada3 n x xs =
  take n (chunksOf n (xs ++ repeat x))

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

verifica :: IO ()
verifica = hspec spec

specG :: (Int -> Int -> [Int] -> [[Int]])  -> Spec
specG listaCuadrada = do
  it "e1" $
    listaCuadrada 3 7 [0,3,5,2,4]  `shouldBe`  [[0,3,5],[2,4,7],[7,7,7]]
  it "e2" $
    listaCuadrada 3 7 [0..]        `shouldBe`  [[0,1,2],[3,4,5],[6,7,8]]

spec :: Spec
spec = do
  describe "def. 1" $ specG listaCuadrada1
  describe "def. 2" $ specG listaCuadrada2
  describe "def. 3" $ specG listaCuadrada3

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

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

-- La propiedad es
prop_listaCuadrada :: Int -> Int -> [Int] -> Bool
prop_listaCuadrada n x xs =
  all (== listaCuadrada1 n x xs)
      [listaCuadrada2 n x xs,
       listaCuadrada3 n x xs]

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

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

-- La comparación es
--    λ> length (listaCuadrada1 (10^4) 5 [1..])
--    10000
--    (2.02 secs, 12,801,918,616 bytes)
--    λ> length (listaCuadrada2 (10^4) 5 [1..])
--    10000
--    (1.89 secs, 12,803,198,576 bytes)
--    λ> length (listaCuadrada3 (10^4) 5 [1..])
--    10000
--    (1.85 secs, 12,801,518,728 bytes)

from itertools import chain, islice, repeat
from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st
from more_itertools import chunked

setrecursionlimit(10**6)

A = TypeVar('A')

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

# grupos(n, xs) es la lista obtenida agrupando los elementos de xs en
# grupos de n elementos, salvo el último que puede tener menos. Por
# ejemplo,
#    >>> grupos(2, [4,2,5,7,6])
#    [[4, 2], [5, 7], [6]]
def grupos(n: int, xs: list[A]) -> list[list[A]]:
    if not xs:
        return []
    return [list(islice(xs, n))] + grupos(n, xs[n:])

def listaCuadrada1(n: int, x: A, xs: list[A]) -> list[list[A]]:
    return grupos(n, list(islice(chain(xs, repeat(x)), n * n)))

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

def grupos2(n: int, xs: list[A]) -> list[list[A]]:
    if not xs:
        return []
    ys, zs = xs[:n], xs[n:]
    return [ys] + grupos(n, zs)

def listaCuadrada2(n: int, x: A, xs: list[A]) -> list[list[A]]:
    return grupos2(n, list(islice(chain(xs, repeat(x)), n * n)))

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

def listaCuadrada3(n: int, x: A, xs: list[A]) -> list[list[A]]:
    return list(chunked(list(islice(chain(xs, repeat(x)), n * n)), n))

# listaCuadrada3 :: Int -> a -> [a] -> [[a]]
# listaCuadrada3 n x xs =
#   take n (chunksOf n (xs ++ repeat x))

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

def test_listaCuadrada() -> None:
    for listaCuadrada in [listaCuadrada1, listaCuadrada2, listaCuadrada3]:
        assert listaCuadrada(3, 7, [0,3,5,2,4]) == [[0, 3, 5], [2, 4, 7], [7, 7, 7]]
        print(f"Verificado {listaCuadrada.__name__}")

# La verificación es
#    >>> test_listaCuadrada()
#    Verificado listaCuadrada1
#    Verificado listaCuadrada2
#    Verificado listaCuadrada3

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

# La propiedad es
@given(st.integers(min_value=1, max_value=100),
       st.integers(),
       st.lists(st.integers(), max_size=100))
def test_listaCuadrada_equiv(n: int, x: int, xs: list[int]) -> None:
    r = listaCuadrada1(n, x, xs)
    assert listaCuadrada2(n, x, xs) == r
    assert listaCuadrada3(n, x, xs) == r

# La comprobación es
#    >>> test_listaCuadrada_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")

# La comparación es
#    >>> tiempo('listaCuadrada1(10**3, 5, range(100))')
#    3.55 segundos
#    >>> tiempo('listaCuadrada2(10**3, 5, range(100))')
#    3.44 segundos
#    >>> tiempo('listaCuadrada3(10**3, 5, range(100))')
#    0.06 segundos

(ql:quickload "fiveam" :silent t)
(ql:quickload "serapeum" :silent t)

(defpackage :lista-cuadrada
  (:use :cl :fiveam)
  (:import-from :serapeum batches))

(in-package :lista-cuadrada)

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

;;; (take n xs) es la lista de los n primeros elementos de xs. Por
;;; ejemplo,
;;;    > (take 2 '(4 2 5 7 6))
;;;    (4 2)
(defun take (n xs)
  (cond ((= n 0) ())
        ((null xs) ())
        (t (cons (first xs) (take (- n 1) (rest xs))))))

;;; (drop n xs) es la lista obtenida eliminando los n primeros elementos
;;; de xs. Por ejemplo,
;;;    > (drop 2 '(4 2 5 7 6))
;;;    (5 7 6)
(defun drop (n xs)
  (cond ((= n 0) xs)
        ((null xs) ())
        (t (drop (- n 1) (rest xs)))))

;;; (grupos n xs) es la lista obtenida agrupando los elementos de xs en
;;; grupos de n elementos, salvo el último que puede tener menos. Por
;;; ejemplo,
;;;    > (grupos 2 '(4 2 5 7 6))
;;;    ((4 2) (5 7) (6))
(defun grupos (n xs)
  (if (null xs)
      ()
      (cons (take n xs) (grupos n (drop n xs)))))

(defun lista-cuadrada1 (n x xs)
  (take n
        (grupos n
                (append xs
                        (make-list (max 0 (- (* n n) (length xs)))
                                   :initial-element x)))))

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

;;; (split-at n xs) son las listas de los n elementos de xs y lo que
;;; queda de xs al eliminar dichos elementos. Por ejemplo,
;;;    > (split-at 0 '(3 4 5 6 7))
;;;    NIL
;;;    (3 4 5 6 7)
;;;    > (split-at 2 '(3 4 5 6 7))
;;;    (3 4)
;;;    (5 6 7)
;;;    > (split-at 9 '(3 4 5 6 7))
;;;    (3 4 5 6 7)
;;;    NIL
(defun split-at (n xs)
  (defun aux (n ys zs)
    (if (or (= n 0) (null zs))
        (values (nreverse ys) zs)
        (aux (1- n)
             (cons (first zs) ys)
             (rest zs))))
  (aux n () xs))

;;; (grupos n xs) es la lista obtenida agrupando los elementos de xs en
;;; grupos de n elementos, salvo el último que puede tener menos. Por
;;; ejemplo,
;;;    > (grupos2 2 '(4 2 5 7 6))
;;;    ((4 2) (5 7) (6))
(defun grupos2 (n xs)
  (if (null xs)
      ()
      (multiple-value-bind (ys zs) (split-at n xs)
        (cons ys (grupos2 n zs)))))

(defun lista-cuadrada2 (n x xs)
  (take n
        (grupos2 n
                 (append xs
                         (make-list (max 0 (- (* n n) (length xs)))
                                    :initial-element x)))))

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

;;; (take-iter n xs) es la lista de los n primeros elementos de xs. Por
;;; ejemplo,
;;;    > (take-iter 2 '(4 2 5 7 6))
;;;    (4 2)
;;;    > (take-iter 9 '(4 2 5 7 6))
;;;    (4 2 5 7 6)
(defun take-iter (n xs)
 (loop for i below n
       for x in xs
       collect x))

;;; (drop-iter n xs) es la lista obtenida eliminando los n primeros elementos
;;; de xs. Por ejemplo,
;;;    > (drop-iter 2 '(4 2 5 7 6))
;;;    (5 7 6)
;;;    > (drop-iter 9 '(4 2 5 7 6))
;;;    NIL
(defun drop-iter (n xs)
  (loop for i below (1+ n)
        for x on xs
        finally (return x)))

;;; (grupos-iter n xs) es la lista obtenida agrupando los elementos de xs en
;;; grupos de n elementos, salvo el último que puede tener menos. Por
;;; ejemplo,
;;;    > (grupos-iter 2 '(4 2 5 7 6))
;;;    ((4 2) (5 7) (6))
(defun grupos-iter (n xs)
  (let ((result '()))
    (loop while xs
          do (push (take-iter n xs) result)
          (setf xs (drop-iter n xs)))
    (nreverse result)))

(defun lista-cuadrada3 (n x xs)
  (take-iter n
             (grupos-iter n
                          (append xs
                                  (make-list (max 0 (- (* n n) (length xs)))
                                             :initial-element x)))))

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

(defun lista-cuadrada4 (n x xs)
  (take n
        (serapeum:batches (append xs
                                  (make-list (max 0 (- (* n n) (length xs)))
                                             :initial-element x))
                          n)))

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

(test lista-cuadrada
  (mapc (lambda (lista-cuadrada)
          (is (equal (funcall lista-cuadrada 3 7 '(0 3 5 2 4))
                     '((0 3 5) (2 4 7) (7 7 7))))
          (is (equal (funcall lista-cuadrada 2 7 '(0 3 5 2 4))
                     '((0 3) (5 2)))))
        '(lista-cuadrada1
          lista-cuadrada2
          lista-cuadrada3
          lista-cuadrada4
          )))

(defun verifica ()
  (run 'lista-cuadrada))

;;; La verificación es
;;;    > (verifica)
;;;
;;;    Running test LISTA-CUADRADA ........

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

;;; La propiedad es
(test lista-cuadrada-equiv
  (for-all ((n (gen-integer :min 1 :max 10))
            (x (gen-integer :min 1 :max 10))
            (xs (gen-list)))
    (let ((ys (lista-cuadrada1 n x xs)))
      (is (equal ys (lista-cuadrada2 n x xs)))
      (is (equal ys (lista-cuadrada3 n x xs)))
      (is (equal ys (lista-cuadrada4 n x xs)))
      )))

(defun comprueba ()
  (run 'lista-cuadrada-equiv))

;;; La comprobación es
;;;    > (comprueba)
;;;
;;;    Running test LISTA-CUADRADA-EQUIV ...

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

;;; La comparación es
;;;    > (time (lista-cuadrada1 2000 5 (make-list 100 :initial-element 0))) (values)
;;;    0.322 seconds of real time
;;;    > (time (lista-cuadrada2 2000 5 (make-list 100 :initial-element 0))) (values)
;;;    0.192 seconds of real time
;;;    (time (lista-cuadrada3 2000 5 (make-list 100 :initial-element 0))) (values)
;;;    0.207 seconds of real time
;;;    > (time (lista-cuadrada3 2000 5 (make-list 100 :initial-element 0))) (values)
;;;    0.155 seconds of real time