Circular Dependency: An Anti-Pattern and Techniques to avoid it in object oriented Design

When I attempted to write my first object oriented program with some meaningful complexity I was hit by the problem of cyclic/circular dependency. As the name suggests the problem definition is very simple. If we need to design two classes which need to call functions of each other directly how do we accomplish that? And what are the issues we may land up into if we do not pay proper attention to avoid circular dependency among them. I am sure this problem would have come up with many other programmers like me. In this post I would like to get in depth of this problem and explain why its call an anti-pattern and what are possible approaches to avoid it.

Heap : A Data Structure for Efficient Programs

With exponential growth in computing capability of present day hardware as per Moore's law one can overlook the importance of efficient algorithms very easily. But efficient algorithm will always be critical as the complexity of programs running on today's efficient hardware has also increased with same pace if not more. 

Today people are dealing with huge social network graphs, or analysing twitter posts, or searching images, or solving any of the hundreds of problems in vogue. They would be wasting time without the fastest possible hardware. But if they use incorrect algorithms they would be sitting forever. Hence there is no substitute for an efficient algorithm.

Getting Started with SystemC-2.3

About systemC

SystemC is a set of C++ classes and macros which provide an event-driven simulation interface in C++. These facilities enable a designer to simulate concurrent processes, each described using plain C++ syntax. SystemC processes can communicate in a simulated real-time environment, using signals of all the datatypes offered by C++, some additional ones offered by the SystemC library, as well as user defined. In certain respects, SystemC deliberately mimics the hardware description languages VHDL and Verilog, but is more aptly described as a system-level modeling language.

SystemC is an IEEE(IEEE 1666-2011) standard and more information about it is available on accellera website(link). This post is not about introducing systemC language as we can get that information from systemC language reference Manual(LRM). There is a reference implementation of systemC available for free download on accellera website(Accellera Home)

Tumblers on a Turn Table Puzzle

You are blindfolded. There is a square turntable in front of you with four tumblers at four corners. Each might be oriented "up" or "down". You make a sequence of "moves". Each move consists of five phases:
(1) A referee turns the table an unknown number of quarter-turns(90,180, 270 or 360 degrees);
(2) You select "adjacent" or "opposite", and then take a pair of tumblers which are either "adjacent" (90 degrees apart) or "opposite" (180), accordingly.
(3) You observe (by touch) the current orientation of these two tumblers.
(4) You turn over one or the other tumbler, or neither, or both.
(5) The referee tells you whether all four tumblers are in the same orientation; if so, you win and the game is over.

After how many moves can you guarantee that you will win no matter whats the starting position or whatever way referee plays?
What is your strategy?

Solution: tumblerPuzzleSolution.pdf

Why Euler Constant ‘e’ is used as preferred logarithm base?

Euler Constant

When I read about logarithm for first time in High school I understood as it as “The logarithm of a number is the exponent to which a base(usually 10) must be raised to produce that number”

For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: 1000 = 10 ×10 ×10 = 10^3. More generally, if x = b^y, then y is the logarithm of x to base b, and is written y = log_b(x), so log₁₀(1000) = 3. This was quite reasonable to understand.

Handshakes in a Party Puzzle

You went to a get together with your wife where three of your friends arrived with their spouses. One couple among your friends were "Raj" and "Kiran". When every one arrived, people shook hands with one another but nobody shook hand with oneself(naturally) or with one's own spouse.

After the party you spoke to each person(except yourself) and asked them how many people they had shaken hands with. Each person replied with a different number.

You shook hands with "Raj". The question is:
1. Did your wife also shake hands with Raj?
2. Did you or your wife shake hands with Kiran?

Solution: HandshakePuzzleSolution

Bowling Pin Arrangement Puzzle

Once you went to bowling with your friend. All the bowling pins were labelled with different integer from 0,1,2 .. to 9. The arrangement of pins (in a triangle form) was very interesting. If two pins are side-by-side, the sum of their labels (reduced modulo 10) is equal to the label of the pin in front and between them. For Example

1   2   4   5

  3   6   9

   9   5

   4

BFS, DFS and Connect Graph Algorithms

 

In mathematics, and more specifically in graph theory, a graph is a representation of a set of objects where some pairs of objects are connected by links. Graphs are incredibly important part of Modern day life. We come across them almost daily. For example we can reach our office via separate ways possible but which one to take(Considering distance, traffic). Whole of social media like Facebook, twitter, linkedin is nothing but a huge graph with people acting as node and their relationship(friendship) acting like links or edges. Computer networks, electricity distribution network, city pipeline network, road network, airline network, Internet are nothing but a form of a Graph. There are several types of Graphs such as Directed, Undirected, Tree, Weighted, Cyclic, Acyclic etc to name a few of them. And we find examples of almost all of them in real life.

Five Friends in a Foreign Restaurant Puzzle

Five friends in Timbuktu go to a local restaurant. They do not recognise any of the dishes on the Menu as they are not familiar with such food but they are excited to try out. Each one of them orders one dish, not necessarily distinct. The waiter brings the dishes and places them in the middle, without saying which is which. At this point, they may be able to tell the names of some of the dishes based on logical reasoning. For example, if two people ordered the same dish, and everyone else ordered different dishes, then the item for which two portions arrived can be told deterministically. They enjoyed the food a lot and were eager to try more of it next day.

They return to the restaurant two more times and followed the same experiment, though with a new set of orders. After three meals, they have eaten all nine dishes on the menu, and can tell which is which.

What pattern of ordering did they follow to fulfil this?

Applying State Design Pattern to Code an FSM

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. The behavior of state machines can be observed in many devices in modern society which perform a predetermined sequence of actions depending on a sequence of events with which they are presented. 

A programmer often needs to model states of classes implementing such real life behavior. States of  a class can be implemented using some class variables denoting the a particular state the class is in. While handling the events the class is sensitive to, a check can be done to find the current state and appropriate action can be taken. For example 'if(state ==ON) do this else do that'. But this approach gets complicated if the number of states or events to which class has to react increase.

Expressing Numbers with Number Puzzle

We are given four integers 1, 2, 3 and 4 to express other numbers with an arithmetic expression using these numbers exactly once and the mathematical operators +,-,* (addition, subtraction, multiplication).  For example 1 can be represented as 1 = (2*3)-(4+1). The arithmetic operation can be used zero or multiple times but the digits(1, 2, 3, 4) should be used exactly once. So an expression to represent 1 = 2+3-4 is not valid. Where as 10 = 1+2+3+4 is a valid expression to represent 10. Also you are allowed to reuse operators (such as 24 = 1*2*3*4) and you are allowed to put '(', ')' at any desired position to change the precedence of evaluation.  But you are not allowed to join digits together such as (12+34).

C++ Exception, Error Management & Debugging

All programs have bugs. The bigger the program, the more bugs, and many of those bugs actually "get out the door" and into final released software. The biggest expense in many major programming efforts is testing and fixing.The least expensive problems or bugs to fix are the ones you manage to avoid creating. Following coding guidelines is the easiest way to avoid bugs. Code rot is a phenomenon when code deteriorates due to being neglected and a perfectly well-written, fully tested code develops new and bizarre behavior six months after it is released. 

Sequence of Equations Puzzle

This is a simple yet tricky puzzle. It seems this puzzle has been solved by pre schoolers in an average 10 Mins. By entry level programmers in around 30 Mins. And strangely people good in mathematics have taken more time to solve this riddle. Check which category you belong to. If you get the answer simply post the value in comment section. Within a day or two I will post the explanation. 

Tracing an object using Decorator Design Pattern

Decorator Pattern is a design pattern used for adding a feature to an object implementing an interface in an non intrusive way either statically or dynamically. In other words the decorator pattern can be used to extend (decorate) the functionality of a certain object statically, or in some cases at run-time, independently of other instances of the same class, provided the object creation is done using a decorator object.

Numbering the CDs Puzzle

A friend of mine works in a data management company and he needs to compulsively records  all the backuped data on CD Roms. To this end, he has a huge collection of CD ROMs. He has long given up on trying to label these cassettes with any meaningful names. Now he just numbers them and maintain the description based on number given to CD else where. The numbers go from 1 up and are consecutive.

The Golf Score Puzzle

Three friends Andrew, watson and Lestrade were playing Golf. Andrew made three statements regarding their scores for a particular round. Can your work out their individual score??

Prisoners and The Switch Room Puzzle

A prison jailor meets with the twenty three convicts when they arrive at the prison. He tells them:

You may meet today to discuss and plan a strategy, but after today you will be locked in isolated cells and have no communication with one another.

There is in this prison a "switch room" which contains two light switches, labeled "A" and "B", each of which can be in the "on" or "off" position. I am not telling you their present positions. The switches are not connected to any appliance. After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the "switch room", and this prisoner will select one of the two switches and reverse its position (e.g. if it was "on", he will turn it "off"); the prisoner will then be led back to his cell. Nobody else will ever enter the "switch room".

Imagining the Tenth Dimension

I still remember the day when my Maths teacher tried to explain about dimensions when I was in high school. Visualizing the first, second and third dimension was easy, but then I asked him, Can there be a fourth dimension? His answer was yes, It was difficult for me to understand then. He tried to explain the concept using example of a Tesseract(Shown Below), still it was very abstract for me to assimilate the concept. In fact he told that there can be a fifth and higher dimension. And infinite dimension is nothing but God himself.

Mysteries and Beauty of Fractals

Its really amazing to know know how a simple equation z_n+1 = z_n² + c can create patterns which are so intricate, so vivid and so beautiful. The set defined by above equation is know as Mandelbrot set and it represents a set of points denoted by c in a complex plane for which z_n+1 remains always bounded starting with  z₀ = 0. 

Going Native - Talk by Bjarne Stroustrup on C++11

"The world runs on C and C++". And hearing from the master himself about it is so enlightening. His emphasis on simple and clean code, explanation of new C++ 11 features and crisp examples to showcase them will encourage many to take a fresh view at the language.  The examples on type rich programming and move constructor are very interesting and that is something I look forward to use. The STL example on vector breaks my conventional understanding of the STL libraries, though I am a avid user of STL libraries myself, I always had a concern that they may not be fast. But thanks to his explanation my belief in STL is vindicated.
This presentation is quite long(Around 90 Mins) so preferably watch it at your leisure and get enlightened..

TSP Simulator based on Simulated Annealing Technique

Traveling Salesman Problem is one of the very interesting topics among algorithm enthusiast. The problem definition is very simple. Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP hard problem with no polynomial time algorithm known till date. It finds several important real life application such as routing and floor planning of Integrated Circuits, Mechanical Arm sequencing etc.
More regarding this interesting problem can by found on Wikipedia(TSP).
Simulated Annealing algorithm is a generic probabilistic metaheuristic technique for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. Simulated Annealing can be used for solving several optimization problems. TSP is one of them.

A Sudoku Solver

For quite sometime Sudoku has become a one of the most enjoyable pass time for many people and they are visible every where. We are having daily Sudoku in newspaper, several online website where we can play Sudoku and several apps for hand held devices on android and Apple app store.  In principle I knew how to solve a Sudoku and have tried several of them as well. But I wanted to code my thought process for a computer to do the job for me. Hence I ended up writing my own Sudoku solver.

The solver employs back tracking algorithm to solve a given Sudoku. Moreover if the Sudoku is not a valid one or if it cannot be solved then this programs reports that as well and exits. The idea of sharing this post is to let the users understand how a back tracking algorithm works and how it can be put in code using a stack. The pseudo code for the algorithm is as below:

Ten Assertions Puzzle

Fill in the blanks with numbers so that all the statements are true.

Number of occurrences of the digit 0 in this puzzle is  _____.
Number of occurrences of the digit 1 in this puzzle is  _____.

Number of occurrences of the digit 2 in this puzzle is  _____.

Number of occurrences of the digit 3 in this puzzle is  _____.

Number of occurrences of the digit 4 in this puzzle is  _____.

Number of occurrences of the digit 5 in this puzzle is  _____.

Number of occurrences of the digit 6 in this puzzle is  _____.

Number of occurrences of the digit 7 in this puzzle is  _____.

Number of occurrences of the digit 8 in this puzzle is  _____.

Number of occurrences of the digit 9 in this puzzle is  _____.

The Bulb Puzzle

There are 100 light bulbs lined up in a row in a long room. Each bulb has its own switch and is currently switched off. The room has an entry door and an exit door. There are 100 people lined up outside the entry door. Each bulb is numbered consecutively from 1 to 100. So is each person. Person No. 1 enters the room, switches on every bulb, and exits. Person No. 2 enters and flips the switch on every second bulb (turning off bulbs 2, 4, 6, …). Person No. 3 enters and flips the switch on every third bulb (changing the state on bulbs 3, 6, 9, …). This continues until all 100 people have passed through the room.

What is the final state of bulb No. 64? And how many of the light bulbs are illuminated after the 100th person has passed through the room?

SystemC Hierarchy Scanner

During integration of a systemC virtual platform often it is desirable to traverse deep down the hierarchy  of systemC and find out type of each systemC components. More over we can also get the hande of exact types by trying out dynamic cast operation on to it. Presenting a sample class to show case the concept of hierarchy scanning. This can be further utilized to build complex utilities. For example using this I was able to build a text based systemC pin connector.

A generic logger class

Sharing the design of a generic logger class in C++ that can be instantiated by any class that need logging facility. IT supports various features like different verbosity level, dynamic configuration of logging and C++ style streaming operator control.