|
Could someone point me to an algorithm or something that might help me solve this problem:
I have 3 tours going to Disneyland, each of these tours need tickets for the passengers to get into Disneyland. In total I have 60 tickets and they can be distributed in this way: I have 20 tickets to share between Tour1 and Tour2. I have another 20 tickets to share between Tour2 and Tour3. I have another 20 tickets for just Tour3.
Image of ticket allocation to tours[^]
For each person that books a tour, the ticket number is reduced by 1.
I want to maximize the availability that is shown to the user when they are attempting to book any of the 3 tours
With no bookings, the Availability for each tour is:
Tour1: 20
Tour2: 40
Tour3: 40
If we now add bookings for each tour:
Tour1 Bookings: 12
Tour2 Bookings: 10
Tour3 Bookings: 10
The availability when looking at each tour INDIVIDUALLY (aka how many tickets can I book), it should return:
Tour1: 8
Tour2: 18
Tour3: 28
Image[^]
As we increase bookings, availability will be adjusted accordingly. Notice in the next example, when there are an additional 10 bookings for Tour1, Availability for all 3 tours change:
Tour1 Bookings: 18
Tour2 Bookings: 10
Tour3 Bookings: 10
The availability when looking at each tour INDIVIDUALLY (aka how many tickets can I book), it should return:
Tour1: 2
Tour2: 12
Tour3: 22
Image[^]
I'm sure someone has already come up with an algorithm for this... could someone point me in the right direction? Please?
modified 5-Oct-17 10:01am.
|
|
|
|
|
I would do it like this :
Assuming that a Tour has more Information/Content than only the Count :
- you have for each Tour an Array (or better a List) with the availible Tours and one with the booked Tours
- if you book one Tour you move it from the Availible_Tours to the Booked_Tours
- the other way round it you free a Tour
If you only need the Count you can work instead of this only with Integer-Variables.
|
|
|
|
|
You need to go "deeper"; and think "allocation" or "reservation" system.
You need "instances" for each ticket (60); tour (3); and "seats" (20;40;40).
A "booking" links a ticket with a passenger / seat.
Iterating over these "lists" of bookings, seats, tours allows you to know at any time what's what.
Draw a picture; or think of a flight seat reservation you make yourself.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Hi,
Let's say, I have an XML file that looks like this.
<donors>
<donor>
<donorid>1
<name>abc
<amount>$50
<donor>
....
and I have a table that looks like this:
Relation Name
-------------
Donor
Columns
-------
DonorID - bigint
DonorName - nvarchar(100)
DonationCeiling - float
I want to get all of the donor names and amounts from the xml and compare them against the maximum amount allowed. I want to remove all donors from the xml whose donation has exceed the ceiling.
I can do this.
XmlNamespaceManager nsmanager = new XmlNamespaceManager(reader.NameTable);
nsmanager.AddNamespace("donor", "www.mydomain.com/xmlns/donor");
nsmanager.PushScope();
XmlDocument doc = new XmlDocument();
doc.Load("donors.xml");
//Select and display the value of all the ISBN attributes.
XmlNodeList donorIds;
XmlNodeList donationAmount ;
XmlElement root = doc.DocumentElement;
nodeList = root.SelectNodes("/donors/donorid", nsmanager);
Is there a way to retrieve all xml node values from two different xml nodes using one xml path expression into one data structure. For instance, get all donor Ids an donation amount as a key-value list in one data-structure making a single call to root.SelectNodes
Once the donation ids and donations amounts are retrieved, even if they are retrieved as two separate XmlNodeLists, what is the most efficient way to compare these values to the DonationCeiling values returned from the Donor table.
The select query to the Donor table would look like this:
string sql = "Select DonorID, DonationCeiling from Donor where DonorID in ('" + (why can't we just pass the whole XmlNodeList as one data-structure here, without having to loop-through and build the list of DonorId's from the XMLNodeList + "') ;
recordset.ExecuteSQL(sql) ;
After the sql returns the recordset, is there an efficient way to compare the DonationAmounts in the XmlNodeList to the DonationCeiling amounts returned from the Donor table without having two nested loops.
int donorId = Convert.ToInt32(donorIds[0].InnerText) ;
while (!recordset.EOF) {
for (int i=0; i < donorIds.Count;i++) {
if (Convert.ToInt32(donationAmount[i].InnerText) > recordSet.Fields("donationCeiling").Value (should not have to cast to string and then to an integer - the compiler should automatically determine the type based on the returned value from the database column) {
// remove donor node from xml file
}
}
}
Is there a way to do the above without two loops?
Thanks for the time you might spend trying to figure this out. If you can't, that is ok, I have not figured it out so far. Maybe, there is no other way.
Thanks,
Saad
|
|
|
|
|
Upload "both" to "tables" (you admit to at least one) and use SQL.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I've written a 6502 assembler (for Commodore machines) and one of its features is conditional assembly, like this;
ifdef var1
<some code>
else
<some other code>
elseif
So if var1 is defined then <some code=""> is assembled, else <some other="" code="">. However I want to expand this by allowing nested conditional assembly, like this:
ifdef var1
ifdef var2
<some code>
else
<some other code>
endif
else
<yet more code>
endif
Basically the way my assembler works at the moment is if the 'ifdef' condition fails (the variable is not defined) then all of the code following it (until the corresponding 'else' directive) is ignored. It's the 'corresponding else' part which is the problem here. How do I determine which 'else' corresponds with which 'ifdef'? Please note that I can't use the code indentation to determine which 'level' the directives are on. In real life, all of the code will be in the first column (no indentation at all) as my assembler needs directives to be in the first column.
I don't need specific code as such, I'm more interested in an algorithm for this.
In case you're interested, here's my assembler:
www.ajordison.co.uk
modified 28-Sep-17 6:16am.
|
|
|
|
|
The common method for processing such nested commands is using a stack. If you encounter a condition, you push it onto the stack which holds the required information like type (if) and evaluated result. Upon an else, you modify the current stack value accordingly (e.g. by setting an else flag), and upon an endif you pop (discard).
|
|
|
|
|
Yes this is the approach I tried first, but I still had the same problem when I hit an 'else', i.e. which 'else' is it?
|
|
|
|
|
It is the else for the current (top of stack, recent) if.
|
|
|
|
|
|
Hello,
I have a problem with finiding soultion to my product configurator. I'm looking for algorithms that could help me with matching similar datas. The problem is all of entries might be even unique cause they are insert by different people and they are wishes of different clients. Generaly product has option that client can choose from LOV but each option can be replaced by manualy added text. For example one product can have 70 unique values and other 400 and only 5 are values of the same atribute and only 3 are the same values but only 1 is described in exactly the same words. I'm not looking for exact solution, only for tips what algorithms could be helpfull.
Example values from one contract only(they are not describing the same thing, just wanted to show what different type of values I'm talking about):
- 81.0PA KNEITZ Sylby Silbergrau 65726598 / add 5 meter roll to contract
- 411.N015 System cable with a plugin connecting the 19 "box to the printer
One thing i can match values is number before "." cause it places value in group, but there can be multiple entries in one group or there could be none.
So at the end i would need to get 3-5 the most likely similar values to the entered one.
|
|
|
|
|
Garbage in; garbage out.
You need to capture "product / upc" codes; the rest is just "comments".
Mind you, USPS does have a "dangerous goods" keyword list.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
I am working with C# and I have a tab control with several tab pages (tab pages T0, T1, T2, etc). On each tab page there are group boxes ("etched borders"), each with a heading (heading H0, H1, H2, etc). In each group box there are labels (L0, L1, L2, etc). The tab controls, headings, and labels are specified randomly in a table:
T0 H0 L2
T1 H2 L1
T0 H1 L4
T0 H0 L0
T2 H4 L2
T2 H3 L6
I need to sort these like this:
T0 H0 L2
T0 H0 L0
T0 H1 L4
T1 H2 L1
T2 H4 L2
T2 H3 L6
Does anybody know what algorithm I should a look into?
|
|
|
|
|
What is the rule according which they have been ordered?
|
|
|
|
|
The first row in the table dictates what label should be in the first group box in the first tab page. Then, all other labels that belong in same the tab page and group box are added in the order they appear in the original table. When no more labels belong to the first group box in the first tab page, then second group box in the first tab page are added in the order they appear in the original table. Then the third group box is processed, then the fourth, etc until there are no more group boxes in the first tab. Then same algorithm applies same way to the second tab page, then the third tab page, then the fourth, etc.
|
|
|
|
|
That looks to be just a simple sort using the T field as the first key, and the H field as the second. Er, except the last two entries.
|
|
|
|
|
I'm not sure it's particularly efficient, but using LINQ, you can at least get the right answer. 
struct Record
{
public int T { get; set; }
public int H { get; set; }
public int L { get; set; }
}
Record[] UnsortedRecords =
{
new Record { T = 0, H = 0, L = 2 },
new Record { T = 1, H = 2, L = 1 },
new Record { T = 0, H = 1, L = 4 },
new Record { T = 0, H = 0, L = 0 },
new Record { T = 2, H = 4, L = 2 },
new Record { T = 2, H = 3, L = 6 },
};
public static IEnumerable<Record> SortRecords(IEnumerable<Record> source)
{
return source
.GroupBy(r => r.T, (key, items) => items
.GroupBy(r => r.H)
.SelectMany(g => g)
)
.SelectMany(g => g);
}
IEnumerable<Record> SortedRecords = SortRecords(UnsortedRecords);
NB: The documentation for GroupBy states that the order of the input sequence is preserved by both the returned groups, and the items within each group:
The IGrouping<TKey,TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey,TElement>. Elements in a grouping are yielded in the order they appear in source.
You might be tempted to use a composite key in the grouping, to reduce the nesting. But that won't work - T0H1 and T1H2 will be returned in the wrong order:
source.GroupBy(r => new { r.T, r.H }).SelectMany(g => g);
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
This seems to be exactly what I need. Does anybody know how I can implement this in Visual Studio 2005? Or, does anybody know how I can convert my traditional ArrayList into an IEnumerable<record>? The contents of my ArrayList are objects of a class containing about 20 different variables (out of which 3 are strings representing tab page, group box, and label).
|
|
|
|
|
You can use LINQBridge[^] to bring the LINQ methods into C# 2.0, although the syntax is nowhere near as clean:
public static IEnumerable<Record> SortRecords(IEnumerable<Record> source)
{
IEnumerable<IEnumerable<Record>> groupT = Enumerable.GroupBy(source,
delegate(Record r) { return r.T; },
delegate(int key, IEnumerable<Record> items)
{
IEnumerable<IGrouping<int, Record>> groupH = Enumerable.GroupBy(items, delegate(Record r) { return r.H; });
return Enumerable.SelectMany(groupH, delegate(IGrouping<int, Record> g) { return g; });
});
return Enumerable.SelectMany(groupT, delegate(IEnumerable<Record> g) { return g; });
}
You can either replace the ArrayList with a List<T>[^], or use the Cast[^] or OfType[^] methods to convert it to an IEnumerable<T>.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
I get the following compiler error on all lines that contain the word Enumerable:
The type arguments for method 'System.Linq.Enumerable.GroupBy<tsource,tkey>(System.Collections.Generic.IEnumerable<tsource>, System.Func<tsource,tkey>)' cannot be inferred from the usage. Try specifying the type arguments explicitly.
Does anybody know how I can correct this?
|
|
|
|
|
That's annoying. It sounds like C# 2.0 can't infer the generic type parameters properly. You might need to specify them explicitly:
public static IEnumerable<Record> SortRecords(IEnumerable<Record> source)
{
IEnumerable<IEnumerable<Record>> groupT = Enumerable.GroupBy<Record, int, IEnumerable<Record>>(source,
delegate(Record r) { return r.T; },
delegate(int key, IEnumerable<Record> items)
{
IEnumerable<IGrouping<int, Record>> groupH = Enumerable.GroupBy<Record, int>(items, delegate(Record r) { return r.H; });
return Enumerable.SelectMany<IEnumerable<Record>, Record>(groupH, delegate(IEnumerable<Record> g) { return g; });
});
return Enumerable.SelectMany<IEnumerable<Record>, Record>(groupT, delegate(IEnumerable<Record> g) { return g; });
}
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Let's do this the old way!
Sorting on multiple keys with a comparer method is straightforward (and easy to understand?). It is just a nested set of comparisons, compare the first key, if equal compare the second key, etc.
For example let's say we have a list of strings and we want a custom sort.
1) by string length
2) alphabetically within each group of equal length
The comparer method is
private static Int32 SortByLengthThenAlpha(String x, String y) {
Int32 result = x.Length.CompareTo(y.Length);
if (result == 0) {
result = x.CompareTo(y);
}
return result;
}
With an array of strings we can perform the sort with
Array.Sort(strings, SortByLengthThenAlpha);
Original Order
==============
Reddish
Yellowish
Redder
Greenish
Red
Orange
Yellow
Orangy
Green
Sorted
======
Red
Green
Orange
Orangy
Redder
Yellow
Reddish
Greenish
Yellowish
Hope that helps explain the general idea. In your case the keys are the numeric values of T, H and L.
Alan.
|
|
|
|
|
I think my example data was not so good, the following is probably better:
Unsorted:
"City" "Florida" "Miami"
"Animal" "Land" "Dog"
"Animal" "Land" "Rabbit"
"Food" "Dessert" "Chocolate Mousse"
"Food" "Dinner" "Hamburger"
"Animal" "Water" "Fish"
"Animal" "Land" "Cat"
"Food" "Dessert" "Cake"
"Animal" "Air" "Bird"
"Food" "Dessert" "Ice Cream"
"Food" "Dinner" "Steak"
"Animal" "Water" "Sea Lion"
"City" "Texas" "Austin"
"Food" "Breakfast" "Cereal"
"Food" "Breakfast" "Pancakes"
"City" "Florida" "Tampa"
"Animal" "Air" "Fly"
"City" "California" "San Francisco"
"Food" "Breakfast" "Bacon and Eggs"
"City" "Texas" "Dallas"
"City" "Texas" "Houston"
"City" "California" "Los Angeles"
"Animal" "Water" "Dolphin"
"Animal" "Air" "Bee"
"City" "Florida" "Orlando"
"City" "California" "San Diego"
"Food" "Dinner" "Lasagna"
Sorted:
"City" "Florida" "Miami"
"City" "Florida" "Tampa"
"City" "Florida" "Orlando"
"City" "Texas" "Austin"
"City" "Texas" "Dallas"
"City" "Texas" "Houston"
"City" "California" "San Francisco"
"City" "California" "Los Angeles"
"City" "California" "San Diego"
"Animal" "Land" "Dog"
"Animal" "Land" "Rabbit"
"Animal" "Land" "Cat"
"Animal" "Water" "Fish"
"Animal" "Water" "Sea Lion"
"Animal" "Water" "Dolphin"
"Animal" "Air" "Bird"
"Animal" "Air" "Fly"
"Animal" "Air" "Bee"
"Food" "Dessert" "Chocolate Mousse"
"Food" "Dessert" "Cake"
"Food" "Dessert" "Ice Cream"
"Food" "Dinner" "Hamburger"
"Food" "Dinner" "Steak"
"Food" "Dinner" "Lasagna"
"Food" "Breakfast" "Cereal"
"Food" "Breakfast" "Bacon and Eggs"
"Food" "Breakfast" "Pancakes"
How would I then use your code to sort it?
|
|
|
|
|
The problem you have is that the desired arrangement within the 3 columns has no discernable order. You are grouping terms, City, California, Water, Breakfast etc, but the order of the groups seems completely random. For example why is the order of the states Florida, Texas, California? There is nothing about the strings which would suggest that order so there must be some other factor which is not in the data that you have shown.
Alan.
|
|
|
|
|
First, pretend only column 1 (tab page string) and column 2 (groupbox string) are present and then simply remove all duplicate rows. This is the sorted order for columns 1 and 2. Now, insert column 3 items in the groupbox where they belong and preserve the unsorted order within each groupbox.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
