Algorithm for rounding and clamping a number to specific ends

Question

I'm looking for an efficient algorithm that clamps an integer value within a range, while also changing its base10 end to one of multiple, variable length ends.

This should clamp a value between the min and max, while changing the end to one of the specific ends defined in ends, as close as possible to the original value.

Example input data:

ends: [26, 201, 330] (sorted list of integers, at least a factor 10 smaller than <value>)
min: 5350
max: 7392

value: 2000 -> 5426
value: 6205 -> 6201
value: 7400 -> 7330

I'll implement this in Go, but any pseudocode or other imperative language is also appreciated.

Answer 1

Assuming your ends list isn't massive, it's probably simplest to pre-compute all the valid values between vmin and vmax and then binary search that list to find the closest value. You could implement that like this in python:

import math

def expand_ends(ends, vmin, vmax):
    all_ends = []
    for end in ends:
        inc = 10 if end < 10 else 10 ** (int(math.log10(end)) + 1)
        v = vmin - vmin % inc + end
        if v < vmin:
            v += inc
        while True:
            if v > vmax:
                break
            all_ends.append(v)
            v += inc
    return sorted(all_ends)

def search(values, v):
    # check for end cases (clamp to range)
    # this simplifies the search as we don't need to worry about not
    # finding an insertion point in the list
    if v <= values[0]:
        return values[0]
    if v >= values[-1]:
        return values[-1]
    
    # binary search for closest value
    low = 0
    hi = len(values)
    while (low < hi):
        mid = (low + hi) // 2
        vmid = values[mid]
        if vmid < v:
            vmidp1 = values[mid+1]
            if vmidp1 > v:
                return vmid if (v - vmid) < (vmidp1 - v) else vmidp1
            low = mid + 1
        elif vmid > v:
            vmidm1 = values[mid-1]
            if vmidm1 < v:
                return vmid if (vmid - v) < (v - vmidm1) else vmidm1
            hi = mid
        else:
            return vmid

Usage:

ends = [26, 201, 330]
vmin, vmax = 5350, 7392
all_ends = expand_ends(ends, vmin, vmax)
# [5426, 5526, 5626, 5726, 5826, 5926, 6026, 6126, 6201, 6226, 6326, 6330, 6426, 6526, 6626, 6726, 6826, 6926, 7026, 7126, 7201, 7226, 7326, 7330]

search(all_ends, 2000)
# 5426
search(all_ends, 6205)
# 6201
search(all_ends, 6213)
# 6201
search(all_ends, 6214)
# 6226
search(all_ends, 6328)
# 6326
search(all_ends, 6329)
# 6330
search(all_ends, 7400)
# 7330

Update

I converted the other answer's code to python and used timeit to benchmark the two solutions iterating over every input from vmin-100 to vmin+100:

timeit.timeit(setup='''
import math
def expand_ends(ends, vmin, vmax):
    all_ends = []
    for end in ends:
        inc = 10 if end < 10 else 10 ** (int(math.log10(end)) + 1)
        v = vmin - vmin % inc + end
        if v < vmin:
            v += inc
        while True:
            if v > vmax:
                break
            all_ends.append(v)
            v += inc
    return sorted(all_ends)

def search(values, v):
    # check for end cases (clamp to range)
    # this simplifies the search as we don't need to worry about not
    # finding an insertion point in the list
    if v <= values[0]:
        return values[0]
    if v >= values[-1]:
        return values[-1]
    
    # binary search for closest value
    low = 0
    hi = len(values)
    while (low < hi):
        mid = (low + hi) // 2
        vmid = values[mid]
        if vmid < v:
            vmidp1 = values[mid+1]
            if vmidp1 > v:
                return vmid if (v - vmid) < (vmidp1 - v) else vmidp1
            low = mid + 1
        elif vmid > v:
            vmidm1 = values[mid-1]
            if vmidm1 < v:
                return vmid if (vmid - v) < (v - vmidm1) else vmidm1
            hi = mid
        else:
            return vmid

ends = [26, 201, 330]
vmin, vmax = 5350, 7392
''', stmt='''
all_ends = expand_ends(ends, vmin, vmax)
out = [search(all_ends, v) for v in range(vmin-100, vmax+100)]
''', number = 1_000)

timeit.timeit(setup='''
def nextPowerOf10(n):
    if n == 0:
        return 10    # mathematically not correct but works here
    x = 1
    while n > 0:
        x = x * 10
        n = n // 10    # integer division
    return x

def clampEnd(n, vmin, vmax, end):
    m = max(vmin, min(vmax, n))
    p = nextPowerOf10(end)
    m = m - m % p + end
    diff = -1
    ret = -1
    for x in [m - p, m, m + p]:
        # this rounds down, make abs(n - x) <= diff to round up on equal distance
        if vmin <= x <= vmax and (diff < 0 or abs(n - x) < diff):
            diff = abs(n - x)
            ret = x
    return ret    # returns -1 if no number in range ends with end

def bestEnd(v, ends):
    diffs = [abs(v-end) for end in ends]
    return ends[diffs.index(min(diffs))]

ends = [26, 201, 330]
vmin, vmax = 5350, 7392
''', stmt='''
out = [bestEnd(v, [clampEnd(v, vmin, vmax, end) for end in ends]) for v in range(vmin-100, vmax+100)]
''', number = 1_000)

On my computer, my solution takes 0.57 seconds while the other solution takes 4.56 seconds.

Answer 2

I guess you know how to clamp:

clamp(n, min, max) = max(min, min(max, n))

Then to remove the end and replace it with what it should end, you need the next higher power of 10:

nextPowerOf10(n) {
    if (n == 0)
        return 10    // mathematically not correct but works here
    x = 1
    while (n > 0) {
        x = x * 10
        n = n / 10    // integer division
    }
    return x
}

So replacing the end of a number becomes simple:

replace(n, end) = n - n % nextPowerOf10(end) + end

Then you can check the other candidates on both sides, so when m = replace(clamp(n, min, max), end) and p = nextPowerOf10(end), the other candidates are: m - p and m + p, everything put together:

clampEnd(n, min, max, end) {
    m = clamp(n, min, max)
    p = nextPowerOf10(end)
    m = m - m % p + end
    diff = -1
    ret = -1
    for (x in [m - p, m, m + p]) {
        // this rounds down, make abs(n - x) <= diff to round up on equal distance
        if (x >= min && x <= max && (diff < 0 || abs(n - x) < diff)) {
            diff = abs(n - x)
            ret = x
        }
    }
    return ret    // returns -1 if no number in range ends with end
}

Examples:

• 2000: m = clamp(2000, 5350, 7392) = 5350, p = nextPowerOf10(26) = 100, m = m - m % p + end = 5350 - 5350 % 100 + 26 = 5326, candidates = [m - p, m, m + p] = [5226, 5326, 5426], result = 5426 (only one in range).
• 6205: candidates = [5201, 6201, 7201] => 6201
• 7400: candidates = [6330, 7330, 8330] => 7330