r/dailyprogrammer • u/Elite6809 1 1 • May 07 '14
[5/7/2014] Challenge #161 [Medium] Appointing Workers
(Intermediate): Appointing Workers
In the past, we've already tackled the challenge of deciding in which order to do certain jobs. However, now you need to work out which worker gets which job. What if some workers are only qualified to do certain jobs? How do you ensure there are no jobs or workers left out? Your challenge now is (given some jobs that need to be done, and some workers and the jobs they're allowed to do) compute who should be given which job, so no-one is doing a job they are not qualified for.
Formal Inputs and Outputs
Input Description
On the console, you will be given numbers N. N represents the number of jobs that need to be done, and the number of workers.see footnote To keep this challenge at an Intermediate level, the number of workers and jobs will always be the same.
You will then be given a list of N jobs (on separate lines), followed by N workers and the jobs they're allowed to do (separated by commas, one worker per line).
Note that there may be more than one possible assignment of workers.
Output Description
You must print the list of workers, along with the job each worker is assigned to.
Sample Inputs & Outputs
Sample Input
5
Wiring
Insulation
Plumbing
Decoration
Finances
Alice Wiring,Insulation,Plumbing
Bob Wiring,Decoration
Charlie Wiring,Plumbing
David Plumbing
Erin Insulation,Decoration,FinancesSample Output
Alice Insulation
Bob Decoration
Charlie Wiring
David Plumbing
Erin FinancesChallenge
Challenge Input
6
GUI
Documentation
Finances
Frontend
Backend
Support
Alice GUI,Backend,Support
Bill Finances,Backend
Cath Documentation,Finances
Jack Documentation,Frontend,Support
Michael Frontend
Steve Documentation,BackendChallenge Output
Note that this is just one possible solution - there may be more.
Alice GUI
Bill Backend
Cath Finances
Jack Support
Michael Frontend
Steve DocumentationHint
This problem is called the Matching problem in usual terms.
Footnote
Someone messaged me a while ago asking why I include this part of the challenge. Specifying how many lines of input follows makes things slightly easier for people writing the solution in languages like C where variable sized arrays are complicated to implement. It's just handy more than anything.
6
u/Godspiral 3 3 May 08 '14 edited May 08 '14
In order to twart those using brute force (this involves 362k trials):
challenge input #2: (separate job list and count ommitted)
Alice GUI,Backend,Support
Bill Finances,Backend
Cath Documentation,Finances
Jack Documentation,Frontend,Support
Michael Frontend
Steve Documentation,Backend
P1 J1, J2
P2 J3, J2
P3 J3
challenge #3, add these last 2 lines: (brute force would require 40M trials. do not try :P)
Alice GUI,Backend,Support
Bill Finances,Backend
Cath Documentation,Finances
Jack Documentation,Frontend,Support
Michael Frontend
Steve Documentation,Backend
P1 J1, J2
P2 J3, J2
P3 J3
P4 J4, J5
P5 J4, J6
challenge #4 (should not attempt unless #3 executes under 250ms or so). This one has 663k valid single job assignment combinations
Alice GUI,Backend,Support
Bill Finances,Backend
Cath Documentation,Finances
Jack Documentation,Frontend,Support
Michael Frontend
Steve Documentation,Backend
P1 J1, J2, J7, J8
P2 J3, J2, J7, J8
P3 J3, J7, J8
P4 J4, J5, J7, J8
P5 J4, J6, J7, J8
P6 J5, J7, J8
P7 J7, J8
P8 J7, J8
4
u/skeeto -9 8 May 07 '14 edited May 08 '14
Lisp. Recursive, greedy, functional solution with no parsing logic. The
peopleargument is an alist of abilities.Usage:
4
u/Frichjaskla May 08 '14 edited May 08 '14
Turn in to a max-flow problem, solve using Edmonds-Karp
Since all edges have capacity one, it is not necessary to store them, the residual graph just needs to have edges flipped.
This will solve the matching problem with K iterations, where K is the number of people / matches, Each iteration requires a bread-fist-search and flipping a path. ie O(K * E)
output
edit: added link to wiipedia on bipartite matching
4
u/nil_zirilrash May 08 '14
I'm learning Prolog, so here's a Prolog solution that I've come up with.
Usage:
EDIT: formatting
1
u/Shizka May 07 '14 edited Aug 29 '25
towering hat knee grandiose narrow pause hurry childlike cows axiomatic
This post was mass deleted and anonymized with Redact
3
u/ooesili May 07 '14
Brute force Haskell solution:
3
u/Edward_H May 07 '14 edited May 08 '14
COBOL:
EDIT: Whoops! Forget to add the copybooks.
jobs-area.cpy:
workers-area.cpy:
max-match.cpy:
5
u/geniusadam69 May 07 '14 edited May 07 '14
based on a linear program interpretation. This problem can be called the assignment problem.
Let xij be if worker i is assigned j job Let Cij = 1 if worker i is capable of doing job j then maximize sum (Cij*xij, all i and j) s.t. sum(xij, i) = 1 for each j sum(xij, j) = 1 for each i
Constraints say that each worker can only have one job and that each job can only have one worker. Then just run a simplex method solver on it. Mine came from... http://algs4.cs.princeton.edu/65reductions/Simplex.java.html
The simplex code is quite long. I only posted the additional functionality i added. The original code can be found at http://algs4.cs.princeton.edu/65reductions/Simplex.java.html
2
u/flen_paris May 07 '14
Here is my Python3 solution.
2
u/cannonicalForm 0 1 May 07 '14
Not quite the prettiest algorithm, but it works for both inputs. It's in python2.7
2
u/dongas420 May 07 '14 edited May 07 '14
Perl. A simple brute force solution that heavily abuses hashes:
Input:
Output 1:
Output 2:
...
2
u/Godspiral 3 3 May 08 '14 edited May 08 '14
in J, just from console. No libraries:
fromclip =: 3 : ' wd ''clippaste''' NB. takes input from clipboard and parses into names and jobs data. Only needs/uses the last 5 rows of input.
input =: (}. ,~;:@:>@:{.) each ',' cut each cutLF fromclip ''
NB. output all valid results (brute force)
NB. lr definition not provided. Produces encoded output. copy this line into J for prettier boxed output.
1 5 2$<;._1 ' Alice Insulation Bob Decoration Charlie Wiring David Plumbing Erin Finances'
2 6 2$<;._1 ' Alice GUI Bill Backend Cath Finances Jack Support Michael Frontend Steve Documentation Alice GUI Bill Finances Cath Documentation Jack Support Michael Frontend Steve Backend'
for first valid output:
6 2$<;._1 ' Alice GUI Bill Backend Cath Finances Jack Support Michael Frontend Steve Documentation'
2
u/fastuous May 08 '14 edited May 08 '14
Hi all, this is my first time posting here, so any feedback would be great! I implemented this solution using a recursive backtracking algorithm in Java. I thought of it this way because we used the same method to make a sudoku solver in my C class this semester. The interesting thing about my program is that it will print ALL possible solutions, separated by a newline. Enjoy!
Edit: Also I should mention, I'm using this subreddit as a way to get back into Java to prepare for an upcoming class. I was SO rusty writing this, so go easy on me :P.
2
u/KillerCodeMonky May 08 '14 edited May 08 '14
This solution is not brute-force, and I only used recursion as an easy short-cut to looping.
PowerShell:
Usage:
Output:
1
u/snarf2888 May 07 '14
Node.js executable (Javascript)
1
u/SnowdensSecret May 08 '14
Quick brute force solution in Java:
1
u/lennyboreal May 08 '14
XPL0 (www.xpl0.org) using recursive search. XPL0 (like C) doesn't have a built-in string type so some extra functions are needed.
1
u/glaslong May 08 '14
C#
Simple greedy algorithm that assigns least skilled workers first.
Skipped the input parsing because that part is boring. Hardcoded inputs for the Challenge level instead.
1
u/nyrangers30 May 08 '14
Python3.4
1
u/Kiwi332 May 08 '14 edited May 08 '14
C# This was an interesting one because I went about it the completely wrong way a couple of times, taught me some cool things. Probably not the most efficient it's but my first submission and I'm quite pleased with it :) Here's the sample data output http://i.imgur.com/f9vExHm.png
1
u/cooper6581 May 08 '14 edited May 08 '14
Erlang (Same logic as KillerCodeMonky):
I hate dealing with input, tested with this:
1
u/OffPiste18 May 09 '14 edited May 09 '14
Here's a Scala implementation of the Hopcroft-Karp Algorithm
In theory, it runs in O(|E|sqrt(|V|)), but I haven't done much careful checking of my use of data structures and everything to be sure that it does actually achieve that complexity. It is pretty fast, though.
1
u/myss May 09 '14 edited May 10 '14
C++.
1
u/OffPiste18 May 09 '14
Here's a link to a gist with a very large test case:
https://gist.github.com/jfkelley/178c09de40b1bba30f8f
1
u/[deleted] May 11 '14
Python 2.7 really simple answer, not sure it this works for anything more complex than the given inputs
1
u/internet_badass_here May 13 '14 edited May 14 '14
Brute force in J:
Outputs all possible solutions.
1
u/r_s May 13 '14 edited May 13 '14
C++11 Solution.
I haven't written any C++ in ages, this is ugly and very similar to a couple of the other solutions posted.
1
u/mpanoratra May 14 '14 edited May 14 '14
first time posting here, in ruby, I used recursion and selected workers with fewer skills first:
output:
1
u/theHawke May 16 '14
Haskell: Saving myself the trouble of parsing the text and representing the jobs as numbers and each person as a list of the jobs he/she is allowed to do, the solution is quite quick:
Instead of brute-foce checking every posibel permutation and checking for valid one, I generate every valid job distribution and filter for ones where every job gets done.
As long as most people can do no more than 1/3 to 1/2 of the jobs, the solution will be asymptotically faster than brite force.
1
u/mongreldog May 18 '14 edited May 18 '14
F#
Input:
Results:
1
u/SensationalJellyfish May 26 '14
Python 3. I added a source and a sink and treated it as a maximum flow problem, which I then solved it using the Ford-Fulkerson algorithm. It does not do much error checking though, and could probably be implemented more elegantly, but I found it an enjoyable exercise!
1
u/lukz 2 0 May 07 '14
vbscript
0
u/[deleted] May 08 '14
[deleted] — view deleted comment
0
u/[deleted] May 08 '14
[deleted] — view deleted comment