[geómetracat]

Hola a todos,

Los enunciados de hoy (Beacon Exclusion Zone) sol los siguientes.
Parte 1:

Spoiler

You feel the ground rumble again as the distress signal leads you to a large network of subterranean tunnels. You don't have time to search them all, but you don't need to: your pack contains a set of deployable sensors that you imagine were originally built to locate lost Elves.

The sensors aren't very powerful, but that's okay; your handheld device indicates that you're close enough to the source of the distress signal to use them. You pull the emergency sensor system out of your pack, hit the big button on top, and the sensors zoom off down the tunnels.

Once a sensor finds a spot it thinks will give it a good reading, it attaches itself to a hard surface and begins monitoring for the nearest signal source beacon. Sensors and beacons always exist at integer coordinates. Each sensor knows its own position and can determine the position of a beacon precisely; however, sensors can only lock on to the one beacon closest to the sensor as measured by the Manhattan distance. (There is never a tie where two beacons are the same distance to a sensor.)

It doesn't take long for the sensors to report back their positions and closest beacons (your puzzle input). For example:

Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3

So, consider the sensor at 2,18; the closest beacon to it is at -2,15. For the sensor at 9,16, the closest beacon to it is at 10,16.

Drawing sensors as S and beacons as B, the above arrangement of sensors and beacons looks like this:

               1    1    2    2
     0    5    0    5    0    5
 0 ....S.......................
 1 ......................S.....
 2 ...............S............
 3 ................SB..........
 4 ............................
 5 ............................
 6 ............................
 7 ..........S.......S.........
 8 ............................
 9 ............................
10 ....B.......................
11 ..S.........................
12 ............................
13 ............................
14 ..............S.......S.....
15 B...........................
16 ...........SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....

This isn't necessarily a comprehensive map of all beacons in the area, though. Because each sensor only identifies its closest beacon, if a sensor detects a beacon, you know there are no other beacons that close or closer to that sensor. There could still be beacons that just happen to not be the closest beacon to any sensor. Consider the sensor at 8,7:

               1    1    2    2
     0    5    0    5    0    5
-2 ..........#.................
-1 .........###................
 0 ....S...#####...............
 1 .......#######........S.....
 2 ......#########S............
 3 .....###########SB..........
 4 ....#############...........
 5 ...###############..........
 6 ..#################.........
 7 .#########S#######S#........
 8 ..#################.........
 9 ...###############..........
10 ....B############...........
11 ..S..###########............
12 ......#########.............
13 .......#######..............
14 ........#####.S.......S.....
15 B........###................
16 ..........#SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....

This sensor's closest beacon is at 2,10, and so you know there are no beacons that close or closer (in any positions marked #).

None of the detected beacons seem to be producing the distress signal, so you'll need to work out where the distress beacon is by working out where it isn't. For now, keep things simple by counting the positions where a beacon cannot possibly be along just a single row.

So, suppose you have an arrangement of beacons and sensors like in the example above and, just in the row where y=10, you'd like to count the number of positions a beacon cannot possibly exist. The coverage from all sensors near that row looks like this:

                 1    1    2    2
       0    5    0    5    0    5
 9 ...#########################...
10 ..####B######################..
11 .###S#############.###########.

In this example, in the row where y=10, there are 26 positions where a beacon cannot be present.

Consult the report from the sensors you just deployed. In the row where y=2000000, how many positions cannot contain a beacon?

[cerrar]

Parte 2:

Spoiler

Your handheld device indicates that the distress signal is coming from a beacon nearby. The distress beacon is not detected by any sensor, but the distress beacon must have x and y coordinates each no lower than 0 and no larger than 4000000.

To isolate the distress beacon's signal, you need to determine its tuning frequency, which can be found by multiplying its x coordinate by 4000000 and then adding its y coordinate.

In the example above, the search space is smaller: instead, the x and y coordinates can each be at most 20. With this reduced search area, there is only a single position that could have a beacon: x=14, y=11. The tuning frequency for this distress beacon is 56000011.

Find the only possible position for the distress beacon. What is its tuning frequency?

[cerrar]

Mi solución en Python:

Código: [Seleccionar]

import re

with open("input15.txt") as f:
    inp = f.read().splitlines()
   
def manhattan(x,y):
    return abs(x[0]-y[0]) + abs(x[1]-y[1])
   
positions = [[(int(x), int(y)) for (x,y) in re.findall("x=(-*\d+), y=(-*\d+)", inp[i])] for i in range(len(inp))]
sensors = [x for [x,y] in positions]
beacons = [y for [x,y] in positions]
distances = [manhattan(positions[i][0], positions[i][1]) for i in range(len(positions))]

# Part 1
def update(lst, m, M):
    posm = len([x for x in [x[0] for x in lst] if x<m])
    if posm > 0 and m <= lst[posm-1][1] + 1:
        m = lst[posm-1][0]
        posm -= 1
    posM = len([x for x in [x[1] for x in lst] if x<M])
    if posM < len(lst) and M >= lst[posM][0] - 1:
        M = lst[posM][1]
        posM += 1
    del lst[posm:posM]
    lst.append([m,M])
    return sorted(lst, key = lambda x: x[0])

def compute_range(line, sensor, distance):
    width = distance - abs(sensor[1] - line)
    if width < 0:
        return []
    else:
        return [sensor[0]-width, sensor[0]+width]

def compute_covered(line, sensors, distances, limits = None):
    total = []
    for i in range(len(sensors)):
        srange = compute_range(line, sensors[i], distances[i])
        if srange:
            if limits:
                srange[0] = max(srange[0], limits[0])
                srange[1] = min(srange[1], limits[1])
            total = update(total, srange[0], srange[1])
    return total

def compute_length(total_range):
    total = 0
    for [x,y] in total_range:
        total += y-x
    return total
   
total_range = compute_covered(2000000, sensors, distances)
print(compute_length(total_range))

# Part 2
max_coord = 4000000

def find_beacon(sensors, distances, limits = [0, max_coord]):
    for line in range(max_coord+1):
        rng = compute_covered(line, sensors, distances, limits = [0, max_coord])
        if rng != [[0, max_coord]]:
            return line, rng[0][1]+1

res = find_beacon(sensors, distances, limits = [0, max_coord])
print(res[1]*4000000+res[0])
Bueno, pues después del fiasco de ayer hoy me ha salido en un pispás. Curiosamente he podido aprovechar parte del código y el enfoque de ayer, que era mucho más complicado de la cuenta, para este problema. Eso sí, debe haber maneras mucho mejores de hacer esto, porque me tarda alrededor de 80s la segunda parte.

De todas maneras no me desdigo de lo de ayer: en cuanto me cueste más de la cuenta el problema (como ayer) lo dejaré estar.

[Eparoh]

Hola.

Mi código en Maple:

Código: [Seleccionar]

Datos:= proc(File)
   local s, l, s_aux, x, S, L, i;
      s:=FileTools[Text][ReadLine](File);
      s_aux:="";
      S:=[];
      L:=[];
      while s<>NULL do
         l:=length(s);
         i:=1;
         while i <= l do
            if s[i] = "=" then
               i:=i+1;
               while s[i] <> "," and s[i] <> ":" and i <= l  do
                  s_aux:=cat(s_aux,s[i]);
                  i:=i+1
               od;
               L:=[op(L),parse(s_aux)];
               s_aux:="";
            else
               i:=i+1
            fi;
         od;
         S:=[op(S),L];
         L:=[];
         s_aux:="";
         s:=FileTools[Text][ReadLine](File);
      od;
      FileTools[Text][Close](File);
   RETURN([seq([[S[i][1],S[i][2]],[S[i][3],S[i][4]]],i=1..nops(S))]);
end:

F:=Datos(cat(currentdir(),"\\Template 15.txt")):

Taxicab_dist:=proc(p,q)
   RETURN(abs(p[1]-q[1])+abs(p[2]-q[2]));
end:
Radios:=proc(F)
   RETURN([seq(Taxicab_dist(F[i][1],F[i][2]),i=1..nops(F))]);
end:
No_beacon:=proc(F,R,y,cota:=[-infinity,infinity],ignora:=1)
   local L, i, h, L1, L2;
      L:=[];
      for i from 1 to nops(F) do
         h:=R[i]-Taxicab_dist(F[i][1],[F[i][1][1],y]);
         if h>=0 then
            L1:=max(F[i][1][1]-h,cota[1]);
            L2:=min(F[i][1][1]+h,cota[2]);
            if F[i][2][2]=y and ignora = 1 then
               if L1<=F[i][2][1]-1 and F[i][2][1]+1<=L2 then
                  L:=[op(L),[L1,F[i][2][1]-1],[F[i][2][1]+1,L2]];
               elif L1>F[i][2][1]-1 and F[i][2][1]+1<=L2 then
                  L:=[op(L),[F[i][2][1]+1,L2]];
               elif L1<=F[i][2][1]-1 and F[i][2][1]+1>L2 then
                  L:=[op(L),[L1,F[i][2][1]-1]];
               fi;
            else
               L:=[op(L),[L1,L2]];
            fi;
         fi;
      od;
   RETURN(L);
end:
Union_intervalos:=proc(U)
   local L, L_aux, R, i;
      L:=sort(U);
      L_aux:=L[1];
      R:=[];
      for i from 1 to nops(U)-1 do
         if L_aux[2]>=L[i+1][1] then
            L_aux:=[L_aux[1],max(L_aux[2],L[i+1][2])];
         else
            R:=[op(R),L_aux];
            L_aux:=L[i+1];
         fi;
      od;
   RETURN([op(R),L_aux]);
end:
Long_intervalos:=proc(U)
   RETURN(add(x, x in seq(U[i][2]-U[i][1]+1,i=1..nops(U))));
end:
NO_Beacon:=proc(F,m,M)
   local i, L, R;
   R:=Radios(F);
      for i from m to M do
         L:=Union_intervalos(No_beacon(F,R,i,[m,M],0));
         if Long_intervalos(L)<M-m+1 then
             RETURN([L[1][2]+1,i]);
         fi;
      od;
end:

rad:=Radios(F):
NoB:=No_beacon(F,rad,2000000):
Long_intervalos(Union_intervalos(NoB));
NoB1:=NO_Beacon(F,0,4000000):
4000000*NoB1[1]+NoB1[2];


Bueno, pues después del fiasco de ayer hoy me ha salido en un pispás. Curiosamente he podido aprovechar parte del código y el enfoque de ayer, que era mucho más complicado de la cuenta, para este problema. Eso sí, debe haber maneras mucho mejores de hacer esto, porque me tarda alrededor de 80s la segunda parte.

De todas maneras no me desdigo de lo de ayer: en cuanto me cueste más de la cuenta el problema (como ayer) lo dejaré estar.

A mi también me salió hoy muy rápido, pero tal como dices que habrán formas mucho más eficientes de hacerlo, también te digo que las hay mucho menos eficientes porque el mío tarda cerca de 8 minutos para la segunda parte
Pero, después del tiempo que tarde ayer en hacer el otro no he tenido tampoco ganas de pensarlo mucho más y, con lo poco que he pensado, tampoco se me ha ocurrido una mejor manera de hacerlo.

EDITO: Creo que se me ha ocurrido una forma de hacerlo mucho más rápido. A ver si sale y lo subo.

Un saludo y espero que la cosa siga adelante.

[Eparoh]

Bueno, pues como puse en el post anterior, he tenido una idea mejor y he conseguido pasar de ejecutarse en 8 minutos a hacerlo de forma instantánea 
La idea ha sido rotar 45º las bolas que te da la métrica de Manhattan para poder trabajar con rectángulos paralelos a los ejes, encontrar el punto buscado en esta rotación (donde ahora unir rectángulos de esta forma es mucho más fácil), y luego volver a rotar en sentido contrario para obtener el punto finalmente.

Dejo aquí el código de Maple:

Código: [Seleccionar]

Datos:= proc(File)
   local s, l, s_aux, x, S, L, i;
      s:=FileTools[Text][ReadLine](File);
      s_aux:="";
      S:=[];
      L:=[];
      while s<>NULL do
         l:=length(s);
         i:=1;
         while i <= l do
            if s[i] = "=" then
               i:=i+1;
               while s[i] <> "," and s[i] <> ":" and i <= l  do
                  s_aux:=cat(s_aux,s[i]);
                  i:=i+1
               od;
               L:=[op(L),parse(s_aux)];
               s_aux:="";
            else
               i:=i+1
            fi;
         od;
         S:=[op(S),L];
         L:=[];
         s_aux:="";
         s:=FileTools[Text][ReadLine](File);
      od;
      FileTools[Text][Close](File);
   RETURN([seq([[S[i][1],S[i][2]],[S[i][3],S[i][4]]],i=1..nops(S))]);
end:

F:=Datos(cat(currentdir(),"\\Template 15.txt")):

Taxicab_dist:=proc(p,q)
   RETURN(abs(p[1]-q[1])+abs(p[2]-q[2]));
end:
Radios:=proc(F)
   RETURN([seq(Taxicab_dist(F[i][1],F[i][2]),i=1..nops(F))]);
end:
No_beacon:=proc(F,y)
   local L, i, h, L1, L2, R;
      L:=[];
      R:=Radios(F);
      for i from 1 to nops(F) do
         h:=R[i]-Taxicab_dist(F[i][1],[F[i][1][1],y]);
         if h>=0 then
            L1:=F[i][1][1]-h;
            L2:=F[i][1][1]+h;
            if F[i][2][2]=y then
               if L1<=F[i][2][1]-1 and F[i][2][1]+1<=L2 then
                  L:=[op(L),[L1,F[i][2][1]-1],[F[i][2][1]+1,L2]];
               elif L1>F[i][2][1]-1 and F[i][2][1]+1<=L2 then
                  L:=[op(L),[F[i][2][1]+1,L2]];
               elif L1<=F[i][2][1]-1 and F[i][2][1]+1>L2 then
                  L:=[op(L),[L1,F[i][2][1]-1]];
               fi;
            else
               L:=[op(L),[L1,L2]];
            fi;
         fi;
      od;
   RETURN(L);
end:
Union_intervalos:=proc(U)
   local L, L_aux, R, i;
      L:=sort(U);
      L_aux:=L[1];
      R:=[];
      for i from 1 to nops(U)-1 do
         if L_aux[2]>=L[i+1][1] or L[i+1][1]-L_aux[2]=1 then
            L_aux:=[L_aux[1],max(L_aux[2],L[i+1][2])];
         else
            R:=[op(R),L_aux];
            L_aux:=L[i+1];
         fi;
      od;
   RETURN([op(R),L_aux]);
end:
Long_intervalos:=proc(U)
   RETURN(add(x, x in seq(U[i][2]-U[i][1]+1,i=1..nops(U))));
end:
Union_rect:=proc(U,inicio,med,final)
   local EjeX, C, U_aux, i, j;
      EjeX:={seq(U[i][1][1],i=1..nops(U))} union {seq(U[i][1][2],i=1..nops(U))} union {inicio,med,final};
      C:=[];
      for i from 1 to nops(EjeX)-1 do
         U_aux:=[];
         for j from 1 to nops(U) do
            if U[j][1][1]<=EjeX[i] and EjeX[i+1]<=U[j][1][2] then
               U_aux:=[op(U_aux),U[j][2]];
            fi;
         od;
         U_aux:=Union_intervalos(U_aux);
         C:=[op(C),seq([[EjeX[i],EjeX[i+1]],U_aux[k]],k=1..nops(U_aux))];
      od;
   RETURN(C);
end:
Localizacion_beacon:=proc(F,M)
   local G, R, Rota_diamantes, H, L, i, P_buscado_rotado, P_buscado;
      G:=[seq(F[i][1],i=1..nops(F))];
      R:=Radios(F);
      Rota_diamantes:=[seq([[G[i][1]+G[i][2]-R[i],G[i][1]+G[i][2]+R[i]],[G[i][2]-R[i]-G[i][1],G[i][2]-G[i][1]+R[i]]],i=1..nops(G))];
      H:=Union_rect(Rota_diamantes,0,M,2*M);
      L:=[];
      for i from 1 to nops(H) do
         if H[i][1][1]>=0 and H[i][1][2]<=M and (H[i][2][1]>-H[i][1][1] or H[i][2][2]<H[i][1][1] or H[i][2][1]>-H[i][1][2] or H[i][2][2]<H[i][1][2]) then
            L:=[op(L),H[i]];
         elif H[i][1][1]>=M and H[i][1][2]<=2*M and (H[i][2][1]>H[i][1][1]-2*M or H[i][2][2]<-H[i][1][1]+2*M or H[i][2][1]>H[i][1][2]-2*M or H[i][2][2]<-H[i][1][2]+2*M) then
            L:=[op(L),H[i]];
         fi;
      od;
      P_buscado_rotado:=[L[1][1][1]+L[1][1][2],L[1][2][2]+L[2][2][1]]/2;
      P_buscado:=[P_buscado_rotado[1]-P_buscado_rotado[2],P_buscado_rotado[1]+P_buscado_rotado[2]]/2;
   RETURN(P_buscado);
end:

NoB:=No_beacon(F,2000000):
Long_intervalos(Union_intervalos(NoB));
Loc:=Localizacion_beacon(F,4000000):
4000000*Loc[1]+Loc[2];

Un saludo.

[geómetracat]

 
Muy buena idea.

Yo acabo de leer el enunciado de hoy y, visto el enunciado y vistos los tiempos de los 100 primeros, este año lo dejo aquí. Pero seguiré con interés tus progresos, ¡espero que lo acabes!

[Eparoh]

He sido derrotado  :'(

Llevo desde las 8 de la mañana con el de hoy y ni siquiera he conseguido resolver de forma satisfactoria el ejemplo de juguete.

Como ya comenté hace un par de días de grafos se muy poco y realmente de programación también se bien poco (programo un poco por "intuición", nunca he estudiado programación más allá de los más básico que vi hace años en primero del grado de matemáticas). Así que, si en algún momento te animas a resolver el de hoy y explicar un poco las ideas sobre como se puede resolver, estaría muy feliz de leerlo   

Aún así, seguiré intentando los que quedan y a ver si esta es la única mancha en el historial 

Un saludo