12
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Do you actually need to use -15 to make 23, or could you just use 16-1 and then make 23 using 15+8? \$\endgroup\$
    – Neil
    May 15 at 17:55
  • 2
    \$\begingroup\$ @Neil You could use 16-1 and then make 23. These are just a single solution my program found, other solutions with the same length exist for most of those. \$\endgroup\$ May 15 at 17:56
  • 1
    \$\begingroup\$ Can we output the addition-subtraction chain reversed? \$\endgroup\$
    – Delfad0r
    May 15 at 21:17
  • \$\begingroup\$ @Delfad0r yes. I edited the question. \$\endgroup\$ May 16 at 4:33

10 Answers 10

9
\$\begingroup\$

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.
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Oh, wow, this is so much cleaner! I had hoped describing the list beforehand would allow for some search optimizations and thus be faster then brute force – but that's probably too complicated. :-) \$\endgroup\$
    – xash
    May 15 at 19:04
6
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Could you save a byte with a[l]-n and reversing that ternary? \$\endgroup\$
    – Shaggy
    May 15 at 19:35
  • 2
    \$\begingroup\$ @Shaggy I've just saved a byte with a more convoluted update. I think a[l]-n (or a[l]^n, actually) would have failed for n=0. \$\endgroup\$
    – Arnauld
    May 15 at 19:37
6
\$\begingroup\$

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!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Maybe you should import sys;sys.setrecursionlimit(10**6); to the header in TIO \$\endgroup\$ May 15 at 18:09
  • \$\begingroup\$ @CommandMaster I've added this now, but this doesn't help too much as the recursive solution is a lot slower than the already-slow iterative one anyways. (It takes ~50 times longer for 9) \$\endgroup\$
    – ovs
    May 15 at 20:53
  • 2
    \$\begingroup\$ 87 bytes \$\endgroup\$ May 15 at 21:13
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I've honestly never seen iterL actually get inferred in a program before. Nice answer. \$\endgroup\$
    – Razetime
    May 16 at 5:21
  • 1
    \$\begingroup\$ Very nice answer! One byte can be golfed by using instead of om (Try it online!); I think this also makes it more understandable, but if you want I can provide an explanation of what's happening here :) \$\endgroup\$
    – Leo
    May 17 at 0:53
  • \$\begingroup\$ @Leo Ah, I knew there had to be something--thanks! \$\endgroup\$ May 17 at 5:58
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 42 bytes

Nθ⊞υ⟦¹⟧FυF¬⊙υ№κθFιF⁻⁺⁺ιλ⁻ιλι⊞υ⁺ι⟦μ⟧I⊟Φυ№ιθ

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

Nθ

Input x.

⊞υ⟦¹⟧

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

FυF¬⊙υ№κθ

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

FιF⁻⁺⁺ιλ⁻ιλι

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

⊞υ⁺ι⟦μ⟧

Push a new chain to the search list.

I⊟Φυ№ιθ

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.

\$\endgroup\$
1
  • \$\begingroup\$ "Start a bread-first search" - one of my favorite snack-searching algorithms. \$\endgroup\$
    – Nathan
    May 17 at 18:50
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.