On 29/03/2015 11:35, Steven D'Aprano wrote:
That's why I can't help but feel that, *given the description we've seen*,
perhaps Bart's brute force code doesn't actually solve the problem, and
that's why it is so fast. I'm reminded of the recent thread where somebody
claimed to have a significant speed-up over Timsort by using a binary
search instead of linear search. Tim Peters investigated, and noticed that
the code wasn't actually sorting. It's easy to beat the performance of any
sort algorithm if you don't actually sort...
Anyway, we don't really know where the confusion lies. Perhaps the
description is misleading, or I'm just confused, or Bart's idea of brute
force is not the same as my idea of brute force, or perhaps he really is a
super-genius who has casually relegated C to the dust bin of historic
languages...
My solver definitely works, as the solutions produced by the two
algorithms are identical.
I'm not clever enough to produce a properly analytical solver, but
perhaps it is not quite as brute force as the Python one.
I've looked at my code and I don't really understand it (it's from a
long time ago), and it would take quite a while to convert it to Python
and post it. (Most of it seems to be preoccupied with multiple ways of
indexing the board or grid.)
(If it's of any interest, this non-Python code is here:
http://pastebin.com/5cXd2Pef )
--
Bartc
--
https://mail.python.org/mailman/listinfo/python-list
