Skip to content
K-d Tree Explorer, home
All decision records

DR-001Accepteddecided 2026-10-09

Rebuild the lost program from its surviving outputs, and label what is certain and what is inferred

docs/decisions/DR-001-rebuilding-from-outputs.md

Context

The C source of my 2020 COMP20003 Assignment 2 is gone. The private GitHub repository was deleted, and the Google Drive copy of its .git folder lost the two objects that held the code and the specification. What survived is the test kit (the CLUE 2018 data in five insertion orders and five random subsets), one saved Stage 1 output (coursework/testing-files/result/test1.txt, five queries, 150 records, 57,807 bytes) and my own experiment numbers (result1.csv for Stage 1 and result2.csv for Stage 2, 13 query points each, with the Stage 2 radii not saved).

A portfolio site that says "here is my 2020 program" would be claiming something I cannot show. A site that only shows the data would not show the algorithm at all.

Decision

Rebuild the program in C99 from the evidence, test the rebuild against every surviving output that it should reproduce, and say plainly which design choices the evidence pins down and which ones I inferred. The rebuild lives in coursework/rebuild-2026/, apart from the original files, and the site calls it a rebuild everywhere.

The choices fall into three groups.

Pinned down by the evidence (the rebuild would fail a test without them):

  • The output format. map1 must regenerate result/test1.txt byte for byte: the query echoed as typed, every field as Name: value || , a trailing space, LF endings and a blank line between queries.
  • One node per location, with the businesses at that location kept in file order. The saved output lists 7, 43, 1, 88 and 11 businesses per answer in exactly the order of CLUEdata2018_original.csv.
  • The key and the axis order. Depth 0 splits on x (longitude). Inserted with x first, the kit's median-first file builds a perfectly balanced tree of 13 levels. With y first, the same file builds a 43-level tree, so the person who made that file split on x first.

Consistent with the evidence, but not proven by it:

  • Strictly smaller keys go left and equal keys go right. This keeps the median-first file balanced, but in that file's full-precision keys only 48 of the 4,181 locations share an x value with another location, so the evidence is thin. (DR-002 has the details.)
  • Euclidean distance in raw degrees. The 13 recorded query points get the same nearest location whether distance is measured in degrees or in metres on the Earth's surface, so the surviving outputs cannot tell the two apart. The two rules disagree on 339 of 2,000 seeded random points in the city (17.0%, Wilson 95% CI 15.4% to 18.7%), so the choice matters in general.
  • Stage 2 as an inclusive radius search that prints NOTFOUND when nothing is inside. result2.csv shows a second, much wider search per query, but no Stage 2 output survives.

Not recoverable:

  • The rule my 2020 program used to count comparisons. For the balanced tree it reported 34 to 82 comparisons for query points that sit on a business, where any search that stops at an exact match needs about 12. No counting rule I tried reproduced more than a couple of the 65 recorded numbers. The rebuild counts one comparison per node whose key is compared with the query, and the site shows the 2020 numbers next to the rebuilt ones instead of pretending they agree.

Options considered

  1. Present the rebuild as the original. Rejected. It would be untrue, and the comparison counts would expose it.
  2. Rebuild from memory and the textbook, without tests against the outputs. Rejected. Nothing would show that the rebuild behaves like the 2020 program where it matters.
  3. Rebuild from the evidence, test it against the outputs, and label each choice. Chosen.
  4. Show only the data and the 2020 numbers. Rejected. It would leave out the algorithm, which is the point of the assignment.

Why

The saved output is strong evidence for anything that changes bytes, and weak evidence for anything that does not. Sorting the choices by how well they are supported tells a reader exactly how far to trust each part of the rebuild, and it keeps the original files as the only source of 2020 results.

What happened

  • make test in coursework/rebuild-2026 regenerates result/test1.txt byte for byte and runs 82 regression checks across the whole kit.
  • The TypeScript port in web/src/lib/ matches the compiled C program on all 40 runs of the parity fixture (10 data files, 4 query sets): 2,320 of 2,320 comparison counts and 40 of 40 output files. Even this many agreeing cases only bound the mismatch rate below about 0.17% (Wilson 95% CI 99.8% to 100% for the counts), and only for queries like the ones tested.
  • The 2020 comparison counts are still unexplained. The rebuild's counts are lower for every order, and only one 2020 finding carries over: sorted by x was the most expensive order.
  • web/src/lib/rebuild-evidence.test.ts recomputes the evidence quoted in this record (the 43-level tree with y first, the 13 agreeing queries and the 339 disagreeing points), so the record cannot drift from the data.

What I'd change

Keep build outputs and a copy of the source outside the repository from the start. A single tarball of the 2020 folder would have made this record unnecessary. If I find another 2020 output file (a Stage 2 output, or a run with printed comparison counts), I will test the inferred choices against it and supersede this record with what it shows.