Optimal addition subtraction chain

Question

An addition-subtraction chain, is a sequence \$a_1, a_2, a_3, ... ,a_n\$, such that \$a_1=1\$ and for all \$i > 1\$, there exist \$j,k<i\$ such that \$a_i = a_j \pm a_k\$.

Your task, is given a number \$x\$, find the shortest addition-subtraction chain, such that \$a_n = x\$.

Rules

• You can assume the input is a valid integer
• In case there are multiple optimal addition-subtraction chains, you can print any non-empty subset of them
• You may use any reasonable I/O method (you can output it reversed, with any separator you want, in any base you want, ect.)

Test cases

(these are one solution, you can output anything valid with the same length)

these are all the numbers with a addition subtraction chain of length 6 or less

-31 -> [1, 2, 4, 8, 16, -15, -31]
-30 -> [1, 2, 4, 8, 16, -15, -30]
-28 -> [1, 2, 4, 8, -6, -14, -28]
-24 -> [1, 2, 4, -2, -6, -12, -24]
-23 -> [1, 2, 4, 8, 12, 24, -23]
-22 -> [1, 2, 4, 6, -5, -11, -22]
-21 -> [1, 2, 3, 6, 12, -9, -21]
-20 -> [1, 2, 4, 6, -5, -10, -20]
-19 -> [1, 2, 4, 8, -3, -11, -19]
-18 -> [1, 2, 4, -1, 8, -9, -18]
-17 -> [1, 2, 4, -3, 7, -10, -17]
-16 -> [1, 2, 3, -1, -4, -8, -16]
-15 -> [1, 2, 4, 8, 16, -15]
-14 -> [1, 2, 4, 8, -7, -14]
-13 -> [1, 2, 4, 6, -3, -7, -13]
-12 -> [1, 2, 4, -3, -6, -12]
-11 -> [1, 2, 4, 6, -5, -11]
-10 -> [1, 2, 4, -2, -6, -10]
-9 -> [1, 2, 4, 8, -1, -9]
-8 -> [1, 2, 4, 8, 0, -8]
-7 -> [1, 2, 4, -3, -7]
-6 -> [1, 2, 4, 8, -6]
-5 -> [1, 2, 4, -3, -5]
-4 -> [1, 2, 4, 8, -4]
-3 -> [1, 2, -1, -3]
-2 -> [1, 2, 4, -2]
-1 -> [1, 0, -1]
0 -> [1, 0]
1 -> [1]
2 -> [1, 2]
3 -> [1, 2, 3]
4 -> [1, 2, 4]
5 -> [1, 2, 4, 5]
6 -> [1, 2, 4, 6]
7 -> [1, 2, 4, -3, 7]
8 -> [1, 2, 4, 8]
9 -> [1, 2, 3, 6, 9]
10 -> [1, 2, 4, 5, 10]
11 -> [1, 2, 4, 6, 5, 11]
12 -> [1, 2, 4, 6, 12]
13 -> [1, 2, 3, 5, 10, 13]
14 -> [1, 2, 4, 6, 10, 14]
15 -> [1, 2, 3, 6, 9, 15]
16 -> [1, 2, 4, 8, 16]
17 -> [1, 2, 4, 8, 9, 17]
18 -> [1, 2, 4, 8, 9, 18]
19 -> [1, 2, 4, 8, 9, 17, 19]
20 -> [1, 2, 4, 5, 10, 20]
21 -> [1, 2, 4, 8, 16, 5, 21]
22 -> [1, 2, 4, 8, 12, 24, 22]
23 -> [1, 2, 4, 8, 16, -15, 23]
24 -> [1, 2, 3, 6, 12, 24]
25 -> [1, 2, 4, 8, 12, 13, 25]
26 -> [1, 2, 4, 6, 10, 16, 26]
27 -> [1, 2, 4, 5, 9, 18, 27]
28 -> [1, 2, 4, 8, 12, 14, 28]
30 -> [1, 2, 4, 5, 10, 20, 30]
31 -> [1, 2, 4, 8, 16, -15, 31]
32 -> [1, 2, 4, 8, 16, 32]
33 -> [1, 2, 4, 8, 16, 32, 33]
34 -> [1, 2, 4, 8, 16, 17, 34]
36 -> [1, 2, 3, 6, 9, 18, 36]
40 -> [1, 2, 4, 8, 12, 20, 40]
48 -> [1, 2, 4, 8, 12, 24, 48]
64 -> [1, 2, 4, 8, 16, 32, 64]

you can find a list of all optimal addition subtraction chains for each of them here

This is code golf, so the shortest answer in bytes in each language wins.

Answer 1

Brachylog, 19 17 bytes

∧≜;1⟨∋{+|-}∋⟩ᵃ⁽?t

Try it online!

I guess I shouldn't be too surprised, but funnily enough this produces the exact same outputs as xash's solution--up to \$n = 13\$ after which both time out. Takes input through the output variable and outputs through the input variable.

   1                 Starting with 1,
             ᵃ       repeat on the list of previous results
∧≜;           ⁽      as few times as necessary:
       +             add
      { |-}          or subtract
    ⟨∋     ∋⟩        one element and another (not necessarily distinct),
               ?     such that the final list of results is the input variable
                t    and its last element is the output variable.

Answer 2

JavaScript (ES6), 104 bytes

A very basic and quite long implementation. But it does solve all test cases in ~20 seconds on TIO.

f=(n,l)=>(g=([...a],x)=>a.push(x)<l?a.some(x=>a.some(y=>g(a,x+y)||g(a,x-y))):r=x==n&&a)([],1)?r:f(n,-~l)

Try it online!

Answer 3

Python 3, 88 87 bytes

-1 byte thanks to dingledooper!

f=lambda n,x=[1],*a:x*(n in x)or f(n,*a,*[x+[a+c]for a in x for b in x for c in(b,-b)])

Try it online!

Answer 4

Haskell, 59 bytes

head.(`filter`a).elem
a=[1]:do h<-a;i<-h;j<-h;[i-j:h,i+j:h]

Try it online!

a is the infinite list of all the addition-subtraction chains, sorted by length. The function head.(`filter`a).elem takes an integer (say n) and returns the first chain in a which contains n.

Answer 5

Husk, 18 17 bytes

`ḟ¡SṀ:S×+S+m_;;1€

Try it online!

-1 thanks to Leo

The longer I look at this, the less I have any idea why it seems to work. Probably something to do with the iterL overload that I didn't even know existed. I need coffee

Answer 6

Jelly, 23 bytes

1+;_ɗþ`FQ;€Ʋ€Ẏ$Fċ³¬Ɗ¿ċƇ

Try it online!

A full program taking a single argument and returning a list of all optimal addition subtraction chains, each in reverse order.

Explanation

1                       | Start with 1
                   Ɗ¿   | While the following is true:
               F        | - Flatten list
                ċ³      | - Count the number of occurrences of the input
                  ¬     | - Not (i.e. = 0)
             $          | Do the following:
          Ʋ€            | - For each member of the list, do the following:
    ɗþ`                 |   - Do the following as a dyad mapping over the sublist for both left and right arguments
 +                      |     - Add
  ;                     |     - Concatenated to:
   _                    |       - Subtract
       F                |   - Flatten
        Q               |   - Uniquify
         ;€             |   - Concatenate each value to the original sublist
             Ẏ          | - Join lists together
                     ċƇ | Finally, keep only those list where the input appears

Answer 7

Brachylog, 31 bytes

1g|g;Lc,1↔a₀ᵇb{kgj∋ᵐ{+|-}~t?}ᵐt

Try it online!

How it works

? is the input of the current scope.

1g|g;Lc,1↔a₀ᵇb{kgj∋ᵐ{+|-}~t?}ᵐt
1g                              if ? is 1, return [1].
  |                             else
   g;L                          [[?], L]
      c                         [?, L0, L1, …] (try shorter lists first)
       ,1↔                      [1, L0, L1, …, ?]
              {             }ᵐ  map every
          a₀ᵇb                  prefix except the first ([1]):
                                f.e. [1, L0, L1]
               k                [1, L0]
                gj              [[1, L0], [1, L0]]
                  ∋ᵐ            select any element of each list, f.e.
                                [L0, 1]
                    {+|-}       try L0 + 1 and L0 - 1
                         ~t?    is equal to L1
                              t return the last prefix (which is the list)

Answer 8

Charcoal, 42 bytes

Ｎθ⊞υ⟦¹⟧ＦυＦ¬⊙υ№κθＦιＦ⁻⁺⁺ιλ⁻ιλι⊞υ⁺ι⟦μ⟧Ｉ⊟Φυ№ιθ

Try it online! Link is to verbose version of code. Very¹ slow, so only try it with single-digit integers. Explanation:

Ｎθ

Input x.

⊞υ⟦¹⟧

Start a breadth-first search with the trivial chain of length 1.

ＦυＦ¬⊙υ№κθ

Loop over the search results until a chain is found that includes x.

ＦιＦ⁻⁺⁺ιλ⁻ιλι

Loop over all the sums and differences that aren't already in the chain.

⊞υ⁺ι⟦μ⟧

Push a new chain to the search list.

Ｉ⊟Φυ№ιθ

Print a chain that includes x.

¹Struggles to complete solutions requiring chains of length 6. At a cost of 6 bytes it's possible to speed it up by avoiding pushing duplicate chains to the search list but that's still only enough for it to find all chains of length 6.

Answer 9

Ruby, 77 bytes

->n,*r{*a=1;(a.product(a){|x,y|r|=[a|[x+y],a|[x-y]]};a,*r=r)until a[-1]==n;a}

Try it online!

Answer 10

05AB1E, 22 bytes

X¸¸[ćD©Iå#ãDOsÆ«ε®sª}«

Try it online!

Very slow, the performance can be improved a bit by adding three bytes:

X¸¸[ćD©Iå#ãDOsÆ«®KÙε®sª}«

Try it online!