20
\$\begingroup\$

You are playing a famous game called \$1\text{D Array BattleGround}\$. In the game, the player can be stationed in any position from \$0\$ to \$10^5\$.

You are a Paratrooper in the game and have the ability to do two types of operation \$-\$

  • Advance, which would multiply your position by \$2\$
  • Fall-back, which would decrease your current position by \$1\$

Each type of operation requires \$1\$ second.

You are stationed in \$N\$ and want to go to \$M\$ in the minimum time possible, (\$1≤ N, M ≤10^4\$).

Find out the minimum time you need to Get to \$M\$.

Note: After each operation, you must remain in the zone from \$0\$ to \$10^5\$.

Sample

Input : 4 6
Output: 2

Input : 10 1
Output: 9

Input : 1 3
Output: 3

Input : 2 10
Output: 5

Input : 666 6666
Output: 255

Input : 9999 10000
Output: 5000

This is a code-golf challenge so code with lowest bytes wins!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Ah, my bad. I read that as increase, but it clearly says multiply. Sorry about that. \$\endgroup\$ – Adám Jun 17 '20 at 17:44
  • 5
    \$\begingroup\$ No, I made it myself. \$\endgroup\$ – Jubayer Abdullah Joy Jun 17 '20 at 20:39
  • 1
    \$\begingroup\$ It seems like there should be a number theory equivalent to this. \$\endgroup\$ – Ross Presser Jun 18 '20 at 2:05
  • 1
    \$\begingroup\$ Could you wrap a bold around the multiply? I read it as increase too! \$\endgroup\$ – streetster Jun 18 '20 at 10:34
  • 1
    \$\begingroup\$ @streetster Thank you for pointing it out :) \$\endgroup\$ – Jubayer Abdullah Joy Jun 18 '20 at 13:39

14 Answers 14

23
\$\begingroup\$

JavaScript (ES6), 30 bytes

Takes input as (N)(M).

N=>g=M=>M>N?M%2-~g(M+1>>1):N-M

Try it online!

How?

Instead of going from \$N\$ to \$M\$, we go from \$M\$ to \$N\$.

While \$M\$ is greater than \$N\$:

  • if \$M\$ is odd, increment it and divide it by \$2\$ (2 operations)
  • if \$M\$ is even, just divide it by \$2\$ (1 operation)

When \$M\$ is less than or equal to \$N\$, the remaining number of operations is \$N-M\$.

Example for \$N=666\$, \$M=6666\$:

  M   | transformation     | operations | total
------+--------------------+------------+-------
 6666 | M / 2       = 3333 |      1     |   1
 3333 | (M + 1) / 2 = 1667 |      2     |   3
 1667 | (M + 1) / 2 = 834  |      2     |   5
 834  | M / 2       = 417  |      1     |   6
 417  | M + 249     = 666  |     249    |  255

With inverse operations in reverse order, this gives:

$$((((666-249)\times 2)\times 2-1)\times 2-1)\times 2=6666$$

The idea behind that is that it's always cheaper to process the greatest number of fall-back operations at the beginning of the process (i.e. when \$N\$ is still small) rather than exceeding \$M\$ by too large a margin with hasty advance operations and doing fall-backs afterwards.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Is there a proof that this procedure gives the minimum number of steps? \$\endgroup\$ – Luis Mendo Jun 17 '20 at 20:02
  • 9
    \$\begingroup\$ @LuisMendo Oh yes ... Yes, there is! ... hurried footsteps ... door slamming ... \$\endgroup\$ – Arnauld Jun 17 '20 at 20:18
  • 1
    \$\begingroup\$ This looks right, I think I have an argument why it always works. \$\endgroup\$ – xnor Jun 17 '20 at 20:29
  • 12
    \$\begingroup\$ When considering going from M to N like you're doing, the reversed operations are halving (only for evens) and incrementing. Once M is below N, the only thing to do is to increment it up to N, since making it smaller first would be silly. Before that, we never want to increment twice in a row, since later we'll halve, and increment-increment-halve can be shortened to with halve-increment. This leaves us with only sequences made of halve and increment-halve. These can only be applied to even and odd numbers respectively, and so can be chosen based on parity as in your procedure. \$\endgroup\$ – xnor Jun 17 '20 at 20:55
  • 1
    \$\begingroup\$ (And the limit of 10,000 never comes up because it's even, so you never increment above it.) \$\endgroup\$ – xnor Jun 17 '20 at 20:57
6
\$\begingroup\$

C (gcc), 53 34 bytes

Saved a whopping 19 bytes thanks to the man himself Arnauld!!!

f(N,M){M=M>N?M%2-~f(N,-~M/2):N-M;}

Try it online!

A port of Arnauld's JavaScript answer.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ A more direct port would work as well. :) \$\endgroup\$ – Arnauld Jun 17 '20 at 18:58
  • \$\begingroup\$ @Arnauld Wow! Was wondering if recursion would help and does it ever - thanks! :D \$\endgroup\$ – Noodle9 Jun 17 '20 at 19:37
  • \$\begingroup\$ This doesn't return the answer, merely calculate it. Is it required for code gold answers to return output? \$\endgroup\$ – Chipster Jun 21 '20 at 23:05
  • \$\begingroup\$ @Chipster It most certainly does return the answer! Click on Try it online and see for yourself. \$\endgroup\$ – Noodle9 Jun 22 '20 at 2:13
  • \$\begingroup\$ Hmm, I see it. Does C return things implicitly? \$\endgroup\$ – Chipster Jun 22 '20 at 2:19
6
\$\begingroup\$

APL (Dyalog Unicode), 24 bytes SBCS

Recursive dfn as per Arnauld's answer.

{⍵≤⍺:⍺-⍵⋄(2|⍵)+1+⍺∇⌈⍵÷2}

Try it online! We take Arnauld's approach but we use APL's nice builtins to make a single recursive call instead of having to choose the recursive call that we want to make (which would depend on the parity of M):

{⍵≤⍺:⍺-⍵⋄(2|⍵)+1+⍺∇⌈⍵÷2} ⍝ dfn taking N on the left and M on the right
{⍵≤⍺:                    } ⍝ if N is less than or equal to M
      ⍺-⍵                  ⍝ just return N - M
          ⋄                 ⍝ otherwise
                   ⍺∇⌈⍵÷2  ⍝ divide M by 2, round up and call this function recursively
                 1+         ⍝ to which we add 1 unconditionally
          (2|⍵)+            ⍝ and to which we add the parity of M, i.e. add one more iff M is odd.
\$\endgroup\$
6
\$\begingroup\$

Husk, 11 bytes

←V€⁰¡ṁ§eD←;

Try it online! Arguments are in reversed order (first target, then initial position).

Explanation

Brute force turned out shorter than more efficient methods.

←V€⁰¡ṁ§eD←;  Inputs: M (stored in ⁰) and N (implicit).
          ;  Wrap in list: [N]
    ¡        Iterate, returning an infinite list:
     ṁ         Map and concatenate:
         ←       Decrement and
        D        double,
      §e         put the results in a two-element list.
 V           1-based index of first list that
  €⁰         Contains M.
←            Decrement.
\$\endgroup\$
5
  • \$\begingroup\$ This solution is producing tle for the last case where \$N=9999 \$ and \$ M= 10000.\$ Were you able to produce a result from that case? \$\endgroup\$ – Jubayer Abdullah Joy Jun 18 '20 at 19:42
  • 1
    \$\begingroup\$ @JubayerAbdullahJoy TIO cuts execution time at 60 seconds. It should eventually finish if I run it locally. I can try that tomorrow. \$\endgroup\$ – Zgarb Jun 18 '20 at 19:53
  • 1
    \$\begingroup\$ @JubayerAbdullahJoy Well, the program quickly filled my computer's memory and I had to kill it. I maintain that it's correct in the sense that given enough time and memory, it will eventually output 5000, even though it's practically untestable. \$\endgroup\$ – Zgarb Jun 19 '20 at 16:19
  • \$\begingroup\$ oh, I am new to code-golf. What should we do if a solution can't be verified? Can it be accepted? :( \$\endgroup\$ – Jubayer Abdullah Joy Jun 19 '20 at 16:44
  • 1
    \$\begingroup\$ There has been some discussion on our meta site (here and here) about untestable answers. The consensus seems to be that an explained solution that works on small inputs and seems scalable is acceptable, unless of course someone finds inputs on which it fails. OTOH, since Husk and JavaScript are like apples and oranges, consider not accepting any answer. \$\endgroup\$ – Zgarb Jun 19 '20 at 19:08
4
\$\begingroup\$

Jelly, 13 bytes

Took quite a while to find an approach which could be implemented in under 16 bytes.

‘:Ḃȯ⁹>$Ɗ?Ƭ2i’

A dyadic Link accepting M on the left and N on the right which yields the time you need to manoeuvre.

Try it online!

How?

‘:Ḃȯ⁹>$Ɗ?Ƭ2i’ - Link: M, N
          2   - use two as the right argument (R) of:
         Ƭ    -   collect up, starting at M, while results are distinct:
        ?     -     if...
       Ɗ      -     ...condition: last three links as a monad - i.e. f(current_value):
  Ḃ           -       LSB (i.e. is current_value odd?)
      $       -       last two links as a monad:
     ⁹        -         chain's right argument, N
    >         -         greater than? (i.e. is current_value less than N?)
   ȯ          -       logical OR (i.e. is current_value either odd or less than N?)
‘             -     ...then: increment
 :            -     ...else: integer divide by R (2)
          i  - 1-based index of first occurrence of N in that
           ’ - decrement
\$\endgroup\$
4
  • \$\begingroup\$ For case three where \$N = 1\$ and \$M = 3\$ this code gives result \$2\$. The expected result is \$3\$. I hope you will be able to figure out this case :) \$\endgroup\$ – Jubayer Abdullah Joy Jun 18 '20 at 19:51
  • 1
    \$\begingroup\$ OK sorted it. Thanks for spotting that. \$\endgroup\$ – Jonathan Allan Jun 18 '20 at 23:28
  • 2
    \$\begingroup\$ Why less than 16 bytes, specifically? \$\endgroup\$ – Shaggy Jun 18 '20 at 23:41
  • 1
    \$\begingroup\$ Found a few different solutions for 16 along the way. \$\endgroup\$ – Jonathan Allan Jun 19 '20 at 1:31
4
\$\begingroup\$

Japt, 15 14 bytes

Heading tag now includes the completely unnecessary space SE are forcing on us for no good reason

Well, seeing as everyone else is taking Arnauld's approach ...! Be sure to +1 him if you're +1ing this.

Takes input in reverse order.

>V?¢ÌÒß°Uz:UnV

Try it

>V?¢ÌÒß°Uz:UnV     :Implicit input of integers U=M and V=N
>V                 :Is U greater than V
  ?                :If so
   ¢               :  Convert U to base-2 string
    Ì              :  Get last character
     Ò             :  Subtract the bitwise negation of
      ß            :  A recursive run of the programme with argument U (V remains unchanged)
       °U          :    Increment U
         z         :    Floor divide by 2
          :        :Else
           UnV     :  U subtracted from V
\$\endgroup\$
5
  • 2
    \$\begingroup\$ The missing space in your header is an offense to our new Commonmark overlords! \$\endgroup\$ – Arnauld Jun 18 '20 at 15:02
  • \$\begingroup\$ What missing space, @Arnauld? Noticed it's not being formatted; I'm guessing something's broken in their parser. \$\endgroup\$ – Shaggy Jun 18 '20 at 15:21
  • \$\begingroup\$ Although, it is being formatted in other solutions. Retyped mine from scratch, still the same. Tried h2 instead, still the same. :\ \$\endgroup\$ – Shaggy Jun 18 '20 at 15:23
  • \$\begingroup\$ Our site has been migrated to CommonMark yesterday. The space after a # is now mandatory. \$\endgroup\$ – Arnauld Jun 18 '20 at 15:23
  • 1
    \$\begingroup\$ Ah. Well, that's seems to be a pretty moronic and unnecessary change, particularly the change to headings. \$\endgroup\$ – Shaggy Jun 18 '20 at 15:25
3
\$\begingroup\$

05AB1E, 18 bytes

[ÐÆd#`DÉD½+;‚¼}ƾ+

Inspired by @Arnauld's JavaScript answer, so make sure to upvote him!

Try it online or verify all test cases.

Explanation:

[         # Start an infinite loop:
 Ð        #  Triplicate the pair at the top
          #  (which will use the implicit input in the first iteration)
  Æ       #  Reduce it by subtracting (N-M)
   d      #  If this is non-negative (>=0):
    #     #   Stop the infinite loop
  `       #  Pop and push both values separated to the stack
   D      #  Duplicate the top value `M`
    É     #  Check if it's odd (1 if odd; 0 if even)
      ½   #  If it's 1: increase the counter_variable by 1
     D    #  (without popping by duplicating first)
     +    #  Add this 1/0 to `M`
      ;   #  And halve it
       ‚  #  Then pair it back together with the `N`
 ¼        #  At the end of each iteration, increase the counter_variable by 1
}Æ        # After the infinite loop: reduce by subtracting again (N-M)
  ¾+      # And add the counter_variable to this
          # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

perl -alp, 62 bytes

$;=pop@F;{$_<$;||last;$"+=1+$;%2;$;+=$;%2;$;/=2;redo}$_+=$"-$;

Try it online!

This uses the same logic as most other solutions.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 24 bytes

Nθ⊞υNW¬№υθ≔⁺⊖υ⊗υυI⊖L↨Lυ²

Try it online! Link is to verbose version of code. Takes inputs in the order M, N. Horribly inefficient breadth-first search, so don't bother putting in large numbers. Explanation:

Nθ

Input M.

⊞υN

Push N to the predefined empty list.

W¬№υθ

Repeat until M is present in the list...

≔⁺⊖υ⊗υυ

... concatenate the decremented list with the doubled list.

I⊖L↨Lυ²

Calculate the number of concatenations.

\$\endgroup\$
1
\$\begingroup\$

Batch, 153 bytes

@echo off
@set/an=%1,c=0
:l
@if %n%==%2 echo %c%&exit/b
@set/a"c+=1,p=~-%2/n+1,q=p&p-1,r=n*p-%2,n-=1
@if %q%==0 if %r% lss %p% set/an=n*2+2
@goto l

Explanation:

set /a n=%1, c=0

Initialise n from the first parameter and clear the loop count.

if %n% == %2 echo %c% & exit /b

Output the count once the target in the second parameter is reached.

set /a " c += 1, p = ~-%2 / n + 1, q = p & p - 1, r = n * p - %2, n -= 1
  • Increment the loop count
  • Calculate the number of advances needed
  • Calculate how near to the target advances would get
  • Assume that we'll fall back
if %q% == 0 if %r% lss %p% set /a n = n * 2 + 2

If the advances would get near to the target then undo the fall back and advance instead.

\$\endgroup\$
1
\$\begingroup\$

bc, 61 bytes

define f(n,m){if(n>=m)return n-m;return 1+m%2+f(n,(m+m%2)/2)}

Try it online!

Given n, and m, return n - m if n is greater than or equal to m. Else, it returns 1 plus 1 (if m is odd), plus the result of (n, m / 2), with the division rounded upwards. The latter is done with a recursive call.

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

Befunge-98, 75 bytes

The program keeps a running total of moves at (0, 0) and remembers N at (1, 0). It definitely could be golfed some more.

p&01p&>:01g-0\`|>:2%|
2/1  v  >0g+.@ >^   >
1+2/2v  ^0-\g10<    >
0+g00<^p0

Try it online! Edit: I had to add some extra arrows for it to run on TIO for some reason. See comments.

I used the logic from Arnauld's JavaScript answer.

\$\endgroup\$
6
  • \$\begingroup\$ Do you have a TIO link with an example? If I try that program in TIO, I can't find an input where the program finishes within a minute. Even simple cases like 1 1, or 1 2 seem to run forever. \$\endgroup\$ – Abigail Jun 18 '20 at 0:08
  • \$\begingroup\$ @Abigail I spent awhile trying to get it to run in TIO, but couldn't identify the issue (wrapping around doesn't work correctly?). It works fine locally and also on: qiao.github.io/javascript-playground/… \$\endgroup\$ – Dallan Jun 18 '20 at 0:53
  • \$\begingroup\$ That link is to a Befunge-93 interpreter, not Befunge-98. If I use TIO with Befunge-93, I have some success, that is, some inputs give the right answer, but some inputs seem to get stuck in a loop trying to divide by 0. 666 6666 for instance TIO link \$\endgroup\$ – Abigail Jun 18 '20 at 10:06
  • \$\begingroup\$ Ah, I found the problem. You are writing the input numbers in the Befunge space. But they take a signed tinyint. The TIO interpretation is strict, and putting a 666 into a cell means -102 is actually put there. The link you post allows writing large numbers into cells. \$\endgroup\$ – Abigail Jun 18 '20 at 10:10
  • \$\begingroup\$ @Abigail Thanks for looking into this. According to the specification, Funge-98 programs can have values up to 2bil. I only use Funge-93 commands, but run in Funge-98 to handle the large characters \$\endgroup\$ – Dallan Jun 18 '20 at 13:09
1
\$\begingroup\$

Erlang (escript), 65 bytes

Port of Arnauld's answer.

f(X,Y)->if X>Y->X-Y;true->1+(Y rem 2)+f(X,(Y+(Y rem 2))div 2)end.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

J, 22 bytes

A port of RGS' APL answer with J's hooks and forks.

-`(($:>.@-:)+1+2|])@.<

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.