The Lowest Level PL
4 days ago
- #combinatorics
- #inclusion-exclusion
- #programming-languages
- Problem statement: Placing six colored cubes (two red, two green, two blue) into nine labeled holes with the constraint that no two adjacent cubes are of the same color.
- Mathematical approach: Uses inclusion-exclusion principle to count valid arrangements, calculating total permutations and subtracting invalid ones.
- Total arrangements without restrictions: 7,560.
- Subtracting arrangements with adjacent same colors: 5,040 for one color, adding back overlaps: 1,260 for two colors, and subtracting again: 120 for all three colors.
- Final count of valid arrangements: 3,660.
- Implementation in Lean: Defines color types and counts, uses recursive function to build valid sequences, and prints solutions.
- Implementation in Haskell: Similar to Lean, with data types for colors and counts, recursive building of sequences, and printing.
- Implementation in Rust: Uses enums for colors, struct for counts, and backtracking to generate valid sequences, then prints them.