3 kyu

The boolean order

361 of 1,388KenKamau
Description
Loading description...
Strings
Algorithms
View
AllIssues6Questions9Suggestions4Show Resolved
  • Please sign in or sign up to leave a comment.
  • Ubzugajir Avatar

    This comment has been hidden.

  • junayet229 Avatar

    This comment has been hidden.

  • laurens1234 Avatar

    This comment has been hidden.

  • renskir Avatar

    This comment has been hidden.

  • SerhiyShamshetdinov Avatar

    Ken, I see your below comment is actually the part of task specification. Otherwize it has another understandings & solutions. -Add to spec please something like your answer below-. Nice Kata, but has not clear spec))

    UPDATED!!! The following author comment (that you may find in the answers several year ago) actually is wrong OR confusing! My final solution counts both ((1&0)&0) & (1&(0&0)) variants.

    .... For instance, there is no real difference between the first and the second line given above. Adding extra parentheses does not change this fact. Look at them again:

    [ '((1|(1&0))^((1&0)&0))' ]
[ '((1|(1&0))^(1&(0&0)))' ]

    The main differences are at the ends of the two equations.

    Extra parentheses would have made sense if the last two operators were different. If they are the same, as in this case, extra parentheses result in duplicates.

    I hope this helps.

  • hertatra Avatar

    can somebody give me a little hint? am I supposed to find the most effecient way to list all the parenthesis combination and then eval() it one by one OR is there a clever way to just find a True-result parenthesis combination? (my answer works but time out )

  • udovr Avatar

    Damnit, I'm almost there. (works but times out)

    I just need a formula to calculate how many combinations (wether true or false doesn't matter)

    I can make of a (remaining) part of the equation, to speed up things...

    I get weird numbers when I do it with the solver: for x times True and (x-1) times & : on the 4, 8 and 16 times True I get odd results. The rest are even.

    (I only went to 16, next would have taken 10 minutes or so)

    What college degree math theory am I missing here? (math noob here)

  • unclecid Avatar

    Can someone explain to me how there can be more than 300 possible parenthesis combinations for an "s" of length 8?

    There should be at most 64 combinations for "s" of length 8, and some of them will be false.

    If you go by the examples provided in the description everything must be enclosed in parenthesis. And the number of combinations of parenthesis go 1,2,4,8,16, etc for length 2,3,4,5,6, etc. It doesnt seem to make sense.

    What am I missing? Thanks.

  • tweller Avatar

    How many braces am I supposed to put into the equation? The test "t", "" (true with no operator at all) has unlimited results, depending on the number of braces to be used: (t), ((t)), (((t))), ((((t)))), etc.

    Reading the other comments, I also wonder what the operator precedence shall be in order to sort out the duplicates.

  • Spickelbing Avatar

    very nice kata, I learnt something from this

  • Minecraftian14 Avatar

    I wrote some good amount of mess to solve it... As far as I understand my own code (which I forgot right after writing) the algorithm seems to be working just fine! Well the results are of cource not correct 😝. Here are a few tests

    tft,^& = 2
ttftff, |&^&& = 36
ttftfftft,|&^&&||^ = 23296
tt, | = 1
ttt, || = 2
tttt, ||| = 6
ttttt, |||| = 24

    If anyone has a clue, please help me out 😁.

  • fibonaccios Avatar

    This one looks scary as hell!

  • Will_Burrows Avatar

    I'm not sure I'm getting the instructions correctly. In the second case, Test.assert_equals(solve("ttftff","|&^&&"),16), why are there supposed to be 16 arrangements that evaluate to True? These are the possible arrangements of parentheses:

    ((((1|1)&0)^1)&0)&0 (((1|1)&0)^1)&(0&0) ((1|1)&0)^((1&0)&0) ((1|1)&0)^(1&(0&0)) (1|1)&(((0^1)&0)&0) (1|1)&((0^1)&(0&0)) (1|1)&(0^((1&0)&0)) (1|1)&(0^(1&(0&0))) 1|((((1&0)^1)&0)&0) 1|(((1&0)^1)&(0&0)) 1|((1&0)^((1&0)&0)) 1|((1&0)^(1&(0&0))) 1|(1&(((0^1)&0)&0)) 1|(1&((0^1)&(0&0))) 1|(1&(0^((1&0)&0))) 1|(1&(0^(1&(0&0))))

    There are 16 of them in total, and at least one of them is False (namely, the first one). So... is there something I'm completely missing? And if so, what is it?

  • panda666666 Avatar

    well,that is very funny.i have one solution not be tested which is that you can select one operator and than calcuate the result that the right number and the left,and then put the result in the new number list and reselect one operator and repeat so on.The only case what i concern is that this alogrithm will overtime>.....

  • aydang Avatar

    Fun Kata! I think my solution was memory over efficiency but oh well.

  • Arganancer Avatar

    Hella challenging. I feel embarrassed, but I had to inspire myself from a solution I found online. Definitely a mind bender. Thanks for the challenge!

  • erik6690 Avatar

    This comment has been hidden.

  • erik6690 Avatar

    I think there must be an issue with the acceptance test. The basic test is passing fine for me but the remote test is failing with warnings that say warning: comparison of integers of different signs: 'int' and 'std::__cxx11::basic_string<char, std::char_traits, std::allocator >::size_type' (aka 'unsigned long') [-Wsign-compare]. It goes on to reference code that I didn't write. I tried every concievable change to variable types but I keep getting the exact same error.

  • erik6690 Avatar

    This comment has been hidden.

  • colin9 Avatar

    How about an advanced variant of this kata where it doesn't count (a&b)&c different to a&(b&c) Test.assertEquals(solve("tft","^&"),2); Test.assertEquals(solve("ttt","&&"),1);

  • colin9 Avatar

    What if you added this to the sample tests: Test.assertEquals(solve("ttt","&&"),2);

    I think that might eliminate a lot of confusion about what counts. This is assuming that your answer (like mine) does return 2 for that test.

  • JustARatherRidiculouslyLongUsername Avatar

    I've got a solution that passses all the sample tests in ~0.3 seconds. It times out in the full test though. If it isn't too much to ask, could you possibly tell what the maximum length of 's' is that we're supposed to handle, so i can know whether or not im on the right track? Thanks!

  • eidelen Avatar

    Great Kata. Thank you! For days I was a useless father and husband :)

  • KataSideKick Avatar

    C# Translation added.Please review and approve~

  • ThomasMrY Avatar

    Some of the test sample results' orders of magnitude too big num = 945766470799 for i in range(num): i += 1

  • gkucmierz Avatar

    In second case Test.assertEquals(solve("ttftff","|&^&&"),16); Which of these should be considered as distinct?

    [ '((1|(1&0))^((1&0)&0))' ]
[ '((1|(1&0))^(1&(0&0)))' ]
[ '(1|((((1&0)^1)&0)&0))' ]
[ '(1|(((1&0)^1)&(0&0)))' ]
[ '((1|(1&0))^((1&0)&0))' ]
[ '(1|(((1&0)^(1&0))&0))' ]
[ '((1|(1&0))^((1&0)&0))' ]
[ '(1|((1&0)^((1&0)&0)))' ]
[ '((1|(1&0))^(1&(0&0)))' ]
[ '(1|(((1&0)^1)&(0&0)))' ]
[ '((1|(1&0))^(1&(0&0)))' ]
[ '(1|((1&0)^(1&(0&0))))' ]
[ '(1|(((1&(0^1))&0)&0))' ]
[ '(1|((1&(0^1))&(0&0)))' ]
[ '(1|((1&((0^1)&0))&0))' ]
[ '(1|(1&(((0^1)&0)&0)))' ]
[ '(1|((1&(0^1))&(0&0)))' ]
[ '(1|(1&((0^1)&(0&0))))' ]
[ '((1|(1&0))^((1&0)&0))' ]
[ '(1|(((1&0)^(1&0))&0))' ]
[ '((1|(1&0))^((1&0)&0))' ]
[ '(1|((1&0)^((1&0)&0)))' ]
[ '(1|((1&(0^(1&0)))&0))' ]
[ '(1|(1&((0^(1&0))&0)))' ]
[ '((1|(1&0))^((1&0)&0))' ]
[ '(1|((1&0)^((1&0)&0)))' ]
[ '(1|(1&(0^((1&0)&0))))' ]
[ '((1|(1&0))^(1&(0&0)))' ]
[ '(1|(((1&0)^1)&(0&0)))' ]
[ '((1|(1&0))^(1&(0&0)))' ]
[ '(1|((1&0)^(1&(0&0))))' ]
[ '(1|((1&(0^1))&(0&0)))' ]
[ '(1|(1&((0^1)&(0&0))))' ]
[ '((1|(1&0))^(1&(0&0)))' ]
[ '(1|((1&0)^(1&(0&0))))' ]
[ '(1|(1&(0^(1&(0&0)))))' ]
  • paranoya123 Avatar

    solve("ttftff","|&^&&") == 16 Im really cant get it =) As I understand if first argument is true and last action is ( | ) than we can have variations of last 4 actions (&^&&) = 1 * 2 * 3 * 4 = 24 and all this solutions are true. But in test we got only 16. Help me please !

  • asameshimae Avatar

    This is a great challenge, thanks, but I'm struggling to optimise my code! Similarly to some comments, I solved this for the order in which terms are evaluated - giving multiple solutions for the same parenthetical expression, e.g. (t&t)|(f&f) - this can be evaluated in two orders, but only counts as one solution.

    I made my function translate the order into parenthetical notation, then filter out duplicates, so it works, but this makes it far too slow. Any tips on how to reconceptualise this?

  • AdmiralSausage Avatar

    I had a really hard time understanding the rules, like several people in the comments, because you express the problem in terms of adding braces.

    Could I suggest that you phrase the problem something like: "Varying the order of evaluation, how many distinct expression trees evaluate to true?"

    This is unambiguous and answers questions like: "is t|t|t distinct from (t|t)|t and t|(t|t) ?" (answer: no, it's either one or the other)

    Even once you understand the problem, I think it's a little hard for 3 kyu. I really enjoyed it anyway, so thanks.

  • EatSomeCookies Avatar

    Hi, i have problem with c++ random test. String with operators contain same number of characters as string of values:

    basic_tests Log size var=3, size_op=2 var=tft, op= ^& size var=6, size_op=5 var=ttftff, op= |&^&& size var=8, size_op=7 var=ttftfftf, op= |&^&&|| size var=9, size_op=8 var=ttftfftft, op= |&^&&||^ size var=10, size_op=9 var=ttftfftftf, op= |&^&&||^& size var=25, size_op=24 var=ttftfftftffttfftftftfftft, op= |&^&&||^&&^^|&&||^&&||&^ Test Passed random_tests Log size var=20, size_op=20 var=ffttfttftfttfttttfff, op= ^^&^|&&||&&|||^&&&^&

  • C-V Avatar

    C++ translation published

  • ba78 Avatar

    According to the description above, solve("tft", "^&") should be 2. You have replied to a question that "(t ^ f & t)" is a valid expression. I'm confused, because all of these are true:

    • "((t ^ f) & t)" = True
    • "(t ^ (f & t))" = True
    • "(t ^ f & t)" = True

    What's wrong with my logic? It would help for me, if your description include the False cases as well.

  • bellson0d Avatar

    This comment has been hidden.

  • user6793616 Avatar

    This comment has been hidden.

  • skank Avatar

    This comment has been hidden.

  • yidui Avatar

    Excellent kata. I learned a lot about how to optimize my code from it! Thanks:)

  • lechevalier Avatar

    Scary kata at first sight but once you get the right approach, it is an enjoyable one! Do you have such other tasty katas? :-D

  • Blind4Basics Avatar

    Java translation

    Please review and approve.

  • ZED.CWT Avatar

    Approved. It is not hard but i should admit that i was scared when i first saw it. I think it is 5kyu but considering how many skips there are, well, approved with 4kyu. Please let me know if the rank should be modified

  • mro Avatar

    In random tests length of ops must be one less than of string. However ops and string have the same length.

  • docgunthrop Avatar

    Just to clarify with a couple examples, the following sets for each example are all regarded as distinct?

    Example 1:
t & (t & t)
(t & t) & t
t & t & t

    and

    Example 2:
f | (f | (t | f) & t)
f | ((f | t) | (f & t))
f | (f | t) | (f & t)
f | (f | t | f & t)
f | ((f | t | f) & t)
f | (((f | t) | f) & t)
(((f | f) | t) | f) & t
f | f | t | f & t
  • docgunthrop Avatar

    For the tests, Expected and instead got are reversed.

  • anter69 Avatar

    I feel that the instrutions are a bit vague: why do you need outer braces? What about the normal operator order (left to right)? Is there any difference between ((t ^ f) & t) and (t ^ f) & t and (t ^ f & t) and t ^ f & t ?!