RogerBW's Blog

Perl Weekly Challenge 65: summing digits and finding palindromes 23 June 2020

I’ve been doing the Perl Weekly Challenges. The latest involved generating large numbers and splitting strings into palindromes.

You are given two positive numbers $N and $S.

Write a script to list all positive numbers having exactly $N digits where sum of all digits equals to $S.

Well what do you know, it's another breadth-first search with a FIFO buffer. This time each buffer entry contains the digits so far, ending with their sum.

my @out;
my @l;
do {
  my $n=[0];
  if (@l) {
    $n=shift @l;
  }
  my $s=pop @{$n};

This is where we get sneaky. If we already have all-but-one of the digits, there's only one possible value the last digit can have.

  if (scalar @{$n} == $N-1) {
    my $digit=$S-$s;
    if ($digit>=0 && $digit<=9) {
      push @out,join('',@{$n},$digit);
    }
  } else {

Otherwise, append each digit that doesn't make the sum too large. (We can always end with a string of zeroes.)

    foreach my $digit (($s==0?1:0)..min($S-$s,9)) {
      push @l,[@{$n},$digit,$s+$digit];
    }
  }
} while (@l);

print join(', ',sort @out),"\n";

Perl6 is basically the same, with the trick to get it to put a plain list in my list.

push @l,(map {$_},@n,$digit,$s+$digit);

(What's the precedence of map vs comma? It doesn't matter.)

You are given a string $S. Write a script print all possible partitions that gives Palindrome. Return -1 if none found.

Please make sure, partition should not overlap. For example, for given string “abaab”, the partition “aba” and “baab” would not be valid, since they overlap.

Well, I started this, but then I realised that the examples were inconsistent with the problem statement. The second example makes it clear that you don't have to include all characters in the string in your output (a valid answer for "abbaba" is "abba"); but then why do the valid answers for "aabaab" not include "aabaa"? Therefore my answer is:

The problem is underspecified and cannot be solved unambiguously.

(Also the obvious way to do this is yet another BFS with FIFO buffer and I am bored with every problem having basically the same solution. It's like those stories they tell kids in the sort of metachurchy things that are meant to persuade them of the wonderfulness of God: if you are not entirely stupid, you rapidly notice that the answer is always Jesus so the story was just an excuse.)

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1