# 50 digits of π in HQ0-9+-INCOMPUTABLE?

## Background

HQ0-9+-INCOMPUTABLE?! is a half-joke programming language introduced in Internet Problem Solving Contest 2011, Problem H.

HQ9+ is an esoteric programming language specialized for certain tasks. For example, printing “Hello, world!” or writing a quine (a program that prints itself) couldn’t be any simpler. Unfortunately, HQ9+ doesn’t do very well in most other situations. This is why we have created our own variant of the language, HQ0-9+-INCOMPUTABLE?!.

A HQ0-9+-INCOMPUTABLE?! program is a sequence of commands, written on one line without any whitespace (except for the trailing newline). The program can store data in two memory areas: the buffer, a string of characters, and the accumulator, an integer variable. Initially, the buffer is empty and the accumulator is set to 0. The value of the buffer after executing all the commands becomes the program’s output.

HQ0-9+-INCOMPUTABLE?! supports the following commands:

command description
h, H appends helloworld to the buffer
q, Q appends the program source code to the buffer (not including the trailing newline)
0-9 replaces the buffer with n copies of its old value – for example, 2 doubles the buffer (aab would become aabaab, etc.)
+ increments the accumulator
- decrements the accumulator
i, I increments the ASCII value of every character in the buffer
n, N applies ROT13 to the letters and numbers in the buffer (for letters ROT13 preserves case; for digits we define ROT13(d) = (d + 13) mod 10)
c, C swaps the case of every letter in the buffer; doesn’t change other characters
o, O removes all characters from the buffer whose index, counted from the end, is a prime or a power of two (or both); the last character has index 1 (which is a power of 2)
m, M sets the accumulator to the current buffer length
p, P removes all characters from the buffer whose index is a prime or a power of two (or both); the first character has index 1 (which is a power of 2)
u, U converts the buffer to uppercase
t, T sorts the characters in the buffer by their ASCII values
a, A replaces every character in the buffer with its ASCII value in decimal (1–3 digits)
b, B replaces every character in the buffer with its ASCII value in binary (exactly eight 0/1 characters)
l, L converts the buffer to lowercase
e, E translates every character in the buffer to l33t using the following table:
ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 0123456789
48(03=6#|JXLM~09Q257UVW%Y2 a6<d3f9hijk1m^0p9r57uvw*y2 O!ZEA$G/B9 ? removes 47 characters from the end of the buffer (or everything if it is too short) ! removes 47 characters from the beginning of the buffer (or everything if it is too short) To prevent code injection vulnerabilities, during the execution of your program the buffer must never contain non-alphanumeric characters, i.e. characters other than A-Z, a-z, and 0-9. Should this happen, the program fails with a runtime error, and your submission will be rejected. The original problem statement contains limits about the code length and buffer length, but I removed them in this challenge. This is also reflected in the interpreter link below. (If you need even larger buffer, you can change the MAX_BUFFER constant near the top. I doubt using a longer buffer will give reasonably short code though.) ## Task Output the string (which is 50 digits of Pi without leading 3.) 14159265358979323846264338327950288419716939937510  in HQ0-9+-INCOMPUTABLE?!. An answer is scored as follows: • Each occurrence of Q/q adds 1,000,000 points. • Each occurrence of E/e adds 10,000 points. • Each occurrence of any other valid command adds 1 point. Lowest score wins. Bonus: +500 bounty to the first answer that achieves the score of 9,999 points or lower. I have confirmed that this is possible. claimed by dingledooper C++ interpreter If you're wondering about the role of the accumulator, you're right: it still does nothing useful. • I wonder what happened to "99 bottles of beer on the wall" Commented Nov 14, 2022 at 4:58 • @py3_and_c_programmer It was deemed the most useless of the four operations, and was superseded by "replace the buffer with 9 copies of its old value" :P Commented Nov 14, 2022 at 5:08 • Most useless? I'd have Q removed as it's not even an exact quine. Commented Nov 14, 2022 at 5:20 • @Pacmanboss256 > If you're wondering about the role of the accumulator, you're right: it still does nothing useful. Commented Nov 14, 2022 at 15:11 • @DanielSchepler Seems like it. Commented Nov 14, 2022 at 21:22 ## 5 Answers # HQ0-9+-INCOMPUTABLE?!, 788451344122 806 points Thanks to @JonathanAllan for suggesting using n in the pool code Thanks to @Neil for suggesting being looser with the pool and using strings instead of char code arrays hahaha!!4?????3?????????h?2!!????2!!!h?2!!!2!!!!!hh2????2???2hhhhh?hhh2!!!!!!!!h?2!!?????!6!!!!!!!!!!!!hhh?hhhhh?hhhh?2!!?????!!2hhhhh?3!!!!!!hhhh?2??2!hh2????2???h?2!???!2hhhh?2!!!h3??????hh?2!??!2!h?3!!!2?2!hhhh?hhh2!!!h?2!!h2??h2??h?2?!6!!!!!!!h?2!!2!?4!!!!h?2?h?2??2?!2!3!!!!!3!!!!h?5????2?h?2?2hhhhh?2!!!h2!!2??2?2!hhh?hhh2!!!hh?hhhh2????2??!2h2!!!hhhh?hhhh?2??!2!3!!!2!!3???2??2?6????????2!???!2!hhh2!!!h?3!!!!!3????h3??????2?!2h?2!!!2!!!!hh2!!!hh?2!??2hh3!!!!!!!!hh?h2??2???h?2??!2hhhh?2!??2!hh2!!!!h?hhhh?2??!2!2!!hhhh?2?4???h2???2???2!??2hh?2!!!!2!!!!!hhhh2?????2!???!2!4!!!!!2!!!3???h?2?2!!hh?2!!2??2?!2h?hhh2!!!!3??????h?2!??2hhhh?2!!!hh2!!!!2???h2???2??!2!h2!hh2!!!!2??2???2?4!!!!h2!!!h2???2????2??!2!hhhh?hhhh?2??!6!!!!!2!!h2??2?2!hh2!!!!h?2??3????2?2!2!!!!!2????2????h?2!???!3!!hhh2!!!h3?????  Verify it online! This uses a much different approach from dingledooper's answer – notably, it only uses h1-9a?!. The initial hahaha fills the buffer with a pool containing all digits, and then it uses careful duplications and slices to construct the string in a contiguous stretch in the buffer, at which point it chops off the surrounding character pool. ## Generating Program import { BinaryHeap } from "https://deno.land/[email protected]/collections/binary_heap.ts"; class State { constructor(public answer = "", public buffer = "") {} clone() { return new State(this.answer, this.buffer.slice()); } set(state: State) { this.answer = state.answer; this.buffer = state.buffer; } i() { this.answer += "i"; this.buffer = fromCharCodes(toCharCodes(this.buffer).map((x) => x + 1)); } a() { this.answer += "a"; this.buffer = toCharCodes(this.buffer).join(""); } h() { this.answer += "h"; this.buffer += "helloworld"; } n() { this.answer += "n"; this.buffer = fromCharCodes( toCharCodes(this.buffer).map((x) => x >= "0".charCodeAt(0) && x <= "9".charCodeAt(0) ? ((x - "0".charCodeAt(0) + 13) % 10) + "0".charCodeAt(0) : x >= "a".charCodeAt(0) && x <= "z".charCodeAt(0) ? ((x - "a".charCodeAt(0) + 13) % 26) + "a".charCodeAt(0) : x >= "A".charCodeAt(0) && x <= "Z".charCodeAt(0) ? ((x - "A".charCodeAt(0) + 13) % 26) + "A".charCodeAt(0) : -1 ), ); } cutStart47(n = 47): number { while (n >= 47) { n -= 47; this.answer += "!"; this.buffer = this.buffer.slice(47); } return n; } cutEnd47(n = 47): number { while (n >= 47) { n -= 47; this.answer += "?"; this.buffer = this.buffer.slice(0, -47); } return n; } copy(n: 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) { this.answer += n; this.buffer = this.buffer.repeat(n); } cut(start: number, end: number) { start = this.cutStart47(start); end = this.cutEnd47(end); [start, end] = this.search( [start, end], (_, [start]) => start === 0, function* (state, [start, end]) { if (state.buffer.length % 47) { for (const n of [2, 3, 4, 5, 6, 7, 8, 9] as const) { const state2: State = state.clone(); let start2 = start + state2.buffer.length * (n - 1); state2.copy(n); start2 = state2.cutStart47(start2); yield [state2, [start2, end]]; } } state.h(); end += 10; end = state.cutEnd47(end); yield [state, [start, end]]; }, )!; // start = this.cutStart47(start); // end = this.cutEnd47(end); this.search( end, (_, end) => end === 0, function* (state, end) { if (state.buffer.length % 47) { for (const n of [2, 3, 4, 5, 6, 7, 8, 9] as const) { const state2 = state.clone(); let end2 = end + state2.buffer.length * (n - 1); state2.copy(n); end2 = state2.cutEnd47(end2); yield [state2, end2]; } } state.h(); end += 10; end = state.cutEnd47(end); yield [state, end]; }, ); } search<T>( init: T, isDone: (state: State, data: T) => boolean, opts: (state: State, data: T) => Iterable<[State, T]>, ) { const pq = new BinaryHeap<[State, T]>(([a], [b]) => a.answer.length - b.answer.length ); pq.push([this.clone(), init]); let cur; while ((cur = pq.pop())) { if (isDone(...cur)) { this.set(cur[0]); return cur[1]; } pq.push(...opts(...cur)); } } } function toCharCodes(x: string) { return [...x].map((x) => x.charCodeAt(0)); } function fromCharCodes(x: number[]) { return x.map((x) => String.fromCharCode(x)).join(""); } let state = new State(); state.h(); state.a(); state.h(); state.a(); state.h(); state.a(); const goal = "14159265358979323846264338327950288419716939937510"; let nextEnd = 0; for (let i = 0; i < goal.length;) { if (state.buffer.length > i + nextEnd + 47) { const state2 = state.clone(); state2.cutStart47(); if ( [..."1234567890"].every((x) => state2.buffer.slice(0, -nextEnd).includes(x) ) ) { state = state2; continue; } } console.log(state.buffer, i); let bestCnt = 0; for (let j = 0; j < state.buffer.length; j++) { let cnt = 0; while (goal[i + cnt] === state.buffer[j + cnt]) cnt++; bestCnt = Math.max(cnt, bestCnt); } if (bestCnt === 0) throw 0; let bestLen = Infinity; let best: [State, [number, number]] | undefined; for (let j = 0; j < state.buffer.length; j++) { let cnt = 0; while (goal[i + cnt] === state.buffer[j + cnt]) cnt++; if (cnt !== bestCnt) continue; const inner: State = state.clone(); const len = inner.buffer.length - nextEnd; if (i === 0) { const end = inner.cutEnd47(len + nextEnd - j - cnt); best = [inner, [i + cnt, end]]; continue; } inner.copy(2); inner.cut(j, nextEnd); inner.copy(2); inner.cutStart47(len + nextEnd - j); const end = inner.cutEnd47(len * 2 + nextEnd - j - cnt); if (i + cnt === goal.length) { inner.cut(inner.buffer.length - end - goal.length, end); } if (inner.answer.length < bestLen) { bestLen = inner.answer.length; best = [inner, [i + cnt, end]]; } } [state, [i, nextEnd]] = best!; } state.answer = state.answer.replace(/22/g, "4").replace(/23|32/g, "6"); console.log(state.answer); console.log(state.answer.length); console.log(state.buffer); console.log(goal);  • @JonathanAllan Testing it on Bubbler's interpreter, it doesn't seem to work – I think the issue is with c%16+13%10+48, as precedence makes it equivalent to (c%16)+51, but I'm not sure what exactly the precedence you intended was Commented Nov 15, 2022 at 0:11 • I don't think n in the generated code would help, as it operates on the whole buffer, and the generated code relies on preserving what it's already build. Commented Nov 15, 2022 at 0:15 • Ah, in that case it is only 5129, seems you've beaten that now anyway :) Commented Nov 15, 2022 at 1:23 • Score 3063 if you replace both uses of len - ind with len - ind - (len - ind) % 47. (Also, using arrays of character codes is very fiddly; generator code is much simpler if you use strings instead.) – Neil Commented Nov 15, 2022 at 10:15 • Ah, so you can in fact avoid eagerly trimming the end as well. I guess that makes your explanation slightly out of date. – Neil Commented Nov 16, 2022 at 11:34 # Score 1253791717684495 379 hicnhannnhh?4!4!!h?3!hh?3!!!!4?h?3!h?3!hh?5?!h?4??2?h?3!3?!!h?5?!!5?!!!!h2???4!!!h2?h?4?!h?5!!!!2??4!!!2???3!!2??4!!!!2h?5?????2???3?!h2!!hhh?2!!7?!!!!!!3!h?2!!!hhhh?5????h?3!!!!3?3????!!!!3??!hhh?3!!!!!4??!!hh2!!h?4!!h?hhhh?2?hhh?hhh2!!h?2!!!5???h?5???!!!!h?2!hhh?2!!4??!3???2??4??!h3!!!!!!!!2???3??!h?2!!!2!!hhhh?3??2!!h2!!!!h?7???!!!2???2???2?2???h?3???!!!2!!!2!!2?2??h?3!!!!!  Try it online! ##### How? Just a heavily tweaked (but still surely not optimal) version of @tjjfvi's strategy. Thanks to @Mukundan314 for -9. # HQ0-9+-INCOMPUTABLE?!, 8265 8261 points -5 points thanks to @Bubbler -4 points thanks to @Mukundan314 This was a very interesting puzzle to solve; note that this is definitely not the cleanest solution. h5?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinhhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?ichhhhh?iiiiiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiichhhhh?iiiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniihhhhh?iiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiichhhhh?iiiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?ichhhhh?iiiiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?chhhhh?iiiiiiiiiiiiinciiiichhhhh?iiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iichhhhh?iiiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?ihhhhh?iiiiiiiiiiiinhhhhh?iihhhhh?iiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinihhhhh?iiiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiihhhhh?iiiiiiiiiinhhhhh?iiiihhhhh?iiiiiiiiiniihhhhh?iiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiiihhhhh?iiiiiiiiiniihhhhh?iiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iihhhhh?iiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiichhhhh?iiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinihhhhh?iiiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiiihhhhh?iiiiiiiiinhhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiichhhhh?iiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiichhhhh?iiiiiiiiinciiiihhhhh?iiiiiiiiiniiiihhhhh?iiiiiiiiinchhhhh?iiiiiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?chhhhh?iiiiiiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinhhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?iiiihhhhh?iiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iihhhhh?iiiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiichhhhh?iiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiihhhhh?iiiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?iiichhhhh?iiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?ihhhhh?iiiiiiiiiiiinhhhhh?chhhhh?iiiiiiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiiihhhhh?iiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiichhhhh?iiiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iichhhhh?iiiiiiiiiiinciiiichhhhh?iiiiiiiiinchhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiiniiiihhhhh?iiiiiiiiiniiiichhhhh?iiiiiiiiinchhhhh?iiiihhhhh?iiiiiiiiinhhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?hhhhh?iiiihhhhh?iiiiiiiiinhhhhh?apppppppppppppppppppppppppphhhhhhhhhhhhhh???  Verify it online! ### Explanation The main idea is to generate a long string of letters, and then perform a single a operation to convert it to the desired output. By itself, there is no such sequence of letters which lead exactly to the first 50 digits of pi. To increase our chances, we can instead find a sequence that works after performing some number of p operations. To illustrate this, if p=1, we would need to find a sequence of letters that decodes to the below (the ?s are wildcards): ?????1??41?5?92??6?535?89793?2??3846?264?3?383?27950?28841?9?71?69?399?3?7510  And for p=2: ??????????????1?????41??5?92?????6?5?35??8?979?3?2???3846??2?64??3??38?3??2795?0?2?8841??9?71?69??39?9??3??7?510  As you can see, the position of the digits become more sparse, therefore there is more room for a valid letter sequence to exist. The next part is figuring out how to build this letter sequence. First, notice that a command with 33 hs followed by 7 ?s appends exactly one h to the buffer. Second, take note of the a and r operations, which increments and rot13s each character, respectively. Using these two facts, we can effectively append every letter from a to h. For example, to append c to abg, we can take these steps: • Perform aaaaa, so abg becomes fgl • Perform 33 hs + 7 ?s, so fgl becomes fglh • Perform aaaaaaaa, so fglh becomes notp • Perform n, so notp becomes abgc Alright, so we know how to build an arbitrary string consisting of a-h (as well as A-H, by making use of the c operator). It turns out that there exists a string consisting of only a-hA-H, such that it turns into the desired output after applying an a followed by 14 ps (don't quote me on this number). We can calculate this string in many ways, such as with dynamic programming. In essence, this is how the algorithm works. The actual code actually applies another optimization that decreased my score from 30K to <10K. That is, instead of using 33 hs and 7 ?s every time we want to append, we can instead use 5 hs and 1 ?, which creates the string hel. Note that this requires more ps so that the digits are sparse enough for a solution to exist. • The leading iiiic seems redundant. Commented Nov 14, 2022 at 7:31 • Btw, it was too fast :P I'll give out the bounty 2 days later. Commented Nov 14, 2022 at 7:37 • Thanks :P Just curious, did your solution use a similar idea? (at least from what you can decipher in the code) Commented Nov 14, 2022 at 7:41 • Pretty much yes (there are not that many options anyway), but I have a bit more sophisticated post-processing which gives 7906 points. Commented Nov 14, 2022 at 7:50 • 4078 points Commented Nov 15, 2022 at 16:57 # HQ0-9+-INCOMPUTABLE?!, 1577...536 510 points hcoh3ioohhh8hh???????ichhhhh?iichh6????iiihh7?????iiiiiiinch9h?????chh3??3h?ch5???ich4hhh???ihhhhh?2hh?h8??????ch2?3hhh??h4???3hh??2hh3h??????iiiiiiiiiiinchh2h??2?ihhhhhhh2????iih6hh???????iiiiiiiiiinh5hhh??????iichhhh2h???chh2??iihh3hh????iiiiiiiiiniiichh3h????ihhhhh?ih2h??iiiiiiiiniiih2h??hhhhh?ihhhhh?iiiiiiiiinihhhhh?ih2??iih3????2hhhhhh???iihh3h?????iiiiiiiniihhhhh?ihhh3hh??????iiiiiiiiiinchhhhh2????hhhhh2????iihh2h???iichhhhh?2??chhh3??????2??2hhhh???2hhh???iiiiiiiiinhhhhh?2hh???2h???2???iannnnppop?o  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 (bit outdated): import functools import itertools import json import pathlib import time import re2 as re # stdlib's regex can't handle this TARGET = "14159265358979323846264338327950288419716939937510" CACHE_PATH = pathlib.Path(__file__).parent / "incomputable-cache.json" MAX_BUFFER = 10**5 ROT_13 = ( "------------------------------------------------" "3456789012" "-------" "NOPQRSTUVWXYZABCDEFGHIJKLM" "------" "nopqrstuvwxyzabcdefghijklm" "-----" ) 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 REMOVE_SET = set(prime_list(MAX_BUFFER) + [2**i for i in range(24)]) def run(prog, buffer=()): """HQ0-9+-INCOMPUTABLE?! interpreter""" buffer = list(buffer) for char in prog: if char == "h": buffer.extend("helloworld") elif char.isdigit(): buffer *= ord(char) - 48 elif char == "i": if any(i in "9Zz" for i in buffer): return buffer = [chr(ord(c) + 1) for c in buffer] elif char == "n": buffer = [ROT_13[ord(c)] 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 (len(buffer) - i) not in REMOVE_SET] elif char == "p": buffer = [c for i, c in enumerate(buffer) if (i + 1) not in REMOVE_SET] elif char == "u": buffer = [c.upper() for c in buffer] elif char == "t": buffer.sort() 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: return return buffer def unrun(prog, buffer): """un-runs part of a program; computes possible buffers before prog was executed""" ret = list(buffer) for char in reversed(prog): if char == "o": ret = ["#" if i + 1 in REMOVE_SET else ret.pop() for i in range(10 * len(ret)) if ret] ret.reverse() elif char == "p": ret.reverse() ret = ["#" if i + 1 in REMOVE_SET else ret.pop() for i in range(10 * len(ret)) if ret] elif char == "?": ret.extend("#" * 47) elif char == "!": ret = ["#"] * 47 + ret return ret def brute_start(max_length=5): """ brute-force for programs that satisfy conditions: - shortest to generate its output - does not contain 0-9, m-z, M-Z in output """ if CACHE_PATH.exists(): saved = json.loads(CACHE_PATH.read_text()) return list(zip(saved.values(), saved.keys())) mid_chars = "h23456789incopt?!" last_chars = "hincopt?!" saved = {"": ""} for length in range(1, max_length + 1): for prog in itertools.product("h", *[mid_chars] * (length - 2), last_chars): if (output := run(prog)) is None or any(c.lower() > "l" for c in output): continue output = "".join(output) if output not in saved: saved[output] = "".join(prog) CACHE_PATH.write_text(json.dumps(saved)) return list(zip(saved.values(), saved.keys())) @functools.cache def optimal_trim(size, trim): """more optimal ways exists, but good enough for now""" best = None for i in range(1, 10): tens = (-(trim + size * (i - 1)) * pow(10, -1, 47)) % 47 rem = (size * (i - 1) + tens * 10 + trim) // 47 pre, post = tens // i, tens % i curr = f"{'h' * pre}{i if i != 1 else ''}{'h' * post}{'?' * rem}" if best is None or len(curr) < len(best): best = curr return best @functools.cache def optimal_prefix(size, extra): """optimal way to achieve buffer + buffer[:extra]""" best = None for i in range(2, 10): if size * (i - 1) < extra: continue if size * (i - 1) == extra: return str(i) trim = optimal_trim(size * i, size * (i - 1) - extra) if best is None or len(trim) + 1 < len(best): best = f"{i}{trim}" return best def solve(target, start, transform_map, max_prog=10 ** 9): dp = [(None, None)] * (len(target) + 1) def add(matched, prog, output): if len(prog) > max_prog: return if dp[matched][0] is None or len(prog) < len(dp[matched][0]): dp[matched] = (prog, output) for prog, output in start: transformed = [j for i in output for j in transform_map[i]] if all(i in ["#", j] for i, j in zip(target, transformed)): add(len(transformed), prog, output) for matched, (prog, output) in enumerate(dp): if prog is None: continue for prefix in ["h", "he", "hel", "hell"]: trim = optimal_trim(len(output) + 10, 10 - len(prefix)) for shift in range(ord(min(prefix)) - ord('a') + 1): shifted = "".join(chr(ord(i) - shift) for i in prefix) for is_upper, cased in enumerate([shifted, shifted.upper()]): transformed = [j for i in cased for j in transform_map[i]] if matched + len(transformed) > len(target): continue if all(target[i] in ["#", c] for i, c in enumerate(transformed, matched)): add( matched + len(transformed), ( f"{prog}" f"{'c' * is_upper}" f"{'i' * shift}" f"h{trim}" f"{'i' * (-shift % 13)}{'n' * bool(shift)}" f"{'c' * is_upper}" ).replace("cc", ""), output + cased, ) new_matched, new_output = matched, output for i, c in enumerate(itertools.cycle(output)): if new_matched + len(transform_map[c]) > len(target) or i >= len(output) * 8: break if not all(target[j] in ["#", k] for j, k in enumerate(transform_map[c], new_matched)): break new_output += c new_matched += len(transform_map[c]) add(new_matched, prog + optimal_prefix(len(output), i + 1), new_output) return dp[-1] def main(): start = brute_start() # constraint: transform(a) + transform(b) == transform(a + b) transforms = [f"{'n'*j}a{'n'*i}" for i in range(10) for j in range(2)] best = None prev = time.perf_counter() for transform in transforms: transform_map = {i: run(transform, i) for i in "ABCDEFGHIJKLabcdefghijkl"} regex_filter = re.compile(f"^({'|'.join(''.join(f'[{j}#]' for j in i) for i in transform_map.values())})+$")

print(
"\033[0;33m",
f"[{time.perf_counter() - prev:.2f}]",
f"transform: {transform}",
f"(filter size: {regex_filter.programsize})",
"\033[0m",
)

prev = time.perf_counter()

for end in itertools.product("po", repeat=11):
sparse_target = unrun(end, TARGET)
if regex_filter.match("".join(sparse_target)) is None:
continue

prog, _ = solve(sparse_target, start, transform_map, len(best) if best else 2000)
if prog is not None:
prog = f"{prog}{transform}{''.join(end)}"
# assert "".join(run(prog)) == TARGET
if best is None or len(prog) < len(best):
print(len(prog), prog)
best = prog

if __name__ == "__main__":
main()


1000076 points

1415c9c265c35c89c7c93238c46264c338c3c279c5028cc8c41971c693c9cc93c7c51cc0cccqo


c is a placeholder. It can be replaced with any digit, or with any other letter command that has no effect when the buffer is empty.

The only commands that do anything are q and o. So it loads the source code into the buffer then removes characters using o, but it only removes the letters. I tried to do it by ending with qp instead but it didn't line up.

These two attempts don't work because if you use q then ? can not be in the source code.


14159265358979323846264338327950288419716939937510q111111111111111111111111111111111111111111111?

14159265358979323846264338327950288419716939937510q5?????

• Welcome to Code Golf, and nice answer! Commented Dec 2, 2022 at 20:26