2
$\begingroup$

You have a tanker that can hold any amount of water. You have $n$ taps that either let in or let out water. The rate of flow of water (in $ml/min$) for each tap is given by $f_n$ (positive for inflow, negative for outflow). The tank initially has $x\ ml$ and you must bring it to a state of $y\ ml$.

Values of $f_n$ are real numbers and $n,x,y$ are integers. Taps are opened or closed only once every minute: no action can be taken except when the second hand of the clock is at $0$. Any number of taps can be closed or opened simultaneously. All these values are given to you.

Q1: What is the fastest algorithm to find a solution (or find that one does not exist)?

Q2: Such questions when put to other humans are usually not that hard (as compared to those put to a computer). Can you suggest some tricks that a person can use to solve such questions faster?

Q3: What if there are initially $k$ taps open and when you open taps, you must also simultaneously close taps, such that exactly $k$ taps remain open throughout.

(I hope I haven't clubbed too many questions together. This Q may require some serious math, please explain your conclusions in simple words also.)

$\endgroup$

closed as off-topic by Engineer Toast, Irishpanda, Alexis, Ric, AJL Nov 12 '15 at 21:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Engineer Toast, Irishpanda, Alexis, Ric, AJL
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I'm not entirely sure I understand t he bit on the time setting.. do you mean that 'state changes' always happen on the minute, an never in between those time slots? $\endgroup$ – Tim Couwelier Oct 1 '15 at 15:42
  • $\begingroup$ Water flows in at a fixed rate, but you must attain the final state at the end of a minute. For example, you cannot fill $3\ ml$ in an empty tank using a tap that fills $2\ ml/s$ because this state is achieved in the middle of a minute and you cannot shut the tap immediately. $\endgroup$ – ghosts_in_the_code Oct 1 '15 at 15:44
  • $\begingroup$ IMO asking for the fastest algorithm to perform a computation might be off topic for puzzling.SE $\endgroup$ – Julian Rosen Oct 1 '15 at 16:27
  • $\begingroup$ Taps are opened or closed only in between two consecutive minutes. Does this mean we are allowed to open/close taps every 60 seconds? $\endgroup$ – Rohcana Oct 1 '15 at 19:13
  • $\begingroup$ @Anachor Yes, no action is to be taken in the middle of a minute. $\endgroup$ – ghosts_in_the_code Oct 2 '15 at 6:16
1
$\begingroup$

Q1

In this specific context I would approach the problem as follows:

(0) What is given?

  • n taps;
  • Fn is a set representing the rate of flow of water, where Fn > 0 is inflow and Fn < 0 is outflow;
  • x is the initial state;
  • y is the end (goal) state.

(1) What can we deduce?

  • delta_xy = x - y, where delta_xy > 0 means that it requires outflow; or delta_xy < 0 means that it requires inflow.

(2) What is the stopping condition?

  • delta_xy = 0

(3) Constraints and Edge cases:

  • Cannot remove more than what is contained, and cannot overflow.
  • The set Fn is constructed such that from x, it is possible to attain end state y.

i.e.: - n = 2 - Fn = {-5, +5} - x = 3, y = 7.

It should be obvious that given these initial conditions it is impossible to attain end state y, given initial state x and set Fn.

Algorithm

One could interpret this problem as a Subset Sum Problem; where we ask the following question:

given a set of integers Fn and an integer delta_xy , is there any non-empty subset that sums to an integer Z , such that Z + delta_xy = 0?

Multiple solutions exists already for this problem, but in this particular case I would opt for a solution that employs Dynamic Programming. We define a function Q(i,s) that returns a boolean corresponding to the answer of the following question:

is there a non-empty subset of {x_1, ... , x_i} whose sum is s, where s <= Z if delta_xy < 0; or s >= Z if delta_xy > 0?

By computing this function and storing the results, as prescribed by the DP technique, eventually all the possible result of the function will be pre-computed and the complexity will become linear. As per this article, the time complexity is O(sN) where s is the sum we are trying to find, in this case Z which is proportional to delta_xy; and N is the size of the set, or the number of taps in this case.

At every cycle (or minute) we alter the value of Z for the next cycle, which ensure eventual completion, given that the subset respects the constraints. It is possible to analyze the subset to ensure eventual completion prior to starting the algorithm itself.

$\endgroup$
0
$\begingroup$

Mostly a train of thought answer:

Generally, when searching for values out of a group to fit another value, I tend to take it in proportions: is there some value that is close to my end value, are the options finer or coarser, can I combine options to make new options, etc.

Q3 is likely the hardest for both humans and computers, since you have to substitute a lot. I suppose it's a bit like the original question, only working with differences instead of values.

$\endgroup$

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