Acertijo: Consistencia en gorros de béisbol

Imagina un grupo de aficionados en una fila para un partido de béisbol. Cada persona lleva un gorro del equipo, pero algunos lo usan hacia adelante (indicado como 'F') y otros hacia atrás (indicado como 'B'). Como guardia, solo puedes dejar pasar al grupo si todos los gorros están orientados de la misma manera, ya sea todos hacia adelante o todos hacia atrás. No puedes ordenar directamente "gíralo hacia adelante" o "hacia atrás", solo puedes decir "gira tu gorro". El objetivo es minimizar el número de instrucciones emitidas, idealmente en una sola pasada por la fila.

Por ejemplo, con esta secuencia de gorrros:

F F B B B F B B B F F B F

Las instrucciones óptimas podrían involucrar rangos: "gira los gorros de la posición 2 a la 4", "de la 6 a la 8", y "en la posición 11".

Algoritmo uno: Identificación de segmentos contiguos

Este algoritmo cuenta los segmentos donde los gorros están orientados de la misma manera. Se determina qué orientación tiene menos segmentos, y se giran esos segmentos para lograr la consistencia. El código original se simplifica añadiendo un marcador al final para manejar el último segmanto sin lógica adicional.

def ajustar_gorros(gorros):
    gorros.append('M')  # Marcador para facilitar el procesamiento
    segmentos = []
    inicio = 0
    conteo_adelante = 0
    conteo_atras = 0
    for i in range(1, len(gorros)):
        if gorros[inicio] != gorros[i]:
            segmentos.append((inicio, i - 1, gorros[inicio]))
            if gorros[inicio] == 'F':
                conteo_adelante += 1
            else:
                conteo_atras += 1
            inicio = i
    orientacion_objetivo = 'B' if conteo_adelante > conteo_atras else 'F'
    for seg in segmentos:
        if seg[2] == orientacion_objetivo:
            if seg[0] == seg[1]:
                print(f"Gira el gorro en la posición {seg[0]}")
            else:
                print(f"Gira los gorros desde la posición {seg[0]} hasta {seg[1]}")

gorros_ejemplo = ['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B', 'B', 'F', 'F', 'B', 'F']
ajustar_gorros(gorros_ejemplo)
# Salida esperada:
# Gira los gorros desde la posición 2 hasta 4
# Gira los gorros desde la posición 6 hasta 8
# Gira el gorro en la posición 11

Algoritmo dos: Pasada única

Se basa en la observación de que la orientación del primer gorro determina la orientación con más segmentos, ya que ese grupo siempre será igual o mayor. Por lo tanto, se puede generar instrucciones en una sola iteración comparando cada gorro con el anterior.

def ajustar_gorros_pasada_unica(gorros):
    gorros.append(gorros[0])  # Añade un elemento al final para simplificar la lógica
    i = 1
    while i < len(gorros):
        if gorros[i] != gorros[i - 1]:
            inicio_rango = i
            while i < len(gorros) and gorros[i] != gorros[i - 1]:
                i += 1
            fin_rango = i - 1
            if gorros[inicio_rango] != gorros[0]:
                print(f"Desde la posición {inicio_rango}")
            else:
                print(f"Hasta la posición {fin_rango}: gira los gorros")
        else:
            i += 1

gorros_ejemplo = ['F', 'F', 'B', 'B', 'B', 'F', 'B', 'B', 'B', 'F', 'F', 'B', 'F']
ajustar_gorros_pasada_unica(gorros_ejemplo)
# Salida esperada (formato simplificado):
# Desde la posición 2
# Hasta la posición 4: gira los gorros
# Desde la posición 6
# Hasta la posición 8: gira los gorros
# Desde la posición 11
# Hasta la posición 11: gira los gorros

Concepto subyacente: Compresión de datos

Este acertijo ilustra un principio de compresión de datos, donde instrucciones repetitivas para grupos contiguos se reducen a comandos concisos. Un método relacionado es el Run-Length Encoding (RLE), que codifica secuencias de caracteres idénticos como un conteo seguido del carácter. Por ejemplo, la cadena "WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB" se comprime a "13W2B12W5B".

Implementación de Run-Length Encoding en Python

def codificar_rle(cadena):
    if not cadena:
        return ""
    resultado = ""
    contador = 1
    caracter_actual = cadena[0]
    for i in range(1, len(cadena)):
        if cadena[i] == caracter_actual:
            contador += 1
        else:
            resultado += f"{contador}{caracter_actual}"
            caracter_actual = cadena[i]
            contador = 1
    resultado += f"{contador}{caracter_actual}"
    return resultado

def decodificar_rle(cadena_codificada):
    resultado = ""
    i = 0
    while i < len(cadena_codificada):
        num = ""
        while i < len(cadena_codificada) and cadena_codificada[i].isdigit():
            num += cadena_codificada[i]
            i += 1
        if i < len(cadena_codificada):
            caracter = cadena_codificada[i]
            resultado += caracter * int(num)
            i += 1
    return resultado

cadena_original = "WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB"
cadena_codificada = codificar_rle(cadena_original)
print(f"Cadena codificada: {cadena_codificada}")
print(f"Cadena decodificada: {decodificar_rle(cadena_codificada)}")
# Salida:
# Cadena codificada: 13W2B12W5B
# Cadena decodificada: WWWWWWWWWWWWWBBWWWWWWWWWWWWBBBBB