santa

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);
}