Recientemente, en el recientemente lanzado Puzzling.SE , había un problema sobre los espías que arrojaban piedras a un río que en realidad era bastante desafiante:

Dos espías deben pasarse mutuamente dos números secretos (un número por espía), sin ser notados por sus enemigos. Han acordado un método para hacer esto usando solo 26 piedras indistinguibles de antemano.

Se encuentran en un río, donde hay un montón de 26 piedras. Comenzando con el primer espía, se turnan para arrojar un grupo de piedras al río: el primer espía arroja algunas piedras, luego la segunda, luego la primera otra vez ...

Cada espía debe lanzar al menos una piedra en su turno, hasta que todas las piedras se hayan ido.

Observan todos los lanzamientos y divergen cuando no hay más piedras. Guardan silencio todo el tiempo y no se intercambia información, excepto el número de piedras arrojadas en cada turno.

¿Cómo pueden intercambiar los números con éxito si los números pueden ser del 1 al M?

Su tarea es construir un par de programas spy1y spy2eso puede resolver este problema lo más alto posible M.

Sus programas tomarán un número de cada uno 1a su elección Mcomo entrada. Luego, spy1generará un número que representa el número de piedras que arroja al río, que se ingresará a las spy2cuales también generará un número para ingresar spy1, y así sucesivamente hasta que los números generados se sumen 26. Al final del lanzamiento, cada programa generará el número que cree que tenía el otro programa, que debe coincidir con el número que realmente se ingresó al otro programa.

Su programa debe funcionar para todos los posibles pares ordenados de números (i, j)donde ambos iy jpueden variar de 1a M.

El programa que funcione para los más grandes Mserá el ganador, con la primera respuesta que se publicará rompiendo un empate. Además, otorgaré una recompensa de reputación de +100 a la primera solución para la que se ha demostrado que funciona M >= 2286, y +300 a la primera solución para la que se ha demostrado que funciona M >= 2535.

C #, M = 2535

Esto implementa * el sistema que describí matemáticamente en el hilo que provocó este concurso. Reclamo el bono de 300 repeticiones. El programa prueba automáticamente si lo ejecuta sin argumentos de línea de comandos o con --testun argumento de línea de comandos; para el espía 1, ejecuta con --spy1, y para el espía 2 con --spy2. En cada caso, toma el número que debo comunicar desde stdin, y luego realiza los lanzamientos a través de stdin y stdout.

* En realidad, he encontrado una optimización que hace una gran diferencia (desde varios minutos para generar el árbol de decisión, hasta menos de un segundo); el árbol que genera es básicamente el mismo, pero todavía estoy trabajando en una prueba de eso. Si desea una implementación directa del sistema que describí en otra parte, consulte la revisión 2 , aunque es posible que desee realizar una copia de seguridad del registro adicional Mainy de las mejores comunicaciones entre subprocesos TestSpyIO.

Si quieres un caso de prueba que completa en menos de un minuto, el cambio Na 16y Ma 87.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace CodeGolf
{
    internal class Puzzle625
    {
        public static void Main(string[] args)
        {
            const int N = 26;
            const int M = 2535;

            var root = BuildDecisionTree(N);

            if (args.Length == 0 || args[0] == "--test")
            {
                DateTime startUtc = DateTime.UtcNow;
                Console.WriteLine("Built decision tree in {0}", DateTime.UtcNow - startUtc);
                startUtc = DateTime.UtcNow;

                int ok = 0;
                int fail = 0;
                for (int i = 1; i <= M; i++)
                {
                    for (int j = 1; j <= M; j++)
                    {
                        if (Test(i, j, root)) ok++;
                        else fail++;
                    }
                    double projectedTimeMillis = (DateTime.UtcNow - startUtc).TotalMilliseconds * M / i;
                    Console.WriteLine("Interim result: ok = {0}, fail = {1}, projected test time {2}", ok, fail, TimeSpan.FromMilliseconds(projectedTimeMillis));
                }
                Console.WriteLine("All tested: ok = {0}, fail = {1}, in {2}", ok, fail, DateTime.UtcNow - startUtc);
                Console.ReadKey();
            }
            else if (args[0] == "--spy1")
            {
                new Spy(new ConsoleIO(), root, true).Run();
            }
            else if (args[0] == "--spy2")
            {
                new Spy(new ConsoleIO(), root, false).Run();
            }
            else
            {
                Console.WriteLine("Usage: Puzzle625.exe [--test|--spy1|--spy2]");
            }
        }

        private static bool Test(int i, int j, Node root)
        {
            TestSpyIO io1 = new TestSpyIO("Spy 1");
            TestSpyIO io2 = new TestSpyIO("Spy 2");
            io1.Partner = io2;
            io2.Partner = io1;

            // HACK! Prime the input
            io2.Output(i);
            io1.Output(j);

            Spy spy1 = new Spy(io1, root, true);
            Spy spy2 = new Spy(io2, root, false);

            Thread th1 = new Thread(spy1.Run);
            Thread th2 = new Thread(spy2.Run);
            th1.Start();
            th2.Start();

            th1.Join();
            th2.Join();

            // Check buffer contents. Spy 2 should output spy 1's value, so it's lurking in io1, and vice versa.
            return io1.Input() == i && io2.Input() == j;
        }

        private static Node BuildDecisionTree(int numStones)
        {
            NodeValue[] trees = new NodeValue[] { NodeValue.Trivial };
            for (int k = 2; k <= numStones; k++)
            {
                int[] prev = trees.Select(nv => nv.Y).ToArray();
                List<int> row = new List<int>(prev);
                int cap = prev.Length;
                for (int i = 1; i <= prev[0]; i++)
                {
                    while (prev[cap - 1] < i) cap--;
                    row.Add(cap);
                }

                int[] next = row.OrderByDescending(x => x).ToArray();
                NodeValue[] nextTrees = new NodeValue[next.Length];
                nextTrees[0] = trees.Last().Reverse();
                for (int i = 1; i < next.Length; i++)
                {
                    int cp = next[i] - 1;
                    nextTrees[i] = trees[cp].Combine(trees[i - prev[cp]]);
                }

                trees = nextTrees;
            }

            NodeValue best = trees.MaxElement(v => Math.Min(v.X, v.Y));
            return BuildDecisionTree(numStones, best, new Dictionary<Pair<int, NodeValue>, Node>());
        }

        private static Node BuildDecisionTree(int numStones, NodeValue val, IDictionary<Pair<int, NodeValue>, Node> cache)
        {
            // Base cases
            // NB We might get passed val null with 0 stones, so we hack around that
            if (numStones == 0) return new Node(NodeValue.Trivial, new Node[0]);

            // Cache
            Pair<int, NodeValue> key = new Pair<int, NodeValue>(numStones, val);
            Node node;
            if (cache.TryGetValue(key, out node)) return node;

            // The pair-of-nodes construction is based on a bijection between
            //     $\prod_{i<k} T_i \cup \{(\infty, 0)\}$
            // and
            //     $(T_{k-1} \cup \{(\infty, 0)\}) \times \prod_{i<k-1} T_i \cup \{(\infty, 0)\}$

            // val.Left represents the element of $T_{k-1} \cup \{(\infty, 0)\}$ (using null for the $(\infty, 0)$)
            // and val.Right represents $\prod_{i<k-1} T_i \cup \{(\infty, 0)\}$ by bijection with $T_{k-1} \cup \{(\infty, 0)\}$.
            // so val.Right.Left represents the element of $T_{k-2}$ and so on.
            // The element of $T_{k-i}$ corresponds to throwing $i$ stones.
            Node[] children = new Node[numStones];
            NodeValue current = val;
            for (int i = 0; i < numStones && current != null; i++)
            {
                children[i] = BuildDecisionTree(numStones - (i + 1), current.Left, cache);
                current = current.Right;
            }
            node = new Node(val, children);

            // Cache
            cache[key] = node;
            return node;
        }

        class Pair<TFirst, TSecond>
        {
            public readonly TFirst X;
            public readonly TSecond Y;

            public Pair(TFirst x, TSecond y)
            {
                this.X = x;
                this.Y = y;
            }

            public override string ToString()
            {
                return string.Format("({0}, {1})", X, Y);
            }

            public override bool Equals(object obj)
            {
                Pair<TFirst, TSecond> other = obj as Pair<TFirst, TSecond>;
                return other != null && object.Equals(other.X, this.X) && object.Equals(other.Y, this.Y);
            }

            public override int GetHashCode()
            {
                return X.GetHashCode() + 37 * Y.GetHashCode();
            }
        }

        class NodeValue : Pair<int, int>
        {
            public readonly NodeValue Left;
            public readonly NodeValue Right;

            public static NodeValue Trivial = new NodeValue(1, 1, null, null);

            private NodeValue(int x, int y, NodeValue left, NodeValue right) : base(x, y)
            {
                this.Left = left;
                this.Right = right;
            }

            public NodeValue Reverse()
            {
                return new NodeValue(Y, X, this, null);
            }

            public NodeValue Combine(NodeValue other)
            {
                return new NodeValue(other.X + Y, Math.Min(other.Y, X), this, other);
            }
        }

        class Node
        {
            public readonly NodeValue Value;
            private readonly Node[] _Children;

            public Node this[int n]
            {
                get { return _Children[n]; }
            }

            public int RemainingStones
            {
                get { return _Children.Length; }
            }

            public Node(NodeValue value, IEnumerable<Node> children)
            {
                this.Value = value;
                this._Children = children.ToArray();
            }
        }

        interface SpyIO
        {
            int Input();
            void Output(int i);
        }

        // TODO The inter-thread communication here can almost certainly be much better
        class TestSpyIO : SpyIO
        {
            private object _Lock = new object();
            private int? _Buffer;
            public TestSpyIO Partner;
            public readonly string Name;

            internal TestSpyIO(string name)
            {
                this.Name = name;
            }

            public int Input()
            {
                lock (_Lock)
                {
                    while (!_Buffer.HasValue) Monitor.Wait(_Lock);

                    int rv = _Buffer.Value;
                    _Buffer = null;
                    Monitor.PulseAll(_Lock);
                    return rv;
                }
            }

            public void Output(int i)
            {
                lock (Partner._Lock)
                {
                    while (Partner._Buffer.HasValue) Monitor.Wait(Partner._Lock);
                    Partner._Buffer = i;
                    Monitor.PulseAll(Partner._Lock);
                }
            }
        }

        class ConsoleIO : SpyIO
        {
            public int Input()
            {
                return Convert.ToInt32(Console.ReadLine());
            }

            public void Output(int i)
            {
                Console.WriteLine("{0}", i);
            }
        }

        class Spy
        {
            private readonly SpyIO _IO;
            private Node _Node;
            private bool _MyTurn;

            internal Spy(SpyIO io, Node root, bool isSpy1)
            {
                this._IO = io;
                this._Node = root;
                this._MyTurn = isSpy1;
            }

            internal void Run()
            {
                int myValue = _IO.Input() - 1;
                int hisValue = 1;

                bool myTurn = _MyTurn;
                Node n = _Node;
                while (n.RemainingStones > 0)
                {
                    if (myTurn)
                    {
                        if (myValue >= n.Value.X) throw new Exception("Internal error");
                        for (int i = 0; i < n.RemainingStones; i++)
                        {
                            // n[i] allows me to represent n[i].Y values: 0 to n[i].Y - 1
                            if (myValue < n[i].Value.Y)
                            {
                                _IO.Output(i + 1);
                                n = n[i];
                                break;
                            }
                            else myValue -= n[i].Value.Y;
                        }
                    }
                    else
                    {
                        int thrown = _IO.Input();
                        for (int i = 0; i < thrown - 1; i++)
                        {
                            hisValue += n[i].Value.Y;
                        }
                        n = n[thrown - 1];
                    }

                    myTurn = !myTurn;
                }

                _IO.Output(hisValue);
            }
        }
    }

    static class LinqExt
    {
        // I'm not sure why this isn't built into Linq.
        public static TElement MaxElement<TElement>(this IEnumerable<TElement> e, Func<TElement, int> f)
        {
            int bestValue = int.MinValue;
            TElement best = default(TElement);
            foreach (var elt in e)
            {
                int value = f(elt);
                if (value > bestValue)
                {
                    bestValue = value;
                    best = elt;
                }
            }
            return best;
        }
    }
}

Instrucciones para usuarios de Linux

Necesitará mono-csccompilar (en sistemas basados ​​en Debian, está en el mono-develpaquete) y monoejecutar ( mono-runtimepaquete). Entonces los encantamientos son

mono-csc -out:codegolf31673.exe codegolf31673.cs
mono codegolf31673.exe --test

etc.

Programa de prueba de Python

Supongo que sería útil tener un programa de prueba que pueda verificar que su implementación esté funcionando. Ambos scripts a continuación funcionan con Python 2 o Python 3.

Programa de prueba ( tester.py):

import sys
import shlex
from subprocess import Popen, PIPE

def writen(p, n):
    p.stdin.write(str(n)+'\n')
    p.stdin.flush()

def readn(p):
    return int(p.stdout.readline().strip())

MAXSTONES = 26

def test_one(spy1cmd, spy2cmd, n1, n2):
    p1 = Popen(spy1cmd, stdout=PIPE, stdin=PIPE, universal_newlines=True)
    p2 = Popen(spy2cmd, stdout=PIPE, stdin=PIPE, universal_newlines=True)

    nstones = MAXSTONES

    writen(p1, n1)
    writen(p2, n2)

    p1turn = True
    while nstones > 0:
        if p1turn:
            s = readn(p1)
            writen(p2, s)
        else:
            s = readn(p2)
            writen(p1, s)
        if s <= 0 or s > nstones:
            print("Spy %d output an illegal number of stones: %d" % ([2,1][p1turn], s))
            return False
        p1turn = not p1turn
        nstones -= s

    n1guess = readn(p2)
    n2guess = readn(p1)

    if n1guess != n1:
        print("Spy 2 output wrong answer: expected %d, got %d" % (n1, n1guess))
        return False
    elif n2guess != n2:
        print("Spy 1 output wrong answer: expected %d, got %d" % (n2, n2guess))
        return False

    p1.kill()
    p2.kill()

    return True

def testrand(spy1, spy2, M):
    import random
    spy1cmd = shlex.split(spy1)
    spy2cmd = shlex.split(spy2)

    n = 0
    while 1:
        i = random.randrange(1, M+1)
        j = random.randrange(1, M+1)
        test_one(spy1cmd, spy2cmd, i, j)
        n += 1
        if n % 100 == 0:
            print("Ran %d tests" % n)

def test(spy1, spy2, M):
    spy1cmd = shlex.split(spy1)
    spy2cmd = shlex.split(spy2)
    for i in range(1, M+1):
        print("Testing %d..." % i)
        for j in range(1, M+1):
            if not test_one(spy1cmd, spy2cmd, i, j):
                print("Spies failed the test.")
                return
    print("Spies passed the test.")

if __name__ == '__main__':
    if len(sys.argv) != 4:
        print("Usage: %s <M> <spy1> <spy2>: test programs <spy1> and <spy2> with limit M" % sys.argv[0])
        exit()

    M = int(sys.argv[1])
    test(sys.argv[2], sys.argv[3], M)

Protocolo: se ejecutarán los dos programas espía especificados en la línea de comandos. Se espera que interactúen únicamente a través de stdin / stdout. Cada programa recibirá su número asignado como la primera línea de entrada. En cada turno, el espía 1 emite el número de piedras para lanzar, el espía 2 lee un número de stdin (que representa el lanzamiento del espía 1), y luego repiten (con las posiciones invertidas). Cuando cualquiera de los espías determina que se han arrojado 26 piedras, se detienen y emiten su conjetura para el número del otro espía.

Ejemplo de sesión con un spy1 compatible ( >denota la entrada al espía)

> 42
7
> 5
6
> 3
5
27
<program quits>

Si elige una muy grande M, y se tarda demasiado tiempo para correr, puede cambiar test(para testrand(en la última línea para ejecutar las pruebas al azar. En este último caso, deje el programa en funcionamiento durante al menos unos pocos miles de pruebas para generar confianza.

Programa de ejemplo ( spy.py), para M = 42:

import sys

# Carry out the simple strategy for M=42

def writen(n):
    sys.stdout.write(str(n)+"\n")
    sys.stdout.flush()

def readn():
    return int(sys.stdin.readline().strip())

def spy1(n):
    m1,m2 = divmod(n-1, 6)
    writen(m1+1)
    o1 = readn() # read spy2's number

    writen(m2+1)
    o2 = readn()

    rest = 26 - (m1+m2+o1+o2+2)
    if rest > 0:
        writen(rest)
    writen((o1-1)*6 + (o2-1) + 1)

def spy2(n):
    m1,m2 = divmod(n-1, 6)
    o1 = readn() # read spy1's number
    writen(m1+1)

    o2 = readn()
    writen(m2+1)

    rest = 26 - (m1+m2+o1+o2+2)
    if rest > 0:
        readn()

    writen((o1-1)*6 + (o2-1) + 1)

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print("Usage: %s [spy1|spy2]" % (sys.argv[0]))
        exit()

    n = int(input())
    if sys.argv[1] == 'spy1':
        spy1(n)
    elif sys.argv[1] == 'spy2':
        spy2(n)
    else:
        raise Exception("Must give spy1 or spy2 as an argument.")

Ejemplo de uso:

python tester.py 42 'python spy.py spy1' 'python spy.py spy2'

Java, M = 2535

OK, aquí está mi implementación. En cada paso, un espía hace un movimiento. Cada posible movimiento representa un rango de códigos. El espía elige el movimiento que coincide con su código secreto. A medida que arrojan más piedras, el rango de códigos posibles se reduce hasta que, al final, para ambos espías, solo un código sigue siendo posible de acuerdo con los movimientos que hicieron.

Para recuperar los códigos secretos, puede reproducir todos los movimientos y calcular los rangos de códigos correspondientes. Al final, solo queda un código para cada espía, ese es el código secreto que quería transmitir.

Desafortunadamente, el algoritmo se basa en una gran tabla precalculada con cientos de miles de enteros. El método no podría aplicarse mentalmente con más de 8-10 piedras tal vez.

El primer archivo implementa el algoritmo de Spy. La parte estática codeCountcalcula previamente una tabla que luego se usa para calcular cada movimiento. La segunda parte implementa 2 procedimientos, uno para seleccionar cuántas piedras lanzar, y el otro para reproducir movimientos para ayudar a reconstruir los códigos secretos.

El segundo archivo prueba ampliamente la clase Spy. El método simulatesimula el proceso. Utiliza la clase Spy para generar una secuencia de lanzamientos a partir de los códigos secretos y luego reconstruye los códigos a partir de la secuencia.

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...
    }

}

Como referencia, la matriz codeCount precalculada contiene los siguientes valores:

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]

Esto se relaciona directamente con los conjuntos de Tk de Peter Taylor. Tenemos:

(x,y) in Tk  <=>  y <= codeCount[x]

ksh / zsh, M = 126

En este sistema simple, cada espía arroja dígitos binarios al otro espía. En cada lanzamiento, la primera piedra se ignora, las siguientes piedras son cada bit 0, y la última piedra es el bit 1. Por ejemplo, para lanzar 20, un espía arrojaría 4 piedras (ignorar, 0, 2, agregar 4), luego tira 3 piedras (ignora, 8, suma 16), porque 4 + 16 = 20.

El conjunto de números no es contiguo. 0 a 126 están adentro, pero 127 está afuera. (Si ambos espías tienen 127, necesitan 28 piedras, pero tienen 26 piedras). Luego entran 128 a 158, 159 sale, 160 a 174 entran, 175 salen, 176 a 182 entran, 183 salen, 184 a 186 está adentro, 187 está afuera, y así sucesivamente.

Ejecute un intercambio automático con ksh spy.sh 125 126, o ejecute espías individuales con ksh spy.sh spy1 125y ksh spy.sh spy2 126. Aquí, kshpuede ser ksh93, pdksh o zsh.

EDITAR 14 de junio de 2014: Solucione un problema con algunos coprocesos en zsh. Estarían inactivos para siempre y no podrían salir, hasta que el usuario los matara.

(( stones = 26 ))

# Initialize each spy.
spy_init() {
    (( wnum = $1 ))  # my number
    (( rnum = 0 ))   # number from other spy
    (( rlog = -1 ))  # exponent from other spy
}

# Read stone count from other spy.
spy_read() {
    read count || exit
    (( stones -= count ))

    # Ignore 1 stone.
    (( count > 1 )) && {
        # Increment exponent.  Add bit to number.
        (( rlog += count - 1 ))
        (( rnum += 1 << rlog ))
    }
}

# Write stone count to other spy.
spy_write() {
    if (( wnum ))
    then
        # Find next set bit.  Prepare at least 2 stones.
        (( count = 2 ))
        until (( wnum & 1 ))
        do
            (( wnum >>= 1 ))
            (( count += 1 ))
        done

        (( wnum >>= 1 ))  # Remove this bit.
        (( stones -= count ))
        print $count      # Throw stones.
    else
        # Throw 1 stone for other spy to ignore.
        (( stones -= 1 ))
        print 1
    fi
}

# spy1 writes first.
spy1() {
    spy_init "$1"
    while (( stones ))
    do
        spy_write
        (( stones )) || break
        spy_read
    done
    print $rnum
}

# spy2 reads first.
spy2() {
    spy_init "$1"
    while (( stones ))
    do
        spy_read
        (( stones )) || break
        spy_write
    done
    print $rnum
}

(( $# == 2 )) || {
    name=${0##*/}
    print -u2 "usage: $name number1 number2"
    print -u2 "   or: $name spy[12] number"
    exit 1
}

case "$1" in
    spy1)
        spy1 "$2"
        exit;;
    spy2)
        spy2 "$2"
        exit;;
esac

(( number1 = $1 ))
(( number2 = $2 ))

if [[ -n $KSH_VERSION ]]
then
    eval 'cofork() { "$@" |& }'
elif [[ -n $ZSH_VERSION ]]
then
    # In zsh, a co-process stupidly inherits its own >&p, so it never
    # reads end of file.  Use 'coproc :' to close <&p and >&p.
    eval 'cofork() {
        coproc {
            coproc :
            "$@"
        }
    }'
fi

# Fork spies in co-processes.
[[ -n $KSH_VERSION ]] && eval 'coproc() { "$@" |& }'
cofork spy1 number1
exec 3<&p 4>&p
cofork spy2 number2
exec 5<&p 6>&p

check_stones() {
    (( stones -= count ))
    if (( stones < 0 ))
    then
        print -u2 "$1 is in trouble! " \
            "Needs $count stones, only had $((stones + count))."
        exit 1
    else
        print "$1 threw $count stones.  Pile has $stones stones."
    fi
}

# Relay stone counts while spies throw stones.
while (( stones ))
do
    # First, spy1 writes to spy2.
    read -u3 count report1 || mia spy1
    check_stones spy1
    print -u6 $count

    (( stones )) || break

    # Next, spy2 writes to spy1.
    read -u5 count report2 || mia spy2
    check_stones spy2
    print -u4 $count
done

mia() {
    print -u2 "$1 is missing in action!"
    exit 1
}

# Read numbers from spies.
read -u3 report1 || mia spy1
read -u5 report2 || mia spy2

pass=true
(( number1 != report2 )) && {
    print -u2 "FAILURE: spy1 put $number1, but spy2 got $report2."
    pass=false
}
(( number2 != report1 )) && {
    print -u2 "FAILURE: spy2 put $number2, but spy1 got $report1."
    pass=false
}

if $pass
then
    print "SUCCESS: spy1 got $report1, spy2 got $report2."
    exit 0
else
    exit 1
fi