12
\$\begingroup\$

Your task is to build a natural number using the fewest number of ones and only the operators + or -. For example, the number seven can be written 1+1+1+1+1+1+1=7, but it can also be written as 11-1-1-1-1=7. The first one uses 7 ones, while the latter only uses 6. Your task is to return the minimum number of ones that can be used given the input of some natural number, n.

This is code golf, so the shortest valid code in bytes wins.

Test cases

Input => Output

0 => 2 (since 1-1=0)
7 => 6
121 => 6
72 => 15
1000 => 7
2016 => 21
\$\endgroup\$

closed as off-topic by Jakube, manatwork, NoOneIsHere, mbomb007, cat May 3 '16 at 15:13

  • This question does not appear to be about programming puzzles or code golf within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Nice first challenge. I'd suggest including more test cases. Is "VALID OUTPUTS" a mistake, given that there's a single output? Also, is 0 a valid input, and if so, what should be output? \$\endgroup\$ – xnor May 3 '16 at 2:29
  • \$\begingroup\$ This is an interesting challenge. You may want to add an explanation for the outputs, change VALID OUTPUTS. It's your choice, but generally people like bold or italics instead of CAPITAL LETTERS (they make it look like shouting instead of emphasis). Bold is **bold text**, and italics is *italics text*. You could also use ### Text for bold-er text. Anyway, welcome to PPCG! \$\endgroup\$ – NoOneIsHere May 3 '16 at 2:34
  • \$\begingroup\$ You should make a computer-readable table or list of test cases that people can run their code on. See this tip. \$\endgroup\$ – xnor May 3 '16 at 2:59
  • 6
    \$\begingroup\$ I'm voting to close this question because this question is of a duplicate of the current (active!!) golfing challenge over at codefights.com/challenges. Even if the OP is also the author of the original challenge on codefights (which I doubt), the question should be closed until the challenge on codefights isn't active any more. \$\endgroup\$ – Jakube May 3 '16 at 10:18
  • 1
    \$\begingroup\$ @Jakube the direct link could've been helpful, but I agree. I will vote to close. \$\endgroup\$ – NoOneIsHere May 3 '16 at 14:27
3
\$\begingroup\$

JavaScript (ES6), 127 126 87 bytes

f=(n,z=2,m=n*9+'',r=m.replace(/./g,1))=>n?m.length+(m<'55'?f(n- --r/10,0)-1:f(r-n,0)):z
Input: <input type="number" oninput="result.textContent=f(this.value)"> Result: <span id="result"></span>

Should work to about 101415 at which point you start running into JavaScript's integer limits. Explanation:

f=(                             Recursive function
 n,                             Parameter
 z=2,                           Zero workaround
 m=n*9+'',                      Magic
 r=m.replace(/./g,1)            Find repunit not less than than n
)=>n?                           Nothing to do if n is zero
 m.length+                      Assume subtracting from repunit
 (m<'55'?                       Should we subtract from repunit?
  f(n- --r/10,0)                No, so subtract previous repuint
   -1:                          Which is one 1 shorter
  f(r-n,0)):                    Subtract from repunit
 z                              Return special case if n is zero

This uses the n*9 magic twice; firstly, it gives me the length of the next repunit, secondly, if the first two digits of n*9 are 55 or higher, then we need to subtract n from that next repunit, otherwise we need to subtract the previous repunit (which is calculated by subtracting 1 and dividing by 10). This should work up to 1015.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 19 16 bytes

ffqQvs+R1Y^c3"+-

Test suite

Brute force algorithm. The necessary strings are generated by taking all lists whose elements are ['+', '-', ''] of length equal to the number of 1s being tested, appending a 1 to each, and concatenating to a single string. These strings are then evaluated and compared with the input. This is repeated until a successful string is found.

Some strings with a leading + or - are tested, but this isn't a problem. It would be if the input was negative though.

It can run up to length 9 before it becomes too slow.

Explanation:

ffqQvs+R1Y^c3"+-
ffqQvs+R1Y^c3"+-"T    Implicit variable introduction
                      Q = eval(input())
f                     Starting with T = 1 and counting upwards, repeat until true.
                      The value of T where the result is first true is output.
           c3"+-"     Chop "+-" into thirds, giving ['+', '-', '']
          ^      T    Form every list with those elements of length T.
 f                    Filter over those lists, lambda var Y.
      +R1Y            Append a 1 to each element of the list.
     s                Concatenate.
    v                 Eval.
  qQ                  Compare for equality with the input.
                      The inner filter will let through the successful cases.
                      The outer filter will stop when there is a successful case.
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 92 bytes

f=(n,i=3)=>eval([...s=i.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n?f(n,i+1):s.length-1
n = <input type="number" oninput="R.textContent=f(this.value)" /><pre id="R"></pre>

Explanation

Recursive function. This generates all possible permutations of 1s separated by either +, - or nothing. It does this by incrementing a base-3 number, turning it into an array of digits, converting each digit 0 to -, 1 to + and 2 to an empty string, then joining them together with 1s. The resulting string is evald as a JavaScript statement which returns the result of the equation.

Because the operators are joined with 1s in between (like +1+1+1+), there are length - 1 1s. The first operator is ignored (because +1 = 1, <nothing>1 = 1 and it's a number so there will never be a leading 0 for -) and the final operator is also ignored (by appending .0 to the equation).

Higher Output Version, 96 bytes

The other version can't return outputs higher than ~10 because of the recursion call stack limit. This version uses a for loop instead of recursion, so it can return outputs up to ~33. The amount of time required increases exponentially though so I don't recommend testing it.

n=>eval('for(a=3;eval([...s=a.toString(3)].map(d=>"-+"[d]||"").join`1`+".0")-n;)a++;s.length-1')
\$\endgroup\$
  • \$\begingroup\$ This sounds overcomplicated, I like it. \$\endgroup\$ – Bálint May 5 '16 at 6:56

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