Build a digital clock in Conway's Game of Life

  • Your task is to build a Game of Life simulation representing a digital clock, which satisfies the following properties:

    1. The clock displays the hours and minutes in decimal (e.g. 12:00, 3:59, 7:24) with a different state for each of the 1,440 minutes of the day — either the hours will go from 0 to 23 or from 1 to 12 with a PM indicator.

    2. The pattern is periodic, and the state loops around without any outside interaction.

    3. The minutes update at regular intervals — from one change of minute to the next takes the same number of generations.

    4. An anonymous bystander is able to tell at a glance that the display is supposed to be a digital clock. In particular, this entails:

      • The digits are visible and clearly distinguishable. You must be able to tell with certainty at a glance what time is being displayed.

      • The digits update in place. Each new number appears in the same place as the previous number, and there is little to no movement of the bounding boxes of the digits. (In particular, a digit does not contain 10 different digits in different places that get uncovered every time the digits change.)

      • The digits appear next to each other, without an excessive amount of space between them.

    Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

    • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

    • Fastest execution — the fewest generations to advance one minute wins.

    • Initial live cell count — smaller count wins.

    • First to post — earlier post wins.

    Does the clock have a fixed starting time?

    Can The display be in binary?

    @FryAmTheEggman No, but the starting time shouldn't matter if the display state is cyclic.

    @tuskiomi No, the display must be decimal.

    I'm pretty sure this is B3/S23, but could you confirm or deny?

    Yes, B3/S23 is correct.

    "from one change of minute to the next must take the same number of generations" assuming our digits change in a cascade-of-pixels fashion, can we simply ensure that the cascade starts and/or ends at the same time each minute? that is, 1 is narrower than 0, so 1 probably won't take as long to change. it can start, or middle, or end at the same time as 0, but not all 3 without a lot more work.

    "They must also update in place — each new number must appear in the same place as the previous number." How do you define "in the same place", since the digits won't necessarily be rectangular.

    how discernable must our decimal digits be? is "if you know what it is and you squint then you can tell the difference between 0 and 8" enough, or does it need to pass the "an anonymous bystander can tell what it is with no prompting" test?

    @Sparr You can ensure that a cascade starts or ends, and an anonymous bystander should be able to tell without prompting.

    @MartinEnder There should be little to no movement of the bounding boxes of the digits. (You can make "1" right-aligned like a seven-segment display if you're implementing that, but otherwise the digits should all have roughly the same bounding box.)

    @MartinEnder I think he means it can't be a glider.

    @PyRulez I built that rule to exclude the kinds of digits that appear in different positions and just get uncovered when the clock is on that digit. The digital clock display should look roughly like an actual digital clock display.

    @Mego B3/S23, rectangular grid.

    This is even harder than tetris as it seems.

    How about this analogue clock⸮ (not made by me)

    So, its now answered, now you make a challenge harder than a clock but easier than tetris. what about... Pong?

    @SIGSEGV A pong challenge already exists, so they could answer there.

    The tetris challenge has been solved, you can update the top.

  • dim

    dim Correct answer

    4 years ago

    11,520 generations per clock count / 10,016 x 6,796 box / 244,596 pop count

    There you go... Was fun.

    Well, the design is certainly not optimal. Neither from the bounding box standpoint (those 7-segment digits are huge), nor from the initial population count (there are some useless stuff, and some stuff that could certainly be made simpler), and the execution speed - well... I'm not sure.

    But, hey, it's beautiful. Look:

    enter image description here

    Run it!

    Get the design from this gist. Copy the whole file text to the clipboard.

    New: here is a version with both AM and PM indicators for the demanding.

    Go to the online JavaScript Conway life simulator. Click import, paste the design text. You should see the design. Then, go to settings and set the generation step to 512, or something around those lines, or you'll have to wait forever to see the clock display updating.

    Click run, wait a bit and be amazed!

    Direct link to in-browser version.

    Note that the only algorithm that makes this huge design useable is hashlife. But with this, you can achieve the whole clock wraparound in seconds. With other algorithms, it is impractical to even see the hour changing.

    How it works

    It uses p30 technology. Just basic things, gliders and lightweight spaceships. Basically, the design goes top-down:

    • At the very top, there's the clock. It is a 11520 period clock. Note that you need about 10.000 generations to ensure the display is updated appropriately, but the design should still be stable with a clock of smaller period (about 5.000 or so - the clock needs to be multiple of 60).

    • Then, there is the clock distribution stage. The clock glider is copied in a balanced tree, so at the end, there are 32 gliders arriving at the exact same moment to the counters stage.

    • The counter stage is made using a RS latch for each state, and for each digit (we're counting in decimal). So there is 10 states for the right digit of the minutes, 6 states for the left digit of the minuts, and 12 states for the hours (both digits of the hours are merged here). For each of these groups, the counter behaves like a shift register.

    • After the counting stage, there are the lookup tables. They convert the state pulses to display segments ON/OFF actions.

    • Then, the display itself. The segments are simply made with multiple strings of LWSS. Each segment has it own latch to maintain its state. I could have made a simple logical-OR of the digit states to know wether a segment must be ON or OFF, and get rid of these latches, but there would be glitches for non-changing segments, when the digits are changing (because of signal delays). And there would be long streams of gliders coming from the lookup table to the digit segments. So it wouldn't be as nice-looking. And it needed to be. Yes.

    Anyway, there is actually nothing extraordinary in this design. There are no amazing reactions that have been discovered in this process, and no really clever combinations that nobody thought of before. Just bits taken here and there and put together (and I'm not even sure I did it the "right" way - I was actually completely new to this). It required a lot of patience, however. Making all those gliders coming up at the right time in the right position was head-scratching.

    Possible optimizations:

    • Instead of copying and distributing the same root clock to the n counter cells, I could have just put the same clock block n times (once for each counter cell). This would actually be much simpler. But then I wouldn't be able to adjust it as easily by changing the clock at a single point... And I have an electronics background, and in a real circuit, that would be horribly wrong.

    • Each segment has it own RS latch. This requires the lookup tables to output both R and S pulses. If we had a latch that would just toggle its state from a common input pulse, we could make the lookup tables half as big. There is such a latch for the PM dot, but it is huge, and I'm unable to come up with something more practical.

    • Make the display smaller. But that wouldn't be as nice-looking. And it needed to be. Yes.

    Beautiful. Nice answer.

    I'm only a little disappointed that the PM indicator is just on/off. It would be dope to have it swap between AM and PM. Nice job with this

    It's too big. I'm not able to copy that large of a file to my clipboard. I, too, would recommend using something other than Pastebin.

    @mbomb007 Copying works fine for me on windows, tho

    I click the "copy" button, and I get an error. Maybe it's Chrome, but idk.

    @mbomb007 Oh, for that I had to go to raw mode. The copy button seems to do nothing

    Give this a try next!

    @riker I know. I'll have a look, but it is more complicated, despite what some said. There is more information to share between blocks, there is the problem of making a convenient input mean, and generating the next blocks as randomly as possible, etc...

    @Poke come on, you could have tried to add this yourself... Anyway, I have edited the post with a version with both AM+PM, for your pleasure.

    @mınxomaτ Thanks. I moved the code to an anonymous gist, and linked to the raw file directly. It seems anonymous gists never expire.

    @dim well played, sir

    Well played sir. Inspirational.

    what would code golfing suggestions on this post look like?

    Just so you know, this answer has been featured in Microsiervos, one of the most important blogs about technology in Spanish, with over 800K followers on Twitter

    @Luis wow. Thanks for the info. I'll have a look.

    @Luis oh, I forgot one detail: I can't read spanish. Nevermind. But I'm both a bit proud and a bit ashamed because I'm sure the real GoL researchers would laugh at the way I did things. I, myself, see many thing that aren't right in this solution.

    It killed my browser. :) Too much RAM allocated.

    This is incredible. Is it possible to determine a step rate which would guarantee a minute between digit changes?

    @polynomial. No, not with the existing game of life programs: it depends on the computer speed and the step rate must be a power of two, which disallows accurate tuning. But you could make a specific game of life simulation program that guarantees it, however, since the number of generation steps between minute increment is constant.

    @copy Cool! Thanks, it makes it a lot easier. May I ask you to put a link to this question from the pattern info dialog? Just for the credit, and in case the design evolves. Also, so that people can have the explanation on how it works, eventually. Thanks a lot, anyway.

    How would you even start designing something like this?

    @Rory You take your head, smash it on the wall a dozen times as hard as you can. You are then ready to start.

    It seems this stuff has gone viral...

    @dim I'd suggest you add it to the pattern file: `#O Your comment here`

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM