title: Minimum cost block diagonalisation

text:
# Question
Title: Minimum cost block diagonalisation
Consider binary block diagonal matrices which have square blocks of 1s on the main diagonal, and are 0 everywhere else. Let's call such matrices "valid" matrices.

For example, here are some valid 4x4 matrices:

```
1 0 0 0     1 1 0 0     1 0 0 0     1 0 0 0     1 1 0 0    1 1 1 1
0 1 0 0     1 1 0 0     0 1 1 0     0 1 1 1     1 1 0 0    1 1 1 1
0 0 1 0     0 0 1 0     0 1 1 0     0 1 1 1     0 0 1 1    1 1 1 1
0 0 0 1     0 0 0 1     0 0 0 1     0 1 1 1     0 0 1 1    1 1 1 1

```

Note that an alternative way of describing such matrices is that there is a chain of square 1 blocks from the top-left to the bottom-right, touching corner to corner, and everywhere else is 0.

For contrast, here are some invalid 4x4 matrices:

```
1 0 1 0     1 0 1 0     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 1 1 1     0 1 0 1     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
1 0 0 1     1 0 1 0     0 0 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 0 1 0     0 1 0 1     0 0 0 1     1 0 0 0     0 0 1 1    0 0 0 0

```

You will be given an `n` by `n` binary matrix as input – what is the minimum number of `0` bits you'll need to set to `1` in order to get a valid matrix?

You may write a function or program taking in any convenient string, list or matrix format representing an `n` by `n` matrix of 0s and 1s (as long as it isn't preprocessed). Rows must be clearly separated in some way, so formats like a 1D array of bits are not allowed.

This is , so the goal is to minimise the number of bytes in your program.

## Examples

For example, if the input is

```
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1

```

then the answer is 5, since you can set five `0` bits to `1` to get:

```
1 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 1 0
0 0 0 0 1

```

and this is the minimum number required. However, if the input was

```
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

```

then the answer is 24, since the only valid 5x5 matrix where the top-right is `1` is the matrix of all `1`s.

## Test cases

Tests are represented here as a 2D array of integers.

```
[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

```

## Notes

# Answer
# MATL, ~~46~~ 43 bytes

```
nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

```

Input is a 2D array with semicolon as row separator. For example, the input for the last test case is

```
[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

```

Try it online! Or verify all test cases (code slightly modified to take all inputs; the results appear after a few seconds)

### Explanation

Let the input be an *N*×*N* matrix. The code first computes all (*N*+1)-tuples of block sizes that produce the appropriate matrix size. For example, for *N*=4 the tuples are `0 0 0 0 4`, `0 0 0 1 3`, ..., `4 0 0 0 0`. For each tuple it builds the block-diagonal matrix with those block sizes. It then checks if the matrix covers all the `1` entries in the input, and if so takes note of the number of `1` entries that were not present in the input. The final result is the minimum of all the obtained numbers.

```
nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display

```
> 3 votes

# Answer
## Python with numpy, 102

```
from numpy import*
lambda M:sum(diff([k for k in range(len(M)+1)if(M|M.T)[:k,k:].any()-1])**2)-M.sum()

```

An efficient algorithm. Finds the "neck points" on the diagonal that can separate blocks. These have all 0's above and right, as well as below and left. The minimal blocks are those between neck points.

```
??000
??000
00???
00???
00???

```

The length of a block is the difference between consecutive neck points, so their total area of the sum of squares of these. Subtracting the sum of the original matrix then gives the number of flips needed from 0 to 1.
> 3 votes

# Answer
# Pyth, 45 bytes

```
-hSlMf@I.DRlQx1sQTms.b^+LsYN2d+0._ds.pM./lQss

```

Difficult task, so it's quite long.

Try it online: Demonstration or Test Suite

### Explanation:

`s.pM./lQ` computes all integer partitions of `len(matrix)`. `ms.b^+LsYN2d+0._d` converts them into coordinate-pairs. For instance the partition `[1, 2, 2]` of `5` gets converted into `[[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4]`.

`f@I.DRlQx1sQT` then filters for partitions, that completely overlap the matrix (`.DRlQx1sQ` computes all coordinate-pairs of the active cells in the matrix).

`-hSlM...ss` counts the cells of each remaining partitions, chooses the one with the least cells, and subtracts the already active cells.
> 2 votes

# Answer
# Matricks, 180 bytes (noncompeting)

Matricks is a new esolang I created very recently to deal with matrix problems (such as this one), by only having 2 data types: floats and matricies. It is not fully featured yet, and still has a lot of missing operations (I had to add some functionality for this challenge). Anyway, here's the code:

```
il=1:j3;:bdx;;;s1::L;j1;;
b{q:1;mgr:c;|gc:r;|(r=c)|(gr-1:c;|gr:c+1;)&(rec)|(gr+1:c;|gr:c-1;)&(cer):l:L;};z:(l-1)/2;B1;s1::g1:;-1;ig1:;=0:j2;:j1;;
s1::d{q:1;};;kg1:;-g:;;
kg:;*-1+1;

```

## Explanation

The first part, `il=1:j3;:...;` checks if the array is of size 1. If it is, it jumps to the last line, `kg:;*-1+1;`, which is a simple `0 <-> 1` function.

Otherwise, it continues on with the rest of the code. `bdx;;;` sets the cell `0,0` to the current sum, and `s1::L;j1;` creates a counter in the cell in the row below.

The next line is a bit more complicated. It is a loop that runs `n` times, `n` being the size of the matrix. I'll use the 3rd test case as an example. When we first get to the second line, the matrix looks like this:

```
1 0 1
2 0 0

```

First, we go into the matrix comprehension `{q:1;m...;}`. This makes the diagonal, and tries its best to clean up 0 that need filling in. All this is accomplished using simple boolean operators. Then, we prepend it to the current matrix, giving this:

```
    V--data we want to keep
1 1 1 0 1 <-|
1 1 2 0 0 <-- old matrix

```

Then, we cut of the old matrix using `z:(l-1)/2;`, and rotate the entire matrix to the left using `B1;`. That gives us a matrix ready for the next iteration, looking like:

```
1 1 1
2 1 1

```

Finally, we decrement the counter, check it, and continue with `ig1:;=0:j2;:j1;;`

Once the loop is broken out of, we find the new sum and set the counter's old spot with `s1::d{q:1;};;`. Finally, we take the difference and return `kg1:;-g:;;`. `k` sets the current array to a value, and printing is implicit.

...

As you can see, **Matricks** is pretty verbose, and not a very good golfing language. But heck, I wanted to show it off.
> 0 votes

---
Tags: code-golf, array
---


title: Make a directory tree

text:
# Question
Title: Make a directory tree
Imagine for a second that you can compose a tree out of dots.

```
       .
      ...
     .....
    .......
   .........
  ...........
 .............
...............
      ...
      ...

```

This tree is 13 dots tall.

Now imagine for a second that your filesystem looked like these dots. Your task in this challenge is to make a tree out of folders.

# The Challenge

Given an input integer (let's call it `n`), make a tree out of subdirectories.

1. In each tree, you should start with a folder called 1.
2. In that folder, put the folders 1, 2, and 3.
3. In every level of folder thereon until `n-3`, in folder 1 of this level of the tree, there should be a folder labelled 1 and 2. In folder 2 of this level of the tree, there should be a folder called 3, in folder 3, a folder called called 4, and so on until the last folder (the integer this folder is called, we'll call `k`), in which there should be a folder called `k` and one called `k+1`.
4. At level `n-3`, however, all of the subdirectories but the middle three folders should be replaced with a file with the name that the subdirectories would have had. The middle three subdirectories should remain as subdirectories.
5. These three subdirectories should contain a folder called 1, 2, or 3 with respect to the order of these directories' name.
6. These are followed by a layer of files where 1 is in folder 1, 2 is in folder 2, and 3 is in folder three.

The example shown at the top of this question is represented below in folder form.

This would be `n = 13`.

# Rules

* You may use builtins for folder creation, but not for subdirectory creation.
* All other standard loopholes apply.
* You must support past n=5, but do not have to support greater than n=30.

# Answer
# Windows Batch File, ~~429~~ ~~423~~ 404 bytes

```
md 1
set C= call:
set/a M=%1-2
%C%f 1 1 2 L
%C%f 1 2 2 M
%C%f 1 3 2 R
goto:eof
:f
md %1\%2
set/a P=%2+1
set/a Q=%2+2
set/a L=%3+1
set D= (%C%t %1\%2\%P%
if %L%==%M% (if %4==L .>%1\%2\1
if %Q%==%M%%D%1)else (if %P%==%M%%D%2)else (if %2==%M%%D%3)else .>%1\%2\%P%))
if %4==R .>%1\%2\%Q%
)else (if %4==L%C%f %1\%2 1 %L% L
%C%f %1\%2 %P% %L% M
if %4==R%C%f %1\%2 %Q% %L% R)
goto:eof
:t
md %1\%2
.>%1\%2\%2

```

Call it with the value of n as a command line parameter.

Here is a visualization of the output tree for n=9:

```
                   1
                +--+--+
                1  2  3
             +--+  |  +--+
             1  2  3  4  5
          +--+  |  |  |  +--+
          1  2  3  4  5  6  7
       +--+  +  |  |  |  |  +--+
       1  2  3  4  5  6  7  8  9
    +--+  |  |  |  |  |  |  |  +--+
    1  2  3  4  5  6  7  8  9 10 11
 +--+  |  |  |  |  |  |  |  |  |  +--+
 1  2  3  4  5  6  7  8  9 10 11 12 13
                |  |  |
                1  2  3
                |  |  |
                1  2  3

```
> 3 votes

---
Tags: code-golf, file-system
---


title: Solve a traffic intersection

text:
# Question
Title: Solve a traffic intersection
# The task

Write a program or function that takes a traffic intersection structure and outputs the sequence, in which vehicles will pass.

The output should contain at most four lines with the following format `#. x->y\n`, where `#` is a sequence number number, followed by the dot `.`, `x` and `y` are characters `["N", "E", "S", "W"]`. They should be separated by characters `->`. If you do not return an array of strings, each line must end with a `\n` (new line character) or equivalent to your system.

The input should take the following form:

* Part 1: four characters, each having the destination road for the source roads in order N, E, S, W (clockwise). The allowed characters are `N`, `S`, `W`, `E` or . Space means that there is no vehicle on particular road. For example string `S WE` means, that N vehicle wishes to go South, space means that there is no E vehicle, `W` means that S wishes to go West, `E` means West wishes to go East.
* Part 2 - a space or a single letter meaning which one is of the emergency vehicle.
* Part 3 - two characters determining which two roads have priority (eg. `NE` means that North and East both have higher priorities than both South and West). If it is easier for you, you may take lower priority roads (in that case `SW`).

In an unsolvable situation you are allowed to return a one-line string which is clear to the user, like `unsolvable`, `no solution` and similar. JavaScript users may take built-in `undefined` constant.

This is a code-golf, so the shortest answer in bytes wins.

# The rules of traffic

*Please note that some of the rules may not follow your country traffic rules. Some of them have been simplified to make the challenge easier. Do not use this question as a guide for real life traffic system.*

1. For the challenge you are allowed to use only right-side traffic.
2. The traffic intersection consists of exactly four roads which meet in one point. They are marked `N` (as for "North"), `S`, `W`, `E`. These letters should be used instead of `x` and `y` in the output example above.

3. On each road there is at most one vehicle. It is not guaranteed that there is a vehicle on each road. Each vehicle can drive in any of four directions, ie. turn left, turn right, go straight or make a U-turn.

4. If paths of two vehicles do not intersect (they do not collide), they can go at the very same moment. Paths do not collide, if two vehicles (the list might not be complete, but this is intentional, just to give you a clue):
    * come from opposite directions and both go straight, or at least one of them turns right,
    * come from opposite directions and both turn left,
    * come from opposite directions and one of them turns in any direction or makes the U-turn, while the other makes the U-turn,
    * come from orthogonal directions, the one to the left is turning right and the other does not make the U-turn
    > Some examples of not colliding paths below. Please note that on the third drawing any path of N would collide with the path of E, even if N makes a U-turn.

5. If two paths collide, it is necessary to use other rules. If two vehicles are on the same priority road (see below), the right of way is given to the vehicle that:
    * is comes from the road on the right side, if they come from orthogonal directions
    * turns right if the other turns left
    * goes straight or turns right if the other makes a U-turn.
    > In both examples below the E vehicle has right of way over the vehicle S.

> In the example below first goes W, then N, then E and last goes S.

> For this particular case the output of your program should be:

```
1. W->S
2. N->S
3. E->S
4. S->S

```
6. All drivers use turn signals and know where all others want to go to (for simplicity we assume that it is possible to distinguish between the left turn and the U-turn).
7. Sometimes roads are given priority signs, which are more important that the rules above. A road with higher priority has a priority sign (priority sign image). If the priority road does not go straight, also additional signs are used, like this one. The roads with lower priority have a yield sign or a stop sign (they are equivalent). None or exactly two different roads will have higher priority. The user of your program should be able to enter which roads have higher (or lower) priorities.
8. A vehicle that comes from the road with higher priority has the right of way over a vehicle coming from lower priority road, even if it is on its left side.
9. If paths of two vehicles coming from the roads with the same priority collide, above right-side rules are active.
> On the example below roads S and W have priority signs, which means that vehicles on N and E should give them the way. The S vehicle has the priority over the W vehicle, because it is on its right side, so goes first. Then goes W, because it is on the road of higher priority than E. The vehicle N has right of way from E, because it is on its right side. As the last goes E.

> For this particular case the output of your program should be:

```
1. S->W
2. W->N
3. N->S
4. E->W

```
10. It is possible that one (and no more) vehicle is an emergency vehicle, which has the priority regardless to which direction it comes from or goes to, and what sign it has (it always goes first). The program should allow the user to enter, which vehicle is an emergency vehicle. Considering that on the last example N is an emergency vehicle, N goes first, then S, W and as the last E.

> For this particular case with an emergency vehicle at N the output of your program should be:

```
1. N->S
2. S->W
3. W->N
4. E->W

```
11. If two vehicles are allowed to go at the very same moment (their paths do not collide and they do not have to give way to other vehicles), your program should find this out and return them as having the same sequence number
> On the example below paths of N and E as well as E and S or W and E do not collide. Because S has to give way to N and W give way to S, S cannot go simultaneously with E, etc. The N and E can. So at first N and E go together, than goes S, and W as the last.

> The proper output of your program should be:

```
1. N->W
1. E->E
2. S->W
3. W->N

```

> You are free to choose the order of lines `1` (`N->W / E->E` is equivalent to `E->E / N->W`)

12. Sometimes the traffic may lead to unsolvable situation, that does not allow any vehicle to go. In real life it is solved when one of the drivers voluntarily resigns from his right of way. Here, your program should output `unsolvable` etc., as mentioned in the first part of the question.
> Below is an example of unsolvable situation. E should give way to W, W should give way to S, and S should give way to E.

# Answer
## Q, 645 Bytes

```
r:{(1_x),*x}                                                    /rot
R:{x 3,!3}                                                      /-rot
A:4 4#/:@[16#0;;:;]'[(&0100011001111100b;&0001111101100010b;&0010001111000100b;0);(&0 6 2;&0 1 7;&0 3 3;0)]
K:,/{,'/A x}'3 R\3 0 2 1                                        /Konflick matrix
G:3 R\|E:"NESW"                                                 /E:NESW  G:WSEN NWSE ENWS SENW
m:{x-y*_x%y}                                                    /mod
t:{1=+/m'[_x%4;2]}                                              /orthogonal
w:{-1($x),". ",y[0],"->",y 1;}                               /write
b:{_x%4}                                                        /n-> base dir.
g:m[;4]                                                         /n-> turn
e:(!4)in                                                        /exists
d:{s:r a:e b x;R s&~a}                                       /right free
I:{(G[a]?x 1)+4*a:E?*x}                                         /"dd"->n
O:{E[a],G[a:b x]g x}                                            /n-> "dd"
P:{N::(y=4)&z~4 4;a@&0<a:(@[4#0;b x;:;4-g x])+(5*d x)+(24*e z)+99*e y}          /priority
H:{a::K ./:/:x,/:\:x; if[N&2 in *a;:,0N]; x@&{~|/x[;z]'y}[a]'[!:'u+1;u:!#x]}    /each set of concurrent movements
f:{i:I'(E,'a)@&~^a:4#x; i:i@p:>P[i;E?x 4;E?x 5 6]; {0<#x 1}{a:H x 1;$[a~,0N;-1"unsolvable";w[*x]'O'a];$[a~,0N;(0;());(1+*x;x[1]@&~x[1] in a)]}/(1;i);}

```

**COMMENTS**

Definitively, it's not short (nor simple) code. It can be (severely) compacted, but it's left as excercise to the reader (I've dedicated too much time to this problem).

I've included multiline commented solution, but assume newlines as 1 Byte and discard comments (from / to end of line) to count size

The main difficulty is to fully understand all rules. Early optimization of code length is incompatible with developing a solution for a complex problem. Nor bottom-up or top-down approach copes well with unreadable code.

Finally, I developed a decission table (conflict matrix) with 16 rows and 16 columns (for each direction combined with each possible turn). The values of the items are 0 (compatibility), 1 (preference for row), or 2 (preference for column). It satisfies all test, by I'm not sure that all possible situations are well covered

Source file must have k extension. Start interactive interpreter (free for non-commertial use, kx.com) and evaluate at prompt (as shown in 'test' paragraph)

**TEST**

```
q)f " WN    "
1. E->W
2. S->N

q)f " SW    "
1. E->S
2. S->W

q)f "SSSS   "
1. W->S
2. N->S
3. E->S
4. S->S

q)f "SWWN WS"
1. S->W
2. W->N
3. N->S
4. E->W

q)f "SWWNNWS"
1. N->S
2. S->W
3. W->N
4. E->W

q)f "WEWN   "
1. N->W
1. E->E
2. S->W
3. W->N

q)f " SWE   "
unsolvable

```

**EXPLANATION**

The base structure is the 'precedence matrix'

```
   N       E       S       W
   W S E N N W S E E N W S S E N W
NW 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
 S 0 0 0 0 0 1 1 0 0 0 1 1 2 2 2 2
 E 0 0 0 0 0 1 1 1 2 2 0 0 0 2 2 0
 N 0 0 0 0 2 2 0 0 0 2 0 0 0 0 2 0
EN 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0
 W 2 2 2 2 0 0 0 0 0 1 1 0 0 0 1 1
 S 0 2 2 0 0 0 0 0 0 1 1 1 2 2 0 0
 E 0 0 2 0 0 0 0 0 2 2 0 0 0 2 0 0
SE 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
 N 0 0 1 1 2 2 2 2 0 0 0 0 0 1 1 0
 W 2 2 0 0 0 2 2 0 0 0 0 0 0 1 1 1
 S 0 2 0 0 0 0 2 0 0 0 0 0 2 2 0 0
WS 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
 E 0 1 1 0 0 0 1 1 2 2 2 2 0 0 0 0
 N 0 1 1 1 2 2 0 0 0 2 2 0 0 0 0 0
 W 2 2 0 0 0 2 0 0 0 0 2 0 0 0 0 0

```

Meaning (by example)

* `m[NW][SE]` has 0 value (both movements are compatible -concurrent-)
* `m[EW][SN]` has 1 value (EW has priority over SN) NOTE.- other priority factors may alter this sentence (emergency vehicles, priority road, ..)
* `m[NE][SE]` has 2 value (SE has priority over NE) NOTE.- other priority factors may alter this sentence (emergency vehicles, priority road, ..)

The matrix can be constructed using four submatrix (4x4) types

```
  NESW  A    B    C    D
N DACB  0100 0001 0010 0000
E BDAC  0110 2222 0011 0000
S CBDA  0111 0220 2200 0000
W ACBD  2200 0020 0200 0000

```

The matrix is complemented with a function that assigns a priority to each movement. That function takes account of emergency vehicles, priority roads, orthogonal directions, type of turn and vehicles 'comming from right'

We sort movements by priority and applies matrix values. The resulting submatrix includes conflicts and priority of each movement.

* we analyze unsolvable cases (mutual conflicts)
* if not, we select most priority item and all movements compatible with it and not incompatible with previous incompatible movements, and create a set of movements allowed to go simultaneously
* Write that set of movements and iterate over the rest of candidates
> 8 votes

---
Tags: code-golf
---


title: Visualize Church numerals

text:
# Question
Title: Visualize Church numerals
# Background

### Visualizing λ-calculus terms

Famous lambda-juggler (and code golfer) John Tromp devised an interesting visualization of terms in the λ-calculus. In his words:

> abstractions (lambdas) are represented by horizontal lines, variables by vertical lines emanating down from their binding lambda, and applications by horizontal links connecting the leftmost variables.

For example, the lambda term λf.λx.f (f (f (f x))) corresponds to the visualization:

```
-------------------
 |   |   |   |
-------------------
 |   |   |   |   |
 |   |   |   |----
 |   |   |----
 |   |----
 |----
 |

```

Read it from top to bottom:

* The first horizontal line represents the first λ.
* The four lines descending from it represent the **f**s in the body.
* Similarly, the second horizontal line represents the second λ, and the single new line descending from it represents the **x** in the body.
* The rightmost **f** line and the **x** line are connected by a horizontal line representing an application **(f x)**.
* The next application is **(f (f x))**, et cetera.

### Church numerals

The Church numerals are a specific sequence of terms in the λ-calculus, taking on the following pattern:

```
0 = λf. λx. x
1 = λf. λx. f x
2 = λf. λx. f (f x)
3 = λf. λx. f (f (f x))
...

```

# Task

Given an input number **n**, print some ASCII art that visualizes the **n**th Church numeral. For instance, the example above is your target output when given **n = 4**. For **n = 0**, print:

```
---

---
 |
 |

```

# Test cases

Your answer must output **exactly** the same text (modulo trailing newlines) as this stack snippet for all integer inputs **n ≥ 0**:

```
function visualize() {
  var vin = document.getElementById('visualize-in');
  var vout = document.getElementById('visualize-out');
  var n = Number(vin.value);
  if (n < 0) n = 0;
  var line = '-'.repeat(4 * n + 3);
  var bars = function(k) { return '   |'.repeat(k).substr(2); };
  var img = [line, bars(n), line, bars(n + 1)];
  for (var i = n; i > 0; --i) img.push(bars(i) + '----');
  vout.innerHTML = img.join('\n') + '\n |';
}
```

```
<label for="visualize-in">n <input style="width:50px;" type="number" id="visualize-in" name="visualize-in" onchange="visualize()"/></label>
<pre style="background-color: #eff0f1" id="visualize-out"></pre>
```

This is , so the shortest code in bytes wins.

# Answer
> 4 votes
## Retina, ~~74~~ ~~67~~ 63 bytes

Byte count assumes ISO 8859-1 encoding.

```
.
 |
^
$.'$*----¶
\z
¶$` |
+`(.+\|) .+$
$&¶$1----
$
¶ |
  ¶
¶

```

Input is in unary, using any character except linefeeds as the digit.

Try it online!

### Explanation

```
.
 |

```

We start by turning each unary digit into  `|`  (note the trailing spaces). This gives us the second line of the output (plus two trailing spaces if the input is at least `1`).

```
^
$.'$*----¶

```

We match the beginning of the string in order to prepend the first line. This is done using some Retina-specific substitution features. `$*` repeats the character on the right as many times as its left arugment. `$.'` evaluates the number of characters to the right of the match. Since the match is only the beginning of the string this gives as many `-` as there are characters in the string and `---` appends three more. The  is an alias for a linefeed. So now we've got the first two lines.

```
\z
¶$` |

```

Now we append the next two lines. We do this by matching the end of the string and appending a linefeed, the entire string again and then  `|` to get the fourth line right.

```
+`(.+\|) .+$
$&¶$1----

```

Time for the applications. The leading `+` makes Retina repeat this stage until the output stops changing (in this case because the regex no long matches). The regex matches the entire last line, provided it contains a `|` follows by a space. We capture everything up to the `|` (which will be the second to last) in group `1`. We write the line back with `$&`, a linefeed, then group 1 (thereby dropping the last `|`) and then `----`.

```
$
¶ |

```

This just adds the final line containing only a single `|`.

```
  ¶
¶

```

Finally we need to get rid of the trailing spaces on the second line.

# Answer
> 2 votes
## JavaScript (ES6), 112 bytes

```
f=
n=>`${d=`-`.repeat(n*4+3)}
${(b=` |  `.repeat(n)).slice(0,-2)}
${d}
${b} |
${b.replace(/ \|  /g,`$' |----
`)} |`
;
```

```
<input id=i type=number min=0 oninput=o.textContent=f(this.value)>
<pre id=o></pre>
```

# Answer
> 2 votes
# Python, 201 bytes

```
from pylab import*
n=input()
p=array(list(' -|\n'))
a=zeros((n+5,n*4+4),int)
for k in range(n):l=4*k+5;a[:-k-1,l]=2;a[-k-2,l-3:l+1]=1
a[:,1]=2
a[1,-3]=0
a[0]=a[2]=1
a[:,-1]=3
print''.join(ravel(p[a]))

```

# Answer
> 1 votes
# Python 2, 138 bytes

```
def f(n,a=1):
 if ~n:b="---\n";c=" |";d="  "+c;print("-"*n*4+b+c*(n>0)+d*(n-1)+"\n"+"-"*n*4+b+c+d*n+"\n")*a+c+d*(n-1)+"-"*4*(n>0);f(n-1,0)

```

The function contains an extra parameter, but it is for internal use only. It has a default value and should be omitted when calling the function. I hope this doesn't violate the rules.

The function draws the first 5 rows, then recursively calls itself to draw the remaining rows.

Try it online

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


title: Recognize a vine

text:
# Question
Title: Recognize a vine
## Background

I have a bunch of old and grainy black-and-white images. Some of them depict vines climbing on a wall, others don't – your task is to classify them for me.

## Input and output

Your input is a rectangular 2D array of bits **A**, given in any convenient format. It will not be empty, but it's not guaranteed to contain both 0s and 1s. The array depicts a vine if the following conditions hold:

* The bottom row of **A** contains at least one 1. These are the roots of the vine.
* Every 1 in **A** is connected to the bottom row by a path of 1s that only goes left, right and down (not up, and not diagonally). These paths are the branches of the vine.

Your output is a consistent truthy value if the input depicts a vine, and a consistent falsy value otherwise.

## Examples

This array depicts a vine:

```
0 0 1 0 0 1
0 1 1 0 0 1
0 1 0 1 1 1
1 1 0 1 0 1
0 1 1 1 0 1
0 0 1 0 1 1

```

This input does not depict a vine, since there's a 1 at the middle of the right border that's not connected to the roots by a branch:

```
0 0 0 1 1 0
0 1 0 1 1 1
0 1 0 1 0 1
0 1 1 1 1 0
0 0 1 1 0 1

```

The all-0 array never depicts a vine, but the all-1 array always does.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

## Test cases

Truthy inputs:

```
1

0
1
1

01
11

0000
0111
1100
1001

1111
1111
1111
1111

001001
011001
010111
110101
011101
001011

1011011
1001001
1111111
0100000
0111111
1111001
1001111
1111101

0000000
0011100
0010100
0011100
0001000
1111111
0001000
0011100
0010100
0010100

```

Falsy inputs:

```
0

1
0

10
01

000
000
000

011
110
000

111111
000000
101011
111001

010010
001000
000010
110001

001100
111111
110101
010011
111011

000110
010111
010101
011110
001101

11000000
10110001
10011111
11110001
01100011
00110110
01101100
01100001
01111111

```

# Answer
> 26 votes
## Snails, ~~25~~ ~~19~~ 17 bytes

```
&
\0z),(\1dlr)+d~

```

Try it online!

### Explanation

Snails is a 2D pattern-matching language inspired by regex, which was originally developed for our 2D pattern matching language design challenge.

The `&` makes Snails try the pattern from every possible starting position and prints `0` or `1` depending on whether the pattern fails in any of them or matches in all of them.

Now Snails can work with implicit parentheses, so the pattern is shorthand for the following:

```
(\0z),(\1dlr)+d~

```

The `,` acts like a `*` in regex (i.e. match zero or more times), whereas the `+` is the same as in regex (match one or more times). So we start by matching `\0z` as often as necessary, which matches a single `0` and then allows the snail to reset its direction arbitrarily with `z`. This allows zeros in the input, provided a valid vine cell can be found anywhere else.

Then we match at least one `\1dlr`, which matches a single `1` and then allows the snail to reset its direction either down, left or right. Note that if the cell we've started at contains a `1` then we're only matching this part. It basically allows the snail to traverse a vine from a branch down to the roots.

Finally, we need to ensure that we did reach the ground by looking for an out-of-bounds cell (`~`) below (`d`).

# Answer
> 3 votes
## JavaScript (ES6), 135 bytes

```
s=>s.replace(/^[^1]*\n/,``).split`
`.map(s=>+`0b${s}`).reverse(g=(n,m,o=(m<<1|m|m>>1)&n)=>n-m?o-m&&g(n,o):n).reduce((m,n,i)=>g(n,n&m))

```

Note: Due to limitations of integer type, only works for vines of up to 31 characters wide. Explanation: Each row is bitwise ANDed with the adjacent row to determine the connection points, and then the `g` function is used to recursively expand the row horizontally until it can expand no more. For instance, if two adjacent rows are `1110111` and `1011100` then the connection points are `1010100` and this is then expanded to `1110110` and then `1110111` which then finds that the row is connected. If the `g` function fails then it returns zero which causes all subsequent `g` functions to fail too, and the result is then falsy. If the `g` function succeeds it returns the new row which is then propagated through the `reduce` to test the next row.

```
s=>s.replace(/^[^1]*\n/,``)         Remove irrelevant leading "blank" rows
    .split`\n`                      Split into lines
    .map(s=>+`0b${s}`)              Convert into binary
    .reverse(                       Process from bottom to top
     g=(n,m,o=(m<<1|m|m>>1)&n)=>     Expand row horizontally
      n-m?o-m&&g(n,o):n)             Check whether rows are connected
    .reduce((m,n,i)=>g(n,n&m))      Check all rows

```

# Answer
> 2 votes
# Python 2, 254 bytes

No libraries

```
def f(A,r=0,c=-1):
 B=A[r];R=len(A)-1;C=len(B);i=1 in A[R]
 if c<0:
    for j in range(R*C+C):
        if A[j/C][j%C]:i&=f(A,j/C,j%C)
    return i&1
 _=B[c];B[c]=0;i=_&(r==R)
 if _:
    if c>0:i|=f(A,r,c-1)
    if r<R:i|=f(A,r+1,c)
    if c<C-1:i|=f(A,r,c+1)
 B[c]=_;return i

```

Note that the second and third level indents are formed with tabs in the byte count.

Try it online

# Answer
> 1 votes
# Wolfram - 254

Spend some time making this work, so I'll just leave it here:

```
f[s_]:=(
v=Characters@StringSplit@s;
{h,w}=Dimensions@v;
g=GridGraph@{w,h};
r=First/@Position[Flatten@v,"0"];
g=VertexDelete[Graph[VertexList@g,
EdgeList@g/.x_y_/;Abs[x-y]>1yx],r];
v=VertexList@g;
v≠{}∧v~Complement~VertexOutComponent[g,Select[v,#>w h-w&]]{}
)

```

Basically I construct a grid graph with directed edges pointing up, remove vertices that correspond to 0s, check that bottom vertex components contain all vertices. Ridiculous, I know...

# Answer
> 0 votes
## Python + NumPy ~~204~~ ~~202~~ 195 Bytes

```
from numpy import*
def f(A):
 r,c=A.shape
 z,s=zeros((r,1)),array([0,2,c+3])
 B=hstack((z,A,z)).flat
 for i in range(1,(r-1)*(c+2)):
    if B[i]and not any(B[s]):return 1<0
    s+=1
 return any(B[i:])

```

Expects `A` to be a 2D numpy array.

Takes the matrix, pads zero columns left and right and flattens the matrix. `s` is a stencil that points to the left, right and lower element. The loop checks each element except the last line if it is `1` and at least one of its stencil is `1`, returns `False` otherwise. Afterwards, check if the last line contains any `1`.

Two testcases for you:

```
I1 = '001001\n011001\n010111\n110101\n011101\n001011'
A1 = array([int(c) for c in I1.replace('\n','')]).reshape(6,6)
print f(A1) #True

I2 = '001100\n111111\n110101\n010011\n111011'
A2 = array([int(c) for c in I2.replace('\n','')]).reshape(5,6)
print f(A2) #False

```

Edit1: `1<0` is shorter than `False`

Edit2: `flat` is a fine alternative to `flatten()` and using tabulators for the second intendation in the loop

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


title: How's your string theory?

text:
# Question
Title: How's your string theory?
Back to the basics! You're in you comp sci class again, except wiser and golfier. You have the tools, you have the power… but do you have the *skill*? Probably.

# Crash Course for the non-Computer Scientist (skip if you don't need it)

A string is symbolically represented by an arbitrary letter (usually, for our purposes, will be etc. Of course, we know a string as something like `"Hello, World!"` or `'Hello, World!'`, or, if you're the snarky Python user, `"""Hello, World!"""`.

An alphabet can be thought of as a set (i.e. no repeating characters) of symbols, of which strings can be made. For example, ; this is the binary alphabet, of which contains strings like and . These strings can said to be *strings over* , or, alternatively, .

The length of any string is denoted . For example, .

There is the empty or null string , which is equivalent to `""`. It is a valid string in over any alphabet. In other words, is the unique string satisfying the property .

The set is the set of all strings over for which .

The set is called the *Kleene closure* of , and is the set of all strings over . This can be considered the *language of* .

The concatenation of two strings and is denoted , and is the string containing the characters of followed by the characters of .

is said to be a prefix of if there is some string that satisfies the equality . (If , then is said to be a proper prefix of .)

The alphabet of a string is denoted , and is the minimal alphabet so that is a string over

The projection of a string relative to an alphabet is defined as

and is essentially the removal of all characters in not in .

---

# TL;DR

**Objective** Write a program, series of functions, series of programs etc. that can calculate as many of the following tasks as possible:

* (1) Calculate, given a string `s`, its length.
* (2) Arrive at, given a string `s` and an alphabet `Σ`, whether or not (output a truthy/falsy value) that string is over said alphabet.
* (1) Given an alphabet, arrive at whether or not (output a truthy/falsy value) the alphabet is valid (a valid alphabet can have no repeating characters, but is otherwise valid).
* (4) Given an alphabet `Σ` and a positive integer `n`, display .
* (6) Given an alphabet `Σ` and an integer `n`, display the first `n` entries in (Remember that `ε ∈ Σ`!)
* (1) Given a string `s` and a string `t`, output `st`.
* (3) Given a string `s`, output `Al(s)`.
* (5) Given a string `s` and an alphabet `Σ`, output `π<sub>Σ</sub>(s)`.

Input is given by a string or your language's closest equivalent for a string input, an array, tuple, or *n*-ordinate of characters for an alphabet (your language's closest equivalent), and a number for a number (or your language's closest equivalent, heaven forbid your language does not support numbers!).

Each task has a score (the number in parenthesis). Your submission's score is calculated as follows:

```
        sum points scored
score = —————————————————
         length of bytes

```

***Highest*** score wins.

## Bonuses

* ×4 final score iff you output (with the correct symbols!) the input query. E.g., outputting `\pi_{\{0,1\}}(012345678910111213)=01101111` for an input of `Σ = [0,1]; s = 012345678910111213`. (You may choose to do this in either HTML or (La)TeX. Either counts.)
* (I'm open to suggestions.)

# Answer
# APL, score 3

### Task 7: 3 / 1

This is a built-in that – according to this discussion – can be considered an unnamed function.

Try it online on TryAPL.
> 6 votes

# Answer
I think, under the current scoring system, my best score is:

# Pyth, 5/3

```
@wz

```

Task 8

---

# Pyth, 295/42 ~ 7.024

### Task 1: 1/2

```
lz

```

### Task 2: 2/4

```
!-wz

```

### Task 3: 1/3

```
.{z

```

### Task 4: 4/3

```
^zQ

```

### Task 5: 6/7

```
<s^LzQQ

```

Warning: Extremely slow.

### Task 6: 1/3

```
+zw

```

### Task 7: 3/2

```
{z

```

### Task 8: 5/3

```
@wz

```

Demonstration

Exactly two of these are not Pyth builtins, namely tasks 2 and 5.
> 3 votes

# Answer
# Mathematica, score 64033/52668 = 1.215785676

```
StringLength
StringMatchQ[#,#2..]&
#==DeleteDuplicates@#&
""<>#&/@Tuples@##&
Table[""<>#&/@#~Tuples~i,{i,#2}]&
#<>#2&
Union@Characters@#&
""<>StringCases@##&

```
> 2 votes

# Answer
# Pyth, score 1/2 = 0.5

> Challenge 1:
>
> ```
> lz
>
> ```
>
> Try it out
> 2 votes

# Answer
# CJam, score 3/3 = 1.00

Best score for the current definition of the scoring function counts only task 7:

```
r_&

```

This is a complete program, and scores 3 points with 3 bytes of code.

As bonus material, here are my solutions for all the tasks but task 5:

Task 1, score 1/2:

```
r,

```

Task 2, score 2/4:

```
rr-!

```

Task 3, score 1/5:

```
r__&=

```

Task 4, score 4/7:

```
rrim*S*

```

Task 6, score 1/2:

```
rr

```

Task 7, score 3/3:

```
r_&

```

Task 8: score 5/6:

```
rr_@--

```
> 2 votes

# Answer
# Ruby, score = 17 / 153 = 0.111

I've just started with the tasks, I'll try to solve all of them.

Task 1 (13 bytes):

```
a=->s{s.size}

```

Task 2 (33 bytes):

```
b=->s,a{s.chars.all?{|c|a[c]!=p}}

```

Task 3 (28 bytes):

```
c=->a{a.chars==a.chars.uniq}

```

Task 4 (88 bytes, awfully long...):

```
d=->a,n{a.chars.map{|e|e*=n}.join.chars.permutation.map(&:join).map{|e|e=e[0...n]}.uniq}

```

Tash 6 (12 bytes):

```
f=->s,t{s+t}

```

Task 7 (19 bytes):

```
g=->s{s.chars.uniq}

```

Task 8 (48 bytes):

```
h=->s,a{g='';s.chars.map{|c|a[c]==p ? 0:g+=c};g}

```
> 2 votes

# Answer
# Ceylon score 16/167 = 1/11 = 0.090909...

This code of length 176 defines for projection, size and the iterators, giving 5 + 1 + 4 + 6 = 16 points:

`import ceylon.language{S=String,B=Boolean}import ceylon.collection{H=HashSet}S al(S s)=>S(H{*s});B v(S s)=>s==al(s);S p(S a,S s)=>S(s.filter(a.contains));B i(S s,S a)=>s==p(a,s);S c(S s,S t)=>s+t;Integer(S)l=S.size;`

The alphabet is also provided in form of a string (a character iterable `{Character*}` would work just the same, but take more code space).

I did actually implement all of the functions, but the other ones took more length per point.

All of them formatted and commented:

```
import ceylon.language {
    S=String,
    I=Integer,
    B=Boolean
}

// minimal alphabet of a string → 3 points
// taken from http://codegolf.stackexchange.com/a/59789/2338
S b(S s) => S { for (x->c in s.indexed) if (!c in s[0:x]) c };

// is the alphabet valid? → 1 point
// we simply check if it is its own minimal alphabet.
B v(S a) => a == b(a);

// project string to alphabet → 5 points
S p(S a, S s) => S(s.filter(a.contains));
//  S p(S a, S s) => S(s.filter((c)=>c in a));

// is string s over alphabet a? → 2 points
// we check if the string is its own projection.
B i(S a, S s) => s == p(a, s);

// concatenate → 1 point
S c(S s, S t) => s + t;

// length of a string → 1 point
// uses a different syntax than the usual I l(S s) => s.size, because it is slightly shorter.
I(S) l = S.size;

// strings of length n over alphabet a → 4 points
{S*} x(S a)(I n) =>
// defined recursively.
        n == 0
        then { "" }
        else { for (s in x(a)(n - 1))
        for (c in a)
            S { c } + s };

// first n strings → 6 points
{S*} y(S a, I n) => expand((0..n).map(x(a))).take(n);

```

(I guess I could replace the `..` by `:` in the last line, but then the score wouldn't be so nice anymore.)
> 1 votes

# Answer
# Haskell, score=1/3

If function is not allowed, this submission is invalid.

The best score is task 8 with score (5/16).

Task 1(1/6):

```
length

```

I somehow misread Prelude.

Task 2(2/13):

```
all.flip elem

```

First argument is alphabet, the second is string

Task 3(1/32):

```
c[]=2>1;c(x:xs)=all(/=x)xs&&c xs

```

Sigh, is is overly long.

Task 4(1/16):

```
_#0=[[]];x#y=concatMap(flip map$x#(y-1))$map(:)x

```

Task 5(1/12):

```
_#0=[[]];x#y=concatMap(flip map$x#(y-1))$map(:)x;n&k=take k.map(n#)[1..]

```

Task 6(1/4 or 1/2):

```
(++)

```

I don't know if the paratheses is allowed to be dropped in this case

Task 7(3/32 or 3/22 or 3/20):

It is same as delete duplicates

```
a[]=[];a(x:y)=x:(a$filter(\=x)y)

```

If using library is not cheating

```
import Data.List
a=nub

```

Or even drop the `a=`

Task 8(5/16):

For Haskell it is ridiculously easy.

```
filter.flip elem

```
> 1 votes

# Answer
# Haskell, 5, possible cheating

(This was invalidated by a rules update.)

This strongly depends on how you interpret the minutiae of the grading rules.

```
$

```

I claim that this solves task 8 (5 points) in 1 byte for a reasonable interpretation of the inputs. I have asked for clarification and not really received much, so I am posting this solution in order to induce more discussion.

# The scope of the liberties I am taking

The freedom afforded to us is **not** "You have to use the most obvious thing that someone would use if they talked about a "string" in your language" but rather,

> Input is given by the most convenient method that does not complete anything for the challenge. E.g., you can accept a string for the first challenge, but not the length of the string.

I am choosing some methods as "convenient" which are convenient in two niche areas of programming. They do not "complete anything for the challenge" in the sense that neither one completes the challenge by itself, nor does the challenge have any well-defined subtasks (and if these challenges *did* have subtasks then builtins would likely be disallowed!).

## Stealing a lambda-calculus-style list

In lambda calculus the usual way that you encode a list is the Church encoding with direct reference to its `foldr`; a variant encoding will run the function on the empty list `[]`, it is constrained only in its output type and not in its function. In other words, `list_from_fn f = f (:); fn_from_list ls f = foldr f [] ls.` I think that this is relatively noncontroversial because this is in fact a usual way to think of a list in functional programming circles.

## Stealing a Clojure-transducer-style alphabet.

The specification of the alphabet is more contorted and may fall foul of the rather-vague rule. For my alphabet I find it quite convenient to use a filtering arrow, more precisely the sort of filtering arrow you'd see in the Kleisli representation of the List monad. So that requires maybe a bit of explaining: there are these functions from `a -> [b]` which are composed, in the Kleisli category, with the function `(.).concatMap`. A filtering arrow is the specific `a -> [a]` which has the form

```
filterArrow predicate a = if predicate a then [a] else []

```

So far, so good: an alphabet is equivalent to its filter which is equivalent to its filter arrow, which makes perfect sense in a certain class of applications. However, these applications ***are*** *used in practice*: the programming language Clojure a few years ago started a big hacker-media frenzy when they introduced this Kleisli category `a -> [b]` into mainline Clojure under the name "Transducers," with the only difference being that they were transformed with a bit of continuation-passing so that the order of the composition was reversed.

So both of those seem to be relatively straightforward and real programmers really use both.

## Where cheating may be occurring

However where I might be cheating is that I actually am expecting as "convenient" for the list function to be the *concatenating* foldr applied to the empty string, `(a -> [b]) -> [b]`. This is still 100% equivalent to a list, as evidenced by the isomorphism

```
list_from_fn f = f (:[])
fn_from_list ls f = foldr ((++).f) [] ls

```

however I do not have any prior art of its widespread usage to represent lists. It's quite possible that someone has done it before, but I can't prove it.
> 1 votes

# Answer
# dc: `1k 1 1+2 3+/p`: 0.4 points

Strings `s` and `t`, as applicable, must be present on the top of the stack at execution time, with `s` topmost.

## Calculate length of string `s`: 1pt, 2B

```
Zp

```

## Concatenate `s` and `t`: 1pt, 3B

```
rnn

```
> 1 votes

# Answer
# Java, score: 8 / 491 467 465 462 ~= 0.0173

I just wanted to see how many tasks I can figure out.

```
import static java.lang.System.*;interface a{static void main(String[]A){char[]Z=A[1].toCharArray();switch(A[0]){case"a":out.print(A[1].length());break;case"b":int b=1;for(char B:Z)b=A[2].contains(new String(c))?b:0;out.print(b>0);break;case"c":String B="";int c=1;for(char C:Z){c=B.contains(new String(C))?0:c;B+=C;}out.print(c>0);break;case"d":out.print(A[1]+A[2]);break;case"e":String C="";for(char d:Z)C+=C.contains(new String(d))?"":d;out.print(C);break;}}}

```

The program (ab)uses command line arguments to get the tasks done. Here's how it works (note that every argument should be enclosed in double quotes like `"arg1" "arg2" "arg3"`):

* If the first argument is `a`, the second argument's length is printed (calculates the length of a given string). Syntax: `a <string>`
* If the first argument is `b`, `true` is printed in case of the second argument being over the third argument, which is taken as an alphabet (given a string and an alphabet, find out if the string is over the alphabet). Syntax: `b <string> <alphabet>`
* If the first argument is `c`, `true` is printed if the second argument is a valid alphabet where every character occurs only once (given an alphabet, find out if it's valid). Syntax: `c <alphabet>`
* If the first argument is `d`, the concatenation of the second and third arguments is printed - the second argument comes first (given two strings, concatenate them). Syntax: `d <first string> <second string>`
* If the first argument is `e`, the smallest alphabet which the second argument is over is printed (given a string, find out its alphabet). Syntax: `e <string>`

Oh wait, let me ungolf the program for you:

```
import static java.lang.System.*;
interface a {
    static void main(String[] A) {
        char[] Z = A[1].toCharArray();
        switch (A[0]) {
        case "a":
            out.print(A[1].length());
            break;
        case "b":
            int b = 1;
            for (char B : Z)
                b = A[2].contains(new String(c)) ? b : 0;
            out.print(b > 0);
            break;
        case "c":
            String B = ""; int c = 1;
            for (char C : Z){
                c = B.contains(new String(C)) ? 0 : c;
                B += C;
            }
            out.print(c > 0);
            break;
        case "d":
            out.print(A[1] + A[2]);
            break;
        case "e":
            String C = "";
            for (char d : Z)
                C += C.contains(new String(d)) ? "" : d;
            out.print(C);
            break;
        }
    }
}

```
> 1 votes

# Answer
# Python 3, 27 / 158 ≈ 0.1709

I tried for as many tasks as possible instead of the highest score possible.

```
from itertools import*
L=len
lambda s,a:all(c in a for c in s)
lambda a:L(set(a))==L(a)
permutations
str.__add__
set
lambda s,a:filter(a.__contains__,s)

```

### Task 1:

```
L=len

```

Pretty self-explanatory. I assign it because it's used later, and naming it `L` saved 4 bytes.

### Task 2:

```
lambda s,a:all(c in a for c in s)

```

This maps `s` to a list of boolean values telling if the corresponding character is in the string. If they are all `True`, then `s` is over `a`.

### Task 3:

```
lambda a:L(set(a))==L(a)

```

Here's where I used that `len` rename. In Python, the `set` class is a container of unique objects, and if the constructor is given a container with duplicates, it removes them.

### Task 4:

```
permutations

```

The Python library function `itertools.permutations` does *exactly* what is needed.

### Task 5:

nope

### Task 6:

```
str.__add__

```

Shamelessly co-opting class methods. Not much else to say.

### Task 7:

```
set

```

Once again, the beautiful uniquefying `set` comes in handy. Here, it automatically finds the minimal alphabet.

### Task 8:

```
lambda s,a:filter(a.__contains__,s)

```

Filters out the characters in s `s` which are not also in `a`. Alternative with the same length: `[c for c in s if c in a]`
> 0 votes

---
Tags: string, code-challenge, logic, multiple-holes
---


title: Geobitsian Language

text:
# Question
Title: Geobitsian Language
*Geobitsian language* is a new perversion of English where a word is broken into segments that each must start with a different letter. Then every time one of those starting letters appears in another string, it is replaced with its entire corresponding segment, maintaining capitalization.

This process is called *Geobitsizing*.

For example the word "Geobits" could be broken into `geo bits`, and the nonsense poem

```
Algy met a Bear
A Bear met Algy
The Bear was bulgy
The bulge was Algy

```

would be Geobitsized with it as

```
Algeoy met a Bitsear
A Bitsear met Algeoy
The Bitsear was bitsulgeoy
The bitsulgeoe was Algeoy

```

because every `g` becomes `geo`, every `G` (though there are none) becomes `Geo`, every `b` becomes `bits`, and every `B` becomes `Bits`.

Note that each substitution is performed with respect to the original string, not any intermediate step. e.g. if `geo` had been `gbo` instead, the `b`'s created would not replaced with `bits`.

# Challenge

Write a program or function that can generate Geobitsian language.

Take in a single-line string made of lowercase letters (a-z) and spaces. This will be the word used as the Geobitsizing argument, with the spaces separating the segments. You can assume:

* Segments will not be empty. So spaces will not neighbor each other nor be at the start or end of the string.
* Each segment starts with a different letter. Thus there cannot be more than 26.

For example, some valid segmented strings you must support are `geo bits`, `butt ner`, `alex`, and `do o r k nob` (single letter segments have no effect but are valid). But `geo` , `butt ner`, `Alex`, and `do o r k n ob` are invalid.

Your program or function also needs to take in another arbitrary string to apply the Geobitsizing to, and print or return the resulting Geobitsian language.

* You can assume this string only contains newlines and printable ASCII.
* Remember that letter cases must be preserved from the input to the output.

Here are some more examples using `no pro gr am m ing` as the Geobitsizing argument:

`[empty string]``[empty string]`

`i``ing`

`I``Ing`

`Mmmm, mmm... MmmmMMM: m&m!``Mmmm, mmm... MmmmMMM: m&m!` (no change)

`People think bananas are great, don't you?``Proeoprole thingnok bamnoamnoams amre grreamt, dono't you?`

```
Pet a Puppy
Google Wikipedia

```

```
Proet am Prouproproy
Groogrle Wingkingproedingam

```

Note that the results should be identical no matter how the argument is arranged, e.g. `ing pro m no am gr` should yield the same results as above.

**The shortest code in bytes wins.**

# Answer
> 6 votes
# Jelly, 18 bytes

```
ṣ⁶;Œu1¦€$;©ZḢiÐ€ị®

```

Try it online!

### Alternative version, 15 bytes

Jelly's title case function had a bug; it didn't capitalize the first word. That has been fixed, so the following works now.

```
ṣ⁶;Œt$;©ZḢiÐ€ị®

```

This code does the same as in the competing version, except that `Œt` (title case) replaces the conditional uppercasing achieved by `Œu1¦€`.

### How it works

```
ṣ⁶;Œu1¦€$;©ZḢiÐ€ị®  Main link. Left argument: w (words). Right argument: s (string)

ṣ⁶                  Split w at spaces.
        $           Combine the two links to the left into a monadic chain.
       €              Map over the words.
   Œu1¦                 Uppercase the item at index 1.
  ;                   Append the result to the unmodified words.
         ;          Append all characters in s to the list of words.
          ©         Copy the result to the register.
           Z        Zip/transpose, grouping the first chars into the first list.
            Ḣ       Head; extract the list of first characters.
             iÐ€    Find the first index of each character in s.
                ị®  Select the characters/strings from the list in the register
                    that are at those indices.

```

# Answer
> 5 votes
# Python 3, 71 bytes

```
lambda w,s:s.translate({ord(t[0]):t for t in(w+' '+w.title()).split()})

```

Test it on Ideone.

### How it works

In Python *3*, the built-in `str.translate` takes a string and a dictionary, and replaces each character in the string whose code point is a key of that dictionary with the corresponding value, which may be a string, an integer or **None** (equivalent to the empty string).

Converting the string of words **w** to title case (i.e., capitalizing the first letter of each word) and appending it to the result of `w+' '` creates a string of space separated words with lower- and uppercase version (first letter). Without a second argument, `str.split` splits at whitespace, so `(w+' '+w.title()).split()` creates the *list* of all words.

Finally, the dictionary comprehension `{ord(t[0]):t for t in...}` turns each word **t** into a dictionary entry with key `ord(t[0])` (code point of the first letter) and value **t**, so `str.translate` will perform the intended substitutions.

# Answer
> 3 votes
## Python, ~~126~~ ~~99~~ ~~95~~ 81 bytes

Alot thanks to Dennis:

```
lambda G,S,j=''.join:j(s+j(g[1:]for g in G.split()if g[0]==s.lower())for s in S)

```

Edit1: don't need to append to a temporary

Edit2: `S` may contain uppercase...

Edit3: don't duplicate G

Edit4: compressed a little bit more and shoved it into one line

Edit5: using unnamed lambda and `j=join' '`

# Answer
> 2 votes
# Pyth, 19 bytes

```
.rzsC_hMBsm,rd0rd3c

```

Try it online!

# Answer
> 2 votes
# Vim, 46 keystrokes

Ugly, and Hacky.

```
A <esc>:s/\<\w/:%s\/\0\\c\/\\0/g<cr>:s/ /eg<C-v><Cr>/g<cr>dgg@"

```

# Answer
> 2 votes
# Python 2, ~~83~~ 78 bytes

```
lambda w,s:''.join(c+w[(' '+w).find(' '+c.lower()):].split()[0][1:]for c in s)

```

Test it on Ideone.

### How it works

We iterate over all characters **c** in the string **s**.

We prepend a space to the string of words **w**, then search for a occurrence of lowercased **c**, preceded by a space.

* If such an occurrence exists, `find` will return the index of the space in the string `' '+w`, which matches the index of **c** in **w**.

`w[...:]` thus returns the tail of **w**, starting from the word with first letter **c**. `split()` splits the tail at spaces, `[0]` selects the first chunk (the word) and `[1:]` removes its first letter.

After prepending **c** to the previous result, we obtain the correctly cased word that starts with **c**.
* If no word begins with **c**, `find` will return **-1**.

Thus, `w[...:]` yields the last character of **w**, `split()` wraps it in an array, `[0]` undoes the wrapping, and `[1:]` removes the only character from the string.

After prepending **c**, we obtain the singleton string whose character is **c**, so the whole operation is a no-op.

Finally, `''.join` concatenates all resulting strings, returning the Geobitsized version of **s**.

# Answer
> 2 votes
## Retina, 36 bytes

Byte count assumes ISO 8859-1 encoding.

```
i`(?<=^.*\b\2(\w+)[^·]*?(\w))
$1
A1`

```

Try it online!

# Answer
> 2 votes
# Pyth, ~~18~~ 16

```
MsXGhMJcjdrBH3)J

```

Try it here

Defines a function `g` that performs the geobitsising. As a program this would be a bit shorter if the second string is single line, but multiline input isn't worth it:

```
sXwhMJcjdrBz3)J

```

The general idea here was to title case the geobitsian string and append that to the original string. Then split that on spaces and for each string, take the first letter and map it to the string it represents. That way `X` will turn the first letter of each word into the full word.

# Answer
> 1 votes
# JavaScript ES6, ~~67~~ ~~63~~ 70 bytes

```
g=>s=>s.replace(/\S/g,l=>l+(g.match(`\\b\\${l}(\\S+)`,'i')||[,""])[1])

```

Test this on Firefox. bugs are making this longer than I'd like

## Explanation

```
function(gbarg, str) {
   return str.replace(/\S/g, function(chr) { // Replace non-whitespace w/...
        return chr + (
         gbarg.match(`\\b\\${l}(\\S+)`,'i')  // That word in the gbstr
        ||[,""])[1]                          // if not in gbstr, use blank str
   });
}

```

# Answer
> 1 votes
# Julia, ~~72~~ 68 bytes

```
w%s=prod(c->"$c"join((W=w|>split)[find(t->t[1]==c|' ',W)])[2:end],s)

```

Try it online!

# Answer
> 1 votes
## CJam, 19 bytes

```
lq\S/_32af.^+_:c\er

```

Test it here.

### Explanation

```
l       e# Read first line of input (list of words).
q\      e# Read remaining input and swap with first line.
S/      e# Split around spaces.
_       e# Duplicate.
32af.^  e# Convert the first letter of each word to upper case by taking
        e# the element-wise XOR with the list [32].
+       e# Append the upper-cased words to the original ones.
_:c     e# Duplicate and convert each word to its first character.
\       e# Swap characters with words.
er      e# Transliteration, replacing each character with the corresponding word.

```

# Answer
> 0 votes
# Ruby, ~~65~~ ~~60~~ 58 bytes

```
->w,s{s.gsub(/\w/){|c|w=~/\b#{c}(\w+)/i;c+($1||c)[1..-1]}}

```

Try it online!

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


title: The happy Ender problem

text:
# Question
Title: The happy Ender problem
The happy ending problem (actually a theorem) states that

> Any set of five points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral.

The problem was so named by Paul Erdős when two mathematicians who first worked on the problem, Ester Klein and George Szekeres, became engaged and subsequently married.

Clarifications:

* *General position* here means that no three points are collinear.
* The quadrilateral formed by the four vertices will always be considered to be non-intersecting, irrespective of the order of the points. For example, given the four points `[1 1]`, `[1 2]`, `[2 1]`, `[2 2]` the intended quadrilateral is the square, not the bow-tie:
* A non-intersecting quadrilateral is convex if no interior angle exceeds 180 degrees; or equivalently if both diagonals lie inside the quadrilateral.

## The challenge

Given 5 points with positive integer coordinates, output 4 of those points that form a convex quadrilateral.

## Rules

If there are several solutions (that is, several sets of 4 points), you can consistently choose to output one of them or all.

Input and output formats are flexible as usual (arrays, lists, list of lists, strings with reasonable separators, etc).

Code golf, fewest bytes wins.

## Test cases

1. Input:

```
[6 8] [1 10] [6 6] [5 9] [8 10]

```

There is only one possible output:

```
[6 8] [1 10] [6 6] [5 9]

```
2. Input:

```
[3 8] [7 5] [6 9] [7 8] [5 1]

```

There are five solutions:

```
[3 8] [7 5] [6 9] [7 8]
[3 8] [7 5] [6 9] [5 1]
[3 8] [7 5] [7 8] [5 1]
[3 8] [6 9] [7 8] [5 1]
[7 5] [6 9] [7 8] [5 1]

```
3. Input:

```
[4 8] [1 9] [9 9] [10 2] [1 6]

```

There are three solutions:

```
[4 8] [1 9] [10 2] [1 6]
[4 8] [9 9] [10 2] [1 6]
[1 9] [9 9] [10 2] [1 6]

```

To illustrate, here are the three solutions to this case:

# Answer
## CJam, ~~37~~ ~~34~~ 32 bytes

```
{e!Wf<{2*3ew{)f.-~W%.*:-V>},!}=}

```

Not sure if `:-V` is happy enough, but as K Zhang points out, there's the `=}` at the end. :)

This only prints one solution because removing duplicates would be more expensive.

Test it here.

### Explanation

The idea is fairly simple. We generate all possible quadrilaterals (including all orderings of the points) and then just select the convex ones. We test convexity by looking at every pair of edges and checking that they're all turning in the same direction.

The turning sense can be obtained quite easily from a dot product. If you take the three consecutive points on a quadrilateral, and draw lines from the first to the second, and the first to the third, and then project the latter onto the perpendicular of the former... you get a number whose sign tells you whether these three points turn left or right. (I should probably add a diagram for this.) This "projecting onto the perpendicular" is sounds quite involved, but really just means that we reverse one of the two vectors and subtract the components after multiplication instead of adding them. So here's the code...

```
e!       e# Generate all permutations of the five input points.
Wf<      e# Discard the fifth point in each permutations, giving all
         e# possible quadrilaterals.
{        e# Select the first for which this block gives a truthy result...
  2*     e#   Double the list of points, so that it includes each cyclically
         e#   adjacent set of three points.
  3ew    e#   Get all sublists of length 3, i.e. all sets of three consecutive
         e#   points (with two duplicates).
  {      e#   Filter these sets of three points...
    )    e#     Pull off the last point.
    f.-  e#     Subtract it from the other two, giving vectors from it to
         e#     to those.
    ~    e#     Unwrap the array dumping both vectors on the stack.
    W%   e#     Reverse one of them.
    .*   e#     Element-wise multiplication.
    :-   e#     Subtract the second element from the first. This completes
         e#     the projection.
    V>   e#     Check whether it's greater than 0. This is *false* for right-
         e#     turning sets of three points.
  },     e#   If all corners are right-turning, this will result
         e#   in an empty array.
  !      e#   Logical NOT - hence, only quadrilaterals where all corners
         e#   are right-turning give something truthy.
}=

```
> 22 votes

# Answer
# MATLAB, 67 bytes

```
I=input('');for k=~eye(5);if nnz(convhull(I(k,:)))>4;I(k,:),end;end

```

Input is in the form of a 2D matrix where the columns are X and Y respectively:

```
[6 8; 1 10; 6 6; 5 9; 8 10]
[3 8; 7 5; 6 9; 7 8; 5 1]
[4 8; 1 9; 9 9; 10 2; 1 6]

```

All sets of 4 points that create convex quadrilaterals are displayed in the same format.

Here is a demo that is slightly modified to work with Octave

**Explanation**

This solution takes all subsets of 4 points of the input (order doesn't matter). To do this, we create the identity matrix and negate it: `~eye(5)`. We loop through the columns of this matrix and `k` (the loop index) is a logical array which specifies which of the 4 points to consider. We then use this to grab these 4 XY points from the input (`I(k,:)`).

We then compute the convex hull of these 4 points (`convhull`). The output of `convhull` is the indices of the input that correspond with the points that make up the convex hull (with the first index duplicated to close the hull).

For a convex quadrilateral, all four points will be part of the convex hull of the same points (`nnz(convhull(points)) > 4`). If we detect that this is the case, we display the points that were used for this particular iteration.
> 8 votes

# Answer
# Mathematica ~~105~~ 96 bytes

`Select[#~Subsets~{4},f@#&]&` selects, from a list of (5) points, those subsets of 4 points that satisfy `f`.

`f` is satisfied when each point, of the 4 points in a set, lies on the `RegionBoundary` of the `ConvexHull` of the 4 points.

```
f@p_:=Apply[And,RegionBoundary@ConvexHullMesh@p~RegionMember~#&/@p];
Select[#~Subsets~{4},f@#&]&

```

---

## Test Cases

**1.** Let's look at at the 5 convex hulls of subsets (each of 4 points) of {{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}}.

```
Select[#~Subsets~{4},f@#&[{{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}}]

```

{{{6, 8}, {1, 10}, {6, 6}, {5, 9}}}

---

{{6, 8}, {1, 10}, {6, 6}, {5, 9}} is the only solution; each of the four points serves as a vertex of the convex hull (of the same 4 points).

---

{{6, 8}, {1, 10}, {6, 6},{8, 10}} is not a solution; the convex hull has only 3 vertices. {6, 8} lies within the hull.

---

The remaining subsets also are not solutions:

---

**2.** {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} has three solutions.

```
Select[#~Subsets~{4},f@#&[{{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}}]

```

{
{{4, 8}, {1, 9}, {10, 2}, {1, 6}},
{{4, 8}, {9, 9}, {10, 2}, {1, 6}},
{{1, 9}, {9, 9}, {10, 2}, {1, 6}}
}

---

**3.** {{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}} has 5 solutions.

```
Select[#~Subsets~{4},f@#&[{{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}}]

```

{
{{3, 8}, {7, 5}, {6, 9}, {7, 8}},
{{3, 8}, {7, 5}, {6, 9}, {5, 1}},
{{3, 8}, {7, 5}, {7, 8}, {5, 1}},
{{3, 8}, {6, 9}, {7, 8}, {5, 1}},
{{7, 5}, {6, 9}, {7, 8}, {5, 1}}
}

Note that each of the five points lies on the boundary of the convex hull of all points.

If any one of the points is removed, the remaining 4 points will each be vertices of the reduced convex hull.
> 3 votes

# Answer
# Javascript (ES6), ~~306~~ ~~293~~ 283 bytes

```
c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

```

**Explanation**:

The function `c` computes the cross product of the vector between 3 adjacent points of the polygon and returns 1 if it is positive and 0 otherwise (note: the cross product cannot be zero as the points cannot be co-linear).

```
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}

```

The function `k` and `j` generate all cyclic permutations (ignoring reversing the order) of the input array.

```
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])

```

The function 'i' is then called for each cyclic permutation to calculate the sum of the function `c` for each of the 4 triplets of adjacent co-ordinates. If the cross products all have the same sign then they will all either be 0 or 1 and total to 0 (modulo 4) and the polygon is concave and is pushed into the output array. If any triplet has a different sign then the total will be non-zero (modulo 4) and the polygon is convex.

```
f=(v)=>(r=[],k(...v),r)

```

The function `f` is used to initialise the output array and then call the above functions before returning the output.

**Tests**:

```
c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

tests = [
  [[6,8],[1,10],[6,6],[5,9],[8,10]],
  [[3,8],[7,5],[6,9],[7,8],[5,1]],
  [[4,8],[1,9],[9,9],[10,2],[1,6]]
];

tests.forEach(
  (test,i)=>{
    console.log( "Test " + (i+1) );
    f(test).forEach(
      (x)=>console.log( "  " + x.map((e)=>"("+e[0]+","+e[1]+")").join(','))
    );
  }
);
```

**Edit**:

Can also handle co-linear points using the original version and changing the first two lines to:

```
t=(a,b,c)=>Math.sign((b[0]-a[0])*(b[1]-c[1])-(b[1]-a[1])*(b[0]-c[0]))
p=(a,b,c,d)=>[t(a,b,c),t(b,c,d),t(c,d,a),t(d,a,b)].filter(x=>x).reduce((p,c,i,a)=>p&c==a[0],1)
q=(a,m,n,o)=>[a[0],a[m],a[n],a[o]]
f=(a)=>{r=[];for(i=0;i<5;i++){b=a.slice();b.splice(i,1);r.push(q(b,1,2,3));r.push(q(b,1,3,2));r.push(q(b,2,1,3))}return r.filter((a)=>p(...a))}

```

However, since that case is specifically excluded in the question then the extra characters aren't necessary.
> 3 votes

---
Tags: code-golf, number, geometry, integer
---


# Question
Title: Show the Top Five Comment Scores on a SE Post
A Stack Exchange script determines which five comments on questions or answers are initially seen on the main page of sites through the number of upvotes on them; the five comments with the highest number of votes are displayed. Your task is to recreate this behavior.

Write a full program or function taking input through STDIN, command-line args, or function arguments and prints or returns the top five comment scores. Input will be an array of integers representing the number of upvotes on the comments of some post. For instance, an input of

```
0, 2, 5, 4, 0, 1, 0

```

means that the first comment has no votes, the second one has two votes, the third has five, the fourth had four, etc. The order of the comment scores should remain the same in the output.

If the input contains five or fewer comment scores, then the output should contain nothing more than the ones given. If two or more comment scores are the same, the first score(s) should be displayed. You may assume that the input array will contain at least one comment score.

The numbers in the output should be easily distinguished (so 02541 for case 1 is invalid). Otherwise there are no restrictions on output format; the numbers may be separated by a space or newline, or they may be in list format, etc.

Test cases:

```
[0, 2, 5, 4, 0, 1, 0] -> [0, 2, 5, 4, 1]
[2, 1, 1, 5, 3, 6] -> [2, 1, 5, 3, 6]
[0, 4, 5] -> [0, 4, 5]
[1, 1, 5, 1, 1, 5] -> [1, 1, 5, 1, 5]
[0, 2, 0, 0, 0, 0, 0, 0] -> [0, 2, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0] -> [0, 0, 0, 0, 1]
[5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7] -> [5, 8, 7, 6, 7]
[6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2] -> [6, 69, 22, 37, 5]

```

The last example was taken from this Stack Overflow question.

If possible, please provide a link in your post where your submission can be run online.

This is code golf, so the shortest code in bytes wins. Good luck!

# Answer
# Jelly, 6 bytes

```
NỤḣ5Ṣị

```

Try it online! or verify all test cases at once.

### How it works

```
NỤḣ5Ṣị    Main link. Input: A (list)

N         Negate (multiply by -1) all elements of A.
 Ụ        Grade the result up.
          This consists in sorting the indices of A by their negated values.
          The first n indices will correspond to the n highest vote counts,
          tie-broken by order of appearance.
  ḣ5      Discard all but the first five items.
    Ṣ     Sort those indices.
          This is to preserve the comments' natural order.
     ị    Retrieve the elements of A at those indices.

```
> 10 votes

# Answer
# Python 2, 58 bytes

```
x=input()[::-1]
while x[5:]:x.remove(min(x))
print x[::-1]

```

Test it on Ideone.

### How it works

`list.remove` removes the first occurrence if its argument from the specified list. By reversing the list **x**, we essentially achieve that it removes the *last* occurrence instead.

Thus, it suffices to keep removing the comment with the minimal amount of upvotes until a list of no more than five comments is reached. Afterwards, we reverse the list once more to restore the original order.
> 10 votes

# Answer
## Pyth, 11 bytes

```
_.-_Q<SQ_5

```

We calculate the multiset intersection of the input (`Q`) with the five greatest elements in `Q` (in the order they appear in `Q`), then take the first five of those.

```
_ .-           Reverse of multiset difference
     _ Q       of reversed Q
     <         with all but last 5 elements of sorted Q
       S Q
       _ 5

```

Try it here.
> 9 votes

# Answer
# Python 3, 76

Saved 9 bytes thanks to Kevin reminding me that I can abuse if statements in a list comp.

Saved 5 bytes thanks to DSM.

Pretty simple solution right now. Grab the top 5 scores and then parse through the list adding them to the result as we find them.

```
def f(x):y=sorted(x)[-5:];return[z for z in x if z in y and not y.remove(z)]

```

Here are my test cases if anyone wants them:

```
assert f([0, 2, 5, 4, 0, 1, 0]) == [0, 2, 5, 4, 1]
assert f([2, 1, 1, 5, 3, 6]) == [2, 1, 5, 3, 6]
assert f([0, 4, 5]) == [0, 4, 5]
assert f([0, 2, 0, 0, 0, 0, 0, 0]) == [0, 2, 0, 0, 0]
assert f([0, 0, 0, 0, 1, 0, 0, 0, 0]) == [0, 0, 0, 0, 1]
assert f([5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]) == [5, 8, 7, 6, 7]
assert f([6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2]) == [6, 69, 22, 37, 5]

```
> 5 votes

# Answer
# MATL, 16 bytes

```
tn4>?t_FT#S5:)S)

```

This uses current release (10.2.1), which is earlier than this challenge.

**Try it online!**

### Explanation

```
          % implicitly get input
t         % duplicate
n         % number of elements
4>?       % if greater than 4...
  t       % duplicate
  _       % unary minus (so that sorting will correspond to descending order)
  FT#S    % sort. Produce the indices of the sorting, not the sorted values
  5:)     % get first 5 indices
  S       % sort those indices, so that they correspond to original order in the input
  )       % index the input with those 5 indices
          % implicitly end if
          % implicitly display

```
> 5 votes

# Answer
# JavaScript, ~~74 65 62~~ 61 bytes

3 bytes off thanks @user81655. 1 byte off thanks @apsillers.

```
f=a=>5 in a?f(a.splice(a.lastIndexOf(Math.min(...a)),1)&&a):a

```

```
f=a=>5 in a?f(a.splice(a.lastIndexOf(Math.min(...a)),1)&&a):a

document.write('<pre>' +
  '[0, 2, 5, 4, 0, 1, 0] -> ' + f([0, 2, 5, 4, 0, 1, 0]) + '<br>' +
  '[2, 1, 1, 5, 3, 6] -> ' + f([2, 1, 1, 5, 3, 6]) + '<br>' +
  '[0, 4, 5] -> ' + f([0, 4, 5]) + '<br>' +
  '[1, 1, 5, 1, 1, 5] -> ' + f([1, 1, 5, 1, 1, 5]) + '<br>' +
  '[0, 2, 0, 0, 0, 0, 0, 0] -> ' + f([0, 2, 0, 0, 0, 0, 0, 0]) + '<br>' +
  '[0, 0, 0, 0, 1, 0, 0, 0, 0] -> ' + f([0, 0, 0, 0, 1, 0, 0, 0, 0]) + '<br>' +
  '[5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7] -> ' + f([5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]) + '<br>' +
  '[6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2] -> ' + f([6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2]) + '<br>' +
'</pre>')
```
> 5 votes

# Answer
# 05AB1E, ~~12~~ 11 bytes

Code:

```
E[Dg6‹#Rß\R

```

Explanation:

```
E           # Evaluate input
 [          # Infinite loop
  D         # Duplicate top of the stack
   g        # Get the length
    6‹#     # If smaller than 6, break
       R    # Reverse top of the stack
        ß\  # Extract the smallest item and remove it
          R # Reverse top of the stack
            # Implicit, print the processed array

```

Uses CP-1252 encoding.
> 4 votes

# Answer
## CJam, 16 bytes

```
{ee{1=~}$5<$1f=}

```

An unnamed block (function) that takes an array and returns an array.

Test suite.

### Explanation

```
ee   e# Enumerate the array, pairing each number with its index.
{    e# Sort by...
 1=  e#   The original value of each element.
 ~   e#   Bitwise NOT to sort from largest to smallest.
}$   e# This sort is stable, so the order tied elements is maintained.
5<   e# Discard all but the first five.
$    e# Sort again, this time by indices to recover original order.
1f=  e# Select the values, discarding the indices.

```
> 4 votes

# Answer
## PowerShell v4, ~~120~~ 97 bytes

```
param($a)$b=@{};$a|%{$b.Add(++$d,$_)};($b.GetEnumerator()|sort Value|select -l 5|sort Name).Value

```

Experimenting around, I found an alternate approach that golfed off some additional bytes. However, it seems to be specific to PowerShell v4 and how that version handles sorting of a hashtable -- it seems, by default, that in v4 if multiple Values have the same value, it takes the one with a "lower" Key, but you're not guaranteed that in v3 or earlier, even when using the ordered keyword in v3. I've not fully vetted this against PowerShell v5 to say if the behavior continues.

This v4-only version takes input as `$a`, then creates a new empty hashtable `$b`. We loop through all the elements of the input `$a|%{...}` and each iteration add a key/value pair to `$b` (done by pre-incrementing a helper variable `$d` as the key for each iteration). Then we `sort` `$b` based on `Value`, then `select` the `-l`ast `5`, then `sort` by `Name` (i.e., the key), and finally output only the `.Value`s of the resultant hash.

If fewer than 5 elements are entered, it will just sort on value, select the last five (i.e., all of them), re-sort on key, and output.

---

### Older, 120 bytes, works in earlier versions

```
param($a)if($a.Count-le5){$a;exit}[System.Collections.ArrayList]$b=($a|sort)[-5..-1];$a|%{if($_-in$b){$_;$b.Remove($_)}}

```

Same algorithm as Morgan Thrapp's answer, which is apparently an indication that great minds think alike. :)

Takes input, checks if the number of items is less-than-or-equal-to 5, and if so outputs the input and exits. Otherwise, we create an ArrayList `$b` (with the exorbitantly lengthy `[System.Collections.ArrayList]` cast) of the top five elements of `$a`. We then iterate over `$a` and for each element if it's in `$b` we output it and then remove it from `$b` (and here's why we need to use ArrayList, as removing elements from an Array isn't a supported feature in PowerShell, since they're technically fixed size).

Requires v3 or greater for the `-in` operator. For an answer that works in earlier versions, swap `$_-in$b` for `$b-contains$_` for a total of **126 bytes**.
> 3 votes

# Answer
# Bash + GNU utilities, 36

```
nl|sort -nrk2|sed 5q|sort -n|cut -f2

```

I/O formatted as newline-separated lists via STDIN/STDOUT.

Try it online.
> 3 votes

# Answer
## Python, 68 bytes

```
lambda l,S=sorted:zip(*S(S(enumerate(l),key=lambda(i,x):-x)[:5]))[1]

```

Example run.

A lump of built-ins. I think the best way to explain is to run through an example.

```
>> l
[5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]
>> enumerate(l)
[(0, 5), (1, 4), (2, 2), (3, 1), (4, 0), (5, 8), (6, 7), (7, 4), (8, 6), (9, 1), (10, 0), (11, 7)]

```

`enumerate` turns the list into index/value pairs (technically an `enumerate` object).

```
>> sorted(enumerate(l),key=lambda(i,x):-x)
[(5, 8), (6, 7), (11, 7), (8, 6), (0, 5), (1, 4), (7, 4), (2, 2), (3, 1), (9, 1), (4, 0), (10, 0)]
>> sorted(enumerate(l),key=lambda(i,x):-x)[:5]
[(5, 8), (6, 7), (11, 7), (8, 6), (0, 5)]

```

The pairs are sorted by greatest value first, keeping the current order of index for ties. This puts at the front the highest-scored comments, tiebroken by earlier post. Then, the 5 best such comments are taken.

```
>> sorted(_)
   [(0, 5), (5, 8), (6, 7), (8, 6), (11, 7)]
>> zip(*sorted(_))[1]
   (5, 8, 7, 6, 7)

```

Put the top five comments back in posting order, and then remove the indices, keeping only the scores.
> 3 votes

# Answer
# PHP 5, ~~107~~ 102

Saved 5 bytes thanks to @WashingtonGuedes

```
function p($s){uasort($s,function($a,$b){return$a<=$b;});$t=array_slice($s,0,5,1);ksort($t);return$t;}

```

# Ungolfed

```
function p($scores) {
    // sort the array from high to low,
    // keeping lower array keys on top of higher
    // array keys
    uasort($scores,function($a, $b){return $a <= $b;});
    // take the top 5
    $top_five = array_slice($scores,0,5,1);
    // sort by the keys
    ksort($top_five);
    return $top_five;
}

```

Try it.
> 2 votes

# Answer
## Haskell, 62 bytes

```
import Data.List
map snd.sort.take 5.sortOn((0-).snd).zip[0..]

```

Usage example: `map snd.sort.take 5.sortOn((0-).snd).zip[0..] $ [5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]` -\> `[5,8,7,6,7]`.

How it works: augment each element with it's index, sort descending, take first 5 elements, sort by index and remove index.
> 2 votes

# Answer
# Ruby, 82 ~~87~~ ~~89~~ bytes

`$><<eval($*[0]).map.with_index{|x,i|[i,x]}.sort_by{|x|-x[1]}[0,5].sort.map(&:last)`

to call: `ruby test.rb [1,2,2,3,4,5]`

original submission - 56 bytes but fails on certain test cases & didn't support $stdin and $stdout

~~`_.reduce([]){|a,x|a+=_.sort.reverse[0..4]&[x]if !a[4];a}`~~

Explanation

```
$><<               # print to stdout
eval($*[0])        # evals the passed in array in stdin ex: [1,2,3,4]
.map.with_index    # returns an enumerator with indices
{|x,i|[i,x]}       # maps [index,value]
.sort_by{|x|-x[1]} # reverse sorts by the value
[0,5]              # selects the first 5 values
.sort              # sorts item by index (to find the place)
.map{|x|x[1]}      # returns just the values

```
> 0 votes

# Answer
# Julia, 48 bytes

```
!x=x[find(sum(x.<x',2)+diag(cumsum(x.==x')).<6)]

```

Try it online!

### How it works

The comment **c1** has higher precedence than the comment **c2** iff one of the following is true:

* **c1** has more upvotes than **c2**.
* **c1** and **c2** have the same amount of upvotes, but **c1** was posted earlier.

This defines a total ordering of the comments, and the task at hand is to find the five comments that have the highest precedences.

Instead of sorting the comments by precedence (which would alter their order, for each comment **c**, we count the comments that have a greater or equal precedence. We keep **c** if and only if this count is **5** or less.

To partially sort the comments by number of upvotes, we do the following. Let **x** be the column vector containing the vote counts. Then `x'` transposes **x** ‐ thus creating a row vector ‐ and `x.<x'` creates a Boolean matrix that compares each element of **x** with each element of **xT**.

For **x = \[0, 2, 5, 4, 0, 1, 0\]**, this gives

```
<     0      2      5      4      0      1      0
0 false   true   true   true  false   true  false
2 false  false   true   true  false  false  false
5 false  false  false  false  false  false  false
4 false  false   true  false  false  false  false
0 false   true   true   true  false   true  false
1 false   true   true   true  false  false  false
0 false   true   true   true  false   true  false

```

By summing across rows (via `sum(...,2)`), we count the number of comments that have strictly *more* upvotes than the comment at that index.

For the example vector, this gives

```
4
2
0
1
4
3
4

```

Next, we count the number of comments with an equal amount of upvotes have been posted earlier than that comment. We achieve this as follows.

First we build an equality table with `x.==x'`, which compraes the elements of **x** with the elements of **xT**. For our example vector, this gives:

```
=     0      2      5      4      0      1      0
0  true  false  false  false   true  false   true
2 false   true  false  false  false  false  false
5 false  false   true  false  false  false  false
4 false  false  false   true  false  false  false
0  true  false  false  false   true  false   true
1 false  false  false  false  false   true  false
0  true  false  false  false   true  false   true

```

Next, we use `cumsum` to calculate the cumulative sums of each columns of of the matrix.

```
1  0  0  0  1  0  1
1  1  0  0  1  0  1
1  1  1  0  1  0  1
1  1  1  1  1  0  1
2  1  1  1  2  0  2
2  1  1  1  2  1  2
3  1  1  1  3  1  3

```

The diagonal (`diag`) holds the count of comments that have an equal amount of upvotes and occur no later than the corresponding comment.

```
1
1
1
1
2
1
3

```

By adding the two row vectors we produced, we obtain the priorities (**1** is the highest) of the comments.

```
5
3
1
2
6
4
7

```

Comments with priorities ranging from **1** to **5** should be displayed, so we determine their indices with `find(....<6)` and retrieve the corresponding comments with `x[...]`.
> 0 votes

# Answer
# Java 7, 155 bytes

```
import java.util.*;List c(int[]f){LinkedList c=new LinkedList();for(int i:f)c.add(i);while(c.size()>5)c.removeLastOccurrence(Collections.min(c));return c;}

```

**Ungolfed & test-code:**

Try it here.

```
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

class Main{
    static List c(int[] f){
        LinkedList c = new LinkedList();
        for (int i : f){
            c.add(i);
        }
        while(c.size() > 5){
            c.removeLastOccurrence(Collections.min(c));
        }
        return c;
    }

    public static void main(String[] a){
        System.out.println(Arrays.toString(c(new int[]{ 0, 2, 5, 4, 0, 1, 0 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 2, 1, 1, 5, 3, 6 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 0, 4, 5 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 1, 1, 5, 1, 1, 5 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 0, 2, 0, 0, 0, 0, 0, 0 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 0, 0, 0, 0, 1, 0, 0, 0, 0 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2 }).toArray()));
    }
}

```

**Output:**

```
[0, 2, 5, 4, 1]
[2, 1, 5, 3, 6]
[0, 4, 5]
[1, 1, 5, 1, 5]
[0, 2, 0, 0, 0]
[0, 0, 0, 0, 1]
[6, 69, 22, 37, 5]

```
> 0 votes

# Answer
# Python 3.5, 68 bytes

```
f=lambda x,*h:x and x[:sum(t>x[0]for t in x+h)<5]+f(x[1:],*h,x[0]+1)

```

No match for my Python 2 answer, but only three bytes longer than its port to Python 3, and I think it's different enough to be interesting.

I/O is in form of tuples. Test it on repl.it.
> 0 votes

---
Tags: code-golf, array, sorting
---


title: Code Golf of Death

text:
# Question
Title: Code Golf of Death
Write some code that causes a BSOD or kernel panic!

Rules:

* On Windows, you must cause a BugCheck (Blue Screen of Death), on Linux (or other \*nix systems) you must cause a kernel panic.
* **Must not damage the system (i.e. it should work on reboot)**
* Kernel-mode drivers are allowed.
* State your OS and version information.
* Explain how the crash is caused.
* It's not against the rules to use tools that are specifically designed to cause a crash, but doing so isn't very creative!
* Highest upvotes wins.

# Answer
> 26 votes
# Bash, x86 Linux 2.6.20 kernel

**Warning: the following command may cause permanent damage to your system.**

```
cat /dev/urandom > /dev/mem

```

Will output the following (try here). After this, the script hangs.

```
/var/root # cat /dev/urandom > /dev/mem
BUG: unable to handle kernel paging request at virtual address 474e82a5
 printing eip:
c01450c4
*pde = 00000000
Oops: 0000 [#1]
CPU:    0
EIP:    0060:[<c01450c4>]    Not tainted VLI
EFLAGS: 00000082   (2.6.20 #12)
EIP is at free_block+0x54/0xf0
eax: 00000000   ebx: 474e82a1   ecx: c00745c8   edx: c0005e80
esi: c0070ce0   edi: c002c1a0   ebp: 00000000   esp: c0085eec
ds: 007b   es: 007b   ss: 0068
Process events/0 (pid: 3, ti=c0084000 task=c0094030 task.ti=c0084000)
Stack: c0076410 00000002 c0051db0 c0051db0 c0051da0 00000002 c002c1a0 c01457dd
       00000000 c0070ce0 c002c1a0 c0091840 c0145800 c0145870 00000000 00000000
       c02cb2a0 c02cb2a0 00000296 c011dd27 c003fab0 c0094030 c009413c 00047e6c
Call Trace:
 [<c01457dd>] drain_array+0x7d/0xa0
 [<c0145800>] cache_reap+0x0/0x110
 [<c0145870>] cache_reap+0x70/0x110
 [<c011dd27>] run_workqueue+0x67/0x130
 [<c011df17>] worker_thread+0x127/0x140
 [<c010c7d0>] default_wake_function+0x0/0x10
 [<c010c817>] __wake_up_common+0x37/0x70
 [<c010c7d0>] default_wake_function+0x0/0x10
 [<c011ddf0>] worker_thread+0x0/0x140
 [<c0120d94>] kthread+0x94/0xc0
 [<c0120d00>] kthread+0x0/0xc0
 [<c0102ee7>] kernel_thread_helper+0x7/0x10
 =======================
Code: 04 0f 8d 8f 00 00 00 8b 44 24 08 8b 0c a8 8d 91 00 00 00 40 c1 ea 0c c1 e2

```

Here is another exception found with the same command:

```
/dev # cat urandom > mem
------------[ cut here ]------------
Kernel BUG at c014514c [verbose debug info unavailable]
invalid opcode: 0000 [#1]
CPU:    0
EIP:    0060:[<c014514c>]    Not tainted VLI
EFLAGS: 00000046   (2.6.20 #12)
EIP is at free_block+0xdc/0xf0
eax: 1608347b   ebx: c009b010   ecx: c003f508   edx: c00057e0
esi: c009b000   edi: c002cd40   ebp: 00000000   esp: c0085eec
ds: 007b   es: 007b   ss: 0068
Process events/0 (pid: 3, ti=c0084000 task=c0094030 task.ti=c0084000)
Stack: c009b010 00000004 c009b010 c009b010 c009b000 00000004 c002cd40 c01457dd
       00000000 c02ddf20 c002cd40 c0091840 c0145800 c0145870 00000000 00000000
       c02cb2a0 c02cb2a0 00000296 c011dd27 c005c5a0 c0094030 c009413c 000409ed

```

# Answer
> 25 votes
## C, 16 chars, for P5 x86

```
main=-926478352;

```

Remember the F00F bug everyone? I helped lock up a machine or two back in the day with this little program. (Yes, I've been golfing for that long.)

Granted, it's not quite what was asked for, and it only works on old steppings of the P5 Pentium chips. But in its favor, it's cross-platform, working on both Linux *and* Windows!

# Answer
> 9 votes
# QBASIC, 38 Characters

```
DEF SEG=0:FOR I=0 TO 4^8:POKE I,1:NEXT

```

Not sure how you would define a BSOD or Kernel panic in DOS, but this is probably pretty close. When run the screen just goes blank, and the machine responds to nothing, not even Ctrl+Alt+Delete. You have to restart with a hard reset or power cycle to get the machine going again. This is running on DOS 6.22 under VirtualBox. Not sure exactly why it causes the system to crash, but, basically the program is writing (POKE) to memory that it has no business writing to.

# Answer
> 8 votes
## sh (in JSLinux)

Linux gives the init process special protection against signals. However, I noticed that in JSLinux, `/sbin/init` is a shell script that executes other binaries (most symlinked to `/bin/busybox`).

This "infinite" while loop restarts `sh` as necessary:

```
while /bin/true; do

  setsid sh -c 'exec sh </dev/ttyS0 >/dev/ttyS0 2>&1'

done

```

However, what if `/bin/true` does not always return an exit code of 0? `/bin` is on the read-only root file system, yet Linux lets us change that using "bind" mounts:

```
cp -R /bin /tmp/boom
rm /tmp/boom/true
printf '#!/bin/sh\nexec [ $PPID != 1 ]' > /tmp/boom/true
chmod 755 /tmp/boom/true
mount -o bind /tmp/boom /bin
killall -9 sh

```

And we get:

```
/var/root # ./boom.sh
Killed
Kernel panic - not syncing: Attempted to kill init!

```

# Answer
> 4 votes
## Bash on Linux, 27 chars

```
echo c>/proc/sysrq-trigger

```

## Or if you have sudo permissions:

```
echo c|sudo tee /proc/sysrq-trigger

```

# Answer
> 4 votes
## GTB, 13 characters

Executed from a TI-84 calculator

```
:"+"→_[_+_→_]

```

If most of the RAM is free, it will crash with `ERR:MEMORY`

Otherwise, the calculator's RAM is so clogged that it turns off and clears it besides.

> Great example of a "calculator virus"

# Answer
> 4 votes
# Batch (Windows 98)

```
\con\con

```

This is actually a BSOD Easter Egg of Windows 98...

# Answer
> 2 votes
```
:(){ :|:& };:

```

In bash shell,

I am not so sure if this counts here, but if you let it run long enough CPU overheats and system crashes, and it does reboots safely without harm, of course if you do it all the time there will be some system damage.

# Answer
> 2 votes
## Ruby (run as root), 36 or 40 chars (depending on matches for `/p*/s*r`)

See http://www.kernel.org/doc/Documentation/sysrq.txt and search for `'c'` (including quotes!) to see why it works.

```
open(Dir['/p*/s*r'][0],?a){|f|f<<?c}

```

EDIT: Longer version that works if you have other things matching `/p*/s*r`

```
open('/proc/sysrq-trigger',?a){|f|f<<?c}

```

EDIT 2: Intentionally overkill.

# Answer
> 2 votes
```
get-process | stop-process -force

```

in powershell

# Answer
> 1 votes
## Linux bash

```
cat /dev/zero > /dev/mem

```

Clear the entire memory and cause a infinite kernel panic.

Try it here.

# Answer
> 0 votes
# Batch, 15 bytes

```
:A
start
goto A

```

Merely overflows the memory in linear time by starting up `cmd.exe` hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds and hundreds of times.

There's a deadlier (but probably non-competing) 24-byte program that starts up *itself* over and over again, thus overflowing the memory in logarithmic time (i.e upgrading your RAM doesn't delay the crash). Suppose the below code is located in `C:\a.bat`:

```
:A
start C:\a.bat
goto A

```

.

Honestly I'm afraid to try those out.

---
Tags: popularity-contest
---