We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

HQ0-9+-INCOMPUTABLE?!, ^{(削除) 1577 (削除ここまで)...(削除) 1010 (削除ここまで)} 771 points

ho3ochhhhh?9h?9hhhh?6h???????3h???3hhh????6?????????ciiiihhhhh?iiiiiiiiinc3hh?????chhhhh?ihhhhh?iiiiiiiiiiiinc2hhh???hhhhh?chhhhh?ciiihhhhh?iiiiiiiiiinhhhhh?hhhhh?2h???4hhhhhh??????????2hhhhhh????chhhhh?ciiihhhhh?iiiiiiiiiin4h??????????chhhhh?c2hhhh????4h???????????chhhhh?chhhhh?iiihhhhh?iiiiiiiiiinchhhhh?hhhhh?iiihhhhh?iiiiiiiiiinhhhhh?chhhhhhhhhhhhhhhhhhh????chhhhh?ciiihhhhh?iiiiiiiiiinhhhhh?hhhhh?2hhh?????5hhhhh???????????????????iiihhhhh?iiiiiiiiiinchhhhh?iiihhhhh?ihhhhh?iiiiiiiiinchhhhh?hhhhh?2h?????2h?????hhhhhhhhhhhhhhhhhhh????iihhhhh?iiiiiiiiiiinhhhhh?ciiihhhhhhhhhhhhhhhhhhh????iiiiiiiiiinhhhhh?iiihhhhh?iiiiiiiiiinc3h???????????2h??????chhhhh?ciiiihhhhh?iiiiiiiiinhhhhh?hhhhh?2??????2hhh???????ciiihhhhh?iiiiiiiiiinchhhhh?2??????hhhhh?aoppoopppponnnnnnnnn

Try it online!

This mostly extends @dingledooper approach; differences:

• uses both o and p operation
• allows constructing rot13 of the solution the transforming it back
• uses 2-9 (multiplication) in the middle of the solution

Things that are tuned by hand:

• currently there are occurrences of i...ini...i in the result which can be shortened by hand
• the end of the sequence can usually be optimized manually since we are no longer restricted to characters in a-fA-F

Code used for generation:

import itertools
import codecs
def prime_sieve(n):
 """returns a sieve of primes >= 5 and < n"""
 flag = n % 6 == 2
 sieve = bytearray((n // 3 + flag >> 3) + 1)
 for i in range(1, int(n**0.5) // 3 + 1):
 if not (sieve[i >> 3] >> (i & 7)) & 1:
 k = (3 * i + 1) | 1
 for j in range(k * k // 3, n // 3 + flag, 2 * k):
 sieve[j >> 3] |= 1 << (j & 7)
 for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
 sieve[j >> 3] |= 1 << (j & 7)
 return sieve
def prime_list(n):
 """returns a list of primes <= n"""
 res = []
 if n > 1:
 res.append(2)
 if n > 2:
 res.append(3)
 if n > 4:
 sieve = prime_sieve(n + 1)
 res.extend(3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)
 return res
should_remove = set(prime_list(10**7) + [2**i for i in range(24)]).__contains__
def run(prog, MAX_BUFFER_SIZE=10000):
 buffer = []
 for char in prog:
 if char == "h":
 buffer.extend("helloworld")
 elif char == "n":
 buffer = [str((int(c) + 3) % 10) if c.isdigit() else codecs.encode(c, 'rot13') for c in buffer]
 elif char.isdigit():
 buffer *= int(char)
 elif char == "i":
 buffer = [chr(ord(c) + 1) for c in buffer]
 elif char == "c":
 buffer = [c.swapcase() for c in buffer]
 elif char == "o":
 buffer = [c for i, c in enumerate(buffer) if not should_remove(len(buffer) - i)]
 elif char == "p":
 buffer = [c for i, c in enumerate(buffer) if not should_remove(i + 1)]
 elif char == "u":
 buffer = [c.upper() for c in buffer]
 elif char == "a":
 buffer = [i for c in buffer for i in str(ord(c))]
 elif char == "b":
 buffer = [i for c in buffer for i in f"{ord(c):08b}"]
 elif char == "l":
 buffer = [c.lower() for c in buffer]
 elif char == "?":
 buffer = buffer[:-47]
 elif char == "!":
 buffer = buffer[47:]
 if len(buffer) > MAX_BUFFER_SIZE:
 return ""
 return "".join(buffer)
def solve(pattern, programs, start_programs):
 dp = [""] * (len(pattern) + 1)
 data = [""] * (len(pattern) + 1)
 for word, (prog, text) in start_programs.items():
 if (
 len(word) < len(dp)
 and (dp[len(word)] == "" or len(prog) <= len(dp[len(word)]))
 and all(i == "." or i == j for i, j in zip(pattern[:len(word)], word))
 ):
 dp[len(word)] = prog
 data[len(word)] = text
 for i in range(len(pattern)):
 if dp[i] == "" and i != 0:
 continue
 for word, (prog, text) in programs.items():
 if (
 i + len(word) < len(dp)
 and (dp[i + len(word)] == "" or len(dp[i]) + len(prog) <= len(dp[i + len(word)]))
 and all(j == "." or j == k for j, k in zip(pattern[i : i + len(word)], word))
 ):
 dp[i + len(word)] = (dp[i] + prog).replace("cc", "")
 data[i + len(word)] = data[i] + text
 pattern[i : i + len(word)]
 for j in range(i + 1, min(i + 100, len(pattern))):
 best = ""
 for k in range(1, 9):
 h = (33 * ((j - i) - len(data[i]) * k)) % 47
 r = ((len(data[i]) * k + 10 * h) - (j - i)) // 47
 if h * 10 < r * 47 and (best == "" or 1 + h + r < len(best)):
 best = f"{k + 1}{'h' * h}{'?' * r}"
 if best:
 text = (data[i] * int(best[0]))[:j - i]
 word = "".join(str(ord(k)) for k in text)
 if (
 i + len(word) < len(dp)
 and (dp[i + len(word)] == "" or len(dp[i]) + len(best) < len(dp[i + len(word)]))
 and all(j == "." or j == k for j, k in zip(pattern[i : i + len(word)], word))
 ):
 dp[i + len(word)] = dp[i] + best
 data[i + len(word)] = data[i] + text
 data[i + len(word)] = data[i] + text
 return dp[-1]
def expand_program(base, output):
 expanded = {}
 for i in range(ord(min(output)) - ord('a') + 1):
 expanded["".join(str(ord(j) - i) for j in output)] = (
 f"{'i' * i}{base}{'i' * (-i % 13)}{'n' if i else ''}",
 "".join(chr(ord(j) - i) for j in output),
 )
 expanded["".join(str(ord(j) - i) for j in output.upper())] = (
 f"c{'i' * i}{base}{'i' * (-i % 13)}{'n' if i else ''}c",
 "".join(chr(ord(j) - i) for j in output.upper()),
 )
 return expanded
def generate_start():
 start_programs = {}
 for prog in itertools.product(["", *"h23456789?!poctin"], repeat=4):
 if (text := run(prog := "h" + "".join(prog))) and all(i < 'm' for i in text.lower()):
 output = "".join(str(ord(i)) for i in text)
 if output not in start_programs or len(prog) < len(start_programs[output]):
 start_programs[output] = (prog, text)
 return start_programs
def sparse_p(s):
 s.reverse()
 return ['.' if should_remove(i + 1) else s.pop() for i in range(10 * len(s)) if s]
def sparse_o(s):
 s.reverse()
 return sparse_p(s)[::-1]
start_programs = generate_start()
programs = {
 **expand_program("hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh???????", "h"),
 **expand_program("hhhhhhhhhhhhhhhhhhh????", "he"),
 **expand_program("hhhhh?", "hel"),
 **expand_program("hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh????????", "hell"),
}
target = "14159265358979323846264338327950288419716939937510"
best = float('inf')
for i in range(10):
 pseudo_target = "".join(str((int(j) - 3 * i) % 10) for j in target)
 for size in range(9, 11):
 print(i, size)
 for operations in range(1 << size):
 sparse_target = list(pseudo_target)
 prog = ["n"] * (size + i)
 for j in reversed(range(size)):
 sparse_target = [sparse_o, sparse_p][operations & 1](sparse_target)
 prog[j] = "op"[operations & 1]
 operations >>= 1
 if solution := solve(sparse_target, programs, start_programs):
 prog = f"{solution}a{''.join(prog)}"
 if len(prog) < best:
 best = len(prog)
 print(prog, len(prog))
 assert run(prog) == target