search

pcuci / meteor-santa

Secret santa, meteorized.
0 stars 1 forks source link

Matching algorithm must ignore significant others #3

Open pcuci opened 8 years ago

pcuci commented 8 years ago

Disallow matching between lovers.

Update matching algorithm to exclude conjointes.

pcuci commented 8 years ago

image

Trying various scenarios by hand, looks like an adjacency matrix is generalizable to conspiracy Santa too, the more complicated version of the game where teams can form to find someone a present. This implementation can also identify one person who needs to be Santa for 2+ people, in a future version, if needed (should the constraints be enforced to a maximum).

This solution doesn't readily support subgroups to gift other subgroups, as in a couple (together) buying a (one) present to another couple (happens in real life, all the time!). However, this exotic scenario may be abstracted/reduced to a simpler graph problem; further investigation required. Out of scope for now.

pcuci commented 8 years ago

After randomizing the players into giftees we need to (stably) sort them by out-degree (number of people not to gift, e.g.: self and maybe the better half if not single). Then, we can mechanically go through the matrix left to right and discover if there is a solution, and if yes, provide a possible answer.

Sorting a the randomized giftees list (a copy of all the players) ensure the randomness of secret santa matches.

pcuci commented 8 years ago

Came across an edge case which the random sort solution fails, seems like the problem is NP-hard (if I stumbled across the correct isomorph). The edge case is 5 players, A-B, C, D, E. Random sort will always pick C>A, D>B, A>C, B>D, and we're left with E which can't link to itself...

The challenge is to find a path through all nodes that are not connected (i.e. without passing through the paired paths).

Seems to be equivalent to the longest path problem: https://en.wikipedia.org/wiki/Longest_path_problem

pcuci commented 8 years ago

http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.longest_path

http://stackoverflow.com/questions/28730153/find-all-paths-in-a-directed-unweighted-graph-for-a-selected-node

pcuci commented 8 years ago

http://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

pcuci commented 8 years ago

http://stackoverflow.com/questions/27944340/longest-path-in-unweighted-undirected-graph

pcuci commented 8 years ago

The minimal number of players for paired-play is 4, either 2 pairs or one pair and two singles is required for a solution to exist.