The N Transmitters Problem

The Problem:
                 There is a one-dimensional road of infinite length, which extends from -∞ to +∞. There are "n' one-dimensional transistors placed on the road at various points. Each transistor emits a signal. For every transistor, the signal can be transmitted across a region "r" which may differ from transmitter to transmitter. Since the road is one-dimensional, by radius "r", we mean that the signal can be received up to "r" distance to its left and "r" distance to its right.
                 There is a group of one-dimensional beings that wish to stay on this one-dimensional road. A region on this road is said to be habitable if and only if it can get at least "k" signals from "k" different transmitters. Given the road and the transmitters and their signal radius and the value of "k", we need to find out all the regions that can be considered habitable.

Assumptions: 
                 1) There is no concept of signal strength in our world. A signal will have full strength up to its radius "r" and beyond that, it will have zero strength.
                 2) We have considered, without the loss of generality in the algorithm, the coordinates and the ranges of the transmitters to be purely integers. There will be no change in the algorithm in case we take them as floats, or doubles.
                 3) There will not be more than one transmitter on a point. If that is the case, the transmitter whose signal can travel farthest will be considered.

Brute Force Approach:
                The brute force approach would be to keep a set of each n transmitters and the regions to which each can provide signals. In this case, the required answer would be the intersection of any k sets of the n total sets just formed. The time complexity of this approach is O(ⁿC_k)

O(nLogn) Approach:

                 Algorithm Axiom: Solutions become much more efficient when the data is arranged in some particular order.
                Imagine us being a part of the one-dimensional world mentioned above. We have an infinite road in front of us. Beginning our search from somewhere in the middle is difficult because we do not know about the transmitters to our left and right. So we can make no sound decision about which direction to start looking for habitable regions in, If however, say, someone tells us that the region we are currently in is the left-most end of the range of the left-most transmitter, we know for a fact that there can be no habitable regions to our left. This makes our next step clear - to go to the right in the search of habitable regions.
                 Coming back to our algorithm, if we sort the input transmitters in the non-decreasing order of their coordinates. If we start from the first transmitter, we will traverse the list of transmitters in one direction, along with keeping a track of whether the region we are currently in habitable or not. The only question that now remains is how to keep track of habitable regions. It is impossible to keep a count of all the signals available at every point on the road, as there are infinite points.
                  Point to be noted: All habitable regions will begin from a transmitter's left-most signal limit and end at (possible another) transmitter's right-most signal limit.
                  Our task is simplified if we take into consideration the above point. To identify a region, we only require its start and end points, and these points will only be the let and right limits of some transmitters. Hence, instead of analyzing all points, we analyze only those points where a transmitters range ends or begins. There are maximum "2n" such points for "n" transmitters.

Algorithm NTransmitters (transmittersList, Integer k):
1) sortAscending(transmittersList) on their coordinates;

2) beginsEnds := list of all the left-limits and right-limits of all the transmitter signals;
3) Traverse only begin and end lists from beginsEnds[0]; //beginsEnds[0] will hold the left-most end of                                                                                           the road where a signal is being received. The                                                                                           traversal will not include all the points, just the                                                                                          "begin" and "end" points of the list.
4) If beginsEnds[i] = "begin":
               count := count+1
    Else:
               count := count-1   
5) If count >= k :
               output region as habitable; 

Following is a well-commented Java code for the above algorithm. The only other noteworthy thing is that we have maintained a TreeMap instead of the usual HashMap. TreeMap extends HashMap, but sorts the data on their key value. This is needed so that we start from the left-most begin point. (it will be the one with the least coordinate value). Also, we have maintained 2 separate lists of begin and end to optimize memory requirements, As always, anyone is free to ask any doubts or share any comments in the comments section.

                  


  

Pokemon AI Game In Python

Following is the link to the AI game which I developed a while back. Feel free to fork/like/share it or leave any comments.
The aim is to simulate the very well-known Pokemon battle between a Pokemon trainer(the computer agent) and the user. Using propositional and monotonic logic along with a combination of minimax tree with forward arc checking of level 2, the computer A.I will automatically calculate the next move which will help it win the battle.
                                           https://github.com/Tejash241/Pokemon-AI-Game

Zero Sum Game With Min-max Trees

What is a min-max game tree?
                 Every two-player game which is also zero-sum can be represented as a min-max tree wherein one player assumes the role of "max" and another is assumed to be "min". This type of assumption is ideal for zero-sum games because the best move for "max" will be the worst move for "min". Every zero-sum game has only one governing utility function that decides the "goodness" of a move for a player. If the value returned by that function for a move for max is 'a', then the value for the same move for min will be '-a' and vice versa. Thus, at any state of the game, the total utility value for both players is zero.
                We maintain a tree structure wherein the nodes of the tree represent the player's (either min or max) state, and the edges represent the move it takes to go from one such state to another.

The Nim game:
                 Since this was intended to be a lesson on min-max tree, we started with a simple game. Our implementation of the Nim game has one pile of 'x' number of stones, where 'x' is taken as an input to our program. Each player can pick up at most 2 stones (i.e either 1 stone or 2 stones). The player which picks up the last stone(s) loses i.e. the player for which there are no more stones left to pick wins. 

Our Implementation:
                   We keep a global static variable 'remStones' which holds the number of stones left in the pile. Since there are at most 2 possible moves (one wherein the player picks 1 stone and another wherein he picks 2), our GameNode data structure can have maximum 2 children (left and right). The left child signifies the state which occurs after the player picks 2 stones, and the right occurs after he picks 1 stone. The left child may be null (in case there is only 1 stone left), or both the children may be null. By linking nodes with its children, we indirectly maintain a tree in the memory space.
                   Remember that in the code, the program acts as the "max" player and the opposite person, whose moves will be inputs to the console during run-time acts as "min". Thus, inside the tree, every move is scored from our perspective i.e. if the move benefits us, we give it a high score. Also, the root node will always signify our(max's) turn. We use a simple utility function:
                    For every leaf node:
                                 if max wins:
                                          score +1 to that node
                                 else:
                                          score -1 to that node
                    We now also propagate the score to the parents and eventually to the entire tree. The method makeMove() takes the current node as input and makes the move that give a state with the highest score. Thus, as the game progresses, a subset of the tree is traversed along a particular path and at every max turn, we calculate the next move based on the utility function.

Below is a commented code of the same program. Any doubts/suggestions/comments are most welcome.