Tricky Timers

We basically just need the information of the non-zero timers. Since $0$ timers that are defective are indistinguishable from $0$ timers that have not been yet activated, then they can't give any information about the current hour.

Let $A=\{a_1,a_2,...,a_{1000}\}$ the set of activation times, and $B=\{b_1,b_2,...,b_k\}$ the set of non-zero timers, and $C=\{c_1,c_2,...,c_k\}$ , the activation times that each timer $b_i$ is matched to. Obviously $C \subset A$ . WLOG, $B$ is ordered in the following way: $b_1 \ge b_2 \ge ... \ge b_k$

Now, since every clock counts the time at the same speed, and $\text{Activation time } + \text{Timer's time} = \text{Current Time}$ , we must have that $b_1+c_1 = b_2+c_2 = ... = b_k +c_k$ .

With those equalities we can see that for all $2 \le i \le k$ $c_k = c_1 + b_1 - b_k$

Since, $c_1$ is one of the activation times, we can choose some element of $A$ and assume it is $c_1$ , and then construct the rest of $C$ with the chosen $c_1$ and the above equality. We can then check if $C \subset A$ , to see if it's a valid choice of $c_1$ . The first time that happens, we found a correct match, and we can just output $b_1+c_1$ as the current time, since we can assume the current time can be uniquely determined.

Of course, we can check the subset and construct $C$ at the same time as a minor optimization.

Here is my Python 3 code:

with open("tricky_timers.txt") as problem:
    problem_input = [int(x) for x in problem]    

times = set(problem_input[:1000])
timers = list(filter(lambda x: x!= 0,reversed(sorted(problem_input[1000:]))))    

def matches(time):
    for b in timers[1:]:
        if time + timers[0] - b not in times:
            return False    

    return time + timers[0]    

for time in times:
    candidate = matches(time)
    if candidate != False:
        print(candidate)

The current time will be the sum of timer corresponding to its written time. The current time can't be found explicitly. So, we take one of the many values of timer and add it with all the values of written times. One of these sums will be the current time. Then we take another element and add it will all the values of written times. We, compare this list of sums with previous list and see if any sum is common. We do this till we find one sum which is common with all such list and that would be the current time.

I have done the above thing down below using the Python lang. It's not very clear and done in very unprofessional way but still, here it is:

data = open('tricky_timers.txt', 'r') # Opening the file
allLines = [num.rstrip() for num in data] # making a list of given numbers
allLines = map(int, allLines) # convert each str to int in list of numbers

times = [] # this will store the random times from 0 to 1000
for i in range(1000):
    times.append(allLines[i])

validTimers = [] # this will store the value of timers which aren't defective
for i in range(1000, 2000):
    if allLines[i] != 0:
        validTimers.append(allLines[i])

# temp1 to temp4 will store sum of first four element of validTimers with all times        
temp1 = []
temp2 = []
temp3 = []
temp4 = []

for a in times:
    temp1.append(a + validTimers[0])
for a in times:
    temp2.append(a + validTimers[1])
for a in times:
    temp3.append(a + validTimers[2])
for a in times:
    temp4.append(a + validTimers[3])
commonSum = [] # this will store the elements which are common in all temp's
for i in temp1:
    if i in temp2 and i in temp3 and i in temp4:
        commonSum.append(i)

print commonSum

Nice Problem!Obviously the sum of any time listed by Jacks Parents and any timer time must add up to the current time.This is of course unless the timer is defective. So I just ignored all 0 timer times and found unique sums that sum up to the current time and checked if they fit.

I first check all possible times using the sum of the timers and list of times.I then associate each possible time with the timer times that can sum up to it.I do this by putting the timer times for that possible answer in a list. If at the end,this list is exactly the same as the given timer times then that possible time is our answer.The algorithm is $O (timer \times times)$

Code in python:

with open('tricky_timers.txt','r') as tt:
        All = map(int,tt.read().split('\n'))
        Times , Timers = All[0:len(All)/2] , All[len(All)/2::]

Lookup = sorted(list(set(Timers)))[1::]
Dict = dict()
for time in Times:
        for timer in Timers:
                if timer == 0:continue
                Possible_Time = time + timer
                try:
                        Dict[Possible_Time].append(timer)
                        Dict[Possible_Time].sort()
                except KeyError:
                        Dict[Possible_Time] = [timer]


for i in Dict:
        if Dict[i] == Lookup:
                print i

For the sake of shortness, I'm skipping the gory details of handling the input data. Let's assume we have a list timers which stores the $2000$ integers provided in the question. We split it into two parts: original and dummy , where original stores the first $1000$ integers and dummy stores the last $1000$ integers.

original= timers[:1000]
dummy= timers[-1000:]

We make another list, another , which stores the non-zero values of dummy .

another = [i for i in dummy if i != 0]

Here comes the crucial step. Note that the largest element of original which doesn't get assigned to a faulty timer must be associated with the smallest element of another . However, since we don't know which element gets assigned to a faulty timer, we keep on checking with the largest element of original . To be precise, we define L= max(original) , K= min(another) , and n= K+L . A system will be valid if and only if $\forall \ x \in \text{another}, \ n-x \in \text{original}$ . We now declare a loop, which runs $1000$ times. Each time it runs, it checks whether the system is valid assuming the largest element of original is paired with the smallest element of another . The Boolean val is True if the system is valid, and False otherwise. The list listofvalues stores the values of val at each step. Once a check is complete, the largest element of original gets appended to the list listofnumbers , and then removed from original , and the loop runs again.

K= min(another)
listofvalues= []
listofnumbers= [] 
for k in range(1000):

  L= max(original)
  n= K+L

  val= True
  for x in range(len(another)):
   if n-another[x] not in original:
      val= False
  listofvalues.append(val)
  listofnumbers.append(L)
  original.remove(L)
  k+=1

Now, note that the time will be unique iff there is exactly one True stored in listofvalues . We iterate over this list to find out how many True values it has. If it has exactly $1$ True , we iterate over listofnumbers to find out the corresponding time on the original timers, and add it to the minimum value stored in another .

if listofvalues.count(True)==1:
  for i in range(len(listofvalues)):
    if listofvalues[i]==True:
      print listofnumbers[i]+K
else:
  print "https://i.imgur.com/QFyLFRR.jpg"

This prints $790480$ , whose last three digits are $\boxed{480}$ .

The following algorithm check the matching conditions counting on the sorted lists of times and timers (reversed order):

#include <iostream>
#include <stdlib.h>

void quickSort(int *v, int first, int last) {
int start[2], end[2], pivot, i;
int temp;

if (first < last) {
 start[1] = first;
 end[0] = last;
 pivot = v[(first + last) / 2];
 while (start[1] <= end[0]) {
   while (v[start[1]] > pivot)
     start[1]++;
   while (pivot > v[end[0]])
     end[0]--;
   if (start[1] <= end[0]) {
     temp = v[start[1]];
     v[start[1]] = v[end[0]];
     v[end[0]] = temp;
     start[1]++;
     end[0]--;
   }
 }
 start[0] = first;
 end[1]   = last; 

 quickSort(v, start[0], end[0]);
 quickSort(v, start[1], end[1]);
  }
}

int main(int argc, char** argv) {
int times[1000];
int timers[1000];
char s[20]; int i=0;

FILE* f = fopen("input.txt", "r");
while(fgets(s, sizeof(s)-1, f)){
  if (i<1000){
    times[i] = atoi(s);
  } else {
    timers[i%1000] = atoi(s);
  }
  i++;
}
fclose(f);

quickSort(timers, 0, 999);

i=0;
int tot, j=0, k, p;

while(i<1000){   
tot = times[i] + timers[j];
printf("\ncurrent total=%d composed by times[%d]=%d and timers[%d]=%d", tot, i, times[i], j, timers[j]);
k=i+1; p=j+1;

while(timers[p] != 0 && p<1000){ 
  while(k<1000 && (times[k] + timers[p] <= tot)) k++;
  if (times[k-1] + timers[p] == tot){
    printf("\ntimes[%d]=%d + timers[%d]=%d = %d", k-1, times[k-1], p, timers[p], tot);
    p++;
  } else {
  printf("\ntimes[%d]=%d + timers[%d]=%d = %d <> %d ", k-1, times[k-1], p, timers[p], times[k-1] + timers[p], tot) ;
  break;
  }
}
if (timers[p]==0) {
printf("\nsolution found.");
break;
}
i++;j=0;
}
printf("\ntotal=%d", tot);

return 0;
}

The output:

current total=783378 composed by times[0]=1367 and timers[0]=782011
times[6]=7441 + timers[1]=775131 = 782572 <> 783378
current total=784842 composed by times[1]=2831 and timers[0]=782011
times[7]=8469 + timers[1]=775131 = 783600 <> 784842
current total=786143 composed by times[2]=4132 and timers[0]=782011
times[10]=10970 + timers[1]=775131 = 786101 <> 786143
current total=787368 composed by times[3]=5357 and timers[0]=782011
times[10]=10970 + timers[1]=775131 = 786101 <> 787368
current total=787876 composed by times[4]=5865 and timers[0]=782011
times[11]=12604 + timers[1]=775131 = 787735 <> 787876
current total=788000 composed by times[5]=5989 and timers[0]=782011
times[11]=12604 + timers[1]=775131 = 787735 <> 788000
current total=789452 composed by times[6]=7441 and timers[0]=782011
times[13]=13671 + timers[1]=775131 = 788802 <> 789452
current total=790480 composed by times[7]=8469 and timers[0]=782011
times[16]=15349 + timers[1]=775131 = 790480
times[23]=20607 + timers[2]=769873 = 790480
times[31]=28711 + timers[3]=761769 = 790480
times[40]=40472 + timers[4]=750008 = 790480
times[46]=53255 + timers[5]=737225 = 790480
times[58]=65250 + timers[6]=725230 = 790480
times[78]=85723 + timers[7]=704757 = 790480
times[93]=99580 + timers[8]=690900 = 790480
times[112]=118557 + timers[9]=671923 = 790480
times[129]=134684 + timers[10]=655796 = 790480
times[136]=139021 + timers[11]=651459 = 790480
times[150]=154298 + timers[12]=636182 = 790480
times[168]=174492 + timers[13]=615988 = 790480
times[183]=186825 + timers[14]=603655 = 790480
times[194]=200591 + timers[15]=589889 = 790480
times[206]=218622 + timers[16]=571858 = 790480
times[216]=224459 + timers[17]=566021 = 790480
times[236]=244402 + timers[18]=546078 = 790480
times[251]=264868 + timers[19]=525612 = 790480
times[257]=269763 + timers[20]=520717 = 790480
times[268]=276302 + timers[21]=514178 = 790480
times[287]=294996 + timers[22]=495484 = 790480
times[301]=309580 + timers[23]=480900 = 790480
times[311]=315626 + timers[24]=474854 = 790480
times[316]=321841 + timers[25]=468639 = 790480
times[328]=332087 + timers[26]=458393 = 790480
solution found.
total=790480