Java, M = 2535
OK, here is my implementation. At each step one spy makes a move. Each possible move represents a range of codes. The spy chooses the move matching his secret code. As they throw more stones, the range of possible codes reduces until, at the end, for both spies, only one code remains possible according to the moves they did.
To recover the secret codes, you can replay all the moves and compute the corresponding code ranges. At the end, only one code remains for each spy, that is the secret code he wanted to transmit.
Unfortunately, the algorithm relies on a large precomputed table with hundred of thousands of integers. The method couldn't be applied mentally with more than 8-10 stones maybe.
The first file implements the Spy's algorithm. The static part precomputes a codeCount
table that is later used to compute each move. The second part implements 2 procedures, one to select how many stones to throw, the other to replay a moves to help reconstruct the secret codes.
The second file tests the Spy class extensively. The method simulate
simulates the process. It uses the Spy class to generate a sequence of throws from the secret codes and then reconstructs the codes from the sequence.
Spy.java
package stackexchange;
import java.util.Arrays;
public class Spy
{
// STATIC MEMBERS
/** Size of code range for a number of stones left to the other and the other spy's range */
static int[][] codeCount;
// STATIC METHODS
/** Transpose an array of code counts */
public static int[] transpose(int[] counts){
int[] transposed = new int[counts[1]+1];
int s = 0;
for( int i=counts.length ; i-->0 ; ){
while( s<counts[i] ){
transposed[++s] = i;
}
}
return transposed;
}
/** Add two integer arrays by element. Assume the first is longer. */
public static int[] add(int[] a, int[] b){
int[] sum = a.clone();
for( int i=0 ; i<b.length ; i++ ){
sum[i] += b[i];
}
return sum;
}
/** Compute the code range for every response */
public static void initCodeCounts(int maxStones){
codeCount = new int[maxStones+1][];
codeCount[0] = new int[] {0,1};
int[] sum = codeCount[0];
for( int stones=1 ; stones<=maxStones ; stones++ ){
codeCount[stones] = transpose(sum);
sum = add(codeCount[stones], sum);
}
}
/** display the code counts */
public static void dispCodeCounts(int maxStones){
for( int stones=1 ; stones<=maxStones ; stones++ ){
if( stones<=8 ){
System.out.println(stones + ": " + Arrays.toString(codeCount[stones]));
}
}
for( int s=1 ; s<=maxStones ; s++ ){
int[] row = codeCount[s];
int best = 0;
for( int r=1 ; r<row.length ; r++ ){
int min = r<row[r] ? r : row[r];
if( min>=best ){
best = min;
}
}
System.out.println(s + ": " + row.length + " " + best);
}
}
/** Find the maximum symmetrical code count M for a number of stones */
public static int getMaxValue(int stones){
int[] row = codeCount[stones];
int maxValue = 0;
for( int r=1 ; r<row.length ; r++ ){
int min = r<row[r] ? r : row[r];
if( min>=maxValue ){
maxValue = min;
}
}
return maxValue;
}
// MEMBERS
/** low end of range, smallest code still possible */
int min;
/** range size, number of codes still possible */
int range;
/** Create a spy for a certain number of stones */
Spy(int stones){
min = 1;
range = getMaxValue(stones);
}
/** Choose how many stones to throw */
public int throwStones(int stonesLeft, int otherRange, int secret){
for( int move=1 ; ; move++ ){
// see how many codes this move covers
int moveRange = codeCount[stonesLeft-move][otherRange];
if( secret < this.min+moveRange ){
// secret code is in move range
this.range = moveRange;
return move;
}
// skip to next move
this.min += moveRange;
this.range -= moveRange;
}
}
/* Replay the state changes for a given move */
public void replayThrow(int stonesLeft, int otherRange, int stonesThrown){
for( int move=1 ; move<stonesThrown ; move++ ){
int moveRange = codeCount[stonesLeft-move][otherRange];
this.min += moveRange;
this.range -= moveRange;
}
this.range = codeCount[stonesLeft-stonesThrown][otherRange];
}
}
ThrowingStones.java
package stackexchange;
public class ThrowingStones
{
public boolean simulation(int stones, int secret0, int secret1){
// ENCODING
Spy spy0 = new Spy(stones);
Spy spy1 = new Spy(stones);
int[] throwSequence = new int[stones+1];
int turn = 0;
int stonesLeft = stones;
while( true ){
// spy 0 throws
if( stonesLeft==0 ) break;
throwSequence[turn] = spy0.throwStones(stonesLeft, spy1.range, secret0);
stonesLeft -= throwSequence[turn++];
// spy 1 throws
if( stonesLeft==0 ) break;
throwSequence[turn] = spy1.throwStones(stonesLeft, spy0.range, secret1);
stonesLeft -= throwSequence[turn++];
}
assert (spy0.min==secret0 && spy0.range==1 );
assert (spy1.min==secret1 && spy1.range==1 );
// System.out.println(Arrays.toString(throwSequence));
// DECODING
spy0 = new Spy(stones);
spy1 = new Spy(stones);
stonesLeft = stones;
turn = 0;
while( true ){
// spy 0 throws
if( throwSequence[turn]==0 ) break;
spy0.replayThrow(stonesLeft, spy1.range, throwSequence[turn]);
stonesLeft -= throwSequence[turn++];
// spy 1 throws
if( throwSequence[turn]==0 ) break;
spy1.replayThrow(stonesLeft, spy0.range, throwSequence[turn]);
stonesLeft -= throwSequence[turn++];
}
int recovered0 = spy0.min;
int recovered1 = spy1.min;
// check the result
if( recovered0 != secret0 || recovered1 != secret1 ){
System.out.println("error recovering (" + secret0 + "," + secret1 + ")"
+ ", returns (" + recovered0 + "," + recovered1 + ")");
return false;
}
return true;
}
/** verify all possible values */
public void verifyAll(int stones){
int count = 0;
int countOK = 0;
int maxValue = Spy.getMaxValue(stones);
for( int a=1 ; a<=maxValue ; a++ ){
for( int b=1 ; b<=maxValue ; b++ ){
count++;
if( simulation(stones, a, b) ) countOK++;
}
}
System.out.println("verified: " + countOK + "/" + count);
}
public static void main(String[] args) {
ThrowingStones app = new ThrowingStones();
Spy.initCodeCounts(26);
Spy.dispCodeCounts(26);
app.verifyAll(20);
// app.verifyAll(26); // never managed to complete this one...
}
}
For reference, the precomputed codeCount array contains the following values:
1: [0, 1]
2: [0, 1, 1]
3: [0, 2, 1, 1]
4: [0, 3, 2, 1, 1, 1]
5: [0, 5, 3, 2, 2, 1, 1, 1, 1]
6: [0, 8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1]
This related directly to Peter Taylor's Tk sets. We have:
(x,y) in Tk <=> y <= codeCount[x]
Solution means algorithm, or a program, which generates set of dissisions for each (i,j)? – klm123 – 2014-06-13T05:27:36.670
Not one program, but two. They must communicate independently, as in your problem. – Joe Z. – 2014-06-13T06:09:12.897
3Since the programs are going to need to share their decision tree, can we make it one program which takes an argument to say which spy it is? – Peter Taylor – 2014-06-13T09:57:28.510
As long as you can guarantee that each spy communicates independently and there is no extra information exchanged between them. – Joe Z. – 2014-06-13T17:35:28.120
Independently I have verified that 2535 is the information-theoretic max for this problem. I quite strongly believe now that no program can do better. – nneonneo – 2014-06-14T23:11:47.523