This year, I wrote the four problems myself. I am concerned that Problem 4 was the only one with any correct submissions. Thus, I would really like feedback from participants about the problems: level of difficulty, clarity, length, etc. One complaint was that in C++ it is difficult to detect a blank line. (Just use the istream::readline method.) Another complaint was that the problems were too long. I would welcome any additional feedback.
I would like to get a team together to send to the regional ACM competition. Anyone who is interested should just send me e-mail.
There were 38 participants.
Here is my solution:
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
/***************************************************************************
Perpetual Motion
Play the Solitaire game Perpetual Motion. Given an initial deck, indicate
whether the game was won, blocked, or we got bored.
***************************************************************************/
#define MAX 80 /* maximum line length */
#define NUM 52 /* number of cards */
#define STOP 100 /* if no cards removed for this many rounds, stop */
void play(char deck[MAX]);
/***************************************************************************
main
***************************************************************************/
void main(void)
{
char line[MAX];
int i;
int seed;
for (i = 1; ; i++)
{
/* Read a line containing the cards. If the line is blank, it's the
end of input. */
if (gets(line) == NULL)
/* EOF detected. End of input. */
return;
if (strlen(line) == 0)
/* Blank line detected. End of input. */
return;
/* Play the game, and do appropriate output. */
printf("Game %2d: ", i);
play(line);
}
}
/***************************************************************************
play
Play the card game, and print the appropriate message.
***************************************************************************/
void play(char deck[MAX])
{
char pile[4][NUM];
int index[4];
char deck2[NUM];
int n = 52;
int i, j, k;
int same, removed;
int round, no;
#define JUNK 'X'
#define card(q) (index[q] > 0 ? pile[q][index[q]-1] : JUNK)
round = 0;
for (round = 1; ; round++)
{
/* Initialize all piles to empty. */
for (j = 0; j < 4; j++)
index[j] = 0;
removed = 0;
/* Deal out the cards onto the piles. Remove cards and move to left
if possible. */
for (i = 0; i < n; i += 4)
{
/* Deal 4 cards, face up, one per stack. */
for (j = 0; j < 4; j++)
{
pile[j][index[j]] = deck[i+j];
index[j] ++;
}
/* Check if cards can be removed or collected. */
remove:
/* Check if cards can be removed. */
if (card(0) != JUNK)
{
same = 1;
for (j = 1; j < 4; j++)
if (card(j) != card(0))
same = 0;
if (same)
{
for (j = 0; j < 4; j++)
index[j] --;
removed = 1;
goto remove;
}
}
collect:
/* Check if cards can be moved to left. */
for (j = 0; j < 3; j++)
if (card(j) != JUNK)
for (k = j+1; k < 4; k++)
if (card(j) == card(k))
{
pile[j][index[j]] = card(k);
index[j] ++;
index[k] --;
goto collect;
}
/* Cannot remove or collect. Deal 4 more cards. */
}
/* Remake the deck from the piles. */
n = 0;
for (j = 0; j < 4; j++)
for (k = 0; k < index[j]; k++)
deck2[n++] = pile[j][k];
/* Check if we've won. */
if (n == 0) break;
/* We haven't won. Check if we're blocked or bored. */
if (! removed)
{
/* Make sure decks haven't repeated. */
same = 1;
for (i = 0; i < n; i++)
if (deck[i] != deck2[i])
same = 0;
if (same) break;
/* If too many rounds with same number of cards, stop. */
no ++;
if (no == STOP) break;
}
else
/* There have been 0 rounds with same number of cards. */
no = 0;
/* Copy the secondary deck into the primary deck. */
for (i = 0; i < n; i++)
deck[i] = deck2[i];
}
/* Print winning or losing message. */
if (n == 0)
printf("Won after %d rounds.\n", round);
else if (same)
printf("Blocked after %d rounds with %d cards left.\n", round, n);
else
printf("Got bored after %d rounds with %d cards left.\n", round, n);
}
The test input was:
556Q7QQ99A26KK839700444483356AA379JA08225KJQ786J0K2J 783QA5837JA5035K39Q46200K095J62Q4A2944Q7JK27KJ98A668 3604A97A20K935854J76884QK94K36223AQJAQ568Q05J2K7907J J2JAAQ34Q95A736765K420972864K3820Q9386058A4KQJJ09K57 758A425KK60635729533J9A496KQ07QJ20A884K9Q0J4J7A2Q368 53823A9A670K96KJA498K575Q2Q7JK8J00JQ3794AQ2243064658 K6J74A6392A904A58923KKJ0JQ7K59Q6230Q8A658QJ473724580 A04QJ24A777239Q5J078A42686J495K039582K50QKQK6633A89J Q24375JJ66Q75A74629A24QK859J9J4AK380A0028K35608KQ739 84Q9A232634J690J7Q7556Q90KA8396A048A5JK322KK7QJ70584 44359Q9A7JAA85238K7J8A55Q400602Q7J0QKK629J869632743K 49K79055Q3KQJA2953J824J029066386476J3AA8Q8Q7024K75AK 3K46QK076K8A825692QAK5239786504AJQA97J30907Q824J3J45 5Q5J3J2QAK23KAK956776047324K6870AQ4J20JQ43569880899A 4906AK56374Q907652KJ07485323K8AJJ5Q62Q89KQ72A49308JA 484Q6403JKJ793AA757608Q905A60J23Q35Q7A8K496JK822925K K649A3Q5KA7652A0923QJ6K88A72JQ050K497J35836089Q424J7The correct output was:
Game 1: Won after 17 rounds. Game 2: Won after 15 rounds. Game 3: Won after 28 rounds. Game 4: Won after 51 rounds. Game 5: Won after 42 rounds. Game 6: Won after 42 rounds. Game 7: Blocked after 23 rounds with 12 cards left. Game 8: Blocked after 49 rounds with 12 cards left. Game 9: Blocked after 45 rounds with 16 cards left. Game 10: Blocked after 85 rounds with 12 cards left. Game 11: Blocked after 41 rounds with 12 cards left. Game 12: Blocked after 44 rounds with 8 cards left. Game 13: Got bored after 151 rounds with 16 cards left. Game 14: Got bored after 138 rounds with 16 cards left. Game 15: Got bored after 127 rounds with 16 cards left. Game 16: Got bored after 145 rounds with 16 cards left. Game 17: Got bored after 147 rounds with 20 cards left.According to some tests I ran, you have about a 15% chance of winning this particular version of Solitaire.
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
/************************************************************************
Arithmetic Maze
A maze is described by a series of one-way edges. Each edge has an operation
(add, subtract, multiply, or divide) and a value associated with it. Find
the "best" path from the first node to the last. The best path is the one
with the highest value, when travelling along the path and performing the
operations (beginning with 0). If two paths result in the same value, then
the shorter one is preferred. If two paths have the same value and the same
length, then it doesn't matter which one is output.
************************************************************************/
#define MAX 80 /* maximum line length */
#define MSG 6 /* maximum length of points description of any edge */
#define N 50 /* maximum number of nodes */
#define M 100 /* maximum number of edges */
typedef enum { ADD, SUB, MULT, DIV } Operation;
typedef struct
{
int from;
int to;
Operation op;
int val;
} EdgeType;
int read_maze(int *n, int *m, EdgeType edges[M]);
EdgeType parse_edge(char line[MAX], int *n);
void search(int n, int m, EdgeType edges[M]);
/************************************************************************
main
************************************************************************/
void main(void)
{
int n; /* number of nodes */
int m; /* number of edges */
EdgeType edges[M]; /* array of edges */
int set = 0;
while (read_maze(&n, &m, edges))
{
printf("Maze %d\n", set+1);
search(n, m, edges);
printf("\n");
set ++;
}
}
/************************************************************************
read_maze
Read a maze. Return 1 if the read was successful.
************************************************************************/
int read_maze(int *n, int *m, EdgeType edges[M])
{
char line[MAX];
int count = 0;
/* Initialize number of nodes and edges to zero. */
*m = *n = 0;
/* Read edge descriptions until the end of file or a blank line. */
while (gets(line) && strlen(line))
/* Parse an edge description. */
edges[count++] = parse_edge(line, n);
/* Return 1 iff a maze was successfully read. */
if (count == 0)
return 0;
*m = count;
return 1;
}
/************************************************************************
parse_edge
Given an edge description, extract the source and destination of the edge,
the operation performed while crossing it, and its value. Also, determine
how many edges there are.
************************************************************************/
EdgeType parse_edge(char line[MAX], int *n)
{
char str[MSG];
EdgeType ret;
/* Read the source and destination nodes. */
sscanf(line, "%d %d %s", &(ret.from), &(ret.to), str);
/* Record the number of nodes. */
if (ret.from >= *n)
*n = ret.from + 1;
if (ret.to >= *n)
*n = ret.to + 1;
/* Process the operation. */
switch (str[0])
{
case '+' : ret.op = ADD; break;
case '-' : ret.op = SUB; break;
case '*' : ret.op = MULT; break;
case '/' : ret.op = DIV; break;
default : printf("Unrecognized message '%s'\n", str); exit(1);
}
/* Process the value. */
ret.val = atoi(str+1);
return ret;
}
/************************************************************************
search
Perform a depth-first search to find the best path from node 0 to node
n-1. The best path is the one with the highest score. If two paths have
the same score, then the shorter path is better.
************************************************************************/
void search(int n, int m, EdgeType edges[M])
{
/* We're really cool, so we'll manage our own stack. None of this so-called
recursion. */
typedef struct
{
int loc; /* current node number */
int score; /* current score */
int edge; /* edge used to get to this node */
int next; /* next edge to look at */
} State;
State state[N+1]; /* stack */
int s = 0; /* length of our stack */
State best[N+1]; /* best path found so far */
int b = -1; /* length of best path found so far */
int used[M]; /* array indicating which edges have been used */
int e;
int i;
/* Define the initial state. We start at node 0 with a score of 0. We did not
use any edges to get here. The next edge to look at is edge 0. */
state[0].loc = 0;
state[0].score = 0;
state[0].edge = -1;
state[0].next = 0;
/* Mark all the edges as unused. */
for (i = 0; i < m; i++)
used[i] = 0;
/* Do the depth-first search. */
while (s >= 0)
if (state[s].loc == n-1)
{
/* We have found a path to the end. */
if ((b == -1) || (state[s].score > best[b].score) ||
((state[s].score == best[b].score) && (s < b)) )
{
/* This path is the first one, or it's better than the old path,
or it's the same score but shorter, then keep it. */
for (i = 0; i <= s; i++)
best[i] = state[i];
b = s;
}
/* Pop this state off the stack. */
if (state[s].edge >= 0)
used[state[s].edge] = 0;
s --;
}
else if (state[s].next == m)
{
/* We have looked at all edges. Pop this state off the stack. */
if (state[s].edge >= 0)
used[state[s].edge] = 0;
s --;
}
else
{
/* Look at the next edge, and take it if possible. */
/* Remember which edge we're currently considering. */
e = state[s].next;
/* Next time, we will consider the next edge. */
state[s].next ++;
/* Make sure this edge starts where we're currently located. */
if (edges[e].from == state[s].loc)
/* The next edge does start on our node. Make sure we haven't
already used this edge. */
if (! used[e])
/* We haven't used this edge yet. Push a new state onto the
stack. */
{
used[e] = 1; /* Mark this edge as used. */
s ++;
state[s].loc = edges[e].to;
state[s].score = update(state[s-1].score, edges[e]);
state[s].edge = e;
state[s].next = 0;
}
}
/* Print out the best path. */
if (b == -1)
printf("There is no path.\n");
else
for (i = 0; i <= b; i++)
printf("%3d: node = %d, score = %d\n", i+1, best[i].loc, best[i].score);
}
/************************************************************************
update
Given a current score and an edge type, return the score obtained by
travelling across that edge.
************************************************************************/
int update(int score, EdgeType edge)
{
int s = score;
switch (edge.op)
{
case ADD : s += edge.val; break;
case SUB : s -= edge.val; break;
case MULT : s *= edge.val; break;
case DIV : s /= edge.val; break;
default : printf("Unrecognized operation\n"); exit(1);
}
return s;
}
The test input was:
0 1 +1 0 2 -1 1 3 *2 2 4 /3 3 5 +1 4 5 +10 1 0 +999 0 0 -999 0 1 +1 0 2 +2 0 3 +3 1 4 *2 2 5 *3 3 6 +5 4 7 +2 5 7 -1 5 8 +1 6 8 -3 7 3 +1 7 9 *2 8 1 +2 8 9 /2 0 1 -1 1 0 -1 0 2 +1 2 0 +2 0 3 +1 3 0 +1 0 4 /2 4 0 *2 4 5 +1 5 4 *2 4 6 *2 6 4 +1 4 7 +1The correct output was:
Maze 1 1: node = 0, score = 0 2: node = 2, score = -1 3: node = 4, score = 0 4: node = 5, score = 10 Maze 2 There is no path. Maze 3 1: node = 0, score = 0 2: node = 2, score = 2 3: node = 5, score = 6 4: node = 7, score = 5 5: node = 3, score = 6 6: node = 6, score = 11 7: node = 8, score = 8 8: node = 1, score = 10 9: node = 4, score = 20 10: node = 7, score = 22 11: node = 9, score = 44 Maze 4 1: node = 0, score = 0 2: node = 2, score = 1 3: node = 0, score = 3 4: node = 3, score = 4 5: node = 0, score = 5 6: node = 4, score = 2 7: node = 5, score = 3 8: node = 4, score = 6 9: node = 6, score = 12 10: node = 4, score = 13 11: node = 7, score = 14
#include < stdio.h > #include < stdlib.h > #include < string.h > /*************************************************************************** Class Sorter Read in a list of classes and their prerequisites. Each line is of the formThe test input was:: ... for some number of prerequisites (possibly 0). Print out the order in which the classes must be taken, so that the prerequisite requirement is satisfied. If two classes could be taken at the same time, take the one with the lowest number first; if the numbers match, take the one with the alphabetically highest department first. ***************************************************************************/ #define NUM 100 /* maximum number of classes */ #define MAX 80 /* maximum line length */ #define NAME 8 /* maximum length of a class name */ void initialize(char pre[NUM][NUM], int *count); void add_class(char line[MAX], char pre[NUM][NUM], char name[NUM][NAME+1], int *count); int get_word(char line[MAX], char temp[MAX], int *i); int valid(char c); int name_lookup(char temp[MAX], char name[NUM][NAME+1], int *count); void top_sort(char name[NUM][NAME+1], char pre[NUM][NUM], int count); int compare(char a[], char b[]); int number(char name[]); /*************************************************************************** main ***************************************************************************/ void main(void) { char pre[NUM][NUM]; char name[NUM][NAME+1]; char line[MAX]; int count; int set = 0; char *ret; initialize(pre, &count); do { ret = gets(line); if (strlen(line) > 0) { /* Add this class and its prerequisites. */ add_class(line, pre, name, &count); } else if (count > 0) { printf("Dataset %d:\n", set+1); set ++; /* We should perform the topological sort and print the output. */ top_sort(name, pre, count); printf("\n"); /* Reinitialize. */ initialize(pre, &count); } } while (ret); } /*************************************************************************** initialize ***************************************************************************/ void initialize(char pre[NUM][NUM], int *count) { int i, j; for (i = 0; i < NUM; i++) for (j = 0; j < NUM; j++) pre[i][j] = 0; *count = 0; } /*************************************************************************** add_class ***************************************************************************/ void add_class(char line[MAX], char pre[NUM][NUM], char name[NUM][NAME+1], int *count) { char temp[MAX]; int i = 0; int c, k; /* Get the name of the class. Look it up in the list of names. If it is not found, then add it. */ get_word(line, temp, &i); c = name_lookup(temp, name, count); /* Read all the prerequisites and update the array. */ while (get_word(line, temp, &i)) { k = name_lookup(temp, name, count); pre[c][k] = 1; } } /*************************************************************************** get_word Extracts the next word from line. i indicates where to start. After reading the word, i is changed to the end of the word for the next reading. ***************************************************************************/ int get_word(char line[MAX], char temp[MAX], int *i) { int j = 0; /* Skip white space. If the end of the line is found, return that no word was read. */ while (! valid(line[*i])) { if (line[*i] == 0) return 0; (*i) ++; } /* Copy the word. */ while (valid(line[*i])) { temp[j] = line[*i]; j ++; (*i) ++; } /* Terminate the copied word correctly and return that a word was found. */ temp[j] = 0; return 1; } /*************************************************************************** valid Return 1 iff the character is an uppercase letter or a numeral. ***************************************************************************/ int valid(char c) { if (('A' <= c) && (c <= 'Z')) return 1; if (('0' <= c) && (c <= '9')) return 1; return 0; } /*************************************************************************** name_lookup Return the location of in the list . If does not occur, then add it and return the new location. ***************************************************************************/ int name_lookup(char temp[MAX], char name[NUM][NAME+1], int *count) { int i; /* Check if temp occurs in the list of names. */ for (i = 0; i < *count; i++) if (strcmp(temp, name[i]) == 0) return i; /* It doesn't occur. Add it. */ strcpy(name[*count], temp); (*count) ++; return (*count) - 1; } /*************************************************************************** top_sort Perform the topological sort. If two classes have no unsatisfied prerequisites, then take the one that has the lowest number; if the numbers are the same, take the one with the alphabetically lowest department. If a cycle is detected, print that out. ***************************************************************************/ void top_sort(char name[NUM][NAME+1], char pre[NUM][NUM], int count) { char used[NUM]; /* flag indicating whether class has been printed by sort */ int total[NUM]; /* total number of prerequisites that a class has */ int order[NUM]; /* Order that classes are printed out. */ int i, j, k; /* Initialize that all classes are un-used, and count total number of prerequisites for each class. */ for (i = 0; i < count; i++) { used[i] = 0; total[i] = 0; for (j = 0; j < count; j++) if (pre[i][j]) total[i] ++; } /* Perform topological sort. */ for (i = 0; i < count; i++) { k = -1; for (j = 0; j < count; j++) if (!used[j] && (total[j] == 0)) { /* Class j has no unsatisfied prerequisites. */ if (k == -1) /* We have not found a class yet with no unsatisfied prereqs. */ k = j; else /* We have found another class with no unsatisfied prereqs. Keep the class with the lowest number, or if numbers are the same, alphabetically lowest department. */ { if (compare(name[k], name[j]) == 1) k = j; } } if (k == -1) { /* There is no class with unsatisfied prereqs. Must be a cycle. */ printf("A cycle was detected in the classes.\n"); return; } /* Mark class k as used, and remove it from the array of prereqs. */ used[k] = 1; for (j = 0; j < count; j++) if (pre[j][k]) { pre[j][k] = 0; total[j] --; } /* We'll eventually print out this class next. */ order[i] = k; } /* No cycles were detected. Print out the classes in order. */ for (i = 0; i < count; i++) printf("%3d: %s\n", i+1, name[order[i]]); } /*************************************************************************** compare Returns -1 if a < b, 0 if a == b, and 1 if a > b. The order is defined by first comparing the number part of the class names; if they're equal, compare the department part. ***************************************************************************/ int compare(char a[], char b[]) { int na, nb; na = number(a); nb = number(b); if (na < nb) return -1; if (na > nb) return 1; return strcmp(a, b); } /*************************************************************************** number Returns the number portion of a class's name. ***************************************************************************/ int number(char name[]) { int i = 0; while (('A' <= name[i]) && (name[i] <= 'Z')) i ++; return atoi(name + i); }
CS113 : CS100 CS114 : CS100 CS130 : CS211 : CS100 CS212 : CS100 CS213 : CS211 CS222 : CS100 MATH294 CS280 : CS211 CS314 : CS211 CS381 : CS280 CS400 : CS280 CS410 : CS280 CS412 : CS314 CS381 CS410 CS414 : CS314 ARCH374: CS211 CS421 : MATH294 CS481 : CS280 CS381 CS482 : CS481 CS410 MATH294 : MATH293 Z1 : X1 Y1 Y1 : X1 X1 : W1 W1 : Z1 EF1006 : EF1005 MATH1001 EE2005 : EF1006 EE2006 : EE2005 EE2504 : EF1005 EE4505 : EE2504 EE4506 : EE4505The correct output was:
Dataset 1: 1: CS100 2: CS113 3: CS114 4: CS130 5: CS211 6: CS212 7: CS213 8: CS280 9: MATH293 10: MATH294 11: CS222 12: CS314 13: ARCH374 14: CS381 15: CS400 16: CS410 17: CS412 18: CS414 19: CS421 20: CS481 21: CS482 Dataset 2: A cycle was detected in the classes. Dataset 3: 1: MATH1001 2: EF1005 3: EF1006 4: EE2005 5: EE2006 6: EE2504 7: EE4505 8: EE4506
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
/***************************************************************************
New Alphabetical Order
Read in a new alphabetical order, and a list of words. Print out the words
in (the new) alphabetical order.
***************************************************************************/
#define MAX 80 /* maximum line length */
#define NUM 50 /* maximum number of words to alphabetize */
#define WORD 16 /* maximum word length */
void make_order(char line[MAX], int order[26]);
void sort(int order[26], char words[NUM][WORD+1], int count);
int compare(int order[26], char a[WORD+1], char b[WORD+1]);
/***************************************************************************
main
***************************************************************************/
void main(void)
{
char line[MAX];
char *ret;
char words[NUM][WORD+1];
int order[26];
int set = 0;
int count;
count = -1;
do {
line[0] = 0;
ret = gets(line);
if (strlen(line) > 0)
{
/* This is either the new alphabetical order, or a word to be
alphabetized. */
if (count == -1)
/* This is the new alphabetical order. */
make_order(line, order);
else
/* This is a word to be alphabetized. */
strcpy(words[count], line);
/* Either way, increment our counter. */
count ++;
}
else if (count >= 0)
{
printf("Dataset %d\n", set+1);
/* We should alphabetize the words and print them out in order. */
sort(order, words, count);
/* Reset our counters. */
count = -1;
set ++;
printf("\n");
}
} while (ret);
}
/***************************************************************************
make_order
Makes an array such that given a letter c, the index of c in the new
alphabetical order is order[c - 'a'].
***************************************************************************/
void make_order(char line[MAX], int order[26])
{
int i;
for (i = 0; i < 26; i++)
order[line[i] - 'a'] = i;
}
/***************************************************************************
sort
Print out the words in the new alphabetical order.
***************************************************************************/
void sort(int order[26], char words[NUM][WORD+1], int count)
{
int used[NUM];
int i, j;
int low;
/* Reset used array to all 0's. */
for (i = 0; i < count; i++)
used[i] = 0;
for (i = 0; i < count; i++)
{
/* Each time through loop, find alphabetically-lowest unused word. */
low = -1;
for (j = 0; j < count; j++)
if (!used[j])
{
if (low == -1)
low = j;
else
if (compare(order, words[low], words[j]) == 1)
low = j;
}
/* Now, low is index of smallest word. Print it out. */
printf("%3d: %s\n", i, words[low]);
/* Mark this word as used. */
used[low] = 1;
}
}
/***************************************************************************
compare
Compare the two words a and b. Return -1 if a is less, 0 if they are
the same, and 1 if b is less. Use the new alphabetical order defined by
order.
***************************************************************************/
int compare(int order[26], char a[WORD+1], char b[WORD+1])
{
int i = 0;
int aa, bb;
while (1)
{
if ((a[i] == 0) && (b[i] == 0))
/* We have simultaneously hit the end of both words. They must be the
same. */
return 0;
if (a[i] == 0)
/* We have hit end of a. It must be less. */
return -1;
if (b[i] == 0)
/* We have hit end of b. It must be less. */
return 1;
/* Look up values of ith character in a and b in the new alphabet. */
aa = order[a[i] - 'a'];
bb = order[b[i] - 'a'];
if (aa < bb)
return -1;
if (aa > bb)
return 1;
/* So far, words are same and haven't ended. Keep going. */
i ++;
}
}
The test input was:
abcdefghijklmnopqrstuvwxyz bca bcb aac abb abc aca bcc acb acc baa bbc ccc bab bac bba aab bbb caa cab cac cba cbb aba cbc cca ccb aaa qwertyuiopasdfghjklzxcvbnm now is the time for all good men to come to the aid of their country mary had a little lamb whose fleece was white as snowThe correct output was:
Dataset 1 0: aaa 1: aab 2: aac 3: aba 4: abb 5: abc 6: aca 7: acb 8: acc 9: baa 10: bab 11: bac 12: bba 13: bbb 14: bbc 15: bca 16: bcb 17: bcc 18: caa 19: cab 20: cac 21: cba 22: cbb 23: cbc 24: cca 25: ccb 26: ccc Dataset 2 0: was 1: white 2: whose 3: time 4: to 5: to 6: the 7: the 8: their 9: is 10: of 11: a 12: aid 13: as 14: all 15: snow 16: for 17: fleece 18: good 19: had 20: little 21: lamb 22: country 23: come 24: now 25: men 26: mary