davide.guerri
BAN USERI think one of the following can be used:
en.wikipedia.org/wiki/Simplex_algorithm (constraints relaxation is need for this one) or, probably better: en.wikipedia.org/wiki/Branch_and_bound
Being both optimisation methodologies, they will try to maximise (optimise) the problem.
This means a solution is found if (and only if) this maximum equals the sum of the array content (as stated by Naren above).
Some of the needed constraints are stated in my previous comment.
Using regex (python)
import re
def check_dict(dictionary, word):
regex = '^(' + '|'.join(dictionary) + ')+$'
return re.match(regex, word) != None
Nice solution (came up with a very similar one myself).
But it won't work for a corner case:
f('', words) != False
Also the substring comparison function is startswith() (not beginswith())
def check_dict(dictionary, word):
for w in dictionary:
if word.startswith(w):
if len(w) == len(word):
return True
else:
return check_dict(dictionary, word[len(w):])
return False
Very nice.
I think we need to add some constraint:
Assuming A1, A2 and A3 natural numbers.
A1 != A2
A1 != A3
A2 != A2
A1 + 2 != A2 + 3
A1 + 2 != A3 + 4
A2 + 3 != A3 + 4
A1 + 2 <= 6 (i.e. A1 < 5)
A2 + 3 <= 6 (i.e. A2 < 4)
A3 + 4 <= 6 (i.e. A3 < 3)
A1 + A2 + A3 = 6
In some way this problem reminds me of the Knapsack problem...
- davide.guerri November 16, 2014This is still a back tracking solution...
- davide.guerri November 15, 2014We already know that a backtracking algorithm exists.
The point here is to demonstrate whether a different algorithm exists or not.
We could either write an algorithm that solve the problem (for an arbitrary N) or try to reduce this to a well-known problem for which doesn't exist (or exist) a solution that doesn't use BT.
This could help: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
Hi Matoy,
- davide.guerri January 26, 2015if the above methods work (and I think they need more attention), it is true that we have just turned the problem in an equivalent one. We did that on purpose, actually, because with the initial problem it is straightforward to use a backtracking algorithm but (at least for me) it is not easy to find a different algorithm.
Turning a problem in a equivalent one doesn't change its _complexity_, of course.
But, _complexity_ and _type_ of algorithm used are two different things. Many _algorithm_ could exist for a given problem, each with the same _complexity_.
Specifically, _if_ the simplex method can be used, we will be able to solve the problem with one of its implementation (which are not backtracking).
_If_ the branch and bound algorithm can be used, we can use alpha–beta pruning which again is different from backtracking.
So no, no Turing prize this year, unfortunately! :P