I have a puzzle game which I am not sure how to prove that I have the right answer. I am sure that a code can be written to get all the possible solutions and find the best one from them. However, I am not sure what logic this code should follow. I managed to write a code which can follow my logic, but it does not try all options and therefor maybe a better option exists

The Puzzle is the following:

We have a wizard which makes very special jewelry. However, because they are so special there are some rules that he should follow when creating them.

He has 30 types of beads and unlimited count from each type. Every bead has different color but for simplicity lets name them (B1, B2, B3, B4 … B30 because this is not important). The important part is that every bead type costs different amount of gold coins

B1 -> 1 gold coin

B2 -> 2 gold coins

B3 -> 3 gold coins

…

B30 -> 30 gold coins

There are three special operations that he can use when creates a jewelry:

- He can buy beads, but every time when he buys a bead he should put it at the end of the jewelry.
For example:

When he starts the jewelry no bead is added, so he can buy for example B4 for 4 gold coins and put it on the first place

After that he can buy another bead, for example B6 for 6 gold coins and he should put it at the end.

Now he has jewelry from B4 – B6

After that he can buy another bead, for example B11 for 11 gold coins and he should put it at the end.

Now he has jewelry from B4 – B6 – B11

The total amount of gold coins that he used for creation of this jewelry is 21

- He is so good that if he has jewelry from some beads he can cast a magic and he can increment all the beads with one. However, this magic costs 2 gold coins.
For example:

If we continue with the jewelry from the previous point B4 – B6 – B11, he can cast this magic and the result will be a new jewelry B5 – B7 – B12. This operation will cost for him 2 gold coins.

If he continue incrementing one more time, the jewelry will become: B6 – B8 – B13. This will cost him 2 gold coins.

From these two steps he spend 4 more gold coins and the total amount of the jewelry at the moment is 25

- The third and the last operation that he can use is to switch position of two adjacent beads. This will cost him 1 gold coin.
For example if we continue with the jewelry from previous step B6 – B8 – B13:

He can change the position of the second and third beads and the new jewelry will become B6 – B13 – B8 and the cost for this operation is 1 gold coin.

Now he can change the position of the second and first beads and the new jewelry will become B13 – B6 – B8 and the cost for this operation is 1 gold coin.

From these two steps he spend 2 more gold coin and the total amount of the jewelry at the moment is 27

The question is what is the smallest amount of gold coins that he should use to create the following jewelry:B18 – B1 – B16 – B19 – B6 – B22 – B14 – B15 – B2 – B12 – B27 – B18 – B11 – B1 – B14 – B9 – B23 – B1

One thing to notice. The start and end bead of the jewelry are not connected. So there is no easy way to swap their positions with one move. You should move through all other beads.

The general approach of solving that I took is:

Instead of starting from 0, I start from the complete jewelry. If I have B1 at last position, I just remove it (this conforms to buy B1 action). If it is not a last position I move it to the last position and then remove it. If I do not have B1, I decrease until I have B1 and repeat all the other steps. If we are left with 2 beads just use them.

`var final = [18, 1, 16, 19, 6, 22, 14, 15, 2, 12, 27, 18, 11, 1, 14, 9, 23, 1]; var totalSum = 0; var resultTable = []; function sum() { return final.reduce((acc, el) => acc + el, 0); } function removeOne(arr, indexOfOne) { if (indexOfOne === arr.length - 1) { totalSum += 1; arr.pop(); resultTable.push({ action: "remove last", arr: arr.toString(), cost: 1, totalCost: totalSum }); } else { var nextOfOne = indexOfOne + 1; var temp = arr[indexOfOne]; arr[indexOfOne] = arr[nextOfOne]; arr[nextOfOne] = temp; totalSum += 1; resultTable.push({ action: "swap", arr: arr.toString(), cost: 1, totalCost: totalSum }); } } function decrementAll(arr) { final = arr.map(el => el - 1); totalSum += 2; resultTable.push({ action: "decrement", arr: arr.toString(), cost: 2, totalCost: totalSum }); } var i = 2; while (sum() > 0) { var indexOfOne = final.lastIndexOf(1); if (final.length === 2) { totalSum += final.pop(); totalSum += final.pop(); resultTable.push({ action: "sell", arr: final.toString(), totalCost: totalSum }); break; } if (indexOfOne !== -1) { removeOne(final, indexOfOne); } else { decrementAll(final); } } console.table(resultTable); `

It can be run here: https://repl.it/@SamAAZZ/wizardjewerly

However, without using a code I managed to get answer 129, 128.

Do you have any idea how can I improve the code to get the right answer. Maybe this involves finding all solutions, but I really do not know how I can make it. A general idea how to approach such kind of tasks is also a good start for me.

Any code in different languages is also OK. I can run it and observe how it works to check logic behind finding all possible solutions. I know how to get all solutions if I have only one operation to test, however here there are three operations for 18 positions and I really do not have idea how to approach this problem

Thanks in advanced