Pythonでポリゴンを初期状態にリセットするプログラムの実装方法

ここでは、n 個の頂点、n 本の反転軸(対称軸)、n 個の回転点を持つ多角形を考えます。反転軸と回転点については、以下の性質が成り立ちます。

• n が奇数の場合、各反転軸は1つの頂点と、その反対側の辺の中点を通ります。
• n が偶数の場合、半分の軸は向かい合う頂点同士を通り、残りの半分は向かい合う辺同士の中点を通ります。
• 隣り合う2つの軸がなす角度は 360/2n 度です。

問題の概要

この多角形に対して操作を行います。操作には n 種類の回転器があり、k-rotator は軸 k を基準にして多角形を時計回りに (360 × k)/n 度回転させます。

入力として、複数の整数ペアを含むリスト input_list が与えられます。各ペアの最初の整数は、多角形を「回転」するか「反転」するかを表します。値が 1 なら回転、2 なら反転です。2番目の整数は k を表し、反転の場合は軸 k で反転し、回転の場合はその値に応じた角度だけ回転します。リストが空になるまで、これらの回転と反転が順に適用されます。

この記事の課題は、リストに要素をもう1つ追加して、多角形を初期位置にリセットできるようにすることです。

上の図は、2種類の多角形における回転軸を示しています。

例えば、入力が n = 6、input_list = [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]] の場合、出力は (1, 4) になります。

これは、一連の変換を行った後、4番目の軸に沿って回転すると、多角形が初期位置に戻ることを意味します。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• decision_var := False(反転の有無を管理するフラグ)
• position := 0(現在の位置を表す変数)
• input_list 内の各要素について以下を処理します。
  • x := item[0](操作の種類)
  • y := item[1](操作の対象となる値)
  • x が 1 の場合:
    • position := position + y(回転なので位置を加算)
  • それ以外の場合:
    • position := y − position(反転なので位置を差分で更新)
    • decision_var := not(decision_var)(フラグを反転)
• position := position mod n(n で割った余りに正規化)
• decision_var が真(反転が奇数回)の場合:
  • ペア (2, position) を返す
• それ以外の場合:
  • ペア (1, n − position) を返す

ポイントは、回転操作は単純な加算で追跡できる一方、反転操作は位置の符号を入れ替える効果を持つため、y − position という形で更新し、さらに反転回数の偶奇をフラグで記録しておくことです。最後に偶奇によって、必要な追加操作が「回転」なのか「反転」なのかを判断します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(n, input_list):
    decision_var = False
    position = 0

    for item in input_list:
        x = item[0]
        y = item[1]
        if x == 1:
            position += y
        else:
            position = y - position
            decision_var = not decision_var

    position = position % n

    if decision_var:
        return (2, position)
    else:
        return (1, n - position)

print(solve(6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]))

入力

6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]

出力

(1, 4)

このように、全ての操作を線形時間 O(n) で処理しながら、多角形を初期状態へ戻すために必要な最後の操作を効率的に求めることができます。