online advertising

Friday, December 4, 2015

LeetCode OJ - Game of Life

Problem: 

Please find the problem here.

Solution:

This is a relatively trivial programming exercise except we need to do it in-place. Technically, it isn't really in-place, it is just to leverage we used more spaces in the input representation than it would have to.

The key idea of the code involve carefully encoding the states.

0 represent it was dead
1 represent it was alive

and this encoding is dictated by the problem statement.

Now I have the freedom to choose the temp states, at minimal I need two temp states,

now_dead_was_live (?)
now_live_was_dead (?)

The encoding should be chosen to maximize computational speed for accessing its old state and new state. There could be multiple ways of doing that, but I chose to do this.

Step 1) Keep the LSB unchanged, so LSB represents old state

Now we can choose the second bit, notice if we do not want to change an array entry if the cell stay the same. then we cannot use the second bit to represent the new state, so we simply set the second bit on when it is changed, so overall, LSB is the old state, and second bit means change or not.

now_dead_was_live 3
now_live_was_dead 2

Last but not least, we need to map (1, 2) -> 1 and also (0, 3) -> 0. At a glance, seems no easy way. Here is the cleverness, if we look at the number + 1, then we find something interesting

0 + 1 -> 1 -> 001 need to map to 0
1 + 1 -> 2 -> 010 need to map to 1
2 + 1 -> 3 -> 011 need to map to 1
3 + 1 -> 4 -> 100 need to map to 0

See, it is simply the second bit of the binary representation, so we saved ourselves from doing conditionals in the mapping process.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/game-of-life/

#include "LEET_GAME_OF_LIFE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_GAME_OF_LIFE
{
    class Solution
    {
    public:
        void gameOfLife(vector<vector<int>>& board)
        {
            // Note the design of the NOW variant
            // the least significant bit indicate the old state, so we just read the LSB for old state
            const int DEAD = 0;
            const int LIVE = 1;
            const int NOW_LIVE_WAS_DEAD = 2;
            const int NOW_DEAD_WAS_LIVE = 3;

            int height = board.size();
            if (height == 0)
            {
                return;
            }
            int width = board[0].size();
            if (width == 0)
            {
                return;
            }
            for (int r = 0; r < height; r++)
            {
                for (int c = 0; c < width; c++)
                {
                    int living_neighbor_count = 0;
                    for (int rd = -1; rd <= 1; rd++)
                    {
                        for (int cd = -1; cd <= 1; cd++)
                        {
                            int nr = r + rd;
                            int nc = c + cd;
                            if (nr >= 0 && nr < height && nc >= 0 && nc < width)
                            {
                                if ((board[nr][nc] & 1) == 1)
                                {
                                    living_neighbor_count++;
                                }
                            }
                        }
                    }
                    if ((board[r][c] & 1) == 1)
                    {
                        // For living cell, we need to discount itself.
                        living_neighbor_count--;
                        if (living_neighbor_count < 2 || living_neighbor_count > 3)
                        {
                            board[r][c] = NOW_DEAD_WAS_LIVE;
                        }
                    }
                    else
                    {
                        if (living_neighbor_count == 3)
                        {
                            board[r][c] = NOW_LIVE_WAS_DEAD;
                        }
                    }
                }
            }
            // Clear temp flags
            for (int r = 0; r < height; r++)
            {
                for (int c = 0; c < width; c++)
                {
                    // Now we need a function that maps
                    // DEAD (0) and NOW_DEAD_WAS_LIVE (3) to 0
                    // LIVE (1) and NOW_LIVE_WAS_DEAD (2) to 1
                    // The problem is easier if we look at the number + 1
                    // 0 + 1 = 1 (001) -> 0
                    // 3 + 1 = 4 (100) -> 0
                    // 1 + 1 = 2 (010) => 1
                    // 2 + 1 = 3 (011) => 1
                    // Note the answer is simply the second bit
                    board[r][c] = ((board[r][c] + 1) & 2) >> 1;
                }
            }
        }
    };
};

using namespace _LEET_GAME_OF_LIFE;

int LEET_GAME_OF_LIFE()
{
    Solution solution;
    vector<vector<int>> board;
    board.resize(3);
    board[0].push_back(1);    board[0].push_back(1); board[0].push_back(0);
    board[1].push_back(1);    board[1].push_back(1); board[1].push_back(0);
    board[2].push_back(1);    board[2].push_back(1); board[2].push_back(0);
    solution.gameOfLife(board);
    cout << board[0][0] << board[0][1] << board[0][2] << endl;
    cout << board[1][0] << board[1][1] << board[1][2] << endl;
    cout << board[2][0] << board[2][1] << board[2][2] << endl;
    return 0;
}

No comments :

Post a Comment