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