Penalize an incorrect item down to a score of -2
[mnemon] / mnemon.c
1 /*
2  * Copyright © 2006 Carl Worth
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2, or (at your option)
7  * any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
17  */
18
19 /* for asprintf */
20 #define _GNU_SOURCE
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <stdarg.h>
24 #include <stdint.h>
25
26 #include <sys/types.h>
27 #include <dirent.h>
28 #include <errno.h>
29 #include <string.h>
30 #include <assert.h>
31
32 #include <readline/readline.h>
33 #include <readline/history.h>
34
35 typedef int bool_t;
36
37 typedef struct _item {
38     int score;
39     char *challenge;
40     char *response;
41 } item_t;
42
43 typedef struct _bin {
44     int score;
45     int items_size;
46     int num_items;
47     item_t **items;
48 } bin_t;
49
50 typedef struct _category {
51     char *name;
52     int items_size;
53     int num_items;
54     item_t *items;
55 } category_t;
56
57 typedef struct _mnemon {
58     char *dir_name;
59
60     int categories_size;
61     int num_categories;
62     category_t *categories;
63
64     int bins_size;
65     int num_bins;
66     bin_t *bins;
67 } mnemon_t;
68
69 static void *
70 xmalloc (size_t size)
71 {
72     void *ret;
73
74     ret = malloc (size);
75     if (ret == NULL) {
76         fprintf (stderr, "Error: out of memory\n");
77         exit (1);
78     }
79
80     return ret;
81 }
82
83 static void *
84 xrealloc (void *ptr, size_t size)
85 {
86     void *ret;
87
88     ret = realloc (ptr, size);
89     if (ret == NULL) {
90         fprintf (stderr, "Error: out of memory\n");
91         exit (1);
92     }
93
94     return ret;
95 }
96
97 static char *
98 xstrdup (const char *s)
99 {
100     char *ret;
101
102     ret = strdup (s);
103     if (s == NULL) {
104         fprintf (stderr, "Error: out of memory\n");
105         exit (1);
106     }
107
108     return ret;
109 }
110
111 static void
112 xasprintf (char **strp, const char *fmt, ...)
113 {
114     va_list ap;
115     int ret;
116
117     va_start (ap, fmt);
118     ret = vasprintf (strp, fmt, ap);
119     va_end (ap);
120
121     if (ret < 0) {
122         fprintf (stderr, "Error: out of memory\n");
123         exit (1);
124     }
125 }
126
127 static void
128 item_init (item_t       *item,
129            int           score,
130            const char   *challenge,
131            const char   *response)
132 {
133     item->score = score;
134
135     item->challenge = xmalloc (strlen (challenge) + 1 +
136                                strlen (response) + 1);
137     item->response = item->challenge + strlen (challenge) + 1;
138
139     strcpy (item->challenge, challenge);
140     strcpy (item->response, response);
141 }
142
143 static void
144 item_fini (item_t *item)
145 {
146     /* item->response shares allocation with item->challenge, so
147      * doesn't require a separate call to free */
148     free (item->challenge);
149 }
150
151 static void
152 category_init (category_t *category,
153                const char *name)
154 {
155     category->name = xstrdup (name);
156     
157     category->items_size = 0;
158     category->num_items = 0;
159     category->items = NULL;
160 }
161
162 static void
163 category_fini (category_t *category)
164 {
165     int i;
166
167     for (i = 0; i < category->num_items; i++)
168         item_fini (&category->items[i]);
169
170     free (category->items);
171
172     free (category->name);
173 }
174
175 static void
176 category_grow (category_t *category)
177 {
178     if (category->items_size)
179         category->items_size *= 2;
180     else
181         category->items_size = 1;
182
183     category->items = xrealloc (category->items,
184                                 category->items_size * sizeof (item_t));
185 }
186
187 static item_t *
188 category_add_item (category_t   *category,
189                    int           score,
190                    const char   *challenge,
191                    const char   *response)
192 {
193     item_t *item;
194
195     if (category->num_items == category->items_size)
196         category_grow (category);
197
198     item = &category->items[category->num_items++];
199
200     item_init (item, score, challenge, response);
201
202     return item;
203 }
204
205 static void
206 category_print (category_t      *category,
207                 FILE            *file)
208 {
209     int i;
210     item_t *item;
211
212     for (i = 0; i < category->num_items; i++) {
213         item = &category->items[i];
214         if (i != 0)
215             fprintf (file, "\n");
216         fprintf (file, "%d\n%s\n%s\n",
217                  item->score,
218                  item->challenge,
219                  item->response);
220     }
221 }
222
223 static void
224 bin_init (bin_t *bin,
225           int    score)
226 {
227     bin->score = score;
228
229     bin->items_size = 0;
230     bin->num_items = 0;
231     bin->items = NULL;
232 }
233
234 static void
235 bin_fini (bin_t *bin)
236 {
237     free (bin->items);
238 }
239
240 static void
241 bin_grow (bin_t *bin)
242 {
243     if (bin->items_size)
244         bin->items_size *= 2;
245     else
246         bin->items_size = 1;
247
248     bin->items = xrealloc (bin->items,
249                            bin->items_size * sizeof (item_t*));
250 }
251
252 static void
253 bin_add_item (bin_t     *bin,
254               item_t    *item)
255 {
256     assert (item->score == bin->score);
257
258     if (bin->num_items == bin->items_size)
259         bin_grow (bin);
260
261     bin->items[bin->num_items++] = item;
262 }
263
264 static void
265 bin_remove_item (bin_t  *bin,
266                  int     item_index)
267 {
268     /* Replace the current item with the last item, (no need to shift
269      * any more than that since we don't care about the order of the
270      * items within a bin). */
271     bin->num_items--;
272     if (bin->num_items)
273         bin->items[item_index] = bin->items[bin->num_items];
274 }
275
276 static void
277 mnemon_init (mnemon_t *mnemon)
278 {
279     char *home;
280
281     home = getenv ("HOME");
282     if (home == NULL)
283         home = "";
284
285     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
286
287     mnemon->categories_size = 0;
288     mnemon->num_categories = 0;
289     mnemon->categories = NULL;
290
291     mnemon->bins_size = 0;
292     mnemon->num_bins = 0;
293     mnemon->bins = NULL;
294 }
295
296 static void
297 mnemon_fini (mnemon_t *mnemon)
298 {
299     int i;
300
301     for (i = 0; i < mnemon->num_bins; i++)
302         bin_fini (&mnemon->bins[i]);
303     free (mnemon->bins);
304
305     for (i = 0; i < mnemon->num_categories; i++)
306         category_fini (&mnemon->categories[i]);
307     free (mnemon->categories);
308
309     free (mnemon->dir_name);
310 }
311
312 static void
313 mnemon_categories_grow (mnemon_t *mnemon)
314 {
315     if (mnemon->categories_size)
316         mnemon->categories_size *= 2;
317     else
318         mnemon->categories_size = 1;
319
320     mnemon->categories = xrealloc (mnemon->categories,
321                                    mnemon->categories_size * sizeof (category_t));
322 }
323
324 static category_t *
325 mnemon_get_category (mnemon_t   *mnemon,
326                      const char *name)
327 {
328     int i;
329     category_t *category;
330
331     for (i = 0; i < mnemon->num_categories; i++)
332         if (strcmp (mnemon->categories[i].name, name) == 0)
333             return &mnemon->categories[i];
334
335     mnemon_categories_grow (mnemon);
336
337     category = &mnemon->categories[mnemon->num_categories++];
338
339     category_init (category, name);
340
341     return category;
342 }
343
344 static void
345 mnemon_bins_grow (mnemon_t *mnemon)
346 {
347     if (mnemon->bins_size)
348         mnemon->bins_size *= 2;
349     else
350         mnemon->bins_size = 1;
351
352     mnemon->bins = xrealloc (mnemon->bins,
353                              mnemon->bins_size * sizeof (bin_t));
354 }
355
356 static bin_t *
357 mnemon_get_bin (mnemon_t        *mnemon,
358                 int              score)
359 {
360     int i;
361     bin_t *bin;
362
363     for (i = 0; i < mnemon->num_bins; i++)
364         if (mnemon->bins[i].score == score)
365             return &mnemon->bins[i];
366         else if (mnemon->bins[i].score > score)
367             break;
368
369     if (mnemon->num_bins == mnemon->bins_size)
370         mnemon_bins_grow (mnemon);
371
372     bin = &mnemon->bins[i];
373
374     /* Make room to insert new bin at its sorted location. */
375     if (i < mnemon->num_bins)
376         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
377     mnemon->num_bins++;
378
379     bin_init (bin, score);
380
381     return bin;
382 }
383
384 static void
385 mnemon_remove_bin (mnemon_t     *mnemon,
386                    bin_t        *bin)
387 {
388     int i = bin - mnemon->bins;
389
390     bin_fini (bin);
391
392     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
393     mnemon->num_bins--;
394 }
395
396 static void
397 chomp (char *s)
398 {
399     int len = strlen (s);
400     if (len == 0)
401         return;
402     if (s[len - 1] == '\n')
403         s[len - 1] = '\0';
404 }
405
406 static void
407 mnemon_load_category (mnemon_t          *mnemon,
408                       const char        *name)
409 {
410     FILE *file;
411     char *line = NULL, *end;
412     size_t line_size = 0;
413     ssize_t bytes_read;
414     int line_count = 0;
415     char *path;
416     category_t *category;
417     int i;
418
419     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
420     sprintf (path, "%s/%s", mnemon->dir_name, name);
421
422     file = fopen (path, "r");
423     if (file == NULL) {
424         fprintf (stderr, "Error: Failed to open %s: %s\n",
425                  path, strerror (errno));
426         exit (1);
427     }
428
429     category = mnemon_get_category (mnemon, name);
430
431     while (1) {
432         int score;
433         char *challenge, *response;
434
435         /* Read bin number (ignoring blank separator lines) */
436         do {
437             bytes_read = getline (&line, &line_size, file);
438             if (bytes_read == -1)
439                 goto END_OF_FILE;
440             line_count++;
441             chomp (line);
442         } while (*line == '\0');
443
444         score = strtol (line, &end, 10);
445         if (*end != '\0') {
446             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
447                      line, path, line_count);
448             exit (1);
449         }
450
451         /* Read challenge */
452         bytes_read = getline (&line, &line_size, file);
453         if (bytes_read == -1)
454             break;
455         line_count++;
456         chomp (line);
457         challenge = strdup (line);
458
459         /* Read response */
460         bytes_read = getline (&line, &line_size, file);
461         if (bytes_read == -1)
462             break;
463         line_count++;
464         chomp (line);
465         response = line;
466
467         category_add_item (category, score, challenge, response);
468
469         free (challenge);
470     }
471   END_OF_FILE:
472
473     free (line);
474     fclose (file);
475     free (path);
476
477     /* Resize category items to fit exactly. */
478     category->items_size = category->num_items;
479     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
480
481     /* Now that the category is completely loaded, with stable
482      * pointers to every item, we can add each item to its appropriate
483      * bin. */
484     for (i = 0; i < category->num_items; i++) {
485         item_t *item = &category->items[i];
486         bin_t *bin = mnemon_get_bin (mnemon, item->score);
487
488         bin_add_item (bin, item);
489     }
490 }
491
492 static void
493 mnemon_load (mnemon_t *mnemon)
494 {
495     DIR *dir;
496     struct dirent *dirent;
497
498     dir = opendir (mnemon->dir_name);
499     if (dir == NULL) {
500         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
501                  mnemon->dir_name, strerror (errno));
502         exit (1);
503     }
504
505     while (1) {
506         dirent = readdir (dir);
507         if (dirent == NULL)
508             break;
509
510         if (dirent->d_type == DT_REG) {
511             /* Ignore files matching *~, (yes, this shouldn't be
512              * hard-coded in such an ad-hoc way, but there you go. */
513             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
514                 mnemon_load_category (mnemon, dirent->d_name);
515         }
516     }
517
518     closedir (dir);
519 }
520
521 static void
522 mnemon_save (mnemon_t *mnemon)
523 {
524     int i, err;
525     char *filename, *lock_filename;
526     FILE *file;
527     category_t *category;
528
529     for (i = 0; i < mnemon->num_categories; i++) {
530         category = &mnemon->categories[i];
531
532         xasprintf (&filename, "%s/%s",
533                    mnemon->dir_name, category->name);
534         xasprintf (&lock_filename, "%s/.#%s",
535                    mnemon->dir_name, category->name);
536
537         file = fopen (lock_filename, "w");
538         if (file == NULL) {
539             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
540                      lock_filename, strerror (errno));
541             continue;
542         }
543
544         category_print (category, file);
545
546         fclose (file);
547
548         err = rename (lock_filename, filename);
549         if (err < 0) {
550             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
551                      lock_filename, filename, strerror (errno));
552             continue;
553         }
554
555         free (filename);
556         free (lock_filename);
557     }
558 }
559
560 /* Return a uniformly-distributed pseudo-random integer within the
561  * range:
562  *
563  *      0 <= result < num_values
564  */
565 static int
566 rand_within (int num_values)
567 {
568     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
569 }
570
571 /* Return an exponentially-distributed pseudo-random integer within
572  * the range:
573  *
574  *      0 <= result < num_values
575  *
576  * The distribution is such that each successively larger value will
577  * occur with a probability of half of the previous value.
578  */
579 static int
580 rand_within_exponential (int num_values)
581 {
582     static int r;
583     static uint32_t mask = 0;
584     int ones;
585     int bit;
586
587     /* Optimize the constant case. */
588     if (num_values == 1)
589         return 0;
590
591     ones = 0;
592
593     do {
594         if (mask == 0) {
595             r = rand ();
596             mask = 1 << 31;
597             while (mask > RAND_MAX)
598                 mask >>= 1;
599         }
600         bit = r & mask;
601         mask >>= 1;
602         if (bit) {
603             ones++;
604             if (ones == num_values)
605                 ones = 0;
606         }
607     } while (bit);
608
609     return ones;
610 }
611
612 static void
613 mnemon_select_item (mnemon_t     *mnemon,
614                     bin_t       **bin_ret,
615                     int          *item_index_ret)
616 {
617     int bin_index;
618     bin_t *bin;
619
620     bin_index = rand_within_exponential (mnemon->num_bins);
621
622     bin = &mnemon->bins[bin_index];
623
624     *bin_ret = bin;
625     *item_index_ret = rand_within (bin->num_items);
626 }
627
628 static void
629 mnemon_do_challenges (mnemon_t *mnemon,
630                       int       to_introduce)
631 {
632     bin_t *bin;
633     int item_index;
634     item_t *item;
635     char *response;
636     bool_t correct;
637     int unlearned;
638     int i;
639
640     /* Count the number of items with negative scores. */
641     unlearned = 0;
642     for (i = 0; i < mnemon->num_bins; i++) {
643         bin = &mnemon->bins[i];
644         if (bin->score >= 0)
645             break;
646         unlearned += bin->num_items;
647     }
648
649     to_introduce -= unlearned;
650     if (to_introduce < 0)
651         to_introduce = 0;
652
653     if (unlearned) {
654         printf ("You've got %d items to learn already. ", unlearned);
655         if (to_introduce)
656             printf ("I'll introduce %d more as we go.", to_introduce);
657         printf ("\n");
658     } else {
659         printf ("Introducing %d new items.\n", to_introduce);
660     }
661     printf ("\n");
662
663     do {
664         mnemon_select_item (mnemon, &bin, &item_index);
665
666         if (bin->score == 0)
667             to_introduce--;
668
669         item = bin->items[item_index];
670
671         printf ("%s\n", item->challenge);
672
673         response = readline ("> ");
674         if (response == NULL) {
675             printf ("\n");
676             break;
677         }
678
679         correct = (strcmp (response, item->response) == 0);
680
681         bin_remove_item (bin, item_index);
682
683         /* If the bin is now empty, we must remove it. Also if we just
684          * picked the last word we'll ever pick from the bin with
685          * score 0, then we can remove that as well. */
686         if (bin->num_items == 0 ||
687             (bin->score == 0 && to_introduce == 0))
688         {
689             mnemon_remove_bin (mnemon, bin);
690         }
691
692         if (correct) {
693             item->score++;
694             /* We reserve an item score of 0 for an item that has
695              * never been asked. */
696             if (item->score == 0) {
697                 item->score = 1;
698                 unlearned--;
699                 printf ("You got it!");
700             } else if (item->score < 0) {
701                 printf ("Yes---just give me %d more.",
702                         - item->score);
703             } else if (item->score == 1) {
704                 printf ("On your first try, no less!");
705             } else {
706                 printf ("Masterful (%dx).", item->score);
707             }
708         } else {
709             printf ("  %s is the correct answer.",
710                     item->response);
711             /* Penalize an incorrect response by forcing the score
712              * negative. */
713             if (item->score >= 0) {
714                 if (item->score > 0)
715                     printf ( " Oops, you knew that, right?\n ");
716                 unlearned++;
717                 /* We go to -2 to force a little extra reinforcement
718                  * when re-learning an item, (otherwise, it will often
719                  * get asked again immediately where it is easy to get
720                  * a correct response without any learning). */
721                 item->score = -2;
722             } else {
723                 item->score--;
724             }
725         }
726
727         printf (" (");
728         if (to_introduce)
729             printf ("%d to come.", to_introduce);
730         if (to_introduce && unlearned)
731             printf (" ");
732         if (unlearned)
733             printf ("%d still unlearned.", unlearned);
734         if (to_introduce == 0 && unlearned == 0)
735             printf ("Great job!");
736         printf (")\n\n");
737
738         bin = mnemon_get_bin (mnemon, item->score);
739
740         bin_add_item (bin, item);
741     } while (unlearned || to_introduce);
742 }
743
744 int
745 main (int argc, char *argv[])
746 {
747     mnemon_t mnemon;
748
749     srand (time (NULL));
750
751     mnemon_init (&mnemon);
752
753     mnemon_load (&mnemon);
754
755     mnemon_do_challenges (&mnemon, 10);
756
757     mnemon_save (&mnemon);
758
759     mnemon_fini (&mnemon);
760
761     return 0;
762 }