Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import std.stdio;
- import std.range;
- import std.algorithm;
- import std.exception;
- import std.string;
- import std.conv;
- enum string[] names = ["Luke Skywalker",
- "Leia Skywalker",
- "Toula Portokalos",
- "Gus Portokalos",
- "Bruce Wayne",
- "Virgil Brigman",
- "Lindsey Brigman"];
- class Person {
- static int instances = 0;
- string name;
- bool hasGiven;
- bool hasReceived;
- override string toString() {
- return "Person(%s,%s,%s)".format(name, hasGiven, hasReceived);
- };
- this(string s ) {
- name = s;
- };
- bool isFamily( Person other) {
- return familyName(name) == familyName(other.name);
- };
- }
- string familyName( string s ) {
- return s.split(" ")[1];
- }
- bool isFamily( string a , string b) {
- return familyName(a) == familyName(b);
- }
- class Gift {
- Person giver;
- Person recipient;
- this( Person g, Person r ) {
- giver = g;
- recipient = r;
- };
- override string toString() {
- return format("Gift(%s,%s)", giver, recipient);
- }
- }
- auto people = names.map!( x => new Person(x)).array;
- void makeGift( ref Gift g) {
- enforce( !g.giver.hasGiven, "Logic error");
- enforce( !g.recipient.hasReceived, "Logic error");
- g.giver.hasGiven = true;
- g.recipient.hasReceived = true;
- }
- void takeBackGift( ref Gift g) {
- enforce( g.giver.hasGiven, "Logic error");
- enforce( g.recipient.hasReceived, "Logic error");
- g.giver.hasGiven = false;
- g.recipient.hasReceived = false;
- }
- Gift[] emptyGift;
- Gift[] possibleMoves(int movesMade) {
- if (movesMade>=people.length) {
- return emptyGift;
- } else {
- auto giver = people[movesMade];
- enforce(!giver.hasGiven, "Logic error");
- auto ret = people
- .filter!( x => !x.hasReceived && !giver.isFamily(x) )
- .map!( x => new Gift( giver, x))
- .array;
- return ret;
- }
- }
- bool isSolved() {
- return people.all!"a.hasReceived && a.hasGiven";
- }
- void main()
- {
- Gift[][] movesRemaining;
- Gift[] movesMade;
- movesRemaining ~= possibleMoves(0);
- void dump() {
- foreach( m ; movesMade) {
- writeln(m);
- }
- }
- auto solutions = 0;
- while( !movesRemaining.empty) {
- if (movesRemaining[$-1].empty) {
- movesRemaining.length -= 1;
- if (movesMade.empty) continue;
- takeBackGift( movesMade[$-1]);
- movesMade.length -= 1;
- } else {
- auto moveToMake = movesRemaining[$-1][$-1];
- movesRemaining[$-1].length -= 1;
- makeGift(moveToMake);
- movesMade ~= moveToMake;
- movesRemaining ~= possibleMoves(to!int(movesMade.length));
- }
- if (isSolved()) {
- writeln("\nSolved");
- foreach( ref q ; movesMade) {
- writeln(q);
- }
- solutions++;
- }
- }
- writefln("Found %s solutions", solutions);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement