The The Warp Tables
Stardate 55160.1 · UES Magnanimous
Briefing
The energy needed for warp factor n is the sum of the energies for n - 1 and n - 2, starting from 2 and 3. Ensign Tannenbaum wrote this down exactly as stated, as a function that calls itself twice, and it is beautiful and correct and for factor 40 it makes four hundred million calls. For factor 80 it would finish after the ship was decommissioned.
The formula is fine. The repetition is the problem: it computes the same small values over and over. Remember them, or build the table from the bottom up in a loop, and factor 80 takes no time at all. ARCHIE will time a medium factor first and only try factor 80 if that was fast, because Commander Raghunathan does not want to explain a frozen console to the Captain again.
Mission objectives
ARCHIE checks all five every time you run diagnostics.
- •Factors 0 and 1 are 2 and 3
- •Small factors match the recurrence
- •Factor 40 is 433,494,437
- •A medium factor is fast (no repeated work)
- •Factor 80 is 99,194,853,094,755,497, if the medium one was fast
Objective
Rewrite warp_energy(n) so it returns the same values as the recurrence
(warp_energy(0) == 2, warp_energy(1) == 3, and each later
value is the sum of the two before it) but without repeating work, so that
warp_energy(80) is instant.
Press Run Diagnostics and I will tell you which objectives you actually met.
Objective
Rewrite warp_energy(n: u32) -> u64 so it returns the same values as
the recurrence (warp_energy(0) == 2, warp_energy(1) == 3, and
each later value is the sum of the two before it) but without repeating work, so that
warp_energy(80) is instant.
Press Run Diagnostics and I will tell you which objectives you actually met.
Ask Commander Raghunathan for a hint
Either build up from the bottom in a loop, keeping the last two values, or cache results in a dictionary or map so each factor is computed once. Python's functools.lru_cache is a one-line version of the second.
Debrief
Factor 80 in a millisecond. Ensign Tannenbaum has asked why the slow version was wrong if it gave the right answer, and Commander Raghunathan has told him it was not wrong, it was late, and that in Engineering those are the same thing. He has written that down. It is the first thing he has written down all season.