4
\$\begingroup\$

enter image description here

(The text asks how many boxes there are in the picture)

Now you are required to generate such a problem and its answer.

Input

  • an integer n
  • (optionally) random source of two values, in case you don't want to use the default random.

Output can be

  • a 3D array A[n][n][n] of booleans, where A[i][j][k] => (i==0 || A[i-1][j][k]) && (j==0 || A[i][j-1][k]) && (k==0 || A[i][j][k-1]) (assuming 0-index)
    where && is logical AND, || is logical OR, and => is "implies" (if X is true, then Y is true).

    Basically this says that if you have a box at some position then for each coordinate that coordinate must be either 0 or also have a box if that coordinate is one less. So no holes in any direction that gets you closer to the origin.

  • a 2D array B[n][n] of integers, where B[i][j] means how many k satisfy A[i][j][k]

    Basically this is the height of the stacks where these heights can't become lower in any direction that gets you closer to the origin.

  • Besides the array, the amount of boxes (how many i,j,k satisfy A[i][j][k])

Every valid output should have nonzero probability to be outputted.

Example: (Here use 2D output format for convenience)

1 => [[0]] 0 or [[1]] 1
2 => [[0,0],[0,0]] 0 
     [[1,0],[0,0]] 1 
     [[1,0],[1,0]] 2 
     [[1,1],[0,0]] 2 
     [[1,1],[1,0]] 3 
     [[1,1],[1,1]] 4 
     [[2,0],[0,0]] 2 
     [[2,0],[1,0]] 3 
     [[2,0],[2,0]] 4 
     [[2,1],[0,0]] 3 
     [[2,1],[1,0]] 4 
     [[2,1],[1,1]] 5 
     [[2,1],[2,0]] 5 
     [[2,1],[2,1]] 6 
     [[2,2],[0,0]] 4 
     [[2,2],[1,0]] 5 
     [[2,2],[1,1]] 6 
     [[2,2],[2,0]] 6 
     [[2,2],[2,1]] 7 or
     [[2,2],[2,2]] 8

So for input 2 your program should randomly return one of the 20 possible outputs, and if run enough times every one of them should be returned at some point.

Your program must terminate.

Winning criteria

This is , shortest code in bytes win!

\$\endgroup\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – l4m2 Mar 12 '18 at 1:34
  • \$\begingroup\$ I didn't define "behind" or anything in the output array \$\endgroup\$ – l4m2 Mar 12 '18 at 1:43
  • 3
    \$\begingroup\$ Rust: std::collections::BinaryHeap::new<Box<i32>>() (generates a heap of boxes) \$\endgroup\$ – Esolanging Fruit Mar 12 '18 at 1:52
  • 1
    \$\begingroup\$ The outputs are called (3D) Young diagrams. Related. (Asks for an ASCII art representation instead of an array representation.) \$\endgroup\$ – Martin Ender Mar 12 '18 at 9:24
  • 1
    \$\begingroup\$ I think it is fine now, but I can't speak for the people who voted to close. \$\endgroup\$ – FryAmTheEggman Mar 12 '18 at 17:19
4
\$\begingroup\$

Perl 5, -ap 121 bytes / 56 bytes

This 121 byte solution has a uniform distribution over all valid arrangements of boxes. It tries to be somewhat efficient but still times out on TIO for size 4 or more

#!/usr/bin/perl -ap
@a=((0 x$_.$")x$_.$/)x$_."";s%0%/0(|.{@F}|(\X{@F}\X){@F})\G/+${$z="$`1$'"}++||push@a,$z;0%eg for@a;$_=$a[rand@a];$\=y/1//

Try it online!

If you don't care about uniformity it's of course easy to go shorter, e.g. this 56 bytes solution is very biased towards the origin (it probably gives more nice pictures for the motivating example though)

#!/usr/bin/perl -a
say map{\@$_[rand@;+1,$#{$_-1}];@;-$#$_.$"}@;for@;=1..$_

Try it online!

(checked for size 2 and 3 that it indeed generates all possible outputs)

\$\endgroup\$
2
\$\begingroup\$

Python 2, 144 bytes

from random import*
n=input()
a=[n]*n*n
for x in range(n*n):a[x]=randint(0,min(a[x-(x%n>0)],a[x-n]))
print[a[i*n:i*n+n]for i in range(n)],sum(a)

Try it online!

Quick and dirty solution.

Generates a random number (which is upper-bounded by its left (if present) and upper cells) for each cell as a linear array, and then prints its 2D version and the sum.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 100 bytes

n=>[...Array(n)].map((_,i,a)=>k=a.map((_,j)=>l=0|Math.random()*-~(i?j?Math.min(k[j],l):k[0]:j?l:n)))
\$\endgroup\$
1
\$\begingroup\$

Jelly, 16 bytes

³‘X’¤þ`ṂƤ€Z$⁺ṄS⁺

Try it online!


I made a terrible mistake. No idea why no-one noticed that.

Full program. Prints the array and the sum.

Not uniform, of course. Return all-zero most of the time.

Verification for side length 2.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.