juni 18, 2013

10 år med blogg

Idag för exakt tio (10, t-i-o) år sedan skrev jag det första blogginlägget på min svenska blogg hakank.blogg: Mina första 1000 dagar med Taiji samt det andra Min första dag med webblogg (som naturligtvis var ett metainlägg, definitivt inte det sista eftersom just bloggfenomenet på olika nivåer intresserades för).

Detta påbörjade en (emellan lite för) intensiv period där saker som intresserades av skrevs ned och diskuteras. Något som inte räknades med - en positiv bieffekt - var att få kontakt med många väldigt trevliga, intressanta och smarta människor, både via bloggarna men även IRL/AFK, t.ex. via de s.k. blogg(are)träffarna (något som fortfarande hålls på med, men utan kallelser och de långa sammanfattningarna och via en Facebookgrupp som sammanhållande tekniskt stöd. Säg till om du är intresserad.).

Här är några saker som det skrivits om; referens görs till respektive kategorier i bokstavsordning:

Efter cirka 2010 skrevs det inte så mycket på denna blogg utan det skrevs på andra ställen i stället, dels - ett kort tag -
Arrays in Flux. Däremot har det skrivits relativt ofta sedan 2009 - men oregelbundet - på My Constraint Programming Blog som handlar om Constraint Programming (Wikipedia), dvs det som på svenska kallas "villkorsprogrammering"; och det är - kortfattat - ett sätt att beskriva och lösa framförallt kombinatoriska problem på ett sätt som är mer högnivå och deklarativt än traditionella programspråk.

En av anledningarna till att det inte bloggas så väldigt mycket nu för tiden är att de s.k. sociala närverkssystemen har tagit över mycket av de långa - och korta - blogginläggen. Här är de trenne ställen som månne kan vara intressant för den som vill följa det som händer, men inte där heller är det en drös av länkexplosioner eller omvärdskommentarsfyrverkerier.

Som har skrivits om tidigare, är den korrekta kontaktadressen hakank@gmail.com och inget den där gamla bonetmail-adressen.

Tidigare bloggades det i princip om alla program, findings, programsspråkslärande som gjordes/upptäcktes/testades, men numera läggs det endast en länk på hemsidan www.hakank.org, eventuellt följt av twittrande, googleplussande eller facebookande kring detta faktum.

Här är för övrigt några andra länkar till/kring/för diverse facetter av livet (törhända en viss begränsad del av detsamma liv: det görs en hel del andra saker som det dock inte (be)skrivs om publikt):

Några "för övrigt" (eller se-även):

  • Jonas Söderström - en Sveriges allra första bloggare, för övrigt känd författare av boken Jävla skitsystem! - håller på att skriva en bok om den svenska blogggistoren. Han kallar bloggen om detta påpassligt just för Den svenska blogghistorien

  • Om du vill kolla in ett nytt multiparadigm-programmeringsspråk som är inspirerat av logikprogrammering, funktionsprogrammering, med imperativa konstruktioner samt stöd för villkorsprogrammering så kanske Picat är något för dig. Det är väldigt nytt (vi pratar dagar publikt tillgängligt) så vissa saker saknas; påverkanskampanjer har påbörjats för vissa av dessa vissa saknade saker. Och här är My Picat page med över 200 program/modeller/exempel på vad man kan göra; lejonparten av dessa använder villkorsprogrammering ("standardproblemen"), men det finns även lite från Rosetta Code etc.

Tack för denna tid alla goa med-bloggare och läsare!

Notera (eftersom föregående interjektion kan tolkas): Detta blogginlägg är inte det sista, bara det - i skrivande stund - det senaste.

Posted by hakank at 10:30 FM Posted to Blogging

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:

  • My Constraint Programming Blog (uppdateras typ någon/några gånger i månaden)
  • Arrays in Flux (som i och för sig mest innehåller gamla livstecken)
  • hakank.org som innehåller - men odaterade - tecken om olika saker som gjorts (den senaste - i skrivande stund - tiden har det varit rätt mycket lekande med nya - för mig - programspråk och liknande).

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:
  • accelerationsmunstycke
  • satellitkommunikationssystem

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

  • satellitkommunikationssystemåtgärdsförslag

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:

  • a: 1
  • b: 1
  • c: 1
  • e: 2
  • g: 1
  • h: 1
  • i: 1
  • j: 1
  • k: 1
  • l: 2
  • m: 1
  • n: 2
  • r: 2
  • s: 1
  • t: 2
  • u: 1
  • y: 1
  • å: 1
  • ö: 1

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:

  • giftermålsanbud
  • ishockeyförbund
  • jämlikhetsfråga
  • oförvansklighet

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

februari 21, 2010

Ny engelskspråkig blogg: Arrays in Flux

Häromdagen startade jag min andra engelskspråkiga blogg: Arrays in Flux (ungefär "Vektorer i rörelse").

Det första inlägget Arrays in Flux: My third blog, and second English beskriver inriktningen och förklarar namnet mer.

Det andra inlägget, som precis publicerades, Symbolic regression (using genetic programming) with JGAP beskriver det jag hållt på med de senaste veckorna. Det är en utveckling av det som skrevs om i Eureqa: equ.ation discovery med genetisk programmering.

Posted by hakank at 06:46 EM Posted to Blogging | Machine learning/data mining

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

september 17, 2009

På Twitter: http://twitter.com/hakankj

I dag bestämde jag mig att börja använda Twitter mer, och mer systematiskt. För tillfället innebär det primärt att jag notifierar om nya constraint programming-modeller (i stället för att vänta en vecka med att blogga om ett gäng nya modeller) och därmed relaterade saker, men även annat kan dyka upp. Det förra (constraint programming) kommer primärt att vara på engelska.

Min Twitter-sida är www.twitter.com/hakankj. Notera användarnamnet, med ett avslutande "j" (tyvärr var det vanliga namnet upptaget när jag registerade mig augusti 2008).

Posted by hakank at 05:45 EM Posted to

augusti 30, 2009

The Pop-11 programming language and Poplog environment

First I must apologize for the Swedish readers for including an english text here: Sorry about that. I may do it again, but this blog has not permanently gone English. It has, however, changed its focus somewhat in other ways from the start in june 2003.

Pop-11 and its environment Poplog is relatively unknown, originally designed for research and education in artificial intelligence. From What is Poplog:
Poplog is an integrated toolkit providing a highly extendable collection of languages and tools for teaching, research and development. By default it includes incremental compilers for three powerful AI programming languages
* Pop-11--the core language -- used to implement itself and the others;
* Common Lisp; and
* Prolog;
as well as
* Standard ML, a widely used functional language.

...

Most of Poplog is implemented in Pop-11, including the incremental compilers for all four languages and the integrated programmable editor.
Here I will mostly write about the programming language Pop-11, but also mention how it is possible to integrate Pop-11, Prolog, and Lisp. See the programs below.

Pop-11/Poplog is a huge system which includes - besides the four languages mentioned above and the VED editor which is also used for the help/teach system - much material for learning the system, as well as learning artificial intelligence. "Huge" above refers to the content of the system, not to the actual memory "footprint". For more about the size, see the entry Size at the Free Poplog page.

The language Pop-11 is Lisp-like in its approach but uses an Algol-like syntax. It has many of my favorite features of a programming language:
  • interactive environment
  • array/list comprehension
  • pattern matching (on lists), and supports regular expressions
  • functional programming, higher order functions
  • multi-paradigm approach
  • arbitrary precision

Some larger teaching examples

Here are some examples of the teach/help files. Many of these shows how to use a specific library, and some of them just teaches an artificial intelligence concept.

Documents and links

Mailing lists

My Pop-11/Poplog page

My Pop-11/Poplog page contains some of my Pop-11 programs. Some of them are the "mandatory" programs I always implement when learning a new programming language.

Some of the program below requires functions from the GOSPL (Global Open Source Poplog Library) library, such as split, split_with. GOSPL was available from www.poplog.org, but that site seems to be defunct right now. The library is now available from www.cs.bham.ac.uk/research/projects/poplog/, or more specific here: gospl_1_2_0.tar.gz

  • init.p
    init.p: My init.p file.
  • compiling
    compile_test.p demonstres how to:
    - compile a Pop-11 program to a saved (.psv) image,
    - compile to an executable program.
    Note: This was tested on a Linux machine (Mandriva).
  • Concordance
    concord.p: Reads a file and show the number of occurrence of the words (sorted in order of occurrence). Requires GOSPL (see above).
  • Project Euler
    euler_project.p: My Pop-11 solutions of the first 16 Euler Project problems. Requires newmemo.p, and GOSPL (see below). A note about the style in this program: When learning a programming language which has an interactive shell, I tend to use one-liners and array comprehension a lot. Especially in this case, since I used much of the principles used from my Lisp programs (using loop a lot).
  • join (string)
    join.p is a small utility function to join the characters of a string.
    Syntax: join(string, separator)
    e.g. join('hello,world','|') results in h|e|l|l|o|,| |w|o|r|l|d. This is used for example in read_test.p.
  • Lisp in Pop-11
    lisp_in_pop11_test.p demonstrates how to run (Poplog's) Lisp code in Pop-11.
  • Grammar generation (swedish)
    mygram.p generates some swedish (nonsense) sentences given a simple grammar and lexicon. It uses the GRAMMAR library (which includes a simple english grammar and lexicon).

    The generating sentences is presented first as a parse tree, then the sentence.
    ** [s [np [snp_t [det_t ett]
                     [adj_t svagt]
                     [adj_aux_t [fastän trött]]
                     [noun_t handsfack]]]
          [vp [verb [grävde ned]]
              -
              [verb_aux [utan vett och sans]]
              -
              [np [snp_n [det_n en] [noun_n buske]]]]]
    
    ;;; The sentence:
    ** ett svagt [fastän trött] handsfack [grävde ned] - [utan vett och sans] - en buske.
    
    ;;; Flattened
    ** ett svagt fastän trött handsfack grävde ned - utan vett och sans - en buske.
    
    Which may be translated as something like
    a weak although tired glove department dug down - without wit or sense - a bush
    
    Also, see tparse_test_swe.p mentioned below for generating the parse tree from this sentence.
  • Memo function
    newmemo.p defines a Memo function (from Robin Popplestone's Pop-11 book) and use it for the Fibonacci sequence.
  • N-puzzle
    n-puzzle.p: 8-puzzle and 15-puzzle, etc using the library SOLVEMS.
  • Pop-11 in Lisp
    pop11_in_lisp_test.lsp: Simple demonstration how to run Pop-11 code in (Poplog's) Lisp.
  • Pop-11 in Prolog
    pop11_in_prolog_test.pl: Simple demonstration how to run Pop-11 code in (Poplog's) Prolog.
  • Prolog in Pop-11
    prolog_in_pop11_test.p: Simple demonstration how to run (Poplog's) Prolog code in Pop-11.
  • Primes / dynamic ("lazy") lists
    primes.p generates prime numbers using a dynamic ("lazy") list.
  • Regular expressions
    Pop-11 has regular expressions, albeit with a slighly different syntax than we are used to. The program read_test.p reads a word list and test each words against the regular expressions of consecutive characters, e.g. ".*a.*.b.*c.*" (in Pop-11 'a@.@*b@.@*c@.@*'), ".*b.*c.*d.*", ".*c.*d.*e.*", etc.

    Using the standard Linux wordlist /usr/dict/words if found no word where there are 6 consecutive letters, but there are many of length 5. e.g.
    ** [Testing abcde a@.@*b@.@*c@.@*d@.@*e]
    ** [abecedaire abecedaries abjectedness aborticide absconded abscondedly
            abscondence absconder absconders abstractedness ambuscade ambuscaded
            ambuscader ambuscades ambuscadoed amebicide amoebicide bambocciade
            bambochade carbacidometer Cerambycidae nonabstractedness Oxylabracidae
            scabicide unabstractedness]
    Counter: 25
    
    ...
    
    ** [Testing qrstu q@.@*r@.@*s@.@*t@.@*u]
    ** [quasi-respectful quasi-respectfully]
    Counter: 2
    
    ...
    
    
    Using a swedish wordlist I found some words of 6 consecutive characters.
    ** [Testing klmnop k@.@*l@.@*m@.@*n@.@*o@.@*p]
    ** [alkoholmonopol kaliumtetracyanokuprat kaliumtetracyanoplatinat komplemento  peration kulminationspunkt vinkelmätningsmikroskop]
    
    This program requires join.p.
  • String matching, strmatches
    read_test_strmatches.p: Read a word list and test each words against a string pattern of consecutive characters. Same as read_test.p (see above), but uses the strmatches function (not in the standard Poplog distribution). This version is much slower than using regular expression. Also, see comments below about strmatches.
  • Solver: Banana problem
    solver_banana_problem.p: (GPS) Banana problem using SOLVER library (schema and problem from Norvig "Paradigms of Artificial Intelligence Programming").
  • Solver: Block worlds
    solver_blocks_world.p: (GPS) Blocks world problem using SOLVER library (schema and problem from TEACH SOLVER).
  • Solver: Maze problem
    solver_maze_problem.p: (GPS) Maze problem using SOLVER library (schema and problem from Norvig "Paradigms of Artificial Intelligence Programming").
  • Solver: School problem
    solver_school_problem.p: (GPS) School problem using SOLVER library (schema and problem from Norvig "Paradigms of Artificial Intelligence Programming").
  • Timing
    timing_test.p: Two timing functions which only run the procedure once (as opposed to the builtin timing which runs many times). One definition is a syntax word, the other is a procedure proper. Includes a simple test.
  • Parsing (swedish text)
    tparse_test_swe.p: Parses (simple) swedish sentences given a simple grammar and lexicon. Uses the TPARSE library.

    Continuing from the grammar example above:
    listparses("s", [ett svagt
                     [fastän trött]
                     handsfack
                     [grävde ned]
                     [utan vett och sans]
                     en buske])==>
    
    ** [[s [np [snp_t [det_t ett]
                      [adj_t svagt]
                      [adj_aux_t [fastän trött]]
                      [noun_t handsfack]]]
           [vp [verb [grävde ned]]
               [verb_aux [utan vett och sans]]
               [np [snp_n [det_n en] [noun_n buske]]]]]]
    

Installation

This is how I install Pop-11/Poplog when a new version arrives. I run on a linux and the current_poplog directory is a symbolic link to the actual latest distribution directory. Here I assume that the version is v15.63.
  • move the previous installation, e.g.
      rm current_poplog # this is a link
       mv v15.63 v15.63.old
    
  • Download the latest version of ./get-and-install-v15.63-poplog-here (or whatever version) from http://www.cs.bham.ac.uk/research/projects/poplog/v15.63/#installing.
  • chmod +x get-and-install-v15.63-poplog-here
  • ./get-and-install-v15.63-poplog-here
  • After the installation:
    ln -s v15.63 current_poplog
  • Fetch the latest contrib.tar.gz
    Unpack and copy in
    current_poplog/pop/v15.63/pop/packages/contrib/

Posted by hakank at 09:26 FM Posted to Program | Comments (1)

augusti 05, 2009

En uppdatering om vad som händer

Som tidigare nämts så är det på andra bloggen My Constraint Programming Blog det händer saker numera.

Vad har hänt där då (sedan maj)? Faktiskt en hel del. Jag länkar inte till alla inlägg utan endast till några "high lights":

Maj

* Report from SweConsNet2009, including my presentation, som alltså är en rapport från villkorsprogrammeringsworkshopen SweConsNet09, där jag var med och föreläste en stund. Stora delar av maj gick åt till att förebereda för denna föreläsning.

Juni

* Lyckades efter ett antal genomläsningar av några olika skrifter förstå hur det globala villkoret (global constraint) cumulatives funkar i Gecode, och skrev om detta i Scheduling with the cumulatives constraint in Gecode .

* Publicerade och bloggade om villkorsprogrammeringssystemet ECLiPSe (nej, det ska inte förväxlas med utveckligs-GUI:t). Det är ett riktigt trevligt Prolog-baserat system med mycket användbara utökningar såsom loopar och arrays som gör att man inte måste lösa allting med rekursioner och listor. Se vidare My ECLiPSe page som nu innehåller cirka 120 modeller; till största delen har just desamma utökningar används.

Juli

* Skapade ett samlingssida över de problem som modellerats i fler än ett villkorsprogrammeringssystem: Common constraint programming problems som presenterades i Common constraint programming problems.

* Modellerade mina cirka 17 basmodeller ("learning models") i ett ytterligare villkorsprogrammeringssystem: Tailor, som konverterar Essence' (ett högnivåspråk liksom t.ex. MiniZinc och Comet) till Minion, Gecode eller FlatZinc (det som MiniZinc använder). Och det var just stödet av FlatZinc inspirerade till detta.

Tailor presenterades i New Tailor version (v0.3.2) and My Essence'/Tailor page.
Se mera på My Tailor/Essence' page.

Augusti, idag faktiskt

Följande når världen för första gången här, nämligen en liten MiniZinc-modell som löser Strimko-problem. Strimko är en mer avancerad variant av latinska kvadrater (alla rader respektive alla kolumner måste innehålla distinkta värden) där man även ska se till så att ytterligare villkor i form av en "strängar" av celler också måste vara olika. (Strimko är således inte helt väsensskilt från Sudoku.)

MiniZinc-modellen är strimko.mzn med de tre probleminstanserna:
strimko_067.dzn, strimko_068.dzn samt strimko_070.dzn.

Inspiration till detta var från bloggen 360: A New Twist on Latin Squares.


Till sist, för denna gång
För en sammanställning över de olika villkorsprogrammeringssystem jag kikat (och fortfarande kikar) på, se översiktsidan med det passande - men i någon mån förutsägbara - namnet My Constraint Programming Page.

Posted by hakank at 07:50 EM Posted to Constraint Programming

maj 03, 2009

spipat: SNOBOL/SPITBOL-patterns i C++ och Python

spitpat är ett C/C++-bibliotek som implementerar SNOBOL/SPITBOL-patterns för C++ och Python. Så här presenteras spitpat i distributionens fil README:
This is a transliteration (largely mechanincal translation) to C99
of the GNU Ada Translator (GNAT) SPITBOL.Pattern (spipat) package by
Robert Dewar, the creator of SPITBOL GCC v3 provides all needed
features.

The primary goal is to enable embedding SNOBOL4 style patterns in
popular scripting languages (ie; Ruby, Python, Perl, JavaScript),
which are almost universally written in C.

Testing and programming pattern construction in C is painful, due to
the lack of operator overload. To hasten testing, I've written a C++
wrapper "Pattern" around the C spipat library. The goal is to enable
testing, and provide an experience familiar to SNOBOL programmers. A
more pure C++ approach might be to use method chaining to construct
patterns, and to implement the entire package as a template that takes
an arbitrary scalar type to represent a character.
Naturligtvis är det Phil Budne som gjort denna translitterering; det är han som ligger bakom den fria SNOBOL4-implementationen CSNOBOL4 full av klockor och visslor.

C++
Så här kan SNOBOL/SPITBOL se ut i C++:
#include 
#include 

using namespace std; 

#include 

int main() {
 string subject1("Hello World!");
 string hello("Hello");
 Pattern hello_pattern(hello);
 Pattern world_pattern("World");
  
 // pattern w/ concatenation
 Pattern p1 = hello_pattern & ' ' & world_pattern;
 Pattern p2 = hello_pattern & ' ' & world_pattern & Arb();
 Pattern p3 = hello_pattern & Arb() & world_pattern;

 Matchres m1;
 cout << "p1: " << p1 << "\n";
 cout << "p2: " << p2 << "\n";
 cout << "p3: " << p3 << "\n";
 cout << "subject1 ~ p1: " << Match(subject1, p1) << "\n";
 cout << "subject1 ~ p2: " << Match(subject1, p2) << "\n";
 cout << "subject1 ~ p3: " << Match(subject1, p3) << "\n";

 return(0);
}

Pythonstöd
Än så länge finns det - av de agila programspråken - endast stöd för Python men ovanstående antyder att det även kan komma stöd för andra programspråk. Det finns ett par exempel i distributionen, t.ex. nqueens där det emfatiska området är de SNOBOL-specifika delarna
# from Victor Berstis' Minnesota SNOBOL4 distribution
# N queens problem, a string oriented version to demonstrate the power
# of pattern matching.

# translated to Python w/ spipat by Phil Budne

from spipat import *

n = 8
nm1 = n - 1
np1 = n + 1
nsz = n * np1

# This pattern tests if the first queen attacks any of the others:
test = break_("Q") + "Q" + (arbno(len_(n) + "-") + len_(n) + "Q"  |
			    arbno(len_(np1) + "-") + len_(np1) + "Q" |
                            arbno(len_(nm1) + "-") + len_(nm1) + "Q")
p = len_(nm1) * 'x' + len_(1)
l = "Q" + "-" * nm1 + " "

solution = 0
def solve(b):
    global solution

    if len(b) == nsz:
        solution = solution + 1
        print "Solution number", solution, "is:"
        while len(b) >= np1:
            print b[0:np1]
            b = b[np1:]
    else:
        # Add another row with a queen:
        b = l + b
        # "LOOP"
        i = 0
        while i < n:
            i += 1
            if not test.match(b):
                solve(b)

            # "NEXT"
            # Try queen in next square:
            m = p.match(b)
            if m:
                b = m.repl('-' + m.dict()['x'])

solve('')
Se även
* För andra SNOBOL/SPITBOL-relaterade saker, se www.snobol4.org.
* David Shield har nyligen skrivit en del SNOBOL/SPITBOL-relaterat på sin blogg The Wayward Word Press , t.ex. Announcing New LinkedIn Group, SPITBOL , Announcing spitbol, a New Project Hosted at Google Code.

Posted by hakank at 09:42 FM Posted to SNOBOL/SPITBOL

april 28, 2009

Karl Wettin intervjuas om Lucene and Mahout

Karl Wettin har blivit långintervjuad i Interview with Karl Wettin on Lucene and Mahout.

Grant Ingersoll talks to Karl Wettin, an Apache Lucene and Mahout Committer and independent Lucene Solr consultant. Karl talks about lexically complex European languages, using terms with shingles to simplify queries rather than complex span queries, and improving spellchecking with reinforcement learning, and looking at Mahout NLP.

Kul, Kalle!

Via Clas på Frisim som faktiskt lyckades avkoda att "Wolkan Schellestum" är mitt namn. (Jag har inte lyckats lyssna på ljudversionen; där är det kanske tydligare.)

Det skrevs för övrigt om Kalle anno 2003 i Silvertejp.

Posted by hakank at 09:07 EM Posted to Machine learning/data mining

april 10, 2009

Mitt föredrag på SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned"

Sedan jag startade min engelskspåkiga My Constraint Programming Blog kring årsskiftet har jag fått flera nya kontakter och haft mycket intressanta maildiskussioner.

Några av dessa diskussioner har lett till att jag kommer att prata på SweConsNet Workshop 2009 27 maj 2009 i Linköping. SweConsNet (Network for Sweden-based researchers and practitioners of Constraint programming) presenteras mer här (Uppsala Universitet), workshoppen beskrivs även i bloggartikeln SweConsNet Workshop 2009.

Titeln på föredraget är Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned och kommer att innehålla findings funna under tiden jag kollat in och lärt mig olika constraint programming-system (och jag lär mig nya saker hela tiden), jämförelser mellan systemen och kanske ett och annat önskemål.

För mer om de system som kommer att tas upp, se vidare :

Tiden före den specialinriktade bloggen skrevs om dessa saker (främst MiniZinc, JaCoP samt Gecode/R) på denna svenska blogg i kategorin Constraint programming.

Under tiden jag förbereder föredraget planerar jag att blogga mer systematiskt kring de olika saker som kommer att tas upp.


Not: Jag skrev ungefär samma saker häromdagen i My talk at SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned", men tyckte det kunde vara kul att skriva om det här också.

Posted by hakank at 09:52 FM Posted to Constraint Programming

mars 16, 2009

Lite om vad som händer på andra bloggen: My Constraint Programming Blog

Som tidigare nämnts är det inte här utan på My Constraint Programming Blog ("Min villkorsprogrammeringsblogg") jag numera mest håller till.

Här är en liten sammanfattning om vad som hänt där och i samband med detta.

* En stor drös med Comet modeller på My Comet page. Några exempel:


* En mycket mindre drös med MiniZinc-modeller på My MiniZinc page.

Men de modeller som tagit mest tid är följande

Nonogram
Här är de blogganteckningarna som presenterar de olika varianterna, i normal sorterad tidordning:
1) More Comet models, e.g. Nonogram, Steiner triplets, and different set covering problems som presenterade den första Nonogram-modellen. Långsam var den.
2) Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more presenterade en mycket snabbare Nonogram-modell som använder principen bakom reguljära uttryck (villkoret regular).
3) samt slutligen Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about 1 second där jag hittade lite mer saker att förbättra, bl.a. med hjälp av en av mina husgudar Pascal Van Hentenryck och som är en av skaparna av just Comet.

Ungefär samtidigt kom jag i kontakt med gänget bakom Gecode (C++ baserat), det snabbate constraint programming-systemet som jag känner till. Roligt nog har de nu lagt in samma förbätring i sitt Nonogramprogram.


Pi Day Sudoku
I lördags var det Pi-dagen (3.14 som vissa skriver den 14 mars) och som hyllning skapade Brainfree Puzzles några dagar tidigare en tävling: Pi Day Sudoku 2009. Det är som vanliga Sudoku fast med knorr: förutom att det ska vara 1..9 på samtliga rader och kolumner ska det finnas exakt tre stycken Pi. Till detta kommer att man inte har de vanliga kvadratiska regionerna som kräver samma fördelning av siffror utan det är även olika former på regionerna (kolla sajten så förstår ni bättre). Jag har slutat med att lösa Sudokuproblem för hand, däremot var de speciella kriterierna ett intressant problem att modellera med villkorsprogrammering (constraint programming).

Första modellen, som var rätt långsam, skrevs om i Pi Day Sudoku 2009. Efter lite funderande, och framförallt diskuterande med Mikael Zayenz Lagerkvist (från sagda Gecode team), snabbades modellen upp avsevärt. Detta beskrevs i Solving Pi Day Sudoku 2009 with the global cardinality constraint.

Till förfång för alla de som som söker på Pi Day Sudoku har varken lösningen på problemet eller modellerna presenterats på bloggen (det blir inte förrän tävlingen är över).


Gecode 3.0.0
Vi får ju inte heller glömma att version 3.0.0 av Gecode släpptes för några dagar sedan. Jag rekommenderar varmt den mycket trevliga introduktion till modellering i Gecode: Modeling with Gecode (PDF).

I och med att version 3 har släppts kommer det inom kort även stöd för det grafiska verktyget Gist till MiniZinc, dvs när man har Gecode/FlatZinc som lösare (och det har man alltid som förstaval). Det ser jag mycket fram emot.


Till sist: MiniZinc Challenge 2008
Resultat av constraint programming-tävlingen MiniZinc Challenge 2008 kom förra vecka. Inte förvånande vann Gecode. Mer om detta skrevs i MiniZinc Challenge 2008 Results.

Posted by hakank at 08:34 EM Posted to Constraint Programming | Reguljära uttryck etc

februari 28, 2009

Bloggträff söndag 1 mars kl 17.00 på Kin Long i Malmö

Söndagen den 1:a mars klockan 17.00 är det bloggträff på Kin Long i Malmö. Alla är välkomna. Meddela gärna att ni kommer så vi kan reservera bord för ungefär rätt antal. Anmäl antingen bland kommentarerna här eller via mail, hakank@bonetmail.com

Det finns också en Facebookgrupp Bloggträffar i Malmöregionen, öppen där alla får bli medlemmar.

Posted by hakank at 05:14 EM Posted to Bloggmiddagar

januari 31, 2009

Constraint programming modeller i Comet

Den senaste veckan har constraint programming (och constraint-based local search) systemet Comet kollats in.

Systemet beskrivs i följande två anteckningar på My Constraint Programming Blog (det är där jag håller till mest nuförtiden):
* Comet version 1.1., där finns länkar och övergrippande information om systmet.
* I Some Comet constraint programming (CP) models , som innehåller kommentar om systemet, lite kodexempel samt länkar till modeller.

Mer information om systemet, samt några Comet-modeller finns på My Comet page.

I framtiden kommer jag bl.a. att kolla in mer hur man arbetar med constraint-based local search som klarar av att lösa mycket stora problem. Detta begrepp (med Comet som exempel) beskrivs i den trevliga och inspirerande boken Constraint-Based Local Search skriven av Pascal van av Hentenryck and Laurent Michel (huvudutvecklarna av Comet).

Posted by hakank at 12:00 EM Posted to Constraint Programming

januari 15, 2009

Constraint programming modeller i Gecode/R (Ruby interface till Gecode)

För er som är intresserade av (eller åtminstone nyfikna på) både constraint programming och Ruby kan jag rekommendera Gecode/R, ett mycket trevligt system

Jag har den senaste tiden skapat en del Gecode/R-modeller och lagt dem på My Gecode/R page. Alldeles nyss skrevs om detta på min constraint programming blog: Some models in Gecode/R (Ruby interface to Gecode). Ni får läsa mer själva.

Posted by hakank at 08:46 EM Posted to

januari 05, 2009

Isomorfa ord (Isomorphic Words) - programmet

2004 skrevs programmet Isomorphic words som söker efter isomorfa ord till ett givet källord. Programmet och begreppet "isomorfa ord" presenterades i Isomorfa ord (Isomorphic Words).

För ett tag sedan kom en förfrågan om källkoden till programmet, varpå en CLI (Command Line Interface)-version av webb-programmet skapades. Tänkte nu att programmet likaväl kunde komma till allmänhetens fromma.

isomorphic_words.py
Programmet isomorphic_words.py är ett Pythonprogram som gör i stort sett allting som CGI-programmet gör. Syntaxen är:

     python isomorphic_words.py word exact_match language

där argumenten har följande betydelse:

* word: ordet som ska isomorferas.
* exact_match: 0 eller 1 (default 1). Om det ska göras en exakt match eller inte. Se ovanstående länkar för betydelsen av detta.
* language: Språk, eller snarare ordlista. CLI-programmet stöder endast språk "eng" som är kopplat till ordlistan /usr/dict/words (standardplaceringen i Linux). Av copyright-skäl etc lämnas inte den svenska ordlistan ut.


Exempel
Här är en exempelkörning på "ordet" (snarare strukturen) abbab, dvs att första och fjärde bokstäverna ska vara samma, och andra, tredje och femte bokstäverna ska vara samma. Ordlistan är /usr/dict/words, dvs engelska ord.


     python isomorphic_words.py abbab

Med resultatet:


Word: abbab
Word structure of 'abbab': [0, 1, 1, 0, 1]
Exact isomorphism: yes
Language: english
Print mappings: yes

beebe
2 chars: "a" -> "b"
3 chars: "b" -> "e"

esses
2 chars: "a" -> "e"
3 chars: "b" -> "s"

poopo
2 chars: "a" -> "p"
3 chars: "b" -> "o"

taata
2 chars: "a" -> "t"
3 chars: "b" -> "a"


It was 4 isomorphics words to 'abbab', with exact isomorphism: yes


Not
Om programmet används får det gärna refereras till ovanstående program och/eller till undertecknad.

Posted by hakank at 11:00 FM Posted to Språk | Systemutveckling

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

januari 02, 2009

Musikutmaning: Tolv låtar - eller snarare: N musikinspelningar

Åsk (vars blogg inte är åtkomlig i skrivande stund) kedjebloggade mig i Musikutmaning: Tolv låtar som ska säga något om mig.

Eftersom jag är en lat person (eller låt oss kallade det för Mashupinspirerad) så återanvänds mycket av det som skrevs i Musikfrågor på en liknande fråga. Notera att det alltså görs en förskjutning av frågan så den inte enbart handlar om specifika låtar utan även större musikkompileringar. I slutet blir det dock några specifika låtar, samt att det (sist) har tillförts saker som inte tidigare varit känt i vidare kretsar. Jag skippar citeringar, blockquotes eller andra anföringsindikatorer för att ange att texten är från den gamla blogganteckningen.


Följande är några av de skivor som påverkade musikintresset i en ny riktning på ett eller annat sätt. Vi får se hur många det blir. Talen inom parentes är åren då skivan inköptes.

* Nicke Lilltroll "den med ekorrar" (1967?)
Nicke Lilltroll och speciellt den där historien om ekorrar: "så kom en ekorre till och tog sig en nöt", påverkade mig troligen mycket i min uppfattning av humor. Möjligen skulle man kunna kalla detta för proto-hiphop.

Så, resten är musikaliska inspirationer.

* Ekseption: Ekseption (1969)
Den första icke-topplisteskiva som inköptes (innehöll iofs Beethovens femma i fet rock-version som blev en stor hit). Musikrollen bassist upptäcktes, här representerad av Cor Dekker. Låt:: Beethovens femma.

* Osibisa: Osibisa (1972)
Svänging world music, perfekt partymusik.

* Hoola Bandola Band: Vem kan man lita på (1972)
Här kommer så några år med svensk proggmusik. Påverkade politiskt men inte speciellt mycket musikalisk.

* Charlie Parker (1975)
Egentligen ingen speciell platta, men vi kan väl säga "The Best of Charlie Parker". Ville förstå det här med jazz och lyssnade, lyssnade, läste och lyssnade. Till slut började jag inse det geniala med denna musikstil och började själv spela slik musikstil.

* Frank Zappa: Zoot Allures (1976)
Första Zappaplattan jag lyssnade ordentligt på: Rockmusik är mer än dunkadunka, 4-ackordsmusik eller gitarryl. (Hade nu spelat elbas i melodiösa rockband något år.)

* Samla Mannas Manna: Klossa Knapitatet (1976)
Svenskar kan också spela spännande musik. Kallades emellanåt för svensk Frank Zappa-kopia, men SMM (senare *Z*) hade ofta en svensk folklighet och en något mildare form av humor än FZ.

* Jaco Pastorius: Jaco Pastorius (1976)
Pastorius var bassist i Weather Report, framförallt på den fantastiska plattan "Heavy Weather", och blev sedan en husgud. Se även Husgudar - Jaco Pastorius.

* Pat Metheney: Bright Size Life (1978?)
Började nu också lyssna på annan ECM-musik. ECM-musik kännetecknas av att det är väldigt "luftigt" arrangemang (se även kommentar nedan under JSB).

* Earth, Wind and Fire: I am (1979)
Symbolen för det allra bästa inom discofunk-musiken (något som jag gärna lyssnade på och dansade till och sedemerade även spelade). Låt:: September.

* Johan Sebastian Bach: Musikalisher Opfer (1980)
Lyssnade i stort sett endast på Bach när jag läste Douglas Hofstadters "Gödel, Escher, Bach" (det står mycket om Bach i boken, härav titeln), och blev sedan mer genuint intressad av klassisk musik. Det var troligen Bach som gjorde mig uppmärksam hur viktig tystnaden är i musiken, något som minimalisterna (Reich, Glass etc) sedan accentuerade, liksom även ECM-skivorna. (Om jag skulle ta upp musiken igen på gamla dar skulle det bli generalpaus :-)

* Level 42: Level 42 (1980)
Med Mark King, ännu en rackarns duktig bassist. Spelade "slap bass" underbart. Fast på den där konserten 81/82 i Lund var det alldeles för hög volym för att vara njutbart.

Övriga och senare inköpta plattor är mer eller mindre (logisk) utveckling av ovanstående brytpunkter. Möjligen skulle intresset för indisk (via John McLaughlin), japansk (via vem?) och senare kinesisk musik ha egna entries.

Tre låtar som inte finns med på skivorna ovan, men som betyder mycket för dig.
* Musiken från filmen Gudfadern (köpte 1972 en mandolin för att kunna spela dessa låtar samt "Duelling Banjos" (sic!) från "Den sista färden")
* Jaco Pastorius "Three Views of a Secret" ("skärgårdslåten", har många minnen till denna låt)
* Den kinesiska folksången "On the General's Orders" som används som tema i Wong Fei Hung-filmerna (dvs Hong Kong/Kung fu-filmer, Jackie Chan) såsom "Once upon a time in China N".


2009-01-02: Nytt tillägg till ovanstående:
- Rick Astley: "When I falling in love" eftersom det är en av de få låtarna jag sjungit solo offentligt och det sporrad efter en helgs sångkurs. Publiken var inte speciellt stor och hade blivit inlockad utan att veta vad de gav sig in på.
- "Somewhere" från Leonard Bernsteins West Side Story, av nästan samma orsak som ovan.

För övrigt lyssnas musik numera nästan enbast via Sveriges Radios P2 (eller på ett i jobbet delat rum kompromisslösningen P3) samt - och främst - via last.fm (ja, jag kör Linux). De "kanaler" (kluster) jag då tenderar att välja är inte speciellt förvånande:
- Osibisa
- Ennio Morricone (för filmmusik. Fast det var Nina Rota som skrev Gudfadern-musiken.)
- Earth Wind & Fire
- Jaco Pastorius
- Johan Sebastian Bach
- Level 42

Posted by hakank at 07:28 EM Posted to Musik | Comments (6)

december 29, 2008

My Constraint Programming Blog

Som antyddes i slutkommentaren till Constraint programming-nyheter samt nya MiniZinc-modeller funderades det på att skapa en engelskspråklig specialblogg om constraint programming (och relaterade paradigm).

Sagt och gjort: My Constraint Programming Blog vars första inlägg Welcome to my My Constraint Programming Blog innehåller - förutom indroducerande information - länkar till fyra nyskrivna MiniZinc-modeller.

Nya MiniZinc-modeller
Först tre modeller med uppgifter från Rosetta code.
* 99_bottles_of_beer.mzn : 99 bottles of beer
* knapsack_problem.mznKnapsack problem
* pyramid_of_numbers.mzn: Pyramid of numbers

Samt en operations research-modell
* sportsScheduling.mzn: Sports scheduling.


Noter
* Vi får helt enkelt se hur frekvent My Constraint Programming Blog uppdateras och i vilket håll den kommer att utvecklas. "Relaterade paradigm" är en vidlyftig ballong.
* Jag kommer inte här att upprepa allting som skrivs på My Constraint Programming Blog, däremot kommer uppsamlingsanteckningar skrivas med oregelbunden regelbundenhet.
* My Constraint Programming Blog kommer inte att pinga intressant.se, twingly eller andra svenska ping-portaler.
* Orsaken till den frekventa länkningen till My Constraint Programming Blog ovan (och här) är naturligtvis sökmotorrelaterad. Sorry about that.

Posted by hakank at 09:29 FM Posted to Constraint Programming

december 27, 2008

Constraint programming-nyheter samt nya MiniZinc-modeller

Här är några nyheter kring constraint programming sedan cirka oktober 2008 och inkluderar naturligtvis även en del MiniZinc-modeller.

My Constraint Programming page

För att samla ihop mina constraint programming-modeller/-referenser har skapats Constraint Programming som i stort sett endast är länkar till respektive "My XXXXXX page" (där "XXXXX" in {MiniZinc, Choco, JaCoP}).

MiniZinc

För vidare info, se My MiniZinc page.

JaCoP

För vidare info, se My JaCoP page.


Choco


  • finns nu i version 2.0.0.3

För vidare info, se My Choco page.


Minion/Tailor


Tailor är ett trevligt modelleringsspråk som översätter en Essence'-modell (en nedstrippad variant av modelleringsspråket Essence) till Minion. Tailor är implementerat i Java.

Jag har skrivit några Tailor-modeller men de är ännu inte publikt publicerade, bland annat eftersom specifikationen av Tailor/Essence' inte har varit stabil. Återkommer om detta. Kan också notera att några av mina MiniZinc-modeller är portade från just Tailor/Essence'.


Global Constraint Catalog


Global constraint catalogue uppdaterades 2008-11-15. Det var några nya constraints, framförallt geost och andra packnings-constraints.

Det gjordes då också en strukturell förändring av sajten med ett nytt URL-schema. I stället för URL-ar såsom http://www.emn.fr/x-info/sdemasse/gccat/sec4.5.html (för alldifferent_cst), så är URL-en numera http://www.emn.fr/x-info/sdemasse/gccat/Calldifferent_cst.html, dvs .../C följt av constraint-namnet. Jag har dock inte ändrat referenserna i mina MiniZinc-modeller på My MiniZinc page; däremot har nya modeller den nya URL-en.


Gecode


Gecode har inte kommit ut med någon ny officiell release sedan augusti 2008. Däremot har Gecode/flatzinc uppdaterats (SVN-versionen) några gånger för att stödja nya versioner av MiniZinc. Som tidigare sagt är Gecode/flatzinc min favorit-MiniZinc-solver.


Gecode/R


Gecode/R är ett Ruby-gränssnitt till Gecode:

Gecode/R provides access to many, but not all, of the features in Gecode 2.2.0. Gecode/R is only a modelling interface, it does not provide support for e.g. creating new propagators.

Version 1.0 kom i september. Har inte kollat in Gecode/R så mycket, vilket emellanåt förvånar mig...

Comet

Comet är ett constraint programming-system som bygger på "local search". Det har kommersialierats och en tidsbegränsad version av 1.02 finns nu att ladda ner på Dynadec.

Denna version är mer kompetent och komplett än förra, men det är nu ännu fler skillnader mot det som beskrivs i boken Constrant-based local search av Pascal Van Hentenryck, Laurent Michel.


Nya MiniZinc modeller


Sedan sist har det skrivit ett flertal nya MiniZinc-modeller (och några har uppdaterats men det - med ett undantag - noteras inte här nedan). Som vanligt finns de alla samlade på My MiniZinc page.

Referenser och oftast en kort förklaring finns att läsa i respektive modell.

Pyssel och andra matematiska förströelse



GLPK


GLPK (GNU:s Linear Programming Kit) är en open source-projekt för linjär/heltals-programmering. GLPK har bl.a. ett AMPL-liknande språk kallat MathProg varpå följande MathProg-exempel har konverterats till MiniZinc. Några av de allra största exemplen har - ännu - inte konverterats.


Global constraints


En handfull global constraints från Global constraint catalogue har skapats:

Operations research, linear programming, integer programming

Kommentaren "Williams" refererar till den mycket trevliga boken om modellering inom operations research och matematisk programmering: Model Building in Mathematical Programming (4th edition), skriven av H. Paul Williams.

Combinatorial


Övrigt



Slutord


Det har sedan länge insetts att målgruppen för ovanstående saker i svensk språkdräkt inte är så väldigt stor, varför det har tänkts att starta en separat blogg på engelska som endast handlar om constraint programming och relaterade paradigm såsom nyheter samt nyskrivna modeller. Mer om detta senare.

Posted by hakank at 10:51 EM Posted to Constraint Programming | Comments (4)

oktober 22, 2008

Complete Rewrite: Intressant blogg om databaser och systemutveckling

Complete Rewrite är en ny intressant blogg om Personal viewpoints on database systems and computer programming.

Författaren, Jesper Larsson, presenterar sig så här:

Passionate programmer since I got my first programmable calculator in 1985, my work developing search engine and data management software, as well as my own understanding of database systems and software design, at Apptus Technologies has taken me quite some distance from my background as a practical algorithm theoretician with Ph.D. on suffix trees and data compression, and allowed me to develop insights and opinions on such diverse areas as object-oriented design, the relational data model, transactional systems, development processes, and logic.

Till dags dato har skrivits två (långa) artiklar:

* Why the Database Masters Fail Us

There is hardly any field in computing more plagued by religious wars than database systems. For nearly 40 years, the battle has raged between various architechtures, occasionally with some combattants replaced – or at least renamed. Still, it seems that we are further away than ever from a sort of database that we can be satisfied with. (I am not going into the details of the problems right now, that will be a subject of future posts. But if you are in the business I am sure you are familiar with some of them.)
...


* Text search and relational model

It is particularly common to write off the relational model in the text search field. You can frequently hear people say that things like the relational model is not suitable for capturing the structure of text, or referring to text by the peculiar term “unstructured data”. Some writers talk about combining text and relational data, as if there were a contradiction. As if relational data were a special kind of data. A more correct account, like that of Curt Monash, is to simply note that text does not work very well with the architecture of mainstream relational products – which is true.
...
Since text search is one of my top areas of expertise, I hope I can explain to you why the relational model is perfectly capable of capturing the structure of text. I'll start at the very bottom, explaining what text search really is.

Eventuellt bör nämnas att jag känner Jesper, han är en både smart och klok (samt trevlig) person.

Posted by hakank at 06:36 EM Posted to Blogging | Systemutveckling | Comments (3)