40
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
10
  • 3
    \$\begingroup\$ I wonder what happened to "99 bottles of beer on the wall" \$\endgroup\$
    – SectorCorruptor
    Commented Nov 14, 2022 at 4:58
  • 3
    \$\begingroup\$ @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 \$\endgroup\$
    – Bubbler
    Commented Nov 14, 2022 at 5:08
  • 1
    \$\begingroup\$ Most useless? I'd have Q removed as it's not even an exact quine. \$\endgroup\$
    – SectorCorruptor
    Commented Nov 14, 2022 at 5:20
  • 2
    \$\begingroup\$ @Pacmanboss256 > If you're wondering about the role of the accumulator, you're right: it still does nothing useful. \$\endgroup\$
    – Seggan
    Commented Nov 14, 2022 at 15:11
  • 1
    \$\begingroup\$ @DanielSchepler Seems like it. \$\endgroup\$
    – Aiden Chow
    Commented Nov 14, 2022 at 21:22

5 Answers 5

Reset to default
34
\$\begingroup\$

HQ0-9+-INCOMPUTABLE?!, 7884 5134 4122 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);
Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ @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 \$\endgroup\$
    – tjjfvi
    Commented Nov 15, 2022 at 0:11
  • \$\begingroup\$ 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. \$\endgroup\$
    – tjjfvi
    Commented Nov 15, 2022 at 0:15
  • \$\begingroup\$ Ah, in that case it is only 5129, seems you've beaten that now anyway :) \$\endgroup\$
    – Jonathan Allan
    Commented Nov 15, 2022 at 1:23
  • \$\begingroup\$ 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.) \$\endgroup\$
    – Neil
    Commented Nov 15, 2022 at 10:15
  • \$\begingroup\$ Ah, so you can in fact avoid eagerly trimming the end as well. I guess that makes your explanation slightly out of date. \$\endgroup\$
    – Neil
    Commented Nov 16, 2022 at 11:34
29
\$\begingroup\$

Score 1253 791 717 684 495 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.

Improve this answer
\$\endgroup\$
0
28
+500
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ The leading iiiic seems redundant. \$\endgroup\$
    – Bubbler
    Commented Nov 14, 2022 at 7:31
  • \$\begingroup\$ Btw, it was too fast :P I'll give out the bounty 2 days later. \$\endgroup\$
    – Bubbler
    Commented Nov 14, 2022 at 7:37
  • \$\begingroup\$ Thanks :P Just curious, did your solution use a similar idea? (at least from what you can decipher in the code) \$\endgroup\$
    – dingledooper
    Commented Nov 14, 2022 at 7:41
  • \$\begingroup\$ Pretty much yes (there are not that many options anyway), but I have a bit more sophisticated post-processing which gives 7906 points. \$\endgroup\$
    – Bubbler
    Commented Nov 14, 2022 at 7:50
  • \$\begingroup\$ 4078 points \$\endgroup\$
    – Mukundan314
    Commented Nov 15, 2022 at 16:57
13
\$\begingroup\$

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()
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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?????
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$
    – naffetS
    Commented Dec 2, 2022 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.