text:
Patch the Paragraph
In the spirit of Patch the Image, here's a similar challenge but with text.
Challenge
Bit rot has afflicted your precious text! Given a paragraph composed of ASCII characters, with a rectangular hole somewhere in it, your program should try to fill in the hole with appropriate text, so that the paragraph blends as best as possible.
Further definitions

The hole will always be rectangular, and it may span multiple lines.
There will only ever be one hole.
Note that the hole does not necessarily fall on word boundaries (in fact, it usually won't).
The hole will be at most 25% of the input paragraph, but may overlap or extend past the "end" of the "normal" text (see the Euclid or Badger examples below).
Since finding the hole is not the main point of this challenge, it will be composed solely of hash marks # to allow for easy identification.
No other location in the input paragraph will have a hash mark.
Your code cannot use the "normal" text in the examples below - it will only receive and process the text with the hole in it.
The input can be as a single multi-line string, as an array of strings (one element per line), as a file, etc. -- your choice of what is most convenient for your language.
If desired, an optional additional input detailing the coordinates of the hole can be taken (e.g., a tuple of coordinates or the like).
Please describe your algorithm in your submission.

Voting
Voters are asked to judge the entries based on how well the algorithm fills in the text hole. Some suggestions include the following:

Does the filled in area match the approximate distribution of spaces and punctuation as the rest of the paragraph?
Does the filled in area introduce faulty syntax? (e.g., two spaces in a row, a period followed by a question mark, an erroneous sequence like , ,, etc.)
If you squint your eyes (so you're not actually reading the text), can you see where the hole used to be?
If there aren't any CamelCase words outside the hole, does the hole contain any? If there aren't any Capitalized Letters outside the hole, does the hole contain any? If There Are A Lot Of Capitalized Letters Outside The Hole, does the hole contain a proportionate amount?

Validity Criterion
In order for a submission to be considered valid, it must not alter any text of the paragraph outside of the hole (including trailing spaces). A single trailing newline at the very end is optional.
Test Cases
Format is original paragraph in a code block, followed by the same paragraph with a hole. The paragraphs with the hole will be used for input.
1 (Patch the Image)
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, based on the information outside of that patch. And it does a
quite good job, considering it is just a program. As a human, you can sometimes
see that something is wrong, but if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.

In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, #############information outside of that patch. And it does a
quite good job, co#############is just a program. As a human, you can sometimes
see that something#############t if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.

2 (Gettysburg Address)
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here have thus far so nobly advanced. It
is rather for us to be here dedicated to the great task remaining before us-
that from these honored dead we take increased devotion to that cause for which
they gave the last full measure of devotion-that we here highly resolve that
these dead shall not have died in vain-that this nation, under God, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.

But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here h######################advanced. It
is rather for us to be here dedicated to the######################before us-
that from these honored dead we take increas######################use for which
they gave the last full measure of devotion-######################solve that
these dead shall not have died in vain-that ######################, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.

3 (Lorem Ipsum)
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit
in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt
mollit anim id est laborum.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conse################irure dolor in reprehenderit
in voluptate velit esse cil################giat nulla pariatur. Excepteur
sint occaecat cupidatat non################in culpa qui officia deserunt
mollit anim id est laborum.

4 (Jabberwocky)
'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.

'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe.

5 (Euclid's proof of the Pythagorean Theorem)
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are collinear. Similarly for B, A, and H.
6.Angles CBD and FBA are both right angles; therefore angle ABD
equals angle FBC, since both are the sum of a right angle and angle ABC.
7.Since AB is equal to FB and BD is equal to BC, triangle ABD
must be congruent to triangle FBC.
8.Since A-K-L is a straight line, parallel to BD, then rectangle
BDLK has twice the area of triangle ABD because they share the base
BD and have the same altitude BK, i.e., a line normal to their common
base, connecting the parallel lines BD and AL. (lemma 2)
9.Since C is collinear with A and G, square BAGF must be twice in area
to triangle FBC.
10.Therefore, rectangle BDLK must have the same area as square BAGF = AB^2.
11.Similarly, it can be shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.

1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are #############milarly for B, A, and H.
6.Angles C#############e both right angles; therefore angle ABD
equals ang############# both are the sum of a right angle and angle ABC.
7.Since AB#############FB and BD is equal to BC, triangle ABD
must be co#############iangle FBC.
8.Since A-#############ight line, parallel to BD, then rectangle
BDLK has t############# of triangle ABD because they share the base
BD and hav#############titude BK, i.e., a line normal to their common
base, conn#############rallel lines BD and AL. (lemma 2)
9.Since C #############with A and G, square BAGF must be twice in area
to triangl#############
10.Therefo############# BDLK must have the same area as square BAGF = AB^2.
11.Similar############# shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.

6 (Badger, Badger, Badger by weebl)
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger##################badger, badger,
badger##################badger, badger
Mushro##################
Badger##################badger, badger,
badger##################badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

may I assume the hole is at least three characters wide

@RohanJhunjhunwala Sure. Given the sizes of the text, that's a fairly safe assumption.

The gettysburg example apparently contains em dashes, which aren't plain ascii. Just pointing that out since you said in your comments in one of the answers that you'd use plain ascii test cases.

@SuperJedi224 Thanks - fixed.

Python 2
I know that @atlasologist already posted a solution in Python 2, but the way my works is a bit different. This works by going through all holes, from top to bottom, left to right, looking 5 characters back and at the character above, and finding a character where these matches. If multiple characters are found, it picks the most common one. In case there are no characters found, it removes the above-character restriction. If there are still no characters found, it decreases the amount of characters it looks back, and repeats.
def fix(paragraph, holeChar = "#"):
    lines = paragraph.split("\n")
    maxLineWidth = max(map(len, lines))
    lines = [list(line + " " * (maxLineWidth - len(line))) for line in lines]
    holes = filter(lambda pos: lines[pos[0]][pos[1]] == holeChar, [[y, x] for x in range(maxLineWidth) for y in range(len(lines))])

    n = 0
    for hole in holes:
        for i in range(min(hole[1], 5), 0, -1):
            currCh = lines[hole[0]][hole[1]]
            over = lines[hole[0] - 1][hole[1]]
            left = lines[hole[0]][hole[1] - i : hole[1]]

            same = []
            almost = []
            for y, line in enumerate(lines):
                for x, ch in enumerate(line):
                    if ch == holeChar:
                        continue
                    if ch == left[-1] == " ":
                        continue
                    chOver = lines[y - 1][x]
                    chLeft = lines[y][x - i : x]
                    if chOver == over and chLeft == left:
                        same.append(ch)
                    if chLeft == left:
                        almost.append(ch)
            sortFunc = lambda x, lst: lst.count(x) / (paragraph.count(x) + 10) + lst.count(x)
            if same:
                newCh = sorted(same, key=lambda x: sortFunc(x, same))[-1]
            elif almost:
                newCh = sorted(almost, key=lambda x: sortFunc(x, almost))[-1]
            else:
                continue
            lines[hole[0]][hole[1]] = newCh
            break

    return "\n".join(map("".join, lines))

Here's the result of Badger, Badger, Badger:
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a- b
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

Here's the result from the proof:
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are the same areamilarly for B, A, and H.
6.Angles CAB and CA, sqe both right angles; therefore angle ABD
equals angle ABD becaus both are the sum of a right angle and angle ABC.
7.Since ABD because theFB and BD is equal to BC, triangle ABD
must be construction ofiangle FBC.
8.Since A-angle ABD becight line, parallel to BD, then rectangle
BDLK has the same area  of triangle ABD because they share the base
BD and have the base thtitude BK, i.e., a line normal to their common
base, conngle and G, sqrallel lines BD and AL. (lemma 2)
9.Since C = BD × BK + with A and G, square BAGF must be twice in area
to triangle FBC. (lemma
10.Therefore angle and  BDLK must have the same area as square BAGF = AB^2.
11.Similarly for B, A,  shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.

And the result of Jabberwocky:
'Twas brillig, and the slithy toves
Did gyre and the mo in the wabe;
All mimsy toves, anborogoves,
And the mome raths outgrabe.

That Badger one is pretty impressive, and Jabberwocky looks like it could be the legit poem. Nice work.

Python 2
This is a pretty straight-forward solution. It creates a sample string composed of words that are between average word length A-(A/2) and A+(A/2), then it applies leading and trailing space trimmed chunks from the sample to the patch area. It doesn't handle capitalization, and I'm sure there's a curveball test case out there that would break it, but it does okay on the examples. See the link below to run all the tests.
I also put a patch in the code for good measure.
def patch(paragraph):
    sample = [x.split() for x in paragraph if x.count('#') < 1]
    length = max([x.count('#') for x in paragraph if x.find('#')])
    s = sum(####################
    sample,[####################
    ])      ####################
    avg=sum(####################
    len(w)  ####################
    for w in####################
    s)//len(s)
    avg_range = range(avg-(avg//2),avg+(avg//2))
    sample = filter(lambda x:len(x) in avg_range, s)
    height=0
    for line in paragraph:
        if line.find('#'):height+=1
        print line.replace('#'*length,' '.join(sample)[(height-1)*length:height*length].strip())
    print '\n'

Lorem Ipsum, original then patched:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit
in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt
mollit anim id est laborum.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conseore dolore magnairure dolor in reprehenderit
in voluptate velit esse cilenim minim quisgiat nulla pariatur. Excepteur
sint occaecat cupidatat nonnisi mollit aniin culpa qui officia deserunt
mollit anim id est laborum.

Try it

Hehe mushroger ...

Well, it doesn't patch your code in an interesting way.

@mbomb007 that's because of the other # characters in the code.

@atlasologist Even if you change them to something else like @, nothing interesting.

Java Shakespeare
Who needs a grasp of standard english conventions? Just make your own! Just like the bard was allowed to make up his own words. This bot doesn't worry to much about correcting the cut off words, he really just inserts random words. The result is some beautiful Poetry. As a bonus feature the bard is of a higher caliber and can handle multiple holes provided they are the same size!

Sample Input

 From fairest creatures we desire increase,
  That thereby beauty's rose might never die,
  But as the riper should by time decease,
  His tender############bear his memory:
  But thou c############ thine own bright eyes,
  Feed'st th############ame with self-substantial fuel,
  Making a famine where abundance lies,
  Thy self thy foe, to thy sweet self too cruel:
  Thou that art now the world's fresh ornament,
  And only herald to the gaudy spring,
  Within thine own bud buriest thy content,
  And tender churl mak'st was############ding:
    Pity the world, or else t############be,
    To eat the world's due, b############and thee.

                     2
  When forty winters shall besiege thy brow,
  And dig deep trenches in thy beauty's field,
  Thy youth's proud livery so gazed on now,
  Will be a tattered weed of small worth held:
  Then being asked, where all thy beauty lies,
  Where all the treasure of thy lusty days;
  To say within thine own deep sunken eyes,
  Were an all-eating shame, and thriftless praise.
  How much more praise deserved thy beauty's use,
  If thou couldst answer 'This fair child of mine
  Shall sum my count, and make my old excuse'
  Proving his beauty by succession thine.
    This were to be new made when thou art old,
    And see thy blood warm when thou feel'st it cold.

                     3
  Look in thy glass and tell the face thou viewest,
  Now is the time that face should form another,
  Whose fresh repair if now thou not renewest,
  Thou dost beguile the world, unbless some mother.
  For where is she so fair whose uneared womb
  Disdains the tillage of thy husbandry?
  Or who is he so fond will be the tomb,
  Of his self-love to stop posterity?
  Thou art thy mother's glass and she in thee
  Calls back the lovely April of her prime,
  So thou through windows of thine age shalt see,
  Despite of ############s thy golden time.
    But if th############mbered not to be,
    Die singl############image dies with thee.

Beautiful output

 From fairest creatures we desire increase,
  That thereby beauty's rose might never die,
  But as the riper should by time decease,
  His tender should of bear his memory:
  But thou c all mbered  thine own bright eyes,
  Feed'st th Proving Or ame with self-substantial fuel,
  Making a famine where abundance lies,
  Thy self thy foe, to thy sweet self too cruel:
  Thou that art now the world's fresh ornament,
  And only herald to the gaudy spring,
  Within thine own bud buriest thy content,
  And tender churl mak'st was he Thou my ding:
    Pity the world, or else t So the the be,
    To eat the world's due, b t thine so and thee.

                     2
  When forty winters shall besiege thy brow,
  And dig deep trenches in thy beauty's field,
  Thy youth's proud livery so gazed on now,
  Will be a tattered weed of small worth held:
  Then being asked, where all thy beauty lies,
  Where all the treasure of thy lusty days;
  To say within thine own deep sunken eyes,
  Were an all-eating shame, and thriftless praise.
  How much more praise deserved thy beauty's use,
  If thou couldst answer 'This fair child of mine
  Shall sum my count, and make my old excuse'
  Proving his beauty by succession thine.
    This were to be new made when thou art old,
    And see thy blood warm when thou feel'st it cold.

                     3
  Look in thy glass and tell the face thou viewest,
  Now is the time that face should form another,
  Whose fresh repair if now thou not renewest,
  Thou dost beguile the world, unbless some mother.
  For where is she so fair whose uneared womb
  Disdains the tillage of thy husbandry?
  Or who is he so fond will be the tomb,
  Of his self-love to stop posterity?
  Thou art thy mother's glass and she in thee
  Calls back the lovely April of her prime,
  So thou through windows of thine age shalt see,
  Despite of  Look gazed s thy golden time.
    But if th When be, mbered not to be,
    Die singl repair the image dies with thee.

The last couple lines are deeply poetic if I do say so myself.
It performs suprisingly well on the gettysburg address as well.
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here h to of rather us of advanced. It
is rather for us to be here dedicated to the who be it, vain who before us
that from these honored dead we take increas be dead the the what use for which
they gave the last full measure of devotion  dead government The solve that
these dead shall not have died in vain that  the take nor world , shall have
a new birth of freedom and that government of the people, by the people, for
the people, shall not perish from the earth.

Lets see what makes Shakespeare tick. Here is the code. Essentially he strives to build a vocabulary base from the input. He then uses these words and randomly places them in the hole (ensuring that it fits nicely). He is deterministic as he uses a fixed seed for randomness.

package stuff;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

/**
 *
 * @author rohan
 */
public class PatchTheParagraph {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("File Name :");
        String[] text = getWordsFromFile(in.nextLine());
System.out.println("==ORIGINAL==");
        for(String s:text){
    System.out.println(s);
}
                    int lengthOfHole= 0;
        int rows = 0;
            for(String s: text){
                s = s.replaceAll("[^#]", "");

//      System.out.println(s);
                if(s.length()>0){
                    lengthOfHole = s.length();
                rows++;
                }
            }
            ArrayList<String> words = new ArrayList<>();
            words.add("I");
            for(String s:text){
                String[] w = s.replaceAll("#", " ").split(" ");
for(String a :w){
    words.add(a);
            }

            }
                        Iterator<String> j = words.iterator();
            while(j.hasNext()){
                String o;
                if((o = j.next()).equals("")){
                    j.remove();
                }
            }
            System.out.println(words);
            Stack<String> out = new Stack<>();
            String hashRow = "";
            for(int i = 0;i<lengthOfHole;i++){
                hashRow+="#";
            }

        for(int i = 0;i<rows;i++){
            int length = lengthOfHole-1;
            String outPut = " ";
            while(length>2){
String wordAttempt = words.get(getRandom(words.size()-1));
while(wordAttempt.length()>length-1){
 wordAttempt = words.get(getRandom(words.size()-1));
}
length -= wordAttempt.length()+1;
            outPut+=wordAttempt;
                outPut+=" ";
            }
        out.push(outPut);
    }
System.out.println("==PATCHED==");
        for(String s : text){
            if(s.contains(hashRow)){
                System.out.println(s.replaceAll(hashRow,out.pop()));
            }else{
                System.out.println(s);
            }
        }
                                    }
public static final Random r = new Random(42);
    public static int getRandom(int max){
    return (int) (max*r.nextDouble());
}
    /**
     *
     * @param fileName is the path to the file or just the name if it is local
     * @return the number of lines in fileName
     */
    public static int getLengthOfFile(String fileName) {
        int length = 0;
        try {
            File textFile = new File(fileName);
            Scanner sc = new Scanner(textFile);
            while (sc.hasNextLine()) {
                sc.nextLine();
                length++;
            }
        } catch (Exception e) {
System.err.println(e);
        }
        return length;
    }

    /**
     *
     * @param fileName is the path to the file or just the name if it is local
     * @return an array of Strings where each string is one line from the file
     * fileName.
     */
    public static String[] getWordsFromFile(String fileName) {
        int lengthOfFile = getLengthOfFile(fileName);
        String[] wordBank = new String[lengthOfFile];
        int i = 0;
        try {
            File textFile = new File(fileName);
            Scanner sc = new Scanner(textFile);
            for (i = 0; i < lengthOfFile; i++) {
                wordBank[i] = sc.nextLine();
            }
            return wordBank;
        } catch (Exception e) {
            System.err.println(e);
            System.exit(55);
        }
        return null;
    }
}

Most of Shakespeare's poetry is public domain.

Comments are not for extended discussion; this conversation has been moved to chat.

Python 2.7
Another Python solution with a different approach. My program sees the text as a Markov chain, where each letter is followed by another letter with a certain probability. So the first step is to build the table of probabilities. The next step is to apply that probabilities to the patch.
Full code, including one sample text is below. Because one example used unicode characters, I included an explicit codepage (utf-8) for compatibility with that example.
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import numpy

texts = [
"""'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe."""
]

class Patcher:
    def __init__(self):
        self.mapper = defaultdict(lambda: defaultdict(int))

    def add_mapping(self, from_value, to_value):
        self.mapper[from_value][to_value] += 1

    def get_patch(self, from_value):
        if from_value in self.mapper:
            sum_freq = sum(self.mapper[from_value].values())
            return numpy.random.choice(
                self.mapper[from_value].keys(),
                p = numpy.array(
                    self.mapper[from_value].values(),dtype=numpy.float64) / sum_freq)
        else:
            return None

def add_text_mappings(text_string, patcher = Patcher(), ignore_characters = ''):
    previous_letter = text_string[0]
    for letter in text_string[1:]:
        if not letter in ignore_characters:
            patcher.add_mapping(previous_letter, letter)
            previous_letter = letter
    patcher.add_mapping(text_string[-1], '\n')

def patch_text(text_string, patcher, patch_characters = '#'):
    result = previous_letter = text_string[0]
    for letter in text_string[1:]:
        if letter in patch_characters:
            result += patcher.get_patch(previous_letter)
        else:
            result += letter
        previous_letter = result[-1]
    return result

def main():
    for text in texts:
        patcher = Patcher()
        add_text_mappings(text, patcher, '#')
        print patch_text(text, patcher, '#')
        print "\n"

if __name__ == '__main__':
    main()

Sample output for the Lorem Ipsum:
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conse Exe eut ccadamairure dolor in reprehenderit
in voluptate velit esse cilore indipserexepgiat nulla pariatur. Excepteur
sint occaecat cupidatat non upir alostat adin culpa qui officia deserunt
mollit anim id est laborum.

An extra poetic line in the Jabberwocky:
'Twas brillig, and the slithy toves
Did gyre and me the in the wabe;
All mimsy was
An inborogoves,
And the mome raths outgrabe.

Which example text has Unicode? They should all be straight ASCII. Please let me know, and I'll correct it.

Python complains about the mınxomaτ in the first text, refering to PEP 263.

Ah - didn't even realize. I've edited that to be straight ASCII. Thanks for letting me know!

C# 5 massive as ever
I threw this together, it's a bit of a mess, but it produces some OK results some of the time. It a mostly-deterministic algorithm, but with some (fixed-seed) randomness added to avoid it producing the same string for similar gaps. It goes to some effort to try to avoid just having columns of spaces either side of the gaps.
It works by tokenizing the input into words and punctuation (punctuation comes from a manually entered list, because I can't be bothered to work out if Unicode can do this for me), so that it can put spaces before words, and not before punctuation, because this is fairly typical. It splits on typical whitespace. In the vein of markov chains (I think), it counts how often each token follows each other token, and then doesn't compute probabilities for this (I figure that because the documents are so tiny, we would do better to bias toward things we see a lot where we can). Then we perform a breadth-first search, filling the space left by the hashes and the 'partial' words either side, with the cost being computed as -fabness(last, cur) * len(cur_with_space), where fabness returns the number of times cur has followed last for each appended token in the generated string. Naturally, we try to minimise the cost. Because we can't always fill the gap with words and punctuation found in the document, it also considers a number of 'special' tokens from certain states, including the partial strings on either side, which we bias against with arbitrarily increased costs.
If the BFS fails to find a solution, then we naively try to pick a random adverb, or just insert spaces to fill the space.
Results
All 6 can be found here: https://gist.github.com/anonymous/5277db726d3f9bdd950b173b19fec82a
The Euclid test-case did not go very well...
Patch the Image
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, that patches information outside of that patch. And it does a
quite good job, co the patch a is just a program. As a human, you can sometimes
see that something In a short it if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.

Jabberwocky
'Twas brillig, and the slithy toves
Did gyre and the in in the wabe;
All mimsy the mome borogoves,
And the mome raths outgrabe.

Badger
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, badger, badger
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!

_I'm glad with how this one turned out... it's fortuate that "badger, badger," fits, or this one would not have done so well
Code
Run it with
csc ParaPatch.cs
ParaPatch.exe infile outfile

There is quite a lot of it. The only remotely interesting bit is the Fill method. I include the heap implementation, because .NET doesn't have one (WHY MS WHY?!).
using System;
using System.Collections.Generic;
using System.Linq;

namespace ParaPatch
{
    class Program
    {
        private static string[] Filler = new string[] { "may", "will", "maybe", "rather", "perhaps", "reliably", "nineword?", "definitely", "elevenword?", "inexplicably" }; // adverbs
        private static char[] Breaking = new char[] { ' ', '\n', '\r', '\t' };
        private static char[] Punctuation = new char[] { ',', '.', '{', '}', '(', ')', '/', '?', ':', ';', '\'', '\\', '"', ',', '!', '-', '+', '[', ']', '£', '$', '%', '^', '—' };

        private static IEnumerable<string> TokenizeStream(System.IO.StreamReader reader)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();

            HashSet<char> breaking = new HashSet<char>(Breaking);
            HashSet<char> punctuation = new HashSet<char>(Punctuation);

            while (!reader.EndOfStream)
            {
                int ci = reader.Read();
                if (ci == -1) // sanity
                    break;

                char c = (char)ci;

                if (breaking.Contains(c))
                {
                    if (sb.Length > 0)
                        yield return sb.ToString();
                    sb.Clear();
                }
                else if (punctuation.Contains(c))
                {
                    if (sb.Length > 0)
                        yield return sb.ToString();
                    yield return ""+c;
                    sb.Clear();
                }
                else
                {

                    sb.Append(c);
                }
            }

            if (sb.Length > 0)
                yield return sb.ToString();
        }

        private enum DocTokenTypes
        {
            Known,
            LeftPartial,
            RightPartial,
            Unknown,
        }

        private class DocToken
        {
            public DocTokenTypes TokenType { get; private set; }
            public string StringPart { get; private set; }
            public int Length { get; private set; }

            public DocToken(DocTokenTypes tokenType, string stringPart, int length)
            {
                TokenType = tokenType;
                StringPart = stringPart;
                Length = length;
            }
        }

        private static IEnumerable<DocToken> DocumentTokens(IEnumerable<string> tokens)
        {
            foreach (string token in tokens)
            {
                if (token.Contains("#"))
                {
                    int l = token.IndexOf("#");
                    int r = token.LastIndexOf("#");

                    if (l > 0)
                        yield return new DocToken(DocTokenTypes.LeftPartial, token.Substring(0, l), l);

                    yield return new DocToken(DocTokenTypes.Unknown, null, r - l + 1);

                    if (r < token.Length - 1)
                        yield return new DocToken(DocTokenTypes.RightPartial, token.Substring(r + 1), token.Length - r - 1);
                }
                else
                    yield return new DocToken(DocTokenTypes.Known, token, token.Length);
            }
        }

        private class State : IComparable<State>
        {
            // missing readonly params already... maybe C#6 isn't so bad
            public int Remaining { get; private set; }
            public int Position { get; private set; }
            public State Prev { get; private set; }
            public string Token { get; private set; }
            public double H { get; private set; }
            public double Fabness { get; private set; }
            public string FullFilling { get; private set; }

            public State(int remaining, int position, Program.State prev, double fabness, double h, string token, string toAdd)
            {
                Remaining = remaining;
                Position = position;
                Prev = prev;
                H = h;
                Fabness = fabness;
                Token = token;

                FullFilling = prev != null ? prev.FullFilling + toAdd : toAdd;
            }

            public int CompareTo(State other)
            {
                return H.CompareTo(other.H);
            }
        }

        public static void Main(string[] args)
        {
            if (args.Length < 2)
                args = new string[] { "test.txt", "testout.txt" };

            List<DocToken> document;
            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0], System.Text.Encoding.UTF8))
            {
                document = DocumentTokens(TokenizeStream(reader)).ToList();
            }

            foreach (DocToken cur in document)
            {
                Console.WriteLine(cur.StringPart + " " + cur.TokenType);
            }

            // these are small docs, don't bother with more than 1 ply
            Dictionary<string, Dictionary<string, int>> FollowCounts = new Dictionary<string, Dictionary<string, int>>();
            Dictionary<string, Dictionary<string, int>> PreceedCounts = new Dictionary<string, Dictionary<string, int>>(); // mirror (might be useful)

            HashSet<string> knowns = new HashSet<string>(); // useful to have lying around

            // build counts
            DocToken last = null;
            foreach (DocToken cur in document)
            {
                if (cur.TokenType == DocTokenTypes.Known)
                {
                    knowns.Add(cur.StringPart);
                }

                if (last != null && last.TokenType == DocTokenTypes.Known && cur.TokenType == DocTokenTypes.Known)
                {
                    {
                        Dictionary<string, int> ltable;
                        if (!FollowCounts.TryGetValue(last.StringPart, out ltable))
                        {
                            FollowCounts.Add(last.StringPart, ltable = new Dictionary<string, int>());
                        }

                        int count;
                        if (!ltable.TryGetValue(cur.StringPart, out count))
                        {
                            count = 0;
                        }
                        ltable[cur.StringPart] = count + 1;
                    }

                    {
                        Dictionary<string, int> ctable;
                        if (!PreceedCounts.TryGetValue(cur.StringPart, out ctable))
                        {
                            PreceedCounts.Add(cur.StringPart, ctable = new Dictionary<string, int>());
                        }

                        int count;
                        if (!ctable.TryGetValue(last.StringPart, out count))
                        {
                            count = 0;
                        }
                        ctable[last.StringPart] = count + 1;
                    }
                }

                last = cur;
            }

            // build probability grid (none of this efficient table filling dynamic programming nonsense, A* all the way!)
            // hmm... can't be bothered
            Dictionary<string, Dictionary<string, double>> fabTable = new Dictionary<string, Dictionary<string, double>>();
            foreach (var k in FollowCounts)
            {
                Dictionary<string, double> t = new Dictionary<string, double>();

                // very naive
                foreach (var k2 in k.Value)
                {
                    t.Add(k2.Key, (double)k2.Value);
                }

                fabTable.Add(k.Key, t);
            }

            string[] knarr = knowns.ToArray();
            Random rnd = new Random("ParaPatch".GetHashCode());

            List<string> fillings = new List<string>();
            for (int i = 0; i < document.Count; i++)
            {
                if (document[i].TokenType == DocTokenTypes.Unknown)
                {
                    // shuffle knarr
                    for (int j = 0; j < knarr.Length; j++)
                    {
                        string t = knarr[j];
                        int o = rnd.Next(knarr.Length);
                        knarr[j] = knarr[o];
                        knarr[o] = t;
                    }

                    fillings.Add(Fill(document, fabTable, knarr, i));
                    Console.WriteLine(fillings.Last());
                }
            }

            string filling = string.Join("", fillings);

            int fi = 0;

            using (System.IO.StreamWriter writer = new System.IO.StreamWriter(args[1]))
            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0]))
            {
                while (!reader.EndOfStream)
                {
                    int ci = reader.Read();
                    if (ci == -1)
                        break;

                    char c = (char)ci;
                    c = c == '#' ? filling[fi++] : c;

                    writer.Write(c);
                    Console.Write(c);
                }
            }

//            using (System.IO.StreamWriter writer = new System.IO.StreamWriter(args[1], false, System.Text.Encoding.UTF8))
//            using (System.IO.StreamReader reader = new System.IO.StreamReader(args[0]))
//            {
//                foreach (char cc in reader.ReadToEnd())
//                {
//                    char c = cc;
//                    c = c == '#' ? filling[fi++] : c;
//
//                    writer.Write(c);
//                    Console.Write(c);
//                }
//            }

            if (args[0] == "test.txt")
                Console.ReadKey(true);
        }

        private static string Fill(List<DocToken> document, Dictionary<string, Dictionary<string, double>> fabTable, string[] knowns, int unknownIndex)
        {
            HashSet<char> breaking = new HashSet<char>(Breaking);
            HashSet<char> punctuation = new HashSet<char>(Punctuation);

            Heap<State> due = new Heap<Program.State>(knowns.Length);

            Func<string, string, double> fabness = (prev, next) =>
            {
                Dictionary<string, double> table;
                if (!fabTable.TryGetValue(prev, out table))
                    return 0; // not fab
                double fab;
                if (!table.TryGetValue(next, out fab))
                    return 0; // not fab
                return fab; // yes fab
            };

            DocToken mostLeft = unknownIndex > 2 ? document[unknownIndex - 2] : null;
            DocToken left = unknownIndex > 1 ? document[unknownIndex - 1] : null;
            DocToken unknown = document[unknownIndex];
            DocToken right = unknownIndex < document.Count - 2 ? document[unknownIndex + 1] : null;
            DocToken mostRight = unknownIndex < document.Count - 3 ? document[unknownIndex + 2] : null;

            // sum of empty space and partials' lengths
            int spaceSize = document[unknownIndex].Length
                + (left != null && left.TokenType == DocTokenTypes.LeftPartial ? left.Length : 0)
                + (right != null && right.TokenType == DocTokenTypes.RightPartial ? right.Length : 0);

            int l = left != null && left.TokenType == DocTokenTypes.LeftPartial ? left.Length : 0;
            int r = l + unknown.Length;

            string defaultPrev =
                left != null && left.TokenType == DocTokenTypes.Known ? left.StringPart :
                mostLeft != null && mostLeft.TokenType == DocTokenTypes.Known ? mostLeft.StringPart :
                "";

            string defaultLast =
                right != null && right.TokenType == DocTokenTypes.Known ? right.StringPart :
                mostRight != null && mostRight.TokenType == DocTokenTypes.Known ? mostRight.StringPart :
                "";

            Func<string, string> topAndTail = str =>
            {
                return str.Substring(l, r - l);
            };

            Func<State, string, double, bool> tryMove = (State prev, string token, double specialFabness) =>
            {
                bool isPunctionuation = token.Length == 1 && punctuation.Contains(token[0]);
                string addStr = isPunctionuation || prev == null ? token : " " + token;
                int addLen = addStr.Length;

                int newRemaining = prev != null ? prev.Remaining - addLen : spaceSize - addLen;
                int oldPosition = prev != null ? prev.Position : 0;
                int newPosition = oldPosition + addLen;

                // check length
                if (newRemaining < 0)
                    return false;

                // check start
                if (oldPosition < l) // implies left is LeftPartial
                {
                    int s = oldPosition;
                    int e = newPosition > l ? l : newPosition;
                    int len = e - s;
                    if (addStr.Substring(0, len) != left.StringPart.Substring(s, len))
                        return false; // doesn't match LeftPartial
                }

                // check end
                if (newPosition > r) // implies right is RightPartial
                {
                    int s = oldPosition > r ? oldPosition : r;
                    int e = newPosition;
                    int len = e - s;
                    if (addStr.Substring(s - oldPosition, len) != right.StringPart.Substring(s - r, len))
                        return false; // doesn't match RightPartial
                }

                if (newRemaining == 0)
                {
                    // could try to do something here (need to change H)
                }

                string prevToken = prev != null ? prev.Token : defaultPrev;
                bool isLastunctionuation = prevToken.Length == 1 && punctuation.Contains(prevToken[0]);

                if (isLastunctionuation && isPunctionuation) // I hate this check, it's too aggresive to be realistic
                    specialFabness -= 50;

                double fab = fabness(prevToken, token);

                if (fab < 1 && (token == prevToken))
                    fab = -1; // bias against unrecognised repeats

                double newFabness = (prev != null ? prev.Fabness : 0.0)
                    - specialFabness // ... whatever this is
                    - fab * addLen; // how probabilistic

                double h = newFabness; // no h for now

                State newState = new Program.State(newRemaining, newPosition, prev, newFabness, h, token, addStr);

//                Console.WriteLine((prev != null ? prev.Fabness : 0) + "\t" + specialFabness);
//                Console.WriteLine(newFabness + "\t" + h + "\t" + due.Count + "\t" + fab + "*" + addLen + "\t" + newState.FullFilling);

                due.Add(newState);
                return true;
            };

            // just try everything everything
            foreach (string t in knowns)
                tryMove(null, t, 0);

            if (left != null && left.TokenType == DocTokenTypes.LeftPartial)
                tryMove(null, left.StringPart, -1);

            while (!due.Empty)
            {
                State next = due.RemoveMin();

                if (next.Remaining == 0)
                {
                    // we have a winner!!
                    return topAndTail(next.FullFilling);
                }

                // just try everything
                foreach (string t in knowns)
                    tryMove(next, t, 0);
                if (right != null && right.TokenType == DocTokenTypes.RightPartial)
                    tryMove(next, right.StringPart, -5); // big bias
            }

            // make this a tad less stupid, non?
            return Filler.FirstOrDefault(f => f.Length == unknown.Length) ?? new String(' ', unknown.Length); // oh dear...
        }
    }

    //
    // Ultilities
    //

    public class Heap<T> : System.Collections.IEnumerable where T : IComparable<T>
    {
        // arr is treated as offset by 1, all idxes stored need to be -1'd to get index in arr
        private T[] arr;
        private int end = 0;

        private void s(int idx, T val)
        {
            arr[idx - 1] = val;
        }

        private T g(int idx)
        {
            return arr[idx - 1];
        }

        public Heap(int isize)
        {
            if (isize < 1)
                throw new ArgumentException("Cannot be less than 1", "isize");

            arr = new T[isize];
        }

        private int up(int idx)
        {
            return idx / 2;
        }

        private int downLeft(int idx)
        {
            return idx * 2;
        }

        private int downRight(int idx)
        {
            return idx * 2 + 1;
        }

        private void swap(int a, int b)
        {
            T t = g(a);
            s(a, g(b));
            s(b, t);
        }

        private void moveUp(int idx, T t)
        {
        again:
            if (idx == 1)
            {
                s(1, t);
                return; // at end
            }

            int nextUp = up(idx);
            T n = g(nextUp);
            if (n.CompareTo(t) > 0)
            {
                s(idx, n);
                idx = nextUp;
                goto again;
            }
            else
            {
                s(idx, t);
            }
        }

        private void moveDown(int idx, T t)
        {
        again:
            int nextLeft = downLeft(idx);
            int nextRight = downRight(idx);

            if (nextLeft > end)
            {
                s(idx, t);
                return; // at end
            }
            else if (nextLeft == end)
            { // only need to check left
                T l = g(nextLeft);

                if (l.CompareTo(t) < 0)
                {
                    s(idx, l);
                    idx = nextLeft;
                    goto again;
                }
                else
                {
                    s(idx, t);
                }
            }
            else
            { // check both
                T l = g(nextLeft);
                T r = g(nextRight);

                if (l.CompareTo(r) < 0)
                { // left smaller (favour going right if we can)
                    if (l.CompareTo(t) < 0)
                    {
                        s(idx, l);
                        idx = nextLeft;
                        goto again;
                    }
                    else
                    {
                        s(idx, t);
                    }
                }
                else
                { // right smaller or same
                    if (r.CompareTo(t) < 0)
                    {
                        s(idx, r);
                        idx = nextRight;
                        goto again;
                    }
                    else
                    {
                        s(idx, t);
                    }
                }
            }
        }

        public void Clear()
        {
            end = 0;
        }

        public void Trim()
        {
            if (end == 0)
                arr = new T[1]; // don't /ever/ make arr len 0
            else
            {
                T[] narr = new T[end];
                for (int i = 0; i < end; i++)
                    narr[i] = arr[i];
                arr = narr;
            }
        }

        private void doubleSize()
        {
            T[] narr = new T[arr.Length * 2];
            for (int i = 0; i < end; i++)
                narr[i] = arr[i];
            arr = narr;
        }

        public void Add(T item)
        {
            if (end == arr.Length)
            {
                // resize
                doubleSize();
            }

            end++;
            moveUp(end, item);
        }

        public T RemoveMin()
        {
            if (end < 1)
                throw new Exception("No items, mate.");

            T min = g(1);

            end--;
            if (end > 0)
                moveDown(1, g(end + 1));

            return min;
        }

        public bool Empty
        {
            get
            {
                return end == 0;
            }
        }

        public int Count
        {
            get
            {
                return end;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<T> GetEnumerator()
        {
            return (IEnumerator<T>)arr.GetEnumerator();
        }
    }
}


text:
Algebraic curve plotter
An algebraic curve is a certain "1D subset" of the "2D-plane" that can be described as set of zeros {(x,y) in R^2 : f(x,y)=0 }of a polynomial f. Here we consider the 2D-plane as the real plane R^2 such that we can easily imagine what such a curve could look like, basically a thing you can draw with a pencil.
Examples:

0 = x^2 + y^2 -1  a circle of radius 1
0 = x^2 + 2y^2 -1  an ellipse
0 = xy  a cross shape, basically the union of the x-axis and the y-axis
0 = y^2 - x  a parabola
0 = y^2 - (x^3 - x + 1) an elliptic curve
0 = x^3 + y^3 - 3xy the folium of Descartes
0 = x^4 - (x^2 - y^2) a lemniscate
0 = (x^2 + y^2)^2 - (x^3 - 3xy^2) a trifolium
0 = (x^2 + y^2 - 1)^3 + 27x^2y^2 an astroid

Task
Given a polynomial f (as defined below), and the x/y-ranges, output an black and white image of at least 100x100 pixels that shows the curve as black line on a white background.
Details
Color: You can use any two other colours of your choice, it should just be easy to tell them apart.
Plot: Instead of a pixel image you can also output this image as ascii-art, where the background "pixels" should be space/underline or an other character that "looks empty" and the line can be made of a character that looks "full" like M or X or #.
You do not have to worry about aliasing.
You only need to plot lines where the sign of the polynomial changes from one side of the line to the other (that means you could e.g. use the marching square algorithm), you do not have to correctly plot "pathological cases like 0 = x^2 where the sign does not change when going from one side of the line to the other. But the line should be continuous and separating the regions of the different signs of f(x,y).
Polynomial: The polynomial is given as a (m+1) x (n+1) matrix/list of lists of (real) coefficients, in the example below the terms of the coefficients are given in their position:
[   1 * 1,   1 * x,   1 * x^2,   1 * x^3,  ... , 1 * x^n ]
[   y * 1,   y * x,   y * x^2,   y * x^4,  ... , y * x^n ]
[   ...  ,   ...   ,   ...   ,    ...   ,  ... ,   ...   ]
[ y^m * 1, y^m * x, y^m * x^2, y^m * x^3 , ..., y^m * x^n]

If you prefer, you can assume the matrix to be square (which can always be done with the necessary zero-padding), and if you want, you can also assume that the size of the matrix is given as aditional inputs.
In the following, the examples from above are represented as a matrix defined like this:
Circle:       Ellipse:      Parabola:  Cross:    Elliptic Curve: e.t.c
[-1, 0, 1]    [-1, 0, 1]    [ 0,-1]    [ 0, 0]   [-1, 1, 0,-1]
[ 0, 0, 0]    [ 0, 0, 0]    [ 0, 0]    [ 0, 1]   [ 0, 0, 0, 0]
[ 1, 0, 0]    [ 2, 0, 0]    [ 1, 0]              [ 1, 0, 0, 0]

Test cases with x-range / y-range:
(In a not so readable but better copy-paste-able format available here on pastebin.)
Circle:
[-1, 0, 1]   [-2,2]   [-2,2]
[ 0, 0, 0]
[ 1, 0, 0]

Ellipse:
[-1, 0, 1]   [-2,2]   [-1,1]
[ 0, 0, 0]
[ 2, 0, 0]

Cross:
[ 0, 0]      [-1,2]   [-2,1]
[ 0, 1]

Parabola:
[ 0,-1]      [-1,3]   [-2,2]
[ 0, 0]
[ 1, 0]

Elliptic Curve:
[-1, 1, 0,-1]    [-2,2]   [-3,3]
[ 0, 0, 0, 0]
[ 1, 0, 0, 0]

Folium of Descartes:
[  0,  0,  0,  1]    [-3,3]   [-3,3]
[  0, -3,  0,  0]
[  0,  0,  0,  0]
[  1,  0,  0,  0]

Lemniscate:
[  0,  0, -1,  0,  1]    [-2,2]   [-1,1]
[  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0]

Trifolium:
[ 0, 0, 0,-1, 1]    [-1,1]   [-1,1]
[ 0, 0, 0, 0, 0]
[ 0, 3, 2, 0, 0]
[ 0, 0, 0, 0, 0]
[ 1, 0, 0, 0, 0]

Astroid:
[ -1,  0,  3,  0, -3,  0,  1]    [-1,1]   [-1,1]
[  0,  0,  0,  0,  0,  0,  0]
[  3,  0, 21,  0,  3,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[ -3,  0,  3,  0,  0,  0,  0]
[  0,  0,  0,  0,  0,  0,  0]
[  1,  0,  0,  0,  0,  0,  0]

I've got the inspiration for some curves from this pdf.

Does "You do not have to worry about aliasing" mean that we can just colour each pixel according to whether its centre lies on the line?

I don't see the connection to aliasing. But no, there should be a continuous line separating the regions of different signs.

The matrix is not mxn,  but (m+1)x(n+1). What do we take as input: m, n, or m+1,n+1? Or can we choose?

Can we just show the graphed function in a new window?

@R.Kap Yes, sure!

@LuisMendo Thanks. It doesn't really matter whether you take m-1,m or m+1, or as unary or whatever.

Can we choose axis orientation? Like showing the figures flipped

@LuisMendo Yes, the axis can be in any direction you like. (As long they are orthogonal=)

Why’s this tagged [tag:abstract-algebra]?

@Lynn Algebraic curves are studied in algebraic geometry which is part of abstract algebra.

Haskell, 283 275 bytes
The function g should be called with the matrix and the two ranges as arguments. The matrix is just a list of lists, the ranges each a two element list.
import Data.List
t=transpose
u=tail
z=zipWith
l%x=sum$z(*)l$iterate(*x)1                                   --generate powers and multiply with coefficients
e m y x=[l%x|l<-m]%y                                         --evaluate the encoded polynomial
a#b=[a,a+(b-a)/102..b]                                       --create a range
g m[u,w][i,j]=unlines$v[map((0<).e m y)$u#w|y<-i#j]          --evaluate the function on the grid, get the sign
f g=u[u$u$map fst$scanl(\(r,l)c->(c==l,c))(1<0,1<0) l|l<-g]  --find +- or -+ transitions within lines
a&b|a&&b=' '|0<1='#'                                         --helper function for creating the string
v g=z(z(&))(f g)(t$f$t g)                                    --create the string

Here the outputs for the more interesting cases: Note that I had to downsize the resultion from 100x100 to about 40x40 such that it sill fits in the console (just change the hardcoded 102 to a smaller number). Also note that the y-axis is pointing downwards.

There are a couple of pretty small golfs you can make here.  The last line uses parens when it could use $ to save a byte.  Both places where you use map could be (<$>), and since you only use e once you can pull the (0<) inside it's definition.  Also e could be named (!) to save 3 bytes.

And infixing z in the definition of v allows you to get rid of 4 parentheses (around z(&) and f g).

You could also rename # to a single character (e.g. s) and have it pattern match on the lists instead of g. (e.g. s[a,b]=[a,a+(b-a)/102..b];g m u i=unlines$v[m!y<$>s u|y<-s i])

Matlab, 114 100 92 bytes
The right tool for the job? I use the interesting way Matlab does printf to generate a polynomial as a string. This polynomial can be provided to ezplot which plots the implicit curve on the specified domain. For readability the code is presented with newlines after ; which isn't needed and isn't counted towards the size.
function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

Golfing progress as expandable snippet.

Iteration 1, clean arguments, 114 bytes
---------------------------------------
function P(A,W,H)
h=size(A,1);
t=0:numel(A)-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])

Iteration 1.5, historical revisionism (thanks @flawr), 111 bytes
--------------------------------------------------------------
function P(A,W,H)
[h,w]=size(A);
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H])

Iteration 2, playing dirty, 100 bytes
-------------------------------------
The code can be golfed further if I use that taking matrix sizes as inputs are
fair game, but it feels sad to ruin such neat input arguments. However,
this is code golf and I'll abuse anything I can and I end up at a nice 100 bytes:

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';floor(t/h);rem(t,h)]),[W,H]);

Iteration 2.5, fix your code (thanks @LuisMendo), 98 bytes
----------------------------------------------------------
function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%d*y^%d',[A(:)';fix(t/h);rem(t,h)]),[W,H]);

Iteration 3, more power to printf, 92 bytes [current best]
----------------------------------------------------------
Use `%.0f` instead of `fix`/`floor`.

function P(A,W,H,h,w)
t=0:h*w-1;
ezplot(sprintf('+%d*x^%.0f*y^%d',[A(:)';t/h;rem(t,h)]),[W,H])

Output of the test cases (click for full view):

Really nice solution using sprintf/ezplot!

Using fix instead of floor might help you reach the two-digit byte count :-)

You could also use [h,w]=size(A);t=0:h*w-1; to save another three bytes!

@LuisMendo Actually, I can do better. I was sad that Matlab's printf doesn't have a integer placeholder, but it still supports things like %.0f. That means I can drop flooring altogether and let printf fix it!

@flawr I do use the second part of that in later iterations. I realize my formatting with the best version last wasn't perfectly obvious. Edited formatting to make this crystal clear.

I think you don't necessarily have to show the whole history, but I'd post the shortest one on top :D

@flawr What about now? Looks ok?

Python 2, 261 bytes
E=enumerate
M,[a,c],[b,d]=input()
e=(c-a)/199.
I=200
J=-int((b-d)/e-1)
print'P2',I,J,255
i=I*J
while i:i-=1;x,y=c-i%I*e,b+i/I*e;u,v,w=map(sum,zip(*((z*p/x,z*q/y,z)for q,R in E(M)for p,t in E(R)for z in[t*x**p*y**q])));print int(255*min(1,(w*w/(u*u+v*v))**.5/e))

Input format: matrix,xbounds,ybounds (e.g. [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]).  Output format: plain PGM.
This estimates the distance from every pixel center to the curve using the first-order approximation d(x, y) = |p(x, y)| / |∇p(x, y)|, where ∇p is the gradient of the polynomial p. (This is the distance from (x, y) to the intersection of the tangent plane at (x, y, p(x, y)) with the xy–plane.) Then the pixels where d(x, y) is less than one pixel width of the curve proportionally to d(x, y), resulting in nice antialiased lines (even though that isn’t a requirement).

Here are the same graphs with the distance function divided by 16 to make it visible.

Wait, so where in the code does the actual graphical plotting happen?

@R.Kap The code writes an image in plain PGM format to stdout. There’s one print statement for the image header and one print statement in the while loop for the value of each pixel.

Wow, that is really cool! Would you mind going a little bit more in depth about your plotting algorithm?

@flawr I’ve expanded the explanation a bit; does that answer your questions?

@AndersKaseorg Yes, thank you very much!

Python 3.5 + MatPlotLib + Numpy, 352 bytes:
from matplotlib.pyplot import*;from numpy import*
def R(M,S,U,r=range):N=linspace;E='+'.join([str(y)+'*'+m for y,m in[q for i,g in zip(M,[[i+'*'+p for p in['1']+['x^%d'%p for p in r(1,len(M[0]))]]for i in['1']+['y^%d'%i for i in r(1,len(M))]])for q in zip(i,g)if q[0]]]);x,y=meshgrid(N(*S,200),N(*U,200));contour(x,y,eval(E.replace('^','**')),0);show()

A named function. Pretty long, but hey, I'm just happy I was able to accomplish the task. Takes 3 inputs, which are the m by n matrix, the x-range, and y-range, which should all be in arrays (for example, [[-1,0,1],[0,0,0],[1,0,0]],[-2,2],[-2,2]). Outputs the completed graph in a new, graphical, interactive window. Will golf this down more of time when I can, but for now, I'm happy with it.
Final Outputs for the Test Cases:

MATL, 67 61 bytes
8Wt:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4=0YG

This code runs in release 18.5.0 of the language, which precedes the challenge. Input uses the optional m, n parameters. The matrix has semicolons as row separators. The exact input format (using the parabola as an example) is
[-1,3]
3
[-2,2]
2
[0,-1; 0, 0; 1, 0]

The code produces an image with size 255×255. This can be tested using @Suever's MATL Online compiler, which, among other very interesting features, includes graphical output. See for example

Elliptic curve;
Folium of Descartes.

This compiler is still in an experimental stage. Please report any issues to @Suever in the MATL chatroom. If the "Run" button doesn't work, try refreshing the page and clicking again.
If you prefer ASCII output, the code needs to be modified a little (the changes only affect the first two and last four characters of the code above):
101t:qwq/t2:"wid*2M1)+i:q!^]!2&!w[1IK2]&!**ss&eZS5Y62&Y+|4<42*c

This produces a 100×100 ASCII grid which uses character * to represent the curve. You can also test this with @Dennis' Try it online! platform:

Elliptic curve;
Folium of Descartes.

Note that the aspect ratio of ASCII output is altered because the characters are slightly higher than are wide.
Explanation
The code first computes the two-variable polynomial on an x-y grid. This makes heavy use of broadcasting, computing an intermediate 4D array where each dimension represents x values, y values, x exponents, y exponents respectively.
From that function, the zero level line is computed. Since the challenge specifes that only sign changes need to be detected, the code applies 2D convolution with a 2×2 block of ones, and marks a pixel as belonging to the line if not the four values of the block have the same sign.
8W      % Push 2^8, that is, 256. (The ASCII-output version pushes 101 instead)
t:q     % Duplicate. Push range [0 1 ... 255]
wq      % Swap. Subtract 1 to obtain 255
/       % Divide. Gives normalized range [0 1/255 2/255... 1]
t       % Duplicate
2:"     % For loop: do this twice
  w     %   Swap top two elements in the stack
  i     %   Input two-number array defining x range (resp. y in second iteration)
  d     %   Difference of the two entries
  *     %   Multiply by normalized range
  2M1)  %   Push the array again and get its first entry
  +     %   Add. This gives the range for x values (resp. y)
  i     %   Input m (n in second iteration)
  :q    %   Range [0 1 ...m-1] (resp. [0 1 ...n-1])
  !     %   Convert to column array
  ^     %   Power, element-wise with broadcast. This gives a matrix of size m×256
        %   (resp. n×256) of powers of x (resp. y) for the range of values computed
        %   previously
]       % End for loop
!       % Transpose. This transforms the n×256 matrix of powers of y into 256×n
2       % Push 2
&!      % Permute dimensions 1 and 3: transforms the 256×n matrix into a 4D array
        % of size 1×n×256×1
w       % Swap top two elements in the stack: bring 256×m matrix to top
[1IK2]  % Push vector [1 3 4 2]
&!      % Permute dimensions as indicated by the vector: transforms the m×256 matrix
        % into a 4D array of size m×1×1×256
*       % Multiply element-wise with broadcast: gives 4D array of size m×n×256×256
        % with mixed powers of x and y for at the grid of x, y values
*       % Implicitly input m×n matrix. Multiply element-wise with broadcast: gives
        % 4D array of size m×n×256×256
ss      % Sum along first two dimensions: gives 4D array of size 1×1×256×256
&e      % Squeeze singleton dimensions: gives matrix of size 256×256. This is the
        % two-variable polynomial evaluated at the x, y grid.
        % Now we need to find the zero level curve of this function. We do this by
        % detecting when the sign of the function changes along any of the two axes
ZS      % Matrix of sign values (1, 0 or -1)
5Y6     % Predefined literal: matrix [1 1; 1 1]
2&Y+    % Compute 2D convolution, keeping only the valid (central) part
|4=     % True if absolute value of result is 4, which indicates no sign changes.
        % (The ASCII version computes a negated version of this, for better display)
0YG     % Display as image. (The ASCII-output version does the following instead:
        % multiply by 42 and convert to char. 42 is ASCII for '*', and character 0
        % is shown as space. The 2D char array is then implicitly displayed)

All test cases
Here are all inputs in the appropriate format, in case you want to try:
Circle:
[-2,2]
3
[-2,2]
3
[-1, 0, 1; 0, 0, 0; 1, 0, 0]

Ellipse:
[-2,2]
3
[-1,1]
3
[-1, 0, 1; 0, 0, 0; 2, 0, 0]

Cross:
[-1,2]
2
[-2,1]
2
[0, 0; 0, 1]

Parabola:
[-1,3]
3
[-2,2]
2
[0,-1; 0, 0; 1, 0]

Elliptic Curve:
[-2,2]
3
[-3,3]
4
[-1, 1, 0,-1; 0, 0, 0, 0; 1, 0, 0, 0]

Folium of Descartes:
[-3,3]
4
[-3,3]
4
[0,  0,  0,  1; 0, -3,  0,  0; 0,  0,  0,  0; 1,  0,  0,  0]

Lemniscate:
[-2,2]
3
[-1,1]
5
[0,  0, -1,  0,  1; 0,  0,  0,  0,  0; 1,  0,  0,  0,  0]

Trifolium:
[-1,1]
5
[-1,1]
5
[0, 0, 0,-1, 1; 0, 0, 0, 0, 0; 0, 3, 2, 0, 0; 0, 0, 0, 0, 0; 1, 0, 0, 0, 0]

Astroid
[-1,1]
7
[-1,1]
7
[-1,  0,  3,  0, -3,  0,  1; 0,  0,  0,  0,  0,  0,  0; 3,  0, 21,  0,  3,  0,  0; 0,  0,  0,  0,  0,  0,  0; -3,  0,  3,  0,  0,  0,  0; 0,  0,  0,  0,  0,  0,  0; 1,  0,  0,  0,  0,  0,  0]

Still more readable than Perl. Great job, also a nice online compiler!

@flawr more readable than Perl LOL. As for the online compiler, it's all Suever's work!

@flawr Now with convolution!

<3 convolution!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Hofstadter Q-sequence
Definition

a(1) = 1
a(2) = 1
a(n) = a(n-a(n-1)) + a(n-a(n-2)) for n > 2 where n is an integer

Task
Given positive integer n, generate a(n).
Testcases
n  a(n)
1  1
2  1
3  2
4  3
5  3
6  4
7  5
8  5
9  6
10 6
11 6
12 8
13 8
14 8
15 10
16 9
17 10
18 11
19 11
20 12

Reference

Obligatory OEIS A005185

Related.

Related answer.

Can we return True in languages where it can be used as 1?

@Dennis If in that language true is equivalent to 1 then yes.

Apart from the OEIS link it might be good to reference GEB where the sequence first appeared.

Related

Completing the list of GEB-related sequence challenges.

You could probably translate the problem description into Haskell by only adding a few characters.

What input does it have to support up to?

That´s not Leonard Hofstadter, is it?

Haskell, 35 33 bytes
a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)

Defines a function a.

Nice trick with the bind! Wouldn't something like (b.b)1+(b.b)2 be shorter than the sum?

Why yes, thanks @xnor.

Retina, 84 83 79 74 bytes
Byte count assumes ISO 8859-1 encoding.
.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1

Try it online! (The first line enables a linefeed-separated test suite.)
I'll have to golf this some more later.

Julia, 29 bytes
!n=n<3||!(n-!~-n)+!(n-!~-~-n)

Try it online!
How it works
We redefine the unary operator ! for our purposes.
If n is 1 or 2, n<3 returns true and this is our return value.
If n larger than 2, n<3 returns false and the || branch gets executed. This is a straightforward implementation of the definition, where ~-n yields n - 1 and ~-~-n yields n - 2.

Sesos, 54 bytes
0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7  ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383  ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f                       v.<?c.~.....

Try it online
Disassembled
set numin
set numout
add 1
fwd 1
add 1
fwd 6
get
sub 1
jmp
    jmp
        sub 1
        fwd 1
        add 1
        rwd 1
    jnz
    fwd 1
    sub 1
    rwd 2
    add 2
    jmp
        rwd 4
        jmp
            sub 1
            fwd 3
            add 1
            rwd 3
        jnz
        fwd 4
        jmp
            sub 1
            rwd 3
            add 1
            rwd 1
            add 1
            fwd 4
        jnz
        rwd 3
        jmp
            sub 1
            fwd 3
            add 1
            rwd 3
        jnz
        fwd 4
        add 2
        jmp
            rwd 5
            jmp
                rwd 1
                jmp
                    sub 1
                    fwd 2
                    add 1
                    rwd 2
                jnz
                fwd 1
                jmp
                    sub 1
                    rwd 1
                    add 1
                    fwd 1
                jnz
                rwd 1
                sub 1
            jnz
            fwd 2
            jmp
                sub 1
                rwd 1
                add 1
                rwd 1
                add 1
                fwd 2
            jnz
            fwd 1
            jmp
                rwd 2
                jmp
                    sub 1
                    fwd 1
                    add 1
                    rwd 1
                jnz
                fwd 2
                jmp
                    sub 1
                    rwd 2
                    add 1
                    fwd 2
                jnz
                fwd 1
            jnz
            fwd 3
            sub 1
        jnz
        rwd 2
        jmp
            sub 1
            rwd 3
            add 1
            fwd 3
        jnz
        fwd 1
        sub 1
    jnz
    fwd 2
jnz
rwd 7
put

Or in Brainfuck notation:
+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.

C, 43 42 bytes
Saved 1 byte thanks to @Dennis
Every answer is the same, I must do something different!
Try it online!
a(n){return n<3?:a(n-a(n-2))+a(n---a(n));}

Explanation: it's basically a(n-a(n-2))+a(n-a(n-1)) but with swaggyundefinedbehavior (works on my phone (gcc) and ideone).

You should also mention the compiler; your "swag" is undefined behavior. 2. With GCC, you don't need the 1 between ? and :.

@Dennis Interestingly, that same formulation works in my iterative PowerShell answer... $b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]

@TimmyD some compilers may compile the a(n) before the n--, and there isn't a standart (or defined) behavior for that. Thus, undefined behavior.

@betseg Yep, I agree. Just pointing out that it's not necessarily unique to C.

@TimmyD Oh I misunderstood that. I just wanted to change the function that everybody uses, so mine would be different and swaggy :D

…If you just want to be different, you could use ~-n == n-1 rather than relying on undefined behavior.

Mathematica, 36 bytes
Byte count assumes ISO 8859-1 encoding and Mathematica's $CharacterEncoding set to WindowsANSI (the default on Windows; other settings might work as well, but some like UTF-8 definitely don't).
±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))

Defines ± as a unary operator.
I tried getting rid of the duplication, but ended up with the same byte count:
±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]

I may give you a +200 bounty if you do it in Retina

@LeakyNun okay? :)

Two days later.

@LeakyNun Soon you're going to have no rep left if you give out bounties so easily.

Let us continue this discussion in chat.

Jelly, 15 14 bytes
2Rạ⁸ß€$⁺Sµ1>?2

Try it online! or verify all test cases (takes a few seconds).
How it works
2Rạ⁸ß€$⁺Sµ1>?2  Main link. Argument: n (integer)

2R              Yield [1, 2].
      $         Combine the previous three links into a monadic chain.
   ⁸                Yield n.
  ạ                 Take the absolute difference of the return value and n.
    ß€              Recursively call the main link on each result.
       ⁺            Duplicate the chain.
                    The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
                    The second copy maps [a(n - 1), a(n - 2)] to
                    [a(n - a(n - 1)), a(n - a(n - 2))].
        S           Take the sum.
         µ          Combine all links to the left into a chain.
            ?       If...
           > 2          n is greater than 2, call the chain.
          1         Else, return 1.

I may give you a +400 bounty if you do it in Sesos.

@LeakyNun There seems to be an Sesos answer. It came out one day after your comment.

Jelly, 14 12 11 bytes
ịḣ2S;
1Ç⁸¡2ị

This is an iterative approach.
Try it online! or verify all test cases.
How it works
1Ç¡2ị   Main link. Argument: n

1       Set the return value to 1.
 Ç¡     Call the helper link n times, updating the return value after each call.
   2ị   Extract the second element of the resulting array.

ịḣ2S;   Helper link. Argument: A (array)

ị       At-index; retrieve the elements of A at the values of A.
 ḣ2     Head 2; extract the first two results.
    S   Take the sum of the result.
     ;  Prepend the sum to A.

JavaScript (ES6), 45 Bytes 34 Bytes
A recursive solution in ES6. Any golfing tips much appreciated.
a=n=>n>2?a(n-a(n-1))+a(n-a(n-2)):1

Thank you to /u/ismillo for shortening even further.

Python, 45 40 bytes
a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))

Simple naïve interpretation of the challenge.
Saved 5 bytes thanks to @LeakyNun!

Haskell, 39 37 Bytes
h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))

exactly like described in the challenge, using guards

Sorry, I didn't saw your solution before posting my (identical) haskell solution. However isn't the byte count 38 as the new-line has to be taken into account?

And the guard has to be n<3 for h 2  to be 1.

@Laikoni It's 37 according to Pythons len feature with a multiline (""") string, unless you count newline as two bytes. Yeah, I noticed the other thing it's fixed now.

TIL notepad++ counts newline as two character.

@Laikoni got rid of the newline it's indisputably 37 bytes now.

@Laikoni In windows a newline is quite often represented as \r\n, while \n is sufficient.

@flawr Good to know.

I thought we're allowed to count the newlines as singles always.

C#, 51 44 bytes
int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));

i wonder if this can be shortened by making it anonymous
thanks pinkfloydx33!

c# 6 expression bodied function int a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));

Seems I typod while typing that on my phone. The inner most -a in the first set of parens should be -1

I didn't notice it either, ill fix it rq

R, 50 bytes
a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))

Usage:
> a(1)
  1
> a(20)
  12

CJam, 19 18 bytes
XXri{_($2$$+}*]-3=

Try it online!
Uses the iterative approach.

Ruby, 36 bytes
A direct implementation. Any golfing suggestions are welcome.
a=->n{n<3?1:a[n-a[n-1]]+a[n-a[n-2]]}

Afaik, you can get rid of the a=. If you post it here, it suffices when your code starts with the ->. It counts as an anonymous function then.

@Seims Unfortunately, as the function calls itself with a[n-1] and such, the function needs to be named.

Golfscript, 29 bytes
~[1 1]{..0=(=\..1=(=@+\+}@*2=

Try it online!

Java 7, 68 61 51 bytes
17 saved thanks to Leaky Nun.
int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}

Welcome to PPCG!

Welcome to PPCG! You might like Tips for Golfing in Java. An alternate form would be: int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}, but unfortunately it uses the same amount of bytes as the answer you already have.. Also, I would specify that your answer is in Java 7, since the Java 8 answer would be shorter: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2)) (39 bytes).

Thanks for the welcomes guys, and thanks for the tip on Java8 - I didn't realize lambdas were allowed like that - although they're allowed like that in Python, so I guess I just never thought about it. Does the lambda need a semi-colon?

@JustinTervay I don't use Java 8 a lot, but from what I've heard the semi-colon isn't counted on single-line expressions, according to a comment by @DavidConrad and @CAD97 in one of my own Java answers.

05AB1E, 29 bytes
An iterative solution.
XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è

Try it online

APL, 20 bytes
{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}

Explanation:
{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
 ⍵≤2:1               If argument is 2 or less, return 1
      ⋄              Otherwise:
               ⍵-⍳2  Subtract [1, 2] from the argument
             ∇¨      Recursive call on both
           ⍵-        Subtract both results from the argument
         ∇¨          Recursive call on both again
       +/            Sum

VBA Excel 87 bytes
Non-recursive, since I want this to work for n=100000, say:
Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1

... and press return (byte #87) at the end of the line to get the End Function statement for "free". Note that B values are offset by -1 to avoid initializing for n=1 and 2.
Invoke in spreadsheet as normal, eg =A(100000) to get 48157
The recursive version, 61 bytes,
Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))

starts to get unreasonably slow for n>30, and couldn't be said to work at all for n>40.

We don't care about performance. We care about code length. You should move your shorter solution to the top of your answer.

@mbomb007 Since I'm nowhere near winning the golf, I'll make my own choices on what constitutes a working program. Not able to handle even single byte integers is not good enough as far as I'm concerned, when there is a solution which can do so easily.

Oasis, 9 7 5 bytes
Non-competing, since the language postdates the challenge. Thanks to Kenny Lau for saving 4 bytes. Code:
ece+V

Expanded form (V is short for 11):
a(n) = ece+
a(0) = 1
a(1) = 1

Code:
e        # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
 c       # Calculate a(n - 2)
  e      # Calculate a(n - a(n - 2))
   +     # Add up

Try it online!. Calculates n = 1000 in 0.1 seconds.

PowerShell v2+, 85 79 69 bytes
param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]

Takes input $n, sets $b to be an array of @(1, 1), then enters a loop from 2 .. $n. Each iteration we tack onto $b the latest calculation in the sequence with a simple += and the definition of the sequence. We then output the appropriate number from $b (with a -1 because arrays in PowerShell are zero-indexed). This works if $n is 1 or 2 because both of those values are pre-populated into the lower indices of $b from the start, so even if the loop tacks on junk, it's ignored anyway.

Recursive solution 78 76 bytes
$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}

First time I've used the equivalent of a lambda as the answer, as usually an iterative solution is shorter (as you can see from all the nested parens). But, in this case, the nested parens are almost duplicated in the iterative solution with the nested array calls, so the recursive solution is shorter. Nope, the iterative solution is indeed shorter (see above).
Call it via the execution-operator, like &$a 20. Just a straight-up recursive call.

Maple, 43 41 bytes
a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)

Usage:
> a(1);
  1
> a(20);
  12

This problem is certainly a good candidate for memoization. Using option cache, the run times are cut down significantly:
aC := proc(n)
      option cache;
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 );
end proc:

This can be seen using:
CodeTools:-Usage( aC(50) );

JavaScript (ES6), 66 bytes
n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])

Non-recursive version for speed; recursive version is probably shorter but I'll leave it for someone else to write. I always like it when I get to use reduce. Note: 1 byte saved by returning true (which casts to 1 when used in an integer context) for of a(1) and a(2).

Pyth, 16 bytes
L|<b3smy-bytdtBb

L                  def y(b):
 |<b3                b < 3 or …
      m      tBb       map for d in [b - 1, b]:
       y-bytd            y(b - y(d - 1))
     s                 sum

Defines a function y.
Try it online
(added yMS20 to print the first 20 values)

Forth, 76 bytes
I finally got it working!
: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;

Try it online
Explanation:
: Q recursive                           \ Define a recursive function Q
    dup dup 3 <                         \ I moved a dup here to golf 2 bytes
    if                                  \ If n < 3, return 1
        - 1                             \ Golf: n-n is zero, add one. Same as 2drop 1+
    else
        2dup 2 - Q - Q                  \ Copy n until 4 on stack, find Q(n-Q(n-2))
        -rot                            \ Move the result below 2 copies of n
        1- Q - Q +                      \ Find Q(n-Q(n-2)), then add to previous ^
    then ;

Try it online (slightly un-golfed from above)
Unfortunately, mutual recursion is a bit too wordy to use for golfing.

Lua, 59 bytes
function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end

Husk, 17 bytes
!¡λṁ!¹m≠→L¹↑_2)ḋ3

Try it online!
Feels too long. I'll post something with fix soon.

Japt, 20 bytes
No big shenanigans, just recursively calculates the result.
§2?1:ßU-ßUÉ)+ßU-ßU-2
§2                   // If the input is less than or equal to 2
  ?1                 // return 1,
    :                // otherwise
     ß               // recursively recall with
      U-ßUÉ          // input minus recursive recall input minus one
           )+        // plus
             ßU-ßU-2 // same with input minus two.

Try it here.

15 bytes

J, 29 28 bytes
1:`(+&$:/@:-$:@-&1 2)@.(2&<)

Uses the recursive definition.
Usage
Extra commands are used for formatting multiple input/output.
   f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
   (,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6  6  6  8  8  8 10  9 10 11 11 12

Explanation
1:`(+&$:/@:-$:@-&1 2)@.(2&<)  Input: n
                        2&<   If n < 2
1:                              Return 1
                              Else
               -&1 2            Subtract [1, 2] from n to get [n-1, n-2]
            $:@                 Call recursively on n-1 and n-2
           -                    Subtract each of the results from n
        /@:                     Reduce using
      $:                          A recursive call on each
    +&                            Then summation
                                Return that value as the result

dc, 62 bytes
?si2sa1dd2:a:a[la1+dsadd1-;a-;alad2-;a-;a+r:ali;a0=A]dsAxli;af

This solution makes use of arrays and recursion.
?si          # Take input from stdin and store it in register `i'
2sa          # Initialise register `a' with 2, since we'll be putting in the first
             #   two values in the sequence
1dd2         # Stack contents, top-down: 2 1 1 1
:a           # Pop index, then pop value: Store 1 in a[2]
:a           # Ditto:                     Store 1 in a[1]
[            # Open macro definition
 la 1+ dsa   # Simple counter mechanism: Increment a and keep a copy on stack

# The STACK-TRACKER(tm): Top of stack will be at top of each column, under the
#   dashed line. Read commands from left to right, wrapping around to next line.
#   This will be iteration number n.
  dd   1-    ;a       -          ;a            la            d
#-----------------------------------------------------------------------
# n    n-1   a[n-1]   n-a[n-1]   a[n-a[n-1]]   n             n
# n    n     n        n          n             a[n-a[n-1]]   n
# n    n     n                                 n             a[n-a[n-1]]
#                                                            n
#

  2-            ;a            -             ;a            +      r    :a
#-----------------------------------------------------------------------
# n-2           a[n-2]        n-a[n-2]      a[n-a[n-2]]   a[n]   n
# n             n             a[n-a[n-1]]   a[n-a[n-1]]   n      a[n]
# a[n-a[n-1]]   a[n-a[n-1]]   n             n
# n             n

 li;a        # Load index of target element, and fetch that element's current value
             #    Uninitialised values are zero
 0=A         # If a[i]==0, execute A to compute next term
]dsAx        # Close macro definition, store on `A' and execute
li;a         # When we've got enough terms, load target index and push value
f            # Dump stack (a[i]) to stdout

In conclusion, if anyone is building an IDE for dc, let me know!

Erlang, 46 bytes
f(N)when N<3->1;f(N)->f(N-f(N-1))+f(N-f(N-2)).

Racket, 63 bytes
(define(a n)(if(> n 2)(for/sum([m'(1 2)])(a(- n(a(- n m)))))1))

><>, 65+2 = 67 bytes
^n;
.+]{0$
v1}\
v2} @2->1[
v3}>-  /:::1-1[
>4}:2)?^~~1]{0$.
/0$1[

Input neds to be present on the stack at program start, so +2 bytes for the -v flag. Try it online!
More ridiculously slow recursive madness. Test case for 20 on TIO takes 20.5 seconds, so use larger inputs at your own risk

Clojure, 86 bytes
(defn a[n](cond(< 0 n 3)1 1(+(a(- n(a(dec n))))(a(- n(a(- n 2)))))))

Very literal.
(defn a [n]
  (cond
    (< 0 n 3) 1 ; Return 1 if n is 1 or 2
    :else (+ (a (- n (a (dec n)))) ; Else, recurse 4 times and do some math
             (a (- n (a (- n 2)))))))

(doseq [n (range 1 21)]
  (println n (a n)))

1 1
2 1
3 2
4 3
5 3
6 4
7 5
8 5
9 6
10 6
11 6
12 8
13 8
14 8
15 10
16 9
17 10
18 11
19 11
20 12

I think you can get rid of the 0 in the < statement, because the challenge specs state that the input is a positive integer.

@Qwerp-Derp ohh, thanks. I'll fix that when I get on my laptop.

Lithp, 70 bytes
(def a #N::((if(<= N 2)(1)((+(a(- N(a(- N 1))))(a(- N(a(- N 2)))))))))

Warning: incredibly slow. Very recursive. Implements the exact algorithm in challenge.
Try it online!
An alternate solution that is much faster, using caching of results:
Lithp, 166 bytes
((def a #N::((if(<= N 2)(1)((+(b(- N(b(- N 1))))(b(- N(b(- N 2)))))))))(var C(dict))
 (def b(scope #N::((if(!(dict-present C N))((dict-set C N(a N))))(dict-get C N)))))

Try it online!

Just curious, why did you make functions like (def a #N::(+ N 1)), where a is a successor?

I'm sorry I don't quite understand you. What do you mean by successor?

A successor function is a function that increments a number, but that's besides the point. I'm just curious about the way to define functions in Lithp - why did you choose to do #arg:: when defining functions? I haven't really seen that done in a Lisp-like before.

Ah, thank you. Firstly, lowercase names are atoms. Names beginning with an uppercase are variables. It follow Erlang's design in this way. Next, I struggled to read most Lisp code, though I loved the elegance of it. The way I've designed my syntax is to be easy to read, and an anonymous function (format: #[Args,...] :: ( calls .. )) was easy to see what arguments are being passed.
It's only sort-of Lisp-like really. I like the elegance of the braces, and it's easy to parse.

Oh, that's how it works, thanks! I was looking at the arguments and it seemed a bit weird, but now that you've explained it I can understand why it's like that.

PHP, 56 bytes
function q($n){return$n<3?:q($n-q($n-1))+q($n-q($n-2));}

recursive function; requires PHP 5.6 or later (or replace ?: with ?1:).

Japt -N, 14 bytes
Note that the -N flag isn't strictly necessary here as it would seem returning true instead of 1 is allowed.
§2ªCìx@ßU-ßXnU

Try it or run all test cases
§2ªCìx@ßU-ßXnU     :Implicit input of integer U
§2                 :Less than or equal to 2?
  ª                :Logical OR with
   C               :12
    ì              :To digit array
     x             :Reduce by addition
      @            :After passing each X through the following function
       ß           :  Recursive call with argument
        U-         :    U minus
          ß        :      Recursive call with argument
           XnU     :        U minus X

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/