juli 04, 2008
Martin Chlond's Integer Programming Puzzles i MiniZinc
Som tidigare nämnts är Puzzles - Integer Programming in Recreational Mathematics en mycket trevlig samling pyssel skapad av Martin Chlond. De flesta problemen är klassiker inom området (recreational mathematics) och flera används som paradigmproblem i constraint programming eller integer programming.
I april skrevs MiniZinc-modeller för samtliga problem men jag har inte kommit loss att hyfsa till dem. Förrän nu. Samliga 48 problem har nu gåtts igenom så att de har en enhetlig struktur, kommentarer är på engelska etc.
Förutom MiniZinc-modellen nedan finns även en länk till Martin Chlonds lösning av problemet (oftast skrivet som en XPress Model, men de allra sista är i AMPL). MiniZinc-modellerna är i stort sett en konvertering av Chlonds modell. I några fall har flyttalsrepresentationer omvandlats till heltalsrepresentationer.
Nedanstående listning finns även på min MiniZinc-sida, men det blir en bättre bäring om de även listas här.
Martin Chlond's Integer Programming Puzzles
The collection is separated in four sections where the problems is presented:* Integer Programming Puzzles section 1
* Integer Programming Puzzles section 2
* Integer Programming Puzzles section 3
* Integer Programming Puzzles section 4
Problems: Integer Programming Puzzles section 1
Solutions:
Twelve draughts puzzle (Chlond's solution)
Description : Twelve draughts puzzle Source : Boris Kordemsky - The Moscow Puzzles (P36)
Coin puzzle
(Chlond's solution)
Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)
Egg basket puzzle
(Chlond's solution)
Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)
Evens puzzle
(Chlond's solution)
Description : Evens puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P8)
Fifty puzzle
(Chlond's solution)
Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)
Honey division puzzle
(Chlond's solution)
Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics
Wine cask puzzle
(Chlond's solution)
Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)
Knight domination puzzle - all squares threatened
(Chlond's solution)
Description : Knight domination puzzle - all squares threatened
Source : M Kraitchik - Mathematical Recreations (P256)
Mango puzzle
(Chlond's solution)
Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)
Remainder puzzle
(Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)
5 X 5 puzzle
(Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown
Lights on puzzle
(Chlond's solution)
Description : Lights on puzzle
Source : Unknown
Problems: Integer Programming Puzzles section 2
Solutions:
Clarke's tobacconist
(Chlond's solution)
Description : Clarke's tobacconist
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.
Tommy's Birthday Coins
(Chlond's solution)
Description : Tommy's Birthday Coins
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.
Lewis Carroll coin puzzle
(Chlond's solution)
Description : Lewis Carroll coin puzzle
Source : Wakeling, E., (1995), Rediscovered Lewis Carroll Puzzles, Dover.
Dudeney's tea mixing problem
(Chlond's solution)
Description : Dudeney's tea mixing problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Jive turkeys
(Chlond's solution)
Description : Jive turkeys
Source : rec.puzzles
Public School Problem
(Chlond's solution)
Description : Public School Problem
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.
Dudeney's bishop placement problem I
(Chlond's solution)
Description : Dudeney's bishop placement problem I
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Dudeney's bishop placement problem II
(Chlond's solution)
Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Kraitchik's queen placement problem
(Chlond's solution)
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.
Schuh's queen placement problem
(Chlond's solution)
Description : Schuh's queen placement problem
Source : Schuh, F., (1943), Wonderlijke Problemen;
Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.
Dudeney's queen placement problem
(Chlond's solution)
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Joshua and his rats
(Chlond's solution)
Description : Joshua and his rats
Source : Sole, T., (1988), The Ticket to Heaven, Penguin Books
Problems: Integer Programming Puzzles section 3
Solutions:
The Abbott's Puzzle
(Chlond's solution)
Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
The Abbott's Window
(Chlond's solution)
Description : The Abbott's Window
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
The First Trial
(Chlond's solution)
Description : The First Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Second Trial
(Chlond's solution)
Description : The Second Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Third Trial
(Chlond's solution)
Description : The Third Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Fourth Trial
(Chlond's solution)
Description : The Fourth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Fifth Trial
(Chlond's solution)
Description : The Fifth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The Sixth Trial
(Chlond's solution)
Description : The Sixth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
Werewolves II
(Chlond's solution)
Description : Werewolves II
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall
Werewolves IV
(Chlond's solution)
Description : Werewolves IV
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall
Earthlings
(Chlond's solution)
Description : Earthlings
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling
Equal Vision
(Chlond's solution)
Description : Equal Vision
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling
Problems: Integer Programming Puzzles section 4
Solutions:
On the road
(Chlond's solution)
Description : On the road
Source : Poniachik, J. & L, (1998), Hard-to-solve Brainteasers, Sterling
The Riddle of the Pilgrims
(Chlond's solution)
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.
The Logical Labyrinth
(Chlond's solution)
Description : The Logical Labyrinth
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press
The gentle art of stamp-licking
(Chlond's solution)
Description : The gentle art of stamp-licking
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
The crowded board
(Chlond's solution)
Description : The crowded board
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
Non-dominating queens problem
(Chlond's solution)
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt
Enigma
(Chlond's solution)
Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani
Price change puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations (p 33-35), Dover
Book buy puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover
Shopping puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover
Book discount problem
(Chlond's solution)
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling
Seven 11 (Chlond's solution)
Source: alt.math.recreational
Posted by hakank at 07:09 FM Posted to Constraint Programming | Pyssel | Comments (0)
juni 29, 2008
Gruppteoretisk lösning av M12 puzzle i GAP
I Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc) presenterades det gruppteoretiska pysslet M12, då med en lösning i MiniZinc (modellen M12.mzn).
När jag läste om M12 tänkte jag att det skulle vara skoj med även en gruppteoretisk lösning eftersom det är ett gruppteoretiskt problem. En sådan lösning har nu gjorts med hjälp av det abstrakta algebraiska systemet GAP. Numera finns GAP även med i distributionen av det öppna matematiska (och mycket trevliga) systemet Sage.
Uppdatering
Efter lite funderande kom jag på en bättre lösning. I stället för att ändra en massa i denna text skrev jag en ny: Gruppteoretisk lösning av M12 puzzle i GAP - take 2, vilken se.
Kort beskrivning av M12
Som tidigare beskrivits går M12-pysslet ut på att man har en sekvens av 12 siffror i en härlig oordning och man ska med hjälp av två operationer återställa sekvensen till 1,2,3,4,5,6,7,8,9,10,11,12. Operationerna är:
Merge: [1, 12, 2, 11,3, 10, 4, 9, 5, 8, 6, 7] blir [1,2,3,4,5,6,7,8,9,10,11,12].
Inverse: Vänder listan om, [1,2,3,4,5,6,7,8,9,10,11,12] blir [12,11,10,9,8,7,6,5,4,3,2,1]. Not, jag kallar operationen (av historiska skäl) för Reverse här nedan.
GAP-program
Här är GAP-programmet (M12_gap.txt). Resultat från ett kommando eller kommentar skrivs efter "#".
Först definierar vi operatorerna, dvs generatorerna i gruppen. Här används PermList som tar en lista och skapar en permutationscykel.
#
# Solving the M12 for a specific sequence
#
#
# Define the operators
#
# Reverse (Inverse)
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
# (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)
# Merge
merge := PermList([1,12,2,11,3,10,4,9,5,8,6,7]);
# (2,12,7,4,11,6,10,8,9,5,3)
Skapa gruppen g och gör några tester.
# Create the group
g:=Group([reverse, merge]);
# Group([ (1,12)(2,11)(3,10)(4,9)(5,8)(6,7), (2,3,5,9,8,10,6,11,4,7,12) ])
# Which group is it?
StructureDescription(g);
# "M12"
Size(g);
# 95040
Bra, det är alltså gruppen M12, dvs Mathieu-grupp av ordningen 12. Notera att det finns ett inbyggt kommando för att skapa en Mathieugrupp (MathieuGroup), men den har inte de generatorer som vil ska använda, alltså rullar vi vår egen.
Nu börjar det roliga. Låt oss som exempel ta följande sekvens som nyss skapats av M12-programmet.
#
# Create the puzzle to solve
#
puzzle:=[4, 5, 11, 1, 9, 6, 3, 10, 2, 7, 12, 8];;
För att få reda på lösningen görs en "faktorisering", med hjälp av funktionen Factorization.
Factorization(g, PermList(puzzle)^-1);
# x1*x2^2*x1*x2^-5*x1*x2^-5
Här har vi en lösning som ska tolkas som operationer i pysslet:
x1*x2^2*x1*x2^-5*x1*x2^-5
x1 betyder den första generatorn (dvs Reverse/Inverse) och x2 är Merge.
Det finns två saker att tänka på här:
- man ska läsa sekvensen baklänges
- alla operationer med negativ exponent måste konverteras till en positiv exponent. Det görs med en enkel subtraktion: x2^-5 innebär samma sak som x2^(11-5) = x2^6
Om vi översätter enligt ovanstående två regler blir det:
x2^6 x1 x2^6 x1 x2^2 x1
Så, uttolkat i samma form som M12-applikationen blir lösningen följande. Tänk på att vi arbetar med lösningen bakifrån och att x1 är I och x2 är M:
M6 I M6 I M2 I
Detta är en lösning med 6+1+6+1+2+1 = 17 steg.
En variant
Förutom Factorization finns det en annan metod, och det är den som generellt rekommenderas för att göra denna typ av "faktoriseringar". Tyvärr tenderar den att generera längre lösningar än med Factorization.
#
# This is the recommended function for factorizations, but it gives longer
# solutions (strings) than Factorization.
#
#
# Create names to identify the operations
#
M:=g.2; R:=g.1;
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);
#
# Now, solve the puzzle
#
PreImagesRepresentative(hom,PermList(puzzle)^-1);
# M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2
Lösningen är alltså:
M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2
Notera att R^-1 ska tolkas som en Inverse-operation.
Ovanstående motsvarar följande M12-operationer:
M2 I M10 I M8 I M3 I M I M4 I M8
Detta är en lösning på 2 + 1 + 10 + 1 + 8 + 1 + 3 + 1 + 1 + 1 + 4 + 1 + 8 = 42 steg, vilket är mycket längre än Factorization-approachen.
Man bör notera att dessa faktoriseringar är optimerade att få så små exponenter som möjligt oavsett om det är positiva eller negativa exponenter. Vi är dock endast intresserade av positiva exponenter och lider därför av denna optimering.
Om man adderar exponenterna utan tecken, ger Factorization i alla fall en enklare lösning.
Factorization: x1*x2^2*x1*x2^-5*x1*x2^-5 = 1 + 2 + 1+ 5 +1+ 5 = 15 steg.
PreImagesRepresentative: M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2 = 3 + 1 + 4 + 1 + 1+ 3+ 1 + 3+ 1+ 1 + 1 + 2 = 22 steg.
Båda dessa faktoriseringar går mycket snabbt, typ någon sekund eller så.
Jämförelse med MiniZinc-lösningen
Jag testade att köra pysslet med MiniZinc-modellen M12.mzn. Den tar väldigt lång tid (typ 10-tals minuter) och ger följande lösning på 18 steg, dvs något sämre än Factorization-varianten. Operatorn 1 motsvarar Merge och operatorn 2 motsvarar Inverse.
2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2
dvs operationerna: R M6 R M2 R M R M3 R M
Så här ser sekvensen ut för respektive operation. Siffran till vänster är operationen. Första raden är ursprungssekvensen och är endast med för presentationens skull.
0: 4 5 11 1 9 6 3 10 2 7 12 8
2: 8 12 7 2 10 3 6 9 1 11 5 4
1: 8 7 10 6 1 5 4 11 9 3 2 12
1: 8 10 1 4 9 2 12 3 11 5 6 7
1: 8 1 9 12 11 6 7 5 3 2 4 10
1: 8 9 11 7 3 4 10 2 5 6 12 1
1: 8 11 3 10 5 12 1 6 2 4 7 9
1: 8 3 5 1 2 7 9 4 6 12 10 11
2: 11 10 12 6 4 9 7 2 1 5 3 8
1: 11 12 4 7 1 3 8 5 2 9 6 10
1: 11 4 1 8 2 6 10 9 5 3 7 12
2: 12 7 3 5 9 10 6 2 8 1 4 11
1: 12 3 9 6 8 4 11 1 2 10 5 7
2: 7 5 10 2 1 11 4 8 6 9 3 12
1: 7 10 1 4 6 3 12 9 8 11 2 5
1: 7 1 6 12 8 2 5 11 9 3 4 10
1: 7 6 8 5 9 4 10 3 11 2 12 1
2: 1 12 2 11 3 10 4 9 5 8 6 7
1: 1 2 3 4 5 6 7 8 9 10 11 12 % Solution!
Posted by hakank at 08:25 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)
juni 24, 2008
Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc)
Här är några matematiska / logiska pyssel med lösningar i MiniZinc.
n-puzzle (8-puzzle, 15-puzzle)
n-puzzle (8-puzzle, 15-puzzle) är ett synnerligen standardpyssel som ofta används för att testa algoritmer och liknande inom AI eller för att träna hjärnan. Det går ut på att flytta en blank bricka runt i en matris så att siffrorna återställs till en given ordning (oftast 1..15 eller 1..8) och den blanka ska vara i den nedersta högra rutan .Min lösning på detta problem finns i n_puzzle.mzn och får väl anses vara ett pseudo-härke eftersom det använder en del trixerier såsom dummy-drag (kring rad 111).
Här är exempel på 8-puzzle, dvs en matris med 3x3. Talet 9 representerar den blanka rutan som flyttas runt.
Definiera först utgångspositionen:
puzzle =
[|2,3,6,
|1,4,9,
|7,5,8|];
Resultatet är (med num_sols = 8, dvs antal olika drag):
puzzle:
2 3 6
1 4 9
7 5 8
...
0: 2 3 6 1 4 9 7 5 8
0: 2 3 9 1 4 6 7 5 8
0: 2 9 3 1 4 6 7 5 8
0: 9 2 3 1 4 6 7 5 8
0: 1 2 3 9 4 6 7 5 8
0: 1 2 3 4 9 6 7 5 8
0: 1 2 3 4 5 6 7 9 8
1: 1 2 3 4 5 6 7 8 9
moves:
0 6
6 3
3 2
2 1
1 4
4 5
5 8
8 9
Lösningen finns i andra kolumnen i moves, dvs
6 3 2 1 4 5 8 9
Där 6 betyder att blank (9) och brickan som finns i position 6 ska byta plats, 3 att 9 och brickan i position 3 ska byta plats etc.
Raderna med matrisen visar hur draget påverkar matrisen (som en vektor). Talet framför raden (0 eller 1) visar om lösningen är gjort (1) eller inte (0).
M12
M12 är ett pyssel inspirerat av spel såsom ovanstående 15-pyssel och Rubiks kub (och dess släktingar). Skaparna av M12, gor Kriz and Paul Siegel, beskrev det Scientific American-artikeln Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups" för någon vecka sedan:
What we wanted for educational purposes was an entertaining way to develop people’s intuitions for groups entirely unlike the ones represented by the cube. And what we wanted as puzzle fans was a new set of puzzles whose solutions require a substantially different strategy from that of Rubik’s Cube and its relatives. So we made the natural connection: we were able to develop three new puzzles based on groups known as sporadic simple groups, whose properties are both remarkable and not well known except to specialists. Happily, the experiences of our colleagues show that anyone who can learn to solve Rubik’s Cube can gain an equally substantial understanding of these sporadic simple groups by doing our puzzles. But more, these puzzles are challenging in the sense that they do not yield to the methods that work with Rubik’s Cube—and we think they are a lot of fun. Readers who want to get their hands on them right away can download them.
Kortfattad beskrivning av M12
Talen 1 till och med 12 används, och de blandas slumpmässigt (fast inte hur som helst). Själva pysslet går ut på att man ska få tillbaka ursprungspositionen 1..12 med hjälp av endast två operationer:
- invert: placera talen i omvänd ordning, dvs 1..12 blir 12..1.
- merge: detta är en variant av "perfekt blandning". Den beskrivs som is a "card shuffle" best understood by trying it out, och kan väl enklast förklaras med följande: Om konfigurationen är
a) 1 12 2 11 3 10 4 9 5 8 6 7
och man gör en merge blir resultatet
b) 1 2 3 4 5 6 7 8 9 10 11 12
dvs man får då lösningspositionen.
Lösning i MiniZinc
I M12.mzn finns en modell för att lösa M12, dvs det enklaste av de tre problemen. För mer avancerade problemkonfigurationer, säg antal operationer > 24, tar det rätt lång tid.
Exempel:
Här är ett enkelt problem:
init = [7,1,8,9,12,5,3,10,4,11,6,2]
Lösning:
init: [7, 1, 8, 9, 12, 5, 3, 10, 4, 11, 6, 2]
check: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
check_ix: 10
operations: [0, 1, 1, 1, 2, 1, 1, 1, 1, 2, 0, 0]
0: 7 1 8 9 12 5 3 10 4 11 6 2
1: 7 8 12 3 4 6 2 11 10 5 9 1
1: 7 12 4 2 10 9 1 5 11 6 3 8
1: 7 4 10 1 11 3 8 6 5 9 2 12
2: 12 2 9 5 6 8 3 11 1 10 4 7
1: 12 9 6 3 1 4 7 10 11 8 5 2
1: 12 6 1 7 11 5 2 8 10 4 3 9
1: 12 1 11 2 10 3 9 4 8 5 7 6
1: 12 11 10 9 8 7 6 5 4 3 2 1
2: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12
Operationerna som används är kodade enligt:
0: gör inget (samma som föregående rad) . Not: Första raden är en dummy operation.
1: merge (M)
2: inverse (I)
Lösningen här är alltså: MMMIMMMMI .
Tyvärr klarar MiniZinc inte av att presentera strängar därav de numeriska värdena.
Tips: Antalet rader i lösningen (rows) påverkar väldigt mycket hur lång tid det tar. Börja därför med ett lägre värde (t.ex. 12) och öka detta försiktigt.
Not: Modellen är till strukturen rätt lik modellen för n-pysslet (se ovan) och det är ingen slump. (Jag skrev dock M12.mzn före n_puzzle.mzn)
Mer info om M12
* För att spela M12 (och dess storebröder) online kan man gå hit.
* Spelen finns även att tillgå som Windows-program från en av författarnas hemsida Igor Kriz. Se README för mer info.
* God Plays Dice skrev lite om detta i Rubik's deck of cards?.
* Wikipedia om den gruppteoretiska bakgrunden: Sporadic group.
SET puzzle
Tommy på Användbart skrev om dessa problem för några dagar sedan. Problemet påminner om vissa typer av IQ-test där man ska lista ut vilka saker som hör ihop med andra, och tycker man sådana problem är intressanta är SET värt att bita i.
När Tommy berättade om detta på senaste bloggträffen var en av mina första reaktioner att börja med att skapa en modell för problemet. Vilket sålunda har gjorts.
Läs mer om SET, med regler, tips etc:
* Wikipedia Set_(game), som väldigt korfattat beskriver problemet så här
Different "categories":
* They all have the same number , or they have three different numbers.
* They all have the same symbol , or they have three different symbols.
* They all have the same shading, or they have three different shadings.
* They all have the same color , or they have three different colors.
* New York Times har ett pyssel varje dag, och här förklaras lite mer.
* Ett lärt paper om SET: Benjamin Lent Davis and Diane Maclagan, The Card Game Set (PDF).
Huvuddelen av MiniZinc-modellen visas här med kommentarer. Den fullständiga modellen finns i set_puzzle.mzn.
include "globals.mzn";
int: n = 9; % number of items
% int: n = 12; % number of items
int: num_sets = 4; % number of Sets to find
% int: num_sets = 5; % number of Sets to find
int: m = 3; % number of items in a Set
int: num_flavours = 3; % number of flavours of the attributes
int: num_attributes = 4; % number of different attributes in each item
array[1..n, 1..num_attributes] of var 1..num_flavours: puzzle;
% decision variable: the sets to find
array[1..num_sets] of var set of 1..n: x;
% solve satisfy;
solve :: set_search(x, "input_order", "indomain_min", "complete") satisfy;
constraint
% exact three items in each set
forall(i in 1..num_sets) (
card(x[i]) = m
)
/\ % must be different sets
all_different(x)
/\
forall(i in 1..num_sets) (
% identify the items in this set
forall(a in 1..num_attributes) (
let {
array[1..m] of var 1..n: arr
}
in
% assign the set
forall(j in 1..m) (
arr[j] in x[i]
)
/\ % symmetry breaking: all different and sorted
forall(j in 1..m-1) (
arr[j] < arr[j+1]
)
/\
(
% EITHER all are same with regard to this attribute
forall(j in 1..m-1) (
puzzle[arr[j],a] = puzzle[arr[j+1],a]
)
\/
% OR all are different with regard to this attribute
forall(i, j in 1..m where i != j) (
puzzle[arr[i],a] != puzzle[arr[j],a]
)
)
) % end forall 1..num_attributes
) % end forall 1..num_sets
% /\ % Symmetry breaking: order the sets
% % Only works for flatzinc version >= 0.8
% increasing(x)
;
output [
show(x)
]
Idealet vore naturligtvis att man kunde förevisa bilden för programmet och sedan löstes problemet, men så långt har jag inte kommit. Istället används en enkel kodning från bilden med de ingående rutornas attribut till en matris av tal. Den kodning som används är följande, dvs det tal som visas inom parentes.
Symbols: Each card has ovals (1), squiggles (2), or diamonds (3) on it;
Color : The symbols are red (1), green (2), or purple (3);
Number : Each card has one (1), two (2), or three (3) symbols on it;
Shading: The symbols are solid (1), striped (2), or open (3).
Det problem som Tommy visar hos sig kodas så här:
puzzle =
array2d(1..n, 1..num_attributes,
[2,1,2,1,
3,3,2,1,
1,2,2,2,
1,2,2,1,
3,2,2,1,
3,1,2,1,
3,2,2,2,
2,3,2,2,
1,2,2,3,
]);
Det finns en unik lösning till detta problem (modulo symmetrier), nämligen dessa fyra mängder
{1, 2, 4}
{2, 5 6}
{3, 4, 9}
{6, 8, 9}
Posted by hakank at 09:07 FM Posted to Constraint Programming | Pyssel | Comments (0)
juni 05, 2008
Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips
Mats Andersson har tidigare haft flera roliga tävlingar. Inför fotbolls-VM 2006 var det en tävling där man skulle gissa resultat i matcherna.
Eftersom mitt kunnande om fotboll var synnerligen begränsat valde jag en enkel metod genom att skapa ett beslutsträd för hur resultaten skulle bli. Och kom naturligtvis sist.
Inför fotbolls-EM (som alltså startar på lördag) har Mats en ny tävling, och den vill man ju inte missa.
Constraint programming-modell i MiniZinc
Eftersom kunnandet kring fotboll fortfarande är (ännu mer synnerligen) begränsat kan det inte vara frågan om att göra några bedömningar kring hur matchresultaten kommer att bli.Denna gång tänkte jag istället parasitera på Mats fantastiska fotbollskunnande och utnyttja det tips han själv gjort. För detta har skapats en modell i constraint programming-systemet MiniZinc. Modellen finns här och visas även nedan.
Modellen bygger på Mats tips med följande villkor.
Möjligen är några av villkoren lite väl begränsande men har fördelen att det inte blir så många lösningar (om man t.ex. skulle göra någon form av okulärbedömning av dem, vilket inte gjorts här, så det spelar egentligen inte någon roll hur många lösningar som genereras)
1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips.
Kommentar: Om Mats anser att ett lag vinner så gör jag det också. Mats borde veta sådant.
2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
som för Mats tips.
Kommentar: Detta är för att få ner antalet möjliga lösningar.
3) Inga resultat får vara exakt samma som Mats.
Kommentar: Egentligen borde man tillåta att några resultat är samma som Mats, men det blir roligare så här.
4) Det får vara maximalt 5 mål per match.
Kommentar: Kanske det skulle vara maximalt 6 mål, eller 7?
Det finns 29 olika lösningar till detta problem. Redan innan jag tittade på resultaten beslöt jag mig för att ta den sista lösningen som solvern Gecode fz (version 1.2.1) genererade.
Mitt tips
Här är alltså mitt tips till fotbolls-EM 2008.1. Schweiz - Tjeckien 2-2
2. Portugal - Turkiet 1-0
3. Österrike - Kroatien 0-1
4. Tyskland - Polen 1-2
5. Rumänien - Frankrike 1-3
6. Holland - Italien 1-2
7. Spanien - Ryssland 1-0
8. Grekland - Sverige 1-1
9. Tjeckien - Portugal 1-3
10. Schweiz - Turkiet 1-1
11. Kroatien - Tyskland 0-0
12. Österrike - Polen 1-3
13. Italien - Rumänien 2-0
14. Holland - Frankrike 0-1
15. Schweiz - Portugal 0-1
16. Turkiet - Tjeckien 1-1
17. Sverige - Spanien 1-3
18. Grekland - Ryssland 1-3
19. Österrike - Tyskland 0-3
20. Polen - Kroatien 0-1
21. Holland - Rumänien 1-0
22. Frankrike - Italien 1-3
23. Grekland - Spanien 1-4
24. Ryssland - Sverige 0-1
MiniZinc-modellen
Här nedan visas MiniZinc-modellen för problemet. (webb-versionen kan ha några små skillnader.)
%
% MiniZinc-modell för Mats Anderssons tävling om resultatet i fotbolls-EM 2008.
%
% För beskrivning av tävlingen se:
% http://www.mats-andersson.se/blogg/show.asp?svarsID=1956
%
%
% Min variant bygger på Mats tips med följande villkor:
%
% 1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips
% (om Mats anser att ett lag vinner så gör jag det också. Mats borde veta
% sådant).
% 2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
% som för Mats tips
% 3) Inga resultat får vara exakt samma som Mats.
% 4) Det får vara maximalt 5 mål per match.
%
% Med dessa begränsningar finns det 29 olika lösningar.
% Det beslöts innan lösningarna studerats att ta den sista lösningen
% som solvern Gecode fz (version 1.2.1) genererade.
%
%
% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%
int: n = 24; % antal fotbollsmatcher
array[1..n, 1..2] of 0..4: m; % Mats tips
array[1..n, 1..2] of var 0..4: h; % mitt tips
int: m_sum = sum(i in 1..n) (m[i,1] + m[i,2]); % totalt antal mål i Mats tips
var int: h_sum; % total antalet mål i mitt tips
solve satisfy;
constraint
forall(i in 1..n) (
% förhållandet i mål mellan lagen ska vara samma som Mats tips
m[i,1] - m[i,2] = h[i,1] - h[i,2]
/\ % max 5 mål per match
h[i,1] + h[i,2] <= 5
)
/\ % inga matcher får ha exakt samma resultat som Mats
sum(i in 1..n) (
bool2int(
m[i,1] = h[i,1] /\ m[i,2] = h[i,2]
)
) = 0
/\ % totalt antal mål i mitt tips
h_sum = sum(i in 1..n) (
h[i,1] + h[i,2]
)
/\ % totalt antal mål ska vara samma i Mats och mitt tips
h_sum = m_sum
;
output
[
if j = 1 then "\n" ++ show(i) ++ ": " else " " endif ++
show(h[i,j])
| i in 1..n, j in 1..2
];
%
% Mats tips
%
m = [
1,1, % 1. Schweiz - Tjeckien 1-1
2,1, % 2. Portugal - Turkiet 2-1
1,2, % 3. Österrike - Kroatien 1-2
0,1, % 4. Tyskland - Polen 0-1
0,2, % 5. Rumänien - Frankrike 0-2
0,1, % 6. Holland - Italien 0-1
2,1, % 7. Spanien - Ryssland 2-1
0,0, % 8. Grekland - Sverige 0-0
0,2, % 9. Tjeckien - Portugal 0-2
0,0, % 10. Schweiz - Turkiet 0-0
2,2, % 11. Kroatien - Tyskland 2-2
0,2, % 12. Österrike - Polen 0-2
3,1, % 13. Italien - Rumänien 3-1
1,2, % 14. Holland - Frankrike 1-2
1,2, % 15. Schweiz - Portugal 1-2
0,0, % 16. Turkiet - Tjeckien 0-0
0,2, % 17. Sverige - Spanien 0-2
0,2, % 18. Grekland - Ryssland 0-2
1,4, % 19. Österrike - Tyskland 1-4
2,3, % 20. Polen - Kroatien 2-3
2,1, % 21. Holland - Rumänien 2-1
0,2, % 22. Frankrike - Italien 0-2
0,3, % 23. Grekland - Spanien 0-3
1,2 % 24. Ryssland - Sverige 1-2
];
%
% End of MiniZinc model.
%
Notera att MiniZinc inte hanterar strängar speciellt bra så resultatet presenteras endast så här:
1: 2 2
2: 1 0
3: 0 1
4: 1 2
5: 1 3
6: 1 2
7: 1 0
8: 1 1
9: 1 3
10: 1 1
11: 0 0
12: 1 3
13: 2 0
14: 0 1
15: 0 1
16: 1 1
17: 1 3
18: 1 3
19: 0 3
20: 0 1
21: 1 0
22: 1 3
23: 1 4
24: 0 1
Slutord
Från början tänkte jag använda någon form av statistisk metod som analyserade Mats tips för att skapa mitt eget tips. Ovanstående angreppssätt ligger definitivt mer i linje med det jag håller på med nu.
Naturligtvis ska man se allt detta som en liten etyd i constraint programming.
Posted by hakank at 09:18 EM Posted to Constraint Programming | Pyssel | Comments (0)
maj 26, 2008
Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem
Här är några MiniZinc-modeller som skapats sedan förra anteckningen om sådana modeller.
Samtliga modeller att tilnå finns via My MiniZinc page.
Digital Tomography samt några varianter
Det problem som skrevs om i Ett litet april-pyssel löste jag själv med en digital tomografi-teknik. Se modellen tomography.mzn.
En viss förklaring av digital tomografi finns på sidan Open problems in discrete tomography. Sidan innehåller några Java-applets som man själv kan leka med.
I ovanstående modell var det bara en färg ("svart") man arbetade med, men problem kan generaliseras till flera färger. En sådan generalisering görs i tomography_n_colors.mzn, och som exempel modelleras bl.a. "The two atom problem".
Solitaire Battleship (wikipedia) är en variant av "Sänka skepp" som har liknande förutsättningar som digital tomografi. MiniZinmodell: solitaire_battleships.mzn.
SONET problem
SONET-problemet är ett standardproblem inom constraint programming som jag inte hittat någon MiniZinc-modell av så därför rullade jag en egen: sonet_problem.mzn.
För mer om problemet se t.ex. Simplified SONET Problem (Postscript-fil).
A Coin Puzzle
Detta problem på en rätt stor "grid" beskrivs utförligt av Tony Hürlimann i A coin puzzle - SVOR-contest 2007 (PDF).
Min MiniZinc-implementation av problemet finns i coins_grid.mzn. Ett tips är att låta en linear programming-solver lösa problmet, dvs ECLiPSe:s eplex eller MiniZincs nya option "--solver mip". Då löses det blixsnabbt.
Några Operations Research-problem
I John Hooker:s föreläsning A framework for integrating optimization and constraint programming finns några OR-problem som imlementerats:
- freight_transfer.mzn
- product_configuration.mzn
Ett skoj fotbollspussel
I Yahoo!-gruppen lp_solve kom ett skoj problem. Tyvärr krävs inloggning till gruppen, så MiniZinc-modellen innehåller hela meddelandet.
Problemet (som är en knapsack-variant) går ut på att optimera köp av brittiska fotbollsspelare med vissa krav:
- budgeten är på 30 miljoner (pund)
- man måste köpa ett visst antal spelare (målvakt, försvarsspelare etc) för en given kostnad per spelare
- man ska maximera den totala kostnaden men inte komma över budgeten.
Problemet uttrycks i flyttal men jag har valt att arbeta med heltal av två skäl:
- för tillfället är det fler MiniZinc-solvers som klarar av helttal än flyttal
- när det gäller spelarkostnader är inte orimligt att anta hela pund.
MiniZinc-modellen finns i football.mzn och är ganska generell.
Några andra modeller
- Funktionspartitionering, dvs partionera ett gäng heltal med avseende på en funktion t.ex. modulo-funktionen: modulo_partition.mzn. Det är enkelt att ändra funktion i modellen.
- Beslutsträd. Här modelleras ett fullständigt binärt beslutsträd: decision_tree_binary.mzn.
- Markovkedjor: markov_chains.mzn: Här räknar man ut "stable state" av marknadsandelnarna för tre företagsmärken.
- Yet another recreational schackproblem: peacableArmyOfQueens.mzn.
Raymond Smullyans logiska pyssel
Så till det jag satt med i helgen.
I den underbara boken What is the name of this book? beskriver Raymond Smullyan ett stort antal logiska pyssel, de allra flesta är skapade av Smullyan själv.
Några av de mest kända pysslen från denna bok är "Knights and Knaves"-problemen från kapitel 3 (som heter just "Knights and Knaves"): Alla "knights" talar alltid sanning och alla "knaves" ljuger alltid. Senare i kapitlet kommer även "Normals" med, sådan ljuger ibland och talar sanning ibland, och så tillkommer speciella giftasregler mellan de olika typerna. Problemet är att försöka lista ut vem som är vad med ledtråd av några få ledtrådar.
De allra flesta problemen från kapitel 3 finns modellerade i respektive modell:
- smullyan_knight_knaves.mzn: bara knights och knaves
. Problem 26 till och med 35. (Problem 36, 37 och 38 har av olika skäl inte modellerats.)
- smullyan_knight_knaves_normals.mzn: här finns även normals
. Problem 39 till och med 42 (modellen för 43 är inte korrekt).
- smullyan_knight_knaves_normals_bahava.mzn, med speciella giftoregler mellan knights, knaves och normals. Problem 44, 45 och 46.
Wikipedia har mer info om Knights and Knaves.
Uppdatering något senare
Några fler problem från samma bok:
- De första problemen om Lion och Unicorn från kapitel 4 "Alice in the Forest of Forgetfulness": smullyan_lion_and_unicorn.mzn. Lejon och enhörningar ljuger vissa dagar och talar sanning andra dagar. Här gäller det att lista ut vilken dag de säger olika saker.
- De första problemen från kapitel 5 "The mystery of Portias Caskets" smullyan_portia.mzn.
Posted by hakank at 06:54 EM Posted to Constraint Programming | Pyssel | Comments (0)
april 26, 2008
Ett litet april-pyssel
För tre år sedan (2005) publicerades ett Aprilpyssel. Det är dags att åter ta upp denna tradition.
Naturligtvis är nedanstående pyssel - på något sätt - kopplat till det jag kollar in just nu, dvs constraint programming/integer programming/MiniZinc.
Denna typ av pyssel har ett specifikt namn - som jag inte avslöjar just nu - och tillhör en grupp mer generella problem (som vad jag vet inte har något speciellt namn, dock med åtminstone ett undantag).
Problem
Inledning
Betänk följande binära matris (dvs endast 0 och 1 förekommer) där summorna för respektive rader och kolumner visas i fetstil.
1 010
1 010
0 000
020
Vi sammanfattar respektive summor i två vektorer:
- radsummor: [1,1,0]
- kolumnsummor: [0,2,0].
Dagens pyssel går nu ut på, att givet en radsummavektor och en kolumnsummavektor, lista ut vilken matris som ligger som grund för dessa summor.
Delproblem
Det är två stycken delproblem som vardera på något vis kan ge ledtråd till lösningen av det andra delproblemet.
Delproblem a
radsummor= [0,2,2,2,2,2,8,8,4,4,4,4,4,0]
kolumnsummor = [0,0,0,12,12,2,2,2,2,7,7,0,0,0]
Delproblem b
radsummor = [0,0,8,2,6,4,5,3,7,0,0]
kolumnsummor = [0,0,7,1,6,3,4,5,2,7,0,0]
Ett av dessa problem har jag snott ("kopierat" är en mer korrekt term för detta förfarande) från någonstans, det andra har jag hittat på själv. Ordningen mellan delproblemen, liksom presentationen av dess härlednad i föregående mening, är faktiskt slumpad med ett slumptalsprogram, nämligen R.
Vinnerier etc
Vinnaren i detta pyssel anses den vara som först till pysselledningen:
- p) ger korrekt svar på båda delproblem
- q) samt redogör för hur problemet löstes.
"Till pysselledningen" definieras här som antingen en kommentar i denna blogganteckning, eller ett mail till hakank@bonetmail.com.
Vinnaren erhåller i kommentarerna till denna blogganteckning eller i en separat blogganteckning ett "Bra gjort, X!", där X ersätts av vinnarens namn/handle/smeknamn etc. Möjligen kommer "Bra gjort" att ersättas av synonymiserade uttryck och/eller kompletteras med kraftfullare attribut (såsom "Mycket") då i kombination med erforderliga ändringar av resten av uttrycket för att det ska bli så korrekt svenska som möjligt (byte av stor till liten bokstav etc).
Pysselledningen förbehåller sig att dela ut noll (0) eller flera stilprogram till förslag som ej är korrekt lösta, inkompletta men på något sätt (subjektivt bedömt) förtjänar ett stilpoäng, men även till korrekta lösningar som förtjänar sådan stilpoäng. Negativa stilpoäng kommer inte att delas inte, åtminstone inte officiellt. Eventuella felaktigheter som eventuellt påpekas för eventualla lösningsförslag definieras inte som negativa stilpoäng i detta sammanhang.
Till allt detta kommer vinnaren även att erhålla en av följande vid nästa eller någon (dock endast en) efterföljande IRL-träff (den virtuella glassen är än så länge alldeles för blaskig för att bjuda på):
- glass
- öl
- kaffe
- te
- eller annan motsvarande dryck
Not: Glass/öl/etc kan delas ut av den person som råkar utgöra pysselledningen i helt andra sammanhang och av helt andra skäl. Detta ska då ses som något som är hetl frikopplat från denna pysseltävling.
Lösningens presenterande etc
Det är planerat att presentera den av pysselledningen ansedda korrekta lösningen (inklusive några kommentarer samt åtminstone en vidarelänk) efter en viss tid har s.a.s. runnit, inklusive en MiniZinc-modell. Exakt när detta sker beror på.
Slutord
En av de saker som intresserar mig är hur man går till väga för att lösa slika problem. Därför är punkt q) viktig i lösningen. Det behöver inte vara (men kan vara) speciellt långt svar, men ange gärna metod, systemstöd samt - vilket är lika intressant - eventuella felskär.Slutligen: Förutom "Lycka till!" kan noteras (vilket säkert redan gjorts av den observante läsaren) att ovanstående pysselformulering kunde - om omständigheterna vore annorlunda - göras mycket kortare. Men det är de inte så det gjordes inte.
Posted by hakank at 10:25 FM Posted to Constraint Programming | Pyssel | Comments (8)
oktober 11, 2006
Oktober-rebusen
Liksom förra "rebusen" så var Jimmy Höögs Internetlänkars 2:a rebus också kul.
Själv fastnade jag rejält på 13 -> 14, men efter lite funderande (och kort därefter en mental smack i huvudet att det var faktiskt inte var så svårt men helt annorlunda än de relativt avancerade teorierna som först testades) så fixades även den. Det var den jag satt med längst, såväl i funderingstid som kalendertid.
För en annan uppgift var jag lat och skrev Perl-program, men fick äta upp det sedan. Det finns säkert en bra moral härvidlag.
För den som inte testat dessa "rebusar" (jag skulle hellre kalla det för länkgåtor, URL-gåtor eller något sådant men är definitivt inte kittslig) gäller det att skriva in en URL (typ någonting.htm) genom att via texten (och eventuellt ledtråden) som finns på sidan lista ut regeln för denna sida och sedan applicera regeln för nästa tal i ordningen (dvs efter 1 kommer 2 etc).
Notifierad när nästa månadsgåta går igång kan man bli genom att registrera på Nyhetsbrevet.
(Jag har faktiskt inte gett mig på detta problem, vilket naturligtvis är en stor brist i min karaktär. Det verkar inte helt lätt...)
Andra bloggar om: rebus, gåtor.
Posted by hakank at 07:02 EM Posted to Pyssel | Comments (0)
juli 10, 2006
Kul brädspel: Entropy Game (Hyle 7)
Entropy Game (kallas även Hyle 7) är ett kul datorbaserat brädspel skapat av Eric Solomon.
Man väljer antingen Chaos eller Order och programmet spelar den andra rollen. Chaos börjar med att lägga ut en färgad bricka någonstans varpå Order ska försöka skapa ett mönster. Den ende som får poäng är Order enligt hur mycket ordning det är raderna och kolumnerna. Den exakta poängberäkningen finns inte i appleten (men visas i marginalerna), se istället spelets sida på Mind Sport Olympiad.
Se även
Erik Solomons publikationer.
Bok av Solomon: Game Programming (1984, Bokus, ISBN=052127110X).
Andra Java-spel av Solomon.
(Via think again!)
Andra bloggar om: spel, brädspel
Posted by hakank at 09:21 FM Posted to Pyssel | Comments (0)
juni 09, 2006
Utanvitsar (utangåtor, utanrebusar): ett program
Håkan Karlsson har beskrivit ett skoj ordpyssel i Utanvitsen, där det gäller att komma på vilket ordpar som avses utifrån en bokstav samt en liten beskrivning.
Några exempel:
k: barnlösa monarker ( = kungar utan ungar)
r: outvecklad kommunism (= revolution utan evolution)
r: torkade fikon (frukt utan fukt)
I kommentarerna ger Bloggblad följande paradigmatiska exempel (som Lotten Berglund löste elegant)
m = magerlagd engelsman (mister utan ister)
Läs mer underbara exempel hos hakke.
Mer schematiskt:
[bokstav]: "ord_X med [bokstav]" utan "ord_X utan [bokstav]"
Det kan även finnas mer strikta regler, t.ex. att [bokstav] måste finnas i början eller i slutet av ord_X (denna regel används i programmet som beskrivs nedani.
Programmet Utanvitsar
Efter och enligt önskemål från hakke har jag skrivit ett litet program för att underlätta konstruktionerna av själva utanvits-paren (som jag något fånigt kallar "utanvitskompisar"): Utanvitsar.
Ordlistan som används är på cirka 90 000 svenska ord.
Exempel på en körning
Ordet mister ger följande två kompisar:
* mister - ister
* mister - miste
Och ordet yra ger denna ansamling:
* fyra - yra
* hyra - yra
* lyra - yra
* myra - yra
* pyra - yra
* syra - yra
* yra - yr
För att underlätta konstruktionerna ännu mer har det skapats en fil med mer än 10 000 svenska sådana par (utifrån samma ordlista på cirka 90 000 ord som används i programmet): utanvitspar_swe.txt. Filen innehåller även ordböjningar som näppeligen är speciellt skojiga (t.ex. "frostskadad - frostskada").
Med ett enkelt handgrepp kan man även få engelska utanvitskompisar (without pal pairs?).
Noter
Not 1
Programmet söker endast efter utanvits-kompisar som kan skapas genom att första eller sista bokstaven tas bort/läggs till. Detta innebär att kombinationen "frukt - fukt" inte kommer med. Denna begränsning är helt enligt hakkes önskemål.
Not 2
Det är inte alls säkert att det finns en sådana kompisar för det givna ordet.
Not 3
Den där beskrivningen som följer efter den ensamma bokstaven - som helst ska vara poängfull och förvirrande och om möjligt med en samhällstillvänd udd - får man själv komma på.
Posted by hakank at 09:39 EM Posted to Program | Pyssel | Språk | Comments (1)
april 27, 2006
Smith code: Kod i Dan Browns Da Vinci-kod dom
I Expressen-artikeln Dan Brown-domaren smög in en kod i domen står att läsa:
Det är något mystiskt med domen som friade författaren Dan Brown från plagiat.
Det finns en kod i den.
Domare Peter Smiths kod....
Plötsligt dyker det upp en kursiverad bokstav mitt i ett ord. Där kan exempelvis plötsligt stå "claimant".
Lägg ihop de kursiverade bokstäverna i de första sju paragraferna och man får: Smithy code -Smithykoden.
Om man nu tar samtliga kursiverade bokstäver (de som kursiverades via programmet pdftohtml) får man följande sträng
smithycodeJaeiextostgpsacgreamqwfkadpmqzv
Den första delen - "smithycode" - nämndes i Expressen-artikeln, och hela strängen finns även i andra källor (se nedan).
Några tankar (ej lösning!)
Här är några tankar, där den principiella förutsättningen är att det en relativt enkel form av kodning och inte någon superkryptometod.
En tanke är att det finns tre separata delar (bokstäverna helt enkelt verkar tillhöra olika delar) som är kodade med olika typer av tekniker:
1. smithycode
2. Jaeiextostgpsacgream
3. qwfkadpmqzv
2 känns som det skulle kunna vara något anagram (på latin?). Problemet med anagram är att de tenderar att ha väldigt många lösningar så det är troligen inte rätt väg. Internet Anagram Server hittar dock inget anagram på latin. På engelska finns det däremot många (obs. stor sida!).
3 kanske är någon form av rotationskryptering. Här är 0 till 25-rotationerna och dess reverser för strängen "qwfkadpmqzv":
rot(0): qwfkadpmqzv reverse: vzqmpdakfwq
rot(1): rxglbeqnraw reverse: warnqeblgxr
rot(2): syhmcfrosbx reverse: xbsorfcmhys
rot(3): tzindgsptcy reverse: yctpsgdnizt
rot(4): uajoehtqudz reverse: zduqtheojau
rot(5): vbkpfiurvea reverse: aevruifpkbv
rot(6): wclqgjvswfb reverse: bfwsvjgqlcw
rot(7): xdmrhkwtxgc reverse: cgxtwkhrmdx
rot(8): yensilxuyhd reverse: dhyuxlisney
rot(9): zfotjmyvzie reverse: eizvymjtofz
rot(10): agpuknzwajf reverse: fjawznkupga
rot(11): bhqvloaxbkg reverse: gkbxaolvqhb
rot(12): cirwmpbyclh reverse: hlcybpmwric
rot(13): djsxnqczdmi reverse: imdzcqnxsjd
rot(14): ektyordaenj reverse: jneadroytke
rot(15): fluzpsebfok reverse: kofbespzulf
rot(16): gmvaqtfcgpl reverse: lpgcftqavmg
rot(17): hnwbrugdhqm reverse: mqhdgurbwnh
rot(18): ioxcsvheirn reverse: nriehvscxoi
rot(19): jpydtwifjso reverse: osjfiwtdypj
rot(20): kqzeuxjgktp reverse: ptkgjxuezqk
rot(21): lrafvykhluq reverse: qulhkyvfarl
rot(22): msbgwzlimvr reverse: rvmilzwgbsm
rot(23): ntchxamjnws reverse: swnjmaxhctn
rot(24): oudiybnkoxt reverse: txoknbyiduo
rot(25): pvejzcolpyu reverse: uyploczjevp
där det enda jag hittar är "warn" för reverse(rot(1)). Inget att hänga i julgranen, alltså.
Hmm, det där "y":et i "smithycode" kanske är en ledtråd...
(Tack Jonas för Expressen-länken.)
Se även
Dokumenten att leka med: Sammanfattningen. och själva domen (PDF).
Reuters: Latest Da Vinci mystery: judge's own secret code
Slashdot (naturligtvis) Judge Creates Own Da Vinci Code.
Posted by hakank at 07:15 EM Posted to Pyssel | Comments (2)
april 18, 2006
Choco: Constraint Programming i Java
Bakgrund
Mitt intresse för Constraint Programming (CP) (som tidigare kallades Constraint Logic Programming, CLP) väcktes för ett antal år sedan strax efter en företagskamp (som kort beskrevs i Uppdaterat program: AnaCheck), där ett av uppdragen var följande matematiska pyssel:
Vilken är den minsta differensen man kan få mellan två tal om man måste använda samtliga siffror (0..9) exakt en gång?
Lösningen presenteras nedan.
Ungefär samtidigt stötte jag på Constraint (Logic) Programming och med detta och liknande pyssel i bakhuvudet, och blev väldigt fascinerad av programmeringsparadigmet. Kanske inte så förvånande eftersom många standardexempel är just matematiska pyssel.
Tanken är att man endast behöver skriva de problemspecifika villkoren (constraints), sedan får systemet lista ut bästa sättet att lösa problemet. Det finns många olika metoder och heuristiker för att lösa problemen, och ibland måste hjälpa till så att lösningen kommer denna sidan regnbågen eftersom vissa problem är mycket tunga.
Ett citat som ofta nämns i sammanhanget är Eugene C. Freuder (CONSTRAINTS, April 1997)
Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it..
Prologbaserade system
I början arbetade jag mestadels med logikprogramspråket Prolog som "moderspråk", Sicstus Prolog samt ECLiPSe Constraint Programming System (det senare inte att förväxlas med utvecklingsmiljön med ungefär samma stavning).
Imperativa språk
Som komplement till de Prologbaserade systemen har jag letat efter mer imperativa - samt icke-kommersiella - moderspråk såsom Java, C, C++, Perl, Python, eftersom vissa saker är lättare att programmera med sådana språk (men ibland svårare) En av dessa implementationer Python-constraint och nämns i kommentarerna till Sesemans matematiska klosterproblem samt lite Constraint Logic Programming.
Choco
Så till det system jag har kollat i nyligen: det Java-baserade Choco. I slutet av anteckningen finns fler referenser.
Choco är snabbt och det har en stor mängd funktioner. Exemplen nedan är endast för "finita domäner" (löses med hjälp av heltal), men det finns även domäner med reella tal samt mängder.
Det är dock inte lika elegant att skriva constraints som i Sicstus/ECLiPSe, vilket vi nu kommer att titta på.
Minsta differensproblemet - en jämförelse av kodskrivning
För att tydliggöra skillnader och likheter mellan Choco och de Prologbaserade systemen visas hur minsta differensproblemet kan lösas i respektive system.
I ECLiPSe skriver man själva constraint-delen av problemet på följande sätt; i Sicstus Prolog skriver man snarlikt. Obs: koden är inte riktigt komplett att bara köra.
:-lib(fd), lib(fd_search), lib(fd_global),lib(fd_domain).
% ....
LD = [A,B,C,D,E,F,G,H,I,J], % deklarera de 10 variablerna
LD :: [0..9], % intervallet för variblerna, mellan 0 och 9
fd_global:alldifferent(LD), % alla värden ska vara olika
%
% constraints
%
% A + B + C + D + E = F + G + H + I + J
X #= 10000*A+1000*B+100*C+10*D+E,
Y #= 10000*F+1000*G+100*H+10*I+J,
% differensen ska bli positiv
X #< Y,
% differensen
Diff #= Y - X,
% minimera differensen (Diff) samt heuristik för att hitta lösningen snabbt
minimize(search(LD,0,anti_first_fail,indomain_max,credit(64,bbs(15)),[]),Diff).
Elegant och lite magiskt, eller hur?
Motsvarande Choco-program är lite längre, främst eftersom det saknas syntaktiskt socker. Det går att pressa antalet rader (sådant har gjorts) men här görs en mer expressiv form för att jämförelsen ska bli tydligare. Programmet finns att ladda ner här nedan.
// Choco program
import choco.Problem;
import choco.*;
import choco.integer.*;
public class LeastDiff {
public static void main(String[] args) {
new LeastDiff().puzzle();
}
public void puzzle () {
Problem pb = new Problem();
// definiera variablerna A .. J så att dess värden är mellan 0 och 9
IntDomainVar A = pb.makeEnumIntVar("A", 0, 9);
IntDomainVar B = pb.makeEnumIntVar("B", 0, 9);
IntDomainVar C = pb.makeEnumIntVar("C", 0, 9);
IntDomainVar D = pb.makeEnumIntVar("D", 0, 9);
IntDomainVar E = pb.makeEnumIntVar("E", 0, 9);
IntDomainVar F = pb.makeEnumIntVar("F", 0, 9);
IntDomainVar G = pb.makeEnumIntVar("G", 0, 9);
IntDomainVar H = pb.makeEnumIntVar("H", 0, 9);
IntDomainVar I = pb.makeEnumIntVar("I", 0, 9);
IntDomainVar J = pb.makeEnumIntVar("J", 0, 9);
IntDomainVar[] letters = {A,B,C,D,E,F,G,H,I,J};
IntDomainVar Diff = pb.makeBoundIntVar("Diff", 0, 10000);
// Temporära variabler
IntDomainVar X = pb.makeBoundIntVar("X", 0, 100000);
IntDomainVar Y = pb.makeBoundIntVar("Y", 0, 100000);
// alla värden ska vara unika
for (int i = 1; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
if (i==j) {
continue;
}
pb.post(pb.neq(letters[i], letters[j]));
}
}
// X = A+B+C+D+E
pb.post(pb.eq(X, pb.scalar(new int[]{10000, 1000, 100, 10, 1},
new IntDomainVar[]{A,B,C,D,E})));
// Y = F +G + H + I + J
pb.post(pb.eq(Y, pb.scalar(new int[]{10000, 1000, 100, 10, 1},
new IntDomainVar[]{F,G,H,I,J})));
// Diff = X - Y
pb.post(pb.eq(pb.minus(X, Y), Diff));
// minimera skillnaden
pb.minimize(Diff,false);
// nu ska vi lösa problemet
Solver s = pb.getSolver();
pb.solve(true);
// Skriv ut lösningen
System.out.println("Result: "+ A.getVal() + B.getVal() + C.getVal() +D.getVal() + E.getVal() + " - " + F.getVal() + G.getVal() + H.getVal() + I.getVal() + J.getVal() + " = " + Diff.getVal() );
} // end puzzle
} // end class
Lösningen som ges av dessa båda program är samma, nämligen
50123 - 49876 = 247
Några körbara (kompilerbara) Choco-program
Här är källkoden till några andra mindre Choco-program, varav några är standardproblem inom constraint programming. Choco-distributionen innehåller några andra.
LeastDiff2.java: Ovanstående exempel
FurnitureMoving.java: Planering av möbelflyttande, använder cumulative.
Knapsack.java: ett enkelt knapsack-problem (minimize)
Zebra.java: ett standardpyssel
Seseman.java: Choco-versionen av Sesemans matematiska klosterproblem
Se även
om Choco:
Choco: projektsidan på Sourceforge
Wiki
User guide
Choco API
Forum
om constraint programming
Roman Barták: On-line Guide to Constraint Programming
Roman Barták: Constraint Programming: In Pursuit of the Holy Grail (PDF)
tidigare skrivet om C(L)P
Sesemans matematiska klosterproblem samt lite Constraint Logic Programming
Automatisk "lösning" av Minesweeper i Mozart/Oz
JaCoP är ett annat Javabaserat system, utvecklat vid Lunds Universitet som man kan få tillgång till om man frågor någon av dess skapare. Har inte kollat in det så mycket ännu, men det verkar också trevligt.
Posted by hakank at 09:59 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)
november 21, 2005
Bloggforum 3 - Några tankar samt Isobels och Lisas pizzeriabordsproblem
Nedanstående är inte avsedd att vara någon fullständig redovisning av vad som hände eller gjordes under Bloggforum 3 eller helgen kringgärdande detta evenemang. Snarare är det tankar kring det man pratade om i och utanför det formella programmet. Vad gäller fysiska trajektorier och de yttre omständigheterna kan refereras till Mats Anderssons utmärkta och innehållsrika Summering av Bloggforum 3.
Ett stort tack till Rebecca Crusoe, Stefan Geens och Erik Stattin för deras fina arbete att anordna ett så intressant program, och som gjorde det möjligt att få förmånen träffa så väldigt trevliga och intressanta personer.
Det har skrivit väldigt mycket redan om forumet. De naturliga samlingspunkterna är
- Bloggforum 3
- del.icio.us/tag/bloggforum3
Bloggen är död
Temat (med glimten i ögat) för detta forum var "Bloggen är död". Det är egentligen absurt att nu när begreppet blogg håller på att bli känt för en större allmänhet anser man att bloggen är död.
Personligen har jag sedan ett tag känt att formatet känts begränsande i vissa fall. I såväl bloggverktyg som kommentarer finns en tendens att endast bry sig om det som skrevs nyligen. Det innebär att det man skrivits tidigare (t.ex. en vecka, en månad eller ett år sedan) inte läses längre i ett naturligt sammanhang. Denna dominans till det kronologiska har alltså stört mig rätt länge. I vissa fall är det naturligt eftersom det ofta är dagsaktuella frågor som diskuteras och man anser att debatt etc är över. Men det man missar är samlandet av kunskap kring det som man - eventuellt - kom fram till.
Det verkar även finnas andra som haft liknande tankar kring begränsningarna, men kanske av andra skäl, vilket inte är så konstigt. Nu har man hunnit experimenterat med mediet, funnit det som passar ens egna syften och identifierat det som är mindre intressant. Det verkar gälla såväl traditionell (text)bloggning, podcasting som videobloggning. Detta är tiden att fundera över mediers inneboende begränsningar.
Stefan Geens undrar lite Bloggforum 3 - what I saw vad Bloggforum 4bör innehålla. Det rykte som Jon skriver om i sin kommentar är något som bl.a. jag själv underblåst (eller vad det nu är man gör med rykten), eftersom jag inte tror att det finns behov för ett Blogg-forum om ett halvår, och diskuterade detta lite med både Erik Stattin och Stefan Geens i helgen.
Däremot ser jag mycket fram emot ett X-forum (alternativt X-logg-forum) där man visar hur det-vi-nu-nu-kallar-blogg ("the thing formerly known as blog") har utvecklats och förändrats, och hur det eventuellt påverkat t.ex. socialt eller tekniskt. Självklart kommer det fortfarande att finnas bloggar med eller utan t.ex. wiki-liknande utökningar, men jag tror och hoppas att vi kommer att se en större variantion i såväl form som innehåll.
Troligen har det om ett halvår även hänt saker inom lagstiftning, politik, media samt i det sociala landskapet (t.ex. olika typer av forskning kring bloggning) som är väl värt att föreläsa om eller ha sessioner kring.
Som Ben Hammersley beskriver i sin "Åtta idéer som verkligen kommer att revolutionera 2000-talet (och varför blogging inte är en av dem)" är bloggen i sig inte inte en någon revolutionerande idé, men inkorporerar många av de idéer som har eller kommer att revolutionerna informationsamhället eller åtminstone påverka det.
Web 2.0 och agenter
Under flera tillfällen diskuterades det Web 2.0, t.ex. med Simon Winter, Henrik Torstensson och Jon Åslund. Jag har inte stenkoll på vad det är och tycker det liknar det som man sa kring 98/99 om webben eller t.ex. när WAP kom. Men nu har det faktiskt blivit möjligt för en företagsam person att göra dessa applikationer med öppna API och "öppen data".
En sak som jag har saknat i diskussionerna är intelligeta agenter som kommunicerade med varandra för att lösa all världen (informations)problem. Vad blev de egentligen av? Jag vill ha min shoppingagent!
Jyri Engström: Sociala object
Jyri Engströms föredrag var det föredrag som jag var mest intresserad av och var även det som jag uppskattade mest. Engström poängterade att det viktiga med sociala mjukvaroprogram (och man borde kunna se bloggen som ett sådant) är gemensamma sociala objekt, där objekt kan vara väl definierat men även uppstå spontant efter ett tag.
Som exempel på hur viktigt det är med gemensamt socialt objekt visades en av mina favoriter bland Monty Python-sketcherna: Fotbollsmatchen mellan grekiska och tyska filosofer. Detta fick mig att parafrasera Wittgensteins berömda setens från Filosofiska undersökningar: "a serious and good philosophical or social work could be written that would consist entirely of jokes from Monty Python".
Inledningsvis nämnde Engström några böcker som jag har faktiskt läst och skrivit lite om, se mer Social Network Analysis och Complex Networks - En liten introduktion. Se även tidigare bloggningar: Social Network Analysis/Complex networks.
Engström rekommenderade även en nyutkommen bok (den där med bilderna på det italienska mötet respektive potatisodlingen) och som verkar intressant: John Thackara In The Bubble - Designing in a Complex World.
Det antyds att Lotta at Work kommer att publicera ljud/video från Engströms föredrag.
Ben Hammersleys vision
Ben Hammersley hade en något provocerande rubrik på sitt föredrag "Åtta idéer som verkligen kommer att revolutionera 2000-talet (och varför blogging inte är en av dem)" som fick sin förklaring, och gav faktiskt en koppling till bloggandet genom att bloggande (och bloggare) "inkorporerar" alla(?) dessa punkter.
Föredraget var intressant även om jag inte riktigt håller med honom i hans undergångsbeskrivning. Hans tes att detta är en unik tid som vi aldrig tidigare skådat känns också som en något omotiverad kontemporär-centrism, dvs att vår tid är viktigare eller mer märkvärdigt än tidigare tider. Vad är det för märkvärdigt med vår tid? Å andra sidan är uppgång och nedgång av civilisationer inte heller någon naturlag.
En kommentar kring en detalj som verkar vara viktigt för resonemanget. Hammersley menar att den tekniska utvecklingen numera bara fortsätter att öka genom att den tekniska utvecklingen förstärker sig själv, t.ex. genom att snabbare datorer gör det möjligt att skapa ännu snabbare datorer som i sin tur möjliggör skapande av snabbare datorer etc. Han stödde denna tes med en bild föreställande en exponentiell kurva som påstods visa att datorerna blir allt snabbare/billigare/kraftfullare datorerna utan någon gräns eller avtagande. Troligen kan man även tolka kurvan som en logistisk kurva, eftersom den i början ser den ut som en exponentiell kurva men planar sedan ut till en "mättnadsnivå". En alternativt tolkning att det var i stort sett samma kurva ("sinuskurva") som Hammersley tidigare visat att symboliserade tidigare civilisationer hade följt: först uppgång, sedan nedgång ("crawling in the mud"?) och sedan uppgång igen och sedan nedgång. Således är det inte nödvändigt att det är en exponentiell tillväxt.
Han varnade i och för sig för att beskrivningen skulle störa personer med vissa kunsaper inom historia och teknik (samt eventuellt matematik).
Hur som helst var det ett mycket energirikt och inspirerande föredrag. Det finns en ljudupptagning via Lotta at Work.
Mozz Hussain: MSN Spaces i praktiken
Mozz Hussain "Busting blogging myths - the present and future of blogging" handlade om erfarenheterna kring MSN Spaces. Det var i och för sig intressant och gav inblickar i den sociala strukturen kring bloggar, men detaljerna fastnade inte så mycket. Kanske beror detta på att MSN Spaces inte representerar så mycket den typ av bloggning som jag själv tycker är mest intressant att följa, det som bl.a. Jonas Söderström kallar för kunskapsbloggar.
Copyfight
Detta hade jag sett framemot, bl.a. eftersom Simon Winter var med i panelen. Simon är en av mina absoluta favoriter bland de svenska bloggarna och som jag haft förmånen att träffa flera gånger tidigare. Simon summerar några av sina tankar kring debatten i Vad är viktigt med upphovsrätt?.
Med en något elak förenkling kan man säga att man kom fram till att man egentligen inte vet vad som gäller. Det var dock intressant att följa debatten, speciellt de konkreta exemplen som framfördes såväl från panelen som publiken.
Debatten blir inte lättare med att begreppen "kopiering", "fildelning", "piratkopiering" nu är så inflammerade att det verkar som en vettig diskussion av det är omöjlig, och det känns som om antipiratbyrå-sidan för tillfället äger dessa begrepp. Ett förslag är att försöka hitta en mer neutral begreppsapparat som gör det möjligt att föra rationella diskussioner. Under kvällen föreslogs det att begreppet "kopiera filer" skulle bytas ut mot det neutrala "kgegg" (så tror jag att det stavas), ett ord som länge sökt sin användning.
Gamla vänner, nya vänner samt att bli överraskad
Waldemar på Teche skriver följande i Det bloggforum jag inte var på:
Jag är lite förvånad över bloggosfären fortfarande håller i sig som en enad miljö. Trots allt är det ju rätt skilda ämnen och åsikter som avhandlas numer, men att man ännu delar en gemensam plattform... det tyder på att det kanske kommer att hålla i sig.
Ett skäl till kan exemplifieras med just Bloggforum är just att där finns så många olika intressen men alla har en gemensam referensram: bloggar. De allra flesta är också sådana som brinner för något och sådana personer är nästan alltid intressant att träffa eller få kontakt med (undantag finns naturligtvis). Det är flera kluster som - speciellt i Bloggforum - blandas i det gemensamt intresse av att uttrycka sig . I pausar, lunchen eller på "cocktail-partyt" kan man mingla med personer som man normalt inte träffar. Precis som i riktiga vänskapslivet kan man bli "hit it off" med en väns vän eller dennes vän
Den sociala poängen med dessa tillställningar är flerfaldig: att träffa sina gamla vänner, att prata med dem man har läst men inte träffats tidigare, samt helt enkelt bli överraskad av ett möte med någon man inte ens kände till. Detta sistnämnda ska inte underskattas.
På ungefär samma sätt vill man att sociala nätverkssystem ska fungera. Nyhetsbevakningsystem och rekommendationssystem har liknande syften:
- man vill bli uppdaterad inom de områden man känner väl till
- man vill lära sig mer inom ett ämne
- man vill bli överraskad av nya kunskaper eller ämnen.
En social nätverksanalys-kommentar: I många Bloggforum 3.0-redogörelser länkas det till personerna som träffats. Det skulle vara intressant att jämföra dessa med t.ex. bloggrullen eller de man länkat till föregående samt eventuellt efterföljande. Avspeglar kontakterna på Bloggforum det normala sociala mönstret inom bloggosfären? Min egen intuition kring detta är att cocktail-parties har en annan social dynamik än de dagliga bloggkontakterna.
Några längre-än-kortare kontakter
Här är den nästan-obligatoriska lista över personer som träffades och som pratades med mer än några sekunder. De med (*) anger nya IRL-bekantskaper. Det skulle ta alldeles för lång tid att skriva ner vad vi pratade om så det blir i stort sett endast en uppräkning av namn. Tack till er för trevliga pratstunder.
- Mats Andersson, resekamrat, hotellrumssdelare, gåtlösare samt galapetter
- Steffanie Müller
- Simon Winter
- Stefan Geens
- Andreas Haugstrup (*)
- Henrik Torstensson
- Någonting Söderström(?), Henrik Torstenssons ej bloggande kompis (*).
- Eric Wahlforss (*)
- Erik Stattin
- Jenny Isaksson (*)
- Niki Bergman (*)
- Rebecca Crusoe
- Daniel Lundh (*)
- Håkan Hakke Karlsson, varvid våra respektive skulder tillvarandra nu är reglerade.
- Rosemari Södergren (*)
- Erik Starck
- Jimmy Wilhelmsson
- Johnny Söderberg, mitt mål att prata med honom mer än några sekunder blev uppfyllt.
- David Hall
- Lisa Förare Winbladh
- Isobel Hadley-Kamptz (*), naturen av vår kontakt beskrivs nedan under "Isobels och Lisas pizzeriabordsproblem".
- Jonas Söderström
- Jon Åslund (*)
- Coola morsan, men vi hade lämnat vår musikideologiska skiljelinjer bakom oss.
- Oscar Swartz (*)
- Karolina Lassbo (*).
- Per Gudmundsson
Två personer som jag inte träffade men hade tänkt prata med:
- Patrik Wallström (som jag skulle hälsa från en gemensam vän tillika listsvågrar)
- Christian Ubbesson (listsvåger och arbetar med saker, text mining, som jag är intresserad av)
Geekighet
Jag var med i flera diskussioner om geeekighet, vilket nog faller sig naturligt på en så här rätt geekig tillställning. Många av de personer som jag pratade med eller åhörde kan nog anses vara geekar, i alla fall i en något vidare mening (se nedan).
* en mer allmän diskussion med Steffanie Müller som började med att hon ansåg mig vara en större geek än hon själv (som om man kan jämföra geekigheter på detta sätt), varpå vi diskuterade naturen av detta begrepp.
* Jimmy Wilhelmsson berättade om dokusåpan FCZ som består av ett gäng geekar som spelar fotboll (och som jag inte sett men ändå stött på indirekt i ett rätt geekigt sammanhang) där geeken nu får ett ansikte och personlighet.
* både direkt och indirekt med Jon Åslund - som jag uppfattar som en übergeek, och det är en komplimang, Jon - i alla fall de facetter jag såg, vilket möjligen avspeglar mina egna intressen och värderingar. Lite roligt här är att jag förra söndagen stötte på Jons namn i ett helt annat sammanhang; nästan helt annat, eftersom det var i samband med att Hakke lämnade in sina svar på Bloggforum-pyssel i lite för poetiska formuleringar, nämligen att Jon är skapare av det underbara programspråket The Shakespeare Programming Language som jag känt till tidigare.
Det finns ett test The Nerd? Geek? or Dork? Test där jag själv fick följande resultat:
Pure Nerd
82 % Nerd, 47% Geek, 43% Dork
For The Record:
Man definierar de olika begreppen på ett sätt som jag inte nödvändigtvis håller med om.
A Nerd is someone who is passionate about learning/being smart/academia.
A Geek is someone who is passionate about some particular area or subject, often an obscure or difficult one.
A Dork is someone who has difficulty with common social expectations/interactions.You scored better than half in Nerd, earning you the title of: Pure Nerd.
The times, they are a-changing. It used to be that being exceptionally smart led to bei
ng unpopular, which would ultimately lead to picking up all of the traits and tendences
associated with the "dork." No-longer. Being smart isn't as socially crippling as it o
nce was, and even more so as you get older: eventually being a Pure Nerd will likely be
replaced with the following label: Purely Successful.
Isobels och Lisas pizzeriabordsproblem
Under lunchen satt vi (Lisa, Rosmarie, Johnny, Hakke, hakank samt Daniel) på en pizzeria. Efter en stund ropar Lisa: "Isobel!" varpå denna kom fram till vårt bord. Efter lite inledandes flamsande ville naturligtvis Isobel och Lisa uttrycka sin ömsesidiga vänskap genom en kram eller liknande, varvid man insåg snabbt att ett logistiskt problem hade uppstått genom att bordplaceringen var sålunda:
Förkortningar:
1: Lisa (som alltså är den som känner Isobel)
2: Rosmarie
3: Johnny
4: Hakke
5: hakank
6: Daniel
Bordplaceringen:
_ V Ä G G
V 2 4 6
Ä _ _ _ Isobel (stående och rörlig)
G 1 3 5
G
_ V Ä G G
Där "V Ä G G" - på härsan och tvärsan - betyder omgärdande av en vägg eller väggliknande hinder. Bordet motsvaras av "_ _ _".
Problem: Hur optimerar man en hälsningsceremoni mellan Lisa och Isobel?
Eftersom sällskapet omslutes av tre väggar (eller väggliknande hinder) finns det inget sätt sätt för Isobel och 1 att enkelt uttrycka en fysisk hälsningsceremoni utan att 3 och 5 förflyttar sig från soffan. Det fanns ingen plats under bordet för Isobel att krypa in under, och det var såväl fysiskt, ekonomiskt som socialt omöjligt att använda bordet som transportsträcka. (Alternativa lösningar som att använda en wire för att utnyttja det lediga luftrummet ansågs inte realistiskt eftersom vi skulle alla vara tillbaka inom rätt kort tid och kranarbetarna var troligen på lunch under denna tid. Att använda elektronisk utrustning för att t.ex. skicka hälsningsemail, hälsnings-SMS eller bloggogram tänkte man troligen inte på i den då innevarande stunden.)
Lösningsalternativ A
Följande lösning är troligen det normala förfarandet i liknande uppkomna situationer. Inom parentes anges kostnaden för förflyttningen (se även kommentaren nedan), där vi här antar att förflyttning av en plats kostar 1 (dvs en enhet något).
a) Isobel flyttar sig en liten bit ut från bordet för att ge plats åt 5 (1)
b) 5 makar sig ut från bordet (1)
c) 3 makar sig ut från bordet (2)
d) 1 makar sig ut från bordet (3)
e) 1 uttrycker sin vänskap med Isobel (0)
f) 1 makar sig tillbaka till sin plats (3)
g) 3 makar sig tillbaka till sin plats (2)
h) 5 makar sig tillbaka till sin plats (1)
i) Isobel återställer sig på sin plats. (1)
Summa kostnad: 1 + 1 + 2 + 3 + 0 + 3 + 2 + 1 + 1 = 14
Lösningsalternativ B
Det finns en variant till A där Isobel i stället makar sig in i soffan enligt följande schema:
a) Isobel flyttar sig en liten bit ut från bordet (1)
b) 5 makar sig ut från bordet (1)
c) 3 makar sig ut från bordet (2)
d') Isobel makar sig in till plats 2 (2+1.5=3, se nedan)
e) 1 uttrycker sin vänskap med Isobel (0)
f') Isobel makar sig ut från bordet (2*1.5=3, se nedan)
g) 3 makar sig in till sin plats (2)
h) 5 makar sig in till sin plats (1)
i) Isobel återställer sig på sin plats. (1)
Summa kostnad: Summa kostnad: 1 + 1 + 2 + 3 + 0 + 3 + 2 + 1 + 1 = 14
Isobel behöver här endast förflytta sig två (2) platser vilket ger en kostnad på 2, men eftersom Isobel är fullt påklädd i vacker förvinterskrud medför förflyttning i soffa en något större kostnad per förflyttning, dvs 2 * 1.5 (kostnad 3).
Det är alltså samma kostnad för alternativ A och B (14).
Alternativ C: en mer kostnadseffektiv lösning
Efter snabbt övervägande föreslogs en "proxylösning":
Isobel kramar 5 (0.5)
5 kramar 3 (0.5)
3 kramar 1 (0.5)
1 kramar 3 (0.5)
3 kramar 5 (0.5)
5 kramar Isobel (0.5)
Totalkostnad: 6 * 0.5 = 3.
Eftersom kramar i en soffa förnärvarande har en kostnad på cirka 0.5 skulle detta ge en totalkostand på 6*0.5 = 3 var det naturligtvis bättre än de ovanstående föreslagna alternativa lösningarna.
Alternativ D: mer effektiv lösning och den implementerade
Den lösning som faktiskt implementerades var med (kind)pussar. Som tidigare anges kostnaden inom parentes.
a) 1 pussar 3 (0.1)
b) 3 pussar 5 (0.1)
c) 5 pussar Isobel (0.1)
d) Isobel pussar 5 (0.1)
e) 5 pussar 3 (0.1)
f) 3 pussar 1 (0.1)
Totalkostnad: 0.6
Detta verkar således vara det optimala tidsödande sättet om man använder hälsningsceremonierna kram eller kindpuss.
Kommentarer
I föreslagningsalternativen A och B antogs en kostnad 0 för kram mellan 1 och Isobel men i C antogs den vara 0.5. Hur går detta ihop? Jo, helt enkelt genom att här anta att vinsten för hälsningsceremonin också är 0.5. Detta kan med rätta kritiseras, och man kan här fundera på om det överhuvudtag går att jämföra kostnaden de två principiella olika hälsningsmodellerna:
* direkt hälsningsceremoni, dvs där Lisa och Isobel verkligen hälsar på varandra
* den indirekta ceremonin (proxyvarianten) där hälsningen skrev via andra på platsen närvarande personer.
Om vinsten i den direkta hälsningsmodellen är tillräckligt stor kan alternativ A eller B vara att föredra framför C och D. Vidare forskning - förhoppningsvis kompletterade med empiriska studier - inom området kan förhoppningsvis klargöra detta.
Vidare utökning av modellerna bör även studera de vinster som uppstår hos proxy-personerna. I ovanstående modell har vi helt ignorerat vinsterna för 3 och 5 som får förmånen att interagera med 1, med Isobel samt med varandra. Troligen är sådana vinster inte försummbara.
Två noter
a) Om Isobel eller för den delen 1, 2, 3, 4 respektive 6 skulle känna sig kränkta av ovanstående beskrivning bes det om ursäkt.
b) Det inses snabbt att ovanstående beskrivning - i sin nuvarande form - inte skulle bli publicerad i Hänt-i-Veckan eller liknande förmedlingsmedier, oavsett om det funnes kompletterande tillfällestagna bilder på de alternativa lösningarna. Möjligen skulle bilderna själva kunna publiceras med en något mer snärtig bildtext, t.ex. Algoritmchock kring logistiskt hälsningsceremoniproblem eller - mer troligen - Pusschock med Isobel!.
Posted by hakank at 09:59 EM Posted to Blogging | Matematik | Pyssel | Comments (9)
november 13, 2005
Bloggforum-pyssel
Nästa helg är det Bloggforum 3.0 och det ska bli både intressant och trevligt.
Inför detta evenemang kommer här ett litet pyssel som bygger på namnen för dem som hittills - 11-snåret 20051113 - anmält sig till forumet. Pysslet kan ses som ett sätt att bli bekant med meddeltagarna, eller i alla fall deras namn.
Koder för de anmäldas namn
I denna lista visas anmälningsnamnet samt en kod. Exempel:
David Hall: 201
Henrik Torstensson: 200
Pelle Sten: 200
Sara Holm Stålhand: 311
Kal Ström: 210
Jonas Morian: 201
...
Det som avgjort koden är endast anmälningsnamnet, inget annat. Ordningen i listan är samma ordning som på Bloggforum-sajten (förutom att första namnet är borttaget ur listan eftersom det tillhör tävlingen).
Pyssel
Tävlingen består i att besvara följande två frågor:
1) Vilken princip har använts för att tilldela ett namn just denna kod.
2) Vilken kod får mitt namn (Håkan Kjellerstrand) enligt denna princip.
Det först korrekta svaret på båda frågorna belönas med en ära samt en öl (*), att överlämnas t.ex. just på Bloggforumdagens kväll. Sista svarsdag är torsdagen 18 17 november 2005. Svar kan lämnas antingen i kommentarerna till denna blogganteckning eller via epost till hakank@bonetmail.com. Besvarare får även gärna berätta hur man gått tillväga för att angripa problemet.
Not: Denna tävling är på intet sätt sanktionerad av arrangörerna av Bloggforum 3.0 . Dessa arrangörer har inte heller någon insides information om det korrekta svaret på pysslet, och är naturligtvis även välkomna att deltaga.
(*) Sedvanlig disclaimer: Vi pratar här om en normalöl, inga kaggar eller specialvarianter etc. Vad gäller äran finns inga sådana begränsningar.
Uppdatering: Vinnare!
Vi har en vinnare! Håkan hakke Karlsson var den förste (och hittills ende) som klarat samtliga uppgifter, vilket han gjorde både galant och elegant. Stor heder samt en öl åt honom (och det står 3-2 i öl till honom nu). Han har även i detalj beskrivit sina blind- och felskär i sin problemsondering vilket var mycket intressant att läsa.
Den officiella tävlingen är nu alltså avslutad, men fundera gärna på det tredje delproblemet, med eller utan hjälp av ledtråden som finns nedan. Det blir dock ingen ersättning - mer än del-äran - till den som kommer med korrekt svar.
Det korrekta svaret på den tredje delfrågan kommer att publiceras i veckan. Om du är väldigt hialös får du gärna maila efter lösningen eller fler ledtrådar.
Delsvar a och b
Det var alltså tre delproblem, där en siffra i koden motsvarar ett delproblem. Första och andra siffran verkar inte ha varit så svåra att lista ut.
a) Första siffran är antal ord i namnet. "David Hall" ger 2, "Sara Holm Stålhand" ger 3, "Siv A" 2 etc.
b) Andra siffran är 1 eller 0 beroende på om antalet tecken - efter borttagninga av mellanslag - är jämt respektive udda.
Koden för "Håkan Kjellerstrand" är hittills: 21?.
Fortsatt pyssel, delproblem c
Den tredje siffran var tydligen svårare (vilket var vad jag hoppades). Här är en ledtråd och ett tips till den som vill fortsätta.
Ledtråd: Badge problem, som också var inspirationen till detta pyssel.
Tips: Det är troligen enklare att utgå från de kortaste namnen (strängarna) för att begränsa antalet olika möjliga lösningar, vilka här listas:
Maria: 100
Rasmus: 110
Eva: 101
Anna: 110
Siv A: 211
gonza: 100
mary: 111
Uppdatering Torsdag 2005-11-17: Svar på sista delproblemet
Här kommer så svaret på den sista delfrågan, dvs den sista siffran i koden.
c) Sista siffran anger om tredje sista tecknet är en vokal eller konsonant. En vokal betecknas med en etta och en konsonant med en nolla.
Den fullständiga - tresiffriga - koden för "Håkan Kjellerstrand" blir alltså 211, eftersom det tredje sista tecknet är "a" som är en vokal och ger siffran 1.
Det var det. Tack till er som skickat in era lösningar, och ett speciellt tack till Hakke som var först och även meddelat detaljerade redogörelser för problemlösningsförfarandet, vilka troligen kommer att publiceras å det offentliga, antingen här eller där. Jag är imponerad av att han löste det med endast POP - penna och papper - som extern hjälp. (Själv skriver jag nästan alltid några program för att lösa slika problem eller för att verifiera att lösningen är korrekt.)
Posted by hakank at 11:20 FM Posted to Pyssel | Comments (2)