online advertising

Thursday, September 8, 2016

LeetCode OJ - Mini Parser

Problem:

Please find the problem here.

Analysis/Solution:

Top down recursive parsing, nothing special here.

The code is a bit messy as the requirement to handle negative number and empty brackets is discovered late, so I patched up the code instead of writing as separate grammar rules.

Not great, but it worked, so that's it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/mini-parser/

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

using namespace std;

namespace _LEET_MINI_PARSER
{
    // This is the interface that allows for creating nested lists.
    // You should not implement it, or speculate about its implementation
    class NestedInteger
    {
    public:
        // Constructor initializes an empty nested list.
        NestedInteger()
        {
            this->_isInteger = false;
        }

        // Constructor initializes a single integer.
        NestedInteger(int value)
        {
            this->_isInteger = true;
            this->value = value;
        }

        // Return true if this NestedInteger holds a single integer, rather than a nested list.
        bool isInteger() const
        {
            return this->_isInteger;
        }

        // Return the single integer that this NestedInteger holds, if it holds a single integer
        // The result is undefined if this NestedInteger holds a nested list
        int getInteger() const
        {
            return this->value;
        }

        // Set this NestedInteger to hold a single integer.
        void setInteger(int value)
        {
            this->value = value;
        }

        // Set this NestedInteger to hold a nested list and adds a nested integer to it.
        void add(const NestedInteger &ni)
        {
            this->list.push_back(ni);
        }

        // Return the nested list that this NestedInteger holds, if it holds a nested list
        // The result is undefined if this NestedInteger holds a single integer
        const vector<NestedInteger> &getList() const
        {
            return this->list;
        }

        const void ToString(stringstream& sout)
        {
            if (this->_isInteger)
            {
                sout << this->value;
            }
            else
            {
                sout << "[";
                bool first = true;
                for (auto&& n : this->list)
                {
                    if (first)
                    {
                        first = false;
                    }
                    else
                    {
                        sout << ",";
                    }
                    n.ToString(sout);
                }
                sout << "]";
            }
        }


    private:
        bool _isInteger;
        int value;
        vector<NestedInteger> list;
    };

    class Solution {
    public:
        NestedInteger deserialize(string s) {
            parser t(s);
            return t.ParseNestedInteger();
        }
    private:
        enum token_type
        {
            open_bracket,
            close_bracket,
            comma,
            integer,
        };
        class scanner
        {
        public:
            scanner(string& s) : m_s(s), m_position(0), m_negative(false) { }
            void scan()
            {
                char c = this->m_s[this->m_position++];
                if (c == '[')
                {
                    if (this->m_negative)
                    {
                        throw 3;
                    }
                    this->m_token_type = token_type::open_bracket;
                }
                else if (c == ']')
                {
                    if (this->m_negative)
                    {
                        throw 3;
                    }
                    this->m_token_type = token_type::close_bracket;
                }
                else if (c == ',')
                {
                    if (this->m_negative)
                    {
                        throw 3;
                    }
                    this->m_token_type = token_type::comma;
                }
                else if (c == '-')
                {
                    if (this->m_negative)
                    {
                        throw 3;
                    }
                    this->m_negative = true;
                    this->scan();
                }
                else if (c >= '0' && c <= '9')
                {
                    this->m_token_type = token_type::integer;
                    this->m_value = c - '0';
                    while (true)
                    {
                        c = this->m_s[this->m_position++];
                        if (c >= '0' && c <= '9')
                        {
                            this->m_value = this->m_value * 10 + c - '0';
                        }
                        else
                        {
                            break;
                        }
                    }

                    if (this->m_negative)
                    {
                        this->m_value = -1 * this->m_value;
                        this->m_negative = false;
                    }
                    this->m_position--;
                }
                else
                {
                    // The input is invalid!
                    throw 0;
                }
            }

            token_type get_token_type()
            {
                return this->m_token_type;
            }

            int get_token_value()
            {
                return this->m_value;
            }
        private:
            
            string& m_s;
            int m_position;
            token_type m_token_type;
            int m_value;
            bool m_negative;
        };
        class parser
        {
        public:
            parser(string& s) : m_scanner(s)
            {
                this->m_scanner.scan();
            }
            NestedInteger ParseNestedInteger()
            {
                if (this->m_scanner.get_token_type() == token_type::integer)
                {
                    return NestedInteger(this->m_scanner.get_token_value());
                }
                else if (this->m_scanner.get_token_type() == token_type::open_bracket)
                {
                    NestedInteger result;
                    while (true)
                    {
                        this->m_scanner.scan();
                        if (this->m_scanner.get_token_type() == token_type::close_bracket)
                        {
                            break;
                        }
                        result.add(this->ParseNestedInteger());
                        this->m_scanner.scan();
                        if (this->m_scanner.get_token_type() == token_type::close_bracket)
                        {
                            break;
                        }
                        else if (this->m_scanner.get_token_type() != token_type::comma)
                        {
                            // The input is invalid
                            throw 1;
                        }
                    }
                    return result;
                }
                else
                {
                    throw 2;
                }
            }
        private:
            scanner m_scanner;
        };
    };
};

using namespace _LEET_MINI_PARSER;

int LEET_MINI_PARSER()
{
    Solution solution;
    NestedInteger result = solution.deserialize("[-32,[]]");
    stringstream sout;
    result.ToString(sout);
    cout << sout.str() << endl;
    return 0;
}

LeetCode OJ - Perfect Rectangle (I)

Problem:

Please find the problem here.

Analysis:

This is a hard problem. I peeped at the discussion forum and I know other can do that in linear time, so I challenged myself to do that. The judge gives really large input, so naive/brute force method does not work.

The implementation I have is still not great, I knew there is a better solution presented in the discussion forum after I have done with my idea coding. But I wanted to present my idea anyway, since that is original, mine.

Solution:

The key idea of my presentation is that in order for all the rectangles to tile properly without overlap, all the left edges should be sticking with a corresponding right edges (except the bounding boxes, obviously). The correspondence could be partial (i.e. my left edge matches part of some right edge, or part of my left edge match with one or more right edges, ...), but the sum of them should all matches together. Similarly with the top edges matching bottom edges.

One could come up with a lot of criteria like this (i.e. sufficient conditions for the rectangle to tile), The key is that the criterion must be easy (i.e. linear time) to evaluate. The criterion above can be evaluated by mean of hash tables.

1) We can hash all left/right edges by their x coordinates, each x coordinate contains an edge set.
2) In an edge set, we can join the edges by their endpoint by hashing the edges by the endpoints.
3) Once we have gone through indexing them all, compare all the values in the hash table.

This allow us to check criterion in linear time. However, we are using too many hash tables here. The judge is unhappy with the amount of memory I consumed. Still, it is a linear time algorithm, so I am presenting this anyway.

Code:

#include "stdafx.h"

// https://leetcode.com/contest/2/problems/perfect-rectangle/

#include "LEET_PERFECT_RECTANGLE.h"
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PERFECT_RECTANGLE
{
    struct Range
    {
        Range(int from, int to)
        {
            this->from = from;
            this->to = to;
        }
        int from;
        int to;
    };

    class Ranges
    {
    public:
        Ranges(int from, int to)
        {
            Range* range = new Range(from, to);
            fromIndex.insert(make_pair(from, range));
            toIndex.insert(make_pair(to, range));
        }

        void add_range(int from, int to)
        {
            auto leftFind = toIndex.find(from);
            auto rightFind = fromIndex.find(to);
            if (leftFind != toIndex.end())
            {
                Range* leftRange = leftFind->second;
                fromIndex.erase(leftRange->from);
                toIndex.erase(leftRange->to);
                from = leftRange->from;
                delete leftRange;
            }
            if (rightFind != fromIndex.end())
            {
                Range* rightRange = rightFind->second;
                fromIndex.erase(rightRange->from);
                toIndex.erase(rightRange->to);
                to = rightRange->to;
                delete rightRange;
            }

            Range* range = new Range(from, to);
            fromIndex.insert(make_pair(from, range));
            toIndex.insert(make_pair(to, range));
        }

        unordered_map<int, Range*> fromIndex;
        unordered_map<int, Range*> toIndex;

    };

    void AddEdge(unordered_map<int, Ranges*>& allRanges, int key, int from, int to)
    {
        auto iter = allRanges.find(key);
        if (iter == allRanges.end())
        {
            Ranges* ranges = new Ranges(from, to);
            allRanges.insert(make_pair(key, ranges));
        }
        else
        {
            Ranges* ranges = iter->second;
            ranges->add_range(from, to);
        }
    }

    class Solution
    {
    public:
        int area(vector<int>& rectangle)
        {
            return (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
        }
        bool isRectangleCover(vector<vector<int>>& rectangles)
        {
            int total_area = 0;
            int min_x = rectangles[0][0];
            int min_y = rectangles[0][1];
            int max_x = rectangles[0][2];
            int max_y = rectangles[0][3];
            for (size_t i = 0; i < rectangles.size(); i++)
            {
                total_area += area(rectangles[i]);
                min_x = min(min_x, rectangles[i][0]);
                min_y = min(min_y, rectangles[i][1]);
                max_x = max(max_x, rectangles[i][2]);
                max_y = max(max_y, rectangles[i][3]);
            }
            int expected_area = (max_x - min_x) * (max_y - min_y);
            if (total_area != expected_area)
            {
                return false;
            }
            
            unordered_map<int, Ranges*> topEdges;
            unordered_map<int, Ranges*> bottomEdges;
            unordered_map<int, Ranges*> leftEdges;
            unordered_map<int, Ranges*> rightEdges;

            // Imagine the min box is actually adjacent to four big boxes (so all edges have their 'other' sides)
            topEdges.insert(make_pair(min_y, new Ranges(min_x, max_x)));
            bottomEdges.insert(make_pair(max_y, new Ranges(min_x, max_x)));
            rightEdges.insert(make_pair(min_x, new Ranges(min_y, max_y)));
            leftEdges.insert(make_pair(max_x, new Ranges(min_y, max_y)));

            for (size_t i = 0; i < rectangles.size(); i++)
            {
                int x1 = rectangles[i][0];
                int y1 = rectangles[i][1];
                int x2 = rectangles[i][2];
                int y2 = rectangles[i][3];
                AddEdge(topEdges, y2, x1, x2);
                AddEdge(bottomEdges, y1, x1, x2);
                AddEdge(leftEdges, x1, y1, y2);
                AddEdge(rightEdges, x2, y1, y2);
            }

            for (auto topEdgeKeyValuePair : topEdges)
            {
                auto topEdgeKey = topEdgeKeyValuePair.first;
                
                auto bottomEdgeIter = bottomEdges.find(topEdgeKey);
                if (bottomEdgeIter == bottomEdges.end())
                {
                    return false;
                }

                auto topEdgeRanges = topEdgeKeyValuePair.second;
                auto bottomEdgeRanges = bottomEdgeIter->second;

                if (topEdgeRanges->fromIndex.size() != bottomEdgeRanges->fromIndex.size())
                {
                    return false;
                }

                for (auto topEdgeRangeKeyValuePair : topEdgeRanges->fromIndex)
                {
                    auto& topEdgeRange = topEdgeRangeKeyValuePair.second;

                    auto bottomEdgeRange = bottomEdgeRanges->fromIndex.find(topEdgeRange->from);
                    if (bottomEdgeRange == bottomEdgeRanges->fromIndex.end())
                    {
                        return false;
                    }
                    else if (bottomEdgeRange->second->to != topEdgeRange->to)
                    {
                        return false;
                    }
                }
            }
            for (auto rightEdgeKeyValuePair : rightEdges)
            {
                auto rightEdgeKey = rightEdgeKeyValuePair.first;

                auto leftEdgeIter = leftEdges.find(rightEdgeKey);
                if (leftEdgeIter == leftEdges.end())
                {
                    return false;
                }

                auto rightEdgeRanges = rightEdgeKeyValuePair.second;
                auto leftEdgeRanges = leftEdgeIter->second;

                if (rightEdgeRanges->fromIndex.size() != leftEdgeRanges->fromIndex.size())
                {
                    return false;
                }

                for (auto rightEdgeRangeKeyValuePair : rightEdgeRanges->fromIndex)
                {
                    auto& rightEdgeRange = rightEdgeRangeKeyValuePair.second;

                    auto leftEdgeRange = leftEdgeRanges->fromIndex.find(rightEdgeRange->from);
                    if (leftEdgeRange == leftEdgeRanges->fromIndex.end())
                    {
                        return false;
                    }
                    else if (leftEdgeRange->second->to != rightEdgeRange->to)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    };
};

using namespace _LEET_PERFECT_RECTANGLE;

int LEET_PERFECT_RECTANGLE()
{
    // Better, but now the judge bitches on memory consumption
    // After all I am using linear memory, maybe we can get there with compact encoding
    Solution solution;
    int r[5][4] = { {1, 1, 3, 3},{3, 1, 4, 2},{3, 2, 4, 4},{1, 3, 2, 4},{2, 3, 3, 4} };
    vector<vector<int>> rectangles;
    rectangles.push_back(vector<int>(r[0], r[0] + 4));
    rectangles.push_back(vector<int>(r[1], r[1] + 4));
    rectangles.push_back(vector<int>(r[2], r[2] + 4));
    rectangles.push_back(vector<int>(r[3], r[3] + 4));
    rectangles.push_back(vector<int>(r[4], r[4] + 4));
    cout << solution.isRectangleCover(rectangles) << endl;
    return 0;
}

LeetCode OJ - Elimination Game

Problem:

Please find the problem here.

Analysis:

I experimented with the judge, it gives very big number as input (e.g. 10000000), therefore direct simulation of the game is not the way to go.

I have stuck for this problem for a good while, but a key observation saved me, by looking at the game in binary notation.

Suppose we are playing the game with input 9, here is how to elimination process go

First round

0001
0010
0011
0100
0101
0110
0111
1000
1001

The first round eliminate all the odd numbers, no surprise there, we already know. The key one is the next elimination, let's see:

0010
0100
0110
1000

The key observation here is that the second (least significant) bit of the crossed number is always 0. Think about it, it has to be, because we are now crossing every other one. Here is the last round.

0010
0110

This one is not obvious, but one can argue the third (least significant) bit of the crossed number must be 0.

Solution:

With that observation, now we can derive a solution. The first (least signficant) bit must be 0 because we crossed out all the odd numbers. The second (least signficant) bit must be 1 because we crossed out all the 0, and so on.

Therefore the key to the puzzle is to find out which bit is crossed out and output the other bit. To determine that, just find out the corresponding bit of the number that is crossed out first, to do that, all we need to do is to maintain the begin and the end to the array. With the begin and end, we can determine the corresponding bit in constant time, and therefore, we are constructing the solution in $ O(number of bits) $ time, that is bounded by $ O(\log n) $, much faster than direct simulation.

Note that in the code, to make it easy to code, I simply shifted away the least significant bits once I have done with computing that. This make it easy for me to extract the corresponding bit.

Code:

#include "stdafx.h"

// https://leetcode.com/contest/2/problems/elimination-game/

#include "LEET_ELIMINATION_GAME.h"
#include <stack>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

#include <stdio.h>

using namespace std;

namespace _LEET_ELIMINATION_GAME
{
    class Solution
    {
    public:
        int lastRemaining(int n)
        {
            return lastRemaining(1, n, 0);
        }

        int lastRemaining(int smallest, int largest, int round)
        {
            if (smallest == largest)
            {
                return smallest;
            }
            if (round % 2 == 0)
            {
                if (smallest % 2 == 0)
                {
                    // Eliminate all 0
                    smallest += 1;
                    if (largest % 2 == 0) { largest -= 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 1) * 2 + 1;
                }
                else
                {
                    // Eliminating all 1
                    smallest += 1;
                    if (largest % 2 == 1) { largest -= 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 1) * 2;
                }
            }
            else
            {
                if (largest % 2 == 0)
                {
                    // Eliminate all 0
                    largest -= round;
                    if (smallest % 2 == 0) { smallest += 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 0) * 2 + 1;
                }
                else
                {
                    // Eliminating all 1
                    largest -= round;
                    if (smallest % 2 == 1) { smallest += 1; }
                    return lastRemaining(smallest >> 1, largest >> 1, 0) * 2;
                }
            }
        }
    };
};

using namespace _LEET_ELIMINATION_GAME;

int LEET_ELIMINATION_GAME()
{
    Solution solution;
    cout << solution.lastRemaining(10000000) << endl;
    return 0;
}