Some engineers got tired of dealing with all the different ways of encoding status messages, so they decided to invent their own. In their new scheme, an encoded status message consists of a sequence of integers representing the characters in the message, separated by spaces. Each integer is between 1 and M, inclusive. The integers do not have leading zeroes. Unfortunately they decided to compress the encoded status messages by removing all the spaces!

Your task is to figure out how many different encoded status messages a given compressed status message could have originally been. Because this number can be very large, you should return the answer modulo 4207849484 (0xfaceb00c in hex).

For example, if the compressed status message is “12″ it might have originally been “1 2″, or it might have originally been “12″. The compressed status messages are between 1 and 1000 characters long, inclusive. Due to database corruption, a compressed status may contain sequences of digits that could not result from removing the spaces in an encoded status message.

Input

The input begins with a single integer, N, the number of compressed status messages you must analyze. This will be followed by N compressed status messages, each consisting of an integer M, the highest character code for that database, then the compressed status message, which will be a string of digits each in the range ’0′ to ’9′, inclusive. All tokens in the input will be separated by some whitespace.

Output

For each of the test cases numbered in order from 1 to N, output “Case #i: ” followed by a single integer containing the number of different encoded status messages that could be represented by the corresponding compressed sequence modulo 4207849484. If none are possible, output a 0.

Constraints

5 <= N <= 25
2 <= M <= 255
1 <= length of encoded status <= 1000

Example input

5
12
12
255
219
30
1234321
2
101
70 8675309

Example output

Case #1: 2
Case #2: 4
Case #3: 6
Case #4: 0
Case #5: 2

Preliminaries

Let’s assume that there is a routine which split input string into a sequence of the smallest valid numbers. Zero and numbers greater than max value M are invalid. Consider following examples:

Input: M=2, S=101
Output: L= {} – Input is invalid

Input: M=11, S=101
Output: L= {10, 1}

Input: M=124, S=18143
Output: L= {1, 8, 1, 4, 3}

Now, we will concentrate on solving following problem. Given a sequence of numbers L, count all possible sequences that could be constructed from original sequence by combining consecutive numbers, such that obtained number is less than maximum value M.

Example, given M = 181 and L={1, 4, 3} we can construct 4 sequences:

1. {1, 4, 3} – original sequence is valid
2. {1, 43}
3. {14, 3}
4. {143}

Naïve approach

An obvious solution is to perform exhaustive search and actually construct all such sequences. The algorithm is as simple as:

• If sequence contains one value return 1.
• Put count = 0
• For each number in sequence
  • Try to combine it with the next number (if it exists).
    • If combination is not possible proceed to the next number.
    • Otherwise replace two consecutive numbers with combined value, recursively call this routine with modified sequence, put count = 1 + returned value, restore sequence. Proceed to the next number

No surprise this approach will only work for small sequences ~ 15-20 numbers.

But we can do better, by figuring out recurrent formula for possible number of valid sequences.

Recurrent formula

Let’s imagine that we calculated the number of different sequences S(L) for input of n numbers:

S({x₁, x₂, …, x_n} ) = S_n

What will happen if we add another number x_n+1? We might notice that:

S({x₁, x₂, …, x_n, x_n+1 } ) = S({x₁, x₂, …, x_n})+ S({x₁, x₂, …, (x_n x_n+1)})
+ S({x₁, x₂, …, (x_n-1 x_n x_n+1)}).
S({x₁, x₂, …, (x_n x_n+1)}) = S({x₁, x₂, …, x_n-1}).
S({x₁, x₂, …, (x_n-1 x_n x_n+1)}) = S({x₁, x₂, …, x_n-2}).

The structure of solutions is shown on this illustration:

Links

• Solution in C#
• Execute on Ideone

You are racing on a 2D lattice grid starting from the origin (0,0) towards a goal (M,N) where M and N are positive integers such that 0 < M <= N. There is a checkpoint that’s neither on the origin nor on the goal with coordinates (m,n) such that 0 <= m <= M and 0 <= n <= N. You must clear the checkpoint before you reach the goal. The shortest path takes T = M + N steps.

At each point, you can move to the four immediate neighbors at a fixed speed, but since you don’t want to lose the race, you are only going to take either a step to the right or to the top.

Even though there are many ways to reach the goal while clearing the checkpoint, the race is completely pointless since it is relatively easy to figure out the shortest route. To make the race more interesting, we change the rules. Instead of racing to the same goal (M,N), the racers get to pick a goal (x,y) and place the checkpoint to their liking so that there are exactly S distinct shortest paths.

For example, given S = 4, consider the following two goal and checkpoint configurations

Placing the checkpoint at (1, 3) and the goal at (2,3). There are 4 ways to get from the origin to the checkpoint depending on when you move to the right. Once you are at the checkpoint, there is only one way to reach the goal with minimal number of steps. This gives a total of 4 distinct shortest paths, and takes T = 2 + 3 = 5 steps. However, you can do better.

Placing the checkpoint at (1, 1) and the goal at (2,2). There are two ways to get from the origin to the checkpoint depending on whether you move to the right first or later. Similarly, there are two ways to get to the goal, which gives a total of 4 distinct shortest paths. This time, you only need T = 2 + 2 = 4 steps.

As a Hacker Cup racer, you want to figure out how to place the checkpoint and the goal so that you cannot possibly lose. Given S, find the smallest possible T, over all possible checkpoint and goal configurations, such that there are exactly S distinct shortest paths clearing the checkpoint.

Input

As input for the race you will receive a text file containing an integer R, the number of races you will participate in. This will be followed by R lines, each describing a race by a single number S. Lines are separated using Unix-style (“\n”) line endings.

Output

Your submission should contain the smallest possible length of the shortest path, T for each corresponding race, one per line and in order.

Constraints

5 <= R <= 20

1 <= S <= 10000000

Example input

5
4
5
12
14
1

Example output

Case #1: 4
Case #2: 6
Case #3: 6
Case #4: 9
Case #5: 2

Source:

• Facebook Hacker Cup 2012, Round 2, Checkpoint

Preliminaries

Let’s start from the following problem. Given a lattice grid and a starting point (0,0), find how many there are ways to reach point (x,y) using no more than x steps to the left and y steps to the top. The problem is known as “Block walking”.

The following picture shows two possible different ways to reach the point (2, 3) from the origin:

It is easy to observe that the length of each such path consists of exactly x+y steps. Each path can be encoded as sequence of 0 and 1. Where, 0 means “move up” and 1 means “move right” respectively. For example, blue path might be encoded as 00011 and pink path 01100. Now, calculating the total number of different paths G(x,y) from (0,0) to (x,y) is equivalent to finding the number of different rearrangements of y zeros and x ones:

 G(x,y) = C(x, x+y) = C(y, x+y) = (n+k)!/(k!n!). (*)

One important property of this equation is that G(x,y) = G(y,x).

Now, for each (x,y) the value of G(x,y) might be easily calculated. The grid with actual values looks like:

Naïve calculation of this grid using formula (*) will be extremely inefficient. Let’s investigate some important properties that might be used to calculate this grid efficiently:

• The values in the grid are symmetrical G(x,y) = G(y,x).
• G(x,0) = G(0,x) = 1
• G(x,1) = G(1,x) = x+1
• G(x,y) = G(x-1,y)+G(x,y-1)
• G(x,x) = 2*G(x-1,x) = 2*G(x, x-1)

These formulas lead to a very efficient algorithm for building such a table:

           for (int i = 0; i < max; i++) {
            for (int j = i; j < max; j++) {
                if (i == 0) {
                    d[i, j] = 1;
                    d[j, i] = 1;
                } else if (i == j)
                    d[i, i] = 2 * d[i - 1, i];
                else {
                    d[i, j] = d[i - 1, j] + d[i, j - 1];
                    d[j, i] = d[i, j];
                }
            }
        }

The program doesn’t even have to store the complete grid, only the previously calculated row or column. There is no need to perform calculations when any of coordinates is equal to 0 or 1. This will be implemented in the final solution.

It’s time to introduce checkpoint into consideration. And the next sub-task that should be solved is finding how many shortest paths S(m,n,M,N) exist from origin (0,0) to the goal (M,N) through checkpoint (m,n), such that (**):

• (m,n)!=(0,0)
• (m,n)!=(M,N)
• 0 <= m <= M and 0 <= n <= N

Path from the origin through checkpoint towards the goal

Combinatorial rule of product gives us the answer:

S(m,n,M,N) = G(m,n) * G(M-m, N-n)

So, the ultimate task is the following. Over all possible combinations of (m,n) and (M,N) find such that:

S = S(m,n,M,N)

T = argmin_M,N(M+N) where m,n,M,N satisfy conditions (**)

There is one more sub-task left before we can formulate final algorithm to solve the problem: given an integer number S find all possible positive integers S1 and S2 such that:

• S = S1*S2
• S1<=S2

This problem is a special case of integer factorization problem. The algorithm to factor any integer number into two multipliers is as simple as:

        int s1 = 1;
        int threshold = (int)Math.Sqrt(s) + 1;

        while (s1 < = threshold) {
            int ost = s % s1;
            if (ost == 0) {
                int s2 = s / s1;
                if (s2 < s1) break;
	        // Output s1*s2 = s
            }
            s1++;
        }

Problem solution

It is time to formulate an algorithm that solves given task:

• 1)If S = 1 output 2.
• 2)Factor input number S into all possible multipliers S1*S2, S1<=S2
  • a. For each S1, S2
    • i.  Find all points (m1,n1) and (m2,n2) such that G(m1,n1)=S1, G(m2,n2)=S2. To calculate point (m1, n1). Build rows of triangular matrix G until numbers in the row are less than S1. If number G(x,y) = S1, then use m1=x, n1 = y. There are might be several such (m1,n1) in the matrix.
      • 1. For each found (m1,n1),(m2,n2) find minimum T₀ of m1+n1+m2+n2.
• 3)The smallest found T₀ is a solution.

There is always a solution for any number S. If S is a prime, then there is only one factorization: S = 1*S and one possible solution: from origin (0,0) go to closest checkpoint (1,0) and to the point (1,S-1); T = 1+0+1+S-1 = S+1;

Example: consider S = 9.

1) Factorization gives us two pairs (1,9) and (3,3).

1. For S1 = 1, this is boundary case, take one point (1,0)
2. For S2 = 9, there is one point (1,8)
   • i. T₀ = 1+0+1+8=10

1. For S1 = 3, this is boundary case, take one point (1,2)
2. For S2 = 3, this is boundary case, take one point (1,2)
   • i. T₀ = 1+2+1+2=6

2) The smallest found T₀ is 6.

There is no need to recalculate matrix G for each number S. Instead in the solution the rows of the matrix G will be built until numbers in the row are less than 10000000 (task constraint). Based on the matrix, a mapping from integer to a list of points < (x1,y1), (x2,y2), … > will be created, such that for each point (x,y) in the list of number N: N = G(x,y). Which means that step 2.a.i is no more than two lookups in such a mapping. The program can build a mapping once and reuse it while processing all test cases.

Time complexity analysis

The program should complete 20 test cases in less than 6 minutes. Building a mapping takes around 13 seconds on my laptop and ~1Gb of RAM which is acceptable. The rest is spent on factorizing and finding minimum values. There are two things I checked before I was convinced that my solution works fast enough to finish execution in 6 minutes:

• The longest list of points in the mapping. Surprisingly enough, the longest list appears for the number 3003 and the length is 4. So, in the worst case it will lead to a loop of 4*4=16 iterations at the step 2.a.i.1. That should not be of any performance problem.
• The number in the range of [0.. 10000000] that factorized into maximum number of two different multipliers. I have performed factorization of all numbers, it took about ~3 minutes. This magic number is 8648640 giving 224 pairs of numbers.

So the worst possible input is 20 numbers equal to 8648640. Running the program on this input proves that on my machine it will take less than 15 seconds for any possible input. Most of that time spent on building the mapping.

Results

The initial solution was coded in C#, submitted and accepted by Facebook:

The code that uses all above mentioned optimizations runs much faster and completes all test cases almost instantly. The code could be obtained by the following link: Final Checkpoint Solution or executed at Ideone.com

Links

• http://en.wikipedia.org/wiki/Block_walking
• http://en.wikipedia.org/wiki/Rule_of_product
• http://en.wikipedia.org/wiki/Factorization

Recently I saw nice video from Stephan T. Lavavej where he presents regular expressions from C++’s STL library. In this video he mention an interesting use case, where regular expressions might be used to create tokenizers. Usually when writing tokenizers one would express rules for matching tokens, while in the proposed approach you are expected to write rules for matching token separators. Piece of the text that does not match regex for separator is your token.

I have tried to write something more complicated than just splitting text using whitespace characters as separators. Tokenization then became a two phase process:

• At the first stage, tokenizer will split input text using whitespaces.
• At the second stage, tokens will be matched against a set of regular expressions. This set contains regular expressions for matching:
  • numbers,
  • urls,
  • e-mail addresses,
  • dates.

  Once text from the first stage match one of the given regexes it will be converted into token of specific type. Otherwise the text will be split into sub-tokens using punctuation characters.

Here is an example. The text: “My birthday is 20/01/1984″, will be first split into following tokens:

“My” “birthday” “is” “20/01/1984″

Then each token will be matched against more restrictive regular expressions. “20/01/1984″ will be recognized as date.

As mentioned in the video there are specializations of regex type for string types: string and wstring. However, I wanted my tokenizer to work well with files. According to standard regex require bidirectional iterators. So, I’ve decided to write very simple implementation of a custom bidirectional file based iterator. It provides buffered access to ASCII text files and might be found in attached solution.

Downloads: Regex tokenizer C++ solution.

Final thoughts. Even though presented approach looks promising, regular expressions are very powerful in capturing various patterns, implementation appears to perform slow comparing to handwritten tokenizer. So, it is only practical for parsing small files. On my Dell Studio 1555 laptop (Intel Core 2 Duo P8700 2.53GHz with 4GB of RAM and x64 Windows 7) the speed of tokenization is only about 400-800 Kilobytes per second comparing to handwritten tokenizer reaching about 5-10 megabytes per second.

In my example I’ve used some regular epxressions from the following website: http://regexlib.com.

A good introduction to TR1 C++ regular expressions might be found here.

Here is a puzzle: Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes–without the process taking longer than nine minutes

Here is my solution:

Let’s start with a final result of the algorithm:

Small white rectangles approximate circle’s border. Red rectangles form an inner area of the circle. Yellow does not belong to the circle and might be removed.

Building quad tree is simple. We start from the bounding rectangle. Then it will be split into four smaller rectangles of the equal size. Let’s say, input rectangle is defined by following points (x1,y1) -> (x2,y2). Then rules for splitting it into four smaller rectangles are following:

• (x1, y1) -> (x2-width/2,y2-height/2)
• (x1, y1+height/2) -> (x1+width/2,y2)
• (x2-width/2, y2-height/2) -> (x2,y2)
• (x2-width/2, y1) -> (x2,y2-height/2)

This procedure might be recursively applied to all leafs in the tree until new leaf rectangles reach certain size.

In order to make a decision if given leaf rectangle should be split, we need a function f, which for a given rectangle r will return how many of its verteces belong to the figure. There are obviously four cases:

• f(r) = 4 – Rectangle belongs to the inner area of the figure. No further split required. (Such rectangles are red)
• f(r) = 3 or 2 – These rectangles touch the border of the figure and about half of the rectangle belongs to figure. (White rectangles)
• f(r) = 1 – Less than half of the rectangle belongs to figure. (Gray rectangles)
• f(r) = 0 – Rectangle lays outside the figure. No further split required. (Yellow rectangles)

For a circle, function f is quite simple:

• f(x1,y1,x2,y2) = belongs(x1,y1)+belongs(x1,y2)+belongs(x2,y2)+belongs(x2,y2),

Where

• belongs(x,y) = 1, if x*x+y*y< =r*r and 0 otherwise,
• r – is the radius of the circle.

There is a C# solution that shows this basic algorithm: Download.

By modifying function f, one can adopt this algorithm for other 2D figures.

Principles, guidelines and tools were developed to facilitate creation of extendible systems. For examples refer to the following links:

• Key Principles of Software Architecture,
• Managed Extensibility Framework,
• Unity Application Block,

In this post I am going to present two ways of implementing another common technique towards building extendible software using .NET Framework 4. In other words I am going to show how to create scriptable applications, i.e. applications controlled by script. Scriptable application allows extending its base functionality by means of user scripts, like Excel allows user creating a VBScript which performs common operations.

I have already posted few articles and solutions on this topic:

• Building DLR scripting language:
  • Simple DLR language
  • Creating Variable in DLR (DLR Language – Part 2)
  • DLR Language with Generated parser (Part 3)
  • Expression evaluator in 15 minutes with Irony & Dlr
• S# is a complete scripting solution for .NET,

However as development platforms and tools evolve, new efficient ways of doing certain things appear. Approaches based on dynamic assembly generation and Lambda expressions will be presented.

Let’s start with Lambda expressions, as a preferred approach for simple scenarios. It is possible to construct expression at runtime and compile it to dynamic method (Dynamic method is a garbage collected object):

var argument = Expression<Func<int, bool>>
                      .Parameter(typeof(int), "p");
var expression = Expression<Func<int, bool>>
  .Lambda<Func<int, bool>>(
   Expression<Func<int, bool>>
    .LessThan(argument, Expression<Func<int, bool>>.Constant(5)),
       argument);

Which is essentially the same as following lambda function in C#: p=>p<5.

Now expression could be compiled and executed:

 Func<int, bool> function = (Func<int, bool>)expression.Compile();
 bool result = function(4);

So, what is required to build scripting language out of lambda expressions? Of course you will need a parser for your language. There are a lot of information and tools available on this topic. I will just mention following: ANTLR parser generator, GOLD Parsing System, Irony, and of course Lex & Yacc . Excellent book describing underlying theory is also available: Compilers: Principles, Techniques, and Tools

For demonstration purposes I’ve built simple recursive descent parser for arithmetic expressions. It could recognize arithmetic expressions composed of integer constants and +,-,*, / operations and build lambda expression out of it:

 LambdaExpression expression = Parser.ParseCode("3+(5-1)*2");

Lambda expression as we saw before could be compiled as delegate:

 Func<double> function = (Func<double>)expression.Compile();

The function might now be executed:

 double result = function(); // result = 11

This is already a step towards extendible software. Imagine that user could define expression as string value; input it to the application somehow (via GUI, configuration, services) and application can execute it. Of course to be of real value your expression language should provide ways to interact with application object model. This could be achieved via functions, objects, messages, etc. Look for example at Excel Object Model and how it could be accessed from VBA.

Designing a language for an application and then writing a parser could be unrealistic task for many projects. Back in 2008 at PDC Anders Hejlsberg talked about rewriting the C# compiler and providing a “compiler as a service”. Unfortunately this does not happen, but there is an old API around csc command line compiler, which allows compiling code from managed .NET application into new assembly. This assembly could be then dynamically loaded and used from a host application. The main drawback of this approach is that in .NET, assembly can’t be unloaded from the memory once it had been loaded. The only possible way to do this is to create a dedicated AppDomain, load new assembly into this domain, execute it and then unload the whole domain. In some scenarios such approach could be beneficial, especially if overhead of compilation and creating new AppDomain could be neglected.

An approach based on dynamic assembly compilation could be found in DynamicCodeExecutor.cs. It has two classes: DynamicCompiler and DynamicCodeExecutor.

The purpose of DynamicCompiler is to compile provided C# code into assembly using CSharpCodeProvider and load it into current application domain. Then it might be used to execute static public method of any public class from generated assembly (see method Execute).

DynamicCodeExecutor creates a new application domain and instantiates an instance of DynamicCompiler object in this new domain. In order to perform that, DynamicCompiler should be serializable and inherited from MarshalByRefObject.

AppDomainSetup domainSetup = new AppDomainSetup();
domainSetup.ApplicationBase = AppDomain.CurrentDomain.BaseDirectory;
domainSetup.DisallowBindingRedirects = false;
domainSetup.DisallowCodeDownload = true;
domainSetup.ConfigurationFile = AppDomain.CurrentDomain
                            .SetupInformation.ConfigurationFile;

AppDomain workerAppDomain = AppDomain
            .CreateDomain("Compiler", null, domainSetup);

DynamicCompiler compiler = (DynamicCompiler)workerAppDomain
            .CreateInstanceAndUnwrap(
                 typeof(DynamicCompiler).Assembly.GetName().Name,
                 typeof(DynamicCompiler).FullName);

After that, it invokes Compile method of DynamicCompiler. On successful compilation, it will call execute method with provided arguments. Finally, DynamicCodeExecutor unloads AppDomain and deletes generated assembly.

 IEnumerable<CompilerError> results
                   = compiler.Compile(code, assemblies);
 object result = compiler.Execute(type, method, args);
 AppDomain.Unload(workerAppDomain);

Here is a code snippet that shows how DynamicCodeExecutor could be used in C# code:

Console.WriteLine(DynamicCodeExecutor.CompileAndExecute(
     @"class DynamicClass{
         public static string DynamicMethod(string name){
              return name.ToUpper();
         }
          }",
         "DynamicClass",
         "DynamicMethod",
         new object[] { "Hello World" },
         new string[] { "System.dll" }));

There is however a third way available. Any .NET application could become scriptable by using S# scripting language. S# is a weakly-typed dynamic language and runtime infrastructure for making extendable, customizable and highly flexible applications. It allows introducing expressions and large code blocks within your applications in the similar way Microsoft Office deals with VBScript. It gives possibilities for providing rich formula evaluation capabilities like it can be seen in Microsoft Excel and other office applications.

Minimal usage scenario contains only 3 lines of code:

 RuntimeHost.Initialize();
 Script.RunCode("Console.WriteLine('This is Script');");
 RuntimeHost.CleanUp();

More about S# could be found at: S# Wiki.

Conclusions

I have demonstrated three different ways for introducing dynamic code execution in .NET application. Each of these approaches has different usage scenarios and strong points. Lambda expressions are good for simple arithmetic calculations. Generating dynamic assembly on the other hands allows utilizing full power of C# and .NET libraries; however it is not always suitable because of performance overhead on compilation and AppDomain creation, security limitations, etc. S# is a good compromise that combines expressive power of programming language and ability to use .NET libraries and efficient interpreter purely written in C #that does not involve any code generation and IL emitting.

Downloads

Example Source Code

Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.

Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.
Constraints

1 < = N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

Solution in C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication6 {
    class Program {
        static int N;

        static void Main(string[] args) {
            string s = File.ReadAllText(args[0]);
            string[] splits = s.Split(new char[] { '\n', '\r' },
                              StringSplitOptions.RemoveEmptyEntries);

            N = int.Parse(splits[0]);
            for (int i = 1; i < N + 1; i++) {
                string[] words = splits[i]
                                         .Split(' ')
                                         .Skip(1)
                                         .ToArray();

                Console.WriteLine(Solve(words));
            }
        }

        private static string Solve(string[] words) {
            string prefix = string.Empty;
            List sorted = new List(words);

            while (true) {
                sorted = sorted.OrderBy(x => x).ToList();
                if (sorted.Count == 0) break;

                string pr = sorted.First();
                string sf = sorted.Skip(1)
                                .Where(a => a.StartsWith(pr))
                                .Select(s => s.Substring(pr.Length))
                                .Where(s => !string.IsNullOrEmpty(s))
                                .OrderBy(x => x + pr)
                                .FirstOrDefault();

                if (string.Compare(pr + pr, pr + sf) < 0)
                    sf = null;

                prefix += pr + sf;
                sorted.Remove(pr + sf);
            }

            return prefix;
        }
    }
}

Sources: C# Implementation

Examples:

• Sample Input/Output 1
• Sample Input/Output 2

The blog will be maintained by Mariya Bezverkha, PhD and lecturer in Computer Science. It will contain various learning materials, lab practicums, book overviews, etc. Blog languages are: English, Ukrainian.

Published information targeted on students in computers science & software engineering, quality assurance engineers (QA), and university teachers.