2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
◂●▸ ?
Proyecto: Un Robot
“ [...] la pregunta de si las Máquinas Pueden Pensar [...] es tan relevante como la
pregunta de si los Submarinos Pueden Nadar.”
— Edsger Dijkstra, Las amenazas a la ciencia informática
En los capítulos del “proyecto”, dejaré de golpearte con nueva teoría por un
breve momento, y en su lugar trabajaremos en un programa juntos. La teoría
es necesaria para aprender a programar, pero leer y entender programas reales
es igual de importante.
Nuestro proyecto en este capítulo es construir un autómata, un pequeño
programa que realiza una tarea en un mundo virtual. Nuestro autómata será
un robot de entrega de correo que recoge y deja paquetes.
Meadowfield
El pueblo de Meadowfield no es muy grande. Consiste en 11 lugares con 14
carreteras entre ellos. Se puede describir con este array de carreteras:
[Link] 1/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
const roads = [
"Casa de Alice-Casa de Bob","Casa de Alice-Cabaña",
"Casa de Alice-Oficina de Correos","Casa de Bob-Ayuntamiento",
"Casa de Daria-Casa de Ernie","Casa de Daria-Ayuntamiento",
"Casa de Ernie-Casa de Grete","Casa de Grete-Granja",
"Casa de Grete-Tienda","Plaza del Mercado-Granja",
"Plaza del Mercado-Oficina de Correos","Plaza del Mercado-Tienda
"Plaza del Mercado-Ayuntamiento","Tienda-Ayuntamiento"
];
La red de carreteras en el pueblo forma un gráfico. Un gráfico es una colección
de puntos (lugares en el pueblo) con líneas entre ellos (carreteras). Este gráfico
será el mundo por el que se moverá nuestro robot.
El array de cadenas no es muy fácil de trabajar. Lo que nos interesa son los
destinos a los que podemos llegar desde un lugar dado. Vamos a convertir la
lista de carreteras en una estructura de datos que, para cada lugar, nos diga qué
se puede alcanzar desde allí.
function buildGraph(edges) {
let graph = [Link](null);
function addEdge(from, to) {
if (from in graph) {
graph[from].push(to);
} else {
[Link] 2/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
graph[from] = [to];
}
}
for (let [from, to] of [Link](r => [Link]("-"))) {
addEdge(from, to);
addEdge(to, from);
}
return graph;
}
const roadGraph = buildGraph(roads);
Dado un array de aristas, buildGraph crea un objeto de mapa que, para cada
nodo, almacena un array de nodos conectados.
Utiliza el método split para pasar de las cadenas de carreteras, que tienen la
forma "Inicio-Fin" , a arrays de dos elementos que contienen el inicio y el fin
como cadenas separadas.
La tarea
Nuestro robot se moverá por el pueblo. Hay paquetes en varios lugares, cada
uno dirigido a algún otro lugar. El robot recoge los paquetes cuando llega a
ellos y los entrega cuando llega a sus destinos.
El autómata debe decidir, en cada punto, hacia dónde ir a continuación. Habrá
terminado su tarea cuando todos los paquetes hayan sido entregados.
Para poder simular este proceso, debemos definir un mundo virtual que pueda
describirlo. Este modelo nos dice dónde está el robot y dónde están los
paquetes. Cuando el robot decide moverse a algún lugar, necesitamos
actualizar el modelo para reflejar la nueva situación.
Si estás pensando en términos de programación orientada a objetos, tu primer
impulso podría ser empezar a definir objetos para los diferentes elementos en
el mundo: una clase para el robot, una para un paquete, tal vez una para
[Link] 3/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
lugares. Estos podrían tener propiedades que describen su estado actual, como
la pila de paquetes en un lugar, que podríamos cambiar al actualizar el mundo.
Esto es incorrecto. Al menos, usualmente lo es. El hecho de que algo suene
como un objeto no significa automáticamente que deba ser un objeto en tu
programa. Escribir reflexivamente clases para cada concepto en tu aplicación
tiende a dejarte con una colección de objetos interconectados que tienen su
propio estado interno cambiable. Estos programas a menudo son difíciles de
entender y, por lo tanto, fáciles de romper.
En lugar de eso, vamos a condensar el estado del pueblo en el conjunto mínimo
de valores que lo define. Está la ubicación actual del robot y la colección de
paquetes no entregados, cada uno de los cuales tiene una ubicación actual y
una dirección de destino. Eso es todo.
Y mientras lo hacemos, hagamos que no cambiemos este estado cuando el
robot se mueve, sino que calculemos un nuevo estado para la situación después
del movimiento.
class VillageState {
constructor(place, parcels) {
[Link] = place;
[Link] = parcels;
}
move(destination) {
if (!roadGraph[[Link]].includes(destination)) {
return this;
} else {
let parcels = [Link](p => {
if ([Link] != [Link]) return p;
return {place: destination, address: [Link]};
}).filter(p => [Link] != [Link]);
return new VillageState(destination, parcels);
}
}
}
[Link] 4/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
El método move es donde ocurre la acción. Primero verifica si hay un camino
desde el lugar actual hasta el destino, y si no lo hay, devuelve el estado anterior
ya que este no es un movimiento válido.
Luego crea un nuevo estado con el destino como el nuevo lugar del robot. Pero
también necesita crear un nuevo conjunto de paquetes: los paquetes que lleva
el robot (que están en el lugar actual del robot) deben ser trasladados al nuevo
lugar. Y los paquetes dirigidos al nuevo lugar deben ser entregados, es decir,
deben ser eliminados del conjunto de paquetes no entregados. La llamada a
map se encarga del traslado y la llamada a filter de la entrega.
Los objetos de parcela no se modifican cuando se mueven, sino que se vuelven
a crear. El método move nos proporciona un nuevo estado de aldea pero deja
intacto por completo el anterior.
let first = new VillageState(
"Oficina de Correos",
[{place: "Oficina de Correos", address: "Casa de Alice"}]
);
let next = [Link]("Casa de Alice");
[Link]([Link]);
// → Casa de Alice
[Link]([Link]);
// → []
[Link]([Link]);
// → Oficina de Correos
El movimiento hace que la parcela se entregue, y esto se refleja en el siguiente
estado. Pero el estado inicial sigue describiendo la situación en la que el robot
está en la oficina de correos y la parcela no se ha entregado.
Datos persistentes
Las estructuras de datos que no cambian se llaman inmutables o persistentes.
Se comportan de manera similar a las cadenas de texto y los números en el
[Link] 5/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
sentido de que son lo que son y se mantienen así, en lugar de contener cosas
diferentes en momentos diferentes.
En JavaScript, casi todo puede cambiarse, por lo que trabajar con valores que
se supone que son persistentes requiere cierta moderación. Existe una función
llamada [Link] que cambia un objeto para que la escritura en sus
propiedades sea ignorada. Podrías usar esto para asegurarte de que tus objetos
no se modifiquen, si así lo deseas. Congelar requiere que la computadora
realice un trabajo adicional, y que las actualizaciones se ignoren es casi tan
propenso a confundir a alguien como hacer que hagan lo incorrecto. Por lo
tanto, suelo preferir simplemente decirle a las personas que un objeto dado no
debe ser modificado y esperar que lo recuerden.
let object = [Link]({value: 5});
[Link] = 10;
[Link]([Link]);
// → 5
¿Por qué me estoy esforzando tanto en no cambiar los objetos cuando el
lenguaje obviamente espera que lo haga?
Porque me ayuda a entender mis programas. Una vez más, esto se trata de
gestionar la complejidad. Cuando los objetos en mi sistema son cosas fijas y
estables, puedo considerar operaciones sobre ellos de forma aislada: moverse a
la casa de Alice desde un estado inicial dado siempre produce el mismo nuevo
estado. Cuando los objetos cambian con el tiempo, eso añade toda una nueva
dimensión de complejidad a este tipo de razonamiento.
Para un sistema pequeño como el que estamos construyendo en este capítulo,
podríamos manejar ese poco de complejidad extra. Pero el límite más
importante respecto a qué tipo de sistemas podemos construir es cuánto
podemos entender. Cualquier cosa que haga que tu código sea más fácil de
entender te permite construir un sistema más ambicioso.
Desafortunadamente, aunque entender un sistema construido sobre
estructuras de datos persistentes es más fácil, diseñar uno, especialmente
[Link] 6/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
cuando tu lenguaje de programación no ayuda, puede ser un poco más difícil.
Buscaremos oportunidades para usar estructuras de datos persistentes en este
libro, pero también usaremos aquellas que pueden cambiar.
Simul ación
Un robot de entrega observa el mundo y decide en qué dirección quiere
moverse. Como tal, podríamos decir que un robot es una función que toma un
objeto VillageState y devuelve el nombre de un lugar cercano.
Dado que queremos que los robots puedan recordar cosas, para que puedan
hacer y ejecutar planes, también les pasamos su memoria y les permitimos
devolver una nueva memoria. Por lo tanto, lo que un robot devuelve es un
objeto que contiene tanto la dirección en la que quiere moverse como un valor
de memoria que se le dará la próxima vez que se llame.
function runRobot(state, robot, memory) {
for (let turn = 0;; turn++) {
if ([Link] == 0) {
[Link](`Terminado en ${turn} turnos`);
break;
}
let action = robot(state, memory);
state = [Link]([Link]);
memory = [Link];
[Link](`Movido a ${[Link]}`);
}
}
Consideremos lo que un robot tiene que hacer para “resolver” un estado dado.
Debe recoger todos los paquetes visitando cada ubicación que tenga un paquete
y entregarlos visitando cada ubicación a la que esté dirigido un paquete, pero
solo después de recoger el paquete.
¿Cuál es la estrategia más tonta que podría funcionar? El robot podría
simplemente caminar en una dirección aleatoria en cada turno. Eso significa
[Link] 7/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
que, con gran probabilidad, eventualmente se topará con todos los paquetes y
en algún momento también llegará al lugar donde deben ser entregados.
Esto es cómo podría lucir eso:
function randomPick(array) {
let choice = [Link]([Link]() * [Link]);
return array[choice];
}
function randomRobot(state) {
return {direction: randomPick(roadGraph[[Link]])};
}
Recuerda que [Link]() devuelve un número entre cero y uno, pero
siempre por debajo de uno. Multiplicar dicho número por la longitud de un
array y luego aplicarle [Link] nos da un índice aleatorio para el array.
Dado que este robot no necesita recordar nada, ignora su segundo argumento
(recuerda que las funciones de JavaScript pueden ser llamadas con argumentos
adicionales sin efectos adversos) y omite la propiedad memory en su objeto
devuelto.
Para poner a trabajar a este sofisticado robot, primero necesitaremos una
forma de crear un nuevo estado con algunos paquetes. Un método estático
(escrito aquí añadiendo directamente una propiedad al constructor) es un buen
lugar para poner esa funcionalidad.
[Link] = function(parcelCount = 5) {
let parcels = [];
for (let i = 0; i < parcelCount; i++) {
let address = randomPick([Link](roadGraph));
let place;
do {
place = randomPick([Link](roadGraph));
} while (place == address);
[Link]({place, address});
}
[Link] 8/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
return new VillageState("Oficina de Correos", parcels);
};
No queremos ningún paquete que sea enviado desde el mismo lugar al que está
dirigido. Por esta razón, el bucle do sigue eligiendo nuevos lugares cuando
obtiene uno que es igual a la dirección.
Vamos a iniciar un mundo virtual.
runRobot([Link](), randomRobot);
// → Movido a Mercado
// → Movido a Ayuntamiento
// → …
// → Terminado en 63 turnos
Al robot le lleva muchas vueltas entregar los paquetes porque no está
planificando muy bien. Abordaremos eso pronto.
Para tener una perspectiva más agradable de la simulación, puedes usar la
función runRobotAnimation que está disponible en el entorno de
programación de este capítulo. Esto ejecuta la simulación, pero en lugar de
mostrar texto, te muestra al robot moviéndose por el mapa del pueblo.
runRobotAnimation([Link](), randomRobot);
La forma en que runRobotAnimation está implementada permanecerá como
un misterio por ahora, pero después de que hayas leído los capítulos
posteriores de este libro, que tratan sobre la integración de JavaScript en los
navegadores web, podrás adivinar cómo funciona.
Ruta del camión de c orreo
Deberíamos poder hacerlo mucho mejor que el robot aleatorio. Una mejora
sencilla sería inspirarnos en la forma en que funciona la entrega de correo en el
mundo real. Si encontramos una ruta que pase por todos los lugares del
pueblo, el robot podría recorrer esa ruta dos veces, momento en que se
[Link] 9/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
garantizaría que ha terminado. Aquí tienes una de esas rutas (comenzando
desde la oficina de correos):
const mailRoute = [
"Casa de Alice", "Cabaña", "Casa de Alice", "Casa de Bob",
"Ayuntamiento", "Casa de Daria", "Casa de Ernie",
"Casa de Grete", "Tienda", "Casa de Grete", "Granja",
"Plaza del Mercado", "Oficina de Correos"
];
Para implementar el robot que sigue la ruta, necesitaremos hacer uso de la
memoria del robot. El robot guarda el resto de su ruta en su memoria y deja
caer el primer elemento en cada turno.
function routeRobot(state, memory) {
if ([Link] == 0) {
memory = mailRoute;
}
return {direction: memory[0], memory: [Link](1)};
}
Este robot es mucho más rápido ya. Tomará un máximo de 26 vueltas (el doble
de la ruta de 13 pasos) pero generalmente menos.
runRobotAnimation([Link](), routeRobot, []);
Búsqueda de caminos
Aún así, no llamaría a seguir ciegamente una ruta fija un comportamiento
inteligente. Sería más eficiente si el robot ajustara su comportamiento a la
tarea real que debe realizarse.
Para hacer eso, tiene que poder moverse deliberadamente hacia un paquete
dado o hacia la ubicación donde se debe entregar un paquete. Hacer eso,
incluso cuando el objetivo está a más de un movimiento de distancia, requerirá
algún tipo de función de búsqueda de ruta.
[Link] 10/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
El problema de encontrar una ruta a través de un grafo es un problema de
búsqueda típico. Podemos determinar si una solución dada (una ruta) es una
solución válida, pero no podemos calcular directamente la solución como
podríamos hacerlo para 2 + 2. En su lugar, debemos seguir creando soluciones
potenciales hasta encontrar una que funcione.
El número de rutas posibles a través de un grafo es infinito. Pero al buscar una
ruta de A a B, solo estamos interesados en aquellas que comienzan en A.
Además, no nos importan las rutas que visiten el mismo lugar dos veces, esas
definitivamente no son las rutas más eficientes en ningún lugar. Así que eso
reduce la cantidad de rutas que el buscador de rutas debe [Link] hecho,
estamos mayormente interesados en la ruta más corta. Por lo tanto, queremos
asegurarnos de buscar rutas cortas antes de mirar las más largas. Un buen
enfoque sería “expandir” rutas desde el punto de inicio, explorando cada lugar
alcanzable que aún no haya sido visitado, hasta que una ruta llegue al objetivo.
De esta manera, solo exploraremos rutas que sean potencialmente
interesantes, y sabremos que la primera ruta que encontremos es la ruta más
corta (o una de las rutas más cortas, si hay más de una).
Aquí hay una función que hace esto:
function findRoute(graph, from, to) {
let work = [{at: from, route: []}];
for (let i = 0; i < [Link]; i++) {
let {at, route} = work[i];
for (let place of graph[at]) {
if (place == to) return [Link](place);
if () {
[Link]({at: place, route: [Link](place)});
}
}
}
}
La exploración debe realizarse en el orden correcto: los lugares que se
alcanzaron primero deben explorarse primero. No podemos explorar de
inmediato un lugar tan pronto como lleguemos a él porque eso significaría que
[Link] 11/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
los lugares alcanzados desde allí también se explorarían de inmediato, y así
sucesivamente, incluso si puede haber otros caminos más cortos que aún no se
han explorado.
Por lo tanto, la función mantiene una lista de trabajo. Esta es una matriz de
lugares que deben ser explorados a continuación, junto con la ruta que nos
llevó allí. Comienza con solo la posición de inicio y una ruta vacía.
La búsqueda luego opera tomando el siguiente elemento en la lista y
explorándolo, lo que significa que se ven todas las rutas que salen de ese lugar.
Si una de ellas es el objetivo, se puede devolver una ruta terminada. De lo
contrario, si no hemos mirado este lugar antes, se agrega un nuevo elemento a
la lista. Si lo hemos mirado antes, dado que estamos buscando rutas cortas
primero, hemos encontrado o bien una ruta más larga a ese lugar o una
exactamente tan larga como la existente, y no necesitamos explorarla.
Puedes imaginar visualmente esto como una red de rutas conocidas que se
extienden desde la ubicación de inicio, creciendo de manera uniforme en todos
los lados (pero nunca enredándose de nuevo en sí misma). Tan pronto como el
primer hilo alcance la ubicación objetivo, ese hilo se rastrea de vuelta al inicio,
dándonos nuestra ruta.
Nuestro código no maneja la situación en la que no hay más elementos de
trabajo en la lista de trabajo porque sabemos que nuestro gráfico está
conectado, lo que significa que se puede llegar a cada ubicación desde todas las
demás ubicaciones. Siempre podremos encontrar una ruta entre dos puntos, y
la búsqueda no puede fallar.
function goalOrientedRobot({place, parcels}, route) {
if ([Link] == 0) {
let parcel = parcels[0];
if ([Link] != place) {
route = findRoute(roadGraph, place, [Link]);
} else {
route = findRoute(roadGraph, place, [Link]);
}
}
[Link] 12/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
return {direction: route[0], memory: [Link](1)};
}
Este robot utiliza el valor de su memoria como una lista de direcciones en las
que moverse, al igual que el robot que sigue la ruta. Cuando esa lista está vacía,
debe averiguar qué hacer a continuación. Toma el primer paquete no entregado
del conjunto y, si ese paquete aún no ha sido recogido, traza una ruta hacia él.
Si el paquete ya ha sido recogido, todavía necesita ser entregado, por lo que el
robot crea una ruta hacia la dirección de entrega.
Veamos cómo lo hace.
runRobotAnimation([Link](),
goalOrientedRobot, []);
Este robot suele terminar la tarea de entregar 5 paquetes en aproximadamente
16 turnos. Eso es ligeramente mejor que routeRobot pero definitivamente no
es óptimo.
Ejercicios
Medición de un rob ot
Es difícil comparar de manera objetiva los robots solo dejando que resuelvan
algunos escenarios. Tal vez un robot simplemente tuvo tareas más fáciles o el
tipo de tareas en las que es bueno, mientras que el otro no.
Escribe una función compareRobots que tome dos robots (y su memoria
inicial). Debería generar 100 tareas y permitir que cada uno de los robots
resuelva cada una de estas tareas. Cuando termine, debería mostrar el número
promedio de pasos que cada robot dio por tarea.
Por el bien de la equidad, asegúrate de darle a cada tarea a ambos robots, en
lugar de generar tareas diferentes por robot.
function compareRobots(robot1, memory1, robot2, memory2) {
// Tu código aquí
[Link] 13/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
compareRobots(routeRobot, [], goalOrientedRobot, []);
Mostrar pistas...
Eficiencia del rob ot
¿Puedes escribir un robot que termine la tarea de entrega más rápido que
goalOrientedRobot ? Si observas el comportamiento de ese robot, ¿qué cosas
claramente absurdas hace? ¿Cómo podrían mejorarse?
Si resolviste el ejercicio anterior, es posible que desees utilizar tu función
compareRobots para verificar si mejoraste el robot.
// Tu código aquí
runRobotAnimation([Link](), tuRobot, memoria);
Mostrar pistas...
Grup o per sist ent e
La mayoría de las estructuras de datos proporcionadas en un entorno estándar
de JavaScript no son muy adecuadas para un uso persistente. Los Arrays tienen
métodos slice y concat , que nos permiten crear fácilmente nuevos arrays sin
dañar el antiguo. Pero Set , por ejemplo, no tiene métodos para crear un nuevo
conjunto con un elemento añadido o eliminado.
Escribe una nueva clase PGroup , similar a la clase Grupo del Capítulo 6, que
almacena un conjunto de valores. Al igual que Grupo , tiene métodos add ,
delete , y has .
Sin embargo, su método add debería devolver una nueva instancia de PGroup
con el miembro dado añadido y dejar la anterior sin cambios. De manera
similar, delete crea una nueva instancia sin un miembro dado.
[Link] 14/15
2/6/25, 13:41 Proyecto: Un Robot :: Eloquent JavaScript
La clase debería funcionar para valores de cualquier tipo, no solo para strings.
No tiene que ser eficiente cuando se utiliza con grandes cantidades de valores.
El constructor no debería ser parte de la interfaz de la clase (aunque
definitivamente querrás usarlo internamente). En su lugar, hay una instancia
vacía, [Link] , que se puede usar como valor inicial.
¿Por qué necesitas solo un valor [Link] , en lugar de tener una función
que cree un nuevo mapa vacío cada vez?
class PGroup {
// Tu código aquí
}
let a = [Link]("a");
let ab = [Link]("b");
let b = [Link]("a");
[Link]([Link]("b"));
// → true
[Link]([Link]("b"));
// → false
[Link]([Link]("a"));
// → false
Mostrar pistas...
◂●▸ ?
[Link] 15/15
