const roads = ["Alice's House-Bob's House", "Alice's House-Cabin", "Alice's House-Post Office", "Bob's House-Town Hall", "Daria's House-Ernie's House", "Daria's House-Town Hall", "Ernies' House-Grete's House", "Grete's House-Farm", "Grete's House-Shop", "Marketplace-Farm", "Marketplace-Post Office", "Marketplace-Shop", "Marketplace-Town Hall", "Shop-Town Hall"];

function buildGraph(edges) {
  let graph = Object.create(null);
  function addEdge(from, to) {
    if(graph[from] == null) {
      graph[from] = [to];
    } else {
      graph[from].push(to);
    }
  }
  for (let [from, to] of edges.map(r => r.split("-"))) {
    addEdge(from, to);
    addEdge(to, from);
  }
  return graph;
}

const roadGraph = buildGraph(roads);

class VillageState {
  constructor(place, parcels) {
    this.place = place;
    this.parcels = parcels;
  }
  
  move(destination) {
    // Check if the move is valid, otherwise return old state.
    if(!roadGraph[this.place].includes(destination)) {
      return this;
    } else {
      let parcels = this.parcels.map(p => {
        // If the parcel's location is not equal to the robot's, the parcel won't move next round. (Parcel is not yet picked up)
        if(p.place != this.place) return p;
        // If the parcel's location is equal to the robot's, the parcel's next location will be the robot's destination. (Parcel is picked up)
        return { place: destination, address: p.address }
        // Filter out the parcel's who's current location have been updated to their destination address (Parcel is delivered)
      }).filter(p => p.place != p.address);
      return new VillageState(destination, parcels);
    }
  }
}

// Takes a VillageState (starting location and parcels (with a location and a destination)), a robot and a memory
function runRobot(state, robot, memory) {
  for (let turn = 0;; turn++) {
    if (state.parcels.length == 0) {
      console.log(`Done in ${turn} turns`);
      return turn;
    }
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
    console.log(`Moved to ${action.direction}`);
  }
}

function randomPick(array) {
  let choice = Math.floor(Math.random() * array.length);
  return array[choice];
}

function randomRobot(state) {
  return {direction: randomPick(roadGraph[state.place])};
}

VillageState.random = function(parcelCount = 5) {
  let parcels = [];
  for (let i = 0; i < parcelCount; i++) {
    let address = randomPick(Object.keys(roadGraph));
    let place;
    do {
      place = randomPick(Object.keys(roadGraph));
    } while (place == address);
    parcels.push({place, address});
  }
  return new VillageState("Post Office", parcels); 
};

// runRobot(VillageState.random(), randomRobot);

const mailRoute = [
  "Alice's House", "Cabin", "Alice's House", "Bob's House", "Town Hall", "Daria's House", "Ernie's House", "Grete's House", "Shop", "Grete's House", "Farm", "Marketplace", "Post Office"
];

function routeRobot(state, memory) {
  if(memory.length == 0) {
    memory = mailRoute;
  }
  return {direction: memory[0],
    memory: memory.slice(1)};
}

// runRobot(VillageState.random(), routeRobot);

function findRoute(graph, from, to) {
  // Start with a work list of places to explore next [at]
  // along with the route that got us there (route)
  let work = [{at: from, route: []}];
  // Loop through the work list (it will grow 
  // inside the loop)
  for (let i=0; i < work.length; i++) {
    // Take the current location (at) and the current route
    let {at, route} = work[i];
    // For the current location, loop through the 
    // possible next destinations
    for (let place of graph[at]) {
      // If one of the destinations is the target, add it to
      // the route and return the route.
      if (place == to) return route.concat(place);
      // If the target is not found, and if we haven't
      // looked at this place before, we add it to the 
      // list.
      if(!work.some(w => w.at == place)) {
        work.push({at: place, route: route.concat(place)});
      }
    }
  }
}

function goalOrientedRobot({place, parcels}, route) {
  if (route.length == 0) {
    let parcel = parcels[0];
    if(parcel.place != place) {
      route = findRoute(roadGraph, place, parcel.place);
    } else {
      route = findRoute(roadGraph, place, parcel.address);
    }
  }
  return {direction: route[0], memory: route.slice(1)}
}

runRobot(VillageState.random(), goalOrientedRobot, []);

function compareRobots(robotOne, robotTwo) {
  robotOneResults = [];
  robotTwoResults = [];
  for (let i=0; i<100; i++) {
    let villageState = VillageState.random();
    robotOneResults.push(runRobot(villageState, robotOne, []));
    robotTwoResults.push(runRobot(villageState, robotTwo, []));
  }
  console.log(`Robot 1: ${getAverage(robotOneResults)}`);
  console.log(`Robot 2: ${getAverage(robotTwoResults)}`);
}

function getAverage(inputArray) {
  return inputArray.reduce((acc, c) => (acc + c)) / inputArray.length;
}

// compareRobots(goalOrientedRobot, randomRobot);

function nearestParcelRobot({place, parcels}, route) {
  if (route.length == 0) {
    let parcel = parcels[getNearestParcelIndex(place, parcels)];
    if(parcel.place != place) {
      route = findRoute(roadGraph, place, parcel.place);
    } else {
      route = findRoute(roadGraph, place, parcel.address);
    }
  }
  return {direction: route[0], memory: route.slice(1)}
}


function getNearestParcelIndex(currentLocation, parcels) {
  let nearestParcelLocation = '';
  let shortestRouteSoFar = 99;
  let index = -1;
  for (let parcel of parcels) {
    index++;
    route = findRoute(roadGraph, currentLocation, parcel.place);
    if (route.length < shortestRouteSoFar) {
      shortestRouteSoFar = route.length;
      console.log(shortestRouteSoFar);
      indexForShortestRoute = index;
    }
  }
  return indexForShortestRoute;
}


// Notes
// Map the parcels array onto a new array of routes which includes a route property which we bind to the result of findRoute for that parcel's location
// In the same element in the new array, track whether the parcel has been picked up and when it hasn't, give that option a 0.5 score. 
// Add the length of the route to the score and choose the parcel with the lowest score.


function lazyRobot({place, parcels}, route) {
  if (route.length == 0) {
    // Describe a route for every parcel
    let routes = parcels.map(parcel => {
      if (parcel.place != place) {
        return {route: findRoute(roadGraph, place, parcel.place),
                pickUp: true};
      } else {
        return {route: findRoute(roadGraph, place, parcel.address),
                pickUp: false};
      }
    });

    // This determines the precedence a route gets when choosing.
    // Route length counts negatively, routes that pick up a package
    // get a small bonus.
    function score({route, pickUp}) {
      return (pickUp ? 0.5 : 0) - route.length;
    }
    route = routes.reduce((a, b) => score(a) > score(b) ? a : b).route;
  }

  return {direction: route[0], memory: route.slice(1)};
}


// compareRobots(nearestParcelRobot, lazyRobot);

class PGroup {
  constructor(inputArray) {
    this.members = inputArray;
  }
  
  add(value) {
    if (this.has(value)) return this;
    return new PGroup([...this.members, value]);
  }
  
  delete(value) {
    if (!this.has(value)) return this;
    return new PGroup(this.members.filter(x => x !== value));
  }
  
  has(value) {
    return this.members.includes(value);
  }
  
}

PGroup.empty = new PGroup([]);

let a = PGroup.empty.add("a");
let ab = a.add("b");
let b = ab.delete("a");

console.log(b.has("b"));
// → true
console.log(a.has("b"));
// → false
console.log(b.has("a"));
// → false