# Question
Title: Test if a string can be made with substrings!
Given a string `s` and an array/list `l`, determine whether or not `s` can be made with parts from `l`.

For example, if the string is `"Hello, world!"` and the list is `[' world!', 'Hello,']`, then the program/function should return a truthy value, because you can arrange the list to form the string. The following list would also return a truthy value: `['l', 'He', 'o, wor', 'd!']`. Just imagine the `'l'` filling in where it needs to in he string. So yes, you may repeat elements of the list to form the string. If it cannot form the string, it should return a falsy value. Standard methods of IO, standard loopholes apply.

**Test cases:**

```
Input (In the form of s, l)
Output (1 if possible, 0 if impossible)

"Hello, world!", ["l", "He", "o, wor", "d!"]
1

"la lal al ", ["la", " l", "al "]
1

"this is a string", ["this should return falsy"]
0

"thi is a string", ["this", "i i", " a", " string"]
0

"aaaaa", ["aa"]
0

"foo bar foobar", ["foo", "bar", " ", "spam"]
1

"ababab", ["a","ba","ab"]
1

"", ["The string can be constructed with nothing!"]
1

```

# Answer
# Brachylog, 8 bytes

```
~c¬{∋¬∈}

```

Try it online!

This is really slow. Took about 37 seconds for the "Hello, world!" test case on my PC, and timed-out on TIO.

This takes the string through the Input variable and the list through the Output variable

### Explanation

```
             String = ?, List = .

             It is possible to find…
~c           …a deconcatenation of ?…
  ¬{   }     …such that it is impossible…
    ∋¬∈      …that an element of that deconcatenation is not an element of .

```
> 11 votes

# Answer
## Mathematica, 29 bytes

```
StringMatchQ[#,""|##&@@#2..]&

```

## Explanation:

```
             #,               (* The first argument *)
StringMatchQ[                 (* matches the string pattern *)
               ""|##&         (*   Alternatives *)
                     @@       (*     applied to *)
                       #2     (*     the second argument *)
                         ..   (*   repeated *)
                           ]&

```

## Borderline cheating solution, 21 bytes

```
StringMatchQ[#,#2..]&

```

Since Mathematica is a symbolic programming language, there is no\* difference between the expressions `List[a,b,...]` and `Alternatives[a,b,...]` other than how they interact with other symbols and how they are displayed (`{a,b,...}` and `a|b|...`, respectively). When used in the second argument of `StringMatchQ`, an `Alternatives` expression is treated as a string pattern, and thus we can save `8` bytes over my above solution by taking the second argument as an `Alternatives` expression.

* Technically `List` is also `Locked`, which prevents users from `Unprotect`ing it and changing its behavior.
> 7 votes

# Answer
# Pyth, 23 bytes

```
AQW&GhGJ.(G0Vf!xJTH aG>JlN;G

```

Takes input like `[['string'],['list', 'of', 'parts']]`. The output is either an empty list or a list with values inside. In Pyth, a list containing anything, even a null string (`['']`), evaluates to true.

Try it online!

Explanation:

```
                             | Implicit: Q = eval(input())
AQ                           | Assign the first value of Q to G and the second to H
  W&GhG                      | While G is not empty and G doesn't contain an empty string:
       J.(G0                 |  Pop the first value of G and store into J
            Vf!xJTH          |  For N in elements in H that match the beginning of J:
                             |   Additional space for suppressing printing
                    aG>JlN   |   Append to G the elements of J from the length of N to the end
                          ;  | End all loops
                           G | Print G

```

This solution continuously tries to remove every possible part from the beginning of the string, and keeps track of what values it still needs to look through.

If we look at the value of `G` in the test case `[['ababab'],['a','ba','ab']]` after each iteration of the while loop, this is what we get:

```
['ababab']
['babab', 'abab']
['abab', 'bab']
['bab', 'bab', 'ab']
['bab', 'ab', 'b']
['ab', 'b', 'b']
['b', 'b', '']
['b', '']
['']   <---Remember, this evaluates to True

```

And, in the test case `[['aaaaa'],['aa']]`, this is what we get:

```
['aaaaa']
['aaa']
['a']
[]   <---And this evaluates to False

```

I created another test case, `[['aaaaaa'],['a','aa','aaa']]` and the output was this:

```
['', 'aaa', 'aa', 'a', 'aa', 'a', '', 'a', '', 'aa', 'a', '', 'a', '', '', 'a', '', '']

```

The output list contains a bunch of garbage inside of it, but it's still a truthy value.
> 5 votes

# Answer
# Perl 5, 39 bytes

38 bytes of code + `-p` flag.

```
map{chop;$v.="\Q$_\E|"}<>;$_=/^($v)*$/

```

Try it online!

For the input `"Hello, world!", ["l", "He", "o, wor", "d!"]` (separated by newlines actually), it construct the pattern `l|He|o, wor|d!|` (with the metacharacters escaped, thanks to `\Q..\E`), and then looks if the first string matches this pattern with `/^($v)*$/`.

On the TryItOnline, note that there need to be a trailing newline.
> 5 votes

# Answer
# PHP, 69 Bytes

```
<?=($s=$_GET[0])>""?ctype_digit(strtr($s,array_flip($_GET[1])))?:0:1;

```

Testcases
> 4 votes

# Answer
# Python 2, 141 bytes

```
lambda s,l:s in[''.join(i)for r in range(len(s)+1)for j in combinations_with_replacement(l,r)for i in permutations(j)]
from itertools import*

```

Try it Online!

*Extremely* inefficient. The first test case times out on TIO.
> 3 votes

# Answer
## JavaScript (ES6), 59 bytes

Takes the array of substrings `a` and the string `s` in currying syntax `(a)(s)`. Returns `false` / `true`.

```
a=>g=s=>!s||a.some(e=>s.split(e)[0]?0:g(s.slice(e.length)))

```

### Commented

```
a =>                          // main function that takes 'a' as input
  g = s =>                    // g = recursive function that takes 's' as input
    !s ||                     // if 's' is empty, return true (success!)
    a.some(e =>               // else, for each element 'e' in 'a':
      s.split(e)[0] ?         //   if 's' doesn't begin with 'e':
        0                     //     do nothing
      :                       //   else:
        g(s.slice(e.length))  //     remove 'e' at the beginning of 's' and
    )                         //     do a recursive call on the remaining part

```

### Test cases

```
let f =

a=>g=s=>!s||a.some(e=>s.split(e)[0]?0:g(s.slice(e.length)))

console.log(f(["l", "He", "o, wor", "d!"])("Hello, world!"))        // true
console.log(f(["la", " l", "al "])("la lal al "))                   // true
console.log(f(["this should return falsy"])("this is a string"))    // false
console.log(f(["this", "i i", " a", " string"])("thi is a string")) // false
console.log(f(["aa"])("aaaaa"))                                     // false
console.log(f(["foo", "bar", " ", "spam"])("foo bar foobar"))       // true
console.log(f(["a","ba","ab"])("ababab"))                           // true
```
> 3 votes

# Answer
# Haskell, 35 bytes

`#` takes a `String` and a list of `String`s, and returns a `Bool`.

```
s#l=elem s$concat<$>mapM("":)(l<$s)

```

Try it online!

Just don't mind the test case I left out because it thrashed my meager laptop, even with -O2. I suspect GHC doesn't fuse away that intermediate 30517578125 element list, it has too much sharing to get swiftly garbage collected, and because the test case is false the program has to generate all of it... feel free to try if you can handle that.

`mapM("":)(l<$s)` is a list of all ways of making a `length s` list of elements that are either empty strings or strings from `l`.
> 3 votes

# Answer
# Pyth, ~~17~~ ~~15~~ ~~11~~ 14 bytes

```
AQ|!G}Ym-dH./G

```

The requirement for the empty string changed, adding 3 bytes.

Explanation

```
AQ|!G}Ym-dH./G
AQ                     Save the input into G, H.
           ./G         Get all partitions of G.
       m-dH            Check if the parts are in H.
     }Y                The empty list should be present if and only
                           if the string can be made...
  |!G                  ... or the string might be empty.

```

Old versions

```
AQ}Ym-dH./G

```

Shorter *and* runs in the lifespan of the universe!

Explanation

```
AQ}Ym-dH./G
AQ                  Save the input into G, H.
        ./G         Get all partitions of G.
    m-dH            Check if the parts are in H.
  }Y                The empty list should be present if and only
                        if the string can be made.

AQ&G}GsMs.pMy*HlG

```

This is horrifyingly slow, but it works for my (trivially small) test cases.

Explanation

```
AQ&G}GsMs.pMy*HlG
AQ                  Save the input into G, H.
             *HlG   Repeat the list of substrings for each character of G.
            y       Take the power set.
         .pM        Take every permutation of each set of substrings.
      sMs           Get a list of all the joined strings.
    }G              Check if G is one of them.
  &G                Make sure G is not empty.

```
> 3 votes

# Answer
# Jelly, ~~14~~  ~~12~~ 8 bytes

```
;FŒṖḟ€Ạ¬

```

Try it online!

**How it works**

```
;FŒṖḟ€Ạ¬   - main function, left argument s, right argument l
;F         - concatenate to the string the list, flattened to deal with "" as string
  ŒṖ       - Get all partitions of s, that is, all ways to make s from substrings
     €     - For each partition...
    ḟ      -   Filter out (exclude) those elements which are not in...
           -   (implicit right arg) the list l. This leaves the empty set (falsy) if the partition can be made of elements from the list
      Ạ    - If any element is falsy (thus constructable from l), return 0; else return 1
       ¬   - Apply logical not to this, to yield the proper 1 = constructable from list, 0 otherwise.

```

*bugfix on case `"", ["The string can be constructed with nothing"]` thanks to @JonathanAllan*
> 3 votes

# Answer
# R, 49 bytes

```
function(s,l)gsub(paste(l,collapse='|'),"",s)==""

```

Try it online!
> 2 votes

# Answer
# Pyth, 10 ~~8~~ bytes

```
f!-TQ./+zh

```

Test suite

This takes the list on the first line of STDIN, and the string (without quotes) on the second.

To start, the list is stored in `Q`, and the string is stored in `z`. Next, we form all possible partitions of `z`. Each partition will be filtered (`f`) to check if it uses only pieces in `Q`. To do this, we remove all elements of `Q` from `T`, the partition we're partitioning, and logically negate the result with `!`, so that only partitions where every element was in `Q` are kept.

To fix the problem that `''` has no partitions, we add the first word of the dictionary to z, so that it won't be an empty string.
> 2 votes

# Answer
# PowerShell, ~~61~~ ~~58~~ 57 bytes

```
{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};+!$s}

```

Try it online!

Old solutions:

```
{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};[int]!$s}
{$s,$l=$_;$l|sort -d length|%{$s=$s.replace($_,'')};0+!$s}

```
> 2 votes

# Answer
# Python 2, 64 bytes

```
lambda s,l:len(re.findall("^("+"|".join(l)+")*$",s))>0
import re

```

Try this online!
> 1 votes

# Answer
# PowerShell, 78

```
$s,$l=$args;!($s-creplace(($l|sort -d length|%{[regex]::escape($_)})-join'|'))

```

Pretty straightforward regex-based approach.
> 1 votes

# Answer
## CJam (16 bytes)

```
{Ma+1$,m*:e_\a&}

```

This is an anonymous block (function) taking the string and the array of strings on the stack. Online demo.

It uses the obvious algorithm:

```
{        e# Declare a block. Call the args str and arr
  Ma+    e#   Add the empty string to the array
  1$,m*  e#   Take the Cartesian product of len(str) copies of (arr + [""])
  :e_    e#   Flatten each element of the Cartesian product into a single string
  \a&    e#   Intersect with an array containing only str
}

```

The return value is an empty array/string (falsy) if `str` can't be made, or an array containing `str` (truthy, even if `str` is itself the empty string) if it can be made.
> 1 votes

# Answer
# C++(Bcc), 287 bytes

```
#include<algorithm.h>
f(a,b)char*a,**b;{int i,j,k,v,p[256];if(!a||!b||!*b)return-1;for(v=0;v<256&&b[v];++v)p[v]=v;if(v>=256)return-1;la:for(i=0,j=0;j<v&&a[i];){for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);j=b[p[j]][k]?(i-=k),j+1:0;}if(a[i]&&next_permutation(p,p+v)) goto la;return i&&!a[i];}

```

because i do not wrote or used too much the next\_permutation() i don't know if is all ok. I don't know 100% if it is a solution too possibly this is out of quality... One list of string is here one array of pointers to char; NULL terminated The algo is easy, there is one algo that linearity try if all string in the list fit with argument "a" string there is one other algo that permute the index of the list of string so it try all possible combination.

ungolf it, test code and results here

```
#include<stdio.h>
g(a,b)char*a,**b;
{int i,j,k,v,p[256];
 if(!a||!b||!*b) return -1;
 for(v=0;v<256&&b[v];++v) p[v]=v;
 if(v>=256)      return -1; // one array of len >256 is too much
la:
 for(i=0,j=0;j<v&&a[i];)
   {for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);
    j=b[p[j]][k]?(i-=k),j+1:0;
   }
 if(a[i]&&next_permutation(p,p+v)) goto la;
 return i&&!a[i];
}

#define F for
#define P printf

test(char* a, char** b)
{int i;
 P("f(\"%s\",[",a);
 F(i=0;b[i];++i)
       P("\"%s\"%s", b[i], b[i+1]?", ":"");
 P("])=%d\n", f(a,b));
}

main()
{char *a1="Hello, world!",    *b1[]={"l","He", "o, worl", "d!",      0};//1
 char *a2="la lal al ",       *b2[]={"la", " l", "al ",              0};//1
 char *a3="this is a string", *b3[]={"this should return falsy",     0};//0
 char *a4="thi is a string",  *b4[]={"this", "i i", " a", " string", 0};//0
 char *a5="aaaaa",            *b5[]={"aa",                           0};//0
 char *a6="foo bar foobar",   *b6[]={"foo","bar"," ","spam",         0};//1
 char *a7="ababab",           *b7[]={"a","ba","ab",                  0};//1
 char *a8="",                 *b8[]={"This return 0 even if has to return 1", 0};//0
 char *a9="ababc",            *b9[]={"a","abc", "b", 0};//1

  test(a1,b1);test(a2,b2);test(a3,b3);test(a4,b4);test(a5,b5);test(a6,b6);
  test(a7,b7);test(a8,b8);test(a9,b9);
}

f("Hello, world!",["l", "He", "o, worl", "d!"])=1
f("la lal al ",["la", " l", "al "])=1
f("this is a string",["this should return falsy"])=0
f("thi is a string",["this", "i i", " a", " string"])=0
f("aaaaa",["aa"])=0
f("foo bar foobar",["foo", "bar", " ", "spam"])=1
f("ababab",["a", "ba", "ab"])=1
f("",["This return 0 even if has to return 1"])=0
f("ababc",["a", "abc", "b"])=1

```

this would compile in gcc C++ compiler

```
#include<algorithm>

int f(char*a,char**b){int i,j,k,v,p[256];if(!a||!b||!*b)return -1;for(v=0;v<256&&b[v];++v)p[v]=v;if(v>=256)return -1;la:;for(i=0,j=0;j<v&&a[i];){for(k=0;b[p[j]][k]==a[i]&&a[i];++i,++k);j=b[p[j]][k]?(i-=k),j+1:0;}if(a[i]&&std::next_permutation(p,p+v))goto la;return i&&!a[i];}

```
> 1 votes

# Answer
# Python, 66 bytes

```
lambda s,l:s==''or any(x==s[:len(x)]and f(s[len(x):],l)for x in l)

```

### Ungolfed:

```
def f(s,l):
    if s=='':
        return 1
    for x in l:
        if s.startswith(x) and f(s[len(x):],l):
            return 1
    return 0

```
> 1 votes

# Answer
# Microsoft Sql Server, 353 bytes

```
u as(select s.n,s collate Latin1_General_BIN s,l collate Latin1_General_BIN l,
row_number()over(partition by l.n order by len(l)desc)r from s,l where s.n=l.n),
v as(select n,s,l,replace(s,l,'')c,r from u where r=1 union all
select u.n,u.s,u.l,replace(v.c,u.l,''),u.r from v,u where v.n=u.n and v.r+1=u.r)
select s,iif(min(c)='',1,0)u from v group by n,s

```

Test it online.

Readable version:

```
with s as(
  select n,s
  from(values(1,'Hello, world!'),
             (2,'la lal al '),
             (3,'this is a string'),
             (4,'thi is a string'),
             (5,'aaaaa'),
             (6,'foo bar foobar'),
             (7,'ababab'),
             (8,''))s(n,s)),
l as(
  select n,l
  from(values(1,'l'),(1,'He'),(1,'o, wor'),(1,'d!'),
             (2,'la'),(2,' l'),(2,'al '),
             (3,'this should return falsy'),
             (4,'this'),(4,'i i'),(4,' a'),(4,' string'),
             (5,'aa'),
             (6,'foo'),(6,'bar'),(6,' '),(6,'spam'),
             (7,'a'),(7,'ba'),(7,'ab'),
             (8,'The string can be constructed with nothing!'))l(n,l)),
--The solution starts from the next line.
u as(
  select s.n,
    s collate Latin1_General_BIN s,
    l collate Latin1_General_BIN l,
    row_number()over(partition by l.n order by len(l)desc)r
  from s,l
  where s.n=l.n),
v as(
  select n,s,l,replace(s,l,'')c,r from u where r=1
    union all
  select u.n,u.s,u.l,replace(v.c,u.l,''),u.r
  from v,u
  where v.n=u.n and v.r+1=u.r
)
select s,iif(min(c)='',1,0)u from v group by n,s

```
> 0 votes

# Answer
## C, 140 bytes

I'm sure there is a shorter way to do this in C but I wanted to create a solution that tests all the possible combinations of substrings instead of the usual find/replace method.

```
char p[999];c,o;d(e,g,l,f)int*e,**g,**l;{c=f&&c;for(l=g;*l;)strcpy(p+f,*l++),(o=strlen(p))<strlen(e)?d(e,g,0,o):(c|=!strcmp(e,p));return c;}

```

Try it online

Ungolfed:

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

char buf[999];
int result;
int temp;

int test(char *text, char **ss, char **ptr, int length)
{
    if (length == 0)
        result = 0;

    for(ptr = ss; *ptr; ptr++)
    {
        strcpy(buf + length, *ptr);
        temp = strlen(buf);
        if (temp < strlen(text))
        {
            // test recursivly
            test(text, ss, 0, temp);
        }
        else
        {
            if (strcmp(buf, text) == 0)
                result = 1;
        }
    }
    return result;
}

int main()
{
    char *text = "Hello,World";
    char *keywords[] = { "World", "Hello", ",", 0 };
    printf("%d", test(text, keywords, 0, 0));
}

```
> 0 votes

---
Tags: code-golf, string, decision-problem, subsequence
---


# Question
Title: The mad chemist and the clever programmer
# Backstory

You wake up dizzy in a chemistry laboratory, and you realize you have been kidnapped by a old mad chemist. Since he cannot see very well because of his age, he wants you to work for him and only then, you can escape the laboratory.

# Task

It is your task to return the structural formulae of the molecules whose chemical formula will be given as input. Note that only the carbon (`C`), oxygen (`O`) and hydrogen (`H`) atoms will be used as input. Unlike in chemical formulas, a `0` is a valid quantifier and a `1` cannot be omitted (e.g. `C1H4O0` is valid input, but `CH4` isn't).

To prevent ambiguity, we assume double and triple bonds do not appear in the molecules. All carbon atoms need 4 single bonds, all oxygen atoms need 2, and hydrogen atoms need one. We also assume that `O-O` bonds do not exist as well. The molecule does not have to exist nor be stable.

The input will never contain more than `3` carbon atoms to ensure lightness in the output's display.

You only should display the molecules whose carbons atoms are arranged in a straight line without interruption. Ergo, no `C-O-C` bonds.

You must return **all** possible molecules not excluded by the previous rules. You do not need to handle invalid inputs.

The following example displays all the solutions you have to handle for that molecule.

A rotation by 180 degrees in the plane of the page of one of the molecule's formula is considered a redundancy and does not need to be displayed.

In the example below I'll show all of the possible formulae for a molecule, then point out the ones that do not need to be displayed.

# Example

Input: `C2H6O2`

First, here are all the possible formulae for this input (Thank you to @Jonathan Allan)

```
01        H
          |
          O   H
          |   |
  H - O - C - C - H
          |   |
          H   H

02            H
              |
          H   O
          |   |
  H - O - C - C - H
          |   |
          H   H

03        H   H
          |   |
  H - O - C - C - O - H
          |   |
          H   H

04        H   H
          |   |
  H - O - C - C - H
          |   |
          H   O
              |
              H

05        H   H
          |   |
  H - O - C - C - H
          |   |
          O   H
          |
          H

12        H   H
          |   |
          O   O
          |   |
      H - C - C - H
          |   |
          H   H

13        H
          |
          O   H
          |   |
      H - C - C - O - H
          |   |
          H   H

14        H
          |
          O   H
          |   |
      H - C - C - H
          |   |
          H   O
              |
              H

15        H
          |
          O   H
          |   |
      H - C - C - H
          |   |
          O   H
          |
          H

23            H
              |
          H   O
          |   |
      H - C - C - O - H
          |   |
          H   H

24            H
              |
          H   O
          |   |
      H - C - C - H
          |   |
          H   O
              |
              H

25            H
              |
          H   O
          |   |
      H - C - C - H
          |   |
          O   H
          |
          H

34        H   H
          |   |
      H - C - C - O - H
          |   |
          H   O
              |
              H

35        H   H
          |   |
      H - C - C - O - H
          |   |
          O   H
          |
          H

45        H   H
          |   |
      H - C - C - H
          |   |
          O   O
          |   |
          H   H

```

And here are the formulae that should be in the output if we take out the rotations of 180° in the plane of the page :

```
01        H
          |
          O   H
          |   |
  H - O - C - C - H
          |   |
          H   H

03        H   H
          |   |
  H - O - C - C - O - H
          |   |
          H   H

12        H   H
          |   |
          O   O
          |   |
      H - C - C - H
          |   |
          H   H

13        H
          |
          O   H
          |   |
      H - C - C - O - H
          |   |
          H   H

14        H
          |
          O   H
          |   |
      H - C - C - H
          |   |
          H   O
              |
              H

 15      H
         |
         O   H
         |   |
     H - C - C - H
         |   |
         O   H
         |
         H

23            H
              |
          H   O
          |   |
      H - C - C - O - H
          |   |
          H   H

25            H
              |
          H   O
          |   |
      H - C - C - H
          |   |
          O   H
          |
          H

35        H   H
          |   |
      H - C - C - O - H
          |   |
          O   H
          |
          H

```

You do not need to output the labels of the formulae and you can output either of the rotations when two exist. For example you can output either 02 or 35.

Here are some valid inputs to test your code:

```
C3H8O2 C1H4O0 C2H6O2 C1H4O1 C2H6O2

```

The PC the chemist gave you to complete your task is quite old so you do not have a lot of memory on it to save your code, thus this is and the shortest amount of byte wins!

# Answer
> 3 votes
# Ruby, 275

```
->s{(k=4<<2*c=s[1].to_i).times{|i|z=" "*8
t=("  H|O|"[i%2*2,4]+"C|"*c+"O|H   "[i>>c&2^2,4]).chars.map{|j|z+j+z}
(c*2).times{|j|t[4+j&-2][j%2*10,7]="    H - O - H    "[[i>>j/2-1&4,-7-(i>>c*2-j/2-1&4)][j%2],7]}
i*(k+1)>>c+1&k-1<i||("%b"%i).sum%16!=s[5].to_i||i%7>c*3||puts(t)}}

```

Combined formulas for left and right sidechains and eliminated variable `h`

# Ruby, 279

```
->s{(k=1<<h=2+2*c=s[1].to_i).times{|i|t=("  H|O|"[i%2*2,4]+"C|"*c+"O|H   "[i>>c&2^2,4]).chars.map{|j|(z=" "*8)+j+z}
c.times{|j|t[4+j*2][0,7]="    H - O -"[i>>j-1&4,7]
t[4+j*2][10,7]="- O - H    "[i>>h-j-3&4^4,7]}
i*(k+1)>>h/2&k-1<i||("%b"%i).sum%16!=s[5].to_i||i%7>c*3||puts(t)}}

```

**Ungolfed in test program**

```
f=->s{
  (k=1<<h=2+2*c=s[1].to_i).times{|i|                       #c=number of C atoms. h=number of H (calculated)
                                                           #iterate i from 0 to (k=1<<h)-1

  t=("  H|O|"[i%2*2,4]+"C|"*c+"O|H   "[i>>c&2^2,4]).       #compose a backbone string H-C...C-H. Insert O at the top where bit 0 of i set, and O at the bottom where bit c+1 of i set
  chars.map{|j|(z=" "*8)+j+z}                              #convert string to an array of characters, pad each character left and right with 8 spaces

  c.times{|j|t[4+j*2][0,7]="    H - O -"[i>>j-1&4,7]       #overwrite spaces on left with H or HO according to bits 1 up to c
             t[4+j*2][10,7]="- O - H    "[i>>h-j-3&4^4,7]} #overwrite spaces on right with H or OH according to bits h-1 down to c+1

  i*(k+1)>>h/2&k-1<i||                                     #rotate the bits of i by h/2. if this is less than i, do not output the structure (eliminates rotations by 180deg by outputtng the lexically highest)
  ("%b"%i).sum%16!=s[5].to_i||                             #if the number of 1's in i differs from the number of O's indicated in the input, do not output
  i%7>c*3||                                                #if i%7>c*3, do not output (empirical solution to avoid 90deg rotations for C=1)
  puts(t)                                                  #if the above are all false, output the current structure.
  }
}

f[gets]

```

**Output**

Spacing is as per question output. Backbone vertical instead of horizontal allowed per comments. Rotations of the entire display through 90 or 180 degrees considered equivalent.

```
C2H6O2
        H
        |
        O
        |
H - O - C - H
        |
    H - C - H
        |
        H

        H
        |
        O
        |
    H - C - H
        |
H - O - C - H
        |
        H

        H
        |
H - O - C - H
        |
H - O - C - H
        |
        H

        H
        |
        O
        |
    H - C - H
        |
    H - C - H
        |
        O
        |
        H

        H
        |
H - O - C - H
        |
    H - C - H
        |
        O
        |
        H

        H
        |
    H - C - H
        |
H - O - C - H
        |
        O
        |
        H

        H
        |
H - O - C - H
        |
    H - C - O - H
        |
        H

        H
        |
    H - C - H
        |
H - O - C - O - H
        |
        H

        H
        |
    H - C - O - H
        |
H - O - C - H
        |
        H

```

---
Tags: code-golf, string, ascii-art, chemistry
---


title: Sp|Lit wo(r)dS, S(P)lit wO|rds

text:
# Question
Title: Sp|Lit wo(r)dS, S(P)lit wO|rds
m|Y bR|ain is We|iRd. F(o)R T(h)E La|sT fi(v)e YE|ars O|R s|o, (I) ha|ve C(u)T wO|rds in h(a)lf wh|En (I) s(e)e Th|em. Wh|EN I started Do|ing it, it To|oK a meN|TaL effort - B(u)T I almost cou(l)dn't N(o)T d|o it. N(o)w, I d|o it in the back of my head, a(n)d hardly ev|en not|iCe it. However, I thought this wo|uld make a great challenge.

# Definitions

For this challenge, each letter is given a point score, based on my judgement of its width in a sans-serif font. You will use this width to cut a word into two halves of equal width. The characters that this challenge will use are the alphabet in lower and upper cases, apostrophe, and hyphen.

```
Width  Characters
1      i l I '
2      f j r t -
3      a b c d e g h k n o p q s u v x y z
4      m w A B C D E F G H J K L N O P Q R S T U V X Y Z
5      M W

```

For my explanations and test cases, `|` denotes the location in which a word can be cleanly split in half. `(` and `)` on either side of a letter indicate that that letter will be split in half to create a clean split.

# Input

Input will consist of a single "word" (which is not required to be in the dictionary). You can take this word in whatever text input you would like (String, char array, etc.). This word will only contain letters, `'`, and `-` (see above table). Because of what you will do with this word (see below), case of input is left to the developer's discretion. Trailing newlines allowed if needed.

# The Task

Permutate through all forms of the input (all letters at all possible upper or lower case positions). For example, for input `it's`, the below is all permutations:

```
it's
it'S
iT's
iT'S
It's
It'S
IT's
IT'S

```

To split a permutation of a word in half, the points on one side of the word must be the same as the points of the other side of the word. However, if a letter is stuck in between two even sections, you can also cut a letter cleanly in half.

Please note that "half" does not mean that you have moved halfway into the string. "Half" means that the points on both sides are equal.

Examples:

`W` is 5 points. `i` is 1 point. Splitting the permutation `Wiiiii` in half will result in `W | iiiii`, with 5 points on each side of the `|`.

`T` is 3 points. Splitting the permutation `TTTT` in half will result in `TT | TT`, with 6 points on each side of the `|`.

`w` is 4 points. a is 3 points. Splitting the permutation `waw` in half will result in `w (a) w`, with 5.5 points on each side. The points from `a` are distributed to both sides, as `a` is split in half.

# Output

Your output is an integer of the number of unique permutations of the input that can be cleanly split in half. Trailing newlines allowed if needed.

# Test Cases

I will be outputting all valid permutations of the input for the test cases. Remember that that is not part of the specs for you.

In my intermediate output, the numbers indicate the point value of the letter above them, so the output is a bit easier to visualize.

```
Input: a
( a )
  3
( A )
  4
Output: 2

Input: in
Output: 0

Input: ab
A | B
4   4
a | b
3   3
Output: 2

Input: abc
A ( B ) C
4   4   4
A ( b ) C
4   3   4
a ( B ) c
3   4   3
a ( b ) c
3   3   3
Output: 4

Input: will
W ( I ) L l
5   1   4 1
W ( I ) l L
5   1   1 4
W ( i ) L l
5   1   4 1
W ( i ) l L
5   1   1 4
w I | L l
4 1   4 1
w I | l L
4 1   1 4
w i | L l
4 1   4 1
w i | l L
4 1   1 4
Output: 8

Input: stephen
S T E ( P ) H E N
4 4 4   4   4 4 4
S T E ( p ) H E N
4 4 4   3   4 4 4
S T E | p h e n
4 4 4   3 3 3 3
S T e ( P ) H E n
4 4 3   4   4 4 3
S T e ( P ) H e N
4 4 3   4   4 3 4
S T e ( P ) h E N
4 4 3   4   3 4 4
S T e ( p ) H E n
4 4 3   3   4 4 3
S T e ( p ) H e N
4 4 3   3   4 3 4
S T e ( p ) h E N
4 4 3   3   3 4 4
S t E ( P ) H e n
4 2 4   4   4 3 3
S t E ( P ) h E n
4 2 4   4   3 4 3
S t E ( P ) h e N
4 2 4   4   3 3 4
S t E ( p ) H e n
4 2 4   3   4 3 3
S t E ( p ) h E n
4 2 4   3   3 4 3
S t E ( p ) h e N
4 2 4   3   3 3 4
S t e ( P ) h e n
4 2 3   4   3 3 3
S t e p | H E N
4 2 3 3   4 4 4
S t e ( p ) h e n
4 2 3   3   3 3 3
s T E ( P ) H E n
3 4 4   4   4 4 3
s T E ( P ) H e N
3 4 4   4   4 3 4
s T E ( P ) h E N
3 4 4   4   3 4 4
s T E ( p ) H E n
3 4 4   3   4 4 3
s T E ( p ) H e N
3 4 4   3   4 3 4
s T E ( p ) h E N
3 4 4   3   3 4 4
s T e ( P ) H e n
3 4 3   4   4 3 3
s T e ( P ) h E n
3 4 3   4   3 4 3
s T e ( P ) h e N
3 4 3   4   3 3 4
s T e ( p ) H e n
3 4 3   3   4 3 3
s T e ( p ) h E n
3 4 3   3   3 4 3
s T e ( p ) h e N
3 4 3   3   3 3 4
s t E ( P ) h e n
3 2 4   4   3 3 3
s t E p | H E N
3 2 4 3   4 4 4
s t E ( p ) h e n
3 2 4   3   3 3 3
s t e P | H E N
3 2 3 4   4 4 4
s t e p | H E n
3 2 3 3   4 4 3
s t e p | H e N
3 2 3 3   4 3 4
s t e p | h E N
3 2 3 3   3 4 4
Output: 37

Input: splitwords
S P L I T | W O r d s
4 4 4 1 4   5 4 2 3 3
<snip>
s p l i t w | o R d S
3 3 1 1 2 4   3 4 3 4
Output: 228

Input: 'a-r
' a ( - ) R
1 3   2   4
' a | - r
1 3   2 2
Output: 2

Input: '''''-
' ' ' ( ' ) ' -
1 1 1   1   1 2
Output: 1

```

# Victory

This is , so shortest answer in bytes wins. You must be able to output all test cases (so, all inputs up to 10 characters) in a reasonable amount of time. Do not artificially cap your input.

# ~~Bounty~~

~~I do not know if this is in the realm of possibility. However, you're golfers - you'll do anything for rep. I am offering a 200 rep bounty (I'll start it once this bounty condition is fulfilled, as it seems basically impossible to me) for a program that outputs the correct output for `antidisestablishmentarianism` in under 15 seconds on an average computer (aka mine). Please note that this test case must not be hard coded in any way.~~

@DigitalTrauma crushed my bounty, coming in well under two seconds. Check out his answer here.

# Answer
> 8 votes
# Pyth, ~~75~~ ~~74~~ ~~73~~ 70 bytes

```
~~lfsm}sT-Bysded._Tm.n]d*Fmm?k|qd\i+4}d"mw"|}d"il'"h|}d"fjrt-"+2}d"mw"-2}d"'-~~
~~lfsm}sT-Bysded._Tm.n]d*Fmm?k|qd\i+4}d"mw"|x}Ld+c"mw il' fjrt-")G1 4-2}d"'-~~
~~lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"-2}d"'-~~
lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

```

Try it online!

For the love of God, please don't even try `antidisestablishmentarianism` in the interpreter. You'll crash it.

## Explanation

```
lfsm}sT-Bysded._Tm.n]d*Fm<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

```

Let us break down this code into X parts.

### The first part: generating cased versions and mapping to the values

```
m<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dG

```

Let us be clear here. In **no** part of the process are letters capitalized. We just need to map one letter to two values (and the punctuation marks to one value), without the need of capitalizing them. We'll be deciding for which characters we will be needing two values, and for which characters we will be needing one:

```
m<,|x}Ld+c"mw il' fjrt-")G1 4|qd\i+4}d"mw"h}dGQ  Q implicitly appended
m                                             Q  for d in Q:
                                           }dG       d in alphabet?
                                          h          +1 (T/F as 1/0)
 <   take the first ^ elements of the following array
     for d in alphabet, it will take 2 elements;
     for d being ' or -, it will take 1 element.
  ,          pair up the following two values
   |x}Ld+c"mw il' fjrt-")G1 4                  this is the first value
                             |qd\i+4}d"mw"    this is the second value

```

As you see, even the first part is too long.

The first value is for lowercase version, which includes `'` and `-`. The second value is for uppercase version, with `'` and `-` will not take.

The first value:

```
|x}Ld+c"mw il' fjrt-")G1 4
       "mw il' fjrt-"        does what it says on the tin
      c              )       split on spaces, creating an
                             array with three elements
     +                G      append another element, which
                             is the alphabet, as a fail-safe;
                             now the array has 4 elements
  }Ld                        check if d is in each array
                             as with above, True becomes 1
                             and False becomes 0 (T/F as 1/0)
 x                     1     find the first occurrence of 1
|                        4   logical or with 4. If it was 0,
                             it would become 4 now.

```

The first string contains `"mw"` at index 0. It has a value of 4, which explains the need of the logical or. Note that Pyth uses 0-indexing. Also, the space before the `4` is to separate it from `1`.

The second value (uppercase):

```
|qd\i+4}d"mw"
 qd\i          d=="i"
|              logical OR
       }d"mw"  is d in "mw"? That is, is d "m" or "w"?
     +4        +4

```

If `d` is `"i"`, then it gives `1` on the first step. Otherwise, it continues. If `d` is `"m"` or `"w"`, then the third step gives `1`, which is added to `4` to give `5`. If `d` is not `"m"` or `"w"`, then the third step gives `0`, which is added to `4` to give `4`.

## The second part: getting the job done

```
lfsm}sT-Bysded._Tm.n]d*F

```

This is prepended to the first part, which technically is not separated from the second part (it is still one command). So, the value from the first part is passed to the right.

Recap: in the first part, we mapped the letters to their possible values (lowercase and uppercase for letters, just one value for the two punctuation marks). For input `"ab"`, one would get `[[3,4],[3,4]]`.

To generate the different cased versions (which should have been done in the first part, but that would overflow), we use the Cartesian product repeatedly, and then flatten the result. Problems arise when there is only one letter (first testcase), because the Cartesian product would not give us an array, and the flatten command (`.n`) is overflowed to give strange results to numbers. We'll see how I circumvented this issue.

```
lfsm}sT-Bysded._Tm.n]d*F
                      *F  reduce by Cartesian product
                 m   d    for d in each unflattened version:
                    ]         [d] (wrap in array)
                  .n          flatten
 f                filter for resulting arrays as T
              ._T all prefixes of T
   m              for d in each prefix:
          sd          find the sum of d
         y            double
       -B   ed        [above, above - last element of d]
    }sT               is the sum of T in the above array of 2 elements?
  s               sum the 1/0 generated in each prefix
                  any non-zero value is regarded as truthy
l                 length

```

If it is a split in the middle by `|`, then the prefix would have the sum doubled being the sum of the total.

If it is split by `()`, then the prefix sum doubled minus the value in parentheses would be the sum of the total.

# Answer
> 11 votes
# c, 378 bytes; about 0.6s for `antidisestablishmentarianism`

**Updated answer**. I read @JonathanAllan's comment about `i`s, and at first I didn't understand this optimization, but now I see that since both `i` and `I` have a width of 1, then we can count the associated permutations twice with only having to validate once. Previously my solution used multiple threads to spread the load over multiple CPUs and with that I was just about able to go through all 228 possibilities on my machine. Now with the `i` optimization there is no need to mess with threads - a single thread does the job easily within the time restriction.

Without further ado - golfed c function:

```
char m[128]={[39]=10,[45]=20};f(s,l,p)char *s;{m[65]?:bcopy("PPPPPPPPPPPdPPPPPPPPPdPPP      <<<<<(<<(<P<<<<(<(<<P<<<",m+65,58);int g,h,u=0,v=0,x=0,y=0,c=0;if(p<l){g=s[p];if(g>64&&g-'i'){s[p]-=32;c+=f(s,l,p+1);}s[p]=g;c+=((g=='i')+1)*f(s,l,p+1);}else{for(l--,p=0,g=m[s[p]],h=m[s[l]];p<=l;){y=v;x=u;if(u+g>v+h){v+=h;h=m[s[--l]];}else{u+=g;g=m[s[++p]];}}c=u==v||y==x;}return c;}

```

The recursive function `f` takes 3 parameters - a pointer to the input string, the string length and the offset in the string to start processing (should be 0 for top-level call). The function returns the number of permutations.

Try it online. TIO seems to typically run through all testcases (including `antidisestablishmentarianism` in under 2 seconds.

Note that there are some unprintables in the string that is `bcopy()`ed to `m[]`. The TIO seems to handle these correctly.

Ungolfed:

```
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <assert.h>

int width_tbl[] = {
    ['\''] = 1,
    ['-'] = 2,
    ['A'] = 4,4,4,4,4,4,4,4,1,4,4,4,5,4,4,4,4,4,4,4,4,4,5,4,4,4,
    ['a'] = 3,3,3,3,3,2,3,3,1,2,3,1,4,3,3,3,3,2,3,2,3,3,4,3,3,3
};

int
f (char *str, int len, int pos) {
    int lidx, ridx;
    int tot_width = 0;
    int lwidth, rwidth;
    int tot_lwidth = 0, tot_rwidth = 0;
    int prev_tot_lwidth = 0, prev_tot_rwidth = 0;
    char tmp;
    int perm_cnt = 0;

    if (pos < len) {
        tmp = str[pos];
        if (isalpha(tmp) && (tmp != 'i')) {
            str[pos] = toupper(str[pos]);
            perm_cnt += f(str, len, pos+1);
        }
        str[pos] = tmp;
        perm_cnt += ((tmp == 'i') + 1) * f(str, len, pos+1);
    } else {
        //puts(str);
        lidx = 0;
        ridx = len - 1;
        lwidth = width_tbl[str[lidx]];
        rwidth = width_tbl[str[ridx]];
        while (lidx <= ridx) {
            prev_tot_rwidth = tot_rwidth;
            prev_tot_lwidth = tot_lwidth;
            if (tot_lwidth + lwidth > tot_rwidth + rwidth) {
                tot_rwidth += rwidth;
                rwidth = width_tbl[str[--ridx]];
            } else {
                tot_lwidth += lwidth;
                lwidth = width_tbl[str[++lidx]];
            }
        }
        if (tot_lwidth == tot_rwidth) {
            perm_cnt = 1;
        } else if (prev_tot_rwidth == prev_tot_lwidth) {
            perm_cnt = 1;
        }
    }
    return perm_cnt;
}

int main (int argc, char **argv) {
    int i;
    int perm_cnt;

    if (argc > 0) {
        char *str = strdup(argv[1]);
        assert(str);

        perm_cnt = f(str, strlen(str), 0);

        printf("n = %d\n", perm_cnt);
    }

    return 0;
}

```

I have a mid-2015 MacBook Pro running MacOS 10.12.4. The compiler is the default MacOS clang. I am compiling with:

```
cc splitwords.c -O2 -o splitwords

```

Running all testcases, including `antidisestablishmentarianism` gives:

```
$ time ./splitwords
Testcase "a": n = 2
Testcase "in": n = 0
Testcase "ab": n = 2
Testcase "abc": n = 4
Testcase "will": n = 8
Testcase "stephen": n = 37
Testcase "splitwords": n = 228
Testcase "'a-r": n = 2
Testcase "'''''-": n = 1
Testcase "antidisestablishmentarianism": n = 83307040

real    0m0.573s
user    0m0.564s
sys 0m0.003s
$

```

This is by no means optimal. The algorithm simply brute-forces its way through all possibilities (modulo `i` \- see comments above), and counts the words that may be split according to the criteria.

# Answer
> 1 votes
## JavaScript (ES6), ~~199~~ ~~169~~ 167 bytes

Expects the input string in lower case. Too slow for the bounty.

```
f=(s,r=[],t=R=0,i=3,x=parseInt("k1048cccctt"["i'l-fjrtmw".search(c=s[0])+1],36)+8>>i&7)=>x&&(c?(i&&f(s,r,t,0),f(s.slice(1),[x,...r],t+x)):R+=r.some(x=>t==x|!(t-=2*x)))

```

### Test cases

```
f=(s,r=[],t=R=0,i=3,x=parseInt("k1048cccctt"["i'l-fjrtmw".search(c=s[0])+1],36)+8>>i&7)=>x&&(c?(i&&f(s,r,t,0),f(s.slice(1),[x,...r],t+x)):R+=r.some(x=>t==x|!(t-=2*x)))

;[ "a", "in", "ab", "abc", "will", "stephen", "splitwords", "'a-r", "'''''-" ]
.map(
  s => console.log(s, '->', f(s))
)
```

# Answer
> 1 votes
## C, ~~403~~ 394 bytes,

Thanks Kevin!

```
r;char*g[]={"","ilI'","fjrt-","","mw","MW",0},**p,b[99];q(c){for(p=g;*p;p++)if(strchr(*p,c))return p-g;return c>='a'&&c<='z'?3:4;}f(char*w,int l){int i,n,c,t,x,y;if(*w){for(i=0;i<2;i++)x=tolower(*w),y=toupper(*w),!i||x!=y?b[l]=i%2?x:y,b[l+1]=0,f(w+1,l+1):0;}else{t=0;for(c=0;c<2;c++)for(i=0;i<l;i++){x=y=0;for(n=0;n<l;n++)c==0||n!=i?((n<i)?(x+=q(b[n])):(y+=q(b[n]))):0;t|=x==y;}r+=t;}return r;}

```

Try it online

Ungolfed code:

```
int getwidth(int c)
{
    char **p, *g[] = { "", "ilI'", "fjrt-", "", "mw", "MW", 0};
    for (p=g; *p; p++)
    {
        if (strchr(*p,c))
            return p-g;
    }
    return c >= 'a' && c <= 'z' ? 3 : 4;
}

int test(char* w, int l)
{
    int i, n, c, t, x, y;

    if (*w)
    {
        for (i=0;i<2; i++)
        {
            x = tolower(*w);
            y = toupper(*w);
            if (!i || x != y)
            {
                b[l] = i % 2 ? x : y;
                b[l + 1] = 0;
                test(w + 1, l+1);
            }
        }
    }
    else
    {
        t = 0;
        for (c=0; c<2; c++)
        {
            for (i=0; i<l; i++)
            {
                x = 0;
                y = 0;
                for (n=0; n<l; n++)
                {
                    if (c == 0 || n != i)
                    {
                        if (n < i)
                            x += getwidth(b[n]);
                        else
                            y += getwidth(b[n]);
                    }
                }
                t |= x == y;
            }
        }
        r += t;
    }
    return r;
}

```

---
Tags: code-golf, string
---


title: Calculate my reading speed

text:
# Question
Title: Calculate my reading speed
*Create a program that calculates my reading speed!*

# The challenge

Write a program which takes some text as input and waits for a *start* signal from the user to display the input. When to user gives a second *end* signal, the program should output the *reading speed* of the user, which is defined as the number of words in the input divided by the time between both signals in minutes.

The word count of the input text is determined by splitting the text at white space.

## Input

* A block of text via any standard input means.
* A *start* and *end* signal by the user, either a click or pressing a certain key of your choice.

## Output

* The block of input text.
* The *reading speed* of the user as defined above.

## Rules

* The start and end signal may **not** be running and ending the program.
* The text may wrap or the user may scroll.
* The reading speed value may be returned in any of the standard methods in the meta post found here, though the text must be displayed beforehand to the user, e.g. by printing to `stdout`.
* This is , so the shortest code in bytes wins.

# Answer
> 5 votes
# MATL, 24 bytes

```
O$Y.Y`OYDtDYbn60*O$Y.Z`/

```

**Explanation**

```
O$Y.    % Wait for the user's keypress
Y`      % Start the timer
        % Implicitly grab the input
OYD     % Converts control characters and creates a string
tD      % Duplicate the string and display
Ybn     % Split the string into words and count them
60*     % Multiply by 60 to convert words per second to words per minute
O$Y.    % Wait for user to press a key
Z`      % Get the elapsed time in seconds
/       % Divide the number of words (times 60) by the time in seconds
        % Implicitly display the result

```

# Answer
> 4 votes
# Octave, 59 bytes

```
pause;tic;disp(x=input(''));pause;numel(strsplit(x))*60/toc

```

**Explanation**

```
pause               % Wait for a user's keypress
tic                 % Start the timer
disp(..)            % Display paragraph
pause;              % Wait for user's keypress
numel(strsplit(x))  % Determine number of words
*60                 % Multiply by 60 to convertwords per second to words per minute
/toc                % Divide by the total time that it took (in seconds)

```

# Answer
> 2 votes
# Processing Js 77 bytes

```
var i="",b=second();println(i);i.split(" ");keyTyped=function(){println(i.length/(second()-b));};

```

Try it out

---
Tags: code-golf
---


title: Equality Comes in Threes

text:
# Question
Title: Equality Comes in Threes
# Taken from: OEIS-A071816

Your task, given an upper bound of `n`, is to find the number of solutions that satisfy the equation:

```
a+b+c = x+y+z, where 0 <= a,b,c,x,y,z < n

```

The sequence starts out as described on the OEIS page, and as below (1-indexed):

```
1, 20, 141, 580, 1751, 4332, 9331, 18152, 32661, 55252, 88913, 137292, 204763, 296492, 418503, 577744, 782153, 1040724, 1363573, 1762004, 2248575, 2837164, 3543035, 4382904, 5375005, 6539156, 7896825, 9471196, 11287235, 13371756

```

---

For `n = 1`, there's only one solution: `(0,0,0,0,0,0)`

For `n = 2`, there are 20 ordered solutions `(a,b,c,x,y,z)` to `a+b+c = x+y+z`:

```
(0,0,0,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,1,0,0,0,1),
(0,1,0,0,1,0), (0,1,0,1,0,0), (0,1,1,0,1,1), (0,1,1,1,0,1), (0,1,1,1,1,0),
(1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,1,1), (1,0,1,1,0,1),
(1,0,1,1,1,0), (1,1,0,0,1,1), (1,1,0,1,0,1), (1,1,0,1,1,0), (1,1,1,1,1,1).

```

---

# I & O

* Input is a single integer denoting `n`.
* Output is a single integer/string denoting `f(n)`, where `f(...)` is the function above.
* The indexing is exactly as described, no other indexing is acceptable.

This is , lowest byte-count wins.

# Answer
# Jelly, ~~9~~ 6 bytes

```
ṗ6ḅ-ċ0

```

**O(n6)** solution.

Try it online!

### How it works

```
ṗ6ḅ-ċ0  Main link. Argument: n

ṗ6      Cartesian power 6; build all 6-tuples (a, x, b, y, c, z) of integers in
        [1, ..., n]. The challenge spec mentions [0, ..., n-1], but since there
        are three summands on each side, this doesn't matter.
  ḅ-    Unbase -1; convert each tuple from base -1 to integer, mapping (a, ..., z)
        to a(-1)**5 + x(-1)**4 + b(-1)**3 + y(-1)**2 + c(-1)**1 + z(-1)**0, i.e.,
        to -a + x - b + y - c + z = (x + y + z) - (a + b + c). This yields 0 if and
        only if the 6-tuple is a match.
    ċ0  Count the number of zeroes.

```
> 11 votes

# Answer
## Mathematica 17 or 76 Bytes

Using the formula:

```
.55#^5+#^3/4+#/5&

```

(Saved 3 bytes per @GregMartin and @ngenisis)

Rather than using the formula, here I literally compute all the solutions and count them.

```
Length@Solve[a+b+c==x+y+z&&And@@Table[(0<=i<#),{i,{a,b,c,x,y,z}}],Integers]&

```
> 9 votes

# Answer
# Haskell, 48 bytes

I didn't notice the formula before writing this, so it's definitely not the shortest (or fastest) general method, but I thought it was pretty.

```
f n=sum[1|0<-foldr1(-)<$>pure[1..n]`mapM`[1..6]]

```

Try it online!

`f n` generates all lists of 6 elements from `[1..n]`, then counts the ones whose alternating sum is 0. Uses the fact that `a+b+c==d+e+f` is the same as `a-(d-(b-(e-(c-f))))==0`, and also that it doesn't matter if we add a 1 to all the numbers.
> 8 votes

# Answer
# MATL, 12 bytes

```
l6:"G:gY+]X>

```

Try it online!

### Explanation

I couldn't miss the chance to use convolution again!

This makes use of the following characterization from OEIS:

> `a(n) = largest coefficient of (1+...+x^(n-1))^6`

and of course polynomial multiplication is convolution.

```
l        % Push 1
6:"      % Do the following 6 times
  G:g    %   Push a vector of n ones, where n is the input
  Y+     %   Convolution
]        % End
X>       % Maximum

```
> 6 votes

# Answer
# Pyth, ~~13~~ 12 bytes

```
JsM^UQ3s/LJJ

```

Saved one byte thanks to Leaky Nun.

Explanation

```
JsM^UQ3s/LJJ
   ^UQ3         Get all triples in the range.
JsM             Save the sums as J.
        /LJJ    Count occurrences of each element of J in J.
       s        Take the sum.

```
> 5 votes

# Answer
# Jelly, 9 bytes

```
ṗ3S€ĠL€²S

```

Not as short as @Dennis's, but it finishes in under 20 seconds for input `100`.

Try it online!

### How it works

```
ṗ3S€ĠL€²S  Main link. Argument: n

ṗ3         Cartesian power; yield all subsets of [1, ..., n] of length 3.
  S€       Sum each.
    Ġ      Group indices by their values; for each unique sum S, list all indices whose
           values are equal to S.
     L€    Length each; for each unique sum S, yield the number of items in the original
           array that sum to S.
       ²   Square each; for each unique sum S, yield the number of pairs that both sum to S.
        S  Sum; yield the total number of equal pairs.

```
> 5 votes

# Answer
# Python 3, 28 bytes

```
lambda n:.55*n**5+n**3/4+n/5

```

Try it online!
> 4 votes

# Answer
# TI-BASIC, 19 bytes

```
:Prompt X
:.05X(11X^4+5X²+4

```

Evaluates the OEIS formula.
> 2 votes

# Answer
# Oasis, 17 bytes

```
5m11*n3m5*nz++20÷

5                   n 5             implicit n for illustration
 m                  n**5
  11                n**5 11
    *               11*n**5
     n              11*n**5 n
      3             11*n**5 n 3
       m            11*n**5 n**3
        5           11*n**5 n**3 5
         *          11*n**5 5*n**3
          n         11*n**5 5*n**3 n
           z        11*n**5 5*n**3 4*n
            +       11*n**5 5*n**3+4*n
             +      11*n**5+5*n**3+4*n
              20    11*n**5+5*n**3+4*n 20
                ÷  (11*n**5+5*n**3+4*n)÷20

```

Try it online!

Oasis is a stack-based language optimized for recurring sequences. However, the recursion formula would be too long for this case.
> 2 votes

# Answer
# Brachylog, 17 bytes

```
{>ℕ|↰}ᶠ⁶ḍD+ᵐ=∧D≜ᶜ

```

Try it online!

### Explanation

```
{  |↰}ᶠ⁶           Generate a list of 6 variables [A,B,C,D,E,F]...
 >ℕ                  ...which are all in the interval [0, Input)
        ḍD         Dichotomize; D = [[A,B,C],[D,E,F]]
          +ᵐ=      A + B + C must be equal to D + E + F
             ∧
              D≜ᶜ  Count the number of possible ways you can label the elements of D while
                     satisfying the constraints they have

```
> 2 votes

# Answer
# JavaScript, 24 bytes

```
x=>11*x**5/20+x**3/4+x/5

```

Uses the formula from the OEIS page.

Try it online!
> 1 votes

# Answer
# Octave, ~~25~~ ~~23~~ 21 bytes

```
@(n).55*n^5+n^3/4+n/5

```

Try it online!

Uses the formula from the OEIS-entry. Saved ~~two~~ four bytes by rearranging the formula and using `.55` instead of `11/20`, thanks to fəˈnɛtɪk.
> 1 votes

# Answer
# Python 2.7, 109 105 99 96 bytes

Thanks ETHproductions and Dennis for saving a few bytes:

```
from itertools import*
lambda s:sum(sum(x[:3])==sum(x[3:])for x in product(range(s),repeat=6))

```
> 1 votes

# Answer
# Octave, 41 bytes

```
@(n)round(max(ifft(fft(~~(1:n),n^2).^6)))

```

Try it online!

Similar to my MATL answer, but computes the convolution via a discrete Fourier transform (`fft`) with a sufficient number of points (`n^2`). `~~(1:n)` is used as a shorter version of `ones(1,n)`. `round` is necessary because of floating point errors.
> 1 votes

# Answer
## Mathematica, 52 bytes

Kelly Lowder's implementation of the OEIS formula is way shorter, but this computes the numbers directly:

```
Count[Tr/@#~Partition~3&/@Range@#~Tuples~6,{n_,n_}]&

```

Well, it actually counts the number of solutions with `1 <= a,b,c,x,y,z <= n`. This is the same number, since adding 1 to all the variables doesn't change the equality.

Explanation: `Range@#~Tuples~6` makes all lists of six integers between 1 and n, `#~Partition~3&/@` splits each list into two lists of length 3, `Tr/@` sums these sublists, and `Count[...,{n_,n_}]` counts how many pairs have the same sum. I got very lucky with the order of precedence between `f @`, `f /@` and `~f~`!
> 1 votes

# Answer
# CJam, 17 bytes

```
ri,6m*{3/::+:=},,

```

Input of `11` times out on TIO, and `12` and higher run out of memory.

Try it online!

**Explanation**

```
ri                e# Read an int from input.
  ,               e# Generate the range 0 ... input-1.
   6m*            e# Take the 6th Cartesian power of the range.
      {           e# Keep only the sets of 6 values where:
       3/         e#  The set split into (two) chunks of 3
         ::+:=    e#  Have the sums of both chunks equal.
              },  e# (end of filter)
                , e# Get the length of the resulting list.

```
> 0 votes

# Answer
## Clojure, 79 bytes

```
#(count(for[r[(range %)]a r b r c r x r y r z r :when(=(+ a b c)(+ x y z))]1))

```

Tons of repetition in the code, on larger number of variables a macro might be shorter.
> 0 votes

---
Tags: code-golf, number, sequence
---


title: Verify Eigenpairs

text:
# Question
Title: Verify Eigenpairs
In this challenge, you will be given a square matrix `A`, a vector `v`, and a scalar `λ`. You will be required to determine if `(λ, v)` is an eigenpair corresponding to `A`; that is, whether or not `Av = λv`.

# Dot Product

The dot product of two vectors is the sum of element-wise multiplication. For example, the dot product of the following two vectors is:

```
(1, 2, 3) * (4, 5, 6) = 1*4 + 2*5 + 3*6 = 32

```

Note that the dot product is only defined between two vectors of the same length.

# Matrix-Vector Multiplication

A matrix is a 2D grid of values. An `m` x `n` matrix has `m` rows and `n` columns. We can imagine an `m` x `n` matrix as `m` vectors of length `n` (if we take the rows).

Matrix-Vector multiplication is defined between an `m` x `n` matrix and a size-`n` vector. If we multiply an `m` x `n` matrix and a size-`n` vector, we obtain a size-`m` vector. The `i`-th value in the result vector is the dot product of the `i`-th row of the matrix and the original vector.

### Example

```
        1 2 3 4 5
Let A = 3 4 5 6 7
        5 6 7 8 9

        1
        3
Let v = 5
        7
        9

```

If we multiply the matrix and the vector `Av = x`, we get the following:

x1 = AT1 * v `/* AT1 means the first row of A; A1 would be the first column */` = (1,2,3,4,5) * (1,3,5,7,9) = 1\*1 + 2\*3 + 3\*5 + 4\*7 + 5\*9 = 1+6+15+28+45 = 95

x2 = AT2 * v = (3,4,5,6,7) * (1,3,5,7,9) = 3\*1 + 4\*3 + 5\*5 + 6\*7 + 7\*9 = 3+12+25+42+63 = 145

x3 = AT3 * v = (5,6,7,8,9) * (1,3,5,7,9) = 5\*1 + 6\*3 + 7\*5 + 8\*7 + 9\*9 = 5+18+35+56+81 = 195

So, we get `Av = x = (95, 145, 195)`.

# Scalar Multiplication

Multiplication of a scalar (a single number) and a vector is simply element-wise multiplication. For example, `3 * (1, 2, 3) = (3, 6, 9)`. It's fairly straightforward.

# Eigenvalues and Eigenvectors

Given the matrix `A`, we say that `λ` is an eigenvalue corresponding to `v` and `v` is an eigenvector corresponding to `λ` **if and only if** `Av = λv`. (Where `Av` is matrix-vector multiplication and `λv` is scalar multiplication).

`(λ, v)` is an eigenpair.

# Challenge Specifications

### Input

Input will consist of a matrix, a vector, and a scalar. These can be taken in any order in any reasonable format.

### Output

Output will be a truthy/falsy value; truthy if and only if the scalar and the vector are an eigenpair with the matrix specified.

# Rules

* Standard loopholes apply
* If a built-in for verifying an eigenpair exists in your language, you may not use it.
* You may assume that all numbers are integers

# Test Cases

```
 MATRIX  VECTOR  EIGENVALUE
 2 -3 -1    3
 1 -2 -1    1    1    ->    TRUE
 1 -3  0    0

 2 -3 -1    1
 1 -2 -1    1    -2   ->    TRUE
 1 -3  0    1

 1  6  3    1
 0 -2  0    0    4    ->    TRUE
 3  6  1    1

 1  0 -1    2
-1  1  1    1    7    ->    FALSE
 1  0  0    0

-4 3    1
 2 1    2    2    ->    TRUE

2    1    2    ->    TRUE

```

I will add a 4x4 later.

Unreadable Test Cases that are easier for testing

# Answer
> 11 votes
# Jelly, 5 bytes

```
æ.⁵⁼×

```

This is a triadic, full program.

Try it online!

### How it works

```
æ.⁵⁼×  Main link
       Left argument:  v (eigenvector)
       Right argument: λ (eigenvalue)
       Third argument: A (matrix)

  ⁵    Third; yield A.
æ.     Take the dot product of v and A, yielding Av.
    ×  Multiply v and λ component by component, yielding λv.
   ⁼   Test the results to the left and to the right for equality.

```

# Answer
> 13 votes
## Mathematica, 10 bytes

```
#2.#==#3#&

```

Takes input like `{vector, matrix, scalar}` and returns a boolean.

# Answer
> 11 votes
# MATL, 7 bytes

```
*i2GY*=

```

Inputs in order: `l`,`v`,`A`.

Explanation:

```
*  % implicitly get l and v, multiply.
i  % get A
2G % get second input, i.e., v again
Y* % perform matrix multiplication
=  % test equality of both multiplications

```

Surprisingly long answer, if you ask me, mostly because I needed a way to get all the input correctly. I do not think that less than 5 bytes is possible, but it would be cool if someone found a 5 or 6 byte solution.

Basically, this calculates `l*v==A*v`.

# Answer
> 6 votes
# CJam, 15 bytes

```
q~W$f.*::+@@f*=

```

Takes input in the form `vector scalar matrix`.

Try it online!

**Explanation**

```
q~               e# Read and eval the input
  W$             e# Copy the bottom most value (the vector)
    f.*::+       e# Perform element-wise multiplication with each row of the matrix, then
                 e#   sum the results of each (ie dot product with each row)
          @@     e# Move the resulting vector to the bottom of the stack
            f*   e# Element-wise multiplication of the scalar and the vector
              =  e# Check if the two vectors are equal

```

# Answer
> 5 votes
# MATLAB, 16 bytes

```
@(A,v,l)A*v==v*l

```

Rather trivial answer. Defines an anonymous function taking the inputs, and calculates element-wise equality of the resulting vectors. A single zero in a logical array makes an array falsey in MATLAB.

# Answer
> 2 votes
# MATLAB, 38 bytes

```
function r=f(m,v,s);r=isequal(m*v,s*v)

```

Returns 1 or 0.

# MATLAB, 30 bytes

```
function r=f(m,v,s);r=m*v==s*v

```

Returns

```
1
1
1

```

as a truthy value. A falsy value is a similar vector with any or all values 0 instead of 1.

# Answer
> 2 votes
# C++, ~~225~~ 203 bytes

*Thanks to @Cort Ammon and @Julian Wolf for saving 22 bytes!*

```
#import<vector>
#define F(v,i)for(i=0;i<v.size();++i)
using V=std::vector<float>;int f(std::vector<V>m,V v,float s){V p;int i,j;F(m,i){p.push_back(0);F(v,j)p[i]+=v[j]*m[i][j];}F(v,i)v[i]*=s;return v==p;}

```

Try it online!

# Answer
> 2 votes
# Python 2.7, 33 bytes

```
f=lambda m,s,e:all(m.dot(s)==e*s)

```

input: m=matrix, s=scalar, e=eigenvalue. M and s are numpy arrays

# Answer
> 2 votes
# Python 3, ~~96~~ 70 bytes

No builtins for matrix-vector or scalar-vector multiplication!

```
lambda A,L,v:all(L*y==sum(i*j for i,j in zip(x,v))for x,y in zip(A,v))

```

Try it online!

-26 bytes by using `zip` thanks to @LeakyNun!

# Answer
> 2 votes
# Julia, 17 bytes

```
(a,b,c)->a*b==b*c

```

Try it online!

# Answer
> 1 votes
# R, ~~30~~ 25 bytes

```
s=pryr::f(all(a%*%v==λ*v))

```

Anonymous function, fairly straightforward. Returns `TRUE` or `FALSE`.

# Answer
> 1 votes
# 05AB1E, 11 bytes

```
vy²*O})²³*Q

```

Try it online!

```
vy²*O})     # Vectorized product-sum.
       ²³*  # Vector * scalar.
          Q # Equivalence.

```

# Answer
> 0 votes
# oK, 12 bytes

```
{y~z%+/y*+x}

```

This is a function, it takes in `[matrix;vector;scalar]`.

This does not work in k for the same reasons that `3.0~3` gives `0` as a result.

---

The following works in **k**, with **14 bytes**:

```
{(y*z)~+/y*+x}

```

# Answer
> 0 votes
# Python, 26 bytes

```
lambda a,b,c:c*b==a.dot(b)

```

`a` and `b` are numpy arrays, `c` is an integer.

Try it online!

# Answer
> 0 votes
# Axiom, 27 bytes

```
f(a,b,c)==(a*b=c*b)@Boolean

```

exercises

```
(17) -> m:=matrix[[2,-3,-1],[1,-2,-1],[1,-3,0] ]; v:=matrix[[3],[1],[0]];
(18) -> f(m,v,1)
   (18)  true

(19) -> m:=matrix[[2,-3,-1],[1,-2,-1],[1,-3,0] ]; v:=matrix[[1],[1],[1]];
(20) -> f(m,v,-2)
   (20)  true

(21) -> m:=matrix[[1,6,3],[0,-2,0],[3,6,1] ]; v:=matrix[[1],[0],[1]];
(22) -> f(m,v,4)
   (22)  true

(23) -> m:=matrix[[1,0,-1],[-1,1,1],[1,0,0] ]; v:=matrix[[2],[1],[0]];
(24) -> f(m,v,7)
   (24)  false

(25) -> m:=matrix[[-4,3],[2,1] ]; v:=matrix[[1],[2]];
(26) -> f(m,v,2)
   (26)  true

(27) -> f(2,1,2)
   (27)  true

```

# Answer
> 0 votes
## Clojure, 60 bytes

```
#(=(set(map(fn[a v](apply -(* v %3)(map * a %2)))% %2))#{0})

```

This checks that all deltas are zero, thus collapsing into the set of zero. Calling example:

```
(def f #(=(set(map(fn[a v](apply -(* v %3)(map * a %2)))% %2))#{0}))
(f [[1 6 3][0 -2 0][3 6 1]] [1 0 1] 4)

```

---
Tags: code-golf, math, matrix, linear-algebra
---


# Question
Title: Linear interpolation of the Fibonacci sequence
Your task is to find the *nth* Fibonacci number, but *n* is not necessarily an integer.

The Fibonacci sequence, 0-indexed, goes as follows:

```
0, 1, 2, 3, 4, 5,  6,  7, ...

1, 1, 2, 3, 5, 8, 13, 21, ...

```

However, what happens if we want the 2*.4*th number?

The 2.4th number is 0.4 times the difference between the 3rd and 2nd Fibonacci numbers plus the 2nd Fibonacci number. So, the 2.4th Fibonacci number is `2 + 0.4 * (3 – 2) = 2.4`.

Similarly, the 6.35th Fibonacci number is `13 + 0.35 * (21 – 13) = 15.8`.

Your task is to find the *nth* Fibonacci number, such that *n* is greater than or equal to 0.

You may do this zero- or one-indexed, just please say which one you are using.

### This is , so shortest code in bytes wins!

Some more examples:

```
0        1
4.5    6.5
0.7      1
7       21

```

# Answer
# Jelly, 5 bytes

```
_Ḟ1+¡

```

This is an iterative solution without built-ins. It uses the same indexing as the challenge spec.

Try it online!

### Background

Let **f** be the function defined in the challenge spec and **F** the Fibonacci function defined as usual (i.e., with **F(0) = 0**). For a non-negative integer **n**, we have **f(n) = F(n + 1)**. When **0 ≤ x \< 1**, the challenge spec defines **f(n + x)** as **f(n) + (f(n + 1) - f(n))x**.

Clearly, this just affects the base cases, but not the recursive formula, i.e., **f(n) = f(n - 1) + f(n - 2)** holds as it would for **F**. This means we can simplify the definition for non-integer arguments to the easier **f(n) = f(n) + f(n - 1)x**.

As others have noted in their answers, the recursive relationship also holds for non-integer arguments. This is easily verifiable, as

Since **f(0) = f(1) = 1**, **f** in constant in the interval **\[0, 1\]** and **f(0 + x) = 1** for all **x**. Furthermore, **f(-1) = F(0) = 0**, so **f(-1 + x) = f(-1) + (f(0) - f(-1))x = 0 + 1x = x**. These base cases cover in **\[-1, 1)**, so together with the recursive formula, they complete the definition of **f**.

### How it works

As before, let **n + x** be the only argument of our monadic program.

`¡` is a *quick*, meaning that it consumes some links to its left and turns them into a *quicklink*. `¡` in particular consumes either one or two links.

* `<F:monad|dyad><N:any>` calls the link **N**, returning **r**, and executes **F** a total of **r** times.
* `<nilad|missing><F:monad|dyad>` sets **r** to the last command-line argument (or an input from STDIN in their absence) and executes **F** a total of **r** times.

Since `1` is a nilad (a link without arguments), the second case applies, and  will execute `+` **n** times (a non-integer argument is rounded down). After each call to `+`, the left argument of the quicklink is replaced with the return value, and the right argument with the previous value of the left argument.

As for the entire program,  floors the input, yielding **n**; then `_` subtract the result from the input, yielding \**x, which becomes the return value.

`1+¡` then calls  – as described before – with left argument **1 = f(0 + x)** and right argument **x = f(-1 + x)**, which computes the desired output.
> 7 votes

# Answer
# Mathematica, 32 bytes

```
If[#<2,1~Max~#,#0[#-1]+#0[#-2]]&

```

Pure function taking a nonnegative real number as input and returning a real number. If `1~Max~#` were replaced by `1`, this would be the standard recursive definition of the 0-indexed Fibonacci numbers for integer arguments. But `1~Max~#` is the correct piecewise linear function for real inputs between 0 and 2, and the recursion takes care of the rest. (Trivia fact: changing this to the 1-indexed Fibonacci numbers can be accomplished simply by changing the `Max` to a `Min`!)

The shortest I could get with the builtin is the 37-byte `(b=Fibonacci)[i=Floor@#](#-i)+b[i+1]&`.
> 4 votes

# Answer
## JavaScript (ES6), 30 bytes

```
f=x=>x<1?1:x<2?x:f(x-1)+f(x-2)
```

```
<input type=number value=2.4 oninput="O.value=f(value)"> <input id=O value=2.4 disabled>
```

Trivial modification of the zero-indexed recursive Fibonacci sequence definition. May give slight rounding errors for some inputs.
> 3 votes

# Answer
# Python 2, 42 bytes

```
f=lambda n:n<3and max(1,n)or f(n-1)+f(n-2)

```

Try it online!
> 3 votes

# Answer
# Jelly, ~~17~~ 12 bytes

```
’Ñ+Ñ
’»0‘ÇỊ?

```

Try it online!

Non-builtin solution.

## Explanation

**Helper function `1Ŀ`**

```
’Ñ+Ñ
 Ñ    Call the main program on
’       {the input} - 1;
   Ñ  Call the main program on {the input};
  +   Add those results{and return the result}

```

**Main program**

```
’»0‘ÇỊ?
’        Subtract 1
 »0      but replace negative results with 0
     Ị?  If the result is less than or equal to 1
   ‘     Return the result plus 1
    Ç    else return the result

```

An input in the range 0 to 1 will therefore saturated-subtract to 0, thus we add 1 to get F(0)=F(1)=1. An input in the range 1 to 2 will return itself. Those base cases are sufficient to do a typical Fibonacci recursion and calculate the other values from there.
> 1 votes

# Answer
# JavaScript (ES6), ~~67~~ 64 bytes

Has a few issues with rounding

```
n=>(i=(g=(z,x=1,y=0)=>z?g(--z,x+y,x):y)(++n|0))+n%1*(g(++n|0)-i)

```

---

## Try It

```
f=
n=>(i=(g=(z,x=1,y=0)=>z?g(--z,x+y,x):y)(++n|0))+n%1*(g(++n|0)-i)
console.log(f(2.4))
console.log(f(6.35))
console.log(f(42.42))
```
> 1 votes

# Answer
## Excel, ~~137 124 119 113 102~~ 97 Bytes

Non-recursive/iterative approach. (Directly calculate the nth terms) This uses the **one-indexed** method. Adding `+1` to `=TRUNC(B1)` changes it to zero-indexed.

```
=A7+(A8-A7)*MOD(B1,1)
=5^.5
=(1+A2)/2
=TRUNC(B1)
=A4+1
=-1/A3
=(A3^A4-A6^A4)/A2
=(A3^A5-A6^A5)/A2

```

The code snippet is intended to be placed starting in cell **A1**.

The input cell is **B1**. The output cell is **A1**.
> 1 votes

# Answer
# Jelly, ~~13~~ 9 bytes

```
,‘ḞÆḞḅ%1$

```

This uses the same indexing as the challenge spec.

Try it online!

### Background

Per the spec, we have **F(n + x) = F(n) + (F(n + 1) - F(n))x**, for natural **n** and **0 ≤ x \< 1**. Since **F(n + 1) = F(n) + F(n - 1)**, this can be rewritten as **F(n + x) = F(n) + F(n - 1)x**.

Furthermore, the indexing used in the challenge spec defines a function **f(n) = F(n + 1)** (where **F** is the usual Fibonacci function, i.e., **F(0) = 0**), so we get the formula **f(n + x) = F(n + 1) + F(n)x**.

### How it works

```
,‘ḞÆḞḅ%1$  Main link. Argument: n + x

 ‘         Increment; yield n + 1 + x.
,          Pair; yield [n + x, n + 1 + x].
  Ḟ        Floor; yield [n, n + 1].
   ÆḞ      Fibonacci; yield [F(n), F(n + 1)].
      %1$  Modulus 1; yield (n + x) % 1 = x.
     ḅ     Unbase; yield F(n)x + F(n + 1).

```
> 0 votes

# Answer
# PHP, 90 Bytes

```
for($f=[1,1];$i<$a=$argn;)$f[]=$f[+$i]+$f[++$i];echo$f[$b=$a^0]+($a-$b)*($f[$b+1]-$f[$b]);

```

Online Version
> 0 votes

# Answer
# Perl 6,  ~~48~~  38 bytes

## 48

```
{$/=(1,1,*+*...*)[$_,$_+1];$0+($_-.Int)*($1-$0)}

```

Try it

## 38

```
sub f(\n){3>n??max 1,n!!f(n-1)+f(n-2)}

```

Try it

## Expanded:

## 48

```
{
  $/ =          # store here so we can use $0 and $1
  (
    1,1,*+*...* # Fibonacci sequence
  )[
    $_,         # get the value by using floor of the input
    $_ + 1      # and get the next value
  ];

    $0            # the first value from above
  +
    ( $_ - .Int ) # the fractional part of the input
  *
    ( $1 - $0 )   # the difference between the two values in the sequence
}

```

(`$0` and `$1` is short for `$/[0]` and `$/[1]`)

## 38

```
sub f (\n) {
    3 > n           # if n is below 3
  ??
    max 1, n        # return it if it is above 1, or return 1
                    # if it was below 1, the answer would be 1
                    # the result for numbers between 1 and 3
                    # would be the same as the input anyway
  !!
    f(n-1) + f(n-2) # the recursive way to get a fibonacci number
}

```

This was inspired by other Python, and Javascript solutions
> 0 votes

# Answer
# Julia 0.5, 31 bytes

This is basically just Rod's answer translated.

```
f(n)=n<3?max(1,n):f(n-1)+f(n-2)

```

Try it online!
> 0 votes

---
Tags: code-golf, math, sequence, arithmetic, fibonacci
---


title: Print the Greek alphabet in words

text:
# Question
Title: Print the Greek alphabet in words
This is different from Print the Greek alphabet! because it is in words.
This is different from "Hello, World!" because the output is different and much longer, leading to different techniques.
This is different from We're no strangers to code golf, you know the rules, and so do I because the output is different and much shorter, leading to different techniques.

Your task is to print this exact text: (the Greek alphabet in words)

```
alpha beta gamma delta epsilon zeta eta theta iota kappa lambda mu nu xi omicron pi rho sigma tau upsilon phi chi psi omega

```

Capitalization does not matter.

Remember, this is , so the code with the smallest number of bytes wins.

# Answer
> 7 votes
# Python 2, ~~99~~ 81 bytes

```
from unicodedata import*
i=913
exec"print name(unichr(i+(i>929)))[21:],;i+=1;"*24

```

Thanks to @xnor for saving 15 bytes!

This uses the `unicodedata.name()` method to get the name of every character. Unfortunately, the code point 930 gives an error for some reason, so that cost a few extra bytes.

This also prints the output in uppercase, which is allowed.

# Answer
> 4 votes
# Scala, 76 bytes

```
print((913 to 937)filter(930!=)map(Character getName _ drop 21)mkString " ")

```

Explanation:

```
print(                  //print...
  (913 to 937)            //build a range of the codepoints for aplha to omega
  filter(930!=)           //filter out that sigma in the middle
  map(                    //map each char...
    Character getName _     //to its full unicode name, e.g. "GREEK CAPITAL LETTER ALPHA"
    drop 21                 //and drop the first 21 chars, aka "GREEK CAPITAL LETTER "
  )
  mkString " "            //join them with a space
)

```

# Answer
> 4 votes
# Jolf, 7 bytes

```
RΜpΧ΅z♣

```

Replace  with `0x05`, or try it here! Or, use this link to generate the code. (Just click run, the code will be written into the code box.)

## Explanation

```
RΜpΧ΅z♣
 ΜpΧ     map Greek character alphabet
    ΅z    with the toGreek function (converts greek characters to names)
R     ♣  and join that with spaces.

```

# Answer
> 3 votes
# ///, ~~119~~ 117 bytes

```
/1/eta //2/psilon //3/a /alph3b1gamm3delt3e2z11th1iot3kapp3lambd3mu nu xi omicron pi rho sigm3tau u2phi chi psi omega

```

*-2 bytes thanks to steenbergh*

Try it online!

# Answer
> 3 votes
# PHP, 68 characters, 92 bytes

```
<?=strtr(htmlentities(αβγδεζηθικλμνξοπρστυφχψω),["&"=>"",";"=>" "]);

```

uses UTF-8; prints a trailing space. Run with `-nr`.

* turn the lowercase greek alphabet into html entities
* remove ampersands and replace semicolons with spaces
* print

Try it online

# Answer
> 2 votes
# BF, 1265 bytes

```
++++++++++.--[--->++++<]>+.+++++++++++.++++.--------.-------.-[->+++<]>.[->+++<]>++.+++.[--->+<]>---.+[->+++<]>++.-[->+++<]>.++[->+++<]>+.------.++++++++++++..------------.-[->+++<]>.+[->+++<]>+.+.+++++++.++++++++.+[->+++<]>++.-[->+++<]>.+[->+++<]>++.+++++++++++.+++.----------.+++.+++.-.-[->+++++<]>-.-[->++++<]>--.---[->+++<]>.[--->+<]>---.+[->+++<]>++.-[->+++<]>.+[->+++<]>++.[--->+<]>---.+[->+++<]>++.-[->+++<]>.---[->++++<]>.------------.---.[--->+<]>---.+[->+++<]>++.-[->+++<]>.-[--->++<]>-.++++++.+++++.+[->+++<]>++.-[->+++<]>.-[--->++<]>+.----------.-[++>-----<]>..[----->++<]>+.-[->+++<]>.++[--->++<]>.-----------.++++++++++++.-----------.++.---.-[->+++<]>.+[----->+<]>.++++++++.-[---->+<]>+++.+[----->+<]>+.+++++++.-[---->+<]>+++.--[->++++<]>.[->+++<]>+.[--->+<]>---.+++++[->+++<]>.--.----.------.-[--->+<]>----.---.-.-[->+++++<]>-.[-->+++++++<]>.-------.[--->+<]>---.---[----->++<]>.----------.+++++++.[--->+<]>-----.---[->++++<]>-.----------.--.++++++.------------.-[->+++<]>.---[->++++<]>.+[->+++<]>++.--[--->+<]>.-[---->+<]>+++.---[->++++<]>+.-----.+++.----------.+++.+++.-.-[->+++++<]>-.[-->+++++++<]>.--------.+.[--->+<]>---.+[->+++<]>.+++++.+.[--->+<]>---.[-->+++++++<]>.+++.----------.[--->+<]>---.+++++[->+++<]>.--.--------.++.------.>++++++++++.

```

# Answer
> 2 votes
# Mathematica, ~~85~~ 66 bytes

*Thanks to ngenisis for pointing the way to a 19-byte savings!*

```
CharacterName@Alphabet@"Greek"~Riffle~" "~StringDelete~"Curly"<>""

```

Returns the string with every Greek letter capitalized. Just thought it would be fun to coerce Mathematica into doing all the work!

`Alphabet@"Greek"` returns a nicely formatted list of the Greek alphabet characters; `CharacterName@` converts each of those characters into a string naming that character, and `~Riffle~" "` inserts a space between each such string. Unfortunately, two of the letters are called `"CurlyEpsilon"` and `"CurlyPhi"`, and so we need `~StringDelete~"Curly"` to fix that. Finally, `<>""` concatenates all these strings together.

Previous submission:

```
StringDelete[ToString@FullForm@Alphabet@"Greek","List"|"Curly"|"["|"]"|"\""|"\\"|","]

```

`Alphabet@"Greek"` returns a nicely formatted list of the Greek alphabet characters as before, but `FullForm` forces it to show the internal structure rather than the nice formatting; `ToString` converts that internal structure into a string that can be manipulated:

```
"List[\"\\[Alpha]\", \"\\[Beta]\", \"\\[Gamma]\", \"\\[Delta]\", \"\\[CurlyEpsilon]\", \"\\[Zeta]\", \"\\[Eta]\", \"\\[Theta]\", \"\\[Iota]\", \"\\[Kappa]\", \"\\[Lambda]\", \"\\[Mu]\", \"\\[Nu]\", \"\\[Xi]\", \"\\[Omicron]\", \"\\[Pi]\", \"\\[Rho]\", \"\\[Sigma]\", \"\\[Tau]\", \"\\[Upsilon]\", \"\\[CurlyPhi]\", \"\\[Chi]\", \"\\[Psi]\", \"\\[Omega]\"]"

```

From here, `StringDelete[..."List"|"Curly"|"["|"]"|"\""|"\\"|","]` gets rid of all the stuff we don't want.

# Answer
> 1 votes
# Pyth - ~~104~~ 83 bytes

Base conversion with separator `f`. Unfortunately, it starts with smallest code point `a`.

```
tX."azT¢ç§ªVôòé!þm<EÞ6ä¿û2_w}MªÍ]·¥ünBPæúòRÜÔYcWed¼(É?«/~{"\fd

```

Try it online here.

# Answer
> 1 votes
# Jelly, 58 bytes

```
“ßẓ⁸!ȧøḌçỊ¤¢Q=4QẠė⁷¤yż>S⁺ẓṬḄṂċK~⁼Ṛ7&⁼s<ụɦ³ḳMŻyVẉƑƭ6Ẋ⁵ỌQ⁸ẹ»

```

Try it online!

# Answer
> 1 votes
# Perl 6, 47 bytes (44 characters)

```
put squish ~«map {.uniname~~/\w+$/},"α".."ω"

```

Prints `LAMDA` instead of `LAMBDA`, bus so do the other Unicode database based solutions.

Try it online!

# Answer
> 0 votes
# 05AB1E, 86 bytes

```
“¤±¢ªœÏ¤œ epsilon zeta etaìÛ iota kappaÊ¯ mu nu xi omicron¾î rho¿Ã tau upsilonÐ¢Â¶á‚Åµ

```

Try it online!

# Answer
> 0 votes
## Perl6 (71)

```
(913..937).grep(*!= 930)>>.chr>>.uniname>>.substr(21).join(" ").lc.say

```

---
Tags: code-golf, kolmogorov-complexity
---


title: Calculate Wind Chill

text:
# Question
Title: Calculate Wind Chill
The Australian Apparent Temperature (aka, wind chill) in °C `AT` is given by this algorithm from the Australian Bureau of Meterology (wp, source):

```
AT = T<sub>a</sub> + (0.33 * e) - (.7 * ws) - 4.0
```

Where:

> `T<sub>a</sub>` = Dry bulb temperature (°C)
>
> `e` = Water vapour pressure (hPa)
>
> `ws` = Wind speed (m/s) (at an elevation of 10 meters)

The water vapour pressure in hectoPascals `e` is given by this algorithm:

```
e = (rh / 100) * 6.105 * exp( ( 17.27 * T<sub>a</sub> ) / ( 237.7 + T<sub>a</sub> ) )
```

Where:

> `T<sub>a</sub>` = Dry bulb temperature (°C)
>
> `rh` = Relative humidity \[%\]
>
> `exp` represents the exponential function

The domain of:

> * `T<sub>a</sub>` is -273.15°C to 2e7°C.
> * `e` is the real numbers
> * `ws` is 0 m/s to 2e7 m/s
> * `rh` is 0% to 100%

For inputs outside these domains, your code can do anything, including give the right answer.

---

## Output

Given a dry bulb **temperature** in °C, a **wind speed** in metres / second, and a **relative humidity** in %, your code should give the Apparent Temperature in °C, accurate to 0.1°C.

Assuming your platform or language can represent reals, for correct functions `correct_func`,

or in C, `fabsl( correct_func(Ta, rH, ws) - expected ) < 0.1`.

### Test cases

```
1 value for T<sub>a</sub>, rh, ws -> output

0 -> -4
2 -> -3.35346
4 -> -2.69275
6 -> -2.01507
8 -> -1.31719
10 -> -0.595428
12 -> 0.154404
14 -> 0.937065
16 -> 1.75793
18 -> 2.62308
20 -> 3.5393
22 -> 4.51423
24 -> 5.55638
26 -> 6.67525
28 -> 7.88137
30 -> 9.18643

49, 99, 67 -> 36.268

```

Repl.it for any test case: https://repl.it/H9xL/0

You can use a builtin function for the exponential function, `e<sup>x</sup>`, if you like.

This is , so the shortest code wins!

# Answer
> 5 votes
# Python 3, 76 bytes

```
t=lambda T,r,V:.0201465*r*2.718281828459045**(1727*T/(100*T+23770))+T-.7*V-4

```

Try it online!

# Answer
> 4 votes
# Python, ~~78~~ ~~72~~ 66 bytes

Pretty much a direct implementation of the algorithm provided in the challenge description.

```
lambda T,r,w:T+.0201465*r*2.7182818284**(17.27*T/(237.7+T))-.7*w-4

```

**Try it online**

This was specifically tested with the maximum value of `T` to find how many digits of Euler's constant were required for the error to be within the allowed amount.

# Answer
> 3 votes
# TI-BASIC, 41 bytes

```
:Prompt T,R,W
:T-.7W-4+.02014565Re^(17.27T/(237.7+T

```

Surprisingly, a calculator is really good at crunching numbers.

# Answer
> 2 votes
# Javascript, 56 bytes

```
(a,r,w)=>a+.0201465*r*Math.exp(17.27*a/(237.7+a))-.7*w-4

```

```
var f = (a,r,w)=>a+.0201465*r*Math.exp(17.27*a/(237.7+a))-.7*w-4
var expected = [-4, -3.35346, -2.69275, -2.01507, -1.31719, -0.595428, 0.154404, 0.937065, 1.75793, 2.62308, 3.5393, 4.51423, 5.55638, 6.67525, 7.88137, 9.18643]; for (var i = 0; i < 16; i++) {var g = f(2*i,2*i,2*i); var diff = expected[i] - g; document.getElementById('w').innerHTML += '\n' + ((diff > 0.1 || diff < -0.1) ? 'KO' : 'OK') + '   ' + (expected[i] - g) + '   ' + g + '   ' + expected[i];}
```

```
<pre id="w">Passed  |  Diff  |  Actual result  |  Expected</pre>
```

# Answer
> 2 votes
# Octave, ~~54~~ 49 bytes

```
@(T,r,V).0201465*r*e^(17.27*T/(237.7+T))+T-.7*V-4

```

Try it online!

# Answer
> 2 votes
# Japt, ~~40~~ 38 bytes

```
U+.0#É465*V*MEp17.27*U/(#í.7 +U)-.7*W-4

```

Try it online!

This is my first Japt answer, so please don't judge it too harshly ;-)

# Answer
> 1 votes
## Perl 6, 52 (possibly non-competing)

```
{$^a+.0201465*$^c*exp(17.27*$a/(237.7+$a))-4-.7*$^b}

```

This can't be evaluated by itself. You either have to pass in arguments, or store the block into a variable.

---
Tags: code-golf, math
---


title: Draw me the (weird) unit circle!

text:
# Question
Title: Draw me the (weird) unit circle!
## Introduction

You may know and love your normal unit circle. But mathematicans are crazy and thus they have abstracted the concept to any point that satisfies `x*x+y*y=1`. Because Cryptographers1 are also weird, they *love* finite fields and *sometimes* finite rings (it is not like they have much choice though), so let's combine this!

## The Challenge

### Input

A positive integer larger than one in your favorite encoding. Let's call this number n.

### Output

You will output the "picture" (which consists of n times n characters) of the unit circle modulo the input integer as ASCII-Art using "X" (upper-case latin X) and " " (a space). Trailing spaces and newlines are allowed.

### More Details

You have to span a coordinate system from bottom-left to top-right. Whenever a point fulfills the circle equation, place an X at the position, otherwise place a space.

The condition for a point to be considered part of the circle border is:
`mod(x*x+y*y,n)==1`.

Here a quick illustration of the coordinate-system:

```
(0,4)(1,4)(2,4)(3,4)(4,4)
(0,3)(1,3)(2,3)(3,3)(4,3)
(0,2)(1,2)(2,2)(3,2)(4,2)
(0,1)(1,1)(2,1)(3,1)(4,1)
(0,0)(1,0)(2,0)(3,0)(4,0)

```

If it helps you, you may also invert the direction of any of the axes, but the examples assume this orientation.

## Who wins?

This is so the shortest code in byte wins! Only the default I/O methods are allowed and all standard loopholes are banned.

## Examples

Input: 2

```
X
 X

```

Input: 3

```
X
X
 XX

```

Input: 5

```
X

X
 X  X

```

Input: 7

```
X
  X  X

  X  X
X
 X    X

```

Input: 11

```
X

     XX

   X    X
   X    X

     XX

X
 X        X

```

Input: 42

```
X
         X                       X

            X                 X
       X                           X
      X                             X
                     X
  X             X         X             X

     X             X   X             X
X
               X           X
              X             X
         X                       X

            X                 X
                     X
        X           X X           X
                     X
            X                 X

         X                       X
              X             X
               X           X
X
     X             X   X             X

  X             X         X             X
                     X
      X                             X
       X                           X
            X                 X

         X                       X
X
 X           X               X           X

```

---

1 I suggest you take a look at my profile if you're wondering here.

# Answer
> 6 votes
# Bash + GNU Utilities, 59

```
x={0..$[$1-1]}d*
eval echo $x$x+$1%1-0r^56*32+P|dc|fold -$1

```

Input `n` given as a command-line parameter. The y-axis is inverted.

Try it online.

# Answer
> 4 votes
# Octave, ~~45~~ 44 bytes

```
@(n)[(mod((x=(0:n-1).^2)+x',n)==1)*56+32,'']

```

Try it online!

# Answer
> 3 votes
## Mathematica, 56 48 bytes

*Edit: Thanks to Greg Martin and Martin Ender for saving 8 bytes.*

```
Grid@Array[If[Mod[#^2+#2^2,x]==1,X]&,{x=#,#},0]&

```

## Original solution:

```
Grid@Table[If[Tr[{i-1,j-1}^2]~Mod~#==1,X,],{i,#},{j,#}]&

```

# Answer
> 3 votes
# Haskell, 68 bytes

```
f n|r<-[0..n-1]=unlines[[last$' ':['X'|mod(x*x+y*y)n==1]|y<-r]|x<-r]

```

Try it online! The y-axis is flipped. Usage: `f 42` returns a newline delimited string.

This is a nested list comprehension where both `x` and `y` are drawn from the range `[0..n-1]`. `last$' ':['X'|mod(x*x+y*y)n==1]` is a shorter form of `if mod(x*x+y*y)n==1 then 'X' else ' '`. The list comprehension evaluates to a list of strings which is turned into a single newline separated string by `unlines`.

# Answer
> 2 votes
## CJam, 23 bytes

```
ri:X,2f#_ff{+X%(S'X?}N*

```

Try it online!

```
ri:X    e# Read input, convert to integer, store in X.
,       e# Turn into range [0 1 ... X-1].
2f#     e# Square each value in the range.
_ff{    e# 2D map over all pairs from that list.
  +     e#   Add the two values in the current pair.
  X%    e#   Take the sum modulo X.
  (     e#   Decrement, so that x^2+y^2==1 becomes 0 (falsy) and everything
        e#   else becomes truthy.
  S'X?  e#   Select space of 'X' accordingly.
}
N*      e# Join rows with linefeeds.

```

# Answer
> 2 votes
## JavaScript (ES6), 81 bytes

```
f=
n=>[...Array(n)].map((_,x,a)=>a.map((_,y)=>(x*x+y*y)%n-1?` `:`X`).join``).join`
`
```

```
<input type=number oninput=o.textContent=f(+this.value)><pre id=o>
```

The Y-axis is the reverse of the OP.

# Answer
> 2 votes
# Röda, 74 bytes

```
f n{seq n-1,0|{|y|seq 0,n-1|{|x|["X"]if[(x^2+y^2)%n=1]else[" "]}_;["
"]}_}

```

Try it online!

Ungolfed:

```
function f(n) {
    seq(n-1, 0) | for y do
        seq(0, n-1) | for x do
            if [ (x^2 + y^2) % n = 1 ] do
                push("X")
            else
                push(" ")
            done
        done
        print("")
    done
}

```

# Answer
> 2 votes
# Python 3, ~~87~~ 83 bytes

```
lambda n:"\n".join("".join(" X"[(y*y+x*x)%n==1]for x in range(n))for y in range(n))

```

Try it online!

The y-axis is inverted

# Answer
> 2 votes
# Jelly, ~~14~~ 13 bytes

```
R²+þ`%=1ị⁾X Y

```

The x-axis is inverted.

Try it online!

### How it works

```
R²+þ`%=1ị⁾X Y  Main link. Argument: n

R              Range; yield [1, ..., n].
 ²             Square; yield [1², ..., n²].
  +þ`          Self table addition; compute x+y for all x and y in [1², ..., n²],
               grouping by the values of y.
     %         Take all sums modulo n.
      =1       Compare them with 1, yielding 1 or 0.
        ị⁾X    Index into "X ".
            Y  Separate by linefeeds.

```

# Answer
> 1 votes
# dc, 79 bytes

```
?dsRsQ[88P]sl[32P]sH[0sM[lM2^lR2^+lQ%d1=l1!=HlM1+dsMlQ>c]dscx10PlR1-dsR0<S]dsSx

```

The `y`-axis is inverted whereas the `x`-axis is not.

Try it online!

# Answer
> 1 votes
# Python 3, (102 98 95 bytes)

### y-axis inverted

```
n=int(input());r=range(n);p=print
for i in r:
 for j in r:p(end=' 'if(i*i+j*j)%n-1else'X')
 p()

```

Try it online!

* saved 4 bytes: omitted variable c in c=' 'if(i*i+j*j)%n-1else'X'
* saved 3 bytes: Thanks to ovs (modified print statement)

# Answer
> 1 votes
# MATL, 13 bytes

```
:qU&+G\1=88*c

```

Origin is at top left. So the output is flipped upside down compared with the examples in the challenge.

Try at MATL online!

### Explanation

```
:      % Input n implicitly. Push [1 2 ... n]
q      % Subtract one (element-wise)
U      % Square (element-wise)
&+     % Matrix of pairwise sums
G      % Push n
\      % Modulo
1=     % Equal to 1? (element-wise)
88*    % Multiply by 88 (ASCII code of 'X')
c      % Convert to char. Char 0 will be displayed as a space
       % Display implicitly

```

# Answer
> 1 votes
## Lithp, 125 bytes

```
#N::((join(map(seq(- N 1)0)(scope #Y::((join(map(seq 0(- N 1))(scope #X::
((?(== 1(@(+(* X X)(* Y Y))N))"X" " "))))""))))"\n")

```

Linebreak for readability.

Try it online!

Not the shortest. I think I need some sort of shorthand module. See the Try it Online link for further explanation, ungolfed version, and some tests. For best results, expand the output window to see more.

# Answer
> 1 votes
# Python 3, 82 bytes

```
f=lambda n,k=0:k<n>f(n,k+1)!=print(''.join(' X'[(k*k+j*j)%n==1]for j in range(n)))

```

Try it online!

# Answer
> 1 votes
# GNU APL, 41 chars, 59 bytes

Reads an integer and displays the circle.

```
N←⎕◊⌽{(⍵+1)⊃' ' 'X'}¨{1=(N|(+/⍵*2))}¨⍳N N

```

### Ungolfed

```
N←⎕
⌽                           ⍝ flip the X axis so 0,0 is bottom left
{
    (⍵+1) ⊃ ' ' 'X'         ⍝ substitute space for 0, X for 1
} ¨ {
    1=(N|(+/⍵*2))           ⍝ mod(x*x+y*y, 1)==1
} ¨ ⍳N N                    ⍝ generate an NxN grid of coordinates

```

# Answer
> 0 votes
# Haskell, 115 bytes

```
n#(a,b)|mod(a*a+b*b)n==1='X'|1>0=' '
m n=map(n#)<$>zipWith(zipWith(,))(replicate n[0..n-1])(replicate n<$>[0..n-1])

```

The y axis is inverted.

Try it online!

All those parentheses are kind of annoying me...

## Explanation

```
n#(a,b)|mod(a*a+b*b)n==1='X'|1>0=' '
n#(a,b)                                 --Operator #, takes a number n and a tuple (a,b)
       |mod(a*a+b*b)n==1                --Test if the mod equals 1
                        ='X'            --If so, return 'X'
                            |1>0=' '    --Otherwise, return ' '

m n=map(n#)<$>zipWith(zipWith(,))(replicate n[0..n-1])(replicate n<$>[0..n-1])
m n=                                                                           --Make a new function m with argument n
                                 (replicate n[0..n-1])                         --Make a list of [[0,1,2,3..n-1],[0,1,2,3..n-1],(n times)]
                                                      (replicate n<$>[0..n-1]) --Make a list of [[0,0,0(n times)],[1,1,1(n times)]..[n-1,n-1,n-1(n times)]
              zipWith(zipWith(,))                                              --Combine them into a list of list of tuples
    map(n#)<$>                                                                 --Apply the # operator to every tuple in the list with the argument n

```

# Answer
> 0 votes
# , 20 bytes

```
' x'{~1=[|+/~@:*:@i.

```

Try it online!

# Answer
> 0 votes
# GolfScript, 34 bytes

```
~:c,{.*}%:a{:b;a{b+c%1=' x'=}%}%n*

```

Try it online!

I really don't like using variables...

---
Tags: code-golf, math, ascii-art, abstract-algebra
---