Randomly Pair Teams From Text File Twice

Question

I'm fairly new to C programming and I'm attempting to complete this random pairing program but I'm having issues with starting it. Basically, the program needs to read in the 3 letter team names from a text file, place them into an array, and then randomly pair teams against each other. There are two rounds and in the second round, there cannot be any rematches. Additionally, teams from the same school cannot play against each other. Teams from the same school share the same first character and line in the text file. Can anyone help me with how to code this? :) Here is the text file named provisions.txt:

ABA ABC ABD ABG
BAA BAB BAC
CAB CBA
DAB DBC DBE DBA
EAB
FAB FAC FAA
GAB GAA
HAA HAB
IAB
JAA
KAA
LAL LAB
MAA MAB MBA MUM
NAN NAB

My code so far is:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>

int main()
{
// Read characters from text file into array
FILE *file = fopen("provision.txt", "r");

char teamList[115];
char teams[32][4];  // Holds team names
int i;

for(i = 0; i < 32; i++){
    fscanf(file, "%s", teams[i]);
}

for(i = 0; i < 32; i++){
        printf("%s \n", teams[i]);  // Test to make sure teams are read in
}

// Clean up
fclose(file);

return 0;
}

If possible, I would like to store the output of both rounds in text files named round1_pairings.txt and round2_pairings.txt.

Answer 1

This program attempts to solve a few subtle problems such as random selection bias, backing out of dead-end matching attempts, etc. It is not guaranteed to terminate in the case where a given round cannot be paired due to insufficient teams from other schools, which is more likely to occur at higher numbers of rounds (unlikely with only two rounds and many schools).

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define NAMELEN 3
#define ROUNDS 2
#define RETRIES 10 // max attempts before restarting matching                                                           

#define STR_HELPER(x) #x // http://stackoverflow.com/a/5459929/4323                                                     
#define STR(x) STR_HELPER(x)
#define NAMEPRINTF "%" STR(NAMELEN) "s"

typedef char team_t[NAMELEN + 1];

typedef struct
{
    team_t team;
    team_t opponents[ROUNDS];
} pairing_t;

// the first round is round=0                                                                                           
// when round>0, prior round matches will be prevented from recurring                                                   
void make_matches(pairing_t* pairings, size_t count, size_t round)
{
    // clip random() range to avoid bias toward first teams                                                             
    long randmax = LONG_MAX - LONG_MAX % count - 1;
  begin:
    for(size_t ii = 0; ii < count; ++ii) {
        if(pairings[ii].opponents[round][0]) continue; // already paired                                                
        //printf("matching: %s\n", pairings[ii].team);                                                                  
        unsigned retry = 0;
        while(retry < RETRIES) {
            long rand = random();
            if (rand > randmax) continue; // avoid bias                                                                 
            pairing_t *opp = &pairings[rand % count];
            if(opp->team[0] == pairings[ii].team[0]) { // same school                                                   
                ++retry;
                continue;
            }
            if(opp->opponents[round][0]) continue; // already paired                                                    
            size_t prior;
            for(prior = 0; prior < round; ++prior) {
                if(!memcmp(opp->team, pairings[ii].opponents[prior], sizeof(team_t))) {
                    break;
                }
            }
            if(prior != round) continue; // duplicate pairing                                                           
            //printf("match made: %s %s\n", opp->team, pairings[ii].team);                                              
            memcpy(pairings[ii].opponents[round], opp->team, sizeof(team_t));
            memcpy(opp->opponents[round], pairings[ii].team, sizeof(team_t));
            break;
        }
        if(retry == RETRIES) { // matching failed, start again                                                          
            for(size_t ii = 0; ii < count; ++ii) {
                memset(pairings[ii].opponents[round], 0, sizeof(team_t));
            }
            goto begin;
        }
    }
}

int main(void)
{
    srandom(time(NULL));

    FILE *file = fopen("provision.txt", "r");

    size_t capacity = 15; // arbitrary initial size                                                                     
    pairing_t *pairings = calloc(capacity, sizeof(pairing_t));
    if(!pairings) abort();

    size_t count = 0;
    while(fscanf(file, NAMEPRINTF, pairings[count].team) != EOF) {
        //printf("%s\n", pairings[count].team);                                                                         
        ++count;
        if(count >= capacity) { // expand array                                                                         
            capacity *= 2;
            pairings = realloc(pairings, capacity * sizeof(pairing_t));
            if(!pairings) abort();
            memset(&pairings[count], 0, (capacity - count) * sizeof(pairing_t));
        }
    }

    for(size_t round = 0; round < ROUNDS; ++round) {
        make_matches(pairings, count, round);
    }

    for(size_t ii = 0; ii < count; ++ii) {
        printf("%s %s %s\n", pairings[ii].team, pairings[ii].opponents[0], pairings[ii].opponents[1]);
    }

    free(pairings);
    fclose(file);
    return 0;
}

The output is a simple table with three columns: the team playing, their first opponent, and their second opponent. I'm sure you can figure out how to write these to separate files as required.