Solving Problems with Automata
summary
Finite automata solve concrete puzzles here: using Clojure libraries automat and reduce-fsm a maximal non‑segment sum becomes an O(n) one‑pass algorithm by tracking per‑state best sums and collapsing dominated branches, not brute force. Constraint solving with loco enforces a regular constraint over finite‑domain vars to produce a 7‑nurse 10‑day schedule (3 day, 2 night per day, no >3 workdays or 3 nights in a row) and to fill a 5x5 crossword; large dictionary automaton builds in ~6.8s and solves in ~7.6s.
AI-written summary · about
chapters (27)
- 0:00Intro
- 1:01Finite State Machines
- 2:06Puzzles
- 2:37The maximal segment problem
- 3:53Brute force approach
- 4:50Bitmasks
- 5:19Regular Expressions
- 6:36Automata Library
- 7:23Advanced Function
- 9:27NonSegmented Mask Prefix
- 9:52Cartesian Product Function
- 10:38Can we do better
- 17:14Big Ideas
- 18:34Constraint Programming
- 19:31Finite Domain Integer Variables
- 21:20Propagators
- 21:58Propagators Example
- 23:52Loco Trick
- 24:34Fusion
- 24:54Regular Constraint
- 25:55Transition Table
- 26:16Scheduling
- 30:05Scheduling Diagram
- 31:15Crossword Puzzle
- 34:40Dictionary Automata
- 36:08Code Demo
- 37:12Takeaways
related talks
38mA Clash Course in Solving Sudoku (Functional Pearl)
34mFinite State Machines for Functional Software Machinery
33mOptimising your code with math
32mFunctional Programming Over Sets with Atoms
54mExperiments in Reasoning -
33mAll I needed for FP I learned in High School Algebra
01h 02mSolving Problems the Clojure Way
38mFun with Functional Programming in Clojure