title: mtDNA mutation tree

text:
# Question
Title: mtDNA mutation tree
**Background:**

MtDNA is a part of the human DNA that is passed from a mother to a child and it rarely mutates. Since this is true for all humans it is possible to create a huge tree that visualize how all humans are related to each other through their maternal ancestry all the way back to the hypothetical EVE. Every mutation in the MtDNA when a child is born creates a new sub-branch from its parent branch in the tree.

Find out more about Mitochondrial DNA (mtDNA) here: https://en.wikipedia.org/wiki/Mitochondrial\_DNA

**Objective:**

> Your program is served a list of mtDNA tree branches mutation count and your program should deliver a tree view of it

**Example input and output:**

The input is a 3-column semi-colon separated table with a line for each branch. Example:

```
L0a'b'f'k;L0;14
L0a'b'f;L0a'b'f'k;23
L0;mtEVE;10
L0a'b;L0a'b'f;30
L0a;L0a'b;38
L0a1'4;L0a;39
L0a1;L0a1'4;40
L0a1a;L0a1;42
L0a1a NL;L0a1a;43
L0a1a1;L0a1a NL;44
L0a1a2;L0a1a NL;45
L0a1a3;L0a1a NL;44
L0a1 NL;L0a1;41
L0a1b;L0a1 NL;44
L0a1b NL;L0a1b;45
L0a1b1;L0a1b NL;46
L0a1b1a;L0a1b1;47
L0a1b1a1;L0a1b1a;48
L0a1b2;L0a1b NL;48
L0a1b2a;L0a1b2;50
L0a1c;L0a1 NL;45
L0a1d;L0a1 NL;44
L0a4;L0a1'4;55
L0a2;L0a;47
L0a2a;L0a2;49
L0a2a1;L0a2a;50
L0a2a1a;L0a2a1;51
L0a2a1a1;L0a2a1a;53
L0a2a1a2;L0a2a1a;53
L0a2a2;L0a2a;53
L0a2a2a;L0a2a2;54
L0a2b;L0a2;57
L0a2b1;L0a2b;58
L0a2c;L0a2;60
L0a2d;L0a2;49
L0a3;L0a;53
L0b;L0a'b;48
L0f;L0a'b'f;37
L0f1;L0f;61
L0f2;L0f;41
L0f2a;L0f2;46
L0f2a1;L0f2a;59
L0f2b;L0f2;63
L0k;L0a'b'f'k;39
L0k1;L0k;48
L0k2;L0k;54
L0d;L0;21
L0d1'2;L0d;25
L0d1;L0d1'2;30
L0d1 NL;L0d1;31
L0d1a;L0d1 NL;38
L0d1a1;L0d1a;41
L0d1c;L0d1 NL;39
L0d1c1;L0d1c;45
L0d1c1a;L0d1c1;46
L0d1c1b;L0d1c1;46
L0d1b;L0d1 NL;36
L0d1b1;L0d1b;40
L0d2;L0d1'2;31
L0d2a'b;L0d2;32
L0d2a;L0d2a'b;42
L0d2a1;L0d2a;43
L0d2b;L0d2a'b;46
L0d2c;L0d2;45
L0d3;L0d;39

```

Your program should output a left-to-right tree view including some numbers based on the input. Based on the example input, this is valid output:

```
  0│ ┐                                                               mtEVE               [  0][ 63]
 10│ └♦♦♦♦♦♦♦♦♦┬────────────────┬─────────────────────────────────── L0                  [ 10][ 63]
 21│           │                └♦♦♦♦♦♦♦♦♦♦┬──────┬───────────────── L0d                 [ 11][ 46]
 39│           │                           │      └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d3                [ 18][ 39]
 25│           │                           └♦♦♦┐                     L0d1'2              [  4][ 46]
 30│           │                               ├♦♦♦♦┬─────────────── L0d1                [  5][ 46]
 31│           │                               │    └┬────┬┐         L0d1 NL             [  1][ 46]
 36│           │                               │     │    │└♦♦♦♦┬─── L0d1b               [  5][ 40]
 40│           │                               │     │    │     └♦♦♦ L0d1b1              [  4][ 40]
 38│           │                               │     │    └♦♦♦♦♦♦┬── L0d1a               [  7][ 41]
 41│           │                               │     │           └♦♦ L0d1a1              [  3][ 41]
 39│           │                               │     └♦♦♦♦♦♦♦┬────── L0d1c               [  8][ 46]
 45│           │                               │             └♦♦♦♦♦┬ L0d1c1              [  6][ 46]
 46│           │                               │                   ├ L0d1c1a             [  1][ 46]
 46│           │                               │                   └ L0d1c1b             [  1][ 46]
 31│           │                               └♦♦♦♦♦┬┬───────────── L0d2                [  6][ 46]
 45│           │                                     │└♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d2c               [ 14][ 45]
 32│           │                                     └┬──┐           L0d2a'b             [  1][ 46]
 42│           │                                      │  └♦♦♦♦♦♦♦♦♦┬ L0d2a               [ 10][ 43]
 43│           │                                      │            └ L0d2a1              [  1][ 43]
 46│           │                                      └♦♦♦♦♦♦♦♦♦♦♦♦♦ L0d2b               [ 14][ 46]
 14│           └♦♦♦┬────────┐                                        L0a'b'f'k           [  4][ 63]
 39│               │        └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦┬─────┬──────── L0k                 [ 25][ 54]
 48│               │                                 │     └♦♦♦♦♦♦♦♦ L0k1                [  9][ 48]
 54│               │                                 └♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0k2                [ 15][ 54]
 23│               └♦♦♦♦♦♦♦♦┬──┐                                     L0a'b'f             [  9][ 63]
 30│                        │  └♦♦♦♦♦♦┬───────────┐                  L0a'b               [  7][ 60]
 48│                        │         │           └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0b                 [ 18][ 48]
 38│                        │         └♦♦♦♦♦♦♦┬────┬─┬────────────── L0a                 [  8][ 60]
 53│                        │                 │    │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0a3                [ 15][ 53]
 39│                        │                 │    └┬────┐           L0a1'4              [  1][ 55]
 40│                        │                 │     │    └┬────┬──── L0a1                [  1][ 50]
 42│                        │                 │     │     │    └♦┬── L0a1a               [  2][ 45]
 43│                        │                 │     │     │      └┬┐ L0a1a NL            [  1][ 45]
 44│                        │                 │     │     │       │├ L0a1a1              [  1][ 44]
 44│                        │                 │     │     │       │└ L0a1a3              [  1][ 44]
 45│                        │                 │     │     │       └♦ L0a1a2              [  2][ 45]
 41│                        │                 │     │     └┬────┬┐   L0a1 NL             [  1][ 50]
 44│                        │                 │     │      │    │└♦♦ L0a1d               [  3][ 44]
 45│                        │                 │     │      │    └♦♦♦ L0a1c               [  4][ 45]
 44│                        │                 │     │      └♦♦┬───── L0a1b               [  3][ 50]
 45│                        │                 │     │         └┬─┐   L0a1b NL            [  1][ 50]
 46│                        │                 │     │          │ └┬─ L0a1b1              [  1][ 48]
 47│                        │                 │     │          │  └┬ L0a1b1a             [  1][ 48]
 48│                        │                 │     │          │   └ L0a1b1a1            [  1][ 48]
 48│                        │                 │     │          └♦♦┬─ L0a1b2              [  3][ 50]
 50│                        │                 │     │             └♦ L0a1b2a             [  2][ 50]
 55│                        │                 │     └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0a4                [ 16][ 55]
 47│                        │                 └♦♦♦♦♦♦♦♦┬─┬───┬────┬─ L0a2                [  9][ 60]
 49│                        │                          │ │   │    └♦ L0a2d               [  2][ 49]
 49│                        │                          │ │   └♦┬┬─── L0a2a               [  2][ 54]
 50│                        │                          │ │     │└┬── L0a2a1              [  1][ 53]
 51│                        │                          │ │     │ └┬─ L0a2a1a             [  1][ 53]
 53│                        │                          │ │     │  ├♦ L0a2a1a1            [  2][ 53]
 53│                        │                          │ │     │  └♦ L0a2a1a2            [  2][ 53]
 53│                        │                          │ │     └♦♦♦┬ L0a2a2              [  4][ 54]
 54│                        │                          │ │         └ L0a2a2a             [  1][ 54]
 57│                        │                          │ └♦♦♦♦♦♦♦♦♦┬ L0a2b               [ 10][ 58]
 58│                        │                          │           └ L0a2b1              [  1][ 58]
 60│                        │                          └♦♦♦♦♦♦♦♦♦♦♦♦ L0a2c               [ 13][ 60]
 37│                        └♦♦♦♦♦♦♦♦♦♦♦♦♦┬─┬─────────────────────── L0f                 [ 14][ 63]
 61│                                      │ └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0f1                [ 24][ 61]
 41│                                      └♦♦♦┬───┬───────────────── L0f2                [  4][ 63]
 46│                                          │   └♦♦♦♦┬──────────── L0f2a               [  5][ 59]
 59│                                          │        └♦♦♦♦♦♦♦♦♦♦♦♦ L0f2a1              [ 13][ 59]
 63│                                          └♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦ L0f2b               [ 22][ 63]

```

**Input: Details**

The input table is *not* sorted in any particular order. If we randomly reorder the input lines, the output should remain the same.

Each line in the input represents a mtDNA tree branch or a hypothetical tree branch. The input table could be any number of lines in length.

**Input: Details - Column A (branch name):**

The first column is the actual branch name. The name divides the input lines into 2 groups of line types that should be handled different (explained later) from each other:

* Type 1: Name consists of any `'` or the suffix `NL`
* Type 2: Name doesn't consist of any `'` or the suffix `NL`.

The name can be up to 20 characters in length.

**Input: Details - Column B (parent branch name):**

The second column contains a pointer to the parent branch name. Several lines (branches) can share the same parent. There is always exactly 1 distinct parent branch name in the input table that points to a parent that isn't represented among the input lines, that parent branch name is the root for the tree. In the example input that is the third line pointing to the root: `mtEVE`. If the input has more than one root, or endless loops, it is an invalid input.

**Input: Details - Column C (# of mutations):**

The third column is the total number of mutations that particular branch has had counting from the root. Human mtDNA hasn't mutated more than 100 times in a single line from the hypothetical maternal root (Human/chimp ancestor EVE), but your program should be able to handle 3 digit # of mutations, up to 999.

From the input you can calculate a branch # of unique mutations by substracting its # of mutations from its parent # of mutations.

**Output: Details**

Your program should output 1 out of 3 different error messages if the input is invalid according to the input description.

* Error message 1, if the input has more than one root: `ERROR: Multiple roots`
* Error message 2, if the input parent pointers loops: `ERROR: Endless loop`
* Error message 3, anything else invalid about the input: `ERROR: Invalid input`

If the input contains no errors, your program should output the tree according to the following constraints: Each line consists of 5 parts A, B, C, D, and E:

* A: 5 characters, 3 char right-aligned # of mutations, a vertical line character: `|` and 1 blankspace
* B: \[max # of mutations\] characters wide tree + 1 blankspace
* C: 20 characters, left-aligned branch name
* D: 5 characters, 3 character right-aligned # of unique mutations for the branch encapsulated between `[` and `]`. (Unique mutations will be explained below).
* E: 5 characters, 3 character right-aligned max # of total mutations for this branch and all child-branches encapsulated between `[` and `]`.

A branch # of unique mutations is the difference in # of mutations the current branch has from the # of mutations its parent branch has. The first line is the root and it should be represented with `0` for # of mutations and # of unique mutations.

**Output: Details - line order/sortation**

If two or more sub-branches are sharing the same parent, the branches are ordered by the sub-branches maximum # of total mutations in descending order. In our example `L0a1'4`, `L0a3` and `L0a2` shares the parent: `L0a`.

In the tree view the order from top to bottom is, sub-branches maximum # of total mutations within parenthesis: `L0a3` (53), `L0a1'4` (55), `L0a2` (60).

If two or more sub-branches shares the same maximum # of mutations on child branches, they are vertically aligned and branched from their parent from the same spot, line ordering among those sub-branches is alphabetical.

**Output: Details - tree (part B)**

The tree should be drawn with the following ascii characters: , , , , , ,

The logic of the tree is that all mutations should be represented. A branch from a parent branch:  or  represents 1 mutation. Additional unique mutations on the same branch are represented by:  and they must be left-aligned and placed before the first sub-branch.

Sub-branches are branched from their parent along the x-axis and the position is determined by the maximum # of mutations among all subsequent child branches.

As hinted before the input has 2 different type of input lines. Type 1 with any ' characters or the NL suffix in the branch name, should not fill the horizontal line to the far right on their line but end with a  on the last sub-branch. In the example it is applied to the following branches:

```
L0a'b'f'k;L0;14
L0a'b'f;L0a'b'f'k;23
L0a'b;L0a'b'f;30
L0a1'4;L0a;39
L0a1a NL;L0a1a;43
L0a1 NL;L0a1;41
L0a1b NL;L0a1b;45
L0d1'2;L0d;25
L0d1 NL;L0d1;31
L0d2a'b;L0d2;32

```

Hopefully the example input and output answers any additional questions about how the tree should be drawn, consider it part of the challenge to figure out the logic.

**Inspiration**

You are welcome to try out my (un-golfed) javascript version for inspiration: http://artificial.se/DNA/mtDNAmutationTree3.html (it lacks error checking, and some statistics is added that is not part of this particular challenge).

A complete mtDNA-tree version \[based on http://www.phylotree.org/ mtDNA tree Build 16 (19 Feb 2014)\] can be found here:

http://artificial.se/DNA/mtDNAfull.html

The data-file used for the full tree:

http://artificial.se/DNA/mtDNA\_full.txt

This is a code-golf challenge.

# Answer
> 6 votes
# Python 3, 925 bytes

Yay, under 1 KB! Probably still room for golfing...

```
import sys
class L:
 def __init__(x,**k):x.__dict__.update(k)
m={}
def e(x):print('ERROR: '+x);exit()
try:
 for x in sys.stdin:a,b,c=x.split(';');m[a]=L(s=a,p=b,m=int(c),l=0)
except:e('Invalid input')
a=set()
def k(x):
 if x.l<0:e('Endless loop')
 if x.l<1:y=m.get(x.p);x.l=-1;k(y)if y else a.add(x.p);x.l=1
for x in m:k(m[x])
r=L(s=a.pop(),p=0,m=0)
if a:e('Multiple roots')
m[r.s]=r
c={}
def u(x):
 c[x.s]=[m[y]for y in m if m[y].p==x.s];x.x=x.m
 for y in c[x.s]:u(y);x.x=max(x.x,y.x)
u(r)
o=[]
def f(p,x,o=o):
 d=x.m-p.m;j=p.m+r.x-x.x;s=x.s;x.i=len(o);l=sorted(c[s],key=lambda t:(t.x,t.s));q=' '*j+'└'+'♦'*(d-1);z='─'
 if"'"in s or s[-2:]=='NL'or x==r:q+=z*(x.x-l[0].x);z=' '
 o+=list("%3d│ "%x.m+q+z*(r.x-len(q))+' %-20s[%3d][%3d]'%(s,d,x.x)),;j+=5;o[p.i][j]='┐┬'[o[p.i][j]in'─┬']
 for i in range(p.i+1,x.i):o[i][j]='├│'[o[i][j]in' │']
 for y in l:f(x,y)
f(r,r)
print('\n'.join(''.join(x)for x in o))

```

---
Tags: code-golf, ascii-art, tree-traversal
---


title: Poor man's LaTeX

text:
# Question
Title: Poor man's LaTeX
You are transported in a parallel universe where people write mathematical equations on computers as ASCII art by hand. As a LaTeX addict, this is totally unacceptable, and you ought to automate this process somewhat.

Your goal is to write a program that outputs an ASCII version of an equation inputed as a LaTeX math command.

### Mandatory LaTeX commands to support

* Sum: the LaTeX command for a sum is `\sum_{lower bound}^{upper bound}`

The ASCII figure you have to use for sums is:

```
upper bound
    ___
    \  `
    /__,
lower bound

```
* Product: the LaTeX command for a product is `\prod_{lower bound}^{upper bound}`

The ASCII figure you have to use for products is:

```
upper bound
    ____
    |  |
    |  |
lower bound

```
* Fraction: the LaTeX command for fractions is `\frac{numerator}{denominator}`

The ASCII figure you have to use for fractions is:

```
 numerator
-----------
denominator

```

Anything that is not one of those three commands is displayed as is. For example, `\sum{i=3}^{e^10}\frac{3x+5}{2}`should be displayed as

```
e^10
___  3x+5
\  ` ----
/__,  2
i=3

```

### Inputs

The input is a LaTeX command passed as a string (or your language's equivalent to strings). LaTeX commands can be nested, for instance `\frac{\frac{1}{2}}{3}` is a valid input. Inputs are supposed to be always correct (no need to check LaTeX's syntax in your code). Inputs will only consist of the three LaTeX commands presented above and 'text' that you won't need to format.

LaTeX commands will always come with the syntax presented above, i.e. sums and products will always have upper and lower bounds (although they can be empty) and there will always be a numerator and denominator for fractions.

We assume that the bounds of sums and products are at most 4 characters long (= the width of the sum and product symbols), so that you don't have to worry about possible overlap issues. For similar reasons, we assume that the bounds are just 'text' and will never be LaTeX commands, e.g. `\sum_{\sum_{1}^{2}}^{1}` is not a valid input.

### Outputs

Your program's output is the ASCII representation of the LaTeX command you were given as input.

Your program has to take horizontal alignment into account: for instance, the bounds of the sum or the product have to be horizontally aligned with the sum or product symbol (which are both 4 characters wide). If the bound has an odd number of characters, it does not matter whether it is one character off to the right or to left of the center, whichever is fine. The fraction's line has to be as long as the numerator or the denominator, whichever is the longest.

Your program has to take vertical alignment into account: for instance, `\frac{\frac{1}{2}}{3} = \frac{1}{6}` should be displayed as

```
1
-
2   1
- = -
3   6

```

For sums and products, since the symbols are 4 characters high, the vertical center is assumed to be the second line from the top.

Horizontal spacing is assumed to be correct in the given input, i.e. the spaces in the input should be displayed in the output.

### Test cases

* Input `abc = 2`

Output `abc = 2`
* Input `e = \sum_{n=0}^{+inf} \frac{1}{n!}`

Output

```
    +inf
    ___  1
e = \  ` --
    /__, n!
    n=0

```
* Input `e^x = 1 + \frac{x}{1 - \frac{x}{2 + x - ...}}`

Output

```
                 x
e^x = 1 + ---------------
                   x
          1 - -----------
              2 + x - ...

```
* Input `\prod_{i=1}^{n} \frac{\sum_{j=0}^{m} 2j}{i + 1}`

Output

```
       m
      ___
      \  ` 2j
 n    /__,
____  j=0
|  |  -------
|  |   i + 1
i=1

```
* Input `\frac{sum}{prod} = \sum_{frac}^{prod} sum`

Output

```
       prod
sum    ___
---- = \  ` sum
prod   /__,
       frac

```

### Scoring

This is , so the shortest code wins.

# Answer
# Python 2, ~~656~~ ~~627~~ 618 bytes

```
M=max
O=lambda l,o=2:[(p+o,c)for p,c in l]
def C(s,m=0):
 if''<s<'}'[m:]:f,w,h,d,s=C(s,1);F,W,H,D,s=C(s);e=M(d,D);return[O(f,e-d)+O(F,w*1j+e-D),w+W,M(h-d,H-D)+e,e,s]
 if'\\'!=s[:1]:return[[(0,s[:1])]*m,m,m,0,s[1:]]
 t=s[1]<'s';e=s[1]>'f';f,w,h,d,s=C(s[5+t+e:]);F,W,H,D,s=C(s[1+e:]);g=M(w,W);G=C('-'*g)[0]
 if e:f,w,h,F,W,H=F,W,H,f,w,h;g=4;p=C('|  |')[0];G=C('_'*(3+t))[0]+[O(C('/__,')[0])+[(1,'\\'),(1+3j,'`')],O(p,1)+O(p)][t]
 x=M(w,W,g);return[O(f,(x-w)/2*1j)+O(F,(x-W)/2*1j+h+3**e)+O(G,(x-g)/2*1j+h),x,h+3**e+H,h+e,s]
f,w,h,d,s=C(raw_input())
for y in range(h):print"".join(dict(f).get(y+x*1j,' ')for x in range(w))

```

Takes input on STDIN and writes output to STDOUT.

The program assumes that no other control sequence than `\frac`, `\sum` or `\prod` appears in the input (i.e., it won't show as normal text,) and that `~` doesn't appear as well (it has a special meaning in math mode anyway.) On the other hand, the program *does* support arbitrary formulas as limits for `\sum` and `\prod`.

## Explanation

It works just like TeX! (well, sort of...) Each subformula (starting from single characters and building up to more complex formulas) is turned into a box, with an associated width, height and depth (baseline). Boxes of simpler formulas are combined into bigger boxes to form complex formulas, and so on. The contents of each box are represented as a list of position/character pairs, relative to the top-left corner of the box; when boxes are combined into a bigger box, the positions are offset according to the relative positions of the smaller boxes inside the bigger one, and the lists are concatenated.

Eventually, we end up with a top-level box, which is converted to a printable form.

---

To spice it up a little, the following version also supports square roots:

```
M=max;R=range
O=lambda l,o=2:[(p+o,c)for p,c in l]
def C(s,m=0):
 if''<s<'}'[m:]:f,w,h,d,s=C(s,1);F,W,H,D,s=C(s);e=M(d,D);return[O(f,e-d)+O(F,w*1j+e-D),w+W,M(h-d,H-D)+e,e,s]
 if'\\'!=s[:1]:return[[(0,s[:1])]*m,m,m,0,s[1:]]
 t=s[1]<'s';e=s[1]>'f';f,w,h,d,z=C(s[5+t+e:])
 if'r'>s[2]:return[O(f,1j+h*1j+1)+O(C('_'*w)[0],1j+h*1j)+[(h,'\\')]+[(h-y+y*1j+1j,'/')for y in R(h)],w+1+h,h+1,d+1,z]
 F,W,H,D,s=C(z[1+e:]);g=M(w,W);G=C('-'*g)[0]
 if e:f,w,h,F,W,H=F,W,H,f,w,h;g=4;p=C('|  |')[0];G=C('_'*(3+t))[0]+[O(C('/__,')[0])+[(1,'\\'),(1+3j,'`')],O(p,1)+O(p)][t]
 x=M(w,W,g);return[O(f,(x-w)/2*1j)+O(F,(x-W)/2*1j+h+3**e)+O(G,(x-g)/2*1j+h),x,h+3**e+H,h+e,s]
f,w,h,d,s=C(raw_input())
for y in R(h):print"".join(dict(f).get(y+x*1j,' ')for x in R(w))
```

Examples:

* `\frac{-b +- \sqrt{b^2 - 4ac}}{2a}`

```
        _________
-b +- \/b^2 - 4ac
-----------------
       2a

```
* `|v| = \sqrt{ \sum_{i}^{} v[i]^2 }`

```
           _____________
          / ___
|v| =    /  \  ` v[i]^2
        /   /__,
      \/     i

```
> 23 votes

# Answer
# LaTeX, 540 532 characters

Disclaimer: This is not perfect and arguably does not count as a valid answer.

```
\usepackage[LGRgreek]{mathastext}
\renewcommand{\sum}{\kern-1ex\displaystyle\mathop{\vphantom{\int}\begin{array}{l}\mbox{\underline{\hspace{12pt}}}\\ \mbox{\textbackslash}\hspace{8pt}`\\\mbox{/\underline{\hspace{8pt}},}\end{array}}\displaylimits}
\renewcommand{\prod}{\kern-1ex\displaystyle\mathop{\vphantom{\int}\begin{array}{c}\mbox{\underline{\hspace{16pt}}}\\|\ \ \ \ | \\| \ \ \ \ |\end{array}}\displaylimits}
\renewcommand{\frac}[2]{\mathop{\xleaders\hbox{-}\hfill\kern0pt}\limits^{#1}_{#2}}
\DeclareMathSizes{10}{10}{10}{10}

```

Some help from @Fatalize, see comments for details.

### Test:

**Input:** `\prod_{i=1}^{n} \frac{\sum_{j=0}^{m} 2j}{i + 1}`

**Output:**

As you can see, the output does not exactly follow the spec. This may disqualify my answer, but I still think it's worth posting.

I wrote this on sharelatex.com. You can play with it here.
> 23 votes

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


# Question
Title: Snakes and Ladders probability of winning
(This is my first Q here, and I don't know much about code golfing.)

Your aim is to predict the winner of an ongoing Snakes and Ladders game.

**INPUT**

* A single number (2-1000) indicating the number of spaces on the board, say *x*.
* Another number (2-4) indicating number of players, say *n*.
* *n* numbers, each giving the position of each player on the game board.
* Another number (1-15) indicating number of snakes and ladders (combined), say *s*.
* *s* lines of input, each with 2 numbers - the start and end of each snake/ladder.

**OUTPUT**

*n* decimal numbers, accurate to 2 decimal places, indicating the probability of each player winning.

**WINNER**

The person to give the fastest program wins, not necessarily the shortest code. This might help those using a different algorithm to gain a huge advantage.

**Notes**

Players start on space 1, not 0. They win on reaching space *x*.

All players use a fair 6 sided dice. There are no re-rolls for 6s.

We assume that there is no 'bad' input given, such as more than 4 players, or a snake starting at the last space.

Players are given the same order of play as your input. The first player is the first to roll now, then the second and so on.

Even if you overshoot the win space, you still win.

# Answer
# C, ~.25 seconds

I have calculated by using dynamic simulations instead of probability of each dice roll. The more accurate the probability, the slower... here a brief code...

Compile using:

```
gcc -o Snakes snakes.c

```

Code:

```
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

int main()
{
    srand(time(0));

    // initialize principal variables
    int NumberOfSpaces   = 100,
    NumberOfPlayers  = 4,
    PlayerPosition[] = { 46, 56, 36, 66 };
    //PlayerPosition[] = {0, 0, 0, 0};

    // arrays of positions, must be in numerical order,
    // must be in (start, end) format. correct - 1, 2, 5, 6, 8, 9
    //                               incorrect - 1, 2, 8, 9, 5, 6
    int LadderPositions[10] = { 3, 10, 5, 20, 20, 31, 22, 49, 44, 87 },      // positions of ladders
    SnakePositions[10] = { 11, 3, 15, 1, 35, 22, 54, 29, 60, 20 }, // positions of snakes
    SnakesLadders    = 10;                                       // # of snakes + ladders

    // static arrays to hold
    // # of dice rolls to complete game
    int Player1Wins[10000],
    Player2Wins[10000],
    Player3Wins[10000],
    Player4Wins[10000];

    int NumberOfSimulations = 10001;

    int OutsideLoop, Counter = 1, i, a, Win, EvenArray;
    for (OutsideLoop = 0; OutsideLoop < NumberOfPlayers; OutsideLoop++)      // do a simulation for each player
        for (a = 0; a < NumberOfSimulations; a++)                       // play for each simulation
        {
            for (i = PlayerPosition[OutsideLoop]; i <= NumberOfSpaces + 1; i += (rand() % 6 + 1)) // roll the dice for each turn
            {
                Counter++ ;
                for (EvenArray = 0; EvenArray < SnakesLadders; EvenArray+=2) // check if space is snake or ladder
                {
                    if (i == LadderPositions[EvenArray])
                        i = LadderPositions[EvenArray + 1];
                    if (i == SnakePositions[EvenArray])
                        i = SnakePositions[EvenArray + 1];
                }
             }
             // put value in array
             if (OutsideLoop == 0)
                 Player1Wins[a] = Counter;
             else if (OutsideLoop == 1)
                 Player2Wins[a] = Counter;
             else if (OutsideLoop == 2)
                 Player3Wins[a] = Counter;
             else if (OutsideLoop == 3)
                 Player4Wins[a] = Counter;
             Counter = 0;
        }

    // count how many time each person won
    int P1Wins = 0, P2Wins = 0, P3Wins = 0, P4Wins, Ties = 0;
    for (Win = 0; Win < NumberOfSimulations; Win++)
    {
        if (Player1Wins[Win] < Player2Wins[Win] && Player1Wins[Win] < Player3Wins[Win] && Player1Wins[Win] < Player4Wins[Win])
            P1Wins++;
        else if (Player2Wins[Win] < Player1Wins[Win] && Player2Wins[Win] < Player3Wins[Win] && Player2Wins[Win] < Player4Wins[Win])
            P2Wins++;
        else if (Player3Wins[Win] < Player1Wins[Win] && Player3Wins[Win] < Player2Wins[Win] && Player3Wins[Win] < Player4Wins[Win])
            P3Wins++;
        else if (Player4Wins[Win] < Player1Wins[Win] && Player4Wins[Win] < Player2Wins[Win] && Player4Wins[Win] < Player3Wins[Win])
            P4Wins++;
        else if (Player2Wins[Win] == Player1Wins[Win] == Player3Wins[Win])
            Ties++;
    }

    printf("[ + ] Namaste! Welcome to the Snakes & Ladders guess who wins program!\n");
    printf("[ + ] I will run 10K simulations of the game to make a guess on the probability of the winner.\n");
    printf("[ + ] Given %i players, with starting positions of :\n[ + ] P1 - %i\n[ + ] P2 - %i\n[ + ] P3 - %i\n[ + ] P4 - %i\n[ + ] Here's the probability I think each player has of winning...\n", NumberOfPlayers, PlayerPosition[0], PlayerPosition[1], PlayerPosition[2], PlayerPosition[3]);
    printf("[ + ] P1 = %i / 10000\n[ + ] P2 = %i / 10000\n[ + ] P3 = %i / 10000\n[ + ] P4 = %i / 10000\n[ + ] Ties = %i\n", P1Wins, P2Wins, P3Wins, P4Wins, Ties);
    return 0;
}

```

Environment - timed using `time` (bash command) on linux core i7

10 simulations ~ .003 second

10000 simulation ~ .030 second

Sample outputs :

```
time ./Snakes
[ + ] Namaste! Welcome to the Snakes & Ladders guess who wins program!
[ + ] I will run 10K simulations of the game to make a guess on the probability of the winner.
[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 10
[ + ] P2 - 21
[ + ] P3 - 50
[ + ] P4 - 70
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 86 / 10000
[ + ] P2 = 254 / 10000
[ + ] P3 = 131 / 10000
[ + ] P4 = 9098 / 10000
[ + ] Ties = 0
real    0m0.036s
user    0m0.036s
sys 0m0.000s

```

Alt input position:

```
[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 15
[ + ] P2 - 5
[ + ] P3 - 60
[ + ] P4 - 50
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 955 / 10000
[ + ] P2 = 3041 / 10000
[ + ] P3 = 1833 / 10000
[ + ] P4 = 3572 / 10000
[ + ] Ties = 0
real    0m0.024s
user    0m0.024s
sys     0m0.000s

```

More input:

```
[ + ] Given 4 players, with starting positions of :
[ + ] P1 - 46
[ + ] P2 - 56
[ + ] P3 - 36
[ + ] P4 - 66
[ + ] Here's the probability I think each player has of winning...
[ + ] P1 = 94 / 10000
[ + ] P2 = 442 / 10000
[ + ] P3 = 2454 / 10000
[ + ] P4 = 6319 / 10000
[ + ] Ties = 0
real    0m0.018s
user    0m0.018s
sys     0m0.000s

```
> 3 votes

---
Tags: game, fastest-code, board-game
---


title: Calculate the Orthocenter of a Triangle

text:
# Question
Title: Calculate the Orthocenter of a Triangle
Try to write the shortest program or function you can that prints or returns the calculated orthocenter of a triangle.

The orthocenter of a triangle is the intersection point of the three altitudes of a triangle. The altitude of a triangle is a perpendicular segment from the vertex of the triangle to the opposite side.

Input:

* Three points in 2D space correponding to the triangle's vertices

Output:

* The calculated orthocenter of the triangle

A sample input would be

```
A(0,0)
B(3,6)
C(6,0)

```

and a sample output would be:

```
Calculated Othocenter (3, 1.5)

```

One formula for orthocenter can be written as

```
(x, y) = ((ax*tan(α) + bx*tan(β) + cx*tan(γ))/(tan(α) + tan(β) + tan(γ),
          (ay*tan(α) + by*tan(β) + cy*tan(γ))/(tan(α) + tan(β) + tan(γ))

```

Shortest program in bytes wins.

# Answer
> 5 votes
# Python, ~~193~~ 168

Should work for any valid triangle...

```
def h(a,A,b,B,c,C):
 if A==B:b,B,c,C=c,C,b,B
 m=(a-b)/(B-A)
 return m,C-m*c
def f(a,A,b,B,c,C):
 m,q=h(a,A,b,B,c,C)
 k,z=h(c,C,b,B,a,A)
 x=(q-z)/(k-m)
 return (x,k*x+z)

```

# Answer
> 4 votes
# CJam, 90 bytes

```
q~:C2$]_2ew::.-:D;;D1=0=D2=0=*D1=1=D2=1=*+D0=1=D2=0=*D0=0=D2=1=*-/_D0=1=*C0=+C1=@D0=0=*-S\

```

Try it online

CJam isn't really optimized for geometry, so the code isn't doing anything fancy. It uses the parametric representation for two of the lines passing through a corner and being orthogonal to the opposite side, and solves the 2x2 system of equations resulting from intersecting the two lines. Well, it only needs one of the resulting parameters, which is then used for calculating the intersection point.

Note that some of the signs in the intermediate values are wrong. Instead of flipping them with additional code, I kept them the way they are, and corrected for the wrong sign by changing additions to subtractions (or vice versa) when the value is used later. For example, if you see a `+` where you would normally expect a `-` when calculating a determinant, that's because one of the terms has the wrong sign. In fact, both determinants have the wrong sign (at least relative to my paper notes), but that doesn't matter because they are divided by each other.

Since the input format was not precisely specified, I made it CJam friendly. The code expects 3 points in CJam array format, where the values have to be floating point. For the given example, the expected input is:

```
[0. 0.] [3. 6.] [6. 0.]

```

Explanation:

```
q~      Get and interpret input.
:C      Store away the last point in variable C. Will be needed at the end
        to calculate the intersection point.
2$]     Repeat the first point, and wrap all points in an array.
_2ew    Generate array with all pairs of points [[A B] [B C] [C A]].
::.-    Calculate the vector difference of all point pairs [A-B B-C C-A].
        These are the vectors for each side of the triangle.
:D;;    Store the side vectors in a variable, and clear the stack.
D1=0=D2=0=*D1=1=D2=1=*+
        Calculate determinant for first unknown in 2x2 system of equations.
D0=1=D2=0=*D0=0=D2=1=*-
        Calculate main determinant of 2x2 system of equations.
/       Divide the two determinants. This gives the parameter of the
        intersection point for the line starting at C and orthogonal to A-B.
_       Copy it because we'll need it twice.
D0=1=*C0=+
        Calculate x-coordinate of intersection point.
C1=@D0=0=*-
        Calculate y-coordinate of intersection point.
S\      Put a space between the two values.

```

# Answer
> 2 votes
# R, ~~102~~ ~~70~~ 68 bytes

As an unnamed function which implements the formula in the question. The parameter for the function a vector of complex numbers (X+Yi) and it returns a complex number. I'm assuming that complex numbers are okay for input and output.

```
function(E)sum((F=tan((D=Arg(E-E[c(3,1,2)]))-D[c(2,3,1)]))*E)/sum(F)

```

**Edit** Vectorized it a lot

Expanded explanation

```
f=function(E){
    D=Arg(E-E[c(3,1,2)]); # Angles of sides
    F=tan(D-D[c(2,3,1)]); # Internal triangle angles tangents
    sum(E*F)/sum(F);      # Orthocenter coordinate return
}

```

Test

```
> f=function(E)sum((F=tan((D=Arg(E-E[c(3,1,2)]))-D[c(2,3,1)]))*E)/sum(F)
> f(c(0+0i,3+6i,6+0i))
[1] 3+1.5i

```

# Answer
> 0 votes
# Cobra - 247

```
def f(p as System.Drawing.Point[])
    a,b,c=p
    d,e,f=for q in[[b,c],[a,c],[a,b]]get if(z=q[0].x-q[1].x,(q[0].y-q[1].y)/z,0f)
    print (a.x*(g=((e-f)/(1+e*f)).abs)+b.x*(h=((d-f)/(1+d*f)).abs)+c.x*(i=((e-d)/(1+e*d)).abs))/(j=g+h+i),(a.y*g+b.y*h+c.y*i)/j

```

---
Tags: code-golf, geometry
---


title: Princely Prefix by a Program in Pattern

text:
# Question
Title: Princely Prefix by a Program in Pattern
You should write a program or function which outputs or returns as much of Chapter I of The Little Prince as it can. Your program or function has to be an M-by-N block of code containing only printable ascii characters (codepoint from 32 to 126) and newlines at the end of each row.

You can only **use at most 26 characters** of your choosing from the 96 printable ascii characters (and the newlines at the end of the rows).

**In each row and column every character has to be distinct** similar to a sudoku puzzle i.e. there can't be a letter in a row or column twice.

A correct example codeblock with `M = 4`, `N = 3` and `alphabet = {a,b,c,d,/,*}`:

```
abcd
bcd*
*/ac

```

## Code details

* You can choose the shape of your code-block (i.e. `M` and `N`).
* The block has to be filled with characters entirely i.e. every row has to have the same length.
* A trailing newline at the end of the last row is optional.
* As written above in each row and column every character has to be distinct.

## Output details

* You should output or return a prefix of Chapter I of The Little Prince without any additional output.
* If you reach a newline in the text you can represent it as any common variant (\r,\n,\r\n) but use only one of them and count it as 1 byte to the score.
* An extra trailing newline is optional.

**Your score is the length of the output text** excluding an additional newline if present. Higher score is better.

## Example answer

```
##Python3, score = 6

alphabet = `print('O\ce w)#X` (alphabet element count = 16)

    print('O\
    nce w')#X

```

You can check the validity of your code with this Python 3 (ideone) program or this CJam program (online) provided by @MartinBüttner.

# Answer
# CJam, 47

```
"Once wh
en Imwas
msix yea
r2s oldm
I "N-'m/
Sc*2s-O"
saw"N/SO
o'aS"m2
a"Oo2s-N
-S/OI*so
'yI-a"nr
wiNadI"c
cel'iaIS
/m2*Oo'x
 I-scel*
Ooel'c 2
2/'e*ON-

```

Try it online

Alphabet:  `"'*-/2INOSacdehilmnorswxy`

**Explanation:**

```
"Once wh
en Imwas
msix yea
r2s oldm
I "         push this string
N-          remove newlines
'm/Sc*      replace m's with spaces (the c is redundant)
2s-         convert 2 to string and remove 2's
O           push an empty string
"
saw"        push this string
N/          split into lines (effectively removes the newline)
S           push a space
Oo          print empty string (no-op)
'a          push 'a'
S           push a space
"m2
a"          push this string
Oo          print empty string (no-op)
2s-         convert 2 to string and remove 2's
N-          remove newline
S/          split by space (effectively removes the space)
OI*so       print an empty string repeated 18 times (no-op)
'y          push 'y'
I-          subtract 18 -> 'g'
a           wrap in array (string) -> "g"
"nr
wiNadI"     push this string
c           convert to (first) character -> 'n'
c           convert to character (no-op)
el          convert to lowercase (no-op)
'i          push 'i'
a           wrap in array (string) -> "i"
IS/         split " " into slices of length 18 -> [" "]
m           (acting as -) remove space strings from "i" (no-op)
2*          repeat "i" 2 times -> "ii"
Oo          print empty string (no-op)
'x          push 'x'
I-          subtract 18 -> 'f'
sc          convert to string and back to char (no-op)
el          convert to lowercase (no-op)
*           join "ii" with separator 'f' -> "ifi"
Oo          print empty string (no-op)
el          convert to lowercase (no-op)
'c          push 'c'
2 2/        divide 2 by 2 -> 1
'e          push 'e'
*           repeat 'e' 1 time -> "e"
O           push empty string
N-          remove newlines (no-op)

```
> 4 votes

# Answer
# Pip, score = 38

```
eyli:
"Once
when0
I was
si01x
year5
old I
0sMw1
1M 0"
X1RMh
Rnsxy
iR:'M
'aiR
:5'si

```

Alphabet:  `"'015:IMORXacdehilnorswxy`

(I sure would hate to try this in a *real* programming language.)

Explanation:

```
eyl      Statements consisting of single variables are no-ops
i:       Assign to i the following:
"Once
when0
I was
si01x
year5
old I
0sMw1
1M 0"    ...this string
X1       ...repeated once (no-op to get alignment right)
RMh      ...with all 1s and 0s removed (h is preinitialized to 100)
Rns      ...and all newlines replaced with spaces.
xy       More no-ops
iR:'M'a  Replace every M with a, assigning result back to i
iR:5's   Replace every 5 with s, assigning result back to i
i        Auto-print i

```
> 7 votes

# Answer
# Python 3, score=11

This is a really tough problem for Python, as the restrictions on repeating characters on a line or column make it nearly impossible to make more than one string literal. The various ways of joining strings together are thus fairly useless, since you can't get the strings to start with in any useful way. Here's my best attempt:

```
x=chr
print(
"Once\
 when"
,x(73)
)#prin

```

Note that there is a space at the end of the first line. The alias `x` for `chr` is necessary to avoid the same character ending up in more than one column. The comment characters at the end could be almost anything.

The alphabet is 21 printable characters, plus newline (note the space at the start):

```
 "#(),37=O\cehinprtwx

```

Output is:

> Once when I
> 4 votes

# Answer
# CJam, score = 21

```
"Once wh
en I"N-o
N;S"was
six y"N-

```

Alphabet: `-;INOSacehinoswxy`

Just to get the ball rolling; this can probably be beaten easily.
> 3 votes

# Answer
# CJam, score = 15

I've had this idea for a while now but I haven't had time to sit down and shuffle things around until I get the needed column uniqueness, so here's a baby version for now:

```
 79c32"*)+#,105468:;=>Ibef
,:=>Ibcef";7 6)#*219435+80
50I=>;9)6#*127438+ ":,bcfe
),68:>=Ibcef";20 5#*17394+
6)4*b123,97>:c"80f5=+;e# I
"9>+f=e# ),*0481362bI:;5c7

```

Alphabet (26): `" #)*+,0123456789:;=>Ibcef`

Try it online.

## Explanation

The basic idea is to make use of base encoding so we can print more than 26 types of chars. The core code is

```
79c                             e#  Push "O"
85032995607801617394 28b        e#  Push array of indices, encoding using base 28
123,97>:c" I                    e#  Push "abcdefghijklmnopqrstuvwxyz I\n"
"+
f=                              e#  Map indices to chars

```

Note that we treat the first `"O"` for `"Once"` separately because including it in our string would take too much of our alphabet. If we wanted to we could try extended our indexing string, but since no more uppercase characters happen for a while apart from `"I"` I didn't bother too much with this.

We then need to build the big number on the second line somehow. The approach I took was to repeatedly multiply by some power, then add a constant, and repeat, so in the above code `85032995607801617394` is replaced by

```
32
7 6) # * 219435 +
9) 6 # * 127438 +
20 5 # * 17394 +

```

where `)` is increment and `#` is exponentiation in CJam.

Then the rest (the most annoying part) is padding each row to fulfill the column criteria. To do this we dump chars in strings and use `;` to pop them. Unfortunately, while we would very much like to use `e#` for comments as well to make things easier, the fact that `#` is exponentiation forbids this, so this is only done on the last line.

I'm fairly certain this method can be extended up until the comma in the first sentence, but unfortunately shuffling things around to meet the column criteria is proving difficult, so I might need another method of generating the base-encoded integer.
> 2 votes

# Answer
# Python 2, score = 13 (invalid)

Python isn't the best language for this.... Upon further inspection, there are two `n`s in my first line. There is no worthwhile remedy, and I'm going to stop wasting my time with Python. I'm currently working on making a solution in another language, but will not share which one yet.

```
print"Once wh\
en I",#Oncehtp
chr(0167)#Onwt

```

Alphabet (22): `"#(),0167IOcehinprtw`

Output: `Once when I w`
> 1 votes

---
Tags: code-challenge, kolmogorov-complexity, restricted-source, source-layout
---


title: Fill a water balloon

text:
# Question
Title: Fill a water balloon
In this challenge, you must display ASCII art of a water balloon given the amount of water that the balloon is filled with:

```
|  __||__  |
| / #   #\ |
| |######| |
| |######| |
| |######| |
| |######| |
| |######| |
| \######/ |
|          |
|          |
+----------+

```

## How to draw the balloon

To display a balloon of size `n`, follow the following steps (note: whenever the division symbol (`/`) is used, it represents integer division, rounding down):

1. Draw a container consisting of ten vertical bars (`|`) on the left and right, ten dashes (`-`) on the bottom, and a plus sign (`+`) in the bottom left and bottom right corner. This makes the whole thing 12x11, and the "inside" 10x10.

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

```
2. Draw two vertical bars (the opening of the balloon) centered in the middle of the top row, with `n/2` underscores (`_`) on either side (for this example, `n` will be 5):

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

```
3. Draw one slash (`/`) and one backslash (`\`) surrounding this top row, one row below:

```
|  __||__  |
| /      \ |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

```
4. Draw `n` rows of identically-spaced vertical bars, and then one row of a pair of (still identically-spaced) backslash and slash:

```
|  __||__  |
| /      \ |
| |      | |
| |      | |
| |      | |
| |      | |
| |      | |
| \      / |
|          |
|          |
+----------+

```
5. "Fill" the balloon with water, represented by a hash sign (`#`). Start at the lowest row, and work upwards. If a row is not entirely filled, you may place the hash marks wherever you want (in the below example, they are placed randomly, but you could put them, say, all on the left side if you want).

```
|  __||__  |
| / #   #\ |
| |######| |
| |######| |
| |######| |
| |######| |
| |######| |
| \######/ |
|          |
|          |
+----------+

```

The maximum `n` is 7, and the minimum is 0.

## Input

The input will be an integer `i`, which is the amount of hash marks (water) that must be drawn.

It will never be less than 2, or greater than 100.

## Output

The output should be a balloon of size `n` containing `i` hash marks (units of water), where `n` is the lowest possible size that can hold `i` units of water. Since `i` will always be 2 or greater, `n` will always be 0 or greater.

The maximum possible size a balloon can be drawn at is `n` = 7. If a size 7 balloon cannot fit the amount of water specified, the balloon pops:

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

```

(The above should be the output for input `i` = 76. Just like the unpopped balloon, the six extra units of water on the top row may be arranged however you please.)

## Test cases

Why have *one* test case, when you can have *all* of them?

Here's an animated GIF of all inputs `i` from 2 to 100:

## Scoring

This is , so the shortest code in bytes wins.

# Answer
# Octave, 523 bytes

23 of those bytes are just for the n=100 case. Maybe someone can suggest a more efficient way...

```
n=input(0);x=zeros(11,6)+32;x(:,1)=124;x(11,:)=45;x(11,1)=43;
if n<5
w=3;h=2;a=2;
elseif n<7
w=3;h=3;a=2;
elseif n<17
w=4;h=4;a=4;
elseif n<37
w=5;h=6;a=6;
else
w=6;h=9;a=8;
end
if n<73
x(1,6)=124;x(1,9-w:5)=95;x(2,8-w)=47;x(3:1+h,8-w)=124;x(1+h,8-w)=92;x(2:1+h,9-w:6)=35;x=[x,fliplr(x)];x(2,5+w)=92;x(1+h,5+w)=47;x(2:1+floor((a*h-n)/a),9-w:4+w)=32;x(2+floor((a*h-n)/a),9-w+a-mod(a-n,a):4+w)=32;
else
x=[x,fliplr(x)];x(max(1,ceil((100-n)/10)):10,2:11)=35; if (n<100) x(ceil((100-n)/10),(2+mod(n,10)):11)=32; end
end
char(x)

```

### Test

**Input:** 21

**Output:**

```
|  __||__  |
| /      \ |
| |      | |
| |###   | |
| |######| |
| |######| |
| \######/ |
|          |
|          |
|          |
+----------+

```
> 2 votes

# Answer
# Python 2, 591 bytes

Took me some time and it probably could be golfed much more.

Hope there aren't any major errors.

```
r=[list(x)for x in ("|          |!"*10+"+----------+").split('!')]
s,t=[0]*4+[1]*2+[2]*10+[3]*4+[4]*16+[5]*6+[6]*22+[7]*8+[8]*29,[(4,2,2),(4,3,2),(3,4,4),(3,5,4),(2,6,6),(2,7,6),(1,8,8),(1,9,8),(0,9,10)]
a,b,c,d,e='|','/','\\','_','#'
def p(x,y,w):r[y][x]=w
def q(l):
 h,j,u=l
 p(5,0,a);p(6,0,a)
 for o in range(4-h):p(h+o+1,0,d);p(h+u-o,0,d)
 p(h,1,b);p(h+u+1,1,c)
 for o in range(j-2):p(h,o+2,a);p(h+u+1,o+2,a)
 p(h,j,c);p(h+u+1,j,b)
def w(i,l):
 h,j,u=l
 for o in range(i):x,y=o%u,o/u;p(h+x+1,j-y,e)
def f(i):
 n=s[i]
 l=t[n]
 if n<8:q(l)
 w(i,l)
 print "\n".join(["".join(x)for x in r])

```

Example run:

```
f(34)

```

gives:

```
|  __||__  |
| /####  \ |
| |######| |
| |######| |
| |######| |
| |######| |
| \######/ |
|          |
|          |
|          |
+----------+

```
> 2 votes

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


title: How many characters per character?

text:
# Question
Title: How many characters per character?
At http://shakespeare.mit.edu/ you can find the full text of each of Shakespeare's plays on one page (e.g. Hamlet).

Write a script that takes in the url of a play from stdin, such as http://shakespeare.mit.edu/hamlet/full.html, and outputs the number of text characters each play character spoke to stdout, sorted according to who spoke the most.

The play/scene/act titles obviously do not count as dialogue, nor do the character names. *Italicized text* and \[square bracketed text\] are not actual dialogue, they should not be counted. Spaces and other punctuation within dialogue should be counted.

(The format for the plays looks very consistent though I have not looked at them all. Tell me if I've overlooked anything. Your script does not have to work for the poems.)

# Example

Here is a simulated section from Much Ado About Nothing to show what I expect for output:

> # More Ado About Nothing
>
> ## Scene 0.
>
> **Messenger**
>
> I will.
>
> **BEATRICE**
>
> Do.
>
> **LEONATO**
>
> You will never.
>
> **BEATRICE**
>
> No.

Expected output:

```
LEONATO 15
Messenger 7
BEATRICE 6

```

# Scoring

This is code golf. The smallest program in bytes will win.

# Answer
> 4 votes
# PHP (240 characters)

Divides the html into strings (using as a delimeter), then runs a couple of regular expressions to extract name and words spoken. Saves length of words spoken into array. Golfed:

```
<?@$p=preg_match_all;foreach(explode('/bl',implode(file(trim(fgets(STDIN)))))as$c)if($p('/=s.*?b>(.*?):?</',$c,$m)){$p('/=\d.*?>(.*?)</',$c,$o);foreach($m[1]as$n)@$q[$n]+=strlen(implode($o[1]));}arsort($q);foreach($q as$n=>$c)echo"$n $c\n";

```

Ungolfed:

```
<?php
$html = implode(file(trim(fgets(STDIN))));
$arr = explode('/bl',$html);
foreach($arr as $chunk){
    if(preg_match_all('/=s.*?b>(.*?):?</',$chunk,$matches)){
        $name = $matches[1];
        preg_match_all('/=\d.*?>(.*?)</',$chunk,$matches);
        foreach($name as $n)
            @$names[$n] += strlen(implode($matches[1]));
    }
}
arsort($names);
foreach($names as $name=>$count)
    echo "$name $count\n";

```

Note: This considers 'All' to be a separate character.

Example:

```
$php shakespeare.php <<< "http://shakespeare.mit.edu/hamlet/full.html"
HAMLET 60063
KING CLAUDIUS 21461
LORD POLONIUS 13877
HORATIO 10605
LAERTES 7519
OPHELIA 5916
QUEEN GERTRUDE 5554
First Clown 3701
ROSENCRANTZ 3635
Ghost 3619
MARCELLUS 2350
First Player 1980
OSRIC 1943
Player King 1849
GUILDENSTERN 1747
Player Queen 1220
BERNARDO 1153
Gentleman 978
PRINCE FORTINBRAS 971
VOLTIMAND 896
Second Clown 511
First Priest 499
Captain 400
Lord 338
REYNALDO 330
FRANCISCO 287
LUCIANUS 272
First Ambassador 230
First Sailor 187
Messenger 185
Prologue 94
All 94
Danes 75
Servant 49
CORNELIUS 45

```

# Answer
> 3 votes
# Rebol - ~~556~~ 527

```
t: complement charset"<"d: charset"0123456789."m: map[]parse to-string read to-url input[any[(s: 0 a: copy[])some["<A NAME=speech"some d"><b>"copy n some t</b></a>(append a trim/with n":")some newline]<blockquote>newline any["<A NAME="some d">"copy q some t</a><br>newline(while[f: find q"["][q: remove/part f next find f"]"]s: s + length? trim head q)|<p><i>some t</i></p>newline][</blockquote>|</body>](foreach n a[m/:n: either none? m/:n[s][s + m/:n]])| skip]]foreach[x y]sort/reverse/skip/compare to-block m 2 2[print[x y]]

```

This could probably be golfed further however its unlikely to get below the answer(s) already provided :(

### Ungolfed:

```
t: complement charset "<"
d: charset "0123456789."
m: map []

parse to-string read to-url input [
    any [
        (s: 0 a: copy [])

        some [
            "<A NAME=speech" some d "><b>" copy n some t </b></a>
            (append a trim/with n ":")
            some newline
        ]

        <blockquote> newline
        any [
            "<A NAME=" some d ">" copy q some t </a><br> newline (
                while [f: find q "["] [
                    q: remove/part f next find f "]"
                ]
                s: s + length? trim head q
            )
            | <p><i> some t </i></p> newline
        ]
        [</blockquote> | </body>]
        (foreach n a [m/:n: either none? m/:n [s] [s + m/:n]])

        | skip
    ]
]

foreach [x y] sort/reverse/skip/compare to-block m 2 2 [print [x y]]

```

This program removes \[square bracketed text\] and also trims surrounding whitespace from the dialogue. Without this the output is identical to *es1024* answer.

### Example:

```
$ rebol -q shakespeare.reb <<< "http://shakespeare.mit.edu/hamlet/full.html"
HAMLET 59796
KING CLAUDIUS 21343
LORD POLONIUS 13685
HORATIO 10495
LAERTES 7402
OPHELIA 5856
QUEEN GERTRUDE 5464
First Clown 3687
ROSENCRANTZ 3585
Ghost 3556
MARCELLUS 2259
First Player 1980
OSRIC 1925
Player King 1843
GUILDENSTERN 1719
Player Queen 1211
BERNARDO 1135
Gentleman 978
PRINCE FORTINBRAS 953
VOLTIMAND 896
Second Clown 511
First Priest 499
Captain 400
Lord 338
REYNALDO 312
FRANCISCO 287
LUCIANUS 269
First Ambassador 230
First Sailor 187
Messenger 185
Prologue 89
All 76
Danes 51
Servant 49
CORNELIUS 45

```

# Answer
> 0 votes
# Common Lisp - 528

```
(use-package :plump)(lambda c(u &aux(h (make-hash-table))n r p)(traverse(parse(drakma:http-request u))(lambda(x &aux y)(case p(0(when(and n(not(ppcre:scan"speech"(attribute x"NAME"))))(setf r t y(#1=ppcre:regex-replace-all"aside: "(#1#"^(\\[[^]]*\\] |\\s*)"(text x)"")""))(dolist(w n)(incf(gethash w h 0)(length y)))))(1(if r(setf n()r()))(push(intern(text(aref(children x)0)))n)))):test(lambda(x)(and(element-p x)(setf p(position(tag-name x)'("A""b"):test #'string=)))))(format t"~{~a ~a~^~%~}"(alexandria:hash-table-plist h)))

```

# Explanation

This is a slightly modifed version which adds printing informations (see paste).

```
(defun c (u &aux
                 (h (make-hash-table)) ;; hash-table
                 n ;; last seen character name
                 r p
                 )
      (traverse                 ;; traverse the DOM generated by ...
       (parse                   ;; ... parsing the text string
        (drakma:http-request u) ;; ... resulting from http-request to link U
        )

       ;; call the function held in variable f for each traversed element
       (lambda (x &aux y)
         (case p
           (0 ;a
            (when(and n(not(alexandria:starts-with-subseq"speech"(attribute x "NAME"))))
              (setf r t)
              (setf y(#1=ppcre:regex-replace-all"aside: "(#1#"^(\\[[^]]*\\] |\\s*)"(text x)"")""))
              (format t "~A ~S~%" n y) ;; debugging
              (dolist(w n)
                (incf
                    (gethash w h 0) ;; get values in hash, with default value 0
                    (length y)))) ;; length of text
            )
           (1 ;b
            (if r(setf n()r()))
            (push (intern (text (aref (children x)0)))n))))

       ;; but only for elements that satisfy the test predicate
       :test
       (lambda(x)
         (and (element-p x) ;; must be an element node
              (setf p(position(tag-name x)'("A""b"):test #'string=)) ;; either <a> or <b>; save result of "position" in p
              )))

        ;; finally, iterate over the elements of the hash table, as a
        ;; plist, i.e. a list of alternating key values (k1 v1 k2 v2 ...),
        ;; and print them as requested. ~{ ~} is an iteration control format.
  (format t "~&~%~%TOTAL:~%~%~{~a ~a~^~%~}" (alexandria:hash-table-plist h)))

```

# Notes

* I remove bracketed text as well as the "aside: " occurence that is not present in brackets (I also trim whitespace characters). Here is a trace of execution with the text being matched and the total for each character, for Hamlet.
* As other answers, **All** is assumed to be a character. It could be tempting to add the value of all to all other characters, but this would be incorrect since "All" refers to the characters actually present on stage, which requires to keep a context of who is present (tracking "exit" "exeunt" and "enter" indications). This is not done.

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


title: Print n-z characters of Unicode table

text:
# Question
Title: Print n-z characters of Unicode table
The challenge is to write a program which outputs all characters of the Unicode table from n to z range.

For code "0000" is the first in order and you must skip all blank Unicode combinations. For example, let n = 134 and z = 300, you must save or print all unicode characters between 0134 and 0300.

The output of the program does not HAVE to output them, for example using std::cout can be used but if you have an array with all the saved characters then that still qualifies.(You don't have to print them out)

The shortest program in bytes wins.

# Answer
# Pyth - 16 bytes

Maps `C`har-of over the range, and detects unprintables by if the string `"\x"` is inside its repr because that is how python represents unprintables like `\x00`.

```
f!}"\\x"`TCMrQvw

```

Try it here online.
> 9 votes

---
Tags: code-golf, unicode
---


# Question
Title: National Scheduling Conflict Championships
(I meant to post this while 1542: Scheduling Conflict was still the current xkcd, but I had a scheduling conflict.)

## Input

The input will be a list of `3n` elements, which represent `n` events. The first element in each group of 3 will be the name of an event; the second and third, the start and end time respectively. For example:

```
foo 12 34 bar 56 78

```

represents an event `foo` that starts at "time 12" (times are represented simply by integers; you can think of them as minutes past midnight) and ends at 34, and a second event `bar` that starts at 56 and ends at 78.

The names of events will always consist of only alphanumeric characters, and the times will always be integers ≥ 0 and \< 1440. The end time will always be at least 1 greater than the start time. They are not guaranteed to be sorted in any way.

If you would like, you may take this as a single space-separated string; otherwise it should be taken as an array, list, vector, or your language's equivalent.

## Output

The output should be a space-separated list of event names. The rules for which event names to output are as follows:

* None of the events that you output may conflict with each other. For example, with the input `a 0 10 b 5 15`, you may not output both `a` and `b` because the times conflict (that is, partially overlap). If an event ends exactly as another one starts, you may include both.
* You may not output the event called `NSCC` ("National Scheduling Conflict Competition"), of which there will *always* be exactly one of in the input. You also **must** output at least one event that conflicts (partially overlaps) with `NSCC` (and there will always be at least one of those as well).
* You must output as many events as possible while following the above two rules. (This is so that you look as busy as possible, so that missing the NSCC seems more credible.)

This may also be output as either a single space-separated string or an array, list, vector, etc.

There can be more than one possible output.

## Test cases

Note that the outputs listed are only examples. Your code may output something different, as long as it still follows the three rules above (notably, this means there must be the same *amount* of events as the example).

In: `UnderwaterBasketWeavingConvention 50 800 NSCC 500 550`
Out: `UnderwaterBasketWeavingConvention`

In: `SconeEating 0 50 RegexSubbing 45 110 CodeGolfing 95 105 NSCC 100 200`
Out: `SconeEating CodeGolfing`

In: `VelociraptorHunting 0 300 NerdSniping 200 500 SEChatting 400 700 DoorknobTurning 650 750 NSCC 725 775`
Out: `NerdSniping DoorknobTurning`

In: `NSCC 110 115 A 100 120 B 120 140 C 105 135 D 100 105 E 135 500`
Out: `C D E`

In: `A 800 900 NSCC 700 1000 B 650 750 C 950 1050 D 655 660 E 660 665 F 1030 1040 G 1040 1060`
Out: `A D E F G`

In: `A 10 11 B 11 12 C 12 13 D 13 14 NSCC 15 1090 E 10 16`
Out: `E`

Feel free to add more test cases in an edit if there are edge-cases that I missed.

## Rules

* Your code must complete within 30 seconds for all of the provided test cases (this is more of a sanity check, as it should probably complete much faster for all the test cases combined) on a reasonable personal machine.
* This is , so the shortest code in bytes wins.

# Answer
# Pyth, 45 bytes

```
AGH.gqhk"NSCC"m,hdrFtdcQ3hMef&.{KseMT@KehHtyG

```

This one was quite tough to golf. Found quite a few 45 byte solutions, this one is probably the most exotic one, since it uses `A` (pair-assign) and `.g` (group-by).

Try it online: Demonstration or Test harness

### Explanation

```
                            implicit: Q = input list
                      cQ3   split Q into triples
              m             map each triple d to:
               ,              the pair containing
                hd              - d[0] (name)
                  rFtd          - range from start-time to end-time
   .g                       group these tuples k by:
     qhk"NSCC"                k[0] == "NSCC"
AGH                         pair assign to G,H. This assigns all
                            tuples != NSCC to G, and the NSCC one to H

                  yG        generate all subsets of G
                 t          remove the first one (the empty subset)
   f                        filter for subsets T, which satisfy:
         eMT                  get the last item (the range) for all tuples in T
        s                     and combine them (sum)
       K                      assign to K
     .{                       check for uniqueness of K (no overlapping times)
    &                         and
            @KehH             check the intersection of K and H[0][1]
  e                         take the last element (most events)
hM                          get the first item (name) for each event
                            and implicitly print this list

```
> 9 votes

# Answer
# SWI-Prolog, ~~537~~ ~~524~~ ~~516~~ ~~502~~ ~~447~~ 436 bytes

```
z(A:B:C,[D:E:F|G]):-(A=D;B>=F;E>=C),(G=[];z(A:B:C,G)).
u([A|B],C):-z(A,C),(B=[];u(B,C)).
y([A,B,C|D])-->[A:B:C],(y(D);{_=_}).
d-->[A:_],{write(A),tab(1)},d;{_=_}.
l([H|T],R):-T=[],R=H;length(H,N),l(T,X),length(X,M),(N>M,R=H;R=X).
v([],_,R,R).
v([A|T],Z,B,R):-u(A,A),\+z(Z,A),v(T,Z,[A|B],R);v(T,Z,B,R).
s([E|T],[F|N]):-E=F,(N=[];s(T,N));s(T,[F|N]).
x(A):-y(A,D,[]),K="NSCC":_,select(K,D,E),setof(L,s(E,L),B),v(B,K,[],R),l(R,S),d(S,[]),!.

```

Brief explanation of what each predicate does:

* `z(A,B)` checks that an event A doesn't conflict with any event of a list of events B
* `u(A,B)` checks that every event of a list A does not conflict with any event of a list B (used to check that there are no conflicts in list A by calling `u(A,A)`)
* `y(A,B,C)` splits a List into a list of triplets (to transform inputs into a list of events)
* `d(A)` prints the names of events in a list A
* `l(A,R)` evaluates the longest list of events R contained in the list of lists A
* `v(A,NSCC,C,R)` returns a list R containing every list of events in A that have no internal conflict and that conflict with the event NSCC
* `s(A,B)` true if B is a subset of A
* `x(A)` main predicate, A is the input.

**Test cases**: execute `test.` in the interpreter after loading the code above with the following added after it:

```
test:-
    x(["UnderwaterBasketWeavingConvention",50,800,"NSCC",500,550]),
    nl,
    x(["SconeEating",0,50,"RegexSubbing",45,110,"CodeGolfing",95,105,"NSCC",100,200]),
    nl,
    x(["VelociraptorHunting",0,300,"NerdSniping",200,500,"SEChatting",400,700,"DoorknobTurning",650,750,"NSCC",725,775]),
    nl,
    x(["NSCC",110,115,"A",100,120,"B",120,140,"C",105,135,"D",100,105,"E",135,500]),
    nl,
    x(["A",800,900,"NSCC",700,1000,"B",650,750,"C",950,1050,"D",655,660,"E",660,665,"F",1030,1040,"G",1040,1060]),
    nl,
    x(["A",10,11,"B",11,12,"C",12,13,"D",13,14,"NSCC",15,1090,"E",10,16]).

```

This took me way more time than I thought it would. This can probably be golfed significantly more. Also you could probably use the various constraint programming libraries that exist to get shorter solutions.

**Edit:** Thanks to @Oliphaunt for the idea of using `A:B:C` instead of `[A,B,C]` for triplets. Saves 14 bytes.

**Edit2:** Thanks again to @Oliphaunt for pointing out that the predicate \`\`t/3\`was useless. Saves 55 bytes

**Edit3:** Gained 11 bytes using definitive clause grammar on predicates `y` and `d`.
> 13 votes

# Answer
# JavaScript (*ES6*), 228

Second try, I hope this one works.

My target is the longest sequence of events that has a timing conflict, but no timing conflict when the event NSCC is removed. This modified sequence with NSCC removed is the output requested.

I use a Breadth First Search examining a queue of candidate solutions, starting with longest (the first is the initial list). From a candidate solution of *n* events I build and enqueue *n* more candidate solutions, removing one of the events and keeping the others.

A candidate solution is valid if there is a timing conflict 'as is', but when the NSCC event is filtered out there is no conflict. I use a subfunction K to check for conflicts.

Probably could be golfed a little more...

Test running the snippet below (being EcmaScript 6, FireFox only)

```
F=l=>(K=>{
  l.map(v=>l.push(l.splice(0,3)));// I'm particularly proud of this trick for grouping in triplets (in pith it's "cQ3")
  for(S=[l.sort((a,b)=>a[1]-b[1])];!K(l=S.shift())|K(m=l.filter(x=>x[0]!='NSCC'));)
    l.map((v,i)=>(S.push(n=[...l]),n.splice(i,1)));
})(l=>l.some(x=>[p>+x[1],p=+x[2]][0],p=0))||m.map(x=>x[0])

// Less golfed and ES5

function Find(l) {
  var n,m;
  var Check = function(l) {
    // check timing conflict comparing start time and end time of previous event (events must be sorted)
    var p = 0 // previous event end time, init to 0
    return l.some( function(x) {
      var err = p > +x[1]; // unary plus convert string to number
      p = +x[2]; // update end time
      return err;
    });
  };
  // group initial array in triplets
  // forEach repeats for the initial number of elements in l, even if l becomes shorter
  // so it loops more times than necesary, but it works anymay
  l.forEach(function() {
    l.push(l.splice(0,3)); // remove first 3 elements and add to back as a triple
  })
  l.sort(function(a,b) { return a[1]-b[1]} ); // sort by start time
  var S=[l]; // S is the main queue, start with complete list

  while (l = S.shift(), // current list
         m = l.filter( function(x) { return x[0]!='NSCC'} ), // current list with NSCC removed
         !Check(l)|Check(m)) // loop while list ha no errors or filtered list do have errors
  {
    // build new candidate to check
    l.forEach ( function(v,i) {
      n = l.slice(); // make a copy of l
      n.splice(i,1); // remove ith element
      S.push(n); // put in S
    });
  }
  // when exiting while, m has the list with NSCC removed
  return m.map( function(x) { return x[0]; }); // keep the event name only
}

// Test

out=(...x)=>O.innerHTML += x + '\n';

test=[
  ['UnderwaterBasketWeavingConvention 50 800 NSCC 500 550','UnderwaterBasketWeavingConvention']
, ['SconeEating 0 50 RegexSubbing 45 110 CodeGolfing  95 105 NSCC 100 200','SconeEating CodeGolfing']
, ['VelociraptorHunting 0 300 NerdSniping 200 500 SEChatting 400 700 DoorknobTurning 650 750 NSCC 725 775'
  ,'NerdSniping DoorknobTurning']
, ['NSCC 110 115 A 100 120 B 120 140 C 105 135 D 100 105 E 135 500','C D E']
, ['A 800 900 NSCC 700 1000 B 650 750 C 950 1050 D 655 660 E 660 665 F 1030 1040 G 1040 1060','A D E F G']
, ['A 10 11 B 11 12 C 12 13 D 13 14 NSCC 15 1090 E 10 16','E']
]

test.forEach(x=>{
  var l=x[0].split(/\s+/), r=F(l).sort().join(' '), e=x[1].split(/\s+/).sort().join(' ');
  out('Test ' + (r==e ? 'OK':'FAIL')+'\nInput:    '+x[0]+'\nResult:   '+r+'\nExpected: '+e)
} )
```

```
<pre id=O></pre>
```
> 6 votes

# Answer
# Java, 828 bytes

There's probably a more concise Java implementation out there, but here's my stab:

```
String s(String e){String[] a=e.split(" ");String m="";String[] c=g(a.length/3);int l=0;for(int i=0;i<a.length;i+=3)if(a[i].equals("NSCC"))l=i/3;for(String p:c)if(p.indexOf(l+"")==-1&&!h(p,a)&&h(p+l,a)&&p.length()>m.length())m=p;String r="";for(int i=0;i<m.length();i++)r+=a[3*(m.charAt(i)-48)]+((i==m.length()-1)?"":" ");return r;}boolean h(String c, String[] e){for(int i=0;i<c.length()-1;i++){int p=c.charAt(i)-48;for(int j=i+1;j<c.length();j++){int q=c.charAt(j)-48;if((Integer.parseInt(e[3*p+1])-Integer.parseInt(e[3*q+2]))*((Integer.parseInt(e[3*p+2])-Integer.parseInt(e[3*q+1])))<0)return true;}}return false;}String[] g(int n){if(n>1){String[] result=new String[(int)Math.pow(2,n)];String[] l=g(n-1);for(int i=0;i<l.length;i++){result[2*i]=l[i];result[2*i+1]=l[i]+(n-1);}return result;}else return new String[]{"","0"};}

```
> 1 votes

# Answer
# Python, 373 characters

```
import itertools as j
a=zip(*[iter(input())]*3)
f,g,r=[],0,"NSCC"
p=f
for q in a:
 p=(p,q)[q[0]==r]
for h in range(1,len(a)+1):
 for i in j.combinations(a,h):
  s,i,l,m=0,sorted(i,key=lambda k:int(k[1])),-1,len(i)
  for n in i:
   s=(s,1)[p[1]<n[2]or p[2]<n[1]]
   if r==n[0]or n[1]<l:
    m=-1
    break
   else:
    l=n[2]
  if s*m>g:
   g,f=m,i
for o in f:
 print o[0]

```

Creates all possible combinations and checks each one.

### Test

**Input:** `["NSCC",110,115,"A",100,120,"B",120,140,"C",105,135,"D",100,105,"E",135,500]`

**Output:**

```
D
C
E

```
> 0 votes

---
Tags: code-golf
---


title: The very weird word counter

text:
# Question
Title: The very weird word counter
INPUT: Any string consisting exclusively of lowercase letters via function argument, command line argument, STDIN, or similar.

OUTPUT: Print or return a number that will represent the sum of the distances of the letters according to the following metric:

You take the first and second letter and count the distance between them. The distance is defined by the QWERTY keyboard layout, where every adjacent letter in the same row has distance 1 and every adjacent letter in the same column has distance 2. To measure the distance between letters that aren't adjacent, you take the shortest path between the two.

Examples:

```
q->w is 1 distance apart
q->e is 2 distance
q->a is 2 distance
q->s is 3 distance (q->a->s or q->w->s)
q->m is 10 distance

```

Then you take the second and third letter, then the third and fourth, etc., until you reach the end of the input. The output is the sum of all those distances.

Example input and output:

```
INPUT: qwer
OUTPUT: 3

INPUT: qsx
OUTPUT: 5

INPUT: qmq
OUTPUT: 20

INPUT: tttt
OUTPUT: 0

```

Here is an image showing which letters are in the same column:

This is code golf, so the shortest code in bytes wins!

# Answer
# CJam, 50 bytes

```
r{i",ÙZ°^ªýx´|"257b27b=A+Ab}%2ew::.-::z2fb:+

```

Note that the code contains unprintable characters.

Try it online in the CJam interpreter. If the permalink doesn't work, copy the code from this paste.

### Background

We start assigning positions **0** to **9** to the letters on the top row, **10** to **18** to the letters on the home row and **20** to **26** to the letters on the bottom row.

The positions of all 26 letters, in alphabetical order, are

```
[10 24 22 12 2 13 14 15 7 16 17 18 26 25 8 9 0 3 11 4 6 23 1 21 5 20]

```

This is an array of length 26. Since arrays wrap around in CJam, and the code point of the letter **h** is **104 = 4 × 26**, we rotate the array 7 units to the left, so that each letter's position can be accessed by its code point.

```
[15 7 16 17 18 26 25 8 9 0 3 11 4 6 23 1 21 5 20 10 24 22 12 2 13 14]

```

Now we encode this array by considering its elements digits of a base 27 number and convert the resulting integer to base 257.

```
[6 153 44 8 217 90 176 156 94 24 170 253 147 120 180 124]

```

By replacing each integers by the corresponding Unicode character, we obtain the string from the source code.

### How it works

```
r              e# Read a whitespace separated token from STDIN.
{              e# For each character:
  i            e#   Push its code point.
  ",ÙZ°^ªýx´|" e#   Push that string.
  257b27b      e#   Convert from base 257 to base 27.
  A+Ab         e#   Add 10 and convert to base 10.
               e#   Examples: 7 -> [1 7], 24 -> [3 4]
}%             e#
2ew            e# Push all overlapping slices of length 2.
::.-           e# Subtract the corresponding components of the pairs in each slice.
::z            e# Apply absolute value to the results.
2fb            e# Convert each to integer (base 2).
               e# Example: [2 5] -> 2 × 2 + 5 = 9
:+             e# Add the distances.

```
> 2 votes

# Answer
# Python 2, ~~220~~ ... ~~124~~ 119 Bytes

*Huge thanks to Sp3000 for saving a **lot** of bytes.*

```
f='qwertyuiopasdfghjkl zxcvbnm'.find
g=lambda i:sum(abs(f(x)%10-f(y)%10)+2*abs(f(x)/10-f(y)/10)for x,y in zip(i,i[1:]))

```

Usage:

```
g("tttt") -> 0

```

Check it out here.

Slightly ungolfed + explanation:

```
f='qwertyuiopasdfghjkl zxcvbnm'.find  # Defining keyboard rows and aliasing find
g=lambda i:                           # Defining a function g which takes variable i
    sum(                              # Sum of
        abs(f(x)%10-f(y)%10)          # horizontal distance, and
        + 2*abs(f(x)/10-f(y)/10)      # vertical distance,
        for x,y in zip(i,i[1:]))      # for each pair in the zipped list

# Example of zipping for those unaware:
# Let i = asksis, therefore i[1:] = sksis, and zip would make
# the list of pairs [(a,s),(s,k),(k,s),(s,i),(i,s)].

```
> 7 votes

# Answer
# Java, 266 bytes

```
int c(String q){String[]r={"qwertyuiop","asdfghjkl","zxcvbnm"};int v=0,l=q.length();int[][]p=new int[l][2];for(int i=0;i<l;i++){while(p[i][0]<1)p[i][0]=r[p[i][1]++].indexOf(q.charAt(i))+1;v+=i<1?0:Math.abs(p[i][0]-p[i-1][0])+2*Math.abs(p[i][1]-p[i-1][1]);}return v;}

```

Ungolfed version:

```
int c(String q) {
    String[] r = {
        "qwertyuiop",
        "asdfghjkl",
        "zxcvbnm"
    };
    int v = 0, l = q.length(); // v=return value, l = a shorter way to refer to input length
    int[][] p = new int[l][2]; // an array containing two values for each
                               // letter in the input: first its position
                               // within the row, then its row number (both
                               // 1 indexed for golfy reasons)
    for(int i = 0; i<l; i++) { // loops through each letter of the input
        while (p[i][0] < 1) // this loop populates both values of p[i]
            p[i][0] = r[p[i][1]++].indexOf(q.charAt(i))+1;
        v += (i<1) ? 0 : Math.abs(p[i][0]-p[i-1][0])+2*Math.abs(p[i][1]-p[i-1][1]); // adds onto return value
    }
    return v;
}

```
> 5 votes

# Answer
# SWI-prolog, 162 bytes

```
a(A):-a(A,0).
a([A,B|C],T):-Z=`qwertyuiopasdfghjkl0zxcvbnm`,nth0(X,Z,A),nth0(Y,Z,B),R is T+(2*abs(Y//10-X//10)+abs(Y mod 10-X mod 10)),(C=[],print(R);a([B|C],R)).

```

Example: `a(`qmq`)` outputs `20` (And `true` after it but there's nothing I can do about that).

**Edit:** had to use 3 more bytes. My original program passed the test cases given but was actually incorrect (absolute values were misplaced/missing)

Note: if you want to use it on say Ideone, you have to replace all backquotes ``` to double quotes `"`. Backquotes in my case (which is the current standard in SWI-Prolog) represent codes list for strings, and double-quotes character strings, but this is different in older versions of SWI-Prolog.
> 3 votes

---
Tags: code-golf, keyboard
---


title: Tokenize a String

text:
# Question
Title: Tokenize a String
Write a program or function that takes in a string through STDIN or function parameters, tokenizes it by parenthesis, and outputs the tokens on different lines. If the string contains a parentheses error, the program/function must output a falsey value or error message.

### Examples:

**Input:** `abc(def)ghi`

**Output:**

```
abc   ghi
   def

```

**Input:** `abc(def(ghi))jklm(n)op((q))rs`

**Output:**

```
abc      jklm op rs
   def       n
      ghi       q

```

**Input:** `blah(blah)(blah`

**Output:**

```
Error

```

### Notes:

* The falsey value or error message must be generated by program, and the program must terminate successfully. A built in error message due to a crash does not count.
* This is code golf. I will accept the shortest answer in bytes one month from today (July 30th).
* No standard loopholes.

# Answer
# Cobra - 238

```
def f(s='')
    x,y,l=0,0,for n in (r=s.count('('))get' '.repeat(s.length-2*r)
    try
        for c in s,branch c
            on c'(',y+=1
            on c')',y-=1
            else,l[y]=l[y][:x]+'[c]'+l[y][x+=1:]
        assert y==0
    catch
        print'Error'
    success,print l.join('\n')

```
> 1 votes

---
Tags: code-golf
---


title: Testing if a number is a square

text:
# Question
Title: Testing if a number is a square
Write a *GOLF* assembly program that given a 64-bit unsigned integer in register `n` puts a non-zero value into register `s` if `n` is a square, otherwise `0` into `s`.

**Your *GOLF* binary (after assembling) must fit in 4096 bytes.**

---

Your program will be scored using the following Python3 program (which must be put inside the *GOLF* directory):

```
import random, sys, assemble, golf, decimal

def is_square(n):
    nd = decimal.Decimal(n)
    with decimal.localcontext() as ctx:
        ctx.prec = n.bit_length() + 1
        i = int(nd.sqrt())
        return i*i == n

with open(sys.argv[1]) as in_file:
    binary, debug = assemble.assemble(in_file)

score = 0
random.seed(0)
for i in range(1000):
    cpu = golf.GolfCPU(binary)

    if random.randrange(16) == 0: n = random.randrange(2**32)**2
    else:                         n = random.randrange(2**64)

    cpu.regs["n"] = n
    cpu.run()
    if bool(cpu.regs["s"]) != is_square(n):
        raise RuntimeError("Incorrect result for: {}".format(n))
    score += cpu.cycle_count
    print("Score so far ({}/1000): {}".format(i+1, score))

print("Score: ", score)

```

Make sure to update *GOLF* to the latest version with `git pull`. Run the score program using `python3 score.py your_source.golf`.

It uses a static seed to generate a set of numbers of which roughly 1/16 is square. Optimization towards this set of numbers is against the spirit of the question, I may change the seed at any point. Your program must work for any non-negative 64-bit input number, not just these.

### Lowest score wins.

---

Because *GOLF* is very new I'll include some pointers here. You should read the *GOLF* specification with all instructions and cycle costs. In the Github repository example programs can be found.

For manual testing, compile your program to a binary by running `python3 assemble.py your_source.golf`. Then run your program using `python3 golf.py -p s your_source.bin n=42`, this should start the program with `n` set to 42, and prints register `s` and the cycle count after exiting. See all the values of the register contents at program exit with the `-d` flag - use `--help` to see all flags.

# Answer
# Score: 22120 (3414 bytes)

My solution uses a 3kB lookup table to seed a Newton's method solver that runs for zero to three iterations depending on the result's size.

```
    lookup_table = bytes(int((16*n)**0.5) for n in range(2**10, 2**12))

    # use orlp's mod-64 trick
    and b, n, 0b111111
    shl v, 0xc840c04048404040, b
    le q, v, 0
    jz not_square, q
    jz is_square, n

    # x will be a shifted copy of n used to index the lookup table.
    # We want it shifted (by a multiple of two) so that the two most
    # significant bits are not both zero and no overflow occurs.
    # The size of n in bit *pairs* (minus 8) is stored in b.
    mov b, 24
    mov x, n
    and c, x, 0xFFFFFFFF00000000
    jnz skip32, c
    shl x, x, 32
    sub b, b, 16
skip32:
    and c, x, 0xFFFF000000000000
    jnz skip16, c
    shl x, x, 16
    sub b, b, 8
skip16:
    and c, x, 0xFF00000000000000
    jnz skip8, c
    shl x, x, 8
    sub b, b, 4
skip8:
    and c, x, 0xF000000000000000
    jnz skip4, c
    shl x, x, 4
    sub b, b, 2
skip4:
    and c, x, 0xC000000000000000
    jnz skip2, c
    shl x, x, 2
    sub b, b, 1
skip2:

    # now we shift x so it's only 12 bits long (the size of our lookup table)
    shr x, x, 52

    # and we store the lookup table value in x
    add x, x, data(lookup_table)
    sub x, x, 2**10
    lbu x, x

    # now we shift x back to the proper size
    shl x, x, b

    # x is now an intial estimate for Newton's method.
    # Since our lookup table is 12 bits, x has at least 6 bits of accuracy
    # So if b <= -2, we're done; else do an iteration of newton
    leq c, b, -2
    jnz end_newton, c
    divu q, r, n, x
    add x, x, q
    shr x, x, 1

    # We now have 12 bits of accuracy; compare b <= 4
    leq c, b, 4
    jnz end_newton, c
    divu q, r, n, x
    add x, x, q
    shr x, x, 1

    # 24 bits, b <= 16
    leq c, b, 16
    jnz end_newton, c
    divu q, r, n, x
    add x, x, q
    shr x, x, 1

    # 48 bits, we're done!

end_newton:

    # x is the (integer) square root of n: test x*x == n
    mulu x, h, x, x
    cmp s, n, x
    halt 0

is_square:
    mov s, 1

not_square:
    halt 0

```
> 1 votes

# Answer
# Score: 27462

About time I'd compete in a *GOLF* challenge :D

```
    # First we look at the last 6 bits of the number. These bits must be
    # one of the following:
    #
    #     0x00, 0x01, 0x04, 0x09, 0x10, 0x11,
    #     0x19, 0x21, 0x24, 0x29, 0x31, 0x39
    #
    # That's 12/64, or a ~80% reduction in composites!
    #
    # Conveniently, a 64 bit number can hold 2**6 binary values. So we can
    # use a single integer as a lookup table, by shifting. After shifting
    # we check if the top bit is set by doing a signed comparison to 0.

    and b, n, 0b111111
    shl v, 0xc840c04048404040, b
    le q, v, 0
    jz no, q
    jz yes, n

    # Hacker's Delight algorithm - Newton-Raphson.
    mov c, 1
    sub x, n, 1
    geu q, x, 2**32-1
    jz skip32, q
    add c, c, 16
    shr x, x, 32
skip32:
    geu q, x, 2**16-1
    jz skip16, q
    add c, c, 8
    shr x, x, 16
skip16:
    geu q, x, 2**8-1
    jz skip8, q
    add c, c, 4
    shr x, x, 8
skip8:
    geu q, x, 2**4-1
    jz skip4, q
    add c, c, 2
    shr x, x, 4
skip4:
    geu q, x, 2**2-1
    add c, c, q

    shl g, 1, c
    shr t, n, c
    add t, t, g
    shr h, t, 1

    leu q, h, g
    jz newton_loop_done, q
newton_loop:
    mov g, h
    divu t, r, n, g
    add t, t, g
    shr h, t, 1
    leu q, h, g
    jnz newton_loop, q
newton_loop_done:

    mulu u, h, g, g
    cmp s, u, n
    halt 0
yes:
    mov s, 1
no:
    halt 0

```
> 10 votes

# Answer
## Score: 161558 ~~227038~~ ~~259038~~ ~~260038~~ ~~263068~~

I took the fastest integer square root algorithm I could find and return whether its remainder is zero.

```
# based on http://www.cc.utah.edu/~nahaj/factoring/isqrt.c.html
# converted to GOLF assembly for http://codegolf.stackexchange.com/questions/49356/testing-if-a-number-is-a-square

# unrolled for speed, original source commented out at bottom
start:
    or u, t, 1 << 62
    shr t, t, 1
    gequ v, n, u
    jz nope62, v
    sub n, n, u
    or t, t, 1 << 62
    nope62:

    or u, t, 1 << 60
    shr t, t, 1
    gequ v, n, u
    jz nope60, v
    sub n, n, u
    or t, t, 1 << 60
    nope60:

    or u, t, 1 << 58
    shr t, t, 1
    gequ v, n, u
    jz nope58, v
    sub n, n, u
    or t, t, 1 << 58
    nope58:

    or u, t, 1 << 56
    shr t, t, 1
    gequ v, n, u
    jz nope56, v
    sub n, n, u
    or t, t, 1 << 56
    nope56:

    or u, t, 1 << 54
    shr t, t, 1
    gequ v, n, u
    jz nope54, v
    sub n, n, u
    or t, t, 1 << 54
    nope54:

    or u, t, 1 << 52
    shr t, t, 1
    gequ v, n, u
    jz nope52, v
    sub n, n, u
    or t, t, 1 << 52
    nope52:

    or u, t, 1 << 50
    shr t, t, 1
    gequ v, n, u
    jz nope50, v
    sub n, n, u
    or t, t, 1 << 50
    nope50:

    or u, t, 1 << 48
    shr t, t, 1
    gequ v, n, u
    jz nope48, v
    sub n, n, u
    or t, t, 1 << 48
    nope48:

    or u, t, 1 << 46
    shr t, t, 1
    gequ v, n, u
    jz nope46, v
    sub n, n, u
    or t, t, 1 << 46
    nope46:

    or u, t, 1 << 44
    shr t, t, 1
    gequ v, n, u
    jz nope44, v
    sub n, n, u
    or t, t, 1 << 44
    nope44:

    or u, t, 1 << 42
    shr t, t, 1
    gequ v, n, u
    jz nope42, v
    sub n, n, u
    or t, t, 1 << 42
    nope42:

    or u, t, 1 << 40
    shr t, t, 1
    gequ v, n, u
    jz nope40, v
    sub n, n, u
    or t, t, 1 << 40
    nope40:

    or u, t, 1 << 38
    shr t, t, 1
    gequ v, n, u
    jz nope38, v
    sub n, n, u
    or t, t, 1 << 38
    nope38:

    or u, t, 1 << 36
    shr t, t, 1
    gequ v, n, u
    jz nope36, v
    sub n, n, u
    or t, t, 1 << 36
    nope36:

    or u, t, 1 << 34
    shr t, t, 1
    gequ v, n, u
    jz nope34, v
    sub n, n, u
    or t, t, 1 << 34
    nope34:

    or u, t, 1 << 32
    shr t, t, 1
    gequ v, n, u
    jz nope32, v
    sub n, n, u
    or t, t, 1 << 32
    nope32:

    or u, t, 1 << 30
    shr t, t, 1
    gequ v, n, u
    jz nope30, v
    sub n, n, u
    or t, t, 1 << 30
    nope30:

    or u, t, 1 << 28
    shr t, t, 1
    gequ v, n, u
    jz nope28, v
    sub n, n, u
    or t, t, 1 << 28
    nope28:

    or u, t, 1 << 26
    shr t, t, 1
    gequ v, n, u
    jz nope26, v
    sub n, n, u
    or t, t, 1 << 26
    nope26:

    or u, t, 1 << 24
    shr t, t, 1
    gequ v, n, u
    jz nope24, v
    sub n, n, u
    or t, t, 1 << 24
    nope24:

    or u, t, 1 << 22
    shr t, t, 1
    gequ v, n, u
    jz nope22, v
    sub n, n, u
    or t, t, 1 << 22
    nope22:

    or u, t, 1 << 20
    shr t, t, 1
    gequ v, n, u
    jz nope20, v
    sub n, n, u
    or t, t, 1 << 20
    nope20:

    or u, t, 1 << 18
    shr t, t, 1
    gequ v, n, u
    jz nope18, v
    sub n, n, u
    or t, t, 1 << 18
    nope18:

    or u, t, 1 << 16
    shr t, t, 1
    gequ v, n, u
    jz nope16, v
    sub n, n, u
    or t, t, 1 << 16
    nope16:

    or u, t, 1 << 14
    shr t, t, 1
    gequ v, n, u
    jz nope14, v
    sub n, n, u
    or t, t, 1 << 14
    nope14:

    or u, t, 1 << 12
    shr t, t, 1
    gequ v, n, u
    jz nope12, v
    sub n, n, u
    or t, t, 1 << 12
    nope12:

    or u, t, 1 << 10
    shr t, t, 1
    gequ v, n, u
    jz nope10, v
    sub n, n, u
    or t, t, 1 << 10
    nope10:

    or u, t, 1 << 8
    shr t, t, 1
    gequ v, n, u
    jz nope8, v
    sub n, n, u
    or t, t, 1 << 8
    nope8:

    or u, t, 1 << 6
    shr t, t, 1
    gequ v, n, u
    jz nope6, v
    sub n, n, u
    or t, t, 1 << 6
    nope6:

    or u, t, 1 << 4
    shr t, t, 1
    gequ v, n, u
    jz nope4, v
    sub n, n, u
    or t, t, 1 << 4
    nope4:

    or u, t, 1 << 2
    shr t, t, 1
    gequ v, n, u
    jz nope2, v
    sub n, n, u
    or t, t, 1 << 2
    nope2:

    or u, t, 1 << 0
    shr t, t, 1
    gequ v, n, u
    jz nope0, v
    sub n, n, u
    nope0:

end:
    not s, n        # return !remainder
    halt 0

# before unrolling...
#
# start:
#     mov b, 1 << 62  # squaredbit = 01000000...
# loop:               # do {
#     or u, b, t      #   u = squaredbit | root
#     shr t, t, 1     #   root >>= 1
#     gequ v, n, u    #   if remainder >= u:
#     jz nope, v
#     sub n, n, u     #       remainder = remainder - u
#     or t, t, b      #       root = root | squaredbit
# nope:
#     shr b, b, 2     #   squaredbit >>= 2
#     jnz loop, b      # } while (squaredbit > 0)
# end:
#     not s, n        # return !remainder
#     halt 0

```

EDIT 1: removed squaring test, return !remainder directly, save 3 ops per test

EDIT 2: use n as the remainder directly, save 1 op per test

EDIT 3: simplified the loop condition, save 32 ops per test

EDIT 4: unrolled the loop, save about 65 ops per test
> 5 votes

# Answer
# Score: 344493

Does a simple binary search within the interval `[1, 4294967296)` to approximate `sqrt(n)`, then checks if `n` is a perfect square.

```
mov b, 4294967296
mov c, -1

lesser:
    add a, c, 1

start:
    leu k, a, b
    jz end, k

    add c, a, b
    shr c, c, 1

    mulu d, e, c, c

    leu e, d, n
    jnz lesser, e
    mov b, c
    jmp start

end:
    mulu d, e, b, b
    cmp s, d, n

    halt 0

```
> 3 votes

---
Tags: number-theory, fewest-operations, golf-cpu
---


# Question
Title: Write a program that finds the most occurring paired letter in a string
The program must output the letter that is paired the most. For example, if your program was given the following string:

```
"Sally's friend Bobby searched for seashells."

```

it must output `L` because `"ll"` occurs twice, which is more frequent than the other pair `"bb"`.

Rules:

* If more than one letter has 1st place for occurrences, then output all of them in alphabetical order (e.g. `"Sally's friends Jimmy and Bobby rummaged for seashells."` should output both `L` AND `M` \[or `"LM"` if you please\] because they both occur more frequently than other pairs.)
* Letters which are tripled, quadrupled, etc. count as one pair (e.g. `"lll"` in `"willless"` is counted as only one pair of `L`.)
* Letter pairs must be in one word (e.g. `"Sally's sociable friends Sammy and Bobby searched for fabulous seashells."` should output `L` and not `S` because despite `"ss"` having more occurrences than `"ll"`, they are separated by spaces.)
* Count only letters from the English alphabet
* Case does not matter (e.g. `"Ss"` is the same as `"SS"` or `"ss"`, and all are counted as one pair of `S`.)

You may read your input from wherever you please. Shortest code wins.

# Answer
> 6 votes
# Pyth, ~~26~~ ~~25~~ ~~24~~ ~~16~~ 15 bytes

```
.M/sfthTrrz08ZG

```

Try it online: Demonstration

### Explanation:

```
.M/sfthTrrz08ZG   implicit: z = input string
         rz0      convert z to lower-char
        r   8     run-length-encoding (into tuples [count, char])
    f             filter for tuples T, which satisfy:
     thT            T[0]-1 != 0 (count > 1)
   s              join to a string
.M            G   find the elements Z of "abcd...z", which produce the highest value:
  /...........Z       count of Z in ...

```

# Answer
> 7 votes
# Bash + GNU coreutils, 133

```
grep -Eo '([A-Z])\1+'<<<"${1^^}"|cut -c1|sort|uniq -c|sort -rn|while read n l
do((a-n&&a-0))&&exit||echo $l&&a=$n
done|sort|tr -d \\n

```

### Testcases:

```
$ for t in "Sally's friend Bobby searched for seashells." \
> "Sally's friends Jimmy and Bobby rummaged for seashells." \
> "willless" \
> "Sally's sociable friends Sammy and Bobby searched for fabulous seashells." \
> "11ss11aa"
> do
> ./mostpaired.sh "$t"
> echo
> done
L
LM
LS
L
AS
$

```

# Answer
> 5 votes
# CJam, ~~29~~ 27 bytes

```
leue`{2a>},s_el-$e`$z~\)-,>

```

*Thanks to @Optimizer for golfing off 2 bytes!*

Try it online in the CJam interpreter.

### How it works

```
leu    e# Read a line from STDIN and covert to uppercase.
e`     e# Perform run-length encoding.
       e# Example: "AABBBC!!" -> [[2 'A] [3 'B] [1 'C] [2 '!]]
{2a>}, e# Filter out all pairs that are less of equal to [2].
s      e# Stringify.
       e# Example: [[2 'A] [3 'B] [2 '!]] -> "2A3B2!"
_el    e# Push a copy of the string and convert to lowercase.
       e# Example: "2A3B2!" -> "2a3b2!"
-      e# Remove all character from the second string from the first.
       e# Example: "2A3B2!" "2a3b2!" - -> "AB"
$e`$   e# Sort, perform run-length encoding and sort again.
       e# Example: "ABACABDBC" -> "AAABBBCCD"
       e#                      -> [[3 'A] [3 'B] [2 'C] [1 'D]]
                               -> [[1 'D] [2 'C] [3 'A] [3 'B]]
z~     e# Zip and dump.
       e# Example: [[1 'D] [2 'C] [3 'A] [3 'B]] -> [1 2 3 3] ['D 'C 'A 'B]
\)     e# Pop out the last element from the first array.
       e# Example: [1 2 3 3] -> [1 2 3] 3
-      e# Remove all occurrences of the popped element from the array.
       e# Example: [1 2 3] 3 -> [1 2]
,      e# Compute the length of the remainder.
>      e# Skip that many elements from the character array.

```

# Answer
> 4 votes
# Pyth - 23 22 21 20 bytes

Uses regexp substitution to replace all of two or greater of alphabet to a temp value, and uses `.M`aximal to get all the have the highest occurrence. Thanks to @Jakube for pointing out the redundancy of sorting and saving a byte.

```
.M/:rz0+Z"{2,}"KC0KG

```

Takes input from stdin and outputs like `['l', 'm']` to stdout.

```
.M        G         Values which yield maximal amount over lowercase alphabet
 /                  Count
  :                 Regexp substitution
   rz0              Lowercased input
   +Z               String concatenate current loop var
    "{2,}"          Regexp 2 or more of previous group
   KCZ              Inline assign null byte to K and use value
  K                 Count K which is null byte

```

Try it online here.

# Answer
> 4 votes
# C, 155

Something different, no regexps.

```
m=1,i=1,n[91];
main(c,a)char**a;
{
  char*t=a[1];
  for(;c=*t++;)(c&=95)>64&&c<91&&(c-(*t&95)?i=1:(c=(n[c]+=i),i=0,m=m<c?c:m));
  for(c=0;++c<91;)n[c]-m||putchar(c);
}

```

# Answer
> 3 votes
# Python 2, ~~132~~ 143 bytes

```
def f(x):import re;x=re.findall(r'(.)\1+',x.upper());s={l:x.count(l)for l in x};print "".join(sorted([l for l in s if s[l]==max(s.values())]))

```

Example run:

```
f("Sally's friends Jimmy and Bobby rummaged for seashells.")
LM

```

# Answer
> 2 votes
# R, 105 bytes

```
cat(substr(names(b<-table(regmatches(s<-toupper(readline()),gregexpr("([A-Z])\\1+",s))))[b==max(b)],1,1))

```

This reads a line of text from STDIN and prints a space delimited list of the most common paired letters to STDOUT.

Ungolfed + explanation:

```
# Read a string from STDIN, convert to uppercase
s <- toupper(readline())

# Get each match of the regex /([A-Z])\1+/
matches <- regmatches(s, gregexpr("([A-Z])\\1+", s))

# Compute the frequency of each match
freq <- table(matches)

# Get the matches with the highest frequency
highest <- names(freq)[freq == max(freq)]

# Each element of highest is the literal pair, so take the first character
first <- substr(highest, 1, 1)

# Print to STDOUT
cat(first)

```

Examples:

```
> (code)
Sally's friends Jimmy and Bobby rummaged for seashells.
L M

> (code)
Sally's friend Bobby searched for seashells.
L

> (code)
Sally's sociable friends Sammy and Bobby searched for fabulous seashells.
L

> (code)
11ss11nn
N S

```

You can try it online!

# Answer
> 2 votes
# CJam, 37 bytes

```
leue`{~_el-\(e&},1f=$e`$_W=0=f-{,1=},

```

Try it online

Without regular expression support, I'm afraid it will be tough to compete with Pyth. This is the best I came up with on a first pass.

Explanation:

```
l     Get input.
eu    Convert it to upper case, since case does not matter.
e`    Run length encoding, to split into groups of same characters.
{     Start of block for filtering.
  ~     Unpack the length/letter pair.
  _     Copy the letter.
  el    Change copy to lower case.
  -     Subtract to compare. If result is non-zero, this is a letter.
  \     Swap count to top.
  (     Decrement to get truthy value for count > 1.
  e&    Logical and: It's a letter, and count is > 1.
},    End of filter.
1f=   Don't need the counts anymore, filter out the letters only from the RLE pairs.
$     Sort them, so that multiples of the same letter are sequential.
e`    RLE again, to count how many multiples of each letter we had.
$     And sort again, to get the count/letter pairs in order of incrementing count.
_     Copy list.
W=0=  Pick out count of last element, which is the highest count.
f-    Remove count from pairs that have the highest count. This leaves them
      as one member lists with letter only, while others still have count/letter.
{     Start block for filter.
  ,1=   Check for list length one.
},    End filter.

```

# Answer
> 2 votes
# Q (66)

Relatively readable to boot:

```
{where g=max g:.Q.A#count each group y where not differ y:upper x}

```

# Answer
> 2 votes
# Python 2, 185 159 153

```
i=input().lower()
d=sorted({l:len(i.split(l+l))for l in map(chr,range(97,123))}.items(),None,lambda x:x[1],1)
print sorted(c for c,k in d if k==d[0][1])

```

Takes input as a quoted string.

# Answer
> 2 votes
# Ruby, 60

```
f=->s{(?a..?z).group_by{|l|s.scan(/#{l*2}+/i).size}.max[1]}

p f["Sally's friends Jimmy and Bobby rummaged for seashells."]

```

`group_by` creates a hash (dictionary) structure where the keys are the output of the block and the values are lists of letters that result in each key. In this case, the keys are counts of 2+ runs of a letter, case-insensitive. `max` compares each `[key,value]` tuple lexicographically, so it just finds the maximum key. Then `[1]` returns the value list part of the tuple.

# Answer
> 2 votes
# C# 160 Bytes

Where `s` is the input:

```
char? d(string s){s=s.ToUpper();return s.Select((x,i)=>new{y=x,z=i==0?(char?)null:s[i-1]}).Where(x=>x.y==x.z).GroupBy(x=>x.z).OrderBy(x=>x.Count()).Last().Key;}

```

# Answer
> 1 votes
# rs, 146 bytes

```
[^A-Za-z]/
*(.)\1+/\1\1
*(.)(?!\1)/
$/#
+*(.)#(?!.*?\1)/#\1
+*(.)(.*)#(.*)\1/\2#\3\1\1
#/
*(.)(\1*)/\1(_)^^((^^\1\2))
([^_])(_+)(?!_)(?=.*\2_)/
_/

```

Try it! Please! It took me forever to make the buttons even with the output box on that page...

Well, this was fairly...crazy. The logic here is kind of weird; I'll only post an explanation if someone asks. (Of course, I also said that for an INTERCAL answer whose explanation was requested...that I never explained... ;)

# Answer
> 1 votes
# JavaScript 156 153

```
var x=prompt(),f={},a=0,o
x.toUpperCase().replace(/([A-Z])\1+/g,function(m,s){m=f[s]=-~f[s]
if(a==m)o.push(s)
if(a<m)a=m,o=[s]})
alert(o.sort().join(""))
```

# Answer
> 1 votes
**Bash + textutils (grep, sed), 111 chars**

```
fold -1<<<$s|uniq -iD|sort -f|uniq -ic|sort -rn|grep -i [A-Z]|sed -n '1h;G;s/\(\s*\S\+\s\)\(.\)\n\1./\2/p'|sort

```

**Bash + awk (instead of sed), 97 chars**

```
fold -1<<<$s|uniq -iD|sort -f|uniq -ic|sort -rn|grep -i [A-Z]|awk '!n{n=$1};n==$1{print $2}'|sort

```

to test it, first assign s

```
s="Sally's friends Jimmy ää and Bobby rummaged ää for seashells."

```

# Answer
> 0 votes
# R, 98 bytes

Very similar to Alex's solution, but uses a substitution rather than a match to determine consecutive letters. Scan is used to get the input and also to split the substitution result on spaces.

```
cat(names(a<-table(scan(,'',t=gsub('([A-z]?)(\\1?)[^A-z]*','\\U\\2 ',scan(,''),T,T))))[a==max(a)])

```

A couple of tests

```
> cat(names(a<-table(scan(,'',t=gsub('([A-z]?)(\\1?)[^A-z]*','\\U\\2 ',scan(,''),T,T))))[a==max(a)])
1: 11 was a race horse, 22 was one too. 11 won one race and 22 one won too.
19:
Read 18 items
Read 2 items
O
> cat(names(a<-table(scan(,'',t=gsub('([A-z]?)(\\1?)[^A-z]*','\\U\\2 ',scan(,''),T,T))))[a==max(a)])
1: Sally's friends Jimmy and Bobby rummaged for seashells.
9:
Read 8 items
Read 5 items
L M
> cat(names(a<-table(scan(,'',t=gsub('([A-z]?)(\\1?)[^A-z]*','\\U\\2 ',scan(,''),T,T))))[a==max(a)])
1: 11ss11nn
2:
Read 1 item
Read 2 items
N S
>

```

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