Project Euler 828 - Numbers Challenge

Official link:

Thought Process

My first thought was how to even test if a number can be created from a set of other numbers.

I read this article: which was extremely well explained and allowed me to make an algorithm that could indeed test if a number could be constructed through arithmetic operations.

I will not go through the details as I essentially implemented everything inside the article, but modified for this problem, and added some features which would help me sanity check and debug such as actually showing the sequence which constructs the minimal sum. I give my code below, please read it alongside the article!

However, this was not enough to solve the problem.  Each test took around 40 seconds to 200 seconds, and with 200 tests I wasn't going to wait for that long for the code to finish.

Using the idea above, I reconstructed the whole program into a recursive version. What it does it finds every possible value that can be calculated from a set of numbers, then I run it on every subset of the 6 numbers we are given and test if our goal value is inside. 

In the above code the usage of a mask made it very easy to test if our possible combinations of numbers were disjoint, however in this recursive manner it was not so easy. Instead of a mask, I simply checked if 2 subsets intersected, and if they did, if those numbers were repeated (since otherwise simply checking for empty intersection would eliminate sets which contained 2 of the same number).

I again add my code for the solution of problem, with minor comments. In the end it took 8 seconds to run which is reasonable enough for me!

Interactive Code

Input an integer, which denotes the goal (g)

Input any amount of integers, which denotes the numbers allowed to be used (A)

Code will output all possible constructions of g using the numbers A

Please note: This is the first code which is quite slow for 6 numbers!