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?

Over 40 sek kjøretid, se om jeg rekker å optimalisere noe senere:

$total = 0;
for($i=1;$i<=123454321;$i++) {
	$is = (string) $i;
	if ( strrev($is) !== $is) {
		$p = (string)($i + (int) strrev((string)$i));
		if ( strrev($p) === $p) {
			$total+=$i;
		}
	}
}
var_dump($total);`

Dagens JavaScript løsning:

const luke19 = ((from, to) => {
    const isPalindrome = (n) => {
        const s = String(n);
        const firstHalf = s.substr(0, s.length >> 1);
        const secondHalf = s.substr((s.length >> 1) + (s.length & 1));
        const rSecondHalf = Array.from(secondHalf).reverse().join('');
        return (firstHalf === rSecondHalf);
    };

    const addReversed = (n) => n + Number(Array.from(String(n)).reverse().join(''));    

    const isHiddenPalindrome = (n) => (!isPalindrome(n) && isPalindrome(addReversed(n)));

    return Array.from(Array(to - from + 1).keys()).map(
            (n) => isHiddenPalindrome(n + from) ? (n + from) : void 0
    ).filter(Number.isFinite).reduce((acc, cv) => acc + (+cv), 0);
});

console.log(luke19(1, 123454321));

Dagens python. Brukte mest tid fordi jeg ikke klarte å lese summen av.

def hidden_palindrome(n):
    n_s = str(n)

    if n_s == n_s[::-1]:
        return False

    s = str(n + int(n_s[::-1]))

    return s == s[::-1]


def test_hidden_palindrome():
    assert hidden_palindrome(38)
    assert not hidden_palindrome(49)


if __name__ == '__main__':
    s = 0

    for x in range(1, 123454321+1):
        if x % 1000000 == 0:
            print(x)

        s += x if hidden_palindrome(x) else 0

    print(s)

Løsning i Nim

proc reverse(x: int): int =
    var ans = 0
    var c = x
    while c > 0:
      ans *= 10
      ans += c %% 10
      c =  c div 10
    return ans
  
proc is_palindrome(x:int): bool =
    return x == reverse(x)

  
var hidden_p_sum = 0
for i in countup(1, 123454321):
    if not i.is_palindrome():
        if is_palindrome(i + i.reverse()):
            hidden_p_sum += i
          
echo hidden_p_sum

Tenkte å friske opp Fortran-kunnskapene mine. Koden er på ingen måte optimalisert. Kjøretid ca 5,6 sek på en gammel og treig ThinkPad.

integer function revers(tall)
    integer, intent(in) :: tall
    integer :: n

    n = tall
    revers = 0
    do while (n > 0)
      revers = 10 * revers + mod(n, 10)
      n = n / 10
    end do
end function revers

logical function er_palindrom(tall)
      integer, intent(in) :: tall
      integer :: revers

      er_palindrom = (tall == revers(tall))
end function er_palindrom

program palindrom
      implicit none

      integer :: i
      integer :: grense = 123454321

      integer :: revers
      integer :: r
      logical :: er_palindrom

      integer(kind=16) :: total

      i = 1
      total = 0
      do while (i <= grense)
          r = revers(i)
          if ((.not. (i == r))) .and. (er_palindrom(i + r))) then
              total = total + i
          end if
          i = i + 1
      end do
      print *, total

end program

Laget først en versjon i dag tidlig, men synes den var for treig. Har laget en ny versjon her med forsøk på optimaliseringer, men viser seg at den var enda tregere. Tipper det er pga. bruk av dynamiske arrays, er ikke sikker. Ja-ja, kaller dette endelig løsning for i dag.

Go (3m)

package main

import (
	"fmt"
)

func digitize(n int) (s, r []int) {
	for {
		digit := n % 10
		s = append([]int{digit}, s...)
		r = append(r, digit)
		n /= 10
		if n == 0 {
			break
		}
	}
	return
}

func equals(a, b []int) bool {
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func add(a, b []int) (s, r []int) {
	rest := 0
	for i := len(a) - 1; i >= 0; i-- {
		sum := rest + a[i] + b[i]
		digit := sum % 10
		rest = sum / 10
		s = append([]int{digit}, s...)
		r = append(r, digit)
	}
	if rest > 0 {
		digit := rest
		s = append([]int{digit}, s...)
		r = append(r, digit)
	}
	return
}

func main() {
	// Hva er summen av alle skjulte palindromtall mellom 1 og 123454321?
	sum := 0
	for i := 2; i < 123454321; i++ {
		s, r := digitize(i)
		if !equals(s, r) && equals(add(s, r)) {
			sum += i
		}
	}
	fmt.Println(sum)
}

Var så fornøyd med den nye måten å reversere nummer jeg fant ut av (fremfor å splitte til og joine fra array) at jeg trodde det kom til å gå kjemperaskt, men den gang ei. Tar alt for mange minutter til at jeg vil nevne det en gang.

use strict;
use integer;

my $i;
my $sum = 0;

for($i = 10; $i < 123454321; $i++) {
  my $reverse = reverseit($i);
  if ($reverse != $i) {
    my $added = $i + $reverse;
    $reverse = reverseit($added);
    if ($reverse == $added) {
      $sum += $i;
    }
  }
}
print "Sum: $sum\n";

sub reverseit {
  my $number = $_[0];
  my $revnumber = 0;
  while($number != 0) {
    $revnumber = ($revnumber * 10) + ($number % 10);
    $number /= 10;
  }
  return $revnumber;
}

Synes dagens formulering var grei, jeg. Jeg var også usikker etter første gjennomlesning, om et palindromtall også kan være et skjult palindromtall, men det var jo ikke verre enn å lese én gang til, så sto jo svaret svart på hvitt opptil flere steder. Støtter dog vedkommende over her som sa at utfordringen ikke bør ligge i å tolke og forstå oppgaven rett (eller noe i den duren), og det er jeg helt enig i. Likevel var ikke dagens luke den verste, imo.

@danieman @jonathangjertsen ja, er jo enig i det jeg også :) Er ikke så glad i sånne gåter og rebuser og sånn :)

Enkel (og sykt treig!) løsning i Rust.
Regner med det er konvertering mellom tall og string som gjør den treig.

fn is_palindrome(s: &str) -> bool {
    s == s.chars().rev().collect::<String>()
}

fn is_hidden_palindrome(n: u64) -> bool {
    if is_palindrome(&format!("{}", n)) {
        return false;
    }
    let n_plus_rev = &format!(
        "{}",
        n + format!("{}", n)
            .chars()
            .rev()
            .collect::<String>()
            .parse::<u64>()
            .unwrap()
    );

    is_palindrome(&format!("{}", n_plus_rev))
}

fn main() {
    let mut sum = 0;
    for i in 1..123_454_321 {
        if is_hidden_palindrome(i) {
            sum += i;
        }
    }
    println!("{}", sum);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_is_hidden_palindrome_should_be_true() {
        assert_eq!(is_hidden_palindrome(38), true);
    }

    #[test]
    fn test_is_hidden_palindrome_should_be_false() {
        assert_eq!(is_hidden_palindrome(49), false);
    }
}

real    1m57.187s
user    1m41.953s
sys     0m1.438s

raskere å skrive koden enn å runne den, menmen:

x = 0
for i in range(1, 123454322):
    s = str(i)
    rev = s[::-1]
    if s != rev:
        num = i+int(rev)
        s = str(num)
        rev = s[::-1]
        if s == rev:
            x += i
print(x)

C#. Kort kode, laaang kjøretid. Bør ikke gå via string, gjør det likevel.

static void Main(string[] args)
{
    var sum =
        Enumerable
            .Range(1, 123454321)
            .AsParallel()
            .Where(x => IsHiddenPalindrome(x) && !IsPalindrome(x))
            .Sum(Convert.ToInt64);
    Console.WriteLine($"Sum: {sum}");
}

static bool IsHiddenPalindrome(long number)
    => IsPalindrome(number + Convert.ToInt64(string.Join(string.Empty, number.ToString().Reverse())));

static bool IsPalindrome(long number)
    => number.ToString().SequenceEqual(number.ToString().Reverse());

C#, rett-frem-løsning med LINQ uten særlig tanke på ytelse annet enn bruk av AsParallel. Kjører på 20 sekunder.

using Common;
using System;
using System.Diagnostics;
using System.Linq;

namespace KnowitJulekalender19
{
    class Program
    {
        static void Main(string[] args)
        {
            Test();
            Stopwatch sw = Stopwatch.StartNew();

            var sum = SumHiddenPalindromes(1, 123454321);

            var elapsed = sw.Elapsed;
            Console.WriteLine($"Sum av skjulte palindromtall er {sum} ({elapsed.TotalMilliseconds} ms).");
        }

        public static void Test()
        {
            var palindrome = "agnes i senga";
            var notPalindrome = "fisk";
            if (!IsPalindrome(palindrome) || IsPalindrome(notPalindrome)) throw new Exception("IsPalindrome failed test");

            var alreadyPalindrome = 121;
            var hidden = 83;
            var notHidden = 49;
            if (!IsHiddenPalindrome(hidden) || IsHiddenPalindrome(notHidden) || IsHiddenPalindrome(alreadyPalindrome)) throw new Exception("IsHiddenPalindrome failed test");
        }

        public static long SumHiddenPalindromes(int start, int count)
        {
            return Enumerable.Range(start, count)
                .AsParallel()
                .Sum(l => IsHiddenPalindrome(l) ? l : 0L);
        }

        public static bool IsHiddenPalindrome(long l)
        {
            string s = l.ToString();
            if (IsPalindrome(s)) return false;
            var reverse = s.Reverse();
            var summed = l + (long.Parse(reverse));
            return IsPalindrome(summed.ToString());
        }

        private static bool IsPalindrome(string s)
        {
            var l = s.Length;
            var l2 = l / 2;
            for (int i = 0; i < l2; i++)
            {
                if (s[i] != s[l - i - 1]) return false;
            }
            return true;
        }
    }
}

C# LINQ som kjører på ca 1,5 sek (Greit speed up ved å bruke AsParallel()), unngår også strings:

private static long Luke19()
        {

            return Enumerable.Range(1, 123454321)
                .AsParallel()
                .Select(i => (long)i)
                .Where(i => !IsPalindrome(i) && IsHiddenPalindrome(i))
                .Sum();
        }

        private static bool IsPalindrome(long i) => i == Reverse(i);

        private static bool IsHiddenPalindrome(long i) => IsPalindrome(i + Reverse(i));

        private static long Reverse(long n)
        {
            long i = 0;
            while (n > 0)
            {
                i = i * 10 + n % 10;
                n = n / 10;
            }
            return i;
        }

js:

function isPalindrome(i) {
    let isPalindrome = i === i.split('').reverse().join('');
    return isPalindrome;
}

function isHiddenPalindrome(i) {
    let strReversed = i.toString().split('').reverse().join('');
    let sum = i + parseInt(strReversed);
    let sumStr = sum.toString();
    return isPalindrome(sumStr);
}

let sumHiddenPalindromes = 0;
for (let i = 2; i < 123454321; i++) {
    if (!isPalindrome(i.toString()) && isHiddenPalindrome(i)) sumHiddenPalindromes += i;
}

console.log(sumHiddenPalindromes);

Skippet inkludering av extension metoder, en del gjenbruk. Ikke optimalt, denne er kandidat for optimalisering :)

interface KnowItJuleKalenderLuke
{
    Task<string> OpenAsync();
}

public class Luke19 : KnowItJuleKalenderLuke
{
    public Task<string> OpenAsync()
    {
        long sum = 0;
        for (long i = 1; i < 123454321; i++)
        {
            var digits = i.Digits();
            var digitsReverse = digits.Reverse();
            if (!digits.Equal(digitsReverse))
            {
                long j = digitsReverse.ToLong();
                long k = i + j;
                digits = k.Digits();
                digitsReverse = digits.Reverse();
                if (digits.Equal(digitsReverse))
                {
                    // Så ser at ve e på vei :)
                    if (i % 1000000 == 0) Console.WriteLine(i.ToString() + " : (j : " + j + ") " +  k + " sum: " + sum); 
                    sum += i;
                }
            }
        }

        return Task.FromResult(sum.ToString());
    }
}

F#, måtte bruke lokal mutasjon for å komme ned mot 4s, ca 2s med parallel array. Mulig jeg må bruke en annen pakke eller Linq for å kunne bruke parallel filter som i C# til finnmich

open Microsoft.FSharp.Core.Operators.Checked

let reverser n =
  let mutable n = n
  let mutable reversert = 0UL
  while n <> 0UL do
    reversert <- (reversert * 10UL) + (n % 10UL)
    n <- n / 10UL
  reversert

let erPalindrom n = 
  n = reverser n

let skjultePalindromer range =
  seq {
    for n in range do
      if not (erPalindrom n) then
        if erPalindrom (n + reverser n) then
          yield n
  }

{1UL..123454319UL}
|> skjultePalindromer
|> Seq.sum

Ganske rett fram, men treg, Haskell:

main :: IO ()
main =
  print . sum . filter (palindrome  . show . sumRev) $
  filter (not . palindrome . show) [1 .. 123454321]

palindrome :: String -> Bool
palindrome s = s == reverse s

sumRev :: Integer -> Integer
sumRev x = x + (read . reverse $ show x)

Elixir ❤️

reverse = fn (n) ->
  Integer.digits(n)
  |> Enum.reverse()
  |> Integer.undigits()
end

is_palindrome = fn (n) -> reverse.(n) == n end

is_hidden_palindrome = fn (n) ->
  if is_palindrome.(n) do
    false
  else
    reverse.(n)
    |> Kernel.+(n)
    |> is_palindrome.()
  end
end

1..123454321
|> Enum.filter(&is_hidden_palindrome.(&1))
|> Enum.sum()
|> IO.puts()

@flogvit Alternativt summen av A065206

Fikk lyst å optimalisere likevel.

Go (5s)

package main

import (
	"fmt"
)

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

func main() {
	// Hva er summen av alle skjulte palindromtall mellom 1 og 123454321?
	sum := 0
	for n := 2; n < 123454321; n++ {
		nr := reverse(n)
		if n == nr {
			continue
		}
		s := n + nr
		sr := reverse(s)
		if s == sr {
			sum += n
		}
	}
	fmt.Println(sum)
}

@aude: Fort gjort 😄
Hva lå den gamle løsningen på?

Kom ned i 1200 ms etter optimalisering, koden ble basically den samme som postet av @finnmich over.

Prøvde så å gjøre noen krumspring for å se om jeg kunne hente ut mer:

• For tall (summer) med partall siffere, sjekke om tallet er delelig med 11 og returnere tidlig om det ikke er det
• Ikke reversere summen men i stedet sjekke siffer for siffer om den er palindrom og returnere tidlig ved første avvik
• Dele opp arbeidsmengden i bolker for hhv 1-7, 8, 9 siffer og utnytte kunnskap om antall siffer for å slippe å beregne på nytt

Dessverre bar ingen av disse noen frukter, det kan se ut som man jobber litt mot JIT-eren her. Tror jeg gir opp å komme ned i C-territorie når det gjelder kjøretid på denne.

        public static IEnumerable<long> Range(long start, long count)
        {
            long max = start + count;
            while (start < max) yield return start++;
        }

        public static long SumHiddenPalindromes(int start, int count)
        {
            long sum = Range(start, count)
                    .AsParallel()
                    .Sum(l => IsHiddenPalindrome(l));

            return sum;
        }

        public static long IsHiddenPalindrome(long l)
        {
            var reversed = ReverseDigits(l);
            if (l == reversed) return 0;

            var sum = l + reversed;
            var sumReversed = ReverseDigits(sum);
            if (sum == sumReversed) return l;
            return 0;
        }

        public static long ReverseDigits(long l)
        {
            long reversed = 0;
            long rest = l;
            while (rest > 0)
            {
                reversed *= 10;
                reversed += (rest % 10);
                rest /= 10;
            }

            return reversed;
        }

@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?

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).

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!