# Battling the 538 Riddler

Every Friday morning FiveThirtyEight posts a math challenge in their *Riddler* column. The May 21, 2021 problem featured “anti-isosceles” sets. I’ll let the Riddler himself explain in more detail:

But this week, Jordan is asking about what he calls

anti-isosceles sets. Consider aN×Ngrid of points. What is the greatest subset of theseN^{2}points such thatno three of themform an isosceles triangle? (Note: Degenerate triangles, or triangles with zero area,docount as triangles here, as long as their three vertices are distinct.)As shown below, the largest anti-isosceles set in a 2×2 grid has two points; for a 3×3 grid, the largest anti-isosceles set has four points. (Note: For both grids, there are multiple sets with these maximum numbers of points.)

[Source: FiveThirtyEight]

Although the problem asked readers to identify the maximum number of points in an anti-isosceles 4×4 grid, this post will walk through solving a 3×3 grid. The process is essentially unchanged but a 3×3 grid is much less computationally expensive.

The general strategy will be:

- Generate a list of all possible 3×3 grid “permutations.”
- Within each grid, find all unique triangles and check if any are isosceles.
- Filter out solutions that are a rotated copy of another.
- Plot the solutions.

This script will make extensive use of *NumPy *arrays to represent 3×3 grids. It will also take advantage of *itertools* from the standard library to generate permutations and combinations. And *Matplotlib* will visualize any solutions we discover.

import numpy as np from itertools import permutations, combinations from math import sqrt import matplotlib.pyplot as plt

#### 1. Find all possible 3×3 grids.

The first step is to create a list of all possible 3×3 grids. This means all grids that have 3 dots, plus all that have 4 dots, and so on. We can be fairly confident that any solution will have at least 3 points, so it seems reasonable to ignore grids with 0, 1 or 2. This will save some CPU cycles and if we fail to find an anti-isosceles solution, we can always come back and adjust.

At this point we can work with normal 1-dimensional Python lists. Once we have a list of grids we’ll reshape them into 3×3 *NumPy* arrays.

Positions where a point exists will be represented by a 1 and empty positions will be 0. I call the set of numbers from which to draw permutations the `well`

. For example, in the first pass of the loop below, `dots`

will be 3. That will generate a well equal to:

[1, 1, 1, 0, 0, 0, 0, 0, 0]

We then find all permutations of those 9 items. Since in this problem every point counts the same, i.e. there’s no difference between the first 1 and the second 1, we put the permutations into a Python `set`

, which eliminates duplicates.

possible_layouts = [] for dots in range(3, 10): well = [1] * dots + [0] * (9 - dots) perms = set(permutations(well, 9)) for layout in perms: possible_layouts.append(layout)

Our `possible_layouts`

list contains 466 unique grids—although at this point the grids are just lists of 9 numbers. Next comes the hunt for solutions. Which of the 466 grids contain zero isosceles triangles?

[Note: There is a more efficient way to generate all possible layouts that uses binary string formatting. I’ll mention it at the end of the post.]

#### 2. Find all unique triangles within each grid. Check if any are isosceles.

There’s more code than I’d like in the following snippet but it would be difficult to break it apart. Start by reading the `for`

loop near the bottom.

Each 1×9 list is reshaped into a 3×3 *NumPy* array. For example:

[[1 0 1] [1 1 0] [0 0 1]]

We use `np.where(grid == 1)`

to get coordinates of every occupied point within a grid. Then `itertools.combinations`

produces a list of all unique triangles among those points. The Riddler mentioned that we should count degenerate triangles, which in non-Batman-villain lingo are just straight lines.

Once we have a list of triangles represented by their vertices’ coordinates, it’s straightforward to check whether any is isosceles. That’s where `check_if_anti_isosceles()`

goes to work. If none of the triangles is isosceles then we’ve found a solution to the Riddler’s challenge!

The `check_if_anti_isosceles`

function works by initially setting a flag to `True`

. It assumes that a grid is anti-isosceles until proven otherwise. But it only takes 1 isosceles triangle for the assumption to be broken. Its approach is to find a triangle’s 3 side lengths and put them into a Python *set*, which as we saw above refuses to hold duplicate values. That’s useful when identifying isosceles triangles because if 2 side lengths are equal, the set will eliminate 1 of them and hold only 2 values. If the function sees a set with 2 values it knows that particular grid fails the anti-isosceles test. It breaks out of the loop and returns `False`

.

def get_distance(p1, p2): return sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) def check_if_anti_isosceles(triangles): is_anti_iso = True for tri in triangles: vertex1, vertex2, vertex3 = tri side_lengths = [get_distance(vertex1, vertex2), get_distance(vertex1, vertex3), get_distance(vertex2, vertex3)] if len(set(side_lengths)) == 2: is_anti_iso = False break return is_anti_iso solutions = [] for layout in possible_layouts: grid = np.array(layout) grid = grid.reshape((3, 3)) ones_y, ones_x = np.where(grid == 1) ones_coords = list(zip(ones_y, ones_x)) combs = list(combinations(ones_coords, 3)) # All possible triangles among the points. is_anti_isosceles = check_if_anti_isosceles(combs) if is_anti_isosceles: solutions.append(grid)

Grids that pass the test are appended to a `solutions`

list. However at this point the list will contain 4 grids for every “real” solution. That’s because solutions can be rotated 90, 180, or 270 degrees. We’ll deal with that in the next step.

#### 3. Filter duplicate solutions.

Before we filter rotated duplicate grids let’s check how many points are in the “best” solution(s). We already know it will be 4 because the Riddler told us, but just to be sure… That information can be used to ignore solutions that use fewer points.

Since *NumPy* has built-in safeguards against ambiguous truth evaluations (I know that’s a mouthful. You can read more here.), it’s easiest to temporarily convert arrays into lists while we compare them. We’ll turn them back into 2-D arrays once we’ve checked them against the rotated duplicate arrays in `check_list`

.

max_points = max([grid.sum() for grid in solutions]) filtered_solutions = [] for grid in solutions: if grid.sum() == max_points: check_list = [filtered_solutions.count(np.rot90(grid, 1).tolist()), filtered_solutions.count(np.rot90(grid, 2).tolist()), filtered_solutions.count(np.rot90(grid, 3).tolist())] if not any(check_list): filtered_solutions.append(grid.tolist()) filtered_solutions = [np.asarray(grid) for grid in filtered_solutions]

After *The Great Filter* we’re left with 4 (mostly) unique anti-isosceles grids! We’ve come a long way. The grid solutions should look like this:

[[1 1 0] [0 0 1] [0 0 1]] [[0 1 1] [0 0 0] [1 1 0]] [[1 1 0] [0 0 0] [0 1 1]] [[0 0 0] [1 0 1] [1 0 1]]

I say “mostly” unique because the second and third solutions are mirrors of one another. That might bother you or it might not. If you wanted to eliminate this possibility you could add cases to the `check_list`

filter above.

#### 4. Plot.

Console prints are okay but let’s plot these solutions using *Matplotlib*. The plot uses a custom *mplstyle* I created because I find the built-in dark styles somewhat lacking. A true black (#000000) like in *dark_background* is hard on the eyes. The style is included in the *Download* link at the bottom of this post.

Create a 2×2 subplot grid to display the 4 solutions. Subplot axes can be addressed like a 2-D *NumPy* array. Use `np.where`

to separate occupied coordinates from empty ones.

plt.style.use("wollen_dark.mplstyle") fig, axs = plt.subplots(2, 2, figsize=(7, 7)) fig.subplots_adjust(wspace=0.3, hspace=0.3, top=0.95, bottom=0.05, left=0.05, right=0.95) for ax, solution in zip(axs.flatten(), filtered_solutions): coords_y, coords_x = np.where(solution == 1) ax.scatter(coords_x, coords_y, s=400, color="#16AD2F") coords_y, coords_x = np.where(solution == 0) ax.scatter(coords_x, coords_y, s=400, color="#555555") ax.set_xticks(range(3), labels=[]) ax.set_yticks(range(3), labels=[]) ax.set_xlim([-0.14, 2.14]) ax.set_ylim([-0.14, 2.14]) plt.show()

The output:

Notice the upper-right solution is the same one pictured in the Riddler’s original example. But now we’ve written a script to find anti-isosceles sets ourselves! Pow!

I mentioned that there is a more efficient way to find all possible grid layouts. In the code above we used `itertools.permutations`

and then pared down the list by putting it into a `set`

. But another way to think about the problem is that, since all points are either 1 or 0, we’re working with binary sequences. Each of the 9 digits can be 0 or 1 so there are 2^{9}=512 possible grids. The sequences can be generated like this:

for n in range(2**9): sequence_str = f"{n:09b}" sequence = [int(c) for c in sequence_str] possible_layouts.append(sequence)

It’s as simple as counting to 512 in binary with leading zeroes.

**Full Code:**

import numpy as np from itertools import permutations, combinations from math import sqrt import matplotlib.pyplot as plt def get_distance(p1, p2): return sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) def check_if_anti_isosceles(triangles): is_anti_iso = True for tri in triangles: vertex1, vertex2, vertex3 = tri side_lengths = [get_distance(vertex1, vertex2), get_distance(vertex1, vertex3), get_distance(vertex2, vertex3)] if len(set(side_lengths)) == 2: is_anti_iso = False break return is_anti_iso possible_layouts = [] for dots in range(3, 10): well = [1] * dots + [0] * (9 - dots) perms = set(permutations(well, 9)) for layout in perms: possible_layouts.append(layout) solutions = [] for layout in possible_layouts: grid = np.array(layout) grid = grid.reshape((3, 3)) ones_y, ones_x = np.where(grid == 1) ones_coords = list(zip(ones_y, ones_x)) combs = list(combinations(ones_coords, 3)) is_anti_isosceles = check_if_anti_isosceles(combs) if is_anti_isosceles: solutions.append(grid) max_points = max([grid.sum() for grid in solutions]) filtered_solutions = [] for grid in solutions: if grid.sum() == max_points: check_list = [filtered_solutions.count(np.rot90(grid, 1).tolist()), filtered_solutions.count(np.rot90(grid, 2).tolist()), filtered_solutions.count(np.rot90(grid, 3).tolist())] if not any(check_list): filtered_solutions.append(grid.tolist()) filtered_solutions = [np.asarray(grid) for grid in filtered_solutions] plt.style.use("wollen_dark.mplstyle") fig, axs = plt.subplots(2, 2, figsize=(7, 7)) fig.subplots_adjust(wspace=0.3, hspace=0.3, top=0.95, bottom=0.05, left=0.05, right=0.95) for ax, solution in zip(axs.flatten(), filtered_solutions): coords_y, coords_x = np.where(solution == 1) ax.scatter(coords_x, coords_y, s=400, color="#16AD2F") coords_y, coords_x = np.where(solution == 0) ax.scatter(coords_x, coords_y, s=400, color="#555555") ax.set_xticks(range(3), labels=[]) ax.set_yticks(range(3), labels=[]) ax.set_xlim([-0.14, 2.14]) ax.set_ylim([-0.14, 2.14]) plt.show()