title: Palindromic palindrome generator

text:
# Question
Title: Palindromic palindrome generator
Create a program, that converts input string to a palindrome starting with the input string. The program itself must be a palindrome.

For example input: `neverod`, print `neveroddoreven`. You should handle multi-word, multi-line inputs as well.

# Answer
> 28 votes
# Dyalog APL, 6 4

```
⌽,,⌽

```

Try it here.

Other solutions:

```
⌽,⊢⊢,⌽
⌽⊢⊢,⊢⊢⌽

```

### Explanation

They are just:

```
{⌽((,⍵),(⌽⍵))}
{⌽((,⍵)⊢((⊢⍵),(⌽⍵)))}
{(⌽⍵)⊢((⊢⍵),((⊢⍵)⊢(⌽⍵)))}

```

Monadic `,` and  does nothing on strings. Dyadic `,` is concatenation. Dyadic  returns its right operand. And  is obviously reversion.

# Answer
> 23 votes
# piet 19x2 = 38

Accepts input until it encounters 0x00. Doesn't terminate, but output will be correct.

# Answer
> 19 votes
## APL, 9

```
⍞←Z,⌽,Z←⍞

```

Explanation:

```
       Z←⍞  ⍝ read a line from the keyboard, and store it in Z
      ,     ⍝ flatten into one-dimensional array (this has no effect here)
     ⌽      ⍝ reverse
   Z,       ⍝ concatenate Z to its reverse
⍞←         ⍝ explicit output (not necessary, but it makes it a palindrome)

```

# Answer
> 13 votes
# CJam, 13 bytes

```
qL;_-1%1-_;Lq

qL;                 "Read the input, Put an empty array on stack and pop that array";
   _-1%             "Now the string is on top, make a copy and reverse the copy";
       1-           "Remove occurrences of integer 1 from the reverse string. [no-op]";
         _;         "Copy the reversed string and pop it";
           Lq       "Put an empty array on stack and read the remaining input. Remaining";
                    "input will be empty as we already read whole of the input";

```

Try it online here

---

or..

# GolfScript, 9 bytes

```
.-1%}%1-.

.                 "Input is already on stack. Make a copy";
 -1%              "Reverse the copy";
    }             "This marks the beginning of a super comment. Anything after this in the";
                  "code is a comment";
     %1-.         "no-op comment";

```

Try it here

# Answer
> 8 votes
## C++, 162 bytes

```
#include<cstdio>//
main(){int c=getchar();if(c>0)putchar(c),main(),putchar(c);}//};)c(rahctup,)(niam,)c(rahctup)0>c(fi;)(rahcteg=c tni{)(niam
//>oidtsc<edulcni#

```

## C, 117 bytes

```
main(c){c=getchar();if(c>0)putchar(c),main(),putchar(c);}//};)c(rahctup,)(niam,)c(rahctup)0>c(fi;)(rahcteg=c{)c(niam

```

# Answer
> 8 votes
# Haskell, 102+22=124 bytes

```
a b fa=fa<|>b
fa=reverse>>=a
main=interact fa
niam=main
af tcaretni=niam
a=>>esrever=af
b>|<af=af b a

```

This must be run with the `Control.Applicative` module in scope, which can be set via the ghci init file `.ghci`: `:m Control.Applicative` (-\> +22 bytes).

No comment trick, just 7 functions where 4 of them are never called.

If functions (instead of programs) are allowed:

# Haskell, 55+22=77 bytes

```
a b fa=fa<|>b
f=reverse>>=a
a=>>esrever=f
b>|<af=af b a

```

Usage `f "qwer"`-\> `"qwerrewq"`

Edit: the previous version was just wrong.

# Answer
> 3 votes
# Pyth, 11 bytes

```
+z_z " z_z+

```

In Pyth, anything preceding with a space is not printed. So we simply add the negative of the string to itself, put a space, start a string and mirror the left side of the quote"

Try it online here

# Answer
> 3 votes
# Ruby, 44

```
s=gets p
s+=s.reverse||esrever.s=+s
p steg=s

```

Takes a multiline string as input from stdin, outputs a Ruby representation of that string concatenated to its reverse. Could trim a character by replacing `||` with `#` to comment out the dead code on the second line.

# Answer
> 3 votes
# Jolf, 9 bytes

Try Here

```
aη+i_i+ηa

```

Explanation: I only just started Jolf and I don't think I'm explaining this properly.

```
aη         alert function, arity of the function can't be reduced by 1 so it stays at 1
  +i_i     concatenate the input with the reversed input
      +η   arity of the add reduced by 1, it just takes the following character (a)
        a  returns the input

```

# Answer
> 3 votes
## PowerShell, 67

```
$args|%{$_+-join$_[$_.Length..0]}#}]0..htgneL._$[_$nioj-+_${%|sgra$

```

Try it online

As suggested by @mazzy the code can be shortened by 12 bytes when using a static range. This, however, limits the input length to 9KBytes. Theoratically 9MBytes would be possible but it would slow down the code significantly.

```
$args|%{$_+-join$_[9kb..0]}#}]0..bk9[_$nioj-+_${%|sgra$

```

# Answer
> 3 votes
# Japt, 4 bytes

```
êêêê

```

Try it online!

### How it works

```
U.ê("ê".ê("ê"))  Transpiled to JS

       .ê("ê")   String.ê(string): true if `this` is palindrome
    "ê".ê("ê")   true (treated same as 1)
U.ê(          )  String.ê(number): palindromify
                   "abc"->"abccba" if `number` is odd, "abcba" otherwise
                 `true` is odd number, so we achieve the desired function

```

# Alternative 4 bytes

```
pwwp

```

Try it online!

### How it works

```
U.p("w".w("p"))  Transpiled to JS
    "w".w(   )   Reverse of "w" ("p" is ignored)
U.p("w")         Append U.w(), which is reverse of U, to the right of U

```

# Answer
> 2 votes
# Fuzzy Octo Guacamole, 17 bytes

```
^dz''sjX@Xjs''zd^

```

Alt solution in 19 bytes:

```
^Czs''.jX@Xj.''szC^

```

They both take input, duplicate and reverse, and join the stack.

Explanation:

```
^dz''sj@js''zd^
^                # Get input
 d               # Duplicate ToS (input)
  z              # Reverse ToS
   ''            # Push empty string (for joining separator)
     s           # Move the empty string to the inactive stack
      j          # Join the active stack with the top of the inactive stack as the delimiter and push the result.
       X         # Print the ToS
        @        # End the program
        Xjs''zd^  # Backwards version of the beginning.

```

# Answer
> 2 votes
## \<\>^v, 55 bytes

```
.~""?§0 26 0«0 72!=0_~?(___|___(?~_0=!27 0«0 62 0§?""~.

```

##### Explanation

```
.~""?§0 26 0«0 72!=0_~?(___|___(?~_0=!27 0«0 62 0§?""~.

.                            Input string, push to stack
 ~                           Print top of stack without newline
  ""                         Push empty string to stack
    ?                        Swap top two elements
     §                       Split top of stack (now the user input) with second element of stack (`""`)
      0                      Push 0
        26                   Push 26
           0                 Push 0
            «                Goto ; redirects program to the `|`
                           | Reverses instruction pointer direction, now going left
                          _  Pop stack
                         _   Pop stack (again)
                        _    For the third time, pop the stack
                       )     Decrement top of stack
                      ?      Swap top two elements
                     ~       Print top of stack without newline
                    _        Pop stack
                   0         Push 0
                  =          Execute next instruction only if top two elements of the stack are equal
                 !           Exit, executed only if the top two elements of the stack are equal
               72            Push 27 (pointer is going left, so literal 72 -> value 27
             0               Push 0
            «                Goto _
                          _  (Loop goes on, go back to the first "Pop stack")
                            ___(?~_0=!27 0«0 62 0§?""~. This part is useless and never executed, only for the palindrom requirement

```

What it does is first print the first part of the palindrom, the string itself. Then it stores every letter of the string and the string's length on the stack in reverse order, and print them.

run online (`>` is the prompt, it is not an output of the program)

---

Or, with the string reverse operator :

```
.~—;!;—~.

```

Inputs a string, prints it, reverses it, and prints it. run online

# Answer
> 1 votes
# tinyBF, 40

```
|=||==>|=|=|=+|=>==||==>=|+=|=|=|>==||=|

```

My first thought was Brainfuck, but it's impossible to match the braces... fortunately tinyBF has simpler flow control.

No comments, it takes a null terminated string as input and returns the result in a null terminated string. You can test it here, just be forewarned that it doesn't halt (although Firefox at least prompts to stop the unresponsive script).

**Commented:**

```
|=|                        Retrieve a byte of input.
|                          Positive (opening) bracket.
   ==                      Output the byte.
   >                       Move the pointer in positive direction.
   |=|                     Retrieve a byte of input.
   =                       Switch direction to negative.
|                          Negative (closing) bracket.
=                          Switch direction.
+                          Increment byte to execute return loop.
|                          Opening bracket.
   =>                      Move the pointer in negative direction.
   ==                      Output the byte.
|                          Closing bracket.
|=|                        Output the null terminator.
|==>|=|=|=+|=>==|          ...and keep null terminating it just to be sure.

```

Note that if you encode it into 2 bit instructions, it cuts the size to 10 bytes (wouldn't be a palindrome).

# Answer
> 1 votes
## Python 3, 59 bytes

```
a=input()#
print(a+a[::-1])#([1-::]a+a)tnirp
#()tupni=a

```

I tried my best to find a solution that only used one line but I had no luck.

## Python 3, 79 bytes

```
a=input()#()tupni=a#
print(a+a[::-1])#([1-::]a+a)tnirp
#a=input()#()tupni=a

```

My original attempt in which every line is a palindrome. I don't think that it is necessary for this challenge, but I included it just in case.

# Answer
> 1 votes
# Vitsy, 9 bytes

```
z:Zr?rZ:z
z          Grab all string input from the command line arguments.
 :         Duplicate this stack.
  Z        Print all elements in this stack as a string.
   r       Reverse (reverses an empty stack).
    ?      Go right a stack.
     r     Reverse (reverses the input).
      Z    Print all elements in this stack as a string.
       :   Duplicate the stack (duplicates an empty stack).
        z  Grab all input from the command line (the command line arguments stack is already empty).

```

Try it online!

# Answer
> 1 votes
# Befunge, 37 bytes

```
~:0`!#v_:,
  >:#,_@_,#:>
,:_v#!`0:~

```

Try it online!

The top line pushes and prints every character of input. The second line (before the `@`) prints the stack in reverse, but we enter at the contional `_` to consume the -1 generated when finish reading input. The other half of the code (including those ugly trailing newlines) makes the source a palindrome, but nevers runs.

# Answer
> 1 votes
# C# (~~33~~ 32 + 1) * 2 = ~~68~~ 66 bytes

saved 2 bytes to the use of .Aggregate()

```
s=>s+s.Aggregate("",(a,b)=>b+a);//;)a+b>=)b,a(,""(etagerggA.s+s>=s

```

Oh the good old lambda, you can catch it with

```
Func<string, string> f=<lambda here>

```

and then call it with

```
f("neverod")

```

# Answer
> 1 votes
## Perl, 45 bytes

```
;print$_=<>,~~reverse;m;esrever~~,><=_$tnirp;

```

Pretty straightforward, `print`s the input (`$_=<>`) followed by the `reverse` of it. `reverse` returns `$_` because we're using it in scalar context by prefixing with `~~`. Then we match (`m//` using `;` as delimiter), in void context, against the reverse of the script.

If we can guarrantee we won't have to create a palindrome of `esrever,><=_$tnirp` we can shorten the code to **43 bytes**:

```
g.print$_=<>,reverse.m.esrever,><=_$tnirp.g

```

### Usage

```
echo -n 'neverod' | perl -e 'g.print$_=<>,reverse.m.esrever,><=_$tnirp.g'
neveroddoreven

```

---

## Perl, 26 bytes

**Includes 25 bytes code + 1 for `-p`.**

```
$_.=reverse;m;esrever=._$

```

I don't think this is valid since it requires the `-p` flag which I don't think can be easily combined into the script contents to make a true palindrome. Pretty much the same calls as above, except it relies on the fact that `-p` also adds a `;` behind the scenes (on newer Perls...) to close the `m//`.

### Usage

```
echo -n 'neverod' | perl -pe ';$_.=reverse;m;esrever=._$;'
neveroddoreven

```

# Answer
> 1 votes
# 05AB1E, ~~5~~ 3 bytes

```
R«R

```

-2 bytes thanks to *@ovs*.

Try it online.

**Explanation:**

```
R        # Reverse the (implicit) input
         #  i.e. "neverod" → "doreven"
 «       # Append it to the (implicit) input
         #  → "neveroddoreven"
  R      # Reverse it (no-op, since it's a palindrome)
         # (after which the result is output implicitly)

```

If we are allowed to output `neverodoreven` for the input `neverod`, which is still a palindrome, it can be done in **1 byte** instead with the palindromize builtin:

```
û

```

Try it online.

# Answer
> 1 votes
# Vyxal, 1 byte

```
m

```

Try it Online!

A simple 1-byter - `m` mirrors input by appending its reverse.

# Answer
> 1 votes
# MathGolf, ~~5~~ 3 bytes

```
x+x

```

Try it online.

Or 1 byte if overlapping the last character would be allowed, with the palindromize builtin:

```
ñ

```

Try it online.

**Explanation:**

```
x    # Reverse the (implicit) input
 +   # Append it to the (implicit) input
  x  # Reverse it (no-op, since it's a palindrome)
     # (after which the entire stack is output implicitly)

```

# Answer
> 0 votes
# Pyth, 15

```
 k k+ z_z +k k

```

Notice the space at the beginning and at the end.

Quite annoying task in Pyth. `z_z` prints the desired palindrome, but it prints `z` (the input string) and `_z` the inverse on two different lines. `+` combines the two words, but `+` at the end requires two new statements at the end (and at the beginning). I choose `k` and `k`, which are just empty strings. Then a lot of white space, which suppresses printing (and printing empty spaces, which generate of course line breaks).

Since the white space suppresses every output except the `+z_z`, you can replace the `k`s and literal with arity 0. E.g. `1 2+ z_z +2 1` or `T Z+ z_z +Z T`.

Try it online.

# Answer
> 0 votes
# Javascript, 138 bytes

I'm not using the "comment trick" but I am using the escaped quotation mark trick lol.

```
"a\"};))''(nioj.)(esrever.)''(tilps.b(tacnoc.b nruter{)b(a noitcnuf;";function a(b){return b.concat(b.split('').reverse().join(''));};"\a"

```

# Answer
> 0 votes
# JavaScript, 58 bytes

```
p=>p+[...p].reverse().join``//``nioj.)(esrever.]p...[+p>=p

```

# Answer
> 0 votes
# PHP, 28+1+28=57 bytes

```
<?=($x=$argv[1]).strrev($x);#;)x$(verrts.)]1[vgra$=x$(=?<

```

takes input from command line argument. quote for multi-word, escape newlines for multi-line.

# Answer
> 0 votes
# Python 2, 51 bytes

```
s=input();print s+s[::-1]#]1-::[s+s tnirp;)(tupni=s

```

I'm surprised no-one thought of this! Needs quoted input (`'` or `"`). If functions were allowed, I could have done this for 37 bytes instead:

```
lambda x:x+x[::-1]#]1-::[x+x:x adbmal

```

# Answer
> 0 votes
# C++14, ~~152~~ 116 bytes

As unnamed lambda, assumes `s` to be `string`

```
[](auto s){decltype(s)r;for(auto c:s){r=c+r;}return s+r;}//};r+s nruter};r+c=r{)s:c otua(rof;r)s(epytlced{)s otua(][

```

Old solution:

```
[](auto s){auto r=s;for(auto p=s.rbegin()-1;++p!=s.rend();r+=*p);return r;}//};r nruter;)p*=+r;)(dner.s=!p++;1-)(nigebr.s=p otua(rof;s=r otua{)s otua(][

```

Usage:

```
auto f=[](auto s){decltype(s)r;for(auto c:s){r=c+r;}return s+r;};

main(){
 string a="123456789";
 cout << f(a) << endl;
}

```

# Answer
> 0 votes
# x86-64 Assembly (Microsoft x64 calling convention), 89 bytes:

```
80 39 00 48 8B D1 4C 8B C1 74 0B 48 FF C2 49 FF C0 80 3A 00 75 F5 48 FF CA 8A 02 41 88 00 48 8B C2 48 FF CA 49 FF C0 48 3B C1 77 ED C3 ED 77 C1 3B 48 C0 FF 49 CA FF 48 C2 8B 48 00 88 41 02 8A CA FF 48 F5 75 00 3A 80 C0 FF 49 C2 FF 48 0B 74 C1 8B 4C D1 8B 48 00 39 80

```

Disassembled:

```
 0000000000000000: 80 39 00           cmp         byte ptr [rcx],0
 0000000000000003: 48 8B D1           mov         rdx,rcx
 0000000000000006: 4C 8B C1           mov         r8,rcx
 0000000000000009: 74 0B              je          0000000000000016
 000000000000000B: 48 FF C2           inc         rdx
 000000000000000E: 49 FF C0           inc         r8
 0000000000000011: 80 3A 00           cmp         byte ptr [rdx],0
 0000000000000014: 75 F5              jne         000000000000000B
 0000000000000016: 48 FF CA           dec         rdx
 0000000000000019: 8A 02              mov         al,byte ptr [rdx]
 000000000000001B: 41 88 00           mov         byte ptr [r8],al
 000000000000001E: 48 8B C2           mov         rax,rdx
 0000000000000021: 48 FF CA           dec         rdx
 0000000000000024: 49 FF C0           inc         r8
 0000000000000027: 48 3B C1           cmp         rax,rcx
 000000000000002A: 77 ED              ja          0000000000000019
 000000000000002C: C3                 ret
 000000000000002D: ED                 in          eax,dx
 000000000000002E: 77 C1              ja          FFFFFFFFFFFFFFF1
 0000000000000030: 3B 48 C0           cmp         ecx,dword ptr [rax-40h]
 0000000000000033: FF 49 CA           dec         dword ptr [rcx-36h]
 0000000000000036: FF 48 C2           dec         dword ptr [rax-3Eh]
 0000000000000039: 8B 48 00           mov         ecx,dword ptr [rax]
 000000000000003C: 88 41 02           mov         byte ptr [rcx+2],al
 000000000000003F: 8A CA              mov         cl,dl
 0000000000000041: FF 48 F5           dec         dword ptr [rax-0Bh]
 0000000000000044: 75 00              jne         0000000000000046
 0000000000000046: 3A 80 C0 FF 49 C2  cmp         al,byte ptr [rax+FFFFFFFFC249FFC0h]
 000000000000004C: FF 48 0B           dec         dword ptr [rax+0Bh]
 000000000000004F: 74 C1              je          0000000000000012
 0000000000000051: 8B 4C D1 8B        mov         ecx,dword ptr [rcx+rdx*8-75h]
 0000000000000055: 48 00 39           add         byte ptr [rcx],dil
 0000000000000058: 80

```

Note that the code after the `ret` instruction at `2C` is unreachable so it doesn't matter that it's nonsense

# Answer
> 0 votes
# Backhand, ~~33~~ 27 bytes

```
iH~0}|{<:: oi]io ::<{|}0~Hi

```

Try it online!

Unlike a lot of the solutions here, this one actually *does* use the palindromised code!

### Explanation:

```
i  0 |{      Get the first character and enter the loop
        :  o    Output the character while preserving it
              i  :     Get input and duplicate it
                   <{  Turn around
             ]         Increment the copy to check if EOF
    }| <    Loop again if not EOF
  ~   If EOF, pop the extra copy of EOF
 H    Terminate, printing the contents of the stack.

```

Altogether, the unexecuted instructions are:

```
       :   i  o :   |}0~Hi

```

# Answer
> 0 votes
# Zsh \+ coreutils, <sup>~~33~~</sup> 23 bytes

```
tee >(rev) # )ver(> eet

```

Try it online!

# Answer
> 0 votes
# Python 3, 53 bytes

```
t=input();print(t+t[::-1])#)]1-::[t+t(tnirp;)(tupni=t

```

Try it online!

# Answer
> 0 votes
# Pyth, 7 bytes

```
+ Q_Q +

```

Try it online!

Uses implicit variables at the end of the program, which was not a feature when the other Pyth answers here were posted.

# Answer
> 0 votes
# 05AB1E, 1 byte

```
º

```

Try it online! For multiline input, surround the input in triple quotes (`"""`).

```
º  # full program
º  # push...
   # implicit input...
º  # concatenated with...
   # implicit input...
º  # reversed
   # implicit output

```

# Answer
> 0 votes
# Kotlin, ~~(26+1)\*2=54~~ (19+1)\*2=40 bytes

```
    var palindrome:(String)->String=

```

```
    {s->s+s.reversed()}//})(desrever.s+s>-gnirtS:s{

```

Try it online!

# Answer
> 0 votes
# Headascii, 63 bytes

```
{N)UPO}:+E.N-)++E:{UN)RO}:RPNE.!.ENPR:}OR)NU{:E++)-N.E+:}OPU)N{

```

Try it here! Code will have to be copied and executed like this:

```
erun("{N)UPO}:+E.N-)++E:{UN)RO}:RPNE.!.ENPR:}OR)NU{:E++)-N.E+:}OPU)N{","your input")

```

This was rough. You can't have mismatched curly braces in headass/ascii in code blocks that are accessed, even if the braces are never reached, so I couldn't do anything clever with reusing backwards code.

Explanation:

```
{N)UPO}:+E.N-)++E:{UN)RO}:RPNE.!.ENPR:}OR)NU{:E++)-N.E+:}OPU)N{

{N)UPO}:+E.  Block 0

{     }      Loop, which
 N)    :     While there is still unread input,
   UP        Reads input and concatenates it to the string register
     O       And pushes the input to the "output" array.
        +E   Go to block 1, pop the entire output array,
              and push it onto the input array
          .  Block separator

N-)++E:{UN)RO}:RPNE.  Block 1

N-)                   If there is nothing left in the input array
   ++E                  Go to block 2
      :               Else
       {     }          Loop, which
        U               Reads and discards an input byte
         N)             If there's still more input,
           RO             Recall the discarded byte and
                           save it to the output array
              :         Else, exit the loop, and
               R          Recall the discarded byte and
                P         concatenate it to the string register
                 NE     Return to the start of block 1,
                         pop the entire output array,
                         and push it onto the input array
                   .    Block separator

!.  Block 2

!   Print the string register
 .  Block separator, end execution

ENPR:}OR)NU{:E++)-N.E+:}OPU)N{  Blocks 3 and 4

     }     {           }     {  Tragic mismatched curly braces
                                 which prevent me from reusing
                                 reversed code. These blocks
                                 are invalid and inaccessible

```

Copies the string, repeatedly concatenates the last character of the copy to the original and removes it from the copy, until the copy is gone.

I think block 1 is golfable, but im out of ideas for now. This is pretty much just the canonical solution, without much actual golfing other than `A()`=\>`A)` and `[+` =\> `N` type stuff, small optimizations.

# Answer
> 0 votes
# Scala, 30 bytes

```
s=>s+s.reverse//esrever.s+s>=s

```

Just the "comment trick", I was not able to provide a shorter solution without it :)

Try it online!

# Answer
> 0 votes
# JavaScript, 56 bytes

```
f=([c,...d])=>c?c+f(d)+c:''//'':c+)d(f+c?c>=)]d...,c[(=f

```

Try it online!

Why no one recurse?

# Answer
> 0 votes
# C (gcc), 100 bytes

```
main(c){read(0,&c,1)&&putchar(c,main(write(1)));}//};)))1(etirw(niam,c(rahctup&&)1,c&,0(daer{)c(niam

```

Try it online!

---
Tags: code-golf, string, restricted-source, palindrome
---


title: Generate an arbitrary half of a string

text:
# Question
Title: Generate an arbitrary half of a string
Given a string \\$ x \\$, we say another string \\$ y \\$ is half of it, if both of the following properties are true:

* \\$ y \\$ is a (not necessarily continuous) subsequence of \\$ x \\$ \- there exists a strictly increasing sequence \\$ a\_i \\$ such that \\$ y\_i = x\_{a\_i} \\$
* Each character appears in \\$ x \\$ exactly twice as many times as it appears in \\$ y \\$

For example, "acb", "bac" and "bca" are all halves of "baccba", but "abc" and "ac" aren't.

Given a string with English a-z characters (you can choose if you want it lowercase or uppercase), which you are guaranteed all characters appear an even number of times in, output an arbitrary half of it.

# Test Cases

```
"aaaabbbb" -> "aabb"
"abab" -> "ab", "ba"
"aabbaa" -> "aab", "aba", "baa"
"aabbaaaa" -> "aaba", "abaa", "baaa"
"baccba" -> "acb", "bac", "bca", "cba"
"aabbcc" -> "abc"
"abcabc" -> "abc", "acb", "bac", "bca", "cab"

```

# Rules

* You can use any reasonable I/O format.
* You can print any half of it, or a list containing any non-empty subset of its halves, with or without duplicates.
* The distribution of the output can be whatever you want, as long as only valid outputs have a non-zero chance to be selected.
* Standard loopholes are disallowed.

This is code golf, so the shortest answer wins.

# Answer
> 12 votes
# Python NumPy, 36 bytes

```
lambda s:s[sorted(s.argsort()[::2])]
```

Attempt This Online!

Takes and returns arrays of characters.

# Answer
> 12 votes
# JavaScript (Node.js), 23 bytes

```
a=>a.filter(c=>a[c]^=1)

```

Try it online!

# Answer
> 8 votes
# BQN, 6 bytes

```
⊢/˜2|⊒

```

Try it at BQN REPL

BQN's "Occurrence count" () operator, which returns a number for each element indicating how many previous elements match it, is pretty useful here.
Select elements from the input (`⊢/˜`) specified by the occurrence count of each of them () modulo 2 (`2|`).

# Answer
> 8 votes
# Brachylog, 3 bytes

```
p~j

```

Try it online!

(`jp` with reversed I/O appears not to work.)

Originally, I had `⊇.jp?∧` (which can generate all halves, with an extreme volume of duplicates), but it turns out that the order in which `p` tries permutations maximizes the length of the prefix of items which are not rearranged. So:

```
p      Permute the input such that
 ~j    the output is a string which concatenated with itself is the input.

```

It appears that the output is guaranteed to be in a valid order because of this, but I'm not entirely sure--relevant source if anyone else wants to reason through it, or engineer a counterexample.

# Answer
> 7 votes
# , 11 bytes

```
#~2|1#.]=]\

```

Try it online!

* `#~` Filter by
* `2|1#.]=]\` Prefixes where the count of items that equal the last item is odd.

Just noticed this is the same approach as the BQN answer, though this one I arrived at independently after waking up today.

## port of loopy walt's answer, 14 bytes

```
{~[:/:~_2{.\/:

```

Try it online!

Port of loopy walt's excellent idea.

# Answer
> 6 votes
# Vyxal, 8 bytes

```
ṗṠ'ds?s=

```

Try it Online!

Tack on a `;U` if halves must be unique.

```
ṗṠ       # Subsequences as strings
  '      # Filtered by
   ds    # It doubled, sorted
       = # Equals...
     ?s  # The input sorted

```

# Answer
> 6 votes
# Charcoal, 9 bytes

```
Φθ﹪№…θκι²

```

Try it online! Link is to verbose version of code. Explanation:

```
 θ          Input string
Φ           Filtered where
   №        Count of
       ι    Current character in
     θ      Input string
    …       Truncated to length
      κ     Current index
  ﹪     ²   Is odd

```

# Answer
> 6 votes
# Jelly, 5 bytes

```
Ụm2Ṣị

```

**Try it online!** Or see the test suite.

### How?

Same idea loopy walt had.

```
Ụm2Ṣị - Link: list, X
Ụ     - grade X up -> indices sorted by value
 m2   - mod2 slice -> 1st, 3rd, 5th, etc.
   Ṣ  - sort
    ị - index into X

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), ~~34~~ ~~29~~ ~~26~~ ~~24~~ 23 bytes

```
Select[g@#*=-1&]
_g=1>0

```

Try it online!

Input and output a list of characters. Keeps every other occurrence of each letter, starting from the second.

```
_g=1>0              per-character indicator
Select[        ]    keep in input where:
       g@#*=-1&       negate corresponding indicator
                      (-True is not truthy)
                    (all indicators receive an even # of negations,
                     so are reusable)

```

# Answer
> 4 votes
# Perl 5 `-p`, 27 bytes

```
for$c(a..z){s/$c.*?\K$c//g}

```

Try it online!

# Answer
> 4 votes
# Perl 5 \+ `-lF -M5.10.0`, 20 bytes

```
say grep++${$_}%2,@F
```

Try it online!

# Answer
> 4 votes
# Vyxal, 5 bytes

```
⇧y_sİ

```

Try it Online!

Port of loopy walt's answer. I/O as list of chars.

```
⇧y_sİ
⇧     # Grade up
 y_   # Every other item starting from the first
   s  # Sort
    İ # Index into the input

```

`y_` (uninterleave, pop) could alternatively be `2Ḟ` (every 2nd item).

# Answer
> 3 votes
# lin, 40 bytes

```
.#n.n `pset"2rep.n \;.' eq"`#
.(""sort )

```

Try it here! Outputs an iterator of subsequences.

For testing purposes (use `-i` flag if running locally):

```
"abcabc" ; `_
.#n.n `pset"2rep.n \;.' eq"`#
.(""sort )

```

## Explanation

Similar to @emanresu A's answer. Prettified code:

```
.#n .n `pset ( 2rep .n (.( ""sort )).' eq ) `#

```
* `.#n` input as *n*
* `.n `pset` powerset of *n*
* `(...) `#` filter each subsequence *s*...
    + `2rep` repeat *s*
    + `.n` push *n*
    + `(.( ""sort )).'` sort *s* and *n*
    + `eq` check if equal

# Answer
> 3 votes
# Retina 0.8.2, 34 bytes

```
(.)(?=(?(\1)((?<-3>)|()).|.)*$)\3

```

Try it online! Link includes test cases. Explanation:

```
(.)(?=

```

Capture a character, then looking ahead...

```
(?(\1)

```

... if the initial character appears, then...

```
((?<-3>)|())

```

... unset `$3` if it's set, otherwise set it to the empty string...

```
.|.)*$)

```

... and check all the remaining characters in the string.

```
\3

```

If `$3` is set at this point (i.e. has been toggled an odd number of times), then...

```

```

... delete the character.

# Answer
> 3 votes
# Curry (PAKCS), 28 bytes

```
f[]=[]
f(a:b++a:c)=a:f(b++c)

```

Try it online!

This may returns multiple results, with duplicates, but not necessarily all of them. If this is not allowed, you can add the flag `:set +first` to print only the first result: Try it online!.

# Answer
> 3 votes
# Pyth, 7 bytes

```
q#.-QTy

```

Try it online!

Returns the half of the input which occurs last in the input, repeated for every time it appears as a subsequence of the input.

```
q#.-QTy
      y  subsequences of input
 #       filtered by
  .-QT   multiset difference with input
q        equals the subsequence

```

# Answer
> 3 votes
# Jelly, 13 bytes

```
®;©ṛ
Ç®ċ%2
ÇƇ

```

Try it online!

```
® (load register)
 ; (concatenate with [tacit argument, character we're filtering])
  © (store result of previous link in register)
   ṛ (return right argument [tacit argument, character we're filtering])

Ç (previous link as a monad, [v=character, new_v=character])
 ®ċ (count occurrences of [character] in register)
 %2 (mod2 of [count])

Ç (previous link as monad, [v=character, new_v=1 or 0])
 Ƈ (filter all items, keeping all that satisfy condition, [v=argument])

```

Filter each character, storing them in a growing list of previous seen characters. Every time you see a character for an odd numbered time, keep it.

# Answer
> 3 votes
# x86-64 machine code, 12 bytes

```
AC 84 C0 0F BB C2 77 01 AA 75 F5 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string; and the address of the input, as a null-terminated byte string, in RSI.

In assembly:

```
f:  lodsb           # Load a byte from the string into AL, advancing the pointer.
    test al, al     # Set flags based on that byte. In particular, ZF=1 iff it's 0.
    btc edx, eax    # Invert the bit in EDX indexed by the low 5 bits of that byte.
                    #  Set CF to the previous value of that bit. Leave ZF unchanged.
    ja s            # Jump if CF and ZF are both 0.
    stosb   # (If CF=1 or ZF=1) Add the byte to the output, advancing the pointer.
s:  jnz f           # Jump back, to repeat, if ZF is 0.
    ret             # Return.

```

Because EDX is not initialised, this can keep either the odd instances or the even instances of each letter; either possibility is acceptable. In the TIO demonstration, a `RDRAND` instruction is added to show multiple possibilities.

# Answer
> 2 votes
# , 24 bytes

```
\(x,`+`=order)x[!++x%%2]
```

Attempt This Online!

# Answer
> 2 votes
# Octave / MATLAB, ~~31~~ 30 bytes

```
@(s)s(j^2.^sum(triu(s==s'))>0)

```

Anonymous function that inputs and outputs character vectors.

The code keeps each character that has appeared an even number of times so far.

Try it online!

# Answer
> 2 votes
# 05AB1E, 7 bytes

```
ηε¤¢É}Ï

```

Outputs the first valid prefix.

Try it online or verify all test cases.

Or alternatively (port of *@emanresuA*'s Vyxal answer):

```
æʒº{I{Q

```

Outputs a list of all valid results, with duplicates.

Try it online or verify all test cases.

**Explanation:**

```
η        # Get all prefixes of the (implicit) input-string
 ε   }   # Map each prefix to:
  ¤      #  Push its last character (without popping)
   ¢     #  Count how many times this character occurs
    É    #  Check if the count is odd
      Ï  # Keep all characters of the (implicit) input-string at the truthy indices
         # (after which this string is output implicitly)

æ        # Get the powerset of the (implicit) input-string
 ʒ       # Filter it by:
  º      #  Mirror it (to duplicate its characters)
   {     #  Sort its characters
      Q  #  Check if it's equal to
    I{   #  The input-string with sorted characters as well
         # (after which the filtered list is output implicitly)

```

# Answer
> 1 votes
# Python 3, ~~46~~ 45 bytes

*-1 Thanks to @Command Master*

```
f=lambda s:s and s[:s.count(s[0])%2]+f(s[1:])

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~70~~ 67 bytes

* Saved three bytes thanks to ceilingcat: using K&R-style argument type declaration and a neat `write.2` call to branch on printing a pointed-to character.

```
p[91];main(_,a)char**a;{for(++a;**a;++*a)write(1,*a,!(p[**a]^=1));}

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, 25 bytes

```
^
,
+`,(.)(.*)\1
$1,$2
,

```

Try it online! (Test harness borrowed from Neil's answer.)

### Explanation

```
^
,

```

Insert a comma at the beginning of the string. (Any non-alphabetic delimiter will do.)

```
+`,(.)(.*)\1
$1,$2

```

Repeat until the regex no longer matches: Match the delimiter, the next character after it (group 1), any run of characters (group 2), and the character from group 1 again. Replace with the character from group 1, the delimiter, and group 2.

In effect: Comb through the string from left to right. On each iteration, move the first character to the output section, and delete another copy of that character from later in the string.

```
,

```

Remove the delimiter.

---
Tags: code-golf, string, open-ended-function
---


title: Draw the USA flag

text:
# Question
Title: Draw the USA flag
I noticed that it seems nobody has posted a non-ASCII (related) USA flag challenge yet, so what better time than the 4th of July?

## The Challenge

Draw the current (as of 2022) flag of the United States of America. Here is the flag:

### Specifications

* Hoist (height) of the flag: A = 1.0
* Fly (width) of the flag: B = 1.9
* Hoist (height) of the canton ("union"): C = 0.5385 (A × 7/13, spanning seven stripes)
* Fly (width) of the canton: D = 0.76 (B × 2/5, two-fifths of the flag width)
* E = F = 0.0538 (C/10, one-tenth of the height of the canton)
* G = H = 0.0633 (D/12, one twelfth of the width of the canton)
* Diameter of star: K = 0.0616 (L × 4/5, four-fifths of the stripe width, the calculation only gives 0.0616 if L is first rounded to 0.077)
* Width of stripe: L = 0.0769 (A/13, one thirteenth of the flag height)

The colors used are (as RGB tuples and hex codes):

* White: `255,255,255` or `#FFFFFF`;
* Old Glory Red: `179,25,66` or `#B31942`;
* Old Glory Blue: `10,49,97` or `#0A3161`.

Source: Wikipedia

### Rules

* The image must be sized at a 19:10 ratio, and at least 760 by 400 pixels (if it is a raster image).
* If your language does not allow to use arbitrary RGB colors you may use any colors reasonably recognizable as "white", "red", and "blue".
* The image can be saved to a file or piped raw to STDOUT in any common image file format, or it can be displayed in a window.
* Your program must create the image and not just load it from a website.
* Built-in flag images, flag-drawing libraries, horrendously upscaling a flag emoji or any other emoji are prohibited.

### Scoring

This is , so shortest code wins!

Since the flag can change at any time following the admission of one or more new states, let's make our programs futureproof! **-10 bonus points** if your program can draw other star dispositions by accepting as an **optional** argument a list of star coordinates (which may be a number different than 50) in any coordinate system of your choice (inspired by this challenge).

* If such optional argument is not provided, your program **must** draw the flag as previously described.
* If an empty list is passed as a parameter, you can either draw no stars, or treat it as if no argument has been given (and hence draw the standard flag).
* The other parts of the flag (the stripes and the blue background) must be the same in any case.

---

Sandbox

# Answer
# PostScript, ~~193~~ ~~185~~ ~~170~~ 158 bytes - 10 = 148

```
00000000: 2f73 7b92 4e38 2e32 3392 6c92 3e37 926c  /s{.N8.23.l.>7.l
00000010: 3630 9201 92ad 3020 3492 6b34 7b31 3434  60....0 4.k4{144
00000020: 9288 3020 3492 637d 9283 9242 924d 7d92  ..0 4.c}...B.M}.
00000030: 3328 0a31 61b3 1942 297b 3235 3592 367d  3(.1a..B){255.6}
00000040: 9249 929d 3088 1488 787b 3092 3e32 3437  .I..0...x{0.>247
00000050: 880a 9280 7d92 4892 9d30 883c 3938 2e38  ....}.H..0.<98.8
00000060: 8846 9280 3192 9692 1a30 923d 7b31 8801  .F..1....0.={1..
00000070: 327b 2f69 923e 9233 6920 3288 0b7b 6988  2{/i.>.3i 2..{i.
00000080: 0239 7b31 9258 737d 9248 7d92 487d 9248  .9{1.Xs}.H}.H}.H
00000090: 7d7b 7b7b 737d 9265 7d92 a37d 9255       }{{{s}.e}..}.U

```

Untokenized version:

```
/s{                                            % y x s -
    gsave                                      % star of radius 4 at (x,y)
    8.23 mul exch 7 mul 60 add                 % scale and translate position
    translate                                  % move origin
    0 4 moveto 4{144 rotate 0 4 lineto}repeat  % draw star
    fill                                       % fill it
    grestore
}def
<0a3161b31942>{255 div}forall                  % push blue, red color values
setrgbcolor                                    % red
0 20 120{0 exch 247 10 rectfill}for            % stripes
setrgbcolor                                    % blue
0 60 98.8 70 rectfill                          % rectangle
1 setgray                                      % white
count 0 eq{                                    % if stack empty: standard stars
    1 1 2{/i exch def
      i 2 11{i 2 9{1 index s}for}for           % grid of stars, offset i=1,2
     }for
}{                                             % if stack not empty
    {{s}loop}stopped                           % place stars until stack empty
}ifelse

```

If called without arguments, produces the standard flag.

Takes optional arguments from the stack, which can be inserted from the command line like this:

`gs -c '3 2 5 4' -- usflag.ps`

That plots two stars at (2,3) and (4,5), where (1,1) is the position of the bottom-left star in the standard flag, and the horizontal and vertical units are chosen so that H=1 and F=1.

### Without custom star placement: 131 bytes

Removing the custom star placement code saves 27 bytes:

```
00000000: 280a 3161 b319 4229 7b32 3535 9236 7d92  (.1a..B){255.6}.
00000010: 4992 9d30 8814 8878 7b30 923e 3234 3788  I..0...x{0.>247.
00000020: 0a92 807d 9248 929d 3088 3c39 382e 3888  ...}.H..0.<98.8.
00000030: 4692 8031 9296 3188 0132 7b2f 6992 3e92  F..1..1..2{/i.>.
00000040: 3369 2032 880b 7b69 8802 397b 3192 5892  3i 2..{i..9{1.X.
00000050: 4e38 2e32 3392 6c92 3e37 926c 3630 9201  N8.23.l.>7.l60..
00000060: 92ad 3020 3492 6b34 7b31 3434 9288 3020  ..0 4.k4{144..0
00000070: 3492 637d 9283 9242 924d 7d92 487d 9248  4.c}...B.M}.H}.H
00000080: 7d92 48                                  }.H

```

which only draws the standard flag, and is equivalent to

```
<0a3161b31942>{255 div}forall                  % push blue, red color values
setrgbcolor                                    % red
0 20 120{0 exch 247 10 rectfill}for            % stripes
setrgbcolor                                    % blue
0 60 98.8 70 rectfill                          % rectangle
1 setgray                                      % white
1 1 2{/i exch def i 2 11{i 2 9{
    1 index
    gsave                                      % star of radius 4 at (x,y)
    8.23 mul exch 7 mul 60 add                 % scale and translate position
    translate                                  % move origin
    0 4 moveto 4{144 rotate 0 4 lineto}repeat  % draw star
    fill                                       % fill it
    grestore
}for}for}for

```
> 26 votes

# Answer
# BBC BASIC, ~~210~~ 199 bytes

```
V.19;45840;25,66
F.i=0TO13j=1ANDi+1PLOT101-j,1852*j,i*75N.V.19;2576;49,97,25881;741;450;
F.i=9TO107V.29,i DIV9*61.75;i MOD9*52.5+502;
MOVE0,30F.j=1TO5k=j*88/35MOVE0,0PLOT88-i MOD2,SINk*30,COSk*30N.N.

```

The golfed code contains many of the following obfuscations:

* Abbreviated keywords
* Commands like PLOT and MOVE rendered as lower level VDU commands where expedient for golfing reasons.
* Many pairs of 8-bit VDU codes (terminated by comma) are replaced by 16-bit VDU codes (terminated by semicolon.)

The following are all equivalent: `MOVE x,y`, `PLOT 4,x,y`, `VDU 25,4,x,y`. The value 4 in the plot statement can take many values for everything from moving to drawing rectangles and triangles. BBC basic keeps track of the last two positions of the graphics cursor to facilitate these operations.

**Interpreter**

Download interpreter at https://www.bbcbasic.co.uk/bbcwin/download.html

This interpreter has several differences from the original BBC basic. Firstly the default screen mode is black on white, with the white background being set to `255,255,255` by default.

Secondly, the palette reprogramming `VDU 19`operates quite differently. Original BBC basic could display (depending on mode) up to 16 different logical colours at a time (to save memory) and these could be assigned to any 18-bit physical colour. Reprogramming the palette would immediately change all existing pixels of that logical colour to the new physical colour. With this interpreter, full 24-bit colour is supported and only pixels drawn after the `VDU 19` are affected.

**Explanation**

I selected a value of L=75 and scaled the flag accordingly, in order to make most dimensions integers.

Hopefully the comments below are fairly self explanatory. We draw the stripes first, leaving the cursor at top left to conveniently draw the blue canton by specifying its bottom right corner.

Stars are plotted in the background colour (white.) The origin is changed to the centre of each star prior to plotting for convenience. Stars are plotted on a 9x11 checkerboard grid. Only odd number stars are plotted. For the even number stars, the cursor still moves to trace out the star, but nothing is plotted.

BBC basic keeps track of the last two coordinates visited by the cursor. The stars are drawn as a series of five thin triangles by defining the current point, centre of the star, and the previous point 144 degrees away.

**Ungolfed code**

```
  VDU19,0,16,179,25,66                   :REM Change foreground colour to red
  FORi=0TO13                             :REM Iterate 14 times from bottom to top
    j=1ANDi                              :REM j=0 at bottom of red stripe, j=1 at top
    PLOT100+j,1852*(1-j),i*75            :REM   If j=0 move to bottom right of stripe
  NEXT                                   :REM   If j=1 draw a rectangle from bottom right to top left
  VDU19,0,16,10,49,97                    :REM Change foreground colour to blue
  PLOT101,741,450                        :REM Draw blue canton from top left to bottom right
  FORi=9TO107                            :REM Iterate through 99 possible star positions in checkerboard
    VDU29,i DIV9*61.75;i MOD9*52.5+502.5;:REM Reset the origin to centre of star on 9x11 grid
    MOVE0,30                             :REM Move cursor to top of star
    FORj=1TO5                            :REM Iterate through star points
      k=j*88/35                          :REM k = j * (4/5*PI = 4/5 * 22/7 = 144 degrees)
      MOVE0,0                            :REM Move to centre of star
      PLOT84+i MOD2*3,30*SIN k,30*COS k  :REM If i is odd draw a triangle linking the latest point to the last 2
    NEXT                                 :REM   cursor positions, namely the centre and the previous point
  NEXT                                   :REM   If i is even draw nothing.

```
> 11 votes

# Answer
# Scratch, ~~588~~ 535 bytes

Try it online!

```
define(W)(H
repeat(H
change y by(1
pen down
set x to(W
set x to(-190
pen up
define(X)(Y)(Q
set[y v]to(Y
repeat(Q
set[x v]to(X
change[y v]by(21
repeat((Q)+(1
pen up
go to x(x)y(y
set pen color to[#fff
pen down
set[c v]to[
repeat(5
point in direction(
move(1)steps
turn cw(162)degrees
change[c v]by(2
repeat(5
move(c)steps
turn cw(144)degrees
end
change[x v]by(-5
when gf clicked
go to x(-190)y(-93
set pen color to[#b31942
erase all
repeat(7
[190][15
change y by(16
end
set y to(
set pen color to[668001
[-38][108
(-52)(-8)(5
(-64)(2)(4

```

@att saved 42 bytes by forgoing the -10 byte bonus, and combined the star placement and generation scripts. att also removed the function (custom block) names and converted a hex color to Scratch's RGB system.

## Explanation

```
define(W)(H     custom rectangle function
repeat(H        loop for each px of height
change y by(1   moves up 1px
pen down        applies pen
set x to(W      moves horizontally a specified amount
set x to(-190   resets x-position
pen up          stops applying pen

define(X)(Y)(Q          custom star & placement function
set[y v]to(Y            sets starting y to a specified amount
repeat(Q                loop for each row of stars
set[x v]to(X            sets starting x to a specified amount
change[y v]by(21        increases y value by 21px
repeat((Q)+(1           loop for each star in the width
pen up                  stops applying pen
go to x(x)y(y           goes to coordinate specified by vars
set pen color to[#fff   sets pen color to white
pen down                applies pen
set[c v]to[             sets a counter to null (implicit 0)
repeat(5                loop enough to fill star
point in direction(     resets facing angle
move(1)steps            move 1px in the facing angle
turn cw(162)degrees     rotates 162 degrees
change[c v]by(2         increases the counter 'c'
repeat(5                loop for each point of the star
move(c)steps            moves 'c'px in the facing angle
turn cw(144)degrees     rotates 144 degrees
end                     syntax
change[x v]by(-5        increases the x position

when gf clicked            syntax
go to x(-190)y(-93         resets position
set pen color to[#b31942   sets color to Old Glory Red*
erase all                  clears stage
repeat(7                   loop for each stripe
[190][15                   draw a red stripe
change y by(16             skip over a white stripe
end                        syntax
set y to(                  resets y position
set pen color to[668001    sets color to Old Glory Blue*
[-38][108                  draws the canton
(-52)(-8)(5                draws a 6 by 5 array of stars
(-64)(2)(4                 draws a 5 by 4 array of stars

*The project uses HSB approximations of the specified colors.
 This code uses HEX values and base-10 equivalents.

```
> 8 votes

# Answer
# Desmos, 305 bytes

```
l=[0...9]
a=[1...13]
b=[1...5]
P(x,y)=polygon(x+WcosR,y+WsinR)
W=[1,2/(3+\sqrt5)][mod(l,2)+1]120
R=l\pi/5+\pi/2
0<=x<=7410\{3a-3<=.01y<=3a\}
0<=x<=2964\{18<=.01y<=39\}
w=hsv(0,0,1)
v=rgb(10,49,97)
r=[w,rgb(179,25,66)][mod(a,2)+1]
[P(494i-247,4110-420j)fori=[1...6],j=b]
[P(494i,3900-420j)fori=b,j=[1...4]]

```

Try it on Desmos!

-35 bytes thanks to Aiden Chow
> 7 votes

# Answer
# , 398 bytes

```
\(w='#FFFFFF',r='#B31942',g=\(x,y,d)polygon(x,y,,,F,d),c=7/13,l=c/7,f=c/10,b=1.9,d=.76,h=d/12,z=rep,x=c(z(1:6,5)-.5,z(1:5,4))*2*h,y=1-c(z(1:5,,,6)-.5,z(1:4,,,5))*f*2,p=\(x,y,s=sinpi,d=l*.4,a=0:9/5,e=d*(s(.2)/s(.4))^2)g(x+c(d,e)*s(a),y+c(d,e)*cospi(a),w)){frame();plot.window(c(0,b),0:1);for(i in 0:6)g(c(d*(i>2),d*(i>2),b,b),c(0,l,l,0)+l*i*2,r);g(c(0,0,d,d),c(1-c,1,1,1-c),'#0A3161');mapply(p,x,y)}
```

Attempt This Online!

Takes optional inputs x, y which are the x- and y- components of a list of coordinates.

Multiline form:

```
j=\(w='#FFFFFF',r='#B31942',g=\(x,y,d)polygon(x,y,,,F,d),
  c=7/13,l=c/7,f=c/10,b=1.9,d=.76,h=d/12,z=rep,x=c(z(1:6,5)-.5,z(1:5,4))*2*h,y=1-c(z(1:5,,,6)-.5,z(1:4,,,5))*f*2,
  p=\(x,y,s=sinpi,d=l*.4,a=0:9/5,e=d*(s(.2)/s(.4))^2)g(x+c(d,e)*s(a),y+c(d,e)*cospi(a),w)){
  frame()
  plot.window(c(0,b),0:1)
  for(i in 0:6)g(c(d*(i>2),d*(i>2),b,b),c(0,l,l,0)+l*i*2,r)
  g(c(0,0,d,d),c(1-c,1,1,1-c),'#0A3161')
  mapply(p,x,y)
}

```

The ratio of inner to outer diameters of the pentagonal star was calculated using a pair of similar isoceles triangles with tip angle pi/5 (36 degrees).

`j()` plots the following:

`j(x=c(0.2,0.3),y=c(0.7,0.8))` plots the following:

A few bytes could be saved by not pre-defining w/r since they are only used once.
> 3 votes

# Answer
# SVG(HTML5), ~~576~~ ~~560~~ 522 bytes

```
<svg viewBox=0,0,741,390><path d=M0,15H741m0,60H0m0,60H741m0,60H0m0,60H741m0,60H0m0,60H741m0,60H0 stroke=#B31942 stroke-width=30 /><rect width=296.4 height=210 fill=#0A3161 /><g fill=#fff><g id=8><g id=9><g id=5><g id=4><g id=2><path id=1 d=M24.7,9,31.7534230,30.7082039,13.2873218,17.2917961H36.1126782L17.6465770,30.7082039z /><use href=#1 y=42 /></g><use href=#2 y=84 /></g><use href=#1 y=168 /></g><use href=#4 x=24.7 y=21 /></g><use href=#9 x=49.4 /></g><use href=#8 x=98.8 /><use href=#9 x=197.6 /><use href=#5 x=247
```

I started trying to code this manually but half-way though I discovered that Jay Bala's Wikipedia specification image linked in the question had already golfed the repetition of the stars, so I just removed the explanation, updated the colours to match the question, and golfed it down to the bare minimum acceptable in HTML5. Edit: Turns out that I'd been looking at the wrong image all along - as @Deadcode points out the flag itself is linked in the question, and it uses `#fff` instead of `#ffffff` in two places, thus saving 6 bytes, but I was able to save a further 10 bytes by golfing the star repetition even further. Edit: Saved 38 bytes thanks to @bartyslartfast by dividing all the lengths by 10 and by assuming a white background and only drawing the red stripes.
> 3 votes

# Answer
## SVG(HTML5), 369 bytes

At first glance, repeating the stars with a `<use>` element looks like a good idea, but it isn't. A `<pattern>` element, even with the pesky `patternUnits=userSpaceOnUse` gets much better results.

Node positions of the stars have been rounded to integers, but that leaves the error \<1.25% (0.5 for diameter=40).

```
<svg viewBox=0,0,1235,650><pattern id=p x=22 y=16 width=82 height=70 patternUnits=userSpaceOnUse><path d=M7,35,19,0,31,35,0,13H38ZM48,70,60,35,72,70,41,48H79Z fill=#fff /></pattern><path d=M0,25H1235m0,100H0m0,100H1235m0,100H0m0,100H1235m0,100H0m0,100H1235 stroke=#B31942 stroke-width=50 /><path d=M0,0H494V350H0Z fill=#0A3161 /><path d=M22,16h451v315H22Z fill=url(#p)
```
> 3 votes

# Answer
# Mathematica, 40 bytes

```
Entity["Country", "UnitedStates"]["Flag"]

```

This is not competing, since it does not follow the rules. But it shows off the power of Mathematica, IMHO.
> 1 votes

# Answer
# Python3 (pillow), 403

```
from PIL import Image,ImageDraw as X
W,R,I,O,N=0xffffff,range,Image.new('RGB',(1001,520),4331955),56,66
d=X.Draw(I);Q=d.rectangle
[Q((0,j,1001,40+j),fill=W)for j in R(40,520,80)];Q((0,0,400,279),fill=6359601)
d.polygon([x-20for x in map(ord,'2 0*$*-0+:239:70@*4*2 ')],fill=W)
s,P=I.crop((16,12,44,38)),I.paste;[(P(s,(16+i*N,12+j*O)),P(s,(50+j*N,40+k*O)))for i in R(6)for j in R(5)for k in R(4)]
I.show()

```
> 1 votes

---
Tags: code-golf, kolmogorov-complexity, graphical-output
---


title: Written Word Equation

text:
# Question
Title: Written Word Equation
Word equations, but not as you know it! Given a sentence which will include two numbers, numerically, and a spelt operator, in the order seen in the examples, your goal is to give the numerical answer

The operators will be spelt as: "add", "minus", "times" and "divide"

Any ~~real number~~ integer may be used, as suggested by caird and Jonathan

The solution must take one input and give one output

**Examples**:

```
Input: 7 add 8         Output: 15
Input: 9 times -2      Output: -18
Input: 24 divide 2     Output: 12
Input: 4 minus 5       Output: -1

```

You are not required to deal with divide by zero errors.

If you use a method that parses the expression, such as the python eval or exec, there will be no penalties, but if possible try to give a another interesting solution

**Scoring:**

Fewest bytes will win

# Answer
> 7 votes
# Jelly, 14 bytes

```
Ḣ€Oị2¦“×+ _÷”V

```

Try it online!

Takes input as e.g. `[7, 'add', 8]`. Requires no leading `0` for floats (e.g. `-.5` instead of `-0.5`)

## How it works

```
Ḣ€Oị2¦“×+ _÷”V - Main link. Takes a list [l, op, r]
Ḣ€             - First of each.
  O            - Convert to ordinal
    2¦         - To the element at the 2nd index (the op):
   ị  “×+ _÷”  - Index into the string “×+ _÷”
             V - Evaluate as Jelly

```

For example, consider `[7, 'add', 8]`. Getting the ead of a number leaves it as is in Jelly, so `Ḣ€` turns this into `[7, 'a', 8]`. We then get the char code of each. Again, `O` leaves numbers as they are, so this maps it to `[7, 97, 8]`. We then change only the second element by indexing into `“×+ _÷”`. Jelly indexing is modular, so we get the \\$97 \bmod 5\\$th element of this list (i.e. the second, or `+`). This yields `[7, '+', 8]`, which we then concatenate into a string `7+8` and evaluate as Jelly.

Consider:

| Input operator | First character | Ordinal | \\$\bmod 5\\$ | Index into `“×+ _÷”` |
| --- | --- | --- | --- | --- |
| `add` | `a` | 97 | 2 | `+` |
| `times` | `t` | 116 | 1 | `×` |
| `minus` | `m` | 109 | 4 | `_` |
| `divide` | `d` | 100 | 0 | `÷` |

Note that `0` maps to `÷` as 1-indexed modular indexing means that `0` is the last element

# Answer
> 3 votes
# Factor, 53 bytes

```
[ first3 swap first 5 mod { / * + 0 - } nth execute ]

```

Try it online!

This is a port of @caird coinheringaahing's Jelly solution.

## Explanation:

It is a quotation (anonymous function) that takes a list of objects from the data stack as input and leaves an integer on the data stack as output. Assuming `{ 7 "add" 8 }` is on the data stack when this quotation is called...

* `first3` Put the first three elements of a sequence on the data stack.

**Stack:** `7 "add" 8`
* `swap` Swap the top two objects on the data stack.

**Stack:** `7 8 "add"`
* `first` Get the first element of a sequence. (In this case, get the first code point of the string "add".)

**Stack:** `7 8 97`
* `5 mod` Modulo 5.

**Stack:** `7 8 2`
* `{ / * + 0 - }` Push a sequence with the possible mathematical functions. `0` is a filler that will never be selected because 3 is not a possible index.

**Stack:** `7 8 2 { / * + 0 - }`
* `nth` Take an index and a sequence and return the object at that index.

**Stack:** `7 8 +`
* `execute` Execute a word that is on the data stack.

**Stack:** `15`

# Answer
> 3 votes
# AWK, ~~41~~ 38 bytes

```
$0=/a/?$1+$3:/t/?$1*$3:/v/?$1/$3:$1-$3

```

Try it online!

*Thanks to Dominic van Essen for the clue that cut 3 chars!*

```
$0=                                     -- Override $0, prints automatically
   /a/?$1+$3:                           -- If there's an "a" we add them
             /t/?$1*$3:                 -- If there's a "t" it's multiplication
                       /v/?$1/$3:       -- If there's a "v" it's division
                                 $1-$3  -- It must be subtraction...

```

If we have to make sure it will print in the event the operation yields `0` then it would be 2 characters longer, like this.

```
1,$0=/a/?$1+$3:/t/?$1*$3:/v/?$1/$3:$1-$3

```

# Answer
> 3 votes
# C (gcc), ~~86~~ \\$\cdots\\$ ~~74~~ 73 bytes

```
m;a;b;f(){scanf("%d %c%*s%d",&a,&m,&b);m%=5;a=m?m-1?m-2?a-b:a+b:a*b:a/b;}

```

Try it online!

*Saved a byte thanks to tsh!!!*

Inputs the equation as a string from `stdin`.
Returns the value of the input equation.

### Allowing three parameters:

As allowed for untyped languages like this PHP answer.

# C (gcc), ~~54~~ ~~52~~ 51 bytes

```
f(a,s,b)int*s;{a=(int[]){a/b,a*b,a+b,0,a-b}[*s%5];}

```

Try it online!

*Saved 2 bytes thanks to the man himself Arnauld!!!*
*Saved a byte thanks to Johan du Toit!!!*

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

Expects a string.

```
s=>([a,[b],c]=s.split` `,{a:a-+-c,t:a*c,d:a/c,m:a-c}[b])

```

Try it online!

---

# JavaScript (ES6), 43 bytes

Expects `[a, "operator", b]`.

```
([a,[b],c])=>({a:a+c,t:a*c,d:a/c,m:a-c})[b]

```

Try it online!

Or **41 bytes** if we can take 3 distinct parameters as input (as suggested by Shaggy).

# Answer
> 2 votes
# Java (JDK), 50 bytes

```
(a,o,b)->o[0]<98?a+b:o[0]<'e'?a/b:o[0]<'n'?a-b:a*b

```

Try it online!

Input is a `int, char[], int`.

* -36 bytes from @ceilingcat
* -49 bytes from @Kevin Cruijssen

### Orignal: Java (JDK), 135 bytes

```
int o(int a,String o,int b){switch(o.charAt(0)){case'a':return a+b;case'm':return a-b;case't':return a*b;case'd':return a/b;}return 0;}

```

Try it online!

Simple switch

# Answer
> 2 votes
# Python 2, 83 bytes

```
exec'print '+''.join([`x`,'/*+ -'[ord(str(x)[0])%5]][type(x)==str]for x in input())

```

Try it online!

# Answer
> 2 votes
# Pip, 16 bytes

```
VaR+XL"/*+ -"@A_

```

Takes input as a single command-line argument. Try it online!

### Explanation

Uses the same "character code mod 5" trick as several other answers.

```
 a                ; First command-line argument
  R               ; Replace all occurrences of
   +XL            ; the regex [a-z]+ (run of lowercase letters)
                  ; with the following callback function:
              A_  ;  ASCII code of the first character
      "/*+ -"@    ;  used as a (cyclical) index into that string
V                 ; After replacing, evaluate the resulting string as a Pip expression

```

---

If taking input as three separate arguments is allowed (e.g. if you can just type `python pip.py equation.pip 9 times -2` on the command line), then it's **15 bytes**:

```
Va."/*+ -"@Ab.c

```

Try it online!

And here's a solution without eval (using three separate arguments) in **18 bytes**:

```
[a/ca*ca+c0a-c]@Ab

```

Try it online!

# Answer
> 2 votes
# Vyxal `r`, ~~15~~ ~~14~~ 13 bytes

```
ǔ÷hC`/*+ -`iĖ

```

*-5 bytes thanks to inspiration from @Kevin Cruijssen's 05AB1E answer*

*-2 bytes thanks to @Steffan*

Try it Online! or verify all test cases

Pretty much a port of most of the other answers.

Explanation:

```
ǔ              # Rotate list to the right to get [r, l, op]
 ÷             # Pop then push each item onto the stack
  h            # Get the head (first item) of the operator
   C           # Convert to ASCII code
    `/*+ -`i   # Use that to index into the string "/*+ -"
            Ė  # Execute as Vyxal code (r flag reverses args)

```

# Answer
> 1 votes
**Python3 142 bytes**

```
def f():
a,b,c=input().split(' ');x=b[0];i=int(a);j=int(c);z=i+j if x=='a' else i*j if x=='t' else int(i/j) if x=='d' else i-j;print(z)

```

Splits tokens, applies operator and prints result

# Answer
> 1 votes
# C (gcc), 95 bytes

Fixed and -2 bytes thanks to Arnauld.

Not too fancy, uses scanf and abuses memory by writing the whole string at the address of a char, mod 5 to get b in single digit range, then ternaries to pick the result.

I had a 0 as the true value for the innermost ternary.... But somehow gcc is perfectly happy without it, if anyone can explain how that works I would appreciate the comment.

```
a,c;main(){char b;scanf("%d %s %d",&a,&b,&c);b%=5;printf("%d",b-2?b-4?b-1?b?:a/c:a*c:a-c:a+c);}

```

Try it online!

# Answer
> 1 votes
# PHP, 55 bytes

```
fn($a,$b,$c)=>[$a/$c,$a*$c,$a+$c,0,$a-$c][ord($b[0])%5]

```

Try it online!

uses the format `[7, 'add', 8]`

Nothing new under the sun, combines the tricks used in other answers.

# Answer
> 1 votes
# Japt, 15 bytes

Takes input as an array. Thought there might be some other clever way of working with the charcodes to get the required operator but using caird's method of indexing into the operators seems to be optimal.

```
OvUg1_Îcg"/*+ -

```

Try it

Or without using `eval`:

```
rUj1 ÎÎcg"/*+ -

```

Try it

```
OvUg1_Îcg"/*+ -     :Implicit input of array U
Ov                  :Eval as Japt
  Ug1               :  Modify the element at 0-based index 1 in U
     _              :  By passing it through the following function
      Î             :    First character
       c            :    Charcode
        g"/*+ -     :    Index into "/*+ -"

```

```
rUj1 ÎÎcg"/*+ -     :Implicit input of array U
r                   :Reduce by
 Uj1                :  Remove & return, as a singleton array, the element at 0-based index 1 in U
     Î              :  First element
      Îcg"/*+ -     :  As above

```

# Answer
> 1 votes
# 05AB1E, ~~15~~ 14 bytes

```
ι˜`¨C"*+-÷"è.V

```

Input as a list.

Try it online or verify all test cases.

**Explanation:**

```
ι               # Uninterleave the (implicit) input-list:
                #  [a,"O",b] becomes [[a,b],["O"]]
 ˜              # Flatten this list: [a,b,"O"]
  `             # Pop and push the three values separated to the stack
   ¨            # Remove the last character of the operator string
    C           # Convert it from a binary string to an integer
     "*+-÷"è    # Modulair 0-based index it into string "*+-÷"
            .V  # Evaluate it as 05AB1E code
                # (after which the result is output implicitly)

```

| String | `¨` | `C` | Modulair 0-based index | Operator |
| --- | --- | --- | --- | --- |
| and | an | 121 | 1 | + |
| minus | minu | 714 | 2 | - |
| times | time | 752 | 0 | * |
| divide | divid | 1331 | 3 | ÷ |

`C` on strings basically gets the index of each characters in the string `0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzǝʒαβγδεζηθвимнт ΓΔΘιΣΩ≠∊∍∞₁₂₃₄₅₆ !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~Ƶ€Λ‚ƒ„…†‡ˆ‰Š‹ŒĆŽƶĀ‘’“”–—˜™š›œćžŸā¡¢£¤¥¦§¨©ª«¬λ®¯°±²³\nµ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ•`, and then converts this list of indices to a base-2 integer.

# Answer
> 1 votes
# Python 3, 91 bytes

```
def f(a):a,b,c=a;b=b[0];d=b=='d';return(a+c*((b=='a')-(b=='m')))*[1,[c,1/c][d]][b=='t'or d]

```

Takes a single input as a listed of the values, i.e. `[7, "add", 8]` and returns the result of the equation.

Try it online!

# Answer
> 1 votes
# Python 3, 71 bytes

```
x,y,z=input().split()
print(eval(f'{x}{"/*+ -"[ord(str(y)[0])%5]}{z}'))

```

Try it online!

Inspired by various other answers featuring `ord(str(y)[0])%5`.

If the input is taken as a list like `[5, 'minus', 8]`, then you can get an answer of only 67 bytes;

```
lambda l:print(eval(f'{l[0]}{"/*+ -"[ord(str(l[1])[0])%5]}{l[2]}'))

```

Try it online!

# Answer
> 0 votes
# Charcoal, 26 bytes

```
Ｎθ≡§Ｓ⁰aＩ⁺θＮmＩ⁻θＮtＩ×θＮdＩ∕θＮ

```

Try it online! Link is to verbose version of code. Explanation: Inputs the first number, switches on the string then inputs the second number as it outputs the result of the appropriate operation. 20 bytes with a boring eval-based approach:

```
ＩＵＶ⁺θ⁺§+-*/⌕amtd§η⁰ζ

```

Try it online! Link is to verbose version of code. Explanation: Gets the appropriate Python operator depending on the first letter of the string and evaluates the result as a Python expression.

# Answer
> 0 votes
# Perl 5 `-p`, 44 bytes

```
s/a/+/;s/t/*/;s|v|/|;s/n/-/;s/\pL//g;$_=eval

```

Try it online!

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


title: Array Sandwiches

text:
# Question
Title: Array Sandwiches
(Adapted from Problem C of the first qualifier of the ACM Programming Contest of 2012/2013)

You have several arrays, named \\$A\_1, A\_2, ... , A\_n\\$, each sorted in ascending order. Every item in the array will be a 32-bit integer.

A **sandwich** is a set of indices \\$j\_1, j\_2, ... , j\_n\\$ such that \\$A\_1\[j\_1\] ≤ A\_2\[j\_2\] ≤ ... ≤ A\_n\[j\_n\]\\$. \\$A\_i\[0\]\\$ is the first element of \\$A\_i\\$.

Given some arrays, output every possible sandwich that you can have from those arrays, separated by a newline.

If there is somehow a built-in function which does this in your language, don't use it.

Input can be given in any way, output must be separated with whitespace, but can given in any order.

Test Case:

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

```

Output:

```
0 0 0
0 0 1
0 0 2
0 1 2
0 2 2
0 3 2
1 1 2
1 2 2
1 3 2
2 3 2

```

Test Case:

```
[[10, 20, 30], [1, 2, 3]]

```

Output:

Shortest code wins.

# Answer
> 3 votes
## APL (33)

```
↑1-⍨B/⍨{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B←,⍳⊃∘⍴¨A←⎕

```

Input is read from the keyboad, but it must be given as an APL list, i.e.

```
(1 5 7 10) (2 6 6 8 12) (4 5 9)

```

Explanation:

* `B←,⍳⊃∘⍴¨A←⎕`: A is evaluated input, B is all possible sets of indices in the lists given in A.
* `{(⍳⍴A)∘≡⍋⍵⌷¨A}¨B`: for each set of indices, get the values from the lists (`⍵⌷¨A`) and see if they are sorted (`(⍳⍴A)∘=⍋`)
* `B/⍨`: select from B all sets of indices where the previous expression was true (i.e. all the sandwiches)
* `1-⍨`: subtract one from all indices, because this question assumed 0-based arrays and APL-arrays are 1-based by default.
* : arrange the list of sets of indices as a matrix (so each set is on its own line)

# Answer
> 3 votes
## GolfScript, 51 chars

```
~:A{,}%{*}*,{A{,.@.@/\@%}%\;}%{:k,,{.A=\k==}%.$=},`

```

Example input (on stdin):

```
[[1 5 7 10] [2 6 6 8 12] [4 5 9]]

```

Example output (to stdout):

```
[[0 0 0] [0 0 1] [0 0 2] [0 1 2] [1 1 2] [0 2 2] [1 2 2] [0 3 2] [1 3 2] [2 3 2]]

```

(Note that input *must* be given without commas, otherwise the program will most likely crash.)

---

I guess I should add some explanation about how this code works:

* `~:A` just evaluates the input as GolfScript code and assigns the result (an array of arrays) to `A`. It also leaves a copy of `A` on the stack for the next step.
* `{,}%` replaces each sub-array with its length, and `{*}*` multiplies those lengths together, giving the total number of possible sandwich candidates. This number is then converted by `,` to an array of that many successive integers starting from 0.
* `{A{,.@.@/\@%}%\;}%` converts each number into a the corresponding sandwich candidate (i.e. an array of valid indices into each sub-array in `A`). For example, given the input above, `0` would map to `[0 0 0]`, `1` to `[1 0 0]`, `2` to `[2 0 0]`, `3` to `[3 0 0]`, `4` to `[0 1 0]` and so on. (Figuring out exactly how the code accomplishes that is left as an exercise for the interested reader.)
* `{:k,,{.A=\k==}%.$=},` filters the sandwich candidates by mapping each of them to the corresponding elements of the sub-arrays of `A` (so that e.g. `[0 0 0]` would yield `[1 2 4]`, `[1 0 0]` would yield `[5 2 4]`, and so on, for the input above), sorting the resulting array and comparing it with an unsorted copy. If they are equal, the array was already sorted, and thus the candidate is indeed a sandwich.
* Finally, ``` just turns the filtered array of sandwiches into a string for output.

# Answer
> 3 votes
# Mathematica, 120 130 bytes

## Edit

This version works with arrays of varying sizes.

---

```
l = List;
g = Grid@Cases[Outer[l, Sequence @@ MapIndexed[l, #, {2}], 1]~Flatten~(Length[#] - 1),
x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1] &

```

## Usage

```
g@{{10, 20, 30}, {1, 22, 3}}
g@{{1, 5, 7, 10}, {2, 6, 6, 8, 12}, {4, 5, 9}}
g@{{10, 20, 30}, {1, 2, 3}}
g@{{1, -2, 3}, {-12, -7, 8, 9, 6}, {3, 99, 9}, {100, 10, -23}, {90, 10}}

```

---

## Explanation

Using the first example from above,

```
a = {{10, 20, 30}, {1, 22, 3}}

```

---

`MapIndexed`  sets indices for all the elements. N.B.: Mathematica begins counting with 1. (We'll later take that into account.)

```
MapIndexed[l, a, {2}]

```

> {{{10, {1, 1}}, {20, {1, 2}}, {30, {1, 3}}}, {{1, {2, 1}}, {22, {2, 2}}, {3, {2, 3}}}}

---

`Outer` generates all lists, each a candidate as a sandwich array, and the indices of their elements; `%` contains the results from the prior output. The numbers, `10` and `22` which I highlighted after they were output, refer to a sandwich array `{10,22}` that has yet to be identified as such.

```
Outer[l, Sequence @@ %, 1]~Flatten~(Length[a] - 1)

```

> {{{10, {1, 1}}, {1, {2, 1}}}, {{**10**, {1, 1}}, {**22**, {2, 2}}}, {{10, {1, 1}}, {3, {2, 3}}}, {{20, {1, 2}}, {1, {2, 1}}}, {{20, {1, 2}}, {22, {2, 2}}}, {{20, {1, 2}}, {3, {2, 3}}}, {{30, {1, 3}}, {1, {2, 1}}}, {{30, {1, 3}}, {22, {2, 2}}}, {{30, {1, 3}}, {3, {2, 3}}}}

---

`Cases` tests each element of the above to determine whether a `LessEqual` (less than or equal) relation holds. The results shown below are those instances in which array sandwiches were detected. Once again, I highlighted `{10,22}` in the output.

```
Cases[%, x_ /; LessEqual @@ x[[All, 1]] == True]

```

> {{{**10**, {1, 1}}, {**22**, {2, 2}}}, {{20, {1, 2}}, {22, {2, 2}}}}

---

`%%` refers to the penultimate results. `:>`, \[ RuleDelayed\] returns thos parts of the instances of interest, namely, the indices of the array sandwiches. `-1` corrects for the fact that Mathematica begins arrays with 1 instead of 0.

```
Cases[%%, x_ /; LessEqual @@ x[[All, 1]] == True :> x[[All, 2, 2]] - 1]

```

> {{0, 1}, {1, 1}}

---

`Grid` displays the results in a grid. The first row `0 1` means the that element 0 from the first sublist (i.e. **10**) and the element 1 from the second sublist (i.e. **22**) constitute the first sandwich array that was found.

```
Grid@%

```

> 0 1
>
> 1 1

# Answer
> 2 votes
# Jelly, 10 bytes

```
J€Œpị"ṢƑ¥Ƈ

```

Try it online!

This uses 1-indexing which is the default for Jelly. +2 bytes to use 0-indexing.

## How it works

```
J€Œpị"ṢƑ¥Ƈ - Main link. Takes a 2d array A on the left
 €         - Over each subarray:
J          -   Replace the subarray with its indices
  Œp       - Take the Cartesian product of these indices
        ¥Ƈ - Keep the indices for which the following is true:
    ị"     -   Index into each subarray of A
      ṢƑ   -   The resulting elements are in ascending order?

```

# Answer
> 1 votes
## R - 89 chars

```
i=do.call(expand.grid,lapply(x,seq_along))
i[apply(diff(t(mapply(`[`,x,i)))>=0,2,all),]-1

```

where

```
x = list(c(1, 5, 7, 10), c(2, 6, 6, 8, 12), c(4, 5, 9))

```

or

```
x = list(c(10, 20, 30), c(1, 2, 3))

```

# Answer
> 1 votes
# Python, ~~149~~ ~~141~~ 140

```
import itertools as I;x=input();r=range;print[p for p in I.product(*map(r,map(len,x)))if all(x[i][p[i]]<=x[i+1][p[i+1]]for i in r(len(x)-1))]

```

Python has a useful itertools library that can generate permutations. This just iterates over all possible permutations of valid indices and checks whether they satisfy the criteria.

I think I can make this shorter, still working on it.

Edit: Now all one line for your reading (in)convenience!

# Answer
> 1 votes
# Python 120

```
f=lambda p,k=0:['%i '%j+m for j,v in enumerate(p[0])if v>=k for m in f(p[1:],v)]if p else['']
print'\n'.join(f(input()))

```

... still think, "enumerate" is a very long word.

# Answer
> 1 votes
## GolfScript (44 chars)

```
~{.,,]zip}%{{`{+}+1$\/}%\;}*{2%.$=},{(;2%}%`

```

Same input and output format as Ilmari's entry.

Demo

Rough breakdown:

Map each input row into an array of pairs `[value index]`

```
{.,,]zip}%

```

Fold a Cartesian product over the rows

```
{{`{+}+1$\/}%\;}*

```

Filter to those whose 0th, 2nd, 4th, etc. entries are non-decreasing.

```
{2%.$=},

```

Map each one down to its 1st, 3rd, 5th, etc. entries.

```
{(;2%}%

```

# Answer
> 1 votes
# 05AB1E, 20 bytes

```
εεN].«â€˜ʒεINèsè}¥dP

```

Indexing into matrices is not 05AB1E's strong suit.. :/

Try it online.

**Explanation:**

```
εεN]         #Transform the input to a list of lists of indices:
ε            # Map over each list of the (implicit) input-list:
 ε           #  Map over each inner value in this list:
  N          #   Push the map-index
   ]         # Close both maps

.«â€˜        #Create all combinations of the indices in each list:
.«           # Left-reduce the list of lists by:
  â          #  Taking the cartesian product
   €         # Then map over each inner list of nested lists:
    ˜        #  And flatten the values to a single list

ʒεINèsè}¥dP  #Filter to keep just the indices that are in ascending order
ʒ            # Filter the list of lists of indices by:
 ε           #  Map over each index:
  INè        #   Use the map-index itself to index into the input list of lists
     sè      #   Then use the index we're mapping over to index into this list
       }¥    #  After the map: get all the deltas / forward differences
         d   #  Check for each that they're non-negative (>=0)
          P  #  And check if this is truthy for all of them
             # (after the filter, the result is output implicitly)

```

# Answer
> 1 votes
# Vyxal, 10 bytes

```
vẏΠ'?¨£iÞṠ

```

Try it Online!

Port of Jelly.

# Answer
> 0 votes
# Q, 43

```
{f(&)m~'(asc')m:x@'/:f:(cross/)(!:')(#:')x}

```

# Answer
> 0 votes
# Wolfram Language (Mathematica), 30 bytes

```
#<=##&~Outer~##~Position~True&

```

Try it online!

Returns 1-indexed. For 0-indexing, add `-1` (+2 bytes).

# Answer
> 0 votes
## JavaScript, 138 bytes

```
x=a=>(f=(a,p)=>a[0].flatMap((v,i)=>v<p?null:a[1]?(r=f(a.slice(1),v))&&r.map(j=>j&&[i,...j]):[[i]]))(a).map(i=>i?i.join(' ')+'\n':'').join('')

```

or more readable:

```
x = a => (f = (a, p) => a[0].flatMap(
  (v, i) => v<p
    ? null
    : a[1]
      ? (r = f(a.slice(1), v)) && r.map(j => j && [i, ...j])
      : [[i]]
  )
)(a).map(
  i => i
    ? i.join(' ') + '\n'
    : ''
).join('')

```

# Answer
> 0 votes
# , 22 bytes

```
#&>#:[:I.(-:/:~)@>@,@{

```

Try it online!

Takes input as boxed lists, as J does not allow heterogeneous arrays.

* `>@,@{` The open `>` of the flatten `,` of the Cartesian product `{`. This is just one big matrix whose rows are the elements of the Cartesian product.
* `(-:/:~)@` Which of those matches itself sorted? Returns a single 0-1 boolean list.
* `[:I.` Indices of the ones.
* `#&>#:` Convert to a mixed base number, where the bases are the lengths of the original input lists.

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


title: Runs of Ones (What Fun!)

text:
# Question
Title: Runs of Ones (What Fun!)
Suppose you have an array with some known set of values (e.g. a string of \\$0\\$ and \\$1\\$) and you want to get all the locations of \\$1\\$s. Instead of storing a list of all the indices, if the \\$1\\$s come in "clumps" you can sometimes save space by storing starting and ending indices of "runs" of values -- i.e. substrings which contain just a bunch of \\$1\\$s in a row. For example, take the following list:

```
i =  0 1 2 3 4 5 6 7 8 9
a = [1 0 0 1 1 1 0 0 1 1]
     ^     ^ ^ ^     ^ ^
i =  0     3 4 5     8 9

```

So we output \\$\[(0,0), (3,5), (8,9)\]\\$.

More formally: Given an array \\$\[a\_1, \ldots, a\_n\]\\$ consisting of two distinct values \\$x\\$ and \\$y\\$, output all tuples of indices \\$(i,j)\\$ where the values in the contiguous subsequence \\$\[a\_i, \ldots, a\_j\]\\$ are all \\$y\\$. You must return as few tuples as necessary to cover all \\$y\\$ in the array -- e.g. in the above example you should not return \\$\[(0,0), (3,4), (5,5), (8,9)\]\\$ .

You may use any two distinct values for the input list, and your indices may start from 0 or 1.

Some test cases:

| Input | Output |
| --- | --- |
| \[\] | \[\] |
| \[0\] | \[\] |
| \[1, 1, 1\] | \[(0, 2)\] |
| \[1, 0, 0, 1\] | \[(0, 0), (3, 3)\] |
| \[0, 1, 0, 1\] | \[(1, 1), (3, 3)\] |
| \[1, 0, 0, 1, 1, 1, 0, 0, 1, 1\] | \[(0,0), (3,5), (8,9)\] |

Here's a program to generate test cases.

Standard loopholes are forbidden. Since this is , the shortest program wins.

# Answer
> 1 votes
# Jelly, 8 bytes

```
Tḟ+¥ⱮØ+Z

```

A monadic Link that accepts a list and yields a list of start, end pairs of truthy runs (1-indexed).

**Try it online!**

### How?

```
Tḟ+¥ⱮØ+Z - Link: list, A
T        - Truthy indices of A -> t
     Ø+  - [1,-1]
    Ɱ    - map (for n in [1,-1]) with:
   ¥     -   last two links as a dyad f(t, n):
  +      -     t add n (vectorises)
 ḟ       -     t filter discard those
       Z - transpose

```

# Answer
> 5 votes
# Python, 57 bytes

```
lambda L,i=0:[l+j for j,l in enumerate(L+[0])if i^(i:=l)]
```

Attempt This Online!

Outputs the flattened sequence of endpoints.

### How

Loops using the walrus operator to keep a delayed-by-one copy of the current element. xors to detect changes. By pre- and appending a zero it makes sure that an even number of changes starting with an "on"-change are recorded.

# Answer
> 3 votes
# , ~~52~~ 43 bytes

```
\(x,r=rle(c(0,x)))if(any(x))cumsum(r$l)-r$v
```

Attempt This Online!

Outputs a flat vector 1-indexed.

### Explanation outline:

1. Take run length encoding of the input with `0` prepended.
2. Cumulative sum of the lengths - these are ends of the runs of zeros and ones.
3. Because we prepended a `0`, these are off by one. So actually ends of runs of zeros are starts of runs of ones. And ends of runs of ones are off by one.
4. Correct the above by substracting value of the run.

# Answer
> 2 votes
# Vyxal, 9 bytes

```
aƛ?0pøĖ¦ε

```

Try it Online!

```
aƛ?0pøĖ¦ε
a         # Are there any ones in the list?
 ƛ        # Map over a list in the range [1, that]. For 0 this will just be an empty array, otherwise [1].
  ?       #  Push input
   0p     #  Prepend a zero
     øĖ   #  Run-length encode: Push their values and their lengths, separately, each onto the stack.
       ¦  #  Cumulative sum of the lengths
        ε #  For each in that, take the absolute difference of it and its corresponding value.

```

Returns a singleton list of the list, or in the case of an empty list, an empty list (not `[[]]`). If that's not allowed:

## Vyxal, 10 bytes

```
a[0pøĖ¦ε|¾

```

Try it Online!

```
a[0pøĖ¦ε|¾
a          # Are there any ones in the list?
 [         # If so:
  0p       #  Prepend a zero to the input
    øĖ     #  Run-length encode: Push their values and their lengths, separately, each onto the stack.
      ¦    #  Cumulative sum of the lengths
       ε   #  For each in that, take the absolute difference of it and its corresponding value.
        |  # Otherwise:
         ¾ #  Push an empty list

```

Other solutions:

## Vyxal, 14 bytes

```
ẏ‡?iḊ'h?i;v₍gG

```

Try it Online!

```
ẏ‡?iḊ'h?i;v₍gG
ẏ               # Push a list in the range [0, length)
 ‡  Ḋ           # Adjacent group by:
  ?i            #  Index into the input
     '          # Filter for {when this returns 1}:
      h?i;      #  Index the first item of this list into the input
          v₍gG  # For each, get a list [min, max].

```

Once a bug is fixed, this will work:

## Vyxal, 12 bytes

```
Ġ?żȮ•*~hv₍gG

```

Try it online! Includes a workaround that costs 3 bytes.

```
Ġ?żȮ•*~hv₍gG
Ġ            # Group consecutive identical items into their own list (call this x)
 ?ż          # On the input, get a range [1, length] (call this y)
   Ȯ         # Over, push x again
    •        # Mold y like x
     *       # Vectorizically multiply this by x
     v⟑;     # Bug workaround
      ~h     # Filter for where the first item is not 0
        v₍gG # For each, get a list [min, max]

```

## Vyxal, 11 bytes

```
k+ƛ?T$Ȯ+F;∩

```

Try it Online!

Port of Jelly.

```
k+ƛ?T$Ȯ+F;∩
k+          # Push [1, -1].
  ƛ         # Map over it:
   ?T       #  Get truthy indices in the input (call this X).
     $      #  Swap so the current item (call it Y) is at the top.
      Ȯ     #  Over, push the item next the top item at the stack. Stack: X, Y, X.
       +    #  Vectorizing addition, call this Z.
        F   #  Filter-reject: remove items in X that are in Z.
         ;  # Close map.
          ∩ # Transpose.

```

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

Expects a binary string. Returns a space-separated list of comma-separated 0-based indices.

```
s=>s.replace(/1+|0/g,(s,i)=>+s?[i,i+s.length-1]+' ':'')

```

Try it online!

# Answer
> 1 votes
# Pip `-p`, 13 bytes

```
B-%_MEa@*`\b`

```

Takes a string containing the characters `1` and `,` as a command-line argument. Outputs a flat list of 0-based indices. Try It Online!

### Explanation

```
B-%_MEa@*`\b`
       @*      Find all indices
      a        in command-line argument
         `\b`  of regex matches of word boundaries
               This gives us the beginning and end of each run of 1s, but the end index
               is one past the final 1 in each run, so:
    ME         Enumerate that list and map this function:
B-               The value minus
  %_             its index mod 2
               I.e., subtract 1 from every second element of the list

```

# Answer
> 1 votes
# lin, 46 bytes

```
"1+".?g ?M \; `'
"index""0", g:"len over +1-"'

```

Try it here! Takes string and returns an iterator.

For testing purposes (use `-i` flag if running locally):

```
"1001110011" ; `_
"1+".?g ?M \; `'
"index""0", g:"len over +1-"'

```

## Explanation

Prettified code:

```
"1+".?g ?M \; `'
["index" "0"] g:.( len over + 1- )

```
* `"1+".?g ?M` get matches of consecutive 1s
* `\; `'` map...
    + `["index" "0"] g:` keep index and matched 1s from match object
    + `.( len over + 1- )` get length of 1s, add index, decrement

# Answer
> 0 votes
# Charcoal, 26 bytes

```
ＩΦＥ⪪θ0∧ι⁺⟦⁰⊖Ｌι⟧⁺Ｌ⪫…⪪θ0κωκι

```

Try it online! Link is to verbose version of code. Explanation:

```
    θ                       Input string
   ⪪ 0                      Split on literal string `0`
  Ｅ                         Map over pieces
       ι                    Current piece
      ∧                     Logical And
          ⁰                 Literal integer `0`
             ι              Current piece
            Ｌ               Length
           ⊖                Decremented
         ⟦    ⟧             Make two-element list
        ⁺                   Vectorised plus
                    θ       Input string
                   ⪪ 0      Split on literal string `0`
                  …         Truncated to length
                      κ     Current index
                 ⪫     ω    Joined
                Ｌ           Length
               ⁺            Plus
                        κ   Current index
 Φ                          Filtered where
                         ι  Current piece
Ｉ                           Cast to string
                            Implicitly print

```

# Answer
> 0 votes
# Desmos, 68 bytes

```
L=join(0,l,0)
g(k)=[0...L.length][L[2...]=L+2k-1]+k
f(l)=(g(1),g(0))

```

The function \\$f\\$ returns a list of 1-indexed coordinate pairs. Seems golfable.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 0 votes
# C (clang), 83 bytes

```
c;i;f(*l,n){for(c=i=0;i<=n;++i)l[n-1]*i/n||i-n&&l[i]-c?printf("%d ",i-c,c=l[i]):0;}

```

Try it online!

Inputs a pointer to an array of \\$1\\$s and \\$0\\$s and its length (because pointers in C carry no length info).
Outputs the starting and ending indices of all the runs of consecutive \\$1\\$s to `stdout`.

# Answer
> 0 votes
# , 21 bytes

```
[:]`<:/.@I.2~:/\0,,&0

```

Try it online!

Returns a column vector.

* `0,,&0` Bookend the input with zeros.
* `2~:/` For every consecutive pair, are they unequal?
* `[: ... I.` Get the indexes of the ones, that is, the indexes where we transition from a 0 to a 1 or vice-versa. We are almost done now, but our ending indexes are one too high...
* `]`<:/.` So we alternately transform each element by the identity `]` and decrement `<:` functions.

The TIO link has a handful of alternate approaches, but this was the shortest I found.

# Answer
> 0 votes
# Retina, 25 bytes

```
L$`(?<!1)1*(?=1)
$.` $.>`

```

Try it online! Link includes test cases. Explanation: Retina can compute the character index of the start of the match, and Retina 1 can also compute the character index of the end of the match, but unfortunately the question requires inclusive ranges so rather than simply matching `1+` a more complicated regex is required.

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


title: Parity of a Permutation

text:
# Question
Title: Parity of a Permutation
# Background

The *parity of a permutation*, as defined by wikipedia, is as follows:

> The sign or signature of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd.
>
> The sign of a permutation can be explicitly expressed as
>
> sgn(σ) = (−1)^N(σ)
>
> where N(σ) is the number of inversions in σ.
>
> Alternatively, the sign of a permutation σ can be defined from its decomposition into the product of transpositions as
>
> sgn(σ) = (−1)^m
>
> where m is the number of transpositions in the decomposition.

For those of you who are not fond of Greek alphabet soup in their math, I'll try and simplify the definition a bit with an example (also stolen from wikipedia).

### Example

Consider the input array `{1, 2, 3, 4, 5}`, and a permutation of it, let's say, `{3, 4, 5, 2, 1}`. In order to get from the original array to its permutation, you must swap indices `0` and `2`, `1` and `3`, then `2` and `4`. Although this is not a unique solution, the parity is well-defined so this works for all cases.

Since it requires 3 swaps, we label this permutation with an `odd` parity. As you might expect, a permutation that requires an even amount of swaps is said to have an `even` parity.

# Challenge

Your challenge is to write a program in as few bytes as possible to determine the parity of a permutation. Your program or function must:

* Accept as arguments, two input arrays (or strings) representing a set before and after a permutation.
* Return or print the character `e` for even or `o` for odd, given the permutation.
* Should assume that all indices in the arrays or strings have unique values.

### Test Cases

Assuming you declared a function named `f`:

```
f([10], [10]) == "e"
f([10, 30, 20], [30, 20, 10]) == "e"
f([10, 30, 20, 40], [30, 20, 40, 10]) == "o"

```

This is , the shortest program in bytes wins!

# Answer
> 7 votes
# Jelly, ~~13~~ 12 bytes

```
żṗ2</€⁺Sị“oe

```

Try it online!

### How it works

```
żṗ2</€⁺Sị“oe  Main link. Arguments: A, B (lists)

ż             Zip A with B. Yields an array of pairs [x, σ(x)].
 ṗ2           Generate all pairs [[x, σ(x)], [y, σ(y)]].
   </€        Reduce each pair by </€.
              This maps [[x, σ(x)], [y, σ(y)]] to [x < y, σ(x) < σ(y)].
      ⁺       Repeat the previous link, i.e., execute </€ once more.
              This maps [x < y, σ(x) < σ(y)] to ((x < y) < (σ(x) < σ(y))), which is
              true if and only if x > y and σ(x) < σ(y).
       S      Sum. This counts the number of inversions.
        ị“oe  Retrieve the letter at the corresponding index.
              Indexing is 1-based and modular, so an odd sum retrieves the first
              letter, an even sum the second.

```

# Answer
> 6 votes
# MATL, ~~17~~ 16 bytes

*1 byte removed thanks to a suggestion by Dennis*

```
2$St!<Rz2\'oe'w)

```

This works in current version (15.0.0) of the language.

**Try it online**!

### Explanation

This uses the definition of parity in terms of inversions. An inversion is a pair of elements in the second array that are in the "wrong" order compared with the first array. Since the first array need not be sorted, we first sort it and the same rearrangement needed for that sorting is applied to the second array. Then an inversion corresponds to a pair of elements that is not increasing in the second array.

Note also that the two input arrays can be swapped and the result is the same. So it's not important which array is considered to be the "original" and which the "permuted".

```
2$S     % implicitly take two row vectors. Sort second and apply the indices
        % of that sorting to the first
t!      % duplicate. Transpose into column vector
<       % true for elements of the column vector that exceed those of the
        % row vector. Gives a 2D array with all pairs of comparisons
R       % keep only upper triangular part of that array
z       % number of nonzero elements. This is the number of inversions
2\      % parity of that number: gives 0 or 1
'oe'w   % push string 'eo' below the top of the stack
)       % apply index to produce 'e' or 'o'. An index 1 refers to the first
        % element, whereas 0 refers to the last. Implicitly display

```

# Answer
> 5 votes
## Haskell, 58 bytes

```
k%l|m<-zip k l=cycle"eo"!!sum[1|(a,b)<-m,(c,d)<-m,a<c,b>d]

```

Usage:

```
*Main> [8,3,5]%[5,3,8]
'o'

```

Same method as my Python answer. proud haskeller saved a byte with `cycle`.

Alternative from Wheat Wizard for 58 bytes (56 by modern convention of removing `f=`):

```
g m=cycle"eo"!!sum[0|(a,b)<-m,(c,d)<-m,a<c,b>d]
f=(g.).zip

```

# Answer
> 5 votes
# Octave, ~~56~~ 52 bytes

It seems nobody is using this approach so far: Basically I'm just using the determinants of the corresponding permutation matrices. The expression `det(eye(nnz(a))(a,:))` returns the determinant of the permutation matrix defined by the vector `a`. Then it is just a matter of extracting the right character from the string, depending on the result.

```
p=@(v)eye(nnz(v))(v,:);@(a,b)'ole'(det(p(a)*p(b))+2)

```

# Answer
> 4 votes
## Python 2, 68 bytes

```
lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]

```

Usage:

```
>>> f=lambda*M:"eo"[sum(a<b<M>A>B for a,A in zip(*M)for b,B in zip(*M))%2]
>>> f([8,3,5],[5,3,8])
'o'

```

Counts the number of inversion pairs of two zipped lists, i,e. values `(a,A)` and `(b,B)` from each list at the same index with `a<b` and `A>B`. These comparisons are combines as `a<b<M>A>B`, using the property that the list `M` is greater than any number. The sum is then taken modulo 2 and turned into `e` or `o`.

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

```
(a,b)=>"eo"[r=0,g=a=>a.map((e,i)=>a.slice(i).map(d=>r^=d<e)),g(a),g(b),r]

```

Since we're only interested in the parity, any duplicate transpositions simply cancel out. Conveniently JavaScript's array subscripts are not multidimensional.

# Answer
> 2 votes
# Mathematica, 77 bytes

```
If[Mod[Plus@@Length/@(Join[{0},#]&)/@PermutationCycles[#][[1]],2]==0,"e","o"]&

```

I agree!

# Answer
> 2 votes
# Mathematica, 31 bytes

```
If[Tr[Signature/@{##}]==0,o,e]&

```

> Signature\[list\] gives the signature of the permutation needed to place the elements of list in canonical order

We can reorder one list to the other, by first reordering one list to any order (in this case the canonical order) and reorder this list to the final list. The sign of the overall permutation is even, iff the signs of the two sub-permutations are equal.

# Answer
> 0 votes
# 05AB1E, 13 bytes

```
øDδ›Æ0›˜O„eoè

```

Try it online or verify all test cases.

Or alternatively:

```
øãε`›`›}O„eoè

```

Try it online or verify all test cases.

Both ports of *@Dennis*' Jelly answer, so make sure to upvote him as well!

**Explanation:**

```
ø             # Zip to pair the values in the two (implicit) input-lists together
 D            # Duplicate this list of pairs
  δ           # Apply double-vectorized with the two lists:
   ›          #  > check
              #   (e.g. [a,b] and [c,d] → [a>c,b>d]
    Æ         # Reduce each inner-most pair by subtracting: [a>c,b>d] → (a>c)-(b>d)
     0›       # Check if it's positive: (a>c)-(b>d)>0
       O      # Sum these checks together
           è  # Modular 0-based index it into
        „eo   # string "eo"
              # (which is output implicitly as result)

ø             # Same as above
 ã            # Cartesian product with itself to create pairs of pairs
  ε           # Map over each pair of pairs:
   `          #  Pop and push both pairs to the stack
    ›         #  [a,b] and [c,d] → [a>c,b>d]
     `        #  Pop these values to the check again
      ›       #  (a>c) and (b>d) → (a>c)>(b>d)
  }           # Close the map
   O„eoè      # Same as above, including implicit output

```

Minor note: Jelly uses 1-based indexing and 05AB1E uses 0-based, which is why his string is `"oe"` and mine is `"eo"`.

---
Tags: code-golf, decision-problem, permutations
---


# Question
Title: Swap every two elements in the list every possible way
Inspired by this question.

## Challenge

Let `L` be a list of `n` distinct elements. Let `P` be the set of all (unordered) pairs of positions in P. Let `R` be a result of applying a pair-swap operation on `L` by every pair in `P` in any order.

Example:
`L = [1, 7, 8]`
`P = {(1, 2), (0, 1), (0, 2)}`
`L = [1, 7, 8] -> [1, 8, 7] -> [8, 1, 7] -> [7, 1, 8] = R`

Your task is to output every possible `R` (without multiplicity) in any order.

## Constraints

* `L` can have any length, including 0 and 1
* All elements of `L` are guaranteed to be distinct

## Examples

1. Input: `[1, 5]`
Output: `[5, 1]`
2. Input: `[0, 1, 2, 3]`
Output:
`[3, 2, 1, 0]`
`[1, 0, 3, 2]`
`[2, 3, 0, 1]`
`[3, 0, 2, 1]`
`[1, 2, 0, 3]`
`[1, 3, 2, 0]`
`[2, 0, 1, 3]`
`[2, 1, 3, 0]`
`[0, 2, 3, 1]`
`[3, 1, 0, 2]`
`[0, 3, 1, 2]`
`[0, 1, 2, 3]`
3. Input: `[150]`
Output: `[150]`

## Rules

# Answer
# Factor \+ `koszul math.combinatorics`, ~~60~~ ~~52~~ 65 bytes

```
[ natural-sort [ reverse inversions even? ] filter-permutations ]

```

Try it online!

Uses the following observation by @xnor: "Alternatively, these are all even-signed permutations of the reverse of the list." (Although I found it actually seems to be the reverse of each permutation of the list, not the reverse of the list.)
> 6 votes

# Answer
# Jelly, 13 bytes

```
ŒcżU$Œ!y@ƒ€⁸Q

```

**Try it online!**

### How?

Since the elements are guaranteed to be distinct we can swap pairs of elements rather than elements at pairs of indices and otherwise follow the description in the question.

```
ŒcżU$Œ!y@ƒ€⁸Q - Link: list of distinct integers, L
                                e.g. [1,7,8]
Œc            - pairs           [[1,7],[1,8],[7,8]]
    $         - last two links as a monad:
   U          -   upend         [[7,1],[8,1],[8,7]]
  ż           -   zip           [[[1,7],[7,1]],[[1,8],[8,1]],[[7,8],[8,7]]]
     Œ!       - all permutations
          €   - for each:
         ƒ ⁸  -   reduce by, starting with L:
        @     -     with swapped arguments:
       y      -       translate
            Q - deduplicate

```
> 6 votes

# Answer
# 05AB1E, ~~17~~ 13 bytes

```
œʒRøãε`›`›}OÈ

```

-4 bytes thanks to *@chunes*' corrected version of *@xnor*'s insight: "*These are all even-signed reversed permutations of the list.*"

Try it online or verify all test cases.

**Explanation:**

`øãε`›`›}O` is taken from my 05AB1E answer in the related "*Parity of a Permutation*" challenge (which could alternatively be `øDδ›Æ0›˜O` for the same byte-count).

```
œ           # Get all permutations of the (implicit) input-list
 ʒ          # Filter it by:
  R         #  Reverse the current permutation
   ø        #  Create pairs with the (implicit) input-list
    ã       #  Cartesian product of itself to get a list of all pairs of pairs
     ε      #  Map each pair of pairs to:
      `     #   Pop and push the pairs separately to the stack
       ›    #   Vectorized larger than check: [a,b] and [c,d] → [a>c,b>d]
        `   #   Pop and push the pairs separated to the stack again
         ›  #   Larger than check again: a>c and b>d → (a>c)>(b>d)
     }O     #  After the map: sum to get get the amount of truthy values
       È    #  Check if this sum is even
            # (after which the filtered list is output implicitly)

```
> 3 votes

# Answer
# Vyxal, 13 bytes

```
2ḋṖƛ?$(nnṘĿ;U

```

Try it Online!

Port of Jonathan Allan's new Jelly answer.
> 3 votes

# Answer
# JavaScript (V8), 76 bytes

This is based on xnor's insight.

```
f=(a,k,...p)=>a.map((v,i)=>f(a.filter(_=>i--),i-~k,...p,v))+a||k&1||print(p)

```

Try it online!
> 2 votes

# Answer
# Python, ~~124~~ 121 bytes

```
def p(a,k=0,t=0):
 if a[(i:=k):]:
  while a[i:]:c=[*a];c[k],c[i]=c[i],c[k];p(c,k+1,t+(i>k));i+=1
 elif~t%2:print(a[::-1])

```

Attempt This Online!
> 0 votes

# Answer
# Charcoal, ~~86~~ 36 bytes

```
⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻⎇﹪λ²⮌θθκ⁺κ⟦μ⟧υＥΦυ¬﹪κ²⭆¹ι

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻⎇﹪λ²⮌θθκ⁺κ⟦μ⟧υ

```

Generate all the permutations of the input, alternating between even and odd permutations. This is based on my answer to Hankel transform of an integer sequence but operates directly on the input instead of a range. This works because the elements in the input are guaranteed to be unique.

```
ＥΦυ¬﹪κ²⭆¹ι

```

Pretty-print only the even permutations.
> 0 votes

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