AOJトライに関する知識知見の記録共有：DSL_1_A

タスク概要

Disjoint Set: Union Find Tree

コード実装例

TIPS

1. 例外処理含む評価パターンを追加

import pprint, sys, time

def core(args, adv=False):
    ret = []
    grps = "".join([str(i) for i in range(args[0])])
    for cmd, idx1, idx2 in args[1]:
        r = []
        if cmd == 0:
            if adv:
                grps = grps.replace(grps[idx1], grps[idx2])
            else:
                tmp = ""
                for i in range(len(grps)):
                    if grps[i] == grps[idx1]:
                        tmp = tmp + grps[idx2]
                    else:
                        tmp = tmp + grps[i]
                grps = tmp
        else:
            r = (grps[idx1] == grps[idx2]) * 1
        ret.append([r, [cmd, idx1, idx2], grps])
    return ret

def app(*args):
    ret = []
    for arg in args:
        s = []
        for adv in [True, False]:
            st = time.time()
            try:
                r = core(arg, adv=adv)
            except Exception as e:
                r = e
            s.append([adv, round(time.time() - st, 6), r])
        ret.append([arg, s])
    return ret

print(sys.version)
pprint.pprint(app(
    # basic examples
    [
        5,
        [
            [0, 1, 4],
            [0, 2, 3],
            [1, 1, 2],
            [1, 3, 4],
            [1, 1, 4],
            [1, 3, 2],
            [0, 1, 3],
            [1, 2, 4],
            [1, 3, 0],
            [0, 0, 4],
            [1, 0, 2],
            [1, 3, 0],
        ]
    ],
    # additional examples
    [
        9,
        [
            [0, 4, 1],
            [0, 3, 2],
            [1, 2, 1],
        ]
    ],
    # exceptional examples
    "例外入力"
))

実行結果

各種補足情報出力（入力値FB、デバッグログ等）含む

3.8.10
[GCC 9.3.0]
[[[5,
   [[0, 1, 4],
    [0, 2, 3],
    [1, 1, 2],
    [1, 3, 4],
    [1, 1, 4],
    [1, 3, 2],
    [0, 1, 3],
    [1, 2, 4],
    [1, 3, 0],
    [0, 0, 4],
    [1, 0, 2],
    [1, 3, 0]]],
  [[True,
    1.7e-05,
    [[[], [0, 1, 4], '04234'],
     [[], [0, 2, 3], '04334'],
     [0, [1, 1, 2], '04334'],
     [0, [1, 3, 4], '04334'],
     [1, [1, 1, 4], '04334'],
     [1, [1, 3, 2], '04334'],
     [[], [0, 1, 3], '03333'],
     [1, [1, 2, 4], '03333'],
     [0, [1, 3, 0], '03333'],
     [[], [0, 0, 4], '33333'],
     [1, [1, 0, 2], '33333'],
     [1, [1, 3, 0], '33333']]],
   [False,
    0.000112,
    [[[], [0, 1, 4], '04234'],
     [[], [0, 2, 3], '04334'],
     [0, [1, 1, 2], '04334'],
     [0, [1, 3, 4], '04334'],
     [1, [1, 1, 4], '04334'],
     [1, [1, 3, 2], '04334'],
     [[], [0, 1, 3], '03333'],
     [1, [1, 2, 4], '03333'],
     [0, [1, 3, 0], '03333'],
     [[], [0, 0, 4], '33333'],
     [1, [1, 0, 2], '33333'],
     [1, [1, 3, 0], '33333']]]]],
 [[9, [[0, 4, 1], [0, 3, 2], [1, 2, 1]]],
  [[True,
    1.2e-05,
    [[[], [0, 4, 1], '012315678'],
     [[], [0, 3, 2], '012215678'],
     [0, [1, 2, 1], '012215678']]],
   [False,
    1.2e-05,
    [[[], [0, 4, 1], '012315678'],
     [[], [0, 3, 2], '012215678'],
     [0, [1, 2, 1], '012215678']]]]],
 ['例外入力',
  [[True, 7e-06, TypeError("'str' object cannot be interpreted as an integer")],
   [False,
    3e-06,
    TypeError("'str' object cannot be interpreted as an integer")]]]]

補遺

残課題（Pull Request絶賛募集中！）

1. 実行速度の改善（枝刈り、データ構造の見直し等）
2. コア関数の汎用化