TAMUhack 2023

My First Hackathon

I spend a lot of time programming. The goal for most of my projects is to expand my skills by doing something I had never done before. I don't set deadlines and I don't even commit to spending a certain amount of time working on it. Once I have a viable product, I move on. This process can take weeks or even months sometimes. Hackathons are the complete opposite. In a hackathon, you have to take a problem, design a solution, and implement the solution, all in 24 hours. 24 hours seems like a lot of time, especially with a team, but debugging can take a lot of time.

I was unprepared for this hackathon. I didn't find a team beforehand and I didn't have a project in mind. I thought that the format would be more like a game jam, where everyone is given a theme to get them started. I was surprised that the challenges were not released until the hacking began. I was also surprised that we had the option to create whatever we wanted, without adhering to a theme or solving a specific challenge. I found a team at the beginning of the event and we settled on tackling the CBRE Challenge.

CBRE Challenge

CBRE is the largest Commercial Real Estate Services company by revenue. One common challenge we help our clients overcome is to help fill an office space, given a team structure and preferences. And at the same time, maximize the amount of space available. Create an app to visualize the most optimal way of allotting the teams to the space across the floors, so that none of the floors remain empty and at least 25% of each floor remains occupied.

Learn More (PDF)

This challenge has two main components: the optimization algorithm and the visualization. I decided to focus on the algorithm while my teammate worked on the visualization. I researched many candidate algorithms to solve this problem. This challenge is a combinatorial optimization problem that contains elements of the stable marriage problem and the knapsack problem. I tried several algorithms, but each one only satisfied one of the optimization conditions at a time. The sample data that we were given to test our algorithm contains 11 teams and 5 floors, so it was reasonable to test all the combinations to find the best one. So that is exactly what I did. I wrote the algorithm in C++ for maximum efficiency. Heap allocations are also avoided entirely. This algorithm has a complexity of O(n2) space and time. In practice, the space used by the algorithm is negligible even if there are hundreds of teams, but time is a real problem. When my program is run on the sample data, it takes 15-20 seconds to process. This is reasonable, but there is a possibility that the time could grow to minutes or even hours if there are enough teams. Despite these shortcomings, I was satisfied that my program would always find the most optimal solution.

Creating the API Server

My teammate was creating the frontend in React, so we needed to make sure that the React application could interact with my C++ program. To do this, I created a Python API server with FastAPI to manage the algorithm program. I implemented a basic account system to store team and floor data with each building manager's account. Several API routes were necessary to achieve this functionality.

/**/*                    Redirects to /index.html
/index.html              React frontend
/dev/users               Returns database as json
/dev/logout-all          Invalidates all user tokens
/api/ping                Returns "Pong!" (tests if server is live)
/api/username-available  Checks database for username
/api/register            Registers username with password
/api/login               Validates password for username, grants token on success
/api/logout              Invalidates user token
/api/user                Returns user data including teams.csv and floors.csv
/api/teams               Returns teams.csv as json
/api/teams/upload        Saves teams.csv to account
/api/floors              Returns floors.csv as json
/api/floors/upload       Saves floors.csv to account
/api/calculate           Launches algorithm.cpp, returns team floor assignments as json

Our Final Product

The frontend was a bit rough around the edges. We didn't have time to create the account creation flow, so there is a single hardcoded account. Once you log in with that account, you are able to upload teams.csv and floors.csv, then there is a button to submit. After the optimal floor arrangement is returned to the client, a summary report is generated in the form of a bar graph. Despite the algorithm functioning properly, our visualization was basic in comparison.

Lessons Learned

We didn't win any awards, but we learned a lot about how to problem-solve quickly and pivot when something isn't working. We received some interesting feedback from the judges. One judge mentioned that it might be beneficial to offer multiple options for team arrangements to add an element of choice to the application. It was then that I realized that the whole time I was coming up with the solution, I was thinking of it like a math problem. Sometimes we forget that the solutions that we're creating are going to be used by real people with interests beyond the problem domain. It can also be motivating and give you a sense of purpose to think this way.

I believe I was disadvantaged by not finding a team before the event. If I had worked with these people before or had discussed ideas beforehand, we might have been able to be more efficient. Although, I did get some practice working with people that I hadn't met before. We quickly identified each of our strengths and used that information to assign tasks. Looking back, we could have assisted each other more with our tasks when issues came up.

Overall, I had a lot of fun. This definitely won't be my last hackathon.

The Algorithm

#include <iostream>

using namespace std;

struct Team
{
    int strength;
    int floor_id;
};

struct Floor
{
    int minCapacity;
    int maxCapacity;
    int occupied;
};

int main()
{
    int i, j, k, l;

    int numFloors;
    cin >> numFloors;

    Floor floors[numFloors];

    int capacity;
    for( i = 0; i < numFloors; i++ )
    {
        cin >> capacity;
        floors[i] = { capacity / 4 + 1, capacity, 0 };
    }

    int numTeams;
    cin >> numTeams;

    Team teams[numTeams];
    bool prefers[numTeams][numTeams];
    bool tolerates[numTeams][numTeams];
    bool noWay[numTeams][numTeams];
    int bestArrangement[numTeams];
    int bestScore = -2147483648;

    for( i = 0; i < numTeams; i++ )
    {
        bestArrangement[i] = -1;
        for( j = 0; j < numTeams; j++ )
        {
            prefers[i][j]   = false;
            tolerates[i][j] = false;
            noWay[i][j]     = false;
        }
    }

    int strength, numPrefers, numTolerates, numNoWay, num;
    for( i = 0; i < numTeams; i++ )
    {
        cin >> strength;
        teams[i] = { strength, -1 };

        cin >> numPrefers;
        for( j = 0; j < numPrefers; j++ )
        {
            cin >> num;
            prefers[i][num - 1] = true;
        }

        cin >> numTolerates;
        for( j = 0; j < numTolerates; j++ )
        {
            cin >> num;
            tolerates[i][num - 1] = true;
        }

        cin >> numNoWay;
        for( j = 0; j < numNoWay; j++ )
        {
            cin >> num;
            noWay[i][num - 1] = true;
        }
    }

    bool carry, valid;
    bool done = false;
    int score;
    int permutations = 0, numValid = 0;
    while( !done )
    {
        permutations++;
        valid = true;
        // Calculate occupancies
        for( i = 0; i < numTeams; i++ )
        {
            j = teams[i].floor_id;
            if( teams[i].floor_id == -1 )
                continue;
            floors[j].occupied += teams[i].strength;
            if( floors[j].occupied > floors[j].maxCapacity ) // Floor overfilled, bail out
            {
                valid = false;
                break;
            }
        }

        if( valid )
            for( i = 0; i < numFloors; i++ )
                if( floors[i].occupied < floors[i].minCapacity ) // Floor underfilled, bail out
                {
                    valid = false;
                    break;
                }

        if( valid )
        {
            numValid++;
            score = 0;
            for( i = 0; i < numTeams; i++ )
                for( j = 0; j < numTeams; j++ )
                    if( teams[i].floor_id == -1 )
                        score -= 2 * teams[i].strength;
                    else
                        if( teams[i].floor_id == teams[j].floor_id )
                            score += ( prefers[i][j] - noWay[i][j] ) * ( teams[i].strength );
            if( score > bestScore )
            {
                bestScore = score;
                for( i = 0; i < numTeams; i++ )
                    bestArrangement[i] = teams[i].floor_id;
            }
        }

        // Generate next permutation
        i = 0;
        do {
            teams[i].floor_id++;
            carry = teams[i].floor_id == numFloors;
            if( carry )
            {
                teams[i].floor_id = -1;
                i++;
                if( i == numTeams )
                    done = true;
            }
        } while( carry );

        for( i = 0; i < numFloors; i++ )
            floors[i].occupied = 0;
    }

    for( i = 0; i < numTeams; i++ )
    {
        cout << bestArrangement[i];
        if( i < numTeams - 1 )
            cout << " ";
    }
    cout << endl;

    return 0;
}

Results

Valid Permutations: 948561/362797056

Floor Capacities:
Floor 3 +22 from Team 0
Floor 2 +45 from Team 1
Floor 2 +34 from Team 2
Floor 4 +51 from Team 3
Floor 0 +11 from Team 4
Floor 5 +37 from Team 5
Floor 1 +42 from Team 6
Floor 0 +16 from Team 7
Floor 0 +29 from Team 8
Floor 5 +56 from Team 9
Floor 3 +49 from Team 10

Floor 1: 42/43 (97.6744%)
Floor 2: 79/81 (97.5309%)
Floor 3: 71/73 (97.2603%)
Floor 4: 51/54 (94.4444%)
Floor 5: 93/97 (95.8763%)

TOTAL: 336/348 (96.5517%)

Links

View Code On GitHub View Entry On Devpost View Competition Website