お店の空き時間をビット演算の論理和で算出する

こちらはバイセルテクノロジーズ Advent Calendar 2021 の17日目の記事です。前日の記事は赤川さんの「Smart Proxy Managerを用いたクローラー実行時のアクセス遮断への対策」でした。

こんにちは、テクノロジー戦略本部開発2部の藤本です。

新しく始まったリユースプラットフォームプロジェクトのあるチームでPLをやっております。そちらがメインで最近はあまり実装に参加できていないのですが、少し前にお店の空き時間をビット演算の論理和を使って算出する実装を行い、個人的に面白いと思ったので紹介します。

バイセルの店舗買取について

バイセルでは買取の方法として出張訪問買取・店舗持込買取・宅配買取の3つがあり、店舗持込買取は比較的最近始まったものです。お客様に商品を店舗まで持ち込んでいただき、その場で査定・買取をさせていただきます。いまは5店舗ほど展開しております。

お店でもWeb予約をしたい

弊社の出張訪問買取はWebからも予約できるのですが、お店の予約は弊社コールセンターに電話する方法のみでした。そこで、お店もWeb予約できるようにしたいという要望が上がりました。具体的な要望をまとめると以下のとおりです。

各店舗毎に翌日〜2週間後までの空き時間がわかるようにしたい
1時間枠（9:00-10:00など）で空き時間が表示されるようにしてほしい
1時間枠に少しでも予定が入っているときは、空き時間として表示しないでほしい

実装方法検討

まずは実装方法のイメージを考えました。以下の図のように、店舗スタッフの一人でも1時間枠に空きがあったらそこを空き時間として算出する感じです。白枠の予定と、各スタッフの稼働時間（シフトの情報）はすでにDB上にテーブルとして存在するのですが、それぞれデータ型が異なるため、同じものに変換して計算しやすくすれば実装できそうと考えました。

（店舗のシフトのイメージ図）

ここから実装に落とし込む具体的な方法を検討しました。ちなみにこのシステムのバックエンドはRailsが使われているため、言語はRubyです。

1.RubyのRange型を利用

RubyにはRangeというデータ型があり、範囲を表すオブジェクトとして利用できます。それぞれの予定をRangeに置き換えればできそうと思ったのですが、複数のRangeオブジェクト同士で計算をすることができなさそうでしたので、こちらの利用は諦めました。

2.ビット演算の論理和を利用

上記の図の白枠の予定と各スタッフの稼働時間をすべてビット文字列に変換することでデータ型を統一し、さらにそれらの論理和をとれば、うまい具合に空き時間が算出できそうなので、この方法を採用しました。例えば、ある日に10:00-20:00で稼働してすでに予定が10:00-12:00と13:00-15:00に入っている場合は以下のような感じになります。1が予定ありで、0が予定なしです。

時間 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23
稼働 1  1  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  1  1  1 
予定 0  0  0  0  0  0  0  0  0  0  1  1  0  1  1  0  0  0  0  0  0  0  0  0
空き 1  1  1  1  1  1  1  1  1  1  1  1  0  1  1  0  0  0  0  0  0  1  1  1

具体的な実装

1.店舗スタッフの予定を取得

各店舗のスタッフの稼働時間と予定はすでにデータベースに保存されています。指定の店舗・日時のそれぞれのデータを取得します。（以下のデータはサンプルで、実際のデータとは異なります。）

# 稼働時間
[#<Schedule:0x00005589948ea198
  id: 1,
  staff_id: 2,
  store: "有楽町店",
  start: Tue, 14 Dec 2021 10:30:00 JST +09:00,
  end: Tue, 14 Dec 2021 19:00:00 JST +09:00]

# 予定
[#<Plan:0x00005589948e9978
  id: 1,
  staff_id: 2,
  start: Tue, 14 Dec 2021 11:00:00 JST +09:00,
  end: Tue, 14 Dec 2021 12:00:00 JST +09:00>,
 #<Plan:0x00005589948e9478
  id: 2,
  staff_id: 2,
  start: Tue, 14 Dec 2021 15:00:00 JST +09:00,
  end: Tue, 14 Dec 2021 17:00:00 JST +09:00]

2.各データをビット文字列に変換

1で取得した勤務日のスケジュールと店舗スタッフの稼働日をすべて0,1のビットの文字列に変換します。それぞれのデータを以下のコードに渡して0,1のビットに変換するイメージです。

def build_time_bits
  duration = @start_time.beginning_of_day
  # 24時間分のiterationをしたいので、1日を1時間で等分した範囲オブジェクトを作る
  range = Range.new(1, 1.day / @time_span)

  range.inject('') do |bits, _|
    bits += if @start_time <= duration && duration < @end_time
              @occupied_bit
            else
              @free_bit
            end

    duration += @time_span
    bits
  end
end

これによって以下のようなビット文字列の配列を取得します。

@time_bits = [
  "111111111110000000011111", # 稼働時間
  "000000000001000000000000", # 予定1
  "000000000000000110000000"  # 予定2
]

3.論理和を用いて空き時間ビットを計算

論理和によって稼働時間と予定のどちらかが1だったら1、どちらも0なら0にします

def get_free_time_bits
  @time_bits.inject('') do |result, bit|
    next result = bit if result.empty?

    (result.to_i(2) | bit.to_i(2)).to_s(2)
  end
end
# -> "111111111111000110011111"

4.空き時間ビットを日時に戻し、フロントに返却

3のビットを日時に戻します

def convert_bits_to_times(free_time_bits)
  free_time_bits.each_char.each_with_object([]) do |bit, result|
    result << { start: @day, end: @day + @time_span } if bit.include?('0')
    @day += @time_span
  end
end

日時戻すと以下のようになりますので、それをフロントに返却します

[{:start=>Tue, 14 Dec 2021 12:00:00 JST +09:00, :end=>Tue, 14 Dec 2021 13:00:00 JST +09:00},
 {:start=>Tue, 14 Dec 2021 13:00:00 JST +09:00, :end=>Tue, 14 Dec 2021 14:00:00 JST +09:00},
 {:start=>Tue, 14 Dec 2021 14:00:00 JST +09:00, :end=>Tue, 14 Dec 2021 15:00:00 JST +09:00},
 {:start=>Tue, 14 Dec 2021 17:00:00 JST +09:00, :end=>Tue, 14 Dec 2021 18:00:00 JST +09:00},
 {:start=>Tue, 14 Dec 2021 18:00:00 JST +09:00, :end=>Tue, 14 Dec 2021 19:00:00 JST +09:00}]