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:
The clock displays the hours and minutes in decimal (e.g.
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.
The pattern is periodic, and the state loops around without any outside interaction.
The minutes update at regular intervals — from one change of minute to the next takes the same number of generations.
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.
Can The display be in binary?
@FryAmTheEggman No, but the starting time shouldn't matter if the display state is cyclic.
"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.)
@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.
By Game of Life, do you mean the B3/S23 ruleset originally defined by Conway, or any Life-like cellular automata? Does it need to use a rectangular grid, or is a hexagonal grid acceptable?
this got posted on the Hackaday blog too : http://hackaday.com/2017/03/11/a-clock-created-with-conways-life/
How about this analogue clock⸮ https://copy.sh/life/?pattern=clock2&;fps=1 (not made by me)
So, its now answered, now you make a challenge harder than a clock but easier than tetris. what about... Pong?
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:
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.
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.
- 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.
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 Oh, for that I had to go to raw mode. The copy button seems to do nothing
@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.
@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.
This is incredible. Is it possible to determine a step rate which would guarantee a minute between digit changes?
Direct link: https://copy.sh/life/?gist=f3413564b1fa9c69f2bad4b0400b8090&;step=512 (sorry about undocumented parameters!)
@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.
@Rory You take your head, smash it on the wall a dozen times as hard as you can. You are then ready to start.
I can't even.... so besides being an alien in a human planet, what else do you do in the afternoons? In all seriousness... wow....it would be great if you could do a write up on the design process for this.
@GurupadMamadapur you can set a bounty, but you need to wait for the current one to end. I don't think you should be so generous, though. I wouldn't know what to do with all that rep. Thanks anyway.
@jl6 it is the period at which the oscillators in these design run at. Basically, the number of generation steps between gliders in a stream. So, here it is 30. P30 is used in many designs, because people have found a lot of elementary building blocks for this. But there are other options, the other most frequently used being p46 (used by the OTCA metapixel design) and Herschel (stable - actually no oscillators at all).
Amazing! I managed to fumble-right-click to draw in some extra cells, and the pattern quickly disintegrated like it had cancer; the corrupt parts sending out gliders to corrupt others. So I was thinking: Are there resilient life machines that can clean this up, and have an “immune system”? I imagine it is required to be scaled up by 100 or 1000x from the clock for the complexity of it.
@bluss I'd be tempted to think (but I am far from being an expert on this - what I say here may be complete bullshit) that the stability would be more tied to the ruleset of the game (there are other kinds of cellular automata beyond the B3/S23 "standard life" rules originally defined by Conway) rather than the complexity of the design. There are certainly talented mathematicians working on these questions.
Is it for real or am I daydreaming? `a lot of patience` + `right time in the right position was head-scratching` = how exactly, what was the process?
@Michal you'll understand if you try to design something with that. Basically, the glider moves forward, but to advance one single cell, it needs four generations steps. It therefore has four possible "positions" (some call them "colors"). Now, if you want your glider to make something useful, it has to collide something. Almost everything is constantly moving on the design, because everything is made of oscillators. If your glider comes to collide that thing at the wrong time, or in the wrong position, it will most certainly just create a mess.
So the design process is: "Ok, I need to collide that, and my glider comes from there in this position at this time. Let's see bring it there using two reflectors. Crap, the thing it needs to collide is just two generation steps too soon, there. If I move the reflectors a bit, let's see... Crap, too late. Ok, let's collide them some place else. Crap, I don't have the room to make my glider go there. Ok, let's add two other useless reflectors just to make it arrive there instead. Crap, the reflectors collide this other stream of glider... Crap, let's go to bed."
@mohitmun about two/three weeks, part time. Hard to say exactly how many hours, but quite some. I had to learn a lot of things in the process, too. I had no idea that could be done, actually. I first saw the tetris question and just though "What the hell? Forget that.". Then I saw this question and thought "What the hell again? What's up with this game of life thing, anyway?" So I made a bit of research, and saw many people had made funny things with it, so I thought "Ok, let's try".
@dim You don't need to be able to read Spanish. If you're using Google Chrome, there should be a "Translate this page" button in the address bar if you have the Chrome setting "Offer to translate pages..." enabled. Welcome to the 21st century. :)
@Polynomial 24 FPS with a Generation Step of 8 will be change the display once per minute (24 x 8 x 60 = 11520). If you computer is a bit sluggish, you could also try 12 FPS with Generation Step 16.
@dim, one question i couldnt find a meaningful answer from my basic google searches.. what tools you use to work on this kind of project ?. In addition to your comment on the thought process behind this (which includes a lot of craps :) ), where do you try out, play out and learn the new patterns created by others ?
@funtime. The only tool really required is "golly". Now, the knowledge can be found with extensive google searching. But most of the things I used come from the conwaylife site, both the wiki and the forums. Also the golly samples. The turing machine design also contains interesting patterns (see http://rendell-attic.org/gol/tmdetails.htm). There are other pages (from last century's www) containing various interesting info: http://www.radicaleye.com/lifepage, http://radicaleye.com/DRH/, ...
If there was no rep cap, this single answer would make almost the entirety of his rep... Good job, needless to say +1
@DownChristopher Indeed. And I want to take this opportunity to really thank everybody. I didn't expect that many rewards.
@dim yeah this answer alone has more bounties then rep I have in the entire SE
@DownChristopher If I had more rep I'd put another +500 myself. It's kind of an honour to be one of the people supplying the bounties for such a ground-breaking answer.
How does one even learn something like this just off the internet? I tried googling around for a while, there's just a plethora of random patterns and no instructions on how to combine them into something useful. And then I tried really zooming in in your clock to figure out what's going on (and failed obviously). You've earned another +500 :P But seriously, where did you even learn all this?
@ghosts_in_the_code Thank you. Well, to answer your question, since I have some electronics background, I started to think that way. I thought if I could find some way of producing gliders regularily (clock), some way of sending the same information to multiple places (duplicator), some basic logic operators (and/or gates, ...), and some way of displaying the info (display), I could manage to do it. Googling helped to find these basic patterns (and the display was inspired from the metapixel design). Then, after playing with this a bit, you start to find more efficient ways to combine things.
But, before searching for patterns, you need to know what kind of patterns you're looking for... Maybe that was the step you were missing in your research.
Ok great. I think I'm starting to get it now. Not sure about those lines of gliders at the top of the clock... Why are they running criss cross, and how is all the information encoded in them? Anyways, I'll check it out again. Is there like a list of GoL patterns that are most useful in this kind of programming? Or do all the patterns come handy?
Not sure which line of gliders you're talking about. If you're talking about the zone from cursor Y=-3300 to Y=-2700, these are just duplicators. They copy the original clock pulse (single glider coming from the top of the tree) so there are 29 gliders arriving exactly at the same time to the counter stage, which is made out of some kind of flip-flops. By the way, this part has actually been difficult to design, although it is functionally very simple, because the two gliders the duplicators outputs don't have the same timings, so you have to compensate (with reflectors and stuff).
@ghosts_in_the_code Otherwise, the kind of patterns you need really depend on what you plan to design. But for something like this, duplicators, reflectors, and gates are always useful. See some other comment I made above for reference.
@ghosts_in_the_code I realize you were likely talking about the lookup tables: the squares with several lines/colums of lightweight spaceships (these are not gliders, gliders go diagonally, and LWSS go horizontally/vertically). These tables are translating the digit pulses (0 to 9) to display segment on/off actions. basically, the digit pulse input comes from the top, in the column corresponding to the digit, in the form of a missing LWSS in the stream. When this missing LWSS goes through the pattern you see at some crossings, it is replicated as a new missing LWSS on the horz stream...
each horizontal stream correspond to either a "on" or a "off" action on a specific segment. This information is then conveyed to the flip-flop (a one-bit memory) of the corresponding segment (each segment has one), which will enable or disable the LWSS within the segment (that you see as a digit when zoomed out). Basically, the information contained here is the shape of the digits, and it is encoded by the presence/absence of the little patterns at the line/column crossings.
@dim Ok thanks. Im not sure I can do any of it, but I'll try. Seems interesting. And your clock is inspiring, I must say
What software did you use to do this? I've tried to build some Life machines but I've found the primary pattern programs like Golly very awkward and awfully NOT user-friendly for building patterns -- namely they are sorely missing the ability to copy and paste from a "palette" of components and also "evolve on the spot" (that is, select a set of tiles and evolve it in isolation to get it "into the right phase".). I couldn't imagine building something like this with that. What program did you use?
@mike3 I actually used golly. Yes, it was a pain, and the features you're describing would have made things easier, indeed. Golly has its "layers" concept that somewhat allows that, but I agree it is, at best, not very flexible. Maybe someone should start developing a better tool...
A million congratulations, wonderful work! Very clever use of glider/LWSS interaction in the LUT phase. Now if only I could get off my lazy rear end and actually make good on my two-year-old promise to fulfill the tetris game request, lol ( biggest roadblock being that it requires a ton of new reactions that I'm not sure how to go about finding :[ ).
@dim Apologies for a new addition to an old thread, but I'm looking for official permission to add your digital clock pattern to the Online Archives for Golly 3.2. May I? If you have any attribution or other additional information about the pattern that I should add to the pattern comments, you could send it to [email protected]com (if you'd prefer not to post it here).
@DaveGreene Sure. I grant you all permission to distribute this, modified or unmodified, under the terms you want. I'd appreciate an attribution notice: just put a link to this answer, as I wish to remain anonymous. And thank you very much for the notification. Also, thanks for your work on Golly, without which I certainly wouldn't have been able to do this (although - if I may - this tool could highly benefit from a kind of "reusable components palette" feature: see the comment from The_Sympathizer above).
Yes, the "palette" idea is an old one -- Life32 had a feature like that. On the other hand, you can do what The_Sympathizer mentions in the current Golly, in a way that's only a *little* rough around the edges: open a labeled "stamp collection" of common components in one layer (or even a second copy of Golly), and do your editing in another layer. Tile the layers if you don't want to switch back and forth between tabs. Select and Ctrl+Space in Golly does the evolve-on-the-spot trick; Shift+Space is "freeze selection and evolve everything else". -- And thanks for the official permission!