问:
The Versatile Integer Printer
Write a piece of code that is executable in at least three different languages. The code must output the integer 1 in language number one, 2 in language number two, 3 in language number three etc.

Rules:

The output must be only the integer, but trailing newlines are OK.

The code can't take input of any kind

Different major versions of the same language are considered unique. So, your code can be executable in Python 2 and Python 3, however Python 2.5 and Python 2.7 are not considered unique.

You may use a new language if and only if it has an esolang/wiki article, available interpreter and documentation, and has been used by at least two users on PPCG prior to using it in this challenge. It must also adhere to these 4 rules.

The score of your submission is the number of bytes in your code divided by the number of languages it can run in cubed. So, a 54 byte solution that is executable in 3 languages will have a score of 2:

```<code>54 / 3^3 = 2
</code>```

Lower score is better.

答:
5 languages, 18 bytes / 5^3 = 0.144

Ouroboros, Pip, QBasic, Foo, and Pyth

```<code>5'"4"()"
1?3'@n()2
</code>```

1. Ouroboros

Each line of the program represents a snake eating its tail.

Snake 1

Push 5, ' is a no-op, push 52 (ASCII code of "4"). ( causes the snake to pop a number and eat that many characters of its tail. Since this results in swallowing the instruction pointer (and the entire snake), execution halts.

Snake 2

Push 1, push a random number (?), push 3, ' is a no-op. @ rotates the 1 to the top of the stack and n outputs it as a number, leaving the 3 on top of the stack. Then ( eats this many characters from the end of the snake, swallowing the instruction pointer and halting.

You can run this program online in the Stack Snippet interpreter here.

2. Pip

Most of the program consists of expressions which are evaluated and discarded:

5

'" (character literal)

4

"()"

1?3'@ (ternary expression)

n (variable, = newline)

() (nil)

Finally, the last expression, 2, is printed.

3. QBasic

Everything after ' is a comment. The first line thus boils down to 5, a line number. On the second line, 1 is a line number and ?3 is a shortcut for PRINT 3.

(Apparently having line numbers out of order isn't a problem, though it would be easy to fix if it were.)

4. Foo

Almost everything is no-ops. "4" prints 4. The parentheses (x2) are a loop that runs until the current array cell is zero, which is true immediately and the loop exits. @, when not followed by a number, takes the value of the current array cell (initialized to 0) and pushes it to the stack.

I'm not entirely sure how the second, unmatched " is supposed to be handled. The online version seems to add a newline to the output, which the rules of the challenge allow.

5. Pyth

5 is output. Then the program encounters '"4", which tries to read from a file named 4. As long as no such file exists, I think this should terminate the program with an error. (The online version says name 'open' is not defined--I assume because opening files isn't allowed online.)

The stray " at the end of line 1 ensures that line 2 doesn't cause a syntax error before execution.

Title: The Versatile Integer Printer

Body:
5 languages, 18 bytes / 5^3 = 0.144

Ouroboros, Pip, QBasic, Foo, and Pyth

5'"4"()"
1?3'@n()2

1. Ouroboros

Each line of the program represents a snake eating its tail.

Snake 1

Push 5, ' is a no-op, push 52 (ASCII code of "4"). ( causes the snake to pop a number and eat that many characters of its tail. Since this results in swallowing the instruction pointer (and the entire snake), execution halts.

Snake 2

Push 1, push a random number (?), push 3, ' is a no-op. @ rotates the 1 to the top of the stack and n outputs it as a number, leaving the 3 on top of the stack. Then ( eats this many characters from the end of the snake, swallowing the instruction pointer and halting.

You can run this program online in the Stack Snippet interpreter here.

2. Pip

Most of the program consists of expressions which are evaluated and discarded:

5

'" (character literal)

4

"()"

1?3'@ (ternary expression)

n (variable, = newline)

() (nil)

Finally, the last expression, 2, is printed.

3. QBasic

Everything after ' is a comment. The first line thus boils down to 5, a line number. On the second line, 1 is a line number and ?3 is a shortcut for PRINT 3.

(Apparently having line numbers out of order isn't a problem, though it would be easy to fix if it were.)

4. Foo

Almost everything is no-ops. "4" prints 4. The parentheses (x2) are a loop that runs until the current array cell is zero, which is true immediately and the loop exits. @, when not followed by a number, takes the value of the current array cell (initialized to 0) and pushes it to the stack.

I'm not entirely sure how the second, unmatched " is supposed to be handled. The online version seems to add a newline to the output, which the rules of the challenge allow.

5. Pyth

5 is output. Then the program encounters '"4", which tries to read from a file named 4. As long as no such file exists, I think this should terminate the program with an error. (The online version says name 'open' is not defined--I assume because opening files isn't allowed online.)

The stray " at the end of line 1 ensures that line 2 doesn't cause a syntax error before execution.


问:
Subsequence Substitution
Most languages come with a built-in to search a string for all occurrences of a given substring and replace those with another. I don't know of any language that generalises this concept to (not necessarily contiguous) subsequences. So that's your task in this challenge.

The input will consist of three strings A, B and C, where B and C are guaranteed to be of the same length. If B appears as a subsequence in A it should be replaced with C. Here is a simple example:

```<code>A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345
</code>```

It would be processed like this:

```<code>abcdefghijklmnopqrstuvwxyz
      ||      |   ||
abcdef12ijklmn3pqr45uvwxyz
</code>```

If there are several ways to find B as a subsequence, you should greedily replace the left-most one:

```<code>A: abcdeedcba
B: ada
C: BOB

Result:   BbcOeedcbB
and NOT:  BbcdeeOcbB
</code>```

The same applies if B could be found in multiple disjoint places:

```<code>A: abcdeedcbaabcde
B: ed
C: 12

Result:   abcd1e2cbaabcde
and NOT:  abcd112cbaabc2e (or similar)
</code>```

When B does not appear in A, you should output A unchanged.

Rules

As stated above, take three strings A, B and C as input and replace the left-most occurrence of B as a subsequence in A with C, if there is any.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may take the three strings in any consistent order which you should specify in your answer. You may assume that B and C have the same length. All strings will only contain alphanumeric characters.

Standard code-golf rules apply.

Test Cases

Each test case is four lines: A, B, C followed by the result.

```<code>abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

abcdeedcba
ada
BOB
BbcOeedcbB

abcdeedcbaabcde
ed
12
abcd1e2cbaabcde

121
121
aBc
aBc

abcde
acb
123
abcde

ABC
ABCD
1234
ABC

012345678901234567890123456789
42
TT
0123T5678901T34567890123456789

edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba

edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba

daccdedca
ace
cra
dcrcdadca

aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca

aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44
</code>```

Leaderboard

The Stack Snippet at the bottom of this post generates leaderboards 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>```

/* Configuration */

var QUESTION_ID = 77719; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://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 "http://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,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\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,
      });
    else console.log(body);
  });

  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;
    lang = jQuery(''+lang+'').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) 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/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

```

答:
Julia, <s>62</s> <s>59</s> 58 bytes

```<code>f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)
</code>```

I/O is in form of character arrays.

Verification

```<code>julia> f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)
f (generic function with 2 methods)

julia> F(s,p,r)=join(f([s...],[p...],[r...])) # string/char array conversion
F (generic function with 1 method)

julia> F("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> F("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"
</code>```

ContentLicense: CC BY-SA 3.0

Title: Subsequence Substitution

Body:
Julia, <s>62</s> <s>59</s> 58 bytes

f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)

I/O is in form of character arrays.

Verification

julia> f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)
f (generic function with 2 methods)

julia> F(s,p,r)=join(f([s...],[p...],[r...])) # string/char array conversion
F (generic function with 1 method)

julia> F("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> F("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"


问:
The Luhn algorithm for verifying credit card numbers, etc

Challenge

Write the shortest program or function to calculate the Luhn Algorithm for verifying (credit card) numbers.

Luhn algorithm explained

From RosettaCode, this algorithm for the purposes of this challenge is specified as such, with the example input of 49927398716:

```<code>Reverse the digits, make an array:
    6, 1, 7, 8, 9, 3, 7, 2, 9, 9, 4
Double the numbers in odd indexes:
    6, 2, 7, 16, 9, 6, 7, 4, 9, 18, 4
Sum the digits in each number:
    6, 2, 7, 7, 9, 6, 7, 4, 9, 9, 4
Sum all of the numbers:
    6 + 2 + 7 + 7 + 9 + 6 + 7 + 4 + 9 + 9 + 4 = 70
If the sum modulo 10 is 0, then the number is valid:
    70 % 10 = 0 => valid
</code>```

IO Rules

Input: A string or number (your choice), in your language's input/output format of choice

Output: A truthy or falsy value, respectively, indicating whether or not the input is valid according to the test above.

Notes / Tips

Try not to accidentally post your own credit card or account numbers, if you use them to test :)

If the input is invalid and impossible to process with the specified algorithm (i.e, too short to work with), you can do whatever you want, including blow up my computer.

However, the previous bullet does not mean that your language can do whatever it wants with Numbers that are too large for it to handle. If your language isn't capable of handling a test case, then consider taking a string as input.

Examples

The following examples were validated with this Python script; if you think one is wrong or have a question, just ping @cat.

```<code>49927398716      True
49927398717      False
1234567812345670 True
1234567812345678 False
79927398710      False
79927398711      False
79927398712      False
79927398713      True
79927398714      False
79927398715      False
79927398716      False
79927398717      False
79927398718      False
79927398719      False
374652346956782346957823694857692364857368475368 True
374652346956782346957823694857692364857387456834 False
8 False **
0 True  **
</code>```

** according to the Python implementation, but you may do anything because these are too short to be eligible by a strict adherence to the specification.

If any of the above invalidates existing answers (though I believe that should not be possible), then those answers are stil valid. However, new answers, in order to be valid, should follow the specification above.

Leaderboard

var QUESTION_ID=22,OVERRIDE_USER=73772;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+)(?=[^\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

```

答:
JavaScript (ES6), 61 bytes

Sum of digits of 2*n is 2*n if n in 0..4, 2*n-9 if n in 5..9. That said, all the sum can be computed in one step.

s=>!([...s].reduceRight((t,d)=>t-d-i++%2*(d>4?d-9:d),i=0)%10)
```

ContentLicense: CC BY-SA 4.0


问:
Linear Independence
Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0,  a1v1 + a2v2 + ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -> output):

```<code>[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False
</code>```

答:
Julia, <s>28</s> 27 bytes

```<code>X->X==[]||eigmin(X'X)>eps()
</code>```

This is an anonymous function that accepts a 2-dimensional array with the vectors as columns and returns a boolean. To call it, assign it to a variable.

For any real, non-singular matrix X, the square matrix XTX is positive definite. Since a matrix is non-singular if and only if all of its column vectors are linearly independent and non-singular implies XTX is positive definite, we can declare the vectors to be linearly independent if the product is positive definite. A matrix is positive definite if and only if all of its eigenvalues are strictly positive, or equivalently when its smallest eigenvalue is strictly positive.

So for an input matrix X, we construct XTX and get the minimum eigenvalue using eigmin(X'X). To account for floating point error, we check this against the machine precision, eps, rather than 0, to declare positivity. Since we also want empty input to return true, we can simply add the condition X==[].

Saved 1 byte thanks to Dennis!

Title: Linear Independence

Body:
Julia, <s>28</s> 27 bytes

X->X==[]||eigmin(X'X)>eps()

This is an anonymous function that accepts a 2-dimensional array with the vectors as columns and returns a boolean. To call it, assign it to a variable.

For any real, non-singular matrix X, the square matrix XTX is positive definite. Since a matrix is non-singular if and only if all of its column vectors are linearly independent and non-singular implies XTX is positive definite, we can declare the vectors to be linearly independent if the product is positive definite. A matrix is positive definite if and only if all of its eigenvalues are strictly positive, or equivalently when its smallest eigenvalue is strictly positive.

So for an input matrix X, we construct XTX and get the minimum eigenvalue using eigmin(X'X). To account for floating point error, we check this against the machine precision, eps, rather than 0, to declare positivity. Since we also want empty input to return true, we can simply add the condition X==[].

Saved 1 byte thanks to Dennis!


问:
Sort an Integer List

The Challenge

It's quite simple really, sort a list of numbers.

Details

You must sort a list of numbers in ascending order, without using any built-in sorting functions/libraries/etc (i.e. list.sort() in Python).

Input/output can be done in any method you choose, as long as it is human readable.

Standard loopholes are disallowed as always.

Shortest code in bytes wins.

You must explain/list what sort method you used (Bubble, Insertion, Selection, etc.)

Input will not contain duplicates.

Sample Input/Output

Input: 99,-2,53,4,67,55,23,43,88,-22,36,45

Output: -22,-2,4,23,36,43,45,53,55,67,88,99

Note: A near direct opposite of Sort a List of Numbers

答:
Ruby, 22 bytes

A quick permutation sort. Runs in O(n!) space and time.

```<code>->a{a.permutation.min}
</code>```

Title: Sort an Integer List

Body:
Ruby, 22 bytes

A quick permutation sort. Runs in O(n!) space and time.

->a{a.permutation.min}


问:
Winnable Solitaire Mancala Boards
Mancala is the name of a family of board games that usually involve a series of cups filled with beads that the players manipulate. This challenge will use a specific rule set for a solitaire variant of the game.

The board consists of a "basket" at one end, followed by an infinite number of cups, numbered starting from 1. Some of the cups will have some number of beads in them. If the nth cup has exactly n beads in it, you may "sow" the beads from it. Sowing means to take all n beads out of the cup, then deposit them one at a time in each cup towards the basket. The last bead will go into the basket. The player wins when all of the beads on the board are in the basket.

Clearly, there are many boards which are not winnable, such as if there is exactly one bead in the second cup. There are no legal plays because all the cups with 0 beads cannot be sown, and the second cup does not have enough beads to be sown. This is obviously no fun, so your task will be to create winnable boards.

Task

Given a positive integer representing a number of beads output a list of non-negative integers representing the number of beads that should be put in each cup to make a winnable board as described above. This list should not contain any trailing zeroes.

For any given number of beads, there is always exactly one winnable board configuration.

Demonstration

This is a demonstration of how to play the winnable board for and input of 4. The winnable board is [0, 1, 3]. We start with the only available move, sowing the beads from the third cup to get [1, 2, 0]. Now we actually have a choice, but the only correct one is sowing the first cup, getting: [0, 2, 0]. Then we sow the second cup yielding [1, 0, 0] and finally we sow the first cup again to get all empty cups.

Test cases:

```<code>1 => [1]
2 => [0, 2]
3 => [1, 2]
4 => [0, 1, 3]
5 => [1, 1, 3]
6 => [0, 0, 2, 4]
7 => [1, 0, 2, 4]
8 => [0, 2, 2, 4]
9 => [1, 2, 2, 4]
10 => [0, 1, 1, 3, 5]
11 => [1, 1, 1, 3, 5]
12 => [0, 0, 0, 2, 4, 6]
13 => [1, 0, 0, 2, 4, 6]
14 => [0, 2, 0, 2, 4, 6]
15 => [1, 2, 0, 2, 4, 6]
16 => [0, 1, 3, 2, 4, 6]
17 => [1, 1, 3, 2, 4, 6]
18 => [0, 0, 2, 1, 3, 5, 7]
19 => [1, 0, 2, 1, 3, 5, 7]
20 => [0, 2, 2, 1, 3, 5, 7]
</code>```

Big thanks to PeterTaylor for coming up with a program to generate test cases!

答:
CJam (21 bytes)

```<code>M{_0+0#_Wa*\)+.+}ri*`
</code>```

Online demo

Explanation

I independently derived the "unplaying" technique mentioned in this paper. We prove by induction that there is exactly one winning board for a given number of beads.

Base case: with 0 beads, the only winning board is the empty one.

Inductive step: if we sow from cup k then at the next move cup k will be empty and every cup nearer the basket will contain at least one bead. Therefore we can find the unique winning board with n beads from the winning board with n-1 beads by looking for the lowest numbered empty cup, taking one bead from the basket and one from each cup below that empty cup, and placing them all in the empty cup.

Dissection

```<code>M           e# Start with an empty board
{           e# Loop
  _0+0#     e#   Find position of first 0 (appending to ensure that there is one)
  _Wa*      e#   Make array of that many [-1]s
  \)+       e#   Append the index plus 1 (since board is 1-indexed)
  .+        e#   Pointwise addition
}
ri*         e# Read integer from stdin and execute loop that many times
`           e# Format for display
</code>```

Title: Winnable Solitaire Mancala Boards

Body:
CJam (21 bytes)

M{_0+0#_Wa*\)+.+}ri*`

Online demo

Explanation

I independently derived the "unplaying" technique mentioned in this paper. We prove by induction that there is exactly one winning board for a given number of beads.

Base case: with 0 beads, the only winning board is the empty one.

Inductive step: if we sow from cup k then at the next move cup k will be empty and every cup nearer the basket will contain at least one bead. Therefore we can find the unique winning board with n beads from the winning board with n-1 beads by looking for the lowest numbered empty cup, taking one bead from the basket and one from each cup below that empty cup, and placing them all in the empty cup.

Dissection

M           e# Start with an empty board
{           e# Loop
  _0+0#     e#   Find position of first 0 (appending to ensure that there is one)
  _Wa*      e#   Make array of that many [-1]s
  \)+       e#   Append the index plus 1 (since board is 1-indexed)
  .+        e#   Pointwise addition
}
ri*         e# Read integer from stdin and execute loop that many times
`           e# Format for display


问:
Home improvement for the Minotaur

Home improvement for the Minotaur

The cretan labyrinth is quite easy to draw. Just start with a symmetric shape (here in red). Let us call all the endpoints of those lines 'nodes'. Then you begin drawing the arches (black): The first one alway begins in the top middle node and connects to the node next to it on the right side, then the two nodes closest to the previous arch are connected. This is repeated untill all nodes are covered.

Now we can generalize this concept: We can easily generate new initial patterns by adding more L shapes. I enumerated the initial shapes as follows:

The most left pattern will produce a cretan labyrinth of degree 0. The next one will create a cretan labyrinth of degree 1 (the original one) etc.

Task

Given a nonnegative integer n, your program should output the ascii representation of a cretan labyrinth of degree n, that is shown in the following examples. Trailing spaces/newlines do not matter. You have to include a short explanation of how your code works.

Examples

The output for the original cretan labyrith (degree 1) is following:

```<code>+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |
| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ |
              +---------------+

</code>```

Initial pattern:

```<code>+ | | | +
--+ | +--
----+----
--+ | +--
+ | | | +
</code>```

The cretian labyrinth of degree 0 should look like so:

```<code>+-------------+
| +---------+ |
| | +-----+ | |
| | | +-+ | | |
| | + | + | | |
| +---+---+ | |
+---+ | +---+ |
      +-------+

</code>```

Initial pattern:

```<code>+ | +
--+--
+ | +
</code>```

答:
Python 3.5, 703 695 676 648 587 581 542 535 500 486 462 431 423 411 bytes:

(Thanks to @flawr for advice on saving 55 bytes (486 -> 431)!)

def j(r):R=range;Z=zip;B=r+r+2;P,M='+-';X='| ';q=[*Z(R(0,B-1,2),R(B-1,0,-2))];L=r+1;A=2+r;print('\n'.join([X*w+P+M*v+P+' |'*w for v,w in Z(R(4*L*4-3,0,-4),R(4*L))]+[X*g+P*o+M*k+u+M*k+P*o+' |'*-~g for g,o,k,u in Z([*R(4*L-A,0,-1),*R(4*L-A)],[0]+[1]*(3*r+2),[0,*R(1,4*L,2),*R(4*L+1,11*r,2)],[M*y+'+ '+X*b+P+M*y for y,b in q]+[M*B+P+M*B]+[M*y+'+ '+X*b+P+M*y for y,b in q[::-1]+q[1:]])]+[' '*(8*r+6)+P+M*(8*r+7)+P]))
```

<p>Not very much of a contender for the title, but I still gave it a shot, and it works perfectly. I will try to shorten it more over time where I can, but for now, I love it and could not be happier.</p>

<p>Try it online! (Ideone) (May look a little bit different on here because of apparent online compiler limitations. However, it's still very much the same.)</p>

<h1>Explanation:</h1>

<p>For the purposes of this explanation, let's assume that the above function was executed with the input, <code>r</code>, being equal to <code>1</code>. That being said, basically what's happening, step-by-step, is...</p>

<ol>
<li><p><code>q=[*Z(R(0,B-1,2),R(B-1,0,-2))]</code></p>

<p>A zip object, <code>q</code>, is created with 2 range objects, one consisting of every second integer in the range <code>0=>r+r+1</code> and another consisting of every second integer in the range <code>r+r+1=>0</code>. This is because every starting pattern of a cretan labyrinth of a specific degree will always have an even number of <code>-</code> in each line. For instance, for a cretan labyrinth of degree <code>1</code>, <code>r+r+1</code> equals <code>3</code>, and thus, its pattern will always start with <code>0</code> dashes, followed by another line with <code>4</code> (2+2) dashes. This zip object will be used for the first <code>r+1</code> lines of the labyrinth's pattern.  </p>

<p><strong>Note:</strong> The <em>only</em> reason <code>q</code> is a list and separated from the rest is because <code>q</code> is referenced a few times and subscripted, and to save a lot of repetition and allow subscripting, I simply created a zip object <code>q</code> in the form of a list.</p></li>
<li><p><code>print('\n'.join([X*w+P+M*v+P+' |'*w for v,w in Z(R(4*L*4-3,0,-4),R(4*L))]+[X*g+P*o+M*k+u+M*k+P*o+' |'*-~g for g,o,k,u in Z([*R(4*L-A,0,-1),*R(4*L-A)],[0]+[1]*(3*r+2),[0,*R(1,4*L,2),*R(4*L+1,11*r,2)],[M*y+'+ '+X*b+P+M*y for y,b in q]+[M*B+P+M*B]+[M*y+'+ '+X*b+P+M*y for y,b in q[::-1]+q[1:]])]+[' '*(8*r+6)+P+M*(8*r+7)+P]))</code></p>

<p>This is the last step, in which the labyrinth is built and put together. Here, three lists, the first consisting of the top <code>4*r+1</code> lines of the labyrinth, the second consisting of the middle <code>3*r+3</code> lines of the labyrinth, and the last list consisting of the very last line of the labyrinth are joined together, with line breaks (<code>\n</code>) into one long string. Finally, this one huge string consisting of the entire labyrinth is printed out. Let us go more in depth into what these 2 lists and 1 string actually contain:</p>

<ul>
<li><p>The 1st list, in which another zipped object is used in list comprehension to create each line one by one, with leading <code>|</code>or <code>+</code> symbols, an odd number of dashes in the range <code>0=>4*(r+1)</code>, trailing <code>|</code> or <code>+</code> symbols, and then a newline (<code>\n</code>). In the case of a degree <code>1</code> labyrinth, this list returns:</p>

```+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |
```</li>
<li><p>The 2nd list, which consists of a zip object containing 4 lists, and each list corresponds to the number of leading/trailing <code>|</code> symbols, the number of <code>+</code> symbols, the number of dashes, and finally, the last list, which contains the first <code>r+1</code> lines of the pattern created according to zip object <code>q</code>, the line in the middle of the pattern (the one with no <code>|</code>), and the last <code>r+2</code> lines of the symmetrical pattern. In this specific case, the last list used in this list's zip object would return:</p>

```+ | | | +
--+ | +--
----+----
--+ | +--
+ | | | +
--+ | +--  <- Last line created especially for use in the middle of the labyrinth itself.
```

<p>And therefore, in the case of a 1 degree labyrinth, this entire list would return:</p>

```| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ | <- Here is where the extra line of the pattern is used.
```</li>
<li><p>This final list, in which the last line is created. Here, the first segment (the one before the first space) length of the last line of list <code>P</code> number of spaces are created. Then, the length of the last segment (the ending segment) of the same line + 4 number of dashes are added, all of which are preceded and followed by a single <code>+</code> symbol. In the case of a degree 1 labyrinth, this last list returns:</p>

```              +---------------+
```</li>
</ul>

<p>After joining all this together, this step finally returns the completed labyrinth. In the case of a 1 degree labyrinth, it would finally return this:</p>

```+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |
| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ |
              +---------------+
```

Title: Home improvement for the Minotaur

Body:
Python 3.5, 703 695 676 648 587 581 542 535 500 486 462 431 423 411 bytes:

(Thanks to @flawr for advice on saving 55 bytes (486 -> 431)!)

def j(r):R=range;Z=zip;B=r+r+2;P,M='+-';X='| ';q=[*Z(R(0,B-1,2),R(B-1,0,-2))];L=r+1;A=2+r;print('\n'.join([X*w+P+M*v+P+' |'*w for v,w in Z(R(4*L*4-3,0,-4),R(4*L))]+[X*g+P*o+M*k+u+M*k+P*o+' |'*-~g for g,o,k,u in Z([*R(4*L-A,0,-1),*R(4*L-A)],[0]+[1]*(3*r+2),[0,*R(1,4*L,2),*R(4*L+1,11*r,2)],[M*y+'+ '+X*b+P+M*y for y,b in q]+[M*B+P+M*B]+[M*y+'+ '+X*b+P+M*y for y,b in q[::-1]+q[1:]])]+[' '*(8*r+6)+P+M*(8*r+7)+P]))

Not very much of a contender for the title, but I still gave it a shot, and it works perfectly. I will try to shorten it more over time where I can, but for now, I love it and could not be happier.

Try it online! (Ideone) (May look a little bit different on here because of apparent online compiler limitations. However, it's still very much the same.)

Explanation:

For the purposes of this explanation, let's assume that the above function was executed with the input, r, being equal to 1. That being said, basically what's happening, step-by-step, is...

q=[*Z(R(0,B-1,2),R(B-1,0,-2))]

A zip object, q, is created with 2 range objects, one consisting of every second integer in the range 0=>r+r+1 and another consisting of every second integer in the range r+r+1=>0. This is because every starting pattern of a cretan labyrinth of a specific degree will always have an even number of - in each line. For instance, for a cretan labyrinth of degree 1, r+r+1 equals 3, and thus, its pattern will always start with 0 dashes, followed by another line with 4 (2+2) dashes. This zip object will be used for the first r+1 lines of the labyrinth's pattern.

Note: The only reason q is a list and separated from the rest is because q is referenced a few times and subscripted, and to save a lot of repetition and allow subscripting, I simply created a zip object q in the form of a list.

print('\n'.join([X*w+P+M*v+P+' |'*w for v,w in Z(R(4*L*4-3,0,-4),R(4*L))]+[X*g+P*o+M*k+u+M*k+P*o+' |'*-~g for g,o,k,u in Z([*R(4*L-A,0,-1),*R(4*L-A)],[0]+[1]*(3*r+2),[0,*R(1,4*L,2),*R(4*L+1,11*r,2)],[M*y+'+ '+X*b+P+M*y for y,b in q]+[M*B+P+M*B]+[M*y+'+ '+X*b+P+M*y for y,b in q[::-1]+q[1:]])]+[' '*(8*r+6)+P+M*(8*r+7)+P]))

This is the last step, in which the labyrinth is built and put together. Here, three lists, the first consisting of the top 4*r+1 lines of the labyrinth, the second consisting of the middle 3*r+3 lines of the labyrinth, and the last list consisting of the very last line of the labyrinth are joined together, with line breaks (\n) into one long string. Finally, this one huge string consisting of the entire labyrinth is printed out. Let us go more in depth into what these 2 lists and 1 string actually contain:

The 1st list, in which another zipped object is used in list comprehension to create each line one by one, with leading |or + symbols, an odd number of dashes in the range 0=>4*(r+1), trailing | or + symbols, and then a newline (\n). In the case of a degree 1 labyrinth, this list returns:

+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |

The 2nd list, which consists of a zip object containing 4 lists, and each list corresponds to the number of leading/trailing | symbols, the number of + symbols, the number of dashes, and finally, the last list, which contains the first r+1 lines of the pattern created according to zip object q, the line in the middle of the pattern (the one with no |), and the last r+2 lines of the symmetrical pattern. In this specific case, the last list used in this list's zip object would return:

+ | | | +
--+ | +--
----+----
--+ | +--
+ | | | +
--+ | +--  <- Last line created especially for use in the middle of the labyrinth itself.

And therefore, in the case of a 1 degree labyrinth, this entire list would return:

| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ | <- Here is where the extra line of the pattern is used.

This final list, in which the last line is created. Here, the first segment (the one before the first space) length of the last line of list P number of spaces are created. Then, the length of the last segment (the ending segment) of the same line + 4 number of dashes are added, all of which are preceded and followed by a single + symbol. In the case of a degree 1 labyrinth, this last list returns:

              +---------------+

After joining all this together, this step finally returns the completed labyrinth. In the case of a 1 degree labyrinth, it would finally return this:

+-----------------------------+
| +-------------------------+ |
| | +---------------------+ | |
| | | +-----------------+ | | |
| | | | +-------------+ | | | |
| | | | | +---------+ | | | | |
| | | | | | +-----+ | | | | | |
| | | | | | | +-+ | | | | | | |
| | | | | + | | | + | | | | | |
| | | | +---+ | +---+ | | | | |
| | | +-------+-------+ | | | |
| | +-------+ | +-------+ | | |
| +-------+ | | | +-------+ | |
+-----------+ | +-----------+ |
              +---------------+


问:
Tips for golfing in C++
What general tips do you have for golfing in C++?

I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to C++ (e.g. "remove comments" is not an answer). Please post one tip per answer.

(Tips that apply to C as well can be found in Tips for golfing in C - but note that some C tips don't work in C++.  For example, C++ does require function prototypes and return values.)

答: Instead of writing big powers of 10, use e notation. For example, a=1000000000 is longer than a=1e9. This can be extended to other numbers like a=1e9+24 is better than a=1000000024.

Title: Tips for golfing in C++


答:
MATL, 33 bytes

```<code>|ssQt_w2$:GZy1)Z^!2$1!G*Xs!Xa~s3<
</code>```

This uses current release (16.1.0) of the language, which predates the challenge.

Input format is

```<code>[0 1; 2 3]
</code>```

or

```<code>[[0 1];[2 3]]
</code>```

Try it online!

Explanation

This uses only integer opeations, so it is not subject to rounding errors (as long as the involved integers don't exceed 2^52).

It works by applying the definition. It suffices to test for integer scalars a1, a2, ... between −S−1 and S+1, where S is the sum of absolute values of all numbers in the input 2D array. In fact much lower values of S could be used, but this one requires few bytes to compute.

All "combinations" (Cartesian product) of values a1, a2, ...  between −S−1 and S+1 are tested. The input vectors v1, v2, ... are independent iff only one of the linear combinations a1v1+a2v2+... gives a 0 result (namely that for coefficients a1, a2, ... = 0).

```<code>|ssQ    % sum of absolute values of input plus 1
t_w     % duplicate, negate, swap
2$:     % binary range: [-S-1 -S ... S+1]
GZy1)   % push input. Number of rows (i.e. number of vectors), N
Z^      % Cartesian power. Gives (2S+3)×N-column array
!2$1!   % Permute dimensions to get N×1×(2S+3) array
G       % Push input: N×M array
*       % Product, element-wise with broadcast: N×M×(2S+3) array
Xs      % sum along first dimension (compute each linear combination): 1×M×(2S+3)
!       % Transpose: M×1×(2S+3)
Xa~     % Any along first dimension, negate: 1×1×(2S+3). True for 0-vector results
s       % Sum (number of 0-vector results)
2<      % True if less than 2
</code>```

Title: Linear Independence

Body:
Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0,  a1v1 + a2v2 + ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -> output):

```<code>[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False
</code>```

Body:
MATL, 33 bytes

|ssQt_w2$:GZy1)Z^!2$1!G*Xs!Xa~s3<

This uses current release (16.1.0) of the language, which predates the challenge.

Input format is

[0 1; 2 3]

or

[[0 1];[2 3]]

Try it online!

Explanation

This uses only integer opeations, so it is not subject to rounding errors (as long as the involved integers don't exceed 2^52).

It works by applying the definition. It suffices to test for integer scalars a1, a2, ... between −S−1 and S+1, where S is the sum of absolute values of all numbers in the input 2D array. In fact much lower values of S could be used, but this one requires few bytes to compute.

All "combinations" (Cartesian product) of values a1, a2, ...  between −S−1 and S+1 are tested. The input vectors v1, v2, ... are independent iff only one of the linear combinations a1v1+a2v2+... gives a 0 result (namely that for coefficients a1, a2, ... = 0).

|ssQ    % sum of absolute values of input plus 1
t_w     % duplicate, negate, swap
2$:     % binary range: [-S-1 -S ... S+1]
GZy1)   % push input. Number of rows (i.e. number of vectors), N
Z^      % Cartesian power. Gives (2S+3)×N-column array
!2$1!   % Permute dimensions to get N×1×(2S+3) array
G       % Push input: N×M array
*       % Product, element-wise with broadcast: N×M×(2S+3) array
Xs      % sum along first dimension (compute each linear combination): 1×M×(2S+3)
!       % Transpose: M×1×(2S+3)
Xa~     % Any along first dimension, negate: 1×1×(2S+3). True for 0-vector results
s       % Sum (number of 0-vector results)
2<      % True if less than 2


答:
Julia, 14 bytes

```<code>M->det(M'M)>.5
</code>```

Based on @Anna's MATLAB answer and @AlexA.'s Julia answer. Expects a matrix whose columns are the input vectors and returns a Boolean.

det returns a float, so we cannot compare the result directly with 0. However, since the entries of M are integers, the lowest possible positive determinant is 1.

Verification

```<code>julia> f = M->det(M'M)>.5
(anonymous function)

julia> [f(M) for M in(
         [0 2;1 3],
         [1 2;2 4],
         [2 3;6 9;8 12],
         [1 2 3;2 3 4],
         [1 0 0;0 1 0;0 0 1],
         zeros((1,1)),
         zeros((0,0)),
         [1 0 1;1 1 0],
         [1 1 0;2 3 0;3 5 0]
       )]
9-element Array{Any,1}:
  true
 false
 false
 false
  true
 false
  true
 false
 false
</code>```

Title: Linear Independence

Body:
Julia, 14 bytes

M->det(M'M)>.5

Based on @Anna's MATLAB answer and @AlexA.'s Julia answer. Expects a matrix whose columns are the input vectors and returns a Boolean.

det returns a float, so we cannot compare the result directly with 0. However, since the entries of M are integers, the lowest possible positive determinant is 1.

Verification

julia> f = M->det(M'M)>.5
(anonymous function)

julia> [f(M) for M in(
         [0 2;1 3],
         [1 2;2 4],
         [2 3;6 9;8 12],
         [1 2 3;2 3 4],
         [1 0 0;0 1 0;0 0 1],
         zeros((1,1)),
         zeros((0,0)),
         [1 0 1;1 1 0],
         [1 1 0;2 3 0;3 5 0]
       )]
9-element Array{Any,1}:
  true
 false
 false
 false
  true
 false
  true
 false
 false


问:
Quickly express a number with only 0-9 and the four operations, plus one more extra

Explanation

Befunge is a two-dimensional program that uses stacks.

That means, to do 5 + 6, you write 56+, meaning:

```<code>56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)
</code>```

However, we cannot push the number 56 directly into the stack.

To do so, we must write 78* instead, which multiplies 7 and 8 and pushes the product into the stack.

Details

For each number from 1 to n, find a string consisting of only these characters: 0123456789+-*/: (I would not use % modulo.)

The goal is to find the shortest string that can represent the number, using the format described above.

For example, if the input is 123, then the output would be 67*9:*+. The output should be evaluated from left to right.

If there are more than one acceptable outputs (e.g. 99*67*+ is also acceptable), any one can be printed (no bonus for printing all of them).

Further Explanation

If you still do not understand how 67*9:*+ evaluates to 123, here is a detailed explanation.

```<code>stack    |operation|explanation
          67*9:*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      :     duplicate the top of stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack
</code>```

TL;DR

The program needs to find the shortest string that can represent the input (number), using the format specified above.

SCORING

We have already done it in the shortest amount of code. This time, size does not matter.

Your language of choice has to have a free compiler/interpreter for my operating system (Windows 7 Enterprise).

Bonus if you include the link to the compiler/interpreter (I am too lazy).

If possible, please include a timer for my convenience. The output from the timer is valid.

The score will be the largest n in 1 minute.

That means, the program needs to print the required representation from 1 onward.

No hard-coding, except 0 to 9.

(more) SPECIFICS

The program is invalid if it outputs a string longer than needed for any number.

1/0=ERROR

5/2=2, (-5)/2=-2, (-5)/(-2)=2, 5/(-2)=-2

Disambiguation

The - is second-top minus top, meaning that 92- returns 7.

Likewise, the / is second-top divide top, meaning that 92/ returns 4.

Sample program

Lua

Uses depth-first search.

```<code>local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        elseif c == ':' then
            local a = table.remove(stack)
            if a then
                table.insert(stack,a)
                table.insert(stack,a)
            else
                return -1
            end
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, test)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        if eval(s) ~= -1 or s == "" then for n in ("9876543210+-*/:"):gmatch(".") do
            table.insert(temp, s..n)
        end end
    end
    for i=1,#temp do
        local test = eval(temp[i])
        if input == test then
            print(temp[i])
            return
        end
    end
    samples = temp
end
</code>```

答:
JavaScript Node Brute Force

Program file bfCodes.js

function bfCodes( n)
{   var odo = [0], valid = true, valCount=1;

    const vDUP = 10, vADD = 11, vSUB = 12, vMUL=13, vDIV = 14, vMAX = vDIV;
    const vCHARS = "0123456789:+-*/";

    function inc(sd) // increment significant digit, lsd = 0
    {   if(sd >= odo.length) { odo.push(0); console.log("length: " + (sd+1)); ++valCount; return;}
        var v = ++odo[sd]; // increment and read the base 15 odometer digit
        if( v == vDUP)
            if( valCount) {++valCount; return}
            else { odo[ sd] = vMAX; --valCount; valid = false; return;}

        if( v == vADD)
        {    if( (--valCount) < 1) { valid = false; odo[ sd] = vMAX; return;};
        }
        if( v > vMAX) { odo[sd] = 0; ++valCount; valid = true; inc(sd+1); return;}
    }

    function bfDecode( odo)
    {   var a,b,stack = [];
        for(var i = odo.length; i--;)
        {   var v = odo[ i];
            if( v < 10) { stack.push( v); continue;};
            switch(v) {
            case vDUP: stack.push( stack[stack.length-1]); continue;
            case vADD: b=stack.pop(); stack.push( stack.pop()+b); continue;
            case vMUL: b=stack.pop(); stack.push(stack.pop()*b); continue;
            case vDIV: b=stack.pop(); if(!b) return undefined; a = stack.pop();
                stack.push( (a < 0 ? b < 0 : b > 0) ? (a/b)>>0 : -(-a/b >>0)); continue;
            }
        }
        return stack[0];
    }
    var codes = [], value;
    for( var got = 0; got < n;)
    {   inc(0);
        if(!valid) continue;
        if(!(value = bfDecode( odo))) continue;
        if( value <= 0 || value > n || codes[ value]) continue;
        ++got;
        for(var i = odo.length, s=""; i--;)  s+=vCHARS[ odo[i]];
        codes[ value] = s;
    }
    return codes;
}

function main( args) // node, script, number
{   n = parseInt( args[2]);
    if(isNaN(n)){ console.log("\nTry:  node bfCodes number\nfor script saved as bfCodes.js"); return;}
    console.log("\ngenerating befunge code for numbers up to " + n);
    var start = Date.now();
    var codes = bfCodes(n);
    var end = Date.now();
    console.log("befunge codes:");
    for( var i = 1; i <=n; ++i) console.log( i + ": " + codes[i]);
    console.log(end-start + " msec");
}
main( process.argv);
```

Running under Windows

Download and install Nodejs, a stand alone implementation of Chromes V8 JavaScript engine.

Save the program file above in a working directory using file name "bfCodes.js" (Windows filenames are case insensitive).

Right click in the working directory and create a shortcut to the command shell program (DOS box for oldies) with target cmd.exe

Edit the shortcut's properties and set the working folder to the name of your working directory (click in the location bar and copy).

Open cmd.exe using the shortcut and check the DOS prompt starts with the working directory

Enter "node bfCodes" without quotes and enter - runing node the first time can take longer than running it again.

Enter "node bfCodes 16" to show codes up to 16. Do not use a large number!

Optimization

The algorithm cycles through all combinations of befunge characters starting with a code string of length 1. Think of it as spinning a base 15 odometer from the least significant digit. Higher order digits click over with increasing slowness. bfCodes does not evaluate generated code that would make the stack length zero or negative or leave more than one number on the stack in an attempt to optimize speed of execution.

The Brute Force Problem

For a code set of 15 characters, the time it takes to run through all combinations of a given length is give by

Tlen = 15 * Tlen-1

which is to say that if your program runs fifteen times faster than mine, you will only be able to check  one additional character code strings in the same time. To check two more characters in the same time a program would need to run 225 times faster. Time taken with a brute force approach rises exponentially as the length of code strings increases. And the magnitude of a number does necessarily indicate the number of befunge bytes needed to generate it.

Some figures.

Approximate times to generate a lists of codes on a Windows 7 32 bit notepad for integers up to

9:   1 msec

10: 16 msec

32: 156 msec

81: 312 msec

93: 18.5 seconds

132: 28 seconds

To generate befunge for 3727 (which is 66 squared plus 6) by itself took 1 hour 47 minutes and generated 578*+:*6+

Optimal code generation

Generating befunge for numbers without checking for shortest lengths is relatively simple. Using a recursive algorithm which used integer square roots and remainders, encodings for numbers up to 132 took about 3 msec instead of 28 seconds. They were not optimal. Because of the way it worked this particular algorithm produced638:*-:*+ for 3727 in about 1 msec (instead of an hour or so) which happened to be optimal.

The issue with providing a non brute force method is proving it is optimal in every case. Good luck!

Body:
JavaScript Node Brute Force

Program file bfCodes.js

function bfCodes( n)
{   var odo = [0], valid = true, valCount=1;

    const vDUP = 10, vADD = 11, vSUB = 12, vMUL=13, vDIV = 14, vMAX = vDIV;
    const vCHARS = "0123456789:+-*/";

    function inc(sd) // increment significant digit, lsd = 0
    {   if(sd >= odo.length) { odo.push(0); console.log("length: " + (sd+1)); ++valCount; return;}
        var v = ++odo[sd]; // increment and read the base 15 odometer digit
        if( v == vDUP)
            if( valCount) {++valCount; return}
            else { odo[ sd] = vMAX; --valCount; valid = false; return;}

        if( v == vADD)
        {    if( (--valCount) < 1) { valid = false; odo[ sd] = vMAX; return;};
        }
        if( v > vMAX) { odo[sd] = 0; ++valCount; valid = true; inc(sd+1); return;}
    }

    function bfDecode( odo)
    {   var a,b,stack = [];
        for(var i = odo.length; i--;)
        {   var v = odo[ i];
            if( v < 10) { stack.push( v); continue;};
            switch(v) {
            case vDUP: stack.push( stack[stack.length-1]); continue;
            case vADD: b=stack.pop(); stack.push( stack.pop()+b); continue;
            case vMUL: b=stack.pop(); stack.push(stack.pop()*b); continue;
            case vDIV: b=stack.pop(); if(!b) return undefined; a = stack.pop();
                stack.push( (a < 0 ? b < 0 : b > 0) ? (a/b)>>0 : -(-a/b >>0)); continue;
            }
        }
        return stack[0];
    }
    var codes = [], value;
    for( var got = 0; got < n;)
    {   inc(0);
        if(!valid) continue;
        if(!(value = bfDecode( odo))) continue;
        if( value <= 0 || value > n || codes[ value]) continue;
        ++got;
        for(var i = odo.length, s=""; i--;)  s+=vCHARS[ odo[i]];
        codes[ value] = s;
    }
    return codes;
}

function main( args) // node, script, number
{   n = parseInt( args[2]);
    if(isNaN(n)){ console.log("\nTry:  node bfCodes number\nfor script saved as bfCodes.js"); return;}
    console.log("\ngenerating befunge code for numbers up to " + n);
    var start = Date.now();
    var codes = bfCodes(n);
    var end = Date.now();
    console.log("befunge codes:");
    for( var i = 1; i <=n; ++i) console.log( i + ": " + codes[i]);
    console.log(end-start + " msec");
}
main( process.argv);

Running under Windows

Download and install Nodejs, a stand alone implementation of Chromes V8 JavaScript engine.

Save the program file above in a working directory using file name "bfCodes.js" (Windows filenames are case insensitive).

Right click in the working directory and create a shortcut to the command shell program (DOS box for oldies) with target cmd.exe

Edit the shortcut's properties and set the working folder to the name of your working directory (click in the location bar and copy).

Open cmd.exe using the shortcut and check the DOS prompt starts with the working directory

Enter "node bfCodes" without quotes and enter - runing node the first time can take longer than running it again.

Enter "node bfCodes 16" to show codes up to 16. Do not use a large number!

Optimization

The algorithm cycles through all combinations of befunge characters starting with a code string of length 1. Think of it as spinning a base 15 odometer from the least significant digit. Higher order digits click over with increasing slowness. bfCodes does not evaluate generated code that would make the stack length zero or negative or leave more than one number on the stack in an attempt to optimize speed of execution.

The Brute Force Problem

For a code set of 15 characters, the time it takes to run through all combinations of a given length is give by

Tlen = 15 * Tlen-1

which is to say that if your program runs fifteen times faster than mine, you will only be able to check  one additional character code strings in the same time. To check two more characters in the same time a program would need to run 225 times faster. Time taken with a brute force approach rises exponentially as the length of code strings increases. And the magnitude of a number does necessarily indicate the number of befunge bytes needed to generate it.

Some figures.

Approximate times to generate a lists of codes on a Windows 7 32 bit notepad for integers up to

9:   1 msec

10: 16 msec

32: 156 msec

81: 312 msec

93: 18.5 seconds

132: 28 seconds

To generate befunge for 3727 (which is 66 squared plus 6) by itself took 1 hour 47 minutes and generated 578*+:*6+

Optimal code generation

Generating befunge for numbers without checking for shortest lengths is relatively simple. Using a recursive algorithm which used integer square roots and remainders, encodings for numbers up to 132 took about 3 msec instead of 28 seconds. They were not optimal. Because of the way it worked this particular algorithm produced638:*-:*+ for 3727 in about 1 msec (instead of an hour or so) which happened to be optimal.

The issue with providing a non brute force method is proving it is optimal in every case. Good luck!


答:
J, 18 bytes

```<code>1<:[:-/ .*|:+/ .*]
</code>```

This is a tacit verb that accepts a matrix with the vectors as columns and returns 0 or 1 depending on whether the vectors are linearly dependent or independent, respectively.

The approach is based on Anna's Matlab answer and Dennis' Julia answer. For a matrix X, the square matrix XTX is singular (i.e. has zero determinant) if the columns of X are linearly independent. Since all elements of X are guaranteed to be integers, the smallest possible nonzero determinant is 1. Thus we compare 1 ≤ det|XTX| to get the result.

Examples (note that |: > is just for shaping the input):

```<code>  f =: 1<:[:-/ .*|:+/ .*]
  f |: > 0 1; 2 3
1
  f |: > 1 2; 2 4
0
  f |: > 2 6 8; 3 9 12
0
  f |: > 1 2; 2 3; 3 4
0
  f |: > 1 0 0; 0 1 0; 0 0 1
1
  f 0
0
  f (0 0 $ 0)
1
  f |: > 1 1; 0 1; 1 0
0
  f |: > 1 2 3; 1 3 5; 0 0 0
0
</code>```

Made possible with help from Dennis!

Title: Linear Independence

Body:
J, 18 bytes

1<:[:-/ .*|:+/ .*]

This is a tacit verb that accepts a matrix with the vectors as columns and returns 0 or 1 depending on whether the vectors are linearly dependent or independent, respectively.

The approach is based on Anna's Matlab answer and Dennis' Julia answer. For a matrix X, the square matrix XTX is singular (i.e. has zero determinant) if the columns of X are linearly independent. Since all elements of X are guaranteed to be integers, the smallest possible nonzero determinant is 1. Thus we compare 1 ≤ det|XTX| to get the result.

Examples (note that |: > is just for shaping the input):

  f =: 1<:[:-/ .*|:+/ .*]
  f |: > 0 1; 2 3
1
  f |: > 1 2; 2 4
0
  f |: > 2 6 8; 3 9 12
0
  f |: > 1 2; 2 3; 3 4
0
  f |: > 1 0 0; 0 1 0; 0 0 1
1
  f 0
0
  f (0 0 $ 0)
1
  f |: > 1 1; 0 1; 1 0
0
  f |: > 1 2 3; 1 3 5; 0 0 0
0

Made possible with help from Dennis!


答:
NARS2000 APL, 12 bytes

```<code>(≡≤-.×)⊢+.×⍉
</code>```

How it works

```<code>(≡≤-.×)⊢+.×⍉  Monadic function. Right argument: M

           ⍉  Transpose M.
       ⊢      Yield M.
        +.×   Perform matrix multiplication.
              For empty M, this yields a zero vector (for some reason).
(     )       Apply this matrix to the matrix product:
   -.×          Compute the determinant.
                This (mistakenly) yields 0 if M is empty.
 ≡              Yield the depth of M (1 is non-empty, 0 if empty).
  ≤             Compare.
                Since 0≤0, this corrects the error.
</code>```

Title: Linear Independence

Body:
NARS2000 APL, 12 bytes

(≡≤-.×)⊢+.×⍉

How it works

(≡≤-.×)⊢+.×⍉  Monadic function. Right argument: M

           ⍉  Transpose M.
       ⊢      Yield M.
        +.×   Perform matrix multiplication.
              For empty M, this yields a zero vector (for some reason).
(     )       Apply this matrix to the matrix product:
   -.×          Compute the determinant.
                This (mistakenly) yields 0 if M is empty.
 ≡              Yield the depth of M (1 is non-empty, 0 if empty).
  ≤             Compare.
                Since 0≤0, this corrects the error.


问:
Find the program that prints this integer sequence (Robbers' thread)
This is the robbers' thread. The cops' thread goes here.

In the cops thread, the task was to write a program/function that takes a positive (or non-negative) integer and outputs/returns another number (not necessarily integer). The robbers task is to unscramble the code the cops used to produce this output.

The cracked code doesn't have to be identical, as long as it has the same length and any revealed characters are in the correct positions. The language must also be the same (version numbers can be different). The output must of course be identical.

No-ops can be used in robber's solution.

The winner of the robbers thread will be the user who has cracked the
most submissions by May 7th 2016. If there's a tie, the user who has cracked submissions with the longest combined code will win.

The submission should be formatted like this:

Language, nn characters (including link to answer), Cop's username

Code:

```<code>function a(n)
    if n<2 then
        return n
    else
        return a(n-1) + a(n-2)
    end
end
</code>```

Output

```<code>a(0) returns 0
a(3) returns 2
</code>```

Optional explanation and comments.

答:
05AB1A, 4 bytes, Adnan, A001127

Code:

```<code>$FÂ+
</code>```

Explained:

```<code>$          # push 1 and input
 F         # input number of times, do:
  Â        # duplicate and reverse
   +       # add
</code>```

The sequence starts at 1 and continues by adding the current number to its reverse.

```<code>0: 1
1: 1+1 = 2
2: 2+2 = 4
3: 4+4 = 8
4: 8+8 = 16
5: 16+61 = 77
6: 77+77 = 154
7: 154+451= 605
and so on...
</code>```

Body:
05AB1A, 4 bytes, Adnan, A001127

Code:

$FÂ+

Explained:

$          # push 1 and input
 F         # input number of times, do:
  Â        # duplicate and reverse
   +       # add

The sequence starts at 1 and continues by adding the current number to its reverse.

0: 1
1: 1+1 = 2
2: 2+2 = 4
3: 4+4 = 8
4: 8+8 = 16
5: 16+61 = 77
6: 77+77 = 154
7: 154+451= 605
and so on...


问:
Autocomplete the input
Pre-Note

Because of popular demand, and to avoid disqualifying certain languages, the dictionary can now be provided as input parameter.

Intro

Given a dictionary of words, you should write an autocomplete program or function.

Autocompletion

"Autocomplete, or word completion, is a feature in which an application predicts the rest of a word a user is typing." (Wikipedia)

Autocompletion is oftenly used to reduce the time needed for typing sentences. After typing a single character, the program will start guessing what the user is trying to say. In this challenge we will simulate the behaviour of autocompleting words.

If the program encounters a word it doesn't know, and no matching autocompletion words can be found, it will assume that the user is trying to type a word the program doesn't know. Good autocompletion software will own and edit a custom dictionary of words, but for the sakes of complexity that's not part of this challenge.

Input

Your program/function will take at least a single parameter of input. This parameter can either be a string or an array of characters, and will consist of lowercase characters [a-z].

Optionally, your program/function will take a second parameter containing a dictionary of words. More info on this in the paragraph Dictionary.

Output

You should print or return an array of autocompleted words. For each character in the input, an autocompletion should be added to the output array.

The autocompletions will be taken from the provided dictionary. If a word doesn't exist in the dictionary, it will alphabetically search for the next word matching your characters. If no matching word is found, the input will be returned (see test cases)

Dictionary

If you choose to read the dictionary from a file, the file structure should be your list of words, seperated by newlines.

If you choose to submit the dictionary of words as a parameter of a function call, it should be structured as an ordered list of strings; ['cat', 'cake', ...].

The input is always fully lowercase and sorted alphabetically.

Test case

a.txt content:

```<code>alpha
calf
cave
coax
code
codegimmick
codegolf
cool
gamma
</code>```

Test cases:

```<code>"codegolf"                  // ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"]
"alpaca"                    // ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"]
["t", "h", "i", "s"]        // ["t", "th", "thi", "this"]
("catses", ["cake","cats"]) // ["cake", "cake", "cats", "cats", "catse", "catses"]
</code>```

This is code-golf, shortest code in bytes wins

答:
Javascript ES6, <s>80</s> 77 chars

```<code>(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])
</code>```

Test:

```<code>d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])
;[
f("cat", ["cat"])[0] === "cat",
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]
</code>```

Can reduce 4 chars (73 in total) if return array of single-element arrays:

```<code>(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)
</code>```

Test:

```<code>d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)
;[
// f("cat", ["cat"])[0] === "cat", // will be failed
f("cat", ["cat"])[0][0] === "cat", // ok
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]
[false, true, true, true, true]
</code>```

Title: Autocomplete the input

Body:
Javascript ES6, <s>80</s> 77 chars

(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])

Test:

d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec([d,x])[0])
;[
f("cat", ["cat"])[0] === "cat",
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]

Can reduce 4 chars (73 in total) if return array of single-element arrays:

(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)

Test:

d="alpha,calf,cave,coax,code,codegimmick,codegolf,cool,gamma".split`,`;
f=(w,d)=>[...w].map((x,i)=>RegExp(`\\b${x=w.slice(0,i+1)}\\w*`).exec(d)||x)
;[
// f("cat", ["cat"])[0] === "cat", // will be failed
f("cat", ["cat"])[0][0] === "cat", // ok
f("codegolf", d) == '' + ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"],
f("alpaca", d) == '' + ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"],
f("this", d) == '' + ["t", "th", "thi", "this"],
f("catses", ["cake","cats"]) == '' + ["cake", "cake", "cats", "cats", "catse", "catses"]
]
[false, true, true, true, true]


答:
C#, 126 131 bytes

Edited version to conform with the new question:

```<code>class P{static void Main(){int x,s=0,n=int.Parse(System.Console.ReadLine());for(x=1;x*x<n;x+=2)s+=x*x;System.Console.Write(s);}}
</code>```

Using hardcoded limit:

```<code>using System;namespace F{class P{static void Main(){int x,s=0;for(x=1;x<100;x+=2)s+=x*x;Console.Write(s);Console.Read();}}}
</code>```

Title: Sum the odd square numbers less than N

Body:
Write a program or function to output the sum of the odd square numbers (OEIS #A016754) less than an input n.

The first 44 numbers in the sequence are:

```<code>1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089,
1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481,
3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625, 5929, 6241, 6561, 6889, 7225, 7569
</code>```

The formula for the sequence is a(n) = ( 2n + 1 ) ^ 2.

Notes

Your program's behaviour may be undefined for n < 1 (that is, all valid inputs are >= 1.)

Test cases

```<code>1 => 0
2 => 1
9 => 1
10 => 10
9801 => 156849
9802 => 166650
10000 => 166650
</code>```

Body:
C#, 126 131 bytes

Edited version to conform with the new question:

class P{static void Main(){int x,s=0,n=int.Parse(System.Console.ReadLine());for(x=1;x*x<n;x+=2)s+=x*x;System.Console.Write(s);}}

Using hardcoded limit:

using System;namespace F{class P{static void Main(){int x,s=0;for(x=1;x<100;x+=2)s+=x*x;Console.Write(s);Console.Read();}}}


答:
CJam, 15 Bytes

```<code>qi(mq,2%:)2f#1b
</code>```

Try it online!

Hardcoded 10000 solutions:

Martin's 12 byte solution:

```<code>99,2%:)2f#1b
</code>```

My original 13 byte solution:

```<code>50,{2*)2#}%:+
</code>```

Try it online!

Title: Sum the odd square numbers less than N

Body:
CJam, 15 Bytes

qi(mq,2%:)2f#1b

Try it online!

Hardcoded 10000 solutions:

Martin's 12 byte solution:

99,2%:)2f#1b

My original 13 byte solution:

50,{2*)2#}%:+

Try it online!


Title: Sum the odd square numbers less than N

Body:
Octave, 23 bytes

@(x)(x=1:2:(x-1)^.5)*x'

Testing:

[f(1); f(2); f(3); f(10); f(9801); f(9802); f(10000)]
ans =
        0
        1
        1
       10
   156849
   166650
   166650


答:
05AB1E, <s>10</s> 8 bytes

Code:

```<code><tLDÉÏnO
</code>```

Explanation:

```<code><         # Decrease by 1, giving a non-inclusive range.
 t        # Take the square root of the implicit input.
  L       # Generate a list from [1 ... sqrt(input - 1)].
   DÉÏ    # Keep the uneven integers of the list.
      n   # Square them all.
       O  # Take the sum of the list and print implicitly.
</code>```

Might come in handy: t;L·<nO.

Uses CP-1252 encoding. Try it online!.

Title: Sum the odd square numbers less than N

Body:
05AB1E, <s>10</s> 8 bytes

Code:

<tLDÉÏnO

Explanation:

<         # Decrease by 1, giving a non-inclusive range.
 t        # Take the square root of the implicit input.
  L       # Generate a list from [1 ... sqrt(input - 1)].
   DÉÏ    # Keep the uneven integers of the list.
      n   # Square them all.
       O  # Take the sum of the list and print implicitly.

Might come in handy: t;L·<nO.

Uses CP-1252 encoding. Try it online!.


答:
Java 8, <s>128</s> <s>119</s> <s>117</s> <s>111</s> 49 bytes

n->{int s=0,i=1;for(;i*i<n;i+=2)s+=i*i;return s;}
```
<p>Based on <em>@Thomas</em>' C# solution.</p>
<p><strong>Explanation:</strong></p>
<p>Try it online.</p>
<pre class="lang-java prettyprint-override"><code>n->{           // Method with integer as both parameter and return-type
  int s=0,     //  Sum, starting at 0
      i=1;     //  Index-integer, starting at 1
  for(;i*i<n;  //  Loop as long as the square of `i` is smaller than the input
      i+=2)    //    After every iteration, increase `i` by 2
    s+=i*i;    //   Increase the sum by the square of `i`
  return s;}   //  Return the result-sum
</code>```

Title: Sum the odd square numbers less than N

Body:
Java 8, <s>128</s> <s>119</s> <s>117</s> <s>111</s> 49 bytes

n->{int s=0,i=1;for(;i*i<n;i+=2)s+=i*i;return s;}

Based on @Thomas' C# solution.

Explanation:

Try it online.

n->{           // Method with integer as both parameter and return-type
  int s=0,     //  Sum, starting at 0
      i=1;     //  Index-integer, starting at 1
  for(;i*i<n;  //  Loop as long as the square of `i` is smaller than the input
      i+=2)    //    After every iteration, increase `i` by 2
    s+=i*i;    //   Increase the sum by the square of `i`
  return s;}   //  Return the result-sum


答:
JavaScript (ES6), 30 bytes

```<code>f=(n,i=1)=>n>i*i&&i*i+f(n,i+2)
</code>```

31 bytes if f(1) needs to return zero instead of false:

```<code>f=(n,i=1)=>n>i*i?i*i+f(n,i+2):0
</code>```

Title: Sum the odd square numbers less than N

Body:
JavaScript (ES6), 30 bytes

f=(n,i=1)=>n>i*i&&i*i+f(n,i+2)

31 bytes if f(1) needs to return zero instead of false:

f=(n,i=1)=>n>i*i?i*i+f(n,i+2):0


答:
JavaScript (ES6), 56

Input: array of characters, array of words

Output: array

```<code>(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)
</code>```

Test

f=(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

dict=['alpha','calf','cave','coax','code','codegimmick','codegolf','cool','gamma']

console.log=x=>O.textContent+=x+'\n'

;[['c','o','d','e','g','o','l','f'],['a','l','p','a','c','a'],['t','h','i','s']]
.forEach(t=>console.log(t+' -> '+f(t,dict)))```
<pre class="snippet-code-html lang-html prettyprint-override"><code><pre id=O>``````

Title: Autocomplete the input

Body:
Pre-Note

Because of popular demand, and to avoid disqualifying certain languages, the dictionary can now be provided as input parameter.

Intro

Given a dictionary of words, you should write an autocomplete program or function.

Autocompletion

"Autocomplete, or word completion, is a feature in which an application predicts the rest of a word a user is typing." (Wikipedia)

Autocompletion is oftenly used to reduce the time needed for typing sentences. After typing a single character, the program will start guessing what the user is trying to say. In this challenge we will simulate the behaviour of autocompleting words.

If the program encounters a word it doesn't know, and no matching autocompletion words can be found, it will assume that the user is trying to type a word the program doesn't know. Good autocompletion software will own and edit a custom dictionary of words, but for the sakes of complexity that's not part of this challenge.

Input

Your program/function will take at least a single parameter of input. This parameter can either be a string or an array of characters, and will consist of lowercase characters [a-z].

Optionally, your program/function will take a second parameter containing a dictionary of words. More info on this in the paragraph Dictionary.

Output

You should print or return an array of autocompleted words. For each character in the input, an autocompletion should be added to the output array.

The autocompletions will be taken from the provided dictionary. If a word doesn't exist in the dictionary, it will alphabetically search for the next word matching your characters. If no matching word is found, the input will be returned (see test cases)

Dictionary

If you choose to read the dictionary from a file, the file structure should be your list of words, seperated by newlines.

If you choose to submit the dictionary of words as a parameter of a function call, it should be structured as an ordered list of strings; ['cat', 'cake', ...].

The input is always fully lowercase and sorted alphabetically.

Test case

a.txt content:

```<code>alpha
calf
cave
coax
code
codegimmick
codegolf
cool
gamma
</code>```

Test cases:

```<code>"codegolf"                  // ["calf", "coax", "code", "code", "codegimmick", "codegolf", "codegolf", "codegolf"]
"alpaca"                    // ["alpha", "alpha", "alpha", "alpa", "alpac", "alpaca"]
["t", "h", "i", "s"]        // ["t", "th", "thi", "this"]
("catses", ["cake","cats"]) // ["cake", "cake", "cats", "cats", "catse", "catses"]
</code>```

This is code-golf, shortest code in bytes wins

Body:
JavaScript (ES6), 56

Input: array of characters, array of words

Output: array

(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

Test

f=(s,d,w='')=>s.map(c=>d.find(e=>e.startsWith(w),w+=c)||w)

dict=['alpha','calf','cave','coax','code','codegimmick','codegolf','cool','gamma']

console.log=x=>O.textContent+=x+'\n'

;[['c','o','d','e','g','o','l','f'],['a','l','p','a','c','a'],['t','h','i','s']]
.forEach(t=>console.log(t+' -> '+f(t,dict)))

<pre id=O></pre>


答:
MATL, 10 bytes

```<code>qX^:9L)2^s
</code>```

EDIT (July 30, 2016): the linked code replaces 9L by 1L to adapt to recent changes in the language.

Try it online!

```<code>q    % Implicit input. Subtract 1
X^   % Square root
:    % Inclusive range from 1 to that
9L)  % Keep odd-indexed values only
2^   % Square
s    % Sum of array
</code>```

Title: Sum the odd square numbers less than N

Body:
MATL, 10 bytes

qX^:9L)2^s

EDIT (July 30, 2016): the linked code replaces 9L by 1L to adapt to recent changes in the language.

Try it online!

q    % Implicit input. Subtract 1
X^   % Square root
:    % Inclusive range from 1 to that
9L)  % Keep odd-indexed values only
2^   % Square
s    % Sum of array


答:
Jelly, 7

```<code>’½R²m2S
</code>```

Try it online or try a modified version for multiple values

Shh... Dennis is sleeping...

Thanks to Sp3000 in chat for their help!

Explanation:

```<code>’½R²m2S
’           ##  Decrement to prevent off-by-one errors
 ½R²        ##  Square root, then floor and make a 1-indexed range, then square each value
    m2      ##  Take every other value, starting with the first
      S     ##  sum the result
</code>```

Title: Sum the odd square numbers less than N

Body:
Jelly, 7

’½R²m2S

Try it online or try a modified version for multiple values

Shh... Dennis is sleeping...

Thanks to Sp3000 in chat for their help!

Explanation:

’½R²m2S
’           ##  Decrement to prevent off-by-one errors
 ½R²        ##  Square root, then floor and make a 1-indexed range, then square each value
    m2      ##  Take every other value, starting with the first
      S     ##  sum the result


答:
Jelly, 6 bytes

```<code>½Ċ|1c3
</code>```

Try it online! or verify all test cases.

Background

For all positive integers k, we have 1² + 3² + ⋯ + (2k - 1)² = k(2k - 1)(2k +1) ÷ 3.

Since there are m C r = m! ÷ ((m-r)!r!) r-combinations of a set of m elements, the above can be calculated as (2k + 1) C 3 = (2k + 1)2k(2k - 1) ÷ 6 = k(2k - 1)(2k + 1) ÷ 3.

To apply the formula, we must find the highest 2k + 1 such that (2k - 1)² < n. Ignoring the parity for a moment, we can compute the highest m such that (m - 1)² < n as m = ceil(srqt(n)). To conditionally increment m if it is even, simply compute m | 1 (bitwise OR with 1).

How it works

```<code>½Ċ|1c3  Main link. Argument: n

½       Compute the square root of n.
 Ċ      Round it up to the nearest integer.
  |1    Bitwise OR with 1 to get an odd number.
    c3  Compute (2k + 1) C 3 (combinations).
</code>```

Title: Sum the odd square numbers less than N

Body:
Jelly, 6 bytes

½Ċ|1c3

Try it online! or verify all test cases.

Background

For all positive integers k, we have 1² + 3² + ⋯ + (2k - 1)² = k(2k - 1)(2k +1) ÷ 3.

Since there are m C r = m! ÷ ((m-r)!r!) r-combinations of a set of m elements, the above can be calculated as (2k + 1) C 3 = (2k + 1)2k(2k - 1) ÷ 6 = k(2k - 1)(2k + 1) ÷ 3.

To apply the formula, we must find the highest 2k + 1 such that (2k - 1)² < n. Ignoring the parity for a moment, we can compute the highest m such that (m - 1)² < n as m = ceil(srqt(n)). To conditionally increment m if it is even, simply compute m | 1 (bitwise OR with 1).

How it works

½Ċ|1c3  Main link. Argument: n

½       Compute the square root of n.
 Ċ      Round it up to the nearest integer.
  |1    Bitwise OR with 1 to get an odd number.
    c3  Compute (2k + 1) C 3 (combinations).


问:
Most creative way to reverse a positive integer
Provided an input as an unsigned integer:

```<code>13457
</code>```

Your function/subroutine should return:

```<code>75431
</code>```

Since this is a popularity contest, be creative. Creative solutions use unusual or clever techniques to accomplish given task.

Constraints:

You cannot use arrays.

You cannot use strings.

No RTL Override (&#8238)

Brownie points for using creative arithmetics.

Since this is a popularity contest, I suggest not using the modulo (%) operator in your code.

About Leading zeroes:

If the input is:

```<code>12340
</code>```

Then the output:

```<code>4321
</code>```

would be acceptable.

答:
Turing Machine Code

Using the syntax from here.

```<code>0 * * l 0
0 _ # r 2
2 # # r 2
2 0 # l A
2 1 # l B
2 2 # l C
2 3 # l D
2 4 # l E
2 5 # l F
2 6 # l G
2 7 # l H
2 8 # l I
2 9 # l J
2 _ _ l Z
A * * l A
A _ 0 l Q
B * * l B
B _ 1 l Q
C * * l C
C _ 2 l Q
D * * l D
D _ 3 l Q
E * * l E
E _ 4 l Q
F * * l F
F _ 5 l Q
G * * l G
G _ 6 l Q
H * * l H
H _ 7 l Q
I * * l I
I _ 8 l Q
J * * l J
J _ 9 l Q
Q # # r 2
Q * * r Q
Z # _ l Z
Z * * l ZZ
ZZ _ * r ZZZ
ZZ * * l ZZ
ZZZ 0 _ r ZZZ
ZZZ * * * halt
</code>```

Try it online!

Body:
Turing Machine Code

Using the syntax from here.

0 * * l 0
0 _ # r 2
2 # # r 2
2 0 # l A
2 1 # l B
2 2 # l C
2 3 # l D
2 4 # l E
2 5 # l F
2 6 # l G
2 7 # l H
2 8 # l I
2 9 # l J
2 _ _ l Z
A * * l A
A _ 0 l Q
B * * l B
B _ 1 l Q
C * * l C
C _ 2 l Q
D * * l D
D _ 3 l Q
E * * l E
E _ 4 l Q
F * * l F
F _ 5 l Q
G * * l G
G _ 6 l Q
H * * l H
H _ 7 l Q
I * * l I
I _ 8 l Q
J * * l J
J _ 9 l Q
Q # # r 2
Q * * r Q
Z # _ l Z
Z * * l ZZ
ZZ _ * r ZZZ
ZZ * * l ZZ
ZZZ 0 _ r ZZZ
ZZZ * * * halt

Try it online!


答:
Python 3, 61 49 bytes

lambda n:sum(i*i for i in range(1,n,2)if i*i<n)
```

plenty of savings, thanks for helping me out

Title: Sum the odd square numbers less than N

Body:
Python 3, 61 49 bytes

lambda n:sum(i*i for i in range(1,n,2)if i*i<n)

plenty of savings, thanks for helping me out


答:
Python 2, 49 bytes

This ended up being shorter than a lambda.

x=input()
i=1;k=0
while i*i<x:k+=i*i;i+=2
print k
```
<p><strong>Try it online</strong></p>
<p>My shortest <code>lambda</code>, <strong>53 bytes</strong>:</p>
<pre class="lang-python prettyprint-override"><code>lambda x:sum((n-~n)**2for n in range(x)if(n-~n)**2<x)
</code>```

Title: Sum the odd square numbers less than N

Body:
Python 2, 49 bytes

This ended up being shorter than a lambda.

x=input()
i=1;k=0
while i*i<x:k+=i*i;i+=2
print k

Try it online

My shortest lambda, 53 bytes:

lambda x:sum((n-~n)**2for n in range(x)if(n-~n)**2<x)


答:
Python, 42 38 bytes

```<code>f=lambda n,i=1:i*i<n and i*i+f(n,i+2)
</code>```

Title: Sum the odd square numbers less than N

Body:
Python, 42 38 bytes

f=lambda n,i=1:i*i<n and i*i+f(n,i+2)


答:
Pyth, 10 bytes

```<code>s<#Qm^hyd2
</code>```

Test suite

Explanation:

```<code>s<#Qm^hyd2
    m          Map over the range of input (0 ... input - 1)
       yd      Double the number
      h        Add 1
     ^   2     Square it
 <#            Filter the resulting list on being less than
   Q           The input
s              Add up what's left
</code>```

Title: Sum the odd square numbers less than N

Body:
Pyth, 10 bytes

s<#Qm^hyd2

Test suite

Explanation:

s<#Qm^hyd2
    m          Map over the range of input (0 ... input - 1)
       yd      Double the number
      h        Add 1
     ^   2     Square it
 <#            Filter the resulting list on being less than
   Q           The input
s              Add up what's left


答:
Haskell, <s>32</s> 31 bytes

```<code> n#x=sum[x^2+n#(x+2)|x^2<n]
 (#1)
</code>```

Usage example: (#1) 9802 -> 166650.

Edit: @xnor saved a byte, with a clever list comprehension. Thanks!

Title: Sum the odd square numbers less than N

Body:
Write a program or function to output the sum of the odd square numbers (OEIS #A016754) less than an input n.

The first 44 numbers in the sequence are:

```<code>1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089,
1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481,
3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625, 5929, 6241, 6561, 6889, 7225, 7569
</code>```

The formula for the sequence is a(n) = ( 2n + 1 ) ^ 2.

Notes

Your program's behaviour may be undefined for n < 1 (that is, all valid inputs are >= 1.)

Test cases

```<code>1 => 0
2 => 1
9 => 1
10 => 10
9801 => 156849
9802 => 166650
10000 => 166650
</code>```

Body:
Haskell, <s>32</s> 31 bytes

 n#x=sum[x^2+n#(x+2)|x^2<n]
 (#1)

Usage example: (#1) 9802 -> 166650.

Edit: @xnor saved a byte, with a clever list comprehension. Thanks!


答:
Reng v.3.3, 36 bytes

```<code>0#ci#m1ø>$a+¡n~
:m%:1,eq^c2*1+²c1+#c
</code>```

Try it here!

Explanation

1: initialization

```<code> 0#ci#m1ø
</code>```

Sets c to 0 (the counter) and the input I to the max. 1ø goes to the next line.

2: loop

```<code>:m%:1,eq^c2*1+²c1+#c
</code>```

: duplicates the current value (the squared odd number) and [I m puts max down. I used the less-than trick in another answer, which I use here. %:1,e checks if the STOS < TOS. If it is, q^ goes up and breaks out of the loop. Otherwise:

```<code>         c2*1+²c1+#c
</code>```

c puts the counter down, 2* doubles it, 1+ adds one, and ² squares it. c1+#C increments c, and the loop goes again.

3: final

```<code>        >$a+¡n~
</code>```

$ drops the last value (greater than desired), a+¡ adds until the stack's length is 1, n~ outputs and terminates.

Title: Sum the odd square numbers less than N

Body:
Reng v.3.3, 36 bytes

0#ci#m1ø>$a+¡n~
:m%:1,eq^c2*1+²c1+#c

Try it here!

Explanation

1: initialization

 0#ci#m1ø

Sets c to 0 (the counter) and the input I to the max. 1ø goes to the next line.

2: loop

:m%:1,eq^c2*1+²c1+#c

: duplicates the current value (the squared odd number) and [I m puts max down. I used the less-than trick in another answer, which I use here. %:1,e checks if the STOS < TOS. If it is, q^ goes up and breaks out of the loop. Otherwise:

         c2*1+²c1+#c

c puts the counter down, 2* doubles it, 1+ adds one, and ² squares it. c1+#C increments c, and the loop goes again.

3: final

        >$a+¡n~

$ drops the last value (greater than desired), a+¡ adds until the stack's length is 1, n~ outputs and terminates.


答:
Python, 39 bytes

f=lambda n,i=1:+(i*i<n)and i*i+f(n,i+2)
```
<p>If, for <code>n=1</code>, it's valid to output <code>False</code> rather than <code>0</code>, then we can avoid the base case conversion to get 37 bytes</p>
<pre class="lang-python prettyprint-override"><code>f=lambda n,i=1:i*i<n and i*i+f(n,i+2)
</code>```

It's strange that I haven't found a shorter way to get 0 for i*i>=n and nonzero otherwise. In Python 2, one still gets 39 bytes with

f=lambda n,i=1:~-n/i/i and i*i+f(n,i+2)
```

Title: Sum the odd square numbers less than N

Body:
Python, 39 bytes

f=lambda n,i=1:+(i*i<n)and i*i+f(n,i+2)

If, for n=1, it's valid to output False rather than 0, then we can avoid the base case conversion to get 37 bytes

f=lambda n,i=1:i*i<n and i*i+f(n,i+2)

It's strange that I haven't found a shorter way to get 0 for i*i>=n and nonzero otherwise. In Python 2, one still gets 39 bytes with

f=lambda n,i=1:~-n/i/i and i*i+f(n,i+2)


答:
MATL, <s>13</s> 11 bytes

```<code>t!Y*2$0ZnYo
</code>```

Thanks to Luis for golfing off two bytes.

Based on Anna's MATLAB answer.

Explanation

```<code>t!Y*2$0ZnYo
t              duplicate input
 !             transpose
  Y*           matrix product, yields X^T * X
    2$0Zn      determinant
         Yo    round
</code>```

Title: Linear Independence

Body:
Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0,  a1v1 + a2v2 + ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -> output):

```<code>[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False
</code>```

Body:
MATL, <s>13</s> 11 bytes

t!Y*2$0ZnYo

Thanks to Luis for golfing off two bytes.

Based on Anna's MATLAB answer.

Explanation

t!Y*2$0ZnYo
t              duplicate input
 !             transpose
  Y*           matrix product, yields X^T * X
    2$0Zn      determinant
         Yo    round


答:
PARI/GP, <s>33</s> <s>32</s> 26 bytes

Adapted from Dennis' code:

```<code>n->t=(1-n^.5)\2*2;(t-t^3)/6
</code>```

My first idea (30 bytes), using a simple polynomial formula:

```<code>n->t=((n-1)^.5+1)\2;(4*t^3-t)/3
</code>```

This is an efficient implementation, actually not very different from the ungolfed version I would write:

```<code>a(n)=
{
  my(t=ceil(sqrtint(n-1)/2));
  t*(4*t^2-1)/3;
}
</code>```

An alternate implementation (37 bytes) which loops over each of the squares:

```<code>n->s=0;t=1;while(t^2<n,s+=t^2;t+=2);s
</code>```

Another alternate solution (35 bytes) demonstrating summing without a temporary variable:

```<code>n->sum(k=1,((n-1)^.5+1)\2,(2*k-1)^2)
</code>```

Yet another solution, not particularly competitive (40 bytes), using the L2 norm. This would be better if there was support for vectors with step-size indices. (One could imagine the syntax n->norml2([1..((n-1)^.5+1)\2..2]) which would drop 8 bytes.)

```<code>n->norml2(vector(((n-1)^.5+1)\2,k,2*k-1))
</code>```

Title: Sum the odd square numbers less than N

Body:
PARI/GP, <s>33</s> <s>32</s> 26 bytes

Adapted from Dennis' code:

n->t=(1-n^.5)\2*2;(t-t^3)/6

My first idea (30 bytes), using a simple polynomial formula:

n->t=((n-1)^.5+1)\2;(4*t^3-t)/3

This is an efficient implementation, actually not very different from the ungolfed version I would write:

a(n)=
{
  my(t=ceil(sqrtint(n-1)/2));
  t*(4*t^2-1)/3;
}

An alternate implementation (37 bytes) which loops over each of the squares:

n->s=0;t=1;while(t^2<n,s+=t^2;t+=2);s

Another alternate solution (35 bytes) demonstrating summing without a temporary variable:

n->sum(k=1,((n-1)^.5+1)\2,(2*k-1)^2)

Yet another solution, not particularly competitive (40 bytes), using the L2 norm. This would be better if there was support for vectors with step-size indices. (One could imagine the syntax n->norml2([1..((n-1)^.5+1)\2..2]) which would drop 8 bytes.)

n->norml2(vector(((n-1)^.5+1)\2,k,2*k-1))


答:
Mathcad, 31 "bytes"

Note that Mathcad uses keyboard shortcuts to enter several operators, including the definition and all programming operators.  For example, ctl-] enters a while loop - it cannot be typed and can only be entered using the keyboard shortcut or from the Programming toolbar.   "Bytes" are taken to be the number of keyboard operations needed to enter a Mathcad item (eg, variable name or operator).

As I have no chance of winning this competition, I thought I'd add a bit of variety with a direct formula version.

Title: Sum the odd square numbers less than N


答:
Python 2, 38 bytes

s=(1-input()**.5)//2*2;print(s-s**3)/6
```

Based off Dennis's formula, with s==-2*k. Outputs a float. In effect, the input is square rooted, decremented, then rounded up to the next even number.

Title: Sum the odd square numbers less than N

Body:
Python 2, 38 bytes

s=(1-input()**.5)//2*2;print(s-s**3)/6

Based off Dennis's formula, with s==-2*k. Outputs a float. In effect, the input is square rooted, decremented, then rounded up to the next even number.


答:
C, <s>51, 50</s> 48 bytes

```<code>f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}
</code>```

Because why not golf in one of the most verbose languages? (Hey, at least it's not Java!)

Try it online!

Full ungolfed program, with test I/O:

```<code>int main()
{
    int s;
    f(10, &s);
    printf("%d\n", s);
    char *foobar[1];
    gets(foobar);
}

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}
</code>```

Title: Sum the odd square numbers less than N

Body:
C, <s>51, 50</s> 48 bytes

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}

Because why not golf in one of the most verbose languages? (Hey, at least it's not Java!)

Try it online!

Full ungolfed program, with test I/O:

int main()
{
    int s;
    f(10, &s);
    printf("%d\n", s);
    char *foobar[1];
    gets(foobar);
}

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}