bitwick

The dragons are just indices.

‹ back to the board

Sunday, September 13

Adeptalgorithms & data structures

The Banner on the Battlements

# The Banner on the Battlements

The north wall of bitwick is built from panels set side by side. Every panel is one pace wide and some whole number of paces tall, and the tops are ragged: the masons used whatever stone came up the road.

The banner-maker has cloth enough for a rectangle of any size, but the banner must hang flat against the wall. It covers one run of neighbouring panels, and no part of it may rise above the top of any panel it covers.

heights is a list of non-negative integers: the heights of the panels, in left-to-right order.

Write widestBanner(heights), which returns the largest area of such a rectangle as an integer — that is, the maximum of (j - i + 1) * min(heights[i..j]) over all contiguous ranges of panels i <= j. Return 0 if heights is empty.

  • stacks and queues
  • Adept
  • efficiency bonus

examples

  1. case 1heights of 2, 1, 5, 6, 2, 310 — the panels of height 5 and 6 carry a rectangle 2 wide and 5 tall
  2. case 2heights of 3, 0, 33 — the ground-level gap in the middle blocks anything wider than one panel, so a single panel of height 3 is the best there is
  3. case 3heights of 2, 1, 23 — all three panels together at height 1 beat either tall panel alone
  4. case 4an empty list of heights0
reward
350 XP
signature
widestBanner
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 ragged six
  • a wall of one panel
  • no wall at all
  • a gap down to the ground
  • the narrow valley
  • six level courses
  • a sawtooth stretch
  • the long sloping rampart
The Banner on the Battlements · bitwick