Count the ways to transform (2)

Question

Your input is a matrix (2d array) of positive integers. For example:

\begin{matrix} 1 & 1 & 4 & 7\\ 1 & 3 & 5 & 6\\ 2 & 1 & 4 & 5 \\ \end{matrix}

A semi-continuous transformation of this matrix is a rearranging of elements that preserves immediate neighbors. For example, we can swap the \$2\$ in the bottom left, and the \$1\$ in the top left corner.

\begin{matrix} 2 & 1 & 4 & 7\\ 1 & 3 & 5 & 6\\ 1 & 1 & 4 & 5 \\ \end{matrix}

This is fine, because every number has the same neighborhood counts. That is, we can make a sorted list of numbers and their neighbors, and verify the they are the same:

\begin{matrix} \text{Number} & \text{Neighbors} \\ 1 & 1,1 \\ 1 & 1,2,3 \\ 1 & 1,3,4 \\ 1 & 2,3,4 \\ 2 & 1,1 \\ 3 & 1,1,1,5 \\ 4 & 1,5,7 \\ 4 & 1,5,5 \\ 5 & 3,4,4,6 \\ 6 & 5,5,7 \\ 7 & 4,6 \end{matrix}

Here is another example.

\begin{matrix} 2 & 1 & 1\\ 1 & 3 & 1\\ 1 & 1 & 4\\ \end{matrix}

Let's make a neighbor list. Note that we are gonna have duplicate entries (which is fine)

\begin{matrix} \text{Number} & \text{Neighbors} \\ 1 & 1,1 \\ 1 & 1,1 \\ 1 & 1,2,3 \\ 1 & 1,2,3 \\ 1 & 1,3,4 \\ 1 & 1,3,4 \\ 2 & 1,1 \\ 3 & 1,1,1,1 \\ 4 & 1,1 \\ \end{matrix}

Now, can we swap the top left \$2\$ and the bottom left \$1\$? It may look fine at first glance, but we must be careful! By swapping those two elements we would create a \$1\$ which has neighbors \$2,3,4\$, which didn't exist in the first input.

Just to demonstrate, here is the matrix after this non-semi-continuous transformation:

\begin{matrix} 1 & 1 & 1\\ 1 & 3 & 1\\ 2 & 1 & 4\\ \end{matrix}

And here is the neighbor list:

\begin{matrix} \text{Number} & \text{Neighbors} \\ 1 & 1,1 \\ 1 & 1,1 \\ 1 & 1,1,3 \\ 1 & 1,2,3 \\ 1 & 1,3,4 \\ 1 & 2,3,4 \\ 2 & 1,1 \\ 3 & 1,1,1,1 \\ 4 & 1,1 \\ \end{matrix}

Which is has changed after the transformation, ergo the transformation is non-semi-continuous (on this input).

To clarify, semi-continuity is a property of a transformation on some specific matrix.

Your code will take a matrix as input and output the number of (unique) semi-continuous transformations. Two transformations are different if the output is different. So for example swapping two identical numbers is the same as the identity transform (doing nothing).

Or in other words: Your code will take a matrix and return the number of matrices with those dimensions that have the same neighbor-list.

You can assume that the matrix has positive width and height, and also that if m is the maximum number in the matrix, then the matrix contains all numbers 1 to m inclusive. Or alternatively you can assume that if m is the maximum number, then the matrix contains all numbers from 0 to m inclusive.

Examples

[[1]] -> 1
[[1, 1], [1, 1]] -> 1
[[2, 1], [1, 2]] -> 2
[[2, 2], [1, 2]] -> 4
[[2, 1, 1], [1, 2, 1], [1, 1, 2]] -> 2
[[1, 1, 2, 1, 1, 1, 1]] -> 3
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 8
[[1, 1, 4, 7], [1, 3, 5, 6], [2, 1, 4, 5]] -> 8
[[2, 1, 1], [1, 3, 1], [1, 1, 4]] -> 4

Answer 1

JavaScript, 205 bytes

m=>(a=m.flat(w=m[o=[c=0]].length),s=a=>0+[...a].sort(),g=a=>s(a.map((v,i)=>[v,s([a[i-w],a[i+w],i%w&&a[i-1],++i%w&&a[i]])])),h=b=>b[a.length-1]?o[s(b)==s(a)&g(b)==g(a)&&b]??=++c:a.map(v=>h([...b,v]))|c)([])

Don't try any matrix larger than 2x2. As its time complexity is at least \$\Omega(wh^{wh+1})\$.

m=>(
// counter of output
c=0,
// o as a dictionary, its key is any seen transform
o=[0],
// width of input
w=m[0].length
// convert input into 1d array
a=m.flat(w),
// sort array and convert it into a string
// we don't really care what order the sort works
// as long as it works consistent
s=a=>0+[...a].sort(),
// build the neighbor list of input flatten matrix
g=a=>s(a.map((v,i)=>[
// first item its the cell value itself
v,
// and followed by its neighbors, sorted in some order
s([a[i-w],a[i+w],i%w&&a[i-1],++i%w&&a[i]])
])),
// for each possible matrix with same size and use seen numbers
h=b=>b[a.length-1]?o[
// when sort the matrix, it uses same numbers as input
s(b)==s(a)&
// its neighbor list is same as input
g(b)==g(a)&&
// if above 2 condition meets, we find out a new transform
// we use o[b] to verify if the transform we have ever seen or not
// otherwise, the expression is 0, while o[0] is initialized
b]??=
// increase the counter whenever we find out a new transform
++c:
a.map(v=>h([...b,v]))|c)([])

Answer 2

Python3, 1075 bytes:

from copy import*
from itertools import*
R=range
c=lambda x:[(j,k)for j in R(len(x))for k in R(len(x[0]))]
def n(b):
 Q={}
 for x,y in c(b):
  q=[]
  for J,K in[(0,-1),(0,1),(1,0),(-1,0)]:
   if(j:=x+J)>=0 and(k:=y+K)>=0:
    try:q+=[b[j][k]]
    except:1 
  Q[b[x][y]]=Q.get(b[x][y],[])+[sorted(q)]
 return Q
v=lambda B,N:all(all(i in N[q]for i in p)for q,p in n(B).items())
def u(b,x,y,j,I):
 q=[]
 for J,K in[(0,-1),(0,1),(1,0),(-1,0)]:
  if(j:=x+J)>=0 and(k:=y+K)>=0:
   try:q+=[(b[j][k],(j,k))]
   except:1 
 if len(q)!=len(I):return 0
 for s,(_,(j,k))in zip(I,q):
  if b[j][k] and b[j][k]!=s:return 0
  b[j][k]=s
 return b
F=lambda x:[*chain(*x)]
def r(W,b,n):
 q,S=[b],[b]
 while q:
  if all(map(all,b:=q.pop(0))):yield b;continue
  for x,y in c(b):
   if not b[x][y]:
    for j,k in n.items():
     for i in k:
      for I in permutations(i,len(i)):
       B=deepcopy(b)
       B[x][y]=j
       if(B:=u(B,x,y,j,I))and B not in S and all(F(B).count(O)<=F(W).count(O)for O in n):q+=[B];S+=[B];break
f=lambda b:sum(v(i,n(b))for i in r(b,[[0 for _ in i]for i in b],n(b)))

Try it online!

The main strategy is to produce possible transformations and then count the number of valid results.