# Poniżej podaję wersję "przezroczystą" Juliusz.pl wcześniejszego programu jul.plp. Teraz widzimy detalicznie, jak Jula Wnorowskiego algorytm działa. Na przykład przy 4 więźniach mogło być tak ("new" w outupcie znaczy, że więzień zaczął się liczyć; przedtem mo©l już bywać w pokoju, ale jeszcze nie liczył się):

# /zagadki: perl Juliusz.pl 4
#
# day 1; prisoner 2 - new
# day 2; prisoner 3 - new
# day 3; prisoner 2 - Leader, early gains = 2
#
# day 4; prisoner 2
#
# day 5; prisoner 0 - new
#
# day 6; prisoner 2 - leader; gain = 3
# day 7; prisoner 3
# day 8; prisoner 1 - new
#
# day 9; prisoner 1
# day 10; prisoner 3
# day 11; prisoner 1
# day 12; prisoner 3
# day 13; prisoner 0
# day 14; prisoner 0
# day 15; prisoner 2 - leader; gain = 4

################ program Juliusz.pl ###############

#!/usr/bin/perl
#
# Program: Juliusz.pl
# Author of the Algorithm: Juliusz Wnorowski
# Programmer: Wlodzimierz Holsztynski
# Date: 2011-01-10
#
# Prisoners visit a room, one prisoner per day,
# and leave it with the light on or off. When
# one of them guesses correctly that all of them
# have already visited the room the prisoners
# are freed. In the case of a mistake all of them
# are instantly executed. They can agree in advance
# on a strategy, after which they are not allowed
# to communicate (except via the on/off of the light
# in the room).
#
# This program codes a superb strategy by Juliusz Wnorowski;
# it is a see through version of jul.pl.:

if($s= $ARGV[1]) { srand $s}
else { srand }

use integer;
if ($n = $ARGV[0]) { $nopr =$n }
else { $nopr=5 };     # the number of prisoners

$light=1;
print "\n";
for (1..$nopr)
{   $pr = int(rand $nopr);
    print "day $_; prisoner $pr";
    if($light)
    {   if(!$cnt[$pr])
        {   $cnt[$pr]=$_;
            print " - new"
        }
        else
        {   $light = 0;
            $leader = $pr;
            $gain = $_-1;
            print " - Leader, early gains = ",$gain,"\n"
    }   }
    print "\n"
}
if($light)
{   print "\n\n    Lucky devils won in $nopr days!\n\n";
    exit $nopr
}
elsif(!$cnt[$pr])
{   $light = $cnt[$pr] = 1;
    print "                    - new\n"   }

$day = $nopr;
print "\n";
while($gain < $nopr)
{   $pr = int(rand $nopr);
    print "day ", ++$day, "; prisoner $pr";
    if(!($light||$cnt[$pr]))
    {   $light=1;
        $cnt[$pr]=1;
        print " - new\n"
    }
    elsif(($pr==$leader) && $light)
    {   $light=0;
        print " - leader; gain = ", ++$gain
    }
    print "\n"
}

Tym razem podam iterowaną wersję, która pozwala zastosować algorytm Jula Wnorowskiego do wielu więzień za jednym zamachem. Program podaje średnią liczbę dni potrzebnych do uwolnienia się z więzienia, pry ustalonej liczbie więźniów, tej samej dla każdego więzienia. Właśnie dla 1000 więzień, po 100 więźniów, średnia wyniosła 9375.228, czyli grubo poniżej 100^2. Dla małych parametrów program podaje detaliczne informacje. Dla liczby więzień niewiększej niż 40, podaje informację końcową dla każdego więzienia. Powiedzmy, że działamy w pliku /zagadki. Wtedy program wywołuje się następująco:

/zagadki perl iterJulJul.ppl 100 40 7898

gdzie pierwszy argument 100, to liczba więźniów w każdym więzieniu, drugi argument 40 to liczba więzień, a trzeci jest ziarnem losowym. Można dać tylko od 0 do 3 pierwszych argumentów, i pominąć pozostałe. Dane wywołanie daje output:

PRISON 0 -- free on day 9243
PRISON 1 -- free on day 9394
PRISON 2 -- free on day 9061
PRISON 3 -- free on day 11124
PRISON 4 -- free on day 9606
PRISON 5 -- free on day 10021
PRISON 6 -- free on day 7623
PRISON 7 -- free on day 10003
PRISON 8 -- free on day 10143
PRISON 9 -- free on day 8225
PRISON 10 -- free on day 9552
PRISON 11 -- free on day 10241
PRISON 12 -- free on day 9994
PRISON 13 -- free on day 7747
PRISON 14 -- free on day 10995
PRISON 15 -- free on day 8567
PRISON 16 -- free on day 7942
PRISON 17 -- free on day 10301
PRISON 18 -- free on day 8319
PRISON 19 -- free on day 8697
PRISON 20 -- free on day 10312
PRISON 21 -- free on day 10223
PRISON 22 -- free on day 10223
PRISON 23 -- free on day 8628
PRISON 24 -- free on day 10561
PRISON 25 -- free on day 8565
PRISON 26 -- free on day 8244
PRISON 27 -- free on day 6983
PRISON 28 -- free on day 8000
PRISON 29 -- free on day 9345
PRISON 30 -- free on day 9854
PRISON 31 -- free on day 9366
PRISON 32 -- free on day 7875
PRISON 33 -- free on day 9565
PRISON 34 -- free on day 10443
PRISON 35 -- free on day 10183
PRISON 36 -- free on day 8362
PRISON 37 -- free on day 8132
PRISON 38 -- free on day 9248
PRISON 39 -- free on day 8289

    Average stay in prisons: 9229.975 (total 369199) days

A teraz kod (iterowanego) algorytmu Jula:

#!/usr/bin/perl
#
# Program: iterJulJul.pl
# Author of the Algorithm: Juliusz Wnorowski
# Programmer: Wlodzimierz Holsztynski
# Date: 2011/01/10-12
#
# Prisoners visit a room, one prisoner per day,
# and leave it with the light on or off. When
# one of them guesses correctly that all of them
# have already visited the room the prisoners
# are freed. In the case of a mistake all of them
# are instantly executed. They can agree in advance
# on a strategy, after which they are not allowed
# to communicate (except via the on/off of the light
# in the room).
#
# This program codes a superb strategy by Juliusz Wnorowski;
# it is a see through version of jul.pl., like Juliusz.pl;
# it also allows iteration. For large parameters, only the
# final results are printed.

if($s = $ARGV[2]) { srand $s}
else { srand }
if($n = $ARGV[1]) { $loop = $n }
else { $loop = 10 }

use integer;
if ($n = $ARGV[0]) { $nopr = $n }
else { $nopr=5 };     # the number of prisoners

if(($loop < 9)&&($nopr < 9)) { $show=1 }
if($loop < 41) { $peek = 1 }
$total = 0;   # the total number of days
print "\n";
PRISON: for ($k=0; $k<$loop; ++$k)
{

$light=1;
print "\n    PRISON $k\n\n" if $show;
for (1..$nopr)
{   $pr = int(rand $nopr);
    print "day $_; prisoner $pr" if $show;
    if($light)
    {   if(!$cnt[$pr])
        {   $cnt[$pr]=$_;
            print " - new" if $show
        }
        else
        {   $light = 0;
            $leader = $pr;
            $gain = $_-1;
            print " - Leader, early gains = ",$gain,"\n" if $show
    }   }
    print "\n" if $show
}
if($light)
{   print "PRISON $k - lucky devils won in $nopr days!\n" if $peek;
    $total += $nopr;
    for (0..$nopr-1) { $cnt[$_]=0 }
    next PRISON
}
elsif(!$cnt[$pr])
{   $light = $cnt[$pr] = 1;
    print "                    - new\n" if $show
}

$day = $nopr;
print "\n" if $show;
while($gain < $nopr)
{   $pr = int(rand $nopr);
    ++$day;
    print "day ", $day, "; prisoner $pr" if $show;
    if(!($light||$cnt[$pr]))
    {   $light=1;
        $cnt[$pr]=1;
        print " - new\n" if $show
    }
    elsif(($pr==$leader) && $light)
    {   $light=0;
        ++$gain;
        print " - leader; gain = ", $gain if $show
    }
    print "\n" if $show
}                          # end of a daily loop
print "PRISON $k -- free on day $day\n" if $peek;
$total += $day;
for (0..$nopr-1) { $cnt[$_]=0 }
} # end of an iteration global loop

no integer;
$aver = $total/$loop;
print "\n    Average stay in prisons: $aver (total $total) days\n\n"

######### end #########

Dowiedziałem się od @witzara (via @ww - obu bardzo dziękuję za informację), że algorytm odkryty na nowo i niezależnie przez Jula, był znany wcześniej (ale chyba nieco niedoszlifowany). W każdym razie (poza kwestią doszlifowania) widzę dwa drobne ulepszenia. Tu napiszę o pierwszym, wcześniej przeze mnie anonsowanym. Każdy więzien może sobie zapamiętywać, minimum ilu więźniów - zgodnie z tym co zaobserwowal - bylo w pokoju. Gdy zauważy, że 100, to złoży oświadczenie, nie czekając na leadera, i więźniowie wyjdą na wolność wcześniej. Zajdzie to "astronomicznie" rzadko, ale gdy się wydarzy, to czas w więzieniu skróci się przeciętnie o 100 dni. Na buzzie wyjaśniłem dlaczego, ale jest to raczej oczywiste. W sumie średnia oczekiwania poprawi się ledwo mikroskpijnie.

Żeby nastąpiło polepszenie, to w pierwszym stadium więzien, który był w pokoju tuż przed ustanowieniem lidera ma szansę wiedzieć o każdym nowym więźniu, zapalającym światło w pokoju, przed liderem - szansa na to jest znikoma, ale istnieje. wtedy taki więzień może oznajmić pojawienie się w pokoju ostatniego więźnia.

Trywialny przykład dostajemy dla 2 więźniów (zamiast 100). Ba! wtedy nielider zawsze może skrócić niewolę, bo gdy wejdzie do pokoju, to może ogłosić wygraną. Podam mniej trywialny przykład:

PRZYKŁAD: Liczba więźniów = 3 (zamiast 100). Wizyty:

0 0 1 0 2 1 (!) 1 1 2 2 2 1 2 1 2 1 2 1 1 1 1 2 2 1 0

Liderem zostal gracz 0 przy swojej drugiej wizycie. Wykrzyknik pokazuje moment w ktorym gracz 1 jest w stanie ogłosić zwycięskie wyjście na wolność. Przy podanym ciągu, w ramach czysto liderowego algorytmu, na lidera trzebaby czekać jeszcze długo. Przykład jest nieco przesadny, na ogół czekanie na lidera  byloby krótsze. Poniższa tabelka podaje szansę niedoczekania się lidera przez kolejną liczbę dni:

        0.66667   0.44444   0.29630   0.19753   0.13169
        0.08779   0.05853   0.03902   0.02601   0.01734
        0.01156   0.00771   0.00514   0.00343   0.00228
        0.00152   0.00101   0.00068   0.00045   0.00030

Widzimy, że szansa na niepokazanie się lidera 0 po więźniu 1 aż przez 10 dni (lub dłużej) wynosi mniej niż 1 na 50.

Drugie ulepszenie algorytmu z liderem jest nieco istotniejsze, bo daje lepszy wynik niemal za każdym razem - co prawda tylko rzędu chyba 60-70 (tak na oko, może nawet ciut ponad 70). Ulepszenie polega na tym, że etap wyłaniania lidera wcale nie musi trwać aż 100 dni. Można na przykład umówić się, że (przy 100 więźniach) albo lider starą metodą wyłoni się w 25 dni, albo w przeciwnym wypadku, gdy gracz dnia 26 zastanie światło, to uznaje się za lidera (nikt inny tego nie uczyni). Poza tym wszystko w zasadzie będzie tak samo. Z jednej strony prawie zawsze zyskujemy 75 dni, gdyż prawie zawsze lider wyłoni się w ciągu 25 dni. W pozostałych, rzadkich przypadkach, strata jest niewielka.

Oto, przy 100 więźniach, tabela szans na niewyłonienie się lidera w ciągu k dni (k = 1 ... 40):

1     0.99    0.9702    0.94109    0.90346
0.85828   0.80678   0.75031   0.69028   0.62816

0.56534   0.50315   0.44277   0.38521   0.33128
0.28159   0.23654   0.19633   0.16099   0.13040

0.10432   0.08241   0.06428   0.04950   0.03762
0.02821   0.02088   0.01524   0.01097   0.00779

0.00545   0.00376   0.00256   0.00171   0.00113
0.00074   0.00047   0.00030   0.00018   0.00011

Widzimy, że szansa na niewyłonienie się lidera (w "klasycznym" podejściu) w ciągu 25 dni jest mniejsza niż 1 na 25. Na niewyłonienie się w ciągu 30 dni - mniejsza niż 1 na 100 (poniżej 1 procenta).