Tips for golfing in GolfScript

Question

What, this post doesn't exist yet?

Of course, GolfScript is made for golfing, so you might think that no specific tips are really needed. But to make full use of GolfScript's features, you need to learn some non-obvious tricks. This post is for collecting such helpful tips and tricks.

To start with, here are the official GolfScript reference pages. You should really familiarize yourself with these first:

• Tutorial
• Syntax
• Built-ins
• Quick reference

In particular, I would very much suggest reading the pages in this order — the quick reference is of little use until you're already reasonably familiar with the built-ins, and the tutorial includes some important details that are not explained on the other pages.

---

Ps. For the sake of inspiration and personal interest, here are some questions I'd like to see nice answers to:

• How to do limited transliteration in GolfScript? {FROM?TO=}% works if you can be sure all the inputs are found in FROM (or don't mind them all being mapped to the last element of TO), but all the ways I've seen for leaving unmapped values unchanged have been more or less klugey.

• How to best convert a string into an array of ASCII codes and back? Which operations do this as a side effect? What's the best way to dump the characters in a string onto the stack (like ~ does for arrays)?

Answer 1

Rational / Float / Complex

I've read so many times that GolfScript has only integers that I started to believe it. Well, it's not true.

2-1? # Raise 2 to the power of -1. Result: 0.5
4-1? # Raise 4 to the power of -1. Result: 0.25
+    # Add. Result: 0.75

The output is

3/4

with the standard GolfScript interpreter and

0.75

on Web GolfScript.

Similar hacks allow to cast to Rational, Float or even Complex:

{-2.?./*}:rational
{2.-1??./*}:float
{-2.-1??./*}:complex

Answer 2

Negating a number

One thing GolfScript lacks is a built-in negation operator. The obvious ways to convert a number on the stack to its negative, like -1* or 0\-, need three chars. However, there's a way to do it in two:

~)

This works because GolfScript uses two's complement arithmetic, so that ~x equals −x−1.

Of course, the variant (~ also works; choosing between them is generally a matter of taste.

Answer 3

Shuffling an array

The easiest way to shuffle an array in GolfScript is to sort it by a random sort key. If you only need to crudely shuffle a few values, the following code will do:

{;9rand}$

Note that, even for short lists, this will not give a very good shuffle. Due to the birthday paradox, to get a reasonably uniform shuffle, the argument to rand needs to be significantly greater than the square of the length of the list being shuffled.

Replacing the 9 above with 99 thus gives reasonably good results for lists of up to ten elements, but exhibits noticeable bias for longer lists.

The following code, which uses 9⁹ = 387,420,489 possible values, is good for up to about 1000 items or so (and acceptable for up to about 20,000):

{;9.?rand}$

For really long lists, add one more 9 for 99⁹⁹ ≈ 3.7 × 10¹⁹⁷ values:

{;99.?rand}$

---

Testing:

Here's the distribution of the first element in a 10-element list shuffled using the different variants shown above, sampled over 10,000 trials:

• The output of 10,{;9rand}$0= shows a very clear bias, with 0 being more than three times as likely to end up in the first position as 1:

  0 16537 #######################################################
  1 5444  ##################
  2 7510  #########################
  3 8840  #############################
  4 9124  ##############################
  5 12875 ##########################################
  6 9534  ###############################
  7 8203  ###########################
  8 7300  ########################
  9 14633 ################################################
  

• With 10,{;99rand}$0=, most of the bias is gone, but a noticeable amount still remains:

  0 10441 ##################################
  1 9670  ################################
  2 9773  ################################
  3 9873  ################################
  4 10134 #################################
  5 10352 ##################################
  6 10076 #################################
  7 9757  ################################
  8 9653  ################################
  9 10271 ##################################
  

• With 10,{;9.?rand}$0=, the output is basically indistinguishable from a truly random sample:

  0 9907  #################################
  1 9962  #################################
  2 10141 #################################
  3 10192 #################################
  4 9965  #################################
  5 9971  #################################
  6 9957  #################################
  7 9984  #################################
  8 9927  #################################
  9 9994  #################################
  

---

Ps. For really bad shuffling of numeric arrays or strings, the following code may sometimes be acceptable:

{rand}$

It will generally be ridiculously biased, but as long as all elements of the input array (or all character codes in the string) are greater than one, it has a non-zero probability of producing any permutation of the array, which may sometimes satisfy poorly written challenge requirements.

Answer 4

To address a specific subquestion:

How to best convert a string into an array of ASCII codes and back? Which operations do this as a side effect? What's the best way to dump the characters in a string onto the stack (like ~ does for arrays)?

For those who don't understand the problem, GolfScript's type system gives priority to the types in the order integer, array, string, block. This means that ordinary array operations applied to a string almost always give you a string. E.g.

'ABC123'{)}%

will leave 'BCD234' on the stack.

As a result, the best way to convert a string into an array of ASCII codes is almost certainly to dump the characters on the stack and then gather them into an array.

What's the best way to dump the characters in a string onto the stack? {}/

What's the best way to convert a string into an array of ASCII codes? [{}/] (with the usual caveat that if there's nothing else on the stack you can skip the [)

What's the best way to convert an array of ASCII codes into a string? ''+ (Note that this also flattens the array, so e.g. [65 [66 67] [[[49] 50] 51]]''+ gives 'ABC123')

Answer 5

What is the best way to modify an array at a given index?   – user1502040

That's a good question. There's no direct way to assign a value to an array element in GolfScript, so, one way or another, you're going to have to rebuild the whole array.

The shortest general way I know to insert a new value x at index i in an array is to split the array at the given index and append x to the first half before joining them together again:

• .i<[x]+\i>+ (11 chars) - insert the value x into array at (0-based) index i

To replace the value at index i with x, we just need to shorten the second half of the array by one element:

• .i<[x]+\i)>+ (12 chars) - replace the element at (0-based) index i with the value x

Alternatively, shortening the first half instead will effectively do the same, but with 1-based indexing, which may sometimes be preferable:

• .i(<[x]+\i>+ (12 chars) - replace the element at (1-based) index i with the value x

In all the examples above, if x is a number, the square brackets around it may be omitted to save two characters, since it will be auto-coerced into an array by + anyway:

• .i<x+\i>+ (9 chars) - insert the number x into array at (0-based) index i
• .i<x+\i)>+ (10 chars) - replace the element at (0-based) index i with the number x
• .i(<x+\i>+ (10 chars) - replace the element at (1-based) index i with the number x

The brackets may also be omitted if either x or the input "array" (or both) are actually strings, in which case the result will also be coerced into a string (using the usual array → string conversion rules).

---

Ps. As a special case, if we know that the array has between i and 2 × i elements, we can insert a new element x at the (0-based) index i with i/[x]* (6 chars). What this actually does is split the array into chunks of up to i elements and insert x between each chunk. Note that, in this case, the brackets are necessary even if x is a number.

---

Pps. An alternative approach is to use dynamically named variables. For example,

 'foo' 42 ':x'\+~

will assign the value 'foo' to the variable x42, while

 42 'x'\+~

will retrieve it.

You can optimize this further by omitting the x prefix and just assigning directly to the numeric literals — this is perfectly legal in GolfScript, and allows you to save one char from the assignment code and shorten the retrieval code to just `~ (or nothing at all, if the index is constant!). The down side, of course, is that assigning to a numeric literal will override the value of that literal anywhere else in your code. Often, though, the use of number literals can be avoided (or at least restricted to the beginning of the program, before any of them are reassigned), in which case this trick is perfectly fine.

Answer 6

If your program mysteriously breaks, check your variables

I just spent a while debugging an apparently correct program which used ! as a variable (on the grounds that I wasn't going to use it again). Unfortunately I did use if, and it turns out that the implementation of if calls ! to decide which branch to follow.

Answer 7

Wrapping the top item of the stack into an array

Is there a nice way to transform ... x into ... [x]?

For full generality, the best option appears to be 4 chars. However, in certain special cases it's possible to reduce this.

1 char

] works in the special case that xis the only thing on the stack.

3 chars

[]+ works in the special case that x is an integer.

.,/ works in the special case that x is a truthy array or string. E.g. "AB".,/ gives ["AB"]; 3,.,/ gives [[0 1 2]]. However, "".,/ and [].,/ both give [].

4 chars

[.;] works unconditionally.

Answer 8

I'd like to ask the best ways to do: min, max, and absolute value. All my solutions seem to take way more characters than they should.   – Claudiu

min / max

To find the smallest / largest value in an array, just sort it and take the first / last element:

• $0= (3 chars) - minimum element in an arry
• $-1= (4 chars) - maximum element in an array

If you know the length of the array, and it's 10 elements or less, you can find the maximum in three chars by replacing -1 with the index of the last element.

If you have the values on the stack, you can just collect them into an array first. For this, an occasionally useful trick is that [\] collects the top two elements of the stack into an array, while [@] collects the top three. Thus, we get:

• [\]$0= (6 chars) - minimum of two values on stack
• [@]$0= (6 chars) - minimum of three values on stack
• [\]$1= (6 chars) - maximum of two values on stack
• [@]$2= (6 chars) - maximum of three values on stack

The same trick can also be used to find the median of three values, which can be occasionally useful:

• [@]$1= (6 chars) - median of three values on stack

---

Here's another potentially useful trick for finding the min/max of two values while leaving the original values on the stack:

• .2$>$ (5 chars) - find minimum of two values on stack, while leaving original values untouched
• .2$<$ (5 chars) - find maximum of two values on stack, while leaving original values untouched

The way it works is that .2$ clones the top two elements on the stack in reversed order (i.e. a b → a b b a), < / > compares the copies and returns 0 or 1, and scalar $ then copies either of the two input values depending on the result of the comparison.

---

If you have two nonnegative integers on the stack, you can use ,\,&, (5 chars) to find their minimum and ,\,|, (5 chars) to find their maximum. This trick uses set intersection and union, respectively, over the ranges. You can save another character if it's possible to apply , to each argument separately without having to exchange them. Since this method computes a range for each argument, it's not very efficient for larger numbers, but could be very useful for smaller inputs.

An even shorter way to find the minimum of two non-negative integers on the stack is ,<, (3 chars). Alas, this trick does not work for finding the maximum.

---

absolute value

The GolfScript built-in absolute value operator is abs (3 chars). While this is two chars more than I'd prefer, it's hard to beat in general.

In some cases (e.g. for sorting by absolute value) you might find the square of a number an adequate substitute for its absolute value; this can be computed in two chars, either 2? or .*. Thus, we get:

• {.*}$0= (7 chars) - minimum element by absolute value in array
• {.*}$-1= (8 chars) - maximum element by absolute value in array

Similarly, instead of e.g. testing if the absolute value of a number is less than 3 with abs 3< (6 chars, including space), you can test if its square is less than 9 with .*9< (4 chars, no space needed).

Answer 9

Final output manipulation

By default, when your program ends, the GolfScript interpreter outputs everything on the stack, plus a final newline, exactly as if your program ended with:

]puts

What the documentation doesn't directly mention is that the interpreter literally calls the built-in puts to produce this output, and that this built-in is literally defined as:

{print n print}:puts;

Thus, you can suppress or manipulate the final output by redefining puts, print and/or n (or   if you're feeling really twisted). Here are some examples:

Suppress final newline:

'':n;

(Of course you can leave out the ; if you don't mind an extra empty string on the stack.)

Suppress final output completely:

:puts

This overwrites puts with whatever happens to be on top of the stack. If that happens to be something you don't want to execute, you can use e.g. 0:puts; instead. Note that this also suppresses p (which is defined as {`puts}:p;), but you can still use print for output if you want.

Answer 10

Removing duplicates from an array

The set operators | (union), & (intersection) and ^ (symmetric difference) will collapse multiple array elements into one. Thus, the simplest way to remove duplicate elements from an array is to take its union or intersection with itself:

.|

or:

.&

These operators will treat strings as arrays of characters, so they can also be used to remove duplicate characters from strings.

Answer 11

Turn a string to an array of char

You can do this by typing: 1/ after it.

Example: "String"1/ pushes to stack the array ['S''t''r''i''n''g'].

This is handy when you want to move chars around the string.

Answer 12

Assigning to number literals

Often, instead of writing 1:x and then using/updating the variable x, you can just use and update 1 directly:

1:^;{^.p.+:^;}5*
{1.p.+:1;}5*       (4 bytes shorter)

Of course, this also works for other starting values, but will break if that value occurs anywhere else in your code.

Punctuation as variable names

If you have to use variables, it's also often wise to use punctuation that isn't already in your code -- lots of programs can do without &, |, ^, or ?. This way, for example, you can write &n instead of x n to push your variable and then push a newline.

Answer 13

Limited transliteration

To address a specific subquestion: given a string, what's the best way to perform a tr? E.g. tr/ABC/abc/

If all of the characters in the string will be affected, this is quite easy: {'ABC'?'abc'=}% (overhead: 9 chars).

However, that breaks if some of the characters aren't transliterated and 'ABC'? gives -1.

If the transliteration is non-cyclic it can be done one replacement at a time with string splits and joins: 'AaBbCc'1/2/{~@@/\*}/ (overhead: 15 chars). This may be improvable, but there's an alternative approach which is currently better and works for cyclic transliterations.

Currently, the shortest general solutions have an overhead of 14 characters:

• One approach involves an escape character: {.'ABC'?'abc0'=\or}%, where the 0 denotes a literal null byte. (Of course, this method is not completely general: it cannot map any other character into a null byte.)

• Alternatively, {.'ABC'?'abc'@),+=}% has the same overhead, but uses only printable ASCII characters. The @),+ is a convoluted (but, apparently, the shortest) way to ensure that the replacement string always ends with the input character.

Answer 14

Filtering an array

The most general way to filter an array is to use { },, which evaluates the code block for each element of the array, and selects those elements for which the resulting value is true (i.e. it acts like grep in Perl).

However, using the array subtraction operator - is often shorter. This operator takes two arrays, and removes every element that occurs in the second array from the first. It does not alter the order of the elements in the first array or collapse duplicates. A useful trick is to apply the subtraction operation twice to yield a non-collapsing array intersection operator:

• a b -: remove any elements found in array b from array a
• a. b --: remove any elements not found in array b from array a

---

In particular, this can be used to count the number of times an element occurs in an array:

• a.[c]--,: count the number of times the element c occurs in the array a

In general, this method is not optimal, since either of:

• a[c]/,(: count the number of times the element c occurs in the array a
• a{c=},,: count the number of times the element c occurs in the array a

is one character shorter (and, if it's OK for the count to be off by one, a[c]/, saves one character more). However, in the special case where c is a number and a is a normal array (not a string), the square brackets around c may be omitted because the - operator coerces its arguments to the same type:

• a.c--,: count the number of times the number c occurs in the array (not string!) a

(If a is a string and c is a number between 0 and 9, a.c-- will count the number of times the digit c occurs in a.)

---

A similar trick can by used to find the most common element in an array:

:a{a\[.]-,}$0=

Again, if the input is an array of numbers, the whole [.] sequence may be omitted. Alas, this does not work for strings without the [.].

Answer 15

Read from STDIN

GolfScript can read from stdin:

"#{STDIN.read}"

This will continue reading from STDIN until the EOF is reached. Alternatively:

"#{STDIN.gets}"

or

"#{STDIN.readline}"

Other things available:

getbyte
getc
gets([sep])
gets(limit)
gets(sep, limit)
inspect # perhaps useful for an underhanded contest
isatty
read([length])
readbyte
readchar
readline([sep])
readline(limit)
readline(sep, limit)
readlines([sep])
readlines(limit)
readlines(sep, limit)
readpartial(maxlen [, outbuf])

For each of these, they can only be used once (and also once for each change of the parameter, also once more with empty parentheses); after that, the original value is what you'll get instead of a new value.

Answer 16

Defining new built-in operators

The standard GolfScript interpreter has a rarely used feature that allows interpolated Ruby code in double quoted string literals.

One reason why this feature isn't more commonly used is that, awkwardly, the interpolated code is executed at compile time, and the output is cached by the GolfScript interpreter so that the same string literal will thereafter always yield the same value, even inside string eval.

However, one thing this feature turns out to be good for is defining new GolfScript operators implemented in Ruby code. For example, here's how to define a new binary addition operator that works just like the standard built-in + operator:

"#{var'add','gpush a+b'.cc2}";

It doesn't really matter where you put the definition in your code; the new operator gets defined as soon as the double-quoted string containing the Ruby code is parsed. The add operator defined above works exactly like the built-in + operator, and can be used in exactly the same way:

1 2 add          # evaluates to 3
"foo" "bar" add  # evaluates to "foobar"

Of course, defining a new addition operator is pretty useless, unless you've done something silly like erase the built-in + operator. But you can use the same trick to define new operators that do things Golfscript cannot (easily) do natively such as, say, uniformly shuffling an array:

"#{var'shuf','gpush a.factory(a.val.shuffle)'.cc1}";

10,shuf          # evaluates to 0,1,2,...,9 in random order

or printing the contents of the whole stack:

"#{var'debug','puts Garray.new($stack).ginspect'.cc}";

4,) ["foo" debug  # prints ["" [0 1 2] 3 "foo"], leaving the stack untouched

or interactive input:

"#{var'gets','gpush Gstring.new(STDIN.gets)'.cc}";

]; { "> " print gets ~ ]p 1 } do   # simple GolfScript REPL

or even web access:

"#{
  require 'net/http'
  require 'uri'
  var'get','gpush Gstring.new(Net::HTTP.get_response(URI.parse(a.to_s)).body)'.cc1
}";

"http://example.com" get

Of course, a somewhat golfier (and riskier!) implementation of the latter would be e.g.:

"#{var'get','gpush Gstring.new(`curl -s #{a}`)'.cc1}";

While not particularly golfy in itself, this lets you extend the capabilities of GolfScript beyond what the built-in commands provide.

---

How does it work?

The authoritative reference on how to define new GolfScript operators in this way is, of course, the source code for the interpreter. That said, here's a few quick tips:

• To define a new operator name that runs the Ruby code code, use:

  var'name','code'.cc
  

• Inside the code, use gpop to read a value off the stack, and gpush to push one back in. You can also access the stack directly via the array $stack. For example, to push both a and b onto the stack, it's golfier to do $stack<<a<<b than gpush a;gpush b.

  • The positions of the [ array start markers are stored in the $lb array. The gpop function takes care of adjusting these markers down if the stack shrinks below their position, but manipulating the $stack array directly does not.

• The .cc string method that compiles Ruby code in a string into a GolfScript operator is just a convenience wrapper around Gblock.new(). It also has the variants .cc1, .cc2 and .cc3 that make the operator automatically pop 1, 2 or 3 arguments off the stack and assign them to the variables a, b and c. There's also an .order method that works like .cc2, except that it automatically sorts the arguments by type priority.

• All values on the GolfScript stack are (and should be!) objects of type Gint, Garray, Gstring or Gblock. The underlying native integer or array, where needed, can be accessed via the .val method.

  • However, note that Gstring.val returns an array of Gints! To turn a Gstring into a native Ruby string, call .to_s on it instead (or use it in a context that does that automatically, like string interpolation). Calling .to_gs on any GS value turns it into a Gstring, so any GS value can be stringified with .to_gs.to_s.

• The gpush function doesn't auto-wrap native Ruby numbers, strings or arrays into the corresponding GS types, so you'll often have to do it yourself by explicitly calling e.g. Gstring.new(). If you push anything other than one of the GS value types onto the stack, any code that later tries to manipulate it is likely to crash.

• The GS value types also have a .factory method that calls the type's constructor, which can be useful e.g. for rewrapping arrays/strings after manipulating their contents. All the types also have a .coerce method that performs type coercion: a.coerce(b) returns a pair containing a and b coerced to the same type.

Answer 17

Decoding hexadecimal input

GolfScript has no hex integer literals, so, alas, you can't just parse hexadecimal input with ~. Instead, if your code must take hex input, you'll need to parse it manually.

This 8-char loop, applied to a string, will convert lowercase hex digits to their numeric equivalents:

{39%9-}%

If you have to (also) accept uppercase hex digits, the easiest (and likely shortest) solution is to first lowercase them with 32|, for a total of 11 chars:

{32|39%9-}%

Note that the output will technically still be a string (consisting of the ASCII characters 0 – 15), but most GolfScript array functions will accept strings, too. If you absolutely need an array, you can always use [{39%9-}/] (where the first [ is optional if the stack is otherwise empty).

To convert the output of the code above into an integer, you can simply use 16base (6 chars). If you want an array of bytes instead, the shortest solution I've found in simply to decode each pair of hex digits with 2/{16base}% (11 chars). All put together, the shortest code I've found to turn a hex string into a byte array is 8 + 11 = 19 chars:

{39%9-}%2/{16base}%

Note that the output of this code is indeed an array, not a string. If needed, you can stringify it by concatenating it e.g. with ""+ or, if you don't mind an extra newline at the end, n+.