10
\$\begingroup\$

A secret santa gift exchange is a game where each player is randomly assigned a person to whom they anonymously give a gift. The algorithm is referred to as Derangement.

For example, given the following players:

Mohamad, Carolina, Sami, Tania, Ikram, José

A game may be:

Mohamad gets Sami
Carolina gets José
Sami gets Tania
Tania gets Mohamad
Ikram gets Carolina
José gets Ikram

The important rules are:

  1. A person can not be assigned to themselves.
  2. A person can only be assigned to another person once.
  3. Assignment must be random.

Implementation

This is my object oriented implementation. I do not like my random_player_for implementation. It seems procedural and the use of temporary flags seems like a code smell.

How would you improve this implementation?

class Derangement
  attr_reader :game

  # for convenience
  # PLAYERS = %w[Mohamad Carolina Sami Tania Jose Ikram Rabii Ahmad Kazem]

  def initialize(players)
    @players = players
    @santas = players.dup
    @game = {}
  end

  def solve
    @santas.each do |santa|
      @game[santa] = random_player_for(santa)
    end
  end

private

  def random_player_for(santa)
    found = false
    until found do
      player = @players.sample
      unless player == santa
        found = true
        @players.delete(player)
      end
    end
    player
  end
end
\$\endgroup\$
0

2 Answers 2

5
\$\begingroup\$

I'm a bit unsure about whether the question is about a game of Secret Santa or if it's actually about derangement, specifically. Derangement requires that no element can appear in its original position. But that's irrelevant for a game of Secret Santa, since there's no ordering to speak of.

Edit: As tokland rightly points out in the comments derangement is of course related to the game. I wasn't thinking it through.

For derangement, Rosetta Code has a Ruby implementation you might be able to use or learn from.

For a game of Secret Santa, though, the specs are pretty much as you summed up in your 3 rules (although #3 "Assignment must be random" is a bit difficult to define/verify.) So here, things can be simplified; you need not worry about derangement "by itself" as long as the rules are obeyed. For instance, you might simply do:

players = %w[Mohamad Carolina Sami Tania Ikram Jose].shuffle
players << players.first # repeat the first player

assignments = players.each_cons(2).to_a

which will give you an array of santa/gift-receiver pairs such as:

[["Carolina", "Ikram"],
 ["Ikram", "Mohamad"],
 ["Mohamad", "Jose"],
 ["Jose", "Tania"],
 ["Tania", "Sami"],
 ["Sami", "Carolina"]]

Alternatively, you can get the "Santa targets" for several rounds by doing something like

players = %w[Mohamad Carolina Sami Tania Ikram Jose].shuffle
assignments = players.each_with_index.map do |santa, index|
  others = players.rotate(index+1)[0...-1]
  [santa, others]
end

Which will give you something like

[["Tania", ["Mohamad", "Sami", "Ikram", "Carolina", "Jose"]],
 ["Mohamad", ["Sami", "Ikram", "Carolina", "Jose", "Tania"]],
 ["Sami", ["Ikram", "Carolina", "Jose", "Tania", "Mohamad"]],
 ["Ikram", ["Carolina", "Jose", "Tania", "Mohamad", "Sami"]],
 ["Carolina", ["Jose", "Tania", "Mohamad", "Sami", "Ikram"]],
 ["Jose", ["Tania", "Mohamad", "Sami", "Ikram", "Carolina"]]]

There's a pattern of course (if you've given Ikram a gift, next you'll be giving Carolina a gift, then José, etc.). But if it's Secret Santa, the players shouldn't be able to figure that out anyway unless they cheat (and if they do, well, all bets are off).

You could of course use Array#combination or Array#permutation to achieve similar results. I highly encourage you to check out all of the built-in array methods, and those included from the Enumerable module. There's a lot of good stuff there.

As for a more OOP approach, I wouldn't make a class called "Derangement". Derangement is a method. It's an action, an operation, a means of achieving a certain result or state - not something that is itself stateful.
The simple solution, given your code, is to rename you class to "Game" or something along those lines.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ @Flambino: AFAICS the Secret Santa game is 100% related to derangement, since persons.zip(persons.shuffle_with_derangement) is the solution to the problem. \$\endgroup\$
    – tokland
    Mar 24, 2014 at 10:50
  • 1
    \$\begingroup\$ @tokland Ah, you're right, of course. I'll update my answer - thanks! \$\endgroup\$
    – Flambino
    Mar 24, 2014 at 11:01
  • \$\begingroup\$ @tokland I don't understand something. Is shuffle_with_derangement a ruby method? I can't find it in the docs. \$\endgroup\$
    – Mohamad
    Mar 24, 2014 at 11:52
  • \$\begingroup\$ @Mohamad No, you must write Array#shuffle_with_derangement yourself :) It was just an example to show the relation (but you can actually implement it this way). \$\endgroup\$
    – tokland
    Mar 24, 2014 at 11:59
  • 1
    \$\begingroup\$ @Mohamad: Ruby has a Array#shuffle method, but of course it does not enforce that all elements end up in different positions as you need. But I think this is correct path for the abstraction (adding a generic abstraction to Array) instead of creating a custom object. \$\endgroup\$
    – tokland
    Mar 24, 2014 at 12:17
2
\$\begingroup\$

Your random_player_for() method can be better expressed as:

  def random_player_for(santa)
    loop do
      player = @players.sample
      if player != santa
        @players.delete(player)
        return player
      end
    end
  end

However, you should recognize that there is a possibility for an infinite loop, if all other players have already been assigned to each other and there is only one loner left.

The following method would be an improvement in two ways:

  • Predictable running time
  • Detection of a loner
  def random_player_for(players, santa)
    others = players.reject { |player| player == santa }
    if others.empty?
      throw LonerException.new(santa)
    else
      return players.delete(others.sample)
    end
  end

Then, if solve() catches the LonerException, it could retry all the assignments from scratch.

  def solve
    begin
      @game = {}
      players = @players.dup
      @santas.each { |santa| @game[santa] = random_player_for(players, santa) }
    rescue LonerException
      retry
    end
  end

Better yet, modify random_player_for() such that when there are only two players left, and at least one of them has not yet been given an assignment as a Santa, take care to assign them in such a way that there is no loner.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you. I maybe wrong, but I can not see a scenario where a loner is left. The number of santas should always be equal to the number of players. So every santa will be matched with player other than himself. How can a loner be left over? \$\endgroup\$
    – Mohamad
    Mar 24, 2014 at 4:34
  • 1
    \$\begingroup\$ Take your example: { Mohamad, Carolina, Sami, Tania, Ikram, José }. Let's say the first five form a cycle: Mohamad → Carolina, Carolina → Sami, Sami → Tania, Tania → Ikram, Ikram → Mohamad. Poor José is a loner and would have to be assigned to himself. \$\endgroup\$ Mar 24, 2014 at 6:14
  • 1
    \$\begingroup\$ I see. But doesn't your implementation of the random_player_for leave the chance of duplicate assignments? No where I see we are modifying the player array. So what's to stop the same player being picked on another iteration? Perhaps we should change return others.sample to players.delete(others.sample)? \$\endgroup\$
    – Mohamad
    Mar 24, 2014 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.