Kategoriarkiv: 2018

Texter från 2018

En limerick för årsfesten LXXXV

En massa spektrumiter
stolar på barer sliter
Torsdagkvällen var snabb
och slog till som en klabb
Vasagatan bjöd än en gång öl i liter

Fredag blev det till näst
de flesta mådde som pest
Förkör på Klubben
kolla in snubben
Som visar hur man häver och är bäst

Sedan blev det fest och mat
finklädd satt man sig ner vid sitt fat
Med sång och tal
även en liten bit bal
Ja, årsfesten skapade faktiskt inte hat

Till sillis man sedan gick
uppiggande mat man fick
Snipp, snapp, snut
så var veckan slut
Jubileumsårsfesten var nog riktigt chick

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

 

Palles musikhörna: En πanolåt

Dags för en låt som är mycket starkare bunden till matematik. Låten är en helt söt PI-anolåt (padum tss), där decimalerna i pi används för att bestämma tonläge och längd på noterna. I bakgrunden spelas även ett ackompanjemang, som får melodin att klinga riktigt trevligt. Låten är skapad av personerna bakom YouTube-kanalen YourMJK. Kolla gärna in även andra låtar baserade på pi. Google/Youtube är din vän.

Kan också av egen erfarenhet säga att sättet hur de gjort låten här är mycket smartare än vad jag själv gjorde då jag i tiderna provade mig på att göra en låt av pi. Vill minnas att det fungerade ganska dåligt att ge tal åt varje halvt tonsteg. Därför kunde däremot en musiker kanske tycka att den här låten är lite tråkig, eftersom tonlägen är valda att ha ”rena” intervall mellan varandra, vilket bidrar till att låten inte blir en enda soppa då man börjar sätta ihop slumpmässiga toner.

Palle