title: How many Sets are there?

text:
# Question
Title: How many Sets are there?
This is similar in concept to this challenge, but that is pretty restrictive on input and output and I think opening up these restrictions would lead to a completely different set of solutions that would be interesting in their own right.

---

## Background

*Set* is a card game in which players compete to construct sets of three cards from a collection based on certain rules. Each card has four attributes: number, shape, color, and pattern. For a set to be valid, the cards must all either match or differ in each of the attributes.

For example, three cards being 1 empty green diamond, 1 shaded red diamond, and 1 filled purple diamond would constitute a Set. An example of a non-set is 1 empty green diamond, 2 shaded red diamonds, and 3 filled green diamonds. This is not a valid Set because while the numbers are different, patterns different, and shape the same, two of them share a color that the third does not.

## The Challenge

Your job is to write a function that takes a list of twelve cards as a parameter and outputs the number of valid Sets. The cards must consist of a collection of four values, each representing an attribute on the card. Each attribute may have its own set of values to represent the different states, but there are only three states, and your choice of representation must be consistent across cards and inputs. This is Code Golf, so the shortest solution wins.

## Test Cases

In my test cases, cards are represented by a 4-tuple with each attribute being encoded by a number 0-2. The first column is the expected output, and the second column is the input.

```
0  | (0, 2, 1, 1), (0, 0, 0, 2), (0, 1, 0, 0), (1, 2, 1, 0), (1, 1, 2, 2), (0, 1, 2, 1), (0, 1, 1, 0), (1, 0, 2, 0), (1, 1, 0, 1), (2, 2, 0, 1), (1, 0, 2, 1), (2, 1, 1, 2)
1  | (0, 2, 0, 2), (0, 2, 0, 0), (2, 2, 2, 1), (2, 0, 0, 0), (1, 0, 2, 2), (2, 1, 2, 2), (0, 1, 2, 1), (2, 0, 1, 1), (1, 0, 1, 1), (1, 2, 2, 1), (0, 1, 2, 2), (2, 1, 0, 2)
2  | (2, 0, 1, 0), (1, 0, 1, 1), (0, 1, 0, 0), (2, 0, 1, 2), (2, 0, 0, 1), (2, 2, 2, 0), (0, 1, 2, 2), (1, 1, 0, 0), (0, 2, 2, 2), (1, 1, 1, 1), (0, 1, 0, 2), (0, 1, 0, 1)
3  | (2, 1, 0, 2), (1, 0, 2, 1), (2, 2, 1, 1), (2, 0, 1, 2), (1, 2, 1, 1), (1, 2, 2, 2), (0, 0, 1, 2), (0, 0, 2, 1), (2, 0, 0, 0), (2, 1, 2, 0), (0, 2, 2, 0), (0, 0, 1, 0)
4  | (1, 0, 1, 0), (2, 2, 0, 1), (2, 0, 1, 2), (0, 0, 2, 1), (1, 2, 0, 1), (2, 2, 1, 0), (2, 0, 2, 1), (1, 1, 0, 2), (2, 1, 0, 2), (0, 1, 2, 2), (1, 2, 2, 0), (1, 0, 1, 2)
5  | (2, 2, 1, 0), (1, 2, 1, 0), (2, 0, 0, 0), (0, 0, 1, 2), (0, 0, 0, 2), (0, 1, 2, 0), (0, 2, 0, 1), (2, 2, 2, 0), (1, 2, 1, 2), (0, 1, 1, 0), (2, 0, 1, 0), (2, 1, 2, 1)
6  | (2, 1, 1, 0), (0, 1, 0, 1), (1, 1, 0, 2), (0, 0, 2, 2), (1, 0, 2, 0), (2, 1, 0, 0), (2, 2, 2, 2), (2, 0, 1, 1), (1, 0, 2, 1), (2, 2, 0, 1), (2, 2, 1, 2), (0, 1, 0, 0)
7  | (1, 0, 1, 0), (1, 1, 0, 0), (2, 1, 2, 0), (2, 0, 1, 1), (0, 0, 2, 0), (0, 2, 1, 1), (0, 1, 1, 0), (0, 0, 1, 2), (1, 0, 0, 2), (0, 2, 2, 1), (1, 0, 2, 2), (0, 0, 0, 1)
8  | (1, 2, 0, 1), (2, 2, 2, 1), (1, 2, 2, 0), (0, 1, 2, 2), (1, 1, 0, 1), (0, 0, 1, 1), (0, 2, 2, 0), (2, 0, 2, 1), (2, 1, 0, 2), (0, 1, 0, 0), (1, 2, 1, 2), (2, 0, 0, 2)
9  | (0, 2, 2, 1), (0, 1, 0, 0), (2, 1, 1, 0), (2, 0, 1, 0), (2, 0, 0, 2), (2, 1, 2, 1), (2, 2, 1, 0), (0, 2, 1, 1), (1, 2, 0, 2), (0, 0, 1, 0), (0, 1, 0, 2), (1, 1, 1, 0)
10 | (0, 1, 2, 0), (1, 1, 2, 0), (1, 0, 1, 2), (2, 0, 2, 0), (1, 1, 1, 2), (1, 2, 1, 2), (0, 2, 2, 0), (1, 1, 0, 1), (2, 0, 0, 1), (2, 1, 0, 1), (0, 0, 0, 1), (2, 2, 1, 2)

```

# Answer
> 11 votes
# Jelly, 10 bytes

```
œc3S€3ḍẠ€S

```

Try it online!

### How it works

```
œc3S€3ḍẠ€S    Main link. Input: a list of 4-tuples of 0,1,2
œc3           3-card combinations
   S€3ḍẠ€     For each combination,
   S€         Sum all the cards' values for each attribute
     3ḍ       Test if each sum is divisible by 3
       Ạ€     Test if all of them are true
         S    Sum the boolean array (count the valid Sets)

```

# Jelly, 10 bytes

```
Zœc€3§3ḍPS

```

Try it online!

Alternative solution, which can make a 9 by omitting the leading `Z` if taking the input transposed is allowed.

# Answer
> 6 votes
# K (ngn/k), ~~27~~ 25 bytes

```
{-2+-6!+/*/~+3!+/x@!3#12}

```

Try it online!

*-2 bytes thanks to @ngn*

K doesn't have a built-in for combinations. This code uses simple Cartesian 3rd power instead. If you count the number of sets the same way, you get 12 plus 6 times the desired answer (for 12 self-triples and 6 different permutations for each valid Set). Then just divide by 6 and subtract 2.

# Answer
> 6 votes
# ARM T32 machine code, 48 bytes

```
b570 0084 2000 e00f 590a 594b 18d2 598b
18d2 230b 435a f012 3f0c bf08 3001 3e04
d5f2 3d04 1f2e d5ef 3c04 1f25 d8fa bd70

```

Following the AAPCS, this takes the number of cards in r0 (permitted here; this can handle an arbitrary number of cards), and in r1 the address of the cards as an *array* of size-4 *array*s of 8-bit integers, and returns the result in r0.

Assembly:

```
.section .text
.syntax unified
.global countsets
.thumb_func
countsets:
    push {r4,r5,r6,lr}  @ Save some registers and LR to the stack
    lsls r4,r0,#2       @ First card selector is 4 times number of cards: this is done because narrow LDR can only use for the address the sum of two registers, while only the wide version can have one of the registers shifted
    movs r0,#0          @ Initialise count to 0
    b start
loop:
    ldr r2,[r1,r4]
    ldr r3,[r1,r5]
    adds r2,r3
    ldr r3,[r1,r6]
    adds r2,r3            @ Add up the cards
    movs r3,#11
    muls r2,r3,r2         @ Multiply by 11
    tst.w r2,#0x0C0C0C0C  @ AND with this constant...
    it eq
    addeq r0,#1           @ and increment count if the result is 0
    subs r6,#4     @ Decrease third card selector
    bpl loop       @ Repeat if still nonnegative
    subs r5,#4     @ Decrease second card selector
middle:
    subs r6,r5,#4  @ Third card selector goes to below second card selector
    bpl loop       @ Repeat if that's nonnegative
start:
    subs r4,#4     @ Decrease first card selector
    subs r5,r4,#4  @ Second card selector goes to below first card selector
    bhi middle     @ Jump if that's positive
    pop {r4,r5,r6,pc}  @ Restore saved registers and return

```

This uses three nested loops to iterate over all combinations of three cards. For each combination, it adds the cards up (as 32-bit integers, but the four parts don't interact) and multiplies by 11. The possible results of that are as follows, in binary:

```
0 -> 00000000
1 -> 00001011
2 -> 00010110
3 -> 00100001
4 -> 00101100
5 -> 00110111
6 -> 01000010
-------------
AND: 00001100

```

As 11 is a bit more than 32/3, the result's bottom bits form a low number when the sum is a multiple of 3, and a higher number otherwise. Taking the bitwise AND (`tst`) with an immediate value with each byte being `0C` then yields zero if and only if all four sums are multiples of 3, which means that it is a set.

# Answer
> 5 votes
# Python 3.8, 91 bytes

Outputs `False` for `0`.

Python has a builtin called `itertools.combinations` to get all of the triplets, but it's shorter just to implement it from scratch.

```
f=lambda a,*v:a and f(t:=a[1:],*v,a[0])+f(t,*v)or len(v)==3*all(sum(y)%3<1for y in zip(*v))

```

Try it online!

### Python 3, 94 bytes

```
lambda a:sum(all(sum(y)%3<1for y in zip(*x))for x in combinations(a,3))
from itertools import*

```

Try it online!

# Answer
> 4 votes
# Python 3, ~~84~~ 81 bytes

```
lambda a:sum({*map(sum,zip(x,y,z))}<={0,3,6}for x in a for y in a for z in a)/6-2

```

Incorporating ideas from the answers of @dingledooper and @Bubbler

Try it online!

# Answer
> 3 votes
# , 48 41 bytes

```
1#.](0=1#.3|1#.|:)@#~2(#~3=1#.])@#:@i.@^#

```

Try it online!

*-7 after reading Bubbler's divide by 3 trick*

# Answer
> 3 votes
# , 27 bytes

```
_2+6%~1#.[:,0=1#.3|+"1/^:2~

```

Try it online!

J makes it hard to construct the Cartesian 3rd power directly, but easy to compute the attribute-wise sum of the cards in it. The result of "Table" `x f/ y` is dependent on the function rank of `f`. `+"1` has rank 1 on both sides, so it computes the table of "rows of x added to rows of y".

# Answer
> 3 votes
# Brachylog, 12 bytes

```
{⊇Ṫ\{=|≠}ᵐ}ᶜ

```

Try it online!

```
{⊇Ṫ\{=|≠}ᵐ}ᶜ
{         }ᶜ Count all …
 ⊇           subsets of the input …
  Ṫ          that are length 3 (Ṫriplets) …
   \         which transposed …
    {   }ᵐ   only have rows that …
     =|≠     are all equal or all different.

```

# Answer
> 1 votes
# Vyxal `s`, 8 bytes

```
3ḋƛ÷Ṡ3ḊA

```

Try it Online!

Jelly port be like

# Answer
> 0 votes
# Perl 5, 126 bytes

```
sub{1/6*grep{@s=map@$_,@_[map-65+ord,/./g];!/(.).*\1|[M-Z]/&&!grep{$m=$_;eval(join'+',@s[grep$_%4==$m,0..11])%3}0..3}AAA..LLL}

```

Try it online!

# Answer
> 0 votes
# Charcoal, 31 bytes

```
ＩΣ⭆θ⭆…θκ⭆…θμ⬤Ｅ⁴Ｅ⟦ιλν⟧§ςπ⬤π⁻²№πς

```

Try it online! Link is to verbose version of code. Explanation: A group of cards forms a Set if no single attribute appears exactly twice in any aspect.

```
   θ                            Input
  ⭆                             Map over cards and join
      θ                         Input
     …                          Truncated to length
       κ                        Outer index
    ⭆                           Map over cards and join
          θ                     Input
         …                      Truncated to length
           μ                    Current index
        ⭆                       Map over cards and join
             Ｅ⁴                 Map over aspects
               Ｅ⟦ιλν⟧           Map over cards
                     §ςπ        Aspect of current card
            ⬤                   All aspects satisfy
                         π      Current aspect
                        ⬤       All attributes satisfy
                            №   Count of
                              ς Current attribute
                             π  In current aspect
                          ⁻     Subtract i.e. does not equal
                           ²    Literal `2`
 Σ                              Take the sum (i.e. count)
Ｉ                               Cast to string
                                Implicitly print

```

# Answer
> 0 votes
# 05AB1E, 10 bytes

```
3.Æ€øO3ÖPO

```

Port of *@Bubbler*'s Jelly answer, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
3.Æ         # Get 3-element combinations of the (implicit) input list of lists
   €ø       # Zip/transpose each inner list of lists; swapping rows/columns
     O      # Sum the inner lists of columns together for each inner-most list
      3Ö    # Check for each sum whether it's divisible by 3
        P   # Check if all inner-most were divisible by 3 by taking the product
         O  # And check of many are truthy by taking the sum
            # (after which the result is output implicitly)

```

---
Tags: code-golf, game, counting
---


# Question
Title: Find the Needle in the Haystack (Robbers)
**This is part of a challenge. Go here for the cops' part.**

## The Robbers' Challenge

A cop's answer can be cracked by removing any subset of characters from the Haystack program, so that it outputs `Needle` instead of `Haystack` (while still being a valid submission in the same language). You don't have to find the exact same solution as the cop intended, as long as yours is valid by the above constraints.

If you manage this, post an answer with the solution, linking to the cop's answer, and leave a comment on the cop's answer linking back to yours.

The robber who cracks the most cop answers wins. Ties are broken by the sum of sizes of the cracked cop answers (in favour of the robber who cracks longer submissions).

Each cop answer can only be cracked once, and of course, you're not allowed to crack your own answer. If the cop's answer turns out to be invalid before or after being cracked, it is not counted towards the robber's score.

## Examples

Here are a couple of simple examples in different languages:

```
Ruby

Haystack: puts 1>0?"Haystack":"Needle"
Delete:        XXXXXXXXXXXXXXX
Needle:   puts "Needle"

Python 2

Haystack: print "kcatsyaHeldeeN"[-7::-1]
Delete:          XXXXXXXX        XX
Needle:   print "eldeeN"[::-1]

```

Note that the subset of removed characters doesn't have to be contiguous.

# Answer
> 11 votes
# JavaScript, 85 bytes (ES6)

Cracks Arnauld's answer

```
f=(k=b=x=35)=>x--?f(k*4853461&268435455):k&2?'N'+(k^12408877).toString(b):'Haystack'

```

### "Needle" demo

```
f=(k=b=x=35)=>x--?f(k*4853461&268435455):k&2?'N'+(k^12408877).toString(b):'Haystack'

console.log(f())
```

### Explanation

The original function was:

```
f=(k=b=x=35)=>x--?f(k*74837258394056219&268435455):k&2?'N'+(k^124038877).toString(b):'Haystack'

```

which is more readable as:

```
f = (k=b=x=35) => {
    if (x--) {
        return f(k*74837258394056219&268435455);
    } else {
        if (k&2) {
            return 'N'+(k^124038877).toString(b);
        } else {
            return 'Haystack';
        }
    }
}

```

Note that when `n=21625674`, then `n.toString(35)` is `'eedle'`.

The 35 in the input probably cannot be changed to a subset (because we want a base large enough to contain all the letters 'del', so we need a base that's at least 22). So the numbers to change are `74837258394056219`, `268435455`, and `124038877`. We want to replace them with numbers a, b, c, each formed with a subset of the digits of the original numbers, such that the function `g(k) = (k * a & b)`, starting with `k=35` and iterated 35 times, and then XORed with c, gives `21625674`.

For this one, after thinking a bit, as the lengths are small (the maximal `a` has length 17, `b` and `c` have length 9), I just used brute-force :-) Wrote a C++ program to generate all possible numbers `a`, `b`, `c` formed as subsets of the original numbers, iterate through all `a` and `b`, and check whether the required `c` was in the set. Runs in about 15 seconds, and the only output is `a=4853461`, `b=268435455`, `c=12408877` (turns out the number `b` doesn't need to be changed). I'm not sure whether there's a more clever way of inverting this function.

# Answer
> 5 votes
# Haystack, 82 bytes

Cracks HyperNeutrino's Answer

```
0\1-c\
/
?10F17+c8F+4+cd8F+3+c6-c1+c,c2+c8+c|
 0   \1++c,c|
F/c++2F8
c\8F+2+cd

```

Try it online!

# Answer
> 5 votes
# Brain-Flak, 96 bytes

Cracks Funky Computer Man's answer.

```
([((((()()())){}){}){}](()[()]({}([(((()()()){}))[]])[]({}({}()(((()(({}){}){}){}){}())))[]))())

```

Try it online!

This was a fun challenge.

The -24 at the beginning which converts `y` to `a` in the original is now used to convert `e` to `M`, which is then converted to `N` in place by changing the entire end loop to `())`. The first pushed letter `k` was changed to `e` simply by removing a push-pop that adds 6 to it. The rest mostly just fell into place, with some humorous missteps along the way (including one program whose output was `Meddle`).

Comparison of the two programs:

```
Haystack: ([((((()()())){}){}){}](()([()](()({}([((((()()()){})))[]])[]({}({})[{}]()({}((()(({}){}){}){}){}())))[][][][][][]))[]))(((()[]){}){({}[()()])}{})
Needle:   ([((((()()())){}){}){}](() [()]   ({}([ (((()()()){})) []])[]({}({}     ()(  ((()(({}){}){}){}){}())))[]              ))   ()  )

```

# Answer
> 5 votes
## Haskell

Cracks @Laikoni's answer.

```
s=map;hay=zipWith;a=head;h=s a.(hay(scanr id).s a<*>s(succ<$))$words"Haysta ayst ackH ays k ayst"

```

Try it online!

Original code:

```
hays=map;hay=zipWith;stack=head;h=stack{-
 hay.(hays.(stackany hay$or id).stack hay
<*>hays(sum$stack haystack<$>hay))-}$words
 "Haystack Hayst ackH aysta ckH aystac k"

```

replacing removed characters with underscores:

```
___s=map;hay=zipWith;__a__=head;h=s______
 _a_.(hay__(s__c_an_______r id).s____ _a_
<*>___s(su_____c________c_<$____))__$words
 "Haysta__ _ayst ackH ays__ _k_ ayst____"

```

How `Needle` is constructed: the string at the end of the code is split into words. The first char of each word is incremented as many times as there are characters in the word, e.g. `Haysta` -\> `H` plus 6 chars -\> `N`.

# Answer
> 5 votes
# Hexagony, 17 bytes, H.PWiz

```
];N@cl;e;;(\.s.;_
```

Try it online!

## Comparison with original:

```
];N.@cl;e@;;(\H/;ya;_.>s.;t//<._  original
];N @cl;e ;;(\       . s.;     _  modified

```

## Visualisation:

```
  ] ; N
 @ c l ;
e ; ; ( \
 . s . ;
  _ . .

```

## Explanation

Bonus marks - uses all 6 IPs and all but one of the cells!

The IP #0 starts by heading right along the black path into the `]`.
We then transition to IP #1, which heads along the red path, printing `N` with `N;` then wrapping back into the `]` again.
We then transition to IP #2, which heads along the blue path, storing `e` in the current memory cell, then along the green path, executing (with a reflection at `\`) `;;(;` which prints `ee`, decrements the memory cell from `e` to `d` then prints `d`.
The IP continues along the orange path, executing `Nl;se` which prints `l`, and stores `e` in the current memory cell. It continues along the brown path, printing the `e` with `;`. By this point we have already printed `Needle`, so the rest is just finishing. The IP stores `c`, then hits `]`.
We then transition to IP #3, which heads along the blue path, hitting `\`, bouncing into `_` which bounces into `]`.
We then transition to IP #4, which heads along the green path, bouncing on `_`, then `\` and branching to `]` (since `c` is positive).
Finally, we transition to IP #5, which stores `e` then exits with `@`.

# Answer
> 4 votes
# Python 2, 123 bytes

Cracks agtoever's Answer

```
import numpy
print "".join([dir(numpy)[int(i)][0] for i in numpy.poly1d([-143/2e1,-31,14,131,61,184])(numpy.arange(-3,3))])

```

repl.it

Comparison:

```
print "".join([dir(numpy)[int(i)][1-0] for i in numpy.poly1d([-1*1433/252e1,-3232/1920.,4026./72/2/3.,613/(6*4.)*1,-4723./1.8e2,-9763/120.,-2689/(-1+5*17.),1+138*.4*2])(numpy.arange(-12/3,13%9))])
print "".join([dir(numpy)[int(i)][  0] for i in numpy.poly1d([-1  43 /2  e1,-3    1    ,               1     4    ,       1         3 1   ,  6     1       ,1   8  4  ])(numpy.arange(-   3, 3  ))])

```

I had a lot of fun finding solutions that printed `Meedle` and `Needlf` by fitting a polynomial to the median of the indices of the numpy symbols that start with each of the letters in `Needle`. I then tried to find similar coefficients with subsets of the original program by hand, but I ended up having to resort to brute forcing one to find a valid solution.

# Answer
> 3 votes
## Hexagony, 19 bytes, Martin Ender

```
[@;(...e<l.a;./;N>;

```

Try it online!

### Comparison with original

```
H[@;(...e<l.a;./$.>;\sN;\ac.>).;;;._y
 [@;(...e<l.a;./   ;  N     >  ;

```

### Unfolded code

```
  [ @ ;
 ( . . .
e < l . a
 ; . / ;
  N > ;

```

So, I've never written anything in Hexagony, but I figured with only 37 bytes that I could come up with the crack. Martin, I hope you know I put *a lot* of time into trying to figure this out. :)

I may be incorrect, but I will explain what I *think* this code is doing:

The program starts off with `[`, which automatically moves to IP #5. This IP starts in the west corner, heading toward the `[` once again, which moves it to IP #4. From here, it executes `N;e` then heads to the southeast corner and executes `;`, bounces to the right for another `;` then wraps to `(` which decrements the current `e` to a `d`. It then continues (with a wrap) to `...;.` then bounces to the `l` and gets to the `[` one last time, moving to IP #3. It executes `;`, `>` redirects to the northwest to `.` then `<` redirects to the west, hitting `e`, wrapping to `;`, and terminating on the `@`.

Verbose version

```
[   We move to the previous instruction pointer (starting at the e and moving NE)
e   e is entered into the current memory cell
(   Decrements the memory cell to d
[   We move to the previous instruction pointer (starting at the N and moving NW)
N   N is entered into the current memory cell
;   Outputs N
e   e is entered into the current memory cell (IP now wraps to the SE corner)
;   Outputs e
/   Mirrors IP to the east
;   Outputs e (IP now wraps to ( on NW edge)
(   Decrements the memory cell to d
... No-ops (IP now wraps to ; on SW edge)
;   Outputs d
.   No-op
/   Mirrors IP to the NW
l   l is entered into the current memory cell
.   No-op
[   We move to the previous instruction pointer (starting at the ; and moving west)
;   Outputs l
>   Redirects the IP NW
.   No-op
<   Redirects the IP west
e   e is entered into the current memory cell (IP now wraps to ; on the NE corner)
;   Outputs e
@   Terminates the program
```

I am so glad that you used a normal hexagon size for the Needle program; I was checking size 19 programs (for a length-3 side hexagon) when I realized you could remove any number of characters and it would automatically fill the hexagon with `.`s at the end, which would make it dramatically more difficult to crack. As it is, Hexagony is an evil language for this challenge because (mostly) any character that is removed changes the whole execution path of the program. That being said, I enjoyed trying to come up with this, even if I did end up brute forcing it at the end. :)

# Answer
> 2 votes
# Javascript, 91 bytes

```
_=>(+{}+[])[+[]]+([][[]]+[])[3]+([][[]]+[])[3]+([][[]]+[])[2]+(![]+['t'])[2]+([][[]]+[])[3]

```

Cracks this. It actually was fun.

```
let f =

_=>(+{}+[])[+[]]+([][[]]+[])[3]+([][[]]+[])[3]+([][[]]+[])[2]+(![]+['t'])[2]+([][[]]+[])[3]

console.log(f())
```

# Answer
> 2 votes
# Jelly, 14 bytes

Cracks Jonathan Allan's Answer

```
“¡#ɦṢÞɠ»ḟ“¡pṄ»

```

Try it online!

Comparison:

```
“¿ọ⁽ṅ*FỊ⁼g£¡#!ʋzoɦṪ£ṢÞḲÐɠ`”m3⁾“»jVḟ“¡!pṄ»
“          ¡#    ɦ  ṢÞ  ɠ      »  ḟ“¡ pṄ»

```

I used `œc` to iterate through various subsets of the literal strings, used `tr -d` for each possible filter, and `grep`ed for Needle. Using the assumption that none of the used characters in the first string were used in the answer let it find an answer in under 15 seconds.

# Answer
> 2 votes
# Python 2, 73 bytes

Cracks user71546's Answer.

```
a,b,s=2707385038437,0b10000000,""
while a>0:
 s=chr(a%b)+s
 a//=b
print s

```

Try it online!

Solved with this program.

# Answer
> 2 votes
# Java (OpenJDK 8), 191 bytes

Cracks Luke Steven's answer

```
String d(){int h=3905055,m=55,s=15443;String d="0"+h*2+""+m*20+""+s*7,x="",y;for(int g=0;g<d.length();g+=3){y="";for(int e=0;e<3;e++)y+=d.charAt(e+g);x+=(char)Integer.parseInt(y);}return x;}

```

Try it online!

Deleted chars:

```
int h=3609000-5055+911,m=557558,s=15441301-157*10000
       xx  xxx    xxxx     xxxx       x xxxxxxxxxxxx

```

This makes `d` evaluate to `078101101100108101`, which spells `Needle`.

# Answer
> 2 votes
# Ruby, 149 bytes

Cracks this: https://codegolf.stackexchange.com/a/144790/74216

Module was quite small, so I wrote a multi-threaded birthday thing and hoped for the best.

Edit: And after that found an even shorter answer.

```
x='hxDKFQOoqJLuVNW'
s="n=x.to_i 36;x.bytjs.jach_cons(3){|a,b,c|n+=n*b%c;n*=a^b};puts n%8675309==1388649 ?'Njjdlj':'Haystack'"
eval s.tr ?j,s.size.chr

```

Try it online!

Changes:

```
x='yGwztsPXhxDkBKlCYdFjQnpUROfoHvqmTgbaJSLcEiZrIAuMVNW'
x='        hxD  K    F Q    O o  q     J L       u VNW'

# and here's some more variants for extra pwnage:
x=' G  tsPx     KlCYd  Qn U   o v mT  a SLc    I u  NW'
x='  w  s    D BKl  dF QnpU O        ba SLcEiZrI  MV  '
x='yGwz s Xh Dk K C  F  npU O  Hvq   b   L    rIAu V W'

```

# Answer
> 2 votes
# dc, 34 bytes

```
93 9 2*+432212+ 47*4242160 7 2++*P

```

Cracks this. TIO.

I started by getting the numerical representation of Haystack (5215583380252484459) and Needle (86197399743589). Next, I did a factorisation of the latter, which is 47\*432323\*4242169. From this, it was quite easy to reconstruct those numbers.

Marking the characters used:

```
6 93 3 9 2 2**+*+483622 1 2 3 3*+3*+89 47*+*+3 5 2* 269 158 9**107 97*2 4*++2 3 3*+42 14 2**+*+5*+5 2148 1 6 2*+*+68262 5 280 7 2 3 3*+5 2**+*+*+*+P
  XXX  XXX   XX  X X XX X X     X     XXXX                              X   X      XX X                    X                XXXXX     X     XX     X

```

# Answer
> 1 votes
# Java (OpenJDK 8), 151 bytes

Cracks Kevin Cruijssen's Answer

```
v->{String h="H";int x=7;return new String(new byte[]{(byte)((-~-~-~-~-~-~1^x++*x)+15),new Byte("10"+h.length())})+new StringBuffer("elde").reverse();}

```

Try it online!

Comparison:

```
v->{String h="Haystack";int x=-7;return x<0?h:new String(new java.math.BigInteger(new byte[]{(byte)((~-~-~-~-~-~-~-~-~-~1^-x++*x)+151),new Byte("2"+"1+\"0+\"".length()+(x=h.length()*4/x)+"-x-7")}).toByteArray())+(new StringBuffer("hidden".substring(++x%3^4,--x-x--).replaceFirst("dd","e"+(char)(x*211%+93))).reverse());}
v->{String h="H       ";int x= 7;return       new String(                         new byte[]{(byte)(( -~-~-~-~-~-~      1^ x++*x)+15 ),new Byte("    1   0  "          +   h.length()    )        })               + new StringBuffer("    e                                 l          d    e"      )             .reverse() ;}

```

I feel like the last part wasn't intended.

# Answer
> 1 votes
# Brain-Flak, 102 bytes

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

```

Cracks H.PWiz's answer.

Try it online!

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

```

# Answer
> 1 votes
# Ly, 21 bytes

```
(78)"e"sl(100)"l"l&o;

```

Try it online!

Cracks LyricLy's answer.

# Answer
> 1 votes
# Java by Johnathan S.

```
import java.util.*;interface Main{static void main(String[]args){Stack<Hay>s=new Stack();s.add(new Needle());System.out.println(s.get(s.indexOf(new Hay())+1).a);}}class Needle extends Hay{{a="Needle";}}class Hay{String a="Haystack";public boolean equals(Object o){return getClass().equals(o.getClass());}}

```

TiO

Simply remove the loop that adds the Hay and nothing will be left on the stack but the needle.

# Answer
> 1 votes
# Vyxal `o`, cracks emanresu A's answer

```
‛₍∞

```

Try it Online!

Simply pushes the string `Needle` in compressed form, then prints it implicitly.

Characters removed:

```
‛Ha:₍₴Cv∑∑Ṙ⌊√‹½⇩⇩²C:₴«•∞yλ;ß4ġ∆Ė_□∴9«øc:3Ẏ$4ȯ∇ppĖ5e
 XXX XXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXX

```

# Answer
> 0 votes
# Pyth, 21 bytes

```
Kr."Dn2û"2+Kr."EL8"Z

```

cracks this.

Try it online!

# Answer
> 0 votes
# T-SQL by phroureo, 757 bytes

```
seleCT 'Needle'

```

Somehow I don't think that was the intended solution. Uses the characters surrounded by `{}`:

```
create table a(l int,c int)
in{se}rt into a va{l}u{e}s (1,10),(2,1),(3,8),(4,0)
go
;CREATE FUN{CT}ION b(@ varchar(max)) returns varchar(max) as
begin return{ '}char('+@+'),'''','end
go
;CREATE FU{N}CTION h(@ varchar(max),@a varchar(max), @b varchar(max), @c varchar(max), @d varchar(max), @e varchar(max), @f varchar(max), @g varchar(max), @h varchar(max))
r{e}turns varchar(max) as
b{e}gin
return replace(replace(replace(replace(@,@a,@b),@c,@d),@e,@f),@g,@h)
end
{d}ec{l}ar{e} @x varchar(max),@ int=1,@y varchar(99)={'}'
,@D varchar(4)='Ha',@O varchar(4)='ys'
,@T varchar(3)='ta',@A varchar(4)='ck'
WHILE @<=4
BEGIN
set @y+=(SELECT dbo.b(c+100)from a where l=@)+' '
set @+=1
END
SELECT @x='select
left(dbo.h('''+@D+@O+@T+@A+''','+ left(@y,len(@y)-1) +'),char(56))'
execute(@x)

```

# Answer
> 0 votes
## PHP

Cracks Titus answer

```
for($i=1;$c=H_aNyesetdalcek[$i+=2];)echo$c;

```

Try it online

---
Tags: code-golf, source-layout, cops-and-robbers
---


title: Hide the Needle in the Haystack (Cops)

text:
# Question
Title: Hide the Needle in the Haystack (Cops)
**This is part of a challenge. Go here for the robbers' part.**

## The Cops' Challenge

You should write a program or function in a language of your choice, which outputs the string `Haystack`. However, it must be possible to remove some subset of characters from your program (without reordering the rest), such that the resulting string is *also* a valid program in the same language, which prints `Needle` instead. Both programs/functions may optionally print a single trailing newline (independently of each other), but nothing else. Output is case sensitive and must follow the exact casing provided.

Your goal, of course, is to hide the "needle" very well. But note that your submission can be cracked with *any* valid solution, not just the one you intended.

Please include in your answer:

* The language (and version if relevant) of your submission.
* The size of the Haystack program in bytes.
* The Haystack program itself.
* The output method if it's not STDOUT.
* If possible, a link to an online interpreter/compiler for your chosen language.

Your submission may be either a program or function, but not a snippet and you must not assume a REPL environment. You must not take any input, and you may output via STDOUT, function return value or function (out) parameter.

Both programs/functions have to complete within 5 seconds on a reasonable desktop machine and need to be deterministic. You must not use built-ins for hashing, encryption or random number generation (even if you seed the random number generator to a fixed value).

In the interest of fairness, there must be a freely available interpreter or compiler for your chosen language.

An answer is cracked if the Needle program is found. If your answer has not been cracked for 7 days, you may reveal the intended Needle program in your answer, which renders your submission safe. As long as you don't reveal your solution, it may still be cracked by robbers, even if the 7 days have already passed. The shortest *safe* Haystack program (measured in bytes) wins.

## Examples

Here are a couple of simple examples in different languages:

```
Ruby

Haystack: puts 1>0?"Haystack":"Needle"
Delete:        XXXXXXXXXXXXXXX
Needle:   puts "Needle"

Python 2

Haystack: print "kcatsyaHeldeeN"[-7::-1]
Delete:          XXXXXXXX        XX
Needle:   print "eldeeN"[::-1]

```

Note that the subset of removed characters doesn't have to be contiguous.

## Uncracked Submissions

```
<script>site = 'meta.codegolf'; postID = 5686; isAnswer = false; QUESTION_ID = 144600;</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```

# Answer
> 16 votes
# Haystack, 84 bytes, Cracked

```
0\\1-c\
//
?10F17+c8F+4+cd8F+3+c6-c1+c,c2+c8+c|
 0   \1++c,c|
F/c++2F8
c\8F+2+cd

```

Try it online!

This looks (to me) rather convoluted but if you find the right subset it's a bit too easy... oh well, just to get us started :P

# Answer
> 12 votes
## Hexagony, 37 bytes

```
H[@;(...e<l.a;./$.>;\sN;\ac.>).;;;._y

```

Try it online!

Just my obligatory Hexagony entry...

For convenience, here is the unfolded code:

```
   H [ @ ;
  ( . . . e
 < l . a ; .
/ $ . > ; \ s
 N ; \ a c .
  > ) . ; ;
   ; . _ y

```

How this works:

The program starts off with `H`, then we move to IP #5. This IP starts in the west corner, bouncing and wrapping around while executing (in effect) `;a;y;s;` (so we've printed `Hays`). Then `s` gets incremented to a `t` by `)` and printed, then we pass through `Ne...(c` before getting to `a;c;` (still bouncing around a small section of the hexagon). The program hits the `_`, reflects up through `\` to `l` which gets decremented to a `k` by `(`, which passes through another `\` before being printed and the program terminates on the `@`.

Verbose version

```
H   H is entered into the current memory cell
[   We move to the previous instruction pointer (starting at the / and moving NE)
/   No-op
<   Mirrors the IP back to south-west
/   No-op (IP now wraps to the NE corner)
;   Outputs H
.   No-op
a   a is entered into the current memory cell
>   Mirrors the IP back to north-east
a   a is entered into the current memory cell
.   No-op
;   Outputs a (IP now wraps SE corner)
y   y is entered into the current memory cell
;   Outputs y
.   No-op
s   s is entered into the current memory cell (IP now wraps SW corner)
;   Outputs s
)   Increments the memory cell to t
\   Mirrors the IP west
;   Outputs t
N   N is entered into the current memory cell (IP now wraps to e)
e   e is entered into the current memory cell
... No-ops
(   Decrements the memory cell to d (IP now wraps to . on SE edge)
.   No-op
c   c is entered into the current memory cell
a   a is entered into the current memory cell
\   Mirrors the IP north-east
>   Redirects the IP east
;   Outputs a
\   Mirrors the IP south-west
c   c is entered into the current memory cell
;   Outputs c
_   Mirrors the IP north-west
.\. No-ops
l   l is entered into the current memory cell
(   Decrements the memory cell to k (IP now wraps to . on SE edge)
.\  No-ops
;   Outputs k
.   No-op
@   Terminates the program
```

# Answer
> 10 votes
# Brain-Flak, 146 bytes (Cracked)

```
([((((()()())){}){}){}](()([()](()({}([((((()()()){})))[]])[]({}({})[{}]()({}((()(({}){}){}){}){}())))[][][][][][]))[]))(((()[]){}){({}[()()])}{})

```

Try it online!

## Intended solution, 80 bytes

```
([((((()()())){}){}){}](()([()](()({}([((((()()()){})))[]])[]({}({})[{}]()({}((()(({}){}){}){}){}())))[][][][][][]))[]))(((()[]){}){({}[()()])}{})
( ((   )(                  [(  (( (         )()()){})) []]   ({}(  )    ( (  ( ()(({}){}){}){}){}())))            ))    (((()[]){}){({}[()  ])}{})

```

# Answer
> 9 votes
# Haskell, 168 bytes (Cracked by nimi)

```
hays=map;hay=zipWith;stack=head;h=stack{-
 hay.(hays.(stackany hay$or id).stack hay
<*>hays(sum$stack haystack<$>hay))-}$words
 "Haystack Hayst ackH aysta ckH aystac k"

```

Try it online! Evaluating the identifier `h` returns the string `"Haystack"`, after some deletions `h` yields `"Needle"`.

# Answer
> 8 votes
# JavaScript, 95 bytes (ES6), Cracked

A function returning a string.

```
f=(k=b=x=35)=>x--?f(k*74837258394056219&268435455):k&2?'N'+(k^124038877).toString(b):'Haystack'

```

### "Haystack" demo

```
f=(k=b=x=35)=>x--?f(k*74837258394056219&268435455):k&2?'N'+(k^124038877).toString(b):'Haystack'

console.log(f())
```

# Answer
> 4 votes
# Jelly, 41 bytes (Cracked)

```
“¿ọ⁽ṅ*FỊ⁼g£¡#!ʋzoɦṪ£ṢÞḲÐɠ`”m3⁾“»jVḟ“¡!pṄ»

```

**Try it online!**

Happy hunting!

# Answer
> 4 votes
# Hexagony, 32 bytes. Cracked

I couldn't solve Martin's, so I'm posting my own.

```
];N.@cl;e@;;(\H/;ya;_.>s.;t//<._

```

Try it online!

Here it is formatted:

```
   ] ; N .
  @ c l ; e
 @ ; ; ( \ H
/ ; y a ; _ .
 > s . ; t /
  / < . _ .
   . . . .

```

My aim with this was for both solutions to use as many IPs as possible, I got 6 for **Needle** and only 5 for **Haystack**.

# Answer
> 3 votes
# Pyth, 44 bytes (Cracked)

```
Kr."Dn2û"2sf!/+rrK2 2r."EL8"2Tr."AhÐP®Z"2

```

Try it here.

# Answer
> 3 votes
# Java (OpenJDK 8), 226 217 bytes (Cracked)

First ever code golf, probably very easy but it was a fun challenge!

```
String d(){int h=3609000-5055+911,m=557558,s=15441301-157*10000;String d="0"+h*2+""+m*20+""+s*7,x="",y;for(int g=0;g<d.length();g+=3){y="";for(int e=0;e<3;e++)y+=d.charAt(e+g);x+=(char)Integer.parseInt(y);}return x;}

```

Try it online!

# Answer
> 3 votes
# dc, 148 bytes (Cracked)

```
6 93 3 9 2 2**+*+483622 1 2 3 3*+3*+89 47*+*+3 5 2* 269 158 9**107 97*2 4*++2 3 3*+42 14 2**+*+5*+5 2148 1 6 2*+*+68262 5 280 7 2 3 3*+5 2**+*+*+*+P

```

Try it online!

It is rather simple, but I hope it will be at least a little fun to solve :з

# Answer
> 2 votes
# Brain-Flak, 188 bytes (Cracked)

I only just saw Funky Computer Man's answer As I posted this.

It is somewhat obfuscated.

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

```

Try it online!

### Intended solution, 96 bytes:

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

```

Try it online!

# Answer
> 2 votes
# JavaScript, 119 bytes (ES6), Cracked

A function returning a string. Quite long and not so hard, but hopefully fun.

```
_=>(+{}+['H'])[+[3]]+(+[][[]]+[])[+!!3]+(+[][[]]+['y'])[3]+(+[][[]]+['s'])[-~2]+(~![]+['t'])[2]+(+[][[]]+[])[+!!3]+'ck'

```

### "Haystack" demo

```
let f =

_=>(+{}+['H'])[+[3]]+(+[][[]]+[])[+!!3]+(+[][[]]+['y'])[3]+(+[][[]]+['s'])[-~2]+(~![]+['t'])[2]+(+[][[]]+[])[+!!3]+'ck'

console.log(f())
```

# Answer
> 2 votes
## Python 2.7.10 with Numpy 1.12.1, ~~208~~ 209 bytes (cracked)

It appears that there is a Needle *and* a Haystack in Numpy! Here is the Haystack; see if you can find the Needle. I hope you have as much fun searching for the Needle as I had hiding it.

```
import numpy
print "".join([dir(numpy)[int(i)][1-0] for i in numpy.poly1d([-1*1433/252e1,-3232/1920.,4026./72/2/3.,613/(6*4.)*1,-4723./1.8e2,-9763/120.,-2689/(-1+5*17.),1+138*.4*2])(numpy.arange(-12/3,13%9))])

```

It outputs as specified:

```
Haystack

```

You can repl.it.

# Answer
> 2 votes
## Python 2.7.2, 103 / 117 bytes, Cracked

**Function Version (117 bytes):**

```
def e():
 a,b,s=20070763850923833476353301471991752,0b1010100010010011,""
 while a>0:
  s=chr(a%b)+s
  a//=b
 print s

```

**Program Version (103 bytes):**

```
a,b,s=20070763850923833476353301471991752,0b1010100010010011,""
while a>0:
 s=chr(a%b)+s
 a//=b
print s

```

This should print `Haystack` well. Tested on Python Fiddle.

Btw this is the first attempt.

Not sure if the program version is counted as a snippet, so I put both versions here.

# Answer
> 2 votes
# Java 8, 321 bytes, Cracked

```
v->{String h="Haystack";int x=-7;return x<0?h:new String(new java.math.BigInteger(new byte[]{(byte)((~-~-~-~-~-~-~-~-~-~1^-x++*x)+151),new Byte("2"+"1+\"0+\"".length()+(x=h.length()*4/x)+"-x-7")}).toByteArray())+(new StringBuffer("hidden".substring(++x%3^4,--x-x--).replaceFirst("dd","e"+(char)(x*211%+93))).reverse());}

```

Try it here.

More readable:

```
v->{
  String h="Haystack";
  int x=-7;
  return x<0?
          h
         :
          new String(new java.math.BigInteger(new byte[]{
            (byte)((~-~-~-~-~-~-~-~-~-~1^-x++*x)+151),
            new Byte("2"+"1+\"0+\"".length()+(x=h.length()*4/x)+"-x-7")
          }).toByteArray())
          +(new StringBuffer("hidden".substring(++x%3^4,--x-x--)
             .replaceFirst("dd","e"+(char)(x*211%+93))
            ).reverse());
}

```

Not sure if it's too long/hard.. Then again, Java in general is pretty long to begin with, so hiding the 'Needle' properly of course increases the byte-count quite a bit..
If no one cracks it, I'll add some spoiler-tips later on.

# Answer
> 2 votes
# Ruby, 185 bytes, cracked by cab404

```
x='yGwztsPXhxDkBKlCYdFjQnpUROfoHvqmTgbaJSLcEiZrIAuMVNW'
s="n=x.to_i 36;x.bytjs.jach_cons(3){|a,b,c|n+=n*b%c;n*=a^b};puts n%8675309==1388649 ?'Njjdlj':'Haystack'"
eval s.tr ?j,s.size.chr

```

Try it online!

I'll try to come up with something sneaky, but for now here's a try at "simple but obnoxious."

# Answer
> 2 votes
# T-SQL, 757 characters CRACKED

Apologies for deleting my previous answer--I edited it too many times as I obfuscated, and didn't want to give anything away. :)

In any case, obfuscating in SQL is a bit difficult, unless you want to do crazy stuff like this, and I wasn't that invested.

Also, I unabashedly do not apologize for naming my variables after Dota.

SQL Fiddle

```
create table a(l int,c int)
insert into a values (1,10),(2,1),(3,8),(4,0)
go
;CREATE FUNCTION b(@ varchar(max)) returns varchar(max) as
begin return 'char('+@+'),'''','end
go
;CREATE FUNCTION h(@ varchar(max),@a varchar(max), @b varchar(max), @c varchar(max), @d varchar(max), @e varchar(max), @f varchar(max), @g varchar(max), @h varchar(max))
returns varchar(max) as
begin
return replace(replace(replace(replace(@,@a,@b),@c,@d),@e,@f),@g,@h)
end
declare @x varchar(max),@ int=1,@y varchar(99)=''
,@D varchar(4)='Ha',@O varchar(4)='ys'
,@T varchar(3)='ta',@A varchar(4)='ck'
WHILE @<=4
BEGIN
set @y+=(SELECT dbo.b(c+100)from a where l=@)+' '
set @+=1
END
SELECT @x='select
left(dbo.h('''+@D+@O+@T+@A+''','+ left(@y,len(@y)-1) +'),char(56))'
execute(@x)

```

If this is the easiest answer in this thread, you're probably right. :P It's hard to trick SQL.

# Answer
> 1 votes
# Ly, 40 bytes, cracked

```
(78)"e"&p"Ha"s"yst"l"ck"&o(100)"l"l'&'o;

```

Try it online!

Oh boy, another Ly CNR submission. These haven't worked very well historically (possibly due to me and not the language), ~~but we'll see how this fares~~ and today is no exception.

Solution:

> `(78)"e"sl(100)"l"l&o;`, remove `XXXXXX XXXXX XXXXXX X X` with seven leading spaces

# Answer
> 1 votes
# Java, 345 bytes, Cracked

```
import java.util.*;interface Main{static void main(String[]args){Stack<Hay>s=new Stack();s.add(new Needle());for(int i=0;i<1000;i++)s.add(new Hay());System.out.println(s.get(s.indexOf(new Hay())+1).a);}}class Needle extends Hay{{a="Needle";}}class Hay{String a="Haystack";public boolean equals(Object o){return getClass().equals(o.getClass());}}

```

Try it online!

Really long and probably easy to crack, but at least it's got a `Stack<Hay>`!

# Answer
> 1 votes
# Vyxal `o`, 51 bytes

```
‛Ha:₍₴Cv∑∑Ṙ⌊√‹½⇩⇩²C:₴«•∞yλ;ß4ġ∆Ė_□∴9«øc:3Ẏ$4ȯ∇ppĖ5e

```

Try it Online!

Have fun!

So, here's an explanation of the code:

```
‛Ha                                      # Push 'ha'
   :₍                                    # Duplicate and parallel apply...
     ₴                                   # Flatprint
      C                                  # And charcode, wrapped into a list
       v∑∑Ṙ                              # Get sum, concatenate, reverse (`961aH`)
           ⌊√‹½                          # Intify, square root, decrement and halve (15)
               ⇩⇩²C                      # Subtract 4, convert to char, which happens to be y
                   :₴                    # Dupe and flatprint.
                     «...«               # Push a string, specially chosen, see below
                          øc             # Compress
                            :3Ẏ$4ȯ∇pp    # Insert ToS (`y`) at char 3
                                     Ė   # Evaluate
                                      5e # Every fifth character

```

So, I realised I could use the compressed string `‛₍∞` as the needle program. I could easily sneak in a  and , but  was proving to be a problem. Eventually, I managed to construct a compressed string that contained  and `y`, and had the property that if you took every fifth character, you got 'stack'.

So yeah, this was tricky.

# Answer
> 1 votes
# Vyxal, 44 bytes

```
17SǏ⌊0»¹∇ḃF2»*»∷J∇Y.ḊṖ¼ḭ¦]uy»S4ẇṫ½Y⌊$oḢJCṅĖǐ

```

Try it Online!

# Answer
> 0 votes
# TI-BASIC, 119 bytes (Safe)

Output stored in `Ans`.

```
"TIBASIC→Str1
length(Ans→X
Str1
For(I,X,2(7-4not(X-1
Ans+sub("ACDEHKLNSTY",inString("ABCDEFGHIJK",sub("KCBADAEDJDHIGF",1+remainder(11I-1,14),1)),1
End
sub(Ans,1+X,length(Ans)-X

```

## Solution

Remove characters from `Str1` to give it a length of 1.

```
"C→Str1
length(Ans→X
Str1
For(I,X,2(7-4not(X-1
Ans+sub("ACDEHKLNSTY",inString("ABCDEFGHIJK",sub("KCBADAEDJDHIGF",1+remainder(11I-1,14),1)),1
End
sub(Ans,1+X,length(Ans)-X

```

# Answer
> 0 votes
# PHP, 44 bytes, Cracked

fairly easy to crack; but I like it.

```
for($i=~1;$c=H_aNyesetdalcek[$i+=2];)echo$c;

```

Run with `-nr` or try it online.

# Answer
> 0 votes
# Aceto, 154 bytes (Safe)

```
              27\'dNU   QJi9MLJ€{{x(}]J{'!o∑€xiDQxsJ(]sicpicp1.2sJJicp90I.2+D/edxi-'>xd80J0IJicx'NIx5sJsJidcpIcpL7sssJicpei7+ UUdJicpLI7sJicpx'p\p9*coJcU'p+\p
```

Try it online!

> 'N'ed'd80J0IJic'eUpppppp Try it online!

```
Explanation:
<space>*2 - Two spaces for the hilbert curve to work right
'N pushes 'N' onto the stack
'e pushes 'e'
d duplicates it
'd pushes d
80 pushes 8, 0
J concats top two values
0I pushes 0, pops, increments, pushes back on, net effect: pushes 1
J concats to '108'
i converts to integer
c pops and pushes ascii equiv on stack
'e pushes 'e' (again)
U reverses the stack
and the p's print out the stack

```

# Answer
> 0 votes
# Rattle, 55 bytes

```
Haystack&Needl|Ip0=2+(1*2)!Ps[bg0*3b^](`+5);$b|1,%(?3b)

```

Try it Online!

This isn't terribly difficult but it's not trivial either (note that "Needle" is missing the last "e" near the beginning of the code).

Hint: the Needle program will not have a trailing newline, while the Haystack program does.

---
Tags: code-golf, source-layout, cops-and-robbers
---


# Question
Title: Complement a POSIX Extended Regular Expression
Given a POSIX Extended Regular Expression as input, output its complement (also a POSIX ERE). If the given regular expression matches a string, its complement should not match it, and the regex: `(regex given)|(complement)` should match any string. In other words, negate the regex.

The regex for format input and for output, POSIX ERE, is basically regex without character classes, lookarounds, backreferences, etc. You can assume that we only care about ASCII characters. Also, assume that character classes do not contain `-` for use as ranges (no `[a-d]` as input; instead, the input would be `[abcd]`). Further assume that `?` and `+` and `{}` will not be used in the input as metacharacters. `x?` will be shown with `x|` and `x+` by `xx*` where x is an arbitrary regular expression. The variations of `{m,n}` will be similarly written out (e.g.: instead of `x{1,4}`, you'll get `x|xx|xxx|xxxx`).

Sample Input:

```
^([helo][world])([helo][world])*$

```

Possible Output (Thanks Peter Taylor):

```
^(([helo]([world][helo])*)?$|([helo][world])*[^helo]|[helo]([world][helo])*[^world])

```

Please post a few sample Input/Outputs

# Answer
# JavaScript, 1563 bytes

```
m=>`^${((l,n={s:{[e(l[0])]:""}})=>((t=s=>n[x=e(s)]=n[x]||(n[x]={},r.reduce(((r,o,c)=>(c=l[2](s)(o),t(c),r[x=e(c)]=(r[x]||"[]")[$](0,-1)+("\\"==o||"]"==o?"\\":"")+o+"]",l[1](s)||(r.e=""),r)),{})))(l[0]),(g=Object.keys)(n)[h]((e=>"s"!=e&&(c=n[e],d=c[e],delete c[e],delete n[e],g(n)[h]((l=>(s=n[l][e])!={}.x&&delete n[l][e]&&g(c)[h]((e=>(o=s+(d?`(${d})*`:"")+c[e],n[l][e]=n[l][e]!={}.x?`(${n[l][e]}|${o})`:o)))))))),n.s.e||"[]"))((a=e=>e===e+""?e?[0,e=>1==e,l=>t=>[t==e?1:2,2,2][l]]:[0,e=>!e,e=>e=>1]:[([e])=>[0,l=>!l||l.some((l=>e[1](l))),t=>r=>l((t||[e[0]]).flatMap((l=>[x=e[2](l)(r),...e[1](x)?[e[0]]:[]])))],e=>[e[h]((e=>e[0])),l=>l.some(((l,t)=>e[t][1](l))),l=>t=>l[h](((l,r)=>e[r][2](l)(t)))],([e,t])=>[[e[0],e[1](e[0])?[t[0]]:[]],e=>e[1].some((e=>t[1](e))),r=>s=>[x=e[2](r[0])(s),l([...e[1](x)?[t[0]]:[],...r[1][h]((e=>t[2](e)(s)))])]],l=>[0,e=>1==e,l=>t=>[e[1].includes(t)?1:2,2,2][l]]][e[0]](e[1][h](a)))((f=e=>e.length?e.reduce(((e,l)=>[2,[e,l]])):"")(m[$="slice"](1,-1).split(/(\\.|[^\\])/).filter((e=>e)).reverse(e=JSON.stringify,l=l=>[...new Set(l[h](e))].sort()[h](JSON.parse),r=[...Array(95)][h](((e,l)=>String.fromCharCode(l+32))),h="map")[u="reduceRight"](p=(e,l,t,s)=>e&&{[l]:t=>[...e,l[$](-1)],".":l=>[...e,[3,r]],"*":l=>e.concat([[0,[e.pop()]]]),"[":l=>[...e,((e,l)=>[3,e?r.filter((e=>!l.includes(e))):l])(n="^"==s[t-1],s.splice(s.lastIndexOf("]"),s.length)[$](1,-n||{}.x)[h]((e=>e[$](-1))))],")":l=>(i=e,0),"(":l=>[...e,(s[u](p,[]),[1,i.reduce((([e,...l],t)=>1==t?[[],e,...l]:[[...e,t],...l]),[[]])[h](f)])],"|":l=>[...e,1]}[s.pop()](),[]))))}$`

```

Try it online!

## Input/Output Examples

The challenge was to golf the source, not the output ¯\\\_(ツ)\_/¯

```
Input: ^([helo][world])([helo][world])*$
Output: ^(((((((((|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo])|[ehlo][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ehlo])|[ehlo][dlorw][ehlo][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ehlo][dlorw][ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)|[ehlo][dlorw][ehlo][dlorw][ehlo](|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*))|[ehlo][dlorw][ehlo][dlorw][ehlo][dlorw]([ehlo][dlorw])*([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdfgijkmnpqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*|[ehlo](|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcefghijkmnpqstuvxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)))$

Input: ^.*$
Output: ^[]$ # Empty character set matches nothing

Input: ^[]$
Output: ^(|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)$

Input: ^(|[ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~]([ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\\]^_`abcdefghijklmnopqrstuvwxyz{|}~])*)$
Output: ^[]$

```

## ~~Ungolfed~~ Less Golfed

```
let input = "^([helo][world])([helo][world])*$"

const star = 0
const union = 1
const concat = 2
const group = 3
const charset = [...Array(95)].map((_, i) => String.fromCharCode(i + 32));

input = `.*${input}.*`.replace(/\.\*\^|\$\.\*/g, "");

const makeConcat = x => x.length ? x.reduce((a, b) => [concat, [a, b]]) : "";

const regex = makeConcat(input
  .split(/(\\.|[^\\])/)
  .filter(x => x)
  .reverse()
  .reduceRight(_parseRegex = (acc, char, i, arr) => (
    acc && {
      [char]: _ => [...acc, char.slice(-1)],
      ".": _ => [...acc, [group, charset]],
      "*": _ => acc.concat([[star, [acc.pop()]]]),
      "[": _ => [...acc, ((i, a) =>
        [group, i ? charset.filter(x => !a.includes(x)) : a]
      )(
        invert = arr[i - 1] == "^",
        arr
          .splice(arr.lastIndexOf("]"), arr.length)
          .slice(1, -invert || {}.x)
          .map(x => x.slice(-1))
      )],
      ")": _ => (result = acc, null),
      "(": _ => [...acc, (
        arr.reduceRight(_parseRegex, []),
        [union, result.reduce(([a, ...b], char) => (
          char == union ? [[], a, ...b] : [[...a, char], ...b]
        ), [[]]).map(makeConcat)]
      )],
      "|": _ => [...acc, union],
    }[arr.pop()]()
  ), []))

const str = JSON.stringify;
const set = x => [...new Set(x.map(str))].sort().map(JSON.parse)

const initial = 0;
const accept = 1;
const next = 2;

const dfa = (regexToDfa = re =>
  re === re + ""
    ? re
      ? [0, x => x == 1, x => c => [c == re ? 1 : 2, 2, 2][x]]
      : [0, x => !x, x => c => 1]
    : [
      // star
      ([sub]) => [
        0,
        state => !state || state.some(substate => sub[accept](substate)),
        state => char => set((state || [sub[initial]]).flatMap(substate => [
          x = sub[next](substate)(char),
          ...sub[accept](x) ? [sub[initial]] : []
        ]))
      ],
      // union
      subs => [
        subs.map(sub => sub[initial]),
        state => state.some((substate, i) => subs[i][accept](substate)),
        state => char => state.map((substate, i) => subs[i][next](substate)(char)),
      ],
      // concat
      ([a, b]) => [
        [a[initial], a[accept](a[initial]) ? [b[initial]] : []],
        state => state[1].some(x => b[accept](x)),
        state => char =>
          [
            x = a[next](state[0])(char),
            set([
              ...a[accept](x) ? [b[initial]] : [],
              ...state[1].map(substate => b[next](substate)(char))
            ])
          ]
      ],
      // group
      _ => [
        0,
        state => state === 1,
        state => char => [re[1].includes(char) ? 1 : 2, 2, 2][state],
      ]
    ][re[0]](re[1].map(regexToDfa))
)(regex)

const testDfa = i => dfa[accept]([...i].reduce((a, b) => dfa[next](a)(b), dfa[initial]))

const invertDfa = dfa => [dfa[initial], x => !dfa[accept](x), dfa[next]]

const dfaToString = (dfa, paths = { s: { [str(dfa[initial])]: "" } }) =>
(
  (visitState = (state) => paths[x = str(state)] = paths[x] || (paths[x] = {},
    charset.reduce((obj, char, nextState) => (
      nextState = dfa[next](state)(char),
      visitState(nextState),
      obj[x = str(nextState)] = (obj[x] || "[]").slice(0, -1) + (char == "\\" || char == "]" ? "\\" : "") + char + "]",
      dfa[accept](state) && (obj.e = ""),
      obj
    ), {})
  ))(dfa[initial]),
  Object.keys(paths).map(removeState => removeState != "s" && (
    obj = paths[removeState],
    selfPath = obj[removeState],
    delete obj[removeState],
    delete paths[removeState],
    Object.keys(paths).map(a => (
      initialPath = paths[a][removeState]) !== {}.x &&
      delete paths[a][removeState] &&
      Object.keys(obj).map(b => (
        path = initialPath + (selfPath ? `(${selfPath})*` : "") + obj[b],
        paths[a][b] = paths[a][b] != {}.x ? `(${paths[a][b]}|${path})` : path
      ))
    )
  )),
  paths.s.e || "[]"
)

console.log(`^${dfaToString(invertDfa(dfa))}$`)

```

## Explanation

The program executes the following process:

1. Parse the regex into a tree structure
2. Convert the tree structure into a DFA
3. Invert the accepted/rejected states of the DFA
4. Convert the DFA into a (stringified) regex

In the parsed regex tree, the leaves are characters, and the branches are operations. For example, `^a[bc](d|e*)$` would look like

```
[2 /* concat */, [
  [2 /* concat */, [
    "a",
    [3 /* character group */, [
      "b",
      "c",
    ]],
  ]],
  [1 /* union */, [
    "d",
    [0 /* star */, [
      "e",
    ]],
  ]],
]]

```

A DFA is represented as a 3-tuple:

```
[
  initial /* state */,
  accept /* state => bool */,
  next /* state => char => bool */,
]

```

States are numbers or deep arrays of numbers.

To convert this parsed regex into a DFA, the tree is processed bottom-up. Single characters and character groups become 3-state DFAs (start, accept, and dead). Operations compose their DFA operands in various ways; for example, union tracks the state of each operand, and accepts any state where one of the operands is accepting.

The DFA is then inverted by negating the `accept` function.

To convert the inverted DFA into a regex, it is encoded into a JS object that represents a `(state, state) -> string`. Each string will be a regex that accepts the set of strings that will move the DFA from one state to another. Initially, the strings are simply character classes containing all of the characters between the two states in the DFA. This is what the object would look like initially for the regex `^[ab]$`, if the alphabet was limited to `abc`.

```
{
  s: { 0: "" },
  0: { 1: "[ab]", 2: "[c]" },
  1: { e: "", 2: "[abc]" },
  2: { 2: "[abc]" },
}

```

The special keys `s` and `e` represent the start and end, respectively. In this case, the state `2` is a dead state, where no progress can be made. The leaf values are referred to "arrows"; for example, the `01` arrow goes from `0` to `1` and has a regex of `[ab]`. Any non-existent arrows have a regex of `[]`, a regex that matches nothing.

This object now needs to be distilled to a singular regex. Then, each of the states is removed iteratively. When removing states, the arrows associated with those states must be combined with the other regexes.

If there are states `A` and `B` (not necessarily distinct), and a state `X` which is being removed, arrow `AB` will be upserted to be

```
<AB>|<AX><XX>*<XB>

```

Note that:

* If there is no `XX` arrow, the `AB` arrow will become `<AB>|<AX><XB>`, as `[]*` is equivalent to `()` (the regex that matches the empty string).
* If there is no `AB` arrow, there will be a new arrow that is `<AX><XX>*<XB>`.
* If there is no `AX` arrow or no `XB` arrow, the `AB` arrow will be unchanged.

Thus, the object evolves as follows:

```
// Original
{
  s: { 0: "" },
  0: { 1: "[ab]", 2: "[c]" },
  1: { e: "", 2: "[abc]" },
  2: { 2: "[abc]" },
}

// After removing 0
{
  s: { 1: "[ab]", 2: "[c]" },
  1: { e: "", 2: "[abc]" },
  2: { 2: "[abc]" },
}

// After removing 0 and 1
{
  s: { e: "[ab]", 2: "[c]|[ab][abc]" },
  2: { 2: "[abc]" },
}

// Final
{
  s: { e: "[ab]" },
}

```

In the end, the object will be `{ s: { e: <regex> } }` or `{ s: {} }`. If it's the latter, there was no path from `s` to `e`, so the final regex is `[]`.

Interestingly, this process is far from lossless; running a regex through without inverting it often still explodes the size:

```
Input: ^a[bc](d|e*)$
Output (not inverted): ^((([a][bc]|[a][bc][d])|[a][bc][e])|[a][bc][e][e]([e])*)$

```
> 22 votes

---
Tags: code-golf, regular-expression
---


title: Fix Brain-Flak push-pop redundancy

text:
# Question
Title: Fix Brain-Flak push-pop redundancy
Brain-Flak is a stack-based esoteric language with eight commands:

```
()     Evaluates to 1
<>     Switch active stack; evaluates to 0
[]     Evaluates to height of current stack
{}     Pop current stack; evaluates to the popped number
(...)  Execute block and push the result; evaluates as result
<...>  Execute block; evaluates as 0
[...]  Execute block; evaluates as negation of result
{...}  While top of active stack is nonzero, execute block

```

Write a program or function to detect and remove one common type of push-pop redundancy that often occurs when writing Brain-Flak code.

# Finding Redundancy

To determine whether a push and pop are truly redundant, we must understand which scopes use the return value of instructions:

* The return value of any top-level instruction is ignored.
* `(...)` will always use the return values of its children.
* `<...>` will always ignore the top-level instruction of its children.
* `{...}` will pass the return values of its children to the enclosing scope; that is, their return values will be used if and only if `{...}` itself is in a scope that uses its return value.
* `[...]` theoretically works like `{...}` in this sense; however, you may assume that `[...]` is always in a scope that cares about return value, thus treating it like `(...)`.

The type of redundancy we are interested in occurs in any substring of the form `(A)B{}` satisfying the following:

* `A` is a balanced string; that is, the parentheses around `A` are matched.
* `(A)` is in a scope that ignores its return value.
* `B` does not contain `[]`, `<>`, or either half of the `{...}` monad.
* The `{}` immediately following `B` pops the value pushed by `(A)`. That is, `B` has an equal number of `{}` and `...)`, and no prefix of `B` has more `{}` than `...)`.

Note that `B` is typically not a balanced string.

# Removing Redundancy

To remove this redundancy, we temporarily introduce a symbol `0` to the language, which evaluates to 0. With this symbol, a redundant string `(A)B{}` can be safely replaced by `0BA`. Since Brain-Flak does not have a `0` symbol, we must make simplifications to remove it:

* A `0` with a sibling can be removed entirely, as can any top-level `0`s. (If there are two `0`s as the only children of a monad, only one of them can be removed.)
* `[0]` and `<0>` can be simplified to `0`.
* If you encounter a `(0)`, find the matching `{}`; replace the `(0)` and matching `{}` with `0`s.
* `{0}` will never happen. If I'm wrong about this, you may have undefined behavior in this case.

# Rules

* Input is a string taken by any reasonable method.
* Input is guaranteed to be valid Brain-Flak code consisting only of brackets.
* Any `[...]` monads in the input will be in scopes that do not ignore their return values.
* Output is a semantically equivalent Brain-Flak program with no push-pop redundancies as defined above.
* The output program must not be longer than the result of the algorithm described above.
* The input might not contain any redundancy; in that case, the input program should be output unchanged.
* If your solution is in Brain-Flak, it should hopefully not detect any redundancy in its own code.
* This is , so the shortest program (in bytes) in each language wins.

# Test cases

With redundancy (with redundant push and pop marked):

```
Shortest redundancy
({}){} -> {}
^  ^^^

First example from tips post
({}<>)({}()) -> ({}<>())
^    ^ ^^

Second example from tips post
({}<({}<>)><>)(<((()()()){}[((){}{})])>) -> (<((()()()){}[((){}<({}<>)><>{})])>)
^            ^                 ^^

Inside the zero monad
({}<({}{})>{}) -> ({}{}{})
    ^    ^ ^^

Inside a loop
{({}{})([{}])} -> {([{}{}])}
 ^    ^  ^^

Stack height pushed
([][]())({}()) -> ([][]()())
^      ^ ^^

Loop result pushed
({({}[()])}{})(({})) -> (({({}[()])}{}))
^            ^  ^^

Two redundancies
({}<({}{})>)({}{}) -> ({}{}{})
^   ^    ^ ^ ^^^^

Discovered redundancy
(({})){}({}()) -> ({}())
^^  ^^^^ ^^

Chained redundancy
(<(()()())>)(({}){}{}({})) -> (()()()({}))
  ^      ^         ^^

```

No redundancy (output should be the same as input):

```
-empty string-
(({}<>)({}()))         - unlike the second test case, the pushed value is used again
(({}){})               - standard code for doubling the top value on the stack
({}{})<>{}             - push and pop not on same stack
(()){{}{}}             - loop starts between push and pop
({(({}[()]))}{})([]{}) - stack height is used after push

```

# Answer
> 5 votes
# Haskell, ~~995~~ ~~973~~ 873 bytes

*Nitrodon saved me 22 bytes with a way around the monomorphism restriction*

Not *well* golfed, but golfed a bit.

I implement my own parsing library here. Not a wise idea for golf. If I really wanted to make this short I would probably just use an off the shelf one like `parsec`.

I also lose a ton of bytes to the type and instance declarations. This could definitely be done without them and it would probably save bytes.

```
import Control.Monad
newtype P b a=P{h::b->[(b,a)]}
instance Functor(P b)where fmap f(P p)=P$map(f?)?p
instance Applicative(P b)where pure x=P(\y->[(y,x)]);(<*>)=ap
instance Monad(P b)where P p>>=f=P$(>>=uncurry(flip$h.f)).p
f?x=f<$>x
l=s"("
k=s"()"
o=s")"
w=words
p x=pure x
e=P$p[]
x%y=liftM2(++)x y
P p#P q=P$p%q
b q=P(\x->[(b,a)|a:b<-[x],q a])
t=p?b(p$1>0)
s=mapM$b.(==)
a=foldr(#)e
n p=P(\x->[(x,())|[]==h p x])
v=a[s[x]%c%s[y]%c|[x,y]<-w"() <> {} []"]#s"0"
c=v#s""
d 0=a[n(a$s?w"<> [] { } )")*>a[k,n k*>t]%d 0,o%d 1,p""]
d x=a[n(s"<>"#s"[]")*>k#(p?b(`elem`"(<>[]"))%d x,s"{}"%d(x-1),o%d(x+1)]
f z=a[a[p""|z],(s"{"#s"[")%f z,l%f(0>1),s"<"%f(1>0),v%f z]
m=p""#(t%m)<*q
q=P(\x->[([],"")|[]==x])
z=a[s"0"*>p"",(s"["#s"<")*>z<*(s"]"#s">"),l%z%o*>p"<(0)>"]
r=a[n z*>t%r,z%r,q]
u x=head$(u.snd<$>((>>=h r.snd).h(do x<-f$1>0;l;i<-v;o;y<-d 0;s"{}";((x++'0':y++i)++)?m))x)++[x]

```

Try it online!

# Haskell, Ungolfed

Here's what this looks like ungolfed.

```
balanced :: Parser String
balanced =
  ( choice
    [ string [x]
      <> balanced
      <> string [y]
      <> balanced
    | [x, y] <- ["()", "<>", "{}", "[]"]
    ]
  ) <|> string ""
    <|> string "0"

getBetween :: Int -> Parser String
getBetween pushes
  | pushes > 0 =
  choice
    [ do
      notAhead $ string "<>"
      notAhead $ string "[]"
      start <- string "()" <|> fmap pure (charBy (`notElem` "{})"))
      rest <- getBetween pushes
      pure $ start ++ rest
    , do
      string "{}"
      rest <- getBetween (pushes - 1)
      return $ "{}" ++ rest
    , do
      string ")"
      rest <- getBetween (pushes + 1)
      return $ ')' : rest
    ]
  | pushes == 0 =
  choice
    [ do
      notAhead $ string "<>"
      notAhead $ string "[]"
      notAhead $ char '{'
      notAhead $ char '{'
      notAhead $ char ')'
      start <- choice
        [ string "()"
        , do
          notAhead $ string "()"
          chr <-charBy $ const True
          return [chr]
        ]
      rest <- getBetween pushes
      pure $ start ++ rest
    , do
      string ")"
      rest <- getBetween (pushes + 1)
      return $ ')' : rest
    , pure ""
    ]

getBefore :: Bool -> Parser String
getBefore zeroed
  | zeroed
  =
    choice
      [ pure ""
      , do
        next <- choice $ map char "<{["
        rest <- getBefore zeroed
        return $ next : rest
      , do
        char '('
        rest <- getBefore False
        return $ '(' : rest
      , do
        prefix <- balanced
        guard $ prefix /= ""
        rest <- getBefore zeroed
        return $ prefix ++ rest
      ]
  | otherwise
  =
    choice
      [ do
        next <- choice $ map char "({["
        rest <- getBefore zeroed
        return $ next : rest
      , do
        char '<'
        rest <- getBefore True
        return $ '<' : rest
      , do
        prefix <- balanced
        guard $ prefix /= ""
        rest <- getBefore zeroed
        return $ prefix ++ rest
      ]

mainParser :: Parser String
mainParser =
  do
    before <- getBefore True
    char '('
    inside <- balanced
    guard $ inside /= ""
    char ')'
    between <- getBetween 0
    string "{}"
    after <- many $ charBy $ const True
    end
    return $ before ++ "0" ++ between ++ inside ++ after

zero :: Parser String
zero =
  choice
    [ char '0' *> pure ""
    , choice
      [ char x *> zero <* char y
      | [x, y] <- ["[]", "<>"]
      ]
    , do
      char '('
      zero
      char ')'
      return $ "<(0)>"
    ]

removeZeros :: Parser String
removeZeros =
  choice
    [ do
      notAhead zero
      chr <- charBy $ const True
      rest <- removeZeros
      return $ chr : rest
    , zero <> removeZeros
    , end *> pure ""
    ]

run :: String -> String
run input =
  case
    map snd $ apply (compose mainParser removeZeros) input
  of
    [] ->
      input
    x ->
      head $ map run x

```

Try it online!

# Answer
> 5 votes
# JavaScript, ~~449~~ ~~600~~ 580 bytes

*-13 bytes thanks emanresu A*

(@WheatWizard wrote their answer first, causing me to look at this challenge; this answer is not intended to steal their glory)

```
x=>{for([...x].reduce((_,b)=>"({[<".includes(b)?(y.unshift([b,--i+"#"]),y[1].push(y[0])):(b==")"&&y[0][2]&&j.push(y[0][1]),x=y.shift()).push(b!="}"|x[3]?b:b+(j.pop()||"-0#")),y=[[]],i=0,j=[]),y=y[0].reduce(g=(a,b)=>b[3]?a+b[0]+b[1]+b.slice(2,-1).reduce(g,"")+b[1]+b.pop():a+b[0]+b[2],"");x!=y;)y=(x=y).replace(/(((<-\d+#|^)([<[({]((-\d+#).+\5)?[\])}>]|X)*)(({-\d+#|^)([<[({]((-\d+#).+\11)?[\])}>]|X)*)*)\((-\d+#)(.*)\12\)(((?!\[\]|<>|\{-|#}).)*){}\12|\((-\d+#)(X)\16\)(((?!\[\]|<>|\{-|#}).)*){}\16|\[-\d+#X-\d+#\]|<-\d+#X-\d+#>/,"$1X$18$17$14$13");return y.replace(/-\d+#|X/g,"")}

```

Try it online!

A horrific solution that uses string manipulation.

First, it recursively parses the program and adds annotations:

```
original:
(<(()()())>)(({}){}{}({}))
annotated:
(-1#<-2#(-3#()()()-3#)-2#>-1#)(-7#(-8#{}-1#-8#){}-8#{}-3#(-12#{}-0#-12#)-7#)

```

The `-N%`s inside brackets denote matching brackets. Additionally, `{}`s are annotated with the `-N#` of the `()` they pop.

Then, regex substitutions are repeatedly applied until it stabilizes (`X` is used instead of `0`):

(this is an explanation of the old regex; the new one that accounts for more cases is beyond explanation)

```
/\((-\d+#)(.*)\1\)(((?!\[\]|<>|\{-|#}).)*){}\1/X$3$2
 \(                                                   literal open paren
   (-\d+#)                                            group 1, matches a -N#
          (.*)                                        group 2, this is A
              \1\)                                    matching close paren
                  (((?!\[\]|<>|\{-|#}).)*)            group 3, this is B
                    (?!\[\]|<>|\{-|#})                there can be no [], <>, {-, or #}
                                          {}\1        the {} that pops (A)
                                               X$3$2  replace with X, followed by groups 2 and 3
/\[-\d+#X-\d+#\]/X  replace [-N#X-N#] with X
/<-\d+#X-\d+#>/X  replace <-N#X-N#> with X

```

In the actual implementation, these are all combined into a single unioned regex.

The `(0)` case from the original algorithm is just a special case of the `(A)B{}` -\> `0BA` transformation, so no special casing is needed for it.

Once it stabilizes, all `X`s (these must be have a sibling) and `-N#`s are removed, and the resulting string is returned.

---
Tags: code-golf, brain-flak
---