november 30, 2012

Byte av epostadress, samt annat

Äntligen - säger kanske någon - så kommer det något livstecken från Håkan. Den som säger så har i så fall missat följande livstecken:

Men - "tyvärr" kanske någon säger, eventuellt samma någon som ovan nämnda någon - så är denna blogpost endast (fast nästan) för att meddela den viktiga information att jag numera helt gått över till en annan epostadress, nämligen hakank@gmail.com. Detta eftersom Bredbandsbolaget helt och hållet stänger trotjänaren bonetmailen-adressen som varit med i nästan exakt 10 år (tack för denna tid, för övrigt).

Dock, för att ni inte ska gå helt tomhänta härifrån så kan meddelas följande - till viss del helt orelaterade - saker, fast ändå inte eftersom sak numro 2 är väldigt relaterad, på vissa sätt och vis i alla fall:

Språkligheter

Följande ord innehåller vokalerna a,e,i,o,u,y i ordning:

Detta ord innehåller vokalerna a,e,i,o,u,y,å,ä,ö i ordning:

Och ordet tryckutjämningsbehållare är det ord (från den ordlista som be-sökts)
som innehåller flest olika bokstäver (20 stycken). Här är deras fördelning:

Och följande ord är de som innehåller flest distinkta bokstäver, exakt en förekomst alltså (16 unika bokstäver)
utifrån densamma ordlista:

Se nedan under "Senare not" för en senare not om detta.

Byte av mailadressen

Men - kanske någon kunde säga om just denne någon är bevandrad i data(sv)engelska -: Men hördudu Håkan, byte har ju en engelsk betydelse också, har du tänkt på det?. Varpå jag i så fall kunde svara: Ah, kul du tänkte på det! Det tänker man ju inte på om man bara säger ordet högt., och skulle då därefter kunna beskriva en algoritm för just denna betydelse av "byte av mailadress", nämligen transformeringen av hakank@gmail.com till en byte: Byt (sic!) ut varje bokstav till dess ASCII-värde, summera dess värden tillsammans och på denna summa gör man sedan en fin modulo 255 256. För min nya gmail-adress blir det 37. 43 (så nära!).

Varpå man skulle kunna implementera algoritmen i programspråket K (om man hade den inklinationen och det har man ju ibland, eller hur?):

  (+/{_ic x}'"hakank@gmail.com")!255
43

  (+/{_ic x}'"hakank@gmail.com")!256
37

(K är - för övrigt och som eventuellt kan ses med ovanstående kodexempel - ett väldigt uttrycksfullt "array language" som gör att man mycket kärnfullt kan uttrycka sina innersta tankar kring vissa saker i tillvaron, t.ex. saker såsom saker av ovanstående problemstruktur. Språket är en del i APL-familjen och typ en kusin till programspråket J. Hittills har K varit mer favoritspråk än J, men det är möjligt att detta ändras vad det lider.)

Senare not:
Samma person som påpekade (i ett mail som tyvärr - synnerligen felaktigt - ansetts av Google som spam) att det ska vara modulo 256 istället för 255, gav även förslaget "mödoutvecklingsbar" som ett längre ord med unika bokstäver än ovanstående. Även densamma person ansåg att det föreslagna ordet är "lite krystad, kanske" och påpekade att ordet inte fanns i Googles sökmotor; och det måste vi ju ändra på.
Slut senare not

Posted by hakank at 08:59 EM Posted to Diverse | Personligt | Program | Pyssel | Språk

januari 24, 2010

Eureqa: equation discovery med genetisk programmering

(For English readers: This blog post is available as a Google Translation from this Swedish text: Eureqa: equations discovery with genetic programming.)

För mer än 6 år sedan bloggade jag om equation discovery (att hitta ekvationer/samband givet en datamängd) och hittade några roliga system som jag då kollade in rätt mycket.

Nu är det dags igen: Eureqa är ett modernt equations discovery-system baserat på genetisk programming (närmare bestämt symbolisk regression) och det har ett fint GUI etc.

Eureqa blev världskänt i början av december förra året genom att Wired skrev en artikel om systemet och forskningen/forskarna bakom: Download Your Own Robot Scientist. Faktum är att jag laddade ner systemet och testade det lite men jag höll på på med andra saker.

De senaste dagarna har jag suttit med några enkla problem (dvs datafiler) för att lära känna Eureqa mer. Mer avancerade saker såsom dynamiska modeller (differentialekvationer) och komplexa ekonomiska system (såsom börskurser) tar jag tag i senare.

Jag tänker inte gå in på vad genetisk programmering är mer än att säga att det använder inspiration från biologin för att leta rätt på en lösning. Se vidare genetic programming (Wikipedia) för mer info och länkar.

Huvudprincipen för den variant av genetisk programmering som Eureqa använder är att man har
- en datamängd
- ett visst antal matematiska funktioner ("byggklossar")
- en relation mellan variabler som man vill studera

Eureqa hittar då givet variablerna och funktioner ett antal samband (lösningar, modeller). Med en "felfunktion" (error function) kommer diskrepansen mellan data och den skapade modellen att minska till ett så litet värde som möjligt, förhoppningsvis 0.

Här följer några kommentarer och ett och annat tips. Först beskrivs Eureqa, sedan lite mer om modelleringen med några exempel. Efter det länkar till några av de datafiler som används, och sist mer länkar om Eureqa.

Mycket kortfattat: Jag tycker Eureqa är ett riktigt trevlig och skoj system, tyvärr rätt mycket CPU-slukande för att min dator ska må riktigt bra. Men skoj.

Min vana trogen skapades även en My Eureqa page för länkar, filer och annat etc.

Installation

Programmet finns att ladda ner här.

Tyvärr finns endast en Windows-version men det ska komma klienter för åtminstone Linux. Jag har inga större svårigheter att köra Eureqa under Wine förutom att det alltså tar väldigt mycket kräm när det bearbetar data.

Det installerades på min burk med följande kommando:

wine msiexec /i eureqa_full_0.7.7.msi

och kör det sedan med

wine "<installation path in Wine>/Eureqa.exe"

Mer om systemet

Eureqa har ett mycket trevligt GUI med olika tabbar för data, plottning/smoothing av data, modellering, start/stop och lösning. Dessa tabbar presenteras här kortfattat.

* "Enter Data"
Man kan skriva in data som i ett enkelt spreadsheet à la Open Office Calc eller Excel (vad jag vet stöds inte formler etc). Det sätt jag använder är dock att skapa en text fil (ASCII) som består av följande:
- header med information om fälten. T.ex.
% | x y z |
där "%" är kommentar och de två "|" är avgränsare för variabelnamnen. Tänk på att det bör vara relativt korta namn annars kan det bli svårläst med mer komplexa uttryck.
- sedan data med mellanslag som separator.

För att hämta in en datafil används "File", "Import data...". Om det är fel i filen kommer mer eller mindre lättförståeliga felmeddelanden. Jag har inte testat så mycket att manuellt lägga in data via kalkylprogram men det ska gå.


* "Preview Data" (och smoothing)
I detta fönster man man se de olika värdena plottade i en x/y-graf. Man kan även göra en smoothing (vad jag förstår är det loess man använder), t.ex. om det är mycket brus för någon variabel.

* "Pick Modeling Task"
Här gör man själva modellen, dvs skapar förutsättningen för uttrycket. Se även nedan under "Modellering, några exempel".

- Search for a formula: Här skriver man formen för uttrycket, t.ex.
x1 = f(x2,x3).

- Using building blocks: Här väljs de funktioner ("byggklossar" som man vill att Eureqa ska testa. Normal vill man alltid ha "+","-","*","/", men sedan beror det lite på vad det är för typ av data. Intressant nog är "sin" och "cos" alltid med, vilket väl speglar utvecklarnas preferens för fysiska system. Eftersom de flesta av mina datamändger inte är fysiska system brukar jag börja med att ta bort sin och cos och i stället välja t.ex. square root, exponential och logarithm, eller helt enkelt endast börja med de fyra räknesätten.

Det finns ett flertal andra byggstenar, t.ex. minimum, maximum, Logistic, Gaussian, Gamma, Step och Sign, man inverser och hyperboliska varianter av trigonometriska funktionerna. På forumet antyds att det kommer flera i nästa version, t.ex. de booleanska AND, OR, XOR, samt att man ska kunna definiera egna varianter.

Det finns även andra saker på denna sida, t.ex. att välja Fitness metric och viktningen av datapunkterna.

Det går också att använda flera datorer till en körning. I "Use the following servers" väljer man eventuellt andra datorer som kör en Eureqa server. Detta har jag inte testat.

"Seed previous solution(s)": Här kan man skriva uttryck (formler) som en vink ("bias" till Eureqa att dessa är viktiga formler. Detta har jag inte kollat in så mycket.

* "Start/stop"
Här startar, stoppar och pausar man en körning. Förutom dessa knappar finns en mängd annan information om hur körningen går.

* "Solution Results"
Det är här man ser lösningen både som ett uttryck och även en graf hur bra lösningen är jämfört med de givna datapunkterna. Det är fascinerande att se den växa fram och lära sig.

Datamängden delas upp (automatiskt av Eureqa) innan körningen i två delar: träningsdata (train data) och valideringsdata (validation data). Sedan körs modellen på träningsdatan och valideras på valideringsdatan. Dessa två delar presenteras med olika färger här så man ser hur bra eller dåligt den valda modellen (uttrycket) passar. Mycket trevligt.

Olika statistiska metriker visas för respektive träning- och valideringdata:
- Fitness
- R-squared
- Correlation Coeff
- Mean Squared Error
- Mean Absolute Error
- Minimum Error
- Maximum Error

De flesta av dessa kan man använda som fitness metric i modelleringstabben.

I listan över lösningar ser man en handful lösningar som anses som mest intressanta, med den mest lovande överst. Denna lista växer dynamiskt hela tiden efter hand Eureqa hittar nya modeller. Om man klickar på en av modellerna visar både statistik och plottningen för den valda modellen. Dubbelklickar man på en formel kopieras den för att sedan klistras in i något finns program (t.ex. om man vill blogga om det).

Modellering, några exempel

Här en kort beskrivning om modelleringen. Till skillnad från traditionell "curve-fitting" så skriver man inte några matematiska uttyck som ska parametriseras, utan endast vilka variabler som ska vara med i uttrycket. För dessa variabler väljs om de överhuvudtaget ska vara med samt eventuell parameter. Eureqa hittar även olika konstanter, både "globala" och inom uttryck.

Exempel med sinus
En av de första sakerna jag testade var att skapa en datafil med två kolumner (x och y) skapad på följande sätt (med Perl):

perl -le 'for (-100..100) { print $_/100, " ", sin(2*$_/100)+3}'

som skapar data för sambandet y = sin(2*x) + 3. De sparades i datafilen sin_formula.txt.

Eureqa hittar lösningen efter cirka 10-15 sekunder. Notera att x motsvaras av "x0" och y av f(x0) (eller x1):

  f(x0) = 3 + sin(2 * x0)

Detta var alltså 201 datapunkter, men man behöver inte alls så mycket data för att Eureqa ska hitta en lösning.

En variant där man endast tar 20 slumpmässiga punkter är sin_formula_rand20.txt som är skapad genom att ta 20 punkter mellan 0 och 2*Pi:

perl -le 'for (1..20) { my $x = rand(2*3.14159); print "$x ", sin(2*$x)+3}'

Eureqa hittar 3+sin(2*x0) på cirka 30 sekunder. Det gick (denna gången i alla fall) lite långsammare eftersom det är färre punkter. Man ska dock komma ihåg att färre punkter gör att det är snabbare att kontrollera hur bra lösningen är.

Den viktigaste delen i modelleringen, förutom att hitta tillförlitlig data, är att hitta rätt byggstenar, dvs de matematiska funktioner som ska användas. Det bör göras med viss försiktighet och eftertanke: Om man väljer för många kan det ta väldigt lång tid och man kan får konstiga resultat. Väljer man för få så hittas inte en enkel lösning. Detta är en konst.

Fibonacci-serien
En annan skoj sak som man kan testa är tidsserier eller data som kan ses som tidsserier. T.ex. kan Eureqa hitta en formel för Fibonacci-serien? De 25 första talen i Fibonacciserien är: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946.

För att göra detta till en lämplig representation - och som vanligt är representationen av problemet väldigt viktigt - är att man tar (tids)serien och lägger den i sekvens över flera variabler.

Låt oss anta att vi inte vet så mycket om denna serie, men anar att det finns en rekursivitet i serien, dvs att senare värden beror på de tidigare, normalt de omedelbart föregående (andra tidsserier, till exempel de ekonomiska kan ha andra beoenden såsom säsonger och veckodagsberoenden).

Här tas serien om fyra. Den första raden är 1,1,2,3, och sedan förskjuts serien för varje rad. Hela serien finns alltså i första kolumnen.

% | t1 t2 t3 t4 |
1 1 2 3
1 2 3 5
2 3 5 8
3 5 8 13
5 8 13 21
8 13 21 34
13 21 34 55
21 34 55 89
34 55 89 144
55 89 144 233
89 144 233 377
144 233 377 610
233 377 610 987
377 610 987 1597
610 987 1597 2584
987 1597 2584 4181
1597 2584 4181 6765
2584 4181 6765 10946
4181 6765 10946 17711
6765 10946 17711 28657
10946 17711 28657 46368

Nu kan vi modellera problemet i Eureqa på följande sätt:
- Formel: t4 = f(t1,t2,t3)
- Byggklossar: "+","-","*","/"

Det tar mellan 5 och 10 sekunder för Eureqa att hitta sambandet:
t4 = t3 + t2

Correlation Coefficient är 1.00000, R-squared är 1 och alla error är exakt 0 så det ser helt korrekt ut.

Detta är skoj!

Man kan här notera att egentligen behövde vi ju bara de tre första variablerna t1, t2 och t3 men jag valde att ta med den extra kolumnen t4 för att inte fuska för mycket. En annan sak att notera att det är viktigt att titta på Correlation Coefficient och R-squared samt Error för att se hur bra lösningen är.

Nu kan man göra lite mer roliga saker. Given en lite större datamängd (fib_38.txt) med 38 värden kan vi kolla om Eureqa hittar några andra samband, t.ex. mellan endast två variabler t1 och t2, dvs mellan ett värde och endast de närmast föregående. Här lägger jag till funktionerna "exp", "sqrt" och "log".

Här är några samband som hittades i flera olika körningar. Samtliga dessa har en fitness error på 0.000 (det som i lösningstabben kallas "Error") och correlation coefficient på 1.0

f(t1) = 1.61803*t1
f(t1) = 1.61803*t1 - 0.472137/t1
f(t1) = 1.61803*t1 - 1.67999/exp(t1)
f(t1) = 1.61803*t1 - 1.67999/exp(t1)
f(t1) = 0.809017*t1 + 0.809017*sqrt(t1)*sqrt(t1) - 0.470881/t1
f(t1) = 1.61803*t1 + 0.221196/(t1*t1 - 1.61571*t1 - 1.70552)
f(t1) = 1.61803*t1 + -3.39888*log(t1)/exp(t1*t1 - 1.69947)
f(t1) = (1.61803*t1*t1 - 0.459213)/t1
f(t1) = 1.61803*t1 - 0.440428/(t1 - 0.440428/(1.61803*t1))
f(t1) = 1.61803*t1 - 0.3884/(t1 - 0.354305)

Notera att Eureqa har identifierat konstanten 1.61803 i flera av ovanstående lösningar vilket är väldigt nära phi, dvs "gyllene snittet" (golden ratio) = (1+sqrt(5))/2 ~ 1.6180339...). phi är precis förhållandet mellan två intilliggande Fibonaccital, så det är ju inte konstigt att Eureqa hittade detta samband. Se Fibonacci number på Wikipedia och Encyclopedia of Integer Sequences:A000045 för mycket mer info om detta.

Man kan säkert hitta andra matematiska konstanter om man letar vidare. Plouffe's Inverter är en guldgruva för sådant. T.ex. här är en sökning på konstanten 1.61803. Tyvärr är det väldigt många träffar eftersom det är så liten precision på talet.

Formeln f(t1) = 1.61803*t1 är alltså en approximering av nästa tal i Fibonacci-serien, dvs F[n+1] = phi*F[n] (avrundat till heltal).

Ett mera avancerat exempel är om Eureqa månne kan hitta den slutna formeln för Fibonaccital, dvs

F(n) = (phi^n - (1-phi)^n)/sqrt(5)

För detta krävs en ytterligare parameter i datafilen, nämligen n, dvs index för raden. Så här ser filen ut nu (fib_50.txt"), utökat till 50 rader. Den första kolumnen är alltså index.

% | ix t1 t2 t3 t4 |
1 1 1 2 3
2 1 2 3 5
3 2 3 5 8
4 3 5 8 13
...
48 4807526976 7778742049 12586269025 20365011074
49 7778742049 12586269025 20365011074 32951280099
50 12586269025 20365011074 32951280099 53316291173

Jag vet inte riktigt hur stora tal som Eureqa kan använda, men det saknas i alla fall stöd för arbiträr precison.

När jag skapat filen testades först med samtliga variabler:

t4 = f(ix,t1,t2,t3)

Då kommer lite mer avancerade förslag än tidigare körning, samtliga med Error 0 och correlation coeff på 1.0000 (dock inte med Maximum error 0), några av dem innehåller n, dvs index.

f(ix, t1, t2, t3) = sqrt(1.61803*t2*t3) + (t2*sqrt(t3) - t2*t2)/(sqrt(t3) - t2)

OK, nu till problemet om den slutna formeln
Formel: t1 = f(ix)
Funktioner: +,-,*,/, sqrt

Det vi vill ha är alltså något som liknar:

(phi^n - (1-phi)^n)/sqrt(5)

eller snarare den numeriska motsvarigheten

f(ix) = (1.61803^ix - (1-1.61803)^n)/2.2361
= (1.61803^ix - (-0.61803)^n)/2.2361
= 0.4472071911*1.61803^ix - 0.4472071911*(-0.61803)^ix

(Den tredje varianten hittades via ett matematikverktyg.)

Intressant nog började Eureqa med lösningar där endast ix upphöjt till stora tal (t.ex. 18) samt addition, multiplikation med konstanter. Efter ett tag började experimenten med sqrt, men den körningen hittade inte skoj på många minuter så jag stoppade den.

För att komma runt detta testade jag "hints", dvs "Seed previous solution(s)" på "Pick Modeling Task"-tabben, genom att skriva 1.61803^ix samt sqrt(5). Då kom följande lösningar efter liten stund. De har alla korrelationskoefficient på 1, Error på 0 men stora Maximum Error.

f(ix) = ix + 4*ix*ix*ix + 0.0256922*ix*1.58422^ix
f(ix) = 0.445386*ix + 0.445386*1.61817^ix
f(ix) = 0.0893707 + 0.399785*sqrt(1.61804^ix) + 0.447094*sqrt(1.61804^ix)*sqrt(1.61804^ix)
f(ix) = 2*ix + 0.447097*1.61804^ix
f(ix) = 0.611078*sqrt(1.62499^ix) + 0.447094*1.61804^ix - 127.933

Jag undrar dock hur "naturligt" det är för Eureqa att testa formler på formatet "konstant^variabel", så detta anser jag vara lite fusk. Däremot, om det skulle gärna mer seriösa experiment är denna typ av hintar vettiga. Då anger man vissa samband som grund, ett "alfabet" att bygga vidare på. Jag tror att mer stöd för detta kommer i senare versioner.

Efter detta - ska vi säga misslyckande - skippade jag hintarna och lade på funktionerna "exp", "sin", "cos" och då hittades detta samband och flera liknande, som jag faktiskt inte vet hur det ska tydas. Vad är 0.481188 för något tal i detta sammanhang?

f(ix) = 0.447755*exp(0.481188*ix) - 0.481188*ix*ix*ix

Om man däremot lägger till funktioner "power" (och tar bort alla hintar) så kommer lösningar på formen konstant^ix väldigt snabbt (dvs inom en minut eller så), t.ex.

f(ix) = 32.1653 + 0.446572*1.61809^ix

Där vi möjligen kan ana phi i konstanten 1.61809.

En kommentar om "power": När man väljer den i funktionslistan kommer meddelandet Tip: integer powers are implemented automatically with the multiply operation. This more general power operator may not be needed for modeling the dataset.. Här har vi tydligen ett fall där "power" behövs.

Andra lösningar i olika körningar:

f(ix) = 1.61808^(ix - 1.67492)
f(ix) = 0.0893756 + 0.399799*1.27202^ix + 0.447099*1.27202^ix*1.27202^ix
f(ix) = 1.61804^(ix - 1.67287) + 1.61804^(0.478442*ix - 0.800371)
f(ix) = 1.26564^(2*ix - 1.26564) + 2*ix - 1.26564
f(ix) = ix + 0.447144*1.61804^ix

(Jag har inte analyserat vidare eventuella matematiska samband...)

Notera att även om det är 0 i Error och 1 i korrelationskoeffient så kan det vara stora fel när man pumpar i konkreta värden.

En intressant lösning är följande där man möjligen kan skymta de viktiga beståndsdelarna i den slutna formeln:
- sqrt(5) ~ 2.2361
- 0.4472071911*1.61803 (från tredje varianten av den sökta formeln)

f(ix) = 2.23642*ix + 0.447144*1.61804^ix

Mer komplexa varianter:

f(ix) = 0.447144*1.61804^ix + 2.61804*ix*ix - (ix*ix)^(ix - 48.6408) - 48.6408*ix

Efter detta avslutade jag testet p.g.a. tidsfaktorer.

Slutsats: Vi hittade alltså inte formeln under dessa experiment, men vissa av sambanden kanske kan vara intressanta att studera vidare. Och så lärde vi oss det där med "power". En annan sak detta visar är att man kan vara tvungen att starta om flera gånger för att få mer aptitliga lösningar.

Derivata
Som nämnts några gånger tidigare så har jag inte labbat så mycket med dynamiska modeller, ävenom Eureqa skapats för detta ändamål. En av anledningarna är att jag inte har så bra data tillgänglig, en annan är att de mer intressanta körningarna kan ta lång tid, i vissa fall många timmar; "över natten" är ett uttryck som används några gånger i skrifterna.

Som videon (se Eureqas hemsida för länk) visar finns det möjlighet att använda derivata på följande format:

D(x1,t) = f(x1,x2,t)

och även i högerledet

D(x1,t) = f(x1,x2,D(x2,t))

Andra derivatan skrivs på följande sätt:

D(x1,t,2) = f(x1,x2,t)

Man ska dock tänka på att med derivata så krävs en preprocessing som kan ta mycket lång tid.

Andra modelleingsexempel beskrivs nedan.

Datafiler

Här är några av de datafiler som jag testat. För det mest är det enklare saker, och inte någon dynamisk data. De läses in med "File", "Import data...". Datafilerna finns även att tillgå på My Eureqa page.
  • gelman.csv: Linjär regressionsexempel.

    Data från Andrew Gelman's bloggpost Equation search, part 1, Equation search, part 2. Problemet beskrivs även lite mer i A linear regression example, and a question.

    Skriv följande i Pick Modelling Task:
    y = f(x1,x2)
    och lägg till "sqrt" som funktion.

    En lösning är mycket riktigt

    f(x1,x2) = sqrt(x1^2+x2^2)

    Med en korrelationskoefficient på 1.0 (och det är alltså bra).

  • planets.txt: Keplers tredje lag

    Detta exempel baseras på DTREG, ett annat symboliskt regressions-verktyg. Här hittas Keplers tredje lag baserat på den data som Kepler hade. Keplers tredje lag är:

    Period^2 = Distance^3

    Formel: Period = f(Distance)
    Funktioner: Skippa sin och cos, lägg till square root, exp och logarithm.

    Eureqa hittar rätt snabbt samband såsom:

    Period = sqrt(Distance)*Distance

    och det går snabbt.

  • odd_parity.txt
    En test på "paritet", men det funkar inte eftersom Eureqa än så länge saknar booleanska operatorer såsom OR, AND och XOR. Det ska komma "snart".

  • sin_formula.txt
    Se ovan.

  • sin_formula2.txt
    Se ovan.

  • sqrt_formula.txt

    Skapad så här:

    perl -le 'for (-100..100) { print $_/100, " ", sqrt(abs(2*$_/100))+3}'

    Glöm inte att lägga till sqrt, abs och lite andra funktioner.

  • iris.txt: Iris data
    Iris är ett standardproblem (-datamängd) inom machine learning och traditionell multivariat statistisk analys. Se Iris flower data set (Wikipedia) för mer information. Kortfattat handlar det om att klassifiera tre olika blomtyper (Iris setosa, Iris virginica and Iris versicolor) med avseende på fyra attribut: (Sepal Length, Sepal Width, Petal Length, Petal Width). 50 mätningar gjordes för respektive blomtyp.

    Jag tänkte att det skulle vara skoj att testa det med Eureqa också. Tyvärr klarar inte Eureqa att hantera kategorier (dvs strängrepresentation) så jag döpte om dem till "1", "2", samt "3" vilket troligen förvirrar Eureqa. En standardlösning för visssa typer av analysverktyg/-metoder som inte klarar kategorier är att i stället använda tre binära variabler som representation för de tre kategorierna. Men jag vet inte hur man får in sådant i Eureqa.

    Jag började med att representera attributen som sepallength, sepalwidth, petallength, petalwidth men det blev så trångt i lösningsfönstret att jag ändrade till kortnamnen sl, sw, pl, pw.

    Problemet skrivs på följande sätt

    class = f(sl, sw, pl, pw)

    Första körningen, med standarduppsättningen "+","-","*","/" samt "sin" och "cos" gick inte alls bra. Men när - som experiment - jag lade till funktionerna "minimum", "maximum" och "sqrt" så hittas följande rätt snart

    class = f(sl,sw,pl,pw) = max(1,pw + 2.20/sw)

    med en error på 0.179, fitness på -0.18, correlation coeff på 0.96, mean squared error 0.04. Traditionella metoder inom data mining/machine learning såsom beslutsträd brukar ligga ungefär där med 5-10 felklassificerade instanser.

    Efter lite mer tuggande kommer några bättre lösningar.

    error 0.129:

    f(sl, sw, pl, pw) = 0.975279 + min(0.624122*pw*pw, 2.02407)

    error 0.124:
    f(sl, sw, pl, pw) = 0.926007 + min(max(0.63846*pw*pw, 0.0735181), 2.07556)

    Jag är inte nöjd med detta eftersom min och max inte är så naturliga i sammanhanget och jag har inte analyserat vidare ramifikationerna av detta. Men det är ett roligt experiment. Man skulle kunna gå vidare och kontrollera vad som händer om man representerar de tre kategorierna med talen 100, 200, 300 istället, eller lägger till andra funktioner såsom sign etc.

    Som jämförelse kan nämnas att andra metoder (t.ex. via machine learningverktyget Weka) ger följande resultat, båda med ett antal felklassifikationer.

    J48 (beslutsträd):

    petalwidth <= 0.6: Iris-setosa (50.0)
    petalwidth > 0.6
    | petalwidth <= 1.7
    | | petallength <= 4.9: Iris-versicolor (48.0/1.0)
    | | petallength > 4.9
    | | | petalwidth <= 1.5: Iris-virginica (3.0)
    | | | petalwidth > 1.5: Iris-versicolor (3.0/1.0)
    | petalwidth > 1.7: Iris-virginica (46.0/1.0)


    JRIP (regelbaserad method):

    (petallength <= 1.9) => class=Iris-setosa (50.0/0.0)
    (petalwidth >= 1.7) => class=Iris-virginica (48.0/2.0)
    (petallength >= 5) => class=Iris-virginica (5.0/1.0)
    => class=Iris-versicolor (47.0/0.0)

    Se även min My Weka page för mer saker om Weka.

  • Sunspots.txt: Sunspots
    Solfläcksdata är ett annat standardproblem inom statistik och tidserieanalys. Tyvärr är jag lite osäker på vad denna data kommer ifrån, men det ska mätning av solfläckar på årsbasis. Så ta följande med en viss nypa salt och se det som ett generellt experiment.

    Detta är alltså en tidsserie med 11 "förskjutna" variabler.

    Formel t11 = f(t1,t2,t3,t4,t5,t6,t7,t8,t9,t10)
    Funktioner: +,-,*,/, sin, cos

    Notera att jag lät sin och cos vara med men de användes inte under den cirka halvtimmen jag körde (förutom några tidigare lösningar som förkastades snabbt).

    Efter ett par minuter var följande med i listan över aktuella lösningar (avrundat till 2 decimaler):

    Error: Solution
    0.215: 0.65*t10 + 0.66* (t10 / (0.32+0.08*t8)
    0.237: 7.20+1.34*t10 - 0.58*t9
    0.261: 1.39*10-0.54*t9
    0.302: 1.91*t10-t9
    0.307: t10-0.19*t9
    0.342: 0.84*t10
    0.400: t10

    Ingen av lösningarna är speciellt bra. Vi ser dock att t10 - inte förvånande - alltid är med, ibland t9 och vid ett tillfälle (det bästa) med t8 vilket visar att det finns någon form av beroende av tidigare värden.

  • sin_formula_rand20.txt

    Skapad med följande:

    perl -le 'for (1..20) { my $x = rand(2*3.14159); print "$x ", sin($x)+exp($x)+3}'

    Hittar följande snabbt:

    3 + exp(x0) + sin(x0)

    Testar genom att skippa sin(), men låter cos() vara kvar. Det tar en stund, sedan hittar den följande

    3.00 + exp(x0) + cos(1.57-x0)

  • boyles_law.txt: Boyles gaslag
    Se mer på Wikipedia Boyle's law.

    Detta är en klassiker i sammanhanget (dvs equation/scientific discovery), från boken Langley et.all Scientific discovery (ISBN: 9780262620529, länk till Bokus), sidan 82. Boken beskriver hur systemet BACON angriper problemet. BACON är ett system med liknande intentioner som Eureqa men använder en annan teknik. Boken är för övrigt mycket intressant.

    Eureqa hittar relativt snabbt samtliga samband (vid var sin körning):

    PV = P*V
    V = PV/P
    P = PV/V

    Corelation coeff är 1 och mean error i princip 0.

    Intressant nog kommer under körningen VP=f(V,P) även andra samband efter en stund:

    f(V, P) = (V*P*cos(-1*P - 1.36791) - V*P*P)/(cos(-1*P - 1.36791) - P)

  • fib_25.txt: Fibonacci
    Se ovan.
  • fib_35.txt
    Se ovan.

  • catalan.txt: Catalan-talen.

    Har inte hittat något skoj hittills, men ska nog leta vidare...

  • not_squares.txt
    Tal som inte är kvadrater. Hittade inget skoj.

  • primes.txt: Primtal
    Detta är också en tidsserie-variant med 10 variabler för att se om något skoj samband hittas. Även här får man leta vidare.

  • primes_with_index.txt: Primtal med index (dvs ordningstalet för primtalet)
    Se ovan om primes.txt

  • p4_gap.txt: Polynom
    Detta är ett av exempelproblem från JGAP (ett generellt genetisk programmingssystem i Java) där problemet är att hitta polynomet x^4 + x^3 + x^2 - x.

    Detta tog cirka 30 sekunder att hitta denna funktion i Eureqa. Notera att jag tog bort "sin" och "cos".

    Som jämförelse kan nämnas att JGAP-versionen tog cirka 12 minuter (vid första och enda körningen), men det är inte en rättvis jämförelse eftersom Eureqa är optimerat för denna typ av körningar. Uppdatering: . Jag noterade att anledningen till att det tog så lång tid i JGAP var att det inte fanns några operatorer för Add (+) eller Subtract (-) vilket ju gör problemet mycket svårare. När dessa lades till (samt Sine och Exp togs bort) tog det cirka 10 sekunderi JGAP. JGAP är helt klart ett intressant system för genetisk programmering.

  • p4_1.txt: Polynom
    Jag skrev ett litet program som skapar slumpdata för polynom på formen x^n+n^(n-1)+...n^2+x^1+x. Sådan problem kallar jag för p(n) nedan.

    Detta är alltså p(4). Det tog Eureqa cirka 20 sekunder att hitta

    p(4) = x^4 + x^3 + x^2 + x

    baserat på 30 punkter x,y inom intervallet -5.0..5.0.

  • p10_1.txt Polynom P(10)
    Däremot var det lite problem med p(10) över intervallet -2.5..2.5 och 100 punkter. Jag startade om ett antal gånger efter att ha väntat - ovetenskapligt nog - "några minuter .

    Rätt tidigt hittades x^10+x^8+x^7 men sedan tog det stopp
    och Eureqa började labba med x^12, t.ex. (x^12-x^2)/(x^2-x).

    En trolig förklaring till detta är att Eureqa straffar flera termer till förmån för färre.

    Jag startade om och ändrade Fitness Metric till "Maximum Error" (på tabben "Pick Modeling Task"). Efter cirka 6 minuter hittades

    0.73*x+x^2+x^3+x^4+x^5+x^6+x^7+x^9+x^9+x^10

    med ett Maximum error på 1.76. Correlations coefficienten är 1.0000 vilket ju är bra.

    Lösningen
    (x^12-x^2)/(x^2-x)
    har ett mindre felvärde för den datamängd jag testade, det var ju bara 100 punkter, så en del kan förklaras utifrån slump.

    Jag tröttnade efter typ 20 minuter.

  • p6_1.txt: p(6)

  • p7_1.txt: p(7)

  • circle_1_fixed.txt: Cirkel

    Detta är ett av exemplen till Eureqa, som finns att laddas ner här. Tyvärr är de i ett konstigt format så jag var tvungen att snygga till dem lite, härav namnet "_fixed.txt".

    Formel: x3 = f(x1,x2)

    Hittar lösningen 4*sin(x1) på 20 sekunder.

    Formal: x2 = f(x1,x3)
    Hittar lösningen 4*sin(x1) på 20 sekunder.

    Testar nu derivata:

    Formel: D(x3,x1) = f(x1,x2)
    Lösningen verkar vara

    dx3/dx1 = x2

    Testar formeln D(x3,x2) = f(x1,x2)
    Lösningen är 0 som Eureqa hittar omedelbart.

    Formeln D(x2, x1) = f(x1, x3)
    ger lösningen x3.

Mer om Eureqa

Här är en samling länkar om Eureqa.

Mer om symbolisk regression som är den metod Eureqa använder: Symbolic regression (Wikipedia)

* Andra artiklar om Eureqa:


Posted by hakank at 09:16 FM Posted to Dynamiska system | Machine learning/data mining | Pyssel | Statistik/data-analys

januari 04, 2009

Programspråket Icon och några Project Euler problem

Programspråket Icon och dess något mer aktiva objektorienterade dialekt Unicon (the Unified Extended Dialect of Icon) är ett underskattat språk. Tyvärr utvecklas det inte längre lika aktivt som tidigare av dess grundare (och det är säkert en orsak till underskattningen), men Unicon-projektet håller fortfarande på med skoj utökningar, t.ex. en SNOBOL-liknande strängmatchning.

Icon/Unicon är ett trevlig programspråk med flera ganska unika egenskaper:
- strängmatchningen. Det finns stöd för reguljära uttryck via regex.icn, men man bör först lära känna Icons egen variant som är en utveckling av SNOBOLs patterns
- "målinriktad" programmering, där success och fail avgör programmets flöde (via t.ex. en slags backtracking)
- generatorer med every och "alternattion" (se mina Mankell-skriverier nedan för mer exempel)
- co-expressions (används inte här nedan)
- det har ett drag av funktionsprogramming som tilltalar mig
- det finns ett stort antal exempel och moduler


Project Euler
Jag tänkte här inte prata så mycket om språket som visa några exempel rakt av (se referenserna nedan för mer introducerande material om språket). För detta används de tio första problemen från Project Euler, en sajt med veckoliga programmerings-/matematiska problem där man måste ange lösningen (i form av ett tal) för att komma vidare och läsa andras ofta kreativa lösningar (och p.g.a. detta visas endast programkoden, inte resultatet). De samlade Euler Project-problemen finns här.

Tilläggas kan att mitt Project Euler-ande började under mitt Lisp-skov för några år sedan och jag tenderar att göra åtminstone de första - säg - 20 problemen i programmeringsspråk som jag vill kolla in (såsom t.ex. Pop-11 i höstas; eventuellt kommer en snarlik bloggning om detta).

Nedanstående exempel antyder möjligen att Icon är ett språk för att hantera tal, vilket är lite olyckligt eftersom dess styrka snarare ligger i att hantera text/strängar (och datastrukturer). Detta sagt så skrevs flera artiklar i Icon Analyst om generering av olika talsekvenser.

Hursomhelst, här är programkoden för de 10 första Project Euler-problemen. I vissa fall visas även några (bortkommenterade) varianter av lösningar.



# some libraries used
link patterns, scan, factors, numbers, matrix, math

#
# The mandatory main procedure
#
procedure main()

problem1()
# problem2()
# problem3()
# problem4()
# problem5()
# problem6()
# problem7()
# problem8()
# problem9()
# problem10()
end

Problem 1

# If we list all the natural numbers below 10 that are multiples of 3 or 5,
# we get 3, 5, 6 and 9. The sum of these multiples is 23.
#
# Find the sum of all the multiples of 3 or 5 below 1000.
procedure problem1()
s := 0;
every s +:= mult3_or_5(1 to 999)
write(s)
end

procedure mult3_or_5(n)
# if n % 3 == 0 | n % 5 == 0 then
if n % (3|5) == 0 then
suspend n
end


Problem 2

# Each new term in the Fibonacci sequence is generated by adding the
# previous two terms. By starting with 1 and 2, the first 10 terms will be:
#
# 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
#
# Find the sum of all the even-valued terms in the sequence which do not
# exceed four million.
procedure problem2()
local s := 0
every s +:= fib_test(1 to 100)
write(s)

end

# For problem 2
procedure fib_test(n)
if (f := fib(n)) % 2 == 0 & f < 4000000 then return f
end

procedure fib(n)
nfib := 2;
prevfib :=1
currfib :=1
while nfib prevfib :=: currfib
currfib +:= prevfib
nfib +:= 1
}
return currfib
end


Problem 3

# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?

# pfactors from ipl/procs/factors.icn
procedure problem3()

L := pfactors(600851475143)
write(L[*L]) # write the last value

end


Problem 4

# A palindromic number reads the same both ways. The largest palindrome made
# from the product of two 2-digit numbers is 9009 = 91 × 99.
#
# Find the largest palindrome made from the product of two 3-digit numbers.
procedure problem4()

# Three different versions

## List solution:
# L := []
# every push(L, numeric(palindrome(string( (100 to 999) * (100 to 999)))))
# write(myMax(L))

## Hash table solution:
# H := table(0)
# every H[numeric(palindrome(string( (100 to 999) * (100 to 999))))]:=1
## sort(H,3) sorts on values och returns a list of
## 2*keys entries [key1, value2, key2, value2, etc]
# We want the penultimate element keyxxx in [...,keyxxx, valuexxx]
# L := sort(H,3)
# write(L[*L-1])

# Set solution
local S := set()
every insert(S, numeric(palindrome(string( (100 to 999) * (100 to 999)))))
L := []
every push(L, !S) # and converts to a list
write(myMax(L))

end

procedure myMax(L)

local maximum := get(L)
every maximum <:= !L

return(maximum)

end

procedure palindrome(s)
if s == reverse(s) then return s
end


Problem 5

# 2520 is the smallest number that can be divided by each of the numbers
# from 1 to 10 without any remainder.
#
# What is the smallest number that is evenly divisible by all of the numbers
# from 1 to 20?
procedure problem5()
L:= [];
every put(L, (1 to 20))
write(myLCM(L))

# alternative solution using lcml from library factors.icn
# write(lcml(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20))

end


# inspired by lcml in numbers.icn
procedure myLCM(L)
i := get(L)
while j := get(L) do
i := lcm(i, j)

return i
end


Problem 6

# The sum of the squares of the first ten natural numbers is,
# 1^(2) + 2^(2) + ... + 10^(2) = 385
#
# The square of the sum of the first ten natural numbers is,
# (1 + 2 + ... + 10)^(2) = 55^(2) = 3025
#
# Hence the difference between the sum of the squares of the first ten
# natural numbers and the square of the sum is 3025 − 385 = 2640.
#
# Find the difference between the sum of the squares of the first one
# hundred natural numbers and the square of the sum.
procedure problem6()
L := []
sum_squares := 0;
square_sum := 0;
every put(L, (1 to 100))
every sum_squares +:= !L^2

every square_sum +:= !L
square_sum := square_sum^2
d := square_sum - sum_squares
write(square_sum, " - ", sum_squares, " = ", d)

end


Problem 7

# By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
# that the 6^(th) prime is 13.
#
# What is the 10001^(st) prime number?
procedure problem7()
local p;
# prime() is from numbers.icn and is defined thusly:
# suspend 2 | ((i := seq(3, 2)) & (not(i = (k := (3 to sqrt(i) by 2)) * (i / k))) & i)

# Generate the primes and stop at the 10001:th
every p := prime() \ 10001
write(p)

end


Problem 8

# Find the greatest product of five consecutive digits in the 1000-digit number.
# 73167176531330624919225119674426574742355349194934
# 96983520312774506326239578318016984801869478851843
# 85861560789112949495459501737958331952853208805511
# 12540698747158523863050715693290963295227443043557
# 66896648950445244523161731856403098711121722383113
# 62229893423380308135336276614282806444486645238749
# 30358907296290491560440772390713810515859307960866
# 70172427121883998797908792274921901699720888093776
# 65727333001053367881220235421809751254540594752243
# 52584907711670556013604839586446706324415722155397
# 53697817977846174064955149290862569321978468622482
# 83972241375657056057490261407972968652414535100474
# 82166370484403199890008895243450658541227588666881
# 16427171479924442928230863465674813919123162824586
# 17866458359124566529476545682848912883142607690042
# 24219022671055626321111109370544217506941658960408
# 07198403850962455444362981230987879927244284909188
# 84580156166097919133875499200524063689912560717606
# 05886116467109405077541002256983155200055935729725
# 71636269561882670428252483600823257530420752963450
procedure problem8()
n := "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

## using lists
# L := []
# every i := (1 to (*n)-5 ) do {
# s := n[i:i+5] # string segment
# p := 1
# every p *:= !s # converts automatically to numbers
# put(L, p)
# }
# write(myMax(L))

# using string matching
this_max := 0
n ? {
while x := move(5) do {
move(-4)
p := product(x)
if p > this_max then
this_max := p
}
}

write("this_max: ", this_max)

end


Problem 9

# A Pythagorean triplet is a set of three natural numbers,
# a < b < c, for which, a^(2) + b^(2) = c^(2)
#
# For example, 3^(2) + 4^(2) = 9 + 16 = 25 = 5^(2).
#
# There exists exactly one Pythagorean triplet for which a + b + c = 1000.
# Find the product abc.
procedure problem9()

every c := 1 to 500 &
b := 1 to c &
a := 1 to b &
a + b + c = 1000 &
a^2 + b^2 = c^2
do {
write(a, "^2 + ", b, "^2 = ", c, "^2", " : ", a*b*c) & fail
}
end


Problem 10

# The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
#
# Find the sum of all the primes below two million.
procedure problem10()
s := 0
n := 2000000

every p := p10(n) & p < n & s +:= p
write(s)
end

procedure p10(n)
# prime() from factors.icn
suspend p:= prime() do
if p > n-1 then fail
end

Se även
Tidigare skriverier om Icon:
Programspråket Icon och stavningen av "Henning Mankell"
Fortsatt stavning av "Henning Mankell". Samt lite om agrep
Skapa strängar från reguljära uttryck - eller: Tystnaden de senaste dagarna


Huvudsajter
Icon
Unicon

Education och där speciellt Books där referensverken finns nedladdningsbara. Se speciellt The Icon Analyst var en tidskrift som innehöll intrikata artiklar om Icon såväl på bredden som på djupet.
Nyhetsgruppen comp.lang.icon ("Låg aktivitet")


För Unicon:
The Unicon book (PDF)
Mailing lista

Se även Wikipediasidorna
Icon (programming language)
Unicon (programming_language)
SNOBOL (som för övrigt råkade ut för en liten Wikipedia-skärmytsling förra veckan).

Posted by hakank at 09:53 FM Posted to Pyssel | Systemutveckling

september 28, 2008

Constraint programming: Fler MiniZinc-modeller, t.ex. Martin Gardner och nonogram

Förutom att ha lekt med de Javabaserade villkorsprogrammeringssystemet Choco version 2 har även några MiniZinc-modeller skapats sen sist.

Förra gången räknades till cirka 360 modeller (stora eller små). Nu är det cirka 440 stycken (stora och små), vilket innebär cirka 80 nya modeller. Som vanligt finns de på My MiniZinc page. De läggs upp där så fort som de är klara, så om du är intresserad av nya modeller är det bara att - mer eller mindre - regelbundet kolla den sidan.

Denna gång har det blivit en del problem från husguden Martin Gardner, mest beroende på att jag håller på att beta av samlingen med Martin Gardners pyssel i The Colossal Book of Short Puzzles and Problems, (ISBN: 9780393061147, sammanställd av Dana Richards).

Personliga favoriter
* nonogram.mzn, även känd som "painting by numbers". Utifrån rad- och kolumnsummor ska man skapa bilder. Jämför med "discrete tomography" som nämndes i Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem samt med "Survo puzzle" som nämndes i Nästan 36 modeller med villkorsprogrammering (constraint programming) i MiniZinc.
* two_cube_calendar.mzn: Two cube calendar. Till synes enkelt problem, men det var trixigt att modellera eftersom en siffra kan användas på två olika sätt.
* diffn.mzn. Placering av boxar utan att de överlappar varandra. Stödjer tre olika representationer (vilket tyvärr gör modellen lite svåröverskådlig).
* calculs_d_enfer.mzn: Calculs d'enfer. Yet another alfametiskt problem med några twistar: här används även negativa värden och man ska minimera det största absolutvärdet. En viktig sak är att använda korrekt heuristik annars går det långsamt att lösa problemet: den snabbaste jag hittade var "occurrence" respektive "indomain_max".


Martin Gardner
Detta är några problem från de första kapiteln av (den ovan nämnda) The Colossal Book of Short Puzzles and Problems. En bok att rekommendera. Man noterar redan på de första sidorna (om man inte läst Gardner tidigare för då vet man troligen detta redan) att en del standardexempel - t.ex. SEND + MORE = MONEY, Langfords heltalssekvens - beskrevs eller populariserades av Martin Gardner.

Nedanstående har det gemensamma kännetecknet att de - mig veterligen - inte modellerats i MiniZinc. I vissa fall har jag inte sett någon diskussion alls på nätet (i alla fall inte under dessa namn).

curious_set_of_integers.mzn: Curious set of integers
divisible_by_7.mzn: Divisible by 7
gardner_prime_puzzle.mzn: Prime puzzle
magic_squares_and_cards.mzn: Magic squares and cards
nine_digit_arrangement.mzn: Nine digit arrangements
nine_to_one_equals_100.mzn: Nine to one equals 100
nonogram.mzn
pool_ball_triangles.mzn: Pool ball triangles
two_cube_calendar.mzn: Two cube calendar


Andra pyssel och matematiska gåtor
bank_card
calculs_d_enfer.mzn: Calculs d'enfer puzzle (from the NCL manual), se kommentar ovan
coins_problem.mzn: Minimize the number of coins...
family_riddle.mzn: Family riddle
magic_hexagon.mzn: Magic hexagon
message_sending: Message sending


Operations research, linear programming, integer programming
lectures: ett scheduleringsproblem
scheduling_chip: ännu ett scheduleringsproblem


Non linear problems
spreadsheet.mzn, exempel på problem som ofta löses i spreadsheets


Combinatorics
maximum_subarray.mzn: Maximum subarray
set_packing.mzn, set packing
set_covering_skiena.mzn, set covering (ännu ett exempel)
all_paths_graph.mzn, skapa vägar med utgångspunkt från en grafrepresentation


Global constraints
Som vanligt har även några global constraints modellerats. Förutom att många av dem är nyttiga i sig, är modelleringen av dem en nyttig övning. (Nu finns det cirka 100 global constraints modellerade, endast en tredjedel av den fulla listan. I och för sig är cirka 40-50 global constraints redan definierade i MiniZinc, antingen inbyggda eller i global.mzn, men det är i alla fall en massa kvar...)

contains_array
cumulative_test
diffn
discrepancy
disjunctive
domain
domain_constraint
imply
in_interval
in_set
indexed_sum
inverse_within_range
ith_pos_different_from_0
k_same
k_same_modulo
lex2
lex_between
lex_chain_less
lex_different
lex_greater
max_index
min_index
nclass
open_alldifferent
product_test
roots_test
same_interval
same_modulo
shift
sliding_sum
sliding_time_window
sliding_time_window_from_start
smooth
soft_same_var
sort_permutation
weighted_sum (not in the catalogue)


Prolog/constraint logic programming benchmarks
Här är några benchmarks för Prolog eller constraint programming som inte tidigare modellerats i MiniZinc.

crossbar.mzn
crypta.mzn
eq10.mzn
fractions.mzn
grocery2.mzn
magic3.mzn
magic4.mzn
multipl.mzn
olympic.mzn
parallel_resistors.mzn
sudoku_25x25_250.mzn
voltage_divider.mzn


Övrigt
fizz_buzz Liten programmeringsövning
huey_dewey_louie, litet logiskt problem
power, variant av power-funktionen (som ännu inte funkar i MiniZinc)

Posted by hakank at 08:17 EM Posted to Constraint Programming | Matematik | Pyssel

september 14, 2008

Constraint programming i Java: Choco version 2 släppt - samt jämförelse med JaCoP

I JaCoP - Java Constraint Programming solver gjordes en jämförelse mellan två olika constraint programming system (villkorsprogrammering) i Java:
- JaCoP (se även My JaCoP page)
- Choco (My Choco page)

Då avvaktade jag med framförallt modeller i och mer information om Choco tills det var mer stabilt (beta-versionen har ändrats mycket den senaste tiden) Det är det nu: I onsdags (10 september 2008) släpptes version 2.0 (lagom till internationella constraint programming-kongressen som börjar idag, se nedan under Relaterat). Denna version har en ny hemsida (cf. sidan för Choco version 1).

Choco version 2

Choco presenteras så här:
The CHOCO development team is eager to announce the release of the new version of its open-source constraint solver: CHOCO.

Choco is Java library that can be used for:
* teaching (a user-oriented constraint solver with open-source code)
* research (state-of-the-art algorithms and techniques, user-defined constraints, domains and variables)
* real-life applications (many application now embed choco)

Choco is final-user oriented. It has been under heavy refactoring from V1 to V2. New constraints, new features have been offered.

Choco is available online with a complete documentation, tutorials, various materials, forums, etc.


Dokumentation


Till skillnad från JaCoP finns det mycket dokumentation om Choco, t.ex. en bra och inträngande genomgång hur man skapar modeller, tweakar lösningar och mer avancerade användningar.

Sajten innehåller följande huvuddelar:


Ett exempel: Minesweeper


I JaCoP - Java Constraint Programming solver presenterades JaCoP-modellen för Minesweeper. Här är motsvarande modell i Choco. Input till programmet är en problemfil, t.ex. minesweeper0.txt.

Jag har tagit bort en del saker för att göra listningen kortare. Den fullständiga modellen finns i MineSweeper.java.

Den observante kan notera att det är i stort sett samma modell, med endast några få skillnader:
- namn på variablerna: IntegerVariable i Choco, FDV i JaCoP
- metod att skapa variabler: makeIntVar(...) respektive new FDV(store,...). Notera att Choco har en metod för att initiera en array: makeIntVarArray.
- metod för att ange villkoren: model.addConstraint respektive store.impose
- själva villkoren (constraints), i choco behöver man inte new:a dessa villkor. Se mer om villkoren nedan.

public class MineSweeper {
    int r;        // number of rows
    int c;        // number of cols
    int X = -1;  // represents the unknown value in the problem matrix
    int[][] problem; // The problem matrix
    IntegerVariable[][] game;    // The IntegerVariable version of the problem matrix.
    IntegerVariable[][] mines;   // solution matrix: 0..1 where 1 means mine.
    Model model;
    CPSolver s;
    public void model() {
        model = new CPModel();
        if (problem == null) {
            r = 8;
            c = 8;
            int problemX[][] = {{X,2,X,2,1,1,X,X},
                                {X,X,4,X,2,X,X,2},
                                {2,X,X,2,X,X,3,X},
                                {2,X,2,2,X,3,X,3},
                                {X,X,1,X,X,X,4,X},
                                {1,X,X,X,2,X,X,3},
                                {X,2,X,2,2,X,3,X},
                                {1,X,1,X,X,1,X,1}};
            problem = problemX;
        }
        /*
         * Initialize the constraint variables.
         */
        mines = new IntegerVariable[r][c];
        game  = new IntegerVariable[r][c];
        for(int i = 0; i < r; i++) {
            mines[i] = makeIntVarArray("m_" + i, c, 0,1);
            game[i] = makeIntVarArray("g_" + i, c, -1,8);
        }
        // Add the constraints
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // This is a known value of neighbours
                if (problem[i][j] > X) {
                    // mirroring the problem matrix.
                    model.addConstraint(eq(game[i][j], problem[i][j]));
                    // This could not be a mine.
                    model.addConstraint(eq(mines[i][j], 0));
                    // Sum the number of neighbours: same as game[i][j].
                    ArrayList lst = new ArrayList();
                    for(int a = -1; a <= 1; a++) {
                        for(int b = -1; b <= 1; b++) {
                            if (i+a >= 0 && j+b >=  0 &&
                                i+a < r && j+b < c) {
                                lst.add(mines[i+a][j+b]);
                            }
                        }                        
                    }
                    model.addConstraint(eq(sum(lst.toArray(new IntegerVariable[1])), game[i][j]));
                } // end if problem[i][j] > X
            } // end for j
        } // end for i
    } // end model
   //
   // Search
   //
    public void search() {
        s = new CPSolver();
        s.read(model);
        s.solve();        
        if (s.isFeasible()) {
            int sol = 1;
            do {
                System.out.println("\nSolution # " + sol);
                for(int i = 0; i < r; i++) {
                    for(int j = 0; j < c; j++) {
                        System.out.print(s.getVar(mines[i][j]).getVal() + " ");
                    }
                    System.out.println();
                }
                sol++;
            } while (s.nextSolution() == Boolean.TRUE);
        } else {
            System.out.println("No solutions.");
        } // end if result
    } // end search
   //
   // Main
   //
    public static void main(String args[]) {
        MineSweeper minesweeper = new MineSweeper();
        String file = "";
        if (args.length > 0) {
            file = args[0];
            minesweeper.readFile(file);
        }
        minesweeper.model();
        minesweeper.search();
    } // end main
} // end class


Resultatet:

readFile(minesweeper0.txt)
6
6
..2.3.
2.....
..24.3
1.34..
.....3
.3.3..
22[+0] millis.
16[+0] nodes
20[+0] backtracks
20[+0] fails

Solution # 1
1 0 0 0 0 1
0 1 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 1


Fördelar/nackdelar

* Exempel. Till skillnad från JaCoP så finns det inte så många fullständiga exempel i distributionen. Några av exemplen är kvar från version 1 och är inte portade till version 2 (koden är helt enkelt bortkommenterad). Det är lite synd. I gengäld finns många test cases för i stort sett samtliga metoder i systemet, vilket är informativt.

* Dokumentation. Som ovan sagt är dokumentationen (på sajten) mycket bra och förklarar i stort sett allting. Man bör dock notera att eftersom den slutliga version 2 är så pass ny finns det några ställen där man inte uppdaterat till denna version. Några constraints är inte heller dokumenterade. Jag antar att allt sådant kommer att fixas till snart.

* Domäner. Choco styrka är finita domäner (heltal eller sådant som kan representeras av heltal), men kan - till skillnad från JaCoP - hantera mängder (sets) samt flyttal. Stödet för de två sistnämda är dock inte lika stort eller stablilt som för finita domäner.

* Global constraints. På sidan Constraints presenteras de (global) constraints som finns i systemet. De flesta förväntade finns med såsom allDifferent, boolChanneling, distance etc. Jag blev dock lite förvånad att count (villkor för att ange att ett visst värde ska ha ett visst antal förekomster) saknades. I YoungTableaux behövdes nämligen ett sådant villkor, men det implementerades i stället genom att trixa med globalCardinality (en generalisering av count).

Speciellt intressant är de relativt nya geost för att hantera geometriska villkor, och tree för "tree partitioning".

Man kan också notera att det finns en viss skillnad i inställning av "convenient constraints" mellan Choco och JaCoP. Efter en fråga till JaCoPs utvecklare om varför villkoret XminusYeqZ saknades kom svaret att man följer en minimalistisk princip att endast implementera de nödvändiga villkoren (man kan använda XplusYeqZ i stället). I Choco verkar man inte ha denna princip: där finns såväl plus som minus; man kan initiera en hel vektor på ett bräde med makeVarIntArray och behöver inte loopa över elementens makeVarInt etc.

* XCSP. XCSP är ett XML-format för constraint satisfaction/programming-problem som används bl.a. i Third International CSP Solver Competition (se även nedan under Relaterat). Choco kan läsa i detta format. Efter de tester jag gjort tycker jag att Chocos stöd är något bättre än JaCoPs. Choco kan dock inte skriva XCSP (det kan JaCoP), men det är på gång.

* Prestanda. Jag har inte gjort några formella tester men min känsla är att Choco nästan alltid är snabbare och kan hantera större problem än JaCoP. Men det är alltså en subjektiv åsikt.

* Open source. Choco är open source till skillnad från JaCoP vilket naturligtvis är en stor fördel. JaCoP kommer enligt uppgift att släppas öppet inom kort, men än så länge finns det inte fritt tillgängligt.

Det finns ett Subversion-repositorium på https://choco.svn.sourceforge.net/svnroot/choco . Jag använder fortfarande version 2.0.0 men kommer väl snart att gå över till 2.0.1 (som skapades i förrgår, dvs strax efter den officiella releasen).


Slutkommentar
I och för sig tycker jag om JaCoP eftersom det har en slim och "naturlig" klassmodell, har många exempel. Trots det kommer jag nog mestadels att använda Choco för villkorsprogrammering i Java eftersom det är (än så länge) ett mer fullständigt system, har bättre dokumentation och drivs av fler utvecklare (vad jag förstår är det åtminstone en heltidstjänst enkom för att utveckla Choco).

Mina Choco-modeller

My Choco page finns ett antal Choco-modeller. Det är (i skrivande stund) en portning av de modeller som finns (i skrivande stund) på My JaCoP page (förutom DeBruijnIterate som var en specialmodell för att generera lösningar batch-vis).

Modellerna är (direkt från sidan):


Relaterat


Choco: Constraint Programming i Java om Choco version 1, som skrev i april 2006.


Intressant nog börjar stora villkorsprogrammeringskonferensen International Conference on Principles and Practice of Constraint Programming idag och håller på till 18 september. Jag väntar speciellt med spänning på resultatet av två olika tävlingar:
- Third International CSP Solver Competition
- MiniZinc Challenge 2008 (Rules). En av utvecklarna av MiniZinc har antytt att några av mina MiniZinc-modeller med på ett hörn i denna tävling.

Posted by hakank at 10:56 FM Posted to Constraint Programming | Pyssel

augusti 17, 2008

JaCoP - Java Constraint Programming solver

Fast det jag egentligen hållit på med den senaste veckan är att kolla in JaCoP, ett (annat) constraint programming-system i Java.

Det som beskrivs här nedan är JaCoP version 2. Information om version 1.3 finns på ett annat ställe (LTH, Lunds Universitet), men det är alltså 2:an som gäller.


JaCoP


JaCoP presenteras på följande sätt:

Java Constraint Programming solver, JaCoP in short, is a Java library, which provides Java user with Constraint Programming technology. JaCoP is actively developed since year 2001. Krzysztof Kuchcinski and Radoslaw Szymanek are the authors of this Java library. They are working in their free time to improve this library. They both have worked countless hours to create software which is frequently used not only in their research work.

...

JaCoP is available for free as Java library for research and educational purposes. JaCoP is not free for commercial applications. However, our intention is to charge minimum fees in order to have some additional help in creating better documentation and better product.

I JaCoP google group berättas att man har planer att skapa en "dual license" (dvs både en fri och en komersiell licens).

För att få tillgång till JaCoP-distributionen måste man - än så länge - maila Radoslaw Szymanek (radoslaw.szymanek@gmail.com ) med en förfrågan, helst på engelska. Berätta gärna att du läste om JaCoP här.


Dokumentation


JaCoP Web är stället där man hittar information om systemet. Tyvärr finns ännu inte så mycket dokumenterat för version 2, vilket är en stor nackdel. I distributionen finns ett stort (>= 57) antal exempel som gör att man får bra tips hur JaCoP används (eventuellt finns någon av nedanstående modeller med). Man lär sig även mycket genom att studera den övriga källkoden.

SudukoACSP förklaras detaljerat och pedagogiskt om de viktigaste JaCoP-metoderna via lösning av Sudoku-spelet. Rekommenderad läsning.

Man kan ställda frågor på JaCoPFAQ (kräver registrering).

En PDF-presentation Introduction to JaCoP för version 1 finns på kurssidan EDA340: Constraint Programming (LTH, Lunds Universitet).


Ett exempel: Minesweeper


Här nedan visas ett exempel av ett JaCoP-program. Jag har valt Minesweeper ("MS Röj") för enkel jämförelse med MiniZinc modellen på Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life.

En stor skillnad mellan MiniZinc-modellen och JaCoP-modellen är - förutom att JaCop-modellen är mer pratig - att det finns stöd för att läsa in externa problem-filer (MiniZinc har ett annat sätt att lösa detta).

Input till programmet är en problemfil, t.ex. minesweeper0.txt:

# Minesweeper problem.
# This problem file is used by
# http://www.hakank.org/JaCoP/MineSweeper.java
#
# Problem from Gecode/examples/minesweeper.cc problem 0
6
6
..2.3.
2.....
..24.3
1.34..
.....3
.3.3..


Här nedan visas de mest relevanta delarna av programmet. Det är alltså inte ett komplett program.

import JaCoP.constraints.*;
import JaCoP.core.*;
import JaCoP.search.*;
public class MineSweeper {
    // declare the variables
    int r;        // number of rows
    int c;        // number of cols
    int X = -1;  // represents the unknown value in the problem matrix
    int[][] problem; // The problem matrix
    FDV[][] game;    // The FDV version of the problem matrix.
    FDV[][] mines;   // solution matrix: 0..1 where 1 means mine.
    Store store;
    public void model() {
        store = new FDstore();
        // Initialize the constraint variables.
        mines = new FDV[r][c];
        game  = new FDV[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // 0: no mine, 1: mine
                mines[i][j] = new FDV(store, "m_" + i + "_" + j, 0, 1);
                // mirrors the problem matrix
                game[i][j] = new FDV(store, "g_" + i + "_" + j, -1, 8);
            }
        }
        // Add the constraints
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // This is a known value of neighbours
                if (problem[i][j] > X) {
                    // mirroring the problem matrix.
                    store.impose(new XeqC(game[i][j], problem[i][j]));
                    // This could not be a mine.
                    store.impose(new XeqC(mines[i][j], 0));
                    // Sum the number of neighbours: same as game[i][j].
                    ArrayList lst = new ArrayList();
                    for(int a = -1; a <= 1; a++) {
                        for(int b = -1; b <= 1; b++) {
                            if (i+a >= 0 && j+b >=  0 &&
                                i+a < r && j+b < c) {
                                lst.add(mines[i+a][j+b]);
                            }
                        }                        
                    }
                    store.impose(new Sum(lst, game[i][j]));
                } // end if problem[i][j] > X
            } // end for j
        } // end for i
    } // end model

Till skillnad från MiniZinc (men i likhet med Choco, Gecode etc) måste man uttryckligen ange vilken sökmetod som ska användas. Här används metoden SimpleMatrixSelect över variabelmatrisen mines. Här skrivs endast den sista lösningen ut.

(Jag har önskat en möjlighet att skriva ut samtliga lösningar via en iterator istället för att alla lösningar räknas ut innan presentationen, och det kanske kommer.)

    public void search() {
        SelectChoicePoint select = 
            new SimpleMatrixSelect (mines,
                              new SmallestDomain(),
                              new IndomainMin ()
                              );
        Search label = new DepthFirstSearch ();
        label.getSolutionListener().searchAll(true);
        label.getSolutionListener().recordSolutions(true);
        boolean result = label.labeling(store, select);
        int numSolutions = label.getSolutionListener().solutionsNo();
        if (result) {
            System.out.println("\nThe last solution:");
            for(int i = 0; i < r; i++) {
                for(int j = 0; j < c; j++) {
                    System.out.print(mines[i][j].value() + " ");
                }
                System.out.println();
            }
            System.out.println("numSolutions: " + numSolutions);
        } else {
            System.out.println("No solutions.");
        } // end if result
    } // end search


Fördelar/nackdelar


Här är några kommentarer om JaCoP.

Intrycket efter en vecka är att det är ett trevligt system, och för det mesta är det naturligt hur man programmerar modellerna. De lite mer avancerade modellerna nedan, Minesweeper och de Bruijn sekvenser, portades från MiniZinc-modellerna ganska rakt av och utan några större problem. Det är naturligtvis en fördel att ha modellerat en hel del constraint programming-problem innan.

* Bra exempel. Det finns många exempel som visar hur man använder JaCoP. Många är standardexempelmen det finns några nya saker.

* Dokumentation. En av de stora nackdelarna är avsaknaden av dokumentation, men eftersom det är en enkel klassstruktur är det rätt enkelt att hitta constraints (de finns i katalogen JaCoP/constraints och sökmetoderna (JaCoP/search.

* Finita domäner. JaCoP hanterar endast finita domäner, dvs stöd för mängder (sets) saknas, liksom flyttal. Det senare gör inte så mycket för min egen del, däremot saknar jag sets för modellering av en del problem. En kommentar om detta från utvecklaren av JaCoP finns här.

* Global constraints. JaCoP har ett antal global constraints, vilket förenklar både syntaktiskt och prestandamässigt.

* XCSP. XCSP är ett XML-format för constraint satisfaction/programming problem som används bl.a. i Third International CSP Solver Competition. JaCoP kan både läsa och skriva i detta format. Trevligt! (Tänk på att skapa XML-filen innan sökningen börjar, annars hårdkodas lösningen.)

* Prestanda. Jag har inte gjort några formella tester av hastighet eller minnesanvändning, men de flesta av mina modeller (se nedan) har lösts snabbt, åtminstone lika snabbt som den snabbaste av de solvers som finns för MiniZinc (vilket oftast är Gecode/fz).

* Java. Naturligtvis är det mestadels en fördel att använda ett "riktigt" programspråk och baka in stöd för constraint programming där. Ett exempel på detta är Minesweeper (och Quasigroup completion problem) där man kan läsa in problemfiler av godtyckligt format. Problemet är att det blir emellanåt väldigt pratigt, t.ex. just vid filinläsning, och det är något som jag inte tycker om (och är en stor orsak till min förtjusning över agila programspråk). Ett framtida projekt är att skriva om några modeller till Groovy.

* Jämförelse med Choco 2.0. När jag började med JaCoP så var ett av målen att jämföra med Choco version 2, ett annat constraint programming system i Java. Choco 2.0 är dock för närvarande i beta-status så jag avvaktar med detta till det blivit lite mer stabilt. (Det har tidigare skrivits om Choco version 1 här.)

Choco är mer kompetent än (existerande distribution av) JaCoP: mer dokumentation (både pedagogiska texter och JavaDoc), stöd för mängder och flyttal, och det finns mängder av test-program. Dock finns det betydligt färre "riktiga" exempel än för JaCoP.

Som sagt. Det är ett framtida projekt att jämföra JaCoP och Choco.

Mina JaCoP-modeller

My JaCoP page har jag lagt ett antal modeller för version 2. Några av dem kräver utilitetsklassen HakankUtil.java. Samtliga program (i alla fall i nedanstående lista) finns även som MiniZinc-modell (MiniZinc är ett alldeles utmärkt verktyg för att prototypa constraint programming-problem).


Se även

* Sidan för JaCoP version 1. Där finns referenser som fortfarande är relevanta.

* Choco: Constraint Programming i Java där JaCoP nämns en passant som ett system att kolla in.

Posted by hakank at 10:00 FM Posted to Constraint Programming | Pyssel

juli 20, 2008

Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life

Här är några fler MiniZinc modeller som skapats sedan sist. För en fullständig lista över samtliga publicerade modeller, se My MiniZinc page.

I samtliga modeller anges referenser, inspiration etc.

Personligen tycker jag följande modeller är lite kul:
* Minesweeper (som presenteras speciellt nedan)
* Game of Life
* Quasigroup completion problem (se nedan för ett antal testproblem)
* Födelsedagsproblemet


Minesweeper


Tänkte nämna något mer om Minesweeper.

Modellen till Minesweeper är - möjligen förvånansvärt - enkel. Notera att man s.a.s. "räknar baklänges": genom att summera minorna (mines) för att få de värden som ges i problemet (game). Sådant är typiskt i constraint programming.


% MiniZinc model for Minesweeper.
int: r; % rows
int: c; % column
int: X = -1; % the unknowns

% encoding: -1 for unknown, >= 0 for number of mines in the neighbourhood
array[1..r, 1..c] of -1..8: game;
array[1..r, 1..c] of var 0..1: mines;

constraint
forall(i in 1..r, j in 1..c) (
(
(game[i,j] >= 0 )
->
game[i,j] = sum(a,b in {-1,0,1} where
i+a > 0 /\ j+b > 0 /\
i+a <= r /\ j+b <= c
)
(mines[i+a,j+b])
)
/\
(game[i,j] > X -> mines[i,j] = 0)
/\
(game[i,j] = X <- mines[i,j] = 1)
)
;

Ett exempelproblem, där ett tal anger hur många bomber det finns som grannar och X att vi inte vet något om rutan (det kan vara en bomb men behöver inte vara det).

% Minesweeper example
r = 6;
c = 6;
game = array2d(1..r, 1..c, [
X,X,2,X,3,X,
2,X,X,X,X,X,
X,X,2,4,X,3,
1,X,3,4,X,X,
X,X,X,X,X,3,
X,3,X,3,X,X,
]);

Lösningen - som kommer blixsnabbt - är följande. Positionerna av bomberna markeras med 1.

1 0 0 0 0 1
0 1 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 1

Minesweeper har visats vara ett s.k. NP-komplett problem, dvs ohyggligt svårt att lösa generellt för godtyckligt stora problem. De exempel som används i modellen är dock så (förhållandevis) små att lösningen kommer direkt.

Se vidare
Richard Kaye's Minesweeper Pages
Minesweeper (Wikipedia)
Ian Stewart on Minesweeper
The Authoritative Minesweeper: Articles and Announcements

Automatisk "lösning" av Minesweeper i Mozart/Oz där fler referenser ges.

Övriga modeller

Här är de övriga modellerna, grupperade enligt samma princip som på My MiniZinc page.

Puzzles, small and large

Global constraints

Operations research, linear programming, integer programming

  • Markov chains (fertlizer example from Taha "Operations Research")
  • Talent, exempel från ILOG OPL

Combinatorial problems

Other models


Posted by hakank at 08:23 EM Posted to Constraint Programming | Matematik | Pyssel

juli 07, 2008

Fler MiniZinc modeller kring recreational mathematics

I Martin Chlond's Integer Programming Puzzles i MiniZinc förevisades MiniZinc-modeller för Martin Chlonds Integer Programming Puzzles.

Här är några fler i samma stil (recreational mathematics) som jag just har lagt upp på min Minizinc-sida . Det är MiniZinc-modeller baserade på Chlonds Puzzle artiklar (och de där ingående integer programming-modellerna) i INFORMS Transactions on Education (en öppen tidskrift om operational research).


Och så några andra recreational mathematics modeller som publicerades samtidigt:

Posted by hakank at 07:53 EM Posted to Constraint Programming | Matematik | Pyssel

juli 04, 2008

Martin Chlond's Integer Programming Puzzles i MiniZinc

Som tidigare nämnts är Puzzles - Integer Programming in Recreational Mathematics en mycket trevlig samling pyssel skapad av Martin Chlond. De flesta problemen är klassiker inom området (recreational mathematics) och flera används som paradigmproblem i constraint programming eller integer programming.

I april skrevs MiniZinc-modeller för samtliga problem men jag har inte kommit loss att hyfsa till dem. Förrän nu. Samliga 48 problem har nu gåtts igenom så att de har en enhetlig struktur, kommentarer är på engelska etc.

Förutom MiniZinc-modellen nedan finns även en länk till Martin Chlonds lösning av problemet (oftast skrivet som en XPress Model, men de allra sista är i AMPL). MiniZinc-modellerna är i stort sett en konvertering av Chlonds modell. I några fall har flyttalsrepresentationer omvandlats till heltalsrepresentationer.

Nedanstående listning finns även på min MiniZinc-sida, men det blir en bättre bäring om de även listas här.

Martin Chlond's Integer Programming Puzzles

The collection is separated in four sections where the problems is presented:
* Integer Programming Puzzles section 1
* Integer Programming Puzzles section 2
* Integer Programming Puzzles section 3
* Integer Programming Puzzles section 4


Problems: Integer Programming Puzzles section 1
Solutions:
Twelve draughts puzzle (Chlond's solution)
Description : Twelve draughts puzzle Source : Boris Kordemsky - The Moscow Puzzles (P36)

Coin puzzle
(Chlond's solution)
Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)

Egg basket puzzle
(Chlond's solution)
Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

Evens puzzle
(Chlond's solution)
Description : Evens puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P8)

Fifty puzzle
(Chlond's solution)
Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)

Honey division puzzle
(Chlond's solution)
Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics

Wine cask puzzle
(Chlond's solution)
Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)

Knight domination puzzle - all squares threatened
(Chlond's solution)
Description : Knight domination puzzle - all squares threatened
Source : M Kraitchik - Mathematical Recreations (P256)

Mango puzzle
(Chlond's solution)
Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)

Remainder puzzle
(Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

5 X 5 puzzle
(Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown

Lights on puzzle
(Chlond's solution)
Description : Lights on puzzle
Source : Unknown


Problems: Integer Programming Puzzles section 2

Solutions:
Clarke's tobacconist
(Chlond's solution)
Description : Clarke's tobacconist
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Tommy's Birthday Coins
(Chlond's solution)
Description : Tommy's Birthday Coins
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Lewis Carroll coin puzzle
(Chlond's solution)
Description : Lewis Carroll coin puzzle
Source : Wakeling, E., (1995), Rediscovered Lewis Carroll Puzzles, Dover.

Dudeney's tea mixing problem
(Chlond's solution)
Description : Dudeney's tea mixing problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Jive turkeys
(Chlond's solution)
Description : Jive turkeys
Source : rec.puzzles

Public School Problem
(Chlond's solution)
Description : Public School Problem
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Dudeney's bishop placement problem I
(Chlond's solution)
Description : Dudeney's bishop placement problem I
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Dudeney's bishop placement problem II
(Chlond's solution)
Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Kraitchik's queen placement problem
(Chlond's solution)
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.

Schuh's queen placement problem
(Chlond's solution)
Description : Schuh's queen placement problem
Source : Schuh, F., (1943), Wonderlijke Problemen;
Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.

Dudeney's queen placement problem
(
Chlond's solution)
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Joshua and his rats
(Chlond's solution)
Description : Joshua and his rats
Source : Sole, T., (1988), The Ticket to Heaven, Penguin Books


Problems: Integer Programming Puzzles section 3

Solutions:
The Abbott's Puzzle
(Chlond's solution)
Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The Abbott's Window
(Chlond's solution)
Description : The Abbott's Window
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The First Trial
(Chlond's solution)
Description : The First Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Second Trial
(Chlond's solution)
Description : The Second Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Third Trial
(Chlond's solution)
Description : The Third Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fourth Trial
(Chlond's solution)
Description : The Fourth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fifth Trial
(Chlond's solution)
Description : The Fifth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Sixth Trial
(Chlond's solution)
Description : The Sixth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

Werewolves II
(Chlond's solution)
Description : Werewolves II
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Werewolves IV
(Chlond's solution)
Description : Werewolves IV
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Earthlings
(Chlond's solution)
Description : Earthlings
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling

Equal Vision
(Chlond's solution)
Description : Equal Vision
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling


Problems: Integer Programming Puzzles section 4

Solutions:
On the road
(Chlond's solution)
Description : On the road
Source : Poniachik, J. & L, (1998), Hard-to-solve Brainteasers, Sterling

The Riddle of the Pilgrims
(Chlond's solution)
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.

The Logical Labyrinth
(Chlond's solution)
Description : The Logical Labyrinth
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The gentle art of stamp-licking
(Chlond's solution)
Description : The gentle art of stamp-licking
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The crowded board
(Chlond's solution)
Description : The crowded board
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Non-dominating queens problem
(Chlond's solution)
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt

Enigma
(Chlond's solution)
Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani

Price change puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations (p 33-35), Dover

Book buy puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Shopping puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Book discount problem
(Chlond's solution)
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling

Seven 11 (Chlond's solution)
Source: alt.math.recreational

Posted by hakank at 07:09 FM Posted to Constraint Programming | Pyssel

juni 29, 2008

Gruppteoretisk lösning av M12 puzzle i GAP

I Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc) presenterades det gruppteoretiska pysslet M12, då med en lösning i MiniZinc (modellen M12.mzn).

När jag läste om M12 tänkte jag att det skulle vara skoj med även en gruppteoretisk lösning eftersom det är ett gruppteoretiskt problem. En sådan lösning har nu gjorts med hjälp av det abstrakta algebraiska systemet GAP. Numera finns GAP även med i distributionen av det öppna matematiska (och mycket trevliga) systemet Sage.

Uppdatering
Efter lite funderande kom jag på en bättre lösning. I stället för att ändra en massa i denna text skrev jag en ny: Gruppteoretisk lösning av M12 puzzle i GAP - take 2, vilken se.


Kort beskrivning av M12
Som tidigare beskrivits går M12-pysslet ut på att man har en sekvens av 12 siffror i en härlig oordning och man ska med hjälp av två operationer återställa sekvensen till 1,2,3,4,5,6,7,8,9,10,11,12. Operationerna är:
Merge: [1, 12, 2, 11,3, 10, 4, 9, 5, 8, 6, 7] blir [1,2,3,4,5,6,7,8,9,10,11,12].
Inverse: Vänder listan om, [1,2,3,4,5,6,7,8,9,10,11,12] blir [12,11,10,9,8,7,6,5,4,3,2,1]. Not, jag kallar operationen (av historiska skäl) för Reverse här nedan.


GAP-program
Här är GAP-programmet (M12_gap.txt). Resultat från ett kommando eller kommentar skrivs efter "#".


Först definierar vi operatorerna, dvs generatorerna i gruppen. Här används PermList som tar en lista och skapar en permutationscykel.

#
# Solving the M12 for a specific sequence
#

#
# Define the operators
#

# Reverse (Inverse)
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
# (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

# Merge
merge := PermList([1,12,2,11,3,10,4,9,5,8,6,7]);
# (2,12,7,4,11,6,10,8,9,5,3)

Skapa gruppen g och gör några tester.


# Create the group
g:=Group([reverse, merge]);
# Group([ (1,12)(2,11)(3,10)(4,9)(5,8)(6,7), (2,3,5,9,8,10,6,11,4,7,12) ])

# Which group is it?
StructureDescription(g);
# "M12"

Size(g);
# 95040

Bra, det är alltså gruppen M12, dvs Mathieu-grupp av ordningen 12. Notera att det finns ett inbyggt kommando för att skapa en Mathieugrupp (MathieuGroup), men den har inte de generatorer som vil ska använda, alltså rullar vi vår egen.


Nu börjar det roliga. Låt oss som exempel ta följande sekvens som nyss skapats av M12-programmet.


#
# Create the puzzle to solve
#
puzzle:=[4, 5, 11, 1, 9, 6, 3, 10, 2, 7, 12, 8];;


För att få reda på lösningen görs en "faktorisering", med hjälp av funktionen Factorization.


Factorization(g, PermList(puzzle)^-1);
# x1*x2^2*x1*x2^-5*x1*x2^-5

Här har vi en lösning som ska tolkas som operationer i pysslet:

x1*x2^2*x1*x2^-5*x1*x2^-5

x1 betyder den första generatorn (dvs Reverse/Inverse) och x2 är Merge.

Det finns två saker att tänka på här:
- man ska läsa sekvensen baklänges
- alla operationer med negativ exponent måste konverteras till en positiv exponent. Det görs med en enkel subtraktion: x2^-5 innebär samma sak som x2^(11-5) = x2^6

Om vi översätter enligt ovanstående två regler blir det:

x2^6 x1 x2^6 x1 x2^2 x1

Så, uttolkat i samma form som M12-applikationen blir lösningen följande. Tänk på att vi arbetar med lösningen bakifrån och att x1 är I och x2 är M:

M6 I M6 I M2 I

Detta är en lösning med 6+1+6+1+2+1 = 17 steg.


En variant

Förutom Factorization finns det en annan metod, och det är den som generellt rekommenderas för att göra denna typ av "faktoriseringar". Tyvärr tenderar den att generera längre lösningar än med Factorization.


#
# This is the recommended function for factorizations, but it gives longer
# solutions (strings) than Factorization.
#

#
# Create names to identify the operations
#
M:=g.2; R:=g.1;
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);

#
# Now, solve the puzzle
#
PreImagesRepresentative(hom,PermList(puzzle)^-1);
# M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Lösningen är alltså:

M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Notera att R^-1 ska tolkas som en Inverse-operation.

Ovanstående motsvarar följande M12-operationer:

M2 I M10 I M8 I M3 I M I M4 I M8

Detta är en lösning på 2 + 1 + 10 + 1 + 8 + 1 + 3 + 1 + 1 + 1 + 4 + 1 + 8 = 42 steg, vilket är mycket längre än Factorization-approachen.


Man bör notera att dessa faktoriseringar är optimerade att få så små exponenter som möjligt oavsett om det är positiva eller negativa exponenter. Vi är dock endast intresserade av positiva exponenter och lider därför av denna optimering.

Om man adderar exponenterna utan tecken, ger Factorization i alla fall en enklare lösning.

Factorization: x1*x2^2*x1*x2^-5*x1*x2^-5 = 1 + 2 + 1+ 5 +1+ 5 = 15 steg.

PreImagesRepresentative: M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2 = 3 + 1 + 4 + 1 + 1+ 3+ 1 + 3+ 1+ 1 + 1 + 2 = 22 steg.


Båda dessa faktoriseringar går mycket snabbt, typ någon sekund eller så.


Jämförelse med MiniZinc-lösningen
Jag testade att köra pysslet med MiniZinc-modellen M12.mzn. Den tar väldigt lång tid (typ 10-tals minuter) och ger följande lösning på 18 steg, dvs något sämre än Factorization-varianten. Operatorn 1 motsvarar Merge och operatorn 2 motsvarar Inverse.


2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2

dvs operationerna: R M6 R M2 R M R M3 R M

Så här ser sekvensen ut för respektive operation. Siffran till vänster är operationen. Första raden är ursprungssekvensen och är endast med för presentationens skull.


0: 4 5 11 1 9 6 3 10 2 7 12 8
2: 8 12 7 2 10 3 6 9 1 11 5 4
1: 8 7 10 6 1 5 4 11 9 3 2 12
1: 8 10 1 4 9 2 12 3 11 5 6 7
1: 8 1 9 12 11 6 7 5 3 2 4 10
1: 8 9 11 7 3 4 10 2 5 6 12 1
1: 8 11 3 10 5 12 1 6 2 4 7 9
1: 8 3 5 1 2 7 9 4 6 12 10 11
2: 11 10 12 6 4 9 7 2 1 5 3 8
1: 11 12 4 7 1 3 8 5 2 9 6 10
1: 11 4 1 8 2 6 10 9 5 3 7 12
2: 12 7 3 5 9 10 6 2 8 1 4 11
1: 12 3 9 6 8 4 11 1 2 10 5 7
2: 7 5 10 2 1 11 4 8 6 9 3 12
1: 7 10 1 4 6 3 12 9 8 11 2 5
1: 7 1 6 12 8 2 5 11 9 3 4 10
1: 7 6 8 5 9 4 10 3 11 2 12 1
2: 1 12 2 11 3 10 4 9 5 8 6 7
1: 1 2 3 4 5 6 7 8 9 10 11 12 % Solution!

Posted by hakank at 08:25 EM Posted to Constraint Programming | Matematik | Pyssel

juni 24, 2008

Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc)

Här är några matematiska / logiska pyssel med lösningar i MiniZinc.

n-puzzle (8-puzzle, 15-puzzle)

n-puzzle (8-puzzle, 15-puzzle) är ett synnerligen standardpyssel som ofta används för att testa algoritmer och liknande inom AI eller för att träna hjärnan. Det går ut på att flytta en blank bricka runt i en matris så att siffrorna återställs till en given ordning (oftast 1..15 eller 1..8) och den blanka ska vara i den nedersta högra rutan .

Min lösning på detta problem finns i n_puzzle.mzn och får väl anses vara ett pseudo-härke eftersom det använder en del trixerier såsom dummy-drag (kring rad 111).

Här är exempel på 8-puzzle, dvs en matris med 3x3. Talet 9 representerar den blanka rutan som flyttas runt.

Definiera först utgångspositionen:

puzzle =
[|2,3,6,
|1,4,9,
|7,5,8|];

Resultatet är (med num_sols = 8, dvs antal olika drag):


puzzle:
2 3 6
1 4 9
7 5 8
...
0: 2 3 6 1 4 9 7 5 8
0: 2 3 9 1 4 6 7 5 8
0: 2 9 3 1 4 6 7 5 8
0: 9 2 3 1 4 6 7 5 8
0: 1 2 3 9 4 6 7 5 8
0: 1 2 3 4 9 6 7 5 8
0: 1 2 3 4 5 6 7 9 8
1: 1 2 3 4 5 6 7 8 9
moves:
0 6
6 3
3 2
2 1
1 4
4 5
5 8
8 9

Lösningen finns i andra kolumnen i moves, dvs

6 3 2 1 4 5 8 9

Där 6 betyder att blank (9) och brickan som finns i position 6 ska byta plats, 3 att 9 och brickan i position 3 ska byta plats etc.

Raderna med matrisen visar hur draget påverkar matrisen (som en vektor). Talet framför raden (0 eller 1) visar om lösningen är gjort (1) eller inte (0).


M12


M12 är ett pyssel inspirerat av spel såsom ovanstående 15-pyssel och Rubiks kub (och dess släktingar). Skaparna av M12, gor Kriz and Paul Siegel, beskrev det Scientific American-artikeln Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups" för någon vecka sedan:

What we wanted for educational purposes was an entertaining way to develop people’s intuitions for groups entirely unlike the ones represented by the cube. And what we wanted as puzzle fans was a new set of puzzles whose solutions require a substantially different strategy from that of Rubik’s Cube and its relatives. So we made the natural connection: we were able to develop three new puzzles based on groups known as sporadic simple groups, whose properties are both remarkable and not well known except to specialists. Happily, the experiences of our colleagues show that anyone who can learn to solve Rubik’s Cube can gain an equally substantial understanding of these sporadic simple groups by doing our puzzles. But more, these puzzles are challenging in the sense that they do not yield to the methods that work with Rubik’s Cube—and we think they are a lot of fun. Readers who want to get their hands on them right away can download them.

Kortfattad beskrivning av M12
Talen 1 till och med 12 används, och de blandas slumpmässigt (fast inte hur som helst). Själva pysslet går ut på att man ska få tillbaka ursprungspositionen 1..12 med hjälp av endast två operationer:
- invert: placera talen i omvänd ordning, dvs 1..12 blir 12..1.
- merge: detta är en variant av "perfekt blandning". Den beskrivs som is a "card shuffle" best understood by trying it out, och kan väl enklast förklaras med följande: Om konfigurationen är

a) 1 12 2 11 3 10 4 9 5 8 6 7

och man gör en merge blir resultatet


b) 1 2 3 4 5 6 7 8 9 10 11 12

dvs man får då lösningspositionen.

Lösning i MiniZinc
I M12.mzn finns en modell för att lösa M12, dvs det enklaste av de tre problemen. För mer avancerade problemkonfigurationer, säg antal operationer > 24, tar det rätt lång tid.

Exempel:
Här är ett enkelt problem:

init = [7,1,8,9,12,5,3,10,4,11,6,2]

Lösning:

init: [7, 1, 8, 9, 12, 5, 3, 10, 4, 11, 6, 2]
check: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
check_ix: 10
operations: [0, 1, 1, 1, 2, 1, 1, 1, 1, 2, 0, 0]
0: 7 1 8 9 12 5 3 10 4 11 6 2
1: 7 8 12 3 4 6 2 11 10 5 9 1
1: 7 12 4 2 10 9 1 5 11 6 3 8
1: 7 4 10 1 11 3 8 6 5 9 2 12
2: 12 2 9 5 6 8 3 11 1 10 4 7
1: 12 9 6 3 1 4 7 10 11 8 5 2
1: 12 6 1 7 11 5 2 8 10 4 3 9
1: 12 1 11 2 10 3 9 4 8 5 7 6
1: 12 11 10 9 8 7 6 5 4 3 2 1
2: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12

Operationerna som används är kodade enligt:
0: gör inget (samma som föregående rad) . Not: Första raden är en dummy operation.
1: merge (M)
2: inverse (I)

Lösningen här är alltså: MMMIMMMMI .
Tyvärr klarar MiniZinc inte av att presentera strängar därav de numeriska värdena.

Tips: Antalet rader i lösningen (rows) påverkar väldigt mycket hur lång tid det tar. Börja därför med ett lägre värde (t.ex. 12) och öka detta försiktigt.

Not: Modellen är till strukturen rätt lik modellen för n-pysslet (se ovan) och det är ingen slump. (Jag skrev dock M12.mzn före n_puzzle.mzn)


Mer info om M12
* För att spela M12 (och dess storebröder) online kan man gå hit.
* Spelen finns även att tillgå som Windows-program från en av författarnas hemsida Igor Kriz. Se README för mer info.
* God Plays Dice skrev lite om detta i Rubik's deck of cards?.
* Wikipedia om den gruppteoretiska bakgrunden: Sporadic group.


SET puzzle


Tommy på Användbart skrev om dessa problem för några dagar sedan. Problemet påminner om vissa typer av IQ-test där man ska lista ut vilka saker som hör ihop med andra, och tycker man sådana problem är intressanta är SET värt att bita i.

När Tommy berättade om detta på senaste bloggträffen var en av mina första reaktioner att börja med att skapa en modell för problemet. Vilket sålunda har gjorts.

Läs mer om SET, med regler, tips etc:
* Wikipedia Set_(game), som väldigt korfattat beskriver problemet så här


Different "categories":
* They all have the same number , or they have three different numbers.
* They all have the same symbol , or they have three different symbols.
* They all have the same shading, or they have three different shadings.
* They all have the same color , or they have three different colors.

* New York Times har ett pyssel varje dag, och här förklaras lite mer.
* Ett lärt paper om SET: Benjamin Lent Davis and Diane Maclagan, The Card Game Set (PDF).


Huvuddelen av MiniZinc-modellen visas här med kommentarer. Den fullständiga modellen finns i set_puzzle.mzn.

include "globals.mzn";

int: n = 9; % number of items
% int: n = 12; % number of items
int: num_sets = 4; % number of Sets to find
% int: num_sets = 5; % number of Sets to find
int: m = 3; % number of items in a Set
int: num_flavours = 3; % number of flavours of the attributes
int: num_attributes = 4; % number of different attributes in each item
array[1..n, 1..num_attributes] of var 1..num_flavours: puzzle;

% decision variable: the sets to find
array[1..num_sets] of var set of 1..n: x;

% solve satisfy;
solve :: set_search(x, "input_order", "indomain_min", "complete") satisfy;

constraint

% exact three items in each set
forall(i in 1..num_sets) (
card(x[i]) = m
)
/\ % must be different sets
all_different(x)
/\
forall(i in 1..num_sets) (

% identify the items in this set
forall(a in 1..num_attributes) (
let {
array[1..m] of var 1..n: arr
}
in
% assign the set
forall(j in 1..m) (
arr[j] in x[i]
)
/\ % symmetry breaking: all different and sorted
forall(j in 1..m-1) (
arr[j] < arr[j+1]
)
/\
(
% EITHER all are same with regard to this attribute
forall(j in 1..m-1) (
puzzle[arr[j],a] = puzzle[arr[j+1],a]
)
\/
% OR all are different with regard to this attribute
forall(i, j in 1..m where i != j) (
puzzle[arr[i],a] != puzzle[arr[j],a]
)
)
) % end forall 1..num_attributes

) % end forall 1..num_sets

% /\ % Symmetry breaking: order the sets
% % Only works for flatzinc version >= 0.8
% increasing(x)
;

output [
show(x)
]

Idealet vore naturligtvis att man kunde förevisa bilden för programmet och sedan löstes problemet, men så långt har jag inte kommit. Istället används en enkel kodning från bilden med de ingående rutornas attribut till en matris av tal. Den kodning som används är följande, dvs det tal som visas inom parentes.


Symbols: Each card has ovals (1), squiggles (2), or diamonds (3) on it;
Color : The symbols are red (1), green (2), or purple (3);
Number : Each card has one (1), two (2), or three (3) symbols on it;
Shading: The symbols are solid (1), striped (2), or open (3).

Det problem som Tommy visar hos sig kodas så här:


puzzle =
array2d(1..n, 1..num_attributes,
[2,1,2,1,
3,3,2,1,
1,2,2,2,
1,2,2,1,
3,2,2,1,
3,1,2,1,
3,2,2,2,
2,3,2,2,
1,2,2,3,
]);

Det finns en unik lösning till detta problem (modulo symmetrier), nämligen dessa fyra mängder

{1, 2, 4}
{2, 5 6}
{3, 4, 9}
{6, 8, 9}

Posted by hakank at 09:07 FM Posted to Constraint Programming | Pyssel

juni 05, 2008

Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips

Mats Andersson har tidigare haft flera roliga tävlingar. Inför fotbolls-VM 2006 var det en tävling där man skulle gissa resultat i matcherna.

Eftersom mitt kunnande om fotboll var synnerligen begränsat valde jag en enkel metod genom att skapa ett beslutsträd för hur resultaten skulle bli. Och kom naturligtvis sist.

Inför fotbolls-EM (som alltså startar på lördag) har Mats en ny tävling, och den vill man ju inte missa.

Constraint programming-modell i MiniZinc

Eftersom kunnandet kring fotboll fortfarande är (ännu mer synnerligen) begränsat kan det inte vara frågan om att göra några bedömningar kring hur matchresultaten kommer att bli.

Denna gång tänkte jag istället parasitera på Mats fantastiska fotbollskunnande och utnyttja det tips han själv gjort. För detta har skapats en modell i constraint programming-systemet MiniZinc. Modellen finns här och visas även nedan.

Modellen bygger på Mats tips med följande villkor.

Möjligen är några av villkoren lite väl begränsande men har fördelen att det inte blir så många lösningar (om man t.ex. skulle göra någon form av okulärbedömning av dem, vilket inte gjorts här, så det spelar egentligen inte någon roll hur många lösningar som genereras)

1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips.
Kommentar: Om Mats anser att ett lag vinner så gör jag det också. Mats borde veta sådant.

2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
som för Mats tips.
Kommentar: Detta är för att få ner antalet möjliga lösningar.

3) Inga resultat får vara exakt samma som Mats.
Kommentar: Egentligen borde man tillåta att några resultat är samma som Mats, men det blir roligare så här.

4) Det får vara maximalt 5 mål per match.
Kommentar: Kanske det skulle vara maximalt 6 mål, eller 7?


Det finns 29 olika lösningar till detta problem. Redan innan jag tittade på resultaten beslöt jag mig för att ta den sista lösningen som solvern Gecode fz (version 1.2.1) genererade.

Mitt tips

Här är alltså mitt tips till fotbolls-EM 2008.

1. Schweiz - Tjeckien 2-2
2. Portugal - Turkiet 1-0
3. Österrike - Kroatien 0-1
4. Tyskland - Polen 1-2
5. Rumänien - Frankrike 1-3
6. Holland - Italien 1-2
7. Spanien - Ryssland 1-0
8. Grekland - Sverige 1-1
9. Tjeckien - Portugal 1-3
10. Schweiz - Turkiet 1-1
11. Kroatien - Tyskland 0-0
12. Österrike - Polen 1-3
13. Italien - Rumänien 2-0
14. Holland - Frankrike 0-1
15. Schweiz - Portugal 0-1
16. Turkiet - Tjeckien 1-1
17. Sverige - Spanien 1-3
18. Grekland - Ryssland 1-3
19. Österrike - Tyskland 0-3
20. Polen - Kroatien 0-1
21. Holland - Rumänien 1-0
22. Frankrike - Italien 1-3
23. Grekland - Spanien 1-4
24. Ryssland - Sverige 0-1


MiniZinc-modellen


Här nedan visas MiniZinc-modellen för problemet. (webb-versionen kan ha några små skillnader.)


%
% MiniZinc-modell för Mats Anderssons tävling om resultatet i fotbolls-EM 2008.
%
% För beskrivning av tävlingen se:
% http://www.mats-andersson.se/blogg/show.asp?svarsID=1956
%
%
% Min variant bygger på Mats tips med följande villkor:
%
% 1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips
% (om Mats anser att ett lag vinner så gör jag det också. Mats borde veta
% sådant).
% 2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
% som för Mats tips
% 3) Inga resultat får vara exakt samma som Mats.
% 4) Det får vara maximalt 5 mål per match.
%
% Med dessa begränsningar finns det 29 olika lösningar.
% Det beslöts innan lösningarna studerats att ta den sista lösningen
% som solvern Gecode fz (version 1.2.1) genererade.
%

%
% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

int: n = 24; % antal fotbollsmatcher
array[1..n, 1..2] of 0..4: m; % Mats tips
array[1..n, 1..2] of var 0..4: h; % mitt tips

int: m_sum = sum(i in 1..n) (m[i,1] + m[i,2]); % totalt antal mål i Mats tips
var int: h_sum; % total antalet mål i mitt tips

solve satisfy;

constraint
forall(i in 1..n) (
% förhållandet i mål mellan lagen ska vara samma som Mats tips
m[i,1] - m[i,2] = h[i,1] - h[i,2]

/\ % max 5 mål per match
h[i,1] + h[i,2] <= 5
)
/\ % inga matcher får ha exakt samma resultat som Mats
sum(i in 1..n) (
bool2int(
m[i,1] = h[i,1] /\ m[i,2] = h[i,2]
)
) = 0

/\ % totalt antal mål i mitt tips
h_sum = sum(i in 1..n) (
h[i,1] + h[i,2]
)
/\ % totalt antal mål ska vara samma i Mats och mitt tips
h_sum = m_sum
;

output
[
if j = 1 then "\n" ++ show(i) ++ ": " else " " endif ++
show(h[i,j])
| i in 1..n, j in 1..2
];


%
% Mats tips
%
m = [
1,1, % 1. Schweiz - Tjeckien 1-1
2,1, % 2. Portugal - Turkiet 2-1
1,2, % 3. Österrike - Kroatien 1-2
0,1, % 4. Tyskland - Polen 0-1
0,2, % 5. Rumänien - Frankrike 0-2
0,1, % 6. Holland - Italien 0-1
2,1, % 7. Spanien - Ryssland 2-1
0,0, % 8. Grekland - Sverige 0-0
0,2, % 9. Tjeckien - Portugal 0-2
0,0, % 10. Schweiz - Turkiet 0-0
2,2, % 11. Kroatien - Tyskland 2-2
0,2, % 12. Österrike - Polen 0-2
3,1, % 13. Italien - Rumänien 3-1
1,2, % 14. Holland - Frankrike 1-2
1,2, % 15. Schweiz - Portugal 1-2
0,0, % 16. Turkiet - Tjeckien 0-0
0,2, % 17. Sverige - Spanien 0-2
0,2, % 18. Grekland - Ryssland 0-2
1,4, % 19. Österrike - Tyskland 1-4
2,3, % 20. Polen - Kroatien 2-3
2,1, % 21. Holland - Rumänien 2-1
0,2, % 22. Frankrike - Italien 0-2
0,3, % 23. Grekland - Spanien 0-3
1,2 % 24. Ryssland - Sverige 1-2
];

%
% End of MiniZinc model.
%


Notera att MiniZinc inte hanterar strängar speciellt bra så resultatet presenteras endast så här:


1: 2 2
2: 1 0
3: 0 1
4: 1 2
5: 1 3
6: 1 2
7: 1 0
8: 1 1
9: 1 3
10: 1 1
11: 0 0
12: 1 3
13: 2 0
14: 0 1
15: 0 1
16: 1 1
17: 1 3
18: 1 3
19: 0 3
20: 0 1
21: 1 0
22: 1 3
23: 1 4
24: 0 1


Slutord


Från början tänkte jag använda någon form av statistisk metod som analyserade Mats tips för att skapa mitt eget tips. Ovanstående angreppssätt ligger definitivt mer i linje med det jag håller på med nu.

Naturligtvis ska man se allt detta som en liten etyd i constraint programming.

Posted by hakank at 09:18 EM Posted to Constraint Programming | Pyssel

maj 26, 2008

Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem

Här är några MiniZinc-modeller som skapats sedan förra anteckningen om sådana modeller.

Samtliga modeller att tilnå finns via My MiniZinc page.

Digital Tomography samt några varianter
Det problem som skrevs om i Ett litet april-pyssel löste jag själv med en digital tomografi-teknik. Se modellen tomography.mzn.

En viss förklaring av digital tomografi finns på sidan Open problems in discrete tomography. Sidan innehåller några Java-applets som man själv kan leka med.

I ovanstående modell var det bara en färg ("svart") man arbetade med, men problem kan generaliseras till flera färger. En sådan generalisering görs i tomography_n_colors.mzn, och som exempel modelleras bl.a. "The two atom problem".

Solitaire Battleship (wikipedia) är en variant av "Sänka skepp" som har liknande förutsättningar som digital tomografi. MiniZinmodell: solitaire_battleships.mzn.


SONET problem
SONET-problemet är ett standardproblem inom constraint programming som jag inte hittat någon MiniZinc-modell av så därför rullade jag en egen: sonet_problem.mzn.

För mer om problemet se t.ex. Simplified SONET Problem (Postscript-fil).


A Coin Puzzle
Detta problem på en rätt stor "grid" beskrivs utförligt av Tony Hürlimann i A coin puzzle - SVOR-contest 2007 (PDF).

Min MiniZinc-implementation av problemet finns i coins_grid.mzn. Ett tips är att låta en linear programming-solver lösa problmet, dvs ECLiPSe:s eplex eller MiniZincs nya option "--solver mip". Då löses det blixsnabbt.

Några Operations Research-problem
I John Hooker:s föreläsning A framework for integrating optimization and constraint programming finns några OR-problem som imlementerats:

- freight_transfer.mzn

- product_configuration.mzn


Ett skoj fotbollspussel
I Yahoo!-gruppen lp_solve kom ett skoj problem. Tyvärr krävs inloggning till gruppen, så MiniZinc-modellen innehåller hela meddelandet.

Problemet (som är en knapsack-variant) går ut på att optimera köp av brittiska fotbollsspelare med vissa krav:
- budgeten är på 30 miljoner (pund)
- man måste köpa ett visst antal spelare (målvakt, försvarsspelare etc) för en given kostnad per spelare
- man ska maximera den totala kostnaden men inte komma över budgeten.

Problemet uttrycks i flyttal men jag har valt att arbeta med heltal av två skäl:
- för tillfället är det fler MiniZinc-solvers som klarar av helttal än flyttal

- när det gäller spelarkostnader är inte orimligt att anta hela pund.

MiniZinc-modellen finns i football.mzn och är ganska generell.


Några andra modeller
- Funktionspartitionering, dvs partionera ett gäng heltal med avseende på en funktion t.ex. modulo-funktionen: modulo_partition.mzn. Det är enkelt att ändra funktion i modellen.

- Beslutsträd. Här modelleras ett fullständigt binärt beslutsträd: decision_tree_binary.mzn.

- Markovkedjor: markov_chains.mzn: Här räknar man ut "stable state" av marknadsandelnarna för tre företagsmärken.

- Yet another recreational schackproblem: peacableArmyOfQueens.mzn.


Raymond Smullyans logiska pyssel
Så till det jag satt med i helgen.

I den underbara boken What is the name of this book? beskriver Raymond Smullyan ett stort antal logiska pyssel, de allra flesta är skapade av Smullyan själv.

Några av de mest kända pysslen från denna bok är "Knights and Knaves"-problemen från kapitel 3 (som heter just "Knights and Knaves"): Alla "knights" talar alltid sanning och alla "knaves" ljuger alltid. Senare i kapitlet kommer även "Normals" med, sådan ljuger ibland och talar sanning ibland, och så tillkommer speciella giftasregler mellan de olika typerna. Problemet är att försöka lista ut vem som är vad med ledtråd av några få ledtrådar.

De allra flesta problemen från kapitel 3 finns modellerade i respektive modell:
- smullyan_knight_knaves.mzn: bara knights och knaves
. Problem 26 till och med 35. (Problem 36, 37 och 38 har av olika skäl inte modellerats.)

- smullyan_knight_knaves_normals.mzn: här finns även normals
. Problem 39 till och med 42 (modellen för 43 är inte korrekt).

- smullyan_knight_knaves_normals_bahava.mzn, med speciella giftoregler mellan knights, knaves och normals. Problem 44, 45 och 46.

Wikipedia har mer info om Knights and Knaves.

Uppdatering något senare
Några fler problem från samma bok:

- De första problemen om Lion och Unicorn från kapitel 4 "Alice in the Forest of Forgetfulness": smullyan_lion_and_unicorn.mzn. Lejon och enhörningar ljuger vissa dagar och talar sanning andra dagar. Här gäller det att lista ut vilken dag de säger olika saker.

- De första problemen från kapitel 5 "The mystery of Portias Caskets" smullyan_portia.mzn.

Posted by hakank at 06:54 EM Posted to Constraint Programming | Pyssel

april 26, 2008

Ett litet april-pyssel

För tre år sedan (2005) publicerades ett Aprilpyssel. Det är dags att åter ta upp denna tradition.

Naturligtvis är nedanstående pyssel - på något sätt - kopplat till det jag kollar in just nu, dvs constraint programming/integer programming/MiniZinc.


Denna typ av pyssel har ett specifikt namn - som jag inte avslöjar just nu - och tillhör en grupp mer generella problem (som vad jag vet inte har något speciellt namn, dock med åtminstone ett undantag).


Problem


Inledning

Betänk följande binära matris (dvs endast 0 och 1 förekommer) där summorna för respektive rader och kolumner visas i fetstil.


1 010
1 010
0 000
  020

Vi sammanfattar respektive summor i två vektorer:

- radsummor: [1,1,0]

- kolumnsummor: [0,2,0].


Dagens pyssel går nu ut på, att givet en radsummavektor och en kolumnsummavektor, lista ut vilken matris som ligger som grund för dessa summor.


Delproblem

Det är två stycken delproblem som vardera på något vis kan ge ledtråd till lösningen av det andra delproblemet.

Delproblem a

radsummor= [0,2,2,2,2,2,8,8,4,4,4,4,4,0]
kolumnsummor = [0,0,0,12,12,2,2,2,2,7,7,0,0,0]

Delproblem b

radsummor = [0,0,8,2,6,4,5,3,7,0,0]
kolumnsummor = [0,0,7,1,6,3,4,5,2,7,0,0]


Ett av dessa problem har jag snott ("kopierat" är en mer korrekt term för detta förfarande) från någonstans, det andra har jag hittat på själv. Ordningen mellan delproblemen, liksom presentationen av dess härlednad i föregående mening, är faktiskt slumpad med ett slumptalsprogram, nämligen R.


Vinnerier etc

Vinnaren i detta pyssel anses den vara som först till pysselledningen:

- p) ger korrekt svar på båda delproblem

- q) samt redogör för hur problemet löstes.

"Till pysselledningen" definieras här som antingen en kommentar i denna blogganteckning, eller ett mail till hakank@bonetmail.com.

Vinnaren erhåller i kommentarerna till denna blogganteckning eller i en separat blogganteckning ett "Bra gjort, X!", där X ersätts av vinnarens namn/handle/smeknamn etc. Möjligen kommer "Bra gjort" att ersättas av synonymiserade uttryck och/eller kompletteras med kraftfullare attribut (såsom "Mycket") då i kombination med erforderliga ändringar av resten av uttrycket för att det ska bli så korrekt svenska som möjligt (byte av stor till liten bokstav etc).

Pysselledningen förbehåller sig att dela ut noll (0) eller flera stilprogram till förslag som ej är korrekt lösta, inkompletta men på något sätt (subjektivt bedömt) förtjänar ett stilpoäng, men även till korrekta lösningar som förtjänar sådan stilpoäng. Negativa stilpoäng kommer inte att delas inte, åtminstone inte officiellt. Eventuella felaktigheter som eventuellt påpekas för eventualla lösningsförslag definieras inte som negativa stilpoäng i detta sammanhang.

Till allt detta kommer vinnaren även att erhålla en av följande vid nästa eller någon (dock endast en) efterföljande IRL-träff (den virtuella glassen är än så länge alldeles för blaskig för att bjuda på):

- glass
- öl
- kaffe
- te
- eller annan motsvarande dryck

Not: Glass/öl/etc kan delas ut av den person som råkar utgöra pysselledningen i helt andra sammanhang och av helt andra skäl. Detta ska då ses som något som är hetl frikopplat från denna pysseltävling.


Lösningens presenterande etc


Det är planerat att presentera den av pysselledningen ansedda korrekta lösningen (inklusive några kommentarer samt åtminstone en vidarelänk) efter en viss tid har s.a.s. runnit, inklusive en MiniZinc-modell. Exakt när detta sker beror på.

Slutord

En av de saker som intresserar mig är hur man går till väga för att lösa slika problem. Därför är punkt q) viktig i lösningen. Det behöver inte vara (men kan vara) speciellt långt svar, men ange gärna metod, systemstöd samt - vilket är lika intressant - eventuella felskär.

Slutligen: Förutom "Lycka till!" kan noteras (vilket säkert redan gjorts av den observante läsaren) att ovanstående pysselformulering kunde - om omständigheterna vore annorlunda - göras mycket kortare. Men det är de inte så det gjordes inte.

Posted by hakank at 10:25 FM Posted to Constraint Programming | Pyssel | Comments (8)

oktober 11, 2006

Oktober-rebusen

Liksom förra "rebusen" så var Jimmy Höögs Internetlänkars 2:a rebus också kul.

Själv fastnade jag rejält på 13 -> 14, men efter lite funderande (och kort därefter en mental smack i huvudet att det var faktiskt inte var så svårt men helt annorlunda än de relativt avancerade teorierna som först testades) så fixades även den. Det var den jag satt med längst, såväl i funderingstid som kalendertid.

För en annan uppgift var jag lat och skrev Perl-program, men fick äta upp det sedan. Det finns säkert en bra moral härvidlag.

För den som inte testat dessa "rebusar" (jag skulle hellre kalla det för länkgåtor, URL-gåtor eller något sådant men är definitivt inte kittslig) gäller det att skriva in en URL (typ någonting.htm) genom att via texten (och eventuellt ledtråden) som finns på sidan lista ut regeln för denna sida och sedan applicera regeln för nästa tal i ordningen (dvs efter 1 kommer 2 etc).

Notifierad när nästa månadsgåta går igång kan man bli genom att registrera på Nyhetsbrevet.


(Jag har faktiskt inte gett mig på detta problem, vilket naturligtvis är en stor brist i min karaktär. Det verkar inte helt lätt...)


Andra bloggar om: , .

Posted by hakank at 07:02 EM Posted to Pyssel

juli 10, 2006

Kul brädspel: Entropy Game (Hyle 7)

Entropy Game (kallas även Hyle 7) är ett kul datorbaserat brädspel skapat av Eric Solomon.

Man väljer antingen Chaos eller Order och programmet spelar den andra rollen. Chaos börjar med att lägga ut en färgad bricka någonstans varpå Order ska försöka skapa ett mönster. Den ende som får poäng är Order enligt hur mycket ordning det är raderna och kolumnerna. Den exakta poängberäkningen finns inte i appleten (men visas i marginalerna), se istället spelets sida på Mind Sport Olympiad.


Se även
Erik Solomons publikationer.
Bok av Solomon: Game Programming (1984, Bokus, ISBN=052127110X).
Andra Java-spel av Solomon.

(Via think again!)

Andra bloggar om: ,

Posted by hakank at 09:21 FM Posted to Pyssel

juni 09, 2006

Utanvitsar (utangåtor, utanrebusar): ett program

Håkan Karlsson har beskrivit ett skoj ordpyssel i Utanvitsen, där det gäller att komma på vilket ordpar som avses utifrån en bokstav samt en liten beskrivning.

Några exempel:

k: barnlösa monarker ( = kungar utan ungar)
r: outvecklad kommunism (= revolution utan evolution)
r: torkade fikon (frukt utan fukt)

I kommentarerna ger Bloggblad följande paradigmatiska exempel (som Lotten Berglund löste elegant)

m = magerlagd engelsman (mister utan ister)

Läs mer underbara exempel hos hakke.

Mer schematiskt:

[bokstav]: "ord_X med [bokstav]" utan "ord_X utan [bokstav]"

Det kan även finnas mer strikta regler, t.ex. att [bokstav] måste finnas i början eller i slutet av ord_X (denna regel används i programmet som beskrivs nedani.


Programmet Utanvitsar
Efter och enligt önskemål från hakke har jag skrivit ett litet program för att underlätta konstruktionerna av själva utanvits-paren (som jag något fånigt kallar "utanvitskompisar"): Utanvitsar.

Ordlistan som används är på cirka 90 000 svenska ord.


Exempel på en körning
Ordet mister ger följande två kompisar:

* mister - ister
* mister - miste

Och ordet yra ger denna ansamling:

* fyra - yra
* hyra - yra
* lyra - yra
* myra - yra
* pyra - yra
* syra - yra
* yra - yr

För att underlätta konstruktionerna ännu mer har det skapats en fil med mer än 10 000 svenska sådana par (utifrån samma ordlista på cirka 90 000 ord som används i programmet): utanvitspar_swe.txt. Filen innehåller även ordböjningar som näppeligen är speciellt skojiga (t.ex. "frostskadad - frostskada").

Med ett enkelt handgrepp kan man även få engelska utanvitskompisar (without pal pairs?).


Noter
Not 1
Programmet söker endast efter utanvits-kompisar som kan skapas genom att första eller sista bokstaven tas bort/läggs till. Detta innebär att kombinationen "frukt - fukt" inte kommer med. Denna begränsning är helt enligt hakkes önskemål.

Not 2
Det är inte alls säkert att det finns en sådana kompisar för det givna ordet.

Not 3
Den där beskrivningen som följer efter den ensamma bokstaven - som helst ska vara poängfull och förvirrande och om möjligt med en samhällstillvänd udd - får man själv komma på.

Posted by hakank at 09:39 EM Posted to Program | Pyssel | Språk | Comments (1)

april 27, 2006

Smith code: Kod i Dan Browns Da Vinci-kod dom

I Expressen-artikeln Dan Brown-domaren smög in en kod i domen står att läsa:


Det är något mystiskt med domen som friade författaren Dan Brown från plagiat.
Det finns en kod i den.
Domare Peter Smiths kod.

...

Plötsligt dyker det upp en kursiverad bokstav mitt i ett ord. Där kan exempelvis plötsligt stå "claimant".
Lägg ihop de kursiverade bokstäverna i de första sju paragraferna och man får: Smithy code -Smithykoden.


Om man nu tar samtliga kursiverade bokstäver (de som kursiverades via programmet pdftohtml) får man följande sträng


smithycodeJaeiextostgpsacgreamqwfkadpmqzv

Den första delen - "smithycode" - nämndes i Expressen-artikeln, och hela strängen finns även i andra källor (se nedan).


Några tankar (ej lösning!)
Här är några tankar, där den principiella förutsättningen är att det en relativt enkel form av kodning och inte någon superkryptometod.

En tanke är att det finns tre separata delar (bokstäverna helt enkelt verkar tillhöra olika delar) som är kodade med olika typer av tekniker:
1. smithycode
2. Jaeiextostgpsacgream
3. qwfkadpmqzv

2 känns som det skulle kunna vara något anagram (på latin?). Problemet med anagram är att de tenderar att ha väldigt många lösningar så det är troligen inte rätt väg. Internet Anagram Server hittar dock inget anagram på latin. På engelska finns det däremot många (obs. stor sida!).


3 kanske är någon form av rotationskryptering. Här är 0 till 25-rotationerna och dess reverser för strängen "qwfkadpmqzv":

rot(0): qwfkadpmqzv reverse: vzqmpdakfwq
rot(1): rxglbeqnraw reverse: warnqeblgxr
rot(2): syhmcfrosbx reverse: xbsorfcmhys
rot(3): tzindgsptcy reverse: yctpsgdnizt
rot(4): uajoehtqudz reverse: zduqtheojau
rot(5): vbkpfiurvea reverse: aevruifpkbv
rot(6): wclqgjvswfb reverse: bfwsvjgqlcw
rot(7): xdmrhkwtxgc reverse: cgxtwkhrmdx
rot(8): yensilxuyhd reverse: dhyuxlisney
rot(9): zfotjmyvzie reverse: eizvymjtofz
rot(10): agpuknzwajf reverse: fjawznkupga
rot(11): bhqvloaxbkg reverse: gkbxaolvqhb
rot(12): cirwmpbyclh reverse: hlcybpmwric
rot(13): djsxnqczdmi reverse: imdzcqnxsjd
rot(14): ektyordaenj reverse: jneadroytke
rot(15): fluzpsebfok reverse: kofbespzulf
rot(16): gmvaqtfcgpl reverse: lpgcftqavmg
rot(17): hnwbrugdhqm reverse: mqhdgurbwnh
rot(18): ioxcsvheirn reverse: nriehvscxoi
rot(19): jpydtwifjso reverse: osjfiwtdypj
rot(20): kqzeuxjgktp reverse: ptkgjxuezqk
rot(21): lrafvykhluq reverse: qulhkyvfarl
rot(22): msbgwzlimvr reverse: rvmilzwgbsm
rot(23): ntchxamjnws reverse: swnjmaxhctn
rot(24): oudiybnkoxt reverse: txoknbyiduo
rot(25): pvejzcolpyu reverse: uyploczjevp

där det enda jag hittar är "warn" för reverse(rot(1)). Inget att hänga i julgranen, alltså.

Hmm, det där "y":et i "smithycode" kanske är en ledtråd...


(Tack Jonas för Expressen-länken.)


Se även
Dokumenten att leka med: Sammanfattningen. och själva domen (PDF).

Reuters: Latest Da Vinci mystery: judge's own secret code

Slashdot (naturligtvis) Judge Creates Own Da Vinci Code.

Posted by hakank at 07:15 EM Posted to Pyssel | Comments (2)

april 18, 2006

Choco: Constraint Programming i Java

Bakgrund
Mitt intresse för Constraint Programming (CP) (som tidigare kallades Constraint Logic Programming, CLP) väcktes för ett antal år sedan strax efter en företagskamp (som kort beskrevs i Uppdaterat program: AnaCheck), där ett av uppdragen var följande matematiska pyssel:

Vilken är den minsta differensen man kan få mellan två tal om man måste använda samtliga siffror (0..9) exakt en gång?

Lösningen presenteras nedan.

Ungefär samtidigt stötte jag på Constraint (Logic) Programming och med detta och liknande pyssel i bakhuvudet, och blev väldigt fascinerad av programmeringsparadigmet. Kanske inte så förvånande eftersom många standardexempel är just matematiska pyssel.

Tanken är att man endast behöver skriva de problemspecifika villkoren (constraints), sedan får systemet lista ut bästa sättet att lösa problemet. Det finns många olika metoder och heuristiker för att lösa problemen, och ibland måste hjälpa till så att lösningen kommer denna sidan regnbågen eftersom vissa problem är mycket tunga.

Ett citat som ofta nämns i sammanhanget är Eugene C. Freuder (CONSTRAINTS, April 1997)


Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it..


Prologbaserade system
I början arbetade jag mestadels med logikprogramspråket Prolog som "moderspråk", Sicstus Prolog samt ECLiPSe Constraint Programming System (det senare inte att förväxlas med utvecklingsmiljön med ungefär samma stavning).


Imperativa språk
Som komplement till de Prologbaserade systemen har jag letat efter mer imperativa - samt icke-kommersiella - moderspråk såsom Java, C, C++, Perl, Python, eftersom vissa saker är lättare att programmera med sådana språk (men ibland svårare) En av dessa implementationer Python-constraint och nämns i kommentarerna till Sesemans matematiska klosterproblem samt lite Constraint Logic Programming.


Choco
Så till det system jag har kollat i nyligen: det Java-baserade Choco. I slutet av anteckningen finns fler referenser.

Choco är snabbt och det har en stor mängd funktioner. Exemplen nedan är endast för "finita domäner" (löses med hjälp av heltal), men det finns även domäner med reella tal samt mängder.

Det är dock inte lika elegant att skriva constraints som i Sicstus/ECLiPSe, vilket vi nu kommer att titta på.


Minsta differensproblemet - en jämförelse av kodskrivning
För att tydliggöra skillnader och likheter mellan Choco och de Prologbaserade systemen visas hur minsta differensproblemet kan lösas i respektive system.

I ECLiPSe skriver man själva constraint-delen av problemet på följande sätt; i Sicstus Prolog skriver man snarlikt. Obs: koden är inte riktigt komplett att bara köra.

:-lib(fd), lib(fd_search), lib(fd_global),lib(fd_domain).

% ....

LD = [A,B,C,D,E,F,G,H,I,J], % deklarera de 10 variablerna
LD :: [0..9], % intervallet för variblerna, mellan 0 och 9
fd_global:alldifferent(LD), % alla värden ska vara olika

%
% constraints
%

% A + B + C + D + E = F + G + H + I + J
X #= 10000*A+1000*B+100*C+10*D+E,
Y #= 10000*F+1000*G+100*H+10*I+J,

% differensen ska bli positiv
X #< Y,

% differensen
Diff #= Y - X,

% minimera differensen (Diff) samt heuristik för att hitta lösningen snabbt
minimize(search(LD,0,anti_first_fail,indomain_max,credit(64,bbs(15)),[]),Diff).

Elegant och lite magiskt, eller hur?

Motsvarande Choco-program är lite längre, främst eftersom det saknas syntaktiskt socker. Det går att pressa antalet rader (sådant har gjorts) men här görs en mer expressiv form för att jämförelsen ska bli tydligare. Programmet finns att ladda ner här nedan.


// Choco program

import choco.Problem;
import choco.*;
import choco.integer.*;

public class LeastDiff {

public static void main(String[] args) {
new LeastDiff().puzzle();
}

public void puzzle () {
Problem pb = new Problem();

// definiera variablerna A .. J så att dess värden är mellan 0 och 9
IntDomainVar A = pb.makeEnumIntVar("A", 0, 9);
IntDomainVar B = pb.makeEnumIntVar("B", 0, 9);
IntDomainVar C = pb.makeEnumIntVar("C", 0, 9);
IntDomainVar D = pb.makeEnumIntVar("D", 0, 9);
IntDomainVar E = pb.makeEnumIntVar("E", 0, 9);
IntDomainVar F = pb.makeEnumIntVar("F", 0, 9);
IntDomainVar G = pb.makeEnumIntVar("G", 0, 9);
IntDomainVar H = pb.makeEnumIntVar("H", 0, 9);
IntDomainVar I = pb.makeEnumIntVar("I", 0, 9);
IntDomainVar J = pb.makeEnumIntVar("J", 0, 9);

IntDomainVar[] letters = {A,B,C,D,E,F,G,H,I,J};

IntDomainVar Diff = pb.makeBoundIntVar("Diff", 0, 10000);

// Temporära variabler
IntDomainVar X = pb.makeBoundIntVar("X", 0, 100000);
IntDomainVar Y = pb.makeBoundIntVar("Y", 0, 100000);

// alla värden ska vara unika
for (int i = 1; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
if (i==j) {
continue;
}
pb.post(pb.neq(letters[i], letters[j]));
}
}

// X = A+B+C+D+E
pb.post(pb.eq(X, pb.scalar(new int[]{10000, 1000, 100, 10, 1},
new IntDomainVar[]{A,B,C,D,E})));

// Y = F +G + H + I + J
pb.post(pb.eq(Y, pb.scalar(new int[]{10000, 1000, 100, 10, 1},
new IntDomainVar[]{F,G,H,I,J})));

// Diff = X - Y
pb.post(pb.eq(pb.minus(X, Y), Diff));

// minimera skillnaden
pb.minimize(Diff,false);

// nu ska vi lösa problemet
Solver s = pb.getSolver();
pb.solve(true);

// Skriv ut lösningen
System.out.println("Result: "+ A.getVal() + B.getVal() + C.getVal() +D.getVal() + E.getVal() + " - " + F.getVal() + G.getVal() + H.getVal() + I.getVal() + J.getVal() + " = " + Diff.getVal() );

} // end puzzle

} // end class


Lösningen som ges av dessa båda program är samma, nämligen

50123 - 49876 = 247


Några körbara (kompilerbara) Choco-program
Här är källkoden till några andra mindre Choco-program, varav några är standardproblem inom constraint programming. Choco-distributionen innehåller några andra.

LeastDiff2.java: Ovanstående exempel
FurnitureMoving.java: Planering av möbelflyttande, använder cumulative.
Knapsack.java: ett enkelt knapsack-problem (minimize)
Zebra.java: ett standardpyssel
Seseman.java: Choco-versionen av Sesemans matematiska klosterproblem


Se även
om Choco:
Choco: projektsidan på Sourceforge
Wiki
User guide
Choco API
Forum

om constraint programming
Roman Barták: On-line Guide to Constraint Programming
Roman Barták: Constraint Programming: In Pursuit of the Holy Grail (PDF)


tidigare skrivet om C(L)P
Sesemans matematiska klosterproblem samt lite Constraint Logic Programming
Automatisk "lösning" av Minesweeper i Mozart/Oz


JaCoP är ett annat Javabaserat system, utvecklat vid Lunds Universitet som man kan få tillgång till om man frågor någon av dess skapare. Har inte kollat in det så mycket ännu, men det verkar också trevligt.

Posted by hakank at 09:59 EM Posted to Constraint Programming | Matematik | Pyssel

november 21, 2005

Bloggforum 3 - Några tankar samt Isobels och Lisas pizzeriabordsproblem

Nedanstående är inte avsedd att vara någon fullständig redovisning av vad som hände eller gjordes under Bloggforum 3 eller helgen kringgärdande detta evenemang. Snarare är det tankar kring det man pratade om i och utanför det formella programmet. Vad gäller fysiska trajektorier och de yttre omständigheterna kan refereras till Mats Anderssons utmärkta och innehållsrika Summering av Bloggforum 3.

Ett stort tack till Rebecca Crusoe, Stefan Geens och Erik Stattin för deras fina arbete att anordna ett så intressant program, och som gjorde det möjligt att få förmånen träffa så väldigt trevliga och intressanta personer.

Det har skrivit väldigt mycket redan om forumet. De naturliga samlingspunkterna är
- Bloggforum 3
- del.icio.us/tag/bloggforum3

Bloggen är död
Temat (med glimten i ögat) för detta forum var "Bloggen är död". Det är egentligen absurt att nu när begreppet blogg håller på att bli känt för en större allmänhet anser man att bloggen är död.

Personligen har jag sedan ett tag känt att formatet känts begränsande i vissa fall. I såväl bloggverktyg som kommentarer finns en tendens att endast bry sig om det som skrevs nyligen. Det innebär att det man skrivits tidigare (t.ex. en vecka, en månad eller ett år sedan) inte läses längre i ett naturligt sammanhang. Denna dominans till det kronologiska har alltså stört mig rätt länge. I vissa fall är det naturligt eftersom det ofta är dagsaktuella frågor som diskuteras och man anser att debatt etc är över. Men det man missar är samlandet av kunskap kring det som man - eventuellt - kom fram till.

Det verkar även finnas andra som haft liknande tankar kring begränsningarna, men kanske av andra skäl, vilket inte är så konstigt. Nu har man hunnit experimenterat med mediet, funnit det som passar ens egna syften och identifierat det som är mindre intressant. Det verkar gälla såväl traditionell (text)bloggning, podcasting som videobloggning. Detta är tiden att fundera över mediers inneboende begränsningar.

Stefan Geens undrar lite Bloggforum 3 - what I saw vad Bloggforum 4bör innehålla. Det rykte som Jon skriver om i sin kommentar är något som bl.a. jag själv underblåst (eller vad det nu är man gör med rykten), eftersom jag inte tror att det finns behov för ett Blogg-forum om ett halvår, och diskuterade detta lite med både Erik Stattin och Stefan Geens i helgen.

Däremot ser jag mycket fram emot ett X-forum (alternativt X-logg-forum) där man visar hur det-vi-nu-nu-kallar-blogg ("the thing formerly known as blog") har utvecklats och förändrats, och hur det eventuellt påverkat t.ex. socialt eller tekniskt. Självklart kommer det fortfarande att finnas bloggar med eller utan t.ex. wiki-liknande utökningar, men jag tror och hoppas att vi kommer att se en större variantion i såväl form som innehåll.

Troligen har det om ett halvår även hänt saker inom lagstiftning, politik, media samt i det sociala landskapet (t.ex. olika typer av forskning kring bloggning) som är väl värt att föreläsa om eller ha sessioner kring.

Som Ben Hammersley beskriver i sin "Åtta idéer som verkligen kommer att revolutionera 2000-talet (och varför blogging inte är en av dem)" är bloggen i sig inte inte en någon revolutionerande idé, men inkorporerar många av de idéer som har eller kommer att revolutionerna informationsamhället eller åtminstone påverka det.


Web 2.0 och agenter
Under flera tillfällen diskuterades det Web 2.0, t.ex. med Simon Winter, Henrik Torstensson och Jon Åslund. Jag har inte stenkoll på vad det är och tycker det liknar det som man sa kring 98/99 om webben eller t.ex. när WAP kom. Men nu har det faktiskt blivit möjligt för en företagsam person att göra dessa applikationer med öppna API och "öppen data".

En sak som jag har saknat i diskussionerna är intelligeta agenter som kommunicerade med varandra för att lösa all världen (informations)problem. Vad blev de egentligen av? Jag vill ha min shoppingagent!


Jyri Engström: Sociala object
Jyri Engströms föredrag var det föredrag som jag var mest intresserad av och var även det som jag uppskattade mest. Engström poängterade att det viktiga med sociala mjukvaroprogram (och man borde kunna se bloggen som ett sådant) är gemensamma sociala objekt, där objekt kan vara väl definierat men även uppstå spontant efter ett tag.

Som exempel på hur viktigt det är med gemensamt socialt objekt visades en av mina favoriter bland Monty Python-sketcherna: Fotbollsmatchen mellan grekiska och tyska filosofer. Detta fick mig att parafrasera Wittgensteins berömda setens från Filosofiska undersökningar: "a serious and good philosophical or social work could be written that would consist entirely of jokes from Monty Python".

Inledningsvis nämnde Engström några böcker som jag har faktiskt läst och skrivit lite om, se mer Social Network Analysis och Complex Networks - En liten introduktion. Se även tidigare bloggningar: Social Network Analysis/Complex networks.

Engström rekommenderade även en nyutkommen bok (den där med bilderna på det italienska mötet respektive potatisodlingen) och som verkar intressant: John Thackara In The Bubble - Designing in a Complex World.

Det antyds att Lotta at Work kommer att publicera ljud/video från Engströms föredrag.


Ben Hammersleys vision
Ben Hammersley hade en något provocerande rubrik på sitt föredrag "Åtta idéer som verkligen kommer att revolutionera 2000-talet (och varför blogging inte är en av dem)" som fick sin förklaring, och gav faktiskt en koppling till bloggandet genom att bloggande (och bloggare) "inkorporerar" alla(?) dessa punkter.

Föredraget var intressant även om jag inte riktigt håller med honom i hans undergångsbeskrivning. Hans tes att detta är en unik tid som vi aldrig tidigare skådat känns också som en något omotiverad kontemporär-centrism, dvs att vår tid är viktigare eller mer märkvärdigt än tidigare tider. Vad är det för märkvärdigt med vår tid? Å andra sidan är uppgång och nedgång av civilisationer inte heller någon naturlag.


En kommentar kring en detalj som verkar vara viktigt för resonemanget. Hammersley menar att den tekniska utvecklingen numera bara fortsätter att öka genom att den tekniska utvecklingen förstärker sig själv, t.ex. genom att snabbare datorer gör det möjligt att skapa ännu snabbare datorer som i sin tur möjliggör skapande av snabbare datorer etc. Han stödde denna tes med en bild föreställande en exponentiell kurva som påstods visa att datorerna blir allt snabbare/billigare/kraftfullare datorerna utan någon gräns eller avtagande. Troligen kan man även tolka kurvan som en logistisk kurva, eftersom den i början ser den ut som en exponentiell kurva men planar sedan ut till en "mättnadsnivå". En alternativt tolkning att det var i stort sett samma kurva ("sinuskurva") som Hammersley tidigare visat att symboliserade tidigare civilisationer hade följt: först uppgång, sedan nedgång ("crawling in the mud"?) och sedan uppgång igen och sedan nedgång. Således är det inte nödvändigt att det är en exponentiell tillväxt.

Han varnade i och för sig för att beskrivningen skulle störa personer med vissa kunsaper inom historia och teknik (samt eventuellt matematik).

Hur som helst var det ett mycket energirikt och inspirerande föredrag. Det finns en ljudupptagning via Lotta at Work.


Mozz Hussain: MSN Spaces i praktiken
Mozz Hussain "Busting blogging myths - the present and future of blogging" handlade om erfarenheterna kring MSN Spaces. Det var i och för sig intressant och gav inblickar i den sociala strukturen kring bloggar, men detaljerna fastnade inte så mycket. Kanske beror detta på att MSN Spaces inte representerar så mycket den typ av bloggning som jag själv tycker är mest intressant att följa, det som bl.a. Jonas Söderström kallar för kunskapsbloggar.


Copyfight
Detta hade jag sett framemot, bl.a. eftersom Simon Winter var med i panelen. Simon är en av mina absoluta favoriter bland de svenska bloggarna och som jag haft förmånen att träffa flera gånger tidigare. Simon summerar några av sina tankar kring debatten i Vad är viktigt med upphovsrätt?.

Med en något elak förenkling kan man säga att man kom fram till att man egentligen inte vet vad som gäller. Det var dock intressant att följa debatten, speciellt de konkreta exemplen som framfördes såväl från panelen som publiken.

Debatten blir inte lättare med att begreppen "kopiering", "fildelning", "piratkopiering" nu är så inflammerade att det verkar som en vettig diskussion av det är omöjlig, och det känns som om antipiratbyrå-sidan för tillfället äger dessa begrepp. Ett förslag är att försöka hitta en mer neutral begreppsapparat som gör det möjligt att föra rationella diskussioner. Under kvällen föreslogs det att begreppet "kopiera filer" skulle bytas ut mot det neutrala "kgegg" (så tror jag att det stavas), ett ord som länge sökt sin användning.


Gamla vänner, nya vänner samt att bli överraskad
Waldemar på Teche skriver följande i Det bloggforum jag inte var på:

Jag är lite förvånad över bloggosfären fortfarande håller i sig som en enad miljö. Trots allt är det ju rätt skilda ämnen och åsikter som avhandlas numer, men att man ännu delar en gemensam plattform... det tyder på att det kanske kommer att hålla i sig.

Ett skäl till kan exemplifieras med just Bloggforum är just att där finns så många olika intressen men alla har en gemensam referensram: bloggar. De allra flesta är också sådana som brinner för något och sådana personer är nästan alltid intressant att träffa eller få kontakt med (undantag finns naturligtvis). Det är flera kluster som - speciellt i Bloggforum - blandas i det gemensamt intresse av att uttrycka sig . I pausar, lunchen eller på "cocktail-partyt" kan man mingla med personer som man normalt inte träffar. Precis som i riktiga vänskapslivet kan man bli "hit it off" med en väns vän eller dennes vän

Den sociala poängen med dessa tillställningar är flerfaldig: att träffa sina gamla vänner, att prata med dem man har läst men inte träffats tidigare, samt helt enkelt bli överraskad av ett möte med någon man inte ens kände till. Detta sistnämnda ska inte underskattas.

På ungefär samma sätt vill man att sociala nätverkssystem ska fungera. Nyhetsbevakningsystem och rekommendationssystem har liknande syften:
- man vill bli uppdaterad inom de områden man känner väl till
- man vill lära sig mer inom ett ämne
- man vill bli överraskad av nya kunskaper eller ämnen.


En social nätverksanalys-kommentar: I många Bloggforum 3.0-redogörelser länkas det till personerna som träffats. Det skulle vara intressant att jämföra dessa med t.ex. bloggrullen eller de man länkat till föregående samt eventuellt efterföljande. Avspeglar kontakterna på Bloggforum det normala sociala mönstret inom bloggosfären? Min egen intuition kring detta är att cocktail-parties har en annan social dynamik än de dagliga bloggkontakterna.


Några längre-än-kortare kontakter
Här är den nästan-obligatoriska lista över personer som träffades och som pratades med mer än några sekunder. De med (*) anger nya IRL-bekantskaper. Det skulle ta alldeles för lång tid att skriva ner vad vi pratade om så det blir i stort sett endast en uppräkning av namn. Tack till er för trevliga pratstunder.

- Mats Andersson, resekamrat, hotellrumssdelare, gåtlösare samt galapetter
- Steffanie Müller
- Simon Winter
- Stefan Geens
- Andreas Haugstrup (*)
- Henrik Torstensson
- Någonting Söderström(?), Henrik Torstenssons ej bloggande kompis (*).
- Eric Wahlforss (*)
- Erik Stattin
- Jenny Isaksson (*)
- Niki Bergman (*)
- Rebecca Crusoe
- Daniel Lundh (*)
- Håkan Hakke Karlsson, varvid våra respektive skulder tillvarandra nu är reglerade.
- Rosemari Södergren (*)
- Erik Starck
- Jimmy Wilhelmsson
- Johnny Söderberg, mitt mål att prata med honom mer än några sekunder blev uppfyllt.
- David Hall
- Lisa Förare Winbladh
- Isobel Hadley-Kamptz (*), naturen av vår kontakt beskrivs nedan under "Isobels och Lisas pizzeriabordsproblem".
- Jonas Söderström
- Jon Åslund (*)
- Coola morsan, men vi hade lämnat vår musikideologiska skiljelinjer bakom oss.
- Oscar Swartz (*)
- Karolina Lassbo (*).
- Per Gudmundsson


Två personer som jag inte träffade men hade tänkt prata med:
- Patrik Wallström (som jag skulle hälsa från en gemensam vän tillika listsvågrar)
- Christian Ubbesson (listsvåger och arbetar med saker, text mining, som jag är intresserad av)


Geekighet
Jag var med i flera diskussioner om geeekighet, vilket nog faller sig naturligt på en så här rätt geekig tillställning. Många av de personer som jag pratade med eller åhörde kan nog anses vara geekar, i alla fall i en något vidare mening (se nedan).

* en mer allmän diskussion med Steffanie Müller som började med att hon ansåg mig vara en större geek än hon själv (som om man kan jämföra geekigheter på detta sätt), varpå vi diskuterade naturen av detta begrepp.

* Jimmy Wilhelmsson berättade om dokusåpan FCZ som består av ett gäng geekar som spelar fotboll (och som jag inte sett men ändå stött på indirekt i ett rätt geekigt sammanhang) där geeken nu får ett ansikte och personlighet.

* både direkt och indirekt med Jon Åslund - som jag uppfattar som en übergeek, och det är en komplimang, Jon - i alla fall de facetter jag såg, vilket möjligen avspeglar mina egna intressen och värderingar. Lite roligt här är att jag förra söndagen stötte på Jons namn i ett helt annat sammanhang; nästan helt annat, eftersom det var i samband med att Hakke lämnade in sina svar på Bloggforum-pyssel i lite för poetiska formuleringar, nämligen att Jon är skapare av det underbara programspråket The Shakespeare Programming Language som jag känt till tidigare.

Det finns ett test The Nerd? Geek? or Dork? Test där jag själv fick följande resultat:


Pure Nerd
82 % Nerd, 47% Geek, 43% Dork
For The Record:

Man definierar de olika begreppen på ett sätt som jag inte nödvändigtvis håller med om.


A Nerd is someone who is passionate about learning/being smart/academia.
A Geek is someone who is passionate about some particular area or subject, often an obscure or difficult one.
A Dork is someone who has difficulty with common social expectations/interactions.

You scored better than half in Nerd, earning you the title of: Pure Nerd.

The times, they are a-changing. It used to be that being exceptionally smart led to bei
ng unpopular, which would ultimately lead to picking up all of the traits and tendences
associated with the "dork." No-longer. Being smart isn't as socially crippling as it o
nce was, and even more so as you get older: eventually being a Pure Nerd will likely be
replaced with the following label: Purely Successful.

Isobels och Lisas pizzeriabordsproblem
Under lunchen satt vi (Lisa, Rosmarie, Johnny, Hakke, hakank samt Daniel) på en pizzeria. Efter en stund ropar Lisa: "Isobel!" varpå denna kom fram till vårt bord. Efter lite inledandes flamsande ville naturligtvis Isobel och Lisa uttrycka sin ömsesidiga vänskap genom en kram eller liknande, varvid man insåg snabbt att ett logistiskt problem hade uppstått genom att bordplaceringen var sålunda:

Förkortningar:
1: Lisa (som alltså är den som känner Isobel)
2: Rosmarie
3: Johnny
4: Hakke
5: hakank
6: Daniel

Bordplaceringen:
_ V Ä G G
V 2 4 6
Ä _ _ _ Isobel (stående och rörlig)
G 1 3 5
G
_ V Ä G G

Där "V Ä G G" - på härsan och tvärsan - betyder omgärdande av en vägg eller väggliknande hinder. Bordet motsvaras av "_ _ _".


Problem: Hur optimerar man en hälsningsceremoni mellan Lisa och Isobel?
Eftersom sällskapet omslutes av tre väggar (eller väggliknande hinder) finns det inget sätt sätt för Isobel och 1 att enkelt uttrycka en fysisk hälsningsceremoni utan att 3 och 5 förflyttar sig från soffan. Det fanns ingen plats under bordet för Isobel att krypa in under, och det var såväl fysiskt, ekonomiskt som socialt omöjligt att använda bordet som transportsträcka. (Alternativa lösningar som att använda en wire för att utnyttja det lediga luftrummet ansågs inte realistiskt eftersom vi skulle alla vara tillbaka inom rätt kort tid och kranarbetarna var troligen på lunch under denna tid. Att använda elektronisk utrustning för att t.ex. skicka hälsningsemail, hälsnings-SMS eller bloggogram tänkte man troligen inte på i den då innevarande stunden.)


Lösningsalternativ A
Följande lösning är troligen det normala förfarandet i liknande uppkomna situationer. Inom parentes anges kostnaden för förflyttningen (se även kommentaren nedan), där vi här antar att förflyttning av en plats kostar 1 (dvs en enhet något).

a) Isobel flyttar sig en liten bit ut från bordet för att ge plats åt 5 (1)
b) 5 makar sig ut från bordet (1)
c) 3 makar sig ut från bordet (2)
d) 1 makar sig ut från bordet (3)
e) 1 uttrycker sin vänskap med Isobel (0)
f) 1 makar sig tillbaka till sin plats (3)
g) 3 makar sig tillbaka till sin plats (2)
h) 5 makar sig tillbaka till sin plats (1)
i) Isobel återställer sig på sin plats. (1)
Summa kostnad: 1 + 1 + 2 + 3 + 0 + 3 + 2 + 1 + 1 = 14

Lösningsalternativ B
Det finns en variant till A där Isobel i stället makar sig in i soffan enligt följande schema:

a) Isobel flyttar sig en liten bit ut från bordet (1)
b) 5 makar sig ut från bordet (1)
c) 3 makar sig ut från bordet (2)
d') Isobel makar sig in till plats 2 (2+1.5=3, se nedan)
e) 1 uttrycker sin vänskap med Isobel (0)
f') Isobel makar sig ut från bordet (2*1.5=3, se nedan)
g) 3 makar sig in till sin plats (2)
h) 5 makar sig in till sin plats (1)
i) Isobel återställer sig på sin plats. (1)
Summa kostnad: Summa kostnad: 1 + 1 + 2 + 3 + 0 + 3 + 2 + 1 + 1 = 14

Isobel behöver här endast förflytta sig två (2) platser vilket ger en kostnad på 2, men eftersom Isobel är fullt påklädd i vacker förvinterskrud medför förflyttning i soffa en något större kostnad per förflyttning, dvs 2 * 1.5 (kostnad 3).

Det är alltså samma kostnad för alternativ A och B (14).


Alternativ C: en mer kostnadseffektiv lösning
Efter snabbt övervägande föreslogs en "proxylösning":


Isobel kramar 5 (0.5)
5 kramar 3 (0.5)
3 kramar 1 (0.5)
1 kramar 3 (0.5)
3 kramar 5 (0.5)
5 kramar Isobel (0.5)
Totalkostnad: 6 * 0.5 = 3.

Eftersom kramar i en soffa förnärvarande har en kostnad på cirka 0.5 skulle detta ge en totalkostand på 6*0.5 = 3 var det naturligtvis bättre än de ovanstående föreslagna alternativa lösningarna.

Alternativ D: mer effektiv lösning och den implementerade
Den lösning som faktiskt implementerades var med (kind)pussar. Som tidigare anges kostnaden inom parentes.

a) 1 pussar 3 (0.1)
b) 3 pussar 5 (0.1)
c) 5 pussar Isobel (0.1)
d) Isobel pussar 5 (0.1)
e) 5 pussar 3 (0.1)
f) 3 pussar 1 (0.1)
Totalkostnad: 0.6

Detta verkar således vara det optimala tidsödande sättet om man använder hälsningsceremonierna kram eller kindpuss.

Kommentarer
I föreslagningsalternativen A och B antogs en kostnad 0 för kram mellan 1 och Isobel men i C antogs den vara 0.5. Hur går detta ihop? Jo, helt enkelt genom att här anta att vinsten för hälsningsceremonin också är 0.5. Detta kan med rätta kritiseras, och man kan här fundera på om det överhuvudtag går att jämföra kostnaden de två principiella olika hälsningsmodellerna:
* direkt hälsningsceremoni, dvs där Lisa och Isobel verkligen hälsar på varandra
* den indirekta ceremonin (proxyvarianten) där hälsningen skrev via andra på platsen närvarande personer.

Om vinsten i den direkta hälsningsmodellen är tillräckligt stor kan alternativ A eller B vara att föredra framför C och D. Vidare forskning - förhoppningsvis kompletterade med empiriska studier - inom området kan förhoppningsvis klargöra detta.

Vidare utökning av modellerna bör även studera de vinster som uppstår hos proxy-personerna. I ovanstående modell har vi helt ignorerat vinsterna för 3 och 5 som får förmånen att interagera med 1, med Isobel samt med varandra. Troligen är sådana vinster inte försummbara.


Två noter
a) Om Isobel eller för den delen 1, 2, 3, 4 respektive 6 skulle känna sig kränkta av ovanstående beskrivning bes det om ursäkt.
b) Det inses snabbt att ovanstående beskrivning - i sin nuvarande form - inte skulle bli publicerad i Hänt-i-Veckan eller liknande förmedlingsmedier, oavsett om det funnes kompletterande tillfällestagna bilder på de alternativa lösningarna. Möjligen skulle bilderna själva kunna publiceras med en något mer snärtig bildtext, t.ex. Algoritmchock kring logistiskt hälsningsceremoniproblem eller - mer troligen - Pusschock med Isobel!.

Posted by hakank at 09:59 EM Posted to Blogging | Matematik | Pyssel | Comments (9)

november 13, 2005

Bloggforum-pyssel

Nästa helg är det Bloggforum 3.0 och det ska bli både intressant och trevligt.

Inför detta evenemang kommer här ett litet pyssel som bygger på namnen för dem som hittills - 11-snåret 20051113 - anmält sig till forumet. Pysslet kan ses som ett sätt att bli bekant med meddeltagarna, eller i alla fall deras namn.


Koder för de anmäldas namn
I denna lista visas anmälningsnamnet samt en kod. Exempel:

David Hall: 201
Henrik Torstensson: 200
Pelle Sten: 200
Sara Holm Stålhand: 311
Kal Ström: 210
Jonas Morian: 201
...

Det som avgjort koden är endast anmälningsnamnet, inget annat. Ordningen i listan är samma ordning som på Bloggforum-sajten (förutom att första namnet är borttaget ur listan eftersom det tillhör tävlingen).


Pyssel
Tävlingen består i att besvara följande två frågor:
1) Vilken princip har använts för att tilldela ett namn just denna kod.
2) Vilken kod får mitt namn (Håkan Kjellerstrand) enligt denna princip.


Det först korrekta svaret på båda frågorna belönas med en ära samt en öl (*), att överlämnas t.ex. just på Bloggforumdagens kväll. Sista svarsdag är torsdagen 18 17 november 2005. Svar kan lämnas antingen i kommentarerna till denna blogganteckning eller via epost till hakank@bonetmail.com. Besvarare får även gärna berätta hur man gått tillväga för att angripa problemet.

Not: Denna tävling är på intet sätt sanktionerad av arrangörerna av Bloggforum 3.0 . Dessa arrangörer har inte heller någon insides information om det korrekta svaret på pysslet, och är naturligtvis även välkomna att deltaga.


(*) Sedvanlig disclaimer: Vi pratar här om en normalöl, inga kaggar eller specialvarianter etc. Vad gäller äran finns inga sådana begränsningar.


Uppdatering: Vinnare!
Vi har en vinnare! Håkan hakke Karlsson var den förste (och hittills ende) som klarat samtliga uppgifter, vilket han gjorde både galant och elegant. Stor heder samt en öl åt honom (och det står 3-2 i öl till honom nu). Han har även i detalj beskrivit sina blind- och felskär i sin problemsondering vilket var mycket intressant att läsa.

Den officiella tävlingen är nu alltså avslutad, men fundera gärna på det tredje delproblemet, med eller utan hjälp av ledtråden som finns nedan. Det blir dock ingen ersättning - mer än del-äran - till den som kommer med korrekt svar.

Det korrekta svaret på den tredje delfrågan kommer att publiceras i veckan. Om du är väldigt hialös får du gärna maila efter lösningen eller fler ledtrådar.


Delsvar a och b
Det var alltså tre delproblem, där en siffra i koden motsvarar ett delproblem. Första och andra siffran verkar inte ha varit så svåra att lista ut.

a) Första siffran är antal ord i namnet. "David Hall" ger 2, "Sara Holm Stålhand" ger 3, "Siv A" 2 etc.

b) Andra siffran är 1 eller 0 beroende på om antalet tecken - efter borttagninga av mellanslag - är jämt respektive udda.

Koden för "Håkan Kjellerstrand" är hittills: 21?.


Fortsatt pyssel, delproblem c
Den tredje siffran var tydligen svårare (vilket var vad jag hoppades). Här är en ledtråd och ett tips till den som vill fortsätta.

Ledtråd: Badge problem, som också var inspirationen till detta pyssel.

Tips: Det är troligen enklare att utgå från de kortaste namnen (strängarna) för att begränsa antalet olika möjliga lösningar, vilka här listas:

Maria: 100
Rasmus: 110
Eva: 101
Anna: 110
Siv A: 211
gonza: 100
mary: 111


Uppdatering Torsdag 2005-11-17: Svar på sista delproblemet
Här kommer så svaret på den sista delfrågan, dvs den sista siffran i koden.


c) Sista siffran anger om tredje sista tecknet är en vokal eller konsonant. En vokal betecknas med en etta och en konsonant med en nolla.

Den fullständiga - tresiffriga - koden för "Håkan Kjellerstrand" blir alltså 211, eftersom det tredje sista tecknet är "a" som är en vokal och ger siffran 1.


Det var det. Tack till er som skickat in era lösningar, och ett speciellt tack till Hakke som var först och även meddelat detaljerade redogörelser för problemlösningsförfarandet, vilka troligen kommer att publiceras å det offentliga, antingen här eller där. Jag är imponerad av att han löste det med endast POP - penna och papper - som extern hjälp. (Själv skriver jag nästan alltid några program för att lösa slika problem eller för att verifiera att lösningen är korrekt.)

Posted by hakank at 11:20 FM Posted to Pyssel | Comments (2)