RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved checking dominoes and doing some floating-point operations. (Note that this ends today.)

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 the same if either (a = c and b = d) or (a = d and b = c).

The obvious (to me) way of solving this is to use a hash function which will have the same value for both [y, x] and [x, y]. Perl:

sub dvalue($a) {
  if ($a->[0] < $a->[1]) {
    return $a->[0] * 64 + $a->[1];
  } else {
    return $a->[0] + $a->[1] * 64
  }
}

sub similardominoes($a) {

Count dominoes by hash value.

  my %c;
  map {$c{dvalue($_)}++} @{$a};

Then look through its values. Any bucket with more than one item in it contains dominoes that are similar to any other domino.

  my $t = 0;
  foreach my $v (values %c) {
    if ($v > 1) {
      $t += $v;
    }
  }
  return $t;
}

A counter class is useful once again in languages that have one.

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.

Usual warnings apply with respect to floating-point equality, though the test cases all worked for me in all the languages.

Python:

def boomerang(a):

First, check for coincident points (always return false), and if that passes establish a set of deltas: p0 to p1, p0 to p2. (Yes, I'm doing two unrelated things in the outer loop. I think I may have picked up that habit in my very brief C days, when setting up even a straightforward loop meant mucking about with end conditions.)

  delta = []
  for ij in range(2):
    for ik in range(ij + 1, 3):
      if a[ij][0] == a[ik][0] and a[ij][1] == a[ik][1]:
        return False
    delta.append([a[ij + 1][0] - a[0][0], a[ij + 1][1] - a[0][1]])

If all three points have the same X value, return false.

  if delta[0][0] == 0 and delta[1][0] == 0:
    return False

Otherwise, if just one pair does, return true. (This won't spot the case where p1 and p2 are on the same vertical line distinct from p0, but that's OK; I'm only doing this special case so that my main algorithm won't divide by zero.)

  if delta[0][0] == 0 or delta[1][0] == 0:
    return True

Now we know that delta-X from p0 to p1 is not zero, so we can establish a slope for the line from p0 to p1.

  m = delta[0][1] / delta[0][0]

And a Y-offset. (Yeah, I still think in terms of y = mx + c not y = a + bx. Also I tend to use a as the input variable in these things.)

  c = a[0][1] - a[0][0] * m

Then it's a boomerang if p2 does not lie on that line.

  return a[2][1] != a[2][0] * m + c

Languages which distinguish floating-point obviously have a lot of type conversions in the last three lines.

Full code on github.