title: Detect Perfect Pairings

text:
# Question
Title: Detect Perfect Pairings
Let's have a function \\$f\\$ that takes a string and removes all pairs of adjacent identical characters. For example

\\$f(a\color{red}{bb}ba\color{red}{cc}) = aba\\$

Note that when two pairs overlap we only remove one of them.

We will call a string perfectly paired if repeated application eventually yields the empty string. For example the string above \\$abbbacc\\$ is not perfectly paired because if we apply \\$f\\$ again we still get \\$aba\\$. However a string like \\$eabbccadde\\$ is perfectly paired because if we apply \\$f\\$ three times we get the empty string

\\$f(ea\color{red}{bbcc}a\color{red}{dd}e) = eaae\\$

\\$f(e\color{red}{aa}e) = ee\\$

\\$f(\color{red}{ee}) =\\$

---

Your task is to write perfectly paired computer code that takes a string (of printable ASCII) and decides if it is perfectly paired. **The bytestring of your source must be itself a perfectly paired string**, although your code doesn't necessarily have to be restricted to printable ASCII.

You may output two distinct values: one for the case where the input is perfectly paired, and another one for cases where it isn't.

This is a question so answers will be scored by the size in bytes of their source with fewer bytes being better.

---

## Test Cases

\\$abbbacc \rightarrow \mathrm{False}\\ abcba \rightarrow \mathrm{False}\\ abab \rightarrow \mathrm{False}\\ abbbaabacc \rightarrow \mathrm{True}\\ eabbccadde \rightarrow \mathrm{True}\\ bbbb \rightarrow \mathrm{True}\\$

# Answer
## Haskell, ~~146~~ 124 bytes

```
((""##))
a===bb=bb==a
((aa:bb))##((cc:dd))|aa===cc=bb##dd|1==1=((cc:aa:bb))##dd
a##""=""===a
""##cc=((cc!!00:cc!!00:""))##cc

```

No comments. Returns either `True` or `False`.

Try it online!

Edit: -22 bytes thanks to @Cat Wizard
> 10 votes

# Answer
# Python 2, 94 bytes

```
ss=''

for cc in input():ss=[cc+ss,ss[1:]][cc==ss[:1]]

print''==ss##tnirp[,+[=:)(tupni nirof=

```

Try it online!

The whole update step `ss=[cc+ss,ss[1:]][cc==ss[:1]]` cancels to just `=[+,[`.
> 6 votes

# Answer
# 05AB1E, ~~26 24 22 20~~ 18 bytes

-2 bytes thanks to ovs. Outputs **0** if the string is perfectly paired, **1** otherwise.

```
ΔγʒgÉ}JJ}ĀqqĀÉgʒγΔ

```

Try it online!

```
ΔγʒgÉ}JJ}ĀqqĀÉgʒγΔ – Full program.
Δ       }          – Until the result no longer changes:
 γʒ  }               – Split the string into chunks of equal characters and filter by:
   gÉ                – Is the length odd?
      JJ           – And after filtering, join the parts back together, but do this
                     twice to save 2 bytes, as in the previous versions.
         Ā         – Check whether the result is empty
          q        – Terminate (quit) execution. The rest of the code is ignored.
           qĀÉgʒγΔ – Mirror the non-matched part to help with the source layout.

```

---

### Previous versions

This one purely relies on undefined behaviour (so there's no "dead code"), and outputs **\[\['0'\]\]** for perfectly paired strings and **\[\['1'\]\]** for non-perfectly matched strings:

```
ΔγεDgÉ£}JJ}ĀĀ£ÉgDεγΔ

```

And the 22-byte version, explained, which is just the above but not abusing UB, and yielding *sane* values.

```
ΔγεDgÉ£}JJ}ĀqqĀ£ÉgDεγΔ – Full program.
Δ         }            – Until fixed point is reached (starting from the input value):
 γε    }                 – Group equal adjacent values, and for each chunk,
   DgÉ                     – Duplicate, get its length mod by 2.
      £                    – And get the first ^ characters of it. This yields the
                             first char of the chunk or "" respectively for odd-length
                             and even-length chunks respectively.
         JJ                – Join the result to a string, but do this twice to help
                             us with the source layout, saving 2 bytes.
            Ā           – Check if the result is an empty string.
             q          – Terminate the execution. Any other commands are ignored.
              qĀ£ÉgDεγΔ – Mirror the part of the program that isn't otherwise removed
                          anyways. This part forgoes }JJ} because that substring will
                          always be trimmed by the algorithm anyway.

```
> 5 votes

# Answer
# Cubix, 54 bytes

```
U#;!u1@.Oi>??>i..??O.@1^^...u--u.u!ww;..#..U..;..;!^^!

```

Outputs nothing if the string is perfectly paired and `1` otherwise.
Try it here

### Cubified

```
      U # ;
      ! u 1
      @ . O
i > ? ? > i . . ? ? O .
@ 1 ^ ^ . . . u - - u .
u ! w w ; . . # . . U .
      . ; .
      . ; !
      ^ ^ !

```

### Explanation

Most of the characters are filler needed to perfectly pair the code. Replacing those with `.` (no-op), we get

```
      U # ;
      ! u 1
      @ . O
i . ? . > i . . ? . . .
. . ^ . . . . u - . . .
. . . w ; . . . . . . .
      . ; .
      . ; !
      ^ ^ !

```

This can be broken into three steps:

* Check against the empty string (the left `i` and the `?`).
* Loop, throwing characters onto the stack and popping duplicates (everything on the bottom and right).
* Check if the stack is empty (the stuff at the top).
> 5 votes

# Answer
# , ~~20~~, 18 bytes

```
òóˆ±òø‚

::‚øò±ˆóò

```

Try it online!

Hexdump:

```
00000000: f2f3 88b1 f2f8 820a 0a3a 3a82 f8f2 b188  .........::.....
00000010: f3f2                                     ..                   ....

```

Outputs 0 for truthy, 1 for falsy. Thanks to nmjcman101 for indirectly saving 2 bytes.

```
ò        ò        " Recursively...
 ó                "   Remove...
  <0x88>          "     Any printable ASCII character
        ±         "     Followed by itself
          ø       " Count...
           <0x82> "   The number of non-empty strings

::<0x82>øò±<0x88>óò      " NOP to ensure that the code is paired

```
> 4 votes

# Answer
# , ~~142~~ 126 bytes

Tighter logic and some comment bytes golfed by @Giuseppe

```
f=function(x,p="(.)\\1")"if"(grepl(p,x),f(sub(p,"",x)),!nchar(x))##x(rahcn!,x,,p(bus(f,)x,p(lperg("fi")"1\\).("=p,x(noitcnuf=f

```

Try it online!

```
f=function(x,p="(.)\\1")"if"(nchar(x),"if"(grepl(p,x),f(sub(p,"",x)),0),1)##)1,)0,xp(bus(f,)x,p(lperg("fi",)x(rahcn("fi")"1).("=p,x(noitcnuf=f

```

Original:

Try it online!

Recursive detector function followed by comment with all the characters in the function in reverse order.
> 3 votes

# Answer
# sed 4.2.2, 34 bytes

```
:;:t;ss((..??\??))\1ss1;t;/..??/cc

```

Try it online!

Paired strings give empty output, unpaired ones give `ct:`

The trivial palindromic version is at 32 `:;ss(.)\1ss;t;/./cc/./;t;1\).(;:`. Old solution was `:;ss((..??\??))\1ss1;t;;/./cc/./t:` (changed because current one abused `c` less, edit: yay now there's only 1 character after `c` :D)

(note that `;` is the statement separator)

`:` declares an empty label

`:t` declares the label `t`

`ss((..??\??))\1ss1` is a substitution, in sed you can change the delimiter to a substitution, and this is what I did by changing it to `s`, so what this does is substitute the first (as is denoted by the `1` at the end)

* match of `((..??\??))\1`

+ `.` any character
    + `.??` followed by an optional optional character
    + `\??` and an optional `?`
    + followed by the same thing right beside it
* with nothing

Now this substitution is paired with itself, so the `;`s before and after it get cancelled out too

`t` and loop back to the label until there are no more successful substitutions

`/..?/` if `.` (wildcard) followed by `.?` an optional character is matched

* `cc` change the buffer to `c`
> 3 votes

# Answer
# Add++, 146 bytes

```
D,g,@~~,L2_|*;;*|_2L,@,g,D
D,ff,@^^,BG€gBF;;FBg€GB,@D1:?:

xx:?

aa:1
`bb
Bxx;;B
Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy

O;;O:,B,`,|,`,>$,`,*W`

```

Try it online!

Fun fact: This was 272 bytes long before the explanation was started, now it beats Java.

Outputs `True` for perfectly balanced strings, and `False` otherwise

To my great satisfaction, this beats the boring palindromize version by **2** bytes, to prevent the result being printed twice. I have also aimed to have as little dead code as possible, nevertheless there are still some commented-out sections, and the code exits with an error code of **1**, after printing the correct value.

*NB* : A bug with the `BF` commands was fixed while this answer was in development.

## How it works

The code starts by defining the two key functions, \\$\mathit{ff}\\$ and \\$g\\$. These two functions are used to calculate the next step in the process of removing pairs, and work entirely from \\$\mathit{ff}\\$ i.e. only \\$\mathit{ff}\\$ is called from the main program, never \\$g\\$. If we define the input string as \\$S\\$, \\$\mathit{ff}(S)\\$ modifies \\$S\\$ in the following way:

First, identical adjacent characters in \\$S\\$ are grouped together. For an example of \\$abbbaabacc\\$, this yields the array \\$\[\[a\], \[bbb\], \[aa\], \[b\], \[a\], \[cc\]\]\\$. Over each of the sublists (i.e. the identical groups), we run the function \\$g\\$, and replace the sublists with the result of the function.

\\$g\\$ starts by unpacking the group, splatting the characters onto the stack. It then pushes the number of characters on the stack and takes the absolute difference with \\$2\\$ and that number. We'll call this difference \\$x\\$. Lets see how this transforms the respective inputs of \\$\[a\]\\$, \\$\[bb\]\\$ and \\$\[ccc\]\\$:

$$\[a\] \Rightarrow \[a, 1\]$$ $$\[bb\] \Rightarrow \[b, b, 0\]$$ $$\[ccc\] \Rightarrow \[c, c, c, 1\]$$

As you can see \\$x\\$ indicates how many of the next character we wish to keep. For simple pairs, we remove them entirely (yielding **0** of the next character), for lone characters we leave them untouched, or yield **1** of them, and for groups where \\$x \> 2\\$, we want \\$x - 2\\$ of the character. In order to generate \\$x\\$ of the character, we repeat the character with `*`, and the function naturally returns the top element of the stack: the repeated string.

After \\$g(s)\\$ has been mapped over each group \\$s\\$, we splat the array to the stack to get each individual result with `BF`. Finally, the `^` flag at the function definition (`D,ff,@^^,`) tells the return function to concatenate the strings in the stack and return them as a single string. For pairs, which yielded the empty string from \\$g\\$, this essentially removes them, as the empty string concatenated with any string \\$r\\$ results in \\$r\\$. Anything after the two `;;` is a comment, and is thus ignored.

The first two lines define the two functions, \\$\mathit{ff}\\$ and \\$g\\$, but don't execute \\$\mathit{ff}\\$ just yet. We then take input and store it in the first of our 4 variables. Those variables are:

* \\$\mathit{xx}\\$ : The initial input and previous result of applying \\$\mathit{ff}\\$
* \\$\mathit{yy}\\$ : The current result of applying \\$\mathit{ff}\\$
* \\$\mathit{aa}\\$ : The loop condition
* \\$\mathit{bb}\\$ : Whether \\$\mathit{yy}\\$ is truthy

As you can see, all variables and functions (aside from \\$g\\$) have two letter names, which allows them to be removed from the source code fairly quickly, rather than having a comment with a significant amount of \\$\mathit{xyab}\\$. \\$g\\$ doesn't do this for one main reason:

If an operator, such as , is run over a user defined function \\$\mathit{abc}\\$, the function name needs to be enclosed in `{...}`, so that the entire name is taken by the operator. If however, the name is a single character, such as \\$g\\$, the `{...}` can be omitted. In this case, if the function name was \\$\mathit{gg}\\$, the code for \\$\mathit{ff}\\$ and \\$g\\$ would have to change to

```
D,gg,@~~,L2_|*;;*|_2L,@D             (NB: -2 bytes)
D,ff,@^^,BG€{gg}BF;;FB}gg{€GB,@D?:   (NB: +6 bytes)

```

which is 4 bytes longer.

An important term to introduce now is the *active* variable. All commands except assignment assign their new value to the active variable and if the active variable is being operated on, it can be omitted from function arguments. For example, if the active variable is \\$x = 5\\$, then we can set \\$x = 15\\$ by

```
x+10 ; Explicit argument
+10  ; Implicit argument, as x is active

```

The active variable is \\$x\\$ by default, but that can be changed with the ``` command. When changing the active variable, it is important to note that the new active variable doesn't have to exist beforehand, and is automatically assigned as 0.

So, after defining \\$\mathit{ff}\\$ and \\$g\\$, we assign the input to \\$\mathit{xx}\\$ with `xx:?`. We then need to manipulate our loop conditions ever so slightly. First, we want to make sure that we enter the while loop, unless \\$\mathit{xx}\\$ is empty. Therefore, we assign a truthy value to \\$\mathit{aa}\\$ with `aa:1`, the shortest such value being \\$1\\$. We then assign the truthiness of \\$\mathit{xx}\\$ to \\$\mathit{bb}\\$ with the two lines

```
`bb
Bxx

```

Which first makes \\$\mathit{bb}\\$ the active variable, then runs the boolean command on \\$\mathit{xx}\\$. The respective choices of \\$\mathit{aa} := 1\\$ and \\$\mathit{bb} := \neg \neg \mathit{xx}\\$ matter, as will be shown later on.

Then we enter our while loop:

```
Waa*bb,`yy,$ff>xx,`aa,xx|yy,`bb,Byy,xx:yy

```

A while loop is a *construct* in Add++: it operates directly on code, rather than variables. Constructs take a series of code statements, separated with `,` which they operate on. While and if statements also take a condition directly before the first `,` which consist of a single valid statement, such as an infix command with variables. One thing to note: the active variable cannot be omitted from the condition.

The while loop here consists of the condition `aa*bb`. This means to loop while both \\$\mathit{aa}\\$ and \\$\mathit{bb}\\$ are truthy. The body of the code first makes \\$\mathit{yy}\\$ the active variable, in order to store the result of \\$\mathit{ff}(x)\\$. This is done with

```
`yy,$ff>xx

```

We then activate our loop condition \\$\mathit{aa}\\$. We have two conditions for continued looping:

* 1) The new value doesn't equal the old value (loop while unique)
* 2) The new value isn't the empty string

One of Add++'s biggest drawbacks is the lack of compound statements, which necessitates having a second loop variable. We assign our two variables:

$$\mathit{aa} := \mathit{xx} \neq \mathit{yy}$$ $$\mathit{bb} := \neg \neg (\mathit{yy})$$

With the code

```
`aa,xx|yy,`bb,Byy

```

Where `|` is the inequality operator, and `B` converts to boolean. We then update the \\$\mathit{xx}\\$ variable to be the \\$\mathit{yy}\\$ variable with `xx:yy`, in preperation for the next loop.

This while loop eventually reduces the input into one of two states: the empty string or a constant string, even when applied to \\$\mathit{ff}\\$. When this happens, either \\$\mathit{aa}\\$ or \\$\mathit{bb}\\$ result in False, breaking out of the loop.

After the loop is broken, it can break for one of two reasons, as stated above. We then output the value of \\$\mathit{aa}\\$. If the loop was broken due to \\$\mathit{x} = \mathit{y}\\$, then both the output and \\$\mathit{aa}\\$ are False. If the loop was broken because \\$\mathit{yy}\\$ was equal to the empty string, then \\$\mathit{bb}\\$ is falsy and \\$\mathit{aa}\\$ and the output are truthy.

We then reach our final statement:

```
O

```

The program can now be in one of three states, in all of which the active variable is \\$\mathit{bb}\\$:

* 1) The input was empty. In this case, the loop didn't run, \\$\mathit{aa} = 1\\$ and \\$\mathit{bb} = \mathrm{False}\\$. The correct output is \\$\mathrm{False}\\$.
* 2) The input was perfectly balanced. If so, the loop ran, \\$\mathit{aa} = \mathrm{True}\\$ and \\$\mathit{bb} = \mathrm{False}\\$. The correct output is \\$\mathrm{False}\\$
* 3) The input was not perfectly balanced. If so, the loop ran, \\$\mathit{aa} = \mathrm{False}\\$ and \\$\mathit{bb} = \mathrm{True}\\$. The correct output is \\$\mathrm{True}\\$

As you can see, \\$\mathit{bb}\\$ is equal to the expected output (albeit reversed from the *logical* answer), so we simply output it. The final bytes that help us beat Java come from the fact that \\$\mathit{bb}\\$ is the active variable, so can be omitted from the argument, leaving us to output either \\$\mathrm{True}\\$ or \\$\mathrm{False}\\$, depending on whether the input is perfectly balanced or not.
> 3 votes

# Answer
# Japt, ~~24~~ 22 bytes

Outputs `false` for truthy and `true` for falsey.

```
&&!!e"(.)%1"PP"1%).("e

```

Try it
> 2 votes

# Answer
# Retina, ~~28~~ 26 bytes

```
+`(.)\1

C`^$

$^`C1\).(`+

```

Try it online!

Outputs ``C1\).(`+0`C1\).(`+` for falsy and ``C1\).(`+1`C1\).(`+` for truthy cases.
> 2 votes

# Answer
# APL (Dyalog), 38 bytes

```
''≡{'(.)\1'⎕R''⊢⍵}⍣≡⍝⍝≡⍣}⍵⊢R⎕'1\).('{≡

```

Try it online!
> 2 votes

# Answer
# Brain-Flak, ~~228~~ 200 bytes

```
(()){{{}([]<<{{(({}<<>>)<<>>[({})]){{{{}(<<<<>>()>>)((<<>>))}}}{}{}<<>>{}<<>>}}{}<<>>>>[[]])}}{}(<<({{(())(<<()>>)}}<<>>)>>){{{{}{}}((){{}{}{}{}{}}(()())())[[]((){{}{}}())[]]((){{}{}}[[][]]()){{}{}}}}

```

Try it online!

This is a bit of a proof of concept. It could probably be shorter. It doesn't use any comments however.

Outputs `0,0` if the input is perfectly paired and `0,1` if the input is not.
> 2 votes

# Answer
# Haskell, 66 bytes

```
null.foldr((%))"";;cc%((r:t))|cc==r=t;;t%s=t:s--s:t=s%=r|t:dlof.un

```

Try it online!

Cat Wizard saved 6 bytes.
> 2 votes

# Answer
# Brain-Flak, ~~112 110~~ 108 bytes

```
(()){{}({<<(({}<<>>)<<>>[({})]){{((<<>>)<<>>)}}{}{##{

}<<>>>>{}<<>>}<<>>)}{}((){{<<>>[[]]}})##}{}])}{([)}(}

```

Try it online!

This is based on my answer from *Are the brackets matched?*.

Tried not to use comments, but got stuck trying to make the pop nilads (`{}`) pair up. The problem lies in the easiest way to pair up a pair of brackets is to surround it in another pair of the same kind. While this is easy for other nilads, the `{...}` monad creates loops. In order to exit the loop you have to push a 0, but once you've exited the loop, you then have to pop the 0, which compounds the problem.

The 66 byte pre-paired solution is:

```
(()){{}({<(({}<>)<>[({})]){((<>)<>)}{}{}<>>{}<>}<>)}{}((){<>[[]]})

```

Try it online!

Outputs `1` or `1,0` if the input is a perfect pairing, `0,0` if not.

### No comment version, 156 bytes

```
(()){{{}({<<(({}<<>>)<<>>[({{}((<<[[]]>>)){}}{}(<<[]>>){{}{}}{})]){{((<<>>)<<>>)}}{{}{}{}}{}{}<<>>>>{}<<>>}<<>>)}}{{}{}}{}((){<<>>[[]]})(<<()()>>){{}{}{}}{}

```

Try it online!

As Cat Wizard pointed out, the first answer does not work for all interpreters, as not all handle `#` comments. This version contains no comments.
> 2 votes

# Answer
# Brain-Flak, 96 bytes

```
{<<>>(({})<<>>[(([{}<<>>]))]){((<<[[]]>>))}{}{}{}{}<<>>}<<>>{{{}{}{}{}{}}((<<>>){{}{}}){{{}}}}{}

```

Try it online!

Outputs nothing if the input is perfectly paired, and `0` otherwise.

Non-perfectly paired (original) version:

```
{<>(({})<>[({}<>)]){((<()>))}{}{}{}<>}<>{((<>))}{}

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 76 bytes

Returns a boolean.

```
ff=ss=>ss==(ss=ss.replace(/(.)\1/,''))?!ss:ff(ss)//)(:!?,/1\).(/(ecalper.=(>

```

Try it online!

Suggested by @Shaggy: **58 bytes** by returning an empty string for *perfectly paired* or throwing an error otherwise.
> 1 votes

# Answer
# Wolfram Language (Mathematica), ~~70~~ 64 bytes

```
{#//.{aa___,bb__,bb_,cc___}:>{aa,cc}}=={{}}(**(,{>:}_,{.#{&)**)&

```

Try it online!

### Without comments, 92 bytes

```
((#//.bb_:>StringReplace[00[ecalpeRgnirtS>aa__:_.#&];bb,{{,}};00>00;00;aa:_~~aa_:>""]))==""&

```

Try it online!
> 1 votes

# Answer
# Haskell, 92 bytes

```
gg""

gg((aa:cc:bb))dd|aa==cc=gg bb dd

gg  aa""=""==aa

gg  aa((bb:c))=gg((bb:aa))c--c:=c:|

```

Try it online!

@nimi's answer is pretty cool, it doesn't use any comments. This one is shorter but does use a comment.

@xnor's answer is also pretty cool, it does use comments and is shorter than this one.
> 1 votes

# Answer
# Lua, 178 bytes

```
p=...S={}for a in p:gmatch"."do E=S[#S]~=a;S[E and#S+1 or#S]=E and a or X end;print(#S==0)--)0S#(tnirp;dne X ro a dna E=]S#ro 1+S#dna E[S;a=~]S#[S=E od"."hctamg:p ni a rof}{=S.=p

```

Try it online!

While it is a terribly long solution, this does make quite a bit of use of Lua-specific quirks. This is actually a minified brute force stack algorithm. The program is made complicated by the fact that Lua's patterns don't allow replacing pairs and regex is not built in.

Explanation:

```
p=... -- command-line argument
S={} -- the stack
for c in p:gmatch"." do -- shorter than "for i=1,#p do ..."
    E=S[#S]~=c -- check whether we have the right letter on top of stack
    -- could've saved some bytes by doing == instead of ~=
    -- but the double negation is necessary for ternary operator
    -- to work with nil values
    S[E and #S+1 or #S]=E and c or X -- Lua's awesome "ternary operator"
end
-- i'm sure there is a better way to output this (table indexing?)
print(#S==0)

```
> 1 votes

# Answer
# Gol\>\<\>, 30 bytes

```
1ll1**F:}}:{=Q{~~||lzBBzl{Q={F

```

Try it online!

Everything after the first `B` is excess code and is not executed. A function that returns the top of stack as `1` if the input is a perfect pairing, `0` otherwise.

### Explanation:

```
1       Push 1 as the end string marker
 ll1**  Push n, where n (len+1)*(len+2),
        This is larger than the amount of steps needed to determine pairing
      F           |  Repeat that many times
       :}}:{=        Compare the first two characters of the string
             Q   |   If they are equal
              {~~    Pop both of them
        String is also rotated by 1
        If the string becomes empty, the 1 is compared to itself and removed.
                   lzB   Return whether the length of the stack is 0
                      Bzl{Q={F  Excess code to match unpaired symbols

```
> 1 votes

# Answer
# Cubix, 30 bytes

```
1O@;??;@ii??O;>>;;;..1Wcc1??1W

```

Try it online!

Outputs `1` if the string is perfectly paired and nothing otherwise.

### Cubified

```
      1 O @
      ; ? ?
      ; @ i
i ? ? O ; > > ; ; ; . .
1 W c c 1 ? ? 1 W . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

```

### Simplified

```
      1 O @
      ; ? .
      . @ .
i ? . . . . > ; ; ; . .
. W c . . . ? 1 W . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

```

The logic and general structure are the same as in Mnemonic's answer, but without an explicit check for the empty string.
> 1 votes

# Answer
# Jelly, ~~26 24~~ 22 bytes

```
ẠƬµF€ḂLḣgŒŒgḣLḂ$$€FµƬẠ

```

Try it online!

Weirdly seems to work without moving the backwards code to an unused link.

Returns **0** if the input is perfectly paired, **1** otherwise.

Active code:

```
ŒgḣLḂ$$€FµƬẠ
Œg            Group runs 'abbbcc'->['a','bbb','cc']
       €      For each of these strings:
      $       Monad{
     $            Monad{
   L                  Find the length...
    Ḃ                 ...mod 2.
                      } -> [1, 1, 0] in this example.
  ḣ               Take this many characters from the string.
                  } -> [['a'], ['b'], []]
        F     Flatten -> ['a', 'b']
          Ƭ   Repeat...
         µ    The last monadic chain until a fixed point is reached.
           Ạ  All. If it is not a perfectly paired string, all elements in the
              result of Ƭ will be nonempty and 1 is returned.
              If it is perfectly paired, the last element is [] which is falsy
              and 0 is returned.

```
> 0 votes

# Answer
# Python 2, 114 bytes

```
import re

e=lambda i,nn=1:e(*re.subn('(.)\\1','',i))if nn else''==i##ieslef'1).('(nbus.er*(e:1=,i adbmal=r tropmi

```

Try it online!

Returns `True` for perfectly-paired strings, `False` otherwise.

(Actually fails to verify itself, because `(.)` won't match the newlines in the code! But @Cat Wizard said this is okay, because newlines aren't printable ASCII characters, so my program needn't handle them.)

---

This is a perfectly-paired version of:

```
import re;p=lambda s,n=1:p(*re.subn('(.)\\1','',s))if n else''==i

```

for which a “lazier” perfectization of `code + '##' + f(code[::-1])` would give 120 bytes. (That is, renaming the variables etc. to introduce more collapsed pairs inside the *comment* half of the code saved 6 bytes.)

---

> `re.subn` is a little-known variant of `re.sub` that returns a tuple `(new_string, number_of_substitutions_made)`. It's pretty good for finding regex substitution fixpoints!
> 0 votes

# Answer
# Attache, 82 bytes

```
{0=#Fixpoint[{Replace[_,/"(.)\\1",""]},_]}??}]_,}],"1).("/,_[ecalpeR{[tniopxiF#=0{

```

Try it online!

Nothing incredible here. `Fixpoint`s a function which removes consecutive pairs.
> 0 votes

# Answer
# Java 8, ~~158~~ ~~156~~ 154 bytes

```
n->{for(;n.matches(".*(.)\\1.*");n=n.replaceAll("(.)\\1",""));return  n.isEmpty();}//};)(ytpmEsi.ruter;,"1).("(Aecalper.n=n;)"*.1).(*."(sehctam.n;(rof{>-n

```

Returns a boolean (`true`/`false`).

-2 bytes thanks to *@raznagul*.

Try it online.

**Explanation:**

```
n->{                              // Method with String parameter and boolean return-type
  for(;n.matches(".*(.)\\1.*");   //  Loop as long as the String still contains pairs
    n=n.replaceAll("(.)\\1","")); //   Remove all pairs
  return  n.isEmpty();}           //  Return whether the String is empty now
//};)(ytpmEsi.ruter;,"1).("(Aecalper.n=n;)"*.1).(*."(sehctam.n;(rof{>-n
                                  // Comment reversed of the source code,
                                  // minus the pairs: '\\';'ll';'\\';'""))';'n  n';'//'

```
> 0 votes

---
Tags: code-golf, string, restricted-source, source-layout, balanced-string
---


title: The Jumping Up Sequence

text:
# Question
Title: The Jumping Up Sequence
Consider the following sequence:

```
0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...

```

Looks pretty pattern-less, right? Here's how it works. Starting with `0`, jump up `n` integers, with `n` starting at `1`. That's the next number in the sequence. Then, append any numbers "skipped" and that haven't been seen yet in ascending order. Then, increment `n` and jump from the last number appended. Repeat this pattern.

So, for example, when we reach `11`, we're at `n=5`. We increment `n` to be `n=6`, jump up to `17`, then append `13 14 15 16` since those haven't been seen yet. Our next jump is `n=7`, so the next element in the sequence is `23`.

### The Challenge

Given input `x`, output the `x`th term of this sequence, the first `x` terms of the sequence, or build an infinite list of the terms of the sequence. You can choose 0- or 1-indexing.

## I/O and Rules

* The input and output can be given by any convenient method.
* The input and output can be assumed to fit in your language's native number type.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# JavaScript (ES7), 41 bytes

Returns the **n-th** term of the sequence, 0-indexed.

```
n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2

```

Try it online!

## How?

### Main case: \\$n \> 3\\$

The first four terms of the sequence are special, so let's put them aside for now.

For \\$n \> 3\\$, the sequence looks like that:

```
 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...

```

We can notice that there are in fact two interleaved sub-sequences:

* Most values belong to the sub-sequence \\$A\\$ for which we simply have:

$$A(n) = n - 1$$
* Some other values belong to the sub-sequence \\$B\\$ (highlighted with brackets in the above diagram) whose indices follow the arithmetic sequence **3, 3, 4, 6, 9, 13, 18, 24** ... and for which we have:

$$B(n,k) = n + k - 1$$

where \\$n\\$ is the index in the main sequence and \\$k\\$ is the index in the sub-sequence \\$B\\$.

The indices of \\$B\\$ in the main sequence are given by:

$$n\_k = \frac{k^2 - k + 6}{2}$$

Given \\$n\\$, we know that the corresponding term in the main sequence belongs to \\$B\\$ if \\$n\\$ is an integer solution of the quadratic equation:

$$x^2 - x + 6 - 2n = 0$$

whose discriminant is:

$$\Delta = 1 - 4(6 - 2n) = 8n - 23$$

and whose positive solution is:

$$x = \frac{1 + \sqrt{\Delta}}{2}$$

We expect \\$\sqrt{\Delta}\\$ to be an integer. Hence the test:

```
(d = (n-- * 8 - 23) ** .5) % 1

```

### Special cases: \\$0 \le n \le 3\\$

For \\$n \< 3\\$, the discriminant is negative and taking its square root results in **NaN**. For \\$n = 3\\$, the discriminant is \\$1\\$. Therefore, these first four terms of the sequence are considered to belong to the sub-sequence \\$B\\$.

Should we just apply our standard formula **n - ~d / 2**, we'd get:

$$-\frac 1 2, \frac 1 2, \frac 3 2, 3$$

instead of:

$$0, 1, 3, 2$$

Which is why we XOR these results with \\$0,1,2\text{ and }1\\$ respectively.
> 25 votes

# Answer
# Husk, 12 bytes

```
Θṁṙ_1C+ḣ2tNN

```

Try it online!

Outputs as an infinite list. Here is a version that prints the first **N**.

### Explanation

```
Θṁṙ_1C+ḣ2tNN – Full program. Takes no input, outputs to STDOUT.
         tN  – Construct the infinite list of natural numbers, starting from 2.
      +ḣ2    – And append [1, 2] to it. Yields [1,2,2,3,4,5,6,7,8,9,10,11,...].
     C     N – Cut the infinite list of positive integers into pieces of those
               sizes. Yields [[1],[2,3],[4,5],[6,7,8],[9,10,11,12],...].
 ṁ           – Map and flatten the results thereafter.
  ṙ_1        – Rotate each to the right by 1 unit.
               Yields [1,3,2,5,4,8,6,7,12,9,10,11,...]
Θ            – Prepend a 0. Yields [0,1,3,2,5,4,8,6,7,12,9,10,11,...]

```
> 11 votes

# Answer
# Haskell, 43 bytes

```
0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

```

Try it online!

Defines an infinite list:

```
  0:1:3:2:(5!3)
≡ 0:1:3:2:5:4:(8!4)
≡ 0:1:3:2:5:4:8:6:7:(12!5)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) …

```
> 7 votes

# Answer
# Jelly, 15 bytes

```
+‘ɼṪRṙ-œ|@
0Ç¡ḣ

```

This is a full program that, given **n**, prints the first **n** items of the sequence.

Try it online!

### How it works

```
0Ç¡ḣ        Main link. Argument: n

0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.

+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)

 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.

```
> 4 votes

# Answer
## C (gcc), ~~73~~ ~~67~~ 64 bytes

```
t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}

```

Try it online!

Defines a function `f` that takes 0-indexed `n` and produces the `n`th number in the sequence.

We can analyze the sequence as follows:

```
f(n)  = n   where n = 0, 1

f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2

f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...

f(n)  = n-1 // for all cases not yet covered

```

First we handle the middle section:

```
for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);

```

Note that the arguments on the left (4, 6, 9, 13, ...) follow a pattern: first add two, then add three, then add four, and so on. We start at `t=4` and add `d` (which starts at 2) each iteration of the loop, incrementing `d` in the process.

The body of the loop is more interesting. Remember that we want to map 4 to 5, 6 to 8, 9 to 12, etc.; that's just adding `d-1` if `x` is `t`. However, this logic comes before the last case, `f(n) = n - 1`, so we know we're going to subtract 1 at the end. Therefore, we can simply add `d` if `x == t` (`x-t||(x+=d)`). However, we will also need to break out of the loop immediately after this -- so we add *that* to `d` to get the absurd-looking `d+=x+=d`, which will always make the `d<x` condition fail.

This covers everything except for the first four values. Looking at them in binary, we get:

```
00 -> 00
01 -> 01
10 -> 11
11 -> 10

```

So, we want to flip the last bit if `2 <= x < 4`. This is accomplished with `x^x/2`. `x/2` gives the second least significant bit, so XORing this with the original number flips the last bit if the number is 2 or 3.
> 3 votes

# Answer
# Jelly,  ~~13~~  10 bytes

-3 Thanks to Dennis (use 0-indexing to save 2 from cumulative sum setup and a final decrement)

```
Ḷ»2Äi+_>2$

```

A monadic link accepting an integer, **0**-indexed **n**, which returns an integer, **a(n)**

**Try it online!** Or see a test-suite
> 3 votes

# Answer
# MATL, 22 bytes

```
1y:"t0)@+h5M:yX-h]qw:)

```

Outputs the first `n` terms of the sequence.

Try it online!

### Explanation

```
1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display

```
> 2 votes

# Answer
## Perl 5 with `-pl`, 70 bytes

```
$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]

```

Try it online!
> 2 votes

# Answer
# Haskell, 51 bytes

```
0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]

```

Try it online!

Quite a bit longer than Lynn's Haskell answer, but the different approach might be interesting non the less.
> 2 votes

# Answer
# Ruby, 73 bytes

```
f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}

```

Try it online!

Recursive function that returns the first x numbers of the list.
> 1 votes

# Answer
# QBasic, 58 bytes

```
DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP

```

Outputs indefinitely. You may want to add a `SLEEP 1` inside the loop or make it `LOOP WHILE b<100` or something like that in order to see the results.

This basically just implements the spec. Observe that the numbers we go back for will always be the numbers between the most recently jumped-to number and the jumped-to number prior to that. So we store these bounds as `a` and `b` and use a `FOR` loop to print all the numbers between them.
> 1 votes

# Answer
# 05AB1E, 14 bytes

```
0)sƒ¤N+LÁ«}Ùs£

```

Try it online!
> 1 votes

# Answer
# , 70 bytes

```
function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}

```

Try it online!

* 1-indexed
* -4 bytes using `F` constant thanks to @JAD suggestion
* -5 bytes reversing the list thanks to @Giuseppe suggestion
* -2 bytes removing useless braces in for loop thanks to @JAD suggestion
* -2 bytes using `setdiff` instead of `x[x %in% y]`

---

Previous version (79 bytes)
> 1 votes

# Answer
# Python 2, 123 bytes

```
def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s

```

Try it online!

Given input x, output the first x terms of the sequence,

I'm learning Python and this challenges make things more interesting.

Edit: shave some whitespace
> 1 votes

# Answer
# Jelly, 16 bytes

```
RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

```

Try it online!

One byte longer than the existing Jelly answer but this could possibly be golfed a little. `RÄṬŻk²Ḋ$` could maybe be shorter.

**18 bytes**

```
RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

```

Longer but different.
> 0 votes

# Answer
# Ruby, 63 bytes

```
->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}

```

Try it online!

0-indexed. Can probably be golfed down.
> 0 votes

# Answer
# Perl 6, 52 bytes

```
(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

```

Try it online!

This is a generator expression using the `...` operator. It looks for gaps in the prior sequence `@_` via `((^max @_)∖@_).min.?key`:

```
      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2

```

The `?` is necessary for the initial value which doesn't have a `.key`. If no gaps are found, then it adds n (here in the `$` variable) to the last value in the list, plus one for off by 0 errors.
> 0 votes

# Answer
# Python 3, 104 bytes

```
def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1

```

Try it online!

Given input x, output the first x "sequences"
> 0 votes

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


title: Interleaving Sequences

text:
# Question
Title: Interleaving Sequences
Interleaved sequences represent an arbitrary merging of some number of sequences.

An interleaved sequence can be made by appending elements to a list one by one from some number of lists, choosing the next element from some list each time. Therefore, an interleaved sequence will contain exactly the same elements of all the lists combined, in an order consistent with all lists.

The only interleaving of 1 list is that same list.

# Challenge

Your challenge is to create a function/program that takes an arbitrary number of sequences and outputs all possible interleavings of those sequences.

# Examples

```
Input: [1, 2], [3, 4]
Output:
    [1, 2, 3, 4]
    [1, 3, 2, 4]
    [1, 3, 4, 2]
    [3, 1, 2, 4]
    [3, 1, 4, 2]
    [3, 4, 1, 2]

Input: [1, 2, 3, 4, 5]
Output:
    [1, 2, 3, 4, 5]

Input: []
Output:
    []

Input: <nothing>
Output:
    []

(also acceptable)
Input: <nothing>
Output: <nothing>

Input: [1, 2, 3], [4, 5]
Output:
    [1, 2, 3, 4, 5]
    [1, 2, 4, 3, 5]
    [1, 2, 4, 5, 3]
    [1, 4, 2, 3, 5]
    [1, 4, 2, 5, 3]
    [1, 4, 5, 2, 3]
    [4, 1, 2, 3, 5]
    [4, 1, 2, 5, 3]
    [4, 1, 5, 2, 3]
    [4, 5, 1, 2, 3]

Input: [1, 2], [3, 4], [5, 6]
Output:
    [1, 2, 3, 4, 5, 6]
    [1, 2, 3, 5, 4, 6]
    [1, 2, 3, 5, 6, 4]
    [1, 2, 5, 3, 4, 6]
    [1, 2, 5, 3, 6, 4]
    [1, 2, 5, 6, 3, 4]
    [1, 3, 2, 4, 5, 6]
    [1, 3, 2, 5, 4, 6]
    [1, 3, 2, 5, 6, 4]
    [1, 3, 4, 2, 5, 6]
    [1, 3, 4, 5, 2, 6]
    [1, 3, 4, 5, 6, 2]
    [1, 3, 5, 2, 4, 6]
    [1, 3, 5, 2, 6, 4]
    [1, 3, 5, 4, 2, 6]
    [1, 3, 5, 4, 6, 2]
    [1, 3, 5, 6, 2, 4]
    [1, 3, 5, 6, 4, 2]
    [1, 5, 2, 3, 4, 6]
    [1, 5, 2, 3, 6, 4]
    [1, 5, 2, 6, 3, 4]
    [1, 5, 3, 2, 4, 6]
    [1, 5, 3, 2, 6, 4]
    [1, 5, 3, 4, 2, 6]
    [1, 5, 3, 4, 6, 2]
    [1, 5, 3, 6, 2, 4]
    [1, 5, 3, 6, 4, 2]
    [1, 5, 6, 2, 3, 4]
    [1, 5, 6, 3, 2, 4]
    [1, 5, 6, 3, 4, 2]
    [3, 1, 2, 4, 5, 6]
    [3, 1, 2, 5, 4, 6]
    [3, 1, 2, 5, 6, 4]
    [3, 1, 4, 2, 5, 6]
    [3, 1, 4, 5, 2, 6]
    [3, 1, 4, 5, 6, 2]
    [3, 1, 5, 2, 4, 6]
    [3, 1, 5, 2, 6, 4]
    [3, 1, 5, 4, 2, 6]
    [3, 1, 5, 4, 6, 2]
    [3, 1, 5, 6, 2, 4]
    [3, 1, 5, 6, 4, 2]
    [3, 4, 1, 2, 5, 6]
    [3, 4, 1, 5, 2, 6]
    [3, 4, 1, 5, 6, 2]
    [3, 4, 5, 1, 2, 6]
    [3, 4, 5, 1, 6, 2]
    [3, 4, 5, 6, 1, 2]
    [3, 5, 1, 2, 4, 6]
    [3, 5, 1, 2, 6, 4]
    [3, 5, 1, 4, 2, 6]
    [3, 5, 1, 4, 6, 2]
    [3, 5, 1, 6, 2, 4]
    [3, 5, 1, 6, 4, 2]
    [3, 5, 4, 1, 2, 6]
    [3, 5, 4, 1, 6, 2]
    [3, 5, 4, 6, 1, 2]
    [3, 5, 6, 1, 2, 4]
    [3, 5, 6, 1, 4, 2]
    [3, 5, 6, 4, 1, 2]
    [5, 1, 2, 3, 4, 6]
    [5, 1, 2, 3, 6, 4]
    [5, 1, 2, 6, 3, 4]
    [5, 1, 3, 2, 4, 6]
    [5, 1, 3, 2, 6, 4]
    [5, 1, 3, 4, 2, 6]
    [5, 1, 3, 4, 6, 2]
    [5, 1, 3, 6, 2, 4]
    [5, 1, 3, 6, 4, 2]
    [5, 1, 6, 2, 3, 4]
    [5, 1, 6, 3, 2, 4]
    [5, 1, 6, 3, 4, 2]
    [5, 3, 1, 2, 4, 6]
    [5, 3, 1, 2, 6, 4]
    [5, 3, 1, 4, 2, 6]
    [5, 3, 1, 4, 6, 2]
    [5, 3, 1, 6, 2, 4]
    [5, 3, 1, 6, 4, 2]
    [5, 3, 4, 1, 2, 6]
    [5, 3, 4, 1, 6, 2]
    [5, 3, 4, 6, 1, 2]
    [5, 3, 6, 1, 2, 4]
    [5, 3, 6, 1, 4, 2]
    [5, 3, 6, 4, 1, 2]
    [5, 6, 1, 2, 3, 4]
    [5, 6, 1, 3, 2, 4]
    [5, 6, 1, 3, 4, 2]
    [5, 6, 3, 1, 2, 4]
    [5, 6, 3, 1, 4, 2]
    [5, 6, 3, 4, 1, 2]

```

# Rules

* Standard loopholes forbidden (duh)
* Input may be taken in any reasonable format, e.g. a list of lists, vararg list of lists, parameter lists, etc... as long as it is unambiguous where lists begin and end.
* Output may be in any reasonable format, so long as it is clear where lists begin and end. Valid outputs include, but are not necessarily limited to:
    + stdout, with one list per line
    + A list of lists
    + An iterator over lists (can be implemented with a generator if your language has them)
* The order of the yielded interleavings does not matter, however, there should not be any repeated interleavings.
* To simplify repeat detection, you may assume that all elements across all input sequences are unique.
* If given no lists as input, both the empty list and no output are valid outputs.
* Types of the elements in the sequences is irrelevant. (e.g. they could all be one type or a mishmash of types, whichever is more convenient in your language)
* Your program/function must be guaranteed to terminate in a finite amount of time.
* This is , so the shortest code for each language wins.

# Answer
> 5 votes
# Haskell, ~~84~~ ~~77~~ 76 bytes

```
foldl((.(!)).(>>=))[[]]
a#b=(b:)<$>a
x@(a:c)!y@(b:d)=x!d#b++c!y#a
a!b=[a++b]

```

Thanks to @Lynn for 7 bytes and @user9549915 for a byte!

Try it online!

# Answer
> 5 votes
# Python 2, ~~103~~ ~~92~~ ~~79~~ 78 bytes

```
def f(A,c=[]):
 if not[f([b[b==x:]for b in A],c+x[:1])for x in A if x]:print c

```

Try it online!

Or:

# Python 3, 73 bytes

```
def f(A,c=[]):[f([b[b==x:]for b in A],c+x[:1])for x in A if x]or print(c)

```

Try it online!

-1 by replacing `[x[0]]` with `x[:1]` as per xnor

-13 bytes by ~~shamelessly stealing~~ expanding upon `[b[b==x:]for b in A]` as suggested by Neil's answer instead of longer `enumerate` approach.

Takes a list of lists `A` as input. If all elements of `A` are empty, then the list evaluated in the `if` will be empty, so we have reached the end of the recursion and can `print`. Otherwise, we have a list of one or more `None`'s; and we recurse.

# Answer
> 4 votes
# Jelly, 11 bytes

```
FŒ!fÐ€⁼ṛɗÐf

```

Try it online!

### How it works

```
FŒ!fÐ€⁼ṛɗÐf  Main link. Argument: A (array of arrays)

F            Flatten A.
 Œ!          Take all permutations.
        ɗÐf  Filter by the chain to the left, keeping only permutations for which
             it returns a truthy value.
   fÐ€         Intersect the permutation with each array in A.
      ⁼ṛ       Test if the result is equal to A.

```

# Answer
> 3 votes
# Ruby, 66 bytes

```
f=->a,*p{(a-=[[]])[0]?a.flat_map{|b|h,*t=b;f[a-[b]+[t],*p,h]}:[p]}

```

If there are no non-empty sequences, return an empty sequence. Otherwise, for each non-empty sequence, recurse with the first element removed then add it onto the beginning of each result. The implementation uses the assumption that elements are guaranteed to be globally unique, otherwise `a-[b]` could potentially remove more than 1 sequence from the recursive call. Although on reflection, maybe that'd actually be the right behavior to avoid duplicate output.

Example IO:

`f[[[1,2],[3,4]]]
=> [[1, 3, 2, 4], [1, 3, 4, 2], [1, 2, 3, 4], [3, 1, 4, 2], [3, 1, 2, 4], [3, 4, 1, 2]]`

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~76~~ ~~75~~ 71 bytes

```
Cases[Permutations[Join@@#],x_/;And@@OrderedQ/@(x~Position~#&/@#&/@#)]&
(* or *)
Cases[Join/*Permutations@@#,x_/;And@@(x~Position~#&/@#&/*OrderedQ/@#)]&

```

Try it online!

Naive approach: find all permutations that are interleavings of the input.

### Explanation

```
Permutations[Join@@#]

```

Flatten `<input>` and find all of its permutations.

```
Cases[ ... ,x_/; ...]

```

Find all elements `x` such that...

```
(x~Position~#&/@#&/@#)

```

Replace all of the items in depth-2 of `<input>` with their respective position in `x`.

```
And@@OrderedQ/@ ...

```

Check whether all depth-1 lists are ordered (i.e. in increasing order).

### Actual implementation of interleaving, 117 bytes

```
Cases[{}~(f=ReplaceList[#2,{{a___,{b_,c___},d___}/;b>0:>#~Join~{b}~f~{a,{c},d},_:>#}]&)~#,{___},{Tr[1^(Join@@#)]+1}]&

```

Try it online!

# Answer
> 2 votes
# Python 2, ~~87~~ 84 bytes

```
f=lambda a:any(a)and[b[:1]+c for b in a if b for c in f([c[c==b:]for c in a])]or[[]]

```

Try it online! Port of my JavaScript answer. Edit: Saved 3 bytes thanks to @ChasBrown.

# Answer
> 2 votes
# Haskell, 45 bytes

```
f l=max[[]][h:y|h:t<-l,y<-f$t:filter(/=h:t)l]

```

Try it online!

Adapted from Chas Brown's Python answer.

The `max[[]]` is a trick to give a base case of `[[]]` when the input only contains `[]` elements. In that case, the list used for empty, recursing is empty, and `max[[]][]` gives `[[]]`.

When recursing, rather than selectively dropping the first element of the chosen list `h:t`, we make a new list with `t` at the front and `h:t` filtered out.

# Answer
> 0 votes
## JavaScript (Firefox 30-57), 92 bytes

```
f=a=>a.some(b=>b+b)?[for(b of a)if(b+b)for(c of f(a.map(c=>c.slice(c==b))))[b[0],...c]]:[[]]

```

# Answer
> 0 votes
# Japt `-Q`, 14 bytes

```
c á f@e_XfZ eZ
c              // Flatten the input into a single array
  á            // and find all permutations.
    f          // Then filter the results for items
     @e_       // where for each original input
        XfZ eZ // the ordering of the items is unchanged.

```

Takes input as an array of arrays. `-Q` makes the output preserve the array notation.

Try it here.

# Answer
> 0 votes
**Scala:** (not intended to be minimal, more a clear reference resource)

```
object Interleave {

  private def interleavePair[A](x: Seq[A], y: Seq[A]): Seq[Seq[A]] =
    (x, y) match {
      case (a +: c, b +: d) =>
        interleavePair(x, d).map(b +: _) ++ interleavePair(c, y).map(a +: _)
      case _ => Seq(x ++ y)
    }

  def interleave[A](ssa: Seq[Seq[A]]): Seq[Seq[A]] =
    ssa.foldLeft[Seq[Seq[A]]](Seq(Seq.empty)) {
      case (sssat, sa) => sssat.flatMap(interleavePair(sa, _))
    }
}

object Main extends App {

  import Interleave._

  println(interleave(Seq()))
  println(interleave(Seq(Seq(1, 2), Seq(3, 4))))
}

```

Try it online!

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


title: Draw a distribution diagram!

text:
# Question
Title: Draw a distribution diagram!
## Challenge

You are given three integers as input - `min_value, max_value, sample_size`, that you can pass to your answer as either array or several parameters.

Your task is to **output a diagram in any convenient format**, that shows the frequency of numbers in the `(min_value, max_value)` range showing up when a random number in the `(min_value, max_value)` range is picked `sample_size` times. The random number sequence should be generated within your answer.

With large ranges and sample sizes, you're free to change the steps your diagram uses, as long as the representation remains accurate.

## Example

With `[1, 5, 10]` as input:

```
o o o x o
x o x x x
x x x x x
1 2 3 4 5

```

With `[1, 100, 15]` as input (in steps of 10, so 00 shows 1-9, 10 shows 10-19, etc.):

```
xx oo oo xx oo xx oo oo oo oo
xx oo oo xx oo xx xx oo oo oo
xx xx oo xx xx xx xx xx xx oo
00 10 20 30 40 50 60 70 80 90

```

## Scoring

This is , so shortest code in bytes wins.

# Answer
# Jelly, 13 bytes

```
Ṫɓr/;"xẊĠ>ʋ¥G

```

Uses a *very* convenient format:

* Prints the values on the left axis
* Uses `0` as the distribution pixels (like the `x`s) and `1` as the background pixels (like the `o`s)
* Uses as many horizontal spaces between "pixels" as there are characters in the maximum length number in the range (e.g. -23 is length 3, while 23 is length 2).

**Try it online!**

Note: If the input did not have to be an array it would be **11 bytes** taking two arguments, `[from, to]` and `sampleSize` with just `r/;"xẊĠ>ʋ¥G`.

---

I think this may be taking the convenient formatting allowance just a little too far for 4 bytes:

`Ṗ;1K`

This is using the idea (which should be addressed) put forward by Giuseppe in the comments with a single bin identified with `from` and `to` separated by a space, another space representing the axis and and a single `1` representing the height of 100%.

...or even just `Ṗ1` for 2 bytes!
> 3 votes

# Answer
# Octave, ~~34~~ 32 bytes

```
@(a,b,n)hist(--a+randi(b-a,n,1))

```

Doesn't work on TIO, but works on Octave-online.net.

It creates a histogram (bar chart) looking like this:

I'd say that counts as "Any convenient format".

If non-zero bins *must* be shown, then this can be solved in 38 bytes:

```
@(a,b,n)hist(--a+randi(b-a,n,1),a+1:b)

```
> 10 votes

# Answer
# , 36 bytes

```
function(a,b,n)stem(sample(a:b,n,T))

```

Try it online!

Sigh. A stemplot.

The bane of existence for second year university students taking *Introduction to Statistics for \[This Specific Area of Study\]* from some professor who doesn't know what they're talking about but still think stemplots are a good idea because it's still in the 14th edition of the textbook they've been using since the 4th edition was published in 1983.
> 6 votes

# Answer
# Charcoal, 25 bytes

```
≔…·θηθ≔Ｅζ‽θηＥθ№ηι↖←Ｅ⮌θ⮌Ｉι

```

Try it online! Explanation:

```
≔…·θηθ

```

Create an inclusive range of the distribution.

```
≔Ｅζ‽θη

```

Sample the range the desired number of times.

```
Ｅθ№ηι

```

Count and print the number of each of the range in the sample.

```
↖←Ｅ⮌θ⮌Ｉι

```

Print the labels.
> 5 votes

# Answer
# Python 2, 115 bytes

```
from random import*
a,b,n=input()
r=range(a,b+1)
s=sample(r*n,n)
for v in r:print'%%0%dd'%len(`b`)%v,s.count(v)*'x'

```

Try it online!

---

# Python 2, 164 bytes

column-based output.

```
from random import*
a,b,n=input()
r=range(a,b+1)
s=sample(r*n,n)
d=len(`b`)
while n:n-=1;print' '.join(d*'ox'[s.count(v)>n]for v in r)
for v in r:print'%%0%dd'%d%v,

```

Try it online!
> 3 votes

# Answer
# Java 11, ~~184~~ 168 bytes

```
(m,M,s)->{int a[]=new int[M],q=M;for(;s>0;q=M)if((q*=Math.random())>m-2){a[q]++;s--;}for(;m<=M;)System.out.printf("%0"+(M+"").length()+"d%s%n",m,"*".repeat(a[m++-1]));}

```

Try it online. (NOTE: `String.repeat(int)` is emulated as `repeat(String,int)` for the same byte-count, because Java 11 isn't on TIO yet.)

**Explanation:**

```
(m,M,s)->{                         // Method with three integer parameters & no return-type
                                   // (`m` = min_value; `M` = max_value; `s` = sample_size)
  int a[]=new int[M],              //  Integer-array, filled with `M` amount of 0s
      q=M;                         //  Temp integer for the random value, set to `M`
  for(;s>0;                        //  Loop as long as `s` isn't 0 yet:
      q=M)                         //    Reset `q` back to `M` after every iteration
    if((q*=Math.random())          //   Pick a random integer in the range [0, `M`)
       >m-2){                      //   If this random integer is larger than `m-2`:
      a[q]++;                      //    Increase the value at that this random index by 1
      s--;}                        //    And decrease `s` by 1
  for(;m<=M;)                      //  Loop in the range [`m`, `M`]
    System.out.printf(             //   Print with trailing new-line
      "%0"+(M+"").length()+"d%s%n",//   and leading zeros if necessary:
      m,                           //    The number
      "*".repeat(a[m++-1]));}      //    appended with "*" repeated the amount of times
                                   //    specified in the random array at index `m-1`

```
> 3 votes

# Answer
# , 52 bytes

```
function(a,b,n)table(cut(sample(a:b,n,T),a:(b+1)-1))

```

Try it online!

Returns a `table` of frequencies with `names` equal to the half-open intervals selected by `cut`, so `(0,1]`, `(1,2]`, `(2,3]`, and so forth. Makes no effort to select more reasonable binning.
> 2 votes

# Answer
# Ruby, 135 bytes, 117 bytes

```
d=->(m,n,s){p=(m..n);t=(1..s).map{rand(p)};p.map{|h|g=t.count(h);"#{h}-#{'x'*g}#{'o'*(t.map{|e|t.count(e)}.max-g)}"}}

```

Ungolfed:

```
d =-> (m,n,s) {
  p = (m..n)
  t = (1..s).map{rand(p)}
  p.map{ |h|
    g = t.count(h)
    "#{ h }-#{ 'x' * g }#{ 'o' * (t.map{|e| t.count(e) }.max - g) }"
  }
}

puts d.call(1,5,10)

```
> 2 votes

# Answer
## Perl 5, 85 bytes

```
/ \d+/;$d[$`+rand$&-$`+1]++for 1..$';say$"x(length($&)-length),$_,"-"x$d[$_]for$`..$&

```

Try it online!

Produces similar output to @Neil's Charcoal answer.
> 1 votes

# Answer
# JavaScript, 239

I'm sorry about this, but the variables were just named willy-nilly. Anyway, the question said *any convenient format*, so this function returns a sideways graph

```
f=>{x=Math;z=Array;q=_=>x.floor(x.random()*(f[1]-f[0]))+f[0];r=z(f[1]-f[0]).fill(0);z(f[2]).fill``.forEach(_=>r[q()-1]++);u=`${f[1]}`.length;return r.map((e,i)=>`${`${i}`.padEnd(u)}${" x".repeat(e)}`.padEnd(x.max(...r)*2+u," o")).join`\n`}

```
> 1 votes

# Answer
# Japt `-R`, 14 bytes

Takes input in the order max, min, size. Outputs the chart horizontally.

```
õV
öW
Ë+QpVè¥D

```

Try it

---

## Explanation

```
             :Implicit input of integers U=max_value, V=min_value & W=sample_size
õV           :Range [U,V]
\n           :Reassign to U
öW           :Get an array of W random elements from U
\n           :Reassign to V
Ë            :Map each integer D in U
 +           :  Append
  Q          :  Quotation mark
   p         :  Repeat
    Vè       :   Count the elements in V
      ¥D     :    That equal D
             :Implicitly join with newlines and output.

```
> 1 votes

# Answer
# Pyth, 19 bytes

```
JmOK}FPQeQVK,N*/JNd

```

Try it here

### Explanation

```
JmOK}FPQeQVK,N*/JNd
   K}FPQ             Get the inclusive range between the first two inputs as K.
JmO     eQ           Get <last input> random elements as J.
          VK         For each value in the range...
            ,N       ... output a list of the value...
              */JNd  ... and spaces equal to the count in J.

```
> 0 votes

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


title: Rounded Rectangles

text:
# Question
Title: Rounded Rectangles
# Challenge

Given an integer greater or equal to 4, n, print a rounded rectangle of as close as possible (with a gap of 1) sides and a perimeter of n characters.

# Rules

* n is always 4 or greater, because otherwise the output wouldn't be a square
* The characters for the perimeter can be any non-whitespace character
* The rectangle should have equal sides when possible
* When not possible, the rectangle can be up to one character taller or wider than its other side
* The rectangle should have one whitespace character in each corner
* The rectangle can only ever have a gap of 1 (excluding corners) along the entire perimeter
* The gap can be on any side and any position along the perimeter

# Rules

Least amount of bytes wins!

# Examples

```
Input: 4
Output:
 o
o o
 o

Input: 5
Output:
 oo
o  o
 o

Input: 8
Output:
 oo
o  o
o  o
 oo

Input: 21
Output:
 oooooo
o      o
o      o
o      o
o      o
o      o
 ooooo

```

Here is the python3 code I used to generate the above examples:

> ```
> import math
>
> ch = 'o'
>
> def print_rect(p):
>     side_length = math.ceil(p / 4)
>     height = side_length
>     remainder = p - side_length * 3
>     p = side_length + 2
>
>     if side_length - remainder >= 2 or not remainder:
>         remainder += 2
>         height -= 1
>
>     lines = [(ch * side_length).center(p)]
>     for i in range(height):
>         lines.append(ch + ch.rjust(side_length + 1))
>     lines.append((ch * remainder).center(p))
>
>     print('Output:')
>     for line in lines:
>         print(line)
>
> print_rect(int(input('Input: ')))
> ```

# Answer
# Python 2, 91 bytes

```
def f(n):t=(n+3)/4;c,s='o ';h=(n-t+1)/3;print'\n'.join([s+c*t]+[c+s*t+c]*h+[s+c*(n-t-h-h)])

```

Try it online!
> 2 votes

# Answer
# Charcoal, 24 bytes

```
Ｆ⁴«×o⁺÷Ｉθ⁴﹪÷﹪Ｉθ⁴Ｘ²↔⊖ι²¶↷

```

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

```
Ｆ⁴«

```

Loop over the four sides of the rounded rectangle.

```
×o⁺

```

Print a number of `o`s given by the sum of...

```
÷Ｉθ⁴

```

... one quarter of the input as a number, rounded down, and...

```
﹪÷﹪Ｉθ⁴Ｘ²↔⊖ι²

```

... add an extra `o` a) on both horizontal sides if the input has a remainder (modulo 4) of 2 or 3, and b) on the first vertical side if the input is odd.

Omit the corner.

Pivot ready for the next side.
> 2 votes

# Answer
# JavaScript, 143

```
n=>(x=Math.floor(n/4),q=n%2==1?x+1:x,` ${"o".repeat(q)}
${Array(n%4==2||n%4==3?x+1:x).fill(`o${" ".repeat(q)}o`).join`\n`}
 ${"o".repeat(x)}`)

```
> 0 votes

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


# Question
Title: Self-Validating Triangular Checkerboard Program
A checkerboard program is a program where each individual character's ordinal value alternates from even to odd, excluding the line terminator (which can be any standard line-endings).

A triangular program is a program where each line has one additional character than the preceding line, with the first line having one character. You do not need to handle empty input.

Your task is to build a program that validates that the given input adheres to those criteria and outputs/returns something truthy if the program meets the criteria, or something falsy otherwise.

Your program must also meet these criteria.

## Examples of valid programs

```
G
`e
@u^
5r{B

^
cB
+$C
VA01

```

## Rules

* Your program may start with either an odd or an even byte as long as the parity of the characters alternates.
* Your program must validate programs that start with either an odd or an even character.
* For unicode characters, the underlying byte values must have alternating parity.
* You can assume that input only contains printable characters. If your program contains unprintables, it should still be able to validate itself.
* Your program may include one trailing newline, this does not need to be allowed by your validation as you can assume this is removed prior to validating.
* Standard loopholes are forbidden.
* The shortest code in bytes, in each language, wins.

# Answer
# Stax, 26 bytes

```
L
Y$
i:-
 {2%
*OFyF
%vi =*

```

Run test cases online

I had to introduce 3 junk characters. `i` is a no-op when outside all loop constructs.  is always a no-op. `O` tucks a 1 under the top of the stack, but the value isn't used in the program.

```
LY      move input lines into a list and store in Y register
$       flatten
i       no-op
:-      get pairwise differences
{2%*OF  foreach delta, mod by 2, and multiply, then tuck a 1 under the top of stack
yF      foreach line in original input do...
  %v    subtract 1 from length of line
  i=    is equal to iteration index?
  *     multiply

```

Run this one
> 3 votes

# Answer
## C (gcc), 189 bytes

```
j
;l
;b;
d;f␉
(char
␉*␉t)
{b=*␉t%
2;for␉(␉
j=d=0;j=j
+ 1,␉l=j+
1,␉*␉t; ) {
for␉(;l=l- 1
 ;t=t+ 1 )b=
!b␉,␉d=d+ !(␉*
␉t␉*␉(␉*␉t- 10)
*␉(␉*␉t%2-b) ) ;
d␉|=*␉t- 10;t=t+
1 ; }b= !d; } ␉ ␉

```

Try it online!

represents a tab character (I'm sorry). Note that there are several trailing spaces/tabs (I'm more sorry). The original with tabs intact is best viewed in vim with `:set tabstop=1` (words cannot express how sorry I am).

It's a function (called `f`, which isn't immediately obvious from glancing at it) that takes a string as an argument and returns either `0` or `1`.

I *could* reduce this by at least one and probably two or more lines, but note that it gets increasingly messy and low-effort towards the end, mostly because writing such awful code (even by PPCG standards) was making me feel like a bad person and I wanted to stop as soon as possible.

The basic idea here is to avoid constructions that necessarily break the format (`++`, `+=`, `return`, etc.). Miraculously, important keywords like `for`, `char`, and `while` (which I didn't end up using) happen to fit the alternating parity rule. Then I used spaces (even parity) and tabs (odd parity) as padding to make the rest fit the rules.
> 8 votes

# Answer
# Haskell, ~~1080~~ 1033 bytes

```
;
f=
 g
ij=f
a =hi
hi = g
hij= ij
g ' ' =0
g '"' =0;
 g '$' =0;
 g '&' =0-0
g '(' =0-0-0
g '*' =0-0-0;
 g ',' =0-0-0;
 g '.' =0-0-0-0
g '0' =0-0-0-0-0
g '2' =0-0-0-0-0;
 g '4' =0-0-0-0-0;
 g '6' =0; g '8' =0
g ':' =0; g '<' =0-0
g '>' =0; g '@' =0-0;
 g 'B' =0; g 'D' =0-0;
 g 'F' =0; g 'H' =0-0-0
g 'J' =0; g 'L' =0-0-0-0
g 'N' =0; g 'P' =0-0-0-0;
 g 'R' =0; g 'T' =0-0-0-0;
 g 'V' =0; g 'X' =0-0-0-0-0
g 'Z' =0; g '^' =0; g '`' =0
g 'b' =0; g 'd' =0; g 'f' =0;
 g 'h' =0; g 'j' =0; g 'l' =0;
 g 'n' =0; g 'p' =0; g 'r' =0-0
g 't' =0; g 'v' =0; g 'x' =0-0-0
g 'z' =0; g '\92' =0-0; g '|' =0;
 g '~' =0; g y = 1 ;z=0; i(-0)z=z;
 i m('\10':y ) ="y"; ; ; ; ; ; ; ;
i m(mnmnmnmnm:y ) = i(m - 1 ) y ; ;
i k m ="y"; ; k i [ ] =01<1010101010;
 k m('\10':y ) = k(m + 1 )(i m y ) ; ;
 k m y =01>10; m o = k 1$'\10':o ; ; ;
o i('\10':y ) = o i y ; ; ; ; ; ; ; ; ;
o i(k:y )|g k<i = o(1 - i ) y ; ; ; ; ; ;
 o i(k:y )|g k>i = o(1 - i ) y ; ; ; ; ; ;
 o i [ ] =01<10; o i y =01>10;v=01>10101010
s y|o 1 y = m y|o(-0) y = m y ; s y =v; ; ;

```

Try it online!

## Explanation

This has been quite the interesting task for Haskell.

### Parity

To start we need some way of determining if a character has an even or odd code-point. The normal way one might do this is to get the code-point and mod it by 2. However as one might be aware, getting the code-point of a character requires an import, which due to the source restriction means that it cannot be used. A more experienced Haskeller would think to use recursion. `Char`'s are part of the `Enum` typeclass so we can get their predecessors and successors. However `pred` and `succ` are also both unusable because they don't alternate byte parity.

So this leaves us pretty stuck we pretty much can't do any manipulation with chars. The solution to this is to hardcode everything. We can represent (most) even chars as literals, odds we have trouble with because `'` is odd so it can't be next to the char itself making the literal impossible to express most of the odd chars. So we hard code all of the even bytes, and then add a catch all for the odd bytes at the end.

### The problem Bytes

You may notice that there are some even bytes for which literals cannot be made by wrapping it in single-quotes. They are the unprintables, newlines and `\`. We don't need to worry about unprintables since as long as we don't use any of them we don't need to verify. In fact we can still use odd unprintables, like tab, I just don't end up needing to. Newline can sagely be ignored because it will be trimmed from the program anyway. (We could include newline, because it's code-point is rather convenient, but we don't need to). This leaves `\`, now `\` has the codepoint 92, which conveniently is an odd number followed by an even number, so `\92` alternates between evens and odds thus the literal `'\92'` is perfectly valid. Later on when we do need to represent newline we will notice that it luckily has this same property `'\10'`.

### Spacing problems

Now in order to start writing actual code we need to be able to put a sizable number of characters on a single line. In order to do this I wrote the cap:

```
;
f=
 g
ij=f
a =hi
hi = g
hij= ij

```

The cap doesn't do anything except be valid Haskell. I had initially hoped to make definitions that would help us in the code later, but it didn't. There are also easier ways to make the cap, for example whitespace and semicolons, but they don't save bytes over this way so I haven't bothered to change it.

### Hardcoder

So now that I have enough space on a line I start hardcoding values. This is mostly pretty boring, but there are a few things of interest. For one once the lines start getting even longer we can use `;` to put multiple declarations on a line, which saves us a ton of bytes.

The second is that since we can't always start a line with a `g` every so often we have to indent the lines a bit. Now Haskell really cares about indentation, so it will complain about this. However if the last line before the indented line ends in a semicolon it will allow it. Why? I haven't the faintest, but it works. So we just have to remember to put the semicolons on the end of the lines.

### Function Building Blocks

Once the hardcoder is done it is smooth sailing to the end of the program. We need to build a few simple functions. First I build a version of `drop`, called `i`. `i` is different from `drop` in that if we attempt to drop past the end of the string it just returns `"y"`. `i` is different from drop also in that if it attempts to drop a newline it will return `"y"`, These will be useful because later when we are verifying that the program is a triangle this will allow us to return `False` when the last line is not complete, or when a line ends early.

Next we have `k` which in fact verifies that some string is triangular. `k` is pretty simple, it takes a number \\$n\\$ and a string \\$s\\$. If \\$s\\$ is empty it returns `True`. If the string begins with a newline it removes the newline and \\$n\\$ characters from the front. It then calls `k` again with \\$n+1\\$ and the new string. If the string does not start with a newline it returns `False`.

We then make an alias for `k`, `m`. `m` is just `k` with `1` in the first argument, and a newline prepended to the second argument.

Next we have `o`. `o` takes a number and a string. It determines if the string bytes (ignoring newlines) alternate in parity (using our `g`) starting with the input number.

Lastly we have `s` which runs `o` with both `1` and `0`, if either succeeds it defers to `m`. If it fails both it just returns `False`. This is the function we want. It determines that the input is triangular and alternating.
> 4 votes

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

```
¶
¡D
©€g
´ā´Q
´sJÇÈ
¥Ä{´нP

```

Try it online!

Takes the input as a multiline string (input between *"""*). Explanations to come later.
> 3 votes

# Answer
# Python 3 (3.4?), 350 bytes

A tricky challenge for a language as particular about whitespace as Python 3. The submission prints `0` or `1` to standard out and crashes for some inputs. The program expects the final line to be properly terminated, i.e. end with a newline character. The final line of the program is similarly terminated. UTF-8 is used to check byte parity.

Tabs are replaced with spaces in this view.

```
0
i\
= 1
t=(#
 '0'*
 0) ;(
g,) =(#
 open (1
, "w"),)
k = eval (
'p' + 'rin'
 + 't' ) #01
for  a in (#0
open ( 0) ):#0
#01010101010101
 a = a [:- 1 ] #
 if ( len (a )<i\
or len (a )>i ):[\
k('0' ),1 /0] #0101
 i, t= -~i, t+ a #01
(k( 2-len ({(c^i )&1\
 for  i,c in  eval (#0
 "enu"+"m"+"erate")(#01
 eval ( " byte"+"s")( t#
,' u8' ) ) } ) ) ) #01010

```

Works for me with Python 3.4.2; doesn't work on any Python 3 on TIO. Seems to me to be a bug in TIO's interpreters.

## Hex Dump

Revert with `xxd -p -r` on Unix.

```
300a695c0a3d20310a743d28230a202730272a0a093029203b280a672c29
203d28230a206f70656e0928310a2c09227722292c29200a6b203d206576
616c09280a277027202b202772696e270a202b202774272029202330310a
666f7209206120696e092823300a6f70656e092809302920293a23300a23
30313031303130313031303130310a2061203d2061205b3a2d2031205d20
230a2069660928096c656e09286120293c695c0a6f72096c656e09286120
293e6920293a5b5c0a6b2827302720292c31202f305d2023303130310a20
692c09743d202d7e692c09742b2061202330310a286b2809322d6c656e09
287b28635e69202926315c0a09666f720920692c6320696e09206576616c
092823300a0922656e75222b226d222b2265726174652229282330310a20
6576616c092809220962797465222b22732229280974230a2c2720753827
20292029207d202920292029202330313031300a

```
> 1 votes

# Answer
# Java 10, 209 bytes

A void lambda taking an iterable or array of `byte`. Indicates true by returning normally, false by throwing a runtime exception. The program expects the final line to be properly terminated, i.e. end with a newline character. The final line of the program is similarly terminated.

Everything is done under UTF-8, with the interpretation that "character" refers to Unicode code points.

Tabs are replaced with spaces in this view.

```
d
->
{
long
f= 1,
 h=0 ,
c = - 1
,e ;for
( byte a:
 d) {var b
=(e = a^10)
<1&e>- 1 ;f=
b?( h ^ f)> 0
?0/0 : f+ 1: f
;h=b?0 :a>-65 ?
h+ 1: h; c =b? c
:c>=0 & ( (c^a )&
1 )<1 ?0/0 :a ; }
/*1010101010101*/ }

```

Try It Online

## Hex dump

Revert with `xxd -p -r` on Unix.

```
640a2d3e0a7b20090a6c6f6e670a663d20312c0a09683d30092c0a63203d
202d20310a2c65203b666f72090a28096279746520613a0a096429207b76
617209620a3d2865203d20615e3130290a3c3126653e2d2031203b663d0a
623f280968095e0966293e09300a3f302f30093a09662b20313a09660a3b
683d623f30093a613e2d3635203f0a682b20313a09683b2063203d623f20
630a3a633e3d30092609280928635e612029260a3120293c31203f302f30
093a61203b207d200a2f2a313031303130313031303130312a2f207d0a

```

## Ungolfed

```
d -> {
    long f = 1, h = 0, c = ~h, e;
    for (byte a : d) {
        var b = (e = a^10) < 1 & e > -1;
        f = b ?
            (h^f) > 0 ? 0/0 : f + 1
            : f
        ;
        h = b ? 0 :
            a > -65 ? h + 1 : h
        ;
        c = b ? c :
            c >= 0 & ((c^a) & 1) < 1 ? 0/0 : a
        ;
    }
}

```

`f` is the expected number of characters on the current line, `h` is the number of characters seen so far on the current line, `c` is the last byte seen, and `b` is whether `a` is the newline.

The condition `a > -65` tests whether `a` is the first byte in a character. This works because the single-byte (ASCII) characters are nonnegative in 8-bit two's complement, the first byte of longer characters has binary form `11xxxxxx` (at least -64 in two's complement), and the non-leading bytes in those characters are of the form `10xxxxxx`, at most -65 in two's complement. (Source)

When a character violates the triangular or checkerboard pattern (i.e. a newline appears early or late or a byte of the wrong parity appears), the left branch of the corresponding ternary (in assignment to `f` or `c`) activates and the method throws an arithmetic exception.
> 1 votes

---
Tags: code-golf, restricted-source, source-layout
---


title: Bot: Outsnake the game!

text:
# Question
Title: Bot: Outsnake the game!
So, I wrote a simple Javascript game (as yet unnamed) and naturally I wanted to write an API so I could write a bot to play it for me, and naturally I wanted to let the PPCG community have a go for themselves.

It's a 'snake' game with the simple goal of collecting as many blue squares as possible while avoiding red squares or the edge of the board. It was initially controlled with a mouse.

Find the API edition of the game here: https://ajfaraday.github.io/game\_name\_here/api.html

**Gameplay:**

* Type the code for your bot in the field under 'Your function': This will repeat automatically when you tell it to run.
    + Only in Javascript, sorry.
    + See restrictions, below.
* You can try it step-wise by clicking 'step'.
* I suggest you 'Run (fast)' once you have a workable function.
* Click 'Reset' to try a fresh game.
* Every 10 points will increase the points per blue square by 1.
* Every 10 points will increase the red squares spawned by 1.
* You can lose lives by:
    + Gobbling up a red square (Be aware that, while you lose a life, it also breaks down the wall. Sacrificing lives to break through walls is a legitimate tactic).
    + Attempting to leave the game board.
    + Running down the 'Timeout' clock of 20 seconds between blue squares.
* You will not lose a life by 'stepping on your tail' in this version.
* Every 100 points will earn an additional life.
* Be aware that all coordinates are x, y starting in the *top left* corner. 0 indexed.

**Restrictions:**

* There is no security in this code. Please do not hack the game!
    + Only use standard JS and the API methods described.
    + PLEASE! Don't change API.coord
    + You may not interact directly with Sketch, Cell or other entities defined within the game.

**The competition**

* Please give your entry title a short name for your snake.
* Include your JS code and any explanation you'd like to include.
* The OP will copy/paste the code into the game, and run it 5 times (using 'Run (fast)').
* The highest score achieved in those attempts is your score.
* The OP will add your score to the answer, and to a leader board in the question.
* You may submit more than one function.

---

**Leader Board**

```
+--------------------------+---------------------------------+----------+
| Username                 | Snake Name                      | Score    |
+--------------------------+---------------------------------+----------+
| orlp                     | Simple A*                       | 595      |
+--------------------------+---------------------------------+----------+

```

**Rendering Issue**

This rendering issue has now been fixed and deployed.

~~Please be aware that if you call more than one of the direction methods during your function, the snake will visit all of the squares and collect points or lose lives accordingly. However, due to a rendering issue, it will only display the ending position of your snake.~~

Be aware that the snake **can not** travel diagonally between walls without losing a life.

---

**Responsible disclosure:** This is written in pure Javascript, it contains no logging, analytics or other data gathering processes. It's hosted on github pages, typically a trusted home of code.

If you want to confirm this, or would prefer to develop your answer on a locally hosted instance, the code is available here: https://github.com/ajfaraday/game\_name\_here

---

This is my first attempt at a competitive non-golf challenge, so I'm open to suggestions about how I could make it more suitable for this kind of situation.

Happy snaking!

# Answer
# Simple A\* - Official score: 595

This solution uses simple A\* pathfinding, with no long-term strategy - it always finds the optimal route towards just the next blue square.

```
var h = function(p, q) {
    // Manhattan distance.
    return Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]);
};

var s = JSON.stringify;
var p = JSON.parse;
var walls = API.walls.map(s);
var start = API.coord;
var goal = API.goal;

var is_closed = {};
is_closed[s(start)] = 0;
var open = [s(start)];

var came_from = {};
var gs = {};
gs[s(start)] = 0;
var fs = {};
fs[s(start)] = h(start, goal);

var cur;
while (open.length) {
    var best;
    var bestf = Infinity;
    for (var i = 0; i < open.length; ++i) {
        if (fs[open[i]] < bestf) {
            bestf = fs[open[i]];
            best = i;
        }
    }

    cur = p(open.splice(best, 1)[0]);
    is_closed[s(cur)] = 1;

    if (s(cur) == s(goal)) break;

    for (var d of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
        var next = [cur[0] + d[0], cur[1] + d[1]];
        if (next[0] < 0 || next[0] >= API.width ||
            next[1] < 0 || next[1] >= API.height) {
            continue;
        }

        if (is_closed[s(next)]) continue;
        if (open.indexOf(s(next)) == -1) open.push(s(next));
        var is_wall = walls.indexOf(s(next)) > -1;
        var g = gs[s(cur)] + 1 + 10000 * is_wall;
        if (gs[s(next)] != undefined && g > gs[s(next)]) continue;

        came_from[s(next)] = cur;
        gs[s(next)] = g;
        fs[s(next)] = g + h(next, goal);
    }
}

var path = [cur];
while (came_from[s(cur)] != undefined) {
    cur = came_from[s(cur)];
    path.push(cur);
}

var c = path[path.length - 1];
var n = path[path.length - 2];
if (n[0] < c[0]) {
    API.left();
} else if (n[0] > c[0]) {
    API.right();
} else if (n[1] < c[1]) {
    API.up();
} else {
    API.down();
}

```
> 4 votes

---
Tags: code-challenge, game, ai-player
---


title: Create a stem-and-leaf plot

text:
# Question
Title: Create a stem-and-leaf plot
Related: Validate a stem-and-leaf plot

# Input

A non-empty list of positive integers. If needed, they can be taken as strings. You cannot assume it is sorted.

# Output

A stem-and-leaf plot of the numbers. In ~~a~~ this stem-and-leaf plot, numbers are ordered into stems by tens, then all numbers that fit into that stem have their ones value placed into the stem, and then all are sorted. In this challenge, newlines separate the stems, and spaces separate the stems from the leaves.

You may either include or exclude all empty stems that are between non-empty stems.

# Test Cases

(lists can be taken in your language's list default, I used JSON for the below)

Including empty stems:

```
[1, 2, 3, 3, 3, 3, 3, 10, 15, 15, 18, 1, 100]

0 11233333
1 0558
2
3
4
5
6
7
8
9
10 0

[55, 59, 49, 43, 58, 59, 54, 44, 49, 51, 44, 40, 50, 59, 59, 59]

4 034499
5 0145899999

[10000, 10100]

1000 0
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010 0

```

Excluding empty stems:

```
[1, 2, 3, 3, 3, 3, 3, 10, 15, 15, 18, 1, 100]

0 11233333
1 0558
10 0

[55, 59, 49, 43, 58, 59, 54, 44, 49, 51, 44, 40, 50, 59, 59, 59]

4 034499
5 0145899999

[10000, 10100]

1000 0
1010 0

```

# Answer
> 2 votes
# , 12 bytes

```
stem(scan())

```

Try it online!

Explanation:

```
s               # imports RAND's "Million Random Digits"
  e  )          # cooks a pound of spaghetti and places it on the stack
 t              # transposes the output 42 times
       can      # goes for a pee
   m(           # grows moustache, turns head to side and frowns
      s   (     # implicitly ignores all criticism
           )    # makes a stemplot of the input

```

# Answer
> 3 votes
# Python 2, ~~78~~ ~~75~~ 79 bytes

```
s=-1
for i in sorted(input()):
 if i/10^s:s=i/10;print'\n%d-'%s,
 print`i`[-1],

```

Try it online!

# Answer
> 3 votes
# Jelly, 17 bytes

```
Ṣµ:©⁵Ġṁ@%⁵®Q¤żK€Y

```

Try it online!

# Answer
> 3 votes
## Retina, ~~38~~ 30 bytes

*Thanks to Neil for saving 2 bytes, and to Leo for saving another 6.*

Byte count assumes ISO 8859-1 encoding.

```
O#`
.\b
 $&
\B
0
D$`¶?.+
$*

```

Input is a linefeed-separated list of integers. Output omits empty prefixes.

Try it online!

# Answer
> 2 votes
# Python 2, ~~146~~ ~~140~~ ~~133~~ ~~124~~ ~~120~~ ~~118~~ ~~109~~ ~~107~~ ~~90~~ ~~86~~ ~~84~~ ~~91~~ ~~82~~ ~~81~~ ~~70~~ 63 bytes

*-6 bytes thanks to Rod. -9 bytes thanks to ovs.*

```
lambda l:{i/10:[j%10for j in sorted(l)if j/10==i/10]for i in l}

```

Try it online!

Okay, something is slightly wonky. As all Python programmers should know, dicts are unordered, meaning the original order of the key-value pairs is not preserved. However, in my current code, I do not sort the resulting dict at all. Yet, I have tested multiple times, checking for equality and order every single time, and the dict always comes out right. If anybody either disproves that it always comes out right or knows why this works, I'd love to know.

Input as a python list and output as a dict. Example:

Input:

```
[1, 2, 3, 3, 3, 3, 3, 10, 15, 15, 18, 1, 100]

```

Output:

```
{0: [1, 1, 2, 3, 3, 3, 3, 3], 1: [0, 5, 5, 8], 10: [0]}

```

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

```
a=>a.sort((a,b)=>a-b).map(e=>r[d=e/10|0]=(r[d]||d+` `)+e%10,r=[])&&r.filter(e=>e).join`
`

```

# Answer
> 1 votes
# Mathematica, 103 bytes

Code taken from @user202729's deleted answer

```
Grid[Table[{Keys[#][[i]],""<>ToString/@#[[i]]},{i,Length@#}]]&@(GroupBy[Sort@#,⌊#/10⌋&]~Mod~10&@#)&

```

# Answer
> 1 votes
## \>\<\>, 84 bytes

```
1&0\n~a7+3.
 :}<$?)@:$@:v!?
r~&^?-l&:+1&/&:,a-%a::
&=?v~&1+:&ao>n" "o:?!;::a%:@-a,&:

```

Try it online, or at the fish playground!

Assumes the input numbers are already on the stack.

Explanation: First, we sort the stack using a bubble sort, with this bit of code:

```
1&0\
 :}<$?)@:$@:v!?
   ^?-l&:+1&/

```

Next, we compute the integer-quotient of the first thing in the stack by 10 using `::a%-a,`, put that in the register, and go through the stack printing the last digits of the numbers until their first digits aren't the same as the register, then incrementing the register and continuing. When we reach the end of the list, marked with a `0`, we stop.

# Answer
> 1 votes
# PostgreSQL, 53 bytes

```
SELECT n/10,json_agg(n%10ORDER BY n)FROM t GROUP BY 1

```

The list of integers must reside in an `integer` column `n` of an existing table `t`. The result is a two-column table: each row consists of a "stem" column and a "leaves" column. The "leaves" column is in JSON array format. (As noted in the comments, it is not necessary to adhere exactly to the format shown under "Test Cases".)

Though the order of stems is not guaranteed (to save 10 bytes, `ORDER BY 1` is omitted from the end of the query), in my testing, the stems did seem to end up in the correct order.

View result on SQL Fiddle

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


title: Reverse ASCII character map

text:
# Question
Title: Reverse ASCII character map
In Map inputted ASCII characters, I asked you to .. map inputted ASCII characters. This time, you will do the opposite, by immediately mapping all ASCII characters, and then mapping spaces over them.

This program will have practical uses, such as seeing what characters you have left in a challenge submission.

# Challenge

Your job is to write a program that *un*-maps inputted ASCII characters. As soon as the program is run, it will display *this exact map* (except color, font, size, etc.):

Each time the user inputs a printable ASCII character, you will print a space over it.

# Rules

* The initial output must be exactly as shown in the first image above: a 6x16 grid with ASCII characters in their respective positions, with the space (32) at the top left and the tilde (126) at one character left from the bottom right.
* Your program only needs to display the printable ASCII characters, `0x20` to `0x7E`.
* Your program must not terminate and continue to print spaces over characters until all printable ASCII characters have been overwritten. From here, your program can either terminate or run off into Neverland.
* Your reverse map must be updated in realtime (as soon as it receives user input).
* If your program does not read input silently, it must put the cursor out of the way, so the text won't get in the way of the map.

Here's a useful ASCII table for reference.

# Scoring

The answer with the least bytes in each language wins. Have fun!

# Answer
> 2 votes
# SOGL V0.12, 23 bytes

```
] ~Δ8«n"5αx2⁰³⁄¹‘→č@ŗ░T

```

Try it Here!

Takes input in the input box. I hope that it isn't too big of an issue that characters can be deleted :p

Explanation:

```
]                   do.. while (popping (which makes the stack not blow up luckily :D))
  ~Δ                push the ascii characters (range("~"))
    8«n             split into lines of length 16
       "...‘        push "inputs.value" (could be 2 bytes less if my dictionary contained the word "inputs". I even added "input", but only now realise that the input box is id=inputs :/)
            →       evaluate as JavaScript, then push the result
             č      chop into characters
              @ŗ    replace each of the characters in the array with space
                ░   clear the output
                 T  output without popping (so do..while continues looping)

```

# Answer
> 6 votes
# x86-16 Machine Code, 62 bytes

Hex dump:

```
BC0100B101B07EBAFE0581EAE00080EA02B402CD1085E4750830E439C5750A30C0B40ACD1084C074094884D275E085D275D831C031E4CD1630E489C5EBC7

```

Assembly:

```
mov sp, 0x0001           ; Stack pointer is used as a flag; 0 - Print all characters, 1 - Delete specific character
mov cl, 0x01             ; Number of characters to print per interrupt call

printString:
  mov al, 0x7E           ; Last character to print
  mov dx, 0x05FE         ; Row: 0x05, Collumn: 0xFE
  printRow:
    sub dx, 0x00E0       ; Decrement row number + 2 extra characters
    printChar:
      sub dl, 0x02       ; Decrement collumn index + 1 space
      mov ah, 0x02       ; Prepare for interrupt call, 0x02 - Set cursor position
      int 0x10           ; BIOS interrupt

      test sp, sp        ; Are we printing all characters or removing specific character
      jnz print          ; In first case just print it and go on
      xor ah, ah         ; Otherwise reset the upper byte of ax (shorter than "and ax, 0x00FF")
      cmp bp, ax         ; Is the current character same as the input character
      jne after          ; If no, continue searching
      xor al, al         ; If yes, remove it

      print:
        mov ah, 0x0A     ; Prepare for print
        int 0x10         ; Print

      test al, al        ; If we found target character
      jz loop            ; then stop searching

      after:
        dec ax           ; Shorter than "dec, al"
        test dl, dl      ; Is it the last character in the row
        jnz printChar    ; If no, continue searching
    test dx, dx          ; Is it last char
    jnz printRow         ; If no, go to next row

loop:
  xor ax, ax             ; Remove "ah" cache
  xor sp, sp             ; Reset sp (it will never become 1 again)
  int 0x16               ; BIOS interrupt for reading keyboard input
  xor ah, ah             ; Again reset "ah", because BIOS may change it
  mov bp, ax             ; Save it in stack base pointer
  jmp printString        ; Remove the character from the list

```

# Answer
> 2 votes
# C++ (Visual C++), 253 (@Step Hen) ~~261~~ bytes

```
#include<cstdlib>
#include<iostream>
#include<conio.h>
int main(){char a[0x5E];for(int i=0;i<0x5E;i++)a[i]=(char)(i+0x20);while(true){system("cls");for(int i=0;i<0x5E;i++)if(i&&!(i%16))printf("\n%c ",a[i]);else printf("%c ",a[i]);a[_getch()-0x20]=' ';}}

```

# Answer
> 1 votes
# Python 2, 132 bytes

Saved 4 bytes thanks to @alleks!

```
s=''
for i in range(32,128,16):s+=' '.join(map(chr,range(i,i+16)))+'\n'
while 1:print s[:-2];i=2*ord(input())-64;s=s[:i]+' '+s[i+1:]

```

Try it online!

# Answer
> 1 votes
# Python 3, 116 bytes

```
o='\n'.join(''.join(map(chr,range(i,16+i)))for i in range(32,124,16))[:-1]
while 1:print(o);o=o.replace(input()," ")

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6) + HTML, ~~139~~ ~~136~~ 116 + ~~10~~ 16 = 132 bytes

*-3 bytes thanks to @Shaggy.*
*-14 bytes inspired by @Arnauld.*

```
for(i=32;i<127;)O[h="innerText"]+=String.fromCharCode(i++)+(i%16?" ":`
`);onkeypress=e=>O[h]=O[h].replace(e.key," ")
```

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

Closing `pre` tag is required in this case, since we need the `innerText` value to start totally empty.

# Answer
> 1 votes
# QBasic, 107 bytes

An anonymous function that takes as keystrokes, and erases an ASCII table

```
FOR x=32TO 126
L x
?CHR$(x)
NEXT
DO
L ASC(Input$(1))
?" "'<- `"` included for highlighting only
LOOP
SUB L(x)
LOCATE x\16-1,2*(x MOD 16)+1
END SUB

```

-8 bytes thanks to @DLosc

# Answer
> 0 votes
# C# (.NET Core), (138 + using System;) 151 bytes

```
()=>{var j="";for(int i=32;i<127;i++){if(i%16<1)j+='\n';j+=(char)i+" ";}while(1>0){Console.Write(j);j=j.Replace(Console.ReadLine()," ");}}

```

Try it online!

# Answer
> 0 votes
# Node.js ~~233~~ 212 bytes

*Saved 21 bytes thanks to @thePirateBay*

This works, I'm still trying to find an online option as all the repls I've found hijack stdin.

```
a=[];l=_=>console.log(a.join``);for(i=32;i<127;i++)(x=String.fromCharCode(i)),a.push(i%16?x:x+'\n');l();b=require('readline');b.createInterface(process.stdin).on('line',c=>(a=a.join``.replace(c,' ').split``),l())

```

Try it online

# Answer
> 0 votes
# 65c02 machine code + Apple //e ROM, 52 (47?) bytes

Hex dump:

```
8000- 20 58 FC A9 A0 20 20 80
8008- 20 ED FD 1A C9 FF D0 F5
8010- AD 00 C0 10 FB 8D 10 C0
8018- 20 20 80 20 57 DB 80 F0
8020- 48 38 E9 A0 48 29 0F 0A
8028- 85 24 68 4A 4A 4A 4A 20
8030- 5B FB 68 60

```

Commented assembly:

```
 1 HTAB     =     $24        ; HORIZONTAL POSITION OF CURSOR
 2 SETVTAB  =     $FB5B      ; SETS VERTICAL POSITION OF CURSOR FROM ACC
 3 COUT     =     $FDED      ; OUTPUTS CHARACTER IN ACC
 4 HOME     =     $FC58      ; CLEARS SCREEN
 5 OUTSP    =     $DB57      ; APPLESOFT ROUTINE THAT OUTPUTS A SPACE
 6 KBD      =     $C000      ; KEY LAST PRESSED
 7 KBSTROBE =     $C010      ; ACCESS TO RESET "NEW KEY PRESSED" INDICATOR
 8          ORG   $8000
 9          JSR   HOME
10 * PRINT INITIAL CHARACTER MAP
11          LDA   #" "
12 LOOP     JSR   CHARPOS
13          JSR   COUT
14          INC              ; INCREMENT ACCUMULATOR
15          CMP   #"~"+1
16          BNE   LOOP
17 * WAIT FOR KEYPRESS
18 GETCH    LDA   KBD        ; GET LAST KEY PRESSED
19          BPL   GETCH      ; READ AGAIN IF KEYPRESS IS NOT NEW
20          STA   KBSTROBE   ; RESET "NEW KEYPRESS" INDICATOR
21          JSR   CHARPOS
22          JSR   OUTSP
23          BRA   GETCH
24 * SUBROUTINE TO POSITION CURSOR TO PRINT OVER CHARACTER IN ACCUMULATOR
25 CHARPOS  PHA              ; PRESERVE ACC
26          SEC              ; MAKE SURE CARRY IS SET TO SUBTRACT
27          SBC   #" "       ; SUBTRACT CHAR CODE OF SPACE
28          PHA              ; SAVE ACC
29          AND   #$0F       ; GET LOWER 4 BITS TO GET CURSOR X POSITION
30          ASL              ; SHIFT LEFT TO MAKE SPACES BETWEEN CHARS
31          STA   HTAB
32          PLA              ; GET OLD ACC
33          LSR              ; SHIFT HIGH NIBBLE
34          LSR              ; INTO LOW NIBBLE
35          LSR              ; TO GET CURSOR Y POSITION
36          LSR
37          JSR   SETVTAB
38          PLA              ; RESTORE ACC
39          RTS

```

This has no cursor whatsoever. I also have a 47 byte version which might be valid, depending on what is meant by "put the cursor out of the way, so the text won't get in the way of the map":

```
8000- 20 58 FC A9 A0 20 1B 80
8008- 20 ED FD 1A C9 FF D0 F5
8010- 20 0C FD 20 1B 80 20 57
8018- DB 80 F5 48 38 E9 A0 48
8020- 29 0F 0A 85 24 68 4A 4A
8028- 4A 4A 20 5B FB 68 60

```

This puts a cursor at the character after the character you type (which is the space between characters), so it won't overwrite any of the actual characters in the map. Whether this is valid or not is up to the creator of the challenge.

# Answer
> 0 votes
# Python 2, 96 bytes

```
from textwrap import*
a=fill(str(bytearray(range(32,127))),16)
while 1:a=a.replace(input(a),' ')

```

Try it online! Output looks iffy on TIO (because input is passed from a file), but it’s fine interactively. I hope `'A'\n`, `'B'\n` etc is an okay input format.

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


title: XOR reduction bools

text:
# Question
Title: XOR reduction bools
# Description :

Given a string of space separated binary digits or space separated booleans or an array of binary digits or array of booleans . Your job is to find the xor of each until you end up with one answer either 0 or 1. The inputs will always be valid and will only be either 0 or 1.

# Example :

```
1 0 0 1 0 --> 0
1 0 1 1 1 0 0 1 0 0 0 0 --> 1

```

This is code golf so shortest code will win. Good luck.

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

```
s=>eval(s.join`^`)

```

Try it online!

# Answer
> 3 votes
# Java (JDK 10), 12 bytes

```
s->s.sum()%2

```

Try it online!

If a string is really required, then **20 bytes**:

```
s->s.chars().sum()%2

```

Try it online!

The "string" answer uses the fact that a space is codepoint 32, which mod 2 returns 0.

# Answer
> 2 votes
# Python 2, 17 bytes

```
lambda a:sum(a)%2

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 2 bytes

Try it online.

**Explanation:**

* `O`: Take the sum of the input-array
* `É`: Evaluates `sum % 2 == 1`, returning `1` if the sum is odd, `0` otherwise

---

**3 bytes**:

A leading `Ç` can be added if the space-delimited string input was still mandatory, instead of a boolean-array.

Try it online.

* `Ç`: Push the ASCII values of all characters, and implicitly convert it to a list. `0 1` would become `[48, 32, 49]` in that case. The `O` (sum) and `É` (is odd?) will still act the same.

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

```
a=>a.reduce((c,d)=>c^d)

```

Try it online!

# Answer
> 1 votes
# MATL, ~~3~~ 2 bytes

```
so

```

Input can be a numeric vector of the form `[1 0 0 1 0]`, or a string such as `'10010'` (thanks to @Giuseppe for noticing!).

**Try it online!**

### Explanation

The code is `so` simple that it hardly needs an explanation, but here it goes.

```
s    % Implicit input: numeric vector (or string). Sum of the numbers. (For string
     % input, the ASCII codes are summed. Character '1' is odd, '0' is even, and
     % space is even too, so the parity is the same as with numeric vector input)
o    % Parity. Implicit display

```

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 44 bytes

```
A	X =X + INPUT	:S(A)
	OUTPUT =REMDR(X,2)
END

```

Try it online!

# Answer
> 1 votes
# Perl 5 `-p040`, 10 bytes

Assumes the input list can't be empty

```
$\^=0+$_}{

```

Try it online!

# Answer
> 1 votes
# Java 10, 41 bytes

```
b->{var r=1<0;for(var c:b)r^=c;return r;}

```

The variable r is initially set to false, since we are `XOR`ing `b[0]` with it. Try it online here.

# Answer
> 0 votes
# Jelly, ~~5~~ ~~3~~ 2 bytes

```
^/

```

Try it online!

-2 bytes thanks to user202729!

# Answer
> 0 votes
# Add++, 8 bytes

```
L~,€Os2%

```

Try it online!

# Answer
> 0 votes
# (Traditional) APL, 3 or 4 bytes

TIO, courtesy Adám

```
≠/⍎⎕

```

Analysis:

\- Accept input.
\- "unquote" it (if it's a quoted string, this will convert it to a numeric vector. If it's already a numeric vector, this is effectively a null op)
`/` \- reduction - apply the operator to the left to each successive item in the vector to the right
\- "not equal" - when applied strictly to boolean arguments, this is functionally identical to XOR (which is not implemented as a separate operator in APL)

If it may be assumed that the input will be a numeric vector instead of a quoted string, then the 'unquote' can be removed, saving one byte:

```
≠/⎕

```

# Answer
> 0 votes
# Befunge-98 (FBBI), 8 bytes

```
#.~+2%#@

```

Try it online!

# Answer
> 0 votes
# Japt, 2 bytes

```
r^

```

Try it

Does exactly what it says on the tin, `r`educe the array by XORing.

# Answer
> 0 votes
# Cubix, 11 bytes

```
i?+<^<@Oa1<

```

Try it online!

It's been a while, so it feels good to write a Cubix answer!

# Answer
> 0 votes
# Whispers v2, 38 bytes

```
> Input
> 2
>> ∑1
>> 3%2
>> Output 4

```

Try it online!

I feel like 3 answers is too many, but I wanted to get Whispers out again. I'm still working on an XOR approach

# Answer
> 0 votes
# C (gcc), ~~41~~ ~~39~~ 38 bytes

Saved a few bytes with inspiration from ceilingcat.

Saved another byte thanks to Jonathan Frech

```
r;f(char*s){for(r=0;*s;)r^=*s++;r&=1;}

```

Try it online!

# Answer
> 0 votes
# Ruby, 42 bytes

```
->s{s.split(' ').reduce(0){|a,b|a^b.to_i}}

```

Try it online!

# Answer
> 0 votes
# APL (Dyalog Unicode), 2 bytesSBCS

Tacit prefix function.

```
≠/

```

Try it online!

`/` is reduction and  is XOR because XOR only gives `1` if its arguments are unequal.

# Answer
> 0 votes
# Julia 0.6, 12 bytes

```
b->⊻(b...)

```

Try it online!

is the xor symbol, and `b...` distributes an array as individual elements before sending it to the xor function (since xor needs multiple arguments passed separately, not a single array argument).

A bit more interestingly, a version that accepts space separated (/comma-separated/unseparated) boolean values as a string, and returns the xor result :

### Julia 0.6, 22 bytes

```
b->sum(Int.([b...]))%2

```

Try it online!

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


title: Speverse Roonerisms

text:
# Question
Title: Speverse Roonerisms
A spoonerism is what you get when swap the beginnings of two adjacent words in a sentence. In this challenge, we'll try to find a plausible spoonerism based on one incorrect word.

So, given a list of words\** and an input word that is **NOT** in the dictionary, return a string (not necessarily a dictionary word) for which the following property holds.

There exist some indices `i` and `j` such that `input_word[:i] + output_word[j:]` and `output_word[:j] + input_word[i:]` are **BOTH** in the dictionary. Here, I'm using Python notation for substrings: `word[lo:hi]` is the substring of word starting at `lo` and ending at `hi-1`. `[:hi]` is shorthand for `[0:hi]` and `[lo:]` is shorthand for `[lo:len(word)]`.

\** Say, those in the `/usr/share/dict/words` provided by the `wamerican` package in Ubuntu 16.04

An example is in the title:

```
input_word = "roonerisms"
output_word = "speverse"
i, j = 1, 2
print(input_word[:i] + output_word[j:])
print(output_word[:j] + input_word[i:])

```

You can assume that everything is lowercase and the dictionary is preprocessed to contain only letters a-z and newlines. You can take the list in whatever standard format you like (eg. sorted list, set, etc. not a preprocessed lookup table) and you need only return one string, not all of them.

# Answer
# Python 2, ~~154~~ ~~161~~ ~~157~~ 155 bytes

```
def f(s,d):L=len(s);u,v=sum((zip([w[i:]for w in d if w[:i]==s[:i]],[[w,w[:i-L]][i<L]for w in d if w.endswith(s[i:])])for i in range(L+1)),[])[0];return v+u

```

Try it online!

For the testing, uses the 'standard' dictionary with some tweaks (because that dictionary includes single letters, it makes for a lot of boring results).

2 bytes thx to Jakob.
> 2 votes

---
Tags: code-golf
---