Given a range of values and a starting prefix, generate all the values in between (as strings), but dont include digits if all the values sub range are included. I.E. treat all missing trailing "digits" as wildcards.
This is simmilar to an IP prefix without the prefix size, collapsing full ranges into a wildcard, or Geohash filling (but in 1d).
In Geohash filling, missing digits indicate a "rectangle" that includes all the smaller "rectangles".
In the more complex 2d case, this can be used to fill any 2d shape with the fewest number of rectangles (within a given precision).
Examples:
(this one uses * as a wildcard, but the desired result is to just drop the wildcards)
prefix: 123
start: 11
end: 33
Output:
[
// all the (final) digits from 1 to 9
'12311', '12312', '12313', '12314', '12315',
'12316', '12317', '12318', '12319',
'1232*', // notice the wildcard here (as an example only) implies all the digits from 0 to 9
'12330', '12331', '12332', '12333' // from 0 to 3
]
prefix: 00000 (leading zeroes must be strings)
start: 00
end: 9 (assume missing digits for end are all nines)
Output:
[ '00000' ] //just the prefix digits, as all the range digits are collapsed
prefix: ''
start: 11111
end: 33333
Output:
[
// 5 digits
'11111', '11112', '11113', '11114', '11115',
'11116', '11117', '11118', '11119',
// 4
'1112', '1113', '1114', '1115', '1116',
'1117', '1118', '1119',
// 3
'112', '113', '114', '115', '116',
'117', '118', '119',
// 2
'12', '13', '14', '15', '16',
'17', '18', '19',
// 1
'2',
// 2
'30', '31', '32',
// 3
'330', '331', '332',
// 4
'3330', '3331', '3332',
// 5
'33330', '33331', '33332', '33333'
]
prefix: '9870' (for ease of use, accept both strings and numbers as inputs)
start: '' (assume missing digits for start are all zeroes)
end: '28'
Output:
[
'98700', '98701',
'987020', '987021', '987022', '987023', '987024', '987025',
'987026', '987027', '987028'
]
The goal is to find the most concise or readable solution. This problem has complexities that should be hideable with good (standard) libray calls, etc. Also, the recursive method is only one possibility, and wouldn't perform for larger ranges (unless made into a Proper Tail Call in an engine that supports PTCs). A numeric method might be a better option...
An additional challenge would be to generalize this to any ordered character set, not just numeric sets (The Geohash character set, for example).
function normalizeRange (prefix, start, end) {
prefix = prefix.toString()
start = start.toString().padEnd(end.length, '0')
end = end.toString().padEnd(start.length, '9')
while (start.length > 0 && start[0] === end[0]) {
prefix += start[0]
start = start.slice(1)
end = end.slice(1)
}
while (start.slice(-1) === '0' && end.slice(-1) === '9') {
start = start.slice(0, -1)
end = end.slice(0, -1)
}
return { prefix, start, end }
}
function prefixedRange (prefix, start, end) {
return Array.from({ length: end - start + 1 }, (_, index) => `${prefix}${+start + index}`)
}
function fillRangeWithPrefixes ({ end, start, prefix }) {
;({ prefix, start, end } = normalizeRange(prefix, start, end))
if (start.length < 1) return [prefix]
if (start.length === 1) return prefixedRange(prefix, start, end)
return [
...fillRangeWithPrefixes({ prefix, start, end: start[0] }),
...(end[0] - start[0] <= 1
? []
: fillRangeWithPrefixes({ prefix, start: +start[0] + 1, end: end[0] - 1 })),
...fillRangeWithPrefixes({ prefix, start: end[0], end })
]
}// Since Node 10, we're using Mocha.
// You can use `chai` for assertions.
const chai = require("chai");
const assert = chai.assert;
// Uncomment the following line to disable truncating failure messages for deep equals, do:
// chai.config.truncateThreshold = 0;
describe("fillRangeWithPrefixes", function() {
specify("p: 123, s: 11, e: 33", function() {
const range = {prefix: 123, start: 11, end: 33 };
const result = fillRangeWithPrefixes(range);
assert.deepEqual(
result,
[
// all the (final) digits from 1 to 9
'12311', '12312', '12313', '12314', '12315',
'12316', '12317', '12318', '12319',
'1232', // implies all the digits from 0 to 9
'12330', '12331', '12332', '12333' // from 0 to 3
]
);
});
specify("p: '00000', s: '00', e: 9", function() {
const range = {prefix: '00000', start: '00', end: 9 };
const result = fillRangeWithPrefixes(range);
assert.deepEqual(
result,
[ '00000' ]
);
});
specify("p: '', s: 11111, e: 33333", function() {
const range = {prefix: '', start: 11111, end: 33333 };
const result = fillRangeWithPrefixes(range);
assert.deepEqual(
result,
[
// 5 digits
'11111', '11112', '11113', '11114', '11115',
'11116', '11117', '11118', '11119',
// 4
'1112', '1113', '1114', '1115', '1116',
'1117', '1118', '1119',
// 3
'112', '113', '114', '115', '116',
'117', '118', '119',
// 2
'12', '13', '14', '15', '16',
'17', '18', '19',
// 1
'2',
// 2
'30', '31', '32',
// 3
'330', '331', '332',
// 4
'3330', '3331', '3332',
// 5
'33330', '33331', '33332', '33333'
]
);
});
specify("p: '9870', s: '', e: '28'", function() {
const range = {prefix: '9870', start: '', end: '28' };
const result = fillRangeWithPrefixes(range);
assert.deepEqual(
result,
[
'98700', '98701',
'987020', '987021', '987022', '987023', '987024', '987025',
'987026', '987027', '987028'
]
);
});
});