Discuss Scratch

CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

This Advanced Topics Challenge is now over.
It was a long battle, but I think that for most of you it was worth it. Even if you didn't win, you did something that few people have ever done - you created a programming language. Not just any language, but one designed to have short programs - which you made as well.
Without further rambling, here are the results:
1st place: MartinBraendli with Tee++
As the winner of ATC#5, you may now create ATC#6, or designate someone else to do so. You may also wear this medal in your signature.
2nd place: dzaima with BYTT. You may wear this medal in your signature.
3rd place: Random-man with Legar. You may wear this medal in your signature.

Rankings can be found here

Honorable mentions:
These Scratchers not just created a successful codegolfing language, but also created 10 (or more) successful programs to beat some rather tricky challenges. They may wear the ATC#5 ribbon in their signature with pride, if they wish.
MartinBraendli with 15/15 completed
dzaima with 13/15 completed
wizzwizz7 with 12/15 completed
Random-man with 11/15 completed
m99900 with 10/15 completed

Original post:

Challenge Overview
This competition will run in stages. First, you will design your own codegolfing language. If you don't know what that is, no problem, it's explained under Preparation. Then, you'll write an interpreter in Scratch that runs programs in your language. Requirements for the language and interpreter are listed below. Finally, after the Stage 1 deadline, I'll release 15 codegolfing challenges. You'll then have to write programs to beat the challenges, in your own language, to be executed by your own interpreter. You'll ultimately want your programs to be shorter than everyone else's. More details about everything are below.
Preparation
Before you begin, you should definitely check out the codegolf stackexchange to get a good idea of what codegolf is. A codegolf challenge is a challenge where you must make the shortest program (in bytes) that performs a specific task. Most ‘normal’ languages (such as Java or Scratch) aren't made for this, they're made to be usable - so they aren't the best choice of language. Many people have made ‘golfing languages’ where simple tasks can be accomplished in very small amounts of code - and this is what you're going to do. It is strongly suggested to actually invent the language, or a large chunk of it, before programming your interpreter.
Stage 0: Inventing your language

Specifications:
  • Your language must actually be yours. Don't mimic specific aspects of another programming language. If you have seen a method used in multiple other languages, it is acceptable to use. If you have only seen it in one language, you probably shouldn't use it.
  • Your language must only use ASCII characters 32 through 126 (below). If you have fewer (or more) than 95 commands, you may encode your programs to use all 95 characters. Bottom line, if a program requires some other character to operate correctly, it is invalid.
  • Your language should be Turing complete. This is not a requirement, but if your language isn't Turing complete, you will probably not win.
  • Your language will be required to handle numbers: only real numbers will be required, and you will not be required to give answers any more precise than those that Scratch does by default. Using basic Scratch Operator blocks is suggested.
  • Your language will be required to handle strings: strings of characters from the length of 0 to 10240, inclusive. Support for ASCII characters 32 through 126 (below) is required.
'Handle' means that a program must be able to input or output a data type at any time during execution. It must be able to manipulate that data type in any way asked.

Your language is otherwise up to you to define. You are encouraged to add internal booleans, stacks, and lists if you think they could be useful.

Optionally, click this link and fill out the form to document your language. Then share it with me (ac8774@gmail.com) and I'll put it in this folder.

List of ASCII characters 32 through 126 (includes a space at the beginning):
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Stage 1: Creating your interpreter

Rules:
  • Your interpreter must be a Scratch project shared by an account that you control.
  • Don't use any code (Scratch blocks or translated from another language) from an interpreter created by someone other than yourself.
  • There should be a clearly marked button (or the flag) which opens an ask box where code can be pasted. Your interpreter must then execute the code without further interaction required.
  • You must take input by means of an ask box (again for quick copying and pasting) and display output by adding data to a list.
  • Your interpreter must be added to this studio: ATC#5 Submissions Studio

Your interpreter must be added to the submissions studio before this date:
Monday, August 8th 11:59 PM ET
At that time, I will download all submitted interpreters to my computer. We will use the online projects for testing, but if there is suspicion of changes, I will check with my copy.
After the deadline, you will not be allowed to modify your language or interpreter. Any changes (besides visual) to your project after the deadline are grounds for disqualification.
Stage 2: Codegolfing
As of posting this topic, I have already chosen several (15) challenges for you to attempt. In order for you to complete each one, you must write a program in your submitted language that performs the specified action. The program must successfully run in your interpreter and produce results identical to the given test cases. The 15 challenges are as follows:
  • 5 Simple Challenges: These challenges ask you to perform a simple function. Most programs will be 1-10 characters long.

  • 5 Intermediate Challenges: These challenges ask you to perform multiple simple functions or a somewhat complex function. Most programs will be 10-100 characters long.

  • 5 Hard Challenges: These challenges ask you to perform a complex operation. Successful programs will probably be over 100 characters long.
The challenges will be placed in the post below this one. There are example challenges there now.

If your language is Turing complete and follows all specifications, all challenges are possible.
You don't have to complete all of the challenges, but you should complete as many as you can. Successfully completing ten challenges earns you a ribbon.

I will choose a deadline for this Stage once Stage 1 is over.
By that deadline, you must put your programs into the Instructions or Notes & Credits of your interpreter, clearly labeled. Also include the length of each program (I'll double-check, but it's more convenient for everyone else this way).
Scoring
I'll check the validity and lengths of all programs, and put the lengths in a big Google Sheet so that everyone can see them. Rankings will be determined for each challenge. The shortest program wins, and any languages without a program come in last. Then I'll sum up the rankings for each language. The language with the smallest summed rank wins!
Miscellaneous:
  • You can make as many languages and interpreters as you'd like, as long as each is properly submitted.
  • You can encode your language to convert from base 95 to a lower base, as long as the conversion process doesn't last too long. For longer programs, you should also provide the binary or other base equivalent to be executed (to save time). The shorter program's length will be used in scoring. (If you are found to have lied about the length of the encoded program, you will be disqualified (unless it was clear that you made an unintentional error).)
Don't mix up these words!
  • A programming language is just like a spoken language - it is not a physical or representable thing, but it can be described by a dictionary or list of syntax and commands. You will invent at least one language.
  • A program is written in a language. It performs a specific task. You will be asked to write one program in Scratch (your interpreter) and ~15 programs in the language which you create.
  • An interpreter executes a program. You will create at least one interpreter.
This is a challenge for programmers, not lawyers. The goal is not to find legal loopholes.

Last edited by CodeLegend (Aug. 19, 2016 04:20:50)

CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

Stage 2 has begun! Here are your challenges.
Most challenges have one or more test cases. “->” indicates switching between input and output. All test cases start with input or “->”.
Some challenges have examples written in Scrack.

1. FFFFFF
Output 16777215.
Test case: -> 16777215
Scrack example: 88^D
2.
Write a program that does nothing, and runs indefinitely.
Scrack example: 1@
3. Cat Cat Cat Cat Cat Cat Cat Cat Cat Cat
Input a string, then output it. Repeat this ten times total.
Test case: "test" -> "test" -> "testing" -> "testing" -> "Test" -> "Test" -> "test!" -> "test!" -> "test." -> "test." -> "1234" -> "1234" -> "lol test" -> "lol test" -> "test?!?" -> "test?!?" -> "tset" -> "tset" -> "test" -> "test"
Scrack example: ar|
4. Superpower
Input a number. Assume it is positive. Output that number raised to its own power.
Test case: 4 -> 256
Test case: 0.5 -> 0.7071068
Test case: 4.555535705 -> 1000
Scrack example: .^
5. Slippery _____
Input four numbers. Assuming they are a, b, c, and d, in order, output (b-d)/(a-c) or (d-b)/(c-a).
Test case: 0 0 1 1 -> 1
Test case: 3 2 1 6 -> -2
Test case: 7.75 1.7 7.8 -60 -> -1234
Scrack example: ~?-?;_\



6. guess the password
Output "guess the password", then take input from the user. If the user returns "the password", end
the program. Otherwise, start from the beginning, and continue outputting "guess the password" until
the user gives "the password". Case sensitivity is optional.
Test case: "guess the password" -> "the password"
Test case: "guess the password" -> "foo" -> "guess the password" -> "the password"
Test case: "guess the password" -> "password" -> "guess the password" -> "1234" -> "guess the password" -> "the password"
Scrack example: "guess ""the password":+|.$=!(f@)Z
7. No joking
Input a number; assume it is between 1 and 51, inclusive. Output the number of possible hands of
playing cards given that many cards.
Test case: 2 -> 1326
Test case: 5 -> 2598960
Test case: 7 -> 133784560
Scrack example: y52i.i_!,!*i!\
8. 99 bottles of what?
Input a string. Then output the lyrics to the song "99 Bottles of Beer", but replace every instance
of "beer" with the inputted string. Lyrics can be found here:
http://www.99-bottles-of-beer.net/lyrics.html
Scrack example: " bottles of "i" on the wall"j"Take one down and pass it around, "k"1 bottle of "nuo moreoly99mmDDfERmiljy, milz.AmDMkmiljz.Amiljy, milz.Aknljz.Anljy, nlz.Akznoiljz.AzNoiljx, noilz.A"Go to the store and buy some more, 99"iljz.A
9. 9.
Write a program that outputs its own source code. You may not exclusively use tokens that return
themselves, and you may not use any commands that return the program's source code. Your program
must have a nonzero length. You may output the source code in any form that can be executed by
your interpreter.
This program is called a quine. If your language is Turing complete, then you are guaranteed to be
able to write a quine. Before complaining that this is too difficult/impossible, do a little research
and you may find that it isn't so hard after all. (unless, of course, you have a compressed
language... It is still technically possible, but could be very difficult, depending on how you
handle string literals. I've allowed compressed languages to output their source in any form
to try to make the process less painful.)
Scrack example: "Q,:A"Q,:A
10. Who's that Pokemon?
Input a string. Assume that it is either "Bulbasaur", "Ivysaur", "Venusaur", "Charmander",
"Charmeleon", "Charizard", "Squirtle", "Wartortle", "Blastoise", or "Ditto". Output that
Pokemon's Pokedex number (1-9 in order). If the input was "Ditto", you can output any
number from 1 to 721.
Test case: "Squirtle" -> 7
Test case: "Ditto" -> [up to program creator's discretion] 1
Test case: "Venusaur" -> 3



11. sorry
Input two strings. Output the total number of instances that they occur in each other. Case sensitivity
is optional.
Test case: "aba" "ababa" -> 2
Test case: "hi" "hello" -> 0
Test case: "www" "wwwww" -> 3
Test case: "!@#$" "!@#$" -> 2
12. sorry not sorry
Input a number, p. Assume it is an integer larger than 2. Then input 2*p numbers. These numbers form
(x,y) coordinate pairs, and they are the vertices of a p-sided polygon (no intersecting line segments).
Output the area of the polygon.
Test case (parentheses added for readability): 4 (0 0) (1 0) (1 1) (0 1) -> 1
Test case: 3 (-2 -2) (10 0) (-1 7.7) -> 57.2
Scrack example: ppD4R??ss??.,~.,~p7RI*~i*-,pDr+2/U
13. sheesh
Input a number, p. Assume it is an integer larger than 1. Then input 2*p numbers. These numbers form
(x,y) coordinate pairs, representing points which all lie on the graph of a (p-1)-degree polynomial
function. Output the coefficients of the polynomial.
Test case: (parentheses added for readability): 2 (1 1) (2 3) -> 2 -1
Test case: 3 (1 1) (2 3) (3 -5) -> -5 17 -11
Test case: 4 (1 1) (2 3) (3 -5) (-8 5.3) -> -.47707 -2.13758 11.75222 -8.13758
14. wow I'm just evil
Input a string. Then input two numbers. Assume they are between 2 and 10, inclusive. Assume the given
string is a number in base (1st inputted number). Output the same value in base (2nd inputted number).
Test case: "1010" 2 10 -> "10"
Test case: "1010" 10 2 -> "1111110010"
Test case: "247" 8 9 -> "205"
15. you all must hate me
Input a string. Assume that it is composed exclusively of these characters: "1234568790-+*/". Assume
that any operator (-+/*) is preceded and followed by a number. Simplify the expression following
standard mathematics and output the numerical result. Rather than list all of the rules of standard
mathematics, I'll say that the result should be identical to using eval() in Javascript or typing the
string into a Google search.
Test case: "1+1" -> 2
Test case: "2*3+4/5-6" -> 0.8
Test case: "105*4*0+3/9*10" -> 3.3333333

Write a separate program for each challenge that you attempt. Completing ten challenges earns you a ribbon.
Place the code for each challenge in the Instructions or Notes & Credits of your project. If decompression of your code takes more than several seconds, please also provide a decompressed version. The length of the compressed version will be used in scoring. Scoring will be done here.

Now that the Stage 1 deadline is up, you may not make changes to your interpreter EXCEPT:
  • visual improvements
  • changing the I/O methods to conform to the rules if you didn't already
  • changing TUI/GUI to quickly allow users to run your programs
  • approved bug fixes
I've downloaded all of your projects, so I'll know if you've followed the rules.
Bottom rule: don't make changes to your language.

Stage 2 ends:
August 18th 11:59 PM ET


EDIT 1: added newlines so that less scrolling is needed
EDIT 2: added Scrack examples for first five challenges
EDIT 3: added 3 more examples
EDIT 4: added 99 bottles example
EDIT 5: added area example
EDIT 6: slightly modified 99 bottle program to add a period to the end (darn!)
EDIT 7: slightly changed quine rules
EDIT 8: shortened Scrack example 5

Last edited by CodeLegend (Aug. 11, 2016 23:19:53)

CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

This seems like so much fun that I'll also create a language and compete alongside you guys… Don't worry, I won't take advantage of knowing the challenges and I won't factor myself into the scoring

EDIT: Program explanations:
88^D
8 push 8 (8)
8 push 8 (8,8)
^ pop twice, push result (16777216)
D pop, decrement, push result (16777215)
implicit output (16777215)



1@
1 push 1 (1)
@ pop and goto 1



ar|
a push 10 (10)
r pop and repeat the next character that many (10) times
| implicit input, output



.^
. implicit input, pop and push double (a,a)
^ pop twice, push push result (a^a)
implicit output (a^a)



~?-?;_\
~ implicit input twice, flip last two on stack (b,a)
? input (b,a,c)
- pop twice, push result (b,a-c)
? input (b,a-c,d)
; take from the bottom of the stack and put it on the top (a-c,d,b)
_ pop twice, push result (_ is identical to ~-) (a-c,b-d)
\ pop twice, push result (\ is identical to ~/) ((a-c)/(b-d))
implicit output ((a-c)/(b-d))



"guess ""the password":+|.$=!(f@)Z
"guess " push "guess " ("guess ")
"the password" push "the password" ("guess ","the password")
: double duplicate (ab->abab) ("guess ","the password","guess ","the password")
+ pop twice, push result (concatenates strings) ("guess ","the password","guess the password")
| pop and output "guess the password" ("guess ","the password")
. pop and duplicate ("guess ","the password","the password")
$ input a string ("guess ","the password","the password",a)
= pop twice, push result ("guess ","the password",(true or false))
! pop and push result (logical not) ("guess ","the password",(false or true))
(f@) run if true
f push 23
@ pop and goto 23 (":")
Z empty the stack to prevent implicit output



y52i.i_!,!*i!\
y52 push 52 (52)
i pop and set i ()(i=52)
. implicit input and duplicate (a,a)(i=52)
i push i (a,a,52)(i=52)
_ pop twice and push result (a,52-a)
! pop and push result (a,(52-a)!)
, pop and send to top of stack ((52-a)!,a)
! pop and push result ((52-a)!,a!)
* pop twice and push result ((52-a)!*a!)
i push i ((52-a)!*a!,52)
! pop and push result ((52-a)!*a!,52!)
\ pop twice and push result ((52!)/((52-a)!*a!))
implicit output ((52!)/((52-a)!*a!))



" bottles of "i" on the wall"j"Take one down and pass it around, "k"1 bottle of "nuo moreoly99m
" bottles of "i i=" bottles of "
" on the wall"j j=" on the wall"
"Take one down and pass it around, "k k="Take one down and pass it around, "
"1 bottle of "n n="1 bottle of"
uo moreo o="o more" (u delimits 6-char literal)
l l=implicit input
y99m m=99 (y delimits 2-char literal)

mDDfERmiljy, milz.AmDMkmiljz.A
mDD put 97 on the stack
fE put 24 on the stack (f=23,E=increment)
Rmiljy, milz.AmDMkmiljz.A repeat this 24-length string 97 times
milj put vars m, i, l, and j on the stack
y, put ", " on the stack
mil put vars m, i, and l on the stack
z. put "." on the stack
A concatenate the stack and output
mDM m=m-1
kmilj put vars k, m, i, l, and j on the stack
z. put "." on the stack
A concatenate all and output

miljy, milz.Aknljz.Anljy, nlz.Akznoiljz.A
miljy, milz.A explained before
knljz. put k, n, l, j, and "." on the stack
A concatenate all and output
nljy, nlz. put n, l, j, ", ", n, l, and "." on the stack
A concatenate all and output
kznoiljz. put k, "n", o, i, l, j, and "." on the stack
A concatenate all and output

zNoiljx, noilz.A"Go to the store and buy some more, 99"iljz.A
zNoiljx, noilz. put "N", o, i, l, j, "x, ", n, o, i, l, and "." on the stack
A concatenate all and output
"Go to the store and buy some more, 99" put this string on the stack
iljz. put i, l, j, and "." on the stack
A concatenate all and output



"Q,:A"Q,:A
"Q,:A" push "Q,:A" ('Q,:A')
Q push the quote character ('Q,:A','"')
, send to the end of the stack ('"','Q,:A')
: double duplicate ('"','Q,:A','"','Q,:A')
A concatenate all and output " Q,:A " Q,:A



ppD3R??:??.,~.,~p7RI*~i*-,pDr+2/U
p p=input
pD push p-1
3R??: repeat "??ss" p-1 times
?? push input twice
: double duplicate
?? push input twice
., insert a copy of the last stack item to the beginning of the stack
~.,~ insert a copy of the 2nd to last stack item to the beginning of the stack
p7RI*~i*-, repeat "I*~i*-," p times
I i=pop
* pop twice and multiply
~ switch last two stack items
i push i
* pop twice and multiply
- pop twice and subtract
, send result to top of stack (to be summed next)
pDr+ repeat "+" p-1 times (there should be p items in the stack, so this will sum up the stack)
2/ divide result by two
U absolute value

Last edited by CodeLegend (Aug. 12, 2016 20:57:43)

birdoftheday
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

first

Am I the only person who likes 3.0 better than 2.0, or do the people who do just not talk about it?
m99900
Scratcher
48 posts

[ATC#5] Codegolfing to the Extreme!

edit:nevermind

Last edited by m99900 (July 22, 2016 19:48:25)



Spelling issues? I have a friend who can help
<((foo)+(bar))=[foodbar?]>
Make your urls readable
M99900….~making impossible things possible~

CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

m99900 wrote:

just a clarification would https://scratch.mit.edu/projects/62829656/ this project work?
As far as I can tell, yes, but you would want to make a duplicate of it that asks for code as soon as you press the flag.
IcyCoder
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

I am good at this!

Because JS is the future (echos) future future futur futu fut fu f
TheMonsterOfTheDeep
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

Aw snap I'm going on vacation tomorrow so I don't know if I will be able to participate.

my latest extension: 2d vector math
Macie1234
Scratcher
100+ posts

[ATC#5] Codegolfing to the Extreme!

0–0
^
____

I'm gonna try this…


PullJosh
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

Ooooh, I like this…

Base 10 is the best number system.
IcyCoder
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

I am working hard on mine!

Because JS is the future (echos) future future futur futu fut fu f
gtoal
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

TheMonsterOfTheDeep wrote:

Aw snap I'm going on vacation tomorrow so I don't know if I will be able to participate.
Ditto. If I were around to compete… what I'd do is:

not invent a language as such, but a compact bytecode for a VM. Which *is* a language, just not a very human-usable one. But as long as the bytecode could have been produced by hand, it would pass the test.

The majority of language constructs would then reduce to a single character. For a few common combinations of instructions, a peephole optimisation would conflate a couple of sequential operations to a single character.

The bytecode would quite likely be stack based and a textual dump of the Abstract Syntax Tree.

Then for the programs, I'ld write a compiler that took a more readable language and compiled it down to that bytecode. (for extra kudos I'ld write the compiler in Scratch ;-) )

G
CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

TheMonsterOfTheDeep wrote:

Aw snap I'm going on vacation tomorrow so I don't know if I will be able to participate.
Oh no missing internet or missing internet and a computer?

PullJosh wrote:

Ooooh, I like this…
Yay, glad to hear it!

IcyCoder wrote:

I am working hard on mine!
Remember that planning is a very important part of the process…
CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

gtoal wrote:

TheMonsterOfTheDeep wrote:

Aw snap I'm going on vacation tomorrow so I don't know if I will be able to participate.
Ditto. If I were around to compete… what I'd do is:

not invent a language as such, but a compact bytecode for a VM. Which *is* a language, just not a very human-usable one. But as long as the bytecode could have been produced by hand, it would pass the test.

The majority of language constructs would then reduce to a single character. For a few common combinations of instructions, a peephole optimisation would conflate a couple of sequential operations to a single character.

The bytecode would quite likely be stack based and a textual dump of the Abstract Syntax Tree.

Then for the programs, I'ld write a compiler that took a more readable language and compiled it down to that bytecode. (for extra kudos I'ld write the compiler in Scratch ;-) )

G
I was hoping someone would try this… Sorry that you won't be able to either

To anyone who wants to try what gtoal explained, remember that you can only use the 95 listed characters in your language.
-stache-
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

Can,we use s-expressions?


3x3 pb: 13.240
3x3 avg: ~21-26
ilikelegos
Scratcher
100+ posts

[ATC#5] Codegolfing to the Extreme!

Oh fun! I needed to this anyways.

EDIT: One question: Does our language by anymeans have to “readable”? For example, could I have single alt-characters to stand for 2, or maybe even 3 characters of normal code?

Last edited by ilikelegos (July 22, 2016 20:22:45)


Hey! I'm just a kid who loves programming, Rubik's Cubes, and obviously Lego!
CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

-stache- wrote:

Can,we use s-expressions?
Sure! A good rule of thumb is that if it's used in multiple languages, you can use it in yours.
PullJosh
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

CodeLegend wrote:

To anyone who wants to try what gtoal explained, remember that you can only use the 95 listed characters in your language.
Maybe that should be made more clear in the instructions. I was planning on creating a language which had one character for every instruction you could possibly need.

Base 10 is the best number system.
IcyCoder
Scratcher
1000+ posts

[ATC#5] Codegolfing to the Extreme!

A demo of my language:

It is called repeat after me!

 =

Space is ask
= prints

Because JS is the future (echos) future future futur futu fut fu f
CodeLegend
Scratcher
500+ posts

[ATC#5] Codegolfing to the Extreme!

PullJosh wrote:

CodeLegend wrote:

To anyone who wants to try what gtoal explained, remember that you can only use the 95 listed characters in your language.
Maybe that should be made more clear in the instructions. I was planning on creating a language which had one character for every instruction you could possibly need.
I mean, it's somewhere in there…
I'm on a phone now so I'll wait until I get home to edit the first post.

Powered by DjangoBB

Standard | Mobile