26
\$\begingroup\$

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 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]
\$\endgroup\$

6 Answers 6

8
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ I think the inner loop should be [((*i//l*[0],-~p)*l)[i%l:i%l+l]for i in r(l*l)] instead of [((*i//n*[0],-~p)*l)[i%n:i%n+l]for i in r(n*n)] (swap n with l). If so I think you can get rid of [(0,)*l]+ by changing r(l*l) to r(l*l+1). link \$\endgroup\$
    – gsitcia
    Mar 25, 2023 at 3:14
  • \$\begingroup\$ 166 \$\endgroup\$
    – naffetS
    Mar 26, 2023 at 14:08
7
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
8
  • 2
    \$\begingroup\$ You can be more careful with your spacing here. Both places you compare sum(j) you can place the sum on the right side to remove a space. There's also other places where it seems like you could cut down on spacing by reordering things. \$\endgroup\$
    – Wheat Wizard
    Mar 24, 2023 at 17:51
  • 1
    \$\begingroup\$ @TheThonnu Thank you, updated. \$\endgroup\$
    – Ajax1234
    Mar 24, 2023 at 18:11
  • 1
    \$\begingroup\$ 686 \$\endgroup\$
    – The Thonnu
    Mar 24, 2023 at 20:23
  • 1
    \$\begingroup\$ 677 \$\endgroup\$
    – The Thonnu
    Mar 25, 2023 at 13:06
  • 1
    \$\begingroup\$ You can replace -I*g+c with c-I*g. It saves bytes in one place. \$\endgroup\$
    – Wheat Wizard
    Mar 25, 2023 at 20:12
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Because the method calls itself (f), you also need to include the f= in the byte count. However, you can change range(0,h) to range(h) which saves two bytes, so the byte count is unchanged. \$\endgroup\$ Mar 27, 2023 at 20:06
  • \$\begingroup\$ @97.100.97.109 thank you! \$\endgroup\$
    – matteo_c
    Mar 28, 2023 at 11:03
1
\$\begingroup\$

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

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

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))
    }
  }
}

\$\endgroup\$

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.