Alla inlägg av Waffe

Kalkylationer på ett go bräde

Jag tänkte kombinera ett av mina favoritspel med programmering och se vad jag kommer på. Spelet  i fråga är go (kinesiska: wéiqí) och är ”känt för sin strategiska mångfald trots sina enkla regler” [Wikipedia: Go (brädspel)]. Reglerna till go kan förklaras på några minuter; om du inte tror på mig så kan du kolla följande video: Go – Basic Rules.

Du behöver egentligen bara veta följande tre regler:

  • Man spelar turvis på skärningspunkterna av go brädet.
  • Stenar som vidrör varandra räknas till en grupp. Diagonala stenar vidrör inte varandra.
  • Då en grupp av stenar inte vidrör en enda tom punkt blir gruppen uppäten.

Med dessa simpla regler kan man t.ex. få till stånd en ”stege” som illustreras nedan:

En stege som vänder på sig.

Efter varje vita drag måste svart svara med att spela utåt. Alla andra svarta drag leder till att vit kan omringa och äta upp den svarta stegen.

Med dessa simpla regler hittade jag på ett sätt att räkna saker — en go-kalkylator! Go-kalkylatorn fungerar på basis av stegarna jag nämnde tidigare. Spelbrädan kan vara av valfri storlek, och dit kan placeras vissa stenformationer på förhand. För att sparka igång kalkylatorn spelar man en vit sten så att den påbörjar en stege.

För kalkylatorn gäller dock två extra regler:

  • Man skall spela ”kortsiktigt” och ”snålt” genom att alltid försöka hålla alla sina egna grupper i liv, och att inte ge motståndaren chansen att skydda deras grupper.
  • I fall det finns flera stegar spelar man dem i tur och ordning.

Så hur utför man beräkningar? Följande saker kan utföras på stegen:

En stege som hoppar fem stenar åt vänster.
  • Förflyttning och rotation (se också den första animationen)
En duplikator: en stege blir två.
  • Duplikation
Denna formation låter bara den första stegen som når den fortsätta. Märk att detta händer på grund av vitas sten på K10. För att spara tid och ”print screen”-knappens användning placeras båda stegens stenar samtidigt. Det fattas en extra svart sten från K13 för att få detta att fungera deterministiskt (utan val från vitas sida).
  • Val av den första stegen som når en punkt

Den sista av dessa formationer möjliggör kalkyl. I animationen ovan följer stegarna den logiska satsen ”höger, och inte vänster”. Det vill säga att en stege som utvidgas högerut skapas bara då när en stege kommer från höger och ingen stege kommer från vänster.

Med en ”kontrollstege”, som sätts igång i början av programmet, kan man då skapa en steges X negation (”inte X”), som kan sedan användas för att räkna satser som ”X och Y” samt ”Y eller Z”. Med andra ord kan man beräkna alla simpla logiska satser.

Denna formation är ekvivalent med satsen ”A och B”. Symbolerna A och B (på koordinaterna R11 och N1) är inputs för svart, och vitas drag vid fyrhörningen skapar en kontrollstege. Outputten mäts i triangel-punkten.

Fast det skulle vara coolt att programmera en miniräknare på ett go-bräde så finns det ännu problemet med korsande stegar. Utan möjligheten att korsa stegar är kalkylationspotentialen starkt begränsat. T.ex. kan man skapa en 1+1 adderare, men troligtvis inte för större tal.

Extreme hänggubbe

Dags för ett litet ordspel!

Spelet liknar hänggubbe eller hängman, i och med att du skall gissa ett ord som bara jag vet. Du kan gissa bokstäver, ord eller delar av ord, exempelvis ”kaff”.

Jag måste svara på om din gissning finns i mitt ord. Om det dolda ordet är ”abrakadabra” och du gissar på ”bra” svarar jag jakande, men om du gissar ”arb” svarar jag nekande. Du får inte veta var i ordet din gissning förekommer.

Frågan är nu, vad är det snabbaste sättet att klura ut ordet? Några lösningar beskrivs nedan, läs på egen risk!

Att testa sig fram tar i genomsnitt 1/2 * bordn/(bA! bB! … bZ!) försök, där bord är mängden olika bokstäver som finns i ordet. Ordet ”abrakadabra” tar ungefär 1/2 * 2911/(5! 2! 2! 1! 1!) ~ 1.27 * 1013 försök. Ett Twitter-meddelande som inkluderar siffror och små bokstäver kan ta upp till 1.37 * 10210 försök.

Så istället för att bara hitta bokstäverna som förekommer i ordet och sedan testa oss fram, varför klurar vi inte ut alla 2-strängar (2 bokstäver långa teckensträngar) som finns i ordet? Kan vi då få reda på ordet snabbare? Svar: jo.

Att klura ut alla 2-strängar kräver högst B + bord * (bord-1) / 2 eller i värsta fall B/2 + B2/2 gissningar, där B är mängden användbara bokstäver. Detta tar inte så värst länge, men vad har man för nytta av 2-strängar? Kan man med hjälp av dessa bygga snabbt upp 3-strängar?

Genom att visualisera 2-strängar som en graf kan man skära bort flera onödiga gissningar. Noderna i grafen är alla 2-strängar vi känner till, och kanterna länkar strängarna till varandra så att följande sträng börjar med delsträngen som den första slutar med. Notera att mängden olika k-strängar av ordet inte kan vara mer än n-k+1 (eller Bk för den delen). Mängden kanter i grafen kan inte vara mera än (n-k+1) * B, eftersom varje nod har högst en kant per bokstav. 3-strängar kan fortsättningsvis visualiseras som en graf, vilket till slut leder till en n-sträng, vilket måste vara ordet vi söker efter.

Notera att grafen för alla 3-strängar i ”abrakadabra” har blivit en stor ögla. I detta fall kan man gissa sig fram till lösningen genom att välja en nod som startpunkt, och sedan åka ett varv runt. I detta fall får man till näst gissningarna ”abrakadab”, ”brakadabr” och ”rakadabra”. Dessa skapar en simpel graf på 3 noder som sedan leder till ordet vi letade efter, ”abrakadabra”

Värsta möjliga antalet gissningar för ord blir till sist:

B/2 + B2/2 + (n-1) B + (n-2) B + … + 1 B = B/2 + B2/2 +  n2B/2 – nB/2

vilket vi kan avrunda glatt till n2B. I verkligheten krävs det mycket mindre arbete, eftersom grafen som bildas snabbt blir en ögla (”abrakadabra” krävde 45 + B gissningar, och en 137 karaktär lång meddelande krävde ~2100 + B gissningar). Att räkna ut det praktiska tidskravet av den presenterade algoritmen lämnar jag som läxa för läsaren.

PS. Fresh Prince of Bel-Air theme orden (1788 tecken) löses på 31446 gissningar.

PyClojuR: En kod ouroboros

Betrakta Python-koden nedan.

s = 's = %r\nprint(s%%s) #Hello'
print(s%s) #Hello

Du kan prova köra den härifrån. Vad händer?

Ett program som skriver ut sin egen källkod utan att fuska kallas för en ’quine’. (Som ’fusk’ räknas direkt uppläsning av programfilen och annat liknande.) Exemplet ovan består av tre delar:

  1. Kod som data. Strängen ’s = %r\nprint(s%%s) #Hello’ innehåller kopian av programmet i text form.
  2. Kod som processerar datan. Notera att all processerande kod befinner sig i någon form i den användbara datan.
  3. Övrig data. Kommentarerna #Hello samt mellanslagen är fullständigt övriga och kan tas bort utan större problem.

Du kanske tänker att quiner är unika för Python-språket, men i själva verket kan man bevisa följande sats:

För alla vettiga programmeringsspråk L existerar det åtminstone ett program P∈ L som skriver ut innehållet av P.

Beviset kan läsas här för dem som är intresserade. I ett nötskal listas alla giltiga program Pi upp, vartefter det bevisas att för varje beräkningsbar funktion h kan man hitta en fixpunkt k så att Pk och Ph(k) är identiska. Genom att välja funktionen h så att Ph(t) skriver ut innehållet av Pt kan man hitta k så att programmet Pk skriver ut innehållet av sig själv.

Utifrån detta presenterar jag Waffes ouroborosprogram teorem (WOooP teoremet):

Givet vettiga programmeringsspråk L1, L2, … Ln  existerar det ett en serie av program P1∈ L1, P2 ∈ L2, … Pn∈ Ln där Pn skriver ut P1, och Pi skriver ut Pi+1.

Programmen P1, P2, … Pn kallas då för ouroborosprogram, namngett efter den mytologiska ormen som äter sin egen svans. Börjandes från Pi får man efter minst n körningar tillbaka det ursprungliga programmet Pi. En quine kan då tänkas vara ett ouroborosprogram på bara ett språk.

För att bevisa WOooP räcker det med att definiera LC som språkens L1, L2, … Ln sammansättning. Man kan sedan använda första satsen för att bevisa att det måste finnas en quine för LC, vilket är ouroborosprogrammet vi söker efter.

Som ett test på mitt teorem skrev jag ett hackigt ouroborosprogram från Python till Clojure till R. Ta gärna och testa för er själva! Koden finns i min git här: code.py.

Alla tre språken har online terminaler, så inget behöver installeras för att testa koden.

P.S. Här är ett lite längre ouroborosprogram på 128 språk.