kasulksBLOG

Codewars Lösung | Help Suzuki complete his chores!

coden
Codewars. Achieve mastery through challenge.
Daniel Kaser|8. Januar 2024
3 min.

Inhalt

  1. Die Fakten
  2. Beschreibung
  3. Lösung
    1. Pseudo-Code
    2. Code
  4. Feedback

Die Fakten:

Plattform:codewars.com
Name:Help Suzuki complete his chores!
Level:7 kyu
Sprache:TypeScript

Beschreibung:

Suzuki has a long list of chores required to keep the monastery in good order. Each chore can be completed independently of the others and assigned to any student. Knowing there will always be an even number of chores and that the number of students isn't limited, Suzuki needs to assign two chores to each student in a way which minimizes the total duration of the day's work.

For example, with the list of chores [1, 5, 2, 8, 4, 9, 6, 4, 2, 2, 2, 9], he'll need 6 students whose total workload will be: [7, 8, 8, 10, 10, 11] (as for [5+2, 4+4, 6+2, 8+2, 1+9, 9+2]). In this case, the maximal workload is minimized to 11 (=9+2. Keep in mind two chores must be assigned to each student involved).

Input/output

  • Input: 10 ≤ chores length ≤ 30, chores length is always even.
  • Output: array of workloads, in ascending order.

Please also try the other Kata in this series..

Quelle: codewars.com

Lösung

Pseudo-Code

Wie immer gibt's reichlich Varianten, hier ist eine meiner.

Erst die Lösungsschritte in Pseudo-Code. Los geht’s:

Lösungsschritte
Schritt 1

Um die Gesamtdauer von Suzukis Arbeit zu minimieren, müssen wir immer die jeweils längste verbleibende Aufgabe mit der jeweils kürzesten verbleibenden Aufgabe kombinieren.

Schritt 2

Richtig! D.h. als Erstes sollten wir das Input-Array sortieren.

Schritt 3

Beim Sortieren denken wir daran, dass JavaScripts Standard-Sortierfunktion das Ursprungs-Array mutiert, d.h. verändert.

Schritt 4

Als nächstes loopen wir durch das Array. In diesem Fall reicht es, wenn wir nur durch das halbe Array loopen.

Schritt 5

Jetzt können wir die erste und die letzte Zahl addieren. Dann die zweite und die vorletzte, die dritte und die drittletzte usw...

Code

Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:

Lösungsschritte
Als Erstes vergewissern wir uns, dass uns der Code-Editor anschreit, sollten wir am Ende das return vergessen. Wir legen den return-Wert unserer Funktion auf ein Array aus Zahlen fest:
export function choreAssignment(chores: number[]): number[] {
Dann sortieren wir das Input Array. Um mögliche Sideeffects zu vermeiden, erstelle ich vorher eine Kopie der Daten:
const sortedChores = [...chores].sort((a, b) => a - b);
Jetzt wird geloopt. Bis zur Hälfte des Arrays:
for (let i = 0; i < chores.length / 2; i++) {
Um den Code lesbarer zu machen, speichere ich das i-te Element und das dazugehörige i-letzte Element in einer Variablen ab:
const shortChore = sortedChores[i];
const longChore = sortedChores[sortedChores.length - 1 - i];
Jetzt noch Workload berechnen:
const currWorkload = shortChore + longChore;
Und das aktuelle Ergebnis zu einem Array hinzufuegen:
workloads.push(currWorkload);
Jetzt nochmal Workloads sortieren und returnen:
return workloads.sort((a, b) => a - b);
Voilá! 💪

Fragen?

Komplettlösung
export function choreAssignment(chores: number[]): number[] {
  const sortedChores = [...chores].sort((a, b) => a - b);
  const workloads: number[] = [];

  for (let i = 0; i < chores.length / 2; i++) {
    const shortChore = sortedChores[i];
    const longChore = sortedChores[sortedChores.length - 1 - i];

    const currWorkload = shortChore + longChore;

    workloads.push(currWorkload);
  }

  return workloads.sort((a, b) => a - b);
}

Feedback

Schreib mir!