Find an algorithm

Not Active

I've probably been staring at this far too long but I can't find an algorithm that will return the correct results for the code below. Anyone have some fresh ideas?

private void Test()
{
Logic(false, false, false, false, false, false, false);
Logic(false, false, false, false, true, true, true);
Logic(false, false, false, false, true, false, false);
Logic(false, false, true, false, true, true, false);
Logic(false, false, true, true, true, true, true);
}

private void Logic(bool f, bool fl, bool d, bool dl, bool r, bool rl, bool expected)
{
bool result = [What algorithm goes here];

System.Diagnostics.Debug.Assert(result == expected, "Does not match expected results");

}

I know the language. I've read a book. - _Madmatt

Luc Pattyn

Mark Nischalke wrote:

bool result = [What algorithm goes here];

I can not possibly tell you what the name is of what you want. What do you want? What fits there is a logic expression, probably one involving the object's state (no "static") and/or the input parameters. BTW: it looks like a function, but doesn't return anything. A more natural set-up would be:

private void TestAll()
{
Test(false, false, false, false, false, false, false);
Test(false, false, false, false, true, true, true);
Test(false, false, false, false, true, false, false);
Test(false, false, true, false, true, true, false);
Test(false, false, true, true, true, true, true);
}

private bool Test(bool f, bool fl, bool d, bool dl, bool r, bool rl, bool expected)
{
bool result=Logic(bool f, bool fl, bool d, bool dl, bool r, bool rl);
bool OK=result==expected;
System.Diagnostics.Debug.Assert(OK, "Test failed: "+f+f1+d+d1+r+r1+result+expected);
return OK;
}

private bool Logic(bool f, bool fl, bool d, bool dl, bool r, bool rl, bool expected)
{
bool result = ???;
return result;
}

Assuming you meant a static function, one possible expression fitting the test vectors is:

bool mf = f==f1;
bool md = d==d1;
bool mr = r==r1;
bool result=mf && md && mr && (f||d||r);

but there are many more. In fact, your Logic function seems to have 64 different input combinations, each leading to some result, and only 5 test vectors have been defined, so 59 cases are undefined. If no (easy) expression is available, you can always implement a table look-up. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

Lost User

I'll need a complete truth table, unless all other entries are "don't care" (which I'll assume for now) How about r && rl && (dl == d) ? I know it may seem lame, but it fits your specifications.. edit: lameness fixed. I just woke up..

Not Active

Thanks, works perfectly. As I said I was starting at problem too long. Can't see the forest for the trees.

I know the language. I've read a book. - _Madmatt

Lost User

You're welcome :)

lepipele

Try: bool result = expected; :-D

User 4187421

Hi Mark, there's this Karnaugh logic maps, which are actually the normal way you'll solve such problems cheerz nas

R Erasmus

Hi Try out this algorithm: (done in C)

bool result = (((f == fl) && (d == dl) && (r == rl)) && ((f == true) || (d == true) || (r == true)))

Could be simplified, but that is what it boils down to. Regards,

R. Erasmus

modified on Wednesday, November 17, 2010 1:56 AM

Luc Pattyn · modified on Wednesday, November 17, 2010 1:56 AM

Right. That was already provided in the first reply yesterday. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

Not Active

Really? :rolleyes: And to think I spent hours wasting my time doing it with a stone and chisel :rolleyes:

I know the language. I've read a book. - _Madmatt

Not Active

I know I didn't supply all of the possible cases (too much typing and I'm a lazy developer :) ) It turned out to be a little simpler after I realized the variables are paired. For instance, if f == false then fl must also be false, same for d and dl, and r and rl.

I know the language. I've read a book. - _Madmatt

Luc Pattyn

IMO Karnaugh maps aren't very useful. They can't cope with medium or large problems (how many times have you drawn Karnaugh maps with 6 input variables?) and they aren't very useful at solving small problems, as you just don't need them. The one thing they do well is visualize how minterms can be formed, but once you saw the principle, you don't need a graphics tool any more. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

grgran

If it were me I'd ask a lot more questions of whoever gave you this. The first two inputs to Logic appear to have no effect on the result and (if that's true) should be removed. This leaves a four bit table mapping: false, false, false, false, false false, false, true, true, true false, false, true, false, false true, false, true, true, false true, true, true, true, true Which can also be looked at as a bit table d dl r rl Exp Dec 0 0 0 0 0 00 * 0 0 0 1 ? 01 0 0 1 0 0 02 * 0 0 1 1 1 03 * 0 1 0 0 ? 04 0 1 0 1 ? 05 0 1 1 0 ? 06 0 1 1 1 ? 07 1 0 0 0 ? 08 1 0 0 1 ? 09 1 0 1 0 ? 10 1 0 1 1 0 11 * 1 1 0 0 ? 12 1 1 0 1 ? 13 1 1 1 0 ? 14 1 1 1 1 1 15 * There doesn't appear to be an obvious pattern, but there are lots of unknowns. I'd be tempted to change Logic to remove the first two parameters and return a bool? (nullable). I'd then convert d, dl, r and rl into a single byte value and use a switch statement to return the known results, returning null for undefined results. If a pattern later emerges you can do something 'pretty' then.

Luc Pattyn

why do conversions, why introduce decision statements, if all it takes is some simple boolean expression? would you also replace multiplications by loops containing an addition? :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

parth p

Luc Pattyn wrote:

Karnaugh maps aren't very useful

That's why you have Quine–McCluskey algorithm. You can easily implement it in any language and it always works regardless of number of inputs.

- Stop thinking in terms of limitations and start thinking in terms of possibilities -

grgran

Simple because with all the unknowns, 30 secs after the method is finished some "new" result will be expected. Boolean expression are fine when what you are trying to communicate is clear. In this case things don't appear to be 'clear'. Converting isn't necessary, it's just helpful. Cheers

Luc Pattyn

parth.p wrote:

That's why you have Quine–McCluskey algorithm

and more. Pichat's work was more interesting (seems absent on the web??). I did a lot of research on the subject, and came up with my own optimization and design language, even before Verilog and VHDL became popular. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

frank33

have you tried a Karnaugh map?

Frank

Not Active

It seemed to be clear to everyone else

I know the language. I've read a book. - _Madmatt

Not Active

You mean like Member 4190501 suggested over 10 hours ago. If you also read the responses you would see the problem was solved long ago.

I know the language. I've read a book. - _Madmatt