Recursively define a "valid arithmetic expression":

  1. Any natural number is a valid arithmetic expression.
  2. If s is a valid arithmetic expression, then so is (-s).
  3. If p and q are valid arithmetic expressions, then so is (p+q).

In the above, a "natural number" is recursively defined as follows:

  1. 0 1 2 3 4 5 6 7 8 9 are natural numbers.
  2. If a natural number n is not 0, then n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 are natural numbers.

Alternatively, via the regex /^(0|[1-9][0-9]*)$/

Examples of valid arithmetic expressions:


Examples of invalid arithmetic expressions:


The challenge is to print every valid arithmetic expression line by line, i.e. create a program that will output strings line by line with the constraint that every valid arithmetic expression is eventually printed, and that no invalid arithmetic expression is ever printed.

The valid arithmetic expressions can be printed more than once.

The challenge is to do so in as few bytes as possible, since this is .

Standard loopholes apply.

  • 2
    \$\begingroup\$ The output should be infinite, presumably? How can we demonstrate that every valid expression will be printed? \$\endgroup\$ – Phil H Apr 16 '18 at 12:46
  • 1
    \$\begingroup\$ @PhilH well you can challenge an answer that doesn't meet the criterion and the author of the answer would have to justify it... \$\endgroup\$ – Leaky Nun Apr 16 '18 at 12:49
  • 1
    \$\begingroup\$ @PhilH then the entry is invalid. \$\endgroup\$ – Leaky Nun Apr 16 '18 at 13:27
  • 1
    \$\begingroup\$ @PhilH That doesn't satisfy "every valid arithmetic expression is eventually printed", as (-0) is never printed. \$\endgroup\$ – user202729 Apr 16 '18 at 13:40
  • 1
    \$\begingroup\$ @PhilH Seems that you misunderstood the rules? The validity criteria is "for all expression E, there exists a (finite) natural number N, such that the N'th line printed is E" Your example does not satisfy that. \$\endgroup\$ – user202729 Apr 16 '18 at 15:19

Jelly, ... 33 bytes


Try it online!

Wow, writing a correct submission is hard.

Python pseudocode equivalent:

import itertools

# Jelly: ⁾()j
def wrap_in_parentheses(x):
 return str(x).join(['(',')'])
 # or equivalently, `return '('+str(x)+')'

# Jelly: p`j”+Ç$€;;”-;ÇƊ€;®‘©¤Ṅ€
register = 0
def expand_and_print(expressions):
 # Jelly: p`
 result = list(itertools.product(expressions, repeat=2))

 # Jelly: j”+Ç$€
 result = [wrap_in_parentheses('+'.join(expr)) for expr in result]

 # Jelly: ;

 # Jelly: ;”-;ÇƊ€
 result.extend([wrap_in_parentheses('-'+expr) for expr in expression])

 # Jelly: ;®‘©¤
 global register
 register += 1

 # Jelly: Ṅ€
 for expr in result:

 return result

# Jelly: WÇ1¿
expressions = ['0']
while 1:
 expressions = expand_and_print(expressions)

JavaScript ES6, 79 bytes

  • \$\begingroup\$ 1. Infinite large integer in variable, assumed; 2. Totally unrunnable in fact \$\endgroup\$ – l4m2 Apr 16 '18 at 14:10

Python, 241 bytes

g=lambda n,s=0:s<6 and(l+r for x in(["\x13 8"]+list("I-x</"))[s]for a in range(n)for l in g(a,ord(x)%12)for r in g(n-a,ord(x)//12))or[]if n^1else s>7and["(-)+"[s-8]]or list("0123456789"[s==7:])*(s%6<2)
while i:print("\n".join(g(i)));i+=1

This isn't too short, but it's a table-driven approach that's semi-automatically generated from a CFG I wrote for this language. It's unreasonably fast (speed sacrificed for bytes) :)


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.