Let $s$ be the size of an array (36 in your example), $v$ the number
of possible values (here 13) of each element, $n$ the numbers of
reference arrays (here 24), i.e., the size of the set $S=\{A_i \mid i\in[1..n]\}$ of arrays.
I am assuming that the cost for preprocessing the arrays does not
matter. Else, you can alsways simplify the procedure below, as long as
you do it well enough no to exceed the worst case time complexity
$O(n)$.
Ideally you want to get a balanced binary tree of test for
identification so that you get your answer in $\lceil \log_2 n \rceil$
tests, i.e. 5 tests at most with the given figures. In other words,
you are looking for 5 bits of information, that allow you to
discriminate between your $n=24$ arrays.
For that you would need a criterion, testable in one comparison,
that can cut approximately in two any given set of arrays, so that if
$n_1$ and $n_2$ are the sizes of the 2 subsets, $\lfloor \log_2 n_1
\rfloor = \lfloor \log_2 n_2 \rfloor$.
However, that is not always possible. A worst case example is, when
array $A_i$ contains only $0$, except for element $A_i[i]$ that
contains $1$. Then the only way to identify $X$ in the reference set is
to scan the elements of $X$ to find which has value $1$. This has
complexity $O(n)$
So you you know complexity can be as bad as that, when an index will
discriminate at best one array. Of cours, in general, you have to
analyse the set of arrays to determine which indices you have to look
at.
However, if the set of arrays permit, you can do better, as indicated
above. For each index $i$ for the arrays, you try to identify a simple
test $T_i$ that will partition the set $S$ of arrays in two subsets $S_1$ and $S_2$ of nearly
equal sizes: $n_1$ and $n_2$, such that $|n_1-n_2|$ is minimal (this
is a bit stronger than the condition above, but the idea is to keep
some slack on each half for future partitions). You do that for each index
$i\in[1..s]$, and you keep the index $i_0$ that gives the minimal
difference $|n_1-n_2|$. Of course, you can stop as soon as you have a
difference that is less than $2$, or possibly as soon as $\lfloor
\log_2 n_1 \rfloor = \lfloor \log_2 n_2 \rfloor$ (the choice is purely
heuristic). You can even stop earlier if you are not too worried about getting the fastest test tree.
Now for index $i_0$ you have a test $T_{i_0}$ that partitions your set $S$
of arrays into two disjoint subsets $S_1$ and $S_2$ of respective
sizes $n_1$ and $n_2$, on the basis of the values at index $i_0$.
This will be the first test you apply to a new array $X$ to identify
it in the set $S$. This test will tell you whether it is in $S_1$ or
$S_2$. Then you know that your identification of X will take at most
$1+\max(n_1,n_2)$ steps.
Then you pursue the construction of your balanced tree, on each of the
two subsets $S_1$ and $S_2$, and with some luck you can approach the
optimal complexity $O(\log_2 n)$. No garantee given, since a bad set
of arrays can impose the maximum complexity $O(n)$, with the forced
reading of, on average, n/2 elements of $X$.
But there is still one very important detail that is missing. What
kind of test is to be used. The answer is: any kind that is easy
enough to count as one step. So I guess a primality test that
partitions arrays into those with prime integer at index $i$ and those
with non-prime at index $i$ is not a good idea.
Suggestions are: testing if the $A_j[i]$ is equal to a given value, or
whether it is greater than some value, or whether $A_j[i] \mod p = r$
for two values $p$ and $r$. Just use your imagination, if there is a need
for it. This can all be mechanized, tried automatically, but with a
computation cost. What you should do depends on how much speeding up
recognition by thorough preprocessing is essential for you.
A faster solution for large values of $n$, assuming $v$ remains small.
Actually, though the worst case $O(n)$ cannot be improved, one can do
better than the first solution I propose above, assuming $v$ remains small.
The idea is that one does not need to use binary tree. With more
branching, one can get even faster to the answer.
For that purpose, we need to build a function $\phi$ that maps the $v$
values used into the integer range $[1..v]$. This can be done by
hashing or by other means. Then we can assume without loss of
generality that the values used are the integer in $[1..v]$.
Then one could find a minimal set $I$ of indices for the arrays, so that
for any pair of arrays $A_j$ and $A_k$ there is an index $i\in I$ such
that $A_j[i] \neq A_k[i]$. Then, for any array $X$ known to be equal
to an array $A_h\in S$, we can identify $A_h$ by looking only at the
values for the indices in $I$. One could then build a decision tree
based on these indices considered in succession.
However, finding such a minimal set of indices may be difficult (I did
not look into its complexity), and there may be better solutions, by
using independent indices for the different nodes on a given level of
the decision tree.
So we can probably get an even faster result by proceeding as
follow. Choose a first index $i_0$ such that the $p$ different values
for that index partition the set $S$ of arrays into $p$ subsets $S_x$
for $x\in [1..p]$. Depending on whether you try to reduce the average
cost or the maximum cost, you may try to choose $i_0$ so as to
maximize $p$, or to minimize the maximum size of the subsets $S_x$
(though this is heuristic). These $p$ subsets are the daughters of the root in the decision tree being built.
Then you repeat this operation for each subset, finding independently
for each subset $S_x$ a new index $i_{x,1}$, so as to further
partition the subset.
You repeat the operation until you reach the leaves which correspond
to singleton sets, i.e., a specific array in $S$.
You get a widely branching decision tree, where each non-leaf node
(actually corresponding to a subset of arrays) is labeled by an index,
each branch is labeled by a value found for that index, and each leaf
is labeled by an array in $S$. This tree must be implemented so that
each branch can be accessed in one step by direct indexation.
Then, given an array $X$, you read its value at the index $i_0$
labeling the root, and use this value as $\phi(X[i_0])$ to access by
indexation the next node in the tree. Then you repeat the step until
you reach a leaf.
When $v$ is large, the algorithm has to be adapted by using a
different function $\phi$ at each node.
