// UNSOLVED SUBTASK 1 (10 pts)
// UNSOLVED SUBTASK 2 (11 pts)
// UNSOLVED SUBTASK 3 (11 pts)
// UNSOLVED SUBTASK 4 (15 pts)
// UNSOLVED SUBTASK 5 (12 pts)
// UNSOLVED SUBTASK 6 (08 pts)
// UNSOLVED SUBTASK 7 (14 pts)
// UNSOLVED SUBTASK 8 (19 pts)
// [+-+]----------------------
// TOTAL 0/100 pts
#include "vision.h"
#include <algorithm>
#include <bitset>
#include <iostream>
const int BITS = 8;
int ic = 0;
int HEIGHT = -1;
int WIDTH = -1;
int ZERO = -1;
int ONE = -1;
int pixelAt(int x, int y) {
return y * WIDTH + x;
}
std::vector<int> pixelRow(int y) {
std::vector<int> result;
for (int x = 0; x < WIDTH; ++x) {
result.push_back(y * WIDTH + x);
}
return result;
}
std::vector<int> pixelColumn(int x) {
std::vector<int> result;
for (int y = 0; y < HEIGHT; ++y) {
result.push_back(y * WIDTH + x);
}
return result;
}
int resultOfInstruction(int instructionIndex) {
return instructionIndex + WIDTH * HEIGHT;
}
std::vector<int> vectorRange(int start, int size) {
std::vector<int> result;
result.reserve(size);
for (int i = start; i < start + size; ++i) {
result.push_back(i);
}
return result;
}
std::vector<int> add(const std::vector<std::vector<int>>& numbers, bool inputCarry, bool keepCarry) {
std::vector<int> output;
int carry;
switch (inputCarry) {
case false:
carry = ZERO;
break;
case true:
carry = ONE;
break;
}
for (int bit = BITS - 1; bit >= 0; --bit) {
std::vector<int> theseBits;
for (int num = 0; num < numbers.size(); ++num) {
theseBits.push_back(resultOfInstruction(numbers[num][bit]));
}
// vinxor
add_xor(theseBits); // ic
// sumxor
add_xor({resultOfInstruction(ic), carry}); // ic + 1
output.push_back(ic + 1);
// carry and vinxor
add_and({resultOfInstruction(ic), carry}); // ic + 2
// vinor
add_or(theseBits); // ic + 3
// not vinxor
add_not(resultOfInstruction(ic)); // ic + 4
// vinor and not vinxor
add_and({resultOfInstruction(ic + 3), resultOfInstruction(ic + 4)}); // ic + 5
// final or for carry
add_or({resultOfInstruction(ic + 2), resultOfInstruction(ic + 5)}); // ic + 6
carry = resultOfInstruction(ic + 6);
ic += 7;
}
if (keepCarry) {
output.push_back(ic - 1);
}
std::reverse(output.begin(), output.end());
return output;
}
void construct_network(int H, int W, int K) {
HEIGHT = H;
WIDTH = W;
add_and({0, 1, 2});
++ic;
add_not(H * WIDTH);
++ic;
ZERO = HEIGHT * WIDTH;
ONE = HEIGHT * WIDTH + 1;
// Permanent 0 in i[0] and permanent 1 in i[1]
for (int row = 0; row < HEIGHT; ++row) {
add_or(pixelRow(row));
++ic;
}
// i[2..HEIGHT+2] now contains the information for which rows
for (int col = 0; col < WIDTH; ++col) {
add_or(pixelColumn(col));
++ic;
}
// i[HEIGHT+2..HEIGHT+WIDTH+2] now contains the information for which cols
add_xor({resultOfInstruction(2)});
++ic;
for (int row = 1; row < HEIGHT; ++row) {
add_xor({resultOfInstruction(2 + row), resultOfInstruction(HEIGHT + WIDTH + 2 + row - 1)});
++ic;
}
// i[HEIGHT+WIDTH+2..2*HEIGHT+WIDTH+2] now contains the prefix xors for rows
// in particular, i[2*HEIGHT+WIDTH+1] now contains the parity of rows
add_not(resultOfInstruction(2 * HEIGHT + WIDTH + 1)); // i[2*HEIGHT+WIDTH+2]
++ic;
add_xor({resultOfInstruction(HEIGHT + 2)});
++ic;
for (int col = 1; col < WIDTH; ++col) {
add_xor({resultOfInstruction(2 + HEIGHT + col), resultOfInstruction(2 * HEIGHT + WIDTH + 3 + col - 1)});
++ic;
}
// i[2*HEIGHT+WIDTH+3..2*HEIGHT+2*WIDTH+3] now contains the prefix xors for cols
// in particular, i[2*HEIGHT+2*WIDTH+2] now contains the parity of cols
add_not(resultOfInstruction(2 * HEIGHT + 2 * WIDTH + 2)); // i[2*HEIGHT+2*WIDTH+3]
++ic;
for (int row = 0; row < HEIGHT; ++row) {
std::bitset<BITS> bits = row;
for (int i = BITS - 1; i >= 0; --i) {
switch (bits[i]) {
case false:
add_and({ZERO});
++ic;
break;
case true:
add_and({resultOfInstruction(2 + row), resultOfInstruction(2 * HEIGHT + WIDTH + 2)});
++ic;
break;
}
}
}
// i[2*HEIGHT + 2*WIDTH + 4 .. increment in 8 .. 10*HEIGHT + 2*WIDTH + 4] now contains binary of rows
for (int col = 0; col < WIDTH; ++col) {
std::bitset<BITS> bits = col;
for (int i = BITS - 1; i >= 0; --i) {
switch (bits[i]) {
case false:
add_and({ZERO});
++ic;
break;
case true:
add_and({ONE, resultOfInstruction(HEIGHT + 2 + col), resultOfInstruction(2 * HEIGHT + 2 * WIDTH + 3)});
++ic;
break;
}
}
}
// i[10*HEIGHT + 2*WIDTH + 4 .. increment in 8 .. 10*HEIGHT + 10*WIDTH + 4] now contains binary of cols
for (int row = 0; row < HEIGHT; ++row) {
add_and({resultOfInstruction(2 + row), resultOfInstruction(HEIGHT + WIDTH + 2 + row)});
++ic;
}
// i[10*HEIGHT + 10*WIDTH + 4 .. 11*HEIGHT + 10*WIDTH + 4] now contains exactly which row to flip
for (int col = 0; col < WIDTH; ++col) {
add_and({resultOfInstruction(HEIGHT + 2 + col), resultOfInstruction(2 * HEIGHT + WIDTH + 3 + col)});
++ic;
}
// i[11*HEIGHT + 10*WIDTH + 4 .. 11*HEIGHT + 11*WIDTH + 4] now contains exactly which col to flip
for (int row = 0; row < HEIGHT; ++row) {
int flippingBit = resultOfInstruction(10 * HEIGHT + 10 * WIDTH + 4 + row);
for (int bit = 0; bit < BITS; ++bit) {
add_xor({resultOfInstruction(2 * HEIGHT + 2 * WIDTH + 4 + row * BITS + bit), flippingBit});
++ic;
}
}
// i[11*HEIGHT + 11*WIDTH + 4 .. increment in 8 .. 19*HEIGHT + 11*WIDTH + 4] now contains binary row with one flipped
for (int col = 0; col < WIDTH; ++col) {
int flippingBit = resultOfInstruction(11 * HEIGHT + 10 * WIDTH + 4 + col);
for (int bit = 0; bit < BITS; ++bit) {
add_xor({resultOfInstruction(10 * HEIGHT + 2 * WIDTH + 4 + col * BITS + bit), flippingBit});
++ic;
}
}
// i[19*HEIGHT + 11*WIDTH + 4 .. increment in 8 .. 19*HEIGHT + 19*WIDTH + 4] now contains binary col with one flipped
std::vector<std::vector<int>> rowsInBinary;
for (int row = 0; row < HEIGHT; ++row) {
std::vector<int> inBinary;
for (int bit = 0; bit < BITS; ++bit) {
inBinary.push_back(11 * HEIGHT + 11 * WIDTH + 4 + row * BITS + bit);
}
rowsInBinary.push_back(inBinary);
}
std::vector<int> rowSum = add(rowsInBinary, true, false);
std::vector<std::vector<int>> colsInBinary;
for (int col = 0; col < WIDTH; ++col) {
std::vector<int> inBinary;
for (int bit = 0; bit < BITS; ++bit) {
inBinary.push_back(19 * HEIGHT + 11 * WIDTH + 4 + col * BITS + bit);
}
colsInBinary.push_back(inBinary);
}
std::vector<int> colSum = add(colsInBinary, true, false);
std::vector<int> finalSum = add({rowSum, colSum}, false, true); // 9 bit number
std::bitset<9> target = K;
for (int bit = 0; bit < 9; ++bit) {
switch (target[bit]) {
case false:
add_not(resultOfInstruction(finalSum[9 - 1 - bit]));
++ic;
break;
case true:
add_or({resultOfInstruction(finalSum[9 - 1 - bit])});
++ic;
break;
}
}
add_and(vectorRange(resultOfInstruction(ic - 9), 9));
++ic;
return;
}
