Golfing Task #1 - Randomly Reduced

For those who want to see the absolutely minimal solution to a Task, advanced users who want to fine-tune the Task down to as small as possible (and often unreadably so, certainly without comments, and usually extra tweaks and tricks to reduce code)

See Code.Golf for an amazing collection/game

See also: RosettaCode

Also Tixy.land (especially #tixy.land on Twitter) is a great place to code golf graphic patterns.

Feel free to post golfed Task #1 here. Not meant for newbies to use as example code (at first…)

As I’ve been golfing, I wanted to acknowledge a few interpretations that have affected my minimal
LLOC:

  1. Random means perceived as random to the end user, which is subjective, but avoids bikeshedding
  2. Correlations are allowed, such as using the same random variable to drive both hue and index, but a superior solution avoids an observation that is easy to point out to someone: “Did you notice all the red blips are super short?”
  3. For golf, I defined “twinkling” as having a local minima in brightness value within one pixel being lit, thus disqualifying some of the early stuff I came up with pulsing desaturation. This makes it harder.
  4. Some variable amount of darkness between pulses is assumed to be required (a strict reading of the requirements doesn’t seem to imply this) - also makes it more challenging.
1 Like
  1. I had to lookup bikeshedding

  2. I assumed all of the random bits were separately random. All red lights being the same duration isn’t random.

  3. That’s a really strict defining of Twinkle. I left it more vague. Pulsing isn’t twinkling though, is it? Twinkling is to blink, to wink, to scintillate. I’d say random twinkling avoids regular patterning, and changes (color, brightness, etc, so any change to HSV would do that)

  4. I did mean it would do one pixel, then (hopefully short) random interval, then do a new one. If it did a new one right away, though, for newbies, I wouldn’t call that a fail. For folks like you though…

Pretty sure you can kill infinite time playing with random number generators. For my “weird” version ,I wound up with a 16-bit xorshift generator, with the shifts hand tuned to do the right thing for our 16.16 numbers. It’s fast, and definitely “random enough” for this purpose.

I did build the CA based generator, but it’s quite slow – may get back to it later and see if I can run it at twice the bit width and take the right hand half, which is rule 30’s more chaotic side, as the bits for my new random number. This would be bikeshedding! (But it’s fun to see what happens.)

OK, well, here goes. It’s not my most aesthetic, and I swear I have 10 different twinklers, but… This was kinda balancing minimal LLOC and minimal variable use. I’ll post the other ones after some beginners have posted theirs (since the others tend to be more readable :slight_smile: )

var rand
export function beforeRender(delta) {
  v = 1 - time(.01 + rand / 66)
  if (v < .05) rand = random(1) // Reliable down to 30 FPS
  v *= (1 / (1 - v + rand)) % 1 // Twinkler: https://www.desmos.com/calculator/ra90bl33p8
}

export function render(index) {
  hsv(rand << 4, 1, (floor((rand << 8) % pixelCount) == index) * v * v)
}

If I rearrange this for speed over LOC, I'm getting 183 FPS on v3 for 1000 pixels / "no LEDs". Also, comments added to this version as per @Scruffynerf's suggestion.
var rand, pixel, h

function next() {
  // A random number between 0 and 1 will have the 16 bits to the right of the 
  // binary point randomly set to 0 or 1. rand itself will be used directly for timing, 
  // but we can reuse it to get other random numbers from the lower bits.
  rand = random(1)

  // Left shift 4. 0b0.10110110 (0.7109375) becomes 0b1011.0110 (11.375).  
  // `hsv(h,` will drop the integer part of h before the point anyway. so this would 
  // be like calling `hsv(.375,`
  h = rand << 4 

  // We reuse this trick to left shift 8, giving a maximum rand value of 255.996
  // in this case, floor() strips the part to the right of the binary point instead, so we're left
  // with a random integer between 0 and pixelCount. Notice that this would need
  // to be modified if there were > 256 pixels, and it's not equidistributed unless 
  // pixelCount is a factor of 256. I'm on a 64-pixel matrix here, so the resulting 
  // probability mass function is equally distributed 
  pixel = floor((rand << 8) % pixelCount)
}

export function beforeRender(delta) {
  // Minimum time() period of .655 seconds, plus a random 0-100% of ~1 second
  // Normally time sawtooths increasing-to-the-right, so if I want to start with fade-outs,
  // I just invert the 0->1s to be 1->0s with the preceding `1 -`
  // It's worth noting here that we get a second source of randomness somewhat because when
  // the argument to time() changes, you don't start at a predictable point on the sawtooth
  v = 1 - time(.01 + rand / 66)

  // Reset the random stuff driving color, position, and timing when the sawtooth 
  // almost touches 0. This is one of those tricks I say not to use, but here I 
  // calculated and noted it's reliable (given the constants in this pattern) as long
  // as delta < 1/30s, and even then, it will degrade (by missing the timing reset)
  // proportionally to the slowness, and still catch it on some cycles.
  if (v < .05) next() // Reliable down to 30 FPS

  // Comment this out and you'll see the sawtooths directly.
  // Visit the link to see how this transforms 1..0 into twinkling 1..0
  // "+ rand" is the chill version. Try "- rand" for more flutter (but be sure to lose sign in render())
  v *= (1 / (1 - v + rand)) % 1 // Twinkler: https://www.desmos.com/calculator/ra90bl33p8

  // Uncomment this to put delays between blinks, but BE SURE to preserve sign in render (v * v _*v_)
  // v -= rand / 4
}

export function render(index) {
  // The simple trick here is that brightness is 0 unless `pixel == index` (multiply by false = 0)
  hsv(h, 1, (pixel == index) * v * v)
}

You know, I feel like I was observing aliasing artifacts with the xorshift Wizard made in “Static random colors” so I started implementing a 16.16 PCG-XSH-RR and I may reach out for some help. Cause inspecting and wrangling these bits is WOOOO HEEEE HAWWW.

Oh yeah… 'tis truly a joy! I’ve retired it for the evening, will build some primitive test tools tomorrow to see if I’m really even close to random.

If I cross my eyes and stare hard enough at the images on that page, I can see a sailboat. Bonus points for getting that reference.

2 Likes

There are some really good tricks in your code, @jeff

You might want to make a commented version explaining them in detail. Not just the twinkle but the bit shifts, the inverted timer, and the way you reuse V.

Update - excellent comments, lots of cool tricks and shortcuts explained! Here I was worried that only beginners would find these exercises useful, but if we golf these, or even just do fun stuff with it, more advanced users will find it all the more useful. This going to end up being a treasure trove.

2 Likes

Not so much golfing, as looking for wildlife out in the deep rough…

I can make randograms now! This one represents 65000 samples taken directly from a Pixelblaze via javascript (100 at a time – it took a while). It’s colored by repetition – more red == more frequent, so short cycles would show up brightly. (The maximum number of repeats for this run was 7.)

The generator is Wizard’s xorshift system for generating random numbers from 0 to 1, taken directly from the static colors pattern. It’s a 7,9,8 shift and he divides by 100 to move some of the high order bits downward before taking the fractional part. It looks nicely “random enough”, very comparable to the output of random().

(That was a fun paper! Got to say though – my wife is a scientist, and she’d be out to strangle somebody for sure if she had a paper out for peer review with no feedback for almost a year. Yikes!)

2 Likes

Ooh, a sailboat at the beach.

lol… instant headache! I’m kinda glad those things disappeared. Though we could always start a revival!

This is really awesome, Jon!

So perhaps with the divide-by-100 (somewhat right shift), it’s more akin to the xorshift with truncation that has good randograms, or maybe 7,9,8 is just very good parameters.

I looked through a directory of like 100 .epes and plugged in 5 boards and… just can’t find the code that I thought was producing patterned output with it. Perhaps my transforms were introducing the aliasing.

That’s what I was thinking too – the divide by 100 makes it roughly equivalent to xorshift with the multiply. And I also read somewhere else – I think on the retroprogramming site – that 7,9,8 is one of a small set of triples that are known to work well, plus that particular set let you wring better performance out of the Z80. That… was a long time ago.

If you like digging around in bit-magic random number generators, here’s a treasure trove for 8 bit PICs:

A lot is in PIC assembly, but many discuss theory too.

2 Likes

Cool! That site looks like an amazing resource for math methods. Coming from bigger CPUs, it’s just the kind of stuff that’s helpful to know.

On RNG: There’s tons and tons of lore everywhere, and it’s easy to get wrong. I’ve seen the weirdest bugs - long ago, I was PM on an MMO that used the player’s character name, which was globally unique, as part of the server-side RNG seed. There was one guy who complained for months that he never got any loot. Of course, nobody believed him. But he kept complaining, and finally, somebody checked the logs, and sure enough, he was right.

It turned out that the bit pattern in his particular name, and no other that we could find, caused the RNG (which was fairly complex) to generate a super short cycle with almost nothing in the high order bits. Of course, the server team fixed it posthaste, and we apologized profusely, but ever since I’ve been much more inclined to go ahead and do the test for myself, rather than believe the lore.

2 Likes

Wow, so potentially there was a magic name that would have loot boxes dropping from the sky constantly, eh? Good story.

Oh man, in 20 years, I’d never thought of it from that angle. Should’ve done an exhaustive search for the “good” name and decked myself out in l33t finery!

I was very junior, and was mostly just worried. This was the very early 2000s, and the problem of distributing the load for a big multiplayer game over multiple servers was still pretty new. MMOs use tons upon tons of random numbers – the total overall rate was just huge, and I think somebody just thought up a clever shortcut to improve performance and didn’t catch the one tiny little problem…

Now it’s even more like a random dot stereogram!

Here’s the output from the Rule 30 PRNG, 32 cells, with wrap, generating 15-bit fractions (to dodge messing with the sign – because of sign extension when shifting right, 16 bit fractions generated with this method have the range -0.999 to 0.9999. )

My basic stats say, “Max is: 0.999817, Min is: 0.0, Max repeat count is: 10”. Black areas are unhit coords, otherwise the darker the color, from light yellow to red, the higher the repeat count at that point. Distribution looks good, although the pixels are so small and numerous that repeats don’t really stick out.

It’s interesting that wrapping around the ends of the array doesn’t kill it. I had the idea that it would.

1 Like