-
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)}" .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, "" .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) .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
Output:
-
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 = Truedisallowed_swap = disallowed_cmp = Falsecmp_count = 0cmp_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_cmpswap_allowed = Truecmp_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 sliceraise 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 = Trueraise 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_swapif not swap_allowed:disallowed_swap = Trueraise RuntimeError("You may only swap after making a comparison.")if type(i) is not int:# in particular, it should not be sliceraise 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")returnif disallowed_swap:test.fail("swap may only be used once after each comparison")returnresponse = 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 1idx = len(str(xs[:idx])) + 1return idxfor 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 Trueif 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 Trueif len(inputlist) < 20: ## Show lists if smalllist_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 = Falsen = 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 = Trueif 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
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
Please sign in or sign up to leave a comment.