Luke 19.md

Skjulte palindromer

Av: Didrik Pemmer Aalen

Et palindrom er et ord, utrykk eller tall som gir samme resultat uansett om det leses fra høyre eller venstre. I noen tilfeller kan man lage palindromtall av ikke-palindromtall ved å summere det originale tallet med reversen av det originale tallet. Slike tall kaller vi skjulte palindromer.

Eksempel

38 + 83 = 121

38 er ikke et palindrom, men når man legger til 83 (38 reversert) får vi 121, som er et palindrom. 38 er dermed et skjult palindrom.

49 + 94 = 143

49 er ikke et palindrom, og når man legger til 94 (49 reversert) får man 143, som ikke er et palindrom. 49 er dermed ikke et skult palindrom.

Oppgave

Hva er summen av alle skjulte palindromtall mellom 1 og 123454321?

static void Main(string[] args)
{
    long sum = 0;
    var stopWatch = new Stopwatch();
    stopWatch.Start();
    for (var i = 10; i <= 123454321; i++)
        if (IsPalindrome(i, out var x) == false && IsPalindrome(i + x, out var foo)) sum += i;
    stopWatch.Stop();
    var ts = stopWatch.Elapsed;
    Console.WriteLine($"Runtime: {ts.TotalMilliseconds}, Result: " + sum);
}

static bool IsPalindrome(int x, out int y)
{
    y = 0;
    for (var i = x; i > 0; i /= 10) y = y * 10 + i % 10;
    return y == x;
}

@michaelo

@terjew: Jeg synes det der begynner å bli ganske så pent. Det er f.eks. kjappere enn singlethread-varianten min. Hvilken runtime kjører du den med?

Hehe ja, kanskje målsettingen min må være å slå singlethreaded C 😄 Bygger som console app mot .Net Core 3.1 og kjører exe-filen som blir produsert.

Brente en del tid selv på antakelsen om at jeg kunne sjekke ut alle tallene jeg hadde gått igjennom, f.eks. ved å ikke prosessere et tall hvis det var en revers av et tidligere tall. Men det ble for mange edge-cases, spesielt pga at det ikke er gitt at num == revers(revers(num)) (gitt tall som slutter på èn eller flere 0er).

Ja, fort å gå seg litt fast i en sånn runde. Med så store datasett er det ikke gitt at memoization har noe for seg heller, da minnelatency er så høy sammenliknet med integeraritmetikk.

Jeg er fortsatt ikke helt overbevist om hvorfor det ikke skal være raskere å sjekke siffer for siffer og returnere tidlig kontra en full revers av summen, men det har kanskje med branch prediction og speculative execution etc å gjøre. Mulig også at utfallet av den optimaliseringen hadde vært annerledes i C.

Jeg merket forresten en liten ytelsesforbedring på å returnere tallverdien fra palindromsjekk-metoden i stedet for å returnere bool og så sjekke den verdien igjen utenfor, mulig det kan gi en ørliten forbedring hos deg også? Skal jo i teorien spare en unødvendig branching.

@terjew

Hehe ja, kanskje målsettingen min må være å slå singlethreaded C 😄 Bygger som console app mot .Net Core 3.1 og kjører exe-filen som blir produsert.

Altså; Jeg er fan av raskt, og lite sløseri. Men veier man kodetid mot ytelsesgevinst så begynner man der faktisk å havne i et område som ofte vil være akseptabelt. Du var der på 2x min mt, og 1/2 av min st. 👍 (Ikke at min kode nødvendigvis bør være benchmarken 🤣 )

Jeg er fortsatt ikke helt overbevist om hvorfor det ikke skal være raskere å sjekke siffer for siffer og returnere tidlig kontra en full revers av summen, men det har kanskje med branch prediction og speculative execution etc å gjøre. Mulig også at utfallet av den optimaliseringen hadde vært annerledes i C.

Jeg synes den er interessant, takk. Blir fort å gjøre et forsøk på det selv i morgen og se hvordan det oppfører seg 👍

Jeg merket forresten en liten ytelsesforbedring på å returnere tallverdien fra palindromsjekk-metoden i stedet for å returnere bool og så sjekke den verdien igjen utenfor, mulig det kan gi en ørliten forbedring hos deg også? Skal jo i teorien spare en unødvendig branching.

Interessant. Jeg gjorde en test selv med å flate det ut helt, men der ble assemblyen så-og-si identisk så langt jeg fikk skummet over (med -O3, ihvertfall) med slik den er nå. Det så ut til at inlininga gikk som forventet der. Men skal dobbeltsjekke - det var tross alt noen variasjoner i assemblyen 🤷‍♂️ .

90 sekunder skrivetid, 90 sekunder kjøretid 😄 Python!

@michaelo, den gamle lå på ca. 3min.

Fikk lyst å prøve goroutines for første gang. Her er en multi-threaded versjon, som kom seg inn under sekundet 🎉

Go (0.8s)

package main

import (
	"fmt"
	"runtime"
)

// Hva er summen av alle skjulte palindromtall mellom 1 og 123454321?
const min uint64 = 2
const max uint64 = 123454320

func reverse(n uint64) (nr uint64) {
	for nr = 0; n > 0; n /= 10 {
		nr *= 10
		nr += n % 10
	}
	return
}

func isHiddenPalindrome(n uint64) bool {
	nr := reverse(n)
	if n == nr {
		return false
	}
	s := n + nr
	sr := reverse(s)
	if s == sr {
		return true
	}
	return false
}

func main() {
	sum := uint64(0)

	// spawn workers, one per available thread
	workers := uint64(runtime.GOMAXPROCS(0))
	c := make(chan uint64, workers)
	split := (max - min) / workers
	for i := uint64(0); i < workers; i++ {
		start := min + i*split + i
		end := min + (i+1)*split + i
		if end > max {
			end = max
		}

		go func() {
			var partsum uint64 = 0
			for n := start; n <= end; n++ {
				if isHiddenPalindrome(n) {
					partsum += n
				}
			}
			c <- partsum
		}()
	}

	// collect results from workers
	for i := uint64(0); i < workers; i++ {
		sum += <-c
	}

	fmt.Println(sum)
}

@aude: Pent!