Problem 409815 · medium · Level 04 Non-Linear Data Structures

Cells of a Hexagonal Board

py-dataclasses · py-dunder · py-properties · hashable values

A strategy game is played on a board of hexagons. Each cell has axial coordinates (q, r); a third coordinate s = -q - r is often handy. The six neighbours of a cell are found by adding the directions (1, 0), (1, -1), (0, -1), (-1, 0), (-1, 1) and (0, 1), in this order. The distance between two cells (the number of steps between them) is (|dq| + |dr| + |ds|) / 2, a whole number, where dq, dr and ds are the differences of the three coordinates.

Write a class Hex(q, r) and a function reach(start, blocked, steps):

  • repr(h) is Hex(q=1, r=-2). Cells with equal coordinates are equal and hash equally, so they can be set members and dictionary keys. Cells cannot be changed after they are made: assigning h.q = 5 raises an error.
  • Cells sort by q and then by r, with <, sorted, min and max.
  • h.s is the third coordinate, read without brackets.
  • a + b and a - b add and subtract coordinates, h * k multiplies them by an integer.
  • h.distance(other), h.neighbours() (a list of six cells in the direction order above) and h.ring(radius) (the sorted list of cells at exactly radius steps from h; [h] for radius 0).
  • reach(start, blocked, steps) returns the sorted list of cells that can be reached from start in at most steps moves to a neighbouring cell, never entering a cell of the set blocked (start itself is included).

The setup's walls(radius, density, seed) returns a random set of blocked cells within radius of Hex(0, 0) (never the centre), and raises(fn, *args) returns the name of the exception a call raises (or None).

Examples

Input:  a, b = Hex(1, -2), Hex(-1, 3)
        repr(a + b), a.s, a.distance(b), repr(sorted([b, a, Hex(1, -3)]))
Output: ('Hex(q=0, r=1)', 1, 5, '[Hex(q=-1, r=3), Hex(q=1, r=-3), Hex(q=1, r=-2)]')

Input:  repr(reach(Hex(0, 0), {Hex(1, 0), Hex(0, 1)}, 1)), len({Hex(0, 0), Hex(0, 0), Hex(2, 0) - Hex(2, 0)})
Output: ('[Hex(q=-1, r=0), Hex(q=-1, r=1), Hex(q=0, r=-1), Hex(q=0, r=0), Hex(q=1, r=-1)]', 1)

Constraints

  • Coordinates are integers; 0 <= steps <= 40, 0 <= radius <= 40.

Goals

  • Use a frozen, ordered dataclass as a small value type that can be a set member and a dictionary key
  • Add arithmetic special methods and a computed property to a dataclass
  • Let the value type make a search over the board short and clear
Starting Python…