« december 2008 | Main | februari 2009 »

januari 31, 2009

Constraint programming modeller i Comet

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

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

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

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

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

januari 15, 2009

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

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

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

Posted by hakank at 08:46 EM Posted to

januari 05, 2009

Isomorfa ord (Isomorphic Words) - programmet

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

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

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

     python isomorphic_words.py word exact_match language

där argumenten har följande betydelse:

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


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


     python isomorphic_words.py abbab

Med resultatet:


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

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

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

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

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


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


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

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

januari 04, 2009

Programspråket Icon och några Project Euler problem

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

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


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

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

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

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



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

#
# The mandatory main procedure
#
procedure main()

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

Problem 1

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

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


Problem 2

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

end

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

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


Problem 3

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

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

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

end


Problem 4

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

# Three different versions

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

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

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

end

procedure myMax(L)

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

return(maximum)

end

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


Problem 5

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

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

end


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

return i
end


Problem 6

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

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

end


Problem 7

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

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

end


Problem 8

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

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

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

write("this_max: ", this_max)

end


Problem 9

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

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


Problem 10

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

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

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

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


Huvudsajter
Icon
Unicon

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


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

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

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

januari 02, 2009

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

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

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


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

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

Så, resten är musikaliska inspirationer.

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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