The Weekly Challenge #293

Similar Dominoes • Boomerang
Official Challenge • My Solutions on GitHub

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))$.

  1. In a first pass, normalize every domino and count occurrences of each canonical representation using a hash map (or dictionary).
  2. 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:

  1. Distinctness: No two points are identical. We can verify this by checking that the size of the set of points equals 3.
  2. 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"