8
\$\begingroup\$

I'd like some feedback on an idea for a new type of challenge that I have, namely Abstract Syntax Tree golfing.

Code Golfing is a lot of fun. But many of the tricks that get used in a given language are the same for every challenge. I'd like to ask a challenge which, instead of counting bytes, counts pieces of code. "Pieces of code" isn't very specific, so to make it more objective, I will use the size of the abstract syntax tree of the program.

This idea has a major problem: Not every language has an abstract syntax tree (e.g. Seeds), and the same program in the same language may be converted to different ASTs by different interpreters or compilers. To solve this problem, my initial challenge will only allow one language, namely Python. Python is chosen because it has a canonical abstract syntax tree for any piece of code, namely the one returned by the ast module.

The scoring code for this challenge will be as follows:

import ast
print(len(list(ast.walk(ast.parse(code)))))

Note that this code gives the desired result in both Python 2 and 3, though a given piece of code may have a different scoring in the two versions.

Now, there are certain types of code which I am worried may trivialize the challenge:

  • Code execution. exec "stuff" will do anything in 2 tokens, but it's not very interesting. eval has the same issue, as well as ast.literal_eval to a lesser extent, and likely many other functions. I'd like to ban all such functions.

  • Very long data-tokens. More specifically, I'm worried about very long string and numeric literals. For instance, for the challenge "Print all primes under a million", I don't want a literal string with a million lines to win. To handle this, I'd like to ban all tokens longer than 15 characters of source code. This also handles worries about code like the following:

    def crazylongfunctionnameitsreallygettingoutofcontrol(): pass
    print(crazylongfunctionnameitsreallygettingoutofcontrol.__name__)
    

    So I'll just ban it all. If code legitimately needs long strings or large numbers, it can build it out of smaller strings or numbers at some overhead.

    Since I'd like submissions to be fully automatically checked and scored, I'll use Python's tokenize module for this. Code can be found here: simple_counter.py

I'm thinking of posting the classic FizzBuzz challenge as the first challenge of this type.


What do people think of this challenge? Would it produce interesting submissions? Interesting winning submissions? Are there other ways to trivialize the challenge that I haven't thought of?

\$\endgroup\$
  • \$\begingroup\$ Btw: Cheddar also has an ast module \$\endgroup\$ – Downgoat Nov 17 '16 at 4:17
  • \$\begingroup\$ Pytek will also have this feature whenever it ships. \$\endgroup\$ – El'endia Starman Nov 17 '16 at 4:18
  • 1
    \$\begingroup\$ How do you determine the "number of characters of source code" that an AST node corresponds to? \$\endgroup\$ – feersum Nov 17 '16 at 4:19
  • \$\begingroup\$ @feersum I'll use Python's tokenize module, thanks for pointing that out. \$\endgroup\$ – isaacg Nov 17 '16 at 4:34
  • \$\begingroup\$ I'd like to ban all tokens longer than 15 characters of source code. You don't need that, these are already forbidden here : check meta.codegolf.stackexchange.com/questions/1061/… \$\endgroup\$ – Walfrat Nov 17 '16 at 8:43
  • 1
    \$\begingroup\$ @Walfrat That ban usually isn't relevant, sense hardcoding the answer is essentially never optimal. I don't want to put answerers in the positions of trying to skirt a vague rule as closely as possible without going over, so I'll just ban it all. \$\endgroup\$ – isaacg Nov 17 '16 at 8:50
  • \$\begingroup\$ Btw: my implementation of pyth also has an ast, even if it isn't 100% complete \$\endgroup\$ – Maltysen Nov 18 '16 at 19:48
  • \$\begingroup\$ @Walfrat could you link the answer to which you refer? I didn't find anything there about long function names. \$\endgroup\$ – Paŭlo Ebermann Nov 27 '16 at 23:53
  • \$\begingroup\$ Idea: Instead of banning long tokens, just ban _name_ and similar, and count the characters for string tokens. \$\endgroup\$ – Paŭlo Ebermann Nov 27 '16 at 23:54
  • \$\begingroup\$ @PaŭloEbermann if I refer to your example print(crazylongfunctionnameitsreallygettingoutofcontrol.__name__) the answer is here meta.codegolf.stackexchange.com/a/1063/55635. If the standard loopholes are missing some case for you, you may first try to add it there, because it can benefits the others kind of challenges too. \$\endgroup\$ – Walfrat Nov 28 '16 at 8:25
  • \$\begingroup\$ @walfrat I would say using a long name would not just useful for questions with just a single output. For example, there could be solutions where this crazy long name (not my example, though) would not be the full output, but just a part of the output. Or we are evaluating this name as code, or using it otherwise as data. That wouldn't give any advantage for normal codegolf, just for this AST-counting version, so it is a specific loophole of those rules. (And specifically for kolmogorov-complexity those would actually be useful.) \$\endgroup\$ – Paŭlo Ebermann Nov 28 '16 at 20:02
  • 1
    \$\begingroup\$ Isn't that atomic-code-golf? \$\endgroup\$ – OldBunny2800 Nov 30 '16 at 0:27

You must log in to answer this question.

Browse other questions tagged .