Simple Algorithm feedback

Hello, I have a task at hand and would like to discuss with you what you think of my solution and whether would you do it completely differently or just change a thing here and there. Problem: Imagine you have a to-do list including tasks like the one below:

to_do_list = [
  {priority: 2, name: "Take out trash"},
  {priority: 1, name: "Go running"},
  {priority: 20, name: "Do homework"},
  {priority: 5, name: "Feed a dog"},
  {priority: 20, name: "Water plants"},
]

where priority >= 0.
Your task is to reduce priority values to minimum while persisting their priority order. eg: Right now, there are 5 tasks with priorities 1, 2, 5, 20. The goal is to reduce these numbers to look like 0, 1, 2, 3 without changing the order of tasks in the to_do_list.

Expected outcome:

to_do_list = [
  {priority: 1, name: "Take out trash"},
  {priority: 0, name: "Go running"},
  {priority: 3, name: "Do homework"},
  {priority: 2, name: "Feed a dog"},
  {priority: 3, name: "Water plants"},
]

My solution:

  1. Create a dictionary for unique priority values
  2. Store all tasks of the same priority in a list under its corresponding section(key) in the dictionary
  3. Create a list of sorted keys(priorities) from the dictionary in ascending order
  4. Initialise new priority to 0
  5. Iterate for each priority in the sorted keys(priorities)
  • access list of tasks with the same priority
  • change all the tasks’ priority attribute to new priority
  • increase new priority by 1
        # Step 1
        tasks_by_priority = dict()
        # Step 2 - start
        for task in to_do_list:
            priority = task['priority']
            # if first occurance of task's priority in the dictionary
            # initialise it with empty list
            if priority not in tasks_by_priority:
                tasks_by_priority[priority] = []
            # add item to the list
            tasks_by_priority[priority].append(item)
        # Step 3
        sorted_priorities = sorted(tasks_by_priority.keys())
        # Step 4
        new_priority = 0
        # Step 5
        for priority in sorted_priorities:
            for task in tasks_by_priority[priority]: 
                    task['priority'] = new_priority
            new_priority += 1

Thank you for you feedback

There are two serious problems. First, it’s not clear that it’s correct. The expected output for the example looks wrong but I have no way of knowing. Second, you’re copying the dictionaries from one list to another list, changing the values there, and end up changing the values in the original list of dictionaries. This isn’t wrong but it is confusing and unnecessary. You could rewrite it like this:

priorities = []
for task in task_list:
    priorities.append(task['priority']) if task['priority'] not in priorities
priorities.sort()
priority_map = {}
for new_priority, priority in enumerate(priorities):
    priority_map[priority] = new_priority
for task in task_list:
    task['priority'] = priority_map[task['priority']]

Hello,

I appreciate that you took your time and gave me a feedback.

Could you please help me understand how could I make it more clear that my solution is correct?
What would I need to do?
Why do you think the expected outcome looks wrong?
I’ve changed the names for now.

The expected outcome is 1, 0, 4, 3, 4. Why? What happened to 2? Is your code wrong or is the example/description wrong? I don’t know.

Apart of the main goal of this algorithm, I also want it to perform well—doing as few steps as possible. The idea is to “scan” the to_do_list first and create categories of priority and assign each task to its category. Let’s say the size of to_do_list is N. In that case, the time complexity of the scan takes N time.
View of tasks_by_priority after the initial scan:

tasks_by_priority = {
    1: [{priority: 1, name: "Go running"}],
    2: [{priority: 2, name: "Take out trash"}],
   20: [{priority: 20, name: "Do homework"}, {priority: 20, name: "Water plants"}],
    5: [{priority: 5, name: "Feed a dog"}],   
}

And it does not really copy the tasks, only the references to the tasks in the to_do_list.
Another thing is that I want the lowest priority to start with 0 and I can’t tell ahead whether there already are tasks with that priority or not. Also, I don’t really care what their values are, I only need to reduce their values while persisting the priority order. That’s why I take the keys and sort them. That will take (n log n) time on average.
Finally, I can loop through the sorted_priorities, accessing keys from the tasks_by_priority dictionary in order I need. That will also take N time as I need to iterate just once.
I just realised, I am losing a little time with creating the sorted_priorities from the dictionary keys so I could initialise priorities = [] at the beginning and append them during the scan, like this:

if priority not in tasks_by_priority:
                tasks_by_priority[priority] = []
                priorities.append(priority)

and sort them after.

From the point of view of time taken, the algorithm look like this:

  1. Scan => n time
  2. Sort priorities => n log n time
  3. Modify priorities => n time

You are right, I made a mistake there for some reason… Stupid me.
When you look at the description again, is that more clear now?
I would not be asking If I didn’t know I need to work on describing things in a clearer way.
Thanks

Code after revision:

# Step 1
        tasks_by_priority = dict()
        priorities = list()
        # Step 2 - start
        for task in to_do_list:
            priority = task['priority']
            # if first occurance of task's priority in the dictionary
            # initialise it with empty list
            if priority not in tasks_by_priority:
                tasks_by_priority[priority] = []
                priorities.append(priority)
            # add item to the list
            tasks_by_priority[priority].append(item)
        # Step 3
        priorities.sort()
        # Step 4 & 5
        for new_priority, priority in enumerate(priorities):
            for task in tasks_by_priority[priority]: 
                    task['priority'] = new_priority
            new_priority += 1

Okay. I’ve just learn that adding an item to a set() takes O(1) time on average. I understand why you think my code was unreasonably confusing. I had been thinking of your implementation too, but I was trying to avoid the is member of the priorities check on every iteration:

task['priority']) if task['priority'] not in priorities

I’ve implemented the same logic with using set() for priorities, which should theoretically run faster.

The way I actually wrote this was this:

priorities = sorted(list(set([task['priority'] for task in task_list])))  # [1, 2, 5, 20]
priority_map = {priority:index for index, priority in enumerate(priorities)}  # {1: 0, 2: 1, 5: 2, 20: 3}
for task in task_list:
    task['priority'] = priority_map[task['priority']]

I then rewrote it for you without using comprehensions. This is more readable and maintainable, at least for me. Those are the things I care about and performance is a distant third, at least in Python. If you’re interested in runtime performance, might I suggest Go instead?

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.