Skip to Content
Read

Optionals instead of sentinels

?Int, None, ??, max= and min=, and a BFS without INF.

"No answer" is usually encoded as -1, INF or 1e18, and then the sentinel leaks: INF + w overflows, -1 wins a max, 1e18 gets printed. In CP Lang "no value" is part of the type.

?Int is an Int or nothing. Nothing is written None; a value is Some(x).

Output
Press Run (Ctrl+Enter).

This prints the largest even number, or -1 if there is none. Two operators did the work.

best max= x means best = max(best, x), and None loses to everything, so the first even number simply replaces it. min= works the same way. There is no "is this the first one?" branch and no -INF to pick.

best ?? -1 is "the value, or -1 if there is none". The -1 appears once, at the output, which is the only place the statement mentions it.

Getting the value out

You cannot use a ?Int as an Int by accident; best + 1 on a ?Int stays a ?Int. To get the number out you say what happens when it is missing:

Output
Press Run (Ctrl+Enter).
  • x ?? d: the value, or d.
  • if let x = e: runs the block only when there is a value, and names it.
  • e!: "I know it's there". If it isn't, the run traps and says so: `!` on `none`: there is no value here.

Arrays of optionals

var dist: [V]?Int = None is the usual "distance, if reached" array. dist[v] == None is "not visited", so there is no separate visited array and no INF. Shortest paths in the library return exactly this shape. An optional costs no extra memory in the common cases: the compiler stores None in a value the range can't take.

dist[v] min= d is the relaxation step, and it is also a condition that is true when the value improved. That is the whole of a BFS:

Output
Press Run (Ctrl+Enter).

Vertex 5 is not connected to anything, so its distance stays None and prints as -1. dist[u]! is safe here because every vertex in the queue has a distance.

Problem: Second place

You are given n scores (1 ≤ n ≤ 2·10⁵, each from 1 to 10⁹). Print the largest score strictly below the maximum, or -1 if every score is the same. For 3 1 4 1 5 the answer is 4.

6 tests · Ctrl+Enter

More like this: Leaderboard. The next chapters are being written; until then, continue with the tour.

On this page