RogerBW's Blog

Perl Weekly Challenge 127: Disjoint Conflict 26 August 2021

I’ve been doing the Weekly Challenges. The latest involved set intersections and merging intervals. (Note that this is open until 29 August 2021.)

TASK #1 › Disjoint Sets

You are given two sets with unique integers.

Write a script to figure out if they are disjoint.

I.e. they have no members in common, which is the same as saying that the intersection of the two sets is empty.

The "modern" languages on my palette have sets and set operations built in, so for example in Raku:

  my $sa=set @a;
  my $sb=set @b;
  my $inter=$sa (&) $sb;
  if $inter.elems == 0 {
    return 1;
  } else {
    return 0;
  }

Ruby has &, and Python and Rust have an intersection() method in their Set class. So that's easy.

Perl doesn't have a set class, but its hashes are ferociously optimised; so I turn the first set into a hash (the values are irrelevant, it's just the keys that matter), then test each member of the second set to see if it's in the first.

sub ds {
  my ($a,$b)=@_;
  my %h=map {$_ => 1} @{$a};
  foreach my $n (@{$b}) {
    if (exists $h{$n}) {
      return 0;
    }
  }
  return 1;
}

PostScript doesn't have sets either, but it does have dicts which include a known method, so I use the same trick. (Interesting how divergent the terminology is round associative arrays, starting with whether they're called that, a dictionary, a hash, a map, a collection or a table. For testing whether a particular key is defined, we might have exists, known, has_key?, in, contains… the idea has been around for a while, I believe first getting language support in 1969's SNOBOL4, so it's surprising the terminology hasn't settled out the way e.g. arrays and indices have.)

/ds {
    dup length dict /dd exch def
    {
       dd exch 1 put
    } forall
    /dj 1 def
    {
        dd exch known {
            /dj 0 def
            exit
        } if
    } forall
    dj
} def

TASK #2 › Conflict Intervals

You are given a list of intervals.

Write a script to find out if the current interval conflicts with any of the previous intervals.

Not quite the standard coding-interview problem (see PWC #50), which would ask you to reduce the intervals to a minimal set (e.g. if you had (1,3) and (2,4) you'd merge them and spit out (1,4)). One normally starts the approach to that problem by sorting the input, but the desired result here will differ based on the order in which things occur (the first interval given can never conflict with anything).

So for each interval after the first, check all earlier intervals for possible overlap. If we find one, put this interval in the output queue and go on to the next one. One might also do the merge to reduce the list of earlier intervals that need to be checked, but I'm not convinced it would be helpful.

Any overlap will match at least one of these conditions:

  • the lower bound lies within the earlier interval
  • the upper bound lies within the earlier interval
  • the lower bound is below the earlier interval, and the upper bound is above it

The Ruby code is probably the easiest to read.

def ci(a)
  o=[]
  1.upto(a.length-1) do |i|
    0.upto(i-1) do |j|
      if (a[i][0] >= a[j][0] && a[i][0] <= a[j][1]) ||
         (a[i][1] >= a[j][0] && a[i][1] <= a[j][1]) ||
         (a[i][0] <= a[j][0] && a[i][1] >= a[j][1]) then
        o.push(a[i])
        break
      end
    end
  end
  return o
end

Full code on github.

See also:
Perl Weekly Challenge 50: merged intervals and noble integers

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

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 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 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 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-nebula reread in brief avoid instrumented life julie enfield kickstarter learn to play leaving earth linux liquor lovecraftiana mecha men with beards museum music mystery naval 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 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