RogerBW's Blog

Perl Weekly Challenge 115: Largest Chain 05 June 2021

I’ve been doing the Perl Weekly Challenges. The latest involved chained strings and number construction. (Note that this is open until 6 June 2021.)

TASK #1 › String Chain

You are given an array of strings.

Write a script to find out if the given strings can be chained to form a circle. Print 1 if found otherwise 0.

A string $S can be put before another string $T in circle if the last character of $S is same as first character of $T.

In other words, can you by changing the order of the strings arrange them so that for each adjacent pair the last character of the first is the first character of the next – with a wrap round at the end?

This isn't really a part 1 question, because of two extra cases that make it distinctly less trivial:

  • There might be two separate cycles (e.g. abc dea fgh hif), so merely counting and matching string starts and ends won't work.
  • There might be one cycle but multiple ways of assembling the sequence (e.g. abc cgd dec cfa), of which only some are valid – so using a simple hash table that maps starts to ends won't work.

So one approach would be to permute and filter the strings, but I've done permutation searches, so I thought I'd try something a bit more specific to this particular problem.

sub sc {
  my @n=@_;

I ended up building two structures: m is a list of final characters of strings (same index numbers as the strings themselves), and i is a hash (keyed on first characters) of lists of indices of strings starting with those characters. So in the first test case (abc dea cd), m is [c,a,d], and i is {a => [0], d => [1], c => [2]}.

  my @m;
  my %i;
  foreach my $t (@n) {
    push @m,substr($t,-1,1);
    push @{$i{substr($t,0,1)}},$#m;
  }

chain is the search path, containing a list of lists of indices.

  my @chain=([0]);

Each time I look at extending the path, I pull the last entry off the chain (we don't care whether we're depth-first or breadth-first here), then construct a list of valid indices that might extend it – i.e. all the indices that it doesn't already use. If there are none left, we have used each element once.

  while (@chain) {
    my $stub=pop @chain;
    my %v=map {$_ => 1} (0..$#n);
    map {delete $v{$_}} @{$stub};

If there are any valid extensions, see if any of them matches the last character of the current path, and continue.

    if (%v) {
      if (exists $i{$m[$stub->[-1]]}) {
        my @x=grep {exists $v{$_}} @{$i{$m[$stub->[-1]]}};
        foreach my $x (@x) {
          push @chain,[@{$stub},$x];
        }
      }

Otherwise we might have an actual solution. We've used all the pieces; did we get back to where we started? (This was a bug in my original code.)

    } else {
      if (exists $i{$m[$stub->[-1]]} && $i{$m[$stub->[-1]]}[0]==0) {
        return 1;
      }
    }
  }
  return 0;
}

Not much to see in the other languages, except that they have sets (hashes that just have keys, not values), which I use for v.

TASK #2 › Largest Multiple

You are given a list of positive integers (0-9), single digit.

Write a script to find the largest multiple of 2 that can be formed from the list.

Well, there's a simple optimisation here that beats brute force (a bit like last week's part 2): put the lowest even character at the right-hand end of the string to make the result even, and sort the rest into descending order.

Only one extra test case this time: what if no even number can be constructed at all? (I choose to return 0.)

List::MoreUtils has firstidx to do this in one operation in Perl, but that's not a core module; in the other languages I was able to extract both index and value in a single operation. Overall this turned out to be rather less work than part 1 was, in fact. Raku:

sub lm(**@n) {
  my @o=sort @n;
  my ($i,$t)=@o.first({$_ % 2 == 0}, :kv);
  unless (defined $i) {
    return 0;
  }
  splice @o,$i,1;
  @o=reverse @o;
  push @o,$t;
  return join('',@o);
}

The other languages work similarly, with more or less complication (especially if they don't have an equivalent of splice and you have to build up the output piece by piece).

Full code on github.


  1. Posted by RogerBW at 10:58am on 08 June 2021

    An interpretation I didn't spot for part 1 was that you might be allowed to make a cycle with fewer than all the strings. Treating this as a directed graph problem is probably a more efficient approach than mine, and there was a wide range of interesting approaches.

    For part 2, almost everyone took the same basic approach: sort the digits descending, extract the lowest even one from the list and put it on the end. (A couple of exceptions: generate all permutations, filter for even, take highest.)

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 advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2022 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript 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 ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge 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