Sinking the Submarine Puzzle

So every now and then one comes across some puzzle which makes you delve deep into number theory and though things appear weird at the start, they end up being deterministic... or precisely certainly solvable though in infinity !!

Here is the "Sinking the Submarine" problem -

[I got this puzzle from Alex Mikhailov and a little help from Yuval]

An enemy submarine is somewhere on the number line (consider only integers for this problem). It is moving at some rate (again, integral units per minute). You know neither its position nor its velocity. You can launch a torpedo each minute at any integer on the number line. If the the submarine is there, you hit it and it sinks. You have all the time and torpedoes you want. You must sink this enemy sub - devise a strategy that is guaranteed to eventually hit the enemy sub.

Solution :-

Looking at the problem, one feels a simple strategy can help us reach the solution. But then one goes into asking random questions, like 

- Do we know the initial position?

- Should we even care about the initial position?

Remember that the submarine does not have an acceleration. So atleast, some randomness has already been constrained. So, lets go about proving that the submarine can be sinked certainly.

In this puzzle, we have combination of values for velocity and displacement of submarine on the number line based on a function between initial position and velocity. Remember, that the speed(velocity) remains constant. So, the submarine would be travelling the same distance between time t0 to t1 as it would between time t1 and t2.

The possible values of velocity are 0,1,2,..... infinity

The possible values of starting displacement are 0,1,2,...infinity.

So, we need to traverse the combinations of starting displacement and velocity in such a way that we hit the submarine somewhere before infinity. Using a simple function, such as 
currentPostion = startingDisplacement + (time * velocity) 
we can brute force each combination value and sink the submarine before infinity.
Here is one of the lame ways to iterate over all possible combinations of velocity and time

Had some free time, so decided to code it in.

1: import java.util.Scanner;
2: 
3: public class SinkTheSubmarine {
4:
5: public static void printNumShotsRequired(long startPosition, long velocity) {
6:  if (startPosition == 0 && velocity == 0) {
7:   System.out.println("Submarine hit on 1 attempt"); 
8:   return;
9:  } 
10:  long subPosition = startPosition;
11:  long time = 1;
12:  long startDisp = 0;
13:  long vel = 0;
14:  long shotPosition = 0;
15:  boolean hit = false;
16:  boolean changeStartDisp = false;
17:  boolean changeVel = false;
18:  
19:  startDisp++;
20:  changeStartDisp=true;
21:  do { 
22:   System.out.println("startDisp:"+startDisp+" vel:"+vel);
23:   subPosition = startPosition + (time * velocity);
24:   shotPosition = startDisp + (time * vel);
25:   if (shotPosition == subPosition) {
26:    System.out.println("Submarine hit on " + (time + 1) + " attempt"); 
27:    hit = true;
28:   }
29:   if (changeStartDisp && !changeVel) {
30:    if (startDisp == 0) {
31:     //Move down
32:     vel++;
33:     changeStartDisp = false;
34:     changeVel = true;
35:    } else {
36:     //Move left bottom
37:     vel++;
38:     startDisp--;
39:    }
40:   }else if(!changeStartDisp && changeVel) {
41:    if (vel == 0) {
42:     //Move right
43:     startDisp++;
44:     changeStartDisp = true;
45:     changeVel = false;
46:    } else {
47:     //Move right up
48:     startDisp++;
49:     vel--;
50:    }
51:   }  
52:   time++;
53:  } while(!hit);
54:  return;
55: }
56: 
57: public static void main(String[] args) {
58:  Scanner scanner = new Scanner(System.in);
59:  System.out.println("Enter starting location of submarine:");
60:  long startstartDisplacement = scanner.nextInt();
61:  System.out.println("Enter velocity of submarine:");
62:  long velocity = scanner.nextInt();
63:  System.out.println(startstartDisplacement + " " + velocity);
64:  printNumShotsRequired(startstartDisplacement, velocity);
65: }
66:}

Remember, that if we had acceleration in the picture, then we would have to change our function with something like Newton's second law of motion -
s = ut + (at²/2)

and will have to iterate over combinations for starting displacement, velocity and acceleration and hence, even in that case, sinking the submarine is a certainty.