// #include <boost/functional/hash/hash.hpp>
#include <deque>
#include <functional>
#include <type_traits>
#include <unordered_set>
#include <vector>
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
int board[5][4] = {
// 0 1 2 3
{ 1, 2, 2, 3, }, // 0
{ 1, 2, 2, 3, }, // 1
{ 4, 5, 5, 6, }, // 2
{ 4, 7, 8, 6, }, // 3
{ 9, 0, 0, 10 } }; // 4
struct Mask;
const int kRows = 5;
const int kColumns = 4;
const int kBlocks = 10;
enum class Shape // : int8_t
{
kInvalid,
kSingle,
kHorizon,
kVertical,
kSquare,
};
struct Block
{
Shape shape;
int left, top; // int8_t
Block()
: shape(Shape::kInvalid),
left(-1),
top(-1)
{
}
Block(Shape s, int left, int top)
: shape(s),
left(left),
top(top)
{
assert(shape != Shape::kInvalid);
assert(left >= 0 && left < kColumns);
assert(top >= 0 && top < kRows);
}
int bottom() const
{
const static int delta[] = { 0, 0, 0, 1, 1, };
assert(shape != Shape::kInvalid);
return top + delta[static_cast<int>(shape)];
}
int right() const
{
const static int delta[] = { 0, 0, 1, 0, 1, };
assert(shape != Shape::kInvalid);
return left + delta[static_cast<int>(shape)];
}
void mask(int8_t value, Mask* mask) const;
};
struct Mask
{
Mask()
{
bzero(board_, sizeof(board_));
}
bool operator==(const Mask& rhs) const
{
return memcmp(board_, rhs.board_, sizeof board_) == 0;
}
size_t hashValue() const
{
const int8_t* begin = board_[0];
// return boost::hash_range(begin, begin + sizeof(board_));
size_t ret = 0;
for (; begin != board_[0] + sizeof(board_); ++begin)
ret = 31*ret + *begin;
return ret;
}
void print() const
{
for (int i = 0; i < kRows; ++i)
{
for (int j = 0; j < kColumns; ++j)
{
printf(" %c", board_[i][j] + '0');
}
printf("\n");
}
}
void set(int8_t value, int y, int x)
{
assert(value > 0);
assert(x >= 0 && x < kColumns);
assert(y >= 0 && y < kRows);
assert(board_[y][x] == 0);
board_[y][x] = value;
}
bool empty(int y, int x) const
{
assert(x >= 0 && x < kColumns);
assert(y >= 0 && y < kRows);
return board_[y][x] == 0;
}
private:
int8_t board_[kRows][kColumns];
};
namespace std
{
template<> struct hash<Mask>
{
size_t operator()(const Mask& x) const
{
return x.hashValue();
}
};
}
inline void Block::mask(int8_t value, Mask* mask) const
{
mask->set(value, top, left);
switch (shape)
{
case Shape::kHorizon:
mask->set(value, top, left+1);
break;
case Shape::kVertical:
mask->set(value, top+1, left);
break;
case Shape::kSquare:
mask->set(value, top, left+1);
mask->set(value, top+1, left);
mask->set(value, top+1, left+1);
break;
default:
assert(shape == Shape::kSingle);
;
}
}
struct State
{
Mask toMask() const
{
Mask m;
for (int i = 0; i < kBlocks; ++i)
{
Block b = blocks_[i];
b.mask(static_cast<int>(b.shape), &m);
}
return m;
}
bool isSolved() const
{
// FIXME: magic number
Block square = blocks_[1];
assert(square.shape == Shape::kSquare);
return (square.left == 1 && square.top == 3);
}
template<typename FUNC>
void move(const FUNC& func) const
{
static_assert(std::is_convertible<FUNC, std::function<void(const State&)>>::value,
"func must be callable with a 'const State&' parameter.");
const Mask mask = toMask();
for (int i = 0; i < kBlocks; ++i)
{
Block b = blocks_[i];
if (b.top > 0 && mask.empty(b.top-1, b.left))
{
bool moveUp = false;
if (b.shape == Shape::kHorizon || b.shape == Shape::kSquare)
{
if (mask.empty(b.top-1, b.left+1))
moveUp = true;
}
else
moveUp = true;
if (moveUp)
{
State next = *this;
next.step++;
next.blocks_[i].top--;
func(next);
}
}
if (b.bottom() < kRows-1 && mask.empty(b.bottom()+1, b.left))
{
bool moveDown = false;
if (b.shape == Shape::kHorizon || b.shape == Shape::kSquare)
{
if (mask.empty(b.bottom()+1, b.left+1))
moveDown = true;
}
else
moveDown = true;
if (moveDown)
{
State next = *this;
next.step++;
next.blocks_[i].top++;
func(next);
}
}
if (b.left > 0 && mask.empty(b.top, b.left-1))
{
bool moveLeft = false;
if (b.shape == Shape::kVertical || b.shape == Shape::kSquare)
{
if (mask.empty(b.top+1, b.left-1))
moveLeft = true;
}
else
moveLeft = true;
if (moveLeft)
{
State next = *this;
next.step++;
next.blocks_[i].left--;
func(next);
}
}
if (b.right() < kColumns-1 && mask.empty(b.top, b.right()+1))
{
bool moveRight = false;
if (b.shape == Shape::kVertical || b.shape == Shape::kSquare)
{
if (mask.empty(b.top+1, b.right()+1))
moveRight = true;
}
else
moveRight = true;
if (moveRight)
{
State next = *this;
next.step++;
next.blocks_[i].left++;
func(next);
}
}
}
}
// std::vector<State> moves() const;
Block blocks_[kBlocks];
int step = 0;
};
int main()
{
printf("sizeof(Mask) = %zd, sizeof(State) = %zd\n", sizeof(Mask), sizeof(State));
std::unordered_set<Mask> seen;
std::deque<State> queue;
State initial;
initial.blocks_[0] = Block(Shape::kVertical, 0, 0);
initial.blocks_[1] = Block(Shape::kSquare, 1, 0);
initial.blocks_[2] = Block(Shape::kVertical, 3, 0);
initial.blocks_[3] = Block(Shape::kVertical, 0, 2);
initial.blocks_[4] = Block(Shape::kHorizon, 1, 2);
initial.blocks_[5] = Block(Shape::kVertical, 3, 2);
initial.blocks_[6] = Block(Shape::kSingle, 1, 3);
initial.blocks_[7] = Block(Shape::kSingle, 2, 3);
initial.blocks_[8] = Block(Shape::kSingle, 0, 4);
initial.blocks_[9] = Block(Shape::kSingle, 3, 4);
queue.push_back(initial);
seen.insert(initial.toMask());
while (!queue.empty())
{
const State curr = queue.front();
queue.pop_front();
if (curr.isSolved())
{
printf("found solution with %d steps\n", curr.step);
break;
}
else if (curr.step > 200)
{
printf("too many steps.\n");
break;
}
curr.move([&seen, &queue](const State& next) {
auto result = seen.insert(next.toMask());
if (result.second)
queue.push_back(next);
});
// for (const State& next : curr.moves())
// {
// auto result = seen.insert(next.toMask());
// if (result.second)
// queue.push_back(next);
// }
}
}
Ly8gI2luY2x1ZGUgPGJvb3N0L2Z1bmN0aW9uYWwvaGFzaC9oYXNoLmhwcD4KCiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDx0eXBlX3RyYWl0cz4KI2luY2x1ZGUgPHVub3JkZXJlZF9zZXQ+CiNpbmNsdWRlIDx2ZWN0b3I+CgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiNpbmNsdWRlIDxzdGRkZWYuaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0cmluZ3MuaD4KCmludCBib2FyZFs1XVs0XSA9IHsKLy8gIDAgIDEgIDIgIDMKICB7IDEsIDIsIDIsIDMsIH0sICAgLy8gMAogIHsgMSwgMiwgMiwgMywgfSwgICAvLyAxCiAgeyA0LCA1LCA1LCA2LCB9LCAgIC8vIDIKICB7IDQsIDcsIDgsIDYsIH0sICAgLy8gMwogIHsgOSwgMCwgMCwgMTAgfSB9OyAvLyA0CgpzdHJ1Y3QgTWFzazsKCmNvbnN0IGludCBrUm93cyA9IDU7CmNvbnN0IGludCBrQ29sdW1ucyA9IDQ7CmNvbnN0IGludCBrQmxvY2tzID0gMTA7CgplbnVtIGNsYXNzIFNoYXBlIC8vIDogaW50OF90CnsKICBrSW52YWxpZCwKICBrU2luZ2xlLAogIGtIb3Jpem9uLAogIGtWZXJ0aWNhbCwKICBrU3F1YXJlLAp9OwoKc3RydWN0IEJsb2NrCnsKICBTaGFwZSBzaGFwZTsKICBpbnQgbGVmdCwgdG9wOyAgLy8gaW50OF90CgogIEJsb2NrKCkKICAgIDogc2hhcGUoU2hhcGU6OmtJbnZhbGlkKSwKICAgICAgbGVmdCgtMSksCiAgICAgIHRvcCgtMSkKICB7CiAgfQoKICBCbG9jayhTaGFwZSBzLCBpbnQgbGVmdCwgaW50IHRvcCkKICAgIDogc2hhcGUocyksCiAgICAgIGxlZnQobGVmdCksCiAgICAgIHRvcCh0b3ApCiAgewogICAgYXNzZXJ0KHNoYXBlICE9IFNoYXBlOjprSW52YWxpZCk7CiAgICBhc3NlcnQobGVmdCA+PSAwICYmIGxlZnQgPCBrQ29sdW1ucyk7CiAgICBhc3NlcnQodG9wID49IDAgJiYgdG9wIDwga1Jvd3MpOwogIH0KCiAgaW50IGJvdHRvbSgpIGNvbnN0CiAgewogICAgY29uc3Qgc3RhdGljIGludCBkZWx0YVtdID0geyAwLCAwLCAwLCAxLCAxLCB9OwogICAgYXNzZXJ0KHNoYXBlICE9IFNoYXBlOjprSW52YWxpZCk7CiAgICByZXR1cm4gdG9wICsgZGVsdGFbc3RhdGljX2Nhc3Q8aW50PihzaGFwZSldOwogIH0KCiAgaW50IHJpZ2h0KCkgY29uc3QKICB7CiAgICBjb25zdCBzdGF0aWMgaW50IGRlbHRhW10gPSB7IDAsIDAsIDEsIDAsIDEsIH07CiAgICBhc3NlcnQoc2hhcGUgIT0gU2hhcGU6OmtJbnZhbGlkKTsKICAgIHJldHVybiBsZWZ0ICsgZGVsdGFbc3RhdGljX2Nhc3Q8aW50PihzaGFwZSldOwogIH0KCiAgdm9pZCBtYXNrKGludDhfdCB2YWx1ZSwgTWFzayogbWFzaykgY29uc3Q7Cn07CgpzdHJ1Y3QgTWFzawp7CiAgTWFzaygpCiAgewogICAgYnplcm8oYm9hcmRfLCBzaXplb2YoYm9hcmRfKSk7CiAgfQoKICBib29sIG9wZXJhdG9yPT0oY29uc3QgTWFzayYgcmhzKSBjb25zdAogIHsKICAgIHJldHVybiBtZW1jbXAoYm9hcmRfLCByaHMuYm9hcmRfLCBzaXplb2YgYm9hcmRfKSA9PSAwOwogIH0KCiAgc2l6ZV90IGhhc2hWYWx1ZSgpIGNvbnN0CiAgewogICAgY29uc3QgaW50OF90KiBiZWdpbiA9IGJvYXJkX1swXTsKICAgIC8vIHJldHVybiBib29zdDo6aGFzaF9yYW5nZShiZWdpbiwgYmVnaW4gKyBzaXplb2YoYm9hcmRfKSk7CiAgICBzaXplX3QgcmV0ID0gMDsKICAgIGZvciAoOyBiZWdpbiAhPSBib2FyZF9bMF0gKyBzaXplb2YoYm9hcmRfKTsgKytiZWdpbikKICAgICAgcmV0ID0gMzEqcmV0ICsgKmJlZ2luOwogICAgcmV0dXJuIHJldDsKICB9CgogIHZvaWQgcHJpbnQoKSBjb25zdAogIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwga1Jvd3M7ICsraSkKICAgIHsKICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBrQ29sdW1uczsgKytqKQogICAgICB7CiAgICAgICAgcHJpbnRmKCIgJWMiLCBib2FyZF9baV1bal0gKyAnMCcpOwogICAgICB9CiAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICB9CgogIHZvaWQgc2V0KGludDhfdCB2YWx1ZSwgaW50IHksIGludCB4KQogIHsKICAgIGFzc2VydCh2YWx1ZSA+IDApOwogICAgYXNzZXJ0KHggPj0gMCAmJiB4IDwga0NvbHVtbnMpOwogICAgYXNzZXJ0KHkgPj0gMCAmJiB5IDwga1Jvd3MpOwogICAgYXNzZXJ0KGJvYXJkX1t5XVt4XSA9PSAwKTsKICAgIGJvYXJkX1t5XVt4XSA9IHZhbHVlOwogIH0KCiAgYm9vbCBlbXB0eShpbnQgeSwgaW50IHgpIGNvbnN0CiAgewogICAgYXNzZXJ0KHggPj0gMCAmJiB4IDwga0NvbHVtbnMpOwogICAgYXNzZXJ0KHkgPj0gMCAmJiB5IDwga1Jvd3MpOwogICAgcmV0dXJuIGJvYXJkX1t5XVt4XSA9PSAwOwogIH0KCiBwcml2YXRlOgogIGludDhfdCBib2FyZF9ba1Jvd3NdW2tDb2x1bW5zXTsKfTsKCm5hbWVzcGFjZSBzdGQKewogIHRlbXBsYXRlPD4gc3RydWN0IGhhc2g8TWFzaz4KICB7CiAgICBzaXplX3Qgb3BlcmF0b3IoKShjb25zdCBNYXNrJiB4KSBjb25zdAogICAgewogICAgICByZXR1cm4geC5oYXNoVmFsdWUoKTsKICAgIH0KICB9Owp9CgppbmxpbmUgdm9pZCBCbG9jazo6bWFzayhpbnQ4X3QgdmFsdWUsIE1hc2sqIG1hc2spIGNvbnN0CnsKICBtYXNrLT5zZXQodmFsdWUsIHRvcCwgbGVmdCk7CiAgc3dpdGNoIChzaGFwZSkKICB7CiAgICBjYXNlIFNoYXBlOjprSG9yaXpvbjoKICAgICAgbWFzay0+c2V0KHZhbHVlLCB0b3AsIGxlZnQrMSk7CiAgICAgIGJyZWFrOwogICAgY2FzZSBTaGFwZTo6a1ZlcnRpY2FsOgogICAgICBtYXNrLT5zZXQodmFsdWUsIHRvcCsxLCBsZWZ0KTsKICAgICAgYnJlYWs7CiAgICBjYXNlIFNoYXBlOjprU3F1YXJlOgogICAgICBtYXNrLT5zZXQodmFsdWUsIHRvcCwgbGVmdCsxKTsKICAgICAgbWFzay0+c2V0KHZhbHVlLCB0b3ArMSwgbGVmdCk7CiAgICAgIG1hc2stPnNldCh2YWx1ZSwgdG9wKzEsIGxlZnQrMSk7CiAgICAgIGJyZWFrOwogICAgZGVmYXVsdDoKICAgICAgYXNzZXJ0KHNoYXBlID09IFNoYXBlOjprU2luZ2xlKTsKICAgICAgOwogIH0KfQoKc3RydWN0IFN0YXRlCnsKICBNYXNrIHRvTWFzaygpIGNvbnN0CiAgewogICAgTWFzayBtOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBrQmxvY2tzOyArK2kpCiAgICB7CiAgICAgIEJsb2NrIGIgPSBibG9ja3NfW2ldOwogICAgICBiLm1hc2soc3RhdGljX2Nhc3Q8aW50PihiLnNoYXBlKSwgJm0pOwogICAgfQogICAgcmV0dXJuIG07CiAgfQoKICBib29sIGlzU29sdmVkKCkgY29uc3QKICB7CiAgICAvLyBGSVhNRTogbWFnaWMgbnVtYmVyCiAgICBCbG9jayBzcXVhcmUgPSBibG9ja3NfWzFdOwogICAgYXNzZXJ0KHNxdWFyZS5zaGFwZSA9PSBTaGFwZTo6a1NxdWFyZSk7CiAgICByZXR1cm4gKHNxdWFyZS5sZWZ0ID09IDEgJiYgc3F1YXJlLnRvcCA9PSAzKTsKICB9CgogIHRlbXBsYXRlPHR5cGVuYW1lIEZVTkM+CiAgdm9pZCBtb3ZlKGNvbnN0IEZVTkMmIGZ1bmMpIGNvbnN0CiAgewogICAgc3RhdGljX2Fzc2VydChzdGQ6OmlzX2NvbnZlcnRpYmxlPEZVTkMsIHN0ZDo6ZnVuY3Rpb248dm9pZChjb25zdCBTdGF0ZSYpPj46OnZhbHVlLAogICAgICAgICAgICAgICAgICAiZnVuYyBtdXN0IGJlIGNhbGxhYmxlIHdpdGggYSAnY29uc3QgU3RhdGUmJyBwYXJhbWV0ZXIuIik7CiAgICBjb25zdCBNYXNrIG1hc2sgPSB0b01hc2soKTsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IGtCbG9ja3M7ICsraSkKICAgIHsKICAgICAgQmxvY2sgYiA9IGJsb2Nrc19baV07CiAgICAgIGlmIChiLnRvcCA+IDAgJiYgbWFzay5lbXB0eShiLnRvcC0xLCBiLmxlZnQpKQogICAgICB7CiAgICAgICAgYm9vbCBtb3ZlVXAgPSBmYWxzZTsKICAgICAgICBpZiAoYi5zaGFwZSA9PSBTaGFwZTo6a0hvcml6b24gfHwgYi5zaGFwZSA9PSBTaGFwZTo6a1NxdWFyZSkKICAgICAgICB7CiAgICAgICAgICBpZiAobWFzay5lbXB0eShiLnRvcC0xLCBiLmxlZnQrMSkpCiAgICAgICAgICAgIG1vdmVVcCA9IHRydWU7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICAgIG1vdmVVcCA9IHRydWU7CiAgICAgICAgaWYgKG1vdmVVcCkKICAgICAgICB7CiAgICAgICAgICBTdGF0ZSBuZXh0ID0gKnRoaXM7CiAgICAgICAgICBuZXh0LnN0ZXArKzsKICAgICAgICAgIG5leHQuYmxvY2tzX1tpXS50b3AtLTsKICAgICAgICAgIGZ1bmMobmV4dCk7CiAgICAgICAgfQogICAgICB9CgogICAgICBpZiAoYi5ib3R0b20oKSA8IGtSb3dzLTEgJiYgbWFzay5lbXB0eShiLmJvdHRvbSgpKzEsIGIubGVmdCkpCiAgICAgIHsKICAgICAgICBib29sIG1vdmVEb3duID0gZmFsc2U7CiAgICAgICAgaWYgKGIuc2hhcGUgPT0gU2hhcGU6OmtIb3Jpem9uIHx8IGIuc2hhcGUgPT0gU2hhcGU6OmtTcXVhcmUpCiAgICAgICAgewogICAgICAgICAgaWYgKG1hc2suZW1wdHkoYi5ib3R0b20oKSsxLCBiLmxlZnQrMSkpCiAgICAgICAgICAgIG1vdmVEb3duID0gdHJ1ZTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgICAgbW92ZURvd24gPSB0cnVlOwogICAgICAgIGlmIChtb3ZlRG93bikKICAgICAgICB7CiAgICAgICAgICBTdGF0ZSBuZXh0ID0gKnRoaXM7CiAgICAgICAgICBuZXh0LnN0ZXArKzsKICAgICAgICAgIG5leHQuYmxvY2tzX1tpXS50b3ArKzsKICAgICAgICAgIGZ1bmMobmV4dCk7CiAgICAgICAgfQogICAgICB9CgogICAgICBpZiAoYi5sZWZ0ID4gMCAmJiBtYXNrLmVtcHR5KGIudG9wLCBiLmxlZnQtMSkpCiAgICAgIHsKICAgICAgICBib29sIG1vdmVMZWZ0ID0gZmFsc2U7CiAgICAgICAgaWYgKGIuc2hhcGUgPT0gU2hhcGU6OmtWZXJ0aWNhbCB8fCBiLnNoYXBlID09IFNoYXBlOjprU3F1YXJlKQogICAgICAgIHsKICAgICAgICAgIGlmIChtYXNrLmVtcHR5KGIudG9wKzEsIGIubGVmdC0xKSkKICAgICAgICAgICAgbW92ZUxlZnQgPSB0cnVlOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgICBtb3ZlTGVmdCA9IHRydWU7CiAgICAgICAgaWYgKG1vdmVMZWZ0KQogICAgICAgIHsKICAgICAgICAgIFN0YXRlIG5leHQgPSAqdGhpczsKICAgICAgICAgIG5leHQuc3RlcCsrOwogICAgICAgICAgbmV4dC5ibG9ja3NfW2ldLmxlZnQtLTsKICAgICAgICAgIGZ1bmMobmV4dCk7CiAgICAgICAgfQogICAgICB9CgogICAgICBpZiAoYi5yaWdodCgpIDwga0NvbHVtbnMtMSAmJiBtYXNrLmVtcHR5KGIudG9wLCBiLnJpZ2h0KCkrMSkpCiAgICAgIHsKICAgICAgICBib29sIG1vdmVSaWdodCA9IGZhbHNlOwogICAgICAgIGlmIChiLnNoYXBlID09IFNoYXBlOjprVmVydGljYWwgfHwgYi5zaGFwZSA9PSBTaGFwZTo6a1NxdWFyZSkKICAgICAgICB7CiAgICAgICAgICBpZiAobWFzay5lbXB0eShiLnRvcCsxLCBiLnJpZ2h0KCkrMSkpCiAgICAgICAgICAgIG1vdmVSaWdodCA9IHRydWU7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICAgIG1vdmVSaWdodCA9IHRydWU7CiAgICAgICAgaWYgKG1vdmVSaWdodCkKICAgICAgICB7CiAgICAgICAgICBTdGF0ZSBuZXh0ID0gKnRoaXM7CiAgICAgICAgICBuZXh0LnN0ZXArKzsKICAgICAgICAgIG5leHQuYmxvY2tzX1tpXS5sZWZ0Kys7CiAgICAgICAgICBmdW5jKG5leHQpOwogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KCiAgLy8gc3RkOjp2ZWN0b3I8U3RhdGU+IG1vdmVzKCkgY29uc3Q7CgogIEJsb2NrIGJsb2Nrc19ba0Jsb2Nrc107CiAgaW50IHN0ZXAgPSAwOwp9OwoKaW50IG1haW4oKQp7CiAgcHJpbnRmKCJzaXplb2YoTWFzaykgPSAlemQsIHNpemVvZihTdGF0ZSkgPSAlemRcbiIsIHNpemVvZihNYXNrKSwgc2l6ZW9mKFN0YXRlKSk7CiAgc3RkOjp1bm9yZGVyZWRfc2V0PE1hc2s+IHNlZW47CiAgc3RkOjpkZXF1ZTxTdGF0ZT4gcXVldWU7CgogIFN0YXRlIGluaXRpYWw7CiAgaW5pdGlhbC5ibG9ja3NfWzBdID0gQmxvY2soU2hhcGU6OmtWZXJ0aWNhbCwgMCwgMCk7CiAgaW5pdGlhbC5ibG9ja3NfWzFdID0gQmxvY2soU2hhcGU6OmtTcXVhcmUsICAgMSwgMCk7CiAgaW5pdGlhbC5ibG9ja3NfWzJdID0gQmxvY2soU2hhcGU6OmtWZXJ0aWNhbCwgMywgMCk7CiAgaW5pdGlhbC5ibG9ja3NfWzNdID0gQmxvY2soU2hhcGU6OmtWZXJ0aWNhbCwgMCwgMik7CiAgaW5pdGlhbC5ibG9ja3NfWzRdID0gQmxvY2soU2hhcGU6OmtIb3Jpem9uLCAgMSwgMik7CiAgaW5pdGlhbC5ibG9ja3NfWzVdID0gQmxvY2soU2hhcGU6OmtWZXJ0aWNhbCwgMywgMik7CiAgaW5pdGlhbC5ibG9ja3NfWzZdID0gQmxvY2soU2hhcGU6OmtTaW5nbGUsIDEsIDMpOwogIGluaXRpYWwuYmxvY2tzX1s3XSA9IEJsb2NrKFNoYXBlOjprU2luZ2xlLCAyLCAzKTsKICBpbml0aWFsLmJsb2Nrc19bOF0gPSBCbG9jayhTaGFwZTo6a1NpbmdsZSwgMCwgNCk7CiAgaW5pdGlhbC5ibG9ja3NfWzldID0gQmxvY2soU2hhcGU6OmtTaW5nbGUsIDMsIDQpOwoKICBxdWV1ZS5wdXNoX2JhY2soaW5pdGlhbCk7CiAgc2Vlbi5pbnNlcnQoaW5pdGlhbC50b01hc2soKSk7CgogIHdoaWxlICghcXVldWUuZW1wdHkoKSkKICB7CiAgICBjb25zdCBTdGF0ZSBjdXJyID0gcXVldWUuZnJvbnQoKTsKICAgIHF1ZXVlLnBvcF9mcm9udCgpOwoKICAgIGlmIChjdXJyLmlzU29sdmVkKCkpCiAgICB7CiAgICAgIHByaW50ZigiZm91bmQgc29sdXRpb24gd2l0aCAlZCBzdGVwc1xuIiwgY3Vyci5zdGVwKTsKICAgICAgYnJlYWs7CiAgICB9CiAgICBlbHNlIGlmIChjdXJyLnN0ZXAgPiAyMDApCiAgICB7CiAgICAgIHByaW50ZigidG9vIG1hbnkgc3RlcHMuXG4iKTsKICAgICAgYnJlYWs7CiAgICB9CgogICAgY3Vyci5tb3ZlKFsmc2VlbiwgJnF1ZXVlXShjb25zdCBTdGF0ZSYgbmV4dCkgewogICAgICBhdXRvIHJlc3VsdCA9IHNlZW4uaW5zZXJ0KG5leHQudG9NYXNrKCkpOwogICAgICBpZiAocmVzdWx0LnNlY29uZCkKICAgICAgICBxdWV1ZS5wdXNoX2JhY2sobmV4dCk7CiAgICB9KTsKCiAgICAvLyBmb3IgKGNvbnN0IFN0YXRlJiBuZXh0IDogY3Vyci5tb3ZlcygpKQogICAgLy8gewogICAgLy8gICBhdXRvIHJlc3VsdCA9IHNlZW4uaW5zZXJ0KG5leHQudG9NYXNrKCkpOwogICAgLy8gICBpZiAocmVzdWx0LnNlY29uZCkKICAgIC8vICAgICBxdWV1ZS5wdXNoX2JhY2sobmV4dCk7CiAgICAvLyB9CiAgfQp9Cg==