# Question
Title: How many consecutive descending numbers in my number?
2019 has come and probably everyone has noticed the peculiarity of this number: it's in fact composed by two sub-numbers (20 and 19) representing a sequence of consecutive descending numbers.

### Challenge

Given a number `x`, return the length of the maximum sequence of consecutive, descending numbers that can be formed by taking sub-numbers of `x`.

Notes :

* sub-numbers cannot contain leading zeros (e.g. `1009` cannot be split into `10`,`09`)
* consecutive and descending means that a number in the sequence must be equal to the previous number -1, or \\$n\_{i+1} = n\_{i}-1\\$ (e.g. `52` cannot be split into `5,2` because `5` and `2` are not consecutive, `2 ≠ 5 - 1`)
* the sequence must be obtained by using the full number, e.g. in `7321` you can't discard `7` and get the sequence `3`,`2`,`1`
* only one sequence can be obtained from the number, e.g. `3211098` cannot be split into two sequences `3`,`2`,`1` and `10`,`9`,`8`

### Input

* An integer number (`>= 0`) : can be a number, or a string, or list of digits

### Output

* A single integer given the maximum number of decreasing sub-numbers (note that the lower-bound of this number is `1`, i.e. a number is composed by itself in a descending sequence of length one)

### Examples :

```
2019         --> 20,19           --> output : 2
201200199198 --> 201,200,199,198 --> output : 4
3246         --> 3246            --> output : 1
87654        --> 8,7,6,5,4       --> output : 5
123456       --> 123456          --> output : 1
1009998      --> 100,99,98       --> output : 3
100908       --> 100908          --> output : 1
1110987      --> 11,10,9,8,7     --> output : 5
210          --> 2,1,0           --> output : 3
1            --> 1               --> output : 1
0            --> 0               --> output : 1
312          --> 312             --> output : 1
191          --> 191             --> output : 1

```

### General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

# Answer
# JavaScript (ES6), 56 bytes

A port of ArBo's Python answer is significantly shorter. However, it fails on some test cases because of too much recursion.

```
f=(n,a=0,c=0,s)=>a<0?f(n,a-~c):n==s?c:f(n,--a,c+1,[s]+a)

```

Try it online!

---

# JavaScript (ES6), 66 bytes

Takes input as a string.

```
f=(s,n=x='',o=p=n,i=0)=>s[i++]?o==s?i:f(s,--n,o+n,i):f(s,p+s[x++])

```

Try it online!

### Commented

```
f = (               // f = recursive function taking:
  s,                //   s = input number, as a string
  n =               //   n = counter
  x = '',           //   x = position of the next digit to be added to p
  o = p = n,        //   o = generated output; p = prefix
  i = 0             //   i = number of consecutive descending numbers
) =>                //
  s[i++] ?          // increment i; if s[i] was defined:
    o == s ?        //   if o is matching s:
      i             //     stop recursion and return i
    :               //   else:
      f(            //     do a recursive call with:
        s,          //       s unchanged
        --n,        //       n - 1
        o + n,      //       (n - 1) appended to o
        i           //       i unchanged (but it was incremented above)
      )             //     end of recursive call
  :                 // else:
    f(              //   this is a dead end; try again with one more digit in the prefix:
      s,            //     s unchanged
      p + s[x++]    //     increment x and append the next digit to p
    )               //   end of recursive call

```
> 6 votes

# Answer
# Jelly,  ~~15~~  9 bytes

Bugfix thanks to Dennis

```
ŻṚẆDfŒṖẈṀ

```

**Try it online!** (even `321` takes half a minute since the code is at least \\$O(N^2)\\$)

### How?

```
ŻṚẆDfŒṖẈṀ - Link: integer, n
Ż         - [0..n]
 Ṛ        - reverse
  Ẇ       - all contiguous slices (of implicit range(n)) = [[n],...,[2],[1],[0],[n,n-1],...,[2,1],[1,0],...,[n,n-1,n-2,...,2,1,0]]
   D      - to decimal (vectorises)
     ŒṖ   - partitions of (implicit decimal digits of) n
    f     - filter discard from left if in right
       Ẉ  - length of each
        Ṁ - maximum

```
> 6 votes

# Answer
# Perl 6, ~~43 41~~ 40 bytes

*-1 byte thanks to nwellnhof*

```
{/(<-[0]>.*?|0)+<?{[==] 1..*Z+$0}>/;+$0}

```

Try it online!

Regex based solution. I'm trying to come up with a better way to match from a descending list instead, but Perl 6 doesn't do partitions well

### Explanation:

```
{                                        }  # Anonymous code block
 /                                /;        # Match in the input
   <-[0]>.*?      # Non-greedy number not starting with 0
            |0    # Or 0
  (           )+  # Repeatedly for the rest of the number
                <?{             }>  # Where
                        1..*Z+$0       # Each matched number plus the ascending numbers
                                       # For example 1,2,3 Z+ 9,8,7 is 10,10,10
                   [==]                # Are all equal
                                    +$0  # Return the length of the list

```
> 5 votes

# Answer
# Python 3, 232 228 187 181 180 150 149 bytes

-1 thanks to @Jonathan Frech

```
e=enumerate
t=int
h=lambda n,s=1:max([1]+[i-len(n[j:])and h(n[j:],s+1)or s+1for j,_ in e(n)for i,_ in e(n[:j],1)if(t(n[:j])-t(n[j:j+i])==1)*t(n[0])])

```

Try it online!

Initial ungolfed code:

```
def count_consecutives(left, right, so_far=1):
    for i,_ in enumerate(left, start=1):
        left_part_of_right, right_part_of_right = right[:i], right[i:]
        if (int(left) - int(left_part_of_right)) == 1:
            if i == len(right):
                return so_far + 1
            return count_consecutives(left_part_of_right, right_part_of_right, so_far + 1)
    return so_far

def how_many_consecutives(n):
    for i, _ in enumerate(n):
        left, right = n[:i], n[i:]
        for j, _ in enumerate(left, start=1):
            left_part_of_right = right[:j]
            if int(left) - int(left_part_of_right) == 1 and int(n[i]) > 0:
                return count_consecutives(left, right)
    return 1

```
> 4 votes

# Answer
# Python 2, ~~78~~ ~~74~~ 73 bytes

```
l=lambda n,a=0,c=0,s="":c*(n==s)or a and l(n,a-1,c+1,s+`a-1`)or l(n,a-~c)

```

Try it online!

<sub> -1 byte thanks to Arnauld </sub>

Takes input as a string. The program rather quickly runs into Python's recursion depth limit, but it can finish most of the test cases.

### How it works

```
l=lambda n,                              # The input number, in the form of a string
         a=0,                            # The program will attempt to reconstruct n by
                                         #  building a string by pasting decreasing
                                         #  numbers, stored in a, after each other.
         c=0,                            # A counter of the amount of numbers
         s="":                           # The current constructed string
              c*(n==s)                   # Return the counter if s matches n
              or                         # Else
              a and l(n,a-1,c+1,s+`a-1`) # If a is not yet zero, paste a-1 after s
              or                         # Else
              l(n,a-~c)                  # Start again, from one higher than last time

```
> 4 votes

# Answer
# 05AB1E, 10 bytes

```
ÝRŒʒJQ}€gà

```

Extremely slow, so the TIO below only works for test cases below 750..

Try it online.

**Explanation:**

```
Ý           # Create a list in the range [0, (implicit) input]
            #  i.e. 109 → [0,1,2,...,107,108,109]
 R          # Reverse it
            #  i.e. [0,1,2,...,107,108,109] → [109,108,107,...,2,1,0]
  Œ         # Get all possible sublists of this list
            #  i.e. [109,108,107,...,2,1,0]
            #   → [[109],[109,108],[109,108,107],...,[2,1,0],[1],[1,0],[0]]
   ʒ  }     # Filter it by:
    J       #  Where the sublist joined together
            #   i.e. [10,9] → "109"
            #   i.e. [109,108,107] → "109108107"
     Q      #  Are equal to the (implicit) input
            #   i.e. 109 and "109" → 1 (truthy)
            #   i.e. 109 and "109108107" → 0 (falsey)
       €g   # After filtering, take the length of each remaining inner list
            #  i.e. [[109],[[10,9]] → [1,2]
         à  # And only leave the maximum length (which is output implicitly)
            #  i.e. [1,2] → 2

```
> 3 votes

# Answer
# Pyth, 16 bytes

```
lef!.EhM.+vMT./z

```

Try it online here, or verify all the test cases at once here.

```
lef!.EhM.+vMT./z   Implicit: z=input as string
             ./z   Get all divisions of z into disjoint substrings
  f                Filter the above, as T, keeping those where the following is truthy:
          vMT        Parse each substring as an int
        .+           Get difference between each pair
      hM             Increment each
   !.E               Are all elements 0? { NOT(ANY(...)) }
 e                 Take the last element of the filtered divisions
                     Divisions are generated with fewest substrings first, so last remaining division is also the longest
l                  Length of the above, implicit print

```
> 3 votes

# Answer
# Jelly, 11 bytes

```
ŒṖḌ’Dɗ\ƑƇẈṀ

```

Byte for byte, no match for the other Jelly solution, but this one should be roughly \\$O\left(n^{0.3}\right)\\$.

Try it online!

### How it works

```
ŒṖḌ’Dɗ\ƑƇẈṀ  Main link. Argument: n (integer)

ŒṖ           Yield all partitions of n's digit list in base 10.
        Ƈ    Comb; keep only partitions for which the link to the left returns 1.
       Ƒ       Fixed; yield 1 if calling the link to the left returns its argument.
      \          Cumulatively reduce the partition by the link to the left.
     ɗ             Combine the three links to the left into a dyadic chain.
  Ḍ                  Undecimal; convert a digit list into an integer.
   ’                 Decrement the result.
    D                Decimal; convert the integer back to a digit list.

```
> 3 votes

# Answer
# Japt, 27 bytes

```
ò pÊÔpÊqÊfl²i1Uì q"l?"¹ÌèÊÉ

```

Try it online! or Check most test cases

This doesn't score well, but it uses a unique method and there might be room to golf it a lot more. It also performs well enough that all test cases other than `201200199198` avoid timing out.

Explanation:

```
ò                              #Get the range [0...input]
  pÊ                           #Add an "l" to the end
    Ô                          #Reverse it
     pÊ                        #Add an "l" to the end
       qÊ                      #Add an "l" between each number and turn to a string
         f            ¹        #Find the substrings that match this regex:
          l²                   # The string "ll"
            i1                 # With this inserted between the "l"s:
              Uì               #  All the digits of the input
                 q"l?"         #  With optional spaces between each one
                       Ì       #Get the last match
                        èÊ     #Count the number of "l"s
                          É    #Subtract 1

```
> 3 votes

# Answer
# Python 3, ~~302~~ ~~282~~ 271 bytes

-10 bytes thanks to the tip by @ElPedro.

Takes input as a string. Basically, it takes increasing larger slices of the number from the left, and sees if for that slice of the number a sequence can be formed using all the numbers.

```
R=range
I=int
L=len
def g(n,m,t=1):
 for i in R(1,L(m)+1):
  if I(m)==I(n[:i])+1:
   if i==L(n):return-~t
   return g(n[i:],n[:i],t+1)
 return 1
def f(n):
 for i in R(L(n)):
  x=n[:i]
  for j in R(1,L(x)+1):
   if (I(x)==I(n[i:i+j])+1)*I(n[i]):return g(n[i:],x)
 return 1

```

Try it online!
> 3 votes

# Answer
# Charcoal, 26 bytes

```
Ｆ⊕ＬθＦ⊕Ｌθ⊞υ⭆κ⁻Ｉ…θιλＩ﹪⌕υθ⊕Ｌθ

```

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

```
Ｆ⊕Ｌθ

```

Loop `i` from 0 to the length of the input.

```
Ｆ⊕Ｌθ

```

Loop `k` from 0 to the length of the input.

```
⊞υ⭆κ⁻Ｉ…θ⊕ιλ

```

Calculate the first `k` numbers in the descending sequence starting from the number given by the first `i` digits of the input, concatenate them, and accumulate each resulting string in the predefined empty list.

```
Ｉ﹪⌕υθ⊕Ｌθ

```

Find the position of the first matching copy of the input and reduce it modulo 1 more than the length of the input.

Example: For an input of `2019` the following strings are generated:

```
 0
 1  0
 2  0-1
 3  0-1-2
 4  0-1-2-3
 5
 6  2
 7  21
 8  210
 9  210-1
10
11  20
12  2019
13  201918
14  20191817
15
16  201
17  201200
18  201200199
19  201200199198
20
21  2019
22  20192018
23  201920182017
24  2019201820172016

```

`2019` is then found at index 12, which is reduced modulo 5 to give 2, the desired answer.
> 3 votes

# Answer
## Haskell, 87 bytes

```
maximum.map length.(0#)
a#(b:c)=[a:x|c==[]||b>0,x<-b#c,a==x!!0+1]++(10*a+b)#c
a#b=[[a]]

```

Input is a list of digits.

Try it online!

Function `#` builds a list of all possible splits by looking at both

* prepending the current number `a` to all splits returned by a recursive call with the rest of the input (`x<-b#c`), but only if the next number not zero (`b>0`) (or it's the last number in the input (`c==[]`)) and `a` is one greater than the first number of the respective previous split `x` (`a==x!!0+1`).

and

* appending the next digit `b` from the input list to the current number `a` and going on with the rest of the input (`(10*a+b)#c`)

Base case is when the input list is empty (i.e. does not pattern match `(b:c)`). The recursion starts with the current number `a` being `0` (`(0#)`), which never hits the first branch (prepending `a` to all previous splits), because it will never be greater than any number of the splits.

Take the length of each split and find the maximum (`maximum.map length`).

A variant with also 87 bytes:

```
fst.maximum.(0#)
a#(b:c)=[(r+1,a)|c==[]||b>0,(r,x)<-b#c,a==x+1]++(10*a+b)#c
a#b=[(1,a)]

```

which basically works the same way, but instead of keeping the whole split in a list, it only keeps a pair `(r,x)` of the length of the split `r` an the first number in the split `x`.
> 3 votes

# Answer
# Dyalog APL, 138 bytes

Bit of a mouthful, but it works fast for big numbers too. If you try it online, prefix the dfn by `⎕←` and provide input on the right as a list of digits.

```
{⌈/⍵((≢⊂)×1∧.=2-/10⊥¨⊂)⍨⍤1⊢1,{⍬≡1↓⍵:↑⍬1⋄0=⊃⍵:0,∇1↓⍵⋄↑,0 1∘.,⊂⍤1∇1↓⍵}1↓⍵}

```

### Explanation

First, the inner dfn on the right which recursively constructs a list of possible ways to partition (with ) the list of digits. For example `1 0 1 0 ⊂ 2 0 1 9` returns the nested vector `(2 0)(1 9)`.

```
{
   ⍬≡1↓⍵: ↑⍬1       ⍝ Edge case: If ⍵ is singleton list, return the column matrix (0 1)
   0=⊃⍵: 0,∇1↓⍵     ⍝ If head of ⍵ is 0, return 0 catenated to this dfn called on tail ⍵
   ↑,0 1∘.,⊂⍤1∇1↓⍵  ⍝ Finds 1 cat recursive call on tail ⍵ and 0 cat recursive call on ⍵.
}                    ⍝ Makes a matrix with a row for each possibility.

```

We use `1,` to add a column of 1s at the start and end up with a matrix of valid partitions for ⍵.

Now the function train on the left in parens. Due to  the left argument to the train is the row of the partitions matrix and the right argument is the user input. The train is a pile of forks with an atop as the far left tine.

```
((≢⊂)×1∧.=2-/10⊥¨⊂)⍨     ⍝ ⍨ swaps left and right arguments of the train.
                  ⊂       ⍝ Partition ⍵ according to ⍺.
             10⊥¨         ⍝ Decode each partition (turns strings of digits into numbers)
          2-/             ⍝ Difference between adjacent cells
      1∧.=                ⍝ All equal 1?
   ⊂                      ⍝ Partition ⍵ according to ⍺ again
  ≢                       ⍝ Number of cells (ie number of partitions)
     ×                    ⍝ Multiply.

```

If the partition creates a sequence of descending numbers, the train returns the length of the sequence. Otherwise zero.

`⍤1⊢` applies the function train between the user input and each row of the partitions matrix, returning a value for each row of the matrix.  is necessary to disambiguate between operand to  and argument to the derived function of .

`⌈/` finds the maximum.

Could find a shorter algorithm but I wanted to try this way which is the most direct and declarative I could think of.
> 3 votes

# Answer
## Haskell, 65 bytes

```
f i=[y|x<-[0..],y<-[1..length i],i==(show=<<[x+y-1,x+y-2..x])]!!0

```

Input is a string.

Try it online!

Completely different to my other answer. A simple brute force that tries all lists of consecutive descending numbers until it finds one that equals the input list.

If we limit the input number to 64-bit integers, we can save 6 bytes by looping `y` through `[1..19]`, because the largest 64-bit integer has 19 digits and there's no need to test lists with more elements.

### Haskell, 59 bytes

```
f i=[y|x<-[0..],y<-[1..19],i==(show=<<[x+y-1,x+y-2..x])]!!0

```

Try it online!
> 2 votes

# Answer
# Python 2, 95 bytes

```
lambda n:max(j-i for j in range(n+1)for i in range(-1,j)if''.join(map(str,range(j,i,-1)))==`n`)

```

Another slow, brute-force solution.

Try it online!
> 2 votes

# Answer
# TSQL, 169 bytes

Note: this can only be executed when the input can be converted to an integer.

Recursive sql used for looping.

Golfed:

```
DECLARE @ varchar(max) = '1211109876';

WITH C as(SELECT left(@,row_number()over(order by 1/0))+0t,@+null z,0i
FROM spt_values UNION ALL
SELECT t-1,concat(z,t),i+1FROM C WHERE i<9)SELECT
max(i)FROM C WHERE z=@

```

Ungolfed:

```
DECLARE @ varchar(max) = '1211109876';

WITH C as
(
  SELECT
    left(@,row_number()over(order by 1/0))+0t,
    @+null z,
    0i
  FROM
    spt_values
  UNION ALL
  SELECT
    t-1,
    concat(z,t),
    i+1
  FROM C
  WHERE i<9
)
SELECT max(i)
FROM C
WHERE z=@

```

**Try it out**
> 1 votes

# Answer
# , 101 bytes

```
function(a,N=nchar(a)){for(x in 1:N)F=max(F,which(Reduce(paste0,seq(substr(a,1,x),,-1,N),a=T)==a));F}

```

Try it online!

More than 2 weeks have passed without any R answer, so I decided to post my own :)

The code is pretty fast since it uses a "limited" brute force approach

### Unrolled code and explanation :

```
function(a){                  # get string a as input (e.g. "2019")

  N = nchar(a)                # set N = length of a (e.g. 4)
  Y = 0                       # initialize Y = 0 (in the actual code we abuse F)

  for(x in 1:N){              # for x in 1 ... N

    S = substr(a,1,x)         # get the first x characters of a (e.g. "20" for x=2)

    Q = seq(S,,-1,N)          # create a decreasing sequence (step = -1)
                              # of length N starting from S converted into integer
                              # (e.g. Q = c(20,19,18,17) for x=2)

    R = Reduce(paste0,Q,a=T)  # concatenate all the increasing sub-sequences of Q
                              # (e.g. R = c("20","2019","201918","20191817") for x=2)

    I = which(R == a)         # Get the index where R == a, if none return empty vector
                              # (e.g. I = 2 for x=2)

    Y = max(Y,I)              # store the maximum index found into Y
  }
  return(Y)                   # return Y
}

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Random Golf of the Day #1: Shuffle an Array
# About the Series

I will be running a little series of code-golf challenges revolving around the theme of randomness. This will basically be a 9-Hole Golf Course, but spread out over several questions. You may participate in any challenge individually as if it was a normal question.

However, I will maintain a leaderboard across all challenges. The series will run over 9 challenges (for now), one posted every few days. Every user who participates in *all 9 challenges* is eligible for winning the entire series. Their overall score is the sum of their shortest submissions on each challenge (so if you answer a challenge twice, only the better answer one is counted towards the score). If anyone holds the top spot on this overall leaderboard for **28 days** I will award them a bounty of **500 rep**.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

# Hole 1: Shuffle an Array

The first task is pretty simple: given a non-empty array of integers, shuffle it randomly. There are a few rules though:

* **Every possible permutation must be returned with the same probability** (so the shuffle should have a uniform distribution). You can check if your algorithm is uniform/unbiased by implementing it in JavaScript on **Will it Shuffle**, which will produce a matrix of the biases - the result should look as uniform as their built-ins *Fisher-Yates* or *sort (random order)*.
* You must not use any built-in or 3rd-party method to shuffle the array or generate a random permutation (or enumerate all permutations). In particular, **the only built-in random function you may use is getting a single random number at a time**. You *may* assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval (in a mathematical sense - you may ignore details of floating-point representation here). If your language lets you obtain a list of *m* random numbers at once, you may use this facility, provided the *m* numbers are independent of each other, and you count it as O(m).
* Your implementation must not exceed a **time complexity of O(N)**, where **N** is the size of the array to be shuffled. For instance, you cannot "sort by random numbers".
* You may either shuffle the array in place, or create a new array (in which case the old array may be modified however you like).

You may write a full program or a function and take input via STDIN, command-line argument, function argument or prompt and produce output via return value or by printing to STDOUT (or closest alternative). If you write a function that shuffles the array in place, you don't need to return it of course (provided your language lets you access the modified array after the function returns).

Input and output may be in any convenient list or string format, but must support arbitrary integers in the range **-231 ≤ x \< 231**. In principle, your code should work for arrays up to length **231**, although this doesn't necessarily have to fit in your memory or complete within a reasonable amount of time. (I just don't want to see arbitrary size limits to hardcode loops or something.)

This is code golf, so the shortest submission (in bytes) wins.

# Leaderboard

The following snippet will generate a leaderboard across all challenges of the series.

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

*(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)*

```
/* Configuration */

var QUESTION_IDs = [45302, 45447, 46991, 49394, 51222, 66319, 89621, 120472]; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!.FjwQBrX2KXuFkv6p2lChi_RjzM19";

/* App */

var answers = [], page = 1, currentQ = -1;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_IDs.join(";") + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function getAnswers() {
  $.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>((?!>).)*<\/s>|((?!>).)+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^\n,]+)(?=,)/;//

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  if (!pass) console.log(a);
  return pass;
}

function getAuthorName(a) {
  return a.owner.display_name;
}

function getAuthorId(a) {
  return a.owner.user_id;
}

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var users = {};
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    var question = QUESTION_IDs.indexOf(a.question_id);
    var size = parseInt((headline.match(SIZE_REG)||[0])[0]);
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    var userId = getAuthorId(a);
    if (!users[userId]) users[userId] = {name: user, nAnswer: 0, answers: []};
    if (!users[userId].answers[question]) {
      users[userId].answers[question] = {size: Infinity};
      users[userId].nAnswer++;
    }
    if (users[userId].answers[question].size > size) {
      users[userId].answers[question] = {size: size, link: a.share_link}
    }
  });

  var sortedUsers = [];
  for (var userId in users)
    if (users.hasOwnProperty(userId)) {
      var user = users[userId];
      user.score = 0;
      user.completedAll = true;
      for (var i = 0; i < QUESTION_IDs.length; ++i) {
        if (user.answers[i])
          user.score += user.answers[i].size;
        else
          user.completedAll = false;
      }
      sortedUsers.push(user);
    }

  sortedUsers.sort(function (a, b) {
    if (a.nAnswer > b.nAnswer) return -1;
    if (b.nAnswer > a.nAnswer) return 1;
    return a.score - b.score;
  });

  var place = 1;
  for (var i = 0; i < sortedUsers.length; ++i) {
    var user = sortedUsers[i];
    var row = '<tr><td>'+ place++ +'.</td><td>'+user.name+'</td>';
    for (var j = 0; j < QUESTION_IDs.length; ++j) {
      var answer = user.answers[j];
      if (answer)
        row += '<td><a href="'+answer.link+'">'+answer.size+'</a></td>';
      else
        row += '<td class="missing"></td>';
    }
    row += '<td></td>';
    if (user.completedAll)
      row += '<td class="total">'+user.score+'</td>';
    else
      row += '<td class="total missing">'+user.score+'</td>';
    row += '</tr>';
    $("#users").append(row);
  }
}
```

```
body { text-align: left !important}

#leaderboard {
  width: 500px;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

td.total {
  font-weight: bold;
  text-align: right;
}

td.missing {
  background: #bbbbbb;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="leaderboard">
  <h2>Leaderboard</h2>
  <p>
    Missing scores are shown as grey cells. A grey total indicates that the user has not participated in all challenges and is not eligible for the overall victory yet.
  </p>
  <table class="_user-list">
    <thead>
      <tr><td></td><td>User</td>
        <td><a href="https://codegolf.stackexchange.com/q/45302/8478">#1</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/45447/8478">#2</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/46991/8478">#3</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/49394/8478">#4</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/51222/8478">#5</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/66319/8478">#6</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/89621/8478">#7</a></td>
        <td><a href="https://codegolf.stackexchange.com/q/120472/8478">#8</a></td>
        <td></td><td>Total</td>
      </tr>
    </thead>
    <tbody id="users">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
> 21 votes
# Dyalog APL, ~~25~~ 24 bytes

First for the 25-character solution: `i{⊃a[⍺⍵]←a[⍵⍺]}¨?i←⌽⍳⍴a←⎕`

```
                      a←⎕ ⍝ evaluated input, assign to "a"
                     ⍴a   ⍝ length
                    ⍳⍴a   ⍝ 1 2 .. length
                   ⌽⍳⍴a   ⍝ length .. 2 1
                 i←       ⍝ assign to "i"
                ?i        ⍝ random choices: (1..length)(1..length-1)..(1 2)(1)
i{            }¨?i        ⍝ for each index ⍺ and corresponding random choice ⍵
   a[⍺⍵]←a[⍵⍺]            ⍝ swap a[⍺] and a[⍵]
        ←                 ⍝ in Dyalog, assignment returns its right-hand side
  ⊃                       ⍝ first element, i.e. a[⍵]
                          ⍝ the result from {} is an array of all those a[⍵]

```

After some equivalence transformations on the above:

```
i {}¨ ?i  ←→  i {}¨∘? i   ⍝ because A f∘g B ←→ A f g B
          ←→  {}¨∘?⍨ i    ⍝ because f⍨ B ←→ B f B

```

we can get rid of the assignment `i←` and save a character:

`{⊃a[⍺⍵]←a[⍵⍺]}¨∘?⍨⌽⍳⍴a←⎕`

# Answer
> 12 votes
# 80386 machine code, 44 24 bytes

Hexdump of the code:

```
60 8b fa 0f c7 f0 33 d2 f7 f1 49 8b 04 8f 87 04
97 89 04 8f 75 ed 61 c3

```

Thanks to FUZxxl, who suggested using the `rdrand` instruction.

Here is the source code (can be compiled by Visual Studio):

```
__declspec(naked) void __fastcall shuffle(unsigned size, int array[])
{
    // fastcall convention:
    // ecx = size
    // edx = array
    _asm
    {
        pushad;             // save registers
        mov edi, edx;       // edi now points to the array

    myloop:
        rdrand eax;         // get a random number
        xor edx, edx;
        div ecx;            // edx = random index in the array

        dec ecx;            // count down
        mov eax, [edi + 4 * ecx];   // swap elements
        xchg eax, [edi + 4 * edx];  // swap elements
        mov [edi + 4 * ecx], eax;   // swap elements
        jnz myloop;

        popad;              // restore registers
        ret;
    }
}

```

Yet another Fisher-Yates implementation. Most of the golfing was achieved by passing parameters in registers.

# Answer
> 9 votes
# Java, 88 ~~101~~

A basic Fisher-Yates shuffle does the trick. I get the feeling it'll be used pretty commonly here, since it's quick and easy to implement. There's some loop/assignment cramming here, but there's honestly not *too* much to golf; it's just short by nature.

```
void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}

```

With some line breaks:

```
void t(int[]s){
    for(int i=s.length,t,x;
        i>0;
        t=s[x*=Math.random()],
        s[x]=s[i],
        s[i]=t
    )
        x=i--;
}

```

This shuffles in place, modifying the original array `s[]`. Test program:

```
public class Shuffle {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        new Shuffle().t(a);
        for(int b:a)
            System.out.print(b+" ");
    }
    void t(int[]s){for(int i=s.length,t,x;i>0;t=s[x*=Math.random()],s[x]=s[i],s[i]=t)x=i--;}
}

```

# Answer
> 8 votes
# Python 2, 86 bytes

```
from random import*
def S(L):i=len(L);exec"i-=1;j=randint(0,i);L[i],L[j]=L[j],L[i];"*i

```

This is a function which shuffles the array in place without returning it, using a straightforward implementation of the Fisher-Yates shuffle. Getting random numbers from Python is *expensive*...

Thanks to @xnor and @colevk for tips.

# Answer
> 8 votes
## J, ~~45~~ 44 characters

This was a tricky one.

```
<@({.,?@#@}.({,<^:3@[{])}.)&>/@(<"0@i.@#,<)

```

Here is an explanation:

1. `# y`: The *tally* of `y`, that is, the number of elements in `y`.
2. `?@# y`: A random number uniformly distributed over the range from `1` to `(#y)-1`.
3. `x { y`: The item *from* `y` at index `x`.
4. `(<<<x) { y`: All items except the item at index `x` in `y`.
5. `x , y`: `y` *appended* to `x`.
6. `x ({ , <^:3@[ { ]) y`: The item at index `x` in `y`, then all the other items.
7. `(?@# ({ , <^:3@[ { ]) ]) y` A random it from `y`, then all the other items.
8. `x {. y`: The first `x` items *taken* from `y`.
9. `x }. y`: The first `x` items *dropped* from `y`.
10. `x ({. , }.) y`: The first `x` items *taken* from `y`, then the first `x` items *dropped* from `y`
11. `x ({. , (?@# ({ , <^:3@[ { ]) ])@}.) y`: The first `x` items *taken* from `y`, then the first `x` items from `y` processed as in number 7.
12. `x ({. , ?@#@}. ({ , <^:3@[ { ]) }.) y`: The same thing with the *drop* pulled in to save one character.
13. `u/ y`: `u` *inserted* between the items of `y`.
14. `< y`: `y` *boxed*.
15. `<"0 y`: Each item of `y` *boxed*.
16. `i. y`: *integers* from `0` to `y - 1`.
17. `i.@# y`: *integers* from `0` to `(#y) - 1`.
18. `(<"0@i.@# , <) y`: Integers from `0` to `(#y) - 1` each *boxed* and then `y` in a single box. This is needed because arrays in J are uniform. A box hides the shape of its content.
19. `x u&v y`: like `(v x) u (v y)`.
20. `> y`: `y` *opened*, that is, without its box.
21. `x ({. , ?@#@}. ({ , <^:3@[ { ]) }.)&> y` the phrase from number 12 applied to its unboxed arguments.
22. `({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/ y` the phrase from number 21 *inserted* between items of `y`.
23. `({. , ?@#@}. ({ , <^:3@[ { ]) }.)&>/@(<"0@i.@# , <) y` the phrase from number 22 applied to the the result of the phrase from number 18, or, a uniform permutation of the items of `y`.

# Answer
> 5 votes
# Pyth, 25 bytes

Test it here.

Yet another Fisher-Yates implementation. Is essentially the same as @Sp3000 python solution, just in pyth.

```
FNrlQ1KONJ@QN XXQN@QKKJ)Q

```

Thanks to @Jakube for the swapping trick

```
<implicit>    Q=input()
FNrlQ1        For N in len(Q) to 1, only goes len Q-1 because how range implemented in pyth
 KON          K = random int 0-N
 J@QN         J=Q[N]
 <space>      Suppress print
 XXQN@QKKJ    Swap K and J
)             End for
Q             Print Q

```

# Answer
> 4 votes
# Perl, ~~68~~ ~~56~~ 44

Like many other solutions, this uses the Fisher-Yates algorithm.

Using nutki's comment, 12 characters are saved by using `$_` instead of `$i` and performing the operations in the array indices.

44:

```
sub f{@_[$_,$j]=@_[$j=rand$_,--$_]for 1..@_}

```

56:

```
sub f{$i=@_;$j=int(rand$i),@_[$i,$j]=@_[$j,$i]while$i--}

```

This is my first codegolf.

# Answer
> 3 votes
## Octave, ~~88~~ 77 bytes

```
function s=r(s)for(i=length(s):-1:1)t=s(x=randi(i));s(x)=s(i);s(i)=t;end;end

```

Yet another Fisher-Yates implementation... Should be fairly straightforward if I add the usual line returns and spacing:

```
function s=r(s)
  for(i=length(s):-1:1) # Counting down from i to 1
    t=s(x=randi(i));    # randi is builtin number generator for an int from 0 to i
    s(x)=s(i);
    s(i)=t;
  end
end

```

~~The "end" keywords really kill the golf score here, unfortunately.~~ Hey, I can use "end" instead of "endfor" and "endfunction"!

# Answer
> 3 votes
# C, ~~63~~ ~~61~~ 60 bytes

```
i,t;s(a,m)int*a;{for(;m;a[m]=t)t=a[i=rand()%m--],a[i]=a[m];}

```

Just a straight implementation of Fischer-Yates that sorts the given array in place. Compiles and links perfectly fine with the visual studio compiler (vs2013, haven't tested the other versions) and the Intel Compiler. Nice looking function signature is `s(int array[], int length)`. I'm legitimately impressed I beat Python and Ruby.

This does assume `srand()` is called and rand() is implemented properly, but I believe this rule allows for that:

```
You may assume that any built-in random number method runs in O(1) and is perfectly uniform over the requested interval

```

Nicely formatted version:

```
index, temp;
shuffle(array, length) int* array;  {
    for(;length; array[index] = temp)
        index = rand() % length--,
        temp = array[length],
        array[length] = array[index];
}

```

# Answer
> 2 votes
# Ruby, 57 bytes

```
->a{a.size.times{|i|j=rand(i+1);a[i],a[j]=a[j],a[i]};p a}

```

### Input (as lambda function):

```
f.([1,2,3,4,5])

```

### Output:

```
[2, 1, 4, 3, 5]

```

# Answer
> 2 votes
# Java 8, 77

```
(x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};

```

It's a lambda taking `int[]` and returning void. My first attempt seemed not very interesting, so I decided to have it exit by throwing an exception.

Test program:

```
interface shuff {
    void shuff(int[] x);
}
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        shuff s = (x)->{for(int i=x.length,j,t;;t=x[j*=Math.random()],x[j]=x[i],x[i]=t)j=i--;};
        int[] x = {3, 9, 2, 93, 32, 39, 4, 5, 5, 5, 6, 0};
        try {
            s.shuff(x);
        } catch(ArrayIndexOutOfBoundsException _) {}
        for(int a:x) System.out.println(a);
    }
}

```

# Answer
> 2 votes
# Golflua, 37

How to run Golflua?

```
~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$

```

The input is provided as a table in the variable X. The table is shuffled in place.

Example usage:

```
> X={0,-45,8,11,2}
> ~@i=1,#X`r=M.r(i)X[i],X[r]=X[r],X[i]$
> w(T.u(X))
-45 0 8 11 2

```

# Answer
> 2 votes
# R, 79 bytes

```
f=function(x){n=length(x);for(i in 1:n){j=sample(i:n,1);x[c(i,j)]=x[c(j,i)]};x}

```

This is a straightforward implementation of the Fisher-Yates shuffle. The R function `sample` draws a simple random sample of a given size from a given vector with equal probability. Here we're drawing a random sample of size 1 at each iteration from the integers `i`, ..., `n`. As stated in the question, this can be assumed to be O(1), so in all this implementation should be O(N).

# Answer
> 2 votes
# Mathematica, ~~82 90 83~~ 93 bytes

Note: This variation the Fisher-Yates shuffle is actually Martin Büttner's solution, with some code paring by alephalpha. `s` is the input array. Nothing fancy-smancy, but sometimes the simple things are the most elusive.

```
f@s_:=(a=s;m=Length@a;Do[t=a[[r=RandomInteger@{1,m-1}]];a[[r]]=a[[m]]; a[[m]]=t,{n,1,m-1}];a)

```

# Answer
> 2 votes
# Matlab, 67

Also implementing Fisher-Yates.

```
a=input('');n=numel(a);for i=1:n;k=randi(i);a([i,k])=a([k,i]);end;a

```

I thought it was too bad I could not use Matlab's `randperm` function. But after some fiddling around, I thought I may look at the source of `randperm` to see how it is done, and I was astonished to see that there was just one line: `[~,p] = sort(rand(1,n))` =)

# Answer
> 2 votes
# Perl, 44

```
sub f{($_[$x],$_)=($_,$_[$x=rand++$i])for@_}

```

Another perl in 44 characters. Example use:

```
@x=(1..9);f(@x);print@x

```

# Answer
> 2 votes
# TI-BASIC, 46 bytes

```
For(X,dim(L1),2,-1:randInt(1,X→Y:L1(X→Z:L1(Y→L1(X:Z→L1(Y:L1

1   111   2  1111112       1111112 111112 1112 111112 1112

```

Source for byte count

# Answer
> 2 votes
# K, 31 chars

```
f:{{l[i:x,1?x]:l@|i}'|!#l::x;l}

```

Not quite as short as the one I put up before (which got disqualified)...oh well.

It's a basic Fisher-Yates shuffle. This was built with lots of help from the Kona mailing list.

# Answer
> 2 votes
# JavaScript (ES6), 66

This function shuffles the array in place. It also returns a byproduct array that is NOT the shuffled output and must not be considered.

```
F=a=>a.map((v,i)=>a[a[i]=a[j=0|i+Math.random()*(a.length-i)],j]=v)

```

# Answer
> 2 votes
# MATL, 16 bytes

```
XH`HnYr&)XHxvHHn

```

Try it online!

Fisher-Yates in MATL. Almost a third of this program is devoted to the letter `H`, which corresponds to the clipboard function in MATL.

Basically, `H` stores the unused items from the input, while the stack keeps track of the shuffled list.

# Answer
> 2 votes
# Japt, 12

```
rÈiMqZÄ Y}[]

```

Try it!

-10 (about half ;) thanks to @Shaggy!

I have been wanting to try out a golfing language, and the Japt interpreter had good documentation and a way to try things out in the browser.

Below is the strategy I took:

* Reduce input seeding with an empty array
* At each step, find a random slot to insert the current element

# Answer
> 1 votes
# STATA, 161

```
di _r(s)
set ob wordcount($s)
token $s
g a=0
foreach x in $s{
gl j=floor(runiform()*_n)+1
replace a=`$j' if word($s,_n)=`x'
replace a=`x' if word($s,_n)=`$j'
}
l

```

Expects input as space separated numbers. I can remove the headers and observation numbers from the output if you would like, but otherwise this is shorter.

# Answer
> 1 votes
# CJam - 30

```
q~_,,W%{_I=I)mr:J2$=@I@tJ@t}fI

```

Try it at http://cjam.aditsu.net/

Example input: `[10 20 30 40 50]`
Example output: `3020401050` (add a `p` at the end of the code for pretty printing)

~~If the code is allowed to take the input from the stack (like a function), then the first 2 characters can be removed, reducing the size to 28.~~

**Explanation:**

The code is longer than I hoped, due to the lack of a "swap" operator for arrays
(to be implemented later :p)

```
q~            read and evaluate the input (let's call the array "A")
_,,           make an array [0 1 2 ... N-1] where N is the size of A
W%            reverse the array, obtaining [N-1 ... 2 1 0]
{…}fI         for I in this array
    _I=       push A[I]
    I)mr:J    push a random number from 0 to I (inclusive) and store it in J
              stack: A, A[I], J
    2$=       get A[J]
    @I@t      set A[I] = A[J]
              stack: former A[I], A
    J@t       set A[J] = former A[I]

```

# Answer
> 1 votes
## SQF, 91 bytes

```
params["i"];{n=floor random count i;i set[_forEachIndex,i select n];i set[n,_x]}forEach i;i

```

# Answer
> 1 votes
# Pyth, 27 bytes

Test it here

```
FkQJOhlYaY?@YtJJkIJ XYtJk;Y

```

This is an implementation of the incremental Fisher-Yates shuffle, mentioned second here.

# Answer
> 1 votes
## Javascript ES6, 69

```
a=>{m=a.length;while(m)[a[m],a[i]]=[a[i=~~(Math.random()*m--)],a[m]]}

```

It's Fisher–Yates.

PS: Can be tested in Firefox

# Answer
> 1 votes
# Haskell, 170

```
import System.Random
import Data.Array.IO
s a=do(_,n)<-getBounds a;sequence$map(\i->do j<-randomRIO(i,n);p<-a%i;q<-a%j;writeArray a j p;return q)[1..n]where(%)=readArray

```

Another Fisher-Yates solution inspired by the algorithm at https://wiki.haskell.org/Random\_shuffle.

`s` is a function which has signature: `IOArray Int a -> IO [a]`

# Answer
> 1 votes
# JavaScript (ES 6), 61

```
S=a=>(a.map((c,i)=>(a[i]=a[j=Math.random()*++i|0],a[j]=c)),a)

```

You can test it here by just adding a line that says `shuffle = S` (Firefox only).

# Answer
> 1 votes
# Java, 93 bytes

```
a->{for(int b=0,c,d=0,e=a.length;b<e;c=a[b],a[b]=a[d],a[d]=c,b++,d=b)d+=Math.random()*(e-b);}

```

Example usage: http://ideone.com/RqSMnZ

# Answer
> 1 votes
# Perl, 41 bytes

```
sub f{push@b,splice@_,rand@_,1while@_;@b}

```

Try it online!

# Answer
> 0 votes
# Jolf, 46 bytes

*Invalid, since language postdates question. Is otherwise a perfectly valid answer.* Try it *ici*!

```
v'nlKW«n)v'HC*mrhntv'S.Kn$K[n]=K[H];K[H]=S$}K

```

## Explanation

```
v'nlKW«n)v'HC*mrhntv'S.Kn$K[n]=K[H];K[H]=S$}K
                                              implicit: K = input array
v'n                                           set n to
   lK                                           the length of K
     W«n)                                     while(--n){
         v'H                                    set H to
            C     t                               the integer part of
             *mr                                  Math.random() times
                hn                                  n+1
                   v'S                          set S to
                      .Kn                         the nth member of K
                         $K[n]=K[H];K[H]=S$     eval as javascript (perform swap)
                                           }  }
                                            K K
                                              implicit: print K

```

This runs in O(n) time, I believe, as `n` is strictly decreasing.

I used this as the basis for the code

# Answer
> 0 votes
# Julia 0.6, 56 bytes

```
!a=for i=length(a):-1:1;j=rand(1:i);a[[i,j]]=a[[j,i]]end

```

Try it online!

Fisher-Yates.

`a[[i,j]]=a[[j,i]]` is slightly shorter than `a[i],a[j]=a[j],a[i]`.

`rand(1:i)` samples from the range `1:i`.

# Answer
> 0 votes
# SmileBASIC, 56 bytes

Fisher-Yates algorithm of course.

```
DEF S A
FOR I=1-LEN(A)TO-1SWAP A[-I],A[RND(1-I)]NEXT
END

```

Downwards FOR loops are expensive (`STEP -1`), so instead you can just negate the start/end values, which only adds 1 extra character. This is the code if FOR implicitly went backwards when the end value is lower than the start:

```
DEF S A
FOR I=LEN(A)-1TO 1SWAP A[I],A[RND(I+1)]NEXT '1 character less
END

```

# Answer
> 0 votes
# PowerShell, 39 27 bytes

-4 bytes thanks to @mazzy

```
$args-split','|sort{random}

```

Accepts input as commandline arguments, and outputs as an array.

# Answer
> -1 votes
**VBA/Basic, 96**

Someday I will find a good challenge for vba or basic, but not today

Fisher-Yates

```
Sub s(o(), n)
For i = 0 To n
r = Int(Rnd() * (n + 1))
x = o(r)
o(r) = o(i)
o(i) = x
Next
End Sub

```

---
Tags: code-golf, random, array, permutations
---


title: Hilbertize an image

text:
# Question
Title: Hilbertize an image
For a computer vision app I want to do a mapping of an image, in such a way that every pixel fit hilbert curve, instead of conventional layout. So task could be as follows:

---

## Task description

Given square 2D image `A` with side `2^^N`, (`N>0`), with common Z-order, or row-major representation of pixels in RAM. I need to run a hilbert curve through this image (Like a digital camera, where photodiodes are soldered in a hilbert curve and numbered and accessed in a 1-d ordered manner). Then pixels along this curve just layed down as a regular scanline in image B. So now any consequent samples in output array B now should represent spatially close points in input array A.

---

## Example for `N=2`

```
Input: array A (imagination of 2D image)
0 1 E F
3 2 D C
4 7 8 B
5 6 9 A

Input: array A (1D actual layout in memory)
0 1 E F 3 2 D C 4 7 8 B 5 6 9 A

Output: array B (answer)
0 1 2 3 4 5 6 7 8 9 A B C D E F

```

Note, that values inside arrays are "values". In this example, for array B accidentally they became same as indices. So basically I want index mapping function B\[i\]=A\[?\], e.g B = A\[E\]. Hope code golfing helps.

---

## Example for N=9:

Taken popular 512\*512 test image. Each pixel was threated as 32bit integer, in RGBA format and algorithm proceeded:

Input:

Output:

---

## Reverse question:

Here is reversed-task question on codegolf.

In terms of that question, I want to do opposite transform: "I want to *Reravel* image A, then *Unravel* to image B". In terms of examples of that question: I want to take *photo the lion* on the camera with hilbert-curved-sensor (look *Output* array for lion photo) and get that long "scanline of spatially close pixels" (Input for lion photo, in that question)

---

## Reference implementation:

If i take `d2xy()` function from LGPL sources found here I may write a following program, which works, but maybe not its best way:

```
#include "hilbert_curve.h"
int main(){
  int *A,*B,i,x,y;
  for(i=0;i<(1<<(N<<1));++i){
    d2xy(N,i,&x,&y);
    B[i]=A[y*(1<<N)+x];
  }
}

```

---

## Resources:

# Answer
> 1 votes
# Jelly, 38 bytes

```
U1¦U;$;;UN$
Ll2’ð⁽Æ¬b3’s2Ç⁸¡⁵DW¤;+\Ḋœị

```

A monadic Link accepting a square matrix of side \\$2^n\\$, \\$n\\$ a positive integer which yields an array of the inputs elements in Hilbert curve order.

**Try it online!**

### How?

First we create `[row, column]` index deltas describing the U shape with an initial right move (i.e into the \\$n=1\\$ matrix's top-left corner from the left) - that is `[[0, 1], [1, 0], [0, 1], [-1, 0]]`.

Then we repeatedly perform a transform keeping the current list of deltas to describe the bottom-right quarter of the next and adding the other three quarters as copies with reversed deltas (swapping row changes with column ones where necessary and negating directions of the new top-right quarter).

Finally we prepend a starting index of `[1,0]` (to the left of the top-left of our \[1-indexed\] matrix), cumulatively reduce by addition to get the indexes, discard the `[1, 0]` and index into the input.

### How?

```
U1¦U;$;;UN$ - Link 1, transform deltas to next size: list of current deltas
U1¦         - reverse the first delta (makes bottom-left)
   U;$      - reverse each of those and concatenate with that (adds top-left)
      ;     - concatenate with the input (adds bottom-right)
        UN$ - reverse each of the input deltas and negate (makes top-right)
       ;    - concatenate (adds top-right)

Ll2’ð⁽Æ¬b3’s2Ç⁸¡⁵DW¤;+\Ḋœị - Main Link: square matrix (of side 2^n), M
L                          - length of M
 l2                        - log base 2 (=n)
   ’                       - decrement
    ð                      - start a new dyadic chain (i.e. f(n-1, M))
     ⁽Æ¬                   - compressed literal = 4258
        b3                 - to base 3 = [1,2,2,1,1,2,0,1]
          ’                - decrement = [0,1,1,0,0,1,-1,0]
           s2              - split into twos = [[0,1],[1,0],[0,1],[-1,0]]
               ¡           - apply repeatedly...
              ⁸            - ...number of times: chain's left argument, n-1
             Ç             - ...what?: last Link as a monad
                           -           - gets all deltas
                   ¤       - nilad followed by link(s) as a nilad:
                ⁵          -   literal ten
                 D         -   to decimal digits = [1,0]
                  W        -   wrap = [[1,0]]
                    ;      - concatenate with the deltas
                     +\    - cumulative reduce using addition (N.B. Ä wont work here)
                       Ḋ   - dequeue (drop the [1, 0] leading index)
                        œị - multi-dimensional index into M

```

---
Tags: code-golf, array, geometry, image-processing, fractal
---


title: Dig a border trench

text:
# Question
Title: Dig a border trench
**Background:** Too many illegal immigrants from Blandia are crossing the border to Astan. The emperor of Astan has tasked you with digging a trench to keep them out, and Blandia must pay for the expenses. Since all typists have been furloughed until the trench is arranged, your code must be as short as possible.*

**Task:** Given a 2D map of the border between Astan and Blandia, make the Blands pay (with land) for a border trench.

**For example:** With Astanian cells marked `A`, Blandic cells marked `B` and trench cells marked `+` (the map frames are only for clarity):

```
┌──────────┐ ┌──────────┐
│AAAAAAAAAA│ │AAAAAAAAAA│
│ABAAAAAABA│ │A+AAAAAA+A│
│ABBBAABABA│ │A+++AA+A+A│
│ABBBAABABA│ │A+B+AA+A+A│
│ABBBBABABA│→│A+B++A+A+A│
│ABBBBABBBB│ │A+BB+A++++│
│ABBBBABBBB│ │A+BB+A+BBB│
│ABBBBBBBBB│ │A+BB+++BBB│
│BBBBBBBBBB│ │++BBBBBBBB│
└──────────┘ └──────────┘

```

**Details:** The map will have at least three rows and three columns. The top row will be entirely Astanian and the bottom row will be entirely Blandic.
You may use any three values to represent Astanian territory, Blandic territory, and border trench, as long as input and output are consistent.

**Automaton formulation:** A Blandic cell with at least one Astanian cell in its Moore neighbourhood becomes a border trench cell.

# Test cases

```
[
  "AAAAAAAAAA",
  "ABAAAAAABA",
  "ABBBAABABA",
  "ABBBAABABA",
  "ABBBBABABA",
  "ABBBBABBBB",
  "ABBBBABBBB",
  "ABBBBBBBBB",
  "BBBBBBBBBB"
]

```

becomes:

```
[
  "AAAAAAAAAA",
  "A+AAAAAA+A",
  "A+++AA+A+A",
  "A+B+AA+A+A",
  "A+B++A+A+A",
  "A+BB+A++++",
  "A+BB+A+BBB",
  "A+BB+++BBB",
  "++BBBBBBBB"
]

```

---

```
[
  "AAA",
  "AAA",
  "BBB"
]

```

becomes:

```
[
  "AAA",
  "AAA",
  "+++"
]

```

---

```
[
  "AAAAAAAAAA",
  "AAAABBBAAA",
  "AAAABBBAAA",
  "AAAABBBAAA",
  "AAAAAAAAAA",
  "BBBBBBABBB",
  "BBBBBBAABB",
  "BBBAAAAABB",
  "BBBBBBBBBB"
]

```

becomes:

```
[
  "AAAAAAAAAA",
  "AAAA+++AAA",
  "AAAA+B+AAA",
  "AAAA+++AAA",
  "AAAAAAAAAA",
  "++++++A+++",
  "BB++++AA+B",
  "BB+AAAAA+B",
  "BB+++++++B"
]

```

---

* DISCLAIMER: ANY RESEMBLANCE TO ACTUAL GEOPOLITICS IS PURELY COINCIDENTAL!

# Answer
# Wolfram Language (Mathematica), 15 bytes

```
2#-#~Erosion~1&

```

Try it online!

Or (39 bytes):

```
MorphologicalPerimeter[#,Padding->1]+#&

```

Try it online!

What else would we expect from Mathematica? Characters used are `{Astan -> 0, Blandia -> 1, Trench -> 2}`.
> 30 votes

# Answer
# MATL, ~~11~~ 8 bytes

*Inspired by @flawr's Octave answer and @lirtosiast's Mathematica answer.*

```
EG9&3ZI-

```

The input is a matrix with Astan represented by `0` and Blandia by `1`. Trench is represented in the output by `2`.

Try it online!

### How it works

```
E       % Implicit input. Multiply by 2, element-wise
G       % Push input again
9       % Push 9
&3ZI    % Erode with neighbourhood of 9 elements (that is, 3×3)
-       % Subtract, element-wise. Implicit display

```
> 9 votes

# Answer
# JavaScript (ES7),  ~~84~~  82 bytes

*Saved 2 bytes thanks to @Shaggy*

Takes input as a matrix of integers, with \\$3\\$ for Astan and \\$0\\$ for Blandia. Returns a matrix with the additional value \\$1\\$ for the trench.

```
a=>(g=x=>a.map(t=(r,Y)=>r.map((v,X)=>1/x?t|=(x-X)**2+(y-Y)**2<v:v||g(X,y=Y)|t)))()

```

Try it online!

### Commented

```
a => (                      // a[] = input matrix
  g = x =>                  // g = function taking x (initially undefined)
    a.map(t =               //   initialize t to a non-numeric value
      (r, Y) =>             //   for each row r[] at position Y in a[]:
      r.map((v, X) =>       //     for each value v at position X in r[]:
        1 / x ?             //       if x is defined (this is a recursive call):
          t |=              //         set the flag t if:
            (x - X) ** 2 +  //           the squared Euclidean distance
            (y - Y) ** 2    //           between (x, y) and (X, Y)
            < v             //           is less than v (3 = Astan, 0 = Blandia)
        :                   //       else (this is the initial call to g):
          v ||              //         yield v unchanged if it's equal to 3 (Astan)
          g(X, y = Y)       //         otherwise, do a recursive call with (X, Y) = (x, y)
          | t               //         and yield the flag t (0 = no change, 1 = trench)
      )                     //     end of inner map()
    )                       //   end of outer map()
)()                         // initial call to g

```
> 8 votes

# Answer
# K (ngn/k), 24 bytes

```
{x+x&2{++/'3':0,x,0}/~x}

```

Try it online!

uses `0 1 2` for `"AB+"`

`{` `}` function with argument `x`

`~` logical not

`2{` `}/` twice do

* `0,x,0` surround with 0-s (top and bottom of the matrix)
* `3':` triples of consecutive rows
* `+/'` sum each
* `+` transpose

`x&` logical and of `x` with

`x+` add `x` to
> 7 votes

# Answer
# APL (Dyalog Unicode), 11 bytesSBCS

```
⊢⌈{2∊⍵}⌺3 3

```

this is based on @dzaima's 12-byte solution in chat. credit to @Adám himself for thinking of using  in the dfn, and to @H.PWiz for reminding us to use the same encoding for input and output

Try it online!

represents `'AB+'` as `2 0 1` respectively

`{` `}⌺3 3` apply a function to each overlapping 3×3 region of the input, including regions extending 1 unit outside the matrix, padded with 0s

`2∊⍵` is a 2 present in the argument? return a 0/1 boolean

`⊢⌈` per-element max of that and the original matrix
> 5 votes

# Answer
# PowerShell, 220 bytes

It's not as small as the other submissions, but I thought I'd add it for reference. \[FORE!\]

```
function m($i,$m){($i-1)..($i+1)|?{$_-in0..$m}}
$h=$a.count-1;$w=$a[0].length-1
foreach($i in 0..$h){-join$(foreach($j in 0..$w){if ($a[$i][$j]-eq'B'-and($a[(m $i $h)]|?{$_[(m $j $w)]-match'A'})){'+'}else{$a[$i][$j]}})}

```

Try it online!
> 5 votes

# Answer
# Octave, ~~37 31~~ 26 bytes

This function performs a morphological erosion on the Astan (`1-b`) part of the "image" using ~~`conv2`~~ `imerode`, and then uses some arithmetic to make all three areas different symbols. Thanks @LuisMendo for -5 bytes!

```
@(b)2*b-imerode(b,ones(3))

```

Try it online!
> 4 votes

# Answer
# , 28 bytes

```
>.3 3(2 e.,);._3(0|:@,|.)^:4

```

Try it online!

`'AB+'` -\> `2 0 1`

Inspired by ngn's APL solution. 12 bytes just to pad the matrix with zeroes...
> 3 votes

# Answer
# Charcoal, 20 bytes

```
≔⪫θ⸿θＰθＦθ⎇∧№ＫＭA⁼Bι+ι

```

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

```
≔⪫θ⸿θ

```

Join the input array with carriage returns rather than the usual newlines. This is needed so that the characters can be printed individually.

```
Ｐθ

```

Print the input string without moving the cursor.

```
Ｆθ

```

Loop over each character of the input string.

```
⎇∧№ＫＭA⁼Bι

```

If the Moore neighbourhood contains an `A`, and the current character is a `B`...

```
+

```

... then overwrite the `B` with a `+`...

```
ι

```

... otherwise print the current character (or move to the next line if the current character is a carriage return).
> 2 votes

# Answer
# JavaScript, 85 bytes

Threw this together late last night and forgot about it. Probably still room for some improvement somewhere.

Input and output is as an array of digit arrays, using `3` for Astan, `0` for Blandia & `1` for the trench.

```
a=>a.map((x,i)=>x.map((y,j)=>o.map(v=>o.map(h=>y|=1&(a[i+v]||x)[j+h]))|y),o=[-1,0,1])

```

Try it online (For convenience, maps from & back to the I/O format used in the challenge)
> 2 votes

# Answer
# Javascript, ~~126~~ 118 bytes

```
_=>_.map(x=>x.replace(/(?<=A)B|B(?=A)/g,0)).map((x,i,a)=>[...x].map((v,j)=>v>'A'&&(a[i-1][j]<v|(a[i+1]||x)[j]<v)?0:v))

```

Pass in one of the string arrays from the question, and you'll get an array of ~~strings~~ character arrays (thanks @Shaggy!) out using 0 for the trench. Can *probably* be golfed more (without switching over to numerical arrays), but I can't think of anything at the moment.
> 2 votes

# Answer
# Retina 0.8.2, ~~92~~ 80 bytes

```
(?<=¶(.)*)B(?=.*¶(?<-1>.)*(?(1)_)A|(?<=¶(?(1)_)(?<-1>.)*A.*¶.*))
a
iT`Ba`+`.?a.?

```

Try it online! Loosely based on my answer to Will I make it out in time? Explanation: Any `B`s immediately above or below `A`s are turned into `a`s. This then reduces the problem to checking `B`s to the left or right of `A`s or `a`s. The `a`s themselves also need to get turned into `+`s of course, but fortunately the `i` flag to `T` only affects the regex match, not the actual transliteration, so the `A`s remain unaffected.
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 187 bytes

```
a=>a.Select((b,i)=>b.Select((c,j)=>{int k=0;for(int x=Math.Max(0,i-1);x<Math.Min(i+2,a.Count);x++)for(int y=Math.Max(0,j-1);y<Math.Min(j+2,a[0].Count);)k+=a[x][y++];return k>1&c<1?9:c;}))

```

Instead of chaining `Take()`s, `Skip()`s, and `Select()`s, instead this uses double for loops to find neighbors. HUGE byte decrease, from 392 bytes to 187. Linq isn't always the shortest!

Try it online!
> 1 votes

# Answer
# Java 8, ~~169~~ 145 bytes

```
m->{for(int i=m.length,j,k;i-->0;)for(j=m[i].length;j-->0;)for(k=9;m[i][j]==1&k-->0;)try{m[i][j]=m[i+k/3-1][j+k%3-1]<1?2:1;}catch(Exception e){}}

```

-24 bytes thanks to *@OlivierGrégoire*.

Uses `0` instead of `A` and `1` instead of `B`, with the input being a 2D integer-matrix. Modifies the input-matrix instead of returning a new one to save bytes.

The cells are checked the same as in my answer for the *All the single eights* challenge.

Try it online.

**Explanation:**

```
m->{                            // Method with integer-matrix parameter and no return-type
  for(int i=m.length,j,k;i-->0;)//  Loop over the rows
    for(j=m[i].length;j-->0;)   //   Inner loop over the columns
      for(k=9;m[i][j]==1&       //    If the current cell contains a 1:
          k-->0;)               //     Inner loop `k` in the range (9, 0]:
        try{m[i][j]=            //      Set the current cell to:
             m[i+k/3-1]         //       If `k` is 0, 1, or 2: Look at the previous row
                                //       Else-if `k` is 6, 7, or 8: Look at the next row
                                //       Else (`k` is 3, 4, or 5): Look at the current row
              [j+k%3-1]         //       If `k` is 0, 3, or 6: Look at the previous column
                                //       Else-if `k` is 2, 5, or 8: Look at the next column
                                //       Else (`k` is 1, 4, or 7): Look at the current column
               <1?              //       And if this cell contains a 0:
                  2             //        Change the current cell from a 1 to a 2
                 :              //       Else:
                  1;            //        Leave it a 1
        }catch(Exception e){}}  //      Catch and ignore ArrayIndexOutOfBoundsExceptions
                                //      (try-catch saves bytes in comparison to if-checks)

```
> 1 votes

# Answer
# Perl 5, ~~58~~ 46 bytes

```
$m=($n=/$/m+"@+")-2;s/A(|.{$m,$n})\KB|B(?=(?1)A)/+/s&&redo

```

TIO

-12 bytes thanks to @Grimy

```
/.
/;s/A(|.{@{-}}.?.?)\KB|B(?=(?1)A)/+/s&&redo

```

TIO

* `-p` like `-n` but print also
* `-00` paragraph mode
* to get the width-1 `/.\n/` matches the last character of first line
* `@{-}` special array the position of start of match of previous matched groups, coerced as string (first element)
* `s/../+/s&&redo` replace match by `+` while matches
    + `/s` flag, so that `.` matches also newline character
* `A(|.{@{-}}.?.?)\KB` matches
    + `AB` or `A` followed by (width-1) to (width+1) characters folowed by `B`
    + `\K` to keep the left of `B` unchanged
* `B(?=(?1)A)`,
    + `(?1)` dirverting recursive, to reference previous expression `(|.{$m,$o})`
    + `(?=..)` lookahead, to match without consuming input
> 1 votes

# Answer
# 05AB1E, 29 bytes

```
_2FIн¸.øVgN+FYN._3£})εøO}ø}*Ā+

```

Matrices aren't really 05AB1E's strong suit (nor are they my strong suit).. Can definitely be golfed some more, though.
Inspired by *@ngn*'s K (ngn/k) answer, so also uses I/O of a 2D integer matrix with `012` for `AB+` respectively.

Try it online. (The footer in the TIO is to pretty-print the output. Feel free to remove it to see the matrix output.)

**Explanation:**

```
_                # Inverse the values of the (implicit) input-matrix (0→1 and 1→0)
                 #  i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]]
                 #   → [[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0]]
 2F              # Loop `n` 2 times in the range [0, 2):
   Iн            #  Take the input-matrix, and only leave the first inner list of 0s
                 #   i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]] → [0,0,0,0]
     ¸           #  Wrap it into a list
                 #   i.e. [0,0,0,0] → [[0,0,0,0]]
      .ø         #  Surround the inverted input with the list of 0s
                 #   i.e. [[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0]] and [0,0,0,0]
                 #    → [[0,0,0,0],[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0]]
        V        #  Pop and store it in variable `Y`
   g             #  Take the length of the (implicit) input-matrix
                 #   i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]] → 4
    N+           #  Add `n` to it
                 #   i.e. 4 and n=0 → 4
                 #   i.e. 4 and n=1 → 5
      F          #  Inner loop `N` in the range [0, length+`n`):
       Y         #   Push matrix `Y`
        N._      #   Rotate it `N` times towards the left
                 #    i.e. [[0,0,0,0],[1,1,1,1],[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0]] and N=2
                 #     → [[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,1,1,1]]
            3£   #   And only leave the first three inner lists
                 #    i.e. [[1,0,1,1],[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,1,1,1]]
                 #     → [[1,0,1,1],[1,0,0,0],[0,0,0,0]]
              }  #  After the inner loop:
    )            #  Wrap everything on the stack into a list
                 #   → [[[0,0,0,0],[1,1,1,1],[1,0,1,1]],[[1,1,1,1],[1,0,1,1],[1,0,0,0]],[[1,0,1,1],[1,0,0,0],[0,0,0,0]],[[1,0,0,0],[0,0,0,0],[0,0,0,0]]]
     €ø          #  Zip/transpose (swapping rows/columns) each matrix in the list
                 #   → [[[0,1,1],[0,1,0],[0,1,1],[0,1,1]],[[1,1,1],[1,0,0],[1,1,0],[1,1,0]],[[1,1,0],[0,0,0],[1,0,0],[1,0,0]],[[1,0,0],[0,0,0],[0,0,0],[0,0,0]]]
       O         #  And take the sum of each inner list
                 #   → [[2,1,2,2],[3,1,2,2],[2,0,1,1],[1,0,0,0]]
        ø        #  Zip/transpose; swapping rows/columns the entire matrix again
                 #   i.e. [[2,1,2,2],[3,1,2,2],[2,0,1,1],[1,0,0,0]]
                 #    → [[2,3,2,1],[1,1,0,0],[2,2,1,0],[2,2,1,0]]
               } # After the outer loop:
                 #   i.e. [[3,5,5,4,2],[4,6,5,4,2],[2,3,2,2,1],[1,1,0,0,0]]
  *              # Multiple each value with the input-matrix at the same positions,
                 # which implicitly removes the trailing values
                 #  i.e. [[3,5,5,4,2],[4,6,5,4,2],[2,3,2,2,1],[1,1,0,0,0]]
                 #   and [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]]
                 #    → [[0,0,0,0],[0,1,0,0],[0,2,1,0],[2,2,1,0]]
   Ā             # Truthify each value (0 remains 0; everything else becomes 1)
                 #  i.e. [[0,0,0,0],[0,1,0,0],[0,2,1,0],[2,2,1,0]]
                 #   → [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,0,0]]
    +            # Then add each value with the input-matrix at the same positions
                 #  i.e. [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,0,0]]
                 #   and [[0,0,0,0],[0,1,0,0],[0,1,1,1],[1,1,1,1]]
                 #    → [[0,0,0,0],[0,2,0,0],[0,2,2,2],[2,2,1,1]]
                 # (and output the result implicitly)

```
> 1 votes

# Answer
# PowerShell, ~~86~~ 80 bytes

```
$p="(.?.?.{$(($args|% i*f '
')-1)})?"
$args-replace"(?s)(?<=A$p)B|B(?=$p`A)",'+'

```

Try it online!

The map is a string with newlines. This script replaces `B` to `+` with regexp `(?<=A(.?.?.{$MapWidth-1})?)B|B(?=(.?.?.{$MapWidth-1})?A)`.

Less golfed Test script:

```
$f = {
$l=($args|% indexOf "`n")-1
$p="(.?.?.{$l})?"
$args-replace"(?s)(?<=A$p)B|B(?=$p`A)",'+'
}

@(
,(@"
AAAAAAAAAA
ABAAAAAABA
ABBBAABABA
ABBBAABABA
ABBBBABABA
ABBBBABBBB
ABBBBABBBB
ABBBBBBBBB
BBBBBBBBBB
"@,@"
AAAAAAAAAA
A+AAAAAA+A
A+++AA+A+A
A+B+AA+A+A
A+B++A+A+A
A+BB+A++++
A+BB+A+BBB
A+BB+++BBB
++BBBBBBBB
"@)
,(@"
AAA
AAA
BBB
"@,@"
AAA
AAA
+++
"@)
,(@"
AAAAAAAAAA
AAAABBBAAA
AAAABBBAAA
AAAABBBAAA
AAAAAAAAAA
BBBBBBABBB
BBBBBBAABB
BBBAAAAABB
BBBBBBBBBB
"@,@"
AAAAAAAAAA
AAAA+++AAA
AAAA+B+AAA
AAAA+++AAA
AAAAAAAAAA
++++++A+++
BB++++AA+B
BB+AAAAA+B
BB+++++++B
"@)
) | % {
    $map,$expected = $_
    $result = &$f $map
    $result-eq$expected
    #$result # uncomment this line to display results
}

```

Output:

```
True
True
True

```
> 1 votes

# Answer
# Ruby, 102 bytes

```
->a{a+=?.*s=a.size
(s*9).times{|i|a[j=i/9]>?A&&a[j-1+i%3+~a.index($/)*(i/3%3-1)]==?A&&a[j]=?+}
a[0,s]}

```

Try it online!

input/output as a newline separated string
> 0 votes

# Answer
# Python 2, ~~123~~ 119 bytes

```
lambda m:[[[c,'+'][c=='B'and'A'in`[x[j-(j>0):j+2]for x in m[i-(i>0):i+2]]`]for j,c in e(l)]for i,l in e(m)];e=enumerate

```

Try it online!

I/O is a list of lists
> 0 votes

# Answer
# TSQL, 252 bytes

Splitting the string is very costly, if the string was split and already in a table the byte count would be 127 characters. Script included in the bottom and completely different. Sorry for taking up this much space.

Golfed:

```
WITH C as(SELECT x,x/z r,x%z c,substring(@,x+1,1)v
FROM spt_values CROSS APPLY(SELECT number x,charindex(char(10),@)z)z
WHERE'P'=type)SELECT @=stuff(@,x+1,1,'+')FROM c WHERE
exists(SELECT*FROM c d WHERE abs(r-c.r)<2and
abs(c-c.c)<2and'AB'=v+c.v)PRINT @

```

Ungolfed:

```
DECLARE @ varchar(max)=
'AAAAAAAAAA
ABAAAAAABA
ABBBAABABA
ABBBAABABA
ABBBBABABA
ABBBBABBBB
ABBBBABBBB
ABBBBBBBBB
BBBBBBBBBB';

WITH C as
(
  SELECT x,x/z r,x%z c,substring(@,x+1,1)v
  FROM spt_values
  CROSS APPLY(SELECT number x,charindex(char(10),@)z)z
  WHERE'P'=type
)
SELECT
  @=stuff(@,x+1,1,'+')
FROM c
WHERE exists(SELECT*FROM c d
         WHERE abs(r-c.r)<2
           and abs(c-c.c)<2 and'AB'=v+c.v)
PRINT @

```

**Try it out**

# TSQL, 127 bytes(Using table variable as input)

Execute this script in management studio - use "query"-"result to text" to make it readable

```
--populate table variable
USE master
DECLARE @v varchar(max)=
'AAAAAAAAAA
ABAAAAAABA
ABBBAABABA
ABBBAABABA
ABBBBABABA
ABBBBABBBB
ABBBBABBBB
ABBBBBBBBB
BBBBBBBBBB'

DECLARE @ table(x int, r int, c int, v char)

INSERT @
SELECT x+1,x/z,x%z,substring(@v,x+1,1)
FROM spt_values
CROSS APPLY(SELECT number x,charindex(char(10),@v)z)z
WHERE'P'=type and len(@v)>number

-- query(127 characters)

SELECT string_agg(v,'')FROM(SELECT
iif(exists(SELECT*FROM @
WHERE abs(r-c.r)<2and abs(c-c.c)<2and'AB'=v+c.v),'+',v)v
FROM @ c)z

```

**Try it out** \- warning output is selected and not readable. Would be readable with print, but that is not possible using this method
> 0 votes

---
Tags: code-golf, matrix, cellular-automata
---


title: Is magic possible?

text:
# Question
Title: Is magic possible?
A magic square is an **n-by-n** square grid, filled with distinct positive integers in the range **1,2,...n^2**, such that each cell contains a different integer and the sum of the integers in each row, column and diagonal is equal.

Your task is to take an **n-by-n** matrix consisting of positive numbers, and a placeholder character for empty cells (I'll use **0**, but you can use any non-numeric character or datatype you like), and determine if it's possible to make a magic square by filling in the missing numbers

The matrix will be at least **2-by-2**, and at most **10-by-10**. The smallest possible non-trivial magic square is **3-by-3**. The numbers in the input matrix might be higher than **n^2**, and it's possible that all cells are filled.

## Test cases:

```
2   2
2   0
False

8   0   6
0   5   0
0   9   2
True

16    2    3   13
 5   11   10    8
 9    7    6   12
 4   14   15    1
True

10   0   1
 0   5   9
 3   7   5
False

99    40    74     8    15    51     0    67     0     1
 0    41    55    14     0    57    64     0    98     0
81    47    56    20    22    63    70    54     0    88
 0    28     0    21     0    69    71    60    85    19
 0    34     0     2     9    75    52    61     0    25
24    65    49     0    90    26    33    42    17    76
 0     0    30    89    91     0    39    48     0    82
 6    72    31    95     0    38    45    29     0    13
12    53     0    96    78     0     0     0    10    94
18    59    43    77     0     0    27    36     0   100
True

```

# Answer
> 5 votes
## JavaScript (ES6), ~~270~~ 268 bytes

Takes the matrix as a 2D array. Returns `0` or `1`.

```
a=>(g=(x,y=0,w=a.length,p,R=a[y])=>[0,1,2,3].some(d=>a.some((r,y)=>(p=s)^(s=r.reduce((p,v,x)=>(o|=1<<(v=[v,(b=a[x])[y],b[x++],b[w-x]][d]),p+v),0))&&p),s=o=0)||o/2+1!=1<<w*w?R&&[...Array(w*w)].map((_,n)=>(p=R[x])==++n|!p&&(R[x]=n,g(z=(x+1)%w,y+!z),R[x]=p)):r=1)(r=0)&&r

```

### Test cases

This is definitely too slow for the last test case. :-(

```
let f =

a=>(g=(x,y=0,w=a.length,p,R=a[y])=>[0,1,2,3].some(d=>a.some((r,y)=>(p=s)^(s=r.reduce((p,v,x)=>(o|=1<<(v=[v,(b=a[x])[y],b[x++],b[w-x]][d]),p+v),0))&&p),s=o=0)||o/2+1!=1<<w*w?R&&[...Array(w*w)].map((_,n)=>(p=R[x])==++n|!p&&(R[x]=n,g(z=(x+1)%w,y+!z),R[x]=p)):r=1)(r=0)&&r

console.log(f([
  [ 2,  2 ],
  [ 2,  0 ]
]));

console.log(f([
  [ 8,  0,  6 ],
  [ 0,  5,  0 ],
  [ 0,  9,  2 ]
]));

console.log(f([
  [ 16,   2,   3,  13 ],
  [  5,  11,  10,   8 ],
  [  9,   7,   6,  12 ],
  [  4,  14,  15,   1 ]
]));

console.log(f([
  [ 10,  0,  1 ],
  [  0,  5,  9 ],
  [  3,  7,  5 ]
]));
```

# Answer
> 4 votes
# 05AB1E, ~~45~~ 38 bytes

```
gn¹à@¹˜āsKœ0ªεÎ˜r.;¹gôD©ø®Å\®Å/)O˜Ë}à*

```

Also uses \\$0\\$ as placeholder. The more \\$0\\$s in the input, the slower the program is. Size of the matrix doesn't matter that much (a 10x10 matrix with three \\$0\\$s runs quite a bit faster than a 3x3 matrix with seven \\$0\\$s).

Could have been 4 bytes less, but there is currently a bug in the builtin `.;` with 2D lists. `:` and `.:` work as expected, but `.;` doesn't do anything on 2D lists right now.. hence the work-around of `˜` and `¹gô` to flatten the matrix; use `.;` on the list; and transform it back into a matrix again.

Try it online or verify some more test cases. (NOTE: Last test case of the challenge description is not included, because it has way too many 0s..)

**Explanation:**

```
g          # Get the length of the (implicit) input-matrix (amount of rows)
           #  i.e. [[8,0,6],[0,5,0],[0,0,2]] → 3
 n         # Square it
           #  → 9
  ¹        # Push the input-matrix again
   à       # Pop and push its flattened maximum
           #  → 8
    @      # Check if the squared matrix-dimension is >= this maximum
           #  → 9 => 8 → 1 (truthy)
¹          # Push the input-matrix again
 ˜         # Flatten it
           #  → [8,0,6,0,5,0,0,0,2]
  ā        # Push a list in the range [1,length] (without popping)
           #  → [1,2,3,4,5,6,7,8,9]
   s       # Swap so the flattened input is at the top of the stack again
    K      # Remove all these numbers from the ranged list
           #  → [1,3,4,7,9]
œ          # Get all possible permutations of the remaining numbers
           # (this part is the main bottleneck of the program;
           #  the more 0s and too high numbers, the more permutations)
           #   i.e. [1,3,4,7,9] → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]]
 0ª        # Add an item 0 to the list (workaround for inputs without any 0s)
           #  i.e. [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]]
           #   → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1],"0"]
ε          # Map each permutation to:
 Î         #  Push 0 and the input-matrix
  ˜        #  Flatten the matrix again
   r       #  Reverse the items on the stack, so the order is [flat_input, 0, curr_perm]
    .;     #  Replace all 0s with the numbers in the permutation one by one
           #   i.e. [8,0,6,0,5,0,0,0,2] and [1,3,4,7,9]
           #    → [8,1,6,3,5,4,7,9,2]
      ¹g   #  Push the input-dimension again
        ô  #  And split the flattened list into parts of that size,
           #  basically transforming it back into a matrix
           #   i.e. [8,1,6,3,5,4,7,9,2] and 3 → [[8,1,6],[3,5,4],[7,9,2]]
 D         #  Duplicate the current matrix with all 0s filled in
  ©        #  Store it in variable `®` (without popping)
   ø       #  Zip/transpose; swapping rows/columns of the top matrix
           #   → [[8,3,7],[1,5,9],[6,4,2]]
 ®Å\       #  Get the top-left to bottom-right main diagonal of `®`
           #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [8,5,2]
 ®Å/       #  Get the top-right to bottom-left main diagonal of `®`
           #   i.e. [[8,1,6],[3,5,4],[7,9,2]] → [6,5,7]
    )      #  Wrap everything on the stack into a list
           #   → [[[8,1,6],[3,5,4],[7,9,2]],
           #      [[8,3,7],[1,5,9],[6,4,2]],
           #      [8,5,2],
           #      [6,5,7]]
     O     #  Sum each inner list
           #   → [[15,12,18],[18,15,12],15,18]
      ˜    #  Flatten it
           #   → [15,12,18,18,15,12,15,18]
       Ë   #  Check if all values are the same
           #   → 0 (falsey)
}à         # After the map: Check if any are truthy by taking the maximum
           #  → 1 (truthy)
*          # And multiply it to the check we did at the start to verify both are truthy
           #  → 1 (truthy)
           # (after which the result is output implicitly)

```

The part `D©ø®Å\®Å/)O˜Ë` is also used in my 05AB1E answer for the *Verify Magic Square* challenge, so see that answer for a more in-depth explanation about that part of the code.

---
Tags: code-golf, math, number, decision-problem, matrix
---


# Question
Title: Random Golf of the Day #2: Numbers from a Normal Distribution
# About the Series

First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You can find the leaderboard along with some more information about the series in the first post.

Although I have a bunch of ideas lined up for the series, the future challenges are not set in stone yet. If you have any suggestions, please let me know on the relevant sandbox post.

# Hole 2: Numbers from a Normal Distribution

I can't believe this hasn't been done yet! You're to generate random numbers, drawing from a normal distribution. Some rules (the majority of them are probably automatically covered by most submission, but some of them are in place to ensure consistency of results between vastly different languages):

* You should take **two non-negative integers as input**: a seed `S` and the amount `N` of numbers to return. The output should be a list of `N` floating point numbers, drawn from a normal distribution with **mean 0** and **variance 1**. Whenever your submission is given the same seed `S` it should produce the same number. In particular, if it is called once with `(S, N<sub>1</sub>)` and once with `(S, N<sub>2</sub>)`, the first `min(N<sub>1</sub>, N<sub>2</sub>)` entries of the two outputs should be identical. In addition, **at least 216 different values of `S` should produce different sequences.**
* You may use any built-in random number generator that is documented to draw numbers from an (approximately) *uniform* distribution, provided you can pass `S` on to it and it supports at least 216 different seeds. If you do, **the RNG should be able to return at least 220 different values** for any given number you request from it.
* If your available uniform RNG has a smaller range, is not seedable, or supports too few seeds, you must either first build a uniform RNG with a sufficiently large range on top of the built-in one or you must implement your own suitable RNG using the seed. This page may be helpful for that.
* If you don't implement an established algorithm for generating normal distributions, please include a proof of correctness. In either case, **the algorithm you choose must yield a theoretically exact normal distribution** (barring limitations of the underlying PRNG or limited-precision data types).
* Your implementation should use and return either **floating-point numbers (at least 32 bits wide)** or **fixed-point numbers (at least 24 bits wide)** and all arithmetic operations should make use of the full width of the chosen type.
* You must not use any built-in functions directly related to normal distribution or Gaussian integrals, like the Error function or its inverse.

You may write a full program or a function and take input via STDIN, command-line argument, function argument or prompt and produce output via return value or by printing to STDOUT (or closest alternative).

`S` and `N` will be non-negative integers, each less than 220. Output may be in any convenient, unambiguous list or string format.

This is code golf, so the shortest submission (in bytes) wins. And of course, the shortest submission per user will also enter into the overall leaderboard of the series.

# Leaderboard

**The first post of the series generates a leaderboard.**

To make sure that your answers show up, please start every answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

*(The language is not currently shown, but the snippet does require and parse it, and I may add a by-language leaderboard in the future.)*

# Answer
> 8 votes
# R, 68 bytes

```
function(S,N){set.seed(S);sqrt(-2*log(runif(N)))*cos(2*pi*runif(N))}

```

This uses the `runif()` function, which generates random deviates from a uniform distribution. The seed for the random number generation is specified using `set.seed()`, which by default uses the Mersenne-Twister algorithm with a period of 2^19937-1.

The result is an R vector of length N containing the computed standard normal deviates.

This uses the Box-Muller method: For two independent uniform random variables U and V,

# Answer
> 8 votes
# Dyalog APL, 33 bytes

`{(.5*⍨¯2×⍟?0)×1○○2×?0}¨⍳⎕⊣⎕rl←1+⎕`

Box-Muller:

```
⎕         ⍝ evaluated input
⎕rl←1+⎕   ⍝ set APL's random seed to 1+⎕ (S)
          ⍝   add 1 because ⎕rl←0 has special meaning: sets the seed randomly
{ }¨⍳N    ⍝ do the thing in braces N times
?0        ⍝ random number 0≤x<1
1○○2×A    ⍝ sin(2πA)
.5*⍨¯2×⍟B ⍝ sqrt(-2lnB)

```

# Answer
> 4 votes
## Dyalog APL, ~~42~~ 34

```
{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}

```

This is a function that takes `S` as its left argument and `N` as its right argument.

```
     5{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}10
3.019132549 ¯0.2903143175 ¯0.7353414637 1.421417015 2.327544764 ¯0.00005019747711 ¯0.9582127248 ¯0.2764568462
      ¯0.1602736853 ¯0.9912352616
     5{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}20
3.019132549 ¯0.2903143175 ¯0.7353414637 1.421417015 2.327544764 ¯0.00005019747711 ¯0.9582127248 ¯0.2764568462
      ¯0.1602736853 ¯0.9912352616 0.642585109 ¯0.2450019151 ¯0.415034463 0.03481768503 ¯0.4621212815 ¯0.760925979
      0.2592913013 1.884867889 ¯0.9621252731 0.3062560446

```

It's an implementation of the Box-Muller transform, using Dyalog APL's built-in random operator `?`, which by default is a Mersenne twister that returns 64-bit values, which should be enough.

Explanation:

* `⎕RL←⍺`: set the random seed to .
* `?⍵2⍴0`: generate  pairs of random numbers between 0 and 1.
* `{`...`}/`: apply the following function to each pair:
    + `(.5*⍨¯2×⍟⍺)×1○⍵×○2`: calculate the `Z0` value (`sqrt(-2 ln ⍺)×cos(2π⍵)`).

# Answer
> 3 votes
# Java, ~~164~~ 161 bytes

```
class B extends java.util.Random{B(int s,int n){super(s);for(;n-->0;System.out.println(Math.sqrt(-2*Math.log(nextDouble()))*Math.cos(2*Math.PI*nextDouble())));}}

```

This takes in input via function and output via stdout. It uses the Box-Muller method.

# Answer
> 3 votes
# Perl, 67

```
sub f{srand$_[0];map{cos(atan2(1,1)*rand 8)*sqrt-2*log rand}1..pop}

```

Box-Muller as in other entries. `f` takes parameters in order `S, N`.

Use:

```
$ perl -le 'sub f{srand$_[0];map{cos(atan2(1,1)*rand 8)*sqrt-2*log rand}1..pop}print for f(5,3)'
-1.59212831801942
0.432167710756345
-0.533673305924252

```

# Answer
> 3 votes
# Commodore 64 Basic, ~~76~~ ~~70~~ 63 bytes

```
1INPUTS,N:S=R/(-S):F┌I=1TON:?S●(-2*LOG(R/(1)))*S╮(2*π*R/(1)):N─

```

Since the PETSCII character set contains some symbols not present in Unicode, I've made substitutions: `/` = `SHIFT+N`,  = `SHIFT+O`,  = `SHIFT+Q`,  = `SHIFT+I`,  = `SHIFT+E`

This implements the standard Box-Muller transform to generate the numbers; I picked the sin(x) half of the transform because Commodore 64 Basic has a two-character shortcut for `sin()`, but not for `cos()`.

Although the manual states otherwise, the value of the argument to `RND` *does* matter: if a negative number is passed, the random number generator is not merely re-seeded, it is re-seeded *with that number*. This makes seeding much simpler: instead of needing to `POKE` five memory locations, I merely need to make a do-nothing call to `RND`, which reduces the code from two lines/121 bytes to 1 line/76 bytes.

Edit: Golfed six bytes off by realizing I could combine the two `INPUT` statements, and that the space after `TO` was optional.

Edit: Golfed another seven off: Commodore Basic does, in fact, have Pi as a built-in constant, and it's even typeable on a modern keyboard (`SHIFT+PgDn`, in case you were wondering).

# Answer
> 3 votes
# 80386 machine code, 72 bytes

Hexdump of the code:

```
60 8b 7c 24 24 33 ed 8d 75 fb 8d 46 79 f7 e2 f7
f6 8b da b3 7f 0f cb d1 eb 89 1f d9 07 d9 e8 de
e9 33 ee 75 e5 d9 ed d9 c9 d9 f1 dc c0 d9 e0 d9
fa d9 c9 d9 eb de c9 dc c0 d9 ff de c9 d9 1f 83
c7 04 e2 c6 61 c2 04 00

```

Here is the source code (can be compiled by Visual Studio):

```
__declspec(naked) void __fastcall doit(int count, unsigned seed, float* output)
{
    _asm {
                                // ecx = count
                                // edx = seed
        // save registers
        pushad;
        mov edi, [esp + 0x24];  // edi = pointer to output
        xor ebp, ebp;           // ebp = 0
        lea esi, [ebp - 5];     // esi = 4294967291 (a prime number)

    myloop:
        // Calculate the next random number
        lea eax, [esi + 121];   // eax = 116
        mul edx;
        div esi;
        mov ebx, edx;

        // Convert it to a float in the range 1...2
        mov bl, 0x7f;
        bswap ebx;
        shr ebx, 1;

        // Convert to range 0...1 and push onto the FPU stack
        mov [edi], ebx;
        fld dword ptr [edi];
        fld1;
        fsubp st(1), st;

        // Make 2 such random numbers
        xor ebp, esi;
        jnz myloop;

        // Calculate sqrt(-2*ln(x))
        fldln2;
        fxch;
        fyl2x;
        fadd st, st(0);
        fchs;
        fsqrt;

        // Calculate cos(2*pi*y)
        fxch st(1);
        fldpi;
        fmul;
        fadd st, st(0);
        fcos;

        // Calculate and write output
        fmulp st(1), st;
        fstp dword ptr [edi];
        add edi, 4;

        // Repeat
        loop myloop

        // Return
        popad;
        ret 4;
    }
}

```

---

Here I use a a Lehmer random number generator. It uses the following algorithm:

```
x(k+1) = 116 * x(k) mod 4294967291

```

Here 4294967291 is a big (2^32-5) prime number, and 116 is a small (less than 128; see below) number that is its primitive root. I chose a primitive root that has a more-or-less random distribution of zeros and ones in binary representation (01110100). This RNG has the maximum possible period of 4294967290, if the seed is nonzero.

---

The relatively small numbers I used here (116 and 4294967291, which can be represented also as -5) let me take advantage of the `lea` instruction encoding:

```
8d 46 79     lea eax, [esi+121]

```

It is assembled to 3 bytes if the numbers can fit into 1 byte.

---

The multiplication and division use `edx` and `eax` as their working registers, which is why I made `seed` the second parameter to the function (`fastcall` calling convention uses `edx` to pass the second parameter). In addition, the first parameter is passed in `ecx`, which is a good place to hold a counter: a loop can be organized in 1 instruction!

```
e2 c6        loop myloop

```

---

To convert an integer into a floating-point number, I exploited the representation of single-precision floating-point numbers: if I set the high 9 bits (exponent) to the bit pattern `001111111`, and leave the 23 low bits random, I'll get a random number in the range 1...2. I took the idea from here. To set the high 9 bits, I used some bit-fiddling on `ebx`:

```
mov ebx, edx;    xxxxxxxx|yyyyyyyy|zzzzzzzz|aaaaaaaa
mov bl, 0x7f;    xxxxxxxx|yyyyyyyy|zzzzzzzz|01111111
bswap ebx;       01111111|zzzzzzzz|yyyyyyyy|xxxxxxxx
shr ebx, 1;      00111111|1zzzzzzz|zyyyyyyy|yxxxxxxx

```

---

To generate two random numbers, I used a nested loop of 2 iterations. I organized it with `xor`:

```
xor ebp, esi;    first time, the result is -5
jnz myloop;      second time, the result is 0 - exit loop

```

---

The floating-point code implements the Box-Muller transform.

# Answer
> 2 votes
# Haskell, 118  ~~144~~

```
import System.Random;h z=let(u,r)=random z in(cos$2*pi*fst(random r)::Float)*sqrt(-2*log u):h r;g=(.(h.mkStdGen)).take

```

Example usage:

```
*Main> g 3 0x6AE4A92CAFA8A742
[0.50378895,-0.20593005,-0.16684927]
*Main> g 6 0x6AE4A92CAFA8A742
[0.50378895,-0.20593005,-0.16684927,1.1229043,-0.10026576,0.4279402]
*Main> g 6 0xE09B1088DF461F7D
[2.5723906,-0.5177805,-1.3535261,0.7400385,3.5619608e-3,-8.246434e-2]

```

The return type of `random` is constrained to `Float`, which makes `random` generate a uniform float in \[0, 1). From then on it's a simlpe box-muller formula with some pointless magic for list generation.

# Answer
> 2 votes
# Octave, 91 ~~96~~ 88 bytes

```
function r=n(s,n)rand("seed",s);x=rand(2,n);r=cos(2*pi*x(1,:)).*sqrt(-2*log(x(2,:)));end

```

Or, with whitespace:

```
function r=n(s,n)
  rand("seed",s);
  x=rand(2,n);
  r=cos(2*pi*x(1,:)).*sqrt(-2*log(x(2,:)));
end

```

Set the seed up front, and use the Box-Mueller method.

NB: Octave allows for generation of arrays of random numbers, and can use standard operations on these arrays which produce array outputs. The `.*` operator is element-by-element multiplication of two arrays to produce the result.

# Answer
> 2 votes
# Golflua, 63 ~~70~~

Golflua info and instructions.

```
\g(n,s)`_ENV,b=M,{}rs(s)~@i=1,n b[i]=q(l(r()^-2))*c(r()*pi)$~b$

```

Returns a table containing the values. In the example I'm using `~T.u( )`, which is the same as `return table.unpack( )` in lua.

```
> ~T.u(g(3,1234567))
0.89302672974232 0.36330401643578 -0.64762161593981
> ~T.u(g(5,1234567))
0.89302672974232 0.36330401643578 -0.64762161593981 -0.70654636393063 -0.65662878785425
> ~T.u(g(5,7654321))
0.3867923683064 -0.31758512485963 -0.58059120409317 1.2079459300077 1.1500121921242

```

A lot of chars were saved by setting the function's environment to `M` (aka `math`).

# Answer
> 2 votes
# Java, 193 bytes

While this doesn't beat the current Java leader, I decided to post anyway to show a different method of calculation. It's a golfed version of OpenJDK's `nextGaussian()`.

```
class N extends java.util.Random{N(int s,int n){super(s);for(float a,v;n-->0;System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))for(a=0;a>=1|a==0;a=v*v+(v=2*nextFloat()-1)*v)v=2*nextFloat()-1;}}

```

With line breaks:

```
class N extends java.util.Random{
    N(int s,int n){
        super(s);
        for(float a,v;
            n-->0;
            System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))
                for(a=0;
                    a>=1|a==0;
                    a=v*v+(v=2*nextFloat()-1)*v)v=2*nextFloat()-1;
    }
}

```

# Answer
> 2 votes
# SAS, 108

I already posted an answer in R that's shorter than this, but there are very few SAS answers on PPCG, so why not add another?

```
%macro f(s,n);data;do i=1 to &n;x=sqrt(-2*log(ranuni(&s)))*cos(8*atan2(1,1)*ranuni(&s));put x;end;run;%mend;

```

With some white space:

```
%macro f(s, n);
    data;
        do i = 1 to &n;
            x = sqrt(-2 * log(ranuni(&s))) * cos(8 * atan2(1, 1) * ranuni(&s));
            put x;
        end;
    run;
%mend;

```

This defines a macro which can be called like `%f(5, 3)`. The macro executes a data step which loops through the integers 1 to N, and at each iteration it computes a random normal deviate using Box-Muller and prints it to the log using the `put` statement.

SAS has no built-in for pi, so the best we can do is approximate it with arctangent.

The `ranuni()` function (which is deprecated but requires a couple fewer characters than the newer function) returns a random number from a uniform distribution. The SAS documentation doesn't give a whole lot of detail on the RNG implementation other than it has a period of 2^31-2.

In SAS macros, macro variables are referenced with a preceding `&` and resolve to their values at run time.

As you've probably witnessed, SAS is rarely an actual contender in a contest.

# Answer
> 2 votes
## T-SQL, 155 bytes

```
CREATE PROC R(@S BIGINT,@N INT)AS
DECLARE @ INT=0,@K INT=8388607WHILE @<@N
BEGIN
SELECT SQRT(-2*LOG(RAND(@S*@%@K)))*COS(2*PI()*RAND(@S*9*@%@K))SET @+=1
END

```

Use with EXEC R S,N because there is no STD\_IN in T-SQL where S and N are the seed and N respectively. S will produce "random" (RAND(seed) is a really bad random number implementation) sequences when S\>2^16 (possibly before that, but I won't guarantee it). Uses Box-Muller like most solutions so far. 8388607 is 2^23-1, which should hopefully generate 2^20 different values.

# Answer
> 2 votes
## Powershell, 164 bytes

```
Param($s,$n)$q=2147483647
$a=GET-RANDOM -SETSEED $s
FOR(;$n---gt0;){$a=GET-RANDOM
$b=GET-RANDOM
[math]::SQRT(-2*[math]::LOG($a/$q))*[math]::COS(2*[math]::PI*$b/$q)}

```

Same as most answers with Box-Muller. Not very experienced with Powershell, so any help golfing would be appreciated.

# Answer
> 2 votes
# Matlab, 77

The first input should be `n`, the second one `s`.

```
a=input('');
rand('seed',a(2));
for i=1:a;
    (-2*log(rand))^.5*cos(2*pi*rand)
end

```

# Answer
> 2 votes
# Ruby, 72 bytes

```
->n,s{include Math;srand s;n.times{p sqrt(-2*log(rand))*sin(2*rand*PI)}}

```

### Input (as lambda function):

```
f.(6, 12353405)

```

### Output:

```
-1.1565142460805273
0.9352802655317097
1.3566720571574993
-0.9683973210257978
0.9851210877202192
0.14709635752306677

```

PS: I would like to know if this can be golfed further. I'm just a beginner.

# Answer
> 2 votes
# Pyth, 32 bytes

No Python being used now in super-quotes because of the new functions Pyth has now. Yet another Box-Mueller.

```
 .xvzVQ*@_y.lOZ2.71 2.ty*3.14OZ1

```

That space in the beginning is important.

```
.xvz             Seed RNG with evaluated input
VQ               For N in second input
*                Multiplication
 @       2       Square root
   _y            Times negative 2
    .l )         Natural log
     OZ          Of random float (RNG with zero give [0, 1) float)
 .t       1      Cosine from list of trig functions
  y              Double
   *             Multiplication
    .nZ          Pi from constants list
    OZ           Random Float

```

The seeding doesn't seem to work in the online interpreter, but it works fine in the local version. The online interpreter seems to be fixed, so here's a permalink: permalink

# Answer
> 1 votes
## STATA, 85 bytes

```
di _r(s)_r(n)
set se $s
set ob $n
g a=sqrt(-2*ln(runiform()))*cos(2*runiform()*_pi)
l

```

Takes input via standard in (first number is S, then N). Sets the seed to S. Sets the number of observations to N. Makes a variable and sets its value to the Box Muller transform value (thanks to @Alex for showing it). Then lists all of the observations in a table with column header a and observation numbers next to them. If these are not okay, let me know, and I can remove headers and/or observation numbers.

# Answer
> 1 votes
# R, 89 Bytes

I know R has been done before but I wanted to show a different approach than the Box-Muller that everyone else used. My solution uses the Central Limit Theorem.

```
f=function(S,N){set.seed(S);a=1000;for(i in(1:N)){print(sqrt(12/a)*(sum(runif(a))-a/2))}}

```

# Answer
> 1 votes
# Perl, ~~150~~ ~~108~~ 107 bytes

This uses the Marsaglia Polar Method. Called with f(S, N).

Moved the assignment of `$a` into the calculation of `$c`.

107:

```
sub f{srand$_[0];map{do{$c=($a=-1+2*rand)**2+(-1+2*rand)**2}until$c<1;print$a*sqrt(-2*log($c)/$c)}1..$_[1]}

```

Removed spare number storage and the definition of `$b`.

108:

```
sub f{srand$_[0];map{do{$a=-1+2*rand,$c=$a**2+(-1+2*rand)**2}until$c<1;print$a*sqrt(-2*log($c)/$c)}1..$_[1]}

```

150:

```
sub f{srand$_[0];map{$h?$h=!print$s:do{do{$a=-1+2*rand,$b=-1+2*rand,$c=$a*$a+$b*$b}until$c<1;$d=sqrt(-2*log($c)/$c);$s=$b*$d;$h=print$a*$d;}}1..$_[1]}

```

# Answer
> 1 votes
## TI-Basic, 74 bytes

```
Prompt S,N:S→rand:For(X,1,N:0→A:0→V:0→W:While A≥1 or A=0:2rand-1→V:2rand-1→W:V²+W²→A:End:Disp VW√(Aֿ¹-2log(A:End

1      1111111   11   1111111111111111111     1111   111111   1111111   11111111111111  11    111111111   111

```

The `¹` is actually the inverse operator.

# Answer
> 1 votes
## Swift, 144 142

Nothing clever, just seeing how Swift works.

```
import Foundation;func r(s:UInt32,n:Int){srand(s);for i in 0..<n{println(sqrt(-2*log(Double(rand())/0xffffffff))*sin(2*Double(rand())*M_PI))}}

```

I was hoping I could use (0...n).map{} but it the compiler doesn't seem to recognise map{} unless you use a parameter.

# Answer
> 1 votes
# Haskell, 97 bytes

```
import System.Random
h(a:b:c)=sqrt(-2*log a::Float)*cos(2*pi*b):h c
f a=take a.h.randoms.mkStdGen

```

Try it online!

Just your basic Box-Muller transformation, on an infinite list of random numbers.

# Answer
> 1 votes
# Python 3, 118 bytes

```
from random import*
from math import*
def f(s,n):seed(s);return[sqrt(-2*log(random()))*cos(tau*random())for _ in[0]*n]

```

Try it online!

# Answer
> 0 votes
# SmileBASIC, 81 bytes

Well, now that I've answered the first question, I have to do all the rest...

Generating random numbers is cheap, but seeding the RNG uses the *longest* builtin function in the language, `RANDOMIZE`.

```
DEF N S,N
RANDOMIZE.,S
FOR I=1TO N?SQR(-2*LOG(RNDF()))*COS(PI()*2*RNDF())NEXT
END

```

Maybe there's some way to optimize the formula. I don't see how it's required to use two RNG calls.

---
Tags: code-golf, number, random
---