28
\$\begingroup\$

Scratch is a visual programming language, meant for teaching kids how to program.
It's completely absent from this site, which, I think, is worth fixing.

I have no specific challenge in mind.

A scratch program is not made of text, but of visual building blocks, that represent actions, control structures and expressions. Therefore, the code-golf metric isn't trivial - we should decide what to count.

Suggested counting:

  1. Each block is 1 point.
  2. Each constant is 1 point per character (or per digit).
  3. Each operator is 1 point.
  4. Each variable used in an expression is 1 point.
  5. If initialized lists are used, each value is counted as a constant.

Example program:
enter image description here

Calculated cost:

  1. When flag clicked - 1
  2. ask <n=> and wait - 3 (block + 2-char constant)
  3. set n to <answer> - 2 (block + variable answer).
  4. set i to 0 - 2 (block + constant).
  5. repeat until <n=1> - 4 (block, operator =, variable, constant).
  6. if <n mod 2 = 0> - 6 (block, operators = and mod, variable, 2 constants).
  7. set n to n/2 - 4 (block, operator, variable, constant).
  8. set n to 3*n+1 - 6 (block, operators * and +, variable, 2 constants).
  9. change i by 1 - 2 (block, constant).
  10. say i - 2 (block, variable).

Total score: 32 points.

Another way, which Peter Talyor suggested, is to find a textual program representation Scratch uses itself.
I found one thing, in the Scratch web interface, but I don't really like it. You need to save the project, rename the file to ZIP, and extract a JSON file. A part of it is the script, which looks like this:

["whenGreenFlag"],
["doAsk", "n="],
["setVar:to:", "i", 0],
["setVar:to:", "n", ["answer"]],
["doUntil",
["=", ["readVariable", "n"], "1"],
[["doIfElse",
["=", ["%", ["readVariable", "n"], 2], "0"],
[["setVar:to:", "n", ["\/", ["readVariable", "n"], 2]]],
[["setVar:to:", "n", ["+", ["*", 3, ["readVariable", "n"]], 1]]]],
["changeVar:by:", "i", 1]]],
["say:", ["readVariable", "i"]]]]

With this, we can simply count the length in characters (better ignore whitespace). However, the resulting length is strange. For example, variable access becomes very expensive. Also, the process of extracting this is annoying.

Also, we may want a more convenient format to post answers, instead of a screenshot.

\$\endgroup\$
  • 1
    \$\begingroup\$ Surely it must have some file format for saving your programs? If that isn't a binary blob, then it would seem to be both the way to post the program and the way to count it. \$\endgroup\$ – Peter Taylor Oct 7 '13 at 9:42
  • 1
    \$\begingroup\$ @PeterTaylor, Sort of, maybe. I'm updating the question. \$\endgroup\$ – ugoren Oct 7 '13 at 14:16
  • \$\begingroup\$ In addition to Scratch, there's a whole slew of visual flow-control languages (pd, Max/MSP, etc.) that suffer from this problem. For example Max does have a text output format but it is cluttered by detailed layout information for every single element of the program. There's no way to get the logic without the layout - but that's as it has to be, because in Max and PD layout affects order of operations. Since I love quixotic exotic answers, I may have to answer a question in PD one of these days. \$\endgroup\$ – Jonathan Van Matre Feb 17 '14 at 22:56
  • 1
    \$\begingroup\$ Is the JSON code sufficient to import and run the code in Scratch? If you alter the source code to reduce it but it won't run in Scratch, that's cheating, because the code won't be runnable as the codes in other languages. Or you have to apply the same rule to other languages and replace malloc by m etc. I find the idea of Scratch very interesting, but I think it's just not applicable when the shortest code is expected. It's still valid in other contests. \$\endgroup\$ – A.L Mar 30 '14 at 2:39
  • \$\begingroup\$ @n.1, I think the real problem is that a scratch program is not only code, but also sprite definitions, positions and graphics. I have no idea how should we count these. \$\endgroup\$ – ugoren Mar 30 '14 at 6:35
  • 1
    \$\begingroup\$ Answers are meant to be self-contained, all the code necessary to run must be contained in the answer. Is it possible with Scratch? \$\endgroup\$ – A.L Mar 30 '14 at 16:54
  • 1
    \$\begingroup\$ Quines are almost impossible. \$\endgroup\$ – Elliot A. Feb 6 '16 at 15:38
  • \$\begingroup\$ @ElliotA. Quines are never impossible. \$\endgroup\$ – PyRulez Jun 27 '17 at 0:42
19
\$\begingroup\$

I have two very different scoring methods that i'm going to post as separate answers. Here's the other one.


We could use ScratchBlocks2 syntax, which is a way of representing Scratch blocks as they are written. We can then simply count bytes of that output.

For the example code in the question, that becomes 193 bytes:

when gf clicked
ask[n=]and wait
set[n v]to(answer)
set[i v]to[0]
repeat until<(n)=[1]>
if<((n)mod(2))=[0]>then
set[n v]to((n)/(2))
else
set[n v]to(((3)*(n))+(1))
end
change[i v]by(1)
end
say(i)

You can also leave off closing brackets and parentheses at the end of a line, which brings it down to 183 bytes.

Yes, this is a high byte count. I think that can simply be a hazard of using Scratch as your language.

This also happens to be a very convenient way of posting Scratch code without images. ScratchBlocks2 even comes with a generator to create text code from a project.

\$\endgroup\$
  • 1
    \$\begingroup\$ I definitely endorse this method. It has its drawbacks, but I think it's the best option available. \$\endgroup\$ – timothymh Oct 28 '15 at 6:10
  • 7
    \$\begingroup\$ This seems fine, since an actual transpiler from this syntax to Scratch blocks exists, so that this code is ultimately executable. (Just leaving this comment here, because people are occasionally referring to this discussion as a precedent for "making up convenient, countable syntax for non-text-based languages".) \$\endgroup\$ – Martin Ender Jul 27 '16 at 7:53
  • \$\begingroup\$ It's locale dependant. Should we say that we must use English when generating the ScratchBlocks2? \$\endgroup\$ – Max Aug 6 '18 at 6:19
9
\$\begingroup\$

Code golf and atomic code golf do not mix

is a valid challenge type, but this style of scoring does not apply to . If you are entering a code golf challenge using Scratch then the number of bytes in the source code is the only valid score.

There can be debate over what counts as the source code, but that does not introduce the possibility of scoring based on atomic elements of the code.

When deciding whether a given format counts as source code, simply ask whether there is a compiler or interpreter that will accept that source code and run it correctly.

Current consensus is that it is acceptable to write a compiler or interpreter for just this purpose, in order to make a given format of source code valid. See May I create my own programming language, which uses existing compiler?

Without this, an arbitrary way of representing scratch code will not be valid.

\$\endgroup\$
7
\$\begingroup\$

Scratch is not absent from PPCG anymore. At least an answer here uses it:
Create a Simon Clone!, which brings up the scoring issue again.

I agree with the first proposal of counting based on blocks and constants, rather than a textual representation.
The scoring in the latter case would be strongly dependent on the encoding. To reduce that effect one could choose an encoding that minimises the number of characters used, for example assigning a single char to the most used blocks. This solution would likely make the textual representation of the program not very readable and probably give a similar score to that based on 'block counting'. Hence my proposal.

\$\endgroup\$
2
\$\begingroup\$

This was meant to be a comment, but then I realised it was too long.

I think we have to take into account sprite definitions and graphics and audio, otherwise it would be very unfair. (I don't really have a suggestion though.)

For example, in this answer of mine, the scripts depend heavily on the costumes of the sprites. It assumes the sprite only has two costumes (hence using next costume twice reverts back to the original), and it uses these two costumes to create the blinking effect. All these are counted as two bytes. Also, according to this proposed scoring, playing the sound effect is only one byte. This would create a very high advantage and soon perhaps every answer here will be in Scratch.

Besides, this scoring has missed out the use of lists in Scratch.

enter image description here

Here in the white input field, we can either write a numerical index, or choose one of the two special options, last and all. If we are to use the scoring method proposed in the question, I propose that we add 4 and 3 bytes to the use of last and all respectively. This applies similarly here:

enter image description here

In addition, I propose that these two should be counted as variable use.

enter image description here

And this as an operator.

enter image description here

Finally, I propose that, if the above scoring is used, subroutines should be counted with the define block as 1, plus the name of the subroutine, plus one for each call of the subroutine. Example:

enter image description here

Here, the purple blocks should add up to 5. (I personally recommend 8, but this is to be consistent with the proposed scoring system.)

\$\endgroup\$
2
\$\begingroup\$

Position Statement: It is all about bits and bytes

When golfing the object is to get as small a representation of the program as possible. If something is a computer program, it has to be able to be represented as bytes, and from the computers point of view the size is all about the number of bytes.

Even with text programs, the number of bytes is useful. To a normal person "echo e" only has five characters. But it takes 6 bytes so we score it as 6 (unless removing the whitespace does not affect the correctness, in which case the answer is "really" the whitespace free version, and the whitespace has just been added for human readers). If we were to take a more normal definition of characters then virtually every golfing question could be answered in 0 points with Whitespace.

By scoring by bytes, can apply an objective size to any program. Even if non-binary computers become common we don't need a subjective definition of program size. We can prove that a base-n digit has provides exactly log(n)/log(2) times as much information as a (binary) bit. This information theory also guarantees that if we count bytes we avoid ridiculous cheats in languages implemented prior to the challenge. For example, if you hardcode every function you can think of as a single operation, then you are going to need multiple bytes per operation and may still not win. If you implement a language where every program can be specified as a single unicode character, you are going to need lots of code code points to specify that one character; again this "cheat" language won't guaranty victory. This theory applies just as well to visual languages as textual.

Therefore it is always reasonable to ask "what is the size of your program in bytes". For a program to run on a computer it has to exist a bunch of bytes, if your development environment doesn't give you those bytes, that is a limitation of your DE; not a limitation of byte counts as a score nor a limitation of visual languages.

The only relevant sequence of bytes seems to be the JSON script. It is unnecessarily long, but then Java also has to deal with lots of pointless boilerplate before it will compile.

Factors such as "is this machine generated" vs is it source seem somewhat subjective. Many IDE generate C code, and many 4th Generation Languages treat C as output not as input. Regardless, you should be charged 1 point per 8 bits of information.

The proposal does not admit an obvious encoding

Given that every other language has an encoding that can be measured objectively by byte-count, it doesn't seem fair to simply assume the existence of a super-efficient encoding of Scratch. Such an encoding would have to deal with issues such as:

  • How do you terminate string constants?
    • If you add a terminator, you need another byte (and what do you do if the terminator exists in the string constant?)
  • Can all blocks be defined in a single character? If not, which blocks should be single character?
  • How do you know when a loop ends? An End Loop opcode should do, but there is another byte and when golfing every byte counts.

A possible efficient encoding

If we agree than we want to keep scoring programs by their byte count, but want Scratch programs to be able to compete then we need an efficient encoding for Scratch.

I have made a compiler for reasonably efficient GolfScratch encoding, but it still loses a few more bytes here and there. For an example of the language, the above script can be represented in GolfScratch version 0.12 as follows:

GA"n="Si0Sn["answer"]U=Rn"1"[O=%Rn2"0"[SnMRn2][Sn+*3Rn1]Ci1]["say:"Ri

This GolfScratch code generates precisely the JSON script above, except without the trailing "]]".

It is still pretty concise. I would not be surprised if a initial draft in GolfScratch rang rings round a final Java answer. Never-the-less it is a real machine readable specification that whose character count can meaningfully compared to e.g. a specification in GolfScript. It wasn't optimised for a particular golfing problem, and we know that it can't pack more than 8 bits of information per byte, so it can't be good to the point of being completely broken. It should be able to represent any Scratch program so it is just an efficient encoding, not a completely new language.

One could also perhaps define a more readable pythonesque encoding for Scratch that would be useful for explanation and review.

\$\endgroup\$
  • \$\begingroup\$ You have good points, and my suggestion does make Scratch "too good". But I don't think the JSON is the source - it's a way to keep the source plus meta-data, similarly to a Virtual Studio project. The trouble is that the source isn't textual. \$\endgroup\$ – ugoren Apr 2 '14 at 4:40
  • \$\begingroup\$ OK, I now use the term "representation" instead of "source". Does this resolve your objection? \$\endgroup\$ – gmatht Apr 2 '14 at 17:59
  • \$\begingroup\$ I accept you claims that my suggestion isn't good enough, but not your solutions. The JSON, being machine generated, doesn't work. Your GolfScratch seems to me like another language, somewhat related to Scratch but not the same one. \$\endgroup\$ – ugoren Apr 2 '14 at 18:55
  • \$\begingroup\$ We seem to disagree on what what the important factors are in scoring golf, so I have reworked my answer to focus more on my argument that byte-count of a real encoding is the most important factor in scoring. BTW, GolfScratch represents exactly the same syntax tree as Scratch and the JSON, so arguably it is just a more efficient encoding similar to how UTF8 is often more efficient than UTF16. \$\endgroup\$ – gmatht Apr 3 '14 at 14:32
  • \$\begingroup\$ In fact, the JSON file is not the only code in a Scratch project. Media files, such as the costumes of the sprites (in svg) and sound files (in mp3/wav) are included in the project, and only a md5 hash of these media files are present in the JSON. So, when these are required, having only the JSON file is not enough. \$\endgroup\$ – ace_HongKongIndependence Apr 11 '14 at 19:05
0
\$\begingroup\$

I have two very different scoring methods that i'm going to post as separate answers. Here's the other one.


I think that your scoring method is very short. Too short to be fair, perhaps.

A fairer scoring method based on this would be to count each block token (word or insert) as 1, plus constants. Also, lists and variables should count as overhead in addition to being used in a script. I'm thinking 1 byte per variable/list, plus the byte count of the name, plus treating values as constants. And using a variable in a script should be 1 token + the name of the var. Also, in your counting, you completely ignored dropdown menus. Those are also constants.

Since my explanation probably wasn't too clear, i'll just give the accounting for your example script:

enter image description here

  • when flag clicked - 3
  • ask <n=> and wait - 6 (4-token block (3 words + 1 input) + 2-char constant)
  • set <n> to <answer> - 6 (4-token block + constant n + variable answer).
  • set <i> to <0> - 6 (same as above).
  • repeat until <<n>=<1>> - 9 (3-token block "repeat", 3-token block "=", 1-character variable + variable call, constant).
  • if <<<n> mod <2>> = <0>> then - 13 (3 3-token blocks: if, =, and mod; 1-character variable + var call, 2 constants). Perhaps we can count the if as only two, since in the past it didn't have the then token.
  • set <n> to <<n>/<2>> - 11 (4-token block, 3 token division block, variable (2), 2 constants).
  • else - 1 (1 token).
  • set <n> to <<<3>*<n>>+<1>> - 12 (4-token block, 3-token blocks * and +, variable (2), 3 constants).
  • {end} - 1. We need a way to mark ending a C block.
  • change <i> by <1> - 6 (see beginning).
  • end - 1 (again).
  • say <i> - 4 (2-token block, variable (2)).
  • Overhead: 4 - 2 variables, each with 1-character names.

Total: 83.
Yes, this is over twice your count. Scratch is verbose. :)

I also want to give my take on procedures. I'll use the example script from ace's answer:

enter image description here

The define block should count as 2 tokens, plus the text inside. Inputs count the way they always do. Each time you call the block costs 1 token, plus the name of the block and any inserts.

This should total:

  • define <buz> - 5 (2-token "define" block, 3-character name of proc).
  • move <10> steps - 5 (normal score).
  • when gf clicked - 3.
  • turn clockwise <15> degrees - 6.
  • buz - 4 (1-token block call + 3-character proc name).
  • turn clockwise <15> degrees - 6.

Total: 29.

A more advanced example:

enter image description here

This should be:

  • define <jump <amount>> - 13 (2-token define, 4-character "jump", 1-token input, 6-character "amount").
  • change y by <amount> - 11 (4-token block, variable call, 6-character variable name).
  • wait <1> secs> - 4.
  • change y by <amount> - 11 (4-token block, variable call, 6-character variable name).
  • jump <10> - 9 (1-token block call, 2-token block, 4-char "jump", 2-digit constant).

Total: 48. (Wow! Functions can be expensive! Choose short names. ;))

We should also count sprites, costumes, and sounds when necessary, but i'm not going to do that right now.

\$\endgroup\$
-2
\$\begingroup\$

Edit: Seems the community didn't like the previous counting rules proposed by me, so I'm modifying them.

Blocks

Every block in every sprite counts as 1 point.

Inputs

Strings and numbers in every sprite are scored based on their length (in bytes). Colors and drop-downs are 1 point.

Variables and Lists

Variables and Lists are scored normally. If custom variables or lists alerady exist, and they don't have a value of 0, then 1 point is added for each one-sprite variable, and 1 point for each all-sprite variable.

Sprites, costumes, backdrops

Sprites are not counted. Costumes and backdrops are, but the 1st backdrop isn't counted.

Project name, instructions, notes/credits and tags

Those do not count, as they are technically not part of the source code.

Final counting

The formula used for the final score counting is:

  • bblocks
  • icombined length of all number/string inputs
  • Vnumber pre-existing variables with value not equal to 0
  • ccombined number of costumes in all sprites and all backdrops
  • b+i+V+c-2formula
\$\endgroup\$
  • \$\begingroup\$ Why should when gf clicked be excluded? That like saying in c `I'm not counting main because it's required. If something is part of the program it should be included in the source code. \$\endgroup\$ – Generic User Apr 9 '16 at 20:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .