hakank.blogg

Jag tänkte väl att det skulle kunna föranleda en programmeringsinsats i ett språk med lustiga bokstäver :)

Även jag satt med papper och penna, när jag väl kom på att det även finns ett antal assymetriska lösningar. Och slutade när jag inte kom på fler. Vad som vore intressant är om det går att få fram alla _egentliga_ lösningar, alltså där rotationer och speglingar är borträknade. Där får du nästa utmaning :)

Off topic - jag klickar alltid i att du ska komma ihåg mig. Eller ja, din blogg alltså. När jag lämnar kommentarer. Men det gör den aldrig.

Hakke: Tack för att du gav mig ytterligare en utmaning. Jag är inte säker på att jag har tagit emot den ännu. :-) [En analys av begreppet utmaning får vara så länge, möjligen tills den mognar som en fin ost, whisky eller rött vin.]

Men håller naturligtvis med dig om att rotations-/speglings-fria lösningar vore önskvärda.

Ang. off topic-frågan: har du månne slagit av kakorna i din brynare? Du kan testa att ta bort dem för sajten och sedan skriva en fin kommentar igen. (Jag har själv inte några problem med slika ihågkomster.)

"Man kan möjligen misstänka att Fredrik nu kommer att skriva ett mycket elegantare Python-program för detta problem."

Jag antar att man skulle kunna få till något rätt elegant om man korsar http://pyclips.sourceforge.net/ med http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/303057, fast resultatet (minus all klisterkod) skulle nog se ut ungefär som ditt eclipse-program. Det skulle säkert också gå att sno ihop en enkel constraint-lösare just för detta problem, fast den energin har jag inte denna dag.

Vill du ha Python-kod för det andra problemet (dom hundra nun^H^H^Hfångarna) så kan jag däremot stå till tjänst.

"Seseman's Convent Problem" - jo man tackar! Tack också för alla intressanta kommentarer och för att ni lagt ner så mycket tid på detta. Undrar vad Seseman skulle ha sagt? En anmärkning bara: vad är det för mening med att ha celler med bara 1 person om det hela går ut på att smuggla in Karlar?

Bengt: Med tanke på att det är 4-8 karlar på 24 svältfödda nunnor kanske det är karlarna som behöver enmansrummen för vila och återhämtning. Hämta andan helt enkelt. Eller syndernas förlåtelse. :)

Håkan: Off-topic: Jag kör MSIE och tillåter kakor på både hem- och jobbdator. Har haft samma problem på båda sedan ett par veckor tillbaks.

Fredrik: Tack för länktipsen. Ska kolla in dem vidare.

Jag hittade Python-constraint som verkar vara snabbt, i alla fall på seseman-problemet och de exempel som följer med. Programmet seseman.py blev mycket riktigt ganska likt Eclipse-programmet.

När det gäller glödlampeproblemet fanns det en Python-lösning på den URL du gav hos Bengt, dvs ug's projects: 100 prisoners and a light bulb. Har du något annat program på lut?

Bengt: En annan sak är om Abedissan var medveten om att det var Karlar i cellerna och hennes reaktion över detta. Historien förtäljer ju inget om detta. Hon var blind enligt historien men knappast döv eller utan känsla uti fingrarna?

Hakke: OK, jag antog tydligen din utmaning. Nu kan programmet även visa unika lösningar, vilket har gjorts genom att samla de lösningar som är lika på något sätt: spegling, rotation etc.

Som står i uppdateringsnotisen ovan finns denna logik inte i Eclipse-programmet utan i CGI-programmet och det skrevs för att jag ville ha lite analysunderlag för vidare analyser.

Så det är i alla fall halva vägen. För en användare av programmet spelar det ju ingen roll var sådant ligger, eller hur.

Jag tycker att vi tar ditt kak-problem off-blogg.

Imponerande. Anledningen till att jag frågade efter unika lösningar var att jag förstås sorterade bort dessa när jag satt själv. Jag försökte komma på så många jag kunde på den lilla stund jag hade att lägga på problemet. Tyckte nog det gick ganska bra, men när jag ser det verkliga antalet unika lösningar inser jag att CGI och CLP trots allt är överlägset POP. Men det beror kanske mest på vem det är som sitter vid pappret och håller i pennan :)

Hakke: Man ska inte underskatta POP som redskap för snabbt skisserande av problem. Friare sätt att tänka finns inte (möjligen med undantag av Whyteboard). En stor fördel är att POP tenderar att vara lättare än en bärbar dator (liksom lättare än en Whyteboard).

[Det följande är en programspråks-aside.]
Inte heller bör man underskappa POP i form av det trevliga men undanskymda programspråket POP-11, som väl bäst kan beskrivas som ett språk för AI och processande av naturligt språk. En implementation finns i Poplog och det finns faktiskt en icke inaktiv usenetgrupp comp.lang.pop.

Jag kikade på POP-11 i samband med böckerna "Artificial Intelligence: Strategies, Applications, and Models Through Search" (ISBN: 1579580041) av Chris Thornton, Benedict Du Boulay samt "Computers and Thought: A Practical Introduction to Artificial Intelligence" (ISBN: 0262192853) av Mike Sharples, David Hogg et.al.

Jaha, sent omsider skrev jag ett yttepyttelitet matlab-program för att lösa problemet, och ut trillade lösningar. Det är 8 obekanta och 5 ekvationer i varje delproblem, vilket normalt antyder att fler lösningar är möjliga, men jag orkar inte riktigt fundera över det nu, eftersom jag fick så fina lösningar :-)!

Jag använde den inbyggda funktionen pinv (pseudoinvers), som gav symmetriskt snygga och positiva lösningar, använder man en minsta-kvadrat-approach får man t ex minus-nunnor och/eller minus-Karlar som lösning, och hur kul är det?! Och egentligen är det inte sant att man bara har fem ekvationer, eftersom man har ytterligare 8 ekvationer A>=0, B>=0 osv ... Egentligen ett överbestämt problem. Och dessutom vill man ha heltalslösningar, för lika lite som minus-Karlar vill man ha decimal-Karlar ju, eller hur ;-).

Men, jag gör det enkelt för mig och redovisar det lilla matlab-programmet som ger en trevlig lösning i varje fall:

% 1.

A = [1 1 1 0 0 0 0 0;

1 0 0 1 0 1 0 0;

0 0 0 0 0 1 1 1;

0 0 1 0 1 0 0 1;

1 1 1 1 1 1 1 1];

YA = [9 9 9 9 24]';

SA = pinv(A)*YA;

% 2.

B = [1 1 1 0 0 0 0 0;

1 0 0 1 0 1 0 0;

0 0 0 0 0 1 1 1;

0 0 1 0 1 0 0 1;

1 1 1 1 1 1 1 1];

YB = [9 9 9 9 28]';

SB = pinv(B)*YB;

% 3.

C = [1 1 1 0 0 0 0 0;

1 0 0 1 0 1 0 0;

0 0 0 0 0 1 1 1;

0 0 1 0 1 0 0 1;

1 1 1 1 1 1 1 1];

YC = [9 9 9 9 20]';

SC = pinv(C)*YC;

% 4.

D = [1 1 1 0 0 0 0 0;

1 0 0 1 0 1 0 0;

0 0 0 0 0 1 1 1;

0 0 1 0 1 0 0 1;

1 1 1 1 1 1 1 1];

YD = [9 9 9 9 32]';

SD = pinv(D)*YD;

----------
Låter man matlab räkna ut en minsta-kvadratlösning får man t ex i första fallet följande lösning (samma notation som i din uppställning med A, .., H);
[9 0 0 6 0 -6 6 9] ... :-D!

----
Sådär, enkelt att sätta upp. Nu kanske jag skulle tänka lite på problemet också ... ;-)

Thebe: Tack för din lösning. Trevligt med olika alternativ att lösa samma problem. Eventuellt kommer en tredje variant att presenteras.

Som service kommer här en liten förklaring vad som pågår i Thebes lösning. Matriserna A (liksom B, C och D) motsvarar rummen på följande sätt.

A B C D E F G H # De åtta rummen
1 1 1 0 0 0 0 0 # A + B + C
1 0 0 1 0 1 0 0 # A + D + F
0 0 0 0 0 1 1 1 # F + G + H
0 0 1 0 1 0 0 1 # C + E + H
1 1 1 1 1 1 1 1 # A + B + C +D + E + F + G + H

De fyra lösningarn blir således:

SA:
3.0000
3.0000
3.0000
3.0000
3.0000
3.0000
3.0000
3.0000

dvs
3 3 3
3 _ 3
3 3 3

SB =

2.0000
5.0000
2.0000
5.0000
5.0000
2.0000
5.0000
2.0000

dvs:
2 5 2
5 _ 5
2 5 2

SC =

4.0000
1.0000
4.0000
1.0000
1.0000
4.0000
1.0000
4.0000

dvs
4 1 4
1 _ 1
4 1 4

samt slutligen

SD =

1.0000
7.0000
1.0000
7.0000
7.0000
1.0000
7.0000
1.0000

dvs

1 7 1
7 _ 7
1 7 1

Tack för att du expliciterade lösningen, Håkan,jag var lite slö med uppställningen av problem-formuleringen där tror jag ;-)!

Till övriga: Observera dock lösningen SB i Håkans förtydligande, där den förväntade, och korreakta, tvåan bytts ut till en trea. En test av vår uppmärksamhet! :-D

Thebe: Eftersom du var så uppmärksam har den där 3:an nu korrigigerats till en 2:a. :-)