Drabbad av virus

Det har varit ganska glest mellan uppdateringarna här på bloggen ett tag, och jag misstänker att åtminstone en del av min trogna läsarkrets[1] börjat frukta att jag fallit offer för något slags östasiatiskt virus. Ett sådant gjorde ju entre för dryga tiotalet år sedan, och det är detta som jag nu fallit pladask för. Men nej, jag pratar inte om Covid-19, eller någon annan covid-släkting — jag pratar om Sudoku.

Det började lite lätt med att jag någon gång under förra vintern upptäckte att The Guardian på helgerna publicerade något som de kallade »killer sudoku». Detta fenomen var åtminstone relativt nytt för mig, och jag fann snart att även om de oftast var någon nivå svårare än vanliga vanilj-sudokus, så kunde de också bjuda på mer intressanta logiska slutledningar.

Men sjukdomen bröt inte ut på allvar förrän jag i just The Guardian stötte på en artikel om ett märkligt youtube-fenomen, en kanal vid namn Cracking the Cryptic, där två distingerade engelsmän löser sudokus och andra logiska problem av varierande svårighetsgrad, från dunderknepiga till snudd på omöjliga, i realtid[2]. Den video som länkades till i artikeln behandlar en så kallad »miracle sudoku», som består av en nästan tom sudoku, där bara två(!) siffror angetts, och tre extra villkor — (1) två likadana siffror får inte placeras ett springarsteg ifrån varandra; (2) två likadana siffror får inte placeras ett kungssteg[3] ifrån varandra; och (3) två konsekutiva siffror får inte placeras i ortogonalt angränsande rutor[4]. Så här ser miraklet ut:

Erkänn att det är svårt att tro både att det finns en unik lösning, och att det i så fall går att hitta den utan datorhjälp. Men det är faktiskt inte alls så knepigt, visade det sig när man kom igång; den enda »krisen» kommer när man placerat in alla ettor och tvåor som går att placera, och måste börja placera treor — där måste man endera vara intelligent, som Simon Anthony i en video som för tillfället setts sådär 1,5 miljoner(!) gånger, eller ihärdig, som under-över-eller-var-jag-nu-är-tecknad[5].

Riktigt allvarlig blev dock inte sjukdomsbilden förrän min nyfikenhet drev mig att googla efter en sajt som CtC, som Cracking the Cryptic brukar förkortas, hämtat ett flertal av sina mest intressanta objekt från — Logic Masters Germany. Särskilt deras lista med sudokus, med variationer av alla möjliga slag fångade mig. Jag inser naturligtvis att jag inte borde sprida sjukdomen så här lättvindigt, men här kommer några av de problem som jag fastnat för. De prövas, naturligtvis, på egen risk — you have been warned…

  • Fyra små rätter. Det här är förmodligen det enklaste problemet i den här listan; det består av fyra 6*6 sudokus med lite olika interna varianter, som länkas samman av en summa där (oftast) två av de ingående delproblemen ger bidrag. Lite matematiska kunskaper skadar inte, som till exempel att triangeltalen för 5 och 6 är 15 respektive 21.
  • 144, men inte 35. Det här är likaledes förmodligen det svåraste av de här uppräknade problemen; om man inte har en matematisk överblick måste man ta hjälp av papper och penna, Notepad eller, som i mitt fall, Excel[6]. Kompositören har delat in de 81 sudoku-rutorna i sexton fem-rutiga områden (så kallade pentominos) och en överbliven ruta, samt meddelar att alla utom en har två egenskaper, förutom den »vanliga» att inga dublettsiffror är tillåtna: (1) produkten av de fem talen i pentominon är jämnt delbar med 144, och (2) produkten är inte delbar med 35. Om du till äventyrs skulle fundera på att skapa ett problem där alla 16 pentominorna följer denna enkla regel, så kommer du snart att upptäcka att den elaka verkligheten sätter upp vissa hinder i din väg. Meddela mig gärna om du lyckas, men jag hoppas du ursäktar om jag tar ett eller annat andetag under tiden.
  • Oss fyrkanter emellan. Ett annat problem med en utpräglat matematisk grundidé (enligt uppgift är kompositören en amerikansk matematiklärare). Här står kvadrater för de huvudsakliga ledtrådarna, kompletterade av några diagonalsummor som av någon anledning går under namnet »little killers».
  • En schacksudoku. Att matematik och sudoku hör samman är väl ganska naturligt, men det finns faktiskt en hel del sudokus med schackinslag också, inte bara de anti-regler som var viktiga komponenter i miraklet ovan. Det här är en av dem; nio kungar, representerade av ettor, måste skyddas från schackar av torn, löpare och springare (2,3 och 4). En intressant idé, som fått en genomgång på CtC.
  • En genial idé. Ett av de första problem jag löste på sajten, och jag prickade ett mästerverk; det är inte bara jag som tycker så — med 35 lösare har den fortfarande en ranking på 100%, en högre uppskattning är svår att få. Idén är lika enkel som genial; ett antal »mördarlådor», där summan av de två talen är exakt tio, några »termometrar, som indikerar siffror i en stigande sekvens räknat från »kvicksilverkulan», och det antispringarvillkor vi bekantade oss med i mirakelsudokun. Problemet får mig att tänka på Göran (Forslund); det här är ett problem han skulle gillat, eller till och med kunnat komponera. (Även detta problem har lösts av CtC.)
  • En golvläggarsudoku.Till slut ett problem som i skrivande stund enbart har en (officiell) lösare, och det här är ett försök att ändra på den saken. Att det bara är en lösare betyder emellertid inte att det är ett oerhört svårt problem; snarare är det en indikation på att reglerna var ganska oklart formulerade från början. Det som gjorde att jag kunde lösa den var att jag skrev en dold kommentar (dvs en kommentar som bara kommentatorn, författaren och de som löst problemet kan se) där jag förklarade mina (som det skulle visa sig felaktiga) tolkningar av reglerna, och varför jag såg mig tvungen att ge upp. Författaren förtydligade då reglerna, vilket gjorde att jag ganska raskt kunde finna lösningen. Så gör gärna ett försök att knäcka nöten; om inte annat för att det inte är varje dag som kvadratroten ur 20 innehar en viktig roll i en sudoku.

Jag hoppas att du kunnat njuta av någon eller några av dessa logiska läckerheter, utan att bli smittad av den åkomma som jag råkat utför. Tyvärr använder jag inte munskydd, men i mitt nuvarande skäggiga tillstånd lär det inte ha gjort särskilt stor nytta i alla fall.

And now for something not completely different…

För något år sedan fick jag ett så kallat ryck, och bestämde mig för att försöka lära mig något om logikprogrammering. Valet föll på Prolog eftersom jag relativt nyligen hittat en bok om detta språk på ett antikvariat[7]; någonstans i bakhuvudet fanns säkert tanken att det borde relativt lätt gå att lösa sudokus med ett sådant språk. Jag laddade också ned GNU-Prolog, och började läsa, googla och testa.

Innan jag fortsätter bör jag komma med en brasklapp av ansenliga mått; mina kunskaper i Prolog är forfarande på nybörjarnivå, och alla uppgifter om språket jag kommer att uttrycka och de programexempel jag visar bör betraktas som just synpunkter från en nybörjare i logikprogrammering, men med relativt stor erfarenhet av »traditionell» programmering.

Jag började med klassiska problem av den typ som Göran tog upp i sin problembok, och vars lösning jag avslöjade i mina errata till Görans bok. Så här ser mitt program ut:

solvetrav :- Trav = [[1,_,_],[2,_,_],[3,_,_]],
  members([[_,ptro,_],[_,gnagg,_],[_,galopp,_]],Trav),
  members([[_,_,nisse],[_,_,janne],[_,_,sven]],Trav),

  member([3,gnagg,_],Trav),
  member([2,_,sven],Trav),
  nonmember([1,_,janne],Trav),
  nonmember([_,galopp,nisse],Trav),

  write(Trav),
  nl,
  fail.

Den första raden bestämmer att lösningen (»Trav») ska vara en lista bestående av tre listor, där varje lista består av tre uppgifter; tillsammans med de två övriga raderna i det första blocket ser man att de är placeringen, hästnamnet och ägaren i den ordningen (variabeln »_» är speciell, och uttolkas »här kan du stoppa in vad du vill; jag bryr mig inte».)

Det följande kodblocket anger de uppgifter man känner till om loppet — Gnägg kom trea (det var, har jag för mig, den häst som bröt benet), Svens häst kom tvåa, Jannes häst vann inte och Nisses häst hette inte Galopp. Kommatecknen mellan uppgifterna fungerar som logiska »och»; så länge som det går att konstruera en lösning fortsätter programmet, annars backar det något eller några steg för att pröva något annat.

Det sista blocket är ett standardtrick för att finna alla möjliga lösningar; skriv ut lösningen och en ny rad, samt låtsas att det inte var den här lösningen man sökte. Jag bör kanske påpeka att »members» och »nonmember» inte är standardrutiner i Prolog, utan sådant som jag hittat på nätet, så programmet som sådant går inte att köra direkt utan att man lägger till de komponenterna.

Innan jag fortsätter känner jag mig förpliktigad att försvara mig, eller åtminstone förklara mig. När allt kommer omkring ställde jag ju i början av 90-talet upp tre enkla regler för användandet av rekursion:

  • Använd inte rekursion.
  • Använd inte rekursion!!
  • Använd rekursion då, om du absolut måste, men skyll inte på mig om det leder till kärnvapenkrig, pandemier eller att himlen trillar ned över ditt huvud.

Åkej, jag kanske inte hotade med pandemier på den tiden, men jag hoppas den allmänna avogheten mot rekursion som dessa rader är avsedda att förmedla framgår tydligt. Vad jag eventuellt inte berättade för alla som fick ta del av mina rekursionstips var den bakomliggande historien.

Under min tid som programmeringssupport vid NSC fick jag en gång ett mejl, där en person frågade varför ett visst program bara var 2-3 ggr snabbare på Crayen än på användarens arbetsstation. Programmet i fråga visade sig beräkna (om jag minns rätt) — det 40:e fibonaccitalet, uträknat med den rekursiva formel man ibland kan hitta i mindre nogräknade läromedel. Jag är fast motståndare till dödsstraff, men skulle jag tvingas ange ett brott som förtjänar ett sådant straff bör sagda läromedels författare snarast vidta åtgärder som att byta namn och skaffa lösskägg[8]. Tiotalet år senare såg jag en IT-journalist skriva något i stil med att hen testade en dator med en »tung beräkning», vilket visade sig vara en fibonacciberäkning av liknande slag.

Jag gissar att jag skulle kunna räkna ut det 40:e fibonaccitalet med papper, penna och, säg, en halvtimmes arbete; och jag försäkrar att all aritmetik jag kan utföra på en halvtimme ska en dator värd namnet klara av att utföra på mindre än en mikrosekund. Med andra ord, de 118[9] CPU-sekunder som vår Cray X-MP använde för att beräkna det 40:e fibonaccitalet hade kunnat användas till bättre ting. Som en jämförelse tog en standardkörning av mitt program för att beräkna en viss typ av spektrum för en mellanstor molekyl (ca 40-50 atomer) ca 90 CPU-sekunder på samma maskin.

Numera är jag, som kanske framgått, inte fullt lika rabiat motståndare till rekursion, och har till och med börjat använda det här och var själv, när ingen ser på. Jag har därför modifierat den tredje punkten ovan till »Det är tillåtet att använda rekursion, om du först skaffat dig 20 års erfarenhet av ett riktigt programmeringsspråk[10][11].

Det finns ett grundläggande problem här, vars existens jag för tillfället inte hittar någon författare som vågar erkänna rakt av. Det bästa jag kan erbjuda är ett citat ur Concepts of programming languages (3. ed) av Robert W. Sebesta: »One of the essential characteristics of logic programming languages is their semantics, which is called declarative semantics. The basic concept of this semantics is that there is a simple way to determine the meaning of each statement, and it does not depend on how the statement might be used to solve a problem.» Låt mig formulera om det så som jag har förstått det: »Prolog och språk av liknande typ gör att användaren bara behöver specifiera alla kända data, hur lösningen sedan ska hittas bestäms av programmet vid körningen.» Min åsikt om detta är att det uttrycker ett slags önskedröm, vars förverkligande möjligen ligger i en (avlägsen?) framtid, och att de program som för tillfället existerar kan i bästa fall ses som leksaker, som är bra på att lösa vissa typer av problem, men kräver ingående kännedom om hur programmet fungerar för att lösa dessa problem. Och detta förklarar/försvarar mitt intresse i Prolog — som pensionär är jag fri att välja mina leksaker som jag vill! SDS[12], OHS[13] och QED.

Du är inte övertygad om att Prolog är usel på att hitta lösningsmetod själv? Eller tror inte att man som programmerare kan hjälpa till? Låt mig då visa ett exempel; ganska extremt, det medges, men samtidigt hoppas jag det är illustrativt.

Problemet jag tänkte ta upp är följande, från 536 Puzzles & Curious Problems av en av alla tiders största problemmakare — Henry Dudeney. Detta är närmare bestämt nummer 393 i boken:

There is something very fascinating about star puzzles. I give an example, taking the case of the simple five-pointed star. It is required to place a different number in every circle so that the four circles in a line shall add up to 24 in all the five directions. No solution is possible with ten consecutive numbers, but you can use any whole number you like.

Och utan några alltför stora krumbukter, här kommer lösningsförslag 1, den stendumma varianten:

solvefivestar :- Numbers = [N0,N1,N2,N3,N4,N5,N6,N7,N8,N9],
  integerlist(1,18,Tal),
  member(N0,Tal),
  member(N1,Tal),
  member(N2,Tal),
  member(N3,Tal),
  member(N4,Tal),
  member(N5,Tal),
  member(N6,Tal),
  member(N7,Tal),
  member(N8,Tal),
  member(N9,Tal),
  uniquelist(Numbers),

  (N0+N5+N6+N2 =:= 24),
  (N0+N9+N8+N3 =:= 24),
  (N1+N5+N9+N4 =:= 24),
  (N1+N6+N7+N3 =:= 24),
  (N2+N7+N8+N4 =:= 24),

  write(Numbers),
  nl,
  fail.

»integerlist» och »uniquelist» är två enkla komponenter som jag skrev för att dels skapa en lista med heltal som kunde bli aktuella (som synes räknade jag bara med positiva heltal), samt att kontrollera att det inte fanns dubletter i lösningslistan. 18 valde jag efter en snabb huvudräkning, som sa att 18+1+2+3 = 24, så något tal större än 18 kunde med säkerhet inte komma ifråga i lösningmängden.

Här har jag bara deklarerat vilka tal som kan vara aktuella, och vilka relationer som gäller mellan dem, utan några krusiduller. När jag körde programmet hände dock ingenting. Jag vill minnas att jag bröt efter så där en och en halv timma, och då hade programmet inte ens hittat en enda lösning. Jag kan visserligen utesluta möjligheten av att den fortfarande skulle ha letat om jag inte tryckt på ctrl-c, men det beror mer på att den dator den körde på säckade ihop för gott för en månad sedan.

Skam den som ger sig. Jag misstänkte naturligtvis att den algoritm som programmet använde i princip kunde betecknas som 10 for-loopar inuti varandra, och det kunde ju förklara varför den tog så lång tid på sig. Ett rimligt försök att snabba upp beräkningen borde då vara att presentera de begränsande villkoren så snart som möjligt. Denna tanke ledde till detta detta program, med lite mänsklig hjälp:

solvefivestar(Const) :- Numbers = [N0,N1,N2,N3,N4,N5,N6,N7,N8,N9],
  integerlist(1,18,Tal),
  member(N0,Tal),
  member(N2,Tal),
  member(N5,Tal),
  (N6 is Const -(N0+N2+N5)),
  member(N6,Tal),
  member(N3,Tal),
  member(N8,Tal),
  (N9 is Const -(N0+N3+N8)),
  member(N9,Tal),
  member(N1,Tal),
  (N4 is Const -(N1+N5+N9)),
  member(N4,Tal),
  (N7 is Const -(N1+N6+N3)),
  member(N7,Tal),
  uniquelist(Numbers),
  (N2+N7+N8+N4 =:= Const),

  write(Numbers),
  nl,
  fail.

Som synes är detta program inte lika enkelt att förstå som förra försöket; i stället för ett block med deklarationer och ett med relationer, så har jag den här gången introducerat relationerna så tidigt som möjligt för att begränsa de nödvändiga looparna. Och resultatet är över förväntan; på min gamla dator, den som säckade ihop, spottade den ut ett par skärmsidor lösningar på lite drygt sex sekunder, och ersättaren, den som jag använder nu, tar bara 4.5 sekunder på sig. En remakaber[14] skillnad, eller hur?

Nu är jag naturligtvis inte den förste som noterat att Prolog inte är särskilt bra på den här typen av problem. Jag hittade en artikel på nätet som beklagade sig över att man fortfarande lärde ut ”is” och aritmetisk likhet (=:=), när det fanns så mycket bättre möjligheter (om jag minns rätt kallade författaren det hela för constraint programming over finite domains, vilket jag inte vågar mig på att försöka översätta). Idéerna i artikeln resulterade i följande program:

solvefivestarcp(Const) :- Numbers = [N0,N1,N2,N3,N4,N5,N6,N7,N8,N9],
  fd_domain(Numbers,1,18),
  fd_all_different(Numbers),

  N0+N5+N6+N2 #= Const,
  N0+N9+N8+N3 #= Const,
  N1+N5+N9+N4 #= Const,
  N1+N6+N7+N3 #= Const,
  N2+N7+N8+N4 #= Const,

  fd_labeling(Numbers),

  write(Numbers),
  nl,
  fail.

Lägg märke till den strukturella likheten med mitt första, stendumma, försök; först tala om hur lösningen bör se ut, sedan villkoren. Och för den som är bekant med Sidney Harris’ klassiska teckning, det är i fd_labeling miraklet sker — där används den givna informationen på något intelligent sätt; min nya dator behöver nu bara en kvarts sekund på sig för att lista alla lösningar.

Jag hoppas detta exempel visar att det fortfarande är viktigt att veta vad man pysslar med — att skriva in data och regler/relationer, för att sedan låta maskinen överta alla beräkningar är än så länge bara en dröm.

Låt mig avsluta med att begå det brott jag tidigare yrkade på dödstraff för, men i en form som förvisso inte meriterar en så hård påföljd. Jag har nämligen sedan någon månad tillbaka övergått till en av Prologs efterföljare, Picat, som tagit med sig många av de goda sidorna i Prolog, och samtidigt rättat till en del av missarna. Så här försöker man fixa till fibonacci-problemet (från boken »Constraint Solving and Planning with Picat», som kan laddas ner som en PDF-fil från sajten i länken ovan).

table
fib(1) = 1.
fib(2) = 1.
fib(N) = F, N > 2 => F = fib(N-1)+fib(N-2).

Det som räddar författarna (och mig) från galgen är ordet »table»; detta anger att resultat ska cachas, vilket enligt författarna förvandlar beräkningstiden från exponentiell till linjär. Jag har inte undersökt detta närmare, men det låter underligt i mina öron. Om resultatet cachas fullt ut, borde beräkningstiden vara konstant om resultatet fanns i cachen, linjärt om det måste beräknas. Men hur som helst kommer man inte ifrån att rekursion kräver utrymme på stacken, så även om rekursionen i det här fallet är acceptabel, så är det inte det bästa sättet att utföra beräkningen. SDS.


Fotnoter:

  1. Här antar jag alltså att en sådan existerar, vilket naturligtvis är mer baserat på en önskedröm än något slags verklighetsunderlag. []
  2. Det händer dock att verkligheten tränger sig på och genererar ett avbrott, och en gång har till och med en av dem gjort en miss och tvingats ge upp (för att sedan i ett tillägg förklara sin miss och korrigera den). []
  3. Egentligen räcker det ju att säga ett ferssteg ifrån varandra, eftersom kungens raka stegmöjlighet redan är förbjuden med standardsudokuregler. []
  4. eller ett vesir-steg från varandra, om vi ska fortsätta med (fantasi)schackpjäs-terminologin []
  5. Inte första gången, och antagligen inte sista, där den stupida envishet jag understundom kan utveckla kan misstolkas som ett utslag av intelligens. []
  6. Eller, för att vara mer exakt, Calc, Libreoffice’ klon av Excel. []
  7. Det är nu inte hela sanningen, eftersom min boksamling även innehåller en bok om LISP, men jag vill ju inte framstå som en person som gör saker lite slumpartat, så därför måste jag uppfinna ett skäl för mitt handlande. []
  8. Detta senare försök att förändra utseendet kan dock verka misstänkt på eventuella kvinnliga fibonaccirekursionister, så dessa bör nog försöka andra förklädnader. []
  9. Jag är inte säker på det exakta antalet, men mitt undermedvetna propsar på att skicka fram detta tal. Det är i alla fall inte helt taget ur luften. []
  10. Och med ett »riktigt programmeringsspråk» avses naturligtvis Fortran. []
  11. Det betyder visserligen att jag inte skulle vara berättigad att använda rekursion än, så jag har för mitt samvetes skull lagt till att tre års Pascal-programmering må i särskilt behjärtansvärda fall få ersätta ett års »riktig» programmering. []
  12. Så Det Så []
  13. Och Hör Sedan []
  14. Nej, jag har inte stavat fel; jag kunde bara inte bestämma mig för om skillnaden var makaber eller remarkabel, så jag skapade ett nytt ord. []

Sortera med Linux

Linux är på många sätt ett charmigt operativsystem. Till att börja med är det (oftast) gratis, även om det finns skumma element som då och då försöker göra pengar på det eller delar av det. En annan klämmig sida av Linux är de många frivilliga insatser som gjorts och görs av utvecklare för att uppdatera koden och lägga till nya finesser; tycker du någon detalj saknas kan du ofta ladda ner källkoden, skriva till lite kod, och skicka in för testning och eventuell användning i en kommande release[1]. Och tycker man att ett projekt håller på att spåra ur kan man oftast »gaffla» det, dvs starta ett nytt projekt baserat på koden vid ett visst tillfälle i utvecklingen, se till exempel historien om Mambo och Joomla.

Men så är det ju det här med att sortera text under Linux. Jag har varit med i svängen under en längre tid, och har hittills inte stött på något datorsystem som varit särskilt lyckat vad det gäller sortering, men Linux tar ändå priset för det mest sofistikerade upplägget, kombinerat med det mest patetiska misslyckandet. Jag har för eget bruk hackat min Opensuse-burk så att den sorterar som jag vill, men innan jag berättar om mitt hack måste jag beskriva vari problemet ligger; hav tålamod några skärmsidor![2]

Låt oss anta att vi vill sortera följande illustrativa och informativa textmassa:

aåä  
a äå 
å aä 
å äa 
a åä 
aäå  
aå ä 
ä aå 
aä å 

Om jag nu, med rosor på kind och solsken i blick, skriver sort fil, så sorterar datorn om texten på nedanstående sätt:

å äa 
ä aå 
a äå 
aä å 
aäå  
å aä 
a åä 
aå ä 
aåä  

Ärligt talat är det inte självklart att texten faktiskt är sorterad och inte randomiserad på något sätt; visserligen har jag »amerikansk engelska» som default, men måste den använda en så bisarr sorteringsalgoritm? Om någon vill försöka lista ut hur sorteringen gått till, så gömmer jag lösningen i den kommande fotnoten; men jag kommer strax att avslöja en av »finesserna» i sorteringen, så i så fall bör ni klura ut det innan ni läser vidare.[3].

Vad händer då om man använder »lokalen» (min översättning av det engelska »locale») för svenska? Lokalen för sortering styrs av miljövariabeln LC_COLLATE, och för att för att få svensk sortering kan man enklast skriva LC_COLLATE=sv_SE.UTF-8 sort fil, så får man svensk sortering bara för detta enstaka kommando[4]. Nu blir resultatet som följer:

aåä  
a åä 
aå ä 
aäå  
a äå 
aä å 
å aä 
å äa 
ä aå

Det börjar likna något, eller hur? Ordningen mellan a, å och ä är fixad, men det finns fortfarande ett problem — blankslag hanteras som om de inte existerade, vilket gör sorteringen fel i mina ögon. Ärligt talat vet jag inte hur Svenska Akademin, eller vad det nu kan vara för instans som standardiserar svenska sorteringar, ser på saken, men för mitt ändamål, ett KWIC-index över Anders F Rönnbloms texter, kändes metoden att ignorera blankslag helt bakvänd.

En snabb googling avslöjar att jag inte är den ende att förfasa mig över detta, men som så ofta är de som frågar och svarar engelsktalande, och den lösning de flesta nöjer sig med är att använda kollationeringsordningen »C», som återskapar hur datorer sorterade på stenåldern, då bara engelska talades i datorvärlden. Och då ser resultatet ut så här:

a äå 
a åä 
aä å 
aäå  
aå ä 
aåä  
ä aå 
å aä 
å äa

Om vi undantar det lilla faktum att »å» och »ä» blivit omkastade så är det så här jag skulle vilja att det ser ut.

Det »traditionella sättet»[5] att lösa problemet är att på något sätt mappa om texten så att »å» blir »ä» och vice versa, och sedan mappa tillbaka efter sorteringen; seds kommando »y» är som gjort för denna typ av hack. Men den här gången[6] beslöt jag mig för att försöka göra detta enligt Linux alla regler.

För att göra en lång historia kort, jag har ännu inte lyckats. Såvitt jag förstår borde det gå att lösa med de metoder som man använder för att mappa om »basfilen» till lokaler som till exempel den svenska, men jag har inte hittat något sätt att göra det. Huvudproblemet är att alla omdefinieringar jag sett inleds med kommandot »reorder-after», men space-tecknet, det som jag vill ändra, är definierat som det första tecknet i kollationeringsordningen. Jag har därför gått in i den bamsiga huvudfilen och ändrat på egenskaperna hos det allra första tecknet i sorteringsordningen, vilket känns ungefär som att göra en månghundraåriga ek en decimeter kortare genom att kapa den alldeles intill roten, ta av en decimeter på stammen, och sedan limma ihop rasket igen. Eller, som Otis Gibbs uttrycker det i sin fantastiska poddradio »Thanks for giving a damn»: I’d like to say up front that I haven’t the slightest idea what I’m doing, but I decided to do it anyway.

Här är mitt recept för att fixa problemet:

1. Leta rätt på filen iso14651_t1_common; under OpenSuse 12.3 ligger den i foldern /usr/share/i18n/locales, men det kan säkert vara annorlunda i andra distributioner. Öppna filen med lämplig editor[7], och gå till den rad som ser ut så här:

<U0020> IGNORE;IGNORE;IGNORE;<U0020> # 32 <SP>

Ändra denna till nedanstående:

#<U0020> IGNORE;IGNORE;IGNORE;<U0020> # 32 <SP>
<U0020> <BAS>;<BAS>;<MIN>;IGNORE   # 32 <SP>

Den första raden är naturligtvis bara originalet, sparat som en kommentar för att hålla reda på hur det såg ut innan ändringen; det är en god programmerarpraxis att behålla gammal kod ifall den nya visar sig innebära oväntade katastrofer. Den andra raden utför själva ändringen, och betyder, om jag förstått det rätt, att blanktecknet inte totalt ignoreras, som i raden ovan, utan sorteras som tecknet »BAS», vilket egentligen betyder »utan diakritiska tecken» och är definierat bland diverse arabiska diakritiska tecken; min åsikt är att det torde vara svårt att hitta ett tecken som är mer kemiskt rent på dylika än just blankslaget, och därför valde jag att återanvända detta snarare än att skapa ett nytt tecken.

2. Kompilera en ny lokal med kommandot

localedef -i sv_SE -f UTF-8 sv_SE.UTF-8

Sådär! Nu blir äntligen resultatet som förväntat:

a åä 
a äå 
aå ä 
aåä  
aä å 
aäå  
å aä 
å äa 
ä aå 

Implementeras på egen risk; inga garantier lämnas…


Fotnoter:

  1. En favorit är den tidszonsdatabas som alla Linux-system använder, och som innehåller en fantastisk mängd ihopsamlade uppgifter från runt om i världen. Ett exempel på den akribi som deltagarna ådagalägger, och som dokumenteras via kommentarer i koden: »During World War II, Germany maintained secret manned weather stations in East Greenland and Franz Josef Land, but we don’t know their time zones. My source for this is Wilhelm Dege’s book mentioned under Svalbard.» []
  2. Som den i hackermentalitet insatte säkert misstänkt är det faktiskt andra gången jag implementerar detta hack, det första hacket skrevs över vid en uppdatering; denna blogga är ett försök att korta av implementeringstiden för det tredje hacket, och därefter följande hack. []
  3. För att få denna sortering måste man göra tre saker: 1. Alla blankslag ignoreras, dvs sorteras som om de inte existerade; 2. I fas ett betraktar man alla a-liknande tecken som »a», vilket tillsammans med punkt 1 gör att alla nio raderna i min testfil förvandlas till »aaa»; 3. I fas 2 tas hänsyn till de diakritiska tecknen i ordningen »a», »å», »ä», men strängarna sorteras bakifrån; detta ger den ordning som visas ovan. []
  4. Under förutsättning att man anväder unicode, närmare bestämt dess kodning UTF-8. För att gå händelserna lite i förväg så var mitt beslut att konvertera en nyckelfil till UTF-8 från ISO 8859-1 den huvudsakliga anledningen till att jag övergav »det traditionella sättet» som jag nämner nedan. []
  5. Det vill säga, det var så jag löste detta problem på den gamla goda ABC800-tiden i mitten av 80-talet. Metoden fick sedan hänga med in i Unix-tiden, och jag använde den till och med i den första versionen av f-indexet för sådär tio år sedan. []
  6. Eller, mer korrekt — den förra för ett par år sedan, om ni är med på fotnoterna. []
  7. Härmed avses naturligtvis emacs, och inte vi. []