Water Pouring : functional approach (scala, java 8)

App.java

package jm.desprez.bucketproblem;

import javaslang.Function1;
import javaslang.collection.LinkedHashSet;
import javaslang.collection.List;
import javaslang.collection.Set;
import javaslang.collection.Stream;
import javaslang.control.Option;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.ToString;

public class App {

	public static <T> Set<T> Set(final T of) {
		return LinkedHashSet.of(of);
	}

	@Data
	@AllArgsConstructor
	public static class WaterPouringSolver {
		private final int target;
		private Set<Integer> capacities;


		public Stream<Set<Path>> from(final Set<Path> paths, final Set<State> explored) {

			final Set<Path> newPaths = paths.flatMap((path) -> path.endState.moves()
					.map(path::add)
					.filter((newPath) -> !explored.contains(newPath.endState)));

			if (newPaths.isEmpty()) {
				return Stream.empty();
			}

			final Set<Path> pathsToDistinctStates = newPaths.distinctBy((p) -> p.endState);
			return Stream.cons(paths,
					() -> from(pathsToDistinctStates,
							explored.addAll(newPaths.map((p) -> p.endState))));

			// final Map<State, ? extends Set<Path>> distinctStates = newPaths.groupBy((p) -> p.endState);

			// final Set<Path> pathsToDistinctStates = distinctStates.mapValues((sp) -> sp.head())
			// .values()
			// .toSet();

			// return Stream.cons(paths, () -> from(pathsToDistinctStates, distinctStates.keySet()));
		}


		public Option<Path> solution() {

			final State initialState = new State(capacities.map(Glass::new));
			final Path initialPath = new Path(List.empty(), initialState);

			return from(Set(initialPath), Set(initialState)).flatMap((sp) -> sp)
					.filter((p) -> p.endState.glasses.exists((g) -> g.water == target))
					.headOption();

		}
	}

	@Data
	@AllArgsConstructor
	public static class Path {
		private List<Move> moves;
		private State endState;


		public Path add(final Move move) {
			return new Path(moves.prepend(move), move.apply(endState));
		}


		@Override
		public String toString() {
			return moves.reverse().mkString("\n");
		}
	}

	public static interface Move extends Function1<State, State> {}

	@Data
	@AllArgsConstructor
	public static class Empty implements Move {
		private final Glass theOneToEmpty;


		@Override
		public State apply(final State input) {
			return new State(input.glasses.remove(theOneToEmpty).add(theOneToEmpty.empty()));
		}
	}

	@Data
	@AllArgsConstructor
	public static class Fill implements Move {
		private final Glass theOneToFill;


		@Override
		public State apply(final State input) {
			return new State(input.glasses.remove(theOneToFill).add(theOneToFill.fill()));
		}
	}

	@Data
	@AllArgsConstructor
	public static class Pour implements Move {
		private final Glass from;
		private final Glass to;


		@Override
		public State apply(final State input) {
			final int moved = Math.min(from.water, to.capacity - to.water);
			return new State(input.glasses.remove(from)
					.add(from.minus(moved))
					.remove(to)
					.add(to.plus(moved)));
		}
	}

	@Data
	@AllArgsConstructor
	@EqualsAndHashCode
	@ToString(of = "glasses")
	public static class State {
		private Set<Glass> glasses = LinkedHashSet.empty();


		private Set<? extends Move> emptyMoves() {
			return glasses.map(Empty::new);
		}


		private Set<? extends Move> fillMoves() {
			return glasses.map(Fill::new);
		}


		private Set<? extends Move> pourMoves() {
			return glasses.flatMap((g) -> glasses.remove(g).map((h) -> new Pour(g, h)));
		}


		public Set<? extends Move> moves() {
			return LinkedHashSet.<Move> empty()
					.addAll(emptyMoves())
					.addAll(fillMoves())
					.addAll(pourMoves());
		}

	}

	@Data
	@AllArgsConstructor
	@EqualsAndHashCode
	public static class Glass {
		private final int capacity;
		private final int water;


		public Glass(final int capacity) {
			this(capacity, 0);
		}


		public Glass empty() {
			return new Glass(capacity, 0);
		}


		public Glass fill() {
			return new Glass(capacity, capacity);
		}


		public Glass plus(final int water) {
			return new Glass(capacity, this.water + water);
		}


		public Glass minus(final int water) {
			return new Glass(capacity, this.water - water);
		}
	}


	public static void main(final String[] args) {

		final LinkedHashSet<Integer> capacities = LinkedHashSet.of(2, 4, 6, 35);
		final State initialState = new State(capacities.map(Glass::new));
		final WaterPouringSolver solver = new WaterPouringSolver(5, capacities);

		final Option<Path> solution = solver.solution();
		if (solution.isDefined()) {
			final List<Move> moves = solution.get().moves;
			final List<State> states = moves.scanRight(initialState, (m, s) -> m.apply(s));
			System.out.println(states.reverse().mkString("\n"));
			System.out.println(solution.get());
			System.out.println(solution.get().endState);
			System.out.println(solution.get().moves.foldRight(initialState, (m, s) -> m.apply(s)));
		} else {
			System.out.println("impossible");
		}
	}
}

WaterPouring.scala

package streams

object WaterPouring extends App {
  val solver = WaterPouringSolver(4, Set(7, 9))
  println(solver.solution)

  val solver2 = WaterPouringSolver(20, Set(2, 7, 19, 47))
  println(solver2.solution)

  case class WaterPouringSolver(target: Int, capacities: Set[Int]) {
    val initialState = State(capacities.map(Glass(_, 0)))
    val initialPath = Path(Nil, initialState)

    def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] = {
      val newPaths = for {
        path <- paths
        move <- path.endState.moves
        newPath = path.add(move)
        if !explored.contains(newPath.endState)
      } yield newPath
      val distinctStates = newPaths.groupBy(_.endState)
      val pathsToDistinctStates=distinctStates.map { case (_, paths) => paths.head }.toSet
      paths #:: from(pathsToDistinctStates, distinctStates.keySet)
    }

    def solution = (for {
      steps <- from(Set(initialPath), Set(initialState))
      path <- steps
      if path.endState.glasses.exists(_.water == target)
    } yield path).headOption
  }

  case class Path(moves: List[Move], endState: State) {
    def add(move: Move) =
      Path(move :: moves, move(endState))

    override def toString = moves.reverse.mkString("\n")
  }

  trait Move {
    def apply(s: State): State
  }

  case class Empty(g: Glass) extends Move {
    def apply(s: State) = State(s.glasses - g + g.copy(water = 0))
  }

  case class Fill(g: Glass) extends Move {
    def apply(s: State) = State(s.glasses - g + g.copy(water = g.capacity))
  }

  case class Pour(from: Glass, to: Glass) extends Move {
    val moved = from.water min (to.capacity - to.water)
    def apply(s: State) = State(s.glasses - from - to +
      from.copy(water = from.water - moved) +
      to.copy(water = to.water + moved))
  }

  case class State(glasses: Set[Glass]) {
    def emptyMoves = glasses.map(Empty)
    def fillMoves = glasses.map(Fill)
    def pourMoves = for {
      g <- glasses
      h <- glasses
      if g != h
    } yield Pour(g, h)

    def moves: Set[Move] = emptyMoves ++ fillMoves ++ pourMoves
  }

  case class Glass(capacity: Int, water: Int)
}