Problem 98: アナグラム平方数

9718 ワード
ProjectEuler Python 平方数 アルゴリズム Python テキストリンク
  • 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 98. アナグラム平方数

原文 Problem 98: Anagramic squares

問題の要約：ファイルから読んだ英単語の文字を数字に変換したときに平方数になる場合。元の単語のアナグラムを同じ規則で数字で変換したものも平方数になるような最大の平方数を求めよ

問題の文章が分かりづらいですが、以下の例のようにCAREとRACEを同じ規則(C-1,A-2,R-9,E-6)で数字に変換すると、どちらも平方数になるのでこれが「アナグラム平方数単語ペア」ということになります。このときの平方数の大きい方の最大値を求めよという問題になのでこの例の場合は$9216$が答えになります。

元の英単語 変換した平方数 英単語のアナグラム 同じ規則で変換
CARE $1296=36^2$ RACE $9216=96^2$

以下のステップで考えます。いつものようにファイルから読み込む部分は最後に添付しました。

  1. 与えられた単語の中からアナグラムになっているペアを探す
  2. 平方数を長さごとにリストしておく
  3. str.makestansを使って単語を平方数に変換して、同じルールでペアの単語も平方数になるものを探す。このとき逆変換をして元に戻ることを確認して1対1のものに限る。

アナグラムになっているペアの単語を探す

isAnaPairで2つの英単語がアナグラムがどうかチェックしています。単純にCounterの結果を比較するだけです。

from itertools import combinations
from collections import Counter

def isAnaPair(s1, s2):
  return len(s1) == len(s2) and Counter(s1)== Counter(s2)   

# words : list of words read from the file
apairList = [[len(w1),w1,w2] for w1, w2 in combinations(words,2) if isAnaPair(w1,w2) ]
print(len(apairList), apairList)
# 44 [[3, 'ACT', 'CAT'], [5, 'ARISE', 'RAISE'], [5, 'BOARD', 'BROAD'], .....

平方数を桁の長さごとにリスト

後で利用しやすいように平方数を桁の長さごとにリストします。

sqnum = [[] for i in range(15)]
for n in range(2,10**5):
  sqstr = str(n**2)
  sqnum[len(sqstr)].append(sqstr)

ペアの単語が同じルールに平方数に変換できるチェック

str.makestansを使って単語を平方数に変換します。　ペアの両方とも平方数に変換出来たら逆変換をして1対1になっているかをチェックします。

maxsq = 0
for wpair in apairList:    # all anagmamic pairs
  wlen = wpair[0]          # word length
  for ns1 in sqnum[wlen]:
    ns2 = wpair[2].translate(str.maketrans(wpair[1],ns1))   # tranlate w2 to n2 with w1-ns1 rule
    if ns2 in sqnum[wlen]:
      w2 = ns2.translate(str.maketrans(ns1,wpair[1]))       # translate ns2 back to w2 to confirm 1-to-1 relation
      if w2 == wpair[2]:    
        msq = max(int(ns1),int(ns2))
        if msq > maxsq: 
          maxsq, mwpair = msq, wpair
        break  

print(f"Answer: {maxsq}, ({mwpair})")

(添付) ファイルから読み込んで英単語のリストを作る

# show upload dialog
from google.colab import files
uploaded = files.upload()
f = open("p098_words.txt")
words = f.read()
f.close()
words = words.replace('"','').split(",")

（開発環境：Google Colab）