37
\$\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.

\$\endgroup\$
10
  • 3
    \$\begingroup\$ I wonder what happened to "99 bottles of beer on the wall" \$\endgroup\$ Nov 14 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
    Nov 14 at 5:08
  • 1
    \$\begingroup\$ Most useless? I'd have Q removed as it's not even an exact quine. \$\endgroup\$ Nov 14 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
    Nov 14 at 15:11
  • 1
    \$\begingroup\$ @DanielSchepler Seems like it. \$\endgroup\$
    – Aiden Chow
    Nov 14 at 21:22

4 Answers 4

33
\$\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/std@0.164.0/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);
\$\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
    Nov 15 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
    Nov 15 at 0:15
  • \$\begingroup\$ Ah, in that case it is only 5129, seems you've beaten that now anyway :) \$\endgroup\$ Nov 15 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
    Nov 15 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
    Nov 16 at 11:34
26
+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.

\$\endgroup\$
8
  • \$\begingroup\$ The leading iiiic seems redundant. \$\endgroup\$
    – Bubbler
    Nov 14 at 7:31
  • \$\begingroup\$ Btw, it was too fast :P I'll give out the bounty 2 days later. \$\endgroup\$
    – Bubbler
    Nov 14 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\$ Nov 14 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
    Nov 14 at 7:50
  • \$\begingroup\$ 4078 points \$\endgroup\$ Nov 15 at 16:57
25
\$\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.

\$\endgroup\$
0
11
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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