Detect sonar imposters

Question

You are the sonar captain aboard an underwater submarine. The way sonar works is that every submarine sends out a ping at regular intervals. Each interval is a whole number of seconds. Each submarine has an identifying amplitude, that is no two submarines send out pings at the same amplitude. The amplitude is always a positive integer, so when two submarines send out pings at the same time, they constructively interfere and it appears on your ship's readout as a single ping at the sum of the amplitudes.

However, there are imposters in the deep sea. An imposter will send out pings at a different submarine's amplitude to imitate them. That means that when there's an imposter in the midst there will be two submarines pinging at the same amplitude.

If you see the following readout over a 10 second interval

0,1,1,0,1,1,0,1,1,0

Then you know there must be an imposter. The 1 pings don't occur at regular intervals. However if you see the following:

0,3,3,0,3,3,0,3,3,0

You can't be certain there's an imposter. There might be an imposter imitating the 3 submarine:

0,3,0,0,3,0,0,3,0,0
0,0,3,0,0,3,0,0,3,0

Or there might be 3 submarines with two of them interfering:

0,1,0,0,1,0,0,1,0,0
0,2,0,0,2,0,0,2,0,0
0,0,3,0,0,3,0,0,3,0

Now the interference can make things pretty complicated. Can you tell quickly whether there's an imposter in the following readout:

5,7,5,3,9,4,5,7

It's possible, but it's also possible there's no imposter:

0,4,0,0,4,0,0,4
3,3,3,3,3,3,3,3
0,0,0,0,0,1,0,0
2,0,2,0,2,0,2,0

So you'd like to write a computer program which takes a readout and tells you quickly, without having to do any working by hand, whether there is definitely an imposter.

Task

Given a readout of your submarine's sonar as a list of non-negative integers, output a value if there is definitely an imposter, and output a different distinct value otherwise.

Your submarine is under a lot of pressure so your code should be pressurized as well. This is code-golf the goal is to minimize the size of your source code as measured in bytes.

Test cases

Imposter

[0,1,1,0,1,1,0,1,1,0]
[0,1,1]
[1,1,2]
[9,2,8,7,3,6,1,1]
[9,10,7,3,8,8,2,2]
[2,9,2,6,1]

Maybe imposter

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

Answer 1

Python, 180 173 169 166 bytes

-7 bytes thanks to @gsitcia
-3 bytes thanks to @naffetS

lambda a,r=range:(l:=len(a))!=a in[[*map(sum,zip(*s))]for s in product(*[[((*i//l*[0],-~p)*l)[i%l:i%l+l]for i in r(l*l+1)]for p in r(max(a))])]
from itertools import*

Attempt This Online!

Very inefficient for inputs with larger maximum values.

Brute force solution -- goes through every set of submarines which does not contain an imposter and checks if any of them produce the given input.

Answer 2

JavaScript (ES10), 198 bytes

Returns true for imposter or false for maybe imposter.

Looks like this code could be pressurized some more...

f=([v,...a],c=[],F=(n,l=[],i=1)=>n?i>n||F(n-i,[i,...l],++i)&&F(n,l,i):f(a,[...c,l]))=>v+1?F(v):c.flat().some(v=>(m=(s=c.map(l=>l.includes(v)|!++a).join``).match(/(10*)1/))&&!m[1].repeat(a).match(s))

Try it online!

Answer 3

Python3, 677 bytes:

lambda b:next(C(b),0)!=0
R,T,U,M=range,sorted,lambda x:''.join(map(str,x)).lstrip('0'),lambda r,k:any(all(j==K for j,K in zip(U(i),U(k)))for i in r)
def C(b):
 q,S=[([],0)],[]
 while q:
  r,c=q.pop(0);L=len(b)
  if all(a==sum(j)for a,j in zip(b,zip(*r)))and r:yield r
  if c==L:continue
  if not b[c]:q+=(r,c+1),;continue
  for i in{*R(1,b[c]+1)}-{j for k in r for j in k}:
   for g in R(1,L+1):
    k=[0]*L;k[c]=i;I=1
    while I*g+c<L or-I*g+c>=0:
     if-I*g+c>=0:k[-I*g+c]=i
     if I*g+c<L:k[I*g+c]=i
     I+=1
    if all(a>=sum(j)for a,j in zip(b,zip(*r+[k])))and not M(r,k)and T(r+[k])not in S:
     q+=(K:=r+[k],c+1),;S+=T(K),
     if b[c]>sum(j[c]for j in K):q+=(K,c),

Try it online!

Answer 4

Python, 157 155 bytes

-2 bytes thanks to @97.100.97.109

f=lambda p,n=1:all(x>=0for x in p)and(sum(p)<1or n<=max(p)and any(f([p-n*(i%h==o)for i,p in enumerate(p)],n+1)for h in range(1,len(p)+2)for o in range(h)))

Attempt This Online!

Answer 5

Desmos, 220 bytes

m=l.max
g(N,K,b)=mod(floor(bN/b^{[1...K]}),b)
A=[1...m][g(a,m,2)=1]
L=l.length
B=A.length
P=g(p,B,L)+1
M=P.max
f(l)=0^{∑_{a=1}^{2^m}∑_{p=0}^{L^B}∑_{d=0}^{M^B}0^{∑_{i=1}^L(total(0^{mod(i-g(d,B,M)-1,P)}A)-l[i])^2}}

Guys please tell me if there is anything wrong... I have spent a while planning out this answer (I literally wrote out all my steps on a txt file before doing any of the desmos coding lol) but I may have missed some crucial details.

Because of the very inefficient brute force methods used in this answer, it can only handle the smallest of test cases, so I went ahead to make some of my own. I did test those new test cases against other answers here to compare and they seem to match, so this gives me a little more confidence that this answer should mostly be correct. The test cases given in the question that the code could run in a reasonable amount of time also do match as well.

As an aside, it actually did not come out as long as I expected; I was expecting at least 300 bytes when I initially started planning this out.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 6

Scala, 202 bytes.

Golfed version. Try it online!

def f(p:List[Int],n:Int=1):Boolean=p.forall(_>=0)&&(p.sum<1||(n<=p.max&&{for(h<-1 to p.length+1;o<-0 until h)yield f(p.zipWithIndex.map{case(p,i)=>p-n*((i%h==o).compare(false))},n+1)}.exists(identity)))

Ungolfed version. Try it online!

object Main {
  def f(p: List[Int], n: Int = 1): Boolean = {
    def helper(p: List[Int], h: Int, o: Int, n: Int): Boolean = {
      val updatedP = p.zipWithIndex.map { case (p, i) => p - n * (if((i % h == o))1 else 0) }
      f(updatedP, n + 1)
    }
    p.forall(_ >= 0) && (p.sum < 1 || (n <= p.max && (for (h <- 1 to p.length + 1; o <- 0 until h) yield helper(p, h, o, n)).exists(identity)))
  }

  def main(args: Array[String]): Unit = {
    val tests = List(
      List(0, 1, 1, 0, 1, 1, 0, 1, 1, 0),
      List(0, 1, 1),
      List(1, 1, 2),
      List(2, 9, 2, 6, 1),
      List(),
      List(9),
      List(9, 9),
      List(9, 9, 9),
      List(9, 9, 9, 9),
      List(0, 3, 3),
      List(3, 1, 1)
    )

    for (x <- tests) {
      if (x.isEmpty)
        println()
      else
        println(f(x))
    }
  }
}