Percursos
/
Factor
Factor
/
Exercícios
/
A Despensa do Comissário
A Despensa do Comissário

A Despensa do Comissário

Exercício de aprendizagem

Introdução

As tabelas de hash em Factor são arrays associativos: coleções de pares key/value com consulta em O(1). Fazem parte da família mais ampla dos assocs.

Literais de tabelas de hash

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

H{ } é uma tabela de hash vazia. As tabelas de hash são mutáveis: crescem e encolhem à medida que adicionas e removes chaves. Faz clone primeiro se precisares de deixar a original intacta. Imprimir uma tabela de hash mostra as suas entradas, mas a ordem não segue a ordem de inserção: as tabelas de hash não são ordenadas.

Leitura

at (em assocs) lê um valor e devolve f se a chave não existir:

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

Escrita

set-at adiciona ou substitui; delete-at remove; change-at executa uma quotation sobre o valor atual. As três mutam:

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: o atalho para contabilizar

inc-at (também em assocs) soma 1 ao valor existente de uma chave e insere-a com 1 quando não existe. É perfeito para contabilizar:

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

Iteração e inserção preguiçosa

assoc-each percorre cada par ( key value -- ); cache devolve o valor de uma chave e calcula-o uma única vez com a quotation fornecida, se a chave não existir.

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

cache é o padrão «consultar ou criar» numa única palavra, o que dá jeito quando estás a construir uma tabela de hash a partir de um fluxo de chaves e não queres tratar do caso da entrada em falta em cada local de chamada.

Aplicar uma atualização a uma tabela de hash ao longo de uma sequência de chaves

Quando a entrada é uma sequência de chaves e queres atualizar a tabela de hash uma vez por chave, itera a sequência com each e usa uma quotation frita '[ _ … ] (do fry) para incorporar a tabela de hash no corpo do ciclo. Por exemplo, para remover uma lista de chaves:

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

'[ _ delete-at ] captura a tabela de hash que está por cima na pilha, para que em cada iteração each só tenha de fornecer a chave. keep executa a quotation e preserva a tabela de hash para o . final.

Construir uma tabela de hash a partir de uma sequência

map>assoc (em assocs) mapeia uma quotation sobre uma sequência e reúne os resultados ( elt -- key value ) num assoc do tipo do exemplar:

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

Chaves, valores e pares

keys e values (em assocs) devolvem apenas as chaves ou apenas os valores; >alist devolve os 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 e values correspondem-se: o valor numa dada posição pertence à chave na mesma posição.

sort-keys (em sorting) devolve os pares { key value } ordenados pela chave:

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

De pares de volta a uma tabela de hash

>hashtable (em hashtables) é o inverso de >alist: transforma qualquer assoc, habitualmente um alist de pares { key value }, numa tabela de hash com consulta em O(1).

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

Dá jeito quando reuniste ou transformaste uma lista de pares e queres voltar a transformá-la numa tabela de hash para consultar entradas pela chave.

Instruções

És o comissário do navio, responsável pela gestão do inventário da despensa. O inventário é uma tabela de hash em que cada chave é o nome de um item e o valor é a quantidade em stock.

1. Criar um inventário a partir de uma lista

Define create-inventory para receber uma sequência de nomes de itens e devolver uma tabela de hash que associa cada nome único à respetiva contagem.

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

2. Adicionar mais itens

Define add-items para receber um inventário e uma sequência de itens e devolver um novo inventário cujas contagens foram incrementadas para cada item listado. O inventário original não deve ser modificado.

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

3. Decrementar contagens

Define decrement-items para receber um inventário e uma sequência de itens e devolver um novo inventário cujas contagens foram diminuídas em uma unidade para cada item listado. As contagens nunca podem ficar abaixo de zero, e os itens que ainda não estão no inventário devem ser omitidos (não são inseridas entradas negativas).

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

4. Remover um item por completo

Define remove-item para receber um inventário e um item e devolver um novo inventário com esse item removido. Se o item não estiver presente, devolve uma cópia inalterada.

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

5. Listar os itens disponíveis

Define list-inventory para receber um inventário e devolver um array de pares { name quantity } que contém apenas os itens cuja quantidade é maior que zero, ordenados alfabeticamente por nome.

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Editar via GitHub A ligação abre numa nova janela ou separador
Factor Exercism

Estás pronto para começar A Despensa do Comissário?

Inscreve-te no Exercism para aprenderes e dominares Factor com 47 conceitos163 exercícios, e mentoria humana real, tudo grátis.