MyInnoQBlog

Da ich grade dabei bin Ruby zu lernen, möchte ich mal ein kleines Programm zeigen und Probleme auflisten, die ich damit hatte.

Auf rubyquiz.com gibt es sehr viele Aufgaben, die man mit Ruby lösen kann und soll. Ich kann diese Seite nur empfehlen. Von dieser stammt auch das folgende Problem: Secret Santas.

Zu deutsch würde man das wohl als "Wichteln" bezeichnen. So werden gegenseitig zufällig Wichtelpartner zugeordnet. Die Einschränkung ist, dass Personen aus der selben Familie nicht gegenseitig zugeteilt werden dürfen.

Nachdem ich das Grundgerüst relativ schnell stehen hatte und zumindest teilweise das Problem mit den gleichen Nachnamen gelöst hatte, bestand am Ende das Problem, dass manchmal noch eine Person zugeteilt werden musste, diese aber den gleichen Nachnamen hatte, wie die Person, der noch der Wichtelpartner fehlte.

So habe ich mich auf die Suche nach einer Lösung gemacht, und meinte das Problem mathematisch lösen zu können/müssen (Stichwort: Permutationen).

Nachdem ich absolut nicht auf den grünen Zweig gekommen bin, habe ich dann doch mal in die Lösung geguckt. Eine elegante Lösung ist der Hill Climbing Algorithmus. Hier werden die Wichtelpartner zunächst einfach zufällig zugewiesen und am Ende wird die Liste der Personen mit ihren Partnern durchgegangen und ggf. falsche Übereinstimmungen (gleicher Nachname) durch vertauschen der jeweiligen Partner gelöst.

Also war's doch etwas unkomplizierter, als ich es mir vorher vorgestellt hatte. Meine Lösung:

[Update:] Bei der Suche nach geeigneten Kandidaten für einen Tausch der Partner, muss auf jeden Fall noch folgender Ausdruck nach dem && hinzugefügt werden:

people.select { |p| p.personal_santa.can_be_santa_of?(person)
&& person.personal_santa.can_be_santa_of?(p) }

Ansonsten kann es trotzdem vorkommen, dass falsche Wichtelpartner zugeordnet werden.

class Person
  attr_writer :personal_santa
  attr_reader :firstname, :lastname, :email, :personal_santa

  def initialize (firstname, lastname, email)
    @firstname = firstname
    @lastname = lastname
    @email = email
  end

  def can_be_santa_of?(other)
    @lastname != other.lastname
  end
end

#switches the two personal_santas of the passed people
def swap_santas (person1, person2)
  temp = person1.personal_santa
  person1.personal_santa = person2.personal_santa
  person2.personal_santa = temp  
end

#assigns each person his secret santa
def assign_santas(people, santas)
  people.each { |person| person.personal_santa = santas.delete_at
(rand(santas.length)) } #assigns santas randomly
  people.each { |person| 
    unless person.personal_santa.can_be_santa_of? person
      #finds possible candidates for a swap
      candidates = people.select { |p|
p.personal_santa.can_be_santa_of?(person)
&& person.personal_santa.can_be_santa_of?(p) }
      swap_santas(person, candidates[rand(candidates.length)])
    end
    }
end

person1 = Person.new("Daniel","Pietzsch","[email protected]")
person2 = Person.new("...") #parameter in the above format
person3 = Person.new("...")
person4 = Person.new("...")
person5 = Person.new("...")
person6 = Person.new("...")

people = [person1, person2, person3, person4, person5, person6]
santas = Array.new(people) #Copy of the people array

assign_santas(people, santas) #assigns each person his secret santa

#output
people.each {|person| puts "#{person.firstname} #{person.lastname}:
<#{person.email}>\nPersonal Santa: #{person.personal_santa.firstname}
#{person.personal_santa.lastname}\n\n"}