Skip to content

Instantly share code, notes, and snippets.

@knowitkodekalender

knowitkodekalender/Luke 19.md Secret

Created Dec 18, 2019
Embed
What would you like to do?

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?

@amumurst

This comment has been minimized.

Copy link

@amumurst amumurst commented Dec 19, 2019

Dagens lille scala løsning. Får se om jeg gidder optimalisere noe ila dagen :)

object Day19 extends App {
  def reverseN(l: Long)     = l.toString.reverse.toLong
  def isPalindrome(l: Long) = reverseN(l) == l
  val n = Iterator.from(1).map(_.toLong).take(123454321).filter(l => !isPalindrome(l) && isPalindrome(l + reverseN(l))).sum
  println(n)
}
@bobcat4

This comment has been minimized.

Copy link

@bobcat4 bobcat4 commented Dec 19, 2019

Litt i overkant av 5s kjøretid. Det kan nok forbedres.
C-kode:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

long inline reverse(long n)
{
    long rev = 0;
    while (n != 0)
    {
        rev *= 10;
        rev += n%10;
        n /= 10;
    }
    return rev;
}

long inline add_reverse(long n)
{
    return n + reverse(n);
}

int inline is_luke19_palindrom(long n)
{
    return add_reverse(n) == reverse(add_reverse(n));
}

int inline (is_palindrom(long n)) {
    return n == reverse(n);
}

int main ()
{
    long cnt = 0;
    for (long i = 2 ; i < 123454321 ; i++)
    {
        if (!is_palindrom(i) && is_luke19_palindrom(i)) cnt += i;
    }
    printf("%ld\n", cnt);
    return 0;

}
@KFBI1706

This comment has been minimized.

Copy link

@KFBI1706 KFBI1706 commented Dec 19, 2019

Kjapp løsning i rust.

fn rev(mut n:u64) -> u64 {
    let mut rev = 0;
    while n > 0 {
        rev = rev * 10 + n % 10;
        n /= 10
    }
    return rev
}

fn main() {
    let mut sum: u64 = 0;
    let mut r: u64;
    for i in 1u64..123454321 {
        r = rev(i);
        if i != r && i+r == rev(i+r) {
            sum += i;
        }
    }
    println!("{}", sum);
}
@teilin

This comment has been minimized.

Copy link

@teilin teilin commented Dec 19, 2019

Kjapp løsning i Go. Det tok litt tid å kjøre, men men.

package main

import (
	"fmt"
	"strconv"
	"strings"
)

func sliceToInt(a []int64) int64 {
	if len(a) == 0 {
		return 0
	}

	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.FormatInt(v, 10)
	}
	tmp, _ := strconv.ParseInt(strings.Join(b, ""), 10, 64)
	return tmp
}

func intToSlice(num int64) []int64 {
	if num == 0 {
		return []int64{0}
	}
	var slice []int64
	for {
		slice = append(slice, num%10)
		num /= 10
		if num <= 0 {
			break
		}
	}
	return reverseSlice(slice)
}

func sumSlice(slice []int64) int64 {
	var sum int64 = 0
	for _, i := range slice {
		sum += i
	}
	return sum
}

func reverseSlice(s []int64) []int64 {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
	return s
}

func isPalidrome(num int64) bool {
	rs := true
	numSlice := intToSlice(num)
	numSliceReversed := reverseSlice(numSlice)
	for i, j := 0, len(numSliceReversed)-1; i <= j; i, j = i+1, j-1 {
		rs = numSlice[i] == numSliceReversed[j]
		if !rs {
			break
		}
	}
	return rs
}

func isHiddenPalindromer(num int64) bool {
	if isPalidrome(num) {
		return false
	}
	n := num + sliceToInt(reverseSlice(intToSlice(num)))
	return isPalidrome(n)
}

func main() {
	var sum int64 = 0
	var i int64
	for i = 1; i < 123454321; i++ {
		if isHiddenPalindromer(i) {
			sum += i
		}
	}
	fmt.Println(sum)
}
@jonathangjertsen

This comment has been minimized.

Copy link

@jonathangjertsen jonathangjertsen commented Dec 19, 2019

Mye som var uklart i oppgaveteksten. Hva betyr "mellom"? Skal man ta med 1? 123454321? Og hva er kriteriet? Oppgaven kan tolkes på flere måter:

  • Slik jeg tolket oppgaven: isPalindrome(n + reverseDigits(n))
  • Det neste jeg prøvde: isPalindrome(n) || isPalindrome(n + reverseDigits(n))
  • Det som viste seg å være riktig: !isPalindrome(n) && isPalindrome(n + reverseDigits(n))

Anyway, Python

def hidden_palindrome(n):
    n_rev = int(str(n)[::-1])
    if n == n_rev:
        return False
    pair_sum = str(n + n_rev)
    return pair_sum == pair_sum[::-1]

print(sum(filter(hidden_palindrome, range(1, 123454321))))
@amumurst

This comment has been minimized.

Copy link

@amumurst amumurst commented Dec 19, 2019

@jonathangjertsen Jeg gjorde akkurat den samme rekka med feil selv og vurderte om jeg syntes det var uklart. Men ved ny gjennomlesning så syntes jeg det egentlig er godt nok beskrevet:
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.
Om mellom er inklusive eller eksklusive kan jeg være enig i at ikke er heelt klart. Men siden man ikke skal regne med de som alt er palindromer så ender det med å være irrelevant :)

@lassem

This comment has been minimized.

Copy link

@lassem lassem commented Dec 19, 2019

Koden er nesten så treg som det går an men... Kanskje ikke her Python er på sitt beste.

#!/usr/bin/env

def reverse(n):
    r = 0
    while n > 0:
        r = (10 * r) + n % 10
        n = n // 10
    return r

s = 0
for i in range(123454321):
    r = reverse(i)

    if i == r:
        continue
    
    if (i + r) == reverse(i + r):
        s += i

print(s)
@jonathangjertsen

This comment has been minimized.

Copy link

@jonathangjertsen jonathangjertsen commented Dec 19, 2019

@amumurst godt poeng. Kunne hatt f.eks 121 som testvektor for å illustrere det.

@Nilzone-

This comment has been minimized.

Copy link

@Nilzone- Nilzone- commented Dec 19, 2019

function reverse(n) {
	let _n = 0;
	while (n) {
		_n = _n*10+(n%10);
		n = (n/10) | 0;
	}
	return _n;
}

const N = 123454321;
let [c, r] = [0, 0];
for (let i = 1; i <= N; i++) {
	r = reverse(i);
	c += (i + r) === reverse(i + r) && r !== i  ? i : 0;
}
console.log(c)
@Suppen

This comment has been minimized.

Copy link

@Suppen Suppen commented Dec 19, 2019

Haskell. Kjøretid på over to minutter.... Men koden ble hvertfall kort og lesbar, og rent numerisk.
Jeg slet også med feil svar fordi det ikke var veldig godt beskrevet i oppgaven at skjulte palindromer ikke selv kan være palindromer.

-- Note: Digits are in reverse order
type Digits = [Int]

toDigits :: Int -> Digits
toDigits 0 = []
toDigits n = n `mod` 10 : toDigits (n `div` 10)

fromDigits :: Digits -> Int
fromDigits ds = fromDigits' 0 ds
    where fromDigits' _ [] = 0
          fromDigits' n (d:ds) = d*10^n + fromDigits' (n+1) ds

isHiddenPalindrome :: Int -> Bool
isHiddenPalindrome n = isPalindrome (n + (fromDigits . reverse . toDigits $ n))

isPalindrome :: Int -> Bool
isPalindrome n = ds == reverse ds
    where ds = toDigits n

main =
    print
        . sum
        . filter isHiddenPalindrome
        . filter (not . isPalindrome)
        $ [1..123454321]

JS-kode med mye samme logikk, som går om strings for å reversere. Kjøretiden var opprinnelig noen sekunder mer enn Haskelløsningen, men så optimaliserte jeg isPalindrome til å halvere antall sjekker, og da ble jammen kjøretiden også halvert til 1m 14s

"use strict";

function* nums(start, end) {
        let i = start;
        do {
                yield i++;
        } while (i <= end);
}

const isPalindrome = n => {
        const s = n.toString();
        const l = s.length;
        const lh = l / 2;
        for (let i = 0; i < lh; i++) {
                if (s.charAt(i) !== s.charAt(l-1-i)) {
                        return false;
                }
        }
        return true;
};

const isHiddenPalindrome = n => isPalindrome(Number.parseInt(n.toString().split("").reverse().join("")) + n);

let sum = 0;
for (const n of nums(1, 123454321)) {
        if (!isPalindrome(n) && isHiddenPalindrome(n)) {
                sum += n;
        }
}

console.log(sum);

EDIT: En kompis informerer meg om at det selvfølgelig er mulig å gjøre bare for (let i = 1; i <= 123454321; i++) istedet for å tukle med en generator. Jeg har tydeligvis blitt litt for funksjonell i tankegangen i det siste

@myrdyr

This comment has been minimized.

Copy link

@myrdyr myrdyr commented Dec 19, 2019

Stygg brute-force, men optimaliseringene krever også at man sjekker veldig mye underveis, så de må utelukke ganske store deler av mengden før de har noen effekt.

print(sum(i for i in range(123454321) if (f:=str(i))!=f[::-1] and (e:=str(i+int(str(i)[::-1])))==e[::-1]))
@jostyposty

This comment has been minimized.

Copy link

@jostyposty jostyposty commented Dec 19, 2019

@amumurst godt poeng. Kunne hatt f.eks 121 som testvektor for å illustrere det.

Jeg kunne godt tenkt meg at det stod fra og med 1 til og med 123454321, eller noe sånt, så det ikke er tvil om hvile tall man skal se på.
Men jeg synes det er helt supert at eksemplene ikke dekker alle løsninger. Da ville det blitt for lett.

@joakimwinum

This comment has been minimized.

Copy link

@joakimwinum joakimwinum commented Dec 19, 2019

AWK løsning:
awk -f door_19.awk

BEGIN {
	PROCINFO["sorted_in"] = "@ind_num_desc"
	for (number = 1; number <= 123454321; number++) {
		if (checkPalindrome(number) == 1 || checkPalindrome(number + reverse(number)) != 1) {
			continue
		}
		sum += number
	}
	print sum
}


function checkPalindrome(string,    stringLength, letters, halfStringLength, i)
{
	stringLength = split(string, letters, "")
	halfStringLength = int(stringLength / 2)
	for (i = 1; i <= halfStringLength; i++) {
		if (letters[i] != letters[stringLength + 1 - i]) {
			return 0
		}
	}
	return 1
}

function reverse(string,    letters, i, ans)
{
	split(string, letters, "")
	for (i in letters) {
		ans = ans letters[i]
	}
	return ans
}
@cathrinevaage

This comment has been minimized.

Copy link

@cathrinevaage cathrinevaage commented Dec 19, 2019

Det ble denne særs elegante js løsningen i dag.
Trenger bare ~7GB minne, og kjører på bare ~15 minutt.

const createRange = (from, to) => (
  Array(to - from + 1)
    .fill(true)
    .map((_, index) => (
      index + from
    ))
)

const getAmountOfDigits = (n) => (
  n === 0
    ? 1
    : Math.floor(Math.log10(n)) + 1
)

const toDigits = (number) => {
  const amountOfDigits = getAmountOfDigits(number)

  return createRange(1, amountOfDigits)
    .map((digitPosition) => {
      const divisor = 10 ** (amountOfDigits - digitPosition)

      return Math.floor(number / divisor % 10)
    })
}

const fromDigits = (digits) => (
  digits
    .reduce((sum, digit, index) => (
      sum + (digit * 10 ** (digits.length - index - 1))
    ), 0)
)

const reverseNumber = (number) => {
  const digits = toDigits(number)

  return fromDigits(digits.reverse())
}

const isPalindrome = (number) => (
  number === reverseNumber(number)
)

const isHiddenPalindrome = (number) => {
  const reversedNumber = reverseNumber(number)

  const sum = number + reversedNumber

  return isPalindrome(sum)
}

const hiddenPalindromes = createRange(10, 123454320)
  .filter((number) => (
    !isPalindrome(number) && isHiddenPalindrome(number)
  ))

const hiddenPalindromeSum = hiddenPalindromes
  .reduce((sum, addend) => (
    sum + addend
  ), 0)

console.log(hiddenPalindromeSum)

Edit:
Endret !isPalindrome(number) && isHiddenPalindrome(number) til isHiddenPalindrome(number) && !isPalindrome(number) i filteret, og sparte inn ~4 min

@dappa

This comment has been minimized.

Copy link

@dappa dappa commented Dec 19, 2019

En for PHP

<?php

$palindromes = 0;
$i = 123454321;

while ($i > 0) {
    $reverse = strrev($i);
    $palindromes += ($i != $reverse && $reverse + $i == strrev($reverse + $i)) ? $i : 0;
    $i--;
}

echo "Sum of palindromes " . $palindromes . "\n";
@mathiasose

This comment has been minimized.

Copy link

@mathiasose mathiasose commented Dec 19, 2019

Kort og grei Elixir med streams, litt i underkant av 4min kjøretid. Syns også at oppgaveteksten kunne vært klarere på om et palindrom også kan være et skjult palindrom, eller om skjulte palindrom per def ikke inkluderer "ekte" palindrom.

defmodule Knowit.Day19 do
  def reverse(n),
    do:
      n
      |> Integer.digits()
      |> Enum.reverse()
      |> Integer.undigits()

  def is_palindrome?(n), do: reverse(n) == n

  def is_secret_palindrome?(n), do: (n + reverse(n)) |> is_palindrome?
end

true = 38 |> Knowit.Day19.is_secret_palindrome?()

false = 49 |> Knowit.Day19.is_secret_palindrome?()

1..123_454_321
|> Stream.reject(&Knowit.Day19.is_palindrome?/1)
|> Stream.filter(&Knowit.Day19.is_secret_palindrome?/1)
|> Enum.sum()
|> IO.inspect()
@jonathangjertsen

This comment has been minimized.

Copy link

@jonathangjertsen jonathangjertsen commented Dec 19, 2019

Men jeg synes det er helt supert at eksemplene ikke dekker alle løsninger. Da ville det blitt for lett.

Da kan heller selve problemet være vanskeligere IMO. Mer interessant med en vanskelig oppgave som er overtydelig spesifisert enn en lett oppgave hvor det eneste vanskelige er at man må lese teksten med markeringspenn. Advent of Code gjør dette bra, oppgavene er ofte relativt omfattende, men hvis man får eksemplene til å funke får man sannsynligvis riktig svar på oppgaven også.

@michaelo

This comment has been minimized.

Copy link

@michaelo michaelo commented Dec 19, 2019

Gikk for en naiv rett-frem tilnærming. Testet både singlethread og multithread.
Jeg ser et par umiddelbare optimaliseringsmuligheter som jeg skal test.
F.eks tror jeg at jeg ganske enkelt kan tilnærme meg en ca halvering av kjøretid for singlethread, men den samme algoritmen vil ikke umiddelbart da fungere for multithread. Skal legge hodet litt i bløt for å se om jeg kan få skviset det ytterligere...
EDIT: Påstanden min om enkel løsning for halvert kjøretid på singlethread var nok litt prematur. Det var noen edge-caser som stakk kjepper i hjula.

Hyperfine:
singlethread:

  • Time (mean ± σ): 2.760 s ± 0.114 s

multithread (8):

  • Time (mean ± σ): 567.3 ms ± 53.8 ms
#define MULTITHREADED

#include <assert.h>
#include <math.h>
#ifdef MULTITHREADED
    #include <pthread.h>
#endif
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

static const int NUM_THREADS = 8;
static const int NUM_ITERATIONS = 1;
static const uint32_t LIMIT = 123454321;
static const uint64_t EXPECTED = 659277075458904;


static inline uint32_t reverse(uint32_t num) {
    uint32_t reverse = 0;
    /*
    123 -> 3
    12 -> 32
    1 > 321
    */

    while(num > 0) {
        reverse = reverse*10 + (num%10);
        num /= 10;
    }

    return reverse;
}

static inline bool evaluate(uint32_t num) {
    uint32_t rev = reverse(num);
    if (rev == num) return false;
    return num+rev == reverse(num+rev);
}

static inline uint32_t min(uint32_t a, uint32_t b) {
    if(a < b) return a;
    return b;
} 

#ifdef MULTITHREADED
typedef struct
{
  pthread_t thread_ref;
  uint32_t from;
  uint32_t to;
  uint64_t result;
} thread_definition_t;

static thread_definition_t threads[NUM_THREADS];

void* worker(void* arg) {
    thread_definition_t* workorder = (thread_definition_t*)arg;
    printf("Work work: %d->%d\n", workorder->from, workorder->to);
    for (uint32_t i = workorder->from; i<workorder->to; i++) {
        if (evaluate(i)) {
            workorder->result += i;
        }
    }
    return NULL;
}

static uint64_t mt_solve() {
    // hyperfine: Time (mean ± σ):     567.3 ms ±  53.8 ms
    int chunk_size = ceil(1.0*LIMIT/NUM_THREADS);
    for(int t=0; t<NUM_THREADS; t++) {
        threads[t].from = t*chunk_size;
        threads[t].to = min(LIMIT, (t+1)*chunk_size);
        threads[t].result = 0;
        pthread_create(&(threads[t].thread_ref), NULL, worker, &threads[t]);
    }

    uint64_t result = 0;
    for(int t=0; t<NUM_THREADS; t++) {
        pthread_join(threads[t].thread_ref, NULL);
        result += threads[t].result;
    }
    return result;
}
#endif

static uint64_t solve() {
    // hyperfine: Time (mean ± σ):      2.760 s ±  0.114 s
    uint64_t result = 0;
    for (uint32_t i = 1; i<LIMIT; i++) {
        if (evaluate(i)) {
            result += i;
        }
    }

    return result;
}

int main() {
    // assert(reverse(123) == 321);
    for(int i=0; i<NUM_ITERATIONS; i++) {
        uint64_t result = 0;
        #ifdef MULTITHREADED
        result = mt_solve();
        #else
        result = solve();
        #endif
        printf("Result: %llu\n", result);
        assert(result == EXPECTED);
    }
    return 0;
}
@skanin

This comment has been minimized.

Copy link

@skanin skanin commented Dec 19, 2019

Ser ut som jeg tenkte litt som @myrdyr i dag. Kjører ikke veldig raskt, men det får gå

print(sum(filter(lambda n: str(int(str(n)[::-1]) + n)[::-1] == str(
   int(str(n)[::-1]) + n) and not str(n)[::-1] == str(n), range(1, 123454322))))
@Sjark

This comment has been minimized.

Copy link

@Sjark Sjark commented Dec 19, 2019

Super slow c# kode:

static void Main(string[] args)
{
    long sumOfHiddenPalindromes = 0;

    for (int i = 1; i < 123454321; i++)
    {
        var numberArray = i.ToString().ToCharArray();
        Array.Reverse(numberArray);
        var reverseNumber = int.Parse(new string(numberArray));
        var newNum = i + reverseNumber;

        if (!IsPalindrome(i) && IsPalindrome(newNum))
        {
            sumOfHiddenPalindromes += i;
        }
    }

    Console.WriteLine(sumOfHiddenPalindromes);
}

private static bool IsPalindrome(int newNum)
{
    if (_palindromes.Contains(newNum))
    {
        return true;
    }

    var newNumString = newNum.ToString();

    for (int i = 0; i < newNumString.Length / 2; i++)
    {
        var n1 = newNumString[i];
        var n2 = newNumString[^(i + 1)];

        if (n1 != n2)
        {
            return false;
        }
    }

    _palindromes.Add(newNum);

    return true;
}
@flogvit

This comment has been minimized.

Copy link

@flogvit flogvit commented Dec 19, 2019

For de interesserte så er altså tallene vi er ute etter å summere definert i https://oeis.org/A030547 som a(n)=2. De som ender opp med -1 er mulige Lychrel tall. Lykke til med 196 :)

@bobcat4

This comment has been minimized.

Copy link

@bobcat4 bobcat4 commented Dec 19, 2019

@jonathangjertsen

Da kan heller selve problemet være vanskeligere IMO.

Vanskelig problemstilling. Oppgaven med å finne volum til en 3d-figur ble også lett kritisert fordi den krevde matte-kunnskaper, eller evnen til å Google formel. Jeg er litt enig. Som utvikler syns jeg ikke at man skal måles på hvor flink man er til å Google, skjønt jeg må innrømme at jeg selv Googler flittig (og jeg får betalt for å utvikle software). Det er tross alt ikke alle som har alt i hodet. ;-)

Så hvordan skal vi øke vanskelighetsgraden?
Tja, noe a la "Ackermann function" tvinger alle til å finne på noe rekursivt. Da siler vi ut alle som ikke behersker rekursjon. Men Ackermann kan googles... Det å finne en funksjon, som ikke er "primitive recursive" og som ikke finens på Google, er ikke lett... Vi kan ikke forlange det av oppgaveforfatteren.

Jeg mener at oppgavene her absolutt holder god kvalitet, bortsett fra gårsdagens der jeg løste den med buggy software. Slikt skal ikke forekomme. Seile-oppgaven kunne også løses med unøyaktig kode.

@flogvit

This comment has been minimized.

Copy link

@flogvit flogvit commented Dec 19, 2019

@jonathangjertsen @bobcat4

Personlig liker jeg oppgaver som denne og f eks labyrinten, der man i begynnelsen ikke var helt spesifikk på hva som er med. Hvis man leser oppgaven og ser på datasettet så sier det seg selv. Ta i dag. Er 1 eller 123454321 med? Vel, hadde man lest at skjulte palindromer ikke er palindromer i utgangspunktet så vet man jo at 1 og 123454321 ikke skal være med. I labyrinten stod det x og y, og det kunne bety at man satte det opp som et koordinatsystem og begynte nede til venstre. Problemet var at det var kun døren nedover som var åpen, dermed måtte systemet begynne oppe til venstre for å komme seg ut.

Og jeg er for å google. Oppgaver i jobbsammenheng skal løses på en gitt tid. Hva du kan før du begynner spiller ingen rolle, så lenge man løser oppgaven på den tiden man skal. En av grunnene til at jeg likte UiO sin tilnærming på eksamen der man kunne ha med alle bøkene man ville, for det var produktet man produserte i løpet av n timer med eksamen som var viktig.

@Suppen

This comment has been minimized.

Copy link

@Suppen Suppen commented Dec 19, 2019

@bobcat4 Project Euler, som denne kalenderen forøvrig er inspirert av, har en stor mengde problemer som er veldig klart definert, med eksempler. Utfordringen ligger i å finne en (effektiv) algoritme. De fleste kan man komme opp med en form for brute-force på, men det vil ofte ta altfor mye tid eller minne, men alle problemene kan løses på under ett minutt med en god algoritme.

Gårsdagens oppgave var jo helt på bærtur i klarhet. Skulle mellomrommet telles med i lengden på det fulle navnet? Hvilken alfabetposisjon har mellomrom? Eller '? Vi begge, og flere, fikk feil svar på den grunnet uklarheter i oppgaveteksten, uten at vi hadde noe reell mulighet til å finne ut hva som var galt. Et eksempel med et kvinnenavn, som jo hadde en helt annen algoritme på etternavnet, ville ikke vært å forakte.

Men nå er det jo også sånn at kunder altfor ofte vil ha "en app som gjør data, helst i skyen", så å tolke en oppgave og å lese mellom linjene for å finne ut hva som egentlig ønskes er jo også en nyttig egenskap.

@jonathangjertsen

This comment has been minimized.

Copy link

@jonathangjertsen jonathangjertsen commented Dec 19, 2019

Men nå er det jo også sånn at kunder altfor ofte vil ha "en app som gjør data, helst i skyen", så å tolke en oppgave og å lese mellom linjene for å finne ut hva som egentlig ønskes er jo også en nyttig egenskap.

Haha, jeg tenkte akkurat det samme! Hvis oppgavene skal samsvare med det man gjør i arbeidslivet er det viktig å ha en ufullstendig spesifikasjon.

@amumurst

This comment has been minimized.

Copy link

@amumurst amumurst commented Dec 19, 2019

Så litt på optimalisering. Først og fremst var det reverse metodens toString som brukte mye tid (selvsagt). skrev ut en spesifikk reversering for long så speedet det opp en hel del. Løser seg nå på ~5sek (kompilert med graal native-image på mb pro 2018). Forrige brukte ~1:30min.

object Day19 extends App {
  def reverse(l: Long, acc: Long = 0): Long = if(l == 0) acc else reverse(l / 10, acc*10 + l%10)
  def isHiddenPalindrome(l: Long)(r: Long = reverse(l)) = reverse(r + l) == r + l && (l != r)
  println(Iterator.from(1).map(_.toLong).take(123454321).filter(isHiddenPalindrome(_)()).sum)
}
@bobcat4

This comment has been minimized.

Copy link

@bobcat4 bobcat4 commented Dec 19, 2019

@Suppen @jonathangjertsen
I så fall bør oppgaven lyde: Lag noe som er bra. Vi vet ikke hva det er så du må prøve forskjellige varianter av en vag idé som vi har. Regn med masse endringer! :-)

Joda, kjenner meg igjen. Vi må veldig ofte komme opp med kravspesifikasjonen selv...

how-users-see-programmers

@iamxerc

This comment has been minimized.

Copy link

@iamxerc iamxerc commented Dec 19, 2019

Fikk feil svar fordi jeg mener selv at palindrom som også er skjulte palindrom skal taes med. Nå er det ikke alle som er utviklere som skal lage ting etter spesifikasjoner (eller mangel på) her heller 😜 Tingen under kjører vel på 45 sekunder ish 😅

<?php
function hp($i) {
    $r = strrev($i);
    return ($i != $r ? ($i+$r == strrev($i+$r)) : false);
}
for($i=0,$sum=0;$i<=123454321;$i++,(hp($i) ? $sum += $i : ''));
echo $sum;
@jostyposty

This comment has been minimized.

Copy link

@jostyposty jostyposty commented Dec 19, 2019

Vil bare presisere: Jeg liker denne kalenderen og oppgavene veldig godt! Mange er veldig morsomme og unnagjort på under et kvarter. Helt perfekt for en kaffepause. Og noen er litt vanskeligere selvsagt, men helt innenfor, selv i en hektisk førjulstid. Tommel opp!

Ja, og så liker jeg at det ikke er noe stress med å måtte løse oppgaven først og sånn. Man kan ta det når det passer :)

@iamxerc

This comment has been minimized.

Copy link

@iamxerc iamxerc commented Dec 19, 2019

Ja, og så liker jeg at det ikke er noe stress med å måtte løse oppgaven først og sånn. Man kan ta det når det passer :)

Enig! Ikke alle holder på med slikt daglig (eller står opp 06), morro å få en sjangs, samt å faktisk få til oppgavene 😄

@MarcusTL12

This comment has been minimized.

Copy link

@MarcusTL12 MarcusTL12 commented Dec 19, 2019

Gadd ikke implementere noe raskt enda. Enkel løsning i julia med å reversere String, som er notorisk tregt med kjøretid på 50 sec, menmen.

palindrome(n) = (s = string(n)) == reverse(s)


function hiddenpalindrome(n)
    palindrome(n + parse(Int, reverse(string(n)))) && !palindrome(n)
end


function main()
    sum(filter(hiddenpalindrome, 1 : 123454321))
end

Edit:
forbedret løsningen en del med å skrive en mer fornuftig reverserings funksjon. Med å gjøre det alene gikk tiden ned til 13 sec.

amtdigits(n) = floor(Int, log10(n) + 1)


function reversenum(n)
    d = amtdigits(n)
    
    nnum = 0
    
    for i in 1 : d
        nnum *= 10
        nnum += n % 10
        n ÷= 10
    end
    
    nnum
end


palindrome(n) = n == reversenum(n)


function hiddenpalindrome(n)
    palindrome(n + reversenum(n)) && !palindrome(n)
end


function main()
    sum(filter(hiddenpalindrome, 1 : 123454321))
end
@langemyh

This comment has been minimized.

Copy link

@langemyh langemyh commented Dec 19, 2019

Alt for lang kjøretid, men hjernen min klarer ikke helt å finne bedre måter

#!/usr/bin/python
psum = 0 
for i in xrange(1, 123454321+1):
    ir = int(str(i)[::-1])
    rsum = i + ir
    if rsum == int(str(rsum)[::-1]):
        psum += 1 if not i == ir else 0
print psum
@Intellipush

This comment has been minimized.

Copy link

@Intellipush Intellipush commented Dec 19, 2019

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);`
@ricardivntnu

This comment has been minimized.

Copy link

@ricardivntnu ricardivntnu commented Dec 19, 2019

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));
@matslindh

This comment has been minimized.

Copy link

@matslindh matslindh commented Dec 19, 2019

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)
@AndersSteenNilsen

This comment has been minimized.

Copy link

@AndersSteenNilsen AndersSteenNilsen commented Dec 19, 2019

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

This comment has been minimized.

Copy link

@hildenost hildenost commented Dec 19, 2019

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

This comment has been minimized.

Copy link

@aude aude commented Dec 19, 2019

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)
}
@bgrasmo

This comment has been minimized.

Copy link

@bgrasmo bgrasmo commented Dec 19, 2019

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;
}
@danieman

This comment has been minimized.

Copy link

@danieman danieman commented Dec 19, 2019

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.

@jostyposty

This comment has been minimized.

Copy link

@jostyposty jostyposty commented Dec 19, 2019

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

@christianfosli

This comment has been minimized.

Copy link

@christianfosli christianfosli commented Dec 19, 2019

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

This comment has been minimized.

Copy link

@sat90 sat90 commented Dec 19, 2019

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)
@anderaus

This comment has been minimized.

Copy link

@anderaus anderaus commented Dec 19, 2019

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());
@terjew

This comment has been minimized.

Copy link

@terjew terjew commented Dec 19, 2019

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;
        }
    }
}
@finnmich

This comment has been minimized.

Copy link

@finnmich finnmich commented Dec 19, 2019

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;
        }
@Runebjo

This comment has been minimized.

Copy link

@Runebjo Runebjo commented Dec 19, 2019

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);
@Aha43

This comment has been minimized.

Copy link

@Aha43 Aha43 commented Dec 19, 2019

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());
    }
}
@hakonrossebo

This comment has been minimized.

Copy link

@hakonrossebo hakonrossebo commented Dec 19, 2019

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

This comment has been minimized.

Copy link

@Stian108 Stian108 commented Dec 19, 2019

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)
@gunnar2k

This comment has been minimized.

Copy link

@gunnar2k gunnar2k commented Dec 19, 2019

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()
@Stian108

This comment has been minimized.

Copy link

@Stian108 Stian108 commented Dec 19, 2019

@flogvit Alternativt summen av A065206

@aude

This comment has been minimized.

Copy link

@aude aude commented Dec 19, 2019

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)
}
@michaelo

This comment has been minimized.

Copy link

@michaelo michaelo commented Dec 19, 2019

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

@terjew

This comment has been minimized.

Copy link

@terjew terjew commented Dec 19, 2019

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;
        }
@michaelo

This comment has been minimized.

Copy link

@michaelo michaelo commented Dec 19, 2019

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

@kennydl

This comment has been minimized.

Copy link

@kennydl kennydl commented Dec 20, 2019

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;
}
@terjew

This comment has been minimized.

Copy link

@terjew terjew commented Dec 20, 2019

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

@michaelo

This comment has been minimized.

Copy link

@michaelo michaelo commented Dec 20, 2019

@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 🤷‍♂️ .

@danieman

This comment has been minimized.

Copy link

@danieman danieman commented Dec 20, 2019

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

@aude

This comment has been minimized.

Copy link

@aude aude commented Dec 20, 2019

@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)
}
@michaelo

This comment has been minimized.

Copy link

@michaelo michaelo commented Dec 20, 2019

@aude: Pent!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.