30 June 2018 Tagged: eulorapython

The focus of my recent work has been on reliable mining automation. One missing piece is a solution to the abundance of mining outputs of differing qualities that quickly fill all available table slots.

One proposed solution is a stacking algorithm that separates resources first into bands of quality (specified by the user) and then carefully steps through a stacking procedure. A careful procedure is needed because when you stack piles of resources with different qualities the resulting quality of that stacked pile is an averaging based on quality and quantity that rounds down any decimal remainder to an integer. This rounding down amounts to lost value and so to avoid losing value you must only stack in round numbers, as it were.

This careful procedure is going to be messy to write, once I’ve wrapped each step in 1) wait time for server round trip 2) coordination between state machine code and server message handling code 3) error handling / recovery code.

Before I get too far down that road I decided to implement the lossless stacking algo independently in python to make it possible for me to get quicker feedback about the correctness of my assumptions and my understanding of the problem.

Usage

stacker.py reads lines from stdin, treats each line as a specification of a table, losslessly stacks down everything in the table to the minimum number of slots, and prints out a specification of the resulting table.

The specification format of a table is any number of slots separated by a space. The format of a slot is AxBq where A is an integer quantity and B is an integer quality. For example: 200x1000q indicates a slot that contains 200 items of 1000 quality.

Basic Usage
python stacker.py < stacker.txt

If in the above example stacker.txt has the following contents:

Stacker Test File
44x103q 101x102q 15x104q 12x105q
44x103q 101x102q 15x104q 12x105q 44x107q 11x106q

then the output will be:

Stacker Test Output
110x103q 62x102q
147x104q 80x103q

There is also a verbose mode that lists every stack movement and the table state after each move.

Verbose Usage
python stacker.py -v < stacker.txt

Assumptions

This code is based on the assumption that separating stacks of different item types, and separating items in different quality bands has already been done. Those separations are trivial to implement and orthogonal to the stacking problem. Therefore all stacks are assumed to be same-item and same-band.

Algorithm

The ordered steps for finding the next one move, at a high level, are as follows:

  • If there are two slots with items if the same quality, move all the items in the higher numbered slot onto the lower.

  • Find the pair of slots that has both even quality (or both odd), has primarily the largest difference in quality and secondarily contains an element with the minimum quantity.

  • If found, move items from the higher quantity stack to the lower quantity slot. The number of items to move is equal to the number of items in the lower quantity slot.

  • If not found, terminate.

The approach is, at worst, near optimal with respect to the number of slot movements required. It may be optimal, but I haven’t taken the time to prove it.


Add a Comment