#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
+#include <stdint.h>
+#include <math.h>
#include <sys/types.h>
#include <dirent.h>
#include <string.h>
#include <assert.h>
+#include <readline/readline.h>
+#include <readline/history.h>
+
+typedef int bool_t;
+
typedef struct _item {
- int count;
+ int score;
char *challenge;
char *response;
} item_t;
typedef struct _bin {
- int count;
+ int score;
int items_size;
int num_items;
item_t **items;
int bins_size;
int num_bins;
bin_t *bins;
+
+ int to_introduce;
+ int to_master;
+ int unlearned;
+ int mastered;
} mnemon_t;
static void *
static void
item_init (item_t *item,
- int count,
+ int score,
const char *challenge,
const char *response)
{
- item->count = count;
+ item->score = score;
item->challenge = xmalloc (strlen (challenge) + 1 +
strlen (response) + 1);
static item_t *
category_add_item (category_t *category,
- int count,
+ int score,
const char *challenge,
const char *response)
{
item = &category->items[category->num_items++];
- item_init (item, count, challenge, response);
+ item_init (item, score, challenge, response);
return item;
}
if (i != 0)
fprintf (file, "\n");
fprintf (file, "%d\n%s\n%s\n",
- item->count,
+ item->score,
item->challenge,
item->response);
}
static void
bin_init (bin_t *bin,
- int count)
+ int score)
{
- bin->count = count;
+ bin->score = score;
bin->items_size = 0;
bin->num_items = 0;
bin_add_item (bin_t *bin,
item_t *item)
{
- assert (item->count == bin->count);
+ assert (item->score == bin->score);
if (bin->num_items == bin->items_size)
bin_grow (bin);
bin->items[bin->num_items++] = item;
}
+static void
+bin_remove_item (bin_t *bin,
+ int item_index)
+{
+ /* Replace the current item with the last item, (no need to shift
+ * any more than that since we don't care about the order of the
+ * items within a bin). */
+ bin->num_items--;
+ if (bin->num_items)
+ bin->items[item_index] = bin->items[bin->num_items];
+}
+
static void
mnemon_init (mnemon_t *mnemon)
{
mnemon->bins_size = 0;
mnemon->num_bins = 0;
mnemon->bins = NULL;
+
+ mnemon->to_introduce = 3;
+ mnemon->to_master = 0;
+ mnemon->unlearned = 0;
+ mnemon->mastered = -1;
}
static void
static bin_t *
mnemon_get_bin (mnemon_t *mnemon,
- int count)
+ int score)
{
int i;
bin_t *bin;
for (i = 0; i < mnemon->num_bins; i++)
- if (mnemon->bins[i].count == count)
+ if (mnemon->bins[i].score == score)
return &mnemon->bins[i];
+ else if (mnemon->bins[i].score > score)
+ break;
+
+ if (mnemon->num_bins == mnemon->bins_size)
+ mnemon_bins_grow (mnemon);
- mnemon_bins_grow (mnemon);
+ bin = &mnemon->bins[i];
- bin = &mnemon->bins[mnemon->num_bins++];
+ /* Make room to insert new bin at its sorted location. */
+ if (i < mnemon->num_bins)
+ memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
+ mnemon->num_bins++;
- bin_init (bin, count);
+ bin_init (bin, score);
return bin;
}
static void
-mnemon_add_item (mnemon_t *mnemon,
- category_t *category,
- int count,
- const char *challenge,
- const char *response)
+mnemon_remove_bin (mnemon_t *mnemon,
+ bin_t *bin)
{
- item_t *item;
- bin_t *bin;
+ int i = bin - mnemon->bins;
- item = category_add_item (category, count, challenge, response);
+ bin_fini (bin);
- bin = mnemon_get_bin (mnemon, count);
-
- bin_add_item (bin, item);
+ memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
+ mnemon->num_bins--;
}
static void
int line_count = 0;
char *path;
category_t *category;
+ int i;
path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
sprintf (path, "%s/%s", mnemon->dir_name, name);
category = mnemon_get_category (mnemon, name);
while (1) {
- int count;
+ int score;
char *challenge, *response;
/* Read bin number (ignoring blank separator lines) */
chomp (line);
} while (*line == '\0');
- count = strtol (line, &end, 10);
+ score = strtol (line, &end, 10);
if (*end != '\0') {
fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
line, path, line_count);
chomp (line);
response = line;
- mnemon_add_item (mnemon, category, count, challenge, response);
+ category_add_item (category, score, challenge, response);
free (challenge);
}
free (line);
fclose (file);
free (path);
+
+ /* Resize category items to fit exactly. */
+ category->items_size = category->num_items;
+ category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
+
+ /* Now that the category is completely loaded, with stable
+ * pointers to every item, we can add each item to its appropriate
+ * bin. */
+ for (i = 0; i < category->num_items; i++) {
+ item_t *item = &category->items[i];
+ bin_t *bin = mnemon_get_bin (mnemon, item->score);
+
+ bin_add_item (bin, item);
+ }
}
static void
mnemon->dir_name, category->name);
xasprintf (&lock_filename, "%s/.#%s",
mnemon->dir_name, category->name);
+
file = fopen (lock_filename, "w");
if (file == NULL) {
fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
category_print (category, file);
+ fclose (file);
+
err = rename (lock_filename, filename);
if (err < 0) {
- fprintf (stderr, "Error: Failes to rename %s to %s: %s\n",
+ fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
lock_filename, filename, strerror (errno));
continue;
}
+
+ free (filename);
+ free (lock_filename);
}
}
+/* Return a uniformly-distributed pseudo-random integer within the
+ * range:
+ *
+ * 0 <= result < num_values
+ */
+static int
+rand_within (int num_values)
+{
+ return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
+}
+
+/* Return an exponentially-distributed pseudo-random integer within
+ * the range:
+ *
+ * 0 <= result < num_values
+ *
+ * The distribution is such that each successively larger value will
+ * occur with a probability of half of the previous value.
+ */
+static int
+rand_within_exponential (int num_values)
+{
+ static int r;
+ static uint32_t mask = 0;
+ int ones;
+ int bit;
+
+ /* Optimize the constant case. */
+ if (num_values == 1)
+ return 0;
+
+ ones = 0;
+
+ do {
+ if (mask == 0) {
+ r = rand ();
+ mask = 1 << 31;
+ while (mask > RAND_MAX)
+ mask >>= 1;
+ }
+ bit = r & mask;
+ mask >>= 1;
+ if (bit) {
+ ones++;
+ if (ones == num_values)
+ ones = 0;
+ }
+ } while (bit);
+
+ return ones;
+}
+
+static void
+mnemon_select_item (mnemon_t *mnemon,
+ bin_t **bin_ret,
+ int *item_index_ret)
+{
+ int bin_index;
+ bin_t *bin;
+
+ bin_index = rand_within_exponential (mnemon->num_bins);
+
+ bin = &mnemon->bins[bin_index];
+
+ *bin_ret = bin;
+ *item_index_ret = rand_within (bin->num_items);
+}
+
+
+#define HISTOGRAM_ROW_FORMAT "%3d: %3d"
+#define HISTOGRAM_BAR_WIDTH 63
+
+static void
+print_histogram_bar (double size,
+ double max)
+{
+ int units_per_cell = (int) ceil (max / HISTOGRAM_BAR_WIDTH);
+ static char const *boxes[8] = {
+ "█", "▉", "▊", "▋",
+ "▌", "▍", "▎", "▏"
+ };
+
+ while (size > units_per_cell) {
+ printf(boxes[0]);
+ size -= units_per_cell;
+ }
+
+ size /= units_per_cell;
+
+ if (size > 7.5/8.0)
+ printf(boxes[0]);
+ else if (size > 6.5/8.0)
+ printf(boxes[1]);
+ else if (size > 5.5/8.0)
+ printf(boxes[2]);
+ else if (size > 4.5/8.0)
+ printf(boxes[3]);
+ else if (size > 3.5/8.0)
+ printf(boxes[4]);
+ else if (size > 2.5/8.0)
+ printf(boxes[5]);
+ else if (size > 1.5/8.0)
+ printf(boxes[6]);
+ else if (size > 0.5/8.0)
+ printf(boxes[7]);
+
+ printf ("\n");
+}
+
+static void
+mnemon_print_histogram (mnemon_t *mnemon)
+{
+ int i, last_score, max;
+ bin_t *bin;
+
+ if (mnemon->num_bins == 0)
+ return;
+
+ max = mnemon->bins[0].num_items;
+ for (i = 1; i < mnemon->num_bins; i++)
+ if (mnemon->bins[i].num_items > max)
+ max = mnemon->bins[i].num_items;
+
+ for (i = 0; i < mnemon->num_bins; i++) {
+ bin = &mnemon->bins[i];
+ if (i != 0)
+ while (bin->score - last_score > 1)
+ printf (HISTOGRAM_ROW_FORMAT "\n", ++last_score, 0);
+ printf (HISTOGRAM_ROW_FORMAT " ", bin->score, bin->num_items);
+ print_histogram_bar (bin->num_items, max);
+ last_score = bin->score;
+ }
+}
+
+static void
+mnemon_handle_command (mnemon_t *mnemon,
+ const char *command)
+{
+ switch (command[0]) {
+ case 'h':
+ mnemon_print_histogram (mnemon);
+ break;
+ default:
+ printf ("Unknown command: %s\n", command);
+ break;
+ }
+}
+
+static void
+mnemon_handle_response (mnemon_t *mnemon,
+ bin_t *bin,
+ int item_index,
+ item_t *item,
+ const char *response)
+{
+ bool_t correct;
+
+ correct = (strcmp (response, item->response) == 0);
+
+ bin_remove_item (bin, item_index);
+
+ /* If the bin is now empty, we must remove it. Also if we just
+ * picked the last word we'll ever pick from the bin with
+ * score 0, then we can remove that as well. */
+ if (bin->num_items == 0 ||
+ (bin->score == 0 && mnemon->to_introduce == 0))
+ {
+ mnemon_remove_bin (mnemon, bin);
+ }
+
+ if (correct) {
+ item->score++;
+ /* We reserve an item score of 0 for an item that has
+ * never been asked. */
+ if (item->score == 0) {
+ item->score = 1;
+ mnemon->unlearned--;
+ printf ("You got it!");
+ if (mnemon->unlearned == 0 && mnemon->to_master == 0) {
+ mnemon->to_master = 10;
+ mnemon->mastered = 0;
+ }
+ } else if (item->score < 0) {
+ printf ("Yes---just give me %d more.",
+ - item->score);
+ } else if (item->score == 1) {
+ printf ("On your first try, no less!");
+ } else {
+ printf ("Masterful (%dx).", item->score);
+ if (mnemon->to_master)
+ mnemon->mastered++;
+ }
+ } else {
+ printf (" %s is the correct answer.",
+ item->response);
+ /* Penalize an incorrect response by forcing the score
+ * negative. */
+ if (item->score >= 0) {
+ if (item->score > 0)
+ printf ( " Oops, you knew that, right?\n ");
+ mnemon->unlearned++;
+ /* We go to -2 to force a little extra reinforcement
+ * when re-learning an item, (otherwise, it will often
+ * get asked again immediately where it is easy to get
+ * a correct response without any learning). */
+ item->score = -2;
+ } else {
+ item->score--;
+ }
+ }
+
+ printf (" ");
+ if (mnemon->to_introduce)
+ printf ("%d to come. ", mnemon->to_introduce);
+ if (mnemon->unlearned)
+ printf ("%d still unlearned. ", mnemon->unlearned);
+ if (mnemon->to_master) {
+ if (mnemon->mastered < mnemon->to_master)
+ printf ("%d items to master",
+ mnemon->to_master - mnemon->mastered);
+ else
+ printf ("Great job!");
+ }
+ printf ("\n\n");
+
+ bin = mnemon_get_bin (mnemon, item->score);
+
+ bin_add_item (bin, item);
+}
+
+static void
+mnemon_do_challenges (mnemon_t *mnemon)
+{
+ bin_t *bin;
+ int item_index;
+ item_t *item;
+ char *response;
+ int i;
+
+ /* Count the number of items with negative scores. */
+ mnemon->unlearned = 0;
+ for (i = 0; i < mnemon->num_bins; i++) {
+ bin = &mnemon->bins[i];
+ if (bin->score >= 0)
+ break;
+ mnemon->unlearned += bin->num_items;
+ }
+
+ mnemon->to_introduce -= mnemon->unlearned;
+ if (mnemon->to_introduce < 0)
+ mnemon->to_introduce = 0;
+
+ /* Get rid of bin with score of 0 if we aren't going to be
+ * introducing anything from it. */
+ if (mnemon->to_introduce == 0) {
+ bin = mnemon_get_bin (mnemon, 0);
+ mnemon_remove_bin (mnemon, bin);
+ }
+
+ if (mnemon->unlearned) {
+ printf ("You've got %d items to learn already. ", mnemon->unlearned);
+ if (mnemon->to_introduce)
+ printf ("I'll introduce %d more as we go.", mnemon->to_introduce);
+ printf ("\n");
+ } else {
+ printf ("Introducing %d new items.\n", mnemon->to_introduce);
+ }
+ printf ("\n");
+
+ do {
+ mnemon_select_item (mnemon, &bin, &item_index);
+ item = bin->items[item_index];
+
+ if (bin->score == 0)
+ mnemon->to_introduce--;
+
+ while (1) {
+ printf ("%s\n", item->challenge);
+
+ response = readline ("> ");
+ /* Terminate on EOF */
+ if (response == NULL) {
+ printf ("\n");
+ return;
+ }
+
+ if (response[0] == '/')
+ mnemon_handle_command (mnemon, response + 1);
+ else
+ break;
+ }
+
+ mnemon_handle_response (mnemon, bin, item_index,
+ item, response);
+ } while (mnemon->mastered < mnemon->to_master);
+}
+
int
main (int argc, char *argv[])
{
mnemon_t mnemon;
+ srand (time (NULL));
+
mnemon_init (&mnemon);
mnemon_load (&mnemon);
+ mnemon_do_challenges (&mnemon);
+
mnemon_save (&mnemon);
mnemon_fini (&mnemon);