Re: Is this program OOP?

On 14/12/2024 09:22, wij wrote:

On Thu, 2024-12-12 at 08:59 +0100, David Brown wrote:

"21 * 33 * 13 * 33 * 33 = 9810801" is a pretty much *optimized* solution.
Depending on the viewpoint (what kind of problem you want to solve),
the puzzle solving algorithm can be from O(1) to O(2^N).
 

"Optimised" would mean, as I see it, as fast as possible within reasonably practical limits.  (And of course it would be unreasonable to simply pre-calculate the answer.)  For a problem like this, there are three kinds of optimisations - algorithmic, choice of language or compute platform, and optimisation of the implementation itself.
I have done none of these, so IMHO my solution is far from optimal.  All I did was split the problem into two parts based on a simple criteria. To me, the split was so obvious that I do not see it as something special - but perhaps it is one of these things that seems obvious once you have thought of it.
Algorithmic optimisation would involve dividing the problem into more parts, probably using a search tree and stack structure of some kind but ensuring that it is all allocated and handled with as little dynamic allocation as possible.
Language and compute platform choice optimisation would certainly result in something other than single-threaded Python.  It might mean Prolog, it might mean C++.  Maybe this can be done on a GPU in CUDA - I don't know such platforms well.  Certainly it would aim to be multi-threaded (at least, for a similar style of problem that is large enough to justify the overheads).  And a key consideration would be cache friendly structures.
And I didn't bother doing any kind of implementation optimisation at all.  There is probably scope for increasing speed by a factor of 5 or so in straightforward Python, more from the use of numpy.  But there's a lot more possibility in C++.

>
Now I just need to translate my code into C++ :-)

 So far from I know, using C++ to beat those numbers you provided from Python
is no trivial task. I estimate the limit is 0.08s (on my PC's speed) if nothing
significantly changed.
 

I don't think it should be hard to do a lot better than the Python code from a fairly direct translation of the Python - lists to std::vector<>, and so on.  Translating into more optimal C++ code would lead to a huge improvement in speed.  I would not expect the results to be measurable with the "time" command without looping the algorithm many times.