title: Complement of a Regex

text:
# Question
Title: Complement of a Regex
For the purposes of this challenge, we define a postfix regex dialect with alphabet `{1, 0}` and the following operations:

* `1` and `0` match themselves literally.
* `_` matches the empty string.
* `!` always fails (i.e. it does not match anything).
* `ab;` matches `a`, followed by `b`.
* `ab|` matches both `a` and `b`.
* `a+` matches one or more instances of `a`.

The regex should always start matching from the start of the string, and stop matching at the end of a string (in other word, it is implicitly wrapped in `^$`).

As an example, the following regex matches any string with an even number of `1`s:

```
0+_|10+_|;10+_|;;+_|;

```

This is equivalent to the regex `0*(10*10*)*`.

The following regex matches any nonempty string of ASCII letters, expressed in binary:

```
110|010|10|10|10|;;;;1010|10|10|;;;10010|;10;|;;|;|;;+

```

This is equivalent to the regex `(1.(0....|1(0...|10(0.|10))))*` (where `.` matches any character.

You can test regexes with this program.

## The Challenge

Given a regex in the format described above, return a regex in this format that matches precisely those strings that are *not* matched by the input.

One potential method to do this would be to convert the regex into a nondeterministic finite automaton, then convert that into a deterministic finite automaton, flip which states are designated as accept states, and then convert it back to a regex.

## Test Cases

```
format:
input   => potential output
           equivalent infix regex

0       => _101|+_|;|
           |1.*
1       => _001|+_|;|
           |0.*
_       => 01|+
           .+
!       => 01|+_|
           .*
01|+    => _

01|+_|  => !
           [] (empty character class)
1001;;; => _01|01|01|;01|01|01|;;001|01|01|01|+_|;;;;01|101|01|01|+_|;;;;01|01|101|01|+_|;;;;01|01|01|001|+_|;;;;|||||||
           |.|..|...|0....*|.1...*|..1..*|...0.*

```

# Answer
# Dyalog APL, 166 bytes

```
{l←!!5*≢⍵⋄z←⊂''⋄n←,∘.,⍨⋄k←{⊃,/n\l/⊂⍵}⋄f←{⊃⊃{⍺∊';|':(2↓⍵),⍨⍺{';'=⍺:n/⍵⋄,/⍵}2↑⍵⋄⍺='_':⍵,⍨⊂z⋄'+'=⍺:⊂∘k∘⊃@1,⍵⋄⍺,⍵}/⌽1,⍵}⋄w←f⍵⋄⊃q/⍨{0=≢((z,k'01')~w∪f⍵)∪w∩f⍵}¨q←k'10!_|;+'}

```

The solution is a function that works by brute-forcing. It cannot be run in reasonable time nor with reasonable memory on any of the inputs, so no TIO link is provided; this is due to looping over every possible regex over the factorial of the factorial of 5 to the power of the input length. Note that the numbers involved go out of Dyalog's maximum number size for an input regex of length greater than 1. To test this, take a look at the function `f`, which returns a value that includes all matches less than the calculated upper bound `l`, and test it on the complementarity check `{0=≢ ... ⍵∩f⍵}`. Using smaller values of `l` can make the function provide wrong results, so note that before reducing its value.

---

There is an upper bound for the minimum length of the complementary regex as a function of the length of the input regex, and an upper bound for the length of the longest string the two regexes need to be tested against to determine their complementarity. These parameters are used to brute force the complementary regex, by comparing the strings accepted by the input regex and the regex being tested for complementarity.

We start by comparing the length of a regular expression to the number of states of its respective DFA.

The non-deterministic finite automaton (NFA) for the regex `1` is the following (using `(Sn)` to denote accepting states)

```
   1
Si-->(Sf)

```

The regex `_` representing an \\$\epsilon\\$-transition can be represented by an NFA that has less than 2 states, as can the regex `!` representing non-acceptance.

```
 _

(Si)

```

```
 !

Si

```

Thus, a regex with only characters from `01_!` with length `n` will have an NFA with max size `n+1`.

The regex `ab;`, where `a` and `b` are sub-regexes, denotes the concatenation of `a` and `b` and can be described as the following. (`Si#` denotes an initial state and `(S##)` denotes a final state.)

```
  Si1-->...-->(Sf1)   Si2-->...-->(Sf2)    ;

                     ε
NFA= Si1-->...-->Sf1-->Si2-->...-->(Sf2)

```

The regex `a+` denotes one or more occurrences of `a`.

```
  Si1-->...-->(Sf1)   +

            ε
      +------------+
      v            |
NFA= Si1-->...-->(Sf1)

```

This produces an NFA with the same size as that of `a`. Again, a regex with only characters from `01_!;` with length `n` will have an NFA with max size `n+1`.

The regex `ab|` denotes an alternative of either `a` or `b`.

```
  Si1-->...-->(Sf1)   |   Si2-->...-->(Sf2)

      Si1-->...-->(Sf1)
NFA=
      Si2-->...-->(Sf2)

```

Both `Si1` and `Si2` are starting states in the above NFA. This does not fit the traditional definition of an NFA, where an NFA has only 1 starting state, but the size of the resulting deterministic finite automaton (DFA) does not increase. If needed, the NFA for `+` can be changed so that there is an ε-transition from the final state to the second state, and the NFAs for `_` and `!` changed to have 2 states each, so that a traditional NFA can be constructed for alternation with ε-transitions between Si1 and Si2.

An NFA resulting from alternation will be as large as the sum of the two sub-regexes that make it up. A regex of length `n` will have an NFA with a maximum size of `n+1`.

By the powerset construction, an NFA with size \\$n\\$ will result in a DFA with size \\$2^n\\$. So a regex of length \\$n\\$ will have a minimal DFA upper-bounded by \\$2^{n+1}\\$. A DFA can be inverted by simply switching the final and non-final states, so its complement will have the same number of states as itself.

With this information, we need an upper limit on the size of the complementary regex as a function of the length of the number of states of the DFA. To do this, I use an algorithm to convert a DFA to a regex; the idea is to represent every possible path from Si to any other state, as well as accounting for loops by tracking every loop that starts and ends at Si, in a recursive manner. For every state that can be reached in 1 step from Si, the process is repeated and a path is constructed from this new state to every other state *except* the states that have already been encountered, i.e. Si in the first iteration, since loops back to Si would already be covered by tracking loops. An example of the construction can make this clearer.

```
0<c0>;1<c1>;|+_|
0<r0>;1<r1>;<a>||
;

```

This is a regex that represents a DFA that I will call the "base form". The base form for a state is a regex that traverses paths from that state to every state in the DFA except for, as we will see, states that have been explicitly excluded for a particular iteration. The accept/reject status of each path is denoted by `<a>`, being `_` for accept or `!` for reject. The second line of the regex accounts for this "breadth-first" filling, by transitioning to states that are 1 step way, and recursing the base form (as represented by `<r0>` and `<r1>`) on those states. Each time we recurse, we exclude the original "parent" state from the graph traversal to prevent the algorithm from infinitely looping. Loops in the regex are tracked in the first line, where, also, every possible path is traversed, halting when reaching the parent state, but these sub-regexes, as denoted by `<c0>` and `<c1>`, consider only the parent state to be the accepting state.

At each level of recursion, the number of excluded states increases by 1, until every possible state is covered at which point the algorithm ends.

The base form, without the recursive parts, is of length 16. Each iteration spawn 4 new sub-regexes, and there are as many iterations as states in the DFA.

If a DFA has n states, an upper bound for the regex length is \\$16 + 16×4 + 16×4×4 + ... + 16×4^{n-1}\\$. This is a geometric series and can also be written as

$$\frac{16}{3}\left(4^n-1\right)$$

Now given a regex with length s, the length of its complement is bounded by

$$h=\frac{16}{3}\left(4^{2^{n+1}}-1\right)$$

(I felt that this upper bound could be improved to a mere exponential instead of a double exponential, potentially saving some bytes, but I was proven wrong by this answer.)

We can check if two regexes are equivalent by brute force, but to do that we need to know the upper limit of the input length to test. If the DFAs of the two regexes are a and b, we can construct another DFA c whose states are the Cartesian product of the states of a and b, so each state of DFA c can be labeled as a 2-tuple `(a_j,b_k)` where `a_j` and `b_k` are states of DFA a and b respectively. The transition of DFA c's state `(a_j,b_k)` under input letter `l` is the tuple of the transition of each state `a_j` and `b_k` in DFAs a and b respectively under letter `l`. The final states of DFA c are all the states `(a_j,b_k)` where either both `a_j` and `b_k` are final states or they are both non-final states. DFA c accepts a word if both DFAs a and b accept this word, i.e. DFAs a and b do not yield complementary results on this word. DFAs a and b are complementary iff DFA c does not accept any word. By the pumping lemma, to check for this, we only need to check of input word sizes up to the number of states of DFA c, minus 1.

The size of the DFA of the complementary regex is `2^(h+1)` and that of the input regex is `2^(n+1)`. Thus we only need to check for input lengths up to `2^(h+1)×2^(n+1)-1`.

$$2^{\frac{16}{3}\left(4^{2^{n+1}}-1\right)+1+n+1}-1$$

We need to find a golfy way to write a function that is always greater than the triple exponential above for n≥1. Factorials grow faster than exponentials and are 1 byte shorter and so can be useful. However, the factorial of 1 is still 1, so we cannot simply chain 3 factorials together. The first function can instead be an exponential `b*n`, APL for b to the power of n, after which two factorials can be added in place of the remaining double exponential, yielding `!!b*n`. \\$b=3\\$ is too small for the base case of n=1, \\$b=4\\$ is slightly smaller, but \\$b=5\\$ goes above the function.

$$l=(5^{≢\omega}!)!$$

This gives the first statement of the APL code, `l←!!5*≢⍵` assign to the variable `l` the factorial `!` of the factorial `!` of `5` to the power of `*` the length  of  the right argument.

# The submission

```
{l←!!5*≢⍵⋄z←⊂''⋄n←,∘.,⍨⋄k←{⊃,/n\l/⊂⍵}⋄f←{⊃⊃{⍺∊';|':(2↓⍵),⍨⍺{';'=⍺:n/⍵⋄,/⍵}2↑⍵⋄⍺='_':⍵,⍨⊂z⋄'+'=⍺:⊂∘k∘⊃@1,⍵⋄⍺,⍵}/⌽1,⍵}⋄w←f⍵⋄⊃q/⍨{0=≢((z,k'01')~w∪f⍵)∪w∩f⍵}¨q←k'10!_|;+'}

```

The regex is parsed and its matches returned by the function `f`. It works on the reversed regex, and 'fold'ing ('reducing' in APL-speak) over it. It returns all matches of a regex, with the special case of the regex `a+` only returning up to the first `l` repetitions of sub-regex `a`, thus keeping the list of matches finite. By having this behaviour of `+`, all input matches up to a length of `l` are included in the result of `f`, i.e. nothing less than what is needed to test for complementarity. APL reduces from right to left, due to order of operations being from right to left. Each intermediate results of the reduce is formed by the matches of each sub-regex encountered thus far. For the initial case, a 1 is prepended to the regex before reversing it, after which the reduce operation is applied.

```
f←{⊃⊃{⍺∊';|':(2↓⍵),⍨⍺{';'=⍺:n/⍵⋄,/⍵}2↑⍵⋄⍺='_':⍵,⍨⊂z⋄'+'=⍺:⊂∘k∘⊃@1,⍵⋄⍺,⍵}/⌽1,⍵}

```

The right argument  contains the matches of each sub-regex encountered so far. The left argument  is the next character of the regex that is being processed. Each case of the regex character is checked using `=` equality or  belongs-to when multiple cases can be joined into 1.

Of particular note, `!` in the regex is treated the same as `0` or `1`, resulting in a match of the character `!`. Due to how the regexes are checked for complementarity, this works fine. Its exact mechanism is `⍺,⍵`, concatenate , a single character being either of `0`, `1`, or `!`, with .

`_` matches the empty string, `z` in the APL code refers to `z←⊂''` present earlier in the entire submission; `⍵,⍨⊂z` the enclosed empty string, i.e. signifying that only the empty string is being matched, is prepended to .

The mechanism of `+` is dependent on the function `k←{⊃,/n\l/⊂⍵}`, which given a list of strings , performs the Cartesian concatenation (Cartesian product, but using concatenation instead of set union) of `l` copies of , where the Cartesian concatenation is defined earlier as `n←,∘.,⍨`. This is achieved using the `@` operator, applying the function `⊂∘k∘⊃` on the list of matches at index `1`, the  enclose and  pick functions are required due to the behaviour of `@`.

Concatenation and alternation are considered together. On `2↑⍵` the list of the first two elements of , `n/` (reduce by `n` Cartesian concatenation) is applied in the case of concatenation, and `,/` (reduce by concatenation). The remaining  is concatenated at the end of this result.

After the execution of the reduce operation, its first set of matches is retrieved using .

The regex does not give errors even on incorrect regexes. The handling of `+` uses the `@` operator which expects the argument to be indexable. When `+` is by itself,  is the scalar `1`, so `@` on `1` would not work, but the `,` applied on  converts it into a list, preventing an error. `+` then takes the Cartesian concatenation of `1` with `l` copies of itself.

`;` and `|` with too few arguments are implicitly handled by the functionality of the  take function and the  function. `2↑` takes the first 2 elements of the right argument, but if the right argument is shorter, the result is padded with sufficient prototype values, for example the prototype of a strictly numeric array is 0, while that of a character array is the space character `' '`.

However, even with this treating of anomalous regexes, these regexes will not be returned by the entire complementary regex function as a complementary regex. This is due to the fact that they cannot be shorter than the respective shortest valid postfix regex, and even if these incorrect regexes are of the same length as the shortest valid regex, they are ordered lexicographically later than a valid regex, with the order being specified later while performing the complementarity check by `10!_|;+`, and only the first (again, ordered lexicographically) complementary regex is picked as a result to the function submission.

### Complementarity check

The checking for complementarity is done by the following part. `q←k'10!_|;+'` generates all possible regexes up to a length of `l` (`k` computes this function as mentioned earlier) and assigns this to `q`. The ordering specified by this part is what prevents incorrect regexes from being returned by the function.

For each of these strings `¨`, the following function is computed, ( denotes the right argument, in this case, each string for which the following function is applied on)

```
{0=≢((z,k'01')~w∪f⍵)∪w∩f⍵}

```

`w` is assigned earlier to the matches of the input regex. `w∩f⍵` computes the intersection of `w`, the matches of the input, with `f⍵`, the matches of . For complementary regexes, this should be the empty set.

`w∪f⍵` computes the union of `w` and `f⍵`. `~` performs set complement. `z` is `⊂''`, the enclosed empty string. `k'01'` computes all binary strings with length up ≤ `l`, so `z,k'01'` is a list containing all these binary strings, along with the empty string.

The result of `(z,k'01')~w∪f⍵` is all the binary strings that are not present in `w∪f⍵`, so it contains the strings that are matches by neither the input regex nor . For complementary regexes this should be the empty set.

`((z,k'01')~w∪f⍵)∪w∩f⍵` is the union of the two sets above. This should be empty if the regexes are complementary. Its emptiness is checked by counting the number of elements contained within it using , and comparing this result with `0`. (Using  doesn't work because in Dyalog APL, empty lists can have different prototype lists.)

This function explained above returns 1 is the regexes are complementary, and 0 if they are not. The first truthy regex is picked by `⊃q/⍨`, being returned by the function.

### Alternative approaches

Initially, I thought that using the approach recommended in the challenge of doing the conversion regex → NFA → DFA → regex would yield a short solution in APL because of APL's strength with matrices (by storing the NFA/DFA as a 3-dimensional array, with each of its 2-dimensional arrays being adjacency matrices for transitions involving each input character and ε-transitions). I got to implement a part of this for the regex matching challenge that popped up recently, but I got a solution much longer than what I had expected at over 250 bytes. It's the handling of individual matrix entries that made the program long, for example, I had to include specific transitions between specific states, like an ε-transition from state 1 to states 2 and 3 for alternation. However the handling of the entire array or its component matrices was short, as was needed to execute the NFA on the input string. And besides, all that the \>250 byte program did was *only* to determine if 1 string matches the input regex. Maybe storing the NFA in a "sparse" format with list of lists of numbers representing states might end up being shorter that the matrix-oriented approach.

I tried another approach to that regex matching challenge by listing all the matches of the input regex, with `+` repetitions bounded by the input length, and checking if the input string belongs to this list, which yielded a \>140-byter, almost half the length of my previous approach. This approach ended up being adapted into function `f` of my submission to this challenge. Unlike the approach mentioned in the previous paragraph, this approach generates the list of all input matches, so I do not have to separately run the regex matching function on each of the possible inputs to see which ones it matches, thus saving a great deal of bytes.

Moreover, I had also tried `⎕r`, Dyalog APL's PCRE replace function, for this challenge but that resulted in a postfix → PCRE converter at \>110 bytes. Besides, similarly to the approach where I stored the NFA in an array, implementing the matching as well as finding all of the matches of this regex on all (bounded) input strings added too many bytes.

It was when I stumbled upon ankh-morpork's Prolog submission to the regex decomposition challenge and by the power of Prolog DCGs that I started working on this regex complement challenge in Prolog. However my Prolog skills was not good enough to make it work, and seeing how my approach ended up becoming un-Prolog-y and more APL-y I switched to APL and started this solution with the knowledge I had gathered from attempting the regex matching challenge. This brute-force approach proved to be significantly short than any other approach I could think of, so I went ahead with this. I left the calculation of the upper bound to the very end, i.e. the `l←` bit, and golfed the rest of my program from an initial size of \>210 bytes.

The complementary check might be further golfable, perhaps there's a nice way to get rid of the parentheses, or an alternative logic. In function `f`, under the case when `⍺∊';|'`, I feel the `2↑⍵` and `2↓⍵` surrounding the code has a shorter alternative; I tried `@1 2⊢⍵`, but this results in an error for invalid regexes requiring me to use an error guard.
> 13 votes

# Answer
# Python 2, <sup>~~1996~~</sup> 1960 bytes

```
lambda s:L(J(I(s)))
_=set;Z=sorted;x,y,z={0},{1},{2}
A=lambda a,b,c:{e for d in b for e in a[c][d]}
def B(a,b):b=_(b);c=b|A(a,b,2);return B(a,c)if b<c else c
C=lambda a,b:any(c in a for c in b)
def D(a):
 b,c,d,e=a;f=_();g=tuple(Z(B(e,{c})));h=_();i={0:{},1:{},2:{}};j=[g]
 while j:
  l=j.pop()
  if l in f:continue
  f.add(l);C(d,l)and h.add(l)
  for k in i:i[k][l]=_()
  for k in[0,1]:m=tuple(Z(B(e,A(e,l,k))));j.append(m);i[k][l].add(m)
 return f,g,h,i
def E(b,a):c,d,e,f=b;return{(a,g)for g in c},(a,d),{(a,g)for g in e},{k:{(a,g):{(a,h)for h in f[k][g]}for g in f[k]}for k in f}
def F(a,b):c,d,e,f=E(a,0);g,h,i,j=E(b,1);l=f.copy();[l[k].update(j[k])for k in l];[l[2][m].add(h)for m in e];return c|g,d,i,l
def G(a,b):c,d,e,f=E(a,0);g,h,i,j=E(b,1);l=f.copy();[l[k].update(j[k])or l[k].update({0:_(),1:_()})for k in l];l[2][0]|={d,h};[l[2][m].add(1)for m in e|i];return c|g|x|y,0,y,l
def H(a):b,c,d,e=a;f=_(d);g={k:e[k].copy()for k in e};[g[2][h].add(c)for h in f];return _(b),c,f,g
def I(s):
 a=[]
 for c in s:
  if c in'10_!':a.append({'1':(x|y|z,0,y,{0:{0:z,1:z,2:z},1:{0:y,1:z,2:z},2:{0:_(),1:_(),2:_()}}),'0':(x|y|z,0,y,{0:{0:y,1:z,2:z},1:{0:z,1:z,2:z},2:{0:_(),1:_(),2:_()}}),'_':(x|y,0,x,{0:{0:y,1:y},1:{0:y,1:y},2:{0:_(),1:_()}}),'!':(x,0,_(),{0:{0:x},1:{0:x},2:{0:_()}})}[c])
  elif c in'|;':a[-2:]=[{'|':G,';':F}[c](a[-2],a[-1])]
  else:a[-1]=H(a[-1])
 return D(a[-1])
def J(a):b,c,d,e=a;f={};[f.update({(g,h):f.get((g,h),'!')+str(k)+'|'})for k in e for g in e[k]for h in e[k][g]];return b,c,b-d,f
def K(a,b,c,d):
 for e in a-{c,d}:
  g={f:b[(f,t)]for f,t in b if t==e!=f};h={t:b[(f,t)]for f,t in b if f==e!=t};i={(f,t):b[(f,t)]for f,t in b if f!=e!=t}
  for f in g:
   for t in h:j=i.get((f,t),'!');i[(f,t)]=g[f]+b.get((e,e),'!')+'+_|;'+h[t]+';'+j+'|'
  b=i
 l,m,n,o=[b.get(pair,'!')for pair in[(c,c),(c,d),(d,d),(d,c)]];return l+'+_|'+(m+';'+o+l+'+_|;'+m+';'+n+'|+_|;')*(c!=d)
def L(a):b,c,d,e=a;return''.join(K(b,e,c,f)for f in d)+'!'+'|'*len(d)

```

Try it online!

Since user41805 came up with a very short but only theoretically-working solution, here is a practical one (practical as in "you can actually observe the output for small inputs"). The TIO link also includes a kind of test-battery to check for complement-ness.

It should be theoretically possible to solve Complement of POSIX ERE by reusing large chunks of code here, but I don't think I'll tackle it anytime soon. Feel free to solve it and take the 200 bounty.

## Ungolfed, and how it works

The code is mainly divided into three parts: construct an NFA from the input regex, convert it to a DFA and invert its accept states, and convert it back to a regex.

### Preliminary definitions

```
from collections import namedtuple

NFA = namedtuple('NFA', ['nodes', 'start', 'accept', 'trans'])
DFA = namedtuple('DFA', ['nodes', 'start', 'accept', 'trans'])

```

The definitions for NFA and DFA are there just to help reading the code. `NFA` and `DFA` have the same field names, but the `trans` fields contain different data structures.

### Input regex to NFA

```
def step_once(trans, nodes_from, step):
    return {n for x in nodes_from for n in trans[step][x]}

def e_closure(trans, nodes_from):
    nodes_from = set(nodes_from)
    nodes_to = nodes_from | step_once(trans, nodes_from, '')
    while nodes_from != nodes_to:
        nodes_from = nodes_to
        nodes_to = nodes_from | step_once(trans, nodes_from, '')
    return nodes_to

def is_accept(accept, nodes):
    return any(node in accept for node in nodes)

def to_dfa(nfa):
    new_nodes = set()
    new_start = tuple(sorted(e_closure(nfa.trans, {nfa.start})))
    new_accept = set()
    new_trans = {0:{}, 1:{}, '':{}}
    stack = [new_start]
    while stack:
        node_set = stack.pop()
        if node_set in new_nodes: continue
        new_nodes.add(node_set)
        if is_accept(nfa.accept, node_set): new_accept.add(node_set)
        for k in new_trans: new_trans[k][node_set] = set()
        for k in [0, 1]:
            node_step = e_closure(nfa.trans, step_once(nfa.trans, node_set, k))
            node_step = tuple(sorted(node_step))
            stack.append(node_step)
            new_trans[k][node_set].add(node_step)
    return NFA(new_nodes, new_start, new_accept, new_trans)

```

`to_dfa` eliminates ϵ-moves and non-deterministic moves from the given ϵ-NFA. The algorithm is pretty standard: starting from the ϵ-closure of the start state, record all the reachable state sets by traversing through 0- and 1-moves followed by ϵ-closure.

```
one = NFA({0,1,2}, 0, {1}, {
    0: {0:{2}, 1:{2}, 2:{2}},
    1: {0:{1}, 1:{2}, 2:{2}},
    '': {0:set(), 1:set(), 2:set()}
})

zero = NFA({0,1,2}, 0, {1}, {
    0: {0:{1}, 1:{2}, 2:{2}},
    1: {0:{2}, 1:{2}, 2:{2}},
    '': {0:set(), 1:set(), 2:set()}
})

empty = NFA({0,1}, 0, {0}, {
    0: {0:{1}, 1:{1}},
    1: {0:{1}, 1:{1}},
    '': {0:set(), 1:set()}
})

null = NFA({0}, 0, set(), {
    0: {0:{0}},
    1: {0:{0}},
    '': {0:set()}
})

```

The NFA definitions for the four base regexes `10_!` respectively.

```
def prefix(nfa, a):
    new_nodes = {(a,node) for node in nfa.nodes}
    new_start = (a,nfa.start)
    new_accept = {(a,node) for node in nfa.accept}
    new_trans = {k: {(a,node): {(a,dest) for dest in nfa.trans[k][node]} for node in nfa.trans[k]} for k in nfa.trans}
    return NFA(new_nodes, new_start, new_accept, new_trans)

```

`prefix` helper function converts an NFA into an equivalent one, but with each node key `n` wrapped into a 2-tuple `(a,n)`. This is used for combining two NFAs to avoid key collisions. In Python, a tuple is hashable whenever all of its elements are hashable (thus appropriate for a dict key).

```
def concat(a, b):
    a = prefix(a, 0)
    b = prefix(b, 1)
    new_nodes = a.nodes | b.nodes
    new_start = a.start
    new_accept = b.accept
    new_trans = a.trans.copy()
    for k in new_trans: new_trans[k].update(b.trans[k])
    for a_acc in a.accept: new_trans[''][a_acc].add(b.start)
    return NFA(new_nodes, new_start, new_accept, new_trans)

def branch(a, b):
    a = prefix(a, 0)
    b = prefix(b, 1)
    new_nodes = a.nodes | b.nodes | {0, 1}
    new_start = 0
    new_accept = {1}
    new_trans = a.trans.copy()
    for k in new_trans: new_trans[k].update(b.trans[k]); new_trans[k].update({0:set(), 1:set()})
    new_trans[''][0] |= {a.start, b.start}
    for acc in a.accept | b.accept: new_trans[''][acc].add(1)
    return NFA(new_nodes, new_start, new_accept, new_trans)

def plus(nfa):
    new_nodes = set(nfa.nodes)
    new_start = nfa.start
    new_accept = set(nfa.accept)
    new_trans = {k: nfa.trans[k].copy() for k in nfa.trans}
    for acc in new_accept: new_trans[''][acc].add(new_start)
    return NFA(new_nodes, new_start, new_accept, new_trans)

```

Three combiner functions corresponding to `ab;`, `ab|`, `a+` respectively.

`ab;`: Connect the accept states of `a` to the start state of `b` through ϵ-moves.

```
            e
S1 ... A1 -----> S2 ... A2

```

`ab|`: Introduce the overall start and accept states, and connect them through ϵ-moves like the following.

```
     e                e
   -----> S1 ... A1 ----->
S {                       } A
   -----> S2 ... A2 ----->
     e                e

```

`a+`: Connect the accept states back to the start states through ϵ-moves.

```
S ... A
|     |
\<----/
   e

```

Finally, we combine all of them to convert the input regex into a deterministic NFA.

```
def input_to_nfa(s):
    stack = []
    for c in s:
        if c == '1': stack.append(one)
        elif c == '0': stack.append(zero)
        elif c == '_': stack.append(empty)
        elif c == '!': stack.append(null)
        elif c == '|': stack[-2:] = [branch(stack[-2], stack[-1])]
        elif c == ';': stack[-2:] = [concat(stack[-2], stack[-1])]
        elif c == '+': stack[-1] = plus(stack[-1])
    return to_dfa(stack[-1])

```

### NFA to DFA

```
def nfa_to_dfa(nfa):
    nodes = nfa.nodes
    start = nfa.start
    accept = nfa.nodes - nfa.accept
    trans = {}
    for k in nfa.trans:
        for node_from in nfa.trans[k]:
            for node_to in nfa.trans[k][node_from]:
                trans[(node_from, node_to)] = trans.get((node_from, node_to), '!') + str(k) + '|'
    return DFA(nodes, start, accept, trans)

```

Invert the accept states by set difference, and convert the data structure of the transition table so that it is suitable for regex construction.

### DFA to regex

```
# dfa-style trans
def path_to_regex(nodes, trans, node_from, node_to):
    for node in nodes - {node_from, node_to}:
        left_nodes = {f: trans[(f,t)] for f,t in trans if t == node != f}
        right_nodes = {t: trans[(f,t)] for f,t in trans if f == node != t}
        loop = trans.get((node, node), '!')
        new_trans = {(f, t): trans[(f,t)] for f,t in trans if f != node != t}
        for f in left_nodes:
            for t in right_nodes:
                existing = new_trans.get((f, t), '!')
                new_trans[(f,t)] = left_nodes[f] + loop + '+_|;' + right_nodes[t] + ';' + existing + '|'
        trans = new_trans
    ff, ft, tt, tf = [trans.get(pair, '!') for pair in [(node_from, node_from), (node_from, node_to), (node_to, node_to), (node_to, node_from)]]
    if node_from == node_to: return ff + '+_|'
    return ff + '+_|' + ft + ';' + tf + ff + '+_|;' + ft + ';' + tt + '|+_|;'

def dfa_to_regex(dfa):
    regexes = [path_to_regex(dfa.nodes, dfa.trans, dfa.start, acc) for acc in dfa.accept]
    if not regexes: return '!'
    return ''.join(regexes) + '|' * (len(regexes) - 1)

```

For each pair of `start -> accept` states, eliminate all the other states by regex chaining and convert the result into a single regex. If we have multiple accept states, link the resulting regexes by `|`. If we have zero accept states, return a single '!'.

```
def solution(s):
    return dfa_to_regex(nfa_to_dfa(input_to_nfa(s)))

```

Solves the entire task by chaining the three core functions.
> 6 votes

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


title: The Bridge and Torch Problem

text:
# Question
Title: The Bridge and Torch Problem
The inspiration for this code golf puzzle is the Bridge and Torch problem, in which ***d*** people at the start of a bridge must all cross it in the least amount of time.

The catch is that at most two people can cross at once, otherwise the bridge will crush under their weight, and the group only has access to one torch, which must be carried to cross the bridge.

Each person in the whole puzzle has a specified time that they take to walk across the bridge. If two people cross together, the pair goes as slow as the slowest person.

There is no set number of people that must cross the bridge; your solution MUST work for any value of ***d***.

You needn't use standard input for this problem, but for the sake of explaining the problem, I will be using the following input and output format for the explanation. The first number, ***d***, is the number of people at the start of the bridge. Then, the code will scan for ***d*** numbers, each representing the speed of a person.

The code output will be the LEAST amount of time required to cross everyone from the start of the bridge to the end of the bridge, while meeting the criteria explained earlier.

Here are some input cases and output cases and the explanation for the first input case. It is up to you to derive an algorithm from this information to solve the problem in the fewest bytes of code possible.

**input**

```
4
1 2 5 8

```

**output**

```
15

```

To reach this output, the people must cross in the following way.

```
A and B cross forward (2 minutes)
A returns (1 minute)
C and D cross forward (8 minutes)
B returns (2 minutes)
A and B cross forward (2 minutes)

```

Here's another test case to guide you along your way.

**input**

```
5
3 1 6 8 12

```

**output**

```
29

```

Rules:

1. Assume that the input will not be sorted, and you must do so on your own (if you need to)
2. The number of people in the puzzle is not fixed at 4 (N \>= 1)
3. Every group and individual crossing must have a torch. There is only one torch.
4. Each group must consist of a maximum of only 2 people!
5. No, you may not jump off the bridge and swim to the other side. No other tricks like this ;).

# Answer
> 9 votes
## Python 3, ~~100~~ 99 bytes

a recursive solution

```
f=lambda s:s[0]+s[-1]+min(2*s[1],s[0]+s[-2])+f(s[:-2])if s.sort()or 3<len(s)else sum(s[len(s)==2:])

```

*Thanks to @xnor for this paper*

*Thanks to @lirtosiast save 2 bytes, @movatica save 1 bytes and to @gladed pointing at that my previous solution doesn't work*

use the following trick to evaluate something in lambda function `s.sort() or s` here we compute sort and return the result of the test `s.sort()or len(s)>3`

## Ungolfed

```
def f(s):
    s.sort()                                   # sort input in place
    if len(s)>3:                               # loop until len(s) < 3
        a = s[0]+s[-1]+min(2*s[1],s[0]+s[-2])  # minimum time according to xnor paper
        return  a + f(s[:-2])                  # recursion on remaining people
    else:
        return sum(s[len(s)==2:])              # add last times when len(s) < 3

```

## Results

```
>>> f([3, 1, 6, 8, 12])
29
>>> f([1, 2, 5, 8])
15
>>> f([5])
5
>>> f([1])
1
>>> f([1, 3, 4, 5])
14

```

# Answer
> 4 votes
# Python 2, ~~119~~ ~~114~~ ~~112~~ ~~119~~ ~~110~~ ~~100~~ 95 bytes

I have been advised to separate my answers out.

A solution using `Theorem 1, A2:09` of this paper xnor linked. To quote the paper (changing it to zero-indexing): `The difference between C_{k-1} and C_k is 2*t_1 - t_0 - t_{N-2k}.`

```
lambda n,t:t.sort()or(n-3)*t[0]*(n>1)+sum(t)+sum(min(0,2*t[1]-t[0]-t[~k*2])for k in range(n/2))

```

**Ungolfing:**

```
def b(n, t): # using length as an argument
    t.sort()
    z = sum(t) + (n-3) * t[0] * (n>1) # just sum(t) == t[0] if len(t) == 1
    for k in range(n/2):
        z += min(0, 2*t[1] - t[0] - t[-(k+1)*2]) # ~k == -(k+1)
    return z

```

# Answer
> 3 votes
# APL (Dyalog Extended), 39 bytes

```
{2≥≢⍵:⊃⍵⋄(⊃∘⌽+⊃+(∇1↓⊢)⌊(∇2↓⊢)+2×2⊃⌽)⍵}∨

```

Try it online!

A tacit function which includes a recursive dfn.

### How it works: the idea

My solution is based on subproblem analysis. Given the crossing times \\$ t\_1, t\_2, \cdots, t\_n \\$ sorted in ascending order, there are two possibly optimal ways to help the worst person cross the bridge:

1. \\$ (t\_1, t\_n) \rightarrow t\_1 \\$: net effect is \\$ t\_n \\$ crossing, and the cost is \\$ t\_n + t\_1 \\$.
2. \\$ (t\_1, t\_2) \rightarrow t\_2 \rightarrow (t\_{n-1}, t\_n) \rightarrow t\_1 \\$: net effect is \\$ t\_{n-1} \\$ and \\$ t\_n \\$ crossing, and the cost is \\$ t\_1 + 2t\_2 + t\_n \\$.

Let's say \\$ T\_k \\$ be the optimal time to cross the first \\$k\\$ people. Then, for the first \\$k\\$ people crossing, we can choose between "use (1) and let \\$ k-1 \\$ remaining people cross" and "use (2) and let \\$ k-2 \\$ remaining people cross", which becomes

$$ \begin{aligned} T\_k &= \min(T\_{k-1} + t\_n + t\_1, T\_{k-2} + t\_1 + 2t\_2 + t\_n) \\ &= t\_1 + t\_n + \min(T\_{k-1}, T\_{k-2} + 2t\_2) \end{aligned} $$

### How it works: the code

```
{2≥≢⍵:⊃⍵⋄(⊃∘⌽+⊃+(∇1↓⊢)⌊(∇2↓⊢)+2×2⊃⌽)⍵}∨
                                      ∨  ⍝ Descending sort to get [t_n .. t_1]
{                                    }   ⍝ Pass on to recursive function

 2≥≢⍵:⊃⍵  ⍝ Base case: If input length ≤ 2, return the first element
          ⍝   [t_1] → t_1, [t_2 t_1] → t_2

 (⊃∘⌽+⊃+(∇1↓⊢)⌊(∇2↓⊢)+2×2⊃⌽)⍵  ⍝ Recursive case
        ( 1↓⊢)                 ⍝ Choice 1: Drop 1 to get [t_{n-1} .. t_1]
         ∇                     ⍝           Recursive call to get T_{n-1}
               (∇2↓⊢)          ⍝ Choice 2: Drop 2 and recurse to get T_{n-2}
                     +2×2⊃⌽    ⍝           and add 2×t_2
              ⌊                ⍝ Minimum of two choices
  ⊃∘⌽+⊃+                       ⍝ Add common terms t_1 and t_n

```

---

Using DP to solve the recursive problem costs a few more bytes:

# APL (Dyalog Extended), 44 bytes

```
⊃⊃(+∘(⊃∘⌽+⊃⌊2∘⊃+2×2⊃⌽),⊢)/(¯2∘↓,∘⊂0~⍨¯2∘↑)∨⎕

```

Try it online!

A full program.

### How it works: the code

```
∨⎕  ⍝ Descending sort the given array

(¯2∘↓,∘⊂0~⍨¯2∘↑)  ⍝ Set up the initial element for reduce
                  ⍝ e.g. [12 8 6 3 1] → [12 8 6 (3 1)]
           ¯2∘↑   ⍝ Take the last two elements
                  ⍝   If input length is 1, ↑ becomes "overtake" and yields [0 n]
        0~⍨       ⍝ Remove zeros to undo "overtake"
       ⊂          ⍝ Enclose to make it the initial item
 ¯2∘↓,∘           ⍝ Append to the original array with last two elements dropped

(+∘(⊃∘⌽+⊃⌊2∘⊃+2×2⊃⌽),⊢)/  ⍝ Reduce by the logic, right to left
          2∘⊃+2×2⊃⌽       ⍝ Choice (2):
          2∘⊃+            ⍝   T_{k-2} +
              2×2⊃⌽       ⍝   2*t_2
        ⊃                 ⍝ Choice (1): T_{k-1}
   (⊃∘⌽+           )      ⍝ Common term: + t_1
 +∘                       ⍝              + t_n
                    ,⊢    ⍝ Prepend the resuting value T_k to the DP array
(                     )/  ⍝ Reduce by the function above

⊃⊃  ⍝ Remove the layering and take the first element (which is T_n)

```

# Answer
> 2 votes
# Ruby, ~~94~~ ~~133~~ ~~97~~ ~~96~~ ~~101~~ ~~96~~ 99 bytes

I have been advised to separate my answers out.

This is a solution based on the algorithm described in `A6:06-10` of this paper on the Bridge and Torch Problem.

**Edit:** Fixing a bug where `a=s[0]` is not yet defined when `a` is called at the end if `s.size <= 3`.

```
->s{r=0;(a,b,*c,d,e=s;r+=a+e+[b*2,a+d].min;*s,y,z=s)while s.sort![3];r+s.reduce(:+)-~s.size%2*s[0]}

```

**Ungolfing:**

```
def g(s)
  r = 0
  while s.sort![3]      # while s.size > 3
    a, b, *c, d, e = s  # lots of array unpacking here
    r += a + e + [b*2, a+d].min
    *s, y, z = s        # same as s=s[:-2] in Python, but using array unpacking
  end
  # returns the correct result if s.size is in [1,2,3]
  return r + s.reduce(:+) - (s.size+1)%2 * s[0]
end

```

# Answer
> 2 votes
# Python 2, 89 bytes

```
lambda t:t.sort()or reduce(lambda x,c:x+[min(x[-2]+x[1]*2,x[-1])+c+x[0]],t[2:],t[:2])[-1]

```

Try it online!

Uses the same formulation as my APL answer, except that direct reduction turns out shorter in this case. Incidentally, this wins against all the previous entries (except APL).

# Answer
> 1 votes
# Scala, ~~113~~ 135 (darnit)

```
def f(a:Seq[Int]):Int={val(s,b)=a.size->a.sorted;if(s<4)a.sum-(s+1)%2*b(0)else b(0)+Math.min(2*b(1),b(0)+b(s-2))+b(s-1)+f(b.take(s-2))}

```

Ungolfed somewhat:

```
def f(a:Seq[Int]):Int = {
    val(s,b)=a.size->a.sorted      // Sort and size
    if (s<4) a.sum-(s+1)%2*b(0)    // Send the rest for cases 1-3
    else Math.min(b(0)+2*b(1)+b(s-1),2*b(0)+b(s-2)+b(s-1)) + // Yeah.
        f(b.take(s-2))             // Repeat w/o 2 worst
}

```

Tester:

```
val tests = Seq(Seq(9)->9, Seq(1,2,5,8)->15, Seq(1,3,4,5)->14, Seq(3,1,6,8,12)->29, Seq(1,5,1,1)->9, Seq(1,2,3,4,5,6)->22, Seq(1,2,3)->6, Seq(1,2,3,4,5,6,7)->28)
println("Failures: " + tests.filterNot(t=>f(t._1)==t._2).map(t=>t._1.toString + " returns " + f(t._1) + " not " + t._2).mkString(", "))

```

Not great in general, but maybe not bad for a strongly-typed language. And begrudging thanks to xnor for spotting a case I didn't catch.

# Answer
> 1 votes
# Ruby, ~~104~~ ~~95~~ 93 bytes

I have been advised to separate my answers out.

This is a solution based on my Python 2 solution and `Theorem 1, A2:09` of this paper on the Bridge and Torch Problem.

```
->n,t{z=t.sort!.reduce(:+)+t[0]*(n>1?n-3:0);(n/2).times{|k|z+=[0,2*t[1]-t[0]-t[~k*2]].min};z}

```

**Ungolfing:**

```
def b(n, t) # using length as an argument
  z = t.sort!.reduce(:+) + t[0] * (n>1 ? n-3 : 0)
  (n/2).times do each |k|
    a = t[1]*2 - t[0] - t[-(k+1)*2] # ~k == -(k+1)
    z += [0, a].min
  end
  return z
end

```

# Answer
> 0 votes
# Pyth, 34 bytes

```
W>l=SQ3=+Zs[hQ.)QhS[y@Q1+hQ.)Q;+Zs

```

There's probably some way to write it as a reduce or some other functional magic, but I've spent enough time doing high school programming coursework today that actually writing anything resembling good code is a nice change of pace.

Try it online!

---
Tags: code-golf
---


title: The most common substring

text:
# Question
Title: The most common substring
The purpose of this task is to write a program or function to find the most common substring within a given string, of the specified length.

## Inputs

1. A string, `s`, of any length and characters that are valid as inputs for your language.
2. A number, `n`, indicating the length of substring to find. Guaranteed to be equal to or less than the length of the string.

## Output

The most common (case-sensitive) substring of `s` of length `n`. In the case of a tie, any of the options may be output.

## Win Criteria

This is , so lowest bytes wins; usual exceptions etc. apply.

## Examples

`Hello, World!`, `1` \> `l` (appears 3 times)
`Hello! Cheerio!`, `2` \> `o!` (appears twice)
`The Cat sat on the mat`, `2` \> `at` (appears three times)
`The Cat sat on the mat`, `3` \> `at`  or `he`  (both with trailing spaces. Both appear twice - note case-sensitivity so `The` and `the` are different substrings)
`Mississippi`, `4` \> `issi` (appears twice, note that the two occurrences overlap each other)

## Some more examples, all using the same input string*

```
Bb:maj/2
F:maj/5
Bb:maj/2
G:9/3
Bb:maj7
F:maj/3
G:min7
C:sus4(b7,9)
C:sus4(b7,9)
C:sus4(b7,9)
F:maj
F:maj

```

(note the trailing newline)

1 \> `\r\n`(appears 12 times, counting `\r\n` as a single character - my choice, your code may differ on this - otherwise either `\r` or `\n` appear the same number of times). `:` also appears 12 times
2 \> `:m` (appears 8 times)
3 \> `:ma` or `maj` (appears 7 times)
4 \> `:maj` (appears 7 times)
5 \> `F:maj` or `\r\nF:ma` or `:maj/` (appears 4 times)
14 \> `\r\nC:sus4(b7,9)\r\n` (appears 3 times)

(\* input is taken from How predictable is popular music?. The result of this task might be used, for example, to find the most efficient way to apply a substitution in order to compress the string)

# Answer
# 05AB1E, 5 bytes

```
ŒIù.M

```

Try it online or verify the smaller test cases or verify the larger test case (which is a bit slow).

**Explanation:**

```
Œ      # Push all substrings of the (implicit) input-string
 Iù    # Only keep substrings of a length equal to the second input-integer
   .M  # Only keep the most frequent item of the remaining substrings
       # (after which it is output implicitly as result)

```
> 7 votes

# Answer
# Python 3.8, ~~75~~ ~~68~~ ~~97~~ 63 bytes

```
lambda s,n:max(l:=[s[j:j+n]for j in range(len(s))],key=l.count)

```

You can try it online! Increased byte count because, as @xnor kindly pointed out, Python's `str.count` doesn't count overlapping substrings... But then @xnor's reformulation of what I was doing allowed to slice a third of the bytes!

## How:

```
l:=[s[j:j+n]for j in range(len(s))]

```

This creates a list of all the substrings in `s` of size `n`, plus the suffixes of size `n-1`, `n-2`, ..., `1`. Then we find the `max` on that list, with the numerical value being used to sort given by

```
l.count

```

That means that if `a` and `b` are from `l`, `a > b` if `a` shows up more times in `l` than `b`. This means the shorter suffixes are never the result of the `max` because they only show up once, and even if the correct-sized substrings only show up once, they are first in `l` so they come out instead of the short suffixes. This allows me to save some bytes in the `range` used, given that I don't have to prevent `i+n` from being larger than `len(s)`.

~~\# Python, ~~83~~ 64 bytes~~

~~```
lambda s,n:max((s[i:i+n]for i in range(len(s)-n+1)),key=s.count)

```
Thanks to @mypetlion I saved a LOT of bytes :D
~~

~~You can try it online with my very own incredible test case!~~
> 10 votes

# Answer
# Brachylog, 8 bytes

```
s₎ᶠọtᵒth

```

Try it online!

### Explanation

```
  ᶠ        Find all…
s          …substrings of <1st element of input>…
 ₎         …of length <2nd element of input>
   ọ       Get the list of each substring with its number of occurrence
    tᵒ     Order by the number of occurrence
      t    Take the last one
       h   Output the substring itself

```
> 5 votes

# Answer
# Perl 6, ~~49~~ 46 bytes

*-3 bytes thanks to SirBogman*

```
{$^n;bag($^a~~m:ov/.**{$n}/X~$).max(*{*}).key}

```

Try it online!

### Explanation

```
{                                            }  # Anonymous block
 $^n;  # Declare argument
         $^a~~m   /       /  # Regex match input string
               :ov           # Also return overlapping matches
                   .**{$n}   # Match n-character strings
                           X~$   # Stringify matches
     bag(                     )  # Convert to Bag (multiset)
                               .max(*{*})  # Find Pair string=>count with max value
                                         .key  # Get key (string)

```
> 5 votes

# Answer
# JavaScript (ES6),  ~~85 83~~  80 bytes

Takes input as `(string)(length)`.

```
s=>n=>[...s].map(o=m=(x,i)=>(o[k=s.substr(i,n)]=-~o[k])<m|!k[n-1]?0:m=o[O=k])&&O

```

Try it online!
> 5 votes

# Answer
# Java 10, ~~212~~ ~~211~~ ~~196~~ ~~195~~ ~~146~~ 143 bytes

```
s->n->{String r="",t;for(int m=0,c,j,i=s.length();i-->n;)for(c=0,j=-1;(j=s.indexOf(t=s.substring(i-n,i),j+1))>=0;)if(++c>m){m=c;r=t;}return r;}

```

-15 bytes by outputting the substrings with their count, which is allowed.
-1 byte thanks to *@ceilingcat*.
-52 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
s->n->{         // Method with String and Integer parameters and String return-type
  String r="",  //  Result-String, starting empty
         t;     //  Temp-String
  for(int m=0,  //  Largest count, starting at 0
          c,    //  Temp count integer
          j,    //  Temp index integer
          i     //  Index-integer `i`
      =s.length();i-->n;)
                //  Loop `i` in the range (input-length, n]:
    for(c=0,    //   Reset the temp-count to 0
        j=-1;   //   And the temp-index integer to -1
        (j=s.indexOf(t=s.substring(i-n,i)
                //   Set String `t` to a substring of the input-String in the range [i-n,i)
           j+1))//   Set the temp-index `j` to the index of String `t` in the input-String,
                //   only looking at the trailing portion after index `j+1`
        >=0;)   //   And continue looping as long as long as that substring is found
      if(++c>m){//    If the temp-count + 1 is larger than the current largest count:
        m=c;    //     Set this current largest count to this temp-count + 1
        r=t;}   //     And the result-String to this temp-String
  return r;}    //  After the nested loops, return the result-String

```
> 5 votes

# Answer
# PHP, ~~133~~ 126 bytes

```
for(;$k<=strlen($i=$argv[1])-$j=$argv[2];)$s[]=substr($i,$k++,$j);$c=array_count_values($s);asort($c);echo array_key_last($c);

```

Try it online!

Annoyingly `asort()` ~~and `end()`~~ can't be chained into one expression.

-7 bytes thanks to @manatwork
> 4 votes

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

```
s=>n=>s.map(F=t=>([F[w=(w+t).slice(-n)]=-~F[w],w]),w="").sort(([a],[b])=>a-b)[s.length-1][1]

```

Try it online!

Takes `s` as a list of characters in `(s)(n)` syntax.
> 3 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~97~~, ~~96~~, 92 bytes

```
s=>n=>s.Skip(n-1).Select((_,i)=>s.Substring(i,n)).GroupBy(x=>x).OrderBy(g=>g.Count()).Last()

```

Try it online!

Explanation:

```
s.Skip(n-1).Select((_,i)=>s.Substring(i,n)) //select every substring of size n
    .GroupBy(x=>x)                          //group by value
        .OrderBy(g=>g.Count())              //order by increasing recurrence
            .Last()                         //return the last one

```
> 3 votes

# Answer
# Charcoal, 28 bytes

```
ＮθＦ⊕⁻Ｌηθ⊞υ✂ηι⁺θιＵＭυ⟦№υιι⟧⊟⌈υ

```

Try it online! Link is to verbose version of code. Outputs the lexicographically largest substring with the highest count. Explanation:

```
Ｎθ

```

Input the desired substring length.

```
Ｆ⊕⁻Ｌηθ⊞υ✂ηι⁺θι

```

Extract all substrings of that length and push them to a list.

```
ＵＭυ⟦№υιι⟧

```

Replace each substring with a tuple of its count and the substring..

```
⊟⌈υ

```

Print the substring with the highest count.
> 2 votes

# Answer
# Japt `-g`, 8 bytes

```
ãV ü ñÊÌ

```

Try it
> 2 votes

# Answer
# Wolfram Language (Mathematica), 30 bytes

```
#&@@Commonest[##~Partition~1]&

```

Takes an array of characters, returns an array of characters.

Try it online!

# Wolfram Language (Mathematica), 36 bytes

```
#&@@Commonest[##~StringPartition~1]&

```

Takes a string, returns a string.

Try it online!
> 2 votes

# Answer
# Zsh, 89 bytes

```
local -A m
repeat $#1 ((++m[${1:$[i++]:$2}]))
for k v (${(kv)m})((v>M))&&r=$k&&M=$v
<<<$r

```

Try it online!

```
local -A m                    # associative array, "local" is shorter than "typeset"
repeat $#1 {                  # looping for the length of the string will cause the
                              # program to use shorter, invalid strings as
                              # the bash-style slice gets cut short
    ((++m[${1:$[i++]:$2}]))   # increment the map at the key with substring
}                             # starting at $[i++] with length $2
for k v (${(kv)m}) {          # loop over the associative array's keys/values
    ((v>M)) && r=$k && M=$v   # find the max value M, save the key as r.
}                             # looping forward ensures we avoid our invalid subtrings
<<<$r                         # print $r

```
> 2 votes

# Answer
# C++ (clang), ~~201~~ \\$\cdots\\$ ~~151~~ 150 bytes

```
#import<map>
using S=std::string;S f(S s,int n){std::map<S,int>m;S t,r;for(int i=0,x=0;i<=s.size()-n;r=x<++m[t=s.substr(i++,n)]?x=m[t],t:r);return r;}

```

Try it online!

# Ungolfed

```
#include<map>
#include<string>
std::string f(const std::string& s,int n) {
    std::map<std::string,int> m;
    for(int i=0;i<=s.size()-n;++i) {
        m[s.substr(i,n)]++;
    }
    int x=0;
    std::string r;
    for(auto a:m) {
         if(x<a.second) {
             x=a.second;
             r=a.first;
         }
    }
    return r;
}

```
> 2 votes

# Answer
# Excel (Ver. 1911), 60 Bytes

```
B2 'Input: String
B3 'Input: Sub-string Length
C2 =-COUNTIF(D2#,D2#)
D2 =MID(B2,SEQUENCE(LEN(B2)),B3)
E2 =SORT(C2#:D2)
F2 'Output

```

### Test Sample

Note: Newlines do exist in cells, but default formatting doesn't show them. Also only 10 of the 105 rows are shown to keep the image a decent size.
> 2 votes

# Answer
# Jelly, 6 bytes

I have a feeling there may be an elusive 5-byter out there.

```
ṡċ@Þ`Ṫ

```

**Try it online!**
> 1 votes

# Answer
# PowerShell, 72 bytes

```
param($s,$n)(0..($s.Length-$n)|%{$s|% s*g $_ $n}|group|sort C*|% N*)[-1]

```

Try it online!

Unrolled:

```
param($s,$n)
(
    0..($s.Length-$n)|%{
        $s|% substring $_ $n
    }|group|sort Count|% Name
)[-1]

```
> 1 votes

# Answer
# Ruby, 58 bytes

```
->s,n{a=(0..s.size).map{|i|s[i,n]};a.max_by{|e|a.count e}}

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-lp`, 47 bytes

```
++$k{$_}>$k{$\}&&($\=$_)for<>=~/(?=(.{$_}))/g}{

```

Try it online!
> 1 votes

# Answer
# Japt `-h`, 8 bytes

```
ãV
ñ@è¶X

```

Try it
> 1 votes

# Answer
# Go, 131 bytes

```
func f(s string,l int)(p string){x,i:=0,0
m:=map[string]int{}
for;i<=len(s)-l;i++{t:=s[i:i+l]
m[t]++
if m[t]>x{x=m[t]
p=t}}
return}

```

Takes as input a `string` and an `int` representing the string and the length of the substring respectively.

Some newlines can be replaced by semicolons if people prefer one-liners.

Try it online!
> 1 votes

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


title: Phony fractions

text:
# Question
Title: Phony fractions
# Context

If `a0` and `b0` are two decimal numbers, with `a` and `b` representing the decimal expansion of all digits but the least significant one, then we know that

$$\frac{a0}{b0} = \frac{a{\not\mathrel0}}{b{\not\mathrel0}}= \frac{a}{b}$$

# Phony fraction

A *phony fraction* is a fraction where the numerator and denominator share a digit (other than a 0 in the units place) and, when that digit is erased from both numerator and denominator, the simplified fraction happens to be equal to the original one.

## Example

\\$16/64\\$ is a *phony fraction* because if we remove the \\$6\\$, we get \\$16/64 = 1{\not\mathrel6}/{\not\mathrel6}4 = 1/4\\$, even though the intermediate step of removing both sixes is wrong.

# Task

Given a fraction, determine if it is *phony* or not.

## Note

Notice that `10/20` is not a *phony fraction*. Even though `10/20 = 1/2`, the simplification here was mathematically sound, you divided numerator and denominator by `10`, which amounts to "crossing out a 0 on the num. and the den.".

On the other hand, `102/204 = 12/24` is a phony fraction, because supposedly we can't cross out the 0s.

Because of this, when the input fraction is such that crossing out 0 gives an equivalent fraction to the original, the behaviour is unspecified.

# Input

The fraction we care about, with positive numerator and denominator, in any sensible format. Some examples of sensible formats include:

* a list `[num, den]` or `[den, num]`
* a string of the form `"num/den"`
* the exact fraction, if your language supports it
* two different arguments to your function

Assume both are greater than 9. You can also assume the denominator is strictly larger than the numerator.

# Output

A Truthy value if the fraction is *phony* and a Falsy value if it is not.

# Test cases

(Please keep an eye out for the comments, as some people have really nice test case suggestions! I'll edit them in, but sometimes I don't do it immediately.)

## Truthy

```
69/690 = 9/90
99/396 = 9/36
394/985 = 34/85
176/275 = 16/25
85/850 = 5/50
59/295 = 5/25
76/760 = 6/60
253/550 = 23/50
52/520 = 2/20
796/995 = 76/95
199/796 = 19/76
88/583 = 8/53
306/765 = 30/75
193/965 = 13/65
62/620 = 2/20
363/561 = 33/51
396/891 = 36/81
275/770 = 25/70
591/985 = 51/85
165/264 = 15/24
176/671 = 16/61
385/781 = 35/71
88/484 = 8/44
298/596 = 28/56
737/938 = 77/98
495/594 = 45/54
693/990 = 63/90
363/462 = 33/42
197/985 = 17/85
462/660 = 42/60
154/451 = 14/41
176/374 = 16/34
297/990 = 27/90
187/682 = 17/62
195/975 = 15/75
176/473 = 16/43
77/671 = 7/61
1130/4181 = 130/481

```

## Falsy

```
478/674
333/531
309/461
162/882
122/763
536/616
132/570
397/509
579/689
809/912
160/387
190/388
117/980
245/246
54/991
749/892
70/311
344/735
584/790
123/809
227/913
107/295
225/325
345/614
506/994
161/323
530/994
589/863
171/480
74/89
251/732
55/80
439/864
278/293
514/838
47/771
378/627
561/671
43/946
1025/1312

```

You can check this reference implementation that I used to generate some *phony fractions* by brute-force.

---

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

# Answer
> 14 votes
# , 22 bytes

```
%&".e.=/#&,%/&(1".\.])

```

Try it online!

quick explanation for now:

1. take the input as strings
2. `%/&(1".\.])` creates a function table `%/` whose axes are the integer `".` lists formed by the 1-outfixes `\.` (remove 1 digit at a time) of both args, and whose cells are the quotients of those numbers
3. `=/` forms a corresponding function table of the same shape, which acts as a boolean mask which is only `1` when corresponding "removed" digits are equal
4. `#&,` Flattens `,` both function tables into lists and uses the boolean mask to filter `#` the quotients, since cancelling is only valid when the digits are equal
5. `%&".` the true quotient of the inputs after converting to ints
6. `e.` is that true quotient an element of the filtered list from step 4.

# Answer
> 12 votes
# Python 3, 86 bytes

```
lambda a,b:g(a)&g(b)
g=lambda s:{(int(s[:i]+s[i+1:])/int(s),x)for i,x in enumerate(s)}

```

Try it online!

*-8 bytes thanks to ovs*

Making use of the fact that the boolean value for `a0/b0==a/b` is equivalent to `a0/a==b0/b`. The helper function `g` generates all ratios `a0/a` and keeps track of the removed digit. Then it does the same for `b0/b`. The main function determines the intersection of the two sets.

Returns a non-empty set (boolean True in Python) if a match is found, and an empty set (boolean False in Python) otherwise.

# Answer
> 6 votes
# 05AB1E, ~~26~~ ~~23~~ 22 bytes

```
€æ`âεR*Ë9ÝºIJySõ.;å*}à

```

-3 bytes thanks to *@Grimmy*.

Input as a pair `[numerator, denominator]`.

Try it online or verify all test cases.

**Explanation:**

```
€æ         # Get the powerset of each number in the (implicit) input-pair
  `        # Push both lists separated to the stack
   â       # Create all possible pairs by taking the cartesian product
ε          # Map each pair to:
 R         #  Reverse the pair
  *        #  Multiply it by the (implicit) input-pair
   Ë       #  Check if both values are the same
 9Ý        #  Push a list in the range [0,9]
   º       #  Mirror each horizontally: [00,11,22,33,44,55,66,77,88,99]
 IJ        #  Push the input, joined together
   y       #  Push the pair we're mapping again
    S      #  Convert it to a flattened list of digits
     õ.;   #  Remove the first occurrence of those digits in the joined input,
           #  by replacing each first occurrence with an empty string
 å         #  Check if what remains is in the list of doubled digits
        *  #  And check if both that and the earlier check are truthy
}à         # After the map: check if any where truthy by taking the maximum
           # (after which this is output implicitly as result)

```

The `R*Ë` checks with input-pair \\$\[a,b\]\\$ and potentially reduced pair \\$\[c,d\]\\$ whether \\$a×d=b×c\\$ (source).

# Answer
> 5 votes
# Jelly,  ~~18~~  17 bytes

```
DḌ-Ƥż$€÷þ/Ẏċ÷/,1Ɗ

```

A monadic Link accepting a list, `[numerator, denominator]` which yields zero (falsey) if not reducible, or a positive integer (truthy) if reducible.

**Try it online!** Or see the test-suite.

### How?

```
DḌ-Ƥż$€÷þ/Ẏċ÷/,1Ɗ - Link: [n, d]
D                 - decimal digits (vectorises)
     $€           - last two links as a monad for each:
  -Ƥ              -   for overlapping 1-outfixes (i.e. less 1 digit):
 Ḍ                -     un-decimal
    ż             -   zip (with digits - these are in the same order)
         /        - reduce by:
        þ         -   outer-product with:
       ÷          -     division -> [outfixesDivided, digitsDivided]
          Ẏ       - tighten (to a list of pairs)
                Ɗ - last three links as a monad:
             /    -   reduce ([n, d]) by:
            ÷     -     division
               1  -   one
              ,   -   pair -> [n÷d, 1]  i.e. digitsDivided must be 1
           ċ      - count occurrences

```

Unfortunately enumerate, `Ė`, given a number, `n`, yields `[[1, n]]` not simply the first pair `[1, n]`, which would save a byte with `...ċ÷/Ė$`.

# Answer
> 4 votes
# T-SQL, 192 bytes

Returns -1 for true, 0 for false

```
WITH x as(SELECT substring(@n,number,1)b,substring(@,number,1)a,number
n FROM spt_values)SELECT~(1/~count(*))FROM x,x y
WHERE x.b=y.a AND x.b>0and 1*stuff(@,x.n,1,'')*@n=@*1*stuff(@n,y.n,1,'')

```

**Try it online**

# Answer
> 4 votes
# JavaScript (ES6),  ~~100~~  93 bytes

*Saved 7 bytes by using @Jitse's method*

Takes input as `('numerator')('denominator')`. Returns a Boolean value.

```
n=>d=>(g=n=>[...n].map((x,i)=>x+-(n.slice(0,i)+n.slice(i+1))/n))(n).some(v=>g(d).includes(v))

```

Try it online!

# Answer
> 4 votes
# Perl 6, 58 bytes

```
{[(&)] .map:{m:g/./>>.&{(.prematch~.postmatch)/.orig~$_}}}

```

Try it online!

Same approach as in Jitse's Python answer.

### Alternative, 75 bytes

```
{?grep {[==] $_ Z*$^m[(3,4),(0,2)]>>.join},m:ex/^(.*)(.)(.*)\s(.*)$1(.*)$/}

```

Try it online!

Same regex-based approach as in Neil's Retina answer.

# Answer
> 4 votes
# Jelly, 22 bytes

```
DżḌ-Ƥ$€ŒpḢ€E$Ƈ÷/€F=÷/Ẹ

```

Try it online!

A monadic link taking a list of `[num, den]` and returning `1` for phony and `0` for non-phony.

## Explanation

```
D                      | Convert to decimal digits
     $€                | For each list of decimal digits:
 ż                     | - Zip with:
  Ḍ-Ƥ                  | - A list of lists of digits each one with 1 removed, that has then been converted back to a list of integers
       Œp              | Cartesian product
            $Ƈ         | Keep those where the following is true:
         Ḣ€            | - The heads of each list (which will be the removed digits)
           E           | - Are equal
              ÷/€      | Reduce each by dividing
                 F     | Flatten (to remove the nested lists)
                  =÷/  | Equal to the original argument reduced by division
                     Ẹ | Any

```

# Answer
> 3 votes
# Ruby, ~~109 86 81~~ 78 bytes

```
->n,d{g=->n,d{w=1;n.digits.map{|s|[s,d*(n%w+w*(n/w*=10))]}};g[n,d]&g[d,n]!=[]}

```

Try it online!

Saved some bytes by using multiplication instead of division: if `a/b==a0/b0`, then `a*b0==a0*b`.

Then stole some ideas from Jitse's excellent Python answer (upvote him!) to trim a couple of bytes off the corners.

# Answer
> 3 votes
# C (gcc), ~~128~~ ~~126~~ 124 bytes

```
P,h,o,n,_=10;i(e,s){for(n=P=1;e/P;P*=_)for(h=1;s/h;h*=_)e/P%_&&e/P%_==s/h%_&&(o=s/h/_*h+s%h,n*=!o|(e/P/_*P+e%P)*s-e*o);e=n;}

```

Try it online!

# Answer
> 3 votes
# Excel (Ver. 1911), 64 Bytes

Fraction entered as a row literal of 2 strings e.x. `={"16","64"}`

```
A1    'Input: row literal of 2 strings -> ={num,den}
C1:D9 {=SUBSTITUTE(A$1#,ROW(),,1)} 'Array formula (entered with <C-S-Enter>)
E1    =SUM((C1:C9/D1:D9=A1/B1)*(A1#<>C1#)) 'Output (truthy/falsy int)

```

### Test Sample

# Answer
> 2 votes
# Retina, 69 bytes

```
L$w`(.)(.*)/(.*)\1
$($`$2)*$($3$1$')*_/$($`$1$2)*$($3$')*
\b(_+)/\1\b

```

Try it online! Link includes test suite. Outputs the number of phony pairs of digit cancellations. Explanation:

```
L$w`(.)(.*)/(.*)\1

```

List all matching pairs of digits in the numerator and denominator, including overlaps.

```
$($`$2)*$($3$1$')*_/$($`$1$2)*$($3$')*

```

Cross-multiply each value with the digit removed from the other value.

```
\b(_+)/\1\b

```

Count how many times this results in the same answer, indicating that this digit cancellation was a phony fraction.

# Answer
> 2 votes
# Charcoal, 27 bytes

```
⊙θ⊙η∧⁼ιλ⁼×ＩΦη⁻ξμＩθ×ＩΦθ⁻ξκＩη

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for phony, nothing otherwise. Explanation:

```
 θ                          First input as a string
⊙                           Any character satisfies
   η                        Second input as a string
  ⊙                         Any character satisfies
      ι                     First character
     ⁼                      Equals
       λ                    Second character
    ∧                       Logical And
            η               Second input
           Φ                Filtered by
              ξ             Inner index
             ⁻              Minus (i.e. not equal to)
               μ            Second index
          Ｉ                 Cast to integer
         ×                  Multiplied by
                 θ          First input
                Ｉ           Cast to integer
        ⁼                   Equals
                     θ      First input
                    Φ       Filtered by
                       ξ    Inner index
                      ⁻     Minus (i.e. not equal to)
                        κ   First index
                   Ｉ        Cast to integer
                  ×         Multiplied by
                          η Second input
                         Ｉ  Cast to integer
                            Implicitly print

```

---
Tags: code-golf, math, arithmetic, integer, rational-numbers
---


title: Output a pretty box

text:
# Question
Title: Output a pretty box
Your challenge is to exactly output the following box:

```
..................................................
..................................................
..                                              ..
..                                              ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++                                      ++  ..
..  ++                                      ++  ..
..  ++  ..................................  ++  ..
..  ++  ..................................  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..................................  ++  ..
..  ++  ..................................  ++  ..
..  ++                                      ++  ..
..  ++                                      ++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..                                              ..
..                                              ..
..................................................
..................................................

```

The box is height and width 50, spaces are two wide.

You must write a function or program which outputs or returns a string and takes no input.

Fewest bytes wins!

# Answer
> 10 votes
## Pyke, ~~20~~ 17 bytes

```
k25V". + "ohe@A.X

```

Try it here!

```
k                 - out = ""
 25V              - repeat 25 times:
          oh      -     (o++)+1
            e     -    ^//2
    ". + "   @    -   " + ."[^] (wraps around)
              A.X -  out = surround(out, ^)

```

The surround function was made for questions like this!

# Answer
> 15 votes
## , 25 bytes

```
echo'. + '{~4|>./~2#|i:12

```

Try it online!

## Explanation

```
echo'. + '{~4|>./~2#|i:12
                     i:12  Range from -12 to 12.
                    |      Take absolute values,
                  2#       duplicate every element,
                /~         compute "multiplication table"
              >.           using maximum,
            4|             take mod 4 of every element,
    '. + '{~               index into this string,
echo                       print char matrix for everyone to see.

```

# Answer
> 11 votes
# C, 115 bytes

```
#define M(x,y)x<(y)?x:y
f(i){for(i=2549;i;i--)putchar(i%51?". + "[(M(i%51-1,M(50-i%51,M(i/51,49-i/51))))/2%4]:10);}

```

Defines a function `f` (call as `f();`) that prints the string to STDOUT.

# Answer
> 9 votes
# C, ~~535~~ ~~478~~ 477 Bytes

Now that's a lot of golf :-/

```
i;main(j){for(;++i<51;puts(""))for(j=0;++j<51;)putchar(i<3|i>48?46:j<3|j>48?46:i>4&i<47&j>4&j<47?i<7|(i>44&i<47)|(j>2&j<7)|(j>44&j<47)?43:j>8&j<43&((i>8&i<11)|(i>40&i<43))?46:i>9&i<41&((j>8&j<11)|(j>40&j<43))?46:i>13&i<37&((j>12&j<15)|(j>36&j<39))?43:((i>12&i<15)|(i>36&i<39))&j>12&j<39?43:i>17&i<33&((j>16&j<19)|(j>32&j<35))?46:((i>16&i<19)|(i>32&i<35))&j>16&j<35?46:i>21&i<29&((j>20&j<23)|(j>28&j<31))?43:((i>20&i<23)|(i>28&i<31))&j>20&j<31?43:i>24&i<27&j>24&j<27?46:32:32);}

```

Here's the output;

```
..................................................
..................................................
..                                              ..
..                                              ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++                                      ++  ..
..  ++                                      ++  ..
..  ++  ..................................  ++  ..
..  ++  ..................................  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..................................  ++  ..
..  ++  ..................................  ++  ..
..  ++                                      ++  ..
..  ++                                      ++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..                                              ..
..                                              ..
..................................................
..................................................

```

# Answer
> 6 votes
## Haskell, 72 bytes

```
q=(\n->[n,n]).abs=<<[-12..12]
unlines[[". + "!!mod(max x y)4|y<-q]|x<-q]

```

@Zgarb's solution in Haskell. I've also tried to construct the box by adding layers around the core `["..",".."]`, but it is 9 bytes longer (81 bytes).

```
e!b=e:e:b++[e,e];s#c=(c!)<$>(c<$s!!0)!s
unlines$foldl(#)["..",".."]" + . + . + ."

```

# Answer
> 5 votes
# Stacked, noncompeting, 35 bytes

Try it here!

```
ε'.'3$' + .'2*tostr*+$surroundfold

```

Ungolfed:

```
'' '.  ++  ..  ++  ..  ++  ..' $surround fold

```

Quite simple. `surround` is a function that, well, surrounds an entity with a fill entity. For example, `(0) 1 surround` is `((1 1 1) (1 0 1) (1 1 1))`. `$surround` is `surround` as a function, not evaluated. `fold` takes an initial value, then something to fold over, then a function. In this case, `surround` is `fold`ed, surrounding the initially empty string `''` (equiv. `ε`) with each character of the string.

```
'.'3$' + .'2*tostr*+

```

This is first making a character string `$' + .'`, that, when multiplied by a number, repeats each character. This leaves us with: `++ ..`. This is then casted to a string. Then, we repeat this string thrice, and finally prepend a `.`, giving us the desired string.

---

A different approach for 39 bytes:

```
' .'3$' + .'2*tostr*+toarr$surround#\out

```

`#\` is insert and takes the initial char of the string as the starting value. It also only works on Arrays.

# Answer
> 4 votes
# Jelly, 18 bytes

```
12ŒRAx2»þ`ị“ + .”Y

```

Try it online!

Same approach as Zgarb’s J answer: `12ŒRA` is `abs([-12 … 12])`, `x2` repeats every element twice, `»þ`` creates a table of maximums, `ị“ + .”` cyclically indexes into a string, and `Y` joins by newlines.

# Answer
> 4 votes
## JavaScript (ES6), 117 bytes

```
f=(n=12,c=`. + `[n%4],t=c.repeat(n*4+2))=>n?t+`
${t}
${f(n-1).replace(/^|$/gm,c+c)}
${t}
`+t:`..
..`
console.log(f())
```

Nonrecursive solution took me 128 bytes:

```
console.log([...Array(100)].map((_,i,a)=>a.map((_,j)=>`. + `[j=j>50?j-50:51-j,(i>j?i:j)%8>>1],i=i>50?i-50:51-i).join``).join`\n`)

```

Where `\n` represents the literal newline character.

# Answer
> 4 votes
# C, 97 bytes

```
i,x,y;main(){for(;i<2550;putchar(++i%51?". + "[(x*x<y*y?y:x)&3]:10))x=i%51/2-12,y=i/102-12;}

```

# Answer
> 3 votes
# 05AB1E, ~~39~~ ~~35~~ 33 bytes

```
•â3fM~•3B…012… .+‡.pvyD¤sg25s-×«Â«})Â«»

```

Try it online!

```
•â3fM~•3B                               # Push 1100220011002200110022001
         …012… .+‡                      # Push ..  ++  ..  ++  ..  ++  .
                  .p                    # All prefixes of the above string.
                    vy            }     # For each prefix.
                      D¤sg25s-×         # Repeat the last letter until length is 25.
                               «Â«      # Concat, bifurcate, concat.
                                   )Â«» # Wrap to array, bifurcate, concat, print.

```

---

33 Byte version that is cooler now because Emigna commented saving me 2 bytes:

```
". + "DøJ3×'.«.pvy¤25yg-×«Â«})Â«»

```

Try it online!

# Answer
> 3 votes
# Python 3, 89 bytes

```
r=range(-24,26)
for i in r:print("".join([". + "[max(abs(i//2),abs(j//2))%4]for j in r]))

```

Try it online!

# Answer
> 2 votes
# MATL, 21 bytes

```
'. + '[]25:"TTYaQ]2/)

```

Try it online!

```
'. + '    % Push this string
[]        % Push empty array. This will be used as "seed"
25:"      % Do the following 25 times
  TTYa    %   Extend the array with a frame of zeros
  Q       %   Add 1 to each entry
]         % End
2/        % Divide by 2
)         % Index modularly into the string. Non-integer indices are rounded
          % Implicitly display

```

# Answer
> 2 votes
# Octave, 53 bytes

```
 '.  ++  .'(mod(bsxfun(@max,x=[24:-1:0 0:24],x'),8)+1)

```

Generate repeating pattern of 1 to 8 from center outward and use it as the index for extraction of elements of `. ++ .`

Try It Online!

# Answer
> 2 votes
# Ruby, 77 bytes

```
-623.upto(676){|i|print i%26>0?". + "[[(i%26-13).abs,(i/52).abs].max%4]*2:$/}

```

# Answer
> 2 votes
# Charcoal, 25 bytes

```
Ｆ…¹¦²⁶⁺×ι§. + ÷ι²¶‖Ｏ↗‖Ｃ↑←

```

Try it online! Link contains verbose mode for explanation

# Answer
> 1 votes
**Haskell, 385 Bytes**

```
    b 0 = ["..", ".."]
b n = f:f:s:s:m (b (n - 1)) ++s:s:f:f:[]
    where f = replicate (8*n+2) $ d
          s = l++replicate ((8*n)-6) ' ' ++r
          m (x:xs) = map (\x -> l ++ x ++ r ) $ t
          l = d:d:' ':' ':[]
          r = reverse l
          t = b (n - 1)
          d :: Char
          d | n `mod` 2 == 0 = '.'
            | n `mod` 2 == 1 = '+'
main = mapM_ putStrLn $ b 6

```

First round of code golf here... looking forward to seeing how others tackle this one.

Output:

```
..................................................
..................................................
..                                              ..
..                                              ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++                                      ++  ..
..  ++                                      ++  ..
..  ++  ..................................  ++  ..
..  ++  ..................................  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++      ++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..  ++++++++++  ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..              ..  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++  ..................  ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++                      ++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..  ++++++++++++++++++++++++++  ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..                              ..  ++  ..
..  ++  ..................................  ++  ..
..  ++  ..................................  ++  ..
..  ++                                      ++  ..
..  ++                                      ++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..  ++++++++++++++++++++++++++++++++++++++++++  ..
..                                              ..
..                                              ..
..................................................
..................................................

```

# Answer
> 1 votes
# Bash, ~~191~~ 184 bytes

```
echo H4sIALBITF4CA72WuQ0AIAzEeqagR8r+47EAgTyH01BZApPPLBvDKshMRR1Z4eghsUv1kbdcDfKSq0LucnXITa4S8eVqEU+uGjnL1SMnuT8Q/1QixFuIfyFyjKgXovaJPkb0ZGK+ELOSmPvEDkPsYxvgYU8W9gkAAA|base64 -d|gunzip

```

Can probably get smaller, but was smaller than my algorithmic attempts.

Update: Use --best on gzip for great power. Thanks orthoplex.

# Answer
> 1 votes
## C#, 203 bytes

Complete, readable program:

```
using System;
public class P
{
    public static void Main(string[] a)
    {
        Func<string> f = () =>
        {
            var z = 25;
            var t = "";
            Func<int, string> c = (q) => q % 4 == 0 ? ".." : (q % 4 != 2 ? "  " : "++");
            for (var y = 0; y < z; y++)
            {
                var l = "";
                for (var x = 0; x < z; x++)
                        l += ((y > z / 2) ? (x >= y | x < z - y) : (x < y | x >= z - y)) ? c(x):c(y);
                l += "\n";
                t += l + l;
            }
            return t;
        };

        Console.Write(f());
        Console.ReadKey();
    }
}

```

Golfed **function**:

```
()=>{var z=25;var t="";Func<int,string>c=(q)=>q%4==0?"..":(q%4!=2?"  ":"++");for(var y=0;y<z;y++){var l="";for(var x=0;x<z;x++)l+=((y>z/2)?(x>=y|x<z-y):(x<y|x>=z-y))?c(x):c(y);l+="\n";t+=l+l;}return t;};

```

# Answer
> 1 votes
# 05AB1E, 33 bytes

```
14G" . +"NL¤¸13N-.×«€D¨Â«èD})¨Â«»

```

Try it online!

**Explanation**

```
14G                               # for N in [1 ... 13]
   " . +"                         # push this string
         NL                       # push range [1 ... N]
           ¤¸13N-.×               # push a list of 13-N repetitions
                                  # of the last element of the above range
                   «              # concatenate the two ranges
                    €D            # duplicate each element
                      ¨           # remove the last element
                       Â«         # concatenate a reversed copy to the list
                         è        # use the elements of the list to index into the string
                          D       # duplicate the resulting string
                           }      # end loop
                            )     # wrap the strings in a list
                             ¨    # remove the last element
                              Â«  # concatenate a reversed copy
                                » # join the list on newlines

```

# Answer
> 1 votes
# PowerShell, ~~171~~ 151 bytes

```
($x=(1..12|%{' . +'[$_%4]}|%{($a+=$_+$_)})+"$a."|%{$c=if(++$i%2){('+','.')[($b=!$b)]}else{' '};$_.PadRight(25,$c)}|%{,($_+-join$_[25..0])*2});$x[23..0]

```

Try it online!

Ho-hum answer. I'm sure there's a shorter way (given the lengths of the other answers, I'm confident), but this shows some neat tricks.

### Explanation:

`1..12|%{' . +'[$_%4]}` generates an array of strings (of one character in length), in the correct pattern we need. Try it online!

We then add on `|%{($a+=$_+$_)})+"$a."` which takes the array and expands it sideways based on the previous row. Try it online!

Those strings are then sent into a loop, `|%{$c=if(++$i%2){('+','.')[($b=!$b)]}else{' '};$_.PadRight(25,$c)}`. Each iteration, we're choosing the correct character (either a plus, a dot, or a space), and then using the `.PadRight` function to pad out to the appropriate number of characters. Try it online!

Now, we have the foundation of the upper-right corner. We need to reverse each string `|%{,($_+-join$_[($z=25..0)])*2}` and append them together so we can get the top of the block. This is done with the `-join` command and indexing backward `25..0`. Additionally, we encapsulate the strings in an array `,(...)` and make 'em double `*2` so we get the whole top. Try it online!

That is all stored into `$x` and encapsulated in parens so it places the strings on the pipeline. Finally, we reverse `$x` (being sure to snip out the duplicate-duplicate middle row, else we'd have four `..` in the middle) and leave those on the pipeline. An implicit `Write-Output` sticks a newline between the strings, so we get that for free.

# Answer
> 1 votes
# PowerShell, ~~90~~ ~~75~~ 69 bytes

```
($r=25..1+1..25)|%{$y=$_
-join($r|%{'..  ++  '[($_,$y)[$_-lt$y]%8]})}

```

Try it online!

# Answer
> 1 votes
# Perl 5, ~~137~~ ~~135~~ ~~132~~ 123 bytes

```
for$i(0..24){$e=49-$i;map{$a[$_][$i]=$a[$_][$e]=$a[$i][$_]=$a[$e][$_]=substr'. + ',$i%8/2,1}$i..$e}print join'',@$_,$/for@a

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 21 bytes

```
". + "12Ýû€Dã€ßèJ50ô»

```

Inspired by *@Zgarb*'s J answer, so make sure to upvote him as well.

Try it online.

**Explanation:**

```
    12Ý              # Push a list in the range [0,12]
       û             # Palindromize it: [12,11,10,...,2,1,0,1,2,...,10,11,12]
        €D           # Duplicate each item in this list: [12,12,11,11,10,10,...]
          ã          # Create all possible pairs by taking the cartesian product with itself
           €ß        # For each pair, leave the lowest value
". + "       è       # (0-base) index those into the string ". + "
              J      # Join all those characters together to a single string
               50ô   # Split it into 50 lines
                  »  # And join those by newlines
                     # (after which the result is output implicitly)

```

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


title: Generate a secure password

text:
# Question
Title: Generate a secure password
# Task

Your task is to generate a password that is both secure and short in the fewest bytes possible given an integer seed as input.

# Input

No seed Or An integer seed

# Output

A password

# Scoring

Your score is how many seconds the password takes to crack on How secure is my password divided by (bytes * password length)

Scoring is unbalanced because this is for fun

# Answer
# APL (Dyalog Unicode), ∞

Full program. Does not need a seed.

```
⎕AV

```

Try it online!

`⎕AV` is the **A**tomic **V**ector, i.e. the code page: `"\u0000\b\n\r \f\u0006\u0007\u001B\t⌶ɫ%'⍺⍵_abcdefghijklmnopqrstuvwxyz\u0001\u0002¯.⍬0123456789\u0003⊢¥$£¢∆ABCDEFGHIJKLMNOPQRSTUVWXYZ\u0004\u0005ý·⍙ÁÂÃÇÈÊËÌÍÎÏÐÒÓÔÕÙÚÛÝþãìðòõ{€}⊣⌷¨ÀÄÅÆ⍨ÉÑÖØÜßàáâäåæçèéêëíîïñ[/⌿\\⍀<≤=≥>≠∨∧-+÷×?∊⍴~↑↓⍳○*⌈⌊∇∘(⊂⊃∩∪⊥⊤|;,⍱⍲⍒⍋⍉⌽⊖⍟⌹!⍕⍎⍫⍪≡≢óôöø\"#\u001E&´┘┐┌└┼─├┤┴┬│@ùúû^ü`∣¶:⍷¿¡⋄←→⍝)]\u001F §⎕⍞⍣"`
> 2 votes

# Answer
# 05AB1E, Infinite score.

Gets `Forever` on the password generator. So score is Infinite.

```
žĆ

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 11 bytes, score = Infinity

An evil password.

```
_=>1n<<666n

```

Try it online!

Generates:

```
306180206916083902309240650087602475282639486413866622577088471913520022894784390350900738
050555138105234536857820245071373614031482942161565170086143298589738273508330367307539078
392896587187265470464n

```

The final '**n**' in the output is what makes *howsecureismypassword.net* believe that there are enough distinct characters for this to take forever to crack.

Without it, it would take only 79,220,219,535,072,410,000,000,000,000 quinquagintillion years. :-)
> 1 votes

# Answer
# Python 3, ~~19~~ 6 bytes, Score: Inf

Whopping -13 thanks to @a'\_'

```
help()

```

Try it online!
> 1 votes

# Answer
# SOGL V0.12, 1 byte, score: Infinity

Since we can't win 05AB1E, what about a shorter solution? This program basically yields the full SOGL code page.

Try it Here!
> 0 votes

# Answer
# GolfScript, 4 bytes, score = Infinity

An evil password.

```
74,`

```

Try it online!

Generates:

```
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73]

```

The final '**\`**' is what makes *howsecureismypassword.net* believe that there are enough distinct characters for this to take forever to crack.

Without it, it would take only 79,220,219,535,072,370 quinquagintillion years. :-)
> 0 votes

# Answer
# brainfuck, 5 bytes, Score = Inf

```
+[+.]

```

Try it online!
> 0 votes

# Answer
# PHP, 10 bytes -\> Infinite score

```
phpinfo();

```

Try it online!

Basically a kind of port of @SurculoseSputum's python answer
> 0 votes

---
Tags: code-challenge
---


title: Tips for Golfing in BBC BASIC

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

# Answer
> 4 votes
Spaces after keywords are optional because of tokenisation. For example:

```
INPUT answer$
PRINT answer$
IF answer$ = 'Hi' THEN
  PRINT 'Hi!'
ENDIF

```

Can be shortened to

```
INPUTanswer$
PRINTanswer$
IFanswer$='Hi'THEN
  PRINT'Hi!'
ENDIF

```

The corollary of this is, a variable name cannot start with a keyword. So `PRINTa` is not a valid variable name. However `printa` is.

Spaces *before* keywords can be more tricky. Variable names can end with a keyword, so if variable name and keyword are run together they will be interpreted as a variable name.

For example the following gives a "no such variable" error because the variable `aPRINT` is not defined:

```
  a=7
  IF7=aPRINT"seven"

```

By rearranging this can be avoided:

```
  a=7
  IFa=7PRINT"seven"

```

This is a trivial example, but frequently rearranging an expression to end in a number or bracket instead of a variable name will enable you to eliminate a trailing space.

# Answer
> 2 votes
Choose your interpreter well.

Very few of us have access to an original BBC micro, There's a whole range of interpreters at http://www.bbcbasic.co.uk/bbcbasic.html . Each implementation is slightly different.

My preferred interpreter is the first one on the list, "BBC Basic for Windows" written by RT Russell and available for Linux through Wine. It covers virtually all the features of original BBC Basic, including for example sound through the windows API, and has many enhancements. Its IDE and help are easy to use and feature packed.

It frequently allows you to omit colons between statements (which other implementations also do to some extent, but less) and it does not require you to number the lines of your program. On the downside, it only handles strings up to 255 characters and the evaluation version is restricted to 16k memory.

The other major family of BBC basics is Brandy Basic and its derivatives. Written in C, this is extremely portable, but has less features. For example it does not include sound, and rather than simply ignoring sound commands the program crashes. It is however able to handle longer strings than R T Russell's implementation so I have used it on occasion. There is no modern IDE, but it replicates BBC Basic's commandline fairly well (so it's not difficult to use *if* you are already familiar with BBC Basic.)

# Answer
> 2 votes
Use VDU codes to perform graphics tasks.

All graphics in BBC basic was performed via machine-specific ASCII control characters. The `VDU` command exists to enable you to pass ASCII characters direct to the video controller.

For example in `PLOT101,500,300` (draw a rectangle whose diagonal corners are the last position of the graphics cursor and the new point 500,300) can be subsituted by `VDU25,101,500;300;` The coordinates are followed by `;` because they are double byte values. We can also replace `25,101,` by `25881;` which is the 16-bit little-endian representation of these 2 bytes.

Although this actually makes things longer when you have only one PLOT statement, if you have several it is shorter. When you have a long string of VDU codes every PLOT can be replaced by `25,` (or if you declare `a=25` simply by `a,`)

Here's an example of this technique: https://codegolf.stackexchange.com/a/26732/15599

Note that this is not just limited to `PLOT`. `MODE, GCOL, COLOUR, ORIGIN etc` can all work out shorter when expressed as a series of numeric values in a long `VDU` statement.

# Answer
> 1 votes
Use FN instead of PROC or GOSUB

GOSUB is very old fashioned. it requires a line number, so you have the following:

```
    GOSUB90
    .
    .
 90 dosomething
    RETURN

```

7 characters to call, 8 characters to define and return.

PROC doesnt require a line number. Here you have

```
    PROCa(x,y,z)
    .
    .
    DEFPROCa(x,y,z)
    dosomething
    ENDPROC

```

5 characters to call (excluding arguments), 13 characters to define and return

With FN you have

```
    q=FNa(x,y,z)
    .
    .
    DEFFNa(x,y,z)
    dosomething
    =1

```

5 characters to call (excluding arguments, but including the obligatory use of the return value.) 8 characters to define and return

FN wins pretty much all the time, especially if you can make use of the return value. If you have no arguments you can omit the brackets.

# Answer
> 1 votes
**Use Abbreviated Keywords**

Surprised this wasn't mentioned before, but BBC Basic supports abbreviated versions of keywords so that, eg:

`1 FOR X=1 TO 10 STEP 2:PRINT X:NEXT X`

Can be rewritten as (omitting space where possible too):

`1F.X=1TO10S.2:P.X:N.X`

Some keywords don't have abbreviations (eg, `IF`). The complete list is in the BBC Basic manual chapter 48, there's a handy copy here too.

The most surprising part is that abbreviations for some functions include the opening parenthesis, eg: `PRINT MID$("HELLO",3,2)` is abbreviated as `P.M."HELLO",3,2)` \- note the closing parenthesis is required even though the opening one was abbreviated away.

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


title: Smile! Just smile

text:
# Question
Title: Smile! Just smile
It's well known that **Brainf\*ck** is very bad at Kolmogorov-complexity problems, for example, it requires around 100 characters just to print "Hello world".

However, there might be texts where Brainf\*ck is just very good at.

Your task is now to write a program that takes no input, and it displays the following:

That is, a smiley face (ASCII 1, if you browser does not render it).

Brainf\*ck can do it in 2 characters.

```
+.

```

**Try to find a language that beats it!**

We assume your console can actually display that character (or your font has it, etc.).

Shortest code wins. If there are more of the same length, the first wins, but I'll upvote the others as well.

**EDIT:** I'm very sorry, I did not think the first post arrives this soon. A quick edit: the language has to be Turing-complete!

# Answer
## FALSE (2)

```
1,

```

All that reading about BF paid off! False is an ancestor of Brainfuck.
> 10 votes

# Answer
## C, 18 chars

Far from beating Brainf\**k, but as good as C can get (I guess).
Only works on little-endian platforms, must run without parameters.

```
main(c){puts(&c);}

```
> 8 votes

# Answer
# Micronetics System MUMPS 4.4 (7 chars)

```
w $c(1)

```
> 7 votes

# Answer
## Brainf\*ck (only 2 characters)

```
+.

```
> 5 votes

# Answer
Doesn't beat 2 chars, but:

## **PHP 11 chars.**

```
<?=chr(1)?>

```

---

For everyone saying you can simply place the smiley in php and it will output :

Running it with php.exe in the command line gives `Γÿǁ` and placing it in the browser gives `â˜º`

It does **not** work.
> 5 votes

# Answer
# DC - 2 characters

```
1P

```

It doesn't require any explanation.
> 5 votes

# Answer
### Golfscript, 3 characters

```
"☺"

```

Not a golfscript expert, but I don't believe there is a way to convert an integer into the corresponding ASCII character using only 1 character, so it seems like this is the shortest it can get
> 4 votes

# Answer
# PHP (1)

Technically this is a valid PHP file (a web server will happily serve it).
> 4 votes

# Answer
# LaTeX (51/77 characters)

Short solution

```
\documentclass{book}
\begin{document}
☺
\end{document}

```

Good solution (Compile with `latex main.tex`):

```
\documentclass{book}
\usepackage{wasysym}
\begin{document}
\smiley
\end{document}

```
> 3 votes

# Answer
# Q/k (9 chars)

Can't do it in 2 unfortunately.

```
-1"\001";

```

I seem to recall a bug in an older version of the interpreter which produced the other smile symbol in less characters. I'll look it up.

Edit: found the quirk. It only appears to work on windows versions of the interpreter:

```
q)1(1b);
☺

```
> 2 votes

# Answer
# J (3 chars)

```
'☺'

```

The code require appropriate font.

According to Wikipedia

> In the Wingdings font, the letter "J" is rendered as a smiley face (note this is distinct from the Unicode code point U+263A, which renders as ☺).
> 2 votes

# Answer
# Whitespace, 9 bytes

```

```

Try it online!

```
ssstl   push 1 on stack
tlss    output char

```
> 2 votes

# Answer
# Burlesque - 6 Characters

`,1L[sh`

Explanation:

`,` pops stdin. `1L[` pushes one and convert to char (by codepoint) `sh` is used to switch to pretty format. (Otherwise it would print a leading `'`).
> 1 votes

# Answer
## Tcl, 1

Displays a ☺ with some other stuff.
There are rumors that this also works with PHP or other languages.
> 1 votes

# Answer
## Arduino, 24

```
char a=1;Serial.print(a)

```
> 1 votes

# Answer
# Stax, 2 bytes

```
1]

```

Run and debug it
> 1 votes

# Answer
# Keg, 2 characters

Push the number 1 and print it. (Surprised that `1,` also works; -1 from Lyxal.)

```
1,

```

Try it online!

# Keg, 1 character

Keg is actually Turing-complete, and any unrecognized command acts as a push onto the stack.

Try it online!
> 1 votes

# Answer
# 05AB1E, 2 characters

Just a boring hard-coding. It's encoded in CP437.

```
"☺

```

Try it online!

# 05AB1E, 2 bytes

Try it online!
> 1 votes

# Answer
# chevron \- 4 bytes/2 runes

```
>☺

```
> 1 votes

# Answer
# Perl 6 (7 chars)

```
say '☺'

```

I'm bending the rules a little by assuming that a \n is welcome to avoid shell prompt mess.
> 0 votes

# Answer
# JavaScript, 10 Bytes

```
alert("☺")

```
> 0 votes

# Answer
# SmileBASIC, 3 characters

```
?"☺

```

> 0 votes

# Answer
# PowerShell, 5 bytes

if a program should output the smile face char.

```
'☺'

```

Try it online!

---

# PowerShell, 7 bytes

if a program should output the char with code 1.

```
[char]1

```

Try it online!
> 0 votes

# Answer
# Gol\>\<\>, 2 bytes

```
1H

```

Try it online!

Just for completeness. Push a single 1, print all the contents as characters and halt.
> 0 votes

# Answer
# MineFriff, 5 bytes

```
C1,o;

```

Try it online!

Simply:

* Treat the temp register as a character
* Add one to the register and push
* Output the top item and finish.
> 0 votes

# Answer
# C (gcc), 15 bytes

```
f(){puts("☺");}

```

Try it online!
> 0 votes

---
Tags: code-golf, kolmogorov-complexity
---