Writing messages with kids letter blocks for fun...

letter_blocks.c

#include <stdio.h>
#include <stdint.h>
#include <string.h>

/*

This was some idle programming for fun while on vacation.  I was staying
at a vacation house that had a set of kids letter blocks, the sort that
are six-sided wooden blocks with a different letter on each side.  I was
trying to figure out the most entertaining messages I could write with the
blocks, and having a hard time deciding if any message was possible or
not.  While it is most likely an NP-complete problem, I could still solve
it exhaustively in this case since the set is so small (only 22 blocks).
One evening of tinkering later, I had this program.

After looking at all the blocks carefully, it turned out they mostly had
consecutive alphabetical series of 6 letters on the 6 sides.  For example,
one block had C-D-E-F-G-H and another had O-P-Q-R-S-T.  The exceptions
were those that hit the end of the alphbet.  Most of those just wrapped
around Z-to-A, like Y-Z-A-B-C-D.  The final oddball exception was the
block that had W-X-Y-A-B-S -- it was almost a normal Z-to-A wrap, except
they replaced the Z with an S.

For ease of programming, I reference the blocks by the first letter in
their series.  For example, the O-P-Q-R-S-T block is just listed as "O" in
the block lists.

There are definitely ways this program could be made more efficient or
more flexible:

- Add comments in the code instead of just at the function level

- Better suport for non-sequential letter sets on blocks

- More robust block inventory, that doesn't require they be entered
  pre-grouped

- Speed up the find_blocks method by sorting the block inventory and
  string to match with the most likely to fail items first (fewest options)

*/

/**
 * The number of blocks on the shelf
 */
#define NUM_BLOCKS 22

/**
 * The list of blocks we have available on the shelf, one letter per block.  Each is referenced as the first letter on the block's alphabetic sequence.  If we have multiple of the same block, we list the same letter multiple times, being sure to group them	for	efficiency	when	searching.
 */
const char BLOCKS[NUM_BLOCKS+1] = "ACCCEEGIKKKMOOQQQSSSWY";

/**
 * A bitmask with one bit set for each block
 */
const uint32_t ALL_BLOCKS_MASK = ((1 << NUM_BLOCKS) - 1);

/**
 * Just for debug entertainment, we count how many blocks we checked...
 */
long unsigned find_blocks_iterations = 0;

/**
 * This function checks if a letter is available on any of the sides of a given block
 *
 * @param letter The letter we are looking for (must be uppercase)
 * @param block  The reference to the block (first letter in it's alphabetic sequence)
 *
 * @return 1 if the letter is on the block, 0 if not
 */
int letter_on_block(char letter, char block)
{
	char block_end = (block + 5);
	if (block == 'W') {
		// The W block doesn't follow the pattern that every other block does...
		switch (letter) {
			case 'W':
			case 'X':
			case 'Y':
			case 'A':
			case 'B':
			case 'S':
				return 1;
			default:
				return 0;
		}
	}
	if ( block_end > 'Z' ) {
		block_end -= 26;
		return ((letter >= block) || (letter <= block_end)) ? 1 : 0;
	}
	else {
		return ((letter >= block) && (letter <= block_end)) ? 1 : 0;
	}
}

/**
 * The recursive subfunction that does the bulk of the work looking for a selection of blocks that can provide the desired string.
 *
 * @param matching_block_string
 *  			 If a match is found, this string is filled in with the references to the blocks that were able to provide the match.
 * @param string_to_match
 *  			 The string we are trying to match
 * @param blocks_available_mask
 *  			 A bitmask of which of the initial BLOCKS definition are still available
 *
 * @return 1 if a full match found, 0 if not
 */
int find_blocks_helper(char *matching_block_string, const char *string_to_match, uint32_t blocks_available_mask)
{
	const char char_to_match = *string_to_match;
	const char *remaining_string_to_match = string_to_match + 1;
	char previous_block_letter;

	find_blocks_iterations++;

	if ( char_to_match == 0 ) {
		*matching_block_string = 0;
		return 1;
	}
	previous_block_letter = 0;
	for ( int current_block = 0; current_block < NUM_BLOCKS; current_block++ ) {
		const uint32_t current_block_mask = (1 << current_block);
		const char current_block_letter = BLOCKS[current_block];
		if ((current_block_letter != previous_block_letter) &&
			(current_block_mask & blocks_available_mask) &&
			letter_on_block(char_to_match, current_block_letter)) {
			if ( find_blocks_helper((matching_block_string+1),remaining_string_to_match, (blocks_available_mask & ~current_block_mask)) ) {
				*matching_block_string = current_block_letter;
				return 1;
			}
			previous_block_letter = current_block_letter;
		}
	}
	return 0;
}

/**
 * The application-friendly entry point to the recursive block finder.  Also prints to stdout information about whether a match was found, how many iterations it ran through, and what the series of blocks that were able to provide the match were.
 *
 * @param string_to_match
 *  			 The string we are trying to match on the blocks.  Expected to be groomed to all uppercase, alphabet letters only, no spaces.
 *
 * @return 1 if the set of blocks is able to provide the string, 0 if not
 */
int find_blocks(const char *string_to_match)
{
	char block_string[NUM_BLOCKS+1];
	find_blocks_iterations = 0;
	int result;
	if (strlen(string_to_match) > NUM_BLOCKS) {
		printf("find_blocks: result=0 too long\n");
		return 0;
	}
	memset(block_string, 0, sizeof(block_string));
	result = find_blocks_helper(block_string, string_to_match, ALL_BLOCKS_MASK);
	printf("find_blocks: result=%u iterations=%lu block_string=%s\n",result,find_blocks_iterations,block_string);
	return result;
}

/**
 * This was an earlier exploratory bit of code that just printed out a table showing which blocks could be matched to each letter of the user input, and also how many places any given block could be used.  It is not usedin the process of finding a matching	set,	and	was	merely	informative	to	help	me	think	about	the	problem.
 *
 * @param phrase The string we are trying to match on the blocks.  Expected to be groomed to all uppercase, alphabet letters only, no spaces.
 */
void generate_table(const char * const phrase)
{
	const int phrase_len = strlen(phrase);
	unsigned mapping_options[phrase_len][NUM_BLOCKS];
	unsigned mapping_results[NUM_BLOCKS];
	unsigned hits_per_letter;
	int current_letter;
	int current_block;

	memset(mapping_results,0,sizeof(mapping_results));
	printf("	 ");
	for (current_block = 0; current_block < NUM_BLOCKS; current_block++) {
		printf("%2c ",BLOCKS[current_block]);
	}
	printf("\n");
	for (current_letter = 0; current_letter < phrase_len; current_letter++) {
		hits_per_letter = 0;
		printf("  %c: ",phrase[current_letter]);
		for (current_block = 0; current_block < NUM_BLOCKS; current_block++) {
			mapping_options[current_letter][current_block] = (letter_on_block(phrase[current_letter],BLOCKS[current_block])) ? 1 : 0;
			mapping_results[current_block] += mapping_options[current_letter][current_block];
			hits_per_letter += mapping_options[current_letter][current_block];
			printf("%2d ",mapping_options[current_letter][current_block]);
		}
		printf(": %2d\n",hits_per_letter);
	}

	printf("SUM: ");
	for (current_block = 0; current_block < NUM_BLOCKS; current_block++) {
		printf("%2d ",mapping_results[current_block]);
	}
	printf("\n");
	printf("	 ");
	for (current_block = 0; current_block < NUM_BLOCKS; current_block++) {
		printf("%2c ",BLOCKS[current_block]);
	}
	printf("\n");
}

/**
 * Takes a string of text input from the user, removes all non-alphabetic characters, and converts all alphabetic characters to uppercase.  This is used on raw user input to ensure a simpler format that is easier to work with later.
 *
 * @param dest  	Pointer to the destination buffer to receive the groomed string
 * @param src   	Pointer to the source buffer containing the raw user input
 * @param max_bytes Size of the destination buffer in bytes.  Used to ensure we do not have any buffer overflows.  If the output would be longer than this, it is truncated one byte earlier and then null-terminated.
 */
void groom_user_string(char *dest, const char *src, size_t max_bytes)
{
	int bytes_copied = 0;
	while ( bytes_copied < max_bytes ) {
		if ( *src == 0 ) {
			*dest = 0;
			return;
		}
		if ( (*src >= 'a') && (*src <= 'z') ) {
			*dest++ = *src++ - ('a' - 'A');
			bytes_copied++;
		}
		else if ( (*src >= 'A') && (*src <= 'Z') ) {
			*dest++ = *src++;
			bytes_copied++;
		}
		else {
			// fprintf(stderr, "Skipping (%02X) in input!\n",*src,*src);
			src++;
		}
	}
	fprintf(stderr, "Input too big! Truncating!\n");
	dest--;
	*dest = 0;
}

int main(int argc, char *argv[])
{
	char user_string[256];
	char groomed_string[256];
	printf("Enter string, or Ctrl-C to quit: ");
	while ( fgets(user_string,sizeof(user_string),stdin) != NULL ) {
		groom_user_string(groomed_string,user_string,sizeof(groomed_string));
		printf("groomed len=%lu s=%s\n",strlen(groomed_string),groomed_string);
		//generate_table(groomed_string);
		find_blocks(groomed_string);
		printf("Enter string, or Ctrl-C to quit: ");
	}
	return 0;
}