Formally verifying Advent of Code using Dijkstra's program construction
8 days ago
- #programming
- #algorithms
- #formal-methods
- The article discusses solving Advent of Code Day 3 using structured programming principles inspired by Edsger W. Dijkstra.
- It explains the use of quantified notation for array operations and reduction, similar to functional programming concepts.
- The post-condition for the problem is defined, focusing on finding the maximum concatenated joltage from two batteries in an array.
- A domain model is built with theorems and definitions to support the program construction.
- The program loop is designed with invariants, a variant, and a guard to ensure correctness.
- The solution is translated from Guarded Command Language (GCL) to Gleam, a functional programming language.
- Part 2 of the problem is approached differently due to complexity, opting for a straightforward solution.
- The author reflects on the process, highlighting the rigor and proof-based approach of program construction.
- A shout-out is given to the instructor, Henry McLoughlin, for teaching Program Construction with enthusiasm.