A simple program to obtain an optimal city layout for City Bloxx.

optimalbloxx.cpp

#include <iostream>
#include <queue>
#include <array>
#include <set>
#include <vector>
#include <algorithm>
#include <initializer_list>

constexpr int GRID_LENGTH = 5;
constexpr int GRID_SIZE = GRID_LENGTH * GRID_LENGTH;
constexpr int PRUNE_PERCENTILE = 75;
enum BuildingType { 
    EMPTY = 0,
    BLUE = 1,
    RED = 4,
    GREEN = 9,
    YELLOW = 16
};

#define garry std::array<BuildingType, GRID_SIZE>

struct Node {
    BuildingType grid[GRID_SIZE] = { EMPTY };
};

int getBuildingIndex(int x, int y) {
    if (x < 0 || x >= GRID_LENGTH || y < 0 || y >= GRID_LENGTH) {
        return -1;
    }
    return x + y * GRID_LENGTH;
}

int getBuildingX(int index) {
    return index % GRID_LENGTH;
}

int getBuildingY(int index) {
    return index / GRID_LENGTH;
}

bool isValidLayout (BuildingType* grid) {
    for (int i = 0; i < GRID_SIZE; i++) {
        int x = getBuildingX(i);
        int y = getBuildingY(i);

        int neighbors[4] = {
            getBuildingIndex(x, y - 1),
            getBuildingIndex(x - 1, y),
            getBuildingIndex(x + 1, y),
            getBuildingIndex(x, y + 1)
        };

        int emptyCount = 0;
        int blueFlag = 0;
        int redFlag = 0;
        int greenFlag = 0;

        for (int j = 0; j < 4; j++) {
            if (neighbors[j] == -1) {
                continue;
            }

            BuildingType buildingType = grid[neighbors[j]];
            if (buildingType == EMPTY) {
                emptyCount++;
            } else if (buildingType == BLUE) {
                blueFlag = 1;
            } else if (buildingType == RED) {
                redFlag = 1;
            } else if (buildingType == GREEN) {
                greenFlag = 1;
            }
        }

        if (grid[i] == RED && blueFlag + emptyCount < 1) {
            return false;
        }
        if (grid[i] == GREEN && blueFlag + redFlag + emptyCount < 2) {
            return false;
        }
        if (grid[i] == YELLOW && blueFlag + redFlag + greenFlag + emptyCount < 3) {
            return false;
        }
    }

    return true;
}

int calculateScore(const BuildingType* grid) {
    int score = 0;
    for (int i = 0; i < GRID_SIZE; i++) {
        score += grid[i];
    }
    return score;
}

garry identity(const garry& grid) {
    return grid;
}

garry rotate90(const garry& grid) {
    garry newGrid;
    for (int y = 0; y < GRID_LENGTH; y++) {
        for (int x = 0; x < GRID_LENGTH; x++) {
            newGrid[getBuildingIndex(GRID_LENGTH - y - 1, x)] = grid[getBuildingIndex(x, y)];
        }
    }
    return newGrid;
}

garry rotate180(const garry& grid) {
    return rotate90(rotate90(grid));
}

garry rotate270(const garry& grid) {
    return rotate90(rotate180(grid));
}

garry reflHoriz(const garry& grid) {
    garry newGrid;
    for (int y = 0; y < GRID_LENGTH; y++) {
        for (int x = 0; x < GRID_LENGTH; x++) {
            newGrid[getBuildingIndex(x, GRID_LENGTH - y - 1)] = grid[getBuildingIndex(x, y)];
        }
    }
    return newGrid;
}

garry reflVert(const garry& grid) {
    garry newGrid;
    for (int y = 0; y < GRID_LENGTH; y++) {
        for (int x = 0; x < GRID_LENGTH; x++) {
            newGrid[getBuildingIndex(GRID_LENGTH - x - 1, y)] = grid[getBuildingIndex(x, y)];
        }
    }
    return newGrid;
}

// y=x
garry reflDiagYeX(const garry& grid) {
    garry newGrid;
    for (int y = 0; y < GRID_LENGTH; y++) {
        for (int x = 0; x < GRID_LENGTH; x++) {
            newGrid[getBuildingIndex(y, x)] = grid[getBuildingIndex(x, y)];
        }
    }
    return newGrid;
}

// y=-x
garry reflDiagYeNX(const garry& grid) {
    garry newGrid;
    for (int y = 0; y < GRID_LENGTH; y++) {
        for (int x = 0; x < GRID_LENGTH; x++) {
            newGrid[getBuildingIndex(GRID_LENGTH - y - 1, GRID_LENGTH - x - 1)] = grid[getBuildingIndex(x, y)];
        }
    }
    return newGrid;
}

garry (*transformations[8])(const garry&) = {
    identity,
    rotate90,
    rotate180,
    rotate270,
    reflHoriz,
    reflVert,
    reflDiagYeX,
    reflDiagYeNX
};

// Also includes symmetrical layouts
bool isDuplicateLayout(const BuildingType newGrid[], std::set<garry>& seenLayouts) {
    garry layout;
    std::copy(newGrid, newGrid + GRID_SIZE, layout.begin());

    for (int i = 0; i < 8; i++) {
        layout = transformations[i](layout);
        if (seenLayouts.find(layout) != seenLayouts.end()) {
            return true;
        }
    }

    // No transformations matched, add to set
    seenLayouts.insert(layout);
    return false;
}

int main() {
    std::queue<Node> queue;
    std::set<garry> finalLayouts;
    std::set<garry> seenLayouts;
    Node initialNode;
    int buildingCount = 0;

    queue.push(initialNode);

    while (!queue.empty()) {
        Node currentNode = queue.front();
        queue.pop();

        int index = 0;
        while (currentNode.grid[index] != EMPTY || index == GRID_SIZE) {
            index++;
        }

        if (buildingCount < index) {
            buildingCount = index;
            std::cout << "Building " << buildingCount << "..." << std::endl;
            
            // Prune 75% of the lowest scorers every row after the first, to maximize score (so that all blue layouts don't ruin our performance)
            if (buildingCount % GRID_LENGTH == 0 && buildingCount / GRID_LENGTH > 1) {
                int nodeCount = queue.size();
                std::vector<int> scores;
            
                // Collect scores from the queue
                for (int i = 0; i < nodeCount; i++) {
                    Node node = queue.front();
                    queue.pop();
                    scores.push_back(calculateScore(node.grid));
                    queue.push(node);
                }
            
                // Sort scores to find the 75th percentile
                std::sort(scores.begin(), scores.end());
                int percentileIndex = (nodeCount * PRUNE_PERCENTILE) / 100;
                int thresholdScore = scores[percentileIndex];
            
                // Prune nodes below the 75th percentile score
                for (int i = 0; i < nodeCount; i++) {
                    Node node = queue.front();
                    queue.pop();
                    if (calculateScore(node.grid) > thresholdScore) {
                        queue.push(node);
                    }
                }
            }
        }

        // Grid is full
        if (index == GRID_SIZE) {
            continue;
        }

        for (BuildingType building : {BLUE, RED, GREEN, YELLOW}) {
            Node newNode = currentNode;
            newNode.grid[index] = building;

            if (!isValidLayout(newNode.grid) || isDuplicateLayout(newNode.grid, seenLayouts)) {
                continue;
            }

            if (index == GRID_SIZE - 1) {
                garry newGrid;
                std::copy(newNode.grid, newNode.grid + GRID_SIZE, newGrid.begin());
                finalLayouts.insert(newGrid);
            } else {
                queue.push(newNode);
            }
                
        }
    }

    // Loop through final layouts and find the one with the highest score
    int maxScore = 0;
    garry bestLayout;
    for (const garry& layout : finalLayouts) {
        int score = calculateScore(layout.begin());
        if (score > maxScore) {
            maxScore = score;
            bestLayout = layout;
        }
    }

    // Print best layout
    for (int y = 0; y < GRID_LENGTH; y++) {
        for (int x = 0; x < GRID_LENGTH; x++) {
            std::cout << bestLayout[getBuildingIndex(x, y)] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "Score: " << maxScore << std::endl;

    return 0;
}

optimalbloxx.md

OptimalBloxx

A simple program to obtain an optimal city layout for City Bloxx.

Problem Description

City Bloxx is a Java game installed on many legacy Nokia phones. In the Build City mode of the game, players need to build different types of buildings within a 5x5 plot of land. Buildings can be of four types: Blue, Red, Green, and Yellow. Blue buildings are the smallest and have the least population, while yellow buildings are the largest and have the most population.

A building's population is not directly proportional to its size, as bonus points are awarded for perfect stacking during construction. The maximum population for each building has not been specified.

The game puts certain restrictions on the building layout:

• Blue buildings can be built anywhere on the plot.
• Red buildings can only be built adjacent to at least one blue building.
• Green buildings can only be built adjacent to at least one blue and red building each.
• Yellow buildings can only be built adjacent to at least one blue, red, and green building each.

The goal of this program is to find the optimal building layout that maximizes the total population of the city. The program should output the building type and location for each building in the layout.

NOTE: The player can build a building of a higher population type in place of a building of a lower population type by demolishing them under specific circumstances. This program does not take that into account as the new layout does not comply with the building restrictions.

Parameters

• GRID_LENGTH (Default = 5): An integer representing the length of the square grid.
• BuildingType (Default = { 0, 1, 4, 9, 16 }): An 5 element enum representing the maximum population scores for each building type (no building, blue, red, green, yellow).
• PRUNE_PERCENTILE (Default = 75): The percentile of building types that can be pruned from the search space every row (starting from the second row).

Compilation

g++ -std=c++11 optimalbloxx.cpp -o optimalbloxx

Expected Result

2D Layout

• BRBRG
• YGYYB
• RBRGY
• GYGBR
• BRYBG

Building Count:

• Blue: 7
• Red: 6
• Green: 6
• Yellow: 6