Minecraft Inventory Management

Question

Minecraft inventory management is hard. You have 17 diamonds, but you need 7 to craft an enchantment table, a pickaxe, and a sword. Do you pick them up and right click 7 times? Or do you right click once and right click twice and take the 7 left? It's so confusing!

^{for those of you who are now confused, don't worry, I'll explain it all in a sec}

Challenge

Given the size of a stack of items and a desired amount, determine the least number of clicks to get that amount. You only need to handle up to 64 for both inputs and you may assume you have infinite inventory slots. You cannot use the drag-to-distribute trick.

Definitions

The inventory is a collection of slots where you can store items.

A slot is a storage space in your inventory where you can place up to one type of item.

A stack is a number of items placed in the same group. For the purposes of this challenge, a stack is simply a bunch of items in the same place (so ignore stack-size)

The cursor is your pointy thingy. That cursor. It can have items "on it"; in other terms, if you clicked on a slot and picked up items, the items you picked up are "on the cursor" until you put them down.

Specifications

There are four possible situations. Either you have an item on your cursor or you don't, and either you left click or you right click.

If you don't have an item on your cursor and you left-click on a slot, you pick up the entire stack.

If you don't have an item on your cursor and you right-click on a slot, you pick up half the stack, rounded up.

If you have an item on your cursor and you left-click on a slot, you place all of the items into that slot. (For all you Minecraft players, you won't have >64 items for this challenge and they're all 64-stackable, and you only have one type so the item swap does not apply here)

If you have an item on your cursor and you right-click on a slot, you place one item into that slot.

So, you start with all of the items given (first input, or second; you may choose the order) in a slot, and you want to finish with having the desired amount (other input) in your cursor.

Let's run through an example. Say you start with 17 items and you want 7. First, you right-click on the stack, which means you have picked up 9 and there are 8 in that slot. Then, if you right-click on the stack again, you place one item back into the slot, leaving you with 8 and the slot with 9. Finally, you right-click again and you have 7 and the slot has 10. Thus, you would return 3 (the number of clicks).

^{If you manage to out-click-golf me, please tell me and I will edit the example :P}

Test Cases

These are manually generated, so please tell me if there are any errors. I do inventory management through jitter-clicking right click so I don't have experience with optimal inventory management :P

Given, Desired -> Output
17, 7 -> 3
64, 8 -> 5
63, 8 -> 5
10, 10 -> 1
10, 0 -> 0 # note this case
25, 17 -> 7

Explanations

This challenge might be tricky for non-Minecraft players, I have no idea. Here are some explanations.

64, 8 -> 5 because you pick up 32 using right click, place it down, pick up 16, place it down, then pick up 8.

63, 8 -> 5 for the same reason.

25, 17 -> 7 because you pick up 13, place it down, pick up 6 from the leftover 12, place 2 back into the leftover stack, and then place the 4 in the cursor into the 13, and then pick those up.

Rules

• Standard loopholes apply
• You may assume that 0 <= desired <= given <= 64
• You may take input in either order and do I/O in any reasonable format

Answer 1

C++, 498 482 457 bytes

If this function is just called once, it can be 455 bytes.

I found that almost every online GCC compilers (including TIO) forbids me to omit the type of the function f. However, the GCC on my computer allows that, and I don't know why.

This one can handle large inputs if a slot can contain that number of items (though needs a larger array and will probably run out of time).

#import<bits/stdc++.h>
#define t N.first
#define X n.erase(n.find
#define p(c){if(c==r)return l;if(L.emplace(w={n,c},l).second)Q[U++]=w;}
#define T(S,C)n.insert(S);p(C)X(S));
using m=std::multiset<int>;using s=std::pair<m,int>;s Q[99999];int x,l,B,U;int f(int a,int r){if(!r)return 0;std::map<s,int>L;s f({a},B=0),w,N;L[Q[U=1]=f];for(;;){l=L[N=Q[B++]]+1;x=N.second;t.insert(0);for(int i:t){m n=t;X(i));if(x){T(i+x,0)T(i+1,x-1)}if(!x&&i){p(i)T(i/2,i-i/2)}}}}

Ungolfed:

#include <map>
#include <set>
#include <queue>
#include <iostream>

using namespace std;

struct state {
    multiset<int> t; int q;
    bool operator<(const state& i) const { return make_pair(t, q) < make_pair(i.t, i.q); }
};

int f(int a, int target) {
    if (target == 0) return 0;

    map<state, int> len;
    queue<state> qu;
    state first = {{a}, 0};
    qu.push(first);
    len[first] = 0;

    #define push(c) { state a = {n, c}; auto t = len.insert({a, l + 1}); if (t.second) { \
        if (a.q == target) return l + 1; qu.push(a); \
    } } // push new state into queue and check for termination
    #define next(stk, cur) { n.insert(stk); push(cur); n.erase(n.find(stk)); }
    // insert new stack, push new state, erase the stack (for another use)

    while (qu.size()) { // BFS cycle
        state now = qu.front();
        qu.pop();

        int q = now.q;
        int l = len[now];

        multiset<int> n(now.t);
        for (int i : now.t) { // click on non-empty stack
            n.erase(n.find(i));
            if (!q) { // nothing on cursor
                push(i); // click left
                next(i / 2, (i + 1) / 2); // click right
            }
            else { // item on cursor
                next(i + q, 0); // click left
                next(i + 1, q - 1); // click right
            }
            n.insert(i);
        }
        if (q) { // click on empty stack
            next(q, 0); // click left
            next(1, q - 1); // click right
        }
    }
}

Answer 2

Jelly, 74 bytes

Ẏċ⁴¬
HĊ,$Ḟµ€1¦€F€;⁸Ḣ,$€
‘1¦€ṭ€⁹’¤
+1¦€⁹ṭ€0;ç
⁹Ȧ‘Ḥ¤ŀ
Ṫ;0ṙJ$çḢ
Wṭ0WÇ€Ẏ$ÑпL’

A full program with first input (3rd argument) the current stack and the second input (4th argument) the wanted cursor.

Try it online! Due to the implementation this hits the 60 second TIO time out for the 25, 17 test case. This may be remedied by removing the redundancies left in for golfiness using this 84 byter (which filters out zero-sized stacks and sorts those remaining with ḟ€Ṣ¥0¦€0 at the end of link 6 and only keeps unique states at each step with the use of Q$ in the Main link).

How?

The program implements the defined state-machine.
It creates the original state [0, [argument 1]]
then steps through to all the next possible states repeatedly
until one is found matching [argument 2, [...]].

_{Note: the program entry is at the "Main link" which is the bottommost one (Wṭ0WÇ€Ẏ$ÑпL’)}

Ẏċ⁴¬ - Link 1, test a list of states for not having the desired cursor
Ẏ    - tighten by one
  ⁴  - program's fourth argument (second input) - desired cursor
 ċ   - count occurrences (the stack list will never match, so just inspecting the cursors)
   ¬ - logical negation

HĊ,$Ḟµ€1¦€F€;⁸Ḣ,$€ - Link 2, next states given a 0 cursor: list, rotatedStacks; number currentCursor (unused)
     µ€1¦€         - for each rotation of rotatedStacks apply to the first element:
H                  -   halve
   $               -   last two links as a monad
 Ċ                 -     ceiling
  ,                -     pair
    Ḟ              -   floor (vectorises) -- i.e. n -> [floor(ceil(n/2)),floor(n/2)]
                                                     = [ceil(n/2),floor(n/2)]
          F€       - flatten each -- i.e. each [[c1,f1],s2, s3,...] -> [c1,f1,s2,s3,...]
             ⁸     - chain's left argument, rotatedStacks
            ;      - concatenate -- i.e. [[c1,f1,s2,s3,...],[c2,f2,s3,...,s1],...,[s1,s2,s3,...],[s2,s3,...,s1],...]
                $€ - last two links as a monad for each:
              Ḣ    -   head
               ,   -   pair -- i.e. [c1,f1,s2,s3,...] -> [c1,[f1,s2,s3,...]]

‘1¦€ṭ€⁹’¤ - Link 3, next states given a non-0 cursor and a right-click: list, rotatedStacks; number currentCursor
 1¦€      - for each rotation of rotatedStacks apply to the first element:
‘         -   increment -- i.e. place an item into the first stack of each rotation
        ¤ - nilad followed by link(s) as a nilad:
      ⁹   -   chain's right argument -- currentCursor
       ’  -   decrement
    ṭ€    - tack each -- i.e. [s1-1,s2,s2,...] -> [currentCursor-1,[s1-1,s2,s2,...]]

+1¦€⁹ṭ€0;ç - Link 4, next states given a non-0 cursor: list, rotatedStacks; number currentCursor
 1¦€       - for each rotation of rotatedStacks apply to the first element:
    ⁹      -   chain's right argument -- currentCursor
+          -   add
     ṭ€0   - tack each to zero -- i.e. [s1+currentCursor,s2,s3,...] -> [0,[s1+currentCursor,s2,s3,...]]
         ç - call the last link (3) as a dyad -- get the right-click states
        ;  - concatenate

⁹Ȧ‘Ḥ¤ŀ - Link 5, next states: list, rotatedStacks; number currentCursor
     ŀ - call link at the given index as a dyad...
    ¤  -   nilad followed by link(s) as a nilad:
⁹      -     chain's right argument -- currentCursor
 Ȧ     -     any & all -- for our purposes zero if zero, one if not
  ‘    -     increment
   Ḥ   -     double
       - -- i.e. call link 2 if currentCursor is zero else call link 4

Ṫ;0ṙJ$çḢ - Link 6, next states: currentState  e.g. [cc, [s1, s2, s3, ...]]
Ṫ        - tail -- get the stacks, [s1, s2, s3, ...]
 ;0      - concatenate a zero - add an empty stack to the options for use
     $   - last two links as a monad for each:
    J    -   range(length)
   ṙ     -   rotate left by -- i.e. [[s2,s3,0,...,s1],[s3,0,...,s1,s2],[0,...,s1,s2,s3],[...,s1,s2,s3,0],...[s1,s2,s3,0,...]]
       Ḣ - head -- get the currentCursor, cc
      ç  - call the last link (5) as a dyad

Wṭ0WÇ€Ẏ$ÑпL’ - Main link: initialStack, requiredCursor
W             - wrap -- [initialStack]
 ṭ0           - tack to zero -- [0, [initialStack]]
   W          - wrap -- [[0, [initialStack]]]
         п   - loop while, collecting the results:
        Ñ     - ...condition: call next link (1) as a monad -- cursor not found
       $      - ...do: last two links as a monad:
    ǀ        -   call the last link (6) as a monad for each
      Ẏ       -   flatten the resulting list by one level
           L  - length
            ’ - decremented (the collect while loop keeps the input too)