|
It depends on how you're (internally) representing the values.
If you're using regular .NET integer types (e.g., Int32, Int64) then just compare the values.
If you're using strings to represent the values, then
1. if necessary, pad the strings to the same length (leading spaces or zeros)
2. use a case-INsensitive string comparison.
The string representation is a very poor design for something like this!
A positive attitude may not solve every problem, but it will annoy enough people to be worth the effort.
|
|
|
|
|
My bad, I elided some details....
The values are part of numbering sequences for ticket books. Say I have a book with a number range of '9ER78Y' to 9ER79J', stored as strings ('start and 'end') (not my design, it was inherited). Now I am given a ticket number of '9ER79A' I need to find the book of tickets that contains this ticket.
The only way I can see to do it is a brute force table scan, of over 500,000 books 
I am not sure an index would help, unless I added a discriminator column to represent the book start and end range
|
|
|
|
|
Do you need to do this within a DB query (SQL), or is the "search" in-memory?
Are there any other constraints on the problem space that might be used to simplify things?
(E.g., are the ranges all exactly the same size? or a multiple of some size?)
If you need to do significant numbers of checking at a time, then some pre-processing of the data while loading into memory is a good tradeoff.
If these are one-off checks against the DB, then pre-processing is probably not worth it.
A positive attitude may not solve every problem, but it will annoy enough people to be worth the effort.
|
|
|
|
|
You can implement this with a form of binary search.
- [Preparation] Sort the strings representing the first ticket in each book in ascending order:
a. zero-pad any short strings (e.g. "ABC1" should be padded to "00ABC1"
b. sort the strings using a case-insensitive sort
c. pad the list with a dummy ending value (e.g. "ZZZZZZ").
d. pad the list with a dummy starting value (e.g. "000000"). - [Eliminate low values] Use a binary search to find the location of largest value less than or equal to the target string. If the result points to the starting dummy value, then no such value exists.
- [Eliminate high values] Use a binary search to find the location of the smallest value larger than the target string. If the result points to the ending dummy value, then no such value exists.
The range [low, high) contains your result. If low != high, the range should contain a single element that is the desired ticket book. If low == high, no ticket book was found.
Note that you can handle missing books in the sequence by adding dummy book starting values to the array.
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
C# (sorry; I don't do "VB")...
IsInBetween( "A0ZWS0A" );
IsInBetween( "A0ZWS0P" );
IsInBetween( "A0ZWS7P" );
IsInBetween( "A0ZWSAP" );
private static void IsInBetween( string value ) {
string s1 = "A0ZWS0P";
string s2 = "A0ZWS9P";
bool isInbetween =
value.CompareTo( s1 ) == 0 ||
value.CompareTo( s2 ) == 0 ||
( value.CompareTo( s1 ) > 0 && value.CompareTo( s2 ) < 0 );
Console.WriteLine( "Is {0} between {1} {2}? {3}", value, s1, s2, isInbetween );
}
|
|
|
|
|
I will try this....I also am a C# guy, for the last 10 years or so, but the job specced VB so, learn it I did 
|
|
|
|
|
Good for you ... I've been able to avoid VB.NET thus far (though I did dabble in it back when it was called "Visual Basic 1.0").
|
|
|
|
|
And why not use >= and <= operators.
It gives something like:
bool isInbetween = ( value.CompareTo( s1 ) >= 0 && value.CompareTo( s2 ) <= 0 );
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
A base 36 numbering scheme should be the math rappresentation of a normal numer expressed with 36 different ciphers. 
It should be quite an easy task to create a function that converts the strings that you have to plain binary numbers (base 2) understandable to the computer. This function is equivalent to an ascii to bin conversion, only the symbols that have top be handled are 36.
The sequence, I suppose, is: 0 1 2 3 4 5 6 7 8 9 A B C D E F G . . . . . Z
The generic rappresentation of a number expressed in base x is:
Vn*X^n + V(n-1)*X^n-1 + V(n-2)*X^n-2 + ... + V(0)
In plain the sum of all ciphers by the power of the base at the position taken as exponent.
This is sample to convert a base 36 number to a base 2 numberEDIT: This sample converts any ascii rappresentation of a number in all bases between 2 and 36. It acts as the standard atoi, atol, etc. It converts all applicable characters up to the end of string or the first non number with respect to the choosed base. If the first string char is not a valid cipher, or the string is empty it returns NULL.
long long GenRadVal(char *str, int base)
{
if (base<2 || base>36)
return 0LL;
long long val = 0;
for (int i = 0; str[i]; i++)
{
int c = toupper(str[i]);
if ((c < 0) || ((c > '9') && (c < 'A')) || (c > 'Z'))
break;
c = c > '9' ? c - 'A' + 10 : c - '0';
if (c >= base)
break;
val *= base;
val += c;
}
return val;
}
This will give you back a 64 bits number equivalent to the string. To go back to the original value you can use itoa() function in C.
Now comparisons are easy.. 
P.S. the reverse for this function is the stdlib function itoa() with base=36.
modified 17-May-15 12:01pm.
|
|
|
|
|
This will not do a parse of the string as Base 36!
It is treating the 'digits' as in reverse order.
I.e., the right-most digit corresponds to the highest power of 36.
The representation of non-overlapping ranges (see other comments above) will not survive this "parse".
Here's one in C#:
static long Parse36(string s)
{
long v = 0;
foreach(char c in s)
{
char uc = char.ToUpper(c);
bool isDigit = ('0' <= uc && uc <= '9');
if (!(isDigit || ('A' <= uc && uc <= 'Z')))
throw new FormatException();
int d = uc - (isDigit ? '0' : ('A' - 10));
v = v * 36 + d;
}
return v;
}
(It can be simplified a bit if you can guarantee the strings contain only 0-9, A-Z uppercase.)
A positive attitude may not solve every problem, but it will annoy enough people to be worth the effort.
|
|
|
|
|
Thanks Matt, I put it up too fast.
I corrected it with a version that acts like standard libc conversion routines, and can be used for any base.
|
|
|
|
|
I would simply pad the 3 strings on left with '0's so that all values have same length.
After that, it is a simply string comparison problem.
From other answers, I see that you have 500000 books
I guess you have a database, and that books contain consecutive numbers
- make sure all first ticket number of books have the same length by padding 'o' on left.
- make this field an index
- search the base to find the first book with number <= random
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
What? Unclear, and probably not related to algorithms.
|
|
|
|
|
By magic. If you want more detailed answers, please post more specific questions.
|
|
|
|
|
In pseudocode, the general C4.5 algorithm for building decision trees is:
1. Check for base cases
2. For each attribute a
2.1. Find the normalized information gain ratio from splitting on a
3. Let a_best be the attribute with the highest normalized information gain
4. Create a decision node that splits on a_best
5. Recur on the sublists obtained by splitting on a_best, and add those nodes as children of node
|
|
|
|
|
|
Please read: How-to-get-an-answer-to-your-question[^]
As I have a feeling you won't actually do it, here's the important part:
Quote: Be specific! Don't ask "can someone send me the code to create an application that does 'X'.
Have you heard about Google?
And please stop posting the same question again.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
|
|
|
|
|
Can someone explain this question please
There are 2 types of tiles: Type 1: ** * Type 2: ** (where each star is a square block) Each tile can be rotated or flipped in all ways. There is a box with 2-by-n dimensions. So, for example, if n=10 then the box dimensions are 2 X 10 as shown below. ****** ****** You have infinite supplies of Type 1 and Type 2 tiles. You have to cover the box with the tiles that you have. You can use any number of type 1 tiles and type 2 tiles. You can choose to use all tiles of same type and none tiles of the other type. But you cannot overlap the tiles. Also, when you cover the box with tiles, none of the tiles should be out of the boundaries of the box, and no part of the box should be empty (no block shud be empty). The tiles should perfectly cover the box with no holes and no protrusions. Your task is to write a program in python that will count the number of different ways (configurations) in which u can cover the box with tiles. 2 cofigurations of covering a box are different if the type or orientation (or both) of any tile of those 2 configurations are different. To clarify things further, there are following configurations of the tiles: 1) ** 2) * * 3) ** * 4) ** * 5) * ** 6) * ** If there are 2 tiles in the configuration that are of same type and placed in same orientation, then if you swap the positions of these 2 tiles, it WILL NOT be counted as a different configuration because all tiles of same type and same orientation are identical. Write a program that will accept an input, n, and produce an output, the total number of different configurations to cover the box of dimensions 2 X n. Example: If n=2, output should be 2. Because 1 configuration could be 2 type-1 tiles placed vertically, and another configuration could be 2 type-1 tiles placed horizontally. If n=3, output should be 5
|
|
|
|
|
That's a task, not a question. And your post is not a question that fits the purpose of this forum. You didn't ask for an explanation of a specific part of this task, so do you want the whole thing explained in even more words than it already consists of?
I suggest you try a bit harder understanding it and, if needed, come back with a more specific question.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
|
|
|
|
|
It would help if you fixed the formatting, but I get the general idea.
Unsurprisingly, it's a tiling problem. There is a rectangle that you have to fill with these shapes, filling it perfectly. Then you have to count in how many distinct ways that can be done, with "distinct" meaning exactly what you'd expect (but they spell it out for good measure).
|
|
|
|
|
Research bin-packing and knapsack algorithms.
And we won't do your homework for you.
|
|
|
|
|
Hi,
I have the following problem:
Lets say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every person can move x corrdinates per second.
Every task has:
- A coordinate where it can be completed (for example (40/50))
- A importance value ranging from 0 - X (for example importance = 5)
- A time that is needed to complete this task
Also, some tasks can only be done if others are already completed.
Now comes the tricky thing: The group has a certain time, in which they can complete tasks. They now need to choose which tasks they want to complete, the goal is that the summarized "importance value" of the completed tasks is as high as possible. The group is also allowed to split up.
I tried to solve the problem in the past hours but i haven't come far and i'm burnt out. Please help 
|
|
|
|
|
|
Hi,
Your problem is hard to solve as data grow. The general family is Graph.
It is related to classical problems:
- TSP Travelling salesman problem, if only one guy.
- Delivery round, it is a daily problem for every UPS agency.
It may not be your specific problem, but it is the same area/family.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I have an array of several segments of a path with known start / end point. Direction of each segment is not known. It can be from start to end point or vice versa.
Each segment object is something like this:
Connection: {
PointA = p1
PointB = p2
pointA_is_connected = true (false for the first or last segment)
pointB_is_connected = true (false for the first or last segment)
}
I want to create a path from one end to another in one direction with all segments that can be connected to each other. All the segments in an array are segments of a ONE path.
Here is an image of what I have (in red) and what I want to have (in green)
What's the best way to achieve this?
http://pgtehran.euphrat.es/pic.png[^]
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
