6 kyu

Semi-Thue Systems - The Word Problem [Part 1]

50Dr Gabo
Description
Loading description...
Mathematics
Algorithms
View
AllIssues6Questions1SuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • mauro-1 Avatar

    There should be test cases with overlapping occurrences of the left hand side of a rule, e.g.:

    word_problem([('aa', 'bb')], 'aaa', 'abb', 1)  ->  True

    otherwise this kind of solution can pass.

  • Unnamed Avatar

    Missing an edge case test with from_str == to_str.

  • Blind4Basics Avatar

    warning with your random tests: currently, the expected outputs aren't random at all => you need to build them differently, otherwise this kind of solution can pass

  • Blind4Basics Avatar
    • the description doesn't seem clear about the fact that the rules may not be applied systematically to get the answer. Like the last sample test.
    • nothing is said about having a deterministic or undeterministic set of rules. Meaning: could we get several rules with the same original substring leading to different replacement strings? That info should be:
      • talked about in the description
      • if it cannot happen, you should provide the rules as a dict instead
      • if it can happen, you need at least a sample test with that

    EDIT: missing sample test: something with two rules where the initial string of one is a substring of the other, like ('ab',...), ('abc',...), and where you need to pick the second rule to get to the expected output.

    • Dr Gabo Avatar

      As a clarification, you can have two rules with the same left handside, so a dict might not be the best. I will modify the description and make more robust tests later. Thank you for your structured issue :)

    • Blind4Basics Avatar

      ok, then you have another problem: this is never happening in the tests, apparently!

    • Dr Gabo Avatar

      The tests now are much more robust and can filter out all the wrong solutions you gave me. Also, the description has been clarified.

      Issue marked resolved by Dr Gabo 5 years ago
    • Blind4Basics Avatar

      errr... I don't see the new smaple tests (saw the shift to the new framework only / And you could update the test case to the new framework too...)

    • Dr Gabo Avatar

      My bad, I forgot to add the tests to the samples :S (and I shifted the rest of the tests now).

  • Blind4Basics Avatar

    Hi,

    Plz, use the new python test framework. It makes the test suite far more readable.

  • B1ts Avatar

    Is it intended to have only the first occurance of rule (in the string) replaced? Take this test for example: 

    test.assert_equals(word_problem([('a', 'c')], 'aba', 'abc', 1), True)

    My solution would fail that, but it clearly looks valid. There should be more tests for such cases or description altered to clarify this (bad idea IMO)

    • Dr Gabo Avatar

      To apply a rule means to substitute one of the occurences (not necessarily the first one). So to go from 'aba' to 'abc' you need one application and to go from 'aba 'to 'cbc' you need two:

      word_problem([('a', 'c')], 'aba', 'abc', 1) == True
word_problem([('a', 'c')], 'aba', 'cba', 1) == True
word_problem([('a', 'c')], 'aba', 'cbc', 1) == False
word_problem([('a', 'c')], 'aba', 'cbc', 2) == True

      I will modify the description to clarify this fact.

      Question marked resolved by Dr Gabo 5 years ago
    • B1ts Avatar

      That's all well and good, but that means my flawed solution passed all tests, which is an issue =/

    • Dr Gabo Avatar

      That's because it seems like I forgot to add random tests with non-exhaustive rule applications. I will add them later :)

    • Blind4Basics Avatar

      advise: unpublish your kata in the meantime, then. ;)

  • Len512 Avatar

    Needs better random tests, my solution should not pass.

    • Dr Gabo Avatar

      The rules in the random tests happened to be too structured. A randomization did the trick. Thank you for your time.

      Issue marked resolved by Dr Gabo 5 years ago