Get to the Zone!

Question

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!

Ah, my bad. I read that as increase, but it clearly says multiply. Sorry about that. — Adám, Jun 17 '20 at 17:44
It seems like there should be a number theory equivalent to this. — Ross Presser, Jun 18 '20 at 2:05
Could you wrap a bold around the multiply? I read it as increase too! — streetster, Jun 18 '20 at 10:34

Arnauld · Accepted Answer · 2020-06-18 15:50:40Z

23

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.

edited Jun 18 '20 at 15:50

answered Jun 17 '20 at 18:00

Arnauld

139k12 gold badges147 silver badges512 bronze badges

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

add a comment |

Noodle9 · Accepted Answer · 2020-06-17 19:36:32Z

6

C (gcc), ⁵³ 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.

edited Jun 17 '20 at 19:36

answered Jun 17 '20 at 18:51

Noodle9

11.8k2 gold badges15 silver badges33 bronze badges

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

| show 2 more comments

RGS · Accepted Answer · 2020-06-18 16:48:11Z

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.

Zgarb · Accepted Answer · 2020-06-18 18:52:23Z

6

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.

answered Jun 18 '20 at 18:52

Zgarb

41.1k4 gold badges71 silver badges249 bronze badges

\$\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

add a comment |

Jonathan Allan · Accepted Answer · 2020-06-18 23:27:03Z

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

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 :) — Jubayer Abdullah Joy, Jun 18 '20 at 19:51

Shaggy · Accepted Answer · 2020-06-19 15:22:37Z

4

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

edited Jun 19 '20 at 15:22

answered Jun 18 '20 at 12:12

Shaggy

30.1k3 gold badges25 silver badges83 bronze badges

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

add a comment |

Kevin Cruijssen · Accepted Answer · 2020-06-18 06:50:27Z

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)

Abigail · Accepted Answer · 2020-06-18 13:53:54Z

2

perl -alp, 62 bytes

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

Try it online!

This uses the same logic as most other solutions.

answered Jun 18 '20 at 13:53

Abigail

2,8151 silver badge17 bronze badges

add a comment |

Neil · Accepted Answer · 2020-06-18 09:57:06Z

Charcoal, 24 bytes

Ｎθ⊞υＮＷ¬№υθ≔⁺⊖υ⊗υυＩ⊖Ｌ↨Ｌυ²

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:

Ｎθ

Input M.

⊞υＮ

Push N to the predefined empty list.

Ｗ¬№υθ

Repeat until M is present in the list...

≔⁺⊖υ⊗υυ

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

Ｉ⊖Ｌ↨Ｌυ²

Calculate the number of concatenations.

Neil · Accepted Answer · 2020-06-18 10:16:55Z

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.

Abigail · Accepted Answer · 2020-06-18 11:56:13Z

1

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.

answered Jun 18 '20 at 11:56

Abigail

2,8151 silver badge17 bronze badges

add a comment |

Dallan · Accepted Answer · 2020-06-18 13:49:46Z

1

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.

edited Jun 18 '20 at 13:49

answered Jun 17 '20 at 22:38

Dallan

1317 bronze badges

\$\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

| show 1 more comment

user92069user92069 · Accepted Answer · 2020-06-19 12:22:08Z

1

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!

answered Jun 19 '20 at 12:22

user92069

add a comment |

xash · Accepted Answer · 2020-06-19 13:57:22Z

1

J, 22 bytes

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

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

Try it online!

answered Jun 19 '20 at 13:57

xash

6,3671 gold badge8 silver badges23 bronze badges

add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Get to the Zone!

Sample

14 Answers 14

JavaScript (ES6), 30 bytes

How?

C (gcc), ⁵³ 34 bytes

APL (Dyalog Unicode), 24 bytes ^SBCS

Husk, 11 bytes

Explanation

Jelly, 13 bytes

How?

Japt, 15 14 bytes

05AB1E, 18 bytes

perl -alp, 62 bytes

Charcoal, 24 bytes

Batch, 153 bytes

bc, 61 bytes

Befunge-98, 75 bytes

Erlang (escript), 65 bytes

J, 22 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf graph-theory or ask your own question.

Hot Network Questions

Get to the Zone!

Sample

14 Answers 14

JavaScript (ES6), 30 bytes

How?

C (gcc), 53 34 bytes

APL (Dyalog Unicode), 24 bytes SBCS

Husk, 11 bytes

Explanation

Jelly, 13 bytes

How?

Japt, 15 14 bytes

05AB1E, 18 bytes

perl -alp, 62 bytes

Charcoal, 24 bytes

Batch, 153 bytes

bc, 61 bytes

Befunge-98, 75 bytes

Erlang (escript), 65 bytes

J, 22 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf graph-theory or ask your own question.

Related

Hot Network Questions

C (gcc), ⁵³ 34 bytes

APL (Dyalog Unicode), 24 bytes ^SBCS