copy

Thursday, 24 July 2014



CodeEval 1 - Predict The Number


About CodeEval post series



Starting from this post I would like to establish another series of posts which will be different than the typical engineering/Excel/VBA posts that are being published in this blog. The purpose of this series is to demonstrate possible solutions on various CodeEval programming challenges. Each solution has already been submitted and accepted as valid on CodeEval platform, so if you try to submit the presented solution as it is, you will probably get a “not unique solution” result. The solutions will be presented in C# language, but the logic/algorithm behind them is similar despite the language you might use.



What is CodeEval?



CodeEval is a platform used by developers to showcase their skills. Developers can participate in app building competitions and win cash/prizes. They can also solve programming challenges as a way to impress employers with their technical skills. Employers can use CodeEval as a way to enhance their brand by launching competitions/programming challenges and as a means to get introduced to the best developers.



Predict the number – challenge description



Sequence 011212201220200112 ... constructed as follows: first is 0, then repeated the following action: already written part is attributed to the right with replacement 0 to 1, 1 to 2, 2 to 0. E.g.

0 -> 01 -> 0112 -> 01121220 -> ...

Create an algorithm which determines what number is on the N-th position in the sequence.

Input sample

Your program should accept as its first argument a path to a filename. Each line in this file contains an integer N such as 0 <= N <= 3000000000. Example:

0
5
101
25684

Output sample

Print out the number which is on the N-th position in the sequence. Example:

0
2
1
0

The particular challenge has a quite low success rate (59.8% - 23/7/2014) and its level of difficulty is medium. More info you can find here.



Solution



For this challenge I tried at least 3 different solutions but, all of them failed due to the time limitation (the code you submit must complete the given test case without errors and within a certain amount of time – a few ms). Finally, after spending some time I discovered the required pattern and the working solution is given below:

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

/*
---------------------------------------------------------------------
The code below solves the CodeEval challenge - Predict the number.

Written by:    Christos Samaras
Date:          28/06/2014
e-mail:        xristos.samaras@gmail.com
site:          http://www.myengineeringworld.net
---------------------------------------------------------------------
*/

namespace PredictTheNumber
{
    class Program
    {
        static void Main(string[] args)
        {            
            using (StreamReader reader = File.OpenText(args[0]))
            while (!reader.EndOfStream)
            {
                string line = reader.ReadLine();
                if (line != null)
                {
                    long numberToFind = long.Parse(line);
                    int cnt = 0;
                    bool done = false;

                    if (numberToFind > 0)
                    {
                        for (int i = 0; i < 33; i++)
                        {
                            if (numberToFind < (long)Math.Pow(2, i))
                            {
                                long result = 0;
                                long previous = 0;

                                for (int j = i - 1; j > -1; j--)
                                {
                                    result = numberToFind - previous - (long)Math.Pow(2, j);
                                    if (result == 0)
                                    {
                                        cnt++;
                                        done = true;
                                        break;
                                    }
                                    if (result == 1)
                                    {
                                        cnt += 2;
                                        done = true;
                                        break;
                                    }
                                    if (result > 0)
                                    {
                                        cnt++;
                                        previous += (long)Math.Pow(2, j);
                                    }
                                    if (j == 0)
                                    {
                                        done = true;
                                        break;
                                    }
                                }
                            }
                            if (done)
                                break;
                        }
                        Console.WriteLine((cnt % 3).ToString());
                    }
                    else                    
                    Console.WriteLine("0");            
                }
            }
            Console.ReadLine();
        }
    }
}



Points



Here is the proof that the solution works and the points given by the CodeEval platform.

CodeEval 1 - Predict The Number - Score

Did you like this post? If yes, then share it with your friends. Thank you!


Categories:


Mechanical Engineer (Ph.D. cand.), M.Sc. Cranfield University, Dipl.-Ing. Aristotle University, Thessaloniki - Greece.
Communication: e-mail, Facebook, Twitter, Google+ and Linkedin. More info