Skip to content

Instantly share code, notes, and snippets.

@navanchauhan
Created March 17, 2023 07:34
Show Gist options
  • Save navanchauhan/d2469b3c03da907d5071e338830794b1 to your computer and use it in GitHub Desktop.
Save navanchauhan/d2469b3c03da907d5071e338830794b1 to your computer and use it in GitHub Desktop.
Simplest greedy-timeboxing algorithm implementation in Python
# Timeboxing Algorithms
from datetime import datetime, timedelta
timeboxes = []
class TaskEvent:
"""
A class to represent a task with its due date, title, description, priority, and time required to complete.
Attributes
----------
due_date : datetime
The due date of the task.
title : str
The title of the task.
description : str
A brief description of the task.
priority : int
The priority level of the task (lower value means higher priority).
time_required : int
The estimated time required to complete the task in minutes.
"""
def __init__(self, due_date, title: str = "Task", description: str = "Description", priority: int = 2, time_required: int = 40):
self.due_date = datetime.fromisoformat(due_date)
self.title = title
self.description = description
self.priority = priority
self.time_required = time_required
class Timebox:
"""
A class to represent a timebox, which is a block of time allocated for a task.
Attributes
----------
task : TaskEvent
The task to be scheduled in the timebox.
start_time : datetime
The starting time of the timebox.
available : bool
Indicates whether the timebox is available for scheduling a task.
length : int
The length of the timebox in minutes.
"""
def __init__(self, task: TaskEvent, start_time, available: bool = True, length: int = 10):
self.task = task
self.available = available
self.start_time = start_time
self.length = length
def get_num_timeboxes(length: int, start_date: datetime, end_date: datetime) -> int:
"""
Calculate the number of timeboxes that can fit between the start date and the end date.
Parameters
----------
length : int
The length of each timebox in minutes.
start_date : datetime
The start date for creating timeboxes.
end_date : datetime
The end date for creating timeboxes.
Returns
-------
int
The number of timeboxes that can fit between the start date and the end date.
"""
num_days = abs((start_date-end_date).days)
num_minutes_avail = num_days*24*60
return num_minutes_avail//length
def create_timeboxes(length: int, start_date: datetime, end_date: datetime) -> [Timebox]:
"""
Create a list of Timebox objects between the start date and the end date.
Parameters
----------
length : int
The length of each timebox in minutes.
start_date : datetime
The start date for creating timeboxes.
end_date : datetime
The end date for creating timeboxes.
Returns
-------
list
A list of Timebox objects created between the start date and the end date.
"""
timeboxes = []
num_boxes = get_num_timeboxes(length, start_date, end_date)
for _ in range(num_boxes):
box = Timebox(task=None, start_time=start_date, length=length)
start_date += timedelta(minutes=length)
timeboxes.append(box)
return timeboxes
def blackout_before_now(timeboxes) -> [Timebox]:
"""
Set the availability of Timebox objects to False if their start time is before the current time.
Parameters
----------
timeboxes : list
A list of Timebox objects.
Returns
-------
list
A list of Timebox objects with updated availability.
"""
now = datetime.now().timestamp()
boxes = []
for box in timeboxes:
if box.start_time.timestamp() < now:
box.available = False
boxes.append(box)
return boxes
def schedule_tasks(tasks: [TaskEvent], timeboxes: [Timebox], length: int = 10, lpadding: int = 1, rpadding: int = 1) -> [Timebox]:
"""
Schedule tasks in the timeboxes, taking into account the padding before and after the task.
Parameters
----------
tasks : list
A list of TaskEvent objects to be scheduled.
timeboxes : list
A list of Timebox objects.
length : int, optional
The length of each timebox in minutes (default is 10).
lpadding : int, optional
The number of free timeboxes required before the task (default is 1).
rpadding : int, optional
The number of free timeboxes required after the task (default is 1).
Returns
-------
list
A list of Timebox objects with scheduled tasks.
"""
tasks.sort(key=lambda x: (x.priority, x.due_date))
for task in tasks:
num_boxes_required = task.time_required // length
available_boxes = 0
start_index = 0
for index, box in enumerate(timeboxes):
if box.available:
if available_boxes == 0:
start_index = index
available_boxes += 1
else:
available_boxes = 0
if available_boxes == num_boxes_required + lpadding + rpadding:
if lpadding > 0:
start_index += lpadding
for i in range(start_index, start_index + num_boxes_required):
timeboxes[i].available = False
timeboxes[i].task = task
break
return timeboxes
def get_available(timeboxes) -> int:
"""
Count the number of available timeboxes in a list of Timebox objects.
Parameters
----------
timeboxes : list
A list of Timebox objects.
Returns
-------
int
The number of available timeboxes in the list.
"""
avail = 0
for box in timeboxes:
if box.available:
avail += 1
return avail
if __name__ == "__main__":
# Create Sample Tasks
task1 = TaskEvent(due_date="2023-03-19T15:30",priority=1, title="firt")
task2 = TaskEvent(due_date="2023-03-18T23:20",priority=3)
# Sample Dates
start_date = datetime(2023,3,15)
end_date = datetime(2023,3,20)
# Number of Timeboxes to be created between the dates
print(get_num_timeboxes(10, start_date, end_date))
# Create Boxes
boxes = create_timeboxes(10, start_date, end_date)
# Make Boxes before now as unavailable for scheduling
boxes = blackout_before_now(boxes)
# Print how many boxes are available
print(get_available(boxes))
# Schedule our sample tasks
boxes = schedule_tasks([task1, task2], boxes)
# Check if successfully scheduled
print(get_available(boxes))
@navanchauhan
Copy link
Author

Pure python implementation for the algorithm of my Time boxing app (PrudentStudio/TimeSlicer). This is missing the feature of interacting with CalDav Servers to read scheduled events and write back the scheduled tasks as events, which is present in the app.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment