title: Motion on a hexagonal grid

text:
# Question
Title: Motion on a hexagonal grid
Given an input of a series of characters representing movements on a hexagonal grid, output the final coordinates of the "pointer."

Our hexagons will be numbered like so (imagine a rectangular grid with every odd-numbered column shifted downwards slightly):

```
  _____         _____         _____         _____
 /     \       /     \       /     \       /     \
/ -3,-2 \_____/ -1,-2 \_____/  1,-2 \_____/  3,-2 \
\       /     \       /     \       /     \       /
 \_____/ -2,-1 \_____/  0,-1 \_____/  2,-1 \_____/
 /     \       /     \       /     \       /     \
/ -3,-1 \_____/ -1,-1 \_____/  1,-1 \_____/  3,-1 \
\       /     \       /     \       /     \       /
 \_____/ -2,0  \_____/  0,0  \_____/  2,0  \_____/
 /     \       /     \       /     \       /     \
/ -3,0  \_____/ -1,0  \_____/  1,0  \_____/  3,0  \
\       /     \       /     \       /     \       /
 \_____/ -2,1  \_____/  0,1  \_____/  2,1  \_____/
 /     \       /     \       /     \       /     \
/ -3,1  \_____/ -1,1  \_____/  1,1  \_____/  3,1  \
\       /     \       /     \       /     \       /
 \_____/       \_____/       \_____/       \_____/

```

The pointer starts at (0, 0).

The instructions you must support are as follows:

* `q`: move up-left
* `w`: move up
* `e`: move up-right
* `a`: move down-left
* `s`: move down
* `d`: move down-right
* `r`: rotate grid clockwise
* `R`: rotate grid counterclockwise

The rotation commands rotate the entire grid while keeping the pointer at the same coordinates. (Why `qweasd`? They match up with the directions nicely on a QWERTY keyboard.)

To help visualize this, here's what the movement commands would do, assuming the pointer starts in the middle:

```
         _____
        /     \
  _____/   w   \_____
 /     \       /     \
/   q   \_____/   e   \
\       /     \       /
 \_____/       \_____/
 /     \       /     \
/   a   \_____/   d   \
\       /     \       /
 \_____/   s   \_____/
       \       /
        \_____/

```

After a clockwise rotation (`r`), the commands are remapped to (imagine it as rotating the entire hex grid but still keeping "w" as up, etc., which is equivalent to the following):

```
         _____
        /     \
  _____/   e   \_____
 /     \       /     \
/   w   \_____/   d   \
\       /     \       /
 \_____/       \_____/
 /     \       /     \
/   q   \_____/   s   \
\       /     \       /
 \_____/   a   \_____/
       \       /
        \_____/

```

Similarly, rotating counterclockwise (`R`) after that would return the grid to normal, and rotating counterclockwise again would "remap" `qwedsa` to `aqweds`.

Input must be given as a single string, and output can be either a single string joined by any non-numerical characters (ex. `1 2` or `3,4`) or an array of integers.

Since this is , the shortest code in bytes will win.

Test cases:

```
In                         Out
---------------------------------
edeqaaaswwdqqs             -2, 0
dddddddddd                 10, 5
wswseaeadqdq               0, 0
<empty string>             0, 0
esaaqrweesrqrq             -1, 0
wrwrwrwrw                  -1, 0
RRssrrrs                   -1, -1
aRRRRwddrqrrqqq            -1, -4
rrrrrrrrrrrrRRRRRRrrrrrrq  -1, -1
rrRrRrrRrrrrRRrRrRR        0, 0

```

# Answer
# Pyth, 81 bytes

```
J_K1=Y"qwedsa"A,ZZFNz=kxYN ?<kZ=Y?<x\rNZ.>Y1.<Y1A,+G@[JZ1KZJ)k+H@[J_2JK2K)k;,G/H2

```

Output is a list of integers representing the coordinates.

My solution is actually really boring; it just looks up the inputted character in an array (the `qwedsa`), and then accesses two arrays that represent the respective changes in the coordinates. For example, if the input is `w`, then we get 1 (as it is the second character in the array). Then we add `A[1]` to `x` (where `A` is the array for the changes in `x` in respect to the different inputs) and `B[1]` to `y` (where `B` is the changes for `y`). `r` and `R` are achieved by just rotating the `qwedsa` array.

I'm sure someone can do much better using Pyth. I'll continue to try to golf my answer though!

You can try it out here.
> 2 votes

# Answer
## Retina, ~~353~~ ~~339~~ ~~178~~ ~~175~~ ~~150~~ ~~130~~ ~~129~~ 117 bytes

```
R
5$*r
T`aq\we\ds`so`r.+
)`r(.*)
$1
^
:
a
sq
e
wd
+`(.+)q
w$1
+`(.+)d
s$1
+`sw

(.*)(\1w?):
$0$2
+`sw|ws

w+
-$0
\w
1

```

Output is in unary, separated by a colon. That means you won't really see zeroes in the output (although the presence of a colon will tell you which of the two coordinates is zero, if there is only one).

Try it online!

This was really fun and ended up being surprisingly short. :)

### Explanation

Some background first. There are several coordinate systems to describe hexagonal grids. The one asked for uses offset coordinates. That's essentially like rectangular grid coordinates, except that one axis "wobbles" a bit. In particular, the question asks for the "odd-q" layout shown on the linked page. This coordinate system is a bit annoying to work with, because how the coordinates change during a move depends not only on the direction of the move but also on the current position.

Another coordinate system uses axial coordinates. That's essentially imagining the hexgrid as a diagonal slice through a volume of cubes, and using two of the axes (e.g. x and z) to find a position on the 2D plane. On the hex grid, that means that the two axes form an angle of 60 (or 120) degrees. This system is a bit less intuitive but much easier to work with, since every direction corresponds to a fixed "delta" vector. (For a better explanation of how to arrive at this coordinate system, check out the link and the lovely diagrams and animations there.)

So here's what we'll do: we compute the movement in axial coordinates (taking care of rotation as suggested in the challenge, by remapping the meaning of the commands), and when we're done we convert axial to to odd-q offset coordinates.

The six moves map to the following delta vectors in (x-z) axial coordinates:

```
q => (-1,  0)
w => ( 0, -1)
e => ( 1, -1)
d => ( 1,  0)
s => ( 0,  1)
a => (-1,  1)

```

Wait, this is Retina, we'll have to work with unary numbers. How do we work with negative unary numbers? The idea is to use two different digits. One represents `+1` and the other represents `-1`. That means regardless of whether we want add or subtract `1` from the current position, we can always do so by adding a digit. When we're done we collapse the result into its magnitude (of the corresponding digit) by cancelling balanced digits. Then we figure out the sign based on the remaining digit, and replace all digits with `1`.

The plan is to build up the axial x and z components to the left and right of a `:` (as a separator), in front of the input. `w` and `s` will add to the right-hand side. `q` and `d` will add to the left-hand side, and `e` and `a` will add to both sides. Since `w` and `s` are already on the correct side of the `:` (which will go in front), we will use those as the `-1` and `+1` digits, respectively.

Let's go through the code.

```
R
5$*r

```

We start by turning each `R` into five `r`s. Of course, one left turn is the same as five right turns on a hex grid, and by doing so we can a lot of duplication on the remapping step.

```
T`aq\we\ds`so`r.+

```

This is a transliteration stage which rotates the six commands, if they are found after the first `r` (thereby processing the first `r`). `w` and `d` need to be escaped to prevent them from expanding into character classes. The `o` inserts the source set into the target set which saves a bunch of bytes for these rotation tasks. The character mapping is therefore:

```
aqweds
saqweds

```

where the last `s` in the second row can simply be ignored.

```
)`r(.*)
$1

```

This removes the first `r` from the string, because it's been processed (I wish I had already implemented substitution limits...). The `)` also tells Retina to run all stages up to this one in a loop until the string stops changing. On subsequent iterations, the first stage is a no-op because there are no more `R`s and the second stage will apply another rotation as long as there are `r`s left in the string.

When we're done, we've mapped all commands to the direction they correspond to on the unrotated grid and can start processing those. Of course this movement is just a sum of those delta vectors, and sums are commutative, so it doesn't really matter in which order we process them now that rotations have been eliminated.

```
^
:

```

Insert the coordinate delimiter at the front.

Now we don't really need to process `s` and `w`. They are our `+1` and `-1` digits and they're already on the correct side of the `:` so they'll just drop out as required in the end. We can make another simplification: `a` is simply `s + q` and `e` is `w + d`. Let's do that:

```
a
sq
e
wd

```

Again, those `s` and `w` will just drop out. All we need to do is move those `q`s and `d`s to the front and turn them into `w`s and `s`s themselves. We do that with two separate loops:

```
+`(.+)q
w$1
+`(.+)d
s$1

```

So that's done. Time for the conversion from axial to offset coordinates. For that we need to collapse the digits. However, for now we only care about the left-hand side. Due to the way we've processed the `q`s and `d`s, we know that all the `s`s in the left-hand side will appear in front of any `w`s, so we only need to check one pair for collapsing the them:

```
+`sw

```

Now the actual conversion. Here is the pseudocode, taken from link above:

```
# convert cube to odd-q offset
col = x
row = z + (x - (x&1)) / 2

```

Right, so the left-hand side is already correct. The right-hand side needs the correction term `(x - (x&1)) / 2` though. Taking `&1` is the same as modulo 2. This basically parses as `x/2`, integer division, rounded towards minus infinity. So for positive `x`, we add half the number of digits (rounded down), and for negative `x`, we subtract half the number of digits (rounded up). This can be expressed surprisingly concisely in regex:

```
(.*)(\1w?):
$0$2

```

Due to the greediness, for even `x`, group 1 will match exactly half the digits, `\1` the other half and we can ignore the `w?`. We insert that half after the `:` (which is `x/2`). If `x` is even, then we need to distinguish positive and negative. If `x` is positive, then `w?` will never match, so the two groups will still have to match the same number of digits. That's no problem if the first `s` is simply skipped, so we round down. If `x` is negative and odd, then the possible match is with `\1` (half of `x` rounded down) and that optional `w`. Since both of those go into group `2`, we will write `x/2` with the magnitude rounded up (as required).

```
+`sw|ws

```

Now we collapse the digits on the right-hand side. This time, we don't know the order of the `s` and `w`, so we need to account for both pairs.

```
w+
-$0

```

Both parts are now reduced to a single repeated digit (or nothing). If that digit is `w`, we insert a minus sign in front.

```
\w
1

```

And finally we turn both into `w` and `s` into a single reasonable unary digit. (I suppose I could save a byte by using `w` or `s` as the unary digit, but that seems like a bit of a stretch.)
> 12 votes

# Answer
## Python (3.5) ~~193~~ ~~185~~ 182 bytes

I also calcul in axial coordinates and convert at the end.

I add some optimisation according to @Martin Büttner solution : I replace R by r\*5, it doesn't change the bytes count. But with this change we can replace the second test `elif j=='r'` by just `else`

The solution assume we can't have invalid characters in the input.

```
def f(i):
 x=y=0;u=-1,0,-1,1,0,1,1,0,1,-1,0,-1;v='dewqas'
 for j in i.replace('R','r'*5):
  w=v.find(j)*2
  if-1<w:x+=u[w];y+=u[w+1]
  else:u=u[2:]+u[:2]
 print(-x,-x-y+(x-(x%2))/2)

```

## Ungolfed

```
def f(i):
  x=y=0
  u=-1,0,-1,1,0,1,1,0,1,-1,0,-1    # operations list xd,yd,xe,ye...
  v='dewqas'                       # letters list in clockwise order
  i.replace('R','r'*5)             # replace 'R' by 5*'r'
  for j in i:
    w=v.find(j)*2                  # extract letter index
    if-1<w:
      x+=u[w]                      # apply operations
      y+=u[w+1]
    else:
      u=u[2:]+u[:2]                # rotate clockwise the operation string
  print(-x,-x-y+(x-(x%2))/2)       # convert coordinates axial to "odd-q"

```

## Usage

```
>>> f('wrwrwrwrw')
-1 0.0
>>> f('dddddddddd')
10 5.0
>>> f('edeqaaaswwdqqs')
-2 0.0

```
> 1 votes

# Answer
## Batch, ~~708~~ ~~636~~ ~~586~~ 569 bytes

I used doubled y-coordinates because it made the maths simpler. I'm not sure I took the rotation into account in the most ideal way, but it beats counting the number of `r`s.

Edit: Saved 72 bytes by improving on the handling of `R`s. Saved 60 bytes by optimising my `set/a` statements. Saved 17 bytes with some minor optimisations.

```
@echo off
set m=%1
set/ay=x=0
set r=r
set g=goto l
:l
set/a"z=y>>1
if "%m%"=="" echo %x% %z%&exit/b
set c=%m:~0,1%
set m=%m:~1%
goto %r:rrrrrr=%%c%
:a
:rq
:rrw
:rrre
:rrrrd
:rrrrrs
set/ax-=2
:w
:re
:rrd
:rrrs
:rrrra
:rrrrrq
set/ax+=1,y-=1
%g%
:q
:rw
:rre
:rrrd
:rrrrs
:rrrrra
set/ay-=2
%g%
:s
:ra
:rrq
:rrrw
:rrrre
:rrrrrd
set/ax-=2
:e
:rd
:rrs
:rrra
:rrrrq
:rrrrrw
set/ax+=+1,y+=1
%g%
:d
:rs
:rra
:rrrq
:rrrrw
:rrrrre
set/ay+=2
%g%
:r
:rr
:rrr
:rrrr
:rrrrr
:rrrrrr
if %c%==R set c=rrrrr
set r=%c%%r%
%g%

```
> 0 votes

# Answer
# 05AB1E, 60 bytes

```
.•F?äM•U2Å0IvXy'rQiÀUëy'RQiÁUëykÐ5α‚ßsD3%_s3›·+‚<+]Ć`DÉ-2÷+‚

```

Try it online or verify all test cases.

### Explanation:

***General explanation:***

We start with a string `"qwedsa"` and a coordinate `[0,0]`, and loop over the characters of the input.
If it's an "r" or "R" we rotate this string towards the left or right respectively.
If not, we get the 0-based index in this string, and map it as follows:

```
q → 0 → [-1,  0]
w → 1 → [ 0, -1]
e → 2 → [ 1, -1]
d → 3 → [ 1,  0]
s → 4 → [ 0,  1]
a → 5 → [-1,  1]

```

We'll need to convert the index-digits to the following \\$x\\$ and \\$y\\$ coordinates:

```
 x   indices     y   indices
-1 ← 0;5        -1 ← 1;2
 0 ← 1;4         0 ← 0;3
 1 ← 2;3         1 ← 4;5

```

We do this, by converting the index \\$k\\$ as follows:

\\$x = min(k, abs(k-5))-1\\$
\\$y = (0\equiv k\pmod3) + 2(k\gt3) - 1\\$

And after the entire loop, we have to fix the off-set of the \\$y\\$-coordinate based on the \\$x\\$-coordinate, which we do like this (\\$x\\$ remains the same):

\\$y=y+\lfloor\frac{x-x\pmod2}{2}\rfloor\\$

***Code explanation:***

```
.•F?äM•         # Push compressed string "qwedsa"
       U        # Pop and store it in variable `X`
2Å0             # Push list [0,0]
                # (many 3-byte alternatives for this: `00S`; `т¦S`; `0D‚`; `1¾‰`; etc.)
   Iv           # Loop over each character `y` of the input:
     X          #  Push string `X`
      y'rQi    '#  If `y` equals "r":
           À    #   Rotate string `X` once towards the left
            U   #   And pop and store it as new value for `X`
      ëy'RQi   '#  Else-if `y` equals "R":
            ÁU  #   Do the same, but rotate right instead
      ë         #  Else:
       yk       #   Get the 0-based index of `y` in the string `X`
         Ð      #   Triplicate this index
          5α    #   Take the absolute difference with 5
            ‚ß  #   Pair it with the original index, and pop and push the minimum
                #   (maps 0→[0,5]→0; 1→[1,4]→1; 2→[2,3]→2;
                #         3→[3,2]→2; 4→[4,1]→1; 5→[5,0]→0)
         sD     #   Swap to get the original index again, and duplicate it
           3%   #   Take modulo 3
             _  #   And check if it's equals to 0 (1 if truthy; 0 if falsey)
          s3›   #   Swap to take the index again, and check if it's larger than
                #   (again, 1 if truthy; 0 if falsey)
             ·  #   Double this
          +     #   And add both checks together
                #   (maps 0→1+0→1; 1→0+0→0; 2→0+0→0;
                #         3→1+0→1; 4→0+2→2; 5→0+2→2)
         ‚      #   Pair both mapped values together
          <     #   Decrease both by 1, so it becomes: 0→-1; 1→0; 2→1
           +    #   And add it to the current coordinates
    ]           # After the loop with inner if-else statements:
     Ć          # Enclose the coordinate, appending its own head: [x,y] becomes [x,y,x]
      `         # Push all three values separated to the stack
       D        # Duplicate this x
        É       # Check if its odd (1 if truthy; 0 if falsey)
         -      # Subtract it from the duplicated x
          2÷    # Integer-divide it by 2
            +   # Add it to y
             ‚  # And pair it with the original x again
                # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•F?äM•` is `"qwedsa"`.
> 0 votes

# Answer
## Python 3, 227 bytes

```
def G(s):
 q='qwedsa'
 d=[-1,0,1,1,0,-1,-1,-2,-1,1,2,1]
 X=Y=0
 for c in s:
  if c in q:
   n = q.find(c)
   X += d[n]
   Y += d[n+6]
  if c == 'r':
   q = q[1:]+q[0]
  if c == 'R':
   q = q[5]+q[0:5]
 print(X, int((Y-X%2)/2))

```
> -1 votes

---
Tags: code-golf, hexagonal-grid
---


title: Bit floating sequence

text:
# Question
Title: Bit floating sequence
A bit floats from the LSB to the MSB moving one position each time until it floats to the *top* of the container:

```
0000
0001
0010
0100
1000

```

Once one bit floats to the top, another bit begins its journey and it stops when it meets other bit:

```
1001
1010
1100

```

This happens until the container is filled with bits:

```
1101
1110
1111

```

### Challenge

Given an integer number, output the "*Bit floating sequence*" for a container of that number of bits.

* Each term of the sequence can be separated by any separator of your choice.
* **Edit**: Sequence must be shown as decimal integer numbers, starting by the first therm: `0`.
* The container size sould be greater than zero and up to the number of bits of the bigest integer suported by the language of your choice. You can assume that the input always match this requirement.

### Examples

Only the numeric sequence is required, binary representation is shown as example:

* For **1**: `0 1`

```
0 -> 0
1 -> 1

```
* For **3**: `0 1 2 4 5 6 7`

```
000 -> 0
001 -> 1
010 -> 2
100 -> 4
101 -> 5
110 -> 6
111 -> 7

```
* For **4**: `0 1 2 4 8 9 10 12 13 14 15`

```
0000 -> 0
0001 -> 1
0010 -> 2
0100 -> 4
1000 -> 8
1001 -> 9
1010 -> 10
1100 -> 12
1101 -> 13
1110 -> 14
1111 -> 15

```
* For **8**: `0 1 2 4 8 16 32 64 128 129 130 132 136 144 160 192 193 194 196 200 208 224 225 226 228 232 240 241 242 244 248 249 250 252 253 254 255`

```
00000000 -> 0
00000001 -> 1
00000010 -> 2
00000100 -> 4
00001000 -> 8
…
…
…
11111000 -> 248
11111001 -> 249
11111010 -> 250
11111100 -> 252
11111101 -> 253
11111110 -> 254
11111111 -> 255

```

# Answer
# 05AB1E, 10 bytes

```
LRL˜Íoî.¥ï

```

Try it online!

```
L                 # range [1..input]
 R                # reversed
  L               # convert each to a range: [[1..input], [1..input-1], ..., [1]]
   ˜              # flatten
    Í             # subtract 2 from each
     o            # 2**each
      î           # round up (returns a float)
       ï          # convert to integer
        .¥        # undelta

```
> 7 votes

# Answer
# Python 2, 45 bytes

```
y=n=2**input()
while y:print n-y;y=y&y-1or~-y

```

Try it online!

It turns out shorter to generate `2**n` minus each term in the sequence for input `n`. If we look at their binary expansion, below for `n=5`, we see a nice pattern of triangles of 1's in the binary expansions.

```
100000  32
011111  31
011110  30
011100  28
011000  24
010000  16
001111  15
001110  14
001100  12
001000  8
000111  7
000110  6
000100  4
000011  3
000010  2
000001  1

```

Each number is obtained from the previous one by removing the rightmost one in the binary expansion, except if that would make the number 0, we subtract 1 instead, creating a new block of 1's that starts a new smaller triangle. This is implemented as `y=y&y-1or~-y`, where `y&y-1` is a bit trick to remove the rightmost 1, and `or~-y` gives `y-1` instead if that value was 0.

**Python 2, 49 bytes**

```
def f(n,x=0):1%n;print x;f(n-x%2,x+(x%2**n or 1))

```

Try it online!

A function that prints, terminating with error. The more nice program below turned out longer.

**51 bytes**

```
n=input()
x=0
while n:n-=x%2;print x;x+=x%2**n or 1

```

Try it online!
> 7 votes

# Answer
# Jelly, ~~11~~ 10 bytes

```
RUḶ’F2*ĊÄŻ

```

Port of *@Grimy*'s 05AB1E answer, so make sure to upvote him!
-1 byte thanks to *@Grimy*.

Try it online.

**Explanation:**

```
R           # Create a list in the range [1, (implicit) argument]
 U          # Reverse it to [argument, 1]
  Ḷ         # Create an inner list in the range [0, N) for each value N in this list
   ’        # Decrease each by 1
    F       # Flatten the list of lists
     2*     # Take 2 to the power each
       Ċ    # Ceil
        Ä   # Undelta (cumulative sum) the list
         Ż  # And add a leading 0
            # (after which the result is output implicitly)

```
> 6 votes

# Answer
# Perl 5 (`-n`), ~~41~~ 40 bytes

-1 byte thanls to Xcali

```
map{/01.*1/||say oct}glob"0b"."{0,1}"x$_

```

TIO

* `"{0,1}"x$_` : the string `"{0,1}"` repeated n times
* `"0b".` : concatenate to `"0b"`
* `glob` : glob expansion (cartesian product)
* `map{`...`}` : for each element
* `/01.*1/||` : to skip when `01` followed by something then `1`
* `say oct` : to convert to decimal and say
> 4 votes

# Answer
# JavaScript (ES6), 43 bytes

When in doubt, use xnor's method.

```
n=>(g=x=>x?[n-x,...g(x&--x||x)]:[])(n=1<<n)

```

Try it online!

---

# JavaScript (ES6),  ~~59 57 55~~  52 bytes

```
f=(n,x=0)=>x>>n?[]:[x,...f(n,x+=x+(x&=-x)>>n|!x||x)]

```

Try it online!

### How?

We define \\$p(x)\\$ as the highest power of \\$2\\$ dividing \\$x\\$, with \\$p(0)=0\\$ by convention.

This function can be implemented with a simple bitwise AND of \\$x\\$ and \\$-x\\$ to isolate the lowest bit set to \\$1\\$ in \\$x\\$. For instance:

$$p(52)=52 \operatorname{AND}-52=4$$

Using \\$p\\$, the sequence \\$a\_n\\$ can be defined as \\$a\_n(0)=0\\$ and:

$$a\_n(k+1)=\cases{ a\_n(k)+p(a\_n(k)), & \text{if $p(a\_n(k))\neq0$ and $a\_n(k)+p(a\_n(k))\<2^n$}\\ a\_n(k)+1, & \text{otherwise} }$$

### Commented

```
f = (                   // f is a recursive function taking:
  n,                    //   n = input
  x = 0                 //   x = current term of the sequence
) =>                    //
  x >> n ?              // if x is greater than or equal to 2**n:
    []                  //   stop recursion
  :                     // else:
    [                   //   update the sequence:
      x,                //     append the current term to the sequence
      ...f(             //     do a recursive call:
        n,              //       pass n unchanged
        x +=            //       update x:
          x + (x &= -x) //         given x' = lowest bit of x set to 1:
          >> n          //         if x + x' is greater than or equal to 2**n
          | !x          //         or x' is equal to 0: add 1 to x
          || x          //         otherwise, add x' to x
      )                 //     end of recursive call
    ]                   //   end of sequence update

```
> 4 votes

# Answer
# Python 2, ~~95~~ 76 bytes

```
n=input()
a=0
print 0
while n:
 for j in range(n):print a+2**j
 n-=1;a+=2**n

```

Try it online!
> 3 votes

# Answer
# Python 2, 67 bytes

```
n=0
i=2**input()-1
while n<=i:print n;d=n&(~-n^i)or 1;n+=n+d>i or d

```

Try it online!
> 3 votes

# Answer
# Perl 6, 43 bytes

```
{0 x$_,{say :2($_);S/(0)1|0$/1$0/}...1 x$_}

```

Try it online!

Anonymous code block that takes a number and outputs the sequence separated by newlines. This works by starting with 0 repeated n times then replacing either `01` with `10` or the last `0` with a `1` until the number is just ones.

Or 40 bytes, using Nahuel Fouilleul's approach

```
{grep /010*1/|{say :2($_)},[X~] ^2 xx$_}

```

Try it online!
> 3 votes

# Answer
# Python 2, 60 bytes

```
f=lambda i,n=0,b=1:[n][i:]or[n]+f(i-1/b,n^b+b/2,b>>i or 2*b)

```

Try it online!

---

# Python 3, 76 bytes

```
f=lambda n:[0][n:]or[0]+[2**i for i in range(n-1)]+[x|1<<n-1for x in f(n-1)]

```

Try it online!
> 3 votes

# Answer
# Python 3, 62 bytes

```
def f(n,c=0):
 while c<2**n:yield c;r=c&-c;c+=c+r>>n or r or 1

```

Try it online!

The idea is more or less the same as @Arnauld's solution.

Another 65-byte solution:

```
lambda n:g(2**n-1)
g=lambda c:[0][c:]or g(c-((c&-c)//2 or 1))+[c]

```

Try it online!
> 3 votes

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

```
Tsãʒ1ÛSO2‹}C{

```

-1 byte thanks to *@Grimy* (also take a look at his shorter approach here).

Try it online or verify all test cases.

**Explanation:**

```
T             # Push 10
 sã           # Swap to get the (implicit) input, and get the cartesian product with "10"
   ʒ          # Filter it by:
    1Û        #  Remove leading 1s
      SO      #  Get the sum of the remaining digits
        !     #  Check that the sum is either 0 or 1 by taking the factorial
              #  (NOTE: Only 1 is truthy in 05AB1E)
         }C   # After the filter: convert all remaining strings from binary to integer
           {  # And sort (reverse) them
              # (after which the result is output implicitly)

```
> 2 votes

# Answer
# Jelly, 12 bytes

```
⁼þ‘ṚÄUo€ƊẎQḄ

```

Try it online!
> 2 votes

# Answer
# Retina, 26 bytes

```
.+
*0
L$w`.(.*)
$.`*1$'1$1

```

Try it online! Outputs in binary. If that's not acceptable, then for 39 bytes:

```
.+
*0
L$w`.(.*)
$.`*1$'1$1
+`10
011
%`1

```

Try it online! Explanation:

```
.+
*0

```

Convert the input into a string of `n` zeros.

```
L$w`.(.*)

```

Match all possible non-empty substrings.

```
$.`*1$'1$1

```

For each substring, output: the prefix with `0`s changed to `1`s; the suffix; the match with the initial `0` changed to `1`.

```
+`10
011
%`1

```

Convert from binary to decimal.
> 2 votes

# Answer
# Brachylog, 27 bytes

```
1;0|⟦₅;2z^₍ᵐLtT&-₁↰+ᵐ↙T,L,0

```

Try it online!

Outputs out of order and with duplicates. If that's not okay, tack `do` onto the end.
> 2 votes

# Answer
# Charcoal, 19 bytes

```
Ｉ⮌Ｅ⊕θＥι⁺⁻Ｘ²ＩθＸ²ιＸ²λ

```

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

```
    θ               Input
   ⊕                Incremented
  Ｅ                 Map over implicit range
      ι             Outer index
     Ｅ              Map over implicit range
           Ｉθ       Input cast to integer
               ι    Outer index
                  λ Inner index
         Ｘ²  Ｘ² Ｘ²  Power of 2
       ⁺⁻           Subtract and add
 ⮌                  Reverse outer list
Ｉ                   Cast to string
                    Implicitly print

```
> 1 votes

# Answer
# Perl 5, 40 bytes

```
map{say$-;$-+=2**$_}0,0..$_-2;$_--&&redo

```

Try it online!
> 1 votes

# Answer
# Retina, 24 bytes

```
.+
*0
/0/+<0`(0)1|0$
1$1

```

Outputs in binary. Input should have a trailing newline.

Attempt at explanation:

```
.+              #match the entire input
*0              #replace it with that many zeroes
/0/+<0`(0)1|0$  #while the string has a 0, substitute the first match and output
1$1             #if 01 is present in the string, replace it with 10, else replace the last character with $

```

I tried to avoid the 3 bytes long `/0/` regex option by rearranging the options, but couldn't.

Try it online!
> 1 votes

# Answer
# C (clang), 73 bytes

```
o,j,y;f(x){for(o=j=0;printf("%d ",o),x;o+=y+!y,y+=y+!y)j=!j?y=0,--x:--j;}

```

Try it online!

```
for(o=j=0;printf("%d ",o),x;  o+=y+!y, y+=y+!y)
// adds 1, 1+1=>2 , 2+2=> 4 .... sequence

 j=!j?y=0,--x:--j;
// uses ternary instead of nested loop to decrement 'x' when 'j' go to 0

```
> 1 votes

# Answer
# k4, ~~28~~ 24 bytes

```
0,+\"j"$2 xexp,/-1+|,\!:

```

@Grimy's approach ported to k4

edit: -4 thanks to ngn!
> 1 votes

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


title: SQL select number ranges

text:
# Question
Title: SQL select number ranges
I found it quite hard to achieve a range of numbers as rows in `MySQL`.

For example the range 1-5 is achieved by:

```
SELECT 1
UNION
SELECT 2
UNION
SELECT 3
UNION
SELECT 4
UNION
SELECT 5

```

will result in:

> ```
> 1
> 2
> 3
> 4
> 5
>
> ```

for 0-99 I can cross join two 0-9 tables:

```
CREATE TABLE nums as
SELECT 0 as num
UNION
SELECT 1
UNION
SELECT 2
UNION
SELECT 3
UNION
SELECT 4
UNION
SELECT 5
UNION
SELECT 6
UNION
SELECT 7
UNION
SELECT 8
UNION
SELECT 9
;

Select n.num*10+nums.num v
From nums n cross join nums

```

I'm tired of writing all these `UNION`s and looking for a way to shrink the code.

Any ideas how to **golf it** (for example 0-1,000,000 range) in MySQL or any SQL syntax ?

**Extra points** are given for:

* single statement
* no procedures
* no variables
* no DDL statements
* only DQL statements

# Answer
For SQL dialects that support recursive CTEs like sqlite, you can do something like the following:

```
WITH RECURSIVE f(x) AS
(
  SELECT 1 UNION ALL SELECT x + 1 FROM f LIMIT 1000000
)
SELECT x
FROM f;

```

This doesn't depend on any existing table and you can change the LIMIT clause as desired. I originally saw a variant of this on StackOverflow.
> 9 votes

# Answer
Similar to @BradC's method.

I used MS SQL, which has a table in `[master]` with a number range of -1 through 2048. You can use the `BETWEEN` operator to create your range.

```
SELECT DISTINCT(number)
FROM master..[spt_values]
WHERE number BETWEEN 1 AND 5

```

If you want to golf this, you can do:

```
SELECT TOP 5 ROW_NUMBER()OVER(ORDER BY number)FROM master..spt_values

```
> 6 votes

# Answer
### PostgreSQL, 35 bytes

PostgreSQL has this easy:

```
SELECT * FROM generate_series(1,5)

```

If you need it named:

```
SELECT num FROM generate_series(1,5)AS a(num)

```

You can also do this with timestamps. https://www.postgresql.org/docs/9.5/static/functions-srf.html
> 5 votes

# Answer
Great option from this post (found by @Arnauld):

```
SELECT id%1000001 as num
FROM <any_large_table>
GROUP BY num

```

For me - it's pretty much solves the challenge.
> 4 votes

# Answer
# PostgreSQL specific

`generate_series()` generates a set, so you can user it not only in `from` clause, but anywhere where a set may occur:

```
psql=# select generate_series(10, 20, 3);
 generate_series
-----------------
              10
              13
              16
              19
(4 rows)

```

You can also do operations directly on the set:

```
psql=# select 2000 + generate_series(10, 20, 3) * 2;
 ?column?
----------
     2020
     2026
     2032
     2038
(4 rows)

```

If multiple sets have the same length, you can traverse them in parallel:

```
psql=# select generate_series(1, 3), generate_series(4, 6);
 generate_series | generate_series
-----------------+-----------------
               1 |               4
               2 |               5
               3 |               6
(3 rows)

```

For sets with different lengths a Cartesian product is generated:

```
psql=# select generate_series(1, 3), generate_series(4, 5);
 generate_series | generate_series
-----------------+-----------------
               1 |               4
               2 |               5
               3 |               4
               1 |               5
               2 |               4
               3 |               5
(6 rows)

```

But if you use them in `from` clause, you get Cartesian product for same length sets too:

```
psql=# select * from generate_series(1, 2), generate_series(3, 4) second;
 generate_series | second
-----------------+--------
               1 |      3
               1 |      4
               2 |      3
               2 |      4
(4 rows)

```

It can also generate set of timestamps. For example you born on 2000-06-30 and want to know in which years you celebrated your birthday in a weekend:

```
psql=# select to_char(generate_series, 'YYYY - Day') from generate_series('2000-06-30', current_date, interval '1 year') where to_char(generate_series, 'D') in ('1', '7');
     to_char
------------------
 2001 - Saturday
 2002 - Sunday
 2007 - Saturday
 2012 - Saturday
 2013 - Sunday
(5 rows)

```
> 4 votes

# Answer
(These work in MS-SQL, not sure if they works for mySQL or other platforms.)

For smaller sets (ordered or non-ordered), use the `VALUES` constructor:

```
--Generates 0-9
SELECT a
FROM(VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9))x(a)

```

(This works for anything, although strings can get pretty long with all the repeated single quotes.)

Then you can cross-multiply using a named CTE (common table expression) so you don't have to repeat it:

```
--Generates 0-999
WITH x AS(SELECT a FROM(VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9))x(a))
SELECT 100*x.a+10*y.a+z.a
FROM x,x y,x z
ORDER BY 1

```

There are tons of other techniques out there, look for "SQL generating a number table", although most aren't optimized for golfing.
> 3 votes

# Answer
MS SQL has an undocumented system table in the `master` database called `spt_values`. Among other things, it contains a range of numbers from 0 to 2047:

```
--returns 0 to 2,047
SELECT number n
FROM master..spt_values
WHERE TYPE='P'

```

Useful as a numbers table just by itself, but in a CTE you can get some big numbers pretty quickly:

```
--returns 0 to 4,194,304
WITH x AS(SELECT number n FROM master..spt_values WHERE TYPE='P')
SELECT 2048*x.a+*y.a
FROM x,x y
ORDER BY 1

```
> 3 votes

# Answer
One more option, this one specific to MS SQL 2016 and above:

```
SELECT value v
FROM STRING_SPLIT('1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16', ',')

```

I'll likely find this more handy for lists of strings, but I can see ways it will be useful with numbers as well.
> 2 votes

# Answer
# T-SQL, 98 bytes

```
WITH H AS(SELECT 0i UNION ALL SELECT i+1FROM H WHERE i<99)SELECT H.i+1e4*A.i+B.i*1e2FROM H,H A,H B

```
* ✓ single statement
* ✓ no procedures
* ✓ no variables
* ✓ no DDL statements
* ✓ only DQL statements
> 2 votes

# Answer
Another for SQL Server...

```
WITH
    cte_n1 (n) AS (SELECT 1 FROM (VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) n (n)),   -- 10
    cte_n2 (n) AS (SELECT 1 FROM cte_n1 a CROSS JOIN cte_n1 b),                             -- 100
    cte_Tally (n) AS (
        SELECT TOP (<how many ROWS do you want?>)
            ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM
            cte_n2 a CROSS JOIN cte_n2 b                                                    -- 10,000
        )
SELECT
    t.n
FROM
    cte_Tally t;

```
> 1 votes

---
Tags: code-golf, tips, syntax, sql
---


title: Permutations in Disguise

text:
# Question
Title: Permutations in Disguise
Given a \\$n\\$-dimensional vector \\$v\\$ with real entries, find a closest permutation \\$p\\$ of \\$(1,2,...,n)\\$ with respect to the \\$l\_1\\$-distance.

### Details

* If it is more convenient, you can use permutations of \\$(0,1,...,n-1)\\$ instead. If there are multiple closest permutations, you can output any one or alternatively all of them.
* The \\$l\_1\\$ distance between two vectors \\$u,v\\$ is defined as $$d(u,v) = \sum\_i \vert u\_i-v\_i\vert.$$
* If you want, you can assume that the input solely consists of integers.

### Examples

```
[0.5  1] -> [1 2], [2 1]
c*[1 1 ... 1] -> any permutation
[1 4 2 6 2] -> [1 4 3 5 2], [1 4 2 5 3]
[1 3 5 4 1] -> [2 3 5 4 1], [1 3 5 4 2]
[7 7 3 2 5 6 4 2] -> [8 7 3 2 5 6 4 1], [8 7 3 1 5 6 4 2], [7 8 3 2 5 6 4 1], [7 8 3 1 5 6 4 2]
[-2 4 5 7 -1 9 3] -> [1 4 5 6 2 7 3], [2 4 5 6 1 7 3], [1 4 5 7 2 6 3], [2 4 5 7 1 6 3]
[0 4 2 10 -1 10 5] -> [1 4 2 6 3 7 5], [1 4 3 6 2 7 5], [2 4 3 6 1 7 5], [3 4 2 6 1 7 5], [1 4 2 7 3 6 5], [1 4 3 7 2 6 5], [2 4 3 7 1 6 5], [3 4 2 7 1 6 5]

```

Octave script for generating more examples.

# Answer
# Python 2, 60 bytes

```
def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)

```

Try it online!

Uses zero-indexing.

A fast algorithm with a simple idea. If we instead need to permute the input list to make it as close to \\$(1,2,...,n)\\$ as possible, we should just sort it, as proven below. Since we're instead permuting \\$(1,2,...,n)\\$, we choose the permutation that's ordered the same way as the input list, like in my challenge Imitate an ordering (except the input may have repeats). (Edit: miles pointed out this more identical challenge, where Dennis has this same answer.)

> **Claim:** A permutation of the list \\$l\\$ that minimizes its distance to \\$(1,2,...,n)\\$ is \\$l\\$ sorted.
>
> **Proof:** Consider some other permutation \\$l'\\$ of \\$l\\$. We'll prove it can't be better than \\$l\\$ sorted.
>
> Pick two indices \\$i,j\\$ that \\$l'\\$ has out-of-order, that is where \\$i\<j\\$ but \\$l'\_i \> l'\_j\\$. We show that swapping them can't increase the distance to \\$(1,2,...,n)\\$. We note that swap changes the contribution these two elements as follows: $$ |l'\_i - i | + |l'\_j - j | \to |l'\_i - j | + |l'\_j - i|.$$
>
> Here's a neat way to show this can't be an increase. Consider two people walking on a number line, one going from \\$l'\_i\\$ to \\$i\\$ and the other from \\$l'\_j\\$ to \\$j\\$. The total distance they walk is the expression on the left. Since \\$i\<j\\$ but \\$l'\_i \> l'\_j\\$, they switch who is higher on the number line, which means they must cross at some point during their walks, call it \\$p\\$. But when they reach \\$p\\$, they could then swap their destinations and walk the same total distance. And then, it can't be worse for them to have walked to their swapped destinations from the start rather than using \\$p\\$ as a waypoint, which gives the total distance on the right-hand side.
>
> So, sorting two out-of-order elements in \\$l'\\$ makes its distance to \\$(1,2,...,n)\\$ smaller or the same. Repeating this process will sort \\$l\\$ eventually. So, \\$l\\$ sorted is at least as good as \\$l'\\$ for any choice of \\$l'\\$, which means it as optimal or tied for optimal.

Note that the only property of \\$(1,2,...,n)\\$ that we used is that it's sorted, so the same algorithm would work to permute any given list to minimize its distance to any fixed list.

In the code, the only purpose of `z=zip(l,range(len(l)))` is to make the input elements distinct, that is to avoid ties, while keeping the same comparisons between unequal elements. If the input we guaranteed to have no repeats, we could remove this and just have `lambda l:map(sorted(l).index,l)`.
> 14 votes

# Answer
# 05AB1E, 7 bytes

```
āœΣαO}н

```

Try it online!

---

### Explanation

```
ā              # get the numbers 1 to len(input) + 1
 œ             # Permutations of this
  Σ  }         # Sort by ...
   α           # Absolute difference
    O          # Sum these
      н        # And get the first one
               # implicitly print

```
> 5 votes

# Answer
# Perl 6, 44 bytes

```
{permutations(+$_).min((*[]Z-$_)>>.abs.sum)}

```

Try it online!

Anonymous codeblock that returns the first minimum permutation with 0 indexing.

### Explanation:

```
{                                          }   # Anonymous code block
 permutations(+$_)                             # From the permutations with the same length
                  .min(                   )    # Find the minimum by
                                      .sum       # The sum of
                                >>.abs           # The absolute values of
                       (*[]Z-$_)                 # The zip subtraction with the input

```

I think I might also be able to get rid of the `.sum` and sort by just the list of absolute values, but I'm not sure this is actually corret, though it passes my current test cases.
> 3 votes

# Answer
# Jelly, 8 bytes

```
LŒ!ạS¥ÐṂ

```

Try it online!
> 2 votes

# Answer
# Jelly, 5 bytes

```
Œ¿œ?J

```

A monadic Link accepting a list of numbers which yields a list of integers.

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

### How?

```
Œ¿œ?J - Link: list of numbers, X
Œ¿    - Index of X in a lexicographically sorted list of
         all permutations of X's items
    J - range of length of X
  œ?  - Permutation at the index given on the left of the
         items given on the right

```

N.B. `L` (length of) would work in place of `J` since `œ?` given an integer, `n`, on the right would implicitly make the range `[1..n]` to work with, but `J` is explicit.
> 2 votes

# Answer
# Ruby, ~~63~~ 60 bytes

```
->v{[*1..v.size].permutation.max_by{|p|eval [p,0]*'*%p+'%v}}

```

Try it online!

There's a math trick here that could be helpful in other answers too--instead of minimizing the sum of the absolute values of the differences, we *maximize* the sum of the products. Why does that work?

Minimizing the sum of `(x-y) squared` isn't equivalent to minimizing the sum of `|x-y|`, but it will always give a valid answer, it just prioritizes reducing large differences over small ones whereas the actual challenge is indifferent between the two.

But `(x-y)*(x-y)` = `x*x+y*y-2*x*y`. Since the square terms will always show up somewhere in the sum for any permutation, they don't affect the result, so we can simplify to `-2*x*y`. The `2` factors out, so we can simplify to `-x*y`. Then if we change minimizing to maximizing, we can simplify to `x*y`.

Intuitively, this is similar to observing that if you're trying to maximize square footage using a set of horizontal walls and a set of vertical ones, you're best off pairing walls that are close in size to each other to create rooms that are as close to square as possible. `3*3 + 4*4 = 25`, while `3*4 + 4*3 = 24`.

Edit: Saved three bytes by generating and evaluating a format string instead of using zip and sum.
> 2 votes

# Answer
# JavaScript (ES6), 61 bytes

Based on xnor's insight.

```
a=>[...a].map(g=n=>g[n]=a.sort((a,b)=>a-b).indexOf(n,g[n])+1)

```

Try it online!

### Commented

```
a =>                    // a[] = input array
  [...a]                // create a copy of a[] (unsorted)
  .map(g = n =>         // let g be in a object; for each value n in the copy of a[]:
    g[n] =              //   update g[n]:
      a.sort(           //     sort a[] ...
        (a, b) => a - b //       ... in ascending order
      ).indexOf(        //     and find the position
        n,              //       of n in this sorted array,
        g[n]            //       starting at g[n] (interpreted as 0 if undefined)
      ) + 1             //     add 1
  )                     // end of map()

```

---

# JavaScript (ES6),  ~~130~~  128 bytes

There  ~~must be~~  *definitely is* a more direct way...

0-indexed.

```
a=>(m=g=(k,p=[])=>1/a[k]?(h=i=>i>k||g(k+1,b=[...p],b.splice(i,0,k),h(-~i)))``:p.map((v,i)=>k+=(v-=a[i])*v)|k>m||(R=p,m=k))(0)&&R

```

Try it online! (with 1-indexed output)

### How?

The helper function \\$g\\$ computes all permutations of \\$(0,...,n-1)\\$, where \\$n\\$ is the implicit length of the input array \\$a\[\\;\]\\$.

For each permutation \\$p\\$, we compute:

$$k=n-1+\sum\_{i=0}^{n-1}(p\_i-a\_i)^2$$ The only reason for the leading \\$n-1\\$ is that we re-use the internal counter of \\$g\\$ to save a few bytes, but it has no impact on the final result.

We eventually return the permutation that leads to the smallest \\$k\\$.
> 1 votes

# Answer
# Python 2, ~~149~~ ~~126~~ 112 bytes

*-23 bytes thanks to Mr. Xcoder*

*-14 bytes thanks to xnor*

```
from itertools import*
f=lambda a:min(permutations(range(len(a))),key=lambda x:sum(abs(a-b)for a,b in zip(x,a)))

```

Try it online!

Uses permutations of (0 ... n-1).
> 1 votes

# Answer
# Gaia, 13 bytes

```
e:l┅f⟪D†Σ⟫∫ₔ(

```

Try it online!

```
e:		| eval and dup input
l┅f		| push permutations of [1..length(input)]
⟪   ⟫∫ₔ		| iterate over the permutations, sorting with minimum first
 D†Σ		| the sum of the absolute difference of the paired elements
       (	| and select the first (minimum)

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 14 bytes

```
#@*#&@Ordering

```

Try it online!

Based on xnor's insight.
> 1 votes

# Answer
# Japt `-g`, 12 bytes

```
Êõ á ñÈíaU x

```

Try it

For 0-indexed, replace the first 2 bytes with `m,` to map the array to its indices instead.

```
Êõ á ñÈíaU x     :Implicit input of array U
Ê                :Length
 õ               :Range [0,Ê]
   á             :Permutations
     ñÈ          :Sort by
       í U       :  Interleave with U
        a        :  Reduce each pair by absolute difference
           x     :  Reduce resulting array by addition
                 :Implicit output of first sub-array

```
> 0 votes

# Answer
w/o any permutation package

# Python 3, 238 bytes

```
def p(a,r,l):
 if r==[]:l+=[a];return
 for i in range(len(r)):
  p(a+[r[i]],r[:i]+r[i+1:],l)
def m(l):
 s=(float("inf"),0);q=[];p([],list(range(len(l))),q)
 for t in q:D=sum(abs(e-f)for e,f in zip(l,t));s=(D,t)if D<s[0]else s
 return s[1]

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 57 bytes

```
f@n_:=MinimalBy[Permutations@Range@Length@n,Tr@Abs[n-#]&]

```

Try it online!
> 0 votes

# Answer
# , <sup>~~25~~</sup> 8 bytes

```
#\/:@/:]

```

Try it online!

Much shorter answer based xnor's brilliant idea.

## original answer

## , 25 bytes

```
(0{]/:1#.|@-"1)i.@!@#A.#\

```

Try it online!
> 0 votes

---
Tags: code-golf, math, combinatorics, permutations, optimization
---


title: Olympic game scoring

text:
# Question
Title: Olympic game scoring
The challenge is to write a golf-code program that, given n positive real numbers from 0 to 10 (format x.y, y only can be 0 or 5: 0, 0.5, 1, 1.5, 2, 2.5 … 9.5 and 10), discard the lowest and highest values (only one, even though they are repeated) and shows the average of the remaining, in x.y format (y can be 0 or 5, rounded to closest), similar to some Olympic Games scoring.

Examples: Input -\> Output

6 -\> 6

6.5, 9 -\> 8

9, 7, 8 -\> 8

6, 5, 7, 8, 9 -\> 7

5, 6.5, 9, 8, 7 -\> 7

6.5, 6.5, 9.5, 8, 7 -\> 7

5, 6.5, 7.5, 8.5, 9.5 -\> 7.5

Notes: If the input is only two numbers, do not discard any, just average them. If the input is one number, the output is the same.

Clarifying the rounding rule (sorry, little confuse):

x.01 to x.25 round to x.0

x.26 to x.75 round to x.5

x.76 to x.99 round to x+1.0

# Answer
# Jelly, 12 bytes

```
ṢṖḊȯµÆmḤær0H

```

Try it online!

```
    µ           Take
Ṣ               the input sorted,
 Ṗ              without its last
  Ḋ             or first element,
   ȯ            or the unchanged input if that's empty,
     Æm         then calculate the mean,
       Ḥ        double it,
        ær      round it to the nearest multiple of
          0     10^-0 (= 1),
           H    and halve it.

```

A version which rounds halves down, in accordance with the spec at the expense of the second test case:

# Jelly, 12 bytes

```
ṢṖḊȯµÆmḤ_.ĊH

```

Try it online!

The rounding method here is closer to Jonathan Allan's:

```
Ḥ        Double,
 _       subtract
  .      one half,
   Ċ     round up,
    H    and halve.

```
> 5 votes

# Answer
# Retina, 86 bytes

```
\.5
__
\d+
*4*__
O`_+
_+ (.+) _+
$1
O`.
^ *
$.&*__:
(_+):(\1{4})*(\1\1)?_*
$#2$#3*$(.5

```

Try it online! Link includes test cases. Explanation:

```
\.5
__
\d+
*4*__

```

Since Retina can't readily handle fractional or zero numbers, each number is represented in unary as 1 more than 4 times the value. The `.5` therefore expands to 2 `_`s, while the `*4*_` applies to the whole number part, and a final `_` is suffixed.

```
O`_+

```

Sort the numbers into order.

```
_+ (.+) _+
$1

```

If there are at least three numbers, discard the first (smallest) and last (largest).

```
O`.

```

Sort the spaces to the start, thus also summing the numbers.

```
^ *
$.&*__:

```

Count the number of spaces and add `_` and a separator. This then represents the number we have to divide by.

```
(_+):(\1{4})*(\1\1)?_*
$#2$#3*$(.5

```

Divide the sum by the number of numbers, allowing for the fact that we're working in multiples of 4 times the original number, so that the integer and decimal portions can be directly extracted. This is a truncating division, but fortunately because we added an extra `_` to each number, the result effectively includes an extra 0.25, thus giving us the rounding we want.
> 4 votes

# Answer
EDIT: **This answer has since become invalid.** It was valid for about half a minute after it was posted.

# Jelly, 10 bytes

```
ṢḊṖȯƊÆmḤḞH

```

Try it online!
> 3 votes

# Answer
# JavaScript (V8), 213 211 189 176 bytes

Edit: -2 bytes because I ended with `;\n}` when I could just end with a `}`, silly mistake.

Edit 2: -22 more bytes by reading about general JS golfing tips. I managed to take out parentheses from my nested ternaries in the `r` rounding function, and used bitwise math operations to avoid using `Math.floor` and `Math.ceil`

Edit 3: -13 bytes because I was able to replace the `a.length` shortcut function with just direct calls to `a.length` to save 4 bytes. I also moved the g() function directly into the return statement, since it was only used once, which removed the rest of the bytes.

```
a=>{s=i=>a.splice(i,1)
e=_=>a.reduce((t,i)=>t+=i)/a.length
r=n=>(m=n%1,m<0.75?m>0.25?~~(n)+0.5:~~(n):n%1?-~n:n)
return a.length>2?r((a.sort((x,y)=>x-y),s(0),s(-1),e())):r(e())}

```

Try it online!

I'm sure it can be improved as I'm fairly new, but it was fun to solve this one. I believe the main things that could be improved are my rounding logic/methods, and the fact that the main function uses a function body (`{ }` and `return`).

There was one thing in the question that was inconsistent with the examples and I wasn't really sure how to handle it. I implemented it so that it's consistent with the examples, but it doesn't exactly reflect the specified rounding rules, here is the example I found to be inconsistent:

6.5, 9 -\> 8

You say it should be 8, although the average is 7.75. In the rounding rules you say it has to be at least .76 to go +1. I chose to reflect the examples instead of your rounding rules, so \>=0.75 to go +1, and \<=0.25 to go -1, between 0.25 and 0.75 (exclusive) for .5. **If the rounding specifications change, my code should be able to adapt without changing the number of bytes, by just changing the numbers in the rounding function `r`**, and maybe the order of the ternary statement depending on the rules.

Slightly ungolfed with explanation (the math operations were changed to bitwise operations and g() is directly in the return statement)

```
a => { // a is the input array
    s = i=>a.splice(i, 1); // shortcut to remove index i for 1 element
    e = _=>a.reduce((t, i) => t += i) / a.length; // get array avg
    g = _=>(a.sort((x,y)=>x-y), s(0), s(-1), e()); // what to execute when > 2: sort, remove 1st/last, get avg
    t = n=>Math.floor(n); // Math.floor shortcut

    // apply olympic rounding to number by checking the value of n%1
    r = n=>(m=n%1,m < 0.75 ? (m > 0.25 ? t(n) + 0.5 : t(n)) : Math.ceil(n));

    // if arr length > 2: round g(), otherwise round e()
    return a.length > 2 ? r(g()) : r(e());
}

```
> 3 votes

# Answer
# , ~~36~~ 35 bytes

```
[:(1r4<.@+&.+:+/%#)}:@}.^:(2<#)@/:~

```

Try it online!

Borrowed the double / floor / halve trick for rounding to 0.5 increments from Unrelated String.
> 3 votes

# Answer
# Python 3, 62 bytes

```
def f(s):z=sorted(s)[1:-1]or s;return round(2*sum(z)/len(z))/2

```

Try it online!
> 3 votes

# Answer
# Jelly, 12 bytes

```
ṢṖḊȯ⁸ÆmḤ+.ḞH

```

A monadic Link accepting a list of numbers which yields a number.

**Try it online!**

### How?

```
ṢṖḊȯ⁸ÆmḤ+.ḞH - Link, list of numbers, X
Ṣ            - sort X
 Ṗ           - remove the right-most
  Ḋ          - remove the left-most
    ⁸        - chain's left argument, X
   ȯ         - logical OR (if we have nothing left use X instead)
     Æm      - arithmetic mean
       Ḥ     - double
         .   - literal half
        +    - add
          Ḟ  - floor
           H - halve

```
> 2 votes

# Answer
# Brachylog, 19 bytes

```
o{bṀk|}⟨+/l⟩×₄<÷₂/₂

```

Try it online!

And I thought the rounding was awkward in Jelly!
> 2 votes

# Answer
# Swift, 203 bytes

```
func a(b:[Double])->Void{var r=0.0,h=0.0,l=11.0
b.forEach{(c)in h=c>h ?c:h;l=c<l ?c:l;r+=c}
var d=Double(b.count)
r=d>2 ?(r-h-l)/(d-2.0):r/d
d=Double(Int(r))
r=r-d<=0.25 ?d:r-d<=0.75 ?d+0.5:d+1
print(r)}

```

Try it online!
> 2 votes

# Answer
# PHP, 110 bytes

Seems like PHP has some good built-in functions for this. I just array\_sum the whole thing, then if there's more than two elements, subtract the min() and max() values and divide by 2 less than the length of the array.

For the rounding, I use the round() function with the PHP\_ROUND\_HALF\_DOWN flag (which = 2) on double the average, and then divide it by 2 so it goes in increments of 0.5

EDIT: for the case of \[6.5, 9\] I'm following the stated rule that 7.75 rounds to 7.5 and not 8 like in the original example given.

```
function s($s){$c=count($s);$t=array_sum($s);if($c>2){$c-=2;$t-=min($s)+max($s);}return round($t/$c*2,0,2)/2;}

```

Try it online!
> 2 votes

# Answer
# Zsh `--force_float`, ~~141~~ ~~136~~ ~~109~~ 96 bytes

Try it online! ~~109bytes~~ ~~136bytes~~ ~~141bytes~~

```
n=$1;for x ((t+=x,m=x>m?x:m,n=x<n?x:n,s=2*(#>2?(t-m-n)/(#-2):t/#)))
<<<$[(s^0+(s-s^0>.5?1:0))/2]

```

Solution follows latest spec, except for the unclear second test case. Saved a few bytes using implicit `($@)`. Saved more by moving most calculations into the `(( ))` statement.

We implicitly iterate over the arguments with `for x`, and build a running total `t`, and also find maxima, minima `m, n`. If the number of arguments `#` is greater than 2, we discard `m` and `n` from the average. `s` is 2x the resulting average. If the mantissa of `s` is greater than 0.5, round `s` up, otherwise truncate with `s^0`. Finally, divide by 2 and output.
> 2 votes

---
Tags: code-golf, math, statistics
---


title: Output the Hebrew alphabet

text:
# Question
Title: Output the Hebrew alphabet
Your task is to print this exact text:

```
אבגדהוזחטיכךלמםנןסעפףצץקרשת

```

(You are allowed to print a trailing newline)

SHA256 hash of the UTF-8 encoding of the text:

```
0ab6f1e0bf216a0db52a4a5a247f95cba6f51496de7a24dfd01f3985dfcf6085

```

Base64 encoding:

```
15DXkdeS15PXlNeV15bXl9eY15nXm9ea15zXnted16DXn9eh16LXpNej16bXpden16jXqdeq

```

### Rules

* You can't use a builtin outputting this text.
* Standard loopholes are disallowed.
* This is , so the shortest answer wins.

Good luck!

# Answer
> 27 votes
# MATLAB, ~~52~~ 51 bytes

```
[cumsum([1488 'CCCCCCCCCDADDAEADCDAEADCCC'-66]) '']

```

Example use:

```
>> [cumsum([1488 'CCCCCCCCCDADDAEADCDAEADCCC'-66]) '']
ans =
אבגדהוזחטיכךלמםנןסעפףצץקרשת

```

### Explanation

`'CCCCCCCCCDADDAEADCDAEADCCC'-66` produces the array `[1 1 ... -1 2 1 1 1]`, which contains the consecutive differences between the codepoints of the desired characters.

`[1488 ...]` prepends `1488`, so the array is now `[1488 1 1 ... -1 2 1 1 1]`.

`cumsum(...)` computes the cumulative sum: `[1488 1489 ... 1514]`.

`[... '']` concatenates with the empty string. This has the effect of converting to char (and is one byte shorter than `char(...)`)

# Answer
> 20 votes
# Jelly, ~~22~~ ~~21~~ 20 bytes

```
27R+“¿ÇÑÞæ‘¦2Ụ+1487Ọ

```

Try it online!

### Idea

If we subtract **1487** from each code point, we get the array **R** that follows.

```
1 2 3 4 5 6 7 8 9 10 12 11 13 15 14 17 16 18 19 21 20 23 22 24 25 26 27

```

That's just the range from **1** to **27**, but not in ascending order; the pairs **(11, 12)**, **(14, 15)**, **(16, 17)**, **(20, 21)**, and **(22, 23)** have been swapped.

If we take the ascending range and add **2** to **11**, **14**, **16**, **20**, and **22**, we get the array **A** that follows.

```
1 2 3 4 5 6 7 8 9 10 13 12 13 16 15 18 17 18 19 22 21 24 23 24 25 26 27

```

This is no longer a permutation of the range, but if we stably sort the range by the values in that array, we can reconstruct the original array.

### Code

```
27R+“¿ÇÑÞæ‘¦2Ụ+1487Ọ  Main link. No arguments.

27R                   Yield [1, ..., 27].
           ¦          Conditional application:
    “¿ÇÑÞæ‘             At indices 11, 14, 16, 20, and 22...
   +        2           add 2 to the corresponding value.
                      This yields the array A from the previous section.
             Ụ        Grade up; sort the indices of the result by its corresponding
                      values. This yields the array R from the previous section.
              +1487   Add 1487 to each integer in R.
                   Ọ  Unordinal; convert integers to characters.

```

# Answer
> 15 votes
## PowerShell v2+, 58 bytes (UTF-16)

```
'אבגדהוזחטיכךלמםנןסעפףצץקרשת'

```

PowerShell Unicode is UTF-16 unless explicitly specified otherwise, and then it's a crapshoot anyway since it's all UTF-16 in the background.

This just puts the literal string on the pipeline and the default `Write-Output` at the end of program execution prints it to screen.

The shortest I could get the ASCII version is **63**

```
-join([char[]]'ABCDEFGHIJLKMONQPRSUTWVXYZ['|%{[char](1423+$_)})

```

Which takes the ASCII value of the string `ABC...` and adds `1423` to each `char` to get the appropriate string.

# Answer
> 11 votes
# 05AB1E, ~~36~~ ~~29~~ ~~26~~ ~~25~~ 23 bytes

Saved 2 bytes thanks to *Adnan*

Uses CP-1252 encoding.

```
1488•’ÉÇW–moû•5Bvy<+Dç?

```

Try it online!

**Explanation**

```
1488            # push 1488 (accumulator)
•’ÉÇW–moû•      # push 2235174277545950437
5B              # convert from base-5 to base-10 (122222222230330403230403222)
  v             # for each digit in above number
   y<           # decrease it by 1
     +          # add to accumulator
      Dç?       # print a copy of accumulator converted from code point

```

# Answer
> 9 votes
# Brain-Flak, 172 bytes

This answer is based largely one DJMcMayhem's solution here so I recomend you check it out.

Like DJMcMayhem's solution this uses the `-rA` flag to reverse output and print to unicode.

```
(((((()()()()()){})))<(((({}{}{}()){({}[()])}{})){}{})>){({}[()]<(({})())>)}{}(((((()()())((((((((({}(((({}())[()])()())()())[()]))[()])()())())()())[()]))[()])()())())())())

```

Try it online!

## Explanation

I made this answer by running a bunch of micro-optimizations over the original solution provided by DJMcMayhem. These optimizations while saving bytes, make the code unreadable and the algorithm obtuse. I, to be honest, do not really understand how or what my code does.

Perhaps someday I will understand how this works...

# Answer
> 6 votes
# Python 3, 50 bytes

```
#coding:cp862
print('אבגדהוזחטיכךלמםנןסעפףצץקרשת')

```

The file must be created using the CP862 encoding or by reversing the following hexdump.

```
0000000: 23 63 6f 64 69 6e 67 3a 63 70 38 36 32 0a 70 72  #coding:cp862.pr
0000010: 69 6e 74 28 27 80 81 82 83 84 85 86 87 88 89 8b  int('...........
0000020: 8a 8c 8e 8d 90 8f 91 92 94 93 96 95 97 98 99 9a  ................
0000030: 27 29                                            ')

```

This could probably be ported to Python 2 (thus saving two bytes), but I lack the proper locale to test it. Python 3 dutifully prints an UTF-8 encoded version (or whatever is appropriate for the current locale) of the alphabet.

### Verification

```
$ base64 > hebrew.py -d <<< I2NvZGluZzpjcDg2MgpwcmludCgngIGCg4SFhoeIiYuKjI6NkI+RkpSTlpWXmJmaJyk=
$ wc -c hebrew.py
50 hebrew.py
$ echo $LANG
en_US.UTF-8
$ python3 hebrew.py
אבגדהוזחטיכךלמםנןסעפףצץקרשת

```

# Answer
> 5 votes
# CJam, 23 bytes

```
27,"%(*.0"{i_)e\}/'אf+

```

Try it online!

### How it works

```
27,                     Push [0 ... 26].
   "%(*.0"              Push that string. Its code points are [37 40 42 46 48],
                        which are [10 13 15 19 21] modulo the length of the string.
          {     }/      For each character:
           i              Compute its code point.
            _)            Push an incremented copy.
              e\          Swap the integers of [0 ... 26] at those indices.
                  'אf+  Add all resulting integers to the first character of the
                        Hebrew alphabet.

```

# Answer
> 5 votes
## JavaScript (ES6), 59 bytes

```
_=>"אבגדהוזחטיכךלמםנןסעפףצץקרשת"

```

Best I could do in ASCII was ~~80~~ ~~79~~ 78 bytes:

```
_=>String.fromCharCode(...[...0x377babbcf7f.toString(3)].map(c=>++n-c,n=1488))

```

If a character array is acceptable, 75 bytes:

```
_=>[...0x377babbcf7f.toString(3)].map(c=>String.fromCharCode(++n-c),n=1488)

```

Edit: Saved some bytes thanks to @IsmaelMiguel. Saved another byte thanks to @ETHproductions. If you use Firefox 30-57 then you can save another 2 bytes thanks to @ETHproductions using generator or array comprehensions:

```
_=>String.fromCharCode(...(for(c of 0x377babbcf7f.toString(3,n=1488))++n-c))
_=>[for(c of 0x377babbcf7f.toString(3,n=1488))String.fromCharCode(++n-c)]

```

# Answer
> 5 votes
# ///, 27 bytes

```
ABCDEFGHIQSRTVUXWYbdcfeghiq

```

Try it online!

Output is encoded in CP424.

To verify it yourself:

```
$ echo ABCDEFGHIQSRTVUXWYbdcfeghiq | ./slashes.pl | python3 -c 'print(bytes(input(), "utf-8").decode("cp424"))' | base64
15DXkdeS15PXlNeV15bXl9eY15nXm9ea15zXnted16DXn9eh16LXpNej16bXpden16jXqdeqCg==

```

# Answer
> 4 votes
# Brain-Flak, 186 bytes

```
(((((((((((((((((((((((((((((((((()()()()()){})){}{}()){({}[()])}{})){}{})())())())())())())())())())()())[()])()())()())[()])()()())[()])()())())()())[()])()()())[()])()())())())())

```

This code is 182 bytes long, and I added 4 bytes for two command line flags: `-r` and `-u`

Try it online!

Many thanks to @Neil for this awesome integer metagolfer that created this sweet way of pushing 1488 (the code point of the first character)

```
(((((((()()()()()){})){}{}()){({}[()])}{})){}{})

```

Explanation:

Pushing large number in brain-flak is relatively difficult. However, since the act of pushing a number also evaluates to that number, we can push several numbers at the same time for massive byte savings. Here is a more concrete example. The innermost part (that I wrote above) in psuedo code is

```
push(1488)

```

This expression evaluates to 1488, so we wrap the entire thing in another push statement:

```
push(push(1488) + 1)

```

This pushes 1488 *and* 1489, as well as evaluating to 1489. So we wrap this:

```
push(push(push(1488) + 1) + 1)

```

which pushes 1488, 1489, and 1490, as well as evaluating to 1490. Repeat this step for each number we need to push.

However, since the increments aren't always 1, it's a little bit more complicated than that. Here is a more readable version:

```
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
#Push 1488
(((((((()()()()()){})){}{}()){({}[()])}{})){}{})
())     # + 1
())
())
())
())
())
())
())
())
()())   # + 2
[()])   # - 1
()())   # + 2
()())
[()])   # - 1
()()()) # + 3
[()])   # - 1
()())   # + 2
())     # + 1
()())   # + 2
[()])   # - 1
()()()) # + 3
[()])   # - 1
()())   # + 2
())     # + 1
())
())

```

# Answer
> 4 votes
# ///, 54 bytes

```
אבגדהוזחטיכךלמםנןסעפףצץקרשת

```

Try it online!

There can't be any version more golfed than this :(

# Answer
> 3 votes
# 05AB1E, 28\*2-1=55 bytes

```
"אבגדהוזחטיכךלמםנןסעפףצץקרשת

```

Try it online!

-1 byte thanks to Emigna + 28 bytes thanks to DJMCMayhem ;).

# Answer
> 2 votes
# Scala/Groovy/Python 3, 9 ascii-chars + 27 2-byte chars = 63 bytes

```
print("אבגדהוזחטיכךלמםנןסעפףצץקרשת")

```

assuming UTF-8

# Scala, 59 bytes

```
print("ABCDEFGHIJLKMONQPRSUTWVXYZ["map(x=>(x+1423).toChar))

```

`x+1423` is the same as `x-'A'+1488`

# Answer
> 2 votes
# APL (Dyalog), 35 bytes

```
d←⍳27
d[⎕A⍳'KNPTV']+←2
⎕UCS 1487+⍋d

```

Try it online!

# Answer
> 1 votes
# C#6+, ~~76~~ ~~86~~ 82 bytes

```
void f()=>Console.Write("אבגדהוזחטיכךלמםנןסעפףצץקרשת");

```

First attempt at Golfing. Am I doing this right?

**EDIT**: +6 bytes for forgetting to enclose in a function. Thanks @Kevin

# C#5 and below version, ~~86~~ 82 bytes

```
void f(){Console.Write("אבגדהוזחטיכךלמםנןסעפףצץקרשת");}

```

# Answer
> 1 votes
# ArnoldC, 112 bytes

```
IT'S SHOWTIME
TALK TO THE HAND "אבגדהוזחטיכךלמםנןסעפףצץקרשת"
YOU HAVE BEEN TERMINATED

```

# Answer
> 1 votes
# Fourier, 53 bytes

```
|+2a|X1488~i+10(ia^~i)^avaXXva+3avaX^aXva+3avaX^a^a^a
```

Uses functions again.

**Try it FourIDE!**

# Answer
> 1 votes
## Keg, 34 bytes

Inspired by a Powershell solution.

```
ZYXVWTUSRPQNOMKLJIHGFEDCBA(֏+")(,

```

TIO

# Answer
> 0 votes
# **BaCon, 57 bytes**

* In most BASICs, the question mark simply represents PRINT.
* At first glance, the solution below looks like 30 bytes, but the Hebrew characters need 2 bytes of storage because of UTF-8. So there are 27 characters x 2 bytes + 1 byte for the '?' and 2 bytes for the double quotes = 57 bytes.

Solution:

```
?"אבגדהוזחטיכךלמםנןסעפףצץקרשת"

```

# Answer
> 0 votes
# s-lang, 59 bytes

Really simple answer...

```
t[][אבגדהוזחטיכךלמםנןסעפףצץקרשת]

```
* `t` \- replace function (replaces "nothing" in the input with the alphabet...)

## Try it here

# Answer
> 0 votes
# zsh, ~~25~~ 21 bytes

```
echo ${(j..):-{ת..א}}

```

My browser is messing it up: the ת should be the first letter, then the א. If you paste somewhere else, though, it should work. The old version:

```
for i in {ת..א};printf $i

```

# Answer
> 0 votes
# Java 7, 85 bytes

```
void c(){System.out.print("אבגדהוזחטיכךלמםנןסעפףצץקרשת");}

```

I'm not even gonna bother posting test code or a 'Try it here' like I usually do..

# Answer
> 0 votes
## Perl 6 (74)

```
(map (*+1488).chr,[\+] '122222222230330403230403222'.comb >>->>1.join.say

```

# Answer
> 0 votes
# Ruby, 49 bytes

```
-11.upto(15){|r|$><<(""<<r+1499-2601[r]+5202[r])}

```

Try it online!

# Answer
> 0 votes
# Haskell, 23 bytes

```
main=putStr['א'..'ת']

```

Try it online!

This works in TIO's version of Haskell

# Answer
> 0 votes
# C, 49 bytes

```
f(i){for(i=0x5d0;i<=0x5ea;i++)wprintf(L"%lc",i);}

```

Some users may need to call `setlocale` before using this but it worked fine for me.

# Answer
> 0 votes
# Clean, 62 bytes

```
Start="אבגדהוזחטיכךלמםנןסעפףצץקרשת"

```

Try it online!

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


title: Enumerate Derangements

text:
# Question
Title: Enumerate Derangements
Given some positive integer \\$n\\$ generate all derangements of \\$n\\$ objects.

### Details

* A derangement is a permutation with no fixed point. (This means in every derangement number \\$i\\$ cannot be in the \\$i\\$-th entry).
* The output should consist of derangements of the numbers \\$(1,2,\ldots,n)\\$ (or alternatively \\$(0,1,2,\ldots,n-1)\\$).
* You can alternatively always print derangements of \\$(n,n-1,\ldots,1)\\$ (or \\$(n-1,n-2,\ldots,1,0)\\$ respectively) but you have to specify so.
* The output has to be deterministic, that is whenever the program is called with some given \\$n\\$ as input, the output should be the same (which includes that the order of the derangements must remain the same), and the complete output must be done within a finite amount of time every time (it is not sufficient to do so with probability 1).
* You can assume that \\$ n \geqslant 2\\$
* For some given \\$n\\$ you can either generate all derangements or alternatively you can take another integer \\$k\\$ that serves as index and print the \\$k\\$-th derangement (in the order you chose).

### Examples

Note that the order of the derangements does not have to be the same as listed here:

```
n=2: (2,1)
n=3: (2,3,1),(3,1,2)
n=4: (2,1,4,3),(2,3,4,1),(2,4,1,3), (3,1,4,2),(3,4,1,2),(3,4,2,1), (4,1,2,3),(4,3,1,2),(4,3,2,1)

```

OEIS A000166 counts the number of derangements.

# Answer
> 8 votes
# Jelly, 6 bytes

```
Œ!=ÐṂR

```

A monadic Link accepting a positive integer which yields a list of lists of integers.

**Try it online!**

### How?

```
Œ!=ÐṂR - Link: integer, n
Œ!     - all permutations of (implicit range of [1..n])
     R - range of [1..n]
   ÐṂ  - filter keep those which are minimal by:
  =    -   equals? (vectorises)
       -   ... i.e. keep only those permutations that evaluate as [0,0,0,...,0]

```

# Answer
> 5 votes
# Brachylog, 9 bytes

```
⟦kpiᶠ≠ᵐhᵐ

```

Try it online!

This is a generator that outputs one derangement of `[0, …, n-1]` given `n`.

If we wrap it in a `ᶠ - findall` metapredicate, we get all possible generations of derangements by the generator.

### Explanation

```
⟦           The range [0, …, Input]
 k          Remove the last element
  p         Take a permutation of the range [0, …, Input - 1]
   iᶠ       Take all pair of Element-index: [[Elem0, 0],…,[ElemN-1, N-1]]
     ≠ᵐ     Each pair must contain different values
       hᵐ   The output is the head of each pair

```

# Answer
> 5 votes
# JavaScript (V8), 85 bytes

A recursive function printing all 0-based derangements.

```
f=(n,p=[],i,k=n)=>k--?f(n,p,i,k,k^i&&!p.includes(k)&&f(n,[...p,k],-~i)):i^n||print(p)

```

Try it online!

### Commented

```
f = (                   // f is a recursive function taking:
  n,                    //   n   = input
  p = [],               //   p[] = current permutation
  i,                    //   i   = current position in the permutation
  k = n                 //   k   = next value to try
) =>                    //         (a decrementing counter initialized to n)
  k-- ?                 // decrement k; if it was not equal to 0:
    f(                  //   do a recursive call:
      n, p, i, k,       //     leave all parameters unchanged
      k ^ i &&          //     if k is not equal to the position
      !p.includes(k) && //     and k does not yet appear in p[]:
        f(              //       do another recursive call:
          n,            //         leave n unchanged
          [...p, k],    //         append k to p
          -~i           //         increment i
                        //         implicitly restart with k = n
        )               //       end of inner recursive call
    )                   //   end of outer recursive call
  :                     // else:
    i ^ n ||            //   if the derangement is complete:
      print(p)          //     print it

```

# Answer
> 4 votes
# Ruby, 55 bytes

```
->n{[*0...n].permutation.select{|x|x.all?{|i|i!=x[i]}}}

```

Try it online!

Generates all 0-based derangements

# Answer
> 2 votes
# 05AB1E, 9 bytes

```
Lœʒāø€Ë_P

```

Try it online!

**Explanation**

```
L           # push [1 ... input]
 œ          # get all permutations of that list
  ʒ         # filter, keep only lists that satisfy
   āø       # elements zipped with their 1-based index
     €Ë_P   # are all not equal

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 55 bytes

```
Select[Permutations[s=Range@#],FreeQ[Ordering@#-s,0]&]&

```

Try it online!

# Answer
> 2 votes
# Japt, 8 bytes

0-based

```
o á fÈe¦

```

Try it (Footer increments all elements for easier comparison with the test cases)

```
o á fÈe¦     :Implicit input of integer
o            :Range [0,input)
  á          :Permutations
    f        :Filter
     È       :By passing each through this function
      e      :  Every element of the permutation
       ¦     :  Does not equal its 0-based index

```

# Answer
> 2 votes
# Python 2, 102 bytes

```
lambda n:[p for p in permutations(range(n))if all(i-j for i,j in enumerate(p))]
from itertools import*

```

Try it online!

0-based indexing, list of tuples.

Non-`itertools`-based solution:

# Python 2, 107 bytes

```
n=input()
for i in range(n**n):
 t=[];c=1
 for j in range(n):c*=j!=i%n not in t;t+=[i%n];i/=n
 if c:print t

```

Try it online!

0-based indexing, lines of lists, full program.

Note: This solution, even though it doesn't import the `itertools` library, isn't much longer than the other one which does import it, because most of the bulk here is building the permutations. The derangement check is really about 7 additional bytes! The reason is that the check is done on the fly as part of the building of each permutation. This isn't true for the other solution, where you have to check if each permutation returned by the `itertools.permutations` function is in fact a derangement, and, of course, the mapping itself takes a lot of bytes.

# Answer
> 2 votes
# Perl 5 `-MList::Util=none -n`, ~~100~~ 89 bytes

```
$"=',';@b=1..$_;map{%k=$q=0;say if none{++$q==$_||$k{$_}++}/\d+/g}glob join$",("{@b}")x@b

```

Try it online!

# Answer
> 2 votes
# MATL, 11 bytes

```
:tY@tb-!AY)

```

This generates all derangements in lexicographical order.

Try it online!

### Explanation with example

Consider input `3`.

```
:     % Implicit input n. Range [1 2 ... n]
      % STACK: [1 2 3]
t     % Duplicate
      % STACK: [1 2 3], [1 2 3]
Y@    % All permutations, in lexicographical order, as rows of a matrix
      % STACK: [1 2 3], [1 2 3; 1 3 2; ··· ; 3 2 1]
t     % Duplicate
      % STACK: [1 2 3], [1 2 3; 1 3 2; ··· ; 3 2 1], [1 2 3; 1 3 2; ··· ; 3 2 1]
b     % Bubble up: moves third-topmost element in stack to the top
      % STACK: [1 2 3; 1 3 2; ··· ; 3 2 1], [1 2 3; 1 3 2; ··· ; 3 1 2; 3 2 1], [1 2 3]
-     % Subtract, element-wise with broadcast
      % STACK: [1 2 3; 1 3 2; ··· ; 3 2 1], [0 0 0; 0 1 -1; ··· ; 2 -1 -1; 2 0 -2]
!A    % True for rows containining only nonzero elements
      % STACK: [1 2 3; 1 3 2; ··· ; 3 1 2; 3 2 1], [false false ··· true false]
Y)    % Use logical mask as a row index. Implicit display
      % STACK: [2 3 1; 3 1 2]

```

# Answer
> 2 votes
# Haskell, 58 bytes

```
f n|r<-[1..n]=[l|l<-mapM(\i->filter(/=i)r)r,all(`elem`l)r]

```

Try it online!

**60 bytes**

```
f n|r<-[1..n]=foldr(\i m->[x:l|l<-m,x<-r,all(/=x)$i:l])[[]]r

```

Try it online!

# Answer
> 1 votes
# , 26 bytes

```
i.(]#~0~:*/@(-|:))i.@!A.i.

```

Try it online!

```
i. (] #~ 0 ~: */@(- |:)) i.@! A. i.
i. (                   )            NB. 0..input
   (                   ) i.@! A. i. NB. x A. y returns the
                                    NB. x-th perm of y
                                    NB. i.@! returns
                                    NB. 0..input!. Combined
                                    NB. it produces all perms
                                    NB. of y
    ] #~ 0 ~: */@(- |:)             NB. those 2 are passed as
                                    NB. left and right args
                                    NB. to this
    ] #~                            NB. filter the right arg ]
                                    NB. (all perms) by:
         0 ~:                       NB. where 0 is not equal to...
              */@                   NB. the product of the
                                    NB. rows of...
                 (- |:)             NB. the left arg minus
                                    NB. the transpose of
                                    NB. the right arg, which
                                    NB. will only contain 0
                                    NB. for perms that have
                                    NB. a fixed point

```

# Answer
> 1 votes
# , ~~81~~ 80 bytes

```
function(n)unique(Filter(function(x)all(1:n%in%x&1:n-x),combn(rep(1:n,n),n,,F)))

```

Try it online!

Returns a `list` containing all derangements. Highly inefficient, as it generates \\$ n^2\choose n\\$ possible values as the size-`n` combinations of `[1..n]` repeated `n` times, then filters for permutations `1:n%in%x` and derangements, `1:n-x`.

# \+ gtools, 62 bytes

```
function(n,y=gtools::permutations(n,n))y[!colSums(t(y)==1:n),]

```

Try it online!

Much more efficient, returns a `matrix` where each row is a derangement.

# Answer
> 1 votes
# Gaia, 10 bytes

```
┅f⟨:ċ=†ỵ⟩⁇

```

Try it online!

```
┅		| push [1 2 ... n]
 f		| push permutations
  ⟨	⟩⁇	| filter where result of following is truthy
   :ċ		| dup, push [1 2 ... n]
     =†ỵ	| there is no fixed point

```

# Answer
> 1 votes
# C++ (gcc), ~~207~~ 196 bytes

-5 bytes by ceilingcat -6 bytes by Roman Odaisky

```
#include<regex>
#define v std::vector
auto p(int n){v<v<int>>r;v<int>m(n);int i=n;for(;m[i]=--i;);w:for(;std::next_permutation(&m[0],&m[n]);r.push_back(m))for(i=n;i--;)if(m[i]==i)goto w;return r;}

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), 96 bytes

```
lambda n:(p for i in range(n**n)if len({*(p:=[j for k in range(n)for j in{i//n**k%n}-{k}])})==n)

```

Try it online!

# Answer
> 0 votes
# Perl 6, 49 37 bytes

Edit: After some back and forth with Phil H, we've whittled it down to only 37 bytes:

```
(^*).permutations.grep:{all @_ Z-^@_}

```

Try it online!

By using the `Whatever` at the beginning, we can avoid the brackets (saves 2 chars). Next use a the `Z` metaoperator with `-` which takes each element of a permutation (e.g. 2,3,1) and subtracts 0,1,2 in order. If any of them are 0 (falsy) then the all junction fails.

---

Original solution was (Try it online!)

```
{permutations($_).grep:{none (for $_ {$++==$_})}}

```

# Answer
> 0 votes
# C++ (gcc), 133 bytes

I think this has grown different enough from the other submission to merit a separate answer. Finally a use for `index[array]` inside-out syntax!

```
#include<regex>
[](int n,auto&r){int i=n;for(;i[*r]=--i;);for(;std::next_permutation(*r,*r+n);)for(i=n;i--?(r[1][i]=i[*r])-i:!++r;);}

```

Try it online!

# Answer
> 0 votes
# Haskell, 76 bytes

```
n&x=[x++[i]|i<-[1..n],notElem i x,i/=length x+1]
d n=iterate(>>=(n&))[[]]!!n

```

# Answer
> 0 votes
# Python 2, 82 bytes

```
f=lambda n,i=0:i/n*[[]]or[[x]+l for l in f(n,i+1)for x in range(n)if~-(x in[i]+l)]

```

Try it online!

88 bytes as program:

```
M=[],
r=range(input())
for i in r:M=[l+[x]for l in M for x in r if~-(x in[i]+l)]
print M

```

Try it online!

93 bytes using itertools:

```
from itertools import*
r=range(input())
print[p for p in permutations(r)if all(map(cmp,p,r))]

```

Try it online!

# Answer
> 0 votes
# Charcoal, ~~44~~ 28 bytes

crossed out 44 is still regular 44

```
ＮθＩΦＥＸθθＥθ﹪÷ιＸθλθ⬤ι‹⁼μλ⁼¹№ιλ

```

Try it online! Link is to verbose version of code. Loosely based on @EricTheOutgolfer's non-itertools answer. Explanation:

```
Ｎθ                              Input `n`
     Ｘθθ                        `n` raised to power `n`
    Ｅ                           Mapped over implicit range
         θ                      `n`
        Ｅ                       Mapped over implicit range
            ι                   Outer loop index
           ÷                    Integer divided by
             Ｘθ                 `n` raised to power
               λ                Inner loop index
          ﹪     θ               Modulo `n`
   Φ                            Filtered where
                  ι             Current base conversion result
                 ⬤              All digits satisfy
                         №ιλ    Count of that digit
                       ⁼¹       Equals literal 1
                   ‹            And not
                    ⁼μλ         Digit equals its position
  Ｉ                             Cast to string
                                Implicitly print

```

# Answer
> 0 votes
# C (gcc), ~~187~~ 180 bytes

```
*D,E;r(a,n,g,e){e=g=0;if(!a--){for(;e|=D[g]==g,g<E;g++)for(n=g;n--;)e|=D[n]==D[g];for(g*=e;g<E;)printf("%d ",D[g++]);e||puts("");}for(;g<E;r(a))D[a]=g++;}y(_){int M[E=_];D=M;r(_);}

```

Try it online!

# Answer
> 0 votes
# Pyth, 12 bytes

```
f*F.e-bkT.PU

```

Try it online!

```
           UQ # [implicit Q=input] range(0,Q)
         .P  Q# [implicit Q=input] all permutations of length Q
f             # filter that on lambda T:
   .e   T     #   enumerated map over T: lambda b (=element), k (=index):
     -bk      #     b-k
 *F           # multiply all together

```

The filter works like this: if any element is at its original spot, (element-index) will be 0 and the whole product will be 0, and thus falsey.

---
Tags: code-golf, math, number, array, permutations
---