title: Columnar Transposition Cipher

text:
# Question
Title: Columnar Transposition Cipher
# Columnar Transposition Cipher

While I have plenty of programs I have written for more advanced ciphers, I just realised I don't actually have one for one of the simplest: Columnar Transposition. The cipher, in case you don't know, works as follows:

1. First, you take the key, and write it as numbers. The numbers are made by replacing the letter which comes first in the alphabet with `1`, the letter that comes next `2` and so on, ignoring duplicates (the key `GOAT` would become `2314`). These numbers are the headers of the columns.

```
2314
----

```
2. Next, you write your message under the columns.

```
2314
----
Hell
o Wo
rld!

```
3. Finally, rearrange the columns into the numerical order in which they would fall, and read the ciphertext across.

```
1234
----
lHel
Wo o
drl!

```
4. Which will result in your encoded text: `lHelWo odrl!`

## Rules

* Each submission should be either a full program or function. If it is a function, it must be runnable by only needing to add the function call to the bottom of the program. Anything else (e.g. headers in C), must be included.
* There must be a free interpreter/compiler available for your language.
* If it is possible, provide a link to a site where your program can be tested.
* Your program must not write anything to STDERR.
* Your program should take input as an argument or from STDIN (or the closest alternative in your language).
* Standard loopholes are forbidden.

## Requirements

* Case must be preserved.
* Your cipher should be 'irregular', that is, if there are any spaces left after you have written out your message, it is treated as if it were a normal space character.
* Only encryption is required, decryption may come in a later challenge.
* Input should be taken from `STDIN` with the key on the first line, and the plaintext on the second. If you are taking input as an argument, please specify how this is done for your language.
* The key can be in any case.
* Duplicates in the key should be ignored - that is, `ABCDB` would become `ABCD`. Duplicates also apply in any case.
* Trailing whitespace is included.

## Test Cases

```
CBABD, Duplicates are ignored. ==> puDlacit sea eriongr.de
bDaEc, Key can be in multicase! ==> yKce  aenbn mi tucliea s!

```

Full example, with 'surplus space' rule.

```
ADCB
----
"Goo
d Mo
rnin
g!"
he c
alle
d.

ABCD
----
"ooG
dom
rnin
g "!
hc e
aell
d  .

Message: "ooGdom rning "!hc eaelld  .

```

## Scoring

is how we score this challenge!

## Submissions

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

```
# Language Name, N bytes

```

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

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

```

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

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

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

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

```

## Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

```
/* Configuration */

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

/* App */

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

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

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

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

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

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });

  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();

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

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

  langs.sort(function (a, b) {
    if (a.lang > b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

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

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

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
# MATL, 12 bytes

```
kune2M&SY)1e

```

**Try it online!**

### Explanation

The code works using rows instead of columns. This is totally equivalent and fits better with MATL's column-major indexing.

```
k     % Take first input (key) implicitly. Convert to lowercase
u     % Keep unique chars, stably
n     % Number of unique chars
e     % Take second input (message) implicitly. Reshape into char matrix
      % with the above number of rows, padding with zeros if needed
2M    % Push string with unique chars of key again
&S    % Sort and push the indices of the sorting
Y)    % Use as row indices into char matrix
1e    % Reshape into a row. Zeros are displayed as spaces

```
> 2 votes

# Answer
# Python 3, 188 bytes.

There's gotta be a saner way to do this.

```
from itertools import*
def f(a,b):a,c,s=a.upper(),''.join,sorted;return c(map(c,zip_longest(*[v for k,v in s([(v,b[i::len({*a})])for i,v in enumerate(s({*a},key=a.find))])],fillvalue='')))

```

Test cases:

```
assert f('goat', 'Hello World!') == 'lHelWo odrl!'
assert f('GOAT', 'Hello World!') == 'lHelWo odrl!'
assert f('GOAATAT', 'Hello World!') == 'lHelWo odrl!'
assert f('CBABD', 'Duplicates are ignored.') == 'puDlacit sea eriongr.de'

```

Well that was a fun journey back to square one.
> 2 votes

# Answer
## JavaScript (ES6), 170 bytes

```
(k,s)=>[...s].map((c,i)=>(i%l||(r+=t.join``,t=[]),t[[...k].sort().search(k[i%l])]=c),k=[...k=k.toLowerCase()].filter((c,i)=>i==k.search(c)),l=k.length,r=t=[])&&r+t.join``

```

Preprocessing the key is a waste of 56 bytes...
> 1 votes

# Answer
# Python 3.5, 139

```
def f(a,b):a,s,j=a.lower(),sorted,''.join;a=s({*a},key=a.find);l=len(a);return j(map(j,[*zip(*s(zip(*zip(*[iter(a+[*b+' '*l])]*l))))][1:]))

```

Slightly more readable version:

```
def f(a, b):
    a = a.lower()
    # Remove duplicates
    a = sorted({*a}, key=a.find)
    l = len(a)
    # Add the key
    z = zip(*[iter(a + [*b, *[''] * l])]*l)
    # Sort tuples lexicographically, remove the key
    z = [*zip(*sorted(zip(*z)))][1:]
    return ''.join(map(''.join, z))

```
> 1 votes

# Answer
## Javascript, 155 ~~159~~ ~~149~~ ~~151~~

```
(w,s)=>(a='',z=new Set,w=[...[...w].map(z.add,z)[0]].sort(),eval(`s.match(/.{1,${z.size}}/g)`).map(l=>[...l].map((c,i)=>a+=l[[...z].indexOf(w[i])]||'')),a)

```
* Saved 4 bytes thanks @Bergi.

---

Here it goes, ungolfed and explained:

```
function ColumnarTranspositionCipher(word, sentence) {
    var answer = "";

    // the own methods of Set does it shorter than a raw Object
    var z = new Set;

    // As Set only allows unique keys, we get the processed key by adding
    [...word].forEach(function(letter) {
        z.add(letter);
    });

    // word now has the sorted key
    word = [...z].sort(),

    // divide sentence by the processed key's length
    sentence = sentence.match(RegExp(".{1," + z.size + "}", "g"));

    sentence.forEach(function(row) {
        [...row].forEach(function(letter, newIndex) {

            // get the old index - relative to the previous sorted/unsorted keys
            var oldIndex = [...z].indexOf(word[newIndex]);

            // and add to the answer
            answer += row[oldIndex] || "";
        });
    });

    return answer;
}

r= code=> output.innerHTML += '\n>  ' + code + '\n<- "' + eval(code) + '"\n';
r("ColumnarTranspositionCipher('GOAT', 'Hello World!')");
r("ColumnarTranspositionCipher('CBABD', 'Duplicates are ignored.')");
r("ColumnarTranspositionCipher('aBeCd', 'Key can be in multicase!')");
```

```
<pre id=output></pre>
```
> 1 votes

# Answer
## Haskell, ~~98~~ ~~84~~ 83 bytes

```
import Data.List
h c=map snd.sort.zip((<$>nub((`mod`32).fromEnum<$>c)).(,)=<<[1..])

```

Usage example: `h "CBAbD" "Duplicates are ignored."` -\> `"puDlacit sea eriongr.de"`.

How it works:

```
       nub((`mod`32).fromEnum<$>c)  -- turn key to lowercase and remove duplicates
    (<$>      ).(,)=<<[1..]         -- make pairs of (number , char from key)
                                    -- for every character in the key and every
                                    -- number starting with 1. This builds and
                                    -- infinite list, e.g. for the key "cba":
                                    -- (1,c),(1,b),(1,a),(2,c),(2,b),(2,a),(3,c)...
              zip(          )       -- zip this list with input String, e.g. for
                                    -- the string "mnopq" with the key from above:
                                    -- ((1,c),m),((1,b),n),((1,a),o),((2,c),p),((2,b),q)
                                    -- zip stops at the end of the shorter list
         sort                       -- sort lexicographically
 map snd                            -- extract characters of the string

```
> 1 votes

# Answer
# J, 53 bytes

```
(3 :',/|:((/:tolower~.>0{y){|:((-#~.>0{y),\(>1{y)))')

```

Usage example: `(3 :',/|:((/:tolower~.>0{y){|:((-#~.>0{y),\(>1{y)))') ('ADCB';'"Good Morning!" he called.')` ==\> `"ooGdoM rning "!hc eaelld .`

I basically did exactly what the cipher does, no shortcuts. I had to transpose the matrix to deal with ranking the columns then transpose it back.

Try it Online! (make sure to type "j-bot: " without quotes then paste the code.)
> 1 votes

# Answer
# R, 182 177

Here is the golfed version:

```
function(t,k){k=unique(unlist(strsplit(tolower(k),"")));t=unlist(strsplit(t,""));l=length(t);c=length(k);r=ceiling(l/c);t=c(t,rep("",c*r-l));cat(matrix(t,r,c)[order(rank(k)),])}

```

And ungolfed version, which shows how the function takes the data.

```
# test data
key = "aBeCd"
test = "ABCDEabcdeABCDEabcdeABC!"

# t is the test phrase, k is the key
cipher=function(t,k){
    k=unique(unlist(strsplit(tolower(key),"")))
    t=unlist(strsplit(test,""))
    l=length(t)
    c=length(k)
    r=ceiling(l/c)
    t=c(t,rep("",c*r-l))
    cat(matrix(t,r,c)[order(rank(k)),])
}

# Show that it works
cipher(test,key)
## A B D E C a b d e c A B D E C a b d e c A B !  C

```

The test cases provided by the OP seem incorrect. I intentionally chose a test case here that makes it more clear what is happening to the letters, and this seems correct.
> 0 votes

# Answer
# Ruby, 133 bytes

Zip, sort, zip again, combine.

```
->k,s{k=k.upcase.chars.uniq
c,*r=k.zip(*s.scan(/.{1,#{k.size}}/).map(&:chars)).sort
c.zip(*r.map{|e|e ?e:' '})[1..-1].map(&:join)*''}

```
> 0 votes

# Answer
## Q, 52 Bytes

```
f:{n:#u::?_x;,/+(+(0N;n)#(n*-_-(#y)%n)#y,n#" ")@<u}

```

NOTE.- defined as function named f to facilitate tests. As an anonymous function we delete chars f: (50 Bytes)

**Test**

Interpreter (evaluation but unrestricted) downloadable by not fee at kc.com (windows/linux/mac versions)

```
f["CBABD"]"Duplicates are ignored."     /"puDlacit sea eriongr.de"
f["bDaEc"]"Key can be in multicase!"    /"yKce  aenbn mi tucliea s!"

```

**Explanation**

`n:#u:?_x` u is unique chars in lowercase key, and n its length

`(n*-_-(#y)%n)#y,n#" "` appends blanks to accomplish 'space surplus' rule.

`%` is division `-_-` implements ceil as negate floor negate, so `(n*-_-(#y)%n)` is the length required by space surplus. `y,n#" "` append n blank spaces to end of text, and then take length of that extended text

```
(0N;n)#.. takes items of sequence .. to fill a matrix of n columns by row

```

`+(..)` flip that matrix (traspose) to work by rows

`@<u` selects row indexes by ascending index order of u

```
,/(..) concatenates the resulting matrix to obtain a text

```
> 0 votes

---
Tags: code-golf, cipher
---


title: Let's play ASCII mini-golf

text:
# Question
Title: Let's play ASCII mini-golf
Let's play code golf... by playing golf.

## Input

Your input will be a string consisting of `#`'s, an `o`, an `@`, and `.`'s. For example:

```
......@..
.....##..
.........
......o..

```

`.` \- playable golf course (all shots must end on one of these)
`#` \- a barrier (shots cannot go through this)
`o` \- the starting position of your golf ball
`@` \- the hole

## How to Play ASCII Golf

You start at the `o`. Here is a valid shot from point `A` to point `B`:

1) This shot is straight line that can be drawn between `A` and `B` (no curved shots).

```
A....
....B

```

2) The line `AB` may not intersect with a `#` (barrier), e.g.:

```
A.#.B

```

It **may**, however, be tangent to a barrier:

```
A#
.B

```

3) *(For clarity)* You may **not** bounce shots off barriers or the edge of the golf course.

## Output

Print to `stdout` (or an acceptable equivalent) the minimum number of shots to get the ball into the hole `@`. If it is not possible, print `-1`.

## Examples

```
o....@

```

`=> 1`

```
o.#.@

```

`=> -1`

```
o..#
..#@

```

`=> 2` (you can pass through the vertices of a `#`, but not the edges)

```
o#...#
.#.#.#
...#.@

```

`=> 4`

# Answer
# Python 2, 469

Pretty long, but it's a start:

```
R=range
def l(c,x,y,z,t):
 f=abs(z-x);g=1-2*(z<x);p=abs(t-y);q=1-2*(t<y);v=r=0
 for i in R(f):
  w=f+(2*i+1)*p
  for j in R(v,(w-1)/2/f+1):r|='.'>c[x+g*i][y+q*j]
  v=w/2/f
 for j in R(v,p+1):r|='.'>c[z][y+q*j]
 return r
def f(c):
 a="".join(c);n=len(c[0]);b=len(a);d=[[9**9*l(c,i/n,i%n,j/n,j%n)+1for i in R(b)]for j in R(b)]
 for k in R(b):
  for i in R(b):
   for j in R(b):
    t=d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    if"o@"==a[i]+a[j]:r=t
 return-1if r>9**9else r

```

Function f takes a list of strings and returns the number of shots.

Test suite:

```
def test(s,r):
 print"ok"if f(s.split())==r else"fail"

test("o # @", -1)
test("......@.. .....##.. ......... ......o..", 2)
test("o....@", 1)
test("o.#.@", -1)
test("o..# ..#@", 2)
test("o#...# .#.#.# ...#.@", 4)
test("o### #..# ###@", 3)
test("o.## ##.@", 1)
test("...o .@#.", 2)

```
> 3 votes

---
Tags: code-golf, ascii-art, path-finding, simulation
---


title: Chaining Words Together

text:
# Question
Title: Chaining Words Together
Given two words and a list as input, your program must (in as few characters as possible, of course) find the shortest way to "chain" the first word to the last using the ones in the list. Two words are "chained" if their first and last letters are the same, e.g. "Food" and "Door".

Your program will take input as a string with words separated by spaces, and output a list (in whatever format is most convenient: string, array/list type, etc) of the completed chain.

Examples:

`Input: joke corn tan disc need eat`
`Output: joke eat tan need disc corn`

The first two words in the input list are the first and last words in the chain, and the rest are the constituent words.

`Input: best fry easy elf mean tame yam nice`
`Output: best tame elf fry`
NOT: `best tame easy yam mean nice elf fry`

`Input: rug gunned orange purple gains pore soup emo ending`
`Output: rug gunned`

`Input: %3gioxl? 6699-4 !f!!&+ ?4; ;78! +6`
`Output: %3gioxl? ?4; ;78! !f!!&+ +6 6699-4`
The "words" don't have to be real words; for the purpose of the challenge, any ASCII character except the space will count as part of a word.

`Input: mouth rich frame inspire item sold`
Output when the first and last word are impossible to chain is undefined, so handle it however's shortest.

# Answer
# Pyth - 42 bytes

Complete brute force. Surprisingly fast, finishes all possible the test cases in seconds. Will run forever with impossible inputs.

```
Acczd]2.VZIJf.Amqhedehd,VTtTm++hGdeG^HbhJB

```

Test Suite.
> 1 votes

# Answer
# Pyth, ~~51~~ 48 bytes

FGITW.

```
=cQdMqeGhHL++hQb@Q1holN{+Fmf.AgVTtTyM+]Y._d.p>Q2

```

Test suite.
> 2 votes

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


title: Create a fractal tree

text:
# Question
Title: Create a fractal tree
What I would like to see is a fractal tree being drawn where the you can input an integer, and the output will be a fractal tree with the entered amount of branch steps.

Rules:

* The fractal should be a line fractal tree:
* the shape of the fractal should also be the same as this picture.
* Each branch should decrease by 25% in width for each time it splits
* The final layer of branches should be an 1px wide line
* Shortest code wins

Tip: this site might be useful.

# Answer
> 14 votes
## Context Free, ~~82~~ ~~65~~ 57 characters

```
rule T{9*[y 1]SQUARE[]2*{f 90}T{s.75y 8r 25}}startshape T

```

See: http://www.contextfreeart.org/gallery/view.php?id=3384

Golf'd further with help from Context Free Art users *minimaleye, MtnViewJohn,* and *kipling*.

# Answer
> 9 votes
# Python - 215

```
import turtle
t=turtle.Turtle()
def f(w):
    if w>=1:
        s=t.pensize()
        t.pensize(w)
        t.fd(w*9)
        t.rt(20)
        f(w*.75)
        t.lt(40)
        f(w*.75)
        t.right(20)
        t.bk(w*9)
        t.pensize(w)
t.speed(9)
f(9)
t.ht()
raw_input()

```

Close enough?

# Answer
> 9 votes
# Logo, ~~88~~, 86

```
to t:d if:d=0[stop]setpensize:d*.75 fd:d*7 rt 25 t:d-1 lt 50 t:d-1 rt 25 bk:d*7end t [numsteps]

```

Edit: Made the branches decrease as pointed out in the comments.

# Answer
> 9 votes
# Mathematica 127

```
k=12;

r=#2/.{x__Real}:>.1{{7,-#},{#,7}}.{x}+y&;
f@n_:={f@1=N@Polygon@{y={0,.7^k},0y,x={.002,0},x+y},r[-4,p=f[n-1]],4~r~p}
Graphics@f@k

```

Value `.002` adjusted to produce 1 pixel width of the final branches.

# Answer
> 9 votes
# HTML+CSS (no JavaScript) ~~14791~~ 14630 (multiplatform), 294 (webkit only)

You can't specify how many levels you go.. And yes it is pretty big. But it is pure HTML/CSS, without any JavaScript.

```
<style>q{background-color:#000}q::before{content:""}q.start{width:15px;height:100px;position:absolute;top:500px;left:500px}q q{position:absolute;width:75%;height:75%;top:-55%}q q:nth-child(1){left:-90%;transform:rotate(-27deg)}q q:nth-child(2){left:110%;transform:rotate(27deg)}</style><q class="start"><q><q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q></q><q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q></q></q> <q><q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q></q><q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q><q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q><q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q><q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q><q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q><q><q><q><q></q><q></q></q><q><q></q><q></q></q></q><q><q><q></q><q></q></q><q><q></q><q></q></q></q></q></q></q></q></q></q></q></q>

```

Webkit short version:

```
<style>b{background:#000;-webkit-box-reflect: left;}b.i{width:7px;height:100px;position:absolute;top:500px;left:500px}b b{position:absolute;width:75%;height:75%;top:-70%}b b{right:300%;transform:rotate(-27deg)}</style><b class="i"><b><b><b><b><b><b><b><b></b><b></b></b></b></b></b></b></b></b>

```

**Edit:** removed the cross browser prefixes, firefox and google chrome render it properly without it. **Edit 2:** Added a much shorter version that uses -webkit-box-reflect. Only works in webkit based browsers though.

# Answer
> 7 votes
# Mathematica 199

```
f[p : {_, _}, r_, s_, d_] := Module[{q}, If[d == 0, Return[]];
  q = p + {Cos@r, Sin@r}*d;
  DeleteCases[
   Flatten@{{Thickness[.002*1.25^d], Line@{p, q}},
     f[q, r - s, s, d - 1], f[q, r + s, s, d - 1]}, Null]]
g@d_ := Graphics[f[{0, 0}, Pi/2, Pi/9, d]]

```

**Example**

8 is the depth of the tree.

```
g[8]

```

# Answer
> 6 votes
# Postscript ~~216~~ ~~214~~ 209

Uses the criteria "linewidth==1 pixel" as the recursion bound. *Edit:* juggled some constants. *Edit:* tweak, tweak.

```
/b{gsave dup scale rotate
0 0 0 12 0 0 moveto translate lineto stroke
currentlinewidth 0 dtransform dup mul exch dup mul add sqrt 1 ge
{28 .75 b -28 .75 b}if grestore}def
2 setlinewidth
200 20 translate
0 6 b

```

binary-token workfile:

```
0 6 200 20 2
/.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
%/b{gsave dup scale rotate  % gsave=78(N)<4E> dup=56(8)<38> scale=139<8B> rotate=136<88>
/b{
%(N8)$<8B88>$
<4E388B88>$
0 0 0 12 0 0
%moveto translate lineto stroke
% moveto=107(k)<6B> lineto=99(c)<63> translate=173<AD> stroke=167<A7>
%(k)$<AD>$(c)$<A7>$
%<6B63ADA7>$ % <--this typo makes a pot leaf. :-)
<6BAD63A7>$
%currentlinewidth 0 dtransform % clw=38(&) dxfm=55(7)
0(&7)$
%dup mul exch dup mul add sqrt 1 ge % mul=108 sqrt=355 ge=74 add=1 exch=62
(8l>8l)$ add sqrt 1 ge
{28 .75 b -28 .75 b}
%if grestore}def % grestore=77(M) if=84(T) def=51(3)<33>
(TM)$
}
%(3)$
%setlinewidth % slw=155<9B>
%translate % trsl8=173<AD>
<339BAD>$ b

```

# Postscript ~~172~~ 169

Same program using binary token strings.

```
/.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
0 6 200 20 2/b{<4E388B88>$ 0 0 0 12 0 0<6BAD63A7>$
0(&78l>8l)$ add sqrt 1 ge{28 .75 b -28 .75 b}(TM)$}<339BAD>$
b

```

# Answer
> 1 votes
# CoffeeScript (using Canvas) (289 bytes)

The following creates branches until the pixel width is less than 1px. The width and height of the image created is 500px. To see the virtual image that the program draws, add `document.body.appendChild(c)` to the last line of the code.

```
c=document.createElement 'canvas'
c.width=c.height=500
t=c.getContext '2d'
m=Math
b=m.PI/8
f=(w,l,x,y,a)->
    t.beginPath()
    t.moveTo x,y
    X=x+m.cos(a)*l
    Y=y+m.sin(a)*l
    t.lineWidth=w
    t.lineTo X,Y
    t.stroke()
    if w >= 1
        f w*3/4,l*3/4,X,Y,a+b
        f w*3/4,l*3/4,X,Y,a-b
f 10,90,250,0,m.PI/2

```

---
Tags: code-golf, graphical-output, fractal
---


title: The centers of a triangle

text:
# Question
Title: The centers of a triangle
Circles and squares have a single, definite center point. However, the notion of the center of a triangle has long been discussed. Four different centers were known to the Ancient Greeks:

* Incenter: The intersection of the angle bisectors of the triangle
* Centroid: The intersection of the lines from each vertex of the triangle to the middle of its opposite side
* Circumcenter: The intersection of the perpendicular bisectors of the sides
* Orthocenter: The intersection of the altitudes of the triangle

Euler later proved that the centroid, circumcenter and orthocenter are collinear in any triangle. The line that these three points are on in a triangle is called the Euler Line. It is defined for every triangle except an equilateral triangle, where all the points coincide.

Your challenge is to create the shortest program or function that, when given two inputs, outputs a specific center or the Euler Line of the triangle. The first specifies the coordinates of each vertex of a triangle. The second is an integer from 1 to 5, determining what to output.

```
1 - Incenter
2 - Centroid
3 - Circumcenter
4 - Orthocenter
5 - Equation of Euler Line
    (if the Euler Line is vertical, output the `x` value of the line
      (e.g. output `5` if the equation of the line is `x = 5`))

```

You may assume that the given vertices will never be collinear, and that they will always be integer coordinates (this also excludes the possibility of having an equilateral triangle as an input, as per @R.Kap's comment).

The input array should be a valid nested array in your language, and input should be in any reasonable format. Any float values should be displayed to at least 3 decimal places, but no less. An outputted point should be a valid array in your language, matching with the input format.

---

Test cases:

```
Input: [(-2, 0), (1, 0), (0, 1)] 1
Output: (-0.089, 0.451)

Input: [(-2, 0), (1, 0), (0, 1)] 2
Output: (-0.333, 0.333)

Input: [(-2, 0), (1, 0), (0, 1)] 3
Output: (-0.5, -0.5)

Input: [(-2, 0), (1, 0), (0, 1)] 4
Output: (0, 2)

Input: [(-2, 0), (1, 0), (0, 1)] 5
Output: 5x + 2

```

---

**Clarification:** The input can either be from stdin, either space or new-line separated, or as the arguments to a function. The output, however, must be written to stdout.

# Answer
# Python - 908 870

Newlines were added to reduce scrolling. This could probably be golfed further.

```
from math import*;t=eval(input());p=int(input())-1;
r=[];A,B,C=t[0],t[1],t[2];
a,b,c=hypot(B[0]-C[0],B[1]-C[1]),hypot(A[0]-C[0],A[1]-C[1]),hypot(A[0]-B[0],A[1]-B[1]);
r.append(((a*A[0]+b*B[0]+c*C[0])/(a+b+c),(a*A[1]+b*B[1]+c*C[1])/(a+b+c)));
r.append(((A[0]+B[0]+C[0])/3,(A[1]+B[1]+C[1])/3));d,e,f=(0,0),(B[0]-A[0],B[1]-A[1]),(C[0]-A[0],C[1]-A[1]);g=2*(e[0]*f[1]-e[1]*f[0]);
r.append(((f[1]*(e[0]**2+e[1]**2)-e[1]*(f[0]**2+f[1]**2))/g+A[0],(e[0]*(f[0]**2+f[1]**2)- f[0]*(e[0]**2+e[1]**2))/g+A[1]));
h=acos((b*b+c*c-a*a)/(2*b*c));i=acos((a*a+c*c-b*b)/(2*a*c));j=acos((a*a+b*b- c*c)/(2*a*b));k=cos(i)*cos(j);
l=cos(h)*cos(j);m=cos(h)*cos(i);r.append(((a*k*A[0]+b*l*B[0]+c*m*C[0])/(a*k+b*l+c*m),(a*k*A[1]+b*l*B[1]+c*m*C[1])/(a*k+b*l+c*m)));
n,o=r[1][0]-r[2][0],r[1][1]-r[2][1];q=r[1][1]-o/n*r[1][0]if n!=0 else 0;
r.append(r[1]if a==b==c else("x="+str(r[1][0])if n==0 else"".join([str(o/n),"x+(",str(q),")"])));print(r[p])

```

Test cases (annotated):

```
Input: [(-2, 0), (1, 0), (0, 1)]
1
Output: (-0.08907279243665268, 0.45110872103880023) --> More digits than in question

Input: [(-2, 0), (1, 0), (0, 1)]
2
Output: (-0.3333333333333333, 0.3333333333333333) --> More digits than in question

Input: [(-2, 0), (1, 0), (0, 1)]
3
Output: (-0.5, -0.5)

Input: [(-2, 0), (1, 0), (0, 1)]
4
Output: (-1.1702778228588997e-16, 1.9999999999999984) --> More digits than shown in question

Input: [(-2, 0), (1, 0), (0, 1)]
5
Output: 4.999999999999999x+(1.9999999999999996) --> More digits than in question

```

As you can see, there are possibly errors caused by using floating point.

---

**Further golfing:**

Based on suggestions in the comments below, I've managed to make this smaller.

```
from math import*;I=input;t=eval(I());p=int(I())-1;r=[];A,B,C=t[0],t[1],t[2];R,H,D,S,T=r.append,hypot,cos,acos,str;a,b,c=H(B[0]-C[0],B[1]-C[1]),H(A[0]-C[0],A[1]-C[1]),H(A[0]-B[0],A[1]-B[1]);R(((a*A[0]+b*B[0]+c*C[0])/(a+b+c),(a*A[1]+b*B[1]+c*C[1])/(a+b+c)));R(((A[0]+B[0]+C[0])/3,(A[1]+B[1]+C[1])/3));d,e,f=(0,0),(B[0]-A[0],B[1]-A[1]),(C[0]-A[0],C[1]-A[1]);g=2*(e[0]*f[1]-e[1]*f[0]);R(((f[1]*(e[0]**2+e[1]**2)-e[1]*(f[0]**2+f[1]**2))/g+A[0],(e[0]*(f[0]**2+f[1]**2)-f[0]*(e[0]**2+e[1]**2))/g+A[1]));h=S((b*b+c*c-a*a)/(2*b*c));i=S((a*a+c*c-b*b)/(2*a*c));j=S((a*a+b*b-c*c)/(2*a*b));k=D(i)*D(j);l=D(h)*D(j);m=D(h)*D(i);R(((a*k*A[0]+b*l*B[0]+c*m*C[0])/(a*k+b*l+c*m),(a*k*A[1]+b*l*B[1]+c*m*C[1])/(a*k+b*l+c*m)));n,o=r[1][0]-r[2][0],r[1][1]-r[2][1];q=r[1][1]-o/n*r[1][0]if n!=0else 0;R(r[1]if a==b==c else("x="+T(r[1][0])if n==0else"".join([T(o/n),"x+(",T(q),")"])));print(r[p])

```
> 2 votes

# Answer
## AutoHotkey - 731

```
f(z, r:=1){
static 1:="i",2:="m",3:="c",4:="o"
r := %r%,mx :=(z.1.1+z.2.1+z.3.1)/3,my:=(z.1.2+z.2.2+z.3.2)/3
s:=(c:=sqrt((z.2.1-z.1.1)**2+(z.2.2-z.1.2)**2))+(a:=sqrt((z.3.1-z.2.1)**2+(z.3.2-z.2.2)**2))+(b:=sqrt((z.3.1-z.1.1)**2+(z.3.2-z.1.2)**2))
ix:=(a*z.1.1+b*z.2.1+c*z.3.1)/s,iy:=(a*z.1.2+b*z.2.2+c*z.3.2)/s
midx_a:=(z.3.1+z.2.1)/2,midy_a:=(z.3.2+z.2.2)/2,m:=-1*(z.3.1-z.2.1)/(z.3.2-z.2.2),cc_a:=midy_a-(m*midx_a)
midx_b:=(z.3.1+z.1.1)/2,midy_b:=(z.3.2+z.1.2)/2,n:=-1*(z.3.1-z.1.1)/(z.3.2-z.1.2),cc_b:=midy_b-(n*midx_b)
cx:=(cc_b-cc_a)/(m-n),cy:=cc_a+(m*cx),oc_a:=z.1.2-(m*z.1.1),oc_b:=z.2.2-(n*z.2.1),ox:=(oc_a-oc_b)/(n-m),oy:=oc_a+(m*ox)
if r in m,i,c,o
return [%r%x, %r%y]
else return "y=" (m:=(oy-cy)/(ox-cx)) "x+" oy-m*ox
}

```

The function can be more minified (to about 600 chars OR less) by shortening the variable names like midx\_a, midx\_b and so.

### Calling the function

```
d:=f([[-2, 0], [1, 0], [0, 1]], 1)
for k,v in d
    msgbox % k "`n" v

```
> 2 votes

# Answer
# Python 3.5, ~~851~~ 772 bytes:

```
def H(z,a,b,l):c=complex;T=lambda A,B:abs(c(*A)-c(*B));d=T(z,a);e=T(z,b);f=T(a,b);g=[((a[0]+b[0])/2,(a[1]+b[1])/2)for a,b in[[a,b],[z,a],[b,z]]];E=(z[0]+a[0]+b[0])/3;F=(z[1]+a[1]+b[1])/3;m=lambda f:[(a,0)if(b[1][0]-b[0][0])==0else(a,-1/((b[1][1]-b[0][1])/(b[1][0]-b[0][0])))if(b[1][1]-b[0][1])else''for a,b in zip(f,[[a,b],[z,a],[b,z]])];i=[u for u in m(g)if u!=''];C=i[0][1];D=i[0][0][1]-(C*i[0][0][0]);A=i[1][1];B=i[1][0][1]-(A*i[1][0][0]);G=(B-D)/(C-A);H=C*G+D;j=[u for u in m([z,b,a])if u!=''];C=j[0][1];D=j[0][0][1]-(C*j[0][0][0]);A=j[1][1];B=j[1][0][1]-(A*j[1][0][0]);I=(B-D)/(C-A);J=C*I+D;K,L=[((d*b[o])+(e*a[o])+(f*z[o]))/sum([d,e,f])for o in[0,1]];a=(H-J)/(G-I)if(G-I)else'';b=H-(a*G)if a!=''else G;print(['',(K,L),(E,F),(G,H),(I,J),[b,'%sx+%s'%(a,b)][a!='']][l])

```

Takes **input** as a sequence of comma separated coordinates followed by an integer conveying what to output. For instance, if the input coordinates are `(1,0),(2,1),(1,4)` and you want the orthocenter of the triangle corresponding to those coordinates you would simply call the function like so:

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

```

**Outputs** in the format of a tuple if a specific point is needed, in the format of a string with the equation in the form `y=mx+b` if the Euler line is needed and the line is *not* vertical, or simply the `x` value of the line if the Euler line is needed but the line *is* vertical.

So, using the triangle with vertices `(1,0),(2,1),(1,4)`, the outputs would be:

```
1. Incenter: (1.4663911961440428, 1.125967951102358)
2. Centroid: (1.3333333333333333, 1.6666666666666667)
3. Circumcenter: (0.0, 2.0)
4. Orthocenter: (4.0, 1.0)
5. Euler Line: -0.25x+2.0

```

I will try to golf this more over time where and when I can.

Try It Online! (Ideone)
> 1 votes

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


title: Find the number I/O shortest algorithm

text:
# Question
Title: Find the number I/O shortest algorithm
Find the shortest function/algorithm to translate these numbers to the ones after the dash:

```
0 - 0
1 - 10
2 - 20
3 - 30
4 - 40
5 - 50
6 - 60
7 - 70
8 - 80
9 - 90
10 - 100
11 - 115
12 - 130
13 - 150
14 - 175
15 - 200
16 - 230
17 - 260
18 - 300
19 - 350
20 - 400

```

Every integer higher than 20 is calculated by subtracting 10, calculating the corresponding number like done above and then multiplying that by 4.

Some examples (input will be between \[\]):

```
[10] -> 100
[17] -> 260
[21] -> 4*115 -> 460
[32] -> 4*[22] -> 4*(4*130)) -> 2080

```

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

```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

```

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

```
f=n=>n>15?f(n-5)*2:n<11?n*10:f(n-1)+5*"22344"[n-11]

```

Much simpler now that I'm also using @xnor's observation.
> 4 votes

# Answer
# Python 2, 57 bytes

```
lambda n:5*[2*n,4**(n/10-1)*ord('♥♥♥♥#(.4<F'[n%10])][n>9]

```

Replace the four hearts with the ASCII characters 20 (`^T`), 23 (`^W`), 26 (`^Z`), and 30 (`^^`).
> 4 votes

# Answer
## Python 3, 45 bytes

```
lambda n:[16*n,b'(.4<F'[n%5]<<n//5][n>9]//8*5

```

Sticking to printable ASCII and int output. Uses that the values double every 5 steps, which can be computed with a bit shift.

```
10 - 100
11 - 115
12 - 130
13 - 150
14 - 175

15 - 200
16 - 230
17 - 260
18 - 300
19 - 350

```

So, for `n>9`, the output is `[20,23,26,30,35][n%5]<<n/5-2`. These values are doubled and packed in a printable ASCII bytearray. The `-2` in the bit shift is pushed to the outside to avoid a negative shift error when `n<=9` -- this is an ugly hack that can probably be handled better.
> 4 votes

# Answer
# Java, ~~93~~ 89 bytes

```
int f(int n){String x="!$(-28>FP";return n<11?n*10:n<20?(x.charAt(n-11)-10)*5:f(n-10)*4;}

```

A translation of the answer in Python combined with the answer in C++, also inspired by this answer in Python.

## Full program:

```
public class Q80271 {
    int f(int n){String x="!$(-28>FP";return n<11?n*10:n<20?(x.charAt(n-11)-10)*5:f(n-10)*4;}
    public static void main(String args[]){
        int[] testcases = new int[]{
            0,1,2,3,4,5,6,7,8,9,
            10,11,12,13,14,15,16,17,18,19,
            20,21,32
        };
        for(int i=0;i<testcases.length;i++){
            System.out.println(new Q80271().f(testcases[i]));
        }
    }
}

```

## Output:

```
0
10
20
30
40
50
60
70
80
90
100
115
130
150
175
200
230
260
300
350
400
460
2080

```
> 3 votes

# Answer
# Pyth, ~~47~~ 46 bytes

1 byte deletion inspired by Python's deletion of the final item in the lookup table.

```
J9L?gb20*4y-bT+?>bT*5@.u+NYj6045983J1-bhT0*Tby

```

Test suite.

### Principle

The lookup table I built is `[1, 2, 3, 3, 4, 4, 6, 8]`.

If we start from `1`, and then add cumulatively that table:

```
1                   = 1
1+1                 = 2
1+1+2               = 4
1+1+2+3             = 7
1+1+2+3+3           = 10
1+1+2+3+3+4         = 14
1+1+2+3+3+4+4       = 18
1+1+2+3+3+4+4+6     = 24
1+1+2+3+3+4+4+6+8   = 32

```

## Previous 53-byte solution:

```
L?tb+ytbeSmlf!%ydTSydStb1L?>b20*4'-bT+?>bT*5y-bT0*Tb'

```

This needs to be golf... very further. Maybe it would cost less to build a lookup table directly.

Test suite.

### Principle

If we subtract ten times the first number from the second number:

```
115-110 = 5   = 5*1
130-120 = 10  = 5*2
150-130 = 20  = 5*4
175-140 = 35  = 5*7
200-150 = 50  = 5*10
230-160 = 70  = 5*14
260-170 = 90  = 5*18
300-180 = 120 = 5*24
350-190 = 160 = 5*32
400-200 = 200 = 5*40

```

It corresponds with A120679: `1,2,4,7,10,14,18,24,32,40,...`
> 2 votes

# Answer
## PHP, 101 bytes

```
function f($i){$a=array(23,26,30,35,40,46,52,60,70);return $i<11?$i*10:$i<20?$a[$i-11]*5:f($i-10)*4;}

```

Huzzah for nested conditional operator!
> 2 votes

# Answer
# Jelly, ~~32~~ ~~31~~ ~~30~~ 22 bytes

```
ị“.4<F(”Oæ«Ḥ:¥:⁴×µ×>?⁵

```

Uses the astute observation from @xnor's answer, which saved 8 bytes.

Try it online! or verify all test cases.

### How it works

```
ị“.4<F(”Oæ«Ḥ:¥:⁴×µ×>?⁵  Main link. Argument: n (integer)

                   >?⁵  If n is greater than 10:
                 µ   ⁵    Execute the chain to µ's left dyadically, with arguments
                          n (left) and 10 (right).
 “.4<F(”                    Yield the string of code points [46, 52, 60, 70, 40].
ị                           Retrieve the character at index n.
                            Indexing is modular and 1-based, so 1, 6, 11, etc. map
                            to the first character, 0, 5, 10, etc. to the last.
        O                   Ordinal; yield the code point of the character.
             ¥              Combine the two links to the left into a dyadic chain.
           Ḥ                  Yield 2n.
            :                 Divide 2n by 10, flooring the result.
                            This yields n : 5 (integer division).
         æ«                 Shift the code point n : 5 bits to the left.
              :⁴            Divide the result by 16.
                ×           Multiply the result by 10.
                        Else:
                  ×  ⁵    Multiply n by 10.

```
> 2 votes

# Answer
# Python, 81 bytes

```
f=lambda n:n>19and 4*f(n-10)or n>10and[23,26,30,35,40,46,52,60,70][n-11]*5or 10*n

```
> 1 votes

# Answer
# C++11, ~~104~~ ~~95~~ 91 bytes

```
int f(int n){int x={23,26,30,35,40,46,52,60,70};return n<11?n*10:n<20?x[n-11]*5:f(n-10)*4;}

```

Simple lookup table and ternary operator fun.

\[edit\]Thanks! \[edit2\]I'm feeling extra stoopid today. Thanks again!
> 1 votes

# Answer
# Java, 62 bytes

```
i->' '<i?l(i-10)*4:10*i+")*+-037;AIQ".charAt(i>9?i-10:0)%41*5

```
> 1 votes

# Answer
# Javascript ES6, ~~104 103 100 97~~ 93 bytes

```
 h=a=>{return a<11?a*10:a<20?a*10+c[a-11][1/2,1,2,7/2,5,7,9,12,16]*10:4*h(a-10);},u=p=>h(p[0])

```

usage: call `u` with the input **enclosed in brackets like the OP said.** Will golf later.

# 84 bytes if input is not enclosed in brackets and `h()` is called directly

thanks to kenny lau -6 bytes
> 0 votes

# Answer
# Jelly, 42 bytes

```
7568b3+\+\
_⁵ị¢×5+×⁵$
Çµ_⁵ß4×µ20>$?×⁵$>⁵$?

```

Try it online!

Test suite.

Uses the same principle as my answer in Pyth, just that the array is further reduced to `[1, 1, 0, 1, 0, 2, 2]`, which can generate `[1, 2, 3, 3, 4, 4, 6, 8]`, which can generate `[1, 2, 4, 7, 10, 14, 18, 24, 32]`.
> 0 votes

# Answer
## Haskell, ~~71~~ 66 bytes

```
h n|n<11=n*10|n<20=sum$5<$['.'.."DGKPU[ais"!!(n-11)]|1<2=4*h(n-10)

```

Usage example: `h 32` -\> `2080`.

The Haskell version of the algorithm found in many other answers. The results in the middle part for the numbers `11..19` are encoded as strings of consecutive ASCII characters:

```
11:   from . to D  (23 chars)
12:   from . to G  (26 chars)
13:   from . to K  (30 chars)
...

```

Every character in the string is mapped to a 5 and summed up.

Edit: @Lynn helped saving 4 bytes. Thanks!
> 0 votes

# Answer
# Julia 0.4, ~~49~~ 42 bytes

```
n->n>9?5Int("(.4<F"[n%5+1])*2^(n÷5)/8:10n

```

Uses the astute observation from @xnor's answer, which saved 7 bytes. Try it online!

---

# Julia 0.3, 38 bytes

```
n->2.5max("(.4<F"[n%5+1]<<(n÷5-2),4n)

```

This requires a call to `Int` in Julia 0.4, which makes it longer than the other approach.
> 0 votes

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


title: Security by Post-It

text:
# Question
Title: Security by Post-It
As you may know, hackers are everywhere and they want to hack everything. You were asked to make password requirements which will stop any hacker. The problem is, that your boss has heard that paying for LOC is evil and he pays you $1800 - $0.03 * characters inserted per month to make you write simplest thing which possibly could work. So, you have to use small number of characters (hopefully very small), or otherwise forget about cash. Also, your boss doesn't care what language you will use.

The requirements for good passwords are similar to those in mentioned article, except the dictionary based requirements were removed to avoid making solution depend on external files, you don't have to check for letters being rearranged (Hard to understand what it actually means), last rule is removed (What is 3/4?) and it doesn't check old passwords.

The exact requirements after removing certain requirements from linked article are:

* have at least 8 character(s)!
* not be longer than 12 characters!
* have upper and lower case characters!
* have no more than 8 upper-case letter(s)!
* have no more than 8 lower-case letter(s)!
* have at least 2 letter(s)!
* have a leading letter!
* have at least 1 digit(s)!
* not be your username!
* not be your username backwards!
* not contain your username!
* not contain your username backwards!
* have no more than 1 pair(s) of repeating characters!
* not have 3 *occurences* of the same character!
* not contain *carat* (^)
* not contain space
* not contain =
* not *conatain* &
* not contain #
* not contain ,
* not *conatain* ;
* not contain "
* not contain \>
* not contain \<
* not contain \[
* not contain |
* not contain )

All misspellings on this list were left as is.

```
$ ./checkpass
Username: John
Password: L!]E2m69
OK.

$ ./checkpass
Username: John
Password: JohnnhoJ12
Nope.

$ ./checkpass
Username: JOE.smith
Password: JOE!smith123
OK.

```

The shortest code wins money (sent as JPG file). It has to show "Username: " and "Password: " prompts and reply with exact message.

# Answer
## Perl, 203 194 189 193 chars

Here's my Perl take on the problem:

```
print"Username: ";chop($u=<>);$n=reverse$u;print"Password: ";$_=<>;
say/^\pL.{7,11}$/*/\d/*/[A-Z]/*9>y/A-Z//&y/a-z//<9*/[a-z]/*
!/[" #,;->^&[|)]|(.)(.*\1.*\1|\1.*(.)\3)|\Q$u\E|\Q$n/?"OK.":"Nope."

```

The regexes check, in order, that the password:

* starts with a letter, has eight to twelve characters
* contains a digit
* contains an uppercase letter
* has eight or fewer uppercase letters
* has eight or fewer lowercase letters
* contains a lowercase letter
* does not contain any of the forbidden punctuation marks, three occurrences of any character, more than one occurrence of a doubled character, the username, or the username reversed.

(Thanks to Peter Taylor for pointing out a bug in the 189-char version.)
> 8 votes

# Answer
### Ruby, 270 characters

```
$><<"Username: ";u=gets.chop
$><<"Password: ";gets
puts ('^.{8,12}$+\p{Lower}+\p{Upper}+^(\p{Alpha}.*){2}+\d+(\p{Lower}.*){9}+(\p{Upper}.*){9}+(.)\1.*(.)\2+(.).*\1.*\1+[ ^=&#,;"<>\[|)]+'+u+?++u.reverse).split(?+).map{|r|/#{r}/=~$_??A:?B}*""=="AAAAABBBBBBB"?"OK.":"Nope."

```

A ruby implementation build on twelve regular expressions. Each expression is either a positive match (first five) or a negative one (latter seven). As a restriction the username may only contain letters or digits.

Positive regular expression matches:

* `/^.{8,12}$/`: have at least 8 character(s)!, not be longer than 12 characters!
* `/\p{Lower}/` and `/\p{Upper}/`: have upper and lower case characters!
* `/^(\p{Alpha}.*){2}/`: have at least 2 letter(s)!, have a leading letter!
* `/\d/`: have at least 1 digit(s)!

Negative regular expression matches:

* `/(\p{Lower}.*){9}/`: have no more than 8 lower-case letter(s)!
* `/(\p{Upper}.*){9}/`: have no more than 8 upper-case letter(s)!
* `/(.)\1.*(.)\2/`: have no more than 1 pair(s) of repeating characters!
* `/(.).*\1.*\1/`: not have 3 occurences of the same character!
* `/[ ^=&#,;"<>\[|)]/`: not contain caret, space, =, &, #, ,, ;, ", \>, \<, \[, |, )
* `/#{u}/`: not be your username!, not contain your username!
* `/#{u.reverse}/`: not be your username backwards!, not contain your username backwards!
> 5 votes

# Answer
## Python 3, 291 bytes/characters

```
from re import*
n,p=map(input,["Username: ","Password: "])
c,U,L=lambda x:len(split("[%s]"%x,p)),"A-Z","a-z"
print(["OK.","Nope."][any([8>len(p)>12,2>c(U)>9,2>c(L)>9,3>c(U+L),match(U+L,p),2>c("0-9"),n in p,n[::-1]in p,any(c(x)>3 for x in p),len(findall("(.)\\1",p))>1,c(' ^=&#,;"><[|)')>1])])

```

More nicely formatted and commented:

```
# import all elements from the regular expression module
from re import *

# Get the two lines of user input (username `n`, password `p`):
n, p = map(input, ["Username: ","Password: "])

# Assign some internally useful shortcuts (uppercase letters `U`, lowercase letters `L`):
# `c(x)` counts the occurrences of pattern `x` in the password `p` plus 1
c, U, L = lambda x: len(split("[%s]" % x, p)), "A-Z", "a-z"

# Print the test result: `"OK."` if the `any(...)` function returned `False`, else `"Nope."`.
# The `any(...)` combines the result of all enclosed checks and returns `True` if at least
# one of the checks failed (returned `True`).
print(["OK.", "Nope."][any([                                # vvv--- CHECKS: ---vvv
                             8>len(p)>12,                   # password length 8-12
                             2>c(U)>9,                      # 1-8 uppercase letters
                             2>c(L)>9,                      # 1-8 lowercase letters
                             3>c(U+L),                      # at least 2 letters
                             match(U+L,p),                  # starts with a letter
                             2>c("0-9"),                    # at least 1 digit
                             n in p,                        # username is not (in) the pw.
                             n[::-1]in p,                   # reversed name not (in) the pw.
                             any(c(x)>3 for x in p),        # at most 3 same characters
                             len(findall("(.)\\1",p))>1,    # at most 1 pair (e.g. "AA")
                             c(' ^=&#,;"><[|)')>1])         # does not contain special char.
                           ])

```

You can find this solution on ideone.com, but the output looks a bit ugly because it does not show the predefined input or even line breaks there. Also, the username-password combination `"JOE.smith"`-`"JOE!smith123"` is currently entered as fixed input data.
I added a breakdown of all the checks as debug output though.
> 1 votes

---
Tags: code-golf
---


title: Real-time string matching

text:
# Question
Title: Real-time string matching
**Task**

The task is to golf a real-time exact string matching algorithm of your choice.

**Input**

Two lines of text supplied on standard input, separated by a new line. The first line contains the "pattern" and will simply be an ASCII string drawn from the letters `a-z`.

The second line contains the longer "text" and will also simply be an ASCII string drawn from the letters `a-z`.

**Output**

A list of indices of where the exact matches occur. You should output the position of the start of each match that occurs.

**Specification**

Your algorithm can spend linear time preprocessing the pattern. It must then read the text from left to right and take *constant time* for every single character in the text and output any new match as soon as it occurs. Matches can of course overlap each other.

**Algorithm**

There are many real-time exact matching algorithms. One is mentioned on the wiki for KMP for example. You can use any one you like but you must always output the right answer.

I will keep a per language leader table so that those who prefer popular languages can also win in their own way. Please explain which algorithm you have implemented.

**Real-time**

It seems there has been a lot of confusion over what real-time means. It doesn't simply mean linear time. So standard KMP is *not* real-time. The link in the question explicitly points to a part of the wiki page for KMP about a real-time variant of KMP. Neither is Boyer-Moore-Galil real-time. This cstheory question/answer discusses the issue or one can just google "real-time exact matching" or similar terms.

# Answer
# Python 2, 495 bytes

This one is a real-time KMP, which is a lot shorter and only slightly slower than the BMG algorithm (which is usually sublinear). Call with `K(pattern, text)`; output is identical to the BMG algorithm.

```
L,R,o=len,range,lambda x:ord(x)-97
def K(P,T):
 M,N=L(P),L(T);Z=[0]*M;Z[0]=M;r=l=0
 for k in R(1,l):
    if k>r:
     n=0
     while n+k<l<P[n]==P[n+k]:n+=1
     Z[k]=n
     if n>0:l,r=k,k+n-1
    else:
     p,_=k-l,r-k+1
     if Z[p]<_:Z[k]=Z[p]
     else:
        i=r+1
        while i<M<P[i]==P[i-k]:i+=1
        Z[k],l,r=i-k,k,i-1
 F=[[0]*26]*M
 for j in R(M-1,0,-1):z=Z[j];i,x=j+z-1,P[z+1];F[i][o(x)]=z
 s=m=0
 while s+m<N:
    c=T[s+m]
    if c==P[m]:
     m+=1
     if m==M:print s,;s+=1;m-=1
    else:
     if m==0:s+=1
     else:f=F[m][o(c)];s+=m-f;m=f

```
> 2 votes

# Answer
# Python 2, 937 bytes

This ain't short, by any means, but it (a) works, (b) satisfies all the requirements, and (c) is golfed as much as I can possibly make it.

```
L,r,t,o,e,w=len,range,26,lambda x:ord(x)-97,enumerate,max
def m(s,M,i,j,c=0):
 while i<M-c>j<s[i+c]==s[j+c]:c+=1
 return[c,M-i][i==j]
def Z(s):
 M=L(s)
 if M<2:return[[],[1]][M]
 z=[0]*M;z[0:2]=M,m(s,M,0,1)
 for i in r(2,1+z[1]):z[i]=z[1]-i+1
 l=h=0
 for i in r(2+z[1],M):
    if i<=h:k=i-l;b,a=z[k],h-i+1;exec["z[i]=b+m(s,M,a,h+1);l,h=i,i+z[i]-1","z[i]=b","z[i]=min(b,M-i);l,h=i,i+z[i]-1"][cmp(a,b)]
    else:
     z[i]=m(s,M,0,i)
     if z[i]>0:l,h=i,i+z[i]-1
 return z
def S(P,T):
 M,N=L(P),L(T)
 if not 0<M<N:return
 R,a=[[-1]]*t,[-1]*t
 for i,c in e(P):
    a[o(c)]=i
    for j in r(t):R[j]+=a[j],
 if M<=0:R=[[]]*t
 n,F,z,l=Z(P[::-1])[::-1],[0]*M,Z(P),0;G=[[-1,M-n[j]][n[j]>0]for j in r(M-1)]
 for i,v in e(z[::-1]):l=[l,w(v,l)][v==i+1];F[~i]=l
 k,p=M-1,-1
 while k<N:
    i,h=M-1,k
    while 0<=i<[]>h>p<P[i]==T[h]:i-=1;h-=1
    if i<0 or h==p:print-~k-M,;k+=[1,M-F[1]][M>1]
    else:c,q=i-R[o(T[h])][i],i+1;s=w(c,q==M or M-[G,F][G[q]<0][q]);p=[p,k][s>=q];k+=s

```

This is an implementation of the Boyer-Moore-Galil algorithm. Pretty straightforward - call with `S(pattern,text)`; the other two functions are used in preprocessing. Indeed, everything but the last 5 lines is preprocessing.

An example run, which took about a second:

```
>>> a = 'a'*1000
>>> b = 'a'*1999 + 'b'
>>> S(a,b)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999

```
> 1 votes

# Answer
## KMP, Python 2(213 bytes)

```
R=raw_input
E=enumerate
p=R()
t=R()
f=[-1]*((len(p)+1))
j=-1
for i,c in E(p):
 while j+1 and p[j]!=c:j=f[j]
 f[i+1]=j=j+1
j=-1
for i,c in E(t):
 while j+1 and p[j]!=c:j=f[j]
 j+=1
 if j==len(p):print i+1-j;j=f[j]

```

Ungolfed version. The first loop is to build up the KMP automata. The second loop is walking on the automata. They share nearly the same pattern but abstracting them out will cost more bytes so for a code golf I'd rather duplicate this logic. Similar implementation is actually widely used in programing contests.

```
pattern = raw_input()
text = raw_input()

fail = [-1] * (len(pattern) + 1)
j = -1
for i, c in enumerate(pattern):
    while j >= 0 and pattern[j] != c:
        j = fail[j]
    j += 1
    fail[i + 1] = j

j = -1
for i, c in enumerate(text):
    while j >= 0 and pattern[j] != c:
        j = fail[j]
    j += 1
    if j == len(pattern):
        print i + 1 - j
        j = fail[j]

```
> 1 votes

# Answer
## Realtime KMP, Python 2(167 bytes)

```
R=raw_input
E=enumerate
P=R()
T=R()
F=[{}]
for i,c in E(P):j=F[i].get(c,0);F+=[dict(F[j])];F[i][c]=i+1
j=0
for i,c in E(T):
 j=F[j].get(c,0)
 if j==len(P):print i+1-j

```

In normal KMP, we simulate the automaton behavior by using a fail function. In this realtime KMP, the full automaton is constructed so that in the matching phrase it can process each character in realtime(constant time).

The preprocessing time and space complexity is O(n m), where m is the alphabet size and n is the length of pattern string. However, in my tests, the actual size of transition table is always less than 2n so maybe we can prove that the time and space complexity is O(n).

Ungolfed version

```
pattern = raw_input()
text = raw_input()

# transitions[i][c] points to the next state walking from state i by c.
# Transition that point to staet 0 are not stored.
# So use transitions[i].get(c, 0) instead of transitions[i][c]
transitions = [{}]
for i, c in enumerate(pattern):
    j = transitions[i].get(c, 0)
    transitions.append(transitions[j].copy())
    # Before this assignment, transitions[i] served as the fail function
    transitions[i][c] = i + 1

j = 0
for i, c in enumerate(text):
    j = transitions[j].get(c, 0)
    if j == len(pattern):
        print i + 1 - j

```
> 1 votes

# Answer
## Q, 146 Bytes

```
W:S:u:"";n:0;p:{$[n<#x;0;x~(#x)#W;#x;0]};f:{{|/p'x}'((1_)\x#W),\:/:u};F:{S::x 1;W::*x;n::#W;u::?W;T:(f'!1+n),\:0;(&n=T\[0;u?S])-n-1}

```

**Test**

```
F"
 ABCDABD
 ABCdABCDABgABCDABCDABDEABCDABzABCDABCDABDE"
```

generates 15 and 34

**Notes**

Not restricted to alphabet (support any ascii char, and is case-sensitive).

Not uses any of the specific operations defined by Q over strings -\> works on strings as sequences (ops match, length, etc.)

Minimizes transition table joining all characters not in pattern as one unique character-class.

I can squeeze code a little. It's a first attempt to validate solution strategy

Visit any character of text exactly once, and for each input character there is a unique jump. So I assume that search fits as 'real time'

Table construction al state i and char c search for longest substring that ends at i and after appending c is a prefix of S. Construction is not optimized, so i don't know if its valid

Input format doesn't fit well with language. Passing two string arguments will save 16 Bytes

**Explanation**

global W represents pattern and S corresponds to text to search

`x:1_"\n "\:x` weird code to cope with input requirements (Q requires thtat multiline strings has non-first lines indented, so it must discard added space in front of every non-first line)

`n::#W` calculates W lenght and save as global n

`u::?W` calculates unique chars in W, and save as global u

`u?S` generates the characted-class for each char of S

Construct a transition table T with one row per unique character in W (plus one extra), and a column for each index in W (plus one extra). Extra row correspond to initial state, and extra column collects any char in S but not in W. This strategy minimizes table size

`p:{$[n<#x;0;x~(#x)#W;#x;0]}` is the function that search longest prefix

`f:{{|/p'x}'((1_)\x#W),\:/:u}` is the function that calculates a row x of T

```
T:(f'!1+n),\:0 applies f repeteadly to calculate each row, and adds value 0 to each row

```

Search text using transition table. `T\[0;u?S]` iterates over 0 (initial state) and each of the character class of S, using as a new value the value at transitition table T\[state\]\[charClass\]. Final states has value n, so we look for that value in the sequence of states and returns it adjusted (to indicate initial instead of final position of each match)
> 1 votes

# Answer
## Boyer-Moore, Perl (50)

Perl attempts to use Boyer-Moore naturally:

```
$s=<>;$g=<>;chomp$g;print"$-[0] "while$s=~m/($g)/g

```
> 0 votes

---
Tags: code-golf, string, restricted-complexity
---


title: Calculate the Numpad Taxicab

text:
# Question
Title: Calculate the Numpad Taxicab
*Credit goes where credit is due*

---

Given two digits, x, and y, calculate the shortest number of horizontal or vertical jumps to get from x to y on a standard numpad, e.g.

```
789
456
123
00

```

You can safely assume that all inputs will be 0-9, and you do not have to handle invalid inputs. The input *may* be the same number twice, which has a distance of 0.

IO can be in any reasonable format, and standard loopholes are forbidden. Shortest answer in bytes wins!

# Sample IO:

```
1, 4: 1
1, 8: 3
3, 7: 4
8, 2: 2
6, 1: 3
0, 9: 4
4, 4: 0
0, 4: 2

```

# Answer
> 3 votes
# Jelly, 11 bytes

```
o-1.’d3ạ/ḞS

```

Try it online! or verify all test cases.

### How it works

```
o-1.’d3ạ/ḞS  Main link. Argument: [a, b] (list of integers)

 -1.         Yield -1.5.
o            Take the logical OR of a and b with -1.5.
             This maps 0 to -1.5, and all other integers to themselves.
    ’        Decrement the results.
     d3      Divmod; compute quotient and remainder of each result divided by 3.
       ạ/    Reduce by absolute difference across columns.
         Ḟ   Floor; round all differences down to the nearest integer.
          S  Sum; add the rounded absolute differences.

```

# Answer
> 3 votes
# Python, 140 114 bytes

I am a first timer, so please help. Here's my code.

```
def f(x,y):x,y,k=x-1,y-1,abs;return x!=-1 and y!=-1 and k(y//3-x//3)+k(y%3-x%3) or k(y//3-x//3)+int(max(x,y)%3==2)

```

# Answer
> 2 votes
# Jelly, 13 bytes

```
+2$.¹?€d3ạ/SḞ

```

Try it online!

Port of my Pyth answer.

Test suite.

# Answer
> 2 votes
# JavaScript (ES6), 59

Unfortunately, no `divmod` in javascript. In fact, no integer `div`, and no `mod` either: the `%` is not exactly `mod`. But for once, the weird behaviour of `%` with negative numbers is useful.

```
(a,b,A=Math.abs)=>A(~(--a/3)-~(--b/3))+A(a%3-b%3)-(a*b%3<0)

```

**Test**

```
f=(a,b,A=Math.abs)=>A(~(--a/3)-~(--b/3))+A(a%3-b%3)-(a*b%3<0)

for(i=0;i<10;console.log(r),i++)
  for(r='',j=0;j<10;j++)
    r+=[i,j,f(i,j)]+' '
```

# Answer
> 1 votes
# Pyth, ~~22~~ ~~21~~ 19 bytes

FGITW.

```
L.D?b+2b.5 3ssaMCyM

```

Test suite.

Conversion table:

```
0: [0.0, 0.5]
1: [1, 0]
2: [1, 1]
3: [1, 2]
4: [2, 0]
5: [2, 1]
6: [2, 2]
7: [3, 0]
8: [3, 1]
9: [3, 2]

```

# Answer
> 1 votes
# Python 2, 61 bytes

```
lambda x,y:abs(x/-3-y/-3)+abs((x or 1.5)%-3-(y or 1.5)%-3)//1

```

Test it on Ideone.

### How it works

* **Vertical distance**

Integer division always round *down* to the nearest integer in Python, yielding the following results for the 10 possible dividends divided by **-3**.

```
 0  1  2  3  4  5  6  7  8  9
 0 -1 -1 -1 -2 -2 -2 -3 -3 -3

```

Thus, we can compute the vertical distance between **x** and **y** as `abs(x/-3-y/-3)`.
* **Horizontal distance**

For columns, we can avoid treating **0** as a special case by replacing it with **1.5**, thus placing it "between" the first and second column.

Modulus (`%`) always has the sign of the divisor in Python, yielding the following results for the 10 possible dividend modulo **-3**.

```
   0  1  2  3  4  5  6  7  8  9
-1.5 -2 -1  0 -2 -1  0 -2 -1  0

```

Thus, by rounding down (`//1`) the result of `abs((x or 1.5)%-3-(y or 1.5)%-3)`, we can compute the horizontal difference between **x** and **y**.

# Answer
> 1 votes
# Julia, 56 bytes

```
x->sum(abs(-([[divrem(t>0?t+2:.5,3)...]for t=x]...)))÷1

```

Try it online!

# Answer
> 0 votes
## Java ~~149~~ 160 chars

The obligatory: Because... you know... Java! Having fun with Java in under ~~150~~ 161 chars:

```
int d(int f,int t){if(f==t)return 0;if(Math.min(f,t)==0){int m=Math.max(f,t);return Math.min(d(1,m),d(2,m))+1;}return Math.abs(--t%3- --f%3)+Math.abs(t/3-f/3);}

```

Ungolfed into a class:

```
public class Q80357 {

    static int distance(int from, int to) {
        if (from == to)
            return 0;
        if (Math.min(from, to) == 0) {
            int max = Math.max(from, to);
            return Math.min(distance(1, max), distance(2, max)) + 1;
        }
        return Math.abs(--to % 3 - --from % 3) + Math.abs(to / 3 - from / 3);
    }
}

```

### How it works

First it catches the standard case where we don't have to move anywhere.

Now we can assume that both integers differ, thus only the smaller one can be 0. If this is the case we calculate the distance from key 1 and 2 to the other key. We will use the one with the shorter distance and add one step to get from 1 or 2 to 0.

If we don't want to go to/from zero we only have to move in the 3x3 grid. We can determine the column and row of the key by using mod or div respectively. Then we calculate the column and row distance and add them. This is the distance we need to get from one key to another.

I hope the explanation could be understood, feel free to golf :)

### Updates

Had to change it into an actual function as it uses recursion which isn't possible with lambdas :,(

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


title: Largest Distinctly Sum-Free Partition

text:
# Question
Title: Largest Distinctly Sum-Free Partition
related and inspired by -- Finding sum-free partitions

A set `A` is defined here as being *distinctly sum-free* if

* 1) it consists of at least three elements, `|A| ≥ 3`, and
* 2) its distinct self-sum `A + A = { x + y | x, y in A}` (with `x,y` distinct, i.e., `x≠y`) has no elements in common with `A`.

(Obsolete - do not use this going forward. Left here only because some answers may have used it. It does not match with the above conditions. *Alternatively, the equation `x + y = z` has no solution for `x,y,z ∈ A` (again with `x,y,z` distinct, i.e., `x≠y`, `x≠z`, `y≠z`).*)

For a simple example, `{1,3,5}` is distinctly sum-free, but `{1,3,4}` is not. `{1,3}` and `{3}` are also not, since they're not at least three elements.

The challenge here is to find the largest distinctly sum-free subset of the given input.

### Input

* An unordered set `A` of integers in any convenient format.
* The integers could be positive, negative, or zero, but can be assumed to fit in your language's native `[int]` datatype (or equivalent).
* The set is guaranteed to have only distinct elements (no multisets here).
* The set is not necessarily sorted.

### Output

* The largest subset of `A` (which could be `A` itself), that is distinctly sum-free. Output can be in any suitable format.
* If no such subset exists, output an empty set or other falsey value.
* If multiple subsets are tied for largest, output any or all of them.
* The subset does not necessarily need be sorted, or in the same order as the input. For example, for input `{1,3,5}` output `{5,1,3}` is acceptable.

### Additional Rules

### Examples

```
Input     -> Output (any or all)
{0}       -> {}
{1, 2, 3} -> {}
{1, 3, 5} -> {1, 3, 5}
{1, 2, 3, 4, 5} -> {1, 2, 5}  {1, 2, 4}  {1, 3, 5}  {2, 3, 4}  {2, 4, 5}  {3, 4, 5}
{-5, 4, 3, -2, 0} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-5, 4, 3, -2} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-17, 22, -5, 13, 200, -1, 1, 9} -> {-17, 22, -5, 13, 200, -1, 1}  {-17, 22, -5, 200, -1, 1, 9}  {-17, -5, 13, 200, -1, 1, 9}

```

# Answer
> 1 votes
# Jelly, 17 bytes

```
8BḊ+œc2S€f
ŒPÇÐḟṪ

```

Try it online! or verify all test cases.

# Answer
> 4 votes
# MATL, ~~47~~ 43 bytes

```
nW:qB!ts2#Sw2>)PZ)"1G@)XJ2XN!"@sJ@X-m~*]?J.

```

**Try it online!**

### Explanation

This uses two loops: an outer loop to generate all possible subsets, and an inner loop to take all pairs of elements and see if the sum equals any other element of the subset.

Subsets of at least 3 elements are tested in order of decreasing number of elements. The code stops as soon as a valid subset is found.

```
          % Take input implicitly
nW:q      % Generate [0 1 ... 2^n-1] where n is input length
B!        % Convert to binary. Gives a matrix. Each number corresponds to a column.
          % This will be used to select the elements of each subset
ts        % Duplicate. Sum of each column
2#S       % Sort. Output the sorted array and the indices of the sorting. Each index
          % corresponds to one possible subset
w2>       % Swap. Logical index of values that exceed 2. This is used to pick only
          % subsets of more than 2 elements
)         % Keeps only indices of subsets that have at least 3 elements
P         % Flip. This moves subsets with more elements to the front. As soon as a
          % subset fulfills the condition the outer loop will be exited, so we need
          % to start with the bigger subsets
Z)        % Index into columns of binary matrix. Each column is the binary pattern
          % defining a subset with at least 3 elements, starting with bigger subsets
"         % For each column. Each iteration corresponds to a subset
  1       %   Push 1
  G@)     %   Pick actual elements of each subset (logical index into input)
  XJ      %   Copy to clipboard J
  2XN!    %   All pairs of 2 elements from that subset. Each pair is a column
  "       %   For each column. Each iteration corresponds to a pair of elements
    @s    %     Sum of those two elements
    J@X-  %     Array with the other elements (obtained with set difference)
    m~    %     True if the sum of the two elemens is not a member of the array
    *     %     Multiply. Corresponds to logical AND
  ]       %   End for
  ?       %   If result is true: no sum of two elements equalled any element
    J     %     Push found subset (will be displayed implicitly)
    .     %     Exit loop
          %   End if implicitly
          % End for implicitly
          % Display stack implicitly

```

# Answer
> 3 votes
# Python, 137 bytes

A naïve approach. Loops over all subsets of the input containing at least 3 values, checking the property for each one. Returns `[]` when no result is found or `[S]` if at least one result is found (where `S` is some tuple).

```
from itertools import*
lambda a:[c for n in range(3,len(a)+1)for c in combinations(a,n)if all(x+y-z for(x,y,z)in permutations(c,3))][-1:]

```

# Answer
> 2 votes
# Ruby, 107 bytes

Input is an array. Collects one qualifying subset for each subset size from `3` to the input length, then returns the biggest one out of the ones found. Returns `nil` if no result is found.

Because of the conflicting spec, there are two solutions that currently have the same bytecount.

Using the first definition: (`{ x + y | x, y ∈ A } ∩ A = ∅`)

```
->s{((3..s.size).map{|i|s.combination(i).find{|e|e.combination(2).map{|a,b|a+b}&e==[]}}-[p])[-1]}

```

Using the second definition (`∀ x, y, z ∈ A: x + y ≠ z`)

```
->s{((3..s.size).map{|i|s.combination(i).find{|e|e.permutation(3).all?{|a,b,c|a+b!=c}}}-[p])[-1]}

```

# Answer
> 2 votes
### Javascript 246 ~~263~~

```
a=>([...Array(1<<(l=a.length))].map((x,i)=>i.toString(2)).filter(n=>/1.*1.*1/.test(n)).map(s=>('0'.repeat(l)+s).slice(-l).replace(/./g,(b,p)=>+b&&o.push(a[p]),o=[])&&o).filter(u=>u.every((x,i)=>!u.some((y,j)=>j-i&&u.some((z,k)=>k-j&&!(z-x-y))))))

```

So long :( ... But it was a nice coding ..(I think)

Less golfed:

```
f=a=>(
    [...Array(1<<(l=a.length))]
        .map((x,i)=>i.toString(2))
        .filter(n=>/1.*1.*1/.test(n))
        .map(s=>
            ('0'.repeat(l)+s).slice(-l).replace(/./g,
                (b,p)=>+b&&o.push(a[p])
            ,o=[])&&o
        )
        .filter(u=>
            u.every((x,i)=>
                !u.some((y,j)=>
                    j-i&&u.some((z,k)=>k-j&&!(z-x-y))
                )
            )
        )
)

document.body.innerHTML = JSON.stringify( f([1,2,3,4,5]), null, 1 );
```

# Answer
> 2 votes
# Mathematica - ~~89~~ ~~84~~ ~~83~~ ~~77~~ 76 bytes

*6 bytes saved thanks to @Sp3000*

Probably can be golfed a lot more, is there a shorter way to filter?

```
Select[Subsets@#,Length@#>2&&Intersection[#,Tr/@#~Subsets~{2}]=={}&]~Last~0&

```

Anonymous function, returns `0` on no answer.

# Answer
> 0 votes
# Pyth, 27 bytes

```
ef!f!*Fm-Fd.pYfqlY3yTfglT3y

```

Test suite.

---
Tags: code-golf, combinatorics, set-partitions
---


title: Nine Nines of Uptime

text:
# Question
Title: Nine Nines of Uptime
**Uptime** is a very important metric, as we all know, so we'd like to measure the uptime since our service was first launched. The SLA specifies an uptime of a certain number of nines, such as 3 nines for at least `99.9%` uptime, or 1 nine for at least `90%` uptime, and you're wondering if you've actually met the SLA or not. Since you know the service went down last friday night when *someone* pushed to production, and since this is basically standard practice here, you figure there's no need for your code to handle 100% uptime as a special case.

Everytime a server stops or starts, Nagios sends you an email. The service in question has some level of fault tolerance, so only `m` servers have to be online for the service to be available. You just wrote a quick script to extract the important information from these emails. Now it's time for the fun part, and you're in the mood for golfing.

**Your task** is to write a program or function that analyzes the input, figures out the uptime, and prints the largest integer number of nines achieved by the service.

**Input:**

* The number of servers required to be running for the service to be considered online: `m` \> 0.
* Followed by at least one line, one for each server. Each line contains start/stop times for that server. Since we've measured this since the service was launched, the first number is the time the server started the first time. The second time is a stop time, the third another start time etc.
* No single server is ever started and stopped at the same time.
* This means that if the server is currently running, you haven't gotten an email about it shutting down yet, so the number of numbers on that line would be odd.
* The lines are sorted, but the ordering between different lines is not enforced.
* The input is EOF-terminated. The last character of the input will be `\n` followed by `EOF` (ctrl+D).
* The time starts at time `0` and ends at the last recorded start/stop of a single server, since that's all the information we have so far. This can be done by adding max(last number on each line) to the end of all odd-length lines.
* Time is discrete.
* All input numbers are guaranteed to fit inside a 32bit integer.
* The service will never have 100% uptime.
* If you would like to add an integer telling you how many servers there are, you may do so. You may also add an integer in the beginning of each server line telling you how many measurements there are for that server. See example in first testcase. **You may also use whatever native format you'd like.**

**Output:**
The output consists of a single integer; the highest number of nines that you can guarantee you had in hindsight, i.e. `3` for at least `99.9%` uptime or `4` for at least `99.99%` uptime.

**Testcases:**

First:

```
1
0 5 8 10
0 1 7

-> 1

```

First, with counts (if you prefer that):

```
1 2
4 0 5 8 10
3 0 1 7

-> 1

```

Second:

```
1
0 999 1001 2000

-> 3

```

Third:

```
3
0 42

-> 0

```

**Reference implementation:** (Python 2)

```
"""
Slow and huge, but useful for checking smaller inputs.

input: m, followed by n lines of start and stop times, all servers are turned off in the beginning, all numbers fit inside 32bit signed integers, counts are optional
output: number of nines of uptime

example:
1
0 5 8 9
0 1 7
parsed:
1st node: on 0:5, 7:9
2nd node: on 0:1, 6:9
at least one server is running during:
0:5, 7:9
known time interval: 0:9, only timestep 6 is down, so 90% uptime during the part we can see.
output:
1

"""

import sys

def rangeify(l):
    res = []
    for i in range(0, len(l), 2):
        res += range(l[i], l[i + 1] + 1)
    return res

def parse():
    m = input()
    lines = [map(int, x.split()) for x in sys.stdin.read().split("\n")[:-1]]
    if not lines:
        return [], m
    top = max(map(max, lines))
    nlines = [x + [top] if len(x) % 2 else x for x in lines]

    n2lines = map(rangeify, nlines)
    return n2lines, m

def flatten(ls):
    res = []
    for l in ls:
        res += l
    return sorted(res)

def join(ups):
    res = {}
    for up in ups:
        if up not in res:
            res[up] = 0
        res[up] += 1
    return res

def bin(ups, m):
    res = []
    for up in range(max(ups)+1):
        res += [up in ups and ups[up] >= m]
    return res

def nines(a):
    s = ("%.15f" % a)[2:]
    s2 = s.lstrip("9")
    return len(s) - len(s2)

def solve(l, m):
    if len(l) < m:
        return nines(0)
    b = bin(join(flatten(l)), m)
    return nines(sum(b) / float(len(b)))

print solve(*parse())

```

# Answer
## JavaScript (ES6), 161 bytes

```
(m,a)=>a.map(b=>b.map(n=>l=n>l?n:l),l=0)|a.map(b=>c.map((_,i)=>{k=b[j]==i;j+=k;n^=k;c[i]+=n|k},j=n=0),c=Array(++l).fill(0))|Math.log10(l/c.filter(n=>n<m).length)

```

Accepts an integer representing the minimum number of concurrent servers and an array of arrays representing the start and stop times of each server. Edit: Now uses inclusive ranges, so correctly returns 1 for the first example.
> 1 votes

# Answer
# Pyth - 26 bytes

```
/`.Omgsm%lf<dTk2.QQeSs.Q`9

```

Try it online here.
> 1 votes

---
Tags: code-golf
---