问:
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)

```<code>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.
</code>```

2 (Gettysburg Address)

```<code>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.
</code>```

3 (Lorem Ipsum)

```<code>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.
</code>```

4 (Jabberwocky)

```<code>'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.
</code>```

5 (Euclid's proof of the Pythagorean Theorem)

```<code>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.
</code>```

6 (Badger, Badger, Badger by weebl)

```<code>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!
</code>```

答:
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'
```

<p>Lorem Ipsum, original then patched:</p>

```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

Title: Patch the Paragraph

Body:
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


问:
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

```<code>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
</code>```

Reference

Obligatory OEIS A005185

答:
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).

```<code>±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))
</code>```

Defines ± as a unary operator.

I tried getting rid of the duplication, but ended up with the same byte count:

```<code>±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]
</code>```

ContentLicense: CC BY-SA 3.0

Title: Hofstadter Q-sequence

Body:
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}]


问:
Coin Change Problem Enumeration Using N Coins And Each Denomination
The coin change problem is very well documented. Given an infinite supply of coins of denominations x_1 to x_m you need to find the number of combinations which add up to y. For example, given x = {1,2,3} and y = 4 we have four combinations:

{1,1,1,1}

{1,1,2}

{1,3}

{2,2}

Introduction

There are several variations of the coin change problem. In this variation  we have two additional restrictions:

Every denomination must be used at least once.

Exactly a fixed number of coins must be used in total.

For example, given x = {1,2,3}, y = 36 and n = 15 where n is the total number of coins that must be used, we get four combinations:

{1,2,2,2,2,2,2,2,3,3,3,3,3,3,3} (1 ones, 7 twos, 7 threes)

{1,1,2,2,2,2,2,3,3,3,3,3,3,3,3} (2 ones, 5 twos, 8 threes)

{1,1,1,2,2,2,3,3,3,3,3,3,3,3,3} (3 ones, 3 twos, 9 threes)

{1,1,1,1,2,3,3,3,3,3,3,3,3,3,3} (4 ones, 1 twos, 10 threes)

Challenge

The challenge is to write a function enumerate in the language of your choice which enumerates all the combinations as described above given:

The list of denominations. For example {1,5,10,25}. You may use either lists or arrays.

A non-negative integer y that denotes the sum of every combination.

A non-negative integer n that denotes the total number of coins.

The order of the arguments doesn't matter. Pointfree functions are allowed.

The output of the enumerate function must be a list of combinations. Each combination must be unique and it must be a list of n integers which add up to y. Every denomination must appear at least once in each combination and no combination must be missing. The ordering of the integers and the combinations doesn't matter. You may use either lists or arrays for the output.

Keep in mind the following edge cases:

If both y and n are zero and the list of denominations is empty then the output is a list of one combination, the empty combination (i.e. {{}}).

Otherwise, if y is zero, n is zero or the list of denominations is empty then the output is a list of zero combinations (i.e. {}).

More generally, if y is less than the sum of the denominations or n is less than the number of denominations then the output is a list of zero combinations.

Scoring will be based on the size of the entire program in bytes. Note that this includes the enumerate function, helper functions, import statements, etc. It does not include test cases.

答:
Python 3, <s>120</s> 106 bytes

```<code>from itertools import*
lambda d,t,l:[i+d for i in combinations_with_replacement(d,l-len(d))if sum(i+d)==t]
</code>```

An anonymous function that takes input of a tuple of denominations of the form (x_1, x_2, x_3 ... , x_k), a target value, and a number of coins via argument, and returns a list of tuples of the form [(solution_1), (solution_2), (solution_3), ... (solution_k)].

How it works

Itertools's combinations_with_replacement function is used to generate all l-len(d) combinations, with replacement, of the denominations. By appending d to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length l. If the elements of a combination sum to t, the combination is added to the return list as a tuple.

Try it on Ideone

An alternative method for 108 bytes

```<code>from itertools import*
lambda d,t,l:set(tuple(sorted(i+d))for i in product(d,repeat=l-len(d))if sum(i+d)==t)
</code>```

An anonymous function that takes input of a tuple of denominations of the form (x_1, x_2, x_3 ... , x_k), a target value, and a number of coins via argument, and returns a set of tuples of the form {(solution_1), (solution_2), (solution_3), ... (solution_k)}.

How it works (other version)

This uses the product function from itertools to generate all l-len(d) arrangements of the denominations. By appending d to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length l. If the elements of a combination sum to t, the combination is sorted, converted from a list to a tuple, and added to the return tuples. Finally, calling set removes any duplicates.

Try it on Ideone (other version)

Body:
Python 3, <s>120</s> 106 bytes

from itertools import*
lambda d,t,l:[i+d for i in combinations_with_replacement(d,l-len(d))if sum(i+d)==t]

An anonymous function that takes input of a tuple of denominations of the form (x_1, x_2, x_3 ... , x_k), a target value, and a number of coins via argument, and returns a list of tuples of the form [(solution_1), (solution_2), (solution_3), ... (solution_k)].

How it works

Itertools's combinations_with_replacement function is used to generate all l-len(d) combinations, with replacement, of the denominations. By appending d to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length l. If the elements of a combination sum to t, the combination is added to the return list as a tuple.

Try it on Ideone

An alternative method for 108 bytes

from itertools import*
lambda d,t,l:set(tuple(sorted(i+d))for i in product(d,repeat=l-len(d))if sum(i+d)==t)

An anonymous function that takes input of a tuple of denominations of the form (x_1, x_2, x_3 ... , x_k), a target value, and a number of coins via argument, and returns a set of tuples of the form {(solution_1), (solution_2), (solution_3), ... (solution_k)}.

How it works (other version)

This uses the product function from itertools to generate all l-len(d) arrangements of the denominations. By appending d to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length l. If the elements of a combination sum to t, the combination is sorted, converted from a list to a tuple, and added to the return tuples. Finally, calling set removes any duplicates.

Try it on Ideone (other version)


答:
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.

Title: Hofstadter Q-sequence

Body:
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

```<code>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
</code>```

Reference

Obligatory OEIS A005185

Body:
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.


问:
Array Sandwiches
(Adapted from Problem C of the first qualifier of the ACM Programming Contest of 2012/2013)

You have several arrays, named \$A_1, A_2, ... , A_n\$, each sorted in ascending order. Every item in the array will be a 32-bit integer.

A sandwich is a set of indices \$j_1, j_2, ... , j_n\$ such that \$A_1[j_1] ≤ A_2[j_2] ≤ ... ≤ A_n[j_n]\$. \$A_i[0]\$ is the first element of \$A_i\$.

Given some arrays, output every possible sandwich that you can have from those arrays, separated by a newline.

If there is somehow a built-in function which does this in your language, don't use it.

Input can be given in any way, output must be separated with whitespace, but can given in any order.

Test Case:

```<code>[[1, 5, 7, 10], [2, 6, 6, 8, 12], [4, 5, 9]]
</code>```

Output:

```<code>0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2
</code>```

Test Case:

```<code>[[10, 20, 30], [1, 2, 3]]
</code>```

Output:

Shortest code wins.

ContentLicense: CC BY-SA 4.0

Title: Array Sandwiches

Body:
Q, 43

{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}


答:
C, <s>43</s> 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).

Title: Hofstadter Q-sequence

Body:
C, <s>43</s> 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).


答:
PowerShell v2+, <s>85</s> <s>79</s> 69 bytes

```<code>param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]
</code>```

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 <s>78</s> 76 bytes

```<code>$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}
</code>```

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). <s>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.</s> Nope, the iterative solution is indeed shorter (see above).

Call it via the execution-operator, like &$a 20. Just a straight-up recursive call.

Title: Hofstadter Q-sequence

Body:
PowerShell v2+, <s>85</s> <s>79</s> 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 <s>78</s> 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). <s>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.</s> Nope, the iterative solution is indeed shorter (see above).

Call it via the execution-operator, like &$a 20. Just a straight-up recursive call.


答:
Retina, <s>84</s> <s>83</s> <s>79</s> 74 bytes

Byte count assumes ISO 8859-1 encoding.

```<code>.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1
</code>```

Try it online! (The first line enables a linefeed-separated test suite.)

I'll have to golf this some more later.

Title: Hofstadter Q-sequence

Body:
Retina, <s>84</s> <s>83</s> <s>79</s> 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.


答:
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))
```

<p>Here's the result of Badger, Badger, Badger:</p>

```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!
```

<p>Here's the result from the proof:</p>

```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.
```

<p>And the result of Jabberwocky:</p>

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

Title: Patch the Paragraph

Body:
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)

```<code>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.
</code>```

2 (Gettysburg Address)

```<code>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.
</code>```

3 (Lorem Ipsum)

```<code>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.
</code>```

4 (Jabberwocky)

```<code>'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.
</code>```

5 (Euclid's proof of the Pythagorean Theorem)

```<code>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.
</code>```

6 (Badger, Badger, Badger by weebl)

```<code>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!
</code>```

Body:
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.


问:
Partial factorisations of a positive integer
A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if

```<code>d_1 * d_2 * ... * d_k = n
</code>```

Each positive integer has a unique prime factorisation, but in general they also have factorisations in which some of the terms are composite. E.g.

```<code>12 = 6 * 2 = 4 * 3 = 3 * 2 * 2
</code>```

Write a program, function, verb, or similar which takes as input a single positive integer and returns or prints a complete list of its distinct factorisations. The factorisations may be produced in any order, and their terms may be in any order, but no two should be permutations of each other. Factorisations may not include 1 with two exceptions: for input n you may give the factorisation n*1 instead of n; and for input 1 you may give the factorisation 1 instead of the empty list.

You may assume that the input will be in the range of a signed 32-bit integer. If the output is as a string, there should be a clear distinction between the delimitation of numbers within a factorisation and the delimitation of the factorisations, but it is not necessary (for example) for the factors to be joined with an *.

Your code should be capable of handling any valid input within 10 minutes on a reasonable desktop machine.

Examples

```<code>1                  [[]]
                or [[1]]
                or [[1 1]]

7                  [[7]]
                or [[7 1]]
                or [[1 7]]

12                 [[12] [6 2] [4 3] [2 3 2]]
                or variants

16                 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
                or variants

901800900          a list of 198091 factorisations

1338557220         a list of 246218 factorisations
</code>```

答:
Ruby 1.9+, <s>87</s> <s>89</s> 87 bytes

This answer is based on Anders Kaseorg's Pyth answer. This code only works for versions after Ruby 1.9, as stabby lambdas -> were only introduced in 1.9. Any golfing suggestions are welcome.

g=->n,m=2{(m..Math.sqrt(n)).select{|i|n%i<1}.flat_map{|d|g[n/d,d].map{|j|[d]+j}}+[[n]]}
```

<p><strong>Ungolfed:</strong></p>

<pre class="lang-ruby prettyprint-override"><code>def g(n, m=2)
  a = [[n]]
  s = (m..Math.sqrt(n))
  t = s.select{|i|n%i<1}
  t.each do |d|
    g[n/d,d].each do |j|
      a.push([d]+j)
    end
  end
  return a
end
</code>```

Body:
Ruby 1.9+, <s>87</s> <s>89</s> 87 bytes

This answer is based on Anders Kaseorg's Pyth answer. This code only works for versions after Ruby 1.9, as stabby lambdas -> were only introduced in 1.9. Any golfing suggestions are welcome.

g=->n,m=2{(m..Math.sqrt(n)).select{|i|n%i<1}.flat_map{|d|g[n/d,d].map{|j|[d]+j}}+[[n]]}

Ungolfed:

def g(n, m=2)
  a = [[n]]
  s = (m..Math.sqrt(n))
  t = s.select{|i|n%i<1}
  t.each do |d|
    g[n/d,d].each do |j|
      a.push([d]+j)
    end
  end
  return a
end


答:
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]]}
```

Title: Hofstadter Q-sequence


问:
Catalan Numbers
The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics.

The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as [[][]]; formally defined as a string using two characters a and b such that any substring starting from the beginning has number of a characters greater than or equal to number of b characters, and the entire string has the same number of a and b characters) with length 2n. The nth Catalan number (for \$n\ge0\$) is also explicitly defined as:
$$C_n=\frac1{n+1}\binom{2n}n$$
Starting from \$n=0\$, the first 20 Catalan numbers are:

```<code>1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
</code>```

Challenge

Write a full program or function that takes a non-negative integer n via STDIN or an acceptable alternative, and outputs the nth Catalan number. Your program must work at minimum for inputs 0-19.

I/O

Input

Your program must take input from STDIN, function arguments or any of the acceptable alternatives per this meta post. You can read the inputted number as its standard decimal represention, unary representation, or bytes.

If (and only if) your language cannot take input from STDIN or any acceptable alternative, it may take input from a hardcoded variable or suitable equivalent in the program.

Output

Your program must output the nth Catalan number to STDOUT, function result or any of the acceptable alternatives per this meta post. You can output the Catalan number in its standard decimal representation, unary representation or bytes.

The output should consist of the approriate Catalan number, optionally followed by one or more newlines. No other output can be generated, except constant output of your language's interpreter that cannot be suppressed (such as a greeting, ANSI color codes or indentation).

This is not about finding the language that is the shortest. This is about finding the shortest program in every language. Therefore, I will not accept an answer.

In this challenge, languages newer than the challenge are acceptable as long as they have an implementation. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language. Other than that, all the standard rules of code-golf must be obeyed. Submissions in most languages will be scored in bytes in an appropriate preexisting encoding (usually UTF-8). Note also that built-ins for calculating the nth Catalan number are allowed.

Catalog

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```<code>## Language Name, N bytes
</code>```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```<code>## Ruby, <s>104</s> <s>101</s> 96 bytes
</code>```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```<code>## Perl, 43 + 2 (-p flag) = 45 bytes
</code>```

You can also make the language name a link which will then show up in the snippet:

```<code>## [><>](http://esolangs.org/wiki/Fish), 121 bytes
</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

Title: Catalan Numbers

Body:
Maple, 18 bytes

(2*n)!/((n+1)!*n!)

Usage:

> f := n->(2*n)!/((n+1)!*n!);
> f(19);
  1767263190


Title: Hofstadter Q-sequence

Body:
Golfscript, 29 bytes

~[1 1]{..0=(=\..1=(=@+\+}@*2=

Try it online!


答:
Maple, <s>43</s> 41 bytes

```<code>a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)
</code>```

Usage:

```<code>> a(1);
  1
> a(20);
  12
</code>```

This problem is certainly a good candidate for memoization. Using option cache, the run times are cut down significantly:

```<code>aC := proc(n)
      option cache;
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 );
end proc:
</code>```

This can be seen using:

```<code>CodeTools:-Usage( aC(50) );
</code>```

Title: Hofstadter Q-sequence

Body:
Maple, <s>43</s> 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) );


答:
Java 7, 68 61 51 bytes

17 saved thanks to Leaky Nun.

```<code>int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}
</code>```

Title: Hofstadter Q-sequence

Body:
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));}


Title: Hofstadter Q-sequence

Body:
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


问:
Draw the national flag of Iceland
This year's UEFA Euro 2016 is over and besides a couple of negative headlines there has been a very positive surprise as well – the Iceland national football team. Let's draw their national flag.

Input

Well, obviously this challenge has no input.

Output

Draw the flag of Iceland in any applicable visual format of at least 100 x 72 pixels or 25 x 18 characters.

Save the output to a file or present it instantly – example formats are: images like png, jpg etc., vector graphics, draw on HTML canvas or even use non-whitespace characters for visualization.

Use these colors: blue: #0048e0, white: #ffffff and red: #d72828.

If your language doesn't support specific color values, use the standard values for red, blue and white from the ANSI color codes.

Draw the flag with the correct proportions, as shown in the figure below:

Boilerplate

You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.

This is code-golf so shortest answer in bytes wins.

Standard loopholes are disallowed.

Leaderboard

var QUESTION_ID = 85141; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 41859; // This should be the user ID of the challenge author.
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;function answersUrl(index) {return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;}function commentUrl(index, answers) {return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;}function getAnswers() {jQuery.ajax({url: answersUrl(answer_page++),method: "get",dataType: "jsonp",crossDomain: true,success: function (data) {answers.push.apply(answers, data.items);answers_hash = [];answer_ids = [];data.items.forEach(function(a) {a.comments = [];var id = +a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id] = a;});if (!data.has_more) more_answers = false;comment_page = 1;getComments();}});}function getComments() {jQuery.ajax({url: commentUrl(comment_page++, answer_ids),method: "get",dataType: "jsonp",crossDomain: true,success: function (data) {data.items.forEach(function(c) {if (c.owner.user_id === OVERRIDE_USER)answers_hash[c.post_id].comments.push(c);});if (data.has_more) getComments();else if (more_answers) getAnswers();else process();}});}getAnswers();var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG = /^Override\s*header:\s*/i;function getAuthorName(a) {return a.owner.display_name;}function process() {var valid = [];answers.forEach(function(a) {var body = a.body;a.comments.forEach(function(c) {if(OVERRIDE_REG.test(c.body))body = '
' + c.body.replace(OVERRIDE_REG, '') + '
';});var match = body.match(SCORE_REG);if (match)valid.push({user: getAuthorName(a),size: +match[2],language: match[1],link: a.share_link,});});valid.sort(function (a, b) {var aB = a.size,bB = b.size;return aB - bB});var languages = {};var place = 1;var lastSize = null;var lastPlace = 1;valid.forEach(function (a) {if (a.size != lastSize)lastPlace = place;lastSize = a.size;++place;var answer = jQuery("#answer-template").html();answer = answer.replace("{{PLACE}}", lastPlace + ".").replace("{{NAME}}", a.user).replace("{{LANGUAGE}}", a.language).replace("{{SIZE}}", a.size).replace("{{LINK}}", a.link);answer = jQuery(answer);jQuery("#answers").append(answer);var lang = a.language;if (! /<a/.test(lang)) lang = '' + lang + '';lang = jQuery(lang).text().toLowerCase();languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link, uniq: lang};});var langs = [];for (var lang in languages)if (languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function (a, b) {if (a.uniq > b.uniq) return 1;if (a.uniq < b.uniq) return -1;return 0;});for (var i = 0; i < langs.length; ++i){var language = jQuery("#language-template").html();var lang = langs[i];language = language.replace("{{LANGUAGE}}", lang.lang).replace("{{NAME}}", lang.user).replace("{{SIZE}}", lang.size).replace("{{LINK}}", lang.link);language = jQuery(language);jQuery("#languages").append(language);}}```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body { text-align: left !important}#answer-list {padding: 10px;width: 290px;float: left;}#language-list {padding: 10px;width: 290px;float: left;}table thead {font-weight: bold;}table td {padding: 5px;}</code>```

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/Sites/codegolf/all.css?v=617d0685f6f3">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}

{{LANGUAGE}}	{{NAME}}	{{SIZE}}

```

If you can't find your answer, format your language and byte count as explained in the Leaderboard's "Info Section".

This challenge is inspired by Draw the national flag of france.

答:
ZX Spectrum Z80 assembly, <s>49</s>, <s>47</s> <s>46</s>, 47 bytes

Program when running uses 47 bytes + 4 for stack usage

 stack usage is 2 bytes to store return address and 2 for internal use

It uses no other programs and uses no other external Ram/Rom
The output is the modification of the video Ram.

Brief idea of how program draws flag.

The background is coloured blue.

Then if vertically or horizontally in the red area draw red. (offset 9 and 10)

Then if vertically or horizontally in the white area draw white, only if the background is not already coloured in red. (offset 8 and 11)

```<code>          org   8000H
red:      equ   16
white:    equ   120
blue:     equ   8
;
start:

          ld    hl,5800h
          ld    c,18
main:
          ld    b,25
loop:
          ld   de,red*256+blue
          ld   (hl),e
          ld   a,c
          call check
          ld   a,l
          and  31
          call check
          inc  hl
          djnz loop
          ld   d,b
          add  hl,de
          dec  hl
          dec  c
          jr   nz,main
          ret

check:
          sub   e
          ret   c
          jr    z,white_line
          sub   3
          jr    z,white_line
          ret   nc
          ld    (hl),d
white_line:
          ld    a,d
          cp    (hl)
          ret   z
          ld    (hl),white
          ret

          end

;         47 bytes
</code>```

Original code 49 bytes

edit 1  47 bytes  changed logic flow

edit 2  46 bytes  removed a ret

edit 3  47 bytes. fixed output to exact dimensions

Title: Draw the national flag of Iceland

Body:
ZX Spectrum Z80 assembly, <s>49</s>, <s>47</s> <s>46</s>, 47 bytes

Program when running uses 47 bytes + 4 for stack usage

 stack usage is 2 bytes to store return address and 2 for internal use

It uses no other programs and uses no other external Ram/Rom
The output is the modification of the video Ram.

Brief idea of how program draws flag.

The background is coloured blue.

Then if vertically or horizontally in the red area draw red. (offset 9 and 10)

Then if vertically or horizontally in the white area draw white, only if the background is not already coloured in red. (offset 8 and 11)

          org   8000H
red:      equ   16
white:    equ   120
blue:     equ   8
;
start:

          ld    hl,5800h
          ld    c,18
main:
          ld    b,25
loop:
          ld   de,red*256+blue
          ld   (hl),e
          ld   a,c
          call check
          ld   a,l
          and  31
          call check
          inc  hl
          djnz loop
          ld   d,b
          add  hl,de
          dec  hl
          dec  c
          jr   nz,main
          ret

check:
          sub   e
          ret   c
          jr    z,white_line
          sub   3
          jr    z,white_line
          ret   nc
          ld    (hl),d
white_line:
          ld    a,d
          cp    (hl)
          ret   z
          ld    (hl),white
          ret

          end

;         47 bytes

Original code 49 bytes

edit 1  47 bytes  changed logic flow

edit 2  46 bytes  removed a ret

edit 3  47 bytes. fixed output to exact dimensions


问:
Lithp Tranthlator
My friend made a lisp translator the other day, that is to say it took a string and converted s=>th and S=>Th. It was quite long and I thought that it could be golfed.

So the task is to make a program/function that takes an input string, translates it in to lisp and outputs the string

Test case

```<code>Sam and Sally like Sheep        Tham and Thally like Thheep
Sally likes sausages            Thally liketh thauthageth
Sally sells seashells           Thally thellth theathhellth
</code>```

Note that it doesn't matter that h gets repeated all the time

This is code golf so shortest answer wins

答:
35 Byteth of Julia:

```<code>s->replace(s,r"s"i,s->"$(s[1]+1)h")
</code>```

Try it online! (includes all test cases)

Title: Lithp Tranthlator

Body:
35 Byteth of Julia:

s->replace(s,r"s"i,s->"$(s[1]+1)h")

Try it online! (includes all test cases)


答:
J, <s>29</s> 28 bytes

```<code>1:`(+&$:/@:-$:@-&1 2)@.(2&<)
</code>```

Uses the recursive definition.

Usage

Extra commands are used for formatting multiple input/output.

```<code>   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
</code>```

Explanation

```<code>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
</code>```

Title: Hofstadter Q-sequence

Body:
J, <s>29</s> 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


答:
05AB1E, 20 bytes

```<code>g-¹sã€{Ùvy¹«DO³Qiˆ}¯
</code>```

Input is in the order: list of values, nr of coins, sum to reach.

Explanation in short

Get all permutations of the coin list of length: final length - length of unique coin list

Add the list of unique coins to these lists.

If the sum equals the sought after sum, save the list

Output all saved lists

Try it online

The online compiler can't handle large number of coins.

Title: Coin Change Problem Enumeration Using N Coins And Each Denomination

Body:
The coin change problem is very well documented. Given an infinite supply of coins of denominations x_1 to x_m you need to find the number of combinations which add up to y. For example, given x = {1,2,3} and y = 4 we have four combinations:

{1,1,1,1}

{1,1,2}

{1,3}

{2,2}

Introduction

There are several variations of the coin change problem. In this variation  we have two additional restrictions:

Every denomination must be used at least once.

Exactly a fixed number of coins must be used in total.

For example, given x = {1,2,3}, y = 36 and n = 15 where n is the total number of coins that must be used, we get four combinations:

{1,2,2,2,2,2,2,2,3,3,3,3,3,3,3} (1 ones, 7 twos, 7 threes)

{1,1,2,2,2,2,2,3,3,3,3,3,3,3,3} (2 ones, 5 twos, 8 threes)

{1,1,1,2,2,2,3,3,3,3,3,3,3,3,3} (3 ones, 3 twos, 9 threes)

{1,1,1,1,2,3,3,3,3,3,3,3,3,3,3} (4 ones, 1 twos, 10 threes)

Challenge

The challenge is to write a function enumerate in the language of your choice which enumerates all the combinations as described above given:

The list of denominations. For example {1,5,10,25}. You may use either lists or arrays.

A non-negative integer y that denotes the sum of every combination.

A non-negative integer n that denotes the total number of coins.

The order of the arguments doesn't matter. Pointfree functions are allowed.

The output of the enumerate function must be a list of combinations. Each combination must be unique and it must be a list of n integers which add up to y. Every denomination must appear at least once in each combination and no combination must be missing. The ordering of the integers and the combinations doesn't matter. You may use either lists or arrays for the output.

Keep in mind the following edge cases:

If both y and n are zero and the list of denominations is empty then the output is a list of one combination, the empty combination (i.e. {{}}).

Otherwise, if y is zero, n is zero or the list of denominations is empty then the output is a list of zero combinations (i.e. {}).

More generally, if y is less than the sum of the denominations or n is less than the number of denominations then the output is a list of zero combinations.

Scoring will be based on the size of the entire program in bytes. Note that this includes the enumerate function, helper functions, import statements, etc. It does not include test cases.

Body:
05AB1E, 20 bytes

g-¹sã€{Ùvy¹«DO³Qiˆ}¯

Input is in the order: list of values, nr of coins, sum to reach.

Explanation in short

Get all permutations of the coin list of length: final length - length of unique coin list

Add the list of unique coins to these lists.

If the sum equals the sought after sum, save the list

Output all saved lists

Try it online

The online compiler can't handle large number of coins.


问:
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:

```<code>[   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]
</code>```

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:

```<code>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]
</code>```

Test cases with x-range / y-range:

(In a not so readable but better copy-paste-able format available here on pastebin.)

```<code>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]
</code>```

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

答:
Haskell, <s>283</s> 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.

```<code>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
</code>```

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.

Title: Algebraic curve plotter

Body:
Haskell, <s>283</s> 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.


答:
Jelly, <s>14</s> <s>12</s> 11 bytes

```<code>ịḣ2S;
1Ç⁸¡2ị
</code>```

This is an iterative approach.

Try it online! or verify all test cases.

How it works

```<code>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.
</code>```

Title: Hofstadter Q-sequence

Body:
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

```<code>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
</code>```

Reference

Obligatory OEIS A005185

Body:
Jelly, <s>14</s> <s>12</s> 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.


问:
Big or Little Endian
Write a program or function that outputs an L if run on a little endian architecture or a B if run on a big endian architecture. Lower case output l or b is also acceptable.

There is no input.

Scoring is code golf, so the code with the fewest bytes wins.

Edit: As per the comments below, I am clarifying that the entry must be able to run on either architecture.

I believe that there is only one answer that this affects, and that answer has clearly indicated that this is the case.

答:
C# 50 49 bytes

Works, but has to be marked as unsafe

```<code>char i(){var a=0x0001;return*(byte*)&a>0?'L':'B';}
</code>```

Updated:

```<code>unsafe char i(){int a=1;return"BL"[*(byte*)&a];}
</code>```

Title: Big or Little Endian

Body:
C# 50 49 bytes

Works, but has to be marked as unsafe

char i(){var a=0x0001;return*(byte*)&a>0?'L':'B';}

Updated:

unsafe char i(){int a=1;return"BL"[*(byte*)&a];}


答:
CJam, <s>19</s> 18 bytes

```<code>XXri{_($2$$+}*]-3=
</code>```

Try it online!

Uses the iterative approach.

Title: Hofstadter Q-sequence

Body:
CJam, <s>19</s> 18 bytes

XXri{_($2$$+}*]-3=

Try it online!

Uses the iterative approach.


答:
05AB1E, 29 bytes

An iterative solution.

```<code>XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è
</code>```

Try it online

Title: Hofstadter Q-sequence

Body:
05AB1E, 29 bytes

An iterative solution.

XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è

Try it online


答:
APL, 20 bytes

```<code>{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
</code>```

Explanation:

```<code>{⍵≤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
</code>```

Title: Hofstadter Q-sequence

Body:
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


问:
Prime Wednesdays

Prime Wednesdays

Your task is to count the number of Wednesdays that fall on a prime day of the month in a particular year. For instance, 7-13-16 is a prime Wednesday. For consistency use the Gregorian calendar for all dates.

Input

The input to your program/function will be a year (eg 2016) and is flexible. The year will be an integer between 1912 and 2233 inclusive.

Output

The output is also flexible and should be the number of prime Wednesdays (eg 18).

Scoring

This is code-golf so shortest code in bytes wins!

Test Cases

input     -> output

  --------------------

  1912  ->   19

  1914  ->   16

  1984  ->   17

  1996  ->   19

  2063  ->   19

  2150  ->   16

  2199  ->   18

  2233  ->   18

Title: Prime Wednesdays

Body:
JavaScript ES6, <s>187</s> <s>182</s> <s>181</s> 179 bytes

179 Swapped in a for-loop for the while-loop

z=y=>{D=new Date("1/3/1912");N=0;a=()=>D.getFullYear();b=()=>D.getDate();c=()=>D.setDate(b()+7);for(;a()<=y;c())N+=y-a()?0:-1<[2,3,5,7,11,13,17,19,23,29,31].indexOf(b());return N}

181 Compacted the ternary

z=y=>{D=new Date("1/3/1912");N=0;a=()=>D.getFullYear();b=()=>D.getDate();c=()=>D.setDate(b()+7);while(a()<=y){N+=y-a()?0:-1<[2,3,5,7,11,13,17,19,23,29,31].indexOf(b());c()}return N}

182 Combined the two loops

z=y=>{D=new Date("1/3/1912");N=0;a=()=>D.getFullYear();b=()=>D.getDate();c=()=>D.setDate(b()+7);while(a()<=y){N+=a()==y?-1<[2,3,5,7,11,13,17,19,23,29,31].indexOf(b()):0;c()}return N}

187

z=y=>{D=new Date("1/3/1912");N=0;a=()=>D.getFullYear();b=()=>D.getDate();c=()=>D.setDate(b()+7);while(a()<y)c();for(;a()==y;c())N+=-1<[2,3,5,7,11,13,17,19,23,29,31].indexOf(b());return N}


答:
Bash (and other unix shells), 32 (33) bytes

First and second attempt:

```<code>case `echo|od` in *5*)echo B;;*)echo L;;esac # portable
[[ `echo|od` =~ 5 ]]&&echo B||echo L         # non-portable
</code>```

Thanks to Dennis, shorter version:

```<code>od<<<a|grep -q 5&&echo L||echo B  # non-portable
echo|od|grep -q 5&&echo B||echo L # portable
</code>```

The echo utility outputs a newline, with hex value 0A, and no other output. For <<<a it is 61 0A.

The od utility, by default, interprets the input as two-byte words, zero-padded if the number of bytes is odd, and converts to octal. This results in the output of echo being interpred as 0A 00, which is converted to 005000 as big-endian or 000012 in little-endian. 61 0A becomes 005141 in little-endian and 060412 in big-endian. The full output of od also includes address and size data meaning we cannot use 0, 1, or 2 for the test.

The command is well-defined to expose the system's endianness. From the standard:

The byte order used when interpreting numeric values is implementation-defined, but shall correspond to the order in which a constant of the corresponding type is stored in memory on the system.

Compatibility notes

I am not certain if putting echo|od in backquotes with no double quotes around them [which results in a three-word argument to case] is supported on all systems. I am not certain if all systems support shell scripts with no terminating newline. I am mostly certain but not 100% of the behavior of od with adding the padding byte on big-endian systems. If needed, echo a can be used for the portable versions. All of the scripts work in bash, ksh, and zsh, and the portable ones work in dash.

Title: Big or Little Endian

Body:
Write a program or function that outputs an L if run on a little endian architecture or a B if run on a big endian architecture. Lower case output l or b is also acceptable.

There is no input.

Scoring is code golf, so the code with the fewest bytes wins.

Edit: As per the comments below, I am clarifying that the entry must be able to run on either architecture.

I believe that there is only one answer that this affects, and that answer has clearly indicated that this is the case.

Body:
Bash (and other unix shells), 32 (33) bytes

First and second attempt:

case `echo|od` in *5*)echo B;;*)echo L;;esac # portable
[[ `echo|od` =~ 5 ]]&&echo B||echo L         # non-portable

Thanks to Dennis, shorter version:

od<<<a|grep -q 5&&echo L||echo B  # non-portable
echo|od|grep -q 5&&echo B||echo L # portable

The echo utility outputs a newline, with hex value 0A, and no other output. For <<<a it is 61 0A.

The od utility, by default, interprets the input as two-byte words, zero-padded if the number of bytes is odd, and converts to octal. This results in the output of echo being interpred as 0A 00, which is converted to 005000 as big-endian or 000012 in little-endian. 61 0A becomes 005141 in little-endian and 060412 in big-endian. The full output of od also includes address and size data meaning we cannot use 0, 1, or 2 for the test.

The command is well-defined to expose the system's endianness. From the standard:

The byte order used when interpreting numeric values is implementation-defined, but shall correspond to the order in which a constant of the corresponding type is stored in memory on the system.

Compatibility notes

I am not certain if putting echo|od in backquotes with no double quotes around them [which results in a three-word argument to case] is supported on all systems. I am not certain if all systems support shell scripts with no terminating newline. I am mostly certain but not 100% of the behavior of od with adding the padding byte on big-endian systems. If needed, echo a can be used for the portable versions. All of the scripts work in bash, ksh, and zsh, and the portable ones work in dash.


答:
JavaScript (ES6), 135 bytes

```<code>g=(a,n,y,r)=>n>0?y>0&&a.map((x,i)=>g(a.slice(i),n-1,y-x,[...r,x])):n|y||console.log(r)
(a,n,y)=>g(a,n-a.length,a.reduce((y,x)=>y-x,y),a)
</code>```

Body:
JavaScript (ES6), 135 bytes

g=(a,n,y,r)=>n>0?y>0&&a.map((x,i)=>g(a.slice(i),n-1,y-x,[...r,x])):n|y||console.log(r)
(a,n,y)=>g(a,n-a.length,a.reduce((y,x)=>y-x,y),a)


答:
JavaScript (ES6), 66 bytes

```<code>n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])
</code>```

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).

Title: Hofstadter Q-sequence

Body:
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).


问:
Golf all the 16 logic gates with 2 inputs and 1 output!
For example, the gate A and B is a logic gate with 2 inputs and 1 output.

There are exactly 16 of them, because:

each logic gate takes two inputs, which can be truthy or falsey, giving us 4 possible inputs

of the 4 possible inputs, each can have an output of truthy and falsey

therefore, there are 2^4 possible logic gates, which is 16.

Your task is to write 16 programs/functions which implement all of them separately.

Your functions/programs must be independent.

They are valid as long as they output truthy/falsey values, meaning that you can implement A or B in Python as lambda a,b:a+b, even if 2 is produced for A=True and B=True.

Score is total bytes used for each function/program.

List of logic gates

0,0,0,0 (false)

0,0,0,1 (and)

0,0,1,0 (A and not B)

0,0,1,1 (A)

0,1,0,0 (not A and B)

0,1,0,1 (B)

0,1,1,0 (xor)

0,1,1,1 (or)

1,0,0,0 (nor)

1,0,0,1 (xnor)

1,0,1,0 (not B)

1,0,1,1 (B implies A)

1,1,0,0 (not A)

1,1,0,1 (A implies B)

1,1,1,0 (nand)

1,1,1,1 (true)

Where the first number is the output for A=false, B=false,
the second number is the output for A=false, B=true,
the third number is the output for A=true, B=false,
the fourth number is the output for A=true, B=true.

Leaderboard

var QUESTION_ID=82938,OVERRIDE_USER=48934;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:\.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;```
<pre class="snippet-code-css lang-css prettyprint-override"><code>body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}</code>```

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

```

答:
C, 164 Bytes

```<code>#define r (a,b){return
c r 0;}d r a&b;}e r a>b;}f r a;}g r a<b;}h r b;}i r a^b;}j r a|b;}k r !b>a;}l r a==b;}m r !b;}n r !b|a;}o r !a;}p r !a|b;}q r !b|!a;}s r 1;}
</code>```

Body:
C, 164 Bytes

#define r (a,b){return
c r 0;}d r a&b;}e r a>b;}f r a;}g r a<b;}h r b;}i r a^b;}j r a|b;}k r !b>a;}l r a==b;}m r !b;}n r !b|a;}o r !a;}p r !a|b;}q r !b|!a;}s r 1;}


答:
Pyth, 16 bytes

```<code>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
</code>```

Defines a function y.

Try it online
(added yMS20 to print the first 20 values)

Title: Hofstadter Q-sequence

Body:
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)


答:
Haskell, <s>35</s> 33 bytes

```<code>a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)
</code>```

Defines a function a.

Title: Hofstadter Q-sequence

Body:
Haskell, <s>35</s> 33 bytes

a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)

Defines a function a.


答:
Forth, 76 bytes

I finally got it working!

```<code>: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;
</code>```

Try it online

Explanation:

```<code>: 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 ;
</code>```

Try it online (slightly un-golfed from above)

Unfortunately, mutual recursion is a bit too wordy to use for golfing.

Title: Hofstadter Q-sequence

Body:
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.


问:
Write the fastest Fibonacci
This is yet another challenge about the Fibonacci numbers.

The goal is to compute the 20'000'000th Fibonacii number as fast as possible. The decimal output is about 4 MiB large; it starts with:

28543982899108793710435526490684533031144309848579

The MD5 sum of the output is

fa831ff5dd57a830792d8ded4c24c2cb

You have to submit a program that calculates the number while running and puts the result to stdout. The fastest program, as measured on my own machine, wins.

Here are some additional rules:

You have to submit the source code and a binary runnable on an x64 Linux

The source code must be shorter than 1 MiB, in case of assembly it is also acceptable if only the binary is that small.

You must not include the number to be computed in your binary, even in a disguised fashion. The number has to be calculated at runtime.

My computer has two cores; you are allowed to use parallelism

I took a small implementation from the Internet which runs in about 4.5 seconds. It should not be very difficult to beat this, assuming that you have a good algorithm.

答:
C, naive algorithm

Was curious, and I hadn't used gmp before... so:

```<code>#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main(int argc, char *argv[]){
    int n = (argc>1)?atoi(argv[1]):0;

    mpz_t temp,prev,result;
    mpz_init(temp);
    mpz_init_set_ui(prev, 0);
    mpz_init_set_ui(result, 1);

    for(int i = 2; i <= n; i++) {
        mpz_add(temp, result, prev);
        mpz_swap(temp, result);
        mpz_swap(temp, prev);
    }

    printf("fib(%d) = %s\n", n, mpz_get_str (NULL, 10, result));

    return 0;
}
</code>```

fib(1 million) takes about 7secs... so this algorithm won't win the race.

Title: Write the fastest Fibonacci

Body:
C, naive algorithm

Was curious, and I hadn't used gmp before... so:

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main(int argc, char *argv[]){
    int n = (argc>1)?atoi(argv[1]):0;

    mpz_t temp,prev,result;
    mpz_init(temp);
    mpz_init_set_ui(prev, 0);
    mpz_init_set_ui(result, 1);

    for(int i = 2; i <= n; i++) {
        mpz_add(temp, result, prev);
        mpz_swap(temp, result);
        mpz_swap(temp, prev);
    }

    printf("fib(%d) = %s\n", n, mpz_get_str (NULL, 10, result));

    return 0;
}

fib(1 million) takes about 7secs... so this algorithm won't win the race.