Java2016

Java2K는 내장 함수가 의도한 동작을 확률적으로만 수행하는 난해한 프로그래밍 언어다. 존은 Java2K를 연습하려고 훨씬 단순한 언어 Java2016을 만들었다. Java2016의 연산자는 결정적이지만 피연산자가 무작위다. Java2016의 모든 값은 0 이상 255 이하의 정수다.

Java2016에는 우선순위가 세 단계인 연산자 여섯 개가 있다.

<expression> ::= <expression> min <sum> | <expression> max <sum> | <sum>
<sum>        ::= <sum> + <term> | <sum> - <term> | <term>
<term>       ::= <term> * <factor> | <term> / <factor> | <factor>
<factor>     ::= ( <expression> ) | ? | <macro>

min과 max는 보통의 최솟값과 최댓값이다. 덧셈, 뺄셈, 곱셈은 256으로 나눈 나머지로 계산한다. 나눗셈은 0 쪽으로 내림하고, 나누는 값이 0이면 프로그램이 죽는다. ?는 0부터 255까지 고르게 무작위로 뽑은 값이고, 식에 나오는 ?는 자리마다 서로 독립이다.

프로그램은 매크로 정의 0개 이상과 마지막 결과 식으로 이루어진다.

<macrodef> ::= <macro> = <expression>
<macro>    ::= a | b | ... | z

매크로는 쓰기 전에 정의해야 하고 다시 정의할 수 없다. 매크로는 쓰인 자리마다 정의된 식으로 그대로 펼쳐진다. 예를 들어 a = ? max ?를 정의하고 쓴 식 (a max a) / a는 ((? max ?) max (? max ?)) / (? max ?)로 펼쳐지고, 펼친 식의 ? 여섯 개는 모두 독립이다. 식 ? / ? / ?가 0이 될 확률은 98.2%이고 프로그램이 죽을 확률은 0.8%다.

존은 Java2016에 확률적 상수를 넣으려고 한다. 값마다, 죽지 않고 그 값으로 계산될 확률이 $1/2$ 이상인 프로그램이 필요하다. 죽는 경우는 실패로 센다.

첫 줄에 목표 상수 $c$가 주어진다. ($0 \le c \le 255$)

$c$로 계산될 확률이 $1/2$ 이상인 프로그램은 여러 개다. 답을 하나로 정하기 위해, 다음 규칙으로 만든 프로그램을 그대로 출력한다.

먼저 매크로 정의 20줄을 아래와 똑같이 출력한다.

a = ? max ?
b = a max a
c = b max b
d = c max c
e = d max d
f = e max e
g = f max f
h = g max g
i = h max h
j = i max i
k = j max j
l = k max k
m = l / l
n = m + m
o = n + n
p = o + o
q = p + p
r = q + q
s = r + r
t = s + s

그다음 마지막 줄에 결과 식을 출력한다. 결과 식은 m - m으로 시작한다. $i = 0, 1, \ldots, 7$ 순서로, $c$를 2진법으로 나타냈을 때 $2^i$ 자리가 1이면 결과 식 뒤에 +와 매크로 이름을 이어 붙인다. $2^i$에 대응하는 매크로 이름은 1부터 128까지 차례로 m, n, o, p, q, r, s, t다.

연산자와 = 양옆에는 위 예시처럼 공백을 하나씩 둔다. 이렇게 만든 프로그램이 $c$로 계산될 확률은 0.9999보다 크고, 공백을 뺀 길이는 143자 이하다.