title: CSV for fun and profit (mostly neither)

text:
# Question
Title: CSV for fun and profit (mostly neither)
Similar to the Catalogue of hello world. I want to produce a catalogue of short ways to produce CSV.

# CSV Definition

In this case CSV meaning the more literal interpretation of; A string representation of a list or array separated by commas.

The input types should not be mixed i.e \[1, "hello"\] is NOT valid input

The output should not start with a comma or end with a comma. The output should not contain newline (in any way shape or form).

see example; "John,Henry,Carol,Carl"

# Input

An array of variable length, containing only simple types. The array representation is how your chosen language defines arrays or lists.

# Output

A string representation of the array separated with commas.

# Example

Input: \["John", "Henry", "Carol", "Mike"\]

Output: "John,Henry,Carol,Mike"

# How do I win?

This is , so shortest answer (in bytes) in wins.

## The Catalogue

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

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

```
## 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 snippet:

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

```

```
/* Configuration */

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

/* App */

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

function answersUrl(index) {
  return "http://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 "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

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

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

getAnswers();

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

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

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

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<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,
      });
    else console.log(body);
  });

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

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

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

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

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

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

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

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

}
```

```
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="language-list">
  <h2>Shortest Solution 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>
<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>
<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
# TeaScript, 0 bytes

An empty TeaScript program does this.

TeaScript implicitly adds the input to the operator stack.

The result of the operator stack is outputted. In this case it's the input, due to JavaScript's nature, when it's casted to a string, commas are added.

Try it online

# Answer
> 6 votes
# JavaScript (ES6), 7 bytes

```
a=>a+""

```

an array cast to a string has `,`s implicitly inserted.

# Answer
> 3 votes
# Python 3, 8 bytes

Saved 12 bytes thanks to DSM.

This isn't even close to a complete implementation of the CSV, but it satisfies the letter of what the challenge is looking for.

```
','.join

```

# Answer
> 2 votes
## Haskell, 16 bytes

```
tail.((',':)=<<)

```

Usage example: `tail.((',':)=<<) $ ["john", "henry", "carol", "Mike"]` -\> `"john,henry,carol,Mike"`.

# Answer
> 2 votes
# Pyth, 4 bytes

```
j\,Q

```

Evaluates input and joins by comma. Nothing much to say.

Try it online.

# Answer
> 2 votes
# , 1 char / 2 bytes

```
ï

```

`Try it here (Firefox only).`

This one just outputs the input; however, with arrays, the brackets and quotes are discarded, leaving only the items and commas.

# Answer
> 2 votes
# DUP, 29 bytes

```
[`$~][$'"=^'[=2ø']=||[][,]?]#

```

`Try it here.`

Takes input from STDIN as something like `["asdf","adsf","fdsa"]` because DUP doesn't really have arrays that can hold strings.

# Explanation

```
[   ][                     ]# {while loop}
 `$~                          {read an input char until end of input (-1)}
      $'"=^'[=2ø']=||         {check if input char is [,], or "}
                     [][ ]?   {conditional}
                        ,     {if not, output char}

```

# Answer
> 2 votes
# Python 2, 10 bytes (or may be 8, without assignment)

```
x=','.join

```

Test

```
>>> x(["John", "Henry", "Carol", "Mike"])
'John,Henry,Carol,Mike'

```

# Answer
> 1 votes
## PowerShell, 16 bytes

```
$args[0]-join','

```

Takes input, `-join`s 'em together. PowerShell supports mixed array types without anything special.

**Example**

```
PS C:\Tools\Scripts\golfing> .\csv-for-fun.ps1 ('Doorknob',33,'Martin','Peter')
Doorknob,33,Martin,Peter

```

---

**Additionally**

If you want an *actual* CSV output, PowerShell also has the excellent Export-CSV command. For example, `('Doorknob',33,'Martin','Peter')|epcsv -Path .\c.csv` (with `epcsv` as an alias).

# Answer
> 1 votes
# Jelly, 3 bytes

```
j”,

```

Try it online!

# Answer
> 1 votes
## POSIX sh, 15 bytes

```
IFS=,
echo "$*"

```

### Example

```
# bash, dash, zsh, ksh, mksh... any basically POSIX-compatible shell.
dash -c 'IFS=,;echo "$*"' -- 'Foo B' ar baz
# -> Foo B,ar,baz

```

### Explanation

`$*` is basically `argv[1:].join(IFS[0])`. Double-quoted to avoid further splitting and globbing, which in our case will give us back `a b c`. If you passed something like `a b '*'` in instead, you will find all your files listed due to the globbing.

The positional parameters, i.e. `argv[1:]`, is the basic way to represent arrays in pure POSIX shell scripts. Functions are sometimes used to create new space for holding such parameter lists. You can only have one array working at a time using this technique.

# Answer
> 1 votes
# Milky Way 1.6.5, 10 bytes

```
'C"'[]"-G!

```

---

### Explanation

```
'C          ` push input to the stack as a list of characters
  "'[]"     ` push a string containing a single quote & square brackets
       -    ` remove the characters in the TOS from the STOS
        G!  ` output the remaining characters

```

---

### Usage

```
$ ./mw <path-to-code> -i "['John','Phil','Dave','Matt H.','Matt D.']"
John,Phil,Dave,Matt H.,Matt D.

```

Input should be provided as the string of an array, containing no double quotes.

# Answer
> 1 votes
# Dyalog APL, 11 bytes

```
1↓∊',',¨⍕¨⎕

```

Works even on numbers and mixed datatypes (remove `⍕¨` if unnecessary\`). Takes list of strings as prompted input

prompt for and evaluate input
`',',¨` prepend comma to each
flatten
`1↓` remove initial comma

# Answer
> 1 votes
# Perl 6, 12 bytes

```
{.join: ','}

```

# Answer
> 0 votes
# Mathematica, ~~19~~ ~~30~~ 28 bytes

```
""<>Riffle[ToString/@#,","]&

```

`#~StringRiffle~","&` works if only strings will be input (which nobody actually knows)

# Answer
> 0 votes
# Retina, 3 bytes

```
¶
,

```

`Try it online!`

Takes newline-separated list. If this isn't valid, here's another 6-byte solution that takes a more... *conventional*... format.

```
["{}]
<empty>

```

`Try it online!`

# Answer
> 0 votes
## Lua, 42 Bytes

Simple use of the `table.concat()` function, limiting the type-mixing possibility to only numbers and strings.

```
function f(t)print(table.concat(t,","))end

```

# Answer
> 0 votes
## PHP, ~~37~~ 34 bytes

```
function i($a){echo join(",",$a);}

```

The vast majority of the size comes from setting the function. As a simple call it's just `join(",",$a)`.

If we allow the array to come from the URL:

## PHP, ~~24~~ 21 bytes

```
echo join(",",$_GET);

```

# Answer
> 0 votes
# Gogh, 1 byte

```
s

```

Usage:

```
$ ./gogh noa "s" 'John Mike Henry'

```

See the wiki to understand Gogh's array input.

---

### Explanation

```
     “ Implicit input    ”
s    “ String conversion ”
     “ Implicit output   ”

```

---
Tags: code-golf
---


title: Help me sort my socks!

text:
# Question
Title: Help me sort my socks!
I have a pile of clean socks that I want to sort into pairs. Unfortunately, I can only take socks from either end of the pile, not the middle. Further, I can only remove socks from the pile a matching pair at a time. My strategy is to first split the pile into one or more smaller piles. I think some examples will make this clear. I'll represent each sock as a positive integer (matching integers indicate equal socks).

If the initial pile of socks is

```
1 2 3 3 2 1

```

then I don't have to do any splitting. I can remove both `1` socks, then both `2` socks, then both `3` socks.

If instead the initial pile is

```
1 2 3 2 3 1

```

then I have to split it first because I won't be able to pair all the socks by just removing them from the end. One possibility is to split it into the two piles

```
1 2 3 and 2 3 1

```

Now I can remove the `1` socks, leaving `2 3 and 2 3`, followed by the `3` socks, leaving `2 and 2`, and finally the `2` socks.

## Your Job

Given the initial pile of socks, write a program that will split it into smaller piles that will allow me to sort the socks. Your program should split the pile into the fewest number of piles possible (if there are multiple best solutions, you need only find one).

The input will be given as a list, delimited string, or other convenient form. It will contain only integers between `1` and some maximum value `n`, with each integer occurring exactly twice.

The output should consist of the input list split into smaller lists, given in any convenient form.

## Examples

```
Input             Sample Output
1 1               1 1
1 2 1 2           1; 2 1 2
1 3 2 4 3 2 1 4   1 3 2; 4 3 2 1 4
1 2 3 4 3 4 1 2   1; 2 3; 4 3 4 1 2
1 1 2 2 3 3       1 1 2; 2 3 3
4 3 4 2 2 1 1 3   4 3 4 2; 2 1 1 3

```

Note that this isn't the only allowed output for most of these inputs. For the second case, for example, the outputs `1 2; 1 2` or `1 2 1; 2` would also be accepted.

Thanks to Sp3000 for some test suggestions!

I hate spending a long time sorting my clothes, so make your code as short as possible. Shortest answer in bytes wins!

## Notes

* I don't want to have to look behind a sock to see if its matching pair is there, so taking both socks in a pair from the same end is not allowed. E.g. if the pile is `1 1 2 2` then you wouldn't be able to leave it as one pile and take both `1` socks from the left end.

# Answer
> 7 votes
# Pyth, 25 bytes

```
hf!u #-R.-F{BhMs_BMGGT)./

```

Test suite

Explanation:

```
hf!u #-R.-F{BhMs_BMGGT)./
                       ./    Form all partitions (implicitly) of the input.
 f                           Filter the permutations on
   u                 T)      Run the following function on the partition
                             until it reaches a fixed point:
                _BMG         Bifurcate the lists on reversal
               s             Concatenate
             hM              Take the first element of each list.
                             These elements are all the ones on the ends of lists.
           {B                Bifurcate on deduplication
        .-F                  Bagwise subtraction.
                             Only elements repeated in ends of lists remain.
      -R            G        Remove these elements from each list.
   ' #'                      Filter out empty lists.
  !                          Negate. Only an empty list as fixed point succeeds.
h                            Output the first successful partition.

```

# Answer
> 5 votes
# JavaScript (ES6), 329

Not an easy task for a language that has no combinatorics builtins.

Probably sligthly more golfable.

Note: all partition are at least of size 2, as a partition with a single element is always less useful.

```
Example: [1] [2 3 4] // can take 1 or 2 or 4
Better: [1 2] [3 4] // can take 3 too

```

```
a=>{G=(v,i,u=v)=>{if(i--){for(;r[i]=--u;)if(G(u,i))return 1;}else for(w=[...r,n=l].map((x,i)=>a.slice(z,z=x-~i),z=0),y=w.join`;`;w.map(b=>[0,1].map(q=>(x=b[q*=~-b.length])&&(t[x]?([c,p]=t[x],n-=2,p?c.pop():c.shift(),q?b.pop():b.shift()):t[x]=[b,q])),c=0,t=[]),c;)if(!n)return 1};for(l=a.length,r=[],k=0;!G(l-k-1,k);k++);return y}

```

**Explanation in parts**

(it's overly verbose, but I found it tough to explain - eventually skip to "put it all together")

A recursive function to enumerate all possible splits of an array

```
// v: array length
// i number of splits
// fill the global array r that must exists
G=(v,i,u=v)=>
{
  if(i--)
  {
    for(;r[i]=--u;)
      G(u,i)
  }
  else
  {
    // the current split position are in r, ready to use
    // for instance...
    parts = [...r,a.length].map(x=>a.slice(z,z=x),z=0)
    console.log(r, parts)
  }
};

r=[]
a=['A','B','C','D']
G(4, 2)

// output in console (firebug)
[2, 3] [["A", "B"], ["C"], ["D"]]
[1, 3] [["A"], ["B", "C"], ["D"]]
[1, 2] [["A"], ["B"], ["C", "D"]]

```

Now, I need partitions of size 2 or more, so I must use this function with sligtly different parameters. The parameter v is "array size - number of desired partitions - 1". Then I must build the partitions in a slightly different way.

```
// Same call (4,2), same r, but the array b is of size 7
part = [...r,b.length].map((x,i)=>
          b.slice(z,z=x+i+1) // add 1 more element to each partition
       ,z=0))
// output in console (firebug)
[2, 3] [["A", "B", "C"], ["D", "E"], ["F", "G"]]
[1, 3] [["A", "B"], ["C", "D", "E"], ["F", "G"]]
[1, 2] [["A", "B"], ["C", "D"], ["E", "F", "G"]]

```

So, I can enumerate the list of partitions for no split, 1 split, 2 splits and so on. When I find a working partition I will stop and output the result found.

To check, scan the partition list, note the values at start and end of each, if found a repated value then remove it. Repeat until nothing can be removed, at last: if all pairs were removed then this partition is good.

```
t = []; // array to note the repeated values
// t[x] == [
//           subarray holding value x,
//           position of value x (I care zero or nonzero)
//         ]
n = a.length // counter start, must reach 0
// remember part just in case, because this check will destroy it
result = part.join(';') // a string representation for return value
do
{
  // in the golfed code there is a forr loop
  // all this body is inside the for condition
  c = 0; // init c to a falsy, if a pair is found c becomes truthy
  part.forEach(b=> // b: array, current partition
    [0,1].forEach(q=> ( // exec for 0 (start), 1 (end)
      q *= b.length-1, // now q is the correct index
      x = b[q]) // x is the value at start or end
      x && ( // b could be empty, check that x is not 'undefined'
        t[x] ? // is there a value in t at position x?
           ( // yes, remove the pair
             n-=2, // pair found, decrement counter
             [c, p] = t[x], // get stored array and position
             p ? c.pop() : c.shift(), // remove from c at start or end
             q ? b.pop() : b.shift()  // remove twin value from b
           )
           : // no, remember the value in t
             t[x] = [b, q]
    )) // end [0,1].forEach
  ) // end part.forEach
}
while (c) // repeat until nothing can be removed
if(!n) return 1 // wow, result found (in 'result' variable)

```

Then, the missing part is just a loop caling the G function increasing the partition count. The loop exit when a result is found.

*Put it all together*

```
F=a=>{
  G=(v,i,u=v)=>{
    if (i--)
    {
      for(; r[i]=--u; )
        if (G(u,i))
          return 1;
    }
    else
    {
      w = [...r,n=l].map((x,i)=>a.slice(z, z = x-~i), z = 0);
      y = w.join`;`;
      for(; // almost all the for body is inside the condition
        w.map(b=>
          [0,1].map(q=>
            (x=b[q*=~-b.length])
             &&(t[x]
                ?([c,p]=t[x],n-=2,
                   p?c.pop():c.shift(),
                   q?b.pop():b.shift())
                :t[x]=[b,q])) // end [0,1].map
          ,c=0,t=[] // init variables for w.map
        ),c; // the loop condition is on c
      )
        if(!n)return 1 // this is the for body
    }
  };
  for(l = a.length, r = [], k = 0; !G(l-k-1, k); k++);
  return y
}

```

**Test**

```
F=a=>{G=(v,i,u=v)=>{if(i--){for(;r[i]=--u;)if(G(u,i))return 1;}else for(w=[...r,n=l].map((x,i)=>a.slice(z,z=x-~i),z=0),y=w.join`;`;w.map(b=>[0,1].map(q=>(x=b[q*=~-b.length])&&(t[x]?([c,p]=t[x],n-=2,p?c.pop():c.shift(),q?b.pop():b.shift()):t[x]=[b,q])),c=0,t=[]),c;)if(!n)return 1};for(l=a.length,r=[],k=0;!G(l-k-1,k);k++);return y}

console.log=x=>O.textContent+=x+'\n'

TestData=[[1,1],[1,2,1,2],[1,3,2,4,3,2,1,4],[1,2,3,4,3,4,1,2],[1,1,2,2,3,3],[4,3,4,2,2,1,1,3]]

TestData.forEach(t=>console.log(t+' -> '+F(t)))

function RandomTest() {
  var l=I.value*2
  var a=[...Array(l)].map((_,i)=>1+i/2|0)
  a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v) // shuffle
  Q.textContent=a+''+'\n\n'+F(a).replace(/;/g, ';\n') // better readability
}
```

```
Base test
<pre id=O></pre>
Random test. Number of pairs: <input id=I value=15><button onclick="RandomTest()">-></button>
<pre id=Q></pre>
```

---
Tags: code-golf
---


title: Write a narcissist program!

text:
# Question
Title: Write a narcissist program!
A narcissist program is simple. It is related to a quine.

If the input is equal to it's source code, it prints a truthy value, if not it prints a falsy one. That is it.

Rules:

* It can't read it's own file.
* This is code-golf, so the shortest answer wins.
* Hash functions are *not* allowed. This trivializes it into just string matching.
* The submission may be a function.

An example would be:

Code:

```
someprogramhere

```

Input:

```
someprogramhere

```

Output:

```
1

```

Or input:

```
a

```

Output:

```
0

```

Your code most certainly won't be `someprogramhere`, but you get the idea.

Go code.

# Answer
# JavaScript ES6, 14 bytes

```
$=_=>_==`$=`+$

```

Simple modification of the traditional "bling quine".
> 2 votes

---
Tags: code-golf, quine
---


title: Highest score on the field

text:
# Question
Title: Highest score on the field
### Introduction

Let a field be a rectangle filled with *only* the characters `-` and `[0-9]`. An example of a field is:

```
11-011123
111-010--
0010---01
111-01234

```

You see that this field has been separated into three smaller areas:

To calculate the score of a smaller area, we just add all numbers up. For example:

```
11
111
0010
111

1 + 1 + 1 + 1 + 1 + 0 + 0 + 1 + 0 + 1 + 1 + 1 = 9

```

The total score for this area is **9**. We now do the same thing for the second area:

```
   011123
    010

0 + 1 + 1 + 1 + 2 + 3 + 0 + 1 + 0 = 9

```

The total score is also **9**. Now we have to examine the last area:

```
       01
    01234

0 + 1 + 0 + 1 + 2 + 3 + 4 = 11

```

This has a total score of **11**. The highest score on the field is 11, so this is what we need to output.

### The Task

Given a field (in the form of a 2D string, an array, etc.), output the **highest score** on the field. You may assume that the given fields will *always* contain at least 1 digit. This is , so the submission with the least amount of bytes wins!

### Test cases

Test case 1:

```
Input:
1

Output:
1

```

Test case 2:

```
Input:
1-1-1-1
-1-1-1-
2-1-1-1
-1-1-1-

Output:
2

```

Test case 3:

```
Input:
12-45-
4-65-9
87-654
12-487
45----
684764

Output:
69

```

Test case 4:

```
Input:
111-12
------
21--10

Output:
3

```

# Answer
# MATL, ~~54~~ ~~51~~ 49 bytes

```
n:"G~1@(2Y6Z+leG45>1e*5M@)*]vtz:"otY*g]G48-X:*sX>

```

Input is a 2D char array in MATL(AB) format, with `;` as row separator. The inputs in the example and in the test cases are respectively:

```
['11-011123';'111-010--';'0010---01';'111-01234']
['1']
['1-1-1-1';'-1-1-1-';'2-1-1-1';'-1-1-1-']
['12-45-';'4-65-9';'87-654';'12-487';'45----';'684764']
['111-12';'------';'21--10']

```

**Try it online!**

### Explanation

This works by building an adjacency matrix of the graph defined by the relation "being connected". As an example, consider the 3×4 field

```
52-4
15-8
3-72

```

Entries in a 2D array are easily described in MATL using (column-major) linear indexing. In the 3×4 case, the linear index of each entry is given as

```
1  4  7 10
2  5  8 11
3  6  9 12

```

The adjacency matrix is built in steps using matrix multiplication. In the first step, *immediate* neighbours are considered. For example, the point indexed 3 is neighbour of itself and of that with index 2. It's not a neighbour of 6 because that point doesn't contain a number according to the field. In this example the adjacency matrix of the relation "immediate-neighbour" is the 12×12 matrix **L** given as

```
1 1 0 1 0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 1 1

```

(It can seen that column 3 has value `1` at rows 2 and 3.) This matrix is always symmetric and its diagonal has value `1` for points that don't contain `-`.

The next step would be the adjacency matrix of the relation "connected with *at most one point in between*". To obtain it, it suffices to multiply **L** by itself and set nonzero entries to `1`. In general, the adjacency matrix of the relation "connected by *some* path", **M**, is obtained by raising **L** to an exponent (in matrix sense) that represents the maximum possible path length. An upper bound of the maximum path length is the number of nonzero entries in **L**.

Computing the matrix power directly may cause overflow, because large numbers quickly occur. So it's better to gradually multiply by the same matrix, converting nonzero entries into 1 after each step to prevent large numbers from building up.

Column *i* of **M** represents the points that are connected (by any path) with point *i*. Now, the level field can be reduced to a column vector **c** in linear order, where each entry contains the corresponding number or an undefined value for `-`. So in this case **c** would be

```
5
1
3
2
5
-
-
-
7
4
8
2

```

Mutiplying each column of **M** by **c** element-wise and computing the sum of each column gives, for each point *i*, the total score of the area point *i* belongs to. An area is defined by all points that are mutually connected. Note that many columns will give the same result; namely, columns *i* and *j* will give the same sum if points *i* and *j* are connected (belong to the same area). The final result is the maximum of those sums.

```
        % Implicitly take input: 2D char array
n:      % Range [1,...,N], where N is number of entries in the input
"       % For loop. Each iteration builds a row of matrix L
  G     %   Push input again
  ~     %   Logical negate: transform into matrix of zeros
  1     %   Push 1, to be written into a matrix entry
  @     %   Iteration index. Ranges from 1 to N
  (     %   Write that 1 into the N-th entry (linear order)
  2Y6   %   Push array [0 1 0; 1 1 1; 0 1 0]: mask of immediate neighbours
  Z+    %   Convolve and keep same-size result
  le    %   Linearize into row array
  G45>  %   Array of same size as the input that contains 1 for numbers, 0 for '-'
  1e    %   Linearize into row array
  *     %   Multiply element-wise
  5M    %   Push last array again: 1 for numbers, 0 for '-'
  @)    %   Get 0 or 1 value of that array corresponding to current iteration
  *     %   Multiply. This is to give a row of zeros for non-numbers
]       % End. We have all rows of L in the stack
v       % Concatenate all rows into a matrix: L.
tz:     % Duplicate. Range [1,...,K], where K is the number of nonzeros in L
"       % For loop. Repear K times. This loop computes the 0/1 matrix power
  o     %   Convert matrix entries to double
  tY*   %   Duplicate and matrix-multiply
  g     %   Convert to logical values, that is, nonzero values become 1
]       % End. We have matrix M
G48-    % Convert input chars to the corresponding numbers by subtractig 48
X:      % Linearize into column array. This is vector c
*       % Element-wise multiplication with broadcast (implicit repetition)
s       % Sum of each column. Gives a row array
X>      % Maximum of that row array
        % Implicitly display

```
> 3 votes

# Answer
# JavaScript (ES6), 157 bytes

```
s=>[...o=s].map((n,i)=>o=n<'.'|(a=[...s]).map(_=>a.map((c,j)=>c>'-'&c<10&(a[j+1]|a[j-1]|a[j+l]|a[j-l])>90?a[n-=-c,j]=99:0),a[i]=99)|o>n?o:n,l=~s.search`
`)|o

```

## Explanation

Takes an input field as a string. For each number in the field, sums all numbers in the area. It does this by iterating over each number in the field multiple times, adding the number to the score if an adjacent cell contains a previously counted number. Counted numbers that are part of the area are represented by setting them to 99 so that they are not counted again. Outputs the highest score as a number.

```
var solution =

s=>
  [...o=s].map((n,i)=>o=n<'.'|             // for each number on the field
                                           // n = area score
      (a=[...s])                           // a = array of each field character
      .map(_=>                             // loop to ensure whole area is found
        a.map((c,j)=>                      // for each cell c at index j
          c>'-'&c<10&                      // if the current cell is a number
          (a[j+1]|a[j-1]|a[j+l]|a[j-l])>90 // and an adjacent cells is in the area
          ?a[n-=-c,j]=99:0                 // add the cell to the area
        ),                                 // and the number to the score
        a[i]=99                            // mark the starting cell as counted
      )
      |o>n?o:n,                            // o = output (max of o and n)
    l=~s.search`
`                                          // l = line length of field
  )
  |o                                       // return o
```

```
<textarea id="input" rows="6" cols="40">12-45-
4-65-9
87-654
12-487
45----
684764</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```
> 3 votes

# Answer
# Pyth, 93 bytes

```
A,hlh.zjJ\-.zKsm?qdJd\#HD'b=KXKbJR+i@HbTsm?&&gd0<dlKq@Kd\#'d0[tbhb-bG+bG;Wh=NxK\#=+Y'N)h.MZY

```

Try it online!

## How it works

---

### First step: read the input

```
A,hlh.zjJ\-.zKsm?qdJd\#H
A,                           Assign the following to G and H:
  hlh.z                          G = increment(length(first(all_input())))
       jJ\-.z                    H = join(J="-",all_input())
                m       H    for d in H:
                 ?qdJ            if equal(d,J):
                     d               add d to the list
                                 else:
                      \#             add "#" to the list
                             end
               s             sum the list
              K              assign to K

Sample input:
11-011123
111-010--
0010---01
111-01234

G = 10
H = "11-011123-111-010---0010---01-111-01234" (note the extra dashes connecting each line)
J = "-"
K = "##-######-###-###---####---##-###-#####"

```

### Second step: define a function to evaluate one area

```
D'b=KXKbJR+i@HbTsm?&&gd0<dlKq@Kd\#'d0[tbhb-bG+bG;
D'b                                             ;  def quote(b):
   =KXKbJ                                              K[b] = J
         R+                                            return the sum of A and B, where:
           i@HbT                                         A = to_integer(H[b],10)

                 m                   [tbhb-bG+bG         for d in {dec(b), inc(b), minus(b,G), add(b,G)}:
                  ?&&                                      if .... and ........ and ............... :
                     gd0                                      d>=0
                        <dlK                                           d<len(K)
                            q@Kd\#                                                  equal(K[d],"#")
                                  'd                           add quote(d) to temp_list
                                                           else:
                                    0                          add 0 to temp_list
                s                                        B = sum(temp_list)

Basically, this function (quote) is given a starting
point (b), and then recursively find its neighbour and
add their values to the output.

```

### Third step: read all the areas and find the rqeuired maximum

```
Wh=NxK\#=+Y'N)h.MZY
Wh=NxK\#     )         while inc(N=find(K,"#")):   --while K still has "#"
        =+Y'N              Y+= quote(N)
               .MZY    find the maximum of Y,
              h        then print the first.

```
> 2 votes

---
Tags: code-golf, number, grid
---


# Question
Title: Unlocking the Secrets to a 1-Dimensional Labyrinth
## Background

You awake to find yourself lost in a one dimensional labyrinth! A mystical genie (or something) appears and explains that the exit lies in front of you, but that between you and the exit is a series of challenges. As you wander forward you realize that all of the so-called *challenges* are merely locked doors. You first see a door with a tee-shaped key-hole, and having no such key yourself, retrace your steps, looking for a key with a `T` shape.

Frustrated, you find an alphabet soup of keys on the ground, none of which match the door you've come across. By some stroke of genius (or idiocy), you decide that the lower-case `t`-shaped key might be able to fit in the slot if you jam it in there hard enough. As you approach the door with the lower-case `t` key in hand, the `T` hole glows green and the door dissolves in front of you.

One down, many more to go...

## Challenge

The goal of this challenge is to mark how many steps it takes you to exit the labyrinth.

The input of this challenge is the labyrinth: one string containing only characters `[A-Za-z^$ ]`. Glossary:

* `^` -- The start space. The input will contain exactly one `^`.
* `$` -- The exit (freedom!). The input will contain exactly one `$`.
* `[A-Z]` -- Capital letters signify doors. You can only go through this door if you have already collected the requisite key.
* `[a-z]` -- Lower case letters signify keys. You collect these keys by walking onto the space that contains the key.

There will be at most one of each capital letter in the input. This means the total number of doors will be between 0-26 inclusive.

Every locked door `[A-Z]` will have exactly one corresponding lower case key `[a-z]`. There may be any number of spaces () in the input.

All of the doors will be to the right of the start, and to the left of the exit. Thus there will be no superfluous doors. All inputs will be solvable.

The output for this challenge will be a number, the number of steps it took to exit the labyrinth.

## Algorithm

Your methodical approach to exiting this wretched place is as follows:

* Start at the beginning (`^`) and move forward (right) collecting any keys you come across.
* When you come across a door, if you have the correct key, you proceed forward onto the door. If you don't have the correct key, you walk backwards (left) collecting keys you come across until you find the key for the most recent door that you couldn't open.
* Once you collect the key for the current troublesome door, you turn back to the right and proceed onward.
* Repeat this process until you step on to the exit (`$`).

Experienced golfers will understand that your code doesn't have to implement this specific algorithm as long as it outputs the same result as if you had run this algorithm.

## Counting

Each time you step from one square onto another square, that counts as one step. Turning 180º incurs no additional step. You cannot step forward onto a door without the requisite key. You must step onto a key to pick it up, and must step onto the exit to win. After your first move, the start space (`^`) behaves just like any other regular space.

## Examples

In these examples I've left the spaces as underscores for human-readability.

Input is `_a_^_A__$__`. The output is `11`. You take `1` step forward, notice that you have no key for the `A` door, and then about face. You walk backward until you occupy the space containing the `a` (`3` steps backward, now `4` total). You then walk forward until you occupy the space containing the exit (`7` steps forward, `11` total).

Input is `b__j^__a_AJB_$`. The output is `41` You make two separate trips to the back of the labyrinth, one to get the `j` key, and the next one to get the `b` key.

Input is `__m__t_^__x_T_MX_$____`. The output is `44`. You won't make any extra trip to get the `x` key, as you picked it up on your way from the start to door `T`.

Input is `g_t_^G_T$`. The output is `12`. You cannot move onto the `G` space without a key, and immediately about-face. You're lucky enough to pick up the `t` key on the way to the `g` key, and thus open both doors on your way to freedom.

Input is `_^_____$`. The output is `6`. That was easy.

## I/O Guidelines and Winning Criterion

Standard I/O rules apply. This is a challenge.

# Answer
> 3 votes
# CJam, 45

```
1q_'$#<'^/~\W%:A;ee{~32+A#)_T>{:T+2*+}&]0=)}/

```

Try it online

**Explanation:**

```
1         initial step count; this 1 is actually for the last step :)
q_'$#<    read the input and only keep the part before the '$'
'^/~      split by '^' and dump the 2 pieces on the stack
\W%:A;    take the first piece, reverse it and store it in A
ee        enumerate the other piece (making [index char] pairs)
{…}/      for each [index char] pair
  ~32+    dump the index and character on the stack, and add 32 to the character;
           uppercase letters become lowercase and other chars become garbage
  A#)     find the index of this character in A and increment it (not found -> 0)
  _T>     check if this index (number of steps from '^' back to the key)
           is greater than T (which is initially 0)
  {…}&    if that's true (we need to go back), then
    :T    store that index in T (keeping track of how far we go back before '^')
    +     add to the other index (from the pair, number of steps we took after '^')
    2*    double the result (going back and forth)
    +     add it to the step count
  ]0=     keep only the first value from the bottom of the stack (step count)
           (if the condition above was false, we'd have 2 extra values)
  )       increment the step count (for the current step)

```

# Answer
> 7 votes
# Pyth, 51 bytes

```
JxQ"^"K-xQ"$"JVQI&}NrG1>JxQrN0=JxQrN0=+K*2t-xQNJ;pK

```

sum the distance between the door and its key (doubled, to take the round trip), ignoring the "nested" keys and the distance from the start to the end:

```
JxQ"^"                                              #Initialize the farther point with the starting position
      K-xQ"$"J                                      #Initialize the step counter with the difference between the exit and the start
              VQ                                    #iterate over the input
                I&}NrG1>JxQrN0                      #check if is upper and if the keys is father than one stored (to eliminate nested keys)
                              =JxQrN0               #update the farther key
                                     =+K*2t-xQNJ;   #update step counter with the round trip door<>key
                                                 pK #print the step counter

```

same algorythm in python2.7 :

```
lab=raw_input()
farther_key=lab.index('^')
steps = lab.index('$') - farther_key
for i in lab:
    if i.isupper():
        if farther_key> lab.index(i.lower()):
            farther_key=lab.index(i.lower())
            steps+=((lab.index(i) - farther_key)-1)*2
print steps

```

# Answer
> 5 votes
# Python 2, ~~155~~ ~~154~~ ~~134~~ 128 bytes

Edit: Thanks to @user2357112 and @loovjo for their comments that helped me shave another ~~20~~ 26 bytes off my solution!

```
def f(l):
 i=l.index;b=i('^');t=i('$')-b
 for d in filter(str.isupper,l):
  k=i(d.lower())
  if k<b:b=k;t+=2*(i(d)-k-1)
 print t

```

# Answer
> 4 votes
# C, 136 bytes

```
q,x,p[300],z,c,k;main(i){for(;p[c=getchar()]=++i,c-36;z&&(k+=(x=p[c+32])&&x<q?(q=q>x?x:q,2*i-2*x-1):1))z=p[94],q||(q=z);printf("%d",k);}

```

# Answer
> 4 votes
# PHP 5.3, 123 bytes

This is my first post on Code Golf, hopefully this is of golfing quality high enough for a first post. Definitely a fun challenge and an awesome question!

```
function n($m){while('$'!=$o=$m[$i++])$o=='^'?$b=$i+$c=0:$o>'Z'||$b<=$k=stripos($m,$o))?$c++:$c+=2*$i-3-2*$b=$k;return$c;}

```

This program nicely abuses the fact that PHP doesn't need you to pre-declare any variables before you use them.

It also turned out to be a couple bytes shorter in my final solution to start at 0 and reset the step count when the start character is found, rather than starting at the '^'.

Any tips are definitely welcome!

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

```
s=>(i=c=>s.indexOf(c),p=i`^`,l=i`$`-p,s.replace(/[A-Z]/g,(c,j)=>p>(t=i(c.toLowerCase()))?l+=j-(p=t)-1<<1:0),l)

```

Port of @Rob's Pyth answer.

# Answer
> 2 votes
# Python 2.7, ~~234~~ ~~199~~ 179

```
a=raw_input()
x=a.index
v=x('^')
b=x('$')-v
l=filter(str.islower,a[:v])[::-1]
for i in filter(str.isupper,a):
 k=i.lower()
 if k in l:b+=(x(i)-x(k)-1)*2;l=l[l.index(k)+1:]
print b

```

# Answer
> 1 votes
## AWK, 174 Bytes

```
func f(xmS){x+=S
c=a[x]
if(c~/^[A-Z]/&&!k[c]){C=c
S=-S
s--}else{c=toupper(c)
k[c]=1
s++
if(c==C){S=-S;C=9}}if(c=="$"){print s}else f(x,S)}{split($0,a,"")
f(index($0,"^"),1)}

```

There's probably a tighter algorithm, but this is what I came up with.

Do note that I'm using `gawk`. Some implementations of `AWK` may not split a string on `""` this way.

# Answer
> 1 votes
# C#, 309 bytes

```
class P{static void Main(string[]a){string m=Console.ReadLine(),k="";var f=true;char b,c=b=' ';int j=m.IndexOf('^'),t=0;for(;m[j]!='$';j+=f?1:-1){c=m[j];if(char.IsUpper(c)){if(k.IndexOf(char.ToLower(c))<0){f=!f;b=c;t--;}}if(char.IsLower(c)){k+=c;if(char.ToUpper(c)==b){f=!f;t--;}}t++;}Console.WriteLine(t);}}

```

Ungolfed version:

```
    class P
{
    static void Main(string[] a)
    {
        string m = Console.ReadLine(), k = "";
        var f = true;
        char b, c = b = ' ';
        int j = m.IndexOf('^'), t = 0;
        for (; m[j] != '$'; j += f ? 1 : -1)
        {
            c = m[j];
            if (char.IsUpper(c))
            {
                if (k.IndexOf(char.ToLower(c)) < 0)
                {
                    f = !f; b = c; t--;
                }
            }

            if (char.IsLower(c))
            {
                k += c;
                if (char.ToUpper(c) == b) { f = !f; t--; }
            }

            t++;
        }
        Console.WriteLine(t);
        Console.ReadKey();

    }
}

```

Nothing fancy here, just iterate through the string and change direction based on the character and whether the key is contained in a keys string.

m = the maze string

k = the keys string

f = the direction (true is forward in the maze)

b = the key to search for when backtracking

c = placeholder for m\[j\] to save some bytes due to frequent use

j = the char index of the string to look at

t = the count

Still relatively new to golfing so if you see somewhere I can slim it down, let me know!

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


title: Interpret your lang, but not yourself?

text:
# Question
Title: Interpret your lang, but not yourself?
There are many challenges that say "interpret X", where X is a simple language. In my opinion, that is way too boring. To give all the procrastinating people on the internet something interesting to do, you can try to do this challenge:

## Challenge

Choose a language `$LANG`. `$LANG` can be any turing complete programming language or a turing complete subset of a programming language. Beware that if you omit a feature of your language in `$LANG` for interpretation, you must not use it for your own program, too, since your submission must be written in `$LANG`, too.

Write a compiler / interpreter for `$LANG` written in `$LANG`. You may use all facilities (including `eval` and friends) of your language that are available to write this compiler. To make the task more challenging, there is one restriction: You program should be able to interpret / compile all valid programs of `$LANG` except your interpreter / compiler itself. If it occurs that the program to be interpreted / compiled is your interpreter or compiler itself (regardless of the filename), your program should do something completely unrelated to the functionality of an interpreter or compiler (such as barfing or printing `Hello, world!`).

To make this task even more complex, your program must not read its own source when compiling or interpreting.

## Specifications

* This task is code golf. The submission with the least characters that is correct wins. In case of a tie, the solution that was submitted first wins.
* Your program / script should read the program to be interpreted from a file. You may hardcode its path and name. When the file is read, you may either compile the file to another file (That must be executable on your system) or run it directly. If `$LANG` lacks file-reading capabilities, you can choose another way to read in the code that fits `$LANG`. You may not choose `$LANG` as a subset of another language but with file-reading capabilites removed.
* Usual code-golf rules apply. That is: your personal pet-language that you made up just to solve this challenge is forbidden, if the solution becomes trivial using it (Such as defining a single-char program that exactly implements the solution). Abuse of rules is encouraged.

# Answer
> 8 votes
## Ruby, 63

```
b=$<.read
t="b=$<.read\nt=%p\nb!=t%%t&&eval(b)"
b!=t%t&&eval(b)

```

# Answer
> 11 votes
### Perl, 89 chars, no cheating

```
$_=q($_=q(Q);s/Q/$_/;($q=join"",<>)eq$_?die:eval$q);s/Q/$_/;($q=join"",<>)eq$_?die:eval$q

```

Note that this code is *extremely* picky about what counts as "itself". In particular, it will not recognize itself if there are any trailing newlines or other extra whitespace in the input. To test it, save it into a file named (for example) `unquine.pl` and do this:

```
$ perl unquine.pl unquine.pl
Died at unquine.pl line 1, <> line 1.

```

Remember, the `unquine.pl` file should be *exactly* 89 bytes long, no more, no less. Running it with some other Perl script as input just executes the other script, as it should:

```
$ perl unquine.pl hello.pl
Hello, world!

```

As the name might suggest, the implementation is based on a quine — specifically, this one:

```
$_=q($_=q(Q);s/Q/$_/);s/Q/$_/

```

This code sets `$_` equal to itself; the rest of the program (which, of course, must be duplicated inside `$_`) just compares `$_` to the input, dies if they match and evaluates the input otherwise.

# Answer
> 6 votes
# GolfScript, 30 chars

```
{`".~"+"#{$<.read}".@=!{~}*}.~

```

This program reads the contents of a file named on the command line and, if it does not exactly equal the code above, interprets it as GolfScript. If the input is exactly equal to the code above, it will simply be printed unchanged (except for a newline appended to the end).

This is a fairly straightforward adaptation of this self-identifying program. Specifically:

* `{ }` is a code block literal in GolfScript.
* `.~`, applied to a code block, duplicates the block and executes the copy.

Inside the code block:

* ``` stringifies the copy of the code block.
* `".~"+` appends the characters `.~` to it, yielding a string containing the source code of the program.
* `"#{$<.read}"` is a documented hack that allow the execution of Ruby code within GolfScript. In this case, it executes the Ruby statement `$<.read` (shamelessly stolen from Lowjacker's Ruby solution), which reads and returns the contents of any files specified on the command line. This hack is needed because GolfScript itself provides no explicit file I/O capabilities.
* `.@` duplicates and shuffles the elements on top of the stack so that the stack contains two copies of the file contents followed by the source code of this program.
* `=!` compares the top two items on the stack (i.e. the file contents and the source), returning 1 if they are different and 0 if they are the same.
* `{~}*` evaluates the remaining copy of the file contents as GolfScript code, but only if the result of the comparison is 1. (Technically, it executes the code block `{~}` as many times as given by the number on the stack, i.e. 0 or 1 times. Inside the block, `~` is the GolfScript eval operator.)

**Ps.** If reading the code to execute from stdin is allowed, this challenge can be solved in **21 characters** without having to shell out to Ruby:

```
{`".~"+1$=!{""\~}*}.~

```

This program will read an input string from stdin and, if it does not match its own source, executes it (with an empty input). Like the program above, input that does match the source is simply echoed back.

# Answer
> 5 votes
# Python, 167 130 118 bytes

This is my first attempt at golfing, so here goes! It interprets any program except itself

Improved version:

```
i=open(raw_input()).read();q='i=open(raw_input()).read();q=%s;i==q%%repr(q)and a;exec(i)\n';i==q%repr(q)and a;exec(i)

```

If it gets itself then it barfs with:

```
Traceback (most recent call last):
  File "pygolf.py", line 1, in <module>
    i=open(raw_input()).read();q='i=open(raw_input()).read();q=%s;i==q%%repr(q)and a;exec(i)\n';i==q%repr(q)and a;exec(i)
NameError: name 'a' is not defined

```

I think this solution works pretty much the same way as Ilmari Karonen's, the basic idea is something like:

```
input = read_some_file()
if input == some_quine()
    barf()
interpret(input)

```

The quine I used was based on this one:

```
(lambda x: x + repr((x,)))('(lambda x: x + repr((x,)))',)

```

But I since realized a much shorter quine is:

```
q='q=%s;q%%repr(q)';q%repr(q)

```

And that can be even shorter if you allow the interactive python shell, in which case you can do:

```
'%s;_%%repr(_)';_%repr(_)

```

Since python doesn't have a short way to get command line args, I went with raw\_input() (which is still pretty long, but not as long as

```
import sys;sys.argv[1]

```

Usage is:

```
echo "foobar.py" | python quinterpretter.py

```

or

```
python quinterpretter.py
<type filename and hit enter>

```

I found a shorter quine to use, but here is my old version (for posterity):

```
i=open(raw_input()).read();a if i==(lambda x,y:x+repr((x,y))+y)('i=open(raw_input()).read();a if i==(lambda x,y:x+repr((x,y))+y)', ' else 1;exec(i)\n') else 1;exec(i)

```

# Answer
> 4 votes
I can't exactly read from a file using Javascript (ok, I could, using the HTML5 FileReader thing, but that makes things a lot more complicated than I need). So, this is a function that accepts a Javascript program as a string and runs it.

This probably isn't as golfed as it could be, but here it is anyway:

# Javascript, 252

```
function c(p){q='\"';s='\\';a="function c(p){q='\"';s='\\';a=%;a=a.slice(0,17)+s+a.slice(17,24)+a[23]+a.slice(24);a=q+a.replace('%',q+a+q)+q;alert(a);}";a=a.slice(0,17)+s+a.slice(17,24)+a[23]+a.slice(24);a=a.replace('%',q+a+q);alert(a);if(p!=a)eval(p)}

```

Let me know if anybody knows a better technique for forming a quine in Javascript.

# Answer
> 3 votes
# Common Lisp, 59

```
#+~ #.(#:a)(defun L(p)(compile-file p))(push :~ *features*)

```
* In a fresh Lisp REPL, compile your file (e.g. `sbcl --load`)
* You now have a function `L`, which can compile Common Lisp files
* However, if you call `(L <your file>)`, an error is signaled while *reading* the file.

### Why?

Because the first time, you pushed the `:~` keyword into `*features*`. Now, your environment knows about the `~` feature, and the reader macro `#+`, upon evaluating the `~` feature expression, will succeed and read the following form instead of skipping it as it did the first time. In your file, the following form is `#.(#:a)`, which asks to evaluate `(#:a)` at *read-time* and use the resulting value as the code being read. But `(#:a)` calls the function associated with the uninterned symbol `#:a`. Since `#:a` is uninterned, it is a fresh symbol which is not bound to any function (i.e. not `fboundp`). Error.

# Answer
> 3 votes
# Javascript ES6, 45 bytes

```
$=(_=prompt())=>eval(_==`$=${$};$()`?0:_);$()

```

Still competitive! (thx @Downgoat)

# Answer
> 2 votes
```
read p<p;read c<c;[ "$p" = "$c" ]||. ./c

```

45 characters of sh (POSIX shell). The code to be run must be in the file `./c`.

The code for the interpreter itself must be in the file `./p`, so I guess I kind of cheated, although the challenge doesn't seem to forbid it. Or would this disqualify my "language" from being a "turing-complete programming language"?

Using a tool that's normally an external executable, but might theoretically be built into the shell, the code can be shortened:

```
cmp -s p c||. ./c

```

That's 18 characters, and the `-s` bit is just to suppress a line that would otherwise always be printed for valid (non-self) programs.

And then you can always build a version of the shell language that does the above with more concise syntax.

And then you can always build a program that, when the input consists of a single '.' --or hell, the empty string-- evaluates the contents of another file as normal code, and call this a programming language. So the empty string would be your solution to the challenge, in the language you built. In fact, here's an interpreter for such a language:

```
read code; if [ "$code" ]; then eval "$code"; else . ./othercode; fi

```

Using the language the above script interprets, the solution is the empty string. And the code location needn't be hardcoded anymore.

Problem?

# Answer
> 2 votes
### JavaScript, 135 chars

```
function c(p){q='function c(p){q=%27Q%27;p!=unescape(q).replace(/Q/,q)?eval(p):alert()}';p!=unescape(q).replace(/Q/,q)?eval(p):alert()}

```

Peter Olson's JavaScript solution inspired me to try porting my Perl solution to JS. Like his solution, this code defines a function `c` that accepts a string, and evals it if it's not equal to the code above.

It took me a while to figure out a good way to deal with the absence of balanced string delimiters in JavaScript, until I found what in hindsight is the obvious solution: `unescape()`.

Conveniently, my code doesn't contain any backslashes or double quotes, so it can be safely stored in a double quoted strings. This makes it easy to test:

```
e = "function c(p){q='function c(p){q=%27Q%27;p!=unescape(q).replace(/Q/,q)?eval(p):alert()}';p!=unescape(q).replace(/Q/,q)?eval(p):alert()}"
h = "alert('Hello, world!')"

eval(e)  // defines the function c()

c(h)     // evaluates h
c(e)     // does not evaluate e, alerts "undefined" instead

```

# Answer
> 2 votes
# Scheme, 48 or 51 characters

Scheme is a language with many different implementations. Despite implementations having to conform to the latest RnRS, the latest working standard (R6RS) has been unpopular due to its lack of minimalism. R7RS is soon to be released as a remedy, while splitting the language in 2. The first language being powerful and minimalistic and the second, a superset of the first intended to provide feature extensions for interoperability between implementations. Until then, we rely on SRFIs (Scheme Requests For Implementation), which provide (if implemented in the host implementation or manually (as is common in scheme)) a means to portably accomplish common tasks. All this to say that the first code snippet (51 characters), while remaining as portable as it can, relies on SRFI-22 (executing scheme scripts in UNIX) for access to command-line arguments:

```
(define(main x y)(case y(x => error)(else => load)))

```

or more readably:

```
(define (main current-file arg)
  (case arg
    [current-file => error]
    [else => load]))

```

The second (48 characters) is an file-less means to interpretation which cannot evaluate itself (in a null environment):

```
(define(e)(write(eval(read)null-environment))(e))

```

or more readably:

```
(define (interpret)
  (write (eval (read) null-environment))
  (interpret))

```

# Answer
> 1 votes
# Groovy, 13 bytes

```
{Eval.me(it)}

```

This should interpret a subset of Groovy.

test cases:

```
p={Eval.me(it)}

p'''
    (0..37).each{println"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"[it..it+2]}
'''

p'''
    {Eval.me(it)}
'''

```

Unfortunately while it certainly barfs, it does so in a completely interpreter-like way, and it does it for quite a lot of input.

---
Tags: code-golf, quine, interpreter
---


title: Magic number of a given length

text:
# Question
Title: Magic number of a given length
Your program must take an input (`n` for the purpose of description) and output all permutations of a number that is `n` digits long with no repeating digits, where each of the digits preceding and including its index are divisible by the place in the number that it falls.

You can read about magic numbers here.

## Rules:

* `1 <= n <= 10`
* No digits may be repeated
* The leading 0 must be present (if applicable)
* The 1st through `x`th digit of the number (starting with the first character as 1) must be divisible by `x`, i.e. in `30685`, `3` is divisible by 1, `30` is divisible by 2, `306` is divisible by 3, `3068` is divisible by 4, and `30685` is divislbe by 5.
* The program must take an integer as input (through the command line, as a function argument, etc.) and print all permutations that satisfy the rules.
* Output must be separated by 1 or more white space character
* Permutations **may** start and with zero (so they're not *technically* magic numbers).
* The order of output does not matter
* You do **not** need to handle unexpected input
* Least characters in bytes wins

## Examples

Given 1:

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

```

Given 2:

```
02
04
06
08
10
12
14
16
18
20
24
26
28
30
32
34
36
38
40
42
46
48
50
52
54
56
58
60
62
64
68
70
72
74
76
78
80
82
84
86
90
92
94
96
98

```

Given 10:

```
3816547290

```

Credit to Pizza Hut & John H. Conway for the original puzzle (Option A). Thanks to @Mego and @sp3000 for their links.

# Answer
> 4 votes
# Jelly, ~~20~~ ~~17~~ 16 bytes

```
QḣQV%S
ØDṗçÐḟRj⁷

```

This is *very* slow and memory intensive... Try it online!

### How it works

```
ØDṗçÐḟRj⁷  Main link. Input: n (integer)

ØD         Yield d := '0123456789'.
  ṗ        Compute the nth Cartesian power of d.
      R    Range; yield [1, ..., n].
    Ðḟ     Filter false; keep strings of digits for which the following yields 0.
   ç         Apply the helper link to each digit string and the range to the right.
       j⁷  Join the kept strings, separating by linefeeds.

QḣQḌ%S     Helper link. Arguments: s (digit string), r (range from 1 to n)

Q          Unique; deduplicate s.
 ḣ         Head; get the prefixes of length 1, ..., n or less.
           If s had duplicates, the final prefixes fill be equal to each other.
  Q        Unique; deduplicate the array of prefixes.
   V       Eval all prefixes.
    %      Compute the residues of the kth prefixes modulo k.
           If s and the array of prefixes have different lengths (i.e., if the
           digits are not unique), some right arguments of % won't have corr. left
           arguments. In this case, % is not applied, and the unaltered right
           argument is the (positive) result.
     S     Add all residues/indices. This sum is zero iff all digits are unique
           and the kth prefixes are divisible by k.

```

# Answer
> 6 votes
## JavaScript (Firefox 30-57), 77 bytes

```
f=n=>n?[for(s of f(n-1))for(c of"0123456789")if(s.search(c)+(s+c)%n<0)s+c]:[""]

```

Edit: Saved 1 byte thanks to @edc65.

# Answer
> 3 votes
# MATL, 30 bytes

```
4Y2Z^!"@Sd@!U10G:q^/kPG:\~h?@!

```

Try it online!

It's very slow. For `input 3` it takes a few seconds in the online compiler. To see the numbers appearing one by one, include a `D` at the end of the code.

### Explanation

```
4Y2       % predefined literal: string '0123456789'
Z^        % implicit input. Cartesian power: 2D char array. Each number is a row
!         % transpose
"         % for each column
  @       %   push current column
  Sd      %   sort and compute consecutive differences (*)
  @!U     %   push current column. Convert to number
  10G:q^  %   array [1 10 100 ... 10^(n-1)], where n is the input
  /k      %   divide element-wise. Round down
  P       %   reverse array
  G:      %   array [1 2 ... n]
  \~      %   modulo operation, element-wise. Negate: gives 1 if divisible (**)
  h       %   concatenate (*) and (**). Truthy if all elements are nonzero
  ?       %   if so
    @!    %     current number as a row array of char (string)
          %   implicitly end if
          % implicitly end if
          % implicitly display stack contents

```

# Answer
> 3 votes
# Pyth, 19 bytes

```
jf!s%VsM._TS;.PjkUT

```

Demonstration

A brute force solution. Explanation to follow. Inspiration thanks to FryAmTheEggman

---

# 22 bytes

```
juf!%sThH{I#sm+LdTGQ]k

```

Demonstration

Numbers are built and stored as strings, and only converted to ints to check divisibility.

Explanation:

```
juf!%sThH{I#sm+LdTGQ]k
 u                 Q]k    Apply the following input many times, starting with ['']
             m    G       For each string at the previous step,
              +LdT        Append each digit to it
            s             Concatenate
         {I#              Filter out strings with repeats
  f                       Filter on
     sT                   The integer
    %  hH                 Mod the 1 indexed iteration number
   !                      Is zero.
j                         Join on newlines.

```

# Answer
> 1 votes
# Ruby, 87 bytes

Basic recursive solution.

```
f=->n,x="",j=1{j>n ?puts(x):([*?0..?9]-x.chars).map{|i|f[n,x+i,j+1]if((x+i).to_i)%j<1}}

```

If you're allowed to return a list of the permutations instead of printing, 85 bytes:

```
f=->n,x="",j=1{j>n ?x:([*?0..?9]-x.chars).map{|i|f[n,x+i,j+1]if((x+i).to_i)%j<1}-[p]}

```

# Answer
> 1 votes
## Python, 132 bytes

```
lambda n:[x for x in map(("{:0%s}"%n).format,(range(10**n)))if all(int(x[:i])%i<1and len(set(x))==len(x)for i in range(1,len(x)+1))]

```

Dropped 26 bytes by getting rid of `itertools`, thanks to Sp3000 for making me realize I shouldn't be using it.

Dropped 2 bytes by using a list comprehension rather than `filter`, thanks again to Sp3000 for the tip.

Try it online: Python 2, Python 3

---
Tags: code-golf, permutations
---


title: Rectangle Detection

text:
# Question
Title: Rectangle Detection
Write a program or function that takes in a multiline string of `0`'s and `1`'s. No other characters will be in the string and the string will always be rectangular (all lines will have same number of characters), with dimensions as small as 1×1, but otherwise the `0`'s and `1`'s may be arranged arbitrarily.

You may assume the string has an optional trailing newline, and if desired you may use any two distinct printable ASCII characters in place of `0` and `1`.

Print or return a truthy value if ***all* of the path connected regions of both `0`'s and `1`'s in the string are *solid rectangles***, else output a falsy value.

A *path connected region* of `0`'s means that from any one `0` in the region, all the other `0`'s can be reached by only moving up, down, left and right to other `0`'s (and *not* moving diagonally, *not* moving to any `1`, and *not* moving outside the string bounds). The same idea applies to `1` path connected regions.

A *solid rectangle* of `0`'s means the entire area of the rectangle is filled with `0`'s and no `1`'s. The same idea applies to `1` solid rectangles.

**The shortest code in bytes wins. Tiebreaker is earlier answer.**

(Note that the string does not wrap around with toroidal boundary conditions.)

# Examples

**1)** This input string has 3 path connected regions (2 for `0` and 1 for `1`). Only the bottom right `00` region is a solid rectangle though, so the output would be falsy.

```
0011
0111
0100

```

**2)** This input string has 4 path connected regions (2 for both `0` and `1`). All of them are solid rectangles so the output would be truthy.

```
0011
0011
1100

```

**3)** This input has 2 path connected regions, but only one of them is a solid rectangle, so the output would be falsy.

```
00000000
01111110
00000000

```

**4)** This input has only 1 path connected region and is trivially a solid rectangle, so the output is truthy.

```
11111111
11111111
11111111

```

# Test Cases

A `T` just below the input string means truthy, `F` means falsy.

```
0
T

1
T

00
T

01
T

10
T

11
T

0000000
T

1111111
T

011100100100101100110100100100101010100011100101
T

00
11
T

01
10
T

01
11
F

00
01
F

11
11
T

110
100
F

111
000
T

111
101
111
F

101
010
101
T

1101
0010
1101
0010
T

1101
0010
1111
0010
F

0011
0111
0100
F

0011
0011
1100
T

00000000
01111110
00000000
F

11111111
11111111
11111111
T

0000001111
0000001111
T

0000001111
0000011111
F

0000001111
1000001111
F

1000001111
1000001111
T

1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F
```

# Answer
> 5 votes
# Jelly, 7 bytes

```
ṣ⁷µ=ḢZE

```

This uses the same algorithm as @LevelRiverSt's Ruby answer. The actual algorithm fits in the last 4 bytes; the first 3 bytes are required to parse the input format.

Try it online!

### How it works

```
ṣ⁷µ=ḢZE  Main link. Argument: t (string)

ṣ⁷       Split t at linefeeds..
  µ      Begin a new, monadic link. Argument: A (list of strings)
    Ḣ    Pop the first string of A.
   =     Compare all other strings in A with the first.
         = compares characters, so this yields a list of Booleans for each string.
         For a truthy input, all pairs of lines now have been transformed in lists
         of only 1's or only 0's. That means all columns must be equal.
     Z   Zip; transpose rows with columns.
      E  Check if all rows (former columns) are equal to each other.

```

# Answer
> 16 votes
## Jelly, ~~11~~ 10 bytes

```
ṣ⁷^2\⁺€FS¬

```

Massive thanks to @Dennis for golfing this one down to half its original size (via undocumented features).

Try it online! Note that the triple quotes are for a multiline string.

### Explanation

The basic algorithm is: return true iff every 2x2 subgrid has an even number of 1s (or, equivalently, 0s).

It's clear why an odd number of 1s can't work, since we would have one of the following:

```
10  01  00  00  01  10  11  11
00  00  01  10  11  11  10  01

```

Note that the first 4 are rotations of the same thing, and ditto for the last 4. The reflex angle can't be part of a rectangle, hence why it would be invalid.

In other words, all 2x2 subgrids must be one of the following:

```
00  00  11  01  10  01  10  11
00  11  00  01  10  10  01  11

```

which, if we look at the boundaries, can be imagined as the following "puzzle pieces":

```
 ___    ___    ___    ___
|   |  | | |  |   |  | | |
|   |  | | |  |---|  |-|-|
|___|  |_|_|  |___|  |_|_|

```

And try forming a non-rectangle with those puzzle pieces :) (whilst having the ends match up)

The actual implementation is thus:

```
ṣ⁷               Split input by newlines to give rows
  ^2\            Taking overlapping sets of 2 rows at a time: accumulate rows by XOR
                 Note that strings cast to integers automatically for bitwise operators
     ⁺€          Repeat the previous link (⁺), on each (€) element in the resulting array
       F         Flatten the array
        S        Sum (effectively reducing by OR)
         ¬       Logical negation of the result

```

For example, for the input

```
100
010
000
101

```

we have:

```
  ṣ⁷: ["100", "010", "000", "101"]
 ^2\: [[1, 1, 0], [0, 1, 0], [1, 0, 1]]    (e.g. first entry is "100" ^ "010")
^2\€: [[0, 1], [1, 1], [1, 1]]             (e.g. the first entry is [1^1, 1^0] - this
                                            gives the counts of 1s in each subgrid, mod 2)
   F: [0, 1, 1, 1, 1, 1]
   S: 5                                    (this gives the number of invalid 2x2 subgrids,
                                            which is indeed all but the top left)
   ¬: 0

```

# Answer
> 12 votes
# Ruby, 76

```
->s{j=!r=1
s.lines{|t|i=t.to_i(2)
j&&r&&=(j^i)%t.tr(?0,?1).to_i(2)<1
j=i}
r}

```

In any grid composed entirely of rectangles, each line must be identical to the line before, or have all bits flipped from 0 to 1 and vice versa.

This is easy to prove. Take a piece of paper and draw arbitrary vertical and horizontal lines all the way across it. Now colour the rectangles using only 2 colours. You will end up with a distorted checkerboard, where all the colours flip at each line.

Want to draw rectangles with lines only part way across? try deleting a segment of any of your lines. You will now need more than 2 colours to colour your design, because you will have points where 3 rectangles meet (2 corners and an edge.) Such designs are therefore irrelevant to this question.

I'm surprised answers so far haven't noticed this.

I think this algorithm should be a lot shorter in some other language.

**Ungolfed in test program**

```
f=->s{
  j=!r=1                              #r = truthy, j=falsy
  s.lines{|t|                         #for each line
    i=t.to_i(2)                       #i = value of current line, converted to a number in base 2 (binary)
    j&&                               #if j is truthy (i.e this is not the first line)
      r&&=(j^i)%t.tr(?0,?1).to_i(2)<1 #XOR i with the previous line. Take the result modulo (current line with all 0 replaced by 1)
                                      #if the result of the XOR was all 0 or all 1, the modulo == zero (<1). Otherwise, it will be a positive number.
j=i}                                  #j = value of current line (always truthy in ruby, even if zero)
r}                                    #return 1 or true if all the modulo calculations were zero, else false.

#text to print after test case to check answer is as desired
T='T

'
F='F

'

#test cases
puts f['0'],T

puts f['1'],T

puts f['00
'],T

puts f['01'],T

puts f['10'],T

puts f['11
'],T

puts f['0000000'],T

puts f['1111111'],T

puts f['011100100100101100110100100100101010100011100101'],T

puts f['00
11'],T

puts f['01
10'],T

puts f['01
11'],F

puts f['00
01'],F

puts f['11
11
'],T

puts f['110
100'],F

puts f['111
000'],T

puts f['111
101
111'],F

puts f['101
010
101
'],T

puts f['1101
0010
1101
0010'],T

puts f['1101
0010
1111
0010'],F

puts f['0011
0111
0100
'],F

puts f['0011
0011
1100'],T

puts f['00000000
01111110
00000000'],F

puts f['11111111
11111111
11111111'],T

puts f['0000001111
0000001111'],T

puts f['0000001111
0000011111'],F

puts f['0000001111
1000001111'],F

puts f['1000001111
1000001111'],T

puts f['1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111'],F

```

# Answer
> 3 votes
# Snails, 20 bytes

```
!{to{\0w`3\1|\1w`3\0

```

Prints the area of the grid if there isn't a 2x2 square with 3 zeroes and a one or 3 ones and a zero, or `0` if such a 2x2 square exists.

# Answer
> 3 votes
# MATL, 12 bytes

```
Ybc2thYCs2\~

```

Same algorithm as @sp3000's great answer.

To allow multiline input, MATL needs the row char array (string) to be explicitly built using character `10` for newline. So the input of the four examples are (note that `[]` is concatenation, so each of these is a row array of chars):

```
['0011' 10 '0111' 10 '0100']
['0011' 10 '0011' 10 '1100']
['00000000' 10 '01111110' 10 '00000000']
['11111111' 10 '11111111' 10 '11111111']

```

and the last three test cases are

```
['0000001111' 10 '1000001111']
['1000001111' 10 '1000001111']
['1110100110101010110100010111011101000101111' 10 '1010100100101010100100010101010101100101000' 10 '1110100110010010110101010111010101010101011' 10 '1010100100101010010101010110010101001101001' 10 '1010110110101010110111110101011101000101111']

```

Truthy output is an array containing only ones.

**Try it online!**

### Explanation

This uses the fact that the parity of chars `'0'` and `'1'` is the same as that of numbers `0` and `1`, so there's not need to convert from char to the digit it represents,

```
Yb     % split implicit input by whitespace. Gives a cell array
c      % concatenate cell contents into 2D char array
2th    % push array [2 2]
YC     % get 2×2 sliding blocks and arrange as columns
s      % sum of each column
2\     % modulo 2 of each sum
~      % negate. Implicit display

```

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

Same algorithm of Jelly answer from @Sp3000 (and happy not having to prove it works). Just *8 times* longer

```
s=>[...s].every((x,i)=>[++i,i+=s.search`
`,i+1].some(p=>!(x^=p=s[p],p>`
`))|!x)

```

*Less golfed*

```
s=>[...s].every((x,i)=> // repeat check for every sub square
     [++i,                  // array of position for next char in row
      i+=s.search`\n`, i+1] // and 2 chars at same column in next row
       .some(p=> // for each position
          !(
            x^=s[p],  // xor current value with value at position p
            s[p]>`\n` // true if value at position p is valid
           ) // the condition is negated
       ) // if any value scanned is not valid, .some return true
         // else, we must consider the check for current square
       | !x // x can be 0 or 1, to be valid must be 0
   )

```

**Test suite**

```
f=s=>[...s].every((x,i)=>[++i,i+=s.search`
`,i+1].some(p=>!(x^=p=s[p],p>`
`))|!x)

testData=`
0
T

1
T

00
T

01
T

10
T

11
T

0000000
T

1111111
T

011100100100101100110100100100101010100011100101
T

00
11
T

01
10
T

01
11
F

00
01
F

11
11
T

110
100
F

111
000
T

111
101
111
F

101
010
101
T

1101
0010
1101
0010
T

1101
0010
1111
0010
F

0011
0111
0100
F

0011
0011
1100
T

00000000
01111110
00000000
F

11111111
11111111
11111111
T

0000001111
0000001111
T

0000001111
0000011111
F

0000001111
1000001111
F

1000001111
1000001111
T

1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F`

console.log=x=>O.textContent+=x+'\n'

testData.split('\n\n').forEach(t=>{
  var k=t.slice(-1)=='T',
      r=f(t.slice(0,-1))
  console.log(t+' '+r+ (k==r?' OK\n':' KO\n'))
})
```

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

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

```
s=>!s.split`
`.some((t,i,u)=>[...t].some((v,j)=>v^t[0]^u[0][j]^s[0]))

```

I believe that the path connectedness rectangle criterion is equivalent to requiring that given any four points that form the corners of an arbitrary rectangle that there is an even number of `1`s. Note that the parity of the rectangle (0, b), (x, y) is the same as (0, b), (a, y) `^` (a, b), (x, y) so I only have to check those rectangles whose top left corner is at (0, 0). Also by De Morgan's laws, `!.some()` is the same as `.every(!)` which saves me a couple of bytes.

Edit: I notice that the Jelly solution checks the parity of the corners of all 2×2 rectangles, which can be shown to be equivalent.

# Answer
> 1 votes
## Grime v0.1, 31 bytes

```
E=\0+|\1+
N=.+&E!
e`(E/N|N/E)#!

```

Prints `1` for match and `0` for no match. Try it online!

## Explanation

Grime is my 2D pattern matching language. I did modify it today, but only to change the character of a syntax element (``` instead of `,`), so it doesn't affect my score.

I'm using a similar approach to that of Sp3000: an input is falsy if it contains a 2×N rectangle whose one row contains both `0` and `1`, and the other row does not.

```
E=             Define a nonterminal E, which matches
  \0+|           a horizontal run of one or more 0s, OR
      \1+        a horizontal run of one or more 1s.
N=             Define a nonterminal N, which matches
  .+             a horizontal run of one or more characters,
    &E!          which is NOT matched by E (so contains both 0 and 1).
e`             Match entire input to this pattern:
            !    not
           #     contains
  (E/N|N/E)      E on top of N, or N on top of E

```

# Answer
> 1 votes
# JavaScript (ES6), 64 bytes

```
s=>(a=s.split`
`).every(l=>l==a[0]|l==a[0].replace(/./g,n=>n^1))

```

Based on @LevelRiverSt's observation that each line must either be the same or the opposite of the first.

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


title: Map string to Hilbert curve

text:
# Question
Title: Map string to Hilbert curve
Let's map some strings to 2d space, fractal style. Your task is to compute a Hilbert curve and lay a string along it.

### Task

The task is to take the single-line input string, and lay it out along a Hilbert curve big enough to contain it, but no bigger. Try to make the byte count as low as possible; this *is* after all!

### Conditions

* Any gaps to be padded with whitespace, but padding is not required at the end of lines.
* The start of the line should be in the top-left corner, and the end in the bottom-left.
* You may create a program or function.
* There may be some new test-cases appearing, so don't hardcode anything!

### Bonuses

Note: Bonuses stack like this: `-50% & -20% on 100B` = `-20% on 50B` or `-50% on 80B` = `40B`.

* -50% If the input is a multi-line string, reverse the process to create the original input. Test cases for the bonus: just use the existing ones (including the bonus test cases!)
* -20% If you strip all unnecessary whitespace from the output (e.g. at the end of a line).
* -5% If you don't pollute the global namespace (you know what I mean!)

### Test cases

```
abcdefghijklmn

adef
bchg
 nij
 mlk

The quick brown fox jumps over the lazy dog.

Thn f ju
 ewooxpm
qckr rs
ui btevo
    hlaz
    e  y
      do
      .g

```

And for the whitespace-stripping bonus:

```
No  hitespac  her

Noher

hesc
itpa

```

### Leaderboard

```
/* Configuration */

var QUESTION_ID = 66958; // 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 = 43394; // 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+(?:[.]\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>
```

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

```

# Answer
## CJam, ~~119~~ ~~117~~ ~~113~~ ~~112~~ 109 * 0.5 * 0.8 = 43.6 bytes

*Thanks to Dennis for saving 1 byte.*

Here is a start...

```
{+e`W<e~}:F;q_N-,4mLm]0aa{4\#4e!1=f*\:G[zGGW%zW%G].ff+2/{~.+~}%}@:L/\_N&{N/]z:z:~$1f>sS}{4L#' e]f{f=SF}N*N}?F

```

Test the forward transform. Test the inverse transform.

I'm sure there's a shorter way to generate the curve...

### Explanation

First, I define a function to trim some element from the end of an array, because I need that in several places. It expects the array and the element (inside a separate array) on top of the stack.

```
{
  +  e# Append the element to the array.
  e` e# Run-length encode.
  W< e# Discard last run.
  e~ e# Run-length decode.
}:F; e# Store in F and discard.

```

Now the majority of the code determines the size of the required Hilbert curve and constructs it as 2D array where the elements are indices along the curve. I construct this based on the following observation:

Consider the 2x2 Hilbert curve:

```
01
32

```

The 4x4 Hilbert curve is:

```
0345
1276
ed89
fcba

```

If we subtract the minimum value from each quadrant (and separate them a bit for visual clarity), we get:

```
03 01
12 32

21 01
30 32

```

This pattern holds for any size. It means that we can construct the next level from the current one, by using as the four quadrants: a) the transpose of the current level, b) the current level itself, c) the transpose along the anti-diagonal, d) again the current level itself. And then we offset them 0, 1, 3, 2 times the size of the current level, respectively.

```
q           e# Read input.
_N-         e# Make a copy and remove all linefeeds.
,4mLm]      e# Take that string's length's logarithm with base 4, rounded up.
            e# This is the Hilbert curve level we need.
0aa         e# Push [[0]] as the level-0 Hilbert curve.
{           e# Store the Hilbert curve level in L. Then for each i from 0 to L-1...
  4\#       e#   Compute 4^i. This is the offset of the four quadrants.
  4e!1=     e#   Get [0 1 3 2] as the second permutation returned by 4e!.
  f*        e#   Multiply each of them by the offset.
  \:G       e#   Swap with the Hilbert curve so far and call it G.
  [         e#   Create an array with...
    z       e#     The transpose of G.
    G       e#     G itself.
    GW%zW%  e#     The anti-diagonal transpose of G.
    G       e#     G itself.
  ]
  .ff+      e#   Add the appropriate offsets to the indices in each of the four quadrants.
  2/        e# Split into a 2x2 grid.
  {         e# Map this onto each pair of quadrants...
    ~       e#   Dump both quadrants on the stack.
    .+      e#   Concatenate them line by line.
    ~       e#   Dump the lines on the stack.
  }%        e# Since this is a map, the lines will automatically be collected in an array.
}@:L/

```

Finally, we use this Hilbert curve of indices to apply the appropriate transformation to the input:

```
\_        e# Swap the curve with the input and make another copy.
N&{       e# If the input contains linefeeds, execute the first block, else the second...
  N/      e#   Split the input into lines. The stack now has a grid of indices and a grid
          e#   of characters.
  ]z:z:~  e#   This is some weird transposition magic which zips up the indices with the
          e#   corresponding characters from both grids, and finally flattens the grid
          e#   into a linear list of index/character pairs. Those cells that don't have
          e#   characters due to trimmed whitespace in the input will be turned into
          e#   arrays containing only an index.
  $       e#   Sort the pairs (which sorts them by indices).
  1f>     e#   Discard the indices.
  s       e#   Flatten the result into a single string.
  S       e#   Leave a space on the stack to be trim trailing spaces later.
}{        e# or...
  4L#     e#   Compute the size of the Hilbert curve.
  ' e]    e#   Pad the input to that size with spaces.
  f{      e#   Map this block over lines of the curve, passing the padding input as an
          e#   additional parameter...
    f=    e#     For each index in the current line, select the appropriate character
          e#     from the padded input.
    SF    e#     Trim spaces from the end of the line.
  }
  N*      e#   Join the lines with linefeed characters.
  N       e#   Leave a linefeed on the stack to be trim trailing linefeeds later.
}?
F         e# We left either a space or a linefeed on stack... trim that character from
          e# the end of the string.

```
> 7 votes

# Answer
# Python 3, ~~467~~ ~~434~~ ~~423~~ ~~457~~ ~~451~~ ~~426~~ ~~386~~ ~~374~~ ~~342~~ ~~291~~ 304 * 80% * 95% = 231.04 bytes

The way this works is that I make the Hilbert curve using a Lindenmayer system and follow the left, right and forward instructions along an array of strings. There are probably many ways this could be golfed better, though; especially in the conditionals and in making the array of strings. (I did attempt `[" "*p for i in range(p)]` but strings don't support item assignment (apparently). If I could get that to work, I could get rid of join, too)

**Edit:** Golfed some of the conditionals with thanks to Dennis. And I golfed down the array of strings. And a no-byte change because the results were coming out transposed compared to the examples above.

**Edit:** Implemented the whitespace-stripping bonus.

**Edit:** Fixed a bug in my whitespace-stripping code for six more bytes

**Edit:** Since this answer doesn't pollute the global namespace, I get the 5% bonus, according to wizzwizz4 here.

**Edit:** Changed how `g` is incremented and decremented. Now using `eval()` and `str.translate`.

**Edit:** This answer is now a program instead of a function.

**Edit:** Fixed some bugs from the previous golf.

```
s=input();m=(len(bin(len(s)-1))-1)//2;t=eval("[' ']*2**m,"*2**m);t[0][0],*s=s;x=y=g=0;b="A";exec("b=b.translate({65:'-BF+AFA+FB-',66:'+AF-BFB-FA+'});"*m)
while s:
 c,*b=b;g+=(c<"-")-(c=="-")
 if"B"<c:x,y=[[x+1-g%4,y],[x,y+g%4-2]][g%2];t[x][y],*s=s
print("\n".join(''.join(i).rstrip()for i in t).rstrip())

```

**Ungolfed:**

```
# hilbert(it) is now implemented in the code with exec("b=b.translate")

def hilbert(it):
    s="A"
    n=""
    for i in range(it):
        for c in s:
            if c == "A":
                n += "-BF+AFA+FB-"
            elif c == "B":
                n += "+AF-BFB-FA+"
            else:
                n += c
        s=n;n=""
    return s

def string_to_hilbert(string):
    length = len(string)
    it = (len(bin(length-1))-1)//2
    hil = hilbert(it)
    pow_2 = 2**it
    # we use eval("[' ']*pow_2,"*pow_2) in the code, but the following is equivalent
    output = [[" "for j in range(pow_2)] for i in range(pow_2)]
    output[0][0] = string[0]
    x = 0
    y = 0
    heading = 0
    while string: # while there are still characters in string
        char, *hil = hil
        if char == "-": heading = heading - 1
        elif char == "+": heading = heading + 1
        elif char == "F":
            if heading % 4 == 3: y += 1
            elif heading % 4 == 2: x -= 1
            elif heading % 4 == 1: y -= 1
            else: x += 1
            output[x][y], *string = string
    array = [''.join(i).rstrip()for i in output]
    array = "\n".join(array).rstrip()
    print(array)
    return

```
> 3 votes

# Answer
# Ruby, ~~358~~ ~~356~~ ~~344~~ ~~322~~ 319 * 80% * 95% = 242.44 bytes

This is my Python code transpiled to Ruby. I should write more answers in Ruby. It's a decent language to golf in.

**Edit:** I forgot that functions don't need to be named in this question.

**Edit:** Since this answer doesn't pollute the global namespace, I get the 5% bonus, according to wizzwizz4 here.

```
->s{l=s.size;m=((l-1).bit_length+1)/2;x=2**m;t=(1..x).map{[" "]*x};t[0][0]=s[0];x=y=g=z=0;d=1;b=?A;m.times{b=b.split("").map{|c|c==?A?"-BF+AFA+FB-":c==?B?"+AF-BFB-FA+":c}.join("")};(c=b[z];z+=1;g+=c<?-?1:c==?-?-1:0;(g%2>0?y+=g%4-2:x+=1-g%4;t[x][y]=s[d];d+=1)if c>?B)while d<l;puts (t.map{|i|(i*'').rstrip}*"\n").rstrip}

```

**Ungolfed:**

```
def map_string(string)
  len = string.size
  m = ((len-1).bit_length+1)/2
  pow = 2**m
  output = (1..pow).map{[" "]*pow}
  output[0][0] = s[0]
  x = y = heading = char_index = 0
  chars_in_output = 1
  b = ?A
  m.times do |j|
    a = b.split("").map do |char|
      if char == "A"
        "-BF+AFA+FB-"
      else if char == "B"
        "+AF-BFB-FA+"
      else
        char
      end
    end
    b = a.join("")
  end
  while chars_in_output < len
    char = b[char_index]
    char_index += 1
    if char == "-"
      heading += -1
    else if char == "+"
      heading += 1
    else if char == "F"
      if heading % 2 == 0
        y += heading % 4 - 2
      else
        x += 1 - heading % 4
      end
    end
    output[x][y] = string[char_index]
    char_index += 1
  end
  return (output.map{|i|(i*'').rstrip}*"\n").rstrip

```
> 2 votes

# Answer
# JavaScript (ES6), 227 - 20% : 181.6 bytes

```
m=>{for(n=1<<((33-Math.clz32(m.length-1))/2),t='',y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

```

*Trying to get the 5% bonus*

```
m=>{for(var n=1<<((33-Math.clz32(m.length-1))/2),t='',x,y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(var p,q,u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

```

241 * 0.8 \*0.95 : 183.16 bigger

**Less golfed**

```
m=>
{
  // calc the size of the bounding square, clz32 is a bit shorter than ceil(log2()
  n = 1<<( (33-Math.clz32(m.length-1)) / 2);
  t = '';
  for(y = 0; y < n; y++)
  {
    for(x = 0 ; x < n; x++)
    {
      // for each position x,y inside the square
      // get the index postion in the hilbert curve
      // see https://en.wikipedia.org/wiki/Hilbert_curve (convert x,y to d)
      for(u=y, v=x, h=0, s=n; s >>= 1; )
      {
        h += s*s*(3 * !!(p = u & s) ^ !!(q = v & s));
        q || (p && (u = s+~u, v = s+~v),[u,v]=[v,u])
      }
      // add char at given index to output
      t += m[h]||' '; // blank if beyond the length of m
    }
    t += '\n'; // add newline add end line
  }
  return t.replace(/ +$/mg,'').trim() // to get the 20% bonus
}

```

**Test**

```
F=m=>{for(n=1<<((33-Math.clz32(m.length-1))/2),t='',y=0;y<n;y++,t+=`
`)for(x=0;x<n;x++,t+=m[h]||' ')for(u=y,v=x,h=0,s=n;s>>=1;q||(p&&(u=s+~u,v=s+~v),[u,v]=[v,u]))h+=s*s*(3*!!(p=u&s)^!!(q=v&s));return t.replace(/ +$/mg,'').trim()}

function Test() { O.textContent = F(I.value) }

Test()
```

```
#I { width: 90% }
#O { border: 1px solid #ccc}
```

```
<input id=I oninput='Test()' value='The quick brown fox jumps over the lazy dog.'>
<pre id=O></pre>
```
> 1 votes

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