80.0% ≤ sim ≤ 100%

HW05

get_coordinates,get_all_unjabbed_pairs,first_hop,get_adjacency_set,get_infectable_ids,get_all_clusters: 8 clusters, 16 submissions

>> cluster #1(2)
# 6530054521 (point = 94.44%) sim = 100%
def get_coordinates(population, vaccinated):
    ans={}
    for e in population:
        if e['vaccinated']==vaccinated:
            ans[e['id']]=e['coordinate']
    return ans
def get_all_unjabbed_pairs(population, radius):
    ans=[]
    coo = []
    coor = get_coordinates(population, False)
    for e in coor:
        coo.append([e,coor[e]])
    coo.sort()
    coor = {}
    for e in coo:
        coor[e[0]]=e[1]
    for e in coor:
        for l in coor:
            if e!=l:
                x1,y1=coor[e]
                x2,y2=coor[l]
                if ((x2-x1)**2+(y2-y1)**2)<=radius**2:
                   ans.append((e,l))
    ans=sorted(ans)
    answer=[]
    for e in ans:
        answer.append(e)
    for i in range(len(ans)-1):
        for j in range(i+1,len(ans)):
            a,b=ans[i][0],ans[i][1]
            c,d=ans[j][0],ans[j][1]
            if a==d and b==c:
                answer.remove(ans[j])
    return answer
def first_hop(population, id, radius): 
    anss=[]
    for o in range(len(population)):
        if population[o]['id']==id:
            co=population[o]['coordinate']
            co1,co2=co[0],co[1]
    for i in range(len(population)-1):
        if population[i]['id']!=id:
            if population[i]['vaccinated']==False:
                a=population[i]['coordinate']
                c=population[i]['id']
                x1,y1=a[0],a[1]
                if (x1-co1)**2+(y1-co2)**2<=radius**2:
                    anss.append(c)
    anss=sorted(anss)
    return anss
def get_adjacency_set(pairs):
    di={}
    for e in pairs:
        if e[0] not in di:
            di[e[0]]={e[1]}
        else:
            di[e[0]]|={e[1]}
        if e[1] not in di:
            di[e[1]]={e[0]}
        else:
            di[e[1]]|={e[0]}
    return di
def get_infectable_ids(pairs,seed):
    x=get_adjacency_set(pairs)
    output=[]
    f=[seed]
    while f!=[]:
        p=f.pop(0)
        output.append(p)
        if p in x:
           for e in x[p]:
              if e not in output:
                  f.append(e)
    ans=set(output)
    return ans
def get_all_clusters(pairs):
    y=[]
    k=[]
    ans=[]
    answer=[]
    for e in pairs:
        for o in e:
            if o!=[] and o not in k:
                k.append(o)
    k=sorted(k)
    for seed in k:
        x=get_infectable_ids(pairs,seed)
        if x not in ans:
            ans.append(x)
    return ans
# 6530026021 (point = 94.44%) sim = 100%
def get_coordinates(population, vaccinated):
    d = {}
    for i in population :
        if i['vaccinated'] == vaccinated :
            d[i['id']] = i['coordinate']
    return d
def get_all_unjabbed_pairs(population, radius):
    ans = []
    coo = []
    gee = get_coordinates(population, False)
    for e in gee:
        coo.append([e,gee[e]])
    coo.sort()
    gee = {}
    for e in coo:
        gee[e[0]] = e[1]
    for e in gee:
        for l in gee:
            if e!= l: 
                x1,y1 = gee[e]
                x2,y2 = gee[l]
                if ((x2-x1)**2+(y2-y1)**2) <= radius**2:
                   ans.append((e,l))
    ans = sorted(ans)
    sea = []
    for e in ans:
        sea.append(e)
    for i in range(len(ans)-1):
        for j in range(i+1,len(ans)):
            a,b=ans[i][0],ans[i][1]
            c,d=ans[j][0],ans[j][1]
            if a == d and b == c:
                sea.remove(ans[j])
    return sea
def first_hop(population, id, radius): 
    anss=[]
    for o in range(len(population)):
        if population[o]['id']==id:
            co=population[o]['coordinate']
            co1,co2=co[0],co[1]
    for i in range(len(population)-1):
        if population[i]['id']!=id:
            if population[i]['vaccinated']==False:
                a=population[i]['coordinate']
                c=population[i]['id']
                x1,y1=a[0],a[1]
                if (x1-co1)**2+(y1-co2)**2<=radius**2:
                    anss.append(c)
    anss=sorted(anss)
    return anss
def get_adjacency_set(pairs):
    d={}
    for e in pairs:
        if e[0] not in d:
            d[e[0]]={e[1]}
        else:
            d[e[0]]|={e[1]}
        if e[1] not in d:
            d[e[1]]={e[0]}
        else:
            d[e[1]]|={e[0]}
    return d
def get_infectable_ids(pairs,seed):
    x=get_adjacency_set(pairs)
    output=[]
    f=[seed]
    while f!=[]:
        p=f.pop(0)
        output.append(p)
        if p in x:
           for e in x[p]:
              if e not in output:
                  f.append(e)
    ans=set(output)
    return ans
def get_all_clusters(pairs):
    y = []
    k = []
    ans=[]
    answer=[]
    for e in pairs:
        for o in e:
            if o!=[] and o not in k:
                k.append(o)
    k=sorted(k)
    for seed in k:
        x=get_infectable_ids(pairs,seed)
        if x not in ans:
            ans.append(x)
    return ans

>> cluster #2(2)
# 6530124821 (point = 83.33%) sim = 99%
def get_coordinates(population, vaccinated):
  v = vaccinated
  a = []
  for i in range(len(population)):
    if population[i]['vaccinated'] == v:
      a.append(population[i])
  b = {}
  for i in range(len(a)):
    c = a[i]['id']
    d = a[i]['coordinate']
    b[c] = d
  return b
def get_all_unjabbed_pairs(population, radius):
  a = []
  for i in range(len(population)):
    if population[i]['vaccinated'] == False:
      a.append(population[i])
  e = []
  for i in range(len(a)):
    if i < len(a)-1:
      x, y = a[i]['coordinate']
      x1, y1 = a[i]['coordinate']
    else:
      x, y = a[i]['coordinate']
      x1, y1 = a[0]['coordinate']
    d = (((x1-x)**2)+((y1-y)**2))**0.5
    if d <= radius:
      e.append(a[i])
    else:
      pass
  b = []
  for i in range(len(e)):
    c = []
    if i < len(e)-1:
      c.append(e[i]['id'])
      c.append(e[i+1]['id'])
    else:
      c.append(e[i]['id'])
      c.append(e[0]['id'])
    b.append(c)
  for i in range(len(b)):
    b[i].sort()
  b.sort()
  for i in range(len(b)):
    b[i] = tuple(b[i])
  return b
def first_hop(population, id, radius):
  a = []
  for i in range(len(population)):
    if population[i]['vaccinated'] == False:
      a.append(population[i])
  for i in range(len(population)):
    if id == population[i]['id']:
      index = int(i)
  e = []
  for i in range(len(population)):
    x, y = population[i]['coordinate']
    x1, y1 = population[index]['coordinate'] 
    d = (((x1-x)**2)+((y1-y)**2))**0.5
    if d == 0:
      pass
    elif d <= radius:
      e.append(population[i])
    else:
      pass
  f = []
  for n in e:
    if n in a:
      f.append(n)
    else:
      pass
  out = []
  for i in range(len(f)):
    out.append(f[i]['id'])
    out.sort()
  return out
def get_adjacency_set(pairs):
  a = []
  out = {}
  for i in range(len(pairs)):
    b1, b2 = pairs[i][0], pairs[i][1]
    if b1 not in a:
      a.append(b1)
    if b2 not in a:
      a.append(b2)
  for i in a:
    t = set()
    for b in pairs:
      if (b[0] == i):
        t.add(b[1])
      elif (b[1] == i):
        t.add(b[0])
    out[i] = t
  return out
def get_infectable_ids(pairs,seed):
  a = get_adjacency_set(pairs)
  out = set()
  f = [seed]
  while len(f) != 0:
    p = f.pop(0)
    out.add(p)
    for i in list(a[p]):
      if i not in out:
        f.append(i)
  return out
def get_all_clusters(pairs):
  an = []
  d = get_adjacency_set(pairs)
  for key in d:
    c = get_infectable_ids(pairs,key)
    if c not in an:
      an += [c]
      pass
    else:
      pass
  return an
# 6530025321 (point = 83.33%) sim = 99%
def get_coordinates(population, vaccinated) :
  v = vaccinated
  a = []
  for i in range(len(population)) :
    if population[i]['vaccinated'] == v :
      a.append(population[i])
  b = {}
  for i in range(len(a)) :
    c = a[i]['id']
    d = a[i]['coordinate']
    b[c] = d
  return b
def get_all_unjabbed_pairs(population, radius) :
  a = []
  for i in range(len(population)) :
    if population[i]['vaccinated'] == False :
      a.append(population[i])
  e = []
  for i in range(len(a)) :
    if i < len(a)-1 :
      x, y = a[i]['coordinate']
      x1, y1 = a[i]['coordinate']
    else :
      x, y = a[i]['coordinate']
      x1, y1 = a[0]['coordinate']
    d = (((x1-x)**2)+((y1-y)**2))**0.5
    if d <= radius :
      e.append(a[i])
    else :
      pass
  b = []
  for i in range(len(e)) :
    c = []
    if i < len(e)-1 :
      c.append(e[i]['id'])
      c.append(e[i+1]['id'])
    else :
      c.append(e[i]['id'])
      c.append(e[0]['id'])
    b.append(c)
  for i in range(len(b)) :
    b[i].sort()
  b.sort()
  for i in range(len(b)) :
    b[i] = tuple(b[i])
  return b
def first_hop(population, id, radius) : 
  a = []
  for i in range(len(population)) :
    if population[i]['vaccinated'] == False :
      a.append(population[i])
  for i in range(len(population)) :
    if id == population[i]['id'] :
      index = int(i)
  e = []
  for i in range(len(population)) :
    x, y = population[i]['coordinate']
    x1, y1 = population[index]['coordinate'] 
    d = (((x1-x)**2)+((y1-y)**2))**0.5
    if d == 0 :
      pass
    elif d <= radius :
      e.append(population[i])
    else :
      pass
  f = []
  for n in e :
    if n in a :
      f.append(n)
    else :
      pass
  out = []
  for i in range(len(f)) :
    out.append(f[i]['id'])
    out.sort()
  return out
def get_adjacency_set(pairs) :
  a = []
  out = {}
  for i in range(len(pairs)) :
    b1, b2 = pairs[i][0], pairs[i][1]
    if b1 not in a :
      a.append(b1)
    if b2 not in a :
      a.append(b2)
  for i in a :
    t = set()
    for b in pairs :
      if (b[0] == i) :
        t.add(b[1])
      elif (b[1] == i) :
        t.add(b[0])
    out[i] = t
  return out
def get_infectable_ids(pairs,seed) :
  a = get_adjacency_set(pairs)
  out = set()
  f = [seed]
  while len(f) != 0 :
    p = f.pop(0)
    out.add(p)
    for i in list(a[p]) :
      if i not in out :
        f.append(i)
  return out
def get_all_clusters(pairs) :
  an = []
  d = get_adjacency_set(pairs)
  for key in d :
    c = get_infectable_ids(pairs,key)
    if c not in an:
      an.append(c)
      pass
    else :
      pass
  return an

>> cluster #3(2)
# 6530398421 (point = 100.0%) sim = 92%
def get_coordinates(population, vaccinated):
  answer_dict = {}
  for e in population:
    if(vaccinated==e['vaccinated']):
      answer_dict[e['id']] = e['coordinate']
  return  answer_dict
def get_all_unjabbed_pairs(population, radius):
  ans = []
  for i in range(len(population)):
    dic1 = population[i]
    if(dic1['vaccinated']==True):
      continue
    for j in range(i+1,len(population)):   
      dic2 = population[j]
      if(dic2['vaccinated']==True):
        continue
      x1 = dic1['coordinate'][0]
      y1 = dic1['coordinate'][1]
      x2 = dic2['coordinate'][0]
      y2 = dic2['coordinate'][1]
      if(radius**2 >= (x1-x2)**2 + (y1-y2)**2):
        if(dic1['id']<dic2['id']):
          ans.append((dic1['id'],dic2['id']))
        else:
          ans.append((dic2['id'],dic1['id']))
  ans.sort()
  return ans
def first_hop(population, id, radius): 
  ans =[]
  pair = get_all_unjabbed_pairs(population, radius)
  print(pair)
  for e in pair:
    if(e[0]==id):
      ans.append(e[1])
    if(e[1]==id):
      ans.append(e[0])
  ans.sort()
  return ans
def get_adjacency_set(pairs):
  now=[]
  for e in pairs:
    if(not e[0] in now):
      now.append(e[0])
    if(not e[1] in now):
      now.append(e[1])
  now.sort()
  ans={}
  for e in now:
    ans[e]=set()
    for k in pairs:
      if(e==k[0]):
        ans[e].add(k[1])
      if(e==k[1]):
        ans[e].add(k[0])
  return  ans
def get_infectable_ids(pairs,seed):
  path = get_adjacency_set(pairs)
  f = [seed]
  res = set()
  while(len(f)>0):
    now = f[0]
    f.pop(0)
    res.add(now)
    for e in path[now]:
      if(not e in res):
        f.append(e)
  return  res
def get_all_clusters(pairs):
  cou = []
  res = []
  for e in pairs:
    if(not e[0] in cou):
      now = get_infectable_ids(pairs,e[0])
      res.append(now)
      for k in now:
        cou.append(k)
    if(not e[1] in cou):
      now = get_infectable_ids(pairs,e[1])
      res.append(now)
      for k in now:
        cou.append(k)
  return res
# 6530080821 (point = 100.0%) sim = 92%
def get_coordinates(population, vaccinated):
  ans = {}
  for e in population:
    if(e['vaccinated']==vaccinated):
      ans[e['id']] = e['coordinate']
  return  ans
def get_all_unjabbed_pairs(population, radius):
  ans = []
  for i in range(len(population)):
    e1 = population[i]
    if(e1['vaccinated']==False):
      for j in range(i+1,len(population)):   
        e2 = population[j]
        if(e2['vaccinated']==True):
          continue
        x1 = e1['coordinate'][0]
        y1 = e1['coordinate'][1]
        x2 = e2['coordinate'][0]
        y2 = e2['coordinate'][1]
        if(radius**2 >= (x1-x2)**2 + (y1-y2)**2):
          if(e1['id']<e2['id']):
            a=e1['id']
            b=e2['id']
          else:
            a=e2['id']
            b=e1['id']
          ans.append((a,b))
  ans.sort()
  return ans
def first_hop(population, id, radius): 
  ans =[]
  ch = get_all_unjabbed_pairs(population, radius)
  for e in ch:
    if(e[0]==id):
      ans.append(e[1])
    if(e[1]==id):
      ans.append(e[0])
  ans.sort()
  return ans
def get_adjacency_set(pairs):
  ch=[]
  for e in pairs:
    if(not e[0] in ch):
      ch.append(e[0])
    if(not e[1] in ch):
      ch.append(e[1])
  ch.sort()
  ans={}
  for e in ch:
    ans[e]=set()
    for k in pairs:
      if(e==k[0]):
        ans[e].add(k[1])
      if(e==k[1]):
        ans[e].add(k[0])
  return  ans
def get_infectable_ids(pairs,seed):
  path = get_adjacency_set(pairs)
  f = [seed]
  ans = set()
  while(len(f)>0):
    now = f[0]
    f.pop(0)
    ans.add(now)
    for e in path[now]:
      if(not e in ans):
        f.append(e)
  return  ans
def get_all_clusters(pairs):
  mark = []
  ans = []
  for e in pairs:
    if(not e[0] in mark):
      ch = get_infectable_ids(pairs,e[0])
      ans.append(ch)
      for k in ch:
        mark.append(k)
    if(not e[1] in mark):
      ch = get_infectable_ids(pairs,e[1])
      ans.append(ch)
      for k in ch:
        mark.append(k)
  return ans

>> cluster #4(2)
# 6530088921 (point = 100.0%) sim = 86%
def get_coordinates(population, vaccinated):
    out = {}
    for i in population:
        id = i['id']; vac = i['vaccinated']; coor = i['coordinate']
        if vac == vaccinated : out[id] = coor
    return out
def get_all_unjabbed_pairs(population, radius):
    out = [] ; data = get_coordinates(population, False)
    data = sorted(data.items(),key= lambda x:x[0])
    for i in range(len(data)):
        for k in range(i+1,len(data)):
            coor1 = data[i][1]
            coor2 = data[k][1]
            if ((coor1[0]-coor2[0])**2+(coor1[1]-coor2[1])**2)**(1/2) <= radius:
                out += [(data[i][0],data[k][0])]
    return out
def first_hop(population, id, radius):
    out = [] ; data = get_all_unjabbed_pairs(population, radius) 
    for i in data:
        if id in i : out += i
    while True :
        if id not in out : break
        else : out.remove(id)
    return sorted(out)
def get_adjacency_set(pairs):
    out = {}
    for i in pairs:
        if i[0] in out :
            item = set(out[i[0]])
            item.add(i[1])
            out.update({i[0]:item})
        else : out[i[0]] = {i[1]}
        if i[1] in out:
            item = set(out[i[1]])
            item.add(i[0])
            out.update({i[1]: item})
        else: out[i[1]] = {i[0]}
    return out
def get_infectable_ids(pairs,seed):
    out = set() ; f = [seed] ; data = get_adjacency_set(pairs)
    while len(f) != 0 :
        p = f.pop(0)
        out.add(p)
        for i in data[p]:
            if i not in out : f += [i]
    return out
def get_all_clusters(pairs):
    data_agency = get_adjacency_set(pairs) ; out = []
    for i in data_agency:
        data = get_infectable_ids(pairs,i)
        if data not in out : out += [data]
    return out
# 6530069021 (point = 100.0%) sim = 86%
def get_coordinates(population, vaccinated):
    ans = {}
    for i in population :
        if i['vaccinated'] == vaccinated:
            ans[i['id']] = i['coordinate']
    return ans 
def get_all_unjabbed_pairs(population, radius):
    ans = []
    data = get_coordinates(population, False)
    data = sorted(data.items(), key=lambda x: x[0])
    for i in range(len(data)):
        for k in range (i+1,len(data)):
            coor1 = data[i][1]
            coor2 = data[k][1]
            if ((coor1[0]-coor2[0])**2 + (coor1[1]-coor2[1])**2)**0.5 <= radius:
                ans.append((data[i][0],data[k][0]))
    return ans
def first_hop(population, id, radius): 
    ans = []
    a = set()
    b = set()
    data = get_all_unjabbed_pairs(population, radius)
    for e in data:
        if id in e:
            a.add(e)
    for i in a:
        for e in i:
            b.add(e)
    for i in b:
        ans.append(i)
    ans.remove(id)
    return sorted(ans)
def get_adjacency_set(pairs):
    ans = {}
    for i in pairs:
        if i[0] in ans :
            item = set(ans[i[0]])
            item.add(i[1])
            ans.update({i[0]:item})
        else:
            ans[i[0]] = {i[1]}
        if i[1] in ans :
            item = set(ans[i[1]])
            item.add(i[0])
            ans.update({i[1]:item})
        else:
            ans[i[1]] = {i[0]}
    return(ans) 
def get_infectable_ids(pairs,seed):
    ans = set()
    f = [seed]
    data = get_adjacency_set(pairs)
    while len(f) != 0:
        p = f.pop(0)
        ans.add(p)
        for i in data[p]:
            if i not in ans:
                f += [i]
    return(ans)
def get_all_clusters(pairs):
    ans = []
    data1 = get_adjacency_set(pairs)
    for e in data1:
        data2 = get_infectable_ids(pairs,e)
        if data2 not in ans:
            ans.append(data2)
    return(ans)

>> cluster #5(2)
# 6431418421 (point = 100.0%) sim = 86%
def get_coordinates(population, vaccinated):
    ans={}
    for i in population:
        if i['vaccinated'] == vaccinated:
            ans[i['id']] = i['coordinate']
    return ans
def get_all_unjabbed_pairs(population, radius):
    small = get_coordinates(population, False)
    small2= get_coordinates(population, False)
    small=dict(sorted(small.items()))
    small2=dict(sorted(small2.items()))
    ans=[]
    for x in small:
        small2.pop(x)
        for y in small2:
            dis = ((small[x][0]-small2[y][0])**2+(small[x][1]-small2[y][1])**2)**0.5
            if dis <= radius:
                ans.append((x,y))
    return ans  
def first_hop(population, id, radius):
    x=get_all_unjabbed_pairs(population, radius)
    ans=[]
    for i in x:
        if i[0] == id:
            ans.append(i[1])
        if i[1] == id:
            ans.append(i[0])
    ans.sort()
    return ans
def get_adjacency_set(pairs):
    want={}
    for i in pairs:
        if i[0] not in want:
            ans=[]
            for ii in pairs:
                if ii[0] == i[0]:
                    ans.append(ii[1])
                if ii[1] == i[0]:
                    ans.append(ii[0])
            ans.sort()
            want[i[0]]=set(ans)
        if i[1] not in want:
            ans=[]
            for ii in pairs:
                if ii[0] == i[1]:
                    ans.append(ii[1])
                if ii[1] == i[1]:
                    ans.append(ii[0])
            ans.sort()
            want[i[1]]=set(ans)
    return want 
def get_infectable_ids(pairs,seed):        
    x = get_adjacency_set(pairs)
    f=[seed]
    output=set()
    while True:
        if len(f) == 0:
            break
        p=f.pop(0)
        output.add(p)
        for i in x[p]:
            if i not in output:
                f.append(i)
    return output
def get_all_clusters(pairs):
    a=[]
    for i in pairs:
        a.append(i[0])
        a.append(i[1])
    a=list(set(a))
    a.sort()
    ans=[]
    for i in a:
        c = get_infectable_ids(pairs,i)
        if c not in ans:
            ans.append(c)
    return ans
# 6431416121 (point = 48.86%) sim = 86%
def get_coordinates(population, vaccinated):
    s = {}
    for i in range(len(population)) :
        if  population[i]['vaccinated'] == False :
            s[population[i]['id']] = population[i]['coordinate']
    return s
def get_all_unjabbed_pairs(population, radius):
    s = get_coordinates(population, False)
    k = get_coordinates(population, False)
    s = dict(sorted(s.items()))
    k = dict(sorted(k.items()))
    p = []
    for key in s :
        k.pop(key)
        for u in k :
            rem = (((s[key])[0]-k[u][0])**2+((s[key])[1]-k[u][1])**2)**0.5
            if rem <= int(radius) :
                p.append((key,u))
    return p
def first_hop(population, id, radius): 
  c = []
  x = get_all_unjabbed_pairs(population, 10)
  for i in x :
    if id == i[0] :
      c.append(i[1])
    if id == i[1] :
      c.append(i[0])
  c.sort()
  return c
def get_adjacency_set(pairs):
    a = {}
    for i in pairs :
        if i[0] not in a :
            k = []
            for u in pairs :
                if u[0] == i[0] :
                    k.append(u[1])
                if u[1] == i[0] :
                    k.append(u[0])
            k.sort()
            a[i[0]] = set(k)
        if i[1] not in a :
            k = []
            for u in pairs :
                if u[0] == i[0] :
                    k.append(u[1])
                if u[1] == i[0] :
                    k.append(u[0])
            k.sort()
            a[i[1]] = set(k)
    return a
def get_infectable_ids(pairs,seed):
    u = get_adjacency_set(pairs)
    y = [seed]
    o = set()
    while True :
        if len(y) == 0 :
            break
        p = y.pop(0)
        o.add(p)
        for i in u[p] :
            if i not in o :
                y.append(i)
    return o
def get_all_clusters(pairs):
  alls=[]
  for i in pairs:
    z1 = get_infectable_ids(pairs,i[0])
    if z1 not in alls:
      alls.append(z1)
    z2 = get_infectable_ids(pairs,i[1])
    if z2 not in alls:
      alls.append(z2)
  return alls

>> cluster #6(2)
# 6531028421 (point = 100.0%) sim = 84%
def get_coordinates(population, vaccinated):
  cord = {}
  for i in range(len(population)):
    if population[i]['vaccinated'] == vaccinated:
      cord[population[i]['id']] = population[i]['coordinate']
  return  cord
def get_all_unjabbed_pairs(population, radius):
    unjabbed = []
    for i in population: 
        if i['vaccinated'] == False :
            unjabbed.append(i)
    unj_rad = []
    for p1 in unjabbed :
        for p2 in unjabbed:
            if p1 != p2 and p1['id'] < p2['id'] and dis(p1['coordinate'], p2['coordinate']) <= radius :
                unj_rad.append((p1['id'], p2['id']))
    unj_rad = sorted(unj_rad)
    return unj_rad
def dis(z1, z2) :
    x1, y1 = z1
    x2, y2 = z2
    return ((x1-x2)**2 + (y1 - y2)**2)**0.5
def first_hop(population, id, radius):
    idcord = (0,0)
    for i in population :
        if id == i['id'] :
            idcord = i['coordinate']
            break
    nearly = []
    for i in population :
        if i['id'] != id :
            if i['vaccinated'] == False :
                if dis(i['coordinate'], idcord) <= radius:
                    nearly.append(i['id'])
    nearly = sorted(nearly)
    return nearly
def get_adjacency_set(pairs):
    adj = {}
    for i,j in pairs :
        if j not in adj :
            adj[j] = set()
        if i not in adj :
            adj[i] = set()
        adj[i].add(j)
        adj[j].add(i)
    return adj
def get_infectable_ids(pairs,seed):
    adj = get_adjacency_set(pairs)
    risk = set()
    f = [seed]
    while len(f) > 0 :
        p = f.pop(0)
        risk.add(p)
        for i in adj[p] :
            if i not in risk :
                f.append(i)
    return risk
def get_all_clusters(pairs):
    p = set()
    for i,j in pairs :
        p.add(i)
        p.add(j)
    clusters = []
    risk = set()
    t = set()
    for i in p :
        if i not in risk :
            t = get_infectable_ids(pairs, i)
            clusters.append(t)
            for o in t :
                risk.add(o)
    return clusters
# 6531017521 (point = 100.0%) sim = 84%
def get_coordinates(population, vaccinated):
  population_with_vaccinated = {}
  for person in population :
    if person['vaccinated'] == vaccinated :
      population_with_vaccinated[person['id']] = person['coordinate']
  return population_with_vaccinated
def get_all_unjabbed_pairs(population, radius):
  not_vaccinated = []
  for person in population :
    if person['vaccinated'] == False :
      not_vaccinated.append(person)
  unjabbed = []
  for person1 in not_vaccinated :
    for person2 in not_vaccinated :
      if person1 != person2 and person1['id'] < person2['id'] and           distance(person1['coordinate'], person2['coordinate']) <= radius :
        unjabbed.append((person1['id'], person2['id']))
  unjabbed.sort()
  return unjabbed
def distance(p1, p2) :
  x1, y1 = p1
  x2, y2 = p2
  return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
def first_hop(population, id, radius): 
  id_coordinate = (0.0, 0.0)
  for person in population :
    if person['id'] == id :
      id_coordinate = person['coordinate']
      break
  first_hop = []
  for person in population :
    if person['id'] != id and person['vaccinated'] == False and distance(person['coordinate'], id_coordinate) <= radius :
      first_hop.append(person['id'])
  first_hop.sort()
  return first_hop
def get_adjacency_set(pairs):
  adjacency_set = {}
  for id1, id2 in pairs :
    if id1 not in adjacency_set :
      adjacency_set[id1] = set()
    if id2 not in adjacency_set :
      adjacency_set[id2] = set()
    adjacency_set[id1].add(id2)
    adjacency_set[id2].add(id1)
  return adjacency_set
def get_infectable_ids(pairs,seed):
  adjacency_pair = get_adjacency_set(pairs)
  infectable = set()
  f = [seed]
  while len(f) > 0 :
    u = f.pop(0)
    infectable.add(u)
    for v in adjacency_pair[u] :
      if v not in infectable :
        f.append(v)
  return infectable
def get_all_clusters(pairs):
  clusters = []
  people = set()
  for p1, p2 in pairs :
    people.add(p1)
    people.add(p2)
  visited = set()
  for person in people :
    if person not in visited :
      cluster = get_infectable_ids(pairs, person)
      clusters.append(cluster)
      for p in cluster :
        visited.add(p)
  return clusters

>> cluster #7(2)
# 6530185021 (point = 100.0%) sim = 83%
def get_coordinates(population, vaccinated):
    dic = {}
    for e in population:
        if e['vaccinated'] == vaccinated:
            dic[e['id']] = e['coordinate']
    return dic
def get_all_unjabbed_pairs(population, radius):
    ans = []
    id_tuple = ()
    for e in population:
        for f in population:
            if e != f:
                if not e['vaccinated'] and not f['vaccinated'] :
                    xe = e['coordinate'][0]
                    ye = e['coordinate'][1]
                    xf = f['coordinate'][0]
                    yf = f['coordinate'][1]
                    distance = (((xe-xf)**2)+((ye-yf)**2))**(1/2)
                    if distance <= radius:
                        id_list = [e['id'],f['id']]
                        id_list.sort()
                        for g in id_list:
                            id_tuple += (g,)
                        if id_tuple not in ans:
                            ans.append(id_tuple)
                        id_tuple = ()
    ans.sort()
    return ans
def first_hop(population, id, radius):
    id_list = []
    i_d = get_coordinates(population, False)
    x0,y0 = i_d[id][0],i_d[id][1]
    for e in i_d:
        if e != id:
            x1,y1 = i_d[e][0],i_d[e][1]
            distance = (((x1-x0)**2)+((y1-y0)**2))**(1/2)
            if distance <= radius:
                id_list.append(e)
    id_list.sort()
    return id_list
def get_adjacency_set(pairs):
    dic = {}
    for e in pairs:
        if e[0] not in dic:
            dic[e[0]] = {e[1]}
        else:
            dic[e[0]].add(e[1])
        if e[1] not in dic:
            dic[e[1]] = {e[0]}
        else:
            dic[e[1]].add(e[0])
    return dic
def get_infectable_ids(pairs,seed):
    pairs = get_adjacency_set(pairs)
    output = set()
    f = [seed]
    while f != []:
        p = f.pop(0)
        output.add(p)
        for e in pairs[p]:
            if e not in output:
                f.append(e)
    return output
def get_all_clusters(pairs):
    clusters = []
    for seed in get_adjacency_set(pairs):
        if get_infectable_ids(pairs,seed) not in clusters:
            clusters.append(get_infectable_ids(pairs,seed))
    return clusters
# 6530174121 (point = 100.0%) sim = 83%
def get_coordinates(population, vaccinated):
    ans = {}
    for e in population:
        if e["vaccinated"] == vaccinated:
            ans[e["id"]] = e['coordinate']
    return  ans
def get_all_unjabbed_pairs(population, radius):
    ans = []
    id_tuple = ()
    for i in range(len(population)):
        for j in range(len(population)):
            if j != i:
                if population[i]['vaccinated'] == False and population[j]['vaccinated'] == False:
                    x1 = population[i]['coordinate'][0]
                    y1 = population[i]['coordinate'][1]
                    x2 = population[j]['coordinate'][0]
                    y2 = population[j]['coordinate'][1]
                    distance = (((x1-x2)**2)+((y1-y2)**2))**(0.5)
                    if distance <= radius:
                        id_list = [population[i]['id'],population[j]['id']]
                        id_list.sort()
                        for e in id_list:
                            id_tuple = id_tuple + (e,)
                        if id_tuple not in ans:
                            ans.append(id_tuple)
                        id_tuple = ()
    ans.sort()
    return ans
def first_hop(population, id, radius): 
    ans = []
    pop = get_coordinates(population, False)
    xcenter = pop[id][0]
    ycenter = pop[id][1]
    for e in pop:
        if e != id:
            x = pop[e][0]
            y = pop[e][1]
            distance = (((xcenter-x)**2)+((ycenter-y)**2))**(0.5)
            if distance <= radius:
                    ans.append(e)
    ans.sort()
    return ans
def get_adjacency_set(pairs):
    ans = {}
    for e in pairs:
        if e[0] not in ans:
            ans[e[0]] = {e[1]}
        else:
            ans[e[0]].add(e[1])
        if e[1] not in ans:
            ans[e[1]] = {e[0]}
        else:
            ans[e[1]].add(e[0])
    return  ans
def get_infectable_ids(pairs,seed):
    pairs = get_adjacency_set(pairs)
    output = set()
    f = [seed]
    while f != []:
        p = f.pop(0)
        output.add(p)
        for e in pairs[p]:
            if e not in output:
                f.append(e)
    return  output
def get_all_clusters(pairs):
    ans = []
    for pair in pairs:
        for seed in pair:
            output = get_infectable_ids(pairs,seed)
            if output not in ans:
                ans.append(output)
    return ans

>> cluster #8(2)
# 6530142021 (point = 100.0%) sim = 82%
def get_coordinates(population, vaccinated):
    idc = {}
    for d in population:
        if d['vaccinated'] == vaccinated:
            idc[d['id']] = d['coordinate']
    return idc
def get_all_unjabbed_pairs(population, radius):
    out = []
    d = get_coordinates(population, False)
    ids = []
    for k in d:
        ids.append(k)
    for i in range(len(d)):
        for j in range(i+1,len(d)):
            aid = ids[i]
            bid = ids[j]
            xa,ya = d[aid]
            xb,yb = d[bid]
            r = ((xa-xb)**2 + (ya-yb)**2)**0.5
            if r <= radius:
                if aid < bid:
                    out.append((aid,bid))
                else:
                    out.append((bid,aid))        
    out.sort()
    return out
def first_hop(population, id, radius): 
    pairs = get_all_unjabbed_pairs(population,radius)
    out = []
    for id1,id2 in pairs:
        if id1 == id:
            out.append(id2)
        elif id2 == id:
            out.append(id1)
    out.sort()
    return out
def get_adjacency_set(pairs):
    d = {}
    for aid,bid in pairs:
        if aid not in d:
            d[aid] = {bid}
        else:
            d[aid].add(bid)
        if bid not in d:
            d[bid] ={aid}
        else:
            d[bid].add(aid)
    return d
def get_infectable_ids(pairs,seed):
    d_adjs = get_adjacency_set(pairs)
    output = set()
    f = [seed]
    while len(f) != 0:
        p = f.pop(0)
        output.add(p)
        adjs = d_adjs[p]
        for adj in adjs:
            if adj not in output:
                f.append(adj)
    return output
def get_all_clusters(pairs):
    out = []
    ids = set()
    for id1,id2 in pairs:
        ids.add(id1)
        ids.add(id2)
    for seed in ids:
        c = get_infectable_ids(pairs,seed)
        if c not in out:
            out.append(c)
    return out
# 6430206521 (point = 100.0%) sim = 82%
def get_coordinates(population, vaccinated):
  d={}
  for e in population:
      if e['vaccinated'] == vaccinated:
          d[e['id']] = e['coordinate']
  return d
def get_all_unjabbed_pairs(population, radius):
  d= get_coordinates(population,False)
  ids = list(d.keys())
  l=[]
  for i in range(len(d)-1):
      for j in range(i+1,len(d)):
        id_a = ids[i]
        id_b = ids[j]
        co_a = d[id_a]
        co_b = d[id_b]
        r = ((co_a[0]-co_b[0])**2 + (co_a[1]-co_b[1])**2)**0.5
        if r <= radius:
            if id_a < id_b:
                l.append((id_a,id_b))
            else:
                l.append((id_b,id_a))
  l.sort()
  return l 
def first_hop(population, id, radius): 
  l = get_all_unjabbed_pairs(population,radius)
  ans = []
  for id_a,id_b in l:
    if id_a == id:
      ans.append(id_b)
    elif id_b == id:
      ans.append(id_a)
  ans.sort()
  return ans 
def get_adjacency_set(pairs):
  d={}
  for id_a,id_b in pairs:
    if id_a in d:
      d[id_a].add(id_b)
    else:
      d[id_a] = {id_b}
    if id_b in d:
      d[id_b].add(id_a)
    else:
      d[id_b] = {id_a}
  return d
def get_infectable_ids(pairs,seed):
  output = set()
  f = [seed]
  while len(f) != 0:
    p = f.pop(0)
    output.add(p)
    for id_a,id_b in pairs:
      if id_a == p:
        if id_b not in output:
          f.append(id_b)
      elif id_b == p:
        if id_a not in output:
          f.append(id_a)
  return output
def get_all_clusters(pairs):
  ids = set()
  out = []
  for id_a , id_b in pairs:
    ids.add(id_a)
    ids.add(id_b)
  for id in ids:
    cluster = get_infectable_ids(pairs,id)
    if cluster not in out:
      out.append(cluster)
  return out