Counting shapes with a hash map

Geometry that is really Unit 1: fix one thing, look up what the others would have to be.

Why it works

Fix the diagonal, and the other corners are determined

Take the query point and any other point that could be its diagonal opposite. For an axis-aligned square that means the two differ in both coordinates by the same non-zero amount.

Once those two corners are fixed, the other two are completely determined: they are the combinations of the two x values with the two y values. So the count contributed is the product of how many points sit at each of those two positions.

No searching, no geometry beyond that observation. The rest is bookkeeping.

Below, one query point is tested against three candidates, and for the one that qualifies the other two corners are read straight off the coordinates.

1query = (1, 1)2qx, qy = query3 4for candidate in [(3, 3), (3, 1), (1, 1)]:5    px, py = candidate6    diagonal = abs(px - qx) == abs(py - qy) and px != qx7    if diagonal:8        print(candidate, "is a diagonal partner; the other corners must be",9              (px, qy), "and", (qx, py))10    else:11        print(candidate, "is not a diagonal partner")

The query point matches itself on the distance test, which is why the second condition is needed.

Predict the output· 5 min

Predict the output: counting points that sit on top of each other

Three corners of a square are fixed, and one of them has two points at the same position. Type the two lines it prints.

Python

1from collections import Counter2 3points = Counter([(1, 1), (1, 3), (3, 1), (3, 3), (3, 3)])4 5print("points at each corner:", [points[(1, 3)], points[(3, 1)], points[(3, 3)]])6print("squares with (1,1) as one corner:", points[(1, 3)] * points[(3, 1)] * points[(3, 3)])

Printed output

Problem· 30 min

Detect Squares

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1query = (1, 1)2qx, qy = query3 4for candidate in [(3, 3), (3, 1), (1, 1)]:5 px, py = candidate6 diagonal = abs(px - qx) == abs(py - qy) and px != qx7 if diagonal:8 print(candidate, "is a diagonal partner; the other corners must be",9 (px, qy), "and", (qx, py))10 else:11 print(candidate, "is not a diagonal partner")

1from collections import Counter2 3points = Counter([(1, 1), (1, 3), (3, 1), (3, 3), (3, 3)])4 5print("points at each corner:", [points[(1, 3)], points[(3, 1)], points[(3, 3)]])6print("squares with (1,1) as one corner:", points[(1, 3)] * points[(3, 1)] * points[(3, 3)])