dancing-circle-optimizer

The Sardana is a popular dance in Catalunya where men and women form a circle and dance while holding their hands. Commonly, if there are enough pairs of men m and women w, two dancers of the same gender do not hold hands in the circle, i.e they alternate each other:

                               m  -  w
                            /           \
                          w               m
                          |               |
                          m               w
                            \           /
                               w  -  m

It is also the case that dancers dance more comfortably next to someone who has a similar height, because when heights are very different they have to adopt uncomfortable arm positions and the circle loses aesthetics.

This program accepts a list of man and woman dancers with their respective heights, together with a set of restrictions on who can dance next to who, and outputs a list of all the possible dancing circles sorted decreasingly by how good they are based on the criteria of height difference minimization.

Restrictions

The first lines of the dancing-circle-optimizer.pl source file specify the list of dancers, their heights and the restrictions on who can dance together, who does not dance, etc.

Example:

men([fabio-174, jordan-176, joe-180, george-171, eddard-172, tyrion-180, gregor-175]).
women([cersei-165, sansa-171, melisandre-165, brienne-170, margaery-162, ygritte-168, missandei-164]).

% RULE SEMANTICS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% dancesOnRightSide(X, Y) <=> X must dance on the right side of Y

% doesNotDanceOnRightSide(X, Y) <=> X cannot dance on the right side of Y
% doesNotDance(X, Y) <=> X cannot dance with Y, on any side
% doesNotDance(X) <=> X does not dance

% doesNotDanceBetween(X, Y, Z) <=> Z cannot dance between X and Y
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% MANUALLY SPECIFIED CONDITIONS
dancesOnRightSide(sansa, tyrion).

doesNotDanceOnRightSide(cersei, jordan).
doesNotDanceOnRightSide(brienne, tyrion).
doesNotDance(george, brienne).
doesNotDance(fabio, cersei).
doesNotDanceOnRightSide(george, cersei).

doesNotDance(margaery).
doesNotDance(gregor).

doesNotDanceBetween(george, eddard, _). % No one can dance between these two men

You can include your own dancers and restrictions by manually changing this section of the source code, just follow the same definition format as the example.

Building

SWI Prolog must be installed in your system.

Run make to compile the prolog program.

Running

Run ./dancing-circle-optimizer. It will output a list with all the possible dancing circles, sorted increasingly by score, where a higher score means the dancing circle is worse.

Example output:

-eddard-ygritte-joe-sansa-tyrion-brienne-jordan-cersei-george-missandei-fabio-melisandre (2074)
-eddard-ygritte-joe-sansa-tyrion-brienne-jordan-cersei-george-melisandre-fabio-missandei (2076)
-eddard-brienne-joe-sansa-tyrion-ygritte-jordan-cersei-george-missandei-fabio-melisandre (2090)
-eddard-brienne-joe-sansa-tyrion-ygritte-jordan-cersei-george-melisandre-fabio-missandei (2092)
-eddard-cersei-joe-sansa-tyrion-brienne-jordan-ygritte-george-missandei-fabio-melisandre (2104)
-george-ygritte-jordan-brienne-joe-sansa-tyrion-cersei-eddard-melisandre-fabio-missandei (2104)
-eddard-sansa-tyrion-brienne-joe-ygritte-jordan-cersei-george-missandei-fabio-melisandre (2106)
-george-ygritte-jordan-brienne-joe-sansa-tyrion-cersei-eddard-missandei-fabio-melisandre (2106)
-eddard-cersei-joe-sansa-tyrion-brienne-jordan-ygritte-george-melisandre-fabio-missandei (2106)
-eddard-sansa-tyrion-brienne-joe-ygritte-jordan-cersei-george-melisandre-fabio-missandei (2108)
-eddard-melisandre-joe-sansa-tyrion-brienne-jordan-cersei-george-missandei-fabio-ygritte (2110)
-eddard-cersei-joe-sansa-tyrion-brienne-jordan-melisandre-george-missandei-fabio-ygritte (2110)
-george-melisandre-jordan-brienne-joe-sansa-tyrion-cersei-eddard-ygritte-fabio-missandei (2110)
-george-ygritte-jordan-sansa-tyrion-brienne-joe-cersei-eddard-melisandre-fabio-missandei (2112)
-george-missandei-jordan-brienne-joe-sansa-tyrion-cersei-eddard-ygritte-fabio-melisandre (2114)
-george-ygritte-jordan-sansa-tyrion-brienne-joe-cersei-eddard-missandei-fabio-melisandre (2114)
-eddard-cersei-joe-sansa-tyrion-brienne-jordan-missandei-george-melisandre-fabio-ygritte (2114)
-george-melisandre-jordan-brienne-joe-sansa-tyrion-cersei-eddard-missandei-fabio-ygritte (2118)
-eddard-melisandre-joe-sansa-tyrion-brienne-jordan-cersei-george-ygritte-fabio-missandei (2118)
-eddard-cersei-joe-sansa-tyrion-brienne-jordan-melisandre-george-ygritte-fabio-missandei (2118)
-george-melisandre-jordan-sansa-tyrion-brienne-joe-cersei-eddard-ygritte-fabio-missandei (2118)
-eddard-cersei-joe-sansa-tyrion-brienne-jordan-missandei-george-ygritte-fabio-melisandre (2120)
-george-missandei-jordan-brienne-joe-sansa-tyrion-cersei-eddard-melisandre-fabio-ygritte (2120)
-eddard-sansa-tyrion-ygritte-joe-brienne-jordan-cersei-george-missandei-fabio-melisandre (2122)
-george-missandei-jordan-sansa-tyrion-brienne-joe-cersei-eddard-ygritte-fabio-melisandre (2122)
-eddard-missandei-joe-sansa-tyrion-brienne-jordan-cersei-george-melisandre-fabio-ygritte (2124)
-eddard-sansa-tyrion-ygritte-joe-brienne-jordan-cersei-george-melisandre-fabio-missandei (2124)
-george-melisandre-jordan-sansa-tyrion-brienne-joe-cersei-eddard-missandei-fabio-ygritte (2126)
-george-missandei-jordan-sansa-tyrion-brienne-joe-cersei-eddard-melisandre-fabio-ygritte (2128)
.
.
.