« juli 2008 | Main | september 2008 »

augusti 30, 2008

Ubiquity 0.1 - kommandoradsfunktionalitet i Firefox

Den senaste veckan har det pratats en del om version 0.1 av Firefox-tillägget Ubiquity från Mozilla Labs. Här är några kommentarer efter en första sittning.

Och det är helläckert!

Med en enkel tangentbordskombination (Alt-mellanslag i min Firefox 3.0 + Mandriva Linux) får man upp en "kommandorad" där man kan skriva in kommandon. Detta kallas för "Ubiq", vilket på svenska torde bli "att ubiqa" (eller möjligen "att ubika").

En mycket trevlig introduktion av funktionaliteten, inklusive en kort video, görs i Introducing Ubiquity.


Exempel


Här är några enkla exempel på hur man kan använda Ubiquity. Fler - och mer avancerade - exempel finns i User Tutorial.

google

google Ubiquity

gör en googlesökning på sökfrasen "Ubiquity".

this
Stöter man på en fras (t.ex. "constraint programming") kan man markera den och sedan ubiqa med


wiki this

varpå en Wiki-sökning görs. this avser det markerade området:. Man skriver alltså this.


translate
Markera en engelsk fras och ubiqa


translate this from english to swedish

Översättningen visas redan i previewfältet så man behöver inte ens exekvera kommandot. Riktigt trevligt.

Den finns stöd för en massa andra sökmotorer etc. såsom Yahoo, IMDB etc.

Andra kommandon som är bra att känna till:

* command-list: Visar vilka kommandon som finns tillgängliga för tillfället i browsern, inklusive egentillverkade (se nästa avsnitt).


Skriva egna Ubiquity-kommandon


Naturligtvis vill man utöka reportoaren med egna Ubiquity-kommandon som skrivs i Javascript. Här är två enkla exempel som jag personligen kommer att använda.

Instruktioner hur man skapar egna kommandon finns i Author Tutorial, där det finns mycket mer avancerade saker än nedanstående.

För att testa kommandona använder man en webbaserad kommandoeditor via kommandot command-editor, där man skriver in kommandona. Man behöver inte göra något speciellt mer än skriva (eller klistra in) koden, saker sker automatiskt i bakgrunden.

Det första exemplet är en sökning på Bokus och den andra en sökning på knuff.se. Det är inte rocket science, men funkar. (Jag har inte laborerat med mer de avancerade preview-funktionerna speciellt mycket.)


makeSearchCommand({
name: "bokus",
url: "http://www.bokus.com/cgi-bin/book_search.cgi?FAST={QUERY}",
icon: "http://www.bokus.com/favicon.ico",
description: "Searches Bokus for your books, movies, and games.",
preview: function(pBlock, directObj) {
if (directObj.text)
pBlock.innerHtml = "Searches Bokus for " + directObj.text;
else
pBlock.innerHTML = "Searches Bokus for the given words.";
}
});

makeSearchCommand({
name: "knuff",
url: "http://knuff.se/q/{QUERY}",
icon: "http://knuff.se/favicon.ico",
description: "Searches knuff.se for phrases from the swedish blogosphere.",
preview: function(pBlock, directObj) {
if (directObj.text)
pBlock.innerHtml = "Searches knuff.se for " + directObj.text;
else
pBlock.innerHTML = "Searches knuff.se for the given words.";
}

});

Det enda man egentligen behöver veta för att göra liknande kommandon är sökurlen och sedan byta ut sökfrasen med {QUERY}.

Man kan nu testa detta med


bokus constraint programming

eller för att söka på ett ISBN som man ser hos sin favoritblogg: 9780140286809 . Märk detta och skriv


bokus this

(Boken har inget med Ubiquity att göra - mer än möjligen indirekt genom associationer.)



knuff Ubiquity

som ger följande resultat.


För mer persistent användning av kommandona, för att ge sina medmänniskor tillgång till dem - och eventuellt "prenumerera" för att få automatiska uppdateringar - bör man publicera koden någonstans på webben. Läs i Author Tutorial hur man gör detta.

Jag har dock inte publicerat någon sådan sida. Eventuellt kommer det senare.


Säkerhet


Genom Ubiquity får användaren tillgång till mycket avancerade funktioner i webbläsaren. Tyvärr kan (och kommer att) elaka människor utnyttja detta för sina elakheter. Det finns för närvarande (i Ubiquity 0.1) ett visst skydd genom att man man får se en stor fet varningsskylt innan man börjar prenumerera, men det är naturligtvis inte tillräckligt. Det talar om en framtida "web of trust" där användare kan rekommendera/varna för en speciell prenumeration. Vi får väl helt enkelt se...

Detta sagt, testa gärna funktionaliteten, men prenumerera inte på något som du inte känner till/litar på.


Några andra kommentarer


* Jag har inte fått email eller add-to-calendar (stödjer endast Googles gmail/calendar) att fungera ordentligt.

* De speciella internationella tecknen (framförallt "å", "ä" och "ö") stökade i kommandot translate, möjligen är det något konstigt i min miljö...

* Vissa kommandon, t.ex. translate skriver in texten där (mus)markören befinner sig. Vad jag vet finns det inget sätt att ångra detta utan man måste ladda om sidan igen för att ta bort texten. Jag trodde att undo skulle göra det, men icke.

* Detta är version 0.1 och mycket kommer säkerligen att ändras...

* För övrigt påminner detta en del om programmeringsspråket/-miljön Rebol.


Länkar


Här är lite länkar om Ubiquity (varav några redan nämnts):

* Wiki: Ubiquity
Introducing Ubiquity
* Google-gruppen ubiquity-firefox
* User Tutorial
* Author Tutorial
* Forum

Posted by hakank at 10:18 EM Posted to Program | Sökmotorer | Comments (4)

augusti 23, 2008

Nästan 36 modeller med villkorsprogrammering (constraint programming) i MiniZinc

(Språklig not: Av någon anledning tycker jag inte riktigt om namnet "villkorsprogrammering" utan använder hellre det engelska "constraint programming", men det svenska namnet är vedertaget framförallt i vissa utbildningscentra så det måste nämnas emellanåt.)


Sedan sist har fler MiniZinc-modeller skapats. Det finns nu över 360 .mzn-filer - modeller och datafiler - på My MiniZinc page och det känns därför som rätt tillfälle att rensa lite från inkorgen, närmare bestämt nedanstående nästan 36 modeller. Grupperingen här nedan är inte riktigt samma som på MiniZinc-sidan.

Referenser till problemformulering/originalmodell/inspiration finns som vanligt i respektive modell.


Personliga favoriter


Några personliga favoriter av nedanstående är:
* Survo puzzle. Ett kul litet pyssel som är som en blanding av magiska fyrkanter och diskret tomografi. (Det finns även en JaCoP modell: SurvoPuzzle.java)
* Nadel's construction problem, där "soft constraints" används, dvs där det tillåts att vissa villkor inte uppfylls och man minimerar över antalet som inte uppfylls. Detta eftersom denna modell inte ger några resultat om man kräver att alla villkor ska vara uppfyllda (vilket naturligtvis kan innebära att modellen inte är helt korrekt). Tyvärr har jag inte hittat något facit...

Modeller

Kombinatorik/global constraints
* Dominating Set
* Graph Degree Sequence
* Stretch circuit
* Subsequence sum


Operations research
*
Data Envelopment Analysis (DEA) model. (För tillfället är det endast ECLiPSe's eplex-solver som klarar detta.)


Enigma-pyssel
*
Enigma eighteen
*
Five fives
* Eight times
* Eight times 2, alternativ modell
* Planets


Dell Logic Puzzles
Logiska problem från brownbuffalo.sourceforge.net.
* Tunapalooza
* A round of golf
* Arch friends
* Four islands
* Breaking news
* Baby sitting
* Lecture series


100 dörrars-problemet
Problemformulering t.ex. hos Rosetta code.
* 100 doors problem, unoptimized (version 1)
* 100 doors problem, unoptimized (version 2)
* 100 doors problem, optimized, using set representation
* 100 doors problem, optimized, using array representation


Andra pyssel
* Clock triplets
* Franklin's 8x8 magic square
* Magic sequence, version 3 (en av flera varianter)
* Murder: Ett mord har begåtts ..(logiskt pysse)
* Number Generation, generalisering av Devil's Word (devils_word.mzn respektive Devil's word CGI-program).
* Self Referential Quiz
* Survo puzzle

Två exempel från Constraint Processing skriven av Rina Dechter
* Nadel's construction problem, sidan 5
* Scheduling speakers, sidan 72


Två exempel från theorem proving (automated reasoning)
* Jobs puzzle
* Who killed Agatha?


Övriga modeller
* Family, familjeträd, ett standard Prologprogram formulerat i MiniZinc
* ISBN: en etyd i konstruktion av ISBN-13 (med kontrollsiffra)

Posted by hakank at 08:35 FM Posted to

augusti 19, 2008

Digital grusväg 1/2008 ute!

Via ett personligt epost-meddelande erhölls den glädjande nyheten att Digital Grusväg (Aperiodisk tidskrift) numro 1 anno 2008 är officiell. För att citera (delar av relevanta) delar av mailet:


I detta nummer...Vad är det i mjölken? Har sista bussen gått?

Samtidigt kan passas på att tipsas om Nerdlunchers (kreativitetens högborg på nätet, som lyckats lokalisera tillståndet av total förvirring, vilket dock måste sägas inte råder å nämnda nätplats), speciellt Wikin där Hr. Grusväg emellanåt och från tid till annan smular sitt oefterlikneliga grus.

Tidigare här på bloggen diskussioner diskuterar sådant som namnets ("Digital Grusväg"s) tillkommande (ehuru länkar är - som vanligt i denna av regn småningom fyllda spindelvävsvärld - inaktuella) .

Posted by hakank at 07:32 EM Posted to Diverse

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

augusti 16, 2008

En vecka med Asus Eee Pc 900

För en vecka sedan (lördags lite i 12:00) inköptes en Asus Eee PC 900. Det gjordes efter att ha följt Tommy k Johansson och hans eminenta rapportering kring dessa modeller. (Jag hade sett lillebror 700 av en slump för en månad sedan och började därför kolla in dessa modeller.)

I och för sig skulle jag hellre vilja ha en 901:a - som framförallt har bättre batteritid än 900 - men de inköpsställen i Malmö som besöktes svarade följande på frågan när modellen skulle komma in och vad den skulle kosta:
* slutet på september och kommer att kosta 4000
* vi vet inte
* har ingen aning

Så, tillbaka till 900:an som med anledning av ovanstående således inköptes.

Det är en trevlig lite sak på knappt kilot inklusive batteri. Förvånansvärt mycket går in på den lilla skärmen så det är inga problem att kolla vad som händer i *sfären på Bloglines eller vilka TV-program som går nu, eller läsa mail. Det är ju så jobbigt att gå de drygt 10 metrarna till "stordatorn"

Men det egentliga skälet till inköpet är att jag länge önskat mig en liten "programmeringsdator" där jag kan fortsätta mina (programmerings)skov under reklamavbrott, på bussen eller annorstädes i naturen (där i naturen inberäknas sovrummet). 16 gigg (varav 12 är ledigt) är väldigt mycket eftersom jag inte planerar att dra ner kilovis med filmer eller musik på maskinen.

Efter att ha läst igenom manualen och samtidigt laddat batteriet (och samtidigt tittat på Sverige-matchen i damfotboll) gjordes första surfandet. Nätverket funkade helt enkelt genom att bara sätta i nätverkskabeln vilket överraskade posititvt.

Men efter några minuters surfande och lekande med filmkameran och patiensspelande (en alldeles utmärkt träning för att lära sig musplattan) och OpenOfficande var det: "OK, ge mig nu en prompt.. Det är i ju Linux vi pratar om." Skalet finns via Filhanteraren, /bin/bash (tyvärr finns inte zsh installerad default). ssh:ade in till huvuddator utan problem och packade ihop det som skulle kopieras.

Några spridda kommentarer kring detta:
- användarkontot är /home/users
- "|" (pipe-tecknet) finns via shift + Alt Gr + Z
- CTRL-ALT-t ger en terminal (det finns dock ingen fin ikon) med där får man inte skalet varmed man kan kopiera text med.

De flesta program som testades att kopiera rakt av från Mandriva-distributionen funkade rakt av, t.ex. Java, MiniZinc och lite annat. Men inte Haskells Hugs 98, där jag får "Aritmetiskt räknefel" vid start av hugs. Tyvärr finns ingen gcc installerad för att kompilera källkoden och jag vågar ännu inte att installera det eftersom det har antytts i forum etc att sådant kan bli problem (och Hugs-paketen vågar jag inte heller att installera av samma skäl). Fast det är naturligtvis Emacs som ska installeras först;; vim finns men det blir endast konstiga tecken när man i insert-läge trycker på piltangenterna (ja, det är så jag navigerar och det är möjligen en konsekvens av att vim körs i bash).

Det finns alltså en hel del att göra och lära sig. Och sådant är alltid roligt.

Några andra kommentarer:
- kul med musplattan: Man scrollar genom att föra två fingrar upp/ned, och man zoomar in/ut genom att placera två fingrar i mitten på plattan och sära dem (och vice versa).
- jag är alltså mycket nöjd med maskinen
- batteriet blir varmt så om man - tvärtemot varningen som finns i manualen - vill ha datorn i knät bör man ha en extra skiva som skydd för kläder (eller skinn nu på sommaren).
- ett kilo dator känns faktiskt mer än ett kilo socker i ryggsäcken.

Se även
Här är några sajter som har en viss myckethet av information om Asusarna:

Tommy j Johanssons skriverier
IDG Allt om Asus Eee PC
All about Asus EEE PC…
Eee User forum
Asus Eee News, Mods, and Hacks

Posted by hakank at 09:59 FM Posted to Diverse | Comments (8)