3 ms·

My current scores: Square: 0x07 cycles Checkerboard: 0x4C cycles 4 Squares: 0x09 cycles I will post my solutions in 24-48 hours.

by OMGWTF 11y ago

ekimekim 11y ago
Checkerboard: 0x24 cycles. http://imgur.com/C1UeEdn http://imgur.com/C1UeEdn (EDIT: 0x16, see below) My key insight was twofold: 1. If you start every thread at 0x00 and make the first N commands "THR @00", you get 2^(n+1)-1 threads running by the time your first thread exits the chain of THR commands. 2. You can use a single array MOV instruction to set a range of program counters, effectively causing every thread to jump to a set position. So in the first 5 cycles I start 31 threads, then my main thread drops into a loop where all it does is set every thread's position (including its own) to a start point every 2 cycles. Every single thread is now a 2-cycle loop with no JMP cycle spent to return to the start each time. Then I simply make 16 loops of: PIX counter color ADD counter 1 counter with color being one of two memory positions, which the main thread swaps out each loop. I initialize counter such that each thread is doing its own row of the output (0, 10, 20, etc). The leftover threads I don't actually want (but it's hard to fine tune the thread count, so I left them in), so they share the first thread's loop. The repeated actions are effectively a noop. Note that, due to space constraints, I use the unused 4th byte of each PIX instruction as the counter for that loop. Doing this got me to 0x24 cycles. I shaved a further 4 cycles by using the leftover space to add 4 more loops. These ones run vertically and operate on the last two columns (two threads doing one column together). By the time the row-moving threads have reached the 2nd last column, the column-moving threads have finished the last two columns, and so the program is finished 4 cycles earlier. I think I could get another 2-cycle saving if I fine-tuned the number of threads started, compressed everything down again and got another two column-moving threads. The bigger improvement is converting the whole thing to 1-cycle loops instead of 2-cycle, and having half the loops incrementing the counters and the other half doing PIX instructions. This might just be possible in the available space if I've run the numbers correctly, and would result in a total time of 0x14. EDIT: Did the latter: http://imgur.com/zD1Gw5H http://imgur.com/zD1Gw5H It came out to 0x16, as I failed to account for the extra time to spin up more threads.
- chipsy 11y ago
  I started optimizing by making separate increment/render threads with a buffer and copy, and then doubled it to 4 threads. It's currently at 0xDD cycles but I don't think I'm going to take it farther: http://i.imgur.com/sD5IAXP.png http://i.imgur.com/sD5IAXP.png The thread sync is pretty inefficient. It will need to incorporate some "tricky" techniques like what you've described to go faster.
- keely 11y ago
  Awwww this is great stuff. I would love to hear your thoughts on how the language could be changed/improved to make puzzles and optimizing even more fun.
  - ekimekim 11y ago
    The biggest thing for me is being able to save/load solutions. I ended up keeping multiple browser tabs open as I tried to tweak solutions / attempt different puzzles. As for the language itself, a MOD operation to go with the DIV operation is useful. bitwise AND / OR / NOT / XOR could be interesting. Something that would make threads a lot more versatile would be some way to have them behave differently from one another even when executing the same code. Perhaps a new instruction like JTI X Y: Jump if Thread Id (defined as 0xFF - location of program counter) is equal to Y Or much more versatile but harder to account for in opcodes: a new prefix #XX which behaves like @(XX + thread id). So you could, for example, write 0x42 to a per-thread slot in an array starting at 0xA0 by doing "MOV 042 #A0" For making the puzzles interesting: The problem is most shapes and images can simply be described in memory and subsequently brute-force PIXed in sequence. After the simplest puzzles, the trick is having images that do not fit easily in memory and require procedural description. Checkerboard is a good example here. What about something like fizzbuzz but described in colors (like this: http://imgur.com/RMEaKAg http://imgur.com/RMEaKAg)? Or tricky questions where a seemingly random image actually has a simple pattern (like this: http://imgur.com/TbTPZnh http://imgur.com/TbTPZnh (spoilers here: http://imgur.com/73De5QF http://imgur.com/73De5QF ))? Unfortunately you're very limited as there's no actual input; the program's exact output is always entirely known. Several people here have mentioned TIS-100: It's not the exact same thing as what you're doing, but it could be an interesting thing to compare with if you haven't played it yet. EDIT: Just for fun, my best time for that second puzzle I posted is 0x103.
OMGWTF 11y ago
Solution for square: spawn threads, distribute PIX instructions for each pixel evenly across threads. Checkerboard and 4 Squares: http://imgur.com/a/dJRhM http://imgur.com/a/dJRhM

My current scores: Square: 0x07 cycles Checkerboard: 0x4C cycles 4 Squares: 0x09 cycles I will post my solutions in 24-48 hours.

by OMGWTF 11y ago

My current scores: Square: 0x07 cycles Checkerboard: 0x4C cycles 4 Squares: 0x09 cycles I will post my solutions in 24-48 hours.

ekimekim 11y ago

Checkerboard: 0x24 cycles. http://imgur.com/C1UeEdn http://imgur.com/C1UeEdn (EDIT: 0x16, see below) My key insight was twofold: 1. If you start every thread at 0x00 and make the first N commands "THR @00", you get 2^(n+1)-1 threads running by the time your first thread exits the chain of THR commands. 2. You can use a single array MOV instruction to set a range of program counters, effectively causing every thread to jump to a set position. So in the first 5 cycles I start 31 threads, then my main thread drops into a loop where all it does is set every thread's position (including its own) to a start point every 2 cycles. Every single thread is now a 2-cycle loop with no JMP cycle spent to return to the start each time. Then I simply make 16 loops of: PIX counter color ADD counter 1 counter with color being one of two memory positions, which the main thread swaps out each loop. I initialize counter such that each thread is doing its own row of the output (0, 10, 20, etc). The leftover threads I don't actually want (but it's hard to fine tune the thread count, so I left them in), so they share the first thread's loop. The repeated actions are effectively a noop. Note that, due to space constraints, I use the unused 4th byte of each PIX instruction as the counter for that loop. Doing this got me to 0x24 cycles. I shaved a further 4 cycles by using the leftover space to add 4 more loops. These ones run vertically and operate on the last two columns (two threads doing one column together). By the time the row-moving threads have reached the 2nd last column, the column-moving threads have finished the last two columns, and so the program is finished 4 cycles earlier. I think I could get another 2-cycle saving if I fine-tuned the number of threads started, compressed everything down again and got another two column-moving threads. The bigger improvement is converting the whole thing to 1-cycle loops instead of 2-cycle, and having half the loops incrementing the counters and the other half doing PIX instructions. This might just be possible in the available space if I've run the numbers correctly, and would result in a total time of 0x14. EDIT: Did the latter: http://imgur.com/zD1Gw5H http://imgur.com/zD1Gw5H It came out to 0x16, as I failed to account for the extra time to spin up more threads.

chipsy 11y ago
I started optimizing by making separate increment/render threads with a buffer and copy, and then doubled it to 4 threads. It's currently at 0xDD cycles but I don't think I'm going to take it farther: http://i.imgur.com/sD5IAXP.png http://i.imgur.com/sD5IAXP.png The thread sync is pretty inefficient. It will need to incorporate some "tricky" techniques like what you've described to go faster.
keely 11y ago
Awwww this is great stuff. I would love to hear your thoughts on how the language could be changed/improved to make puzzles and optimizing even more fun.
- ekimekim 11y ago
  The biggest thing for me is being able to save/load solutions. I ended up keeping multiple browser tabs open as I tried to tweak solutions / attempt different puzzles. As for the language itself, a MOD operation to go with the DIV operation is useful. bitwise AND / OR / NOT / XOR could be interesting. Something that would make threads a lot more versatile would be some way to have them behave differently from one another even when executing the same code. Perhaps a new instruction like JTI X Y: Jump if Thread Id (defined as 0xFF - location of program counter) is equal to Y Or much more versatile but harder to account for in opcodes: a new prefix #XX which behaves like @(XX + thread id). So you could, for example, write 0x42 to a per-thread slot in an array starting at 0xA0 by doing "MOV 042 #A0" For making the puzzles interesting: The problem is most shapes and images can simply be described in memory and subsequently brute-force PIXed in sequence. After the simplest puzzles, the trick is having images that do not fit easily in memory and require procedural description. Checkerboard is a good example here. What about something like fizzbuzz but described in colors (like this: http://imgur.com/RMEaKAg http://imgur.com/RMEaKAg)? Or tricky questions where a seemingly random image actually has a simple pattern (like this: http://imgur.com/TbTPZnh http://imgur.com/TbTPZnh (spoilers here: http://imgur.com/73De5QF http://imgur.com/73De5QF ))? Unfortunately you're very limited as there's no actual input; the program's exact output is always entirely known. Several people here have mentioned TIS-100: It's not the exact same thing as what you're doing, but it could be an interesting thing to compare with if you haven't played it yet. EDIT: Just for fun, my best time for that second puzzle I posted is 0x103.

OMGWTF 11y ago

Solution for square: spawn threads, distribute PIX instructions for each pixel evenly across threads. Checkerboard and 4 Squares: http://imgur.com/a/dJRhM http://imgur.com/a/dJRhM