# Question
Title: Spotify Shuffle (music playlist shuffle algorithm)
## Background

Perfect shuffle algorithms like Fisher-Yates shuffle don't produce great results when it comes to music playlist shuffling, because it often produces clusters of songs from the same album. In an attempt to solve this problem, Spotify introduced an interesting shuffle algorithm in 2014. At the end of the article, they claimed (emphasis mine):

> All in all the algorithm is **very simple** and it can be implemented in **just a couple of lines**. It’s also very fast and produces decent results.

Let's see if this is indeed the case.

## Task

Implement the modified Spotify shuffle. The algorithm described in the article has some gaps in its specification, so I present a refined one here.

### The algorithm

Let's assume we have a list of items grouped into categories, e.g.:

```
[['A', 'AA', 'AAA'], ['B'], ['C', 'CC'], ['D'], ['E', 'EE', 'EEE', 'EEEE']]

```
1. Shuffle items within each category.

* You may use any shuffle algorithm that can produce every possible permutation with nonzero probability.

```
[['AAA', 'A', 'AA'], ['B'], ['C', 'CC'], ['D'], ['EEE', 'EEEE', 'EE', 'E']]

```
2. Assign each item a "positional value". Items in one category should be uniformly spaced, but with some randomness. To achieve this, do the following operations on each category having `n` items:
3. Initialize the positional value vector `v` of length `n` with the values `v[k] = k/n` for `0 <= k < n` (i.e. 0-indexed), so that the items have default spacing of `1/n`.
4. Generate an initial random offset `io` within the range of `0 <= io <= 1/n`, and add it to every `v[k]`.
5. Generate `n` individual random offsets `o[k]` within the range of `-1/10n <= o[k] <= 1/10n`, and apply `v[k] += o[k]` for each `k`. So the positional value of `k`-th item (0-indexed) within an `n`-item category will be `v[k] = k/n + io + o[k]`.

* The random offsets `io` and `o[k]` should ideally be picked from a uniform random variable, but can be approximated by picking from a discrete distribution with at least 5 distinct equally-spaced outcomes, including both lower and upper bounds. (e.g. you can choose to randomly pick `io` from `[0, 1/4n, 2/4n, 3/4n, 1/n]`.)
* Don't do extra processing even if `v[k] < 0` or `v[k] > 1`.

```
[['AAA' -> 0.1, 'A' -> 0.41, 'AA' -> 0.79],
 ['B' -> 0.2],
 ['C' -> 0.49, 'CC' -> 1.01],
 ['D' -> 0.03],
 ['EEE' -> 0.12, 'EEEE' -> 0.37, 'EE' -> 0.6, 'E' -> 0.88]]

```
3. Sort all items by the positional values.

```
['D', 'AAA', 'EEE', 'B', 'EEEE', 'A', 'C', 'EE', 'AA', 'E', 'CC']

```

The shuffled result roughly looks like this (from the article):

(source: wordpress.com)

Here is Python-like pseudocode of the above algorithm:

```
x = nested array of items
uniform(a,b) = uniformly generate a random value between a and b
items = []
v = []
for i in range(len(x)):  # for each category
    shuffle(x[i])  # shuffle items within category in place
    items += x[i]
    n = len(x[i])  # size of the current category
    io = uniform(0, 1/n)  # initial offset
    o = [uniform(-0.1/n, 0.1/n) for k in range(n)]  # individual offsets
    v += [k/n + io + o[k] for k in range(n)]  # resulting positional values
sort items by v
print items

```

## Input and output

The input is a list of groups of items (i.e. a nested list) as shown in the example above. An item is a string made of only uppercase letters (or only lowercase if you want). You can assume that all items are distinct, within and across categories.

The output is a shuffled list including all items in the input, which is produced by the algorithm described above.

The randomness requirements are covered in the algorithm description.

## Scoring and winning criterion

Standard rules apply. Shortest code in bytes wins.

# Answer
# JavaScript (Node.js),  ~~125~~  124 bytes

*Saved 1 byte thanks to @KevinCruijssen*

```
a=>a.flatMap(a=>a.sort(_=>R()-.5).map(v=>[(o++-.1+R()/5)/a.length,v],o=R()),R=Math.random).sort(([a],[b])=>a-b).map(a=>a[1])

```

Try it online!

### Commented

```
a =>                          // a[] = input
  a.flatMap(a =>              // for each category a[] in a[]:
    a.sort(_ => R() - .5)     //   shuffle a[]
    .map(v =>                 //   for each value v in a[]:
      [                       //     build a pair [position, value]:
        ( o++                 //       increment o
          - .1                //       subtract 1/10
          + R() / 5           //       add 2/10 * random value in [0,1)
        ) / a.length,         //       divide the result by the length of a[]
        v                     //       use v as the 2nd element
      ],                      //     end of pair
      o = R()                 //     start with o in [0,1)
    ),                        //   end of map()
    R = Math.random           //   R = alias for Math.random
  )                           // end of flatMap()
  .sort(([a], [b]) => a - b)  // sort by first element, in ascending order
  .map(a => a[1])             // keep only the 2nd element

```
> 7 votes

# Answer
# Python 3, ~~244~~ ~~218~~ 200 bytes

```
from random import*
l,r,u=len,range,uniform
def f(x):
 I,v=[],[]
 for i in r(l(x)):shuffle(x[i]);I+=x[i];n=l(x[i]);t=0.1/n;v+=[k/n+u(0,1/n)+u(-t,t)for k in r(n)]
 return[s[1]for s in sorted(zip(v,I))]

```

Try it online!

Literally just a golfed version of the algorithm in the challenge. I mean, someone had to do it!

Thanks to ValueInk for golfing suggestions!
> 4 votes

# Answer
# Jelly, 28 bytes

```
‘9xX€’÷8Ḣ__.÷5ƊƊ_@Ẋ÷
ẈÇ€FỤịẎ

```

Try it online!

A pair of links that is called monadically with input and output as described in the question. Jelly doesn’t generate random uniform numbers so a random rational number between 0 and 1 in increments of 0.125 is used instead.

Incidentally, per the question’s quote, I’ve implemented it in a **couple of lines**.

## Explanation

### Helper link, generates scores for each collection

Argument is the length of the collection

```
‘                    | Increment by 1
 9x                  | 9 repeated that many times
   X€                | Generate a random number from 1..9 for each
     ’               | Decrement by 1
      ÷8             | Divide by 8
               Ɗ     | Following as a monad:
        Ḣ            | - Head
         _     Ɗ     | - Subtract following as a monad:
          _.         |   - (Remainder of list) subtract 0.5
            ÷5       |   - Divide by 5
                _@Ẋ  | Subtract this from shuffled list from 1..original argument (subtracted to get zero-based number)
                   ÷ | Divide by original argument

```

# Main link

```
Ẉ       | Lengths of collections
 Ç€     | Call helper link for each
   F    | Flatten
    Ụ   | Sort indices by values
     ịẎ | Index into original argument joined into one list of strings

```
> 3 votes

# Answer
# , ~~52~~ ~~42~~ 32 bytes

```
/:&;(%~_.1+?~+?@0+5%~?@#&0)@#&.>

```

Try it online!
> 3 votes

# Answer
# Red, 180 bytes

```
func[b][random/seed now extract next sort/skip collect[forall
b[i: random 1.0 /(d: length? t: random b/1)repeat n
d[keep n - 1.0 / d + i +(0.1 / d - random 0.2 / d)keep t/:n]]]2 2]

```

Try it online!

Just a straightforward implementation of the algorithm
> 2 votes

# Answer
# 05AB1E, 37 bytes

```
ε.rDg©т*ÝΩVεN®/тD(ŸΩY‚₄/O+‚]˜2ôΣθ}€¨

```

Port of *@Arnauld*'s JavaScript answer, so make sure to upvote him as well!

Try it online (feel free to remove the last 2 or 3 bytes (`}€¨`) to see the resulting \\$v\[k\]\\$ values it sorts on).

**Explanation:**

```
ε             # Map each group of the (implicit) 2D integer-list to:
 .r           #  Randomly shuffle the group
   Dg         #  Duplicate, and pop and push the length: n
     U        #  Pop and store this length in variable `X`
   ₄Ý         #  Push a list in the range [0,1000]
     ₄/       #  Divide each value by 1000 to make the range [0,1] in increments of 0.001
       ©      #  Store this list in variable `®` (without popping)
        Ω     #  Pop and push a random value from this list
         V    #  Pop and store that random value in variable `Y`
    ε         #  Map over each value in this shuffled group:
     Y        #   Push the random value from variable `Y`
      N+      #   Add the 0-based loop index to it
     Tz-      #   Subtract 1/10 from it
     ®        #   Push the [0,1] list from variable `®` again
      Ω       #   Pop and push a random value r from this list
       5/     #   Divide it by 5
         +    #   Add it to the earlier Y-0.1
          X/  #   And divide it all by the length of the group from variable `X`
     ‚        #   And pair this v[k] with the value name
]             # After both maps:
 ˜            # Flatten the entire list of list of value,key pairs
  2ô          # And then split it into parts of size 2
              # (so we now have a flattened value,key paired list)
    Σ }       # Sort these key-value pairs by:
     θ        #  The last item (so by the key v[k])
       €¨     # And then remove the last item (so the key v[k]) from each pair
              # (after which the resulting list of (wrapped) values is output implicitly)

```
> 2 votes

# Answer
# Ruby, 93 bytes

Another straightforward implementation. -9 bytes from borrowing ideas from Arnauld's value generation code, which I saw right before I posted my answer.

```
->a{v=a.flat_map{|e|i=rand-1;e.shuffle.map{|s|[(rand/5-0.1+i+=1)/e.size,s]}}.sort.map &:last}

```

Try it online!
> 2 votes

# Answer
# , ~~104~~ 101 bytes

```
function(x,`!`=unlist,`+`=runif)(!x)[order(!lapply(lengths(x),function(l)(sample(l)-+1--+l/5-.1)/l))]

```

Try it online!

A function taking a list of character vectors and returning a character vector.

Thanks to @RobinRyder for saving 3 bytes!
> 1 votes

# Answer
# Charcoal, 60 bytes

```
Ｆθ«≔⟦⟧ηＷ⁻ιη⊞η‽κ≔∕‽⁵¦⁴ιＦＥη⟦∕⁺λ⁺ι∕⊖⊘‽⁵χＬηκ⟧⊞υκ»Ｗ⌊υ«≔Φυ¬⁼ικυ⟦⊟ι

```

Try it online! Link is to verbose version of code. Uses 5 distinct equally-spaced random numbers each time as allowed by the question. Explanation:

```
Ｆθ«

```

Loop over each category.

```
≔⟦⟧η

```

Start with no shuffled items.

```
Ｗ⁻ιη

```

Repeat until the set difference between the items and shuffled items is empty.

```
⊞η‽κ

```

Randomly pick one element of the difference to append to the shuffled items.

```
≔∕‽⁵¦⁴ι

```

Pick a random number between `0` and `1` which represents `io*n`.

```
∕⁺λ⁺ι∕⊖⊘‽⁵χＬη

```

For each item, add its index within its category `v*n` to `io*n` and a randomly generated offset `o*n` between `-0.1` and `0.1`, then divide the sum by `n` to get the final positional value.

```
ＦＥη⟦...κ⟧⊞υκ»

```

Save each random value and item in a separate list.

```
Ｗ⌊υ«

```

Repeat while the (minimum of) the list of random values and items is not empty.

```
≔Φυ¬⁼ικυ

```

Filter out the minimum value from the list.

```
⟦⊟ι

```

Output the item with that value.
> 1 votes

# Answer
# Python 3, 147 bytes

```
lambda a:[*zip(*sorted(((j+l.index(k)+random()/5-.1)/len(l),k)for j,l in((random(),sample(m,len(m)))for m in a)for k in l))][1]
from random import*

```

Try it online!

Assumes no duplicates
> 1 votes

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


title: Is everything in order?

text:
# Question
Title: Is everything in order?
## Challenge:

**Input:** a string, consisting of only printable ASCII characters
**Output:** a truthy/falsey value whether its characters are in alphabetical order (based on their UTF-8 unicode values), from any starting point inside the string including wrap-around by going left-to-right

For example: `xyzabc` would give a truthy result, because we could travel `a→b→c→x→y→z`, but `xzy` would give a falsey result, because all possible starting points (`x→y→z`; `y→z→x`; `z→x→y`) are not in the correct order.

This sounds pretty simple, right? But there is one catch, as this is a challenge: your program/function has to be in the correct order as well.

*†: Based on the order of the characters in your own codepage. i.e. a program written in Jelly need to be (with the wraparound of course) in the order of its own codepage, instead of UTF-8 order.*

## Challenge rules:

* The input can be in any reasonable format. Can be a string, read from STDIN, a list of characters, etc. (No, you are not allowed to take a list of unicode values - which would basically be an integer list - unless your language does this conversion by default (i.e. Java (`char` only), Whitespace, etc.)
* The input is guaranteed to be printable ASCII (range \\$\[32,126\]\\$ / `[' ','~']`).
* If your program/function is written in a different codepage, it does not necessary have to hold a truthy value when used as input for itself. The source code does need to be in the correct order based on the used codepage of course.
* The input is guaranteed to be non-empty. (An input of one or two characters will always result in a truthy output.)
* The input (and your source) can contain multiple of the same characters.
* This is , for which the longest answer counting only **distinct** bytes wins (i.e. if your source code is `ABBCabbc1223` your score would be 9 for `123ABCabc`).

## General rules:

* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

Truthy:

~
ab
ba
```
*5a
Test
test
xyzabc
aaabbbccc
aaabbbCCC
AAAbbbccc
msuwy !#),-./0123:;<?@BCFGILMNOQTWX]^_bf
oqqx}}~#$'''*+-./33489=?ABCHLQQQRTW[\]^_abcfgjkklmnno
</code></pre>

Falsey:

```
xzy
C-U
TeSt
tesT
aaaBBBccc
M3"b=J7Uh:kg&F~\p`GLx?9#!%XCOZBv.m_)Y4V*

```

# Answer
> 10 votes
# 05AB1E, ~~10~~ ... 172 distinct bytes

```
\]^_abcdefghiijklmnopqrstuvwxyz{|}}}~ƵƵ€Λ‚„…†‡ˆ‰ŠĆĆĆŽƶĀ‘‘’’““””••–—™š›œćŸā¡¢¢¢¤¤¦§¨©ª«¬®¯°±´¶·¸º»¼½½¾¿ÀÁÁÂÃÄÅÇÌÍÐÐÐÐÐÐÑÒÓÔÕÖ×ØÙÚÛÜÝßàáâãäåçèéêëìíîïðñòóôõö÷úü
 -.0123456789;<>@ABCDDDHKKOPQRSTUVWXYZ

```

Try it online! or validate all test cases (note: the "all test cases" version omits `]` and `ë`, since those don't play well with the header and footer required to run the code repeatedly).

Uses the 05AB1E code page. Validate restricted-source and scoring.

The useful code is just:

```
Ć            # append the first character of the input to the input
 Ç           # convert to a list of codepoints
  ü-         # pairwise subtraction
    1@       # >= 1?
      D      # duplicate
       O     # sum
        Q    # equal?
         Z   # maximum

```

The rest amounts to NOOPs.

---
Tags: string, code-challenge, restricted-source, code-bowling
---


# Question
Title: Regex in reverse - decompose regular expressions
# The Problem

I have a bunch of regular expressions that I need to use in some code, but I'm using a programming language that doesn't support regex! Luckily, I know that the test string will have a maximum length and will be composed of printable ASCII only.

# The Challenge

You must input a regex and a number `n`, and output every string composed of printable ASCII (ASCII codes 32 to 126 inclusive,  to `~`, no tabs or newlines) of length less than or equal to `n` that matches that regex. You may **not** use built-in regular expressions or regex matching functions in your code at all. Regular expressions will be limited to the following:

* Literal characters (and escapes, which force a character to be literal, so `\.` is a literal `.`, `\n` is a literal `n` (equivalent to just `n`), and `\w` is equivalent to `w`. You do not need to support escape sequences.)
* `.` \- wildcard (any character)
* Character classes, `[abc]` means "a or b or c" and `[d-f]` means anything from d to f (so, d or e or f). The only characters that have special meaning in a character class are `[` and `]` (which will always be escaped, so don't worry about those), `\` (the escape character, of course), `^` at the beginning of the character class (which is a negation), and `-` (which is a range).
* `|` \- the OR operator, alternation. `foo|bar` means either `foo` or `bar`, and `(ab|cd)e` matches either `abe` or `cde`.
* `*` \- match the previous token repeated zero or more times, greedy (it tries to repeat as many times as possible)
* `+` \- repeated one or more times, greedy
* `?` \- zero or one times
* Grouping with parentheses, to group tokens for `|`, `*`. `+`, or `?`

The input regex will always be valid (i.e., you do not have to handle input like `?abc` or `(foo` or any invalid input). You may output the strings in any order you would like, but each string must appear only once (don't output any duplicates).

# The Test Cases

Input: `.*`, `1`
Output: (empty string), , `!`, `"`, ..., `}`, `~`

Input: `w\w+`, `3`
Output: `ww`, `www`

Input: `[abx-z][^ -}][\\]`, `3`
Output: `a~\`, `b~\`, `x~\`, `y~\`, `z~\`

Input: `ab*a|c[de]*`, `3`
Output: `c`, `cd`, `ce`, `aa`, `cde`, `ced`, `cdd`, `cee`, `aba`

Input: `(foo)+(bar)?!?`, `6`
Output: `foo`, `foo!`, `foofoo`, `foobar`

Input: `(a+|b*c)d`, `4`
Output: `ad`, `cd`, `aad`, `bcd`, `aaad`, `bbcd`

Input: `p+cg`, `4`
Output: `pcg`, `ppcg`

Input: `a{3}`, `4`
Output: `a{3}`

# The Winner

This is , so the shortest code in bytes will win!

# Answer
# Haskell ~~757 705 700 692 679~~ 667

```
import Data.List
data R=L Char|A R R|T R R|E
h=[' '..'~']
k(']':s)a=(a,s)
k('^':s)_=l$k[]s
k('-':c:s)(a:b)=k([a..c]++b)s
k('\\':c:s)a=k s$c:a
k(c:s)a=k s$c:a
l(a,b)=(h\\a,b)
c#E=L c
c#r=A(L c)r
o(a,b)=(foldr(#)E a,b)
t%0=E
t%n=A(t%(n-1))$T t$t%(n-1)
d s n=m(fst$r s)[[]] where{m E a=a;m(L c)a=[b++[c]|b<-a,length b<n];m(A r s)x=nub$(m r x)++m s x;m(T r s)a=m s$m r a;r s=w$e s E;w(u,'|':v)=(\(a,b)->(A u a,b))$r v;w x=x;e(')':xs)t=(t,xs);e s@('|':_)t=(t,s);e s@(c:_)t=g t$f$b s;e[]t=(t,[]);g t(u,v)=e v$T t u;f(t,'*':s)=(t%n,s);f(t,'+':s)=(T t$t%n,s);f(t,'?':s)=(A t E,s);f(t,s)=(t,s);b('(':s)=r s;b('\\':s:t)=(L s,t);b('.':s)=o(h,s);b('[':s)=o$k s[];b(s:t)=(L s,t)}

```

output:

```
ghci> d ".*" 1
[""," ","!","\"","#","$","%","&","'","(",")","*","+",",","-",".","/","0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","@","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]","^","_","`","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","{","|","}","~"]
ghci> d "w\\w+" 3
["ww","www"]
ghci> d "[abx-z][^ -}][\\\\]" 3
["x~\\","y~\\","z~\\","b~\\","a~\\"]
ghci> d "ab*a|c[de]*" 3
["aa","aba","c","ce","cd","cee","cde","ced","cdd"]
ghci> d "(foo)+(bar)?!?" 6
["foo!","foobar","foo","foofoo"]
ghci> d "(a+|b*c)d" 4
["ad","aad","aaad","cd","bcd","bbcd"]
ghci> d "p+cg" 4
["pcg","ppcg"]
ghci> d "a{3}" 4
["a{3}"]

```

Explanation: this one's a textbook regex implementation. R is the regex type, with constructors A (alternate), L (literal), T (then) and E (empty/epsilon). The usual 'Star' doesn't appear because I inline it as alternates during the parse (see '%'). 'm' runs the simulation. The parser (start at 'r s=....') is just recursive descent; 'k' parses ranges. The function '#' expands ranges into alternations.
> 8 votes

# Answer
# Python v2.7 ~~1069~~ ~~1036~~ ~~950~~ ~~925~~ ~~897~~ ~~884~~ ~~871~~ ~~833~~ 822

This answer seems rather long for a code golf, but there are a lot operators that need to be handled and I know what purpose each byte in this answer does. Since there is no existing answer I submit this as a target for other users to beat. See if you can make a shorter answer :).

The two main functions are `f` which parses the regex starting at the `i`th character, and `d` which generates the matching strings, using `r` the sub-regexes we can recursed into, 'a' the array representing the part of the current sub-regex not yet processed, and a string suffix `s` which represents the part of the string generated so far.

Also check out the sample output and a test harness.

```
import sys;V=sys.argv;n=int(V[2]);r=V[1];S=len;R=range;C=R(32,127)
Z=[];z=-1;D='d(r,p,';F='for j in '
def f(i,a):
 if i>=S(r):return a,i
 c=r[i];x=0;I="|)]".find(c)
 if c in"([|":x,i=f(i+1,Z)
 if I+1:return([c,a,x],[a],[c,a])[I],i
 if'\\'==c:i+=1;x=c+r[i]
 return f(i+1,a+[x or c])
def d(r,a,s):
 if S(s)>n:return
 while a==Z:
        if r==Z:print s;return
        a=r[z];r=r[:z]
 e=a[z];p=a[0:z]
 if'|'==a[0]:d(r,a[1],s);d(r,a[2],s)
 elif']'==a[0]:
        g=a[1];N=g[0]=='^';g=(g,g[1:])[N];B=[0]*127;O=[ord(c[z])for c in g]
        for i in R(0,S(g)):
         if'-'==g[i]:exec F+'R(O[i-1],O[i+1]):B[j]=1'
         else:B[O[i]]=1
        for c in C:N^B[c]<1or d(r,Z,chr(c)+s)
 elif' '>e:d(r+[p],e,s)
 else:c=p[:z];exec{'.':F+'C:'+D+'chr(j)+s)','?':D+'s);d(r,p[:z],s)','*':F+'R(0,n+1):d(r,c,s);c+=[p[z]]','+':"d(r,p+['*',p[z]],s)"}.get(e,D+'e[z]+s)')
d(Z,f(0,Z)[0],"")

```

Note that tabs in the original solution have been `expand`ed. To count the number of characters in the original use `unexpand < regex.py | wc`.
> 9 votes

# Answer
# Prolog (SWI), 586 bytes

The built in backtracking ability of Prolog makes it an awesome choice for this challenge. By taking advantage of backtracking, generating strings for a regex becomes exactly the same task as testing if a string is matched by a regex. Unfortunately, much of my golfing effort went into writing a shorter regex parsers. The actual task of decomposing a regular expression we easily golfed.

```
R-L-S:-R*A,-(B,A,[]),setof(Z,(0/L/M,length(C,M),C+B+[],Z*C),S).
-R-->e+S,S-R.
R-T-->{R=T};"|",e+S,u+R+S-T.
Z+Y-->(".",{setof(C,32/126/C,R)};"[^",!,\E,"]",{setof(C,(32/126/C,\+C^E),R)};"[",\R,"]";"(",-R,")";{R=[C]},([C],{\+C^`\\.[|+?*(`};[92,C])),("*",{S=k*R};"+",{S=c+R+k*R};"?",{S=u+e+R};{S=R}),({Y=c+Z+S};c+Z+S+Y).
\C-->{C=[H|T]},+H,\T;{C=[]};+A,"-",+B,\T,{setof(C,A/B/C,H),append(H,T,C)}.
+C-->[92,C];[C],{\+C^`\\]-`}.
S+e+S.
[C|S]+D+S:-C^D.
S+(B+L+R)+T:-B=c,!,S+L+U,U+R+T;S+L+T;S+R+T.
S+k*K+U:-S=U;S+K+T,S\=T,T+k*K+U.
A/B/C:-between(A,B,C).
A^B:-member(A,B).
A*B:-string_codes(A,B).

```

Try it online!

# Ungolfed Code

```
generate_string(R, L, S) :-
    % parse regex
    string_codes(R, RC),
    regex_union(RE, RC, []),

    % bound string length
    between(0, L, M),
    length(SC, M),

    % find string
    match(SC, RE, []),

    string_codes(S, SC).

% Parsers
%%%%%%%%%

regex_union(R) -->regex_concat(S), regex_union1(S, R).

regex_union1(R,T) --> [124], regex_concat(S), regex_union1(regex_union(R,S), T).
regex_union1(R, R) --> [].

regex_concat(R) --> regex_op(S), regex_concat1(S, R).

regex_concat1(R, T) --> regex_op(S), regex_concat1(regex_concat(R,S), T).
regex_concat1(R, R) --> [].

regex_op(regex_kleene(R)) --> regex_lit(R), [42].
regex_op(regex_concat(R,regex_kleene(R))) --> regex_lit(R), [43].
regex_op(regex_union(regex_empty,R)) --> regex_lit(R), [63].
regex_op(R) --> regex_lit(R).

regex_lit(regex_char([C])) --> [C], {\+ regex_ctrl(C)}.
regex_lit(regex_char([C])) --> [92], [C].

regex_lit(regex_char(CS)) --> [46], {findall(C, between(32,126, C), CS)}.

regex_lit(regex_char(DS)) -->
    [91], [94], !, class_body(CS), [93],
    {findall(C, (between(32, 126, C), \+ member(C, CS)), DS)}.
regex_lit(regex_char(CS)) --> [91], class_body(CS), [93].

regex_lit(R) --> [40], regex_union(R), [41].

class_body([C|T]) --> class_lit(C),class_body(T).
class_body(CS) -->
    class_lit(C0), [45], class_lit(C1), class_body(T),
    {findall(C, between(C0, C1, C), H), append(H,T,CS)}.
class_body([]) --> [].

class_lit(C) --> [C], {\+ class_ctrl(C)}.
class_lit(C) --> [92], [C].

class_ctrl(C) :- string_codes("\\[]-", CS), member(C, CS).
regex_ctrl(C) :- string_codes("\\.[]|+?*()", CS), member(C, CS).

% Regex Engine
%%%%%%%%%%%%%%

% The regex empty matches any string without consuming any characters.
match(S, regex_empty, S).

% A regex consisting of a single character matches any string starting with
% that character. The chanter is consumed.
match([C|S], regex_char(CS), S) :- member(C, CS).

% A union of two regex only needs to satisify one of the branches.
match(S, regex_union(L,R), T) :- match(S, L, T); match(S, R, T).

% A concat of two regex must satisfy the left and then the right.
match(S, regex_concat(L, R), U) :- match(S, L, T), match(T, R, U).

% The kleene closure of a regex can match the regex 0 times or it can the regex
% once before matching the kleene closure again.
match(S, regex_kleene(_), S).
match(S, regex_kleene(K), U) :- match(S, K, T), S \= T, match(T, regex_kleene(K), U).

```
> 2 votes

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


title: Check if simple regex matches string

text:
# Question
Title: Check if simple regex matches string
A simple regex is either:

* `_` (which matches the empty string)
* Any lowercase letter `a` to `z` (which matches that letter)
* `r*`, where `r` is a regex (which matches `r` any number of times)
* `(r|s)`, where `r` and `s` are regexes (which matches either `r` or `s`)
* `(r+s)`, where `r` and `s` are regexes (which matches `r` followed by `s`)

Note that due to the recursive definition, `*` can occur multiple times in a row.

Here are some examples of regexes and their matches:

* `(a+b)` matches only `ab`
* `((a|_)+b*)` matches , `a`, `b`, `ab`, `bb`, `abb`, but not `baaa`, `aab`
* `(c+(o+((l+(o+(u|_)))+r)))` matches only `color` and `colour`
* `(a|b)*` matches only strings containing letters `a` and `b` (so , `ab`, `bab`, but not `abc`)
* `(_***|(a+b***))` matches only the empty string or `a` followed by any number of `b`s.

Your task is to write a program that takes such a regex and a string of lowercase letters, and outputs whether or not the regex matches the entire string (output should be as described here).

The shortest code in bytes wins.

# Answer
# Haskell, 203 bytes

Nobody had done this by implementing a small regex engine yet, and I felt like it had to be done. This obviously won't win. but I'm hoping it will inspire someone to write an even more golfed regex engine.

I've rewritten my solution to avoid directly parsing the regular expression into its AST. Instead, the parsing process constructs a function that is used to match a string against the input regex.

The main function is `(&) :: String -> String -> Bool` which takes a string representation of a regex and a string to test, returning a boolean value. This calls to the next function which handles most of the work in parsing the regex and matching the string.

Function `p :: String -> ([String] -> [String], String)` takes a string representation of a regex and returns as the first element of a tuple a function that returns a list of all possible unmatched suffixes of strings in the input list after satisfying the regex parsed from the input string. The regex fully matches the string if the empty string is contained in the list of possible unmatched suffixes.

```
r&s=elem""$fst(p r)[s]
p(c:t)|c>'`'=t% \s->[t|h:t<-s,c==h]|c>'^'=t%id|(l,o:t)<-p t,(r,_:u)<-p t=u%last(r.l:[\s->r s++l s|o>'+'])
m#s=s++filter(`notElem`s)(m s)
('*':t)%m=t%until(\s->s==m#s)(m#)
s%m=(m,s)

```

Try it online!

To get rid of one byte, I replaced `import Data.List; m#s=nub$s++m s` with `m#s=s++filter(`notElem`s)(m s)`. These functions aren't equivalent if there are duplicate elements in either `s` of `m s`. The new function does, however, remove all elements from `m s` that already exist in `s`, so `until` still terminates once no new suffixes are discovered by the application of `m`.

# Ungolfed Code

```
import Data.List

match :: String -> String -> Bool
match r s =elem ""$(fst $ parseRegex r)[s]

parseRegex :: String -> ([String] -> [String], String)
parseRegex ('_':t) = parseKleene id t
parseRegex (c:t) | c >= 'a' = parseKleene (>>=p) t
  where p (c':t')| c==c' = [t']
        p _ = []
parseRegex ('(':t) =
  let (l, (o:t')) = parseRegex t in
  let (r, (_:t'')) = parseRegex t' in
  parseKleene (if o=='+' then (r.l) else (\ss-> (r ss)++(l ss))) t''

parseKleene :: ([String] -> [String]) -> String -> ([String] -> [String], String)
parseKleene p ('*':t) = parseKleene p' t
  where
    p' ss
      | ss' <- nub$ p ss,
        ss /= ss' = ss ++ (p' ss')
      | otherwise = ss
parseKleene p s = (p,s)

```

---

# GolfScript, 198 bytes

I was able to beat my Haskell solution by implementing the first algorithm I tried in GolfScript instead of Haskell. I don't think it's interesting enough for a separate answer, so I'll just leave it here. There are likely some golfing opportunities since I learned GolfScript just for this.

This solution is in the form of a block that expects the test string on the top of the stack followed by the regex string.

```
{[.;]\1+{(.96>{0[\]}{2%0{r\(\r\:s;[@]s(;\}i}{if}:i~\{(.3%}{;\2[\]\}until[.;]\+\}:r~\;{.{(.{.4%{2%{)@\m\)\;m}{)\;{.@.@m 1$|.@={\;}{\o}i}:o~}i}{;)@.@m@@\)\;m|}i}{;(:c;;{,},{(\;c=},{(;}%}i}{;}i}:m~""?}

```

Try it online!
> 20 votes

# Answer
# APL (Dyalog Unicode), 39 bytesSBCS

***Edit:*** *now works with runs of `*` even after `_`*

Full program. Prompts stdin for string and then for regex. Returns a list consisting of an empty list (by default, this prints as two spaces) for matches and an empty list (empty line) for non-matches.

```
(1⌽'$^','\*+' '_'⎕R'*' '()'⊢⍞~'+')⎕S⍬⊢⍞

```

Try it online! (output made easier to read by converting all output to JSON)

prompt stdin (for string)

on that, apply the following:

`(``)⎕S⍬` PCRE **S**earch for the following, returning an empty list for each match

`~'+'` remove all plusses from the following:

prompt stdin (for regex)

on that, apply the following:

`'\*+' '_'⎕R'*' '()'` PCRE **R**eplace runs of `*` with `*` and `_` with `()`

`'$^',` prepend dollar sign and caret (indicating end and start)

`1⌽` rotate the first character (`$`) to the end
> 9 votes

# Answer
# Python 3, 69 bytes

```
lambda r,s:re.match(re.sub('(?<=[_*])\*+|[_+]','',r)+'$',s)
import re

```

Try it online!

Simple - just convert it to ordinary regex, using ordinary regex!
> 7 votes

# Answer
# APL (Dyalog Unicode), ~~295~~ 277 bytes

```
a←819⌶⎕A
E←{⍵{(⍺⊆⍨~⍵),⍺[⍸⍵]}(⍵∊'|+')∧0=+\-⌿'()'∘.=⍵}1↓¯1↓⊢
M←{c←⊃⌽⍵⋄c∊'0',a:0⋄c∊'_*':1⋄r s o←E⍵⋄o='|':∨/∇¨r s⋄∧/∇¨r s}
D←{c←⊃⌽⍵⋄c∊'0_':'0'⋄c=⍺:'_'⋄c∊a:'0'⋄c='*':1⌽∊')('(⍺∇¯1↓⍵)'+'⍵⋄r s o←E⍵⋄o='|':1⌽∊')('(⍺∇r)'|',⍺∇s⋄M r:1⌽∊')(('(⍺∇r)'+'s')|',⍺∇s⋄1⌽∊')('(⍺∇r)'+'s}
{M⊃D/(⌽⍵),⊂⍺}

```

Try it online!

-18 bytes thanks to @ngn.

This is a proof of concept that we can do a "simple regex matching" without any backtracking, thus avoiding possible infinite loops due to `_*` or `r**`. This is also a showcase that APL is a general-purpose programming language.

The anonymous function at the last line does the regex matching; use it as `(regex) f (input string)`. The return value is 1 if the match is successful, 0 otherwise.

### Concept

Given a simple regex `R` and the first character `c` of input string, we can construct (or *derive*) another simple regex `R'` that matches exactly the strings `s` where the original `R` matches `c+s`.

$$ \forall R \in \text{simple regex}, c \in \text{\[a-z\]}, s \in \text{\[a-z\]\*}, \\ \exists R' \in \text{simple regex}, R' =\sim s \iff R =\sim c+s $$

Combine this with a tester which checks if `r` matches an empty string (epsilon), and we get a fully working simple regex matcher: given a regex \\$ R\_0 \\$ and string \\$ s = c\_1 c\_2 \cdots c\_n \\$, sequentially derive \\$ R\_0, c\_1 \rightarrow R\_1, c\_2 \rightarrow R\_2 \cdots \rightarrow R\_n \\$ and then test if \\$ R\_n \\$ matches epsilon.

My code uses the following algorithm for testing epsilon match (`MatchEps`) and computing `R'` from `R` and `c` (`Derive`).

```
T = True, F = False
0 = null regex (never matches)
_ = "empty string" regex
a = single-char regex
r, s = any (sub-)regex

MatchEps :: regex -> bool
MatchEps 0 = F    # Null regex can't match empty string
MatchEps _ = T    # Empty-string regex trivially matches empty string
MatchEps a = F    # Single-char can't match
MatchEps r* = T   # Kleene matches as zero iteration
MatchEps (r|s) = MatchEps r or MatchEps s
MatchEps (r+s) = MatchEps r and MatchEps s

Derive :: char -> regex -> regex
# No matching string at all
Derive c 0 = 0
# _ can't match any string that starts with c
Derive c _ = 0
# Single-char regex only matches itself followed by empty string
Derive c a = if c == 'a' then _ else 0
# r* matches either _ or (r+r*);
# _ can't start with c, so it must be first `r` of (r+r*) that starts with c
Derive c r* = ([Derive c r]+r*)
# r or s; simply derive from r or derive from s
Derive c (r|s) = ([Derive c r]|[Derive c s])
# r followed by s; it matters if r can match _
Derive c (r+s) =
  # if r matches _, either [r starts with c] or [r matches _ and s starts with c]
  if MatchEps r then (([Derive c r]+s)|[Derive c s])
  # otherwise, r always starts with c
  else ([Derive c r]+s)

```

### Ungolfed, with comments

```
⍝ Unwrap single layer of (...) and extract (r, s, op) from (r|s) or (r+s)
ExtractRS←{⍵{(⍺⊆⍨~⍵),⍺[⍸⍵]}(⍵∊'|+')∧0=+\-⌿'()'∘.=⍵}1↓¯1↓⊢
  ⍝ 1↓¯1↓⊢    Drop the outermost ()
  ⍝ {...}     Pass the result to the function as ⍵...
  ⍝   +\-⌿'()'∘.=⍵    Compute the layers of nested ()s
  ⍝   (⍵∊'|+')∧0=     Locate the operator (`|` or `+`) as bool vector
  ⍝   ⍵{...}          Pass to inner function again ⍵ as ⍺, above as ⍵
  ⍝     ⍺[⍸⍵]     Extract the operator
  ⍝     (⍺⊆⍨~⍵),  Prepend the left and right regexes

⍝ Tests if the given regex matches an empty string (epsilon, eps)
MatchEps←{
    c←⊃⌽⍵                 ⍝ Classify the regex by last char
    c∊'0',819⌶⎕A:0        ⍝ 0(no match) or lowercase: false
    c∊'_*':1              ⍝ _(empty) or Kleene: true
    r s op←ExtractRS ⍵    ⍝ The rest is (r|s) or (r+s); extract it
    op='|': ∨/∇¨r s       ⍝ (r|s): r =~ eps or s =~ eps
    ∧/∇¨r s               ⍝ (r+s): r =~ eps and s =~ eps
}

⍝ Derives regex `R'` from original regex `R` and first char `c`
Derive←{
    c←⊃⌽⍵             ⍝ Classify the regex by last char
    c∊'0_':,'0'       ⍝ 0 or _ doesn't start with any c
    c=⍺:,'_'          ⍝ Single char that matches
    c∊819⌶⎕A:'0'      ⍝ Single char that doesn't match
    c='*': '(',(⍺∇¯1↓⍵),'+',⍵,')'    ⍝ One char from Kleene: (R*)' = (R'+R*)
    r s op←ExtractRS ⍵               ⍝ Extract (r|s) or (r+s)
    op='|': '(',(⍺∇r),'|',(⍺∇s),')'  ⍝ (r|s): one char from either branch
    MatchEps r: '((',(⍺∇r),'+',s,')|',(⍺∇s),')'   ⍝ (r+s) and r =~ eps: ((r'+s)|s')
    '(',(⍺∇r),'+',s,')'                           ⍝ (r+s) but not r =~ eps: (r'+s)
}

⍝ Main function: Fold the string by Derive with initial regex,
⍝                and then test if the result matches eps
f←{MatchEps⊃Derive/(⌽⍵),⊂⍺}

```

### Final note

This is not an original idea of mine; it is part of a series of exercises on a theorem proving textbook. I can claim that the algorithm is proven to work (because I did complete the correctness proofs), though I can't open the entire proof to public.
> 7 votes

# Answer
# JavaScript (ES6), 45 bytes

Takes input as `(regex)(string)`. Returns a Boolean value.

Applies the straightforward method of removing `[_+]` from the simple regex to turn it into a standard regex.

```
r=>s=>!!s.match(`^${r.replace(/[_+]/g,"")}$`)

```

Try it online!

Or 43 bytes by returning either `null` or an object.
> 4 votes

# Answer
# Retina, ~~38~~ 35 bytes

```
*1A`
1G`
^
a`
_
()
\*+
*
"$-5"~`\+

```

Try it online! Takes the simple regex on the first line and the string to match on the second. Explanation:

```
*1A`

```

Delete the first line, but don't actually change the working string. The string to match still gets stored in the history, which allows us to refer to it later.

```
1G`

```

Keep only the first line.

```
^
a`

```

Prefix the `a` modifier to anchor the pattern to the whole string.

```
_
()

```

Turn the `_`s into `()`s to match an empty string that can be "repeated" with `*`.

```
\*+
*

```

Reduces runs of `*` to a single `*`.

```
\+

```

Delete any `+`s.

```
"$-5"~`

```

Execute that as a stage, using the history as the working string.
> 4 votes

# Answer
# , ~~55~~ 75 bytes

```
function(x,y)grepl(paste0("^",gsub("([+_]|(?<=\\*))\\**","",x,pe=T),"$"),y)

```

Try it online!

A function that takes a simple regex `x` and a vector of strings `y` and returns a vector of logical values the same length as `y` indicating whether `x` matches.
> 4 votes

# Answer
# Java 8, 55 bytes

```
r->s->s.matches(r.replaceAll("\\+|(_|(\\*))\\**","$2"))

```

Try it online.

Removes all `+`; all `_` with zero or more trailing `*`; and changes all sequences of more than one subsequent `*` with a single `*`. Then it check if the String matches this modified regex. Note that in Java, the `String#matches` method implicitly adds a leading and trailing `^...$` to check the entire String.
> 3 votes

# Answer
# PHP, ~~983~~ ~~976~~ ~~954~~ ~~930~~ ~~910~~ ~~892~~ 838 bytes

```
<?php list(,$s,$i)=$argv;$p=0;$u=[2,[3,[2,[1,'('],$o=[2,[4,[2,&$u,[1,'|+']]],&$u],[1,')']],[1,'_'.join(range('a','z'))]],[5,[1,'*']]];m($o,$a);$s=$i;$p=0;echo m(o($a))&&$p==strlen($s);function m($m,&$a=[]){global$p,$s;$r=$p;$n=array_shift($m);foreach($m as$t){$b=[];if($n==1)if(($c=$s[$p]??0)&&strpos($t,$c)!==!1){$a[]=$c;$p++;return 1;}if($n==2){if(!m($t,$b)){$p=$r;return!1;}$a[]=$b;}if($n==3){if(m($t,$b)){$a[]=$b;return 1;}}if($n==4){k:$b=[];$r=$p;if(!m($t,$b)){$p=$r;return 1;}$a[]=$b;goto k;}if($n==5){if(m($t,$b))$a[]=$b;else{$a[]=[];$p=$r;}return 1;}if($n==6)return 1;}return $n==2?:$p!=$p=$r;}function o($a){$e=$b=u($a[1]);if($a[0]){$e=[2];foreach($a[0]as$u){$e[]=u($u[0]);$e[0]=$u[1][0]=='+'?2:3;}$e[]=$b;}return$e;}function u($u){$w=$u[0][0];$v=$w[0][0];$t=$v!='('?($v=='_'?[6,0]:[1,$v]):o($w[1]);return$u[1][0]==[]?$t:[4,$t];}

```

Try it online!

## Ungolfed

```
<?php

list($dummy,$string,$user_test)=$argv;

$pointer = 0;

//production rules
$unit = [];
$char = ['char','_abcdefghijklmnopqrstuvwxyz'];
$separator = ['char','|+'];
$unit_and_separator = ['and',&$unit,$separator];
$operators_list = ['list',$unit_and_separator];
$operators = ['and',$operators_list,&$unit];
$open_bracket = ['char','('];
$close_bracket = ['char',')'];
$brackets = ['and',$open_bracket,$operators,$close_bracket];
$atom = ['or',$brackets,$char];
$star = ['opt',['char','*']];
$unit = ['and',$atom,$star];

$ast = [];
match($operators, $ast);

$user_regex = buildoperators($ast);

$user_ast = [];
$string = $user_test;
$pointer = 0;

// answer here 1=matched blank=not matched
echo match($user_regex, $user_ast)&&($pointer==strlen($string));

// recursive descent parser
function match($test_match, &$ast) {
    global $pointer,$string;

    $original_pointer = $pointer;

    foreach (array_slice($test_match,1) as $test) {
        switch ($test_match[0]) {
            case 'and':
                $sub_match = [];
                $pass = match($test,$sub_match);
                if (!$pass) {$pointer = $original_pointer;return false;}
                $ast[] = $sub_match;
                break;
            case 'or':
                $sub_match = [];
                $pass = match($test, $sub_match);
                if ($pass) {
                    $ast[] = $sub_match;
                    return true;
                }
                break;
            case 'list':
                do {
                    $sub_match = [];
                    $original_pointer=$pointer;
                    $pass = match($test, $sub_match);
                    if (!$pass) {
                        $pointer = $original_pointer;
                        return true;
                    }
                    $ast[] = $sub_match;
                } while (true);
                break;
            case 'char':
                $char = substr($string,$pointer,1);
                if ($char && @strpos($test,$char)!==false) {
                    $ast[]=substr($string,$pointer,1);
                    $pointer++;
                    return true;
                }
                break;
            case 'emptystring':
                return true;
                break;
            case 'opt':
                $pass = match($test, $sub_match);
                if ($pass) {$ast[] = $sub_match;} else {$ast[] = []; $pointer = $original_pointer;}
                return true;
                break;
        }
    }

    if ($test_match[0] == 'and') {
        return true;
    } else {
        $pointer = $original_pointer;
        return false;
    }
}

// build user production rules
function buildoperators($ast) {
    if ($ast[0]) {
        $engine = ['and'];
        foreach ($ast[0] as $unit_and_separator) {
            $engine[] = buildunit($unit_and_separator[0]);
            switch ($unit_and_separator[1][0]) {
                case '+':
                    $engine[0]='and';
                    break;
                case '|':
                    $engine[0]='or';
                    break;
            }

        }
        $engine[] = buildunit($ast[1]);
    } else {
        $engine = buildunit($ast[1]);
    }
    return $engine;
}

function buildunit($unit) {
    $star = !empty($unit[1][0]);
    if ($star) {
        return ['list',buildatom($unit[0][0])];
    } else {
        return buildatom($unit[0][0]);
    }
}

function buildatom($atom) {
    if ($atom[0][0]=='(') {
        return buildoperators($atom[1]);
    } elseif ($atom[0][0]=='_') {
        return ['emptystring',''];
    } else {
        return ['char',$atom[0][0]];
    }
}

```
> 2 votes

# Answer
# Perl 5, 47 + `-alp` flag = 50 bytes

```
$_=$F[0];s/[_+]/()/g;s/\*+/*/g;$_=$F[1]=~/^$_$/

```

Try it online!

---

# Perl 5, 41 + `-alp` flag = 44 bytes

Obsolete: it not supports `_***`-like regexes

```
$_=eval'$F[1]=~/^'.($F[0]=~y/_+//rd).'$/'

```

Try it online!
> 1 votes

# Answer
# Perl 5, 34 + `-p` flag = 35 bytes

Full program. Takes the simple regex pattern, followed by string to match against, from stdin as two separate lines, then loops and does it again, until EOF is encountered. Prints `1` for a match or nothing for a non-match (with no newline in either case).

@ankh-morpork has pointed out that technically, given the question's description of simple regexes, any number of `*` in a row makes a valid simple regex. @Bubbler has pointed out that `_*` also needs to work (and be equivalent to `_`). The other answers haven't taken these things into account yet, but I will do so:

```
s/[_+]/()/g;s/\*+/*/g;$_=<>=~/^$_/

```

Try it online!

To allow simple regexes such as `(_***+a)` to work, `_` is changed to `()` instead of . For golf reasons, `+` is also changed to `()`, although changing it to  would work.

This solution exploits the fact that valid input won't contain newlines, input can be assumed to be valid, and both the implicit `<>` (from `-p`) and the explicit `<>` include the terminating newline read from stdin, thus `$` doesn't need to be added at the end of the regex (as both the pattern and the string ), only `^` needs to be inserted at the beginning.

---

## Perl 5, 20 + `-p` flag = 21 bytes (looser, obsolete interpretation of question)

```
y/_+//d;$_=<>=~/^$_/

```

Try it online!

Like most of the other solutions, deletes the `_` and `+` characters to turn the simple regex into a standard regex. This means that the simple regex `(_*+a)` will not work, as it becomes `(*a)` after the deletion. Anything containing `**` won't work either; in standard regex, an already-quantified expression cannot be quantified again.
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 522 bytes

```
a=>b=>{int y=0,e=a.Length,k=0,o,q;var z=new int[e];for(;k<e;k++)if(a[k]<41){for(o=q=1;o>0;q++)o+=a[q+k]<41?1:a[q+k]>41?0:-1;z[k+--q]=k+1;z[k]=k+q+2;}void t(string s,int j){for(;j<e;){var l=a[j++];var w=j<e&&a[j]==42;if(j>1&&a[j-2]<41)for(int r=j,d=0;r<z[j-2]-1;)if(a[r++]>123&z.Take(r).Skip(j-2).Count(x=>x>0)%2>0)t(s,r);if(l>96&l<124)do{if(w)t(s,j+1);if(s==""||s[0]!=l)return;s=s[1..];}while(w);if(l==42&&a[j-2]==41||l<41&z[j-1]<=e&&a[z[j-1]-1]==42)t(s,z[j-1]);j=l>123?a.IndexOf(')',j)+1:j;}y=s==""?1:y;}t(b,0);return y;}

```

Saved 6 bytes thanks to ceilingcat

Try it online!
> 1 votes

# Answer
# Japt , 13 bytes

```
è^+'$iVr"_|%+

```

Try it

```
true

```
> 0 votes

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


title: Build a steady brick wall

text:
# Question
Title: Build a steady brick wall
A brick wall is a rectangle made of horizontal 1-by-n bricks stacked into rows. Here's a wall of height 4 and width 8, with brick sizes shown on the right.

```
[______][______]    4 4
[__][____][__][]    2 3 2 1
[][______][____]    1 4 3
[____][______][]    3 4 1

```

This wall is unsteady because it has a *fault*, a place where two vertical cracks between bricks line up, shown below with parens in the surrounding bricks.

```
[______][______]
[__][____)(__][]
[][______)(____]
[____][______][]

```

But, the cracks bordering the size-1 bricks on the right don't form a fault because they are separated by a row.

Write code that finds and displays a steady wall constructed out of bricks of specified sizes. Fewest bytes wins.

**Input**

A non-empty list of brick sizes (positive numbers) and a height that's at least 2. This list may be sorted if you wish. You may alternatively take in a count of bricks of each size.

**Output**

A picture of a steady rectangular wall of the required height that uses all the bricks given. Print it or return it as a string with newlines.

Draw a brick of size n as 2n characters, underscores surrounded by brackets.

```
1: []
2: [__]
3: [____]
4: [______]
...

```

The input is guaranteed to have at least one solution. If there's multiple, you should still only draw one wall.

There's no time restriction; use as much brute force as you want. Your algorithm should in theory work on inputs of any size.

**Test cases:**

There are multiple solutions, so your outputs might be different.

```
>> [1, 1, 2, 2], 2
[][__]
[__][]

>> [1, 1, 1, 2, 2, 2, 2, 3], 2
[__][____][__]
[][__][][__][]

>> [1, 1, 2, 2, 3, 3, 3, 3], 3
[][__][____]
[__][____][]
[____][____]

>> [1, 2, 3, 4, 5, 6, 7, 8, 9], 5
[][______________]
[__][____________]
[________________]
[____][__________]
[______][________]

>> [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 5
[][__][__]
[__][__][]
[][__][__]
[__][__][]
[][__][__]

```

# Answer
# Perl, 166 ~~170 194~~

A perfect task for a language created by Larry Wall.

```
#!perl -pa
$_=(1x($x=2/($y=pop@F)*map{1..$_}@F)."
")x$y;sub
f{my$l=$_;$-|=!@_;for$=(@_){$Z=__
x~-$=;$f=0;s/(11){$=}/[$Z]/&!/\]..{$x}\[/s&&f(grep$=ne$_||$f++,@_);$-or$_=$l}}f@F

```

Brute force, but quite fast on the test cases (\<1s). Usage:

```
$ perl ~/wall.pl <<<"1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 5"
[][__][__]
[__][__][]
[][__][__]
[__][__][]
[][__][__]

```

Test me.
> 21 votes

# Answer
# CJam, ~~94 92~~ 82 bytes

This is the 92 bytes version. 82 byte version follows.

```
l~1$,:L,:)m*{1bL=},\e!\m*{~W<{/(\e_}%}%{::+)-!},{{_,,\f<1fb}%2ew{:&,(},!}={{(2*'_*'[\']}/N}/

```

This partitions the bricks into every possible way and take only the one which is valid. Pretty brute force for now but still runs the last test case in about 10 seconds on the Java Interpreter on my machine.

**Explanation**:

The code is split into 5 parts:

1) Given an array of length `L`, how all can we partition it into `H` parts.

```
l~1$,:L,:)m*{1bL=},
l~                     e# Read the input as string and evaluate it.
  `$,:L                e# Copy the array and take its length. Store that in L
       ,:)             e# Get an array of 1 to L
          m*           e# Cartesian power of array 1 to L of size H (height of wall)
            {1bL=},    e# Take only those parts whose sum is L

```

After this, we have all possible ways of splitting up our input array into H brick layers.

2) Get all permutations of the input array and then further get all partitions for all permutations

```
\e!\m*{~W<{/(\e_}%}%
\e!                    e# Put the input array on top of stack and get all its permutations
   \m*                 e# Put the all possible partition array on top and to cartesian
                       e# product of the two permutations. At this point, every
                       e# permutation of the input array is linked up with every
                       e# permutation of splitting L sized array into H parts
      {           }%   e# Run each permutation pair through this
       ~W<             e# Unwrap and remove the last part from the partition permutation
          {     }%     e# For each part of parts permutation array
           /           e# Split the input array permutation into size of that part
            (\         e# Take out the first part and put the rest of the parts on top
              e_       e# Flatten the rest of the parts so that in next loop, they can be
                       e# split into next part length

```

After this, we have all possible layouts of the input bricks into an `H` layers brick wall.

3) Filter out only those layouts whose brick lengths are same

```
{::+)-!},
{      },              e# Filter all brick layouts on this condition
 ::+                   e# Add up brick sizes in each layer
    )-!                e# This checks if the array contains all same lengths.

```

After the end of this filter, all remaining layouts would be perfect rectangles.

4) Take out the first brick layout which matches the stability criteria

```
{{_,,\f<1fb}%2ew{:&,(},!}=
{                       }=   e# Choose the first array element that leaves truthy on stack
 {         }%                e# For each brick layer
  _,,                        e# Create an array of 0 to layer length - 1
     \f<                     e# Get all sublists starting at 0 and ending at 0
                             e# through length - 1
        1fb                  e# Get sum of each sub list. This gives us the cumulative
                             e# length of each brick crack except for the last one
           2ew               e# Pair up crack lengths for every adjacent layer
              {    },        e# Filter layer pairs
               :&            e# See if any cumulative crack length is same in any two
                             e# adjacent layers. This means that the layout is unstable
                 ,(          e# make sure that length of union'd crack lengths is greater
                             e# than 1. 1 because 0 will always be there.
                     !       e# If any layer is filtered through this filter,
                             e# it means that the layer is unstable. Thus negation

```

After this step, we simply have to print the layout

5) Print the layout

```
{{(2*'_*'[\']}/N}/
{               }/           e# For each brick layer
 {           }/              e# For each brick
  (2*'_*                     e# Get the (brick size - 1) * 2 underscores
        '[\']                e# Surround with []
               N             e# Newline after each layer

```

Try it online here

---

# 82 bytes

```
l~:H;{e_mrH({H-X$,+(mr)/(\e_}%_::+)-X${_,,\f<1fb}%2ew{:&,(},+,}g{{(2*'_*'[\']}/N}/

```

This is almost similar to the 92 byte version, except that it has a touch of randomness. If you have read the explanation for the 92 byte version, then in the 82 byte version, parts 3, 4 and 5 are exactly same, while instead of iterating over all permutations from part 1 and 2, this version simply randomly generates one of the permutation at a time, tests it using part 3 and 4, and then restarts the process if the tests of part 3 and 4 fail.

This prints the results very quickly for the first 3 test cases. The height = 5 test case is yet to give an output on my computer.

**Explanation of the difference**

```
l~:H;{e_mrH({H-X$,+(mr)/(\e_}%_::+)-X${_,,\f<1fb}%2ew{:&,(},+,}g
l~:H;                           e# Eval the input and store the height in H
     {   ...   }g               e# A do-while loop to iterate until a solution is found
      e_mr                      e# Flatten the array and shuffle it.
          H({               }%  e# This is the random partition generation loop
                                e# Run the loop height - 1 times to get height parts
             H-X$,+(            e# While generating a random size of this partition, we
                                e# have to make sure that the remaining parts get at least
                                e# 1 brick. Thus, this calculation
                    mr)         e# Get a random size. Make sure its at least 1
                       /(\e_    e# Similar to 92's part 2. Split, pop, swap and flatten

_::+)-                          e# 92's part 3. Copy and see if all elements are same
      X${_,,\f<1fb}%2ew{:&,(},  e# 92's part 4. Copy and see if layers are stable
+,                              e# Both part 3 and 4 return empty array if
                                e# the layout is desirable. join the two arrays and
                                e# take length. If length is 0, stop the do-while

```

*The idea for this version was given by randomra (Get it ?)*

Try this one online
> 13 votes

# Answer
# Python 2, ~~680~~ ~~670~~ 660 bytes

I don't know why I insist on having these super long "golfs"... but anyway, here you go.

```
M,L,R,N=map,len,range,None
exec"J=@:M(''.join,x);B=@:'['+'_'*2*~-x+']';K=@:M(B,x);W=@:J(M(K,x));C=@:set(M(sum,[x[:i]for i in R(L(x))]))-{0};T=@,w:w[x:]+w[:x]\ndef F(i):f=filter(@:i[x-1]&i[x],R(1,L(i)));return f and f[0]".replace('@','lambda x')
def P(e,x,i,w,h):
 for j in[-~_%h for _ in R(i-1,h+i-2)]:
    for s in R(w):
     if not e&C(T(s,x[j])):return j,s
 return N,N
def b(l,h):
 w,d=[[]for _ in R(h)],2*sum(l)/h
 for _ in l[::-1]:q=M(L,W(w));w[[q.index(i)for i in sorted(q)if i+L(B(_))<=d][-1]]+=_,
 g=M(C,w);i=F(g)
 while i:
    e=g[i-1];j,s=P(e,w,i,d,h)
    if j!=N:w[j]=T(s,w[j]);w[i],w[j]=w[j],w[i];g=M(C,w);i=F(g)
    else:b(T(-1,l),h);return
 print'\n'.join(W(w))

```

This requires the output in sorted ascending order, and is called via `b(brick_sizes, height)`.

Test cases:

```
>>> tests = [([1, 1, 2, 2], 2),([1, 1, 1, 2, 2, 2, 2, 3], 2), ([1, 1, 2, 2, 3, 3, 3, 3], 3), ([1, 2, 3, 4, 5, 6, 7, 8, 9], 5), ([1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 5)]
>>> for t in tests:
...     b(*t); print
...
[__][]
[][__]

[____][__][__]
[][][__][__][]

[____][____]
[__][__][][]
[____][____]

[________________]
[______________][]
[____________][__]
[__________][____]
[________][______]

[__][__][]
[][__][__]
[__][__][]
[][__][__]
[__][__][]

```

The way this works is:

1. Assign the bricks (longest-\>shortest) to layers, trying to fill each layer before moving to the next.
2. Whenever adjacent layers are unstable, try swapping layers and shifting bricks until you find something that works.
3. If nothing works, move the longest brick to the front of the sizes list and recurse.
> 9 votes

# Answer
# Haskell, 262 bytes

```
import Data.List
c=concat
n=init.scanl1(+)
1%l=[[[l]]]
n%l=[map(h:)(c$(n-1)%t)|(h,t)<-map(`splitAt`l)[1..length l]]
v[x]=1<2
v(x:y:z)=sum x==sum y&&n x==n x\\n y&&v(y:z)
l#n=unlines$map(>>=(\b->'[':replicate(2*b-2)'_'++"]"))$head$filter v$c.(n%)=<<permutations l

```

Example usage:

```
*Main> putStr $  [1, 2, 3, 4, 5, 6, 7, 8, 9] # 5
[______][________]
[__________][____]
[____________][__]
[][______________]
[________________]

*Main> putStr $ [1, 1, 2, 2, 3, 3, 3, 3] # 3
[____][____]
[__][__][][]
[____][____]

```

How it works: the main function `#` takes a list `l` (list of bricks) and a number `h` (height) and splits all permutations of `l` into `h` sublists at all possible positions (via function `%`, e.g. `2%[1,2,3,4]` -\> `[ [[1],[2,3]] , [[1,2],[3]] , [[1,2,3],[]] ]`) . It keeps those where two consecutive elements have the same sum (i.e. same length in bricks) and the lists of subtotals don't have common elements (i.e. cracks don't line up, function `v`). Take the first list that fits and build a string of bricks.
> 5 votes

# Answer
# Python 2, ~~528~~, ~~417~~, ~~393~~, 381

Very long, bruteforce solution. It works but that's about it, the universe may end before getting the result for the last test case.

```
exec u"from itertools import*;m=map;g=@w,n:([[w]],[[w[:i]]+s#i?range(1,len(w))#s?g(w[i:],n-1)])[n>1];r=@x:set(m(sum,[x[:i]#i?range(1,len(x))]));f=@w:1-all(m(@(x,y):not x&y,zip(m(r,w[:-1]),m(r,w[1:]))));a=@s,h:['\\n'.join([''.join(['[%s]'%(' '*(s-1)*2)#s?r])#r?o])#p?permutations(s)#o?g(p,h)if len(set([sum(r)#r?o]))<2 and~-f(o)][0]".translate({64:u"lambda ",35:u" for ",63:u" in "})

```

**a** is the main function:

```
>> a([1, 1, 2, 2], 2)
'[][  ]\n[  ][]'

```
> 4 votes

# Answer
# JavaScript (ES6) 222 ~~232 265 279 319~~

~~Still to be golfed.~~ This one find all the solutions, output just the last found, and it's quite fast.

Run snippet in Firefox to test

```
f=(n,h,b=[],s=0)=>
  (R=(z,l,p,k,t)=>
    z?b.map((v,a)=>
      v&&k.indexOf(v=t+a)<0&v<=s&&(
        --b[a],h=l+`[${'__'.repeat(a-1)}]`,
        v-s?R(z,h,[...p,v],k,v):R(z-1,h+'\n',[],p,0),
        ++b[a]
      ))
    :n=l
  )(h,'',[],[],0,n.map(n=>(b[n]=-~b[n],s+=n)),s/=h)&&n

// Test suite

out=x=>OUT.innerHTML=OUT.innerHTML+x+'\n'

;[
 [[1, 1, 2, 2], 2], [[1, 1, 1, 2, 2, 2, 2, 3], 2], [[1, 1, 2, 2, 3, 3, 3, 3], 3]
,[[1, 2, 3, 4, 5, 6, 7, 8, 9], 5], [[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 5]]
.forEach(([a,b])=>out(a+' '+b+'\n'+f(a,b)))
```

```
<pre id=OUT></pre>
```

**Ungolfed** And explained

```
function f(n, h) {
  var b=[], s=0, result // in golfed version will re-use n for result variable
  n.forEach(function (n) {
    b[n] = -~b[n] // group equal input numbers in buckets
    s+=n          // calc sum of input numbers
  });
  // example of buckets: input 1,1,4,1,5,4 -> b[1]=3,b[4]=2,b[5]=1
  s /= h // total sum / height => sum expected for each brick layer

  // recursive scan function
  function R(z, // layer count, from h downto 1
             l, // output so far
             p, // current layer partial sums array, mark intervals between bricks
             k, // prev layer parial sums, checked to avoid faulds
             t  // current partial sum
             )
  {
    if (z > 0)
    { // still building
      b.forEach( function (v,a) { // a:number from input list, v: repeat count
        var w, m   // locals (in golfed version, reuse other variables avoid defining locals)
        w = t + a; // increased running total for current layer
        if (v != 0  // repeat count still > 0
           && k.indexOf(w) < 0 // running total not found on list in prev layer (no fault)
           && w <= s) // current layer length not exceeded
        {
           --b[a]; // decrease repeat count, number used one more time
           m = l+"["+ '__'.repeat(a-1) + "]"; // new output with a brick added
           // l is not changed, it will be used again in this loop
           if (w == s)
           {   // layer complete, go to next (if any)
               // recurse, new layer, add newline to output, p goes in k, and t start at 0 again
               R(z-1, m+'\n', [], p, 0);
           }
           else
           {   // layer still to complete
               // recurse, same layer, m goes in l, add current sum to array p
               R(z, m, [...p,w], k, w);
           }
           ++b[a]; // restore value of repeat count for current loop
        }
      })
    }
    else
    { // z == 0, all layers Ok, solution found, save in result and go on to next
      result = l;
    }
  }

  R(h,'',[],[],0);
  return result; // this is the last solution found
}

```
> 4 votes

# Answer
## Python 2, grid method (290 chars)

```
x,h=input()
from itertools import *
w = sum(x)*2/h
for p in permutations(x):
 bricks = ''.join('[' + '_'*(2*n-2) + ']' for n in p)
 cols = map(''.join,zip(*zip(*[iter(bricks)]*w)))
 if all(c=='[' for c in cols[0]) and all(c==']' for c in cols[-1]) and not any(']]' in col or '[[' in col for col in cols[1:-1]):
  print('\n'.join(map(''.join,zip(*cols))))
  print()

```

The method here is you transpose the grid and look for a `[[` or `]]` anywhere in the columns. You also test that all the bricks on the left and right sides of the wall line up: the cute thing here is to test that all elements of a string are the same: `'[[[[[['.strip('[')==''`

---

mini version of above:

```
x,h=input()
from itertools import*
w=sum(x)*2/h
z=zip
j=''.join
for p in permutations(x):
 C=map(j,z(*z(*[iter(j('['+'_'*(2*n-2)+']'for n in p))]*w)))
 if C[0].strip('[')==''and C[-1].strip(']')==''and not any(']]'in c or '[['in c for c in C[1:-1]):
  print('\n'.join(map(j,z(*C))))
  break

```

---

This could probably be done more easily in a matrix-manipulation language.

...or abuse of regexes, which lets us combine the "blocks align on ends" condition with the "no cracks" condition:

Say the width of the wall was w=6. The locations of the substring "\[.....\[", and "\].....\]" must be exactly the set {0,w-1,w,2w-1,2w,3w-1,...}. Not-existence at those points means the bricks 'linewrap' like so:

```
       v
[][__][_
___][__]
       ^

```

Existence NOT at those points means there is an unsteady 'crack' in the wall:

```
     vv
[][__][]
[    ][]
     ^^

```

Therefore we reduce the problem to set equivalence, where the sets in questions are the indices of a regular expression match.

```
# assume input is x and height is h

from itertools import *
import re
w=sum(x)*2/h

STACKED_BRACKET_RE = r'(?=\[.{%i}\[|\].{%i}\])'%(w-1,w-1)  # ]....] or [....[
STRING_CHUNK_RE = '.{%i}'%w  # chunk a string with a regex!
bracketGoal = set().union(*[(x*w,x*w+w-1) for x in range(h-1)])  # expected match locations

for p in permutations(x):
 string = ''.join('['+'_'*(2*n-2)+']'for n in p)
 bracketPositions = {m.start() for m in re.finditer(STACKED_BRACKET_RE,string)}
 print(string, bracketPositions, bracketGoal, STACKED_BRACKET_RE) #debug
 if bracketPositions==bracketGoal:
  break

print('\n'.join(re.findall(STRING_CHUNK_RE,string)))

```

---

## Python, regexp method (304 chars):

```
from itertools import*
import re
x,h=input()
w=sum(x)*2/h
for p in permutations(x):
 s=''.join('['+'_'*(2*n-2)+']'for n in p)
 if {m.start()for m in re.finditer(r'(?=\[.{%i}\[|\].{%i}\])'%(w-1,w-1),s)}==set().union(*[(x*w,x*w+w-1) for x in range(h-1)]):
  break

print('\n'.join(re.findall('.{%i}'%w,s)))

```
> 2 votes

# Answer
# PowerShell, 266 bytes

```
param($b,$h)$w=($b|%{'['+'__'*--$_+']'})+,"
"*--$h|sort;filter p{if($k=--$_){$k|p;0..($k-1)|%{$j=($_,0)[$_%2];$w[$j],$w[$k]=$w[$k,$j]
$k|p}}else{,(-join$w-split"
")}}$w.Length|p|?{!(($x=($a=$_)|% Le*|gu).Rank-or-join(1..($x-2)|%{$a|% Ch* $_})-match']]')}|select -f 1

```

Try it online!

This script is brute force algorithm:

1. converts numbers to related strings \[\], \[\__\], \[\____\], ...
2. adds as many LFs as the height is
3. generates all permutations by Heap's algorithm
4. checks and PassThru a valid wall only
5. returns first only wall

What can be improved: generate permutations for numbers, not strings. build a string representation in final.

Unrolled:

```
param($briks,$height)

$wall =
    ($briks|%{'['+'__'*--$_+']'})   +   # string [], [__], ... related to numbers
    ,"`n"*--$height                 |   # as many LF as the height
    sort                                # sort briks and LFs

# Heap's algorithm generates all possible permutations of $_ objects
# https://en.wikipedia.org/wiki/Heap%27s_algorithm
filter get-permutation{
    if($k=--$_){
        $k|get-permutation
        0..($k-1)|%{
            $j=($_,0)[$_%2]
            $wall[$j],$wall[$k]=$wall[$k,$j]
            $k|get-permutation
        }
    }
    else{
        ,(-join$wall -split "`n")       # return an array of strings represent a wall
    }
}

$wall.Length|get-permutation|where{     # generates all permutations, then check and PassThru a valid wall only
    !(                                                  # not
        ($x=($a=$_)|% Length|Get-Unique).Rank -or       #   length of all wall rows are different or
        -join(1..($x-2)|%{$a|% Chars $_})-match']]'     #   the wall is not steady
    )
}|select -First 1

```
> 1 votes

# Answer
# 05AB1E, 36 bytes

```
œIδ.Œ€`ʒOË}.ΔεηO¨}üåà≠}<·'_×€€…[ÿ]J»

```

Slow brute-force approach (already times out for the last test case on TIO), but it works.

First input is the list of brick sizes and second input is the height integer.

Try it online or verify a few test cases at once.

**Explanation:**

First get all possible ways to divide the list of bricks into the height amount of rows (resulting in a list of list of list of integers, which we'll reference to as list of walls for now):

```
œ       # Take the powerset of the (implicit) input-list
        # (this holds a list of all possible ways to order the input-list)
 I      # Using the second height integer,
  δ     # map each inner permutation of the input-list to:
   .Œ   #  Get all possible ways to divide the permutation into the height amount of pieces
     €` # Then flatten once

```

Then we'll filter this list to only keep walls whose rows have an equal width (so we're left with all rectangular walls):

```
ʒ       # Filter this list of walls by:
 O      #  Take the sum of each inner row
  Ë     #  Check if the sums of all the rows are equal
}       # Close the filter

```

Then we'll search for the first wall which doesn't have any vertical gaps between two adjacent rows:

```
.Δ      # Find the first wall which is truthy for:
  ε     #  Map each row to:
   η    #   Get the prefixes of bricks in this row
    O   #   Sum each prefix
     ¨  #   Remove the last (right side of the wall), since those are supposed to line up
  }     #  Close the inner map (we now have a list of list of integers, a.k.a. list of gaps)
   ü    #  Map over each pair of gaps:
    å   #   Check for each gap in the second gaps-list if it's in the first gaps-list
     à  #  Take the flattened maximum to check if any is truthy
      ≠ #  And invert that boolean, since we want to find a wall without gaps lining up
}       # Close the find_first

```

Now we've found our wall. All that's left is to transform it into the desired output-format and print it:

```
<       # Decrease each brick-value by 1
 ·      # Then double each
  '_×  '# And convert those integers to that amount of "_" as string
€       # Then map over each row:
 €      #  And each inner brick consisting of "_"
  …[ÿ]  # And surround it by "[" and "]"
J       # Then join each list of bricks together to form the rows
 »      # And join those rows by newlines to form the wall
        # (after which this is output implicitly as result)

```
> 1 votes

# Answer
# PHP, ~~918~~ ~~870~~ 650 bytes

```
[$z,$h]=json_decode($argn);$j=$h-1;$p=array_fill(0,$c=100,[0,array_chunk($z,ceil(count($z)/$h))]);$r=fn($x)=>rand(0,$x);g:foreach($p as&$s){$b=[];for($s[0]=$l=0;$l<$h;$l++){for($m=$k=0;$k<~-count($v=$s[1][$l]);)$b[$l][]=$m+=$v[$k++];$s[0]+=abs(array_sum($z)/$h-$m-$v[$k]);}for($l=0;$l<$j;){if(array_intersect($b[$l]??[],$b[1+$l++]??[]))$s[0]+=9;}}usort($p,fn($a,$b)=>$a[0]<=>$b[0]);if(!$p[0][0]){foreach($p[0][1]as$l){foreach($l as$b)echo'[',str_repeat('_',~-$b*2),']';echo"\n";}die;}for($o=0;$o<99;$o++){$w=&$p[(int)sqrt($r($c*$c-1))][1];$a=&$w[$r($j)];$t=&$a[$i=$r($u=count($a)-1)];if($u){unset($a[$i]);$a=array_values($a);$w[$r($j)][]=$t;}}goto g;

```

Try it online!

## Ungolfed

The idea is to use a hill climbing approach.

A population of walls is set up and each wall is scored. There are penalties for a wall's row of bricks not matching the expected width and for bricks lining up on consecutive rows. The scores are then ordered and a mutation operation applied favouring higher (worse) scoring walls.

Scoring and mutation are applied in succesive rounds until a solution is found. Solutions are usually found in under a second - except for the last test case, so it's quick (although bloaty).

```
[$brick_sizes,$height]=json_decode($argn);

$width = array_sum($brick_sizes)/$height;

$walls=[];

$walls[0]=array_chunk($brick_sizes,ceil(count($brick_sizes)/$height));

$population_count = 100;

// Clone default wall and set up initial population
for ($wall_index=1;$wall_index<$population_count;$wall_index++) {
    $walls[$wall_index] = $walls[0];
}

$iteration = 0;
do {
    // score population
    $scores = array_fill(0,$population_count, [0,0]);
    foreach ($walls as $wall_index => $wall) {
        foreach ($wall as $level) {
            $scores[$wall_index][0] += abs($width - array_sum($level));
            $scores[$wall_index][1] = $walls[$wall_index];
        }

        // Score alignment of bricks with penalty
        $brick_positions=[];
        for ($level=0;$level<$height;$level++) {
            $running_sum=0;

            for ($brick_index=0;$brick_index<(count($wall[$level])-1);$brick_index++) {
                $running_sum += $wall[$level][$brick_index];
                $brick_positions[$level][] = $running_sum;
            }

        }

        for ($level=0;$level<($height-1);$level++) {
            if (array_intersect($brick_positions[$level]??[],$brick_positions[$level+1]??[])) {
                $scores[$wall_index][0] += 10;
            }
        }

    }

    // sort score by best fit first
    usort($scores, function ($a, $b) {
        return $a[0] <=> $b[0];
    });

    //echo $iteration,':',$scores[0][0],"\n";

    // draw wall and exit
    if ($scores[0][0] == 0) {
        foreach ($scores[0][1] as $level){
            foreach ($level as $brick){
                echo '['.str_repeat('_',2*($brick-1)).']';
            }
            echo "\n";
        }
        die;
    }

    // sort population by score
    $walls = array_map(function($m){return $m[1];},$scores);

    // randomise bricks in population
    for ($rando = 0; $rando < 100; $rando++) {
        $wall_index = (int)sqrt(rand(0, $population_count*$population_count - 1));
        $level = [];
        $index = [];
        for ($do = 0; $do <= 1; $do++) {
            $level[$do] = rand(0, $height - 1);
            $index[$do] = rand(0, count($walls[$wall_index][$level[$do]]) - 1);
        }

        $temp = $walls[$wall_index][$level[0]][$index[0]];

        if (count($walls[$wall_index][$level[0]])>1) {
           unset($walls[$wall_index][$level[0]][$index[0]]);
           $walls[$wall_index][$level[0]]=array_values($walls[$wall_index][$level[0]]);
           $walls[$wall_index][$level[1]][] = $temp;
        }
    }

    $iteration++;

} while (true);

```

Try it online!
> 1 votes

# Answer
## Matlab (359)

```
function p(V),L=perms(V);x=sum(V);D=find(rem(x./(1:x),1)==0);for z= 2:numel(D-1)for y=1:numel(L),x=L(y,:);i=D(z);b=x;l=numel(x);for j=1:l,for k=j-1:-1:2,m=sum(x(1:k));if mod(m,i),if mod(m,i)<mod(sum(x(1:k-1)),i)||sum(x(1:j))-m==i,b=0;,end,end,end,end,if b,for j=1:l,fprintf('[%.*s]%c',(b(j)-2)+b(j),ones(9)*'_',(mod(sum(x(1:j)),i)<1)*10);end,return,end;end,end

```

## Input

a vector of integers , example: p(\[1 1 2 2 3\])

## Output

the scheme of the wall example:

```
[____]

[__][]

[][__]

```
> 0 votes

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


title: Cutting Sequence for N dimensions

text:
# Question
Title: Cutting Sequence for N dimensions
# Inputs:

The program or function should take 2 vector-like (e.g. a list of numbers) O and V of the same number of dimensions, and a number T (all floating-point numbers or similar)

### Constraints:

* T \>= 0
* All elements of Vector O will be in the range `[0,1)`

# Output:

The program or function should output the N dimensional cutting sequence given an infinite ray whose origin is the first vector, and whose velocity is the second vector. The sequence should include every cut the ray makes on the time interval `(0, T]`, appearing in order of when they occur. Details on the format and specification of the sequence are explained below

# Cutting sequence

In a N dimensional Cartesian coordinate system, there exist **axis-aligned unit coordinate facets**, e.g. the integer points on a 1 dimensional number line, the unit grid lines on a 2D grid, planes like `x = 1`, `z =- 10` or `y = 0` in 3D space. As this problem is generalized to N dimensions, from here forward we will no longer use lettered axes, but instead number the axes starting with 0. Every facet can be defined by some equation like `Axis j = k`, where `j` and `k` are integers, and `j` is the characteristic axis of the facet.

As the ray extends through N dimensional space, it intersects these facets. This is called a cut. Each of these cuts is described by 2 things.

1. The characteristic axis of the facet.
2. The direction of the cut, i.e. whether the ray extending positively or negatively with respect to the characteristic axis.

Hence each cut shall be outputted in the sequence as a string of a plus or minus sign corresponding to the direction of the cut, then the number (base 10) of the characteristic axis of the cut facet.

The sequence will be outputted as a continuous string of these cuts, e.g. `+0+1+0+0+1-2+0`

# Examples

This image from the Wikipedia page for Cutting Sequence shows a 2D example. This is equivalent to `O=[0,0] V=[1,0.618] T = 6.5`, where the output is `+0+1+0+0+1+0+1+0+0+1`

For 1 dimension, all non-empty cutting sequences will look like `+0+0+0...` or `-0-0-0...`

More examples / test cases to be added

# Special cases

* If two or more cuts occur at exactly the same time (to the precision of your numeric type), they must appear in the sequence in order of their axis from least to greatest
* Your program should be accurate for extreme input values
    + e.g. for `V=[1, -0.0009765625]`, the sequence will have a repeating pattern of `+0` 1024 times and then a `-1`. This pattern should hold exactly for arbitrarily large values of T
* Your program must always output a sequence, e.g.
    + If Vector V has a length 0, the program should not loop indefinitely, but output an empty sequence.
    + If the inputs are of 0 dimensions, the program should output an empty sequence

# Answer
> 2 votes
# Python, 226 bytes

Assumes the lists `O` and `V` are defined, as well as the time `T`, either an int or a float.

Try it online

```
s=lambda x:int(x/abs(x));r=range;f=lambda O,V,T:"".join(map(lambda t:t[1],sorted(sum([[((i-o)/v,"%+d"%(s(v)*c))for i in r((v>0)-(v<0)*(o==0),int((o+T*v)//1)+(v>0),s(v))]for c,o,v in zip(r(len(O)),O,V)],[]),key=lambda t:t[0])))

```

The idea of the code is simple, first we loop over all coordinates, and for each coordinate we:

1. find where the first cut is, depending on the sign of `v` and the origin being `0` or not, the first cut might be at `-1`, `0` or `1`;
2. find how far the ray goes in the time given with `o + v*T` (which then needs proper rounding to be an argument for the `range` function);
3. find the time `t` for which each successive cut occurs, by solving `o + v*t = i` iff `t = (i - o)/v`, for the successive integer values of `i` (this amounts to finding the time for which the ray crosses the hyperplane `x_c = i`);
4. sort everything by the time and drop the time, as it was just an auxiliary thing.

The code un-golfed:

```
# sign function, returns 1 for positive numbers and -1 for negative numbers
sgn = lambda x: int(x/abs(x))
l = []
# c is the coordinate we are in,
# o is the origin in this coordinate and v the velocity
for (c, o, v) in zip(range(len(O)), O, V):
    # find all the cuts for this coordinate
    sub_l = []
    # this is how far the ray goes, rounded to integers, in T seconds
    stop_at = int((o + T*v)//1) # if this is negative, //1 pushes the result away from 0
    if v > 0:
        stop_at += 1
    # this is where the first cut occurs (depends on o == 0 and the sign of v)
    if v > 0:
        start_at = 1
    elif o > 0:
        start_at = 0
    else:
        start_at = -1
    for i in range(start_at, stop_at, sgn(v)):
        # this is the time at which the ray cuts the x_c = i hyperplane
        t = (i - o)/v
        # append the time of the cut and the signed axis
        sub_l.append((t, "%+d"%(sgn(v)*c)))
    l.append(sub_l)
print(l)
# flatten list
l = sum(l, [])
# order list by the time at which the cut occurs
l.sort(key = lambda tup: tup[0])
# remove the times, keep the coordinates
l = map(lambda tup: tup[1], l)
# join and print
print("".join(l))

```

Then we just need to note a couple of things, like I can save some bytes if I redefine `r = range` or if I assign `start_at = (v>0)-(v<0)*(o==0)` and `stop_at = int((o+T*v)//1)+(v>0)`.

I don't feel this is properly golfed, I just wrote a program that works and then crammed everything together. Please feel free to give me some feedback.

I used a flatten from https://stackoverflow.com/a/952946/2828287 and getting the sign of a number from https://stackoverflow.com/a/2763445/2828287

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


title: Introduce Your Language!

text:
# Question
Title: Introduce Your Language!
Your task is to write a program or function that takes a string as input, and prints `Hello (input), I'm (language name)`.

## Examples

**Python:**
Input: `Oliver`
Output: `Hello Oliver, I'm Python`

**C++:**
Input: `Jacob`
Output: `Hello Jacob, I'm C++`

etc.

Remember, this is , so the code with the lowest number of bytes wins.

## Leaderboards

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

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

```
# Language Name, N bytes

```

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

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

```

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

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

```

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

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

```

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

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

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

# Answer
> 5 votes
# pl, 15 bytes

```
Hello _, I'm pl

```

Try it online!

# Answer
> 8 votes
## Python, 29 bytes

```
"Hello {}, I'm Python".format

```

Strings methods for the win! The built-in method format of a string substitutes the arguments (here a single string) into any replacement fields (here `{}`).

Usage:

```
f = "Hello {}, I'm Python".format
print f("xnor")

```

```
Hello xnor, I'm Python

```

Previous 30-byte:

```
"Hello %s, I'm Python".__mod__

```

# Answer
> 5 votes
# Assembly (x86-64, Linux), ~~217~~ 205 bytes

*4927 segmentation faults later...*

```
.global main
.data
s:.ascii"Hello %qs, I'm Assembly\n"
f:.ascii"%qs"
i:.ascii""
main:mov $i,%rsi
mov $f,%rdi
mov $0,%rax
call scanf
mov $0,%rax
mov $i,%rsi
mov $s,%rdi
call printf
end:mov $0,%rax
call exit

```

Doesn't work for inputs with a length greater than 7, because this exceeds the memory limits of a quadword(?). Also, because I'm a noob in Assembly.

### Explanation:

```
.global main

.data

output_string: .ascii "Hello %qs, I'm Assembly\n"
format_input: .ascii "%qs"
input_string: .ascii ""

main:
    mov $input_string, %rsi     # Place the memory address to the second argument
    mov $format_input, %rdi     # Place the format string to the first argument
    mov $0, %rax                # Set RAX to 0
    call scanf                  # Call scanf with RDI and RSI as the arguments

    mov $0, %rax                # Set RAX to 0
    mov $input_string, %rsi     # Place the input string to the second argument
    mov $output_string, %rdi    # Place the output format to the first argument
    call printf                 # Call printf with RDI and RSI as the arguments

end:
    mov $0, %rax                # Set RAX to 0 (which is the exit code)
    call exit                   # Call the exit function

```

Save in a file called *myProgram.s* and do the following:

```
$ gcc -o myProgram myProgram.s
$ ./myProgram

```

# Answer
> 4 votes
# 05AB1E, ~~21~~ 17 bytes

```
”Ÿ™ ÿ, I'm 05AB1E

```

Try it online!

# Answer
> 3 votes
# Java, 88 bytes

```
interface A{static void main(String[]a){System.out.print("Hello "+a[0]+", I'm Java!");}}

```

Takes input on first command-line argument. Verbose Java is verbose.

# Answer
> 3 votes
# Jelly, 16 bytes

```
“' ṗr>ƊḳȧT°ḋZ»Ỵj

```

Try it online!

### How it works

Call the argument of the main link **s**.

```
“' ṗr>ƊḳȧT°ḋZ»

```

represents an integer in bijective base 256 that encodes a sequence of dictionary words and/or characters. In this specific case, it encodes the dictionary word **Hello**, followed by **¶, I'm** with a leading space ( represents a linefeed), followed by the dictionary word **Jelly** with a leading space.

The result is as follows.

```
Hello
, I'm Jelly

```

The  atoms splits this string at linefeeds, yielding the following array.

```
["Hello ", "", I'm Jelly"]

```

Finally, the `j` atom joins that array, using the string **s** as separator.

# Answer
> 3 votes
# Cheddar, 26 bytes

```
"Hello %s I'm Cheddar"&(%)

```

# Answer
> 3 votes
## Straw, 25 bytes

```
(Hello b, I'm Straw!)b</>

```

Try it online!

Simple regex substitution.

# Answer
> 3 votes
# Minecraft, 27 bytes

```
say Hello @p, I'm Minecraft

```

`say` Prints the given string and replaces `@p` with the name of the nearest player

# Answer
> 2 votes
# MATL, 24 bytes

```
'Hello %s, I''m MATL'jYD

```

**Try it Online!**

# Answer
> 2 votes
# Element, 28 bytes

```
Hello\ _\,\ I\'m\ Element..`

```

(link to TIO)

Woo! Two months since this site's previous Element answer!

# Answer
> 2 votes
## Batch, 25 bytes

```
@echo Hello %*, I'm Batch

```

Conveniently `'` isn't a quote character in Batch.

# Answer
> 2 votes
# Emotinomicon, 73 bytes

```
Hello✖➕⏫, I'm Emotinomicon⏪⏬⏩

```

If you go to the Interpreter you can generate an explanation

Thanks to @Oliver Ni for make me notice that bug that Emotinomicon removes whitespaces at the end of the String literal

# Answer
> 1 votes
# sh, 24 bytes

```
echo "Hello $1, I'm sh!"

```

# Answer
> 1 votes
## Pyke, 21 bytes

```
"Hello , I'm Pyke"6Q:

```

Try it here!

# Answer
> 1 votes
# Nim, 40 bytes

```
echo "Hello "&stdin.readAll&", I'm Nim!"

```

# Answer
> 1 votes
# PHP, 29 Bytes

```
<?="Hello $argv[1], I'm PHP";

```

# Answer
> 1 votes
## Pyth, 21 bytes

```
X6"Hello , I'm Pyth"Q

```

Try it here!

# Answer
> 1 votes
# JavaScript, 32 bytes

```
x=>`Hello ${x}, I'm JavaScript`

```

Simple enough. `${x}` is inline `x`, the argument.

# Answer
> 1 votes
# C, ~~50~~ 39 bytes

```
f(char*s){printf("Hello %s, I'm C",s);}

```

# Answer
> 1 votes
# J, 22 bytes

```
', I''m J',~'Hello '&,

```

This is a fork:

```
', I''m J' ,~ 'Hello '&,

```

`'Hello '&,` prepends `Hello` and `', I''m J' ,~` appends `, I'm J`.

Example run:

```
   (', I''m J',~'Hello '&,)'Conor'
Hello Conor, I'm J

```

# Answer
> 1 votes
# Jolf, ~~20~~ 17 bytes

```
"Ξ\x08£C¦i, I‘m Jolf

```

Try it here! Replace `\x08` with the literal character.

`¦i` is interpolated input, and `Ξ\x08£C` is compressed form of `Hello` with a trailing space. This outputs, for input `Conor`:

```
Hello Conor, I'm Jolf

```

---

Alternatively, for 23 bytes:

```
"Hello ¦i, I‘m ¦ᖒ

```

# Answer
> 1 votes
# dc, 23 bytes

```
[, I'm dc!]?[Hello ]PPP

```

dc doesn't provide any means of getting raw strings, so you have to wrap your input in `[`brackets`]`. For example:

```
$ dc hello.dc <<< [Daniel]
Hello Daniel, I'm dc!

```

# Answer
> 1 votes
# GolfScript, 27 bytes

```
"Hello "\", I'm GolfScript"

```

Takes input from STDIN.

# Answer
> 1 votes
## Ruby, 32 bytes

```
puts "Hello #{$*[0]}, I'm Ruby"

```

Save as `intro.rb`, run as `ruby intro.rb <name>`.

# Answer
> 1 votes
# Scala, 25 bytes

```
n=>s"Hello $n, I'm Scala"

```

To use it, assign this function to a variable.

```
val greeting = n=>s"Hello $n, I'm Scala"
greeting("Jacob")

```

I didn't expect that you can drop the type annotation if the parameter is of type `Any`.

# Answer
> 1 votes
# Wren, 33 bytes

```
Fn.new{|x|"Hello %(x), I'm Wren"}

```

Try it online!

## Explanation

```
Fn.new{|x|                      } // New anonymous function
          "Hello %(x), I'm Wren"  // Surrounding the input w/ Hello & wren

```

# Answer
> 0 votes
# Python, 33 bytes

```
lambda a:"Hello %s, I'm Python"%a

```

# Answer
> 0 votes
# S.I.L.O.S ~~112~~ 110 bytes

```
loadLine
def : lbl
print Hello
a=256
:a
x=get a
if x c
if 1 e
:c
printChar x
a+1
if x a
lble
print , I'm S.I.L.O.S

```

It should be loosely readable. Just a trivial modification of the cat program

Try it online!

# Answer
> 0 votes
# CJam, 21 bytes

```
"Hello "l", I'm CJam"

```

Try it online!

# Answer
> 0 votes
# sed, 22 bytes

```
s/.*/Hello &, I'm sed/

```

**Try it online!**

**Run:**

```
sed -f hello.sed <<< "PPCG"

```

**Output:**

```
Hello PPCG, I'm sed

```

# Answer
> 0 votes
# Turing Machine Code, 360 bytes

```
0 * * l 1
1 _ [ l 2
2 _ o l 3
3 _ l l 4
4 _ l l 5
5 _ e l 6
6 _ H * 7
7 [ _ r 8
7 * * r *
8 _ ,  r 9
8 * * r *
9 _ _ r I
I _ I r '
' _ ' r m
m _ m r ~
~ _ _ r T
T _ T r u
u _ u r r
r _ r r i
i _ i r n
n _ n r g
g _ g r #
# _ _ r M
M _ M r a
a _ a r c
c _ c r h
h _ h r í
í _ i r ñ
ñ _ n r e
e _ e r ^
^ _ _ r C
C _ C r o
o _ o r d
d _ d r è
è _ e r halt

```

Try it online!

# Answer
> 0 votes
## `j`, ~~17~~ 14 bytes

Short language names for the win. (I beat pl, and Dennis as well)

```
L~¶├'◄b₧û☻♪▼ºº

```

## Explanation

```
Hello "           % Start the output string with "Hello"
       a          % Insert the input onto the stack
        ", I'm W" % End the output string with ", I'm W"
                  % Implicit join whole stack at the end of the program

```

# Answer
> 0 votes
# GolfScript, 28 bytes

```
"Hello
, I'm GolfScript"n/*

```

Try it online!

# Explanation

```
"Hello
, I'm GolfScript"    # Define the string to be inserted: "Hello \n, I'm GolfScript"
                 n/  # Split upon newlines             : ["Hello " ", I'm GolfScript"]
                   * # Join the array by input         : ["Hello input, I'm GolfScript"]

```

---
Tags: code-golf
---


title: Quoting Big Brother

text:
# Question
Title: Quoting Big Brother
Task: Have your program randomly choose one of the following two quotes at runtime and print that one quote, exactly as shown.

1:

```
Under the spreading chestnut tree
I sold you and you sold me.
There lie they, and here lie we
Under the spreading chestnut tree.

```

2:

```
WAR IS PEACE.
FREEDOM IS SLAVERY.
IGNORANCE IS STRENGTH.

```

Restrictions: The words `spreading`, `chestnut`, `PEACE`, `FREEDOM`, and `STRENGTH` **must** appear in your code. No word from the above two quotes may appear in your code **more than once**.

Shortest solution wins.

# Answer
# PHP 179

Inspired by es1024's answer.

```
<?=strtr(rand()%2?"0
I 1 232 1 me.
T5 they,35 we
0.
":"WAR4PEACE.
FREEDOM4SLAVERY.
IGNORANCE4STRENGTH.
",["Under the spreading chestnut tree",sold,you," and "," IS ","here lie"]);

```
> 3 votes

# Answer
# Perl (~~191~~ 184 characters)

```
$_=$$&1?"0
I12321me6T4they,34we
06":"WAR5PEACE6FREEDOM5SLAVERY6IGNORANCE5STRENGTH6";s/\d/("Under the spreading chestnut tree"," sold ",you," and ","here lie "," IS ",".
")[$&]/ge;print

```

Thanks @core1024 for tips on golfing this.
> 4 votes

# Answer
# Java, 338

I can't get it below 338...

```
class B{public static void main(String[]a){String b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=".\n",i=" IS ";if(Math.random()>.5)System.out.print(b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+h);else System.out.print("WAR"+i+"PEACE"+h+"FREEDOM"+i+"SLAVERY"+h+"IGNORANCE"+i+"STRENGTH"+h);}}

```

Bit ungolfed:

```
class B{public static void main(String[]a){String b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=".\n",i=" IS ";
if(Math.random()>.5)System.out.print(b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+h);
else System.out.print("WAR"+i+"PEACE"+h+"FREEDOM"+i+"SLAVERY"+h+"IGNORANCE"+i+"STRENGTH"+h);}}

```
> 3 votes

# Answer
# Javascript 229 ~~254 256~~

**Edit 1** using `new Date` as suggested by @Doorknob - still unclear to me how javascript Dates morph to strings or integers or whatever

**Edit 2** simplified. A lot.

```
t=(new Date&1
   ?'0WAR0 IS 0PEACE0.\n0FREEDOM020SLAVERY040IGNORANCE020STRENGTH.'
   :'0Under the spreading chestnut tree0\nI 0sold 0you 0and 04030me.\nT0here lie 0they, 05090we\n010.'
  ).split(0);
for(i=o='';j=t[++i];)o+=t[j|0||i];alert(o)

```
> 2 votes

# Answer
# C# (268)(260) (256)

This is executable in LINQPad, using the `Dump()` method:

```
string b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=" IS ";if(new Random().Next(9)>4)(b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+".").Dump();else("WAR"+h+"PEACE.\nFREEDOM"+h+"SLAVERY.\nIGNORANCE"+h+"STRENGTH.").Dump();

```

Ungolfed:

```
string b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=" IS ";

if(new Random().Next(9)>4)
    (b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+".").Dump();
else
    ("WAR"+h+"PEACE.\nFREEDOM"+h+"SLAVERY.\nIGNORANCE"+h+"STRENGTH.").Dump();

```

**Update:**

Using the ternary operator and 1 extra variable, I was able to cut another 6 characters:

```
string a,b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=" IS ";a=new Random().Next(9)>4?(b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+"."):("WAR"+h+"PEACE.\nFREEDOM"+h+"SLAVERY.\nIGNORANCE"+h+"STRENGTH.");a.Dump();

```

Ungolfed:

```
string a,b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=" IS ";

a=new Random().Next(9)>4 ?
    (b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+".") :
    ("WAR"+h+"PEACE.\nFREEDOM"+h+"SLAVERY.\nIGNORANCE"+h+"STRENGTH.");

a.Dump();

```

**Update2:**

Thanks to the ingenious suggestion of `tsavinho` I was able to save 4 more chars by placing braces around the ternary operation:

```
string b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=" IS ";(new Random().Next(9)>4?(b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+"."):("WAR"+h+"PEACE.\nFREEDOM"+h+"SLAVERY.\nIGNORANCE"+h+"STRENGTH.")).Dump();

```

Ungolfed:

```
string b="Under the spreading chestnut tree",c="sold ",d="you ",e="and ",f="me.\nT",g="here lie ",h=" IS ";
(new Random().Next(9)>4?
    (b+"\nI "+c+d+e+d+c+f+g+"they, "+e+g+"we\n"+b+"."):
    ("WAR"+h+"PEACE.\nFREEDOM"+h+"SLAVERY.\nIGNORANCE"+h+"STRENGTH.")
).Dump();

```
> 2 votes

# Answer
# Python 3 - 228

```
for x in[b"AB:87078@624>049BA6",b"?;<61;=63;56"][id(id)%3-1]:print("and |FREEDOM|T|IGNORANCE|here lie |STRENGTH|.\n|you |sold |we|I | IS |PEACE|SLAVERY|they, |WAR|me|Under the spreading chestnut tree|\n".split("|")[x-48],end="")

```

Slightly ungolfed:

```
# id(id) returns an even number based on memory address of id
# id(id)%3-1 gives -1, 0 or 1
randomNumber = id(id)%3-1

# Word list
words = "and |FREEDOM|T|IGNORANCE|here lie |STRENGTH|.\n|you |sold |we|I | IS |PEACE|SLAVERY|they, |WAR|me|Under the spreading chestnut tree|\n".split("|")

# Byte Literals for Under the chestnut and WAR IS PEACE
# each byte correspond to the word's index in the word list
byteLiterals = [b"AB:87078@624>049BA6", b"?;<61;=63;56"]
choice = byteLiterals[randomNumber]

for x in choice:
    print(words[x-48], end="") # Print each word out

```
> 1 votes

# Answer
# PowerShell 205

```
("{0}.`nI{1}{2}{3}{2}{1} me.`nT{4}they,{3} {4}we`n{0}."-f"Under the spreading chestnut tree"," sold"," you"," and","here lie "),("WAR","PEACE.`nFREEDOM","SLAVERY.`nIGNORANCE","STRENGTH."-join" IS ")|Random

```

Uses the `-f` operator to put strings on the first quote, and the second one is joined by `IS`, after that it selects a random element of those 2 quotes and prints it...
> 1 votes

# Answer
## JavaScript / jQuery 396

```
var B={
U:"Under the spreading chestnut tree",
s:"sold ",
y:"you ",
l:"lie ",
a:"and ",
i:"IS ",
b:"</br>"
};
var A={
P:B.U+B.b+"I "+B.s+B.y+B.a+B.y+B.s+"me."+B.b
+"There "+B.l+"they, "+B.a+"here "+B.l+"we."+B.b+B.U,
Q:"WAR "+B.i+"PEACE."+B.b+"FREEDOM "+B.i+"SLAVERY."+B.b
+"IGNORANCE "+B.i+"STRENGTH."
};
$(function(){
var z=(Math.random()<0.5)?A.P:A.Q;
$('#d').append(z);
});

```
> 1 votes

# Answer
# T-SQL, ~~337~~ 327

Just for fun, I've made another solution in T-SQL, which is one byte shorter than my Java 8 solution:

```
DECLARE @b char(33)='Under the spreading chestnut tree',@c char(5)='sold',@d char(4)='you',@e char(4)='and',@f char(9)='here lie',@ char='
',@h char(4)=' IS'IF rand()>.5PRINT @b+@+'I '+@c+@d+@e+@d+@c+'me.'+@+'T'+@f+'they, '+@e+@f+'we'+@+@b+'.'ELSE PRINT'WAR'+@h+'PEACE.'+@+'FREEDOM'+@h+'SLAVERY.'+@+'IGNORANCE'+@h+'STRENGTH.'

```

By declaring the `char`s one too long, you can add an 'automatic' space, saving up a few bytes.

Using the code in the proposed edit by user PenutReaper, you can indeed shave off 10 bytes.
> 1 votes

# Answer
# JavaScript, 233 bytes

```
Math.random()>0.5?(a="Under the spreading chestnut tree")+"\nI "+(s="sold")+(y=" you ")+(n="and")+y+s+" me.\nT"+(h="here ")+(l="lie ")+"they "+n+" "+h+l+"we\n"+a+".":["WAR","PEACE.\nFREEDOM","SLAVERY.\nIGNORANCE","STRENGTH."].join(" IS ")

```

Wrote this without looking at other answers. Makes good use of assignments as expressions.
> 1 votes

# Answer
# C (gcc), ~~307~~ ~~289~~ ~~271~~ 270 bytes

-37 bytes thanks to ceilingcat

```
*y=" IS ";main(){int*r[]={"WAR",y,"PEACE.\nFREEDOM",y,"SLAVERY.\nIGNORANCE",y,"STRENGTH.",0,"Under the spreading chestnut tree","\nI"," sold ","you"," and ",r[11],r[10],"me.\n","T","here lie ","they,",r[12],r[17],"we\n",r[8],".",0},z=r;for(z=z/2&8;r[z];)printf(r[z++]);}

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 119 bytes

```
“‚â€€ spreading chestnutíÍ““Iïê€î€ƒ€îïê€á.““€Çº¤€»,€ƒ€Îº¤€¦“).ªĆ»‘‡î€ˆ PEACE.
FREEDOM€ˆÃÒRY.
IGNORANCE€ˆ STRENGTH‘)'.«Ω

```

Try it online!
> 0 votes

# Answer
# Python 3, 222 bytes

```
a,b,c,d,e,f='Under the spreading chestnut tree',' you ',' lie ','and','sold',' IS '
print({f'{a}\nI {e}{b}{d}{b}{e} me.\nThere{c}they, {d} here{c}we\n{a}.',f'WAR{f}PEACE.\nFREEDOM{f}SLAVERY.\nIGNORANCE{f}STRENGTH.'}.pop())

```

Try it online!
> 0 votes

---
Tags: code-golf, string, kolmogorov-complexity, restricted-source, random
---