Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @tcooke,validated by @User123,@Add_A_Nickname11 and @xenon97909.
If you have any issues, feel free to ping them.
Interesting problem. But in my opinion the difficulty of this puzzle should be medium, not easy.
1 Like
Thanks for the comment. I thought it was on the more difficult side of Easy for sure. But my solution was less than 50 lines of Python, and took me much less an hour to write, which is my calibration point for separating Easy from Medium. I would also look at “Community Success Rate”, which I would expect to be <50% for a Medium problem in the Easy section. It’s currently on 63%, so I feel the difficulty is appropriate.
While the “Community Success Rate” is a helpful metric, the current sample size is too small to draw definitive conclusions. It would be better to wait until hundreds or even thousands of players have started/finished the puzzle, allowing the rate to stabilise and provide a clearer reflection of its true difficulty.
Interesting puzzle, definitely looks like it could be above easy calibration, but with enough thought, it is simple enough! might just take more time than your average easy to figure out, but once you get the trick, you are good to go!
thanks @tcooke , it was enjoyable!
Good fun puzzle.
A hint for anyone failing first validator only;
Check all possible numbers of blockers are covered.
Ok there must be something I am missing here, how can so many configurations be checked in a reasonable time? Even by taking into account symetries, checking each config validity is not feasible,yet I don’t see how to handle the shape complexity otherwise.
Any hint pls?
You can count independently the number of configurations with 2 valid L-shapes, and then the number of neutral-block configurations.
Additional speedup possibility (I used it in PHP, not sure if really needed): as the grid size is at most 8x8, a valid L-shape location can be represented as a single u64 (bitmap). All valid locations can be pre-generated, then whether 2 L-shapes are overlapping can be checked with a single bitwise and operator.
I definitely struggle with the optimisation. Currently I’m generating a grid with neutral block then testing to place one L and then the second. But it’s obvious that’s quitte a lot of iteration. Biggest problem is to fine a way to simulate a board with 2L without taking that much operation.
As @TBali stated, you could try placing the L blocks first …
the problem statement has a subtle hint, towards the placements ..
if you check carefully, you’ll figure out how to initially place the L pieces, think of 1 piece first, then think of how to check for valid two pieces placements, if you can figure this out, I guarantee you will be able to complete the solution easily !
Ok I got the gist of it.
An actual hint for those like me that tried to go down the optimization rabbit hole : its a probability puzzle
further hint : the only goal to having all Lblocks configurations before blockers is to know how many there are
That said, I have two issues with this puzzle.
First, this hardly fit in the easy category. Building the configurations alone could fit the category. But the puzzle encourages to do far more exploratory work that is beyond the scope of an easy category.
Second, the last test, with its enormous scale, is completely in float precision issues territory. I can get different answers based on my order of operations, so I choose the one that validate the last test, but no order should be better than the others. (I assume this is why I don’t green the last validator, but I can’t prove it 
)
Everything can fit in int64, no need for any floats.
Of course you need to calculate “n over k” a bit cleverly, not by calculating first n! just to divide it by k! and (n-k)! in the next step. The interim result n! is int64 overflow of course.
Python with its “automatic bigint” is bad for such puzzles because it silently ignores such int64 overflows thus does not encourage thinking.