{"id":488,"date":"2021-06-04T07:00:57","date_gmt":"2021-06-04T12:00:57","guid":{"rendered":"https:\/\/wollen.org\/blog\/?p=488"},"modified":"2024-04-28T22:32:28","modified_gmt":"2024-04-29T03:32:28","slug":"battling-the-538-riddler","status":"publish","type":"post","link":"https:\/\/wollen.org\/blog\/2021\/06\/battling-the-538-riddler\/","title":{"rendered":"Battling the 538 Riddler"},"content":{"rendered":"

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

 <\/p>\n

\n

But this week, Jordan is asking about what he calls anti<\/em>-isosceles sets. Consider a N<\/em>\u00d7N<\/em> grid of points. What is the greatest subset of these N<\/em>2<\/sup> points such that no three of them<\/em> form an isosceles triangle? (Note: Degenerate triangles, or triangles with zero area, do<\/em> count as triangles here, as long as their three vertices are distinct.)<\/p>\n

As shown below, the largest anti-isosceles set in a 2\u00d72 grid has two points; for a 3\u00d73 grid, the largest anti-isosceles set has four points. (Note: For both grids, there are multiple sets with these maximum numbers of points.)<\/p>\n

\"\"<\/a><\/p>\n

[Source: FiveThirtyEight<\/a>]<\/p>\n<\/blockquote>\n

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.<\/p>\n

The general strategy will be:<\/p>\n

    \n
  1. Generate a list of all possible 3×3 grid “permutations.”<\/li>\n
  2. Within each grid, find all unique triangles and check if any are isosceles.<\/li>\n
  3. Filter out solutions that are a rotated copy of another.<\/li>\n
  4. Plot the solutions.<\/li>\n<\/ol>\n
    \n

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

    import numpy as np\r\nfrom itertools import permutations, combinations\r\nfrom math import sqrt\r\nimport matplotlib.pyplot as plt<\/pre>\n
    1. Find all possible 3×3 grids.<\/h4>\n
    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.<\/p>\n
    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<\/em> arrays.<\/p>\n
    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<\/code>. For example, in the first pass of the loop below, dots<\/code> will be 3. That will generate a well equal to:<\/p>\n
    [1, 1, 1, 0, 0, 0, 0, 0, 0]<\/pre>\n
    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<\/code>, which eliminates duplicates.<\/p>\n
    possible_layouts = []\r\n\r\nfor dots in range(3, 10):\r\n    well = [1] * dots + [0] * (9 - dots)\r\n    perms = set(permutations(well, 9))\r\n    for layout in perms:\r\n        possible_layouts.append(layout)<\/pre>\n
    Our possible_layouts<\/code> list contains 466 unique grids\u2014although 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?<\/p>\n
    [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.]<\/p>\n
    \n
    2. Find all unique triangles within each grid. Check if any are isosceles.<\/h4>\n
    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<\/code> loop near the bottom.<\/p>\n
    Each 1×9 list is reshaped into a 3×3 NumPy<\/em> array. For example:<\/p>\n
    [[1 0 1]\r\n [1 1 0]\r\n [0 0 1]]<\/pre>\n
    We use np.where(grid == 1)<\/code> to get coordinates of every occupied point within a grid. Then itertools.combinations<\/code> produces a list of all unique triangles among those points. The Riddler mentioned that we should<\/span> count degenerate triangles, which in non-Batman-villain lingo are just straight lines.<\/p>\n
    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()<\/code> goes to work. If none of the triangles is isosceles then we’ve found a solution to the Riddler’s challenge!<\/p>\n
    The check_if_anti_isosceles<\/code> function works by initially setting a flag to True<\/code>. 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<\/em>, 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<\/code>.<\/p>\n
    def get_distance(p1, p2):\r\n    return sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)\r\n\r\n\r\ndef check_if_anti_isosceles(triangles):\r\n    is_anti_iso = True\r\n    for tri in triangles:\r\n        vertex1, vertex2, vertex3 = tri\r\n        side_lengths = [get_distance(vertex1, vertex2),\r\n                        get_distance(vertex1, vertex3),\r\n                        get_distance(vertex2, vertex3)]\r\n        if len(set(side_lengths)) == 2:\r\n            is_anti_iso = False\r\n            break\r\n    return is_anti_iso\r\n\r\n\r\nsolutions = []\r\n\r\nfor layout in possible_layouts:\r\n    grid = np.array(layout)\r\n    grid = grid.reshape((3, 3))\r\n    ones_y, ones_x = np.where(grid == 1)\r\n    ones_coords = list(zip(ones_y, ones_x))\r\n    combs = list(combinations(ones_coords, 3))   # All possible triangles among the points.\r\n    is_anti_isosceles = check_if_anti_isosceles(combs)\r\n    if is_anti_isosceles:\r\n        solutions.append(grid)<\/pre>\n
    Grids that pass the test are appended to a solutions<\/code> 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.<\/p>\n
    \n
    3. Filter duplicate solutions.<\/h4>\n
    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.<\/p>\n
    Since NumPy<\/em> has built-in safeguards against ambiguous truth evaluations (I know that’s a mouthful. You can read more here<\/a>.), 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<\/code>.<\/p>\n
    max_points = max([grid.sum() for grid in solutions])\r\n\r\nfiltered_solutions = []\r\n\r\nfor grid in solutions:\r\n    if grid.sum() == max_points:\r\n        check_list = [filtered_solutions.count(np.rot90(grid, 1).tolist()),\r\n                      filtered_solutions.count(np.rot90(grid, 2).tolist()),\r\n                      filtered_solutions.count(np.rot90(grid, 3).tolist())]\r\n        if not any(check_list):\r\n            filtered_solutions.append(grid.tolist())\r\n\r\nfiltered_solutions = [np.asarray(grid) for grid in filtered_solutions]<\/pre>\n
    After The Great Filter<\/em> we’re left with 4 (mostly) unique anti-isosceles grids! We’ve come a long way. The grid solutions should look like this:<\/p>\n
    [[1 1 0]\r\n [0 0 1]\r\n [0 0 1]]\r\n\r\n[[0 1 1]\r\n [0 0 0]\r\n [1 1 0]]\r\n\r\n[[1 1 0]\r\n [0 0 0]\r\n [0 1 1]]\r\n\r\n[[0 0 0]\r\n [1 0 1]\r\n [1 0 1]]<\/pre>\n
    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<\/code> filter above.<\/p>\n
    \n
    4. Plot.<\/h4>\n
    Console prints are okay but let’s plot these solutions using Matplotlib<\/em>. The plot uses a custom mplstyle<\/em> I created because I find the built-in dark styles somewhat lacking. A true black (#000000) like in dark_background<\/em> is hard on the eyes. The style is included in the Download<\/em> link at the bottom of this post.<\/p>\n
    Create a 2×2 subplot grid to display the 4 solutions. Subplot axes can be addressed like a 2-D NumPy<\/em> array. Use np.where<\/code> to separate occupied coordinates from empty ones.<\/p>\n
    plt.style.use(\"wollen_dark.mplstyle\")\r\nfig, axs = plt.subplots(2, 2, figsize=(7, 7))\r\nfig.subplots_adjust(wspace=0.3, hspace=0.3,\r\n                    top=0.95, bottom=0.05, left=0.05, right=0.95)\r\n\r\nfor ax, solution in zip(axs.flatten(), filtered_solutions):\r\n\r\n    coords_y, coords_x = np.where(solution == 1)\r\n    ax.scatter(coords_x, coords_y, s=400, color=\"#16AD2F\")\r\n\r\n    coords_y, coords_x = np.where(solution == 0)\r\n    ax.scatter(coords_x, coords_y, s=400, color=\"#555555\")\r\n\r\n    ax.set_xticks(range(3), labels=[])\r\n    ax.set_yticks(range(3), labels=[])\r\n    ax.set_xlim([-0.14, 2.14])\r\n    ax.set_ylim([-0.14, 2.14])\r\n\r\nplt.show()<\/pre>\n
    The output:<\/p>\n
    \"\"<\/a><\/p>\n
    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!<\/p>\n
    \n
    I mentioned that there is a more efficient way to find all possible grid layouts. In the code above we used itertools.permutations<\/code> and then pared down the list by putting it into a set<\/code>. 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 29<\/sup>=512 possible grids. The sequences can be generated like this:<\/p>\n
    for n in range(2**9):\r\n    sequence_str = f\"{n:09b}\"\r\n    sequence = [int(c) for c in sequence_str]\r\n    possible_layouts.append(sequence)<\/pre>\n
    It’s as simple as counting to 512 in binary with leading zeroes.<\/p>\n
    \n
    Download the data<\/strong><\/a>.<\/p>\n
    Full Code:<\/strong><\/p>\n
    import numpy as np\r\nfrom itertools import permutations, combinations\r\nfrom math import sqrt\r\nimport matplotlib.pyplot as plt\r\n\r\n\r\ndef get_distance(p1, p2):\r\n    return sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)\r\n\r\n\r\ndef check_if_anti_isosceles(triangles):\r\n    is_anti_iso = True\r\n    for tri in triangles:\r\n        vertex1, vertex2, vertex3 = tri\r\n        side_lengths = [get_distance(vertex1, vertex2),\r\n                        get_distance(vertex1, vertex3),\r\n                        get_distance(vertex2, vertex3)]\r\n        if len(set(side_lengths)) == 2:\r\n            is_anti_iso = False\r\n            break\r\n    return is_anti_iso\r\n\r\n\r\npossible_layouts = []\r\n\r\nfor dots in range(3, 10):\r\n    well = [1] * dots + [0] * (9 - dots)\r\n    perms = set(permutations(well, 9))\r\n    for layout in perms:\r\n        possible_layouts.append(layout)\r\n\r\nsolutions = []\r\n\r\nfor layout in possible_layouts:\r\n    grid = np.array(layout)\r\n    grid = grid.reshape((3, 3))\r\n    ones_y, ones_x = np.where(grid == 1)\r\n    ones_coords = list(zip(ones_y, ones_x))\r\n    combs = list(combinations(ones_coords, 3))\r\n    is_anti_isosceles = check_if_anti_isosceles(combs)\r\n    if is_anti_isosceles:\r\n        solutions.append(grid)\r\n\r\nmax_points = max([grid.sum() for grid in solutions])\r\n\r\nfiltered_solutions = []\r\n\r\nfor grid in solutions:\r\n    if grid.sum() == max_points:\r\n        check_list = [filtered_solutions.count(np.rot90(grid, 1).tolist()),\r\n                      filtered_solutions.count(np.rot90(grid, 2).tolist()),\r\n                      filtered_solutions.count(np.rot90(grid, 3).tolist())]\r\n        if not any(check_list):\r\n            filtered_solutions.append(grid.tolist())\r\n\r\nfiltered_solutions = [np.asarray(grid) for grid in filtered_solutions]\r\n\r\nplt.style.use(\"wollen_dark.mplstyle\")\r\nfig, axs = plt.subplots(2, 2, figsize=(7, 7))\r\nfig.subplots_adjust(wspace=0.3, hspace=0.3, top=0.95, bottom=0.05, left=0.05, right=0.95)\r\n\r\nfor ax, solution in zip(axs.flatten(), filtered_solutions):\r\n\r\n    coords_y, coords_x = np.where(solution == 1)\r\n    ax.scatter(coords_x, coords_y, s=400, color=\"#16AD2F\")\r\n\r\n    coords_y, coords_x = np.where(solution == 0)\r\n    ax.scatter(coords_x, coords_y, s=400, color=\"#555555\")\r\n\r\n    ax.set_xticks(range(3), labels=[])\r\n    ax.set_yticks(range(3), labels=[])\r\n    ax.set_xlim([-0.14, 2.14])\r\n    ax.set_ylim([-0.14, 2.14])\r\n\r\nplt.show()<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    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<\/p>\n","protected":false},"author":1,"featured_media":737,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[40],"tags":[76,79,82,84,77,86,81,80,83,47,24,75,85,78,51],"class_list":["post-488","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-math","tag-76","tag-anti-isosceles","tag-array","tag-combination","tag-fivethirtyeight","tag-geometry","tag-grid","tag-isosceles","tag-itertools","tag-math","tag-matplotlib","tag-numpy","tag-permutation","tag-riddler","tag-triangle"],"_links":{"self":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts\/488","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/comments?post=488"}],"version-history":[{"count":35,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts\/488\/revisions"}],"predecessor-version":[{"id":1537,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/posts\/488\/revisions\/1537"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/media\/737"}],"wp:attachment":[{"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/media?parent=488"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/categories?post=488"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wollen.org\/blog\/wp-json\/wp\/v2\/tags?post=488"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}