12
$\begingroup$

In AI we can classify a problem in 3 classes, ignorable, recoverable or irrecoverable problems. Now while reading Water jug Problem

enter image description here

I am wondering in which of these 3 class it should fall? It should reside under recoverable right? As we can go back to the previous state in Water Jug Problem by altering the water level, I think it is recoverable. Is my thinking right?

$\endgroup$
  • 9
    $\begingroup$ Is the "ignorable, recoverable, irrecoverable" classification commonly understood? I googled it, and it seems to be a specific Indian classification scheme. Also, it doesn't appear to be related to AI at all. This is essentially a graph problem, where the problem is just "what is the path from {12,0,0} to {6,6,0} ?". $\endgroup$ – MSalters Nov 12 at 11:00
  • $\begingroup$ Classifying problems in these 3 categories helps you a lot while approaching a problem, for example chess is irrecoverable as you cant reverse your move, but this is not the case for 8 puzzle. Based on these assumptions we can formulate our strategy to approach this problem $\endgroup$ – HIRAK MONDAL Nov 12 at 13:50
  • 4
    $\begingroup$ This looks like a combinatorial game theory (CGT) problem, not AI. It's rather related to mathematics and theoretical computer science. I think the question should be re-formulated and re-located. $\endgroup$ – Quora Feans Nov 12 at 17:32
  • 3
    $\begingroup$ @HIRAKMONDAL I don't see that distinction making any difference in AI, unless it's a reinforcement learner interacting with the real physical system. The computer can always "undo" a move that's been made virtually. Chess computers undo millions of speculative moves per second. $\endgroup$ – hobbs Nov 12 at 22:34
  • 1
    $\begingroup$ @hobbs - that's not always the case. Consider encrypting state data (taking more than half of your working memory) in-place with someone else's public key for a somewhat-contrived example. I see your point though. $\endgroup$ – TLW Nov 13 at 6:34
16
$\begingroup$

Recoverable, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable:

[12, 0, 0]
[4,  8, 0]
[4,  3, 5]
[9,  3, 0]
[9,  0, 3]
[1,  8, 3]
[1,  6, 5]
[6,  6, 0]  # <-- SOLVED; 7 steps

DETAILS: The problem stated as-is is recoverable, and in a machine learning problem statement, we take the problem as-defined, not how it could be defined. For any # of jugs of any sizes, as long as we start with only one jug filled, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable.

[0, 0, ..., X,   ..., 0] <-- only one jug filled
[2, 0, ..., X-2, ..., 0]
...
[2, 4, ..., ?,   ..., 7] <-- some arbitrary state
...
[0, 0, ..., X,   ..., 0] <-- RECOVERED; empty all other jugs into original jug

Update: the system is also recoverable if starting with any # of jugs filled, as long as they're fully filled. They also don't necessarily have to be fully filled, but it then becomes jugsize-dependent, and no generalization w/o mathematical formulation can be made.


DEFINITIONS: OP hasn't defined "recoverable", "irrecoverable", or "ignorable" - and neither Google nor DuckDuckGo reveal much. Giving my best attempt at making sense of it, each can be defined as follows:

  • Recoverable: state t0 can be restored from any other state T when starting at t0
  • Irrecoverable: there exists some state T we can get to from t0, but no longer revert to t0
  • Ignorable: we don't care, and can solve the problem at hand either way

Irrecoverable example: [0, 1, 2] --> [0, 0, 3]. Goodbye forever, 1 liter & 2 liters.


Ignorable example: goal: two jugs empty. In this case, both the original [12, 0, 0] and the irrecoverable case [0, 1, 2] work.

$\endgroup$
  • $\begingroup$ Is there an initial state that would not be recoverable? Does that change the classification of the problem? $\endgroup$ – Mars Nov 12 at 0:34
  • $\begingroup$ @Mars Yes, but that would change the problem itself - in defining a machine learning problem, this would be specified, so the problem stated as-is is either recoverable or underspecified. Also I don't know what these exact distinctions are, but am answering from a model design POV & an interpretation of "recoverable" $\endgroup$ – OverLordGoldDragon Nov 12 at 0:39
  • 1
    $\begingroup$ @Mars Agreed, but I actually don't have a clue - and I couldn't find much via search besides some loosely-put text in form of a quiz answer key. If you come across a better source, I can summarize it if you link it $\endgroup$ – OverLordGoldDragon Nov 12 at 0:52
  • 2
    $\begingroup$ This should be the accepted answer. The line "For any # of jugs of any sizes, as long as we start with only one jug filled, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable" says it all. $\endgroup$ – Vincent Nov 12 at 11:26
  • 1
    $\begingroup$ @Mars made an attempt at defining - updated $\endgroup$ – OverLordGoldDragon Nov 13 at 2:33
7
$\begingroup$

The state described (3, 2, 0) in the currently accepted answer is not achievable from the initial state of the given problem, unless "pour water on the ground" is a valid move, in which case I agree it's non-recoverable without a very good shop-vac.

I couldn't in a quick Google through the textbooks tell whether recoverability requires immediate, single-move recoverability (ctrl-Z-style) with each undo step being O(1) complexity, and which can be implementable as a sequence of moves in a push/pop stack. They always use guaranteed-single-move-undo examples (8-puzzle, Towers of Hanoi) for their recoverable examples, and always chess for their irrecoverable example.

Textbooks never describe the interesting cases :(

If our criteria for recoverability requires single-move-undo, then it's easy to think of an example where it is not recoverable in a single move:

(1,8,3) -> (0,8,4) cannot be undone in a single move (or pour).

If recovery can be multi-move, then (0,8,4 -> (some magic steps here) -> 1,8,3) gives recovery in multiple pours. However, this recovery path requires solving a path to recovery, which is sort of putting the cart before the horse: to undo a step towards solving the problem, we have to first solve the problem!

But in the example given, we can always guarantee that we can regain a previous position by doing: rightmost jug to leftmost jug; center jug to leftmost jug (thus returning to the initial condition); repeat all steps from the start until we get back to the desired recovery step. This does require that we store all moves made, though; but I think that would likely be the output of most answers anyway, so may be considered OK?

It seems intuitively obvious that we can't, through any sequence of moves, get to a position that we can't duplicate by repeating that set of moves from the initial condition. So the problem as given is recoverable, though we can't just implement it as a push/pop stack: while that's all we need for write, we need to be able to iterate it for reading.

More importantly, this makes undo an O(N+2) operation, instead of an O(1) operation. For most problems, we can just hit the reset button and replay in O(N), so we really gain nothing from doing this. Unless initial setup is prohibitively expensive for some reason, we'll be slightly more efficient if we solve it as non-recoverable, than if we kept replaying the whole thing every time we backtracked. So the problem given is not worth recovering this way.

And what if the problem stated instead: "We start with the same jugs, this time containing 9, 1.5, and 1.5 liters." Now we can never regain that initial state through any sequence of moves, so there exist jug problems which are not recoverable.

I think this makes the class of jug problems as a whole "non-recoverable", but any example we'll ever find in a textbook is likely to be "recoverable but not worth recovering", because textbooks never describe the interesting cases :(

$\endgroup$
  • $\begingroup$ How do you get from 0/8/4 to 1/6/5 in one pour? All three jugs change the amount of water in them, but only two can be involved in a single pour. And I don't see how to get the single liter in the left jug... $\endgroup$ – Hazel Troost Nov 12 at 22:54
  • $\begingroup$ @HazelTroost By failing to brain, of course! Thanks for catching, fixing... :D $\endgroup$ – Dewi Morgan Nov 13 at 17:03
6
$\begingroup$

Suppose the leftmost jug had 3 liters, the center jug had 2 liters, the right jug is empty. Suppose you poured the leftmost jug to the center jug. Now the leftmost jug is empty, and the center jug contains 5 liters. At this point you cannot go back to your original state. Consequently, your problem is irrecoverable.

$\endgroup$
  • 3
    $\begingroup$ What do 3 & 2 liters in left & center jugs have to do with this problem? Why does this prove the problem is "irrecoverable"? What does "irrecoverable" even mean - impossible? $\endgroup$ – OverLordGoldDragon Nov 11 at 19:32
  • 3
    $\begingroup$ If "recoverable" means that a particular state can be restored, then starting with 12 liters, we can always restore the original state - and thus any state derived thereof - by pouring all the water back to the leftmost jug - hence your answer is wrong. $\endgroup$ – OverLordGoldDragon Nov 11 at 19:40
  • $\begingroup$ @Dukeling If our initial state involves a single jug with X liters of water, assuming no additional water is introduced later on, then no matter how many other jugs there are of any size, the problem is recoverable as we can always pour water from all jugs back to the original to restore X - and hence any state derived thereof. See my answer $\endgroup$ – OverLordGoldDragon Nov 11 at 20:27
  • 7
    $\begingroup$ I fail to see how this answer addresses the actual problem described in the question. In your situation, sure, the problem can reach an irrecoverable state. But in the problem described in the question, there is 12L of water in the 12L jug, not 3L. And though an arbitrary state might not be recoverable from an immediately following state depending on the action taken, the initial state can be recovered from any state by simply pouring all the water back into the 12L jug. $\endgroup$ – Abion47 Nov 11 at 22:25
  • 8
    $\begingroup$ Yeah, this whole question and answer is incoherent and almost insane. The question makes a sensible first impression, but is actually just a bunch of undefined and unrelated terminology thrown together, mixed with a riddle. There is no formal definition for these "3 classes" of problems - they don't exist. And what does it have to do with AI? Why are the numbers of liters totally different in the accepted answer? What are we actually talking about here? $\endgroup$ – ig-dev Nov 12 at 4:59
-2
$\begingroup$

In Recoverable method: 12lit. 8lit. 5lit. ( 4 , 8, 0) ( 4, 3, 5) ( 9, 3, 0) ( 1, 8, 3) ( 1, 6, 5) ( 6, 6, 0) //step 6 Splited. In step 6,you can split up the water to give away exactly 6 litres and keep 6 litres

$\endgroup$
  • $\begingroup$ This is an answer to the puzzle that the question describes, but is not an answer to the question itself. The question asks about whether a step in the process is recoverable; that is, whether you can "undo" all steps. You can clearly undo (4,8,0)->(4,3,5) by pouring the third jug back into the second, but it is less obvious how to "undo" the step from, say, (4,3,5)->(7,0,5). If you did that step by accident, can you "recover" from your mistake, or do you need to start over? $\endgroup$ – Dewi Morgan Nov 14 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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