Problem 44374. Tautology

Most solutions will fail a test with more than 2 variables in the expression, e.g., 'A&B&C'.

below a list of randomly generated test cases (just with two variables), in case these help: assert(isequal(tautology('((0&1)|~B)&~B'),false));
assert(isequal(tautology('((0&~B)&~B)'),false));
assert(isequal(tautology('((0|A)&~A)'),false));
assert(isequal(tautology('((0|A)|1)'),true));
assert(isequal(tautology('((0|~B)|1)'),true));
assert(isequal(tautology('((1&0)|B)'),false));
assert(isequal(tautology('((1&1)&A)'),false));
assert(isequal(tautology('((1|0)|A)'),true));
assert(isequal(tautology('((1|A)|0)'),true));
assert(isequal(tautology('((1|~A)&B)'),false));
assert(isequal(tautology('((A&1)|~A)|A'),true));
assert(isequal(tautology('((A&~A)&~B)|~A'),false));
assert(isequal(tautology('((A&~B)&1)|B'),false));
assert(isequal(tautology('((A|0)&1)&~B'),false));
assert(isequal(tautology('((A|A)&A)|~A'),true));
assert(isequal(tautology('((B|0)&B)'),false));
assert(isequal(tautology('((B|1)&B)&A'),false));
assert(isequal(tautology('((B|A)|~A)'),true));
assert(isequal(tautology('((~A&~A)&0)&B'),false));
assert(isequal(tautology('((~A&~A)|0)'),false));
assert(isequal(tautology('((~A&~A)|~A)|1'),true));
assert(isequal(tautology('((~A|A)|~B)&1'),true));
assert(isequal(tautology('((~A|B)|A)'),true));
assert(isequal(tautology('((~A|~A)|1)'),true));
assert(isequal(tautology('((~A|~B)&0)'),false));
assert(isequal(tautology('((~B&0)&A)'),false));
assert(isequal(tautology('(0&1)|1&1'),true));
assert(isequal(tautology('(0|~A&B)'),false));
assert(isequal(tautology('(1|A&0)'),true));
assert(isequal(tautology('(A&A&~B)'),false));
assert(isequal(tautology('(A&~A|1)'),true));
assert(isequal(tautology('(A|1)|B'),true));
assert(isequal(tautology('(A|A)|A|1'),true));
assert(isequal(tautology('(B&1)|~B'),true));
assert(isequal(tautology('(B&~B)&~B&0'),false));
assert(isequal(tautology('(B|~B)|B'),true));
assert(isequal(tautology('(~A&B&0)'),false));
assert(isequal(tautology('(~A|0)|~B&~A'),false));
assert(isequal(tautology('(~A|1)|1'),true));
assert(isequal(tautology('(~A|B&B)'),false));
assert(isequal(tautology('(~A|B)|~B'),true));
assert(isequal(tautology('(~A|~A)|0'),false));
assert(isequal(tautology('(~B&0)&1|1'),true));
assert(isequal(tautology('1&B|~B|0'),true));
assert(isequal(tautology('B&1&A&1'),false));
assert(isequal(tautology('~A&0&1|1'),true));
assert(isequal(tautology('~B&0&~A|B'),false));
assert(isequal(tautology('~B|1|1|~B'),true));
assert(isequal(tautology('~B|~B&1|1'),true));

I believe the new test 16 is incorrectly defined (it should be y_correct=true)

it's boring if you change tests all the time.

Test 16 is still wrong.

Sorry, fixed.

@Jean-Marie - Between the various test suites, I think this is the fourth time I've had to solve the problem. How can you call that boring? :) But seriously, I think it's great that Jan's trying to get the test suite both challenging and correct. A robust test suite is much better than having only a few tests that can easily be fooled.

@James. Its the third try for me and it's boring because these updates (tests 15 and 16 particularly) are tricky and useless. I suggest to create an harder version of this problem.

@Jean - Blame Peng for bringing up the "more than 2 variables" caveat that caused all of my solutions to either time out (at least a dozen of mine have vanished due to timing out while rescoring) or outright fail! :-) I agree that having the 26 variables is slight overkill, but that is what makes this the "hard" problem. I set them all equal to 0, then all equal to 1, and then ran a bunch of random permutations of 0 and 1. I evaluated all of those conditions to determine if any of them would come back false. Not perfect, but enough to satisfy the test suite and much quicker than the 2^26 combinations needed for the every possible combination of A-Z.

@James. Blame me for the "more than 2 variables" comment? Absolutely nonsense! Commenting is one of Cody's core features which allows players, i.e., ALL OF US, to effectively discuss, share, and communicate on any aspects of a problem or solution, and this is how us players help to make Cody an exciting world. Remember that "Comment on any problem or solution" is the 5th top feature appearing in the definition of Cody (https://www.mathworks.com/matlabcentral/about/cody/) .

@Peng - I apologize. Your solutions are usually among the best for the problems, and I meant no offense. The "Blame Peng" portion of the comment was meant as a joke. You are 100% right that most of the earlier solutions (including all of mine!) would fail with more than two variables. As I said in my earlier comment to Jean, the fact that Jan is trying to come up with a more robust test suite is a good thing, as it will help everyone get better at MATLAB. Again, apologies.

I don't agree with your comments guys. I don't like rescoring because the process don't respect player solutions already submitted. Cody5 is a challenge with a deadline. These problems are special. If you want to update the tests, create another version for the community. Tests 15 and 16 are made only to avoid the creation of a thruth table with regexp/dec2bin. I don't know why you want to exclude this correct approach (with an artificial sequence of 26 letters). But it's just my opinion.

@James. Thank you for your explanation, and I do appreciate. I don't have problems with Jan's approach which gradually reinforces the testsuite and makes the problem harder and harder. In fact, all he did was just addressing all raised comments from the solvers side (thus, nothing to blame here). But I personally hesitated to make such significant changes on my own problem once it is published in the Cody5 anniversary group, because solvers are not notified when their solutions failed the new added test cases. If solvers do not come back to check themselves, they would never know and hence miss the opportunity to complete the problem. Taking my own problem as an exmaple (https://www.mathworks.com/matlabcentral/cody/problems/44353), I did receive a comment on whether there exists a way to make the resolution of the solution map better. I do have a simple way to address this comment by truncating the extremely large solution size to a smaller upper limit (say 100) which would lead to much higher resolution on the solution map. But I didn't do so because it may change the current ranking of the solutions (as the solutions in my problem are measured by runtime speed, which may vary in different runs). I don't want to disappoint any solvers to my problems, so I didn't make any changes to my test suite. I do understand the dilemma here because it is extremely hard to make a perfect test suite for a hard problem, which is perhaps much harder than solving the problem.

Having said that, I would raise suggestion to the Cody team that whenever a problem is updated and rescored, all solvers, or at least the solvers whose solutions failed the new tests, should be notified.

I agree with Jean-Marie that Cody5 problems are somewhat special and perhaps we should be treating them a bit more carefully wrt rescoring. In my opinion it is somewhat unfortunate that Cody Badges can be lost after they are obtained (this happens when one of the problems gets rescored and all of your solutions to that problem fail). I believe this is sometimes fixed by Cody admins directly, but it still creates some lingering problems (e.g. badge events get removed from the timeline so they do not have a date/time). In addition, unless you come back to Cody often, it is simply very hard to notice when a problem has been rescored and one or all of your solutions now fail the new testsuite (e.g. you may come back to Cody and notice that your score has decreased, but it is very hard to know exactly why), which makes this a particularly sticky issue in a challenge like Cody5 with a definite deadline and a lot of new players. In any way, because of all of this, perhaps we, as problem creators, should be just a little bit more careful when dealing particularly with Cody5 problems just to make sure that players do not loose their achievements/solutions somewhat "unfairly". That does not mean, in my opinion, that we should not re-score at all (e.g. personally I still feel that it is perfectly fine to re-score as many times as you need in order to fix/improve your testsuite, as well as to rescore simply with the intention of removing cheat entries -e.g. look-up table solutions limited to testsuite cases only-), but it probably means that we should be careful (and perhaps a bit conservative) with testsuite changes just to make sure that we are not invalidating otherwise reasonable (even if not perfect) solutions. In this particular case, tests 15 and 16 probably lie right in this borderline scenario, where I can see how they are helping improve the testsuite, but they may also be removing somewhat-unfairly otherwise good solutions that simply did not consider this rather-extreme case of all 26 variables being simultaneously included in a logic statement, so perhaps these two tests could be removed or changed to some other case that is not so taxing?. Would love to hear your thoughts

@Jean - It is indeed possible to make a 2^26 truth table, you just have to do it efficiently ;)

I also agree with Alfonso wrt rescoring, you could lose your solved problems and you wouldn't notice until a week or so has passed, for example.

@Daniel, that is true, but other approaches (e.g. @James random-sampling approach) would still fail on tests 15/16, or anything that looks like assert(isequal(tautology(strjoin(arrayfun(@(i)['~'*ones(rand>.5) char('A'+i-1)],1:26,'uni',0),'|')),false)) while still working just fine on less-taxing scenarios. The point is that the original testsuite did not include cases for this sort of extreme scenarios (to be precise the original testsuite only included two-variable A/B cases) so it feels a bit unfair to expect original solutions to be general enough to cover this sort of scenarios. For example, Jan could probably invalidate *all* of the current solutions if he considers "A" and "a" to be two different variables, and creates a few tests that include 52 mixed-case variables. I believe that is probably not a great idea in the context of Cody5, even though I think it would be a fantastic idea to create a new problem that asks you explicitly to solve this rather-difficult larger-number-of-variables case.

@Daniel, and funny that you should mention, my apologies that this happened to you!! If I remember correctly you already had all cody5:hard problems solved on Oct 21st, despite your badge indicating a Oct 31st date now, so appropriate bragging rights to you :)

@Alfonso - You're right. But I couldn't beat you anyway, you're just too good. And I'm pretty sure I wouldn't ended up as good as second if some others had started the problems earlier.

Personally, I keep a really great memory of the Cody series Hackathon and Singularity by Alfonso and Get Me by Frequency Domain where difficulty has been increased gradually. It's very didactic because you must study other solutions to really understand limits of your algorithm. At the same time, you have the feeling to play a game where you must progress. Difficulty can be pushed very hard. In the same idea, you have Codejam competition with the small and large datasets. But it's a lot of work for the creator.

Am I the only one that thinks test case 49 is incorrect? How is:

(1|A&0)

always true? 1|A is always 1, but 1&0 is always 0. What am I missing?