Secret Santa with Groups on Swift

Question

I am working on an special version of Secret Santa with internal sub-groups.

Typical Secret Santa (SS) requirements:

• Cannot be assigned to themselves
• Should be random
• Every participant should be assigned to someone
• Every participant should have someone assigned to

Special requirements; there are subgroups that should be taken into consideration:

• Reduce participants assigned to someone into their same group as much as possible (none if possible)

Implementation

I am new to Swift, I am working on a playground. Let's first consider the problems to solve:

Problems to consider

For one group (normal SS)

Let's assume a 3 people group

1->2
2->1
3->?

In that case there is no possible person for 3 to give to.

For multiple groups

Assume these 3 groups group-participant:

[1-1,1-2]
[2-1]
[3-1]

This could be assigned like this

2-1 -> 3-1
3-1 -> 2-1
1-1 -> 1->2
1-2 -> 1->1

Which is not a desired outcome.

Algorithm

Pick random participant p from all the possible participants. Also save the first p apart.

if p is not from the largest group
    r is a random element from the largest group
else if p is from the largest group and there are multiple non-empty groups
    r is a random element from the any other group
else if p is not from the largest group and is from the only remaining group
    r is a random element from its group that it is not p
p gives present to r

Now remove p from the groups and repeat the same but make p=r until it is there are no more participants. The last one gives to the first one and the shuffle is complete.

Code

            class Participant: CustomStringConvertible {
        var name = "noname"
        var contact = "nocontact"
        var giveTo:Participant?
        init(name:String,contact:String){
            self.name = name
            self.contact = contact
        }
        var description: String {return name + ((giveTo==nil) ?"":"->\(giveTo!.name)")}
    }

    class Group: CustomDebugStringConvertible {
        static var allGroups:[Group]=[]
        static var counter = 0
        var participants:[Participant]=[]
        var name = "G-x"
        var description:String {return name}
        var debugDescription:String {return name}
        init(participants:[Participant]){
            self.participants=participants
            name = "G-\(Group.counter++)"
            Group.allGroups.append(self)
            Group.allGroups = Group.sortGroups(Group.allGroups)
        }

        func size()->Int{return self.participants.count}

        func getRandParticipant()->Participant{
            let p = participants[Int(arc4random_uniform(UInt32(participants.count)))]
            return p
        }

        func remove(p:Participant)->Bool{
            let originalIndex = participants.count
            participants = participants.filter() { $0.name != p.name }
            return originalIndex != participants.count
        }

        static func sortGroups(g:[Group])->[Group]{
            //remove groups with size = 0
            let rg = g.filter() {return $0.size()>0}
            //sort
            return rg.sort() {return $0.0.size()>$0.1.size()}
        }

        static func getRandGroup(groups:[Group])->Group{
            return groups[Int(arc4random_uniform(UInt32(groups.count)))]
        }

        static func removeFromGroups(groups:[Group],p:Participant)->[Group]{
            for g in groups{
                if(g.remove(p)){
                    break;
                }
            }
            return sortGroups(groups)
        }

        static func getPairs(groups:[Group])->[Participant]{
            var groups2consume = groups
            var giverGroup = getRandGroup(groups2consume)
            var searchIn:[Group]
            var giver:Participant = giverGroup.getRandParticipant()
            let first = giver
            var returnArray:[Participant] = []
            while(groups2consume.count>0){
                let indexO = groups2consume.indexOf() {$0.name==giverGroup.name}
                if let index = indexO{
                    if (index>0){
                        //if giverGroup is 0 it means it is in the largest group
                        searchIn = [groups2consume[0]]
                    }else if groups2consume.count>1{
                        //if giverGroup is not 0 and the count is >0 then there are smaller groups
                        searchIn = groups2consume
                        searchIn.removeFirst()
                    }else{
                        //there is only one group left
                        searchIn = groups2consume
                        searchIn[0].remove(giver)
                    }
                    if searchIn[0].participants.count>0{
                        let receiverGroup = getRandGroup(searchIn)
                        let receiver = receiverGroup.getRandParticipant()
                        groups2consume = removeFromGroups(groups2consume, p: giver)
                        giver.giveTo=receiver
                        returnArray.append(giver)
                        giverGroup = receiverGroup
                        giver = receiver
                    }else{
                        groups2consume = removeFromGroups(groups2consume, p: giver)
                    }
                }else{
                    break
                }
            }
            giver.giveTo=first
            returnArray.append(giver)
            return returnArray
        }
    }

Test

    Group(participants:[
        Participant(name: "p🍎1", contact: "n🍎1"),
        Participant(name: "p🍎2", contact: "n🍎2"),
        Participant(name: "p🍎3", contact: "n🍎3"),
        Participant(name: "p🍎4", contact: "n🍎4"),
        Participant(name: "p🍎5", contact: "n🍎5")])

    Group(participants:[
        Participant(name: "p🍊1", contact: "n🍊1")])


    Group(participants:[
        Participant(name: "p🍒1", contact: "n🍒1"),
        Participant(name: "p🍒2", contact: "n🍒2")])

    Group.allGroups

    let pairs = Group.getPairs(Group.allGroups);
    print("pairs(\(pairs.count))  done \(pairs)")

Output

pairs(8)  done [p🍎1->p🍊1, p🍊1->p🍎4, p🍎4->p🍒2, p🍒2->p🍎2, p🍎2->p🍒1, p🍒1->p🍎3, p🍎3->p🍎5, p🍎5->p🍎1]

Answer 1

Your code works – as far as I can see – correctly. I cannot judge the fairness of the algorithm itself, but I have some suggestions concerning the implementation.

My first point of criticism is the use of the static Group property allGroups:

• Each created Group instance is implicitly appended to allGroups which is not obvious to the user of your code. The call Group(participants:[...]) creates a group and discards the result (which gives a compiler warning), so the initializer is called purely for its side effect.
• It makes the code less reusable. You cannot create an independent second set of groups.

I would suggest to build an array of groups explicitly:

let g1 = Group(participants:[...])
let g2 = Group(participants:[...])
let g3 = Group(participants:[...])
let allGroups = [g1, g2, g3]

Similarly, the static Group property counter is used to assign consecutive names to the each created group. This is acceptable, but why not create each group with an explicit name (as you already do for the participants)?

let g1 = Group(name: "G1", participants:[...])
let g2 = Group(name: "G2", participants:[...])
let g3 = Group(name: "G3", participants:[...])

There is too much logic in the Group class. In fact all the static methods are used for the "Secret Santa" algorithm, and do not use any state of the Group class. I suggest to create a separate class for that purpose:

let g1 = Group(name: "G1", participants:[...])
let g2 = Group(name: "G2", participants:[...])
let g3 = Group(name: "G3", participants:[...])

let santa = SecretSanta(groups: [g1, g2, g3])
let pairs = santa.assignPairs()
print(pairs)

Now lets have a look at the Participant class. There is no need to assign default initial values "noname", "nocontact" because both properties are assigned to in the init method. Moreover, name and contact do never change, so they can be constant properties with let:

class Participant {
    let name : String
    let contact : String
    var giveTo : Participant?

    init(name: String, contact: String) {
        self.name = name
        self.contact = contact
    }
}

For better structuring of the code, protocol implementations such as CustomStringConvertible can be written as an extension. Testing against nil and implicit unwrapping should be avoided in favor of optional binding:

extension Participant: CustomStringConvertible {
    var description: String {
        var desc = name
        if let receiver = giveTo {
            desc += " -> " + receiver.name
        }
        return desc
    }
}

or more compactly using the Optional.map() method:

extension Participant: CustomStringConvertible {
    var description : String {
        return name + (giveTo.map { " -> " + $0.name } ?? "")
    }
}

In the remove() method of Group the name of the participant is used to identify it in an array. This is error-prone because it relies on unique names. A better solution is to implement the Equatable protocol, so that participants can be compared with ==. Since Participant is a class, i.e. a reference type, this can be done with the "identical-to" operator ===, i.e. only identical instances are considered equal:

extension Participant : Equatable { }

func ==(lhs : Participant, rhs : Participant) -> Bool {
    return lhs === rhs
}

Now a simple participants.indexOf(p) can be used to find a participant in an array.

The same suggestions apply to the Group class. If we remove the static properties and methods, this is what it could look like:

class Group {

    let name : String
    var participants: [Participant]

    init(name: String, participants: [Participant]) {
        self.name = name
        self.participants = participants
    }

    var size : Int {
        return participants.count
    }

    func randomParticipant() -> Participant {
        precondition(participants.count > 0, "participants array is empty")
        return participants[Int(arc4random_uniform(UInt32(size)))]
    }

    func removeParticipant(participant : Participant) {
        guard let index = participants.indexOf(participant) else {
            fatalError("participant not found in group")
        }
        participants.removeAtIndex(index)
    }
}

extension Group : CustomStringConvertible {

    var description : String { return name }
}

extension Group : Equatable { }

func ==(lhs : Group, rhs : Group) -> Bool {
    return lhs === rhs
}

• I have made size a computed property instead of a function, similar to count for arrays or length for strings.
• In getRandParticipant() I have removed the "get" prefix which should not be used. In addition, a precondition is added to detect programming errors.
• remove() is renamed to removeParticipant() and expects that the participant is present in the array. Instead of filtering the array, indexOf and removeAtIndex are used as a small optimization.

The remaining logic is moved to a SecretSanta class:

class SecretSanta {

    var remainingGroups : [Group]

    init(groups : [Group]) {
        // Make a copy of the group list:
        self.remainingGroups = groups.map { Group(name: $0.name, participants: $0.participants) }
    }

    // ....

    func assignPairs() -> [Participant] { ... }
}

The init method makes a copy of all groups, so that the algorithm can freely remove participants without modifying the original groups.

Your

static func sortGroups(g:[Group])->[Group]
static func getRandGroup(groups:[Group])->Group

methods become instance methods without parameters which operate directly on the remainingGroups property:

func randomGroup() -> Group {
    precondition(remainingGroups.count > 0, "groups array is empty")
    return remainingGroups[Int(arc4random_uniform(UInt32(remainingGroups.count)))]
}

func sortGroups() {
    // Remove groups without participants:
    remainingGroups = remainingGroups.filter { $0.size > 0 }
    // Sort by number of participants in decreasing order:
    remainingGroups.sortInPlace { $1.size < $0.size }
}

Note that you can omit the return statement in a single-expression closure.

Your

 static func removeFromGroups(groups:[Group],p:Participant)->[Group]

is not needed anymore. At each point in the algorithm, it is known to which group a participant belongs, so there is no need to search it in a group array. Also sorting the groups from within that method is confusing.

Using all that, the main Secret Santa method can be written as

func assignPairs() -> [Participant] {

    var sortedParticipants : [Participant] = []
    sortGroups()

    var giverGroup = randomGroup()
    var giver = giverGroup.randomParticipant()
    let firstGiver = giver

    while true {
        sortedParticipants.append(giver)
        giverGroup.removeParticipant(giver)

        guard let groupIndex = remainingGroups.indexOf(giverGroup) else {
            fatalError("group not found")
        }

        // Determine destination group:
        var receiverGroup : Group
        if groupIndex > 0 {
            // giver is not from the largest group(0)
            receiverGroup = remainingGroups[0]
        } else if remainingGroups.count > 1 {
            // giver is from the largest group(0), there is at least one other group
            repeat {
                receiverGroup = randomGroup()
            } while receiverGroup == giverGroup
        } else if remainingGroups[0].size > 0 {
            // There is only one group, but at least one receiver left
            receiverGroup = remainingGroups[0]
        } else {
            // This was the last giver
            giver.giveTo = firstGiver
            break
        }

        // Determine receiver in destination group and assign:
        let receiver = receiverGroup.randomParticipant()
        giver.giveTo = receiver

        // Prepare for next round:
        sortGroups()
        giverGroup = receiverGroup
        giver = receiver
    }

    return sortedParticipants
}

• I have called it assignPairs because it modifies the participants. A better name is surely possible.
• I have tried to write the code in a way that I understand it :)
• Removing the current "giver" from its group early in the loop makes things a little bit easier later.
• The extra groups array searchIn is not needed if we accept that in one case, several calls to randomGroup() are necessary. In the worst case (only 2 groups left) the average number of calls is 2.

• In your code, at

      let indexO = groups2consume.indexOf() {$0.name==giverGroup.name}
  

  index0 is expected to be non-nil. It is better to abort with an error if that is no satisfied (to detect programming errors early) instead of "silently" breaking from the loop. Note also that

      remainingGroups.indexOf(giverGroup)
  

  takes advantage of the Equatable protocol which we implemented for Group, and does not rely on unique names anymore.

More suggestions:

• Remove the giveTo property from Participants to make the instances immutable, and return a list of pairs (e.g. tuples) instead.
• Add a check that the same participant is not added to more that one group (and throw an error if that happens). I did not check how that situation is handled in your code or my modification, but I don't expect it to work correctly.
• More whitespace – at least around operators and {} code blocks.