(Finished in only 589 lines of code, not including another 420 lines of test code!)
The emailing part was no problem: to send anonymous emails (rather than logging into a server with credentials and blugh!), I created a free account at SMTP2GO.com and simply executed this JavaScript:
var xhr = new XMLHttpRequest();
xhr.onreadystatechange = function()
{
if (xhr.readyState == XMLHttpRequest.DONE)
{
printLine("Done!");
printLine("Status: " + xhr.status);
printLine("Response text:");
printLine(xhr.responseText);
printLine();
printLine();
}
}
xhr.open("POST", "https://api.smtp2go.com/v3/email/send", false);
xhr.setRequestHeader("Content-Type", "application/json");
xhr.send(JSON.stringify(
{
"api_key": apiKey,
"sender": sender,
"to": [receiver],
"subject": subject,
"text_body": "Your assigned person: whomever\n\nGift wisely!"
}));
Simple enough! (Shout out to them, by the way, for giving a free 1,000 emails per month instead of like 10.)Here's where it started to get difficult: there were certain rules that I had to follow.
The first was that nobody could get assigned themselves (duh). So if we have 3 persons: A, B, and C, A cannot be assigned to A!
The second was that everyone had to be assigned to someone unique (or, another way of putting it: everyone had to be an assignee for someone else). For example, with A, B, and C, if A is randomly assigned to B, then B cannot then be randomly assigned to A, because that means that C is not going to receive a gift and either A or B will get two gifts! I will algebraize this as follows:
(First, the situation.)
A=>BC
B=>AC
C=>AB
(Then, the random assignments.)
A=>B
B=>A
(Finally, the conclusion.)
C=>C!
Now normally, I would have solved a problem like this in one of two ways, neither of which will work here:
- Simply create a cycle chain like so: A=>B=>C or C=>B=>A. The problem with this is that it is extraordinarily predictable, which lacks excitement and surprise, and it does not solve the 3rd rule, which I will mention shortly.
- Randomly assign everyone a unique person, using a list of diminishing possibilities: every time a person is assigned to someone, remove that person from the list. Then, if the last person is assigned to themselves, simply pick another person at random and swap their assignments. This also does not solve the 3rd rule.
So, what is this 3rd rule that makes these solutions insufficient? Well, there just so happens to be a few married persons in my family (and a few not). They have stated that they do not want to be assigned to their spouse! (I guess they just get tired of giving each other gifts or something. :) ) This means that no longer is every person compatible with every other person besides themselves.
Thus, there are many persons for whom if their assignments were to be chained together (#1) or swapped out (#2), this process could need to be repeated numerous times (plus it's still just an improper solution)!
Ugh! So how do we get around this? What is the right way to solve it? Well, after analyzing the situation, I noticed three things.
Firstly, as should be obvious, we want to always assign to the person with the least number of persons available to be assigned to them and/or the least number of persons that they themselves can be assigned to.
Secondly, I noticed that if there are X number of persons who are all assigned the same Y other persons (no more, no less), and, if X == Y, then one of these persons must be evaluated immediately.
Now that may sound complex, but the simplest case is a very obvious one. Consider:
A=>B
B=>AC
C=>AB
Obviously A must be evaluated first here, and it satisfies the rule: there are X number of persons (namely, 1: A) who are all assigned the same Y number of other persons (namely, 1: B), and X (1) == Y (1).
Here's a more complicated example:
A=>CD
B=>CD
C=>AB
D=>AC
In this case, there are X number of persons (namely, 2: A and B) who are all assigned the same Y number of other persons (namely, 2: C and D), and X (2) == Y (2).
Note that with C and D, each of their X == 1 (they are not equivalent to each other) and their Y == 2. Since Y > X, this means that they still have some leeway and do not have to be assigned immediately. A and B can be assigned first, then the other of A or B would take the remaining person, and lastly C and D can take the leftovers.
If it is ever the case that Y < X, by the way (that is, fewer duplicate assignees than can be assigned to), this means that the problem (or what's left of it) is impossible to solve.
Now, you might be thinking, "Since A and B have to be assigned to C or D, that means that D cannot be assigned to C and C must be assigned to B." This is correct, but what you are essentially doing is thinking ahead, e.g.:
Random assignment:
A=>C or D
B=>C or D
Conclusion:
D=>A
C=>B
This forward thinking is unnecessary, because, so long as the rules are all followed, such process of elimination will automatically work itself out.
That was the first two things I noticed. Now why do we need a third? Well, there are actually two things we have to watch out for:
- Running out of persons that can be assignee's of any particular person (e.g. only Jake or Bill can be Bob's assignee (who he gifts to)).
- Running out of persons that can be assigned to give to any other particular persons (e.g. only Jake and Bill can have Bob as their assignee, and nobody else (can give their gifts to Bob)).
A=>CD
B=>ACD
C=>AD
D=>AB
Now, at first glance, you might be thinking that it doesn't matter which person has their assignee determined first: A, C, or D, since they all have only 2 possible assignees. This is not the case. Let's turn it around - that is, determine which persons can possibly be assigned to a particular person:
A<=BCD
B<=D
C<=AB
D<= ABC
Now things become a lot clearer! (Though we still need both directions for full clarity.) Obviously D must be assigned to B, because it is the only one that can do so. Then, either A or C should be decided next:
A=>CD
B=>ACD
C=>AD
D=>B
A<=BC
B<=D
C<=AB
D<= ABC
We'll call the former notation "forwards" and the latter notation "backwards".
So now, all we have to do is combine all three of the above, and we can ensure that whatever random assignments are made maintain a viable set of possibilities that follow! Quick recap:
Rules:
- No self-assignments.
- All persons must have unique assignments (all persons must be assignees of someone else).
- Not all persons can be assigned to all other persons.
- Always assign to the person with the least number of available options first.
- If X number of persons all have the exact same Y other persons and X == Y, then these must be evaluated immediately.
- Examine both the forwards and backwards perspectives when determining who has the least number of available options.
- This is not at all my prime code. It is a very rough prototype that I didn't have the time nor need to improve upon. It does have some comments throughout though.
- JavaScript is great for prototyping, but when you need to use heavy arrays and/or objects, as was needed here, it's terrible unless you actually take the time to structure it in OOP fashion. I did not, because I was in a rush to get this done. So you will undoubtedly have great difficulty understanding why I used two different types of for loops and various odd usages of square brackets and periods...
- This is not at all efficient code. There is severe potential to increase its efficiency, and I am well aware of that. Also, if speed were a major concern, I would use a different language like c++. JavaScript was nice and hacky though (good for prototyping), and had easy access to sending SMTP emails.
- I do not have 100% confidence that this algorithm will work in all cases. I tried it a good number of times though and it succeeded every time, so... Good enough. :)
- I used "bananakins" and "bananakin" throughout to refer to family members (just because I can and I do what I want); this is a play on words ("kin"), and it originally stems from a meme regarding Anakin Skywalker from Star Wars:
Alright, alright, the code already! I'm not even going to pretend like this code will fit in the blog. So, here's a raw text link, and here's an HTML link (<= If you wish to be entertained, click the HTML link, scroll down, and refresh the page (F5) a few times, to see it generate new solution sets).
But wait, there's more!
So I was curious to see how it would perform (since it's so inefficient and far from being prime code) if I had 100 people who were all participating together. I modified it, made 100 bananakins, could definitely have made them a lot more incompatible with each other but that would take too long, and here's what I got - final output:
- Choice: a16 => c6
Possible recipients of:
a => ["d2"]
b => ["b11"]
c => ["d11"]
d => ["f5"]
e => ["c"]
f => ["e11"]
a1 => ["e6"]
b1 => ["f11"]
c1 => ["c3"]
d1 => ["d5"]
e1 => ["a16"]
f1 => ["b3"]
a2 => ["a12"]
b2 => ["f6"]
c2 => ["d"]
d2 => ["c1"]
e2 => ["c9"]
f2 => ["b15"]
a3 => ["e"]
b3 => ["a8"]
c3 => ["d8"]
d3 => ["e2"]
e3 => ["f7"]
f3 => ["b"]
a4 => ["d6"]
b4 => ["f3"]
c4 => ["b4"]
d4 => ["a10"]
e4 => ["e7"]
f4 => ["b13"]
a5 => ["d13"]
b5 => ["d9"]
c5 => ["a6"]
d5 => ["e5"]
e5 => ["f2"]
f5 => ["c14"]
a6 => ["e15"]
b6 => ["c11"]
c6 => ["b7"]
d6 => ["e4"]
e6 => ["e8"]
f6 => ["f10"]
a7 => ["c13"]
b7 => ["d7"]
c7 => ["c15"]
d7 => ["a14"]
e7 => ["b10"]
f7 => ["b14"]
a8 => ["e10"]
b8 => ["d14"]
c8 => ["a15"]
d8 => ["a9"]
e8 => ["e14"]
f8 => ["e12"]
a9 => ["b12"]
b9 => ["b8"]
c9 => ["c16"]
d9 => ["b2"]
e9 => ["a13"]
f9 => ["a1"]
a10 => ["b1"]
b10 => ["e13"]
c10 => ["f12"]
d10 => ["f15"]
e10 => ["d1"]
f10 => ["c2"]
a11 => ["b16"]
b11 => ["f1"]
c11 => ["c4"]
d11 => ["a4"]
e11 => ["c8"]
f11 => ["d15"]
a12 => ["a"]
b12 => ["c5"]
c12 => ["e9"]
d12 => ["d4"]
e12 => ["a3"]
f12 => ["d16"]
a13 => ["f4"]
b13 => ["b5"]
c13 => ["e3"]
d13 => ["d3"]
e13 => ["b6"]
f13 => ["b9"]
a14 => ["a5"]
b14 => ["f9"]
c14 => ["f14"]
d14 => ["c7"]
e14 => ["f8"]
f14 => ["a11"]
a15 => ["a2"]
b15 => ["f13"]
c15 => ["d12"]
d15 => ["c12"]
e15 => ["a7"]
f15 => ["e1"]
a16 => ["c6"]
b16 => ["d10"]
c16 => ["f"]
d16 => ["c10"]
Possible givers to:
a <= ["a12"]
b <= ["f3"]
c <= ["e"]
d <= ["c2"]
e <= ["a3"]
f <= ["c16"]
a1 <= ["f9"]
b1 <= ["a10"]
c1 <= ["d2"]
d1 <= ["e10"]
e1 <= ["f15"]
f1 <= ["b11"]
a2 <= ["a15"]
b2 <= ["d9"]
c2 <= ["f10"]
d2 <= ["a"]
e2 <= ["d3"]
f2 <= ["e5"]
a3 <= ["e12"]
b3 <= ["f1"]
c3 <= ["c1"]
d3 <= ["d13"]
e3 <= ["c13"]
f3 <= ["b4"]
a4 <= ["d11"]
b4 <= ["c4"]
c4 <= ["c11"]
d4 <= ["d12"]
e4 <= ["d6"]
f4 <= ["a13"]
a5 <= ["a14"]
b5 <= ["b13"]
c5 <= ["b12"]
d5 <= ["d1"]
e5 <= ["d5"]
f5 <= ["d"]
a6 <= ["c5"]
b6 <= ["e13"]
c6 <= ["a16"]
d6 <= ["a4"]
e6 <= ["a1"]
f6 <= ["b2"]
a7 <= ["e15"]
b7 <= ["c6"]
c7 <= ["d14"]
d7 <= ["b7"]
e7 <= ["e4"]
f7 <= ["e3"]
a8 <= ["b3"]
b8 <= ["b9"]
c8 <= ["e11"]
d8 <= ["c3"]
e8 <= ["e6"]
f8 <= ["e14"]
a9 <= ["d8"]
b9 <= ["f13"]
c9 <= ["e2"]
d9 <= ["b5"]
e9 <= ["c12"]
f9 <= ["b14"]
a10 <= ["d4"]
b10 <= ["e7"]
c10 <= ["d16"]
d10 <= ["b16"]
e10 <= ["a8"]
f10 <= ["f6"]
a11 <= ["f14"]
b11 <= ["b"]
c11 <= ["b6"]
d11 <= ["c"]
e11 <= ["f"]
f11 <= ["b1"]
a12 <= ["a2"]
b12 <= ["a9"]
c12 <= ["d15"]
d12 <= ["c15"]
e12 <= ["f8"]
f12 <= ["c10"]
a13 <= ["e9"]
b13 <= ["f4"]
c13 <= ["a7"]
d13 <= ["a5"]
e13 <= ["b10"]
f13 <= ["b15"]
a14 <= ["d7"]
b14 <= ["f7"]
c14 <= ["f5"]
d14 <= ["b8"]
e14 <= ["e8"]
f14 <= ["c14"]
a15 <= ["c8"]
b15 <= ["f2"]
c15 <= ["c7"]
d15 <= ["f11"]
e15 <= ["a6"]
f15 <= ["d10"]
a16 <= ["e1"]
b16 <= ["a11"]
c16 <= ["c9"]
d16 <= ["f12"]
Completed successfully and validated!
So yeah, there's that.
Therefore, the algorithm works and everyone lived a happily Merry Christmas ever after...
No comments:
Post a Comment