Solving a wooden puzzle using Haskell
glocq.github.io
glocq.github.io
orientations = concat [
[
[(0,0,0), (t,0,0), (2*t,0,0), (3*t,0,0), (2*t, a, b)],
[(0,0,0), (0,t,0), (0,2*t,0), (0,3*t,0), (a,2*t,b)],
[(0,0,0), (0,0,t), (0,0,2*t), (0,0,3*t), (a,b,2*t)]
] | (a, b) <- [(1,0), (-1, 0), (0, 1), (0, -1)], t <- [1, -1]]
The 10 paragraph blog post is the “hard” part: explaining to others who don’t have the same base knowledge.
If I read it correctly, they do even less human-powered work than your solution. It just looks hard because the machinery is unfamiliar.
I wonder if I can still find the source code. (Found it! Source code was in French and not very elegant but it works, glorified brute force aka Backtracking).
I'm eager to improve it to find ALL solutions, not just the first one.
It seems you are fluent in Franglais - https://en.wikipedia.org/wiki/Franglais. I have only respect for someone who can flit between languages with that facility.
I wish it was code-switching but the true may be that my english wasn't very good.
I learn yesterday that a French spy DGSE (French NSA) was spotted by the Canadian after exactly this kind of english errors (and other hints like the use of "octet" instead of "byte" and compiled with french local).
I find it fascinating how you slam words together - who cares about "correct"? Is there really a correct way to program in C++, in both French and a nod to English? In the end if it compiles and works - who cares!
Viva la Franglais++
However, I am aware that for some people, it can be annoying when someone else (me in this case) is seemingly lazy or just plain wrong when deploying words.
I used to be somewhat unkind about grammatical errors but let's face it: grammar is what the majority of people say it is and not what is pinned down in a book half-read and quarter-remembered from years ago.
A bit is perhaps the smallest addressable unit of storage (says my light switch) A byte manages to convey 256 different states and I would need eight light switches to store them.
The definition of byte is not a matter of grammar, and here on a forum centered about computing technology and business the distinction that matters not to you matters to many - CHAR_BIT is still part of current standards in important languages and hardware w/out 8-bit bytes is still in current use.
It's "vive", not "viva", in French, and "français" and "anglais" are both masculine, so "franglais" is masculine as well (so it would use "le" as an article).
You'll probably be more likely to hear "viva los Frenchies" from Brits confusing Spanish with French. To us Germanics, you Romantics sound all the same ... or something 8)
I used a poor man's version to solve a puzzle where one arranges polymino pieces on a grid spelling out the date [1]. No pointers, just keeping track of deleted rows and columns in the recursion.
It is not at all obvious that all 366 days can be solved. To my dismay all of them can be solved in multiple ways - as a human I find some days quite tricky.
[1] https://metterklume.github.io/puzzle/2024/12/24/calendar-puz...
Being able to solve starting from various constraints have turned out really useful for building an intuition for the puzzle.
IIRC it kept a list of board states, updated the list of board states by taking each one and applying possible moves, then removed congruencies or any state that did not have a valid next move.
The pattern seems similar to your approach that deals with rotations, though in 3D
```haskell
len :: V3 Int -> Float
len (V3 x y z) = sqrt (x'*x' + y'*y' + z'*z')
where
x' = fromIntegral x :: Float
y' = fromIntegral y :: Float
z' = fromIntegral z :: Float
exclude :: Shape -> Shape -> Bool
exclude [a1, _, _, d1, _] [a2, _, _, d2, _] = len (a2 - a1) < 1.1
&& len (d2 - d1) < 1.1
```
```haskell
conflict :: Shape -> Shape -> [Shape] -> Bool
conflict occs piece oldPieces = any (\voxel -> elem voxel piece) occs ||
any (\o -> exclude o piece) oldPieces
```
```haskell
subsolutionsSmart :: Int -- ^ How many pieces should be in the subsolution we're looking for?
-> Shape -- ^ Unavailable voxels, already occupied by some piece
-> [Shape]
-> [[Shape]]
subsolutionsSmart 0 _ _ = [[]]
subsolutionsSmart n occupiedVoxels oldPieces = do
let freeVoxel = pickFreeVoxel occupiedVoxels
newPiece <- filter
(\piece -> elem freeVoxel piece &&
not (conflict occupiedVoxels piece oldPieces)
)
allValidPieces
let updatedOccupiedVoxels = newPiece <> occupiedVoxels
let updatedOldPieces = (newPiece:oldPieces)
otherPieces <- subsolutionsSmart (n - 1) updatedOccupiedVoxels updatedOldPieces
return $ newPiece : otherPieces
```
```haskell
allSolutionsSmart :: [[Shape]]
allSolutionsSmart = subsolutionsSmart 25 [] []
```