Bugnik
← All problems

05Pickup Locker Network

C++MediumFeatureSuggested time: 60 min

Pickup locker network (implement assign)

Sign in to start

Before you start

You'll get more out of this problem if you're comfortable with:

Language

  • C++ syntax for structs and classes across headers and sources, and reading g++ errors
  • Iterating with references so changes stick (for (Locker& l : bank.lockers))

Libraries and frameworks

  • std::array, std::vector, std::map, std::sort and std::optional
  • std::string operations (find, compare, substr)

Build and test tools

  • Running the tests and filtering them by name

Reasoning

  • Reading code line by line against a written spec
  • Turning a written spec into a small greedy algorithm with clear tie-breaks

Background

The Last-Mile Hubs team at a large online retailer runs self-service pickup lockers. Each delivery station serves several locker banks; when a driver drops a package off, the system picks a compartment and texts the customer a one-time pickup code. The assignment logic was removed during a refactor and never put back, and QA has found other problems on the way.

How the system works

Dimensions

  • A package's outside size, or a compartment's inside size, is LxWxH in whole centimetres (40x30x15, x or X). Each side is a positive whole number of at most 6 digits; anything else is a ParseError.
  • A package fits a space in some orientation: sort both boxes' sides from largest to smallest and compare them pairwise; the package fits when each of its sorted sides is <= the space's side in the same position. Touching is fine (equal sides fit).
  • Compartment interiors: S 35x25x10, M 45x35x20, L 60x45x40.
  • smallestFit(dims) is the smallest of S, M, L that the package fits, or none if it doesn't even fit L.

Network manifest

One bank per line, as key=value pairs separated by ;:

bank=NEAR; distance=300; lockers=S:2,M:1
bank=FAR;  distance=2500; lockers=S:1,M:1,L:1
  • Keys are case-insensitive, values are trimmed, unknown keys are ignored, blank lines and # lines are skipped.
  • bank, distance and lockers are required. distance (metres from the station) is a whole number ≥ 0.
  • lockers lists SIZE:COUNT items. Size letters are case-insensitive, each count is ≥ 1, and a size may appear only once per bank.
  • Compartments are numbered from 1 per size and named <bank>-<letter><n>: the line above gives NEAR-S1, NEAR-S2, NEAR-M1.
  • Duplicate bank ids are a ParseError. Packages use package=P1; dims=40x30x15 with the same line rules (duplicate package ids are an error).

Bank order

LockerNetwork keeps banks nearest first; banks at the same distance are ordered by bank id (string comparison).

Assigning a locker

LockerNetwork::assign(package) returns the compartment id, or nothing:

  1. If the package is already in a compartment (a retried drop-off), return that compartment and change nothing.
  2. Find the package's smallest fitting size. If it fits no size, return nothing.
  3. Starting with that size, look for a free compartment of exactly that size in each bank in bank order (nearest first), and within a bank in compartment-number order. All banks are tried for one size before moving to the next larger size.
  4. If no compartment of that size is free anywhere, try the next larger size the same way (S → M → L).
  5. When a compartment is found, it now holds the package (it's no longer free) and lockerOf(package) returns it. If nothing is free, return nothing and change nothing.

release(packageId) frees the package's compartment and returns true; it returns false if the package isn't in a compartment (including one already released). freeCount(size) counts free compartments of that size across all banks.

Pickup codes

  • PickupCodes(seed) issues 6-digit codes ("004821") from a seeded generator, so the same seed gives the same sequence of codes.
  • issue(packageId) gives a fresh code and replaces any earlier unredeemed code for that package.
  • redeem(packageId, code) is true only when code is exactly the package's current code: same digits, same length. A shorter, longer or empty code is rejected. A successful redeem uses the code up: redeeming it again is false. A failed attempt leaves the code valid.

Project structure

include/
  util.h            ParseError, trim / toUpper / split, whole-number parsing
  dimensions.h      Dimensions, orientation-free fit check, LxWxH parsing
  locker.h          Size, compartment interiors, Locker, Bank, Package
  manifest.h        bank manifest and package list parsers
  network.h         smallestFit, LockerNetwork (assign / release / counts)
  pickup_codes.h    one-time pickup codes
src/                implementations of the above
tests/              unit tests (testlib.h is the test framework, runner.cpp the entry point)

Your task

  1. Implement LockerNetwork::assign in src/network.cpp exactly as described in "Assigning a locker". Its tests are in tests/test_network.cpp.
  2. Fix the defects that stop the project from building or the tests from passing. QA has reported:
    • The project no longer builds.
    • Some packages are put into compartments they physically can't fit in.
    • A customer opened a locker by typing only part of their pickup code.
  • Do not modify files in tests/.
  • Keep your changes minimal. Fix the defects; don't rewrite modules.
  • Additional hidden tests check the behaviour described in this README.