//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2018 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <random>
int stage = 0;
//------------------------------------------------------------------------------
/// ハッシュ値の計算に使用するランダムな64ビットの値。2^Bits(=1024)個。
/// 適度にランダムであれば何でもいいけど、mt19937_64 で生成してみる。
class Hash {
public:
static const int Bits = 10;
static uint64_t Table[1 << Bits];
public:
Hash() {
std::mt19937_64 rand;
for (int i = 0; i < 1 << Bits; i++) {
Table[i] = rand();
}
}
};
uint64_t Hash::Table[1 << Hash::Bits];
Hash RandomTableInitializer;
//------------------------------------------------------------------------------
/// 3次元ベクトル。
struct Vector3i {
public:
int X;
int Y;
int Z;
Vector3i() {
X = 0;
Y = 0;
Z = 0;
}
Vector3i(int x, int y, int z)
{
X = x;
Y = y;
Z = z;
}
int Weight() {
return X * Y * (Z + 10);
}
bool operator==(Vector3i rhs) {
if (X == rhs.X && Y == rhs.Y && Z == rhs.Z) {
return true;
}
else {
return false;
}
}
};
//------------------------------------------------------------------------------
/// 生地の位置とサイズ。
/// 生地は位置、サイズともに3次元ベクトルで表現する。
/// 位置のzはオーブンに入れる時間。
/// サイズのzは焼けるまでの所要時間。
/// これで、20*20*1000の箱詰め問題となる。
/// (同時に2つ焼けないので、2つ以上の位置のzが同じにならないように注意する必要がある)
struct Box {
public:
Vector3i Position;
Vector3i Size;
Box() {
}
Box(Vector3i position, Vector3i size) {
Position = position;
Size = size;
}
public:
/// 2つの生地が衝突しているかを判定する。
bool Collided(Box& target) {
if (Position.X + Size.X <= target.Position.X) {
return false;
}
if (target.Position.X + target.Size.X <= Position.X) {
return false;
}
if (Position.Y + Size.Y <= target.Position.Y) {
return false;
}
if (target.Position.Y + target.Size.Y <= Position.Y) {
return false;
}
if (Position.Z + Size.Z <= target.Position.Z) {
return false;
}
if (target.Position.Z + target.Size.Z <= Position.Z) {
return false;
}
return true;
}
bool operator==(Box& rhs) {
if (Position == rhs.Position && Size == rhs.Size) {
return true;
}
else {
return false;
}
}
/// この生地の位置とサイズのハッシュ値。
uint64_t GetHashCode() {
uint64_t hash = Position.X + (Position.Y << 5);
hash = Hash::Table[hash & ((1 << Hash::Bits) - 1)] ^ (hash >> Hash::Bits);
hash += Position.Z + 256;
hash = Hash::Table[hash & ((1 << Hash::Bits) - 1)] ^ (hash >> Hash::Bits);
hash += Size.X + (Size.Y << 5);
hash = Hash::Table[hash & ((1 << Hash::Bits) - 1)] ^ (hash >> Hash::Bits);
hash += Size.Z;
hash = Hash::Table[hash & ((1 << Hash::Bits) - 1)] ^ (hash >> Hash::Bits);
hash = Hash::Table[hash & ((1 << Hash::Bits) - 1)] ^ (hash >> Hash::Bits);
return hash;
}
};
//------------------------------------------------------------------------------
/// 時間経過も込みで管理するオーブン。
class Oven3D {
public:
static const int PieceCapacity = 100;
static const int ZMax = 2000;
hpc::Array<Box, PieceCapacity> Pieces;
/// 格納済みのBoxを配置の時間が早いものから順に並べたときのインデックス。
int ZOrders[PieceCapacity];
/// その時間に置く生地があるかどうか。(同時に2つ焼けないため)
bool Busy[ZMax];
uint64_t HashCode;
Oven3D()
{
for (int i = 0; i < ZMax; i++) {
Busy[i] = false;
}
HashCode = 0;
}
public:
/// 1ターン進める。
/// Position.Z から1引くだけ。
/// Position.Z が負のときは、前のターンまでに置いた生地。
/// Position.Z + Size.Z が 0 になると、焼き上がり。
void Update() {
for (int i = 0; i < Pieces.count(); i++) {
auto& piece = Pieces[ZOrders[i]];
HashCode ^= piece.GetHashCode();
if (piece.Position.Z + piece.Size.Z <= 0) {
RemoveAt(ZOrders[i]);
i--;
}
else {
int z = piece.Position.Z;
if (z >= 0) {
#if _DEBUG
HPC_ASSERT(Busy[z] == true);
#endif
Busy[z] = false;
}
piece.Position.Z--;
z--;
if (z >= 0) {
#if _DEBUG
HPC_ASSERT(Busy[z] == false);
#endif
Busy[z] = true;
}
HashCode ^= piece.GetHashCode();
}
}
}
/// 配置済みの生地との衝突判定。
bool Collided(Box& c) {
for (int i = 0; i < Pieces.count(); i++) {
if (Pieces[i].Collided(c)) {
return true;
}
}
return false;
}
/// オーブンに生地を追加する。
void Add(Box& c) {
#if _DEBUG
HPC_ASSERT(Busy[c.Position.Z] == false);
#endif
Busy[c.Position.Z] = true;
Pieces.add(c);
int count = Pieces.count();
ZOrders[count - 1] = count - 1;
for (int i = count - 1; i > 0; i--) {
if (Pieces[ZOrders[i]].Position.Z < Pieces[ZOrders[i - 1]].Position.Z) {
int t = ZOrders[i];
ZOrders[i] = ZOrders[i - 1];
ZOrders[i - 1] = t;
}
else {
break;
}
}
HashCode ^= c.GetHashCode();
}
/// オーブンから生地を取り除く。
void RemoveAt(int index) {
#if _DEBUG
HPC_ASSERT(index >= 0 && index < Count());
#endif
int z = Pieces[index].Position.Z;
if (z >= 0) {
#if _DEBUG
HPC_ASSERT(Busy[z] == true);
#endif
Busy[z] = false;
}
for (int i = 0; i < Pieces.count(); i++) {
if (ZOrders[i] == index) {
for (int j = i; j < Pieces.count() - 1; j++) {
ZOrders[j] = ZOrders[j + 1];
}
break;
}
}
for (int i = 0; i < Pieces.count(); i++) {
if (ZOrders[i] > index) {
ZOrders[i]--;
}
}
HashCode ^= Pieces[index].GetHashCode();
Pieces.erase(index);
}
int Count() {
return Pieces.count();
}
/// 指定したサイズの生地を置くことができる、最も小さいZを座標ごとに求める。
/// オーブンを3次元の箱と見立てて、配置しようとしている生地が入る場所を求める。
/// 戻り値は共有バッファ SharedZS に書き込まれる。
int SharedZS[hpc::Parameter::OvenHeight][hpc::Parameter::OvenWidth];
void CalcVacantZs(Vector3i size, bool zFirst) {
int sh = hpc::Parameter::OvenHeight + 1 - size.Y;
int sw = hpc::Parameter::OvenWidth + 1 - size.X;
int minZ = 0;
for (int i = 0; ; i++) {
if (Busy[i]) {
minZ++;
}
else {
break;
}
}
for (int i = 0; i < sh; i++) {
for (int j = 0; j < sw; j++) {
SharedZS[i][j] = minZ;
}
}
bool minZFound = false;
for (int pi = 0; pi < Pieces.count() && minZFound == false; pi++) {
auto& piece = Pieces[ZOrders[pi]];
int ymin = piece.Position.Y - size.Y + 1;
int ymax = piece.Position.Y + piece.Size.Y;
if (ymin < 0) {
ymin = 0;
}
if (ymax > sh) {
ymax = sh;
}
int xmin = piece.Position.X - size.X + 1;
int xmax = piece.Position.X + piece.Size.X;
if (xmin < 0) {
xmin = 0;
}
if (xmax > sw) {
xmax = sw;
}
for (int i = ymin; i < ymax; i++) {
for (int j = xmin; j < xmax; j++) {
if (SharedZS[i][j] + size.Z <= piece.Position.Z ||
piece.Position.Z + piece.Size.Z <= SharedZS[i][j]) {
if (zFirst) {
if (SharedZS[i][j] + size.Z <= piece.Position.Z) {
minZFound = true;
}
}
}
else {
SharedZS[i][j] = piece.Position.Z + piece.Size.Z;
while (Busy[SharedZS[i][j]]) {
SharedZS[i][j]++;
}
}
}
}
}
}
/// オーブンに配置されている生地全体のハッシュ値。
/// 各生地のハッシュ値をxorしたもの。
uint64_t GetHashCode() {
return HashCode;
}
void Dump() {
std::printf("----------------------------------------\n");
for (int i = 0; i < Pieces.count(); i++) {
std::printf("(%d, %d, %d), (%d, %d, %d)\n", Pieces[i].Position.X, Pieces[i].Position.Y, Pieces[i].Position.Z, Pieces[i].Size.X, Pieces[i].Size.Y, Pieces[i].Size.Z);
}
std::printf("----------------------------------------\n");
}
};
//------------------------------------------------------------------------------
/// Actionを13ビットの値で表現したもの。
struct CompactAction {
public:
static const int Wait = 8191;
static int FromXYPieceID(int x, int y, int pieceID) {
#if _DEBUG
HPC_ASSERT(x >= 0 && x < hpc::Parameter::OvenWidth);
HPC_ASSERT(y >= 0 && y < hpc::Parameter::OvenHeight);
HPC_ASSERT(pieceID >= 0 && pieceID < 2 * hpc::Parameter::CandidatePieceCount);
#endif
return ((y * hpc::Parameter::OvenWidth + x) << 4) | pieceID;
}
static int X(int image) {
return (image >> 4) % hpc::Parameter::OvenWidth;
}
static int Y(int image) {
return (image >> 4) / hpc::Parameter::OvenWidth;
}
static int PieceID(int image) {
return image & 15;
}
};
//------------------------------------------------------------------------------
/// 探索結果の値と、そのときの行動。
/// スコアは、小さい方がいいので、ペナルティという呼び方をする。
/// なお、ペナルティは、レーンで待機中の全ての生地を配置したときの、生地のペナルティの合計。
/// 生地のペナルティは、体積と、配置する時間(1ターン増えるごとに1増える)をかけた値。
struct SearchResult {
public:
int Penalty;
int CompactAction;
SearchResult(int penalty, int compactAction)
{
Penalty = penalty;
CompactAction = compactAction;
}
};
//------------------------------------------------------------------------------
/// 探索結果のキャッシュ。
/// Searchで探索した結果を保存しておく。
/// いわゆるDPのテーブルのようなものだが、全部のオーブンの状態を保存するメモリはないので、
/// オーブンのハッシュ値でキャッシュする。
/// オーブンのハッシュ値のうち、下位14ビットとその上の32ビットの合計46ビット、
/// および使用済み生地が一致するものは、同じノードとみなす。
/// (もしかしたら違うかもしれないけど、非常に確率が低いのと、探索を少し間違える
/// だけで、大きな問題はないと思うので気にしない)
/// ハッシュ値のうち、下位14ビットは、テーブルのどこに入るかで決まるので保存しない。
struct CacheNode {
public:
uint32_t MiniHash;
uint16_t Used;
uint16_t CompactAction;
int Value;
CacheNode() {
MiniHash = 0;
Used = 0;
CompactAction = 0;
Value = 0;
}
CacheNode(uint32_t miniHash, uint16_t used, uint16_t compactAction, int value) {
MiniHash = miniHash;
Used = used;
CompactAction = compactAction;
Value = value;
}
};
//------------------------------------------------------------------------------
/// 探索結果のキャッシュ。
/// ハッシュテーブルのサイズは2^14個(16384個)。
class Cache {
public:
static const int TagBitLength = 14;
static const int BlockCapacity = 200;
static hpc::Array<CacheNode, BlockCapacity> SearchResultCache[1 << TagBitLength];
static void AddResultCache(SearchResult result, uint64_t hash, int used) {
int tag = hash & ((1 << TagBitLength) - 1);
uint32_t miniHash = (uint32_t)(hash >> TagBitLength);
auto& cacheBlock = SearchResultCache[tag];
uint16_t used16 = (uint16_t)used;
for (int i = 0; i < cacheBlock.count(); i++) {
if (cacheBlock[i].MiniHash == miniHash && cacheBlock[i].Used == used16) {
if (cacheBlock[i].Value != result.Penalty ||
cacheBlock[i].CompactAction != result.CompactAction) {
#if _DEBUG
std::printf("Cache hash conflicts. %d, %08x\n", tag, miniHash);
HPC_ASSERT(false);
#endif
}
return;
}
}
if (cacheBlock.count() < BlockCapacity - 1) {
cacheBlock.add(CacheNode(miniHash, used16, (uint16_t)result.CompactAction, result.Penalty));
}
}
static CacheNode* FindResultCache(uint64_t hash, int used) {
int tag = hash & ((1 << TagBitLength) - 1);
uint32_t miniHash = (uint32_t)(hash >> TagBitLength);
auto& cacheBlock = SearchResultCache[tag];
uint16_t used16 = (uint16_t)used;
for (int i = 0; i < cacheBlock.count(); i++) {
if (cacheBlock[i].MiniHash == miniHash && cacheBlock[i].Used == used16) {
return &(cacheBlock[i]);
}
}
return nullptr;
}
};
hpc::Array<CacheNode, Cache::BlockCapacity> Cache::SearchResultCache[1 << Cache::TagBitLength];
//------------------------------------------------------------------------------
/// ソルバー。
class Solver {
public:
int Frame;
Oven3D CurrentOven;
Solver()
{
Frame = 0;
Box ceil(Vector3i(0, 0, hpc::Parameter::GameTurnLimit + 1), Vector3i(hpc::Parameter::OvenWidth, hpc::Parameter::OvenHeight, 1));
CurrentOven.Add(ceil);
}
public:
/// 指定した生地を置くべき位置。
/// なるべく早くおけるところを優先し、置くタイミングが同じなら、外周に近いところを優先する。
Box PutPos(Vector3i& piece) {
const int PenaltyMax = 100000000;
CurrentOven.CalcVacantZs(piece, true);
Box maxCol;
int minPenalty = PenaltyMax;
for (int i = 0; i < hpc::Parameter::OvenHeight + 1 - piece.Y; i++) {
for (int j = 0; j < hpc::Parameter::OvenWidth + 1 - piece.X; j++) {
int yDist = std::min(i, hpc::Parameter::OvenHeight - piece.Y - i);
int xDist = std::min(j, hpc::Parameter::OvenWidth - piece.X - j);
int penalty = xDist + yDist + std::min(xDist, yDist) * 100 + CurrentOven.SharedZS[i][j] * 10000;
if (penalty < minPenalty) {
minPenalty = penalty;
maxCol = Box(Vector3i(j, i, CurrentOven.SharedZS[i][j]), piece);
}
}
}
return maxCol;
}
/// オーブンのペナルティ。なるべく広く開いているものがペナルティが小さくなる。
/// その方が、将来、置く場所の選択肢が増えるため。
/// (ただし、これを入れてもあまり変わらないのと、処理時間がかかるので、今は使ってない)
int OvenPenalty() {
int sizex = 5;
int sizey = 5;
int sizez = 100;
int penalty = 0;
CurrentOven.CalcVacantZs(Vector3i(sizex, sizey, sizez), false);
for (int i = 0; i < hpc::Parameter::OvenHeight + 1 - sizey; i++) {
for (int j = 0; j < hpc::Parameter::OvenWidth + 1 - sizex; j++) {
penalty += CurrentOven.SharedZS[i][j];
}
}
return penalty;
}
/// 生地のペナルティ。
/// 生地の体積と、配置する時間(1ターン遅くなるごとに1増える)をかけた値。
/// つまり、大きいものを後に置くほどペナルティが大きくなる。
int PiecePenalty(Box piece) {
int s = piece.Position.Z * piece.Size.Z;
s *= piece.Size.X * piece.Size.Y;
return s;
}
/// 現在のオーブンに、残りの生地を全部置いたときのペナルティを求める。
/// 生地を置く場所は、その生地にとって最善の位置(なるべく早く置けて、なるべく端に近いところ)とする。
/// 置き方を決める順番をいろいろ変えてみて、最もペナルティの小さいものを採用する。
/// (置く順番ではなく、置く場所と時間を決める順番なので注意！)
/// usedの各ビットで、その生地をすでに置いているかどうかを示す。
/// depthは、探索の深さ。depthが2以上なら次に置く生地を残りの生地すべてで試す。
/// depthが1なら、残りの中から10個ぐらいで試す。
/// depthが0なら、残りの生地を大きいものから順に置いて試す。
/// countは残り個数。
/// limitは、ペナルティがこの値と等しい、または大きくなることが確定したときに、探索を中止する値。
/// そのときは、戻り値として、limitに等しい値、行動はWaitを返す。
SearchResult Search(hpc::Array<Vector3i, 2 * hpc::Parameter::CandidatePieceCount>& pieces,
int used,
int depth,
int count,
int limit
) {
// limitが0または負のときは、探索しなくてもいい。
if (limit <= 0) {
return SearchResult(limit, CompactAction::Wait);
}
// 計算済みのものがキャッシュされていたら、それを返す。
uint64_t hash = CurrentOven.GetHashCode();
CacheNode* cacheNode = Cache::FindResultCache(hash, used);
if (cacheNode != nullptr) {
return SearchResult(cacheNode->Value, cacheNode->CompactAction);
}
SearchResult minResult(limit, CompactAction::Wait);
for (int pi = 0; pi < pieces.count(); pi++) {
if (((used & (1 << pi))) != 0) {
continue;
}
auto& piece = pieces[pi];
Box p = PutPos(piece);
CurrentOven.Add(p);
int penalty;
if (count == 1) {
penalty = 0; // OvenPenalty();
penalty += PiecePenalty(p);
CurrentOven.RemoveAt(CurrentOven.Count() - 1);
if (penalty > limit) {
penalty = limit;
return SearchResult(penalty, CompactAction::Wait);
}
auto result = SearchResult(penalty, p.Position.Z == 0 ? CompactAction::FromXYPieceID(p.Position.X, p.Position.Y, pi) : CompactAction::Wait);
Cache::AddResultCache(result, hash, used);
return result;
}
else {
int lpenalty = PiecePenalty(p);
if (limit - lpenalty <= 0) {
CurrentOven.RemoveAt(CurrentOven.Count() - 1);
return SearchResult(limit, CompactAction::Wait);
}
SearchResult result = Search(pieces, (used | (1 << pi)), depth - 1, count - 1, minResult.Penalty - lpenalty);
result.Penalty += lpenalty;
CurrentOven.RemoveAt(CurrentOven.Count() - 1);
if (result.Penalty < minResult.Penalty) {
minResult = result;
if (p.Position.Z == 0) {
minResult.CompactAction = CompactAction::FromXYPieceID(p.Position.X, p.Position.Y, pi);
}
}
if (depth <= 0) {
Cache::AddResultCache(minResult, hash, used);
return minResult;
}
if (depth == 1 && pi >= 10) {
Cache::AddResultCache(minResult, hash, used);
return minResult;
}
}
}
Cache::AddResultCache(minResult, hash, used);
return minResult;
}
int NextAction(hpc::Array<Vector3i, 2 * hpc::Parameter::CandidatePieceCount>& pieces) {
Frame++;
for (int i = 0; i < 1 << Cache::TagBitLength; i++) {
Cache::SearchResultCache[i].clear();
}
CurrentOven.Update();
int pieceOrders[2 * hpc::Parameter::CandidatePieceCount];
for (int i = 0; i < 2 * hpc::Parameter::CandidatePieceCount; i++) {
pieceOrders[i] = i;
}
// 大きい生地ほど、早く配置を決められるように、並べ替え。
for (int i = 2 * hpc::Parameter::CandidatePieceCount - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (pieces[j].Weight() < pieces[j + 1].Weight()) {
auto t = pieces[j];
pieces[j] = pieces[j + 1];
pieces[j + 1] = t;
int to = pieceOrders[j];
pieceOrders[j] = pieceOrders[j + 1];
pieceOrders[j + 1] = to;
}
}
}
SearchResult result = Search(pieces, 0, 2, 2 * hpc::Parameter::CandidatePieceCount, 1000000000);
int a = result.CompactAction;
if (a != CompactAction::Wait) {
auto box = Box(Vector3i(CompactAction::X(a), CompactAction::Y(a), 0), pieces[CompactAction::PieceID(a)]);
CurrentOven.Add(box);
// 並びを元に戻す
int originalAction = CompactAction::FromXYPieceID(CompactAction::X(a), CompactAction::Y(a), pieceOrders[CompactAction::PieceID(a)]);
return originalAction;
}
else {
return a;
}
}
};
Solver* solver;
//------------------------------------------------------------------------------
namespace hpc {
//------------------------------------------------------------------------------
/// コンストラクタ。
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます。
Answer::Answer()
{
}
//------------------------------------------------------------------------------
/// デストラクタ。
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます。
Answer::~Answer()
{
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理。
/// @detail 各ステージに対する初期化処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
solver = new Solver();
}
//------------------------------------------------------------------------------
/// このターンでの行動を指定する。
/// @detail 希望する行動を Action の static 関数で生成して return してください。
/// 正常ではない行動を return した場合、何も起きません。
/// 詳細は Action のヘッダを参照してください。
/// @param aStage 現在のステージ。
Action Answer::decideNextAction(const Stage& aStage)
{
Array<Vector3i, 2 * Parameter::CandidatePieceCount> pieces;
for (int i = 0; i < 2; i++) {
auto laneType = i == 0 ? hpc::CandidateLaneType_Large : hpc::CandidateLaneType_Small;
for (int j = 0; j < Parameter::CandidatePieceCount; j++) {
auto& piece = aStage.candidateLane(laneType).pieces()[j];
pieces.add(Vector3i(piece.width(), piece.height(), piece.requiredHeatTurnCount() + 1));
}
}
int next = solver->NextAction(pieces);
if (next == CompactAction::Wait) {
return Action::Wait();
}
else {
int pieceID = CompactAction::PieceID(next);
auto laneType = pieceID / hpc::Parameter::CandidatePieceCount == 0 ? CandidateLaneType_Large : hpc::CandidateLaneType_Small;
int piece = pieceID % hpc::Parameter::CandidatePieceCount;
return Action::Put(laneType, piece, Vector2i(CompactAction::X(next), CompactAction::Y(next)));
}
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理。
/// @detail 各ステージに対する終了処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::finalize(const Stage& aStage)
{
delete solver;
stage++;
}
} // namespace
// EOF