Die Bestandsverwaltung von Minecraft ist schwierig. Du hast 17 Diamanten, aber du brauchst 7, um einen Verzauberungstisch, eine Spitzhacke und ein Schwert herzustellen. Heben Sie sie auf und klicken Sie 7 Mal mit der rechten Maustaste? Oder klicken Sie einmal mit der rechten Maustaste und zweimal mit der rechten Maustaste und nehmen Sie die 7 nach links? Es ist so verwirrend!

^{Für diejenigen unter Ihnen, die jetzt verwirrt sind, keine Sorge, ich werde alles in einer Sekunde erklären}

Herausforderung

Bestimmen Sie angesichts der Größe eines Stapels von Elementen und einer gewünschten Menge die geringste Anzahl von Klicks, um diese Menge zu erhalten. Sie müssen nur bis zu 64 für beide Eingaben verarbeiten und können davon ausgehen, dass Sie über unendlich viele Inventarplätze verfügen. Sie können den Drag-to-Distribute-Trick nicht verwenden.

Definitionen

Das Inventar ist eine Sammlung von Slots, in denen Sie Gegenstände aufbewahren können.

Ein Steckplatz ist ein Speicherplatz in Ihrem Inventar, in dem Sie bis zu einem Artikeltyp platzieren können.

Ein Stapel ist eine Anzahl von Elementen, die in derselben Gruppe platziert sind. Für die Zwecke dieser Herausforderung besteht ein Stapel einfach aus mehreren Elementen an derselben Stelle (ignorieren Sie also die Stapelgröße).

Der Cursor ist dein spitzes Ding. Dieser Cursor. Es kann Gegenstände "drauf" haben; Mit anderen Worten: Wenn Sie auf einen Steckplatz geklickt und Gegenstände aufgenommen haben, befinden sich die aufgenommenen Gegenstände "auf dem Cursor", bis Sie sie ablegen.

Spezifikationen

Es gibt vier mögliche Situationen. Entweder haben Sie ein Element auf Ihrem Cursor oder Sie tun es nicht, und entweder haben Sie mit der linken Maustaste oder mit der rechten Maustaste geklickt.

Wenn Sie kein Element auf Ihrem Cursor haben und mit der linken Maustaste auf einen Steckplatz klicken, nehmen Sie den gesamten Stapel auf.

Wenn Sie kein Element auf Ihrem Cursor haben und mit der rechten Maustaste auf einen Steckplatz klicken, nehmen Sie die Hälfte des Stapels aufgerundet auf.

Wenn Sie ein Element auf Ihrem Cursor haben und mit der linken Maustaste auf einen Steckplatz klicken, platzieren Sie alle Elemente in diesem Steckplatz. (Für alle Minecraft-Spieler stehen für diese Herausforderung keine> 64 Gegenstände zur Verfügung, und alle sind 64-stapelbar. Sie haben nur einen Typ, sodass der Gegenstandsaustausch hier nicht gilt.)

Wenn Sie einen Gegenstand auf Ihrem Cursor haben und mit der rechten Maustaste auf einen Steckplatz klicken, platzieren Sie einen Gegenstand in diesem Steckplatz.

Sie beginnen also mit allen angegebenen Elementen (erste Eingabe oder zweite; Sie können die Reihenfolge auswählen) in einem Slot und möchten mit der gewünschten Menge (andere Eingabe) in Ihrem Cursor fertig werden.

Lassen Sie uns ein Beispiel durchgehen. Angenommen, Sie beginnen mit 17 Elementen und möchten 7. Zuerst klicken Sie mit der rechten Maustaste auf den Stapel, was bedeutet, dass Sie 9 aufgenommen haben und sich 8 in diesem Steckplatz befinden. Wenn Sie dann erneut mit der rechten Maustaste auf den Stapel klicken, legen Sie einen Gegenstand wieder in den Steckplatz, sodass Sie 8 und der Steckplatz 9 haben. Schließlich klicken Sie erneut mit der rechten Maustaste und Sie haben 7 und der Steckplatz hat 10. Somit Sie würden zurückkehren 3(die Anzahl der Klicks).

^{Wenn Sie es schaffen, mich zu übertreffen, sagen Sie es mir bitte und ich werde das Beispiel bearbeiten: P.}

Testfälle

Diese werden manuell generiert. Bitte teilen Sie mir mit, ob Fehler vorliegen. Ich mache die Bestandsverwaltung durch Klicken mit der rechten Maustaste, damit ich keine Erfahrung mit der optimalen Bestandsverwaltung habe: 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

Erklärungen

Diese Herausforderung könnte für Nicht-Minecraft-Spieler schwierig sein, ich habe keine Ahnung. Hier sind einige Erklärungen.

64, 8 -> 5 weil Sie 32 mit einem Rechtsklick aufnehmen, legen Sie es ab, nehmen Sie 16 auf, legen Sie es ab und nehmen Sie dann 8 auf.

63, 8 -> 5 aus dem gleichen Grunde.

25, 17 -> 7 weil du 13 aufnimmst, lege es ab, nimm 6 von den verbleibenden 12 auf, lege 2 zurück in den übrig gebliebenen Stapel und setze dann die 4 in den Cursor in die 13 und nimm diese dann auf.

Regeln

• Es gelten Standardlücken
• Sie können das annehmen 0 <= desired <= given <= 64
• Sie können Eingaben in beliebiger Reihenfolge vornehmen und E / A in einem beliebigen vernünftigen Format ausführen

C ++ , 498 482 457 Bytes

Wenn diese Funktion nur einmal aufgerufen wird, können es 455 Bytes sein.

Ich fand heraus, dass fast jeder Online-GCC-Compiler (einschließlich TIO) mir verbietet, den Typ der Funktion wegzulassen f. Das GCC auf meinem Computer erlaubt dies jedoch, und ich weiß nicht warum.

Dieser kann große Eingaben verarbeiten, wenn ein Steckplatz diese Anzahl von Elementen enthalten kann (obwohl er ein größeres Array benötigt und wahrscheinlich keine Zeit mehr hat).

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

Gelee , 74 Bytes

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

Ein vollständiges Programm mit der ersten Eingabe (3. Argument) des aktuellen Stapels und der zweiten Eingabe (4. Argument) des gewünschten Cursors.

Probieren Sie es online aus! Aufgrund der Implementierung wird das 60-Sekunden-TIO-Timeout für den25, 17Testfall erreicht. Dies kann behoben werden, indem die für das Golfen verbleibenden Redundanzen mit diesem 84-Byter entfernt werden (der Stapel mitḟ€Ṣ¥0¦€0derGröße Null herausfiltert und dieam Ende von Link 6verbleibenden Stapel sortiertund bei jedem Schritt nur eindeutige Zustände bei Verwendung vonQ$im Main beibehält Verknüpfung).

Wie?

Das Programm implementiert die definierte Zustandsmaschine.
Es erstellt den ursprünglichen Zustand und wechselt [0, [argument 1]]
dann wiederholt zu allen nächsten möglichen Zuständen,
bis einer gefunden wird, der übereinstimmt [argument 2, [...]].

_{Hinweis: Der Programmeintrag befindet sich unter dem "Hauptlink", dem untersten ( 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)