Challenge: Minimal Toffoli gate

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Challenge: Minimal Toffoli gate

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.

`x = 312, y = 79, rule = LifeHistory71.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.7B62.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.3A2.14B.4B12.A43.3A2.14B.4B12.A\$7.A20B11.A.A45.A20B11.A.A45.A20B11.A.A45.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.3A54.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.13B10.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.2B3C2B4.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 = LifeHistory112.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\$3D5.D2.D.D2.D2.D4.D79.4B\$D3B4.D2.D.D2.D2.D3.D79.4B\$.D3B4.2D3.2D3.D3.3D76.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.5B14.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.9B2C2B2A16B2.7B6.A.AB3.B2A3B\$26.4B16.9BCBC2B2A16B2.7B7.2AB.10B\$27.4B14.2AB3.6BC20B.9B8.13B\$28.4B12.A2.A4.36B8.14B10.2A\$29.4B10.A.2A5.6B3.B2.2B2.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.2A15.17B.B4.9B4.8B9.D2.D.D2.D2.D3.2D\$33.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.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.11BA.2A\$37.4B3.4B22.A9.11B.4B16.9B8.2A\$38.4B.4B22.2A8.16B17.8B9.A\$39.7B33.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.2B3.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.7B4.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.6B72.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.B4.8B4.2A4.3B\$47.11BC4B7.3D.D2.D2.3D41.A.AB3.4B.6B2A2B11.2B\$44.2B.16B62.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.B48.A2.2A.B4.2B3.2B6.A\$122.A.A2.2B3.6B7.2A\$121.2A.A.BA2B.7B\$124.A.A.A9B\$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.BA.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.C3B4.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 ]]`

dvgrn
Moderator

Posts: 5614
Joined: May 17th, 2009, 11:00 pm

Re: Challenge: Minimal Toffoli gate

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.

`x = 766, y = 347, rule = LifeHistory305.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.D2.D.D2.D2.D4.D5.2B2E251.D2.D.D2.D2.D4.D5.B.2D133.D2.D.D2.D2.D4.D5.2B2E\$118.2D3.2D3.D3.3D3.2BD136.2D3.2D3.D3.3D3.2BEB253.2D3.2D3.D3.3D3.2BD136.2D3.2D3.D3.3D3.2BE\$137.4B155.4B273.4B155.4B\$136.4B155.4B273.4B155.4B\$135.4B155.4B273.4B155.4B\$134.4B155.4B273.4B155.4B\$133.4B155.4B273.4B155.4B\$132.4B155.4B273.4B155.4B\$131.4B155.4B273.4B155.4B\$130.4B155.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.4B155.4B\$124.4B155.4B273.4B155.4B\$123.4B155.4B273.4B155.4B\$122.4B155.4B273.4B155.4B\$121.4B155.4B273.4B155.4B\$120.4B155.4B273.4B155.4B\$119.4B155.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.4B155.4B\$113.4B155.4B273.4B155.4B\$15.2D2.D2.D.3D2.2D81.4B58.2D2.D2.D.3D2.2D81.4B176.2D2.D2.D.3D2.2D81.4B58.2D2.D2.D.3D2.2D81.4B\$14.D2.D.D2.D2.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.4B169.3D5.D2.D.D2.D2.D4.D79.4B51.3D5.D2.D.D2.D2.D4.D79.4B\$6.D3B4.D2.D.D2.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.D2.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.4B45.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.4B68.4B44.D2.D.2D3.D28.4B\$15.4B42.3D.D2.D2.3D26.4B70.4B42.3D.D2.D2.3D26.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.2A17.4B76.4B36.2A11.A6.2A17.4B\$19.4B34.B2AB9.A.A4.A2.A15.4B78.4B34.B2AB9.A.A4.A2.A15.4B196.4B34.B2AB9.A.A4.A2.A15.4B78.4B34.B2AB9.A.A4.A2.A15.4B\$20.4B34.3B9.A.A3.A.3A3.A10.4B7.2A71.4B34.3B9.A.A3.A.3A3.A10.4B7.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.4B8.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.A3.2A6.A5.4B11.A4.2A\$23.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A65.4B30.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.6B12.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.A7.5B14.B2ABA.A189.4B26.13B5.A.A2B.A7.5B14.B2ABA.A71.4B26.13B5.A.A2B.A7.5B14.B2ABA.A\$27.4B24.15B5.A2B.2A6.7B14.2B.BA73.4B24.15B5.A2B.2A6.7B14.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.3B10.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.B2A3B195.4B20.29B4.6B6.A6.B2A3B77.4B20.29B4.6B6.A6.B2A3B\$31.4B18.9B2D2B2A16B2.7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B196.4B18.9B2D2B2A16B2.7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B\$32.4B16.9BDBD2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B195.4B16.9BDBD2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B\$33.4B14.2AB3.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.D2.D.3D2.2D45.4B9.A7.6B14.19B.B2A4.8B2.4B5.BA.A7.2D2.D2.D.3D2.2D163.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\$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.19B2A4.6B5.7B.B2A7.D2.D.D2.D2.D5.D\$38.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.2D165.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\$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.D5.D165.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D5.D47.4B11.4B5.A15.17B6.4B4.2A5.7B9.D2.D.D2.D2.D5.D\$40.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D49.4B9.4B7.3A12.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.A10.2AB.15B4.4B7.3A3.9B2.2A.A68.4B7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A186.4B7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A68.4B7.4B10.A10.2AB.15B4.4B7.3A3.9B2.2A.A\$42.4B5.4B21.A.AB4.12B3.4B10.A3.11BA.2A69.4B5.4B21.A.AB4.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.A185.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.5B16.2A18.11B19.16B72.5B16.2A18.11B19.16B190.5B16.2A18.11B19.16B72.5B16.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.11B2E2B16.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.3B11.7B23.10BE4B13.3A\$44.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B24.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.B5.17B6.5B27.15B.12B65.4B.B5.17B6.5B27.15B.12B183.4B.B5.17B6.5B27.28B65.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.5B24.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.A4.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.20BA63.34B27.A.AB2.4B4.20BA\$55.33B28.2AB2.B.2B.A9.12B66.33B28.2AB2.B.2B.A9.12B184.33B28.2AB2.B.2B.A9.12B66.33B28.2AB2.B.2B.A9.12B\$53.2AB2.31B29.3B.AB.A.A8.11B65.2AB2.31B29.3B.AB.A.A8.11B183.2AB2.31B29.3B.AB.A.A8.11B65.2AB2.31B29.3B.AB.A.A8.11B\$52.A.AB4.B.16B2.4B.B33.B3A3.A9.10B65.A.AB4.B.16B2.4B.B33.B3A3.A9.10B183.A.AB4.B.16B2.4B.B33.B3A3.A9.10B65.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.3AB4A10.14BA.A.A.A54.2A12.9B4.4B35.3AB4A10.14BA.A.A.A\$62.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A67.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A185.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A67.11B5.2A9.B2A24.A4.A2.A10.13B.B.A.A\$61.12B6.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.2A2.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.4B57.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.2A66.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.3A63.13B\$52.3A.A.A8B8.A63.14B58.3A.A.A8B8.A63.14B176.3A.A.A8B8.A63.14B58.3A.A.A8B8.A63.14B\$55.A.A.8B73.14B60.A.A.8B73.14B178.A.A.8B73.14B60.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.4B53.3A.2A4.6B72.2A4.4B.2B.4B171.3A.2A4.6B72.2A4.7B.4B53.3A.2A4.6B72.2A4.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.4B51.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.8B70.A8.7B3.4B52.A.2AB.8B70.A8.7B3.4B\$56.10B79.8B3.4B55.10B79.8B3.4B173.10B79.8B3.4B55.10B79.8B3.4B\$56.6B2A3B79.8B3.4B54.6B2A3B79.8B3.4B172.6B2A3B79.8B3.4B54.6B2A3B79.8B3.4B\$56.6B2A2B5.2A73.8B4.4B53.6B2A2B5.2A73.8B4.4B171.6B2A2B5.2A73.8B4.4B53.6B2A2B5.2A73.8B4.4B\$56.10B5.A4.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.D4.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.6B4.A4.4B49.8B2D2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B\$54.8B2D5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B48.8B2D5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B166.8B2D5B8.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.6B2A2B11.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.18B17.2A38.2A18B64.18B17.2A\$49.2AB.17B63.17B58.2AB.17B63.17B176.2AB.17B63.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.6B5.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.7B72.3BA5.4B64.2B.7B190.3BA5.4B64.2B.7B72.3BA5.4B64.2B.7B\$63.BA.A5.4B63.11B72.BA.A5.4B63.11B190.BA.A5.4B63.11B72.BA.A5.4B63.11B\$64.A.A6.4B61.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.A7.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.7B6.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.6B143.A3.2A4.6B261.A3.2A4.6B143.A3.2A4.6B\$129.A.B6.6B144.A.B6.6B262.A.B6.6B144.A.B6.6B\$128.2AB2AB3.7B143.2AB2AB3.7B261.2AB2AB3.7B143.2AB2AB3.7B\$131.2AB.8B147.2AB.8B265.2AB.8B147.2AB.8B\$128.2A3.10B144.2A3.10B262.2A3.10B144.2A3.10B\$128.A4.6B2A3B143.A4.6B2A3B261.A4.6B2A3B143.A4.6B2A3B\$129.A3.6B2A2B5.2A138.A3.6B2A2B5.2A256.A3.6B2A2B5.2A138.A3.6B2A2B5.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.B2A261.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.D121.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.D2.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.4B146.BA.A5.4B\$141.A.A6.4B146.A.A6.4B264.A.A6.4B146.A.A6.4B\$142.A8.3B147.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.D2.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.D4.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.D2.D2.D4.D5.B.2D133.D2.D.D2.D2.D4.D5.2B2E252.2D3.2D3.D3.3D3.2BD136.2D3.2D3.D3.3D3.2BEB\$118.2D3.2D3.D3.3D3.2BD136.2D3.2D3.D3.3D3.2BEB272.4B155.4B\$137.4B155.4B272.4B155.4B\$136.4B155.4B272.4B155.4B\$135.4B155.4B272.4B155.4B\$134.4B155.4B272.4B155.4B\$133.4B155.4B272.4B155.4B\$132.4B155.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.4B155.4B\$126.4B155.4B272.4B155.4B\$125.4B155.4B272.4B155.4B\$124.4B155.4B272.4B155.4B\$123.4B155.4B272.4B155.4B\$122.4B155.4B272.4B155.4B\$121.4B155.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.4B41.A113.4B158.A.A111.4B41.A.A111.4B\$.A.A111.4B41.A.A111.4B158.A2.A110.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.D79.4B168.3E5.D2.D.D2.D2.D4.D79.4B51.3E5.D2.D.D2.D2.D4.D79.4B\$6.3E5.D2.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.E3B4.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.4B93.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.D31.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.D2.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.4B36.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.A2.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.4B34.3B9.A.A3.A.3A3.A10.4B7.2A71.4B34.3B9.A.A3.A.3A3.A10.4B7.2A190.4B32.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.A190.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A66.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A\$22.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A66.4B31.5B8.B2.A.A3.2A6.A5.4B11.A4.2A185.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A65.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.A2.A\$23.4B30.6B6.2ABA2.4A.A5.2A.7B8.4A.2A2.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.BABABA.A\$25.4B29.13B2.A.AB2.A8.6B12.BABABA.A70.4B29.13B2.A.AB2.A8.6B12.BABABA.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.BA\$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.6B14.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.2B10.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.9B2D2B2A16B2.7B6.A.AB3.B2A3B78.4B18.9B2C2B2A16B2.7B6.A.AB3.B2A3B197.4B16.9BDBD2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B\$32.4B16.9BDBD2B2A16B2.7B7.2AB.10B77.4B16.9BCBC2B2A16B2.7B7.2AB.10B196.4B14.2AB3.6BD20B.9B8.13B77.4B14.2AB3.6BC20B.9B8.13B\$33.4B14.2AB3.6BD20B.9B8.13B77.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.2A184.4B10.A.2A5.6B3.B2.2B2.20B4.B3.15B9.A67.4B10.A.2A5.6B3.B2.2B2.20B4.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.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.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.6B5.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.2A15.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.4B11.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.D5.D166.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D49.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.2D\$40.4B9.4B7.3A12.17B5.4B5.A6.9B8.2D3.2D3.D3.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.4B7.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.12B3.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.A9.11B.4B16.9B8.2A\$43.4B3.4B22.A9.11B.4B16.9B8.2A65.4B3.4B22.A9.11B.4B16.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.9B5.BA.A68.7B33.15B12.A.2A2.9B5.BA.A\$45.7B33.15B12.A.2A2.9B5.BA.A68.7B33.15B12.A.2A2.9B5.BA.A187.5B35.13B13.2A.A15B.B2A70.5B35.13B13.2A.A15B.B2A\$46.5B35.13B13.2A.A15B.B2A70.5B35.13B13.2A.A15B.B2A188.5B16.2A18.11B19.16B72.5B16.2A18.11B19.16B\$46.5B16.2A18.11B19.16B72.5B16.2A18.11B19.16B189.7B14.B2AB17.10B20.10BEBE3B71.7B14.B2AB17.10B20.10BDBD3B\$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.A172.3B3.4B14.2B4.3B11.7B23.10BE4B13.3A54.3B3.4B14.2B4.3B11.7B23.10BD4B13.3A\$44.3B3.4B14.2B4.3B11.7B23.10BD4B13.3A54.3B3.4B14.2B4.3B11.7B23.10BE4B13.3A172.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B24.17B10.A\$44.2B5.4B12.14B7.6B24.17B10.A57.2B5.4B12.14B7.6B24.17B10.A175.B7.4B11.14B7.5B25.20B2.2B3.2A56.B7.4B11.14B7.5B25.20B2.2B3.2A\$44.B7.4B11.14B7.5B25.20B2.2B3.2A56.B7.4B11.14B7.5B25.20B2.2B3.2A183.4B.B5.17B6.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.2A4.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.19B2.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.2AB2.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.AB4.B.16B2.4B.4B30.B3A3.A9.10B183.A11.10B.2B3.3B3.4B29.A15.11B.B.2A3.2A55.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.2A12.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.A2.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.A24.3A13.2AB.13B2A.2A183.12B3.3A13.A26.2A11.A.AB4.9B.B69.12B3.3A13.A26.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.A15.2A38.A7.9B\$50.2A.2A2.2A2.11B4.A15.2A38.A7.9B60.2A.2A2.2A2.11B4.A15.2A38.A7.9B177.A.A.A2.A.A2.8B.4B57.2A7.9B59.A.A.A2.A.A2.8B.4B57.2A7.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.2A66.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.12B177.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.A63.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.A4.7B2.4B\$49.A4.B6.6B72.A4.2B3.2B2.4B51.A4.B6.6B72.A4.2B3.2B2.4B170.3AB2AB3.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.8B70.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.2A73.8B4.4B171.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B52.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B\$56.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B52.10B5.A4.3D.D2.D2.2D57.6B2.B2A3.4B169.11B2.BA.A5.D2.2D.D4.D56.7B.BA.A3.4B50.11B2.BA.A5.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.D2.D.2D3.D41.2A15.6B4.A4.4B49.8B2C2B.B2A6.D2.D.2D3.D41.2A15.6B4.A4.4B166.8B2C5B8.D2.D.2D2.D43.A8.B4.8B4.2A4.3B48.8B2C5B8.D2.D.2D2.D43.A8.B4.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.16B62.2AB.13B2A3B11.B44.2B.16B62.2AB.13B2A3B11.B161.2A18B64.18B17.2A38.2A18B64.18B\$49.2A18B64.18B57.2A18B64.18B17.2A156.2AB.17B63.17B17.A2.A37.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.4B63.13B20.A.A164.7B4.4B64.12B20.A47.7B4.4B64.12B\$57.7B4.4B64.12B68.7B4.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.4B64.2B.7B191.BA.A5.4B63.11B72.BA.A5.4B63.11B\$63.BA.A5.4B63.11B72.BA.A5.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.11B194.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.2A2.2A3.B3.4B2.B2A76.A7.3B47.2A.2A2.2A3.B3.4B2.B2A203.2B48.A.A2.A.A3.7B3.BA.A84.2B48.A.A2.A.A3.7B3.BA.A\$77.2B48.A.A2.A.A3.2B.4B3.BA.A84.2B48.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.2A134.A.A2.2B3.6B7.2A\$128.A.A2.2B3.6B7.2A134.A.A2.2B3.6B7.2A251.2A.A.BA2B.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.8B143.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.6B2A3B\$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.2A3.10B5.A138.2A3.10B5.A260.11B2.BA.A142.11B2.BA.A\$132.11B2.BA.A142.11B2.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.D2.D2.2D125.16B6.3D.D2.D2.2D240.2B.16B7.D2.2D.D4.D121.2B.16B7.D2.2D.D4.D\$127.2B.16B7.D2.2D.D4.D121.2B.16B7.D2.2D.D4.D238.2A16B2C7.D2.D.2D2.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.D2.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.4B145.4B6.4B265.3BA5.4B146.3BA5.4B\$139.3BA5.4B146.3BA5.4B265.BA.A5.4B146.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.

dvgrn
Moderator

Posts: 5614
Joined: May 17th, 2009, 11:00 pm

Re: Challenge: Minimal Toffoli gate

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

Macbi

Posts: 659
Joined: March 29th, 2009, 4:58 am

Re: Challenge: Minimal Toffoli gate

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

`x = 152, y = 122, rule = LifeHistory25.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.B2A\$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.4B33.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.4B4.2B3.B3.9B29.B\$62.4B17.4B5.3B.B2A2.10B27.2B\$63.4B15.4B7.A3B2A2.5B2A3B26.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.5B14.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.2A11.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.4B21.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.4B35.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.2A2BA4B3A13B2A2.A7.6B6.6B2.8B.9B.B2.4B\$38.4B16.3BA3BA15B.B10.6B8.20B3A10B\$37.4B17.4B3A16B11.6B10.18BA4BA6B2A\$36.4B51.6B12.16BA5BA6B2A\$35.4B19.4B3A16B9.6B14.16BA12B\$34.4B20.3BA3BA15B.B6.6B16.16B2A10B\$33.4B20.2A2BA4B3A13B2A4.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.BABA2B8.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.6B8.2B3AB.B3A2B13.BE2B4.2D5.D.2D.D\$16.4B61.6B.6B8.B2A2BA.A2B2AB14.3B5.D5.D.D.2D\$15.4B62.B2A3B.3B2AB8.AB4A.4ABA15.2B5.D5.D.D.2D\$14.4B63.BAB2AB.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.4B5.3D4.D.D.2D54.2B2A5.2A2B6.2A6B.6B2A\$4.4B8.D4.D.D.2D73.2A2B2A2B.2B2A2B2A\$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

Kazyan

Posts: 811
Joined: February 6th, 2014, 11:02 pm

Re: Challenge: Minimal Toffoli gate

Kazyan wrote:This is hardly sporting, but [...]

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

`x = 282, y = 287, rule = B3/S23obo\$b2o\$bo67\$263b2o\$263b2o7\$271b2o\$271b2o6\$270b2o\$258b2o9bobo\$244b2o11bo2bo7b2obo4b3o\$243bobo12b2o9b2o\$245bo24bo4\$275b2o\$266b2o6bo\$265bo2bo6b2o\$266b2o3\$275bo\$271b2ob2o\$274bo2bo\$272bo6bo\$272bo2bo3bo\$261b3o9b4o2b3o\$253bo6bo2b2o8bo2bo2b2o\$252b3o5bo2bob2o8bo3bo\$251bo11bobob2o5bob3o\$250b2o11bobo2bo6b3o\$249b3o11bo4bo7bo\$236b2obo23bo3bo\$236b4o6b2o5bo10b3o\$235bo3bo6b2o\$236b3o\$236b3o\$238bo9\$244b3o\$226bo17b4o\$224b2ob2o14bo3b2o\$224b2ob2o19bo2b3o\$225bob3o13b2ob2o3bobo\$224b3o17b4o3b3o\$245bo3\$202bo37bobo\$201bo36b2o2b2o\$201b3o34b2o3b2o\$225b2o11b2o2b2o\$225b2o12b2ob2o\$240b2o\$223bo\$222b2o\$221b3o17b3o\$220bo20bobo\$219b2o4bo15b3o\$220bo3\$201bo\$200bobo\$200bobo\$201bo17b2o\$218bo\$218bo\$184b2o32b7o\$184b2o33bo5bo\$209bo10b3o2bo\$208bobo9bo4bo\$208bobo10bo2bo\$201bo7bo11b3o\$200b3o\$199bo2b2o\$192b2o5b3o12bo\$192b2o20bob2o\$218b2o\$208bo5b2o2bo2bo\$207bobo3b2o2b2obobo\$201bo5bobo8b2ob3o\$201bo13bo5b2o\$201bo19bo\$216b5o\$218b2o\$218bo22\$148b2o\$148b2o2\$209b2o9b2o\$210bo9bobo\$210bobo8b2o4bo\$211b2o13bobo\$227bo\$156b2o\$156b2o5\$234bo\$232b3o\$143b2o13bo72bo\$142bo2bo10b2ob3o68bobo\$143b2o13b3ob2o67bo\$127b2o30bo\$126bobo\$128bo31bo68b2o\$160bo68b2o\$160bo\$151b2o7bobo\$150bo2bo7bo\$151b2o\$203b2o\$202bobo\$159bo39bo2bo\$158b2o39b4o\$158bo\$159bobo37b2o\$159bo2bo36b2o\$160bobo\$146b3o11bobo\$161bo36bo\$140bo5bo3bo46bobo\$139b2o6b4o47bo\$105b2o31b2o10bo44b3o\$126bo3b2o4bobo56bo\$124b2obob3o4bobo\$124bo4b3o62bo\$124bo3bo64bobo\$125b3o66bo\$127bo9\$134bo\$106b3o21bo3b2o\$106bo2bo19bobob2obo\$85bo19bo3bo22bo4bo\$84bo21bo2b2o17b3obo3bo2bo\$84b3o21bo14bo\$106b2o13bobo13bobo\$105b3o12bo2bo14bo\$105b3o13bo\$122b2o\$121bo\$119b3o\$120bo\$105b2o14bobo\$122bo2bo\$104b3o19bo\$103b2o18bobo\$102b2o2\$82bo\$81bobo\$81bobo\$82bo\$100bobo\$100bo2bo\$65b2o33bo2bo\$65b2o36bo\$90bo11b3o\$89bobo\$89bobo\$90bo3\$73b2o7bo\$73b2o7bo\$81bobo11b2o\$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!

calcyman

Posts: 2019
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

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

`x = 282, y = 287, rule = B3/S23obo\$b2o\$bo67\$263b2o\$263b2o7\$271b2o\$271b2o6\$270b2o\$258b2o9bobo\$244b2o11bo2bo7b2obo4b3o\$243bobo12b2o9b2o\$245bo24bo4\$275b2o\$266b2o6bo\$265bo2bo6b2o\$266b2o3\$275bo\$271b2ob2o\$274bo2bo\$272bo6bo\$272bo2bo3bo\$261b3o9b4o2b3o\$253bo6bo2b2o8bo2bo2b2o\$252b3o5bo2bob2o8bo3bo\$251bo11bobob2o5bob3o\$250b2o11bobo2bo6b3o\$249b3o11bo4bo7bo\$236b2obo23bo3bo\$236b4o6b2o5bo10b3o\$235bo3bo6b2o\$236b3o\$236b3o\$238bo9\$244b3o\$226bo17b4o\$224b2ob2o14bo3b2o\$224b2ob2o19bo2b3o\$225bob3o13b2ob2o3bobo\$224b3o17b4o3b3o\$245bo3\$202bo37bobo\$201bo36b2o2b2o\$201b3o34b2o3b2o\$225b2o11b2o2b2o\$225b2o12b2ob2o\$240b2o\$223bo\$222b2o\$221b3o17b3o\$220bo20bobo\$219b2o4bo15b3o\$220bo3\$201bo\$200bobo\$200bobo\$201bo17b2o\$218bo\$218bo\$184b2o32b7o\$184b2o33bo5bo\$209bo10b3o2bo\$208bobo9bo4bo\$208bobo10bo2bo\$201bo7bo11b3o\$200b3o\$199bo2b2o\$192b2o5b3o12bo\$192b2o20bob2o\$218b2o\$208bo5b2o2bo2bo\$207bobo3b2o2b2obobo\$201bo5bobo8b2ob3o\$201bo13bo5b2o\$201bo19bo\$216b5o\$218b2o\$218bo22\$148b2o\$148b2o2\$209b2o9b2o\$210bo9bobo\$210bobo8b2o4bo\$211b2o13bobo\$227bo\$156b2o\$156b2o5\$234bo\$232b3o\$143b2o13bo72bo\$142bo2bo10b2ob3o68bobo\$143b2o13b3ob2o67bo\$127b2o30bo\$126bobo\$128bo31bo68b2o\$160bo68b2o\$160bo\$151b2o7bobo\$150bo2bo7bo\$151b2o\$203b2o\$202bobo\$159bo39bo2bo\$158b2o39b4o\$158bo\$159bobo37b2o\$159bo2bo36b2o\$160bobo\$146b3o11bobo\$161bo36bo\$140bo5bo3bo46bobo\$139b2o6b4o47bo\$105b2o31b2o10bo44b3o\$126bo3b2o4bobo56bo\$124b2obob3o4bobo\$124bo4b3o62bo\$124bo3bo64bobo\$125b3o66bo\$127bo9\$134bo\$106b3o21bo3b2o\$106bo2bo19bobob2obo\$85bo19bo3bo22bo4bo\$84bo21bo2b2o17b3obo3bo2bo\$84b3o21bo14bo\$106b2o13bobo13bobo\$105b3o12bo2bo14bo\$105b3o13bo\$122b2o\$121bo\$119b3o\$120bo\$105b2o14bobo\$122bo2bo\$104b3o19bo\$103b2o18bobo\$102b2o2\$82bo\$81bobo\$81bobo\$82bo\$100bobo\$100bo2bo\$65b2o33bo2bo\$65b2o36bo\$90bo11b3o\$89bobo\$89bobo\$90bo3\$73b2o7bo\$73b2o7bo\$81bobo11b2o\$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:

`x = 279, y = 283, rule = B3/S23obo\$b2o\$bo65\$261b2o\$261b2o7\$269b2o\$269b2o6\$244b2o19b3o3bo\$243bobo10b2o5b5o2bobo\$245bo9bo2bo3b2o8bob3o\$256b2o5b2o4b3o\$264bo3b2o5\$264b2o\$263bo2bo\$264b2o4\$269b2obo\$269b2obobo2bo\$262bo8bo2bo3bo\$260bobo5bobo6bo\$249bo9bo2bo7bo5bo\$248b3o9bo17bo\$248bo2bo9b2o15bo\$246bo4b2o7bo\$245bo3bobo6b3o\$246bo2b2o8bo\$232bo12b5o10bobo\$231bob2o9b2o15bo2bo\$230bo4bo8b2o19bo\$231bo30bobo\$232b4o8\$224bo\$223bobo\$222bo3bo22b3o\$223bo2bo22b3o\$223bo2bo22bo\$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\$190b2o6bobo11b2ob2o\$197bo2bo13bo\$198b2o12b2o2\$199bo13b2o\$199bo\$199bo16bo\$213bobo\$214bo2b2o21\$148b2o\$148b2o4\$207b2o9b2o\$208bo9bobo\$208bobo8b2o4bo\$156b2o51b2o13bobo\$156b2o67bo7\$143b2o13bo73bo\$142bo2bo10b2ob3o68b3o\$143b2o13b3ob2o65bo\$127b2o30bo68bobo\$126bobo100bo\$128bo31bo\$160bo\$160bo66b2o\$151b2o7bobo64b2o\$150bo2bo7bo\$151b2o\$198b2o\$199bo\$159bo39bob2o\$158b2o34bo2b2obobo\$158bo35b4o2bo\$159bobo30b2o5b2o\$159bo2bo28bo2bo2b2o\$160bobo28b3o2bobo\$146b3o11bobo31b2o\$161bo29b2obo\$140bo5bo3bo41bobo2bo\$139b2o6b4o41bobobobo\$105b2o31b2o10bo42b2ob2o\$126bo3b2o4bobo\$124b2obob3o4bobo\$124bo4b3o62bo\$124bo3bo64bobo\$125b3o66bo\$127bo9\$134bo\$106b3o21bo3b2o\$106bo2bo19bobob2obo\$85bo19bo3bo22bo4bo\$84bo21bo2b2o17b3obo3bo2bo\$84b3o21bo14bo\$106b2o13bobo13bobo\$105b3o12bo2bo14bo\$105b3o13bo\$122b2o\$121bo\$119b3o\$120bo\$105b2o14bobo\$122bo2bo\$104b3o19bo\$103b2o18bobo\$102b2o2\$82bo\$81bobo\$81bobo\$82bo\$100bobo\$100bo2bo\$65b2o33bo2bo\$65b2o36bo\$90bo11b3o\$89bobo\$89bobo\$90bo3\$73b2o7bo\$73b2o7bo\$81bobo11b2o\$82b3o9b2ob2o\$82b2o2b4o9b2o\$82bo7bo6bo3bo\$83bo5bo8b3o\$83bo!`
Tanner Jacobi

Kazyan

Posts: 811
Joined: February 6th, 2014, 11:02 pm

Re: Challenge: Minimal Toffoli gate

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.

dvgrn
Moderator

Posts: 5614
Joined: May 17th, 2009, 11:00 pm

Re: Challenge: Minimal Toffoli gate

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:

`x = 91, y = 95, rule = LifeHistory71.A\$71.3A\$65.B8.A\$63.4B6.A.A\$64.4B5.A.AB\$65.4B5.A3B\$66.4B6.4B\$67.4B5.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.B16.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.9B5.A6.6B4.2A.3A\$17.4B10.2AB2.3B.4B8.9B5.2A6.5B4.A2.2A\$18.4B10.11B8.10B5.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.11BA3B14.2A4.4B\$18.11BABA2B14.A6.4B\$17.4B.7BABA2B11.BA.A7.4B\$16.4B4.B2.3BA3B8.2B.B2A9.4B\$15.4B9.6B6.6B12.4B\$3.B10.4B11.6B4.6B14.4B\$2.3B8.4B5.2A5.6B4.7B14.4B\$2.4B6.4B7.A6.6B2.8B15.4B\$3.4B4.4B8.A.AB3.17B15.4B\$4.4B2.4B4.A5.2AB.20B15.4B\$5.8B3.3A7.22B16.4B\$6.6B3.A10.21B18.4B\$7.4B4.2A9.19B21.4B\$2A6.9B11.17B.2B19.4B\$.A7.6B14.18B2A19.4B\$.A.2A5.6B3.B2.2B2.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.AB3.4B\$9.B.B9.2A.2A.A.A6.A7.4B\$10.3B9.A.A3.A.3A2.2A8.4B\$9.B2AB9.A.A4.A2.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!

calcyman

Posts: 2019
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

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:

`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.29B4.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.4B6.2A6.9B14.19B2A\$79.4B12.4B4.2A15.17B.B\$80.4B10.4B5.A15.17B\$81.4B8.4B7.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.2C6B22.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.10B7.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.2A2.A\$101.9B2D10B7.2A\$96.2A3.10B2D7B\$97.A3.18B\$97.A.2A17B\$92.A2.2A.A.A18B\$92.4A2.A4.17B\$90.2A5.2A5.17B\$89.A2.A2.2A6.12B3.4B\$89.3A2.A.A5.4BD3B.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.4B2.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.6B5.2A.2A4.4B\$95.36B4.A2.A2.A4.4B\$95.9B.27B3.B2A2.2A5.4B\$96.7B2.16B2A14B11.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.A2.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.

dvgrn
Moderator

Posts: 5614
Joined: May 17th, 2009, 11:00 pm

Re: Challenge: Minimal Toffoli gate

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)

`x = 296, y = 204, rule = LifeHistory13.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.A79.A79.A79.A\$8.A.A77.A.A77.A.A77.A.A\$9.2A78.2A78.2A78.2A4\$30.2A78.2A78.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.3A77.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.D24.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.3A77.3A77.3A\$26.A79.A79.A79.A2\$2.2A78.2A78.2A78.2A\$3.A79.A79.A79.A\$3A77.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.A4.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.A8.A2.A.A3.2A.A56.A.A8.A2.A.A3.2A.A56.A.A8.A2.A.A3.2A.A56.A.A8.A2.A.A3.2A.A\$9.2A18.A.2A56.2A18.A.2A56.2A18.A.2A56.2A18.A.2A\$29.A79.A79.A79.A\$28.2A78.2A78.2A78.2A5\$9.D18.2A59.E18.2A59.D18.2A59.E18.2A\$9.D.D17.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.2A78.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!`
simeks

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

Re: Challenge: Minimal Toffoli gate

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!

calcyman

Posts: 2019
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

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...

`x = 101, y = 59, rule = LifeHistory22.C\$23.2C\$22.2C2\$99.C\$98.C\$98.3C17\$36.A\$35.A.A\$35.A.A\$33.3A.2A\$2.C29.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.13B2A11BD31.2A\$9.24B33.A\$9.17B.B28.2A9.3A\$10.15B30.A.A11.A\$10.15B5.A3.2A19.A\$11.13B5.A.A3.A18.2A\$13.13B2.A.A3.A\$12.8B4.2A.A.A3.A\$12.6B6.2ABA2.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 --

dvgrn
Moderator

Posts: 5614
Joined: May 17th, 2009, 11:00 pm

Re: Challenge: Minimal Toffoli gate

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:

`x = 46, y = 44, rule = LifeHistory3B\$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.8B13.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!

calcyman

Posts: 2019
Joined: June 1st, 2009, 4:32 pm

Re: Challenge: Minimal Toffoli gate

How about using the H-MWSS as the over-unity component?
`x = 33, y = 66, rule = LifeHistory15.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.3B3DBC2BC3B.6B\$10.5BD2B2C9BE2B\$B.B.B.B.B.18BEBE\$29B2E\$5D25B\$D4BD22B\$D27B\$BD3BD22B\$.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.B2AB3A\$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.
Best wishes to you, Scorbie

Scorbie

Posts: 1379
Joined: December 7th, 2013, 1:05 am

Re: Challenge: Minimal Toffoli gate

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:

`x = 162, y = 141, rule = LifeHistory2.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.A6.B5.4B10.A.AB2.4B.2A2B9.28B\$75.BA.A5.2B6.4B10.2AB2.3B.4B8.30B\$74.3BA5.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.10B2D7B26.6B4.2A.3A\$62.3A.2A4.6B10.A2.A4.A3.18B26.6B6.B4.A\$64.2A2.A4.5B11.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.3B2A6B\$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.5B2DB11.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!`

dvgrn
Moderator

Posts: 5614
Joined: May 17th, 2009, 11:00 pm