# Question
Title: Evaluating Parentheses and Brackets as Integers
Write a program that takes in a string of the four characters `()[]` that satisfies these points:

* Every left parenthesis `(` has a matching right parenthesis `)`.
* Every left bracket `[` has a matching right bracket `]`.
* Matching pairs of parentheses and brackets won't overlap. e.g. `[(])` is invalid because the matching brackets are not fully contained in the matching parentheses, nor vice-versa.
* The first and last characters are a matching pair of parentheses or brackets. So `([]([]))` and `[[]([])]` are valid but `[]([])` is not.

(A grammar for the input format is `<input> ::= [<input>*] | (<input>*)`.)

Each pair of matching parentheses and brackets evaluates to a non-negative integer:

* The values of pairs inside matching parentheses are all *summed*. The empty match `()` has value `0`.
* The values of pairs inside matching brackets are all *multiplied*. The empty match `[]` has value `1`.

<sup>(The sum or product of one number is that same number.)</sup>

For example, `([](())([][])[()][([[][]][][])([][])])` can be broken down and evaluated as `9`:

```
([](())([][])[()][([[][]][][])([][])])    <input>
(1 (0 )(1 1 )[0 ][([1 1 ]1 1 )(1 1 )])    <handle empty matches>
(1 0   2     0   [(1     1 1 )2     ])    <next level of matches>
(1 0   2     0   [3           2     ])    <and the next>
(1 0   2     0   6                   )    <and the next>
9                                         <final value to output>

```

Another example:

```
[([][][][][])([][][])([][][])(((((([][]))))))]    <input>
[(1 1 1 1 1 )(1 1 1 )(1 1 1 )((((((1 1 ))))))]
[5           3       3       (((((2     )))))]
[5           3       3       ((((2       ))))]
[5           3       3       (((2         )))]
[5           3       3       ((2           ))]
[5           3       3       (2             )]
[5           3       3       2               ]
90                                                <output>

```

Your program needs to evaluate and print the integer represented by the entire input string. You can assume the input is valid. The shortest code in bytes wins.

Instead of a program, you may write a function that takes in a string and prints or returns the integer.

# Answer
> 13 votes
# CJam, 23

```
q"])(""1]:*0]:+["4/ers~

```

With BIG credits to Dennis! Try it online

**Explanation:**

The program converts the input to a CJam expression then evaluates it.
`[…]` becomes `[…1]:*` (append 1 and multiply)
`(…)` becomes `[…0]:+` (append 0 and add)

```
q              read input
"])("          characters we want to replace
"1]:*0]:+["    replacement strings, concatenated
4/             split into strings of length 4: ["1]:*" "0]:+" "["]
er             replace (transliterate) the 3 characters with the 3 strings
s              convert the result (mixed characters and strings) to string
~              evaluate

```

# Answer
> 8 votes
# Common Lisp - 98

```
(lambda(s)(eval(read-from-string(#1=ppcre:regex-replace-all"\\["(#1#"]"(#1#"\\("s"(+")")")"(*"))))

```
1. Replace `(` by `(+`
2. Replace `[` by `(*`
3. Replace `]` by `)`
4. Read from string
5. Eval

This requires `cl-ppcre` library to be loaded in current lisp image.

### Explanation

Functions `*` and `+` are variadic and return their neutral value when given no arguments. For your examples, the evaluated lisp form are the following ones:

```
(+ (*) (+ (+)) (+ (*) (*)) (* (+)) (* (+ (* (*) (*)) (*) (*)) (+ (*) (*))))
=> 9

```

and

```
(* (+ (*) (*) (*) (*) (*)) (+ (*) (*) (*)) (+ (*) (*) (*))
   (+ (+ (+ (+ (+ (+ (*) (*))))))))
=> 90

```

### Without regexes - 183 bytes

```
(lambda(s)(do(r(x(coerce s'list))c)((not x)(eval(read-from-string(coerce(reverse r)'string))))(setq c(pop x))(push(case c(#\[ (push #\* r)#\()(#\] #\))(#\( (push #\+ r) #\()(t c))r)))

```

### C'mon, Lisp - 16 bytes (experimental)

```
+((<r*([<r)]<rRE

```

Other languages are so terse that I am tempted to make my own golfing language based on Common Lisp, for shorter string manipulations. Currently there is no spec, and the eval function is the following one:

```
(defun cmon-lisp (expr &rest args)
  (apply
   (lambda (s)
     (let (p q)
       (loop for c across expr
             do (case c
                  (#\< (push (pop p) q))
                  (#\r
                   (let ((a1 (coerce q 'string)) (a2 (coerce p 'string)))
                     (setf p nil
                           q nil
                           s
                             (cl-ppcre:regex-replace-all
                              (cl-ppcre:quote-meta-chars a1) s a2))))
                  (#\R
                   (setf s
                           (if (string= s "")
                               nil
                               (read-from-string s))))
                  (#\E (setf s (eval s)))
                  (t (push c p))))
       s))
   args))

```

Tests:

```
(cmon-lisp "+((<r*([<r)]<rRE" "([] [] ([] []))")
=> 4

```
* there is an implicit argument called `s` and two stacks, `p` and `q`.
* characters in source code are pushed to `p`.
* `<` : pops from `p` and pushes to `q`.
* `r` : replaces in `s` (must be a string) from characters in `q` to charactes in `p`; result is stored in `s`; `p` and `q` are emptied.
* `R` : read from string `s`, store result in variable `s`.
* `E` : eval form `s`, store result in `s`.

# Answer
> 6 votes
# Pyth, ~~35~~ ~~34~~ 33 bytes

```
L?*F+1yMbqb+YbsyMbyvsXzJ"])"+R\,J

```

Demonstration.

*1 byte thanks to @Jakube.*

We start by parsing the input. The input format is close to Python, but not quite. We need commas after each parenthesized or bracketed group. The comma at the end of a bracketed group is unnecessary, but harmless. To accomplish this, we use this code:

```
vsXzJ"])"+R\,J
  X               Translate
   z              in the input
     "])"         the characters "])"
    J             which we will save to J to
             J    J
         +R\,     with each character mapped to itself plus a ",".
 s                Combine the list to a string.
v                  Evaluate as a Python literal.

```

This will leave an extra `,` at the end of the string, which will wrap the whole object in a tuple, but this is harmless, because the tuple will be summed, and so have a value equal to its element.

Now that the string is parsed, we must find its value. This is done using a user defined function, `y`, which is called on the parsed object. the function is defined as follows:

```
L?*F+1yMbqb+YbsyMb
L                     Define a function, y(b), which returns the following:
 ?       qb+Yb        We form a ternary whose condition is whether the input, b,
                      equals the inputplus the empty list, Y. This is true if
                      and only if b is a list.
      yMb             If so, we start by mapping y over every element of b.
  *F+1                We then take the product of these values. The +1 ensures
                      that the empty list will return 1.
                yMb   Otherwise, we start by mapping y over every element of b.
               s      Then, we sum the results.

```

# Answer
> 3 votes
# Emacs lisp, 94

The format looks very lispy, so I thought a simple transformation might work:

```
(defun e()(format-replace-strings'(("("."(+")("["."(*")("]".")")))(eval(read(buffer-string))))

```

The intermediate format looks something like (for the example in the question):

```
(+(*)(+(+))(+(*)(*))(*(+))(*(+(*(*)(*))(*)(*))(+(*)(*))))

```

We're helped by the fact that addition and multiplication already do what we want with an empty argument list.

Degolfed, and interactive, for you playing pleasure:

```
(defun paren_eval()
  (interactive "*")
  (format-replace-strings '(("(" . "(+")
                            ("[" . "(*")
                            ("]" . ")")))
  (eval (read (buffer-string)))
)

```

# Answer
> 2 votes
# Retina, 111 bytes

```
[\([](1+x)[]\)]
$1
\[]
1x
\(\)
x
(\[a*)1(?=1*x1*x)
$1a
a(?=a*x(1*)x)
$1
(\[1*x)1*x
$1
)`(\(1*)x(?=1*x)
$1
[^1]
<empty line>

```

Gives output in unary.

Each line should go to its own file but you can run the code as one file with the `-s` flag. E.g.:

```
> retina -s brackets <input_1
111111111

```

Explanation comes later.

# Answer
> 2 votes
# Java, 349 characters

A simple recursive approach. Expects the string to be the first argument used to call the program.

```
import java.util.*;class K{int a=0,b;String c;public static void main(String[]a){K b=new K();b.c=a[0];System.out.print(b.a());}int a(){switch(c.charAt(a++)){case'(':b=0;for(int a:b())b+=a;break;case'[':b=1;for(int a:b())b*=a;}a++;return b;}List<Integer>b(){List d=new ArrayList();char c;while((c=this.c.charAt(a))!=']'&&c!=')')d.add(a());return d;}}

```

Expanded:

```
import java.util.*;

class K {
    int a =0, b;
    String c;
    public static void main(String[] a){
        K b = new K();
        b.c = a[0];
        System.out.print(b.a());
    }
    int a(){
        switch (c.charAt(a++)){
            case '(':
                b =0;
                for (int a : b())
                    b += a;
                break;
            case '[':
                b =1;
                for (int a : b())
                    b *= a;
        }
        a++;
        return b;
    }
    List<Integer> b(){
        List d = new ArrayList();
        char c;
        while ((c= this.c.charAt(a)) != ']' && c != ')')
            d.add(a());
        return d;
    }
}

```

# Answer
> 2 votes
# Perl 5, 108

Done as an interpreter rather than rewrite-and-eval. Not a great showing, but fun to write anyway.

```
push@s,/[[(]/?[(ord$_&1)x2]:do{($x,$y,$z,$t)=(@{pop@s},@{pop@s});
[$t?$x*$z:$x+$z,$t]}for<>=~/./g;say$s[0][0]

```

Un-golfed:

```
# For each character in the first line of stdin
for (<> =~ /./g) {
    if ($_ eq '[' or $_ eq '(') {
        # If it's an opening...
        # ord('[') = 91 is odd, ord('(') = 40 is even
        push @stack, [ ( ord($_) & 1) x 2 ];
        # so we will push [1, 1] on the stack for brackets and [0, 0] for parens.
        # one of these is used as the flag for which operator the context is, and
        # the other is used as the initial (identity) value.
    } else {
        # otherwise, assume it's a closing
        ($top_value, $top_oper) = @{ pop @stack };
        ($next_value, $next_oper) = @{ pop @stack };
        # merge the top value with the next-to-top value according to the
        # next-to-top operator. The top operator is no longer used.
        $new_value = $next_oper
            ? $top_value * $next_value
            : $top_value + $next_value
        push @stack, [ $new_value, $next_oper ];
    }
}

say $stack[0][0]; # print the value remaining on the stack.

```

# Answer
> 2 votes
# Python, 99

I tried a variety of methods but the shortest I could get was basically just a replacement and eval. I was pleasantly surprised to find that I could leave all the trailing `,`s, as Python can parse `[1,2,]` and the final trailing comma just puts the whole thing in a tuple. The only other non-straightforward part would be the `ord(c)%31%7` to seperate out the different characters (it evaluates to `2`,`3`,`1`,`0` for `(`,`)`,`[`,`]` respectively)

```
F=lambda s:eval(''.join(["],1),","reduce(int.__mul__,[","sum([","]),"][ord(c)%31%7]for c in s))[0]

```

# Answer
> 2 votes
# Clojure - 66 bytes

Notice that `([] (()) ([] []) [()] [([[] []] [] []) ([] [])])` is a valid Clojure form. So:

```
#(letfn[(g[x](apply(if(list? x)+ *)(map g x)))](g(read-string %)))

```
* This is an anonymous function taking a string, reading it and giving to `g`.
* The local `g` function apply `+` or `*` to the result of the invocation of `g` on sub-elements of its arguments.
* The base case of the recursion is a little subtle: it is reached when `x` in an empty sequence; `(map g x)` returns `nil`, and `apply` returns the neutral value for the operation.

# Answer
> 1 votes
# Java, 301

a bit of a different approach than TheNumberOne's answer, although mine is also recursive in nature. Input is taken from the command line. The void method saves a few bytes when removing the characters that are no longer needed.

```
enum E{I;String n;public static void main(String[]r){I.n=r[0];System.out.print(I.e());}int e(){int v=0;if(n.charAt(0)=='('){for(s("(");n.charAt(0)!=')';)v+=e();s(")");}else if(n.charAt(0)=='['){v=1;for(s("[");n.charAt(0)!=']';)v*=e();s("]");}return v;}void s(String c){n=n.substring(1+n.indexOf(c));}}

```

expanded:

```
enum EvaluatingParenthesesAndBrackets{
    AsIntegers;
    String input;
    public static void main(String[]args){
        AsIntegers.input=args[0];
        System.out.print(AsIntegers.evaluate());
    }
    int evaluate(){
        int value=0;
        if(input.charAt(0)=='('){
            for(substringAfterChar("(");input.charAt(0)!=')';)
                value+=evaluate();
            substringAfterChar(")");
        }
        else if(input.charAt(0)=='['){
            value=1;
            for(substringAfterChar("[");input.charAt(0)!=']';)
                value*=evaluate();
            substringAfterChar("]");
        }
        return value;
    }
    void substringAfterChar(String character){
        input=input.substring(1+input.indexOf(character));
    }
}

```

# Answer
> 1 votes
# Python, ~~117~~ ~~110~~ 109 bytes

```
def C(s,p=[0]):
 m=r=s[p[0]]=='[';p[0]+=1
 while s[p[0]]in'[(':t=C(s,p);r=r*t*m+(r+t)*(1-m)
 p[0]+=1;return r

```

One aspect I was struggling with is that the function basically has two return values: the product/sum, and the new position in the string. But I need a function that returns only the result, so returning a tuple does not work. This version uses a "reference" argument (list with one element), to pass the position back from the function.

I have a shorter version (103 bytes) that uses a global variable for the position. But that will only work on the first call. And a function that only works once seems a bit fishy. Not sure if it would be acceptable for code golf.

The algorithm is straightforward recursion. I tried a number of variations for the expression that updates the product/sum. I came up with a few versions that were exactly the same length, but none of them shorter.

I sort of expected that the approach that turns this into an expression that gets evaluated would probably win. But as they say: "To iterate is human, to recurse divine."

# Answer
> 1 votes
## JavaScript (ES6), 116 bytes

```
s=>+[...s].reduce((t,c)=>((x=c==']')||c==')'?t[1].push(t.shift().reduce((a,b)=>x?a*b:a+b,+x)):t.unshift([]),t),[[]])

```

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


title: Calculate a probability exactly

text:
# Question
Title: Calculate a probability exactly
This task is about writing code to compute a probability exactly. The output should be a precise probability written as a fraction in its most reduced form. That is it should never output `4/8` but rather `1/2`.

For some positive integer `n`, consider a uniformly random string of 1s and -1s of length `n` and call it A. Now concatenate to `A` its first value. That is `A[1] = A[n+1]` if indexing from 1. `A` now has length `n+1`. Now also consider a second random string of length `n` whose first `n` values are -1, 0, or 1 with probability 1/4,1/2, 1/4 each and call it B.

For example, consider `n=3`. Possible values for `A` and `B` could be `A = [-1,1,1,-1]` and `B=[0,1,-1]`. In this case the two inner products are `0` and `2`.

Now consider the inner product of `A[1,...,n]` and `B` and the inner product of `A[2,...,n+1]` and `B`.

Your code must output the probability that both inner products are zero.

For `n=1` this probability is clearly `1/2`.

I don't mind how `n` is specified in the code but it should be very simple and obvious how to change it.

**Languages and libraries**

You can use any language and libraries you like. I would like to run your code so please include a full explanation for how to run/compile your code in linux if at all possible.

# Answer
# Pyth, ~~48~~ ~~47~~ ~~46~~ 44 bytes

```
K,smlf!|Fms*Vd.>Tk2^,1_1Q^+0tM3Q^8Qj\//RiFKK

```

Try it online: Demonstration

The online version probably doesn't compute `n=6`. On my laptop (offline version) it takes about 45 seconds.

Brute force approach.

### Explanation:

```
smlf!|Fms*Vd.>Tk2^,1_1Q^+0tM3Q   implicit: Q = input number
                          tM3    the list [-1, 0, 1]
                        +0       add zero, results in [0, -1, 0, 1]
                       ^     Q   all possible lists of length Q using these elements
 m                               map each list d (B in Lembik's notation) to:
                  ,1_1              the list [1, -1]
                 ^    Q             all possible lists of length Q
   f                                filter for lists T (A in Lembik's notation),
                                    which satisfy:
       m        2                      map each k in [0, 1] to:
        s*Vd.>Tk                          scalar-product d*(shifted T by k)
    !|F                                not or (True if both scalar-products are 0)
  l                                 determine the length
s                                add all possibilities at the end

K,...^8QQj\//RiFKK
 ,...^8Q             the list [result of above, 8^Q]
K                    store it in K
              iFK    determine the gcd of the numbers in K
            /R   K   divide the numbers in K by the gcd
         j\/         join the two numbers by "/" and print

```
> 7 votes

# Answer
## Mathematica, ~~159~~ ~~100~~ ~~87~~ ~~86~~ 85 bytes

```
n=3;1-Mean@Sign[##&@@Norm/@({1,0,0,-1}~t~n.Partition[#,2,1,1])&/@{1,-1}~(t=Tuples)~n]

```

To change `n` just change the variable definition at the beginning.

Since it's brute force it's fairly slow, but here are the first eight results:

```
n   P(n)
1   1/2
2   3/8
3   7/32
4   89/512
5   269/2048
6   903/8192
7   3035/32768
8   169801/2097152

```

The last one already took 231 seconds and the runtime is horribly exponential.

## Explanation

As I said it's brute force. Essentially, I'm just enumerating all possible `A` and `B`, compute the two dot products for every possible pair and then find the fraction of pairs that yielded `{0, 0}`. Mathematica's combinatorics and linear algebra functions were quite helpful in golfing this:

```
{1,-1}~(t=Tuples)~n

```

This generates all n-tuples containing `1` or `-1`, i.e. all possible `A`. For `n = 3` that is:

```
{{1, 1, 1},
 {1, 1, -1},
 {1, -1, 1},
 {1, -1, -1},
 {-1, 1, 1},
 {-1, 1, -1},
 {-1, -1, 1},
 {-1, -1, -1}}

```

To compute `B` we do almost the same:

```
{1,0,0,-1}~t~n

```

By repeating `0`, we duplicate each tuple for each `0` it contains, thereby making `0` twice as likely as `1` or `-1`. Again using `n = 3` as an example:

```
{{-1, -1, -1},
 {-1, -1, 0}, {-1, -1, 0},
 {-1, -1, 1},
 {-1, 0, -1}, {-1, 0, -1},
 {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0}, {-1, 0, 0},
 {-1, 0, 1}, {-1, 0, 1},
 {-1, 1, -1},
 {-1, 1, 0}, {-1, 1, 0},
 {-1, 1, 1},
 {0, -1, -1}, {0, -1, -1},
 {0, -1, 0}, {0, -1, 0}, {0, -1, 0}, {0, -1, 0},
 {0, -1, 1}, {0, -1, 1},
 {0, 0, -1}, {0, 0, -1}, {0, 0, -1}, {0, 0, -1},
 {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0},
 {0, 0, 1}, {0, 0, 1}, {0, 0, 1}, {0, 0, 1},
 {0, 1, -1}, {0, 1, -1},
 {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0},
 {0, 1, 1}, {0, 1, 1},
 {1, -1, -1},
 {1, -1, 0}, {1, -1, 0},
 {1, -1, 1},
 {1, 0, -1}, {1, 0, -1},
 {1, 0, 0}, {1, 0, 0}, {1, 0, 0}, {1, 0, 0},
 {1, 0, 1}, {1, 0, 1},
 {1, 1, -1},
 {1, 1, 0}, {1, 1, 0},
 {1, 1, 1}}

```

Now, for each possible `A`, we want the dot product of each of those possible `B`, both with `A[1 .. n]` and `A[2 .. n+1]`. E.g. if our current `A` is `{1, 1, -1}`, we want the dot product with both `{1, 1, -1}` and with `{1, -1, 1}`. Since all our `B` are already conveniently the rows of a matrix, we want the two sublists of `A` as columns of another matrix, so that we can compute a simple dot product between them. But transposing `{{1, 1, -1}, {1, -1, 1}}` simply gives `{{1, 1}, {1, -1}, {-1, 1}}` which is just a list of all 2-element cyclic sublists of `A`. That's what this does:

```
Partition[#,2,1,1]

```

So we compute that and take the dot product with our list of `B`. Since we now get a nested list (since each possible `A` yields a separate vector), we flatten those with `##&@@`.

To find out if a pair `{x, y}` is `{0, 0}` we compute `Sign[Norm[{x,y}]]` where `Norm` gives `√(x²+y²)`. This gives `0` or `1`.

Finally, since we now just want to know the fractions of `1`s in a list of `0`s and `1`s all we need is the arithmetic mean of the list. However, this yields the probability of both at least one dot product being non-zero, so we subtract it from `1` to get the desired result.
> 8 votes

# Answer
# Pyth - 65 55 bytes

**Fixed bug with fraction reduction at cost of one byte.**

Uses brute force approach, and can be golfed hugely, but just wanted to get something out there. Very slow

```
*F-KP/Jmms*Vked,thdPhd*makhk^,1_1Q^[1ZZ_1)Q,ZZ2/lJ^2/K2

```

It uses Cartesian products to generate both `A` and `B`, doing the variable probabilities by making `0` appear twice in the source list and then counts the ones that inner product to zero. The inner product is make easy by the `V`ectorization syntactic sugar. Simplifing the fraction was scaring me initially, but it was pretty easy with the `P`rime Factorization function and the realization that we only have to reduce by powers of 2.

Try it online here.
> 6 votes

# Answer
# CJam, ~~58~~ ~~57~~ ~~54~~ ~~51~~ 46 bytes

```
WX]m*Zm*_{~.+2,@fm<\f.*::+0-!},,__~)&:T/'/@,T/

```

To run it, insert the desired integer between `WX]` and `m*`.

*Thanks to @jimmy23013 for the bit magic and for golfing off 5 bytes!*

Try it online in the CJam interpreter.

### Idea

Most parts of these answer are straightforward, but it uses two neat tricks:

* Instead of pairing all vectors of **{-1, 1}n** with all vectors of **{-1, 0, 1}n** with the desired probabilities, it considers counts the number of triplets of vectors in **{-1, 1}n** that satisfy a certain condition.

If we add the last two vectors of a triplet, the result will be a vector of **{-2, 0, 2}n**.

Since **(-1) + 1 = 0 = 1 + (-1)**, **0**s will occur twice as often as **-2**s and **2**s.

Dividing each component by **2** would yield a vector of **{-1, 0, 1}n** with the desired probabilities.

Since we are only interested if the scalar product is **0** or not, we can skip the division by **2**.
* After counting all triplets satisfying the condition of the question and the total number of triplets, we have to reduce the resulting fraction.

Instead of calculating the GCD of both numbers, since the denominator will always be a power of 2, it suffices to divide both numbers by the highest power of 2 that divides the numerator.

To obtain the highest power of 2 that divides **x**, we can take the bitwise AND of **x** and **~x + 1**.

**~x** reverses all bits of **x**, so all trailing **0**s become **1**s. By adding **1** to **~x**, those **1**s will turn back into **0**s and the last **1** in **~x + 1** will match the last **1** in **x**.

All other bits are either both **0** of distinct, so the bitwise AND return the integer consisting of the last **1** of **x** and all **0**s that follow it. This is the highest power of 2 that divides **x**.

### Code

```
WX]    e# Push the array [-1 1].
       e# Insert N here.
m*     e# Cartesian product: Push the array of all vectors of {-1,1}^N.
Zm*    e# Cartesian product: Push the array of all triplets of these vectors.
_      e# Copy the array.
{      e# Filter; for each triplet of vectors U, V and W in {-1,1}^N:
  ~    e#   Dump U, V and W on the stack.
  .+   e#   Compute X := V + W, a vector of {-2,0,2}^N, where each component is
       e#   zero with probability 1/2.
  2,@  e#   Push [0 1]. Rotate U on top of it.
  fm<  e#   Push [U U'], where U' is U rotated one dimension to the left.
  \f.* e#   Push [U*X and U'*X], where * denotes the vectorized product.
  ::+  e#   Add the components of both products.
  0-   e#   Remove zeroes.
       e#   Push the logical NOT of the array.
},     e#   If the array was empty, keep the triplet.
,      e# Push X, the length of the filtered array.
__~)&  e# Push X & ~X + 1.
:T     e# Save the result in T and divide X by T.
'/     e# Push a slash.
@,T/   e# Dividet he length of the unfiltered array by T.

```
> 6 votes

---
Tags: code-golf, combinatorics, array, rational-numbers, probability-theory
---


title: Burrows, Wheeler and Back

text:
# Question
Title: Burrows, Wheeler and Back
### Background

The Burrows–Wheeler transform (BWT) is a reversible permutation of the characters of a string that results in large runs of similar characters for certain types of strings such as plain text. It is used, for example, in the bzip2 compression algorithm.

The BWT is defined as follows:

Given an input string such as `codegolf`, compute all possible rotations of it and sort them in lexicographical order:

```
codegolf
degolfco
egolfcod
fcodegol
golfcode
lfcodego
odegolfc
olfcodeg

```

The BWT of the string `codegolf` is the string consisting of the last character of each string in that order, i.e., the last column of the block above. For `codegolf`, this yields `fodleocg`.

By itself, this transformation isn't reversible, since the strings `codegolf` and `golfcode` result in the same string. However, if we know that the string ends with an `f`, there is only one possible preimage.

### Task

Implement an involutive program or function that reads a single string from STDIN or as command-line or function argument and prints or returns either the BWT or its inverse of the input string.

If the input string contains no spaces, your submission should append a single space to the input and compute the BWT.

If the input string already contains a space, it should compute the preimage of the BWT that has a trailing space and strip that space.

### Examples

```
INPUT:  ProgrammingPuzzles&CodeGolf
OUTPUT: fs&e grodllnomzomaiCrGgPePzu

```

```
INPUT:  fs&e grodllnomzomaiCrGgPePzu
OUTPUT: ProgrammingPuzzles&CodeGolf

```

```
INPUT:  bt4{2UK<({ZyJ>LqQQDL6!d,@:~L"#Da\6%EYp%y_{ed2GNmF"1<PkB3tFbyk@u0#^UZ<52-@bw@n%m5xge2w0HeoM#4zaT:OrI1I<|f#jy`V9tGZA5su*b7X:Xn%L|9MX@\2W_NwQ^)2Yc*1b7W<^iY2i2Kr[mB;,c>^}Z]>kT6_c(4}hIJAR~x^HW?l1+^5\VW'\)`h{6:TZ)^#lJyH|J2Jzn=V6cyp&eXo4]el1W`AQpHCCYpc;5Tu@$[P?)_a?-RV82[):[@94{*#!;m8k"LXT~5EYyD<z=n`Gfn/;%}did\fw+/AzVuz]7^N%vm1lJ)PK*-]H~I5ixZ1*Cn]k%dxiQ!UR48<U/fbT\P(!z5l<AefL=q"mx_%C:2=w3rrIL|nghm1i\;Ho7q+44D<74y/l/A)-R5zJx@(h8~KK1H6v/{N8nB)vPgI$\WI;%,DY<#fz>is"eB(/gvvP{7q*$M4@U,AhX=JmZ}L^%*uv=#L#S|4D#<
OUTPUT: <#Q6(LFksq*MD"=L0<f^*@I^;_6nknNp;pWPBc@<A^[JZ?\B{qKc1u%wq1dU%;2)?*nl+U(yvuwZl"KIl*mm5:dJi{\)8YewB+RM|4o7#9t(<~;^IzAmRL\{TVH<bb]{oV4mNh@|VCT6X)@I/Bc\!#YKZDl18WDIvXnzL2Jcz]PaWux[,4X-wk/Z`J<,/enkm%HC*44yQ,#%5mt2t`1p^0;y]gr~W1hrl|yI=zl2PKU~2~#Df"}>%Io$9^{G_:\[)v<viQqwAU--A#ka:b5X@<2!^=R`\zV7H\217hML:eiD2ECETxUG}{m2:$r'@aiT5$dzZ-4n)LQ+x7#<>xW)6yWny)_zD1*f @F_Yp,6!ei}%g"&{A]H|e/G\#Pxn/(}Ag`2x^1d>5#8]yP>/?e51#hv%;[NJ"X@fz8C=|XHeYyQY=77LOrK3i5b39s@T*V6u)v%gf2=bNJi~m5d4YJZ%jbc!<f5Au4J44hP/(_SLH<LZ^%4TH8:R

```

```
INPUT:  <#Q6(LFksq*MD"=L0<f^*@I^;_6nknNp;pWPBc@<A^[JZ?\B{qKc1u%wq1dU%;2)?*nl+U(yvuwZl"KIl*mm5:dJi{\)8YewB+RM|4o7#9t(<~;^IzAmRL\{TVH<bb]{oV4mNh@|VCT6X)@I/Bc\!#YKZDl18WDIvXnzL2Jcz]PaWux[,4X-wk/Z`J<,/enkm%HC*44yQ,#%5mt2t`1p^0;y]gr~W1hrl|yI=zl2PKU~2~#Df"}>%Io$9^{G_:\[)v<viQqwAU--A#ka:b5X@<2!^=R`\zV7H\217hML:eiD2ECETxUG}{m2:$r'@aiT5$dzZ-4n)LQ+x7#<>xW)6yWny)_zD1*f @F_Yp,6!ei}%g"&{A]H|e/G\#Pxn/(}Ag`2x^1d>5#8]yP>/?e51#hv%;[NJ"X@fz8C=|XHeYyQY=77LOrK3i5b39s@T*V6u)v%gf2=bNJi~m5d4YJZ%jbc!<f5Au4J44hP/(_SLH<LZ^%4TH8:R
OUTPUT: bt4{2UK<({ZyJ>LqQQDL6!d,@:~L"#Da\6%EYp%y_{ed2GNmF"1<PkB3tFbyk@u0#^UZ<52-@bw@n%m5xge2w0HeoM#4zaT:OrI1I<|f#jy`V9tGZA5su*b7X:Xn%L|9MX@\2W_NwQ^)2Yc*1b7W<^iY2i2Kr[mB;,c>^}Z]>kT6_c(4}hIJAR~x^HW?l1+^5\VW'\)`h{6:TZ)^#lJyH|J2Jzn=V6cyp&eXo4]el1W`AQpHCCYpc;5Tu@$[P?)_a?-RV82[):[@94{*#!;m8k"LXT~5EYyD<z=n`Gfn/;%}did\fw+/AzVuz]7^N%vm1lJ)PK*-]H~I5ixZ1*Cn]k%dxiQ!UR48<U/fbT\P(!z5l<AefL=q"mx_%C:2=w3rrIL|nghm1i\;Ho7q+44D<74y/l/A)-R5zJx@(h8~KK1H6v/{N8nB)vPgI$\WI;%,DY<#fz>is"eB(/gvvP{7q*$M4@U,AhX=JmZ}L^%*uv=#L#S|4D#<

```

```
INPUT:  aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OUTPUT: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

```

```
INPUT:  aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OUTPUT: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

```

### Additional rules

* You cannot use any built-in operators that compute the BWT (or its inverse) of a string.
* You cannot use any built-in operators that invert functions.
* Your code may print a trailing newline if you choose STDOUT for output, even if it doesn't support trailing newlines in the input.
* Your code has to work for any input of 500 or less printable ASCII characters (0x20 to 0x7E), including at most one space.
* For any of the possible inputs described above, your code must finish in under ten minutes on my machine (Intel Core i7-3770, 16 GiB RAM). The last test case should be the slowest, so make sure you time your code with that one.

For most languages and approaches, it should be easy to comply with the time limit. This rule is solely meant to prevent implementing either transform as a brute-force inverse of the other.
* Standard code golf rules apply. The shortest submission in bytes wins.

# Answer
# Pyth, 29 bytes

```
?tthu+VzSGzz}dzseMS.>L+z\ hlz

```

Demonstration. Test harness.

This straightforwardly divides into an encoding and decoding segment, with the code deciding which one to use with a ternary.

```
?tthu+VzSGzz}dzseMS.>L+z\ hlz
                                 Implicit:
                                 z = input()
                                 d = ' '

?           }dz                  If there is a space in the input,
    u     zz                     Update G to the result of the following,
                                 with G starting as z and repeating len(z) times:
     +V                          The vectorized sum of
       zSG                       z and sorted(G)
   h                             Take the first such result, which will consist of
                                 the first character of z followed by the
                                 first cyclic permuation of the pre-BWT string,
                                 which must start with ' '.
 tt                              Remove the first two characters and return.
                 L               Otherwise, left-map (map with the variable as the
                                 left parameter and a constant as the right)
               .>                cyclic right shift
                  +z\            of z + ' '
                      hlz        over range(len(z)+1)
              S                  Sort the shifted strings,
            eM                   take their last charactes,
           s                     combine into one string and return.

```
> 9 votes

# Answer
# CJam, ~~41~~ ~~36~~ 35 bytes

```
q:XS&LX,{X\.+$}*0=1>XS+_,,\fm<$zW>?

```

Test it here.

## Explanation

```
q:X   e# Read STDIN and store it in X.
S&    e# Take the set intersection with " ". We'll use this as a truthy/falsy value to
      e# select the correct output later.

# Compute the iBWT:
LX,   e# Push an empty array, compute the length of X.
{     e# Run the following block that many times:
  X\  e# Push X and pull the other array on top.
  .+  e# Add the characters of X to the corresponding line of the other array,
      e# i.e. prepend X as a new column.
  $   e# Sort the rows.
}*
0=    e# Since we just sorted the rows, the first permutation of the output will be
      e# one starting with a space, followed by the string we actually want. So just
      e# pick the first permutation.
1>    e# Remove the leading space.

# Compute the BWT:
XS+   e# Push X and append a space.
_,    e# Get that string's length N.
,\    e# Turn it into a range [0 .. N-1], swap it with the string.
fm<   e# Map each value in the range to the string shifted left by that many characters.
$     e# Sort the permutations.
zW>   e# Transpose the grid and discard all lines but the last.

?     e# Choose between the iBWT and the BWT based on whether the input had a space.

```
> 6 votes

# Answer
# Perl 5, 179

Another not-so-good one from me. There are probably some gains to be had in this one, but it's not going to compete with the purpose-built golf languages.

```
$_=<>;@y=/./g;if(/ /){@x=sort@y;for(1..$#y){@x=sort map$y[$_].$x[$_],0..$#x}
say$x[0]=~/^ (.*)/}else{push@y," ";say map/(.)$/,sort map{$i=$_;join"",
map$y[($_+$i)%@y],0..$#y}0..$#y}

```

Un-golfed:

```
# Read input
$_ = <>;
# Get all the chars of the input
my @chars = /./g;

if (/ /) {
  # If there's a space, run the IBWT:
  # Make the first column of the table
  my @working = sort @chars;

  # For each remaining character
  for (1 .. $#chars) {
    # Add the input as a new column to the left of @working,
    # then sort @working again
    @working = sort map {
      $chars[$_] . $working[$_]
    } 0 .. $#working;
  }
  # Print the first element of @working (the one beginning with space), sans space
  say $working[0] =~ /^ (.*)/;
} else {
  # BWT
  # Add a space to the end of the string
  push @chars, " ";
  # Get all the rotations of the string and sort them
  @rows = sort map {
    my $offset = $_;
    join "", map {
      $chars[($_ + $offset) % @chars]
    } 0 .. $#chars
  } 0 .. $#chars;

  # Print all the last characters
  say map /(.)$/, @rows;
}

```
> 2 votes

---
Tags: code-golf, string, sorting, compression
---


title: Compact XML Parser

text:
# Question
Title: Compact XML Parser
**Goal:**

The goal of this challenge is to take a simple 6 row by 6 column XML file (without the standard XML header) and parse it out so that the program can return the value of a cell given it's coordinates.

The entry with the shortest overall length by language and overall will be declared the winner.

**Additional information:**

The XML syntax will always be an HTML table with each inner level being indented by four single spaces. You may assume that every file put into the program will be exactly like the one given below.

If your program uses imports you do not need to include them in the golfed version of your code but you must submit a copy of the program in the explanation that shows all imports used. This explanation will not effect your entries byte count.

**Rules:**

* The XML file cannot be hardcoded
* XML libraries/functions cannot be used

**Extra Credit:**

* Can pretty print the table if given the `--all` flag (20 bytes off of total)
* Can print all entries of a column given the column number in `--col=number` (20 bytes off of total)
* Can print all entries of a row given the row number in `--row=number` (20 bytes off of total)
* Can parse any size file as long as #rows = #columns (40 bytes off of total)

**XML File:**

```
<table>
    <tr>
        <th>Foo</th>
        <th>Bar</th>
        <th>Baz</th>
        <th>Cat</th>
        <th>Dog</th>
        <th>Grinch</th>
    </tr>
    <tr>
        <th>Something</th>
        <th>Something</th>
        <th>Darkside</th>
        <th>Star</th>
        <th>Wars</th>
        <th>Chicken</th>
    </tr>
    <tr>
        <th>Star</th>
        <th>Trek</th>
        <th>Xbox</th>
        <th>Words</th>
        <th>Too</th>
        <th>Many</th>
    </tr>
    <tr>
        <th>Columns</th>
        <th>Not</th>
        <th>Enough</th>
        <th>Words</th>
        <th>To</th>
        <th>Fill</th>
    </tr>
    <tr>
        <th>Them</th>
        <th>So</th>
        <th>I</th>
        <th>Will</th>
        <th>Do</th>
        <th>My</th>
    </tr>
    <tr>
        <th>Best</th>
        <th>To</th>
        <th>Fill</th>
        <th>Them</th>
        <th>All</th>
        <th>Up</th>
    </tr>
</table>

```

# Answer
> 2 votes
# JavaScript (*ES6*), 158 bytes

A function, parameters:

* xml
* row number (1 to n)
* col number (1 to n or 0 to get the whole row as an array)

It works with an xml string with any number of rows and columns (formatted as in the example, no extra tags inside rows or cells).

I don't claim any bonus as the input mode is not what requested (--row=, etc)

Using this same expression in any language that implements regexps (perl maybe) you can have a stand-alone program.

Test running the snipper below (ES6 so Firefox only)

```
F=(t,r,c)=>(
  m=t.match(RegExp(`(<tr>(\\s*<th>(.*?)</th>\\s*){${c}}[\\s\\S]*?</tr>\\s*){${r}}`,"i")),
  c?m[3] // single cell
  :m[1].split(/<th>(.*?)<\/th>/g).filter((v,i)=>i&1) // clean row value
)

// test

function test()
{
  var r=+R.value, c=+C.value, t=T.value
  X.value=F(t,r,c)
}
```

```
#X { width: 440px; }
#T { width: 440px; height: 10em; }
#R,#C { width: 3em; }
```

```
Row: <input id=R value=1> (1 ... n)
Col: <input id=C value=1> (1...n, 0 for whole row)
<button onclick="test()">Get</button>
<br><input readonly id=X>
<br>Xml:<br>
<textarea id=T><table>
    <tr>
        <th>Foo</th>
        <th>Bar</th>
        <th>Baz</th>
        <th>Cat</th>
        <th>Dog</th>
        <th>Grinch</th>
    </tr>
    <tr>
        <th>Something</th>
        <th>Something</th>
        <th>Darkside</th>
        <th>Star</th>
        <th>Wars</th>
        <th>Chicken</th>
    </tr>
    <tr>
        <th>Star</th>
        <th>Trek</th>
        <th>Xbox</th>
        <th>Words</th>
        <th>Too</th>
        <th>Many</th>
    </tr>
    <tr>
        <th>Columns</th>
        <th>Not</th>
        <th>Enough</th>
        <th>Words</th>
        <th>To</th>
        <th>Fill</th>
    </tr>
    <tr>
        <th>Them</th>
        <th>So</th>
        <th>I</th>
        <th>Will</th>
        <th>Do</th>
        <th>My</th>
    </tr>
    <tr>
        <th>Best</th>
        <th>To</th>
        <th>Fill</th>
        <th>Them</th>
        <th>All</th>
        <th>Up</th>
    </tr>
</table></textarea>
```

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


title: Pushing items in the sequence

text:
# Question
Title: Pushing items in the sequence
# Aim

If you are given a sequence such as `(A, G, M, _, _, C, D, _, G)` your aim is to push all non empty elements to one side to get `(A, G, M, C, D, G, _, _, _)`. You must preserve the order of the non-empty elements.

# Rules

1. You are free to choose the sequence type. (strings, numbers, containers etc). You must also choose a Nil/None/Null character or element that will fit your sequence type. eg; spaces or underscores inside a string.
2. User should be able to input the push direction (left or right) and the sequence. Input values and format are up to you to choose. eg; Your code handles sequences that are numbers with `7` as the null character. You set `R` for right, `L` for left. So user inputs `R, 1577462722727777`. The result is `7777777715462222`
3. Rearranged sequence should be displayed or written to a file.
4. Your code should not exceed 128 bytes.

# Points

1. **+(10 / bytes)** golfing points
2. **+1** for Moses-Mode. Push half the elements to the left, and half to the right. If odd number of items are present, you may choose the direction of the final element. eg; `(A, G, M, _, _, _, C, D, G)`

*You may use use this calculator to round your points to the hundredth decimal place.*

# Answer
# R - 10 / ~~71~~ ~~70~~ ~~66~~ 39 bytes = 0.26 points

Saved **27 bytes** thanks to Mickey!

```
function(d,s)s[order(xor(!is.na(s),d))]

```

This creates an unnamed function which takes a direction `d` (logical with `TRUE` corresponding to right and `FALSE` to left (legit per OP's comment)) and a vector `s` (assumed to use `NA` for empty elements) as input and returns a vector. To call it, give it a name, e.g. `f=function(d,s)...`.

This does not support "Moses Mode."

Ungolfed + explanation:

```
f <- function(d, s) {
    # Order the elements of s by non-missing exclusive or direction
    s[order(xor(!is.na(s), d))]
}

```

Examples:

```
> test <- c(1, 5, NA, NA, 4, 6, 2, NA, 2, 2, NA, 2, NA, NA, NA, NA)
> f(FALSE, test)
[1] NA NA NA NA NA NA NA NA  1  5  4  6  2  2  2  2
> f(TRUE, test)
[1]  1  5  4  6  2  2  2  2 NA NA NA NA NA NA NA NA

```

And an extra special example just for FryAmTheEggman:

```
> c(f(TRUE, test), "BATMAN")
[1] "1" "5" "4" "6" "2" "2" "2" "2" NA NA NA NA NA NA NA NA "BATMAN"

```
> 6 votes

# Answer
# Pyth, 10 / ~~15~~ 14 bytes + 1 = 1.71 points

```
s@.pac2-zd@dzQ

```

This takes two lines of input. The first one is a string (spaces are the special characters) and the second one is `0` (push all spaces to the right), `1` (Moses-mode) or `4` (push all spaces to the left).

Try it online: Demonstration

Thanks to @isaacg for saving one byte

### Explanation:

```
                 implicit: z = input string, Q = input number
       -zd       remove all spaces from z
     c2          split into 2 equal pieces
    a            append
          @dz    get all spaces in z
  .p             create all permutation of the 3 strings
 @           Q   choose the Qth permutation
s                and join the strings

```

# Pyth, 10 / 7 bytes = 1.43 points

```
oqQqNdz

```

Input format: string on first line, and `0` (push spaces to the left) or `1` (push spaces to the right) on second line.

Try it online: Demonstration

This is worth less points, but it's a quite simple and elegant solution.

### Explanation:

```
          implicit: z = input string, Q = input number
o     z   order the chars N of z by the key:
 qQqNd       Q == (N == " ")

```

When `Q == 0` all spaces get the key `0` and all other chars get the key `1`, otherwise it's exactly opposite. Then the string is sorted by their keys. Since sorting is stable in Pyth, it sorts all spaces either to the beginning or the end and keeps all other chars in the same order.
> 4 votes

# Answer
# Haskell 10/24 bytes = 0.42 points

```
import Data.List
(.sort)

```

Sadly the `sort` function is in `Data.List`, so I have to import it.

The sequence type is boolean values, i.e. `True` or `False`. The empty value is `False`. Pushing non empty values to the right is indicated by `id` and to the left by `reverse`.

Example usage:

```
*Main> (.sort) id [True,False,False,True,False,True]
[False,False,False,True,True,True]
*Main> (.sort) reverse [True,False,False,True,False,True]
[True,True,True,False,False,False]

```
> 4 votes

# Answer
I honestly don't mind that the challenge has a byte limit. It is the OP's choice to impose that restriction to make things more interesting. However, just to represent how a "wordy" language would do, here's java:

# Java

**283 bytes = 0.04points + 1 = 1.04**

```
enum E{;public static void main(String[]r){String s="",t=r[0].substring(1),d="_";char p=r[0].charAt(0);for(;t.indexOf(d)>=0;){r=t.split(d,2);t=r[0]+r[1];s+=d;}int x=(t.length()-1)/2;if(p=='L')t+=s;else if(p=='R')t=s+t;else t=t.substring(0,x)+s+t.substring(x+1);System.out.print(t);}}

```

Input is from the command line. The first character can be L for left, R for right, anything else for moses mode. Underscore is used for the null character.

If I remove the moses mode code, I get:

**207 bytes = 0.05points**

```
enum E{;public static void main(String[]r){String s="",t=r[0].substring(1),d="_";char p=r[0].charAt(0);for(;t.indexOf(d)>=0;){r=t.split(d,2);t=r[0]+r[1];s+=d;}if(p=='L')t+=s;else t=s+t;System.out.print(t);}}

```

Input is from the command line. L is left, anything else is right. Underscore is null.

I quite enjoyed the challenge of trying to fit Java code inside 128 bytes. Java just isn't a competitive language for codegolfs though.
> 4 votes

# Answer
# k,10/12 = 0.83 points

```
{x((>:;<:)y)x}

```

It takes an array of booleans and a 0 or 1 to say to push to the right or the left.

```
k){x((>:;<:)y)x}[1011110101101b;0]
1111111110000b
k){x((>:;<:)y)x}[1011110101101b;1]
0000111111111b

```

# k, 10/29 = 0.34 points

A more flexible version that should work for all input types and which allows you to choose the null character.

```
{x@,/$[~z;|:;](&~:;&:)@\:x=y}

```

.

```
k){x@,/$[~z;|:;](&~:;&:)@\:x=y}[1 0 3 6 5 6 0 6 0;6;0]
6 6 6 1 0 3 5 0 0
k){x@,/$[~z;|:;](&~:;&:)@\:x=y}[1 0 3 6 5 6 0 6 0;6;1]
1 0 3 5 0 0 6 6 6
k){x@,/$[~z;|:;](&~:;&:)@\:x=y}[1 0 3 6 5 6 0 6 0;0;1]
1 3 6 5 6 6 0 0 0
k){x@,/$[~z;|:;](&~:;&:)@\:x=y}["abc def ghi";" ";1]
"abcdefghi  "
k){x@,/$[~z;|:;](&~:;&:)@\:x=y}["abc def ghi";" ";0]
"  abcdefghi"

```
> 2 votes

# Answer
# Pyth - 10 / 1 byte + 1 = 11

Really cheaty, but it seems allowed, basically puts all the code in the options. Doing bonus now.

It takes an array of ints, with `0` as falsey.

The left value is: `Y.append(eval(input())) or [i for i in Y[0] if i] + [0]*Y[0].count(0)`

The right value is: `Y.append(eval(input())) or [0]*Y[0].count(0) + [i for i in Y[0] if i]`

The Moses value is: `Y.append(eval(input())) or Y.append(chop(2, [i for i in Y[0] if i])) or Y[1][0] + [0]*Y[0].count(0) + Y[1][1]`

So here is the code:

```
Q

```

Because of security reasons it only works locally, not online.

## Old, non-cheaty one - 0.83:

Not going for the bonus, takes array of ints, `0` is falsey, and `1` for right, `-1` for left.

```
Ms%H,fTGf!TG

```

Explanation coming soon.

```
M           Two var lambda
 s          Join the two parts of the array
  %         String slice step, reverses if -1, unchanged if 1
   H        Second arg
   ,        Two element list
    fTG     Filter arg 1 for truthiness
    f!TG    Filter arg 1 for falsiness

```

Try it here online.
> 1 votes

# Answer
# R 10 / 69 + 1 = 1.14

Not very pretty. An unnamed function where d is a either 0 (left), 1 (right) or .5 (Moses). s is a vector of integers where 0 as the null.

```
function(d,s)c(rep(0,(l=length(s[!s]))*(1-d)),s[!!s],rep(0,(l*d)+.5))

```

Test example

```
> g=function(d,s)c(rep(0,(l=length(s[!s]))*(1-d)),s[!!s],rep(0,(l*d)+.5))
> test=c(17,0,2,42,2,4,35,0,0,45,0,2,0,7,9)
> g(0,test)
 [1]  0  0  0  0  0 17  2 42  2  4 35 45  2  7  9
> g(1,test)
 [1] 17  2 42  2  4 35 45  2  7  9  0  0  0  0  0
> g(.5,test)
 [1]  0  0 17  2 42  2  4 35 45  2  7  9  0  0  0
> test=c(17,0,2,42,0,2,4,35,0,0,45,0,2,0,7,9)
> g(0,test)
 [1]  0  0  0  0  0  0 17  2 42  2  4 35 45  2  7  9
> g(1,test)
 [1] 17  2 42  2  4 35 45  2  7  9  0  0  0  0  0  0
> g(.5,test)
 [1]  0  0  0 17  2 42  2  4 35 45  2  7  9  0  0  0
>

```
> 1 votes

# Answer
## CoffeeScript, 172 bytes = 1.06 points

```
x=(m,d)->c='concat';l='length';s=d.filter((el)->el);z=new Array(d[l]-s[l]).fill 0;(Array.prototype.splice.apply(s,[d[l]/4,0][c] z);return s)if!m--;return z[c] s if!m;s[c] z

```

First parameter is mode: 0 (or false) for Moses mode, 1 for push right (prepend), 2 for push left (append)

Second parameter is an array of integers where 0 is considered the empty token (though all falsy values are considered empty, but will be replaced with 0).

### Version without Moses mode: 91 bytes = 0.11 points

```
x=(d,a)->o=a.filter((l)->''!=l);o[if d then'push'else'unshift'] ''while a.length-o.length;o

```

First parameter is a Boolean indicating whether to push right (`true` or any truthy value) or push left (`false` or any falsy value).

Second parameter is the array. Empty tokens include empty strings.
> 1 votes

# Answer
## JavaScript (ES6) - 168 bytes, 1.06 points

```
x=(d,a)=>{c='concat',l='length',o=a.filter(l=>l),z=new Array(a[l]-o[l]).fill(0);if(!d)Array.prototype.splice.apply(o,[a[l]/4,0][c](z));return d?(d>1?z[c](o):o[c](z)):o}

```

Input:

* 0 (or any falsy value) for Moses mode, 1 for push left, 2 for push right
* Array of integers in second parameter, 0 considered empty

### Unminified code

```
x = (mode, data) => {
    var concat = 'concat',
        length = 'length',
        stripped = data.filter(el => {
            return !!el;
        }),
        zeroes = new Array(data[length] - stripped[length]).fill(0);

    if (!mode) {
        Array.prototype.splice.apply(stripped, [data[length] / 4, 0][concat](zeroes));
    }

    return mode ? (mode > 1 ? zeroes[concat](stripped) : stripped[concat](zeroes)) : stripped;
};

```
> 1 votes

# Answer
## PHP - 176 bytes, 1.06 points

```
function x($m,$d){$c=count;$y=array_merge;$s=array_filter($d);$z=array_fill(0,$c($d)-$c($s),0);if(!$m)array_splice($s,$c($s)/4+1,0,$z);return!$m?$s:(--$m?$y($z,$s):$y($s,$z));}

```

Where `$m` is:

* 0: Moses mode
* 1: Append (push left)
* 2: Prepend (push right)

And `$d` is the an array of numeric where 0 or 0.0 is considered empty.

There are notices for undefined constants but they still work.
> 1 votes

# Answer
# rs, 41 bytes

```
+(.)(\d+)_(\d+)/\1_\2\3
l(_+)(.+)/\2\1
r/

```

Takes input as a sequence of numbers, with `l` for left, `r` for right, and the underscore as the null character, e.g. `r_3_12`.

Live demo here.
> 1 votes

# Answer
# k2, 28 bytes

```
{,/ :[y;|:](x@&~x=0;x@&x=0)}

```

I already have another answer, and there's another K answer (for k3), but I believe this one uses a vastly different approach, IMO. 0 is used as the null value. Two unfortunate issues:

1. k2 has no binary vectors.
2. #1 makes this one *really* long.

Usage:

```
{,/ :[y;|:](x@&~x=0;x@&x=0)}[1 1 0 1 2 3 0 1;1] / outputs 0 0 1 1 1 2 3 1
{,/ :[y;|:](x@&~x=0;x@&x=0)}[1 1 0 1 2 3 0 1;0] / outputs 1 1 1 2 3 1 0 0

```

Now, if I am allowed to use just 1 and 0 as my input, I can get much shorter, but then it ends up being almost the same thing as the other K answer. So...yeah. This sucks. :(
> 1 votes

# Answer
> Some have mentioned above that wordy languages can't participate because of the restriction in byte count. I doubt it. Here's a python solution, and I think python is a wordy language, somewhat golfed.

# Python 2.7

### 68 bytes, 0.15 points

### 62 bytes, 0.16 points (thanks to @Sp3000)

```
d,s=input();e=filter(None,s),[0]*s.count(0)
print e[d]+e[d+1]

```

### input/ouput

```
0 for right, -1 for left, list of numbers as sequence. 0 is the null character
>>>0, [1, 0, 2, 3, 6, 0, 0, 0, 5]
[1, 2, 3, 6, 5, 0, 0, 0, 0]
>>>-1, [1, 0, 2, 3, 6, 0, 0, 0, 5]
[0, 0, 0, 0, 1, 2, 3, 6, 5]

```
> 0 votes

# Answer
# Perl - 103 bytes, 1.09 points

```
$_=<>;s/\n//;$b='_'x s/_//g;$x=length($_)/2;print(($b.$_,$_.$b,(substr($_,0,$x).$b.substr$_,$x))[<>+0])

```

The sequence is a string. The null element is an underscore character. It reads the string as a line from the standard input, then reads the direction as another line: `0` for right, `1` for left, `2` for Moses mode.

## Version without Moses Mode - 49 bytes, 0.20 points

```
$_=<>;s/\n//;$b='_'x s/_//g;print<>+0?$_.$b:$b.$_

```

Same as the above except shorter and without Moses mode implemented.
> 0 votes

---
Tags: code-golf
---


title: Coding hex board game

text:
# Question
Title: Coding hex board game
# Introduction

Hex is a strategy board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Other popular dimensions are 13×13 and 19×19 as a result of the game's relationship to the older game of Go. According to the book A Beautiful Mind, John Nash (one of the game's inventors) advocated 14×14 as the optimal size.

# Game Rules

Each player has an allocated color, conventionally Red and Blue or White and Black. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal for each player is to form a connected path of their own stones linking the opposing sides of the board marked by their colors, before their opponent connects his or her sides in a similar fashion. The first player to complete his or her connection wins the game. The four corner hexagons each belong to both adjacent sides.

# Coding Rules

1. You may use any program or language. Do not use any third party libraries or modules (full or in part) that implements the same game. The rest are fine.
2. Players are computer and user.
3. You may choose the size of the grid.
4. You may use either CLI or GUI for output (see points).
5. Your code should not exceed 5120 bytes.

# Points

* **+(5120 - bytes) / 100** golfing points
* **+50** points for making GUI
* **+50** for two player mode
* **+75** for best-move-prediction**#**
* **+50** for undo-move

**#** Tell the user, if they wish, their next best move.

# Super bot challenge

* **+150** points if your bot is undefeatable. Add this points ONLY IF you are absolutely certain of your bot's 100% winning capability. If any user defeats your bot and reports it all your points will be taken away (zero points). The person reporting this must either post a screenshot or input sequences based on the implementation of game. **They will be awarded +150 points, if they have posted an answer.**

# Answer
# HTML5 and JavaScript, 12.72 + 50 + 50 + 50 = 162.72 points

Hi, this is my very first code golf, but I think, the following code works quite well (it's a full HTML page, 3848 bytes).

```
<html><head><meta charset="utf-8"><title>Hex</title><script type="text/javascript">var r=20;var w=r*2*(Math.sqrt(3)/2);var ctx;var s=[-1,-1];var b=new Array(14);var h=[];var p=0;var m=false;var t=true;function H(c,x,y,r){c.beginPath();c.moveTo(x,y-r);for(var i=0;i<6;i++)c.lineTo(x+r*Math.cos(Math.PI*(1.5+1/3*i)),y+r*Math.sin(Math.PI*(1.5+1/3*i)));c.closePath();c.fill();c.stroke();}function P(c,p){c.lineWidth=10;c.beginPath();c.moveTo((p[0][0]+p[0][1])*w-(p[0][1]-4)*(w/2),(p[0][1]+2)*1.5*r);for(var i=1;i<p.length;i++)c.lineTo((p[i][0]+p[i][1])*w-(p[i][1]-4)*(w/2),(p[i][1]+2)*1.5*r);c.stroke();}function S(e){var l=ctx.getImageData(e.clientX-20,e.clientY,1,1).data;l[0]-=l[2]==38||l[2]==178 ? 241 : 0;l[1]-=l[2]==178 ? 220 : (l[2]==38 ? 0 : 140);if(l[0]>=0&&l[0]<=13&&l[1]>=0&&l[1]<=13&&(l[2]==38||l[2]==171||l[2]==178))s=[l[0],l[1]];else s=[-1,-1];}function Ai(){var pos;do pos=[Math.floor(Math.random()*14),Math.floor(Math.random()*14)];while(b[pos[0]][pos[1]]!=-1);h.push([pos[0],pos[1],1]);b[pos[0]][pos[1]]=1;}function Fa(a,d){for(var i=0;i<a.length;i++)if(JSON.stringify(a[i])==JSON.stringify(d))return i;return -1;}function C(x,y,c,o,s){var a=[-1,0,1,0,0,-1,0,1,1,-1,-1,1];var r=[];for(var i=0;i<6;i++)if(x+a[i*2]>=0&&x+a[i*2]<14&&y+a[i*2+1]>=0&&y+a[i*2+1]<14)if(b[x+a[i*2]][y+a[i*2+1]]==c&&Fa(o,[x+a[i*2],y+a[i*2+1]])==-1&&Fa(s,[x+a[i*2],y+a[i*2+1]])==-1)r.push([x+a[i*2],y+a[i*2+1]]);return r;}function W(c){var o=[],op=[],s=[],sp=[];for(var a=0;a<14;a++){if(b[c==0?a:0][c==0?0:a]==c){o.length=op.length=s.length=sp.length=0;var pf=false;o.push([c==0?a:0,c==0?0:a]);op.push(-1);while(o.length>0){var u=o[0];o.splice(0,1);var uI=op.splice(0,1);s.push(u);sp.push(uI);if(u[c==0?1:0]==13){pf=true;break;}var n=C(u[0],u[1],c,o,s);for(var i=0;i<n.length;i++){o.push(n[i]);op.push(s.length-1);}}if(pf){var p=[];var u=s.length-1;while(sp[u]!=-1){p.push(s[u]);u=sp[u];}p.push([c==0?a:0,c==0?0:a]);p.reverse();t=false;return p;}}}return false;}function Md(e){S(e);if(t){if(s[0]!=-1&&s[1]!=-1){h.push([s[0],s[1],p]);b[s[0]][s[1]]=p;if(m)p=p==0 ? 1 : 0;else Ai();D();var p0=W(0),p1=W(1);if(p0!=false){P(ctx,p0);alert((m?"The red player":"You")+" won!");}else if(p1!=false){P(ctx,p1);alert((m?"The blue player":"The computer")+" won!");}}}}function Mm(e){S(e);if(t)D();}function D(){ctx.clearRect(0,0,850,600);ctx.lineWidth=1;ctx.fillStyle="rgb(0,154,172)";ctx.beginPath();ctx.moveTo(w*15.65,r);ctx.lineTo(w*23.5,24.5*r);ctx.lineTo(0,r);ctx.lineTo(w*7.85,24.5*r);ctx.closePath();ctx.fill();ctx.fillStyle="rgb(255,0,39)";ctx.beginPath();ctx.moveTo(0,r);ctx.lineTo(w*15.65,r);ctx.lineTo(w*7.85,24.5*r);ctx.lineTo(w*23.5,24.5*r);ctx.closePath();ctx.fill();var num=0;ctx.strokeStyle="white";for(var y=0;y<14;y++){for(var x=0;x<14;x++){if(b[x][y]==0)ctx.fillStyle="rgb(255,0,39)";else if(b[x][y]==1)ctx.fillStyle="rgb(0,154,172)";else if(x==s[0]&&y==s[1])ctx.fillStyle="rgb("+(x+(p==0?241:0))+","+(y+(p==0?0:140))+","+(p==0?38:171)+")";else ctx.fillStyle="rgb("+(x+241)+","+(y+220)+",178)";H(ctx,(x+y)*w-(y-4)*(w/2),(y+2)*1.5*r,r);num++;}}}function Mp(){m=!m;p=0;I();}function U(){if(t){var a;if(h.length>0){a=h[h.length-1];b[a[0]][a[1]]=-1;h.pop();}if(!m){a=h[h.length-1];b[a[0]][a[1]]=-1;h.pop();}p=a[2];D();}}function I(){for(var i=0;i<14;i++){b[i]=new Array(14);for(var j=0;j<14;j++)b[i][j]=-1;}history.length=0;t=true;D();}function L(){var a=document.getElementById("o");ctx=a.getContext("2d");document.getElementById("mp").checked=false;a.onmousedown=Md;a.onmousemove=Mm;I();}</script></head><body onload="L()"><canvas style="position:absolute;top:0px;left:20px" width="850" height="600" id="o"></canvas><div style="position:absolute;top:250px;left:20px"><input type="button" onClick="I()" value="New game"><br><br>Multiplayer: <input id="mp" type="checkbox" onClick="Mp()"><br><input type="button" onClick="U()" value="Undo"></div></body></html>
```

**Expanded**

```
<html>
<head>
    <meta charset="utf-8">
    <title>Hex</title>
    <script type="text/javascript">
        var r = 20;
        var w = r*2*(Math.sqrt(3)/2);
        var ctx;
        var sel = [-1, -1];
        var board = new Array(14);
        var hist = [];
        var player = 0;
        var multiplayer = false;
        var active = true;

        function drawHexagon(c, x, y, r)
        {
            c.beginPath();
            c.moveTo(x, y-r);
            for(var i=0; i<6; i++)
                c.lineTo(x+r*Math.cos(Math.PI*(1.5+1/3*i)), y+r*Math.sin(Math.PI*(1.5+1/3*i)));
            c.closePath();
            c.fill();
            c.stroke();
        }

        function drawPath(c, p)
        {
            c.lineWidth = 10;
            c.beginPath();
            c.moveTo((p[0][0]+p[0][1])*w - (p[0][1]-4)*(w/2), (p[0][1]+2)*1.5*r);
            for(var i=1; i<p.length; i++)
                c.lineTo((p[i][0]+p[i][1])*w - (p[i][1]-4)*(w/2), (p[i][1]+2)*1.5*r);
            c.stroke();
        }

        function getSel(e)
        {
            var color = ctx.getImageData(e.clientX-20, e.clientY, 1, 1).data;
            color[0] -= color[2]==38||color[2]==178 ? 241 : 0;
            color[1] -= color[2]==178 ? 220 : (color[2]==38 ? 0 : 140);
            if(color[0] >= 0  &&  color[0] <= 13  &&  color[1] >= 0  &&  color[1] <= 13  &&  (color[2] == 38  ||  color[2] == 171  ||  color[2] == 178))
                sel = [color[0], color[1]];
            else
                sel = [-1, -1];
        }

        function aiMove()
        {
            var pos;
            do
                pos = [Math.floor(Math.random()*14), Math.floor(Math.random()*14)];
            while(board[pos[0]][pos[1]] != -1);
            hist.push([pos[0],pos[1],1]);
            board[pos[0]][pos[1]] = 1;
        }

        function findArr(a, b)
        {
            for(var i=0; i<a.length; i++)
                if(JSON.stringify(a[i]) == JSON.stringify(b))
                    return i;
            return -1;
        }

        function getConnections(x, y, c, open, closed)
        {
            var a = [-1, 0, 1, 0, 0, -1, 0, 1, 1, -1, -1, 1];
            var ret = [];
            for(var i=0; i<6; i++)
                if(x+a[i*2] >= 0  &&  x+a[i*2] < 14  &&  y+a[i*2+1] >= 0  &&  y+a[i*2+1] < 14)
                    if(board[x+a[i*2]][y+a[i*2+1]] == c  &&  findArr(open, [x+a[i*2],y+a[i*2+1]]) == -1  &&  findArr(closed, [x+a[i*2],y+a[i*2+1]]) == -1)
                        ret.push([x+a[i*2],y+a[i*2+1]]);
            return ret;
        }

        function checkWin(c)
        {
            var open = [], openPrev = [], closed = [], closedPrev = [];
            for(var a=0; a<14; a++)
            {
                if(board[c==0?a:0][c==0?0:a] == c)
                {
                    open.length = openPrev.length = closed.length = closedPrev.length = 0;
                    var pathFound = false;
                    open.push([c==0?a:0, c==0?0:a]);
                    openPrev.push(-1);
                    while(open.length > 0)
                    {
                        var u = open[0];
                        open.splice(0, 1);
                        var uI = openPrev.splice(0, 1);
                        closed.push(u);
                        closedPrev.push(uI);
                        if(u[c==0?1:0] == 13)
                        {
                            pathFound = true;
                            break;
                        }
                        var connections = getConnections(u[0], u[1], c, open, closed);
                        for(var i=0; i<connections.length; i++)
                        {
                            open.push(connections[i]);
                            openPrev.push(closed.length-1);
                        }
                    }
                    if(pathFound)
                    {
                        var path = [];
                        var u = closed.length-1;
                        while(closedPrev[u] != -1)
                        {
                            path.push(closed[u]);
                            u = closedPrev[u];
                        }
                        path.push([c==0?a:0, c==0?0:a]);
                        path.reverse();
                        active = false;
                        return path;
                    }
                }
            }
            return false;
        }

        function mouseDown(e)
        {
            getSel(e);
            if(active)
            {
                if(sel[0] != -1  &&  sel[1] != -1)
                {
                    hist.push([sel[0],sel[1],player]);
                    board[sel[0]][sel[1]] = player;
                    if(multiplayer)
                        player = player==0 ? 1 : 0;
                    else
                        aiMove();
                    draw();
                    var p0 = checkWin(0), p1 = checkWin(1);
                    if(p0 != false)
                        { drawPath(ctx, p0); alert((multiplayer?"The red player":"You") + " won!"); }
                    else if(p1 != false)
                        { drawPath(ctx, p1); alert((multiplayer?"The blue player":"The computer") + " won!"); }
                }
            }
        }

        function mouseMove(e)
        {
            getSel(e);
            if(active)
                draw();
        }

        function draw()
        {
            ctx.clearRect(0, 0, 850, 600);
            ctx.lineWidth = 1;

            ctx.fillStyle = "rgb(0,154,172)";
            ctx.beginPath();
            ctx.moveTo(w*15.65, r);
            ctx.lineTo(w*23.5, 24.5*r);
            ctx.lineTo(0, r);
            ctx.lineTo(w*7.85, 24.5*r);
            ctx.closePath();
            ctx.fill();

            ctx.fillStyle = "rgb(255,0,39)";
            ctx.beginPath();
            ctx.moveTo(0, r);
            ctx.lineTo(w*15.65, r);
            ctx.lineTo(w*7.85, 24.5*r);
            ctx.lineTo(w*23.5, 24.5*r);
            ctx.closePath();
            ctx.fill();

            var num = 0;
            ctx.strokeStyle = "white";
            for(var y=0; y<14; y++)
            {
                for(var x=0; x<14; x++)
                {
                    if(board[x][y] == 0)
                        ctx.fillStyle = "rgb(255,0,39)";
                    else if(board[x][y] == 1)
                        ctx.fillStyle = "rgb(0,154,172)";
                    else if(x == sel[0]  &&  y == sel[1])
                        ctx.fillStyle = "rgb(" + (x+(player==0?241:0)) + "," + (y+(player==0?0:140)) + "," + (player==0?38:171) + ")";
                    else
                        ctx.fillStyle = "rgb(" + (x+241) + "," + (y+220) + ",178)";
                    drawHexagon(ctx, (x+y)*w - (y-4)*(w/2), (y+2)*1.5*r, r);
                    num++;
                }
            }
        }

        function chgMP()
        {
            multiplayer = !multiplayer;
            player = 0;
            init();
        }

        function undo()
        {
            if(active)
            {
                var a;
                if(hist.length > 0)
                {
                    a = hist[hist.length-1];
                    board[a[0]][a[1]] = -1;
                    hist.pop();
                }
                if(!multiplayer)
                {
                    a = hist[hist.length-1];
                    board[a[0]][a[1]] = -1;
                    hist.pop();
                }
                player = a[2];
                draw();
            }
        }

        function init()
        {
            for(var i=0; i<14; i++)
            {
                board[i] = new Array(14);
                for(var j=0; j<14; j++)
                    board[i][j] = -1;
            }
            hist.length = 0;
            active = true;
            draw();
        }

        function load()
        {
            var canvas = document.getElementById("output");
            ctx = canvas.getContext("2d");
            document.getElementById("mp").checked = false;
            canvas.onmousedown = mouseDown;
            canvas.onmousemove = mouseMove;
            init();
        }
    </script>
</head>
<body onload="load()">
    <canvas style="position:absolute; top:0px; left:20px" width="850" height="600" id="output">Canvas not supported...</canvas>
    <div style="position:absolute; top:250px; left:20px"><input type="button" onClick="init()" value="New game"><br><br>Multiplayer: <input id="mp" type="checkbox" onClick="chgMP()"><br><input type="button" onClick="undo()" value="Undo"></div>
</body>
</html>

```

**Explanation**

The code uses the HTML5's `canvas`-tag to display the game (14x14 board). You can undo the last step and play against another player (enable Multiplayer) or the computer, but its AI is still very weak (it just uses a random position to place the next field). The entire graphical design is based on your screenshot.
> 6 votes

# Answer
# Mathematica, 419.16 points

```
m = False;
Manipulate[
 ClickPane[
  Dynamic@Graphics[
    GraphicsComplex[
     Join @@ Array[{{2, 1}, {0, Sqrt[3]}}.{##} &, {9, 5}], {Red,
      Polygon[{5, 25, 21, 41}], Blue, Polygon[{5, 21, 25, 41}],
      EdgeForm[Gray], If[m, Red, Gray],
      Polygon[{22, 27, 28, 24, 19, 18}]}],
    PlotLabel ->
     Column[{If[m, "Red Wins", "Red to Move"],
       Row@{"Best move is: ",
         Which[m, "(There are no legal moves remaining)", p == 1,
          "(Computer's turn)", ! m, "1,1"]}}, Alignment -> Center]],
  If[p == 2, m = True] &], {{p, 1, "# of players"}, {1, 2}},
 Row@{Button["Start", If[p == 1, m = True]],
   Button["Undo", If[p == 2, m = False]], Button["Reset", m = False]}]

```

Except for the use of `GraphicsComplex`, this code is entirely ungolfed.

## Controls

* The `# of players` selector chooses the number of players. Note that there is a bug that allows you to change between 1-player (human vs. cpu) and 2-player (human vs. human) while a game is in progress.
* `Start` lets the computer start playing in 1-player mode.
* `Undo` takes back the last player's move in 2-player mode.
* `Reset` sets the board back to the starting position.
* Clicking on a hex when it is a human's turn plays in that hex. Note that there is a bug that allows a click outside the playing field to select hex 1,1.

Red always goes first, and in 1-player mode Red is always controlled by the computer. The computer always plays perfectly.

## Points

* 704 bytes: **44.16** points (This can be golfed down significantly.)
* GUI: **50** points (It's worth it to add a gui if you can do it in under 5k (50 * 100) characters... yeah, Mathematica can do that.)
* Two-player mode: **50** points (The second player never gets to go, but that's just too bad.)
* Best-move display: **75** points (There is only one possible move, so this is trivial. Note that it is always displayed: the requirement is "if they wish" not "*iff* they wish.")
* Undo: **50** points (Since there is only one possible move, there is only one possible action to undo: also trivial.)
* Super bot challenge: **150** points (Since I have programmed the computer to always play first, there is no sequence of inputs that can cause it to lose.)
> 0 votes

---
Tags: code-challenge, board-game, hexagonal-grid
---


title: Compute minimal string segment sizes

text:
# Question
Title: Compute minimal string segment sizes
A common optimization to save space in binaries is to merge string literals where one literal is the suffix of another. For instance, a binary with the string literals

```
a: foobar
b: bar
c: barbaz
d: foobarbaz
e: baz

```

might contain the following string literal pool (`#` representing the `\0`-terminator):

```
foobar#foobarbaz#

```

with the symbols `a`, `b`, `c`, and `d` having the following values relative to the beginning of the string pool:

```
a:  0
b:  3
c: 10
d:  7
e: 13

```

In this task, you have to compute the minimal size of a string pool for a given set of input strings.

## Input

The input is a series of up to 999 strings each comprising up to 80 ASCII characters (not including the newline) in the range from 32 to 127 inclusive and then a single newline character.

## Output

Find the shortest string such that each of the input strings (including the terminating newlines) are substrings of that string. The output shall be the length of that shortest string. Do not output the string, only its length.

## Scoring

This challenge is code golf, standard loopholes apply. The solution with the least length in octets wins.

## Examples

1. Input:

```
foobar
bar
barbaz
foobarbaz
baz

```

shortest string, `#` representing newline:

```
foobar#foobarbaz#

```

length: 17
2. Input:

```
foobar
foobaz
foobarbaz
barbaz

```

shortest string, `#` representing newline:

```
foobar#foobaz#foobarbaz#

```

length: 24

# Answer
> 4 votes
# Pyth, ~~20~~ 18 bytes

```
hljb-{.zsmteM./d.z

```

Demonstration.

`{` can be removed if duplicates are not allowed.

Explanation:

```
hljb-{.zsmteM./d.z
                .z     The input, as a list of strings.
         m             Map each strings to
             ./d       all possible partitions of the string into separate strings.
           eM          take the last element of each, giving all suffixes.
          t            Remove the first suffix, giving all suffixes other than
                       the string itself.
        s              Sum, combining the list of lists into a single list.
    -{.z               From the set of input strings, remove all suffixes.
                       This is the list of strings in the minimal segment.
  jb                   Join the strings together on newlines.
 l                     Take the length of the resulting string.
h                      Add one and print.

```

# Answer
> 3 votes
# CJam, 22 bytes

```
qN%_&Nf+:G{Gs\/,3<},s,

```

Try it online.

### How it works

```
qN%   e# Split the input from STDIN at linefeeds, discarding the last, empty chunk.
_&    e# Intersect the array with itself to remove duplicates.
Nf+   e# Append a linefeed to each chunk.
:G    e# Save the result in G.
{     e# Filter; for each chunk in G:
  Gs  e#   Flatten the array of strings G.
  \/  e#   Split at occurrences of G.
  ,3< e#   Compare the resulting number of chunks with 3.
},    e#   Keep the chunk iff the comparision pushed 1 (true).
s,    e# Flatten the resulting array of strings and push the result's length.

```

# Answer
> 1 votes
## python 2, 132

Just to start a race:

```
def f(s):
    l=set(s.split('\n'))
    for x in l:
        for y in l:
            if x!=y and x.endswith(y):l.remove(y)
    return sum(len(x)+1 for x in l)

```

It works:

```
>>> f(r'''foobar
foobaz
foobarbaz
barbaz''')
24
>>> f(r'''foobar
bar
barbaz
foobarbaz
baz
''')
17

```

# Answer
> 1 votes
# Haskell, ~~101~~ 85 bytes

```
import Data.List
length.unlines.(\l->[x|x<-nub l,x`notElem`((tails.tail)=<<l)]).lines

```

A function without a name. Usage example:

```
*Main>  length.unlines.(\l->[x|x<-nub l,x`notElem`((tails.tail)=<<l)]).lines $ "foobar\nbar\nfoobaz"
14

```

How it works: split input string at newlines. Remove duplicates from the word list `l`. Keep a word `x` from the remaining list if it's not in the list of all tails of the words of `l`. Join those `x` with newlines in-between (and at the end!) to a single string and count it's length.

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