如何检查循环范围的重叠（每年重叠的周期）
How to check for overlap of cyclic ranges (overlapping yearly recurring periods)
我正在尝试寻找一种优雅的算法来检查两个年度重复周期是否重叠。该期间与年份无关，但可以预期年份始终是闰年。
例如，时间段 A =（3 月 1 日至 5 月 1 日）和时间段 B =（4 月 1 日至 9 月 1 日）重叠。
此外，期间 A =（10 月 1 日至 2 月 1 日）和期间 B =（1 月 1 日至 3 月 1 日）重叠。
然而，我发现这比我预期的要难。复杂性来自于跨越年末的时期。
我有一个可行的解决方案（请参阅下面的 doesOverlap(A,B) 方法），但我发现它令人困惑。
# for the rest of the MWE context code, see further
# WORKING, but a bit convulted
def doesOverlap(A, B):
'''returns True if yearly period A and B have overlapping dates'''
# list to track if day in year is part of a period A
# (this could probably be done a bit cheaper with a dictionary of tuples, but not relevant for my question)
yeardayCovered = [False for x in range(366)] # leap year
# mark the days of A
for d in range(A.start, A.start + A.length):
yeardayCovered[d % 366] = True
# now check each of the days in B with A
for d in range(B.start, B.start + B.length):
if yeardayCovered[d % 366]:
return True
return False
我相信应该可以用更少的检查和更优雅的方式来做到这一点。我尝试将其中一个开始日期设置为零偏移量，应用一些模运算符，然后进行常规（非循环）范围重叠检查（Algorithm to detect overlapping periods）。但我还没有得到它适用于我所有的测试用例。
#NOT WORKING CORRECTLY!!
def doesOverlap(A, B):
'''determines if two yearly periods have overlapping dates'''
Astart = A.start
Astop = A.stop
Bstart = B.start
Bstop = B.stop
# start day counting at Astart, at 0
offset = Astart
Astart = 0
Astop = (Astop - offset) % 366
Bstart = (Bstart - offset) % 366
Bstop = (Bstop - offset) % 366
# overlap?
#
return (Astart <= Bstop and Bstart <= Astop)
注意：我已经完成了 Python 中的代码，但理想情况下，解决方案不应过于 Python 具体（即不使用通常只是开箱即用的功能在 Python 中可用，但在 C 或 C# 中不可用）
# MWE (Minimal Working Example)
import datetime
import unittest
class TimePeriod:
def __init__(self, startDay, startMonth, stopDay, stopMonth):
self.startDay = startDay
self.startMonth = startMonth
self.stopDay = stopDay
self.stopMonth = stopMonth
def __repr__(self):
return "From " + str(self.startDay) + "/" + str(self.startMonth) + " to " + \
str(self.stopDay) + "/" + str(self.stopMonth)
def _dayOfYear(self, d, m, y=2012):
'''2012 = leap year'''
date1 = datetime.date(year=y, day=d, month=m)
return date1.timetuple().tm_yday
@property
def start(self):
'''day of year of start of period, zero-based for easier modulo operations! '''
return self._dayOfYear(self.startDay, self.startMonth) - 1
@property
def stop(self):
'''day of year of stop of period, zero-based for easier modulo operations! '''
return self._dayOfYear(self.stopDay, self.stopMonth) - 1
@property
def length(self):
'''number of days in the time period'''
_length = (self.stop - self.start) % 366 + 1
return _length
def doesOverlap(A, B):
# code from above goes here
class TestPeriods(unittest.TestCase):
pass
def test_generator(a, b, c):
def test(self):
self.assertEqual(doesOverlap(a, b), c)
return test
if __name__ == '__main__':
#some unit tests, probably not complete coverage of all edge cases though
tests = [["max", TimePeriod(1, 1, 31, 12), TimePeriod(1, 1, 1, 1), True],
["BinA", TimePeriod(1, 3, 1, 11), TimePeriod(1, 5, 1, 10), True],
["BoverEndA", TimePeriod(1, 1, 1, 2), TimePeriod(10, 1, 3, 3), True],
["BafterA", TimePeriod(1, 1, 1, 2), TimePeriod(2, 2, 3, 3), False],
["sBoutA", TimePeriod(1, 12, 2, 5), TimePeriod(1, 6, 1, 7), False],
["sBoverBeginA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 10, 1, 12), True],
["sBinA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 1, 1, 2), True],
["sBinA2", TimePeriod(1, 11, 2, 5), TimePeriod(1, 12, 10, 12), True],
["sBinA3", TimePeriod(1, 11, 2, 5), TimePeriod(1, 12, 1, 2), True],
["sBoverBeginA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 10, 1, 12), True],
["Leap", TimePeriod(29, 2, 1, 4), TimePeriod(1, 10, 1, 12), False],
["BtouchEndA", TimePeriod(1, 2, 1, 2), TimePeriod(1, 2, 1, 3), True]]
for i, t in enumerate(tests):
test_name = 'test_%s' % t[0]
test = test_generator(t[1], t[2], t[3])
setattr(TestPeriods, test_name, test)
# unittest.main()
suite = unittest.TestLoader().loadTestsFromTestCase(TestPeriods)
unittest.TextTestRunner(verbosity=2).run(suite)
您可以将跨年末的时间段分成两部分，然后将两者进行比较。这将导致不需要任何 Python 特定功能的非常简单的递归函数：
def overlap(start_a, stop_a, start_b, stop_b):
if start_a > stop_a:
return overlap(start_a, 365, start_b, stop_b) or overlap(0, stop_a, start_b, stop_b)
elif start_b > stop_b:
return overlap(start_a, stop_a, start_b, 365) or overlap(start_a, stop_a, 0, stop_b)
else:
return start_a <= stop_b and start_b <= stop_a
def doesOverlap(A, B):
return overlap(A.start, A.stop, B.start, B.stop)
def overlap(a0, a1, b0, b1):
# First we "lift" the intervals from the yearly "circle"
# to the time "line" by adjusting the ending date if
# ends up before starting date...
if a1 < a0: a1 += 365
if b1 < b0: b1 += 365
# There is an intersection either if the two intervals intersect ...
if a1 > b0 and a0 < b1: return True
# ... or if they do after moving A forward or backward one year
if a1+365 > b0 and a0+365 < b1: return True
if a1-365 > b0 and a0-365 < b1: return True
# otherwise there's no intersection
return False
我正在尝试寻找一种优雅的算法来检查两个年度重复周期是否重叠。该期间与年份无关，但可以预期年份始终是闰年。
例如，时间段 A =（3 月 1 日至 5 月 1 日）和时间段 B =（4 月 1 日至 9 月 1 日）重叠。 此外，期间 A =（10 月 1 日至 2 月 1 日）和期间 B =（1 月 1 日至 3 月 1 日）重叠。
然而，我发现这比我预期的要难。复杂性来自于跨越年末的时期。
我有一个可行的解决方案（请参阅下面的 doesOverlap(A,B) 方法），但我发现它令人困惑。
# for the rest of the MWE context code, see further
# WORKING, but a bit convulted
def doesOverlap(A, B):
'''returns True if yearly period A and B have overlapping dates'''
# list to track if day in year is part of a period A
# (this could probably be done a bit cheaper with a dictionary of tuples, but not relevant for my question)
yeardayCovered = [False for x in range(366)] # leap year
# mark the days of A
for d in range(A.start, A.start + A.length):
yeardayCovered[d % 366] = True
# now check each of the days in B with A
for d in range(B.start, B.start + B.length):
if yeardayCovered[d % 366]:
return True
return False
我相信应该可以用更少的检查和更优雅的方式来做到这一点。我尝试将其中一个开始日期设置为零偏移量，应用一些模运算符，然后进行常规（非循环）范围重叠检查（Algorithm to detect overlapping periods）。但我还没有得到它适用于我所有的测试用例。
#NOT WORKING CORRECTLY!!
def doesOverlap(A, B):
'''determines if two yearly periods have overlapping dates'''
Astart = A.start
Astop = A.stop
Bstart = B.start
Bstop = B.stop
# start day counting at Astart, at 0
offset = Astart
Astart = 0
Astop = (Astop - offset) % 366
Bstart = (Bstart - offset) % 366
Bstop = (Bstop - offset) % 366
# overlap?
#
return (Astart <= Bstop and Bstart <= Astop)
注意：我已经完成了 Python 中的代码，但理想情况下，解决方案不应过于 Python 具体（即不使用通常只是开箱即用的功能在 Python 中可用，但在 C 或 C# 中不可用）
# MWE (Minimal Working Example)
import datetime
import unittest
class TimePeriod:
def __init__(self, startDay, startMonth, stopDay, stopMonth):
self.startDay = startDay
self.startMonth = startMonth
self.stopDay = stopDay
self.stopMonth = stopMonth
def __repr__(self):
return "From " + str(self.startDay) + "/" + str(self.startMonth) + " to " + \
str(self.stopDay) + "/" + str(self.stopMonth)
def _dayOfYear(self, d, m, y=2012):
'''2012 = leap year'''
date1 = datetime.date(year=y, day=d, month=m)
return date1.timetuple().tm_yday
@property
def start(self):
'''day of year of start of period, zero-based for easier modulo operations! '''
return self._dayOfYear(self.startDay, self.startMonth) - 1
@property
def stop(self):
'''day of year of stop of period, zero-based for easier modulo operations! '''
return self._dayOfYear(self.stopDay, self.stopMonth) - 1
@property
def length(self):
'''number of days in the time period'''
_length = (self.stop - self.start) % 366 + 1
return _length
def doesOverlap(A, B):
# code from above goes here
class TestPeriods(unittest.TestCase):
pass
def test_generator(a, b, c):
def test(self):
self.assertEqual(doesOverlap(a, b), c)
return test
if __name__ == '__main__':
#some unit tests, probably not complete coverage of all edge cases though
tests = [["max", TimePeriod(1, 1, 31, 12), TimePeriod(1, 1, 1, 1), True],
["BinA", TimePeriod(1, 3, 1, 11), TimePeriod(1, 5, 1, 10), True],
["BoverEndA", TimePeriod(1, 1, 1, 2), TimePeriod(10, 1, 3, 3), True],
["BafterA", TimePeriod(1, 1, 1, 2), TimePeriod(2, 2, 3, 3), False],
["sBoutA", TimePeriod(1, 12, 2, 5), TimePeriod(1, 6, 1, 7), False],
["sBoverBeginA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 10, 1, 12), True],
["sBinA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 1, 1, 2), True],
["sBinA2", TimePeriod(1, 11, 2, 5), TimePeriod(1, 12, 10, 12), True],
["sBinA3", TimePeriod(1, 11, 2, 5), TimePeriod(1, 12, 1, 2), True],
["sBoverBeginA", TimePeriod(1, 11, 2, 5), TimePeriod(1, 10, 1, 12), True],
["Leap", TimePeriod(29, 2, 1, 4), TimePeriod(1, 10, 1, 12), False],
["BtouchEndA", TimePeriod(1, 2, 1, 2), TimePeriod(1, 2, 1, 3), True]]
for i, t in enumerate(tests):
test_name = 'test_%s' % t[0]
test = test_generator(t[1], t[2], t[3])
setattr(TestPeriods, test_name, test)
# unittest.main()
suite = unittest.TestLoader().loadTestsFromTestCase(TestPeriods)
unittest.TextTestRunner(verbosity=2).run(suite)
您可以将跨年末的时间段分成两部分，然后将两者进行比较。这将导致不需要任何 Python 特定功能的非常简单的递归函数：
def overlap(start_a, stop_a, start_b, stop_b):
if start_a > stop_a:
return overlap(start_a, 365, start_b, stop_b) or overlap(0, stop_a, start_b, stop_b)
elif start_b > stop_b:
return overlap(start_a, stop_a, start_b, 365) or overlap(start_a, stop_a, 0, stop_b)
else:
return start_a <= stop_b and start_b <= stop_a
def doesOverlap(A, B):
return overlap(A.start, A.stop, B.start, B.stop)
def overlap(a0, a1, b0, b1):
# First we "lift" the intervals from the yearly "circle"
# to the time "line" by adjusting the ending date if
# ends up before starting date...
if a1 < a0: a1 += 365
if b1 < b0: b1 += 365
# There is an intersection either if the two intervals intersect ...
if a1 > b0 and a0 < b1: return True
# ... or if they do after moving A forward or backward one year
if a1+365 > b0 and a0+365 < b1: return True
if a1-365 > b0 and a0-365 < b1: return True
# otherwise there's no intersection
return False