La gestión del inventario de Minecraft es difícil. Tienes 17 diamantes, pero necesitas 7 para crear una mesa de encantamiento, un pico y una espada. ¿Los recoges y haces clic derecho 7 veces? ¿O haces clic derecho una vez y haces clic derecho dos veces y tomas el 7 izquierdo? ¡Es muy confuso!

^{para aquellos de ustedes que ahora están confundidos, no se preocupen, lo explicaré todo en un segundo}

Desafío

Dado el tamaño de una pila de artículos y la cantidad deseada, determine la menor cantidad de clics para obtener esa cantidad. Solo necesita manejar hasta 64 para ambas entradas y puede asumir que tiene ranuras de inventario infinitas. No puedes usar el truco de arrastrar para distribuir.

Definiciones

El inventario es una colección de máquinas tragamonedas donde puede almacenar artículos.

Una ranura es un espacio de almacenamiento en su inventario donde puede colocar hasta un tipo de artículo.

Una pila es una cantidad de elementos colocados en el mismo grupo. Para los propósitos de este desafío, una pila es simplemente un montón de artículos en el mismo lugar (ignore el tamaño de la pila)

El cursor es tu cosita puntiaguda. Ese cursor Puede tener elementos "en él"; en otros términos, si hizo clic en una ranura y recogió elementos, los elementos que recogió están "en el cursor" hasta que los suelte.

Especificaciones

Hay cuatro situaciones posibles. O tiene un elemento en el cursor o no, y o bien hizo clic con el botón izquierdo o derecho.

Si no tiene un elemento en el cursor y hace clic con el botón izquierdo en una ranura, recoge toda la pila.

Si no tiene un elemento en su cursor y hace clic derecho en una ranura, recoge la mitad de la pila, redondeada.

Si tiene un elemento en el cursor y hace clic con el botón izquierdo en una ranura, coloca todos los elementos en esa ranura. (Para todos los jugadores de Minecraft, no tendrás> 64 elementos para este desafío y todos son apilables en 64, y solo tienes un tipo, por lo que el intercambio de elementos no se aplica aquí)

Si tiene un elemento en el cursor y hace clic derecho en una ranura, coloca un elemento en esa ranura.

Entonces, comienza con todos los elementos proporcionados (primera entrada o segunda; puede elegir el orden) en una ranura, y desea terminar con la cantidad deseada (otra entrada) en su cursor.

Veamos un ejemplo. Digamos que comienza con 17 elementos y desea 7. Primero, haga clic derecho en la pila, lo que significa que ha recogido 9 y hay 8 en esa ranura. Luego, si vuelve a hacer clic derecho en la pila, vuelve a colocar un elemento en la ranura, dejándolo con 8 y la ranura con 9. Finalmente, vuelve a hacer clic derecho y tiene 7 y la ranura tiene 10. Por lo tanto, devolvería 3(el número de clics).

^{Si logra hacer clic fuera de mi campo de golf, dígame y editaré el ejemplo: P}

Casos de prueba

Estos se generan manualmente, así que dígame si hay algún error. Hago gestión de inventario haciendo clic derecho con jitter, así que no tengo experiencia con una gestión de inventario óptima: 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

Explicaciones

Este desafío puede ser complicado para los jugadores que no son de Minecraft, no tengo idea. Aquí hay algunas explicaciones.

64, 8 -> 5 porque recoge 32 utilizando el botón derecho, colóquelo, recoja 16, colóquelo y luego levante 8.

63, 8 -> 5 por la misma razón.

25, 17 -> 7 porque recoges 13, lo colocas hacia abajo, recoges 6 del resto 12, colocas 2 nuevamente en la pila de restos y luego colocas el 4 en el cursor dentro del 13, y luego los recoges.

Reglas

• Se aplican lagunas estándar
• Puedes suponer que 0 <= desired <= given <= 64
• Puede tomar la entrada en cualquier orden y hacer E / S en cualquier formato razonable

C ++ , 498 482 457 bytes

Si esta función solo se llama una vez, puede tener 455 bytes.

Descubrí que casi todos los compiladores de GCC en línea (incluido TIO) me prohíben omitir el tipo de función f. Sin embargo, el GCC en mi computadora lo permite, y no sé por qué.

Este puede manejar entradas grandes si una ranura puede contener ese número de elementos (aunque necesita una matriz más grande y probablemente se quedará sin tiempo).

#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)}}}}

Sin golf:

#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
        }
    }
}

Jalea , 74 bytes

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

Un programa completo con la primera entrada (tercer argumento) la pila actual y la segunda entrada (cuarto argumento) el cursor deseado.

Pruébalo en línea! Debido a la implementación, esto alcanza el tiempo de espera TIO de 60 segundos para el25, 17caso de prueba. Esto puede remediarse eliminando las redundancias que quedan para el golf utilizando este 84 byter (que filtra las pilas de tamaño cero y clasifica las que quedanḟ€Ṣ¥0¦€0al final del enlace 6 y solo mantiene estados únicos en cada paso con el uso deQ$Main enlace).

¿Cómo?

El programa implementa la máquina de estado definida.
Crea el estado original y [0, [argument 1]]
luego
pasa a todos los siguientes estados posibles repetidamente hasta encontrar uno que coincida [argument 2, [...]].

_{Nota: la entrada del programa se encuentra en el "Enlace principal", que es el más inferior ( 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)