Author |
Message |
MP #1 / 11
|
algorithm head scratcher
This seems like it should have a simple and elegant solution. I won't admit how long I've been struggling with it :-) I have code that works "to some extent some of the time" <g> but is horribly long and ugly and convoluted and therefore hard to modify I have a sneaking suspicion there'd be a real simple way to do this oversimplified example of the problem: given a list of strings each string represents a "code" or "descriptor" each code has two elements each element has 4 possible values: N L R or B (none, Left, Right, Both) the list is presorted in a defined order before being sent to the algorithm in question so the following combinations are possible (presorted in a defined order) (oversimplifying by looking at only the two "middle conditions" of the first element <L and R>) LN LL LR LB RN RL RR RB assuming the above is my input list, I want to increment a counter and assign each descriptor a number however if an element = R and a corresponding previous element was = L, then this descriptor doesn't increment the counter, I go back and get the previous number(from it's opposite counterpart) and add "oppsuffix" for opposite hand... clear as mud? :-) for example: the result for a complete list (one containing all possible combinations but no duplicates) would be: LN =1 LL =2 LR =3 LB =4 RN =1OPP ....(RN is opposite of LN) RL =3OPP ....(RL is opposite of LR) RR =2OPP ...(RR is opposite of LL) RB =4OPP ...(RB is opposite of LB) however, maybe there's not a L corresponding to a given R...in which case it's not opposite to anything and therefore increments the counter...for example: LL =1 LR =2 LB =3 RN =4 ..........(no LN to be opposite to) RL =2OPP....(RL is opposite of LR) RR =1OPP ...(RR is opposite of LL) RB =3OPP ...(RB is opposite of LB) the list can(will) contain duplicates, in which case the counter doesn't increment, the number is assigned to all matching items and further more some combinations might be "invalid" so, for example I might define "LR and RL" as "invalid" under certain conditions currently I'm trying things like: ...assume the two elements are contained in variables sFirst and sSecond for first and second elements of the "descriptor" For Each Descriptor in List (actually a loop through a recordset) 'Get sFirst and sSecond (fldFirst, fldSecond) 'if invalid then mark as such and loop to next descriptor 'if same as last one then apply current counter and loop to next descriptor 'if it's different than the last one then apply further tests 'if it's a left hand variety enter into dictionary for opp test 'check against dictionary for opp hand 'if not opp hand then increment Next Descriptor 'the check to increment or not is based on embedded select cases (two levels) Select Case sFirst Case N 'check for opp and SelectCase second Case L 'enter into list of lefts 'check for opp and SelectCase second Case R 'check for opp and SelectCase second Case B 'check for opp and SelectCase second End Select inside each case above theres' a second SelectCase Select Case sSecond Case N 'check for opp or increment counter Case L 'enter into list of lefts 'check for opp or increment counter Case R 'check for opp or increment counter Case B 'check for opp or increment counter End Select like I said...horribly long and ugly :-) especially since this whole LR check is inside each case of another SelectCase of 1-8 "upper level options" where each 1 - 8 may assign different IsInvalid() tests for various LR combinations For Each Descriptor in List SelectCase 1-8 Case 1 'define valid combos SelectCase NLRB1 SelectCase NLRB2 Case 2 'define valid combos SelectCase NLRB1 SelectCase NLRB2 Case .... Next :-) any inspirations? mark
|
Tue, 28 Dec 2010 04:52:36 GMT |
|
|
dpb #2 / 11
|
algorithm head scratcher
Quote:
> This seems like it should have a simple and elegant solution. ... > oversimplified example of the problem:
Observation: Oversimplification of the problem is highly unlikely to lead to a solution to the real problem... Quote: > given a list of strings > each string represents a "code" or "descriptor" > each code has two elements > each element has 4 possible values: N L R or B (none, Left, Right, Both) > the list is presorted in a defined order before being sent to the algorithm > in question ... > assuming the above is my input list, I want to increment a counter and > assign each descriptor a number > however if an element = R and a corresponding previous element was = L, then > this descriptor doesn't increment the counter, I go back and get the > previous number(from it's opposite counterpart) and add "oppsuffix" for > opposite hand... > clear as mud? :-)
Absolutely...I have no clue what the above is intended to describe as the problem statement. Quote: > for example: > the result for a complete list (one containing all possible combinations but > no duplicates) would be: > LN =1 > LL =2 > LR =3 > LB =4 > RN =1OPP ....(RN is opposite of LN) > RL =3OPP ....(RL is opposite of LR)
Why isn't it the opposite of LL???? Seems like you switched from comparing first position to both in midstream... Quote: > RR =2OPP ...(RR is opposite of LL)
ditto in reverse... Quote: > RB =4OPP ...(RB is opposite of LB)
... My initial reaction is the problem statement needs more work to unequivocally define the rules before asking somebody else to attack it. My other reaction is that it sounds like "lookup table" or "state machine" but that's w/ only a very cursory guess at what the problem really is. --
|
Tue, 28 Dec 2010 06:17:33 GMT |
|
|
Larry Serflate #3 / 11
|
algorithm head scratcher
Quote: > This seems like it should have a simple and elegant solution. > I won't admit how long I've been struggling with it :-) > I have code that works "to some extent some of the time" <g> but is horribly > long and ugly and convoluted and therefore hard to modify > I have a sneaking suspicion there'd be a real simple way to do this
Generally the first step to solving a problem, is to actually understand the problem. If you can't describe it 'clearer than mud', then its certainly going to be difficult to understand. Quote: > oversimplified example of the problem: > given a list of strings > each string represents a "code" or "descriptor" > each code has two elements > each element has 4 possible values: N L R or B (none, Left, Right, Both) > the list is presorted in a defined order before being sent to the algorithm > in question
After that, you go on to say you want to increment a counter based on certain factors, which may change. From a 'birds eye view', I'd suggest you see if your algorithm will support lookup tables to determine if the counter is incremented or not. Each element has 4 states: N, L, R, B; consider how those states can be represented in a binary form: N = 00 L = 01 R = 10 B = 11 Each code has two elements, so to represent any possible combination of the two elements, you'd need a 4 bit value: NN = 0000 NL = 0001 NR = 0010 NB = 0011 LN = 0100 LL = 0101 LR = 0110 ... BB = 1111 The total number of permuations for those two elements is 16 different states. You can then use a 16 element array to indicate if your counter should be incremented, for example: inc = Array(0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0) Then you can build a translating Collection object to quickly translate those 2 character strings to array index values: trans.Add 0, "NN" trans.Add 1, "NL" trans.Add 2, "NR" trans.Add 3, "NB" trans.Add 4, "LN" ... trans.Add 15, "BB" so then given a string like "LR" you can adjust your counter from the array: cnt = cnt + inc(trans("LR")) And given your need to change the factors you can reassign the array as needed: Select Case Need Case 1 inc = Array(1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0) Case 2 inc = Array(0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1) ... Case 8 inc = Array(1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0) End Select That may or may not be the exact solution you need, but perhaps it is illuminating a more concise approach to your problem. HTH LFS
|
Tue, 28 Dec 2010 06:18:17 GMT |
|
|
MP #4 / 11
|
algorithm head scratcher
Quote:
>> This seems like it should have a simple and elegant solution. snip > That may or may not be the exact solution you need, but > perhaps it is illuminating a more concise approach to your problem. > HTH > LFS
Thanks Larry and dbp I will look into lookup tables Sounds like a good possibility Mark
|
Tue, 28 Dec 2010 09:31:26 GMT |
|
|
MP #5 / 11
|
algorithm head scratcher
Quote:
>> This seems like it should have a simple and elegant solution. > ... >> oversimplified example of the problem: > Observation: Oversimplification of the problem is highly unlikely to lead > to a solution to the real problem...
well, maybe oversimplifcation was the wrong term it is an exact description of what I have to do, although it's in the context of a larger bit of work, parts of which I already have a solution to. So even though I have actually 6 fields to read, sort, assign number to, and write back to db, I'm only talking about the 2 fields that are pertinent to this question of opposite hands. >> assuming the above is my input list, I want to increment a counter and Quote: >> assign each descriptor a number >> however if an element = R and a corresponding previous element was = L, >> then this descriptor doesn't increment the counter, I go back and get the >> previous number(from it's opposite counterpart) and add "oppsuffix" for >> opposite hand... >> clear as mud? :-) > Absolutely...I have no clue what the above is intended to describe as the > problem statement.
sorry, although the words are a correct and exact statement of what i have to do, I understand they're hard to understand, cause it is kind of a confusing "sorting issue" (that's why I followed it with an example showing the required results given the supplied input) Quote: >> for example: >> the result for a complete list (one containing all possible combinations >> but no duplicates) would be: >> LN =1 >> LL =2 >> LR =3 >> LB =4 >> RN =1OPP ....(RN is opposite of LN) >> RL =3OPP ....(RL is opposite of LR) > Why isn't it the opposite of LL????
because the second L is the same, not opposite MirrorImage would have been a better term to use so RL is MirrorImage of LR but RL is only different from LL, not MirrorImage of LL Seems like you switched from Quote: > comparing first position to both in midstream...
it only seems that way, in fact I compare both in all cases LN is Opp to RN because L is opp to R and N has no Opp, so they are in fact mirror images likewise with B, which also has no opposite LB is Opp to RB because L is opp to R and B has no Opp, so they are in fact mirror images Quote: > My initial reaction is the problem statement needs more work to > unequivocally define the rules before asking somebody else to attack it.
I defined the rules by providing the chart of all possible combinations and their respective "opposites" I thought the inclusive example would be clearer than trying to describe it in words.... as usual it didn't work. :-) Quote: > My other reaction is that it sounds like "lookup table" or "state machine" > but that's w/ only a very cursory guess at what the problem really is.
lookup tables sound like a possibility if I can find how to implement them in google searches so far all i've found is "Lookup table " in databases at first I thought it was some kind of vb implementation but msdn hasn't shed any light on "lookup" in any way I can seem to apply yet. I wasn't sure if you and Larry were suggesting a database lookup table... my input data is coming from a database so I could add some kind of table if needed, if I can figure out how you two are suggesting I use them... so far my overview "pseudo code" is For each vEntry in List If IsAlreadyOnList(vEntry) Then 'nothing to do ElseIf IsMirrorImageOnList(vEntry) Then 'get "counter" from MirrorImage and enter into list as opp hand(mirror image) ElseIf IsOppHandButDifferentLengthOnList(vEntry) Then 'bump counter and enter in list as opp Else 'bump counter and enter in list End if Next it still seems like I need to store a 'running list' (of encountered values) of some kind to compare each new entry back to so far i don't understand how to use a lookup table to do that comparison for me. it also may be that I could do this in sql if I could figure out the right query syntax since the original data is gotten from a recordset and the final result written back to the table in an update statement. mark
|
Sat, 01 Jan 2011 02:26:24 GMT |
|
|
MP #6 / 11
|
algorithm head scratcher
Quote:
> Generally the first step to solving a problem, is to actually understand > the problem. If you can't describe it 'clearer than mud', then its > certainly > going to be difficult to understand.
well, I think it's a verbally accurate description of the problem and is clear to me since I'm acquainted with it, but I assume it's hard to understand on first reading when distilled down to a succinct form for the sake of brevity in posting. :-) Quote: >> oversimplified example of the problem: >> given a list of strings >> each string represents a "code" or "descriptor" >> each code has two elements >> each element has 4 possible values: N L R or B (none, Left, Right, Both) >> the list is presorted in a defined order before being sent to the >> algorithm >> in question > After that, you go on to say you want to increment a counter based > on certain factors, which may change.
the counter either increments or not depending on whether this entry has been encountered already or if it's mirror image has been encountered (in this "batch"), or if it's a new sequence (new NLRB or new length) thus, from the op: "however if an element = R and a corresponding previous element was = L, then this descriptor doesn't increment the counter, I go back and get the previous number(from it's opposite counterpart) " depending on certain other conditions(the upper level select case in which this inner select appears) some combinations of NLRB may be nonsensical and therefore "invalid" so there could be a lookup table to define "invalid combinations" and that could change with each upper level select case. the idea of your inc = Array( ) could possibly be useful for testing which combinations are valid IsInvalid = Array(0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0) but whether to increment or not is dependent on preceeding entries so I still think I need a temp storage collection to refer back to as each entry is processed (ps one of the fields i didn't mention in the simplified op question was "length") so far i think my overview "pseudo code" should be something like: For each vEntry in List If IsValid(vEntry) Then If IsAlreadyOnList(vEntry) Then 'nothing to do ElseIf IsMirrorImageOnList(vEntry) Then '(opp hand and same length...exact mirror image) 'get "counter" from MirrorImage and enter into list as opp hand(mirror image) ElseIf IsOppHandButDifferentLengthOnList(vEntry) Then '(opp hand but different length) 'bump counter and enter in list as opp Else 'bump counter and enter in list End if'on list End if 'valid Next Quote: > From a 'birds eye view', I'd suggest you see if your algorithm will > support lookup tables to determine if the counter is incremented > or not. > Each element has 4 states: N, L, R, B; consider how those states > can be represented in a binary form: > N = 00 > L = 01 > R = 10 > B = 11 > Each code has two elements, so to represent any possible combination > of the two elements, you'd need a 4 bit value: > NN = 0000 > NL = 0001 > NR = 0010 > NB = 0011 > LN = 0100 > LL = 0101 > LR = 0110 > ... > BB = 1111 > The total number of permuations for those two elements is 16 different > states. You can then use a 16 element array to indicate if your counter > should be incremented, for example: > inc = Array(0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0) > Then you can build a translating Collection object to quickly translate > those 2 character strings to array index values: > trans.Add 0, "NN" > trans.Add 1, "NL" > trans.Add 2, "NR" > trans.Add 3, "NB" > trans.Add 4, "LN" > ... > trans.Add 15, "BB" > so then given a string like "LR" you can adjust your counter from the > array: > cnt = cnt + inc(trans("LR")) > And given your need to change the factors you can reassign the array as > needed: > Select Case Need > Case 1 > inc = Array(1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0) > Case 2 > inc = Array(0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1) > ... > Case 8 > inc = Array(1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0) > End Select > That may or may not be the exact solution you need, but > perhaps it is illuminating a more concise approach to your problem. > HTH > LFS
|
Sat, 01 Jan 2011 03:48:41 GMT |
|
|
dpb #7 / 11
|
algorithm head scratcher
... Quote: > but whether to increment or not is dependent on preceeding entries so > I still think I need a temp storage collection to refer back to as > each entry is processed ...
Think state machine. Quote: > (ps one of the fields i didn't mention in the >> simplified op question was "length")...
Which was one of my complaints before and you blew me off, remember??? Thanks, but no thanks, I'm not spending time on another moving target post... :( --
|
Sat, 01 Jan 2011 05:36:55 GMT |
|
|
MP #8 / 11
|
algorithm head scratcher
Quote:
> ... >> but whether to increment or not is dependent on preceeding entries so >> I still think I need a temp storage collection to refer back to as >> each entry is processed ... > Think state machine.
no clue what that is but sounds very interesting, will google, thanks ps one of the fields i didn't mention in the Quote: >>> simplified op question was "length")... > Which was one of my complaints before and you blew me off, remember???
Ouch! I didn't blow you off...I was just trying to explain that I thought i was "focusing" the question on a certain area... Quote: > Thanks, but no thanks, I'm not spending time on another moving target > post... :(
sorry, my loss
|
Sat, 01 Jan 2011 06:00:51 GMT |
|
|
dpb #9 / 11
|
algorithm head scratcher
... Quote: > Ouch! I didn't blow you off...I was just trying to explain that I thought i > was "focusing" the question on a certain area...
... And I (as well as was Larry totally independently) was trying to explain that unless you can write a succinct and comprehensible problem statement that encompasses the entire problem domain your chances of solving it in an coherent fashion are pretty much nil. Even if you do manage to get a solution to a subset, it's highly likely even from what you have described so far that the next set of conditions will break that solution leaving you to, essentially, start over again. I am still confident that while you may believe you understand the problem, you have not spent enough time trying to formalize the statement of the problem into a set of rules that can be applied and that when you do this, you will then be on your way to the solution. A state machine in simplistic terms is simply an enumeration of the possibilities and the allowable transitions from one state to the next. In multiple choice nested situations such as this, creating that set of states and transitions can be the key. You started with the 2-character subset, add to it the other conditions. --
|
Sat, 01 Jan 2011 06:23:01 GMT |
|
|
dpb #10 / 11
|
algorithm head scratcher
... Quote: > A state machine ...
And, you may still find it useful to use the lookup table as part of a state machine...they're not necessarily either/or. --
|
Sat, 01 Jan 2011 06:29:30 GMT |
|
|
MP #11 / 11
|
algorithm head scratcher
Quote:
> ... >> Ouch! I didn't blow you off...I was just trying to explain that I >> thought i was "focusing" the question on a certain area... > ... > And I (as well as was Larry totally independently) was trying to explain > that unless you can write a succinct and comprehensible problem statement > that encompasses the entire problem domain your chances of solving it in > an coherent fashion are pretty much nil. > Even if you do manage to get a solution to a subset, it's highly likely > even from what you have described so far that the next set of conditions > will break that solution leaving you to, essentially, start over again. > I am still confident that while you may believe you understand the > problem, you have not spent enough time trying to formalize the statement > of the problem into a set of rules that can be applied and that when you > do this, you will then be on your way to the solution. > A state machine in simplistic terms is simply an enumeration of the > possibilities and the allowable transitions from one state to the next. In > multiple choice nested situations such as this, creating that set of > states and transitions can be the key. You started with the 2-character > subset, add to it the other conditions. > --
Thanks working on it. :-) mark
|
Sat, 01 Jan 2011 06:55:07 GMT |
|
|
|