Beta

Finite automation 1: DFA Runner

55aland97
Description
Loading description...
Fundamentals
View
AllIssues7Questions1SuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • Kees de Vreugd Avatar
     
    
q0 -0-> q1
q1 -0-> q0
q0 -0-> q1
When characters are over, DFA is in state q1 which is not accepted.

    That's not correct. I think. Add an extra 1 and you end up in state 2, which is the accepted state. Or am I missing something here?

  • JohanWiltink Avatar

    The Example tests are pretty much useless: they pass both () => false and () => true. Also, they have actual and expected in the wrong order and they have it nested in it.

    Were they updated when the Submit tests were, or was that overlooked? ( Yes, I reset the Trainer. )

  • FArekkusu Avatar

    This kata is effectively a duplicate of any FNS executor, e.g. this one - the addition of a couple if (curState not in X) return false statements doesn't make it novel or unique.

    • aland97 Avatar

      if that was the only difference I would agree

    • aland97 Avatar

      but in the indicated kata all transitions and state hardcoded

    • FArekkusu Avatar

      if that was the only difference I would agree but in the indicated kata all transitions and state hardcoded

      Is this a joke? Turning a hard-coded value into a function parameter changes absolutely nothing about the task or the algorithm.

      Are you also going to tell me that these are 2 completely different things, and by adding another parameter you're "generalizing" something?

      f = n => n + 1;
g = (n, m) => n + m;
    • aland97 Avatar

      yes this is how it works

    • dfhwze Avatar

      I'd say this kata is in the grey zone of being a duplicate. As it's the first kata of a series of kata's that get harder and harder, I would opt to keep this one.

    • Blind4Basics Avatar

      imo, it's too much of a duplicate, yes. The series can still exist, it would just need to put the #1 on the next one.

  • Blind4Basics Avatar

    Hi,

    The description is extremly convoluted, using different notations to denote the same thing (code/description), changing the oprder from time to time, the inputs aren't clearly described (at least not when it would be appropriate), sometimes using "qi" sometimes talking about numbers, most of the actual arguments name aren't even showing up explicitely in the description, ...

    You're doing your best at losing the reader, there. :s

    • aland97 Avatar

      I agree with you. I'm really bad in the descriptions)) tried to improve. If it does not bother you, could you give specific advice on increasing readability.

    • JohanWiltink Avatar

      Actual specs, including any encodings, for the function arguments would help.

      Does the DFA input need to be consumed exactly completely?

    • aland97 Avatar

      i hope it's more clear now

    • Blind4Basics Avatar

      ex on this one:

      Prefere to use the arguments names in the descirption:

      • DFA starts in the Starting state S start
      • Read next character of string input (and there you realize that an argument named input is rather unfortunate)
      • The state is set to the state corresponding to the transition -> that one is totally uncomprehensible
      • If string are over and state from A, then string accepted, else go to (3) -> same here. Even after I solved the kata, I have no clue about what you're trying to convey here

      English wording is helping too, or at least something closer to english (if I see the mistakes, that's a bad sign x) ;o )

      If there are no transition for the current state and current symbol, then string is not accepted

      This DFA accepts "0011" and does not accept "000".

      A title section is missing before that line => ### Example

      States for "0011":

      => Succession of states for the input "0011", starting in state start

      generally, you put the example at the end (before any "notes"), or at the very least, once you've described the actual task.

    • aland97 Avatar

      Made changes, I hope I didn't miss anything

    • Blind4Basics Avatar

      Starting state of S from Q

      => A starting state startState from Q

      The set of accepted states A, a subset of Q

      => The set of final accepted states acceptStates, a subset of Q

    • Blind4Basics Avatar
      Issue marked resolved by Blind4Basics 3 years ago
  • FArekkusu Avatar
    • Tests are not using describe and it blocks correctly
    • 200k random tests is way too much
    • Duplicate as pointed out below
    • aland97 Avatar
      1. What i am doing wrong
      2. I have reduced the number of tests to 10.000
      3. Generalization is an important part, I continue to believe that this is not a duplicate
    • JohanWiltink Avatar
      1. Looking at the example tests: nothing. Assertions must be wrapped in exactly one it-block; it-blocks can be wrapped in any number ( including zero ) of describe-blocks.

      Anybody who believes describe is not optional is invited to provide a reference.

    • Blind4Basics Avatar

      Anybody who believes describe is not optional is invited to provide a reference.

      and why do you feel that urge for breaking the homogeneity of the practices further...? I still don't get that.

    • dfhwze Avatar

      This comment has been hidden.

    • aland97 Avatar

      I cannot use 'it' for every string, there are too many of them. But i use 'describe' for separetateing example and random tests, and provide information about DFA and input on fail. I think this is enough to cover the first two points of issue. If you agree, please close it and open new for third point.

    • FArekkusu Avatar

      open new for third point

      Done.

      Issue marked resolved by FArekkusu 3 years ago
    • JohanWiltink Avatar

      Anybody who believes describe is not optional is invited to provide a reference.

      and why do you feel that urge for breaking the homogeneity of the practices further...? I still don't get that.

      I'm not breaking homogeneity. Haskell has exactly the same wrapping rules. describe is a no-op in terms of testing; all it does is group.

      Please note I'm not getting notifications for this thread and probably won't come across it in the future. You can reach me on Gitter.

  • dfhwze Avatar

    I haven't tried this one, but is it a duplicate? https://www.codewars.com/kata/5268acac0d3f019add000203

    • aland97 Avatar

      not quite, there is a given number of states and predefined transitions. This kata is more general, and is rather needed to close the gap in the series of kata about finite automata.

    • aland97 Avatar

      I have planned 5 kata about regex, DFA and NFA

    • FArekkusu Avatar

      not quite

      No, it's pretty much the same unless you're saying that throwing in 2 small if statements makes your kata any novel. Implying that the list of transitions being provided as an argument instead of being hardcoded makes any difference would be ridiculous.

      This kata is rather needed

      Needed by whom and why?

  • Voile Avatar

    The third fixed test case (the Should work for /a(aa|bb)*b/ one) is invalid: input is 00 but the states are ab. It's not mentioned that such cases needs to be handled.

  • mortonfox Avatar

    Random tests generate transition tables that violate this condition: There can be only one transition for each "s1" and "a".

  • rowcased Avatar

    The input can be modified by the user.