Move History

Fork Selected
  • Code
    import random
    
    # kata description:
    # https://www.codewars.com/kata/64fdf3cf18692c9b4eebbb83
    
    # enforced rules:
    # - `cmp` may be used `length` times
    # - `swap` may be used at most one times after `cmp` (and also once before first cmp)
    
    # this is :carrot:'s solution used as demo
    # don't comment on the kumite since then this shows up on the front page with solution
    
    def one_quicksort_pass(length, cmp, swap):
        e, i, w = length - 1, 1, 1
        while i <= e:
            c = cmp(i-w, i)
            if c > 0:
                swap(i-w, i)
                i += 1
            elif c < 0:
                if random.randrange(5): # 20% chance to behave wrong, remove condition for correct solution
                    swap(i, e)
                e -= 1
            else:
                w += 1
                i += 1
    
    
    Test Cases Failed
    import codewars_test as test
    import random
    from solution import one_quicksort_pass
    
    
    def render_history(history, xs):
        if len(xs) > 20:
            return ""
        xs = xs[:]
        output = []
        output.append("")
        output.append("")
        output.append("initial list:")
        output.append(str(xs))
        output.append("")
    
        def pos_in_str(idx):
            if idx == 0:
                return 1
            idx = len(str(xs[:idx])) + 1
            return idx
    
        for name, i, j in history[:]:
            if name == "cmp":
                outcome = 1 if xs[i] > xs[j] else -1 if xs[i] < xs[j] else 0
                output.append(f"{name}({i}, {j}) = {outcome}")
            else:
                output.append(f"swap({i}, {j})")
    
            xss = str(xs)
            arrows = list(" " * len(xss))
            arrows[pos_in_str(i)] = "↑" if i != j else "⇈"
            if i != j:
                arrows[pos_in_str(j)] = "↑"
            arrows = "".join(arrows).rstrip()
            output.append(xss)
            output.append(arrows)
            output.append("")
            if name == "swap":
                xs[i], xs[j] = xs[j], xs[i]
        output.append("final result:")
        output.append(f"{xs}")
        return "\n".join(output)
    
    
    def run_test(xs):
        title = str(xs) if len(xs) <= 20 else f"list of length {len(xs)}"
    
        @test.it(title)
        def _():
            original = xs[:]
            # starting with a swap budget of 1 so that solver is able to move pivot
            # before doing any comparisons if they so wish
            swap_budget = 1
            cmp_budget = len(xs)
            exceeded_swap_budget = exceeded_cmp_budget = False
            history = []
    
            def validate_args(i, j):
                # in particular, they should not be slices,
                # since that would allow operating on multiple locations at once
                if type(i) is not int:
                    raise TypeError(f"index must be int, got {type(i)}")
                if type(j) is not int:
                    raise TypeError(f"index must be int, got {type(j)}")
    
            def cmp(i, j):
                nonlocal swap_budget, cmp_budget, exceeded_cmp_budget
                swap_budget = 1
                validate_args(i, j)
                if cmp_budget < 1:
                    exceeded_cmp_budget = True
                cmp_budget -= 1
                history.append(("cmp", i, j))
                if xs[i] > xs[j]:
                    return 1
                if xs[i] < xs[j]:
                    return -1
                return 0
    
            def swap(i, j):
                nonlocal swap_budget, exceeded_swap_budget
                if swap_budget < 1:
                    exceeded_swap_budget = True
                validate_args(i, j)
                swap_budget -= 1
                history.append(("swap", i, j))
                xs[i], xs[j] = xs[j], xs[i]
    
            one_quicksort_pass(len(xs), cmp, swap)
            passed, errmsg = validate_quicksort(original, xs)
            passed = passed and not (exceeded_cmp_budget or exceeded_swap_budget)
            debug_output = render_history(history, original) if not passed else ""
    
            if exceeded_cmp_budget:
                test.fail(
                    f"too many comparisons: {len(xs)} are allowed,"
                    f" but you used {len(xs) + abs(cmp_budget)}"
                    f"{debug_output}"
                )
            elif exceeded_swap_budget:
                test.fail(f"you made more than one swap between comparisons{debug_output}")
            else:
                test.expect(passed, errmsg + debug_output)
            return passed
    
    
    def validate_quicksort(inputlist, userlist) -> tuple[bool, str]:
        if not isinstance(userlist, list):
            return False, "Not a list!"
        if sorted(inputlist) != sorted(userlist):
            return False, "contents of userlist don't match inputlist."
    
        if inputlist == []:
            if userlist == []:
                return True, ""
            else:
                return False, "userlist should be []."
    
        pivot = inputlist[0]
        i = 0
        # less-than
        for i, x in enumerate(userlist):
            if x == pivot:
                break
            if x > pivot:
                return False, f"{x} is greater than pivot {pivot} but was found before pivot."
        # pivot
        for i in range(i + 1, len(userlist)):
            x = userlist[i]
            if x != pivot:
                break
            if x < pivot:
                return False, f"{x} is less than pivot {pivot} but was found after pivot."
        # greater-than
        for i in range(i + 1, len(userlist)):
            x = userlist[i]
            if x < pivot:
                return False, f"{x} is less than to pivot {pivot} but was found after pivot."
            if x == pivot:
                return False, f"{x} is equal to pivot {pivot} but was found after pivot."
    
        return True, ""
    
    
    @test.describe("Fixed Tests")
    def _():
        tests = [
            [5, 3, 9, 8, 2],  ## General example
            [2, 3, 9, 8, 5, 6],  ## Pivot is smallest
            [9, 8, 3, 5],  ## Pivot is biggest
            [2, 3, 9, 8, 0, 5, 6],  ## Pivot is 2nd-smallest
            [9, 8, 3, 5, 11],  ## Pivot is 2nd-biggest
            [5, 2, 9, 8, 5, 3, 1, 5],  ## Pivot is duplicated
            [5, 5, 5, 5, 5, 5, 5, 5],  ## All duplicates
            [5, 5, 5, 5, 5, 8, 5, 5],  ## Duplicates plus 1 other
            [5, 3, 5, 5, 5, 5, 8, 5],  ## Duplicates plus 2 others
            [5, 8, 5, 5, 8, 8, 5, 5],  ## Duplicates plus 1 other duplicated
            [5, 9, 3, 8, 2, 8, 1, 0, 11, 7, 5, 5, 8, 1, 12, 9, 999, 5, 8],  ## Many duplicates
            [],  ## Empty list
            [5],  ## One-element list
            [5, 3],  ## Two-element list
            [3, 5],  ## Two-element list
            [5, 5],  ## Two-element list
            [5, 8, 3],  ## Three-element list
        ]
        for test in tests:
            run_test(test)
    
    
    @test.describe("Random Tests")
    def _():
        failure_limit = 5
        lengths = list(range(3, 20)) * 3
        random.shuffle(lengths)
        for length in lengths:
            randomlist = [random.randint(1, 10) for _ in range(length)]
            passed = run_test(randomlist)
            if not passed:
                failure_limit -= 1
                if failure_limit < 1:
                    break
  • Code
    • import random
    • # kata description:
    • # https://www.codewars.com/kata/64fdf3cf18692c9b4eebbb83
    • # enforced rules:
    • # - `cmp` may be used `length` times
    • # - `swap` may be used at most one times after `cmp`
    • #
    • # ... thoughts?
    • # - `swap` may be used at most one times after `cmp` (and also once before first cmp)
    • # this is :carrot:'s solution used as demo
    • # don't comment on the kumite since then this shows up on the front page with solution
    • def one_quicksort_pass(length, cmp, swap):
    • e, i, w = length - 1, 1, 1
    • while i <= e:
    • c = cmp(i-w, i)
    • if c > 0:
    • swap(i-w, i)
    • i += 1
    • elif c < 0:
    • if random.randrange(5): # 20% chance to behave wrong, remove condition for correct solution
    • swap(i, e)
    • e -= 1
    • else:
    • w += 1
    • i += 1
    • i += 1
    Test Cases
    • import codewars_test as test
    • import random
    • from solution import one_quicksort_pass
    • # there's a lot of garbage in here that needs to be cleaned up,
    • # it may very well crash too
    • # but as some sort of proof-of-concept version while we figure out if this is worth going with -
    • def render_history(history, xs):
    • if len(xs) > 20:
    • return ""
    • xs = xs[:]
    • output = []
    • output.append("")
    • output.append("")
    • output.append("initial list:")
    • output.append(str(xs))
    • output.append("")
    • def pos_in_str(idx):
    • if idx == 0:
    • return 1
    • idx = len(str(xs[:idx])) + 1
    • return idx
    • for name, i, j in history[:]:
    • if name == "cmp":
    • outcome = 1 if xs[i] > xs[j] else -1 if xs[i] < xs[j] else 0
    • output.append(f"{name}({i}, {j}) = {outcome}")
    • else:
    • output.append(f"swap({i}, {j})")
    • xss = str(xs)
    • arrows = list(" " * len(xss))
    • arrows[pos_in_str(i)] = "↑" if i != j else "⇈"
    • if i != j:
    • arrows[pos_in_str(j)] = "↑"
    • arrows = "".join(arrows).rstrip()
    • output.append(xss)
    • output.append(arrows)
    • output.append("")
    • if name == "swap":
    • xs[i], xs[j] = xs[j], xs[i]
    • output.append("final result:")
    • output.append(f"{xs}")
    • return "\n".join(output)
    • def run_test(xs):
    • @test.it(f"don't mind me")
    • title = str(xs) if len(xs) <= 20 else f"list of length {len(xs)}"
    • @test.it(title)
    • def _():
    • original = xs[:]
    • swap_allowed = True
    • disallowed_swap = disallowed_cmp = False
    • cmp_count = 0
    • cmp_limit = len(xs)
    • # starting with a swap budget of 1 so that solver is able to move pivot
    • # before doing any comparisons if they so wish
    • swap_budget = 1
    • cmp_budget = len(xs)
    • exceeded_swap_budget = exceeded_cmp_budget = False
    • history = []
    • def cmp(i, j):
    • nonlocal swap_allowed, cmp_count, disallowed_cmp
    • swap_allowed = True
    • cmp_count += 1
    • def validate_args(i, j):
    • # in particular, they should not be slices,
    • # since that would allow operating on multiple locations at once
    • if type(i) is not int:
    • # in particular, it should not be slice
    • raise ValueError(f"index i must be int, got {type(i)}")
    • raise TypeError(f"index must be int, got {type(i)}")
    • if type(j) is not int:
    • raise ValueError(f"index j must be int, got {type(j)}")
    • if cmp_count > cmp_limit:
    • disallowed_cmp = True
    • raise RuntimeError(f"You may only make {cmp_limit} comparisons.")
    • history.append(("cmp",i,j))
    • raise TypeError(f"index must be int, got {type(j)}")
    • def cmp(i, j):
    • nonlocal swap_budget, cmp_budget, exceeded_cmp_budget
    • swap_budget = 1
    • validate_args(i, j)
    • if cmp_budget < 1:
    • exceeded_cmp_budget = True
    • cmp_budget -= 1
    • history.append(("cmp", i, j))
    • if xs[i] > xs[j]:
    • return 1
    • if xs[i] < xs[j]:
    • return -1
    • return 0
    • def swap(i, j):
    • nonlocal swap_allowed, disallowed_swap
    • if not swap_allowed:
    • disallowed_swap = True
    • raise RuntimeError("You may only swap after making a comparison.")
    • if type(i) is not int:
    • # in particular, it should not be slice
    • raise ValueError(f"index i must be int, got {type(i)}")
    • if type(j) is not int:
    • raise ValueError(f"index j must be int, got {type(j)}")
    • history.append(("swap",i,j))
    • swap_allowed = False
    • nonlocal swap_budget, exceeded_swap_budget
    • if swap_budget < 1:
    • exceeded_swap_budget = True
    • validate_args(i, j)
    • swap_budget -= 1
    • history.append(("swap", i, j))
    • xs[i], xs[j] = xs[j], xs[i]
    • one_quicksort_pass(len(xs), cmp, swap)
    • if disallowed_cmp:
    • test.fail("too many comparisons")
    • return
    • if disallowed_swap:
    • test.fail("swap may only be used once after each comparison")
    • return
    • response = validate_quicksort(original, xs)
    • passed = isinstance(response, bool)
    • debug_output = []
    • cmp_limit = float('inf')
    • if len(xs) < 101:
    • xs[:] = original[:]
    • debug_output.append("")
    • debug_output.append("initial array:")
    • debug_output.append(str(xs))
    • debug_output.append("")
    • def pos_in_str(idx):
    • if idx == 0: return 1
    • idx = len(str(xs[:idx])) + 1
    • return idx
    • for name, i, j in history[:]:
    • debug_output.append(f"{name}({i}, {j})")
    • xss = str(xs)
    • arrows = list(" " * len(xss))
    • arrows[pos_in_str(i)] = "↑" if i != j else "⇈"
    • if i != j:
    • arrows[pos_in_str(j)] = "↑"
    • arrows = "".join(arrows).rstrip()
    • debug_output.append(xss)
    • debug_output.append(arrows)
    • debug_output.append("")
    • if name == "swap":
    • swap(i, j)
    • else:
    • cmp(i, j)
    • test.expect(passed, str(response) + "\n" + "\n".join(debug_output))
    • def validate_quicksort(inputlist, userlist): ## Returns an error message or True
    • if not isinstance(userlist, list): return f"Not a list!"
    • if sorted(inputlist) != sorted(userlist): return f"contents of userlist don't match inputlist."
    • # if len(inputlist) > 100 and userlist == sorted(inputlist): return f"userlist is perfectly sorted, which is very unlikely to happen unless you used the library sorting method"
    • passed, errmsg = validate_quicksort(original, xs)
    • passed = passed and not (exceeded_cmp_budget or exceeded_swap_budget)
    • debug_output = render_history(history, original) if not passed else ""
    • if exceeded_cmp_budget:
    • test.fail(
    • f"too many comparisons: {len(xs)} are allowed,"
    • f" but you used {len(xs) + abs(cmp_budget)}"
    • f"{debug_output}"
    • )
    • elif exceeded_swap_budget:
    • test.fail(f"you made more than one swap between comparisons{debug_output}")
    • else:
    • test.expect(passed, errmsg + debug_output)
    • return passed
    • def validate_quicksort(inputlist, userlist) -> tuple[bool, str]:
    • if not isinstance(userlist, list):
    • return False, "Not a list!"
    • if sorted(inputlist) != sorted(userlist):
    • return False, "contents of userlist don't match inputlist."
    • if inputlist == []:
    • if userlist != []: return f"userlist should be []."
    • else: return True
    • if len(inputlist) < 20: ## Show lists if small
    • list_contents = f"Inputlist was {inputlist} and userlist was {userlist}. "
    • else: list_contents = ''
    • if userlist == []:
    • return True, ""
    • else:
    • return False, "userlist should be []."
    • pivot = inputlist[0]
    • pivot_found = greater_than_pivot = False
    • n = len(inputlist)
    • for i in range(n):
    • current = userlist[i]
    • if not pivot_found and current > pivot:
    • return f"{list_contents}Element {current} greater than pivot {pivot} found before pivot."
    • if pivot_found:
    • if current > pivot: greater_than_pivot = True
    • if greater_than_pivot and current <= pivot:
    • if current == pivot: return f"{list_contents}Element {current} equal to pivot {pivot} found after pivot."
    • else: return f"{list_contents}Element {current} less than pivot {pivot} found after pivot."
    • elif current < pivot:
    • return f"{list_contents}Element {current} less than pivot {pivot} found after pivot."
    • if current == pivot: pivot_found = True
    • i = 0
    • # less-than
    • for i, x in enumerate(userlist):
    • if x == pivot:
    • break
    • if x > pivot:
    • return False, f"{x} is greater than pivot {pivot} but was found before pivot."
    • # pivot
    • for i in range(i + 1, len(userlist)):
    • x = userlist[i]
    • if x != pivot:
    • break
    • if x < pivot:
    • return False, f"{x} is less than pivot {pivot} but was found after pivot."
    • # greater-than
    • for i in range(i + 1, len(userlist)):
    • x = userlist[i]
    • if x < pivot:
    • return False, f"{x} is less than to pivot {pivot} but was found after pivot."
    • if x == pivot:
    • return False, f"{x} is equal to pivot {pivot} but was found after pivot."
    • return True
    • return True, ""
    • @test.describe('Fixed Tests')
    • @test.describe("Fixed Tests")
    • def _():
    • tests = [
    • [5, 3, 9, 8, 2], ## General example
    • [2, 3, 9, 8, 5, 6], ## Pivot is smallest
    • [9, 8, 3, 5], ## Pivot is biggest
    • [2, 3, 9, 8, 0, 5, 6], ## Pivot is 2nd-smallest
    • [9, 8, 3, 5, 11], ## Pivot is 2nd-biggest
    • [5, 2, 9, 8, 5, 3, 1, 5], ## Pivot is duplicated
    • [5, 5, 5, 5, 5, 5, 5, 5], ## All duplicates
    • [5, 5, 5, 5, 5, 8, 5, 5], ## Duplicates plus 1 other
    • [5, 3, 5, 5, 5, 5, 8, 5], ## Duplicates plus 2 others
    • [5, 8, 5, 5, 8, 8, 5, 5], ## Duplicates plus 1 other duplicated
    • [5, 9, 3, 8, 2, 8, 1, 0, 11, 7, 5, 5, 8, 1, 12, 9, 999, 5, 8], ## Many duplicates
    • [], ## Empty list
    • [5], ## One-element list
    • [5, 3], ## Two-element list
    • [3, 5], ## Two-element list
    • [5, 5], ## Two-element list
    • [5, 8, 3], ## Three-element list
    • ]
    • for test in tests:
    • run_test(test)
    • @test.describe("Small Random Tests")
    • @test.describe("Random Tests")
    • def _():
    • for _ in range(25):
    • length = random.randint(3, 10)
    • failure_limit = 5
    • lengths = list(range(3, 20)) * 3
    • random.shuffle(lengths)
    • for length in lengths:
    • randomlist = [random.randint(1, 10) for _ in range(length)]
    • run_test(randomlist)
    • @test.describe("Bigger Random Tests")
    • def _():
    • for _ in range(20):
    • length = random.randint(10, 100000)
    • randomlist = [random.randint(1, 100) for _ in range(length)]
    • run_test(randomlist)
    • passed = run_test(randomlist)
    • if not passed:
    • failure_limit -= 1
    • if failure_limit < 1:
    • break