/*****************************************************************************

  Copyright (c) British Informatics Olympiad, 2004

  BIO 2004 Question 3 "Morse Code"
  Question by Richard Forster
  Example solution by Antony Rix.

  This program may be freely copied by persons or organisations
  involved in the British Informatics Olympiad or the International
  Olympiad in Informatics, on condition that no changes are made and
  this notice is not altered or removed. Distribution for profit is
  forbidden unless permission is first obtained in writing from the BIO.

  This program is for educational purposes only and comes with no
  warranty, implied or otherwise, as to its fitness for any purpose.

  http://www.olympiad.org.uk/

*****************************************************************************/

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

/* Represent the basic Morse code, from a to z: */
char * Morse[26] = {
	".-",
	"-...",
	"-.-.",
	"-..",
	".",
	"..-.",
	"--.",
	"....",
	"..",
	".---",
	"-.-",
	".-..",
	"--",
	"-.",
	"---",
	".--.",
	"--.-",
	".-.",
	"...",
	"-",
	"..-",
	"...-",
	".--",
	"-..-",
	"-.--",
	"--.."
};

/* The length of each code */
int MorseLength[26];

/* The text message and its length in characters */
char Message[255];
int Nmessage;

/* The Morse Code of the message and its length in symbols (dots/dashes).
   We allocate this to be longer than we need to simplify searching - we
   don't need to worry about running off the end. */
char Code[1024];
int Ncode;

/* The number of messages found for Q3a */
long Nfound;

/* The current message being tried */
char Current[255];

/* Recursive helper function for Q3a */
void Q3a_recurse(char * Next, int Nm_remain, char * Code, int Nc_remain) {
	/* Try to match the characters remaining in Message (which has length
	   Nm_remain) with the morse Code, which has Nc_remain symbols. */
	int i;

	/* See if we've found a match */
	if( (Nm_remain == 0) && (Nc_remain == 0) ) {
		Next[0] = '\0';
		printf("%s ", Current);
		Nfound++;
		return;
	} else if( (Nm_remain == 0) || (Nc_remain == 0) ) return;

	for( i = 0; i < 26; i++ )
		if( strncmp(Morse[i], Code, MorseLength[i]) == 0 ) {
			/* This letter matches at this position, so try what happens if we make this match. */
			Next[0] = 'a' + i;
			Q3a_recurse(Next+1, Nm_remain-1, Code+MorseLength[i], Nc_remain-MorseLength[i]);
		}
}

/* Solve the problem set in Q3a - find the number of messages of length
   Nmessage that correspond to Code[]. */
void Q3a( void ) {
	Nfound = 0;
	Q3a_recurse(Current, Nmessage, Code, Ncode);
	printf("\n%ld messages correspond to %s.\n", Nfound, Message);
}

/* Recursive helper function for Q3b */
void Q3b_recurse(char * Code, int Nc_remain) {
	/* Try to match the characters remaining in Code without a limit on message length. */
	int i;

	/* See if we've found a match */
	if( (Nc_remain == 0) ) {
		Nfound++;
		return;
	}

	for( i = 0; i < 26; i++ )
		if( strncmp(Morse[i], Code, MorseLength[i]) == 0 ) {
			/* This letter matches at this position, so try what happens if we make this match. */
			Q3b_recurse(Code+MorseLength[i], Nc_remain-MorseLength[i]);
		}
}

/* Solve the problem set in Q3b - find the number of messages of any length
   that correspond to Code[]. */
void Q3b( void ) {
	Nfound = 0;
	Q3b_recurse(Code, Ncode);
	printf("\n%ld messages correspond to %s.\n", Nfound, Message);
}

void main( void ) {
	/* Code to check that the Morse Code has been typed in correctly:
	char c;
	for( c = 'a'; c <= 'z'; c++ ) printf("%c %s\n", c, Morse[c-'a']);
	*/
	int i;
	char * p;

	/* Store the length of the Morse Codes */
	for( i = 0; i < 26; i++ ) MorseLength[i] = strlen(Morse[i]);

	/* Read in the message */
	printf("Enter message in lower-case text: ");
	scanf("%s", &Message);
	Nmessage = strlen(Message);

	/* Convert to Morse code, without pauses between letters */
	p = Code;
	Ncode = 0;
	for( i = 0; i < Nmessage; i++ ) {
		if( (Message[i] < 'a') || (Message[i] > 'z') ) {
			printf("ERROR! message contains characters other than a..z\n");
			exit(1);
		}
		strcpy(p, Morse[Message[i] - 'a']);
		Ncode += strlen(Morse[Message[i] - 'a']);
		p += strlen(Morse[Message[i] - 'a']);
	}
	*p = '\0'; /* Stick a null character at the end */
	printf("Morse code of message is %s\n", Code);

	/* Find the number of messages of this length that could correspond to this message */
	Q3a();
}