Utter beginner - I don't even know where to start with this simple arithmetic algo

[MrDude1515]

Given an integer, and a small list of other integers, I need to add and subtract integers from the small list to get the first one.

In practice in my program, the target integer is in the range 0-63, and the list is [6,10,15,17]. I can add or subtract any of those as many times as I want to hit my target integer.

I've never written a single algorithm before, so I don't know if I'm even approaching it the right way. My initial thought was to solve a few problems on my own and see if I could find any sort of recursive process that I was following to reach my answer. I didn't make much headway with that.

I'm not looking for someone to just give me the answer - in fact, I'd rather that not happen. I was hoping someone could tell me where to start working on this, since I haven't a clue where to start writing an algorithm.

[nuzzle]

I haven't a clue where to start writing an algorithm.


All numbers you can form from the list numbers can be described as,

n = i*6 + j*10 + k*15 + l*17

where i, j, k, l are integers.

To generate every possible n you can use 4 nested loops with i, j, k, l as loop variables. In the innermost loop you just check whether the current n corresponds to the target integer. If it does the i,j,k and l then tells you how many times the list numbers should be subtracted or added to compose the target integer.

In practice you must put bounds on i,j,k and l and define ranges for them. You can for example let them vary between -10 and 10. This translates into a lot of looping, namely 20*20*20*20 = 160.000 times. And if you increase the ranges the looping soon will continue for days so there's a limit to how large you can allow them to be.

Another problem with ranges is that you may not find the solution because it may lie outside the ranges. Also there may exist an infinite number of solutions. This is because n == i*6 + j*10 + k*15 + l*17 defines a hyperplane in 4-dimensional space and every integral point on that surface is a solution.

Still, with this information you can start coding and find solutions within the ranges.

[MrDude1515]

Thanks, that helped a lot! Turns out (-2,2) is a sufficient range to generate integers -63 through 63. That's good enough that finding the optimal one (maybe I can do it in the -1 to 1 range instead?) isn't an issue for me.