# Fountain OOO REliving
Provided file is [fountain-ooo-relive](https://pastebin.com/raw/ncHEVjuw)
Theme hints at Game of Life, comment in file hints that it can be opened with Golly (a Game of Life engine). It's a really big pattern with some gridlike sections and some labels indicating that it's a computer - opcodes, RAM and ROM, etc.
But zoom in further and each pixel turns out to be made of many smaller pixels in standard Game of Life layouts. These form [OTCA Metapixels](https://www.conwaylife.com/wiki/OTCA_metapixel). Each is 2048x2048 Life cells and they can simulate the Game of Life itself, or any other similar ruleset. But something's a little different - different metapixels have different rulesets and they don't form a complete grid.
Some research into the architecture of the computer this is all being used to simulate (the names of the opcodes like "MLZ" etc make good search terms) turns up the [Quest for Tetris](https://github.com/QuestForTetris), a project to implement Tetris in Game of Life by using OTCA metapixels to build a computer which can run Tetris. A [thread](https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life) on Code Golf StackOverflow has a good overview of the architecture.
To play around with this more we should get it to run, but it runs very slowly because each metapixel cycle takes thousands of Life cycles and each CPU cycle takes thousands of metapixel cycles, so we should "decompile" the metapixels into single pixels in the VarLife ruleset (this is the opposite of the process Quest for Tetris used to generate the computer). `meta2varlife.lua` (run as a script within Golly) will do this by checking the pixels which program each metacell's ruleset and translating into VarLife. `Varlife.rule` (copied from Quest For Tetris) has been modified with the colors dimmed except for the "on" states which makes it much easier to read the contents of RAM and see the computer operating.
Now we can see that RAM is initially all 0 except for address 1 which has a few bits set. When we run, RAM fills up and then is modified and eventually the CPU halts. Maybe the flag is in RAM?  `readram.lua` dumps the contents of RAM and we can use that to get the initial and final states (see `ram.txt`). But there's no obvious ASCII encoded text or anything like that.
The challenge is tagged as reversing so let's see what the program is doing. `readrom.lua` reads the program ROM and translates into the QFTASM assembly language (`rom.txt`), which we can run on the QFTASM [interpreter](http://play.starmaninnovations.com/qftasm/) and confirm that we get the same results there as when running in Golly. The code writes a bunch of constants into addresses 2 through 39, then subtracts a different constant XOR the value at address 1 from each of those addresses, then halts.
Since this computer has no I/O, input is done by writing directly into memory. So it seems like the value in address 1, which is never written to but is used to modify the contents of memory, is supposed to be the input, and its value affects the final value in each of the addresses 2 through 39 which the program modifies. So maybe we need to find the right value at address 1 which will end up with the flag in those addresses. We can check if we have it right because we know the flag format starts with "OOO" and it will be ASCII.
`hack.swift` simulates the program's calculations for every possible value of address 1 (it's only 16 bits so we can just brute force, no need to use some fancy solver) and filters to only those which produce valid ASCII and start with "OOO". It will quickly find the flag: `OOO{in_this_life___youre_on_your_own}`.
## Files
### meta2varlife.lua```local g = golly()
local getcell = g.getcelllocal setcell = g.setcell
local r = g.getrect()local x, y, width, height = r[1], r[2], r[3], r[4]
local mygrid = {}
-- bounding box is -8388608, -8388607, 10295296, 2965504-- print('expected bounding box:', -8388608, -8388607, 10295296, 2965504)-- print('actual bounding box:  ', x, y, width, height)
-- Pixel addresses of the pixels indicating rules for a random metapixel:-- B8 -8386412 -7094915-- B7 -8386412 -7094905-- B6 -8386412 -7094895-- B5 -8386412 -7094869-- B4 -8386412 -7094859-- B3 -8386412 -7094849-- B2 -8386412 -7094823-- B1 -8386412 -7094913-- B0 -8386412 -7094803-- S8 -8386412 -7094913-- S7 -8386412 -7094903-- S6 -8386412 -7094893-- S5 -8386393 -7094867-- S4 -8386393 -7094857-- S3 -8386393 -7094847-- S2 -8386393 -7094821-- S1 -8386393 -7094911-- S0 -8386393 -7094801
-- rulesets for varlife: B/S (no metapixel), B1/S, B2s, B12/S1-- So we can just check B1 and B2-- B2 -8386412 -7094823-- B1 -8386412 -7094913-- take those relative to the x,y of bounding box, modulo 2048:-- b1: (148, 1496), b2: (148, 1506)-- now I don't really understand Varlife.rule but we can go off the colors-- and cross-reference with the colors here:-- http://play.starmaninnovations.com/varlife/BeeHkfCpNR-- [not listed] 0 -> B/S dead-- 1 255 255 255  -> B/S alive (should never happen)-- 2 0 0 255      -> B1/S dead-- 3 0 255 255    -> B1/S alive-- 4 0 255 0      -> B2/S dead-- 5 255 255 0    -> B2/S alive-- 6 255 0 0      -> B12/S1 dead-- 7 255 128 0    -> B12/S1 alive
-- finally some metapixels are enabled-- one of the pixels in the center of one which is enabled is at:-- -1754083, -7103591-- relative to bounding box, mod 2048:-- 1053, 920alive_count = 0for _y = y,y+height,2048 do    local row = {}    for _x = x,x+width,2048 do        local b1 = getcell(148 + _x, 1506 + _y)        local b2 = getcell(148 + _x, 1496 + _y)        local state = getcell(1054 + _x, 920 + _y)
        -- b1=0,b2=0: 0        -- b1=1,b2=0: 2        -- b1=0,b2=1: 4        -- b1=0,b2=1: 6        -- (+1 for enabled)        state = state + b2 * 4 + b1 * 2
        table.insert(row, state)        if state == 1 then            alive_count = alive_count + 1        end    end    table.insert(mygrid, row)end
g.addlayer()g.setrule('Varlife')
for y, row in ipairs(mygrid) do    for x, state in ipairs(row) do        setcell(x,y,state)    endend
g.fit()```
### Varife.rule```@RULE Varlife
A mixed rule game of life designed in the Quest for Tetris
The PPCG QFT (not Quantum/Quick Fourier Transform) crew, August 10, 2016
@TREE
num_states=8num_neighbors=8num_nodes=291 0 0 2 2 4 4 6 61 0 0 3 2 4 4 7 72 0 1 0 1 0 1 0 11 0 0 2 2 5 4 7 62 1 3 1 3 1 3 1 33 2 4 2 4 2 4 2 42 3 0 3 0 3 0 3 03 4 6 4 6 4 6 4 64 5 7 5 7 5 7 5 72 0 0 0 0 0 0 0 03 6 9 6 9 6 9 6 94 7 10 7 10 7 10 7 105 8 11 8 11 8 11 8 113 9 9 9 9 9 9 9 94 10 13 10 13 10 13 10 135 11 14 11 14 11 14 11 146 12 15 12 15 12 15 12 154 13 13 13 13 13 13 13 135 14 17 14 17 14 17 14 176 15 18 15 18 15 18 15 187 16 19 16 19 16 19 16 195 17 17 17 17 17 17 17 176 18 21 18 21 18 21 18 217 19 22 19 22 19 22 19 228 20 23 20 23 20 23 20 236 21 21 21 21 21 21 21 217 22 25 22 25 22 25 22 258 23 26 23 26 23 26 23 269 24 27 24 27 24 27 24 27
@COLORS
1 32 32 322 0 0 323 0 0 1284 0 32 05 128 128 06 32 0 07 255 255 255```
### readram.lua```lualocal g = golly()
local getcell = g.getcell
-- ram is on a grid of bits 16 x 71-- bits are spaced out 22 cells apart (x and y)-- (16 bit word size)-- address 0 (lowest x value) is the program counter-- lowest y value is 1s bit-- lowest bit of pc is at 3454,32
local words = 71local word_size = 16local spacing = 22local start_x = 3454local start_y = 32
function signedshort(n)    -- convert positive int to signed for 16-bit twos complement    if n < 0 or n >= 1<<16 then        error("Out of range: " .. n)    end    if n >= 1 << 15 then        return n - (1 << 16)    else        return n    endend
local output = ""for address = 0,words-1 do    local x = start_x + address * spacing    word = 0    for place = word_size-1,0,-1 do        local y = start_y + place * spacing        local bit = getcell(x, y) % 2        word = word | (bit << place)    end    output = output .. address .. ": " .. signedshort(word) .. "\n"end
g.setclipstr(output)g.note("RAM dump copied to clipboard")```
### ram.txt```
Initial RAM contents:0: 01: 122922: 03: 04: 0...
RAM contents after running to completion:0: -11: 122922: 164783: -162884: 164505: 164906: -162607: -162898: -163069: -1625310: -1629911: -1626412: 1651813: -1627414: -1625915: -1629816: 1646917: -1629618: -1627219: 1646420: 1646221: -1627822: 1648223: 1648824: -1628925: -1626626: 1649627: -1625828: -1628929: -1627230: 1652031: 1651032: 1651433: -1625734: -1627035: 1651036: 1648837: -1628738: 1649639: -2591740: 041: 042: 043: 4444: 045: 046: 0...```
### readrom.lua```lualocal g = golly()
local getcell = g.getcell
-- rom is a grid of instructions 58 bits high and 116 instructions wide-- it's "upside down" - opcode at the bottom-- grows leftwards, so first instruction is at the right-- bits are spaced out 11 cells apart (x and y)-- bottom right bit of ROM is at 3198,1378local instructions = 116local spacing = 11local start_x = 3198local start_y = 1378
local opcodes = {    [0] = 'MNZ',    [1] = 'MLZ',    [2] = 'ADD',    [3] = 'SUB',    [4] = 'AND',    [5] = 'OR' ,    [6] = 'XOR',    [7] = 'ANT',    [8] = 'SL' ,    [9] = 'SRL',    [10] = 'SRA',}
local types = {    [0] = '',    [1] = 'A',    [2] = 'B',    [3] = 'C'}
function getbit(address, bit)    local x = start_x - address * spacing    local y = start_y - bit * spacing     -- state of cell will be 0 or 2, convert to 0 or 1    return (getcell(x, y) == 0) and 0 or 1end
function getbits(address, bottombit, count)    -- get bits for the instruction at address    -- bottombit is the bit index into the instruction    -- count is the count    -- returns as a number    local val = 0    for bit=0,count-1 do        val = val | (getbit(address, bottombit + bit) << bit)    end    return valend
function signedshort(n)    -- convert positive int to signed for 16-bit twos complement    if n < 0 or n >= 1<<16 then        error("Out of range: " .. n)    end    if n >= 1 << 15 then        return n - (1 << 16)    else        return n    endend
local output = ""for address = 0,instructions-1 do    local opcode = getbits(address, 0, 4)    local arg1v = getbits(address, 4, 16)    local arg1t = getbits(address, 20, 2)    local arg2v = getbits(address, 22, 16)    local arg2t = getbits(address, 38, 2)    local arg3v = getbits(address, 40, 16)    local arg3t = getbits(address, 56, 2)
    output =        output .. address .. ". " ..        opcodes[opcode] .. " " ..        types[arg1t] .. signedshort(arg1v) .. " " ..        types[arg2t] .. signedshort(arg2v) .. " " ..        types[arg3t] .. signedshort(arg3v) .. ";\n"end
g.setclipstr(output)g.note("ROM dump copied to clipboard")```
### rom.txt```0. MLZ -1 44 43;1. XOR 0 0 2;2. MLZ -1 25971 2;3. MLZ -1 14554 3;4. MLZ -1 22445 4;5. MLZ -1 25411 5;6. MLZ -1 3743 6;7. MLZ -1 13391 7;8. MLZ -1 12059 8;9. MLZ -1 2554 9;10. MLZ -1 15823 10;11. MLZ -1 5921 11;12. MLZ -1 18009 12;13. MLZ -1 14823 13;14. MLZ -1 4757 14;15. MLZ -1 7754 15;16. MLZ -1 22480 16;17. MLZ -1 8371 17;18. MLZ -1 12418 18;19. MLZ -1 22738 19;20. MLZ -1 16499 20;21. MLZ -1 7132 21;22. MLZ -1 22793 22;23. MLZ -1 22307 23;24. MLZ -1 12485 24;25. MLZ -1 7936 25;26. MLZ -1 26630 26;27. MLZ -1 15483 27;28. MLZ -1 6471 28;29. MLZ -1 1806 29;30. MLZ -1 22705 30;31. MLZ -1 25019 31;32. MLZ -1 16442 32;33. MLZ -1 5145 33;34. MLZ -1 15593 34;35. MLZ -1 23867 35;36. MLZ -1 23738 36;37. MLZ -1 14086 37;38. MLZ -1 23123 38;39. MLZ -1 0 39;40. XOR A1 -27179 39;41. SUB A39 A2 2;42. XOR A1 -14018 39;43. SUB A39 A3 3;44. XOR A1 -22549 39;45. SUB A39 A4 4;46. XOR A1 -27735 39;47. SUB A39 A5 5;48. XOR A1 -225 39;49. SUB A39 A6 6;50. XOR A1 -15190 39;51. SUB A39 A7 7;52. XOR A1 -8339 39;53. SUB A39 A8 8;54. XOR A1 -1415 39;55. SUB A39 A9 9;56. XOR A1 -12768 39;57. SUB A39 A10 10;58. XOR A1 -6243 39;59. SUB A39 A11 11;60. XOR A1 -18725 39;61. SUB A39 A12 12;62. XOR A1 -13743 39;63. SUB A39 A13 13;64. XOR A1 -7402 39;65. SUB A39 A14 14;66. XOR A1 -4444 39;67. SUB A39 A15 15;68. XOR A1 -22495 39;69. SUB A39 A16 16;70. XOR A1 -12017 39;71. SUB A39 A17 17;72. XOR A1 -16138 39;73. SUB A39 A18 18;74. XOR A1 -22234 39;75. SUB A39 A19 19;76. XOR A1 -20283 39;77. SUB A39 A20 20;78. XOR A1 -5054 39;79. SUB A39 A21 21;80. XOR A1 -22161 39;81. SUB A39 A22 22;82. XOR A1 -22641 39;83. SUB A39 A23 23;84. XOR A1 -16096 39;85. SUB A39 A24 24;86. XOR A1 -4238 39;87. SUB A39 A25 25;88. XOR A1 -26510 39;89. SUB A39 A26 26;90. XOR A1 -13059 39;91. SUB A39 A27 27;92. XOR A1 -5726 39;93. SUB A39 A28 28;94. XOR A1 -2182 39;95. SUB A39 A29 29;96. XOR A1 -22211 39;97. SUB A39 A30 30;98. XOR A1 -28099 39;99. SUB A39 A31 31;100. XOR A1 -20296 39;101. SUB A39 A32 32;102. XOR A1 -7012 39;103. SUB A39 A33 33;104. XOR A1 -12961 39;105. SUB A39 A34 34;106. XOR A1 -21059 39;107. SUB A39 A35 35;108. XOR A1 -21210 39;109. SUB A39 A36 36;110. XOR A1 -14493 39;111. SUB A39 A37 37;112. XOR A1 -21817 39;113. SUB A39 A38 38;114. MLZ -1 -2 0;115. MLZ 0 0 0;```
### hack.swift```swiftimport Foundation
#if !swift(>=5.2)// if your system Swift on macOS is too old try "xcrun swift"#error("Requires Swift 5.2 or higher")#endif
// subtrahends are the values initially loaded into memory 2 through 39let subtrahends: [Int16] = [    25971,    14554,    22445,    25411,    3743,    13391,    12059,    2554,    15823,    5921,    18009,    14823,    4757,    7754,    22480,    8371,    12418,    22738,    16499,    7132,    22793,    22307,    12485,    7936,    26630,    15483,    6471,    1806,    22705,    25019,    16442,    5145,    15593,    23867,    23738,    14086,    23123,]
// paddedMinuends are the values xor'd with the value in address 1// the results are then subtracted from each memory location 2 through 39 let paddedMinuends: [Int16] = [    -27179,    -14018,    -22549,    -27735,    -225,    -15190,    -8339,    -1415,    -12768,    -6243,    -18725,    -13743,    -7402,    -4444,    -22495,    -12017,    -16138,    -22234,    -20283,    -5054,    -22161,    -22641,    -16096,    -4238,    -26510,    -13059,    -5726,    -2182,    -22211,    -28099,    -20296,    -7012,    -12961,    -21059,    -21210,    -14493,    -21817,]
let result = (Int16.min...Int16.max).map { pad -> [UInt16] in    // pad is the input value at address 1    // try every possible value for pad    // perform the same calculation as the QFT machine    // final[i] = paddedMinuend[i] ^ pad - subtrahend[i]    zip(subtrahends, paddedMinuends).map { subtrahend, paddedMinuend in        let minuend = paddedMinuend ^ pad        return UInt16(bitPattern:minuend &- subtrahend)    }}.filter { result in    // filter only those which produce only single-byte results    !result.contains { value in         value > UInt8.max    }}.compactMap { result -> String? in    // convert to string (discarding any which are not valid ASCII)    let bytes = result.map { short in UInt8(short) }    return String(bytes: bytes, encoding: .ascii)}.first { string in    // find the flag, which we know starts with "OOO"    string.hasPrefix("OOO")}
print(result ?? "No solution")```