Hanoi - Editorial

#include <algorithm>
#include <vector>
#include <deque>
#include <cstdlib>
#include <cassert>
#include "EasyBMP.h"
using namespace std;

RGBApixel Black;
RGBApixel White;

void initColors() {
    Black.Red = 0x0;
    Black.Blue = 0x0;
    Black.Green = 0x0;
    Black.Alpha = 0xFF;
    White.Red = 0xFF;
    White.Blue = 0xFF;
    White.Green = 0xFF;
    White.Alpha = 0xFF;
}

struct Point {
    int x;
    int y;
    Point() {
        x = 0;
        y = 0;
    }
    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

struct Rectangle {
    Point lowCorner;
    Point highCorner;
    Rectangle(Point a, Point b) {
        lowCorner = a;
        highCorner = b;
    }
    void fillInBMPwithColor(BMP& bmp, RGBApixel color) {
        for (int i = lowCorner.x; i < highCorner.x; i++) {
            for (int k = lowCorner.y; k < highCorner.y; k++) {
                bmp.SetPixel(i, k, color);
            }
        }
    }
};

void drawBorderedRectangleAtBmp(Rectangle rect, BMP& bmp) {
    rect.fillInBMPwithColor(bmp, Black);
    rect.highCorner = Point(rect.highCorner.x - 2, rect.highCorner.y - 2);
    rect.lowCorner = Point(rect.lowCorner.x + 2, rect.lowCorner.y + 2);
    rect.fillInBMPwithColor(bmp, White);
}

void clearBmp(BMP& bmp) {
    Rectangle(Point(0, 0), Point(bmp.TellWidth(), bmp.TellHeight())).fillInBMPwithColor(bmp, White);
}

int disks[50];

void drawHanoiTowers(BMP& bmp) {
    Rectangle tower(Point(0, 10), Point(20, bmp.TellHeight() - 10));
    int d = 0;
    for(int x = bmp.TellWidth() / 6; x < bmp.TellWidth(); x += bmp.TellWidth() / 3) {
        tower.lowCorner.x = x - 10;
        tower.highCorner.x = x + 10;
        tower.fillInBMPwithColor(bmp, Black);
        int start_disks = d;
        for ( ; d < 50 && disks[d] >= 0; d++) {

        }
        int end_disks = d;
        std::sort(disks + start_disks, disks + end_disks);
        std::reverse(disks + start_disks, disks + end_disks);
        int y = bmp.TellHeight() - 10;
        for (int k = start_disks; k < end_disks; k++) {
            int width = disks[k] * 2 + 20;
            Rectangle disk(Point(x - width, y - 6), Point(x + width, y + 6));
            y -= 10;
            // printf("%d %d %d %d\n", disk.lowCorner.x, disk.lowCorner.y, disk.highCorner.x, disk.highCorner.y);
            drawBorderedRectangleAtBmp(disk, bmp);
        }
        d++;
    }
}

void fillInputData() {
 for (int i = 0; i < 48; i++) {
    disks[i] = i;
 }
 disks[48] = -1;
 disks[49] = -2;
 for (int k = 0; k < 100; k++) {
    std::random_shuffle(disks, disks + 50);
 }
 // freopen("output.txt", "w", stdout);
 for (int i = 0; i < 51; i++) {
    printf("%d\n", disks[i]);
 }
}

class HanoiSolver {
private:
    int movementsRemaining;
    vector<int> tower[3];
    bool isDiskOnTower(int disk, const vector<int>& t) {
        for (auto i : t) {
            if (disk == i) {
                return true;
            }
        }
        return false;
    }
    int findDisk(int disk) {
        int ret = -1;
        for (int i = 0; i < 3; i++) {
            if(isDiskOnTower(disk, tower[i])) {
                ret = i;
                break;
            }
        }
        assert(ret != -1);
        return ret;
    }
    int otherTowerIndex(int a, int b) {
        return 3 - a - b;
    }
    void moveDiskFromTowerToTower(int a, int b) {
        printf("Move from %d to %d\n", a, b);
        assert(tower[a].size() > 0);
        assert(tower[b].size() == 0 || tower[a].back() < tower[b].back());
        int disk = tower[a].back();
        tower[a].pop_back();
        tower[b].push_back(disk);
        /*for (int k = 0; k < 3; k++){
           for (int i = 0; i < tower[k].size(); i++){
               printf("%d ", tower[k][i]);
           }
           printf("\n");
        }*/
        movementsRemaining--;
        if (movementsRemaining < 1) {
            exit(0);
        }
    }
    void solveNormalHanoi(int numberOfDisks, int origin, int dest) {
        if (numberOfDisks == 1) {
            moveDiskFromTowerToTower(origin, dest);
        } else {
            int other = otherTowerIndex(origin, dest);
            solveNormalHanoi(numberOfDisks - 1, origin, other);
            moveDiskFromTowerToTower(origin, dest);
            solveNormalHanoi(numberOfDisks - 1, other, dest);
        }
    }
    void moveAllEqualOrSmallerDisksToTower(int disk, int destTower) {
        int originTower = findDisk(disk);
        if (disk == 0) {
            if(originTower != destTower) {
                moveDiskFromTowerToTower(originTower, destTower);
            }
            return;
        }
        if (originTower == destTower) {
            return moveAllEqualOrSmallerDisksToTower(disk - 1, destTower);
        }
        int otherTower = otherTowerIndex(originTower, destTower);
        moveAllEqualOrSmallerDisksToTower(disk - 1, otherTower);
        moveDiskFromTowerToTower(originTower, destTower);
        solveNormalHanoi(disk, otherTower, destTower);
    }
public:
    void solveHanoi(const vector<int>& a, const vector<int>& b, const vector<int>& c, int dest) {
        movementsRemaining = 200;
        tower[0] = a;
        tower[1] = b;
        tower[2] = c;
        for (int i = 0; i < 3; i++) {
            sort(tower[i].begin(), tower[i].end());
            reverse(tower[i].begin(), tower[i].end());
        }
        moveAllEqualOrSmallerDisksToTower(a.size() + b.size() + c.size() - 1, dest);
        assert(tower[dest].size() == a.size() + b.size() + c.size());
    }

};

HanoiSolver solver;

void testSolver(int n) {
 vector<int> tower[3];
 for (int i = n - 1; i >= 0; i--) {
    int towerId = rand() % 3;
    tower[towerId].push_back(i);
 }
 for (int k = 0; k < 3; k++){
    for (int i = 0; i < tower[k].size(); i++){
        printf("%d ", tower[k][i]);
    }
    printf("\n");
 }
 solver.solveHanoi(tower[0], tower[1], tower[2], 0);
}

void solveBigCase() {
    vector<int> towers[3];
    int index = 0;
    for (int i = 0; i < 50; i++) {
        if (disks[i] < 0) {
            index++;
        } else {
            towers[index].push_back(disks[i]);
        }
    }
    solver.solveHanoi(towers[0], towers[1], towers[2], 1);
}

int main( int argc, char* argv[] )
{
    initColors();
 cout << endl
      << "Using EasyBMP Version " << _EasyBMP_Version_ << endl << endl
      << "Copyright (c) by the EasyBMP Project 2005-6" << endl
      << "WWW: http://easybmp.sourceforge.net" << endl << endl;

 BMP Output;
 Output.SetSize( 800 , 550 );
 Output.SetBitDepth( 24 );
 clearBmp(Output);
 fillInputData();
 drawHanoiTowers(Output);

 cout << "writing 24bpp ... " << endl;
 Output.WriteToFile( "output.bmp" );
 solveBigCase();
// testSolver(5);
 return 0;
}