5
$\begingroup$

Story Setup

It's Percy the Pelican's first day running the front desk of his master's magical pebble shop. His job is to fetch pebbles from the stock room to fulfill customer orders.

The stock room has a pile containing 999 pebbles, and his master has set up an enchantment to refill the pile between customers. Because of the energy requirement and potentially hazardous side effects of the restock enchantment, Percy is only allowed to use it when there are no customers in the store.

Customers will always place an order between 1 and 999 pebbles. To fetch pebbles from the stock room, Percy can either carry a single pebble with his feet, or use his fledgling magical talents to scoop up either all or half (rounded up) of the pebbles from the pile in his beak, no matter how large the pile is. He then deposits the pebbles he was carrying on a pile in the front room. Percy can also carry pebbles from the front room back to the stock room in the same manner.

Regardless of how many pebbles he's carrying, Percy always takes one minute to travel between rooms. Percy can also choose not to carry any pebbles, but this still takes one minute. Percy always starts in the front room, and must end in the front room in order to complete the sale.

Percy's master has a strict "Fulfillment in 15 Minutes or Your Order Is Free" policy, and Percy suspects that his rival, Barry the Badger, is going to try to make a difficult order that will force him to take more than 15 minutes. Through studying the restock enchantment, Percy has found a way to divert some of the pebbles from the store room to the front room, so that the 999 pebbles are divided between the two rooms whenever the stock is reset. He'll only be able to modify the enchantment once, before any customers arrive for the day.

What is the minimum number of pebbles Percy will need to divert to be able to fulfill any order between 1 and 999 in less than 15 minutes?

Summary and Clarifications

  1. When an order is placed, there are initially 999 pebbles divided between the store room and the front room. Percy always starts in the front room.

  2. Percy can grab 0, 1, All, or Half (rounded up) of the pebbles in the room he's in and take them to the other room. This movement always takes a minute.

  3. To fulfill an order, the front room needs to have the exact number of pebbles requested, all other pebbles must be in the store room, and Percy must be in the front room.

  4. Percy needs to know the minimum number of pebbles that should be diverted to the front room whenever the stock is reset in order to fulfill any order between 1 and 999 pebbles in less than 15 minutes.


This puzzle was originally inspired by the inventory mechanics of Stardew Valley, where items can be shifted between inventories either one at a time, all at once, or by splitting a stack in half, and the maximum stack size is 999.

$\endgroup$

1 Answer 1

4
$\begingroup$

The answer is

336.

I got the answer by

dynamic programming.

Fun trivia:

All numbers from 336 to 815 (inclusive) work (so there are 480 of them) (and these are the only ones). If you choose 0, then there are 32 ways to fail.

Details:

We will do this in Python. First, we make some imports and set some fixed parameters. Then, we set the Front-to-Back-Move (FBM) and Back-to-Front Move (BFM) matrices. These are fixed matrices that denote valid moves. Specifically, FBM[i, j] is True if and only if, starting with i pebbles in the front room, Percy can move some (or zero) pebbles from the front room to the back room such that the front room ends with j pebbles. On the other hand, BFM[i, j] is True if and only if, starting with i pebbles in the front room, Percy can move some (or zero) pebbles from the back room to the front room such that the front room ends with j pebbles.


 import numpy as np
 import math
 NUM_PEBBLES = 999
 MAX_ROUND_TRIPS = 7
 N = NUM_PEBBLES + 1

 def front_to_back(n):
     return [n, max(0, n - 1), n // 2, 0]
 # Setting the Front-to-Back-Move (FBM) Matrix
 FBM = np.full((N, N), False)
 for i in range(N):
     FBM[i, front_to_back(i)] = True

 def back_to_front(n):
     return [n, min(NUM_PEBBLES, n + 1), n + math.ceil((NUM_PEBBLES - n) / 2), NUM_PEBBLES]
 # Setting the Back-to-Front-Move (BFM) Matrix
 BFM = np.full((N, N), False)
 for i in range(N):
     BFM[i, back_to_front(i)] = True
 

The Reachable matrix is iteratively updated. We initialise it as the identity because if we allow zero minutes, then we can only fulfill the order if the requested number is exactly equal to the initial number of pebbles in the front room.

We iterate 14 times (7 each way). Before we execute R[source] = np.any(FBM[R[source], :], axis=0), the row R[source] are the "reachable" indices, starting from the source index, before doing the current iteration. So FBM[R[source], :] applies another front-to-back move, which is the current iteration. Then, np.any() takes the logical or over all valid moves. We then update R[source].


 # Initialising the Reachable (R) Matrix as Identity to start the iteration
 R = np.eye(N, dtype=bool)

 # Main iterations
 for _ in range(MAX_ROUND_TRIPS):
     for source in range(N):
         R[source] = np.any(FBM[R[source], :], axis=0)
     for source in range(N):
         R[source] = np.any(BFM[R[source], :], axis=0)

 # Results
 np.argmax(np.all(R, axis=1)) # 336
 

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.