A Crime on Logic Island - Proposed New Problem
Back to General discussions forum
This is intended to be an amusing little problem which is not too difficult.
Clive, thank you for you care not to leave us without some curious puzzle for long :) This one seems inspiring - it is online now (I'll be back at it in some minutes to add minor text outlining etc)
oh, so we are doing profiling now? /j
I had initially intended to go for that sort of size. Unfortunately, as you have probably discovered, a purely random choice of parameters rarely results in a unique solution. I had to keep the size small to allow the checker to try a large number of possibilities before getting one which works.
I like the way that you got the 777777 in.
Despite feeling some joy for being able to solve the puzzle, I also feel a kind of loss because it allows simpler approach than I imagined when just reading the story. Perhaps we may some day have and "advanced" version?
I had to keep the size small to allow the checker to try a large number of possibilities
we may try one of the handful of approaches
- either precalculate a good heap of suitable inputs and simply make generator pick one from the list
- or allow non-unique solutions
- at last, we can try whimsically generated inputs (rather than based on LCG)
in two first cases we seemingly would like to utilize the feature which calls the generator-checker code again to verify solution; in the third we'll need to use the recent feature when generator code is executed on server along with the submitted solution to feed input to it (main drawback being in this case the problem only can be solved in a number of mainstream languages supported by the "sandbox" server). surely I'll be glad to help with any of these variants if any of them looks promising
Option 1 would work well - I have used it before to speed up the problem generation.
For this particular problem, bruteforce O(n^2) solutions are sufficient for smaller problem sizes,
but for larger n it's better to think about a more efficient approach.
And as I've hinted earlier, there are parallels to Throwing Easter Eggs
(and that's where my preference for 777_777 came from ;)).
When I ended up with a problem which was easier to solve than I had originally intended, I wasn't particularly disappointed because I realised that more people would be able to have the satisfaction of solving it. I try to set easier problems from time to time because I don't want people to get the impression that all of my problems are impossibly hard. That would result in them not bothering to read any of the subsequent problems and possibly missing out on something that they could solve. Even with the harder problems, where it is possible to use multiple sets of test data, I always ensure that less efficient methods of solution will be able to solve the earlier sets of test data. This in itself should provide some satisfaction and hopefully might spur the solver on to finding a more efficient solution.
Clearly there is some demand for the Advanced version of the problem so it should be in place fairly soon.
Thank you, Clive! As of having two versions of a puzzle - I completely agree (clever marketing!) Additionally this has more "educative" effect - as more people solve the easier version and become aware of the difficulty arising from the non-linear complexity of the algorithm!
The advanced version you presented is now online - so, well, time to think hard for some of us :)
Danke! almost forgotten of existence of this feature. looks like working.
UPD: I'm glad to find quick solution, but I also noticed that running time for slow solution on the "advanced" version
could be about 1 hour. If it is preferable to avoid such "lazy" approach, we can add time limit (say, 10 or 15 minutes).
And yep, immediately after the first hint of the Easter Eggs I recollected vaguely what idea those problems by Mathias are based upon and probably it turned the flow of my thought in suitable direction, thanks :) Truly it is good now to review that Bunnies' puzzles!