{"_id":"@awarnes/shipment-routing","_rev":"3-0a81722139ac1b21e164ac9d8d8e35b5","name":"@awarnes/shipment-routing","dist-tags":{"latest":"1.1.0","next":"1.0.0-0"},"versions":{"0.0.1":{"name":"@awarnes/shipment-routing","version":"0.0.1","description":"Take home code challenge","bin":{"shipment-routing":"index.js"},"main":"index.js","scripts":{"lint":"eslint . --ext .js","test":"npm run lint && npm run test:unit && npm run test:integration","test:coverage":"jest --coverage","test:integration":"jest test/integration.test.js","test:unit":"jest src","test:watch":"jest --watch","postinstall":"INIT_CWD=$(git rev-parse --show-toplevel) node resources/git-hooks.js"},"repository":{"type":"git","url":"git+https://github.com/awarnes/shipment-routing.git"},"author":{"name":"awarnes"},"license":"ISC","bugs":{"url":"https://github.com/awarnes/shipment-routing/issues"},"homepage":"https://github.com/awarnes/shipment-routing#readme","dependencies":{"@conpago/address":"^0.2.1","commander":"^10.0.0","hungarian-on3":"^0.3.1"},"devDependencies":{"@faker-js/faker":"^7.6.0","eslint":"^8.34.0","eslint-config-semistandard":"^17.0.0","eslint-config-standard":"^17.0.0","eslint-plugin-import":"^2.27.5","eslint-plugin-jest":"^27.2.1","eslint-plugin-n":"^15.6.1","eslint-plugin-promise":"^6.1.1","jest":"^29.4.3"},"gitHead":"addb913c04b197bddb38c5cc5ea2597c84470b19","_id":"@awarnes/shipment-routing@0.0.1","_nodeVersion":"18.13.0","_npmVersion":"8.19.3","dist":{"integrity":"sha512-BLi0yjaWvpYj5paS3cI3LhxTcrlX1cV7WtqkDXTxymeArOw31zcGsieCv/54GRO7lHGZAH/IDmeI6t6+It7oiw==","shasum":"7f436937349f60c7ce7f4acc21f8cd2f51b68a52","tarball":"https://registry.npmjs.org/@awarnes/shipment-routing/-/shipment-routing-0.0.1.tgz","fileCount":32,"unpackedSize":146584,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDglgm9Gd+vCuy/YjQ3ZscxF0oaiO876qpihq+1h50DPgIhAIuSgCSew/+GCiBibyr4mZcRt82Lv5meIUc2gK6AE+1q"}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v4.10.10\r\nComment: https://openpgpjs.org\r\n\r\nwsFzBAEBCAAGBQJj+lRwACEJED1NWxICdlZqFiEECWMYAoorWMhJKdjhPU1b\r\nEgJ2VmqlsQ//XplGfzVBc7MMxLnRMKr2vDrM5i/R7d/zZQFjiEwJgV01Zfc6\r\nzW+E85ivG2+Xn3fjqa5C2oelmeWaFYV8tPiHHfAMtxC4KpDkYDWDUajxs82N\r\n6j527Lf53j97AnwXHbyogeNH0Z9VIx3HYBN80DiStq73pYn4BCZdh5uWQRVx\r\ncLLNT9NhqQr4DDOGK1vxSJ9ifQxrd8j/S6o7KF5gThkQ3ACzRSpxDehYROKX\r\n179cyYTRp/xTahqMWGVYlHEzrCw8mEpM48Ee3Wi9rCgJIRnsYqFoTVEszbkO\r\nlazO/nNSTbr9S0tH+EpqI3fU0yngBOnvxSuVMKIo3shoXtappsXVIko1DYNX\r\nK/jOwlLtNGqzyTvv8Q7JW/gi2lT9KCRT7TIcvRf1BoNjYPjZM+j5hcQ42hnl\r\nIHoUfiaAO2ELkAV+Zz1oURz4hFDvPQPtp+i+CJuzV3pcjdBHqBKxT+hcJ0NK\r\ndzsBomoJq1A2Y6YMK+O6uLHtBQcY0p5BZ+ECIw7VsT6ksK35OIQEzanGgWnm\r\nZU1nAde306vuL2K3bbshpFByHx+kkc7bdNjJJUycxFH3aa8I9Rz2eREbVDMm\r\nZpfYpNWX7DqcKVwOj2dQgkHJyfm64PNDOigh6x47MeCkTynXdHKvbhEKYSFE\r\nfI2nfxGG0Ljytwa/DejOHLJjVy/wZa3nBHs=\r\n=vZI2\r\n-----END PGP SIGNATURE-----\r\n"},"_npmUser":{"name":"awarnes","email":"warnes.alexander@gmail.com"},"directories":{},"maintainers":[{"name":"awarnes","email":"warnes.alexander@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/shipment-routing_0.0.1_1677350000177_0.9795354550201412"},"_hasShrinkwrap":false},"1.0.0-0":{"name":"@awarnes/shipment-routing","version":"1.0.0-0","description":"Take home code challenge","bin":{"shipment-routing":"index.js"},"main":"index.js","scripts":{"lint":"eslint . --ext .js","test":"npm run lint && npm run test:unit && npm run test:integration","test:coverage":"jest --coverage","test:integration":"jest test/integration.test.js","test:unit":"jest src","test:watch":"jest --watch","postinstall":"INIT_CWD=$(git rev-parse --show-toplevel) node resources/git-hooks.js"},"repository":{"type":"git","url":"git+https://github.com/awarnes/shipment-routing.git"},"author":{"name":"awarnes"},"license":"ISC","bugs":{"url":"https://github.com/awarnes/shipment-routing/issues"},"homepage":"https://github.com/awarnes/shipment-routing#readme","dependencies":{"@conpago/address":"^0.2.1","@faker-js/faker":"^7.6.0","commander":"^10.0.0","hungarian-on3":"^0.3.1"},"devDependencies":{"eslint":"^8.34.0","eslint-config-semistandard":"^17.0.0","eslint-config-standard":"^17.0.0","eslint-plugin-import":"^2.27.5","eslint-plugin-jest":"^27.2.1","eslint-plugin-n":"^15.6.1","eslint-plugin-promise":"^6.1.1","jest":"^29.4.3"},"readme":"# Shipment Routing\n\nCode challenge to create a CLI for routing shipments to drivers.\n\n## Table of Contents\n\n1. [Description](#description)\n1. [Assumptions](#assumptions)\n1. [Installation](#installation)\n1. [Usage](#usage)\n1. [Challenges](#challenges)\n1. [Future Possibilities](#future-possibilities)\n## Description\n[To Top ↑](#table-of-contents)\n\nOur 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.\n\nEach 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.\n\nWith 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.\n\nThe top-secret algorithm is:\n- If the length of the shipment's destination street name is even, the base suitability\nscore (SS) is the number of vowels in the driver’s name multiplied by 1.5.\n- If the length of the shipment's destination street name is odd, the base SS is the\nnumber of consonants in the driver’s name multiplied by 1.\n- If the length of the shipment's destination street name shares any common factors\n(besides 1) with the length of the driver’s name, the SS is increased by 50% above the\nbase SS.\n\nWrite 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.\n\nThe output should be the total SS and a matching between shipment destinations and drivers.\n\nYou do not need to worry about malformed input, but you should certainly handle both upper and lower case names.\n\n## Assumptions\n[To Top ↑](#table-of-contents)\n\nSome of the assumptions that were made for this project:\n\n1. Driver's name includes their entire name and spaces between:\n    - honorific/title (if applicable)\n    - First Name\n    - Middle Name(s)\n    - Last Name\n    - Any other titles\n1. Destinations will generally meet [USPS address specifications](https://pe.usps.com/text/pub28/28c2_001.htm)\n1. The `destination street name` is the [street name](https://pe.usps.com/text/pub28/28c2_012.htm) with no direction signifiers, prefixes, or suffixes. For example:\n    - `123 Fake St` the street name is `Fake`\n    - `1242 East Paddington Highway` the street name is `Paddington`.\n1. Driver names and destination addresses will each be input on a single line (no newline breaks internal to the name/address)\n## Installation\n[To Top ↑](#table-of-contents)\n\nInstallation should be a simple:\n```bash\nnpm install\n```\n\n### Postinstall Script\nThe `postinstall` script will run after all dependencies have been installed. 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.\n\n> Note: If in dire need you can always add the `--no-verify` flag to your push command to skip the checks. Make sure that everything lints and passes testing prior to creating your PR though!\n\n## Usage\n[To Top ↑](#table-of-contents)\n\nThere are two commands with several options each. The easiest way to see how to use them is to run:\n```bash\nnode index help\n```\n\n### Route\n\nUsage:\n- `node index route [options]`\n- `shipment-routing route [options]`\n\nRoute shipments to drivers given a list of shipments and list of drivers\n\n| Options | Description |\n|---------|-------------|\n| -d --driverFile | File of driver names \\\\n separated|\n| -s --destinationFile | File of shipment destinations \\\\n separated |\n| -t --testData | Comma separated count of number of drivers and destinations to generate. |\n| -f --file | Dump output to file |\n| -h, --help | display help for command |\n\n#### Examples\nRead drivers and destinations from file\n```bash\nnode index route -d ./test/data/drivers100.data -s ./test/data/destinations100.data\n```\nRead drivers and destinations from file and output to file\n```bash\nnode index route -d ./test/data/drivers100.data -s ./test/data/destinations100.data -f\n```\nRoute 25 randomized drivers and 25 randomized destinations\n```bash\nnode index route -t 25,25\n```\n\n### Generate\n\nUsage:\n- `node index generate [options]`\n- `shipment-routing generate [options]`\n\nGenerate data for use with the command line tool\n\n| Options | Descriptions |\n| ------- | ------------ |\n| -d --driverCount | Number of driver names to generate|\n| -s --destinationCount | Number of destinations to generate|\n| -p --path | Path to save files. If not included will output on command line. |\n| -h, --help | display help for command|\n\n#### Examples\nPrint out 25 randomized drivers and 25 randomized destinations\n```bash\nnode index generate -d 25 -s 25\n```\nWrite 25 randomized drivers and 25 randomized destinations to files in the current working directory.\n```bash\nnode index generate -d 25 -s 25 -p .\n```\n## Challenges\n[To Top ↑](#table-of-contents)\n\nThis project was a lot of fun. I especially enjoyed being able to add all the quality of life features that every project should have. However, I did run into several challenges during the process.\n### Algorithm\n#### Assignment Problem\nI 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:\n>...maximizes the total SS over the set of drivers...\n\nI tried a few brute force 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.\n\nAfter more research I was able to find the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem) and realized that was what I needed to code around. It was fairly quick work to find a library that could handle the task relatively quickly. It could be interesting in the future to code my own algorithm, but this seems to be working efficiently for now.\n#### Map Jobs\nAs part of the required input for the [hungarian method](https://en.wikipedia.org/wiki/Hungarian_algorithm) we need to create a table of all possible combinations. I have a very rudimentary O(nm) ≈ O(n<sup>2</sup>) mapping function which is easily the worst 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.\n\n### Testing Commander\nOne of the other big challenges I had was how to manage the integration testing for [Commander.js](https://www.npmjs.com/package/commander). 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 that there could be issues with the way the integration tests are set up.\n## Future Possibilities\n[To Top ↑](#table-of-contents)\n\nIt's never over! Here are a few more things that could be fun/interesting to add to the project.\n1. Publish package\n    - see [Issue #13](https://github.com/awarnes/shipment-routing/issues/13)\n1. Fancy Address Parsing\n    - Address parsing/validation API: https://www.smarty.com/pricing/choose-your-plan\n    - NLP Based Address Parsing: https://www.npmjs.com/package/node-postal\n1. Properly handle `sometimes y` vowel/consonant counts\n    - see [Issue #14](https://github.com/awarnes/shipment-routing/issues/14)\n1. Re-add Node v14.x support\n    - see [Issue #3](https://github.com/awarnes/shipment-routing/issues/3)","readmeFilename":"README.md","gitHead":"3a09ceba884a37b20b762a5fac1444211c333b2d","_id":"@awarnes/shipment-routing@1.0.0-0","_nodeVersion":"18.13.0","_npmVersion":"8.19.3","dist":{"integrity":"sha512-+jDx11UGvZS5bpcOLKeyGWwAuAcznBBEeHDHwc5fgnKje7ynf5qd7TqQY9TVlwCS0WBriov/piuliZEIB9hl0w==","shasum":"5433a8f11d907437a6a47e7ae4f17d2b93df9ab2","tarball":"https://registry.npmjs.org/@awarnes/shipment-routing/-/shipment-routing-1.0.0-0.tgz","fileCount":13,"unpackedSize":22111,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQDQVkXHf/amwTr0gQXSH3M9d8ovI7jwm3ZcT8/p0/huswIgeq3WlJPZVVvtS6qNfMIJgARO1vNr1+232E8i0sfkt40="}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v4.10.10\r\nComment: https://openpgpjs.org\r\n\r\nwsFzBAEBCAAGBQJj+l2OACEJED1NWxICdlZqFiEECWMYAoorWMhJKdjhPU1b\r\nEgJ2Vmp3cQ/9Ef/nh24M/OFc61QBBte+YmhZ3UgPS1gQ87TMAOquaceuys7a\r\niVvfkmYBuIe3vgTl3Kkb6nXKn4VJUrwcCL6R/wSbFTF40UIOjUvXeKfLgeYH\r\nniKOnCtjsQaqccFgHWsUc11j/W5DVuHF4rMe48hkGjEtu58cihKJnB/ftTBJ\r\n/ztiNpFhSL8krF2/ZWS0OT7neySVD5edaXaoZi6wfOr8zcq8anxcVm8yGWRl\r\nMZQF8cdFs9JMnx3gJEF7O5/CqdAeUdy07XIHKkaZ8D03So2arPKdofx5z0Dc\r\n9MQKZfdSmyRmq+la7IqRo4Fy7+hVleP9OiNnOYBiJ9Nr62EbttSq42i0uM84\r\ny/jWG2fbkGh+8GcMZNFnVADP9GfcTmpZagp4rdN9ZHwQwTiavrBnYESHC5Vx\r\nMK7GLnq1L6U8ZmduTNOCCeiPLJww/PuC8hTYNgL8GGXkMZNEVvaO4+yUzJVf\r\noarm7pAdng2s4sWblCcf3f/2n2tMQGRgH1LmnO3R8EQae59TF0OQtqChoEAJ\r\n6HewXQGWQDpztGOlek+nf6tAwHv010vqRpsm5u1Rs6+n4JeyRxw4zoP0G4wQ\r\nQOTrc4lgez3PX4mU9bUkaMu6XDSpbckUDoPB2W6qowPwckxuLt+h7s6COauh\r\nIle1PdzgBmM1RqqM4CipOo+EiwhV6pGul30=\r\n=pOcP\r\n-----END PGP SIGNATURE-----\r\n"},"_npmUser":{"name":"awarnes","email":"warnes.alexander@gmail.com"},"directories":{},"maintainers":[{"name":"awarnes","email":"warnes.alexander@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/shipment-routing_1.0.0-0_1677352334192_0.2772768802313734"},"_hasShrinkwrap":false},"1.0.0":{"name":"@awarnes/shipment-routing","version":"1.0.0","description":"Take home code challenge","bin":{"shipment-routing":"index.js"},"main":"index.js","scripts":{"lint":"eslint . --ext .js","test":"npm run lint && npm run test:unit && npm run test:integration","test:coverage":"jest --coverage","test:integration":"jest test/integration.test.js","test:unit":"jest src","test:watch":"jest --watch","prepare":"INIT_CWD=$(git rev-parse --show-toplevel) node resources/git-hooks.js"},"repository":{"type":"git","url":"git+https://github.com/awarnes/shipment-routing.git"},"author":{"name":"awarnes"},"license":"ISC","bugs":{"url":"https://github.com/awarnes/shipment-routing/issues"},"homepage":"https://github.com/awarnes/shipment-routing#readme","dependencies":{"@conpago/address":"^0.2.1","@faker-js/faker":"^7.6.0","commander":"^10.0.0","hungarian-on3":"^0.3.1"},"devDependencies":{"eslint":"^8.34.0","eslint-config-semistandard":"^17.0.0","eslint-config-standard":"^17.0.0","eslint-plugin-import":"^2.27.5","eslint-plugin-jest":"^27.2.1","eslint-plugin-n":"^15.6.1","eslint-plugin-promise":"^6.1.1","jest":"^29.4.3"},"gitHead":"bf8ed3ed726f109b3bffa4c602370986f48008cf","_id":"@awarnes/shipment-routing@1.0.0","_nodeVersion":"18.13.0","_npmVersion":"8.19.3","dist":{"integrity":"sha512-W5fd3SHHDJUH7IPf/uFes+XWGyc/cxxoIF7z8PrBBOetMR6KmAYH0x0pcxw66n8w0TNrkJRxVQg+uFv65n/KPw==","shasum":"cdd867527351c7a1a794146e13fea92afed5e533","tarball":"https://registry.npmjs.org/@awarnes/shipment-routing/-/shipment-routing-1.0.0.tgz","fileCount":13,"unpackedSize":22676,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQCXAG/Nc8zGTM3T8f8ikwG2fhUERPF5tk4Au5XOSBMCwgIgUOo2mZZ8sxI9eZ+QD+lSoxwPdEE1oSdBUOreOsF/aZA="}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v4.10.10\r\nComment: https://openpgpjs.org\r\n\r\nwsFzBAEBCAAGBQJj+mHlACEJED1NWxICdlZqFiEECWMYAoorWMhJKdjhPU1b\r\nEgJ2Vmqqow//b/S374lLqsAlIFoDMWCTrlIkiGAQc5lD6W0lUqRe0Irx9y1A\r\nsHdy+tYO7mz4Rilsnu/IXhxum8Fud3HPd0FpuzkoIbdCKhC0qQducGcxnjyU\r\n6X7DO7jSEqFUqYQP7LpKO8aqCHBAGWl/qAYlhtQb4Y+wR1tu5Tv6815flAZ3\r\nk2Qpx+dsogKAaC4EXiKIE0TvNNzXEbkKAWY5FmVWIz6DjNOwzqD/eHOlJaJn\r\nfJfJH8uuzVac6ITGjuRWUo2p7NCbGchj2AJheyPSQEZWHIyUq3aIpWKjTHEw\r\n/TgMKJTqsBC7mAVeOCA2+S9Jos2O6gkzh9iEaKomXvNVPTxS5HxYSWPPxovM\r\nFGBrUVqkQijPw76uOJzCTXtTKqpf051UsbTG3n3f7NjANt2r8Q4661JAEGe6\r\nolY8Iw4OVDZsUp+m5rubgV2j+4CU1Yesaygd2nlGjZ+nqlYeCBRhyhJXd63e\r\nQX24UyCtPoeU+AFtZCDGahxAjjkbi1tW922FJhraSpc60NdIwAH3mZONAlJn\r\n32KzxzUl8paJKTk6SoT9zHmeMU1pp4FvhWPqT6gtZExQBSfWZdgYGyF7i33c\r\nZbC8TxzDcM8wQy2Wx4KJ4zEvjeAbLhcWj69jPDBfUjPo/Pm6UhCLf/bNBdL4\r\nnxOPkgau/z+q8Hlh6801U4TMEZ1cf+FaRH0=\r\n=ajsF\r\n-----END PGP SIGNATURE-----\r\n"},"_npmUser":{"name":"awarnes","email":"warnes.alexander@gmail.com"},"directories":{},"maintainers":[{"name":"awarnes","email":"warnes.alexander@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/shipment-routing_1.0.0_1677353445527_0.2207368241460037"},"_hasShrinkwrap":false},"1.1.0":{"name":"@awarnes/shipment-routing","version":"1.1.0","description":"Take home code challenge","bin":{"shipment-routing":"index.js"},"main":"index.js","scripts":{"lint":"eslint . --ext .js","test":"npm run lint && npm run test:unit && npm run test:integration","test:coverage":"jest --coverage","test:integration":"jest test/integration.test.js","test:performance":"node test/performance.js","test:unit":"jest src","test:watch":"jest --watch","prepare":"INIT_CWD=$(git rev-parse --show-toplevel) node resources/git-hooks.js"},"repository":{"type":"git","url":"git+https://github.com/awarnes/shipment-routing.git"},"author":{"name":"awarnes"},"license":"ISC","bugs":{"url":"https://github.com/awarnes/shipment-routing/issues"},"homepage":"https://github.com/awarnes/shipment-routing#readme","dependencies":{"@conpago/address":"^0.2.1","@faker-js/faker":"^7.6.0","commander":"^10.0.0","hungarian-on3":"^0.3.1"},"devDependencies":{"eslint":"^8.34.0","eslint-config-semistandard":"^17.0.0","eslint-config-standard":"^17.0.0","eslint-plugin-import":"^2.27.5","eslint-plugin-jest":"^27.2.1","eslint-plugin-n":"^15.6.1","eslint-plugin-promise":"^6.1.1","jest":"^29.4.3"},"gitHead":"fdce7e0e47c4aa6fd2bc7cfbf279eeeef9df5bb3","_id":"@awarnes/shipment-routing@1.1.0","_nodeVersion":"18.13.0","_npmVersion":"8.19.3","dist":{"integrity":"sha512-BK/imR4OqIn4WY7s6N/3VT4hojUl1ET615Yn50XSYkonUJxK4KY15XZ9HFQku491/CNNqK6TwnUNGZouivhDOw==","shasum":"4e2e5518066f033e0e09cc5416c2372244889fb0","tarball":"https://registry.npmjs.org/@awarnes/shipment-routing/-/shipment-routing-1.1.0.tgz","fileCount":19,"unpackedSize":36570,"signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIF7AsqpVn7SbL7iMw6mSyRa+Hgexdq46VZQtsIbdXhsVAiEA8vUFQgsB1HXslUnIOzLWS0jjvIPzq3AHveLe9VyFqfA="}],"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v4.10.10\r\nComment: https://openpgpjs.org\r\n\r\nwsFzBAEBCAAGBQJj+scJACEJED1NWxICdlZqFiEECWMYAoorWMhJKdjhPU1b\r\nEgJ2Vmo9fw/+Ma/zRXPQ0GZAABe80fr3lPBUtE6t+4uz8M/5iwsQP3hcQOsB\r\nDs9ltIHAMqUy0SqHrRGgqyb5cUL/2+Dk1+zb+Kk+prVfv7frh2nn3IhGngKQ\r\n2owbAWJzI95P4gWQp/s7qW8d5sC9PwaiqHJR+METe+CQH2yDG2Xp8EoxCcLb\r\nvw6xecWu2e5kJQpVVkQkdzk+L88rNaoeZ1CAuKwJns+H8RXq/3j1E8Qr59Dd\r\nciTeTfVZg85II2edCHS2Gr0SiZOsAMTv25MmMtHSEUL78WiCPNhIPRO4KzQT\r\nJq1EwBByiWM8oYvq/d8dSjQ7+JCqpIBfmuk/FGi1EYlOx8BRQsDlcB3U9fYD\r\nTnZG2ykSztACVsPaS1T7Fg8a/B77qufSnfu/3nPFkRJn/4apf/XwoOHoanJJ\r\nMc46XznrS+FyNoTj1ymT/psAby70ANntgYPEtjw1vE4/MDqbgecGy37gf3u8\r\nscPMVjeioZhZoiULLUu/5x0muba0Ugb5JOwcgpRZgL4mrPAiQk1Sktb4fbfi\r\nvSuPAFXPCkrU5bThbzkEA6l8MEnGHaDlbMTZNZ/HWOhKNUQInM23TrQEp4Pn\r\n9ols30IXJgA76NHXvhIflRGxQbafBDsQdy14e6zxr08GCPJ/KdE977tlGxg3\r\ngfpHcF4/XHtEGJkpHI74+Hw+FE/YVjhy7tk=\r\n=8TYs\r\n-----END PGP SIGNATURE-----\r\n"},"_npmUser":{"name":"awarnes","email":"warnes.alexander@gmail.com"},"directories":{},"maintainers":[{"name":"awarnes","email":"warnes.alexander@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/shipment-routing_1.1.0_1677379336797_0.11499174379195276"},"_hasShrinkwrap":false}},"time":{"created":"2023-02-25T18:33:20.105Z","0.0.1":"2023-02-25T18:33:20.406Z","modified":"2023-02-26T02:42:17.113Z","1.0.0-0":"2023-02-25T19:12:14.360Z","1.0.0":"2023-02-25T19:30:45.691Z","1.1.0":"2023-02-26T02:42:17.018Z"},"maintainers":[{"name":"awarnes","email":"warnes.alexander@gmail.com"}],"description":"Take home code challenge","homepage":"https://github.com/awarnes/shipment-routing#readme","repository":{"type":"git","url":"git+https://github.com/awarnes/shipment-routing.git"},"author":{"name":"awarnes"},"bugs":{"url":"https://github.com/awarnes/shipment-routing/issues"},"license":"ISC","readme":"# Shipment Routing\n\nCode challenge to create a CLI for routing shipments to drivers.\n\n## Table of Contents\n\n1. [Installation](#installation)\n1. [Usage](#usage)\n1. [Description](#description)\n1. [Assumptions](#assumptions)\n1. [Challenges](#challenges)\n1. [Future Possibilities](#future-possibilities)\n\n## Installation\n[To Top ↑](#table-of-contents)\n\nInstall package:\n```bash\nnpm install @awarnes/shipment-routing\n```\nInstall pre-release:\n```bash\nnpm install @awarnes/shipment-routing@next\n```\n\n### Prepare Script\nThe `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.\n\n> Note: If in dire need you can always add the `--no-verify` flag to your push command to skip the checks. Make sure that everything lints and passes testing prior to creating your PR though!\n\n## Usage\n[To Top ↑](#table-of-contents)\n\nThere are two commands with several options each. The easiest way to see how to use them is to run:\n```bash\nshipment-routing help\n```\n\n### Route\n\nUsage: `shipment-routing route [options]`\n\nRoute shipments to drivers given a list of shipments and list of drivers\n\n| Options | Description |\n|---------|-------------|\n| -d --driverFile | File of driver names \\\\n separated|\n| -s --destinationFile | File of shipment destinations \\\\n separated |\n| -t --testData | Comma separated count of number of drivers and destinations to generate. |\n| -x --maxThreads | Maximum number of threads to allow for the mapJobs function. Default 4. |\n| -f --file | Dump output to file |\n| -h, --help | display help for command |\n\n#### Examples\nRead drivers and destinations from file\n```bash\nshipment-routing route -d ./some/file/with/driver.data -s ./some/file/with/destination.data\n```\nRead drivers and destinations from file and output to file\n```bash\nshipment-routing route -d ./some/file/with/driver.data -s ./some/file/with/destination.data -f\n```\nRoute 25 randomized drivers and 25 randomized destinations\n```bash\nshipment-routing route -t 25,25\n```\n\n### Generate\n\nUsage: `shipment-routing generate [options]`\n\nGenerate data for use with the command line tool\n\n| Options | Descriptions |\n| ------- | ------------ |\n| -d --driverCount | Number of driver names to generate|\n| -s --destinationCount | Number of destinations to generate|\n| -p --path | Path to save files. If not included will output on command line. |\n| -h, --help | display help for command|\n\n#### Examples\nPrint out 25 randomized drivers and 25 randomized destinations\n```bash\nshipment-routing generate -d 25 -s 25\n```\nWrite 25 randomized drivers and 25 randomized destinations to files in the current working directory.\n```bash\nshipment-routing generate -d 25 -s 25 -p .\n```\nGenerate a file of 25 drivers and 25 destinations, then run the routing function on them.\n```bash\nshipment-routing generate -d 25 -s 25 -p . && shipment-routing route -d ./drivers.data -s ./destinations.data\n```\n\n## Description\n[To Top ↑](#table-of-contents)\n\nOur 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.\n\nEach 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.\n\nWith 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.\n\nThe top-secret algorithm is:\n- If the length of the shipment's destination street name is even, the base suitability\nscore (SS) is the number of vowels in the driver’s name multiplied by 1.5.\n- If the length of the shipment's destination street name is odd, the base SS is the\nnumber of consonants in the driver’s name multiplied by 1.\n- If the length of the shipment's destination street name shares any common factors\n(besides 1) with the length of the driver’s name, the SS is increased by 50% above the\nbase SS.\n\nWrite 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.\n\nThe output should be the total SS and a matching between shipment destinations and drivers.\n\nYou do not need to worry about malformed input, but you should certainly handle both upper and lower case names.\n\n## Assumptions\n[To Top ↑](#table-of-contents)\n\nSome of the assumptions that were made for this project:\n\n1. Driver's name includes their entire name and spaces between:\n    - honorific/title (if applicable)\n    - First Name\n    - Middle Name(s)\n    - Last Name\n    - Any other titles\n1. Destinations will generally meet [USPS address specifications](https://pe.usps.com/text/pub28/28c2_001.htm)\n1. The `destination street name` is the [street name](https://pe.usps.com/text/pub28/28c2_012.htm) with no direction signifiers, prefixes, or suffixes. For example:\n    - `123 Fake St` the street name is `Fake`\n    - `1242 East Paddington Highway` the street name is `Paddington`.\n1. Driver names and destination addresses will each be input on a single line (no newline breaks internal to the name/address)\n1. `Y` is always a consonant (see [Issue #14](https://github.com/awarnes/shipment-routing/issues/14))\n\n## Challenges\n[To Top ↑](#table-of-contents)\n\nThis 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.\n### Algorithm\n#### Assignment Problem\nI 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:\n>...maximizes the total SS over the set of drivers...\n\nI 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.\n\nAfter more research I was able to find the [assignment problem](https://en.wikipedia.org/wiki/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.\n#### Map Jobs\nAs part of the required input for the [hungarian method](https://en.wikipedia.org/wiki/Hungarian_algorithm) we need to create a table of all possible combinations. I have a very rudimentary O(nm) ≈ O(n<sup>2</sup>) 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](https://github.com/awarnes/shipment-routing/issues/15)).\n\n##### UPDATE 2/25/23:\nI'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.\n\nGiven 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.\n\nThe implementation of the hungarian algorthim that we're using here is expected to be O(n<sup>3</sup>) 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.\n\n###### Performance Testing\nIn 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:\n```\nTesting with [10] drivers and [10] destinations\n┌─────────────────┬─────────┐\n│     (index)     │ Values  │\n├─────────────────┼─────────┤\n│   driverTime    │ '0.000' │\n│ destinationTime │ '0.008' │\n│   mapJobsTime   │ '0.197' │\n│  hungarianTime  │ '0.002' │\n└─────────────────┴─────────┘\nTesting with [100] drivers and [100] destinations\n┌─────────────────┬─────────┐\n│     (index)     │ Values  │\n├─────────────────┼─────────┤\n│   driverTime    │ '0.000' │\n│ destinationTime │ '0.008' │\n│   mapJobsTime   │ '0.195' │\n│  hungarianTime  │ '0.002' │\n└─────────────────┴─────────┘\nTesting with [500] drivers and [500] destinations\n┌─────────────────┬─────────┐\n│     (index)     │ Values  │\n├─────────────────┼─────────┤\n│   driverTime    │ '0.002' │\n│ destinationTime │ '0.039' │\n│   mapJobsTime   │ '2.470' │\n│  hungarianTime  │ '0.215' │\n└─────────────────┴─────────┘\nTesting with [1000] drivers and [1000] destinations\n┌─────────────────┬─────────┐\n│     (index)     │ Values  │\n├─────────────────┼─────────┤\n│   driverTime    │ '0.007' │\n│ destinationTime │ '0.074' │\n│   mapJobsTime   │ '4.064' │\n│  hungarianTime  │ '1.603' │\n└─────────────────┴─────────┘\n```\n### Testing Commander\nOne of the other big challenges I had was how to manage the integration testing for [Commander.js](https://www.npmjs.com/package/commander). 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.\n## Future Possibilities\n[To Top ↑](#table-of-contents)\n\nIt's never over! Here are a few more things that could be fun/interesting to add to the project.\n1. Publish package :white_check_mark:\n    - ~~see [Issue #13](https://github.com/awarnes/shipment-routing/issues/13)~~\n1. Fancy Address Parsing\n    - Address parsing/validation API: https://www.smarty.com/pricing/choose-your-plan\n    - NLP Based Address Parsing: https://www.npmjs.com/package/node-postal\n1. Properly handle `sometimes y` vowel/consonant counts\n    - see [Issue #14](https://github.com/awarnes/shipment-routing/issues/14)\n1. Re-add Node v14.x support\n    - see [Issue #3](https://github.com/awarnes/shipment-routing/issues/3)\n1. Add more command line feedback for the user\n    - What part of the process is the program on?\n    - How far along is it?\n    - Expected time to completion?","readmeFilename":"README.md"}