# Question
Title: Cooke and Wheatstone telegraph, five-needle
# Definition

According to Wikipedia:

> The Cooke and Wheatstone telegraph was an early electrical telegraph system dating from the 1830s invented by English inventor William Fothergill Cooke and English scientist Charles Wheatstone. It was the first telegraph system to be put into commercial service. The receiver consisted of a number of needles which could be moved by electromagnetic coils to point to letters on a board. This feature was liked by early users who were unwilling to learn codes, and employers who did not want to invest in staff training.

It works like this:

In the middle are five needles, which can be deflected clockwise (as is the case of the middle needle) or anti-clockwise (as is the case of the last needle).

In the picture above, the two deflected needles point to the letter `G`, which means that the letter being transmitted/received is the letter `G`.

Note that the letters `C`, `J`, `Q`, `V`, `X`, `Z` are missing and thus have to be substituted with other letters.

# Task

You will receive a character in `ABDEFGHIKLMNOPRSTUWY` as input, and you will output the corresponding configuration of the five needles, with undeflected as `|`, deflected clockwise as `/`, and deflected anti-clockwise as `\`.

# Testcases

This covers **all** the possible inputs

```
input output
A     /|||\
B     /||\|
D     |/||\
E     /|\||
F     |/|\|
G     ||/|\  (explanation: see above)
H     /\|||
I     |/\||
K     ||/\|
L     |||/\
M     \/|||
N     |\/||
O     ||\/|
P     |||\/
R     \|/||
S     |\|/|
T     ||\|/
U     \||/|
W     |\||/
Y     \|||/

```

### Rules/Requirements

* 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.
* If it is possible, provide a link to a site where your program can be tested.
* Your program must not write anything to `STDERR`.
* Standard Loopholes are forbidden.
* Your program can output in any case, but it must be printed (not an array or similar).

### Scoring

Programs are scored according to bytes, in UTF-8 by default or a different character set of your choice.

***`Eventually`***, the answer with the least bytes will win.

# 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 = 87104; // 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 = 48934; // 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
# C, ~~124~~ ~~107~~ 98 bytes

As a function:

```
x,i;W(char*v){for(i=strcspn(" MRUYH NSWEI OTBFK PADGL",v);x<5;++x)putchar(x^i%5?x^i/5?124:92:47);}

// main(int c,char**v){W(v[1]);}

```

This works by using rotating the grid 45 degrees and looking up the row/column from the resulting block.

---

As a full executable (107 bytes):

```
x;main(i,v)char**v;{for(i=strcspn(" MRUYH NSWEI OTBFK PADGL",v[1]);x<5;++x)putchar(x^i%5?x^i/5?124:92:47);}

```

---

An alternative full executable: (same bytecount but takes input from stdin and includes newline after output)

```
main(i){char*r=" MRUYH NSWEI OTBFK PADGL",b[]="|||||";i=strchr(r,getchar())-r;b[i%5]=47;b[i/5]=92;puts(b);}

```

Breakdown:

```
x;                                      // Implicit int declaration
main(i,v)char**v;{                      // K&R function declaration to save a byte
    for(i=strcspn("<...>",v[1]);        // Find index of input in lookup table
        x<5;++x)                        // Loop 0 to 4
        putchar(x^i%5?x^i/5?124:92:47); //  Print /, \ or | depending on value of i
}

```

Alternate breakdown:

```
main(i){
    char*r="<...>",                     // Store lookup table
    b[]="|||||";                        // Malleable base string for return
    i=strchr(r,getchar())-r;            // Find input in lookup table
    b[i%5]=47;                          // Set correct char in output to /
    b[i/5]=92;                          // Set correct char in output to \
    puts(b);                            // Print result
}

```

---

Bonus: 0-9 extension from the wikipedia page:

```
x;main(i,v)char**v;{for(i=strcspn(" MRUY6H NSW7EI OT8BFK P9ADGL 012345",v[1]);x<5;++x)putchar(x^i%6?x^i/6?124:92:47);}

```

---

Bonus bonus: a complete (if messy) program for both encoding and decoding messages:

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

static const char *REF = " MRUY6H NSW7EI OT8BFK P9ADGL 012345 ";

char sub(char c) {
    c = toupper(c);
    if(c == 'C') { c = 'K'; }
    if(c == 'J') { c = 'G'; }
    if(c == 'Q') { c = 'K'; }
    if(c == 'V') { c = 'W'; }
    if(c == 'X') { c = 'S'; }
    if(c == 'Z') { c = 'S'; }
    return c;
}

void print_encoded(char c) {
    char b[] = "|||||";
    const char *p = strchr(REF, sub(c));
    if(!p) { return; }
    int i = p - REF;
    if(i) {
        if(i%6 < 5) { b[i%6] = '/'; }
        if(i/6 < 5) { b[i/6] = '\\';}
    }
    puts(b);
}

char decode(const char *m) {
    int pf = 5;
    int pb = 5;
    for(int x=0;x<5;++x) {
        if(m[x] == '/') {
            pf=x;
        } else if(m[x] == '\\') {
            pb=x;
        } else if(m[x] == '\0') {
            return '!';
        }
    }
    return REF[pb*6+pf];
}

int main(int c, const char **v) {
    int inArg;
    bool isDecode;
    if(c > 1 && (strcmp(v[1], "-h") == 0 || strcmp(v[1], "--help") == 0)) {
        printf("Usage:\n  %s [-d] [<input>]\n\n", v[0]);
        printf("Converts input to/from Cooke and Wheatstone 5-needle encoding.\n\n");
        printf("If no input arguments are given, takes input from stdin.\n\n");
        printf("Parameters:\n");
        printf("  -h --help   Displays help.\n");
        printf("  -d --decode Switches to decode mode.\n");
        printf("\n");
        return 0;
    } else if(c > 1 && (strcmp(v[1], "-d") == 0 || strcmp(v[1], "--decode") == 0)) {
        inArg = (c > 2 ? 2 : 0);
        isDecode = true;
    } else if(c > 1) {
        inArg = 1;
        isDecode = false;
    } else {
        inArg = 0;
        isDecode = false;
    }
    if(isDecode) {
        if(inArg == 0) {
            char ln[6];
            while(scanf("%5s", ln) == 1) {
                putchar(decode(ln));
            }
        } else {
            for(int p = inArg; p < c; ++p) {
                for(const char *q = v[p], *e = strchr(v[p], '\0'); q < e; q += 5) {
                    while(*q == ' ') { ++q; }
                    putchar(decode(q));
                }
            }
        }
        putchar('\n');
    } else {
        if(inArg == 0) {
            int c;
            while((c = getchar()) != EOF) {
                print_encoded(c);
            }
        } else {
            for(const char *p = v[inArg]; *p; ++p) {
                print_encoded(*p);
            }
        }
    }
    return 0;
}

```
> 6 votes

# Answer
## CJam, 42 bytes

```
r"HEBAMRUYIFDNSWKGOTLP"5e!{_$"/\|"er}%_&er

```

Test it here

Although there's a lot of structure to the outputs I'm not entirely sure yet I can compute the results efficiently (in terms of bytes). So this is still a lookup table, but I'm generating the list of possible needle configurations via permutations of the list `[0 1 2 3 4]`.
> 5 votes

# Answer
# Python 2, ~~172~~ ~~152~~ ~~151~~ 79 bytes

```
lambda x:r'/|||\/|||/\|||/|\||/||\|/||'['APONM LKIHY GFEWU DBTSR'.find(x):][:5]

```

No algorithm, just a lookup table.

*Saved 20 bytes thanks to @LeakyNun!*

*Saved a byte thanks to @TheBikingViking!*

*Saved a whopping **72** bytes thanks to @Keeta!*
> 3 votes

# Answer
# MATL, 50 bytes

```
'!#$kYAqof^EZC}40iA*9n4JK?45/J~v'6Y2'\|/'Za5eioZ)!

```

**Try it online!**

### Short explanation

The code decompresses the shown string (`'!#$...J~v'`) into a string containing `\`, `|` and `/`; reshapes it into an array where each column corresponds to a letter; and indexes that array with the input character.

### Long explanation

The compressesed string has been obtained (offline) using base-3 to base-95 encoding. The data from the challenge has been arranged into a long string of `\`, `|` and `/`, where each group of `5` characters corresponds to a letter. This string is interpreted as the base-3 representation of some big number, which is converted to base-95, using all printable ASCII chars as digits. The result is the compressed string that appears in the code (`'!#$...J~v'`).

The program starts decompressing this string, that is, converting from base-95 to base-3 with alphabet `\`, `|`, `/`. The decompressed string is reshaped into a 5-row 2D char array, in which each column representing a letter. Let us call this array `Λ`. This array will be indexed using the ASCII code point of the input letter.

The array `Λ` includes two tricks:

1. It has been filled with dummy values for the five letters missing between `A` and `Y`;
2. It starts with `L` (not `A`) and then proceeds circularly.

The reasons for these two tricks are as follows:

1. Letter `A` has code point `65`. The last letter that needs to be handled is `Y`, with code point `89`. So we need to handle a range of `25` values, even if some intermediate ones (such as letter `C`) don't exist. To facilitate indexing, the five missing letters between `A` and `Y` have been filled with a dummy representation, so they do have a column in `Λ`. Thus, `Λ` has size 5×25.
2. Modular indexing is used. So letter `A`, or number `65`, is the same as `65 mod 25`, that is `15`. Therefore `A` needs to be in column `15` of `Λ`, `B` in column `16`, ..., and `Y` in column `14`.

### Commented code

```
'!#$kYAqof^EZC}40iA*9n4JK?45/J~v'     % Compressed string (in base-95)
6Y2                                   % Predefined literal 'AB...Z': source alphabet
                                      % for decompression
'\|/'                                 % Target alphabet for decompression
Za                                    % Change of base representation (decompress)
5e                                    % Reshape into 5-row array `Λ`
i                                     % Input letter
o                                     % Convert to number (ASCII code point)
Z)                                    % Use as column index into `Λ`
!                                     % Transpose into a row. Implicitly display

```
> 3 votes

# Answer
# 05AB1E, ~~37~~ 34 bytes

Code:

```
"/\|||"œ€JÙ•3wxìeNðƒ2xGÑäß•36BIk<è

```

Uses the **CP-1252** encoding. Try it online!.
> 1 votes

# Answer
## JavaScript (ES6), ~~97~~ 89 bytes

```
c=>(n=`ABEHMDFINRGKOSULPTWY`.search(c),s=[...`|||||`],s[4-n%5]=`\\`,s[n>>2]=`/`,s.join``)

```

Edit: Saved 3 bytes by switching to a lookup table that doesn't need padding. Saved 5 bytes by setting array elements instead of trying to edit a string.

Explanation: The table `ABEHMDFINRGKOSULPTWY` is organised so that if you split it into 5 groups of 4 adjacent letters then each letter in the group is on the same `/` slant in the diagram, while if you split it into 5 groups by taking the index modulo 5 then each letter in the group is on the same `\` slant in the diagram. These latter groups are in reverse order but that's easily handled by subtracting from 4. (Arranging the table so that the former groups were in reverse order cost more to fix.)
> 1 votes

# Answer
# VBA, 106 bytes

```
Function v(s):v="|||||":p=InStr(1,v &"MRUYH NSWEI OTBFK PADGL",s):Mid(v, p\5)="\":Mid(v, (p Mod 5)+1)="/"

```

Final byte is `enter` which auto-generates `End Function`. With acknowledgements to the scheme @Dave devised.

Invoke in spreadsheet or in VBA Immediate window eg with `?v("K")`
> 1 votes

# Answer
# Mathematica, 129 bytes

```
""<>(IntegerDigits[IntegerDigits[36^^3ucgb2abu46m2rewohw225q4lc6hczypueyb3,190][[LetterNumber@#]],3,5]/.{0->"|",1->"/",2->"\\"})&

```

Anonymous function. Takes a string as input and returns a string representing its code as output. Uses a relatively simple encoding scheme.
> 0 votes

# Answer
# Python 2, ~~115~~ 111 bytes

This is a simple implementation, but it could use some golfing. Suggestions welcome.

```
def f(c):s=["|"]*5;a=0xdb52384ebd9f46caa72899c838d50/25**(ord(c)-65)%25;s[a/5]="/";s[a%5]="\\";return''.join(s)

```

**Ungolfed:**

```
def f(c):
    s = ["|"] * 5
    d = ord(c) - 65
    # 0xdb52384ebd9f46caa72899c838d50 is our lookup number
    # 0040004100304231200043322110342300120124130214000304
    # in hexadecimal
    a = 0xdb52384ebd9f46caa72899c838d50 / 25**d % 25
    s[a/5] = "/"
    s[a%5] = "\\"
    return ''.join(s)

```
> 0 votes

# Answer
# Pyth, 27 bytes

```
@{.p"/|\||"x."AW
Ú/Ç\x94E\x18µð££

```

Replace the escapes `\x94`, `\x18` with the corresponding bytes.

Try it online

### How it works

```
@                                      index into this list:
  .p"/|\||"                              permutations of /|\||
 {                                       deduplicate
                                       at index:
            ."AW\nÚ/Ç\x94E\x18µð££"      compressed string: EBAHIFDNSWKGOTLPMRU
           x                       Q     index in that of input (or -1 for Y)

```

# Pyth, 32 bytes

Without using any hard-coded lookup tables.

```
@o-xN\/xN\\{.p"/\|||"x-rG2"CJQVX

```

Try it online

### How it works

```
@                                    index into this list:
            .p"/\|||"                  all permutations of /\|||
           {                           deduplicate
 o                                     sort by the following key for N in the list:
   xN\/                                  index of / in N
  -    xN\\                              … minus index of \ in N
                                     at index:
                       rG2             capitalized alphabet
                      -   "CJQVX"      minus CJQVX
                     x           Q     index in that of input

```
> 0 votes

# Answer
# C, 78 bytes

```
i;f(x){for(i=5;i--;)putchar("|/\\|"["^\\ NXLFPH DBow{} gsyc q a"[x-65]>>i&3]);}

```

version shown is all printable ASCII, 79 bytes. The second `\\` can be replaced by any single byte that has the same last 6 bits as the `\` character 0x5C : 0x1C (if your compiler allows it), 0x9C or 0xDC.

The input character is looked up in the magic string which contains values for `A` to `Y` (including spaces for the unsupported characters `CJQVX`.) The character from the lookup table is interpreted as five overlapping 2-bit codes where:

```
01 = /   10 = \    00 or 11 = |

```

**Commented code in test program**

```
/*
magic string codes: bytes are 01XXXXXX
A     /|||\ 011110 ^
B     /||\| 011100 \\
D     |/||\ 001110 N
E     /|\|| 011000 X
F     |/|\| 001100 L
G     ||/|\ 000110 F
H     /\||| 010000 P
I     |/\|| 001000 H
K     ||/\| 000100 D
L     |||/\ 000010 B
M     \/||| 101111 o
N     |\/|| 110111 w
O     ||\/| 111011 {
P     |||\/ 111101 }
R     \|/|| 100111 g
S     |\|/| 110011 s
T     ||\|/ 111001 y
U     \||/| 100011 c
W     |\||/ 110001 q
Y     \|||/ 100001 a

                                     ABBCDEFGHIJKLMNOPQRSTUVWXY*/
i;f(x){for(i=5;i--;)putchar("|/\\|"["^\\ NXLFPH DBow{} gsyc q a"[x-65]>>i&3]);}

j;
main(){
  j=getchar();
  f(j);
}

```
> 0 votes

# Answer
# Ruby, 159 bytes

```
v=[1,2,3,4,7,8,9,13,14,19];w=v+v.map{|e|25+e};a="HEBAIFDKGLMRUYNSWOTP";b="\\/"
x=w[a.index($*[0][0])];g="|"*5;y=(x>25)?0:1;g[(x/5)%5]=b[y];g[x%5]=b[1-y];puts g

```

### Explanation:

The positions of the deflected needles are mapped to 0..4, and thought as a base-5 number (2 digits). For A-L, the numbers are "as is"; for M-Z, add 25 to the number. The map is from variables `a` to `w`.

Given the number corresponding to the letter, use its base-5 representation: the 5s digit for the first needle, the 1s digit for the second needle, and the 25s digit for the needles' directions.

A program to encode an entire string, instead of one character, is just a bit longer: 172 bytes.

```
v=[1,2,3,4,7,8,9,13,14,19];w=v+v.map{|e|25+e};a="HEBAIFDKGLMRUYNSWOTP";b="\\/"
$*[0].each_char{|c|x=w[a.index(c)];g="|"*5;y=(x>25)?0:1;g[(x/5)%5]=b[y];g[x%5]=b[1-y];puts g}

```
> 0 votes

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


title: Is the DAG a transitive reduction?

text:
# Question
Title: Is the DAG a transitive reduction?
The goal of this challenge is given a finite directed acyclic graph (DAG), determine if the graph is a transitive reduction.

A brief explanation of what a DAG and transitive reductions are:

A DAG is a graph with directed edges (i.e. you can only travel in one direction on that edge) such that given any starting node on the graph, it is impossible to return to the starting node (i.e. there are no cycles).

Given any starting node, if it is possible to travel to another ending node in the graph via any arbitrary positive number of edges, then that ending node is defined as reachable from the starting node. In a general DAG, there might be multiple paths which can be taken from a starting node to a target ending node. For example, take this diamond graph:

To get to node `D` from `A`, you could take the path `A->B->D` or `A->C->D`. Thus, `D` is reachable from `A`. However, there is no path which can be taken to get to node `B` starting from node `C`. Thus, node `B` is not reachable from node `C`.

Define the reachability of the graph as the list of reachable nodes for every starting node in the graph. So for the same example diamond graph, the reachability is:

```
A: [B, C, D]
B: [D]
C: [D]
D: []

```

Another graph which has the same reachability as the above graph is shown below:

However, this second graph has more edges than the original graph. The transitive reduction of a graph is a graph with the least number of edges and same reachability of the original graph. So the first graph is the transitive reduction of the second one.

For a finite DAG, the transitive reduction is guaranteed to exist and is unique.

# Input

The input is a "list of lists", where the external list has the length of the number of vertices, and each internal list is the length of the number of edges leaving the associated node, and contains the indices of destination nodes. For example, one way to describe the first graph above would be (assuming zero based indexing):

```
[[1, 2], [3], [3], []]

```

You may begin indexing of the first node at any arbitrary integer value (e.g. 0 or 1 based indexing).

The input may come from any input source desired (stdio, function parameter, etc.). You are free to choose the exact input format as long as no additional information is given. For example, if you want to take input from stdio, you could have each line be a list of edges for the associated node. Ex.:

```
1 2
3
3
'' (blank line)

```

The indices in each adjacency list is not necessarily sorted, and there could be multiple edges connecting two nodes (ex.: `[[1,1],[]]`). You may assume the input graph is weakly connected, and contains no cycles (i.e. it is a DAG).

# Output

The output is truthy if the given input DAG is a transitive reduction, and a falsy value otherwise. This may be to any sink desired (stdio, return value, output parameter, etc.)

# Examples

All examples use 0-based indexing.

```
[[1,2],[3],[3],[]]
true

[[1,2,3],[3],[3],[]]
false

[[1,1],[]]
false

[[1,2,3,4],[5,6,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true

[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true

[[5,6,7],[2,3,0,4,14,5,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false

[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10,14],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false

[[1,3],[2],[3],[]]
false

```

# Scoring

This is code golf; smallest code in bytes wins. Your code should complete in a reasonable amount of time (10 minutes max on whatever hardware you have). Standard loopholes apply. You may use any built-ins desired.

# Answer
# Ruby, ~~101~~ 97 bytes

Simple approach that calculates the reach from each node and considers if a child node can be reached via any of the other nodes. Seemingly fails on cyclic graphs, but the definition of a DAG implies that it shouldn't be cyclic anyways.

Try it online!

```
->g{r=->i{i|i.map{|j|r[g[j]||[]]}.inject([],:|)}
g.all?{|e|e==e&e&&e.none?{|i|r[e-[i]].index i}}}

```
> 5 votes

# Answer
# Mathematica, ~~95~~ 82 bytes

<sup>*13 bytes saved due to @MartinEnder.*</sup>

```
#~IsomorphicGraphQ~TransitiveReductionGraph@#&@Graph[x=0;##&@@Thread[++x->#]&/@#]&

```

Anonymous function. Takes a nested list as (1-based) input, and returns `True` or `False` as output. The main solution here is the 46-byte `#~IsomorphicGraphQ~TransitiveReductionGraph@#&`, which tests if a given graph is isomorphic to its transitive reduction. The rest converts the input to a `Graph` object.
> 4 votes

# Answer
## CJam (41 bytes)

```
q~:A_,{{Af=e__&}%_}*]:.|A.&A:$:e`e_2%1-*!

```

Online demo, test harness

### Dissection

```
q~:A      e# Parse input and store in A
_,{       e# Loop V times
  {       e#   Extend adjacency list representation of G^i to G^(i+1)
    Af=   e#   by extending each path by one edge
    e__&  e#   and flattening. NB :| would be shorter but breaks for empty lists
  }%
  _       e#   Duplicate, so that we build up G^2, G^3, ..., G^n
}*]       e# Gather in a single array
:.|       e# Fold pointwise union, giving the reachability from each vertex by
          e# paths of length > 1
A.&       e# Pointwise intersect with the paths of length 1
          e# We hope to get an array of empty arrays

          e# Handle the awkward special case of duplicate edges:
A:$       e# Sort each adjacency list
:e`       e# Run-length encode each adjacency list
e_2%      e# Extract only the run lengths
1-        e# Discard the 1s - so we now have an empty array unless there's a dupe

*         e# Join. We hope to be joining an array of empty arrays by an empty array
          e# giving an empty array
!         e# Check that we get a falsy value (i.e. the empty array)

```
> 3 votes

# Answer
# Jelly, 20 bytes

```
ị³$ÐĿ€ị@Fœ&¥";œ-Q$€E

```

Uses 1-based indexing. Try it online!

## Loose Overview

```
     €                for each vertex,
ị³$ÐĿ                   compute its reach.
        Fœ&¥"         intersect each vertex's lists of children and
      ị@                children's reaches.
             ;        then concatenate the list of intersections with
              œ-Q$€     all duplicate edges in the original graph.
                   E  are all elements equal? checks that all are empty lists,
                        meaning empty intersections and no duplicates.

```
> 3 votes

---
Tags: code-golf, graph-theory
---


title: Leo's Pokerface

text:
# Question
Title: Leo's Pokerface
# Pokerface

### Introduction

Leo enjoys playing poker, but his job at Tech Inc. is too demanding for him to learn how to play well. Leo, being a computer scientist, is not discouraged. He decides to take more time than it would have taken to just learn poker, and use it to write a poker bot to help him play better. But now Leo has a problem: in order to understand how to play a bit better, Leo needs to observe multiple games of multiple "people," but the "people" need different play styles to improve the quality and reality of the game.

### The Challenge

Leo recalls that there is actually a website dedicated to programming challenges, and is enlisting your help! Your job is to write a program which plays "Pokerface" a modified version of 5-card poker. The program will take input as a 5-card hand in whatever format you wish, after which the program will output:

* Exactly (case-sensitive) "true" "1" or "t" if the player wishes to exchange cards, any other non-empty output otherwise.
* If true, list of indices of cards and/or card names the player wishes to exchange.
* A single number between 0 and 3, which specifies how many additional cards the player wants.
* Print out the hand the player wishes to use.

(See formatting below)

### Pokerface rules

* Since pokerface is a text-based adventure game, cards must be presented in a consistent way. Cards are represented by two character codes, the first character is the suit, and the second is the name of the card.
    + Cards:
        - 2-9 = 2-9
        - 10 = T
        - Jack = J
        - Queen = Q
        - King = K
        - Ace = A
    + Suits:
        - Spades = S
        - Clubs = C
        - Hearts = H
        - Diamond = D

So the ace of spades would be SA, the 10 of hearts is HT, the 4th of diamonds is D4, etc.

* A single round of Pokerface consists of four steps:
    + The deck is reshuffled and a five card hand is dealt to each player.
    + Each player is given the chance to exchange as many cards as they want.
    + Each player is given the chance to gain up to three more cards.
    + Each player must reveal their best hand.
* The best hand wins, and gains that player a point. In the event of a tie, both players get a point.
* In a single game, ten rounds are played and the player with the most points wins and gains a single "win point." In the event of a tie, both players gain a win point.
* Leo doesn't really have a large amount of money, so your bot can assume that this is a perfect world with no betting.

### Hands

* Hands are exactly 5 cards in length (initial input and final output).
* Hands are ranked consistent with the rules described here.

### Input / Output

* Leo only knows Java, so your program must be executable via the Process API (command line), and use STDIN and STDOUT for input and output, respectively.
* For each step of input and output detailed above, the input and output must each exist on one line.
* There must be at least one trailing new line after the final output. (This is due to the way input is read from STDIN)
* No extraneous input/output is allowed, other than trailing and leading spaces. The parser simply does not understand things like `final_hand=...` or `draw 0`.
* When drawing, output is a single integer, when exchanging output is a list of integers and/or cards defined below, and when being dealt the original hand, output is a list of cards defined below.
* All input/output numbers must be positive integers in base 10.
* You may define the format for card input (see post format below).
* True is defined as exactly "true," "1" or "t" and false is any other non-empty value.
* During the exchange step:
    + Card indices must be output with at least one space between them (e.g. `3 4 0`)
    + Card names must be output with at least one space between them (e.g. `H4 S8`)
    + Card names and indices may be mixed in the output (e.g. `0 H7 3 D3`)
    + Trailing and leading spaces are allowed.
    + The input as a result of the player outputting the above will be formatted as specified by the `bot.jlsc` file, in the same order as requested
* The number of cards a player wants to add to their hand can have leading and trailing spaces.
* Hands must be output with at least one space between them (e.g. `H4 D5 CA`), trailing spaces and leading spaces are allowed.
* Hands do not need to be output in proper order (e.g. `H4 D4 C4 DA SA` and `H4 DA D4 SA C4` both represent 4, 4, 4, Ace, Ace, which is a full house).
* If you wish to build a strategy by analyzing opponents hands, you may store data in a `<botname>/data` directory.
    + After competing bots have displayed their hands, they will be written to every bots data directory, in hands.txt, with each hand on a new line (separated by \n). The file will be encoded in US\_ASCII.
* After your bot requests new cards or exchange cards, the cards will be input depending on what format you specify in the `bot.jlsc` file.

### Post Format

* Every post must include two things:
    + The source code of your bot, or a link to a public facing repository.
    + A zip file containing:
        - The compiled/executable version of your bot (If the file is a .exe or other non-de-compilable file, please just include compilation instructions in your post).
        - A `bot.jlsc` file, see below (side note: the .jlsc extension is just because of a side project of mine, a configuration format. The file below matches the proper syntax, so don't worry).
    + The .zip file must be named the same as your bot.
* If you don't have access to windows or some other zipping utility, or can't make a .zip for whatever reason, just include the text of the bot.jlsc file in your post

---

bot.jlsc file:

```
name= "Botty"
link= "example.com"
cmd= "java -jar Botty.jar"
input_hand= "${0} ${1} ${2} ${3} ${4}"
input_1= "${0}"
input_2= "${0} ${1}"
input_3= "${0} ${1} ${2}"
input_4= "${0} ${1} ${2} ${3}"

```

---

Where:

* "cmd" is the **windows** command line command to run your bot. Note that your bot will be in directory `<botname>`, so adjust the command accordingly.
* "name" is the name of your bot.
* "link" is the link to your answer, you'll have to edit this in after posting.
    + "input\_hand" is how you want the original dealing to be formatted (with ${#} representing cards 0-4).
* "input\_1" is how you want the input of one additional card to be formatted.
* "input\_2" is how you want the input of two additional cards to be formatted.
* "input\_3" is how you want the input of three additional cards to be formatted.
* "input\_4" is how you want the input of four additional cards to be formatted.

### Specifics

* These loopholes are disallowed (see 'common pitfalls')
* You may not write a bot the will always output the best hand possible, every time, within the rule set. (i.e. no long-running brute-force bots, nothing should be quite as 'good' as LeoBot)
* Your bot should run in ~100 ms or less (Lenient on this point, max of ~1 second)
* Any output of the bot after its chosen hand will be ignored.
* Standard loopholes are disallowed.
* Yes, I know linux is better, but I have a windows PC, so be sure the compiled/executable version of your program can be run from the windows command line.
    + I already have python and java installed on my computer, but I'm willing to update to new versions and install other environments, so please specify what type of environment your program requires.
* You may not write a bot which does the same thing as another bot in every case. Spam bots are allowed, but discouraged.
* Your bot may only use cards it has. Cards lost through exchange or not dealt to begin with are invalid output in the final hand.
* Input and output may only contain ASCII characters.

### Tournaments

* Tournaments will be run when I get the time (my schedule is nearly as packed as Leo's, so this my be a little infrequent. Sorry for the inconvenience.).
* Bots will be pit against eachother in 4 person games, and there will be one game for each possible subset of bots (i.e. lots of games).
    + This process will be repeated five times.
    + Due to the way the tournament handler makes the groups of bots, up to three filler bots will be added to make the number of bots divisible by 4. These bots will simply return the hand they were originally dealt.
* After every round and game is run, the scores of the bots will be computed based on the number games they won.
    + Multiple bots can share a position (ties for first won by first posted).
* After a tournament finishes, the scores will be appended to the bottom of this post.

### Scoring

Normal KoTH rules. The bot(s) that win the most games win the challenge.

### LeoBot

Leo's bot is pretty smart. It doesn't exchange any cards, that's too hard, but it does request the maximum number of additional cards, and it determines the best possible hand it can make, and plays that hand. The main logic of leobot is below.

```
package com.gmail.socraticphoenix.pokerface.leobot;

import com.gmail.socraticphoenix.pokerface.lib.card.Card;
import com.gmail.socraticphoenix.pokerface.lib.card.Deck;
import com.gmail.socraticphoenix.pokerface.lib.rule.HandRegistry;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LeoBot {

    public static void main(String[] args) {
        List<Card> hand = new ArrayList<>();

        Scanner scanner = new Scanner(System.in);
        hand.addAll(Card.parseHand(scanner.nextLine()));
        System.out.println(false);

        System.out.println(3);
        hand.addAll(Card.parseHand(scanner.nextLine()));

        List<List<Card>> possibleHands = LeoBot.getSubsets(hand, 5);
        System.out.println(Deck.toString(possibleHands.stream().sorted((a, b) -> HandRegistry.determineWinner(b, a).comparable()).findFirst().get()));
    }

    private static <T> void getSubsets(List<T> superSet, int k, int idx, List<T> current, List<List<T>> solution) {
        if (current.size() == k) {
            solution.add(new ArrayList<>(current));
            return;
        }
        if (idx == superSet.size()) return;
        T x = superSet.get(idx);
        if (!current.contains(x)) {
            current.add(x);
        }
        getSubsets(superSet, k, idx + 1, current, solution);
        current.remove(x);
        getSubsets(superSet, k, idx + 1, current, solution);
    }

    public static <T> List<List<T>> getSubsets(List<T> superSet, int k) {
        List<List<T>> res = new ArrayList<>();
        getSubsets(superSet, k, 0, new ArrayList<T>(), res);
        return res;
    }

}

```

Note that if LeoBot consistently wins the tournaments, and there are a good amount of entries, I'll stop including him in the running.

### Important Links

### Disclaimer

Leo and Tech Inc. are **story elements** and any resemblance to real-life companies or people is purely unintentional. (However, when Leo's 'situation' adds or subtracts conditions from the question, those are actually part of the question...)

# Answer
# (Python), Pairbot, not quite competing (I don't know how to make cmd commands and stuff)

Pairbot will compete as soon as someone assists with the bot.jlsc, and zip files etc.

---

Pairbot knows that you don't always get good hands. He knows good hands are rare. Pairbot knows pairs and other duplicates are some of the best hands. Pairbot also knows the lowest hand you can get is a seven high, so he knows if he has 6 high, that's actually a straight (pairbot doesn't know why he knows that). He also knows if his lowest card is 10, (with no pairs), that's also a straight (pairbot knows he can get royal flush this way). Pairbot checks mainly for same number dupes, but also checks for two types of straights in special cases.

```
card_values={"2":2, "3":3, "4":4, "5":5, "6":6, "7":7, "8":8,
             "9":9, "T":10, "J":11, "Q":12, "K":13, "A":14,}
straight=False
def card_valuing(item):
    return card_values[item[1]]

input_list=input().split()
pairs_to_keep=[]
for item in input_list:
    if sum(item[1]==card[1] for card in input_list)>1:
        pairs_to_keep+=[item]
cards_to_remove=input_list
for item in pairs_to_keep:cards_to_remove.remove(item)#we want to remove all non pairs
hand=pairs_to_keep
if pairs_to_keep==[]:
    input_list.sort(key=card_valuing, reverse=True)
    if card_values[input_list[0][1]]==6:
        straight=True
        hand=input_list
    elif card_values[input_list[-1][1]]==10:
        straight=True
        hand=input_list
    else:
        print("true\n"+" ".join(input_list[1:]))
        hand+=input_list[0]+input().split()
elif input_list!=[]:
    print("true\n"+" ".join(input_list))
    hand+=input().split()
else:print(0, end=', ')
if straight:print("0\n0\n"+" ".join(hand))
else:
    print("3")
    hand+=input().split()
    same_number_dict={} #holds the amount of each type (A, 2, 3, etc.)

    def dict_value(item):
        return int(same_number_dict[item[1]])*100+card_values[item[1]]

    for card in hand:
        same_number_dict[card[1]]=sum(card[1] == item[1] for item in hand)

    hand=list(sorted(hand, key=dict_value, reverse=True))
    final_hand =[]
    last_number=hand[0][1]
    hand_taken=0
    while hand_taken < 5:
        if last_number==hand[0][1]:
            final_hand+=[hand[0]]
            hand=hand[1:]
            hand_taken+=1
        else:
            for card in hand:
                if same_number_dict[card[1]]>5-hand_taken:
                    same_number_dict[card[1]]=5-hand_taken
            hand=list(sorted(hand, key=dict_value, reverse=True))
            last_number=hand[0][1]
    print(" ".join(final_hand))

```

---

Format for input is the same as in the example: separated by spaces

---

If Socratic Phoenix could assist with the file stuffs, that would be good
> 1 votes

# Answer
# Plumber, Python

Plumber is all about flushes. Plumber also prioritises higher value cards (meaning he can sometimes get straight flushes, especially royal ones (should they occur).) Plumber is pretty much messed if he doesn't get a flush, except that he might be lucky enough for a straight. Plumber will get flushes about 20% of the time, if calculations by *Sherlock9* are correct

```
hand=input().split()
suit_in_hand={"S":0,"C":0,"D":0,"H":0}
card_values={"2":2, "3":3, "4":4, "5":5, "6":6, "7":7, "8":8,
             "9":9, "T":10, "J":11, "Q":12, "K":13, "A":14,}
def value_sort(x):
    return card_values[x[1]]
def suit_sort(x):
    return suit_in_hand[x[0]]

for card in hand:
    suit_in_hand[card[0]]+=1

hand.sort(key=suit_sort, reverse=True)

print(" ".join(hand[suit_in_hand[hand[0][0]]:]))
hand=hand[:suit_in_hand[hand[0][0]]]

for new_card in input().split():
    hand+=[new_card]
    suit_in_hand[new_card[0]]+=1

print(3)

for new_card in input().split():
    hand+=[new_card]
    suit_in_hand[new_card[0]]+=1
hand.sort(key=value_sort, reverse=True)
hand.sort(key=suit_sort, reverse=True)
print(" ".join(hand[:5]))

```

---

Also takes input separated by spaces like other my two bots
> 1 votes

# Answer
## LadyGaga, Python 3

* Is somewhat blind to suits
* Has a dress full of bugs
* And likes to play Poker Face once in a while

```
from math import ceil as f
M=lambda A:max(set(A),key=A.count)
K=lambda A:A.count(M(A))
O=lambda A:range(len(A))
J=lambda A:A[0]+str(U(A[1]))
X={"2":2,"3":3,"4":4,"5":5,"6":6,"7":7,"8":8,"9":9,"T":10,"J":11,"Q":12,"K":13,"A":14}
def V(A):return([A[0]]+[int(X[A[1]])])
def U(c):
 if c==10:c='T'
 if c==11:c='J'
 if c==12:c='Q'
 if c==13:c='K'
 if c==14:c='A'
 return(c)
def P(A):
 S=[];C=[];t=len(A)
 for x in A:S.append(x[0]);C.append(x[1])
 B=[0]*9;q=len(set(C));p=K(C);D=list(set(C));D.sort()
 B[2]=1/f(13**(4-p));B[6]=1/f(13**(3-p));B[8]=1/f(13**(2-p))
 if (p,q)==(2,4):B[3]=1/1100;B[7]=5/34
 if (p,q)==(3,3):B[3]=1/169;B[7]=1/169
 if (p,q)==(4,2):B[3]=1/13;B[7]=1
 if (p,q)==(2,3):B[3]=5/169;B[7]=1
 if (p,q)==(3,2):B[3]=1;B[7]=1
 for x in O(D):D[x]-=x
 j=M(D);h=K(D)-5;B[5]=13**h
 for x in O(D):
  if j+h<D[x]<j-h and D[x]!=j:B[5]*=13
 W=K(S);B[4]=(4**(W-t))*(13-W)/52
 return(B,M(S))
def E(B,h,u):
 x=0;D=[];C=[]
 while 1:
  k=list(C)
  C=[]
  while 1:
   p=list(B);del p[x]
   if len(D)==3:break
   if P(p)[0][h]>=P(B)[0][h]:C.append(B[x])
   x+=1
   if x>len(p):break
  if len(C)==0:break
  for x in O(C):
   if k==C or not((u in C[x])and(len(C)-1)):D.append(C[x]);del B[B.index(C[x])]
 return(D)
s=input()
A=s.split(' ')
b=list(map(V,A));G,u=P(b);F=[649739,72192,4164,693,508,254,46.3,20,1.4];H=[]
for x in O(F):F[x]=1-((1-(1/F[x]))**4)
for x in O(F):H.append(G[x]-F[x])
Y=H.index(max(H));p=[]
e=E(list(b),Y,u);g=list(e)
for x in O(e):e[x]=J(e[x])
print(' '.join(e)if len(e)else'')
for x in g:
 if x in b:del b[b.index(x)]
s=input()
if len(s):
 A=s.split(' ')
 b+=list(map(V,A))
print(3)
s=input()
A=s.split(' ')
b+=list(map(V,A));G,u=P(b);H=[]
for x in O(F):H.append(G[x]-F[x])
Y=H.index(max(H))
e=E(list(b),Y,u)
for x in e:
 if x in b:del b[b.index(x)]
for x in O(b):b[x]=J(b[x])
print(' '.join(b[:5]))
print()

```

+ (I/O) modeled after PlumberBot -Edit: Extensive bugfixes thanks to Destructible Watermelon -Edit: Due to new rules, a trailing newline after the final output
> 1 votes

# Answer
# LuckyBot, Python

Pairbot invited his buddy Luckybot, who sprang for the chance. Luckybot had watched a lot of fictional poker, and reckoned he'd figured out the secret to poker: luck. Everyone knows the real pros (James Bond, for example) really rely and getting good hands, not skill. Hence, he doesn't look at his cards, and tries to pack as much good luck into them as possible

---

```
lucky_number=24 #IMPORTANT

from random import randint as roll

def lucky_shuffle(i):
    return sorted(i, key=lucky_dice)

def lucky_dice(seed):
    return sum(roll(1,6)for i in range(roll(1,6)))

hand=lucky_shuffle(input().split())

throw=lucky_dice(lucky_number)%5
print("true\n"+" ".join(hand[throw:]))

hand=hand[:throw]+lucky_shuffle(input().split())

hand=lucky_shuffle(hand)
hand=lucky_shuffle(hand)
#One more for good luck
hand=lucky_shuffle(hand)
#maybe one more
hand=lucky_shuffle(hand)
#I got a good feeling about this one
hand=lucky_shuffle(hand)

hand=lucky_shuffle(hand)
#I think I'm done
hand=lucky_shuffle(hand)
#for real this time

hand=lucky_shuffle(hand)

print("3")
hand=hand+lucky_shuffle(input().split())
#All right, I got a real good feeling about this,
#let me shuffle some more luck into them cards!

def extra_super_lucky_shuffle(item):
 return lucky_shuffle(lucky_shuffle(lucky_shuffle(\
    lucky_shuffle(lucky_shuffle(lucky_shuffle(\
        lucky_shuffle(lucky_shuffle(lucky_shuffle(item)))))))))

def super_duper_extra_ultra_uber_luckyshuffle(item):
    return extra_super_lucky_shuffle(extra_super_lucky_shuffle(\
        extra_super_lucky_shuffle(extra_super_lucky_shuffle(item))))

hand=super_duper_extra_ultra_uber_luckyshuffle(super_duper_extra_ultra_uber_luckyshuffle(hand))
#cmoooooooooooooooon
print(hand[:5])

```
> 0 votes

---
Tags: king-of-the-hill, card-games
---


title: Count the Unique Rectangles!

text:
# Question
Title: Count the Unique Rectangles!
In my last challenge, you were asked to find *all* rectangles given a `m x n` grid of them. However, it turned out to be very trivial as there actually was a mathematical formula I did not even know about to solve the problem! So now, for a little bit more of a challenge, how about calculating the number of *unique* rectangles, i.e. find the number rectangles that are all of different dimensions?

For example, consider 4 horizontal, or `y` lines at `[-250,-50,50,250]` and 4 vertical, or `x` lines at `[-250,-70,70,250]`. Graphing these on a coordinate plane with infinite dimensions results in the following `500 x 500` pixel closed grid, in which the length of each segment in pixels and the lines corresponding to their respected values from the arrays are shown:

which contains the `16` *unique* rectangles shown in this animated GIF:

However, if the topmost line (`y = 250`) were to be removed, there would only be `12` unique rectangles, as the top 3 rectangles would be factored out since they each won't be fully closed without the `y = 250` line.

## Task

So, as shown above, the task is counting the number of rectangles rectangles with *different dimensions*. In other words, given an input of 2 arrays, with the first one containing all equations of all `x` lines, and the latter containing those of all `y` lines, output the total number of rectangles of *different dimensions* created when the lines corresponding to those equations are graphed on a coordinate plane.

## Rules

* The use of any built-ins that directly solve this problem is explicitly disallowed.
* If either of the arrays have less than `2` elements, the output should be `0`, since if there are less than `4` lines on the plane, there are no closed, `4` sided figures.
* The input arrays are *not* guaranteed to be sorted.
* You can assume that there are not any repeated values in either of the the input arrays.
* A `n x m` rectangle is the same as a `m x n` rectangle. For example, a `300 x 200` rectangle is the same as a `200 x 300` one.
* Standard loopholes are prohibited.

## Test Cases

Given in the format `Comma Separated Arrays Input -> Integer output`:

```
[],[] -> 0
[-250,-50,50,250],[-250,-70,70,250] -> 16 (Visualized above)
[-250,-50,50,250],[-250,-70,70] -> 12
[-40, 40],[-80, 50] -> 1
[10],[10] -> 0
[60, -210, -60, 180, 400, -400], [250, -150] -> 12
[0,300,500],[0,300,500] -> 6
[0,81,90],[0,90,100] -> 9

```

Remember, this is , so shortest code wins!

# Answer
# JavaScript (ES6), 99

```
(X,Y,Z=new Set)=>X.map(v=>X.map(t=>t>v&&Y.map(w=>Y.map(u=>u>w&&Z.add([u-w,t-v].sort()+0)))))|Z.size

```

Note: `sort` is not numeric but lexicographic, but in this specific case I don't care

**Less golfed**

```
(X, Y, Z = new Set) =>
  X.map(
    v => X.map(
      t => t>v && Y.map(
        w => Y.map(
          u => u>w && Z.add([u-w, t-v].sort() + 0)
        )
      )
    )
  ) | Z.size

```

**Test**

```
F=(X,Y,Z=new Set)=>X.map(v=>X.map(t=>t>v&&Y.map(w=>Y.map(u=>u>w&&Z.add([u-w,t-v].sort()+0)))))|Z.size

;[
 [[],[], 0]
,[[-250,-50,50,250],[-250,-70,70,250], 16]
,[[-250,-50,50,250],[-250,-70,70], 12]
,[[-40, 40],[-80, 50], 1]
,[[10],[10], 0]
,[[60, -210, -60, 180, 400, -400], [250, -150], 12]
,[[0,300,500],[0,300,500], 6]
].forEach(t=>{
  var a=t[0],b=t[1],k=t[2],r=F(a,b)

  console.log(r==k?'OK':'KO','['+a+']','['+b+']',r)
})
```
> 6 votes

# Answer
# Jelly, 13 bytes

```
ṢIẆS€µ€ŒpṢ€QL

```

Try it online!

A rectangle is uniquely defined by its height and its width.

```
ṢIẆS€µ€ŒpṢ€QL   Main chain, argument: z

     µ€         For each subarray:
Ṣ                   sort
 I                  compute consecutive increments
  Ẇ                 yield all substrings
   S€               compute sum of each substring
       Œp       Cartesian product
         Ṣ€     Sort each
           Q    Remove duplicates
            L   Length

```
> 3 votes

# Answer
## CJam (22 bytes)

```
q~{2m*::-:z0-}/m*:$_&,

```

Takes input as an array of arrays. Online demo, test suite

### Dissection

```
q~     e# Parse input
{      e# For each of the two elements in the top-level array
  2m*  e#   Take its Cartesian self-product
  ::-  e#   Map fold subtraction, giving the separations between lines
  :z   e#   Map absolute value
  0-   e#   Remove 0, since trivial rectangles don't count
}/
m*     e# Cartesian product of the two sets of separations
:$     e# Sort so that mxn === nxm
_&     e# Deduplicate
,      e# Count

```
> 3 votes

# Answer
# MATL, 22 bytes

```
"@gd&Xfo!s|]Z*!S!Xuz2/

```

Try it online! Or verify all test cases.

### Explanation

```
"        % Implicitly input cell array of two numerical arrays. For each cell
  @g     %   Push cell contents
  d      %   Difference of its two entries
  &Xf    %   Cell array of all substrings
  o      %   Convert to numerical array, padding with zeros
  !s     %   Sum of each row. Gives a row vector
  |      %   Absolute value of each entry
]        % End for
Z*       % Cartesian product
!S!      % Sort each row
Xu       % Unique rows
z2/      % Number of unique rows excluding zeros. Implicitly display

```
> 3 votes

# Answer
**Python, 208 bytes**

```
import itertools as i
def h(x,y):
    s=[]
    k=[p for p in i.product(x,y)]
    for j,(v,w) in enumerate(k):
        for a,b in k[j+1:]:
            q=sorted([abs(a-v),abs(b-w)])
            if 0not in q and q not in s:s+=[q]
    return len(s)

```
> 0 votes

---
Tags: code-golf
---


title: Simulate a sock drawer

text:
# Question
Title: Simulate a sock drawer
## Background

I have a collection of "weekday socks", which are seven pairs of socks labeled by the days of the week. When I wash my socks, they end up in a pile, and I must arrange them into the correct pairs before putting them into the closet. My strategy is to pull one random sock from the pile at a time and put it on a drawer. Whenever there's a matching pair of socks on the drawer, I tie them together and put them in the closet. Your task is to simulate this random process and return the number of draws required to find the first matching pair.

## Input

Your input is an integer **N ≥ 1**. It represents the "number of days in a week": there are **N** pairs of socks in the pile, and each pair has a distinct label. If necessary, you may also take a PRNG seed as input.

## Output

Your output is the number of socks I have to draw before the first matching pair is found. For example, if the first two socks already form a matching pair, the output is `2`.

Of course, the output is random, and depends on the drawing order. We assume that *all drawing orders are equally likely*, so that each time a sock is drawn, the choice is uniform and independent from all other choices.

## Example

Let **N = 3**, so that we have 6 socks in total, labeled **A A B B C C**. One possible run of the "sock-drawing protocol" is as follows:

```
       | Pile   | Drawer | Pairs
Begin  | AABBCC | -      | -
Draw B | AABCC  | B      | -
Draw C | AABC   | BC     | -
Draw B | AAC    | C      | BB
Draw A | AC     | AC     | BB
Draw A | C      | C      | AA BB
Draw C | -      | -      | AA BB CC

```

The first matching pair was found after drawing the second **B**, which was the third sock to be drawn, so the correct output is `3`.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Input and output can be in any reasonable format, including unary (string of `1`s).

You may assume that your language's built-in RNG is perfect. You don't have to actually simulate the sock-drawing protocol, as long as your outputs have the correct probability distribution.

## "Test cases"

Here are the approximate probabilities of all outputs for the input **N = 7**:

```
Output       2     3     4     5     6     7     8
Probability  0.077 0.154 0.210 0.224 0.186 0.112 0.037

```

To test your solution, you can run it for, say, 40 000 times and see whether the output distribution is reasonably close to this.

# Answer
# Jelly, 8 bytes

```
ḤX€Ṛ<RTḢ

```

Try it online! or verify the distribution for **N = 7**.

### Background

Let **n** be the number of pairs; there are **2n** individual socks.

For the first draw, there are **2n** socks and **0** of them would result in a matching pair. Therefore, the probability of success is **0 / 2n = 0**.

Since the first draw wasn't successful, there are **2n - 1** socks on the pile and **1** of them would result in a matching pair. Therefore, the probability of success is **1 / (2n - 1)**.

*If* the second draw wasn't successful, there are **2n - 2** socks on the pile and **2** of them would result in a matching pair. Therefore, the probability of success is **2 / (2n - 2)**.

In general, if the first **k** draws were unsuccessful, there are **2n - k** socks on the pile and **2** of them would result in a matching pair. Therefore, the probability of success is **k / (2n - k)**.

Finally, if none of the first **n** draws was successful, there are **2n - k** socks on the pile and all of them would result in a matching pair. Therefore, the probability of success is **n / (2n - n) = 1**.

### How it works

```
ḤX€Ṛ<RTḢ  Main link. Argument: n

Ḥ         Unhalve; yield 2n.
 X€       Map `random draw' over [1, ..., 2n], pseudo-randomly choosing an integer
          from [1, ..., k] for each k in [1, ..., 2n].
   Ṛ      Reverse the resulting array.
     R    Range; yield [1, ..., n].
    <     Perform vectorized comparison.
          Comparing k with the integer chosen from [1, ..., 2n - (k - 1)] yields 1
          with probability (k - 1) / (2n - (k - 1)), as desired.
          The latter half of elements of the left argument do not have a counter-
          part in the right argument, so they are left untouched and thus truthy.
      T   Truth; yield all indices of non-zero integers.
       Ḣ  Head; extract the first one.

```
> 9 votes

# Answer
## Jelly, 8 bytes

```
Rx2ẊĠṪ€Ṃ

```

Try it online!

```
R    generate [1, 2, ..., n]
x2   duplicate every element (two socks of each pair)
Ẋ    shuffle the list, to represent the order in which socks are drawn
Ġ    group indices by value. this will produce a list of pairs of indices;
       each pair represents the point in time at which each of the corresponding
       socks were drawn
Ṫ€   take the last element of each pair. this returns an array of n integers
       which represent the points in time at which a matching sock was drawn
Ṃ    minimum, find the first point at which a matching sock was drawn

```

To verify, here is a version that displays both the desired output and the result of the "shuffle list" operation (to see what order socks were drawn in).
> 8 votes

# Answer
# Python, 66 bytes

```
from random import*
f=lambda n,k=1:k>randint(1,n*2)or-~f(n-.5,k+1)

```

Dennis thought up a clever way to rearrange things, saving 5 bytes.
> 5 votes

# Answer
# MATL, ~~16~~ 15 bytes

```
Q:"r@qGEy-/<?@.

```

Try it online! Or observe the empirical distribution for 1000 samples in the *N*=7 case (it takes a while).

This **directly generates the random variable** representing the result, based on its probability distribution. Let *N* be the number of sock pairs, and let *p*(*k*) denote the probability that the *k*-th draw is successful, conditioned on the fact that the *k*-1-th draw was not succesful. Then (see also here):

* *p*(1) is obviously 0. You can't have a pair with a single sock.
* *p*(2) is 1/(2\**N*−1). At the second draw there is one winning sock that may be chosen out of 2\**N*−1 remaining socks.
* *p*(3) is 2/(2\**N*−2). At the third draw there are 2 winning socks out of 2\**N*−2. The number of winning socks is 2 because the two socks you got after the second draw were different.
* In general, by the same reasoning, *p*(*k*) is (*k*−1)/(2\**N**k*+1)
* By the above formula, *p*(*N*+1) is 1. If you get to the *N*+1-th draw you are guaranteed to succeed then.

So the code iterates for a maximum of *N*+1 draws. At the *k*-th draw a random variable is generated that equals 1 with probability (*k*-1)/(2\**N*-*k*), or 0 otherwise. Whenever the random variable equals 1 (the draw has been succesful) the process stops and the current *k* is output.

```
Q:      % Input N implicitly. Generate [1 2 ... N+1] (values of draw index, k)
"       % For each
  r     %   Random variable uniformly distributed on the interval (0,1)
  @q    %   Push iteration index, k-1
  GE    %   Push 2*N
  y     %   Duplicate: push k-1 again
  -     %   Subtract: gives 2*N-k+1
  /     %   Divide: gives (k-1)/(2*N-k+1)
  <     %   Push 1 if random value is less than (k-1)/(2*N-k+1), 0 otherwise
  ?     %   If we got a 1
    @   %     Push k
    .   %     Break loop
        %   End if implicitly
        % End loop implicitly
        % Display implicitly

```
> 4 votes

# Answer
# MATL, ~~14~~ 13 bytes

```
EZ@G\&=XRafX<

```

Try it online! Or observe the empirical distribution for 4000 samples in the *N*=7 case (it takes a while).

```
E      % Input N implicitly. Multiply by 2
Z@     % Random permutation of [1 2 ... 2*N]
G\     % Modulo N: random permutation of [0 0 1 1 ... N-1 N-1]
&=     % Compare all pairs for equality. Gives an N×N matrix
XR     % Upper triangular part excluding the diagonal
a      % True for each column if it contains at least one true entry
f      % Get indices of true values
X<     % Take minimum. Implicitly display

```
> 3 votes

# Answer
# JavaScript, ~~77~~ 73 bytes

```
n=>{p={};for(i=n;i--;p[i]=2);while(--p[n*Math.random()|0])i++;return i+2}

```

**Explanation**

```
var f = (n) => {
    var index;      // used first to initialize pile, then as counter
    var pile = {};  // sock pile

    // start with index = n
    // check that index > 0, then decrement
    // put 2 socks in pile at index
    for(index = n; index--; pile[index] = 2);
    // index is now -1, reuse for counter

    // pick random sock out of pile and decrement its count
    // continue loop if removed sock was not the last
    while(--pile[n * Math.random() | 0]) {
        index++;    // increment counter
    }
    // loop finishes before incrementing counter when first matching pair is removed
    // add 1 to counter to account for initial value of -1
    // add 1 to counter to account for drawing of first matching pair
    return index + 2;
};

```
> 3 votes

# Answer
# Python 3, ~~142~~ ~~105~~ 104 bytes

Thanks to *Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ* for saving one byte!

My first answer:

```
import random
i=[x/2 for x in range(int(2*input()))]
d=[]
a=0
random.shuffle(i)
while 1:
 b=i.pop()
 if b in d:
  print(a)
  s
 d=d+[b]
 a+=1

```

My new answer:

```
from random import*
i=range(int(input()))*2
shuffle(i)
j=0
for x in i:
 if x in i[:j]:print(1+j)+s
 j+=1

```

Both exit with a `NameError` on `s`.
> 2 votes

# Answer
## CJam, 17 bytes

```
ri,2*mr{L+:L(&}#)

```

Test it here.
> 2 votes

# Answer
# R, 49

```
N=scan();which(duplicated(sample(rep(1:N,2))))[1]

```

I'm sure there must be a better way of doing this in R! I tried doing something cleverer but it didn't work.

Edit: Improved by @bouncyball since it doesn't have to be a function.
> 2 votes

# Answer
# Python 2, 101 bytes

```
from random import*
d=[]
p=range(input())*2
shuffle(p)
while list(set(d))==d:d+=p.pop(),
print len(d)

```
> 1 votes

# Answer
## VBA, 61 bytes

```
Function K(D):While 2*D-K>K/Rnd:K=K+1:Wend:K=K+1:End Function

```

\- models the shifting probability of sock match given previous failure to match. At the point of evaluation, K is "socks in hand", so draw number is one more.
> 0 votes

# Answer
# Pyth, 14 bytes

```
lhfnT{T._.S*2S

```

Explanation:

```
       ._        #Start with a list of all prefixes of
         .S      #a randomly shuffled
           *2S   #range from 1 to input (implicit), times 2.
  f              #filter this to only include elements where
   nT{T          #element is not equal to deduplicated self (i.e. it has duplicates)
lh               #print the length of the first element of that filtered list

```
> 0 votes

---
Tags: code-golf, random
---


title: Construct the Jacobian matrix

text:
# Question
Title: Construct the Jacobian matrix
Take the vector of unknowns , and apply some generic differentiable function . The Jacobian is then given by a matrix  such that:

For example, suppose `m=3` and `n=2`. Then (using 0-based indexing)

The Jacobian of `f` is then

The goal of this challenge is to print this Jacobian matrix.

# Input

Your program/function should take as input two positive integers `m` and `n`, which represent the number of components of `f` and `u` respectively. The input may come from any source desired (stdio, function parameter, etc.). You may dictate the order in which these are received, and this must be consistent for any input to your answer (please specify in your answer).

# Output

Something which represents the Jacobian matrix. This representation must explicitly spell out all elements of the Jacobian matrix, but the exact form of each term is implementation defined so long as is unambiguous what is being differentiated and with respect to what, and every entry is outputted in a logical order. Example acceptable forms for representing a matrix:

1. A list of lists where each entry of the outer list corresponds to a row of the Jacobian, and each entry of the inner list corresponds to a column of the Jacobian.
2. A string or textual output where each line is a row of the Jacobian, and each delimiter separated entry in a line corresponds to a column of the jacobian.
3. Some graphical/visual representation of a matrix. Example: what is shown by Mathematica when using the `MatrixForm` command
4. Some other dense matrix object where every entry is already stored in memory and can be queried (i.e. you can't use a generator object). Example would be how Mathematica internally represents a Matrix object

Example entry formats:

1. A string of the form `d f_i/d u_j`, where `i` and `j` are integers. Ex: `d f_1/d u_2`. Note that these spaces between `d` and `f_1` or `x_2` are optional. Additionally, the underscores are also optional.
2. A string of the form `d f_i(u_1,...,u_n)/d u_j` or `d f_i(u)/d u_j`. That is, the input parameters of the function component `f_i` are optional, and can either be explicitly spelled out or left in compact form.
3. A formatted graphical output. Ex.: what Mathematica prints when you evaluate the expression `D[f_1[u_,u_2,...,u_n],u_1]`

You may choose what the starting index for `u` and `f` are (please specify in your answer). The output may be to any sink desired (stdio, return value, output parameter, etc.).

# Test cases

The following test cases use the convention `m,n`. Indexes are shown 0-based.

```
1,1
[[d f0/d u0]]

2,1
[[d f0/d u0],
 [d f1/d u0]]

2 2
[[d f0/d u0, d f0/d u1],
 [d f1/d u0, d f1/d u1]]

1,2
[[d f0/d u0, d f0/d u1]]

3,3
[[d f0/d u0, d f0/d u1, d f0/d u2],
 [d f1/d u0, d f1/d u1, d f1/d u2],
 [d f2/d u0, d f2/d u1, d f2/d u2]]

```

# Scoring

This is code golf; shortest code in bytes wins. Standard loopholes are forbidden. You are allowed to use any built-ins desired.

# Answer
> 4 votes
## Python, 63 bytes

```
lambda m,n:["df%d/du%%d "%i*n%tuple(range(n))for i in range(m)]

```

For `m=3,n=2`, outputs

```
['df0/du0 df0/du1 ', 'df1/du0 df1/du1 ', 'df2/du0 df2/du1 ']

```

The string formatting is 1 byte shorter than the more obvious

```
lambda m,n:[["df%d/du"%i+`j`for j in range(n)]for i in range(m)]

```

# Answer
> 3 votes
# R, ~~93~~ 78 bytes

```
function(M,N){v=vector();for(i in 1:N){v=cbind(v,paste0("df",1:M,"/du",i))};v}

```

The numbering is 1-based.

**-15 bytes** thanks to @AlexA. remaks !

# Answer
> 3 votes
# Maxima, 68 bytes

It's too bad I don't know Maxima like I know my dear C and Matlab. But I'll try nontheless.

```
f(m,n):=(x:makelist(x[i],i,m),g:makelist(g[i](x),i,n),jacobian(g,x))

```

Example session using TeXmacs as a Maxima interpreter, mostly for neat math rendering:

There may very well be better ways doing lists and such in Maxima (I would especially like to make the functions appear without the list markers, \[\]), but I don't know the language well enough.

# Answer
> 1 votes
# Ruby, 53 bytes

`f` is 0-indexed, `u` is 1-indexed. Try it online!

```
->m,n{m.times{|i|p (1..n).map{|j|"d f#{i}/d u#{j}"}}}

```

Each row occupies one line as an array representation as seen below. If it isn't compliant to spec, please let me know and I will fix it.

```
["d f0/d u1", "d f0/d u2", "d f0/d u3"]
["d f1/d u1", "d f1/d u2", "d f1/d u3"]

```

# Answer
> 1 votes
# Cheddar, ~~79~~ 49 bytes

```
m->n->(|>m).map(i->(|>n).map(j->"df%d/du%d"%i%j))

```

Apparently a fork of this answer.

For `3,2` returns:

```
[["df0/du0", "df0/du1", "df0/du2"], ["df1/du0", "df1/du1", "df1/du2"]]

```

# Answer
> 0 votes
# Jelly, 18 bytes

```
ps⁴’“ df“/du”ż$€€G

```

Try it out!

Given **(m, n) = (3, 2)**, prints (with spaces marked as `·`:)

```
·df0/du0·df0/du1
·df1/du0·df1/du1
·df2/du0·df2/du1

```

# Answer
> 0 votes
# C, 125 bytes:

```
main(w,y,b,q){scanf("%d %d",&w,&y);for(b=0;b<w;b++){for(q=0;q<y;q++)printf("d f%d/du u%d%s",b,q,q<y-1?", ":"");printf("\n");}}

```

Takes input as 2 space separated integers, `b y`, and outputs the Jacobian Matrix as `y` comma separated strings on `b` lines.

C It Online! (Ideone) or Test Suite (Ideone)

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


title: Simple redstone simulator

text:
# Question
Title: Simple redstone simulator
Redstone is a material in the game Minecraft, and it is used for many complex contraptions. For this program, you will only need to simulate three items: the redstone wire (noted with R), redstone torch (noted with T), and block (noted with B).

Here are a list of basic rules about how redstone works:

```
A redstone torch sends power to any adjacent redstone wire.
TRRRR
 ^This redstone wire is powered.

Redstone wire can only hold power for 15 blocks.
TRRRRRRRRRRRRRRRR
                ^This last wire is unpowered, because the torch is >15 blocks away.

A block is said to be powered if a powered redstone wire is found adjacent to it.
TRRRB
    ^This block is powered.

If a block next to a redstone torch is powered, then the torch stops emitting power.
T
R
R
R
B <This block is powered.
T <This redstone torch does not emit power because of the block next to it.
R <This redstone is unpowered because the torch is not providing power.
R

```

Input will be given in two dimensional arrays up to a size of 64x64, like this:

```
TRRR
   B
TBRTRR
R
RRRRRRRRR
        R
   RRRRRR

```

It is guaranteed that the input will not have any "clocks", or redstone powered by a torch pointing to the block that the torch is on. There will only be one redstone circuit in every input.

Your program must change each character to be a 1 or a 0, 1 indicating if this item is powered/emitting power, and a 0 if it is unpowered/not emitting power.

This input should have this output:

```
1111
   1
100000
1
111111111
        1
   001111

```

This is a code-golf, so shortest code wins, as always.

# Answer
# Haskell, 400

```
import Data.Char
import Data.List
f x=[(++[x]).tail,(x:).init]
h(' ':_)=' '
h('T':s)=if elem 'b's then 'T'else 't'
h('t':s)=h$'T':s
h('B':s)=if any(`elem`s)['e'..'s']then 'b'else 'B'
h('b':s)=h$'B':s
h(_:s)=max 'd'$chr$ord(maximum s)-1
o ' '=' '
o c|elem c"dTB"='0'
o _='1'
a=(map.map)o.(!!(64^2+16)).iterate(map(map h.transpose).transpose.(\l->[g l|g<-id:f(map(const ' ')$head l)++map map (f ' ')]))

```

`map(map h.transpose).transpose.(\l->[g l|g<-id:f(map(const ' ')$head l)++map map (f ' ')])` replaces each tile by a list of itself followed by its four neighbors, then maps that through h. h says for each tile how it reacts to neighbors: Torches turn off ('T' rather than 't') when there's a power block ('b') nearby, wires ('d' for dead through 's') imperfectly copy their most-powered neighbor (though cant get worse than dead), etc.

`iterate` repeats this step, `(!!(64^2+16))` plucks out an iteration at which acyclic circuits are done converging, and I totally wrote it like that to give an intuitive bound, not to land at 400.
> 4 votes

# Answer
# Python, 699

This is just a quick pass (ran out of time for now). It can probably use a lot more golfing.

```
import sys
m=[list(x)for x in sys.stdin.read().split('\n')]
e=enumerate
S=set
s=lambda x:S([(r,c)for r,i in e(m)for c,j in e(i)if j==x])
q=S()
t=s('T')
b=s('B')
n=s('R')
def d(o,r,c,i,h,q):
 if i<0:return 0
 o[(r,c)]=1
 for p in[(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
  if p in q or(p in b and not(r,c)in n):continue
  if(r,c)in b and p in t-q:
   x=S([p])
   q|=x
   o[p]=0
   return 1
  if p in h or not p in o:continue
  h|=S([p])
  if not d(o,p[0],p[1],i-1,h,q):return 1
g=1
while g:
 o=dict(zip(b,[0]*len(b))+zip(n,[0]*len(n))+zip(q,[0]*len(q)))
 g=0
 for x,y in t:
  if not(x,y)in q and d(o,x,y,15,S(),q):g=1
for p in o.keys():m[p[0]][p[1]]=o[p]
print"\n".join(map(lambda x:"".join(map(str,x)),m))

```
> 3 votes

# Answer
# Python 2, 556 bytes

```
c=' 0';L=len;M=map;q=list;r='B';s='16';t='T';u='0';E=enumerate
b=[q(M(lambda x:x+[u,s][x==t],q(w[:-1])))+[c]*(64-L(w))for w in open('redstone.txt')]
k=lambda h,l,z:max(q(M(lambda x:[int((x or c)[1:]),0][l^((x or c)[0]==h)],z)))
def v(d=0):
 for e,f in E(b):
    for g,G in E(f):z=[e!=0and b[e-1][g],g<L(f)-1and f[g+1],e<L(b)-1and b[e+1][g],g and f[g-1]];j=G;i=j[0]+str([[s,u][k(r,1,z)>0],4,4,k(t,0,z),0,max(1,k(r,0,z))-1][ord(j[0])%7]);b[e][g]=i;d=d|(i!=j)
 return d
while v():0
for f in b:print''.join(M(lambda j:[' ',`int(j[1:]!=u)`][j[0]!=' '],f))+'\n'

```

See it in action

* Assumes each line in input ends with a newline
* Outputs via `print()`
* Each line of output ends with lots of whitespace and a newline

---

* Saved lots of bytes thanks to @mbomb007 (#34718)
* Saved 1 byte thanks to @ZacharyT (#55550)
> 3 votes

---
Tags: code-golf, cellular-automata
---


title: Move platforms!

text:
# Question
Title: Move platforms!
## The Challenge

Given either a string (may have newlines), or a two dimensional array, and a positive integer `n`, output the position of the platforms `n` turns after the initial position.

---

`U, D, R, L` are platforms.

`^, v, >, <` are arrows that change the directions of the platforms.

`U, D, R, L` move up, down, right and left, respectively. When an arrow is in front of a platform, it changes the direction.

### Affects platform:

```
R<

```

```
D
^

```

```
v
U

```

```
>L

```

```
>L
 <

```

(top arrow will affect top `L`, but bottom arrow won't affect top `L`)

### Won't affect:

```
 <
R

```

```
>
 L

```

```
v
 U

```

```
D
 ^

```

```
<R

```

(`R` is going right, so `<` won't affect the `R`)

---

For example, if this was the string:

```
>R   <

```

The platform `R` would move right until it's nearly touching the arrow:

```
>   R<

```

After, it would change the direction and start going left:

```
>  R <

```

(even though now it's going left, the letter won't change.)

There are some cases when the platform won't move, such as

```
>R<

```

or

```
v
U
^

```

Last example:

```
v   >
D    Rv
   ^U
^    <

```

After one turn,

```
v   >
    U v
D  ^ R
^    <

```

After one turn,

```
v   >
D    Uv
   ^R
^    <

```

And one more turn:

```
v   >
    R v
D  ^ U
^    <

```

You can assume that the platforms, after `n` turns, won't overlap, that the platforms won't go out of bounds, and that a platform won't touch an arrow that's pointing to the same direction as the platform.

---

## Test Cases

```
Input:
">R   <", 4
Output:
">  R <"

Input:
">R   <", 6
Output:
">R   <"

Input:
">R<", 29
Output:
">R<"

Input:
"v
 U
 ^", 5
Output:
"v
 U
 ^"

Input:
"v

 D
 ^", 1
Output:
"v
 D

 ^"

Input:
"v

 D
 ^", 4
Output:
"v

 D
 ^"

Input:
"v   >
 D    Rv
    ^U
 ^    < ", 2
Output:
"v   >
 D    Uv
    ^R
 ^    <

Input:
">RL<", 3
Output:
">LR<"

Input:
">L  R<", 4
Output:
"> RL <"

Input:
"> RR<
 >L  R <", 6
Ouput:
">RR <
 > RL  <"

Input:
"R   <", 4
Output:
"  R <"

Input:
"R   <", 6
Ouput:
"R   <"

```

---

## Rules

* This is , so shortest answer in bytes wins!
* Standard loopholes are disallowed.

# Answer
# C#, 1245 bytes

```
(i,n)=>{string q="RlherLHEfquDFQUd",D="><v^",H="Rlhe",E="LrHE",X="Dufq",Y="UdFQ",S="#v<>";Func<string,char,int>I=(v,L)=>v.IndexOf(L);Func<char,int,char>z=(y,m)=>q[I(q,y)+m*4];Func<string,char,bool>_=(s,F)=>s.Contains(F);var g=((i as char[][])??((string)i).Split('\n').Select(f=>f.ToCharArray())).ToList();int w=g[0].Length,h=g.Count,u;g=g.Select((r,o)=>r.Select((t,p)=>'R'==t&&w>p+1&&0<=(u=I(D,r[p+1]))?z(t,u):'L'==t&&0<=p-1&&0<=(u=I(D,r[p-1]))?z(t,-1+u):'D'==t&&h>o+1&&0<=(u=I(D,g[o+1][p]))?z(t,-2+u):'U'==t&&0<=o-1&&0<=(u=I(S,g[o-1][p]))?z(t,-u):t).ToArray()).ToList();for(var j=0;j<n;j++){bool L,R,T,B;g=g.Select((r,o)=>r.Select((t,p)=>_(D,t)?t:(R=0<=p-1)&&_(H,r[p-1])?w>p+1&&0<=(u=I(D,r[p+1]))?z(r[p-1],u):r[p-1]:(L=w>p+1)&&_(E,r[p+1])?0<=p-1&&0<=(u=I(D,r[p-1]))?z(r[p+1],-1+u):r[p+1]:(B=0<=o-1)&&_(X,g[o-1][p])?h>o+1&&0<=(u=I(D,g[o+1][p]))?z(g[o-1][p],-2+u):g[o-1][p]:(T=h>o+1)&&_(Y,g[o+1][p])?0<=o-1&&0<=(u=I(S,g[o-1][p]))?z(g[o+1][p],-u):g[o+1][p]:(L&&_(H,t)&&!_(D,r[p+1]))||(R&&_(E,t)&&!_(D,r[p-1]))||(B&&_(Y,t)&&!_(D,g[o-1][p]))||(T&&_(X,t)&&!_(D,g[o+1][p]))?' ':t).ToArray()).ToList();}return string.Join("\n",g.Select(s=>new string(s))).ToUpper().Replace("H","U").Replace("E","D").Replace("F","R").Replace("Q","L").Replace("V","v");};

```

It seemed simpler at first, but then I just kept writing more code. :D

LINQ to enumerate and update the board, changing the character to indicate the direction it's moving. The characters are reverted back before returning. Also assumes that the board is square (so had to modify some of the multi-line test cases to fit this restriction).

Expanded:

```
// Casts to Func<object, int, string> so as to accept both string and char[][] input
(i, n) =>{
    // Shorten constants/functions
    string q = "RlherLHEfquDFQUd", D = "><v^", H = "Rlhe", E = "LrHE", X = "Dufq", Y = "UdFQ",S="#v<>";
    Func<string, char, int> I = (v, L) => v.IndexOf(L);
    Func<char, int, char> z = (y, m) => q[I(q,y) + m * 4]; // Updates the direction of the platform
    Func<string, char, bool> _ = (s, F) => s.Contains(F);

    // Convert either string or char[][] input into common format
    var g = ((i as char[][]) ?? ((string)i).Split('\n').Select(f => f.ToCharArray())).ToList();

    // Get board dimensions
    int w = g[0].Length,h = g.Count,u;

    // Update platforms to reflect the direction they're initially moving
    g = g.Select((r, o) => r.Select((t, p) =>
        'R' == t &&w>p+1&&0<=(u=I(D,r[p+1]))?z(t,u):
        'L' == t &&0<=p-1&&0<=(u= I(D, r[p-1]))?z(t,-1+u):
        'D' == t &&h>o+1&&0<=(u= I(D, g[o+1][p]))?z(t,-2+u):
        'U' == t &&0<=o-1&&0<=(u= I(S,g[o-1][p]))?z(t,-u):t
    ).ToArray()).ToList();

    // Go through each timestep
    for (var j=0;j<n;j++)
    {
        bool L,R,T,B;
        g = g.Select((r, o) => r.Select((t, p) =>
            // Don't change <>^v characters
            _(D,t) ? t :

            // Move platforms going right
            (R=0 <= p - 1) && _(H,r[p-1]) ? w > p+1 && 0<=(u= I(D, r[p+1])) ? z(r[p-1],u) : r[p - 1] :

            // Move platforms going left
            (L=w > p + 1) && _(E,r[p+1]) ? 0 <= p-1 && 0<=(u= I(D, r[p-1])) ? z(r[p+1],-1+u) : r[p + 1] :

            // Move platforms going down
            (B=0 <= o - 1) && _(X,g[o-1][p]) ? h > o+1 && 0<=(u= I(D, g[o+1][p])) ? z(g[o - 1][p],-2+u) : g[o-1][p] :

            // Move platforms going up
            (T=h > o + 1) && _(Y,g[o+1][p]) ? 0<=o-1&&0<=(u= I(S, g[o-1][p]))?z(g[o + 1][p],-u) :g[o+1][p]:

            // Erase platforms that moved
            (L&&_(H,t)&&!_(D,r[p+1]))||
            (R&&_(E,t)&&!_(D,r[p-1]))||
            (B&&_(Y,t)&&!_(D,g[o-1][p]))||
            (T&&_(X,t)&&!_(D,g[o+1][p]))
            ? ' ':

            // Maintain whatever character this was
            t
            ).ToArray()).ToList();
    }

    // Replace direction characters with platform label and join into string return value.
    return string.Join("\n",g.Select(s=>new string(s))).ToUpper().Replace("H", "U").Replace("E", "D").Replace("F", "R").Replace("Q", "L").Replace("V", "v");
};

```
> 2 votes

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


title: Unsorted majorization of two lists

text:
# Question
Title: Unsorted majorization of two lists
### Definition

A vector *a* containing *n* elements is said to majorize or dominate a vector *b* with *n* elements iff for all values *k* such that 1 ≤ *k**n*, the sum of the first element of *a* through the *k*th element of *a* is greater than or equal to the sum of the first through *k*th elements of *b*, where *v* represents the vector *v* sorted in descending order.

That is,

```
                          a_1 >= b_1
                    a_1 + a_2 >= b_1 + b_2
              a_1 + a_2 + a_3 >= b_1 + b_2 + b_3
                              ...
      a_1 + a_2 + ... + a_n-1 >= b_1 + b_2 + ... + b_n-1
a_1 + a_2 + ... + a_n-1 + a_n >= b_1 + b_2 + ... + b_n-1 + b_n

```

where *a* and *b* are sorted in descending order.

For the purpose of this challenge, we will be using a slight generalization of majorization: we will say a list is an *unsorted majorization* of another if all of the above inequalities are true without sorting *a* and *b*. (This is, of course, mathematically useless, but makes the challenge more interesting.)

### Challenge

Given an input of two distinct lists *a* and *b* of integers in the range 0 through 255 (inclusive), both lists of length *n* ≥ 1, output whether the first list unsorted-majorizes the second (*a* \> *b*), the second unsorted-majorizes the first (*b* \> *a*), or neither.

You may optionally require the length of the two lists to be provided as input. The output must always be one of three distinct values, but the values themselves may be whatever you want (please specify which values represent *a* \> *b*, *b* \> *a*, and neither in your answer).

Test cases for *a* \> *b*:

```
[255] [254]
[3,2,1] [3,1,2]
[6,1,5,2,7] [2,5,4,3,7]

```

Test cases for *b* \> *a*:

```
[9,1] [10,0]
[6,5,4] [7,6,5]
[0,1,1,2,1,2] [0,1,2,1,2,1]

```

Test cases for no majorization:

```
[200,100] [150,250]
[3,1,4] [2,3,3]
[9,9,9,9,9,0] [8,8,8,8,8,9]

```

# Answer
# Jelly, ~~10~~ ~~8~~ 6 bytes

**2 bytes thanks to @orlp.**

**2 bytes thanks to @Dennis.**

```
_+\ṠQS

```

Try it online!

`1` for `a>b`, `-1` for `a<b`, `0` for no majorization.

```
_+\ṠQS

_       Difference (vectorized)
 +\     Cumulative sum.
   Ṡ    Sign of every difference
    Q   Deduplicate
     S  Sum

```

If there were both `1` and `-1` present (some cumulative sums are bigger, some smaller), then the last step would produce `0`.
> 6 votes

# Answer
# ngn/apl, 11 bytes

```
{+/∪×+\⍺-⍵}

```

Based on the method in @Leaky Nun's answer.

Given two lists *A* and *B*, find the difference between each value elementwise, or let *C* = *A - B*. Then, find the cumulative sums of *C* and take the sign of each. The sum of the unique sign values will be the result. If *A* \> *B*, the result is 1, if *A* \< *B* the result is -1, and if there is no majority the result is 0.

Try it online.
> 3 votes

# Answer
# Julia, 30 bytes

```
a^b=sum(sign(cumsum(a-b))∪0)

```

Saved 4 bytes thanks to @Dennis!
> 3 votes

# Answer
# Python 3.5, 85 bytes:

```
lambda*e:[all(sum(g[:k])>=sum(h[:k])for k in range(1,-~len(h)))for g,h in[e,e[::-1]]]

```

An anonymous lambda function. Returns `[True,False]` if `a>b`, `[False,True]` if `b>a`, or `[False,False]` if neither of those are true. I hope this is okay.

Try It Online! (Ideone)
> 2 votes

# Answer
# Cheddar, ~~118~~ 114 bytes

```
n->[n.map(i->i[0]-i[1]).map((j,k,l)->l.slice(0,k+1).sum).map(i->i>0?1:i<0?-1:0)].map(j->j has 1?j has-1?0:1:-1)[0]

```

Basically a port of my Jelly answer.

The fact that scope inside function is broken causing inability to define variable inside function means that I would need to do `[xxx].map(i->yyy)[0]` instead of `var a=xxx;yyy`.

Takes transposed array as input.

```
n->[n
.map(i->i[0]-i[1])                     Difference (vectorized)
.map((j,k,l)->l.slice(0,k+1).sum)      Cumulative sum.
.map(i->i>0?1:i<0?-1:0)]               Sign of every difference
.map(j->j has 1?j has-1?0:1:-1)[0]     Deduplicate and Sum

```
> 2 votes

# Answer
# Ruby, ~~72~~ 59 bytes

Returns `1` for `a>b`, `-1` for `a<b`, `0` for neither.

*-13 bytes from cribbing the sum trick off of @Dennis in their Python answer*

Try it online!

```
->a,b{x=y=0;a.zip(b).map{|i,j|(x+=i)<=>y+=j}.uniq.inject:+}

```
> 1 votes

# Answer
# Python 2, 73 bytes

```
a,=b,=r={0}
for x,y in zip(*input()):a+=x;b+=y;r|={cmp(a,b)}
print sum(r)

```

Test it on Ideone.
> 1 votes

# Answer
## Python 2, 59 bytes

```
t=r=0
for x,y in zip(*input()):t+=x-y;r|=cmp(t,0)%3
print r

```

Outputs:

* `1` for `a>b`
* `2` for `b>a`
* `3` for neither

Iterates through the list, tracking the running sum `t` of differences. The number `s` tracks what signs have been seen as a two-bit number `r`: positives in the right bit and negatives in the left bit. This happens via `cmp(t,0)%3`, which gives

* `t>0``+1` → 1
* `t==0``0` → 0
* `t<0``-1` → 2

Taking the `or` of this and the current value of `r` updates the 2 bits with `or`, with zero values having no effect.
> 1 votes

# Answer
# Javascript (using external library-Enumerable) (123 bytes)

```
(a,b)=>(z=(c,d)=>_.Range(1,c.length).All(x=>_.From(c).Take(x).Sum()>=_.From(d).Take(x).Sum()))(a,b)==z(b,a)?0:(z(a,b)?1:-1)

```

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: Pass in vector a and b, create global function z. z will begin by creating an array of integers from 1, for a count of a.length. .All will verify that the predicate is true for every member belonging to a. That predicate says to load a as an enumerable, take a count of that enumerable equivalent to the current iteration value of that range we made, and sum that up. Check if that \>= the same logic from array "b". So, we call z in the order of (a,b), and compare that to the order of (b,a)...if equal we return 0 to signify there is no major. Otherwise, we return 1 if (a,b) is true, else -1
> 0 votes

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


# Question
Title: Help the poor Cryptographers - DLP Edition
## Introduction and Motivation

I'm mainly active on Cryptography.SE and as such have already stumbled across the question: "How the hell am I supposed tools like cado-nfs to *do* stuff!?". They are super-complicated tools for a super-complicated task: Factoring large integers and computing large-scale discrete logarithms.
Now I'm standing here (in a metaphoric sense) and I am asking you:
Please give us poor cryptographers a usable tool. :( This question in particular is about the *discrete logarithm problem* which was broken by Logjam, is frequently used in the world of online security and you're supposed to solve it (as far as current technology goes)!

## Specification

### Input

Your input will be three (potentially) large numbers: A generator, a prime and an argument. The integer encoding should be hex or decimal big-endian. Additionally you may require arbitrary generator and prime dependent state (a bunch of pre-calculations and stuff). The generators, primes and arguments for the score evaluation will **not** be public. But there will be several arguments for one set of generators and primes so caching does make sense here.

### Output

The output is supposed to be one (potentially large) integer, the discrete logarithm of the argument to the base of the generator in the field defined by the prime. Additionally you may output intermediate state that will speed-up future calculations.

### What to do?

Using any library, tool and language you like (no online-services), hit the lowest time of execution for calculating the (correct) discrete logarithm. The parameters will be:

* There will be three pairs of random (safe) prime and an appropriate (small) generator
* Each pair will receive three distinct (random) arguments, for the latter two, intermediate state will speed things up significantly
* The tests will be run on an AWS EC2 c4.large instance
* The tests will use 332-bit (100 decimal digit) primes and arguments

### Who wins?

This is fastest-code so the fastest code wins!
Submissions are evaluated earliest three days after lack of activity (these evaluations cost money!) and clearly inefficient submissions will not be evaluated at all.

**OS:** The submittant has the choice between the default Amazon-provided OSes which are Windows Server (2003 R2 - 2012 R2 Base), Red Hat Enterprise Linux 7.2, SUSE Linux Enterprise Server 12 SP1, Ubuntu Server 14.04 LTS, Debian 8 Jessie (community AMI), CentOS (6 or 7; community AMI) additionally the submittant *can* link to or provide instructions on using / creating a custom Amazon Machine Image (AMI) for testing

Installation instructions or links to those need to be provisioned.

## (Potentially) Helpful resources:

# Answer
Cado-nfs is the right tool to use.

It provides abstract enough way of handling any case, but relies on input specific optimizations that cannot be done by the program anyway.

There is no general (applicable to anything with same efficiency) solution (even theoretical one) for NFS that can be implemented in program at the moment.

Judging by the work done in CADO-nfs, simply coming up with a good enough algorithm for just 100 digit number would take several months of research before any programming can be done.

You should ask around on CADO-nfs forums, there were at least couple of tests mentioning 103-104-digit algorithms, that might be more useful.

If nfs is not a strict requirement, you could mention it in question. Sadly, I cannot comment yet; and no, I am far from specialist in any of the areas.
> 1 votes

---
Tags: math, number-theory, fastest-code, cryptography
---


title: I misspelled my domayn name

text:
# Question
Title: I misspelled my domayn name
According to Alexa rankings, the top 10 websites are:

```
google.com
youtube.com
facebook.com
baidu.com
yahoo.com
wikipedia.org
amazon.com
twitter.com
qq.com
google.co.in

```

Being the top 10 visited websites, these are probably also the top 10 misspelled websites <sup>\[Citation Needed\]</sup>.

# Your task

Your goal is to write a program or function that accepts a string containing a misspelled domain name, and outputs all domain names on the top 10 list that are spelled similarly.

## Rules

* Each input may be up to three characters off from a correct website. A changed character may a substitution (cat -\> cot), addition (cat -\> cant), or removal (cat -\> at).
* Moving a letter counts as two characters changed (the deletion of one character and the addition of another)
* The input will only include the characters a-z, period, and dash
* The name of a website does not include the `http(s)://` or the `www.` The websites are exactly as listed above.
* The program must print out all websites that match the input.
* Case doesn't matter. The test cases will be presented as lower case, but if your program requires upper case, that's fine too.
* As always, no standard loopholes.
* This is , so shortest answer in bytes wins!

# Some test cases

(Input followed by outputs)

```
yahoo.com
yahoo.com (no change for correct spelling)

goggle.com
google.com

wikipedia.organ
wikipedia.org

bidua.cm
baidu.com

.om
qq.com

google.co.i
google.com and google.co.in

google.com
google.com and google.co.in

twipper.com
twitter.com

yahoo.org
yahoo.com

amazing.com
amazon.com

factbook.co
facebook.com

ki-pedia.org
wikipedia.org

google.co.india
google.co.in

goo.com
google.com

aol.com
qq.com

qqzon.com
qq.com and amazon.com

```

## Leaderboards

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

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

```

```
var QUESTION_ID=87174,OVERRIDE_USER=41505;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
> 6 votes
# Mathematica, ~~167~~ 166 bytes

*Saved one byte thanks to Martin Ender*

```
iSelect[{"google.com","youtube.com","facebook.com","baidu.com","yahoo.com","wikipedia.org","amazon.com","twitter.com","qq.com","google.co.in"},#~EditDistance~i<4&]

```

Defines a pure function that returns a list of urls.

The  is this

This answer uses the same method as my NodeJS answer.

# Answer
> 4 votes
# Nim, ~~229~~ ~~205~~ ~~185~~ 174 bytes

```
import strutils,sequtils,future
s=>"googlexyoutubexfacebookxbaiduxyahooxwikipedia.org amazonxtwitterxqqxgoogle.co.in".replace("x",".com ").split.filterIt it.editDistance(s)<4

```

Yep, Nim has a builtin for Levenshtein distance (although it requires an `import`), which is what the question described.

Defines an anonymous procedure, which must be passed to a testing procedure to be used. An testing program is provided below:

```
import strutils,sequtils,future
proc test(d: string -> seq[string]) = echo d #[Your input here]#
test(s=>"googlexyoutubexfacebookxbaiduxyahooxwikipedia.org amazonxtwitterxqqxgoogle.co.in".replace("x",".com ").split.filterIt it.editDistance(s)<4)

```

# Answer
> 3 votes
## JavaScript (ES6), 240 bytes

```
f=
s=>`google.com,youtube.com,facebook.com,baidu.com,yahoo.com,wikipedia.org,amazon.com,twitter.com,qq.com,google.co.in`.split`,`.filter(t=>[...s].map((u,i)=>(q=p=i+1,w=w.map((v,j)=>p=Math.min(++p,q-(u==t[j]),q=++v))),w=[...[...t].keys()])|p<4)
;
```

```
<input oninput=o.textContent=f(this.value).join`\n`><pre id=o>
```

# Answer
> 3 votes
# Python, ~~216~~ ~~200~~ ~~193~~ 183 bytes

```
import editdistance as e
i=raw_input()
print[n for n in"googlexyoutubexfacebookxbaiduxyahooxamazonxtwitterxqqxgoogle.co.in wikipedia.org".replace('x','.com ').split()if e.eval(i,n)<4]

```

The module editdistance calculates the Levenshtein distance, which is the straightforward implementation of what the challenge was asking for.

EDIT: Saved 3 bytes thanks to @shooqie

EDIT 2: Saved another 10 bytes thanks to @shooqie and @Frank

# Answer
> 2 votes
# NodeJS, ~~163~~ ~~161~~ 151 bytes

*10 bytes saved thanks to Copper's Nim solution*

```
x=>"google youtube facebook baidu yahoo wikipedia.org,amazon twitter qq google.co.in".replace(/ /g,".com,").split`,`.filter(y=>require("leven")(x,y)<4)

```

Try it on Tonic

Defines an anonymous function that returns an array of urls.

This solution uses Levenshtein distance, which happens to be exactly what was described by the rules. This answer just selects the urls from an array based on if their Levenshtein distance is small enough.

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