2
\$\begingroup\$

You have a matrix of size m x n.

Each cell in the matrix has a uniformly random integer value v, where 0 ≤ v < i, and i ≤ (m x n). (Meaning, the matrix contains a maximum of m x n distinct values, but it may have fewer.)

1) Write a function that accepts input values of m, n, i, and returns a matrix that meets the criteria above.

2) Write a second function that accepts the output of the first function as input, and returns the smallest contiguous submatrix that contains every value of v (by returning the submatrix itself, or its coordinates). By “smallest” I mean the submatrix containing the fewest cells.

(If it helps you visualize, the original inspiration for this problem was wondering how to find the smallest rectangle within a GIF that contained all the colors in its palette.)

\$\endgroup\$
6
  • 5
    \$\begingroup\$ This needs some clarification about the randomness. Clearly the random variables aren't independent, because that would conflict with the requirement that every possible value of v appear at least once. So what are the permitted distributions? \$\endgroup\$ Oct 22, 2014 at 7:39
  • 1
    \$\begingroup\$ @PeterTaylor: As I understand it, you could for example first place the values from 0 to *i*−1 randomly on the matrix, then fill up the remaining elements with random numbers from 0 to *i*−1. (Or anything that produces the same distribution of matrices.) \$\endgroup\$
    – Wrzlprmft
    Oct 22, 2014 at 10:45
  • \$\begingroup\$ @Wrzlprmft, probably. But could you also just make all the matrices generated by your program be permutations of the first mn characters from an infinite sequence which just repeats 0 to i? \$\endgroup\$ Oct 22, 2014 at 11:02
  • \$\begingroup\$ @weston When i = mn, the second part of the question is trivial, so i ≤ mn is deliberate. \$\endgroup\$ Oct 22, 2014 at 14:57
  • 1
    \$\begingroup\$ Smallest submatrix regarding which metric? Product of dimensions? \$\endgroup\$
    – Ingo Bürk
    Oct 22, 2014 at 18:35

1 Answer 1

2
\$\begingroup\$

APL (23 + 56 = 79)

Function 1 (23):

{¯1+⍵⍴(V⍴⍺?⍺)[V?V←×/⍵]}

This takes i as its left argument and m n as its right argument, like so:

      +mat←8 {¯1+⍵⍴(V⍴⍺?⍺)[V?V←×/⍵]} 5 5
2 4 7 1 3
7 5 6 7 3
3 1 2 4 6
0 4 2 6 1
5 5 0 0 6

Function 2 (56):

{⊃V[⍋≢∘∊¨V←V/⍨{∧/⍵∊⍨∪∊M}¨V←⊃,/{↓∘⍵¨¯1+,⍳⍴⍵}¨↑∘⍵¨,⍳⍴M←⍵]}

This takes the output from the first function as its right argument, like so:

      {⊃V[⍋≢∘∊¨V←V/⍨{∧/⍵∊⍨∪∊M}¨V←⊃,/{↓∘⍵¨¯1+,⍳⍴⍵}¨↑∘⍵¨,⍳⍴M←⍵]} mat
7 5 6
3 1 2
0 4 2
\$\endgroup\$
1
  • \$\begingroup\$ This makes me want to learn APL. \$\endgroup\$ Oct 31, 2014 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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