13
\$\begingroup\$

Credits to @Agawa001 for coming up with this question.

Explanation

My new "keybore" only has 2 buttons, namely + and -.

The number in the memory starts at 0.

Each consecutive press of + or - will increment/decrement the memory for exactly how many times it has been pressed consecutively.

Therefore, if you press + 4 times, first time it adds 1, the second time it adds 2, the third time it adds 3, the fourth time it adds 4, giving you 10 (ten).

Now, if you press - 3 times, the first time it subtracts 1, the second time 2, the third time 3, leaving you with 4 (four).

TL;DR

Given a string of + and -, divide it at each change of character. Then each resulting string of m + symbols adds the m-th triangle number, and each string of n - symbols subtracts the n-th triangle number.

Walk-through

Now, if you still do not understand, I will show you how +++--+-- creates 1.

Program   | Counter | Memory
----------------------------
          |  0      | 0
+         | +1      | 1
++        | +2      | 3
+++       | +3      | 6
+++-      | -1      | 5
+++--     | -2      | 3
+++--+    | +1      | 4
+++--+-   | -1      | 3
+++--+--  | -2      | 1

Task

  • You will take a positive integer as input, either as functional argument or from STDIN.
  • Then, you will output/print the minimum number of keystrokes needed to create that number using the method above.

Testcases

Since rearranging the + or - runs gives the same number, for each such group only the lexicographically earliest sequence is listed.

Input | Output | Possible corresponding sequences
-------------------------------------------------
    4 |      5 | -+++-
    6 |      3 | +++
    9 |      5 | ++++-
   11 |      7 | +++-+++
   12 |      7 | +++++--, ++++-++
   19 |      8 | -++++++-
   39 |     12 | +++++++++---
   40 |     13 | +++++++++---+, ++++++++-+++-
   45 |      9 | +++++++++
   97 |     20 | ++++++++++++++--+---, +++++++++++++-++++--, ++++++++++++-++++++-
  361 |     34 | ++++++++++++++++++++++++++-+++-+++

Extra resources

Scoring

This is . Shortest solution in bytes wins.

\$\endgroup\$
14
  • 9
    \$\begingroup\$ Does that mean... you are keybored? \$\endgroup\$ – busukxuan May 29 '16 at 6:27
  • \$\begingroup\$ I think you're OK with 10 test cases now (including mine). \$\endgroup\$ – Erik the Outgolfer May 29 '16 at 9:02
  • \$\begingroup\$ @ΈρικΚωνσταντόπουλος The 12 test case has been added, with a slight modification (since +++++-- is also an alternative, but I removed ++-++++ since that's equivalent to ++++-++). I've still got one more case I'd like to add later in case anyone comes up with an efficient solution, if I manage generate it. \$\endgroup\$ – Sp3000 May 29 '16 at 9:13
  • \$\begingroup\$ @Sp3000 I did not want ++-++++ removed. Also, this was MY edit, not YOURS. \$\endgroup\$ – Erik the Outgolfer May 29 '16 at 9:38
  • \$\begingroup\$ @ΈρικΚωνσταντόπουλος Only 1 solution from each set of equivalent solutions is listed - I thought that if all the minimal solutions were listed, the test cases would be unnecessarily long (there's 6 solutions for 40 and 17 solutions for 97). I do apologise if that intention was not clear. Also you were missing +++++-- (or, equivalently, --+++++), which is why I felt the need to edit in the first place. \$\endgroup\$ – Sp3000 May 29 '16 at 9:57
2
\$\begingroup\$

Python 2, 119 bytes

def g(n,i=0,s=''):
 c=x=t=0
 for d in s:C=int(d)*2-1;t=(c==C)*t+1;c=C;x+=c*t
 return(x==n)*len(s)or g(n,i+1,bin(i)[3:])

Very slow brute-force approach. The third line computes the score of a string x; the other lines loop over all possible binary strings until one whose score equals the argument is found.

@Leaky saved three bytes!

\$\endgroup\$
2
  • \$\begingroup\$ s/x==n and len/(x==n)*len/ \$\endgroup\$ – Leaky Nun May 29 '16 at 11:00
  • \$\begingroup\$ It might save some bytes to get rid of s and just use repeated division, like this: def f(n): \n while n>0:print n%2;n/=2 \$\endgroup\$ – Leaky Nun May 29 '16 at 11:05
2
\$\begingroup\$

Pyth, 25 bytes

ffqyQ.as-Mc*RhdY2{s.pM./T

Try it online.

This is extremely inefficient, and runs out of memory for f(n) ≥ 11. It calculates f(22) = 10 in about 10 seconds on my laptop.

Explanation

  • Starting from 1, loop through numbers T. (f)
    • Generate all partitions of T. (./T)
    • Generate all permutations of those. (.pM)
    • Flatten the list. (s)
    • Uniquify the list. ({) This step could be removed, but it makes the code much faster.
    • Filter the resulting permutations of partitions: (f)
      • Multiply each number d of the partition (*R) by itself plus one (hd). This gives double the number to add/subtract to the result.
      • Chop the list to parts of length 2. (c2)
      • Subtract any second number in those parts from the second number. (-M)
      • Sum the results. This gives double the resulting number if the partition permutation was interpreted as number of additions, then subtractions, etc.
      • Take the absolute value. (.a) If the result was negative, swapping the additions and subtractions gets the positive result.
      • Check if the result equals double the input. (qyQ) In this case the partition permutation is correct, return it.
    • If the filter returned any results, there was a solution of length T. Return and print T.
\$\endgroup\$
2
\$\begingroup\$

MATL, 43 29 bytes

E:"@TFEqZ^!"@Y'tQ**s]vGE=a?@.

This is memory- and time-inefficient. The online compiler can handle up to input 45 only.

Try it online!

Here's a modified version with all test cases up to 40 (it takes almost a minute in the online compiler).

Explanation

This tests all possible key-press sequences of each length, in order of increasing length, until a valid sequence is found.

E:       % Range [1 2 ... 2*N] where N is implicit input. The required sequence length is
         % less than 2*N, so this is enough
"        % For each
  @      %   Push current value: length of sequence
  TFEq   %   Push array [1 -1]
  Z^     %   Cartesian power. Gives all possible sequences of 1, -1 of that length
  !      %   Transpose. Each sequence is now a row
  "      %   For each sequence
    @    %     Push current sequence
    Y'   %     Run-length decoding: Pushes an array of values 1 and -1, and then an
         %     array of run-lengths
    tQ*  %     Duplicate, add 1, multiply. Gives twice the triangular number for each run
    *    %     Multiply element-wise by 1 or -1 to produce correct sign
    s    %     Sum of array. This is the number produced by the current sequence
  ]      %   End for
  v      %   Concatenate all numbers into an array
  GE=a   %   True if any of those numbers equals twice the input
  ?      %   If so
    @    %     Push current sequence length. This is the final result
    .    %     Break loop
         %   End if
         % End for
         % Implicit display
\$\endgroup\$
1
  • \$\begingroup\$ @Sp3000 I've added one too, so, for reference, 4, 6, 9 and 19 are the test cases referred to, in order. \$\endgroup\$ – Erik the Outgolfer May 29 '16 at 9:05
1
\$\begingroup\$

Python, 105 100 bytes

Uses an inefficient breadth-first search.

def k(n):
 m=t=l=0;h=[]
 while m-n:o=1-2*(t>0);(m,t,l),*h=h+[(m+t-o,t-o,l+1),(m+o,o,l+1)]
 return l
  • h is a list used as a queue
  • m is the value of the sequence at the head of the list
  • t is the last number added to m
  • l is the length of the sequence that generated m
  • o is +/-1, the sign is opposite the sign of t

Edit: Leaky Nun shaved five bytes.

\$\endgroup\$
2
  • \$\begingroup\$ s/m,t,l,h=0,0,0,[]/m=t=l=0,h=[]/ \$\endgroup\$ – Leaky Nun May 31 '16 at 12:28
  • \$\begingroup\$ s/while m!=n/while m-n/ \$\endgroup\$ – Leaky Nun May 31 '16 at 12:28

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.