#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Calculate an exponential practice schedule for near-optimal learning.

The basis of this thing here is that generally you retain a fact or
skill without practicing it for some fixed multiple of the amount of
time you’ve already retained it, say about five times as long.  Some
kinds of knowledge last longer, and some learners retain knowledge
longer, but the overall rule is exponential: if you’ve known someone’s
name for five seconds, you can remember it for about thirty seconds
without being reminded, and if you use it at that point (practicing
it), you can remember it for two or three minutes; but if you’ve known
someone (and their name) for a year, you can probably remember it if
you happen to see them again four years later, but maybe not ten years
later, assuming you haven’t happened to think of them in the meantime.

This kind of constant forgetting is presumably helpful to avoid the
retention of now-irrelevant learned responses to past conditions, but
it can be a real annoyance when you are trying to learn things.
However, it doesn’t actually limit the amount you can learn, just
imposes some bookkeeping requirements on your learning optimization
system.

Anki and AnyMemo, among other programs, use this principle of spaced
repetition to help you memorize flash cards, but it’s more broadly
applicable, I think even to practicing procedural skills.

This program calculates a hypothetical learning practice schedule
under some simplifying assumptions, using a recursive temporal
backtracking approach.  It doesn’t try to calculate an *optimal*
practice schedule, just one that won’t lead to you forgetting stuff in
the middle (although it does prefer introducing new material to
practicing old material when possible, thus using greedy search to try
to get close to the optimum), and it sometimes gets a little too
aggressive toward the end, meaning that you would inevitably forget a
bit right afterwards.  Its approach takes time apparently exponential
in the length of schedule it is asked to put together; here are
results for 160, 130, 100, and 60:

ABCDABCDEFGHEFGHIJJIABCDKJKKEFGHILMNNLMOKPONQPRSQSRSLJMOTUVUTPVWQWRSXUYNXZYWTZVabIAabBCDXZYKEFGHcdcabdefffeOcUgggLfWhdMihgeijPkjQkRSlmlmhkjiTZVnlmoncpofXpYqrsgt
ABCDABCDEFGHEFGHIJJIABCDKJKKEFGHILMNNLMOKPONQPRSQSRSLJMOTUVUTPVWQWRSXUYNXZYWTZVabIAabBCDXZYKEFGHcdcabdefffeOcUgggLfWhdMihgeijPkjQl
ABCDABCDEFGHEFGHIJJIABCDKJKKEFGHILMNNLMOKPONQPRSQSRSLJMOTUVUTPVWQWRSXUYNXZYWTZVabIAabBCDXZYKEFGHcdef
ABCDABCDEFGHEFGHIJJIABCDKJKKEFGHILMNNLMOKPONQPRSQSRSLJMOTUVW

Note that the 60-time-unit plan ends in a W, which the 100-unit plan
doesn’t introduce for four more time units, because at that point it
was becoming necessary to practice all of T, P, and V, leaving no time
to practice U later, so U got practiced early, postponing the
introduction time of W.

The 100-unit plan covers 31 letters, of which many are practiced four
times; a few (like K) are unaccountably practiced 5 times; most
(especially L and onwards) are practiced three times; and the last few
introduced (the lowercase letters) are only practiced once or twice.
It’s interesting to note that in the last 21 letters, only 6 new
letters are introduced; the others are all review.  Presumably this is
close to the limiting distribution of review versus new material:
about one third new material, two thirds review, under the assumption
of 4× unpracticed retention.

It seems apparent that the plan is suboptimal; surely the repetitions
fff and ggg could be dealt with by practicing some old material
earlier (such as O, c, U, L, or W), thus allowing a more efficient
introduction of f and g.

Presumably the algorithm runs slowly because its backtracking is
purely temporal, and a bit of nogood recording would get it to run in
essentially linear time.

Times:

60: 260ms
100: 4.5s
130: 5.0s
150: 32.4s
160: 32.4s

These don’t fit an exponential curve very well!

Running with multiple=4 instead of 3, I get this plan:

ABCDEABCDEFGHIJFGHIJKLMNOKLMNOABCDEPQQQPFGHIJRSSRQKLMNOTSUVTPWUVXRWYZXabYZcabdecTfdeghfUVghWijXjiYZbaSkkcjQdellfkmghnimlonpqrospqrtsuvwtxuvy

Using reverse=False (preferring to practice older material instead of
newer material) finds feasible schedules faster, and although they are
different, it is not clear that they are worse, and they may even be
better by some epsilon; for example:

ABCDABCDEFGHEFGHIJABIJCDKLEFKLGHMNIJMNOPQKOPQLRSTMRSTNUVOPUVQWXARWXSTYZAUYZVaBbWaXbAEFCDAYZGIJHKacbdecMdefghLfghiNOPicjdeRjAQfghkl
ABCDABCDEFGHEFGHIJABIJCDKLEFKLGHMNIJMNOPQKOPQLRSTMRSTNUVOPUVQWXARWXSTYZAUYZVaBbWaXbAEFCDAYZGIJHKacbdecMdefghLfghiNOPicjdeRjAQfghASUTiklWjklVmnXomnpoqYpZqklrstuv

These are apparently suboptimal by spending 7 practice slots on A
instead of the requisite 4, but the other letters seem to be
distributed nearly perfectly.

This kind of thing might also work as rhyme schemes or melodies,
although maybe more repetition would be optimal; here’s 2,
reverse=False:

ABCABCDEFDEFABCGADGEFHIJHIJGKLAKLHIJMBCMKLDNAENFMOPAOPGNQHIQJOPRAKRLQSTASTMRUVNUVSTWAOWPUVXYQXYWZabc

And 1.5, reverse=False:

ABABCACDBDECEADFEFGAGBFACGDEHIHIJFJHIAGJKLKLMHMKLIAMJBAECDNKNLFAMNOPOPGAHOPQAQNRIRQAJORPSKSTLTQSMUTV

And 1.2, reverse=False:

ABABCACBDCDEAEDBCEFGFGADFGEHAHBCFHGIJIJAHIJDKEKAFIKJLGLMHMLKNMNABCNLIAMJOAONPOPKQPQDFOQLEPMRHRNQGRST

And 1.1, reverse=False:

ABABCACBDCDEAEDBCEFGFGDEFGHAHBCFHGIAIDEHIJKJKFIJKLGLAHJLKMBMCILMNANDEJNMOKOFLNOPAPAGHPOQMQINPQRSRSTU

And 1.01, reverse=False:

ABABCACBDCDEAEDBCEFGFGDEFGAHBHCFGHIAIEDAIHJAJFGIJKLKLBJKLHCMEMIKLMNJNADANMFGOKOLNPOPQHQPMOQRIRJPNRQS

Of course, a real learning optimization planning system would need to
take into account the random nature of learning, the percentage of
failures, the differing time needed to learn a new skill and practice
an existing skill, the fact that skill-to-task mapping is many-to-many
(so it is possible to practice many skills at once, but not any
possible combination), and so on.

"""
import sys

def main():
    print(''.join(schedule(int(sys.argv[1]), 3,
                           'abcdefghijklmnopqrstuvwxyz'
                           + 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')))

def schedule(length, multiple, items, reverse=True):
    for possibility in _schedule([], length, multiple, items, reverse):
        return possibility

def _schedule(previous, length, multiple, items, reverse):
    if length == 0:
        yield []
        return

    previous_items = set(previous)

    if any(is_overdue(item, previous, multiple) for item in previous_items):
        return

    # All items that haven’t occurred previously are equivalent, so we
    # only consider the first one of them here to avoid a massive
    # exponential slowdown.
    for item in ([sorted(set(items) - previous_items)[0]]
                 + sorted(previous_items, reverse=reverse)):
        for possibility in _schedule(previous + [item], length-1, multiple, items, reverse):
            yield [item] + possibility

def is_overdue(item, previous, multiple):
    first_index = previous.index(item) # raises ValueError if not present
    
    for index in range(len(previous)-1, -1, -1):
        if previous[index] == item:
            last_index = index
            break

    known_span = last_index - first_index + 1
    unpracticed_span = len(previous)-1 - last_index
    return known_span * multiple < unpracticed_span

if __name__ == '__main__':
    main()