Find an algorithm
-
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
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.
-
Hi Mark, there's this Karnaugh logic maps, which are actually the normal way you'll solve such problems cheerz nas
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
-
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.
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
-
Hi Mark, there's this Karnaugh logic maps, which are actually the normal way you'll solve such problems cheerz nas
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.
-
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
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.
-
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.
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.
-
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.
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 -
-
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.
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 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 -
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.
-
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
-
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
It seemed to be clear to everyone else
I know the language. I've read a book. - _Madmatt
-
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
-
It seemed to be clear to everyone else
I know the language. I've read a book. - _Madmatt
-
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
result = ((f&&f1) || (d&&d1) || (r&&r1)) && (f||f1) && (d||d1) && (r||r1)
-
result = ((f&&f1) || (d&&d1) || (r&&r1)) && (f||f1) && (d||d1) && (r||r1)
incorrect, none of the test cases have (f||f1) true. :|
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.
-
incorrect, none of the test cases have (f||f1) true. :|
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.
result = ((f&&f1) || (d&&d1) || (r&r1)) && (f==f1) && (d==d1) && (r==r1);
-
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
Is it simply the number of TRUE arguments passed? No TRUE args ==> FALSE even no of TRUE args ==> TRUE Otherwise ==> FALSE :confused: Tadeusz Westawic Sum quid sum.
-
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
( ( d && dl ) && ( r && rl ) ) || ( (d && dl) && ( !r && !rl) ) || ( (!d && !dl) && ( r && rl ) )
I wasn't, now I am, then I won't be anymore.
-
Is it simply the number of TRUE arguments passed? No TRUE args ==> FALSE even no of TRUE args ==> TRUE Otherwise ==> FALSE :confused: Tadeusz Westawic Sum quid sum.
What are you confused about? Perhaps you are confused that the problem had been solved 18 days ago by people how were not confused.:confused:
I know the language. I've read a book. - _Madmatt
-
( ( d && dl ) && ( r && rl ) ) || ( (d && dl) && ( !r && !rl) ) || ( (!d && !dl) && ( r && rl ) )
I wasn't, now I am, then I won't be anymore.
Only 18 days after everyone else. Glad it wasn't urgentz
I know the language. I've read a book. - _Madmatt