1
$\begingroup$

The most recent challenge on Advent of Code involves constructing an image in a binary pixel array from a sequence of instructions:

  1. rect AxB, which sets all of the pixels in a rectangle A pixels wide by B tall at the top left corner of the array.
  2. rotate row y=A by B, which performs a circular rotation of row A by B pixels.
  3. rotate column x=A by B, which performs a circular rotation of column A.

As part of solving the problem, I produced the following image:

####..##...##..###...##..###..#..#.#...#.##...##..
#....#..#.#..#.#..#.#..#.#..#.#..#.#...##..#.#..#.
###..#..#.#..#.#..#.#....#..#.####..#.#.#..#.#..#.
#....#..#.####.###..#.##.###..#..#...#..####.#..#.
#....#..#.#..#.#.#..#..#.#....#..#...#..#..#.#..#.
####..##..#..#.#..#..###.#....#..#...#..#..#..##..

This got me wondering:

  • How is the inverse problem solved? i.e. given an image, what sequence of instructions generates that image?
  • Are there any images which cannot be created with this set of instructions?
  • Is there a polynomial-time algorithm to find a minimal sequence of instructions that generate a target image? That is, where there is no shorter set of instructions that generates the same image. If not, is there a polynomial-time algorithm for deciding if a given sequence of instructions is minimal?

I've done some Google searches but turned up nothing. I would appreciate any links to materials describing this or similar problems.

$\endgroup$
  • $\begingroup$ @D.W. I've already solved the challenge problem. Now I want to know how to solve the inverse problem - purely out of curiosity. Namely, given an image, how do I construct the sequence of instructions that generates the image. I have amended my question to make it clear that I'm interested in materials that describe the problem. Also, thanks for the hint about attacking smaller problems. $\endgroup$ – castle-bravo Dec 8 '16 at 20:57
  • $\begingroup$ @D.W. If a sequence of instructions is minimal/optimal, then there exists no shorter sequence of instructions that generates the same image. I'm wondering if there's a polynomial time algorithm for finding a minimal set of instructions, and failing that, if there's a polynomial time algorithm for deciding if a given sequence of instructions is itself minimal. $\endgroup$ – castle-bravo Dec 8 '16 at 23:19
  • $\begingroup$ Got it. For the 1D analogue of this problem, finding a minimal sequence of instructions seems feasible (doable in polynomial time). I don't know how to do it for your actual problem, though. $\endgroup$ – D.W. Dec 8 '16 at 23:24
  • $\begingroup$ @D.W. It's fun to think about! My first thought was that the instructions could be represented as a formal system, then theorems from within that system could be applied to simplify the naive sequence of instructions. It's also fun to think about what the system would be like with a few more instructions, for example if there was an instruction to reset pixels/bits in a rectangle... I'll post on here again if I'm able to come up with an algorithm for item 3. $\endgroup$ – castle-bravo Dec 8 '16 at 23:54
1
$\begingroup$

Yes. For every image, there exists some sequence of operations that generates that image.

I'll describe how to implement a set (x,y) operation, which sets the pixel in the xth row and yth column (and leaves all other pixels unchanged). It should be clear that you can construct any image you want by repeatedly applying this primitive.

Here's how to implement the "set (x,y)" operation using the 3 operations you gave us:

  1. Rotate column y upwards by x-1 positions, so that position (x,y) moves to position (x,1).

  2. Rotate row 1 leftwards by y-1 positions, so that position (x,1) moves to position (1,1).

  3. Set the pixel in the upper-left corner (the pixel at position (1,1)).

  4. Rotate row 1 rightwards by y-1 positions, so that position (1,1) moves back to (x,1).

  5. Rotate column y downwards by x-1 positions, so that position (x,1) moves to position (x,y).

It is easy to see that each of these 5 steps can be done using one of your three operations, and that afterwards, the pixel at (x,y) is set and all other pixels are left unchanged.

This shows that given a image with dimensions mxn, we can create it using at most 5mn operations. Of course, this sequence of operations probably isn't the shortest possible. I don't know whether there is an efficient algorithm to find the shortest sequence of operations to generate a target image.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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