algorithm head scratcher 
Author Message
 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  
 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  
 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  
 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  
 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  
 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  
 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  
 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  
 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  
 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  
 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  
 
 [ 11 post ] 

 Relevant Pages 

1. [VB/Word Problem - This is a real head-scratcher]

2. Head-Scratcher: Plain Program Requires DLLs and OCXs?

3. Head scratcher!

4. Weird Text Box "Head Scratcher"

5. sendkeys. here is a head scratcher

6. C & BASIC head to head etc

7. way over my head here

8. Access 97 Column Head Click

9. Bone Head syndrome

10. allow me to be the head ass

11. How to set column heads in ActiveX Listbox

12. Number Search and Heading Style Search Questions

 

 
Powered by phpBB® Forum Software