Problem 44753. Lights Out 3 - 5x5, 6 moves
Will problem "Lights Out 3 - 5x5, 12 moves" be created?
nchoosek(25, 12) = 5200300, not so big.
It can also be solved by brute-forces.
please merge problem "Lights Out 3 - 5x5, 3 moves", "Lights Out 3 - 5x5, 4 moves" , "Lights Out 3 - 5x5, 6 moves" and "Lights Out 3 - 5x5, N moves"(not publish yet), becase they can be solve by same brute-force method.
@li haitao: I understand that you might not want to see so many problems in the series, but they are purposefully building up to larger, more difficult problems in a pedantic fashion so as to be accessible to a broad range of users.
It is rather curious that you make such comments about being able to solve these problems using brute-force methods without having solved any of them, as far as I can see. I have timed each of the submitted problems for the three problems so far using Cody servers, and they yield the following approximate times:
#1 (3 moves): 1/4 to 1/2 second
#2 (4 moves): 1/2 to 2 seconds
#3 (6 moves): 25 to 30 seconds (this includes a modified solution from a prior problem)
As far as I am aware, the Cody servers time out at 30 seconds, so further problems will not be solvable by brute-force methods. I tested that on a planned problem with more moves using two modified solutions from prior problems, and they do appear to time out. While it is technically possible to solve many of these (current and planned) problems by brute-force methods, it is not practically feasible (or possible on Cody due to server time limits). The number of test cases in future problems generally increases or stays at a high number to help prevent brute-force methods from working.
I added various references to the first problem in the series as potential starting points for developing actual solvers. I would encourage you to check them out and try these first problems without using brute-force methods that will only go so far.
@goc "#3 (6 moves): 25 to 30 seconds"
My brute-force solution runs less than 2 second.
@goc I admit that it's hard to solve "12 moves" less than 30 seconds using brute-force methods in cody's computer(but less than 30 seconds in my computer).
I'm glad to see some elegent methods in the future.
@goc "#3 (6 moves): 25 to 30 seconds" My brute-force solution runs less than 0.8 second.
@li haitao: While your solution does solve many test cases in under 0.8 seconds, the times above were referring to the total time for the whole test suite. When your times are added up for all the test cases, the total time is over 4 seconds. While less than the total time for other solutions, it is still increasing over other problems with fewer moves. Also, as I already mentioned, future problems will tend to have even more test cases, making it harder to solve some within the time limit. And, the final problems will most definitely not be solvable by brute-force methods.
With brute-force Alfonso solution you can solve everything, everywhere, every time...
To be clear, I speak about Solution 1720010 of Alfonso (https://www.mathworks.com/matlabcentral/cody/problems/44755-lights-out-4-5x5-8-moves/solutions/1720010).
Incredible no ?
@Jean-Marie Sainthillier: Amazing. I'll have to make sure that some later problems in the series can't be brute forced, even by him, though he may still find a way. These test suites take long enough to create as it is.
Solution CommentsShow comments
Problem Recent Solvers16
Number of 1s in a binary string
Arrange vector in ascending order
Construct an index vector from two input vectors in vectorized fashion
More from this Author139
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!