Challenge: Minimal Toffoli gate

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Challenge: Minimal Toffoli gate

Post by dvgrn » February 18th, 2018, 3:15 pm

A random "Mediocre Challenge" showed up on Stack Exchange via the Quest for Tetris discussion board a while back:
Mego wrote:CMC (Chat Mediocre Challenge): implement a Toffoli gate in Game of Life (B2/S23). Smallest bounding box wins.
I took that to mean B3/S23, since B2/S23 is kind of hard to build anything in -- except maybe if we start with a non-empty universe? The zebra stripes agar is stable, for example, so maybe there are signal wires of various kinds out there somewhere.

But I digress.

After I did my usual thinking-by-building-things, resulting in a few rather silly circuit mechanisms that couldn't possibly work, it eventually became clear that an exact-timing XOR gate was going to be needed. Luckily simeks pointed out a workable piece of an XOR mechanism recently (December). A small initial circuit just needed to be added to suppress the first natural glider.

Code: Select all

x = 312, y = 79, rule = LifeHistory
71.D79.D79.C79.C$69.2D78.2D78.2C78.2C$70.2D78.2D78.2C78.2C27$29.2A78.
2A78.2A78.2A$30.A79.A79.A79.A$30.A.A77.A.A77.A.A77.A.A$31.2A78.2A78.
2A78.2A4$25.A.2A76.A.2A76.A.2A76.A.2A$25.2A.A76.2A.A76.2A.A76.2A.A$
20.2A78.2A78.2A78.2A$21.A79.A79.A79.A$21.A.A17.2A.A56.A.A17.2A.A56.A.
A17.2A.A56.A.A17.2A.A$22.2A17.A.2A57.2A17.A.2A57.2A17.A.2A57.2A17.A.
2A3$8.A79.A79.A79.A$8.3A77.3A77.3A77.3A$11.A10.7B62.A10.7B62.A10.7B
62.A10.7B$10.2A3.2B2.10B61.2A3.2B2.10B61.2A3.2B2.10B61.2A3.2B2.10B$
10.12B.6B61.12B.6B61.12B.6B61.12B.6B$4.2A6.10B.B.4B55.2A6.10B.B.4B55.
2A6.10B.B.4B55.2A6.10B.B.4B$4.A5.12B3.4B12.2A41.A5.12B3.4B12.2A41.A5.
12B3.4B12.2A41.A5.12B3.4B12.2A$5.3A2.14B.4B12.A43.3A2.14B.4B12.A43.3A
2.14B.4B12.A43.3A2.14B.4B12.A$7.A20B11.A.A45.A20B11.A.A45.A20B11.A.A
45.A20B11.A.A$9.12B9.A8.2A48.12B9.A8.2A48.12B9.A8.2A48.12B9.A8.2A$10.
11B8.A.A2.A55.11B8.A.A2.A55.11B8.A.A2.A55.11B8.A.A2.A$11.10B9.A3.3A
54.10B9.A3.3A54.10B9.A3.3A54.10B9.A3.3A$.2A3.2A.B.11B15.A43.2A3.2A.B.
11B15.A43.2A3.2A.B.11B15.A43.2A3.2A.B.11B15.A$.A.A.A.A14B10.4A.3A41.A
.A.A.A14B10.4A.3A41.A.A.A.A14B10.4A.3A41.A.A.A.A14B10.4A.3A$3.A.A.B.
13B10.A2.A4.A42.A.A.B.13B10.A2.A4.A42.A.A.B.13B10.A2.A4.A42.A.A.B.13B
10.A2.A4.A$2.2A.2A13B.B2A13.3A42.2A.2A13B.B2A13.3A42.2A.2A13B.B2A13.
3A42.2A.2A13B.B2A13.3A$6.B.9B4.BA.A11.2A48.B.9B4.BA.A11.2A48.B.9B4.BA
.A11.2A48.B.9B4.BA.A11.2A$8.9B7.A63.9B7.A63.9B7.A63.9B7.A$9.8B7.2A63.
8B7.2A63.8B7.2A63.8B7.2A$10.7B73.7B73.7B73.7B$7.11B69.11B69.11B69.11B
$6.12B68.12B68.12B68.12B$6.12B68.12B68.12B68.12B$6.11B69.11B69.11B69.
11B$6.B3D4B.4B67.B3C4B.4B67.B3D4B.4B67.B3C4B.4B$6.2BD4B4.2A67.2BC4B4.
2A67.2BD4B4.2A67.2BC4B4.2A$6.2B3D2B4.A68.2B3C2B4.A68.2B3D2B4.A68.2B3C
2B4.A$6.6B6.3A65.6B6.3A65.6B6.3A65.6B6.3A$5.7B8.A64.7B8.A64.7B8.A64.
7B8.A$4.4B.B74.4B.B74.4B.B74.4B.B$4.3B77.3B77.3B77.3B$2.2AB77.2AB77.
2AB77.2AB$.A.AB76.A.AB76.A.AB76.A.AB$.A79.A79.A79.A$2A78.2A78.2A78.2A!
This still seems like it's clearly way more complicated than necessary, but I don't think anything better is known (?), any more than for the exact-timing OR problem. Somebody please find something nicer!

Meanwhile, this XOR gate seems to produce a complete Toffoli gate with a bounding box around 110x112 -- or a good bit smaller if Herschels are allowed as inputs, but let's please not go there.

Code: Select all

x = 159, y = 157, rule = LifeHistory
112.2D2.D2.D.3D3.D$111.D2.D.D2.D2.D3.2D7.B$111.D2.D.D2.D2.D4.D6.2D$
111.D2.D.D2.D2.D4.D5.B.2D$112.2D3.2D3.D3.3D3.2BD$131.4B$130.4B$129.4B
$128.4B$127.4B$126.4B$125.4B$124.4B$123.4B$122.4B$121.4B$120.4B$119.
4B$118.4B$117.4B$116.4B$115.4B$114.4B$113.4B$112.4B$111.4B$110.4B$
109.4B$108.4B$107.4B$9.2D2.D2.D.3D2.2D81.4B$8.D2.D.D2.D2.D5.D79.4B$3D
5.D2.D.D2.D2.D4.D79.4B$D3B4.D2.D.D2.D2.D3.D79.4B$.D3B4.2D3.2D3.D3.3D
76.4B$2.4B95.4B$3.4B93.4B$4.4B91.4B$5.4B46.3D.D2.D3.D31.4B$6.4B46.D2.
2D.D2.2D30.4B$7.4B45.D2.D.2D3.D29.4B$8.4B44.D2.D.2D3.D28.4B$9.4B42.3D
.D2.D2.3D26.4B$10.4B79.4B$11.4B77.4B$12.4B36.2A11.A6.2A17.4B$13.4B34.
B2AB9.A.A4.A2.A15.4B$14.4B34.3B9.A.A3.A.3A3.A10.4B7.2A$15.4B32.B.B9.
2A.2A.A.A6.3A7.4B8.A.A$16.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A$17.4B30.
6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A$18.4B29.8B4.2A.A.A3.A7.9B9.A2.A.A.
A.A.2A$19.4B29.13B2.A.AB2.A8.6B12.BABABA.A$20.4B26.13B5.A.A2B.A7.5B
14.B2ABA.A$21.4B24.15B5.A2B.2A6.7B14.2B.BA$22.4B23.15B4.3B10.6B14.3B$
23.4B21.17B.B.2B10.7B5.2A6.4B$24.4B20.29B4.6B6.A6.B2A3B$25.4B18.9B2C
2B2A16B2.7B6.A.AB3.B2A3B$26.4B16.9BCBC2B2A16B2.7B7.2AB.10B$27.4B14.2A
B3.6BC20B.9B8.13B$28.4B12.A2.A4.36B8.14B10.2A$29.4B10.A.2A5.6B3.B2.2B
2.20B4.B3.15B9.A$30.4B9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.
2D$31.4B7.2A6.9B14.19B2A4.6B5.7B.B2A7.D2.D.D2.D2.D5.D$32.4B13.4B4.2A
15.17B.B4.9B4.8B9.D2.D.D2.D2.D3.2D$33.4B11.4B5.A15.17B6.4B4.2A5.7B9.D
2.D.D2.D2.D5.D$34.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D$35.4B7.
4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A$36.4B5.4B21.A.AB4.12B3.4B10.A3.11B
A.2A$37.4B3.4B22.A9.11B.4B16.9B8.2A$38.4B.4B22.2A8.16B17.8B9.A$39.7B
33.15B12.A.2A2.9B5.BA.A$40.5B35.13B13.2A.A15B.B2A$40.5B16.2A18.11B19.
16B$39.7B14.B2AB17.10B20.10BDBD3B$38.4B.4B14.2B6.B11.9B21.11B2D2B16.A
$38.3B3.4B14.2B4.3B11.7B23.10BD4B13.3A$38.2B5.4B12.14B7.6B24.17B10.A$
38.B7.4B11.14B7.5B25.20B2.2B3.2A$47.4B.B5.17B6.5B27.15B.12B$48.28B4.
5B29.7B.4B.B.10B6.2A$48.30B.5B24.2A4.7B.4B3.12B5.A$48.35B26.A4.6B2.4B
.14B2.3A$48.34B27.A.AB2.4B4.20BA$49.33B28.2AB2.B.2B.A9.12B$47.2AB2.
31B29.3B.AB.A.A8.11B$46.A.AB4.B.16B2.4B.B33.B3A3.A9.10B$46.A11.10B.2B
3.3B36.A15.11B.B.2A3.2A$45.2A12.9B4.4B35.3AB4A10.14BA.A.A.A$56.11B5.
2A9.B2A24.A4.A2.A10.13B.B.A.A$55.12B6.A9.BA.A24.3A13.2AB.13B2A.2A$55.
12B3.3A13.A26.2A11.A.AB4.9B.B$44.2A.2A2.2A2.11B4.A15.2A38.A7.9B$43.A.
A.A2.A.A2.8B.4B57.2A7.9B$43.A.A2.2A.B3.7B4.2A66.10B$44.A.A.A2.2B2.7B
4.A66.12B$45.A2.A.BA2B.6B6.3A63.13B$46.3A.A.A8B8.A63.14B$49.A.A.8B73.
14B$46.2A2.A4.5B72.4B.4B3.5B$44.3A.2A4.6B72.2A4.4B.2B.4B$43.A4.B6.6B
72.A4.2B3.2B2.4B$44.3AB2AB3.7B69.3A6.6B3.4B$46.A.2AB.8B70.A8.7B3.4B$
50.10B79.8B3.4B$50.6B2A3B79.8B3.4B$50.6B2A2B5.2A73.8B4.4B$50.10B5.A4.
3D.D2.D2.2D57.6B2.B2A3.4B$49.11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B$49.
8B2C2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B$48.8B2C5B8.D2.D.2D2.D43.A8.B
4.8B4.2A4.3B$47.11BC4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.2B$44.2B.16B
62.2AB.13B2A3B11.B$43.2A18B64.18B$43.2AB.17B63.17B$44.B.4B.8B2.4B63.
13B$51.7B4.4B64.12B$52.6B5.4B65.10B$54.4B6.4B64.11B$56.3BA5.4B64.2B.
7B$57.BA.A5.4B63.11B$58.A.A6.4B61.11B$59.A8.4B60.11B$60.3A6.4B59.11B$
62.A7.3B47.2A.2A2.2A3.B3.4B2.B2A$71.2B48.A.A2.A.A3.2B.4B3.BA.A$72.B
48.A2.2A.B4.2B3.2B6.A$122.A.A2.2B3.6B7.2A$121.2A.A.BA2B.7B$124.A.A.A
9B$121.4A2.A.8B$121.A3.2A4.6B$123.A.B6.6B$122.2AB2AB3.7B$125.2AB.8B$
122.2A3.10B$122.A4.6B2A3B$123.A3.6B2A2B5.2A$122.2A3.10B5.A$126.11B2.B
A.A$126.12B.B2A$125.15B$124.16B6.3D.D2.D2.2D$121.2B.16B7.D2.2D.D4.D$
120.2A16B2C7.D2.D.2D2.2D$120.2AB.14BCBC6.D2.D.2D4.D$121.B.4B.8B2.C3B
4.3D.D2.D2.2D$128.7B4.4B$129.6B5.4B$131.4B6.4B$133.3BA5.4B$134.BA.A5.
4B$135.A.A6.4B$136.A8.3B$137.3A6.2B$139.A7.B!
#C [[ HEIGHT 600 ZOOM 3 THUMBNAIL THUMBSIZE 3 ]]

User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Challenge: Minimal Toffoli gate

Post by dvgrn » February 18th, 2018, 3:27 pm

Just for the record, here's the test pattern showing all eight input combinations. In a Toffoli gate, the outputs are usually the same as the inputs -- except when the first two inputs are both on, in which case you get the opposite of input #3.

Code: Select all

x = 766, y = 347, rule = LifeHistory
305.A435.A$304.A.A433.A.A$304.A2.A432.A2.A$305.2A434.2A$118.2D2.D2.D.
3D3.D143.2D2.D2.D.3D3.D261.2D2.D2.D.3D3.D143.2D2.D2.D.3D3.D$117.D2.D.
D2.D2.D3.2D7.B134.D2.D.D2.D2.D3.2D7.B252.D2.D.D2.D2.D3.2D7.B134.D2.D.
D2.D2.D3.2D7.B$117.D2.D.D2.D2.D4.D6.2D134.D2.D.D2.D2.D4.D6.2E252.D2.D
.D2.D2.D4.D6.2D134.D2.D.D2.D2.D4.D6.2E$117.D2.D.D2.D2.D4.D5.B.2D133.D
2.D.D2.D2.D4.D5.2B2E251.D2.D.D2.D2.D4.D5.B.2D133.D2.D.D2.D2.D4.D5.2B
2E$118.2D3.2D3.D3.3D3.2BD136.2D3.2D3.D3.3D3.2BEB253.2D3.2D3.D3.3D3.2B
D136.2D3.2D3.D3.3D3.2BE$137.4B155.4B273.4B155.4B$136.4B155.4B273.4B
155.4B$135.4B155.4B273.4B155.4B$134.4B155.4B273.4B155.4B$133.4B155.4B
273.4B155.4B$132.4B155.4B273.4B155.4B$131.4B155.4B273.4B155.4B$130.4B
155.4B273.4B155.4B$129.4B155.4B273.4B155.4B$128.4B155.4B273.4B155.4B$
127.4B155.4B273.4B155.4B$126.4B155.4B273.4B155.4B$125.4B155.4B273.4B
155.4B$124.4B155.4B273.4B155.4B$123.4B155.4B273.4B155.4B$122.4B155.4B
273.4B155.4B$121.4B155.4B273.4B155.4B$120.4B155.4B273.4B155.4B$119.4B
155.4B273.4B155.4B$118.4B155.4B273.4B155.4B$117.4B155.4B273.4B155.4B$
116.4B155.4B273.4B155.4B$115.4B155.4B273.4B155.4B$114.4B155.4B273.4B
155.4B$113.4B155.4B273.4B155.4B$15.2D2.D2.D.3D2.2D81.4B58.2D2.D2.D.3D
2.2D81.4B176.2D2.D2.D.3D2.2D81.4B58.2D2.D2.D.3D2.2D81.4B$14.D2.D.D2.D
2.D5.D79.4B58.D2.D.D2.D2.D5.D79.4B176.D2.D.D2.D2.D5.D79.4B58.D2.D.D2.
D2.D5.D79.4B$6.3D5.D2.D.D2.D2.D4.D79.4B51.3D5.D2.D.D2.D2.D4.D79.4B
169.3D5.D2.D.D2.D2.D4.D79.4B51.3D5.D2.D.D2.D2.D4.D79.4B$6.D3B4.D2.D.D
2.D2.D3.D79.4B52.D3B4.D2.D.D2.D2.D3.D79.4B170.D3B4.D2.D.D2.D2.D3.D79.
4B52.D3B4.D2.D.D2.D2.D3.D79.4B$7.D3B4.2D3.2D3.D3.3D76.4B54.D3B4.2D3.
2D3.D3.3D76.4B172.D3B4.2D3.2D3.D3.3D76.4B54.D3B4.2D3.2D3.D3.3D76.4B$
8.4B95.4B56.4B95.4B174.4B95.4B56.4B95.4B$9.4B93.4B58.4B93.4B176.4B93.
4B58.4B93.4B$10.4B91.4B60.4B91.4B178.4B91.4B60.4B91.4B$11.4B46.3D.D2.
D3.D31.4B62.4B46.3D.D2.D3.D31.4B180.4B46.3D.D2.D3.D31.4B62.4B46.3D.D
2.D3.D31.4B$12.4B46.D2.2D.D2.2D30.4B64.4B46.D2.2D.D2.2D30.4B182.4B46.
D2.2D.D2.2D30.4B64.4B46.D2.2D.D2.2D30.4B$13.4B45.D2.D.2D3.D29.4B66.4B
45.D2.D.2D3.D29.4B184.4B45.D2.D.2D3.D29.4B66.4B45.D2.D.2D3.D29.4B$14.
4B44.D2.D.2D3.D28.4B68.4B44.D2.D.2D3.D28.4B186.4B44.D2.D.2D3.D28.4B
68.4B44.D2.D.2D3.D28.4B$15.4B42.3D.D2.D2.3D26.4B70.4B42.3D.D2.D2.3D
26.4B188.4B42.3D.D2.D2.3D26.4B70.4B42.3D.D2.D2.3D26.4B$16.4B79.4B72.
4B79.4B190.4B79.4B72.4B79.4B$17.4B77.4B74.4B77.4B192.4B77.4B74.4B77.
4B$18.4B36.2A11.A6.2A17.4B76.4B36.2A11.A6.2A17.4B194.4B36.2A11.A6.2A
17.4B76.4B36.2A11.A6.2A17.4B$19.4B34.B2AB9.A.A4.A2.A15.4B78.4B34.B2AB
9.A.A4.A2.A15.4B196.4B34.B2AB9.A.A4.A2.A15.4B78.4B34.B2AB9.A.A4.A2.A
15.4B$20.4B34.3B9.A.A3.A.3A3.A10.4B7.2A71.4B34.3B9.A.A3.A.3A3.A10.4B
7.2A189.4B34.3B9.A.A3.A.3A3.A10.4B7.2A71.4B34.3B9.A.A3.A.3A3.A10.4B7.
2A$21.4B32.B.B9.2A.2A.A.A6.3A7.4B8.A.A71.4B32.B.B9.2A.2A.A.A6.3A7.4B
8.A.A189.4B32.B.B9.2A.2A.A.A6.3A7.4B8.A.A71.4B32.B.B9.2A.2A.A.A6.3A7.
4B8.A.A$22.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A66.4B31.5B8.B2.A.A3.2A6.
A5.4B11.A4.2A184.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A66.4B31.5B8.B2.A.A
3.2A6.A5.4B11.A4.2A$23.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A65.4B
30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A183.4B30.6B6.2ABA2.4A.A5.2A.7B8.
4A.2A2.A2.A65.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A$24.4B29.8B4.2A.
A.A3.A7.9B9.A2.A.A.A.A.2A66.4B29.8B4.2A.A.A3.A7.9B9.A2.A.A.A.A.2A184.
4B29.8B4.2A.A.A3.A7.9B9.A2.A.A.A.A.2A66.4B29.8B4.2A.A.A3.A7.9B9.A2.A.
A.A.A.2A$25.4B29.13B2.A.AB2.A8.6B12.BABABA.A70.4B29.13B2.A.AB2.A8.6B
12.BABABA.A188.4B29.13B2.A.AB2.A8.6B12.BABABA.A70.4B29.13B2.A.AB2.A8.
6B12.BABABA.A$26.4B26.13B5.A.A2B.A7.5B14.B2ABA.A71.4B26.13B5.A.A2B.A
7.5B14.B2ABA.A189.4B26.13B5.A.A2B.A7.5B14.B2ABA.A71.4B26.13B5.A.A2B.A
7.5B14.B2ABA.A$27.4B24.15B5.A2B.2A6.7B14.2B.BA73.4B24.15B5.A2B.2A6.7B
14.2B.BA191.4B24.15B5.A2B.2A6.7B14.2B.BA73.4B24.15B5.A2B.2A6.7B14.2B.
BA$28.4B23.15B4.3B10.6B14.3B77.4B23.15B4.3B10.6B14.3B195.4B23.15B4.3B
10.6B14.3B77.4B23.15B4.3B10.6B14.3B$29.4B21.17B.B.2B10.7B5.2A6.4B78.
4B21.17B.B.2B10.7B5.2A6.4B196.4B21.17B.B.2B10.7B5.2A6.4B78.4B21.17B.B
.2B10.7B5.2A6.4B$30.4B20.29B4.6B6.A6.B2A3B77.4B20.29B4.6B6.A6.B2A3B
195.4B20.29B4.6B6.A6.B2A3B77.4B20.29B4.6B6.A6.B2A3B$31.4B18.9B2D2B2A
16B2.7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B196.4B18.9B2D
2B2A16B2.7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B$32.4B16.
9BDBD2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B195.4B16.9B
DBD2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B$33.4B14.2AB
3.6BD20B.9B8.13B77.4B14.2AB3.6BC20B.9B8.13B195.4B14.2AB3.6BD20B.9B8.
13B77.4B14.2AB3.6BC20B.9B8.13B$34.4B12.A2.A4.36B8.14B10.2A65.4B12.A2.
A4.36B8.14B10.2A183.4B12.A2.A4.36B8.14B10.2A65.4B12.A2.A4.36B8.14B10.
2A$35.4B10.A.2A5.6B3.B2.2B2.20B4.B3.15B9.A67.4B10.A.2A5.6B3.B2.2B2.
20B4.B3.15B9.A185.4B10.A.2A5.6B3.B2.2B2.20B4.B3.15B9.A67.4B10.A.2A5.
6B3.B2.2B2.20B4.B3.15B9.A$36.4B9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D
2.D.3D2.2D45.4B9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.2D163.4B
9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.2D45.4B9.A7.6B14.19B.B
2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.2D$37.4B7.2A6.9B14.19B2A4.6B5.7B.B2A7.
D2.D.D2.D2.D5.D45.4B7.2A6.9B14.19B2A4.6B5.7B.B2A7.D2.D.D2.D2.D5.D163.
4B7.2A6.9B14.19B2A4.6B5.7B.B2A7.D2.D.D2.D2.D5.D45.4B7.2A6.9B14.19B2A
4.6B5.7B.B2A7.D2.D.D2.D2.D5.D$38.4B13.4B4.2A15.17B.B4.9B4.8B9.D2.D.D
2.D2.D3.2D47.4B13.4B4.2A15.17B.B4.9B4.8B9.D2.D.D2.D2.D3.2D165.4B13.4B
4.2A15.17B.B4.9B4.8B9.D2.D.D2.D2.D3.2D47.4B13.4B4.2A15.17B.B4.9B4.8B
9.D2.D.D2.D2.D3.2D$39.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D5.D
47.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D5.D165.4B11.4B5.A15.17B
6.4B4.2A5.7B9.D2.D.D2.D2.D5.D47.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D
2.D2.D5.D$40.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D49.4B9.4B7.3A
12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D167.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.
2D3.D3.2D49.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D$41.4B7.4B10.A
10.2AB.15B4.4B7.3A3.9B2.2A.A68.4B7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A
186.4B7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A68.4B7.4B10.A10.2AB.15B4.4B
7.3A3.9B2.2A.A$42.4B5.4B21.A.AB4.12B3.4B10.A3.11BA.2A69.4B5.4B21.A.AB
4.12B3.4B10.A3.11BA.2A187.4B5.4B21.A.AB4.12B3.4B10.A3.11BA.2A69.4B5.
4B21.A.AB4.12B3.4B10.A3.11BA.2A$43.4B3.4B22.A9.11B.4B16.9B8.2A65.4B3.
4B22.A9.11B.4B16.9B8.2A183.4B3.4B22.A9.11B.4B16.9B8.2A65.4B3.4B22.A9.
11B.4B16.9B8.2A$44.4B.4B22.2A8.16B17.8B9.A67.4B.4B22.2A8.16B17.8B9.A
185.4B.4B22.2A8.16B17.8B9.A67.4B.4B22.2A8.16B17.8B9.A$45.7B33.15B12.A
.2A2.9B5.BA.A68.7B33.15B12.A.2A2.9B5.BA.A186.7B33.15B12.A.2A2.9B5.BA.
A68.7B33.15B12.A.2A2.9B5.BA.A$46.5B35.13B13.2A.A15B.B2A70.5B35.13B13.
2A.A15B.B2A188.5B35.13B13.2A.A15B.B2A70.5B35.13B13.2A.A15B.B2A$46.5B
16.2A18.11B19.16B72.5B16.2A18.11B19.16B190.5B16.2A18.11B19.16B72.5B
16.2A18.11B19.16B$45.7B14.B2AB17.10B20.10BDBD3B71.7B14.B2AB17.10B20.
10BDBD3B189.7B14.B2AB17.10B20.10BEBE3B71.7B14.B2AB17.10B20.10BEBE3B$
44.4B.4B14.2B6.B11.9B21.11B2D2B16.A54.4B.4B14.2B6.B11.9B21.11B2D2B16.
A172.4B.4B14.2B6.B11.9B21.11B2E2B16.A54.4B.4B14.2B6.B11.9B21.11B2E2B
16.A$44.3B3.4B14.2B4.3B11.7B23.10BD4B13.3A54.3B3.4B14.2B4.3B11.7B23.
10BD4B13.3A172.3B3.4B14.2B4.3B11.7B23.10BE4B13.3A54.3B3.4B14.2B4.3B
11.7B23.10BE4B13.3A$44.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B
24.17B10.A175.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B24.17B10.A
$44.B7.4B11.14B7.5B25.20B2.2B3.2A56.B7.4B11.14B7.5B25.20B2.2B3.2A174.
B7.4B11.14B7.5B25.20B2.2B3.2A56.B7.4B11.14B7.5B25.20B2.2B3.2A$53.4B.B
5.17B6.5B27.15B.12B65.4B.B5.17B6.5B27.15B.12B183.4B.B5.17B6.5B27.28B
65.4B.B5.17B6.5B27.28B$54.28B4.5B29.7B.4B.B.10B6.2A60.28B4.5B29.7B.4B
.B.10B6.2A178.28B4.5B29.7B.17B6.2A60.28B4.5B29.7B.17B6.2A$54.30B.5B
24.2A4.7B.4B3.12B5.A60.30B.5B24.2A4.7B.4B3.12B5.A178.30B.5B24.2A4.7B.
19B5.A60.30B.5B24.2A4.7B.19B5.A$54.35B26.A4.6B2.4B.14B2.3A61.35B26.A
4.6B2.4B.14B2.3A179.35B26.A4.6B2.19B2.3A61.35B26.A4.6B2.19B2.3A$54.
34B27.A.AB2.4B4.20BA63.34B27.A.AB2.4B4.20BA181.34B27.A.AB2.4B4.20BA
63.34B27.A.AB2.4B4.20BA$55.33B28.2AB2.B.2B.A9.12B66.33B28.2AB2.B.2B.A
9.12B184.33B28.2AB2.B.2B.A9.12B66.33B28.2AB2.B.2B.A9.12B$53.2AB2.31B
29.3B.AB.A.A8.11B65.2AB2.31B29.3B.AB.A.A8.11B183.2AB2.31B29.3B.AB.A.A
8.11B65.2AB2.31B29.3B.AB.A.A8.11B$52.A.AB4.B.16B2.4B.B33.B3A3.A9.10B
65.A.AB4.B.16B2.4B.B33.B3A3.A9.10B183.A.AB4.B.16B2.4B.B33.B3A3.A9.10B
65.A.AB4.B.16B2.4B.B33.B3A3.A9.10B$52.A11.10B.2B3.3B36.A15.11B.B.2A3.
2A55.A11.10B.2B3.3B36.A15.11B.B.2A3.2A173.A11.10B.2B3.3B36.A15.11B.B.
2A3.2A55.A11.10B.2B3.3B36.A15.11B.B.2A3.2A$51.2A12.9B4.4B35.3AB4A10.
14BA.A.A.A54.2A12.9B4.4B35.3AB4A10.14BA.A.A.A172.2A12.9B4.4B35.3AB4A
10.14BA.A.A.A54.2A12.9B4.4B35.3AB4A10.14BA.A.A.A$62.11B5.2A9.B2A24.A
4.A2.A10.13B.B.A.A67.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A185.11B5.2A9.B
2A24.A4.A2.A10.13B.B.A.A67.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A$61.12B
6.A9.BA.A24.3A13.2AB.13B2A.2A65.12B6.A9.BA.A24.3A13.2AB.13B2A.2A183.
12B6.A9.BA.A24.3A13.2AB.13B2A.2A65.12B6.A9.BA.A24.3A13.2AB.13B2A.2A$
61.12B3.3A13.A26.2A11.A.AB4.9B.B69.12B3.3A13.A26.2A11.A.AB4.9B.B187.
12B3.3A13.A26.2A11.A.AB4.9B.B69.12B3.3A13.A26.2A11.A.AB4.9B.B$50.2A.
2A2.2A2.11B4.A15.2A38.A7.9B60.2A.2A2.2A2.11B4.A15.2A38.A7.9B178.2A.2A
2.2A2.11B4.A15.2A38.A7.9B60.2A.2A2.2A2.11B4.A15.2A38.A7.9B$49.A.A.A2.
A.A2.8B.4B57.2A7.9B59.A.A.A2.A.A2.8B.4B57.2A7.9B177.A.A.A2.A.A2.8B.4B
57.2A7.9B59.A.A.A2.A.A2.8B.4B57.2A7.9B$49.A.A2.2A.B3.7B4.2A66.10B58.A
.A2.2A.B3.7B4.2A66.10B176.A.A2.2A.B3.7B4.2A66.10B58.A.A2.2A.B3.7B4.2A
66.10B$50.A.A.A2.2B2.7B4.A66.12B58.A.A.A2.2B2.7B4.A66.12B176.A.A.A2.
2B2.7B4.A66.12B58.A.A.A2.2B2.7B4.A66.12B$51.A2.A.BA2B.6B6.3A63.13B58.
A2.A.BA2B.6B6.3A63.13B176.A2.A.BA2B.6B6.3A63.13B58.A2.A.BA2B.6B6.3A
63.13B$52.3A.A.A8B8.A63.14B58.3A.A.A8B8.A63.14B176.3A.A.A8B8.A63.14B
58.3A.A.A8B8.A63.14B$55.A.A.8B73.14B60.A.A.8B73.14B178.A.A.8B73.14B
60.A.A.8B73.14B$52.2A2.A4.5B72.4B.4B3.5B56.2A2.A4.5B72.4B.4B3.5B174.
2A2.A4.5B72.4B.12B56.2A2.A4.5B72.4B.12B$50.3A.2A4.6B72.2A4.4B.2B.4B
53.3A.2A4.6B72.2A4.4B.2B.4B171.3A.2A4.6B72.2A4.7B.4B53.3A.2A4.6B72.2A
4.7B.4B$49.A4.B6.6B72.A4.2B3.2B2.4B51.A4.B6.6B72.A4.2B3.2B2.4B169.A4.
B6.6B72.A4.7B2.4B51.A4.B6.6B72.A4.7B2.4B$50.3AB2AB3.7B69.3A6.6B3.4B
51.3AB2AB3.7B69.3A6.6B3.4B169.3AB2AB3.7B69.3A6.6B3.4B51.3AB2AB3.7B69.
3A6.6B3.4B$52.A.2AB.8B70.A8.7B3.4B52.A.2AB.8B70.A8.7B3.4B170.A.2AB.8B
70.A8.7B3.4B52.A.2AB.8B70.A8.7B3.4B$56.10B79.8B3.4B55.10B79.8B3.4B
173.10B79.8B3.4B55.10B79.8B3.4B$56.6B2A3B79.8B3.4B54.6B2A3B79.8B3.4B
172.6B2A3B79.8B3.4B54.6B2A3B79.8B3.4B$56.6B2A2B5.2A73.8B4.4B53.6B2A2B
5.2A73.8B4.4B171.6B2A2B5.2A73.8B4.4B53.6B2A2B5.2A73.8B4.4B$56.10B5.A
4.3D.D2.D2.2D57.6B2.B2A3.4B52.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B170.
10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B52.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B
$55.11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B50.11B2.BA.A5.D2.2D.D4.D56.7B.
BA.A3.4B168.11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B50.11B2.BA.A5.D2.2D.D
4.D56.7B.BA.A3.4B$55.8B2D2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B49.8B2D2B
.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B167.8B2D2B.B2A6.D2.D.2D3.D41.2A15.6B
4.A4.4B49.8B2D2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B$54.8B2D5B8.D2.D.2D
2.D43.A8.B4.8B4.2A4.3B48.8B2D5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B166.8B
2D5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B48.8B2D5B8.D2.D.2D2.D43.A8.B4.8B4.
2A4.3B$53.11BD4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.2B47.11BD4B7.3D.D2.
D2.3D41.A.AB3.4B.6B2A2B11.2B165.11BD4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B
11.2B47.11BD4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.2B$50.2B.16B62.2AB.
13B2A3B11.B44.2B.16B62.2AB.13B2A3B11.B162.2B.16B62.2AB.13B2A3B11.B44.
2B.16B62.2AB.13B2A3B11.B$49.2A18B64.18B57.2A18B64.18B175.2A18B64.18B
17.2A38.2A18B64.18B17.2A$49.2AB.17B63.17B58.2AB.17B63.17B176.2AB.17B
63.17B17.A2.A37.2AB.17B63.17B17.A2.A$50.B.4B.8B2.4B63.13B62.B.4B.8B2.
4B63.13B180.B.4B.8B2.4B63.13B20.A.A39.B.4B.8B2.4B63.13B20.A.A$57.7B4.
4B64.12B68.7B4.4B64.12B186.7B4.4B64.12B20.A47.7B4.4B64.12B20.A$58.6B
5.4B65.10B69.6B5.4B65.10B187.6B5.4B65.10B69.6B5.4B65.10B$60.4B6.4B64.
11B70.4B6.4B64.11B188.4B6.4B64.11B70.4B6.4B64.11B$62.3BA5.4B64.2B.7B
72.3BA5.4B64.2B.7B190.3BA5.4B64.2B.7B72.3BA5.4B64.2B.7B$63.BA.A5.4B
63.11B72.BA.A5.4B63.11B190.BA.A5.4B63.11B72.BA.A5.4B63.11B$64.A.A6.4B
61.11B74.A.A6.4B61.11B192.A.A6.4B61.11B74.A.A6.4B61.11B$65.A8.4B60.
11B75.A8.4B60.11B193.A8.4B60.11B75.A8.4B60.11B$66.3A6.4B59.11B76.3A6.
4B59.11B194.3A6.4B59.11B76.3A6.4B59.11B$68.A7.3B47.2A.2A2.2A3.B3.4B2.
B2A76.A7.3B47.2A.2A2.2A3.B3.4B2.B2A194.A7.3B47.2A.2A2.2A3.8B2.B2A76.A
7.3B47.2A.2A2.2A3.8B2.B2A$77.2B48.A.A2.A.A3.2B.4B3.BA.A84.2B48.A.A2.A
.A3.2B.4B3.BA.A202.2B48.A.A2.A.A3.7B3.BA.A84.2B48.A.A2.A.A3.7B3.BA.A$
78.B48.A2.2A.B4.2B3.2B6.A85.B48.A2.2A.B4.2B3.2B6.A203.B48.A2.2A.B4.7B
6.A85.B48.A2.2A.B4.7B6.A$128.A.A2.2B3.6B7.2A134.A.A2.2B3.6B7.2A252.A.
A2.2B3.6B7.2A134.A.A2.2B3.6B7.2A$127.2A.A.BA2B.7B142.2A.A.BA2B.7B260.
2A.A.BA2B.7B142.2A.A.BA2B.7B$130.A.A.A9B145.A.A.A9B263.A.A.A9B145.A.A
.A9B$127.4A2.A.8B143.4A2.A.8B261.4A2.A.8B143.4A2.A.8B$127.A3.2A4.6B
143.A3.2A4.6B261.A3.2A4.6B143.A3.2A4.6B$129.A.B6.6B144.A.B6.6B262.A.B
6.6B144.A.B6.6B$128.2AB2AB3.7B143.2AB2AB3.7B261.2AB2AB3.7B143.2AB2AB
3.7B$131.2AB.8B147.2AB.8B265.2AB.8B147.2AB.8B$128.2A3.10B144.2A3.10B
262.2A3.10B144.2A3.10B$128.A4.6B2A3B143.A4.6B2A3B261.A4.6B2A3B143.A4.
6B2A3B$129.A3.6B2A2B5.2A138.A3.6B2A2B5.2A256.A3.6B2A2B5.2A138.A3.6B2A
2B5.2A$128.2A3.10B5.A138.2A3.10B5.A256.2A3.10B5.A138.2A3.10B5.A$132.
11B2.BA.A142.11B2.BA.A260.11B2.BA.A142.11B2.BA.A$132.12B.B2A143.12B.B
2A261.12B.B2A143.12B.B2A$131.15B144.15B262.15B144.15B$130.16B6.3D.D2.
D2.2D125.16B6.3D.D2.D2.2D243.16B6.3D.D2.D2.2D125.16B6.3D.D2.D2.2D$
127.2B.16B7.D2.2D.D4.D121.2B.16B7.D2.2D.D4.D239.2B.16B7.D2.2D.D4.D
121.2B.16B7.D2.2D.D4.D$126.2A16B2D7.D2.D.2D2.2D121.2A16B2D7.D2.D.2D2.
2D239.2A16B2C7.D2.D.2D2.2D121.2A16B2C7.D2.D.2D2.2D$126.2AB.14BDBD6.D
2.D.2D4.D120.2AB.14BDBD6.D2.D.2D4.D238.2AB.14BCBC6.D2.D.2D4.D120.2AB.
14BCBC6.D2.D.2D4.D$127.B.4B.8B2.D3B4.3D.D2.D2.2D122.B.4B.8B2.D3B4.3D.
D2.D2.2D240.B.4B.8B2.C3B4.3D.D2.D2.2D122.B.4B.8B2.C3B4.3D.D2.D2.2D$
134.7B4.4B144.7B4.4B262.7B4.4B144.7B4.4B$135.6B5.4B144.6B5.4B262.6B5.
4B144.6B5.4B$137.4B6.4B145.4B6.4B263.4B6.4B145.4B6.4B$139.3BA5.4B146.
3BA5.4B264.3BA5.4B146.3BA5.4B$140.BA.A5.4B146.BA.A5.4B264.BA.A5.4B
146.BA.A5.4B$141.A.A6.4B146.A.A6.4B264.A.A6.4B146.A.A6.4B$142.A8.3B
147.A8.3B265.A8.3B147.A8.3B$143.3A6.2B148.3A6.2B266.3A6.2B148.3A6.2B$
145.A7.B150.A7.B268.A7.B150.A7.B25$741.A$305.A434.A.A$304.A.A433.A2.A
$304.A2.A433.2A$305.2A247.2D2.D2.D.3D3.D143.2D2.D2.D.3D3.D$118.2D2.D
2.D.3D3.D143.2D2.D2.D.3D3.D260.D2.D.D2.D2.D3.2D7.B134.D2.D.D2.D2.D3.
2D7.B$117.D2.D.D2.D2.D3.2D7.B134.D2.D.D2.D2.D3.2D7.B252.D2.D.D2.D2.D
4.D6.2D134.D2.D.D2.D2.D4.D6.2E$117.D2.D.D2.D2.D4.D6.2D134.D2.D.D2.D2.
D4.D6.2E252.D2.D.D2.D2.D4.D5.B.2D133.D2.D.D2.D2.D4.D5.2B2E$117.D2.D.D
2.D2.D4.D5.B.2D133.D2.D.D2.D2.D4.D5.2B2E252.2D3.2D3.D3.3D3.2BD136.2D
3.2D3.D3.3D3.2BEB$118.2D3.2D3.D3.3D3.2BD136.2D3.2D3.D3.3D3.2BEB272.4B
155.4B$137.4B155.4B272.4B155.4B$136.4B155.4B272.4B155.4B$135.4B155.4B
272.4B155.4B$134.4B155.4B272.4B155.4B$133.4B155.4B272.4B155.4B$132.4B
155.4B272.4B155.4B$131.4B155.4B272.4B155.4B$130.4B155.4B272.4B155.4B$
129.4B155.4B272.4B155.4B$128.4B155.4B272.4B155.4B$127.4B155.4B272.4B
155.4B$126.4B155.4B272.4B155.4B$125.4B155.4B272.4B155.4B$124.4B155.4B
272.4B155.4B$123.4B155.4B272.4B155.4B$122.4B155.4B272.4B155.4B$121.4B
155.4B272.4B155.4B$120.4B155.4B272.4B155.4B$119.4B155.4B272.4B155.4B$
118.4B155.4B272.4B155.4B$117.4B155.4B158.A113.4B41.A113.4B$2.A113.4B
41.A113.4B158.A.A111.4B41.A.A111.4B$.A.A111.4B41.A.A111.4B158.A2.A
110.4B41.A2.A110.4B$A2.A110.4B41.A2.A110.4B160.2A110.4B43.2A110.4B$.
2A110.4B43.2A110.4B175.2D2.D2.D.3D2.2D81.4B58.2D2.D2.D.3D2.2D81.4B$
15.2D2.D2.D.3D2.2D81.4B58.2D2.D2.D.3D2.2D81.4B175.D2.D.D2.D2.D5.D79.
4B58.D2.D.D2.D2.D5.D79.4B$14.D2.D.D2.D2.D5.D79.4B58.D2.D.D2.D2.D5.D
79.4B168.3E5.D2.D.D2.D2.D4.D79.4B51.3E5.D2.D.D2.D2.D4.D79.4B$6.3E5.D
2.D.D2.D2.D4.D79.4B51.3E5.D2.D.D2.D2.D4.D79.4B169.E3B4.D2.D.D2.D2.D3.
D79.4B52.E3B4.D2.D.D2.D2.D3.D79.4B$6.E3B4.D2.D.D2.D2.D3.D79.4B52.E3B
4.D2.D.D2.D2.D3.D79.4B171.E3B4.2D3.2D3.D3.3D76.4B54.E3B4.2D3.2D3.D3.
3D76.4B$7.E3B4.2D3.2D3.D3.3D76.4B54.E3B4.2D3.2D3.D3.3D76.4B173.4B95.
4B56.4B95.4B$8.4B95.4B56.4B95.4B175.4B93.4B58.4B93.4B$9.4B93.4B58.4B
93.4B177.4B91.4B60.4B91.4B$10.4B91.4B60.4B91.4B179.4B46.3D.D2.D3.D31.
4B62.4B46.3D.D2.D3.D31.4B$11.4B46.3D.D2.D3.D31.4B62.4B46.3D.D2.D3.D
31.4B181.4B46.D2.2D.D2.2D30.4B64.4B46.D2.2D.D2.2D30.4B$12.4B46.D2.2D.
D2.2D30.4B64.4B46.D2.2D.D2.2D30.4B183.4B45.D2.D.2D3.D29.4B66.4B45.D2.
D.2D3.D29.4B$13.4B45.D2.D.2D3.D29.4B66.4B45.D2.D.2D3.D29.4B185.4B44.D
2.D.2D3.D28.4B68.4B44.D2.D.2D3.D28.4B$14.4B44.D2.D.2D3.D28.4B68.4B44.
D2.D.2D3.D28.4B187.4B42.3D.D2.D2.3D26.4B70.4B42.3D.D2.D2.3D26.4B$15.
4B42.3D.D2.D2.3D26.4B70.4B42.3D.D2.D2.3D26.4B189.4B79.4B72.4B79.4B$
16.4B79.4B72.4B79.4B191.4B77.4B74.4B77.4B$17.4B77.4B74.4B77.4B193.4B
36.2A11.A6.2A17.4B76.4B36.2A11.A6.2A17.4B$18.4B36.2A11.A6.2A17.4B76.
4B36.2A11.A6.2A17.4B195.4B34.B2AB9.A.A4.A2.A15.4B78.4B34.B2AB9.A.A4.A
2.A15.4B$19.4B34.B2AB9.A.A4.A2.A15.4B78.4B34.B2AB9.A.A4.A2.A15.4B197.
4B34.3B9.A.A3.A.3A3.A10.4B7.2A71.4B34.3B9.A.A3.A.3A3.A10.4B7.2A$20.4B
34.3B9.A.A3.A.3A3.A10.4B7.2A71.4B34.3B9.A.A3.A.3A3.A10.4B7.2A190.4B
32.B.B9.2A.2A.A.A6.3A7.4B8.A.A71.4B32.B.B9.2A.2A.A.A6.3A7.4B8.A.A$21.
4B32.B.B9.2A.2A.A.A6.3A7.4B8.A.A71.4B32.B.B9.2A.2A.A.A6.3A7.4B8.A.A
190.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A66.4B31.5B8.B2.A.A3.2A6.A5.4B
11.A4.2A$22.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A66.4B31.5B8.B2.A.A3.2A
6.A5.4B11.A4.2A185.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A65.4B30.6B
6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A$23.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A
2.A2.A65.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A184.4B29.8B4.2A.A.A3.
A7.9B9.A2.A.A.A.A.2A66.4B29.8B4.2A.A.A3.A7.9B9.A2.A.A.A.A.2A$24.4B29.
8B4.2A.A.A3.A7.9B9.A2.A.A.A.A.2A66.4B29.8B4.2A.A.A3.A7.9B9.A2.A.A.A.A
.2A185.4B29.13B2.A.AB2.A8.6B12.BABABA.A70.4B29.13B2.A.AB2.A8.6B12.BAB
ABA.A$25.4B29.13B2.A.AB2.A8.6B12.BABABA.A70.4B29.13B2.A.AB2.A8.6B12.B
ABABA.A189.4B26.13B5.A.A2B.A7.5B14.B2ABA.A71.4B26.13B5.A.A2B.A7.5B14.
B2ABA.A$26.4B26.13B5.A.A2B.A7.5B14.B2ABA.A71.4B26.13B5.A.A2B.A7.5B14.
B2ABA.A190.4B24.15B5.A2B.2A6.7B14.2B.BA73.4B24.15B5.A2B.2A6.7B14.2B.B
A$27.4B24.15B5.A2B.2A6.7B14.2B.BA73.4B24.15B5.A2B.2A6.7B14.2B.BA192.
4B23.15B4.3B10.6B14.3B77.4B23.15B4.3B10.6B14.3B$28.4B23.15B4.3B10.6B
14.3B77.4B23.15B4.3B10.6B14.3B196.4B21.17B.B.2B10.7B5.2A6.4B78.4B21.
17B.B.2B10.7B5.2A6.4B$29.4B21.17B.B.2B10.7B5.2A6.4B78.4B21.17B.B.2B
10.7B5.2A6.4B197.4B20.29B4.6B6.A6.B2A3B77.4B20.29B4.6B6.A6.B2A3B$30.
4B20.29B4.6B6.A6.B2A3B77.4B20.29B4.6B6.A6.B2A3B196.4B18.9B2D2B2A16B2.
7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B$31.4B18.9B2D2B2A
16B2.7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B197.4B16.9BDB
D2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B$32.4B16.9BDBD
2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B196.4B14.2AB3.6B
D20B.9B8.13B77.4B14.2AB3.6BC20B.9B8.13B$33.4B14.2AB3.6BD20B.9B8.13B
77.4B14.2AB3.6BC20B.9B8.13B196.4B12.A2.A4.36B8.14B10.2A65.4B12.A2.A4.
36B8.14B10.2A$34.4B12.A2.A4.36B8.14B10.2A65.4B12.A2.A4.36B8.14B10.2A
184.4B10.A.2A5.6B3.B2.2B2.20B4.B3.15B9.A67.4B10.A.2A5.6B3.B2.2B2.20B
4.B3.15B9.A$35.4B10.A.2A5.6B3.B2.2B2.20B4.B3.15B9.A67.4B10.A.2A5.6B3.
B2.2B2.20B4.B3.15B9.A186.4B9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.
3D2.2D45.4B9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.2D$36.4B9.A
7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.2D45.4B9.A7.6B14.19B.B2A4.
8B2.4B5.BA.A7.2D2.D2.D.3D2.2D164.4B7.2A6.9B14.19B2A4.6B5.7B.B2A7.D2.D
.D2.D2.D5.D45.4B7.2A6.9B14.19B2A4.6B5.7B.B2A7.D2.D.D2.D2.D5.D$37.4B7.
2A6.9B14.19B2A4.6B5.7B.B2A7.D2.D.D2.D2.D5.D45.4B7.2A6.9B14.19B2A4.6B
5.7B.B2A7.D2.D.D2.D2.D5.D164.4B13.4B4.2A15.17B.B4.9B4.8B9.D2.D.D2.D2.
D3.2D47.4B13.4B4.2A15.17B.B4.9B4.8B9.D2.D.D2.D2.D3.2D$38.4B13.4B4.2A
15.17B.B4.9B4.8B9.D2.D.D2.D2.D3.2D47.4B13.4B4.2A15.17B.B4.9B4.8B9.D2.
D.D2.D2.D3.2D166.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D5.D47.4B
11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D5.D$39.4B11.4B5.A15.17B6.4B4.
2A5.7B9.D2.D.D2.D2.D5.D47.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D
5.D166.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D49.4B9.4B7.3A12.17B
5.4B5.A6.9B8.2D3.2D3.D3.2D$40.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D
3.2D49.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D168.4B7.4B10.A10.2AB
.15B4.4B7.3A3.9B2.2A.A68.4B7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A$41.4B
7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A68.4B7.4B10.A10.2AB.15B4.4B7.3A3.
9B2.2A.A187.4B5.4B21.A.AB4.12B3.4B10.A3.11BA.2A69.4B5.4B21.A.AB4.12B
3.4B10.A3.11BA.2A$42.4B5.4B21.A.AB4.12B3.4B10.A3.11BA.2A69.4B5.4B21.A
.AB4.12B3.4B10.A3.11BA.2A188.4B3.4B22.A9.11B.4B16.9B8.2A65.4B3.4B22.A
9.11B.4B16.9B8.2A$43.4B3.4B22.A9.11B.4B16.9B8.2A65.4B3.4B22.A9.11B.4B
16.9B8.2A184.4B.4B22.2A8.16B17.8B9.A67.4B.4B22.2A8.16B17.8B9.A$44.4B.
4B22.2A8.16B17.8B9.A67.4B.4B22.2A8.16B17.8B9.A186.7B33.15B12.A.2A2.9B
5.BA.A68.7B33.15B12.A.2A2.9B5.BA.A$45.7B33.15B12.A.2A2.9B5.BA.A68.7B
33.15B12.A.2A2.9B5.BA.A187.5B35.13B13.2A.A15B.B2A70.5B35.13B13.2A.A
15B.B2A$46.5B35.13B13.2A.A15B.B2A70.5B35.13B13.2A.A15B.B2A188.5B16.2A
18.11B19.16B72.5B16.2A18.11B19.16B$46.5B16.2A18.11B19.16B72.5B16.2A
18.11B19.16B189.7B14.B2AB17.10B20.10BEBE3B71.7B14.B2AB17.10B20.10BDBD
3B$45.7B14.B2AB17.10B20.10BDBD3B71.7B14.B2AB17.10B20.10BEBE3B188.4B.
4B14.2B6.B11.9B21.11B2E2B16.A54.4B.4B14.2B6.B11.9B21.11B2D2B16.A$44.
4B.4B14.2B6.B11.9B21.11B2D2B16.A54.4B.4B14.2B6.B11.9B21.11B2E2B16.A
172.3B3.4B14.2B4.3B11.7B23.10BE4B13.3A54.3B3.4B14.2B4.3B11.7B23.10BD
4B13.3A$44.3B3.4B14.2B4.3B11.7B23.10BD4B13.3A54.3B3.4B14.2B4.3B11.7B
23.10BE4B13.3A172.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B24.17B
10.A$44.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B24.17B10.A175.B
7.4B11.14B7.5B25.20B2.2B3.2A56.B7.4B11.14B7.5B25.20B2.2B3.2A$44.B7.4B
11.14B7.5B25.20B2.2B3.2A56.B7.4B11.14B7.5B25.20B2.2B3.2A183.4B.B5.17B
6.5B27.28B65.4B.B5.17B6.5B27.28B$53.4B.B5.17B6.5B27.15B.12B65.4B.B5.
17B6.5B27.15B.12B184.28B4.5B29.7B.17B6.2A60.28B4.5B29.7B.17B6.2A$54.
28B4.5B29.7B.4B.B.10B6.2A60.28B4.5B29.7B.4B.B.10B6.2A178.30B.5B24.2A
4.7B.19B5.A60.30B.5B24.2A4.7B.19B5.A$54.30B.5B24.2A4.7B.4B3.12B5.A60.
30B.5B24.2A4.7B.4B3.12B5.A178.35B26.A4.6B2.19B2.3A61.35B26.A4.6B2.19B
2.3A$54.35B26.A4.6B2.4B.14B2.3A61.35B26.A4.6B2.4B.14B2.3A179.34B27.A.
AB2.4B4.20BA63.34B27.A.AB2.4B4.20BA$54.34B27.A.AB2.4B4.20BA63.34B27.A
.AB2.4B4.20BA182.33B28.2AB2.B.2B.A9.12B66.33B28.2AB2.B.2B.A9.12B$55.
33B28.2AB2.B.2B.A9.12B66.33B28.2AB2.B.2B.A9.12B182.2AB2.31B29.3B.AB.A
.A8.11B65.2AB2.31B29.3B.AB.A.A8.11B$53.2AB2.31B29.3B.AB.A.A8.11B65.2A
B2.31B29.3B.AB.A.A8.11B182.A.AB4.B.16B2.4B.4B30.B3A3.A9.10B65.A.AB4.B
.16B2.4B.4B30.B3A3.A9.10B$52.A.AB4.B.16B2.4B.4B30.B3A3.A9.10B65.A.AB
4.B.16B2.4B.4B30.B3A3.A9.10B183.A11.10B.2B3.3B3.4B29.A15.11B.B.2A3.2A
55.A11.10B.2B3.3B3.3B30.A15.11B.B.2A3.2A$52.A11.10B.2B3.3B3.4B29.A15.
11B.B.2A3.2A55.A11.10B.2B3.3B3.3B30.A15.11B.B.2A3.2A172.2A12.9B4.4B5.
3B27.3AB4A10.14BA.A.A.A54.2A12.9B4.4B5.B29.3AB4A10.14BA.A.A.A$51.2A
12.9B4.4B5.3B27.3AB4A10.14BA.A.A.A54.2A12.9B4.4B5.B29.3AB4A10.14BA.A.
A.A183.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A67.11B5.2A9.B2A24.A4.A2.A10.
13B.B.A.A$62.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A67.11B5.2A9.B2A24.A4.A
2.A10.13B.B.A.A184.12B6.A9.BA.A24.3A13.2AB.13B2A.2A65.12B6.A9.BA.A24.
3A13.2AB.13B2A.2A$61.12B6.A9.BA.A24.3A13.2AB.13B2A.2A65.12B6.A9.BA.A
24.3A13.2AB.13B2A.2A183.12B3.3A13.A26.2A11.A.AB4.9B.B69.12B3.3A13.A
26.2A11.A.AB4.9B.B$61.12B3.3A13.A26.2A11.A.AB4.9B.B69.12B3.3A13.A26.
2A11.A.AB4.9B.B176.2A.2A2.2A2.11B4.A15.2A38.A7.9B60.2A.2A2.2A2.11B4.A
15.2A38.A7.9B$50.2A.2A2.2A2.11B4.A15.2A38.A7.9B60.2A.2A2.2A2.11B4.A
15.2A38.A7.9B177.A.A.A2.A.A2.8B.4B57.2A7.9B59.A.A.A2.A.A2.8B.4B57.2A
7.9B$49.A.A.A2.A.A2.8B.4B57.2A7.9B59.A.A.A2.A.A2.8B.4B57.2A7.9B177.A.
A2.2A.B3.7B4.2A66.10B58.A.A2.2A.B3.7B4.2A66.10B$49.A.A2.2A.B3.7B4.2A
66.10B58.A.A2.2A.B3.7B4.2A66.10B177.A.A.A2.2B2.7B4.A66.12B58.A.A.A2.
2B2.7B4.A66.12B$50.A.A.A2.2B2.7B4.A66.12B58.A.A.A2.2B2.7B4.A66.12B
177.A2.A.BA2B.6B6.3A63.13B58.A2.A.BA2B.6B6.3A63.13B$51.A2.A.BA2B.6B6.
3A63.13B58.A2.A.BA2B.6B6.3A63.13B177.3A.A.A8B8.A63.14B58.3A.A.A8B8.A
63.14B$52.3A.A.A8B8.A63.14B58.3A.A.A8B8.A63.14B179.A.A.8B73.14B60.A.A
.8B73.14B$55.A.A.8B73.14B60.A.A.8B73.14B175.2A2.A4.5B72.4B.12B56.2A2.
A4.5B72.4B.12B$52.2A2.A4.5B72.4B.4B3.5B56.2A2.A4.5B72.4B.4B3.5B172.3A
.2A4.6B72.2A4.7B.4B53.3A.2A4.6B72.2A4.7B.4B$50.3A.2A4.6B72.2A4.4B.2B.
4B53.3A.2A4.6B72.2A4.4B.2B.4B170.A4.B6.6B72.A4.7B2.4B51.A4.B6.6B72.A
4.7B2.4B$49.A4.B6.6B72.A4.2B3.2B2.4B51.A4.B6.6B72.A4.2B3.2B2.4B170.3A
B2AB3.7B69.3A6.6B3.4B51.3AB2AB3.7B69.3A6.6B3.4B$50.3AB2AB3.7B69.3A6.
6B3.4B51.3AB2AB3.7B69.3A6.6B3.4B171.A.2AB.8B70.A8.7B3.4B52.A.2AB.8B
70.A8.7B3.4B$52.A.2AB.8B70.A8.7B3.4B52.A.2AB.8B70.A8.7B3.4B174.10B79.
8B3.4B55.10B79.8B3.4B$56.10B79.8B3.4B55.10B79.8B3.4B173.6B2A3B79.8B3.
4B54.6B2A3B79.8B3.4B$56.6B2A3B79.8B3.4B54.6B2A3B79.8B3.4B172.6B2A2B5.
2A73.8B4.4B53.6B2A2B5.2A73.8B4.4B$56.6B2A2B5.2A73.8B4.4B53.6B2A2B5.2A
73.8B4.4B171.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B52.10B5.A4.3D.D2.D2.2D
57.6B2.B2A3.4B$56.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B52.10B5.A4.3D.D2.D
2.2D57.6B2.B2A3.4B169.11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B50.11B2.BA.A
5.D2.2D.D4.D56.7B.BA.A3.4B$55.11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B50.
11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B168.8B2C2B.B2A6.D2.D.2D3.D41.2A15.
6B4.A4.4B49.8B2C2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B$55.8B2C2B.B2A6.D
2.D.2D3.D41.2A15.6B4.A4.4B49.8B2C2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B
166.8B2C5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B48.8B2C5B8.D2.D.2D2.D43.A8.B
4.8B4.2A4.3B$54.8B2C5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B48.8B2C5B8.D2.D.
2D2.D43.A8.B4.8B4.2A4.3B165.11BC4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.
2B47.11BC4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.2B$53.11BC4B7.3D.D2.D2.
3D41.A.AB3.4B.6B2A2B11.2B47.11BC4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.
2B162.2B.16B62.2AB.13B2A3B11.B44.2B.16B62.2AB.13B2A3B11.B$50.2B.16B
62.2AB.13B2A3B11.B44.2B.16B62.2AB.13B2A3B11.B161.2A18B64.18B17.2A38.
2A18B64.18B$49.2A18B64.18B57.2A18B64.18B17.2A156.2AB.17B63.17B17.A2.A
37.2AB.17B63.17B$49.2AB.17B63.17B58.2AB.17B63.17B17.A2.A156.B.4B.8B2.
4B63.13B20.A.A39.B.4B.8B2.4B63.13B$50.B.4B.8B2.4B63.13B62.B.4B.8B2.4B
63.13B20.A.A164.7B4.4B64.12B20.A47.7B4.4B64.12B$57.7B4.4B64.12B68.7B
4.4B64.12B20.A166.6B5.4B65.10B69.6B5.4B65.10B$58.6B5.4B65.10B69.6B5.
4B65.10B189.4B6.4B64.11B70.4B6.4B64.11B$60.4B6.4B64.11B70.4B6.4B64.
11B190.3BA5.4B64.2B.7B72.3BA5.4B64.2B.7B$62.3BA5.4B64.2B.7B72.3BA5.4B
64.2B.7B191.BA.A5.4B63.11B72.BA.A5.4B63.11B$63.BA.A5.4B63.11B72.BA.A
5.4B63.11B191.A.A6.4B61.11B74.A.A6.4B61.11B$64.A.A6.4B61.11B74.A.A6.
4B61.11B193.A8.4B60.11B75.A8.4B60.11B$65.A8.4B60.11B75.A8.4B60.11B
194.3A6.4B59.11B76.3A6.4B59.11B$66.3A6.4B59.11B76.3A6.4B59.11B196.A7.
3B47.2A.2A2.2A3.8B2.B2A76.A7.3B47.2A.2A2.2A3.8B2.B2A$68.A7.3B47.2A.2A
2.2A3.B3.4B2.B2A76.A7.3B47.2A.2A2.2A3.B3.4B2.B2A203.2B48.A.A2.A.A3.7B
3.BA.A84.2B48.A.A2.A.A3.7B3.BA.A$77.2B48.A.A2.A.A3.2B.4B3.BA.A84.2B
48.A.A2.A.A3.2B.4B3.BA.A203.B48.A2.2A.B4.7B6.A85.B48.A2.2A.B4.7B6.A$
78.B48.A2.2A.B4.2B3.2B6.A85.B48.A2.2A.B4.2B3.2B6.A253.A.A2.2B3.6B7.2A
134.A.A2.2B3.6B7.2A$128.A.A2.2B3.6B7.2A134.A.A2.2B3.6B7.2A251.2A.A.BA
2B.7B142.2A.A.BA2B.7B$127.2A.A.BA2B.7B142.2A.A.BA2B.7B263.A.A.A9B145.
A.A.A9B$130.A.A.A9B145.A.A.A9B260.4A2.A.8B143.4A2.A.8B$127.4A2.A.8B
143.4A2.A.8B261.A3.2A4.6B143.A3.2A4.6B$127.A3.2A4.6B143.A3.2A4.6B263.
A.B6.6B144.A.B6.6B$129.A.B6.6B144.A.B6.6B261.2AB2AB3.7B143.2AB2AB3.7B
$128.2AB2AB3.7B143.2AB2AB3.7B264.2AB.8B147.2AB.8B$131.2AB.8B147.2AB.
8B262.2A3.10B144.2A3.10B$128.2A3.10B144.2A3.10B262.A4.6B2A3B143.A4.6B
2A3B$128.A4.6B2A3B143.A4.6B2A3B262.A3.6B2A2B5.2A138.A3.6B2A2B5.2A$
129.A3.6B2A2B5.2A138.A3.6B2A2B5.2A255.2A3.10B5.A138.2A3.10B5.A$128.2A
3.10B5.A138.2A3.10B5.A260.11B2.BA.A142.11B2.BA.A$132.11B2.BA.A142.11B
2.BA.A260.12B.B2A143.12B.B2A$132.12B.B2A143.12B.B2A260.15B144.15B$
131.15B144.15B261.16B6.3D.D2.D2.2D125.16B6.3D.D2.D2.2D$130.16B6.3D.D
2.D2.2D125.16B6.3D.D2.D2.2D240.2B.16B7.D2.2D.D4.D121.2B.16B7.D2.2D.D
4.D$127.2B.16B7.D2.2D.D4.D121.2B.16B7.D2.2D.D4.D238.2A16B2C7.D2.D.2D
2.2D121.2A16B2C7.D2.D.2D2.2D$126.2A16B2D7.D2.D.2D2.2D121.2A16B2D7.D2.
D.2D2.2D239.2AB.14BCBC6.D2.D.2D4.D120.2AB.14BCBC6.D2.D.2D4.D$126.2AB.
14BDBD6.D2.D.2D4.D120.2AB.14BDBD6.D2.D.2D4.D239.B.4B.8B2.C3B4.3D.D2.D
2.2D122.B.4B.8B2.C3B4.3D.D2.D2.2D$127.B.4B.8B2.D3B4.3D.D2.D2.2D122.B.
4B.8B2.D3B4.3D.D2.D2.2D247.7B4.4B144.7B4.4B$134.7B4.4B144.7B4.4B263.
6B5.4B144.6B5.4B$135.6B5.4B144.6B5.4B264.4B6.4B145.4B6.4B$137.4B6.4B
145.4B6.4B265.3BA5.4B146.3BA5.4B$139.3BA5.4B146.3BA5.4B265.BA.A5.4B
146.BA.A5.4B$140.BA.A5.4B146.BA.A5.4B265.A.A6.4B146.A.A6.4B$141.A.A6.
4B146.A.A6.4B265.A8.3B147.A8.3B$142.A8.3B147.A8.3B266.3A6.2B148.3A6.
2B$143.3A6.2B148.3A6.2B268.A7.B150.A7.B$145.A7.B150.A7.B!
-- Now, I'm not claiming to be an expert in reversible quantum-computation-compatible logic gates. So If this still isn't right for some reason, just let me know. No need to spare my feelings.

I'd be very interested to see how much smaller this can be made, especially with inspired use of oscillators -- either good old standard p30 or p46 technology, or any other periodic trick that can efficiently split signals and do the AND and XOR operations needed by this gate. Let's stick with glider inputs and outputs, though, so the bounding-box comparison is vaguely fair.

On the QFT discussion page I added the note:
dvgrn wrote:If we wanted to make Toffoli gates that are really easy to wire together, then we might be better off encoding '0' and '1' as pairs of gliders following each other with two different spacings, or something like that -- so that you don't need a clock mechanism to tell you whether and when a '0' output has emerged. Then maybe build something that waits for all three signals to come in before emitting the three output signals.
Seems like that would need a significantly bigger circuit mechanism, but it might be much nicer to use -- not as much fiddling around with timing adjustment circuits to bring the inputs in to each gate at just the right time.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Challenge: Minimal Toffoli gate

Post by Macbi » February 18th, 2018, 4:16 pm

As an expert in quantum-computation-compatible logic gates, this is correct.

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Challenge: Minimal Toffoli gate

Post by Kazyan » February 18th, 2018, 9:06 pm

This is hardly sporting, but I think this is a 83x118(?) answer using p46 technology:

Code: Select all

x = 152, y = 122, rule = LifeHistory
25.4B76.A9.A4.4B$26.4B75.3A5.3A3.4B$27.4B77.A3.A5.4B3.3D5.2D2.D2.D.3D
$28.4B75.2A.B.2A3.4B6.D4.D2.D.D2.D2.D$29.4B69.A4.7B2.4B5.3D4.D2.D.D2.
D2.D$30.4B68.3A4.3B3.4B8.D4.D2.D.D2.D2.D$31.4B70.A2.10B7.3D5.2D3.2D3.
D$32.4B68.2A2.9B$33.4B67.3B.9B$34.4B68.11B$35.4B66.12B$36.4B65.10B.B
2A$37.4B65.8B2.BA.A$38.4B63.8B6.A$39.4B63.8B5.2A$40.4B61.9B$41.4B59.
11B$42.4B57.12B$43.4B55.13B$44.4B53.13B$45.4B51.11B.4B$46.4B8.D6.2D2.
D2.D.3D22.11B4.2A$47.4B6.2D5.D2.D.D2.D2.D22.12B4.A$48.4B6.D5.D2.D.D2.
D2.D21.4B2.6B6.3A$49.4B5.D5.D2.D.D2.D2.D20.4B2.7B8.A$50.4B3.3D5.2D3.
2D3.D19.4B2.8B$51.4B39.4B2.8B$52.4B37.4B2.9B$53.4B35.4B2.4B.6B$54.4B
33.4B2.4B.7B$55.4B31.4B2.4B2.6B$56.4B29.4B2.4B3.6B$57.4B27.4B2.4B4.6B
$58.4B25.4B2.4B4.8B$59.4B23.4B2.4B6.8B$60.4B21.4B2.4B6.9B$61.4B19.4B
4.2B3.B3.9B29.B$62.4B17.4B5.3B.B2A2.10B27.2B$63.4B15.4B7.A3B2A2.5B2A
3B26.3B$64.4B13.4B7.A.A3B3.5B2A4B24.4B$65.4B11.4B7.A.AB6.11B23.4B$66.
4B9.4B8.A9.12BA20.4B$67.4B7.4B8.2A11.8B2.3A17.4B$68.4B5.4B22.7B6.A15.
4B$69.4B3.4B23.6B6.2A14.4B$70.4B.4B24.6B21.4B$71.7B25.7B19.4B$72.5B
14.2A8.8B19.4B$72.5B14.A.A7.8B18.4B$71.7B4.2A9.A5.10B.BA14.4B$70.4B.
4B4.A9.2AB2.12BA.A12.4B3.3D5.2D2.D2.D.3D$69.4B3.4B3.A.AB8.AB.12B.2A
11.4B6.D4.D2.D.D2.D2.D$68.4B5.4B3.A.AB.B3.3A12B15.4B5.3D4.D2.D.D2.D2.
D$67.4B7.4B3.A3B2A.A2.13B14.4B6.D6.D2.D.D2.D2.D$66.4B9.4B.3B.B2A.2A2.
13B12.4B7.3D5.2D3.2D3.D$65.4B11.6B3.B7.11B12.4B$64.4B13.6B10.10B12.4B
$63.4B15.6B11.7B12.4B$62.4B17.6B10.7B11.4B$61.4B19.6B9.11B6.4B$60.4B
21.6B6.14B4.4B$59.4B23.6B5.14B3.4B$58.4B25.6B4.15B.4B4.A$57.4B27.6B3.
14B.4B3.3A$56.4B29.6B2.20B.A$55.4B31.6B.20BA.A$54.4B33.24B.2BAB$53.4B
35.22B3.2B$52.4B37.21B2.2B$51.4B37.22B.B2AB$50.4B39.21B2.2A$49.4B42.
19B$48.4B44.18B$47.4B39.2A5.17B2A$46.4B39.B2AB3.18BA.A$45.4B41.2B3.
17B4.A$44.4B10.2A29.2B3.14B2.B5.2A$43.4B11.2AB27.BA2B.4B.10B$42.4B11.
B.2B2.B.9B.B3.4B5.A.A5B.12B$41.4B12.6BA3B2A9B.4B6.A.4B.6B2.6B6.B20.2A
$40.4B13.2A2B2ABAB3A13B2A2.3A4.B.6B4.6B4.5B16.B2A$39.4B14.2A2BA4B3A
13B2A2.A7.6B6.6B2.8B.9B.B2.4B$38.4B16.3BA3BA15B.B10.6B8.20B3A10B$37.
4B17.4B3A16B11.6B10.18BA4BA6B2A$36.4B51.6B12.16BA5BA6B2A$35.4B19.4B3A
16B9.6B14.16BA12B$34.4B20.3BA3BA15B.B6.6B16.16B2A10B$33.4B20.2A2BA4B
3A13B2A4.6B18.9B$32.4B21.2A2B2ABAB3A13B2A3.6B12.B7.14B2A10B$31.4B22.
6BA3B2A9B.4B3.2B3A2B11.3B7.12BA12B$30.4B23.4B2.B.9B.B3.4B2.3B3A3B10.
3B8.10BA5BA6B2A$29.4B25.2AB22.4BA4B2AB7.7B2.2A2.11BA4BA6B2A$28.4B26.
2A22.5B6A3B6.7B.B2A2B.11B3A10B$27.4B50.7BA2BA3B7.7B2.4B2.5B.9B.B2.2B.
B$26.4B51.7B4A3B8.5B.6B4.4B13.B2A$25.4B51.2E6BA2BA3B7.13B5.4B13.2A$
24.4B31.3D4.D.D2.D8.B2E5BA3B2A9.5B.4B8.4B$23.4B34.D4.D.2D.D8.E6B.BABA
2B8.12B8.4B$22.4B33.3D4.D.D.2D10.5B.5B9.12B9.4B$21.4B34.D6.D.D.2D9.6B
.6B8.13B9.4B$20.4B35.3D4.D.D2.D9.6B.6B9.5B.5B11.4B$19.4B58.6B.6B8.6B.
6B11.2B2E$18.4B59.6B.6B8.3BA2B.2BA3B12.2E2B6.D5.D.D2.D$17.4B60.6B.6B
8.2B3AB.B3A2B13.BE2B4.2D5.D.2D.D$16.4B61.6B.6B8.B2A2BA.A2B2AB14.3B5.D
5.D.D.2D$15.4B62.B2A3B.3B2AB8.AB4A.4ABA15.2B5.D5.D.D.2D$14.4B63.BAB2A
B.B2ABAB8.2B3AB.B3A2B21.3D4.D.D2.D$13.4B64.BA3BA.A3BAB8.B3A2B.2B3AB$
12.4B66.2A2BA.A2B2A9.6B.6B$11.4B66.2B3AB.B3A2B8.6B.6B$10.4B68.2BA2B.
2BA2B10.5B.5B$9.4B69.5B.5B9.6B.6B$8.4B68.7B.7B8.5B.5B$7.4B3.3D4.D.D2.
D52.2A6B.6B2A7.5B.5B$6.4B6.D4.D.2D.D52.2A2B2A2B.2B2A2B2A5.7B.7B$5.4B
5.3D4.D.D.2D54.2B2A5.2A2B6.2A6B.6B2A$4.4B8.D4.D.D.2D73.2A2B2A2B.2B2A
2B2A$3.4B7.3D4.D.D2.D75.2B2A5.2A2B$2.4B$.E3B$B2EB$EBE!
A stable circuitry version would replace the two heisenburps with G-to-2Gs.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

Post by calcyman » February 18th, 2018, 10:43 pm

Kazyan wrote:This is hardly sporting, but [...]
42-by-42, and completely inline, using only stable circuitry:

Code: Select all

x = 282, y = 287, rule = B3/S23
obo$b2o$bo67$263b2o$263b2o7$271b2o$271b2o6$270b2o$258b2o9bobo$244b2o
11bo2bo7b2obo4b3o$243bobo12b2o9b2o$245bo24bo4$275b2o$266b2o6bo$265bo2b
o6b2o$266b2o3$275bo$271b2ob2o$274bo2bo$272bo6bo$272bo2bo3bo$261b3o9b4o
2b3o$253bo6bo2b2o8bo2bo2b2o$252b3o5bo2bob2o8bo3bo$251bo11bobob2o5bob3o
$250b2o11bobo2bo6b3o$249b3o11bo4bo7bo$236b2obo23bo3bo$236b4o6b2o5bo10b
3o$235bo3bo6b2o$236b3o$236b3o$238bo9$244b3o$226bo17b4o$224b2ob2o14bo3b
2o$224b2ob2o19bo2b3o$225bob3o13b2ob2o3bobo$224b3o17b4o3b3o$245bo3$202b
o37bobo$201bo36b2o2b2o$201b3o34b2o3b2o$225b2o11b2o2b2o$225b2o12b2ob2o$
240b2o$223bo$222b2o$221b3o17b3o$220bo20bobo$219b2o4bo15b3o$220bo3$201b
o$200bobo$200bobo$201bo17b2o$218bo$218bo$184b2o32b7o$184b2o33bo5bo$
209bo10b3o2bo$208bobo9bo4bo$208bobo10bo2bo$201bo7bo11b3o$200b3o$199bo
2b2o$192b2o5b3o12bo$192b2o20bob2o$218b2o$208bo5b2o2bo2bo$207bobo3b2o2b
2obobo$201bo5bobo8b2ob3o$201bo13bo5b2o$201bo19bo$216b5o$218b2o$218bo
22$148b2o$148b2o2$209b2o9b2o$210bo9bobo$210bobo8b2o4bo$211b2o13bobo$
227bo$156b2o$156b2o5$234bo$232b3o$143b2o13bo72bo$142bo2bo10b2ob3o68bob
o$143b2o13b3ob2o67bo$127b2o30bo$126bobo$128bo31bo68b2o$160bo68b2o$160b
o$151b2o7bobo$150bo2bo7bo$151b2o$203b2o$202bobo$159bo39bo2bo$158b2o39b
4o$158bo$159bobo37b2o$159bo2bo36b2o$160bobo$146b3o11bobo$161bo36bo$
140bo5bo3bo46bobo$139b2o6b4o47bo$105b2o31b2o10bo44b3o$126bo3b2o4bobo
56bo$124b2obob3o4bobo$124bo4b3o62bo$124bo3bo64bobo$125b3o66bo$127bo9$
134bo$106b3o21bo3b2o$106bo2bo19bobob2obo$85bo19bo3bo22bo4bo$84bo21bo2b
2o17b3obo3bo2bo$84b3o21bo14bo$106b2o13bobo13bobo$105b3o12bo2bo14bo$
105b3o13bo$122b2o$121bo$119b3o$120bo$105b2o14bobo$122bo2bo$104b3o19bo$
103b2o18bobo$102b2o2$82bo$81bobo$81bobo$82bo$100bobo$100bo2bo$65b2o33b
o2bo$65b2o36bo$90bo11b3o$89bobo$89bobo$90bo3$73b2o7bo$73b2o7bo$81bobo
11b2o$82b3o9b2ob2o$82b2o2b4o9b2o$82bo7bo6bo3bo$83bo5bo8b3o$83bo!
You could make a glider-only variant by replacing the tubs with p1 Heisenburps.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Kazyan
Posts: 1247
Joined: February 6th, 2014, 11:02 pm

Re: Challenge: Minimal Toffoli gate

Post by Kazyan » February 18th, 2018, 11:17 pm

calcyman wrote:42-by-42, and completely inline, using only stable circuitry:

Code: Select all

x = 282, y = 287, rule = B3/S23
obo$b2o$bo67$263b2o$263b2o7$271b2o$271b2o6$270b2o$258b2o9bobo$244b2o
11bo2bo7b2obo4b3o$243bobo12b2o9b2o$245bo24bo4$275b2o$266b2o6bo$265bo2b
o6b2o$266b2o3$275bo$271b2ob2o$274bo2bo$272bo6bo$272bo2bo3bo$261b3o9b4o
2b3o$253bo6bo2b2o8bo2bo2b2o$252b3o5bo2bob2o8bo3bo$251bo11bobob2o5bob3o
$250b2o11bobo2bo6b3o$249b3o11bo4bo7bo$236b2obo23bo3bo$236b4o6b2o5bo10b
3o$235bo3bo6b2o$236b3o$236b3o$238bo9$244b3o$226bo17b4o$224b2ob2o14bo3b
2o$224b2ob2o19bo2b3o$225bob3o13b2ob2o3bobo$224b3o17b4o3b3o$245bo3$202b
o37bobo$201bo36b2o2b2o$201b3o34b2o3b2o$225b2o11b2o2b2o$225b2o12b2ob2o$
240b2o$223bo$222b2o$221b3o17b3o$220bo20bobo$219b2o4bo15b3o$220bo3$201b
o$200bobo$200bobo$201bo17b2o$218bo$218bo$184b2o32b7o$184b2o33bo5bo$
209bo10b3o2bo$208bobo9bo4bo$208bobo10bo2bo$201bo7bo11b3o$200b3o$199bo
2b2o$192b2o5b3o12bo$192b2o20bob2o$218b2o$208bo5b2o2bo2bo$207bobo3b2o2b
2obobo$201bo5bobo8b2ob3o$201bo13bo5b2o$201bo19bo$216b5o$218b2o$218bo
22$148b2o$148b2o2$209b2o9b2o$210bo9bobo$210bobo8b2o4bo$211b2o13bobo$
227bo$156b2o$156b2o5$234bo$232b3o$143b2o13bo72bo$142bo2bo10b2ob3o68bob
o$143b2o13b3ob2o67bo$127b2o30bo$126bobo$128bo31bo68b2o$160bo68b2o$160b
o$151b2o7bobo$150bo2bo7bo$151b2o$203b2o$202bobo$159bo39bo2bo$158b2o39b
4o$158bo$159bobo37b2o$159bo2bo36b2o$160bobo$146b3o11bobo$161bo36bo$
140bo5bo3bo46bobo$139b2o6b4o47bo$105b2o31b2o10bo44b3o$126bo3b2o4bobo
56bo$124b2obob3o4bobo$124bo4b3o62bo$124bo3bo64bobo$125b3o66bo$127bo9$
134bo$106b3o21bo3b2o$106bo2bo19bobob2obo$85bo19bo3bo22bo4bo$84bo21bo2b
2o17b3obo3bo2bo$84b3o21bo14bo$106b2o13bobo13bobo$105b3o12bo2bo14bo$
105b3o13bo$122b2o$121bo$119b3o$120bo$105b2o14bobo$122bo2bo$104b3o19bo$
103b2o18bobo$102b2o2$82bo$81bobo$81bobo$82bo$100bobo$100bo2bo$65b2o33b
o2bo$65b2o36bo$90bo11b3o$89bobo$89bobo$90bo3$73b2o7bo$73b2o7bo$81bobo
11b2o$82b3o9b2ob2o$82b2o2b4o9b2o$82bo7bo6bo3bo$83bo5bo8b3o$83bo!
You could make a glider-only variant by replacing the tubs with p1 Heisenburps.
Nice! Some welding gets it down to 40x42:

Code: Select all

x = 279, y = 283, rule = B3/S23
obo$b2o$bo65$261b2o$261b2o7$269b2o$269b2o6$244b2o19b3o3bo$243bobo10b2o
5b5o2bobo$245bo9bo2bo3b2o8bob3o$256b2o5b2o4b3o$264bo3b2o5$264b2o$263bo
2bo$264b2o4$269b2obo$269b2obobo2bo$262bo8bo2bo3bo$260bobo5bobo6bo$249b
o9bo2bo7bo5bo$248b3o9bo17bo$248bo2bo9b2o15bo$246bo4b2o7bo$245bo3bobo6b
3o$246bo2b2o8bo$232bo12b5o10bobo$231bob2o9b2o15bo2bo$230bo4bo8b2o19bo$
231bo30bobo$232b4o8$224bo$223bobo$222bo3bo22b3o$223bo2bo22b3o$223bo2bo
22bo$224bobo14b2ob2o2bo$241bo3b4o3b3o$241bobob2obo$249bo3$239b3o$239bo
$198bo42bo$197bo25b2o14bo$197b3o20bob3o14b3o$219bob2o17b2o$222bo17bo$
217b2o3bo16b3o$216b2o2b3o13b3o3bo$217bo3bo14b2o$218b3o15b2o$219bo20bo$
240bo$240bo$199bo$198bobo$198bobo$199bo20bo$216bo3b2o$215bobob2obo$
182b2o34bo4bo$182b2o15bo14b3obo3bo2bo$198b3o6bo$198bob2o4bobo14bobo$
197b2o7bobo15bo$197b2o8bo$197b2o$201bo13bo$190b2o8b2o10b2o$190b2o6bobo
11b2ob2o$197bo2bo13bo$198b2o12b2o2$199bo13b2o$199bo$199bo16bo$213bobo$
214bo2b2o21$148b2o$148b2o4$207b2o9b2o$208bo9bobo$208bobo8b2o4bo$156b2o
51b2o13bobo$156b2o67bo7$143b2o13bo73bo$142bo2bo10b2ob3o68b3o$143b2o13b
3ob2o65bo$127b2o30bo68bobo$126bobo100bo$128bo31bo$160bo$160bo66b2o$
151b2o7bobo64b2o$150bo2bo7bo$151b2o$198b2o$199bo$159bo39bob2o$158b2o
34bo2b2obobo$158bo35b4o2bo$159bobo30b2o5b2o$159bo2bo28bo2bo2b2o$160bob
o28b3o2bobo$146b3o11bobo31b2o$161bo29b2obo$140bo5bo3bo41bobo2bo$139b2o
6b4o41bobobobo$105b2o31b2o10bo42b2ob2o$126bo3b2o4bobo$124b2obob3o4bobo
$124bo4b3o62bo$124bo3bo64bobo$125b3o66bo$127bo9$134bo$106b3o21bo3b2o$
106bo2bo19bobob2obo$85bo19bo3bo22bo4bo$84bo21bo2b2o17b3obo3bo2bo$84b3o
21bo14bo$106b2o13bobo13bobo$105b3o12bo2bo14bo$105b3o13bo$122b2o$121bo$
119b3o$120bo$105b2o14bobo$122bo2bo$104b3o19bo$103b2o18bobo$102b2o2$82b
o$81bobo$81bobo$82bo$100bobo$100bo2bo$65b2o33bo2bo$65b2o36bo$90bo11b3o
$89bobo$89bobo$90bo3$73b2o7bo$73b2o7bo$81bobo11b2o$82b3o9b2ob2o$82b2o
2b4o9b2o$82bo7bo6bo3bo$83bo5bo8b3o$83bo!
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Challenge: Minimal Toffoli gate

Post by dvgrn » February 19th, 2018, 10:43 am

calcyman wrote:
Kazyan wrote:This is hardly sporting, but [...]
42-by-42, and completely inline, using only stable circuitry...
You could make a glider-only variant by replacing the tubs with p1 Heisenburps.
Why a p1 (pseudo) Heisenburp -- just to keep from affecting the inputs, except when necessary? It's not clear that a pseudo-Heisenburp quite counts in that department. You might say it affects the inputs but then pretends that it didn't.

Also, I'm not sure where that criterion crept in, and I think it will kind of blow up the bounding box compared with using standard splitters...! See, there was a reason I was specific about the signal types:
dvgrn wrote:Let's stick with glider inputs and outputs, though, so the bounding-box comparison is vaguely fair.
I think the p46 solution is very nice, though, and perfectly "sporting" -- just maybe it should be the (current) winner in its own Periodic subcategory.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

Post by calcyman » February 19th, 2018, 12:35 pm

Using Kazyan's amazing glider duplicator, it's possible to build a stable 91-by-95 solution whilst adhering to Dave's glider-only rule:

Code: Select all

x = 91, y = 95, rule = LifeHistory
71.A$71.3A$65.B8.A$63.4B6.A.A$64.4B5.A.AB$65.4B5.A3B$66.4B6.4B$67.4B
5.6B$68.4B4.7B$68.5B2.8B.4B.B$67.20B.B2A$66.4B.18B2A$65.4B2.16B.2B$8.
B55.4B3.16B$8.2B53.4B4.15B$8.3B51.4B3.2AB.12B$8.4B49.4B3.A.AB2.11B$9.
4B47.4B4.A5.10B$10.4B45.4B4.2A5.2B2A6B$11.4B43.4B11.3B2A6B$12.4B24.B
16.4B13.10B$13.4B22.3B14.4B14.8B.B2A.A$14.4B11.2A6.3B2A13.6B3.A8.7B3.
B2AB3A$15.4B11.A6.3BA.AB10.7B3.3A6.6B6.B4.A$16.4B10.A.AB2.4B.2A2B8.9B
5.A6.6B4.2A.3A$17.4B10.2AB2.3B.4B8.9B5.2A6.5B4.A2.2A$18.4B10.11B8.10B
5.5B2.8B.A.A$19.4B10.10B7.12B6.3B2.8BA.A.3A$20.4B9.8B8.4B.9B4.5B.9BAB
.A2.A$21.4B8.7B8.4B4.3B2A4B2.13B.2B2.A.A.A$22.4B6.8B7.4B5.2BA2BA17B3.
B.2A2.A.A$23.4B5.8B6.4B7.2B2A18B2.A.A2.A.A.A$24.4B.11B5.4B9.21B2.2A2.
2A.2A$25.17B2.4B8.23B$26.16B.4B6.A2.2A5.16B$27.20B4.3A3.A7.13B10.A$
28.21B.A3.3A9.11B9.3A$28.21BA.A2.A11.11B8.A$28.19B.2BAB13.14B6.2A$27.
19B3.2B12.24B$26.19B5.B.A9.23B$25.21B3.A.A.A8.24B$25.22B2.2A2.A7.25B$
25.21B7.2A6.26B$20.2A3.19B18.21B.4B$21.A3.18B17.3B.6B2.B7.2B3.4B$21.A
.2A17B18.2A4.4B.3B5.BA2B3.4B$16.A2.2A.A.A18B18.A5.2B2.B2AB4.A.A5.4B$
16.4A2.A4.17B14.3A11.2A6.A7.3B$14.2A5.2A5.17B13.A30.2B$13.A2.A2.2A6.
12B3.4B$13.3A2.A.A5.8B.4B4.4B$16.2A.B5.8B11.4B$13.2A.A2.2B3.8B13.4B$
14.A.A.BA2B.8B15.4B$14.A.A.A.A9B17.4B$15.2A.2A.8B19.4B$23.5B21.4B$23.
6B7.2A12.4B$22.7B7.A14.4B$21.10B2.BA.A15.4B$20.12B.B2A17.4B$19.11BA3B
14.2A4.4B$18.11BABA2B14.A6.4B$17.4B.7BABA2B11.BA.A7.4B$16.4B4.B2.3BA
3B8.2B.B2A9.4B$15.4B9.6B6.6B12.4B$3.B10.4B11.6B4.6B14.4B$2.3B8.4B5.2A
5.6B4.7B14.4B$2.4B6.4B7.A6.6B2.8B15.4B$3.4B4.4B8.A.AB3.17B15.4B$4.4B
2.4B4.A5.2AB.20B15.4B$5.8B3.3A7.22B16.4B$6.6B3.A10.21B18.4B$7.4B4.2A
9.19B21.4B$2A6.9B11.17B.2B19.4B$.A7.6B14.18B2A19.4B$.A.2A5.6B3.B2.2B
2.19B.B2A20.4B$2.A2.A4.35B2.B22.4B$3.2AB3.36B26.4B$4.14B2A25B27.4B$5.
13B2A16B2.7B28.4B$6.29B3.7B29.4B$6.17B.B.4B9.6B.BA27.4B$7.15B4.3B10.
7BA.A27.3B$7.15B5.A2B.2A6.8BA$8.13B5.A.A2B.A6.6B.B$10.13B2.A.AB2.A7.
5B$9.8B4.2A.A.A3.A8.6B$9.6B6.2ABA2.4A.A4.2AB.5B$9.5B8.B2.A.A3.2A3.A.A
B3.4B$9.B.B9.2A.2A.A.A6.A7.4B$10.3B9.A.A3.A.3A2.2A8.4B$9.B2AB9.A.A4.A
2.A13.4B$10.2A11.A6.2A15.4B!
It's annoying that the complexity is mostly in splitting the signals, rather than in performing the actual logic: the 'a ^= (b & c)' gate is only 2 eaters and a ship, and then another 2 eater5s to suppress the extra outputs.

Does anyone have a smaller glider duplicator? I think we need a forum thread collecting stable reflectors.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Challenge: Minimal Toffoli gate

Post by dvgrn » February 19th, 2018, 4:55 pm

calcyman wrote:Using Kazyan's amazing glider duplicator, it's possible to build a stable 91-by-95 solution whilst adhering to Dave's glider-only rule...

It's annoying that the complexity is mostly in splitting the signals, rather than in performing the actual logic: the 'a ^= (b & c)' gate is only 2 eaters and a ship, and then another 2 eater5s to suppress the extra outputs.
Maybe even more annoying, this design is amenable to being made "smaller" by making it taller, thanks to the Magic of Long Skinny Rectangles. Here's the same mechanism inside 54x104:

Code: Select all

x = 155, y = 166, rule = LifeHistory
.C$2.C$3C59$98.2A11.A6.2A17.4B$97.B2AB9.A.A4.A2.A15.4B$98.3B9.A.A3.A.
3A3.A10.4B$97.B.B9.2A.2A.A.A6.3A7.4B$97.5B8.B2.A.A3.2A6.A5.4B$97.6B6.
2ABA2.4A.A5.2A.7B$97.8B4.2A.A.A3.A7.9B$98.13B2.A.AB2.A8.6B$96.13B5.A.
A2B.A7.5B$95.15B5.A2B.2A6.7B$95.15B4.3B10.6B$94.17B.B.2B10.7B$94.29B
4.6B$93.13B2A16B2.7B$76.D15.14B2A16B2.7B$77.D13.2AB3.27B.9B$75.3DB11.
A2.A4.36B$78.2B9.A.2A5.6B3.B2.2B2.20B4.B$78.3B8.A7.6B14.19B.B2A$78.4B
6.2A6.9B14.19B2A$79.4B12.4B4.2A15.17B.B$80.4B10.4B5.A15.17B$81.4B8.4B
7.3A12.17B$82.4B6.4B10.A10.2AB.15B$83.4B4.4B21.A.AB4.12B$84.4B2.4B22.
A9.11B$85.8B22.2A8.13B$86.6B33.12B$87.4B35.10B$87.5B24.B10.9B$85.2C6B
22.3B9.9B$84.C.C3.4B11.2A6.3B2A9.9B$86.C4.4B11.A6.3BA.AB7.6B$92.4B10.
A.AB2.4B.2A2B6.5B$93.4B10.2AB2.3B.4B7.5B$94.4B10.11B8.4B$95.4B10.10B
7.4B$96.4B9.8B8.4B.B$97.4B8.7B8.4B$98.4B6.8B7.4B$99.4B5.8B6.4B$100.4B
.11B5.4B$101.17B2.4B$102.16B.4B6.A$103.20B4.3A$104.21B.A$104.21BA.A$
104.19B.2BAB$103.19B3.2B$102.19B5.B.A$101.21B3.A.A.A$101.11BD10B2.2A
2.A$101.9B2D10B7.2A$96.2A3.10B2D7B$97.A3.18B$97.A.2A17B$92.A2.2A.A.A
18B$92.4A2.A4.17B$90.2A5.2A5.17B$89.A2.A2.2A6.12B3.4B$89.3A2.A.A5.4BD
3B.4B4.4B30.C$92.2A.B5.5B2DB11.4B28.C$89.2A.A2.2B3.5BDBD13.4B27.3C$
90.A.A.BA2B.8B15.4B$90.A.A.A.A9B17.4B$91.2A.2A.8B19.4B$99.5B21.4B$99.
4B23.4B$98.4B25.4B$97.5B26.4B12.B$96.6B27.4B10.2B$95.7B28.4B8.3B$93.
9B29.4B6.4B$93.9B30.4B4.4B$92.10B31.4B2.4B$91.12B31.8B$90.14B31.6B$
89.15B8.2A22.4B$89.14B9.A22.6B$93.12B4.BA.A21.7B$93.15B.B2A10.A10.4B
2.4B$93.17B12.3A7.4B4.4B$93.17B15.A5.4B6.4B$90.B.17B15.2A4.4B4.A3.4B$
89.2A19B14.9B4.A.A3.4B$89.2AB.19B14.6B5.A.A4.4B$90.B4.20B2.2B2.B3.6B
5.2A.2A4.4B$95.36B4.A2.A2.A4.4B$95.9B.27B3.B2A2.2A5.4B$96.7B2.16B2A
14B11.4B$96.7B2.16B2A13B13.4B$96.6B4.29B15.4B$96.7B10.2B.B.17B16.4B$
96.6B10.3B4.15B18.3B$95.7B6.2A.2BA5.15B$96.5B7.A.2BA.A5.13B$95.6B8.A
2.BA.A2.13B$94.9B7.A3.A.A.2A4.8B$93.7B.2A5.A.4A2.AB2A6.6B$92.4B5.A6.
2A3.A.A2.B8.5B$91.4B7.3A6.A.A.2A.2A9.B.B$90.4B10.A3.3A.A3.A.A9.3B$89.
4B15.A2.A4.A.A9.B2AB$89.3B17.2A6.A11.2A$89.2B!
This adds some ugly signal crossings, too, so this gate's repeat rate is a lot lower. Luckily recovery time isn't part of the spec.
calcyman wrote:Does anyone have a smaller glider duplicator? I think we need a forum thread collecting stable reflectors.
Seems to me we kinda sorta have one or two such threads -- the H-to-G thread and the Elementary Conduits thread. It's just that record-setting new discoveries in the stable-reflector department are kind of rare.

What we really need is a direct fast G-to-2G, anyway -- preferably (while I'm wishing for vaporpatterns) a constructible one with a repeat time matching the Snark and semi-Snarks, or at least significantly lower than a syringe. That would mean having to completely re-do all the single-channel searches, and we'd probably end up with significantly shorter construction-arm recipes.

simeks
Posts: 402
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: Challenge: Minimal Toffoli gate

Post by simeks » February 20th, 2018, 1:21 pm

dvgrn wrote:Luckily simeks pointed out a workable piece of an XOR mechanism recently (December)
... Somebody please find something nicer!
For the record, these are the previously known XOR mechanisms that I know of, from here and here (at edit 9)

Code: Select all

x = 296, y = 204, rule = LifeHistory
13.A79.A79.A79.A$12.A.A77.A.A77.A.A77.A.A$12.A.A77.A.A77.A.A77.A.A$
10.3A.2A74.3A.2A74.3A.2A74.3A.2A$9.A79.A79.A79.A$10.3A.2A74.3A.2A74.
3A.2A74.3A.2A$12.A.2A76.A.2A76.A.2A76.A.2A3$7.2A78.2A78.2A78.2A$8.A
79.A79.A79.A$8.A.A77.A.A77.A.A77.A.A$9.2A78.2A78.2A78.2A4$30.2A78.2A
78.2A78.2A$30.2A78.2A78.2A78.2A2$9.D29.3D47.E29.3D47.D29.3E47.E29.3E$
9.D.D27.D49.E.E27.D49.D.D27.E49.E.E27.E$9.3D28.D48.3E28.D48.3D28.E48.
3E28.E$11.D79.E79.D79.E5$2.2A78.2A78.2A78.2A$3.A79.A79.A79.A$3A77.3A
77.3A77.3A$A79.A79.A79.A$20.2A78.2A78.2A78.2A$20.2A78.2A78.2A78.2A45$
22.A79.A79.A79.A$22.3A77.3A77.3A77.3A$25.A79.A79.A79.A$24.2A78.2A78.
2A78.2A7$17.A79.A79.A79.A$17.3A77.3A77.3A77.3A$8.A11.A67.A11.A67.A11.
A67.A11.A$8.3A8.2A14.A52.3A8.2A14.A52.3A8.2A14.A52.3A8.2A14.A$11.A22.
A.A54.A22.A.A54.A22.A.A54.A22.A.A$10.2A23.A54.2A23.A54.2A23.A54.2A23.
A4$32.2A78.2A78.2A78.2A$32.A.A77.A.A77.A.A77.A.A$34.A79.A79.A79.A$9.D
24.2A53.E24.2A53.D24.2A53.E24.2A$9.D.D18.2A57.E.E18.2A57.D.D18.2A57.E
.E18.2A$9.3D18.A58.3E18.A58.3D18.A58.3E18.A$11.D11.2A6.3A57.E11.2A6.
3A57.D11.2A6.3A57.E11.2A6.3A$23.A9.A69.A9.A69.A9.A69.A9.A$24.3A77.3A
77.3A77.3A$26.A79.A79.A79.A2$2.2A78.2A78.2A78.2A$3.A79.A79.A79.A$3A
77.3A77.3A77.3A$A79.A79.A79.A6$2.D79.D79.E79.E$2.2D78.2D78.2E78.2E$.D
.D77.D.D77.E.E77.E.E47$24.2A27.D50.2A27.D50.2A27.E50.2A27.E$24.A28.D.
D48.A28.D.D48.A28.E.E48.A28.E.E$21.A4.A2.2A22.2D46.A4.A2.2A22.2D46.A
4.A2.2A22.2E46.A4.A2.2A22.2E$21.5A.A2.A70.5A.A2.A70.5A.A2.A70.5A.A2.A
$7.2A18.2A.A.2A53.2A18.2A.A.2A53.2A18.2A.A.2A53.2A18.2A.A.2A$8.A10.4A
.3A3.A2.A54.A10.4A.3A3.A2.A54.A10.4A.3A3.A2.A54.A10.4A.3A3.A2.A$8.A.A
8.A2.A.A3.2A.A56.A.A8.A2.A.A3.2A.A56.A.A8.A2.A.A3.2A.A56.A.A8.A2.A.A
3.2A.A$9.2A18.A.2A56.2A18.A.2A56.2A18.A.2A56.2A18.A.2A$29.A79.A79.A
79.A$28.2A78.2A78.2A78.2A5$9.D18.2A59.E18.2A59.D18.2A59.E18.2A$9.D.D
17.A59.E.E17.A59.D.D17.A59.E.E17.A$9.3D17.A.2A56.3E17.A.2A56.3D17.A.
2A56.3E17.A.2A$11.D18.A.A58.E18.A.A58.D18.A.A58.E18.A.A5$2.2A78.2A78.
2A78.2A$3.A79.A79.A79.A$3A77.3A77.3A77.3A$A79.A79.A79.A7$30.2A78.2A
78.2A78.2A$30.A3.2A74.A3.2A74.A3.2A74.A3.2A$28.A.A.A2.A72.A.A.A2.A72.
A.A.A2.A72.A.A.A2.A$26.3A.A.2A72.3A.A.2A72.3A.A.2A72.3A.A.2A$25.A3.A.
A73.A3.A.A73.A3.A.A73.A3.A.A$25.2A2.A.A73.2A2.A.A73.2A2.A.A73.2A2.A.A
$30.A79.A79.A79.A!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

Post by calcyman » February 20th, 2018, 2:20 pm

The H-to-Pi-compatible Pi-to-G exact-timing XOR gate used in my Toffoli gate has been known for just under a decade by Dave Greene and me, in private correspondence. (Its existence as a H-to-G has been known publicly for much longer still.)
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Challenge: Minimal Toffoli gate

Post by dvgrn » March 3rd, 2018, 6:43 am

simeks wrote:
dvgrn wrote:Luckily simeks pointed out a workable piece of an XOR mechanism recently (December)
... Somebody please find something nicer!
For the record, these are the previously known XOR mechanisms that I know of, from here and here (at edit 9)...
Thanks, I'd forgotten about those. So technically this would count as a smaller Toffoli gate, at 67x36...

Code: Select all

x = 101, y = 59, rule = LifeHistory
22.C$23.2C$22.2C2$99.C$98.C$98.3C17$36.A$35.A.A$35.A.A$33.3A.2A$2.C
29.A$C.C30.3A.2A$.2C.B30.A.2A$3.3B$3.4B$4.4B22.2A$5.4B22.A$6.4B21.A.A
$7.4B10.A10.2A$8.4B7.3A$9.4B5.A$10.4B4.2A$3.2A6.9B33.2A$4.A7.6B35.2A$
4.A.2A5.6B3.B2.2B2.2B$5.A2.A4.19BD$6.2AB3.20BDBD$7.14B2A9B3DB$8.13B2A
11BD31.2A$9.24B33.A$9.17B.B28.2A9.3A$10.15B30.A.A11.A$10.15B5.A3.2A
19.A$11.13B5.A.A3.A18.2A$13.13B2.A.A3.A$12.8B4.2A.A.A3.A$12.6B6.2ABA
2.4A.A$12.5B8.B2.A.A3.2A7.2A$12.B.B9.2A.2A.A.A10.2A$13.3B9.A.A3.A.3A$
12.B2AB9.A.A4.A2.A$13.2A11.A6.2A!
... except that in practice you'd have to add an edge shooter to one of the inputs, or a highway robber to each output, to string multiple gates together in any useful way.

EDIT: ... and as calcyman points out, it doesn't really count unless you have three outputs, so a signal duplicator would have to be added on each of the kickback inputs. Somebody please find a nice small G-to-2G mechanism --

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

Post by calcyman » March 3rd, 2018, 7:31 am

dvgrn wrote:Thanks, I'd forgotten about those. So technically this would count as a smaller Toffoli gate, at 67x36...
A Toffoli gate has 3 outputs: (A, B, C XOR (A AND B)). Your gate seems to only have the last of these outputs, so is trumped by this:

Code: Select all

x = 46, y = 44, rule = LifeHistory
3B$4B$.4B24.B$2.4B22.3B$3.4B11.2A6.3B2A$4.4B11.A6.3BA.AB10.3B$5.4B10.
A.AB2.4B.2A2B8.4B$6.4B10.2AB2.3B.4B8.4B$7.4B10.11B8.4B$8.4B10.10B7.4B
$9.4B9.8B8.4B$10.4B8.7B8.4B$11.4B6.8B7.4B$12.4B5.8B6.4B$13.4B.11B5.4B
$14.17B2.4B$15.16B.4B6.A$16.20B4.3A$17.21B.A$17.21BA.A$17.19B.2BAB$
16.19B3.2B$15.19B5.B.A$14.21B3.A.A.A$14.22B2.2A2.A$14.21B7.2A$9.2A3.
19B$10.A3.18B$10.A.2A17B$5.A2.2A.A.A18B$5.4A2.A4.17B$3.2A5.2A5.17B$2.
A2.A2.2A6.12B3.4B$2.3A2.A.A5.8B.4B4.4B$5.2A.B5.8B11.4B$2.2A.A2.2B3.8B
13.4B$3.A.A.BA2B.8B15.4B$3.A.A.A.A9B17.4B$4.2A.2A.8B19.4B$13.4B21.4B$
12.4B23.4B$11.4B25.4B$10.4B27.4B$9.4B29.4B!
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Re: Challenge: Minimal Toffoli gate

Post by Scorbie » March 3rd, 2018, 11:32 pm

How about using the H-MWSS as the over-unity component?

Code: Select all

x = 33, y = 66, rule = LifeHistory
15.D$14.3D$7.2A4.D2B2D$8.A4.6B$8.A.AB.6B$9.2AB.7B$11.8B$12.7B$12.7B5.
CBC$8.B4.9B.B2CB$7.A2B.B.12BC$6.A.A16B$7.AB.4BD3B2C4B3.3B$10.3B3DBC2B
C3B.6B$10.5BD2B2C9BE2B$B.B.B.B.B.18BEBE$29B2E$5D25B$D4BD22B$D27B$BD3B
D22B$.B.D.B.B.B.B.15B$15.13B$15.13B$15.11B$14.13B$13.15B$12.16B$11.
17B$12.16B$13.13B$13.5B2E2B$15.3B2E2B$15.8B$17.3D$17.BDB$16.3D2B$16.
5B$15.6B7.A$15.6B6.A.A$16.5B6.A.A$16.6B4.2A.3A$15.6B6.B4.A$15.7B3.B2A
B3A$16.8B.B2A.A$16.10B$15.3B2A6B$9.2A5.2B2A6B$10.A5.10B$10.A.AB2.11B$
11.2AB.12B$13.15B$13.16B$13.16B.2B$13.18B2A$12.17B.B2A$11.4B2.8B.4B.B
$10.4B4.7B$9.4B5.6B$8.4B6.4B$7.2C2B5.A3B$6.C.CB5.A.AB$8.C6.A.A$16.A$
13.3A$13.A!
Edit: Whoops, sorry that was stupid.

User avatar
dvgrn
Moderator
Posts: 10611
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Challenge: Minimal Toffoli gate

Post by dvgrn » March 13th, 2018, 7:15 pm

calcyman wrote:A Toffoli gate has 3 outputs: (A, B, C XOR (A AND B)). Your gate seems to only have the last of these outputs...
So it does. It's always embarrassing when I forget the spec for a construction halfway through.

Here's a new record holder, just barely -- 101x56 instead of 105x54, so a whole 14 cells improvement to the bounding box:

Code: Select all

x = 162, y = 141, rule = LifeHistory
2.C$C.C$.2C71$75.D$76.D$74.3DB$77.2B$77.3B$77.4B$78.4B16.C$79.4B15.C.
C$80.4B14.2C$81.4B$82.4B$83.4B$84.4B54.2A16.2B$85.4B52.B2AB14.3B$86.
4B45.B6.2B14.4B$87.4B24.B18.3B4.2B14.4B$80.A7.4B22.3B13.14B12.4B$78.
3A8.4B11.2A6.3B2A13.14B11.4B$77.A12.4B11.A6.3BA.AB11.17B5.B.4B$76.A.A
6.B5.4B10.A.AB2.4B.2A2B9.28B$75.BA.A5.2B6.4B10.2AB2.3B.4B8.30B$74.3BA
5.3B7.4B10.11B8.31B$72.4B6.4B8.4B10.10B7.32B$70.6B5.4B10.4B9.8B8.32B$
69.7B4.4B12.4B8.7B8.30B2.B2A$62.B.4B.8B2.4B14.4B6.8B7.4B7.16B.B4.BA.A
$61.2AB.17B16.4B5.8B6.4B9.2B.10B11.A$61.2A18B18.4B.11B5.4B13.9B12.2A$
62.2B.16B19.17B2.4B15.11B$65.16B20.16B.4B6.A9.12B$66.15B21.20B4.3A9.
12B$67.12B.B2A20.21B.A2.B10.11B2.2A2.2A.2A$67.11B2.BA.A19.21BA.A10.4B
.8B2.A.A2.A.A.A$68.10B5.A19.19B.2BAB10.2A4.7B3.B.2A2.A.A$68.6B2A2B5.
2A17.19B3.2B12.A4.7B2.2B2.A.A.A$68.6B2A3B22.19B5.B.A7.3A6.6B.2BAB.A2.
A$68.10B22.21B3.A.A.A6.A8.8BA.A.3A$64.A.2AB.8B22.11BD10B2.2A2.A15.8B.
A.A$62.3AB2AB3.7B21.9B2D10B7.2A15.5B4.A2.2A$61.A4.B6.6B9.2A5.2A3.10B
2D7B26.6B4.2A.3A$62.3A.2A4.6B10.A2.A4.A3.18B26.6B6.B4.A$64.2A2.A4.5B
11.3A4.A.2A17B27.7B3.B2AB3A$67.A.A.8B4.2A9.2A.A.A18B27.8B.B2A.A$64.3A
.A.A8B4.A.A5.4A2.A4.17B26.10B$63.A2.A.BA2B.6B6.3A2.A5.2A5.17B24.3B2A
6B$62.A.A.A2.2B2.7B4.A3.A2.A2.2A6.12B3.4B17.2A5.2B2A6B$61.A.A2.2A.B3.
7B4.2A2.3A2.A.A5.4BD3B.4B4.4B17.A5.10B$61.A.A.A2.A.A2.8B.4B5.2A.B5.5B
2DB11.4B16.A.AB2.11B$62.2A.2A2.2A2.11B4.2A.A2.2B3.5BDBD13.4B16.2AB.
12B$73.12B4.A.A.BA2B.8B15.4B17.15B$73.12B4.A.A.A.A9B17.4B16.16B$74.
11B5.2A.2A.8B19.4B15.16B.2B$63.2A12.9B12.5B21.4B14.18B2A$64.A11.10B.
2B9.4B23.4B12.17B.B2A$64.A.AB4.B.16B7.4B25.4B10.4B2.8B.4B.B$65.2AB2.
30B27.4B8.4B4.7B$67.32B29.4B6.4B5.6B$66.32B31.4B4.4B6.4B$66.31B.B31.
4B3.3B5.A3B$66.30B35.4B2.2B5.A.AB$66.28B38.4B.B6.A.A$65.4B.B5.17B40.
4B8.A$64.4B11.14B41.4B4.3A$63.4B12.14B42.4B3.A$62.4B14.2B4.3B47.4B$
61.4B14.2B6.B41.3C5.4B$61.3B14.B2AB49.C6.4B$61.2B16.2A49.C8.4B!

Post Reply