15 R

# for regular expressions
library(stringr)
# for intervals
library(sets)

# manhattan distance between two points
distance = function(v1, v2) {
    return (abs(v1$x - v2$x) + abs(v1$y - v2$y))
}

# parse line into beacon and sensor coordinates
parseLine = function(line, reg) {
    tokens = str_match(line, reg)
    return (list(
        # convert to integer
        sx=strtoi(tokens[2][1]),
        sy=strtoi(tokens[3][1]),
        bx=strtoi(tokens[4][1]),
        by=strtoi(tokens[5][1])
    ))
}

fn = "15.input"
# open file
con = file(fn, open="r")
# regular expression matching the input file structure
reg = ".*x=(?<sx>[-0-9]+), y=(?<sy>[-0-9]+): .* x=(?<bx>[-0-9]+), y=(?<by>[-0-9]+)"
# we are interested in this line
Y = 2000000
# set of disjunct intervals
coverage = interval()
# list of beacons on the Y line
beacons = list()

while (TRUE) {
    # read one line
    line = readLines(con, n=1)
    # if empty, we are at the end of file
    if (length(line) == 0) {
        break
    }
    # get coordinates
    coords = parseLine(line, reg)
    # use associative arrays (lists)
    sensor = list(x=coords$sx, y=coords$sy)
    beacon = list(x=coords$bx, y=coords$by)
    # distance between sensor and beacon
    sbd = distance(sensor, beacon)
    # difference between sbd and the distance sensor<->line Y
    diff = sbd - abs(Y - sensor$y)
    if (diff >= 0) {
        # interval on the line Y
        i = integers(sensor$x-diff, sensor$x+diff)
        # add the interval into the coverage
        coverage = interval_union(i, coverage)
        # count beacons on the line Y
        if (beacon$y == Y && !(beacon$x %in% beacons)) {
            beacons = append(beacons, beacon$x)
        }
    }
}
# close file descriptor
close(con)

# right - left interval boundary + 1 - number of beacons on line Y
print(max(coverage) - min(coverage) + 1 - length(beacons))

library(stringr)
library(sets)

distance = function(v1, v2) {
    return (abs(v1$x - v2$x) + abs(v1$y - v2$y))
}

parseLine = function(line, reg) {
    tokens = str_match(line, reg)
    return (list(
        # convert to integer
        sx=strtoi(tokens[2][1]),
        sy=strtoi(tokens[3][1]),
        bx=strtoi(tokens[4][1]),
        by=strtoi(tokens[5][1])
    ))
}
close(con)

fn = "15.input"
con = file(fn, open="r")
reg = ".*x=(?<sx>[-0-9]+), y=(?<sy>[-0-9]+): .* x=(?<bx>[-0-9]+), y=(?<by>[-0-9]+)"
sensorsX = c()
sensorsY = c()
beaconsX = c()
beaconsY = c()

while (TRUE) {
    line = readLines(con, n=1)
    if (length(line) == 0) {
        break
    }
    coords = parseLine(line, reg)
    sensorsX = append(sensorsX, coords$sx)
    sensorsY = append(sensorsY, coords$sy)
    beaconsX = append(beaconsX, coords$bx)
    beaconsY = append(beaconsY, coords$by)
}

limitX = 4000000
limitY = 4000000
lineY = integers(0, limitX)

# sweep line from 0 to 4 000 000
for (i in 0:limitY) {
    coverage = interval()
    for (j in 1:length(sensorsX)) {
        sx = sensorsX[[j]]
        sy = sensorsY[[j]]
        bx = beaconsX[[j]]
        by = beaconsY[[j]]
        dis = abs(sx - bx) + abs(sy - by)
        diff = dis - abs(i - sy)
        # if the signal has some intersection with the lineY
        if (diff >= 0) {
            # area on lineY covered by the signal
            inter = integers(sx-diff, sx+diff)
            # union with the previous areas
            coverage = interval_union(inter, coverage)
        }
    }
    # if lineY - coverage is not empty, we have the Y and X!
    intdiff = interval_intersection(interval_symdiff(lineY, coverage), lineY)
    if (!interval_is_empty(intdiff)) {
        print(intdiff * 4000000 + i)
    }
}