Entwicklung

Der Wichtel-Algorithmus

Auf Twitter habe ich es schon ein paar mal erwähnt: Ich bin gerade dabei eine Webseite / API zu programmieren mit der man wichteln kann. Derzeit ist das alles noch im frühen Beta Stadium aber ich denke das bekomme ich noch hin bis Weihnachten. Mehr dazu aber in einem späteren Post. Um alle ins Boot zu holen hier mal ein Auszug aus der Wikipedia:

Wichteln (in Norddeutschland und Skandinavien auch „Julklapp“ (reguläres Schwedisch für „Weihnachtsgeschenk“), sowie in Österreich regional auch „Engerl und Bengerl“ genannt, ist ein meist vorweihnachtlicher Brauch […]. Dabei wird durch zufällige Auswahl für jedes Gruppenmitglied ein anderes Gruppenmitglied bestimmt, von dem es dann beschenkt wird.

Ich vermute, die meisten kennen den Brauch. Wir werden dieses Jahr auch wieder wichteln und haben uns dazu einer Webseite bedient namens Wichtel-O-Mat. Man trägt alle Teilnehmer ein und bekommt dann eine E-Mail mit dem Namen der Person, die man beschenken darf. Programmiertechnisch ist das jetzt nichts besonderes, aber ich habe es für mich als Ansporn genommen um die Idee selber nachzuprogrammieren zu Übungszwecken.

Das Interessante an dem Projekt ist im Grunde der Algorithmus, wie die Namen den Leuten zu geordnet werden. Denn hier gibt es ein paar Bedingungen:

  1. Es dürfen nur Teilnehmer mitmachen, die auch eingewilligt haben.
  2. Keiner darf sich selber ziehen
  3. Jeder der teilnimmt …
    1. muss einen (und nur einen) Namen einer anderen Person bekommen (die man beschenken soll)
    2. wird von einer (und nur einer) anderen Person gezogen (keiner darf übrig bleiben)

Das ganze ist jetzt kein Hexenwerk und auch schnell gelöst. Ich habe es inzwischen implementiert. Aber bevor ich euch sage, wie ich es gemacht habe möchte ich, dass ihr selber nachdenkt. Wie würdet ihr das implementieren? Schreibt es in die Kommentare. Morgen um diese Zeit werde ich den Beitrag erweitern und euch sagen, wie ich es gemacht habe.

Mein Wichtel-Algorithmus

Für mich war das mal wieder so ein kleiner Teil Code, bei dem ich Hals über Kopf gleich rein gestiegen bin, weil ich dachte, kann ja nicht so schwer sein. Und erst beim Programmieren musste ich feststellen, dass ich das doch nicht sofort einfach runter programmieren kann. Also musste ich erstmal einen Schritt zurück gehen und überlegen.

Zu allererst wollte ich einen „komplizierten“ Algorithmus bauen, der aus der Liste Leute zieht und anderen zuordnet. Dabei müsste ich dann aber mehrere Dinge checken:

  1. Hat die Person ihre Einwilligung gegeben?
  2. Ist die Person noch nicht gezogen worden?
  3. Zieht die Person sich gerade selber?

Gerade der letzte Punkt hatte mich zum Nachdenken angeregt, denn was ist, wenn die letzte Person aus der Liste sich selber zieht? Es gibt ja keinen anderen mehr, den man ziehen könnte. D.h. ich könnte dann die vorletzte Person und die letzte tauschen oder ich beginne einfach von vorne. … Irgendwie ist das komisch und viel zu kompliziert.

Ich habe mich dann noch mal von meiner Idee verabschiedet und bin dann auf die selbe Idee wie Thorsten (siehe Kommentare) gekommen. Das einfachste wäre, jeder zieht den nächsten in der Liste und der Letzte zieht den ersten. Somit ist sichergestellt, dass jeder einen Wichte-Partner* hat und keiner geht leer aus.

* Wenn ich hier von Partner spreche, meine ich nicht, dass zwei Leute sich gegenseitig beschenken, sondern das Person A einen Wichtel-Partner B zugewiesen bekommt. Somit muss A ein Geschenk für B besorgen. B allerdings nicht für A.

1. Aussortieren

Der erste Punkt ist das filtern der Liste. Durch ein gegebenes Attribut kann ich einfach sehen, ob die Person eingewilligt hat. Ist der Check negativ fliegt die Person raus aus der Liste.

2. Mischen der Liste

Beim Programmieren gab es dann den Punkt wie ich denn sicherstellen könnte, dass jeder einen Namen bekommt, aber ohne dass der Oberwichtel, der der die Namen in die Liste einträgt, raus lesen kann wer wen ziehen wird. Die einfachste Lösung ist: Mischen. Ich bekomme die eingetragene Liste und mische sie einfach bevor ich die Namen zuweise. Somit ist die Reihenfolge nie ersichtlich für Außenstehende.

Ich habe mich am Schluss für den Fisher-Yates Shuffle Algorithmus entschieden. Ein schneller aber durchaus effektiver Shuffel Algorithmus.

3. Wichtel-Partner zuweisen

Jetzt gehe ich die Liste einmal durch und weise jedem den nächsten in der Liste als Partner zu. Der Letzte bekommt den Ersten in der Liste zugewiesen. Somit hat jeder eine Person, die ihm zugewiesen wurde und keiner geht leer aus.

4. Teilnehmer benachrichtigen

Der letzte Schritt ist dann lediglich die Benachrichtigung. Jeder Teilnehmer bekommt eine Mail mit dem Namen der soeben zugewiesenen Person.

Code

Hier ist mein JavaScript Code aus meinem AdonisJS Controller. Es gibt 3 Methoden (1 Generator, 2 Functions). * start() ist der Generator, der bei einem Request aufgerufen wird. Zuerst werden noch ein paar Checks gemacht und dann hole ich mir die Liste der Leute aus der Datenbank. Über die Filter Funktion werfe ich alle Leute raus, die nicht angewilligt haben und übergebe dann die Liste an findWichtelBuddy(). Hier wird als erstes die Liste gemischt mit shuffle() um im Anschluss die Partner zuzuweisen. Im Controller sende ich dann noch die Mails.

'use strict'

const Mail = use('Mail')
const _ = require('lodash')
const Group = use('App/Model/Group')
const Member = use('App/Model/Member')

class WichtelController {

  * start (request, response) {
    const isLoggedIn = yield request.auth.check()

    const data = request.only('group')

    if (!isLoggedIn || request.auth.user.id !== Number(data.group)) {
      return response.unauthorized({
        'status': 401,
        'message': 'Wrong token.',
      })
    }

    const group = yield Group
      .query()
      .where('id', data.group)
      .with('members')
      .first()

    // 0. Get list of members for group with provided ID
    const members = yield Member
      .query()
      .where('group_id', data.group)
      .fetch()

    // 1. Filter list. Keep only approved members
    let approved = _.filter(members.value(), function(m) {
      return (m.status === 'approved')
    });

    // At least 3 people are needed.
    if (approved.length < 3) {
      return response.forbidden({
        'status': 403,
        'message': 'Too few people approved. At least 3 members are needed to start.'
      })
    }

    // Step 2+3
    const assigned = this.findWichtelBuddy(approved)

    // 4. Send mail to members
    for (const member of assigned) {
      yield member.save()
      const buddy = yield Member.find(member.wichtel_id)
      const mailData = {
        name: member.name,
        buddy: buddy.name
      }
      
      yield Mail.send('emails.buddy', mailData, (message) => {
        message.to(member.email, member.name)
        message.from('no-reply@wichtel.me')
        message.subject('Your Wichtel-Buddy is ...')
      })
    }

    // Update status for group to know that the action started.
    group.status = 'started'
    yield group.save()

    response.ok({
      'status': 200,
      'message': 'Woho, our imps are on their way delivering the messages.'
    })

  }

  findWichtelBuddy (members) {
    // 2. shuffle list of approved members
    this.shuffle(members)

    // 3. Assign members
    let assigned = _.map(members, (m, i) => {
      if (i === members.length -1) {
        m.wichtel_id = members[0].id
      } else {
        m.wichtel_id = members[i+1].id
      }

      return m
    })

    // Return updated list
    return assigned
  }

  /**
  * Fisher-Yates Shuffle
  * https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
  */
  shuffle(array) {
    let counter = array.length;

    // While there are elements in the array
    while (counter > 0) {
      // Pick a random index
      let index = Math.floor(Math.random() * counter);

      // Decrease counter by 1
      counter--;

      // And swap the last element with it
      let temp = array[counter];
      array[counter] = array[index];
      array[index] = temp;
    }

    return array;
  }

}

module.exports = WichtelController

3 Kommentare zu “Der Wichtel-Algorithmus

  1. Spaßiger Blogeintrag, gefällt mir sehr. Hier ist meine Version:
    https://gist.github.com/nok/04a3c24ff5a65cecf6030bae6657e3e1

  2. Mein Algorithmus in „Pseudocode“:

    – Nimm alle eingetragenen Teilnehmer.
    – Beschränke auf die, die eingewilligt haben.
    – Diese Teilnehmer nach irgendeinem Verfahren randomisieren.
    – Jeder Teilnehmer beschenkt einfach den „Nächsten“ auf der Liste.
    – Der letzte Teilnehmer beschenkt den ersten auf der Liste.

    Fertig. 🙂

  3. Danke Throsten für den Typ, so geht das echt easy mit wenig Code von der Hand.
    HDGDL!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.