- What is it ?
- What do I need ?
- How to use it ?
- What the configuration file should look like ?
- Does it always work ?
A simple script for making gift for christmas.
Only Python3
- clone this repo (at least copy the
scrumble.py
) - Create a configuration file
- launch the command
python3 scrumble.py conf.json
{
"couple" : [
["couple_a_person_aa", "couple_a_person_ab"],
["couple_b_person_ba", "couple_b_person_bb"],
["couple_c_person_ca", "couple_c_person_cb"],
["couple_d_person_da", "couple_d_person_db"]
]
}
Nope.
The following configuration file have no solution and the current program will loop for ever.
{
"couple" : [
["a", "b"],
["c"]
]
}
Indeed we have the situation:
a -> c
c -> b
b -> a # <- but it's forbiden to make a gift in the couple
This problem could be resume has one person must have only one gift and make one gift to anybody but his familly.
Now if we represent it with a graph with those suppositions:
- vertex represent a person
- oriented edges represent to who you can make a gift
The following configuration file:
{
"couple" : [
["a", "b"],
["c", "d"]
]
}
Would make the graph:
a --> c
a --> d
b --> c
b --> d
c --> a
c --> b
d --> a
d --> d
And it growth in complexity! (In fact it is a Complete graph minus familly edges).
In graph theory this could be modeled as finding an Hamiltonian path. And this is a NP-Complet problem.
Ok, the general problem is hard, but in our case, we have many edges to walk to (aka we can make a gift to anybody), so most of the time we can find a solution fearly easely.
My implementation here is:
- init a map of person who make a gift and to who
- take a random person who are not making a gift,
- select a random person who do not receive a gift AND is not in the familly,
- if you can't find anybody start again (1.)
- if nobody left, so everybody have a gift AND everybody is making a gift, you have a solution
- merry christmas !