1 hour later…
4 hours later…
13 hours later…
8:26 PM
@petStorm @mypronounismonicareinstate @cairdcoinheringaahing @AviFS @Razetime @Dion @DLosc we're starting
This lesson assumes:
- knowledge of stack-based languages (i.e. how stacks work)
- understanding of the fizzbuzz problem
This lesson does not assume:
- knowledge of Vyxal
By the end of this lesson, you will hopefully:
- have a basic understanding of how Vyxal works
- learn golfing techniques you can apply to other languages
- gain language design ideas
- knowledge of stack-based languages (i.e. how stacks work)
- understanding of the fizzbuzz problem
This lesson does not assume:
- knowledge of Vyxal
By the end of this lesson, you will hopefully:
- have a basic understanding of how Vyxal works
- learn golfing techniques you can apply to other languages
- gain language design ideas
When learning a new programming language, figuring out how to write a FizzBuzz program can help learn the syntax and flow of a language: loops, conditional command execution and arithmetic are all covered while outputting the required text. Today's lesson will focus on writing FizzBuzz using Vyxal and golfing it down to 18 bytes.
Before we begin writing any code, I'll explain what Vyxal is and what it is designed for. Vyxal is my most recent esolang (which should be kind of obvious given its name), which focuses on performing well in code golf (competitions where participants try to answer questions with as short a program as possible). It is also designed to retain an aspect of "elegance" whilst remaining terse.
FOR i = 1 TO 100 IF i % 15 == 0 THEN PRINT "FizzBuzz" ELSEIF i % 5 == 0 THEN PRINT "Buzz" ELSEIF i % 3 == 0 THEN PRINT "Fizz" ELSE PRINT i ENDIF NEXT i
1 101 r (i| # FOR i = 1 TO 100 ¥i 15 % 0 = [ # IF i % 15 == 0 THEN `FizzBuzz`, # PRINT "FizzBuzz" | ¥i 5 % 0 = [ # ELSEIF i % 5 == 0 THEN `Buzz`, # PRINT "Buzz" | ¥i 3 % 0 = [ # ELSEIF i % 3 == 0 THEN `Fizz`, # PRINT "Fizz" | # ELSE ¥i , # PRINT i ] ] ] `\n`, )
(Yes, it is highly formatted and commented. Obviously, as we continue, we'll lose the more formal stuff)
- The main control structures are delimited by brackets: this is an intentional break away from the tendency of most golfing languages to use letters to designate things like if-statements and loops
8:34 PM
The part that seems to un-necessarily convolute our current program is the repeated usage of the loop variable
i
. To fix this, we can drop the explicit variable altogether and use the implicit context variable of the for loop.
Within Vyxal, the contextual variable (there is only one) is used to store values associated with different structures. In other words, the context variable has different values based upon its, well, context.
In a for loop, the context variable holds the current iteration value.
In a while loop, the context variable holds the result of the most recent evaluation of the while loop's condition.
If statements don't have a context variable assigned.
In functions and lambdas, the context variable holds the argument(s) passed to the function upon calling.
In a while loop, the context variable holds the result of the most recent evaluation of the while loop's condition.
If statements don't have a context variable assigned.
In functions and lambdas, the context variable holds the argument(s) passed to the function upon calling.
8:40 PM
Our current approach is now shorter, but it still isn't short enough to be considered competitive. What if, instead of checking 3 different modulos, we only check 3 and 5, print each respective word depending on the divisibility and then, if nothing is printed, print the index:
FOR i = 1 TO 100 output = "" IF i % 3 == 0 THEN output += "Fizz" ENDIF IF i % 5 == 0 THEN output += "Buzz" ENDIF IF output == "" THEN PRINT i ELSE PRINT output ENDIF NEXT i
In this iteration, a few new features are introduced:
- `&` acts as a register, and toggles between popping the top of the stack into the register and emptying the register onto the stack (much like ><>)
- Empty strings are regarded as falsey when tested as a boolean value
- `&` acts as a register, and toggles between popping the top of the stack into the register and emptying the register onto the stack (much like ><>)
- Empty strings are regarded as falsey when tested as a boolean value
This approach is good, but what if instead of using a flag to keep track of the output, we short-circuit or'd the register with n? Here's a table of the three possible combinations (note that n is always >0):
Also, because our if statements only have one branch (an if statement without a pipe
|
consists of code to only be executed if the top of the stack is truthy), we can multiply the strings by the result of the comparison: 0 * string = empty string; 1 * string = string. Note that this wouldn't work if the result of n<>%0=
had more than two possible results.
FOR I = 1 TO 100 PUSH "Fizz" PUSH I PUSH 3 MODULO PUSH 0 EQUALS MULITPLY // "Fizz" * ((I % 3) == 0) PUSH "Buzz" PUSH I PUSH 5 MODULO PUSH 0 EQUALS MULITPLY // "Buzz" * ((I % 5) == 0) ADD PUSH I LOGICAL OR PRINT TOP PRINT "\n" NEXT I
Thus far, we've mostly been using variables/registers to keep track of values. However, we can make our program shorter by utilising the stack mechanics of Vyxal. Consider the following pseudocode:
However, we're still not finished yet. For the next byte reduction, we can look at minimizing the
0=
right after each modulo.
If we look at the function of `0=`, we can see that it is acting as a logical NOT operation, inverting the truthiness of the item it's comparing. Let's take a look at an example where we are testing for divisibility by 3:
When the result of `n % 3` is 0, we want to say that we DO need to multiply the string `"Fizz"`: `0 == 0 => 1`. In this way, it NOTs the `0`
Conversely, when the result of `n % 3` is 1 or 2, we want to say that we DO NOT need to multiply the string `"Fizz"`: `1 == 0 => 0` and `2 == 0 => 0`. In this way, it NOTs the truthiness of 1 and 2.
When the result of `n % 3` is 0, we want to say that we DO need to multiply the string `"Fizz"`: `0 == 0 => 1`. In this way, it NOTs the `0`
Conversely, when the result of `n % 3` is 1 or 2, we want to say that we DO NOT need to multiply the string `"Fizz"`: `1 == 0 => 0` and `2 == 0 => 0`. In this way, it NOTs the truthiness of 1 and 2.
@cairdcoinheringaahing You're right about the string compression, but you will be surprised at how we insert the newlines as we get further down.
We're still at 37 bytes (same length as the shortest known APL FizzBuzz, placing us 25th on the leaderboard)
8:50 PM
BEGIN Function(index) PUSH "Fizz" * is_divisible(index, 3) PUSH "Buzz" * is_divisible(index, 5) ADD PUSH index LOGICAL OR RETURN END FOR I = 1 TO 100 PRINT Function(I) PRINT "\n" NEXT I
Well, what if, instead of explicitly looping, there was a way to apply the function to each item in the range?
In this approach, the loop has been changed into a mapping of the function to the list generated by
1 101r
@f:1|...;
: This defines a function called f
which takes a single parameter. Functions are defined as @name:parameters|code;
and called as @name;
°f;
pushes a function reference of f
. Think of this as if you wrote the name of a function in python without the brackets: a = f(x)
calls the function while a = f
assigns the reference of function f to a.
You may be wondering how we can reduce this program when it's clear that the function definition can't be shortened. Notice that we use
f
straight away, we only pass it a single parameter and that we only want a single result. If this was a language like Python, one might suggest using a lambda to eliminate the need for clunky definition syntax. So why don't we do the same in this situation:
Here,
λ...;
defines a lambda (a function that is only accessible via being on the stack) and pushes its reference. Think of it like this: @name:p|...
defines a function that is globally accessible and can be easily reused hundreds of times. λ...;
pushes its function onto the stack as a single encapsulated block and is only usable when its reference is on the stack or in a variable.
Like most golfing languages, when there aren't enough values on the stack to complete an operation, Vyxal takes implicit input and uses that instead. However, this behaviour is different when control flows moves inside a function/lambda call: rather than cycling through the global input of the program, the implicit value provided is the argument(s) passed. (Side note: functions/lambdas operate on their own local stack initialised with the values passed).
At the start of the lambda, n is the only value on the stack, so we can turn
n3œ
into 3œ
because the n
is already provided. We can't do that with n5œ
because the result of the previous multiplication will occupy the stack.
Another thing we can improve is the generation of the range between 1 and 100. Vyxal, like other golfing languages, has built-ins for different ranges based on a single number:
[0, n]
, [0, n)
, [1, n]
, [1, n)
. In the case of FizzBuzz, we want the range [1, 100]
, so we need the [1, n]
range built-in. The reference page tells us that this command is ɾ
. Therefore, 1 101r
becomes 100ɾ
.
We're still 10 bytes away from the shortest known Vyxal FizzBuzz. A quick golf that can be made is string compression: Vyxal has both dictionary and base 255 compression utilities. In this instance, we'll use dictionary compression.
Vyxal's dictionary has approximately 20,000 words that can be used within strings. Each word in the dictionary has a unique two-letter code called a "String Compression Code" (SCC). Really, the SCC is simply the index of the word in the dictionary converted to a bijective base with an alphabet based on the non-ASCII characters on the Vyxal codepage. To use an SCC, simply place it in a string. For example:
Turns into
Hello, World
. Note that the punctuation and whitespace are retained but the SCCs are converted to their respective words. The SCCs for Fizz and Buzz are Ɗ»
and ŨƇ
respectively. Using this gives us:
However, this can still be improved by changing the strings involved: because we only need one SCC per string, we can utilise a feature found in other golfing languages were a single dictionary string can be constructed without the need for a closing character.
ı
pushes a single uncompressed SCC to the stack:
9:22 PM
At this stage, we are 2 bytes away from tying with Jelly. This byte reduction can be achieved through the introduction of a new structure: lambda maps. A lambda map is a lambda that instantly maps its function to the top of the stack, removing the need for an explicit
M
. Its structure is ƛcode;
and is equivalent to λcode;M
(fun fact, the parser turns the lambda map into a lambda token followed by the M command - that's how equivalent it is). We can turn our program into:
What we have works for 20 bytes except for the fact that it actually isn't a valid answer. It maps from 0 to 100 not 1 to 100. Luckily, there's a fix for this that doesn't require the addition of bytes: command-line flags. (We're getting into some contested territory now, so fasten your seatbelts!)
When the Vyxal interpreter is run on the command line with the
h
flag and no other file, a list of all available flags is printed to the console:
Usage: python3 Vyxal.py <file> <flags (single string of flags)> <input(s) (if not from STDIN)> ALL flags should be used as is (no '-' prefix) j Print top of stack joined by newlines L Print top of stack joined by newlines(Vertically) s Sum/concatenate top of stack on execution M Use 1-indexed range [1,n] for mapping integers m Use 0-indexed range [0,n) for mapping integers v Use Vyxal encoding for input file c Output compiled code
(This feature is courtesy of @Razetime: go upvote his posts and star his Github repositories please.)
The
M
flag looks like it will help our situation. It makes lambda maps map over the range [1, n] instead of [0, n]. Now our 20-byte answer is valid with the M
flag. (I'm not going to show the program again as nothing has changed but the command-line flags).
We've tied with Jelly now (at least Dennis' answer). But I'm not done yet. Notice how there is a
j
flag which joins the top of the stack by newlines. We can use this to remove the IJ
which explicitly joins with newlines:
To knock off that final byte to get to 18, we can use the auto-completion of structures. If a structure is unbalanced (e.g.
...[...
or ...ƛ...
gets turned into ...[...]
and ...ƛ...;
at parse time).
And that is how you get FizzBuzz in 18 bytes. Hopefully, this has made some sort of sense, and hopefully, you'll be ableto apply some techniques learnt here to other golfing endeavours.
« first day (382 days earlier) ← previous day next day → last day (1256 days later) »