‹ back to the board

Wednesday, November 4

Adeptalgorithms & data structures

The Frost-Ledges of Skarnholt Glacier

A seam of ice ledges runs across the face of Skarnholt Glacier. The Lodge of Highland Surveyors pays a bounty for every ledge a climber plants a flag on during a single traverse.

The ledges are given west to east in heights, a list of integers. Each integer is one ledge's height in fathoms. Heights may be negative, and the list may be empty.

A traverse is built as follows:

  • The climber chooses any subset of the ledges and visits them in their listed order. Any number of ledges may be skipped.
  • Each chosen ledge must be strictly higher than the chosen ledge before it.

Write longestAscent(heights). It returns an integer: the largest number of ledges that a single valid traverse can include. An empty list returns 0.

  • dynamic programming
  • Adept

examples

  1. case 1heights of [3, 1, 4, 1, 5, 9, 2, 6]4 (for example the ledges at 1, 4, 5, 9)
  2. case 2heights of [5, 5, 5, 5]1 (equal heights cannot follow one another)
  3. case 3heights of []0
reward
320 XP
signature
longestAscent
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…
  • mixed heights
  • empty glacier
  • single ledge
  • all equal heights
  • strictly descending
  • strictly ascending
  • classic scatter
  • interleaved sequence
  • paired duplicates
  • negative heights
  • late better start
The Frost-Ledges of Skarnholt Glacier · bitwick