5
\$\begingroup\$

Let's assume we have the following situation:

  • Multiple project topics exist, each corresponding to a natural number n,
  • students can sign in and choose two projects and give them either priority_1 or priority_2,
  • The name and the time when they sign in is tracked as well.

With all of the information above assume you receive data in the from of a txt-file looking like this

Martin  16:46:32    8   19
Alice   15:22:56    8   12
Alex    17:23:11    19  1
John    19:02:11    11  13
Phillip 19:03:11    11  13
Diego   15:23:57    14  5
Jack    16:46:45    8   3

where the columns represent the name, time, priority 1 and priority 2 in this order. You can assume that all of them signed in on the same day and students which signed in first have a higher priority in comparison to the others.

I wanted to write a program that takes this txt-file as input and returns a txt-file with output

Name    Assigned Project
Alice   8
Diego   14
Martin  19
Jack    3
Alex    1
John    11
Phillip 13

The solution I came up with looks like this:

import numpy as np

dat = np.genfromtxt("data.txt", dtype="str")

class person:
    def __init__(self, name, time, prio1, prio2):
        self.name = name
        sp = time.split(":")
        t = sp[0]*3600 + sp[1]*60 + sp[2]  
        self.time = t
        self.prio1 = prio1
        self.prio2 = prio2

names = dat[:, 0]
time = dat[:, 1]
prio1 = dat[:, 2]
prio2 = dat[:, 3]

people = []
for i,j,k,l in zip(names, time, prio1, prio2):
    people.append(person(i,j,k,l))

people_sorted_time = sorted(people, key=lambda x: x.time) 

for k in range(len(people_sorted_time)):
    for j in range(k + 1, len(people_sorted_time)):
        if people_sorted_time[k].prio1 == people_sorted_time[j].prio1:
            people_sorted_time[j].prio1 = people_sorted_time[j].prio2

res = open("results","w")
res.write("Name"+"\t"+"Assigned Project"+"\n")
for k in range(len(people_sorted_time)):
    res.write(people_sorted_time[k].name + "\t" 
        + people_sorted_time[k].prio1 + "\n")

The code seems to work fine, but I'm not sure if I actually was able to take care of all edge-cases. I'm also not sure if this is really a efficient way to solve the problem, I rarely code stuff like that (mostly computational physics stuff), and would appreciate any kind of suggestions on how one could improve the code in general.

EDIT: What I realized after some thinking is that it would probably be quite hard do implement further priority variables (like prio 3, prio 4, etc.). If someone could suggest a better way of deciding how to assign the projects in terms of priority, I'd be glad to see it.

\$\endgroup\$
  • \$\begingroup\$ Is there any reason to consider three students choosing the same pair? What about students in chronological order A(1,2), B(3,4), C(1,3) where a solution exists as long as you don’t choose greedily? \$\endgroup\$ – Ian MacDonald Dec 16 '18 at 0:48
  • \$\begingroup\$ Also, if a student waits until just after midnight, they are guaranteed first choice! \$\endgroup\$ – Ian MacDonald Dec 16 '18 at 0:50
  • \$\begingroup\$ @IanMacDonald I‘m sorry, but I‘m having a hard time understandig what you mean by A(1,2), etc. To the forst question, well two students chosing the same pair was just a special case which I wanted to have for tests and since popular topics are often chosen multiple times this didn‘t seem to far fetched. Not sure if three and two times the same pair makes really any difference.. And what exactly do you mean by „choose greedily“? \$\endgroup\$ – Sito Dec 16 '18 at 0:52
  • \$\begingroup\$ @IanMacDonald as written in the description you can assume that all students sign-in on the same day... \$\endgroup\$ – Sito Dec 16 '18 at 0:53
4
\$\begingroup\$

There are two issues I personally dislike very much.

Messing with date/time using homebrew algorithm and math

While looking easy to handle time/date are by far more complcated to handle than you ever can think of. Timezones, locals, leap years and so on. When doing time/date math and/or serialisation/deserialisation always(!) go for a library. For python this is datetime

When the code is lying to me when I'm reading it as natural language

With lying I mean your line

people_sorted_time[j].prio1 = people_sorted_time[j].prio2

This is not true. The person clearly stated a first priority project. When you change that value as an algorithmic side effect you immediatly break data integrity. Your person suddenly has both priorities on the same project. You even got yourself tricked. What happens, when a person got the first prio project taken away and later the second one as well?

Other issues

There is no need to have people_sorted_time, as you never refer to the read order again. Just do

people = sorted(people, key=lambda x: x.time) 

Never loop over range(len(something), always try to loop over the elements directly. Your output loop rewrites (still lying about prio1) to

for p in people:
    res.write(p.name + "\t" + p.prio1 + "\n")

You use numpy only for reading a file, then convert back to standard python. This is a fail. Read with python directly.

with open("data.txt") as infile:
    lines = infile.readlines()
people = [Person(*line.split()) for line in lines]

You need time for comparison only. There is no need to mess with it, string comparison will do.

self.time = time

Do not modify the people data but maintain a set of available projects

prio1_projects = set(p.prio1 for p in people)
prio2_projects = set(p.prio2 for p in people)
projects_available = prio1_projects | prio2_projects

When assigning projects we do it like

people = sorted(people, key = lambda p: p.time)
assignments = []
for p in people:
    if p.prio1 in projects_available:
        proj = p.prio1
    elif p.prio2 in projects_available:
        proj = p.prio2
    else:
        proj =  None
    assignments.append(proj)
    if proj is not None:
        projects_available.remove(proj)

Note the new None case.

The output code

with open("results","w") as res:
    res.write("Name"+"\t"+"Assigned Project"+"\n")
    for p, a in zip(people, assignments):
        res.write(p.name + "\t" + str(a) + "\n")
\$\endgroup\$
  • \$\begingroup\$ First of all, thank you very much for the comments! I think I understand most of them, or at least see why one should do it the way you suggest, but there when you say "Never loop over range(len(something)", could you maybe explain why? Is this just a convention, or are there downsides to doing this? \$\endgroup\$ – Sito Dec 16 '18 at 0:46
  • 2
    \$\begingroup\$ @Sito It is considered pythonic. (Convention) The talk, "loop like a native" covers this. \$\endgroup\$ – Ludisposed Dec 16 '18 at 12:07
  • 1
    \$\begingroup\$ @Sito: It has the advantage that you can usually directly use your code whether or not what you iterate over is a list (which is indexable, so range(len(x)) would work), a set (where you cannot use an index, but at least len(x) still works) and a generator (which might be infinite so you don't even know len(x)). Doing for x in foo works for any iterable (by definition). \$\endgroup\$ – Graipher Dec 16 '18 at 12:19
  • 1
    \$\begingroup\$ @Graipher Touché. I'll update my answer. \$\endgroup\$ – stefan Dec 16 '18 at 14:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.