title: Generate all Brain-Flak Snippets

text:
# Question
Title: Generate all Brain-Flak Snippets
> *This question is the second of several Brain-flak Birthday challenges designed to celebrate Brain-Flak's first Birthday! You can find more information about Brain-Flak's Birthday here*

# Challenge

For this challenge you'll be generating all fully matched strings from a list of brackets. To borrow DJMcMayhem's definition of a fully matched string:

* For the purpose of this challenge, a "bracket" is any of these characters: `()[]{}<>`.
* A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

```
()
[]{}

```

Or if every subelement inside of it is also matched.

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

```

Subelements can also be nested several layers deep.

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

```
* A string is considered "Fully matched" if and only if each pair of brackets has the correct opening and closing bracket in the right order.

---

# Input

Your program or function will take a list of four non-negative numbers in any convenient, consistent format. This includes (but is not limited to) a list of integers, a non-digit delimited string, or separate arguments. These four numbers represent the number of matched pairs of each type of bracket. For example, `[1,2,3,4]` would represent:

* 1 pair of `()`
* 2 pairs of `{}`
* 3 pairs of `[]` and
* 4 pairs of `<>`

You may choose which pair of brackets each input corresponds to as long as it is consistent.

# Output

You should output all fully matched string that can be formed from this list of brackets without duplicates. Output can be in any reasonable format which includes printing a non-bracket delimited string to STDOUT, or a list of strings as a return value from a function.

Your algorithm must work for any arbitrary input, but you don't need to worry about memory, time or integer size limits (e.g. if your answer is in C you won't get 233 as an input).

This is , so the shortest answer in bytes wins.

# Example Input and Output

For these example I will use the same input order as above.

For each example, the first line will be input and the following lines will be the output

```
Example 0:
[0,0,0,0]

Example 1:
[1,0,0,0]
()

Example 2:
[0,2,0,0]
{}{}
{{}}

Example 3:
[0,0,1,1]
[]<>
[<>]
<[]>
<>[]

Example 4:
[0,1,2,0]
{}[][]  {}[[]]  {[]}[]  {[][]}  {[[]]}
[{}][]  [{}[]]  [{[]}]  []{}[]  []{[]}
[][{}]  [][]{}  [[{}]]  [[]{}]  [[]]{}

Example 5:
[1,0,0,3]
()<><><>  ()<><<>>  ()<<>><>  ()<<><>>  ()<<<>>>  (<>)<><>  (<>)<<>>
(<><>)<>  (<><><>)  (<><<>>)  (<<>>)<>  (<<>><>)  (<<><>>)  (<<<>>>)
<()><><>  <()><<>>  <()<>><>  <()<><>>  <()<<>>>  <(<>)><>  <(<>)<>>
<(<><>)>  <(<<>>)>  <>()<><>  <>()<<>>  <>(<>)<>  <>(<><>)  <>(<<>>)
<><()><>  <><()<>>  <><(<>)>  <><>()<>  <><>(<>)  <><><()>  <><><>()
<><<()>>  <><<>()>  <><<>>()  <<()>><>  <<()><>>  <<()<>>>  <<(<>)>>
<<>()><>  <<>()<>>  <<>(<>)>  <<>>()<>  <<>>(<>)  <<>><()>  <<>><>()
<<><()>>  <<><>()>  <<><>>()  <<<()>>>  <<<>()>>  <<<>>()>  <<<>>>()

Example 6:
[1,1,1,1]

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

```

# Answer
# Haskell, 128 bytes

`f` is the main function, it takes a list of `Int`s and returns a list of `String`s.

```
f=g.($zip"({[<"")}]>").zipWith replicate
g=max[""].(#g)
l#c=[b:s|x@(b,e):r<-l,s<-(r:filter(/=x:r)l)?(map(e:).c)]
l?c=c l++l#(?c)

```

Try it online!

# How it works

* `f` transforms its input list into a list of lists of tuples, each tuple containing a bracket pair, with each type of bracket in its own sublist. E.g. `[1,2,0,0]` becomes `[[('{','}')],[('[',']'),('[',']')]]`. Then it calls `g` with the transformed list.
* The remaining functions use a partially continuation-passing style intermingled with list manipulation. Each continuation function `c` takes a list `l` of remaining bracket tuple lists and returns a list of possible strings to be suffixed to what's already been generated.
* `g l` generates the list of fully matched strings formable by using all the brackets in `l`.
    + It does this by calling `l#g` to generate strings beginning with some bracket. The recursive `g` parameter is itself used as a continuation by `#`, to generate what comes after the first bracketed subelement.
    + In the case where there are no such strings (because `l` has no brackets left inside) `g` instead returns `[""]`, the list containing just the empty string. Since `[""]` compares smaller to all nonempty lists produceable by `#`, we can do this by applying `max`.
* `l#c` generates strings from `l` beginning with at least one bracketed subelement, leaving to the continuation `c` to determine what follows the element.
    + `b` and `e` are a selected pair of brackets in the tuple `x`, and `r` is the list of remaining tuples of the same bracket type.
    + `r:filter(/=x:r)l` is `l` with the tuple `x` removed, slightly rearranged.
    + `?` is called to generate the possible subelements between `b` and `e`. It gets its own continuation `map(e:).c`, which prefixes `e` to each of the suffix strings generated by `c`.
    + `#` itself prepends the initial `b` to all the strings generated by `?` and `c`.
* `l?c` generates the fully matched strings formable by using zero or more bracket pairs from `l`, and then leaves to its continuation `c` to handle what's left over. The `c l` part goes directly to `c` without adding any subelements, while `l#(?c)` uses `#` to generate one subelement and then call `(?c)` recursively for possible further ones.
> 6 votes

# Answer
# Jelly, ~~50 40~~ 34 bytes

-6 bytes thanks to Leaky Nun (getting reduce to work where I couldn't)

```
“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ

```

Plain and inefficient.

**Try it online!** (times out at TIO for \[1,1,1,1\] - yes, inefficient.)

### How?

Recursively removes pairs of matching brackets that reside right next to each other until no more may be removed for every possible string one may form, keeping such strings which reduce to nothing (hence have all matching content).

```
“()“{}“[]“<>”©ẋ"FŒ!QµW;®œṣF¥/µÐLÐḟ - Main link: list: [n(), n{}, n[], n<>]
“()“{}“[]“<>”                      - literal ["()", "{}", "[]", "<>"]
             ©                     - copy to register
               "                   - zip with:
              ẋ                    -   repeat list
                F                  - flatten
                 Œ!                - all permutations (yeah, it's inefficient!)
                   Q               - de-duplicate
                    µ              - monadic chain separation
                                Ðḟ - filter discard if (non empty is truthy):
                             µÐL   -   loop until no change:
                       ®           -     recall value from register
                     W             -     wrap loop variable in a list
                      ;            -     concatenate
                           ¥/      -     reduce with last two links as a dyad:
                        œṣ         -       split left on occurrences of sublist on the right
                          F        -       flatten the result

```
> 4 votes

# Answer
# Pyth - ~~83~~ ~~74~~ ~~71~~ 63 bytes

```
K("\[]""{}""\(\)""<>")Fd{.psm*:@Kd*\\2k@QdU4JdVldFHK=:JHk))I!Jd

```

Try It

: Kc"\[\] {} () \<\>")Fd{.ps\*V-R\KQJdVldFHK=:JHk))I!Jd

Also, this 53-byte version thanks to Leaky Nun

```
Kc"\[] \{} \(\) <>")Fd{.ps*V-R\\KQJdVldFHK=:JHk))I!Jd

```

Here
> 3 votes

# Answer
# 05AB1E, ~~33~~ ~~32~~ ~~30~~ ~~27~~ 25 bytes

Saved 7 bytes thanks to *Riley*.

Input order is `[(),<>,[],{}]`

```
žu4ä×©JœJÙD[D®õ:DŠQ#]€g_Ï

```

Try it online!

**Explanation**

```
žu                             # push the string "()<>[]{}"
  4ä                           # split in 4 parts
    ©                          # store a copy in register
     ×                         # repeat each bracket a number of times decided by input
      JœJÙ                     # get the unique permutations of the string of brackets
          D                    # duplicate
           [                   # start infinite loop
            D                  # duplicate current list of permutations
             ®õ:               # replace any instance of (), [], <>, {}
                               # with an empty string
                DŠ             # duplicate and move down 2 places on stack
                  Q#           # if the operation didn't alter the list, exit loop
                    ]          # end loop
                     €g        # get the length of each subtring
                       _Ï      # keep only the strings in the original
                               # list of unique permutations
                               # that have a length of 0 in the resulting list

```
> 3 votes

# Answer
# Ruby, 123 bytes

```
->a{"<>{}[]()".gsub(/../){$&*a.pop}.chars.permutation.map(&:join).uniq.grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}

```

Try it online! It's inefficient, though, so even inputs like `[1,2,1,1]` will time out online. All the listed examples will work, at least!

### Explanation

```
->a{                                        # Procedure with input a
    "<>{}[]()".gsub(/../){                  # For all pairs of brackets
                          $&*a.pop          # Pop last item in input, then repeat
                                            #   the bracket pair by that number
                                  }.chars   # Get characters
        .permutation                        # All permutations of characters
                    .map(&:join)            # For each permutation, join the chars
                                .uniq       # Get unique permutations only
            .grep /^((\(\g<1>\)|\[\g<1>\]|\{\g<1>\}|<\g<1>>)*)$/}
                                            # Only return permutations that match
                                            #   this bracket-matching regex

```
> 2 votes

---
Tags: code-golf, string, permutations, balanced-string, brain-flak
---


title: King of the Hill: Bank Heist

text:
# Question
Title: King of the Hill: Bank Heist
**Example run added 4/11**

**Rules Clarification 4/8: All submissions will be competing in one giant free-for-all tournament consisting of as many matches as my computer can perform in 48 hours.**

Anyone who's spent any time watching streams on Twitch is aware of the prevalence of DeepBot, and is perhaps even familiar with its Bank Heist betting game. This King of the Hill tournament is directly inspired by that game. Don't worry, though. I think I've thrown enough extra kinks into this version to keep things interesting.

## A quick example

```
#####GAME 13: 16 players######

Round 1:
gunHeCK bet 0.
PassivePanga bet 69.
SnitcherKing bet 1.
Lurker bet 0.
OC'sRandomTpyos bet 1.
MonisAddiction bet 69.
RaysFive01K bet 28.
LimeadeSneaktar bet 1.
KaylorrCriterion bet 0.
HardHatUmar bet 0.
HeCKuSumer bet 185.

Round 2
HeCKuSumer decided to !guncheck.
LimeadeSneaktar decided to double cross.
MonisAddiction decided to all in.
OC'sRandomTpyos decided to acquire intel.
RaysFive01K decided to deposit.
SnitcherKing decided to finger.
PassivePanga decided to !guncheck.

Results
PassivePanga failed. :(
SnitcherKing failed. :(
OC'sRandomTpyos was successful, and may gain ¥0
MonisAddiction failed. :(
RaysFive01K was successful, and may gain ¥0
LimeadeSneaktar was successful, and may gain ¥1
HeCKuSumer failed. :(

Results:
0. KaylorrCriterion: 3600
1. Lurker: 3600
2. gunHeCK: 3600
3. SnitcherKing: 3586
4. PassivePanga: 2634
5. LimeadeSneaktar: 2496
6. HeCKuSumer: 1909
7. HardHatUmar: 490
8. RaysFive01K: 255
9. OC'sRandomTpyos: 170
10. MonisAddiction: 0

(In this round, 7 players joined the heist, but the dice only rolled right for 3 of them. Of those, only LimeadeSneaktar brought any home--having stolen it from OcsRandomTpyos. RaysFive01K won significantly more, but deposited it all at the bank before leaving. At this point, the players who did not heist are doing well, living off their day jobs.)

#####GAME 14: 231 players######

Round 1:
Lurker bet 0.
HeCKuSumer bet 190.
KaylorrCriterion bet 0.
HardHatUmar bet 0.
MonisAddiction bet 0.
OC'sRandomTpyos bet 1.
gunHeCK bet 0.
LimeadeSneaktar bet 1.
RaysFive01K bet 25.
PassivePanga bet 69.
SnitcherKing bet 1.

Round 2
PassivePanga decided to !guncheck.
OC'sRandomTpyos decided to buy guard.
HeCKuSumer decided to !guncheck.
SnitcherKing decided to finger.
RaysFive01K decided to deposit.
LimeadeSneaktar decided to double cross.

Results
HeCKuSumer failed. :(
OC'sRandomTpyos failed. :(
LimeadeSneaktar failed. :(
RaysFive01K failed. :(
PassivePanga failed. :(
SnitcherKing failed. :(

Results:
0. KaylorrCriterion: 3840
1. Lurker: 3840
2. gunHeCK: 3840
3. SnitcherKing: 3825
4. PassivePanga: 2805
5. LimeadeSneaktar: 2495
6. HeCKuSumer: 1959
7. HardHatUmar: 490
8. MonisAddiction: 240
9. RaysFive01K: 229
10. OC'sRandomTpyos: 161

Six players heisted--but should have been paying more attention to the rabble and backed out, because the probabilities dropped too low to win, and all failed.

#####GAME 15: 300 players######

Round 1:
OC'sRandomTpyos bet 1.
Lurker bet 0.
SnitcherKing bet 1.
MonisAddiction bet 69.
LimeadeSneaktar bet 1.
gunHeCK bet 0.
HardHatUmar bet 0.
RaysFive01K bet 22.
KaylorrCriterion bet 0.
HeCKuSumer bet 195.
PassivePanga bet 69.

Round 2
HeCKuSumer decided to !guncheck.
OC'sRandomTpyos decided to buy guard.
MonisAddiction decided to all in.
PassivePanga decided to !guncheck.
LimeadeSneaktar decided to double cross.
RaysFive01K decided to deposit.
SnitcherKing decided to finger.

Results
OC'sRandomTpyos failed. :(
SnitcherKing failed. :(
MonisAddiction was successful, and may gain ¥0
LimeadeSneaktar failed. :(
RaysFive01K failed. :(
HeCKuSumer failed. :(
PassivePanga failed. :(

And here, the probabilities dropped too low to win again--except for MonisAddiction, who went all in, and therefore avoided the probability modification incurred by the rabble backing out. No winnings are listed here, because a player who wins going all in immediately adds all winnings to its holdings without any possible modification by other players' actions.

```

## Game Rules

### Tournament/Game Structure

* The tournament will consist of a number of games chosen uniformly at random between 1000 and 1100, in which every *serious* submission will be competing simultaneously in a free-for-all.
* Every player starts the first game with 240 *credits* and each subsequent game with the number of credits it had at the end of the previous game.
* Each game proceeds in 2 rounds, and in each round, players are called in an order determined uniformly at random to make one decision:
    + In the first round, a player may pay any integer number of credits between 0 and its current credit holdings to stake participation in a bank heist.
    + In the second round, each player that elected to participate in the heist by wagering at least one credit (hereafter referred to as "heisters") may decide to let its bet ride (and, while doing so, possibly perform some other action), opt out of the heist, or go all-in. (These options are further described below.)
* Based on the number of heisters and the total number of credits they paid, one of five banks is selected on which to stage a heist. This selection affects the individual probability of victory and the odds by which the payout is determined. (The banks are described below.)
* Each heister that did not opt out will, with the bank's (modified) probability, win its stake multiplied by the bank's (modified) betting odds (rounded down), or else lose its stake. Note that each player's success or failure is determined *individually*--some will succeed where others fail.
* All players, whether they participated or not, succeeded or failed, then receive a paycheck (with exceptions described below).
* Note that it is impossible to permanently leave the game. At worst, a player may have to wait a game to receive its next paycheck.
* After all 1000-1100 games, the player with the greatest number of credits will be declared the winner of that tournament.
* The tournament will be repeated an unspecified number of times (as many as can be computed in 48 hours) and the player earnings across all tournaments summed in order to determine the overall winner of this contest.

### The Second Betting Round

* Any player who has wagered a positive stake in the first round may participate in the second round.
* In this round, a player may:
    + reply with the string "back out" to cancel its bet. This will set its wager to zero for the current heist and also slightly decrease the probability the players remaining in the heist will succeed. By taking this option, a player forgoes the 240 credit paycheck that follows the heist as punishment for putting the remaining heisters at risk. (The remaining heisters will succeed with a probability equal to the bank's probability times the fraction of heisters that did not "back out".)
    + reply with the string "all in" to blow its entire credit holdings--and take out a payday loan on its next 240 credit paycheck--to buy all the best gear and intel for a heist and go in alone, guns blazing, without relying on anyone. Such a player's victory probability cannot be affected by other heisters dropping out of the heist, nor can its winnings be stolen by double-crossers. Winning payouts will be determined as if its bet were its entire credit holdings plus 240, while loss will set its holdings to zero.
    + Reply with any other string (including the empty string) in order to stick with the previous bet and go through with the heist as normal. (Recommended reply: "!guncheck"). Certain replies will have additional side effects:
        - A reply of "change jobs" will cause the player to quit its job. Beginning this round, at the end of each round, the player will have a 5% chance to get hired in a new position. If this succeeds, the player is hired and immediately receives its first paycheck. Each new job is guaranteed to pay exactly 5% more than the last (rounded down). This action will succeed whether or not the heist succeeds.
        - A reply of "acquire intel" will, if the heist succeeds, cause the player to spend all of its winnings from that heist to get an extra 0.00001 per credit thus spent on the odds for the bank that was heisted *for that player only*. This odds modification is permanent. As an example, if a player chooses this action when heisting bank 1 and wins 6969 credits in a heist, bank 1's odds for that player will be permanently increased by 0.06969 and the player will receive nothing from that heist.
        - A reply of "buy guard" will cause the player to buy off one of the security guards at the bank being heisted. In exchange for a permanent reduction of 1 credit on that player's paycheck (the guard's regular bribe), the player will receive a "permanent" increased victory probability *at that bank* (due to the guard "forgetting to mention" that player to the cops when asked). The probability will increase by exactly 1% of the difference between the player's current victory probability at that bank and 100%. This action will succeed even if the heist fails. NOTE: If at any time, a player has not enough credits to pay all of its guard bribes, it immediately and "permanently" loses as many probability bonuses as the number of bribes that could not be paid, selected uniformly at random from all bribes registered.
        - A reply of "deposit" will, if the heist succeeds, leave a player's entire winnings in an account at the bank heisted. The credits will not be accessible for any purpose nor be counted towards a player's score until withdrawn. This account will pay interest at a rate of 0.14% per game.
        - A reply of "withdraw" will, if the heist succeeds, add to a player's winnings the entire contents of its account at the bank heisted. The account will be zeroed as a result. Note that these additional winnings *can* be stolen by double-crossers.
        - A reply of "double cross" will do one of two things:
            * If the number of heisters who played "double cross" is at most 1/10th (rounded down) of the total number of non-rabble heisters who decided to go through with the heist (or exactly one if there are less than 10 such players), the player will receive additional winnings equal to the total winnings of all non-double-crossers divided by the number of double-crossers (rounded down). All non-double-crossers in this case receive 0 credits from the heist. In other words, the double-crossers steal everyone else's credits and divide it evenly amongst themselves.
            * If the number of heisters who played "double cross" exceeds the threshold, the player will receive no winnings (if its heist was successful), have its paycheck cut in half, and be fired from its job. (See "change jobs".) All non-double-crossers (including rabble) in this case will receive a bonus payment of the total winnings of all double-crossers divided by the total number of non-double-crossers. In other words, the conspiracy got too big to keep a secret, the conspirators were rooted out and excluded from the heist, and everyone divided up their stakes for punishment--and their reputation for dirty dealing lost them their jobs as well.
        - A reply of "finger" (as in "fingering a double-crossing scoundrel rat") will, if the heist succeeds, give the player eight opportunities (drawing uniformly with replacement from the set of non-rabble heisters) to identify a double-crosser *which has not already been so identified*.
            * Each double-crosser identified this way will immediately pay the fingerer 25% of its current credit holdings (rounded down) in lieu of being shot, lose its job and have its paycheck cut in half (because the boss won't tolerate bad behavior), and lose 5% of its probability of victory at the bank being heisted (as other heisters are extra suspicious in the future and likely to throw it under the bus if things get hairy). Double-crossers identified this way do not affect whether the double-cross was successful for other double-crossers, but they do not receive any of the stolen credits from the double-cross, and said stolen credits will be redistributed back to the non-double-crossers.
            * If no double-crossers are identified this way, the snitch will get stitches for wasting everyone's time--and also pay half its winnings from the current heist, take a 5% cut on its paycheck (boss cuts the tattletale's hours), and lose 5% of its betting odds at the current bank (as other heisters are less likely to be generous/fair with their winnings in the future). The half of its winnings thus lost will be distributed to the unfingered double-crossers if the double-crossers succeeded, or the non-double-crossers (including rabble) if the double-crossers failed.

### The Banks

The bank is selected using the index `numheisters + int(totalamountbet/100000)`, where numheisters is the number of players which wagered a positive stake in round 1 and totalamountbet is the sum of the stakes of all of those players. In other words, a hundred thousand credits is as good as 1 additional heister. Based on this index one of the following banks will be chosen, the bank with the highest threshold that the index meets or exceeds:

```
Bank             Index Threshold   Victory Prob.  Bet Odds
----             ---------------   -------------  --------
0:Municipal                    0           0.540      0.80
1:City                        20           0.488      1.10
2:State                       40           0.425      1.30
3:National                    60           0.387      1.65
4:Federal Reserve             80           0.324      1.95

```

Note that as a tournament continues, the probability of reaching the highest bank level will increase, as the amount each player can bet trends upwards. Note also that these are only *initial* odds and probabilities, before they have been modified by any "acquire intel" or "buy a guard" actions. With the initial probabilities and odds, only the City and National banks have expected winnings exceeding expected losses.

### The Rabble

* The tournament also contains 500 other players, called the "rabble", who participate as regular players in heists but are not scored in the end. These serve to make each game different and somewhat less predictable, and make it possible to reach the riskier/more rewarding banks even with only a few "real" players.
* Each game will include some subset of rabble to participate chosen uniformly at random over all subsets of rabble.
* All rabble use the following strategy:
    + Randomly choose to bet with probability equal to the probability of succeeding at the bank that would be selected based on the decisions of the players *who have already made their decision this round*.
    + If betting a nonzero amount, choose the largest of the following amounts that would not exceed its current holdings: 69, 420, 6969, 80085.
    + In the second round, "back out" with probability equal to 5% plus 50% of the proportion of bettors that have already backed out, otherwise heist as normal. (Note that this means early players in the second round that back out can have huge cascading effects among the rabble--pay attention and be ready for the heist to collapse before it even starts.)

### Inputs and Outputs

In both rounds, programs will be given the following information, in *exactly* this order, *as command line arguments*. Unless otherwise stated, all values are integers containing no decimal.

1. The current game number (zero-indexed)
2. The round number of the current game (1 or 2)
3. The number of players in the current game (including rabble).
4. The number of players that have already taken their turns this round.
5. The number of heisters that have committed a positive stake so far. (In the second round, this will actually be the total number of heisters who bought in in the first round.)
6. The total number of credits invested so far. (In the second round, this will actually be the total number of credits invested in the first round--in particular, it *does not* include more than the initial stakes of "all in" heisters and *does* include the stakes of "back out" heisters.)
7. The number of heisters who have confirmed in the second round (i.e. did not "back out"). This will be zero during the first round.
8. The (zero-indexed) number of the bank to be heisted (during the first round, the bank that would be heisted if no one else bet)
9. The number of credits currently available to the player.
10. The number of credits the player bet in the first round. (This is always zero in the first round.)
11. The number of credits the player will receive in its paycheck at the end of each game.
12. 1 if the player is currently receiving a paycheck, 0 if the player is unemployed
13. Player's rank on the leaderboard (not including rabble) as of the end of the previous game, 1-indexed. (Defined as 1+the number of players with strictly more credits at that time. E.g. during the first game, all players have rank 1.)
14. The mean number of credits held by all players (not including rabble) (represented as a decimal number)
15. The mean absolute deviation in the number of credits held by all players (not including rabble) (represented as a decimal number)
16. The maximum number of credits held by any player (i.e. the number of credits held by a rank 1 player, not including rabble)
17. The number of credits the player has stored in bank 0 account
18. Bank 1 account
19. Bank 2 account
20. Bank 3 account
21. Bank 4 account
22. The player's individual probability of victory at bank 0
23. Bank 1 probability
24. Bank 2 probability
25. Bank 3 probability
26. Bank 4 probability
27. The player's individual payout odds upon a successful heist at bank 0
28. Bank 1 odds
29. Bank 2 odds
30. Bank 3 odds
31. Bank 4 odds

In the first round of a game, a player program must print to stdout an integer between 0 and the total number of credits in that player's account. Any bet amount greater than the available credit balance is taken to be a max bet. Any other output (or error condition) will be interpreted as a zero bet.

In the second round of a game, a player program must print to stdout a string as described in the section "The Second Betting Round" above. An error condition here is taken to be the default action: go through with the heist as normal.

## Controller

The tournament will be run using this controller. Bot examples there as well. Still being tested. More code to come. Feel free to submit bug fixes (on github). Will be updated if any rules change as well.

To run a single tournament on your own machine, add a line to competitors.txt and then use:

```
python bankheist.py 1000

```

## Contest Rules

* Players may submit any number of player programs in any freely available language the programs of which may receive command line arguments.
* Submissions must include fairly explicit instructions for how to compile programs and run them on my PC, including names of tools needed and exact commands to be issued. Submission must include at least one command which executes the program and may have command line arguments appended directly to it.
* Submissions must also have a unique name to identify them (which contains no spaces).
* Programs must run in a reasonably short amount of time. (I'm not setting an upper bound on what constitutes reasonable. Rather, I will simply advise the creator any entry that seems to have an outsize execution time to speed it up.)
* Programs may *not* read or write to files. Nor may they use any other method of storing information between runs. The point of this challenge is to make complex decisions on the basis of limited/summarized information.
* Any and all of these rules are subject to change at any time if necessary. A message will be added at the *top* of this post indicating any such changes.
* This contest ends no sooner than one week after the last *user* submits posts his or her *first submission*. Modifications of existing submissions are allowed at any time up until the contest ends. I'll do my best to keep the current deadline updated in a message at the *top* of this post.
* This contest ends no sooner than one week after the last time the rules were changed, if any. I will do my best to leave comments for any users affected by any rule changes.
* You better bet I'll be participating in this contest myself. ;)

# Answer
> 6 votes
# Some "bad" examples of programs.

These are some bots I've written to test the controller. Mostly, they just do the minimum necessary thing to test one specific type of action. Depending on the level of participation in this KotH, anywhere from a few to all of these will be included in the final tournament, since a lot of the strategy in the game will come from dealing with the behaviors of lots of different bots.

I include them all here mostly as "usage" examples.

## Lurker

Never bet. If you're not beating this, rethink your strategy.

```
print 0

```

## PassivePanga

Always bet 69.

```
import sys

round = int(sys.argv[2])
myyattas = int(sys.argv[9])
if round == 1:
    if myyattas > 69:
        print "69"
    else:
        print "0"
else:
    print "!guncheck"

```

## KaylorrCriterion

Make a Kelly bet if and only if the Kelly Criterion is met. As this rarely happens with doing some "acquire intel" and "buy guard" first, this generally gets the same result as Lurker.

```
import sys
import ast
game,round,numplayers,alreadyplayed,numbet,yattasbet,numready,bankid,myyattas,mybet,mypayment,hired,myrank,mu_yattas,sigma_yattas,max_yattas = map(ast.literal_eval,sys.argv[1:17])
bankholdings = map(int,sys.argv[17:22])
bankprobs = map(float,sys.argv[22:27])
bankodds = map(float,sys.argv[27:32])

def get_bank(bettors,credits):
    selector = min(4,int(bettors+int(credits/100000.)/20))
    return bankprobs[selector],bankodds[selector]

if round == 1:
    if alreadyplayed < 0.37*numplayers or numbet==0:
        print 0
        #sys.stderr.write("1: %d,%d\n"%(alreadyplayed,numbet))
    else:
        ratiosofar = numbet/float(alreadyplayed)
        bettors = ratiosofar * numplayers
        ratesofar = yattasbet/float(numbet)
        credits = bettors*ratesofar
        p,b = get_bank(bettors,credits)
        f = (p*(b+1)-1)/b
        print max(int(f*myyattas),0)
        #sys.stderr.write("2: %d,%d\n"%(p,b))
else:
    if alreadyplayed < 0.37*numbet or numbet==0:
        print "!guncheck"
    else:
        p,b = get_bank(numbet,yattasbet)
        realp = p*numready/float(alreadyplayed)
        f = (realp*(b+1)-(1-240./(myyattas+240.)))/b
        print "!guncheck" if f>0 else "back out"

```

## gunHeCK

Make a Kelly bet if and only if the number of heisters seen so far indicate that the bet *will* meet the Kelly criterion (but don't back out if wrong). Typically does worse than Lurker

```
import sys
import ast
game,round,numplayers,alreadyplayed,numbet,yattasbet,numready,bankid,myyattas,mybet,mypayment,hired,myrank,mu_yattas,sigma_yattas,max_yattas = map(ast.literal_eval,sys.argv[1:17])
bankholdings = map(int,sys.argv[17:22])
bankprobs = map(float,sys.argv[22:27])
bankodds = map(float,sys.argv[27:32])

def get_bank(bettors,credits):
    selector = min(4,int(bettors+int(credits/100000.)/20))
    return bankprobs[selector],bankodds[selector]

if round == 1:
    if alreadyplayed < 0.37*numplayers or numbet==0:
        print 0
        #sys.stderr.write("1: %d,%d\n"%(alreadyplayed,numbet))
    else:
        ratiosofar = numbet/float(alreadyplayed)
        bettors = ratiosofar * numplayers
        ratesofar = yattasbet/float(numbet)
        credits = bettors*ratesofar
        p,b = get_bank(bettors,credits)
        f = (p*(b+1)-1)/b
        print max(int(f*myyattas),0)
        #sys.stderr.write("2: %d,%d\n"%(p,b))
else:
    print "!gunHeCK"

```

## Moni'sAddiction

Go "all in" unless already winning.

```
import sys
import random

round = int(sys.argv[2])
myrank = int(sys.argv[13])
mybet = int(sys.argv[10])

if round == 1:
    if random.random()<0.1:
        print 1
    else:
        print 69
else:
    if myrank>1:
        print "all in"
    else:
        if mybet==1:
            print "back out"
        else:
            print "!guncheck"

```

## HeCKuSumer

Always bet a small constant fraction of holdings.

```
import sys

round = int(sys.argv[2])
myyattas = int(sys.argv[9])

if round==1:
    print int(0.1*myyattas)
else:
    print "!guncheck"

```

## OC'sRandomTpyos

Change jobs a lot in early tournament. Spend all that money improving probabilities and odds. Then spend the last few games going all in. This would probably do a lot better without the going all in unless already in a top spot.

```
import sys
import ast
import random

game,round,numplayers,alreadyplayed,numbet,yattasbet,numready,bankid,myyattas,mybet,mypayment,hired,myrank,mu_yattas,sigma_yattas,max_yattas = map(ast.literal_eval,sys.argv[1:17])
bankholdings = map(int,sys.argv[17:22])
bankprobs = map(float,sys.argv[22:27])
bankodds = map(float,sys.argv[27:32])

if round == 1:
    if game<800 or myrank>3:
        print 1
    else:
        print myyattas/4
else:
    if game<800:
        if hired:
            print "change jobs"
        else:
            print random.choice(["acquire intel","buy guard"])
    else:
        if myrank>3:
            print "all in"
        else:
            print "!guncheck"

```

## HardHatUmar

Changes jobs whenever possible for most of the tournament. Avoids betting more than the minimum necessary. Does decently well, but not great.

```
import sys

game = int(sys.argv[1])
round = int(sys.argv[2])
hired = int(sys.argv[12])

if round==1:
    if game < 900 and hired:
        print 1
    else:
        print 0
else:
    print "change jobs"

```

# LimeadeSneaktar

Change jobs whenever possible during the first part of the tournament. Spend every other game double crossing. Does decently well even against SnitcherKing. Will probably fare more poorly once many other bots are double crossing and fingering. If not--the rules may need changing.

```
import sys
import ast

game,round,numplayers,alreadyplayed,numbet,yattasbet,numready,bankid,myyattas,mybet,mypayment,hired,myrank,mu_yattas,sigma_yattas,max_yattas = map(ast.literal_eval,sys.argv[1:17])
bankholdings = map(int,sys.argv[17:22])
bankprobs = map(float,sys.argv[22:27])
bankodds = map(float,sys.argv[27:32])

if round==1:
    print 1
else:
    if hired and game<900:
        print "change jobs"
    else:
        print "double cross"

```

## SnitcherKing

Always bet the minimum, and always finger. Does pretty well in small tournaments that include LimeadeSneaktar.

```
import sys

round = int(sys.argv[2])

if round == 1:
    print 1
else:
    print "finger"

```

## RaysFive01K

A bit more complicated--and therefore actually pretty good. Most of its advantage comes from depositing all winnings in early tournament (protecting them from double crossers) while driving up its win probabilities (and changing jobs to pay for all those guards and heists), then withdrawing them all at the end of the game (once they have earned serious interest and the probability of failing to withdraw is sufficiently low--though here losses to double crossers is a serious risk). This will definitely be in the tournament, and may or may not be a serious contender.

```
import sys
import ast
import random
game,round,numplayers,alreadyplayed,numbet,yattasbet,numready,bankid,myyattas,mybet,mypayment,hired,myrank,mu_yattas,sigma_yattas,max_yattas = map(ast.literal_eval,sys.argv[1:17])

bankholdings = map(int,sys.argv[17:22])
bankprobs = map(float,sys.argv[22:27])
bankodds = map(float,sys.argv[27:32])

if round ==1:
    if game < 900:
        print myyattas/10
    else:
        print 1
else:
    if game < 500 and hired:
        print random.choice(["change jobs","finger","buy guard"])
    elif game < 900:
        print "deposit"
    elif bankholdings[bankid]>0:
        print "withdraw"
    else:
        if alreadyplayed/float(numplayers)<0.5:
            print "finger"
        else:
            print "back out"

```

# Answer
> 2 votes
# Lone John

```
import sys
import ast

game,round,numplayers,alreadyplayed,numbet,creditsbet,numready,bankid,mycredits,mybet,mypayment,hired,myrank,mu_credits,sigma_credits,max_credits = map(ast.literal_eval,sys.argv[1:17])

bankholdings = map(int,sys.argv[17:22])
bankprobs = map(float,sys.argv[22:27])
bankodds = map(float,sys.argv[27:32])

if round == 1:
    if mycredits > 100 or hired:
        print(int(mycredits)/2)
    else:
        print(0)
else:
    if bankprobs[int(bankid)] > 0.6:
        print("all in")
    elif int(mypayment) > 50 :
        print("buy guard")
    elif int(mycredits) > 200 and int(game) < 900 and hired == "1":
        print("change jobs")
    elif bankprobs[int(bankid)] * (float(numready)+1)/(float(alreadyplayed)+1) < 0.30:
        print "withdraw"
    else:
        print "!guncheck"

```

Bribes guards until he has the probability to win, then goes all in. Alone.

Changes jobs when he needs more money to bribe guards.

---
Tags: game, random, king-of-the-hill
---


title: Take an input, a formula, and do f(x)

text:
# Question
Title: Take an input, a formula, and do f(x)
# What I want:

Take an input, *x*

Take a formula. It has to be capable of reading something in the format:

* ax^m + bx^n + cx^o ... where m, n, o and any terms after that can represent any value.
* coefficients, again for any number. For example, 6x^2. (That means 6(x^2))
* Doesn't necessarily have to put up with spaces
* times, divide, plus and minus
* brackets - up to stacking of *5*
* ANY negative numbers
* fractions
* To the power of *x* , these can be integeric (\<-- is not a word, but that is the best word I can make up!)
* If x = 5, you can put -x to get -5 and -x^2 is -(x^2). You could use (-x)^2

After it interprets the formula, it has to plug *x* into the function, then output the value.

## The Challenge:

* Do it in as less bytes as possible
* The lowest number of bytes wins!

### Note: I feel that I have included everything here, but if I haven't please comment below, and I will answer it within the next 30 minutes!

# Example

Key: bp = Background Process

* Give me an input, (x)

4

* Give me a formula:

2^x

* (bp) So I have to do 2 to the power of x, which is 2^4, which is 16
* Output: 16

# Answer
> 3 votes
# TI BASIC, 6 bytes

This might change, since the rules are still not totally stable, but I wanted to post this while I could.

```
:Prompt X,F
:F

```

Asks for `X`, then parses whatever formula is put into `F` and displays it.

If I could assume that `X` was already stored in the memory, it would be

# ~~TI BASIC (maybe), 0 bytes~~

~~Is this ok?~~Guess not. :-(

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


title: Cheapo Enigma machine (Cops)

text:
# Question
Title: Cheapo Enigma machine (Cops)
For robbers' post, Cheapo Enigma machine (Robbers)

A cop's submission will consist of a program/function that accepts a single byte of data and return a single byte of data. Every possible input must produce a unique output. (In the other words, your function must be bijective)

Robbers will attempt to create the inverse function of yours using as short a code as possible. So your objective is to make your function difficult to invert.

You cannot use built-ins that have the sole purpose of hashing or encryption.

Your byte count cannot exceed 64 bytes. 0-byte solutions are not eligible for winning.

# Input/Output format

8 bits (0 or 1), or a base-10 integer in range 1-256, 0-255 or -128 to 127. Can use standard I/O or file I/O. Function can also return a value as output. Input and output should belong to the same range (binary, 1-256, 0-255 or -128 to 127). The robber will also be required to use this range for input and output.

# Scoring

Ratio of your byte count to that of the best robber's attempt against you. Lowest score wins.

You are eligible to win (as a cop) only if a robber has attempted to defeat you. (This robber may be you)

# Example

C++, uses 0-255 range, 31 bytes

```
int x;
cin>>x;
cout<<(x+1)%256;

```

Possible robber submission in C++, 32 bytes

```
int f(int x)
{return x?x-1:255;}

```

*Using the same language or a similar algorithm isn't a requirement*

This gives a score of 31/32 = 0.97 to both the cop and the robber.

# Answer
> 7 votes
# Javascript, 11 8 bytes, Score: 8 / 5

```
x=>x^x/2

```

Simple implementation of gray code. Decoding usally needs a whole loop. Let's see who comes up with the smallest or even without a loop !

# Answer
> 7 votes
# C, 64 bytes, Score 64/71 = 0.901

```
T[256];f(x){srand(x&&f(x-1));for(;T[x=rand()%256]++;);return x;}

```

Takes input in the range \[0 255\].

Try it online! — on TIO (using GCC), this produces:

```
103,198,105,115,081,255,074,236,041,205,186,171,242,251,227,070,
124,194,084,248,027,232,231,141,118,090,046,099,051,159,201,154,
102,050,013,183,049,088,163,037,093,005,023,233,094,212,178,155,
180,017,014,130,116,065,033,061,220,135,112,062,161,225,252,001,
126,151,234,107,150,143,056,092,042,176,059,175,060,024,219,002,
026,254,067,250,170,058,209,230,148,117,216,190,097,137,249,187,
168,153,015,149,177,235,241,179,239,247,000,229,202,011,203,208,
072,071,100,189,031,035,030,028,123,197,020,075,121,036,158,009,
172,016,080,021,111,034,025,125,245,127,164,019,181,078,152,224,
077,052,188,095,119,108,134,043,085,162,004,211,054,226,240,228,
079,073,253,169,008,138,010,213,068,091,243,142,076,215,045,066,
006,196,132,173,222,048,246,032,133,007,244,185,195,217,160,120,
218,106,083,144,087,238,207,096,210,053,101,063,098,128,165,089,
140,012,192,131,047,039,022,147,184,109,182,193,199,237,018,069,
057,157,174,104,122,166,055,110,003,040,139,086,145,114,129,113,
206,167,191,214,146,221,136,038,156,082,200,029,044,204,223,064

```

Note that on other systems, it may produce different (but still valid) output, since C does not mandate a specific `rand` implementation. My submission is specifically the version running on TIO (as linked).

---

I'm quite disappointed that I wasn't able to get a version like my original (`f(x){return rand(srand(x*229))/229%256;}`) to work on TIO, since I think that's much more elegant. Since that only works on Clang running on OS X, it isn't fair for the competition. This one's still pretty awkward to reverse, so that's enough I guess.

# Answer
> 2 votes
# Jelly, 2/5

```
^H

```

Try it online to see the whole table.

# Answer
> 2 votes
# JavaScript, 44 bytes 22/3

```
x=>a.sort()[x]
for(a=[],i=0;i<256;)a[i]=i++;

```

Uses lexicographic sort (Javascript Default) to rearrange all the numbers from 0-255

Try it online!

# Answer
> 2 votes
# C (gcc), 32 27/30 bytes

Thanks to christoph for golfing 5 bytes.

```
f(x){x=x?f(x*5+1&255)+1:0;}

```

Try it online!

# Answer
> 1 votes
# JavaScript, 13 bytes 13/12

```
x=>(x<<9)%257

```

Input and output are both in the range 1-\>256

Try it online!

# Answer
> 1 votes
# Octave, 16/6

```
@(x)mod(x*3,256)

```

Try it online!

# Answer
> 1 votes
# Javascript, 11/8 bytes

```
x=>x**5%257

```

Domain/range is 1 through 256.

# Answer
> 1 votes
# Javascript, 27/29 bytes

```
x=>x-6?x*95%127+x*98%131:65

```

Edit: Range/Domain is 1..256. Generated via brute force, more or less.

# Answer
> 1 votes
# Java, 35 bytes

```
int a(int v){return (v*v+v)%512/2;}

```

Domain/Range are 0-255

# Answer
> 1 votes
# Ruby, 23 bytes

```
->x{('228'*x).to_i%257}

```

Range and domain is 0..255. Concatenate 228 to itself x times, then take the result modulo 257 (0 maps to 0). 228 is the first magic number after 9 that works for this range (gives distinct values that don't include 256).

# Answer
> 0 votes
## Python 3, 32 bytes 32/23

```
V=lambda x:((3+x)%16)*16+x//16

```

Domain/Range is 0-255.

Flips the first four bytes with the last four, and adds a three to the first bytes.

# Answer
> 0 votes
## Python 3, 55 bytes

```
y=lambda x,i=3:x if i==0 else pow(3,y(5*x,i-1),257)-1

```

Domain/Range is 0-255.

# Answer
> 0 votes
# brainfuck, 37/11

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

```

Try it online!

Not very good but range of 0-255

# Answer
> 0 votes
# Mathematica, 13 bytes

```
Mod[#^7,257]&

```

Uses the range \[1..256\], although it's equally valid on the range \[0..255\]. To see the entire table, copy/paste one of the following lines of code into the Wolfram sandbox:

```
Array[ Mod[#^7,257]&, 256]   (for a list of values in order)
Array[ Rule[#,Mod[#^7,257]]&, 256]   (for a list of input-output rules)

```

---
Tags: permutations, cops-and-robbers
---


title: Lossy or Lossless?

text:
# Question
Title: Lossy or Lossless?
Given an audio file, determine whether it is encoded in a lossy format or a lossless format. For the purposes of this challenge, only the following formats need to be classified:

## Rules

* If input is taken in the form of a filename, no assumptions should be made about the filename (e.g. the extension is not guaranteed to be correct for the format, or even present).
* There will be no ID3 or APEv2 metadata present in input files.
* Any two unique and distinguishable outputs may be used, such as `0` and `1`, `lossy` and `lossless`, `foo` and `bar`, etc.

## Test Cases

The test cases for this challenge consist of a zip file located here which contains two directories: `lossy` and `lossless`. Each directory contains several audio files that are all 0.5-second 440 Hz sine waves, encoded in various formats. All of the audio files have extensions matching the formats above, with the exception of `A440.m4a` (which is AAC audio in a MPEG Layer 4 container).

# Answer
# Jelly, ~~7~~ 5 bytes

```
ƈƈeØA

```

Lossy formats return **0**, lossless formats return **1**.

Try it online! (permalinks in Gist)

### Background

The formats we have to support have the following magic numbers, i.e., they start with these bytes.

```
Format    Header (text)       Header (hex)
-----------------------------------------------------------------------------------
AC3       .w                  0B 77
AMR       #!AMR               23 21 41 4D 52
AAC       ÿñP@..ü             FF F1 50 40 00 1F FC
  M4A     ... ftypM4A         00 00 00 20 66 74 79 70 4D 34 41 20
MP2       ÿû                  FF FB
MP3       ÿû                  FF FB
OGG       OggS                4F 67 67 53
WMA       0&²u.fÏ.¦Ù.ª.bÎl    30 26 B2 75 8E 66 CF 11 A6 D9 00 AA 00 62 CE 6C

AIFF      FORM????AIFF        46 4F 52 4D ?? ?? ?? ?? 41 49 46 46
FLAC      fLaC                66 4C 61 43
TTA       TTA1                54 54 41 31
  FFM2    FFM2                46 46 4D 32
WAV       RIFF????WAVE        52 49 46 46 ?? ?? ?? ?? 57 41 56 45

```

Indented entries are containers for the preceding format that appear in the test cases. `?` denotes a variable byte. `.` denotes an unprintable byte. All other bytes are displayed as their ISO 8859-1 character.

By looking only at the second byte, we can determine the format in an easy way:

**Lossless formats have an uppercase letter as their second byte, while lossy formats do not.**

### How it works

```
ƈƈeØA  Main link. No arguments.

ƈ      Read a char from STDIN and set the left argument to this character.
 ƈ     Read another char from STDIN and set the return value to this character.
   ØA  Yield the uppercase alphabet, i.e., "ABCDEFGHIJKLMNOPQRSTUVWXYZ".
  e    Exists; return 1 if the return value (second char on STDIN) belongs to the
       uppercase alphabet, 0 if not.

```
> 17 votes

# Answer
# C, ~~82~~ ~~80~~ 32 bytes

Inspired by @Dennis' answer, this can be reduced much further:

```
main(){return getchar()&200^64;}

```

Pipe the file data to stdin. Returns 0 for lossless, or nonzero for lossy.

Or the original longer check:

```
char v[5];main(){scanf("%4c",v);return*v&&strstr("fLaC FORM RIFF TTA1 FFM2",v);}

```

Pipe the file data to stdin. Returns nonzero (1) for lossless, or 0 for lossy.

From what I can tell, all the formats you listed have separate magic numbers (except AIFF/WAV, but those are both lossless anyway), so this just checks that magic number for a known lossless value. The `*v&&` is just to protect against matching files which start with a null byte (M4A).

I've included the values I found in spec sheets (`fLaC` = FLAC, `RIFF` = WAV/AIFF, `TTA1` = TTA), and `FORM` = AIFF and `FFM2` = TTA are from the sample files provided (I can only guess these are wrapper formats or later versions).

---

Or a shorter feels-like-cheating alternative:

# Bash + file, 61 bytes

```
N="$(file "$1")";[[ $N = *": d"* || $N = *IF* || $N = *FL* ]]

```

Takes the filename as an argument. Returns 0 for lossless, or nonzero for lossy.

Does exactly what you'd expect; asks `file` what the filetype is, then checks for known patterns. TTA matches `: d` (`: data`), AIFF / WAV match `IF`, and FLAC matches `FL`. None of the lossless results match any of these, and I've tested that it still works if the filenames are removed.

---

Testing:

```
for f in "$@"; do
    echo "Checking $f:";
    ./identify2 "$f" && echo "shorter C says LOSSLESS" || echo "shorter C says LOSSY";
    ./identify < "$f" && echo "longer C says LOSSY" || echo "longer C says LOSSLESS";
    ./identify.sh "$f" && echo "file says LOSSLESS" || echo "file says LOSSY";
done;

# This can be invoked to test all files at once with:
./identify_all.sh */*

```
> 9 votes

# Answer
# GS2, 3 bytes

```
◄5ì

```

Lossy formats return **0**, lossless formats return **1**.

Try it online! (permalinks in Gist)

### Background

The formats we have to support have the following magic numbers, i.e., they start with these bytes.

```
Format    Header (text)       Header (hex)
-----------------------------------------------------------------------------------
AC3       .w                  0B 77
AMR       #!AMR               23 21 41 4D 52
AAC       ÿñP@..ü             FF F1 50 40 00 1F FC
  M4A     ... ftypM4A         00 00 00 20 66 74 79 70 4D 34 41 20
MP2       ÿû                  FF FB
MP3       ÿû                  FF FB
OGG       OggS                4F 67 67 53
WMA       0&²u.fÏ.¦Ù.ª.bÎl    30 26 B2 75 8E 66 CF 11 A6 D9 00 AA 00 62 CE 6C

AIFF      FORM????AIFF        46 4F 52 4D ?? ?? ?? ?? 41 49 46 46
FLAC      fLaC                66 4C 61 43
TTA       TTA1                54 54 41 31
  FFM2    FFM2                46 46 4D 32
WAV       RIFF????WAVE        52 49 46 46 ?? ?? ?? ?? 57 41 56 45

```

Indented entries are containers for the preceding format that appear in the test cases. `?` denotes a variable byte. `.` denotes an unprintable byte. All other bytes are displayed as their ISO 8859-1 character.

By looking only at the second byte, we can determine the format in an easy way:

**Lossless formats have an uppercase letter as their second byte, while lossy formats do not.**

### How it works

```
     (implcit) Push the entire input from STDIN as a string on the stack.
◄    Push 1.
 5   Get the strings character at index 1, i.e., its second character.
  ì  Test if the character is an uppercase letter.

```
> 6 votes

# Answer
# JavaScript (ES6), 20 bytes

```
c=>/^[fFRT]/.test(c)

```

---

## Explanation

Takes the contents of the file as an input and returns `true` if the file is lossless or `false` if it is lossy by testing the first character of that input to see if it is an `f`, `F`, `R` or `T`.

---

## Try It

Paste the contents of a file into the `textarea`.

```
f=
c=>/^[fFRT]/.test(c)
i.addEventListener("input",_=>console.log(f(i.value)))
```

```
<textarea id=i></textarea>
```

---

# Second effort, ~~81~~ 63 bytes

Fetches the contents of a file from a provided URL, which turned out to be overkill.

```
u=>fetch(u).then(r=>r.text()).then(t=>alert(/^[fFRT]/.test(t)))

```

---

## First effort, ~~146~~ ~~116~~ 89 bytes

Invalid as mime types are tied to extensions and, apparently, response headers qualify as additional input.

```
u=>fetch(u).then(r=>alert(/aiff|flac|tta|wave|wav$/.test(r.headers.get("Content-Type"))))

```
> 1 votes

# Answer
# Chip, 11 bytes

```
~Z~S
t'G~aF

```

Shamelessly replicated Dennis' Jelly answer in Chip.

Lossless returns `0x0`, lossy returns `0x1`.

Try it online, links in gist (thanks Dennis for the TIO strategy here)

### Explain!

```
~Z~S
t'

```

This portion is housekeeping: it `S`kips the first byte, and `t`erminates after the second.

```
G~aF

```

This is the meat of the decision. Each input byte is accessed by the bits `HGFEDCBA`. If `G` is set, and `F` is not, that means the byte is within the range `0x40` to `0x5f` (which is roughly equivalent to 'uppercase', and good enough for the task at hand).

However, for byte savings, I invert this decision from `G and (not F)` to `(not G) or F`, since or's can be implicit in Chip.

This resultant true/false value is then placed into `a`, which is the lowest bit of the output. (All other bits will be zero). In the TIO, I run the output through hexdump so that the values are visible.

Equivalently, in C-ish, one would say something like:

```
out_byte = !(in_byte & 0x40) && (in_byte & 0x20)

```
> 1 votes

# Answer
# Cubix, 16 bytes

```
$-!u'HIa'@/1@O<

```

Net form:

```
    $ -
    ! u
' H I a ' @ / 1
@ O < . . . . .
    . .
    . .

```

# Try it yourself

You should input the file decimal byte values in a separated list. The separator doesn't matter, anything that is not a digit or a minus sign suffices. The code really only cares about the first byte, so you can leave out the rest of the file if you like. The program outputs `0` for lossless, and `1` for lossy. Try it here! The default input uses a FLAC header.

# Explanation

The nice thing about files is that (nearly) all of them have a so-called magic. Those are the first few bytes of the file. Good software doesn't check the file extension, but rather the file magic to see if it can handle a certain file.

Dennis has found a way to use this magic to find the compression type, but the fact that he discarded the first byte made me want to try to come up with a method that used the first byte, rather than the second. After all, this community is all about saving bytes.

Here's a list of the first bytes of the different file types. I ordered them into two groups: lossy and lossless. Here are the values of their first byte in decimal, hexadecimal and binary. You might see a pattern already...

```
Lossy:                  Lossless:
255:0xFF:0b11111111     102:0x66:0b01100110
 79:0x4F:0b01001111      84:0x54:0b01010100
 35:0x23:0b00100011      82:0x52:0b01010010
 11:0x0B:0b00001011      70:0x46:0b01000110
  0:0x00:0b00000000

```

The pattern I saw, was that the second bit (counted from left to right) was always on on the "lossless" bytes and the fifth bit was always off. This combination does not appear in any of the lossy formats. To "extract" this, we would simply do a binary AND (by `0b01001000 (=72)`) and then compare to `0b01000000 (=64)`. If both are equal, the input format is lossless, otherwise it's lossy.

Sadly, Cubix doesn't have such a comparison operator, so I used subtraction (if the result is 64, this yields 0, and it results in 8, -56 or -64 otherwise. I'll get back to this later.

First, let's start at the beginning of the program. The binary AND is done using the `a` command:

```
'HIa
'H   # Push 0b01001000 (72)
  I  # Push input
   a # Push input&72

```

Then, we compare to 64 using subtraction (note we hit a mirror that reflects the IP to the top face \[first line, second character, pointing south\] in the middle of this part).

```
'@-
'@  # Push 0b01000000 (64)
  - # Subtract from (input&72)
    # Yields 0 for lossy, non-zero otherwise

```

After the IP is turned around by the `u`, we use some control flow to push a `1` to the stack if (and only if) the top of the stack is non-zero:

```
!$1
!   # if top = 0:
 $1 #   do nothing
    # else:
  1 #   push 1

```

After we wrap around the cube, we hit the `<` instruction, which points the IP west on the fourth line. All that's left to do is output and terminate.

```
O@
O  # Output top of the stack as number
 @ # End program

```

So, the program outputs `0` for lossless, and `1` for lossy.
> 1 votes

---
Tags: code-golf, decision-problem, classification, audio
---


title: Appends or Prepends? Depends

text:
# Question
Title: Appends or Prepends? Depends
> Brain-flak turns one year old tomorrow! In honor of it's birthday, we're having a PPCG style birthday party, where several users post brain-flak related questions! Help us celebrate! :)

---

Brain-flak is an esoteric language I wrote where all of the commands are brackets and all of the brackets must be fully matched. To borrow my own definition:

* For the purpose of this challenge, a "bracket" is any of these characters: `()[]{}<>`.
* A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

```
()
[]{}

```

Or if every subelement inside of it is also matched.

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

```

Subelements can also be nested several layers deep.

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

```
* A string is considered "Fully matched" if and only if:

1. Every single character is a bracket,
    2. Each pair of brackets has the correct opening and closing bracket and in the right order

In celebration of brain-flak's first birthday, today's challenge is about taking an unbalanced set of brackets, and determining what types of operations are needed to make it valid brain-flak.

* For example, `((` is not valid brain-flak code, but if we append `))` to it, it becomes `(())`, which is fully balanced, and therefore valid brain-flak. That makes this input *appendable*.
* Similarly, `>}` is not valid, but we can prepend `{<` to it to make `{<>}`, which is valid. That makes this input *prependable*.
* Some inputs are slightly more complicated. For example, `)][({` cannot be made valid purely by appending or prepending. But it *can* be made valid by prepending `[(` and appending `})]`. Therefore, this input is both *prependable* and *appendable*.
* Lastly, some inputs can never be made valid brain-flak code by any combination of appending or prepending. For example, `(>` can never be made valid. (Prepending `<` creates `<(>`, and appending `)` creates `(>)`, neither of which are valid) Therefore, this input is neither appendable or prependable.

For today's challenge, you must write a program or function that takes a string of brackets and determines if the string is

```
appendable
prependable
both
neither

```

You may pick what values you use to represent for each case. For example, outputting `1, 2, 3, 4`, or `'a', 'p', 'b', 'n'`, or `1, 'foo', 3.1415, -17`, or whatever is fine. As long as each output is *distinct* and *consistent*, that's fine. You *must* however, clearly specify which output corresponds to which case.

You may return this value in whichever format is most convenient (for example, returning from a function, printing to STDOUT, modifying arguments, writing to a file, etc.).

You can assume that the input will never be valid brain-flak or empty.

# Examples

The following inputs are all *prependable*:

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

```

These are all *appendable*:

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

```

These are all *both*:

```
))((
>()[(()){
>{

```

And these are all *neither*:

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

```

As usual, this is , so standard loopholes apply, and the shortest answer in bytes wins!

---

This challenge is particularly difficult in brain-flak, so maximum brownie points to any and every answer written in brain-flak. :)

# Answer
# Jelly, ~~33 32 37 35~~ 34 bytes

*bug found, horrible fix +5 bytes, better fix - 2 bytes, using a trick of Adnan's I saw here for -1 more.*

```
“({[<“)}]>”Z;@WœṣF¥/µÐLO‘&2µIṀ>0ȯQ

```

Return values:

```
prepends [2]
 appends [0]
    both [2,0]
 neither 1

```

(Invalid input returns spurious results, although valid Brain-flack, returns `[]`.)

**Try it online!** \- a test suite (prints mushed representations, so `20` for `[2,0]`, and ignores lines containing any `-`).
> 6 votes

# Answer
# Retina, ~~41~~ ~~40~~ 41 bytes

*1 byte saved thanks to @MartinEnder*

```
+`\(\)|\[]|{}|<>

[]})>]+
1
\W+
0
...+
01

```

Try it online!

* Prependable is `1`
* Appendable is `0`
* Both is `10`
* None is `01`

### Edits

* Gained 1 byte to fix bug noticed by @Neil
> 5 votes

# Answer
## Batch, 337 bytes

```
@echo off
set/ps=
:g
set "t=%s:<>=%
set "t=%t:()=%
set "t=%t:[]=%
set "t=%t:{}=%
if not "%t%"=="%s%" set "s=%t%"&goto g
set "s=%s:<=[%
set s=%s:>=]%
set s=%s:(=[%
set s=%s:)=]%
set s=%s:{=[%
set s=%s:}=]%
:l
if %s:~,2%==]] set s=%s:~1%&goto l
:r
if %s:~-2%==[[ set s=%s:~,-1%&goto l
if not _%s:~2%==_ set s=[]
echo %s%

```

Outputs `]` for prepend, `[` for append, `][` for both, `[]` for neither.
> 3 votes

# Answer
# Haskell, ~~115~~ 108 bytes

EDIT:

* -7 bytes: Use more guards.

```
(""#)
s#""=[s>"",1>0]
s#(c:d)|Just a<-lookup c$zip"([{<"")]}>"=(a:s)#d|(a:b)<-s=[1|a==c]>>b#d|0<1=take 1$s#d

```

Try it online!

Use like `(""#) "))"`. Results are given as:

```
[False,True]: needs nothing
[False]: prependable
[True,True]: appendable
[True]: both
[]: neither

```

# How it works

* The output encoding is chosen such that a need to prepend is signaled by dropping the second element of the result for the remainder, if any, while a complete mismatch is signaled by dropping all of them.
* `s#d` parses a remaining string `d`, given a string/stack `s` of expected closing brackets.
    + The `s#""` line checks if all closing brackets have been found by the end of the string, otherwise appending is needed.
    + The first branch of `s#(c:d)` checks if the next character `c` is an opening bracket, and if so leaves the corresponding closing bracket on the stack for the recursion.
    + Otherwise, if the stack contains closing brackets, the second branch checks if the top one matches the next character, and if not, returns an empty list instead of recursing.
    + Lastly, in the last branch the stack is empty, and we have an unmatched closing bracket that may be fixed by prepending, before recursing.
> 3 votes

# Answer
# PHP, 137 Bytes

```
for($c=1;$c;)$a=preg_replace("#<>|\(\)|\[\]|\{\}#","",$a=&$argn,-1,$c);echo($a=preg_replace(["#[]})>]+#","#[[{(<]+#"],[1,2],$a))<13?$a:0;

```

1 =\>appendable,

2 =\>prependable,

12=\>both,

0 =\>neither

Testcases
> 2 votes

# Answer
# Japt, 44 bytes

```
=Ue"%(%)|%[]|\{}|<>" ®c -1&2|1})f31 |UfD |Ug

```

Outputs `1` for prependable, `3` for appendable, `13` for both, and `31` for neither.

Test it online! or Verify all test cases at once.

### How it works

```
 =Ue"%(%)|%[]|\{}|<>" ®   c -1&2|1})f31 |UfD |Ug
U=Ue"%(%)|%[]|\{}|<>" mZ{Zc -1&2|1})f31 |UfD |Ug

                    // "(((()()())))}"  "([({}{})"    ">()[(()){"  "((((<>()]"
Ue"%(%)|%[]|\{}|<>" // Recursively remove all instances of "()", "[]", "{}", and "<>" from U.
                    // "}"              "(["          ">[{"        "((((]"
mZ{Zc -1&2|1}       // Replace each char Z with (Z.charCodeAt() - 1) & 2 | 1.
                    // "1"              "33"          "133"        "33331"
U=                  // Save the result in U.
f31 |UfD |Ug        // Match all instances of "31" and "13" (D = 13) and bitwise-OR the results with the first char.
                    // null|null|1      null|null|3   null|13|1    31|null|3
                    // 1                3             13           31
                    // Implicit: output result of last expression

```
> 2 votes

---
Tags: code-golf, string, balanced-string, classification, brain-flak
---


title: The bunker of the math lecturer

text:
# Question
Title: The bunker of the math lecturer
After giving back the results of the last topology exam to his students, Pr. Manifold was worried about complaints.

Since he is aware his students know where his office is located, Prof. Manifold decided to transform his office into a bunker with a 10 digit password (all characters are digits).

But he suspected his students to be very clever (despite having tremendously bad grades).

Knowing that, he's not going to pick a password containing certain sequences, such as his StackExchange ID, university parking spot number, and annual salary.

## Your task

Your program or function will take as input an array of integers. No single integer will contain duplicate digits, which implies that none of the integers will have more than 10 digits.

Your code will output how many unique 10 digit passwords Prof. Manifold can choose, taking into account that correct passwords

* must contain each digit 0-9 exactly once, and
* must not contain any of the sequences present in the input array.

### Example

Input: `[18062,6042,35876]`

* `1806234579`, `6042135789`, `3587612409`, `3418062579`, `1237896042`, and `1243587609` are all incorrect passwords, because they each contain at least one of the sequences present in the input array.
* `0113456789` is an incorrect password, because the professor's password must contain each digit exactly once.
* `0123456789` is a correct password, because it doesn't contain any sequence present in the array, and it contains each digit exactly once.

Test case:

```
[18062,6042,35876] -> 3622326

```

This is , so the shortest answer in bytes wins!

# Answer
> 2 votes
# Jelly, ~~14~~  11 bytes

-3 bytes thanks to Dennis (avoid a chain separation allowing some implicit actions; use a filter to avoid the two byte `œ&` multi-set intersection I was using.)

```
⁵ḶŒ!Ẇf¥ÐḟDL

```

**Try it online!** \- the specified version is far too slow for the online interpreter, so **this is a proof of concept** test suite:
\- it does the same thing for only **5** digits `01234`,
\- the first example is the empty list, yielding `120` as expected (**5!**),
\- the last returns `1` as the only permutation still available to the professor is `04321`,
\- an offline run of the full version with input `[18062,6042,35876]` yielded `3622326` as expected.

### How?

```
⁵ḶŒ!Ẇf¥ÐḟDL - Main link: list a
⁵           - literal 10
 Ḷ          - lowered range: [0,1,2,3,4,5,6,7,8,9]
  Œ!        - all permutations
         D  - decimal list (vectorises across a)
       Ðḟ   - filter discard (from the permutations) if: (note - non-empty is truthy)
      ¥     -   last two links as a dyadic operation:
    Ẇ       -     all sublists (of the current permutation)
     f      -     filter keep (if in the decimal list)
          L - length

```

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


title: Write a mutating, replicating program

text:
# Question
Title: Write a mutating, replicating program
This is a variant on the self-replicating program, defined here as a program that outputs its source (or a ). Below is an example of a self-replicating program in Python:

```
s = 's = %r\nprint(s%%s)'
print(s%s)

```

When run from a file, this script should output itself.

Instead of a self-replicating program, I want you to write a mutating, replicating program. This is a program that outputs something similar to its source, but with a mutation. The mutated source *must* also be able to replicate, but it should change the functionality of the program in some way. Here is an example:

```
s = 's = %r\ns = s.replace(s[-17],str(int(s[-17])+222))\nprint(s%%s)'
s = s.replace(s[-17],str(int(s[-17])+222))
print(s%s)

```

When this Python script is run, it outputs the following program:

```
s = 's = %r\ns = s.replace(s[-17],str(int(s[-17])+224224224))\nprint(s%%s)'
s = s.replace(s[-17],str(int(s[-17])+224224224))
print(s%s)

```

If you repeat a number of times, you will see that it continues to mutate but remain functional.

Incorporating a raw dynamic environment variable in your code, like a comment with a timestamp, is boring. Don't do that.

**Edit:** For that matter, let's follow the standard quine rule of no input.

This is so the shortest in bytes wins.

**Clarifications:** I've been asked to clarify, but without much information I'm not sure what needs clarifying. Here's my best shot:

* Each iteration should have source code that is different from the last.
* The iteration must still run.
* The iteration must still replicate according to the same rules.
* Comments or strings can't be the only thing that changes. In dzaima's answer the operations on the string are duplicated, not just the contents of the string--so that is valid.
* Each iteration must be runnable in the same language you started in.

# Answer
> 3 votes
# Jelly, 4 bytes

```
⁾ṘȮṘ

```

**Try it online!**

(Equivalent to the 5-byte: `“ṘȮ”Ṙ`)

Exponentially spawns:

```
“ṘȮ”ṘȮ
“ṘȮ”ṘȮṘȮ
“ṘȮ”ṘȮ“ṘȮ”ṘȮṘȮ
“ṘȮ”ṘȮṘȮ“ṘȮ”ṘȮ“ṘȮ”ṘȮṘȮ
“ṘȮ”ṘȮ“ṘȮ”ṘȮṘȮ“ṘȮ”ṘȮṘȮ“ṘȮ”ṘȮ“ṘȮ”ṘȮṘȮ

```

Since  is a monadic atom which prints a Jelly representation of its input and then yields it's input, and `Ȯ` is a monadic atom which prints its input and yields it's input (neither printing any newlines), while `“...”` defines a list of characters. So each `“ṘȮ”Ṙ` prints `“ṘȮ”` and yields to the following `Ȯ` which prints `ṘȮ` and yields... a trailing `Ȯ` finally yields for the programs return value, which is implicitly printed, so the pattern will continue until resources no longer suffice.

# Answer
> 2 votes
# SOGL, 9 bytes

```
:+q$o”q$o

```

Explanation:

```
:+q$o”     push that string
      q    output it in a new line without popping
       $   push "”"
        o  output that
           implicitly output the original string (in a new line)

```

The iterations go as (one per line)

```
:+q$o”¶:+q$o
:+q$o:+q$o”¶:+q$o:+q$o
:+q$o:+q$o:+q$o:+q$o”¶:+q$o:+q$o:+q$o:+q$o:+q$o:+q$o:+q$o:+q$o”¶:+q$o:+q$o:+q$o:+q$o:+q$o:+q$o:+q$o:+q$o

```

and the next one is 31424 characters long.

The first iteration is

```
:+q$o”        push that string
      ¶       no-op
       :+     add the string to itself
         q    output it in a newline without popping
          $o  append "”"

```

and the next:

```
:+q$o:+q$o”             push that string
           ¶            no-op
            :+          add the string to itself
              q         output it in a newline without popping
               $o       append "”"
                 :+q$o  the same

```

This should never break from what I can see (well except hitting javas string length limit or something), because only the last string is used and the rest of the code is just `multiply, output`.

note: newlines and  are completely interchangeable in SOGL.

# Answer
> 2 votes
# Pyth, 11 bytes

```
jN*2]"jN*4[

```

Try it

Try it online

Gets exponentially longer. Based on this Pyth Quine.

## first 4 iterations

```
jN*2]"jN*4[
jN*4["jN*4[
jN*4["jN*4["jN*4["jN*4[
jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4["jN*4[

```

## Explanation

```
jN*4]"jN*4[
     "jN*4[                 # The String "jN*4["
    ]                       # Make it into a list with one element
  *4                        # Quadruple that list
jN                          # join on quote (N='"')

jN*4["jN*4["jN*4["jN*4[
                 "jN*4[     # The string "jN*4["
                [           # List with the string: ["jN*4["]
              *4            # Quadruple that list
            jN              # Join on quote
     "jN*4["                # The string "jN*4["
    [                       # Put both strings into a list
  *4                        # Quadruple that list
jN                          # join on quote (N='"')

```

(I could probably prove this rigoriosly using induction, but I'm not in the mood for that.) This should (theoretically always work because) it's just even multiples of `jN*4["`. Every second occurence of that sequence of characters is interpreted as a string because of the `"` of the previous one. The `[` of the previous one then puts that string into a list together with what the next one produces. Then that list is repeated four times and joined to string with `"`.

# Answer
> 2 votes
# Python 2, 33 bytes

```
_='_=%r;print _%%_*2;';print _%_;

```

Ideone

Doubles in size. (This is technically only true from the third iteration onwards) Based on this Quine. Similar to my Pyth answer.

### iterations

```
_='_=%r;print _%%_*2;';print _%_;

_='_=%r;print _%%_*2;';print _%_*2;

_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;

_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;
_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;

_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;
_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;
_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;
_='_=%r;print _%%_*2;';print _%_*2;_='_=%r;print _%%_*2;';print _%_*2;

```

---
Tags: code-golf
---


title: Generate a Padovan Spiral

text:
# Question
Title: Generate a Padovan Spiral
## Introduction

Similar to the Fibonacci Sequence, the Padovan Sequence (OEIS A000931) is a sequence of numbers that is produced by adding previous terms in the sequence. The initial values are defined as:

```
P(0) = P(1) = P(2) = 1

```

The 0th, 1st, and 2nd terms are all 1. The recurrence relation is stated below:

```
P(n) = P(n - 2) + P(n - 3)

```

Thus, it yields the following sequence:

```
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, ...

```

Using these numbers as side lengths of equilateral triangles yields a nice spiral when you place them all together, much like the Fibonacci Spiral:

Image courtesy of Wikipedia

---

## Task

Your task is to write a program that recreates this spiral by graphical output, with input corresponding to which term.

## Rules

* Your submission must be able to handle at least up to the 10th term (9)
* Your submission must be a full program or function that takes input and displays a graphical result (either outputs an image or graphs, etc)
* You must show proof of your graphical output in your submission
* Rotations of the output are allowed, in 60 degree multiples, with the same representation
* Going counter-clockwise is also allowed
* Standard loopholes are forbidden

You may assume that input will be \>0 and that correct format of input will be given.

## Scoring

This is , so the shortest code in bytes wins. Happy New Years everyone!

# Answer
> 12 votes
# Mathematica, ~~119~~ 108 bytes

*Thanks to Martin Ender for saving 11 bytes!*

```
±n_:=If[n<4,1,±(n-2)+±(n-3)];Graphics@Line@ReIm@Accumulate@Flatten@{0,z=I^(2/3),±# z^(#+{2,4,1})&~Array~#}&@

```

Unnamed function taking a positive integer argument (1-indexed) and returning graphics output. Example output for the input `16`:

Developed simulataneously with flawr's Matlab answer but with many similarities in design—even including the definition `I^(2/3)` for the sixth root of unity! Easier-to-read version:

```
1  (±n_:=If[n<4,1,±(n-2)+±(n-3)];
2   Graphics@Line@ReIm@
3   Accumulate@Flatten@
4   {0,z=I^(2/3),±# z^(#+{2,4,1})&~Array~#}
5  ])&

```

Line 1 defines the Padovan sequence `±n = P(n)`. Line 4 creates a nested array of complex numbers, defining `z` along the way; the last part `±# z^(#+{2,4,1})&~Array~#` generates many triples, each of which corresponds to the vectors we need to draw to complete the corresponding triangle (the `±#` controls the length while the `z^(#+{2,4,1})` controls the directions). Line 3 gets rid of the list nesting and then calculates running totals of the complex numbers, to convert from vectors to pure coordinates; line 2 then converts complex numbers to ordered pairs of real numbers, and outputs the corresponding polygonal line.

# Answer
> 9 votes
# Matlab, ~~202~~ 190 bytes

```
N=input('');e=i^(2/3);f=1/e;s=[0,e,1,f,-e,e-2];l=[1,1,1,2];M=N+9;T=[l,2:M-3;2:M+1;3:M+2];for k=5:N;l(k)=l(k-2)+l(k-3);s(k+2)=s(k+1)+e*l(k);e=e*f;end;T=[T;T(1,:)];plot(s(T(:,1:N)));axis equal

```

Output for `N=19` (1-based indexing):

### Explanation

The rough idea is basically working with complex numbers. Then the edges of the triangles point always in the direction of a sixth root of unity.

```
N=input('');                         % Fetch input
e=i^(2/3);                           % 6th root of unity
f=1/e;                               %  "
s=[0,e,1,f,-e,e-2];                  % "s" is a list of vertices in the order as the spiral is defined
l=[1,1,1,2];                         % "l" is a list of edge-lengths of the triangles
for k=5:N;                           % if we need more values in "l"/"s" we calculate those
    l(k)=l(k-2)+l(k-3);
    s(k+2)=s(k+1)+e*l(k);
    e=e*f;
end;
M=N+9;
T=[[1,1,1,2,2:M-3];2:M+1;3:M+2]';    % this matrix describes which vertices from s are needed for each triangle (the cannonical way how meshes of triangles are stored)
trimesh(T(1:N,:),real(s),imag(s));   % plotting the mesh, according to "T"
axis equal

```

# Answer
> 7 votes
# PHP + SVG , 738 Bytes

```
<?php
$a=[1,1,1];
for($i=0;$i<99;)$a[]=$a[$i]+$a[++$i];
$d=$e=$f=$g=$x=$y=0;
$c=[333,999];
$z="";
foreach($a as$k=>$v){
if($k==$_GET['n'])break;
$h=$v/2*sqrt(3);
if($k%6<1){$r=$x+$v/2;$s=$y+$h;$t=$r-$v;$u=$s;}
if($k%6==1){$r=$x-$v/2;$s=$y+$h;$t=$x-$v;$u=$y;}
if($k%6==2){$r=$x-$v;$s=$y;$t=$r+$v/2;$u=$y-$h;}
if($k%6==3){$r=$x-$v/2;$s=$y-$h;$t=$r+$v;$u=$s;}
if($k%6==4){$r=$x+$v/2;$s=$y-$h;$t=$r+$v/2;$u=$y;}
if($k%6>4){$r=$x+$v;$s=$y;$t=$r-$v/2;$u=$y+$h;}
$d=min([$d,$r,$t]);
$e=max([$e,$r,$t]);
$f=min([$f,$s,$u]);
$g=max([$g,$s,$u]);
$p="M$x,{$y}L$r,{$s}L$t,{$u}Z";
$z.="<path d=$p fill=#{$c[$k%2]} />";
$x=$r;
$y=$s;
}
?>
<svg viewBox=<?="$d,$f,".($e-$d).",".($g-$f)?> width=100% height=100%>
<?=$z?>
</svg>

```

## Output for 16

```
<svg viewBox=-53,-12.124355652982,75.5,42.435244785437 width=100% height=100%>
<path d=M0,0L0.5,0.86602540378444L-0.5,0.86602540378444Z fill=#333 /><path d=M0.5,0.86602540378444L0,1.7320508075689L-0.5,0.86602540378444Z fill=#999 /><path d=M0,1.7320508075689L-1,1.7320508075689L-0.5,0.86602540378444Z fill=#333 /><path d=M-1,1.7320508075689L-2,0L0,0Z fill=#999 /><path d=M-2,0L-1,-1.7320508075689L0,0Z fill=#333 /><path d=M-1,-1.7320508075689L2,-1.7320508075689L0.5,0.86602540378444Z fill=#999 /><path d=M2,-1.7320508075689L4,1.7320508075689L0,1.7320508075689Z fill=#333 /><path d=M4,1.7320508075689L1.5,6.0621778264911L-1,1.7320508075689Z fill=#999 /><path d=M1.5,6.0621778264911L-5.5,6.0621778264911L-2,-8.8817841970013E-16Z fill=#333 /><path d=M-5.5,6.0621778264911L-10,-1.7320508075689L-1,-1.7320508075689Z fill=#999 /><path d=M-10,-1.7320508075689L-4,-12.124355652982L2,-1.7320508075689Z fill=#333 /><path d=M-4,-12.124355652982L12,-12.124355652982L4,1.7320508075689Z fill=#999 /><path d=M12,-12.124355652982L22.5,6.0621778264911L1.5,6.0621778264911Z fill=#333 /><path d=M22.5,6.0621778264911L8.5,30.310889132455L-5.5,6.0621778264911Z fill=#999 /><path d=M8.5,30.310889132455L-28.5,30.310889132455L-10,-1.7320508075689Z fill=#333 /><path d=M-28.5,30.310889132455L-53,-12.124355652982L-4,-12.124355652982Z fill=#999 /></svg>
```

# Answer
> 4 votes
# Python 3, 280, 262 bytes

18 bytes saved thanks to ovs

Golfed:

```
import turtle
P=lambda n:n<4or P(n-3)+P(n-2)
N=int(input())
M=9
t=turtle.Turtle()
Q=range
R=t.right
L=t.left
F=t.forward
S=[P(x)*M for x in Q(N,0,-1)]
A=S[0]
F(A)
R(120)
F(A)
R(120)
F(A)
L(120)
i=1
while i<N:
 A=S[i]
 for j in Q(3):F(A);L(120)
 F(A)
 L(60)
 i+=1

```

Same thing with some comments:

```
import turtle

# P(n) returns nth term in the sequence
P=lambda n:n<4or P(n-3)+P(n-2)

# M: scales the triangle side-length
M=9
# N: show triangles from 1 to (and including) N from sequence
N=int(input())
t=turtle.Turtle()
Q=range
R=t.right # R(a) -> turn right "a" degrees
L=t.left  # L(a) -> turn left "a" degrees
F=t.forward # F(l) -> move forward "l" units

# S: M*P(N),M*P(N-1), ... M*P(1)
S=[P(x)*M for x in Q(N,0,-1)]

# draw the largest triangle
A=S[0]
F(A)
R(120)
F(A)
R(120)
F(A)
L(120)
i=1

# draw the next N-1 smaller triangles
while i<N:
 A=S[i]
 for j in Q(3):F(A);L(120)
 F(A)
 L(60)
 i+=1

```

Screenshot for `N=9`:

# Answer
> 2 votes
# dwitter 151

```
s=(n)=>{P=(N)=>N<3||P(N-3)+P(N-2)
for(a=i=0,X=Y=500,x.moveTo(X,Y);i<n*4;i++)k=9*P(i/4),x.lineTo(X+=C(a)
*k,Y+=S(a)*k),x.stroke(),a+=i%4>2?1.047:2.094}

```

can be tested on http://dwitter.net (use fullscreen)

basic idea is logo turtle, golfed. stole the P() func from above!

i imagine more could be golfed by recursion but this is not bad.

# Answer
> 1 votes
## LOGO, 119 bytes

```
to s:n
make"x 10
make"y:x
make"z:y
bk:z
repeat:n[lt 60
fw:z
rt 120
fw:z
bk:z
make"w:y+:z
make"z:y
make"y:x
make"x:w]end

```

To use, do something like this:

```
reset
lt 150
s 12

```

Sample output (can't embed because it's not HTTPS and it failed to upload to imgur)

---
Tags: code-golf, sequence, graphical-output, fractal
---


# Question
Title: When life gives you lemons, make lemonade
# Challenge

You will be given an input string, anywhere the word `"Lemon"` is found it should be converted to `"Lemonade"` *but* the `a`, `d`, and `e` must be borrowed from somewhere else in the sentence.

---

# Example

Example Input:

> I found a **lemon** when I was a kid

Example Output:

> I foun a **lemonade** whn I was kid

The **Lemonade** was created by stealing the following superscript letters from the original

> I foun~~**d**~~ a lemonade wh~~**e**~~n I was ~~**a**~~ kid

This is just one possible output example, the "e", "d", and "a", could have been taken from anywhere (*except for from the word `lemon` of course*)

---

# Comments

•If there are not enough `e`, `a`, or `d`s you must output what was do-able with the letters given. For example the input `bdblemon` would output `bblemond`

•The `lemon` text might not always be standalone (space on each side). For example you may have the word `lemons` somewhere in the input and the output should be `lemonades`

•The input may contain any number of `lemon`s, even 0 `lemon`s (in which case the output would be identical to the input)

•You can make your lemonade with uppercase and lowercase letters, for example `leMon` could become `leMonade`, and the `ade` borrowed can be any case (so it could also have become `leMonADe`).
The case of the letter you borrowed must remain what it was when you borrowed it.
(Example input -\> output, `he hAD lemOn` -\> `h h lemOnADe`)

•Does not have to be a full program, a function alone is fine.

•You may assume input will be only the CP437 Character Set

---

# Code Golf

This is , so the lowest number of bytes wins!

---

# Pseudo-TestCases

\*Note: For any given input there might be **multiple possible outputs** so your program may not output exactly as these test cases do, this is more just so people can understand the logic:

> Input: EpaD leMons
> Output: p LeMonaDEs
>
> Input: hello world
> Output: hello world
>
> Input: lemon lemon
> Output: lemon lemon
> \*(*The `e`, `a`, `d` letters should never be taken from another "Lemon")*
>
> Input: HE HAD lemonade
> Output: H H lemonADEade
>
> Input: Do you like lemons? You hAd me at lemon!
> Output: o you lik lemonADes? You h m t lemonade!
>
> Input: AE lemon
> Output: lemonAE
>
> Input: 55bad lemon
> Output: 55b lemonad

# Answer
## JavaScript (ES6), ~~159~~ ~~157~~ ~~155~~ 162 bytes

*Edit: +7 bytes to "output what was do-able with the letters given" rather than throwing out an error*

---

A recursive function that returns the modified string.

```
f=(s,a=s.split(/(lemon)/i),n=(a.length-1)*1.5)=>n?f(n,a.map((s,i)=>i&1|!n||(a[i]=s.replace([/a/i,/e/i,/d/i][n%3],c=>(a[--n/3<<1|1]+=c,''))))&&a,n-(n==s)):a.join``

```

### How it works

The expression `s.split(/(lemon)/i)` splits the input string on `lemon` but preserves the capture groups in the result.

For instance, `"foo lemon bar LEMON baz".split(/(lemon)/i)` will produce the array `[ 'foo ', 'lemon', ' bar ', 'LEMON', ' baz' ]`.

We recursively iterate on this array, extracting the characters `a`, `d` and `e` or their uppercase counterparts from the entries located at an even position, and appending them to the entries located at an odd position.

### Commented

```
f = (                                   // given:
  s,                                    //   s = input string or previous value of 'n'
  a = s.split(/(lemon)/i),              //   a = split array, as described above
  n = (a.length - 1) * 1.5              //   n = total number of characters to be found
) =>                                    //
  n ?                                   // if there's still at least one character to find:
    f(                                  //   do a recursive call with:
      n,                                //     1) the current value of 'n'
      a.map((s, i) =>                   //     2) an updated version of 'a', where
        i & 1 | !n || (                 //       for even positions:
          a[i] = s.replace(             //         we look for the next character
            [/a/i, /e/i, /d/i][n % 3],  //           'a', 'e' or 'd' (case insensitive)
            c => (                      //           append it to
              a[--n / 3 << 1 | 1] += c, //           one of the entries at an odd position
              ''                        //           and remove it from the original entry
            )                           //           end of replace() callback
          )                             //         end of replace()
        )                               //       end of position condition
      ) && a,                           //     end of map() -> yield the updated 'a'
      n -                               //     3) the updated value of 'n', skipping the
      (n == s)                          //        current character if not found at all
    )                                   //   end of recursive call
  :                                     // else:
    a.join``                            //   success: join 'a' and return it

```

### Demo

```
f=(s,a=s.split(/(lemon)/i),n=(a.length-1)*1.5)=>n?f(n,a.map((s,i)=>i&1|!n||(a[i]=s.replace([/a/i,/e/i,/d/i][n%3],c=>(a[--n/3<<1|1]+=c,''))))&&a,n-(n==s)):a.join``

console.log(f("I found a lemon when I was a kid"))
console.log(f("I found a lemon when I was a kid. I found another lemon when I was older."))
console.log(f("bdblemon"))
console.log(f("he hAD lemOn"))
```
> 6 votes

# Answer
## CJam, 130 bytes

```
LqY5m*{"lemon"_eu}%3/:z{~?}f%{_@\/_:,[{1$+}*]);@f{[\]}@+\1a*}/\{1
=}$0f=\1$,{"ade"{__C#)\Ceu#)|(\0+We\)@_N=@+N\t\}fC}fN0a/L*1a/\.{}

```

This is split across two lines for clarity; the newline is not counted.

### Pseudocode:

```
FLAG_1 = object()
FLAG_2 = object()
lemon_instances = [] # CJam: L
input_chars = list(all_input()) # CJam: q
lemons = [
    "LEMON", "LEMOn", "LEMoN", "LEMon", "LEmON", "LEmOn", "LEmoN", "LEmon",
    "LeMON", "LeMOn", "LeMoN", "LeMon", "LemON", "LemOn", "LemoN", "Lemon",
    "lEMON", "lEMOn", "lEMoN", "lEMon", "lEmON", "lEmOn", "lEmoN", "lEmon",
    "leMON", "leMOn", "leMoN", "leMon", "lemON", "lemOn", "lemoN", "lemon"
] # CJam: Y5m*{"lemon"_eu}%3/:z{~?}f%
for i in lemons: # CJam: { ... }/
    temp = input_chars.split(i) # CJam: _@\/
    lengths = temp.map(len) # CJam: _:,
    # Here, accum turns an array like [1,2,3] into [1,3,6].
    indices = accum(lengths) # CJam: [{1$+}*]
    indices.pop() # CJam: );
    temp2 = zip(temp, indices) # CJam: @f{[\]}
    lemon_instances = temp2 + lemon_instances # CJam: @+
    input_chars = join_array(temp, FLAG_1) # CJam: 1a*
lemon_instances.sort(key=lambda x: x[1]) # CJam: {1=}$
lemon_instances = [i[0] for i in lemon_instances] # CJam: 0f=
for i in range(len(lemon_instances)): # CJam: \1$,{...}fN
    for c in "ade": # CJam: "ade"{...}fC
        # list_index returns -1 if not found
        lower = list_index(input_chars, c)+1 # CJam: __C#)
        upper = list_index(input_chars, upper(c))+1 # CJam: \Ceu#)
        char_index = (lower or upper) - 1 # CJam: |(
        input_chars.append(FLAG_2) # CJam: \0+
        # -1 refers to the last element in the list
        swap_list_elements(input_chars, char_index, -1) # CJam: e\
        extracted = input_chars.pop() # CJam: )
        lemon_instances[i] += extracted # CJam: @_N=@+N\t\
remove_all(input_chars, FLAG_2) # CJam: 0a/L*
temp1 = input_chars.split(FLAG_1) # CJam: 1a/
# interleave([1, 2, 3], ["a", "b"]) gives [1, "a", 2, "b", 3]
temp2 = interleave(temp1, lemon_instances) # CJam: \.{}
print("".join(temp2))

```
> 5 votes

# Answer
# Retina, 303 bytes

```
i+`(?<!lemon)(a)(.*)(lemon)(?!a)
$2$3$1
i+`(lemon)(?!a)(.*)(?<!lemon)(a)
$1$3$2
i+(?<!lemona?)(d)(.*)(lemona?)(?![ad])
$2$3$1
i+`(lemona?)(?![ad])(.*)(?<!lemona?)(d)
$1$3$2
i+(?<!lemona?d?)(e)(?!(?<=le)mon)(.*)(lemona?d?)(?![ade])
$2$3$1
i+`(lemona?d?)(?![ade])(.*)(?<!lemona?d?)(e)(?!(?<=le)mon)
$1$3$2

```

Try it online!

Surely I'm doing something wrong here.
> 4 votes

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