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?

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!