#define PROG_NAME "booklets_ag" #define PROG_DESC "Enumerate exam booklets for multiple topics." #define PROG_VERS "2013-12-15" #define booklets_ag_C_COPYRIGHT \ "Copyright © 2013 by the State University of Campinas (UNICAMP)" /* Last edited on 2018-02-13 01:10:35 by stolfilocal */ #define PROG_HELP \ " " PROG_NAME " \\\n" \ " -numTopics {NT} \\\n" \ " -numBlocks {NB} \\\n" \ " -minShared {KMIN} \\\n" \ " -maxShared {KMAX} \\\n" \ " [ -symmetric {SYMM} ] \\\n" \ " " argparser_help_info_HELP " \\\n" \ " > {OUTFILE}" #define PROG_INFO \ "NAME\n" \ " " PROG_NAME " - " PROG_DESC "\n" \ "\n" \ "SYNOPSIS\n" \ PROG_HELP "\n" \ "\n" \ "DESCRIPTION\n" \ " The program enumerates exam booklets for an exam over {NT} topics, by assembling blocks of questions. It assumes that, for each topic, there are {NB} alternative blocks of questions, each of them sufficient and necessary to cover that topic. Each booklet must consist of {NT} question blocks, one for each topic.\n" \ "\n" \ " The program finds a set of booklets, as large as it can, such that any two booklets have at most {K} question blocks in common. These booklets are printed to standard output. Each line has a count of the booklet (starting from 1) followed by {NT} fields describing one booklet. Each field has one or more digits followed by one letter followed. The digits identify the topic (1, 2, ..., up to {NT}). The letter ('A', 'B', 'C', ..., 'Z') identifies the block of questions to be included for that topic. For example, if {NT} is 5 and {NB} is 10, the output might include these lines:\n" \ "\n" \ " ...\n" \ " 251 223411 1B 2C 3F 4F 5G\n" \ " 252 125616 1C 2J 3C 4F 5C\n" \ " ...\n" \ "\n" \ " This output means that booklet #251 of the selected set, which is #223411 in the list of all possible booklets, uses question block 'B' for topic 1, block 'C' for topic 2, block 'F' for topic 3, etc.. Booklet #252 uses question block 'C' for topic 1, block 'J' for topic 2, block 'C' for topic 3, etc.. Note that these two booklets have one block of questions in common (block 'F' for topic 4)." \ "\n" \ " The output starts with a set of {NB} booklets that have at most {KMIN} question blocks in common. Then there are a set of booklets that have at most {KMIN+1} block in common with each other or with the booklets in the initial set. Then more booklets that have at most {KMIN+2} blocks in common with each other or with the previous ones, and so on; until a set of booklets that have at most {KMAX} blocks in common among themselves and with previous booklets.\n" \ "\n" \ "OPTIONS\n" \ " -numTopics {NT}\n" \ " This mandatory argument is the number {NT} of topics in the exam.\n" \ "\n" \ " -numBlocks {NB}\n" \ " This mandatory argument is the number {NB} of question blocks available for each topic.\n" \ "\n" \ " -minShared {KMIN}\n" \ " This mandatory argument is the max number {KMIN} of question blocks that can be shared by two booklets in the initial set of boolets.\n" \ "\n" \ " -maxShared {KMAX}\n" \ " This mandatory argument is the max number {KMAX} of question blocks that can be shared by two booklets in the final set of booklets.\n" \ "\n" \ " -symmetric {SYMM}\n" \ " This optional argument specifies whether the program should try to build a set of boklets that is symmetric through block cycling. For example, if {NT=5}, {NB=6}. and the program selects the booklet 'DBBAC', it will also try to select 'ECCBD', 'FDDCE', 'AEEDF', 'BFFEA', and 'CAAFB'. The value {SYMM} can be 'T', 't', 'Y', 'y', or 1 for \"yes\", and 'F', 'f', 'N', 'n', or 0 for \"no\". If omitted, it defaults to \"no\".\n" \ "\n" \ "DOCUMENTATION OPTIONS\n" \ argparser_help_info_HELP_INFO "\n" \ "\n" \ "SEE ALSO\n" \ " gawk(1).\n" \ "\n" \ "AUTHOR\n" \ " Created 2018-01-12 by Jorge Stolfi, IC-UNICAMP.\n" \ "\n" \ "MODIFICATION HISTORY\n" \ " 2018-01-12 J.Stolfi: created.\n" \ " 2018-01-19 J.Stolfi: added \"-minShared\" option.\n" \ " 2018-02-10 J.Stolfi: reversed notation (topic=number, block=letter).\n" \ " 2018-02-12 J.Stolfi: added \"-symmetric\" option.\n" \ " 2018-02-12 J.Stolfi: moved some stuff to {boag_graph.c}. Min-deg heuristic.\n" \ "\n" \ "WARRANTY\n" \ argparser_help_info_NO_WARRANTY "\n" \ "\n" \ "RIGHTS\n" \ " " booklets_ag_C_COPYRIGHT ".\n" \ "\n" \ argparser_help_info_STANDARD_RIGHTS #define stringify(x) strngf(x) #define strngf(x) #x #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include #include #include typedef struct boag_options_t { int32_t numTopics; /* Number of topics in the exam. */ int32_t numBlocks; /* Number of question blocks for each topic. */ int32_t maxBooklets; /* Max number of booklets to list. */ int32_t minShared; /* Max number of question blocks shared between two booklets in first set. */ int32_t maxShared; /* Max number of question blocks shared between two booklets in last set. */ bool_t symmetric; /* If true, tries to make booklets that are symmetric through block cycling. */ } boag_options_t; /* Arguments from command line. */ boag_options_t *boag_parse_options(int32_t argc, char **argv); /* EXAM PARAMETERS In all procedures below, {NT} is the number of topics in the exam, {NB} is the number of question blocks per topic, and {NV = NB^NT} is the total number of possible booklets. BOOKLET REPRESENTATION A booklet can be represented as a /vector/ {qv[0..NT-1]} where each element is a question block ID in {1..NB}; or as an /index/ {ix} in {0..NV-1}. The correspondence is defined by {boag_booklet_index_from_vector} and {boag_booklet_index_to_vector}. BOOKLET SETS In all procedures below, the boolean {sel[ix]} is true iff booklet with index {ix} has been selected for inclusion in the exam. When defined, the boolean {val[ix]} is true iff the booklet with index {ix} is still a valid candidate for selection. INCOMPATIBILITY GRAPH The {K}-incompatibility graph has one vertex for each booklet, and an edge between two vertices iff the booklets have more than {K} question blocks in common. */ void boag_find_booklets ( int32_t NT, int32_t NB, int64_t NV, bool_t sel[], int64_t *nselP, int32_t K, bool_t symm ); /* Augments a set of selected booklets, so that any two booklets that have at most {K} intersections (shared question blocks). Assumes {NV = NB^NT}. Assumes that {sel[0..NV-1]} already contains a set of booklets with at most {K} pairwise intersections. If {symm} is true, tries to find solutions that are symmetric under cyclic permutations of the booklets in all topics. */ void boag_initialize_valid_set(boag_graph_t *G, int64_t NV, bool_t sel[], int64_t *nselP); /* Marks all vertices of {G} (possible booklets) as valid, minus those that are in the selected set {sel[0..NV-1]} and their neighbors (booklets with more than {G.K} intersections with any selected one). Requires {NV = G.NV}. Also set the degree {G.vdg[0..NV-1]} of each valid booklet in the valid subgraph of the incompatibility graph. Returns in {*nselP} the count of selected vertices. */ void boag_choose_valid_booklet(boag_graph_t *G, int64_t *ixP); /* Chooses a valid candidate booklet and returns its index in {*ixP}. Currently, finds the first vertex of the valid subgraph {H} of {G} (as defined set {G.val[0..G.NV-1]}) that has the minimum degree in {H}. */ void boag_select_booklet(int64_t NV, int64_t ix, bool_t sel[], int64_t *nselP); /* Adds to the set of selected booklets, represented by the bit vector {sel[0..NV-1]}, the booklet with index {ix}; and increments {*nselP}. */ void boag_remove_booklet_and_incompats(boag_graph_t *G, int64_t ix); /* Modifies {G} to account for the fact that the candidate booklet with index {ix} has been selected for the output. The procedure removes from the valid subgraph {H} of {G} the vertex {ix} (if it is currently valid) and all valid vertices that are adjacent to it (i.e. booklet candidates that are incompatible with it). */ void boag_write_booklet(FILE *wr, int32_t NT, int32_t NB, int64_t NV, int32_t qv[], int64_t ix, int64_t nsel); /* Prints to {wr} the booklet with vector {qv[0..NT-1]} and index {ix}, in the format "{nsel-1} {ix} 1{qv[0]} 2{qv[1]} ...". The field "{nsel-1}" is omitted if {nsel} is zero or negative. */ void boag_cycle_booklet(int32_t NT, int32_t NB, int32_t qv[]); /* Modifies the booklet vector {qv[0..NT-1]} by adding 1 to every element, and resetting to 1 if exceeds {NB}. */ void boag_debug_booklet(char *pre, int32_t NT, int32_t NB, int64_t NV, int32_t qv[], int64_t ix); /* Prints the booklet with index {ix} and vector {qv[0..NT-1]} to {stderr}, prefixed by {pre}. */ int32_t main (int32_t argc, char **argv) { boag_options_t *o = boag_parse_options(argc, argv); int32_t NT = o->numTopics; int32_t NB = o->numBlocks; /* Compute the number of all possible booklets, compatible or not: */ int64_t NV = boag_graph_num_vertices(NT, NB); /* Number of possible exam booklets. */ fprintf(stderr, "total %ld possible booklets\n", NV); /* Element {sel[iv]} is true iff booklet with index {ix} was selected: */ bool_t *sel = notnull(malloc(NV*sizeof(bool_t)), "no mem"); for (int64_t ix = 0; ix < NV; ix++) { sel[ix] = FALSE; } int64_t nsel = 0; /* Number of true elements in {sel[0..NV-1]}. */ /* Find the of booklets, one {K}-set at a time: */ int32_t KMIN = o->minShared; int32_t KMAX = o->maxShared; bool_t symm = o->symmetric; for (int32_t K = KMIN; K <= KMAX; K++) { /* Add booklets with at most {K} intersections: */ boag_find_booklets(NT, NB, NV, sel, &nsel, K, symm); } fprintf(stderr, "done.\n"); return 0; } void boag_find_booklets ( int32_t NT, int32_t NB, int64_t NV, bool_t sel[], int64_t *nselP, int32_t K, bool_t symm ) { bool_t debug = TRUE; int64_t nsel = (*nselP); char *cadd = (nsel == 0 ? "" : "additional "); fprintf(stderr, "--- finding %sbooklets with at most %d intersections ---\n", cadd, K); fprintf(stdout, "# booklets with at most %d intersections:\n", K); /* Build the (virtual) incompatibility graph {G}, with all vertices valid: */ boag_graph_t *G = boag_graph_new(NT, NB, K); /* Invalidate all previously selected booklets and their neighbors: */ boag_initialize_valid_set(G, NV, sel, &nsel); fprintf(stderr, "starting with %ld selected and %ld valid booklets\n", nsel, G->NH); int64_t nsel_tot_ini = nsel; /* Save starting booklet count for this {K}. */ int32_t qv[NT]; /* Candidate booklet vector. */ while (G->NH > 0) { fprintf(stdout, "\n"); /* Select a valid booklet {ix,qv}: */ int64_t ix = -1; /* Selected booklet. */ boag_choose_valid_booklet(G, &ix); boag_booklet_index_to_vector(NT, NB, NV, ix, qv); if (debug) { boag_debug_booklet("ix = ", NT, NB, NV, qv, ix); } if (symm) { /* Try to exploit the symmetry under cyclic shifts of question blocks: */ int64_t nsel_lot_ini = nsel; /* Save {nsel}.*/ for (uint32_t j = 0; j < NB; j++) { boag_select_booklet(NV, ix, sel, &nsel); boag_remove_booklet_and_incompats(G, ix); boag_write_booklet(stdout, NT, NB, NV, qv, ix, nsel); boag_cycle_booklet(NT, NB, qv); boag_booklet_index_from_vector(NT, NB, NV, qv, &ix); } int64_t nsel_lot = nsel - nsel_lot_ini; /* Number selected in this symmetry class. */ if (nsel_lot != NB) { fprintf(stderr, " !! warning - simmetry broken - only %ld selected\n", nsel_lot); } } else { /* One booklet at a time: */ boag_select_booklet(NV, ix, sel, &nsel); boag_remove_booklet_and_incompats(G, ix); boag_write_booklet(stdout, NT, NB, NV, qv, ix, nsel); } } fprintf(stdout, "\n"); int64_t nsel_tot = nsel - nsel_tot_ini; /* Number selected in this {K}. */ fprintf(stderr, "found %ld %sbooklets (%ld total)", nsel_tot, cadd, nsel); fprintf(stderr, " with at most %d intersections.\n", K); (*nselP) = nsel; } void boag_initialize_valid_set(boag_graph_t *G, int64_t NV, bool_t sel[], int64_t *nselP) { assert(NV == G->NV); int64_t ND = G->ND; /* Set all vertices as valid, with full degree: */ for (int64_t ix = 0; ix < NV; ix++) { G->val[ix] = TRUE; G->vdg[ix] = ND; } G->NH = NV; int64_t nsel = 0; for (int64_t ix = 0; ix < NV; ix++) { if (sel[ix]) { boag_remove_booklet_and_incompats(G, ix); nsel++; } } (*nselP) = nsel; } void boag_choose_valid_booklet(boag_graph_t *G, int64_t *ixP) { /* Find a vertex of min degree in {H}: */ int64_t NV = G->NV; int64_t ND = G->ND; demand(G->NH > 0, "no more valid vertices"); int64_t dgmin = G->NV; /* Min degree found so far, or {NV}. */ int64_t ixmin = -1; /* Index of a vertex with degree {dgmin}, or {-1}. */ int64_t nval = 0; /* Number of valid vertices actually found. */ for (int64_t ix = 0; ix < NV; ix++) { if (G->val[ix]) { int64_t d = G->vdg[ix]; assert((d >= 0) && (d <= ND)); if (d < dgmin) { dgmin = d; ixmin = ix; } nval++; } } assert(nval == G->NH); (*ixP) = ixmin; } void boag_select_booklet(int64_t NV, int64_t ix, bool_t sel[], int64_t *nselP) { assert((ix >= 0) && (ix < NV)); int64_t nsel = (*nselP); assert((nsel >= 0) && (nsel < NV)); demand(!(sel[ix]), "booklet is already selected"); sel[ix] = TRUE; nsel++; (*nselP) = nsel; } void boag_write_booklet(FILE *wr, int32_t NT, int32_t NB, int64_t NV, int32_t qv[], int64_t ix, int64_t nsel) { demand((ix >= 0) && (ix < NV), "invalid booklet index"); demand((nsel <= 0) || ((nsel >= 1) && (nsel <= NV)), "invalid selected booklet count"); demand(NB <= 26, "too many question blocks"); if (nsel > 0) { fprintf(wr, "%8ld ", nsel-1); } fprintf(wr, "%8ld ", ix); for (uint32_t it = 0; it < NT; it++) { char ct = (char)('A' + qv[it] - 1); fprintf(wr, " %d%c", it+1, ct); } fprintf(wr, "\n"); } void boag_remove_booklet_and_incompats(boag_graph_t *G, int64_t ix) { /* Invalidate the selected vertices and their neighbors: */ auto void invalidate(int64_t ixb); /* Invalidates the booklet {ixb}, if still valid. */ invalidate(ix); boag_graph_enum_incompat_booklets(G, ix, &invalidate); return; /* INTERNAL IMPLEMENTATIONS */ void invalidate(int64_t ixb) { if (G->val[ixb]) { boag_graph_invalidate_vertex(G, ixb); } } } void boag_cycle_booklet(int32_t NT, int32_t NB, int32_t qv[]) { for (uint32_t it = 0; it < NT; it++) { int32_t ib = qv[it]; demand((ib >= 1) && (ib <= NB), "invalid question block index in vector"); qv[it] = (ib == NB ? 1 : ib + 1); } } void boag_debug_booklet(char *pre, int32_t NT, int32_t NB, int64_t NV, int32_t qv[], int64_t ix) { fprintf(stderr, " %s", pre); boag_write_booklet(stderr, NT, NB, NV, qv, ix, -1); } #define boag_numTopics_MAX 99 /* Maximum number of exam topics. */ #define boag_numBlocks_MAX 26 /* Maximum number of question blocks per topic. */ boag_options_t *boag_parse_options(int32_t argc, char **argv) { /* Initialize argument parser: */ argparser_t *pp = argparser_new(stderr, argc, argv); argparser_set_help(pp, PROG_NAME " version " PROG_VERS ", usage:\n" PROG_HELP); argparser_set_info(pp, PROG_INFO); argparser_process_help_info_options(pp); /* Allocate the command line argument record: */ boag_options_t *o = notnull(malloc(sizeof(boag_options_t)), "no mem"); /* Parse keyword parameters: */ argparser_get_keyword(pp, "-numTopics"); o->numTopics = (int32_t)argparser_get_next_int(pp, 1, boag_numTopics_MAX); argparser_get_keyword(pp, "-numBlocks"); o->numBlocks = (int32_t)argparser_get_next_int(pp, 1, boag_numBlocks_MAX); argparser_get_keyword(pp, "-minShared"); o->minShared = (int32_t)argparser_get_next_int(pp, 0, o->numTopics - 1); argparser_get_keyword(pp, "-maxShared"); o->maxShared = (int32_t)argparser_get_next_int(pp, o->minShared, o->numTopics - 1); if (argparser_keyword_present(pp, "-symmetric")) { o->symmetric = argparser_get_next_bool(pp); } else { o->symmetric = FALSE; } /* Check for spurious arguments: */ argparser_finish(pp); return o; }