Tenali Rama explains alldifferent constraint

King is fond of puzzles and generous in rewarding  puzzle solvers. Rama zealously guards king's wealth by attempting to prove the visiting  puzzle solvers wrong. 

The puzzle is

You have 10 bags of coins, each consisting of 100 rupee coins. One entire bag is counterfeit, but you do not know which one. You do know the weight of a genuine rupee coin, say 1 gram, and you are also told that each counterfeit coin weighs one gram more. You may weigh the coins on a pointer scale. You are allowed to weigh only once. How do you identify the counterfeit coins? Will your method work if it is 100 bags instead of 10 with only one counterfeit bag again?

The visitor solves it by a solution he obtained by the mercy of Namagiri, the consort of Narasimha and claims that is the only solution. Tenali Rama contests the claim by  producing another solution.

Visitor's solution: Take 1, 2, 3,....10 coins from the bags and mark them according to the coins taken. Weigh the coins and the difference in weight between the actual and expected weight gives away the counterfeit bag.

Rama's solution: Take 2, 4, 6,....20 coins from the bags and mark them according to the coins taken. Weigh the coins and the difference in weight between the actual and expected weight gives away the counterfeit bag.

Rama explains that it is necessary and sufficient for any pair to have different numbers so that the sequence of 10 numbers is a solution. He predicts there will be a survey paper in 21st century on alldifferent constraint.

The visitor gets only half the reward because his uniqueness claim is wrong. 

An aside:

A quote from "The Science of Programming" by Gries

"I once listened to two computer scientists discuss exponentiation talk right past each other; each

thought he was talking about the exponentiation routine, not knowing

that the other existed."

Gries himself is guilty by the very title of the book without mentioning alternative scientific approaches like logic programming and a computer language like PROLOG.

Tenali Rama's idea defeated by randomization

I concoct another story to tell my future grandchildren.

King is fond of  poetry. He will reward any poet who produces a poem not known to his court poets. Tenali Rama can recite any poem after listening to it once (EkaSandhagrahi). There are five others who  are DviSandhagrahi, Trisandhagrahi etc. among them. They come to an agreement to recite any poem heard from the visiting poet by volunteering in the order of their abilities. This works. King always comes to the conclusion his poets have known the poem all along and sends away the visiting poet. This creates a commotion among the outside poets. They go to guntur gambli who is a poet as well as a gambler. He hates to visit king's court but yields to the pressure of his friends.

He thinks hard and comes up with a plan to teach the clique of court poets a lesson. His poem is all about the virtues of the king and how the king is favored by the gods in any gamble he accepts.  Guntur Gambli requests the King that the order of the poets to recite the poem be determined by throws of dice. Tenali Rama protests saying God does not play dice. King, high on the praise showered on him by Gambli overrules Rama and   finds his court poets failing to recite the poem. Gambli walks away with a reward and the court poets give up their pretensions to omniscience.

Tenali Rama, a software engineer from 16th Century Andhra

I concocted a story to tell my future grandchildren based on a mathematical problem discussed in a previous post

Tenali Rama (T) and his King Krishnadevaraya (K) decide to send a culture-warrior to one neighboring country. K says he has too many fit for the job. T says he knows a few from his native place Tenali.  A  pool is formed by mixing the cards with the names of candidates and  K and T.

King suggests picking randomly two cards and repeating the following and the winner for the job is the one remaining in the end.

If both belong to same (either K or T), throw them out and put in a new card from K. Notice K has a lot of people for the job.

If both K and T cards turn up, T gets to put back the T card and King throws away K card.

King lets Tenali Rama to  choose the number of T cards to start with. He is confident he can overwhelm with K cards. K always loses in spite of this because of clever choice of Rama.

King thinks hard and comes up with an idea. He tells Rama that he too knows a few other people from Tenali and adds equal number of T cards to whatever number Rama chooses.

Now King wins all the time. We all know why.

We established that the number of black beans does not matter at all in the coffee bean problem if all that we are interested in is color of the bean remaining at the end of the process. Neither does the random choice of the two beans has any effect on the number of steps in the process or on the outcome we are interested in. Only thing that matters is the parity of the number of white beans that remains invariant before, during, and after the process.

The correspondence here is (K = Black Bean) and (T = White Bean).
Tenali Rama always starts the game with an odd number of T cards and wins.
King gets it after a lot of thinking and proposes a change to make the starting number of T cards even. Now no chance for Tenali Rama. King always wins.

The Coffee Can Problem from "The Science of Programming" by Gries

" A coffee can contains some black beans and
white beans. The following process is to be repeated as long as possible.
Randomly select two beans from the can. If they are the
same color, throw them out, but put another black bean
in. (Enough extra black beans are available to do this.)
If they are different colors, place the white one back into
the can and throw the black one away.

Execution of this process reduces the number of beans in the can by one.
Repetition of the process must terminate with exactly one bean in the can,
for then two beans cannot be selected. The question is: what, if anything,
can be said about the color of the final bean based on the number of
white beans and the number of black beans initially in the can?"

When I came across this problem in 1984, I reasoned as follows:
If the can has (1b, 1w)  then final bean is white.
If the can has (2b, 1w)  then final bean is white because after the first draw the  state is (1b, 1w).
If the can has (3b, 1w)  then final bean is white because after the first draw the  state is (2b, 1w).

I stopped and looked at it and said to myself maybe I can prove something here by mathematical induction.
If the can has (nb, 1w)  then final bean is white because after the first draw the  state is ((n-1)b, 1w).
By similar reasoning I could prove
If the can has (nb, 0w)  then final bean is black because after the first draw the  state is ((n-1)b, 0w).

That is nice. Becoming a bit bold,
Starting from  (0b, 2w) first  draw results in (1b, 0w) i.e black in the end.
Starting from  (1b, 2w)  first  draw results in either  (2b, 0w)    or (0b, 2w)  resulting in black in the end.
Starting from  (2b, 2w) first  draw results in either (3b, 0w) or (1b, 2w) resulting in black in the end.
Starting from  (3b, 2w) first  draw results in either (4b, 0w) or (2b, 2w) resulting in black in the end.

By mathematical induction   I could prove
 If the can has (nb, 2w) first  draw results in either ((n+1)b, 0w) or ((n-1)b, 2w) resulting in black in the end.  

These three results together form the theorem of irrelevance of number of black beans. I noticed another regularity. Starting with even (odd) number of white beans results in black (white) in the end. 

By mathematical induction I could prove for any even number
Starting from  (1b, (2*n)w) first  draw results in either (2b, (2*n-2)w) or (0b, (2*n)w) resulting in black in the end.
Similarly for any odd number 
 Starting from  (1b, (2*n+1)w) first  draw results in either (2b, (2*n-1)w) or (0b, (2*n+1)w) resulting in black in the end.

I satisfied myself this is mathematically correct and test cases helped to get the feel for the result.

Gries differs.
"It doesn't help much to try test cases! It doesn't help to see what happens
when there are initially I black bean and I white bean, and then to see
what happens when there are initially 2 black beans and one white bean,
etc. I have seen people waste 30 minutes with this approach.

Instead, proceed as follows. Perhaps there is a simple property of the
beans in the can that remains true as beans are removed and that,
together with the fact that only one bean remains, can give the answer.
Since the property will always be true, we will call it an invariant. Well,
suppose upon termination there is one black bean and no white beans.
What property is true upon termination, which could generalize, perhaps,
to be our invariant? One is an odd number, so perhaps the oddness of the
number of black beans remains true. No, this is not the case, in fact the
number of black beans changes from even to odd or odd to even with
each move. But, there are also zero white beans upon termination
-perhaps the evenness of the number of white beans remains true. And,
indeed, yes, each possible move either takes out two white beans or leaves
the number of white beans the same. Thus, the last bean is black if ini-
tially there is an even number of white beans; otherwise it is white."

That was the first time I heard of importance of  invariant.  It is definitely helpful if we can find such properties. Test cases do help us in getting the feel. Is not Gries himself doing the sort of reasoning he discounts in the previous paragraph?

I leave it to the readers to comment on this.

rain array

You have an array of integers, for example: [ 9 8 7 6 2 ].

You graph the values of the array on the y-axis and the index on the x-axis as a bar graph.

Rain falls on the graph. The water collects in any valleys in the graph, and falls off any edges.

In the example array above no water collects because it all falls to the left and right. In [ 3 1 3 ] We get 2 units of water since it collects in the valley between the two 3 bars.

Devise an algorithm to determine how much water is collected by an array. 

Input: Array of integers

Output: Water collected when rain falls on graph

def rain(l=[]):
    result,  leftmaxSoFar, rightmaxSoFar  = 0,  0, 0
    leftMaxList = [0 for i in range(len(l))]
    rightMaxList = [0 for i in range(len(l))]
    capacity = [0 for i in range(len(l))]

    for i in range(len(l)):
        leftMaxList[i] =  leftmaxSoFar
        rightMaxList[len(l) -1 -i]  = rightmaxSoFar
        if l[i] > leftmaxSoFar :
           leftmaxSoFar = l[i]
        if l[len(l) -1 -i] > rightmaxSoFar:
           rightmaxSoFar = l[len(l) -1 -i]
            
    for i in range(len(l)):
        capacity[i] =  min(leftMaxList[i], rightMaxList[i]) -l[i]
        result = result if capacity[i] < 0 else result+capacity[i]
    return result

print rain([3, 1, 3])

print rain( [ 9, 8, 7, 6, 2 ])

Banana Boat Problem

Problem

I am 100 miles from my destination market along a river. To start with, I have 300 bananas and a boat that can hold me and up to 100 bananas. I would like to deliver as many bananas as possible to the market. I may safely leave bananas at the edge of the river and load/unload bananas at no cost. However, when I row with bananas in my boat I end up eating one banana (from among those in the boat) for every one mile (either upstream or downstream). What is the maximum number of bananas that can be delivered to the destination market?

Approaches to Solution by KRU, SRU, SRI, and SUR

Knowledge, Reason, and Understanding (KRU)

Kru's approach is  to reason  about the problem using background knowledge in English and Math to arrive at understanding of the solution.

1. I gain no advantage by taking less bananas in the boat when the boat can carry more because the bananas to be eaten do not depend on the bananas carried but only on the miles traveled.
2. There are no trips less than a mile.
3. Fully loaded boat trips are preferable though not always possible. This follows from one and the fact that in between at some mile, the number of bananas available  may turn out to be less than the capacity of the boat.

Exploring Solutions

Planning just one trip straight to the destination results in no bananas to sell. I load the boat with 100 bananas and I have none left by the time I reach the market as I have to eat one per mile.

I could make a stop at 50 miles  to drop off a few bananas and return to the origin for more. But the boat can only hold a 100 and I would use them up making my way to the 50 mile mark and back in the first 2 round trips. The last trip from origin to 50 mile mark is upstream only and going back is not necessary because no bananas are left at the origin. I bring 50 bananas to the 50 mile mark. After reaching the destination, I still have none left to sell because I need to eat 50 bananas for traveling 50 miles.

Stopping at 25 mile marks
What if I moved all the bananas to the 25 mile first, then the 50, 75 and 100 mile marks?

I load the boat fully and head to the 25 mile mark. The round trip costs 50 bananas but I manage to leave 50 at the shore and make it back to the origin. I can repeat the same process: eat 50 bananas in transit and add 50 bananas to the 25 mile mark. On the final trip, I eat only 25 bananas, because there is no reason to return to the origin. At this point, I have 50 + 50 + 75  bananas at the 25 mile mark.

Getting to the 50 mile mark from the 25 mile mark costs me 50 bananas for the first boat load and 25 bananas for the second. This leaves me with 100 bananas at mile 50. Now I can make it to the market and sell 50.

Can I do better?

Stopping at 10 mile marks
To get to the first 10 mile mark, it costs 50 bananas leaving me with 250. From there to the 20 mile mark, it is another 50 in cost leaving me with 200. To the 30 mile mark it costs only 30 leaving 170. To the 40 mile mark  I can make it with 140. Similarly, I have 110 at the 50 mile mark. If I insist on taking all the 110 bananas, I have to make one round trip and one upstream trip eating 30 bananas and getting only 80 to the 60 mile mark.  It is possible to do better by setting aside 10 bananas and taking just one upstream trip resulting in 90 bananas at 60 mile mark. I can make it to the market with only 50 to sell.

This guess-and-check methodology seems stuck at 50.
Why make an arbitrary assumption about intermediate stops?
Let me explore  answers to a fundamental question.

What is the best thing to do for the first mile?

How many fully loaded  boat trips are possible? 3. It is possible to reach the first mile with 5 bananas loss, The 2 round trips plus one upstream trip have to be taken. More trips would be wasteful. I lose more bananas. Less trips will result in less bananas being moved. The same reasoning applies to the second mile.

How many miles with loss of 5 per mile?
20. After that it is only loss of 3 per mile.

How far can we push at the 3 mile rate?
33 more miles. At the end of 53 miles 101 bananas are left. we have 47 miles to go to the destination and 101 bananas, then we can start with only 100 bananas and get only 53 to the destination. The best we can do at the end of 54 miles is 99. And now it is all the way to market having 53 bananas to sell.

Is there a better solution?
At every mile, there is no better way of getting more bananas to the next mile. That is sufficiently convincing argument. That is a proof of optimal nature of the solution found.

How to prove that 54 is not optimal?
To have    54 for the market I need to have a minimum of 100 bananas at  54 mile.
To have  100 bananas at  54 mile I need to have a minimum of 199 bananas at  21 mile.
To have  199 bananas at  21 mile I need to have a minimum of 204 bananas at  20 mile.
To have  204 bananas at  20 mile I need to have a minimum of 299 bananas at  1 mile.
To have  299 bananas at  1 mile I need to have a minimum of 306 bananas at  0 mile.

54 to the market is not even feasible given that at starting point I have only 300 bananas.
Similar argument holds for any number greater than 54.
52 or less is definitely feasible but not optimal.
53 is maximum achievable subject to constraints of the problem.

What can I learn from this one successful numerical example to solve the problem with different numbers for total bananas, boat capacity,  and distance ?
High School Algebra is sufficient.
I can think of  a few general statements using \(t\), \(c\), \(d\) for total bananas, boat capacity,  and distance respectively.  (t / c) stands for integer division. (1/2) is 0 and (5/3) is 1.

1. If origin is the destination, then all \(t\) bananas are for sale.
2. If a partially loaded boat trip is not necessary because it is not worth making a roundtrip for bananas less than 3,  then only  \(c * (t / c)\) bananas are carried in \(( 2 * (t / c) - 1)\) trips.  \(c * (t / c) - ( 2 * (t / c) - 1)\) will reach the next mile.  This rule is a generalization of my experience with 101 bananas left at 53 mile mark and 300 bananas from the origin. 
3. If a partially loaded  boat trip is necessary then all the  bananas are carried in \(( 2 * (t / c) + 1)\) trips and \(t  - ( 2 * (t / c) + 1)\)  bananas will reach the next mile. This rule is a generalization of my experience  with 99 bananas left at 54 mile mark and 295 bananas left at 1 mile mark. 

Suitable Recursion Unit (SRU)

Sru's approach is to represent Kru's understanding  using Recursion. Notice the straightforward translation of Kru's English and Math into  python 2.7 function.

def bananaBoat(t, c, d):
    if d == 0:
        return t
    if c*(t/c)==t or c*(t/c) == t - 1 or c*(t/c) == t - 2 :
        return  bananaBoat(c*(t/c) - (2*(t / c) - 1), c, d - 1)
    else:
        return  bananaBoat(t - (2*(t/c)+1), c, d - 1)
        
print   bananaBoat(16, 3, 2)     #Answer is  3
print   bananaBoat(45, 15, 10)   #Answer is 13  
print   bananaBoat(300, 100, 100)#Answer is 53

Startup Relevant Ideas (SRI)

Sri is always interested in problem solving ideas relevant for society at large. Given mobile phones for all involved, banana farmers and boat operators how can the startup provide a reliable service of letting the participants to know who is available where using Google cloud service?  What is all needed to make this little python program into industrial-strength software?

Symbolic-Numeric Unification Research (SUR)

A lot of research results are available from Economics, Operations Research, and Computer Science about the use of heuristics. We implicitly used the free disposal assumption economists typically make.

A discrete optimization problem

What is the minimum of the absolute values of a sorted array of  integers?
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 }; the answer is 2.
 The code is based on a slight twist to binary search.

public class MinAbs {
public  int cal(int[] a ){
return recurscal( a,  0,  a.length - 1);
}

private  int recurscal(int[] a,  int begin, int end){
assert (end >= begin);
   if (end == begin) return Math.abs(a[begin]);
if ((end - begin) == 1)
return Math.min(Math.abs(a[begin]), Math.abs(a[end]));

final int middle = begin + (end - begin)/2;

//  on downward slope, the new interval is middle to end

if  (   (Math.abs(a[middle - 1] ) >= Math.abs(a[middle]))
     && (Math.abs(a[middle + 1] ) <= Math.abs(a[middle]))
       )   return recurscal(a,  middle, end);

//  on upward slope, the new interval is begin to middle.
if  (   (Math.abs(a[middle - 1] ) <= Math.abs(a[middle]))
     && (Math.abs(a[middle + 1] ) >= Math.abs(a[middle]))
)return recurscal(a,  begin, middle);

// No more testing. Middle is the answer.
return Math.abs(a[middle]);

}

public static void main(String[] args) {
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 };

MinAbs mia = new MinAbs();
                System.out.println(mia.cal(ia));
}

}