bitwick

The dragons are just indices.

‹ back to the board

Wednesday, September 23

Adeptalgorithms & data structures

The Banner of the Stonemasons' Guild

# The Banner of the Stonemasons' Guild

The north wall of the guild hall in bitwick was raised by stacking cubic stone blocks into a row of columns, left to right. Every block is one unit wide and one unit tall, so column i is a tower of heights[i] blocks. Some columns were never built at all and stand at height zero.

For the midwinter fair the guild wants to hang a single rectangular banner flat against the wall, and the banner may cover nothing but stone.

heights is an array (Python: list) of non-negative integers, possibly empty. A banner covers a contiguous run of one or more columns; its width is the number of columns in that run, and its height may be any whole number that does not exceed the shortest column in the run. Its area is width times height.

Write bannerArea(heights), which returns the largest area any single banner can have, as an integer. If the wall has no columns, return 0.

  • stacks and queues
  • Adept

examples

  1. case 1heights of 2, 1, 5, 6, 2, 310 — the run of the two columns 5 and 6 allows a banner 2 wide and 5 tall
  2. case 2heights of 4, 4, 412 — all three columns, 3 wide and 4 tall
  3. case 3heights of 3, 0, 33 — any run containing the empty column has a shortest column of 0, so the best banner is one column wide and 3 tall
  4. case 4heights of an empty wall0
reward
320 XP
signature
bannerArea
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • the midwinter wall
  • no wall at all
  • a lone column
  • a level course
  • a gap in the stone
  • bare ground
  • the sagging middle
  • the ridged wall
  • the mason's staircase
  • the long descent
The Banner of the Stonemasons' Guild · bitwick