7
\$\begingroup\$

Given a map from arrays of integers of same size to single integers, determine if there is a set of indices such that the output is equal to the maximum of the elements at those indices for every corresponding pair.

You can take the input as a map if your language support, arrays of pairs, separated 2D array of input and its output, or other reasonable format. Shortest code wins.

Test cases

input => output
input => output  ->  truthy/falsey

[1,2,3] => 2
[2,1,3] => 2
[3,2,1] => 3 -> true (maximum of pos 1 and pos 2)

[1,2,3] => 2
[2,3,1] => 2
[3,3,2] => 2 -> false (Whatever positions chosen, 3 must at least appeared in output)

[1,2,3] => 2 -> true (maximum of pos 2, or maximum of pos 1 and 2)

[1,2,3] => 0 -> false (no way maximum of some of 1, 2 and 3 result in 0)
\$\endgroup\$
3
  • \$\begingroup\$ Also, can we take input as a list of input lists and as a list of output values? e.g. [[1,2,3],[2,1,3],[3,2,1]] and [2,2,3]? \$\endgroup\$ Sep 15 at 17:05
  • \$\begingroup\$ @cairdcoinheringaahing That input format should be acceptable \$\endgroup\$
    – l4m2
    Sep 15 at 17:07
  • \$\begingroup\$ I've cleaned up the test cases a bit, as they were a bit difficult to "group" together, and copy/paste for testing \$\endgroup\$ Sep 15 at 17:53
4
\$\begingroup\$

Jelly, 9 bytes

ZŒPZ€Ṁ€€i

Try it online!

Outputs 0 for falsey, non-zero for truthy

-3 bytes thanks to hyper-neutrino!

How it works

ZŒPZ€Ṁ€€i - Main link. Takes a list of inputs I on the left and outputs O on the right
Z         - Transpose I
 ŒP       - Powerset of the columns
   Z€     - Transpose each
       €  - Over each column powerset:
     Ṁ€   -   Get the maximum of each column
        i - Index of O in this list of lists, or 0 if not found
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 70 bytes

Returns false for valid, or true for invalid.

a=>a.some(b=([a,m])=>a.every((v,i)=>v-m|b[i],a.map((v,i)=>b[i]|=v>m)))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes

Times@@Max/@(Sign[#-#2])&

Try it online!

Input [inputs, outputs]. Returns 0 for truthy, and nonzero (1 or -1) otherwise.

             Sign[#-#2]     categorize indices for each i/o (-1 <, 0 =, 1 >)
       Max/@(          )   take max for each index across i/o s
Times@@                     0 present (solutions exist)?
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 7 bytes

øæʒø€àQ

Port of @cairdCoinheringaahing's Jelly answer, so make sure to upvote him!

Outputs an empty list [] as falsey, and a non-empty list (containing one or multiple matrices of integers) as truthy.

Try it online or verify all test cases.

Explanation:

ø        # Zip/transpose the (implicit) first input-matrix, swapping rows/columns
 æ       # Get the powerset of these columns
  ʒ      # Filter this list of matrices by:
   ø     #  Zip/transpose the current matrix, swapping rows/columns
    €    #  For each inner list:
     à   #   Pop and leave the maximum
      Q  #  Check if this list is equal to the (implicit) second input-list
         # (after which the filtered list of matrices is output implicitly as result)
\$\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.