powered by 
Du schreibst Funktionen mit einer Struktur, die zu jedem Schlüssel einen Wert hat: nachschlagen wie im Telefonbuch, Strichlisten führen, Wörter in Gruppen ordnen und einen kleinen Cache nachbauen.
Eine Liste findet ihre Elemente über den Index, 0, 1, 2. Oft will man aber über etwas anderes nachschlagen: die Nummer zu einem Namen, den Preis zu einer Ware. Dafür ordnet man jedem Schlüssel einen Wert zu.
In Ruby heißt das ein Hash:
ages = { 'Ada' => 36, 'Alan' => 41 } puts ages['Ada'] # 36 ages['Grace'] = 85 # ein neues Paar puts ages.key?('Linus') # false: diesen Schlüssel gibt es nicht puts ages.fetch('Linus', 0) # 0, wenn es ihn nicht gibt ages.each do |name, age| puts "#{name} wurde #{age}" end
In Python heißt das ein Dictionary:
ages = {'Ada': 36, 'Alan': 41} print(ages['Ada']) # 36 ages['Grace'] = 85 # ein neues Paar print('Linus' in ages) # False: diesen Schlüssel gibt es nicht print(ages.get('Linus', 0)) # 0, wenn es ihn nicht gibt for name, age in ages.items(): print(f'{name} wurde {age}')
In JavaScript nimmt man dafür ein Objekt:
const ages = { Ada: 36, Alan: 41 }; console.log(ages['Ada']); // 36 ages['Grace'] = 85; // ein neues Paar console.log('Linus' in ages); // false: diesen Schlüssel gibt es nicht console.log(ages['Linus'] || 0); // 0, wenn es ihn nicht gibt for (const name in ages) { console.log(`${name} wurde ${ages[name]}`); }
Die Schlüssel eines Objekts sind immer Texte; eine Zahl als Schlüssel wird zu
einem Text. Wer etwas anderes als Schlüssel braucht, nimmt eine Map.
Nachschlagen geht in einem Dictionary sofort, ganz gleich, wie viele Paare es hat; in einer Liste muss man suchen. Wie das gelingt, zeigt die Handbuchseite Hash Tables.
Ein Telefonbuch ordnet jedem Namen eine Nummer zu: {'Ada' => '030 1815', 'Alan' => '040 1912', 'Grace' => '089 1906'}. Schreib eine Funktion phone_number(book, name), die die Nummer zurückgibt, und 'unbekannt', wenn der Name nicht darin steht: phone_number(book, 'Ada') ergibt '030 1815'.
book['Ada'] ist die Nummer, die zum Schlüssel 'Ada' gehört.
book.key?(name) fragt, ob der Name darin steht.
Ein Telefonbuch ordnet jedem Namen eine Nummer zu: {'Ada': '030 1815', 'Alan': '040 1912', 'Grace': '089 1906'}. Schreib eine Funktion phone_number(book, name), die die Nummer zurückgibt, und 'unbekannt', wenn der Name nicht darin steht: phone_number(book, 'Ada') ergibt '030 1815'.
book['Ada'] ist die Nummer, die zum Schlüssel 'Ada' gehört.
name in book fragt, ob der Name darin steht.
Ein Telefonbuch ordnet jedem Namen eine Nummer zu: {'Ada': '030 1815', 'Alan': '040 1912', 'Grace': '089 1906'}. Schreib eine Funktion phoneNumber(book, name), die die Nummer zurückgibt, und 'unbekannt', wenn der Name nicht darin steht: phoneNumber(book, 'Ada') ergibt '030 1815'.
book['Ada'] ist die Nummer, die zum Schlüssel 'Ada' gehört.
name in book fragt, ob der Name darin steht.
Schreib eine Funktion count_items(items), die zählt, wie oft jedes Element in der Liste steht, und das als Hash zurückgibt: count_items(['Apfel', 'Birne', 'Apfel']) ergibt {'Apfel' => 2, 'Birne' => 1}. Ohne tally und group_by.
Fang mit einem leeren Hash an, {}. Für jedes Element erhöhst du seinen Zähler um 1.
Beim ersten Mal hat das Element noch keinen Zähler: counts.fetch(item, 0) ist dann 0.
Schreib eine Funktion count_items(items), die zählt, wie oft jedes Element in der Liste steht, und das als Dictionary zurückgibt: count_items(['Apfel', 'Birne', 'Apfel']) ergibt {'Apfel': 2, 'Birne': 1}. Ohne Counter.
Fang mit einem leeren Dictionary an, {}. Für jedes Element erhöhst du seinen Zähler um 1.
Beim ersten Mal hat das Element noch keinen Zähler: counts.get(item, 0) ist dann 0.
Schreib eine Funktion countItems(items), die zählt, wie oft jedes Element in der Liste steht, und das als Objekt zurückgibt: countItems(['Apfel', 'Birne', 'Apfel']) ergibt {'Apfel': 2, 'Birne': 1}. Ohne Object.groupBy.
Fang mit einem leeren Objekt an, {}. Für jedes Element erhöhst du seinen Zähler um 1.
Beim ersten Mal hat das Element noch keinen Zähler: counts[item] ist dann undefined, und counts[item] || 0 ist 0.
Im Schulkiosk hat alles seinen Preis, in Cent: {'Brötchen' => 50, 'Brezel' => 80, 'Saft' => 150}. Schreib eine Funktion total_price(prices, cart), die zusammenrechnet, was die Liste cart kostet: total_price(prices, ['Brezel', 'Saft', 'Brezel']) ergibt 310.
Geh den Einkauf durch, nicht die Preisliste. prices['Saft'] ist der Preis eines Safts.
Im Schulkiosk hat alles seinen Preis, in Cent: {'Brötchen': 50, 'Brezel': 80, 'Saft': 150}. Schreib eine Funktion total_price(prices, cart), die zusammenrechnet, was die Liste cart kostet: total_price(prices, ['Brezel', 'Saft', 'Brezel']) ergibt 310.
Geh den Einkauf durch, nicht die Preisliste. prices['Saft'] ist der Preis eines Safts.
Im Schulkiosk hat alles seinen Preis, in Cent: {'Brötchen': 50, 'Brezel': 80, 'Saft': 150}. Schreib eine Funktion totalPrice(prices, cart), die zusammenrechnet, was die Liste cart kostet: totalPrice(prices, ['Brezel', 'Saft', 'Brezel']) ergibt 310.
Geh den Einkauf durch, nicht die Preisliste. prices['Saft'] ist der Preis eines Safts.
scores ordnet jedem Namen seine Punkte zu. Schreib eine Funktion keys_with_value(scores, value), die die Namen mit genau value Punkten als Liste zurückgibt, in der Reihenfolge, in der sie in scores stehen: keys_with_value({'Ada' => 7, 'Alan' => 5, 'Grace' => 7}, 7) ergibt ['Ada', 'Grace'].
scores.each do |name, points| … end geht die Paare der Reihe nach durch, Schlüssel und Wert.
scores ordnet jedem Namen seine Punkte zu. Schreib eine Funktion keys_with_value(scores, value), die die Namen mit genau value Punkten als Liste zurückgibt, in der Reihenfolge, in der sie in scores stehen: keys_with_value({'Ada': 7, 'Alan': 5, 'Grace': 7}, 7) ergibt ['Ada', 'Grace'].
for name, points in scores.items(): geht die Paare der Reihe nach durch, Schlüssel und Wert.
scores ordnet jedem Namen seine Punkte zu. Schreib eine Funktion keysWithValue(scores, value), die die Namen mit genau value Punkten als Liste zurückgibt, in der Reihenfolge, in der sie in scores stehen: keysWithValue({'Ada': 7, 'Alan': 5, 'Grace': 7}, 7) ergibt ['Ada', 'Grace'].
for (const name in scores) { … } geht die Schlüssel der Reihe nach durch; scores[name] ist der Wert.
Schreib eine Funktion letter_count(text), die zählt, wie oft jeder Buchstabe von a bis z im Text vorkommt; groß und klein zählen gemeinsam, alles andere zählt nicht: letter_count('Anna!') ergibt {'a' => 2, 'n' => 2}.
Wie die Strichliste, nur über die Buchstaben des Textes. Welche Zeichen lässt du aus?
Schreib eine Funktion letter_count(text), die zählt, wie oft jeder Buchstabe von a bis z im Text vorkommt; groß und klein zählen gemeinsam, alles andere zählt nicht: letter_count('Anna!') ergibt {'a': 2, 'n': 2}.
Wie die Strichliste, nur über die Buchstaben des Textes. Welche Zeichen lässt du aus?
Schreib eine Funktion letterCount(text), die zählt, wie oft jeder Buchstabe von a bis z im Text vorkommt; groß und klein zählen gemeinsam, alles andere zählt nicht: letterCount('Anna!') ergibt {'a': 2, 'n': 2}.
Wie die Strichliste, nur über die Buchstaben des Textes. Welche Zeichen lässt du aus?
Schreib eine Funktion most_frequent(words), die das Wort zurückgibt, das in der Liste am häufigsten vorkommt: most_frequent(['ja', 'nein', 'ja']) ergibt 'ja'. Kommen mehrere gleich oft vor, gewinnt das, das zuerst in der Liste steht. Die Liste ist nie leer.
Zwei Schritte: Zähl zuerst wie bei der Strichliste. Dann such das Wort mit dem größten Zähler, wie bei der größten Zahl einer Liste.
Geh beim Suchen die Wörter der Liste der Reihe nach durch, dann gewinnt bei gleich vielen das erste.
Schreib eine Funktion most_frequent(words), die das Wort zurückgibt, das in der Liste am häufigsten vorkommt: most_frequent(['ja', 'nein', 'ja']) ergibt 'ja'. Kommen mehrere gleich oft vor, gewinnt das, das zuerst in der Liste steht. Die Liste ist nie leer.
Zwei Schritte: Zähl zuerst wie bei der Strichliste. Dann such das Wort mit dem größten Zähler, wie bei der größten Zahl einer Liste.
Geh beim Suchen die Wörter der Liste der Reihe nach durch, dann gewinnt bei gleich vielen das erste.
Schreib eine Funktion mostFrequent(words), die das Wort zurückgibt, das in der Liste am häufigsten vorkommt: mostFrequent(['ja', 'nein', 'ja']) ergibt 'ja'. Kommen mehrere gleich oft vor, gewinnt das, das zuerst in der Liste steht. Die Liste ist nie leer.
Zwei Schritte: Zähl zuerst wie bei der Strichliste. Dann such das Wort mit dem größten Zähler, wie bei der größten Zahl einer Liste.
Geh beim Suchen die Wörter der Liste der Reihe nach durch, dann gewinnt bei gleich vielen das erste.
Schreib eine Funktion group_by_length(words), die die Wörter nach ihrer Länge in Gruppen ordnet: Der Schlüssel ist die Länge, der Wert die Liste der Wörter mit dieser Länge, in ihrer Reihenfolge. group_by_length(['ich', 'du', 'wir']) ergibt {3 => ['ich', 'wir'], 2 => ['du']}. Ohne group_by.
Die Werte sind Listen. Beim ersten Wort einer Länge gibt es seine Liste noch nicht: groups[length] ||= [] legt sie an, wenn sie fehlt.
Danach hängst du das Wort an: groups[length] << word.
Schreib eine Funktion group_by_length(words), die die Wörter nach ihrer Länge in Gruppen ordnet: Der Schlüssel ist die Länge, der Wert die Liste der Wörter mit dieser Länge, in ihrer Reihenfolge. group_by_length(['ich', 'du', 'wir']) ergibt {3: ['ich', 'wir'], 2: ['du']}. Ohne itertools.groupby.
Die Werte sind Listen. Beim ersten Wort einer Länge gibt es seine Liste noch nicht: Leg sie an, wenn die Länge noch nicht in groups steht.
Danach hängst du das Wort an: groups[length].append(word).
Schreib eine Funktion groupByLength(words), die die Wörter nach ihrer Länge in Gruppen ordnet: Der Schlüssel ist die Länge, der Wert die Liste der Wörter mit dieser Länge, in ihrer Reihenfolge. groupByLength(['ich', 'du', 'wir']) ergibt {3: ['ich', 'wir'], 2: ['du']}. Ohne Object.groupBy.
Die Werte sind Listen. Beim ersten Wort einer Länge gibt es seine Liste noch nicht: Leg sie an, wenn die Länge noch nicht in groups steht.
Danach hängst du das Wort an: groups[length].push(word).
Zwei Klassen haben gezählt, welches Obst sie mögen. Schreib eine Funktion merge_counts(a, b), die beide Zählungen zu einer zusammenrechnet: merge_counts({'Apfel' => 3, 'Birne' => 1}, {'Apfel' => 2, 'Kiwi' => 4}) ergibt {'Apfel' => 5, 'Birne' => 1, 'Kiwi' => 4}. Die beiden Zählungen bleiben, wie sie sind.
Fang mit einer Kopie von a an, a.dup, und geh b durch.
Steht der Schlüssel aus b schon darin? result.fetch(key, 0) ist sein Zähler oder 0.
Zwei Klassen haben gezählt, welches Obst sie mögen. Schreib eine Funktion merge_counts(a, b), die beide Zählungen zu einer zusammenrechnet: merge_counts({'Apfel': 3, 'Birne': 1}, {'Apfel': 2, 'Kiwi': 4}) ergibt {'Apfel': 5, 'Birne': 1, 'Kiwi': 4}. Die beiden Zählungen bleiben, wie sie sind.
Fang mit einer Kopie von a an, dict(a), und geh b durch.
Steht der Schlüssel aus b schon darin? result.get(key, 0) ist sein Zähler oder 0.
Zwei Klassen haben gezählt, welches Obst sie mögen. Schreib eine Funktion mergeCounts(a, b), die beide Zählungen zu einer zusammenrechnet: mergeCounts({'Apfel': 3, 'Birne': 1}, {'Apfel': 2, 'Kiwi': 4}) ergibt {'Apfel': 5, 'Birne': 1, 'Kiwi': 4}. Die beiden Zählungen bleiben, wie sie sind.
Fang mit einer Kopie von a an, { ...a }, und geh b durch.
Steht der Schlüssel aus b schon darin? result[key] || 0 ist sein Zähler oder 0.
colors ordnet jedem Obst seine Farbe zu. Schreib eine Funktion invert(colors), die umgekehrt jeder Farbe die Liste ihrer Obstsorten zuordnet, in ihrer Reihenfolge: invert({'Kiwi' => 'grün', 'Banane' => 'gelb', 'Apfel' => 'grün'}) ergibt {'grün' => ['Kiwi', 'Apfel'], 'gelb' => ['Banane']}. Ohne invert und group_by.
Geh die Paare durch: Jetzt ist die Farbe der Schlüssel, und das Obst kommt in ihre Liste. Wie bei den Längen der Wörter.
colors ordnet jedem Obst seine Farbe zu. Schreib eine Funktion invert(colors), die umgekehrt jeder Farbe die Liste ihrer Obstsorten zuordnet, in ihrer Reihenfolge: invert({'Kiwi': 'grün', 'Banane': 'gelb', 'Apfel': 'grün'}) ergibt {'grün': ['Kiwi', 'Apfel'], 'gelb': ['Banane']}. Ohne eine fertige Funktion fürs Gruppieren.
Geh die Paare durch: Jetzt ist die Farbe der Schlüssel, und das Obst kommt in ihre Liste. Wie bei den Längen der Wörter.
colors ordnet jedem Obst seine Farbe zu. Schreib eine Funktion invert(colors), die umgekehrt jeder Farbe die Liste ihrer Obstsorten zuordnet, in ihrer Reihenfolge: invert({'Kiwi': 'grün', 'Banane': 'gelb', 'Apfel': 'grün'}) ergibt {'grün': ['Kiwi', 'Apfel'], 'gelb': ['Banane']}. Ohne Object.groupBy.
Geh die Paare durch: Jetzt ist die Farbe der Schlüssel, und das Obst kommt in ihre Liste. Wie bei den Längen der Wörter.
grades ist eine Liste von Noten, jede als Paar aus Fach und Note: [['Mathe', 2], ['Kunst', 1], ['Mathe', 3]]. Schreib eine Funktion averages(grades), die für jedes Fach den Durchschnitt seiner Noten zurückgibt: Für diese Liste ergibt es {'Mathe' => 2.5, 'Kunst' => 1.0}.
Für den Durchschnitt brauchst du je Fach zwei Zahlen: die Summe der Noten und wie viele es sind. Zwei Hashes, oder einer mit Paaren.
grades.each do |subject, grade| … end nimmt jedes Paar gleich auseinander. Am Ende teilst du je Fach die Summe durch die Anzahl.
grades ist eine Liste von Noten, jede als Paar aus Fach und Note: [['Mathe', 2], ['Kunst', 1], ['Mathe', 3]]. Schreib eine Funktion averages(grades), die für jedes Fach den Durchschnitt seiner Noten zurückgibt: Für diese Liste ergibt es {'Mathe': 2.5, 'Kunst': 1.0}.
Für den Durchschnitt brauchst du je Fach zwei Zahlen: die Summe der Noten und wie viele es sind. Zwei Dictionaries, oder eines mit Paaren.
for subject, grade in grades: nimmt jedes Paar gleich auseinander. Am Ende teilst du je Fach die Summe durch die Anzahl.
grades ist eine Liste von Noten, jede als Paar aus Fach und Note: [['Mathe', 2], ['Kunst', 1], ['Mathe', 3]]. Schreib eine Funktion averages(grades), die für jedes Fach den Durchschnitt seiner Noten zurückgibt: Für diese Liste ergibt es {'Mathe': 2.5, 'Kunst': 1}.
Für den Durchschnitt brauchst du je Fach zwei Zahlen: die Summe der Noten und wie viele es sind. Zwei Objekte, oder eines mit Paaren.
for (const [subject, grade] of grades) nimmt jedes Paar gleich auseinander. Am Ende teilst du je Fach die Summe durch die Anzahl.
Schreib eine Funktion first_repeat(numbers), die die erste Zahl zurückgibt, die zum zweiten Mal kommt: first_repeat([2, 5, 5, 2]) ergibt 5, denn die zweite 5 kommt vor der zweiten 2. Kommt keine Zahl zweimal, ist das Ergebnis nil. Die Prüfung gibt auch eine Liste mit 100 000 Zahlen: Geht es, ohne bei jeder Zahl die Liste von vorn durchzusehen?
Geh die Zahlen der Reihe nach durch und merk dir, welche schon da waren. Ist die Zahl schon dabei, hast du sie.
In einer Liste nachzusehen dauert bei 100 000 Zahlen lange. In einem Hash geht es sofort: seen.key?(number).
Schreib eine Funktion first_repeat(numbers), die die erste Zahl zurückgibt, die zum zweiten Mal kommt: first_repeat([2, 5, 5, 2]) ergibt 5, denn die zweite 5 kommt vor der zweiten 2. Kommt keine Zahl zweimal, ist das Ergebnis None. Die Prüfung gibt auch eine Liste mit 100 000 Zahlen: Geht es, ohne bei jeder Zahl die Liste von vorn durchzusehen?
Geh die Zahlen der Reihe nach durch und merk dir, welche schon da waren. Ist die Zahl schon dabei, hast du sie.
In einer Liste nachzusehen dauert bei 100 000 Zahlen lange. In einem Dictionary geht es sofort: number in seen.
Schreib eine Funktion firstRepeat(numbers), die die erste Zahl zurückgibt, die zum zweiten Mal kommt: firstRepeat([2, 5, 5, 2]) ergibt 5, denn die zweite 5 kommt vor der zweiten 2. Kommt keine Zahl zweimal, ist das Ergebnis null. Die Prüfung gibt auch eine Liste mit 100 000 Zahlen: Geht es, ohne bei jeder Zahl die Liste von vorn durchzusehen?
Geh die Zahlen der Reihe nach durch und merk dir, welche schon da waren. Ist die Zahl schon dabei, hast du sie.
In einer Liste nachzusehen dauert bei 100 000 Zahlen lange. In einem Objekt geht es sofort: number in seen.
Ein Extra für Schnelle: Die Seite ist ohne dieses Kapitel vollständig.
Zwei Katas, die nicht mitzählen.
Ein Cache hält die letzten Seiten bereit, die jemand aufgerufen hat, höchstens capacity viele. Wird eine Seite verlangt, die nicht darin ist, ist das ein Fehlschlag: Sie kommt hinein, und ist der Cache voll, fliegt die, die am längsten nicht mehr verlangt wurde (»least recently used«). Schreib lru_misses(capacity, requests), die die Fehlschläge zählt: lru_misses(2, ['a', 'b', 'a', 'c', 'b']) ergibt 4.
Eine Liste reicht: vorn die Seite, die am längsten nicht verlangt wurde, hinten die frischeste. Wird eine Seite verlangt, kommt sie nach hinten.
cache.delete(page) nimmt sie heraus, cache << page hängt sie hinten an, cache.shift wirft die vorderste hinaus.
Ein Cache hält die letzten Seiten bereit, die jemand aufgerufen hat, höchstens capacity viele. Wird eine Seite verlangt, die nicht darin ist, ist das ein Fehlschlag: Sie kommt hinein, und ist der Cache voll, fliegt die, die am längsten nicht mehr verlangt wurde (»least recently used«). Schreib lru_misses(capacity, requests), die die Fehlschläge zählt: lru_misses(2, ['a', 'b', 'a', 'c', 'b']) ergibt 4.
Eine Liste reicht: vorn die Seite, die am längsten nicht verlangt wurde, hinten die frischeste. Wird eine Seite verlangt, kommt sie nach hinten.
cache.remove(page) nimmt sie heraus, cache.append(page) hängt sie hinten an, cache.pop(0) wirft die vorderste hinaus.
Ein Cache hält die letzten Seiten bereit, die jemand aufgerufen hat, höchstens capacity viele. Wird eine Seite verlangt, die nicht darin ist, ist das ein Fehlschlag: Sie kommt hinein, und ist der Cache voll, fliegt die, die am längsten nicht mehr verlangt wurde (»least recently used«). Schreib lruMisses(capacity, requests), die die Fehlschläge zählt: lruMisses(2, ['a', 'b', 'a', 'c', 'b']) ergibt 4.
Eine Liste reicht: vorn die Seite, die am längsten nicht verlangt wurde, hinten die frischeste. Wird eine Seite verlangt, kommt sie nach hinten.
cache.splice(i, 1) nimmt sie heraus, cache.push(page) hängt sie hinten an, cache.shift() wirft die vorderste hinaus.
Schreib eine Funktion anagram_groups(words), die die Wörter in Gruppen von Anagrammen teilt, in der Reihenfolge, in der die erste jeder Gruppe vorkommt: anagram_groups(['lampe', 'regen', 'palme', 'ampel', 'gerne']) ergibt [['lampe', 'palme', 'ampel'], ['regen', 'gerne']]. Die Wörter sind klein geschrieben.
Was haben alle Anagramme gemeinsam? Ihre sortierten Buchstaben: aus 'palme' und 'ampel' wird beide Male 'aelmp'. Das ist ein guter Schlüssel.
Wie beim Gruppieren nach der Länge, nur mit diesem Schlüssel. groups.values sind am Ende die Listen.
Schreib eine Funktion anagram_groups(words), die die Wörter in Gruppen von Anagrammen teilt, in der Reihenfolge, in der die erste jeder Gruppe vorkommt: anagram_groups(['lampe', 'regen', 'palme', 'ampel', 'gerne']) ergibt [['lampe', 'palme', 'ampel'], ['regen', 'gerne']]. Die Wörter sind klein geschrieben.
Was haben alle Anagramme gemeinsam? Ihre sortierten Buchstaben: aus 'palme' und 'ampel' wird beide Male 'aelmp'. Das ist ein guter Schlüssel.
Wie beim Gruppieren nach der Länge, nur mit diesem Schlüssel. list(groups.values()) sind am Ende die Listen.
Schreib eine Funktion anagramGroups(words), die die Wörter in Gruppen von Anagrammen teilt, in der Reihenfolge, in der die erste jeder Gruppe vorkommt: anagramGroups(['lampe', 'regen', 'palme', 'ampel', 'gerne']) ergibt [['lampe', 'palme', 'ampel'], ['regen', 'gerne']]. Die Wörter sind klein geschrieben.
Was haben alle Anagramme gemeinsam? Ihre sortierten Buchstaben: aus 'palme' und 'ampel' wird beide Male 'aelmp'. Das ist ein guter Schlüssel.
Wie beim Gruppieren nach der Länge, nur mit diesem Schlüssel. Eine Map behält die Reihenfolge, in der die Schlüssel dazukommen; [...groups.values()] sind am Ende die Listen.