Merging xyz integer blocks with unknown values and occurances

Question

Im currently building a block system for a project im working on. Each block has an occurance value and three integer values (x, y, z) example (4, 2, 3) * 6. Each block can merge with another block if their xyz components match completely (4,2,3)*6, (4,2,3)*5 ->(4,2,3)*11. The catch is, some of the values in the blocks xyz components can be unknown meaning they can be whatever value they want, denoted as "n". Note: all occurance rates are always known and can't be "n". If the unknown values collapse to make the block equivalent to another, they can be merged (4,2,3)*4 merge (4,2,n)*2: if n=3, blocks can merge (4,2,n=3) -> (4,2,3)*6. The example table I've been using as a mental model so far has been:

(1, 5, n) * occurance
(2, 5, 2) * occurance
(2, 5, n) * occurance
(1, n, n) * occurance
(3, 1, 4) * occurance
(4, 0, 0) * occurance
(n, 2, n) * occurance
(n, n, n) * occurance

The occurance value has a stride length in bits given the most

floor(log2(all occurance values) + 1)

Since this storage medium is in binary, max of all occurances = 7 (0b111) means the stride of all amounts is 3 bits to store their occurance rates.

The main problem: For now, let's single out these three blocks.

(1, 5, n) * a
(1, n, n) * b
(n, 2, n) * c

These values could collapse either to

(1,  5,  n) * a -> Merge
(1, <5>, n) * b -> Merge
(n,  2,  n) * c

or

( 1,  5,  n) * a
( 1, <2>, n) * b -> Merge
(<1>, 2,  n) * c -> Merge

Which I would like to merge the most blocks together resulting in the least blocks used while also merging the blocks in a way that keeps the max occurances as low as possible as to not add another bit to store the occurances.

With the full scope, this has been a good staring at the page trying to not implement in n^k iterations

I've thought about culling the XYZ unique values since you don't need to brute force test values that aren't in the column of the current value, but if there's an unknown "n" in said column, This technique is out the window :/

Side note: any "n" values that evaluate without meaningful or undefined values can collapse to zero. example (1,5,n) should collapse to (1,5,0) at the end of all evaluations.

Any help would be greatly appreciated!

Answer 1

Assuming that you have many blocks ( > 500 ) then a worthwhile approximation would be to focus only on merges that give exactly 7 occurrences.

Assign the blocks into 7 containers according to their occurrence numbers.

Loop over pairs of containers that sum to seven ( 6,1 ) ( 5,2 ) ( 4,3 )

Loop over pairs blocks in the two containers.

IF match is possible, do match, storing result in 7 occurrence container and deleting the matching blocks from their containers.

This will leave undone some matches that result in less than 7 occurrences. You will have to decide whether it is worthwhile to go after these by repeating the algorithm on the remaining unmatched blocks aiming of 6, 5, 4, occurrences.

Here are the results from a sample run

Input:
( 1, 5, -1) * 1
( 2, 5, -1) * 1
( 3, 1, 4) * 1
( -1, 2, -1) * 1
( 2, 5, 2) * 6
( 1, -1, -1) * 6
( 4, 0, 0) * 6
( -1, -1, -1) * 6

match ( 1, 5, -1) * 1 and ( 1, -1, -1) * 6 => ( 1, 5, -1) * 7

match ( 2, 5, -1) * 1 and ( 2, 5, 2) * 6 => ( 2, 5, 2) * 7

match ( 3, 1, 4) * 1 and ( -1, -1, -1) * 6 => ( 3, 1, 4) * 7

results:
( -1, 2, -1) * 1
( 4, 0, 0) * 6
( 1, 5, -1) * 7
( 2, 5, 2) * 7
( 3, 1, 4) * 7

Main C++ code to match containers

void matchContainers( int c1, int c2 )
{
    // loop over blocks in container 1
    for (auto &b1 : vb[c1])
    {
        // loop over blocks in container 2
        for (auto &b2 : vb[c2])
        {
            // atempt match
            if( b1.match(b2) )
                {
                    // succesful match
                    // move match to 7 occurence container
                    vb[7].push_back( b1 );
                    b1.count = -1;
                }
        }
    }
}

main()
{
    createSampleProblem();
    display();

    matchContainers( 1, 6 );
    matchContainers( 2, 5 );
    matchContainers( 3, 4 );

    std::cout << "\nresults:\n";
    display();

    return 0;
}

C++ code for block matching method

/* @brief try matching with another block
   @param other block
   @return true if merge successful

   On merge the other block will be marked deleted
   and the attributes of this block updated to the merged block
*/
bool cBlock::match( cBlock &other)
{
    // check for already matched blocks
    if( count == -1 || other.count == -1 )
        return false;

    // check if merge is possible
    if (x != WILD && other.x != WILD && x != other.x)
        return false;
    if (y != WILD && other.y != WILD && y != other.y)
        return false;
    if (z != WILD && other.z != WILD && z != other.z)
       return false;

    // debug display of matching blocks
    std::cout << "\nmatch\n";
    text();
    other.text();

    // do the merge

    count += other.count; // sum the occurences

    other.count = -1; // delete the matched block

    // collapse wild values
    if (x == WILD && other.x != WILD)
        x = other.x;
    if (y == WILD && other.y != WILD)
        y = other.y;
    if (z == WILD && other.z != WILD)
        z = other.z;

    // debug display of merge results
    std::cout << " => ";
    text();

    return true;
}

The C++ code for the complete application is at https://github.com/JamesBremner/BlockMatcher/blob/main/src/main.cpp

I am wondering about your initial condition. Guessing that the blocks occur one at a time, so you will need code to combine single occurrences blocks as they occur. I have added such code to the github repo.