text:
The Hungry Mouse
Sixteen piles of cheese are put on a 4x4 square. They're labeled from \$1\$ to \$16\$. The smallest pile is \$1\$ and the biggest one is \$16\$.
The Hungry Mouse is so hungry that it always goes straight to the biggest pile (i.e. \$16\$) and eats it right away.
After that, it goes to the biggest neighboring pile and quickly eats that one as well. (Yeah ... It's really hungry.) And so on until there's no neighboring pile anymore.
A pile may have up to 8 neighbors (horizontally, vertically and diagonally). There's no wrap-around.
Example
We start with the following piles of cheese:
$$\begin{matrix}
3&7&10&5\\
6&8&12&13\\
15&9&11&4\\
14&1&16&2
\end{matrix}$$
The Hungry Mouse first eats \$16\$, and then its biggest neighbor pile, which is \$11\$.
$$\begin{matrix}
3&7&10&5\\
6&8&12&13\\
15&9&&4\\
14&1&\color{grey}\uparrow&2
\end{matrix}$$
Its next moves are \$13\$, \$12\$, \$10\$, \$8\$, \$15\$, \$14\$, \$9\$, \$6\$, \$7\$ and \$3\$ in this exact order.
$$\begin{matrix}
&\color{grey}\leftarrow&\small\color{grey}\swarrow&5\\
\small\color{grey}\nearrow&\small\color{grey}\swarrow&\color{grey}\uparrow&\color{grey}\leftarrow\\
\color{grey}\downarrow&\small\color{grey}\nwarrow&\small\color{grey}\nearrow&4\\
\small\color{grey}\nearrow&1&\color{grey}\uparrow&2
\end{matrix}$$
There's no cheese anymore around the Hungry Mouse, so it stops there.
The challenge
Given the initial cheese configuration, your code must print or return the sum of the remaining piles once the Hungry Mouse has stopped eating them.
For the above example, the expected answer is \$12\$.
Rules

Because the size of the input matrix is fixed, you may take it as either a 2D array or a one-dimensional array.
Each value from \$1\$ to \$16\$ is guaranteed to appear exactly once.
This is code-golf.

Test cases
[ [ 4,  3,  2,  1], [ 5,  6,  7,  8], [12, 11, 10,  9], [13, 14, 15, 16] ] --> 0
[ [ 8,  1,  9, 14], [11,  6,  5, 16], [13, 15,  2,  7], [10,  3, 12,  4] ] --> 0
[ [ 1,  2,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12], [13, 14, 15, 16] ] --> 1
[ [10, 15, 14, 11], [ 9,  3,  1,  7], [13,  5, 12,  6], [ 2,  8,  4, 16] ] --> 3
[ [ 3,  7, 10,  5], [ 6,  8, 12, 13], [15,  9, 11,  4], [14,  1, 16,  2] ] --> 12
[ [ 8,  9,  3,  6], [13, 11,  7, 15], [12, 10, 16,  2], [ 4, 14,  1,  5] ] --> 34
[ [ 8, 11, 12,  9], [14,  5, 10, 16], [ 7,  3,  1,  6], [13,  4,  2, 15] ] --> 51
[ [13, 14,  1,  2], [16, 15,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12] ] --> 78
[ [ 9, 10, 11, 12], [ 1,  2,  4, 13], [ 7,  8,  5, 14], [ 3, 16,  6, 15] ] --> 102
[ [ 9, 10, 11, 12], [ 1,  2,  7, 13], [ 6, 16,  4, 14], [ 3,  8,  5, 15] ] --> 103

+1 for that mouse character

78? You can be meaner than that! I think 102 is as mean as one can get though (e.g. [[9, 10, 11, 12], [1, 2, 4, 13], [7, 8, 5, 14], [3, 16, 6, 15]]) - hmm [0, 0, 19, 102, ...]

...make that 103: [[9, 10, 11, 12], [1, 2, 7, 13], [6, 16, 4, 14], [3, 8, 5, 15]]

What a nicely written challenge! I'll keep it in mind for the best-of nominations.

After misreading I was a little sad that this was not a hungry moose.

This challenge reminds me of the mouse in the maze program for the txo computer.  This game was written way back in the 1950s, and the txo was the first transistorized computer in the world, according to legend.  Yes, believe it or not,  somebody was writing video games in your grandfather's day.

@akozi Sandboxed challenge "The Hungry Moose": https://codegolf.meta.stackexchange.com/a/17123/39328

If it's hungry why can't it eat some far cheese?

Python 2, 133 130 bytes
a=input();m=16
for i in range(m):a[i*5:i*5]=0,
while m:i=a.index(m);a[i]=0;m=max(a[i+x]for x in[-6,-5,-4,-1,1,4,5,6])
print sum(a)

Try it online!
Takes a flattened list of 16 elements.
How it works
a=input();m=16

# Add zero padding on each row, and enough zeroes at the end to avoid index error
for i in range(m):a[i*5:i*5]=0,

# m == maximum element found in last iteration
# i == index of last eaten element
# eaten elements of `a` are reset to 0
while m:i=a.index(m);a[i]=0;m=max(a[i+x]for x in[-6,-5,-4,-1,1,4,5,6])
print sum(a)

The adjacent-cell expression a[i+x]for x in[-6,-5,-4,-1,1,4,5,6] can be shortened to a[i+j+j/3*2-6]for j in range(9) (the zero entry is harmless). Python 3 can surely do shorter by hardcoding a length-8 bytestring, but Python 2 might still be better overall.

Though your zero padding loop is clever, it looks like it's shorter to take a 2D list: a=[0]*5 for r in input():a=r+[0]+a. Perhaps there's a yet shorter string slicing solution that doesn't require iterating.

MATL, 50 49 47 bytes
16:HZ^!"2G@m1ZIm~]v16eXK68E16b"Ky0)Y)fyX-X>h]s-

Input is a matrix, using ; as row separator.
Try it online! Or verify all test cases.
Explanation
16:HZ^!  % Cartesian power of [1 2 ... 16] with exponent 2, transpose. Gives a
         % 2-row matrix with 1st column [1; 1], 2nd [1; 2], ..., last [16; 16]
"        % For each column, say [k; j]
  2      %   Push 2
  G@m    %   Push input matrix, then current column [k; j], then check membership.
         %   This gives a 4×4 matrix that contains 1 for entries of the input that
         %   contain k or j
  1ZI    %   Connected components (based on 8-neighbourhood) of nonzero entries.
         %   This gives a 4×4 matrix with each connected component labeled with
         %   values 1, 2, ... respectively
  m~     %   True if 2 is not present in this matrix. That means there is only
         %   one connected component; that is, k and j are neighbours in the
         %   input matrix, or k=j
]        % End
v16e     % The stack now has 256 values. Concatenate them into a vector and
         % reshape as a 16×16 matrix. This matrix describes neighbourhood: entry
         % (k,j) is 1 if values k and j are neighbours in the input or if k=j
XK       % Copy into clipboard K
68E      % Push 68 times 2, that is, 136, which is 1+2+...+16
16       % Push 16. This is the initial value eaten by the mouse. New values will
         % be appended to create a vector of eaten values
b        % Bubble up the 16×16 matrix to the top of the stack
"        % For each column. This just executes the loop 16 times
  K      %   Push neighbourhood matrix from clipboard K
  y      %   Copy from below: pushes a copy of the vector of eaten values
  0)     %   Get last value. This is the most recent eaten value
  Y)     %   Get that row of the neighbourhood matrix
  f      %   Indices of nonzeros. This gives a vector of neighbours of the last
         %   eaten value
  y      %   Copy from below: pushes a copy of the vector of eaten values
  X-     %   Set difference (may give an empty result)
  X>     %   Maximum value. This is the new eaten value (maximum neighbour not
         %   already eaten). May be empty, if all neighbours are already eaten
  h      %   Concatenate to vector of eaten values
]        % End
s        % Sum of vector of all eaten values
-        % Subtract from 136. Implicitly display

Idk MatLab, but can you save a little if you push -136 instead of +136?

@Titus Hm I don't see how

or the other way round: I thought instead of 1) push 136 2) push each eaten value 3) sum up eaten values 4) subtract from 136 -> 1) push 136 2) push negative of eaten value 3) sum up stack. But as it obviously is only one byte each; it´s probably no gain.

@Titus Ah, yes, I think that uses the same number of bytes. Also, I need each eaten value (not its negative) for the set difference; negating would have to be done at the end

Python 2, 111 bytes
i=x=a=input()
while x:x,i=max((y,j)for j,y in enumerate(a)if i>[]or 2>i/4-j/4>-2<i%4-j%4<2);a[i]=0
print sum(a)

Try it online!
Method and test cases adapted from Bubbler. Takes a flat list on STDIN.
The code checks whether two flat indices i and j represent touching cells by checking that both row different i/4-j/4 and column difference i%4-j%4 are strictly between -2 and 2. The first pass instead has this check automatically succeed so that the largest entry is found disregarding adjacency.

PHP, 177 174 171 bytes
for($v=16;$v;$u+=$v=max($p%4-1?max($a[$p-5],$a[$p-1],$a[$p+3]):0,$a[$p-4],$a[$p+4],$p%4?max($a[$p-3],$a[$p+1],$a[$p+5]):0))$a[$p=array_search($v,$a=&$argv)]=0;echo 120-$u;

Run with -nr, provide matrix elements as arguments or try it online.

JavaScript, 122 bytes
I took more than a couple of wrong turns on this one and now I've run out of time for further golfing but at least it's working. Will revisit tomorrow (or, knowing me, on the train home this evening!), if I can find a minute.
a=>(g=n=>n?g([-6,-5,-4,-1,1,4,5,6].map(x=>n=a[x+=i]>n?a[x]:n,a[i=a.indexOf(n)]=n=0)|n)-n:120)(16,a=a.flatMap(x=>[...x,0]))

Try it online

+1 for flatMap() :p

:D I think this is the first time I've used it for golf! Out of interest (and to give me a target when I come back to this), what was your score when you tried it?

Didn't get a minute to come back to this today. Hopefully that means I'll be able to start over with completely fresh eyes tomorrow.

I've posted my solution.

R, 128 124 123 112 110 bytes
function(r){r=rbind(0,cbind(0,r,0),0)
m=r>15
while(r[m]){r[m]=0
m=r==max(r[which(m)+c(7:5,1)%o%-1:1])}
sum(r)}

Try it online!
It creates a 4x4 matrix (which helped me to visualize things), pads it with 0's, then begins from 16 and searches it's surrounding "piles" for the next largest, and so forth.
Upon conclusion, it does output a warning, but it is of no consequence and does not change the result.
EDIT: -4 bytes by compressing the initialization of the matrix into 1 line.
EDIT: -1 thanks to Robert Hacken
EDIT: -13 bytes combining Giuseppe and Robin Ryder's suggestions.

You can save one byte changing r==16 for r>15.

117 bytes -- change it to a function taking a matrix and do some aliasing with the which.

112 bytes improving upon @Giuseppe 's suggestions: you can store m as a logical instead of an integer, and thus only need to call which once instead of twice.

110 bytes using @RobinRyder 's golf and messing with compressing the neighborhood adjacency matrix.

@Giuseppe What in tarnation is %o% and how does it work?

@Sumner18 X%o%Y is an alias for outer(X,Y,'*'). outer is one of the handiest functions around as it can function as the "broadcast" feature of Octave/MATLAB/MATL with aribtrary (vectorized) operators. See here; also handy on rare occasions is kronecker which is linked in that page.

Powershell, 143 141 136 130 122 121 bytes
$a=,0*5+($args|%{$_+0})
for($n=16;$i=$a.IndexOf($n)){$a[$i]=0
$n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]}$a|%{$s+=$_}
$s

Less golfed test script:
$f = {

$a=,0*5+($args|%{$_+0})
for($n=16;$i=$a.IndexOf($n)){
    $a[$i]=0
    $n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]
}
$a|%{$s+=$_}
$s

}

@(
    ,( 0  , ( 4,  3,  2,  1), ( 5,  6,  7,  8), (12, 11, 10,  9), (13, 14, 15, 16) )
    ,( 0  , ( 8,  1,  9, 14), (11,  6,  5, 16), (13, 15,  2,  7), (10,  3, 12,  4) )
    ,( 1  , ( 1,  2,  3,  4), ( 5,  6,  7,  8), ( 9, 10, 11, 12), (13, 14, 15, 16) )
    ,( 3  , (10, 15, 14, 11), ( 9,  3,  1,  7), (13,  5, 12,  6), ( 2,  8,  4, 16) )
    ,( 12 , ( 3,  7, 10,  5), ( 6,  8, 12, 13), (15,  9, 11,  4), (14,  1, 16,  2) )
    ,( 34 , ( 8,  9,  3,  6), (13, 11,  7, 15), (12, 10, 16,  2), ( 4, 14,  1,  5) )
    ,( 51 , ( 8, 11, 12,  9), (14,  5, 10, 16), ( 7,  3,  1,  6), (13,  4,  2, 15) )
    ,( 78 , (13, 14,  1,  2), (16, 15,  3,  4), ( 5,  6,  7,  8), ( 9, 10, 11, 12) )
    ,( 102, ( 9, 10, 11, 12), ( 1,  2,  4, 13), ( 7,  8,  5, 14), ( 3, 16,  6, 15) )
    ,( 103, ( 9, 10, 11, 12), ( 1,  2,  7, 13), ( 6, 16,  4, 14), ( 3,  8,  5, 15) )
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"
}

Output:
True: 0
True: 0
True: 1
True: 3
True: 12
True: 34
True: 51
True: 78
True: 102
True: 103

Explanation:
First, add top and bottom borders of 0 and make a single dimensional array:
0 0 0 0 0
# # # # 0
# # # # 0
# # # # 0
# # # # 0

     ↓

0 0 0 0 0 # # # # 0 # # # # 0 # # # # 0 # # # # 0

Powershell returns $null if you try to get the value behind the end of the array.
Second, loop biggest neighbor pile started from 16 to non-zero-maximum. And nullify it (The Hungry Mouse eats it).
for($n=16;$i=$a.IndexOf($n)){
    $a[$i]=0
    $n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]
}

Third, sum of the remaining piles.

Haskell, 163 bytes
o f=foldl1 f.concat
r=[0..3]
q n=take(min(n+2)3).drop(n-1)
0#m=m
v#m=[o max$q y$q x<$>n|y<-r,x<-r,m!!y!!x==v]!!0#n where n=map(z<$>)m;z w|w==v=0|0<1=w
f=o(+).(16#)

Try it online!
The f function takes the input as a list of 4 lists of 4 integers.
Slightly ungolfed
-- helper to fold over the matrix
o f = foldl1 f . concat

-- range of indices
r = [0 .. 3]

-- slice a list (take the neighborhood of a given coordinate)
-- first we drop everything before the neighborhood and then take the neighborhood itself
q n = take (min (n + 2) 3) . drop (n - 1)

-- a step function
0 # m = m -- if the max value of the previous step is zero, return the map
v # m =
    -- abuse list comprehension to find the current value in the map
    -- convert the found value to its neighborhood,
    -- then calculate the max cell value in it
    -- and finally take the head of the resulting list
    [ o max (q y (q x<$>n)) | y <- r, x <- r, m!!y!!x == v] !! 0
       # n -- recurse with our new current value and new map
    where
        -- a new map with the zero put in place of the value the mouse currently sits on
        n = map (zero <$>) m
        -- this function returns zero if its argument is equal to v
        -- and original argument value otherwise
        zero w
            | w == v = 0
            | otherwise = w

-- THE function. first apply the step function to incoming map,
-- then compute sum of its cells
f = o (+) . (16 #)

Java 10, 272 248 239 237 bytes
m->{int r=0,c=0,R,C,M=16,x,y,X=0,Y=0;for(;M-->0;)if(m[M/4][M%4]>15)m[r=M/4][c=M%4]=0;for(;M!=0;m[r=X][c=Y]=0)for(M=0,C=9;C-->0;)try{if((R=m[x=r+C/3-1][y=c+C%3-1])>M){M=R;X=x;Y=y;}}finally{continue;}for(var Z:m)for(int z:Z)M+=z;return M;}

The cells are checked the same as in my answer for the All the single eights challenge.
-24 bytes thanks to @OlivierGrégoire.
-11 bytes thanks to @ceilingcat.
Try it online.
Explanation:
m->{                       // Method with integer-matrix parameter and integer return
  int r=0,                 //  Row-coordinate for the largest number, starting at 0
      c=0,                 //  Column-coordinate for the largest number, starting at 0
      R,C,                 //  Row and column indices (later reused as temp integers)
      M=16,                //  Largest number the mouse just ate, starting at 16
      x,y,X=0,Y=0;         //  Temp integers
  for(;M-->0;)             //  Loop `M` in the range (16, 0]:
    if(m[M/4][M%4]>15)     //   If the current cell is 16:
      m[r=M/4][c=M%4]      //    Set `r,c` to this coordinate
        =0;                //    And empty this cell
                           //  (after this first loop, `M` will be -1)
  for(;M!=0;               //  Loop as long as the largest number `M` isn't 0:
      ;                    //    After every iteration:
       m[r=X][c=Y]         //     Change the `r,c` coordinates,
         =0)               //     And empty this cell
    for(M=0,               //   Reset `M` to 0
        C=9;C-->0;)        //   Inner loop `C` in the range (9, 0]:
          try{if((R=       //    Set `R` to:
            m[x=r+C/3-1]   //     If `C` is 0, 1, or 2: Look at the previous row
                           //     Else-if `C` is 6, 7, or 8: Look at the next row
                           //     Else (`C` is 3, 4, or 5): Look at the current row
             [y=c+C%3-1])  //     If `C` is 0, 3, or 6: Look at the previous column
                           //     Else-if `C` is 2, 5, or 8: Look at the next column
                           //     Else (`C` is 1, 4, or 7): Look at the current column
               >M){        //    And if the number in this cell is larger than `M`
                 M=R;      //     Change `M` to this number
                 X=x;Y=y;} //     And change the `X,Y` coordinate to this cell
          }finally{continue;}
                           //    Catch and ignore ArrayIndexOutOfBoundsExceptions
                           //    (try-finally saves bytes in comparison to if-checks)
  for(var Z:m)             //  Then loop over all rows of the matrix:
    for(int z:Z)           //   Inner loop over all columns of the matrix:
      M+=z;                //    And sum them all together in `M` (which was 0)
  return M;}               //  Then return this sum as result

could you not to int r=c=X=Y=0,R=4,M=1,x,y; ?

@Serverfrog I'm afraid that's not possible when declaring the variables in Java. Your suggestion did give me an idea to save a byte though, by using int r,c,R=4,M=1,x,y,X,Y;for(r=c=X=Y=0;, so thanks. :)

Charcoal, 47 bytes
ＥＡ⭆ι§αλ≔QθＷ›θA«≔⌕ＫＡθθＪ﹪θ⁴÷θ⁴≔⌈ＫＭθA»≔ΣＥＫＡ⌕αιθ⎚Ｉθ

Try it online! Link is to verbose version of code. Explanation:
ＥＡ⭆ι§αλ

Convert the input numbers into alphabetic characters (A=0 .. Q=16) and print them as a 4x4 grid.
≔Qθ

Start by eating the Q, i.e. 16.
Ｗ›θA«

Repeat while there is something to eat.
≔⌕ＫＡθθ

Find where the pile is. This is a linear view in row-major order.
Ｊ﹪θ⁴÷θ⁴

Convert to co-ordinates and jump to that location.
≔⌈ＫＭθ

Find the largest adjacent pile.
A»

Eat the current pile.
≔ΣＥＫＡ⌕αιθ

Convert the piles back to integers and take the sum.
⎚Ｉθ

Clear the canvas and output the result.

JavaScript (ES7), 97 bytes
Takes input as a flattened array.
f=(a,s=p=136,m,d)=>a.map((v,n)=>v<m|(n%4-p%4)**2+(n-p)**2/9>d||(q=n,m=v))|m?f(a,s-m,a[p=q]=0,4):s

Try it online!
Commented
f = (                    // f= recursive function taking:
  a,                     // - a[] = flattened input array
  s =                    // - s = sum of cheese piles, initialized to 1 + 2 + .. + 16 = 136
      p = 136,           // - p = position of the mouse, initially outside the board
  m,                     // - m = maximum pile, initially undefined
  d                      // - d = distance threshold, initially undefined
) =>                     //
  a.map((v, n) =>        // for each pile v at position n in a[]:
    v < m |              //   unless this pile is not better than the current maximum
    (n % 4 - p % 4) ** 2 //   or (n % 4 - p % 4)²
    + (n - p) ** 2 / 9   //      + (n - p)² / 9
    > d ||               //   is greater than the distance threshold:
    (q = n, m = v)       //     update m to v and q to n
  )                      // end of map()
  | m ?                  // if we've found a new pile to eat:
    f(                   //   do a recursive call:
      a,                 //     pass a[] unchanged
      s - m,             //     update s by subtracting the pile we've just eaten
      a[p = q] = 0,      //     clear a[q], update p to q and set m = 0
      4                  //     use d = 4 for all next iterations
    )                    //   end of recursive call
  :                      // else:
    s                    //   stop recursion and return s

Yep, I never would have got anywhere close to that!

95

Julia, 133 127 bytes
*(A,S=136,I=keys(A))=((v,r,c)=maximum(i->(get(A,i,0),i[1],i[2]),I);S-=v;v>0 ? (A[r,c]=0;A*S*[(r+i,c+j) for i=-1:1,j=-1:1]) : S)
-6 bytes by @MarcMush, thx!
Attempt This Online!
readable version:
*(A,S=136,I=keys(A))=(
(v,r,c)=maximum(i->(get(A,i,0),i[1],i[2]),I);S-=v;
v>0 ? (A[r,c]=0;A*S*[(r+i,c+j) for i=-1:1,j=-1:1]) : S)

input: matrix (not a list of lists)
works for arbitrary shaped matrices with positive numbers in it - as long as the path taken by the mouse is uniquely determined by the numbers.
interesting math questions:

what is the expected outcome of this "game"? (i got a value (approx.) between 18.2 and 18.3 with simulation
what is the expected length of the path?

-3 bytes by using * instead of f

an additional -3 bytes with maximum(f,itr) ATO

SAS, 236 219 bytes
Input on punch cards, one line per grid (space-separated), output printed to the log.
This challenge is slightly complicated by some limitations of arrays in SAS:

There is no way to return the row and column indexes of a matching element from multidimensional data-step array - you have to treat the array as 1-d and then work them out for yourself.
If you go out of bounds, SAS throws an error and halts processing rather than returning null / zero.

Updates:

Removed infile cards; statement (-13)
Used wildcard a: for array definition rather than a1-a16 (-4)

Golfed:
data;input a1-a16;array a[4,4]a:;p=16;t=136;do while(p);m=whichn(p,of a:);t=t-p;j=mod(m-1,4)+1;i=ceil(m/4);a[i,j]=0;p=0;do k=max(1,i-1)to min(i+1,4);do l=max(1,j-1)to min(j+1,4);p=max(p,a[k,l]);end;end;end;put t;cards;
    <insert punch cards here>
    ;

Ungolfed:
data;                /*Produce a dataset using automatic naming*/
input a1-a16;        /*Read 16 variables*/
array a[4,4] a:;     /*Assign to a 4x4 array*/
p=16;                /*Initial pile to look for*/
t=136;               /*Total cheese to decrement*/
do while(p);         /*Stop if there are no piles available with size > 0*/
  m=whichn(p,of a:); /*Find array element containing current pile size*/
  t=t-p;             /*Decrement total cheese*/
  j=mod(m-1,4)+1;    /*Get column number*/
  i=ceil(m/4);       /*Get row number*/
  a[i,j]=0;          /*Eat the current pile*/
                     /*Find the size of the largest adjacent pile*/
  p=0;
  do k=max(1,i-1)to min(i+1,4);
    do l=max(1,j-1)to min(j+1,4);
      p=max(p,a[k,l]);
    end;
  end;
end;
put t;              /*Print total remaining cheese to log*/
                    /*Start of punch card input*/
cards;
  4  3  2  1  5  6  7  8 12 11 10  9 13 14 15 16
  8  1  9 14 11  6  5 16 13 15  2  7 10  3 12  4
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
 10 15 14 11  9  3  1  7 13  5 12  6  2  8  4 16
  3  7 10  5  6  8 12 13 15  9 11  4 14  1 16  2
  8  9  3  6 13 11  7 15 12 10 16  2  4 14  1  5
  8 11 12  9 14  5 10 16  7  3  1  6 13  4  2 15
 13 14  1  2 16 15  3  4  5  6  7  8  9 10 11 12
  9 10 11 12  1  2  4 13  7  8  5 14  3 16  6 15
  9 10 11 12  1  2  7 13  6 16  4 14  3  8  5 15
;                    /*End of punch card input*/
                     /*Implicit run;*/

+1 for use of punch cards in PPCG :)

APL (Dyalog Unicode), 42 41 bytesSBCS
16{×⍺:a∇⍨+/,m×⌈/⌈/⊢⌺3 3⊢a←⍵×~m←⍺=⍵⋄+/,⍵}⊢

Try it online!

Jelly,  31 30  29 bytes
³œiⱮZIỊȦ
⁴ṖŒPŒ!€Ẏ⁴;ⱮṢÇƇṪ
FḟÇS

Since the method is far too slow to run within 60s with the mouse starting on 16 this starts her off at 9 and limits her ability such that she is only able to eat 9s or less Try it online! (thus here she eats 9, 2, 7, 4, 8, 6, 3 leaving 97).
How?
³œiⱮZIỊȦ - Link 1, isSatisfactory?: list of integers, possiblePileChoice
³        - (using a left argument of) program's 3rd command line argument (M)
   Ɱ     - map across (possiblePileChoice) with:
 œi      -   first multi-dimensional index of (the item) in (M)
    Z    - transpose the resulting list of [row, column] values
     I   - get the incremental differences
      Ị  - insignificant? (vectorises an abs(v) <= 1 test)
       Ȧ - any and all? (0 if any 0s are present in the flattened result [or if it's empty])

⁴ṖŒPŒ!€Ẏ⁴;ⱮṢÇƇṪ - Link 2, getChosenPileList: list of lists of integers, M
⁴               - literal 16
 Ṗ              - pop -> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
  ŒP            - power-set -> [[],[1],[2],...,[1,2],[1,3],...,[2,3,7],...,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]]
      €         - for each:
    Œ!          -   all permutations
       Ẏ        - tighten (to a single list of all these individual permutations)
        ⁴       - (using a left argument of) literal 16
          Ɱ     - map across it with:
         ;      -   concatenate (put a 16 at the beginning of each one)
           Ṣ    - sort the resulting list of lists
             Ƈ  - filter keep those for which this is truthy:
            Ç   -   call last Link as a monad (i.e. isSatisfactory(possiblePileChoice)
              Ṫ - tail (get the right-most, i.e. the maximal satisfactory one)

FḟÇS - Main Link: list of lists of integers, M
F    - flatten M
  Ç  - call last Link (2) as a monad (i.e. get getChosenPileList(M))
 ḟ   - filter discard (the resulting values) from (the flattened M)
   S - sum

Ah yeah, power-set is not enough!

@Arnauld - finally got a little time to golf :D This should work, but will be (way) too slow for running at TIO with the test case you used before.

Could the down-voter please give some feedback? This works, has a full and clear explanation, and is also the shortest entry at the present time.

I upvoted, but given the O((n^2)!) of this answer I wish the challenge had required polynomial time.

J, 82 bytes
g=.](]*{:@[~:])]_1}~[:>./]{~((,-)1 5 6 7)+]i.{:
[:+/[:(g^:_)16,~[:,0,~0,0,0,.~0,.]

Try it online!
I plan to golf this more tomorrow, and perhaps write a more J-ish solution similar to this one, but I figured I'd try the flattened approach since I hadn't done that before.

Do you really need the leftmost ] in g?

Thanks Galen, you're right.  It's the least of the issues with this code :) I have a much better solution which I'll implement when I have time.

Red, 277 bytes
func[a][k: 16 until[t:(index? find load form a k)- 1
p: do rejoin[t / 4 + 1"x"t % 4 + 1]a/(p/1)/(p/2): 0
m: 0 foreach d[-1 0x-1 1x-1 -1x0 1x0 -1x1 0x1 1][j: p + d
if all[j/1 > 0 j/1 < 5 j/2 > 0 j/2 < 5 m < t: a/(j/1)/(j/2)][m: t]]0 = k: m]s: 0
foreach n load form a[s: s + n]s]

Try it online!
It's really long solution and I'm not happy with it, but I spent so much time fixing it to work in TIO (apparently there are many differences between the Win and Linux stable versions of Red), so I post it anyway...
More readable:
f: func [ a ] [
    k: 16
    until [
        t: (index? find load form a n) - 1
        p: do rejoin [ t / 4 + 1 "x" t % 4 + 1 ]
        a/(p/1)/(p/2): 0
        m: 0
        foreach d [ -1 0x-1 1x-1 -1x0 1x0 -1x1 0x1 1 ] [
            j: p + d
            if all[ j/1 > 0
                    j/1 < 5
                    j/2 > 0
                    j/2 < 5
                    m < t: a/(j/1)/(j/2)
            ] [ m: t ]
        ]
        0 = k: m
    ]
    s: 0
    foreach n load form a [ s: s + n ]
    s
]

Not my best work.  There's some definite improvements to be done, some probably fundamental to the algorithm used -- I'm sure it can be improved by using only an int[], but I couldn't figure out how to efficiently enumerate neighbors that way.  I'd love to see a PowerShell solution that uses only a single dimensional array!
PowerShell Core, 348 bytes
Function F($o){$t=120;$a=@{-1=,0*4;4=,0*4};0..3|%{$a[$_]=[int[]](-join$o[(3+18*$_)..(3+18*$_+13)]-split',')+,0};$m=16;while($m-gt0){0..3|%{$i=$_;0..3|%{if($a[$i][$_]-eq$m){$r=$i;$c=$_}}};$m=($a[$r-1][$c-1],$a[$r-1][$c],$a[$r-1][$c+1],$a[$r][$c+1],$a[$r][$c-1],$a[$r+1][$c-1],$a[$r+1][$c],$a[$r+1][$c+1]|Measure -Max).Maximum;$t-=$m;$a[$r][$c]=0}$t}

Try it online!

More readable version:
Function F($o){
    $t=120;
    $a=@{-1=,0*4;4=,0*4};
    0..3|%{$a[$_]=[int[]](-join$o[(3+18*$_)..(3+18*$_+13)]-split',')+,0};
    $m=16;
    while($m-gt0){
        0..3|%{$i=$_;0..3|%{if($a[$i][$_]-eq$m){$r=$i;$c=$_}}};
        $m=($a[$r-1][$c-1],$a[$r-1][$c],$a[$r-1][$c+1],$a[$r][$c+1],$a[$r][$c-1],$a[$r+1][$c-1],$a[$r+1][$c],$a[$r+1][$c+1]|Measure -Max).Maximum;
        $t-=$m;
        $a[$r][$c]=0
    }
    $t
}

334 bytes after simple restructuring

Oh yeah, weird thing I noticed is that trying to do the (array|sort)[-1] instead of Measure -max worked in PSv5 but was getting incorrect results in core. No idea why.

Yeah, that's weird.  I tested it on (0..10|sort)[-1] but it returns 10 on PSv5 but 9 on PS Core.  This is because it treats it in lexicographical order instead of numeric.  Shame, that.

Classic Microsoft changing the important things.

I agree in this case.  I'm not sure why PS Core Sort throws an array of int32 to an array of strings.  But, this is straying into a rant, so I'll digress.  Thanks for the restructure!

C (gcc), 250 bytes
x;y;i;b;R;C;
g(int a[][4],int X,int Y){b=a[Y][X]=0;for(x=-1;x&lt2++x)for(y=-1;y<2;++y)if(!(x+X&~3||y+Y&~3||a[y+Y][x+X]<b))b=a[C=Y+y][R=X+x];for(i=x=0;i<16;++i)x+=a[0][i];return b?g(a,R,C):x;}
s(int*a){for(i=0;i<16;++i)if(a[i]==16)return g(a,i%4,i/4);}

Try it online!
Note: This submission modifies the input array.
s() is the function to call with an argument of a mutable int[16] (which is the same in-memory as an int[4][4], which is what g() interprets it as).
s() finds the location of the 16 in the array, then passes this information to g, which is a recursive function that takes a location, sets the number at that location to 0, and then:

If there is a positive number adjacent to it, recurse with the location of the largest adjacent number

Else, return the sum of the numbers in the array.

s(int*a){for(i=0;a[i]<16;++i);return g(a,i%4,i/4);}

if g returns sum of eaten you don't need to calculate sum in it. Just return 16*17/2-g() at the end of s

can you use bitwise or instead if logical or?

211 bytes

Wolfram Language (Mathematica), 149 bytes
(g@p_:=#&@@Position[s,Max@p];m=g[s=#];While[Tr[b=s[[##]]&@@#&/@Select[#+m&/@Tuples[{-1,0,1},2],Max@#<5&&Min@#>0&]]>0,m=g@b;s[[##&@@m]]=0];Tr[Tr/@s])&

Try it online!

Add++, 281 bytes
D,f,@@,VBFB]G€=dbLRz€¦*bMd1_4/i1+$4%B]4 4b[$z€¦o
D,g,@@,c2112011022200200BD1€Ω_2$TAVb]8*z€kþbNG€lbM
D,k,@~,z€¦+d4€>¦+$d1€<¦+$@+!*
D,l,@@#,bUV1_$:G1_$:
D,h,@@,{l}A$bUV1_$:$VbU","jG$t0€obU0j","$t€iA$bUpVdbLRG€=€!z€¦*$b]4*$z€¦o
y:?
m:16
t:120
Wm,`x,$f>y>m,`m,$g>x>y,`y,$h>x>y,`t,-m
Ot

Try it online!
Oof, this is a complicated one.
Verify all test cases
How it works
For this explanation, we will use the input
\$M = \left[\begin{matrix}
3 & 7 & 10 & 5 \\
6 & 8 & 12 & 13 \\
15 & 9 & 11 & 4 \\
14 & 1 & 16 & 2 \\
\end{matrix}\right]\$
We start by defining a series of helper functions. We will use \$x\$ to represent an integer such that \$1 \le x \le 16\$, \$M\$ to, initially, represent the \$4\text{x}4\$ input matrix. The functions are:

\$f(x, M)\$: Given a value and a \$4\text{x}4\$ matrix, return the co-ordinates of \$x\$ in \$M\$ e.g. if \$x = 16\$ and \$M\$ is above, \$f(x, M) = (4, 3)\$
\$g(M, y)\$: Given a matrix and two co-ordinates, return the largest of the neighbours of the value at that point e.g. using \$f(x, M)\$ from above, \$g(M, f(x, M)) = 11\$
This implements the two helper functions:
\$k(x)\$ which removes any co-ordinates which would wrap around or be out of bounds
\$l(M, y)\$ which, given a matrix and co-ordinates, returns the value at those co-ordinates
\$h(y, M)\$ which, given a matrix and co-ordinates, sets the value at those indexes to \$0\$

After these functions are defined, we come to the main body of the program. The first step is to assign the four variables, x, y, m and t. x is set to \$0\$ by default, y to the input, m to \$16\$ (the first value to search for) and t to \$120 \: (1 + 2 + \cdots + 14 + 15)\$.
Next, we enter a while loop, that loops while m does not equal \$0\$. The steps in the loop go something along the lines of
While m \$\neq 0\$:

Set x to \$f(\textbf{y}, \textbf{m})\$. For the first iteration, this sets x to the co-ordinates of \$16\$ is \$M\$ (\$x := (4, 3)\$ in our example)
Set m to \$g(\textbf{x}, \textbf{y})\$. This yields the largest new neighbour to m, or \$0\$, if there are no new neighbours (which ends the while loop).
Set y to \$h(\textbf{x}, \textbf{y})\$. This sets the previous value of m (\$16\$ in the first iteration) to \$0\$, in order for the previous step to work
Set t to \$\textbf{t} - \textbf{m}\$, removing that value from the total value amount.

Finally, output t, i.e. the remaining, non collected values.

C# (.NET Core), 258 bytes
Without LINQ.  The using System.Collections.Generic is for the formatting after - the function doesn't require it.
e=>{int a=0,b=0,x=0,y=0,j=0,k;foreach(int p in e){if(p>15){a=x=j/4;b=y=j%4;}j++;}e[x,y]=0;while(1>0){for(j=-1;j<2;j++)for(k=-1;k<2;k++){try{if(e[a+k,b+j]>e[x,y]){x=a+k;y=b+j;}}catch{}}if(e[x,y]<1)break;e[x,y]=0;a=x;b=y;}a=0;foreach(int p in e)a+=p;return a;}

Try it online!

Perl 6, 151 136 126 125 119 bytes
{my@k=$_;my $a=.grep(16,:k)[0];while @k[$a] {@k[$a]=0;$a=^@k .grep({2>$a+>2-$_+>2&$a%4-$_%4>-2}).max({@k[$_]})};[+] @k}

Super shabby solution. Takes input as flattened array.
Try it online!

Perl 5 -MList::Util=sum -p, 137 bytes
splice@F,$_,0,0for 12,8,4;map{$k{++$,}=$_;$n=$,if$_&16}@F;map{map{$n=$_+$"if$k{$"+$_}>$k{$n}&&!/2|3/}-6..6;$k{$"=$n}=0}@F;$_=sum values%k

Try it online!

K (ngn/k), 49 bytes
{{h[,x]:0;*>(+x+0,'1-!3 3)#h}\*>h::(+!4 4)!x;+/h}

Try it online!
the input (x) is a 1d array
(+!4 4)!x a dictionary that maps pairs of coords to the values of x
h:: assign to a global variable h
*> the key corresponding to the max value
{ }\ repeat until convergence, collecting intermediate values in a list
h[,x]:0 zero out the current position
+x+0,'1-!3 3 neighbour positions
( )#h filter them from h as a smaller dictionary
*> which neighbour has the max value? it becomes the current position for the new iteration
+/h finally, return the sum of h's remaining values

Wolfram Language (Mathematica), 124 115 bytes
(p=#&@@Position[m=Join@@ArrayPad[#,1],16];Do[m[[p]]=0;p=MaximalBy[#&@@p+{0,-1,1,-5,5,-6,6,-7,7},m[[#]]&],16];Tr@m)&

Try it online!
This takes a 2D array, pads it on each side, then immediately flattens it so we don't have to spend bytes indexing. The only cost to this is Join@@ to flatten. Afterwards it proceeds as below.
124-byte version for a 2D array: Try it online!
Mostly my own work, with a bit derived from J42161217's 149-byte answer.
Ungolfed:
(p = #& @@ Position[m = #~ArrayPad~1,16];     m = input padded with a layer of 0s
                                              p = location of 16
Do[
    m = MapAt[0&,m,p];                        Put a 0 at location p
    p = #& @@ MaximalBy[                      Set p to the member of
        p+#& /@ Tuples[{0,-1,1},2],             {all possible next locations}
        m~Extract~#&],                        that maximizes that element of m,
                                              ties broken by staying at p+{0,0}=p.
16];                                        Do this 16 times.
Tr[Tr/@m]                                   Finally, output the sum of m.
)&

Not the shortest solution, but pretty straight forward.
Ruby, 207
a=eval(ARGV[0])
n=16
while n!=0 do
a[i=a.index(n)]=0
t=[a[i+4]]
t<<a[i-4]if i>3
if i%4!=0
t<<a[i-5]if i>3
t<<a[i-1]
t<<a[i+3]
end
if i%4!=3
t<<a[i+1]
t<<a[i+5]
t<<a[i-3]if i>3
end
n=t.compact.max
end
p a.sum


text:
Is it an arithmetico-geometric sequence?
An arithmetico-geometric sequence is the elementwise product of an arithmetic sequence and a geometric sequence. For example, 1 -4 12 -32 is the product of the arithmetic sequence 1 2 3 4 and the geometric sequence 1 -2 4 -8. The nth term of an integer arithmetico-geometric sequence can be expressed as
$$a_n = r^n \cdot (a_0 + nd)$$
for some real number \$d\$, nonzero real \$r\$, and integer \$a_0\$. Note that \$r\$ and \$d\$ are not necessarily integers.
For example, the sequence 2 11 36 100 256 624 1472 3392 has \$a_0 = 2\$, \$r = 2\$, and \$d = 3.5\$.
Input
An ordered list of \$n \ge 2\$ integers as input in any reasonable format. Since some definitions of geometric sequence allow \$r=0\$ and define \$0^0 = 1\$, whether an input is an arithmetico-geometric sequence will not depend on whether \$r\$ is allowed to be 0. For example, 123 0 0 0 0 will not occur as input.
Output
Whether it is an arithmetico-geometric sequence. Output a truthy/falsy value, or two different consistent values.
Test cases
True:
1 -4 12 -32
0 0 0
-192 0 432 -1296 2916 -5832 10935 -19683
2 11 36 100 256 624 1472 3392
-4374 729 972 567 270 117 48 19
24601 1337 42
0 -2718
-1 -1 0 4 16
2 4 8 16 32 64
2 3 4 5 6 7
0 2 8 24

False:
4 8 15 16 23 42
3 1 4 1
24601 42 1337
0 0 0 1
0 0 1 0 0
1 -1 0 4 16

FYI you can use inline math mode with \$ to write things like $ a_{0} $.

Are two-term inputs indeed possible? There aren't any in the test cases.

@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy

@user202729 Thanks

Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1

1 -1 0 4 16 would be a useful False case, since it shares four consecutive elements with each of the True cases 1 -1 0 4 -16 and -1 -1 0 4 16.

Wolfram Language (Mathematica), 55 bytes
{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&

Try it online!
Solve return all solution forms. The result is compared with {} to check if there is any solution.

Perl 6, 184 128 135 bytes
{3>$_||->\x,\y,\z{?grep ->\r{min (x,{r&&r*$_+(y/r -x)*($×=r)}...*)Z==$_},x??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1!!y&&z/y/2}(|.[^3])}

Try it online!
Computes \$r\$ and \$d\$ from the first three elements and checks whether the resulting sequence matches the input. Unfortunately, Rakudo throws an exception when dividing by zero, even when using floating-point numbers, costing ~9 bytes.
Enumerates the sequence using \$a_n=r \cdot a_{n-1}+r^n \cdot d\$.
Some improvements are inspired by Arnauld's JavaScript answer.
Explanation
3>$_||  # Return true if there are less than three elements

->\x,\y,\z{ ... }(|.[^3])}  # Bind x,y,z to first three elements

# Candidates for r
x  # If x != 0
??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1  # then solutions of quadratic equation
!!y&&z/y/2  # else solution of linear equation or 0 if y==0

?grep ->\r{ ... },  # Is there an r for which the following is true?

    ( ,                         ...*)  # Create infinite sequence
     x  # Start with x
       {                       }  # Compute next term
        r&&  # 0 if r==0
                (y/r -x)  # d
           r*$_  # r*a(n-1)
                          ($×=r)  # r^n
                +        *  # r*a(n-1)+d*r^n
                                     Z==$_  # Compare with each element of input
min  # All elements are equal?

JavaScript (ES7), 135 127 bytes
a=>!([x,y,z]=a,1/z)|!a.some(n=>n)|[y/x+(d=(y*y-x*z)**.5/x),y/x-d,z/y/2].some(r=>a.every((v,n)=>(v-(x+n*y/r-n*x)*r**n)**2<1e-9))

Try it online!
How?
We use two preliminary tests to get rid of some special cases. For the main case, we try three different possible values of \$r\$ (and the corresponding values of \$d\$, which can be easily deduced) and test whether all terms of the input sequence are matching the guessed ones. Because of potential rounding errors, we actually test whether all squared differences are \$<10^{-9}\$.
Special case #1: less than 3 terms
If there are less than 3 terms, it's always possible to find a matching sequence. So we force a truthy value.
Special case #2: only zeros
If all terms are equal to \$0\$, we can use \$a_0=0\$, \$d=0\$ and any \$r\neq 0\$. So we force a truthy value.
Main case with \$a_0=0\$
If \$a_0=0\$, the sequence can be simplified to:
$$a_n=r^n\times n\times d$$
Which gives:
$$a_1=r\times d\\
a_2=2r^2\times d$$
We know that \$d\$ is not equal to \$0\$ (otherwise, we'd be in the special case #2). So we have \$a_1\neq 0\$ and:
$$r=\frac{a_2}{2a_1}$$
Main case with \$a_0\neq 0\$
We have the following relation between \$a_{n+1}\$ and \$a_n\$:
$$a_{n+1}=r.a_n+r^{n+1}d$$
For \$a_{n+2}\$, we have:
$$\begin{align}a_{n+2}&=r.a_{n+1}+r^{n+2}d\\
&=r(r.a_n+r^{n+1}d)+r^{n+2}d\\
&=r^2a_n+2r.r^{n+1}d\\
&=r^2a_n+2r(a_{n+1}-r.a_n)\\
&=-r^2a_n+2r.a_{n+1}
\end{align}$$
We notably have:
$$a_2=-r^2a_0+2r.a_1$$
Leading to the following quadratic:
$$r^2a_0-2r.a_1+a_2=0$$
Whose roots are:
$$r_0=\frac{a_1+\sqrt{{a_1}^2-a_0a_2}}{a_0}\\
r_1=\frac{a_1-\sqrt{{a_1}^2-a_0a_2}}{a_0}$$

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Arbitrary Randomness
Randomness is fun. Challenges with no point are fun.
Write a function that, given integer input n, will output a set (unordered, unique) of exactly n random integers between 1 and n^2 (inclusive) such that the sum of all integers is equal to n^2.
Randomness does not have to be uniform, provided each valid set has a non-zero chance to occur.
Shortest answer in bytes (per each language) wins.
Examples
Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1

Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3

Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2

Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4

Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8

Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1

Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?

Sandbox

related, but quite different

Are we also allowed to output all possible output-sets?

@KevinCruijssen This defeats the "randomness" element of the challenge, so no. You must output a single random set.

(p/s: If you have a fast algorithm but takes more bytes, consider waiting until the speed edition (currently in sandbox) to post it.)

Do the elements of the chosen set need to be in a random order as well?

@Sok a set is unordered, so the order of the elements is irrelevant to the challenge

@EriktheOutgolfer Although there are (much) better ways than generating all sets and pick a random one, they're much harder to implement and likely longer. Keep them for the speed edition.

@user202729 yeah when it comes to the really golfy languages like 05AB1E and Jelly, I can definitely see generating all possible sets and picking one at random being golfier than brute forcing as I did in C#

The number of sets is OEIS A107379.

@nwellnhof no it isn't, that's the number of ways to express n^2 as the sum of n odd numbers

It's both. See the comment "Also the number of partitions of n^2 into n distinct parts."

@nwellnhof oh so it is, that's neat

Could I return a set with the correct result, but an additional 0 in it that we ignore, as long as every single result my program returns consistently has that added 0?

@Skidsdev For clarity,  "Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?" necessarily renders generating or filtering "Arbitrary Randomness" moot, correct? Is that the intention of the bonus?

@guest271314 the Bonus task is just a tongue in cheek extra question. It's not part of the challenge, no additional reward will be offered for solving the bonus task, I was just curious if there was a way to reliably calculate how many permutations there are for any n. IE a formula in which any n can be passed and it will return the number of valid permutations. Somebody else already answered the bonus task anyway, so my curiosity has been sated.

@KevinCruijssen No, because then the set would not contain exactly n elements

@Skidsdev What is the origin and meaning of the term "tongue in cheek"? Can you edit the question to include " the Bonus task is just a tongue in cheek extra question. It's not part of the challenge, no additional reward will be offered for solving the bonus task, I was just curious if there was a way to reliably calculate how many permutations there are for any n"?

@guest271314 it would've taken you 5 seconds to google and find this. Also it's generally assumed on PPCG that unless a "bonus" lists a reward, it is not part of the main challenge, and as with all StackExchange sites, any answer must answer the main question/challenge of the post. If you want to answer the bonus task as well go ahead, but your posted answer must be an answer to the main challenge for it to be valid as an answer.

Brachylog (v2), 15 bytes (random) or 13 bytes (all possibilities)
Random
~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Try it online!
Function submission (seen in TIO with a wrapper making it into a full program).
Explanation
~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

All possibilities
~lℕ₁ᵐ<₁.+√?∧≜

Try it online!
Function submission, which generates all possible outputs.
Explanation
~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

I'm fairly surprised that ∧≜ works (you'd normally have to write ∧~≜ in order to brute-force the output rather than the input), but it turns out that ≜ has an input=output assumption so it doesn't matter which way round you run it.
Bonus task
In order to get some insight into the sequence of the number of possibilities, I created a different TIO wrapper which runs the program on successive integers to give the sequence of output counts:
1,1,3,9,30,110,436,1801,7657,33401

A trip to OEIS discovers that this is already a known sequence, A107379, described pretty much as in the question (apparently you get the same sequence if you restrict it to odd numbers). The page lists several formulas for the sequence (although none is particularly simple; the second looks like a direct formula for the value but I don't understand the notation).

The second formula is "the coefficient of x^(n*(n-1)/2) in the series expansion of Product_{k=1..n} 1/(1 - x^k)" (not direct at all, unfortunately)

Placing the "all different" constraint before the random labelization step (e.g. A≠≜₁ᵐ) makes the run time much faster on average.

I don't understand why you made this a community wiki. Those are an archaic way to have editable posts before it was possible to edit.

@pipe https://codegolf.stackexchange.com/questions/172716/true-color-code/172776#comment416826_172776

05AB1E, 11 bytes
nÅœʒDÙQ}sùΩ

Try it online or verify all test cases.
Explanation:
n             # Take the square of the (implicit) input
              #  i.e. 3 → 9
 Åœ           # Get all integer-lists using integers in the range [1, val) that sum to val
              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]
   ʒ   }      # Filter the list to only keep lists with unique values:
    D         # Duplicate the current value
     Ù        # Uniquify it
              #  i.e. [2,2,5] → [2,5]
      Q       # Check if it's still the same
              #  i.e. [2,2,5] and [2,5] → 0 (falsey)
        s     # Swap to take the (implicit) input again
         ù    # Only leave lists of that size
              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3
              #   → [[1,2,6],[1,3,5],[2,3,4]]
          Ω   # Pick a random list from the list of lists (and output implicitly)

R, 68, 75 48 bytes (random) and 70 bytes (deterministic)
@Giuseppe's rejection sampling method:
function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Try it online!
Golfed original:
function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Try it online!
The *!!1:2 business is to avoid the odd way sample act when the first argument has length 1.

@Giuseppe "fixed" :-)

very nice. using p directly as an index instead of calculating it and re-using it should save some bytes.

I have function(n){while(sum(F)!=n^2)F=sample(n^2,n);F} for 48 as well...

@Giuseppe are we allowed programs that only terminate with probability 1?

I believe so. I'll try to find the right meta answer for ya.

@Giuseppe I couldn't find anything in meta so I've posted a question there.

What's the purpose of that rep call, @ngm?

@J.Doe to avoid the issue when calling something like sample(2,1) which happens with n=2. So rep just guarantees that this will never happen. There might be a better way but this was quick and I was mad at sample.

You can save a byte with x*!!1:2 over rep(x,2) if your meta question gets a no.

Python (2 or 3), 85 bytes
def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)
from random import*

Try it online!

Jelly, 9 bytes
²œcS=¥Ƈ²X

Try it online!
Generate all n-combinations of the list [1..n²], filter to keep those with sum n², then pick a random one.

Java 10, 250 242 222 bytes
import java.util.*;n->{for(;;){int i=n+1,r[]=new int[i],d[]=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

-20 bytes thanks to @nwellnhof.
Watch out, Java coming through.. It's 'only' five times as long as the other four answers combined, so not too bad I guess.. rofl.
It does run n=1 through n=25 (combined) in less than 2 seconds though, so I'll probably post a modified version to the speed version of this challenge (that's currently still in the Sandbox) as well.
Try it online.
Explanation:
In pseudo-code we do the following:
1) Generate an array of size n+1 containing: 0, n squared, and n-1 amount of random integers in the range [0, n squared)
2) Sort this array
3) Create a second array of size n containing the forward differences of pairs
These first three steps will give us an array containing n random integers (in the range [0, n squared) that sum to n squared.
4a) If not all random values are unique, or any of them is 0: try again from step 1
4b) Else: return this differences array as result
As for the actual code:
import java.util.*;      // Required import for HashSet and Arrays
n->{                     // Method with int parameter and Set return-type
  for(;;){               //  Loop indefinitely
    int i=n+1,           //   Set `i` to `n+1`
        r[]=new int[i];  //   Create an array of size `n+1`
    var S=new HashSet(); //   Result-set, starting empty
    for(r[n<2?           //   If `n` is 1:
           0             //    Set the first item in the first array to:
          :              //   Else:
           1]            //    Set the second item in the first array to:
             =n*n;       //   `n` squared
        i-->2;)          //   Loop `i` in the range [`n`, 2]:
      r[i]=              //    Set the `i`'th value in the first array to:
           (int)(Math.random()*n*n);
                         //     A random value in the range [0, `n` squared)
    for(Arrays.sort(r),  //   Sort the first array
        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:
      S.add(             //    Add to the Set:
        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array
    if(!S.contains(0)    //   If the Set does not contain a 0
       &S.size()==n)     //   and its size is equal to `n`:
      return S;}}        //    Return this Set as the result
                         //   (Implicit else: continue the infinite loop)

n=25 in under 2 seconds is impressive! I'll have to read through the explanation and see how it does it. Is it still a bruteforce method?

Is it uniform? -

@user202729 Although I'm not sure how to prove it, I think it is. The Java builtin is uniform, and it uses that to get random values in the range [0, n squared) first, and then calculates the differences between those sorted random values (including leading 0 and trailing n squared. So I'm pretty sure those differences are uniform as well. But again, I'm not sure how to prove it. Uniformity in randomness isn't really my expertise tbh.

@Skidsdev The generating of the list of n random values that sum to n squared is not bruteforce. But after that I check if the resulting list contains no zeros and if all integers are unique, and if not try again, so that part is bruteforce.

Oh yeah, make sure it's provably uniform if you wanna post it for the fastest-code challenge as well. This one doesn't require uniformity, but that one does.

@Skidsdev I know. Will have to dive in a bit more later. As I mentioned above, I'm pretty sure it is uniform, but I'm not 100% sure. But for the speed challenge I'll try again, because there are definitely performance changes to make that would make the code even longer (but faster), which isn't suitable for a [code-golf] challenge.

You never read from the differences array d or am I missing something?

@nwellnhof Woops.. lol. Thanks for letting me know! I had two arrays, but then I used the set to check that all values are unique. Didn't realize I didn't use d at all anymore..

I'm kind of happy with my 127 bytes solution :D

@OlivierGrégoire Ah nice. Much better than my solution. I guess mine is more suitable for the speed version of this challenge. I'm working on finishing up that answer between work today. :)

Perl 6, 41 bytes
{first *.sum==$_²,(1..$_²).pick($_)xx*}

Try it online!

(1 .. $_²) is the range of numbers from 1 to the square of the input number
.pick($_) randomly chooses a distinct subset of that range
xx * replicates the preceding expression infinitely
first *.sum == $_² selects the first of those number sets that sums to the square of the input number

40 bytes

Pyth, 13 12 bytes
Ofq*QQsT.cS*

Try it online here. Note that the online interpreter runs into a MemoryError for inputs greater than 5.
Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())
                 Trailing QQQ inferred
          S*QQQ   [1-Q*Q]
        .c    Q   All combinations of the above of length Q, without repeats
 f                Keep elements of the above, as T, where the following is truthy:
      sT            Is the sum of T...
  q                 ... equal to...
   *QQ              ... Q*Q?
O                 Choose a random element of those remaining sets, implicit print

Edit: saved a byte by taking an alternative approach. Previous version: Of&qQlT{IT./*

Python 3, 136 134 127 121 114 bytes
from random import*
def f(n):
	s={randint(1,n*n)for _ in range(n)}
	return len(s)==n and sum(s)==n*n and s or f(n)

Try it online!
A commenter corrected me, and this now hits recursion max depth at f(5) instead of f(1). Much closer to being a real competing answer.
I've seen it do f(5) once, and I'm working on trying to implement this with shuffle.
I tried making some lambda expressions for s=..., but that didn't help on bytes. Maybe someone else can do something with this:
s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)
Thanks to Kevin for shaving off another 7 bytes.

So this uses recursion to "regenerate" the set if the one generated is invalid? Definitely something wrong with your code if it's hitting recursion depth at f(1), the only possible array that should be generable at n=1 is [1]
Also there's a lot of extraneous whitespace to be removed here. Remember this is a code-golf challenge, so the goal is to achieve the lowest bytecount

range(1,n) -> range(n) I believe should resolve the bug.

This should fix your bug, and also removes extraneous whitespace. I imagine there's a lot more room for golfing too

@Skidsdev Thanks for reminding me on the whitespace, i've been copypasting from my IDLE window.

Although the recursion slightly worsens from 5 to 4, you can combine your two return statements like this: return len(s)==n and sum(s)==n*n and s or f(n) (Try it online 114 bytes).

You can have it all on one line. 111 bytes

APL (Dyalog Unicode), 20 bytesSBCS
Anonymous prefix lambda.
{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

Try it online!
{…} "dfn"; ⍵ is argument
 ⍵*2 square the argument
 s← assign to s (for square)
 ⍵? find n random indices from 1…s without replacement
 c← assign to c (for candidate)
 +/ sum them
 s= compare to s
 : if equal
  c return the candidate
 ⋄ else
  ∇⍵ recurse on the argument

did you see my and H.PWiz's 18 bytes?

@ngn No, clearly not, but I checked that no APL solution was posted before I posted. Why didn't any of you‽

well, once i've golfed it and shown it to the orchard, there's hardly any incentive to post :)

@ngn For you, no, but for me there is.

certainly, and i think you're doing a great job popularizing apl here. i was just making sure you know shorter solutions have been found and it's probably better to explain one of them (or a variation) instead

@ngn So post. I'll be happy to explain if you don't want to.

if you insist. feel free to edit.

APL (Dyalog Classic), 18 bytes
(≢?≢×≢)⍣(0=+.-∘≢)⍳

Try it online!
uses ⎕io←1
⍳ generates the numbers 1 2 ... n
(...)⍣(...) keep applying the function on the left until the function on the right returns true
≢ length, i.e. n
≢?≢×≢ choose randomly n distinct integers between 1 and n2
+.-∘≢ subtract the length from each number and sum
0= if the sum is 0, stop looping, otherwise try again

Java (JDK), 127 bytes
n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

Try it online!
Infinite loop until a set with the criteria matches.
I hope you have the time, because it's very sloooooow! It can't even go to 10 without timing out.

You can golf 3 bytes by changing if(r.size()==n&s==0) to if(r.size()+s==n).

@KevinCruijssen I've thought about it too, but no I can't because s could be -1 and n could be size() - 1.

Ah wait, you keep adding items to the set as long as s>0, so the size can be larger than n. Ok, in that case it indeed doesn't work. n is a constant, but unfortunately both s and r.size() are variables that can be both below or above 0 and n respectively.

JavaScript, 647 291 261 260 259 251 239 bytes
Thanks to @Veskah for -10 bytes at original version and "Oh yeah, you're outputting all the sets whereas the challenge asks for a random one to be returned"
(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

Try it online!
Create an array of n^2 1-based indexes, sort array randomly, slice n elements from array. While the sum of the random elements does not equal n^2 loop array of random elements; if sum of array elements is greater than n^2 and current element -1 does not equal zero or current element -1 is not in current array, subtract 1; if sum of array is less than n^2 and current element +1 is not in array, add 1 to element. If array sum is equal to n^2 break loop, output array.

637 bytes by pulling z.join into a variable, and k++

@Veskah The two while loops could probably also be reduced to the body of a single function which accepts parameters; and could substitute conditional operators (ternary) for the if..else statements; among other portions of the code that could more than likely be adjusted for golf; i.e.g., removing let statements.

@Veskah 601 bytes without substituting ternary for if..else

Oh yeah, you're outputting all the sets whereas the challenge asks for a random one to be returned (See the OP comments for more details)

@Veskah Must have misinterpreted the challenge and examples, or was too focused on solving this part of the question "Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?". testing if the algorithm consistently returned expected result for n^2 output arrays generated in a single call to the function, and simultaneously considering the similarities to this question N-dimensional N^N array filled with N.

447 bytes removing code which outputs n^2 arrays

Batch, 182 145 bytes
@set/an=%1,r=n*n,l=r+1
@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

Explanation: Calculates the minimum and maximum allowable pick, given that the numbers are to be picked in descending order, and chooses a random value within the range. Example for an input of 4:

We start with 16 left. We can't pick 11 or more because the remaining 3 picks must add to at least 6. We also need to pick at least 6, because if we only pick 5, the remaining 3 picks can only add to 9, which isn't enough for 16. We pick a random value from 6 to 10, say 6.
We have 10 left. We can't pick 8 or more because the remaining 2 picks must add to at least 3. As it happens, we can't pick 6 or more because we picked 6 last time. We also need to pick at least 5, because if we only pick 4, the remaining 2 picks can only add to 5, for a grand total of 15. We pick a random value from 5 to 5, say 5 (!).
We have 5 left. We can't pick 5 or more because the remaining pick must add to at least 1, and also because we picked 5 last time. We also need to pick at least 3, because if we only pick 2, the remaining pick can only be 1, for a grand total of 14. We pick a random value from 3 to 4, say 4.
We have 1 left. As it turns out, the algorithm chooses a range of 1 to 1, and we pick 1 as the final number.

Japt, 12 bytes
²õ àU ö@²¥Xx

Try it
                 :Implicit input of integer U
²                :U squared
 õ               :Range [1,U²]
   àU            :Combinations of length U
      ö@         :Return a random element that returns true when passed through the following function as X
        ²        :  U squared
         ¥       :  Equals
          Xx     :  X reduced by addition

According to a comment made by the OP, order of elements in the output is irrelevant so à should be fine.

Thanks, @KamilDrakari. Updated.

MATL, 18 13 bytes
`xGU:GZrtsGU-

Try it online!
`	# do..while:
x	# delete from stack. This implicitly reads input the first time
	# and removes it. It also deletes the previous invalid answer.
GU:	# paste input and push [1...n^2]
GZr	# select a single combination of n elements from [1..n^2]
tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top

I wouldn't try this in R - random characters almost never produce a valid program.

@ngm hahaha I suppose an explanation is in order.

Ruby, 46 bytes
->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

Try it online!

Clean, 172 bytes
import StdEnv,Math.Random,Data.List
? ::!Int->Int
?_=code{
ccall time "I:I"
}
$n=find(\s=length s==n&&sum s==n^2)(subsequences(nub(map(inc o\e=e rem n^2)(genRandInt(?0)))))

Try it online!

Python (2 or 3), 84 bytes
from random import*;l=lambda n,s=[]:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

Try it online!
Hits max recursion depth at around l(5)

Mathematica 40 bytes
RandomChoice[IntegerPartitions[n^2, {n}]]

First of all it is n^2, not 2^n. Secondly, your program must be a function and also a golfed one. Try this  RandomChoice@IntegerPartitions[#^2,{#}]&

Also the result must be (unordered, unique) but this function fails in both

Japt, 20 bytes
²õ ö¬oU íUõ+)Õæ@²¥Xx

Try it online!
Extremely heavily takes advantage of "Non-uniform" randomness, almost always outputs the first n odd numbers, which happens to sum to n^2. In theory it can output any other valid set, though I've only been able to confirm that for small n.
Explanation:
²õ                      :Generate the range [1...n^2]
   ö¬                   :Order it randomly
     oU                 :Get the last n items
        í   )Õ          :Put it in an array with...
         Uõ+            : The first n odd numbers
              æ_        :Get the first one where...
                  Xx    : The sum
                ²¥      : equals n^2

C (gcc), 128 125 bytes
p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

Try it online!
-3 bytes thanks to ceilingcat
NOTE: The probability is very very far from uniform. See explanation for what I mean and a better means to test that it works (by making the distribution closer to uniform [but still a far cry from it]).
How?
The basic idea is to only choose increasing numbers so as to not worry about duplicates. Whenever we pick a number we have a non-zero chance of 'skipping' it if allowable.
To decide if we can skip a number we need to know x the total left to be reached, k the number of elements we still have to use, and y the current candidate value. The smallest possible number that we could still pick would consist of $$y+(y+1)+(y+2)+...$$ added to the current value. In particular we require the above expression to be less than x. The formula will be $$\frac{k(k+1)}{2}+k(y+1)+y<x$$ Unfortunately we have to be a bit careful about rearranging this formula due to integer truncation in C, so I couldn't really find a way to golf it.
Nonetheless the logic is to have a chance to discard any y that satisfies the above equation.
The code
p(_){printf("%d ",_);}  // Define print(int)
f(n,x,y,i){             // Define f(n,...) as the function we want
    x=n*n;              // Set x to n^2
    y=1;                // Set y to 1
    for(i=0;++i<n;){    // n-1 times do...
        while(rand()&&  // While rand() is non-zero [very very likely] AND
            (n-i)*      // (n-i) is the 'k' in the formula
            (n-i+1)/2+  // This first half takes care of the increment
            (n-i)*(y+1) // This second half takes care of the y+1 starting point
            +y<x)       // The +y takes care of the current value of y
        y++;            // If rand() returned non-zero and we can skip y, do so
    p(y);               // Print y
    x-=y++;             // Subtract y from the total and increment it
    }p(x);}             // Print what's left over.

The trick I mentioned to better test the code involves replacing rand()&& with rand()%2&& so that there is a 50-50 chance that any given y is skipped, rather than a 1 in RAND_MAX chance that any given y is used.

I would love it if someone checked my math for consistency. I also wonder if this type of solution could make the uniform random speed challenge simple. The formula places an upper and lower bound on the answer, does a uniform random number in that range result in uniform random results? I don't see why not - but I haven't done much combinatorics in awhile.

Suggest p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++; instead of ){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;}

@ceilingcat I love these little improvements you find. I always get so focussed on the overall algorithm I forget to optimize for implementation (I basically go autopilot golfing mode once I have a non-golfed source that works - so I miss a lot of savings)

Hey, it's not just you who has those syntax-golfs. I find little improvements in a lot of C/C++ answers like that (except not in yours, @ceilingcat usually snaps those up).

Yeah, I've noticed that you two are probably the most active C/C++ putters (can we use putting to extend the golf analogy to the last few strokes? Why not!). It always impresses me that you can even understand the golfed code well enough to improve it.

Kotlin, 32 bytes
{(1..it*it).shuffled().take(it)}

Try it online!

The sum needs to be n^2

Wolfram Language (Mathematica), 49 bytes
(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

Try it online!
Golfed version by @J42161217.

Wolfram Language (Mathematica), 62 bytes
Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

Try it online!
How it works
Mainly based on this Math.SE question. In order to get partitions of \$n^2\$ into \$n\$ distinct parts, get partitions of \$n^2 - (n^2-n)/2 = (n^2+n)/2\$ instead and add \$0 \cdots n-1\$ to each element. Since Mathematica gives the partitions in decreasing order, \$n-1 \cdots 0\$ is added instead.

The answer to the Bonus Task

Bonus Task: Is there a formula to calculate the number of valid permutations for a given n?

Yes. Define \$part(n,k)\$ as the number of partitions of \$n\$ into exactly \$k\$ parts. Then it satisfies the following recurrence relation:
$$ part(n,k) = part(n-1,k-1) + part(n-k,k) $$
You can understand it as "If a partition contains a 1, remove it; otherwise, subtract 1 from every term". More explanation here on another Math.SE question. Combined with the initial conditions \$ part(n,1) = 1 \$ and \$ n < k \Rightarrow part(n,k) = 0 \$, you can compute it with a program. The desired answer will be:
$$ part(\frac{n^2+n}{2}, n) $$
which is, in Mathematica:
Length@IntegerPartitions[#*(#+1)/2,{#}]&

Try it online!

This is code golf.. 49 bytes (While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Finding the period of a recurring element in an array
Given an array A of integers, there exists at least one positive integer p such that A[i] == A[j] for all i and j for which i % p == j % p == 0. Find the smallest p.
Examples:

Input array: [1, _, 1, _, 1, _, 1, _, 1]. Output: 2
Input array: [1, _, _, 1, _, _, 1, _, _]. Output: 3.
Input array: [1, _, _, _, 1, _, _, _, 1]. Output: 4

Since the only problem is the lack of objective winning criterion, this seems like a good fit for the [tag:code-golf] tag.

wha are the _?

I claim Pyth f!t{%TQ if this turns out to be code-golf.

@Jonah It seems to be a number different from A[i] == A[j]

I take it that _ stands for any entry that isn't 1? And that the array is zero-indexed?

I was really hopeful that it would be i % p == j % p == N instead, which I think would have been a more interesting challenge

This could use more clarity on the quantifiers: I assume that "for all i and j for which" should be "for all i and j which are valid indexes into A and for which". The examples are missing some important corner cases: the empty array, a one-element array, an array of more than one element without repeats. But most importantly, and the reason that I'm voting to close as unclear, either the test suite or the spec is wrong for languages with 1-based indexing.

Python 3, 47 bytes
f=lambda l,d=1:f(l,d+1)if~-len({*l[::d]})else d

Try It Online

Python 3, 43 bytes
f=lambda l,n=1:2>len({*l[::n]})or-~f(l,n+1)

Try it online!
Assumes the list is non-empy. Outputs True as 1, though for 1 byte this can be fixed by changing 2> to 1//.
44 bytes:
f=lambda l,n=1:{l[0]}=={*l[::n]}or-~f(l,n+1)

Try it online!
f=lambda l,n=1:l[:-n:n]==l[n::n]or-~f(l,n+1)

Try it online!

Python 3, 64 Bytes
A recursive approach.
f=lambda x,s=1:s if x[::s].count(x[0])==len(x[::s])else f(x,s+1)

Try it Online
Python 3, 82 81 Bytes
-1 byte thanks to Jakob!
lambda x:[x[::i].count(x[0])==len(x[::i])for i in range(1,len(x)+1)].index(1>0)+1

Try it Online!

How about 1>0 instead of True?

For the recursive approach, you need to initialize s=1 as an optional argument so that the function runs without taking an extra input.

Pyth, 7 bytes
f!t{%TQ

Try it here. Pyth is at a disadvantage because it uses only printable ASCII; optimally encoded this would be \$7 * \log_{256} 95 = 5.749\$ bytes.
f             Find the first positive integer T such that
 !t           there is only one element in
   {          the list obtained by taking unique elements
    %TQ       of every Tth element of the input.

Java 8, 85 bytes
A lambda from a primitive array type to int.
l->{for(int d=0,i;;)for(i=++d;;i+=d){if(i>=l.length)return d;if(l[i]!=l[i-d])break;}}

Try It Online
Ungolfed
l -> {
    for (int d = 0, i; ;)
        for (i = ++d; ; i += d) {
            if (i >= l.length)
                return d;
            if (l[i] != l[i - d])
                break;
        }
}

Japt, 10 bytes
@ëX â ÊÉ}f

Try it online!
Explanation:
@       }f    :Get the first integer X which returns 0 from:
 ëX           : Get every Xth item in the input
    â         : Get the unique values of that list
      Ê       : Count how many there are
       É      : Subtract 1

Japt, 6 bytes
I think this is right, the spec isn't all that clear. Assumes, as the spec would seem to suggest, that the number we're looking for will always appear first in the array and the _s must all be different from that number.
ð¶Ug)æ

Try it
           :Implicit input of array U
ð          :0-based indices of elements
 ¥         :  Equal to
  Ug       :  First element of U
    )      :End indexing
     æ     :First truthy (non-zero) element

Jelly, 6 bytes
Assuming this is meant to be code-golf for now.
mJE€TḢ

Try it online!

Or mJE€i1. Does posting before the question is clarifed get you the win for tiebreaking purposes? I was hesitant to.

For me it just means I got to post from a computer rather than a mobile. Most wont upvote until the winning criteria is given anyway.

Powershell, 82 bytes
(($a=$args)|%{($i++)}|?{"$a"-match"^(\d+)(( -?\d+){$_} \1)*( -?\d+){0,$_}$"})[0]+1

Test script:
$f = {

(($a=$args)|%{($i++)}|?{"$a"-match"^(\d+)(( -?\d+){$_} \1)*( -?\d+){0,$_}$"})[0]+1

}

@(
    ,(1 , 1,1,1,1,1)
    ,(2 , 1,-2,1,3,1,-4,1,5)
    ,(2 , 1,-2,1,3,1,-4,1,5,1)
    ,(3 , 1,-2,1,1,3, 4,1,5,1)  # 1 may be in place '_'
    ,(4 , 1,-2,3,4,1, 5,1,6,1)
    ,(5 , 1,2,3,4,5,1)
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"

}

Explanation:
Regexp match on array.toString() which equivalent array.join(' ').


text:
Arbitrary Randomness (Speed edition)
Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) such that the sum of the set is equal to n^2
Random, in this case, means uniformly random between valid outputs. Each valid output for a given n must have a uniform chance of being generated.
For example, n=3 should have a 1/3 chance each of outputting 6, 1, 2, 3, 5, 1, or 4, 3, 2. As this is a set, order is irrelevant, 4, 3, 2 is identical to 3, 2, 4
Scoring
The winner is the program that can compute the highest n in under 60 seconds.
Note: To prevent possible partial hardcoding, all entries must be under 4000 bytes
Testing
All code will be run on my local Windows 10 machine (Razer Blade 15, 16GB RAM, Intel i7-8750H 6 cores, 4.1GHz, GTX 1060 in case you want to abuse the GPU) so please provide detailed instructions to run your code on my machine.
At request, entries can be run either via Debian on WSL, or on a Xubuntu Virtual Machine (both on the same machine as above)
Submissions will be run 50 times in succession, final score will be an average of all 50 results.

Related

Is hardcoding a bit allowed, if it’s under 4000 bytes?

@Quintec No, hardcoding is a standard loophole, therefore forbidden by default.
The tricky thing is hardcoding is also considered an unobservable criterion, so I can't officially say "No hardcoding" beyond what the loophole disallows. Hence the byte limit.
In other words: Please don't hardcode

Most submissions will use a rejection method and thus running time will be random and have large variability. That makes timing difficult

@LuisMendo I indeed have that with my current answer right now. Sometimes it gives the answer for n=50 in 3 seconds, sometimes in 45 seconds..

@KevinCurijssen  Yup. With standard rejection sampling, running time has a geometric distribution (assuming constant time per iteration), which is unbounded

Updated to somewhat account for time variability

Oh, I forgot -- because some solutions may decide to use low-quality RNG to be fast, it might be necessary to provide a black box routine that takes n and produces a random number in (1..n), and forces all solutions to use it.

Rust, n ≈ 1400
How to run
Build with cargo build --release, and run with target/release/arbitrary-randomness n.
This program runs fastest with lots of memory (as long as it’s not swapping, of course).  You can adjust its memory usage by editing the MAX_BYTES constant, currently set at 8 GiB.
How it works
The set is constructed by a sequence of binary decisions (each number is either inside or outside the set), each of whose probabilities are computed combinatorially by counting the number of possible sets constructible after each choice using dynamic programming.
Memory usage for large n is reduced by using a version of this binomial partitioning strategy.
Cargo.toml
[package]
name = "arbitrary-randomness"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rand = "0.6"

src/main.rs
extern crate rand;

use rand::prelude::*;
use std::env;
use std::f64;
use std::mem;

const MAX_BYTES: usize = 8 << 30; // 8 gibibytes

fn ln_add_exp(a: f64, b: f64) -> f64 {
    if a > b {
        (b - a).exp().ln_1p() + a
    } else {
        (a - b).exp().ln_1p() + b
    }
}

fn split(steps: usize, memory: usize) -> usize {
    if steps == 1 {
        return 0;
    }
    let mut u0 = 0;
    let mut n0 = f64::INFINITY;
    let mut u1 = steps;
    let mut n1 = -f64::INFINITY;
    while u1 - u0 > 1 {
        let u = (u0 + u1) / 2;
        let k = (memory * steps) as f64 / u as f64;
        let n = (0..memory)
            .map(|i| (k - i as f64) / (i as f64 + 1.))
            .product();
        if n > steps as f64 {
            u0 = u;
            n0 = n;
        } else {
            u1 = u;
            n1 = n;
        }
    }
    if n0 - (steps as f64) <= steps as f64 - n1 {
        u0
    } else {
        u1
    }
}

fn gen(n: usize, rng: &mut impl Rng) -> Vec<usize> {
    let s = n * n.wrapping_sub(1) / 2;
    let width = n.min(MAX_BYTES / ((s + 1) * mem::size_of::<f64>()));
    let ix = |m: usize, k: usize| m + k * (s + 1);
    let mut ln_count = vec![-f64::INFINITY; ix(0, width)];
    let mut checkpoints = Vec::with_capacity(width);
    let mut a = Vec::with_capacity(n);
    let mut m = s;
    let mut x = 1;

    for k in (1..=n).rev() {
        let i = loop {
            let i = checkpoints.len();
            let k0 = *checkpoints.last().unwrap_or(&0);
            if k0 == k {
                checkpoints.pop();
                break i - 1;
            }
            if i == 0 {
                ln_count[ix(0, i)] = 0.;
                for m in 1..=s {
                    ln_count[ix(m, i)] = -f64::INFINITY;
                }
            } else {
                for m in 0..=s {
                    ln_count[ix(m, i)] = ln_count[ix(m, i - 1)];
                }
            }
            let k1 = k - split(k - k0, width - 1 - i);
            for step in k0 + 1..=k1 {
                for m in step..=s {
                    ln_count[ix(m, i)] = ln_add_exp(ln_count[ix(m - step, i)], ln_count[ix(m, i)]);
                }
            }
            if k1 == k {
                break i;
            }
            checkpoints.push(k1);
        };

        while m >= k && rng.gen_bool((ln_count[ix(m - k, i)] - ln_count[ix(m, i)]).exp()) {
            m -= k;
            x += 1;
        }
        a.push(x);
        x += 1;
    }
    a
}

fn main() {
    if let [_, n] = &env::args().collect::<Vec<_>>()[..] {
        let n = n.parse().unwrap();
        let mut rng = StdRng::from_entropy();
        println!("{:?}", gen(n, &mut rng));
    } else {
        panic!("expected one argument");
    }
}

Try it online!
(Note: the TIO version has a few modifications.  First, the memory limit is reduced to 1 GiB. Second, since TIO doesn’t let you write a Cargo.toml and depend on external crates like rand, I instead pulled in drand48 from the C library using the FFI.  I didn’t bother to seed it, so the TIO version will produce the same result on every run.  Don’t use the TIO version for official benchmarking.)

Because floating point format is finite, it's possible to optimize ln_add_exp by checking if the absolute difference is larger than ~15 or so, which may be faster if there are a lot of such addition.

@user202729 Nope, nearly all ln_add_exp calls involve comparable inputs.

Java 7+, n=50 in ~30 sec on TIO
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Random;
class Main{
  public static void main(String[] a){

    int n=50;

    Random randomGenerator = new Random();
    int i = n+1;
    int squaredN = n*n;
    int[]randomIntegers = new int[i];
    randomIntegers[n] = squaredN;
    while(true){
      for(i=n; i-->1; ){
        randomIntegers[i] = randomGenerator.nextInt(squaredN);
      }
      Set<Integer> result = new HashSet<>();
      Arrays.sort(randomIntegers);
      for(i=n; i-->0; ){
        result.add(randomIntegers[i+1] - randomIntegers[i]);
      }
      if(!result.contains(0) && result.size()==n){
        System.out.println(result);
        return;
      }
    }
  }
}

Ungolfed version of my answer for the code-golf version of this challenge for now, with only one minor change: java.util.Random#nextInt(limit) is used instead of (int)(Math.random()*limit) for an integer in the range [0, n), since it's about twice as fast.
Try it online.
Explanation:
Approach used:
The code is split into two parts:

Generate a list of n amount of random integers that sum to n squared.
Then it checks if all values are unique and none are zero, and if either is falsey, it will try step 1 again, rinsing and repeating until we have a result.

Step 1 is done with the following sub-steps:
1) Generate an array of n-1 amount of random integers in the range [0, n squared). And add 0 and n squared to this list. This is done in O(n+1) performance.
2) Then it will sort the array with the builtin java.util.Arrays.sort(int[]), This is done in O(n*log(n)) performance, as is stated in the docs:

Sorts the specified array of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

3) Calculate the difference between each pair. This resulting list of differences will contain n integers that sum to n squared. This is done in O(n) performance.
Here an example:
// n = 4, nSquared = 16

// n-1 amount of random integers in the range [0, nSquared):
[11, 2, 5]

// Add 0 and nSquared to it, and sort:
[0, 2, 5, 11, 16]

// Calculate differences:
[2, 3, 6, 5]

// The sum of these differences will always be equal to nSquared
sum([2, 3, 6, 5]) = 16

So these three steps above are pretty good for performance, unlike step 2 and the loop around the whole thing, which is a basic brute-force. Step 2 is split in these sub-steps:
1) The differences list is already saved in a java.util.Set. It will check if the size of this Set is equal to n. If it is, it means all random values we generated are unique.
2) And it will also check that it contains no 0 in the Set, since the challenge asks for random values in the range [1, X], where X is n squared minus the sum of [1, ..., n-1], as stated by @Skidsdev in the comment below.
If either of the two options above (not all values are unique, or a zero is present), it will generate a new array and Set again by resetting to step 1. This continues until we have a result. Because of this, the time can vary quite a bit. I've seen it finish in 3 seconds once on TIO for n=50, but also in 55 seconds once for n=50.
Prove of uniformity:
I'm not entirely sure how to prove this to be completely honest. The java.util.Random#nextInt is uniform for sure, as is described in the docs:

Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. The general contract of nextInt is that one int value is pseudorandomly generated and returned. All 232 possible int values are produced with (approximately) equal probability.

The differences between these (sorted) random values themselves are of course not uniform, but the sets as a whole are uniform. Again, I'm not sure how to prove this mathematically, but here is a script that will put 10,000 generated sets (for n=10) in a Map with a counter, where most sets are unique; some repeated twice; and the maximum repeated occurrence is usually in the range [4,8].
Installation instructions:
Since Java is a pretty well-known language with plenty of information available on how to create and run Java code, I will keep this short.
All the tools used in my code are available in Java 7 (perhaps even already in Java 5 or 6, but let's use 7 just in case). I'm pretty sure Java 7 is already archived though, so I would suggest downloading Java 8 to run my code.
Thoughts regarding improvements:
I'd like to find an improvement for the check for zeros and check all values are unique. I could check for 0 before, by making sure the random value we add to the array isn't already in it, but it would mean a couple of things: the array should be an ArrayList so we can use the builtin method .contains; a while-loop should be added until we've found a random value that isn't in the List yet. Since checking for zero is now done with .contains(0) on the Set (which is only checked once), it's most likely better for performance to check it at that point, in comparison to adding the loop with .contains on the List, which will be checked at least n times, but most likely more.
As for the uniqueness check, we only have our n amount of random integers that sum to n squared after step 1 of the program, so only then we can check whether all are unique or not. It might be possible to keep a sortable List instead of array, and check the differences in between, but I seriously doubt it will improve the performance than just putting them in a Set and check if the size of that Set is n once.

if it helps the speed, no number in the set can be greater than n^2 - sum(1..n-1) for example for n=5 the largest valid number is 5^2 - sum(1, 2, 3, 4) == 25 - 10 == 15

@Skidsdev Thanks, hadn't thought about that. Although with my current approach I can't utilize it, since I get the differences between random-pairs, instead of the random values directly. But it might be useful for other answers perhaps.

The size of the resulting set can never be more than n, can it? In that case, you can add 0 to the set, and then check that the size is (now) more than n. This can only happen if the differences are all nonzero and distinct.

@Neil Oh, that's pretty smart, and I will definitely use that in my code-golf answer to golf a few bytes off. I'm not sure if it will improve the performance here, though. HashSet.contains is in most cases close to O(1), and in the worst case it's O(n) in Java 7, and O(log n) in Java 8+ (it has been improved after they've replaced chaining with collision detection). If I'm allowed to return the Set with the added 0 for the check, then it's indeed slightly better for performance, but if I have to call set.remove(0); inside the if, I'm pretty sure performance is somewhat the same.

Oh, I forgot you need to return the set as well... never mind.

Mathematica n=11
(While[Tr@(a=RandomSample[Range[#^2-#(#-1)/2],#])!=#^2];a)&

Scala, n=50 in ~45 sec on TIO
Port of @Kevin Cruijssen's Java answer in Scala.
Try it online!
import scala.util.Random
import scala.collection.mutable.HashSet

object Main {
  def main(args: Array[String]): Unit = {

    val n = 50
    val randomGenerator = new Random()
    val squaredN = n * n
    var randomIntegers = new Array[Int](n + 1)
    randomIntegers(n) = squaredN

    while(true) {
      for(i <- n-1 to 0 by -1) {
        randomIntegers(i) = randomGenerator.nextInt(squaredN)
      }
      val result = HashSet[Int]()
      scala.util.Sorting.quickSort(randomIntegers)
      for(i <- n-1 to 0 by -1) {
        result.add(randomIntegers(i+1) - randomIntegers(i))
      }
      if(!result.contains(0) && result.size == n) {
        println(result)
        return
      }
    }
  }
}

Python, n ≈ 4500
Runs in expected \$Θ(n^{5/2})\$ time.
import numpy as np

def gen(n):
    target = n**2
    k_bounds = [1 / ((n + 1) / 2 - target / n), 1 / ((n + 1) / 4 - target / n)]
    i = np.arange(n)
    while (k := (k_bounds[0] + k_bounds[1]) / 2) not in k_bounds:
        p = -np.expm1(k * (n - i))
        k_bounds[int(((n - i) / p).sum() > target)] = k

    rng = np.random.default_rng()
    while True:
        output = rng.geometric(p=p).cumsum()
        if output.sum() == target:
            return output

Attempt This Online!
How it works
After selecting a constant \$k < 0\$ (explained below), we draw \$n\$ positive integers \$a_0, a_1, …, a_{n-1}\$ independently from the geometric distributions of probabilities \$p_i = 1 - e^{k(n - i)}\$. We build a candidate set from the prefix sums of the \$a_i\$:
$$S = \{a_0, a_0 + a_1, …, a_0 + a_1 + … + a_{n-1}\}.$$
The probability of generating any particular \$S\$ can be computed as
$$\prod_i (1 - p_i)^{a_i} p_i = \prod_i e^{k(n - i)a_i} p_i = e^{k \sum_i (n - i)a_i} \prod_i p_i = e^{k \sum S} \prod_i p_i,$$
which is proportional to \$e^{k \sum S}\$. In particular, the probability of generating each \$S\$ that sums to \$n^2\$ is the same! We accept \$S\$ if it sums to \$n^2\$, otherwise reject it and repeat the draw.
Although the constant \$k\$ has no effect on correctness, it has a huge effect on the expected running time. We select \$k\$ using a binary search such that \$E[\sum S] = \sum_i \frac{n - i}{p_i}\$ is made equal to \$n^2\$, in order to optimize the probability of acceptance to \$Θ(n^{-3/2})\$.