/scrumble_christmas

Primary LanguagePython

What is it ?

A simple script for making gift for christmas.

What do I need ?

Only Python3

How to use it ?

  1. clone this repo (at least copy the scrumble.py)
  2. Create a configuration file
  3. launch the command python3 scrumble.py conf.json

What the configuration file should look like ?

{
  "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"]
  ]
}

Does it always work ?

Short Answer

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

Longer Answer

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:

  1. init a map of person who make a gift and to who
  2. take a random person who are not making a gift,
  3. select a random person who do not receive a gift AND is not in the familly,
  4. if you can't find anybody start again (1.)
  5. if nobody left, so everybody have a gift AND everybody is making a gift, you have a solution
  6. merry christmas !