Track
/
Factor
Factor
/
Esercizi
/
La dispensa del commissario di bordo
La dispensa del commissario di bordo

La dispensa del commissario di bordo

Esercizio di apprendimento

Introduzione

Le tabelle hash in Factor sono array associativi: collezioni di coppie key/value con ricerca in tempo O(1). Fanno parte della più ampia famiglia di assocs.

Letterali di tabella hash

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

H{ } è una tabella hash vuota. Le tabelle hash sono mutabili: crescono e si riducono man mano che aggiungi e rimuovi chiavi. Se devi lasciare intatta quella originale, fai prima un clone. Stampare una tabella hash ne mostra le voci, ma l'ordine non segue quello di inserimento: le tabelle hash non sono ordinate.

Lettura

at (in assocs) legge un valore e restituisce f se la chiave manca:

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

Scrittura

set-at aggiunge o sovrascrive; delete-at rimuove; change-at esegue una quotation sul valore corrente. Tutte e tre mutano la tabella:

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: la scorciatoia per contare

inc-at (anch'essa in assocs) aggiunge 1 al valore esistente di una chiave e la inserisce con valore 1 se manca. Perfetta per contare:

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

Iterazione e inserimento pigro

assoc-each percorre ogni coppia ( key value -- ); cache restituisce il valore di una chiave e lo calcola una sola volta con la quotation fornita, se la chiave manca.

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

cache è il pattern «cerca o crea» in una sola parola: comodo quando costruisci una tabella hash da un flusso di chiavi e non vuoi gestire il caso della voce mancante a ogni chiamata.

Applicare un aggiornamento della tabella hash a una sequenza di chiavi

Quando l'input è una sequenza di chiavi e vuoi aggiornare la tabella hash una volta per chiave, itera sulla sequenza con each e usa una fried quotation '[ _ … ] (da fry) per incorporare la tabella hash nel corpo del ciclo. Ad esempio, per rimuovere un array di chiavi:

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

'[ _ delete-at ] cattura la tabella hash che sta sopra di essa sullo stack, così a ogni iterazione each deve fornire solo la chiave. keep esegue la quotation preservando la tabella hash per il . finale.

Costruire una tabella hash da una sequenza

map>assoc (in assocs) mappa una quotation su una sequenza e raccoglie i risultati ( elt -- key value ) in un assoc del tipo dell'esemplare:

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

Chiavi, valori e coppie

keys e values (in assocs) restituiscono solo le chiavi o solo i valori; >alist restituisce le coppie { 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 e values sono allineati: il valore in una data posizione appartiene alla chiave nella stessa posizione.

sort-keys (in sorting) restituisce le coppie { key value } ordinate per chiave:

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

Dalle coppie di nuovo a una tabella hash

>hashtable (in hashtables) è l'inverso di >alist: trasforma qualsiasi assoc (il più delle volte un alist di coppie { key value }) in una tabella hash con ricerca O(1).

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

Comodo quando hai assemblato o trasformato un array di coppie e vuoi ripiegarlo in una tabella hash per cercare le voci per chiave.

Istruzioni

Sei il commissario di bordo della nave e gestisci l'inventario della cambusa. L'inventario è una hashtable in cui ogni chiave è il nome di un articolo e il valore è la quantità disponibile.

1. Costruisci un inventario da una lista

Definisci create-inventory in modo che prenda una sequenza di nomi di articoli e restituisca una hashtable che associa ogni nome unico al suo conteggio.

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

2. Aggiungi altri articoli

Definisci add-items in modo che prenda un inventario e una sequenza di articoli e restituisca un nuovo inventario con i conteggi incrementati per ogni articolo elencato. L'inventario originale non deve essere modificato.

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

3. Decrementa i conteggi

Definisci decrement-items in modo che prenda un inventario e una sequenza di articoli e restituisca un nuovo inventario con i conteggi diminuiti di uno per ogni articolo elencato. I conteggi non devono mai scendere sotto zero e gli articoli non ancora presenti nell'inventario vanno lasciati fuori (non vengono inserite voci negative).

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

4. Rimuovi completamente un articolo

Definisci remove-item in modo che prenda un inventario e un articolo e restituisca un nuovo inventario con quell'articolo rimosso. Se l'articolo non è presente, restituisci una copia invariata.

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

5. Elenca gli articoli disponibili

Definisci list-inventory in modo che prenda un inventario e restituisca un array di coppie { name quantity } contenente solo gli articoli con quantità maggiore di zero, ordinati alfabeticamente per nome.

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Modifica tramite GitHub Il link si apre in una nuova finestra o scheda
Factor Exercism

Vuoi iniziare La dispensa del commissario di bordo?

Iscriviti a Exercism per imparare e padroneggiare Factor con 47 concetti163 esercizi e il mentoring di persone reali, tutto gratis.