# Question
Title: Help! My calculator broke! (Turn integer expression into calculator keystrokes)
## Introduction

Help! I accidentally dropped my TI-84 calculator out my window (don't ask how) and it broke. I have a math test tomorrow and the only calculator I can find is one with these buttons:

```
7 8 9 +
4 5 6 -
1 2 3 *
0   = /

```

My math test is a review test on evaluating expressions. I need a program to take an expression such as `1+(5*4)/7` and convert it to the keystrokes needed to solve it on my spare calculator. (And in case you were wondering, this actually happened to me).

## Challenge

Given a non-empty input string containing *only* the characters `0-9`, `(`, `)`, `+`, `-`, `*`, and `/`, output the keystrokes in a space-separated string (eg. `1 + 3 / 3 =`). There must always be an equal sign at the end of the output. Standard loopholes are not allowed.

Examples:

* Input: `1+(5*4)/7`, Output: `5 * 4 / 7 + 1 =`
* Input: `6*(2/3)`, Output: `2 / 3 * 6 =`
* Input: `(7-3)/2`, Output: `7 - 3 / 2 =`

### To make this challenge easier:

* You may assume that the input has a series of keystrokes linked to it that does not require clearing the calculator (`1-(7*3)` is not valid since it would require you to find `7 * 3`, then clear the calculator to do `1 - 21`. All the above examples are valid since there is one, continuous output that does not require the user to clear the calculator and remember a number).
* You may assume that there will only be a single integer after a `/`, as having an input such as `21/(7*3)` would not pass the first assumption either.
* You may assume that there will always be a `*` between an integer and a left parentheses (Valid: `6*(7)`, Invalid: `6(7)`).
* You may assume the input always produces integer output.
* You may assume the input only has three levels of parentheses.

Non-examples

* `2-(14/2)` as you would have to do `14 / 2`, then *clear*, then `2 - 7`.
* `36/(2*3)` as you would have to do `2 * 3`, then *clear*, then `36 / 6`.
* `1024*4/(1*2+2)` as you would have to do `1*2+2`, then *clear*, then `1024 * 4 / 4`.

## Bonuses

* **-5%** if your program can recognize parentheses multiplication (it knows that `6(7)=6*(7)`).
* **-5%** if your program can handle input with decimal numbers (`3.4`, `2.75`, `7.8`) and the output includes `.` (as there must be a `.` key on my spare calculator in this case).
* **-5%** if your program can handle unlimited levels of parentheses.

This is , shortest code in bytes (including the bonuses) wins!

## Leaderboards

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

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

```
## Language Name, N bytes

```

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

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

```

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

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

```

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

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

```

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

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

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

# Answer
# Python 3. ~~337~~ 327 - 10% = 295 bytes

Supports floating-point and unlimited levels of parentheses, so qualifies for **bonus -10%.**

```
import re
def v(s):
 if s[:1]=='(':l,s=e(s[1:]);return l,s[1:]
 m=re.match(r"\d+\.?\d*|\.\d+",s)
 if m:return[m.group()],s[m.end():]
def b(s,f,*O):
 l,s=f(s)
 while s[:1]in O:
  o=s[0]
  r,s=f(s[1:])
  if len(r)>1:l,r=r,l
  l+=[o]+r
 return l,s
m=lambda s:b(s,v,'*','/')
e=lambda s:b(s,m,'+','-')
print(' '.join(e(input())[0]))

```
> 11 votes

# Answer
# TI-BASIC, 605.2 bytes

Eligible for lirtosiast's TI-BASIC bounty under **Fitting but Unsuitable Languages**.

Qualifies for all 3 bonuses, `712 - 15% = 605.2`. There are some golfing opportunities here and there, but I wanted to get this out first, as some of the potential golfs are non-trivial. Please note that TI-BASIC is a tokenized language, and the below is a textual representation of that program. Thus, the program is *not* 1182 bytes, since this program is not encoded under UTF-8. Note that `~` is equivalent to unary negation and `->` to the `STO>` operator. Output is a string, retrievable from `Ans` or `Str1`.

The below program is the result of a few programmer hours thinking and programming, spread over the course of a few weeks.

```
Input "",Str1
0->dim(L1
0->dim(L2
1->I
DelVar S
While I<length(Str1
DelVar T
".->Str3
1->C
While C and I<length(Str1
sub(Str1,I,1->Str2
inString("0123456789.",Str2->C
If C:Then
I+1->I
1->T
Str3+Str2->Str3
End
End
If T=0:Str3+Str2->Str3
sub(Str3,2,length(Str3)-1->Str3
If T=1:Then
expr(Str3->L2(1+dim(L2
End
inString("*+/-",Str3->M
If M:Then
I+1->I
2->T
1->C
While C
dim(L1->C
If C:Then
2fPart(L1(dim(L1))/2)>2fPart(M/2->C
If C:Then
~L1(dim(L1->L2(1+dim(L2
dim(L1)-1->dim(L1
End
End
End
M->L1(1+dim(L1
End
If Str3="(":Then
If S=1:Then
sub(Str1,1,I-1)+"*"+sub(Str1,I,length(Str1)-I+1)->Str1
Else
I+1->I
0->L1(dim(L1)+1
End
End
If Str3=")":Then
I+1->I
While L1(dim(L1
~L1(dim(L1->L2(1+dim(L2
dim(L1)-1->dim(L1
End
dim(L1)-1->dim(L1
End
T->S
End
augment(L2,-seq(L1(X),X,dim(L1),1,-1)->L2
0->dim(L1
1->C
{0,1->L3
For(I,1,dim(L2
L2(I->M
If M>=0:Then
M->L1(dim(L1)+1
Else
If C:Then
L1(dim(L1)-1
Goto S
Lbl A
Ans->Str1
L1(dim(L1->L1(dim(L1)-1
dim(L1)-1->dim(L1
0->C
End
Str1+" "+sub("*+/-",-M,1)+" ->Str1
L1(dim(L1
Goto S
Lbl B
Str1+Ans->Str1
dim(L1)-1->dim(L1
End
End
Goto F
Lbl S
L3Ans->L4
LinReg(ax+b) L3,L4,Y1
Equ►String(Y1,Str2
sub(Str2,1,length(Str2)-3
If C:Goto A
Goto B
Lbl F
Str1

```

## General explanation

Here's the key I worked with while developing the program:

```
Str1        The input string.
Str2        Counter variable (e.g. current character)
Str3        The current token being built.
L1          The operator stack
L2          The output queue
L3          Temporary list
L4          Temporary list
I           Iterator index
T           Type of token (enum)
S           Type of previous token (enum)
M           Temporary variable
C           Conditional variable

Token Types (T)
0           Undefined
1           Number
2           Operator
3           Open Parenthesis

Operator Elements
0           left parenthesis ("(")
1           multiplication ("*")
2           addition ("+")
3           division ("/")
4           subtraction ("-")
5           right parenthesis (")")

Precedence Rule: Remainder(prec, levelno)
0 - add, sub
1 - mul, div
(levelno = 2)

```

And here is the equivalent, hand-written JavaScript code I used to test and develop this program.

```
let Str1, Str2, Str3, L1, L2, I, S, T, M, C;

let error = (type, ...args) => {
    let message = "ERR:" + type + " (" + args.join("; ") + ")";
    throw new Error(message);
};

let isInteger = (n) => n == Math.floor(n);

let inString = (haystack, needle, start=1) => {
    if(start < 1 || !isInteger(start)) {
        error("DOMAIN", haystacak, needle, start);
    }
    let index = haystack.indexOf(needle, start - 1);
    return index + 1;
};

let sub = (string, start, length) => {
    if(start < 1 || length < 1 || !isInteger(start) || !isInteger(length)) {
        error("DOMAIN", string, start, length);
    }
    if(start + length > string.length + 1) {
        error("INVALID DIM", string, start, length);
    }
    return string.substr(start - 1, length);
}

let fPart = (value) => value - Math.floor(value);

// Input "", Str1
Str1 = process.argv[2];
// 0->dim(L1
L1 = [];
// 0->dim(L2
L2 = [];
// 1->I
I = 1;
// DelVar S
S = 0;
// While I<=length(Str1
while(I <= Str1.length) {
    // DelVar T
    T = 0;
    // Disp "Starting",I
    console.log("Starting, I =", I);

    // " read token
    // ".->Str3
    Str3 = ".";
    // 1->C
    C = 1;
    // While C and I<=length(Str1
    while(C && I <= Str1.length) {
        // sub(Str1,I,1->Str2
        Str2 = sub(Str1, I, 1);
        // inString("0123456789",Str2->C
        C = inString("0123456789", Str2);
        // If C:Then
        if(C) {
            // I+1->I
            I++;
            // 1->T
            T = 1;
            // Str3+Str2->Str3
            Str3 += Str2;
        }
    }
    // If T=0:
    if(T == 0) {
        // console.log("Huh?T=0?", Str3, Str2);
        // Str3+Str2->Str3
        Str3 += Str2;
    }

    // " remove placeholder character
    // sub(Str3,2,length(Str3)-1->Str3
    Str3 = sub(Str3, 2, Str3.length - 1);

    // " number
    // If T=1:Then
    if(T == 1) {
        // expr(Str3->L2(1+dim(L2
        L2[L2.length] = eval(Str3);
    }

    // Disp "Str3",Str3
    console.log("post processing, Str3 = \"" + Str3 + "\"");

    // inString("*+/-",Str3->M
    M = inString("*+/-", Str3);
    // " operator
    // If M:Then
    if(M) {
        // I+1->I
        I++;
        // 2->T
        T = 2;
        // Disp "op",M,dim(L1
        console.log("op", M, L1.length);
        // " parse previous operators
        // 1->C
        C = 1;
        // While C
        while(C) {
            // dim(L1->C
            C = L1.length;
            // If C:Then
            if(C) {
                // 2fPart(L1(dim(L1))/2)>2fPart(M/2->C
                C = 2 * fPart(L1[L1.length - 1] / 2) > 2 * fPart(M / 2);
                // If C:Then
                if(C) {
                    // ~L1(dim(L1->L2(1+dim(L2
                    L2[L2.length] = -L1[L1.length - 1];
                    // dim(L1)-1->dim(L1
                    L1.length--;
                }
            }
        }
        // " push current operator
        // M->L1(1+dim(L1
        L1[L1.length] = M;
    }
    // If Str3="(":Then
    if(Str3 == "(") {
        // 3->T
        T = 3;
        // If S=1:Then
        if(S == 1) {
            // sub(Str1,1,I-1)+"*"+sub(Str1,I,length(Str1)-I+1)->Str1
            Str1 = sub(Str1, 1, I - 1) + "*" + sub(Str1, I, Str1.length - I + 1);
        }
        // Else
        else {
            // I+1->I
            I++;
            // 0->L1(dim(L1)+1
            L1[L1.length] = 0;
        }
        // End
    }
    // If Str3=")":Then
    if(Str3 == ")") {
        // I+1->I
        I++;
        // While L1(dim(L1
        while(L1[L1.length - 1]) {
            // ~L1(dim(L1->L2(1+dim(L2
            L2[L2.length] = -L1[L1.length - 1];
            // dim(L1)-1->dim(L1
            L1.length--;
        }
        // End
        // dim(L1)-1->dim(L1
        L1.length--;
    }
    // Disp "Ending",I
    console.log("Ending", I);
    // T->S
    S = T;
    // Pause
    console.log("-".repeat(40));
}

// augment(L2,-seq(L1(X),X,dim(L1),1,-1)->L2
L2 = L2.concat(L1.map(e => -e).reverse());

// Disp L1, L2
console.log("L1", L1);
console.log("..", "[ " + L1.map(e=>"*+/-"[e-1]).join`, ` + " ]");
console.log("L2", L2);
console.log("..", "[ " + L2.map(e=>e<0?"*+/-"[~e]:e).join`, ` + " ]");

// post-processing
let res = "";
// 0->dim(L1
L1.length = 0;
// 1->C
C = 1;
// For(I,1,dim(L2
for(I = 1; I <= L2.length; I++) {
    // L2(I->M
    M = L2[I - 1];
    // If M>=0:Then
    if(M >= 0) {
        // M->L1(dim(L1)+1
        L1[L1.length] = M;
    }
    // Else
    else {
        // If C:Then
        if(C) {
            // L1(dim(L1)-1
            // Goto ST
            // Lbl A0
            // Ans->Str1
            res += L1[L1.length - 2];
            // L1(dim(L1->L1(dim(L1)-1
            L1[L1.length - 2] = L1[L1.length - 1];
            // dim(L1)-1->dim(L1
            L1.length--;
            // 0->C
            C = 0;
        }
        // End
        // Str1+" "+sub("*+/-",-M,1)+" ->Str1
        res += " " + "*+/-"[-M - 1] + " ";
        // L1(dim(L1
        // Goto ST
        // Lbl A1
        // Str1+Ans->Str1
        res += L1[L1.length - 1];
        // dim(L1)-1->dim(L1
        L1.length--;
    }
}
// Goto EF
// Lbl ST
// L3Ans->L4
// LinReg(ax+b) L3,L4,Y1
// Equ►String(Y1,Str2
// sub(Str2,1,length(Str2)-3
// If C:Goto A0
// Goto A1
// Lbl EF
// Str1
console.log(res);

```

I will provide a more in-depth explanation once I'm sure I'm done golfing, but in the meantime, this might help provide a cursory understanding of the code.
> 13 votes

# Answer
## Javascript (ES6), 535 - 80 (15% bonus) = 455 bytes

```
f=z=>{a=[],i=0;c=n=>{while(n[M='match'](/\(/)){n=n[R='replace'](/\(([^()]+)\)/g,(q,p)=>{m=++i;a[m]=c(p);return'['+m+']'})}n=n[R](/(\](?=\[|[\d])|[\d](?=\[))/g,'$1*');n=n[R](/\[?[\d\.]+\]?[*/]\[?[\d\.]+\]?/g,q=>{a[++i]=q;return'['+i+']'});n=n[R](/([\d.]+)\+(\[[\d]+\])/g,'$2+$1');while(n[M](/\[/)){n=n[R](/(\[?[\d\.]+\]?)\*(\[?[\d\.]+\]?)/g,(q,p,r)=>{t=a[r[R](/[\[\]]/g,'')];return r[M](/\[/)?(t&&t[M](/\+|\-/)?(r+'*'+p):q):q});n=n[R](/\[(\d+)\]/g,(q,p)=>{return a[p]+(a[p][M](/\+|-/)?'=':'')})}return n};return c(z)[R](/./g,'$& ')+'='}

```

Not a minimal solution I'm sure, but pretty complete, allowing for all three bonuses. Some instances require multiple pressings of equals key, but do not require clearing of calculator contents. (ex. 3,5,6 & 7 in fiddle)

Link to JSFiddle with some tests: https://jsfiddle.net/2v8rkysp/3/

Here's some unfolded, semi-unobfuscated code with a few comments for good measure.

```
function f(z) {
var a=[],i=0;
function c(n) {
    //// Tokenize parentheses groups recursively
    while (n.match(/\(/)) {
    n = n.replace(/\(([^()]+)\)/g, function(q,p) {
      m = ++i;
      a[m]=c(p);
      return '['+m+']';
    });
    }

    //// Allow implied multiplication with parentheses
    n = n.replace(/(\](?=\[|[\d])|[\d](?=\[))/g, '$1*');

    //// Tokenize mult/division
    n = n.replace(/\[?[\d\.]+\]?[*\/]\[?[\d\.]+\]?/g, function(q) {
      a[++i]=q;
      return '['+i+']';
    });

    //// Move addition tokens to the front
    n = n.replace(/([\d.]+)\+(\[[\d]+\])/g,'$2+$1');

    //// Detokenize
    while (n.match(/\[/)) {
        //// If a token includes addition or subtraction,
        ////   move it to the front of other tokens
        n = n.replace(/(\[?[\d\.]+\]?)\*(\[?[\d\.]+\]?)/g,function(q,p,r) {
          t=a[r.replace(/[\[\]]/g,'')];
          return r.match(/\[/)?(t&&t.match(/\+|\-/)?(r+'*'+p):q):q;
        });
        //// If a token includes addition or subtraction,
        ////   add the equals keypress
        n = n.replace(/\[(\d+)\]/g, function(q,p) {
           return a[p]+(a[p].match(/\+|-/)?'=':'');
        });
    }
    return n;
}
//// Add spaces and final equals keypress
return c(z).replace(/./g, '$& ')+'=';
}

```
> 7 votes

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


title: Find a maximal rectangle of 1s

text:
# Question
Title: Find a maximal rectangle of 1s
## Background

I want to buy an plot of land and build my house on it. My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build on, and I'm having trouble fitting a potential house on the plots. I want you to write a program that analyzes the plots for me.

## Input and output

Your input is a rectangular 2D array of bits, of size at least 1×1, in any reasonable format. The array represents a plot of land; `1`s are "good" areas where I could build my house, and `0`s are "rocky" areas where the house cannot be built.

Your output shall be the maximal area of a solid rectangle of `1`s in the input array. It represents the area of the largest house I could build on the plot. Note that if there are no `1`s in the input, then the output is `0`.

## Example

Consider the input

```
101
011
111

```

The largest rectangle of `1`s is the 2×2 rectangle in the lower right corner. This means that the correct output is `4`.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

## Test cases

```
0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12

```

# Answer
> 13 votes
# Jelly, ~~21~~ ~~20~~ ~~18~~ 17 bytes

```
ṡṂ€€×"
‘×¥\ç"Ụ€FṀ

```

Try it online! or verify all test cases.

### Background

Let **M** be a matrix of bits such as

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

```

We start by counting the number of **1** bits in each column of **M**, resetting the count every time we encounter a **0** bit.

For our example matrix, this gives

```
0 0 0 1 1 0 0 0 0
1 1 0 2 2 0 0 1 0
2 2 0 3 3 1 1 2 0
3 3 0 0 4 2 2 0 0
0 4 0 0 5 3 3 1 1
1 5 1 1 6 4 4 2 2
2 6 2 2 0 5 5 3 0

```

Next, we compute all contiguous sublists of each row. We achieve this by generating all slices of length **k**, where **k** varies between **1** and the number of entries in each row.

For the penultimate row, this gives

```
[1], [5], [1], [1], [6], [4], [4], [2], [2]
[1, 5], [5, 1], [1, 1], [1, 6], [6, 4], [4, 4], [4, 2], [2, 2]
[1, 5, 1], [5, 1, 1], [1, 1, 6], [1, 6, 4], [6, 4, 4], [4, 4, 2], [4, 2, 2]
[1, 5, 1, 1], [5, 1, 1, 6], [1, 1, 6, 4], [1, 6, 4, 4], [6, 4, 4, 2], [4, 4, 2, 2]
[1, 5, 1, 1, 6], [5, 1, 1, 6, 4], [1, 1, 6, 4, 4], [1, 6, 4, 4, 2], [6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4], [5, 1, 1, 6, 4, 4], [1, 1, 6, 4, 4, 2], [1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4], [5, 1, 1, 6, 4, 4, 2], [1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2], [5, 1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2, 2]

```

Next, we map each slice to the product of its minimum and its length. For each slice, this computes the area of the rectangle of **1** bits of maximum height that has the given slice as bottom row.

For the slices of length **3** of the penultimate row of our example matrix, this gives

```
3 3 3 3 12 6 6

```

All that's left to do is take the maximum across all slices of all rows.

For our example matrix, this gives **12**.

### How it works

```
‘×¥\ç"Ụ€FṀ  Main link. Argument: M (2D list of bits)

   \        Reduce the columns of M by the link to the left.
  ¥           Combine the two atoms to the left into a dyadic chain.
‘               Increment the left argument.
 ×              Multiply the result with the right argument.
      Ụ€    Grade up each; yield the indices of each row of M, sorted by their
            values. The order is not important here; we just need the indices.
    ç"      Apply the helper link to each element of the result to the left and
            the corresponding element of the result to the right.
        F   Flatten the resulting, nested list.
         Ṁ  Extract the maximum.

ṡṂ€€×"      Helper link. Arguments: R (row), X (indices of R)

ṡ           For each k in X, split R into overlapping slices of length k.
 Ṁ€€        Compute the minimum of each individual slice.
    ×"      Multiply the minima of all slices of length k by k.

```

# Answer
> 6 votes
# MATL, ~~32~~ ~~31~~ 27 bytes

```
n:"@:"@1M2$ltntG4$bZ+=a*vX>

```

This uses a brute-force 2D convolution-based approach. All possible rectangle sizes are created and convolved with the terrain. The maximum result of all convolutions is the maximal rectangle area.

This is an extremely inefficient solution because in order to save bytes, I create kernels for all rectangles between `[1, 1]` and `[numel(input) numel(input)]` rather than actually determining the number of rows/columns in the input to determine the proper rectangle dimension ranges.

*Thanks to @Luis for suggesting the usage of `M` and omitting the `]]`.*

**Try it Online!**

**Explanation**

```
        % Implicitly grab input as a 2D numeric array
n       % Compute the number of elements in the input (over estimation of max kernel size)
:       % Create array 1:n
"       % For each value
  @     % Current loop index
  :     % Create an array from 1:(current_index)
  "     % For each of these values
    @   % Push the current index onto the stack
    1M  % Grab the input to the previous function call (the outer index)
    2$l % Create an array of 1's whose dimensions are specified by top two stack elements
    tn  % Duplicate this array and compute number of elements
    t   % Duplicate this number
    G   % Explicitly grab input
    4$b % Bubble up the 4th element from the stack (the kernel)
    Z+  % Perform 2D convolution of this kernel and the input
    =a  % Determine if any convolution result (in each column) is equal to the area of the kernel.
        % This yields a row vector
    *   % Multiply the logical result by the area
    v   % Vertically concatenate all results (forces the row vectors above to be column vectors)
    X>  % Compute the maximum yielding the largest area
        % Implicitly display the result.

```

# Answer
> 5 votes
# Julia, ~~83~~ ~~60~~ ~~57~~ 53 bytes

```
!M=M⊆1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)

```

Try it online! The last test case exceeds TIO's time limit, but I've verified it locally.

### How it works

First, **!** checks if its matrix argument **M** consists entirely of **1**'s.

* If so, **!** returns the sum of **M**'s entries, which is equal to its area.
* If not, **!** does the following:

1. Rotate **M** by , **90°**, **180°** and **270°** clockwise.
    2. Remove the first row of each of the four rotations, effectively removing one of top row, bottom row, leftmost column and rightmost column of **M**.
    3. Call itself recursively on each of the submatrices.
    4. Return the maximum of the return values from the recursive calls.

# Answer
> 4 votes
## JavaScript (ES6), 97 bytes

```
a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

```

Turns out bit twiddling still wins. Accepts an array of array of integers. Ungolfed:

```
function rect(array) {
    var max = 0;
    for (var i = 0; i < array.length; i++) {
        var bits = array[i];
        for (var j = 0; i + j < array.length;) {
            var row = array[i + j];
            j++;
            var size = 0;
            for (var k = 0; k < row.length; k++) {
                if (!row[k]) bits[k] = 0;
                size = ones[k] ? size + j : 0;
                if (size > max) max = size;
            }
        }
    }
    return max;
}

```

The array is sliced by rows as per the other answers, so each possible range of rows is looped over. Given a range of rows, the next step is to measure the available rectangles. This is achieved by ANDing the rows together bitwise; the result is a list of bits which were set in the entire range of rows. It then remains to find the maximal length of set bits in the row and multiply that by the height of the range. Test shamelessly stolen from @ed65:

```
f=
a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

// test cases as strings, converted to 2d arrays
result.textContent = [
  ['0', 0],
  ['1', 1],
  ['00 00', 0],
  ['01 10', 1],
  ['01 11', 2],
  ['111 010 111', 3],
  ['101 011 111', 4],
  ['0111 1110 1100', 4],
  ['1111111 1110111 1011101', 7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000', 20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110', 12]
].map(t => t[0].replace(/ /g, '\n') + '\n' + t[1] + '\n' + f(t[0].split` `.map(r => [...r]))).join`\n\n`
```

```
<pre id=result></pre>
```

# Answer
> 4 votes
# Python 2.7, ~~93~~ ~~91~~ ~~89~~ ~~81~~ 79 bytes

```
f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)

```

Input is a list of tuples. Verify the smaller test cases here and the larger test cases here.

Without memoization, the last two test cases exceed Ideone's time limit, as they require, resp., **1,530,831,935** and **2,848,806,121** calls to **f**, which takes **39** and **72** minutes on my machine.

### Algorithm

For a given matrix **M**, the general idea is to iterate over all submatrices of **M** by removing top rows and rotating quarter turns counterclockwise, keeping track of the sizes of encountered submatrices that consist entirely of **1** bits.

Golfing a straightforward recursive implementation of the above idea lead to a function **f(M)** that does the following.

1. If **M** doesn't contain any **0** bits, return its number of **1** bits.
2. If we have rotated **M** two times already and it doesn't contain any **1** bits, return **0**.
3. If we have rotated **M** five times already, return **0**.
4. Recursively call **f** on **M** without its top row.
5. Recursively call **f** on **M** rotated a quarter turn counterclockwise.
6. Return the maximum of the return values from the recursive calls.

### Code

In the implementation, we use an additional function argument **t** that defaults to **1** to keep track of how many times we have rotated this particular matrix already. This allows condensing steps 1 to 3 into a single step by testing ``t/3`in`M`` and returning ``M`.count(`t`)` if the test fails.

1. If **t = 1**, we haven't rotated this particular submatrix previously in this branch.

**t / 3 = 0**, so ``t/3`in`M`` will return **True** iff the string representation of **M** contains the character **0**.

If it doesn't, we return ``M`.count(`t`)`, the number of times the character **1** appears in the string representation of **M**.

Note that a matrix without **0** bits can occur only if **t = 1**, since we do not recurse in this case.
2. If **3 ≤ t ≤ 5**, we've previously rotated this particular submatrix at least two times in this branch.

**t / 3 = 1**, so ``t/3`in`M`` will return **True** iff the string representation of **M** contains the character **1**.

If it doesn't, we return **0** computed as ``M`.count(`t`)`, the number of times the string representation of **t** (i.e., the character **3**, **4** or **5**) appears in the string representation of **M**.
3. If **t = 6**, we've previously rotated this particular submatrix five times in this branch.

**t / 3 = 2**, so ``t/3`in`M`` will return **False**, because the string representation of **M** does not contain the character **2**.

We return **0** computed as ``M`.count(`t`)`, the number of times the character **6** appears in the string representation of **M**.

If **f** didn't return already, the remaining steps are executed.

4. `f(M[1:])` calls **f** on **M** without its top row. Since **t** isn't specified, it defaults to **1**, signaling that this is the first time **f** encounters this particular submatrix in this branch.
5. `f(zip(*M)[::-1],t+1)` calls **f** on **M** rotated a quarter turn counterclockwise, incrementing **t** to keep track of the time we've rotated this particular submatrix in this branch.

The quarter turn is obtained by zipping the rows of **M** with each other, returning tuples of the corresponding elements of **M**'s rows, thus transposing **M**, then reversing the order of rows (i.e., placing the top row at the bottom and vice versa).
6. Finally `max` returns the maximum of the return values from the recursive calls.

# Answer
> 3 votes
# APL (Dyalog Extended), ~~27~~ ~~23~~ 20 bytes

*-3 bytes by Adám and ngn*

```
{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}

```

Try it online!

```
{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}    Monadic function taking an argument ⍵:
                 ⍳⍴⍵     Indices: e.g. for a 3x7 array
                                       (1 1) (1 2) ...  (1 7)
                                       (2 1) (2 2)  ... (2 7)
                                       (3 1) (3 2)  ... (3 7)
    (×/×⍵⍷⍨⍴∘1)         Helper fn: Takes ⍵ and x (e.g. (2 2))
            ⍴∘1             Make an array of 1s of shape x. Call it a.
        ⍵⍷⍨                 All places where a exists in x
     ×/                      Product of x's dims (size of a)
       ×                 Size of a where a is in ⍵, and 0 elsewhere.
    (×/×⍵⍷⍨⍴∘1)¨        Call the helper function on x and each (¨) index.
                            We now have a nested list containing sizes of blocks in ⍵
                            and many 0s.
   ∊                        Flatten
 ⌈/                        Find the maximum value.

```

# Answer
> 2 votes
# JavaScript (ES6), 154 ~~176~~

*Edit* tried to shorten a bit, but cannot compete against @Neil's solution

Try every possible rectangle, return the max size. Probably the same algorithm of the Matl answer, just 6 times longer.
Input as a 2d array of integers

```
g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

```

*Less golfed*

This is the original algorithm, the golfed version abuse a lot of array traversing function istead of for loops

```
g=>{
  v = 0
  for(i = h = g.length; i; i--)
    for(j = w = g[0].length; j; j--)
    {
      p = true
      for(k=0; p && k <= h-i; k++)
        for(l=0; p && l <= w-j; j++)
          p = g.slice(k, k+i).some(r=>r.slice(l, l+j).some(x=>!x));
      if (!p && i*j<v)
        v = i*j
    }
  return v
}

```

**Test**

```
f=g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

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

// test cases as strings, converted to 2d arrays
;[
  ['0',0],['1',1],['00 00',0],['01 10',1],['01 11',2],
  ['111 010 111',3],['101 011 111',4],
  ['0111 1110 1100',4],['1111111 1110111 1011101',7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000',20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110',12]
].forEach(t=>{
  var k=t[1]
  var p=t[0].split` `.map(r=>[...r].map(x=>+x))
  var r=f(p)
  console.log((r==k?'OK':'KO')+' '+r+(r==k?'':' expected '+k)+'\n'+p.join`\n`+'\n')
  })
```

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

# Answer
> 2 votes
# Brachylog, ~~20~~ ~~17~~ 15 bytes

*Thanks to Kroppeb for 2 bytes*

```
{s\sc≡ᵛ¹l}ᶠ⌉|hh

```

Try it online!

### Explanation

```
{        }ᶠ      Find all possible outputs of the following predicate:
 s                Find a sublist of the array (i.e. remove 0 or more rows from the top
                  and/or bottom)
  \               Transpose the array
   s              Find a sublist again
                  The result is some sub-rectangle of the array
    c             Concatenate all the rows in that rectangle into one list
     ≡ᵛ¹          Verify that all the elements are 1
        l         Get the length (i.e. how many 1's make up the rectangle)
                 Now we have a list of the sizes of all possible 1-rectangles
           ⌉     Take the maximum

            |    If no 1-rectangles could be found:
             hh   Take the head of the head of the array (i.e. the top left element)
                 Since the array contains no 1's in this case, this will give 0

```

# Answer
> 1 votes
# , ~~129~~ 122 bytes

```
function(M,D=dim(M),L=`for`){L(i,1:D,L(j,1:D[2],L(r,0:(D-i),L(c,0:(D[2]-j),F<-max(F,i*j*(i*j==sum(M[r+1:i,c+1:j])))))))
F}

```

Try it online!

Plain and simple brute force approach.

Unrolled code and explanation :

```
function(M){                       # M is the matrix of 0/1
n = 0                              # n is the biggest rectangle found
R=nrow(M)
C=ncol(M)
for(i in 1:R)                      # for each possible num of rows of the rectangle
  for(j in 1:C)                    # for each possible num of cols of the rectangle
    for(r in 0:(R-i))              # for each possible position offset on the rows
      for(c in 0:(C-j){            # for each possible position offset on the cols

         subM = M[1:i+r,1:j+c]     # sub-set the matrix given the size of rectangle and offsets

         if(sum(subM)==i*j)        # if sub-matrix is full of 1's
            rec = i*j              # (i.e. nrow*ncol == sum of values in sub-matrix)
         else                      # store the rectangle area
            rec = 0                # otherwise store 0

         n = max(n,rec)            # keep the maximum rectangle found
      }
}

```

# Answer
> 1 votes
# Stax, 14 bytes

```
π└ÿ§L▓═J║φ§╦╢9

```

Run and debug it

# Answer
> 0 votes
# Matlab 106 bytes

```
x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r

```

Ungolfed:

```
x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result

```

The operation in the loop starts with 2D convolution `conv2()` of input array with the `p*m` array of ones. `==p*m` checks if the resulting array contains an element equal to `p*m`. The corresponding element is turned to `1`, all other elements are turned to `0`. `any()` turns the array into vector. Columns containing at least one nonzero entry are turned to `1`, otherwise `0`. `p*m*()` multiplies the vector by `p*m` thereby turning all `1`-s into `p*m`. `[__,r]` square brackets concatenate the obtained result with the previous maximum area stored in `r`. Finally, `max()` finds the maximum value in the resulting vector.

# Answer
> 0 votes
## Matlab ~~(222)~~(209)

Actually ,this solution brings me shame for being double-sized the actual same-language solution but ... blimey, i had been thinking of it for 6 hours! and the trick is a slightly different build off from Dennis and Neil 's answers.

```
    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end

```
* The function is called as

```
y=[1 1 1 0 1 1 0 0 0;
1 1 0 1 1 1 1 0 0;
0 0 1 1 1 1 1 1 0;
0 1 1 1 1 1 1 1 1;
0 0 1 1 1 1 1 1 0;];
t=g(y,y,[],0,0,0);t,

```
* I could save more bytes if introduced matrix length in function's dimentions, eventhough, more golfing is ongoing.
* How does this proceed?

This algorithm adds the actual matrix to itself shifted of it to left direction, with a bit twiddling (&). in any stage the resulted matrix is set as initial and added to itself shifted upward repeatedly,then reloop from the beginning with the new matrix. All sub-elements of all the matrices generated by this operation `(original_matrix+shifted_matrix)&shifted_and_original_matrices)` are maximized to the output.

**example:**

```
     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4

```

# Answer
> 0 votes
# Japt, 30 bytes

```
®åÏ*°X}ÃÕ®£ZãYÄÃm®rm *Zl}Ãc rw

```

Try all test cases

Approximately a port of Dennis's Jelly answer. The test cases are simply 2D arrays of numbers, converted from the question's format using this.

Explanation:

```
®      Ã                          #For each row:
 å    }                           # Replace each number with this running total:
    °X                            #  Increment the previous total
  Ï*                              #  Multiply it by the current number
        Õ                         #Transpose rows and columns
         ®               Ã        #For each column:
          £    Ã                  # Iterate over the range [0..length) as Y:
           ZãYÄ                   #  Get the subsections of that column with length Y+1
                m®      }         # For each subsection:
                  rm              #  Get the minimum
                     *Zl          #  Multiply it by the length
                          c       #Flatten everything to a single list of possible rectangle sizes
                            rw    #Get the maximum

```

# Answer
> 0 votes
# , 38 bytes

```
,"0/&(1+i.)/@$>./@,@:((#**/)@,;._3"$)]

```

Try it online!

## how

```
,"0/&(1 + i.)/@$ >./@,@:((# * */)@,;._3"$) ]
              @$                             NB. pass the shape of
                                             NB. the input (rows, cols)
                                             NB. to...
,"0/&(1 + i.)/                               NB. this verb, which will
    &(1 + i.)/                               NB. will first create 2
                                             NB. lists: 1...num rows
                                             NB. and 1...num cols.
,"0/                                         NB. and then creat a cross
                                             NB. of every possible
                                             NB. concatenation of the two,
                                             NB. giving us all possible
                                             NB. rectangle sizes. pass
                                             NB. that and...
                                           ] NB. the original input
                 >./@,@:((# * */)@,;._3"$)   NB. to this verb, which
                                   ;._3"$    NB. will take every
                                             NB. possible rectangle of
                                             NB. every size,
                                 @,          NB. flatten it and...
                         (# * */)            NB. multiply the size of
                                             NB. the list by the list's
                                             NB. product, yielding the
                                             NB. size of the list if it's
                                             NB. all ones, zero otherwise.
                     ,@:                     NB. Flatten all those results
                                             NB. into one big list
                 >./@                        NB. and take the max.

```

---
Tags: code-golf, array, optimization
---


title: Draw some expanding arrows

text:
# Question
Title: Draw some expanding arrows
This challenge is about printing a series of growing ASCII-art arrows. I'll describe the pattern in words, but it might be easier to look at what the start of this series looks like:

```
>
<
->
<-
-->
<--
--->
<---
---->
<----
----->
<-----
------>
<------
...

```

An arrow with length n contains an arrowhead (`<` or `>`) and `n-1` dashes (`-`). A right-facing arrow has the dashes first, then a `>`. A left-facing arrow starts with `<`, and is followed by the dashes. The series consists of a length `n` right-facing arrow followed by a length n left-facing arrow, with n from 1 to infinity.

To complete the challenge, write a program or function that takes one input, an integer `i >= 1`, and outputs the first `i` arrows. Arrows are individual, not in right-left pairs, so for `i=3` you should output:

```
>
<
->

```

You can return a list of strings, or print them one after the other. If printing, the arrows must be delimited by some consistent delimiter, which doesn't have to be a newline as in the example.

This is , so fewest bytes wins.

# Answer
> 9 votes
# Canvas, 10 bytes

```
⇵-×<ｎ¹［↔｝］

```

Try it here!

# Answer
> 8 votes
# , 69 bytes

```
for(i in 1:scan()-1)cat('<'[i%%2],rep('-',i/2),'>'[!i%%2],'
',sep='')

```

Try it online!

* -5 bytes thanks to @Giuseppe
* -3 bytes thanks to @Robert S.

# Answer
> 8 votes
# Java (JDK), 81 bytes

```
n->{for(int i=0;i<n;)System.out.printf(i%2<1?"<%s%n":"%s>%n","-".repeat(i++/2));}

```

Try it online!

## Explanations

```
n->{                  // int-accepting consumer
 for(int i=0;i<n;)    //  for each i from 0 to n-1 included
  System.out.printf(  //   output on stdout with a pattern
   i%2<1              //    if i is even:
    ?"<%s%n"          //     use the left-arrow pattern
    :"%s>%n",         //    else: use the right-arrow pattern
   "-".repeat(i++/2)  //    fill the "%s" in the pattern with i/2 dashes, and increment i
  );                  //
}                     //

```

# Answer
> 8 votes
## Haskell, ~~41~~ 40 bytes

```
(`take`g">")
g p=p:('<':init p):g('-':p)

```

Try it online!

Plain old recursion: start with string `p` = `">"`, collect `p`, a `<` in front of all but the last char of `p` and a recursive call with one `-` put in front of `p`. Take the first `n` items of this list.

Edit: -1 byte thanks to @xnor.

# Answer
> 6 votes
# Python 2, 54 bytes

thanks to the and Jo King for fixing a bug.

```
k=0
exec"print k%2*'<'+k/2*'-'+~k%2*'>';k+=1;"*input()

```

Try it online!

# Answer
> 6 votes
# Commodore BASIC V2 (C64), 94 bytes

```
0inputn:fOi=1ton:oniaN1gO1:?"<";
1on-(i<3)gO2:fOj=1.5toi/2:?"-";:nE
2on-nOiaN1gO3:?">";
3?:nE

```

Not entirely sure about the byte count, this is based on the text representation for typing the valid program. It's a bit shorter on disk (91 bytes) because BASIC V2 uses a "tokenized" representation of programs.

### Online Demo

Slightly "ungolfed":

```
0 inputn:fori=1ton:oniand1goto1:print"<";    :rem read n from user, loop to n, if odd skip "<"
1 on-(i<3)goto2:forj=1.5toi/2:print"-";:next :rem skip for i<3, print (i-1)/2 times "-"
2 on-notiand1goto3:print">";                 :rem if even skip ">"
3 print:next                                 :rem newline and next loop iteration

```

# Answer
> 6 votes
# Self-modifying Brainfuck, 55 bytes

Take input as character code.
Only support input up to 255.
Use null character to separate lines.

Coincidentally, all arrow-drawing characters are used as BF commands. Unfortunately, it doesn't save any bytes (currently).

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

```

Try it online!

### Explanation

```
 Code  |              Memory         | Output | Comment
-------+-----------------------------+--------+--------------------------
       | '<' '>' '-' [0]  0   0   0  |        |
>>,    | '<' '>' '-'  0   0  [x]  0  |        |
[      |                             |        |
       | '<' '>' '-'  l   0  [x]  0  |        | l = arrow length
<<[-<  |                             |        | copy l to next cell
.>>+<] |                             |        | and print '-'
       | '<' '>' '-' [0]  l   x   0  | -----  | there are l '-'s
<<.    | '<' [>] '-'  0   l   x   0  | >      |
>>.+   | '<' '>' '-' [1]  l   x   0  | <null> |
>>-    | '<' '>' '-'  1   l  [y]  0  |        | y=x-1
[      |                             |        | execute if y>0
<<<<<. | [<] '>' '-'  1   l   y   0  | <      |
>>>>   | '<' '>' '-'  1  [l]  y   0  |        |
[-<+<. |                             |        |
>>]    | '<' '>' '-'  L  [0]  y   0  | -----  | L=l+1
.      | '<' '>' '-'  L  [0]  y   0  | <null> |
>-<]>] |                             |        | decrement y
<>-    |                             |        | do nothing, used as data

```

# Answer
> 5 votes
# Pyth, 17 bytes

```
m_W%d2+*\-/d2@"><

```

Output is a list of strings. Try it online here.

```
m_W%d2+*\-/d2@"><"dQ   Implicit: Q=eval(input())
                       Trailing "dQ inferred
m                  Q   Map [0-Q), as d, using:
          /d2            Floored division of d by 2
       *\-               Repeat "-" the above number of times
      +                  Append to the above...
             @"><"d      Modular index d into "><" - yields ">" for even d, "<" for odd
                         - examples: d=4 gives "-->", d=7 gives "---<"
 _W                      Reverse the above if...
   %d2                   ... (d % 2) != 0
                       Implicit print result of the map

```

# Answer
> 5 votes
# PowerShell, ~~62~~ ~~56~~ 50 bytes

```
param($n)(0..$n|%{($j='-'*$_)+'>';"<$j"})[0..--$n]

```

Try it online!

Loops from `0` up to input `$n`, each iteration creating two arrow strings. Those are then indexed with `0..--$n` to pull out the correct number of elements.

*Saved 6 bytes thanks to KGlasier.*

# Answer
> 5 votes
# Haskell, ~~51~~ 44 bytes

<sup>-7 bytes thanks to xnor (using `iterate` over list-comprehension)!</sup>

```
(`take`do b<-iterate('-':)"";[b++">",'<':b])

```

Try it online!

## Explanation / Ungolfed

Using `do`-notation saves us a `concat`, and using infix-notation allows a pointfree function with `take`, undoing these would give:

```
f n = take n $ concat [ [b++">", '<':b] | b <- iterate ('-':) "" ]

```

# Answer
> 5 votes
# Japt `-m`, ~~16~~ ~~15~~ ~~13~~ 12 bytes

*Saved 1 byte thanks to Shaggy*

```
g<i>)iUUz ç-

```

Test it online

## Explanation:

```
-m            // Map the program through [0...Input); U becomes the iterative number
g<i>)iUUz ç-
 <i>          // ">" prepended with "<", creating "><"
g             //   Get the char at index U, with index-wrapping
    i         // Insert:
     U        //   At index U, with index-wrapping
         ç-   //   "-" repeated:
      Uz      //     U/2 times

```

# Answer
> 5 votes
# Python 3, 53 bytes

My first codegolf answer.

```
lambda x:[i%2*"<"+i//2*"-"+~i%2*">"for i in range(x)]

```

-10 bytes thanks to Jo King

# Answer
> 4 votes
# Jelly, 15 bytes

```
ị⁾><;’H”-ẋƲṚ⁸¡)

```

Try it online!

# Answer
> 4 votes
# Japt `-m`, 14 bytes

```
"<>"¬hUUz ç-)q

```

Try it online!

Updated with a completely new method.

Explanation:

```
                  #Implicitly map over the range [0..input) as U
"<>"              #The string "<>"
    ¬             #Split into the array ["<",">"]
     hU     )     #Replace the element at index U with wrapping:
           -      # The character '-'
          ç       # Repeated a number of times equal to
       Uz         #  U integer divided by 2
             q    #Join the array to a string

```

# Answer
> 4 votes
# MathGolf, ~~17~~ 15 bytes

Saved 2 bytes thanks to Jo King and Kevin Cruijssen

```
{ï½'-*'>ï¥╛Å⌡\n

```

Try it online!

## Explanation

The 15-byte approach is different compared to my original solution, I can't take any credit for the implementation.

```
{                 start block or arbitrary length
 ï                index of current loop, or length of last loop
  ½               pop a : push(a//2 if int else a/2)
   '-             push single character "-"
     *            pop a, b : push(a*b)
      '>           push single character ">"
        ï         index of current loop, or length of last loop
         ¥        modulo 2
          ╛       if without else
           Å      start block of length 2
            ⌡     decrement twice
             \    swap top elements
              n   newline char, or map array with newlines

```

# Answer
> 4 votes
# C (gcc), ~~80~~ ~~77~~ ~~76~~ ~~74~~ 71 bytes

```
g(n,i,j){--n&&g(n);for(j=n%2,i=n/=2;putchar(~n?n---i*j?45:62-j*2:0););}

```

Try it online!

-3 bytes with idea from ASCII-only.

-1 with `\0` instead of `\n`

-5 rearranging parts

---

Output includes a trailing `\0`.

```
g(n,i,j){
    --n&&g(n);              //draw smaller arrows first (if n>1)
    for(j=n%2,i=n/=2;       //j:!(input parity); i:arrow len-1=ceil(input)/2-1
        putchar(~n          //if n>=0, arrow is not yet completed
                ? n---i*j   //if not first (j==1) or last (j==0) char of arrow:
                  ? 45      // output '-'
                  : 62-j*2  // otherwise, output the appropriate arrow head
                : 0););     //\0 after arrow complete. putchar returns 0; loop terminates
}

```

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

Returns a space-separated string.

```
n=>(g=p=>n--?k++&1?`<${p} `+g(p+'-'):p+'> '+g(p):'')(k='')

```

Try it online!

# Answer
> 3 votes
# SNOBOL4 (CSNOBOL4), ~~123~~ ~~122~~ 118 bytes

```
	N =INPUT - 1
P	H =X / 2
	Y =DUPL('-',H)
	OUTPUT =EQ(H,X - H) Y '>'	:S(I)
	OUTPUT ='<' Y
I	X =LT(X,N) X + 1	:S(P)
END

```

Try it online!

# Answer
> 3 votes
# , 22 bytes

```
i>
<Àñäkjjé-já-ñÀGjdG

```

Try it online!

# Answer
> 3 votes
# Charcoal, 16 bytes

```
ＮθＦθ«⊘ι↓>‖Ｔ»Ｆθ‖Ｔ

```

Try it online! Link is to verbose version of code. I had three 17-byte solutions before I eventually stumbled over this one. Explanation:

```
Ｎθ

```

Input `n`.

```
Ｆθ«

```

Repeat `n` times, 0-indexed.

```
⊘ι

```

Draw a line of `-`s of length half the index (truncated).

```
↓>

```

Draw the arrowhead and move to the next line.

```
‖Ｔ»

```

Reflect everything, flipping the arrowheads.

```
Ｆθ‖Ｔ

```

The above loop has `n` reflections, but we need an even number of reflections, so perform another `n` reflections.

# Answer
> 3 votes
# Clean, ~~76~~ 73 bytes

```
import StdEnv,StdLib
$n=take n[s\\i<-inits['--'..],s<-[i++['>'],['<':i]]]

```

Try it online!

Uses the neat fact that `['-','-'..]` is the same as `['--'..]` to save a bit.

# Answer
> 3 votes
# 6502 machine code (C64), 49 bytes

```
00 C0 20 9B B7 A2 00 8A 4A A8 90 05 A9 3C 20 D2 FF A9 2D C0 00 F0 06 20 D2 FF
88 D0 FA 8A 4A B0 05 A9 3E 20 D2 FF A9 0D 20 D2 FF E8 E4 65 D0 D7 60

```

Still quite a bit shorter than BASIC ;) This one has a number range only up to `255` because the natural integer size of the machine has only 8 bits.

### Online demo

Usage: `SYS49152,[n]` (e.g. `SYS49152,3` for the example from the challenge)

**Commented disassembly**:

```
         00 C0       .WORD $C000        ; load address
.C:c000  20 9B B7    JSR $B79B          ; get unsigned byte from commandline
.C:c003  A2 00       LDX #$00           ; main loop counter
.C:c005   .loop:
.C:c005  8A          TXA                ; loop counter to accumulator
.C:c006  4A          LSR A              ; divide by 2, shift lowest bit to C
.C:c007  A8          TAY                ; result to Y
.C:c008  90 05       BCC .toright       ; C clear -> counter even, skip '<'
.C:c00a  A9 3C       LDA #$3C           ; load character '<'
.C:c00c  20 D2 FF    JSR $FFD2          ; output character
.C:c00f   .toright:
.C:c00f  A9 2D       LDA #$2D           ; load character '-'
.C:c011  C0 00       CPY #$00           ; counter/2 == 0 ? then no dashes
.C:c013  F0 06       BEQ .skipdashes
.C:c015   .printdashes:
.C:c015  20 D2 FF    JSR $FFD2          ; output character
.C:c018  88          DEY                ; decrement Y
.C:c019  D0 FA       BNE .printdashes   ; not 0 yet -> repeat
.C:c01b   .skipdashes:
.C:c01b  8A          TXA                ; loop counter to accumulator
.C:c01c  4A          LSR A              ; shift lowest bit to C
.C:c01d  B0 05       BCS .toleft        ; C set -> counter odd, skip '>'
.C:c01f  A9 3E       LDA #$3E           ; load character '>'
.C:c021  20 D2 FF    JSR $FFD2          ; output character
.C:c024   .toleft:
.C:c024  A9 0D       LDA #$0D           ; load newline character
.C:c026  20 D2 FF    JSR $FFD2          ; output character
.C:c029  E8          INX                ; next loop iteration
.C:c02a  E4 65       CPX $65            ; compare to command line argument
.C:c02c  D0 D7       BNE .loop          ; not reached yet -> repeat main loop
.C:c02e  60          RTS                ; exit

```

# Answer
> 3 votes
# JavaScript, 49 bytes

```
f=n=>--n?f(n,l='')+(n%2?`
<`+l:`
${l+='-'}>`):'>'

```

Try it online!

# Answer
> 2 votes
# Powershell, 51 bytes

```
param($n)0..$n|%{'-'*$_+'>';'<'+'-'*$_}|?{$n---gt0}

```

# Answer
> 2 votes
# 05AB1E, ~~23~~ 20 bytes

```
FNÉD„><è'-N;∍«s_iR},

```

Try it online!

First time using 05AB1E or any other golfing language for that matter. Any ideas welcome.

-3 from Kevin Cruijssen

# Answer
> 2 votes
# Perl 6, 39 bytes

```
{map {'<'x$_%2~'-'x$_/2~'>'x$_%%2},^$_}

```

Try it online!

Anonymous code block that returns a list of lines.

# Answer
> 2 votes
# Red, 109 108 bytes

-1 byte thanks to NK1406

```
func[n][repeat i n[print reduce[pick[pad/with pad/left/with]k: i% 2 + 1
pick copy"<>"k i / 2 + k - 1 #"-"]]]

```

Try it online!

# Answer
> 2 votes
# K (ngn/k), ~~31~~ 29 bytes

```
{"<->"x#2,x{(1=*x)_1,2-|x}\0}

```

Try it online!

first we generate lists with 0 instead of `"<"`, 1 instead of `"-"`, and 2 instead of `">"`:

`{` `}` function with argument `x`

`x{`...`}\0` apply the inner function `x` times, starting with an initial value of `0` and preserving intermediate results

`|x` reverse

`2-` replace 0 with 2 and vice versa, keep the 1s as they are

`1,` prepend a 1

`(1=*x)_` is the first of `x` equal to 1? if yes, drop one element, otherwise drop 0 elements (do nothing)

`2,` prepend a 2 for the initial `">"` arrow

`x#` we have a little too many lists, so take only the first `x` of them

`"<->"` use the lists' elements (0/1/2) as indices in this string

# Answer
> 2 votes
# C (gcc), ~~127~~ 95 + 26 = 121 bytes

```
i,j;f(x){for(i=0;i<x;putchar(10),i+=2){for(j=0;E;printf(">\n%c",x-i-1?60:9);for(j=0;x-i-1&&E;}}

```

Try it online!

Compile with `-DE=j<i/2;++j)putchar(45)`

-6 bytes from Logern

Yay mismatched parentheses!

Ungolfed:

```
void f(int x) {
	for (int i = 0; i < x; i += 2) {
		for (int j = 0; j < i/2; ++j) {
			printf("-");
		}
		printf(">\n");
		if (x - i - 1) { // Test for last loop: only print <-- if x is even
			printf("<");
			for (int j = 0; j < i/2; ++j) {
				printf("-");
			}
		}
		else {
			printf("\t"); // This is the 9 in the x-i-1?60:9
		}
		printf("\n");
	}
}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~18~~ 15 bytes

```
F'-N;∍'>«º2äNè,

```

Suggested as a golf for *@nedla2004*'s 05AB1E answer, but he said I should post it myself since it's using a slightly different approach.

Try it online.

**Explanation:**

```
F                # Loop `N` in the range [0, (implicit) input):
   N;            #  Halve the current index `N`
 '-  ∍          '#  Have that many "-" (the halved index decimal .5 is ignored)
      '>«       '#  And append a ">"
         º       #  Now mirror it: i.e. "--->" becomes "---><---"
          2ä     #  Split it into two equal-sized parts: i.e. ["--->","<---"]
            Nè   #  Index the `N` into this array of two strings (with automatic wraparound)
              ,  #  And output it with a trailing newline

```

# Answer
> 2 votes
# ES6, ~~96~~ ~~82~~ ~~79~~ 70 bytes

Try it online! (Thanks to @Oliver)

```
n=>[...Array(n)].map((_,i)=>(i%2?"<":"")+"-".repeat(i/2)+(i%2?"":">"))

```

# Answer
> 2 votes
# C# (.NET Core), 90 bytes

```
a=>{for(int i=0;i<a;i++){var s=new String('-',i/2);Console.WriteLine(i%2<1?s+">":"<"+s);}}

```

Try it online!

Uses an Action delegate to pull in the input and not require a return.

Ungolfed:

```
a => {
    for(int i = 0; i < a; i++)          // from [0, a)
    {
        var s = new String('-', i / 2);     // create string of dashes of length (a / 2)
        Console.WriteLine(i % 2 < 1 ?       // write arrow
                                s + ">" :       // if i is even: dashes plus ">"
                                "<" + s);       // if i is odd: "<" plus dashes
    }
}

```

# Answer
> 2 votes
# 05AB1E, 18 bytes

```
F…> <N'-×.ø#`})s£»

```

Try it online!

---

```
F            }     # Loop from 0 to input...
 …> <              # Push '> <'...
     N'-×          # Push "-" multiplied by N.
         .ø        # Surround with this.
           #`      # Split on spaces, flatten both directions to stack.
              )    # Group all entries together after loop.
               s£  # Take first N.
                 » # Print with newlines.

```

---

Non-iterative, same byte-count:

# 05AB1E, 18 bytes

```
'-×©'>«.s®'<ìη.ιs£

```

Try it online!

**Other, other method:**

# 05AB1E, 18 bytes

```
'-×'>«.sð«.º€#˜s£

```

Try it online!

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 69 bytes

```
i=>{for(var s="";i>0;s+=--i%2<1?"-":"")WriteLine(i%2<1?"<"+s:s+">");}

```

Try it online!

Uses a technique from Meerkat's answer, but has a lot of improvements.

Less golfed code:

```
// anonymous function with
// input i and no return value
i=>{
  for(
    // s is a string of hyphens
    var s="";
    // loop from i down to 0
    i>0;
    // decrement i and conditionally
    // tack on an additional hyphen
    // depending on whether i
    // is even or odd
    s+=--i%2<1?"-":""
  )
    // print the hyphens with an arrow
    // at the start or end, depending
    // on whether i is even or even
    WriteLine(i%2<1?"<"+s:s+">");
}

```

# Answer
> 2 votes
# Perl 5, 36 bytes

```
say$|--?v17^($@.='-'):"$@>"for 1..<>

```

Try it online!

Gets `<` from the bitwise-xor of `-` and `v17` (ASCII 17).

# Answer
> 1 votes
# Tcl, 99 bytes

```
proc A i {time {puts [expr [incr j]%2?"":"<"][string repe - [expr ($j-1)/2]][expr $j%2?">":""]} $i}

```

Try it online!

# Answer
> 1 votes
# Java 8, ~~123~~ ~~120~~ 119 bytes

```
n->{String l="",r="";for(int c=0;c<n;c++)System.out.println(c%2<1?r=c<1?">":c<2?"<":"-"+r:(l+=c<1?">":c<2?"<":"-"));}

```

# Answer
> 1 votes
# Perl 5, 44 bytes

```
map{$_/=2;say'<'x/\./,'-'x$_,'>'x!$&}0..<>-1

```

Try it online!

# Answer
> 1 votes
# Ruby, 47 bytes

```
->n{n.times.map{|x|"<#{?-*n}>"[x%2*~x/=2,x+1]}}

```

Try it online!

# Answer
> 1 votes
# PHP, 113 bytes

```
<?php $x=fgets(STDIN);for($i=0;$i<$x;){echo $i%2<1?str_repeat("-",$i++/2).">\n":"<".str_repeat("-",$i++/2)."\n";}

```

Try it online!

A pretty straightforward solution.

# Answer
> 1 votes
# C#, 99 bytes

```
n=>new string[n].Select((x,i)=>(i%2>0?"<":"")+new String('-',(int)Math.Floor(i/2d))+(i%2<1?">":""))

```

Try it online!

# Answer
> 1 votes
# PHP, ~~76~~ ~~73~~ ~~72~~ 67 bytes

```
for(;$x<$i;)echo$x&1?'<':'',str_repeat('-',$x/2),$x++&1?'':'>',"
";

```

Try it online!

Output:

```
>
<
->
<-
-->
<--
--->
<---
---->
<----
----->
<-----
------>
<------

```

# Answer
> 1 votes
# Lua, ~~69~~ 68 bytes

```
for i=0,...-1 do a=("-"):rep(i//2)print(i%2<1 and a..">"or"<"..a)end

```

---

### Explanation

```
for i=0,...-1 do  -- for 'i' going from 0 to the number on the first argument
  dashes = ("-"):rep(i//2)  -- dashes is a dash repeated by the iteration we are divided by 2 and rounded down
  print(i%2<1 and dashes..">" or "<"..dashes)  -- if 'i' is even, then print the dashes and then the right-facing arrow
                                               -- else, print the left-facing arrow and then the dashes
end

```

Try it online!

# Answer
> 1 votes
# Rust, 152 142 bytes

```
|n|{for i in 0..n{println!("");if i%2==1{print!("<");for _ in 1..i{print!("-");}}else{for _ in 1..i{print!("-");}print!(">");}}println!("");};

```

Down from 152 bytes to 142 bytes thanks to Pavel.

# Answer
> 1 votes
# PHP, 102 bytes

command line options added `-n -d`

```
<?for(;$i++<$argv[1];){$b=str_repeat("-",abs($u=ceil($i/2)*pow(-1,$i+1))-1);echo($u>0)?"<$b
":"$b>
";}

```

Try it online!

**Explanation**

It is not a much different solution, but is using one of the ways to get the n-th term of the series A001057 wich is another way to look at the challenge.

According to A001057 the one way to obtain the n-th term is with the formula `a($n)=ceil($n/2)*pow(-1,$n+1)`.

And you can look at the challenge like this.

```
>     +1
<     -1
->    +2
<-    -2
-->   +3
<--   -3
--->  +4
<---  -4
----> +5
# And so on

```

# Answer
> 1 votes
# CJam, 31 bytes

```
qi{A2%{'<'-A2/*}{'-A2/*'>}?N}fA

```

Explanation:

```
qi{A2%{'<'-A2/*}{'-A2/*'>}?N}fA e# Whole code
qi                              e# Get input as an integer
  {                         }fA e# A for loop, from 0 - (input - 1), stored in var A
   A2%                          e# Is A a multiple of 2?
      {        }{        }?     e# Ternary operator: Left is true, right is false
      {
       '<                       e# Push "<" onto the stack
         '-                     e# Push "-" onto the stack
           A2/                  e# Get A/2
              *                 e# Repeat "-" A/2 times
               }{
                 '-             e# Push "-" onto the stack
                   A2/          e# Get A/2
                      *         e# Repeat "-" A/2 times
                       '>       e# Push ">" onto the stack
                         }
                           N    e# Push a new line after each arrow
                                e# Implicit output

```

Try it online!

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


title: Faro shuffle an array

text:
# Question
Title: Faro shuffle an array
A Faro shuffle is a technique frequently used by magicians to "shuffle" a deck. To perform a Faro shuffle you first cut the deck into 2 equal halves then you interleave the two halves. For example

```
[1 2 3 4 5 6 7 8]

```

Faro shuffled is

```
[1 5 2 6 3 7 4 8]

```

This can be repeated any number of times. Interestingly enough, if you repeat this enough times, you will always end up back at the original array. For example:

```
[1 2 3 4 5 6 7 8]
[1 5 2 6 3 7 4 8]
[1 3 5 7 2 4 6 8]
[1 2 3 4 5 6 7 8]

```

Notice that 1 stays on the bottom and 8 stays on the top. That makes this an outer-shuffle. This is an important distinction.

# The Challenge

Given an array of integers *A*, and a number *N*, output the array after *N* Faro shuffles. *A* may contain repeated or negative elements, but it will always have an even number of elements. You can assume the array will not be empty. You can also assume that *N* will be a non-negative integer, although it may be 0. You can take these inputs in any reasonable manner. The shortest answer in bytes wins!

# Test IO:

```
#N, A,                                              Output
1,  [1, 2, 3, 4, 5, 6, 7, 8]                        [1, 5, 2, 6, 3, 7, 4, 8]
2,  [1, 2, 3, 4, 5, 6, 7, 8]                        [1, 3, 5, 7, 2, 4, 6, 8]
7,  [-23, -37, 52, 0, -6, -7, -8, 89]               [-23, -6, -37, -7, 52, -8, 0, 89]
0,  [4, 8, 15, 16, 23, 42]                          [4, 8, 15, 16, 23, 42]
11, [10, 11, 8, 15, 13, 13, 19, 3, 7, 3, 15, 19]    [10, 19, 11, 3, 8, 7, 15, 3, 13, 15, 13, 19]

```

And, a massive test case:

```
23, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

```

Should output:

```
[1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4, 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36, 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68, 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100]

```

# Answer
> 11 votes
# 05AB1E, 5 bytes

Code:

```
F2äø˜

```

Explanation, input: `N`, `array`:

```
F      # Do the following N times
 2ä    # Split the array into 2 pieces
   ø   # Zip
    ˜  # Deep flatten

```

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

# Answer
> 19 votes
## vim, ~~62~~ ~~59~~ 54

```
qrma50%mb:norm@q<cr>ggqOjdd'apjma'b@q<esc>0"qDJ<C-a>D@"i@r<esc>xxdd@"

```

Wow. This is possibly the hackiest thing I've written for PPCG, and that's saying something.

Input is taken as N on the first line followed by the elements of the array, each on its own line.

```
qr         first, we're going to record the contents of the @r macro. this is
             the macro which does the faro-shuffle operation.
  ma       set the mark 'a at the beginning of the file
  50%      move to the 50% point of the file (i.e. halfway down)
  mb       set another mark here
  :norm@q  evaluate the recursive macro @q. we'll get to what that does later,
             but the interesting part here is that it's :norm@q instead of @q.
             this is because a recursive macro terminates at the end of the
             file, which means when @q terminates, @r would also abort, which
             would make calling it with a count impossible. running @q under
             :norm prevents this.
  gg       move back to the top of the file for the next iteration
q          end recording
O          now we're inserting contents of the @q macro, the recursive part
             we can't record it directly because it's destructive
  j        move to line directly below mark 'b (which was just set before @q)
  dd       delete this line and bring it...
  'ap      up after mark 'a (which starts on line 1, bringing the N/2th line
             directly below line 1, aka line 2)
  jma      replace mark 'a one line below this so that the next time we call
             'ap, the line from the second half is interleaved with the lines
             from the first half
  'b       jump back to mark 'b (remember, 'b is the last line of the first
             half of the file, originally reached via 50%)
  @q       call ourselves, causing the macro to run until hitting EOF
0"qD       delete this into register "q
J          delete the empty line that remains
<C-a>      here's another interesting bit: we want to run @r N times. but 0@r
             means "go to column 0, and then run @r once." so we have to
             increment the input number...
D@"        and then *that* many times...
  i@r        insert @r...
xx         ... and finally, delete two characters, which is the extra @r from
             the increment
dd         delete the sequence of @rs into the "" register...
@"         and run it!

```

I actually possibly found several vim bugs while writing this answer:

* recording macros is not possible within other macros (when setting their text manually, not with `q`) or within `:*map`s.
* `:let @a='<C-v><cr>'<cr>i<C-r>a` outputs two newlines, not one, for whatever arcane reason.

I might investigate those further later.

Thanks to Dr Green Eggs and Ham DJ for 3 bytes!

# Answer
> 6 votes
# Python, ~~68~~ 57 bytes

```
f=lambda n,x:n and f(n-1,sum(zip(x,x[len(x)/2:]),()))or x

```

*Thanks to @Sp3000 for golfing off 11 bytes!*

Test it on Ideone.

# Answer
> 6 votes
## Python 2, 59 bytes

```
def f(n,L):exec"l=len(L)/2;L=(L+L[1:]*~-l)[::l];"*n;print L

```

A different approach, slightly longer than the other Python answers. Only works for positive even numbers of elements.

e.g. for `1, [1,2,3,4,5,6,7,8]`, take the array and append `len(L)/2-1` copies of itself minus the first element, e.g.

```
[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]

```

Then take every `len(L)/2`th element.

```
[1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8,2,3,4,5,6,7,8]
 ^       ^       ^       ^       ^       ^       ^       ^

```

# Answer
> 6 votes
# Haskell, 62 bytes

```
0!a=a
n!a|s<-length a=(n-1)![a!!mod(div(s*i+i)2)s|i<-[0..s-1]]

```

Let *s* = 2·*t* be the size of the list. The *i*-th element of the new list is obtained by taking the -th element of the old list, zero-indexed, modulo *s*.

Proof: if *i* = 2·*k* is even, then

and if *i* = 2·*k* \+ 1 is odd, then

Thus the values used for indexing are 0, *t*, 1, *t* \+ 1, 2, *t* \+ 2, …

# Answer
> 5 votes
# Pyth - ~~8~~ 7 bytes

*saved 1 byte thanks to @issacg*

```
usCc2GE

```

Try it online here.

# Answer
> 5 votes
# J - 12 bytes

Adverb (!) taking number of shuffles on the left and the array to shuffle on the right.

```
/:#/:@$0,#^:

```

The J parser has rules for writing tacit adverbs, but they have very low precedence: if you want to use a train of verbs as a left argument, you can omit an otherwise necessary set of parentheses. So the above is actually short for `(/:#/:@$0,#)^:`, which takes the number of shuffles on the left as an adverb, and then becomes a monadic function taking the array to shuffle on the right.

That said, we shuffle as follows. `#` is the length of the array, so `0,#` is a two element list: 0 followed by something nonzero. Then `#/:@$` replicates that into a list as long as the input array, and takes its **sort vector**.

The sort vector of a list is the information for how to sort the list: the (0-based) invdex of the smallest element, followed by the index of the next-smallest, and so on. For example, the sort vector of `0 1 0 1 ...` will thus be `0 2 4 ... 1 3 5 ...`.

If J were now to sort this sort vector, it would Faro-shuffle it; but that would be trivial, since we'd get `0 1 2 3 ...` back. So we use dyadic `/:` to sort the input array **as if it were** `0 2 4 ... 1 3 5 ...`, which Faro-shuffles it.

Example usage below. Try it yourself at tryj.tk!

```
   1 (/:#/:@$0,#^:) 1 2 3 4 5 6 7 8
1 5 2 6 3 7 4 8

   f =: /:#/:@$0,#^:

   2  f  1 2 3 4 5 6 7 8
1 3 5 7 2 4 6 8

   7  f  _23 _37 52 0 _6 _7 _8 89   NB. "negative 1" is spelled _1
_23 _6 _37 _7 52 _8 0 89

   1  f  0 0 0 0 1 1 1              NB. odd-length lists
0 1 0 1 0 1 0

```

# Answer
> 3 votes
# Jelly, ~~9~~ 7 bytes

2 bytes thanks to Dennis!

```
œs2ZFð¡

```

Try it online!

### Explanation

```
œs2ZFð¡  Main dyadic chain. Arguments: x,y
      ¡  Repeat the following y time:
œs2          Split into two.
   Z         Transpose.
    F        Flatten.

```

## Previous 9-byte version:

```
œs2ZF
Ç⁴¡

```

Try it online!

# Answer
> 2 votes
# MATL, 11 bytes

```
w:"tn2/e!1e

```

*Thanks to @Dennis for a correction*

**Try it online!**

### Explanation

```
w         % Take the two inputs N and A. Swap them
:         % Generate [1 2 ... N]
"         % Repeat N times
  tn2/    %   Duplicate A. Number of elements divided by 2
  e       %   Reshape to that number of rows
  !       %   Transpose
  1e      %   Reshape to one row
          % End (implicit)
          % Display (implicit)

```

# Answer
> 2 votes
# J, ~~22~~ ~~19~~ 17 bytes

3 bytes thanks to @Gareth.

2 bytes thanks to @algorithmshark.

```
-:@#({.,@,.}.)]^:

```

### Usage

```
>> f =: -:@#({.,@,.}.)]^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8

```

Where `>>` is STDIN and `<<` is STDOUT.

## Previous 22-byte version:

```
({~[:,/@|:@i.2,-:@#)^:

```

### Usage

```
>> f =: ({~[:,/@|:@i.2,-:@#)^:
>> 2 f 1 2 3 4 5 6 7 8
<< 1 3 5 7 2 4 6 8

```

Where `>>` is STDIN and `<<` is STDOUT.

# Answer
> 2 votes
## JavaScript (ES6), ~~61~~ 51 bytes

```
(n,a)=>[...a].map((e,i)=>a[(i<<n)%~-a.length||i]=e)

```

Modifies the input array in place and returns a copy of the original array. If this is unacceptable, `&&a` can be suffixed to return the modified array. Only works for small values of `n` due to the limitations of JavaScript's integer arithmetic. ~~61~~ 60 byte recursive version that works with larger `n`, based on @Lynn's formula:

```
f=(n,a,l=a.length)=>n?f(n-1,a.map((_,i)=>a[(i*-~l>>1)%l])):a

```

# Answer
> 1 votes
# Julia, ~~45~~ 42 bytes

```
a\n=n>0?reshape(a,endof(a)÷2,2)'[:]\~-n:a

```

Try it online!

### How it works

We (re)define the binary operator `\` for this task. Let **a** be an array and **n** a non-negative integer.

If **n** is positive, we shuffle the array. This is achieved by reshaping it into a matrix of **length(a) ÷ 2** rows and two columns. `'` transposes the resulting matrix, creating of two rows, then flattening the result with `[:]`. Since Julia stores matrices in column-major order, this interleaves the two rows.

Afterwards, we call `\` recursively with the shuffled **a** and **n - 1** (`~-n`) as arguments, thus performing additional shuffles. Once **n** reaches **0**, we return the current value of **a**.

# Answer
> 1 votes
# APL, ~~23~~ 21 chars

```
({⊃,/⍵(↑,¨↓)⍨2÷⍨⍴⍵}⍣N)A

```

Without the assumption (Thanks to Dennis) and 1 char shorter:

```
({{∊,⌿2(2÷⍨≢⍵)⍴⍵}⍣⎕)⎕

```

Try it on online.

# Answer
> 1 votes
# Mathematica 44 bytes

With 4 bytes saved thanks to @miles.

```
Riffle@@TakeDrop[#,Length@#/2]&~Nest~##&

```

---

`Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[list, nShuffles]` splits the list into two equal sublists and shuffles (`Riffle`s) them.

---

```
 Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@8, 1]

```

{1, 5, 2, 6, 3, 7, 4, 8}

---

```
Riffle @@ TakeDrop[#, Length@#/2] &~Nest~## &[Range@100, 23]

```

{1, 30, 59, 88, 18, 47, 76, 6, 35, 64, 93, 23, 52, 81, 11, 40, 69, 98, 28, 57, 86, 16, 45, 74, 4, 33, 62, 91, 21, 50, 79, 9, 38, 67, 96, 26, 55, 84, 14, 43, 72, 2, 31, 60, 89, 19, 48, 77, 7, 36, 65, 94, 24, 53, 82, 12, 41, 70, 99, 29, 58, 87, 17, 46, 75, 5, 34, 63, 92, 22, 51, 80, 10, 39, 68, 97, 27, 56, 85, 15, 44, 73, 3, 32, 61, 90, 20, 49, 78, 8, 37, 66, 95, 25, 54, 83, 13, 42, 71, 100}

# Answer
> 1 votes
# java, 109 bytes

`int[]f(int[]a,int n){for(int x,q=a.length,d[];0<n--;a=d){d=new int[q];for(x=0;x<q;x++)d[(2*x+2*x/q)%q]=a[x];}return a;}`

Explanation: There is a pattern to how the elements move when they are faro shuffled:

let x be the original index

let y be the new index

let L be the length of the array

* y is double x
* if x is greater than or equal to half of L then increment y
* keep y within the array's bounds

or as code: `y=(2*x+x/(L/2))%L`

This assumes that indicies start at 0. Here's the code further explained:

```
int[] faroShuffle( int[] array, int numberOfShuffles ) {
    //repeat the faro shuffle n times
    for( int index, length=array.length, destination[]; 0<numberOfShuffles--; array=destination ) {
        //new array to copy over the elements
        destination=new int[length];
        //copy the elements into the new array
        for( index=0; index<length; index++ )
            destination[(2*index+2*index/length)%length]=array[index];
        //at the end of each loop, copy the reference to the new array and use it going forward
    }
    return array;
}

```

see ideone for test cases

# Answer
> 0 votes
## Pyke, 7 bytes

```
VDlec,s

```

Try it here!

```
V       - Repeat N times:
 D      -  a,b = a (2nd arg first time round)
  le    -  b = len(b)//2
    c   -  a = chunk(a,b)
     ,  -  a = zip(*a)
      s -  a = sum(a, [])

```

# Answer
> 0 votes
## Actually, 15 bytes

```
`;l½≈@│t)HZ♂i`n

```

Try it online!

Explanation:

```
`;l½≈@│t)HZ♂i`n
`            `n  do the following n times:
 ;l½≈              push half the length of the array
     @             swap
      │            duplicate entire stack
       t)H         last L//2 elements, first L//2 elements
          Z♂i      zip, flatten each element

```

# Answer
> 0 votes
# Prolog, 116 bytes

```
a([],[[],[]]).
a([H,I|T],[[H|U],[I|V]]):-a(T,[U,V]).
f(X,0,X).
f(X,N,Y):-N>0,M is N-1,f(X,M,Z),a(Z,[A,B]),append(A,B,Y).

```

## Usage

```
?- f([1,2,3,4,5,6,7,8],2,X).
X = [1, 5, 2, 6, 3, 7, 4, 8] ;
false.

```

# Answer
> 0 votes
# Perl 5 `-lan`, 52 bytes

```
$a=<>;@F=map@F[$_,@F/2+$_],0..$#F/2while$a--;say"@F"

```

Try it online!

# Answer
> 0 votes
# PHP, 98 bytes

```
function($a,$n){while($n--)for($z=count($a)/2;$z;)array_splice($a,$z--,0,array_pop($a));return$a;}

```

Try it online.

---
Tags: code-golf, permutations, card-games
---


title: Golf the Subset-Sum Problem

text:
# Question
Title: Golf the Subset-Sum Problem
# Task

Given a list of space-delimited integers as input, output all unique non-empty subsets of these numbers that each subset sums to 0.

---

## Test Case

Input: `8 −7 5 −3 −2`
Output: `-3 -2 5`

---

## Winning Criterion

This is , so the shortest code in bytes wins!

# Answer
> 4 votes
### GolfScript, 41 characters

```
~][[]]\{`{1$+$}+%}%;(;.&{{+}*!},{" "*}%n*

```

If you do not care about the specific output format you can shorten the code to 33 characters.

```
~][[]]\{`{1$+$}+%}%;(;.&{{+}*!},`

```

Example (see online):

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

```

# Answer
> 6 votes
# Brachylog (2), 9 characters

```
{⊇.+0∧}ᵘb

```

Try it online!

```
{⊇.+0∧}ᵘb
 ⊇           subset
   +0        that sums to 0
  .  ∧       output the subset
{     }ᵘ     take all unique solutions
        b    except the first (which is the empty solution)

```

# Answer
> 4 votes
## Python, 119 chars

```
def S(C,L):
 if L:S(C,L[1:]);S(C+[L[0]],L[1:])
 elif sum(map(int,C))==0and C:print' '.join(C)
S([],raw_input().split())

```

Enumerates all 2^n subsets recursively and checks each one.

# Answer
> 3 votes
## Python, 120

I'm a character worse than Keith's solution. But... this is too close to not post. One of my favorite features of code-golf is how dissimilar similar-length solutions can be.

```
l=raw_input().split()
print[c for c in[[int(j)for t,j in enumerate(l)if 2**t&i]for i in range(1,2**len(l))]if sum(c)==0]

```

# Answer
> 2 votes
# Mathematica 62 57 38

**Code**

Input entered as integers in an array, `x`.

```
x

```

```
Grid@Select[Subsets@x[[1, 1]], Tr@# == 0 &]

```

---

**Output**

---

**Explanation**

`x[[1, 1]]` converts the input to a list of integers.

`Subsets` generates all subsets from the integers.

`Select....Tr@# == 0` gives all those subsets that have a total equal to 0.

`Grid` formats the selected subsets as space-separated integers.

# Answer
> 2 votes
## Python (~~128 137~~ 136)

Damn you, `itertools.permutations`, for having such a long name!

Brute force solution. I'm surprised it's not the shortest: but I guess `itertools` ruins the solution.

Ungolfed:

```
import itertools
initial_set=map(int, input().split())
ans=[]
for length in range(1, len(x)+1):
    for subset in itertools.permutations(initial_set, length):
        if sum(subset)==0:
            ans+=str(sorted(subset))
print set(ans)

```

Golfed (ugly output):

```
from itertools import*
x=map(int,input().split())
print set(`sorted(j)`for a in range(1,len(x)+1)for j in permutations(x,a)if sum(j)==0)

```

Golfed (pretty output) (183):

```
from itertools import*
x=map(int,input().split())
print `set(`sorted(j)`[1:-1]for a in range(1,len(x)+1)for j in permutations(x,a)if sum(j)==0)`[5:-2].replace("'","\n").replace(",","")

```

`import itertools as i`: importing the itertools module and calling it `i`

`x=map(int,input().split())`: seperates the input by spaces, then turns the resulting lists' items into integers (`2 3 -5` -\> `[2, 3, -5]`)

set(`sorted(j)`for a in range(1,len(x)+1)for j in i.permutations(x,a)if sum(j)==0):
Returns a list of all subsets in `x`, sorted, where the sum is 0, and then gets only the unique items
(`set(...)`)

The graves (\`) around `sorted(j)` is Python shorthand for `repr(sorted(j))`. The reason why this is here is because sets in Python cannot handle lists, so the next best thing is to use strings with a list as the text.

# Answer
> 2 votes
# **SWI-Prolog** 84

This version prints the list, instead of trying to find an appropriate binding for a term in a predicate.

```
s([],O):-O=[_|_],sum_list(O,0),print(O).
s([H|T],P):-s(T,[H|P]).
s([_|T],O):-s(T,O).

```

### Input method

```
s([8,-7,5,-3,-2,4],[]).

```

---

For the record, this is the version that finds a binding to satisfy the predicate:

```
s(L,O):-s(L,0,O),O=[_|_].
s([],0,[]).
s([H|T],S,[H|P]):-R is H+S,s(T,R,P).
s([_|T],S,O):-s(T,S,O).

```

### Input method

```
s([8,-7,5,-3,-2,4],O).

```

Previous revision contains an incomplete solution that didn't manage to remove empty set.

# Answer
> 2 votes
## C# – 384 characters

OK, functional-style programming in C# is not that *short*, but I *love* it! (Using just a brute-force enumeration, nothing better.)

```
using System;using System.Linq;class C{static void Main(){var d=Console.ReadLine().Split(' ').Select(s=>Int32.Parse(s)).ToArray();foreach(var s in Enumerable.Range(1,(1<<d.Length)-1).Select(p=>Enumerable.Range(0,d.Length).Where(i=>(p&1<<i)!=0)).Where(p=>d.Where((x,i)=>p.Contains(i)).Sum()==0).Select(p=>String.Join(" ",p.Select(i=>d[i].ToString()).ToArray())))Console.WriteLine(s);}}

```

Formatted and commented for more readability:

```
using System;
using System.Linq;

class C
{
    static void Main()
    {
        // read the data from stdin, split by spaces, and convert to integers, nothing fancy
        var d = Console.ReadLine().Split(' ').Select(s => Int32.Parse(s)).ToArray();
        // loop through all solutions generated by the following LINQ expression
        foreach (var s in
            // first, generate all possible subsets; well, first just their numbers
            Enumerable.Range(1, (1 << d.Length) - 1)
            // convert the numbers to the real subsets of the indices in the original data (using the number as a bit mask)
            .Select(p => Enumerable.Range(0, d.Length).Where(i => (p & 1 << i) != 0))
            // and now filter those subsets only to those which sum to zero
            .Where(p => d.Where((x, i) => p.Contains(i)).Sum() == 0)
            // we have the list of solutions here! just convert them to space-delimited strings
            .Select(p => String.Join(" ", p.Select(i => d[i].ToString()).ToArray()))
        )
            // and print them!
            Console.WriteLine(s);
    }
}

```

# Answer
> 2 votes
# Jelly, 6 bytes

```
ŒPḊSÐḟ

```

Try it online!

Just for completeness. Similar to Brachylog, Jelly also postdates the challenge, but by now, newer languages compete normally.

```
ŒP       Power set.
  Ḋ      Dequeue, remove the first element (empty set).
    Ðḟ   Filter out the subsets with truthy (nonzero)...
   S       sum.

```

# Answer
> 2 votes
# 05AB1E, 5 bytes

```
æ¦ʒO>

```

Try it online!

---

If input must be space delimited, prepending `#` to this answer is the only change required.

# Answer
> 1 votes
## J, 57 53 51 49 characters

```
>a:-.~(#:@i.@(2&^)@#<@":@(#~0=+/)@#"1 _])".1!:1[1

```

Usage:

```
   >a:-.~(#:@i.@(2&^)@#<@":@(#~0=+/)@#"1 _])".1!:1[1
8 _7 5 _3 _2 4
5 _3 _2
_7 5 _2 4
8 _7 _3 _2 4

```

# Answer
> 1 votes
# Stax, 8 bytesCP437

```
â±3╒yΣ╓à

```

Run and debug online!

## Explanation

Uses the unpacked version (9 bytes) to explain.

```
LS{|+!fmJ
L            Convert to list
 S           Powerset
  {   f      Filter with block
   |+!       Sum is zero
       mJ    Print each subset, joined by spaces

```

# Answer
> 1 votes
# , 34 bytes

```
(a:-.~](<@#~0=+/)@#~[:#:@i.2^#)@".

```

Try it online!

## how

`".` converts the input to a list. then:

```
a: -.~ ] (<@#~ (0 = +/))@#~ [: #:@i. 2 ^ #
                                  i.       NB. ints from 0 to...
                                     2 ^ # NB. 2 to the input len
                            [: #:@         NB. converted to binary masks
       ] (             ) #~                NB. filter the input using
                                           NB. using those masks, giving
                                           NB. us all subsets
         (             )@                  NB. and to each one...
         (  #~ (0 = +/))                   NB. return it if its sum is
                                           NB. 0, otherwise make it
                                           NB. the empty list.
         (<@           )                   NB. and box the result.
                                           NB. now we have our answers
                                           NB. and a bunch of empty
                                           NB. boxes, or aces (a:).
a: -.~                                     NB. remove the aces.

```

# Answer
> 1 votes
# Perl 6, 51 bytes

```
*.words.combinations.skip.grep(!*.sum)>>.Bag.unique

```

Try it online!

Returns a list of unique Bags that sum to 0. A Bag is a weighted Set.

### Explanation:

```
*.words                 # Split by whitespace
 .combinations          # Get the powerset
 .skip                  # Skip the empty list
 .grep(!*.sum)          # Select the ones that sum to 0
 >>.Bag                 # Map each to a weighted Set
 .unique                # And get the unique sets

```

# Answer
> 0 votes
# Ruby, 110 bytes

```
a=gets.split.map &:to_i;b=[];(1...a.length).each{|c|a.permutation(c){|d|d.sum==0?b<<d:0}};p b.map(&:sort).uniq

```

Will add TIO link later.

Takes input from stdin as a list of numbers, e.g. `8 −7 5 −3 −2`

How it works: It converts the input into an array of numbers. Gets all the permutations of the lengths from 1 to the array's length. It adds them to the output array if they sum to 0. It outputs the array without duplicates.

Output for the sample input: `[[-3, -2, 5]]`

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


title: Shortest code for Seven-Eleven

text:
# Question
Title: Shortest code for Seven-Eleven
The Seven-Eleven problem is find 4 positive numbers (with two decimal digits, A.BC) such that their sum is equal to their product and is equal to 7.11.

```
a + b + c + d = a * b * c * d = 7.11
0 < a <= b <= c <= d

```

Write the shortest program to compute all non-decreasing quadruples. Precomputing the values is not allowed.

# Answer
> 5 votes
## Ruby, 105 characters

Unfortunately I didn't get it below the 100 mark. It just brute forces all possible tuples and checks afterwards. Nevertheless it still finishes in finite time.

```
(1..m=711).map{|a|(a..m).map{|b|(b..m).map{|c|d=m-a-b-c;p [a/u=1e2,b/u,c/u,d/u]if d>=c&&a*b*c*d==m*1e6}}}

```

The formatted version looks like this:

```
(1..m=711).map{ |a|
  (a..m).map{ |b|
    (b..m).map{ |c|
      d=m-a-b-c
      p [a/u=1e2,b/u,c/u,d/u] if d>=c && a*b*c*d==m*1e6
    }
  }
}

```

# Answer
> 3 votes
## Haskell - 121

*(extra newline added for readability)*

```
h=711
main=mapM(print.map((/100).realToFrac))
     [[a,b,c,d]|a<-[1..h],b<-[a..h],c<-[b..h],let d=h-a-b-c,c<=d,a*b*c*d==h*10^6]

```

This meets the requirements by only working with numbers with two decimal digits. It computes the solution (there's only one of them) using integer arithmetic, scaled up by 100. Floating-point arithmetic is too untrustworthy for this.

# Answer
> 1 votes
## Python (146 152 characters)

Here's a "real" answer, if my Wolfram Alpha one doesn't please:

```
n=711
r=lambda v:range(v,n)
print [[a*0.01,b*0.01,c*0.01,d*0.01]for a in r(1)for b in r(a)for c in r(b)for d in r(c)if a+b+c+d==n and a*b*c*d==n]

```

It's very, very inefficient, but it works.

# Answer
> 1 votes
# C (229 characters)

Sacrificial offering:

```
#include<stdio.h>
int main(void){int a,b,c,d;for(a=1;a<=711/4;++a)for(b=a;b<=711/4;++b)for(c=b;c<=711/4;++c){d=711-(a+b+c);if(d<c)break;if(a*b*c*d==711000000)printf("a=%.2f,b=%.2f,c=%.2f,d=%.2f\n",a/100.,b/100.,c/100.,d/100.);}}

```

Re-formatted for readability:

```
#include <stdio.h>

int main()
{
    int a, b, c, d;

    for (a = 1; a <= 711 / 4; ++a)
        for (b = a; b <= 711 / 4; ++b)
            for (c = b; c <= 711 / 4; ++c)
            {
                d = 711 - (a + b + c);
                if (d < c) break;
                if (a * b * c * d == 711000000)
                    printf("a = %.2f, b = %.2f, c = %.2f, d = %.2f\n", a / 100., b / 100., c / 100., d / 100.);
            }
}

```

# Answer
> 1 votes
# GNU Prolog REPL, 57 bytes

(The REPL input ends with two newlines, which are included in the byte count.)

```
A+B+C+D#=711,A*B*C*D#=711000000,fd_labeling([A,B,C,D]).

```

The first line prints the first solution (very quickly, in fact; `fd_labeling` often needs tuning to run quickly, but it didn't in this case). GNU Prolog's generates the solution which has the arguments in sorted order first. In this case, only one solution is in sorted order, so we can enter a newline at the "more solutions?" prompt to not generate the remaining solutions; arguably this is hardcoding the *number of solutions*, but as required by the question, it doesn't hardcode the *values* in the solution. Uses fixed-point arithmetic (so the numbers are printed without a decimal point), because GNU Prolog's built-in equation solver handles only integers.

This is just a case of finding a language with a language feature that solves the problem almost directly. Mathematica might be the obvious choice, but GNU Prolog has a constraint solver too. If only the REPL ran `fd_labeling` automatically! (Come to think of it, maybe I should write a language that uses GNU Prolog's constraint solver behind the scenes and has a terser syntax; it'd be useful in this sort of challenge when it comes up in the future, and possibly even for general use. Oh, and that's designed to solve problems using normal arithmetic operations rather than INTERCAL's.)

# Answer
> 1 votes
**K, 67 chars**

Brute force, requires about ten seconds.

For information about K (unique mix of APL, functional, and Database programming language). see kdb.com

```
{if[(_711e6)=*/r:x,711-+/x;R::r]}'?{|':1+a\:x}'!*/a:3#_711%4;R%100

```

generates the answer

```
1.2 1.25 1.5 3.16

```

Explanation:

* Algorithm:

+ Generates range 1..711/4 for each of three values
    + calculates the fourth as 711-sum of the other three
    + Filter to guarantee ascending order of the values
    + Calculates product of values and compare with 711000000
* About syntax

+ Many predefined functions are one-letter operators. There are diad (x OP y) and monad (OP x) variants. Evaluation left to right, no precendence, ';' as sentence separator, 'var : value' to assign. {..} defines an anonimous function
    + diads: % is divide, x:y computes list fo digits of y in x-base, x#y takes, | is max
    + monads: _ is floor, f/ reduces list with funcion f (ej. \*/ calculates product, +/ calculates sumation), !x generate values 0..x-1, ?x return unique values of list x, f': applies f to each pair of the argument list (|':x to guarantee non.decreasing values)
    + func'args applies the function over each of the args

# Answer
> 0 votes
## Scala  168  139

```
def h(i:Int)=i/100.0
val x=711
for(a<-1 to x;
b<-a to x;
c<-b to x;
d=x-a-b-c
if(d>c&&h(a)*h(b)*h(c)*h(d)==7.11))yield(h(a),h(b),h(c),h(d))

```

# Answer
> 0 votes
## Mathematica

```
Solve[
    a + b + c + d == a * b * c * d / 10^6 == 711
        && 0 < a <= b <= c <= d,
    {a, b, c, d},
    Integers
]

```

Basically, solve it as an integer Diophantine equation. The advantage is that this avoids possible floating-point error.

On my computer, Mathematica runs out of memory, but it *might* work in principle...

It might be possible to run this on Wolfram Alpha, but I'm not familiar enough with its syntax.

In Mathematica, this is 58 characters + 1 fraction line + 1 exponentiation box.

---
Tags: code-golf
---