Zarządzanie zapasami w Minecraft jest trudne. Masz 17 diamentów, ale potrzebujesz 7, aby stworzyć stół zaklęcia, kilof i miecz. Czy bierzesz je i klikasz prawym przyciskiem 7 razy? A może raz prawym przyciskiem myszy i dwa razy prawym przyciskiem myszy i wziąć 7 w lewo? To takie mylące!

^{dla tych z was, którzy są teraz zdezorientowani, nie martw się, wyjaśnię to wszystko za chwilę}

Wyzwanie

Biorąc pod uwagę rozmiar stosu przedmiotów i pożądaną ilość, określ najmniejszą liczbę kliknięć, aby uzyskać tę liczbę. Musisz obsłużyć do 64 dla obu danych wejściowych i możesz założyć, że masz nieskończone miejsca na ekwipunek. Nie można użyć sztuczki przeciągania i rozpowszechniania.

Definicje

Inwentarz jest zbiorem szczeliny w której można przechowywać przedmioty.

Szczelina to przestrzeń do przechowywania w magazynie, w którym można umieścić do jednego typu elementu.

Stos jest liczba elementów umieszczonych w tej samej grupie. Na potrzeby tego wyzwania stos jest po prostu zbiorem przedmiotów w tym samym miejscu (więc zignoruj ​​rozmiar stosu)

Kursor to pointy thingy. Ten kursor. Może zawierać elementy „na nim”; innymi słowy, jeśli klikniesz miejsce i podniosłeś przedmioty, przedmioty, które podniosłeś, są „na kursorze”, dopóki ich nie odłożysz.

Dane techniczne

Istnieją cztery możliwe sytuacje. Albo masz element na kursorze, albo go nie masz, albo klikniesz lewym przyciskiem myszy, albo prawym przyciskiem myszy.

Jeśli nie masz przedmiotu na kursorze, a kliknięcie lewym przyciskiem myszy na polu, podnosi cały stos.

Jeśli nie masz przedmiotu na kursorze i klikniesz miejsce prawym przyciskiem myszy, podnosisz połowę stosu, zaokrąglając w górę.

Jeśli masz element na kursorze i klikniesz lewy przycisk na polu, umieścisz wszystkie elementy w tym polu. (W przypadku wszystkich graczy Minecraft nie będziesz mieć> 64 przedmiotów do tego wyzwania i wszystkie można układać w stosy w 64, a masz tylko jeden typ, więc zamiana przedmiotów nie ma tutaj zastosowania)

Jeśli masz kursor na przedmiot i klikniesz na niego prawym przyciskiem myszy, umieścisz w nim jeden przedmiot.

Tak więc zaczynasz od wszystkich podanych elementów (pierwsze wejście lub drugie; możesz wybrać kolejność) w gnieździe i chcesz zakończyć z żądaną ilością (inne wejście) w kursorze.

Przejrzyjmy przykład. Powiedzmy, że zaczynasz z 17 przedmiotami i chcesz 7. Najpierw kliknij stos prawym przyciskiem myszy, co oznacza, że ​​wybrałeś 9 i jest tam 8. Następnie, jeśli ponownie klikniesz stos prawym przyciskiem myszy, umieścisz jeden przedmiot z powrotem w polu, pozostawiając ci 8, a pole 9. Wreszcie, ponownie kliknij prawym przyciskiem myszy i masz 7, a pole ma 10. Zatem, zwrócisz 3(liczba kliknięć).

^{Jeśli uda ci się wygrać w golfa, proszę powiedz mi, a ja wyedytuję przykład: P}

Przypadki testowe

Są one generowane ręcznie, więc proszę o informację, czy są jakieś błędy. Zarządzam zapasami poprzez kliknięcie jittera prawym przyciskiem myszy, więc nie mam doświadczenia w optymalnym zarządzaniu zapasami: 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

Objaśnienia

To wyzwanie może być trudne dla graczy spoza Minecrafta, nie mam pojęcia. Oto kilka wyjaśnień.

64, 8 -> 5 ponieważ podnosisz 32 za pomocą kliknięcia prawym przyciskiem myszy, odkładasz go, podnosisz 16, odkładasz, a następnie podnosisz 8.

63, 8 -> 5 z tego samego powodu.

25, 17 -> 7 ponieważ podnosisz 13, odkładasz, odrywasz 6 z resztek 12, umieszczasz 2 z powrotem na stosie resztek, a następnie umieszczasz 4 w kursorze na 13, a następnie podnosisz je.

Zasady

• Obowiązują standardowe luki
• Możesz to założyć 0 <= desired <= given <= 64
• Możesz przyjmować dane wejściowe w dowolnej kolejności i wykonywać operacje we / wy w dowolnym rozsądnym formacie

C ++ , 498 482 457 bajtów

Jeśli ta funkcja zostanie wywołana tylko raz, może mieć 455 bajtów.

Przekonałem się, że prawie wszystkie internetowe kompilatory GCC (w tym TIO) zabraniają mi pomijania typu funkcji f. Jednak GCC na moim komputerze pozwala na to i nie wiem dlaczego.

Ten może obsłużyć duże dane wejściowe, jeśli gniazdo może zawierać taką liczbę elementów (choć wymaga większej tablicy i prawdopodobnie skończy się czas).

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

Nie golfowany:

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

Galaretka , 74 bajty

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

Pełny program z pierwszym wejściem (3. argument) bieżącym stosem, a drugim wejściem (4. argument) pożądany kursor.

Wypróbuj online! Ze względu na implementację osiąga to 60-sekundowy limit czasu TIO dla25, 17przypadku testowego. Można temu zaradzić, usuwając nadmiarowość pozostawioną do gry w golfa za pomocą 84 bajtów (która odfiltrowuje stosy o zerowej wielkości i sortuje te, które pozostałyḟ€Ṣ¥0¦€0na końcu łącza 6 i zachowuje unikalne stany na każdym kroku przy użyciuQ$w Main połączyć).

W jaki sposób?

Program implementuje zdefiniowaną maszynę stanu.
Tworzy stan pierwotny, [0, [argument 1]]
a następnie wielokrotnie przechodzi do wszystkich następnych możliwych stanów,
aż zostanie znaleziony pasujący [argument 2, [...]].

_{Uwaga: pozycja programu znajduje się pod „linkiem głównym”, który jest najniższy ( 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)