Short accounts make long friends

Puzzles
#1

Bonjour,
je n’ai trouvé aucun post sur ce puzzle, c’est pourquoi je crée celui-ci.
je bloque sur ce puzzle. Mon code est trop lent/long. Je combine tous les nombres avec toutes les opérations (méthode un peu brute-force). Je me doutais bien que cela allait coincer comme ça.
Quelqu’un peut-il m’indiquer une autre piste de résolution ?
Merci.

Hello,
I did not find any post on this puzzle, that is why I create this one.
I block on this puzzle. My code is too slow / long. I combine all the numbers with all the operations (a little brute-force method). I suspected that it would get stuck like this.
Can someone point me to another resolution lead?
Thank you.

1 Like
#2

For any subset X of {a,b,c,d,e,f}, let S(X) be the set of all the values that can be reached using numbers from X. Find a way to compute S recursively – while memoizing the already computed values – to build an efficient enough dynamic programming approach.

2 Likes
#3

It’s that kind of answer i was awaiting for. I don’t ask for “the” solution (no interest).
Thank you for this new approach. I’ll try it.
thanks again.

edit: but your approach also need to compute all that is possible from 6 numbers and 5 operators. Why should it be faster ?

#4

@Zener Because with this approach you will structure the computation in such a way that you won’t do the same calculations too many times while, with your approach, one can guess that you’re doing the same calculations lots of times.

1 Like
#5

I also have tried brute-force, and it took like 40 minutes to calc all possible equations.
@Niako, now I am going to rewrite my code according with your suggestion.

#6

Ahh, finally submitted! Less then a quarter of second.
The hardest problem, and I’ve learned a lot. Thank you, @Niako!

1 Like
#7

@MooMooN, all cases go through but i only get 83% when i submit my solution. I’ve been tested my code with many other combination of numbers and it always works. It blocks on validator 5. Do you have any idea why ?

#8

Validator 5 has nothing special so I did the puzzle to see what could go wrong.

I partition a set s into 2 subsets and find the results recursively on each subset, so basically it looks like this:

for s1, s2 in partition(s):
_for a in results(s1):
__for b in results(s2):
___consider all possible results

I could reproduce your error when I don’t add a alone and b alone in all possible results

3 Likes