Program to determine total stops taken by elevator I was asked a question to write a optimal program that would determine the total number of stops a elevator has taken to serve X number of people.

There is a elevator in a building with M floors. This elevator can take a max of X people at a time or max of total weight Y. Given that a set of people has arrived and their weight and the floor they need to stop given how many stops has the elevator taken to serve all the people. Consider elevator serves in the first come first serve basis.

Example:

Let Array A be the weight of people to be considered A[] = {60, 80, 40 }.

Let Array B be the floors where person needs to be dropped respectively B[] = {2, 3, 5}.

Total building floors be 5,max allowed person in elevator be 2 at a time with max weight capacity being 200. For this example, the elevator would take total of 5 stops floors ground, 2, 3, ground, 5, ground.

What would be the optimal code for this? Is there any other better solutions or ways to improve my code?

class Solution
{
    /// <summary>
    /// Return total stops used
    /// </summary>
    /// <param name="A">weight of people</param>
    /// <param name="B">floors they need to get down</param>
    /// <param name="M">total floors in the building</param>
    /// <param name="X">Max people to carry at a time</param>
    /// <param name="Y">max weight to carry at a time</param>
    /// <returns></returns>
    public int solution(int[] A, int[] B, int M, int X, int Y)
    {
        // initialize variables
        int totalStops = 0;
        long totalWeightPerRound = 0;
        int maxPersonsCount = 0;
        List<int> lstFloors = new List<int>();
        int currPerson = 0;
        bool startLift = false;
        while (currPerson < A.Length)
        {
            //Should current person be considered?
            if ((totalWeightPerRound + A[currPerson]) <= Y && (maxPersonsCount+1) <= X)
            {
                totalWeightPerRound += A[currPerson];
                maxPersonsCount++;
                lstFloors.Add(B[currPerson]);
                //If curr person is last person then start the lift
                if (currPerson == A.Length - 1)
                    startLift = true;

                currPerson++;
            }
            else
            {
                startLift = true;
            }

            if (startLift)
            {
                totalStops += lstFloors.Distinct().Count() + 1;
                //reset variable
                lstFloors.Clear();
                maxPersonsCount = 0;
                totalWeightPerRound = 0;
                startLift = false;
            }
        }

        return totalStops;
    }
}

So you said that the elevator works with the first come first serve basis. That screams like using a Queue. Moreover i like using classes as much as possible because i feel that implementing a solution becomes very easy because the abstraction is more on a human level and the readability increases.
I demonstrate it on my code.

So first you know that you have Persons who want to drive from ground to a Target Floor. A Person also have a Weight. So i have implemented this in a class:

public class Person
{
    public int Weight { get; set; }

    public int ActualFloor { get; set; }

    public int TargetFloor { get; set; }

    public Person(int weight, int targetFloor, int actualFloor = 0)
    {
        this.Weight = weight;
        this.TargetFloor = targetFloor;
        this.ActualFloor = actualFloor;
    }
}

Naming:
Moreover you know that the Elevator has different attributes too. You have implemented them in Y for Maximum Weight and X for the Maximum Number of People and i think that X and Y are really bad names for MaxWeight and MaxPeople. Why not name them what they are? That makes it easier for you as the coder and easier for other coworkers trying to understand your code.

My Elevator Properties and the Constructor are implemented as this:

public class Elevator
{
    public readonly int MaxWeight;

    public readonly int MaxPersons;

    public readonly int MaxFloors;

    public Queue<Person> Persons { get; set; }

    private List<Person> Passengers { get; set; }

    public Elevator(int maxFloors, int maxWeight, int maxPersons)
    {
        this.MaxFloors = maxFloors;
        this.MaxPersons = maxPersons;
        this.MaxWeight = maxWeight;
        this.Persons = new Queue<Person>();
        this.Passengers = new List<Person>();
    }
}

MaxWeight, MaxPersons and MaxFloors should be clear. The Queue Persons contains the People you want to drive around. Passengers are the People which are in this cycle in the elevator.

Now you can calculate the number of stops very easy:

public int CalculateNumberOfStops()
{
    int stops = 0;

    while (!this.Persons.IsEmpty())
    {
        while (this.IsOneMorePersonFitting())
        {
            this.Passengers.Add(this.Persons.Dequeue());
        }

        stops += this.Passengers.GroupBy(x => x.TargetFloor).Count();
        this.Passengers.Clear();

        // Drive to Floor Zero
        stops++;
    }

    return stops;
}

private bool IsOneMorePersonFitting()
{
    return !this.Persons.IsEmpty() &&
           this.Passengers.Sum(x => x.Weight) + this.Persons.Peek().Weight < this.MaxWeight &&
           this.Passengers.Count < this.MaxPersons;
}

I am shifting the People from the Queue into the List as long the cap of the elevator is not full and the Queue is not empty.
The number of stops are calculated with the number of Groups in the List. If you have 2 Passengers and Pass 1 wants to Floor 1 and Pass 2 wants to Floor 2 then you will have two groups. But if both want to the same Floor then you will only have one group.

You can add persons and error check with a helper function like this:

public void AddPersons(IEnumerable<Person> persons)
{
    foreach (var person in persons)
    {
        // Check if person is valid:
        if (person.TargetFloor > this.MaxFloors ||
            person.Weight > this.MaxWeight)
        {
            throw new ArgumentException();
        }

        this.Persons.Enqueue(person);
    }
}

I extended the Methods of Queue with the IsEmpty function to make is a little easier to read:

public static class ExtensionHelper
{
    public static bool IsEmpty<T>(this Queue<T> queue)
    {
        return queue.Count == 0;
    }
}

Using the elevator:

static void Main(string[] args)
{
    var elevator = new Elevator(5, 200, 2);
    elevator.AddPersons(new[] { new Person(60, 2), new Person(80, 3), new Person(40, 5) });
    var stops = elevator.CalculateNumberOfStops();

    Console.WriteLine(stops);
    Console.ReadKey();
}

For better readability you could define an empty constructor and then use it as

var elevator = new Elevator() { MaxWeight = 200, MaxPersons = 2 };

but then you can't use a readonly field and the programmer must know what is needed for the instance.


Add data into lists at runtime, from a database Presentation:

I am trying to write classes to store data from a database.

The data consists in objects, let's call them "Areas". Each area has a name and possibly 'child' areas:

public class Area {
    public string Name;
    public List<Area> SubAreas = new List<Area>();
}

The program reads data from the database (out of the scope of this review), and creates a new Data object to store this data.

The data is returned as a 2D array of stings:
[ [areaName, parentAreaName], ...]

With the following assumptions:

The parent of a root-level area is String.Empty
The parent item is before (in the array) any child item (-> no recurrence needed).

Code:

public static void Main()
    {
        //This comes from the DB
        string[,] areas = new string[4,2] {{"1",""}, {"11","1"},{"12","1"},{"2",""}};

        new Data(areas);
    }

public class Data {
    public List<Area> Areas = new List<Area> ();

    public Data(string[,] areasArray)
    {
        for (int i = 0; i < areasArray.GetLength(0); i++) {
            Area loopSubArea;
            if (areasArray[i,1] != "") {
                loopSubArea = Areas.Where(a => a.Name == areasArray[i,1]).First();
                loopSubArea.SubAreas.Add(new Area() {Name = areasArray[i,0]});
            } else {
                Areas.Add(new Area() {Name = areasArray[i,0]});
            }
        }
    }
}

The full working code is also available in a Fiddle

My concerns:

I initialize the lists during the object creation, meaning that I have possibly a lot of empty Lists around. Is that an issue?
I feel like the loop part could be improved, but I have not been able to think of anything better
I am a beginner in C#, any general advice is of course welcome.

regarding your concerns.

1) I do not believe this initialization is a problem but if later on it will be a problem, you can always change it to lazy initialization.

2,3) I just paste a similar code that I find more readable and improves your loop when you want to find the parent area.

    public class Data
    {
        public List<Area> Areas = new List<Area>();

        public Data(string[,] areasArray)
        {
            for (int i = 0; i < areasArray.GetLength(0); i++)
            {
                var areaName = areasArray[i, 0];
                var parentAreaName = areasArray[i, 1];

                if (string.IsNullOrEmpty(parentAreaName))
                {
                    Areas.Add(new Area() { Name = areaName });
                }
                else
                {
                    var parentArea = Areas.First(a => a.Name == parentAreaName);
                    parentArea.SubAreas.Add(new Area() { Name = areaName });
                }
            }
        }
    }

You can probably still improve the loop but I guess you will lost readability, so I would leave it like this unless you face a real performance issue.

Regards


Get element at a specific position in a string with separator I have created the following user defined function in order to get the element at the position POSI (starting at 0) in the string EXPR. Each element is separated by a separator (SEP).

CREATE FUNCTION [dbo].[getStringElement_Expr_Pos_Sep]
(
  @EXPR nvarchar(MAX),
  @POSI int,
  @SEP nchar
)
RETURNS nvarchar(MAX)
AS
BEGIN
  IF (@POSI < 0)
  BEGIN
    RETURN N'ERROR'
  END

  -- determine the occurrence of SEP in EXPR
  DECLARE @NB_SEP int
  SET @NB_SEP = LEN(@EXPR) - LEN(REPLACE(@EXPR, @SEP, ''))

  -- if there is no SEP -> return original EXPR
  IF (@NB_SEP = 0)
  BEGIN
    RETURN @EXPR
  END

  -- if POSI is higher than number of SEP -> return ERROR
  IF (@POSI > @NB_SEP)
  BEGIN
    RETURN N'ERROR'
  END

  DECLARE @i int = 0

  WHILE (@i < (@POSI))
  BEGIN
    SET @EXPR = SUBSTRING(@EXPR, LEN(LEFT(@EXPR, CHARINDEX(@SEP, @EXPR))) + 1, LEN(@EXPR))
    SET @i = @i + 1
  END

  IF (@POSI = @NB_SEP)
  BEGIN
    RETURN @EXPR
  END

  RETURN LEFT(@EXPR, CHARINDEX(@SEP, @EXPR) - 1)
END

For example, if I want to get the 3rd element (cc) in the string aaa|zzzzz|cc|mmmmm|e, I will call the UDF as below:

SELECT dbo.getStringElement_Expr_Pos_Sep(N'aaa|zzzzz|cc|mmmmm|e', 2, N'|')

Is there a more direct way to achieve the same result ? If not, are there things I could improve in my implementation ?

TL;DR

  Your function seems fine and is suitable and is likely to perform well unless you pass in large expression pushing the varchar(max) limit. However, I would edit it to check if the first index in the expression is the separator since if it isn't, your function would return undesired results. For example,
  SELECT dbo.getStringElement_Expr_Pos_Sep(N'aaa|zzzzz|cc|mmmmm|e', 2, N'|') with your current function returns cc not zzzzz and calling it with 3 returns mmmmmm. So your function is 0 index based (not 1) which you stated, but isn't intuitive for the SQL language as most functions are 1 based. It also doesn't account for the first element being the separator (potentially)

Long Version

One alternative option would be to use a string splitter and avoid the while loop in your current function. So, using Jeff Moden's splitter located here where he explains some performance issues with other splitters, you could achieve your results as such:

declare @EXPR nvarchar(MAX),
        @POSI int,
        @SEP nchar

set @EXPR = '|zzzzz|cc|mmmmm|e'
set @POSI = 2
set @SEP = '|'

select *
from dbo.DelimitedSplit8K(@EXPR,@SEP)
where ItemNumber = @POSI

Generally speaking, loops are slow in SQL Server and most RDMS. Also, as you can imagine, you can use the string splitter to bring back and entire table of elements which have a greater use case than your current function, reducing code maintenance. In this case, however, it depends on the length of your expression

Here is the test I ran:

set statistics time on

select *
from dbo.DelimitedSplit8K('|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e','|')
where ItemNumber = 66

SELECT dbo.getStringElement_Expr_Pos_Sep('|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e|zzzzz|cc|mmmmm|e', 66, '|')

set statistics time off

Results in Avg

Position 66
Splitter = 3ms
YourFun  = 6ms

Position 12
Splitter = 2ms
YourFun  = 4ms

Position 3
AVG
Splitter = 2ms
YourFun  = 3ms

Bias

However, if you are reduce the size of the expression to something small like your original use case, your function will run faster by a millisecond, so if you don't expect large expressions, or don't care about milliseconds, your function seems quite suitable.

Here is the full function

/****** Object:  UserDefinedFunction [dbo].[DelimitedSplit8K]    Script Date: 05/01/2017 9:42:33 AM ******/
SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE FUNCTION [dbo].[DelimitedSplit8K] (@pString VARCHAR(8000), @pDelimiter CHAR(1))
--WARNING!!! DO NOT USE MAX DATA-TYPES HERE!  IT WILL KILL PERFORMANCE!

RETURNS TABLE WITH SCHEMABINDING AS
RETURN

/* "Inline" CTE Driven "Tally Table" produces values from 1 up to 10,000...
enough to cover VARCHAR(8000)*/

  WITH E1(N) AS (
                 SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
                ),                          --10E+1 or 10 rows
       E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows
       E4(N) AS (SELECT 1 FROM E2 a, E2 b), --10E+4 or 10,000 rows max
 cteTally(N) AS (--==== This provides the "base" CTE and limits the number of rows right up front
                     -- for both a performance gain and prevention of accidental "overruns"
                 SELECT TOP (ISNULL(DATALENGTH(@pString),0)) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E4
                ),
cteStart(N1) AS (--==== This returns N+1 (starting position of each "element" just once for each delimiter)
                 SELECT 1 UNION ALL
                 SELECT t.N+1 FROM cteTally t WHERE SUBSTRING(@pString,t.N,1) = @pDelimiter
                ),
cteLen(N1,L1) AS(--==== Return start and length (for use in substring)
                 SELECT s.N1,
                        ISNULL(NULLIF(CHARINDEX(@pDelimiter,@pString,s.N1),0)-s.N1,8000)
                   FROM cteStart s
                )
--===== Do the actual split. The ISNULL/NULLIF combo handles the length for the final element when no delimiter is found.
 SELECT ItemNumber = ROW_NUMBER() OVER(ORDER BY l.N1),
        Item       = SUBSTRING(@pString, l.N1, l.L1)
   FROM cteLen l
;
GO


Pangrams CodeEval challenge I took a challenge on CodeEval. Although the code seems to work for the examples taken from the site, I feel it is not really pretty and must be more complicated than it should be.

  Description:

  The sentence 'A quick brown fox jumps over the lazy dog' contains
  every single letter in the alphabet. Such sentences are called
  pangrams. You are to write a program, which takes a sentence, and
  returns all the letters it is missing (which prevent it from being a
  pangram). You should ignore the case of the letters in sentence, and
  your return should be all lower case letters, in alphabetical order.
  You should also ignore all non US-ASCII characters.In case the input
  sentence is already a pangram, print out the string NULL.

import sys
filepath = sys.argv[1]
f = open(filepath)
wholealphabet = ('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r',
                 's','t','u','v','w','x','y','z')
for line in f:
    sortedletters = list(set(line.lower()))
    i = 0
    while i != len(sortedletters):
        if wholealphabet.count(sortedletters[i]) != 0:
            i = i + 1
        else:
            sortedletters.pop(i)
    missingletters = ""
    for letter in wholealphabet:
        if sortedletters.count(letter) == 0:
            missingletters +=letter
    if len(missingletters) == 0:
        print("NULL")
    else:
        print(missingletters)

One of Python's greatest strengths is its built-in capability to use sets directly. I don't feel you've used sets to their fullest extent here. I'd also like to point out the with statement, which you should probably use to handle file handles.

from __future__ import with_statement
import sys
from string import ascii_lowercase
filepath = sys.argv[1]
wholealphabet = frozenset(ascii_lowercase)

# Use with to handle file … handles
with open(filepath) as f:
    for line in f: # assume a line is a sentence, not exactly per spec?
        # sortedletters = list(set(line.lower())) # guaranteed to be *unsorted*
        missingletters = wholealphabet.difference(line.lower())
        if missingletters:
            print ''.join(sorted(missingletters))
        else:
            print 'NULL'

That's really all you need. Unless you want to reconsider the definition of a sentence. :)


CSS mask clipping and overlay SVG to achieve a two effect I am currently attempting to create a two SVG overlay / masking like the image below:

I have created a SVG for the overlay. As it stands, I am trying to create two elements one for the green side and one for the blue side.

For what I am trying to achieve, is this the best approach? If not, what is?

Is it worth creating two SVGs to achieve the overlay in the example below?

    .hero-overlay {
       position: absolute;
        top: 0;
       height: 100%;
       width: 100%;
     -webkit-mask: url("https://dl.dropboxusercontent.com/u/58412455/circle-mask.svg") no-repeat center center;
      mask: url("https://dl.dropboxusercontent.com/u/58412455/circle-mask.svg") no-repeat center center;
      clip: rect(0px, 580px, 500px, 0px); }

    .mask-left {
      background-color: red; }

.mask-right {
   -webkit-transform: rotate(180deg);
  -ms-transform: rotate(180deg);
      transform: rotate(180deg);
      background-color: blue; }

jsFiddle

I would suggest using an inline svg to create these shapes. This will provide more browser support than using the CSS mask property (canIuse).

Both sides are created with paths and filled with the images using the pattern element :

DEMO

* {margin: 0;padding: 0;}
body {
  background: url('http://lorempixel.com/output/nature-q-g-800-600-5.jpg');
  background-size: cover;
}
svg {
  display: block;
  width: 95vw; height: 47.5vw;
  margin: 2.5vw;
}
<svg viewbox="0 0 100 50">
  <defs>
    <pattern id="img" patternUnits="userSpaceOnUse" x="0" y="0" width="100" height="50">
      <image xlink:href="http://lorempixel.com/output/abstract-h-c-490-500-4.jpg" x="0" y="0" width="49.5" height="50" />
      <image xlink:href="http://lorempixel.com/output/abstract-h-c-490-500-8.jpg" x="50.5" y="0" width="49.5" height="50" />
    </pattern>
  </defs>
  <path d="M0 0 H49.5 V15 A10.02 10.02 0 0 0 49.5 35 V50 H0z" fill="url(#img)" fill-opacity="0.8" />
  <path d="M50.5 0 H100 V50 H51 V35 A10.03 10.03 0 0 0 50.5 15z" fill="url(#img)" fill-opacity="0.8" />
</svg>


Circular Queue using Linked List I want to create a circular queue using a linked list. I also want to create many instances of that data structure (queue) without repeating the code.

This is what I came up with:

#include <stdio.h>
#include <stdlib.h>
struct queue
{
    int info;
    struct queue *next;
    struct queue *front;
    struct queue *rear;
};
void create(struct queue **q)
{
    (*q)->next = 0;
    (*q)->front = 0;
    (*q)->rear = 0;
}
struct queue* makenode(int item){
    struct queue* p = (struct queue*)malloc(sizeof (struct queue));
    if (p) p->info = item;
    return p;
}
void addLast(struct queue **q, int item){
    struct queue* p = makenode(item);
    if ((*q)->front == NULL){

        (*q)->front = (*q)->rear = p;
        (*q)->front->next = (*q)->front;
        (*q)->rear->next = (*q)->rear;
    }
    else
    {
        (*q)->rear->next = p;
        p->next = (*q)->front;
        (*q)->rear = p;
    }
}
int delFirst(struct queue **q){

    struct queue *p = (*q)->front;

    if ((*q)->front == 0)
        printf("\nEmpty Queue\n");
    else
    {

        int temp = (*q)->front->info;
        if (((*q)->front->next) != ((*q)->front))
        {
            (*q)->front = (*q)->front->next;
            (*q)->rear->next = (*q)->front;
        }
        else
        {
            (*q)->front = 0;
        }
        return temp;
    }
    free(p);
}
void main()
{
    struct queue *premium, *normal;
    create(&premium);
    create(&normal);
    addLast(&premium, 5);
    addLast(&premium, 10);
    addLast(&normal, 20);
    addLast(&normal, 30);
    printf("%i\n", delFirst(&premium));
    printf("%i\n", delFirst(&premium));
    delFirst(&premium);
    printf("%i\n", delFirst(&normal));
    printf("%i\n", delFirst(&normal));
    delFirst(&normal);
    getch();
}

Is there a better way to do this? I feel that my code is complicated. I am new to C programming and I only learned basics about queues and linked list. I don't know even my code is 100% right or an elegant code.

I compiled this code using DevC++ and it works fine, but when I compile it using MS Visual Studio 2013, it gave me an exception:

  Access violation writing location....

I am very sure my code is not that good.

Here are some things that may help you improve your code.

Fix the return type for main

Unless you're working on an "unhosted" system (e.g. an embedded microcontroller), main should be declared as returning int and not void.

Update: As pointed out by @TimČas in a comment:

  Actually, main should be declared as int even in freestanding/unhosted (the C99 standard demands that compiler supports it; they are free to allow others, but the int version must be allowed")

The implication, of course, is that even if you're writing for an embedded system, unless you have a very old or noncompliant compiler, you should still use int as the return type for main.

Prefer standard functions

The main() function uses getch() but that's not actually standard.  Instead, you could use getchar() which is standard and will allow this code to work on any platform.

Always return an appropriate value

Your delFirst() routine has control paths that cause it to end without returning any int value.  This is an error and should be fixed.

Be careful with memory pointers

This code declares two pointers, premium and normal and then calls create which dereferences those uninitialized pointers.  That is not going to work.  Whenever you dereference a pointer, you should ask yourself "can this pointer possibly be NULL?" and "is this pointer actually pointing to something?" In this case, the pointers are not pointing to anything because they have not been set to any particular value.  Instead, you should call your makenode function instead, which actually allocates memory, and then initialize the members.

Combine allocation and initialization

The code currently has two separate functions: makenode and create both of which do part of the job of allocation and initialization.  Better would be to combine the two so that the a node is both allocated and initialized.  In C++ this is typically called RAII which stands for "Resource Acquisition Is Initialization" and it simply means that once you have a thing (a struct in this case), it's fully usuable.

Use single pointers where practical

In both your addLast and delFirst routines, the first parameter should be struct queue *q (with a single *) instead of what it currently has which is a **q.  That simplifies the rest of the code where you can replace every instance of (*q) with simply q.

Check for NULL pointers

The code inside makenode correctly avoid dereferencing a NULL pointer if the call to malloc fails, but addLast does not check p before dereferencing it. It should also check q to make sure that's not NULL either.

Consider separating the queue from the linked list

Each of the nodes in a linked list needs a next pointer, but not front or rear pointers.  Really, you only need one front and one rear pointer per queue and then just info and next per node.  You might consider creating separate node and queue structs for that reason.

Don't mix I/O with data operations

Generally speaking having a printf within a data manipulation function such as delFirst is not a good idea.  It makes it harder to reuse the function.  It's OK for diagnostics and for troubleshooting, but it would be better to omit it from the final version.


Parse and clean large log files I have the code below, which works successfully, and is used to parse, clean log files (very large in size) and output into smaller sized files. Output filename is the first 2 characters of each line. However, if there is a special character in these 2 characters, then it needs to be replaced with a '_'. This will help ensure there is no illegal character in the filename.
This would take about 12-14 mins to process 1 GB worth of logs (on my laptop). Can this be made faster?
For example, would it help to run this parallel? I am aware I could do }' "$FILE" &. However, I tested and that does not help much. Perhaps AWK itself could run in parallel (the equivalent of  print $0 >> Fpath & )?
Sample log file
email1@foo.com:datahere2
email2@foo.com:datahere2
email3@foo.com datahere2
email5@foo.com;dtat'ah'ere2
wrongemailfoo.com
nonascii@row.com;data.is.junk-Œœ
email3@foo.com:datahere2

Expected Output
# cat em
email1@foo.com:datahere2
email2@foo.com:datahere2
email3@foo.com:datahere2
email5@foo.com:dtat'ah'ere2
email3@foo.com:datahere2

# cat errorfile
wrongemailfoo.com
nonascii@row.com;data.is.junk-Œœ

Code:
#/bin/sh
pushd "_test2" > /dev/null
for FILE in *
do
    awk '
    BEGIN {
        FS=":"
    }
    {
        gsub(/^[ \t"'\'']+|[ \t"'\'']+$/, "")
        $0=gensub("[,|;: \t]+",":",1,$0)
        if (NF>1 && $1 ~ /^[[:alnum:]_.+-]+@[[:alnum:]_.-]+\.[[:alnum:]]+$/ && $0 ~ /^[\x00-\x7F]*$/)
        {
            Fpath=tolower(substr($1,1,2))
            Fpath=gensub("[^[:alnum:]]","_","g",Fpath)
            print $0 >> Fpath
        }
        else
            print $0 >> "errorfile"
    }' "$FILE"
done
popd > /dev/null

Perhaps switching the outputfile for each line can be avoided by sorting the inputfiles first or with some changes in your script:
# Store the 2-letter filenames
outfile[Fpath];
# Store the highest index for given outputfile
i[Fpath]++;
# Store current line in output array for that file
a[Fpath][i[Fpath]]=$0
# And in the END block print for array per output file
      for (out in outfile) {
         for (j=1;j<=i[out]; j++) {
            print a[out][j] >> out;
         }
      }

This results in
awk '
    BEGIN {
        FS=":"
    }
    {
        gsub(/^[ \t"'\'']+|[ \t"'\'']+$/, "")
        $0=gensub("[,|;: \t]+",":",1,$0)
        if (NF>1 && $1 ~ /^[[:alnum:]_.+-]+@[[:alnum:]_.-]+\.[[:alnum:]]+$/ && $0 ~ /^[\x00-\x7F]*$/)
        {
            Fpath=tolower(substr($1,1,2))
            Fpath=gensub("[^[:alnum:]]","_","g",Fpath);
            outfile[Fpath];
            i[Fpath]++;
            a[Fpath][i[Fpath]]=$0
        }
        else
            print $0 >> "errorfile"
    }
   END {
      for (out in outfile) {
         for (j=1;j<=i[out]; j++) {
            print a[out][j] >> out;
         }
      }
   } ' "$FILE"


Number to words problem This is a very long solution I've been working on to a Number to Words problem. I've identified that there's a lot of repeating logic (e.g. 'if writing > 0', 'writing = integer /',).

How would you refactor this?
When refactoring is there a process you use?
For readability sake would it be better to break this method into various pieces? Why?

def in_words (integer)
  ones_array = ['zero','one','two','three','four','five','six','seven','eight','nine']
  teens_array = ['blank','eleven','twelve','thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen']
  tens_array = ['blank','ten','twenty','thirty','fourty','fifty','sixty','seventy','eighty','ninety']

  result = ""

  #FOR MILLIONS
  writing = integer / 1_000_000
  left_over = integer % 1_000_000

  if writing > 0
    result << in_words(writing) << "million "
    integer = left_over
  end

  #FOR THOUSANDS
  writing = integer / 1000
  left_over = integer % 1000

  if writing > 0
    result << in_words(writing) << "thousand "
    integer = left_over
  end

  #FOR HUNDREDS
  writing = integer / 100
  left_over = integer % 100

  if writing > 0
    result << in_words(writing) << "hundred "
    integer = left_over
  end

  #FOR TENS!!!
  writing = integer / 10
  left_over = integer % 10

  if writing > 0
    if writing == 1 && left_over > 0
      result << teens_array[left_over]
      left_over = 0
    else
      result << tens_array[writing]
    end
  end

  writing = left_over

  #FOR ONES!!!!
  if writing > 0
    result << ones_array[writing]
  end

  result

end

p in_words(4) # => "four"
p in_words(15) # => "fifteen"
p in_words(92) # => "ninety two" or "ninety-two"
p in_words(101) # => "one hundred one"
p in_words(9915) # => "nine thousand nine hundred fifteen"
p in_words(1456789) # =>
    #"one million four hundred fifty six thousand seven hundred eighty nine"

You should use Ruby's Numeric#divmod function:

writing, integer = integer.divmod(1_000_000)

Your function parameter claims to accept an integer, so you should also handle negative inputs.  (It shouldn't be hard to prepend "negative " and flip the sign.)


Count Projects in a Scratch Studio I recently wrote a small Python 3 script to count the number of projects in a Scratch studio:

import re, functools
import requests

PARSE_RE = re.compile(r"""^
                          (?:  http://  |  https://  |  //  )?   # optional header
                          scratch\.mit\.edu/studios/             # main part of URL
                          (\d+)                                  # studio ID
                          (?:  /projects  )?                     # optional /projects
                          /?                                     # optional trailing slash
                          $
                            |
                          ^(\d+)$                                # alternative: just a number for the studio ID
                          """, re.VERBOSE)

EXIT_NO_ARGS = 1
EXIT_INVALID_STUDIO_ID = 2

@functools.lru_cache(maxsize=16)
def query_page(studio_id, page, verbose):
    if verbose:
        print(end="Querying page {0}... ".format(page))
    url = "https://scratch.mit.edu/site-api/projects/in/{0}/{1}/".format(studio_id, page)
    text = requests.get(url).text
    if verbose:
        print("done")
    return text

def is_404(page_html):
    # The 404 page is a full webpage with a <!DOCTYPE>
    return ("<!D" in page_html)

def count_li(page_html):
    # Counts the number of instances of the string "<li" in the argument
    return page_html.count("<li")

def count_pages(studio_id, verbose=False):
    page_maximum = 1
    while True:
        page_html = query_page(studio_id, page_maximum, verbose)
        if is_404(page_html):
            page_minimum = page_maximum // 2
            break
        page_maximum *= 2

    # preform a binary search to find the first 404 studio
    while page_maximum - page_minimum > 1:
        page_num = (page_minimum + page_maximum) // 2
        page_html = query_page(studio_id, page_num, verbose)
        if is_404(page_html):
            page_maximum = page_num
        else:
            page_minimum = page_num

    page_count = page_minimum
    highest_page_html = query_page(studio_id, page_count, verbose)
    highest_page_project_count = count_li(highest_page_html)
    total = (page_count - 1) * 60 + highest_page_project_count
    return total

if __name__ == "__main__":
    import sys

    if len(sys.argv) == 1:
        print("Usage:")
        print("  {0} <url or studio ID>:    counts the projects in that studio".format(sys.argv[0]))
        print("  {0} -v <url or studio ID>: verbose mode (logs all queries)".format(sys.argv[0]))
        sys.exit(EXIT_NO_ARGS)

    verbose = ("-v" in sys.argv)
    studio_match = PARSE_RE.match(sys.argv[-1])
    if not studio_match:
        print("Error: Invalid studio ID")
        print("Must be a URL (scratch.mit.edu/studios/12345678) or a number (12345678)")
        sys.exit(EXIT_INVALID_STUDIO_ID)
    studio_id = studio_match.group(1) or studio_match.group(2)
    print(count_pages(studio_id, verbose))

It requires requests. It can be called from the command line as python3 count.py https://scratch.mit.edu/studios/??? (where ??? is the studio ID), or it can be imported as a module and called using count.count_pages. It also supports a verbose logging mode which logs all requests.

How could this be improved?

I would highlight the following areas of possible improvements:

argument parsing: even though you have only 2 arguments to handle, using argparse would simplify the code and improve readability. It would also might make sense to have "url or studio ID" defined in a custom type, raising ArgumentTypeError if validation fails
HTML parsing: in general, parsing HTML with regexes or using str.count(), str.find() is considered a bad practice. Consider switching to an HTML parser like lxml or BeautifulSoup instead
HTTP requests: instead of using requests.get() every single time, initialize session = requests.Session() and re-use it using session.get(). This would make a positive and noticable impact on performance.

  if you're making several requests to the same host, the underlying TCP connection will be reused, which can result in a significant performance increase

And, see if you can improve on detecting 404 - would issuing .head() requests instead of .get() and checking .status_code work instead of downloading the whole page and checking for <!D in the HTML code.


Lexicographic rank of a string Given a string, find its rank among all its permutations sorted
  lexicographically. For example, rank of “abc” is 1, rank of “acb” is
  2, and rank of “cba” is 6. Assuming there is no duplicated character.

The following is my code:

#include <iostream>
using namespace std;

// A utility function to find factorial of n
int factorial(int i)
{
    if(i == 0)
        return 1;
    return i*factorial(i-1);
}

// A utility function to count smaller characters
// starting from index of ind
int count_smaller_than_cur(string& s, int ind)
{
    int count = 0;
    for(int i = ind+1; i < s.size(); ++i)
        if(s[i] < s[ind])
            count++;
    return count;
}

// A function to find rank of a string in all permutations
// of characters
int rank(string& s)
{
    int r=1;
    int len = s.size();
    int f = factorial(len);

    for(int i=0; i < len; ++i)
    {
        f /= (len-i);

        // count number of chars smaller than str[i]
        // fron str[i+1] to str[len-1]
        int t = count_smaller_than_cur(s, i);
        r += t*f;
    }

    return r;
}

int main()
{
    string str("string");
    cout << rank(str) << endl;

    system("pause");
    return 0;
}

Can anyone help me check it?

I have a couple of issues with the main function.

First, system("pause") may work for windows but won't elsewhere. You should dump it.

Second, Too many returns at the end.

Third, The hardcoded input makes it kinda hard to test (and doesn't look good). Just read the first parameter from the command line or read in from standard in. Here is an easy way to do so:

int main(int argc, char** argv) {
    string str;
    if(argc >= 2){
        str = argv[1];
    } else {
        cout << "Enter a string: ";
        cin >> str;
    }
    cout << rank(str) << endl;
    return 0;
}


Creating accounts in a cpanel/whm account I am trying to make this code that creates accounts in a cpanel/whm account more secure.

Could someone please let me know what needs to be done to make this more secure?

<?php
///////  YOUR WHM LOGIN DATA
$whm_user   = "username";      // reseller username
$whm_pass   = "password";  // the password you use to login to WHM

#####################################################################################
##############          END OF SETTINGS. DO NOT EDIT BELOW    #######################
#####################################################################################

$whm_host   = $_SERVER['HTTP_HOST'];

function getVar($name, $def = '') {
  if (isset($_REQUEST[$name]))
    return $_REQUEST[$name];
  else
    return $def;
}

// Domain name of new hosting account
// To create subdomain just pass full subdomain name
// Example: newuser.zubrag.com
if (!isset($user_domain)) {
  $user_domain = getVar('domain');
}

// Username of the new hosting account
if (!isset($user_name)) {
  $user_name = getVar('user');
}

// Password for the new hosting account
if (!isset($user_pass)) {
  $user_pass = getVar('password');
}

// New hosting account Package
if (!isset($user_plan)) {
  $user_plan = getVar('package');
}

// Contact email
if (!isset($user_email)) {
  $user_email = getVar('email');
}

// if parameters passed then create account
if (!empty($user_name)) {

  // create account on the cPanel server
  $script = "http://{$whm_user}:{$whm_pass}@{$whm_host}:2086/scripts/wwwacct";
  $params = "?plan={$user_plan}&domain={$user_domain}&username={$user_name}&password={$user_pass}&contactemail={$user_email}";
  $result = file_get_contents($script.$params);
}
// otherwise show input form
else {
$frm = <<<EOD
EOD;
echo $frm;
}

?>

EDIT:

This works:

$whm_host   = $_SERVER['SERVER_NAME'];

function getVar($name, $def = '', $sg_method = 'POST') {
  switch($sg_method){
      case 'POST'   : return isset($_POST[$name])   ? $_POST[$name]   : $def;
        break;
      case 'GET'    : return isset($_GET[$name])    ? $_GET[$name]    : $def;
        break;
      case 'COOKIE' : return isset($_COOKIE[$name]) ? $_COOKIE[$name] : $def;
        break;
      default : return $def;
  }
}

// Domain name of new hosting account
// To create subdomain just pass full subdomain name
// Example: newuser.zubrag.com
if (!isset($user_domain)) {
  $user_domain = getVar('domain');
}

// Username of the new hosting account
if (!isset($user_name)) {
  $user_name = getVar('user');
}

// Password for the new hosting account
if (!isset($user_pass)) {
  $user_pass = getVar('password');
}

// New hosting account Package
if (!isset($user_plan)) {
  $user_plan = getVar('package');
}

// Contact email
if (!isset($user_email)) {
  $user_email = getVar('email');
}

// if parameters passed then create account
if (!empty($user_name)) {

  // create account on the cPanel server
  $script = "http://{$whm_user}:{$whm_pass}@{$whm_host}:2086/scripts/wwwacct";
  $params = "?plan={$user_plan}&domain={$user_domain}&username={$user_name}&password={$user_pass}&contactemail={$user_email}";
  $result = file_get_contents($script.$params);
}
// otherwise show input form
else {
$frm = <<<EOD
EOD;
echo $frm;
}

Let's start with the easy fish - $_REQUEST. Going by the PHP manual, $_REQUEST is a combination of $_POST, $_GET, and $_COOKIE.

In your getVar(...) function, you reference the request superglobal, and in the following lines, you use it to get a password. Using the request superglobal would allow a password to be given in via insecure methods like GET and COOKIE. Ideally, you want to POST any sensitive data like a password, so let's modify the code to just grab from POST by default, and let's add a third parameter in case we need to get certain values from GET or COOKIE.

function getVar($name, $def = '', $sg_method = 'POST') {
  switch($sg_method){
      case 'POST'   : return isset($_POST[$name])   ? $_POST[$name]   : $def;
        break;
      case 'GET'    : return isset($_GET[$name])    ? $_GET[$name]    : $def;
        break;
      case 'COOKIE' : return isset($_COOKIE[$name]) ? $_COOKIE[$name] : $def;
        break;
      default : return $def;
  }
}

One glaring security issue is the following line:

$whm_host = $_SERVER['HTTP_HOST'];

You have to remember that HTTP_HOST is gotten from a user-defined header. Unless a business requirement dictates it, you should use SERVER_NAME. See HTTP_HOST vs. SERVER_NAME on Stack Overflow for a better explanation - specifically this answer by BalusC.

Now, we can compress the multiple IF statements into a simpler foreach, as follows:

$user_data = array(
    "domain"   => array($user_domain, 'user_domain'),
    "user"     => array($user_name,   'user_name'),
    "password" => array($user_pass,   'user_pass'),
    "package"  => array($user_plan,   'user_plan'),
    "email"    => array($user_email,  'user_email')
);

foreach($user_data as $key => $val){
    if(empty($val[0])){
        $$val[1] = getVar($key);
    }
}

Below is how I've modified your code:

# Your WHM login data
$whm_user   = "username";  # reseller username
$whm_pass   = "password";  # the password you use to login to WHM

#####################################################################################
##############          END OF SETTINGS. DO NOT EDIT BELOW    #######################
#####################################################################################

$whm_host   = $_SERVER['HTTP_HOST'];

function getVar($name, $def = '', $sg_method = 'POST') {
  switch($sg_method){
      case 'POST' : return isset($_POST[$name]) ? $_POST[$name] : $def;
        break;
      case 'GET' : return isset($_GET[$name]) ? $_GET[$name] : $def;
        break;
      case 'COOKIE' : return isset($_COOKIE[$name]) ? $_COOKIE[$name] : $def;
  }
}

# Domain name of new hosting account
# To create subdomain just pass full subdomain name
# Example: newuser.zubrag.com
$user_data = array(
    "domain"   => array($user_domain, 'user_domain'),
    "user"     => array($user_name,   'user_name'),
    "password" => array($user_pass,   'user_pass'),
    "package"  => array($user_plan,   'user_plan'),
    "email"    => array($user_email,  'user_email')
);

foreach($user_data as $key => $val){
    if(empty($val[0])){
        $$val[1] = getVar($key);
    }
}

# if parameters passed then create account
if (!empty($user_name)) {
  # create account on the cPanel server
  $script = "http:#{$whm_user}:{$whm_pass}@{$whm_host}:2086/scripts/wwwacct";
  $params = "?plan={$user_plan}&domain={$user_domain}&username={$user_name}&password={$user_pass}&contactemail={$user_email}";
  $result = file_get_contents($script.$params);
} else {
    $frm = <<<EOD
EOD;
    echo $frm;
}


How is my Java code for stack implementation? The following example shows how to implement stack by creating user defined push() method for entering elements and pop() method for retrieving elements from the stack.

public class MyStack {
  private int maxSize;
  private long[] stackArray;
  private int top;

  public MyStack(int s) {
    maxSize = s;
    stackArray = new long[maxSize];
    top = -1;
  }

  public void push(long j) {
    stackArray[++top] = j;
  }

  public long pop() {
    return stackArray[top--];
  }

  public long peek() {
    return stackArray[top];
  }

  public boolean isEmpty() {
    return (top == -1);
  }

  public boolean isFull() {
    return (top == maxSize - 1);
  }

  public static void main(String[] args) {
    MyStack theStack = new MyStack(10);
    theStack.push(10);
    theStack.push(20);
    theStack.push(30);
    theStack.push(40);
    theStack.push(50);

    while (!theStack.isEmpty()) {
      long value = theStack.pop();
      System.out.print(value);
      System.out.print(" ");
    }

    System.out.println("");
  }
}

The stack that you have implemented (I guess for an assignment) is too limited because of the following:

It does not support generic types. Since every container class in Java can store any object, I would suggest you to incorporate that facility in your data structure as well.
It has only a limited storage capacity, due to the use of Java array. It would be better to use a container class that can grow dynamically, such as an ArrayList, LinkedList or a Vector.
You should properly handle the boundary condition of popping from an empty stack.
Try to test your main function with a real-life application, such as evaluating a post-fix expression or checking valid parenthesization etc.


Trials, tribulations, and tributaries (Rainfall challenge) This is a fairly simple Ruby solution to the August 2016 community challenge.

Ok, the title is way too dramatic. But tributary is a nice word, and the alliteration was too good to pass up.
Besides, konijn started it!

I didn't bother to output a 2D "map" of the basins, I just print their sizes as the challenge requires. (Printing a map wouldn't be a difficult thing graft onto this, but I just wanted to keep things clean.)

Anyway, the script:

# Simple class that models a point on the terrain
class Cell
  attr_reader :altitude

  # Init with the cell's altitude
  def initialize(altitude)
    @altitude = altitude
    @neighbors = []
  end

  # Add another cell instance as a neighbor of the receiver
  def add_neighbor(cell)
    @neighbors << cell
  end

  # Returns the "drain" of the receiver (lowest of lower neighbors),
  # or nil if no such neighbor exists
  def drain
    @drain ||= @neighbors
      .select { |neighbor| neighbor.altitude < altitude }
      .min_by(&:altitude)
  end

  # Returns the sink of the receiver, i.e. the drain's drain (ad fundum),
  # or self if the cell is itself a sink
  def sink
    @sink ||= drain.nil? ? self : drain.sink
  end
end

# Helper method. Given an array of cells, register adjacent
# cells as neighbors of each other
def link_cells(cells)
  cells.each_cons(2) do |a, b|
    a.add_neighbor(b)
    b.add_neighbor(a)
  end
end

# Get the terrain size (first line of input)
size = gets.chomp.to_i

# Init the altitude cells (as a 2D array) from input
terrain = size.times.map do
  gets.strip.split.map { |altitude| Cell.new(altitude.to_i) }
end

# Register neighbors (first row-wise, then column-wise)
terrain.each { |row| link_cells(row) }
terrain.transpose.each { |col| link_cells(col) }

# Divide into basins (cells sharing same sink) and print basin sizes
basins = terrain.flatten.group_by(&:sink).values
puts basins.map(&:size).sort.reverse.join(" ")

It passes the test cases given in the challenge. It also works with non-square terrains for that matter.

To my eyes, the code suffers a bit from the 2-step process needed to create a useful Cell. It's initialized with an altitude, but that isn't really useful until a 2nd pass links all cells to their neighbors. Just seems crude.
I considered having each cell know its coordinates and adding a Terrain class to handle the neighbor-lookups, but that seemed like overkill. And it'd introduce a pet peeve of mine: The circular referencing between a cell and the collection it's part of. I've run into this tons of times (e.g. board game-type code), and never found a solution that didn't irk me a little.

Anyway, there are probably more efficient solutions out there; I just went for simple and (hopefully) readable.

Looking at it again, I see a couple of issues related to the memoizing, but I'll wait and see what reviewers find.

I'm self-reviewing here, because I found some rough spots. Do not let this keep you, dear reader, from writing a review of your own!

For this review I'll leave the overall approach as-is, and just focus on the details of its implementation. I'm nit-picking like crazy, but that's the fun part.

As mentioned in the question, I'm not super happy with the 2-step "initialization" needed to get a useful Cell instance. Mostly because it makes the Cell class tricky to use. Call #drain or #sink without adding any neighbors, and you get useless results. But at least you can add the neighbors later and try again. But call either method with some but not all neighbors added, it'll memoize possibly incorrect result. Adding neighbors after that won't correct the results.

One solution would be to wrap the Cell usage in an "outer" API. For instance a Terrain class or module, with a #basin_sizes(input) (or initializer) method that uses Cell internally to produce the answer. There'd still be a 2-step "initialization", but it'd be hidden from the outside world and (presumably) handled correctly.

Another (partial) solution would be to null the memoized results whenever a new neighbor is added. This way there wouldn't be the same risk of getting stale results, if, say, #drain was called before all the neighbors were added. It wouldn't solve the problem of #sink being memoized elsewhere, though: A cell's drain might change, but if other cells have already memoized a sink that relies on the cell's previous drain, they won't automatically update. Water doesn't flow uphill.

Speaking of memoizing, there's some inefficiency in the way it's used here. For a sink-cell, #drain will of course evaluate to nil. But memoizing a nil value with ||= has no effect: Next time the method's called, it'll evaluate the right-hand expression all over again - and again and again, always producing nil. The point of memoizing should of course be that the right-hand expression isn't run again.

One way to solve this could be to use a 2nd instance variable to track whether the results been calculated yet:

def drain
  return @drain if @drain_found
  @drain_found = true
  @drain = ...
end

But that's not very elegant.

Alternatively, one could initialize the memoization variable to a separate value/type, like false, and check for that:

def drain
  return @drain if @drain != false
  @drain = ...
end

However, all of this is actually academic. Since the method that's actually called when solving is #sink, and memoization works well for #sink (no risk of a nil value). So in the end, the memoization of #drain doesn't actually matter: It's only called once anyway. In fact, #drain might as well be private.

But perhaps a better alternative overall would be to move the "lowest lower cell"-selection from #drain to #add_neighbor:

def add_neighbor(cell)
  reference = drain ? drain.altitude : altitude # get lowest altitude
  @drain = cell if cell.altitude < reference    # update drain if lower
end

Edit: One could cut that down to

@drain = cell if cell.altitude < (drain || self).altitude

but it's probably clearer as-is.

Obviously, add_neighbor might not be the best name for this method anymore. It's more like "set drain to this cell, maybe, if you feel like it"... yeah, I don't know exactly what the name should be. Maybe just #register_neighbor or something.

Anyway, it'd shift the drain identification to be "up front", and the #drain method could be replaced with an attr_reader.

Implementing the above yields a smaller Cell class, which is nice:

class Cell
  attr_reader :altitude, :drain

  def initialize(altitude)
    @altitude = altitude
  end

  def register_neighbor(cell)
    reference = drain ? drain.altitude : altitude
    @drain = cell if cell.altitude < reference
  end

  def sink
    @sink ||= drain ? drain.sink : self
  end
end

There's still the issue of #sink being memoized, so it shouldn't be called before all neighbors have been added/tested. As far as I can tell, this is a "lesser of two evils" question. Having the memoization there short-circuits the pathfinding, so the cell#sink → cell#sink → cell#sink → ... call stack doesn't have to go full-depth every time, which I feel is worth it. Again, the entire thing can be hidden behind a single API method to protect from premature memoization.

But I won't bother with that. The code's not intended for use outside of this script anyway, so for all intents and purposes the script itself is the wrapper.


Using standard library to simplify pairwise iteration of container values I came up with this code whilst answering this question.

Is there a simpler way of doing this using standard library?

I want to iterate over every object and do something with every other object.

For example, 4 values 1, 2, 3, 4 would pair like:

(1, 2), (1, 3), (1, 4)
(2, 3), (2, 4)
(3, 4)

Each value combines with every other value. None combine with themselves, and symmetric pairings are considered the same.

This might be useful in a collision system where you want to check every solid with every other.

template<typename Iter, typename Func>
void pair_wise(Iter it, Iter last, Func func) {
    while(it != last) {
        Iter other = it;
        ++other;
        while(other != last) {
            func(*it, *other);
            ++other;
        }
        ++it;
    }
}

Usage:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values = {1, 2, 3, 4};

    pair_wise(values.begin(), values.end(),
              [](int& lhs, int& rhs) {
                  std::cout << "(" << lhs << ", " << rhs << ")\n";
              });
}

Output:

(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

It would be possible to write as for_each call to a functor writing for_each again, but I don't think it would actually be shorter.

I don't think pair_wise is a good name. There are two many things that it could mean. I'd suggest something with combinations as it calls the function for all 2-combinations.


Implementation of Sieve of Eratosthenes algorithm I have made an implementation of Sieve of Eratosthenes algorithm in Java, and am not certain that it is as efficient as possible.

I have looked at other peoples implementations on Google, and on this site, which raised concerns for me, as no one has taken a similar approach to me.

public class sieveOfEratosthenes {
    public static void main (String [] args) {
        int maxPrime;
        try (java.util.Scanner tempInput = new java.util.Scanner(System.in)) {
            System.out.println("What number would you like the prime numbers to be generated to?");
            maxPrime = tempInput.nextInt();
            tempInput.close();
        }
        System.out.println("Computing list...");
        long start = System.nanoTime();
        int [] numberList = new int [(maxPrime - 1)];
        boolean [] isPrime = new boolean [(maxPrime - 1)];
        for(int i = 0; i < (maxPrime - 1); i++) {
            numberList[i] = (i + 2);
            isPrime[i] = true;
        }
        int maxTestNum = (int) Math.sqrt(maxPrime);
        int tempAns;
        for(int j = 0; j < maxTestNum; j++) {
            int temp = numberList[j];
            if(isPrime[j] == true) {
                temp = numberList[j];
            }
            for(int k = j; k < (numberList.length - 1); k++) {
                for(int p = 2; p <= numberList.length; p++) {
                    tempAns = temp * p;
                    if(tempAns > maxPrime) {
                        break;
                    }
                    for(int z = 0; z < numberList.length; z++) {
                        if(numberList[z] == tempAns) {
                            isPrime[z] = false;
                        }
                    }
                }
            }
        }
        long stop = System.nanoTime();
        System.out.print("Prime numbers than are <= " + maxPrime + ": ");
        for(int n = 0; n < numberList.length; n++) {
            if (isPrime[n] == true) {
                System.out.print(numberList[n] + " ");
            }
        }
        System.out.println();
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms");
    }
}

The issues I came across whilst creating it were:

What is the best way of storing a list of numbers?
Is there a more efficient way of generating a list of numbers, rather than just using a for loop?
How efficient are arrays? Is there a more efficent 'version' of an array that could have been used to store/access data?

What is the best way of storing a list of numbers?

Not doing them at all? It's both the fastest and the most memory-efficient solution.
And it applies perfectly to your use case as numberList[i] == i+2 always holds.

Is there a more efficent way of generating a list of numbers, rather than just using a for loop.

There are many ways to speed it up, but there's actually always such a loop. One trivial optimization is to ignore even numbers.

How efficent are arrays?

It's the fastest storage when you access data either sequentially or by index. So concerning isPrime, it's the best what you can do (unless you want to trade speed for memory, then look at BitSet).
Concerning numberList, it'd be much better to drop it. Computing i+2 is surely way faster than reading numberList[i].

Now I have a question: How can you code be used? The answer is that

not without user interaction
not without reading the console
not for task like this one

How can it be improved: Separation of concerns. Luckily it's very easy to do in your case: Just extract methods (the IDE can do it for you):

readInput
sieve
printResult

Review
    int maxPrime;

Note that it's (usually) no prime at all.
    int [] numberList = new int [(maxPrime - 1)];
    boolean [] isPrime = new boolean [(maxPrime - 1)];
    for(int i = 0; i < (maxPrime - 1); i++) {
        numberList[i] = (i + 2);
        isPrime[i] = true;
    }

Drop numberList, use Arrays.fill(isPrime, true).
    int tempAns;

You don't need it here.
        int temp = numberList[j];
        if(isPrime[j] == true) {
            temp = numberList[j];
        }

You mean, "in case of a prime, we really want that temp has the value already assigned and assign it once more, just in case".
        for(int k = j; k < (numberList.length - 1); k++) {

No need for parentheses here.
                for(int z = 0; z < numberList.length; z++) {
                    if(numberList[z] == tempAns) {
                        isPrime[z] = false;
                    }
                }

This makes your code very slow. You could do (possibly after some bounds checks)
 isPrime[tempAns-2] == false;

and save yourself a loop.
But actually you should simplify it so that you do just
 isPrime[tempAns] == false;

s saving two elements of a potentially huge array makes no sense. Btw., tempAns is a really bad name (even worse thantemp). Call it product.
        if (isPrime[n] == true) {

Don't do it. All the following expressions are equivalent:

isPrime[n]
isPrime[n] == true
(isPrime[n] == true) == true
((isPrime[n] == true) == true) == true
(((isPrime[n] == true) == true) == true) == true

Just use the simplest one.


Implementation of OOP for retrieving list of objects from database If I have a Person class that outlines the properties of a person and one of People that just contains a List<Person> like so:

public class Person
{
    public Person(){}
    public int personID {get;set;}
    public string name {get;set;}
    public string address {get;set;}
}

public class People
{
    public People(){}

    public List<Person> peoples {get;set;}

    public List<Person> getPeople()
    {
        List<Person> p = new List<Person>();
        //create database connection
        //open datareader

        Person onePerson = new Person();
        //write data to eahc property type and add data to list

        p.Add(onePerson);
        return p;
    }
}

To call the database method that gets the people from the database I could do this:

static void main(string[] args)
{
    People p = new People();
    p.getPeople();
}

Is this how I would do this in terms of OOP?

I'm just beginning to use these techniques in my coding as usually I would remove the getPeople() method from the People class and do this in main():

static void main(string[] args)
{
    List<Person> people = getPeople();
}

private static List<Person> getPeople()
{
    List<Person> p = new List<Person>();
    //create database connection
    //open datareader
    //load data into list

    Person onePerson = new Person();

    p.Add(onePerson);
    return p;
}

Very few things in life are free. C# default constructors are one of those, the compiler generates one automatically for you if your class doesn't explicitly have one! So unless you have another constructor (with parameters) and you also need a parameterless one, putting it in is just clutter.

Encapsulating database operations in a dedicated object (like you're doing with your People class), vs doing it all in a static method, is a step forward in the right direction.. but I don't see what the peoples property is trying to encapsulate.

Think of classes as abstractions - you have a Person abstraction which represents a single record in your database. Then you have a People abstraction which represents an object that can manipulate Person records. That's all nice and tidy and high-level - you don't want to mix this niceness with boilerplate-level SQL connections and queries. Doing that is writing code at the wrong level of abstraction.

So the next step forward would be to create another class that's responsible for dealing with these things - a type that would deal with setting up a connection, running a query and then disposing the connection and every other IDiposable along the way.

Once you've done that, you will (hopefully) realize you've just reinvented the wheel - and that your wheel is more than likely square. At this stage it's all good, the worst thing you could do is start with an Entity Data Model that does it all for you: you want to understand what's going on, if it feels automagic then you've skipped something.

So first (well, after you've written your square wheel!) take a look at Linq to SQL and see what a DataContext can do for you.


Thread-safe LRU Dictionary in C# Can't seem to find one, so trying to build a very simple but fast implementation. Thought I would post on SO for review/feedback, and so that others can just copy/paste for their own use.

I'm using a Dictionary and LinkedList, with a non-granular lock.  Basic benchmark included below:

public class LRUDictionary<TKey,TValue> : IDictionary<TKey,TValue>
{
    private Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>_dict=
        new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();

    private LinkedList<KeyValuePair<TKey, TValue>> _list =
        new LinkedList<KeyValuePair<TKey, TValue>>();

    public int Max_Size { get; set; }

    public LRUDictionary(int maxsize)
    {
        Max_Size = maxsize;
    }

    public void Add(TKey key, TValue value)
    {
        lock (_dict)
        {
            LinkedListNode<KeyValuePair<TKey, TValue>> node;

            if (_dict.TryGetValue(key, out node))
            {
                _list.Remove(node);
                _list.AddFirst(node);
            }
            else
            {
                node = new LinkedListNode<KeyValuePair<TKey, TValue>>(
                new KeyValuePair<TKey, TValue>(key, value));

                 _dict.Add(key, node);
                _list.AddFirst(node);

            }

            if (_dict.Count > Max_Size)
            {
                var nodetoremove = _list.Last;
                if (nodetoremove != null)
                    Remove(nodetoremove.Value.Key);
            }
        }

    }

    public bool Remove(TKey key)
    {
        lock (_dict)
        {
            LinkedListNode<KeyValuePair<TKey, TValue>> removednode;
            if (_dict.TryGetValue(key, out removednode))
            {
                _dict.Remove(key);
                _list.Remove(removednode);
                return true;
            }

            else
                return false;
        }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        LinkedListNode<KeyValuePair<TKey, TValue>> node;

        bool result = false;
        lock (_dict)
            result = _dict.TryGetValue(key, out node);

        if (node != null)
            value = node.Value.Value;
        else
            value = default(TValue);

        return result;
    }

  [rest of IDictionary not implemented yet]

  }

Benchmark:

class Program
{
    static Random rand = new Random();
    static void Main(string[] args)
    {
        var lruspace = 50;
        var setsize = 100;
        var iterations = 1000 * 1000;
        var lrucache = new LRUDictionary<int, int>(lruspace);
        var watch = new Stopwatch();

        watch.Start();

        Parallel.For(0, iterations, (i) =>
        {
            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Add(rand.Next(setsize), 0);

            lrucache.Remove(rand.Next(setsize));
            lrucache.Add(rand.Next(setsize), 0);

            lrucache.Remove(rand.Next(setsize));
            lrucache.Remove(rand.Next(setsize));

            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Remove(rand.Next(setsize));
            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Add(rand.Next(setsize), 0);
        });

        Console.WriteLine(watch.ElapsedMilliseconds);
        Console.ReadLine();

    }
}

Output:

2592ms

Is this the best way to go? Any obvious improvements?

Whilst your code is thread safe, since you have a global lock protecting the dictionary (and the lock is relatively long lived), it will be a serious bottleneck under concurrent load. The principal scalability limit in concurrent applications is the exclusive resource lock.
The chart below shows throughput with an increasing degree of parallelism on a 16 core VM for concurrent LRU reads and writes. It compares an implementation of LRU that does not have a global lock, to an implementation fundamentally the same as your code (with a global lock).

In this test I set the concurrent dictionary concurrency level = number of threads. I believe the unusual dip at the beginning is caused by false sharing. It's old now, but gallery of processor cache effects has a nice description.
The implementation with better throughput is a thread safe pseudo LRU designed for concurrent workloads. Latency is very close to ConcurrentDictionary, ~10x faster than MemoryCache and hit rate is better than a conventional LRU algorithm (these are the other two factors that will determine performance). A full analysis provided in the github link below.
Usage of the ConcurrentLru looks like this:
int capacity = 666;
var lru = new ConcurrentLru<int, SomeItem>(capacity);

var value = lru.GetOrAdd(1, (k) => new SomeItem(k));

GitHub: https://github.com/bitfaster/BitFaster.Caching
Install-Package BitFaster.Caching

Below is the complete source code for the ClassicLRU tested above. It has shorter span locks and uses ConcurrentDictionary. It's not intended for production use (it may have bugs) - it's just to illustrate that even when taking narrow locks throughput is still bad under concurrent load.
public sealed class ClassicLru<K, V> : ICache<K, V>
{
    private readonly int capacity;
    private readonly ConcurrentDictionary<K, LinkedListNode<LruItem>> dictionary;
    private readonly LinkedList<LruItem> linkedList = new LinkedList<LruItem>();

    private long requestHitCount;
    private long requestTotalCount;

    public ClassicLru(int capacity)
        : this(Defaults.ConcurrencyLevel, capacity, EqualityComparer<K>.Default)
    {
    }

    public ClassicLru(int concurrencyLevel, int capacity, IEqualityComparer<K> comparer)
    {
        if (capacity < 3)
        {
            throw new ArgumentOutOfRangeException("Capacity must be greater than or equal to 3.");
        }

        if (comparer == null)
        {
            throw new ArgumentNullException(nameof(comparer));
        }

        this.capacity = capacity;
        this.dictionary = new ConcurrentDictionary<K, LinkedListNode<LruItem>>(concurrencyLevel, this.capacity + 1, comparer);
    }

    public int Count => this.linkedList.Count;

    public double HitRatio => (double)requestHitCount / (double)requestTotalCount;

    ///<inheritdoc/>
    public bool TryGet(K key, out V value)
    {
        Interlocked.Increment(ref requestTotalCount);

        LinkedListNode<LruItem> node;
        if (dictionary.TryGetValue(key, out node))
        {
            LockAndMoveToEnd(node);
            Interlocked.Increment(ref requestHitCount);
            value = node.Value.Value;
            return true;
        }

        value = default(V);
        return false;
    }

    public V GetOrAdd(K key, Func<K, V> valueFactory)
    {
        if (this.TryGet(key, out var value))
        {
            return value;
        }

        var node = new LinkedListNode<LruItem>(new LruItem(key, valueFactory(key)));

        if (this.dictionary.TryAdd(key, node))
        {
            LinkedListNode<LruItem> first = null;

            lock (this.linkedList)
            {
                if (linkedList.Count >= capacity)
                {
                    first = linkedList.First;
                    linkedList.RemoveFirst();
                }

                linkedList.AddLast(node);
            }

            // Remove from the dictionary outside the lock. This means that the dictionary at this moment
            // contains an item that is not in the linked list. If another thread fetches this item,
            // LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an
            // item just as it was about to move to the back of the LRU list and be preserved. The next request
            // for the same key will be a miss. Dictionary and list are eventually consistent.
            // However, all operations inside the lock are extremely fast, so contention is minimized.
            if (first != null)
            {
                dictionary.TryRemove(first.Value.Key, out var removed);

                if (removed.Value.Value is IDisposable d)
                {
                    d.Dispose();
                }
            }

            return node.Value.Value;
        }

        return this.GetOrAdd(key, valueFactory);
    }

    public bool TryRemove(K key)
    {
        if (dictionary.TryRemove(key, out var node))
        {
            // If the node has already been removed from the list, ignore.
            // E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from
            // the List & Dictionary. Now thread A will try to move x to the end of the list.
            if (node.List != null)
            {
                lock (this.linkedList)
                {
                    if (node.List != null)
                    {
                        linkedList.Remove(node);
                    }
                }
            }

            if (node.Value.Value is IDisposable d)
            {
                d.Dispose();
            }

            return true;
        }

        return false;
    }

    // Thead A reads x from the dictionary. Thread B adds a new item. Thread A moves x to the end. Thread B now removes the new first Node (removal is atomic on both data structures).
    private void LockAndMoveToEnd(LinkedListNode<LruItem> node)
    {
        // If the node has already been removed from the list, ignore.
        // E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from
        // the List & Dictionary. Now thread A will try to move x to the end of the list.
        if (node.List == null)
        {
            return;
        }

        lock (this.linkedList)
        {
            if (node.List == null)
            {
                return;
            }

            linkedList.Remove(node);
            linkedList.AddLast(node);
        }
    }

    private class LruItem
    {
        public LruItem(K k, V v)
        {
            Key = k;
            Value = v;
        }

        public K Key { get; }

        public V Value { get; }
    }
}


Script for fetching a list of "end-positions" from a MySQL database This script fetches a list of "end-positions" from a MySQL database. The positions are array positions that are the same in both MySQL and R.

Next, the script takes the previous 34 elements for each metric and calculates their correlation with a query series.

The top X highest correlated (in total for each metric) and bottom X lowest correlated rows are saved.

Finally the initial MySQL list is trimmed to contain only those highly correlated points.

I am very new to R, and I am pretty sure that I did a very inefficient job of implementing this. I am looking for response times under 1 second in length.

#Executed during initialization:
library(RODBC)
library(stats)

channel<- odbcConnect("data")
c<-mat.or.vec(3000,5) #will hold correlations
n1<-seq(-33,0)

z <- sqlQuery(channel,"SELECT RPos,M1,M2,M3,M4 FROM `data`.`z` ") #Get whole series
al_string <- "select RPos,OpenTime FROM z JOIN actionlist on(OpenTime = pTime)"
trim_string<- "DELETE FROM ActionList WHERE OpenTime NOT IN (SELECT OpenTime FROM ReducedList)"

#This segment is called repeatedly. Each time actionlist contains different positions.
actionlist<- sqlQuery(channel,al_string)

#SIMULATION: (x will be filled by something else in reality)
x <- sqlQuery(channel,"SELECT z.pTime AS pTime,M1,M2,M3,M4 FROM z JOIN (SELECT pTime FROM z ORDER BY rand() limit 1) AS X ON (z.pTime<=X.pTime AND z.pTime> x.pTime-(300*34))")
i<-1

This is the part I am most interested in speeding up:

GetTopN<-function(n)
{
  for(i in 1:nrow(actionlist))
  {
              c[i,1]<-actionlist$OpenTime[i];
              for(j in 2:ncol(z)) c[i,j]<-cor(z[actionlist$RPos[i]+n1,j],x[,j]);
  }
  avc     <- (cbind(c[,1],rowSums(c[,2:5])));
  topx    <- c[order(avc[,2], decreasing=T),1][1:n];
  bottomx <- c[order(avc[,2], decreasing=F),1][1:n];
  DF<-as.data.frame(c(topx,bottomx),row.names=NULL);
  colnames(DF)[1]<-"OpenTime";

     sqlSave(channel,dat=DF,tablename="ReducedList",append=FALSE,rownames=FALSE,safer=FALSE);
  sqlQuery(channel,trim_string);
}

The comments are good; I copy them here so this question has a "proper" answer, and add some my own:

  Just off the top of my head: 1) Don't name things c. It's a very important base R function. 2) Now that you've renamed it, don't sort it twice. Sort it once, and then use head and tail. –  joran

and

  Also, change c[i,1]<-actionlist$OpenTime[i] to c[,1]<-actionlist$OpenTime and move it out of the loop. –  Richie Cotton

and

  Also, look at ?Rprof to know how you can check which part of your function is slowing everything down. –  Joris Meys

This last is important; if you don't know where the code is slow, you don't know where to apply effort to speed it up.

My comments are that, if you have a function that is doing some work, all the information that it needs should generally be passed in as arguments. It took me a bit to figure out what c and z (after I overcame the cognitive dissonance of thinking c[i,1] was itself an error).


Calculate total width of a range of numbers I'm mostly curious if there's a faster or more efficient algorithm I could use. I created this for a unique side project, as well as for an issue at work, so what the function does (e.g., return a negative int) isn't what I'm focused on.

In short, can I make this faster or more efficient?

// GetBufferLength returns the minimum length of a buffer that can hold the
// string representation of all the numbers with in the given range of
// integers, N.
// ADD will add additional space for extra characters. E.g., if one
// wanted "$1,$2,$3...", ADD should be 2 in order to gain the additional
// space for the comma and the dollar sign.
// Will return a negative value if N is negative.
func GetBufferLength(n, add int) int {

    // Handle some edge cases
    if n < 10 {
        return n + (n * add)
    }

    if n <= 100 {
        return (n*(2+add) - 9) + 1
    }

    // Gather the largest width of all our numbers.
    if 0 < n {

        // Account for 0
        n++

        // Find the greatest power of 10.
        i, x := 1, 0
        for i < n {
            i *= 10

            // Go doesn't fully support C-style for/while loops,
            // so occasionally we have to do some janky stuff.
            if i > n {
                i /= 10
                break
            }

            // Number of powers.
            x++
        }

        // Count width of numbers.
        l := 10
        for 1 < x {
            // Algorithm is X = W*N, where W is the current width of the
            // number and N is the number of numbers (i.e., the number
            // itself).
            l *= ((x + add) * 10)
            x--

            // Since we start with X being the largest power, we need to
            // subtract the previous power, otherwise we'd double up.
            //
            // E.g., given 1000 we'd end up with (4*1000) = 4000, and
            // that would imply that _all_ numbers from 1-1000 are
            // 4 digits wide. Since 0-9 are one digit, 10-99 are two.
            // and 100-999 are three, we need to compute _their_ widths
            // and subtract their difference from the largest power.
            l -= ((x + add) * 10)
        }

        // Include single digit numbers
        return (n-i)*(2+add) + l
    }

    return n
}

Note that your algorithm is not correct:

For example input n=9, add=2 it properly returns 27 (9*1 + 9*2), but for n=10 it should be 31 (+ 2 for representing "10" and +2 as defined by add) but your algorithm returns 32.

The error increases drastically as n grows. For example n=10000, add=2 it returns 1098374! Even if all the 10000 numbers would be 5 characters long, it would be a really high estimation of 10000*5 + 10000*2 = 70000 (instead of a million).

All the following implementations along with the benchmarking code can be found on the Go Playground. The code posted there is not an executable but a test file. Save it in a file like XX_test.go, and run go test -bench . to run the benchmarks.

The algorithm

Let's examine the algoritm. Since the extra space add has to be added for each number, it always means n * add to the number of total digits. We can incorporate this at the end, so we don't have to think about it. So let's reduce the problem and algorithm putting add aside for now.

Example

Let's take the input number n=23456. How can we calculate the total length of all numbers starting from 1 up to 23456?

The numbers whose length is 5 digits is 13456 + 1, their length: 13456*5 + 5
Numbers with 4 digits and their length: 9000*4
Numbers with 3 digits and their length: 900*3
Numbers with 2 digits and their length: 90*2
Numbers with 1 digit and their length: 9*1

Formalize

Let's formalize the algorithm:

Subtract 1 from the first digit and add +1 to the result, and multiply the result with the digits count of this number.
Add the total number of digits of all the numbers having less digits.
Add extra digits specified by the add parameter.

Implementation

Things to note:

To determine which power of 10 preceeds the input n, we may use a loop always multiplying the previous number by 10. These multiplications (the powers of 10) are constants, we don't need to do this in the function, we can precalculate them and store them in a slice beforehand. Note that for practical reasons, I will store the power of 10's -1. See below the implementation for details.

var pows = []int{0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999}

If we have a sorted slice of the power of 10's, we can use binary search to find the power of 10 for our input number. However as this slice is small (~10 elements), it is faster to just loop over it in a sequencial way.

The total number of digits of all numbers having the same width (same amount of digits) are also constant values. We will precalculate these and store them so we don't have to repeat this constant calculation. For the first 8 digits:

var sums = []int{0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889}

To find the power of 10, it's a simple loop, something like this:

for i := 1; ; i++ {
    if n <= pows[i] {
        // Found it, n is lower than pow(10, i) and greater than pow(10, i-1)
    }
}

The code

Once we have the power of 10 (its index is i), the formalized algorithm:

Subtract 1 from the first digit:
n - (pows[i-1]+1)
Add +1:
n - (pows[i-1]+1) + 1 = n - pows[i-1]  (this is why we stored powers of 10 -1)
Multiply with the digits count:
(n-pows[i-1])*i
Add the total number of digits of all the numbers having less digits:
(n-pows[i-1])*i + sums[i-1]
Add extra digits specified by the add parameter:
(n-pows[i-1])*i + sums[i-1] + n*add

And that's all! It's extremely short and compact! It contains 2 multiplications, no divisions, and maybe like 10 additions and subtractions!

The complete code:

var sums = []int{0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889}
var pows = []int{0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999}

// n must be in the range of 1..999999999
func GetBufLen(n, add int) int {
    for i := 1; ; i++ {
        if n <= pows[i] {
            return (n-pows[i-1])*i + sums[i-1] + n*add
        }
    }
}

Further optimization for small numbers

If the GetBufLen() is called frequently with small numbers, it is profitable to put some additional code which "hardcodes" simplified handling of these cases. Here it is:

// n must be in the range of 1..999999999
func GetBufLenOpt(n, add int) int {
    if n < 10 {
        return n + n*add
    }
    if n < 100 {
        return n*2 - 9 + n*add
    }

    for i := 3; ; i++ {
        if n <= pows[i] {
            return (n-pows[i-1])*i + sums[i-1] + n*add
        }
    }
}

Benchmarking, speed analysis

Let's compare the speed of this algorithm with yours. We'll write a short benchmarking code, one for each of the functions (all look like this, except they call the appropriate function):

func BenchmarkLen(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for j := 1; j < testUpTo; j++ {
            GetBufLen(j, 2)
        }
    }
}

Benchmark results

testUpTo = 1000: ~21% faster

BenchmarkLen      200000              7750 ns/op
BenchmarkLenOpt   200000              6365 ns/op
BenchmarkLen2     200000              8120 ns/op

testUpTo = 100000: ~26% faster

BenchmarkLen        2000           1025102 ns/op
BenchmarkLenOpt     2000            974097 ns/op
BenchmarkLen2       1000           1328132 ns/op

testUpTo = 1000000: ~28% faster

BenchmarkLen         100          11591159 ns/op
BenchmarkLenOpt      100          11691169 ns/op
BenchmarkLen2        100          16331633 ns/op


Effectively calculate the result of geometric series Given \$f(n) = 1 + x + x^2 + x^3 + \ldots + x^n\$ and the fact that computers take more time when multiplying two numbers than when adding, how can we work out the result with greater efficiency?

#include <iostream>
using namespace std;

double powerWithIntExponent(double base, int exponent)
{
    if(exponent == 0)
        return 1;
    if (exponent == 1)
        return base;

    double result = powerWithIntExponent(base, exponent >> 1);
    result *= result;
    if ((exponent & 0x1) == 1) {
        result *= base;
    }
    return result;
}

double func(double x, int n)
{
    if (x == 0) return 1;
    if (x == 1) return n+1;

    double sum = 0;
    double x_n = 0;
    x_n = powerWithIntExponent(x, n+1);// the Geometric series start from x^0
    sum = (1-x_n)/(1-x);
    return sum;

}
int main(int argc, const char * argv[])
{

    double result = func(2, 2);
    cout<<result<<endl;
    return 0;
}

Instead of using a recursive algorithm (which might overflow the stack for large exponents) and calculating the power yourself, use the pow function which is likely pretty optimized.

#include <iostream>
#include <cmath>

using namespace std;

double func(double x, int n)
{
    double x_n;

    x_n = pow(x, n+1);
    return (1-x_n)/(1-x);
}

int main(int argc, const char * argv[])
{

    double result = func(2, 2);
    cout<<result<<endl;
    return 0;
}

Now a few minor remarks about your original code: be sure to be more consistent with your coding style. For example:

if(exponent == 0)
    return 1;
if (exponent == 1)
    return base;

vs.

if (x == 0) return 1;
if (x == 1) return n+1;

Personally, I'd always either write it on one line as in the second example or if there is a newline, I'd always add braces. For reasons see Apple's goto fail;. But it's actually a personal preference, you don't need to do it that way but I highly recommend that you chose one style and stick to it.

(Same with whitespace: there should be a space after the if in if(exponent == 0))

Consistency would also be nice here:

if ((exponent & 0x1) == 1)

Either use 0x1 both times or 1 both times. I feel that mixing these isn't a good idea.


Encapsulating the WebSphere Jython API As you review this, please keep in mind I'm using Jython 2.1 as shipped with IBM's WebSphere 7.0 (their latest-and-greatest).  I don't have decorators, properties, new style objects, or any other Python feature invented in the last decade.

Problem:

Using WebSphere's Jython interface to determine app server configuration information is not exactly fast. I had already begun work on a simple Jython module to encapsulate the convoluted WebSphere Jython API when I decided to try and cache the results of each method invocation.  WebSphere configuration details tend not to change very often.

Inspired by Python 3.2's @functools.lru_cache and Python 2.2's properties I came up with:

from org.python.core import PyString, PyTuple

class Getter:

    def getter(self,attr,valid_attrs):

        if attr == 'valid_attrs': return valid_attrs
        if attr not in valid_attrs.keys(): raise AttributeError

        attr_value = None
        if type(valid_attrs[attr]) == PyString:
            function = getattr(self,valid_attrs[attr])
            attr_value = function()

        elif type(valid_attrs[attr]) == PyTuple:
            function = getattr(self,valid_attrs[attr][0])
            args = []
            kwargs = {}
            for arg in valid_attrs[attr][1:]:
                if type(arg) == PyTuple:
                    if len(arg) > 2:
                        err = ('Named argument tuple %s in %s length > 2.'
                            % (arg, self.__class__.__name__ ))
                        raise NameError(err)

                    kwargs[arg[0]] = arg[1]

                elif type(arg) == PyString:
                    args.append(arg)

                else:
                    err = ('Unknown argument in %s __getattr__ dispatch list'
                            % self.__class__.__name__ )
                    raise NameError(err)

            attr_value = function(*args,**kwargs)

        else:
            raise AttributeError

        return attr_value

class App(Getter):

    def __init__(self, name=None):

        if name:
            self.app_name = name
        else:
            print 'App instance requires name.'
            raise NameError

    def __getattr__(self,attr):

        valid_attrs = { 'app_id': ('get_app_id'),
                        'deployed_nodes': ('get_deployed_nodes'),
                        'deployed_servers': ('get_deployed_servers'),
                        }

        attr_value = Getter.getter(self,attr,valid_attrs)
        setattr(self,attr,attr_value)
        return attr_value

    def get_app_id(self):
        return AdminConfig.getid('/Deployment: %s/' % self.app_name)

    def get_deployed_node(self):
        ### ...

    def get_deployed_servers(self):
        ### ...

As I use this in other classes I change the function dispatch dict (valid_attrs) as needed.

Is this an evil abuse of __getattr__?  Next to code execution speed, I'm most worried about maintainability.  Does this trigger a "WTF?" Or, does it make sense when viewed against the limitations of Jython 2.1 and features, such as @property, found in newer versions?

I'd say calling self.setattr from __getattr__(self, ) is borderline abuse in itself.

I guess you are trying to implement lazy attributes, right?

However in your case valid attributes are constant and their values appear constant too, so why not set them at class "declaration" time?

Also, python syntax for a tuple with 1 element is (1,) not (1) that you have in valid attrs extensively.