Get consecutive integer number ranges from list of intConsolidate list of ranges that overlapConverting from...
What is the smallest unit of eos?
Why did C use the -> operator instead of reusing the . operator?
How to write a column outside the braces in a matrix?
a sore throat vs a strep throat vs strep throat
Pre-plastic human skin alternative
What's the polite way to say "I need to urinate"?
"You've called the wrong number" or "You called the wrong number"
How did Captain America manage to do this?
bldc motor, esc and battery draw, nominal vs peak
Is there really no use for MD5 anymore?
I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?
Extension of 2-adic valuation to the real numbers
Rivers without rain
Can SQL Server create collisions in system generated constraint names?
Like totally amazing interchangeable sister outfits II: The Revenge
Dynamic SOQL query relationship with field visibility for Users
Pulling the rope with one hand is as heavy as with two hands?
What is the most expensive material in the world that could be used to create Pun-Pun's lute?
What is causing the white spot to appear in some of my pictures
Is the claim "Employers won't employ people with no 'social media presence'" realistic?
Phrase for the opposite of "foolproof"
How do I reattach a shelf to the wall when it ripped out of the wall?
Apply MapThread to all but one variable
Why was the Spitfire's elliptical wing almost uncopied by other aircraft of World War 2?
Get consecutive integer number ranges from list of int
Consolidate list of ranges that overlapConverting from binary to unaryFinding the indices of the two items whose price adds up to to a valueHackerEarth - SimpleFunctionFollow-up 1: Compare 2 unordered, rooted trees for shape-isomorphismHackerrank: Max ScoreFilter data with optional parametersAt least 2 paths down the binary tree have the same sumLeetcode 54: Spiral MatrixRecursive function challenge
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
This is an algorithm to return a list of consecutive integer ranges from a list of integers.
The practical use of such an algorithm is to filter lists more efficiently, i.e. rather than check e.g. 1000 items (1..1000; x==1 || x==2 || ... || x==1000), it might be possible to check only 2 items (x >= 1 && x <= 1000).
Does this algorithm have any mistakes, can it be optimized, or are there any other improvements you can suggest?
(As a side note: I know this code does not follow the standard C# naming conventions. I do not like to follow that particular convention; I prefer "snake_case" as it is easier on my eyes.)
Sample output:
(x >= 0 && x <= 1690)
(x >= 13642 && x <= 15331)
(x >= 27283 && x <= 27296)
(x >= 27769 && x <= 27776)
(x >= 28249 && x <= 28256)
(x >= 28729 && x <= 28736)
(x >= 29209 && x <= 29222)
The algorithm (built Visual Studio 2017, C# 7.3, .NET 4.7.2):
public static List<(int from, int to)> get_consecutive_ranges(List<int> fids)
{
if (fids == null || fids.Count == 0) return null;
fids = fids.OrderBy(a => a).Distinct().ToList();
var fids_fast = new List<(int from, int to)>();
var is_conseq_with_last = true;
var start_index = 0;
var end_index = 0;
for (var fids_index = 0; fids_index < fids.Count; fids_index++)
{
var first = fids_index == 0;
var last = fids_index == fids.Count - 1;
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
if (!is_conseq_with_last && !first && !last)
{
end_index = !first && !last ? fids_index - 1 : fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
else if (last)
{
if (!is_conseq_with_last)
{
if (!first)
{
end_index = fids_index - 1;
}
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
end_index = fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
}
}
fids_fast.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return fids_fast;
}
Example use:
// slow:
body = body.Where(a => fids.Contains(a.fid)).ToList();
// fast:
body = body.Where(a => fids_fast.Any(x => a.fid >= x.from && a.fid <= x.to)).ToList();
c# algorithm interval
New contributor
$endgroup$
add a comment |
$begingroup$
This is an algorithm to return a list of consecutive integer ranges from a list of integers.
The practical use of such an algorithm is to filter lists more efficiently, i.e. rather than check e.g. 1000 items (1..1000; x==1 || x==2 || ... || x==1000), it might be possible to check only 2 items (x >= 1 && x <= 1000).
Does this algorithm have any mistakes, can it be optimized, or are there any other improvements you can suggest?
(As a side note: I know this code does not follow the standard C# naming conventions. I do not like to follow that particular convention; I prefer "snake_case" as it is easier on my eyes.)
Sample output:
(x >= 0 && x <= 1690)
(x >= 13642 && x <= 15331)
(x >= 27283 && x <= 27296)
(x >= 27769 && x <= 27776)
(x >= 28249 && x <= 28256)
(x >= 28729 && x <= 28736)
(x >= 29209 && x <= 29222)
The algorithm (built Visual Studio 2017, C# 7.3, .NET 4.7.2):
public static List<(int from, int to)> get_consecutive_ranges(List<int> fids)
{
if (fids == null || fids.Count == 0) return null;
fids = fids.OrderBy(a => a).Distinct().ToList();
var fids_fast = new List<(int from, int to)>();
var is_conseq_with_last = true;
var start_index = 0;
var end_index = 0;
for (var fids_index = 0; fids_index < fids.Count; fids_index++)
{
var first = fids_index == 0;
var last = fids_index == fids.Count - 1;
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
if (!is_conseq_with_last && !first && !last)
{
end_index = !first && !last ? fids_index - 1 : fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
else if (last)
{
if (!is_conseq_with_last)
{
if (!first)
{
end_index = fids_index - 1;
}
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
end_index = fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
}
}
fids_fast.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return fids_fast;
}
Example use:
// slow:
body = body.Where(a => fids.Contains(a.fid)).ToList();
// fast:
body = body.Where(a => fids_fast.Any(x => a.fid >= x.from && a.fid <= x.to)).ToList();
c# algorithm interval
New contributor
$endgroup$
1
$begingroup$
@t3chb0t no I just dislike camel case as I personally find it to be quite difficult to read and thus more likely to cause eye strain. Thanks for your suggestion, I will add it to my question.
$endgroup$
– Aalawlx
6 hours ago
$begingroup$
One more suggestion... if you have any running demo console/unit-test code (which I strongly believe) then you should add it too. It'll make it easier to review your algorithm as people will be able to actually execute it.
$endgroup$
– t3chb0t
5 hours ago
1
$begingroup$
What doesfids
stand for? Would help me understand what your algorithm is doing better ( at least I would hope ).
$endgroup$
– Shelby115
5 hours ago
$begingroup$
@Shelby115 actually, your naming makes it more generic, which is good. However, to answer the question, fids means 'features ids'. The reason I am writing this method is to filter criteria-specific feature id numbers from millions of id numbers (integers). The actual use case is machine learning, classification specifically, where millions of features are available, but only a small subset can be used or tested together.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
$begingroup$
This is an algorithm to return a list of consecutive integer ranges from a list of integers.
The practical use of such an algorithm is to filter lists more efficiently, i.e. rather than check e.g. 1000 items (1..1000; x==1 || x==2 || ... || x==1000), it might be possible to check only 2 items (x >= 1 && x <= 1000).
Does this algorithm have any mistakes, can it be optimized, or are there any other improvements you can suggest?
(As a side note: I know this code does not follow the standard C# naming conventions. I do not like to follow that particular convention; I prefer "snake_case" as it is easier on my eyes.)
Sample output:
(x >= 0 && x <= 1690)
(x >= 13642 && x <= 15331)
(x >= 27283 && x <= 27296)
(x >= 27769 && x <= 27776)
(x >= 28249 && x <= 28256)
(x >= 28729 && x <= 28736)
(x >= 29209 && x <= 29222)
The algorithm (built Visual Studio 2017, C# 7.3, .NET 4.7.2):
public static List<(int from, int to)> get_consecutive_ranges(List<int> fids)
{
if (fids == null || fids.Count == 0) return null;
fids = fids.OrderBy(a => a).Distinct().ToList();
var fids_fast = new List<(int from, int to)>();
var is_conseq_with_last = true;
var start_index = 0;
var end_index = 0;
for (var fids_index = 0; fids_index < fids.Count; fids_index++)
{
var first = fids_index == 0;
var last = fids_index == fids.Count - 1;
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
if (!is_conseq_with_last && !first && !last)
{
end_index = !first && !last ? fids_index - 1 : fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
else if (last)
{
if (!is_conseq_with_last)
{
if (!first)
{
end_index = fids_index - 1;
}
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
end_index = fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
}
}
fids_fast.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return fids_fast;
}
Example use:
// slow:
body = body.Where(a => fids.Contains(a.fid)).ToList();
// fast:
body = body.Where(a => fids_fast.Any(x => a.fid >= x.from && a.fid <= x.to)).ToList();
c# algorithm interval
New contributor
$endgroup$
This is an algorithm to return a list of consecutive integer ranges from a list of integers.
The practical use of such an algorithm is to filter lists more efficiently, i.e. rather than check e.g. 1000 items (1..1000; x==1 || x==2 || ... || x==1000), it might be possible to check only 2 items (x >= 1 && x <= 1000).
Does this algorithm have any mistakes, can it be optimized, or are there any other improvements you can suggest?
(As a side note: I know this code does not follow the standard C# naming conventions. I do not like to follow that particular convention; I prefer "snake_case" as it is easier on my eyes.)
Sample output:
(x >= 0 && x <= 1690)
(x >= 13642 && x <= 15331)
(x >= 27283 && x <= 27296)
(x >= 27769 && x <= 27776)
(x >= 28249 && x <= 28256)
(x >= 28729 && x <= 28736)
(x >= 29209 && x <= 29222)
The algorithm (built Visual Studio 2017, C# 7.3, .NET 4.7.2):
public static List<(int from, int to)> get_consecutive_ranges(List<int> fids)
{
if (fids == null || fids.Count == 0) return null;
fids = fids.OrderBy(a => a).Distinct().ToList();
var fids_fast = new List<(int from, int to)>();
var is_conseq_with_last = true;
var start_index = 0;
var end_index = 0;
for (var fids_index = 0; fids_index < fids.Count; fids_index++)
{
var first = fids_index == 0;
var last = fids_index == fids.Count - 1;
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
if (!is_conseq_with_last && !first && !last)
{
end_index = !first && !last ? fids_index - 1 : fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
else if (last)
{
if (!is_conseq_with_last)
{
if (!first)
{
end_index = fids_index - 1;
}
fids_fast.Add((fids[start_index], fids[end_index]));
start_index = fids_index;
}
end_index = fids_index;
fids_fast.Add((fids[start_index], fids[end_index]));
}
}
fids_fast.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return fids_fast;
}
Example use:
// slow:
body = body.Where(a => fids.Contains(a.fid)).ToList();
// fast:
body = body.Where(a => fids_fast.Any(x => a.fid >= x.from && a.fid <= x.to)).ToList();
c# algorithm interval
c# algorithm interval
New contributor
New contributor
edited 40 mins ago
200_success
132k20158423
132k20158423
New contributor
asked 6 hours ago
AalawlxAalawlx
1214
1214
New contributor
New contributor
1
$begingroup$
@t3chb0t no I just dislike camel case as I personally find it to be quite difficult to read and thus more likely to cause eye strain. Thanks for your suggestion, I will add it to my question.
$endgroup$
– Aalawlx
6 hours ago
$begingroup$
One more suggestion... if you have any running demo console/unit-test code (which I strongly believe) then you should add it too. It'll make it easier to review your algorithm as people will be able to actually execute it.
$endgroup$
– t3chb0t
5 hours ago
1
$begingroup$
What doesfids
stand for? Would help me understand what your algorithm is doing better ( at least I would hope ).
$endgroup$
– Shelby115
5 hours ago
$begingroup$
@Shelby115 actually, your naming makes it more generic, which is good. However, to answer the question, fids means 'features ids'. The reason I am writing this method is to filter criteria-specific feature id numbers from millions of id numbers (integers). The actual use case is machine learning, classification specifically, where millions of features are available, but only a small subset can be used or tested together.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
1
$begingroup$
@t3chb0t no I just dislike camel case as I personally find it to be quite difficult to read and thus more likely to cause eye strain. Thanks for your suggestion, I will add it to my question.
$endgroup$
– Aalawlx
6 hours ago
$begingroup$
One more suggestion... if you have any running demo console/unit-test code (which I strongly believe) then you should add it too. It'll make it easier to review your algorithm as people will be able to actually execute it.
$endgroup$
– t3chb0t
5 hours ago
1
$begingroup$
What doesfids
stand for? Would help me understand what your algorithm is doing better ( at least I would hope ).
$endgroup$
– Shelby115
5 hours ago
$begingroup$
@Shelby115 actually, your naming makes it more generic, which is good. However, to answer the question, fids means 'features ids'. The reason I am writing this method is to filter criteria-specific feature id numbers from millions of id numbers (integers). The actual use case is machine learning, classification specifically, where millions of features are available, but only a small subset can be used or tested together.
$endgroup$
– Aalawlx
4 hours ago
1
1
$begingroup$
@t3chb0t no I just dislike camel case as I personally find it to be quite difficult to read and thus more likely to cause eye strain. Thanks for your suggestion, I will add it to my question.
$endgroup$
– Aalawlx
6 hours ago
$begingroup$
@t3chb0t no I just dislike camel case as I personally find it to be quite difficult to read and thus more likely to cause eye strain. Thanks for your suggestion, I will add it to my question.
$endgroup$
– Aalawlx
6 hours ago
$begingroup$
One more suggestion... if you have any running demo console/unit-test code (which I strongly believe) then you should add it too. It'll make it easier to review your algorithm as people will be able to actually execute it.
$endgroup$
– t3chb0t
5 hours ago
$begingroup$
One more suggestion... if you have any running demo console/unit-test code (which I strongly believe) then you should add it too. It'll make it easier to review your algorithm as people will be able to actually execute it.
$endgroup$
– t3chb0t
5 hours ago
1
1
$begingroup$
What does
fids
stand for? Would help me understand what your algorithm is doing better ( at least I would hope ).$endgroup$
– Shelby115
5 hours ago
$begingroup$
What does
fids
stand for? Would help me understand what your algorithm is doing better ( at least I would hope ).$endgroup$
– Shelby115
5 hours ago
$begingroup$
@Shelby115 actually, your naming makes it more generic, which is good. However, to answer the question, fids means 'features ids'. The reason I am writing this method is to filter criteria-specific feature id numbers from millions of id numbers (integers). The actual use case is machine learning, classification specifically, where millions of features are available, but only a small subset can be used or tested together.
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 actually, your naming makes it more generic, which is good. However, to answer the question, fids means 'features ids'. The reason I am writing this method is to filter criteria-specific feature id numbers from millions of id numbers (integers). The actual use case is machine learning, classification specifically, where millions of features are available, but only a small subset can be used or tested together.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
As a pre-note, I had to translate everything to camelCase and PascalCase because I was having a very difficult time reading your code. No judgments, just understand I was running short on time and didn't translate it back on the conclusion.
Readability
Use meaningful names.
fids
I changed tointegers
as from your description I gather it's the list of integers used to create the ranges.
fids_index
seems very noisy. Standard convention isi
,j
, etc. When you reduce the iterator variable down to a single character it's much easier to focus on what actually matters.- Booleans should be prefixed with
Is
orHas
orWas
etc. So in this caseIsFirst
andIsLast
instead offirst
andlast
makes it easier to read as english. You could even consider usingvar isNotFirst = i != 0;
as you only use!first
in the algorithm. - Last vs Previous.
is_conseq_with_last
is refering to previous, so I switched it to previous to avoid confusion withlast
.
start_index
andend_index
sound like they would be0
andintegers.Count
. They're the start and end of the range you're tracking, let's name them accordingly:rangeStart
andrangeEnd
.
If-Statement Ordering & Flow
We've all been there, written an algorithm, tested it, and it works, all done right? Well, sometimes that algorithm can be restructured to express what we're actually doing much clearer.
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
There's a common denominator here, !first
let's work with that, clearly neither of these happen if it's true.
if (!first)
{
if (fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else
{
is_conseq_with_last = false;
}
}
Well, now it's obvious that inner if-statement can be reduced.
if (!first)
{
is_conseq_with_last = fids[fids_index - 1] == fids[fids_index] - 1;
}
And if you wanted, a ternary operator.
is_conseq_with_last = !first && fids[fids_index - 1] == fids[fids_index] - 1;
And it's now also obvious that you're setting the variable with each iteration, so there's no need to declare it outside the loop.
Similar can be done with the bottom if-statement. Here's what I ended up with altogether.
My Version
I am running short on time so there might be a mistake or two and it's still in my coding style so don't take it for face value and try to apply the concepts I'm showing above yourself.
public static List<(int from, int to)> GetConsecutiveRanges(List<int> integers)
{
if (integers == null || integers.Count == 0) { return null; }
integers = integers.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var rangeStart = 0;
var rangeEnd = 0;
for (var i = 0; i < integers.Count; i++)
{
var isFirst = i == 0;
var isLast = i == integers.Count - 1;
var isConsecutiveFromPrevious = isFirst == false && integers[i-1] == integers[i] - 1;
if (last)
{
if (isConsecutiveFromPrevious == false)
{
rangeEnd = isFirst == false ? i - 1 : rangeEnd;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
rangeEnd = i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
}
else if (isConsecutiveFromPrevious == false && isFirst == false)
{
rangeEnd = isFirst == false && isLast == false ? i - 1 : i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
}
ranges.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return ranges;
}
$endgroup$
$begingroup$
I wonder whether it would be more efficient to swap these two calls.OrderBy(a => a).Distinct().
- just thinking aloud...
$endgroup$
– t3chb0t
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
$begingroup$
Your code is really complicated. First, your code should be abstracted a little more. It is not specific to feature IDs, therefore the terminology should not use these words. The same algorithm can be used to select which pages to print from a document, therefore the variables should be just nums
and ranges
. To test your current code, I wrote:
[Test]
public void TestRanges()
{
Assert.AreEqual("", Str(Ranges(new List<int>())));
Assert.AreEqual("1", Str(Ranges(new List<int> { 1 })));
Assert.AreEqual("1-5", Str(Ranges(new List<int> { 1, 2, 3, 4, 5 })));
Assert.AreEqual("1-3, 5", Str(Ranges(new List<int> { 1, 2, 3, 5 })));
Assert.AreEqual("1, 3, 5-6", Str(Ranges(new List<int> { 1, 3, 5, 6 })));
}
I wrote a helper function Str
so that I don't have to construct a list of ranges for each test case:
public static string Str(List<(int from, int to)> ranges)
{
var parts = new List<string>();
foreach (var range in ranges) {
if (range.from == range.to) {
parts.Add(range.from.ToString());
} else {
parts.Add(range.@from + "-" + range.to);
}
}
return string.Join(", ", parts);
}
After renaming your function to Ranges
, these tests ran successfully. So I was ready to refactor your code. I did not really do this since your code looked too complicated to start with. Instead, I remembered that I had successfully used the following pattern quite often:
var start = ...;
while (start < nums.Count) {
var end = ...;
while (end < nums.Count) {
}
}
With this knowledge I wrote the following code:
public static List<(int from, int to)> Ranges(List<int> nums)
{
nums = nums.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var start = 0;
while (start < nums.Count) {
var end = start + 1; // the range is from [start, end).
while (end < nums.Count && nums[end - 1] + 1 == nums[end]) {
end++;
}
ranges.Add((nums[start], nums[end - 1]));
start = end; // continue after the current range
}
return ranges;
}
This code doesn't need any special cases for the last range, or anything else. A range either stops when the end of the numbers is reached, or when the following number is not consecutive. This sounds sensible, and this is exactly what the code is doing.
I removed the check for nums == null
since it is not necessary. Collections should never be null, and if they are, the code immediately throws an exception, which is fine.
I also removed the special case for nums.Count == 0
since returning an empty list is much better than returning null. Again, expressions that have collection type should never be null. The test cases cover this case, so there's nothing to worry about.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Aalawlx is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f219204%2fget-consecutive-integer-number-ranges-from-list-of-int%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As a pre-note, I had to translate everything to camelCase and PascalCase because I was having a very difficult time reading your code. No judgments, just understand I was running short on time and didn't translate it back on the conclusion.
Readability
Use meaningful names.
fids
I changed tointegers
as from your description I gather it's the list of integers used to create the ranges.
fids_index
seems very noisy. Standard convention isi
,j
, etc. When you reduce the iterator variable down to a single character it's much easier to focus on what actually matters.- Booleans should be prefixed with
Is
orHas
orWas
etc. So in this caseIsFirst
andIsLast
instead offirst
andlast
makes it easier to read as english. You could even consider usingvar isNotFirst = i != 0;
as you only use!first
in the algorithm. - Last vs Previous.
is_conseq_with_last
is refering to previous, so I switched it to previous to avoid confusion withlast
.
start_index
andend_index
sound like they would be0
andintegers.Count
. They're the start and end of the range you're tracking, let's name them accordingly:rangeStart
andrangeEnd
.
If-Statement Ordering & Flow
We've all been there, written an algorithm, tested it, and it works, all done right? Well, sometimes that algorithm can be restructured to express what we're actually doing much clearer.
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
There's a common denominator here, !first
let's work with that, clearly neither of these happen if it's true.
if (!first)
{
if (fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else
{
is_conseq_with_last = false;
}
}
Well, now it's obvious that inner if-statement can be reduced.
if (!first)
{
is_conseq_with_last = fids[fids_index - 1] == fids[fids_index] - 1;
}
And if you wanted, a ternary operator.
is_conseq_with_last = !first && fids[fids_index - 1] == fids[fids_index] - 1;
And it's now also obvious that you're setting the variable with each iteration, so there's no need to declare it outside the loop.
Similar can be done with the bottom if-statement. Here's what I ended up with altogether.
My Version
I am running short on time so there might be a mistake or two and it's still in my coding style so don't take it for face value and try to apply the concepts I'm showing above yourself.
public static List<(int from, int to)> GetConsecutiveRanges(List<int> integers)
{
if (integers == null || integers.Count == 0) { return null; }
integers = integers.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var rangeStart = 0;
var rangeEnd = 0;
for (var i = 0; i < integers.Count; i++)
{
var isFirst = i == 0;
var isLast = i == integers.Count - 1;
var isConsecutiveFromPrevious = isFirst == false && integers[i-1] == integers[i] - 1;
if (last)
{
if (isConsecutiveFromPrevious == false)
{
rangeEnd = isFirst == false ? i - 1 : rangeEnd;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
rangeEnd = i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
}
else if (isConsecutiveFromPrevious == false && isFirst == false)
{
rangeEnd = isFirst == false && isLast == false ? i - 1 : i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
}
ranges.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return ranges;
}
$endgroup$
$begingroup$
I wonder whether it would be more efficient to swap these two calls.OrderBy(a => a).Distinct().
- just thinking aloud...
$endgroup$
– t3chb0t
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
$begingroup$
As a pre-note, I had to translate everything to camelCase and PascalCase because I was having a very difficult time reading your code. No judgments, just understand I was running short on time and didn't translate it back on the conclusion.
Readability
Use meaningful names.
fids
I changed tointegers
as from your description I gather it's the list of integers used to create the ranges.
fids_index
seems very noisy. Standard convention isi
,j
, etc. When you reduce the iterator variable down to a single character it's much easier to focus on what actually matters.- Booleans should be prefixed with
Is
orHas
orWas
etc. So in this caseIsFirst
andIsLast
instead offirst
andlast
makes it easier to read as english. You could even consider usingvar isNotFirst = i != 0;
as you only use!first
in the algorithm. - Last vs Previous.
is_conseq_with_last
is refering to previous, so I switched it to previous to avoid confusion withlast
.
start_index
andend_index
sound like they would be0
andintegers.Count
. They're the start and end of the range you're tracking, let's name them accordingly:rangeStart
andrangeEnd
.
If-Statement Ordering & Flow
We've all been there, written an algorithm, tested it, and it works, all done right? Well, sometimes that algorithm can be restructured to express what we're actually doing much clearer.
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
There's a common denominator here, !first
let's work with that, clearly neither of these happen if it's true.
if (!first)
{
if (fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else
{
is_conseq_with_last = false;
}
}
Well, now it's obvious that inner if-statement can be reduced.
if (!first)
{
is_conseq_with_last = fids[fids_index - 1] == fids[fids_index] - 1;
}
And if you wanted, a ternary operator.
is_conseq_with_last = !first && fids[fids_index - 1] == fids[fids_index] - 1;
And it's now also obvious that you're setting the variable with each iteration, so there's no need to declare it outside the loop.
Similar can be done with the bottom if-statement. Here's what I ended up with altogether.
My Version
I am running short on time so there might be a mistake or two and it's still in my coding style so don't take it for face value and try to apply the concepts I'm showing above yourself.
public static List<(int from, int to)> GetConsecutiveRanges(List<int> integers)
{
if (integers == null || integers.Count == 0) { return null; }
integers = integers.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var rangeStart = 0;
var rangeEnd = 0;
for (var i = 0; i < integers.Count; i++)
{
var isFirst = i == 0;
var isLast = i == integers.Count - 1;
var isConsecutiveFromPrevious = isFirst == false && integers[i-1] == integers[i] - 1;
if (last)
{
if (isConsecutiveFromPrevious == false)
{
rangeEnd = isFirst == false ? i - 1 : rangeEnd;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
rangeEnd = i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
}
else if (isConsecutiveFromPrevious == false && isFirst == false)
{
rangeEnd = isFirst == false && isLast == false ? i - 1 : i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
}
ranges.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return ranges;
}
$endgroup$
$begingroup$
I wonder whether it would be more efficient to swap these two calls.OrderBy(a => a).Distinct().
- just thinking aloud...
$endgroup$
– t3chb0t
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
$begingroup$
As a pre-note, I had to translate everything to camelCase and PascalCase because I was having a very difficult time reading your code. No judgments, just understand I was running short on time and didn't translate it back on the conclusion.
Readability
Use meaningful names.
fids
I changed tointegers
as from your description I gather it's the list of integers used to create the ranges.
fids_index
seems very noisy. Standard convention isi
,j
, etc. When you reduce the iterator variable down to a single character it's much easier to focus on what actually matters.- Booleans should be prefixed with
Is
orHas
orWas
etc. So in this caseIsFirst
andIsLast
instead offirst
andlast
makes it easier to read as english. You could even consider usingvar isNotFirst = i != 0;
as you only use!first
in the algorithm. - Last vs Previous.
is_conseq_with_last
is refering to previous, so I switched it to previous to avoid confusion withlast
.
start_index
andend_index
sound like they would be0
andintegers.Count
. They're the start and end of the range you're tracking, let's name them accordingly:rangeStart
andrangeEnd
.
If-Statement Ordering & Flow
We've all been there, written an algorithm, tested it, and it works, all done right? Well, sometimes that algorithm can be restructured to express what we're actually doing much clearer.
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
There's a common denominator here, !first
let's work with that, clearly neither of these happen if it's true.
if (!first)
{
if (fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else
{
is_conseq_with_last = false;
}
}
Well, now it's obvious that inner if-statement can be reduced.
if (!first)
{
is_conseq_with_last = fids[fids_index - 1] == fids[fids_index] - 1;
}
And if you wanted, a ternary operator.
is_conseq_with_last = !first && fids[fids_index - 1] == fids[fids_index] - 1;
And it's now also obvious that you're setting the variable with each iteration, so there's no need to declare it outside the loop.
Similar can be done with the bottom if-statement. Here's what I ended up with altogether.
My Version
I am running short on time so there might be a mistake or two and it's still in my coding style so don't take it for face value and try to apply the concepts I'm showing above yourself.
public static List<(int from, int to)> GetConsecutiveRanges(List<int> integers)
{
if (integers == null || integers.Count == 0) { return null; }
integers = integers.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var rangeStart = 0;
var rangeEnd = 0;
for (var i = 0; i < integers.Count; i++)
{
var isFirst = i == 0;
var isLast = i == integers.Count - 1;
var isConsecutiveFromPrevious = isFirst == false && integers[i-1] == integers[i] - 1;
if (last)
{
if (isConsecutiveFromPrevious == false)
{
rangeEnd = isFirst == false ? i - 1 : rangeEnd;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
rangeEnd = i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
}
else if (isConsecutiveFromPrevious == false && isFirst == false)
{
rangeEnd = isFirst == false && isLast == false ? i - 1 : i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
}
ranges.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return ranges;
}
$endgroup$
As a pre-note, I had to translate everything to camelCase and PascalCase because I was having a very difficult time reading your code. No judgments, just understand I was running short on time and didn't translate it back on the conclusion.
Readability
Use meaningful names.
fids
I changed tointegers
as from your description I gather it's the list of integers used to create the ranges.
fids_index
seems very noisy. Standard convention isi
,j
, etc. When you reduce the iterator variable down to a single character it's much easier to focus on what actually matters.- Booleans should be prefixed with
Is
orHas
orWas
etc. So in this caseIsFirst
andIsLast
instead offirst
andlast
makes it easier to read as english. You could even consider usingvar isNotFirst = i != 0;
as you only use!first
in the algorithm. - Last vs Previous.
is_conseq_with_last
is refering to previous, so I switched it to previous to avoid confusion withlast
.
start_index
andend_index
sound like they would be0
andintegers.Count
. They're the start and end of the range you're tracking, let's name them accordingly:rangeStart
andrangeEnd
.
If-Statement Ordering & Flow
We've all been there, written an algorithm, tested it, and it works, all done right? Well, sometimes that algorithm can be restructured to express what we're actually doing much clearer.
if (!first && fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else if (!first)
{
is_conseq_with_last = false;
}
There's a common denominator here, !first
let's work with that, clearly neither of these happen if it's true.
if (!first)
{
if (fids[fids_index - 1] == fids[fids_index] - 1)
{
is_conseq_with_last = true;
}
else
{
is_conseq_with_last = false;
}
}
Well, now it's obvious that inner if-statement can be reduced.
if (!first)
{
is_conseq_with_last = fids[fids_index - 1] == fids[fids_index] - 1;
}
And if you wanted, a ternary operator.
is_conseq_with_last = !first && fids[fids_index - 1] == fids[fids_index] - 1;
And it's now also obvious that you're setting the variable with each iteration, so there's no need to declare it outside the loop.
Similar can be done with the bottom if-statement. Here's what I ended up with altogether.
My Version
I am running short on time so there might be a mistake or two and it's still in my coding style so don't take it for face value and try to apply the concepts I'm showing above yourself.
public static List<(int from, int to)> GetConsecutiveRanges(List<int> integers)
{
if (integers == null || integers.Count == 0) { return null; }
integers = integers.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var rangeStart = 0;
var rangeEnd = 0;
for (var i = 0; i < integers.Count; i++)
{
var isFirst = i == 0;
var isLast = i == integers.Count - 1;
var isConsecutiveFromPrevious = isFirst == false && integers[i-1] == integers[i] - 1;
if (last)
{
if (isConsecutiveFromPrevious == false)
{
rangeEnd = isFirst == false ? i - 1 : rangeEnd;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
rangeEnd = i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
}
else if (isConsecutiveFromPrevious == false && isFirst == false)
{
rangeEnd = isFirst == false && isLast == false ? i - 1 : i;
ranges.Add((integers[rangeStart], integers[rangeEnd]));
rangeStart = i;
}
}
ranges.ForEach(a => Console.WriteLine($"(x >= {a.@from} && x <= {a.to})"));
return ranges;
}
answered 4 hours ago
Shelby115Shelby115
1,646517
1,646517
$begingroup$
I wonder whether it would be more efficient to swap these two calls.OrderBy(a => a).Distinct().
- just thinking aloud...
$endgroup$
– t3chb0t
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
$begingroup$
I wonder whether it would be more efficient to swap these two calls.OrderBy(a => a).Distinct().
- just thinking aloud...
$endgroup$
– t3chb0t
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
I wonder whether it would be more efficient to swap these two calls
.OrderBy(a => a).Distinct().
- just thinking aloud...$endgroup$
– t3chb0t
4 hours ago
$begingroup$
I wonder whether it would be more efficient to swap these two calls
.OrderBy(a => a).Distinct().
- just thinking aloud...$endgroup$
– t3chb0t
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@t3chb0t I had exactly the same thought, but in the end, both methods must track values, so performance must surely be similar either way around?
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
$begingroup$
@Shelby115 There are some very interesting points in your answer - thanks a lot.
$endgroup$
– Aalawlx
4 hours ago
add a comment |
$begingroup$
Your code is really complicated. First, your code should be abstracted a little more. It is not specific to feature IDs, therefore the terminology should not use these words. The same algorithm can be used to select which pages to print from a document, therefore the variables should be just nums
and ranges
. To test your current code, I wrote:
[Test]
public void TestRanges()
{
Assert.AreEqual("", Str(Ranges(new List<int>())));
Assert.AreEqual("1", Str(Ranges(new List<int> { 1 })));
Assert.AreEqual("1-5", Str(Ranges(new List<int> { 1, 2, 3, 4, 5 })));
Assert.AreEqual("1-3, 5", Str(Ranges(new List<int> { 1, 2, 3, 5 })));
Assert.AreEqual("1, 3, 5-6", Str(Ranges(new List<int> { 1, 3, 5, 6 })));
}
I wrote a helper function Str
so that I don't have to construct a list of ranges for each test case:
public static string Str(List<(int from, int to)> ranges)
{
var parts = new List<string>();
foreach (var range in ranges) {
if (range.from == range.to) {
parts.Add(range.from.ToString());
} else {
parts.Add(range.@from + "-" + range.to);
}
}
return string.Join(", ", parts);
}
After renaming your function to Ranges
, these tests ran successfully. So I was ready to refactor your code. I did not really do this since your code looked too complicated to start with. Instead, I remembered that I had successfully used the following pattern quite often:
var start = ...;
while (start < nums.Count) {
var end = ...;
while (end < nums.Count) {
}
}
With this knowledge I wrote the following code:
public static List<(int from, int to)> Ranges(List<int> nums)
{
nums = nums.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var start = 0;
while (start < nums.Count) {
var end = start + 1; // the range is from [start, end).
while (end < nums.Count && nums[end - 1] + 1 == nums[end]) {
end++;
}
ranges.Add((nums[start], nums[end - 1]));
start = end; // continue after the current range
}
return ranges;
}
This code doesn't need any special cases for the last range, or anything else. A range either stops when the end of the numbers is reached, or when the following number is not consecutive. This sounds sensible, and this is exactly what the code is doing.
I removed the check for nums == null
since it is not necessary. Collections should never be null, and if they are, the code immediately throws an exception, which is fine.
I also removed the special case for nums.Count == 0
since returning an empty list is much better than returning null. Again, expressions that have collection type should never be null. The test cases cover this case, so there's nothing to worry about.
$endgroup$
add a comment |
$begingroup$
Your code is really complicated. First, your code should be abstracted a little more. It is not specific to feature IDs, therefore the terminology should not use these words. The same algorithm can be used to select which pages to print from a document, therefore the variables should be just nums
and ranges
. To test your current code, I wrote:
[Test]
public void TestRanges()
{
Assert.AreEqual("", Str(Ranges(new List<int>())));
Assert.AreEqual("1", Str(Ranges(new List<int> { 1 })));
Assert.AreEqual("1-5", Str(Ranges(new List<int> { 1, 2, 3, 4, 5 })));
Assert.AreEqual("1-3, 5", Str(Ranges(new List<int> { 1, 2, 3, 5 })));
Assert.AreEqual("1, 3, 5-6", Str(Ranges(new List<int> { 1, 3, 5, 6 })));
}
I wrote a helper function Str
so that I don't have to construct a list of ranges for each test case:
public static string Str(List<(int from, int to)> ranges)
{
var parts = new List<string>();
foreach (var range in ranges) {
if (range.from == range.to) {
parts.Add(range.from.ToString());
} else {
parts.Add(range.@from + "-" + range.to);
}
}
return string.Join(", ", parts);
}
After renaming your function to Ranges
, these tests ran successfully. So I was ready to refactor your code. I did not really do this since your code looked too complicated to start with. Instead, I remembered that I had successfully used the following pattern quite often:
var start = ...;
while (start < nums.Count) {
var end = ...;
while (end < nums.Count) {
}
}
With this knowledge I wrote the following code:
public static List<(int from, int to)> Ranges(List<int> nums)
{
nums = nums.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var start = 0;
while (start < nums.Count) {
var end = start + 1; // the range is from [start, end).
while (end < nums.Count && nums[end - 1] + 1 == nums[end]) {
end++;
}
ranges.Add((nums[start], nums[end - 1]));
start = end; // continue after the current range
}
return ranges;
}
This code doesn't need any special cases for the last range, or anything else. A range either stops when the end of the numbers is reached, or when the following number is not consecutive. This sounds sensible, and this is exactly what the code is doing.
I removed the check for nums == null
since it is not necessary. Collections should never be null, and if they are, the code immediately throws an exception, which is fine.
I also removed the special case for nums.Count == 0
since returning an empty list is much better than returning null. Again, expressions that have collection type should never be null. The test cases cover this case, so there's nothing to worry about.
$endgroup$
add a comment |
$begingroup$
Your code is really complicated. First, your code should be abstracted a little more. It is not specific to feature IDs, therefore the terminology should not use these words. The same algorithm can be used to select which pages to print from a document, therefore the variables should be just nums
and ranges
. To test your current code, I wrote:
[Test]
public void TestRanges()
{
Assert.AreEqual("", Str(Ranges(new List<int>())));
Assert.AreEqual("1", Str(Ranges(new List<int> { 1 })));
Assert.AreEqual("1-5", Str(Ranges(new List<int> { 1, 2, 3, 4, 5 })));
Assert.AreEqual("1-3, 5", Str(Ranges(new List<int> { 1, 2, 3, 5 })));
Assert.AreEqual("1, 3, 5-6", Str(Ranges(new List<int> { 1, 3, 5, 6 })));
}
I wrote a helper function Str
so that I don't have to construct a list of ranges for each test case:
public static string Str(List<(int from, int to)> ranges)
{
var parts = new List<string>();
foreach (var range in ranges) {
if (range.from == range.to) {
parts.Add(range.from.ToString());
} else {
parts.Add(range.@from + "-" + range.to);
}
}
return string.Join(", ", parts);
}
After renaming your function to Ranges
, these tests ran successfully. So I was ready to refactor your code. I did not really do this since your code looked too complicated to start with. Instead, I remembered that I had successfully used the following pattern quite often:
var start = ...;
while (start < nums.Count) {
var end = ...;
while (end < nums.Count) {
}
}
With this knowledge I wrote the following code:
public static List<(int from, int to)> Ranges(List<int> nums)
{
nums = nums.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var start = 0;
while (start < nums.Count) {
var end = start + 1; // the range is from [start, end).
while (end < nums.Count && nums[end - 1] + 1 == nums[end]) {
end++;
}
ranges.Add((nums[start], nums[end - 1]));
start = end; // continue after the current range
}
return ranges;
}
This code doesn't need any special cases for the last range, or anything else. A range either stops when the end of the numbers is reached, or when the following number is not consecutive. This sounds sensible, and this is exactly what the code is doing.
I removed the check for nums == null
since it is not necessary. Collections should never be null, and if they are, the code immediately throws an exception, which is fine.
I also removed the special case for nums.Count == 0
since returning an empty list is much better than returning null. Again, expressions that have collection type should never be null. The test cases cover this case, so there's nothing to worry about.
$endgroup$
Your code is really complicated. First, your code should be abstracted a little more. It is not specific to feature IDs, therefore the terminology should not use these words. The same algorithm can be used to select which pages to print from a document, therefore the variables should be just nums
and ranges
. To test your current code, I wrote:
[Test]
public void TestRanges()
{
Assert.AreEqual("", Str(Ranges(new List<int>())));
Assert.AreEqual("1", Str(Ranges(new List<int> { 1 })));
Assert.AreEqual("1-5", Str(Ranges(new List<int> { 1, 2, 3, 4, 5 })));
Assert.AreEqual("1-3, 5", Str(Ranges(new List<int> { 1, 2, 3, 5 })));
Assert.AreEqual("1, 3, 5-6", Str(Ranges(new List<int> { 1, 3, 5, 6 })));
}
I wrote a helper function Str
so that I don't have to construct a list of ranges for each test case:
public static string Str(List<(int from, int to)> ranges)
{
var parts = new List<string>();
foreach (var range in ranges) {
if (range.from == range.to) {
parts.Add(range.from.ToString());
} else {
parts.Add(range.@from + "-" + range.to);
}
}
return string.Join(", ", parts);
}
After renaming your function to Ranges
, these tests ran successfully. So I was ready to refactor your code. I did not really do this since your code looked too complicated to start with. Instead, I remembered that I had successfully used the following pattern quite often:
var start = ...;
while (start < nums.Count) {
var end = ...;
while (end < nums.Count) {
}
}
With this knowledge I wrote the following code:
public static List<(int from, int to)> Ranges(List<int> nums)
{
nums = nums.OrderBy(a => a).Distinct().ToList();
var ranges = new List<(int from, int to)>();
var start = 0;
while (start < nums.Count) {
var end = start + 1; // the range is from [start, end).
while (end < nums.Count && nums[end - 1] + 1 == nums[end]) {
end++;
}
ranges.Add((nums[start], nums[end - 1]));
start = end; // continue after the current range
}
return ranges;
}
This code doesn't need any special cases for the last range, or anything else. A range either stops when the end of the numbers is reached, or when the following number is not consecutive. This sounds sensible, and this is exactly what the code is doing.
I removed the check for nums == null
since it is not necessary. Collections should never be null, and if they are, the code immediately throws an exception, which is fine.
I also removed the special case for nums.Count == 0
since returning an empty list is much better than returning null. Again, expressions that have collection type should never be null. The test cases cover this case, so there's nothing to worry about.
edited 40 mins ago
answered 48 mins ago
Roland IlligRoland Illig
12.2k12050
12.2k12050
add a comment |
add a comment |
Aalawlx is a new contributor. Be nice, and check out our Code of Conduct.
Aalawlx is a new contributor. Be nice, and check out our Code of Conduct.
Aalawlx is a new contributor. Be nice, and check out our Code of Conduct.
Aalawlx is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f219204%2fget-consecutive-integer-number-ranges-from-list-of-int%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
@t3chb0t no I just dislike camel case as I personally find it to be quite difficult to read and thus more likely to cause eye strain. Thanks for your suggestion, I will add it to my question.
$endgroup$
– Aalawlx
6 hours ago
$begingroup$
One more suggestion... if you have any running demo console/unit-test code (which I strongly believe) then you should add it too. It'll make it easier to review your algorithm as people will be able to actually execute it.
$endgroup$
– t3chb0t
5 hours ago
1
$begingroup$
What does
fids
stand for? Would help me understand what your algorithm is doing better ( at least I would hope ).$endgroup$
– Shelby115
5 hours ago
$begingroup$
@Shelby115 actually, your naming makes it more generic, which is good. However, to answer the question, fids means 'features ids'. The reason I am writing this method is to filter criteria-specific feature id numbers from millions of id numbers (integers). The actual use case is machine learning, classification specifically, where millions of features are available, but only a small subset can be used or tested together.
$endgroup$
– Aalawlx
4 hours ago