Inspired by this Game of Life question.

Wireworld simulates "electrons" flowing through "wires", simple arrangements of which produce typical logic gate behavior.

I challenge you to build a digital clock in the Wireworld cellular automaton. Your clock must count upwards from 00:00 to 23:59 in the usual fashion, or to 11:59 with an AM/PM indicator, then reset.

Your entry should be visibly divided into two parts. Part A should contain all of the non-display logic, all of the parts involved in incrementing and looping the digits. Part B will be the display and the logic that drives it. The only connection between these two parts should be 16 wires representing the four digits of the time in BCD (with one optional wire for the AM/PM indicator, and one optional wire for a signal clock line if your signals aren't continuous). (EDIT: always-zero wires can be omitted)

The timing of the clock behavior should be consistent. The simulation should take the same number of ticks for each of the 1440 transitions between states. Any electrons on the 16 wires should emitted from part A at the same time and start their trip in parallel.

This is a code-golf competition. Your score is the area of the axis aligned bounding box surrounding part A.

By analogy, if this were a textual language, your score would be the size of the clock-management function producing four 4-bit outputs, which contains a loop and the logic for 4 counters, not the function that decodes and prints that output.

Your part B can be as large or small as you'd like. It is only required so that the output of your submission can be seen by someone running it, since there is no easy way to simply "debug" outputs from a wireworld circuit. There are multiple BCD->7segment circuits available online. Feel free to use whichever one you'd like, or make your own if you need a clocked signal line, and display your AM/PM indicator at some scale similar to the digits.

EDIT: Part B is now optional. If you just have the BCD outputs from your part A, feel free to submit that. It will be more tedious to confirm the clock works, but I can read a row of bits just fine in a paused simulation.

  • Here is a small online simulator. – NonlinearFruit Dec 11 '16 at 3:02
  • I've been working on this but only saw it last week so I'll probably miss the bounty. I can't find a 4-wire version of a wireworld bcd->7-segment; building a 4-to-2 converter in front of the popular 2-wire 7-segment device (like the one that comes with golly) may be the way to go. One problem with that device is that, while it's nice-looking, it's slow to update, which will bloat Part A's size because it can pump numbers out faster than they can be displayed and must be artificially slowed down. – wyldstallyns Dec 11 '16 at 16:35
  • I have a 150,000 cell working Part A that I can prove works but currently lacks a rule-compliant Part B. – wyldstallyns Dec 11 '16 at 21:37
  • I didn't expect part B to be difficult. How far apart are your electrons in part A? – Sparr Dec 11 '16 at 21:56
  • 1
    @wyldstallyns It closes at 16/12/2016 03:30:35Z (you can hover over the 'tomorrow' to get the precise times). The very best of luck to you. I genuinely like your clock. It's an elegantly simple idea and an excellent execution. I must admit I was also surprised with how much space mine ended up taking in the end. And I'd be interested to see any improvements you can come up with in yours. So, best of luck :) – niemiro Dec 14 '16 at 21:50
up vote 36 down vote accepted
+550

Latching Clock

Score - 53,508 (of which only 36,828 is actively used due to the L-shaped design)

Clock Running

High Quality recording - https://1drv.ms/u/s!ArQEzxH5nQLKhvt_HHfcqQKo2FODLQ
Golly pattern - https://1drv.ms/u/s!ArQEzxH5nQLKhvwAmwCY-IPiBuBmBw

Guiding Principles -

  • Since this was my first time using a cellular automaton I avoided stringing together large premade components. One valid approach I did not take would have been a binary adder starting at zero and continuously adding one to the last output, followed by a binary to BCD converter, display demultiplexer, 7-segment decoder and 7-segment display.
  • It should be possible to cold start the clock. I imposed on myself the additional restriction that a single electron head placed at a specific conductor cell should correctly start the clock. I did not want to require careful manual synchronisation of many disparate flip-flops and individual timing elements before beginning the simulation.

Part I: The Minute Counter

Mathematics

Counting from 0 to 9 in binary (for the least significant minutes digit) goes as follows -

0 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 1001

Reading that as columns, the least significant (2^0 units bit stream) goes 01010101, the 2^1 units stream goes 0011001100, the 2^2 units stream goes 0000111100 and the 2^3 units stream goes 0000000011.

The first one's easy - just flip-flip 01 forever. The third is a stream of four 1s, six 0s, phase shifted by six zeros. The fourth is a stream of eight 0s and two 1s.

The second is a bit harder as it's got a nasty asymmetry. However, I notice that (where . is concat operator):

0011001100 . 0011001100 = 0011001100 . NOT(1100110011) = 00110011001100110011 XOR 00000000001111111111 = 5(0011) XOR 00000000001111111111

(Incidentally, as alluded to later, the majority of my clock runs on a 60-beat ticker. The 00000000001111111111 double length wave is where the need for the 120-beat ticker comes in).

Design

The output streams from top to bottom go Units of Minutes (2^0, 2^1, 2^2, 2^3) then Tens of Minutes (2^0, 2^2, 2^1). Note that the bottom two wires are crossed.

Minute Counter Annotated

  1. 120-beat main clock.
  2. Where to place an electron for a cold start. Without any electron tail it splits in two directions but the diode immediately above catches one of these giving a nice cycling electron going around and round the 120-beat loop.
  3. 12-beat secondary clock.
  4. Coil of conductor + diode starts the secondary 12-beat clock. Words cannot describe how fiddly this little piece was to sync. You have to sync the 120 and 60 beat clocks, then sync in the 12-beat and frequency halver 24-beat pseudo clocks, followed by tying back the 24-beat clock to the 120-beat clock otherwise the XOR gate doesn't work.
  5. Phase shift.
  6. Flip-flop. A single electron on the input hits the set line first then after a very specific amount of time, hits the reset line giving precisely one pulse in, one pulse out.
  7. Adding humps here - on the reset line, increases the delay between set and reset on the flip-flop. Each extra hump gives an extra pulse. The flip-flop below has nine extra humps, so ten pulses between set and reset.
  8. XOR gate for my tricky 2^1 units of minutes line.
  9. AND-NOT gate and very specific part lengths means each electron pulse which comes past doubles back on itself and annihilates the electron behind. Frequency halver. Creates a 24-beat clock from the 12-beat secondary source.
  10. 60-beat secondary clock, which actually does most of the work. It's just easier to start a fast clock from a slower one, so the slowest clock (120-beats) is the master, even though it's barely used. The 60-beat clock is the heart of this thing.
  11. Feedback wire which carries electrons only when the 60-beat clock is ticking. It's used in conjunction with an AND-NOT gate to stop the clock being restarted repeatedly from the 120-beat master. Otherwise many horrible things happen & Ctrl-Z is saviour.
  12. The diode where the 60-beat clock is started from.
  13. This whole device is a flip flop, AND gate, and AND-NOT gate combined. It gives a latch. One pulse in starts it, one pulse in stops it.
  14. Loop of wire to calibrate the latch to 10 pulses on, 10 pulses off for a one in ten pulse input. Without it we get 12 pulses on, 8 pulses off. These ten on ten off latches form the basic components of the ten minute blocks in the same way the 6-micron (1 pulse) flip-flops formed the basic components of the minute units.
  15. The cold start initial pulse caused all sorts of problems including being two beats out of phase with the clocks it starts. This messes up the latches. This AND gate catches and disposes of out of sync pulses - in particular the starting pulse.
  16. This is a part of the design I somewhat regret in retrospect. It takes an electron, splits it into five and annihilates the five electrons behind, taking 111111 to 100000.
  17. This takes an electron and stitches it on the front. Two phases ahead to be precise. It takes 100000 and makes 101000. Combined with part 16 we get 111111 -> 100000 -> 101000. In retrospect I wish I'd done 111111 -> 101010 -> 101000; it would have achieved the same effect in less space.
  18. The above patterns are then pushed into the bottom latch to achieve 20 on, 40 off. This is split, half is phase shifted by 20 units, and then these form the two high order bit streams of the tens of minutes.

Part II: The Hour Counter

Explanation

The input to the hour counter is a single electron pulse, once an hour. The first step is to reduce this to a single electron pulse, once every twelve hours. This is achieved using several "latch & catch" primitives.

A "latch" is a 6-micron flip-flop connected to an AND-NOT and an AND gate to give a 6-micron on/off latch. A "catch" takes a continuous stream of electrons as input, allows the first through, then annihilates every other electron behind, until the stream ends at which point the catch resets.

Placing a latch, followed by a catch, in series, results in one electron in -> turns on the latch, one electron out the other end (rest caught by catch). Then second electron in -> turns off latch, catch silently resets. Net effect: first electron passes through, second electron is annihilated, and so on and so forth, irrespective of how long the delay is between those electrons.

Now chain two "latch & catch" in series, and you have only one in four electrons passing through.

Next, take a third "latch and catch", but this time embed an entire fourth latch and catch on the flip-flop SET line, between the AND-NOT gate and the flip-flop SET. I'll leave you to think about how this works, but this time only one in three electrons passes through, irrespective of how long the delay is between those electrons.

Finally, take the one in four electrons, and the one in three, combine them with an AND gate, and only one in twelve electrons pass through. This whole section is the messy squiggle of paths to the top left of the hour counter below.

Next, take the electron every twelve hours and split back into one every hour, but output each onto a different conductor wire. This is achieved using the long coiled conductor with thirteen exit points.

Take these electrons - one an hour down different conductors, and hit a flip-flop SET line. The RESET line on that same flip flop is then hit by the next hour's conductor, giving sixty pulses down each wire per hour.

Finally - take these pulses and pass them into seven and a half bytes of ROM (Read-Only Memory) to output the correct BCD bitstreams. See here for a more detailed explanation of WireWorld ROM: http://www.quinapalus.com/wires6.html

Design

Hour Counter Annotated

  1. One electron per hour input.
  2. First latch.
  3. First catch.
  4. "Latch & catch" embedded on an outer "latch & catch" SET line.
  5. AND gate.
  6. AM/PM latch (turned on/off once every twelve hours).
  7. Each loop of wire is 6x60=360 units long.
  8. Flip/Flop turned on its side to create a smaller profile.
  9. Seven and a half bytes of ROM.

Notes

  1. Due to its one electron per minute, 6-micron design, run the simulation at six generations per minute (one generation every 10 seconds) for a real-time clock.
  2. The AM/PM line is high (1) for AM, low (0) for PM. This might seem a slightly unusual way round to choose, but there is justification. During a cold start of the clock, the AM/PM line is naturally low (0) initially. As soon as the AM/PM line is pulled high (1), this indicates that the count has begun at 12:00AM. All output before this point should be disregarded, all output after this point is considered meaningful.

Useful Links

  • changed requirements so that always-zero outputs can be omitted. the 4s and 8s bits for the tens of hours are never used, nor the 8s bit for tens of minutes. – Sparr Dec 13 '16 at 1:34
  • Solid! True engineering. Would any of the other logic gates have been useful? I'm about to brute force some. – wyldstallyns Dec 13 '16 at 1:45
  • 1
    This is beautiful – Sparr Dec 14 '16 at 20:20
  • 1
    Oh good grief that's just close enough now I'm compelled to try and optimize mine. I have repeating patterns I could shorten to make room to fold others in. – wyldstallyns Dec 14 '16 at 21:34
  • 3
    I don't know how active you are on meta, so this is to let you know that I've nominated this answer for the Best of PPCG 2016. – Peter Taylor Jan 10 '17 at 21:37

Delay line memory - 51 x 2880 = 146880

Image

Zoomed out:

Image

Output comes out the top of each loop.

I put all the states directly on the wire with this lua, letting golly step the electrons forward between bits so we don't have to follow the wire with a cursor.

I used this naive method to set a bar and crash course wireworld, golly and lua.

local g = golly()

local minutes_in_day = 1440 -- 60x24
local interval = 4 -- how often to send electrons

local function bcd4(num)
    num=math.floor(num)
    local t={}
    for b=4,1,-1 do
        t[b]=math.floor(math.fmod(num,2))
        num=(num-t[b])/2
    end
    return table.concat(t)
end

local function makewire(x,y1,y2)
    for y1=1,y2 do g.setcell(x,y1,3) end
end

local function makeloop(x,y,size)
    local len = size/2 - 1
    makewire(x,y+1,len); makewire(x+2,y+1,len) -- main wires
    g.setcell(x+1,y,3); g.setcell(x+1,y+len,3) -- endcape
end

local function paint(x,y,pattern)
    for v in string.gmatch(pattern,".") do
        if v=="1" then g.setcell(x, y, 1); g.setcell(x, y-1, 2) end
        x = x + 4
    end
    g.show(pattern);g.update() -- slows things down but more interesting to watch
    for i=1,interval do g.step() end
end

for x=0,63,4 do makeloop(x,0,minutes_in_day * interval) end

for hour = 0,23 do
      for minute = 0,59 do
         paint( 0, 2, bcd4(hour/10) .. bcd4(hour%10) .. bcd4(minute/10) .. bcd4(minute%10) )
      end
end

For testing I added these top wires and watched their tips.

Imgur

Here's the script to collect the 4 sets of 4 wire BCD to eyeball.

-- watches 16 wires spaced 4 apart starting at (0,-4)
local ticks = 1440 -- set to match the length of your 24 hour loop
local g = golly()
local output = ""
local nums = {  ["0000"] = "0", ["0001"] = "1", ["0010"] = "2", ["0011"] = "3", ["0100"] = "4",
                ["0101"] = "5", ["0110"] = "6", ["0111"] = "7", ["1000"] = "8", ["1001"] = "9",
                ["1010"] = "A", ["1011"] = "B", ["1100"] = "C", ["1101"] = "D", ["1110"] = "E",
                ["1111"] = "F" } -- full set in case we have errors (i did)

for i=0,ticks,1 do
   local text = ""
   for i=0,48,16 do -- set your X here, change the 0 and 48
       local word = ""
       for j=0,15,4 do
            local bit = g.getcell(i+j,-4) -- set your Y here, change -4
            if bit == 0 or bit == 3 then word = word .. "0" else word = word .. "1" end
       end
       text = text .. nums[word]
   end
   g.show(text); output = output..' '..text
   g.update(); g.step();g.step();g.step();g.step()
end
g.note(output)

Final answer requires pruning the always-zero lines and routing the rest to their correct BCD inputs.

  • changed requirements so that always-zero outputs can be omitted. the 4s and 8s bits for the tens of hours are never used, nor the 8s bits for tens of minutes. – Sparr Dec 13 '16 at 1:34
  • 2
    This is a hilarious and awesome implementation! – Sparr Dec 13 '16 at 1:35
  • 1
    Ok I've been beat with another functional clock at the 11th hour. I'm going to attack the longest and shortest loops with different tricks. – wyldstallyns Dec 14 '16 at 21:38
  • I'm not going to pull it off. I can save 1/4th of the size by switching to 3 micron pulses, but it still won't coil tight enough to beat niemiro. – wyldstallyns Dec 15 '16 at 22:24

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.