{ "cells": [ { "cell_type": "markdown", "id": "63e2be2b", "metadata": {}, "source": [ "# [Anagramic Squares](https://projecteuler.net/problem=98)\n", "\n", "[Itertools](https://docs.python.org/3/library/itertools.html) to the rescue! But first, we'll read the words we're working with." ] }, { "cell_type": "code", "execution_count": 1, "id": "6db8ba5d", "metadata": {}, "outputs": [], "source": [ "with open(\"txt/0098_words.txt\") as f:\n", " words = [word.strip('\"') for line in f for word in line.split(',')]" ] }, { "cell_type": "markdown", "id": "a2171d35", "metadata": {}, "source": [ "We can then make groups where each word is an anagram of the other words in the group." ] }, { "cell_type": "code", "execution_count": 2, "id": "10a18f2f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[('BOARD', 'BROAD'),\n", " ('CREATION', 'REACTION'),\n", " ('CARE', 'RACE'),\n", " ('ACT', 'CAT'),\n", " ('DANGER', 'GARDEN'),\n", " ('DEAL', 'LEAD'),\n", " ('PHASE', 'SHAPE'),\n", " ('EARTH', 'HEART'),\n", " ('HATE', 'HEAT'),\n", " ('ARISE', 'RAISE'),\n", " ('MALE', 'MEAL'),\n", " ('LEAST', 'STEAL'),\n", " ('MEAN', 'NAME'),\n", " ('EARN', 'NEAR'),\n", " ('RATE', 'TEAR'),\n", " ('EAST', 'SEAT'),\n", " ('EAT', 'TEA'),\n", " ('INTRODUCE', 'REDUCTION'),\n", " ('CREDIT', 'DIRECT'),\n", " ('CENTRE', 'RECENT'),\n", " ('EXCEPT', 'EXPECT'),\n", " ('COURSE', 'SOURCE'),\n", " ('DOG', 'GOD'),\n", " ('SHEET', 'THESE'),\n", " ('FILE', 'LIFE'),\n", " ('FORMER', 'REFORM'),\n", " ('IGNORE', 'REGION'),\n", " ('ITEM', 'TIME'),\n", " ('QUIET', 'QUITE'),\n", " ('NOTE', 'TONE'),\n", " ('SURE', 'USER'),\n", " ('FORM', 'FROM'),\n", " ('NIGHT', 'THING'),\n", " ('SIGN', 'SING'),\n", " ('THROW', 'WORTH'),\n", " ('SHOUT', 'SOUTH'),\n", " ('HOW', 'WHO'),\n", " ('SHUT', 'THUS'),\n", " ('ITS', 'SIT'),\n", " ('NO', 'ON'),\n", " ('NOW', 'OWN'),\n", " ('POST', 'SPOT', 'STOP')]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from itertools import groupby\n", "\n", "anagram_groups = []\n", "for _, g in groupby(sorted(words, key=sorted), key=sorted):\n", " g = tuple(g)\n", " if len(g) > 1:\n", " anagram_groups.append(g)\n", "\n", "anagram_groups" ] }, { "cell_type": "markdown", "id": "2ff00e54", "metadata": {}, "source": [ "When looking for square mappings, we only need to consider square numbers with the same number of digits as a given word. This means if word has $n$ characters, we'll only try to map squares between $10^{n-1}$ and $10^n$. Here's a function to iterate over all square numbers with a given number of digits." ] }, { "cell_type": "code", "execution_count": 3, "id": "aaf851bb", "metadata": {}, "outputs": [], "source": [ "def n_digit_square_numbers(n):\n", " low = ceil(sqrt(10^(n-1)))\n", " high = floor(sqrt(10^n - 1))\n", " for k in range(low, high + 1):\n", " yield k^2" ] }, { "cell_type": "markdown", "id": "53dc4e29", "metadata": {}, "source": [ "Next, a function to generate those mappings. Per the problem, we'll only consider mappings that map distinct characters to distinct digits (i.e. [injective mappings](https://en.wikipedia.org/wiki/Injective_function))." ] }, { "cell_type": "code", "execution_count": 4, "id": "5e4db377", "metadata": {}, "outputs": [], "source": [ "def square_mappings(word):\n", " n = len(word)\n", " for k in n_digit_square_numbers(n):\n", " tr = dict(zip(word, str(k)))\n", " if len(set(tr.values())) != len(tr):\n", " continue\n", " \n", " yield str.maketrans(tr)" ] }, { "cell_type": "markdown", "id": "b3410bb2", "metadata": {}, "source": [ "Then, given two anagrams, we'll determine if they are a square anagram word pair by generating square mappings for one word, and checking if any of those mappings also result in a square number for the other word. If there are multiple such mappings, we'll return the one that makes the largest square number." ] }, { "cell_type": "code", "execution_count": 5, "id": "744be254", "metadata": {}, "outputs": [], "source": [ "def square_anagram_word_pair_mapping(s, t):\n", " best = None\n", " maximum = float('-inf')\n", " \n", " for tr in square_mappings(s):\n", " m, n = s.translate(tr), t.translate(tr)\n", " if m[0] == '0' or n[0] == '0':\n", " continue\n", "\n", " m, n = int(m), int(n)\n", " if is_square(m) and is_square(n) and maximum < max(m, n):\n", " maximum = max(m, n)\n", " best = tr\n", " \n", " return best" ] }, { "cell_type": "markdown", "id": "408ad5a3", "metadata": {}, "source": [ "Now we'll look at every anagram pair and find their best square mapping, if it exists." ] }, { "cell_type": "code", "execution_count": 6, "id": "1ea2a13b", "metadata": {}, "outputs": [], "source": [ "from itertools import combinations\n", "\n", "pairs = dict()\n", "for group in anagram_groups:\n", " for s, t in combinations(group, 2):\n", " pairs[(s, t)] = square_anagram_word_pair_mapping(s, t)" ] }, { "cell_type": "markdown", "id": "d16f4f48", "metadata": {}, "source": [ "With the best mappings, we can find the largest square that can be made from each pair." ] }, { "cell_type": "code", "execution_count": 7, "id": "f064e9e4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{('BOARD', 'BROAD'): 18769,\n", " ('CARE', 'RACE'): 9216,\n", " ('DEAL', 'LEAD'): 4761,\n", " ('HATE', 'HEAT'): 1936,\n", " ('MALE', 'MEAL'): 1936,\n", " ('MEAN', 'NAME'): 9604,\n", " ('RATE', 'TEAR'): 9604,\n", " ('EAST', 'SEAT'): 2916,\n", " ('EAT', 'TEA'): 961,\n", " ('DOG', 'GOD'): 961,\n", " ('FILE', 'LIFE'): 9216,\n", " ('NOTE', 'TONE'): 9216,\n", " ('HOW', 'WHO'): 961,\n", " ('SHUT', 'THUS'): 4761,\n", " ('ITS', 'SIT'): 961,\n", " ('NOW', 'OWN'): 961,\n", " ('POST', 'SPOT'): 2916,\n", " ('POST', 'STOP'): 9604}" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max_squares = {(s, t): max(int(s.translate(tr)), int(t.translate(tr))) for ((s, t), tr) in pairs.items() if tr is not None}\n", "max_squares" ] }, { "cell_type": "code", "execution_count": 8, "id": "00be066e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "18769" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "max(max_squares.values())" ] }, { "cell_type": "markdown", "id": "69a1b066", "metadata": {}, "source": [ "#### Copyright (C) 2025 filifa\n", "\n", "This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)." ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.2" } }, "nbformat": 4, "nbformat_minor": 5 }