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, explainView 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}
endView 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: truePerl
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
endView 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