Beta

Increment a variable ...

4mauro-1
Description
Loading description...
Esoteric Languages
Algorithms
Fundamentals
View
AllIssues2QuestionsSuggestions4Show Resolved
  • Please sign in or sign up to leave a comment.
  • cplir-c Avatar

    I don't think this is a spoiler because it doesn't help solve the kata.

    In case anyone else needs the interpreter code for local testing:

    from collections import namedtuple as _namedtuple
from random import randrange as _randrange
import re as _re

Result = _namedtuple('Result', ('steps', 'out_of_mem', 'pointer', 'value', 'cells'))

class InvalidBfError(ValueError):
    pass

def interpreter(code, values=4096, num_cells=8, timeout=30000):
    def parse_loops(code):
        marks = {}
        start = []
        for i, c in enumerate(code):
            if c == '[':
                start.append(i+1)
            elif c == ']':
                try: s = start.pop()
                except IndexError: raise InvalidBfError("unbalanced ']'")
                marks[s] = i+1
                marks[i+1] = s
        if start: raise InvalidBfError("unbalanced '['")
        return marks
    
    code = _re.findall(r'<|>|\[|\]|\++|-+|[,.]', code)
    loops = parse_loops(code)
    cells = [0] * num_cells
    start = _randrange(values)
    cells[0] = start
    p = i = t = 0
    while i < len(code) and t <= timeout:
        c = code[i]
        c, l = c[0], len(c)
        i += 1
        t += 1
        match c:
            case '+':
                cells[p] = (cells[p] + l) % values
            case '-':
                cells[p] = (cells[p] - l) % values
            case '>':
                p += 1
                if p >= num_cells: break
            case '<':
                p -= 1
                if p < 0: break
            case '[':
                if cells[p] == 0: i = loops[i]
            case ']':
                if cells[p] != 0: i = loops[i]
            case ','|'.':
                raise InvalidBfError(f'I/O command not supported: {c!r}')
    incr = (cells[0] - start) % values
    return Result(t if t <= timeout else -1, p<0, p, incr, cells[1:])
  • Voile Avatar
     
    increment(123)  =>  '>>+++++[<++++++++>-]<+[<+++>-]<'

    Isn't +++++[>++++++++<-]>+[<+++>-]< shorter?

  • yLaWy Avatar

    Typo: "tour task is to generate the BF code that adds n to the cell" should probably be "YOUR task..."

  • lachesism Avatar

    Hi,

    • Your bf interpreter should report errors when the user returns bad bf code, such as mismatched square brackets or containing input/output instructions, rather than continuing to run or just raising an error.

    • You should combine seven assertions into one for a single test. For example:

    def test_increment(n):                                  def test_increment(n):
    test.assert_equal(x, y, err_msg0)                       def validate()
    ...                                                         if x != y: return err_msg0
    test.expect(b, err_msg1)                                    ...
                                              =>                if not b: return err_msg1
                                                            err_msg = validate()
                                                            if err_msg: test.fail(err_msg)
                                                            else: test.pass_()

    • You should make this type of solution less easy to pass.

    • The reference solution passes the entire 0-4095 tests in about 8.5 seconds most of the time, so why are there so few random test cases?

    • mauro-1 Avatar

      Thanks for reporting. Tomorrow I'll review the kata.

      You should make this type of solution less easy to pass.

      IMHO this is cheating, and it's hard to stop (at least in python).

    • lachesism Avatar

      Well, I know it's impossible to stop it, but you can at least make it more difficult.

    • mauro-1 Avatar

      Try now, should be fixed (except anticheat).

    • lachesism Avatar

      Looks much better, although there are still a few minor issues :)

      • Your bf interpreter still ignores input/output commands. It would be more user-friendly to report errors.

      • The number of random tests is still not enough IMO.

        For example, even in the worst case, a solution with 70 wrong answers might take only 40 attempts (1-(1-(1-70/4096)^125)^40=0.993) to pass the random tests.

        So I suggest setting the random tests to random.sample(range(4096),1600).

        This way, even a solution with 10 wrong answers will take C(4096,1600)/C(4096-10,1600)=142.632 attempts on average to pass the random tests.

        You could use 16 batches of 100 random test cases or some other reasonable scheme to organize this many random tests.

      • About the code size limit, existing solutions are basically in the 2.5kb size range. It might be better to set it to 5kb to reduce the possible hard-coded size of future solutions.

    • lachesism Avatar

      Example of a solution having 70 wrong answers passed the random tests.

    • mauro-1 Avatar

      Updated:

      • 5 kB code size limit
      • 1660 random tests
      • BF errors in case of I/O cmds
    • lachesism Avatar

      Nice work! 👍

      Issue marked resolved by lachesism 2 years ago
  • Kacarott Avatar

    Some typos: sigle, core (should be code I assume), forst

  • LRDPRDX Avatar

    First of all, cool Kata! I'd love if it would be available for Haskell. Second of all, I think there is a typo in the description of the operations:

    ]: jump backward to the command after the matching ] if the current cell is non-zero

    Should be

    ]: jump backward to the command after the matching [ if the current cell is non-zero

  • Blind4Basics Avatar

    hi,

    from what I grasp from the example in the description, your wording is incorrect: what the user is apparently supposed to do is to "increment the cell n in the tape", no? 0 indexed? forget that... x)

    edit: this task does ring a bell... I mean, I believe we already have a kata asking for the same kind of optimizations...