Kurzusok
/
Factor
Factor
/
Feladatok
/
A hajógazda éléskamrája
A hajógazda éléskamrája

A hajógazda éléskamrája

Tanulófeladat

Bevezetés

A hashtáblák a Factorban asszociatív tömbök: key/value párok gyűjteményei, amelyekben a keresés O(1). A tágabb assocs családhoz tartoznak.

Hashtábla-literálok

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

A H{ } egy üres hashtábla. A hashtáblák módosíthatók, nőnek és zsugorodnak, ahogy kulcsokat adsz hozzájuk és távolítasz el belőlük. Ha az eredetit érintetlenül akarod hagyni, először hívd meg a clone-t. Egy hashtábla kiírásakor látszanak a bejegyzései, de a sorrend nem igazodik a beszúrás sorrendjéhez. A hashtábláknak nincs meghatározott sorrendjük.

Olvasás

Az at (a assocs szótárban) kiolvas egy értéket, és f-et ad vissza, ha hiányzik a kulcs:

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

Írás

A set-at hozzáad vagy felülír; a delete-at töröl; a change-at pedig lefuttat egy quotationt a jelenlegi értéken. Mindhárom módosítja a hashtáblát:

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, a gyors számlálás

Az inc-at (szintén a assocs szótárban) 1-et ad hozzá a kulcs meglévő értékéhez, és ha a kulcs hiányzik, 1-ként szúrja be. Ideális a darabszámoláshoz:

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

Iteráció és lusta beszúrás

Az assoc-each végigmegy minden ( key value -- ) páron; a cache visszaadja egy kulcs értékét, és ha a kulcs hiányzik, a megadott quotation segítségével egyszer kiszámítja azt.

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

A cache egyetlen szóban a „keresd meg vagy hozd létre” minta. Kézenfekvő, amikor kulcsok sorozatából építesz hashtáblát, és nem akarod minden hívási helyen kezelni a hiányzó bejegyzés esetét.

Hashtábla frissítése kulcsok sorozatán

Amikor a bemenet kulcsok sorozata, és minden kulcsra egyszer akarod frissíteni a hashtáblát, akkor a sorozaton iterálj az each szóval, és egy fried quotationnel ('[ _ … ], a fry szótárból) építsd bele a hashtáblát a ciklustörzsbe. Például egy kulcslista eltávolítása:

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

A '[ _ delete-at ] megragadja a vermen fölötte lévő hashtáblát, így minden iterációban az each-nek csak a kulcsot kell megadnia. A keep lefuttatja a quotationt, és közben megőrzi a hashtáblát a végső . számára.

Hashtábla építése sorozatból

A map>assoc (az assocs szótárban) leképez egy quotationt egy sorozatra, és az ( elt -- key value ) eredményeket a minta típusával megegyező assoc-ba gyűjti:

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

Kulcsok, értékek és párok

A keys és a values (az assocs szótárban) csak a kulcsokat, illetve csak az értékeket adja vissza; a >alist a { key value } párokat.

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

A keys és a values összeillik: egy adott pozícióban lévő érték az ugyanabban a pozícióban lévő kulcshoz tartozik.

A sort-keys (a sorting szótárban) a kulcs szerint rendezett { key value } párokat adja vissza:

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

Pároktól vissza a hashtábláig

A >hashtable (a hashtables szótárban) a >alist inverze: bármely assoc-ot, leggyakrabban { key value } párokból álló alistot, O(1) keresésű hashtáblává alakít.

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

Kézenfekvő, amikor összeállítottál vagy átalakítottál egy párlistát, és vissza akarod hajtani hashtáblába, hogy kulcs alapján keresd ki a bejegyzéseket.

Utasítások

A hajó pénztárosa vagy, aki az éléskamra leltárát kezeli. A leltár egy hashtábla, amelyben minden kulcs egy tételnév, az érték pedig a készleten lévő mennyiség.

1. Készíts leltárt egy listából

Definiáld a create-inventory függvényt úgy, hogy egy tételnevek sorozatát vegye át, és egy olyan hashtáblát adjon vissza, amely minden egyedi nevet a darabszámával párosít.

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

2. Adj hozzá további tételeket

Definiáld az add-items függvényt úgy, hogy egy leltárt és egy tételek sorozatát vegyen át, és egy új leltárt adjon vissza, amelyben minden felsorolt tétel darabszáma meg van növelve. Az eredeti leltárt nem szabad módosítani.

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

3. Csökkentsd a darabszámokat

Definiáld a decrement-items függvényt úgy, hogy egy leltárt és egy tételek sorozatát vegyen át, és egy új leltárt adjon vissza, amelyben minden felsorolt tétel darabszáma eggyel csökkent. A darabszámok soha nem eshetnek nulla alá, és a leltárban még nem szereplő tételeket ki kell hagyni (nem szúrunk be negatív bejegyzéseket).

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

4. Távolíts el egy tételt teljesen

Definiáld a remove-item függvényt úgy, hogy egy leltárt és egy tételt vegyen át, és egy új leltárt adjon vissza, amelyből el van távolítva az a tétel. Ha a tétel nincs a leltárban, adj vissza egy változatlan másolatot.

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

5. Listázd az elérhető tételeket

Definiáld a list-inventory függvényt úgy, hogy egy leltárt vegyen át, és egy { name quantity } párokból álló tömböt adjon vissza, amely csak azokat a tételeket tartalmazza, amelyek mennyisége nullánál nagyobb, név szerint ábécérendbe szedve.

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Szerkesztés GitHubon A hivatkozás új ablakban vagy lapon nyílik meg
Factor Exercism

Készen állsz elkezdeni a(z) A hajógazda éléskamrája feladatot?

Iratkozz fel az Exercism-re, hogy megtanuld és elsajátítsd a(z) Factor nyelvet 47 fogalom163 feladat segítségével, valódi emberi mentorálással, mindez ingyen.