title: Encode - Shuffle - Decode

text:
# Question
Title: Encode - Shuffle - Decode
# Challenge

Your task is to encode an integer as a string of ASCII characters, then successfully decode it after said string has been randomly shuffled.

You will write two programs/functions, which will be referred to as *Encoder* and *Decoder*.

### *Encoder*

* **Input:** an integer \\$n\\$ in the range \\$\[0,2^{31}-1\]\\$.
* **Output:** a string \\$s\\$ of ASCII characters (not necessarily printable).

### *Decoder*

* **Input:** a random permutation \\$s'\\$ of the string \\$s\\$.
* **Output:** the integer \\$n\\$.

# Scoring

Let \\$A\\$ be the **maximum length** of \\$s\\$ across all possible values of \\$n\\$. If the *Encoder* acts non-deterministically (which is allowed, see below), then the \\$A\\$ will be the maximum length of \\$s\\$ that may occur (possibly \\$\infty\\$).

Let \\$L\_E\\$ be the **length of the *Encoder*** in bytes and \\$L\_D\\$ the **length of the *Decoder*** in bytes.

Then your score is \\$A\cdot(L\_E+L\_D)\\$.

Victory is awarded to the submission the **lowest score**.

# Time limit

There is a somewhat arbitrary **time limit of 1 minute** on the execution time of both the *Encoder* and the *Decoder* for a single testcase (i.e. a single value of \\$n\\$).

The goal is to avoid solution that find that brute-force the encoding by enumerating all sequences with certain properties. If your solution does something more clever than that, it will most likely fit the time constraint and will be considered valid. Likewise, if it works on TIO for some randomly selected values of \\$n\\$ it will be considered valid. Otherwise I will test it on my machine, but note that if your solution is pure brute-force it will almost certainly fail.

# Rules

* The *Encoder* and the *Decoder* must be written in the **same language**.
* The *Decoder* must output the **correct** integer \\$n\\$ for every possible permutation \\$s'\\$ of the string \\$s\\$ returned by the *Encoder*.
* The *Encoder* and the *Decoder* are **not** allowed to **share information** in any way (e.g. by means of global variables or files).
* The output of the *Encoder* need **not** be **deterministic** (that is, the same input \\$n\\$ may produce different output strings if the *Encoder* is run multiple times), but the *Decoder* must always guess the correct integer \\$n\\$.
* The *Encoder* and the *Decoder* may take and return the integer \\$n\\$ in **any convenient way** (e.g. if \\$n=14\\$ it is fine for the input to be `14`, `"14"` or `[1,4]`).
* The *Encoder* may output the string \\$s\\$ either by **printing** it on `stdout` **or** by **returning** a string, a list/array of characters or a list/array of integers in the range \\$\[0,127\]\\$; note that the *Decoder* will receive as input a permutation of \\$s\\$ as returned by the *Encoder*, so it should accept the string \\$s'\\$ in the **same format** as \\$s\\$.
* **Standard loopholes** are forbidden.
* If possible, **explain** how your code works and why the score you claim is correct.

# Example

> Assume \\$n=14\\$.
>
> * The *Encoder* receives `14` as input. It may output `"qwerty"`.
> * The *Decoder* receives a permutation of `"qwerty"` as input, for instance `"tweyqr"`. It must output `14` (in any convenient format).

The *Encoder* could have returned `[113,119,101,114,116,121]` as well, in which case the *Decoder* would have received (for instance) `[116,119,101,121,113,114]`.

Note that the string returned by the *Encoder* may also include non-printable ASCII characters (but always in the range `[0x00, ..., 0x7F]`).

# Answer
> 12 votes
# Jelly, (17 bytes + 18 bytes) × length 6 = 210 points

```
b36µỤỤ+×3µŒ¿b3U+Ṣ
```

```
Ṣ:3_J
Ṣ%3Uḅ3œ?Çḅ36
```

Try it online! (or with extra debug info)

Having had a go at solving this challenge aiming at the stated victory condition, I thought it'd be interesting to go for a hypothetical alternative victory condition: given a minimum possible maximum length for the output.

## Explanation

### Encoding

The first step in the encoding is to represent the input as base 36 (`b36`). 366 = 2176782336 \> 2147483647, so there will be at most 6 digits in the result, each of which is in the range 0–35.

Next, we transform this into a representation that contains 6 *different* digits. There are multiple possible algorithms for this, but the one used here is to add 1 to the smallest digit, 2 to the second-smallest, 3 to the third-smallest, and so on. This means that if two digits were the same, one of them will be arbitrarily considered smaller, and thus they'll become different; and obviously, this algorithm can't cause two different digits to become the same. In order to represent this in Jelly, we use  ("sort indexes by values") to get a list of the indexes in sorted order;  again to invert that, effectively mapping each element of the original to its position in sorted order; and `µ…+` to add the original to the new list. The result is a representation of the input number as six *different* digits in the 1–41 range (minimum 0+1, maximum 35+6).

We then split this into yet another form: a *sorted* list of digits in the 1–41 range, alongside a number from 1 to 720 that represents which of the 720 possible permutations the digits were in. (The `Œ¿` and  extract the permutation number and sorted list respectively.)

Finally, we convert the number from 1 to 720 into base 3 (`b3`), reverse it (`U`), and encode the six base 3 digits and six 1–41 digits via packing them each into a single ASCII character using reverse divmod (the value of the character mod 3 is the base 3 digit, the value divided by 3 is the 1–41 digit). The possible range of results is (1×3)+0=3 at minimum, and (41×3)+2=125 at maximum, fitting within our ASCII range. The packing is done via `×3` and `+`, together with an additional `µ` to make sure that every command operates on the right bit of data. (There's a bit of a golfing trick here, in that we do the multiplication by 3 *before* extracting the permutation; that saves the need to spend a byte on a grouping character.)

Incidentally, the reason to reverse the base 3 number is because it may have fewer digits than the 1–41 number. (It can't have more; the smallest number for which *n*! \> 3*n* is slightly above 6.) Jelly effectively inserts trailing zeros when adding together two numbers of different lengths, in order to make them match up; trailing zeroes would affect the interpretation of the number, but *leading* zeroes wouldn't, so the reverse is used to ensure that the extra zeroes end up somewhere that won't mess up our answer.

### Decoding

The first step in decoding is to extract the two numbers (the base 3 number and the 1–41 number). We can get their digits easily enough with division (`:3`) and modulo (`%3`) respectively, but how to know which order they were in? Well, the 1–41 number had its digits in sorted order, and digits in corresponding positions of the two numbers were stored in the same characters; thus, we can work out which order the 1–41 number's digits were shuffled into (by looking at their relative values) and know that the base-3 number's digits must have been shuffled the same way. In fact, because characters of our ASCII encoding sort the same way as the 1–41 number's digits (these were all distinct and they're more significant than the base 3 number's), we can simply put the characters of the encoding back into order with a sort . So both extractions start with , followed by `%3` or `:3` as appropriate.

While the 1–41 number's digits are still in sorted order, we have a very convenient/terse way to go back to the 0–35 digits of base 36; just subtract 1 from the first, 2 from the second, 3 from the third, and so on. In Jelly, we can do that with `_J` ("subtract index").

Meanwhile, in the other branch of the decode, we reverse the base 3 number's digits back into order (`U`), and convert it from base 3 back into a permutation index with `ḅ3`.

We can then combine the two branches with `œ?Ç`; `œ?` means "permute given this permutation index", and `Ç` means "the result of applying the line above", i.e. it's what tells Jelly to run both lines separately on the same input.

What we have now is the digits of the original number, in base 36 (due to the `_J`), and in the original order (due to the `œ?`), so we can simply do a `ḅ36` to convert back from base 36 into a single integer.

## Commentary

The TIO! link above uses 312699167 as the number to encode. This number in base 36 is `[5, 6, 6, 8, 7, 35]`, and thus shows off all aspects of the encoding: the 35 tests the limit of the 0–127 range we have; the duplicate 6s test the resolution of identical digits in the original base 36; and the fact that the digits are almost (but not quite) sorted means that the permutation number is very small, giving it many fewer digits than the base 36 number, and thus showing the need to reverse it before adding it to the original.

It's really convenient how all the constants here fit together. 366 is only *just* high enough to fit 231, 36 is only *just* high enough to fit 6!, and (36+6)×3 is only *just* high enough to fit within the 128 possibilities we have. (The last constraint here is the least tight, because we could use 0-indexing rather than 1-indexing to make use of characters in the 0-2 range. Still, that'd only give enough room to use 37 as the base rather than 36.)

# Answer
> 9 votes
# Jelly, (~~4~~ 3 bytes + ~~6~~ 5 bytes) × length 8 = ~~80~~ 64 points

```
b⁴Ä
```

```
ṢŻIḅ⁴
```

Try it online!

# Jelly, (~~2~~ 1 byte + ~~4~~ 3 bytes) × length 10 = ~~60~~ 40 points

```
Ä
```

```
ṢŻI
```

Try it online!

## Explanation

### Solution 1

This is using a different algorithm from most of the other answers. We start by encoding the value in hexadecimal (`b⁴`), as with the other answers, then take a cumulative sum (`Ä`). Each input will clearly give a different output (as both these operations are reversible), and given that the hexadecimal encoding will contain at most 8 digits whose maximums are 7 (for the 8th-last digit) and 15 (for the last to 7th-last digits), the maximum number in the output list will be 7+(7×15) = 112, less than the 127 required by the question. Additionally, the output will necessarily be in sorted order, allowing us to reverse the shuffle.

For the decoder, we first reverse the shuffle with a sort (); then reverse the cumulative sum, by prepending a zero (`Ż`) and taking the difference of consecutive pairs (`I`); then convert back from hexadecimal (`ḅ⁴`).

### Solution 2

The question actually allows us to take the input as a list of (presumably decimal) digits, so we can "cheat" by simply removing the base conversion; the maximum number used in the output will then be 2 + (9×9) = 83 (actually 82 because 2999999999 is out of range, so the worst possible input is 1999999999). The resulting encoding is pretty terrible as encodings for this problem go, but it has the advantage of being very terse to generate, which outweighs the verbosity of the encoding.

This answer feels so much like cheating that it's not my primary solution for this problem, but it seems like it's worth adding because it technically complies with the rules and produces a better score.

## Commentary

I have some algorithms in mind for getting below length 8, but it seems unlikely you could implement a length-7 algorithm in ≤9 bytes (non-cheating) or ≤5 bytes (cheating), so by the scoring in the question, this is likely the best way to do it. (I might have a go at a solution for the alternative "minimize the length of the encoding" challenge anyway, though, just for fun.)

Unlike some of the solutions, the use of 16 as the base here isn't critical; there are plenty of other numbers that would work for a length 8 solution (e.g. 18). I picked 16 for the first solution simply because Jelly has a 1-byte way to represent that, and other viable bases would need to use up multiple bytes from the program. Of course, the second solution needs to use 10 as the base in order to exploit the loophole.

Thanks to @Dennis for pointing out some newer Jelly commands that made this algorithm even terser to write.

# Answer
> 7 votes
# Shakespeare Programming Language, 10 * (264 + 494) = ~~8650 7910~~ 7580

### Encoder: 264 bytes

```
,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:Open mind.Be you nicer zero?You be the sum ofyou the product ofthe sum ofI a big big pig the sum ofa big big big big cat a big big pig.If soSpeak thy.Ford:You are the sum ofyou a cat.If soLet usAct I.

```

Try it online!

### Decoder: 494

```
,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:Open mind.Is you nicer a pig?If soRemember you.If soLet usAct I.Scene V:.Ford:Remember I.Ajax:Recall.Is you worse the sum ofPage twice the sum ofa big big cat a cat?If soYou be the difference betweenyou Page.If soOpen heart.If notlet usScene V.Scene X:.Ford:Recall.Ajax:Be I nicer zero?If soRemember I.If soLet usScene X.[Exit Ajax][Enter Page]Ford:You be the sum ofyou twice twice the sum ofa big big cat a pig.Let usAct I.

```

Try it online!

This was a thing.

The encoder encodes each digit as the digit plus the index of the digit times twelve. The decoder stores all the input in the Ford's memory and then loops over a counter, outputting then deleting each digit lower than the counter\*12 + 10.

## Explanation:

### Encoder

```
,.Ajax,.Ford,.Act I:.Scene I:.      Boilerplate introducing the two characters
[Exeunt][Enter Ajax and Ford]       Enter the two characters Ajax and Ford
                                    Ford will be handling the input
                                    Ajax will be the counter
Ajax:Open mind.                     Set Ford to the next character of input
Be you nicer zero?                  Check if it is EOF
You be the sum of                   Set Ford to the sum of
    you                             His original value (48 to 58)
    the product of
          the sum of
              I                     Ajax's value
              a big big pig         Minus 4 (this handles the offset of 48)
          the sum of                Multiplied by
              a big big big big cat 2^4
              a big big pig.        + -2^2 = 12
                                    This essentially sets Ford to (F+12*(A-4))
If soSpeak thy.                      If not EOF, print Ford's value
Ford:You are the sum ofyou a cat.   Increment Ajax's value
If soLet usAct I.                   If not EOF, Repeat again.

```

### Decoder

```
,.Ajax,.Ford,.Page,.Act I:.Scene I:.  Boilerplate introducing three characters
                                      Ajax is the spare stack
                                      Ford is the storage stack
                                      Puck is the counter, increasing by 12
[Exeunt][Enter Ajax and Ford]            Enter Ajax and Ford onto the stage
Ajax:Open mind.                          Get the next character of input
Is you nicer a pig?                      If not EOF
If soRemember you.                         Store the value in Ford's memory
If soLet usAct I.                          And repeat the loop
Scene V:.                                Otherwise move to the next scene
Ford:Remember I.                         Store Ford's value (initially -1 from EOF) in Ajax's memory
Ajax:Recall.                             Get the next value from Ford's memory
Is you worse the sum of                  Is the value smaller than
        Puck                                  Puck's value
        twice the sum ofa big big cat a cat?  + 10 ?
                                              i.e. is it the next digit?
If soYou be the difference betweenyou Puck.   If so, subtract Puck's value from Ford
If soOpen heart.                              And print Ford's value
If notlet usScene V.                     If that was not the digit, repeat
Scene X:.
Ford:Recall.                             Get the next value from Ajax's memory
Ajax:Be I nicer zero?                    Until the -1
If soRemember I.                         Returning the values to Ford's memory
If soLet us Scene X.                     Repeat until Ajax's memory is exhausted
[Exit Ajax][Enter Page]                  Swap Ajax and Page
Ford:You be the sum of                   Set Puck's value to
              you                        Puck +
              twice twice the sum of     2*2*(
                           a big big cat      4
                           a pig.             -1) = 12
Let usAct I.                             And start from the beginning again, having removed one number

```

# Answer
> 5 votes
# Python 2.7, 31 * (52 + 37) = 2759

**Encoder (~~69~~ 52 bytes):**

```
lambda n:[chr(i)if n&(1<<i)else""for i in range(32)]

```

**Decoder (~~41~~ 37 bytes):**

```
lambda s:sum([1<<(ord(c))for c in s])

```

Stores the all the non-zero bits in the input number as ascii values. The value of the ascii character stores the position of the set bit. For example the value 'a' would mean that the 97th bit is set.

A few improvements, thanks to @Delfad0r

Try it online!

# Answer
> 5 votes
# Python 3, 8 * (45 + 38) = 664

### Encoder (45 bytes):

```
lambda n:[16*i+(n>>4*i)%16 for i in range(8)]

```

### Decoder (38 bytes):

```
lambda l:sum(x%16<<x//16*4 for x in l)

```

Try it online!

# Answer
> 5 votes
# Stax, score 8 × (10+9) = 152

### Encoder, 10 bytes

```
Ç·MÉJ'♀τ│½

```

Run and debug it

```
16|E{i16*+m Full program, implicit input
16|E        Get hexadecimal digits
    {     m Map:
     i16*+    Add 16 * loop index
            Implicit output as string

```

The encoder outputs the string in an increasing order.

### Decoder, 9 bytes

```
üL∟n╫k∞‼9

```

Run and debug it

```
o{16%m16|E Full program, implicit input
o          Sort string
 {16%m     Module each element by 16
      16|E Interpret as array of hex digits

```

# Answer
> 5 votes
# 05AB1E, 8 maximum length * (8 + 7) bytes = 120

### Encoder (8)

```
hεHN16*+

```

Try it online!

### Decoder (7)

```
{16%hJH

```

Try it online!

Uses the same technique as wastl and Jonathan.

# Answer
> 4 votes
# JavaScript (ES6), 8 * (40 + 32) = 576

The encoder outputs an array of \\$0\\$ to \\$8\\$ integers. The decoder takes the same format as input.

## Encoder (40 bytes)

```
E=(n,k=0)=>n?[k|n&15,...E(n>>4,k+16)]:[]

```

## Decoder (32 bytes)

```
s=>s.map(c=>s|=c%16<<(c/4&~3))|s

```

## Demo

Try it online!

## How?

The input is divided into 8 blocks of 4 bits and each block is encoded with 1 among 16 possible characters. The most significant bit of the last block is never set.

```
       3222222222211111111110000000000
bit:   0987654321098765432109876543210
       \_/\__/\__/\__/\__/\__/\__/\__/
block:  7  6   5   4   3   2   1   0

block #0 is encoded with char. 00 to 0F (NUL to SI)
block #1 is encoded with char. 10 to 1F (DLE to ES)
block #2 is encoded with char. 20 to 2F (' ' to '/')
block #3 is encoded with char. 30 to 3F ('0' to '?')
block #4 is encoded with char. 40 to 4F ('@' to 'O')
block #5 is encoded with char. 50 to 5F ('P' to '_')
block #6 is encoded with char. 60 to 6F ('`' to 'o')
block #7 is encoded with char. 70 to 77 ('p' to 'w')

```

# Answer
> 4 votes
# Jelly, (8 + 9) bytes * 8 max-length = 136

```
b⁴+J’Ɗ⁴¡

```

**Encoder** (footer formats the list as Python would for clarity)

```
Ṣ_J‘Ɗ⁴¡ḅ⁴

```

**Decoder**

It's theoretically possible to have a max-length of six, can that be done in 22 bytes or fewer?

It's impossible with a max-length of five since \\$\sum\_{i=0}^{i=5}\binom{127+i}{127}=321402081\< 2^{31}-1\\$

### How?

Since \\$2^{31}-1\\$ is encodable as 8 hexadecimal digits (`7fffffff` or `[7,15,15,15,15,15,15,15]`) we may then add the zero-based index of each hex-digit multiplied by 16 to ensure such a conversion is always in sorted order while keeping even the rightmost value in-bounds (i.e. `[7,15,15,15,15,15,15,15] + [0,16,32,48,64,80,96,112] = [7,31,47,63,79,95,111,127]`). Decoding is then reversing this same process.

**Encoder**:

```
b⁴+J’Ɗ⁴¡ - Link: integer, n    e.g. 1234
 ⁴       - literal 16               16
b        - convert to base          [4,13,2]
       ¡ - repeat...
      ⁴  - ...16 times:
     Ɗ   -   last 3 links as a monad:
   J     -     range of length        [1,2,3]     iter 2    iter 3    ...  iter 16
  +      -     add                    [5,15,5]   [5,16,7]   [5,17,9]  ...  [5,30,35]
    ’    -     decrement              [4,14,4]   [4,15,6]   [4,16,8]  ...  [4,29,34]
         -                                                                 [4,29,34]

```

**Decoder**:

```
Ṣ_J‘Ɗ⁴¡ḅ⁴ - Link: list of integers   e.g. [29,34,4]
Ṣ         - sort                          [4,29,34]
      ¡   - repeat...
     ⁴    - ...16 times:
    Ɗ     -   last 3 links as a monad:
  J       -     range of length           [1,2,3]
 _        -     subtract                  [3,27,31]   [3,26,29]   [3,25,27]  ...  [3,12,1]
   ‘      -     increment                 [4,28,32]   [4,27,30]   [4,26,28]  ...  [4,13,2]
        ⁴ - literal 16                    16
       ḅ  - from base                     1234

```

# Answer
> 4 votes
# Shakespeare Programming Language, 31 * (472 + ~~383~~ ~~379~~ 344) = ~~26505~~ ~~26381~~ 25296

Previous score: 16909322 * (246 + 217) = **7829016086**

This is still very high, but it's the lowest I can think of right about now.

Encoder:

```
,.Ajax,.Ford,.Act I:.Scene I:.[Enter Ajax and Ford]Ajax:Remember a pig.Ford:Listen tothy.Scene V:.Ajax:Remember the remainder of the quotient betweenI a big cat.Ford:You be the quotient betweenyou a big cat.Be you nicer zero?If solet usScene V.Remember a pig.Scene X:.Ajax:Recall.Ford:Am I worse zero?If notremember I.If notlet usScene X.Ajax:You zero.Scene L:.Ford:Recall.Ajax:You be the sum ofyou a cat.Am I nicer zero?If sospeak thy.Am I worse zero?If notlet usScene L.

```

Try it online!

Decoder:

```
,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You cat.Ford:Open mind.Remember the sum ofyou I.Scene V:.Ajax:Am I nicer a cat?If soyou be twice you.Ford:If soyou be the sum ofyou a pig.If solet usScene V.[Exit Ford][Enter Page]Page:Recall.Ajax:Am I worse a cat?If notyou be the sum ofyou Ford.If notlet usAct I.Open heart

```

Try it online!

Basically, if the string contains a character with the ASCII code (n+1), the nth binary digit is set.

# Answer
> 3 votes
# Charcoal, score 10 * (10 + 15) = 250.

Uses decimal; previous base 16-based solution scored ~~328~~ ~~296~~ 264.

May output nonprintable characters. In particular, character 10 is tricky to input to Charcoal.

Encoder, 10 bytes:

```
⭆⮌Ｓ℅⁺Ｉι×χκ

```

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

Decoder, 15 bytes:

```
ＩΣＥＳ×﹪℅ιχＸχ÷℅ιχ

```

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

Version using a list of integers scores ~~360~~ 296 (base 16; decimal would score 310):

Encoder, 19 bytes:

```
ＮθＩＥ⁸⁺﹪÷θＸ¹⁶ι¹⁶×¹⁶ι

```

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

Decoder, 18 bytes:

```
ＩΣＥＥ⁸Ｎ×﹪ι¹⁶Ｘ¹⁶÷ι¹⁶

```

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

Version using printable characters scores 360 (was ~~416~~ ~~384~~ 368 in base 16):

Encoder, 19 bytes:

```
⭆⮌Ｓ℅⁺Ｉι×χ⁺κ×⁵⊕×³÷κ⁵

```

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

Decoder, 17 bytes:

```
Ｆθ⊞υ⌈Φθ¬№υκ⭆υ﹪℅ιχ

```

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

# Answer
> 3 votes
# Python 3, (208 bytes + 200 bytes) * 6 length = 2448

Try it online! (contains both, the extra byte is the newline between them).

-4 bytes (-24 score) by utilizing the empty list (which allowed more things to start at 0)

### Encoder (208 bytes)

```
def E(n,h=128):
    T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1
    d=l=0
    s=[]
    while n>=T(h,d):
        n-=T(h,d)
        d+=1
    for i in range(d):
        while n>=T(h-l,d+~i):
            n-=T(h-l,d+~i)
            l+=1
        s+=[l]
    return s

```

### Decoder (200 bytes)

```
def D(s):
    T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1
    s.sort()
    l=0
    d=len(s)
    n=sum(T(128,D)for D in range(d))
    for i in s:
        for j in range(l,i):
            n+=T(128-j,d-1)
        l=i
        d-=1
    return n

```

Observations:

* Shuffling can be losslessly reversed for strictly non-increasing (i.e. sorted) lists.
* Strictly non-increasing numerical lists of the same length can be totally ordered (as they are in Python).
* We can define that lists are ordered by length first to form a total order of all sorted lists.
* We can form an indexable sequence of these lists if we define that the only valid values in a list are integers from `0` to `127` inclusive (i.e. there exist a finite number of valid lists with length `L`).

Strategy:

* Encoder: Given a number `N`, find the `N`th valid strictly non-increasing list.
* Decoder: Given a (shuffled) valid list, sort it and return its index in the sequence of valid lists.

Common code explanation:

* `T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1`
* Compute the `n`th `d`-simplex number

+ For `d=0`, always `1`
    + For `d=1`, `n` (the number of dots in a line of dots with length `n`)
    + For `d=2`, \\$\sum\_{i=1}^{n} i\\$, (the number of dots in a triangle of dots with side length `n`)
    + For `d=3`, \\$\sum\_{j=1}^n \sum\_{i=1}^{j} i\\$, (the number of dots in a tetrahedron of dots with side length `n`)

Encoder explanation:

* `def E(n,h=128):` `d=l=0`, `s=[]`
* `n` is the input number, `h` is the "high value" (i.e. the highest number allowed + 1), `d` is the length the output will be, `s` is the output, `l` is the "low value" (starting at 0, explained more later)
* `while n>=T(h,d):`, `n-=T(h,d)`, `d+=1`
* There are `T(h,d)` valid length-`d` lists, and our calculation is easier if `n` is an index relative to the list `[0]*d` (at index `0`) instead of an actual index, so decrement `n` accordingly. This also adjusts `d` (the length) to be correct for the given `n`.
* `for i in range(d):`
* Effectively: "for the `i+1`th number in the list"

+ This is where I will explain `l`, the "low value"
    + After a number has been put into the list, no number less than it can be put in the list (to keep it sorted), so `l` is the last number that was added to the list.
    + `while n>=T(h-l,d+~i):`, `n-=T(h-l,d+~i)`, `i+=1`
    + If `n` is too big to be encoded with an `l` at this "digit", then adjust `n` accordingly and increment `l`
    + `s+=[l]`
    + Encode `n` with an `l` at this "digit".
    + At first, we have `h` options for what "digit" to put in next, but once we put in a "digit" (which is assigned to `l`), we are limited to `h-l` options for the next "digit".
    + At first there were `T(h,d)` valid lists, but we have added a "digit" `l`, decreasing the number of "digits" left to `d-1` and the number of valid next "digits" to `h-l`, so the number of valid lists after this is `T(h-l,d-1)`

Decoder explanation:

* `def D(s):`, `s.sort()`, `l=0`, `d=len(s)`
* `s` is the (shuffled) input list, so `s.sort()` it; `l` is the "low value" (`h` the "high value" is just literal `128`s in the code to save bytes), `n` is the output number, `d` is the length.
* `n=sum(T(128,D)for D in range(d))`
* Adjust `n` to the point in the sequence of `[0]*length`
* `for i in s:`
* For each digit:

+ `for j in range(l,i):`, `n+=T(128-j,d-1)`
    + Adjust `n` to the point in the sequence of `[...prevdigits, thisdigit, 0...]`

    - `l=i`: Set the "low value" to the most recent digit
        - `d-=1`: Decrement the length since we used a digit
* `return n`: After `n` has been adjusted for all of the digits, it is the right number; return it.

Sorry if this isn't clear, but here's my original nongolfed debug version Try it online!, which doesn't use the empty list, so is 1 off from all numbers used in this version

# Answer
> 3 votes
# Ruby, (36+29 bytes)\*8, score 520

Encode:

```
->n{(0..7).map{|x|(n>>x*=4)%16+x*4}}

```

Try it online!

Decode:

```
->a{a.sum{|x|x%16<<(x/4&28)}}

```

Try it online!

### How it works:

The number is encoded using 4-bit chunks and a 3-bit index.

Decoder takes the input array and puts every nibble into its place again.

# Answer
> 2 votes
# Gol\>\<\>, 8 * (14 + 13) = 216

Encoder Try it online!, 14 bytes:

```
I8FfPSD8*L+o|;

```

Decoder Try it online!, 13 bytes:

```
iEh8SD4*2$X*+

```

Since this can output unprintable ascii characters, thus messing with the decoder, there is now a version using numbers in the output / input:

Encoder Try it online!, 14 bytes:

```
I8FfPSD8*L+N|;

```

Decoder Try it online!, 13 bytes:

```
IEh8SD4*2$X*+

```

## Encoding:

The encoding works by breaking the given number into 8 x 4bit chunks. These chunks are then shifted right by 3 bit and the original location of the chunk is appended on the end as a number between 0 and 7. Thus the encoding looks like this:

```
0AAAABBB
 |__|    -> the original part of the number
     |_| -> the position of the chunk inside the original number 0 = LSB and 7 = MSB

```

# Answer
> 2 votes
# Brachylog, 17+18 bytes * 8 length = 280

## Encoder:

```
ḃ₁₆I∧7⟧₁;Iz₁~ḃ₁₆ᵐ

```

## Decoder:

```
ḃ₁₆I∧7⟧₁;Iz₁~ḃ₁₆ᵐp

```

A p can be added to the end of the encoder with no effect. The decoder is run by putting the (shuffled) result as the output and getting the original number in the input.

If there would be a (properly implemented) cumulative sum predicate the score could drop down to 20

Try it online!

# Answer
> 2 votes
# 05AB1E, score: (2 + 2 bytes) * 11 maximum length = 44

**Encoder (2 bytes):**

Try it online.

**Decoder (2 bytes):**

Try it online.

Input of the encoder and output of the decoder are a list of digits.

Port of *@ais523*'s 2nd Jelly answer.

**Explanation:**

```
.¥    # Undelta (automatically prepends a 0)
      #  i.e. [3,0,4,7,8,2,0,1,9] → [0,3,3,7,14,22,24,24,25,34]

{     # Sort
      #  i.e. [14,7,22,25,24,3,0,24,34,3] → [0,3,3,7,14,22,24,24,25,34]
 ¥    # Deltas
      #  i.e. [0,3,3,7,14,22,24,24,25,34] → [3,0,4,7,8,2,0,1,9]

```

Because  prepends a zero to the output, the length of the output is the length of the input + 1. Since \\$2^{31}-1\\$ has a length of 10 digits, the maximum length of the output is 11.

# Answer
> 2 votes
# Perl 6, 10 * (10 + 12) = ~~340~~ 220

Encoder:

```
{^@_ Z~@_}

```

Decoder:

```
{.sort X%10}

```

Try it online!

The encoder function zips each digit with the 0-index of the number. Then the encoder sorts the list of numbers and gets the modulo by 10, in other words the second digit of the number.

The total is 10, since that's the maximum length of 231-1.

# Answer
> 1 votes
# Haskell, 10\*(23+51) = 740

Here's a program that encodes, shuffles, decodes and validates values: Try it online!

## Encoder, 23 bytes

```
zipWith((+).(10*))[0..]

```

Try it online!

## Decoder, 51 bytes

```
map snd.sortOn fst.map(`divMod`10)
import Data.List

```

Try it online!

### Explanation

Since we're allowed to use input as decimal digits, we'll use that.. The encoder maps each digit that occurs to `10*index + digit`, note that all `digit`s will be in `[0..9]` so we can reverse the above by using `divMod`. After restoring the indices and the digits it's only a matter of sorting by the indices and getting rid of them.

The solution is expected to work for values up to \\$2^{31} - 1 = 2147483647\\$ which is 10 digits long, so the maximum code-point we get will be \\$9 \cdot 9 = 81 \< 128\\$. Also each digit will be converted to a "character", so we'll end up with a maximal length of 10.

# Answer
> 1 votes
# Husk, 10\*(7+8) = 150

Straight port of my Haskell solution only with the observation that \\$10 \cdot 9 = 90 \< 128\\$ (Husk's `N` is 1-based):

## Encoder, 7 bytes

```
zo+*10N

```

Try it online!

## Decoder, 8 bytes

```
m→Ö←m‰10

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog Unicode), \\$L\_E+L\_D=36; A=8 \rightarrow 288\\$.

```
d←{16⊥n-16×⍳≢n←⍵[⍋⍵]}
e←(⊢+16×⍳∘≢)16⊥⍣¯1⊢

```

Try it online! (contains 5 extra bytes for the assignments and the newline).

Uses `⎕IO←0`

### How:

```
(⊢+16×⍳∘≢)16⊥⍣¯1⊢ ⍝ Encoder; input 1234
          16⊥⍣¯1⊢ ⍝ Convert input to base 16 → 4 13 2
      ⍳∘≢          ⍝ [0..length of the list-1] → 0 1 2
   16×             ⍝ times 16 → 0 16 32
 ⊢+                ⍝ plus the original list → 4 29 34

```

---

```
{16⊥n-16×⍳≢n←⍵[⍋⍵]} ⍝ Decoder; input ⍵ → 34 4 29
              [⍋⍵]  ⍝ Grade ⍵ up → 2 0 1
             ⍵      ⍝ Index ⍵ with that list → 4 29 34
           n←       ⍝ assign that to n
      16×⍳≢         ⍝ 16×[0..length(n)-1] → 0 16 32
    n-              ⍝ subtract that from n → 4 13 2
 16⊥                ⍝ Decode from base 16 → 1234

```

# Answer
> 1 votes
# PHP, 8\*(44+53) = 776

## encoder, 44 bytes:

```
for(;$n=&$argn;$n>>=4)echo$n&15|16*$i++," ";

```

prints space separated list of integers. Run as pipe with `-nR`.

maximum 8 bytes with 4 data bits (lower nibble) and 3 weight bits (upper nibble).

Simply put:
Put each hex digit in an own character and use the upper half of the byte to store the digit´s position.

## example:

`1457893891` (`0x56e5b203`) will turn into
`0x03`, `0x10`, `0x22`, `0x3b`, `0x45`, `0x5e`, `0x66`, `0x75`
`3 16 34 59 69 94 102 117`

## decoder, 53 bytes:

```
while($i++<8)$n+=(15&$x=$argv[$i])<<($x>>4)*4;echo$n;

```

or

```
while($i++<8)$n+=(15&$x=$argv[$i])<<($x/4&~3);echo$n;

```

or

```
for(;$i<9;$x=$argv[++$i])$n+=$x%16<<($x/4&~3);echo$n;

```

take integers from command line arguments. Run with `-nr`.

---

Try them online.

# Answer
> 0 votes
# Python 2, 10\*(68+54) = 1220

```
e=lambda n:"".join(chr(int(`i`+j))for i,j in enumerate(`n`)if j<'L')
d=lambda s:int("".join(`ord(c)%10`for c in sorted(s)))

```

Try it online!

EDIT: Thanks to Jo King for the pointers - not sure why I was offsetting by 32, in retrospect.

Encodes the position and value of each place as a single character, starting with ~~\[space\] (position 0, value 0)~~ the NUL byte 0x0.

Decodes by:

* sorting the string (Python will sort characters by their ordinal value)
* converts each character into its ordinal value
* takes the last digit of each ordinal integer
* joins the integers into a string
* converts the joined string back into an int

# Answer
> 0 votes
# C (gcc), 10\*112 = 1120

```
c,i;e(i,s)char*s;{for(c=1;i;c+=10,i/=10)*s++=c+i%10;*s=0;}
d(char*s){for(i=0;c=*s++;i+=--c%10*pow(10,c/10));s=i;}

```

Try it online!

I have global variables, but they are not actually passing any info between two functions. Variable declaration for `c` is used in both functions saving me 2 bytes in code length.

A version that uses printable ASCII only for a ~~3~~ 5 byte penalty is here:

```
c,i;e(i,s)char*s;{for(c=32;i;c+=10,i/=10)*s++=c+i%10;*s=0;}
d(char*s){for(i=0;c=*s++;i+=(c-=32)%10*pow(10,c/10));s=i;}

```

Thanks @ceilingcat for 70 points improvements.

---
Tags: code-challenge, permutations, encoding, restricted-time
---


# Question
Title: Rubik-sorting a matrix (a.k.a. the torus puzzle)
The idea for this is simple: given a matrix of integers, let's sort it by applying Rubik-style movements. This means that you can select a single row or column and rotate its elements in any direction:

```
[1, 3, 2, 4]  => [3, 2, 4, 1] (rotate left for rows/up for columns)
[1, 3, 2, 4]  => [4, 1, 3, 2] (rotate right for rows/down for columns)

```

So, given a matrix of integers of any dimension, sort its elements applying only these Rubik-style transformations. A matrix

$$ \begin{bmatrix} a\_{11} & a\_{12} & a\_{13} & a\_{14} \\ a\_{21} & a\_{22} & a\_{23} & a\_{24} \\ a\_{31} & a\_{32} & a\_{33} & a\_{34} \end{bmatrix} $$

will be considered sorted iff its elements comply with the following restriction:

$$ a\_{11} \leq a\_{12} \leq a\_{13} \leq a\_{14} \leq a\_{21} \leq a\_{22} \leq a\_{23} \leq a\_{24} \leq a\_{31} \leq a\_{32} \leq a\_{33} \leq a\_{34} $$

### I/O

* Input will be a matrix of positive integers with no repeated values.
* Output will be the movements needed to sort it. As this is not a code golf challenge and you don't need to worry about its length, the proposed format for every movement is `#[UDLR]` where `#` is the number of the row or column to move (0-indexed) and `[UDLR]` is a single character in that range that specifies if the movement is Up/Down (for columns) or Left/Right (for rows). So `1U` would mean "move the 1-th column upwards" but `1R` would be "move the 1-th row rightwards". Movements will be comma-separated, so a solution will be expressed like this: `1R,1U,0L,2D`.

### Scoring

Trying to sort a matrix this way can be costly as there are a lot of possible combinations of moves, and there are also a lot of possible lists of moves that can sort it, so the goal is to write some code that sorts the N\*N matrices below. **The score will be the greatest size N that you can solve in a reasonable amount of time1 without errors (the greater the size of the matrix solved, the better). In case of a tie, the tie-breaker will be the number of movements in your found path (the shorter the path, the better).**

Example: if a user A finds a solution for N=5 and B finds a solution for N=6, B wins regardless of the length of both paths. If they both find solutions for N=6 but the solution found by A has 50 steps and B's solution has 60 steps, A wins.

Explanations on how your code works are highly encouraged and please post the solutions found so we can test them. You can use Pastebin or similar tools if the solutions are too big. Also, an estimation of the time spent by your code to find your solutions will be appreciated.

### Test cases

The following matrices (Pastebin link for a more copy-pasteable version) have been created starting from already sorted matrices by scrambling them with 10K random, Rubik-style movements:

 \begin{bmatrix} 8 & 5 & 6 \\ 11 & 10 & 1 \\ 3 & 15 & 13 \\ \end{bmatrix} \begin{bmatrix} 21 & 10 & 12 & 16 \\ 17 & 6 & 22 & 14 \\ 8 & 5 & 19 & 26 \\ 13 & 24 & 3 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 13 & 8 & 16 & 5 \\ 9 & 40 & 21 & 26 & 22 \\ 11 & 24 & 14 & 39 & 28 \\ 32 & 19 & 37 & 3 & 10 \\ 30 & 17 & 36 & 7 & 34 \\ \end{bmatrix} \begin{bmatrix} 34 & 21 & 40 & 22 & 35 & 41 \\ 18 & 33 & 31 & 30 & 12 & 43 \\ 19 & 11 & 39 & 24 & 28 & 23 \\ 44 & 1 & 36 & 5 & 38 & 45 \\ 14 & 17 & 9 & 16 & 13 & 26 \\ 8 & 3 & 47 & 6 & 25 & 4 \\ \end{bmatrix} \begin{bmatrix} 20 & 36 & 17 & 1 & 15 & 50 & 18 \\ 72 & 67 & 34 & 10 & 32 & 3 & 55 \\ 42 & 43 & 9 & 6 & 30 & 61 & 39 \\ 28 & 41 & 54 & 27 & 23 & 5 & 70 \\ 48 & 13 & 25 & 12 & 46 & 58 & 63 \\ 52 & 37 & 8 & 45 & 33 & 14 & 68 \\ 59 & 65 & 56 & 73 & 60 & 64 & 22 \\ \end{bmatrix} \begin{bmatrix} 85 & 56 & 52 & 75 & 89 & 44 & 41 & 68 \\ 27 & 15 & 87 & 91 & 32 & 37 & 39 & 73 \\ 6 & 7 & 64 & 19 & 99 & 78 & 46 & 16 \\ 42 & 21 & 63 & 100 & 4 & 1 & 72 & 13 \\ 11 & 97 & 30 & 93 & 28 & 40 & 3 & 36 \\ 50 & 70 & 25 & 80 & 58 & 9 & 60 & 84 \\ 54 & 96 & 17 & 29 & 43 & 34 & 23 & 35 \\ 77 & 61 & 82 & 48 & 2 & 94 & 38 & 66 \\ \end{bmatrix} \begin{bmatrix} 56 & 79 & 90 & 61 & 71 & 122 & 110 & 31 & 55 \\ 11 & 44 & 28 & 4 & 85 & 1 & 30 & 6 & 18 \\ 84 & 43 & 38 & 66 & 113 & 24 & 96 & 20 & 102 \\ 75 & 68 & 5 & 88 & 80 & 98 & 35 & 100 & 77 \\ 13 & 21 & 64 & 108 & 10 & 60 & 114 & 40 & 23 \\ 47 & 2 & 73 & 106 & 82 & 32 & 120 & 26 & 36 \\ 53 & 93 & 69 & 104 & 54 & 19 & 111 & 117 & 62 \\ 17 & 27 & 8 & 87 & 33 & 49 & 15 & 58 & 116 \\ 95 & 112 & 57 & 118 & 91 & 51 & 42 & 65 & 45 \\ \end{bmatrix}

Plaintext Test Cases:

```
[[8, 5, 6], [11, 10, 1], [3, 15, 13]]

[[21, 10, 12, 16], [17, 6, 22, 14], [8, 5, 19, 26], [13, 24, 3, 1]]

[[1, 13, 8, 16, 5], [9, 40, 21, 26, 22], [11, 24, 14, 39, 28], [32, 19, 37, 3, 10], [30, 17, 36, 7, 34]]

[[34, 21, 40, 22, 35, 41], [18, 33, 31, 30, 12, 43], [19, 11, 39, 24, 28, 23], [44, 1, 36, 5, 38, 45], [14, 17, 9, 16, 13, 26], [8, 3, 47, 6, 25, 4]]

[[20, 36, 17, 1, 15, 50, 18], [72, 67, 34, 10, 32, 3, 55], [42, 43, 9, 6, 30, 61, 39], [28, 41, 54, 27, 23, 5, 70], [48, 13, 25, 12, 46, 58, 63], [52, 37, 8, 45, 33, 14, 68], [59, 65, 56, 73, 60, 64, 22]]

[[85, 56, 52, 75, 89, 44, 41, 68], [27, 15, 87, 91, 32, 37, 39, 73], [6, 7, 64, 19, 99, 78, 46, 16], [42, 21, 63, 100, 4, 1, 72, 13], [11, 97, 30, 93, 28, 40, 3, 36], [50, 70, 25, 80, 58, 9, 60, 84], [54, 96, 17, 29, 43, 34, 23, 35], [77, 61, 82, 48, 2, 94, 38, 66]]

[[56, 79, 90, 61, 71, 122, 110, 31, 55], [11, 44, 28, 4, 85, 1, 30, 6, 18], [84, 43, 38, 66, 113, 24, 96, 20, 102], [75, 68, 5, 88, 80, 98, 35, 100, 77], [13, 21, 64, 108, 10, 60, 114, 40, 23], [47, 2, 73, 106, 82, 32, 120, 26, 36], [53, 93, 69, 104, 54, 19, 111, 117, 62], [17, 27, 8, 87, 33, 49, 15, 58, 116], [95, 112, 57, 118, 91, 51, 42, 65, 45]]

```

Please ask for more if you solve them all. :-) And many thanks to the people who helped me refine this challenge while in the sandbox.

---

1 A reasonable amount of time: any amount of time that doesn't undermine our patience while testing your solution. Note that TIO only runs code for 60 seconds, any amount of time over that limit will make us test the code in our machines. Example: my rather inefficient algorithm takes a few milliseconds to solve matrices of order 3x3 and 4x4, but I have just tested it with a 5x5 matrix and it took 317 seconds to solve it (in over 5 million movements, very funny if we consider that the matrix to solve was scrambled *only* 10K times). I tried to reduce the number of movements to less than 10K but I surrendered after 30 minutes executing the code.

# Answer
> 10 votes
# Nim

```
import algorithm, math, sequtils, strutils

let l = split(stdin.readLine())
var m = map(l, parseInt)
let n = int(sqrt(float(len(m))))
let o = sorted(m, system.cmp[int])

proc rotations(P, Q: int): tuple[D, L, R, U: string, P, Q: int]=
  result = (D: "D", L: "L", R: "R", U: "U", P: P, Q: Q)
  if P > n - P:
    result.D = "U"
    result.U = "D"
    result.P = n - P
  if Q > n - Q:
    result.L = "R"
    result.R = "L"
    result.Q = n - Q

proc triangle(r: int): string=
  let p = r div n
  let q = r mod n
  let i = find(m, o[r])
  let s = i div n
  let t = i mod n
  var u = s
  var v = q
  if s == p and t == q:
    return ""
  var patt = 0
  if p == s:
    u = s + 1
    patt = 4
  elif q == t:
    if q == n - 1:
      v = t - 1
      patt = 8
    else:
      u = p
      v = t + 1
      patt = 3
  elif t > q:
    patt = 2
  else:
    patt = 7
  var Q = abs(max([q, t, v]) - min([q, t, v]))
  var P = abs(max([p, s, u]) - min([p, s, u]))
  let x = p*n + q
  let y = s*n + t
  let z = u*n + v
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  let R = rotations(P, Q)

  result = case patt:
    of 2:
      repeat("$#$#," % [$v, R.D], R.P) &
        repeat("$#$#," % [$u, R.L], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) &
        repeat("$#$#," % [$u, R.R], R.Q)
    of 3:
      repeat("$#$#," % [$q, R.U], R.P) &
        repeat("$#$#," % [$p, R.L], R.Q) &
        repeat("$#$#," % [$q, R.D], R.P) &
        repeat("$#$#," % [$p, R.R], R.Q)
    of 4:
      repeat("$#$#," % [$p, R.L], R.Q) &
        repeat("$#$#," % [$q, R.U], R.P) &
        repeat("$#$#," % [$p, R.R], R.Q) &
        repeat("$#$#," % [$q, R.D], R.P)
    of 7:
      repeat("$#$#," % [$v, R.D], R.P) &
        repeat("$#$#," % [$u, R.R], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) &
        repeat("$#$#," % [$u, R.L], R.Q)
    of 8:
      repeat("$#$#," % [$s, R.R], R.Q) &
        repeat("$#$#," % [$t, R.D], R.P) &
        repeat("$#$#," % [$s, R.L], R.Q) &
        repeat("$#$#," % [$t, R.U], R.P)
    else: ""

proc Tw(p, t, P, Q: int): string =
  let S = P + Q
  result = "$#D,$#$#U,$#$#D,$#$#U," % [
    $t, if P > n - P: repeat("$#L," % $p, n - P) else: repeat("$#R," % $p, P),
    $t, if S > n - S: repeat("$#R," % $p, n - S) else: repeat("$#L," % $p, S),
    $t, if Q > n - Q: repeat("$#L," % $p, n - Q) else: repeat("$#R," % $p, Q),
    $t]

proc line(r: int): string=
  let p = n - 1
  let q = r mod n
  let i = find(m, o[r])
  var t = i mod n
  if t == q:
    return ""
  let j = t == n - 1
  var P = t - q
  let x = p*n + q
  let y = x + P
  let z = y + (if j: -1 else: 1)
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  if j:
    let R = rotations(1, P)
    result = "$#D,$#$#U,$#$#R,$#D,$#L,$#U," % [
      $t, repeat("$#$#," % [$p, R.R], R.Q),
      $t, repeat("$#$#," % [$p, R.L], R.Q),
      $p, $t, $p, $t]
  else:
    result = Tw(p, t, P, 1)

proc swap: string=
  result = ""
  if m[^1] != o[^1]:
    m = o
    for i in 0..(n div 2-1):
      result &= Tw(n - 1, n - 2*i - 1, 1, 1)
    result &= "$#R," % $(n - 1)

var moves = ""
for r in 0..(n^2 - n - 1):
  moves &= triangle(r)
if n == 2 and m[^1] != o[^1]:
  m = o
  moves &= "1R"
else:
  for r in (n^2 - n)..(n^2 - 3):
    moves &= line(r)
  if n mod 2 == 0:
    moves &= swap()
  if len(moves) > 0:
    moves = moves[0..^2]

echo moves

```

Try it online!

A quick attempt to implement the Torus puzzle solution algorithm from an article published in Algorithms 2012, 5, 18-29 that I mentioned in comments.

Accepts the input matrix in flattened form, as a line of space-delimited numbers.

Here also is a validator in Python 2. It takes two lines as input: the original scrambled matrix in the same form as the main code, and the proposed sequence of moves. The output of the validator is the matrix resulting from applying these moves.

## Explanation

In the first part of the algorithm, we order all rows except the last one.

We do this by performing series of "triangle rotations" (`proc triangle`) - the sequences of moves that result in only three cells swapping places, and all the rest staying unchanged. We take each consecutive "working" cell with coordinates \\$\[p, q\]\\$, then find the cell \\$\[s, t\]\\$ that currently contains the number that should go to \\$\[p, q\]\\$, and complete the right triangle by selecting a third point \\$\[u, v\]\\$ according to some pattern, as shown in Fig. 4 of the linked article.

In Fig. 2, the authors present 8 possible patterns and the corresponding sequences of moves, but in my code all cases have actually been covered by only 5 patterns, so that no. 1, 5, and 6 are not used.

In the second part, the last row except the two last elements is ordered by performing "three elements rotations" on a line (`proc line`), which consist of two triangle rotations each (see Fig. 3 of the article).

We select our current working cell \\$\[p, q\]\\$ as the left point, cell containing the target value \\$\[s, t\]\\$ as the central point, and \\$\[s, t+1\]\\$ as the right point. This westbound movement is named \\$T\_W\\$ in the article, and so is my string forming proc for this. If \\$t\\$ is already the last column, so that \\$t+1\\$ does not exist, we take \\$\[s, t-1\]\\$ as the third point, and modify the action accordingly: two triangle rotations are performed by patterns 7 and 8 (instead of 7 and 1 in the original \\$T\_W\\$ sequence).

Finally, if \\$n\\$ is odd, the remaining two elements must be already in place, as we are guaranteed that a solution exists. If \\$n\\$ is even, and the two remaining elements are not in place, then according to Lemma 1 (page 22), they can be swapped by a series of \\$T\_W\\$ moves, followed by one shift east (\\$=R\\$). Since the provided example swaps the first two entries, and we need to swap the last two, our `proc swap` performs \\$T\_W\\$ moves in reverse order.

In the edge case of \\$n = 2\\$ we don't need all these complex procedures at all - if the last row elements are not in place after part 1, a single \\$1R\\$ move is sufficient to make the matrix fully ordered.

**Update:** Added new `proc rotations` that reverses the direction of moves if that would result in less steps.

# Answer
> 5 votes
# Python 2, size 100 in \<30 seconds on TIO

```
import random
def f(a):
 d = len(a)
 r = []
 def V(j, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "U%d" % j:r.pop()
    else:r.append("D%d" % j)
    b = a[-1][j]
    for i in range(len(a) - 1):
     a[-1 - i][j] = a[-2 - i][j]
    a[0][j] = b
  else:
   for k in range(b):
    if r and r[-1] == "D%d" % j:r.pop()
    else:r.append("U%d" % j)
    b = a[0][j]
    for i in range(len(a) - 1):
     a[i][j] = a[i + 1][j]
    a[-1][j] = b
 def H(i, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "L%d" % i:r.pop()
    else:r.append("R%d" % i)
    a[i] = a[i][-1:] + a[i][:-1]
  else:
   for k in range(b):
    if r and r[-1] == "R%d" % i:r.pop()
    else:r.append("L%d" % i)
    a[i] = a[i][1:] + a[i][:1]
 b = sorted(sum(a, []))
 for i in range(d - 1):
  for j in range(d):
   c = b.pop(0)
   e = sum(a, []).index(c)
   if e / d == i:
    if j == 0:H(i, e - j)
    elif j < e % d:
     if i:
      V(e % d, 1)
      H(i, j - e)
      V(e % d)
      H(i, e - j)
     else:
      V(e)
      H(1, e - j)
      V(j, 1)
   else:
    if j == e % d:
     H(e / d)
     e += 1
     if e % d == 0:e -= d
    if i:
     V(j, i - e / d)
    H(e / d, e - j)
    V(j, e / d - i)
 c = [b.index(e) for e in a[-1]]
 c = [sum(c[(i + j) % d] < c[(i + k) % d] for j in range(d) for k in range(j)) % 2 and d * d or sum(abs(c[(i + j) % d] - j) for j in range(d)) for i in range(d)]
 e = min(~c[::-1].index(min(c)), c.index(min(c)), key = abs)
 H(d - 1, e)
 for j in range(d - 2):
  e = a[-1].index(b[j])
  if e > j:
   c = b.index(a[-1][j])
   if c == e:
    if e - j == 1:c = j + 2
    else:c = j + 1
   V(e)
   H(d - 1, j - e)
   V(e, 1)
   H(d - 1, c - j)
   V(e)
   H(d - 1, e - c)
   V(e, 1)
 return r

```

Try it online! Link includes three small test cases with full move output, plus a silent test of 100x100 to show that the code works (the move output would exceed TIO's limits). Explanation: The code attempts to perform an insertion sort on the array, building it up in ascending order as it goes. For all the rows except the last row, there are a number of cases:

* The element is in the correct row, but belongs in column 0. In this case, it is simply rotated until it reaches column 0.
* The element is in the correct place. In this case, nothing happens. (This is also true if the element belongs in column 0, it's just that 0 rotations happen in that case.)
* The element is in the top row but in the wrong column. In that case, it is rotated down, then horizontally until the element is in the correct column, then rotated up again.
* The element is in the correct row but in the wrong column. In that case, it is rotated up, then the row is rotated to its column, then it is rotated down, then the row is rotated back. (Effectively this is a rotation of the next case.)
* The element is in the correct column but in the wrong row. In that case, the row is rotated right, to reduce it to the last case.
* The element is in the wrong row and the wrong column. In this case, the correct column is rotated to the wrong row (skipped for the top row), that row is then rotated to the correct column, and the column is then rotated back.

The above rotations are performed in whichever direction minimises the number of steps; a size 2 square is always solved using left and up moves, regardless of the description above.

Before the bottom row is completed, it is rotated to minimise the total distance out of place, but also to ensure that the parity of the bottom row is even, as it can't be changed by the final part of the algorithm. If there is more than one rotation with the same minimal distance, the rotation with the smallest number of moves is chosen.

The algorithm for the bottom row relies on a 7-operation sequence which exchanges the elements in three columns. The sequence is applied to each of the remaining numbers of the bottom row in order in turn to bring them to their desired location; if possible the element in that location is moved to its desired location, but if a straight swap is needed the element is simply moved to the nearest available column, hopefully allowing it to be fixed up next time.

---
Tags: code-challenge, array, sorting, rubiks-cube
---


# Question
Title: A function to take three integers and return a list of integers and alphabet-letters
## Challenge

We take three positive integers `a`, `b`, and `c` as input. Using these integers, first create a sequence in the range `[0, c]` (inclusive on both ends), in steps of `b`. For example, for `a=4, b=2, c=100`, the sequence would be `[0,2,4,...,96,98,100]`.

For every number in this sequence which is divisible by `a`, replace it with the next letter in the lowercase alphabet, starting with the letter 'a' and wrapping back around to 'a' after you reach 'z'.

## Example:

Input: `a=4, b=2, c=100`
Output: `a2b6c10d14e18f22g26h30i34j38k42l46m50n54o58p62q66r70s74t78u82v86w90x94y98z`

## Challenge rules:

* You can assume that `a`, `b`, and `c` are positive integers only, where `b ≤ a ≤ c`.
* You can assume `a` is a multiple of `b`.
* You can assume `c` is divisible by `b`.
* The preferred output is a single concatenated string as above, but a list/array is acceptable as well.

## Test cases:

```
Input: a=4, b=2, c=100
Output:
a2b6c10d14e18f22g26h30i34j38k42l46m50n54o58p62q66r70s74t78u82v86w90x94y98z

Input: a=9, b=3, c=174
Output:
a36b1215c2124d3033e3942f4851g5760h6669i7578j8487k9396l102105m111114n120123o129132p138141q147150r156159s165168t174

Input: a=10, b=2, c=50
Output:
a2468b12141618c22242628d32343638e42444648f

Input: a=25, b=1, c=25
Output:
a123456789101112131415161718192021222324b

Input: a=6, b=6, c=48
Output:
abcdefghi

Input: a=6, b=3, c=48
Output: a3b9c15d21e27f33g39h45i

Input: a=2, b=1, c=100
Output: a1b3c5d7e9f11g13h15i17j19k21l23m25n27o29p31q33r35s37t39u41v43w45x47y49z51a53b55c57d59e61f63g65h67i69j71k73l75m77n79o81p83q85r87s89t91u93v95w97x99y

```

**I'd really like to see an answer in PHP**, but this challenge is open to any language. This is , so the answer should be as short as possible. Standard rules apply for functions/programs and default loopholes are forbidden.

# Answer
> 8 votes
# PHP, 67 bytes

First of all, thanks for posting such a cool challenge! I really enjoyed solving it :) Now, here's my 67 byte solution:

```
<?for(;$i<=($p=$argv)[3];$i+=$p[2])echo$i%$p[1]?$i:chr($l++%26+97);

```

To run it:

```
php -n <filename> {a} {b} {c}

```

Or Try it online!

---

Here's the same solution ungolfed and with explanation comments:

```
$a      = $argv[1];
$b      = $argv[2];
$c      = $argv[3];
$letter = 'a';
for ($i = 0; $i <= $c; $i += $b) {
    if ($i % $a) { // If $i is divisible by $a, the modulo (%) operator will return a remainder of 0, which PHP sees as a falsey value.
        echo $i;
    } else {
        $letter++;
        $letter %= 26; // Wrap $letter around to `a` after it gets to `z`.
        echo chr($letter + 97); // Use PHP's chr function to get the character. 97 is the index of `a`. http://php.net/manual/en/function.chr.php
    }
}

```

---

I did a 60 byte solution, but it doesn't wrap around :(

```
<?for($l=a;$i<=($p=$argv)[3];$i+=$p[2])echo$i%$p[1]?$i:$l++;

```

Try it online!

# Answer
> 6 votes
# Japt, 15 bytes

```
;0ôWV £CgX/U ªX

```

Test it online!

### Explanation

```
;0ôWV £CgX/U ªX    Implicit: U, V, W = inputs
;                  Reset C to the lowercase alphabet (among other variable resets).
 0ôWV              Create the inclusive range [0...W], using a step of V.
      £            Map each item X by this function:
       CgX/U         Get the character at index (X / U) in the lowercase alphabet. If X is
                     not divisible by U, this is a non-integer and the result is undefined.
             ªX      In this case (literally, if falsy), replace it with X.
                   Implicit: output result of last expression

```

# Answer
> 5 votes
# , ~~65~~ 63 bytes

```
function(a,b,c,z=seq(0,c,b)){z[x]=rep(letters,sum(x<-!z%%a));z}

```

Try it online!

*2 bytes saved thanks to JayCe!*

Returns a list of strings, as R will coerce numbers to strings. To print, simply replace the trailing `z` with `cat(z,sep="")`.

# Answer
> 5 votes
# Clojure, 84 79 77 bytes

```
#(for[i(range 0(inc %3)%2)](if(=(mod i %1)0)(char(+(mod(/ i %1)26)(int \a)))i))

```

Givin' Lisp a little love

Try it online!

(-7 bytes thanks to @NikoNyrh!)

# Answer
> 3 votes
# 05AB1E, ~~17~~ 15 bytes

```
/Ý¹*εD³ÖiA¾è¼}?

```

-2 bytes thanks to *@MagicOctopusUrn*.

Takes the input in the order `bca`.

Try it online or verify all test cases.

**Explanation:**

```
/               # Divide the second (implicit) input `c` by the first (implicit) input `b`
                #  i.e. 2 and 100 → 50
 Ý              # Take the range [0, `divided_c`]
                #  i.e. 50 → [0,1,2,...,48,49,50]
  ¹*            # Multiply it with the first input `b`
                #  [0,1,2,...,48,49,50] → [0,2,4,...,96,98,100]
    εD          # For-each in this list:
      ³Öi       #  If the current number is divisible by the third input `a`:
                #   i.e. 8 and `a=4` → 1 (truthy)
                #   i.e. 10 and `a=4` → 0 (falsey)
         A      #   Push the lowercase alphabet
          ¾     #   Push the counter_variable (which starts at 0 by default)
           è    #   Index the alphabet with this counter_variable (wraps around by default)
         ¼      #   Increase the counter_variable by 1
            }   #  Close the if
             ?  #  Output without new-line
                #  (If the if was not entered, the input is implicitly output as else-case)

```

# Answer
> 3 votes
# JavaScript (Node.js), 62 bytes

```
(a,b,c)=>(g=k=>k>c?'':(k%a?k:Buffer([97+x++%26]))+g(k+b))(x=0)

```

Try it online!

# Answer
> 3 votes
# Java 10, ~~93~~ 83 bytes

```
(a,b,c)->{var r="";for(int i=0;i<=c;i+=b)r+=i%a<1?(char)(i/a%26+97):i+"";return r;}

```

Try it online here. Thanks to Scrooble for golfing 10 bytes.

Ungolfed:

```
(a, b, c) -> { // lambda taking 3 integer arguments and returning a String
    var r = ""; // we build the result String in steps
    for(int i = 0; i <= c; i+=b) // loop over the range [0,c] in steps of b
        r += i % a < 1 ? (char) (i / a % 26 + 97) : "" + i; // if i is a multiple of a, append the next letter to r as a char, else append i
    return r; // return the result
}

```

# Answer
> 3 votes
# Perl 6,  ~~60~~  50 bytes

```
->\a,\b,\c{[~] (0,b...c).map:{$_%a??$_!!('a'..'z')[$++%26]}}

```

Test it

```
{$^a;(0,$^b...$^c).map:{$_%$a??$_!!chr 97+$++%26}}

```

Test it

```
{  # bare block lambda with parameters $a,$b,$c

  $^a; # declare param $a, but don't use it
       # (so $a can be used in the inner block)

  (
    0, $^b ... $^c  # the base sequence

  ).map:            # for each of those values
  {
    $_ % $a         # is it not divisible by `$a` ( shorter than `%%` )

    ??  $_          # if it isn't divisible just return it

    !!              # otherwise return the following

        chr         # a character from the following number

          97 +      # 'a'.ord +
          $++       # self incrementing value (starts at 0)
          % 26      # wrap around back to 'a'
  }
}

```

# Answer
> 2 votes
# C (gcc), 74  72 bytes

```
i,l;f(a,b,c){for(i=l=0;i<=c;i+=b)i%a?printf("%d",i):putchar(l++%26+97);}

```

Try it online!

# Answer
> 2 votes
# Python 2, ~~80~~ 70 bytes

Returns a list, since the OP said that is acceptable.

```
lambda a,b,c:map(lambda x:x if x%a else chr(x/a%26+97),range(0,c+1,b))

```

Very different approach from the other Python 2 answer.

Try it online!

# Answer
> 2 votes
# Python 2, ~~65~~ 63 bytes

Returns a list, since the OP said that is acceptable.

```
lambda a,b,c:[[chr(n/a%26+97),n][n%a>0]for n in range(0,c+1,b)]

```

**Try it online!**

---

Previous versions used during the creative process (working backwards):

**84 bytes**

Returns a generator expression.

```
def f(a,b,c,x=0):
    for n in range(0,c+1,b):yield n%a and n or chr(x%26+97);x+=n%a==0

```

**111 bytes**

Uses a generator for the alphabet and returns a list.

```
def g(x=0):
    while 1:yield chr(x%26+97);x+=1
A=g()
f=lambda a,b,c:[n%a and n or next(A)for n in range(0,c+1,b)]

```

# Answer
> 2 votes
# CJam, 23 bytes

```
q~),@/f%{0W):W26%'a+t}%

```

Try it online!

```
q~                              a b c
  ),                            a b [0…c]
    @/                          b [[0…a-1] [a…2a-1] ... […c]]
      f%                        [[0 b…a-b] [a a+b…2a-b] ... […c]]

        {0          t}%         Replace each first with:
          W):W26%'a+            ++W % 26 + 'a'

```

Reading input as `b a c` and dropping the `@` would be 22 bytes (not sure if that's valid).

# Answer
> 1 votes
# PHP, 79 bytes

*Note: Not too good at PHP*

```
<?for(@$l=a;$i<=($p=$argv)[3];$i+=$p[2])$o.=$i%$p[1]?$i:substr($l++,-1);echo$o;

```

Try it online!

---

# PHP, 84 bytes

This is just the same above code just in function format (since you wanted a PHP answer maybe this is better for you)

```
function f($a,$b,$c,$l=a){for(;$i<=$c;$i+=$b)$o.=$i%$a?$i:substr($l++,-1);return$o;}

```

Try it online!

# Answer
> 1 votes
# Excel VBA, 76 bytes

Takes input, `a`,`b`, and `c` from `[A1]`, `[B1]` and `[C1]`, respectively then outputs to the VBE immediate window.

```
For i=0To[C1]Step[B1]:j=i Mod[A1]:?IIf(j,i,Chr(97+k)):k=(k-(j=0))Mod 26:Next

```

# Answer
> 1 votes
# Python 2, 83 bytes

```
f=lambda a,b,c,s=0,p=0:c>=s and[chr(p%26+97),`s`][s%a>0]+f(a,b,c,s+b,p+(s%a<1))or''

```

Try it online!

# Answer
> 1 votes
# Kotlin, ~~80~~ 79 bytes

-1 thanks to O.O.Balance!

```
{a,b,c->var s="";for(x in 0..c step b)s+=if(x%a>0)x else(x/a%26+97).toChar();s}

```

Try it online!

My first time golfing (or doing anything else) in Kotlin! Probably can be improved.

Very similar to this Java answer, I realized after writing it. Save on the `return` and lose on the ternary for almost the same score.

# Answer
> 1 votes
# Python3 - ~~111~~, ~~101~~, ~~98~~, 94 bytes

```
q=iter(map(chr,range(97,123)))
[next(q)if x%a==0else x for x in[y*b for y in range((c+b)//b)]]

```

Probably not the shortest, but there's room for improvement

Try it online!

# Answer
> 1 votes
# CJam, ~~64~~ 63 bytes (*ouch*)

```
97:Y;riri:Bri\/),[{B*}*]{X\_@\%0={Yc\Y):Y'{i={97:Y;}&}{X\}?}fX;

```

Try it online!

**Explanation**

```
97:Y;                                                                 Set a variable "Y" to the ASCII value of 'a' and pop the variable from the stack
     ri                                                               Read one chunk of the input (Space-delimited)
       ri:B                                                           Set a variable "B" to the next input chunk
           ri\/                                                       Divide the next input chunk by the top value in the stack (B)
               1+                                                     Add one to make the values inclusive
                 ,                                                    Turn it into an array
                   {B*}*                                              Multiply all the array values by B
                  [     ]                                             Capture the results in an array
                         {                                   }fX      Massive for loop
                          X\_@\%0=                                    If X modulo (A value) equals zero
                                  {                   }               If condition true
                                   Yc\                                Push the character with an ASCII value of Y
                                      Y):Y                            Increase the value of Y
                                          '{i=                        If Y's value is that same as that of "{" (the character after z in ASCII)
                                              {97:Y;}                 Set Y's value back to ASCII 'a'
                                                     &                If-only flag
                                                       {  }           If condition false (from X\_@\%0=)
                                                        X\            Push X onto the stack
                                                           ?          If-else flag
                                                               ;      Pop A value from the stack

```

---

This could definitely be made better so feel free to join in!

---

### Changes

Helen cut off a byte!

Old: `97:Y;riri:Bri\/1+,[{B*}*]{X\_@\%0={Yc\Y):Y'{i={97:Y;}&}{X\}?}fX;`
New: `97:Y;riri:Bri\/),[{B*}*]{X\_@\%0={Yc\Y):Y'{i={97:Y;}&}{X\}?}fX;`

By changing `1+` to `)` we can cut off a byte.

# Answer
> 1 votes
# Haskell, ~~71~~ 69 bytes

```
(a#b)c=do n<-[0,b..c];[show n,[['a'..]!!mod(div n a)26]]!!(0^mod n a)

```

Try it online!

---

**Previous 71 bytes:**

```
(a#b)c=do n<-[0,b..c];last$show n:[[['a'..]!!mod(div n a)26]|mod n a<1]

```

Try it online!

**Explanation:**

```
(a#b)c=                         -- given the inputs a, b and c
  do n<-[0,b..c];               -- take n from the range from 0 to c with increments of b
  last$   :[   |mod n a<1]      -- if n is not divisible by a
       show n                   -- then use n converted to a string
            [   mod(div n a)26] -- otherwise divide n by a
             ['a'..]!!          -- and use the character at this position in the alphabet

```

# Answer
> 1 votes
# Charcoal, 22 bytes

```
ＮθＮη⭆Φ⊕Ｎ¬﹪ιη⎇﹪ιθι§β÷ιθ

```

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

```
Ｎθ                      Input `a`
  Ｎη                    Input `b`
       Ｎ                Third input (`c`)
      ⊕                 Increment
     Φ                  Filter over implicit range
           η            `b`
          ι             Current value
         ﹪              Modulo
        ¬               Not (i.e. divisible)
    ⭆                   Map over result and join
              ι         Current value
               θ        `a`
             ﹪          Modulo
            ⎇           Ternary
                ι       Current value
                    ι   Current value
                     θ  `a`
                   ÷    Divide
                  β     Predefined lowercase alphabet
                 §      Cyclically index

```

# Answer
> 0 votes
# Jelly, 16 bytes

```
Żmọ⁵œpƊżJṖØaṁƲ$F

```

A full program taking arguments `c b a` which prints the result.

**Try it online!**

# Answer
> 0 votes
# C (gcc/clang), ~~80~~ 68 bytes

```
f(a,b,c,i){for(i=0;i<=c;i+=b)i%a?printf("%d",i):putchar(i/a%26+97);}

```

Port of my Java answer. Try it online here.

# Answer
> 0 votes
## Clojure, 117 bytes

```
#(loop[R""A 0 i 0](if(> i %3)R(let[?(=(mod i %)0)](recur(str R(if ?(char(+(mod A 26)97))i))(if ?(inc A)A)(+ i %2)))))

```

Such imperative. :/

# Answer
> 0 votes
# Jelly, 14 bytes

```
Żmµ⁵ḍaÄ$aị¥Øao

```

Try it online!

# Answer
> 0 votes
# Python 2 and 3 - ~~123~~ 128 Bytes

```
d=-1
lambda a,b,c:[s()if i%a<1else i for i in range(0,c+1,b)]
def s():global d;d=(d+1)%26;return'abcdefghijklmnopqrstuvwxyz'[d]

```

You'll need to put `f=` in front of the `lambda` and then call it with `f(a,b,c)` but I'm pretty sure that's allowed.

# Answer
> 0 votes
# Ruby, ~~59 58~~ 55 bytes

```
->a,b,c{[w=?a]+b.step(c,b).map{|x|x%a>0?x:w=w.next[0]}}

```

Try it online!

Returns a list

---
Tags: code-golf, string, sequence, alphabet
---


title: Is the date alphabetical?

text:
# Question
Title: Is the date alphabetical?
Write a function or program that accepts a date (as a string in `YYYY-MM-DD` format) as input and returns a truthy value if that date is "alphabetical," and a falsey value if it isn't.

An alphabetical date is a date whose month, day and year are in alphabetical order when expressed as a string (and when considered specifically in M - D - Y order). For example, Sept. 26 2018 is an alphabetical date:

```
September 26th 2018 -> September twenty-sixth two thousand eighteen

September
Twenty-sixth
Two thousand eighteen

```

Another way to think of this challenge: "are the elements of a given date lexically sorted?"

Notes:

* 2018 is represented as "two thousand eighteen," not "twenty eighteen" or "two zero one eight." For another example, the year 1456 would be represented as "one thousand four hundred fifty-six," not "fourteen fifty-six."
* 26th is represented as "twenty-sixth," not "twenty-six."
* Each element of the date is considered as a whole. This is why 2018 doesn't automatically fail even though the "e" in eighteen comes before the "t" in two.

The following dates are not alphabetical:

* September 2nd 2018 ("second" should sort ahead of "September")
* April 30th 4000 ("four thousand" should sort ahead of "thirtieth")

Additional Rules:

* You will receive the date as a string, formatted like `YYYY-MM-DD`. The year will always have four digits, and the month and day will always have two digits each. Zero-padding is not represented in the string conversion (e.g., '2000-01-01' is 'January first two thousand' as you'd expect).
* You may assume that dates will always be valid (no February 30th, no Smarch 1st) and that the value of the year will be positive (no dates B.C.), but the date may be far in the future ("in the year ~~two~~ nine thousand...").
* You should return a truthy or falsey value, not necessarily a boolean `True` or `False`. If you do this in Javascript and want to return `'0'` and `0` that's fine. Of course, if you *want* to return a boolean, feel free.
* Standard loopholes are forbidden.
* This is `code-golf`

**More Examples of Alphabetical Dates**

* 2066-01-02 (January second, two thousand sixty-six)
* 1000-04-08 (April eighth, one thousand)
* 6000-08-01 (August first, six thousand)

**More Examples of Non-Alphabetical Dates**

* 1066-01-02 (January second, one thousand sixty-six)
* 1000-04-07 (April seventh, one thousand)
* 8000-08-01 (August first, eight thousand)

# Answer
> 1 votes
# 05AB1E, ~~66~~ ~~62~~ 58 bytes

```
0ì'-¡ÀDΣ2£<•88ΛηΣλšëÇñ0é≠>sîä&ζp°Lć®-αÅ®`•21вŽqT32в£Nèsè}Q

```

Try it online or verify all examples mentioned in the challenge.

**Explanation:**

```
0ì         # Prepend a "0" before the (implicit) input
           #  i.e. "2018-09-26" → "02018-09-26"
  '-¡     '# Then split on "-"
           #  i.e. "02018-09-26" → ["02018","09","26"]
     À     # Rotate it once to the left (so [0yyyy,MM,dd] becomes [MM,dd,0yyyy])
           #  i.e. ["02018","09","26"] → ["09","26","02018"]
D          # Duplicate this list
 Σ         # Sort this list by:
  2£       #  Leave only the first 2 digits of the current item
           #  (which is why the prepended 0 was there at the start for the year)
           #   i.e. "09" → "09"
           #   i.e. "02018" → "02"
    <      #  Decrease it by 1 to make it 0-indexed
           #   i.e. "09" → 8
  •88ΛηΣλšëÇñ0é≠>sîä&ζp°Lć®-αÅ®`•21в
           #  Push the list [7,3,7,0,7,7,7,0,13,10,10,0,4,12,17,6,4,17,15,2,9,17,2,19,17,6,4,17,15,2,9,19,19,19,19,19,19,19,19,19,19,17,17,11,20,18,5,5,16,14,1,8]
   ŽqT32в  #  Push the list [12,31,9]
         £ #  Split the first list into parts of that size: [[7,3,7,0,7,7,7,0,13,10,10,0],
           #    [4,12,17,6,4,17,15,2,9,17,2,19,17,6,4,17,15,2,9,19,19,19,19,19,19,19,19,19,19,17,17],
           #    [11,20,18,5,5,16,14,1,8]]
   Nè      #  Then only leave the relevant list of the three based on the sort-index
     s     #  Swap to get the earlier integer at the top of the stack again
      è    #  And use it to index into the list
           #   i.e. [7,3,7,0,7,7,7,0,13,10,10,0] and 8 → 13
 }         # Close the sort
  Q        # And check if the sorted list is equal to the duplicated list,
           # so whether the order is still [MM,dd,0yyyy] after sorting
           # (and output the result implicitly)

```

See this 05AB1E tip of mine (section *How to compress integer lists?*) to understand why `•88ΛηΣλšëÇñ0é≠>sîä&ζp°Lć®-αÅ®`•21в` is `[7,3,7,0,7,7,7,0,13,10,10,0,4,12,17,6,4,17,15,2,9,17,2,19,17,6,4,17,15,2,9,19,19,19,19,19,19,19,19,19,19,17,17,11,20,18,5,5,16,14,1,8]` and `ŽqT32в` is `[12,31,9]`.

**Additional general explanation:**

The sort function will sort all three types (day, month, year) at the same time, where we will return a truthy value only if `M < D < Y` (where these `D`, `M`, and `Y` are the values we've retrieved from the compressed lists).

Why these three lists mentioned above? If we put all words in order, categorized by type, we have the following order:

```
Sorting nr      Type        Which?

0               Month       April, August, December
1               Year        eight thousand
2               Day         eighteenth, eighth, eleventh
3               Month       February
4               Day         fifteenth, fifth, first
5               Year        five thousand, four thousand
6               Day         fourteenth, fourth
7               Month       January, July, June, March, May
8               Year        nine thousand
9               Day         ninteenth, ninth
10              Month       November, October
11              Year        one thousand
12              Day         second
13              Month       September
14              Year        seven thousand
15              Day         seventeenth, seventh
16              Year        six thousand
17              Day         sixteenth, sixth, tenth, third, thirteenth, thirtieth, thirty-first
18              Year        three thousand
19              Day         twelfth, twentieth, twenty-first through twenty-ninth
20              Year        two thousand

```

If we then look at each type individually and their original order (one thousand, two thousand, etc. for years; January, February, etc. for months; and first, second, etc. for days), the sorting numbers mentioned above are in these orders:

```
Years:  [11,20,18,5,5,16,14,1,8]
Months: [7,3,7,0,7,7,7,0,13,10,10,0]
Days:   [4,12,17,6,4,17,15,2,9,17,2,19,17,6,4,17,15,2,9,19,19,19,19,19,19,19,19,19,19,17,17]

```

# Answer
> 9 votes
# JavaScript (ES6), 101 bytes

*Saved 4 bytes thanks to @Shaggy*

Returns \\$0\\$ or \\$1\\$.

```
s=>'_414044406550'[[,m,d]=s.split`-`,+m]<(d=`_268328715819832871${6e12-12}`[+d])&d<'_6A9338704'[s[0]]

```

Try it online! or Test all dates! (includes some invalid inputs)

### How?

Each month, each day and each year is mapped to an ID in \\$\[0..10\]\\$ (\\$M\\$, \\$D\\$ and \\$Y\\$ respectively) according to the following table. We then test if we have \\$M\<D\\$ and \\$D\<Y\\$.

The last part of the lookup string for day IDs is slightly compressed by using `${6e12-12}`, which expands to `5999999999988` (19th to 31st).

```
  M | Month                D | Day                  Y | Year (millennium)
----+----------------    ----+----------------    ----+-------------------
  0 | April                1 | eighth               0 | eight thousand
  0 | August               1 | eleventh           ----+-------------------
  0 | December             1 | eighteenth           3 | four thousand
----+----------------    ----+----------------      3 | five thousand
  1 | February             2 | first              ----+-------------------
----+----------------      2 | fifth                4 | nine thousand
  4 | January              2 | fifteenth          ----+-------------------
  4 | March              ----+----------------      6 | one thousand
  4 | May                  3 | fourth             ----+-------------------
  4 | June                 3 | fourteenth           7 | seven thousand
  4 | July               ----+----------------    ----+-------------------
----+----------------      5 | ninth                8 | six thousand
  5 | October              5 | nineteenth         ----+-------------------
  5 | November           ----+----------------      9 | three thousand
----+----------------      6 | second             ----+-------------------
  6 | September          ----+----------------     10 | two thousand
                           7 | seventh
                           7 | seventeenth
                         ----+----------------
                           8 | third
                           8 | sixth
                           8 | tenth
                           8 | thirteenth
                           8 | sixteenth
                           8 | thirtieth
                           8 | thirty-first
                         ----+----------------
                           9 | twelfth
                           9 | twentieth
                           9 | twenty-*

```

---
Tags: code-golf
---


title: Track an object in 2d space

text:
# Question
Title: Track an object in 2d space
### Description

The task of this challenge is to devise a program or function that tracks a given object in an \\$n×n\\$ space.

### I/O

Your program will be given 3 inputs, which may be taken in any sensible way:

`n` will be the size of the plane's side. (so, for \\$n=5\\$, your plane will be \\$5×5\\$). You may assume `n` will always be an odd integer.

`s` will be the starting position of the object, given as a pair of \\$(x, y)\\$ coordinates.

`D` will be a vector of ordered pairs. `D` will follow the format \\$D = \[(d\_0,t\_0),(d\_1,t\_1),...,(d\_n,t\_n)\]\\$, where \\$d\_k\\$ will always be *one* of `'N', 'NE', 'E', 'SE', 'S', 'SW', 'W', 'NW'`, for the cardinal and primary intercardinal directions, and \\$t\_k\\$ will be an integer for the number of 'ticks'.

Given these inputs, your program must output a tracking of the object in the plane.

### Rules

The output **must** contain the plane's boundaries. E.g.:

```
- 21012 +
+┌─────┐
2│     │
1│     │
0│     │
1│     │
2│     │
-└─────┘

```

would be an example of an empty \\$5×5\\$ plane. The numbers above and to the side are for reference only and don't need to be printed.

You may use whatever character(s) for the boundaries, as long as it's not whitespace (or renders as whitespace). The characters you choose must delineate the full plane, meaning that there can be no gaps between them.

```
Some acceptable planes include:

┌──┐  ....  ----  +--+
│  │  .  .  |  |  |  |
│  │  .  .  |  |  |  |
└──┘; ....; ----; +--+

Nonacceptable planes include:

      ....  ....  ++++  .  .
            .  .  +  +  .  .
            .     +  +  .  .
    ; ....; ....; +  +; .  .

```

The object to be tracked may be whatever character you choose, as long as it only occupies 1 space on the plane and is different from the boundary characters.

The trace of the tracked object may also be whatever characters you choose, as long as they only occupy 1 space on the plane and are different from the object.

For each element \\$(d\_k,t\_k)\\$ in \\$D\\$, the object must move \\$t\\$ spaces towards \\$d\\$, and leave a trace behind.

If the object would hit a boundary, it'll be reflected. If the object still has any moves left, it'll keep moving in the direction it was reflected to.

For reference, these directions reflect to each other:

\\$N\rightleftharpoons S\\$ → when the top or bottom boundary is met;

\\$E\rightleftharpoons W\\$ → when a lateral boundary is met;

The final output will contain the newest possible traces, that is, if the object would leave a trace in a space where there's already a trace, the newer trace character will overwrite the older.

As usual, standard loopholes are forbidden by default.

### Scoring:

This is a challenge.

### Examples:

Input: \\$n=5\\$, \\$s=(0,0)\\$, \\$D=\[('NW',2),('S',2),('E',1)\]\\$

Working it out:

\\$t=0\\$

```
    0
 ┌─────┐
 │     │
 │     │
0│  ○  │
 │     │
 │     │
 └─────┘

```

\\$t=2\\$

```
    0
 ┌─────┐
 │○    │
 │ \   │
0│  \  │
 │     │
 │     │
 └─────┘

```

\\$t=4\\$

```
    0
 ┌─────┐
 │∧    │
 │|\   │
0│○ \  │
 │     │
 │     │
 └─────┘

```

\\$t=5\\$, which will be the output.

```
    0
 ┌─────┐
 │∧    │
 │|\   │
0│└○\  │
 │     │
 │     │
 └─────┘

```

(The 0s are just for reference, and they don't need to be in the final output.)

---

Input: \\$n=9\\$, \\$s=(3,-1)\\$, \\$D=\[('N',2),('SW',8),('SE',3),('NE',8)\]\\$

Notice that, when \\$t=10\\$:

```
      0
 ┌─────────┐
 │         │
 │         │
 │         │
 │       ∧ │
0│      /| │
 │ ○   / | │
 │⟨   /    │
 │ \ /     │
 │  ∨      │
 └─────────┘

```

The object has been reflected *twice*: once when reaching the *bottom* of the plane while going towards the \\$SW\\$, where it reflects to the \\$NW\\$; then once again when reaching the *left side* of the plane, where \\$NW\\$ reflects to \\$NE\\$.

The final output comes at \\$t=21\\$:

```
      0
 ┌─────────┐
 │    ○    │
 │     \   │
 │      \  │
 │       \ │
0│      /|⟩│
 │ ∧   / / │
 │⟨ \ / /  │
 │ \ \ /   │
 │  ∨ ∨    │
 └─────────┘

```

### Test cases:

Input: \\$n=5\\$, \\$s=(0,0)\\$, \\$D=\[('NW',2),('S',2),('E',1)\]\\$

Output:

```
    0
 ┌─────┐
 │∧    │
 │|\   │
0│└○\  │
 │     │
 │     │
 └─────┘

```

---

Input: \\$n=9\\$, \\$s=(3,-1)\\$, \\$D=\[('N',2),('SW',8),('SE',3),('NE',8)\]\\$

Output:

```
      0
 ┌─────────┐
 │    ○    │
 │     \   │
 │      \  │
 │       \ │
0│      /|⟩│
 │ ∧   / / │
 │⟨ \ / /  │
 │ \ \ /   │
 │  ∨ ∨    │
 └─────────┘

```

---

Input: \\$n=3\\$, \\$s=(1,1)\\$, \\$D=\[('N',5),('W',5)\]\\$

Output:

```
   0
 ┌───┐
 │  |│
0│-○┐│
 │  |│
 └───┘

```

---

Input: \\$n=11\\$, \\$s=(3,-5)\\$, \\$D=\[('NW',8),('E',5),('SE',3),('SW',5),('N',6),('NE',10)\]\\$

Output:

```
       0
 ┌───────────┐
 │     ∧     │
 │    / \    │
 │┌--/-\ \   │
 │ \ |/ \ \  │
 │  \|   \ \ │
0│   |   /  ⟩│
 │   |\ /  / │
 │   | /  ○  │
 │   |/ \    │
 │   ∨   \   │
 │        \  │
 └───────────┘

```

# Answer
> 9 votes
# JavaScript (ES6), 228 bytes

Takes input as `(n,x,y,[[dir,len],[dir,len],...])` where directions are encoded counterclockwise from \\$0\\$ for South to \\$7\\$ for South-West.

Outputs a string with `0` for a boundary, `1` for a trace and `3` for the final position.

```
(n,x,y,a)=>(g=X=>Y>n?'':(Y%n&&X%n&&a.map(([d,l],i)=>(M=H=>(h-X|v-Y||(k|=a[i+!l]?1:3),l--&&M(H=(h+H)%n?H:-H,h+=H,v+=V=(v+V)%n?V:-V)))(~-(D='12221')[d],V=~-D[d+2&7]),h=x+n/2,v=n/2-y,k=' ')&&k)+(X<n?'':`
`)+g(X++<n?X:!++Y))(Y=!++n)

```

Try it online!

### How?

Initializing and drawing into a 'canvas' (i.e. a matrix of characters) is a bit tedious and lengthy in JavaScript.

This code is using a different strategy: instead of storing the output in a 2D array, it builds a string character by character, from left to right and from top to bottom. At each iteration:

* We output a `0` if we're over a boundary.
* Otherwise, we simulate the full path and see if it's crossing our current position. We output either `1` or `3` if it does, or a space otherwise.
* We append a linefeed if we've reached the right boundary.

All in all, this may not be the shortest approach, but I thought it was worth trying.

# Answer
> 9 votes
# Java 10, ~~350~~ ~~343~~ ~~340~~ ~~336~~ ~~334~~ 332 bytes

```
(n,s,S,D)->{int N=n+2,x=N/2+s,y=N/2-S,i=N*N,t;var r=new char[N][N];for(;i-->0;)r[i/N][t=i%N]=i/N*t<1|i/N>n|t>n?'#':32;r[y][x]=42;for(var d:D)for(i=d[0];d[1]-->0;r[y+=i%7<2?1/y*2-1:i>2&i<6?1-y/n*2:0][x+=i>0&i<4?1-x/n*2:i>4?1/x*2-1:0]=42)i=y<2&i<2|y>=n&i>2&i<5?4-i:x<2&i>4|x>=n&i>0&i<4?8-i:y<2&i>6?5:y<n|i!=5?i:7;r[y][x]=79;return r;}

```

`D` is a 2D integer-array where the directions are 0-indexed integers: `N=0, NE=1, E=2, SE=3, S=4, SW=5, W=6, NW=7`. The starting `x,y`-coordinates will be two separate parameters `s` and `S`. The output is a character-matrix.
It uses `#` as border, `*` as trail, and `O` for the ending position (but can be all three be any ASCII characters in the unicode range `[33,99]` for the same byte-count if you'd want).

Try it online.

-8 bytes thanks to *@ceilingcat*.
Can definitely be golfed some more by simplifying the movements and in which direction we're traveling some more.

**Explanation:**

```
(n,s,S,D)->{            // Method with `n`,`s,S`,`D` parameters & char-matrix return-type
  int N=n+2,            //  Set `N` to `n+2`, since we use it multiple times
      x=N/2+s,          //  Calculate the starting `x` coordinate
      y=N/2-S,          //  Calculate the starting `y` coordinate
      i=N*N,            //  Index integer
      t;                //  Temp integer to save bytes
  var r=new char[N][N]; //  Result char-matrix of size `N` by `N`
  for(;i-->0;)          //  Loop `i` in the range (`N**2`, 0]
    r[i/N][t=i%N]=      //    Set the cell at position `i` divmod-`N` to:
      i/N*t<1|i/N>n|t>n?//     If we're at a border:
       '#'              //      Set the current cell to '#'
      :                 //     Else:
       32;              //      Set the current cell to ' ' (a space) instead
  r[y][x]=42;           //  Then set the starting position `x,y` to a '*'
  for(var d:D)          //  Loop over the `D` input:
    for(i=d[0];         //   Set `i` to the current direction
        d[1]-->0        //   Inner loop the current `d` amount of times
        ;               //     After every iteration:
         r[y+=          //      Change `y` based on the current direction
            i%7<2?      //       If the current direction is N, NE, or NW
             1/y*2-1    //        If we're at the top border:
                        //         Go one row down
                        //        Else
                        //         Go one row up
            :i>2&i<6?   //       Else-if the current direction is S, SE, or SW
             1-y/n*2    //        If we're at the bottom border
                        //         Go one row up
                        //        Else
                        //         Go one row down
            :           //       Else (directions E or W)
             0]         //        Stay in the same row
          [x+=          //      Change `x` based on the current direction
            i>0&i<4?    //       If the current direction is E, NE, or SE
             1-x/n*2    //        If we're NOT at the right border
                        //         Go one column to the right
                        //        Else:
                        //         Go one column to the left
            :i>4?       //       Else-if the current direction is W, NW, or SW
             1/x*2-1    //        If we're NOT at the left border:
                        //         Go one column to the left
                        //        Else:
                        //         Go one column to the right
            :           //       Else (directions N or S)
             0]         //        Stay in the same column
               =42)     //      And fill this new `x,y` cell with a '*'
      i=                //    Determine the new direction
        y<2&i<2|y>=n&i>2&i<5?4-i:x<2&i>4|x>=n&i>0&i<4?8-i:y<2&i>6?5:y<n|i!=5?i:7;
                        //     (See loose explanation below)
  r[y][x]=79;           //  And finally set the last `x,y` cell to 'O'
  return r;}            //  And return the result-matrix

```

`y<2&i<2|y>=n&i>2&i<5?4-i:x<2&i>4|x>=n&i>0&i<4?8-i:y<2&i>6?5:y<n|i!=5?i:7` is a golfed version of this below by using `4-i` and `8-i` for most direction changes:

```
y<2?     // If we're at the top border
 i==0?   //  If the current direction is N
  4      //   Change it to direction S
 :i==1?  //  Else-if the current direction is NE
  3      //   Change it to SE
 :i==7?  //  Else-if the current direction is NW
  5      //   Change it to SW
 :       //  Else
  i      //   Leave the direction the same
:x<2?    // Else-if we're at the left border
 i==7?   //  If the current direction is NW
  1      //   Change it to NE
 :i==6?  //  Else-if the current direction is W
  2      //   Change it to E
 :i==5?  //  Else-if the current direction is SW
  3      //   Change it to SE
 :       //  Else
  i      //   Leave the direction the same
:y>=n?   // Else-if we're at the bottom border
 i==3?   //  If the current direction is SE
  1      //   Change it to NE
 :i==4?  //  Else-if the current direction is S
  0      //   Change it to N
 :i==5?  //  Else-if the current direction is SW
  7      //   Change it to NW
 :       //  Else
  i      //   Leave the direction the same
:x>=n?   // Else-if we're at the right border
 i==1?   //  If the current direction is NE
  7      //   Change it to NW
 :i==2?  //  Else-if the current direction is E
  6      //   Change it to W
 :i==3?  //  Else-if the current direction is SE
  5      //   Change it to SW
 :       //  Else
  i      //   Leave the direction the same
:        // Else
 i       //  Leave the direction the same

```

# Answer
> 3 votes
# Charcoal, 74 bytes

```
ＮθＪ⊘⊕θ⊘⊕θＵＲ±⊕⊕θＪＮ±ＮＦＡ«≔⊟ιζＦ⊟ι«≔ζδ↷δ¶Ｆ›⊗↔ⅈθ≦±ζＦ›⊗↔ⅉθ≦⁻⁴ζ≧﹪⁸ζ↷⁴¶↶⁴↶δ↷ζ*¶↶ζＰo

```

Try it online! Link is to verbose version of code. Takes input in the format n, x, y, d where d is an array of arrays of \[distance, direction\] pairs where the direction is a numerical encoding 0 = south clockwise to 7 = south east. Explanation:

```
ＮθＪ⊘⊕θ⊘⊕θＵＲ±⊕⊕θ

```

Input `n` and draw a box whose interior is that size centred on the origin.

```
ＪＮ±Ｎ

```

Input and jump to `x` and `y` (but negate `y` because Charcoal's y-axis is increasing down).

```
ＦＡ«

```

Loop over the entries in `d`.

```
≔⊟ιζ

```

Extract the initial direction.

```
Ｆ⊟ι«

```

Repeat for the desired distance.

```
≔ζδ

```

Save the direction.

```
↷δ¶

```

Make an experimental move in that direction.

```
Ｆ›⊗↔ⅈθ≦±ζ

```

If this goes off the sides then flip the direction horizontally.

```
Ｆ›⊗↔ⅉθ≦⁻⁴ζ

```

If this goes off the top or bottom then flip the direction vertically.

```
≧﹪⁸ζ

```

Reduce the direction modulo 8 (the Pivot commands only accept values from 0 to 7).

```
↷⁴¶↶⁴

```

Undo the experimental move.

```
↶δ↷ζ*¶

```

Face the correct direction, and then print a trace and move.

```
↶ζＰo

```

Face back to the default direction, and print the object in the current position.

# Answer
> 2 votes
# C (gcc), ~~352~~ 323 bytes

Golfed down 29 bytes thanks to ceilingcat.

```
#define G(x,a)x+=a=x<2|x>m-3?-a:a
#define A(p)atoi(v[p])
m,r,c,x,y,s,a,b;main(q,v)int**v;{m=A(1)+2;int f[r=m*m];for(x=A(2)+m/2;r--;f[r]=32);for(y=A(s=3)+m/2;++s<q;)for(a=cos(A(s)*.8)*2,b=sin(A(s)*.8)*2,c=A(++s);c--;G(y,b),f[y*m+x]=42)G(x,a);for(f[y*m+x]=64;++r<m;puts(""))for(c=0;c<m;c++)putchar(c%~-m&&r%~-m?f[r*m+c]:35);}

```

Try it online!

The program takes input as command line arguments (like `a.out 10 1 1 3 5 0 4 7 2`):

* the first argument is the field size,
* the next two are initial coordinates \\$(x,y)\\$ of the actor,
* all pairs of arguments starting from the fourth are \\$(d, t)\\$ pairs where \\$d\\$ is direction (represented as a number 0..7, starting from 0=`E` and turning clockwise) and \\$t\\$ is number of steps.

### Explanation

```
// Update the coordinate AND simultaneously modify the direction (if needed)
#define G (x, a) x += a = x < 2 || x >= m - 2 ? -a : a

// Get the numeric value of an argument
#define A (p) atoi (v[p])

// variables
m, // width and height of the array with field data
r, c, // helpers
x, y, // current coordinates of the actor
s, // helper
a, b; // current direction of the movement

main (q, v) char **v;
{
    // array size is field size + 2 (for borders)
    m = A (1) + 2;

    // allocate the array
    int f[r = m * m];

    // fill the array with spaces,
    for
    (
        // but first get x of the actor
        x = A (2) + m / 2;

        r--;

        f[r] = 32
    );

    // trace: iterate over remaining commandline argument pairs
    for
    (
        // but first get y of the actor
        y = A (s = 3) + m / 2;

        ++s < q; // loop until no args left
    )
        // for each such pair
        for
        (
            a = cos (A (s) * .8) * 2,  // get the x-increment
            b = sin (A (s) * .8) * 2, // get the y-increment
            c = A (++s);  // then get the number of steps

            c--;

            // after each step:
            G (y, b), // update y and maybe the y-direction
            f[y * m + x] = 42 // draw the trail
        )
            G (x, a); // update x and maybe the x-direction

   // output
   for
   (
       f[x * m + y] = 64; // put a @ to the current position of the actor
       ++r < m; // r == -1 at the beginning of the loop so preincrement

       puts("") // terminate each row with newline
   )
       // iterate over columns in the row
       for (c = 0; c < m; c++)
           putchar
           (
               c % ~ -m && r % ~ -m ? // if it is not a border cell,
               f[r * m + c] // output the character from the array
               : 35 // otherwise output the #
           );
}

```

# Answer
> 2 votes
# JavaScript, 206 bytes

Takes input as (n,x,y,\[\[dir,len\],\[dir,len\],...\]) where directions are encoded using bitmasks :

```
S : 1
N : 2
E : 4
W : 8
SE: 5 (1|4)
SW: 9 (1|8)
NE: 6 (2|4)
NW:10 (2|8)

```

Outputs a string with

```
- 1 for top and bottom boundary
- 4 for left and right boundary
- 5 for corners
- 0 for trace
- 8 for the final position.

```

The different values for boundaries are used to evaluate the next direction

```
(n,x,y,d)=>(Q=[e=`
5`+'1'[R='repeat'](n)+5,o=n+3,-o,c=[...e+(`
4`+' '[R](n)+4)[R](n)+e],1,1+o,1-o,,-1,o-1,~o],p=1-o*(~n/2+y)-~n/2+x,c[d.map(([q,s])=>{for(a=q;s--;p+=Q[a^=c[p+Q[a]]*3])c[p]=0}),p]=8,c.join``)

```

*Less golfed*

```
F=(n,x,y,d) => (
  o = n+3, // vertical offset, accounting for boundaries and newline
  // Q = offsets for different directions, bitmask indexed
  Q = [,  // 0000 no direction
     o,   // 0001 S
     -o,  // 0010 N
     ,    // 0011 NS - invalid
     1 ,  // 0100 E
     1+o, // 0101 SE
     1-o, // 0110 NE
     ,    // 0111 NSE - invalid
     -1,  // 1000 W
     o-1, // 1001 SW
    -o-1],// 1010 NW

  e = `\n5`+'1'.repeat(n)+5, // top and bottom boundary
  c = [...e + (`\n4` + ' '.repeat(n) + 4).repeat(n) + e], // canvas
  p = 1 - o*(~n/2+y) - ~n/2 + x, // start position
  d.map( ([q,s]) => { // repeat for each element in 'd'
    a = q; // starting offset pointer - will change when bounce
    while( s-- )
    {
      c[p] = 0; // trace
      b = c[p + Q[a]] // boundary value or 0 (space count 0)
      a ^= b * 3 // xor with 0 if no bounce, else 3 or 12 or 15
      p += Q[q]  // advance position
    }
  })
  c[p] = 8, // set end position
  c.join``
)

```

**TEST**

```
var F=
(n,x,y,d)=>(Q=[e=`
5`+'1'[R='repeat'](n)+5,o=n+3,-o,c=[...e+(`
4`+' '[R](n)+4)[R](n)+e],1,1+o,1-o,,-1,o-1,~o],p=1-o*(~n/2+y)-~n/2+x,c[d.map(([q,s])=>{for(a=q;s--;p+=Q[a^=c[p+Q[a]]*3])c[p]=0}),p]=8,c.join``)

var out=x=>O.textContent+=x

var test=(n,x,y,d)=>{
  var dd = d.map(([d,s])=>[,'S','N',,'E','SE','NE',,'W','SW','NW'][d]+' '+s)
  out([n,x,y]+' ['+dd+']')
  out(F(n,x,y,d))
  out('\n\n')
}

test(5,0,0,[[10,2],[1,2],[4,1]])
test(9,3,-1,[[2,2],[9,8],[5,3],[6,8]])
test(11,3,-5,[[10,8],[4,5],[5,2],[9,5],[2,6],[6,10]])
```

```
<pre id=O></pre>
```

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