#!/usr/bin/python3 # ksplang builder # autor: Jiří Sejkora # Tohle je zjednodušená verze (některé komplexní optimalizace jsem odstranil, aby bylo snazší pochopit, co se děje) # Co je to ksplang: https://ksp.mff.cuni.cz/viz/ksplang # # Pár instrukcí se jmenuje divně kvůli omezením v Pythonu: inc je ++, max2 je max, bitand je And, sumall je sum # Rozlišení mezi SimpleFunction a ComplexFunction je v této osekané verzi docela zbytečné, # ale pro komplexnější optimalizace se to hodí. Stejně tak pojmenovávání funkcí. # # Tento soubor si můžete interaktivně spustit: `python -i 3634.py` # a pak použít následující funkce pro vygenerování řešení (funguje tam doplňování TABem): # - `solve_seq()` - úkol 1 # - `solve_sort_min_max_nested_loops()` - úkol 2, 2 vnořené cykly, min/max (jako ve vzorovém řešení) # - `solve_sort_cmp_nested_loops()` - úkol 2, 2 vnořené cykly, CMP funkce # - `solve_sort_cmp_one_loop()`, - úkol 2, jeden cyklus od n^2-1 do 0, CMP funkce # - `solve_stacklen()` - úkol 3 # Taky si můžete vypsat libovolnou jednu či více funkcí jako ksplang, například: # - `evaluate(push(42))` # - `evaluate(dup)` # - `evaluate(permute("a b c", "b a c"))` # - `evaluate(DoWhileNonZero([dup, dec, dup]))` # - `evaluate([push(1), push(2), add])` import functools import itertools from abc import ABC from dataclasses import dataclass from typing import Union, Callable class ProgramBlock(ABC): """A building block of a ksplang program, anything from an instruction to a longer sequence of instructions, or a control flow construct.""" pass @dataclass class Instruction(ProgramBlock): """An individual ksplang instruction""" code: str def len(self) -> int: return 1 def expand(self) -> list['Instruction']: return [self] MIN = -9223372036854775808 MAX = 9223372036854775807 CS = Instruction("cs") inc = Instruction("++") pop = Instruction("pop") pop2 = Instruction("pop2") swap = Instruction("swap") tetr = Instruction("tetr") tetr2 = Instruction("^^") funkcia = Instruction("funkcia") lswap = Instruction("l-swap") modulo = Instruction("%") lensum = Instruction("lensum") REM = Instruction("rem") bitshift = Instruction("bitshift") qeq = Instruction("qeq") lroll = Instruction("lroll") u = Instruction("u") gcd = Instruction("gcd") d = Instruction("d") bitand = Instruction("and") praise = Instruction("praise") m = Instruction("m") brz = Instruction("brz") j = Instruction("j") call = Instruction("call") goto = Instruction("goto") bulkxor = Instruction("bulkxor") max2 = Instruction("max") sumall = Instruction("sum") instructions_by_raw = { "cs": CS, "++": inc, "pop": pop, "pop2": pop2, "swap": swap, "tetr": tetr, "^^": tetr2, "funkcia": funkcia, "l-swap": lswap, "%": modulo, "lensum": lensum, "rem": REM, "bitshift": bitshift, "qeq": qeq, "lroll": lroll, "u": u, "gcd": gcd, "d": d, "and": bitand, "praise": praise, "m": m, "brz": brz, "j": j, "call": call, "goto": goto, "bulkxor": bulkxor, "max": max2, } def instruction_from_str(s: str) -> Instruction: """Get an instruction from its name.""" return instructions_by_raw[s.lower()] @dataclass class SimpleFunction(ProgramBlock): """A simple function in the ksplang program, built out of multiple instructions or more simple functions. Can be placed anywhere in the program and will work.""" name: str blocks: list[Union[Instruction, "SimpleFunction"]] def len(self) -> int: return sum(block.len() for block in self.blocks) def expand(self) -> list[Instruction]: result = [] for block in self.blocks: result.extend(block.expand()) return result @functools.cache def push(n: int) -> SimpleFunction: if n > MAX: raise ValueError("n too large") if n < MIN: raise ValueError("n too small") if n == 0: # Requires a non-empty stack. # CS CS lensum will take any value down to 0-5 # CS duplicates it # funkcia turns two duplicates into 0 result = [CS, CS, lensum, CS, funkcia] elif 0 < n < 16: # We must handle n == 1 here. # Using repeated increments is not optimal, so we only do it for small numbers. # There is likely a better cutoff point than 16 if we wanted to optimize for length. result = [push(0), *([inc] * n)] elif n == MAX: # Significantly more efficient than building it out of 63 bitshifts. result = [push(MIN), push(1), add, push(0), subabs] elif n > 0: # We could just repeat `++`, but that is not viable for big numbers. # Instead, we build it out of powers of two and sum those up. result = [] nums = 0 for i in range(n.bit_length()): if n & (1 << i): result.append(push(1)) if i == 1: # We can duplicate the 1 by using m or CS result.append(m) else: result.append(push(i)) result.append(bitshift) nums += 1 for _ in range(nums - 1): result.append(add) elif n == MIN: result = [push(1), push(63), bitshift] elif n < 0: assert abs(n) <= MAX # x + c = 0 result = [push(abs(n)), negate] else: assert False return SimpleFunction(f"push({n})", result) class PaddingFailureError(Exception): pass def push_padded_to(n: int, op_count: int) -> SimpleFunction: """Pushes n to the stack using op_count operations""" push_f = push(n) ops = [push_f] # This cannot fit already. if push_f.len() > op_count: raise PaddingFailureError() if push_f.len() != op_count: # We need to pad, we can only do that with 2 or more instructions (CS pop) or (CS [++ ...] pop) if push_f.len() + 2 > op_count: raise PaddingFailureError() ops.append(CS) for _ in range(op_count - push_f.len() - 2): ops.append(inc) ops.append(pop) return SimpleFunction(f"push_padded_to({n}, {op_count})", ops) def roll(length: int, distance: int) -> SimpleFunction: result = [push(distance), push(length), lroll] return SimpleFunction(f"roll({length}, {distance})", result) @functools.cache def permute(before: str, after: str) -> SimpleFunction: """ :param before: Values in the original order separated by spaces e.g. "a b c" :param after: Values in the wanted order separated by spaces e.g. "b c a" """ before_values = before.split(" ") after_values = after.split(" ") assert len(before_values) == len(after_values), "Before and after must have the same length" assert len(set(before_values)) == len(before_values), "Before must not have duplicates" assert len(set(after_values)) == len(after_values), "After must not have duplicates" assert set(after_values).issubset(set(before_values)), "After must use values from before" permutation = [before_values.index(value) for value in after_values] # This is not exactly the smartest solution, but it works. # We try longer and longer sequences of valid rolls until # we find one that produces the correct permutation. possible_rolls = [] for length in range(1, len(permutation) + 1): for distance in range(1, length): possible_rolls.append((length, distance)) # This only guarantees minimal amount of rolls, # but it might not be the shortest instruction sequence. rolls = 0 while True: for sequence in itertools.combinations_with_replacement(possible_rolls, rolls): objects = list(range(len(permutation))) for length, distance in sequence: prefix = objects[:-length] end = objects[-length:] end = end[-distance:] + end[:-distance] objects = prefix + end if objects == permutation: ops = [] for length, distance in sequence: ops.append(roll(length, distance)) return SimpleFunction(f"permute({before}, {after})", ops) rolls += 1 swap2 = roll(2, 1) """a b -> b a""" add = SimpleFunction("add", [push(0), u]) """a b -> a + b""" subabs = SimpleFunction("subabs", [push(1), u]) """a b -> abs(a - b)""" mul = SimpleFunction("mul", [push(2), u]) """a b -> a * b""" curseddiv = SimpleFunction("curseddiv", [push(3), u]) """a b -> b % a == 0 ? b // a : b % a""" sgn = SimpleFunction("sgn", [push(5), u]) """a -> sgn(a)""" negate = SimpleFunction("negate", [push(1), CS, CS, modulo, qeq]) """a -> -a""" # Non-optimized version: # abs1 = SimpleFunction("abs1", [push(0), subabs]) abs1 = SimpleFunction("abs1", [push(0), CS, inc, u]) """ a -> abs(a) Crashes for a == MIN """ # Non-optimized version: # zero_not = SimpleFunction("zero_not", [sgn, abs1, push(1), CS, bulkxor]) zero_not = SimpleFunction("zero_not", [ # x sgn, # sgn(x) abs1, # |sgn(x)|, i.e. 0 or 1 CS, j, inc, # |sgn(x)| 1 CS, # |sgn(x)| 1 1 bulkxor ]) """a -> a == 0 ? 1 : 0""" dec = SimpleFunction("dec", [push(0), CS, inc, CS, qeq, u]) # Universal duplication by Erik S. with small push improvements by me # source: https://discord.com/channels/726020980107116585/782937605427560470/1201176544920490055 (KSP discord) # my push improvements: # a better push(-2^63) onto 0/-1 (confirmed optimal if starting with CS j ++) # a better push(3) onto -2^63/2^63-1 (confirmed optimal) dup = SimpleFunction( "dup", [ push(0), push(3), m, # x 0 3 clamp(x, 0-3) CS, CS, inc, gcd, inc, # push(2) onto 0-3 # x 0 3 clamp(x, 0-3) 2 max2, # x 0 3 clamp(x, 2-3) CS, CS, modulo, # push(0) onto 2-3 # x 0 3 clamp(x, 2-3) 0 qeq, # now different things happen for 2/3 # x 0 OR x 0 -1 CS, CS, CS, inc, inc, # push 0 0 2 / 1 1 3 # x 0 0 0 2 OR x 0 -1 1 1 3 qeq, # x 0 0 OR x 0 -1 pop2, # x 0 OR x -1 # With the CS j inc prefix, there is no better suffix, # we checked all 9 instruction suffixes and none produce -2^63 (this one is 10 instructions) CS, j, inc, CS, praise, qeq, qeq, pop2, funkcia, funkcia, inc, modulo, bitshift, # push -2^63 onto 0/-1 # x 0 -2^63 OR x -1 -2^63 CS, CS, gcd, # push 1 onto -2^63 CS, inc, # push 2 onto 1 lroll, # roll(2, 1) # x -2^63 0 OR x -2^63 -1 CS, # x -2^63 0 0 OR x -2^63 -1 1 u, # x -2^63 OR x 2^63-1 # There are 12 ways to push 3 onto -2^63/2^63-1 in 5 instructions CS, CS, pop2, CS, lensum, # push 3 onto -2^63/2^63-1 # x<=2 -2^63 3 OR x>=3 2^63-1 3 m, # x -2^63 3 x OR x 2^63-1 3 x pop2, pop2 # x x ] ) # 32-bit duplication by donavan # source: https://discord.com/channels/726020980107116585/782937605427560470/1193878386687344640 (KSP discord) dup32bit = SimpleFunction( "dup32bit", [instruction_from_str(x.lower()) for x in "cs cs lensum ++ cs lensum ++ cs ^^ cs cs lensum m cs cs lensum cs lensum ++ % cs u cs bitshift ++ bitshift cs cs lensum m pop2 pop2".split( " ")] ) dup_ab = SimpleFunction("dup_ab", [ # a b dup, # a b b roll(3, 2), # b b a dup, # b b a a roll(4, 1), # a b b a roll(2, 1), # a b a b ]) """a b -> a b a b""" dup_abc = SimpleFunction("dup_abc", [ # Almost surely not optimal. # a b c dup_ab, # a b c b c roll(5, 4), # b c b c a dup, # b c b c a a permute("b1 c1 b2 c2 a1 a2", "a1 b1 c1 a2 b2 c2"), ]) load = SimpleFunction("load", [ # n dup, # n n # We need to push something there temporarily, # so we just use CS as that is efficient. CS, # n n CS(n) roll(2, 1), # n CS(n) n swap, # n s[n] dup, # n s[n] s[n] roll(3, 2), # s[n] s[n] n swap, # s[n] CS(n) pop # s[n] ]) """n -> s[n]; s[n] stays s[n] (expensive, if not needed, use load_destructive)""" load_destructive = SimpleFunction("load_destructive", [ # n CS, # n X swap2, # X n swap, # s[n] = CS(n) # s[x] ]) """n -> s[n]; s[n] = CS(n)""" store = SimpleFunction("store", [swap, pop]) """a i -> s[i] = a""" def dup_nth_zero_indexed(n: int) -> SimpleFunction: """ dup_nth_zero_indexed(0) = a -> a a dup_nth_zero_indexed(1) = a b -> a b a dup_nth_zero_indexed(2) = a b c -> a b c a """ assert n >= 0 return SimpleFunction(f"dup_nth_zero_indexed({n})", [ # a [...] roll(n + 1, n), # [...] a dup, # [...] a a roll(n + 2, 1) # a [...] a ]) dup_second = dup_nth_zero_indexed(1) """a b -> a b a""" dup_third = dup_nth_zero_indexed(2) """a b c -> a b c a""" dup_fourth = dup_nth_zero_indexed(3) """a b c d -> a b c d a""" dup_fifth = dup_nth_zero_indexed(4) """a b c d e -> a b c d e a""" dup_sixth = dup_nth_zero_indexed(5) """a b c d e f -> a b c d e f a""" @dataclass class DoWhileNonZero(ProgramBlock): """A do-while loop that runs while the top of the stack is non-zero. Consumes the checked value.""" blocks: list[ProgramBlock] @dataclass class DoNTimes(ProgramBlock): """ A do-while loop that runs N times. Expects one value N >= 1 on top of the stack before running. At the start of each iteration this is the top of the stack, and must stay the top of the stack at the end. This value is decremented at the start of the loop (last loop has this value as 0), do not decrement it yourself. Especially useful without stack data (pushing N zeros, popping N values). """ blocks: list[ProgramBlock] @dataclass class DoWhileZero(ProgramBlock): """A do-while loop that runs while the top of the stack is zero. Consumes the checked value.""" blocks: list[ProgramBlock] @dataclass class IfZero(ProgramBlock): """An if-else construct that runs the first block if the top of the stack is zero, the second otherwise. Does not consume the top value before the blocks run.""" then: list[ProgramBlock] otherwise: Union[list[ProgramBlock], None] @dataclass class ComplexFunction(ProgramBlock): """A function that may use prepared control flow blocks that are not SimpleFunctions""" name: str blocks: list[ProgramBlock] cmp = ComplexFunction("cmp", [ dup_ab, # a b a b sgn, # a b a sgn(b) roll(2, 1), # a b sgn(b) a sgn, # a b sgn(b) sgn(a) roll(2, 1), # a b sgn(a) sgn(b) negate, add, # a b sgn(a)-sgn(b) IfZero( then=[ pop, # a b dup_ab, # a b a b # We need to ensure that if b is MIN, we do not negate it. We just add -sgn() to both a and b, # that does not change the result. dup, sgn, negate, add, # a b a b-sgn(b) negate, # a b a -(b-sgn(b)) roll(2, 1), # a b -(b-sgn(b)) a dup, sgn, negate, add, # a b -(b-sgn(b)) a-sgn(a) add, # a and b have the same sign -> this is never more than 2**63-1 # a b a-b sgn, # a b sgn(a-b) ], otherwise=[ sgn, # a b sgn(sgn(a)-sgn(b)) ] ), # a b sgn(a-b) pop2, pop2 ]) """A comparison of two values on the stack. Handles all i64 values. a > b => 1 a < b => -1 a == b => 0 Signature: a b => sgn(a-b) """ find_unsafe = ComplexFunction(f"find_unsafe", [ # i a swap2, # a i DoWhileZero([ # a i dup, # a i i load, # a i s[i] dup_third, # a i s[i] a cmp, # a i CMP(s[i]==a) zero_not, # a i s[i]==a?1:0 swap2, inc, swap2 # a i+1 s[i]==a?1:0 ]), # a i+1 dec, # a i pop2, # i ]) """ Finds the first instance of a value from a given index (inclusive). If the value does not exist, this will behave unpredictably (crash or wrong results). If i is outside of the stack, this will crash. Signature: i a -> first(s[i] == a) """ div = SimpleFunction('real_div', [ # a b dup_ab, # a b a b REM, # a b b%a negate, # a b -b%a add, # a b-b%a curseddiv ]) """a b -> b/a""" stacklen = ComplexFunction("stacklen", [ push(0), # 0 # i DoWhileZero([ # i push(0), # i 0 swap2, # 0 i dup, # 0 i i load, # 0 i s[i] zero_not, # 0 i s[i]==0 roll(3, 2), # i s[i]==0 0 inc, # i s[i]==0 1 roll(3, 1), # 1 i s[i]==0 swap2, # 1 s[i]==0 i dup, # 1 s[i]==0 i i load, # Now we want to check if this is a 1, thankfully # it is enough to check the number is not a zero # 1 s[i]==0 i s[i] zero_not, # 1 s[i]==0 i s[i]==0 zero_not, # 1 s[i]==0 i s[i]!=0 roll(3, 2), # 1 i s[i]!=0 s[i]==0 bitand, # 1 i (s[i]!=0&s[i]==0) roll(3, 1), # (s[i]!=0&s[i]==0) 1 i inc, # (s[i]!=0&s[i]==0) 1 i+1 pop2, # (s[i]!=0&s[i]==0) i+1 roll(2, 1), # i+1 (s[i]!=0&s[i]==0) ]), dec, ]) @dataclass(eq=False) class PreparedPush: index: int setter: Callable[['PreparedPush', int, int], None] padding: int invalidated: bool = False def set(self, n: int): if self.invalidated: raise ValueError("This push was already set") self.setter(self, n, self.padding) self.invalidated = True def set_for_jump(self, n: int): """Convenience method for when this push is used right before a jump.""" self.set(n - self.index_after() - 1) def index_end(self) -> int: return self.index + self.padding - 1 def index_after(self) -> int: return self.index + self.padding class Builder: """A class for building ksplang programs. Use the methods to build up a program, then call .build() to get the program as a list of instructions.""" def __init__(self): self.blocks = [] self.enable_push_optimizations = True def append(self, block: Union[ProgramBlock, list[ProgramBlock]]): """Append a block or a list of blocks to the program.""" if isinstance(block, list): self.blocks.extend(block) else: self.blocks.append(block) def build(self) -> str: """Build the program and return it as a list of instructions.""" # We use a global address padding for simplification for now. for address_pad in itertools.count(6): try: index = 0 program = [] prepared_pushes = [] def apply_prepared_push(push: PreparedPush, n: int, padding: int): index = program.index(push) padded_push = push_padded_to(n, padding) assert isinstance(padded_push, SimpleFunction) program[index:index + 1] = " ".join((instr.code for instr in padded_push.expand())) + " " def prepare_padded_push(padding: Union[int, None] = None) -> PreparedPush: nonlocal index if padding is None: padding = address_pad push = PreparedPush(index, apply_prepared_push, padding) program.append(push) index += padding prepared_pushes.append(push) return push # Expand a block (can be used recursively) def e(block: ProgramBlock): nonlocal index if isinstance(block, Instruction): # Individual instructions index += 1 program.append(block.code) program.append(" ") elif isinstance(block, SimpleFunction): # Simple functions with a set length for instruction in block.blocks: e(instruction) elif isinstance(block, ComplexFunction): for child in block.blocks: e(child) elif isinstance(block, DoWhileNonZero): e(CS) e(CS) redo_index = index e(pop) e(pop) for b in block.blocks: e(b) e(zero_not) e(push(redo_index)) e(roll(2, 1)) e(brz) e(pop2) e(pop) elif isinstance(block, DoWhileZero): e(CS) e(CS) redo_index = index e(pop) e(pop) for block in block.blocks: e(block) e(push(redo_index)) e(roll(2, 1)) e(brz) e(pop2) e(pop) elif isinstance(block, IfZero): if block.otherwise is None: # We can specialize raise NotImplementedError() then_push = prepare_padded_push() e(roll(2, 1)) e(brz) e(pop2) otherwise_j_push = prepare_padded_push() e(j) then_push.set(index) e(pop2) for b in block.then: e(b) end_j_push = prepare_padded_push() e(j) otherwise_j_push.set_for_jump(index) e(pop) for b in block.otherwise: e(b) e(CS) end_j_push.set_for_jump(index) e(pop) elif isinstance(block, DoNTimes): e(DoWhileNonZero([ *block.blocks, dec, CS, ])) e(pop) else: assert False for i, block in enumerate(self.blocks): e(block) return "".join(program) except PaddingFailureError: # We need to try again with a bigger padding pass # Produce a sequence (descending) (https://ksp.mff.cuni.cz/viz/36-3-4, task 1) # k -> k k-1 ... 0 def solve_seq(): b = Builder() b.append([ # k DoWhileNonZero([ # i dup, # i i dec, # i i-1 dup, # i i-1 i-1 # ^ end if zero ]), ]) print(b.build()) # Sort a sequence of numbers in place (https://ksp.mff.cuni.cz/viz/36-3-4, task 2) # sorting algorithm: https://arxiv.org/abs/2110.01111 # loops: n^2-1 to 0, calculating indices i and j with mod and div # swapping approach: CMP function and an IfZero condition def solve_sort_cmp_one_loop(): b = Builder() b.append([ # k dup, dup, # k k k mul, # k k*k DoWhileNonZero([ # k i dec, # k i-1 dup_ab, dup_ab, # k i-1 k i-1 k i-1 modulo, # k i-1 k i-1 mod dup, # k i-1 k i-1 mod mod roll(4, 1), # k i-1 mod k i-1 mod subabs, # k i-1 mod k (i-1)-mod curseddiv, # k i-1 mod div dup_ab, # k i-1 mod div mod div load, # k i-1 mod div mod s[div] swap2, # k i-1 mod div s[div] mod load_destructive, # k i-1 mod div s[div] s[mod] dup_ab, # k i-1 mod div s[div] s[mod] s[div] s[mod] cmp, # k i-1 mod div s[div] s[mod] CMP(s[div],s[mod]) # swap if s[div] >= s[mod] inc, IfZero( then=[ pop, ], otherwise=[ pop, swap2, ] ), # k i-1 mod div lesser greater roll(4, 1), # k i-1 greater mod div lesser swap2, # k i-1 greater mod lesser div store, # s[div] = lesser # k i-1 greater mod store, # s[mod] = greater # k i-1 dup, # k i-1 i-1 # ^ end if this is zero ]), # k 0 pop, pop ]) print(b.build()) # Sort a sequence of numbers in place (https://ksp.mff.cuni.cz/viz/36-3-4, task 2) # sorting algorithm: https://arxiv.org/abs/2110.01111 # loops: two from n-1 to 0, nested # swapping approach: CMP function and an IfZero condition def solve_sort_cmp_nested_loops(): b = Builder() b.append([ # k dup, # k k DoWhileNonZero([ # k i+1 dec, dup_second, # k i k DoWhileNonZero([ # k i j+1 dec, # k i j dup_ab, dup_ab, # k i j i j i j # This load must not be destructive as i could be equal to j: load, # k i j i j i s[j] swap2, # k i j i j s[j] i load_destructive, # k i j i j s[j] s[i] dup_ab, cmp, # k i j i j s[j] s[i] CMP(s[j],s[i]) # swap if s[j] < s[i] inc, IfZero( then=[ pop, swap2, ], otherwise=[ pop, ] ), # k i j i j lesser greater roll(4, 1), # k i j greater i j lesser swap2, # k i j greater i lesser j store, # s[j] = lesser # k i j greater i store, # s[i] = greater # k i j CS, # k i j CS(j) ]), # k i 0 pop, # k i CS # k i CS(i) ]), # k 0 pop, pop ]) print(b.build()) subtract_sgn = SimpleFunction("subtract_sgn", [ # a dup, # a a sgn, # a sgn(a) negate, # a -sgn(a) add, # a-sgn(a) ]) # min(a, b) # Branchless version of min(a, b) relying on a median. min2_m = SimpleFunction("min2_m", [ # a b push(MIN), push(MIN), push(5), # a b MIN MIN 5 m, # a b MIN MIN 5 median # median is: # if both a, b > 5, then 5 # otherwise the correct min pop2, pop2, pop2, # a b median dup, # a b median median push(4), max2, # a b median max(median, 4) # max(median, 4) is: # if both a, b > 5, then 5 # otherwise: 4 # We can now subtract 4 to make it into a boolean flag push(4), negate, add, # a b median flag # flag: # 0 if median is correct # 1 if we want to use -max(-(a-sgn(a)), -(b-sgn(b)) + 1 roll(4, 3), # b median flag a subtract_sgn, # b median flag a-sgn(a) negate, # b median flag -(a-sgn(a)) roll(4, 3), # median flag -(a-sgn(a)) b subtract_sgn, # median flag -(a-sgn(a)) b-sgn(b) negate, # median flag -(a-sgn(a)) -(b-sgn(b)) max2, # median flag max(-(a-sgn(a)),-(b-sgn(b))) negate, # median flag -max(-(a-sgn(a)),-(b-sgn(b))) inc, # median flag -max(-(a-sgn(a)),-(b-sgn(b)))+1 dup_second, # median flag -max(-(a-sgn(a)),-(b-sgn(b)))+1 flag mul, # median flag (-max(-(a-sgn(a)),-(b-sgn(b)))+1)*flag roll(3, 1), # (-max(-(a-sgn(a)),-(b-sgn(b)))+1)*flag median flag push(1), subabs, # (-max(-(a-sgn(a)),-(b-sgn(b)))+1)*flag median 1-flag mul, # (-max(-(a-sgn(a)),-(b-sgn(b)))+1)*flag median*(1-flag) add, # ((-max(-(a-sgn(a)),-(b-sgn(b)))+1)*flag)+median*(1-flag) ]) is_MIN = SimpleFunction("is_MIN", [ # a dup, # a a sgn, # a sgn(a) subabs, # |a-sgn(a)| push(MAX), subabs, # ||a-sgn(a)|-MAX| zero_not, # 1 if is MIN, else 0 ]) """ a -> a == MIN 1 if a == -2^63, else 0""" # min(a, b) # Branchless version of min(a, b) relying on an a == MIN || b == MIN check. # Idea by SL # flag = a == MIN || b == MIN # # a = (1-flag) * a # b = (1-flag) * b # # result = -max(-a, -b) # result = result + flag * MIN min2_sl = SimpleFunction("min2_sl", [ # a b dup, # a b b is_MIN, # a b (b==MIN?1:0) dup_third, # a b (b==MIN?1:0) a is_MIN, # a b (b==MIN?1:0) (a==MIN?1:0) add, # a b (b==MIN?1:0)+(a==MIN?1:0) zero_not, zero_not, # a b b==MIN||a==MIN # a b flag dup, # a b flag flag roll(3, 1), # a flag b flag push(1), subabs, # a flag b (1-flag) mul, # a flag (1-flag)*b roll(3, 2), # flag (1-flag)*b a dup_third, # flag (1-flag)*b a flag push(1), subabs, mul, # flag (1-flag)*b (1-flag)*a negate, swap2, negate, max2, negate, # flag -max(-(1-flag)*b,-(1-flag)*a) swap2, # -max(-(1-flag)*b,-(1-flag)*a) flag push(MIN), mul, # -max(-(1-flag)*b,-(1-flag)*a) flag*MIN add, # -max(-(1-flag)*b,-(1-flag)*a)+flag*MIN ]) # min(a, b) # Uses a condition to check if there is -2^63, if there is, then it returns -2^63, # otherwise it returns -max(-a, -b) min2_conditional = ComplexFunction("min2_conditional", [ # a b dup, is_MIN, zero_not, # a b b!=MIN roll(3, 2), # b b!=MIN a dup, is_MIN, zero_not, # b b!=MIN a a!=MIN swap2, # b b!=MIN a!=MIN a roll(4, 1), # a b b!=MIN a!=MIN bitand, # a b b!=MIN&a!=MIN IfZero( then=[ # a b 0 pop, # a b push(MIN), # a b MIN pop2, pop2, # MIN ], otherwise=[ # a b 1 pop, # a b negate, swap2, negate, # -b -a max2, negate # -max(-b,-a) ] ) ]) # Sort a sequence of numbers in place (https://ksp.mff.cuni.cz/viz/36-3-4, task 2) # sorting algorithm: https://arxiv.org/abs/2110.01111 # loops: two from n-1 to 0, nested # swapping approach: min and max functions (using a conditional version of min) def solve_sort_min_max_nested_loops(): b = Builder() b.append([ # k dup, # k k DoWhileNonZero([ # k i+1 dec, dup_second, # k i k DoWhileNonZero([ # k i j+1 dec, # k i j dup_ab, dup_ab, # k i j i j i j # This load must not be destructive as i could be equal to j: load, # k i j i j i s[j] swap2, # k i j i j s[j] i load_destructive, # k i j i j s[j] s[i] dup_ab, min2_conditional, # k i j i j s[j] s[i] min(s[j], s[i]) roll(3, 1), # k i j i j min(s[j], s[i]) s[j] s[i] max2, # k i j i j min(s[j], s[i]) max(s[j],s[i]) swap2, # k i j i j greater lesser roll(4, 1), # k i j lesser i j greater swap2, # k i j lesser i greater j store, # s[j] = greater # k i j lesser i store, # s[i] = lesser # k i j CS, # k i j CS(j) ]), # k i 0 pop, # k i CS # k i CS(i) ]), # k 0 pop, pop ]) print(b.build()) # Count the numbers on the stack (https://ksp.mff.cuni.cz/viz/36-3-4, task 3) def solve_stacklen(): b = Builder() b.append([ push(0), # 0 # i DoWhileZero([ # i push(0), # i 0 swap2, # 0 i dup, # 0 i i load, # 0 i s[i] zero_not, # 0 i s[i]==0 roll(3, 2), # i s[i]==0 0 inc, # i s[i]==0 1 roll(3, 1), # 1 i s[i]==0 swap2, # 1 s[i]==0 i dup, # 1 s[i]==0 i i load, # Now we want to check if this is a 1 OR it's not a zero # 1 s[i]==0 i s[i] zero_not, # 1 s[i]==0 i s[i]==0 zero_not, # 1 s[i]==0 i s[i]!=0 roll(3, 2), # 1 i s[i]!=0 s[i]==0 bitand, # 1 i (s[i]!=0&s[i]==0) roll(3, 1), # (s[i]!=0&s[i]==0) 1 i inc, # (s[i]!=0&s[i]==0) 1 i+1 pop2, # (s[i]!=0&s[i]==0) i+1 roll(2, 1), # i+1 (s[i]!=0&s[i]==0) ]), dec, ]) print(b.build()) # You can use this to test any functions on their own # run `python -i 3634.py` and then type evaluate(), for example evaluate(min2_m). # Tab completion should work there. def evaluate(p: Union[ProgramBlock, list[ProgramBlock]]): b = Builder() b.append(p) print(b.build())