Code challenge to create a CLI for routing shipments to drivers.
Install package:
npm install @awarnes/shipment-routingInstall pre-release:
npm install @awarnes/shipment-routing@nextThere are two commands with several options each. The easiest way to see how to use them is to run:
shipment-routing helpUsage: shipment-routing route [options]
Route shipments to drivers given a list of shipments and list of drivers
| Options | Description |
|---|---|
| -d --driverFile | File of driver names \n separated |
| -s --destinationFile | File of shipment destinations \n separated |
| -t --testData | Comma separated count of number of drivers and destinations to generate. |
| -x --maxThreads | Maximum number of threads to allow for the mapJobs function. Default 4. |
| -f --file | Dump output to file |
| -h, --help | display help for command |
Read drivers and destinations from file
shipment-routing route -d ./some/file/with/driver.data -s ./some/file/with/destination.dataRead drivers and destinations from file and output to file
shipment-routing route -d ./some/file/with/driver.data -s ./some/file/with/destination.data -fRoute 25 randomized drivers and 25 randomized destinations
shipment-routing route -t 25,25Usage: shipment-routing generate [options]
Generate data for use with the command line tool
| Options | Descriptions |
|---|---|
| -d --driverCount | Number of driver names to generate |
| -s --destinationCount | Number of destinations to generate |
| -p --path | Path to save files. If not included will output on command line. |
| -h, --help | display help for command |
Print out 25 randomized drivers and 25 randomized destinations
shipment-routing generate -d 25 -s 25Write 25 randomized drivers and 25 randomized destinations to files in the current working directory.
shipment-routing generate -d 25 -s 25 -p .Generate a file of 25 drivers and 25 destinations, then run the routing function on them.
shipment-routing generate -d 25 -s 25 -p . && shipment-routing route -d ./drivers.data -s ./destinations.dataOur sales team has just struck a deal with Acme Inc to become the exclusive provider for routing their product shipments via 3rd party trucking fleets. The catch is that we can only route one shipment to one driver per day.
Each day we get the list of shipment destinations that are available for us to offer to drivers in our network. Fortunately our team of highly trained data scientists have developed a mathematical model for determining which drivers are best suited to deliver each shipment.
With that hard work done, now all we have to do is implement a program that assigns each shipment destination to a given driver while maximizing the total suitability of all shipments to all drivers.
The top-secret algorithm is:
- If the length of the shipment's destination street name is even, the base suitability score (SS) is the number of vowels in the driver’s name multiplied by 1.5.
- If the length of the shipment's destination street name is odd, the base SS is the number of consonants in the driver’s name multiplied by 1.
- If the length of the shipment's destination street name shares any common factors (besides 1) with the length of the driver’s name, the SS is increased by 50% above the base SS.
Write an application in the language of your choice that assigns shipment destinations to drivers in a way that maximizes the total SS over the set of drivers. Each driver can only have one shipment and each shipment can only be offered to one driver. Your program should run on the command line and take as input two newline separated files, the first containing the street addresses of the shipment destinations and the second containing the names of the drivers.
The output should be the total SS and a matching between shipment destinations and drivers.
You do not need to worry about malformed input, but you should certainly handle both upper and lower case names.
Some of the assumptions that were made for this project:
- Driver's name includes their entire name and spaces between:
- honorific/title (if applicable)
- First Name
- Middle Name(s)
- Last Name
- Any other titles
- Destinations will generally meet USPS address specifications
- The
destination street nameis the street name with no direction signifiers, prefixes, or suffixes. For example:123 Fake Stthe street name isFake1242 East Paddington Highwaythe street name isPaddington.
- Driver names and destination addresses will each be input on a single line (no newline breaks internal to the name/address)
Yis always a consonant (see Issue #14)
This project was a lot of fun. I especially enjoyed being able to add all the quality of life features that every project should have. I did run into a few challenges during the process, which were interesting to solve.
I had put off the actual meat of the algorithm until later on thinking that it wouldn't be so difficult. What I had missed was the solution requirement that it:
...maximizes the total SS over the set of drivers...
I tried a attacking it a few different ways to begin with until I realized that there was a lot more going on to get the optimal value over the entire set of drivers and destinations.
After more research I was able to find the assignment problem and realized that was what I needed to code around. After that, it was fairly quick work to find a library that could handle the task effectively. It could be interesting in the future to code my own algorithm, but this seems to be working efficiently for now.
As part of the required input for the hungarian method we need to create a table of all possible combinations. I have a very rudimentary O(nm) ≈ O(n2) mapping function which is easily the biggest bottleneck in the program. I would like to come back and see if there's a way to make it more efficient for larger data sets (see Issue #15).
I'm sure there are plenty of other ways to look at improving performance of the program, but for now looking at the map jobs function I've set it up to split this into several jobs and run accross multiple worker threads. From initial testing this has improved the performance of the function from ~17 seconds on a 1000x1000 set to ~4 seconds.
Given the pace of the previous functions I had not thought of testing anything higher than that, but after adding the workers I tried running the program with a 10,000x10,000 set. In that single run the mapJobs function took ~290 seconds (~5 mintes). Far longer than I'd generally like, but significantly better than the naive approach.
The implementation of the hungarian algorthim that we're using here is expected to be O(n3) in the worst case. It has been interesting to see that it's often significantly faster than the O(nm) that the mapJobs function runs through. In this 10,000x10,000 case we definitely tipped over the line though because the runtime was approximately 2158 seconds, or 36 minutes. I have not tried that test again.
In the interest of collecting some data about the performance of each part of the program I wrote a simple performance testing function (I'm sure there's better out there, but it gives us an idea). You can run it yourself with npm run test:performance. These are the results from running each test 10 times and averaging the times:
Testing with [10] drivers and [10] destinations
┌─────────────────┬─────────┐
│ (index) │ Values │
├─────────────────┼─────────┤
│ driverTime │ '0.000' │
│ destinationTime │ '0.008' │
│ mapJobsTime │ '0.197' │
│ hungarianTime │ '0.002' │
└─────────────────┴─────────┘
Testing with [100] drivers and [100] destinations
┌─────────────────┬─────────┐
│ (index) │ Values │
├─────────────────┼─────────┤
│ driverTime │ '0.000' │
│ destinationTime │ '0.008' │
│ mapJobsTime │ '0.195' │
│ hungarianTime │ '0.002' │
└─────────────────┴─────────┘
Testing with [500] drivers and [500] destinations
┌─────────────────┬─────────┐
│ (index) │ Values │
├─────────────────┼─────────┤
│ driverTime │ '0.002' │
│ destinationTime │ '0.039' │
│ mapJobsTime │ '2.470' │
│ hungarianTime │ '0.215' │
└─────────────────┴─────────┘
Testing with [1000] drivers and [1000] destinations
┌─────────────────┬─────────┐
│ (index) │ Values │
├─────────────────┼─────────┤
│ driverTime │ '0.007' │
│ destinationTime │ '0.074' │
│ mapJobsTime │ '4.064' │
│ hungarianTime │ '1.603' │
└─────────────────┴─────────┘
One of the other big challenges I had was how to manage the integration testing for Commander.js. I toyed around with a few different things and ended up settling with the current solution of creating a subprocess to the testing process for each test. This seems to be working okay in terms of testing, but is much slower than I'd like it to be. I do worry that if the program took much longer to complete or there was some other complication that there could be issues with the way the integration tests are set up.
Another helping hand is always great! Please feel free to fork and open any PRs as you see fit and we'll review them.
git clone git@github.com:awarnes/shipment-routing.gitor
git clone https://github.com/awarnes/shipment-routing.gitOnce cloned, install dependencies:
npm installRun the tests to make sure everything is working as expected:
npm testThe prepare script will run after all dependencies have been installed (locally). This script will install the pre-push git-hook into the .git/hooks directory in the project. This helps ensure that everything has been properly linted and all tests are passing.
Note: If in dire need you can always add the
--no-verifyflag to your push command to skip the checks. Make sure that everything lints and passes testing prior to creating your PR though!
Make sure to grab an issue that is in the queue from here: https://github.com/awarnes/shipment-routing/issues
Don't see the issue that you want to fix? Feel free to create an issue and dig in. Note: if the issue isn't something that we want added/changed then we may reject the PR. It always helps to
@awarnesin your issue description to make sure that we'll be receptive to the PR.
Once you have your issue, make a feature branch, start your work (don't forget to add/update tests and documentation!) and then create a PR in to the main branch.
Once the PR has passed all CI tests, we'll review for code style, function, and what have you then approve and merge in the change! If you want to help us out, please add some testing notes about how you expect your change to work.
Run linting:
npm run lintFix basic linting issues (suggested before committing):
npm run lint -- --fixRun performance benchmarks:
npm run performanceRun all linting and tests (unit and integration):
npm testNote: This is run prior to any push to the remote to maintain well tested and linted code
Generate test coverage report:
npm run test:coverageRun integration tests:
npm run test:integrationRun unit tests:
npm run test:unitRun all tests continually while developing:
npm run test:watchPost install locally adds the pre-push git hook:
npm run prepareWe use the np package to help handle deployments. When a new package is ready to be built, tested, and deployed that will be run by the repository maintainers.
np helps ensure that everything is ready to go: no un-committed work, everything is tested, and only the right data is making it into the package. Additionally, it helps ensure that a tag is created in the repository, release notes are generated, and that the package version is updated sanely.
It's never over! Here are a few more things that could be fun/interesting to add to the project.
- Publish package ✅
see Issue #13
- Fancy Address Parsing
- Address parsing/validation API: https://www.smarty.com/pricing/choose-your-plan
- NLP Based Address Parsing: https://www.npmjs.com/package/node-postal
- Properly handle
sometimes yvowel/consonant counts- see Issue #14
- Re-add Node v14.x support
- see Issue #3
- Add more command line feedback for the user
- What part of the process is the program on?
- How far along is it?
- Expected time to completion?