5
\$\begingroup\$

We often get questions here on PPCG that favour submitting solutions using only a subset of characters (sufficiently so that there's a tag that identifies a particular subset of those challenges). Wouldn't it be nice if we could automatically cut languages down to a subset of their normal character set?

As an example, JavaScript is sometimes translated into a subset known as JSFuck which contains only the characters []()!+. In this challenge, you're aiming to write the equivalent of a JavaScript to JSFuck translator, but without the language restriction: you're compiling a language of your choice down to a subset of its characters (well, bytes, in order to avoid dubious corner cases).

Clarifications and detailed specification

  • Call the program you submit program A. The input to program A will be a string representing a program (program B). Its output must also be a string representing a program (program C). Program B will be in the same language as program A (there are no restrictions on how your program reacts to invalid input). Program C must also be a program in that language, and have the same behaviour in all cases as program B (i.e. if program C is given input X, it will produce the same probability distribution of outputs as program A does).
  • You may assume that in the case where programs A and B are distinct, program B does not access any files from disk. (In particular, you may assume it does not attempt to read its own source code from disk.).
  • Although part of the scoring is based on a single test case (program A itself), your program must work for any input (in the sense of complying with the specification above; that is, any valid program B must lead to a corresponding output for program C). Optimizing specifically for the test case given is allowed (and might or might not be helpful).
  • A cat implementation is technically speaking a valid answer to this question (as the subsetting of characters is part of the scoring criterion, not the validity criterion), but the scoring is designed so that such a program is unlikely to win. Just as solutions to competitions should make at least an attempt to minimize the number of bytes, solutions to this competition should make at least an attempt to minimize score. (Note that in some languages, cat may genuinely work best because the character sets are already small or impossible to shave down further. These solutions are valid, but ideally wouldn't be upvoted.)
  • You can accept the strings used for your input and output via any reasonable method.
  • Because languages with no computational ability might potentially lead to trivial solutions due to there being few possible programs to consider, this competition is open only to entries written in programming languages.

Victory condition

Let S be the set of bytes that can appear in the outputs C of your program (that is: for any valid input B, if the corresponding output C can potentially contain a byte, then that byte must be an element of S). Let c be the number of elements in S.

Now, let Q be the result of running your program on itself (i.e. the output C produced when A and B are the same program). Let b be the number of bytes in Q. (In order to minimize b and thus your score, you'll want to keep your program short, as in , but also the size of your program's output short, as in .)

Your score for this is:

(b+1000)×loge(c+1)

The winner is the entry with the lowest score. (If there's a tie for first place, the lowest c among the tied entries will win; if there's still a tie for first place, the earliest entry among the entries tied for first will win.) Even if you can't win, though, you're encouraged to show off interesting answers (perhaps answers with a particularly low c, or in a language other people haven't attempted yet).

Improve this question
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Agreed that they're similar. The other challenge has a broken victory condition, though (it has a vaguely worded ban on languages which is the only thing preventing Unary scoring 1). Actually, that challenge probably needs to be closed as unclear. \$\endgroup\$
    – user62131
    Commented Dec 28, 2016 at 11:08
  • \$\begingroup\$ To those who closed as 'unclear what you're asking', what exactly is unclear? I found the challenge plenty clear. \$\endgroup\$
    – orlp
    Commented Dec 28, 2016 at 13:52
  • \$\begingroup\$ @orlp, with the link added to the actual JSFuck page this becomes clear (well actually still a bit muddy on JSFuck's property to seemly be able to run in normal JS, is that required too?) to me. But this is a duplication issue now it seems. \$\endgroup\$
    – redstarcoder
    Commented Dec 28, 2016 at 14:34

1 Answer 1

Reset to default
1
\$\begingroup\$

Brainfuck, (1000 + 133) * loge(8+1) ~= 2489

Requires an interpreter that has wrapping 8-byte unsigned cells and produces 0 or doesn't change the cell on EOF.

,[>>>--[>-<++++++]>>->->->-------------->-->>>-[++[>]<<->+]--[<]<<<[->+>>+<<<]+>>>>[<[->+<]+>[<-]<[->>[[-]>]-[+<-]+>.>]>>>]-[[+]<-],]

A proper brainfuck interpreter ignores any character except []<>+-,., so we minify the character set by keeping only those characters.

For example, giving this as input to the above program produces the above program:

,[>>>
prepare array
--[>-<++++++]>>->->->-------------->-->>>-[++[>]<<->+]--
[<]<<<[->+>>+<<<]+>>>
while number to the right of i
>[
    <[->+<] move sum of both to the right
    +>[<-]<[ if sum == 0
        clear everything to the right
        ->>[[-]>]
        move to the left until we hit 1
        -[+<-]
        output i and move past to stop loop
        +>.>
    ]
    >>>
]
-[[+]<-]
,]
Improve this answer
\$\endgroup\$