Temario Lección 76 de 148 · Límites raros
Límites raros

Primero sin conexión

Por qué importa "Envía la lista entera, gana la última escritura" funciona hasta que dos dispositivos editan sin conexión. Entonces los cambios de una persona desaparecen en silencio, y nadie sabe decir adónde fueron.

Una app familiar de lista de la compra tiene que funcionar en el sótano de un supermercado sin cobertura. Cada dispositivo lleva un log de lo que hizo. Cuando los dispositivos vuelven a conectarse, los dos logs se mezclan en una sola lista. Los dos logs empiezan con la misma historia compartida (todo lo sincronizado antes de quedarse sin conexión), y luego cada uno tiene sus propios cambios.

Log de operaciones: un registro de los cambios hechos (añade esto, quita aquello), en vez de una copia del resultado. Los logs se pueden mezclar; las copias solo pueden sobrescribirse.

("add", "milk", "p7")             # tag p7 is unique to this add
("remove", "milk", ["p7", "s2"])  # removes exactly the adds this device had seen
Tu turno

Escribe merge(log_a, log_b) y devuelve la lista ordenada de artículos de la lista de la compra mezclada (cada artículo una vez). Un log es una lista de operaciones: ("add", item, tag), donde cada add tiene una etiqueta única, y ("remove", item, tags), donde tags enumera los add de ese artículo que el dispositivo podía ver cuando lo quitó.

Límites. No se puede perder ningún cambio: un artículo está en la lista si al menos uno de sus add nunca se quitó. Un remove solo anula las etiquetas que enumera, así que un add que hizo el otro dispositivo sin conexión sobrevive. Los dos logs pueden contener las mismas operaciones compartidas (cuéntalas una vez). merge(a, b) debe ser igual a merge(b, a).

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.