CIDR Subnet Allocator (Go)
Topics: backtracking, constraint satisfaction, networking
Problem
After a series of subnet allocations and reclaims inside a parent CIDR block, the free space is a
set of disjoint ranges of various sizes — a fragmented pool, not one clean contiguous block. Now a
batch of new subnet requests comes in, each asking for at least a certain number of addresses.
Assign each request a free range that's big enough, with no two requests sharing a range, or prove
that's impossible.
type Block struct {
Offset int
Size int
}
type Request struct {
Name string
Size int
}
func AllocateAll(free []Block, requests []Request) (map[string]Block, bool)
free is the pool of available ranges (offset + size) left over after previous splits and
reclaims.- Each
Request needs a block with Size >= Request.Size. The allocation carves out exactly
Request.Size addresses starting at the chosen free block's Offset (a real allocator would
then return the unused remainder to the free pool — out of scope here).
- A free block can satisfy at most one request.
AllocateAll returns a map from request name to the allocated Block and true, or nil, false
if every assignment fails.
free: {0,4}, {4,2}
requests: a wants 2, b wants 4
AllocateAll -> {"a": {4,2}, "b": {0,4}}, true
Key concepts
- Bipartite assignment, not interval splitting. This isn't "split a CIDR block recursively" —
it's "match each request to one of a fixed set of pre-existing free ranges," like assigning jobs
to machines. The search space is which free block goes to which request.
- Why backtracking: in the example above, both free blocks are big enough for
a (size 2). If
the solver greedily gives a the first block it fits ({0,4}), there's nothing left big enough
for b (size 4) — the only block that fits b is gone. The solver must undo that choice and
try {4,2} for a instead, freeing {0,4} for b. This is the same "try a choice, recurse, undo
on dead end" shape as the other backtracking challenges.
- Proving infeasibility: if no combination of distinct free blocks can cover every request
(either because no single block is big enough for some request, or because requests outnumber
blocks that fit), the search must exhaust every assignment before reporting
false.
The Block and Request structs are provided; you implement AllocateAll.
Run
go test -v ./challenges/subnet-allocator/go/
Sign in to submit your solution.