Kategoriarkiv: Blogg

Spektrala artiklar

Redaktionens chilifest 2018

Den 9e april samlades redaktionen åter för testning.

I vår testades torkade Bhut jolokia chilin, a.k.a. Naga jolokia eller Ghost peppers. Dessa chilin är förfärligt starka och var certifierat  världens starkaste chili från 2007-2010. Styrkan av chilin mäts i en så kallad Scoville-skala. Scoville-skalan är proportionell med koncentrationen av kapsaicin, vilket orsakar den upplevda hettan av chilin. En jalapeño rankas kring 5 000 Scoville, en stark habanero rankas kring 100 000 – 300 000 och pepparsprej upp till 5 miljoner. Bhut jolokia chilin som starkast är omkring en miljon Scoville-enheter.

Ovan syns de torkade Bhut Jolokia halvorna.

Som förberedning köpte vi var sin mjölkprodukt för att skölja ner den fettlösliga kapsaicinen. Som en introduktion fick alla åt sig en ”mediumstark” spansk röd chili.  Redaktionen enades om att dessa chilin var extra milda och smakade som paprikor. Vi kryddade sedan chilina med diverse chilisåser för att piffa upp dem lite. Efter detta var det dags för grande finalen…

Vår idé var att äta en Bhut jolokia halva och sedan (försöka) recensera en film eller serie. Först efter recensionen fick recensenten ta åt sig sin munsköljande mjölkprodukt. För att få de torkade chilina ner för strupen tillsatt vi en tesked Devil’s Salad salsa.

Vi lottade om ordningen med hjälp av tärningskast. Frans blev utlottad som den första försökskaninen. Robert var andra och Sebbe valdes till tredje. Paul var fjärde i kön och till sist fick jag min tur. Nedan finns det bilder och redaktionens kommentarer om chilifesten.

Frans lyssnar på Pauls instruktioner före tagningen.

Redaktionen testar chili var verkligen inte min idé. Jag tål inte stark mat nästan alls, men å andra sidan så skall man väl alltid försöka och vara öppen mot nya upplevelser! Jag skulle recensera den första Star Wars filmen (alltså Star Wars – A New Hope, ifall någon inte visste), och trodde det skulle vara en lätt grej för jag har sett en flera gånger och kan handlingen “relativt”bra. Men detta var ju inte sant; jag var den första att testa vår chili och chilin vann mig helt 100-0. Det var länge sedan jag grät så mycket, men nu är det över :)”

– Frans

Robert är bestämd och redo att äta sin chili.

”Innan jag stoppade chilin i munnen hade jag inte egentligen tänkt på hur det skulle kännas. När jag sedan började recensera Star Wars Episode III: Revenge of the Sith förstod jag så småningom implikationerna av att inmundiga en Bhut Jolokia. Vätskor började flöda ut ur diverse hål i ansiktet och tungan kändes som om den satt fast i en skog av glödande järnspikar. Själva recensionen gick inte så bra, men åtminstone fick jag med Anakins och Obi Wans episka duell på planeten Mustafar, vars infernaliska hetta var det närmaste som kunde jämföras med upplevelsen i min mun.”

”10/10, would suffer again” – Robert

Bild på Sebbe strax efter hans recension. Frans sitter bakom med en ”Thousand Yard Stare”.

”Kryddstark mat är inte något som hör till min vardag. Jag har dock alltid trott att jag kan hantera kryddstark mat väl. Det visade sig vara fel. Helt fel. Jag försökte rescensera och återge handlingen i Pulp Fiction men jag kom inte längre än halvvägs innan jag kastade in handduken. Smärtan koncentrerade sig till en punkt längst bak i munhålan, och kändes som om ett vitglödgad knivblad pressades mot svalget. En liter yoghurt och en timme senare hade smärtan förflyttat sig ned till magen och där låg den och glödde resten av kvällen.”

”Aldrig mer.” – Sebbe

Paul ögar misstänksamt på sin chili-cocktail.

”Vi fruktade vad som var att komma, medan alla också verkade ivriga över att prova på något dumt (och kanske även en aning masokistiskt). Jag var fjärde i tur, så jag hann se hur andra redaktörer tog sig igenom det brinnande infernot förrän det blev min tur. Jag kryddade min chili med lite extra hotsauce för att försäkra en eldig upplevelse, och det var ju nog en upplevelse. Hjärtat började bulta hårdare, medan det blev svårare att prata. Recenserade kort filmen The Illusionist medan jag “njöt” av chilin. Slutliga värderingarna för min del blev 9/10 för filmen och 22/22 (lite för mycket) för chilin.”

– Paul

Till sist var det min tur. Ärligt talat så hade jag förväntat mig en mera smärtsam upplevelse. I början brände chilin förfärligt (speciellt när det började svida i näsan) men ganska strax efter det började lågorna dö ut. Jag recenserade den animerade tv-serien Avatar: The last airbender, och när jag kom till andra säsongen beslöt jag att ta en till chili, ifall den första råkade vara en svaging. Jag höll genomgången en aning kortare för de två sista säsongerna, fast jag tycker jag skulle ha klara av det en längre tid. Jag ger Avatar-serien en 4/4 och chilin en 8.3/9.

Vi filmade även allting, for science!  Här finns en kompilation av de bästa och värsta delarna av hela prövningen: https://www.youtube.com/watch?v=tu-WTqbqdn0

Tackar till Sonja Wikström för klippningen av chilifest-videon!

Waffe

PS. Om någon vill pröva på en likadan Bhut jolokia så kan ni kontakta mig!

Språk och tolkning

Eftersom jag har kodat på ett skolprojekt under hela veckoslutet tänkte jag  skriva en artikel om det. Uppgiften var att skriva en programtolk för det simpla MiniPL programmeringsspråket (tekniska specifikationen finns här för de nyfikna).

En vad?

En programtolk/interpretator (eng. interpreter) är ett program som tar in kod av ett specifikt språk och gör/kör det som koden begär. Detta är skillnad till en kompilator, som helt enkelt översätter kod från ett språk till ett annat. Programtolken är ofta uppdelad i 4  huvudsakliga delar: lexikal-, syntax- och semantisk analys, som tillsammans skapar en mängd programinstruktioner, och till sist själva körningen av instruktionerna.

Tolkningen börjar med lexikalanalys där karaktärer grupperas till ”symboler” eller ord (eng. tokens). Vi tar som exempel meningen ”Datorer har en von Neumann-arkitektur.” Karaktärerna kan grupperas till följande symboler: ”Datorer”, ”har”, ”en”, ”von Neumann”, ”-”, ”arkitektur” och till sist ”.”-tecknet. Till symbolerna tillsätts tilläggsdata, som att symbolen ”Datorer” är ett substantiv i plural, symbolen ”har” är ett verb osv.

Syntaxanalysen tar in dessa symboler, och försöker bygga upp satser och meningar av dessa, enligt specifierade grammatikregler. Satserna och meningarna sparas i ett så kallat (abstrakt) syntaxträd. Av exempelmeningen kan man bygga upp följande träd:

I programmeringsspråk är det ytterst viktigt att man kan tolka de givna symbolerna bara på ett visst sätt, dvs. språket får inte vara tvetydigt. Olikt en människa vet inte datorn vad den skall göra då en kod kan betyda två olika saker. Tvetydighet uppkommer oftast i syntaxanalysen, då man inte kan utgöra hurdant syntaxträd som ska byggas upp med hjälp av grammatikreglerna. Grammatiken måste omformas för att fixa problemet.

Efter att syntaxet är granskat så söker den semantiska analysen efter ”meningen” bakom meningarna — vad den givna koden eller texten betyder. En syntaktiskt korrekt mening behöver inte vara semantiskt korrekt. Ett typexempel är ”Färglösa gröna idéer sover häftigt.” Meningen är inte alls vettig (så länge man inte är alltför poetisk av sig), men följer ändå de svenska grammatikreglerna.

Vi tittar igen på exemplet ”Datorer har en von Neumann-arkitektur.” Den semantiska analysen för detta påstående kan bland annat bestå av att svara dessa frågor: Är datorer saker med en ”arkitektur”? Är ”von Neumann-arkitektur” en egenskap som en dator kan ha? Syntaxträdet omvandlas eller påfylls sedan med den information som man har samlat och rent syntaktiska element skärs bort, som punkter och bindestreck.

I semantisk analys av programmeringsspråk granskas det att variabel-/funktiontyperna är överensstämmande och att de variabler/funktioner som används är definierade. Syntaxträdet omvandlas samtidigt till en mängd programinstruktioner (oftast ändå i formen av ett träd) samt en ”symboltabell”, där definitionerna av variabler och funktioner sparas.

Efter allt detta kan instruktionerna köras. Under körningen sparas variabelvärden i symboltabellen, varifrån de kan återhämtas senare. Programtolken borde innehålla en liten mängd basfunktioner (som aritmetik och loopar) som sedan kan användas av programmerare för att bygga upp mer komplexa funktioner. Eller varför inte en ny programtolk?

Allt större flugsmällor för allt mindre flugor

Varning: Detta inlägg innehåller extremt dålig Java-kod.
Läs på egen risk.

Den som nån gång har läst Reddit-sidan ProgrammerHumor har kanske lagt märke till tendenserna att hitta på alldeles absurda lösningar till mycket simpla problem eller koncept.
Till exempel, för cirka 9 månader sedan var volume sliders ett återkommande skämt och därav skapades många vackra implementationer, bl.a:

 

Mer nyligen var temat om hur man ”effektivast” kollar om ett givet heltal är jämnt eller udda. Funktioner som åstadkommer detta är lättare att implementera än volume sliders, så motiverad av mina nyfunna kunskaper i Tira (Tietorakenteet ja algoritmit) bestämde jag mig naturligtvis för att testa några i Java. Metoderna nedan är inspirerade av både ProgrammerHumor och egna idéer. Några av dem kan kräva kunskap om Java eller talteori för att förstå, så en TL;DR i meme- format finns längst ner för dem som inte bryr sig om tekniska detaljer.

Metod 1: Divisionsrest

Kolla talets divisionsrest med 2. Om resten är 0, så är talet jämnt, annars udda.

  • Tråkig normie lösning
  • Använder inte ens rekursion
public boolean isEven1(int n) {
    return n % 2 == 0;
}
Metod 2: Sista siffran

Vi undersöker talets sista siffra. Om den är 1, 3, 5, 7 eller 9 är talet udda, annars jämnt. Javas indexOf()- metod för listor returnerar -1 ifall det sökta objektet inte hittas i listan. Då gör vi ju så klart en lista av de udda siffrorna och kollar om metoden ger -1 för talets sista siffra.

  • Behöver inte utföra nån äcklig aritmetik
  • Konstant tidskomplexitet, fortfarande helt för effektiv
public boolean isEven2(int n) {
    List<Character> lastDigits
        = Arrays.asList('1', '3', '5', '7', '9');
    String number = Integer.toString(n);
    char last = number.charAt(number.length() - 1);
    
    return lastDigits.indexOf(last) == -1;
}
Metod 3: Induktion

Vi använder oss av matematisk induktion. Allmänt gäller att 0 är ett jämnt tal, efter varje jämnt tal följer ett udda, och efter varje udda följer ett jämnt. Vi bygger alltså iterativt upp en array av booleans tills vi nått det n:te elementet, som vi returnerar. Dock för att undvika en OutOfMemoryError måste vi tyvärr fuska lite och emellanåt skriva över gamla värden.

  • O(n) tidskomplexitet. Från Tira vet vi ju att O(n) är bra.
  • Induktionen kräver antagandet att 0 är ett jämnt tal.  Detta kan verifieras med en av de andra metoderna.
public boolean isEven3(int n) {
    n = n < 0 ? -n : n;        //gör n positivt
    int idx = 0;
    boolean isCurrentEven = true;
 
    boolean[] evenOdd = new boolean[10000];
    while (idx <= n) {
        if (idx == 10000) {
            idx -= 10000;
            n -= 10000;
        }
 
        evenOdd[idx] = isCurrentEven;
        isCurrentEven = !isCurrentEven;
        idx++;
    }
    return evenOdd[idx - 1];
}
Metod 4: Overflow

Alla vet ju att rekursion är bra, så här har vi en härlig blandning av rekursion och error handling.

Vi antar som baskunskap att Javas Integer.MAX_VALUE,
dvs. 2^31 – 1, är ett udda tal. Detta kan igen verifieras med någon annan metod.
Om  n = 2^31 – 1 är n udda. Annars kallar vi rekursivt på funktionen med parametern n + 2. Så klart, om n är ett jämnt tal borde den eventuellt hoppa över 2^31 – 1 och orsaka en OverflowException. Men eftersom Java hanterar den här situationen utan att klaga, måste vi använda Math.addExact()- metoden som explicit ger en Exception ifall vi går över 2^31 – 1.

Rekursionen upprepas i värsta fall ca 2^30 gånger, så en StackOverflowError orsakas långt före det. Vid detta skede avbryter vi rekursionen och startar om med en hjälpvariabel som säger hur långt vi kommit förut.

  • O(2^31 – n) tidskomplexitet. Större tal får snabbare svar.
  • isEven4(1200000000) svarade true på endast 23 sekunder.
int offset;
 
public boolean increment(int n) {
    if (n == Integer.MAX_VALUE) {
        return false;
    }
    try {
        n = Math.addExact(n, 2);
        offset += 2;
        return increment(n);
    } catch (ArithmeticException e) {
        return true;
    }
}
 
public boolean isEven4(int n) {
    offset = 0;
    while (true) {
        try {
            return increment(n + offset);
        } catch (StackOverflowError e) {
            //inget fel här, moving on...
        }
    }
}
Metod 5: Goldbach

En välkänd hypotes inom talteorin är den s.k. Goldbach Conjecture, som säger att varje jämnt tal större än 2 kan uttryckas som summan av två primtal. Resultatet har inte bevisats för godtyckligt stora jämna tal, men det har verifierats med dator för tillräckligt stora tal för våra ändamål.
Det enda jämna primtalet är 2, dvs det största jämna talet som kan uttryckas som summan av två jämna primtal är 4. Alltså om vårt tal är större än eller lika med 6 söker vi udda primtal vars summa är vårt givna tal. Annars undersöker vi talet med Metod 4.

Hur kan vi då visa att ett givet tal är ett primtal? Vi använder så klart Wilson’s Theorem. Enligt denna sats är n ett primtal om och endast om talets (n-1)! divisionsrest med n är n-1, dvs.
(n-1)!\ \equiv\ -1 \pmod n
Till detta ändamål har vi hjälpfunktionerna modFactorial och isPrime.

  • Antagligen O(n^3) tidskomplexitet. Funktionen modFactorial är O(n) och isEven5 har en dubbel loop.
  • Körtiden varierar kraftigt mellan udda och jämna tal av ungefär samma storlek:
    isEven5(4000) gav true på 2 sekunder och isEven5(4001) gav false på cirka 15 sekunder.
    isEven5(10000) gav true efter 30 sekunder. Hur länge tog det för isEven5(10001)?
  • Använd alltså den här metoden om du redan anar att ditt tal är jämnt!
public int modFactorial(int p, int mod) {
    if (p < 1) {
        return -1;
    }
    long n = 1;
    for (int i = 1; i <= p; i++) {
        n = n*i % mod;
    }
    return (int) n;
}
 
public boolean isPrime(int n) {
    if (n < 2) {
        return false;
    } else {
        return modFactorial(n - 1, n) == n - 1;
    }
}
 
public boolean isEven5(int n) {
    n = n < 0 ? -n : n; //gör n positivt
    if (n < 6) {
        return isEven4(n);
    }
 
    for (int i = 3; i < n; i++) {
        if (!isPrime(i)) {
            continue;
        }
        for (int j = 3; j <= i; j++) {
            if (!isPrime(j)) {
                continue;
            }
            if (i + j == n) {
                return true;
            }
        }
    }
    return false;
}

Här tog kreativiteten och/eller tålamodet slut, för om vi vill kan vi göra godtyckligt ”effektiva” algoritmer, men de är inte nödvändigtvis så intressanta. Men nu har vi ju jobbat under premissen att vår metod ska ge ett svar för just det talet vi stoppar in, och att svaret ska vara rätt. Vad om vi ändrar på spelreglerna lite? En bonusmetod, isEven6, hittas under länken längst ner.

Det här inlägget kunde tolkas både som en uppmuntran och en varning. Avsiktligt dålig kod kan vara väldigt underhållande och lära en tänka på problem på nya sätt (om det här är en bra eller dålig sak är upp till läsarens tolkning). Å andra sidan är dessa metoder det oundvikliga resultatet av att spendera helt för mycket tid på Tira.

TL;DR

https://i.imgur.com/TUYX6Tq.jpg