title: Tips for golfing in Factor

text:
# Question
Title: Tips for golfing in Factor
What general tips do you have for golfing in Factor? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to Factor (e.g. "remove comments" is not an answer).

# Answer
> 14 votes
# math.unicode

this thing is a golfing jewel. http://docs.factorcode.org/content/vocab-math.unicode.html

Here, I should let it speak for itself.

```
Word    Stack effect    Equivalent   (Byte  Char) Savings (best case)
¬       ( obj -- ? )    not           1     2
²       ( m -- n )      2 ^ , 2^      1     2
³       ( m -- n )      3 ^           1     2
¹       ( m -- n )      1 ^           1     2
¼       ( -- value )    1/4 , 1 4 /   1     2
½       ( -- value )    1/2           1     2
¾       ( -- value )    3/4           1     2
×       ( x y -- z )    *             -1    0
÷       ( x y -- z )    /             -1    0
Π       ( seq -- n )    product       5     6
Σ       ( seq -- n )    sum           1     2
π       ( -- pi )       pi            0     0
φ       ( -- n )        phi           1     2
‰       ( m -- n )      1000 /        4     5
‱       ( m -- n )      10000 /       5     6
ⁿ       ( x y -- z )    ^             -1    0
⅓       ( -- value )    1/3           1     2
⅔       ( -- value )    2/3           1     2
⅕       ( -- value )    1/5           1     2
⅖       ( -- value )    2/5           1     2
⅗       ( -- value )    3/5           1     2
⅘       ( -- value )    4/5           1     2
⅙       ( -- value )    1/6           1     2
⅚       ( -- value )    5/6           1     2
⅛       ( -- value )    1/8           1     2
⅜       ( -- value )    3/8           1     2
⅝       ( -- value )    5/8           1     2
⅞       ( -- value )    7/8           1     2

```

Those are the simple constants. Now for the functions:

```
Word    Stack effect        Equivalent  (Byte  Char) Savings (best case)
∀       ( seq quot -- ? )   all?         1    3
∃       ( seq quot -- ? )   any?         1    3
∄       ( seq quot -- ? )   none?        2    4
∈       ( elt seq -- ? )    member?      4    6
∉       ( elt seq -- y )    ∈ ¬          3    2
∋       ( seq elt -- ? )    swap member? 9    11
∌       ( seq elt -- y )    ∋ ¬          3    2
−       ( x y -- z )        -            -1   0
∕       ( x y -- z )        /            -1   0
∖       ( s1 s2 -- set )    diff         1    3
√       ( x -- y )          sqrt         1    3
∛       ( x -- y )          ⅓ ^          2    2
∜       ( x -- y )          ¼ ^          2    2
∞       ( -- value )        1/0.         1    3
∧       ( o1 o2 -- ? )      and          0    2
∨       ( o1 o2 -- ? )      or           -1   1
∩       ( s1 s2 -- set )    intersect    6    8
∪       ( s1 s2 -- set )    union        2    4
≠       ( o1 o2 -- ? )      = ¬          1    2
≤       ( x y -- ? )        <=           -1   1
≥       ( x y -- ? )        >=           -1   1
⊂       ( s1 s2 -- ? )      subset?      4    6
⊃       ( s1 s2 -- ? )      superset?    6    8
⊄       ( s1 s2 -- ? )      ⊂ ¬          3    2
⊅       ( s1 s2 -- ? )      ⊃ ¬          3    2
⊼       ( o1 o2 -- ? )      ∧ ¬          3    2
⊽       ( o1 o2 -- ? )      or ¬         2    3
⌈       ( x -- y )          floor        2    4
⌊       ( x -- y )          ceiling      4    6

```

Yes, I did make that table by hand, and yes, I did the math in my head, so there might be some, er, wrong numbers. I'll go write a program to do it for me, now :P

# Answer
> 10 votes
## Treasure trove vocabularies

During my time golfing with Factor, these are the non- auto-use vocabularies that have been the most indispensable to me.

* grouping.extras \- Group sequences in various ways.
* math.unicode \- Shorter names for math functions, set operations, and useful combinators.
* math.combinatorics \- Any time you need to get all the combinations or permutations of something, this is your vocab. Comes with tons of great combinators like `filter-permutations` for even more brevity. `nCk` and `inverse-permutation` come in handy sometimes too.
* math.primes \- Useful for prime number questions.
* math.primes.factors \- Get the divisors and prime factors of a number.
* math.matrices \- Matrix arithmetic, combinators and other operations.
* lists.lazy \- Working with infinite lists is sometimes terser than the alternative.
* sequences.merged \- ~~Mostly for `2merge`, which interleaves two sequences.~~ Use `vmerge` in `math.vectors` instead, since it's an auto-use vocabulary.
* math.text.utils \- ~~Shortest way to get a sequence of digits from a number.~~ This is no longer true since `>dec` was added to the language. Now `>dec 48 v-n` is the shortest way.
* math.extras \- Lots of specialized math words. You may not need them often, but when the task calls for it, there might be a built-in for it in here.
* spelling \- For the `ALPHABET` word, which is the shortest way to get the alphabet on the stack.
* english \- Words for natural language processing.
* qw \- Shorten literal sequences of strings.
* pair-rocket \- Shorten literal pairs and by extension literal assocs.
* project-euler.common \- Words commonly needed to solve Project Euler problems. Don't sleep on the individual problem vocabularies either! I've recently used project-euler.014 and project-euler.026 for the `collatz` and `period-length` words.

#### Some useful auto-use vocabularies you may have overlooked

* math.vectors \- A gem of a vocabulary. This lets you do arithmetic with a number and a sequence or two sequences. Plenty of other good stuff in here too. If you find yourself reaching for `2map`, look in here first.
* math.statistics \- Statistics comes up a lot in golf. `histogram`, `cum-sum`, `differences`, `mean`, and `std` are some of my most oft-used words. There's plenty of other great stuff in there too.
* combinators \- Mostly for `to-fixed-point`, which applies a quotation to something until it stops changing. Avoid `case` and `cond`, as they are far too verbose.
* combinators.random \- Conditional words based on probability instead of booleans. Extremely useful when called for.
* generalizations \- Allows you to shuffle the stack in a general way. `dupn` and `repeat` have been especially helpful in golf.
* sequences.generalizations \- Words that can apply to any number of sequences. `narray` is also very useful for golf at times.
* sequences.extras \- Words here can shorten your code compared to composing `sequence` words.
* sequences.deep \- Traverse and flatten nested sequences.
* assocs.extras \- Excellent words for working with assocs.
* interpolate \- This can sometimes be shorter than `formatting` words like `printf`.

#### And for those just getting started

* kernel \- Stack shuffling, loops, conditionals, data flow combinators, and other critical functionality. This is the core of the language. Start here.
* math \- Arithmetic.
* sequences \- Collections. Factor takes the approach of having different implementations all fall under the same `sequence` type, hence the words in this vocabulary will work on most types of collections.
* formatting \- String interpolation.
* assocs \- Associative arrays (dictionaries).

With just these five vocabs, you'll get a starting point similar to what most other languages give you.

# Answer
> 6 votes
Factor is impossible to golf. If you're set on winning, don't use it.

---

I don't just mean it's verbose, like Java or C# or Scala. I mean, because of its functional style, there's a small number of ways to write a given program, and `words are long` and `whitespace is not your friend`, so it's a bad target, worse than LISP.

Factor's power is in its object model, which is highly verbose. I golf in it because I think it's a cool language, and I enjoy learning it.

---

The `::` and `M::` words replace the normal compile word `:`, so that a function has access to lexical variables.

The docs on lexical vars.

Why use these over `:`? Because often, referring to variables by name will be shorter than stack-shuffling with `dup swap rot drop over nip etc`.

# Answer
> 6 votes
## You are free to trash stdout and stack under the top...

... as long as your submission is a function and the result is returned on the top of the stack.

### Simple example

`.` is shorter than `drop`, and `. .` is shorter than `2drop`. (Almost) any object that you will encounter while golfing is printable via `.`, and it has the effect of removing the top item of the stack.

### A real-golfing example

(a solution for Is this number a factorial?, found by golfing user's answer)

```
[ 1 0 [ 1 + 3dup * 3dup > ] loop . = ]

```

Try it online!

This is an extreme use of `3dup`s. It stuffs up a lot of stack items every time it is called, but it is valid (because the desired result is at the top of the stack) and correct (because it keeps the loop invariant for top three items).

Loop invariant:

```
( x prod idx )
1 +
( x prod idx+1 )
3dup *
( x prod idx+1 x prod' )  ! prod' = prod * (idx + 1)
3dup >
( x prod idx+1 x prod' idx+1 x>prod' )

```

Since `loop` consumes the boolean at the top on each iteration, the top three items at the start of the next iteration are `( x prod' idx+1 )`.

# Answer
> 5 votes
When converting between numbers and strings, the

```
string>number
number>string

```

words can be shortened to:

```
dec>
>dec

```

respectively (thanks, chunes, again!).

There are also:

* `bin>` and `>bin` for binary
* `oct>` and `>oct` for octal
* `hex>` and `>hex` for hexadecimal

that are all shorter than `n base>`, if they happen to suit your needs!

And if you need integers, use `1 /i` instead of `>integer`:

```
5 3 /i
5 3 / >integer   = .
=> t
5.77 1 /i
5.77 >integer    = .
=> t

```

---

EDIT:

If it's about printing, keep an eye on these too:

```
.b ! prints a number in binary
.o ! prints a number in octal
.h ! prints a number in hexadecimal

```

# Answer
> 4 votes
## Inline whatever you can.

All words need ***correct*** stack effect declarations in order to compile.

```
: hello ( -- ) "Hello, World!" print ;

```

These are *long*, even if you use single-char identifiers.

```
: m ( a b c d -- e f ) dup [ asd? ] bi swap = ;

```

Unless you use something so often that the benefits outwiegh the costs, inlining is often shorter, and `: p ( a -- ) print ;` aliasing doesn't save bytes.

# Answer
> 4 votes
# string literals are special

I never realised this before, but `"strings"` are rather special to the parser.

```
"asd""abc"

```

is equivalent to:

```
"asd" "abc"

```

and

```
URL" a"split

```

is the same as

```
URL" a" split

```

This is perhaps the only time whitespace isn't necessary in Factor, and also works for `URL" "`, `DLL" "`, `P" "`, `SBUF" "` and the others handled by `parse-string`, as pointed out by @fedes. in the comments.

**Note well** that the opening quote-like marker *must* be preceded by whitespace.

The following are considered one word:

```
filter"asdasd"map
filter"asdasd"

```

And you will get a `No word <blah> found in current vocabulary search path` error.

# Answer
> 4 votes
# Get used to multiple ways to write things

Usually this means to write something using high-level combinators vs. low-level combinators and/or stack shuffle words. In some cases the former wins, in others the latter wins. Therefore, in order to push Factor golf to the limits, it is good to know both and pick the one that turns out shorter.

### (Re-)Using values in the stack

For reusing single value, shuffle words usually win (because Factor has a large variety of them):

```
( n -- np nq) [ p ] [ q ] bi
( n -- np nq) dup p swap q

( n -- np nq nr ) [ p ] [ q ] [ r ] tri
( n -- np nq nr ) dup p over q rot r

( n -- np nq nr ns ) { [ p ] [ q ] [ r ] [ s ] } cleave
( n -- np nq nr ns ) [ p ] [ q ] [ [ r ] [ s ] bi ] tri
( n -- np nq nr ns ) dup p over q pick r roll s

```

But the situation is somewhat different for two or more values, because spread and apply combinators can save a copy or shuffle:

```
( m n -- mp nq ) [ p ] [ q ] bi*
( m n -- mp nq ) [ p ] dip q
( m n -- mp nq ) q swap p swap

( m n -- mnp mnq ) [ p ] [ q ] 2bi
( m n -- mnp mnq ) [ p ] 2keep q
( m n -- mnp mnq ) 2dup p -rot q

```

I can't list all possible combinations here, and one or two shuffle words can be optimized out depending on context. The lesson here is to find out multiple expressions that do the same thing stack-effect-wise.

### Conditionals and loops

Factor has many ways to express some variation of if, while, and boolean logic. But it also has higher-level combinators to express various common patterns: `sequences` has `map`, `map-index`, `reduce`, `filter`, `partition` (I believe these are self-explanatory), `accumulate` (cumulative reduce), `replicate` (run n times and collect intermediate values), and `produce` (run until false and collect intermediate results). `combinators.to-fixed-point` runs until fixed point is reached. `math.times` repeats a lambda for the given number of times.

Check if some of these high-level combinators work for the task given. If so, try to use them. Otherwise, use the simplest construct: `?` or one-branch variations of `if` for a conditional, `loop` for an unbounded loop, `times` for simple repetition (not involving a sequence or range).

### Bonus: Minimize stack item duplications and reorders

When using shuffle words, every time a shuffle word is used, you get +4~6 bytes. Try to minimize their use by duplicating multiple items at once (`2dup`, `3dup`) and reordering inputs and intermediate states. Sometimes multiple library words do the same job but with different input order (e.g. `each` vs. `reduce`); exploit them when possible.

# Answer
> 3 votes
# `split` doesn't need a `string` sequence as an argument

Or, more accurately / generally:

# Factor strings are really just sequences of character values

Meaning string operations work on sequences of chars too

... which is important because, for instance, `" " split` will split a char-array on the number 32.

More directly, this:

```
>string " " split

```

is exactly equivalent to

```
" " split

```

While being 8 chars longer.

# Answer
> 3 votes
# quotations are lambdas, abuse them

Most challenges can be solved with one word definition because of Factor's functional, applicative nature.

I just had the sudden realisation that `[ quoting ]` code is the equivalent of a lambda definition in other languages.

I don't know why I didn't think of this before...

A normal word definition:

```
: f ( a c -- b ) asd asd ;

```

Lamba'd:

```
[ asd asd ]

```

You can do everything inside a `[ quotation ]` that you can inside a `:` word.

# Answer
> 3 votes
The `infix` vocabulary is pretty cool.

It allows for infix notation math, which sounds lame since Factor's RPN, but:

```
IN: scratchpad USE: infix
IN: scratchpad [infix 5-40/10*2 infix] .
-3

```

For longer expressions it's much shorter than RPN because of whitespace, but you'll need to overcome the `[infix` syntax's length.

It also allows Python-style slicing:

> ```
> USING: arrays locals infix ;
> [let "foobar" :> s [infix s[0:3] infix] ] .
> "foo"
>
> ```
>
> Additionally, you can step through sequences with seq\[from:to:step\] notation.
>
> ```
> USING: arrays locals infix ;
> [let "reverse" :> s [infix s[::-1] infix] ] .
> "esrever"
>
> USING: arrays locals infix ;
> [let "0123456789" :> s [infix s[::2] infix] ] .
> "02468"
>
> ```

# Answer
> 3 votes
# Take advantage of auto-use

Some people were already implicitly using this to discount imports. Now it is official (unless the consensus changes). No more `USING: kernel math math.functions sequences ;` -- you can exclude most commonly used library imports from byte count.

Caveats:

* Actually check that the code does work with auto-use enabled. It can't load obscure libraries (e.g. `xxx.private`), and it cannot load if the word is found in multiple libraries.
* If you don't have Factor installed on your machine, you can still check by entering your submission in the code section on this TIO. (Make sure the entire code has no stack effect, i.e. `( -- )`.) If it runs without error, your submission is valid.

# Answer
> 3 votes
## Use linked lists when appropriate

Using linked lists is shorter than using arrays when the code involves a lot of dissection at the start (and you don't need sophisticated sequence operations):

```
first (5)              > car (3)
rest (4)               > cdr (3)
second (6) > 1 nth (5) > cadr (4)
prefix (6)             > cons (4)
swap prefix (11)       > swons (5)
unclip (6)             = uncons (6)
unclip swap (11)       > unswons (7)

```

Note that you don't need `USE: lists` because it is `auto-use`d by default.

If you see a good Haskell answer which uses pattern matching on a list, there is a good chance that a linked-list based solution is shorter in Factor too.

# Answer
> 3 votes
## Use fried quotations to build sequence literals

Occasionally, you may need to build sequences with a mix of arguments and constants. It's shorter to do this

`'[ 1 _ 1 ]`

than this:

`1 1 swapd 3array`.

`quotation` is an instance of `immutable-sequence`. All sequence words work on them as long as they do not mutate. For instance, you can do the following, no problem:

`4 '[ 1 _ 1 ] { 3 4 5 } v+`

Keep in mind many words use the type of the first argument (as is the case with `v+`) as an exemplar for what type the result should be. This is usually unimportant but may occasionally be useful to know.

Here is a real-world example of when this was useful in a golf: https://codegolf.stackexchange.com/a/226034/97916

# Answer
> 2 votes
# Dip \> Swap... so make a call

Idiomatic code uses quotations and `dip`, but short code uses `swap`. Look, you can have an extra swap per two `dip`s.

```
[ dip ] [ dip ] [ dip ] [ dip ] [ dip ]
swap swap swap swap swap swap swap swap

```

However, sometimes trading `swap` for `dip` makes the code longer in other places, so it's a bit of a re**Factor**ing job.

# Answer
> 2 votes
# find all the higher-order functions and use them, often

Factor is *full* of higher-order functions that take `[ quotations ]` or `other-words` and work on sequences / other data.

For example, to take an IP address as a string and sum its fields, you could do:

```
"." split [ 10 >base ] [ + ] map-reduce 10 base>
"." split [ 10 >base ] map 0 + reduce 10 base>
"." split [ 10 >base ] map sum 10 base>

```

Notice that fancy `map-reduce` is actually longest here because of `[ quotation ]` syntax, but there's already a `sum` word for that anyways, which is far shorter.

Here's a place `map-reduce` is shorter:

```
[ "." split [ 10 base> ] [ [ 256 * ] dip + ] map-reduce ] bi@ - abs 1 + ]
[ "." split [ 10 base> ] map 0 [ [ 256 * ] dip + ] reduce ] bi@ - abs 1 + ]

```

Can't use `sum` there.

# Answer
> 2 votes
The following are equivalent

```
[ 1 2 3 ] [ 1 + ] map V{ } clone-like
[ 1 2 3 ] [ 1 + ] V{ } map-as

```

It's just `map-as` and the other `-as` words (`zip-as`, `map-as`, `accumulate-as`, etc) are usually shorter than an `obj clone-like` if you're going to use them anyways.

# Answer
> 1 votes
The following are equivalent:

```
1 '[ _ blah ]
1 [ blah ] curry

```

It's just that the top one is shorter by three bytes.

---
Tags: code-golf, tips
---


# Question
Title: Parentheses sequences in lexicographical order
Challenge Taken from here and also here

An **n** parentheses sequence consists of **n** `(`s and **n** `)`s.

A valid parentheses sequence is defined as the following:

> You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
>
> For example, `(())` is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes `()`, then you can make it empty. `)()(` is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes `)(` and you cannot erase any more

**Task**

Given a number **n** you need to generate all correct parenthesis sequence in lexicographical order

Output can be an array, list or string (in this case a sequence per line)

You can use a different pair of parenthesis such as `{}`, `[]`, `()` or any open-close sign

**Example**

* n = 3

```
((()))
(()())
(())()
()(())
()()()

```
* n = 2

```
(())
()()

```

# Answer
# Perl 6, 36 bytes

```
{grep {try !.EVAL},[X~] <[ ]>xx$_*2}

```

Try it online!

Finds all lexographically sorted combinations of \\$2n\\$ `[]`s and filters the ones that `EVAL` correctly. Note that all valid combinations (even stuff like `[][]`) evaluate to `[]` (which is falsey, but we `not` it (`!`) to distinguish from `try` returning `Nil`)

### Explanation:

```
{                                  }  # Anonymous code block
                        <[ ]>         # Create a list of ("[", "]")
                             xx$_*2   # Duplicate this 2n times
                   [X~]               # Find all possible combinations
 grep {          },                   # Filter from these
            .EVAL                     # The EVAL'd strings
       try !                          # That do not throw an error

```
> 9 votes

# Answer
# , ~~112~~ ~~107~~ 99 bytes

Non-recursive approach. We use "\<" and "\>" because it avoids escape characters in the regex. To allow us to use a shorter specification for an ASCII range, we generate 3^2n 2n-character strings of "\<", "=" and "\>" using `expand.grid` (via their ASCII codes 60, 61 and 62) and then grep to see which combinations give balanced open and close brackets. The "=" possibilities will get ignored, of course.

Via http://rachbelaid.com/recursive-regular-experession/

```
function(n)sort(grep("^(<(?1)*>)(?1)*$",apply(expand.grid(rep(list(60:62),2*n)),1,intToUtf8),,T,T))

```

Try it online!

## Explanation

```
"^(<(?1)*>)(?1)*$" = regex for balanced <> with no other characters
^ # match a start of the string
  ( # start of expression 1
    < # open <>
       (?1)* # optional repeat of any number of expression 1 (recursive)
  # allows match for parentheses like (()()())(()) where ?1 is (\\((?1)*\\))
    > # close <>
  ) # end of expression 1
  (?1)* # optional repeat of any number of expression 1
$ # end of string

function(n)
  sort(
    grep("^(<(?1)*>)(?1)*$", # search for regular expression matching open and close brackets
      apply(
        expand.grid(rep(list(60:62),2*n)) # generate 3^(2n) 60,61,62 combinations
      ,1,intToUtf8) # turn into all 3^(2n) combinations of "<","=",">"
    ,,T,T) # return the values that match the regex, so "=" gets ignored
  ) # sort them

```

# , 107 bytes

Usual recursive approach.

-1 thanks @Giuseppe

```
f=function(n,x=0:1)`if`(n,sort(unique(unlist(Map(f,n-1,lapply(seq(x),append,x=x,v=0:1))))),intToUtf8(x+40))

```

Try it online!
> 6 votes

# Answer
# K (ngn/k), ~~36 35~~ 37 bytes

```
{"()"(|/'0>+\'1-2*)_(x=+/')#+!2|&2*x}

```

Try it online!

`+!2|&2*x` all binary vectors of length 2\*n

`(x=+/')#` only those that sum to n

`(|/0>+\'1-2*)_` only those whose partial sums, treating 0/1 as 1/-1, are nowhere negative

`"()"` use 0/1 as indices in this string
> 5 votes

# Answer
# Python 2, ~~91~~ ~~88~~ ~~84~~ 81 bytes

```
f=lambda n:n and sorted({a[:i]+'()'+a[i:]for a in f(n-1)for i in range(n)})or['']

```

Try it online!

-3 bytes thanks to pizzapants184
> 4 votes

# Answer
# 05AB1E, 13 bytes

```
„()©s·ãʒ®õ:õQ

```

Try it online or verify some more test cases.

**Explanation:**

```
„()            # Push string "()"
   ©           # Store it in the register without popping
    s·         # Swap to get the (implicit) input, and double it
      ã        # Cartesian product that many times
       ʒ       # Filter it by:
        ®      #  Push the "()" from the register
         õ:    #  Infinite replacement with an empty string
           õQ  #  And only keep those which are empty after the infinite replacement

```
> 4 votes

# Answer
# C (gcc), 114 bytes

```
f(n,x,s,a,i){char b[99]={};n*=2;for(x=1<<n;x--;s|a<0||puts(b))for(s=a=i=0;i<n;)a|=s+=2*(b[n-i]=41-(x>>i++&1))-81;}

```

Try it online!

Should work for n \<= 15.

### Explanation

```
f(n,x,s,a,i){
  char b[99]={};   // Output buffer initialized with zeros.
  n*=2;            // Double n.
  for(x=1<<n;x--;  // Loop from x=2**n-1 to 0, x is a bit field
                   // where 1 represents '(' and 0 represents ')'.
                   // This guarantees lexicographical order.
      s|a<0||puts(b))  // Print buffer if s==0 (as many opening as
                       // closing parens) and a>=0 (number of open
                       // parens never drops below zero).
    for(s=a=i=0;i<n;)  // Loop from i=0 to n-1, note that we're
                       // traversing the bit field right-to-left.
      a|=              // a is the or-sum of all intermediate sums,
                       // it becomes negative whenever an intermediate
                       // sum is negative.
        s+=            // s is the number of closing parens minus the
                       // number of opening parens.
                        x>>i++&1   // Isolate current bit and inc i.
                    41-(        )  // ASCII code of paren, a one bit
                                   // yields 40 '(', a zero bit 41 ')'.
             b[n-i]=               // Store ASCII code in buffer.
          2*(                    )-81;  // 1 for ')' and -1 for '(' since
                                        // we're going right-to-left.
}

```
> 4 votes

# Answer
# Japt, ~~15~~ 13 bytes

```
ç>i<)á Ôke/<>

```

Try it

---

## Explanation

```
ç                 :Input times repeat the following string
 >i<              :  ">" prepended with "<"
    )             :End repeat
     á            :Get unique permutations
       Ô          :Reverse
        k         :Remove any that return true (non-empty string)
         e/<>     :  Recursively replace Regex /<>/

```
> 3 votes

# Answer
# Ruby, 70 bytes

```
f=->n{n<1?['']:(0...n).flat_map{|w|f[n-1].map{|x|x.insert w,'()'}}|[]}

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES6), ~~112~~ 102 bytes

This is heavily based on nwellnhof's C answer.

```
f=(n,i)=>i>>2*n?'':(g=(o,k)=>o[2*n]?s|m<0?'':o:g('()'[m|=s+=k&1||-1,k&1]+o,k/2))(`
`,i,m=s=0)+f(n,-~i)

```

Try it online!
> 2 votes

# Answer
# Perl 6, 42 bytes

```
{grep {!S:g/\(<~~>*\)//},[X~] <( )>xx$_*2}

```

Try it online!

Uses a recursive regex. Alternative substitution: `S/[\(<~~>\)]*//`

**38 bytes** with 0 and 1 as open/close symbols:

```
{grep {!S:g/0<~~>*1//},[X~] ^2 xx$_*2}

```

Try it online!

### Explanation

```
{                                        }  # Anonymous block
                              <( )>         # List "(", ")"
                                   xx$_*2   # repeated 2n times
                         [X~]  # Cartesian product with string concat
                               # yields all strings of length 2n
                               # consisting of ( and )
 grep {                },  # Filter strings
        S:g/             # Globally replace regex match
            \(           #   literal (
              <~~>       #   whole regex matched recursively
                  *      #   zero or more times
                   \)    #   literal )
                     //  # with empty string
       !                 # Is empty string?

```
> 2 votes

# Answer
# Red, 214, 184 136 bytes

```
func[n][g: func[b n][either n = length? b[if not error? try[load b][print b]return 0][g append copy b"["n g append copy b"]"n]]g""2 * n]

```

Try it online!

Uses Jo King's approach. Finds all possilble arrangements of brackes using recursion (they are generated in lexicographic order) and print it if the arrangement evaluates as a valid block.
> 2 votes

# Answer
# Perl 5 `-n`, ~~41~~ 39 bytes

*-2 bytes with angle brackets*

```
s/<(?R)*>//gr||say for glob'{<,>}'x2x$_

```

Try it online!

Port of my Perl 6 answer.
> 2 votes

# Answer
# Retina 0.8.2, 50 bytes

```
.+
$*
1
11
+%1`1
<$'¶$`>
Gm`^(?<-1>(<)*>)*$(?(1).)

```

Try it online! Uses `<>`s. Explanation:

```
.+
$*

```

Convert to unary.

```
1
11

```

Double the result.

```
+%1`1
<$'¶$`>

```

Enumerate all of the 2²ⁿ 2n-bit binary numbers, mapping the digits to `<>`.

```
Gm`^(?<-1>(<)*>)*$(?(1).)

```

Keep only balanced sequences. This uses a balanced parentheses trick discovered by @MartinEnder.
> 2 votes

# Answer
# Jelly,  ~~15~~  14 bytes

-1 thanks to ChartZBelatedly! (Use a better fixed-point built-in.)

```
ḤØ(ṗœṣØ(F$ÐLÐḟ

```

A monadic Link accepting \\$n\\$ that yields a list of lists of characters.

**Try it online!** (footer formats the list as lines.)

### How?

```
ḤØ(ṗœṣØ(F$ÐLÐḟ - Link: integer, n
 Ø(            - literal ['(', ')']
Ḥ              - double (n)
   ṗ           - Cartesian power -> all length 2n lists of '(' and/or ')' (already sorted)
            Ðḟ - filter discard if:
          ÐL   -   repeat until a fixed point is reached applying:
         $     -     last two links as a monad, f(current, initially proposed):
    œṣ         -       split at:
      Ø(       -         literal ['(', ')']
        F      -       flatten
                   } -> empty list if balanced (only empty lists are falsey)

```
> 2 votes

# Answer
# Haskell, 80 bytes

```
f n=[x|x<-mapM("()"<$f)[1..2*n],0:y<-[scanr(\b->(sum[2|b>'(']-1+))0x],all(>=0)y]

```

Try it online!
> 2 votes

# Answer
# Jelly, 19 bytes

```
Ø+xŒ!QÄAƑ>ṪƊ$Ƈ=1ịØ(

```

Try it online!

Output clarified over TIO.
> 1 votes

# Answer
# JavaScript (Node.js), 84 bytes

```
f=(n,s='')=>n?f(n-=.5,s+'[')+f(n,s+']'):[...s].some(t=>(n+=t<']'?1:-1)<0)|n?'':s+`
`

```

Try it online!

# JavaScript (Node.js), 90 bytes

```
f=(n,s='')=>n?f(n-=.5,s+'[')+f(n,s+']'):eval("try{eval(s.split``+``),s+`\n`}catch(_){''}")

```

Try it online!

Is it an array?
> 1 votes

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


title: Solve nonimplication-SAT

text:
# Question
Title: Solve nonimplication-SAT
## Background

This is Post's lattice:

Credit: EmilJ

It denotes the lattice of all clones on a two-element set `{0, 1}`, ordered by inclusion (from Wikipedia). That can be a bit of a mouthful so lets look at a concrete example. `MP` (located near the top) is a set that contains all boolean circuits that can be made with `and` and `or`. `DM` (a bit lower) is the set of all boolean circuits that can be made with the majority gate. The majority gate (`maj`) takes three inputs and returns true iff at least two of the inputs are true. This is a hasse diagram ordered by inclusion, which means that since `DM` is below `M` and you can reach it by a sequence of nodes at decreasing heights, `DM` is a (strict) subset of `M`. This means that every circuit that can be made with `maj` can be replicated using  and .

I've colored the nodes according to the computational complexity of the boolean satisfiability problem restricted to that set of circuits. Green means `O(1)`. This means that either the set is always satisfiable or it contains a finite amount of elements. Yellow is linear time. Red is NP-complete.

As you can see, \\$T\_0^\infty\\$ is the smallest NP-complete set. It is generated by  which is the negation of implication. In other words, it is the set of all formulas consisting of  and brackets.

## Task

Your task is to solve a instance of nonimplication-SAT. That is, you are given a boolean formula consisting of variables and the operator  which has the following truth table:

```
a b a↛b
0 0  0
0 1  0
1 0  1
1 1  0

```

Your program has to decide whether there is an assignment to the variables which satisfies the formula. That is, the value of the formula is `1`.

## Test cases

```
a↛a: UNSAT
a↛b: SAT
(a↛b)↛b: SAT
((a↛(c↛a))↛(b↛(a↛b)))↛(a↛(b↛c)): UNSAT

```

## Rules

This is a decision problem so you should have two distinct output values for SAT and UNSAT. Use a reasonable input format. For example:

```
"(a↛(b↛c))↛(b↛a)"
[[0,[1,2]],[1,0]]
"↛↛a↛bc↛ba"

```

Make sure that the format you choose can handle an unlimited amount of variables. For strings just the letters a to z are not enough as there is only a finite amount of them.

Bonus points if your code runs in polynomial time :p

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

```
SatisfiableQ[#/.$->(#&&!#2&)]&

```

Try it online!

Takes input in the form `$[$[a, $[b, c]], $[b, a]]`.

# Answer
> 4 votes
# Charcoal, 57 bytes

```
Ｗ⁻⪪⁻⁻θ(¦)¦>υ⊞υ⌊ι⊙…⁰Ｘ²ＬυＵＶ⪫⟦(lambda ⪫λ=0,¦=0:θ)(⪫⮌↨ι²,¦)⟧ω

```

Try it online! Link is to verbose version of code. Accepts any valid Python identifier as a variable name and represents the nonimplication operator with the `>` character. Outputs a Charcoal boolean, i.e. `-` for satisfiable, nothing if not. Explanation:

```
Ｗ⁻⪪⁻⁻θ(¦)¦>υ⊞υ⌊ι

```

Extract all of the unique variable names from the input.

```
⊙…⁰Ｘ²ＬυＵＶ⪫⟦(lambda ⪫λ=0,¦=0:θ)(⪫⮌↨ι²,¦)⟧ω

```

Compute all possible variable substitutions and evaluate the string as python code with those assignments until one evaluates as `True`, at which point output a `-`.

# Answer
> 1 votes
# Python3, 397 bytes:

```
l=len
b=[{'a':0,'b':0,1:0},{'a':0,'b':1,1:0},{'a':1,'b':0,1:1},{'a':1,'b':1,1:0}]
def g(r):
 if len(r)!=len(b[0])-1:return 0
 if all(str==type(i)for i in r):return all(i in b[0]for i in r)
 return any(all(x==y for x,y in zip(r,[*i.values()][:-1])if type(x)==type(y))for i in b)
def f(d):
 if l(d)!=l(b[0])-1:return 0
 if all(j:=[i if isinstance(i,str)else f(i)for i in d]):
  return g(j)
 return 0

```

Try it online!

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


title: Tips for golfing in Charcoal

text:
# Question
Title: Tips for golfing in Charcoal
Charcoal is a language created by ASCII-only and DLosc that specialises in ASCII art challenges.

What tips do you have for golfing in Charcoal? Obviously I am looking for tips related specifically to Charcoal, not those which can be applied to most - if not all - languages.

# Answer
> 6 votes
# Take advantage of the deverbosifier

Using the deverbosifier means you can write in ASCII (`--dv` or `--deverbosify` to deverbosify, `-v` or `--verbose` to execute as verbose code). Furthermore, it compresses strings for you, which can be useful in some ASCII-art challenges when the string to compress is too long.

@Neil recommends using `-vl` or `-v --sl`. This is short for `--verbose --showlength`, meaning it will be interpreted as verbose Charcoal, and the length of the normal Charcoal code will be shown. Also, when deverbosifying, check the output to make sure that the input has actually been parsed correctly, since Charcoal generally ignores parse errors. If there *is* a syntax error, use `-a` (`--astify`) or `--oa` (`--onlyastify`) to help figure out the problem.

# Answer
> 4 votes
# Learn your reflections and rotations

There are a lot of variations of the basic reflection and rotation, so it pays to know what the subtle differences are. Key to tables:

* Command: Name of the command in Verbose mode.
* Transform: Whether Charcoal should attempt to flip or rotate the characters as it mirrors or rotates them. For instance, a `/` might become `\` after a rotate or flip.
* Keep Original: Whether Charcoal should merge the result with the original canvas.
* Overlap: (Only applies when Keep Original is Yes.) Determines the position of the axis of reflection/rotation, in half characters from the border. In the case of reflections, equivalent to the number of rows/columns that are not affected and end up in the middle of the result. In the case of rotations, the rotated copy is allowed to overwrite clear areas (but not spaces) in the original.

## Reflections

```
|         Command         | Transform | Keep Original | Overlap |
|-------------------------|-----------|---------------|---------|
| Reflect                 | No        | No            | n/a     |
| ReflectCopy             | No        | Yes           | 0       |
| ReflectOverlap          | No        | Yes           | 1       |
| ReflectOverlapOverlap   | No        | Yes           | n       |
| ReflectTransform        | Yes       | No            | n/a     |
| ReflectMirror           | Yes       | Yes           | 0       |
| ReflectButterfly        | Yes       | Yes           | 1       |
| ReflectButterflyOverlap | Yes       | Yes           | n       |

```

The direction of reflection is optional. The default is to reflect once to the right. For those reflections that keep the original, a multiple direction is allowed, which simply repeats the command for each direction. (This means that for instance `ReflectMirror(:¬)` will actually create four copies in total.)

The cursor is moved along with the reflection (even when the original is kept).

## Rotations

```
|         Command         | Transform | Keep Original | Overlap |
|-------------------------|-----------|---------------|---------|
| Rotate                  | No        | No            | n/a     |
| RotateCopy              | No        | Yes           | 0       |
| RotateOverlap           | No        | Yes           | 1       |
| RotateOverlapOverlap    | No        | Yes           | n       |
| RotateTransform         | Yes       | No            | n/a     |
| RotatePrism             | Yes       | Yes           | 0       |
| RotateShutter           | Yes       | Yes           | 1       |
| RotateShutterOverlap    | Yes       | Yes           | n       |

```

For those rotations that keep the original, there is an optional origin of rotation. The default is the bottom right of the canvas. Allowable values are any of diagonal directions.

The amount of rotation (in 45° increments) is optional. The default is 2, i.e. 90° anticlockwise (counterclockwise). For those rotations that keep the original, there are two alternative options: a multidigit integer specifies to rotate the canvas once for each digit and then merge the results, while an integer list simply repeats the command for each rotation, with variable results depending on how the canvas changes in between.

# Answer
> 3 votes
# Use overloads

For example, many commands only need one argument:

* `Rectangle`, `Oblong` and `Box` make a square if only one argument is given
* `Reflect` commands default to reflecting right
* `Rotate` commands default to 90 degrees counterclockwise
* `Polygon` and `PolygonHollow` can accept a multidirectional and a side length. This can be used if all of the sides are the same length.

# Answer
> 3 votes
# Use the predefined variables

Here is a list of all the variables that can be used, giving the succinct greek letter and the verbose letter that represents it.

```
α/a: The uppercase alphabet
β/b: The lowercase alphabet
γ/g: A string of all the ASCII characters from space to ~
δ/d: The fifth input
ε/e: The fourth input
ζ/z: The third input
η/h: The second input
θ/q: The first input
υ/u: An empty array
φ/f: 1000
χ/c: 10
ψ/y: The null character
ω/w: The empty string

```

The variables representing inputs will be empty if not enough input exists, but all other variables not shown here must be assigned before use.

# Answer
> 3 votes
# Avoid consecutive constants of the same type

For example, `Plus(Times(i, 2), 1)` translates as `⁺×ι²¦¹`, but you can save a byte by switching the parameters: `Plus(1, Times(i, 2))` translates as `⁺¹×ι²` and `Plus(Times(2, i), 1)` as `⁺×²ι¹` both of which save a byte. `Plus(1, Times(2, i))` (which translates as `⁺¹×²ι`) would be even better if there was another numeric constant following it.

# Answer
> 2 votes
# Use multidirectionals

Some commands can accept multidirectionals: `+X*|-\/<>^KLTVY7¬⌊⌈`. What they expand to are here. In general, the direction list starts from up and continues clockwise.

# Answer
> 2 votes
# Use commands without a command character

An expression that is not part of a command is printed.
If it is preceded by a direction, the expression is printed in the specified direction.
Numbers are printed as a line with the specified length using a character selected from `\/-|`.

If a direction is not followed by an expression, it is counted as a move one space in the specified direction.

**Note:** This may sometimes be counted as part of the previous command so the command character may actually be required. (thanks Neil for reminding me)

# Answer
> 1 votes
## Make full use of `Sum`

`Sum` has lots of handy overloads:

* On a list of strings, concatenates them together. However, if it's possible that the list might be empty, this would give None, so in this case, use `Join(..., "")` instead.
* On a non-empty list of numbers, simply takes their sum.
* On a non-empty list of lists, concatenates them together (flattens to depth 1).
* On an integer, takes the sum of its digits. (Floating-point values are truncated to integer. If you want the sum of the decimal places, cast to string first.)
* On a string containing only digits and optionally one `.` character, takes the sum of the digits.
* On a string containing numbers and separators, takes the sum of the numbers cast to int or float (but note that `-` counts as a separator).

A convenient side-effect of the last two rules is that if you use `Sum` on a character then the digits `1-9` get cast to their value and everything else returns zero, unlike `Cast`, which fails for non-digit values.

# Answer
> 1 votes
## Use Filter to slice the first character from an array or string

Even if you're lucky, using `Slice` to slice the first character from a string takes 2 bytes: `Slice(..., 1)`. It will take longer if the expression to be sliced ends in a number, requiring a separator, or if the following code can be interpreted as an expression, as in that case `Slice` will want to consume it as an additional parameter.

Instead, just use `Filter(..., k)`, which drops the first element, thus achieving the desired result. (Obviously use the appropriate loop index variable if your expression is nested inside another loop.) This is always 2 bytes and cannot be affected by surrounding code.

# Answer
> 1 votes
## Use switch instead of if (Equals(...)) where possible

The construct

```
if (Equals(q, h)) ...
else ...

```

takes 4 bytes but written as a switch it only takes 3 bytes:

```
switch (q) {
case h: ...
default: ...
}

```

However this only works if the `else` portion can be unambiguously parsed as a command rather than an expression. In particular:

* If the `else` portion is empty, then this only works at the end of a block or program, but that was true for the original `if` statement.
* If the `else` portion contains multiple commands, then this works as an `if` but not as a `switch`.
* If the `else` portion prints an expression, then this only works as a `switch` at the end of a block or program.

# Answer
> 1 votes
## Some useful uses of `Base`

`Base(array, 1)` is like `Sum(array)` for a numeric array, but it returns `0` when the array is empty, while `Sum` returns `None`, which is usually inconvenient to process, unless you're using it in a Boolean context.

`Base(array, 0)` returns the last element of a numeric array (or `0` if the array is empty) without modifying the array.

`Base([x, y], Negate(1))` returns `y-x`. This is useful to compare the elements of a two-element array for equality (typically calculated from a `Map`).

`Base(array, number)` also works to substitute a number in a polynomial.

In all the above cases the two parameters can be exchanged if it is inconvenient to have the number second (i.e. if it would require two consecutive numbers to be separated).

# Answer
> 0 votes
# Use split for a string array, split and cast for a number array

Split for a string array is only three characters of overhead, and split and cast is only four characters of overhead. Compare this to writing the array literally, which would require array start and end, *and* a separator between every array element.

If your number array only has numbers less than 95, use either a cast (if all numbers are less than 10) or index into one of the predefined variables.

---
Tags: code-golf, tips
---


title: Busy beaver in a coin

text:
# Question
Title: Busy beaver in a coin
\\$BB\\$ is the busy beaver function, an uncomputable function. Write a program which when given an integer \\$n\\$ as input, will output \\$BB(n)\\$, with at least \\$\frac 2 3\\$ probability. You can do whatever (return something wrong, infinite loop, explode, etc.) in other cases.

To help you compute it, you're given a function that randomly returns 0 or 1 (false or true, etc.). You can decide the exact probability that it returns 0, but all returns of calls should be independent.

Shortest code wins.

# Notes

* The exact definition of BB doesn't matter much so not clearly defined above.
* If you encode some code into the randomness, they add nothing to length of your solution(actually it's hard to define code and data here). You should, when constructing the coin, show the code, though.

# Answer
> 2 votes
# Python 3.8 (pre-release), 68 66 bytes

```
lambda x:eval(sum(r()for _ in"X"*4**900).to_bytes(225,"big")[:99])

```

Try it online!

-2 bytes thanks to @l4m2

`r` is the random function. Its probability of outputting one encodes a 99-byte code snippet, which is evaluated. This code snippet can then read much more data from the randomness, and basically you can encode any program you want into the randomness stream.

Here is a practical demonstration

Example (less than) 99-byte snippet:

```
eval((sum(r()for _ in"X"*2**88001)>>80000).to_bytes(1000,"big")[99:])

```

As you can see, there is no limit to what kind of code we can run

To actually solve the busy beaver problem, the rest of the randomness is dedicated to just storing the answers to the question (that is, the busy beaver numbers).

The probability of failure depends on the first calculation. I *think* it succeeds with more than 2/3 probability, but i could be wrong. I'll check and add a proof later. Nevertheless, if it fails the criteria, this only results in some adjusting to the magic constants.

For the encoding of the busy beaver numbers, we first use the following encoding (I'm using a list of primes as an example)

`[2,3,5,7,...]`

Is converted into

`110111011111011111110...`

Finally, in order to account for the table-maker's dilemma, we replace`1` with `10` and `0` with `01`, resulting in `101001101010011010101010011010101010101001...`

Then we execute the following code:

```
def get_raw_bit(p):
 # A lot of tries
 tries = 2**(2**p)
 hits = sum(r() for _ in range(2**tries))
 hits >> (tries - p)
def get_bit(p):
 code_len = 1000
 get_bit(code_len + 2*p)
pos = 0
p = -1
while pos < x:
 count = 0
 while get_bit(p:=p + 1):
  count+= 1
print(count)

```

---
Tags: code-golf, random, open-ended-function, busy-beaver
---


title: Rotate a grid 90 degrees clockwise

text:
# Question
Title: Rotate a grid 90 degrees clockwise
The task is simple, given an integer `n` of how many lines the next `n` lines is and, a multi-line input, output the resulting 90 degree tilted grid in a clockwise formation.

E.g.

Input:

```
2
c d
o e

```

Output:

```
o c
e d

```

I/O format:

1. Input will have spaces in between them
2. Input always contains alphabetical characters except the first input `n`

This is code-golf, so shortest code wins!

Credit: https://www.codingame.com/contribute/view/727778c431888fc6c0d03c77037ad93c3fa4 by Tsloa

# Answer
# 05AB1E (legacy), 6 (or 7?) bytes

```
|€#øí»

```

Try it online.

It doesn't need the length as input, but if it's mandatory for whatever reason, you can add a `¦` after the `|` to simply remove it from the list of inputs:
Try it online.

Could be 2 bytes with standard I/O:
Try it online.

**Explanation (of the 7 bytes program):**

```
|        # Get all lines of input as a list
 ¦       # Remove the first item (the additional length)
  €#     # Split each line on spaces
    øí   # Rotate the matrix 90 degrees clockwise:
    ø    #  Zip/transpose; swapping rows/columns
     í   #  Reverse each inner row
      »  # Join each inner list by spaces, and then these strings by newlines
         # (after which the result is output implicitly)

```
> 0 votes

# Answer
# Japt `-R`, 7 bytes

`z` would work on its own if the spacing between characters and lines were consistent.

```
·m¸z m¸

```

Try it
> 2 votes

# Answer
# Charcoal, 8 bytes

```
ＦＮ↓⟦⟦⁻Ｓ `

```

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

```
ＦＮ

```

Input the number of lines and loop that many times:

```
↓⟦⟦⁻Ｓ `

```

Remove spaces from the next line of input, then output it vertically and move the cursor two spaces leftwards.
> 1 votes

# Answer
# Python3, 60 bytes

```
_,*R=map(str.split,open(0))
for r in zip(*R[::-1]):print(*r)

```

Try it online!
> 0 votes

# Answer
# Pari/GP, 89 bytes

```
[[print1(c,if(j--," ","\n"))|c<-r]|r<-Mat(Colrev([Vec(Str(input))|i<-[1..n=input]])),j=n]

```

Try it online!

# Pari/GP 2.13.0, 71 bytes

```
[print(strjoin(r," "))|r<-Mat(Colrev([Vec(Str(input))|i<-[1..input]]))]

```

The newest version of PARI/GP finally has a `strjoin` function. But no TIO.
> 0 votes

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


title: Build a nest

text:
# Question
Title: Build a nest
The challenge is simple: write a program or function that, when given a finite non-negative integer, outputs a nested array.

## The rules

* Your code must produce a **unique** valid nested array for *every* integer 0 ≤ n \< 231.
* **Every** possible nested array with up to 16 open brackets must be outputted within this range. (This does not mean that your code can never output a nested array with more than 16 open brackets.)
* Your code may output a string representation of the nested array instead of an actual array (with or without commas).

One possible mapping:

```
0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.

```

## Scoring

This is , so **the shortest code in bytes wins.**

# Answer
# Python, 153 128 bytes

```
s=l=0;r="";n=input()
for d in bin(n)[2:]*(n>0):c=d<"1";l=[l,s>1][c];r+="]"*c+(1-l*c)*"[";s+=1-c-l*c
print"["+r+"["*l+"]"*(s+l+1)

```

We map a number *n* to a nested list by looking at its binary digits left-to-right. This algorithm works for any number, not just under 232.

1. If the current binary digit is an 1, output `[`.
2. Otherwise, if the sequence of brackets we've output so far would get balanced by a single closing bracket, output `][`.
3. Otherwise, if this is the last 0 in the binary number, output `][`.
4. Otherwise output `]`.

Finally, we close any opened brackets.
> 13 votes

# Answer
# Python 2.7, ~~172 149 124~~ 118 bytes

```
x=input();y="";z=0
for b in bin(x)[2+(x<1):]:y+="[]"[b<"1"];z+=b>"0"or-1;z+=99*(z<0)
print"["+(y,"[]"*(x+16))[z>0]+"]"

```

### Explanation:

Define a bijection by `[``1` and `]``0`. Any arrangement of brackets can then be written as a binary number and vice versa, for instance `[][]``1010`(10) and `[[][]]``110100`(52). All valid arrangements of up to 15 open brackets (30 brackets in total) are covered by numbers with up to 30 bits (ignoring leading zeros), which are precisely the numbers less than 231.

The first for-loop gives the inverse of this bijection, converting a number to an arrangement of brackets, while checking that the arrangement is valid.

Invalid arrangements are replaced within the print statement by long sequences of brackets to avoid collisions. For instance `11`(3)↔`[[` is not valid so we concatenate 3+16 brackets instead. This ensures all arrangements are unique.

The resultant arrangement is placed within a pair of brackets to make a nested array, so that `1010`(10) becomes `[[][]]` and `110100`(52) becomes `[[[][]]]`. The extra open bracket means we've now covered all arrays with 16 open brackets.

---

*The following program can be used to figure out the number for a given array with up to 16 brackets.*

```
s=raw_input();o="";
for c in s[1:-1]:
 if c=="[":o+="1"
 if c=="]":o+="0"
print int(o,2)

```
> 12 votes

# Answer
# Perl, ~~80~~ 79 bytes

Again uses orlp's algorithm, but this time I first checked if it works...

Includes +1 for `-p`

Give input number on STDIN

```
nest.pl <<< 8

```

`nest.pl`:

```
#!/usr/bin/perl -p
($_=sprintf"%b",$_).=2x(s^.^$&or++$n-pos&&/.0/g?++$n%1:$`&&21^eg-$n);y;102;();

```

Linus's solution is 64 bytes in perl:

```
#!/usr/bin/perl -p
$_=sprintf"%b",/.+/g;$_=10x($&&&$&+16)if!/^(1(?1)*0)+$/;y;10;()

```

Dennis's solution is 59 bytes in perl (increasingly slower for large numbers):

```
#!/usr/bin/perl -p
1while$_-=(sprintf"%b",$n++)=~/^(1(?1)*0)+$/;$_=$&;y;10;()

```
> 5 votes

# Answer
# Spoon, 63 bytes (501 bits)

```
000001001001001011001101001010011011111001010001000000101010
101101100110100101101001000101100010001000000100011000010000
000000000000001110111110010000001110110110010100100100100100
000110011010001000000110110000010000001010110011011011011001
000000011010010010010001000000111011011011101001001001000110
110110010100100101011001000100000011010001000000111011011001
010010010010010001101101101001000110110010110001101101101101
100100010001010010001010011011001000000011001101001001010010
000001100101001000111

```

This is the following brainfuck program converted to spoon:

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

```

Reads an integer in binary on stdin, and outputs the nested list on stdin. Requires 0 to be input as the empty string (no digits), and requires a brainfuck interpreter with 8-bit cells. Same algorithm as my Python answer.

Readable version:

```
-[+[+<]>>+]<+++.           push open bracket and print it
[->+>+<<]                  dup
>>++                       increment to close bracket

>>,[                       read input loop
    >-[<->-----]+<+++          subtract 48 and set up if/else
    [-                         if c == 1
        <+                         increment s
        <<.>>>                     output open bracket
    >-<]>[-<                   else
        <-[->+<]                   decrement and move s
        <<<[-]                     zero l
        >>>>[-<+<<<+>>>>]          l = s and restore s
        <<.>                       output close bracket
        >+<[>-]>[-                 if s == 0
            <+                         undo s decrement
            <<.                        output open bracket
        >>>>]<<
    >>]<
,]

<<<<[                      if l
    >.>.                   output pair
<<[-]]
>>>+[-<.>]                 output close bracket s+1 times

```
> 5 votes

# Answer
# Jelly, 28 bytes

```
ḃ2-*µSN;+\>-Ạ
1Ç#Ṫḃ2ṭ2;1ị⁾][

```

This iterates over all strings of the characters `[` and `]` that start with a `[` and end with a `]`, verifies if the brackets match, and prints the **n**th match.

Try it online!
> 5 votes

# Answer
# Python 3, ~~120~~ 114 bytes

```
def f(n,k=0):
 while~n:
  k+=1
  try:r=eval(bin(k).translate({48:'],',49:'['})[3:-1])+[];n-=1
  except:0
 print(r)

```

Test it on Ideone.

### How it works

The defined function **f** takes input **n** and initializes **k** to **0**. We'll keep incrementing **k** until **n + 1** values of **k** result in a valid output. Every time we find such a value of **k**, **n** is decremented once it reaches **-1**, `~n` yields **0**, and the list **r** that corresponds to the last value of **k** is printed.

The partial mapping from the positive integers to nested lists (i.e., **k ↦ r**) has to be bijective, but there are no other constraints. The one used in this answer operates as follows.

1. Convert **k** to a binary string representation, staring with **0b**.

For example, **44 ↦ "0b101100"**.
2. Replace all **0**'s (code point **48**) in the string representation with the string **"\],"** and all **1**'s (code point **49**) with **\[**.

For example, **"0b101100" ↦ "\],b\[\],\[\[\],\],"**.
3. Remove the first three characters (they correspond to **"0b"**) and the trailing character (hopefully a comma).

For example, **"\],b\[\],\[\[\],\]," ↦ "\[\],\[\[\],\]"**.
4. Try evaluating the generated code. If this results in an error, **k** isn't mapped to any list.

For example, **"\[\],\[\[\],\]" ↦ (\[\], \[\[\]\])**.
5. Concatenate the result (if any) with the empty list. If this results in an error, **k** isn't mapped to any list.

For example, **(\[\], \[\[\]\]) + \[\]** errors since **+** cannot concatenate lists and tuples.
> 5 votes

# Answer
## Haskell, 71 bytes

```
p 1=["[]"]
p n=['[':h++t|k<-[1..n-1],h<-p k,_:t<-p$n-k]
((p=<<[1..])!!)

```

The main function on the last line indexes into a list of all nested arrays, sorted by size (number of open brackets). So, all the arrays of size at most 16 are listed first.

Let's first look at code that's nicer and shorter, but Haskell's typechecker refuses to accept.

```
p 1=[[]]
p n=[h:t|k<-[1..n-1],h<-p k,t<-p$n-k]
((p=<<[1..])!!)

```

The function `p` on input `n` gives a list of all nested arrays of size `n` (open brackets). This is done recursively. Each such array consists of some head `h` (first member) of size `k` and some tail `t` (other members) of size `n-k`, both sizes nonzero. Or, it's the empty array for size `n==1`.

The expression `p=<<[1..]` then flattens `p(1), p(2), ...` into a single infinite list of all arrays sorted by size

```
[ [], [[]], [[],[]], [[[]]], [[],[],[]], [[],[[]]], [[[]],[]], [[[],[]]], ...

```

and the main function indexes into it.

... Or, it would, if Haskell didn't whine about "construct\[ing\] the infinite type: t ~ \[t\]". Haskell cannot represent the infinite list above whose elements are arbitrarily nested arrays. All its elements must have the same type, but a type t cannot be the same as a list of t's. In fact, the function `p` itself cannot be assigned a consistent type without dependent typing, which Haskell lacks.

So, instead we work on strings of brackets, simulating the cons operation by acting on `[` and `]` characters. This takes an extra 9 bytes. The perils of golfing in a type-safe language.
> 4 votes

# Answer
## Haskell, ~~87~~ 82 bytes

```
0#0=[""]
n#m=['[':x|n>0,x<-(n-1)#m]++[']':x|n<m,x<-n#(m-1)]
(([0..]>>= \y->y#y)!!)

```

Outputs the array elements. Usage example: `(([0..]>>= \y->y#y)!!) 3` -\> `"[][]"`.

Function `#` builds all nested arrays as strings for `n` open and `m` close brackets, by keeping track of how many of each are left over. Always starts with `n == m`. The main function calls `y # y` for every `y <- [0,1,...]` and picks the element at the index given by the input.
> 3 votes

# Answer
# MATL, 31 bytes

```
O`@BEqXJYs0&)0>w~hA+tG>~]x92J-c

```

Try it online! Or verify the first few test cases (takes a few seconds).

The produced mapping is:

```
0 -> []
1 -> [[]]
2 -> [[][]]
3 -> [[[]]]
4 -> [[][][]]
5 -> [[][[]]]
6 -> [[[]][]]
7 -> [[[][]]]
...

```

## Explanation

The code keeps testing increasing binary numbers, with digit `0` replaced by `-1`; that is, using `1` and `-1` as digits. Digit `1` will represent `'['` and `-1` will represent `']'`.

The program counts until *n*+1 *valid* numbers have been obtained. A number is valid if the following two conditions hold:

1. The sum of digits is zero (that is, there is an equal number of `1` and `-1`)
2. The cumulative sum of digits is always positive (that is, the accumulated number of `1` digits always exceeds that of `-1`) except at the end (where it is zero by condition 1).

Once *n*+1 valid numbers have been obtained, the last one is transliterated by changing `1` into `[` and `-1` into `]`, and then it is displayed.

Code:

```
O          % Push 0: initial count of valid numbers
`          % Do...while
  @        %   Push iteretation index k, starting at 1
  B        %   Convert to binary. For example, k=6 gives [1 1 0 0]
  Eq       %   Multiply by 2, subtract 1: transforms [1 1 0 0] into [1 1 -1 -1]
  XJ       %   Copy that to clipboard J, without popping it
  Ys       %   Cumulative sum: gives [1 2 1 0]
  0&)      %   Split array into its final element and the rest. Gives 0, [1 2 1]
  0>       %   Yields 1 for positive entries (condition 2). So in this case it
           %   gives [1 1 1]
  w        %   Swap: moves second-top element in the stack (0 in this case) to top
  ~        %   Negate: yields 1 if input is 0 (condition 1). Gives 1 in this case
  h        %   Concatenate horizontally. Gives [1 1 1 1]
  A        %   All: gives 1 if all elements are 1. Gives 1 in this case, meaning
           %   that this k is valid
  +        %   Add the result (0 or 1) to the count of valid numbers
  t        %   Duplicate
  G        %   Push input n
  >~       %   Loop condition: false (exit loop) if count exceeds input n
]          % End loop. At this point the result is in clipboard J, in 1/-1 format
x          % Delete count
92         % Push 92. Will be used to convert 1, -1 to '[', ']' (ASCII 91, 93)
J          % Push result in 1/-1 format
-          % Subtract: converts 1 to 91, -1 to 93
c          % Convert to char. Implicitly display

```
> 2 votes

# Answer
# JavaScript (Node.js), 85 bytes

```
x=>eval("g=i=>i>1?(h-=i*2%4-1)&&']['[i%2]+g(i>>1):']';for(i=0;~x;~h||--x)h=0,g(i++)")

```

Try it online!

Work for all positive integers assuming infinite bit width. But may fail when n is large and bit is broken. Slow.

# JavaScript (Node.js), 90 bytes

```
x=>eval("g=i=>i>1?(h-=[i]*2%4-1)&&']['[i%2n]+g(i>>1n):']';for(i=0n;~x;~h||--x)h=0,g(i++)")

```

Try it online!

Should be enough and theoretically all. Slow.

# JavaScript (Node.js), ~~97~~ 96 bytes

```
x=>(h=x.toString(2).replace(/./g,c=>']['[i+=c-.5,i-=!i,c],i=0),i-.5?'['+'[]'.repeat(x+20):h)+']'

```

Try it online!

Only fit the range. Fast for short output
> 0 votes

---
Tags: code-golf, array, balanced-string, open-ended-function, ragged-list
---


title: Is this continuous terrain?

text:
# Question
Title: Is this continuous terrain?
Very related

You're given a piece of ASCII art representing a piece of land, like so:

```
   /‾\
__/   ‾\_
         \_/‾\
              \

```

Since an overline () is not ASCII, you can use a `~` or `-` instead.

Your challenge is to determine if it is connected by the lines of the characters. For example, the above can be traced like so:

To clarify the connections:

* `_` can only connect on the bottom on either side
* (or `~` or `-`) can only connect on the top on either side
* `/` can only connect on the top right and bottom left
* `\` can only connect on the top left and bottom right

It doesn't matter where the connections start and end as long as they go all the way across. Note that one line's bottom is the next line's top, so stuff like this is allowed:

```
_
 ‾

\
 \

 _
/

\
 ‾

```

You can assume input will only contain those characters plus spaces and newlines, and will only contain one non-space character per column.

Input can be taken as ASCII art, an array of rows, a character matrix, etc.

## Testcases

Separated by double newline.

Truthy:

```
\
 \

\_
  \ /\/\_
   ‾     \

/\
  \/

\_
  ‾\

   /‾\
__/   ‾\_
         \_/‾\
              \

```

Falsy:

```
/
 \

//

 ‾‾
/  \

‾
 _

\____/
      /‾‾‾\

```

# Answer
> 11 votes
# Python 3.8, 85 bytes

Input is taken as a list of lines, with  replaced with dashes (`-`).

```
lambda L,n=0:len({(n:=n+2-ord(c:=max(x))//2%5)-x.index(c)+(c<'0')for x in zip(*L)})<2

```

Try it online!

# Answer
> 7 votes
# , 43 39 bytes

```
[:*/2=/@(I.@:*-1#.3 2&=+1&=)\' -\/'i.|:

```

Try it online!

* `' -\/'i.|:` Transpose and convert characters to integers.
* `2...(...)\` For each pair of rows...
* `I.@:*` Get the indices of the non-zero (non-space) element...
* `-1#.3 2&=+1&=` And adjust it as follows:
    + `1&=` If it's a `-` in either position, subtract 1.
    + `3 2&=` If it's a `/` on the left or a `\` on the right, subtract 1.
* `=/@` Are the two row indices equal after this adjustment?
* `[:*/` Are they all equal?

# Answer
> 6 votes
# Retina, 77 bytes

```
m/(?<=^|¶)([\\_]([_\/]|.*¶ [-\\])|[\/-][-\\]| [_\/].*¶[\/-])/+`^.

^\s*\S\s*$

```

Try it online! Link includes test suite that takes double-spaced test cases and converts  to `-` which the script actually uses. Explanation:

```
/(?<=^|¶)([\\_]([_\/]|.*¶ [-\\])|[\/-][-\\]| [_\/].*¶[\/-])/+

```

Repeat while the first two columns have a valid join, either a `\` or `_` followed by either a `_` or `/` or a `-` or `\` on the next line, or a `/` or `-` followed by a `-` or `\`, or a `/` or `-` followed by a `_` or `/` on the previous line, ...

```
m`^.

```

... delete the first character of each line.

```
^\s*\S\s*$

```

Check that only one column is left.

# Answer
> 5 votes
# Charcoal, 37 bytes

```
ＷＳ⊞υι⬤Φθκ¬↨ＥＥ²⭆υ§ν⁺κλ⁺⌕λ⌈λ№⁺_§\/μ⌈λ±¹

```

Try it online! Link is to verbose version of code. Takes input as a rectangle of newline-terminated lines and outputs a Charcoal boolean, i.e. '-' for continuous, nothing if not. Assumes that any character not one of `\_/` or space is the overline character. Explanation:

```
ＷＳ⊞υι

```

Input the land.

```
⬤Φθκ

```

Loop over all the columns except one.

```
Ｅ²⭆υ§ν⁺κλ

```

Get the current and the next column.

```
Ｅ...⁺⌕λ⌈λ№⁺_§\/μ⌈λ

```

Find the positions of the non-space characters, but add 1 if the character is a `_`, or if it is either `\` or `/` depending on the column.

```
¬↨...±¹

```

Ensure the positions are equal.

# Answer
> 3 votes
# BQN, 35 bytesSBCS

Uses `¯` *MACRON* instead of the overline.

```
⌈˝{≡´¯1‿1↓¨((/˘=)-∊'¯'∾⊢)¨"/\"}⍉

```

Run online!

```
┌─
╵"\_                     # Input character matrix    - m
    \ /\/\_
     ¯     \"
             ┘
"\_\¯/\/\_\"             # collapsed - ⌈˝m
⟨ 0 0 1 2 1 1 1 1 1 2 ⟩  # the depth of each column  - /˘(⌈˝m)=(⍉m)

⟨ 0 0 0 1 1 0 1 0 0 0 ⟩  # locations of '¯' and '/'  - (⌈˝m)∊'¯'∾'/'
⟨ 0 0 1 1 0 1 0 1 1 2 ⟩  # depth - ^locations
⟨ 0 0 1 1 0 1 0 1 1 ⟩    # the last element dropped  - ¯1↓...

⟨  1 0 1 1 0 1 0 1 0 1 ⟩ # locations of '¯' and '\'  - (⌈˝m)∊'¯'∾'\'
⟨ ¯1 0 0 1 1 0 1 0 1 1 ⟩ # depth - ^locations
   ⟨ 0 0 1 1 0 1 0 1 1 ⟩ # the first element dropped - 1↓...

```

# Answer
> 1 votes
# Jelly, 28 bytes

```
“-\/_”iⱮⱮZTḢ+S+3BḊƲƲ€FḊs2E€Ạ

```

Try it online!

---
Tags: code-golf, string, ascii-art, decision-problem
---


title: Can this village have a wedding?

text:
# Question
Title: Can this village have a wedding?
The quaint hamlet of Кодгольф in the Russian far east has a problem: their population is low (below 66), and no new people have arrived for years. Moreover, after centuries of near-isolation, just about everybody is related to each other.

Mayor Стекобмен has a solution that should keep the morale high: organise a wedding. However, the question is, are there two bachelors in the town that aren't at least cousins of each other?

The mayor fired up his state-of-the-art Microsoft Боб computer to consult the genealogy charts. They had just been updated to the brand-new ASCII format, and look like this:

```
ы┬К
 ю

```

And this:

```
 А┬д
 О┴п┬Щ
    Ф

```

And this:

```
  з┬Й
Л┬м┴п─┬Ф
Ы┴я┬А ш┬Я
   З   Е

```

And even this:

```
 ю┬────────Й
м┬Е
 │     ш
 │
 │
 Щ

```

Here's how it works. Each person is a letter from the Russian alphabet. Males are capital letters (any of АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ), females are lowercase letters (any of абвгдеёжзийклмнопрстуфхцчшщъыьэюя).

A '┬' between two people means they are married. Right below that is either another person - their child - or a '┴', meaning that this couple has two children; located to the left and right of the symbol.

Moreover, to the right and left of '┬' and '┴' there can be any number of '─' characters, to extend the lines, as it were. Similarly, there can be any number of '│' characters above a '┴' or below a '┬'.

Lastly, a character without any defined symbol above them is considered a new arrival to the village, and by definition unrelated to anybody.

Also be aware that this is a very conservative village. Nobody marries more than once, and every marriage is heterosexual. Furthermore, assume everybody in the graph is alive, and no two people share the same name: e.g., the same Cyrillic character never occurs more than once.

The two bachelors should be of the opposite gender, and they should not be first cousins or any more closely related. First cousins once removed is okay. In other words: they should not share a parent, or a grandparent, or have one's grandparent be another's parent.

## Challenge

Make the shortest possible program with as input either a string (containing newline characters), or a string array, or a rectangular two-dimensional string or char array (no higher or wider than 100 characters), containing the family tree of the town. Assume the input is a valid family tree. Ignore any character not given an explicit function in the above description.

It's fine to use an encoding other than Unicode for input/output purposes, e.g. KOI8-R as long as it's known and standardised by someone other than yourself. Scoring is done per this answer. If your language handles Cyrillic natively, it's an advantage!

Return a boolean value of true or false (or a bit/int of 1 or 0, or any consistent truthy/falsey value used by the language of your choice) to indicate whether there can be a wedding given the family tree.

## Examples

1.

```
ы┬К
 ю

```

FALSE (there's only one bachelor)

2.

```
   А┬д
 ю┬О┴п┬Щ
  Щ   ф

```

FALSE (Щ and ф are cousins)

3.

```
  з┬Й
Л┬м┴п─┬Ф
Ы┴я┬А ш┬Я
   З   Е

```

FALSE (З, Е and Ы are all male)

4.

```
  з┬Й
Л┬м┴п─┬Ф
ё┴А┬я ш┬Я
   З   Е

```

TRUE (ё and Е can marry)

5.

```
             ю┬────────Й
            м┬Е
             │     ш
             │
             │
             Щ

```

TRUE (ш is not related to anybody)

6.

```
           д┬Ф
 ю┬────────Й┴─ё┬З
  │            │
  │            ш <this person smells bad
  │
  │
  Щ <this person betrayed the Party!

```

FALSE (Щ and ш are cousins)

7.

```
Щ 1234567890 quick brown foxes jumped over the lazy dog ш

```

TRUE (Щ and ш are unrelated)

8.

```
    з┬Й
  Л┬м┴п─┬Ф
й┬Ы┴я┬А ш┬Я
 Э   З   ю

```

TRUE (ю and З, and also ю and Э)

9.

```
 А┬д      ф┬Ж
 м┴п┬Щ     ю┬Я
    Ф       ц

```

TRUE (ц and Ф)

NOTE: Here is an ASCII version of roughly the same challenge.

# Answer
# Jelly, ~~160~~ 159 bytes

```
Ø.UN,ƊAN,Ɗ+Ṫ¥+œị2,5yⱮ$ɼ=5,6⁼Ø.Ɗɗ¡ƬṪ¥ƒ⁸’1¦⁺œị®⁼5ƊÐ¿ṖṪ+2¦œị®⁻.Ɗ¡ƬṪ¥ⱮØ+$“”¹?
Odȷ%⁴ỊḢịƊ€€H“¥©“©©‘;U¤œṣjƭƒ$€ƬṪ©=.ŒṪ+2¦œị®ɗⱮØ+f2,4ƊÐḟWÇ€Ẏ$Ƭḣ3ẎƲ€Œcf/ÐḟḢ€€ȧœị¥O>⁽¡FIFẸ

```

Try it online!

A monadic link that takes a list of Jelly strings and returns 1 for true and 0 for false.

I’m sure this could be golfed more. Full explanation to follow.
> 5 votes

# Answer
# K (ngn/k), ~~230 203 200~~ 196 bytes

```
{t:{x*\:x};n:#*x:4(+|0,)/x;p:&2!c:+/"╒ё╡Ё©ъъ"<\:a:,/x;|//(~h=\:h:4!c p)&t[~|/p=/:?,/2#'(p^p^)'g]&3<{&/'x+\:x}/(~=#p)*(#a;1)0|/t'?(+/'p=/:/:g:{?'x,/'x x}/(!#a)+(-e;e,:n;e;n*e:-1 1;())4^"┴┬─│"?a)^0}

```

the input and the k code must be encoded in koi8-r. test with (linux only):

```
git clone https://bitbucket.org/ngn/k
cd k/g
../k can-this-village-have-a-wedding.k

```

please make sure your editor handles koi8-r correctly. for instance, if using vim, you can type `:e ++enc=koi8-r` after opening the file or put `set fencs=utf-8,koi8-r` in your `~/.vimrc`

---

k functions are written in `{` `}`, have an implicit argument `x`, and consist of `;`-separated expressions.

the sequence of expressions is evaluated left-to-right but the code within each expression is right-to-left.

`t:{x*\:x}` helper function that creates a multiplication table (outer product) for a list `x`

`x:4(+|0,)/x` surrounds the input `x` with zeroes. literally: 4 times (`4(` `)/`) add zero(-es) on top (`0,`), reverse (`|`), and transpose (`+`).

`n:#*x` let `n` be the width of the input. literally: length (`#`) of the first (`*`)

`a:,/x` let `a` be the flattened input

`c:+/"╒ё╡Ё©ъъ"<\:a` for each character in `a`, count how many of `"╒ё╡Ё©ъъ"`are before it (in koi8-r). this will give odd numbers for russian letters and even for non-letters. also, the remainder mod 4 will indicate the sex - upper/lowercase.

`p:&2!c` take `c` mod 2 (`2!`) and make a list of the indices where (`&`) it's 1. "`p`" for "people".

the rest of the code will build three `p`×`p` matrices that represent conditions for marriage:

* the couple must be \>3 steps apart in the graph of relatives. a "step" is a relationship of parent-child or spouse or sibling.

+ `4^"┴┬─│"?a` for each in `a` find its index among `"┴┬─│"` and fill in 4 if not found.
    + `(-e;e,:n;e;n*e:-1 1;())` replace `"┴"` with (-1;1;-n), `"┬"` with (-1;1;n), `"─"` with (-1;1), `"│"` with (-n;n), and others with an empty list
    + `(!#a)+` add `0 1 2`.. thus creating lists of neighbours
    + `g:{?'x,/'x x}/` transitive closure - extend (`,/`) each (`'`) neighbour list (`x`) with the neighbour lists of its neighbours (`x x`) and unique it (`?`), until convergence (`{` `}/`); assign to `g` for "graph"
    + `+/'p=/:/:g` for each of `g`'s neighbour lists build a boolean mask for which people are in it. ignore non-people.
    + `?(` `)^0` remove scalar 0s (`(` `)^0`) as they are a by-product of empty neighbour lists, and make the rest unique (`?`). this gives us a list of families as boolean masks.
    + `t'` build a family matrix for each family
    + `0|/` boolean-or of all family matrices
    + `(#a;1)` replace 0s with "infinity" (the length of `a` is as good as infinity here) and keep 1s as they are - this is a graph of how closely related `p` are. we need to find the shortest paths in it.
    + `(~=#p)*` put 0s on the diagonal. literally: multiply (`*`) by the negation (`~`) of the unit matrix (`=`) of that size (`#p`)
    + `{&/'x+\:+x}/` until convergence, try to improve *dist(i,j)* with *dist(i,k)+dist(k,j)* (similar to the floyd-warshall algorithm)
    + `3<` more distant than first cousins
* they must not be already married

+ `t[~|/p=/:?,/2#'(p^p^)'g]` check which `p` are among the first 2 (`2#`) of the intersection between people (`(p^p^)`) and each (`'`) neighbour list in `g`, and make it a boolean table
* they must be of opposite sexes

+ `(~h=\:h:4!c p)` remember that `c` mod 4 encodes gender information

finally, `|//`...`&`...`&`... and-s the three matrices and tests if there's a truthy element in the result
> 7 votes

# Answer
# Python3, 1001 bytes:

```
m='АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
f=m.lower()
def g(t,c,l,w,d,s=[],r=[],o=-1):
 k=0
 for q,(x,y) in [(0,[0,-1]),(1,[1,0]),(1,[-1,0])]:
   if q!=o and len(t[0])>(a:=c[0]+x)>=0 and len(t)>(b:=c[1]+y)>=0 and(a,b)not in r:
    if(h:=t[b][a])=='│'or h=='─':k=1;yield from g(t,(a,b),l,q,d,s,r+[(a,b)])
    elif h =='┴':k=1;yield from g(t,(a,b),h,q,d,s,r+[(a,b)],o=1)
    elif h=='┬':
     if q:d.append(s[-1])
     else:k=1;yield from g(t,(a,b),h,q,d,s,r+[(a,b)])
    elif h in m+f and l in'┬┴':k=1;yield from g(t,(a,b),h,q,d,s+[h],r+[(a,b)])
 if not k:yield s
def e(x,y):
 return not any((q:=set(a)&set(b)) and any(a.index(i)<3 for i in q) for a in x for b in y)
def a(t):
 b,p,z=[*filter(None, t.split('\n'))],{},[]
 for x,y in[(x,y)for x in range(len(b[0]))for y in range(len(b))if(l:=b[y][x])in m+f]:
   for s in g(b,(x,y),b[y][x],0,z,s=[b[y][x]],r=[(x,y)]):
    p[s[0]]=p.get(s[0],[])+[s]
 return any(a not in z and b not in z and len(set([a in m, b in m]))==2 and e(p[a],p[b]) for a in p for b in p)

```

The basic idea is to traverse the input graph, building paths between nodes (the genealogy for each node), marking which nodes are already married, and then checking if it is possible for any two resulting nodes to marry (not already married, male and female, not cousins, etc.)

Try it online!
> 1 votes

---
Tags: code-golf, decision-problem, graph-theory, unicode
---


title: Split along groups (hard mode)

text:
# Question
Title: Split along groups (hard mode)
*This is an alternate version of this earlier challenge with a twist that adds a significant bit of difficulty.*

Like last time, you are going to be given a string containing some alphabetic characters along with `[` and `]`. Your task is to split into sections that are enclosed in a "group" created by `[...]` and those that are not. e.g.

```
"absbn[mesl]meslo[eyyis]me"
->
"absbn"
"mesl"
"meslo"
"eyyis"
"me"

```

However unlike last time, this time a "group" must be non-empty. This means it must contain at least one character. So when there are `[]` next to each other they don't form a group. For example:

```
"absm[]mm[m]"
->
"absm[]mm"
"m"
""

```

The first pair of brackets is empty so it can't form a group. The second one does so it counts as a group and we split it. Notice that the non-group portions *can* be empty, it's just the groups that cannot.

Additionally when there is a conflict where two possible groups could be made: like `co[[x]t` or `m[[e]]it`, we will always choose the *smallest* valid group. In the case of a tie we choose the group that starts the furthest to the left.

Any `[`s left without a match are just regular characters and appear in the output.

So in `co[[x]t` we could do `co` `[x` `t`, but we could also do `co[` `x` `t`. Since the group here is either `[x` or `x` we choose the smaller one and the result is `co[` `x` `t`. In the second case `me[[e]]it` there are 4 ways to make groups here, but unambiguously `me[` `e` `]it` results in the smallest group.

If we have `me[[]]yt` then the smallest group would be `[]`, but that's not a group, so our options are `me [ ]yt` and `me[ ] yt` so we choose `me [ ]yt` because that group starts further to the left.

Your task will be to take a non-empty string of characters `a` through `z` plus two brackets of your choice (`[]`, `{}`, `()` and `<>`) and to split it as described above, providing a list of strings as output.

In cases where a group is on the boundary of the string, e.g. `aaa[b]` or `[ems]ee` you may choose to include or omit an empty string `""` on that boundary. The test cases always include them.

This is . Answers will be scored in bytes with the goal being to minimize the size of your source code.

## Test cases

```
go[cat]me -> "go" "cat" "me"
absbn[mesl]meslo[eyyis]me -> "absbn" "mesl" "meslo" "eyyis" "me"
absm[]mm[m] -> "absm[]mm" "m" ""
co[[x]t -> "co[" "x" "t"
me[[e]]t -> "me[" "e" "]t"
me[[]]yt -> "me" "[" "]yt"
mon[g]]u -> "mon" "g" "]u"
msy]mesl -> "msy]mesl"
eoa[m -> "eoa[m"
a[b[ -> "a[b["
mesi]mmp[mo -> "mesi]mmp[mo"
meu[ems[mela[] -> "meu[ems" "mela[" ""
w[[[] -> "w[" "[" ""
[foo]foobar[bar] -> "" "foo" "foobar" "bar" ""
ab[][]cd -> "ab" "][" "cd"
me[[[][]]yt -> "me[","[","","]","yt"
mem[[[[]]] -> "mem[[" "]" "]]"
mem[ooo[]]t -> "mem[ooo" "]" "t"

```

# Answer
# Retina 0.8.2, 45 bytes

```
0S1`<(.((.))*?)(?<!<(?=(?<-2>.)+>)(?<-2>.)*)>

```

Try it online! Link includes test suite that switches between `[]` and `<>` and separates the output lines for each case with `-` for convenience. Explanation:

```
0S1`

```

Include only capture group 1 in the results.

```
<(.((.))*?)...>

```

Look for a minimal group...

```
(?<!...(?<-2>.)*)

```

... that does not overlap with...

```
<(?=(?<-2>.)+>)

```

... a smaller group.
> 5 votes

# Answer
# Haskell, Reference answer

```
n!('[':x)|']':y<-drop n x="":take n x:n!y
n!(a:x)|i:j<-n!x=(a:i):j
n!x=[x]
f x=foldl(\x->(>>=)x.(!))[x][1..length x]

```

Try it online!

Since there seems to be some issues with understanding exactly the specifications, I thought I would post my Haskell reference solution. It's how I have been checking the test cases. It's golfed just enough to be a valid answer here, but I've left it as a CW since it could certainly be golfed better.

If you are unclear about anything in the question please ask, but this should serve as a way that you can test out cases without having to wait for me to respond.

## Explanation

The algorithm here is very simple. First we split all occurrences of the pattern `[.]`, preferring ones to the right. Then we split all occurrences of `[..]`, then `[...]`, then `[....]` up until the length of the list.

This never splits on empty groups, prioritizes smaller groups and when groups are equal sizes prioritizes to the right.
> 3 votes

# Answer
# Python3, 255 bytes:

```
def f(l):
 r=range
 q=len(l)
 if(j:=[(x,y) for x in r(q)for y in r(x+1,q)if l[x]=='['and l[y]==']'and y-x>1]):
  m=min(j,key=lambda x:[not l[x[0]:x[1]].isalpha(),x[1]-x[0],x[0]])
  yield l[:m[0]];yield l[m[0]+1:m[1]];yield from f(l[m[1]+1:])
 else:yield l

```

Try it online!
> 2 votes

# Answer
# Python, 150 bytes

```
def f(s):(n:=len(s));g,l,i=min([[s[i]>"[",s[i+2:].find("]")%n+3,i]for i in range(n)]+[3*[1]]);return[s]*(g|(l>n))or f(s[:i])+[s[i+1:i+l-1]]+f(s[i+l:])
```

Attempt This Online!

#### Old Python, 168 bytes

```
def f(s):
 r=s[1:];S=[s,r]
 while r:
  _,*r=r;S+=[r]
  if any(m:="".join(d)for x,*d,y in zip(*S)if[x,y]==[*"[]"]):x,y=s.split(f"[{m}]",1);return*f(x),m,*f(y)
 return s,
```

Attempt This Online!

#### Old Python, 174 bytes

```
def f(s):
 r=s[1:];S=[s,r]
 while r>r[:1]:
  _,*r=r;S+=[r]
  if any(m:="".join(d)for x,*d,y in zip(*S)if[x,y]==[*"[]"]):x,y=s.split(f"[{m}]",1);return*f(x),m,*f(y)
 return s,
```

Attempt This Online!

Thee requirement of having to pick a shorter match over a potentially overlapping earlier but longer match is too much for my regex skills.

This approach finds the shortest (first if ties) match, splits the string there and recurses on the ends.

#### Wrong Python, 53 bytes

```
lambda s:re.split(r"\[((?:[^][]+)|\[)\]",s)
import re
```

Attempt This Online!

I must admit I do not fully understand the rules. But this solves all test cases **EDIT:** did solve at the time.
> 1 votes

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


title: Mirror an integer... in NDos' way

text:
# Question
Title: Mirror an integer... in NDos' way
# NDos' Numeral System

NDos' numeral system is a numeral system invented by me. It represents every nonnegative integer by a binary tree. Given a nonnegative integer \\$n\\$:

* If \\$n=0\\$, it is represented as the empty tree.
* Otherwise, the tree has a root. With the binary expansion of \\$n\\$:

+ The left sub-tree of the root recursively represents the **length** of least significant consecutive `0`s of \\$n\\$ (trailing `0`s).
    + The right sub-tree of the root recursively represents the more significant side of \\$n\\$ split right before its least significant `1`. In other words, the right side is the number with its trailing `0`s and their leading `1` stripped off.

For example, if \\$n = 1100100\_2\\$, there are two trailing `0`s, so the left sub-tree will be \\$2\_{10} = 10\_2\\$. Without the trailing `0`s and their leading `1`, \\$ n \\$ becomes \\$1100\_2\\$, so the right sub-tree has that value.

For illustrative purposes, here are the full representation of the trees for \\$n=1\_2\\$ through \\$n=1110\_2\\$:

Note that the numbers of nodes is not monotone. The smallest counterexample is \\$10010\_2\\$ and \\$11000\_2\\$.

Here's a Haskell implementation of conversion between binary and NDos':

```
import Data.Bits

data NDosNat = Zero | Push1 !NDosNat !NDosNat deriving (Eq, Show)

intToNDos :: Int -> NDosNat
intToNDos x
  | x < 0 = error "intToNDos: Negative input"
  | x == 0 = Zero
  | otherwise = let
    lSZN = countTrailingZeros x
    in Push1 (intToNDos lSZN) (intToNDos (shiftR x (lSZN + 1)))

nDosToInt :: NDosNat -> Int
nDosToInt Zero = 0
nDosToInt (Push1 lSZN mBS) = shiftL (shiftL (nDosToInt mBS) 1 .|. 1) (nDosToInt lSZN)

```

(I couldn't convert from nor to `Integer` because of Haskell's poor bit manipulation API.)

# Objective

Given a nonnegative integer, treat it as represented in NDos' numeral system, and output its horizontal mirror image.

# Examples

Here are some mappings. All numbers are in binary:

```
0 ↔ 0
1 ↔ 1
10 ↔ 11
100 ↔ 111
101 ↔ 1000
110 ↔ 110
1001 ↔ 10000000
1010 ↔ 11000
1011 ↔ 100000000
1100 ↔ 1110
1101 ↔ 1000000

```

# Rule

**The input and the output must be integers natively supported by your language.**

# Answer
# x86 32-bit machine code, ~~29~~ 27 bytes

```
51 0F BC C8 74 13 D3 E8 D1 E8 E8 F1 FF FF FF 91 E8 EB FF FF FF 41 F9 D3 D0 59 C3

```

Try it online!

Uses the `regparm(1)` calling convention – argument in EAX, result in EAX.

-2 by making the function preserve ECX, removing the need to save it for the recursive calls.

Assembly:

```
.global f
f:  push ecx        # Save ECX onto the stack.
    bsf ecx, eax    # ECX := position of lowest 1 bit in EAX (= left subtree number).
    jz e            # Jump to the end if EAX was 0, which will return 0.
    shr eax, cl     # Shift EAX right by the number from above, removing the trailing 0s.
    shr eax, 1      # Shift EAX right by 1 more, removing the first 1.
                    #  (Now EAX holds the right subtree number.)
    call f          # Recursive call; apply the function to the right subtree number.
    xchg ecx, eax   # Exchange the value in ECX (the left subtree number)
                    #  with the value in EAX (which is f(the right subtree number)).
    call f          # Recursive call; apply the function to the left subtree number.
    inc ecx         # Add 1 to f(the right subtree number).
    stc             # Set the carry flag to 1.
    rcl eax, cl     # Rotate EAX together with the carry flag left by CL,
                    #  which is 1+f(the right subtree number).
                    # This appends to EAX a 1 and f(the right subtree number) 0s.
e:  pop ecx         # Restore the value of ECX from the stack.
    ret             # Return.

```
> 3 votes

# Answer
# Pari/GP, 50 bytes

-5 bytes borrowing some tricks from @Arnauld's JavaScript answer.

```
f(n,t=valuation(n,2))=if(n,(2*f(t)+1)*2^f(n>>t++))

```

Try it online!
> 5 votes

# Answer
# Python 2, 54 bytes

```
f=lambda n,b=0:n and[f(n/2,b+1),f(b)*2+1<<f(n/2)][n%2]

```

Try it online!

Takes in a non-negative integer and outputs the "mirrored" integer.

Use the recursive relation: If the left and right subtrees are `a` and `b` respectively, then the mirrored number will have `f(b)` and `f(a)` as left and right subtrees. To calculate `a` and `b`, I simply divide `n` by 2, then increment `b` by 1 until `n` is odd.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 58 bytes

-4 bytes thanks to @att.

```
f@0=0
f@n_:=(2f@#+1)2^f[(n/2^#-1)/2]&[n~IntegerExponent~2]

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES6), 45 bytes

A port of Surculose Sputum's Python answer.

```
f=(n,b=0)=>n&1?f(b)*2+1<<f(n/2):n&&f(n/2,b+1)

```

Try it online!

---

# JavaScript (Node.js), 50 bytes

It is unclear what the *arbitrary-length integers natively supported by* JS exactly are. Here is a version assuming that's BigInts.

```
f=(n,b=0n)=>x=n&1n?f(b)-~x<<f(n/2n):n&&f(n/2n,-~b)

```

Try it online!
> 3 votes

# Answer
# Charcoal, 35 bytes

```
ＵＭＥ⊕Ｎ＆ι±ι⊞Ｏυ∧ι×⊕⊗§υ⊖Ｌ↨ι²Ｘ²§υ÷κ⊗ιＩ⊟υ

```

Try it online! Link is to verbose version of code. Explanation: Calculates all of the mirror images from `0` to `n` inclusive and outputs the last one.

```
ＵＭＥ⊕Ｎ＆ι±ι⊞Ｏυ∧ι

```

For each integer `0` to `n`, calculate the maximal power of 2 that is a factor of it, or `0` for `0`. For each of those powers of 2, if the value is `0` then just push that, otherwise push...

```
×⊕⊗§υ⊖Ｌ↨ι²Ｘ²§υ÷κ⊗ιＩ⊟υ

```

... the result of looking up the number of trailing zeros, doubled and incremented and multiplied by 2 to the power the result of looking up the original value integer divided by the doubled power of 2.

```
Ｉ⊟υ

```

Output the last of the calculated values.
> 1 votes

---
Tags: code-golf, integer, integer-partitions
---