Wizard creating a jewelry

Question

I have a puzzle game which I am not sure how to prove that I have the right answer.

The Puzzle is the following:

We have a wizard which makes very special jewelry (a straight line with beads). However, because the jewelry is so special there are some rules that he should follow when creating it.

He has 30 types of beads and unlimited count from each type. Every bead has different color but for simplicity lets name them ($B_1$, $B_2$, $B_3$, $B_4$ ... $B_{30}$ because this is not important). The important part is that every bead type costs different amount of gold coins

$$B_1\text{ -> 1 gold coin}$$

$$B_2\text{ -> 2 gold coins}$$

$$B_3\text{ -> 3 gold coins}$$

$$\dots$$

$$B_{30}\text{ -> 30 gold coins}$$

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

1. 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 $B_4$ for $4$ gold coins and put it on the first place

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

  Now he has jewelry from $B_4$ - $B_6$

• After that he can buy another bead, for example $B_{11}$ for $11$ gold coins and he should put it at the end.

  Now he has jewelry from $B_4$ - $B_6$ - $B_{11}$

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

2. 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 $B_4$ - $B_6$ - $B_{11}$, he can cast this magic and the result will be a new jewelry $B_5$ - $B_7$ - $B_{12}$. This operation will cost for him $2$ gold coins.

• If he continue incrementing one more time, the jewelry will become: $B_6$ - $B_8$ - $B_{13}$. 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$

3. 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 $B_6$ - $B_8$ - $B_{13}$:

• He can change the position of the second and third beads and the new jewelry will become $B_6$ - $B_{13}$ - $B_8$ 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 $B_{13}$ - $B_6$ - $B_8$ 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:

$B_{18}$ - $B_1$ - $B_{16}$ - $B_{19}$ - $B_6$ - $B_{22}$ - $B_{14}$ - $B_{15}$ - $B_2$ - $B_{12}$ - $B_{27}$ - $B_{18}$ - $B_{11}$ - $B_1$ - $B_{14}$ - $B_9$ - $B_{23}$ - $B_1$

The beginning and the end of the jewelry are not connected, so you can not directly switch the last with the first bead. One of them should be switched with all the others in order to get to the other.

Computers are allowed. However, I am not sure how to write a program to solve the problem.

The general approach of solving that I took is:

Edit 1: I removed my approach just not to give a possibly wrong direction for solving. The approach that I took is similar to the first answer of the question from @AxiomaticSystem

Edit 2: I replace the word bracelet with jewelry to remove the confusion that the beginning and the end of the jewelry are connected and we can switch their positions. This is not allowed

Answer 1

The minimum cost is 125 (credits to Ben Barden and Zizy Archer), with steps as follows:

Input: 18 1 16 19 6 22 14 15 2 12 27 18 11 1 14 9 23 1
Minimum cost: 125
Step  1:   1  2  5 10  1  6                                     Buy 1 2 5 10 1 6 (cost: 25, total: 25)
Step  2:   3  4  7 12  3  8                                     Increment 2 times (cost: 4, total: 29)
Step  3:   3  4  7 12  3  8  1                                  Buy 1 (cost: 1, total: 30)
Step  4:   3  1  4  7 12  3  8                                  Swap them into place (cost: 5, total: 35)
Step  5:   5  3  6  9 14  5 10                                  Increment 2 times (cost: 4, total: 39)
Step  6:   5  3  6  9 14  5 10  1  2  1                         Buy 1 2 1 (cost: 4, total: 43)
Step  7:   5  3  6  9  1  2 14  5  1 10                         Swap them into place (cost: 7, total: 50)
Step  8:   7  5  8 11  3  4 16  7  3 12                         Increment 2 times (cost: 4, total: 54)
Step  9:   7  5  8 11  3  4 16  7  3 12  1                      Buy 1 (cost: 1, total: 55)
Step 10:   7  5  8 11  3  4  1 16  7  3 12                      Swap them into place (cost: 4, total: 59)
Step 11:   8  6  9 12  4  5  2 17  8  4 13                      Increment 1 times (cost: 2, total: 61)
Step 12:   8  6  9 12  4  5  2 17  8  4 13  1                   Buy 1 (cost: 1, total: 62)
Step 13:   8  6  9 12  4  5  2 17  8  1  4 13                   Swap them into place (cost: 2, total: 64)
Step 14:  10  8 11 14  6  7  4 19 10  3  6 15                   Increment 2 times (cost: 4, total: 68)
Step 15:  10  8 11 14  6  7  4 19 10  3  6 15  1                Buy 1 (cost: 1, total: 69)
Step 16:  10  8 11 14  6  7  4 19 10  3  6  1 15                Swap them into place (cost: 1, total: 70)
Step 17:  13 11 14 17  9 10  7 22 13  6  9  4 18                Increment 3 times (cost: 6, total: 76)
Step 18:  13 11 14 17  9 10  7 22 13  6  9  4 18  1             Buy 1 (cost: 1, total: 77)
Step 19:  13 11 14  1 17  9 10  7 22 13  6  9  4 18             Swap them into place (cost: 10, total: 87)
Step 20:  18 16 19  6 22 14 15 12 27 18 11 14  9 23             Increment 5 times (cost: 10, total: 97)
Step 21:  18 16 19  6 22 14 15 12 27 18 11 14  9 23  1  2  1  1 Buy 1 2 1 1 (cost: 5, total: 102)
Step 22:  18  1 16 19  6 22 14 15  2 12 27 18 11  1 14  9 23  1 Swap them into place (cost: 23, total: 125)

Note that the result is a generalization to the "swap 1, sell, then decrement" backward approach. For this particular question, using "swap 1, sell, then decrement" works. However, it is not necessarily the case, as can be seen in the following example (credits to Ben Barden):

Input: 1 1 1 1 2 2 2 2 34 34 34
Minimum cost: 105
Step 1:   1  1  1                               Buy 1 1 1 (cost: 3, total: 3)
Step 2:  34 34 34                               Increment 33 times (cost: 66, total: 69)
Step 3:  34 34 34  1  1  1  1  2  2  2  2       Buy 1 1 1 1 2 2 2 2 (cost: 12, total: 81)
Step 4:   1  1  1  1  2  2  2  2 34 34 34       Swap them into place (cost: 24, total: 105)

Also another example:

Input: 1 1 1 10 1 3 3 3 5 5 5 10 99 99 99
Minimum cost: 277
Step  1:   1  1  1                                      Buy 1 1 1 (cost: 3, total: 3)
Step  2:  90 90 90                                      Increment 89 times (cost: 178, total: 181)
Step  3:  90 90 90  1                                   Buy 1 (cost: 1, total: 182)
Step  4:   1 90 90 90                                   Swap them into place (cost: 3, total: 185)
Step  5:  10 99 99 99                                   Increment 9 times (cost: 18, total: 203)
Step  6:  10 99 99 99  1  1  1  1  3  3  3  5  5  5 10  Buy 1 1 1 1 3 3 3 5 5 5 10 (cost: 38, total: 241)
Step  7:   1  1  1 10  1  3  3  3  5  5  5 10 99 99 99  Swap them into place (cost: 36, total: 277)

Below is the code (Python 3.7):

# Import statements
import sys
from argparse import ArgumentParser
from itertools import combinations

EXHAUSTIVE = 'exhaustive'
INCREMENTAL = 'incremental'
THRESHOLD = 'threshold'

def format_beads(beads):
    result = ''
    for bead in beads:
        result += f'{bead:#3d}'
    return result

def get_min_cost(beads, final_len, heuristics=INCREMENTAL):
    min_cost = sum(beads)
    if len(beads) > 0:
        min_operations = [f'{{:{3*final_len}s}}\tBuy {" ".join(map(str, beads))} (cost: {min_cost}, total: {min_cost})'.format(format_beads(beads))]
    else:
        min_operations = []

    # If there are only 2 beads, just buy them
    if len(beads) <= 2:
        return min_cost, min_operations

    increment_cost = 0
    increment_operation = None
    low = min(beads)
    if low > 1:
        diff = low-1
        increment_cost += 2*diff
        increment_operation = f'{{:{3*final_len}s}}\tIncrement {diff} times (cost: {2*diff}, total: ###)'.format(format_beads(beads))
        beads = [bead-diff for bead in beads]

    # Now lowest bead is 1, and at least of length 3
    if heuristics == EXHAUSTIVE:
        def generate_partitions():
            for lower_size in range(0, len(beads)):
                candidates = [idx for idx, bead in enumerate(beads) if bead > 1]
                for lower_idx in combinations(candidates, lower_size):
                    lower_idx = set(lower_idx)
                    higher = [bead for (i, bead) in enumerate(beads) if i not in lower_idx and bead != 1]
                    lower =  [(i, bead) for (i, bead) in enumerate(beads) if i in lower_idx or bead == 1]
                    yield (higher, lower)
    elif heuristics == INCREMENTAL:
        def generate_partitions():
            marked_count = 0
            higher = []
            lower = []
            for i, bead in enumerate(beads):
                if bead-1 <= marked_count:
                    lower.append((i, bead))
                    marked_count += 1
                else:
                    higher.append(bead)
            yield (higher, lower)
            yield ([], list(enumerate(beads)))
    else:
        def generate_partitions():
            for threshold in sorted(set(beads)):
                higher = [bead for bead in beads if bead > threshold]
                lower = [(i, bead) for (i, bead) in enumerate(beads) if bead <= threshold]
                yield (higher, lower)

    for higher, lower in generate_partitions():
        num_higher = len(higher)
        cur_cost, cur_operations = get_min_cost(higher, final_len, heuristics)
        buy_cost = 0
        swap_cost = 0
        for cur, (orig, bead) in enumerate(lower):
            buy_cost += bead
            swap_cost += cur + num_higher - orig
        cur_cost += buy_cost
        cur_operations.append(f'{{:{3*final_len}s}}\tBuy {" ".join(map(lambda x:str(x[1]), lower))} (cost: {sum(bead for i, bead in lower)}, total: {cur_cost})'.format(format_beads(higher+[bead for i, bead in lower])))
        if swap_cost > 0:
            cur_cost += swap_cost
            cur_operations.append(f'{{:{3*final_len}s}}\tSwap them into place (cost: {swap_cost}, total: {cur_cost})'.format(format_beads(beads)))
        if cur_cost < min_cost:
            min_cost = cur_cost
            min_operations = cur_operations

    # Since we are working backwards, need to add this increment after all previous operations are added
    if increment_cost:
        min_cost += increment_cost
        min_operations.append(increment_operation.replace('###', str(min_cost)))
    return min_cost, min_operations

def main(args=None):
    default = [18,1,16,19,6,22,14,15,2,12,27,18,11,1,14,9,23,1]
    parser = ArgumentParser(description='')
    parser.add_argument('beads', type=int, nargs='*',
                        help='The list of beads')
    parser.add_argument('--heuristics', choices=['threshold', 'incremental', 'exhaustive'])
    args = parser.parse_args(args)

    beads = args.beads
    if not beads:
        beads = default
    heuristics = args.heuristics

    cost, operations = get_min_cost(beads, final_len=len(beads), heuristics=heuristics)
    print(f'Input: {" ".join(map(str, beads))}')
    print(f'Minimum cost: {cost}')
    for step, operation in enumerate(operations):
        print(f'Step {step+1:2d}: {operation}')

if __name__ == '__main__':
    main()

---

The Idea

The main idea is to split the sequence into two sub-sequences (not necessarily contiguous), put them side-by-side, then work backwards using the standard "swap, sell, decrement" on the first, and use "swap and sell" on the second part. To split the sequence into two sub-sequences, I consider all beads with value <= threshold to be put in the second sub-sequence, and iterate through all possible thresholds. To solve the first part, note that it is exactly the same as the original problem, but with less beads, so we can recursively call on our function here.

I was inspired mostly by Jeremy's answer that seems to do swap of non-1s, even though it turned out that his answer can be converted into a pure swap, sell, and decrement approach, ever buying and swapping only 1's.

---

The Heuristics

Now, we need to define how to split the sequence into the two sub-sequences. In my code, I implemented this in the generate_partitions function, which can be replaced with any heuristics we want.

It turned out that as Ben Barden mentioned, and as in Zizy Archer's answer, the heuristics that results in the optimal partitioning function is to put into the second sub-sequence those numbers which have at least that many numbers to its left (including itself) which are included in the second sub-sequence. See Zizi's answer for more details. So all numbers in 1,1,3 and 1,1,2,4 should be bought directly instead of swapped and incremented.

However, at some point, the cost of swapping out those numbers from the full sequence will outweigh the cost of buying them directly. So we need to consider both cases (use the above heuristics or simply buy everything), taking the minimum.

---

Original answer

I wrote a recursive program to solve this, and got essentially the same answer as Jeremy Dover, even though I didn't specifically try to follow that heuristics (see second example below, as cleverly pointed out by Ben Barden in comments). Note that I still use some heuristics (see explanation at the end).

Here is the output:

Input: 18 1 16 19 6 22 14 15 2 12 27 18 11 1 14 9 23 1
Minimum cost: 125
Step  1:   1  2  5 10  1  6                                     Buy 1 2 5 10 1 6 (cost: 25, total: 25)
Step  2:   3  4  7 12  3  8                                     Increment 2 times (cost: 4, total: 29)
Step  3:   3  4  7 12  3  8  1                                  Buy 1 (cost: 1, total: 30)
Step  4:   3  1  4  7 12  3  8                                  Swap them into place (cost: 5, total: 35)
Step  5:   4  2  5  8 13  4  9                                  Increment 1 times (cost: 2, total: 37)
Step  6:   4  2  5  8 13  4  9  1                               Buy 1 (cost: 1, total: 38)
Step  7:   4  2  5  8  1 13  4  9                               Swap them into place (cost: 3, total: 41)
Step  8:   5  3  6  9  2 14  5 10                               Increment 1 times (cost: 2, total: 43)
Step  9:   5  3  6  9  2 14  5 10  1  1                         Buy 1 1 (cost: 2, total: 45)
Step 10:   5  3  6  9  1  2 14  5  1 10                         Swap them into place (cost: 5, total: 50)
Step 11:   7  5  8 11  3  4 16  7  3 12                         Increment 2 times (cost: 4, total: 54)
Step 12:   7  5  8 11  3  4 16  7  3 12  1                      Buy 1 (cost: 1, total: 55)
Step 13:   7  5  8 11  3  4  1 16  7  3 12                      Swap them into place (cost: 4, total: 59)
Step 14:   8  6  9 12  4  5  2 17  8  4 13                      Increment 1 times (cost: 2, total: 61)
Step 15:   8  6  9 12  4  5  2 17  8  4 13  1                   Buy 1 (cost: 1, total: 62)
Step 16:   8  6  9 12  4  5  2 17  8  1  4 13                   Swap them into place (cost: 2, total: 64)
Step 17:  10  8 11 14  6  7  4 19 10  3  6 15                   Increment 2 times (cost: 4, total: 68)
Step 18:  10  8 11 14  6  7  4 19 10  3  6 15  1                Buy 1 (cost: 1, total: 69)
Step 19:  10  8 11 14  6  7  4 19 10  3  6  1 15                Swap them into place (cost: 1, total: 70)
Step 20:  13 11 14 17  9 10  7 22 13  6  9  4 18                Increment 3 times (cost: 6, total: 76)
Step 21:  13 11 14 17  9 10  7 22 13  6  9  4 18  1             Buy 1 (cost: 1, total: 77)
Step 22:  13 11 14  1 17  9 10  7 22 13  6  9  4 18             Swap them into place (cost: 10, total: 87)
Step 23:  17 15 18  5 21 13 14 11 26 17 10 13  8 22             Increment 4 times (cost: 8, total: 95)
Step 24:  17 15 18  5 21 13 14 11 26 17 10 13  8 22  1          Buy 1 (cost: 1, total: 96)
Step 25:  17 15 18  5 21 13 14  1 11 26 17 10 13  8 22          Swap them into place (cost: 7, total: 103)
Step 26:  18 16 19  6 22 14 15  2 12 27 18 11 14  9 23          Increment 1 times (cost: 2, total: 105)
Step 27:  18 16 19  6 22 14 15  2 12 27 18 11 14  9 23  1  1  1 Buy 1 1 1 (cost: 3, total: 108)
Step 28:  18  1 16 19  6 22 14 15  2 12 27 18 11  1 14  9 23  1 Swap them into place (cost: 17, total: 125)

My original answer uses the heuristics that all numbers below a threshold should be swapped out together. This might not necessarily be the case. For example, using that heuristics on the following we get:

Input: 1 1 1 10 1 3 3 3 5 5 5 10 99 99 99
Minimum cost: 278
Step  1:   1  1  1                                      Buy 1 1 1 (cost: 3, total: 3)
Step  2:  90 90 90                                      Increment 89 times (cost: 178, total: 181)
Step  3:  90 90 90  1  1                                Buy 1 1 (cost: 2, total: 183)
Step  4:   1  1 90 90 90                                Swap them into place (cost: 6, total: 189)
Step  5:  10 10 99 99 99                                Increment 9 times (cost: 18, total: 207)
Step  6:  10 10 99 99 99  1  1  1  1  3  3  3  5  5  5  Buy 1 1 1 1 3 3 3 5 5 5 (cost: 28, total: 235)
Step  7:   1  1  1 10  1  3  3  3  5  5  5 10 99 99 99  Swap them into place (cost: 43, total: 278)

Now, there is actually a better solution with cost 277 (this I obtained by going through all possible sub-sequence with the --remove_heuristics flag, so this should be optimal):

Input: 1 1 1 10 1 3 3 3 5 5 5 10 99 99 99
Minimum cost: 277
Step  1:   1  1  1                                      Buy 1 1 1 (cost: 3, total: 3)
Step  2:  90 90 90                                      Increment 89 times (cost: 178, total: 181)
Step  3:  90 90 90  1                                   Buy 1 (cost: 1, total: 182)
Step  4:   1 90 90 90                                   Swap them into place (cost: 3, total: 185)
Step  5:  10 99 99 99                                   Increment 9 times (cost: 18, total: 203)
Step  6:  10 99 99 99  1  1  1  1  3  3  3  5  5  5 10  Buy 1 1 1 1 3 3 3 5 5 5 10 (cost: 38, total: 241)
Step  7:   1  1  1 10  1  3  3  3  5  5  5 10 99 99 99  Swap them into place (cost: 36, total: 277)

Note that the first 10 was created using increment, while the second 10 is just bought. This is not possible with the heuristics, since both 10's will have to be bought or both incremented using the first heuristics.

Answer 2

Thinking about this a little further. First, @Chronocidal's approach is really the right one...instead of building up to a bracelet, we should start with the result and deconstruct it back. In this construct, swapping stays the same, but incrementing becomes decrementing, and buying becomes selling. If you think about it this way, there are a couple of pretty obvious principles:

1. If you have one bead, sell it. It costs you 2 to decrement it by 1, but you can sell it one for one.
2. If you have more than one bead and none is worth 1, decrement until you get a bead with value 1. At each stage, it costs you 2 to decrement, but you lose at least 2 from the "sell" cost of the necklace.

So this leaves you with the question: what do you do if you have more than one bead, and one or more of them are worth 1? There are some things you should not do:

1. There is no gain in swapping two beads with value both greater than 1. If you need to swap them eventually, you can wait until decrements knock one of them down to value 1, and swap them then for the same cost.
2. This is less obvious, but feels right: you should never move a 1 to the left. My argument in support is basically that while you have a 1 in your bracelet, you can not decrement, so the only way you can make progress is to sell off a bead at the end, or swap all of your 1s to the end, and sell them. Moving a 1 to the left does not further either of these goals.

So the last thing really says it all: while you have a 1, you should either sell a bead from the end, or move a 1 to the right and sell them so you can decrement again. The question is, should you do this greedily at each step, i.e., pick the least costly of these two moves at any given time? Let's give it a try:

$$ \displaystyle \begin{array}{|l|c|c|c|c|}\hline \text{State}& \text{Kill 1}&\text{Sell last}& \text{Greedy}&\text{Total}\\\hline % \text{18 1 16 19 6 22 14 15 2 12 27 18 11 1 14 9 23 1}&\text{1}&\text{1}&\text{sell}&\text{1}\\ \text{18 1 16 19 6 22 14 15 2 12 27 18 11 1 14 9 23}&\text{4}&\text{23}&\text{kill 1}&\text{5}\\ \text{18 1 16 19 6 22 14 15 2 12 27 18 11 14 9 23}&\text{15}&\text{23}&\text{kill 1}&\text{20}\\ \text{18 16 19 6 22 14 15 2 12 27 18 11 14 9 23}&\text{dec}&\text{1}&\text{time}&\text{22}\\ \text{17 15 18 5 21 13 14 1 11 26 17 10 13 8 22}&\text{8}&\text{22}&\text{kill 1}&\text{30}\\ \text{17 15 18 5 21 13 14 11 26 17 10 13 8 22}&\text{dec}&\text{4}&\text{times}&\text{38}\\ \text{13 11 14 1 17 9 10 7 22 13 6 9 4 18}&\text{11}&\text{18}&\text{kill 1}&\text{49}\\ \text{13 11 14 17 9 10 7 22 13 6 9 4 18}&\text{dec}&\text{3}&\text{times}&\text{55}\\ \text{10 8 11 14 6 7 4 19 10 3 6 1 15}&\text{2}&\text{15}&\text{kill 1}&\text{57}\\ \text{10 8 11 14 6 7 4 19 10 3 6 15}&\text{dec}&\text{2}&\text{times}&\text{61}\\ \text{8 6 9 12 4 5 2 17 8 1 4 13}&\text{3}&\text{13}&\text{kill 1}&\text{64}\\ \text{8 6 9 12 4 5 2 17 8 4 13}&\text{dec}&\text{1}&\text{time}&\text{66}\\ \text{7 5 8 11 3 4 1 16 7 3 12}&\text{5}&\text{12}&\text{kill 1}&\text{71}\\ \text{7 5 8 11 3 4 16 7 3 12}&\text{dec}&\text{2}&\text{times}&\text{75}\\ \text{5 3 6 9 1 2 14 5 1 10}&\text{2}&\text{10}&\text{kill 1}&\text{77}\\ \text{5 3 6 9 1 2 14 5 10}&\text{5}&\text{10}&\text{kill 1}&\text{82}\\ \text{5 3 6 9 2 14 5 10}&\text{dec}&\text{1}&\text{time}&\text{84}\\ \text{4 2 5 8 1 13 4 9}&\text{4}&\text{9}&\text{kill 1}&\text{88}\\ \text{4 2 5 8 13 4 9}&\text{dec}&\text{1}&\text{time}&\text{90}\\ \text{3 1 4 7 12 3 8}&\text{6}&\text{8}&\text{kill 1}&\text{96}\\ \text{3 4 7 12 3 8}&\text{dec}&\text{2}&\text{times}&\text{100}\\ \text{1 2 5 10 1 6}&\text{2}&\text{6}&\text{kill 1}&\text{102}\\ \text{1 2 5 10 6}&\text{5}&\text{6}&\text{kill 1}&\text{107}\\ \text{2 5 10 6}&\text{dec}&\text{1}&\text{time}&\text{109}\\ \text{1 4 9 5}&\text{4}&\text{5}&\text{4}&\text{113}\\ \text{4 9 5}&\text{dec}&\text{3}&\text{times}&\text{119}\\ \text{1 6 2}&\text{3}&\text{2}&\text{sell}&\text{121}\\ \text{1 6}&\text{2}&\text{6}&\text{kill 1}&\text{123}\\ \text{6}&\text{N/A}&\text{6}&\text{sell}&\text{129}\\\hline \end{array}$$

So the greedy algorithm is not optimal. The last two lines show it, when you're at 1 6. The greedy algorithm suggests swapping and selling the 1, then selling the 6, when you could have saved yourself the swap.

Original answer: I think I can get this down to 125:

Step 1:

Start by buying: 1 2 5 10 1 6 (cost 25, total 25)

Step 2:

Increment twice: 3 4 7 12 3 8 (cost 4, total 29)

Step 3:

Buy a 1: 3 4 7 12 3 8 1 (cost 1, total 30)

Step 4:

Swap last 1 to the left 5 times: 3 1 4 7 12 3 8 (cost 5, total 35)

Step 5:

Increment once: 4 2 5 8 13 4 9 (cost 2, total 37)

Step 6:

Buy a one: 4 2 5 8 13 4 9 1 (cost 1, total 38)

Step 7:

Swap last 1 to the left 3 times: 4 2 5 8 1 13 4 9 (cost 3, total 41)

Step 8:

Increment once: 5 3 6 9 2 14 5 10 (cost 2, total 43)

Step 9:

Buy two 1's: 5 3 6 9 2 14 5 10 1 1 (cost 2, total 45)

Step 10:

Swap last ones 4 times and once: 5 3 6 9 1 2 14 5 1 10 (cost 5, total 50)

Step 11:

Increment twice: 7 5 8 11 3 4 16 7 3 12 (cost 4, total 54)

Step 12:

Buy a 1: 7 5 8 11 3 4 16 7 3 12 1 (cost 1, total 55)

Step 13:

Swap 1 left 4 times: 7 5 8 11 3 4 1 16 7 3 12 (cost 4, total 59)

Step 14:

Increment once: 8 6 9 12 4 5 2 17 8 4 13 (cost 2, total 61)

Step 15:

Buy a 1: 8 6 9 12 4 5 2 17 8 4 13 1 (cost 1, total 62)

Step 16:

Swap 1 left twice: 8 6 9 12 4 5 2 17 8 1 4 13 (cost 2, total 64)

Step 17:

Increment twice: 10 8 11 14 6 7 4 19 10 3 6 15 (cost 4, total 68)

Step 18:

Buy a 1: 10 8 11 14 6 7 4 19 10 3 6 15 1 (cost 1, total 69)

Step 19:

Increment thrice: 13 11 14 17 9 10 7 22 13 6 9 18 4 (cost 6, total 75)

Step 20:

Buy a 1: 13 11 14 17 9 10 7 22 13 6 9 18 4 1 (cost 1, total 76)

Step 21:

Increment 4 times: 17 15 18 21 13 14 11 26 17 10 13 22 8 5 (cost 8, total 84)

Step 22:

Buy a 1: 17 15 18 21 13 14 11 26 17 10 13 22 8 5 1 (cost 1, total 85)

Step 23:

Increment once: 18 16 19 22 14 15 12 27 18 11 14 23 9 6 2 (cost 2, total 87)

Step 24:

Buy three 1s: 18 16 19 22 14 15 12 27 18 11 14 23 9 6 2 1 1 1 (cost 4, total 90)

Step 25:

Swap 9 and 23: 18 16 19 22 14 15 12 27 18 11 14 9 23 6 2 1 1 1 (cost 1, total 91)

Step 26:

Swap 6 left 10 times: 18 16 19 6 22 14 15 12 27 18 11 14 9 23 2 1 1 1 (cost 10, total 101)

Step 27:

Swap 2 left 7 times: 18 16 19 6 22 14 15 2 12 27 18 11 14 9 23 1 1 1 (cost 7, total 108)

Step 28:

Swap leftmost 1 left 14 times: 18 1 16 19 6 22 14 15 2 12 27 18 11 14 9 23 1 1 (cost 14, total 122)

Step 29:

Swap second 1 from the right leftward 3 times: 18 1 16 19 6 22 14 15 2 12 27 18 11 1 14 9 23 1 (cost 3, total 125)

Note that my algorithm is basically the same as AxiomaticSystem's, but I start by buying more beads in advance. It looks like the greedy algorithm of optimizing the number of increments is good for long strings, but not optimal for shorter ones.

Answer 3

I got 128 through a fairly overkill approach suggested by the fact that

as long as I have more than two beads, upgrading all my beads is cheaper than having bought them all one level higher
I simply start with buying $1,6,2$ and repeatedly upgrading, buying $1$s, and shifting them into their appropriate places.

Answer 4

My C-coded solution improves on OP but is perhaps not optimal

Minimum cost is 128

Strategy:
1. Work by dismantling the bracelet (create in the reverse sequence).
2. When more than 2 beads, and the smallest is more than $B_1$ it is worth decreasing.
3. At each removal, remove the nearest $B_1$ bead.
The cost is its value plus its distance from the end.

Starting sequence
$B_{18}$ $B_{1}$ $B_{16}$ $B_{19}$ $B_{6}$ $B_{22}$ $B_{14}$ $B_{15}$ $B_{2}$ $B_{12}$ $B_{27}$ $B_{18}$ $B_{11}$ $B_{1}$ $B_{14}$ $B_{9}$ $B_{23}$ $B_{1}$

Remove $B_{1}$ at previous line position $1$, cost $1$, total $1$, giving
$B_{18}$ $B_{1}$ $B_{16}$ $B_{19}$ $B_{6}$ $B_{22}$ $B_{14}$ $B_{15}$ $B_{2}$ $B_{12}$ $B_{27}$ $B_{18}$ $B_{11}$ $B_{1}$ $B_{14}$ $B_{9}$ $B_{23}$

Remove $B_{1}$ at previous line position $4$, cost $4$, total $5$, giving
$B_{18}$ $B_{1}$ $B_{16}$ $B_{19}$ $B_{6}$ $B_{22}$ $B_{14}$ $B_{15}$ $B_{2}$ $B_{12}$ $B_{27}$ $B_{18}$ $B_{11}$ $B_{14}$ $B_{9}$ $B_{23}$

Remove $B_{1}$ at previous line position $15$, cost $15$, total $20$, giving
$B_{18}$ $B_{16}$ $B_{19}$ $B_{6}$ $B_{22}$ $B_{14}$ $B_{15}$ $B_{2}$ $B_{12}$ $B_{27}$ $B_{18}$ $B_{11}$ $B_{14}$ $B_{9}$ $B_{23}$

Reduce each bead in previous line by $1$, cost $2$, total $22$, giving
$B_{17}$ $B_{15}$ $B_{18}$ $B_{5}$ $B_{21}$ $B_{13}$ $B_{14}$ $B_{1}$ $B_{11}$ $B_{26}$ $B_{17}$ $B_{10}$ $B_{13}$ $B_{8}$ $B_{22}$

Remove $B_{1}$ at previous line position $8$, cost $8$, total $30$, giving
$B_{17}$ $B_{15}$ $B_{18}$ $B_{5}$ $B_{21}$ $B_{13}$ $B_{14}$ $B_{11}$ $B_{26}$ $B_{17}$ $B_{10}$ $B_{13}$ $B_{8}$ $B_{22}$

Reduce each bead in previous line by $4$, cost $8$, total $38$, giving
$B_{13}$ $B_{11}$ $B_{14}$ $B_{1}$ $B_{17}$ $B_{9}$ $B_{10}$ $B_{7}$ $B_{22}$ $B_{13}$ $B_{6}$ $B_{9}$ $B_{4}$ $B_{18}$

Remove $B_{1}$ at previous line position $11$, cost $11$, total $49$, giving
$B_{13}$ $B_{11}$ $B_{14}$ $B_{17}$ $B_{9}$ $B_{10}$ $B_{7}$ $B_{22}$ $B_{13}$ $B_{6}$ $B_{9}$ $B_{4}$ $B_{18}$

Reduce each bead in previous line by $3$, cost $6$, total $55$, giving
$B_{10}$ $B_{8}$ $B_{11}$ $B_{14}$ $B_{6}$ $B_{7}$ $B_{4}$ $B_{19}$ $B_{10}$ $B_{3}$ $B_{6}$ $B_{1}$ $B_{15}$

Remove $B_{1}$ at previous line position $2$, cost $2$, total $57$, giving
$B_{10}$ $B_{8}$ $B_{11}$ $B_{14}$ $B_{6}$ $B_{7}$ $B_{4}$ $B_{19}$ $B_{10}$ $B_{3}$ $B_{6}$ $B_{15}$

Reduce each bead in previous line by $2$, cost $4$, total $61$, giving
$B_{8}$ $B_{6}$ $B_{9}$ $B_{12}$ $B_{4}$ $B_{5}$ $B_{2}$ $B_{17}$ $B_{8}$ $B_{1}$ $B_{4}$ $B_{13}$

Remove $B_{1}$ at previous line position $3$, cost $3$, total $64$, giving
$B_{8}$ $B_{6}$ $B_{9}$ $B_{12}$ $B_{4}$ $B_{5}$ $B_{2}$ $B_{17}$ $B_{8}$ $B_{4}$ $B_{13}$

Reduce each bead in previous line by $1$, cost $2$, total $66$, giving
$B_{7}$ $B_{5}$ $B_{8}$ $B_{11}$ $B_{3}$ $B_{4}$ $B_{1}$ $B_{16}$ $B_{7}$ $B_{3}$ $B_{12}$

Remove $B_{1}$ at previous line position $5$, cost $5$, total $71$, giving
$B_{7}$ $B_{5}$ $B_{8}$ $B_{11}$ $B_{3}$ $B_{4}$ $B_{16}$ $B_{7}$ $B_{3}$ $B_{12}$

Reduce each bead in previous line by $2$, cost $4$, total $75$, giving
$B_{5}$ $B_{3}$ $B_{6}$ $B_{9}$ $B_{1}$ $B_{2}$ $B_{14}$ $B_{5}$ $B_{1}$ $B_{10}$

Remove $B_{1}$ at previous line position $2$, cost $2$, total $77$, giving
$B_{5}$ $B_{3}$ $B_{6}$ $B_{9}$ $B_{1}$ $B_{2}$ $B_{14}$ $B_{5}$ $B_{10}$

Remove $B_{1}$ at previous line position $5$, cost $5$, total $82$, giving
$B_{5}$ $B_{3}$ $B_{6}$ $B_{9}$ $B_{2}$ $B_{14}$ $B_{5}$ $B_{10}$

Reduce each bead in previous line by $1$, cost $2$, total $84$, giving
$B_{4}$ $B_{2}$ $B_{5}$ $B_{8}$ $B_{1}$ $B_{13}$ $B_{4}$ $B_{9}$

Remove $B_{1}$ at previous line position $4$, cost $4$, total $88$, giving
$B_{4}$ $B_{2}$ $B_{5}$ $B_{8}$ $B_{13}$ $B_{4}$ $B_{9}$

Reduce each bead in previous line by $1$, cost $2$, total $90$, giving
$B_{3}$ $B_{1}$ $B_{4}$ $B_{7}$ $B_{12}$ $B_{3}$ $B_{8}$

Remove $B_{1}$ at previous line position $6$, cost $6$, total $96$, giving
$B_{3}$ $B_{4}$ $B_{7}$ $B_{12}$ $B_{3}$ $B_{8}$

Reduce each bead in previous line by $2$, cost $4$, total $100$, giving
$B_{1}$ $B_{2}$ $B_{5}$ $B_{10}$ $B_{1}$ $B_{6}$

Remove $B_{1}$ at previous line position $2$, cost $2$, total $102$, giving
$B_{1}$ $B_{2}$ $B_{5}$ $B_{10}$ $B_{6}$

Remove $B_{1}$ at previous line position $5$, cost $5$, total $107$, giving
$B_{2}$ $B_{5}$ $B_{10}$ $B_{6}$

Reduce each bead in previous line by $1$, cost $2$, total $109$, giving
$B_{1}$ $B_{4}$ $B_{9}$ $B_{5}$

Remove $B_{1}$ at previous line position $4$, cost $4$, total $113$, giving
$B_{4}$ $B_{9}$ $B_{5}$

Reduce each bead in previous line by $3$, cost $6$, total $119$, giving
$B_{1}$ $B_{6}$ $B_{2}$

Finally remove the last $3$ beads, cost $2 + 6 + 1 = 9$, total $128$

Answer 5

No need for computers, hand solving will do (though I did use code in the end to avoid making any calculation mess).

It is trivial to see that you should start from the end. Then preferentially remove ones and decrement when you are out of them and have more than 3 beads left.

However, it is also easy to see that whenever you have 1,2 it makes no sense to swap, as it doesn't make sense to swap 1,1,3, or 1,1,1,4 - simply popping the last bead first would cost as much as the swapping (decrement cost is ignored under assumption there are many higher beads still present).

Thus, the observation leading to the optimal solution is pretty trivial:

First, decrement as far as possible (until you get a bead with value 1). Then check how many lower numbers are on the left of the bead, compared to the bead value, starting with the rightmost bead until the first candidate to remove is found. If the bead is worth one more or less than the number of the beads it is holding up, you should remove it before any swapping takes place (eg for 3 there must be 2 beads with value 1 or 2 before removal is neutral or beneficial). This makes sure that if there is no other better bead to remove, it will pick first one and remove it.

This is easy to see that it works:

Imagine you have beads 1234 in that order + tons of higher beads before, after or mixed in between with that sequence. Thus, decrement is a "free" operation because you need to do it anyway for those beads, and its cost will be ignored in analysis. As you can easily see, there is no difference whether you first remove 4 or 1, total cost to remove all the beads will be 10 no matter the sequence. For sequence 1334 this still holds, although note that after removing 4, it does make sense to swap 1 and 3. Same goes for 1324. Cost in these two case is going to be 9 following this approach. Please note that I picked the breakpoint where both approaches (remove 1 vs remove higher) have the same cost. Add 1 to the left of those sequences and it is trivial to see removing higher has lower cost - for example, 11234 would cost 14 starting with 1s and just 11 starting with 4.

Then, simply go through the whole piece and tear it down. The remaining question is

where to stop. I haven't solved this bit in any really sensible way, so I brute-forced it with simple: optimal solution is min(removeOne+doRest, buyAll). This isn't branchy, so it scales pretty well even for crazy long bead sequences.

I got 125 as the optimal solution and my approach also works for all the corner cases presented in other answers.

Code is in MATLAB:

function jt()
goal = [18, 1, 16, 19, 6, 22, 14, 15, 2, 12, 27, 18, 11, 1, 14, 9, 23, 1];
cost = 0;

[~, cost] = recRemove(goal, cost)

end

function [goal, cost] = recRemove(goal, cost)

bfcost = sum(goal)+cost;
[goal, rb1cost] = removeOne(goal, cost);
if length(goal) > 2
    while (~any(goal == 1))
        goal = goal - 1;
        rb1cost = rb1cost + 2;
    end
    [~, rb1cost] = recRemove(goal, rb1cost);
else
    rb1cost = rb1cost + sum(goal); % at 2 left just remove them.
end

cost = min(rb1cost, bfcost);

end


function c = CR1(goal, TP) % cost to remove one bead at position TP.
c = length(goal) - TP + goal(TP);
end


function [goal, cost] = removeOne(goal, cost) %
for i = length(goal) : -1 : 1
    NL = 0;
    for j = 1 : i-1
        if (goal(j) < goal(i))
            NL = NL+1;
        end
    end
    if (NL+1 >= goal(i))
        btr = i;
        break;
    end
end
cost = cost + CR1(goal, btr);
goal(btr)=[];
end