6
$\begingroup$

This is somehow follow up question to How to measure 5 litres using 10L, 7L and 3L vessels

You went to a farm to get some milk. You only need $11$ liters of milk and ask for it to the farmer, but our farmer has only left a filled $13$ liters of vessel with milk with two other empty $5$ and $9$ liters of vessels, he may of course give you his vessels for free. Help him and get for yourself 11 liters of milk without any other equipments available.

At least how many times do you need to pour milk from one vessel to another vessel to buy 11 liters of milk in total?

You may use the table below;

+----+-----+----+----+
| #  | 13V | 9V | 5V |
+----+-----+----+----+
|  0 |  13 |  0 |  0 |
|  1 |     |    |    |
|  2 |     |    |    |
|  3 |     |    |    |
|  4 |     |    |    |
|  5 |     |    |    |
|  6 |     |    |    |
|  7 |     |    |    |
|  8 |     |    |    |
|  9 |     |    |    |
| 10 |     |    |    |
| 11 |     |    |    |
| 12 |     |    |    |
| 13 |     |    |    |
| 14 |     |    |    |
+----+-----+----+----+
Improve this question
$\endgroup$
0

7 Answers 7

Reset to default
6
$\begingroup$

My solution takes

9 times
13 0 0
8 0 5
8 5 0
3 5 5
3 9 1
12 0 1
12 1 0
7 1 5
7 6 0
2 6 5
Now the 9L and 5L vessels contain 11L of milk in total. I just take them both (since there is no requirement that the requested volume should be in a single vessel).

Improve this answer
$\endgroup$
0
4
$\begingroup$

Not sure if it's optimal, but I got a solution of $11$ steps after some trial-and-errors:

+----+-----+----+----+ | # | 13V | 9V | 5V | +----+-----+----+----+ | 0 | 13 | | | | 1 | 8 | | 5 | | 2 | 8 | 5 | | | 3 | 3 | 5 | 5 | | 4 | 3 | 9 | 1 | | 5 | 12 | | 1 | | 6 | 12 | 1 | | | 7 | 7 | 1 | 5 | | 8 | 7 | 6 | | | 9 | 2 | 6 | 5 | | 10 | 2 | 9 | 2 | | 11 | 11 | | 2 | +----+-----+----+----+

Improve this answer
$\endgroup$
3
$\begingroup$

9 steps for 2 vessels and 10 steps for 1 vessel.

0 move 13 - 0 - 0

1 move 0 - 8 - 5

2 move 5 - 8 - 0

3 move 5 - 3 - 5

4 move 10 - 3 - 0

5 move 10 - 0 - 3

6 move 1 - 9 - 3

7 move 1 - 7 - 5

8 move 6 - 7 - 0

9 move 6 - 2 - 5

10 move 11 - 2 - 0

Improve this answer
$\endgroup$
2
$\begingroup$

As other answers show, 11 litres in a single container is achievable in 11 pours. In addition, this is optimal, and in fact every reachable configuration can be reached with 11 pours, and (perhaps surprisingly) this can be checked with a manual search — there are only 28 reachable configurations.

Below is a full breadth-first search of the tree. It was constructed by going down the list in order; for each states, the ones that can be reached from it with one pour are listed; any that have already been reached are cancelled in [brackets], and the remaining new states are added to the bottom of the list (with a note of where they were reached from, and how many pours required). It ends when there are no newly-reached states remaining. Since the search is breadth-first, each state is reached by a path of minimal length. This took about 10–15mins to do, plus another 5–10 for tidying up formatting. 

#  from# pours state     goes to
1    –    0    13/0/0    4/9/0,   8/0/5
2    1    1    4/9/0     0/9/4,   [13/0/0], 4/4/5
3    1    1    8/0/5     0/8/5,   [13/0/0], 8/5/0
4    2    2    0/9/4     9/0/4,   [0/8/5],  4/9/0
5    2    2    4/4/5     [0/8/5], [8/0/5],  9/4/0,    [4/9/0]
6    3    2    0/8/5     [8/0/5], 5/8/0,    [0/9/4]
7    3    2    8/5/0     [4/9/0], 3/5/5,    [13/0/0], [8/0/5]
8    4    3    9/0/4     [0/9/4], [8/0/5],  [13/0/0], [9/4/0]
9    4    3    4/9/0     [0/9/4], [13/0/0], [4/4/5]
10   5    3    9/4/0     [4/9/0], [4/4/5],  [13/0/0], [9/0/4]
11   6    3    5/8/0     [4/9/0], [0/8/5],  [13/0/0], 5/3/5 
12   7    3    3/5/5     [0/8/5], [8/0/5],  [8/5/0],  3/9/1
13   11   4    5/3/5     [0/8/5], [8/0/5],  10/3/0,   [5/8/0]
14   12   4    3/9/1     [0/9/4], 12/0/1,   [3/5/5],  [4/9/0]
15   13   5    10/3/0    [4/9/0], [5/3/5],  [13/0/0], 10/0/3
16   14   5    12/0/1    [3/9/1], [8/0/5],  [13/0/0], 12/1/0
17   15   6    10/0/3    1/9/3,   [8/0/5],  [13/0/0], [10/3/0]
18   16   6    12/1/0    [4/9/0], 7/1/5,    [13/0/0], [12/0/1]
19   17   7    1/9/3     [0/9/4], [10/0/3], 1/7/5,    [4/9/0]
20   18   7    7/1/5     [0/8/5], [8/0/5],  [12/1/0], 7/6/0,
21   19   8    1/7/5     [0/8/5], [8/0/5],  6/7/0,    [1/9/3]
22   20   8    7/6/0     [4/9/0], 2/6/5,    [13/0/0], [7/1/5]
23   21   9    6/7/0     [4/9/0], [1/7/5],  [13/0/0], 6/2/5
24   22   9    2/6/5     [0/8/5], [8/0/5],  [7/6/0],  2/9/2
25   23   10   6/2/5     [0/8/5], [8/0/5],  11/2/0,   [6/7/0]
26   24   10   2/9/2     [0/9/4], 11/0/2,   [2/6/5],  [4/9/0]
27   25   11   11/2/0    [4/9/0], [6/2/5],  [13/0/0], [11/0/2]
28   26   11   11/0/2    [2/9/2], [8/0/5],  [13/0/0], [11/2/0]
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Re "there are only 28 reachable configurations.", I was gonna the program I previously posted to check that today, but I got sidetracked. It uses a BFS too. $\endgroup$
    – ikegami
    Apr 13, 2020 at 6:27
1
$\begingroup$

8 iterations, and the final one for 11lt.

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hi, welcome to puzzling SE :) I think the first step should be counted twice? Because you need to fill the second and third vessel. $\endgroup$
    – newbie
    Apr 11, 2020 at 12:22
  • 4
    $\begingroup$ It's wrong. How do you know that you've pured 5 litres in the 13v from the 9v in step 3? $\endgroup$
    – Stratos
    Apr 11, 2020 at 12:30
  • $\begingroup$ technically step 3 is two steps — you pour 5L from the 5L into the 13L, and you pour 5L from the 9L into the 5L afterwards. $\endgroup$
    – El-Guest
    Apr 11, 2020 at 15:15
  • 1
    $\begingroup$ hello Newbee, welcome! you just need to fix step 3 :) the rest seems correct to me. $\endgroup$
    – Oray
    Apr 11, 2020 at 18:53
1
$\begingroup$

Targeting for 2 in one of the smaller vessels at the end

method description

Improve this answer
$\endgroup$
0
$\begingroup$

The shortest solution requires 9 transfers.

A 9-transfer solution:

0       13      0       0
1       8       5       0
2       8       0       5
3       3       5       5
4       3       1       9
5       12      1       0
6       12      0       1
7       7       5       1
8       7       0       6
9       2       5       6

(5+6=11)

The shortest solution in which a container holds 11 L requires 11 transfers.

0       13      0       0
1       8       5       0
2       0       5       8
3       5       0       8
4       5       5       3
5       10      0       3
6       10      3       0
7       1       3       9
8       1       5       7
9       6       0       7
10      6       5       2
11      11      0       2

There could be other equally short solutions. This wasn't explored.

Solver:

#!/usr/bin/perl

use strict;
use warnings;
use feature qw( say state );

use Algorithm::Loops qw( NestedLoops );
use Cpanel::JSON::XS qw( );
use List::Util       qw( min sum );

sub solved_combined {
   my ($target, $vessels) = @_;

   my @quantities =
      grep { $_ > 0 && $_ <= $target }
         map { $_->[1] }
            @$vessels;

   return 0 if !@quantities;
   return 1 if grep { $_ == $target } @quantities;

   # This always takes time proportional to the square square of @quantities.
   # This can surely be optimized using dynamic programming techniques.
   my $iter = NestedLoops([
      map { [ 0, $_ ] } @quantities,
   ]);

   while ( my @selected = $iter->() ) {
      return 1 if sum(@selected) == $target;
   }

   return 0;
}

sub solved_single {
   my ($target, $vessels) = @_;
   return 0 + grep { $_->[1] == $target } @$vessels;
}

sub key {
   state $encoder = Cpanel::JSON::XS->new->canonical;
   return $encoder->encode($_[0]);
}

sub solve {
   my ($target, $vessels, $solved) = @_;

   my @queue = [ $vessels ];
   my %seen;
   while (@queue) {
      my $states = shift(@queue);
      my $vessels = $states->[-1];

      return $states if $solved->($target, $vessels);

      for my $src (0..$#$vessels) {
         for my $dst (0..$#$vessels) {
            my $xfer = min(
               $vessels->[$src][1],                        # Available to xfer
               $vessels->[$dst][0] - $vessels->[$dst][1],  # Available capacity
            );

            next if $src == $dst || !$xfer;

            my $vessels = [ @$vessels ];
            $vessels->[$src] = [ $vessels->[$src][0], $vessels->[$src][1] - $xfer ];
            $vessels->[$dst] = [ $vessels->[$dst][0], $vessels->[$dst][1] + $xfer ];

            next if $seen{key($vessels)}++;

            push @queue, [ @$states, $vessels ];
         }
      }
   }

   return undef;
}

{
   my $target = 11;
   my $vessels = [
      # Capacity, Contents
      [ 13, 13 ],
      [  5,  0 ],
      [  9,  0 ],
   ];

   my $find_single;

   {
      my $states = solve($target, $vessels, \&solved_combined)
         or die("No solutions possible.\n");

      say join "\t", $_, map $_->[1], @{ $states->[$_] } for 0..$#$states;

      $find_single = !solved_single($target, $states->[-1]);
   }

   if ($find_single) {
      say "---";

      my $states = solve($target, $vessels, \&solved_single)
         or die("No solutions possible.\n");

      say join "\t", $_, map $_->[1], @{ $states->[$_] } for 0..$#$states;
   }
}
Improve this answer
$\endgroup$
2
  • $\begingroup$ To get 11L in a single container, you can actually extend your 9-transfer solutions with 2 additional transfers (2-9-2 and 11-0-2), as pointed by @newbie. $\endgroup$
    – trolley813
    Apr 12, 2020 at 20:31
  • $\begingroup$ @trolley813, I was interested in determining the minimum number of transfers, and my answer already shows it's 11 for a single container with 11 L. I also wanted to use a method that worked for any inputs (number of vessels, size of vessels, and initial contents). For both of these reasons, a way to extend the 5+6 L solution into a 11 L solution is of no interest to me, but thanks anyway! $\endgroup$
    – ikegami
    Apr 12, 2020 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.