Análisis de “Dealing the best hand of cards”

Análisis de "Dealing the best hand of cards"

Jan 7, 2022 • Al Andrade

Este problema se encuentra con dos soluciones en el libro “Programming Interview Problems: Dynamic Programming” de Leonardo Rossi.

Lo que hago en este notebook es graficar la eficiencia de ambas soluciones y hago una modificación en el código para que nos entregue la suma y el set de números que dieron ese resultado.

Planteamiento

Dada una baraja de cartas, tenemos que repartir una mano con cierto número de cartas. Las cartas pueden ser repartidas de arriba o de abajo de la baraja. Determina la mejor mano que puede ser repartida en términos de la suma de valores de las cartas, asumiendo que cada carta tiene un valor específico.

Ejemplo: Para la baraja [3, 1, 1, 6, 2] podemos repartir las siguientes manos de 3 cartas: [3, 1, 1], [3, 1, 2], [3, 2, 6], [2, 6, 1]. La mejor mano es [3, 2, 6] con la suma 11.

Preguntas de aclaración:

¿El repartidor sabe de los valores de las cartas en la baraja y su orden? Si, asume un completo conocimiento de la baraja
¿Que tan grande puede ser una mano? El tamaño límite es 1,000,000 de cartas
¿La mano puede estar vacía? Si, en ese caso, el valor es 0
¿Qué pasa si no hay suficientes cartas en la baraja para construir una mano del tamaño requerido? En ese caso todo la baraja debe ser repartida.

Se repartirán las siguientes manos:

Todas las cartas de abajo de la baraja
n - 1 cartas de abajo y 1 de arriba
n - 2 cartas de abajo y 2 de arriba
…
Todas las cartas de arriba

Solución 1: Fuerza bruta. Eficiencia O(n²)

Para esta solución, modifiqué el código presentado en el libro para que el programa no solo entregue la suma de la mejor mano, si no que también entregue la mano que da esa suma.

import time
from typing import List

def get_best_hand_from_deck(deck: List, hand_size: int):
    '''
    :param deck: Lista de números que representan las cartas con valor númerico
    :param hand_size: número entero, el tamaño de la mano a repartir
    :return: Regresa la mejor mano posible, y su suma.
    '''
    # En caso de que el deck sea menor a la mano solicitada, regresamos la suma de todo el deck
    if hand_size >= len(deck):
        return deck, sum(deck)

    best_hand_sum = 0
    dealt_hands = []

    for num_top in range(hand_size + 1):
        num_bottom = hand_size - num_top
        # Repartimos cartas de abajo hasta 'num_bottom'
        dealt_hand = deck[0:num_bottom]
        hand_sum = sum(deck[0:num_bottom])
        
        # Repartimos 'num_top' cartas de arriba solo si 'num_top' es diferente de 0
        if num_top != 0:
            top_hand = deck[-num_top:]
            top_sum = sum(deck[-num_top:]) if num_top else 0
            hand_sum = hand_sum + top_sum
            dealt_hand = dealt_hand + top_hand
        
        # Actualizamos best_hand_sum y best_hand de ser necesario
        new_max = max(best_hand_sum, hand_sum)
        if new_max > best_hand_sum:
            best_hand_sum = new_max
            best_hand = dealt_hand
        
    return best_hand, best_hand_sum   

Este código tiene una complejidad de O(n2) ya que el número de sumas depende del tamaño de la mano “hand_size”. Ejemplo:

hand size	sum operations
2	4
3	9
4	16
5	25

Prueba del código con diferentes manos

import random

start = time.time()
mano, suma = get_best_hand_from_deck([3,1,1,6,2], 3)
end = time.time()
total_time = round(end-start,6)

print(f'\nLa mejor mano fue {mano}, con valor de {suma}')
print(f'Este algorítmo resolvió el problema en {total_time} segundos')
print(f'\n')
    
start = time.time()        
mano, suma = get_best_hand_from_deck([5,4,2,7,7,6,4,1,1,1,9,7], 6)
end = time.time()
total_time = round(end-start,6)
print(f'\nLa mejor mano fue {mano}, con valor de {suma}')
print(f'Este algorítmo resolvió el problema en {total_time} segundos')
print(f'\n')

start = time.time()        
mano, suma = get_best_hand_from_deck([5,4,2,7,7,6,4,1,1,1,9,7], 9)
end = time.time()
total_time = round(end-start,6)
print(f'\nLa mejor mano fue {mano}, con valor de {suma}')
print(f'Este algorítmo resolvió el problema en {total_time} segundos')
print(f'\n')

start = time.time()        
mano, suma = get_best_hand_from_deck([5,4,2,7,7,6,4,1,1,1,9,7], 12)
end = time.time()
total_time = round(end-start,6)
print(f'\nLa mejor mano fue {mano}, con valor de {suma}')
print(f'Este algorítmo resolvió el problema en {total_time} segundos')
print(f'\n')

Out:

La mejor mano fue [3, 6, 2], con valor de 11 Este algorítmo resolvió el problema en 0.000101 segundos

La mejor mano fue [5, 4, 2, 7, 9, 7], con valor de 34 Este algorítmo resolvió el problema en 0.000112 segundos

La mejor mano fue [5, 4, 2, 7, 7, 6, 4, 9, 7], con valor de 51 Este algorítmo resolvió el problema en 0.000115 segundos

La mejor mano fue [5, 4, 2, 7, 7, 6, 4, 1, 1, 1, 9, 7], con valor de 54 Este algorítmo resolvió el problema en 0.000101 segundos

Utilizando el deck más largo permitido y entregando 8 mil cartas

large_deck = [random.randint(1,9) for x in range(1000000)]
start = time.time()        
mano, suma = get_best_hand_from_deck(large_deck, 8000)
end = time.time()
total_time = round(end-start,6)
print(f'\nLa mejor mano fue {mano}, con valor de {suma}')
print(f'\nEste algorítmo resolvió el problema en {total_time} segundos')
print(f'\n\n')

Out:

La mejor mano fue [7, 3, 7, 9, 2, 1, 8, 5, 3, 9, 2, 3, 2, 3, 8, 8, 6, 1, 7, 4, 4, 4, 1, 1, 2, 8, 1, 5, 3, 7, 7, 2, 8, 3, 7, 3, 5, 7, 4, 2, 1, 3, 9, 4, 1, 7, 6, 1, 8, 9, 7, 2, 7, 5, 1, 1, 7, 1, 7, 3, 1, 5, 9, 3, 9, 4, 7, 6, 1, 4, 9, 1, 4, 3, 8, 9, 2, 2, 2, 9, 8, 4, 9, 7, 3, 7, 4, 8, 8, 8, 9, 9, 1, 5, 5, 4, 9, 7, 7, 3, 5, 9, 3, 4, 4, 1, 2, 5, 7, 1, 5, 1, 3, 5, 5, 2, 2, 3, 7, 4, … … … , 1, 6, 3, 2, 8, 7, 1, 4, 9, 1, 4, 8, 4, 3, 2, 1, 6, 2, 3, 9, 5, 5, 7, 3, 1, 8, 2, 9, 4, 2, 4, 4, 1, 3], con valor de 40170

Este algorítmo resolvió el problema en 1.015973 segundos

Solución 2. Programación dinámica

tiempo O(n)

Podemos optimizar la solución previa evitando la sumatoria redundante sumamos los valores de las manos, reusando las sumas que ya han sido realizadas.

Por ejemplo: La siguiente mano:

abajo –> 3, 1, 1, 6, 2 <– arriba 2 cartas 3, 1 2 1 carta

Para la siguiente mano, la iteración difiere con la anterior en solo 2 cartas. La 1 se remueve y la 6 se agrega.

abajo –> 3, 1, 1, 6, 2 <– arriba 2 cartas 3, 1 2 1 carta 1 carta 3 6, 2 2 cartas

El valor de la nueva mano puede ser computado del valor de la mano previa en O(1) pasos sustrayendo 1 y agregando 6.

Basado en este razonamiento podemos reescribir el algoritmo, pero igual que el código anterior, este fue modificado para almacenar la mejor mano y entregar tanto la suma como la mejor mano. El problema a resolver es no realizar la asignación de esta mano cada que avanza el programa ya que estaríamos aumentando la complejidad a O(n2). Es por eso que solo almacenamos dos indicadores en el momento que encontramos la mejor mano y armamos el set con estos datos al final, conservando la complejidad en O(n)

def get_best_hand_from_deck_2(deck: List, hand_size: int):
    '''
    :param deck: Lista de números que representan las cartas con valor númerico
    :param hand_size: número entero, el tamaño de la mano a repartir
    :return: Regresa la mejor mano posible, y su suma.
    '''
    
    # Handle the case where the deck is too small.
    if hand_size >= len(deck):
        return deck, sum(deck)
    
    # Empezamos entregando una mano con cartas solo de abajo del deck    num_top = 0
    num_bottom = hand_size
    hand = deck[0:num_bottom]
    hand_sum = sum(hand)

    # Llevamos el rastro de la mejor mano
    best_hand_sum = hand_sum
    
    num_top = 0
    while num_top < hand_size:
        
        # Como ya tenemos la suma de las tres cartas de abajo, solo
        # restamos el valor de las cartas de abajo que serán remplazadas
        # por las de arriba
        num_bottom -= 1
        num_top += 1
        hand_sum -= deck[num_bottom]
        hand_sum += deck[-num_top]
        
        # La siguiente linea no la uso, la muestro solo como una forma
        # en que se puede almacenar la mejor mano, con la desventaja de 
        # aumentar la complejidad del algorítmo. 
        
        # hand = deck[:num_bottom] + deck[-num_top:]
        
        # Actualizamos la mejor mano de ser necesario.
        new_hand_sum = max(best_hand_sum, hand_sum)
        if best_hand_sum < new_hand_sum:
            best_hand_sum = new_hand_sum
            best_hand = hand
            best_num_top = num_top
            best_num_bottom = num_bottom
    
    # Con las siguientes líneas armamos la lista con la mejor mano 
    # encontrada
    if num_top:
        best_hand = deck[0:num_bottom] + deck[-num_top:]
    else:
        best_hand = deck[0:num_bottom]
    
    return best_hand, best_hand_sum

Prueba con un deck pequeño

get_best_hand_from_deck_2([8,2,11,13,1], 2)

Out: ([13, 1], 14)

Con el deck más largo permitido y entregando 8mil cartas

start = time.time()        
mano, suma = get_best_hand_from_deck_2(large_deck, 8000)
end = time.time()
total_time = round(end-start,6)
print(f'\nLa mejor mano fue {mano}, con valor de {suma}')
print(f'\nEste algorítmo resolvió el problema en {total_time} segundos')
print(f'\n\n')

Out:

La mejor mano fue [9, 5, 6, 8, 7, 8, 1, 7, 5, 9, 9, 9, 5, 6, 6, 4, 7, 7, 4, 3, 7, 8, 1, 2, 9, 5, 3, 7, 8, 1, 3, 4, 9, 6, 1, 6, 1, 2, 8, 6, 7, 9, 5, 7, 7, 6, 3, 7, 2, 9, 9, 5, 9, 8, 8, 2, 4, 4, 9, 5, 4, 8, 3, 8, 9, 9, 8, 3, 8, 1, 6, 6, 9, 6, 9, 2, 4, 2, 5, 8, 7, 9, 1, 6, 4, 2, 7, 4, 9, 2, 2, 4, 7, 1, 5, 2, 5, 1, 2, 4, 6, 6, 9, 4, 7, 4, 8, 4, 1, 8, 1, 4, 2, 5, 4, 6, 9, 2, 7, 7, 7, 5, 9, 5, 6, 7, 2, 1, 2, 2, 6, 1, 5, 2, 4, 7, 4, 3, 6, 9, 3, 4, 3, 5, 4, 9, 3, 4, 7, 4, 6, 4, 5, 3, 2, 2, 3, 1, 2, 7, 2, 2, 8, 2, 3, 5, 2, 1, 6, 3, 7, 4, 1, 5, 8, 8, 8, 5, … … … … 9, 2, 6, 2, 2, 4, 4, 4, 8, 8, 8, 3, 2, 3, 7, 8, 4, 4, 8, 6, 9, 6, 7, 3, 4, 8, 3, 9, 5, 8, 8, 5, 5, 9, 3, 7, 8, 1, 6, 3, 2, 8, 7, 1, 4, 9, 1, 4, 8, 4, 3, 2, 1, 6, 2, 3, 9, 5, 5, 7, 3, 1, 8, 2, 9, 4, 2, 4, 4, 1, 3], con valor de 40170

Este algorítmo resolvió el problema en 0.004682 segundos

Podemos ver que la diferencia en tiempo de ejecución de los dos códigos es muy grande. El primero tardó .947 segundos, mientras que el segundo tardó 0.006 segundos. Es decir el primero tardó casi 150 veces lo que el segundo código.

Códigos exactamente como en el libro

def get_best_hand_from_deck_book_a(deck, hand_size):
    # Handle the case where the deck is too small. 
    if hand_size >= len(deck):
        return sum(deck)
    # Keep track of the best known hand. 
    best_hand = 0
    for num_top in range(hand_size + 1):
        num_bottom = hand_size - num_top
        # Deal num_bottom cards from the bottom...
        bottom = sum(deck[0:num_bottom])
        # and num_top cards from the top.
        top = sum(deck[-num_top:]) if num_top else 0 
        hand = bottom + top
        # Update the best hand if needed.
        best_hand = max(best_hand, hand)
    return best_hand


def get_best_hand_from_deck_book_b(deck, hand_size):
    # Handle the case where the deck is too small. 
    if hand_size >= len(deck):
        return sum(deck)
    # Start with a hand dealing only from the bottom of the deck
    num_top = 0
    num_bottom = hand_size
    hand = sum(deck[0:num_bottom])
    # keep track of the best known hand.
    best_hand = hand
    while num_top < hand_size:
        # Give up the deepest card from the bottom,
        # replacing it with a card dealt from the top.
        num_bottom -= 1
        num_top += 1
        hand -= deck[num_bottom]
        hand += deck[-num_top]
        #Update the best hand if needed.
        best_hand = max(best_hand, hand)
    return best_hand


start = time.time()        
suma = get_best_hand_from_deck_book_b(large_deck, 8000)
end = time.time()
total_time = round(end-start,6)
print(f'\nLa mejor mano fue con valor de {suma}')
print(f'Este algorítmo resolvió el problema en {total_time} segundos')
print(f'\n\n')

Out:

La mejor mano fue con valor de 40170 Este algorítmo resolvió el problema en 0.004916 segundos

Comparativo gráfico de las funciones

import numpy as np
import matplotlib.pyplot as plt

def total_time(deck: List, hand_size: int):
    start = time.time()
    get_best_hand_from_deck(deck, hand_size)
    end = time.time()
    f1time = end - start
    
    return f1time

def total_time_2(deck: List, hand_size: int):
    start2 = time.time()
    get_best_hand_from_deck_2(deck, hand_size)
    end2 = time.time()
    f2time = end2 - start2
    
    return f2time

def total_time_3(deck: List, hand_size: int):
    start2 = time.time()
    get_best_hand_from_deck_book_b(deck, hand_size)
    end2 = time.time()
    f2time = end2 - start2
    
    return f2time

total_time(large_deck,4)

def compareAsymptotic(deck: List, hand_size: int, step: int):
    x = np.arange(2, hand_size, step)
    y = [total_time(deck, xe) for xe in x]
    y2 = [total_time_2(deck, xe) for xe in x]
    y3 = [total_time_3(deck, xe) for xe in x]
    plt.title(f'O(n^2) vs O(n)')
    plt.plot(x, y, 'r', label='Fuerza bruta')
    plt.plot(x, y2, 'b', label='Mi solución dinámica')
    plt.plot(x, y3, 'y', label='Solución dinámica (Libro)')
    plt.legend()
    plt.show()
    
def compareAsymptotic2(deck: List, hand_size: int, step: int):
    x = np.arange(3, hand_size, step)
    y2 = [total_time_2(deck, xe) for xe in x]
    y3 = [total_time_3(deck, xe) for xe in x]
    plt.title(f'O(n)')
    plt.plot(x, y2, 'b', label='Mi solución dinámica')
    plt.plot(x, y3, 'g', label='Solución dinámica (Libro)')
    plt.legend()
    plt.show()    
    
compareAsymptotic(large_deck, 500, 20)

compareAsymptotic2(large_deck, 100000, 1000)  

Out:

Conclusión

En la primera gráfica podemos ver como el primer código “Fuerza Bruta” crece exponencialmente por lo que con una gran cantidad de datos deja de ser útil. Para pequeños programas que no trabajarán con muchos datos, esta forma de programar no hará gran diferencia, o al menos no será notoria humanamente.

En la segunda gráfica podemos ver que la solución dinámica donde agregé código para entregar además de la suma, la mano que daba ese resultado, crece linearmente casi a la par que la solución dinámica del libro. Es decir, sigue manteniendo su eficiencia aún con una gran cantidad de datos.

Un buen código puede hacer una gran diferencia.

al4ndrade