Uncategorized

Pop Quiz: Applied Object-Oriented Principles with C#


Q1: Does C# allow classes to have multiple inheritance?

C# allows you to to have multiple interface inheritance, but it does NOT allow you to have multiple implementation inheritance like C++. Get over it - this design decision actually makes things easier most of the time.

Q2: Can you add static methods to an interface?  

NO. Although other languages like PHP have this (Late Static Binding), in C# the designers stuck with the OOP principle that interfaces define behaviour of instances - that is they define a contract but not the implementation, hence static methods should be excluded. Java also prevents this. From a technical standpoint it is certainly possible for both Java and C# to add this feature but I suspect the respective language designers would need to be convinced before that happens.

Q3: Can you add operator overload definitions to an interface?

NO because operator overload definitions are static methods and static methods are not allowed in interfaces.

Q4: Can you add accessibility modifiers to interface members?  

NO. The point of an interface is to describe a contract between an implementing type and users of the interface. Outside callers aren't going to care and shouldn't have to care about implementation. If an interface is public then every part of that contract has to be public, otherwise it would mean one thing to friend/internal classes and a different thing to everything else. If you need default implementation then it's best to use an abstract class.

Q5: What's the difference between explicitly and implicitly implemented interfaces?

Unlike C++, in C# we can implement an interface implicitly as well as explicitly. Explicitly implemented interfaces are only available when the instance is cast to that interface. In contrast, implicit interfaces are available via the instance and via a cast of the instance to the interface in question. Explicit interfaces also help skirt the classic diamond problem associated with multiple inheritance and they are allowed to be private if necessary, but they cannot be virtual or abstract. Implicitly implemented interface member functions can be virtual or abstract, but they have to be public.

Q6: Can you define a default, parameterless constructor for a struct? 

NO. Structs provides value-type semantics, while classes provide reference-type semantics. So for efficiency in creating a struct, the rule adopted by the C# team was "the default value for any type can't rely on any initialization". Instead, the C# team resorted to the same trick they use to default value and reference types - doing a bitwise zeroing of the storage location. This results in 0 being assigned to value types used in structs and you can't do anything in the default constructor to change this since you're prevented from creating one.

Q7: Can structs implement interfaces?

Yes they can, but beware - when you cast a struct to an interface it implements you are implicitly boxing the struct since the interface reference is a reference type. This can lead to subtle issues in code as can be seen here.

Q8: Can structs be sub-classed?

NO they are implicitly sealed.


Q9: What sort of static constructors are you allowed to define on non-static classes?

Only a parameterless one - with the same name as the class obviously. Why? Well, a static constructor is run once per type, rather than once per instance, and it is guaranteed to run before any instances of the class are created, before any other static methods are accessed, but after static field initialization occurs although we don't know exactly when it runs - that part is non-deterministic. Since we don't explicitly call the constructor there is no way for the programmer to pass in parameters which is why the compiler ensures you don't waste your time writing static constructors that take parameters.

Q10: Can static constructors of non-static classes be called explicitly?

NO. They are only ever called implicitly by the runtime, and the timing of these calls is non-deterministic.

Q11: Can static classes be sub-classed?

NO. Static classes are implicitly sealed.

Q12: What is meant by the statement "References in C# are polymorphic"?

It means that a reference to a base class can point to an instance of a sub-class. That allows the developer to have methods parameters defined as the base type which accept any sub-class of that base type! Extremely handy.

Q13: Why is calling virtual-methods in a constructor a bad thing?

Consider the case where you have a base class and a derived class and the constructor of the base class calls into a virtual method which is defined in the base class but also overridden by the derived class. In C++, the base class is guaranteed to be created before the derived class so when the constructor of the base class is run it sees the most derived function as the one it has defined. In C# the base class constructor will also run before the constructor of the derived class but calls to virtual methods are always passed to the most derived version which will be the overridden function in the derived class. The problem with this is that the derived class has not been fully initialized at this point and it's constructor hasn't even been run. This is because initializers run in the opposite order as constructors. The fact that the derived class running the virtual override is not fully initialized leads to subtle side-effects that confuse the hell out of people and eventually breaks code. For these reasons it's good practice to avoid calling virtual methods from constructors, unless the class is sealed. IMHO this is one behavior where C++ is more intuitive than C#.

Q14: Is an overridden class member virtual? 

YES. If B is a sub-class of A and overrides a virtual function in A, the function can be overridden again by C, a sub-class of B. This pattern exists unless you use "override sealed" which is equivalent to the "final" keyword in Java - it prevents further overriding thus ending the virtual chain for that specific method.

Q15: Are instance members virtual or non-virtual by default in C#?

Non-virtual. Interestingly, unlike C# which requires the virtual keyword, instance methods in Java are virtual by default. C# went against this for performance and versioning reasons. They figured Java developers often forget to use the final keyword.

Q16: Can you declare a virtual static method in C#? 

NO. Makes no sense. To quote Eric Lippet... the core design principle of static methods, the principle that gives them their name, states that static methods can always be determined exactly, at compile time, what method will be called. That is, the method can be resolved solely by static analysis of the code. Virtual is the exact opposite - the virtual keyword tells the compiler that the method to be called will be determined at run time and based on run time type information.

Q17: Can you have abstract static methods in C#?

No. Abstract methods are implicitly virtual so the same argument applies as given above. See Section 10.6.6 in the C# spec... "When an instance method declaration includes an abstract modifier, that method is said to be an abstract method. Although an abstract method is implicitly also a virtual method, it cannot have the modifier virtual."

Q18: Does the "protected internal" access modifer mean OR or AND?

protected **OR** internal. Not both.


Q19: Can you override static methods in sub-classes?

No - in both Java and C#. It makes no sense to have virtual and overridden static methods.

Q20: Can abstract and virtual methods of a class be marked as private?

No because it makes no sense. The purpose of virtual and abstract methods is to permit/force a derived class to override the base functionality. Hence allowing these to be private defeats that purpose and is disallowed. Note that abstract methods are implicitly virtual.

Q21: Which of these must be done explicitly: upcasting to a base class, or downcasting to a derived class?

Downcasting to a derived class. Since upcasting to a base class is a safe operation that is guaranteed to work it is done implicitly. Conversely, downcasting is not a safe operation which is why the compiler requires you to do it as an explicit cast so it is clear on your intent.

Q22: When you upcast a reference type what happens to the object instance that you apply the cast to?

Nothing. Casting affects only the references. The object instance is not touched.

Q23: Do sub-classes automatically expose the same constructors as their base types?

NO, you have to manually re-declare them.

Q24: Does C# support covariant return types?

NO it doesn't - that's a CLR restriction, not something specific to C# - but they can be simulated using explicit, generic interfaces. Bill Wagner has a good article on that here. This is definitely one thing C++ developers find frustrating when moving over to C# since covariant return types are supported in C++ and Java. [According to this, Microsoft has no plan to change this in the future, however C# 4.0 is planned to allow co- and contra-variance on parameterized interface and delegate types.]

Q25: Can you declare a generic property in C#?

NO, only methods and types can introduce new generic parameters. Properties can of course use existing generic parameters defined in the containing class.

Q26: How do you define a concrete class that implements both an interface and a base class in C#?

You need to specify the base class first after the colon before listing any interfaces implemented.

Uncategorized

Google Code Jam: Always Turn Left

Google Code JamAfter the fun and games of alien number systems the next problem I had a crack at was the Always Turn Left problem in the practice area. This problem asks that you try and draw the "perfect maze" given a representation of the path from the entrance to the exit and vice versa. On the surface of things it didn't seem like a super-hard problem and it's not. According to the stats in the practice area it's the easiest problem of the 4 and I have to agree, but it does pose a few little challenges to navigate around...

Some Observations Before We Begin

  • By walking a "perfect maze" always touching the left wall, from both the entrance and exit, we are guaranteed to get a complete picture of the maze. If the maze were not a "perfect maze" according to the definition given in the problem description, this would not be the case.
  • This is a 2D system so we are going to need to capture the current direction you are facing and cater for "walk" and "turn" functions, but only in 90 degree increments.
  • Although we ultimately would like an RxC matrix of values we won't know what R and C are until we make both the forward and reverse journeys through the maze. This means we cannot setup a fixed-dimension data structure at the outset. (Actually we could try using the parameter limits given by Google but pre-allocating huge arrays is not my idea of efficiency.) To my mind this is the twist in the tail in this problem - how to store the intermiediate results during processing. I ended up using a struct in-memory data structure, rather than a class to avoid a heap allocation.
  • Each "cell" in the maze can have a wall on any of the 4 edges of the cell. We'll greatly simplify our logic and code if we refer to these using compass directions, {N=1, E=2, S=4, W=8} and use a bitmap value to allow simple representation of combinations using a regular primitive. The use of flags makes it easy to add new data in an additive fashion using bitwise operations.

My Approach in a Nutshell

  1. Call your start position (0,0) and imagine you have an infinite grid / cartesian plane surrounding your starting position.
  2. Using the input walk from the entrance to the exit, recording the grid positions covered and the wall structure you ascertain as you go, knowing that the person walking the maze is religously following the "always turn left, if possible" algorithm. Note that you will ascertain information about the cell you are currently in, rather than the cell you are moving to.
  3. Repeat the previous step but using the reverse direction. That is, the trip from the exit to the entrance.
  4. Collate the results of steps (2) and (3) into a nice data structure that you can use to output the results, noting the particular representation of the wall structure that the problem asks that you use.

Recording the Wall Structure

All our movements in the maze are recti-linear with only 3 possible moves : W, L and R and from each of these, regardless of the direction we are travelling, we can elicit a small piece of information about the wall structure of the current cell in the grid as follow:

  • W: Unless we just turned left, a W move means we have a wall on our left. If we keep track of which direction we are facing we can identify the "left" wall using a compass direction, N/S/E/W.
  • L: We can't derive any information about the walls of the current cell from these types of moves.
  • R: This means we must have had a wall directly in front of us and to our left. We can't make any inferences whether there is a wall behind or to the right.

My Code (in C#)

using System;
using System.IO;
using System.Collections.Generic;

namespace GoogleCodeJam.AlwaysTurnLeft
{
    class Program
    {
        [Flags]
        public enum Direction : int
        {   North = 1,
            East = 2,
            South = 4,
            West = 8,
        }

        static Direction TurnLeft(Direction before)
        {
            return TurnRight(TurnRight(TurnRight(before)));
        }

        static Direction TurnRight(Direction before)
        {
            // just right shift one place and do a modulus
            return (Direction)(((int)before << 1)%15);
        }

        // use a struct rather than a class to avoid heap allocation
        public struct CellData
        {
            public int row, col, walls;

            public CellData(int r, int c, int w)
            {
                row = r; col = c; walls = w;
            }
        }

        static void MazeTraverse(ref Direction dir, char lastMove, string moves, ref List<CellData> cells,
            ref int x, ref int y, ref int maxX, ref int maxY, ref int minX, ref int minY)
        {
            for(int i=0; i < moves.Length; i++)
            {
                char c = moves[i];
                bool isLastMove = (i == moves.Length-1);

                switch (c)
                {
                    case ('W'):
                        // moving forward means we have a wall on our left unless we just turned left   
                        if (lastMove != 'L')
                            cells.Add(new CellData(x, y, (int)TurnLeft(dir)));

                        if (!isLastMove)
                        {
                            if (dir == Direction.North) x--;
                            if (dir == Direction.West) y--;
                            if (dir == Direction.South) x++;
                            if (dir == Direction.East) y++;

                            // keep track of the maximum grid size
                            maxX = (x > maxX ? x : maxX);
                            minX = (x < minX ? x : minX);
                            maxY = (y > maxY ? y : maxY);
                            minY = (y < minY ? y : minY);
                        }
                        break;
                    case ('L'):
                        dir = TurnLeft(dir);
                        break;
                    case ('R'):
                        // turning to the right means we have a wall in front and to the left
                        cells.Add(new CellData(x, y, (int)(dir | TurnLeft(dir))));
                        dir = TurnRight(dir);
                        break;
                }
                lastMove = c;
            }
        }

        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader("input.txt");
            StreamWriter outfile = new System.IO.StreamWriter("output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // make this 1-based just for convenience
            {
                List<CellData> cells = new List<CellData>();

                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                string fromEntrance = data[0].ToUpper();
                string fromExit = data[1].ToUpper();

                //trim the initial move into the maze (from both directions)
                fromEntrance = fromEntrance.Substring(1, fromEntrance.Length - 1);
                fromExit = fromExit.Substring(1, fromExit.Length - 1);

                // Pass #1: perform initial walk in forward direction to gather maze info
                int x = 0, y = 0, maxX = 0, minX = 0, maxY = 0, minY = 0;

                // ForwardJourney
                Direction directionFacing = Direction.South;    // entrance is always on the northern edge
                char lastMove = 'W';
                Program.MazeTraverse(ref directionFacing, lastMove, fromEntrance, ref cells,
                                     ref x, ref y, ref maxX, ref maxY, ref minX, ref minY);

                // ReverseJourney
                lastMove = 'W';
                // firstly do a 180 turn
                directionFacing = TurnLeft(TurnLeft(directionFacing));
                Program.MazeTraverse(ref directionFacing, lastMove, fromExit, ref cells,
                                     ref x, ref y, ref maxX, ref maxY, ref minX, ref minY);

                // create a matrix of the compiled data
                int[,] maze = new int[Math.Abs(maxX - minX) + 1, Math.Abs(minY - maxY) + 1];
                foreach (CellData cd in cells)
                {
                    // use bitwise OR since there may be duplicated data
                    maze[cd.row - minX, cd.col - minY] = maze[cd.row - minX, cd.col - minY] | cd.walls;
                }

                // write out the results
                string hexVals = "0123456789abcdef";
                outfile.WriteLine(String.Format("Case #{0}:", caseNo));
                for (int i = 0; i <= maze.GetUpperBound(0); i++)
                {
                    string rowData = "";
                    for (int j = 0; j <= maze.GetUpperBound(1); j++)
                    {
                        int result = 0;
                        if ((maze[i,j] & (int)Direction.North) != (int)Direction.North) result += 1;
                        if ((maze[i,j] & (int)Direction.South) != (int)Direction.South) result += 2;
                        if ((maze[i,j] & (int)Direction.West) != (int)Direction.West) result += 4;
                        if ((maze[i,j] & (int)Direction.East) != (int)Direction.East) result += 8;
                        rowData = rowData + hexVals[result];
                    }
                    outfile.WriteLine(rowData);
                }
            }
            infile.Close();
            outfile.Flush();
            outfile.Close();
        }
    }
}

Uncategorized

Google Code Jam: Alien Numbers

Google Code JamGoogle Code Jam is an annual competition held by the search giant that allows programmers to try their hand at solving increasingly complex problems using the language of their choice. I managed to register for the competition in time but alas, due to various commitments, wasn't able to make it to the actual competition. Damn!!!

Rather than sit on the sidelines waiting for next year to roll around I decided to take a stab at a number of these problems and found them interesting, challenging and a whole bunch of fun. I like the fact that Google lets you work through the problems even if you are officially excluded from the competition. What follows is my attempt at these mind benders starting with the practice problems...

The alien numbers problem asks that you translate from one arbitrary alien numeral system to another alien numeral system...

The decimal numeral system is composed of ten digits, which we represent as "0123456789" (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as "oF8", then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that's written in one alien system into a second alien system.

You can read complete details about the it here: Alien Numbers Problem

My Approach

Firstly you need to understand a few key facts:

  1. a number system represented by X distinct characters is a base X number system
  2. any "number", Z, in abitrary base X can be converted to a "number" in base Y using the polynomial form:

    z = cn.Yn + c(n-1).Y(n-1) + c(n-2).Y(n-2) + ... + c2.Y2 + c1.Y1 + c0.Y0

    where ci is a co-efficient digit taken from the target base system.

Fact (1) above means that we can easily ascertain the source and target base sizes from the input given to us as the problem description clearly indicates that "no digit will be repeated in any representation, and all digits in the alien number will be present in the source language". Those 2 conditions are the necessary and sufficient conditions to ascertain the base sizes. Furthermore, we know that the digits are always given to us in ascending order so we know everything we need to about the base systems. The problem is therefore reduced to a simple base conversion problem which is where Fact (2) comes into play.

Fact (2) tells us we need to think in multiples of Yn when expressing numbers in the new base, Y. For example, if we want to convert the number 79 from base10 to, say base3 represented by the digits {0,1,2}, we need to identify the co-efficients, ci ∈ {0,1,2}, that can be mutliplied against the powers of 3 (30, 31, 32, 33, ...) and added to give us 79. In fact 79 = 2 x 33 + 2 x 32 + 2 x 31 + 1 x 30 , so 79 would be written as 2221 in a base 3 number system using the characters "0","1" and "2". If that base system used the characters "o", "F" and "8" and that represented their ascending order then 79 would be written as 888F.

With respect to the polynomial expression given above you may be asking what the value of n will be. i.e. what the highest-order of Y is needed. This is needed to determine the value of the most significant bit and you can use the formula below to do so:

n=⌊logY(x)⌋

Essentually you take the floor of the base-Y logarithm of the input number, x.

My Code (in C#)


The Code Jam competition places an emphasis on getting the correct result within a time constraint for problems of a certain magnitude. As such you needn't bother with input validation - the input data is always going to be well formatted so the code below has no error handling or input validation around this.


You could also further optimise the code to make use of memoization and perhaps make the function better handle really, really large numbers by using a lowest-highest order bit approach rather than starting with the calculation of the most-significant bit and working down as I have done. But I'll leave that as an excerise for the reader.

using System;
using System.IO;

namespace GoogleCodeJam.AlienNumbers
{
    class Program
    {
        static void Main()
        {
            StreamReader infile = new System.IO.StreamReader(@"c\:input.txt");
            StreamWriter outfile = new System.IO.StreamWriter(@"c:\output.txt");

            int testCases = Int32.Parse(infile.ReadLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read in the input data
                string[] data = (infile.ReadLine()).Split(new char[] { ' ' }, StringSplitOptions.None);
                string alienNoFromSrc = data[0];
                string srcLang = data[1];
                string tgtLang = data[2];

                // we are effectively converting from base(source) to base(target)
                string alienNoFromTgt = Convert(alienNoFromSrc, srcLang, tgtLang);

                // write out the results
                outfile.WriteLine(String.Format("Case #{0}: {1}", caseNo, alienNoFromTgt));
            }

            infile.Close();
            outfile.Flush();
            outfile.Close();
        }

        static string Convert(string number, string baseFrom, string baseTo)
        {
            double input=0;
            double srcBase = baseFrom.Trim().Length;
            double tgtBase = baseTo.Trim().Length;
            string result = "";

            // convert the input "number" to a numeric value first
            for (int i = 0; i< number.Length; i++)
            {
                input = input + (baseFrom.IndexOf(number[i]) * Math.Pow(srcBase, number.Length - 1 - i));
            }

            double index = Math.Floor(Math.Log(input, tgtBase)); // the leftmost index
            while (index >= 0)
            {
                int digit = (int)(Math.Floor(input / Math.Pow(tgtBase, index)));
                result = result + baseTo[digit].ToString();
                input = input - (digit * Math.Pow(tgtBase, index));
                index--;
            }
            return result;
        }
    }
}

And my Java code to do the same:

import java.io.*;

class Main implements Runnable {

    public static void main(String[] args) {
        new Thread(new Main()).start();
    }

    @Override
    public void run() {
        try
        {
            BufferedReader infile = new BufferedReader(new FileReader("/usr/local/data/workspace/AlienNumbers/A-large-practice.in"));
            BufferedWriter outfile = new BufferedWriter(new FileWriter("/usr/local/data/workspace/AlienNumbers/output.txt"));

            int testCases = Integer.parseInt(infile.readLine());
            for (int caseNo = 1; caseNo <= testCases; caseNo++) // note this is 1-based
            {
                // read the input data
                String[] data = (infile.readLine()).split(" ");
                String alienNoFromSrc = data[0];
                String srcLang = data[1];
                String tgtLang = data[2];

                // we are effectively converting from base(source) to base(target)
                String alienNoFromTgt = Convert(alienNoFromSrc, srcLang, tgtLang);

                // write out the results
                outfile.write(String.format("Case #%s: %s\n", caseNo, alienNoFromTgt));
            }
            infile.close();
            outfile.close(); // flush and close
        }
        catch(Exception e) {
            e.printStackTrace();
        }
    }

    public static String Convert(String number, String baseFrom, String baseTo)
    {
        double input=0;
        double srcBase = baseFrom.trim().length();
        double tgtBase = baseTo.trim().length();
        String result = "";

        // convert the input "number" to a numeric value first
        for (int i = 0; i< number.length(); i++)
            input += baseFrom.indexOf(number.charAt(i)) * Math.pow(srcBase, number.length() - 1 - i);

        // Java doesn't let us specify the required base so we use the change-of-base theorem
        double index = Math.floor( Math.log(input) / Math.log(tgtBase)); // the leftmost index
        while (index >= 0)
        {
            int digit = (int)(Math.floor(input / Math.pow(tgtBase, index)));
            result += baseTo.charAt(digit);
            input -= digit * Math.pow(tgtBase, index);
            index--;
        }
        return result;
    }

}

Next »