Perl Weekly Challenge: Oh, oh, Domino!

Don’t wanna discuss it
Think it’s time for a change
You may get disgusted
Start thinking that I’m strange

I mean, I guess I am strange for always wanting to include music in the weekly challenge, but with a first challenge like this, how could I not link to Van Morrison’s Domino.

There’s no need for argument in Perl Weekly Challenge 293.

Task 1: Similar Dominos

You are given a list of dominos, @dominos.

Write a script to return the number of dominoes that are similar to any other domino.

$dominos[i] = [a, b] and $dominos[j] = [c, d] are same if either (a = c and b = d) or (a = d and b = c).

Example 1

Input: @dominos = ([1, 3], [3, 1], [2, 4], [6, 8])
Output: 2

Similar Dominos: $dominos[0], $dominos[1]

Example 2

Input: @dominos = ([1, 2], [2, 1], [1, 1], [1, 2], [2, 2])
Output: 3

Similar Dominos: $dominos[0], $dominos[1], $dominos[3]

Approach

I mean, this seems like a double loop to me: loop over each domino, compare it to the rest of the dominoes. The inner loop gets smaller as we progress through, because we’ll have already compared dominoes.

But something about this input set bothered me: both examples have only one set of dominoes that are similar to other dominoes. What if we had the following?

Input: @dominos = ([1, 2], [3, 4], [2, 1], [4, 3], [1, 2])
Output: 5

Similar Dominos:
  + $dominos[0], $dominos[2], $dominos[4] 
  + $dominos[1], $dominos[3]

There are two distinct sets of dominoes that are similar to any other domino. I should be able to maintain separate lists.

Raku

I’m using a hash %already_matched to skip over dominoes I’ve already matched so I don’t double-count them.

sub isSimilar(@d1, @d2) {
  return (
    (@d1[0] == @d2[0] && @d1[1] == @d2[1])
    ||
    (@d1[0] == @d2[1] && @d1[1] == @d2[0])
  );
}

sub similarDominos(@dominos) {
  my %already_matched;
  my @similar;
  my $sim_count = 0;
  for 0 .. @dominos.end - 1 -> $i {
    next if %already_matched{$i};
    my @sim;
    for $i + 1 .. @dominos.end -> $j {
      next if %already_matched{$j};
      if (isSimilar(@dominos[$i], @dominos[$j])) {
        # only push $i onto the list if this is the first match
        unless %already_matched{$i} {
          @sim.push("\$dominos[$i]");
          $sim_count++;
          %already_matched{$i} = 1;
        }
        @sim.push("\$dominos[$j]");
        $sim_count++;
        %already_matched{$j} = 1;
      }
    }
    @similar.push(@sim) if @sim.elems > 0;
  }
  my $explain = "Similar Dominos: ";
  if ($sim_count == 0) {
    $explain ~= "none";
  }
  elsif (@similar.elems == 1) {
    $explain ~= @similar[0].join(", ");
  }
  else {
    my @s = @similar.map({ .join(", ") });
    $explain ~= "\n + " ~ @s.join("\n + ");
  }
  return $sim_count, $explain;
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
Example 1:
Input: @arr = ([1, 3], [3, 1], [2, 4], [6, 8])
Output: 2

Similar Dominos: $dominos[0], $dominos[1]

Example 2:
Input: @arr = ([1, 2], [2, 1], [1, 1], [1, 2], [2, 2])
Output: 3

Similar Dominos: $dominos[0], $dominos[1], $dominos[3]

Example 3:
Input: @arr = ([1, 2], [3, 4], [2, 1], [4, 3], [1, 2])
Output: 5

Similar Dominos:
 + $dominos[0], $dominos[2], $dominos[4]
 + $dominos[1], $dominos[3]

Perl

Easy-peasy translation from Raku into Perl. Sibling languages, indeed!

sub isSimilar($d1, $d2) {
  return (
    ($$d1[0] == $$d2[0] && $$d1[1] == $$d2[1])
    ||
    ($$d1[0] == $$d2[1] && $$d1[1] == $$d2[0])
  );
}

sub similarDominos(@dominos) {
  my %already_matched;
  my @similar;
  my $sim_count = 0;
  foreach my $i ( 0 .. $#dominos - 1) {
    next if $already_matched{$i};
    my @sim = ();
    foreach my $j ( $i + 1 .. $#dominos ) {
      next if $already_matched{$j};
      if (isSimilar($dominos[$i], $dominos[$j])) {
        # only push $i onto the list if this is the first match
        unless ($already_matched{$i}) {
          push @sim, "\$dominos[$i]";
          $sim_count++;
          $already_matched{$i} = 1;
        }
        push @sim, "\$dominos[$j]";
        $sim_count++;
        $already_matched{$j} = 1;
      }
    }
    push @similar, \@sim if @sim > 0;
  }
  my $explain = "Similar Dominos: ";
  if ($sim_count == 0) {
    $explain .= "none";
  }
  elsif (@similar == 1) {
    $explain .= join(", ", @{$similar[0]});
  }
  else {
    my @s = map { join(", ", @$_) } @similar;
    $explain .= "\n + " . join("\n + ", @s);
  }
  return $sim_count, $explain;
}

View the entire Perl script for this task on GitHub.

Python

The more I do these, the easier it gets to rewrite Raku into Python.

def isSimilar(d1, d2):
  return (
    (d1[0] == d2[0] and d1[1] == d2[1])
    or
    (d1[0] == d2[1] and d1[1] == d2[0])
  )

def similarDominos(dominos):
  already_matched = {}
  similar = []
  sim_count = 0
  for i in range(len(dominos)-1):
    if i in already_matched:
      continue
    sim = []
    for j in range(i + 1, len(dominos)):
      if j in already_matched:
        continue
      if isSimilar(dominos[i], dominos[j]):
        # only push $i onto the list if this is the first match
        if i not in already_matched:
          sim.append(f"$dominos[{i}]")
          sim_count += 1
          already_matched[i] = 1
        sim.append(f"$dominos[{j}]")
        sim_count += 1
        already_matched[j] = 1
    if len(sim) > 0:
      similar.append(sim)
  explain = "Similar Dominos: "
  if (sim_count == 0):
    explain += "none"
  elif len(similar) == 1:
    explain += comma_join(similar[0])
  else:
    s = [ ', '.join(d) for d in similar ]
    explain += "\n + " + "\n + ".join(s)
  return sim_count, explain

View the entire Python script for this task on GitHub.

Elixir

I have to admit that I had trouble getting this one to work, so I stopped working on it to work on Task 2. After not getting my recursive processing of the list of dominoes to work, I decided to take a suggestion I’d seen while working on the Elixir solution for Task 2: convert the list to a map, which would then allow me to access the elements via their subscript without resorting to Enum.at/3. Once I decided to do that, I was able to render the same approach I used in Raku / Perl / Python in Elixir.

The only thing that’s kind of annoying is that because Elixir is functional, any values bound within a code block need to be returned from that code block to be used later. So if I make changes to data inside an if statement, I need to return data from that if statement and bind the return from the if to the data label… or my changes are lost.

  def isSimilar(d1, d2) do
    (Enum.at(d1,0) == Enum.at(d2,0)
     &&
     Enum.at(d1,1) == Enum.at(d2,1))
    ||
    (Enum.at(d1,0) == Enum.at(d2,1)
     &&
     Enum.at(d1,1) == Enum.at(d2,0))
  end

  def similarDominos(dominos) do
    last = length(dominos)-1
    # convert list to map
    dominos = 0..last |> Stream.zip(dominos) |> Enum.into(%{})
    data = %{
      count: 0,
      similar: [],
      i_sim: [],
      matched: %{}
    }
    {_, data} = Enum.map_reduce(0..last-1, data,
    fn i, data ->
      data = if ! data[:matched][i] do
        {_, data} = Enum.map_reduce(i+1..last, data,
        fn j, data ->
          data = if ! data[:matched][j] do
            data = if isSimilar(dominos[i], dominos[j]) do
              data = if ! data[:matched][i] do
                data
                |> Map.put(:count, data[:count] + 1)
                |> Map.put(:matched, Map.put(data[:matched], i, true))
                |> Map.put(:i_sim, data[:i_sim] ++ ["$dominos[#{i}]"])
              else
                data
              end
              data
              |> Map.put(:count, data[:count] + 1)
              |> Map.put(:matched, Map.put(data[:matched], j, true))
              |> Map.put(:i_sim, data[:i_sim] ++ ["$dominos[#{j}]"])
            else
              data
            end
            data
          else
            data
          end
          {j, data}
        end)
        data
      else
        data
      end
      data = if length(data[:i_sim]) > 0 do
        data
        |> Map.put(:similar, data[:similar] ++ [ data[:i_sim] ])
        |> Map.put(:i_sim, [])
      else
        data
      end
      {i, data}
    end)
    explain = "Similar Dominos: " <> case length(data[:similar]) do
      0 -> "none"
      1 -> Enum.join(List.first(data[:similar]), ", ")
      _ ->
        s = Enum.map(data[:similar], fn s ->
          "[" <> Enum.join(s, ", ") <> "]"
        end)
        "\n + " <> Enum.join(s, "\n + ")
    end
    {data[:count], explain}
  end

View the entire Elixir script for this task on GitHub.


Task 2: Boomerang

You are given an array of points, (x, y).

Write a script to find out if the given points are a boomerang.

A boomerang is a set of three points that are all distinct and not in a straight line.

Example 1

Input: @points = ( [1, 1], [2, 3], [3,2] )
Output: true

Example 2

Input: @points = ( [1, 1], [2, 2], [3, 3] )
Output: false

Example 3

Input: @points = ( [1, 1], [1, 2], [2, 3] )
Output: true

Example 4

Input: @points = ( [1, 1], [1, 2], [1, 3] )
Output: false

Example 5

Input: @points = ( [1, 1], [2, 1], [3, 1] )
Output: false

Example 6

Input: @points = ( say  )
Output: true

Approach

How do we determine if the points are in a straight line? Well, there are three possibilities: 1) they all have the same x coordinate, 2) they all have the same y coordinate, or 3) the differences between the x and y coordinates for each is the same. Take Example 2: the points are (1,1), (2,2), (3,3). Each time, both the x and y coordinates go up by 1. Also look at Example 6, because it’s almost a straight line: (0,0), (2,3), (4,5). For each point, the x axis increases by 2. But while the y axis increases by 3 between the first two points, it only increases by 2 between the second and third. If the last point was (4,6) instead, then it would be a straight line.

Checking distinctness feels like a job for a hash again.

Raku

I’m really feeling lazy tonight. I could probably come up with some generalized solution that loops over the points and handles boomerangs of more than three points, but the problem description says a boomerang is “a set of three points”, so I can just manually compare them.

sub isBoomerang(@points) {
  # check that we have three distinct points
  my %distinct;
  for @points -> @p {
    %distinct{"@p[0],@p[1]"}++;
  }
  return 'false' if %distinct.keys.elems < 3;

  # is this a straight line on the X axis?
  return 'false'
    if @points[0][0] == @points[1][0] == @points[2][0];

  # is this a straight line on the Y axis?
  return 'false'
    if @points[0][1] == @points[1][1] == @points[2][1];

  # find the differences between the X coordinates
  my $x_diff_1 = @points[1][0] - @points[0][0];
  my $x_diff_2 = @points[2][0] - @points[1][0];

  # find the differences between the Y coordinates
  my $y_diff_1 = @points[1][1] - @points[0][1];
  my $y_diff_2 = @points[2][1] - @points[1][1];

  # straight line if the diffs are the same
  return 'false'
    if $x_diff_1 == $x_diff_2 && $y_diff_1 == $y_diff_2;

  return 'true';
}

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
Example 1:
Input: @points = ([1, 1], [2, 3], [3, 2])
Output: true

Example 2:
Input: @points = ([1, 1], [2, 2], [3, 3])
Output: false

Example 3:
Input: @points = ([1, 1], [1, 2], [2, 3])
Output: true

Example 4:
Input: @points = ([1, 1], [1, 2], [1, 3])
Output: false

Example 5:
Input: @points = ([1, 1], [2, 1], [3, 1])
Output: false

Example 6:
Input: @points = ([0, 0], [2, 3], [4, 5])
Output: true

Perl

sub isBoomerang(@points) {
  # check that we have three distinct points
  my %distinct;
  foreach my $p ( @points ) {
    $distinct{join ",", @$p}++;
  }
  return 'false' if keys(%distinct) < 3;

  # is this a straight line on the X axis?
  return 'false'
    if $points[0][0] == $points[1][0] == $points[2][0];

  # is this a straight line on the Y axis?
  return 'false'
    if $points[0][1] == $points[1][1] == $points[2][1];

  # find the differences between the X coordinates
  my $x_diff_1 = $points[1][0] - $points[0][0];
  my $x_diff_2 = $points[2][0] - $points[1][0];

  # find the differences between the Y coordinates
  my $y_diff_1 = $points[1][1] - $points[0][1];
  my $y_diff_2 = $points[2][1] - $points[1][1];

  # straight line if the diffs are the same
  return 'false'
    if $x_diff_1 == $x_diff_2 && $y_diff_1 == $y_diff_2;

  return 'true';
}

View the entire Perl script for this task on GitHub.

Python

def comma_join(arr):
    return ', '.join(map(lambda i: str(i), arr))

def isBoomerang(points):
  # check that we have three distinct points
  distinct = {}
  for p in points:
    distinct[ comma_join(p) ] = 1
  if len(list(distinct)) < 3:
    return 'false'

  # is this a straight line on the X axis?
  if points[0][0] == points[1][0] == points[2][0]:
    return 'false'

  # is this a straight line on the Y axis?
  if points[0][1] == points[1][1] == points[2][1]:
    return 'false'

  # find the differences between the X coordinates
  x_diff_1 = points[1][0] - points[0][0]
  x_diff_2 = points[2][0] - points[1][0]

  # find the differences between the Y coordinates
  y_diff_1 = points[1][1] - points[0][1]
  y_diff_2 = points[2][1] - points[1][1]

  # straight line if the diffs are the same
  if x_diff_1 == x_diff_2 and y_diff_1 == y_diff_2:
    return 'false'

  return 'true'

View the entire Python script for this task on GitHub.

Elixir

There really isn’t a good way to easily access the elements of a multi-dimentional lists in Elixir (after I wrote this I went looking and found a blog post suggesting converting the lists into a map), but I find that I actually like this code. It’s pretty readable.

  def isBoomerang(points) do
    # map how many distinct points we have
    {_, distinct} = Enum.map_reduce(points, %{}, fn p, distinct ->
      {p, Map.put(distinct, Enum.join(p, ","), true)}
    end)

    # extract the coordinates
    x0 = points |> Enum.at(0) |> Enum.at(0)
    x1 = points |> Enum.at(1) |> Enum.at(0)
    x2 = points |> Enum.at(2) |> Enum.at(0)
    y0 = points |> Enum.at(0) |> Enum.at(1)
    y1 = points |> Enum.at(1) |> Enum.at(1)
    y2 = points |> Enum.at(2) |> Enum.at(1)

    cond do
      # check that we have three distinct points
      distinct |> Map.keys |> length < 3 -> false
      # is this a straight line on the X axis?
      x0 == x1 == x2 -> false
      # is this a straight line on the Y axis?
      y0 == y1 == y2 -> false
      # straight line if the diffs are the same
      (x1 - x0 == x2 - x1) and (y1 - y0 == y2 - y1) -> false
      
      true -> true
    end
  end

View the entire Elixir script for this task on GitHub.


Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-293/packy-anderson

Leave a Reply