Etikettarkiv: Humor

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

 

Hur logik och ordspråk kan förvränga världen

”Finns det hjärterum så finns det stjärterum”

Några veckor sedan trängde helt för många PRK-medlemmar in sig i en alldeles för liten bastu. Så klart, goda människor som vi är lät vi alla få en sittplats på bastulaven. Den just nämnda frasen är en viktig princip att hålla i tankarna för alla dylika situationer där det uppstår mera hudkontakt än vad som är behagligt.

En nördig matematiker kunde ju inte låta bli att påpeka att det kända ordspråket kan uttryckas i första ordningens logik:
Det finns hjärterum Det finns stjärterum.
Detta är alltså en logisk implikation, en form av propositionsuttryck. En intressant egenskap hos implikationer är att fast premissen är falsk och slutsatsen är sann, så är fortfarande hela implikationen sann. Med andra ord: Det kan finnas stjärterum fastän det inte finns hjärterum!

Någon som har sysslat lite mer med logik känner kanske också till begreppet kontraposition, dvs en logiskt ekvivalent, ”omvänd” form av samma implikation:
Det finns inte stjärterum Det finns inte hjärterum.
Det låter ju inte riktigt lika trevligt, men betydelsen är densamma! Med hjälp av matematisk logik kan vi alltså förvränga det vackra ordspråket till följande cyniska världsbild:
”Alla som inte ger dig en plats ogillar dig, men de som ger dig en plats gillar dig inte nödvändigtvis heller”.

Kan vi utsätta fler klassiska fraser för den totally-not-nödvändiga logiska behandlingen? Såklart!

”Dum fråga får dumt svar”
Du ställde en dum fråga ⇒ Du fick ett dumt svar.
Implikationen håller även om du ställde en smart fråga och fick ett dumt svar.
Tolkning: Då någon näsvist ger dig ett dumt svar, motiverad av denna fras, kan du påpeka att din fråga mycket väl kunde ha varit väl formulerad och smart. Svara lika näsvist tillbaka: ”Check your logic”.

”Allt som glittrar är inte guld”.
Låt X vara ett godtyckligt föremål med möjligheten att glittra och/eller vara guld. Då gäller:
¬(X glittrar ⇒ X är guld)
Här är ‘¬’ symbolen för en negation, dvs det motsatta påståendet. Uttrycket är ekvivalent med: (bortlämnat triviala mellansteg som sanningstabeller och De Morgans lag)
X glittrar och X är inte guld
Tolkning: Inget guld glittrar, eller det guld vi har sett glittra är egentligen inte guld.

Som vi ser är en kombination av logik och ordspråk inte alltid överensstämmande med verkliga livet. Vad gör vi åt detta? Jo, vi hyllar Boole och  Gödel och tolkar matematisk logik som det enda rätta. Ordspråken lämnar vi åt språkstuderande; vi har ju inte hjärterum för humanister.

Det RIKTIGA svaret till livet, universum och allting

Varning!
Följande artikel innehåller grunden för lösningarna till och för alla problem i världen.
Läs på egen risk!

Som spelmånadens sista spelartikel talar vi om… SPEL! Men denna gång i form av en liten introduktion av spelteori.

Vad går spelteori då ut på? Det handlar ganska långt om att man i olika spel söker fram vad är det rationellt sett bästa draget. Spelen utgår alltså från att spelarna är rationella och inte låter “känslor” eller “moral” påverka deras drag. Man är ute efter att maximera ens egen vinst och inget mer. Vi tar och kollar på ett trivialt spel som exempel:
Anta att en studerande, vars favoritmat är pizza, är hungrig och har nyligen inskaffat sin favoriträtt. Låt pizzan vara godtyckligt god och mättande. Studeranden har nu två val: att äta pizzan eller inte äta den. Matrisen för detta spel skulle se ut på följande vis:

GT_pizza

Det självklara valet skulle nu vara (rationella som vi är) att äta pizzan. Att låta bli att äta pizzan ger inget bättre jämfört med att äta den.

Hänger du med såhär långt? Då går vi vidare till spel med två spelare:
Anta att två studiekamrater råkar se varandra vid Kampen på ett avstånd som överskrider den socialt acceptabla hälsningen. Om en av dem hälsar, så hälsar den andra nog tillbaka och saken är biff. Om ingendera hälsar börjar båda fundera på saken, vilket känns pinsamt. Matrisen för detta spel skulle se ut som följande:

GT_halsaOchVanta

Vad är det bästa draget? Rationella som vi är, så vill vi inte skapa friktion mellan våra vänskapsband, så det självklara draget skulle nu vara att hälsa. Det räcker med att ena börjar hälsningen, men eftersom en hälsning inte kräver mycket ansträngning, så kan man lika bra själv hälsa genast.

Förrän vi går vidare till nästa spel, så tar vi en tillbakablick på spelet ovan. I spelet är det relativt enkelt att se vad det bästa valet är, men vad om det inte skulle vara lika klart? Då kan vi använda oss av det fina verktyget som kallas matematik! Vi kan ge resultaten olika värden beroende på hur bra de är och från dessa värden kan vi sedan räkna ut den bästa strategin. I spelteorin används benämningen Nash equilibrium (Nash jämnviktsläge, eller förkortat bara Nash) för de bästa strategiparen och dessa kan räknas enligt följande:
Vi kollar på hälsningsmatrisen pånytt, men denna gång ur matematisk synvinkel med värdena 0 och 1 som resultat.

GT_numeriskHalsaOchVanta

Låt oss säga att vi nu spelar som radspelaren. Nu kan vi från matrisen se att om kolumnspelaren väljer att Hälsa får vi i vilket fall som helst resultatet 1. Alltså är båda dragen lika värda för tillfället. Till näst kollar vi på vad som händer om kolumnspelaren väljer att Vänta. Nu ser vi att draget Hälsa ger resultatet 1, medan Vänta ger resultatet 0. Eftersom 1 > 0 vill vi då hellre välja att Hälsa. Därmed lönar det sig alltid som radspelare att Hälsa. Spelet är symmetriskt, så då vi undersöker kolumnspelaren kommer vi också fram till att det alltid lönar sig för kolumnspelaren att Hälsa. Detta ger oss att vårt Nash är (Hälsa, Hälsa), eftersom det lönar sig för både och att Hälsa.

So far so good. Nu när du fått en inblick till spelmatriser och deras lösningar så tar vi en titt på svårare spel. Till näst använder vi oss av spelteori för att komma fram till den populationsdynamiskt sett evolutionärt stabilaste och optimalaste dejtningsstrategin (Varning! Har inte testats i praktiken (med framgång)).

GT_meme

Vi börjar med att kolla på dejtningsspelet.
I dejtningsspelet finns det två strategier, att sikta på en längre dejtningsperiod där man bygger upp ett romantiskt förhållande under en längre tid (med långa tysta promenader runt Kaisaniemi <3) eller sen kan man gå rakt på sak och genast hoppa i sängen med den andra. Om spelarna har olika dejtningsstrategier tar tålamodet slut för den som valt en Kort strategi. Förhållandet går ingen vart och i så fall har båda slösat sin tid.
Alltså får vi följande matris:

GT_courting

Om man är fullkomligt rationell väljer man förstås den kortsiktiga strategin, eftersom tidsförlusterna är då mindre och man får lika mycket ut av förhållandet såsom man skulle få vid långtidsstrategin. Genom att ge matematiska värden för dessa, så har vi matematiskt bevisat att det lönar sig att dejta kortsiktigt. (Inte riktigt sant, eftersom både (Kort, Kort) och (Långt, Långt) kan vara Nash, beroende på hur mycket ett förhållande är värt jämfört med den satsade tiden, men vi håller oss till en ensidig åsikt för artikelns skull.)

Till näst ser vi på uppfostringsspelet.
I detta spel har spelarna *erhem* kopulerat och tillsammans fått en avkomma. Misstag eller inte, alternativen för båda spelare är att Stanna med sin avkomma eller Rymma iväg. Om båda spelare väljer Stanna, så delar de på tiden att uppfostra avkomman, medan om båda väljer Rymma, så kommer Socialen och för bort den (till en onämnd plats).

Vid fallet att spelarna väljer olika, så kommer den som valt att Stanna att ta fullt ansvar för avkomman, medan den som valt Rymma går vidare i livet nöjd av att ha (re)producerat en avkomma.

GT_parenting

Notera att matrisen inte längre är symmetrisk! Eftersom det är skillnad vid (Rymma, Stanna) och (Stanna, Rymma), så kollar vi i denna matris specifikt alltså på radspelarens resultat!

Här märker vi att den bästa strategin beror på hur mycket man rationellt sett värderar Avkomman jämfört med ansträngningen av Uppfostran. Beroende på dessa parametrar, så kan vi få som Nash antingen (Stanna, Stanna) eller (Rymma, Rymma).

Men vad om man vill kolla på flera saker samtidigt och inte bara en sak i taget? Spelteori har lösningen även för det! Ett spel kan innehålla flera faser, där faserna är mindre enskilda spel. Exempelvis kan vi kombinera de två spelen ovan för att få följande spel:

GT_multistage

Lösningen för dejtningsmatrisen är nu beroende av uppfostringsmatrisen, så vi måste lösa den först. Med vidare matematisk bollning (vilket ni kan bekanta er på i “Evolution and the Theory of Games”-kursens material) får vi till sist att de rationellt sett bästa strategierna är (Kort och Stanna) och (Kort och Rymma). Detta gäller för nästan alla parametrar (dvs. värderingarna på Avkomman med mera). I vissa fall är också (Lång och Stanna) lönsam, men vi kan alla hålla med om att det är onödigt att sätta för mycket tid på romantik!

Slutresultatet är att ifall alla skulle vara rationella istället för att bry sig om onödiga saker som känslor och annat tjafs, så skulle alla vara i korta förhållanden och sedan se hur mycket man bryr sig om avkomman. Så säger spelteorin… och matematiken ljuger aldrig!
– Team WaPaa