Blog do projektu Open Source JavaHotel

niedziela, 25 marca 2018

Find missing number or numbers

Exercise
There is an exercise in Cracking the Code Interview.
Missing Two: You are given an array with all the numbers from 1 to N appearing exactly once,
except for one number that is missing. How can you find the missing number in O(N) time and
0( 1) space? What if there were two numbers missing?
The solution is quite simple, just sum up all numbers from 0 to N using well-known formula, then sum up all numbers in the table and the difference is the number missing.
In case of two numbers missing, this method gives back the sum of the numbers. So it is necessary to conduct additional calculation, for instance, to sum square of the numbers. This method we receive the sum of the squares of the missing number and after resolving quadratic formula, we come up with the numbers.
But this solution has a weak point. If the number is big enough, there is a risk of overflow and the whole calculation is wrong. The threshold is around the square root of the maximum value of the integer involved. For 32 bit integer, it is around 46341.
Alternative solution for one missing
The alternative solution for one number missing is to calculate the number of ones and zeros in a binary representation of all numbers and the same for the table with missing one. Comparing which bits are missing, we can reconstruct the number lost.
The C++ solution is available here. Only number of ones should be calculated.
It does not break the time and space complexity requirement. Although we have to enumerate through bits for every number, the loop is still constant, 32 for 32 integer. 32*N is still O(N). Also, we need additional space for storing the number of bits but it is also constant and keeps O(1).
Solution for two missing
A similar solution can be applied to two numbers missing but only the sum can be reconstructed. If the difference between ones for the whole sum and the table is 0, it means that both missing numbers have zeros at the position. If the difference is 2, we can assume ones. But if the difference is 1, it means a combination of one and zero. Unfortunately, we cannot assign them to the numbers. But in case of the sum, it is not important because addition is commutative so we can assign them as we like.
uint ReconstructMissingSum(ByteCounter &all) const {
   uint missing1 = 0;
   uint missing2 = 0;
   for (int i=BN-1; i>=0; i--) {
 missing1 <<= 1;
 missing2 <<= 1;
 if (all.one_sum[i] != one_sum[i]) missing1 += 1;
 // Sum have two ones at the position. Move the second 1 to the second number.
 // We are calculating the sum, the order does not matter
 if (all.one_sum[i] - one_sum[i] == 2) missing2 += 1;
 }
   // it is not the reconstruction of numbers but the sum only.
   return missing1 + missing2;
}
But, as above, we need an additional equation to extract the exact values of the numbers. The same method can be applied for squares of the numbers. Unfortunately, this solution falls under the curse of overflow. Maybe there is a method to improve it but I was unable to find it so far.

środa, 21 marca 2018

Civilization The Board Game, next version

Introduction
I deployed a new version of my computer implementation of  Civilization The Board Game. The implementation consists of three parts:
New features
  • Wonders of The World.
You can buy wonders and spend money on them. Unfortunately, the functionality of the wonders is not implemented yet, will be added later.
Wonders are displayed in the separate panel. 
No graphic is attached, only the first letter of the Wonder name is exposed. It would be difficult to prepare several dozens of different and meaningful images. Only in the background a symbol of Ancient, Medieval or Modern is added.
When the player piles up the stack of money big enough, is allowed to buy a wonder. Discount for discovering a proper technic is granted also.
One player put aside enough to buy Pyramids or Great Lighthouse. After selecting a wonder, a square where the wonder is to be positioned should be selected. If square already had a building or another wonder atop, the previous content will be replaced.
The wonder is built and the world is staring at it with mouth open.
Next step

  • Economy, coins gathering
  • Culture progress


niedziela, 18 marca 2018

Circus tower

Introduction
There is an exercise in "Cracking the coding interview", Circus Tower.

Circus Tower: A circus is designing a tower routine consisting of people standing atop one anoth­er's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
EXAMPLE
lnput(ht,wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom:
(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)
The solution is based on finding the longest subsequence.
Alternative solution
But I developed a very similar solution in term of the directed graph and the solution is to find the longest possible path in the graph. Usually, we want to find the shortest path but this time it is different.  Athletes in the circus are graph nodes and if an athlete can stand atop the weightier athlete then there is an edge from the second to the first.
The C++ code as Eclipse CDC project is available here.
The class Athlete describes a single person and class AthleteGraph describes the connection. The graph is represented as a two-dimensional adjacency matrix. If there is a connection from i to j, then graph[i][j] is true.
The algorithm is recursive.
Assume that we are at the node i, and there are several adjacent nodes to i :  i1,i2 ... i(n). We calculated recursively the longest paths for i1, i2 .. i(n). The longest path starting from i is i itself concatenated with the longest among paths for i1,i2 ... i(n).
Complexity
The most complex is the graph creation because we have to compare a person with every other person to detect edges. So the complexity is O(n squared). Having the graph built, the complexity is O(m), where m is the number of edges, every edge is visited only once.