X-Git-Url: https://git.cworth.org/git?a=blobdiff_plain;f=wordgame.c;fp=wordgame.c;h=0000000000000000000000000000000000000000;hb=2eb18813b84ae8ad4faeb92b1d8570599135d537;hp=a9c18d6e7e5e38f7a86f38ec0fde34bd801544fe;hpb=fa25398cc50777016fde97191e1bee1c0ab7d1f1;p=wordgame

diff --git a/wordgame.c b/wordgame.c
deleted file mode 100644
index a9c18d6..0000000
--- a/wordgame.c
+++ /dev/null
@@ -1,526 +0,0 @@
-/*
- * Copyright © 2006 Carl Worth
- *
- * This program is free software; you can redistribute it and\/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2, or (at your option)
- * any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
- */
-
-/* Portably, schmortability. I want ease of programming. */
-#define _GNU_SOURCE
-#include <stdio.h>
-#include <stdlib.h>
-#include <stdint.h>
-#include <string.h>
-#include <errno.h>
-#include <ctype.h>
-#include <sys/time.h>
-#include <time.h>
-#include <math.h>
-
-#include <readline/readline.h>
-#include <readline/history.h>
-
-#ifndef FALSE
-# define FALSE 0
-#endif
-
-#ifndef TRUE
-# define TRUE 1
-#endif
-
-typedef int bool_t;
-
-#define TRIE_FLAGS_IS_WORD	(1<<0)
-#define TRIE_FLAGS_SEEN		(1<<1)
-
-typedef struct _trie {
-    uint32_t flags;
-    struct _trie *next[26];
-} trie_t;
-
-typedef bool_t
-(*trie_predicate_t) (trie_t *trie);
-
-void *
-xmalloc (size_t size)
-{
-    void *res;
-
-    res = malloc (size);
-    if (res == NULL) {
-	fprintf (stderr, "Error: out of memory\n");
-	exit (1);
-    }
-
-    return res;
-}
-
-void *
-xrealloc (void *ptr, size_t size)
-{
-    void *res;
-
-    res = realloc (ptr, size);
-    if (res == NULL) {
-	fprintf (stderr, "Error: out of memory\n");
-	exit (1);
-    }
-
-    return res;
-}
-
-void
-chomp (char *s)
-{
-    int len = strlen (s);
-    if (s[len - 1] == '\n')
-	s[len - 1] = '\0';
-}
-
-typedef struct _string {
-    size_t size;
-    char *s;
-    size_t len;
-} string_t;
-
-void
-string_init (string_t *string)
-{
-    string->size = 0;
-    string->s = NULL;
-    string->len = 0;
-}
-
-void
-string_fini (string_t *string)
-{
-    string->size = 0;
-    if (string->s)
-	free (string->s);
-    string->len = 0;
-}
-
-void
-string_append_char (string_t *string, char c)
-{
-    if (string->size == 0) {
-	string->size = 8;
-	string->s = xmalloc (string->size);
-	string->s[0] = '\0';
-	string->len = 0;
-    }
-
-    if (string->len + 1 == string->size) {
-	string->size *= 2;
-	string->s = xrealloc (string->s, string->size);
-    }
-
-    string->s[string->len++] = c;
-    string->s[string->len] = '\0';
-}
-
-void
-string_chop (string_t *string)
-{
-    if (string->len == 0)
-	return;
-
-    string->s[--string->len] = '\0';
-}
-
-static void
-trie_init (trie_t *trie)
-{
-    int i;
-    trie->flags = 0;
-    for (i = 0; i < 26; i++)
-	trie->next[i] = NULL;
-}
-
-trie_t *
-trie_create (void)
-{
-    trie_t *trie;
-
-    trie = xmalloc (sizeof (trie_t));
-
-    trie_init (trie);
-
-    return trie;
-}
-
-void
-trie_destroy (trie_t *trie)
-{
-    int i;
-
-    for (i = 0; i < 26; i++)
-	if (trie->next[i])
-	    trie_destroy (trie->next[i]);
-
-    free (trie);
-}
-
-#define TRIE_CHAR_TO_INDEX(c)	(tolower (c) - 'a')
-#define TRIE_INDEX_TO_CHAR(i)	(i + 'a')
-void
-trie_add (trie_t	*trie,
-	  const char	*word_chunk)
-{
-    char c = word_chunk[0];
-    int i;
-
-    if (c == '\0') {
-	trie->flags |= TRIE_FLAGS_IS_WORD;
-	return;
-    }
-
-    i = TRIE_CHAR_TO_INDEX (c);
-    if (trie->next[i] == NULL)
-	trie->next[i] = trie_create ();
-
-    trie_add (trie->next[i], word_chunk + 1);
-}
-
-trie_t *
-trie_find (trie_t	*trie,
-	   const char	*word_chunk)
-{
-    const char *s = word_chunk;
-
-    while (trie && *s)
-	trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
-
-    return trie;
-}
-
-int
-trie_print (trie_t		*trie,
-	    string_t		*string,
-	    trie_predicate_t	 predicate)
-{
-    char c;
-    int i;
-    int count = 0;
-
-    if (trie->flags & TRIE_FLAGS_IS_WORD
-	&& (predicate == NULL || predicate (trie)))
-    {
-	count = 1;
-	printf ("%s ", string->s);
-    }
-
-    /* Loop over each element, appending the character and recursing. */
-    for (i = 0; i < 26; i++) {
-	if (trie->next[i] == NULL)
-	    continue;
-
-	c = TRIE_INDEX_TO_CHAR (i);
-
-	string_append_char (string, c);
-	count += trie_print (trie->next[i], string, predicate);
-	string_chop (string);
-    }
-
-    return count;
-}
-
-bool_t
-trie_seen_predicate (trie_t *trie)
-{
-    return (trie->flags & TRIE_FLAGS_SEEN);
-}
-
-int
-trie_print_seen (trie_t *trie, string_t *word)
-{
-    return trie_print (trie, word, trie_seen_predicate);
-}
-
-bool_t
-trie_unseen_predicate (trie_t *trie)
-{
-    return (! trie_seen_predicate (trie));
-}
-
-int
-trie_print_unseen (trie_t *trie, string_t *word)
-{
-    return trie_print (trie, word, trie_unseen_predicate);
-}
-
-typedef struct _dict {
-    trie_t *trie;
-} dict_t;
-
-void
-dict_init (dict_t 	*dict,
-	   const char	*filename)
-{
-    FILE *file;
-    char *line = NULL;
-    size_t line_size = 0;
-    ssize_t bytes_read;
-
-    file = fopen (filename, "r");
-    if (file == NULL) {
-	fprintf (stderr, "Error: failed to open %s: %s\n",
-		 filename, strerror (errno));
-	exit (1);
-    }
-
-    dict->trie = trie_create ();
-
-    while (1) {
-	bytes_read = getline (&line, &line_size, file);
-	if (bytes_read == -1)
-	    break;
-	chomp (line);
-	trie_add (dict->trie, line);
-    }
-    if (line)
-	free (line);
-
-    fclose (file);
-}
-
-void
-dict_fini (dict_t *dict)
-{
-    trie_destroy (dict->trie);
-}
-
-void
-dict_print (dict_t *dict)
-{
-    string_t string;
-
-    string_init (&string);
-
-    trie_print (dict->trie, &string, NULL);
-
-    string_fini (&string);
-}
-
-char *cube_faces[16] = {
-    "aaeeng", "abbjoo", "achops", "affkps",
-    "aoottw", "cimotu", "deilrx", "delrvy",
-    "distty", "eeghnw", "eeinsu", "ehrtvw",
-    "eiosst", "elrtty", "himnqu", "hlnnrz"
-};
-
-typedef struct _board {
-    char letters[4][4];
-
-    /* Private, transient state used by enumerate */
-    trie_t *result_trie;
-} board_t;
-
-int
-rand_within (int num_values)
-{
-    return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
-}
-
-void
-shuffle (int *array, int length)
-{
-    int i, r, tmp;
-
-    for (i = 0; i < length; i++)
-    {
-	r = i + rand_within (length - i);
-	tmp = array[i];
-	array[i] = array[r];
-	array[r] = tmp;
-    }
-}
-
-void
-board_init (board_t *board)
-{
-    int i;
-    int cubes[16];
-
-    for (i = 0; i < 16; i++)
-	cubes[i] = i;
-    shuffle (cubes, 16);
- 
-    for (i = 0; i < 16; i++)
-	board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
-}
-
-void
-board_print (board_t *board)
-{
-    int x, y;
-    char c;
-
-    printf ("\n");
-    for (y = 0; y < 4; y++) {
-	for (x = 0; x < 4; x++) {
-	    c = board->letters[y][x];
-	    printf (" %c%s", toupper (c),
-		    c == 'q' ? "u" : " ");
-	}
-	printf ("\n");
-    }
-    printf ("\n");
-}
-
-#define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
-void
-board_enumerate (board_t	*board,
-		 int		 x,
-		 int		 y,
-		 int16_t	 seen,
-		 string_t	*word,
-		 trie_t		*dict_trie)
-{
-    char c;
-    int dx, dy;
-
-    if (x < 0 || x >= 4 ||
-	y < 0 || y >= 4 ||
-	seen & SEEN_BIT (x, y))
-    {
-	return;
-    }
-
-    seen |= SEEN_BIT (x, y);
-
-    c = board->letters[y][x];
-    string_append_char (word, c);
-    dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)];
-    if (dict_trie == NULL)
-	goto BAIL0;
-
-    if (c == 'q') {
-	string_append_char (word, 'u');
-	dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
-	if (dict_trie == NULL)
-	    goto BAIL1;
-    }
-
-    if (dict_trie->flags & TRIE_FLAGS_IS_WORD)
-	trie_add (board->result_trie, word->s);
-
-    for (dy = -1; dy <= 1; dy++)
-	for (dx = -1; dx <= 1; dx++)
-	    board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
-
-  BAIL1:
-    if (c == 'q')
-	string_chop (word);
-  BAIL0:
-    string_chop (word);
-}
-
-void
-board_solve (board_t *board, dict_t *dict, trie_t *solution)
-{
-    int x, y;
-    int16_t seen = 0;
-    string_t word;
-
-    board->result_trie = solution;
-
-    string_init (&word);
-
-    for (y = 0; y < 4; y++)
-	for (x = 0; x < 4; x++)
-	    board_enumerate (board, x, y, seen, &word, dict->trie);
-
-    string_fini (&word);
-}
-
-#define GAME_LENGTH (3 * 60)
-int
-main (void)
-{
-    dict_t dict;
-    board_t board;
-    trie_t *solution;
-    struct timeval tv, tv_stop;
-    int remaining, minutes, seconds;
-    int found, missed;
-    char prompt[7], *response;
-    string_t word;
-
-    gettimeofday (&tv, NULL);
-    srand (tv.tv_sec ^ tv.tv_usec);
-
-    dict_init (&dict, "words.txt");
-    board_init (&board);
-
-    solution = trie_create ();
-    board_solve (&board, &dict, solution);
-
-    board_print (&board);
-
-    gettimeofday (&tv, NULL);
-    tv_stop = tv;
-    tv_stop.tv_sec += GAME_LENGTH;
-    remaining = GAME_LENGTH;
-    do {
-	minutes = remaining / 60;
-	seconds = remaining % 60;
-	sprintf (prompt, "%02d:%02d ", minutes, seconds);
-	response = readline (prompt);
-	add_history (response);
-	chomp (response);
-	if (strlen (response) == 0) {
-	    board_print (&board);
-	} else {
-	    trie_t *t;
-	    t = trie_find (solution, response);
-	    if (t && (t->flags & TRIE_FLAGS_IS_WORD)) {
-		if (t->flags & TRIE_FLAGS_SEEN)
-		    printf ("(repeat)\n");
-		else
-		    t->flags |= TRIE_FLAGS_SEEN;
-	    } else {
-		t = trie_find (dict.trie, response);
-		if (t && (t->flags & TRIE_FLAGS_IS_WORD))
-		    printf ("(a good word, but it's not in the puzzle)\n");
-		else
-		    printf ("*** %s is not a word\n", response);
-	    }
-	}
-	free (response);
-	gettimeofday (&tv, NULL);
-	remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
-	minutes = remaining / 60;
-    } while (remaining > 0);
-
-    printf ("\nWords you found:\n");
-    string_init (&word);
-    found = trie_print_seen (solution, &word);
-    string_fini (&word);
-    printf ("\n");
-
-    printf ("\nWords you missed:\n");
-    string_init (&word);
-    missed = trie_print_unseen (solution, &word);
-    string_fini (&word);
-    printf ("\n");
-
-    printf ("\nYou found %d of %d words (%.2f%%)\n",
-	    found, found + missed,
-	    100 * (double) found / (found + missed));
-
-    dict_fini (&dict);
-
-    return 0;
-}