Solution to Water Jug Puzzle
Java
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
src/waterJugPuzzle
README.md
_config.yml

README.md

Water Jug Puzzle (The Die Hard Riddle)

We would like to collect a specific amount of water in a bottle when we have k water bottles with prespecified capacity and only the following operations are allowed:

  • Fill up either bottle completely.
  • Empty either bottle completely.
  • Pour water from one bottle to the other until the poured bottle becomes empty or the other bottle becomes full.

Water Jug Puzzle was solved using Breadth-First Search in

  • Sequential and
  • Master-worker cluster pattern

Test case: two bottles of size 5, 3 and target amount of 4.

Solution given by Sequential and cluster implementation:

The solution to water jug puzzle with 2 bottles of size [5, 3] is: [0, 0]->[5, 0]->[2, 3]->[2, 0]->[0, 2]->[5, 2]->[4, 3].

To compare sequential and cluster implementation, 10 bottles of size 3,5,7,13,19,29,31,37,39,41 with target amount 21 was considered.

Solution:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]-> [0, 0, 0, 0, 19, 0, 0, 0, 0, 0]-> [0, 0, 0, 0, 19, 0, 0, 0, 0, 41]-> [0, 0, 0, 0, 0, 0, 0, 0, 19, 41]-> [0, 0, 0, 0, 0, 0, 0, 0, 39, 21].
Sequential time Parallel time Speedup
7019 4340 7019/4340 = 1.6

To run Sequential program,

# Compile the java file
javac waterJugPuzzle.java

# Execute compiled java class file
java waterJugPuzzle

To run parallel program

# Compile the parallel program
javac WaterJugClu.java

# Make jar file from compiled class file
jar cf WaterJugClu.jar *.class

# Execute the jar created
java pj2 jar-WaterJugClu.jar WaterJugClu