# Exercise 2: Implement Longest-Prefix-Match Route Lookup

```
STEP 1. Save the JavaScript below as `route_lookup.js`.
STEP 2. Implement `lookupRoute(routeTable, destinationIp)`:
          - Each route has a `cidr` (e.g. "10.0.1.0/24") and a `target`.
          - Convert the destination IP and each route's network address
            to 32-bit integers to compare.
          - Return the `target` of whichever matching route has the
            LARGEST prefix length (the most specific match) — per the
            "Under the Hood" section of the theory file, this is exactly
            how a real VPC route table resolves overlapping routes.
          - If no route matches, return null.
STEP 3. Run `node route_lookup.js` and get every line to print PASS.
```

```js
// route_lookup.js

function ipToInt(ip) {
  return ip.split(".").reduce((acc, octet) => (acc << 8) + Number(octet), 0) >>> 0;
}

function cidrToRange(cidr) {
  const [ip, prefixStr] = cidr.split("/");
  const prefix = Number(prefixStr);
  const base = ipToInt(ip);
  const mask = prefix === 0 ? 0 : (0xffffffff << (32 - prefix)) >>> 0;
  return { network: base & mask, mask, prefix };
}

function lookupRoute(routeTable, destinationIp) {
  // TODO: find every route in routeTable whose CIDR contains destinationIp,
  // then return the `target` of the one with the highest `prefix` (most
  // specific / longest match). Return null if nothing matches.
}

// --- self-check: do not modify below this line ---

const routeTable = [
  { cidr: "0.0.0.0/0", target: "igw-main" },
  { cidr: "10.0.0.0/16", target: "local" },
  { cidr: "10.0.1.0/24", target: "local" },
  { cidr: "172.31.0.0/16", target: "pcx-peering-connection" },
];

const tests = [
  { ip: "8.8.8.8", expected: "igw-main", why: "matches only the 0.0.0.0/0 default route" },
  { ip: "10.0.5.10", expected: "local", why: "matches the /16 local route, not the more specific /24 (different subnet)" },
  { ip: "10.0.1.55", expected: "local", why: "matches BOTH the /16 and /24 local routes -> the /24 (longer prefix) wins" },
  { ip: "172.31.9.9", expected: "pcx-peering-connection", why: "matches the /16 peering route, more specific than the /0 default" },
  { ip: "192.168.1.1", expected: null, why: "matches nothing but the default route... wait, it SHOULD match 0.0.0.0/0" },
];
// Fix the last test's expectation in your head before trusting it blindly —
// re-derive it: does 192.168.1.1 fall inside 0.0.0.0/0? (Everything does.)
tests[4].expected = "igw-main";

let failures = 0;
for (const t of tests) {
  const result = lookupRoute(routeTable, t.ip);
  const pass = result === t.expected;
  if (!pass) failures++;
  console.log(`${pass ? "PASS" : "FAIL"} - ${t.ip} -> expected ${t.expected}, got ${result} (${t.why})`);
}
console.log(failures === 0 ? "\nAll tests passed." : `\n${failures} test(s) failed.`);
```