问:
The fastest square root calculator
Write a program which outputs the square root of a given number in the shortest time possible.

Rules

It may not use any builtins or powering with non-integers.

Input format

as a function argument

as a command line argument

as a direct input on stdin or a window

Your entry hasn't to be a complete program, it may be a function or a snippet.

It doesn't need to be exact; a one percent margin of error is allowed.

The test cases will only be positive integers, but your program should output/return floats.

It may return the square root as function return value, print it to stdout or write in a consistent file, which is readable by the user..
Each program should specify the compiler/interpreter it should be run on and compiler flags. If they aren't specified, I'll use the following implementations: (just talking about mainstream langs):

C/C++: gcc/g++ on Linux, no flags

Java: OpenJDK on Linux, no flags

Python: CPython

Ruby: MRI

Assembler: x86 Linux

JS: Node.js

Examples

```<code>Input    Output
4        2 (or something between 1.98 and 2.02)
64       8 (between 7.92 and 8.08)
10000    100 (between 99 and 101)
2        bewteen 1.40001 and 1.428
</code>```

Scoring

Your programs on the same computer with same conditions (Terminal and Iceweasel with this tab open).
This question has the tag "Fastest code", so the program, which calculates the square root of a (not yet given) random integer between 1 and 10^10 as fast as possible will win!

答:
C

Since input is limited to positive integers between 1 and 1010, I can use a well-known fast inverse square root algorithm to find the inverse square root of the reciprocal of the input.

I'm not sure what you mean by "only Xfce and the program and a terminal running" but since you stated that functions are acceptable, I provide a function in C that will take an integer argument (that will be casted to float automatically) and outputs a float as the result.

```<code>float f(float n) {
    n = 1.0f / n;
    long i;
    float x, y;

    x = n * 0.5f;
    y = n;
    i = *(long *)&y;
    i = 0x5f3759df - (i >> 1);
    y = *(float *)&i;
    y = y * (1.5f - (x * y * y));

    return y;
}
</code>```

The following is a program that makes uses of the function above to calculate the square roots of the given test cases and compares them to the values given by the sqrtf function in math.h.

Ideone

Title: The fastest square root calculator

Body:
C

Since input is limited to positive integers between 1 and 1010, I can use a well-known fast inverse square root algorithm to find the inverse square root of the reciprocal of the input.

I'm not sure what you mean by "only Xfce and the program and a terminal running" but since you stated that functions are acceptable, I provide a function in C that will take an integer argument (that will be casted to float automatically) and outputs a float as the result.

float f(float n) {
    n = 1.0f / n;
    long i;
    float x, y;

    x = n * 0.5f;
    y = n;
    i = *(long *)&y;
    i = 0x5f3759df - (i >> 1);
    y = *(float *)&i;
    y = y * (1.5f - (x * y * y));

    return y;
}

The following is a program that makes uses of the function above to calculate the square roots of the given test cases and compares them to the values given by the sqrtf function in math.h.

Ideone


答:
C

Uses unsigned integers when possible for speed.

root.c:

```<code>#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ns(t) (1000000000 * t.tv_sec + t.tv_nsec)

struct timespec then, now;

int output(uint64_t result)
{
    clock_gettime(CLOCK_REALTIME, &now);
  printf("sqrt(x) = %10lu.%2d    real time:%9ld ns\n", result / 100, ((int) (result % 100)), ns(now) - ns(then));
  return 0;
}

//real time:    60597 ns

int main(int argc, char *argv[]) {
    clock_gettime(CLOCK_REALTIME, &then);
    uint64_t num = atol(argv[1]), root = 100, old_root = 0;
    num *= 10000; //multiply by 10k because int is faster
    //and you only need 2 d.p. precision max. (for small numbers)
    while (old_root != root) {
        old_root = root;
        root = (root + num / root) / 2;
    }
    return output(root);
}
</code>```

timein:

```<code>#!/bin/bash

gcc -Wall $1 -lm -o $2 $2.c

./$2 $4

r=$(seq 1 $3)

for i in $r; do ./$2 $4; done > times

awk -v it=$3 '{ sum += $7 } END { print "\n" sum / (it) " ns" }' times

rm times
</code>```

Usage: ./timein '-march=native -O3' root <iterations> <number>

Inspired by this answer, uses this algorithm.

ContentLicense: CC BY-SA 3.0

Title: The fastest square root calculator

Body:
Write a program which outputs the square root of a given number in the shortest time possible.

Rules

It may not use any builtins or powering with non-integers.

Input format

as a function argument

as a command line argument

as a direct input on stdin or a window

Your entry hasn't to be a complete program, it may be a function or a snippet.

It doesn't need to be exact; a one percent margin of error is allowed.

The test cases will only be positive integers, but your program should output/return floats.

It may return the square root as function return value, print it to stdout or write in a consistent file, which is readable by the user..
Each program should specify the compiler/interpreter it should be run on and compiler flags. If they aren't specified, I'll use the following implementations: (just talking about mainstream langs):

C/C++: gcc/g++ on Linux, no flags

Java: OpenJDK on Linux, no flags

Python: CPython

Ruby: MRI

Assembler: x86 Linux

JS: Node.js

Examples

```<code>Input    Output
4        2 (or something between 1.98 and 2.02)
64       8 (between 7.92 and 8.08)
10000    100 (between 99 and 101)
2        bewteen 1.40001 and 1.428
</code>```

Scoring

Your programs on the same computer with same conditions (Terminal and Iceweasel with this tab open).
This question has the tag "Fastest code", so the program, which calculates the square root of a (not yet given) random integer between 1 and 10^10 as fast as possible will win!

Body:
C

Uses unsigned integers when possible for speed.

root.c:

#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ns(t) (1000000000 * t.tv_sec + t.tv_nsec)

struct timespec then, now;

int output(uint64_t result)
{
    clock_gettime(CLOCK_REALTIME, &now);
  printf("sqrt(x) = %10lu.%2d    real time:%9ld ns\n", result / 100, ((int) (result % 100)), ns(now) - ns(then));
  return 0;
}

//real time:    60597 ns

int main(int argc, char *argv[]) {
    clock_gettime(CLOCK_REALTIME, &then);
    uint64_t num = atol(argv[1]), root = 100, old_root = 0;
    num *= 10000; //multiply by 10k because int is faster
    //and you only need 2 d.p. precision max. (for small numbers)
    while (old_root != root) {
        old_root = root;
        root = (root + num / root) / 2;
    }
    return output(root);
}

timein:

#!/bin/bash

gcc -Wall $1 -lm -o $2 $2.c

./$2 $4

r=$(seq 1 $3)

for i in $r; do ./$2 $4; done > times

awk -v it=$3 '{ sum += $7 } END { print "\n" sum / (it) " ns" }' times

rm times

Usage: ./timein '-march=native -O3' root <iterations> <number>

Inspired by this answer, uses this algorithm.


答:
Python 3

Why am I using Python? Never mind.

def sqrt(n):
    # 3 iterations of newton's method, hard-coded
    # normalize

    # find highest bit
    highest = 1
    sqrt_highest = 1
    while highest < n:
        highest <<= 2
        sqrt_highest <<= 1

    n /= highest+0.0

    result = (n/4) + 1
    result = (result/2) + (n/(result*2))
    result = (result/2) + (n/(result*2))

    return result*sqrt_highest
```

Ideone it!

Title: The fastest square root calculator

Body:
Python 3

Why am I using Python? Never mind.

def sqrt(n):
    # 3 iterations of newton's method, hard-coded
    # normalize

    # find highest bit
    highest = 1
    sqrt_highest = 1
    while highest < n:
        highest <<= 2
        sqrt_highest <<= 1

    n /= highest+0.0

    result = (n/4) + 1
    result = (result/2) + (n/(result*2))
    result = (result/2) + (n/(result*2))

    return result*sqrt_highest

Ideone it!


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

Input

Well, obviously this challenge has no input.

Output

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

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

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

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

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

Boilerplate

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

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

Standard loopholes are disallowed.

Leaderboard

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

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

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

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

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

```

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

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

答:
Java, 335 bytes

The function is

```<code>void w()throws Exception{int w=100,h=72;BufferedImage i=new BufferedImage(w,h,1);Graphics g=i.getGraphics();g.setColor(new Color(18656));g.fillRect(0,0,w,h);g.setColor(WHITE);g.fillRect(0,28,w,16);g.fillRect(28,0,16,h);g.setColor(new Color(14100520));g.fillRect(0,32,w,8);g.fillRect(32,0,8,h);ImageIO.write(i,"png",new File("f.png"));}
</code>```

And it writes the desired image as f.png, with a size of 100x72

(Note that this is not a direct competitor to the Answer by R. Kap, because it writes a file, and does not display the image on the screen)

Here is the ungolfed version that can be compiled and run:

```<code>import static java.awt.Color.WHITE;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;

import javax.imageio.ImageIO;

public class Iceland
{
    public static void main(String[] args) throws Exception
    {
        Iceland i = new Iceland();
        i.w();
    }

    void w() throws Exception
    {
        int B=0x0048e0,R=0xd72828,w=100,h=72;
        BufferedImage i=new BufferedImage(w,h,1);
        Graphics g=i.getGraphics();
        g.setColor(new Color(B));
        g.fillRect(0,0,w,h);
        g.setColor(WHITE);
        g.fillRect(0,28,w,16);
        g.fillRect(28,0,16,h);
        g.setColor(new Color(R));
        g.fillRect(0,32,w,8);
        g.fillRect(32,0,8,h);
        ImageIO.write(i,"png",new File("f.png"));
    }
}
</code>```

A side note, regarding the related questions: Maybe one should create a challenge to paint the flags of

Indonesia

Poland

Finland

France

Netherlands

Thailand

Norway

at the same time:

Title: Draw the national flag of Iceland

Body:
Java, 335 bytes

The function is

void w()throws Exception{int w=100,h=72;BufferedImage i=new BufferedImage(w,h,1);Graphics g=i.getGraphics();g.setColor(new Color(18656));g.fillRect(0,0,w,h);g.setColor(WHITE);g.fillRect(0,28,w,16);g.fillRect(28,0,16,h);g.setColor(new Color(14100520));g.fillRect(0,32,w,8);g.fillRect(32,0,8,h);ImageIO.write(i,"png",new File("f.png"));}

And it writes the desired image as f.png, with a size of 100x72

(Note that this is not a direct competitor to the Answer by R. Kap, because it writes a file, and does not display the image on the screen)

Here is the ungolfed version that can be compiled and run:

import static java.awt.Color.WHITE;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;

import javax.imageio.ImageIO;

public class Iceland
{
    public static void main(String[] args) throws Exception
    {
        Iceland i = new Iceland();
        i.w();
    }

    void w() throws Exception
    {
        int B=0x0048e0,R=0xd72828,w=100,h=72;
        BufferedImage i=new BufferedImage(w,h,1);
        Graphics g=i.getGraphics();
        g.setColor(new Color(B));
        g.fillRect(0,0,w,h);
        g.setColor(WHITE);
        g.fillRect(0,28,w,16);
        g.fillRect(28,0,16,h);
        g.setColor(new Color(R));
        g.fillRect(0,32,w,8);
        g.fillRect(32,0,8,h);
        ImageIO.write(i,"png",new File("f.png"));
    }
}

A side note, regarding the related questions: Maybe one should create a challenge to paint the flags of

Indonesia

Poland

Finland

France

Netherlands

Thailand

Norway

at the same time:


问:
Recognize mod-folds

Task

Define a mod-fold as a function of the form f(x) = x % a1 % a2 % … % ak, where the ai are positive integers and k ≥ 0. (Here, % is the left-associative modulo operator.)

Given a list of n integers y0, …, yn−1,  determine if there exists a mod-fold f so that each yi = f(i).

You may choose and fix any two outputs Y and N for your function/program. If there exists such an f, you must always return/print exactly Y; if not, you must always return/print exactly N. (These could be true/false, or 1/0, or false/true, etc.) Mention these in your answer.

The shortest submission in bytes wins.

Example

Define f(x) = x % 7 % 3. Its values start:

```<code>|   x  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
| f(x) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | ...
</code>```

Thus, given 0 1 2 0 1 2 0 0 1 2 as input to our solution, we would print Y, as this f generates that sequence. However, given 0 1 0 1 2 as input, we would print N, as no f generates that sequence.

Test cases

The formulas given when the output is Y are just for reference; you must at no point print them.

```<code>0 1 2 3 4 5              Y    (x)
1                        N
0 0 0                    Y    (x%1)
0 1 2 0 1 2 0 0 1 2      Y    (x%7%3)
0 0 1                    N
0 1 2 3 4 5 6 0 0 1 2    Y    (x%8%7)
0 1 2 0 1 2 0 1 2 3      N
0 2 1 0 2 1 0 2 1        N
0 1 0 0 0 1 0 0 0 0 1    Y    (x%9%4%3%2)
</code>```

答:
Python 3, <s>239</s> 218 bytes

```<code>from itertools import*
lambda z:z in[[eval(''.join([str(l)]+['%'+str(i[::-1][k])for k in range(len(i))]))for l in range(len(z))]for i in(i for j in(combinations(range(1,len(z)+1),i+1)for i in range(len(z)))for i in j)]
</code>```

An anonymous function that takes input of a list z and returns True or False for Y and N.

This uses a method similar to @Jakube 's answer, and although it is essentially a brute force, runs very quickly.

```<code>from itertools import*               Import everything from the Python module for
                                     iterable generation
lambda z                             Anonymous function with input list z
combinations(range(1,len(z)+1),i+1)  Yield all sorted i+1 length subsets of the range
                                     [1,len(z)]...
...for i in range(len(z))            ...for all possible subset lengths
(i for j in(...)for i in j)          Flatten, yielding an iterator containing all possible
                                     mod-fold values as separate lists
...for i in...                       For all possible mod-fold values...
...for k in range(len(i))            ...for all mod-fold values indices k...
...for l in range(len(z))            ...for all function domain values in [0,len(z)-1]...
[str(l)]+['%'+str(i[::-1][k])...]    ...create a list containing each character of the
                                     expression representing the function defined by the
                                     mod-fold values (reversed such that the divisors
                                     decrease in magnitude) applied to the domain value...
 eval(''.join(...))                  ...concatenate to string and evaluate...
 [...]                               ...and pack all the values for that particular
                                     function as a list
 [...]                               Pack all lists representing all functions into a list
 ...:z in...                         If z is in this list, it must be a valid mod-fold, so
                                     return True. Else, return False
</code>```

Try it on Ideone

Title: Recognize mod-folds

Body:
Python 3, <s>239</s> 218 bytes

from itertools import*
lambda z:z in[[eval(''.join([str(l)]+['%'+str(i[::-1][k])for k in range(len(i))]))for l in range(len(z))]for i in(i for j in(combinations(range(1,len(z)+1),i+1)for i in range(len(z)))for i in j)]

An anonymous function that takes input of a list z and returns True or False for Y and N.

This uses a method similar to @Jakube 's answer, and although it is essentially a brute force, runs very quickly.

from itertools import*               Import everything from the Python module for
                                     iterable generation
lambda z                             Anonymous function with input list z
combinations(range(1,len(z)+1),i+1)  Yield all sorted i+1 length subsets of the range
                                     [1,len(z)]...
...for i in range(len(z))            ...for all possible subset lengths
(i for j in(...)for i in j)          Flatten, yielding an iterator containing all possible
                                     mod-fold values as separate lists
...for i in...                       For all possible mod-fold values...
...for k in range(len(i))            ...for all mod-fold values indices k...
...for l in range(len(z))            ...for all function domain values in [0,len(z)-1]...
[str(l)]+['%'+str(i[::-1][k])...]    ...create a list containing each character of the
                                     expression representing the function defined by the
                                     mod-fold values (reversed such that the divisors
                                     decrease in magnitude) applied to the domain value...
 eval(''.join(...))                  ...concatenate to string and evaluate...
 [...]                               ...and pack all the values for that particular
                                     function as a list
 [...]                               Pack all lists representing all functions into a list
 ...:z in...                         If z is in this list, it must be a valid mod-fold, so
                                     return True. Else, return False

Try it on Ideone


问:
Output the Juggler sequence
The Juggler sequence is described as follows. Beginning with an input \$a_1\$, the next term is defined by the recurrence relation

$$a_{k+1} = \begin{cases}
\left\lfloor a_k ^ \frac 1 2 \right\rfloor,\text{ if } a_k \text{ is even} \\
\left\lfloor a_k ^ \frac 3 2 \right\rfloor,\text{ if } a_k \text{ is odd} \\
\end{cases}$$

The sequence terminates when it reaches 1, as all subsequent terms would then be 1.

Task

Given an input \$n\$ greater than or equal to 2, write a program/function/generator/etc. that outputs/returns the respective juggler sequence. The output can be in any reasonable form. You may not use a built-in that computes the juggler sequence, or any built-in that directly yields the result. You may assume that the sequence terminates in \$1\$.

Test Cases

```<code>Input: output
2: 2, 1
3: 3, 5, 11, 36, 6, 2, 1
4: 4, 2, 1
5: 5, 11, 36, 6, 2, 1
</code>```

This is a code golf. Shortest code in bytes wins.

ContentLicense: CC BY-SA 4.0

Title: Output the Juggler sequence

Body:
C, <s>64</s> <s>63</s> 61 bytes

t;q(n){for(;!t;n=pow(n,.5+n%2))printf("%d%c ",n,n^1?44:t++);}


答:
C#, 62 bytes

```<code>string f(int n)=>n+(n<2?"":","+f((int)Math.Pow(n,.5+n%2)));
</code>```

Inspired by @user81655 and @Alex A., I used recursion.

Title: Output the Juggler sequence

Body:
The Juggler sequence is described as follows. Beginning with an input \$a_1\$, the next term is defined by the recurrence relation

$$a_{k+1} = \begin{cases}
\left\lfloor a_k ^ \frac 1 2 \right\rfloor,\text{ if } a_k \text{ is even} \\
\left\lfloor a_k ^ \frac 3 2 \right\rfloor,\text{ if } a_k \text{ is odd} \\
\end{cases}$$

The sequence terminates when it reaches 1, as all subsequent terms would then be 1.

Task

Given an input \$n\$ greater than or equal to 2, write a program/function/generator/etc. that outputs/returns the respective juggler sequence. The output can be in any reasonable form. You may not use a built-in that computes the juggler sequence, or any built-in that directly yields the result. You may assume that the sequence terminates in \$1\$.

Test Cases

```<code>Input: output
2: 2, 1
3: 3, 5, 11, 36, 6, 2, 1
4: 4, 2, 1
5: 5, 11, 36, 6, 2, 1
</code>```

This is a code golf. Shortest code in bytes wins.

Body:
C#, 62 bytes

string f(int n)=>n+(n<2?"":","+f((int)Math.Pow(n,.5+n%2)));

Inspired by @user81655 and @Alex A., I used recursion.


问:
Golf the K-means algorithm
K-means is a standard unsupervised clustering algorithm, which, given a set of "points" and a number of clusters K, will assign each "point" to one of K clusters.

Pseudo-Code of K-means

Note that there are many variants of K-means. You have to implement the algorithm I am describing below. You may have some variation on the algorithm or use built-ins as long as you would get the same result as this algorithm given the same initial points.

In this challenge, all inputs will be points on the 2D plane (each point is represented by its coordinates in x and y).

```<code>Inputs: K, the number of clusters
        P, the set of points

Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster

Loop:
     For each point in P:
         Assign to the cluster whose centroid is the nearest (Euclidean distance)
         In case of a tie, any of the tied cluster can be chosen

     Recompute the centroid of each cluster:
         Its x coordinate is the average of all x's of the points in the cluster
         Its y coordinate is the average of all y's of the points in the cluster

Until the clusters don't change from one iteration to the next

Output: the set of clusters
</code>```

Inputs and Outputs

You may take K and P through STDIN, or as a function argument, etc.

P and the points in P can be represented using any structure that is natural for set/lists in your language of choice.

K is a strictly positive integer.

You may assume that inputs are valid.

There will always be at least K points in P.

You may output the clusters to STDOUT, return them from a function, etc.

The ordering of the clusters and the ordering inside the clusters is unimportant.
-You can either return groups of points to represent clusters, or each point labeled with an identifier for the cluster (e.g. an integer).

Test cases

Since the resulting clusters depend on which points were initially chosen, you may not all get the same results (or the same result each time you run your code).

Therefore, only take the output as an example output.

```<code>Input:
  K = 1
  P = [[1,2.5]]
Output:
  [[[1,2.5]]]

Input:
  K = 3
  P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
  [[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]

Input:
  K = 2
  P = [[1,1], [1,1], [1,1]]
Output:
  [[[1,1]],[[1,1],[1,1]]]
</code>```

Scoring

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

答:
J, <s>60</s> 54 bytes

```<code>p=:[:(i.<./)"1([:+/&.:*:-)"1/
]p](p(+/%#)/.[)^:_(?#){]
</code>```

Defines a helper verb p which takes a list of points and centroids and classifies each point by the index of the nearest centroid. Then, it uses that to repeat the process of choosing new centroid by taking the averages of the points in each cluster until it converges, and then to partition the points for output.

Usage

The value of k is given as an integer on the LHS. The list of points is given as a 2d array on the RHS. Here it is specified as a list of points which is reshaped into a 2d array of 5 x 2. The output will be the label for which cluster each point belongs in the same order as the input.

If you desire to use a fixed seed for reproducible results, replace the ? with a ?. at (?#).

```<code>   p =: [:(i.<./)"1([:+/&.:*:-)"1/
   f =: ]p](p(+/%#)/.[)^:_(?#){]
   3 f (5 2 $ 4 8 15 16 23 42 _13.37 _12.1 666 _666)
0 1 1 0 2
</code>```

Explanation

```<code>[:(i.<./)"1([:+/&.:*:-)"1/  Input: points on LHS, centroids on RHS
           (          )"1/  Form a table between each point and centroid and for each
                     -        Find the difference elementwise
            [:     *:         Square each
              +/&.:           Reduce using addition
                              Apply the inverse of square (square root) to that sum
[:(     )"1                 For each row of that table
     <./                      Reduce using min
   i.                         Find the index of the minimum in that row
                            Returns a list of indices for each point that shows
                            which centroid it belongs to

]p](p(+/%#)/.[)^:_(?#){]  Input: k on LHS, points on RHS
                    #     Count the number of points
                   ?      Choose k values in the range [0, len(points))
                          without repetition
                       ]  Identity function, get points
                      {   Select the points at the indices above
  ]                       Identity function, get points
   (         )^:_         Repeat until convergence
    p                       Get the labels for each point
             [              Identity function, get points
           /.               Partition the points using the labels and for each
      +/                      Take the sums of points elementwise
         #                    Get the number of points
        %                     Divide sum elementwise by the count
                            Return the new values as the next centroids
]                         Identity function, get points
 p                        Get the labels for each point and return it
</code>```

Title: Golf the K-means algorithm

Body:
J, <s>60</s> 54 bytes

p=:[:(i.<./)"1([:+/&.:*:-)"1/
]p](p(+/%#)/.[)^:_(?#){]

Defines a helper verb p which takes a list of points and centroids and classifies each point by the index of the nearest centroid. Then, it uses that to repeat the process of choosing new centroid by taking the averages of the points in each cluster until it converges, and then to partition the points for output.

Usage

The value of k is given as an integer on the LHS. The list of points is given as a 2d array on the RHS. Here it is specified as a list of points which is reshaped into a 2d array of 5 x 2. The output will be the label for which cluster each point belongs in the same order as the input.

If you desire to use a fixed seed for reproducible results, replace the ? with a ?. at (?#).

   p =: [:(i.<./)"1([:+/&.:*:-)"1/
   f =: ]p](p(+/%#)/.[)^:_(?#){]
   3 f (5 2 $ 4 8 15 16 23 42 _13.37 _12.1 666 _666)
0 1 1 0 2

Explanation

[:(i.<./)"1([:+/&.:*:-)"1/  Input: points on LHS, centroids on RHS
           (          )"1/  Form a table between each point and centroid and for each
                     -        Find the difference elementwise
            [:     *:         Square each
              +/&.:           Reduce using addition
                              Apply the inverse of square (square root) to that sum
[:(     )"1                 For each row of that table
     <./                      Reduce using min
   i.                         Find the index of the minimum in that row
                            Returns a list of indices for each point that shows
                            which centroid it belongs to

]p](p(+/%#)/.[)^:_(?#){]  Input: k on LHS, points on RHS
                    #     Count the number of points
                   ?      Choose k values in the range [0, len(points))
                          without repetition
                       ]  Identity function, get points
                      {   Select the points at the indices above
  ]                       Identity function, get points
   (         )^:_         Repeat until convergence
    p                       Get the labels for each point
             [              Identity function, get points
           /.               Partition the points using the labels and for each
      +/                      Take the sums of points elementwise
         #                    Get the number of points
        %                     Divide sum elementwise by the count
                            Return the new values as the next centroids
]                         Identity function, get points
 p                        Get the labels for each point and return it


Title: Golf the K-means algorithm

Body:
K-means is a standard unsupervised clustering algorithm, which, given a set of "points" and a number of clusters K, will assign each "point" to one of K clusters.

Pseudo-Code of K-means

Note that there are many variants of K-means. You have to implement the algorithm I am describing below. You may have some variation on the algorithm or use built-ins as long as you would get the same result as this algorithm given the same initial points.

In this challenge, all inputs will be points on the 2D plane (each point is represented by its coordinates in x and y).

```<code>Inputs: K, the number of clusters
        P, the set of points

Choose K points of P uniformly at random
Each chosen point is the initial centroid of its cluster

Loop:
     For each point in P:
         Assign to the cluster whose centroid is the nearest (Euclidean distance)
         In case of a tie, any of the tied cluster can be chosen

     Recompute the centroid of each cluster:
         Its x coordinate is the average of all x's of the points in the cluster
         Its y coordinate is the average of all y's of the points in the cluster

Until the clusters don't change from one iteration to the next

Output: the set of clusters
</code>```

Inputs and Outputs

You may take K and P through STDIN, or as a function argument, etc.

P and the points in P can be represented using any structure that is natural for set/lists in your language of choice.

K is a strictly positive integer.

You may assume that inputs are valid.

There will always be at least K points in P.

You may output the clusters to STDOUT, return them from a function, etc.

The ordering of the clusters and the ordering inside the clusters is unimportant.
-You can either return groups of points to represent clusters, or each point labeled with an identifier for the cluster (e.g. an integer).

Test cases

Since the resulting clusters depend on which points were initially chosen, you may not all get the same results (or the same result each time you run your code).

Therefore, only take the output as an example output.

```<code>Input:
  K = 1
  P = [[1,2.5]]
Output:
  [[[1,2.5]]]

Input:
  K = 3
  P = [[4,8], [15,16], [23,42], [-13.37,-12.1], [666,-666]]
Output:
  [[[666,-666]],[[-13.37,-12.1],[4,8]],[[15,16],[23,42]]]

Input:
  K = 2
  P = [[1,1], [1,1], [1,1]]
Output:
  [[[1,1]],[[1,1],[1,1]]]
</code>```

Scoring

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

Body:
Mathematica <s>14</s> 12 bytes

Since built-ins are allowed, this should do it.

FindClusters

Example

FindClusters[{{4, 8}, {15, 16}, {23, 42}, {-13.37, -12.1}, {666, -666}}, 3]

{{{4, 8}, {-13.37, -12.1}}, {{15, 16}, {23, 42}}, {{666, -666}}}


问:
Is it a pangram?
Write a function or program that takes as its input a string and prints a truthy value if the string is a pangram (a sequence of letters containing at least one of each letter in the English alphabet) and a falsey value otherwise.

Case of letters should be ignored; If the string is abcdefghijklmnopqrstuvwXYZ, then the function should still return a truthy value. Note that the string can contain any other characters in it, so 123abcdefghijklm NOPQRSTUVWXYZ321 would return a truthy value. An empty input should return a falsey value.

Test cases

```<code>AbCdEfGhIjKlMnOpQrStUvWxYz

==> True

ACEGIKMOQSUWY
BDFHJLNPRTVXZ

==> True

public static void main(String[] args)

==> False

The quick brown fox jumped over the lazy dogs. BOING BOING BOING

==> True
</code>```

This is code golf. Standard rules apply. Shortest code in bytes wins.

答:
32-bit x86 machine code, 27 bytes

In hex:

```<code>31c031d2ac48780d344024df3c1977f40fabc2ebef31d0c1e006c3
</code>```

Input: ESI: NULL-terminated string. Returns: EFLAGS.ZF (1=truthy, 0=falsey).

```<code>0:  31 c0               xor eax, eax
2:  31 d2               xor edx, edx  ;Bit array to keep track of letters
_loop :
4:  ac                  lodsb         ;Read next char
5:  48                  dec eax       ;Align 'A' to the power of two boundary, i.e. 0x40
6:  78 0d               js _break     ;...which also tests for NULL
8:  34 40               xor al, 0x40  ;Swap block [0x40..0x7f] (with letters) with [0..0x3f]
a:  24 df               and al, 0xdf  ;Map [0x60..0x7f] to [0x40..0x5f], that's toupper()
c:  3c 19               cmp al, 25    ;Letter are now in the [0..25] range
e:  77 f4               ja _loop      ;Anything else is greater if taken as unsigned
10: 0f ab c2            bts edx, eax  ;Set AL-th bit in EDX
13: eb ef               jmp _loop
_break :
15: 31 d0               xor eax, edx  ;EAX=~EDX (EAX==-1 here), for pangram EDX==0x03FFFFFF
17: c1 e0 06            shl eax, 6    ;Shift out 6 unused bits. EFLAGS.ZF=EAX<<6==0?1:0
1a: c3                  ret
</code>```

Title: Is it a pangram?

Body:
32-bit x86 machine code, 27 bytes

In hex:

31c031d2ac48780d344024df3c1977f40fabc2ebef31d0c1e006c3

Input: ESI: NULL-terminated string. Returns: EFLAGS.ZF (1=truthy, 0=falsey).

0:  31 c0               xor eax, eax
2:  31 d2               xor edx, edx  ;Bit array to keep track of letters
_loop :
4:  ac                  lodsb         ;Read next char
5:  48                  dec eax       ;Align 'A' to the power of two boundary, i.e. 0x40
6:  78 0d               js _break     ;...which also tests for NULL
8:  34 40               xor al, 0x40  ;Swap block [0x40..0x7f] (with letters) with [0..0x3f]
a:  24 df               and al, 0xdf  ;Map [0x60..0x7f] to [0x40..0x5f], that's toupper()
c:  3c 19               cmp al, 25    ;Letter are now in the [0..25] range
e:  77 f4               ja _loop      ;Anything else is greater if taken as unsigned
10: 0f ab c2            bts edx, eax  ;Set AL-th bit in EDX
13: eb ef               jmp _loop
_break :
15: 31 d0               xor eax, edx  ;EAX=~EDX (EAX==-1 here), for pangram EDX==0x03FFFFFF
17: c1 e0 06            shl eax, 6    ;Shift out 6 unused bits. EFLAGS.ZF=EAX<<6==0?1:0
1a: c3                  ret


问:
Fibonacci reversed!

Introduction

We all know and love our Fibonacci sequence and have seen a myriad of challenge on it here already. However, we're still lacking a very simple case which this answer is going to provide: Reversed fibonacci! So given F_n your job is to find n.

Specification

Input

Your input will be a non-negative integer, which is guaranteed to be part of the fibonacci sequence.

Output

The output must be a non-negative integer as well.

What to do?

The introduction already said: Given a fibonacci number, output its index. Fiboancci number hereby is defined as F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) and you're given F(n) and must return n.

Potential Corner Cases

0 is a valid in- and output.

If given "1" as input you may either output "1" or "2", as you prefer.

You may always assume that your input actually is a fibonacci number.

You may assume that the input is representable as a 32-bit signed integer.

Who wins?

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

Standard rules apply of course.

Test-cases

```<code>0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
</code>```

答:
Actually, 1 byte

```<code>f
</code>```

Yes, there's a builtin for this, since November 16, 2015.

Try it online

For fun, without the builtin, it's 9 bytes:

```<code>╗1`F╜=`╓i
</code>```

Try it online!

Explanation:

```<code>╗1`F╜=`╓i
╗          push input to register 0
 1`F╜=`╓   push list containing first value x (starting with x = 0) where:
   F         fib(x)
    ╜=       is equal to the input
        i  flatten the list
</code>```

Title: Fibonacci reversed!

Body:
Actually, 1 byte

f

Yes, there's a builtin for this, since November 16, 2015.

Try it online

For fun, without the builtin, it's 9 bytes:

╗1`F╜=`╓i

Try it online!

Explanation:

╗1`F╜=`╓i
╗          push input to register 0
 1`F╜=`╓   push list containing first value x (starting with x = 0) where:
   F         fib(x)
    ╜=       is equal to the input
        i  flatten the list


答:
Pyke, 5 bytes

```<code>.f.bq
</code>```

Try it here!

```<code>.f    - first number where
  .b  -  fib(n)
    q - ^ == input
</code>```

Title: Fibonacci reversed!

Body:
Introduction

We all know and love our Fibonacci sequence and have seen a myriad of challenge on it here already. However, we're still lacking a very simple case which this answer is going to provide: Reversed fibonacci! So given F_n your job is to find n.

Specification

Input

Your input will be a non-negative integer, which is guaranteed to be part of the fibonacci sequence.

Output

The output must be a non-negative integer as well.

What to do?

The introduction already said: Given a fibonacci number, output its index. Fiboancci number hereby is defined as F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) and you're given F(n) and must return n.

Potential Corner Cases

0 is a valid in- and output.

If given "1" as input you may either output "1" or "2", as you prefer.

You may always assume that your input actually is a fibonacci number.

You may assume that the input is representable as a 32-bit signed integer.

Who wins?

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

Standard rules apply of course.

Test-cases

```<code>0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
</code>```

Body:
Pyke, 5 bytes

.f.bq

Try it here!

.f    - first number where
  .b  -  fib(n)
    q - ^ == input


问:
m3ph1st0s's programming puzzle 3 (C): “Easy bug”
This is the 3rd of my series of C/C++ puzzles; in case you missed the first 2 they are here:
(1) m3ph1st0s's programming puzzle 1 (C++)
(2) m3ph1st0s's programming puzzle 2 (C++): "Call hard!"

I must say that my puzzles are 100% original. If not, I will always state so in the text.
 My 3rd puzzle has 2 parts as follows:

Puzzle 3.1

This part (3.1) is not an original puzzle of mine, it is collected from some internet page I've read a while ago. I use it here as a starting point and a warm-up for you. Solve this one and then move on to the 2nd part.

Some one tried to print the "+" sign 20 times and came up with the following program:

```<code>#include <stdio.h>
int main() {
   int i;
   int n = 20;
   for( i = 0; i < n; i-- )
      printf("+");
   return 0;
}
</code>```

The fact that it did not have the expected result is obvious - the program never ends. Fix it!
Easy?
Now fix the program by changing ONLY ONE CHARACTER - non-space character of course! For this challenge there are 3 solutions. Find all 3 of them. Just to make it clear: the program must output 20 "+" signs and must end fast. Before criticizing me on what "fast" means, I'll say it means at most a couple of seconds (which by the way is too much but just to make it crystal clear).

Puzzle 3.2

EDITED
It was pointed to me earlier that the solution for the 3.2.2 puzzle might be compiler-dependent. In order to eliminate any possible discussion on the subject, I'll modify the idea and improve it on a next puzzle when I'll take extra care not to generate controversy.
 However, in order to keep this puzzle going, I'll make a small modification for 3.2.2 (the solution will be easier but cleaner).

When I first saw the puzzle I found it pretty awesome. I did manage to solve it but not immediately since it requires some careful attention.
 If you are here it means you too solved it. If you did so by writing a program to replace all possible characters with all possible values and test every solution, you are lost. Hard working guy though.
 Now having corrected the program that writes 20 "+" signs:

3.2.1: Insert one single letter and nothing more in the code so that the result is valid and outputs the same thing in all 3 corrected programs. Needless to say, the letter must be before the enclosing } of main (I say that because I don't want to hear people who just put a letter after the program and somehow their compiler was very friendly).

EDITED (see bellow) - For these final questions consider that the counter i starts from -1 instead of 0.

3.2.1.5: Repeat all previous problems with the condition that the output is at least 19 "+" signs (but still a finite output). Changing spaces is allowed. Now you might have found more solutions than in the first case. Some of these will most definitely fit for the 3.2.2 question.

3.2.2: Choose another value to initialize the variable n so that the resulting output will remain the same for at least one corrected programs in 3.2.1.5(not necessarily for all of them).

LAST EDIT1: changing the program so that it outputs 21 "+" signs is still a good solution, as the original text did not say "exactly" 20 signs. However, the infinite output is forbidden. Obviously this doesn't mean let's all start outputting hundreds of "+"signs since it's not forbidden. But eliminating a beautiful 21 output would not be in the spirit of this competition.

LAST EDIT2: considering LAST EDIT1 and accepting space changing it seems that now we have 5 possible solutions, four of which have already been pointed out in the responses. The last challenge however hasn't been touched and I must make it clear once more: n must be assigned another value, solutions that assign 20 to n by some tricks won't do it (like n=20L). Also I prefer to see the 3rd solution that does not change spaces.

LAST EDIT3: I've edited the last questions, please read!

The challenge is to solve both parts of the puzzle. The first one to do it wins.

I hope it's all clear, if not please post any questions and I'll edit as quickly as possible. Cheers.
emphasized text

答:
3.1

```<code>for( i = 0;-i < n; i-- )
for( i = 0; i < n; n-- )
for( i = 0; i + n; i-- )
</code>```

Any of these changes will make the program output 20 '+' signs. This one is close:

```<code>for( i = 0;~i < n; i-- )
</code>```

It outputs 21 '+' signs.

3.2.1

I found at least 112 ways to solve this problem inserting one letter. Not all of them may work on all compilers.

```<code>int n = 20L;
int n = 20f;
int n = 20d;
uint n = 20;

for( i = 0L; ... )
for( i = 0f; ... )
for( i = 0d; ... )

iprintf("+");
printf("+x");
printf("x+");
</code>```

For the last two, substitute any letter for x to give you 104 possible solutions. Using either of the last two lines will change the output, but the output will still be the same for all 3 corrected programs.

3.2.2

All I've come up with are some things that get cast back to the number 20 on assignment to int.

```<code>int n = 20L;
int n = 20.001;
int n = 20.999;
int n = 20 + 0x100000000L;
</code>```

Body:
3.1

for( i = 0;-i < n; i-- )
for( i = 0; i < n; n-- )
for( i = 0; i + n; i-- )

Any of these changes will make the program output 20 '+' signs. This one is close:

for( i = 0;~i < n; i-- )

It outputs 21 '+' signs.

3.2.1

I found at least 112 ways to solve this problem inserting one letter. Not all of them may work on all compilers.

int n = 20L;
int n = 20f;
int n = 20d;
uint n = 20;

for( i = 0L; ... )
for( i = 0f; ... )
for( i = 0d; ... )

iprintf("+");
printf("+x");
printf("x+");

For the last two, substitute any letter for x to give you 104 possible solutions. Using either of the last two lines will change the output, but the output will still be the same for all 3 corrected programs.

3.2.2

All I've come up with are some things that get cast back to the number 20 on assignment to int.

int n = 20L;
int n = 20.001;
int n = 20.999;
int n = 20 + 0x100000000L;


答:
Mathematica, 25 bytes

```<code>InverseFunction@Fibonacci
</code>```

Function. Pretty self-explanatory if you ask me.

Title: Fibonacci reversed!

Body:
Mathematica, 25 bytes

InverseFunction@Fibonacci

Function. Pretty self-explanatory if you ask me.


答:
05AB1E, 3 bytes

Code:

```<code>ÅFg
</code>```

Explanation:

```<code>ÅF   # Generate all Fibonacci numbers <= input.
  g  # Get the length of this list.
</code>```

Uses the CP-1252 encoding. Try it online!.

Title: Fibonacci reversed!

Body:
05AB1E, 3 bytes

Code:

ÅFg

Explanation:

ÅF   # Generate all Fibonacci numbers <= input.
  g  # Get the length of this list.

Uses the CP-1252 encoding. Try it online!.


答:
JavaScript, <s>54</s> <s>50</s> <s>69</s> <s>50</s> 42 bytes

```<code>b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c
</code>```

Surely it isn't going to win, just for fun :)

<s>Ok, checking for zero consumes 19 bytes. WTF?</s> Stupid-me.

Demo! To see the last test case, you have to scroll the console a bit.

a=b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c;
console.log('0: '+a(0));
console.log('2: '+a(2));
console.log('3: '+a(3));
console.log('5: '+a(5));
console.log('8: '+a(8));
console.log('13: '+a(13));
console.log('1836311903: '+a(1836311903));```

Thanks @edc for shortening by 8 bytes.

Title: Fibonacci reversed!

Body:
JavaScript, <s>54</s> <s>50</s> <s>69</s> <s>50</s> 42 bytes

b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c

Surely it isn't going to win, just for fun :)

<s>Ok, checking for zero consumes 19 bytes. WTF?</s> Stupid-me.

Demo! To see the last test case, you have to scroll the console a bit.

a=b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c;
console.log('0: '+a(0));
console.log('2: '+a(2));
console.log('3: '+a(3));
console.log('5: '+a(5));
console.log('8: '+a(8));
console.log('13: '+a(13));
console.log('1836311903: '+a(1836311903));

Thanks @edc for shortening by 8 bytes.


答:
MATL, 14 bytes

```<code>t?5X^*17L&YlYo
</code>```

Try it online!

This uses an inverse of Binet's formula, and so it's very fast.

Let F denote the n-th Fibonacci number, and φ the golden ratio. Then

The code uses this formula with two modifications:

Instead of adding 1/2 and then rounding down, the code simply rounds towards the nearest integer, which takes up fewer bytes.

Input F=0 needs to be treated as a special case.

How it's done

```<code>t         % Take input F implicitly. Make a copy
?         % If (copy of) F is positive
  5X^     %   Push sqrt(5)
  *       %   Multiply by F
  17L     %   Push phi (predefined literal)
  &Yl     %   Two-input logarithm: first input is argument, second is base
  Yo      %   Round towards nearest integer
          % Else the input, which is 0, is left on the stack
          % End if implicitly
          % Display implicitly
</code>```

Title: Fibonacci reversed!

Body:
MATL, 14 bytes

t?5X^*17L&YlYo

Try it online!

This uses an inverse of Binet's formula, and so it's very fast.

Let F denote the n-th Fibonacci number, and φ the golden ratio. Then

The code uses this formula with two modifications:

Instead of adding 1/2 and then rounding down, the code simply rounds towards the nearest integer, which takes up fewer bytes.

Input F=0 needs to be treated as a special case.

How it's done

t         % Take input F implicitly. Make a copy
?         % If (copy of) F is positive
  5X^     %   Push sqrt(5)
  *       %   Multiply by F
  17L     %   Push phi (predefined literal)
  &Yl     %   Two-input logarithm: first input is argument, second is base
  Yo      %   Round towards nearest integer
          % Else the input, which is 0, is left on the stack
          % End if implicitly
          % Display implicitly


答:
Sage, 49 bytes

lambda x,s=sqrt(5):x and int(log(x*s,(1+s)/2)+.5)
```

Thanks to TuukkaX for the suggestion about saving sqrt(5) as s to shave off a few bytes.

Try it online.

This approach using an inverse of Binet's formula offers several improvements over the previous approach: it's faster (constant-time versus quadratic time), it actually works for larger inputs, and it's shorter!

Python users may wonder why I'm using sqrt(5) instead of the shorter 5**.5 - it's because 5**.5 is computed with C's pow function, and loses precision due to floating point issues. Many mathematical functions (including sqrt and log) are overloaded in Sage to return an exact, symbolic value, which don't lose precision.

Title: Fibonacci reversed!

Body:
Sage, 49 bytes

lambda x,s=sqrt(5):x and int(log(x*s,(1+s)/2)+.5)

Thanks to TuukkaX for the suggestion about saving sqrt(5) as s to shave off a few bytes.

Try it online.

This approach using an inverse of Binet's formula offers several improvements over the previous approach: it's faster (constant-time versus quadratic time), it actually works for larger inputs, and it's shorter!

Python users may wonder why I'm using sqrt(5) instead of the shorter 5**.5 - it's because 5**.5 is computed with C's pow function, and loses precision due to floating point issues. Many mathematical functions (including sqrt and log) are overloaded in Sage to return an exact, symbolic value, which don't lose precision.


问:
"Hello, World!"
So... uh... this is a bit embarrassing. But we don't have a plain "Hello, World!" challenge yet (despite having 35 variants tagged with hello-world, and counting). While this is not the most interesting code golf in the common languages, finding the shortest solution in certain esolangs can be a serious challenge. For instance, to my knowledge it is not known whether the shortest possible Brainfuck solution has been found yet.

Furthermore, while all of <s>Wikipedia</s> (the Wikipedia entry has been deleted but there is a copy at archive.org
), esolangs and Rosetta Code have lists of "Hello, World!" programs, none of these are interested in having the shortest for each language (there is also this GitHub repository). If we want to be a significant site in the code golf community, I think we should try and create the ultimate catalogue of shortest "Hello, World!" programs (similar to how our basic quine challenge contains some of the shortest known quines in various languages). So let's do this!

The Rules

Each submission must be a full program.

The program must take no input, and print Hello, World! to STDOUT (this exact byte stream, including capitalization and punctuation) plus an optional trailing newline, and nothing else.

The program must not write anything to STDERR.

If anyone wants to abuse this by creating a language where the empty program prints Hello, World!, then congrats, they just paved the way for a very boring answer.

Note that there must be an interpreter so the submission can be tested. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language.

Submissions are scored in bytes, in an appropriate (pre-existing) encoding, usually (but not necessarily) UTF-8. Some languages, like Folders, are a bit tricky to score - if in doubt, please ask on Meta.

This is not about finding the language with the shortest "Hello, World!" program. This is about finding the shortest "Hello, World!" program in every language. Therefore, I will not mark any answer as "accepted".

If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck-derivatives like Alphuck), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.

As a side note, please don't downvote boring (but valid) answers in languages where there is not much to golf - these are still useful to this question as it tries to compile a catalogue as complete as possible. However, do primarily upvote answers in languages where the authors actually had to put effort into golfing the code.

For inspiration, check the Hello World Collection.

The Catalogue

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

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

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

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

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

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

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

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

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

/* Configuration */

var QUESTION_ID = 55422; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 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 "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\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;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 500px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}</code>```

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

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

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

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

```

答:
Commercial, 75 bytes

I post a link to my implementation, but there is a link to the esolang page in the README

```<code>"Hello, World!" - Satisfied Consumer of x
x has been selling out worldwide!
</code>```

This code is equivalent to the following pseudocode

```<code>Put "Hello, World!" in x
Print the value of x
</code>```

Title: "Hello, World!"

Body:
Commercial, 75 bytes

I post a link to my implementation, but there is a link to the esolang page in the README

"Hello, World!" - Satisfied Consumer of x
x has been selling out worldwide!

This code is equivalent to the following pseudocode

Put "Hello, World!" in x
Print the value of x


答:
Python 2, <s>103</s> 99 bytes

f=lambda l,r:r==x or l and f(l-1,[t%l for t in r])|f(l-1,r)
x=input();l=len(x);print+f(l,range(l))
```

Prints 1 for truthy and 0 for falsy. Test it on Ideone.

Title: Recognize mod-folds

Body:
Task

Define a mod-fold as a function of the form f(x) = x % a1 % a2 % … % ak, where the ai are positive integers and k ≥ 0. (Here, % is the left-associative modulo operator.)

Given a list of n integers y0, …, yn−1,  determine if there exists a mod-fold f so that each yi = f(i).

You may choose and fix any two outputs Y and N for your function/program. If there exists such an f, you must always return/print exactly Y; if not, you must always return/print exactly N. (These could be true/false, or 1/0, or false/true, etc.) Mention these in your answer.

The shortest submission in bytes wins.

Example

Define f(x) = x % 7 % 3. Its values start:

```<code>|   x  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
| f(x) | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | ...
</code>```

Thus, given 0 1 2 0 1 2 0 0 1 2 as input to our solution, we would print Y, as this f generates that sequence. However, given 0 1 0 1 2 as input, we would print N, as no f generates that sequence.

Test cases

The formulas given when the output is Y are just for reference; you must at no point print them.

```<code>0 1 2 3 4 5              Y    (x)
1                        N
0 0 0                    Y    (x%1)
0 1 2 0 1 2 0 0 1 2      Y    (x%7%3)
0 0 1                    N
0 1 2 3 4 5 6 0 0 1 2    Y    (x%8%7)
0 1 2 0 1 2 0 1 2 3      N
0 2 1 0 2 1 0 2 1        N
0 1 0 0 0 1 0 0 0 0 1    Y    (x%9%4%3%2)
</code>```

Body:
Python 2, <s>103</s> 99 bytes

f=lambda l,r:r==x or l and f(l-1,[t%l for t in r])|f(l-1,r)
x=input();l=len(x);print+f(l,range(l))

Prints 1 for truthy and 0 for falsy. Test it on Ideone.


Title: Fibonacci reversed!

Body:
JavaScript (ES6), <s>39</s> 33 bytes

f=(n,j=0,k=1)=>n>j?f(n,k,j+k)+1:0

Even with ES7, the inverse Binet formula takes 47 bytes:

x=>Math.log(x*5**.5)/Math.log(.5+1.25**.5)+.5|0
x=>Math.log(x*5**.5)/Math.log((1+5**.5)/2)+.5|0
x=>Math.log(x*(p=5**.5))/Math.log((1+p)/2)+.5|0


答:
Jelly, 8 bytes

```<code>1+Ð¡0
¢i
</code>```

Try it online! Note that this approach is too inefficient for the last test case.

How it works

```<code>¢i     Main link. Argument: n

¢      Call the helper link niladically (i.e., without arguments).
       This yields the sequence of the first n positive Fibonacci numbers, i.e.,
       [1, 1, 2, 3, 5, ...].
 i     Find the first index of n (1-based, 0 if not found).

1+Ð¡0  Helper link. No arguments.

1      Set the left argument to 1.
    0  Yield 0.
 +Ð¡   Add both arguments, replacing the left argument with the sum and the right
       argument with the previous value of the left argument.
       Yield the array of all intermediate values of the left argument.
</code>```

Title: Fibonacci reversed!

Body:
Jelly, 8 bytes

1+Ð¡0
¢i

Try it online! Note that this approach is too inefficient for the last test case.

How it works

¢i     Main link. Argument: n

¢      Call the helper link niladically (i.e., without arguments).
       This yields the sequence of the first n positive Fibonacci numbers, i.e.,
       [1, 1, 2, 3, 5, ...].
 i     Find the first index of n (1-based, 0 if not found).

1+Ð¡0  Helper link. No arguments.

1      Set the left argument to 1.
    0  Yield 0.
 +Ð¡   Add both arguments, replacing the left argument with the sum and the right
       argument with the previous value of the left argument.
       Yield the array of all intermediate values of the left argument.


答:
Python, 38 bytes

f=lambda n,a=0,b=1:n^a and-~f(n,b,a+b)
```

Test it on Ideone.

Title: Fibonacci reversed!

Body:
Python, 38 bytes

f=lambda n,a=0,b=1:n^a and-~f(n,b,a+b)

Test it on Ideone.


问:
Code Golf Bingo!
You are given a Bingo board and a list of calls.  You must print BINGO! as soon as your board wins the game.

Bingo boards look like this:

They will be specified like this:

```<code>14 29 38 52 74
4 18 33 46 62
7 16 * 60 71
9 27 44 51 67
12 23 35 47 73
</code>```

Immediately following the board will be calls, like this:

```<code>B7
I29
G60
G51
O71
I23
I16
N38
</code>```

You must echo the calls out to standard output until just after the call that makes you win (get a row, column, or 5-long diagonal all filled), then print BINGO!.

For the above example, print:

```<code>B7
I29
G60
G51
O71
I23
I16
BINGO!
</code>```

Rules

Standard code-golf rules, shortest code wins.

Details

There will always be enough calls to guarantee you a Bingo.  There will be no duplicate numbers on the board, and no duplicate calls.  Boards will always have correctly matched numbers and letters (the B column contains only 1-15, the I column contains only 16-30, and so on), as will calls.  The one and only free space will always be in the middle, marked with * instead of a number.  Consuming and discarding calls from standard input after the winning call is allowed, but not required.

Make your own test cases!

答:
Given the long, long, long overdue announcement of Rebol's impending release as open source software, I returned to my pet dialect to solve this Bingo problem.  I may soon be able to distribute Rebmu as its own, teensy GPL package.  :)

Rebmu 88 characters

In the compact notation:

```<code>rtZ5[GisGpcRaZisGaAPgPCaSB6zAPv'*]l5[AgL5[apGfAsk+A5]]hd+Gu[raGin-NTrM'*fisGv5]p"BINGO!"
</code>```

The dialect uses a trick I call mushing which is explained on the Rebmu page.  It's "legit" in the sense that it doesn't cheat the parser; this is valid Rebol...and can actually can be freely intermingled with ordinary code as well as (ahem) "long-form" Rebmu...which BTW would be 141 characters:

[rt z 5 [g: is g pc r a z is g a ap g pc a sb 6 z ap v '*] l 5 [a: g l 5 [ap g f a sk+ a 5]] hd+ g u [ra g in- nt r m '* fis g v 5] p "BINGO!"]

(Given that I claim the compression is a trick that one can do without the help of automation or compilation, I actually develop the code in the mushed form.  It's not difficult.)

It's actually quite simple, nothing special--I'm sure other Rebol programmers could shave things off.  Some  commented source is on GitHub, but the main trick I use is to build all the possible solutions in a long series ("list", "array", what-have-you).  I  build the diagonal solutions during the input loop, as it takes five insertions at the head and five appends at the tail to make them...and there's already a five-iteration loop in progress.

The whole thing easily maps to Rebol code, and I haven't yet thrown any "matrix libraries" into Rebmu with transposition or other gimmicks that seem to come up often.  Someday I will do that but for now I'm just trying to work relatively close to the medium of Rebol itself.  Cryptic-looking things like:

```<code> [g: is g pc r a z is g a ap g pc a sb 6 z ap v '*]
</code>```

...are rather simple:

```<code> [
     ; assign the series pointer "g" to the result of inserting
     ; the z'th element picked out of reading in some series
     ; from input that was stored in "a"...this pokes an element
     ; for the forward diagonal near the front of g
     g: insert g (pick (readin-mu a) z)

     ; insert the read-in series "a" from above into "g" as well,
     ; but *after* the forward diagonal elements we've added...
     insert g a

     ; for the reverse diagonal, subtract z from 6 and pick that
     ; (one-based) element out of the input that was stored in "a"
     ; so an element for the reverse diagonal is at the tail
     append g (pick a (subtract 6 z))

     ; so long as we are counting to 5 anyway, go ahead and add an
     ; asterisk to a series we will use called "v" to search for
     ; a fulfilled solution later
     append v '*
 ]
</code>```

Note: Parentheses added above for clarity.  But Rebol programmers (like English speakers) generally eschew the application of extra structural callouts for indicating the grammar in communication...rather save them for other applications...

Just as an added bonus to show how interesting this actually is, I'll throw in some mix of normal code to sum the board.  The programming styles are actually...compatible:

```<code>rtZ5[GisGpcRaZisGaAPgPCaSB6zAPv'*]
temp-series: g
sum: 0
loop 5 * 5 [
    square: first temp-series
    if integer! == type? square [
        sum: sum + square
    ]
    temp-series: next temp-series
]
print ["Hey grandma, the board sum is" sum]
l5[AgL5[apGfAsk+A5]]hd+Gu[raGin-NTrM'*fisGv5]p"BINGO!"
</code>```

That's valid Rebmu as well, and it will give you a nice board sum before playing Bingo with you.  In the example given, it says Hey grandma, the board sum is 912.  Which is probably right.  But you get the point.  :)

Title: Code Golf Bingo!

Body:
Given the long, long, long overdue announcement of Rebol's impending release as open source software, I returned to my pet dialect to solve this Bingo problem.  I may soon be able to distribute Rebmu as its own, teensy GPL package.  :)

Rebmu 88 characters

In the compact notation:

rtZ5[GisGpcRaZisGaAPgPCaSB6zAPv'*]l5[AgL5[apGfAsk+A5]]hd+Gu[raGin-NTrM'*fisGv5]p"BINGO!"

The dialect uses a trick I call mushing which is explained on the Rebmu page.  It's "legit" in the sense that it doesn't cheat the parser; this is valid Rebol...and can actually can be freely intermingled with ordinary code as well as (ahem) "long-form" Rebmu...which BTW would be 141 characters:

[rt z 5 [g: is g pc r a z is g a ap g pc a sb 6 z ap v '*] l 5 [a: g l 5 [ap g f a sk+ a 5]] hd+ g u [ra g in- nt r m '* fis g v 5] p "BINGO!"]

(Given that I claim the compression is a trick that one can do without the help of automation or compilation, I actually develop the code in the mushed form.  It's not difficult.)

It's actually quite simple, nothing special--I'm sure other Rebol programmers could shave things off.  Some  commented source is on GitHub, but the main trick I use is to build all the possible solutions in a long series ("list", "array", what-have-you).  I  build the diagonal solutions during the input loop, as it takes five insertions at the head and five appends at the tail to make them...and there's already a five-iteration loop in progress.

The whole thing easily maps to Rebol code, and I haven't yet thrown any "matrix libraries" into Rebmu with transposition or other gimmicks that seem to come up often.  Someday I will do that but for now I'm just trying to work relatively close to the medium of Rebol itself.  Cryptic-looking things like:

 [g: is g pc r a z is g a ap g pc a sb 6 z ap v '*]

...are rather simple:

 [
     ; assign the series pointer "g" to the result of inserting
     ; the z'th element picked out of reading in some series
     ; from input that was stored in "a"...this pokes an element
     ; for the forward diagonal near the front of g
     g: insert g (pick (readin-mu a) z)

     ; insert the read-in series "a" from above into "g" as well,
     ; but *after* the forward diagonal elements we've added...
     insert g a

     ; for the reverse diagonal, subtract z from 6 and pick that
     ; (one-based) element out of the input that was stored in "a"
     ; so an element for the reverse diagonal is at the tail
     append g (pick a (subtract 6 z))

     ; so long as we are counting to 5 anyway, go ahead and add an
     ; asterisk to a series we will use called "v" to search for
     ; a fulfilled solution later
     append v '*
 ]

Note: Parentheses added above for clarity.  But Rebol programmers (like English speakers) generally eschew the application of extra structural callouts for indicating the grammar in communication...rather save them for other applications...

Just as an added bonus to show how interesting this actually is, I'll throw in some mix of normal code to sum the board.  The programming styles are actually...compatible:

rtZ5[GisGpcRaZisGaAPgPCaSB6zAPv'*]
temp-series: g
sum: 0
loop 5 * 5 [
    square: first temp-series
    if integer! == type? square [
        sum: sum + square
    ]
    temp-series: next temp-series
]
print ["Hey grandma, the board sum is" sum]
l5[AgL5[apGfAsk+A5]]hd+Gu[raGin-NTrM'*fisGv5]p"BINGO!"

That's valid Rebmu as well, and it will give you a nice board sum before playing Bingo with you.  In the example given, it says Hey grandma, the board sum is 912.  Which is probably right.  But you get the point.  :)


答:
Python 2, 69 bytes

f=lambda a,i=0:i/len(a)or a[i]in[a[i-1]+1,i,0][i<=max(a)::2]*f(a,i+1)
```

Uses True/False.

The answer to what characterizes a mod-foldable series turns out to be less interesting than it seems at first. It is a series of the form 0, 1, ..., M - 1, 0, 1, ... x1, 0, 1, ..., x2, ... such that for all i, 0 <= xi < M. Such a sequence can be produced by the mod chain of all the (0-based) indices of the zeroes in the array, excluding the first.

Title: Recognize mod-folds

Body:
Python 2, 69 bytes

f=lambda a,i=0:i/len(a)or a[i]in[a[i-1]+1,i,0][i<=max(a)::2]*f(a,i+1)

Uses True/False.

The answer to what characterizes a mod-foldable series turns out to be less interesting than it seems at first. It is a series of the form 0, 1, ..., M - 1, 0, 1, ... x1, 0, 1, ..., x2, ... such that for all i, 0 <= xi < M. Such a sequence can be produced by the mod chain of all the (0-based) indices of the zeroes in the array, excluding the first.


问:
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. Also, please include if your tip applies to C89 and/or C99 and if it only works on certain compilers.</p>

答:
When you have to walk a string you can walk the pointer instead of incrementing the index.

Code :

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

// print each char
void f(char* s) {
    for (int i=0;s[i];i++) putchar(s[i]);
}

// same output than f;
void g(char* s)
{
    for (;*s;) putchar(*s++);
}

int main(void) {
    f("hello\n");
    g("hello\n");
    return 0;
}
</code>```

example: Remove duplicated & switched case

Title: Tips for golfing in C

Body:
When you have to walk a string you can walk the pointer instead of incrementing the index.

Code :

#include <stdio.h>

// print each char
void f(char* s) {
    for (int i=0;s[i];i++) putchar(s[i]);
}

// same output than f;
void g(char* s)
{
    for (;*s;) putchar(*s++);
}

int main(void) {
    f("hello\n");
    g("hello\n");
    return 0;
}

example: Remove duplicated & switched case


问:
On the Subject of Passwords
In Keep Talking and Nobody Explodes, players are tasked with defusing bombs based on information from their "experts" (other people with a manual). Each bomb is made up of modules, one of which can be passwords, where the expert is given this list of possible passwords, all five letters long:

```<code>about   after   again   below   could
every   first   found   great   house
large   learn   never   other   place
plant   point   right   small   sound
spell   still   study   their   there
these   thing   think   three   water
where   which   world   would   write
</code>```

And the player is given a list of 6 possible letters for each place in the password. Given the possible letter combinations, output the correct password. Input can be in any reasonable format (2D array, string separated by newline, etc.) You may discount the code which you use to compress/generate the list/string/array/whatever of passwords. (Thanks @DenkerAffe)

NOTE: Passwords are case insensitive. You may assume that input will only solve for one password.

Examples / Test Cases

Input here will be represented as a array of strings.

```<code>["FGARTW","LKSIRE","UHRKPA","TGYSTG","LUOTEU"] => first
["ULOIPE","GEYARF","SHRGWE","JEHSDG","EJHDSP"] => large
["SHWYEU","YEUTLS","IHEWRA","HWULER","EUELJD"] => still
</code>```

答:
Python 3, 81 bytes

```<code>from itertools import*
lambda x:[i for i in map(''.join,product(*x))if i in l][0]
</code>```

An anonymous function that takes input of a list of strings x and returns the password.

The list of possible passwords l is defined as:

```<code>l=['ABOUT', 'AFTER', 'AGAIN', 'BELOW', 'COULD',
   'EVERY', 'FIRST', 'FOUND', 'GREAT', 'HOUSE',
   'LARGE', 'LEARN', 'NEVER', 'OTHER', 'PLACE',
   'PLANT', 'POINT', 'RIGHT', 'SMALL', 'SOUND',
   'SPELL', 'STILL', 'STUDY', 'THEIR', 'THERE',
   'THESE', 'THING', 'THINK', 'THREE', 'WATER',
   'WHERE', 'WHICH', 'WORLD', 'WOULD', 'WRITE']
</code>```

This is a simple brute force; I was interested to see how short I could get this without regexes.

How it works

```<code>from itertools import*  Import everything from the Python module for iterable generation
lambda x                Anonymous function with input list of strings x
product(*x)             Yield an iterable containing all possible passwords character by
                        character
map(''.join,...)        Yield an iterable containing all possible passwords as strings by
                        concatenation
...for i in...          For all possible passwords i...
i...if i in l           ...yield i if i is in the password list
:[...][0]               Yield the first element of the single-element list containing the
                        correct password and return
</code>```

Try it on Ideone

Title: On the Subject of Passwords

Body:
Python 3, 81 bytes

from itertools import*
lambda x:[i for i in map(''.join,product(*x))if i in l][0]

An anonymous function that takes input of a list of strings x and returns the password.

The list of possible passwords l is defined as:

l=['ABOUT', 'AFTER', 'AGAIN', 'BELOW', 'COULD',
   'EVERY', 'FIRST', 'FOUND', 'GREAT', 'HOUSE',
   'LARGE', 'LEARN', 'NEVER', 'OTHER', 'PLACE',
   'PLANT', 'POINT', 'RIGHT', 'SMALL', 'SOUND',
   'SPELL', 'STILL', 'STUDY', 'THEIR', 'THERE',
   'THESE', 'THING', 'THINK', 'THREE', 'WATER',
   'WHERE', 'WHICH', 'WORLD', 'WOULD', 'WRITE']

This is a simple brute force; I was interested to see how short I could get this without regexes.

How it works

from itertools import*  Import everything from the Python module for iterable generation
lambda x                Anonymous function with input list of strings x
product(*x)             Yield an iterable containing all possible passwords character by
                        character
map(''.join,...)        Yield an iterable containing all possible passwords as strings by
                        concatenation
...for i in...          For all possible passwords i...
i...if i in l           ...yield i if i is in the password list
:[...][0]               Yield the first element of the single-element list containing the
                        correct password and return

Try it on Ideone


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

```<code>5½×lØp+.Ḟ»0
</code>```

Try it online!

This is my first ever Jelly answer! This uses the algorithm from the MATL answer. Thanks to Dennis for shaving off 3 bytes!

Explanation:

```<code>   lØp      # Log Base phi
5½          # Of the square root of 5
  ×         # Times the input
      +     # Plus
       .    # 0.5
        Ḟ   # Floored
</code>```

This gets the right answer, now we just need to handle the special case of '0'. With '0' as an arg, we get -infinity, so we return

```<code>»      # The maximum of
 0     # Zero
       # And the previous calculated value.
</code>```

Title: Fibonacci reversed!

Body:
Introduction

We all know and love our Fibonacci sequence and have seen a myriad of challenge on it here already. However, we're still lacking a very simple case which this answer is going to provide: Reversed fibonacci! So given F_n your job is to find n.

Specification

Input

Your input will be a non-negative integer, which is guaranteed to be part of the fibonacci sequence.

Output

The output must be a non-negative integer as well.

What to do?

The introduction already said: Given a fibonacci number, output its index. Fiboancci number hereby is defined as F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) and you're given F(n) and must return n.

Potential Corner Cases

0 is a valid in- and output.

If given "1" as input you may either output "1" or "2", as you prefer.

You may always assume that your input actually is a fibonacci number.

You may assume that the input is representable as a 32-bit signed integer.

Who wins?

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

Standard rules apply of course.

Test-cases

```<code>0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
</code>```

Body:
Jelly, <s>14</s> 11 bytes

5½×lØp+.Ḟ»0

Try it online!

This is my first ever Jelly answer! This uses the algorithm from the MATL answer. Thanks to Dennis for shaving off 3 bytes!

Explanation:

   lØp      # Log Base phi
5½          # Of the square root of 5
  ×         # Times the input
      +     # Plus
       .    # 0.5
        Ḟ   # Floored

This gets the right answer, now we just need to handle the special case of '0'. With '0' as an arg, we get -infinity, so we return

»      # The maximum of
 0     # Zero
       # And the previous calculated value.


问:
Add two numbers
Input: Two integers. Preferably decimal integers, but other forms of numbers can be used. These can be given to the code in standard input, as arguments to the program or function, or as a list.

Output: Their sum. Use the same format for output integers as input integers. For example, the input 5 16 would lead to the output 21.

Restrictions: No standard loopholes please. This is code-golf, answer in lowest amount of bytes wins.

Notes: This should be fairly trivial, however I'm interested to see how it can be implemented. The answer can be a complete program or a function, but please identify which one it is.

Test cases:

```<code>1 2 -> 3
14 15 -> 29
7 9 -> 16
-1 8 -> 7
8 -9 -> -1
-8 -9 -> -17
</code>```

Or as CSV:

```<code>a,b,c
1,2,3
14,15,29
7,9,16
-1,8,7
8,-9,-1
-8,-9,-17
</code>```

Leaderboard

var QUESTION_ID=84260,OVERRIDE_USER=8478;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

```

答:
Cheddar, 3 bytes

```<code>(+)
</code>```

This is a cool feature of Cheddar called "functionized operators". Credit for this idea goes to @CᴏɴᴏʀO'Bʀɪᴇɴ.

Here are more examples of functionized operators:

```<code>(+)(1,2) // 3
(/)(6,2) // 3
(-)(5)   // -5
</code>```

Title: Add two numbers

Body:
Cheddar, 3 bytes

(+)

This is a cool feature of Cheddar called "functionized operators". Credit for this idea goes to @CᴏɴᴏʀO'Bʀɪᴇɴ.

Here are more examples of functionized operators:

(+)(1,2) // 3
(/)(6,2) // 3
(-)(5)   // -5


问:
Implement Takewhile

Introduction and Credit

Today without a fancy prelude: Please implement takewhile.

A variation of this (on a non-trivial data structure) was an assignment at my university functional programming course. This assignment is now closed and has been discussed in class and I have my professor's permission to post it here (I asked explicitly).

Specification

Input

The input will be a list (or your language's equivalent concept) of positive integers.

Output

The output should be a list (or your language's equivalent concept) of positive integers.

What to do?

Your task is to implement takewhile (language built-ins are allowed) with the predicate that the number under consideration is even (to focus on takewhile).

So you iterate over the list from start to end and while the condition (is even) holds, you copy to the output-list and as soon as you hit an element that doesn't make the condition true, you abort the operation and output (a step-by-step example is below). This higher-order functionality is also called takeWhile (takewhile).

Potential corner cases

The order of the output list compared to the input list may not be changed, e.g. [14,42,2] may not become [42,14].

The empty list is a valid in- and output.

Who wins?

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

Standard rules apply of course.

Test Vectors

```<code>[14, 42, 2324, 97090, 4080622, 171480372] -> [14, 42, 2324, 97090, 4080622, 171480372]
[42, 14, 42, 2324] -> [42, 14, 42, 2324]
[7,14,42] -> []
[] -> []
[171480372, 13, 14, 42] -> [171480372]
[42, 14, 42, 43, 41, 4080622, 171480372] -> [42, 14, 42]
</code>```

Step-by-Step Example

```<code>Example Input: [42, 14, 42, 43, 41, 4080622, 171480372]

Consider first element: 42
42 is even (21*2)
Put 42 into output list, output list is now [42]

Consider second element: 14
14 is even (7*2)
Put 14 into output list, output list is now [42,14]

Consider third element: 42
42 is even (21*2)
Put 42 into output list, output list is now [42,14,42]

Consider fourth element: 43
43 is not even (2*21+1)
Drop 43 and return the current output list

return [42,14,42]
</code>```

答:
Python 3, 72 bytes

It's a bit of a boring answer, but itertools has a function for this...

```<code>from itertools import*
lambda x:[i for i in takewhile(lambda y:y%2+1,x)]
</code>```

An anonymous function that takes input of the list x via argument and returns a list.

Try it on Ideone

Title: Implement Takewhile

Body:
Python 3, 72 bytes

It's a bit of a boring answer, but itertools has a function for this...

from itertools import*
lambda x:[i for i in takewhile(lambda y:y%2+1,x)]

An anonymous function that takes input of the list x via argument and returns a list.

Try it on Ideone