読者です 読者をやめる 読者になる 読者になる

時間帯重複チェックのお題を解いてみた

python algorithm

ある二つの時間帯(日をまたがない)が重複しているかどうかをチェックする処理を書いて下さい。
時間帯は4つの整数値(開始時,開始分,終了時,終了分)により与えられます。

例1) 午前1時から午前5時30分まで
(1, 0, 5, 30)

例2) 午前9時から午後23時まで
(9, 0, 23, 0)

時は0から24まで、分は0から59まで(ただし時が24の場合は0のみ)を採りますので、これ以外が与えられた場合は適切なエラー処理を行って下さい。
開始時間よりも終了時間のほうが早かった場合は適切なエラー処理を行って下さい。(同一時刻はOKとします)

ここで「重複している」とは二つの時間帯が共有している時間が1分以上ある状態と定義します。
ですので、(1, 0, 2, 0) と (2, 0, 3, 0) は 2時00分がかぶっていますが、同一時刻のため重複はしていません。
もし、(1, 0, 2, 0) と (1, 59, 3, 0) であれば1時59分から2時の1分間がかぶっていますので重複しています。

<チェック例>
timeDuplicationCheck( (1, 0, 5, 30), (9, 0, 23, 0) ) // => false (重複なし)
timeDuplicationCheck( (1, 0, 2, 0), (2, 0, 3, 0) ) // => false (重複なし)
timeDeplicationCheck( (1, 0, 2, 1), (1, 59, 3, 0) ) // => true (重複あり)

お題:時間帯重複チェック - No Programming, No Life

入力値が時間(時, 分)かどうかのエラーチェックは datetime.time で変換してみたら良いんじゃ?と考えたところから始めました。が、しかし、datetime.time は (24, 0) の入力を扱えませんでした。がーん、、、

>>> import datetime
>>> datetime.time(24, 0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: hour must be in 0..23

お仕事だったら、ユーザへお願いして入力は (23, 59) までで勘弁してくださいと何とかお願いして仕様を変えてもらうことから始めます。とはいえ、別システムとの兼ね合いで (24, 0) の入力が重要な意味を持つのかもしれませんし、そのぐらい簡単にできるだろうと上司のマネージャに取りつく島もないかもしれません。実装するのが難しいのではなくて、せっかく用意されているライブラリがあるのに、自分で実装するコードが増えるとそれだけバグが混入する可能性やメンテナンスのコストも高くなるから言ってるのになぁ、、、と愚痴をこぼしながら、仕方なくやることにしました。

う〜ん、う〜ん、どうしようかなぁ。取りあえず (24, 0) の入力値は後で考えよう。

def convert_time(hour, minute):
    """
    >>> convert_time(9, 30)
    datetime.time(9, 30)
    >>> convert_time(24, 0)
    datetime.time(23, 59)
    """
    import datetime
    try:
        return datetime.time(hour, minute)
    except ValueError as err:
        if hour == 24 and minute == 0:
            return datetime.time(23, 59)
        else:
            raise ValueError("{0}, time is {1}:{2}".format(
                                err.message, hour, minute))

(24, 0) は入力できるけれど、内部で勝手に (23, 59) に置き換えています。入力値の時間(時, 分)のエラーチェックはできたことにして次に進んでみます。開始時刻と終了時刻を表す数値のタプルから、datetime.time 型に変換してリストで持ちます。この要件では、数値のままでも比較できそうな気もしますが、今後の拡張性もちょっと考慮して datetime.time 型にしておきましょう。

def convert_start_end_time_data(time_range):
    """
    >>> convert_start_end_time_data((9, 30, 11, 0))
    [datetime.time(9, 30), datetime.time(11, 0)]
    """
    _ct = convert_time  # just for alias
    t = [_ct(*time_range[i:i + 2]) for i in range(0, len(time_range), 2)]
    if t[0] > t[1]:
        raise ValueError("start time {0} must be earlier than "
                         "end time {1}".format(*t))
    return t

要件には、時間の範囲を2つ受け取ることしか書いてありません。実装のコストを考えたら、入力を2つ受け取るのもそれ以上受け取るのもあまり大差ありません。どうせ後になって入力は5つになったとか言ってくるんだろう、、、後になってやり直すのも面倒なので、今のうちに2つ以上の入力も想定して実装しておこう。開始時刻でソートすることで、

n 番目の終了時刻 > n + 1 番目の開始時刻

を満たすときが「重複有り」でシンプルにチェックできます。

def is_duplicated_time(*time_range):
    """
    >>> is_duplicated_time((1, 0, 5, 30), (9, 0, 23, 0))
    False
    >>> is_duplicated_time((2, 0, 3, 0), (1, 0, 2, 0))
    False
    >>> is_duplicated_time((1, 0, 2, 1), (1, 59, 3, 0))
    True
    >>> is_duplicated_time((3, 30, 5, 0), (5, 30, 6, 0), (1, 0, 3, 30))
    False
    >>> is_duplicated_time((3, 30, 5, 0), (5, 30, 6, 0), (1, 0, 3, 31))
    True
    >>> is_duplicated_time((9, 30, 9, 40), (8, 20, 7, 0))
    start time 08:20:00 must be earlier than end time 07:00:00
    >>> is_duplicated_time((1, 0, 2, 1), (24, 59, 3, 0))
    hour must be in 0..23, time is 24:59
    """
    try:
        t = map(convert_start_end_time_data, time_range)
        t.sort(lambda x, y: cmp(x[0], y[0]))
    except Exception as err:
        print err.message
        # error handling
        return

    # duplication check
    ret = False
    for i in range(len(t[:-1])):
        if t[i][1] > t[i + 1][0]:
            ret = True
            break

    return ret

うん。思った通り、シンプルに実装できて良さそうな感じです。さぁ、テストしようかな。

はっ、、、(24, 0) の入力値はどうすんだ!?

分かった、分かった、それ用に特別処理を書いたら良いよね。

def is_duplicated_time_in_24_0(time_range):
    def _get_time_24_0_position(time_range):
        pos = []
        t = sorted(time_range, lambda x, y: cmp(x[0:2], y[0:2]))
        for num, i in enumerate(t):
            if i[0:2] == (24, 0):
                pos.append((num, 0))
            elif i[2:4] == (24, 0):
                pos.append((num, 1))
        return pos, t

    def _is_duplicated_time_in_24_0(sorted_time_range, pos):
        for i, j in pos:
            if j == 1:
                if i < len(sorted_time_range):
                    if sorted_time_range[i + 1][0:2] == (23, 59):
                        return True
            else:
                raise NotImplementedError("gomen-nasai")
        return False

    ret = False
    pos, sorted_time_range = _get_time_24_0_position(time_range)
    if pos:
        ret = _is_duplicated_time_in_24_0(sorted_time_range, pos)
    return ret

えぇー、、、こんな滅多に使われないような特別処理がとんどもないことになってしまいました。それまでシンプルに実装してきたのに、それを台無しにするようなコードが追加されました。さらに不完全実装ー(> <)

...
                raise NotImplementedError("gomen-nasai")

入力として受け取る時間の範囲が2つだけなら、(24, 0) が含まれるときの重複判定結果に影響を与えるパターンが限定されるのでもっとシンプルなチェックだけで済んだかもしれません。時間の範囲の入力を可変にしたことで、考慮するパターンが増えて、特別処理が煩雑になってしまいました。

独自の MyTime クラスを定義しても良いのでしょうが、それだとせっかくライブラリがあるというメリットを生かせないし、MyTime クラスをちゃんと実装できる自信もない。

それなら datetime.time をやめて内部的には datetime.datetime で日付をもって管理してみよう。(24, 0) は翌日の (0, 0) だよね。そうすると、最初の convert_time の処理は次のようになります。

def convert_time(hour, minute):
    """
    >>> convert_time(9, 30)
    datetime.datetime(2011, 3, 1, 9, 30)
    >>> convert_time(24, 0)
    datetime.datetime(2011, 3, 2, 0, 0)
    """
    from datetime import datetime
    _dummy_year=2011
    _dummy_month=3
    _dummy_day=1
    try:
        return datetime(_dummy_year, _dummy_month, _dummy_day, hour, minute)
    except ValueError as err:
        if hour == 24 and minute == 0:
            return datetime(_dummy_year, _dummy_month, _dummy_day + 1, 0, 0)
        else:
            raise ValueError("{0}, time is {1}:{2}".format(
                                err.message, hour, minute))

エラー出力をちょっと修正して、ユーザには日付を意識させないようにします。最終的な実装はこんな感じになりました。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def convert_time(hour, minute):
    """
    >>> convert_time(9, 30)
    datetime.datetime(2011, 3, 1, 9, 30)
    >>> convert_time(24, 0)
    datetime.datetime(2011, 3, 2, 0, 0)
    """
    from datetime import datetime
    _dummy_year=2011
    _dummy_month=3
    _dummy_day=1
    try:
        return datetime(_dummy_year, _dummy_month, _dummy_day, hour, minute)
    except ValueError as err:
        if hour == 24 and minute == 0:
            return datetime(_dummy_year, _dummy_month, _dummy_day + 1, 0, 0)
        else:
            raise ValueError("{0}, time is {1}:{2}".format(
                                err.message, hour, minute))

def convert_start_end_time_data(time_range):
    """
    >>> convert_start_end_time_data((9, 30, 11, 0))
    [datetime.datetime(2011, 3, 1, 9, 30), datetime.datetime(2011, 3, 1, 11, 0)]
    """
    _ct = convert_time  # just for alias
    t = [_ct(*time_range[i:i + 2]) for i in range(0, len(time_range), 2)]
    if t[0] > t[1]:
        s = str(t[0])[11:]
        e = str(t[1])[11:]
        if t[0].day > t[1].day:
            s = "24:00:00"
        raise ValueError("start time {0} must be earlier than "
                         "end time {1}".format(s, e))
    return t

def is_duplicated_time(*time_range):
    """
    >>> is_duplicated_time((1, 0, 5, 30), (9, 0, 23, 0))
    False
    >>> is_duplicated_time((2, 0, 3, 0), (1, 0, 2, 0))
    False
    >>> is_duplicated_time((1, 0, 2, 1), (1, 59, 3, 0))
    True
    >>> is_duplicated_time((3, 30, 5, 0), (5, 30, 6, 0), (1, 0, 3, 30))
    False
    >>> is_duplicated_time((3, 30, 5, 0), (5, 30, 6, 0), (1, 0, 3, 31))
    True
    >>> is_duplicated_time((9, 30, 9, 40), (8, 20, 7, 0))
    start time 08:20:00 must be earlier than end time 07:00:00
    >>> is_duplicated_time((1, 0, 2, 1), (24, 59, 3, 0))
    hour must be in 0..23, time is 24:59
    >>> is_duplicated_time((1, 0, 2, 0), (23, 59, 23, 59), (23, 0, 24, 0))
    True
    >>> is_duplicated_time((24, 0, 23, 59), (23, 59, 23, 59))
    start time 24:00:00 must be earlier than end time 23:59:00
    """
    try:
        t = map(convert_start_end_time_data, time_range)
        t.sort(lambda x, y: cmp(x[0], y[0]))
    except Exception as err:
        print err.message
        # error handling
        return

    # duplication check
    ret = False
    for i in range(len(t[:-1])):
        if t[i][1] > t[i + 1][0]:
            ret = True
            break
    return ret

さっきの訳の分からない特別処理を書くよりはましかなぁ。

広告を非表示にする