Tracks
/
Factor
Factor
/
Ejercicios
/
La despensa del sobrecargo
La despensa del sobrecargo

La despensa del sobrecargo

Ejercicio de aprendizaje

Introducción

Las tablas hash en Factor son arrays asociativos: colecciones de pares key/value con búsqueda en O(1). Forman parte de la familia más amplia de assocs.

Literales de tabla hash

H{ { "coal" 1 } { "wood" 2 } } .

H{ } es una tabla hash vacía. Las tablas hash son mutables: crecen y se encogen a medida que agregas y quitas claves. Haz clone primero si necesitas dejar intacta la original. Al imprimir una tabla hash se muestran sus entradas, pero el orden no está ligado al orden de inserción: las tablas hash no tienen orden.

Lectura

at (en assocs) lee un valor y devuelve f si la clave no está:

at      ( key assoc -- value/f )
key?    ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at .   ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at .   ! => f

Escritura

set-at agrega o sobrescribe; delete-at elimina; change-at ejecuta una quotation sobre el valor actual. Las tres mutan:

set-at     ( value key assoc -- )
delete-at  ( key assoc -- )
change-at  ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }

inc-at: el atajo para contar

inc-at (también en assocs) suma 1 al valor que ya existe para una clave, y la inserta con 1 cuando no está. Perfecto para llevar la cuenta:

inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }

Iteración e inserción perezosa

assoc-each recorre cada par ( key value -- ); cache devuelve el valor de una clave y lo calcula una sola vez con la quotation que le pases, si la clave no está.

assoc-each ( assoc quot: ( key value -- ) -- )
cache      ( key assoc quot: ( key -- value ) -- value )

cache es el patrón «buscar o crear» en una sola palabra: útil cuando estás construyendo una tabla hash a partir de un flujo de claves y no quieres manejar el caso de la entrada faltante en cada sitio de llamada.

Aplicar una actualización de la tabla hash a lo largo de una secuencia de claves

Cuando la entrada es una secuencia de claves y quieres actualizar la tabla hash una vez por clave, itera la secuencia con each y usa una fried quotation '[ _ … ] (de fry) para incorporar la tabla hash al cuerpo del bucle. Por ejemplo, quitar una lista de claves:

{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }

'[ _ delete-at ] captura la tabla hash que está por encima en la pila, de modo que en cada iteración each solo necesita aportar la clave. keep ejecuta la quotation y a la vez conserva la tabla hash para el . final.

Construir una tabla hash a partir de una secuencia

map>assoc (en assocs) aplica una quotation a una secuencia y reúne los resultados ( elt -- key value ) en un assoc del tipo del ejemplar:

map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }

Claves, valores y pares

keys y values (en assocs) devuelven solo las claves o solo los valores; >alist devuelve los pares { key value }.

keys   ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys .     ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values .   ! the matching values

keys y values se corresponden: el valor en una posición dada pertenece a la clave en esa misma posición.

sort-keys (en sorting) devuelve los pares { key value } ordenados por clave:

H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }

De los pares de vuelta a una tabla hash

>hashtable (en hashtables) es la inversa de >alist: convierte cualquier assoc (la mayoría de las veces un alist de pares { key value }) en una tabla hash con búsqueda en O(1).

>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } }   (entry order not guaranteed)

Es útil cuando armaste o transformaste una lista de pares y quieres volver a convertirla en una tabla hash para buscar entradas por clave.

Instrucciones

Eres el sobrecargo del barco y te encargas del inventario de la despensa. El inventario es un hashtable en el que cada clave es el nombre de un artículo y el valor es la cantidad disponible.

1. Construye un inventario a partir de una lista

Define create-inventory para que reciba una secuencia de nombres de artículos y devuelva un hashtable que asocie cada nombre único con su cantidad.

{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }

2. Agrega más artículos

Define add-items para que reciba un inventario y una secuencia de artículos y devuelva un inventario nuevo con las cantidades incrementadas por cada artículo de la lista. El inventario original no debe modificarse.

H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }

3. Disminuye las cantidades

Define decrement-items para que reciba un inventario y una secuencia de artículos y devuelva un inventario nuevo con las cantidades disminuidas en uno por cada artículo de la lista. Las cantidades nunca deben quedar por debajo de cero, y los artículos que todavía no estén en el inventario deben omitirse (no se insertan entradas negativas).

H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }

4. Elimina un artículo por completo

Define remove-item para que reciba un inventario y un artículo y devuelva un inventario nuevo con ese artículo eliminado. Si el artículo no está presente, devuelve una copia sin cambios.

H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }

5. Enumera los artículos disponibles

Define list-inventory para que reciba un inventario y devuelva un array de pares { name quantity } que contenga solo los artículos cuya cantidad sea mayor que cero, ordenados alfabéticamente por nombre.

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Editar en GitHub El enlace se abre en una ventana o una pestaña nuevas
Factor Exercism

¿Todo listo para empezar La despensa del sobrecargo?

Regístrate en Exercism para aprender y dominar Factor con 47 conceptos163 ejercicios y mentoría humana real, todo gratis.