Task 1: Similar Dominoes
You are given a list of dominoes, where each domino is represented as [a, b]. Two dominoes [a, b] and [c, d] are similar if (a == c and b == d) or (a == d and b == c). Write a script to return the count of dominoes that are similar to at least one other domino.
Method Explanation
Two dominoes are identical regardless of their rotation. Therefore, each domino $[a, b]$ can be normalized into a canonical representation by sorting its pair: $(\min(a, b), \max(a, b))$.
- In a first pass, normalize every domino and count occurrences of each canonical representation using a hash map (or dictionary).
- In a second pass, iterate through the original list of dominoes. Any domino whose canonical key has a count $> 1$ belongs to a cluster of duplicates and contributes to the total count.
This approach operates in optimal $O(N)$ time and $O(N)$ space.
Perl Implementation
sub count_similar_dominos ($dominos) {
($dominos) = $DOMINOES_CHECK->($dominos);
my %domino_counts;
my $count = 0;
for my $domino (@$dominos) {
die 'Each domino must have exactly 2 integers' if @$domino != 2;
my ( $u, $v ) = @$domino;
my $key = join( ',', sort { $u <=> $v } ( $u, $v ) );
$domino_counts{$key}++;
}
for my $domino (@$dominos) {
my ( $u, $v ) = @$domino;
my $key = join( ',', sort { $u <=> $v } ( $u, $v ) );
if ( $domino_counts{$key} > 1 ) {
$count++;
}
}
return $count;
}
Python Implementation
def count_similar_dominos(dominos: Sequence[Sequence[int]]) -> int:
"""Return the count of dominoes that have at least one similar domino."""
domino_counts: dict[tuple[int, int], int] = {}
for domino in dominos:
if len(domino) != 2:
raise ValueError("Each domino must have exactly 2 numbers")
key = tuple(sorted(domino))
domino_counts[key] = domino_counts.get(key, 0) + 1
count = 0
for domino in dominos:
key = tuple(sorted(domino))
if domino_counts[key] > 1:
count += 1
return count
Task 2: Boomerang
You are given an array of three points in a 2D plane: [[x1, y1], [x2, y2], [x3, y3]]. A boomerang is a set of three points that are all distinct and not in a straight line. Write a script to return 'true' if the given points form a boomerang, 'false' otherwise.
Method Explanation
A set of three 2D points forms a boomerang if and only if two geometric conditions are satisfied:
- Distinctness: No two points are identical. We can verify this by checking that the size of the set of points equals 3.
- Non-collinearity: The points do not lie on the same straight line. In 2D coordinate geometry, the slope between $P_1$ and $P_2$ equals the slope between $P_1$ and $P_3$ if and only if: $$\frac{y_2 - y_1}{x_2 - x_1} = \frac{y_3 - y_1}{x_3 - x_1}$$ To avoid division by zero for vertical lines, we cross-multiply into the 2D cross-product determinant: $$(x_2 - x_1) \cdot (y_3 - y_1) - (y_2 - y_1) \cdot (x_3 - x_1) \ne 0$$
If the determinant is nonzero and all 3 points are distinct, they form a boomerang.
Perl Implementation
sub is_boomerang ($points) {
($points) = $POINTS_CHECK->($points);
die 'Exactly three points are required' if @$points != 3;
for my $p (@$points) {
die 'Each point must have 2 coordinates' if @$p != 2;
}
my ( $x1, $y1 ) = @{ $points->[0] };
my ( $x2, $y2 ) = @{ $points->[1] };
my ( $x3, $y3 ) = @{ $points->[2] };
my %point_set;
$point_set{"$x1,$y1"}++;
$point_set{"$x2,$y2"}++;
$point_set{"$x3,$y3"}++;
return 'false' if scalar keys %point_set < 3;
my $cross_product = ( $x2 - $x1 ) * ( $y3 - $y1 ) - ( $y2 - $y1 ) * ( $x3 - $x1 );
return $cross_product != 0 ? 'true' : 'false';
}
Python Implementation
def is_boomerang(points: Sequence[Sequence[int]]) -> str:
"""Return 'true' if the 3 points form a boomerang (distinct, non-collinear), 'false' otherwise."""
if len(points) != 3:
raise ValueError("Exactly three points are required")
point_set = set(tuple(p) for p in points)
if len(point_set) < 3:
return "false"
(x1, y1), (x2, y2), (x3, y3) = points
determinant = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
return "false" if determinant == 0 else "true"