Hackerrank: Arithmetic Expressions Problem: Arithmetic expressions

  Given a list of 2..10,000 integer numbers in a range of 1..100 place operators +, - or/and * between them, so that the whole expression results in a number divisible by 101. Output the resulting expression.
  Note, the operators have no precedence and are left-associative: expression a+b*c-d*e shall be interpreted as (((a+b)*c)-d)*e.

Link

import java.io.*;
import java.util.*;

public class Solution {

    static int array[];

    public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
       int n = s.nextInt();
       array = new int[n];
       for (int i = 0; i < n; i++)
           array[i] = s.nextInt();
       System.out.println(array[0] + recursive(array[0], 1));
    }

    public static String recursive(int total, int index) {
       total %= 101;
       if (index == array.length){
           return total == 0 ? "" : null;
       }
       String result =recursive(total-array[index],index +1);
       if (result != null){
          return "-" + array[index] + result;
       }
          result = recursive(total + array[index], index + 1);
       if (result != null){
          return "+" + array[index] + result;
       }
       result = recursive(total * array[index], index + 1);
       if (result != null){
          return "*" + array[index] + result;
       }
       return null;
    }
}

I have tried multiple submissions with alternating the sequence of '+','-','*' and also tried same solution in C but always get the "Terminated due to timeout" message. I am the end of my thinking capacity and would appreciate any help possible.

Note: Changing the sequence of '+','-','*' in recursive function check helped me with few test cases during each sequence , but didn't pass all the test cases for any sequence.

The main thing you are missing is that when total is 0 (a multiple of 101), you can stop the recursion and just make all other operators be *, as you already reached a multiple of 101 and product will keep it like that.

As for the order of operators in the recursive function, the right choice is to put * at the end, which seems to be what you have right now. The main reason is that 101 is prime, so you won´t get a multiple of 101 by the products of numbers. So it´s better to leave that choice for last, as + or - have higher chances of generating a multiple of 101 quicker.

Update: I have tried your resursion solver with the stopping when reaching to 0 remainder but it still gives time out in a few cases, so ended up trying a different approach: dynamic programming.

The trick is that 101 is small, so the possible remainders are only between 0 and 100. The idea is that when looking at the ith number, you don´t really care if the accumulated result from previous operations is 2 or 103 or 204, you only care that its remainder with 101 is 2.

With that in mind, we can make a boolean array where we will store the remainders that can be generated by a combination of operations using the previous numbers.

So for each of these remainders we can get with the previous numbers (0 to i - 1 ), the remainders we could possibly get in the ith step are the same but adding, substracting and multiplying the ith number by that remainder.

I decided to keep a 2 dimensional array, where the first dimension is the step and the second one the remainder: boolean[][] remainders = new boolean[10000][101];

So for each number in the array, if we are on the ith step we iterate remainders[i - 1] and look for the true values. For those, we set the new remainders[i][j + array[i]], remainders[i][j - array[i]], remainders[i][j * array[i]] to true.

Note that we need to add modulo to that to keep it between 0 and 100.

The complexity of this is N * 100. Considering worst case, 10^4 * 100 = 10^6 which should fit nicely in the given time.

With this done, we know for each step what remainders we can get. So according to the problem, remainders[array.length - 1][0] should always be true as it can always be obtained.

There is still the problem that we don´t know what operation we used for each step so we can´t reconstruct the operations just by storing these values in remainders. I suggest you to think over how to do this.

If you still can´t manage, here is my full code that passed the tests. I don´t usually use java so my code surely has some improvements to make.

          import java.io.;
        import java.util.;
        import java.text.;
        import java.math.;
        import java.util.regex.;

        public class Solution {

            static int array[];

            public static void main(String[] args) {
               Scanner s = new Scanner(System.in);
               int n = s.nextInt();
               array = new int[n];
               for (int i = 0; i < n; i++)
                   array[i] = s.nextInt();
               System.out.println(solve());
            }

            public static String solve () {
                boolean[][] remainders = new boolean[10000][101];
                Character[][] operators = new Character[10000][101];
                int[][] previousRemainder = new int[10000][101];

                remainders[0][array[0]] = true;

                for (int i = 1; i < array.length; i++) {
                    int num = array[i];

                    if (remainders[i - 1][0]) {
                        remainders[i][0] = true;
                        operators[i][0] = '';
                        previousRemainder[i][0] = 0;
                    } else {
                        for (int j = 0; j < 101; j++) {
                            if (remainders[i - 1][j]) {
                                remainders[i][Math.floorMod(j + num, 101)] = true;
                                operators[i][Math.floorMod(j + num, 101)] = '+';
                                previousRemainder[i][Math.floorMod(j + num, 101)] = j;

                                remainders[i][Math.floorMod(j - num, 101)] = true;
                                operators[i][Math.floorMod(j - num, 101)] = '-';
                                previousRemainder[i][Math.floorMod(j - num, 101)] = j;

                                remainders[i][Math.floorMod(j * num, 101)] = true;
                                operators[i][Math.floorMod(j * num, 101)] = '*';
                                previousRemainder[i][Math.floorMod(j * num, 101)] = j;
                            }
                        }
                    }

                }

                String result = Integer.toString(array[0]);
                Integer currentRemainder = 0;
                String[] operatorsResult = new String[10000];

                for (int i = array.length - 1; i >= 1; i--) {
                    operatorsResult[i] = Character.toString(operators[i][currentRemainder]);
                    currentRemainder = previousRemainder[i][currentRemainder];
                }

                for (int i = 1; i < array.length; i++) {
                    result += operatorsResult[i] + Integer.toString(array[i]);
                }

                return result;

            }
        }


Java "pulse" between threads I have two threads. One runs a simulation and one runs a UI.

In the UI, it is possible to trigger a "tick" of the simulation. There are a few constraints:

Ticks run on the simulation thread
Each tick takes a bit of time to complete.
When the user asks for n ticks, n ticks should be completed, even if they are requested during the execution of a tick.

To manage the triggering of ticks between threads, I have created a Pulse class. Here it is:

public final class Pulse {

    private final Object Lock = new Object();

    private volatile int count;

    public Pulse() {

        super();

        count = 0;
    }

    public void pulse() {

        synchronized (Lock) {

            count++;

            Lock.notifyAll();
        }
    }

    public void waitForPulse() throws InterruptedException {

        synchronized (Lock) {

            while (count == 0) {

                Lock.wait();
            }

            count--;
        }
    }
}

A single Pulse instance is shared between the UI and simulation threads.

In the UI thread I would have something like:

void onTickRequested() {

    simulationPulse.pulse();
}

And in the simulation thread I have something like:

while (isRunningSimulation) {

    myPulse.waitForPulse();

    tick();
}

Will my code work as expected? Is it thread-safe?

Good code! Just a few points:

super();

This line of code is automatically put in by the compiler and is unnecessary to write it yourself. If it is a habit that you have a hard time breaking, you may leave it, as it does not compromise speed, but I would leave it out, as it does clutter code slightly.
Over-spacing

Though spacing is good, too much space makes code hard to read as well. Your spacing is good, with one thing: you have a space between each line. Maybe it helps you, but I find it difficult to read.

Compare:

public final class Pulse {

    private final Object Lock = new Object();

    private volatile int count;

    public Pulse() {

        super();

        count = 0;
    }

    public void pulse() {

        synchronized (Lock) {

            count++;

            Lock.notifyAll();
        }
    }

    public void waitForPulse() throws InterruptedException {

        synchronized (Lock) {

            while (count == 0) {

                Lock.wait();
            }

            count--;
        }
    }
}

and:

public final class Pulse {

    private final Object Lock = new Object();
    private volatile int count;

    public Pulse() {
        super();
        count = 0;
    }

    public void pulse() {
        synchronized (Lock) {
            count++;
            Lock.notifyAll();
        }
    }

    public void waitForPulse() throws InterruptedException {
        synchronized (Lock) {
            while (count == 0) {
                Lock.wait();
            }
            count--;
        }
    }

}

Note that I've kept some spaces.
private final Object Lock = new Object();

Java conventions state that variable names are camelCase, not PascalCase. Change Lock to lock.


Writing structured file in C++ I have a file with an specific format. It's divided in stripes of 1058816 bytes:

4096 bytes with only a 64 bit unsigned integer.
An array of 512 64 bit unsigned integer.
An array of 512 32 bit unsigned integer.
An array of 512 elements with 2048 bytes each one.

I have to read the file, change some values and write it again.

This is what I'm doing to work with it:

struct Segment {
        char bytes[2048];
};

struct Metadata {
        uint64_t serial;
};

class Stripe {
        uint8_t ptr[STRIPE_SIZE];

        Metadata *metadata;
        uint64_t *hash_array;
        uint32_t *size_array;
        Segment *segment_array;

        do_something(fstream_obj)
        {
                fstream_obj.read(ptr, STRIPE_SIZE);

                metadata = new(ptr) COSSMetadata;
                hash_array = new(ptr + METADATA_BYTES) uint64_t[ARRAY_SIZE];
                size_array = new(ptr + METADATA_BYTES + HASH_ARRAY_BYTES) uint32_t[ARRAY_SIZE];
                segment_array = new(ptr + METADATA_BYTES + HASH_ARRAY_BYTES + SIZE_ARRAY_BYTES) Segment[ARRAY_SIZE];

                // .... code to change the the values.....

                fstream_obj.write(ptr, STRIPE_SIZE);

        }
};

I have more experience with C. I'm not sure if this is the best to do what I want. I think that is faster, because I'm not doing any conversion and the information in ptr already is in the format of the structures. I want to hear opinios of more experience C++ coderes.

I'm not 100% sure how idiomatic this is, but since your data is so structured, it might be worth representing the entire structure as just that: a POD struct that contains the exact sizes and layout desired.

struct Metadata {
    uint64_t serial;
    char _padding_[METADATA_BYTES - 8];
};

struct Segment {
    char bytes[2048];
};

struct Stripe {
    Metadata metadata;
    uint64_t hash_array[512];
    uint32_t size_array[512];
    Segment segment_array[512];
};

(There is probably a better way of doing the padding.)

This means that the layout in memory is exactly the same as the layout on disk, and new Stripe will allocate the appropriate amount of memory with all the components contiguous as desired, without having to do the specific placement yourself. This means you can just allocate the structure, then file.read(stripe, sizeof(Stripe)) and file.write(stripe, sizeof(Stripe)) directly.

You could put a wrapper class around it:

class Stripe {
    Stripe_struct data;

    // methods...
}

Or just convert the original Stripe struct to a class itself.


Implementing Option#map2 Working on an example from Functional Programming in Scala, I'm working on Option#map2:

override def map2[A, B, C](fa: Option[A],fb: Option[B])(f: (A, B) => C): Option[C] = {
  (fa, fb) match {
    case (None, _) => None
    case (_, None) => None
    case (_, _) => Some(f(fa.get, fb.get)) // runtime-safe get calls
  }
}

Is the above implementation reasonable? I presumed that, if either fa or fb were None, then so should be the returned value. Pattern matching seemed the most clean to me, but perhaps there's a cleaner or more concise way to write this method?

Your code is correct - it should work nicely.

The first thing that I would improve on is the // runtime-safe get calls. This is an anti-pattern in Scala and is generally discouraged. In this case you can use pattern matchings powerful extractors to get the value the Option is storing:

case (Some(a), Some(b)) => Some(f(a, b))

But instead of pattern matching the most elegant way to solve this problem is to use for comprehensions. It is functionally the same as your code:

override def map2[A, B, C](fa: Option[A], fb: Option[B])(f: (A, B) => C): Option[C] = {
  for {
    a <- fa
    b <- fb
  } yield f(a, b)
}

Since Option is essentially a collection with either zero or one element it can be used in for-comprehensions. The variable a will only be populated if fa is a Some. If either is None then nothing will be yielded and the result is None.


Project Euler #7 using Java streams I haven't written any Java in years and I wanted to catch up a little, especially on newer features. I started looking at streams and aggregate operations and came up with the following solution to Project Euler #7 (find the 10001st prime).

package com.example;
import java.util.stream.IntStream;
import org.apache.commons.lang3.time.StopWatch;

public class Main {
    static boolean isPrime(int i) {
        int limit = (int)Math.sqrt(i)+1;
        return !IntStream.range(2, limit)
                .anyMatch(n -> i % n == 0);
    }

    public static void main(String[] args) {
        StopWatch stopWatch = new StopWatch();
        int n = 10001;
        stopWatch.start();
        int nthPrime = IntStream.iterate(2, i -> i+1)
                .filter(Main::isPrime)
                .skip(n-1)
                .findFirst().getAsInt();
        stopWatch.stop();
        System.out.printf("The %dth prime is %d\n", n, nthPrime);
        System.out.printf("Execution time: %.2fs\n", (float)stopWatch.getTime()/1000);
    }
}

Is there any obvious way to speed it up? Am I overcomplicating something? My way of getting an infinite sequence of integers, for example. Any other feedback?

Is there any obvious way to speed it up? Am I overcomplicating something? My way of getting an infinite sequence of integers, for example. Any other feedback?

Well, the easiest way to speed it up is to note that there is only one even prime.  So set n to 10000, start with 3 rather than 2, increment by 2 rather than 1, and you can start your isPrime range with 3 as well.  It's unclear how much impact this will have, as at least those values were easy to filter.

If you have sufficient memory, you can save the generated primes and use those to do your isPrime check.  You spend a lot of time checking numbers that you know won't divide the candidate.  For example, you check even numbers larger than 2.

If efficiency is your goal, I'm not sure that streams are the way to go.  Streams are compact to write but may be difficult to optimize.  The argument in favor of streams here is that for small n, being quicker to write is more advantageous than being quick to run.

Of course, your real question may be "Given that I'm using streams, what features could I use?  Not so much on this problem but on other problems where they might matter more?"

Some things that I might do in a non-stream solution that I don't know how to do with a stream (may be impossible).

Only generate a range of odd numbers in isPrime.  Note that I've considered

    int limit = (int)(Math.sqrt(i) / 2);
    return IntStream.range(1, limit)
            .noneMatch(n -> i % (2 * n + 1) == 0);

But that seems wasteful.  It requires two additions and a multiplication to do what a for loop could do with a single addition.  You may want to clock it to see if it's more efficient than your solution.  Probably heavily dependent on the relative efficiencies of multiplication and modulus.  Unless the compiler is smart enough to compile out the multiplication.

What I really want is to either be able to set an increment to range or a limit to iterate.  Either would work.  Neither seems to be available.

Note that I find noneMatch to be easier to read than !anyMatch.
Skip every third odd number after 3.  Note that 3, 5, and 7 are all prime but 9 is not.  11 and 13 are but 15 is not.  17 and 19 are but 21 is not.  What do 9, 15, and 21 have in common?  They're all divisible by 3.  The iterative way to do this is something like

    increment = 6 - increment;
    i += increment;

Where increment starts as either 2 or 4 and will alternate between them (\$6-2=4\$ and \$6-4=2\$).
Use a sieve (e.g. Sieve of Eratosthenes) so as to mask out future values.  Another challenge here is that a sieve doesn't fit this problem well.  It finds all the primes in a range, but here you want to find a certain number of primes, not all the primes less than some maximum value.


Singleton implementation of a database connection I have implemented as follows, a class applying singleton pattern to get a global single access to database.
I intend to provide a thread-safe implementation.

using System.Data.SqlClient;

public sealed class Database
    {
        private static volatile SqlConnection instance;
        private static object syncRoot = new object();
        private const string connectionString = "Data Source=ServerName;" +
                                                "Initial Catalog=DataBaseName;" +
                                                "User id=UserName;" +
                                                "Password=Secret;";

        private Database() { }

        public static SqlConnection Instance
        {
            get
            {
                if (instance == null)
                {
                    lock (syncRoot)
                    {
                        if (instance == null)
                            instance = new SqlConnection(connectionString);
                    }
                }

                return instance;
            }
        }
    }

As per the docs

https://msdn.microsoft.com/en-us/library/system.data.sqlclient.sqlconnection(v=vs.90).aspx

  Any public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe.

This means that while the Singleton instance can be technically correct, it is not correct in this specific context of the SqlConnection class if you plan to access instance members from different threads (and you possibly do).


Python terminal animation Is there a better way of creating this terminal animation without having a series of conditional statements (i.e. if ... elif ... elif...)?

import sys, time
count = 100
i = 0
num = 0

def animation():
    global num
    if num == 0:
        num += 1
        return '[=      ]'
    elif num == 1:
        num += 1
        return '[ =     ]'
    elif num == 2:
        num += 1
        return '[  =    ]'
    elif num == 3:
        num += 1
        return '[   =   ]'
    elif num == 4:
        num += 1
        return '[    =  ]'
    elif num == 5:
        num += 1
        return '[     = ]'
    elif num == 6:
        num += 1
        return '[      =]'
    elif num == 7:
        num += 1
        return '[      =]'
    elif num == 8:
        num += 1
        return '[     = ]'
    elif num == 9:
        num += 1
        return '[    =  ]'
    elif num == 10:
        num += 1
        return '[   =   ]'
    elif num == 11:
        num += 1
        return '[  =    ]'
    elif num == 12:
        num += 1
        return '[ =     ]'
    elif num == 13:
        num = 0
        return '[=      ]'

while i < count:
    sys.stdout.write('\b\b\b')
    sys.stdout.write(animation())
    sys.stdout.flush()
    time.sleep(0.2)

You can build up the string like this:

def animation(counter, length):
    stage = counter % (length * 2 + 2)
    if stage < length + 1:
        left_spaces = stage
    else:
        left_spaces = length * 2 - 1 - stage
    return '[' + ' ' * left_spaces + '=' + ' ' * (length - left_spaces) + ']'

for i in range(100):
    sys.stdout.write('\b\b\b')
    sys.stdout.write(animation(i, 6))
    sys.stdout.flush()
    time.sleep(0.2)

Alternatively store the animation strings in a tuple or list:

animation_strings = ('[=      ]', '[ =     ]', '[  =    ]', '[   =   ]',
                     '[    =  ]', '[     = ]', '[      =]', '[      =]',
                     '[     = ]', '[    =  ]', '[   =   ]', '[  =    ]',
                     '[ =     ]', '[=      ]')
for i in range(100):
    sys.stdout.write('\b\b\b')
    sys.stdout.write(animation_strings[i % len(animation_strings)])
    sys.stdout.flush()
    time.sleep(0.2)

You can replace the animation function with cycle from itertools:

import sys, time
from itertools import cycle
animation = cycle('[=      ]', '[ =     ]', '[  =    ]', '[   =   ]',
                  '[    =  ]', '[     = ]', '[      =]', '[      =]',
                  '[     = ]', '[    =  ]', '[   =   ]', '[  =    ]',
                  '[ =     ]', '[=      ]')
# alternatively:
# animation = cycle('[' + ' ' * n + '=' + ' ' * (6 - n) + ']'
#                   for n in range(7) + range(6, -1, -1))

for _ in range(100):
    sys.stdout.write('\b\b\b')
    sys.stdout.write(animation.next())
    sys.stdout.flush()
    time.sleep(0.2)

Finally, you could make your own generator function.

def animation_generator(length):
    while True:
        for n in range(length + 1):
            yield '[' + ' ' * n + '=' + ' ' * (length - n) + ']'
        for n in range(length + 1):
            yield '[' + ' ' * (length - n) + '=' + ' ' * n + ']'

animation = animation_generator(6)
for _ in range(100):
    sys.stdout.write('\b\b\b')
    sys.stdout.write(animation.next())
    sys.stdout.flush()
    time.sleep(0.2)

EDIT: made the above suggestions less reliant on global variables


Displaying model statistics (as a sentence) in a view A Rails 4.2 app has three models:

User
Author
Quote

... and the following associations:

users HABTM authors
author has_many quotes

If the user is associated with any authors, his "profile" view should display statistics about the number of quotes of each author.

Example:

  Your author(s) Mark Twain has 73 quotes, Charles Dickens has 92 quotes, and Oscar Wilde has 53 quotes.

If the user is not associated with any authors, that same view should display a different message.

Within the user model (app/models/user.rb):

def authors_statistics
  statistics = Array.new
  self.authors.each do |author|
    statistics << "#{author.name} has #{author.quotes.count} quotes"
  end
  statistics.to_sentence
end

Within the user profile view (ERB):

<% if current_user.authors_statistics.empty? %>
    You have not yet been given access to edit any authors&#39; quotes. Please
    <%= link_to 'send us a message', new_contact_form_path %> specifying to
    whose authors quotes you would like to contribute.
<% else %>
    Your author(s) <%= current_user.authors_statistics %>
<% end.to_sentence %>.

It seems to me that there is excessive coupling between the model and the view. Can you think of a better way to do it?

I'd add a counter cache to Author, i.e. quote_count just to avoid doing the extra query to fetch the number of quotes.

Don't put view concerns (the sentence, in this case) in a model; use I18n/localization instead, especially since you're dealing with pluralization (and right now you're taking the lazy route of saying author(s) and assuming quotes, plural).

Even if there's only English, the I18n stuff can do some tricks, for instance (in config/locales/en.yml or similar):

en:
  users:
    show:
      your_authors:
        one: "Your author"
        other: "Your authors"
      author_quotes:
        one: "%{name} has %{count} quote"
        other: "%{name} has %{count} quotes"

With that your view can be something like:

<%= t(".your_authors", count: @authors.count) %>
<%= @authors.map { |author| t(".author_quotes", name: author.name, count: author.quotes.size }.to_sentence %>

And #author_statistics can be removed entirely.


Using Func instead of helper methods in a class I really like functional programming in C#, it gives you a lot of flexibility.
I am wondering if it is the right idea to use functions instead of helper methods, and to make the code more readable.

So here is what I want, I have a method that needs to find Saturday and do something with it:

public void SomeMethod()
{
    var saturday = DateTime.Today;
    while (saturday.DayOfWeek != DayOfWeek.Saturday)
            saturday = saturday.AddDays(-1);

    //rest of the code
}

The problem I am having with this code is readability. I have to scan through 3 lines of code to understand that it needs to find Saturday. Plus seeing var saturday = DateTime.Today;, it really bugs my eyes.

Of course I can write a helper method

private DateTime GetSaturday()
{
    var saturday = DateTime.Today;
    while (saturday.DayOfWeek != DayOfWeek.Saturday)
            saturday = saturday.AddDays(-1);
    return saturday;
}

Now I know exactly what the method does but my problem now is that I know that I won't be calling this method anywhere in the class so it kind of pollutes my class.

So here we are at my favorite:

public void SomeMethod()
{
    Func<DateTime> GetSaturdayFunc = () =>
        {
            var date = DateTime.Today;
            while (date.DayOfWeek != DayOfWeek.Saturday)
                date = date.AddDays(-1);
            return date;
        };

   var saturday = GetSaturdayFunc();
   //rest of the code
}

Although it's a bit more code now my class is not polluted with a lot of utility methods and it is more readable.

What do you think? Is this a good way, are there any better ways?

EDIT

I could also create an extension method which in this case would be appropriate, something like

DateTime.Saturday()

but that's not what I am referring to in my question. I am asking if it is a good practice to wrap a portion of the code as a function inside that method (since that peace of the code will only be used inside that method and might not apply anywhere else), just for readability purposes.

This is a perfect use case for an extension method. It gives maximum readability to your business code, and makes the method available on any DateTime object.

//Test
class Program
{
    static void Main(string[] args)
    {
        Console.Write(DateTime.Today.MostRecent(DayOfWeek.Saturday));
        Console.Read();
    }
}
//Extensions
public static class DateTimeExtensions
{
    public static DateTime MostRecent(this DateTime date, DayOfWeek dayOfWeek)
    {
        var day = date.Date;
        while (day.DayOfWeek != dayOfWeek)
            day = day.AddDays(-1);
        return day;

    }
}


C++ merging sorted linked lists I'd like to see if there's any code reuse I'm missing, or anything else that can be rewritten in a better way, but always following the same data structures (without adding more classes or using the C++ list implementation).

Node* merge(Node* list1, Node* list2){
    if (list1 == nullptr){
        return list2;
    }
    else{
        if (list2 == nullptr){
            return list1;
        }
        else{
            Node* newList = nullptr;
            if (list1->data <= list2->data){
                newList = list1;
            }
            else{
                newList = list2;
            }
            while (list1->next != nullptr) {
                if (list1->next->data > list2->data){
                    Node* aux = list1->next;
                    list1->next = list2;
                    list2 = aux;
                }
                list1 = list1->next;
            }
            if (list1->next == nullptr){
                list1->next = list2;
            }
            return newList;
        }
    }
}

I would do a couple of things differently.
Early escape
Your use of early escape is good and makes the code easier to read but you don't need the else section if the body of if statement returns.
Node* merge(Node* list1, Node* list2)
{
    if (list1 == nullptr){
        return list2;
    }
    if (list2 == nullptr){
        return list1;
    }
    // Main body of code.

This is quite normal. It reduces the number of level of indenting and makes the code look clean.
Self documenting code
I would encourage you to split getting the next item into a separate function (this facilitates self documenting code).
Node* getNextNode(Node*& list1, Node*& list2)
{
    // Work out which list has the smallest value.
    Node*& smallList = (list1->data < list2->data) ? list1 : list2;

    // The head of this list is the result
    Node* result = smallList;

    // Move the list to the next value (notice the call be reference).
    smallList = smallList->next;

    return result;
}

Simplified Body
Now if we rewrite the main body of your code in terms of this helper function;
Node* result  = getNextNode(list1, list2);
Node* current = result;

// Looping over the list until one is empty
// becomes very trivial now.
while(list1 != nullptr && list2 != nullptr)
{
     // Get next node and remove it from its list.
     Node* next    = getNextNode(list1, list2);
     current->next = next;
     current       = next;
}

// One of the lists is empty.
// Add what is left of the other list on the end (ie after current).
current->next = (list1 == nullptr) ? list2 : list1;
return result;


Python adventure game with a deadly cat I wrote a small "game" in Python for practice. I would like if someone could go over it and tell me if there is anything wrong or if there are any improvements I can make.

import time
import sys
class Creature:
    def __init__(self, name, hp, inventory):
        self.name = name
        self.hp = hp
        self.inventory = inventory
    def get_hp(self):
        return self.hp
    def get_name(self):
        return self.name
    def get_inventory(self):
        return self.inventory
    def add_item(self, item):
        self.inventory.append(item)
class Item:
    def __init__(self, name, damage, special):
        self.name=name
        self.damage=damage
        self.special=special

staff = Item("heroStaff", 2, "Nothing")
heroinv = [] # Hero inventory
Hero = Creature("A hero",100,heroinv)
print("You wake up in a dark room")
time.sleep(1)
print("1: Sleep more")
print("2: Look around")
key = input()
if key == "1":
    print("You keep sleeping. Good night")
    time.sleep(1)
    print(".")
    time.sleep(1)
    print(".")
    time.sleep(1)
    print(".")
    print("You wake up, feeling restored, you decide to look around")
time.sleep(1.5)
out = False
emptybox = False
door1key=False
while not out:
    print("")
    print("You look around and find a door, a window, and a box")
    time.sleep(1)
    print("1: Check door")
    print("2: Check window")
    print("3: Check box")
    key = input()
    if key == "1":
        time.sleep(0.5)
        print("trying to unlock door")
        time.sleep(1)
        print(".")
        time.sleep(1)
        if not out:
          for items in Hero.get_inventory():
                if items.name == "Door1Key":
                    print("CLICK!")
                    time.sleep(1)
                    print("*Door opened*")
                    time.sleep(1)
                    out = True
                    door1key=True
        if not door1key:
            print("Door Could not be opened")
            time.sleep(1)
    if key=="2":
        print("The window is locked. Can't break it")
        time.sleep(0.5)
    if key=="3":
        if not emptybox:
            time.sleep(0.5)
            print("You open the chest and find a staff(2 damage) and a key, you take them")
            key=Item("Door1Key",0,"Nothing")
            Hero.add_item(key)
            Hero.add_item(staff)
            time.sleep(2)
            emptybox = True
        else:
            print("The box is empty")
            time.sleep(0.5)

print("You step out of the room")
time.sleep(1)
print("You see an infected cat in front of you, with death in his eyes.")
time.sleep(2)
strkill="HE WANTS TO KILL YOU."
for char in strkill:
    if char==' ':
        sys.stdout.write(char)
        sys.stdout.flush()
        time.sleep(0.5);
    else:
        sys.stdout.write(char)
        sys.stdout.flush()
        time.sleep(0.2);
print("")
time.sleep(1)
print("*Infected cat engages*")

One improvement would be to simplify this:

    if not out:
        for items in Hero.get_inventory():
            if items.name == "Door1Key":
                print("CLICK!")
                time.sleep(1)
                print("*Door opened*")
                time.sleep(1)
                out = True
                door1key=True
    if not door1key:
        print("Door Could not be opened")
        time.sleep(1)

into this:

    if "Door1Key" in [_.name for _ in Hero.get_inventory()]:
        print("CLICK!")
        time.sleep(1)
        print("*Door opened*")
        time.sleep(1)
        break
    else:
        print("Door could not be opened")
        time.sleep(1)

You don't need "if not out:" at the top of this -- you're in a "while not out" loop and out hasn't had a chance to change since the top of the loop.

The "for items" loop just scans through the inventory looking to see if you have the door key. That can be done in a single statement, as I show.

Once you've opened the door, you're out, so we can just break out of the "while not out" loop and carry on from there.

Several of your descriptions are hard-coded:

print("You look around and find a door, a window, and a box")
print("You open the chest and find a staff(2 damage) and a key, you take them")
print("You see an infected cat in front of you, with death in his eyes.")

For the room, you could do something like

room = {'entrances': ['door', 'window'],
        'contents': ['box']}
print("You look around and find " +
      ', '.join(['a ' + _ for _ in room.entrances] +
      'and ' + ', '.join(room.contents))

The idea is that rather than embedding your data in the code, you should structure it in a meaningful way, then use generic code to present the data from the structures in the way you want the player to see it.

I think you're on the right track with your Creature and Item classes. I think maybe you want more classes like Place (or Room), Container (to represent boxes, chests, hidey holes, etc.). If you have to write specific logic for each step in the story, your game is going to be very linear and you'll be limited in how much branching and looping you can manage.

On the other hand, if your game is just a network of Places connected to each other with Items, Containers, other Creatures and such scattered throughout for the Hero to encounter and either fight or befriend, and the Hero is free to wander from Place to Place backward and forward and in loops, then the game becomes much less predictable and more interesting.

What would the code look like to process such a network of Places, Items, Containers, Creatures, and whatever else you can dream up?


Simplified DES encryption This is one of my first Python scripts and I was wondering if it meets the correct conventions. Also are there things that you would write different? I am looking for some good comments so I can start to improve my Python code from the start. (I was not supposed to use imports here)

Here's my implementation of Simplified DES:

__author__ = 'ßaron'

FIXED_IP = [2, 6, 3, 1, 4, 8, 5, 7]
FIXED_EP = [4, 1, 2, 3, 2, 3, 4, 1]
FIXED_IP_INVERSE = [4, 1, 3, 5, 7, 2, 8, 6]
FIXED_P10 = [3, 5, 2, 7, 4, 10, 1, 9, 8, 6]
FIXED_P8 = [6, 3, 7, 4, 8, 5, 10, 9]
FIXED_P4 = [2, 4, 3, 1]

S0 = [[1, 0, 3, 2],
      [3, 2, 1, 0],
      [0, 2, 1, 3],
      [3, 1, 3, 2]]

S1 = [[0, 1, 2, 3],
      [2, 0, 1, 3],
      [3, 0, 1, 0],
      [2, 1, 0, 3]]

KEY = '0111111101'

def permutate(original, fixed_key):
    new = ''
    for i in fixed_key:
        new += original[i - 1]
    return new

def left_half(bits):
    return bits[:len(bits)/2]

def right_half(bits):
    return bits[len(bits)/2:]

def shift(bits):
    rotated_left_half = left_half(bits)[1:] + left_half(bits)[0]
    rotated_right_half = right_half(bits)[1:] + right_half(bits)[0]
    return rotated_left_half + rotated_right_half

def key1():
    return permutate(shift(permutate(KEY, FIXED_P10)), FIXED_P8)

def key2():
    return permutate(shift(shift(shift(permutate(KEY, FIXED_P10)))), FIXED_P8)

def xor(bits, key):
    new = ''
    for bit, key_bit in zip(bits, key):
        new += str(((int(bit) + int(key_bit)) % 2))
    return new

def lookup_in_sbox(bits, sbox):
    row = int(bits[0] + bits[3], 2)
    col = int(bits[1] + bits[2], 2)
    return '{0:02b}'.format(sbox[row][col])

def f_k(bits, key):
    L = left_half(bits)
    R = right_half(bits)
    bits = permutate(R, FIXED_EP)
    bits = xor(bits, key)
    bits = lookup_in_sbox(left_half(bits), S0) + lookup_in_sbox(right_half(bits), S1)
    bits = permutate(bits, FIXED_P4)
    return xor(bits, L)

def encrypt(plain_text):
    bits = permutate(plain_text, FIXED_IP)
    temp = f_k(bits, key1())
    bits = right_half(bits) + temp
    bits = f_k(bits, key2())
    print permutate(bits + temp, FIXED_IP_INVERSE)

def decrypt(cipher_text):
    bits = permutate(cipher_text, FIXED_IP)
    temp = f_k(bits, key2())
    bits = right_half(bits) + temp
    bits = f_k(bits, key1())
    print permutate(bits + temp, FIXED_IP_INVERSE)

encrypt('11101010')
decrypt('10100010')

If you're using constants that are collections you'd be better off making them tuples, not lists. Trying to modify a tuple will raise an error as they're immutable, and using the tuple syntax makes it extra clear that these are unchanging constants.

FIXED_IP = (2, 6, 3, 1, 4, 8, 5, 7)
FIXED_EP = (4, 1, 2, 3, 2, 3, 4, 1)

As Caridorc said, using str.join is faster (depending on your version). It would also allow you to make permutate just one line.

def permutate(original, fixed_key):
    return ''.join(original[i - 1] for i in fixed_key)

It would also be a bit faster to pre-convert all your values in bits and key to integers. You can use map to apply a function to every member of a list, and it's faster than doing it in a list. You could do this when creating the zip object.

def xor(bits, key):
    new = ''
    for bit, key_bit in zip(map(int, bits), map(int, key)):
        new += str(((bit + key_bit) % 2))
    return new

Of course if you wanted this could also be made into a str.join, albeit a long one:

def xor(bits, key):
    return ''.join(str(((bit + key_bit) % 2)) for bit, key_bit in
                   zip(map(int, bits), map(int, key)))

There's a lot of functions here but not a lot of documentation. Explaining what individual functions do would make your code a lot easier to read. And I suspect you have some unnecessary duplicate functions, where you could pass a parameter instead of defining a whole new one. But it's hard to know when I don't entirely understand the functions you have here.


Loading a pseudo-class instance from JSON Is there a better way to do this?

function Person(name)
{
    this._type='Person';
    this.name=name;

    this.hello = function(){
        alert('Hello '+this.name);
    };
}

function object_to_instance(key, value)
{
    if (!value.hasOwnProperty('_type'))
        return value;

    var obj= eval('new '+value._type+'()');

    for (var property in value)
        obj[property]=value[property];
    return obj;
}

var people = [new Person('Harry'), new Person('Sally')];

var people_json = JSON.stringify(people);

var new_people = JSON.parse(people_json, object_to_instance);
new_people[0].hello();

Instead of eval, you could create a Person constructor that accepts an object:

function Person(arg)
{
    if (typeof arg === 'string')
    {
        var name = arg;
        this._type='Person';
        this.name=name;
    }
    else if (typeof arg === 'object')
    {
        var value = arg;
        for (var prop in value)
        {
            if (value.hasOwnProperty(prop))
            {
                this[prop] = value[prop];
            }
        }
    }
}

// Move Person.hello() into the prototype
Person.prototype.hello = function()
{
    alert('Hello '+this.name);
};

Then use the _type to choose a constructor based on a predefined set of classes, rather than a (potentially) unsafe eval:

var classes =
{
    Person: Person
    /* other potential classes to deserialize from here as well */
};

function object_to_instance(key, value)
{
    if (!value._type) return value;
    return new classes[value._type](value);
}

var people = [new Person('Harry'), new Person('Sally')];
var people_json = JSON.stringify(people);
var new_people = JSON.parse(people_json, object_to_instance);
new_people[0].hello();

Basic demo: http://jsfiddle.net/mattball/VfRJn
Using multiple classes: http://jsfiddle.net/mattball/VfwRv


Verifying boardgame mathematics with MATLAB I recently bought this math-based boardgame for my little cousins, and am now trying to verify its design with some MATLAB code. The relevant parts of the game are:

A board with numbers from 1 to 100 in one tile each, and each tile colored in one of nine colors
There are three dice, the usual kind  (1-6)
In your turn, you roll all three dice. You have three numbers x, y and z now, from the dice. Now, using these three numbers, and applying the four basic math operations on them (+, -, *, /) in any order, you must arrive at one of the numbers on the board (i.e. from 1 to 100). The catch is, the resulting numbers have scores based on their color on the board, so that for eg. arriving at 13 or 26 (red tile) gives you a much higher score compared to arriving at 25 (pink). So if you die values are 5, 5, 1, you're much better off going with (5*5+1) = 26 than with (5*5*1) = 25. Choosing these operations right in each turn is the crux of the game.

Now, the part I had doubts about was the coloring of the tiles - were they really colored
according to the difficulty of arriving at them? That seemed easy enough to verify - find the frequency of occurrence of each number from 1 to 100 given three dice and four mathematical operations - and so that's what this MATLAB code attempts to do:

function freq = compute_freq

idx = 1;
for x = 1:6
    for y = 1:6
        two_die_combos = get_combos(x, y);
        for z = 1:6
            three_die_combos = get_combos(two_die_combos, z);

            valid_combos = three_die_combos(three_die_combos > 0 & ...
                                                three_die_combos <= 100 & ...
                                                (three_die_combos == floor(three_die_combos))); % only integer values
            all_combos(idx:idx + length(valid_combos) - 1) = valid_combos;
            idx = idx+length(valid_combos);
        end
    end
end
freq = tabulate(all_combos);

end

function combos = get_combos(a, b)

num_results = length(a) * 6 * length(b);
combos = zeros(1, num_results);
idx = 1;
for x = a
    for y = b
        combos(idx) = x + y;
        combos(idx + 1) = x - y;
        combos(idx + 2) = -x + y;
        combos(idx + 3) = x * y;
        combos(idx + 4) = x / y;
        combos(idx + 5) = x \ y;
        idx = idx + 6;
    end
end

end

I get some frequency values from this, but:

first of all, I have no way of verifying the correctness of results themselves, so I would like to know if there are any logical errors in the code
secondly, I'd love feedback on the quality of the code itself. Loops within loops make me feel icky, but there doesn't seem to be any other reasonable way of doing this (one other option that occurred to me was having character arrays like ['1' '2' '3' '4' '5' '6'] and ['+' '-' '*' '/'], using MATLAB's permutation functions to get all possible expressions and then eval them, but that has complications with commutativity and order, and also... eval!). Am I missing some other better option?

Discussion

You have three dice, which you can assume to hold three places for 1, 2, 3, 4, 5, 6 and the four operations +, -, *, / would hold the two in-between places, which are shown as square brackets and round brackets respectively as shown in this blueprint - [] () [] () [].

The total number of possible combinations would be 6*4*6*4*6 = 3456. Out of these, you need to find the valid ones based on flooring and values in the range [1 100].

Looking at your code, I don't think -x+y would be a valid one, because you can't just pre-append a operator. If that is to be allowed, why not multiplication operator too? Moreover -x essentially means -1*x, for which you are already using two operators - - and * and assuming one of y or z to be 1. For these reasons, I am guesstimating, -x+y to be an invalid one, unless it says in the instructions manual to be a valid one.

Again, x\y won't induce anything new, as we are already juggling through all values of 1 to 6 across all three places around the four operators, as shown in the blueprint earlier.

Code

Considering all the assumptions and avoiding the "scandalous" cases, we would have this vectorized code -

%// Define possible values of x, y and z, denoting values from three dice
x = 1:6;
y = 1:6;
z = 1:6;

%// t1 would take care of x and y and the one operator in between
t1 = [bsxfun(@plus,x',y) ; bsxfun(@minus,x',y) ; bsxfun(@times,x,y') ; bsxfun(@rdivide,x,y')]

%// t2 would take care of x, y and z and the two operators in between
t2 = [bsxfun(@plus,t1(:),z) ; bsxfun(@minus,t1(:),z) ; bsxfun(@times,t1(:),z) ; bsxfun(@rdivide,t1(:),z)]

%// Get the valid ones based on flooring and limiting within the range [1 100]
t2 = t2(t2==floor(t2) & t2<=100 & t2>=1)
freq = tabulate(t2)

Output

freq =
    1.0000  151.0000    7.6186
    2.0000  157.0000    7.9213
    3.0000  146.0000    7.3663
    4.0000  148.0000    7.4672
    5.0000  130.0000    6.5590
    6.0000  150.0000    7.5681
    7.0000   94.0000    4.7427
    8.0000  106.0000    5.3481
    9.0000   87.0000    4.3895
   10.0000   89.0000    4.4904
   11.0000   53.0000    2.6741
   12.0000   91.0000    4.5913
   13.0000   35.0000    1.7659
   14.0000   37.0000    1.8668
   15.0000   46.0000    2.3209
   16.0000   36.0000    1.8163
   17.0000   14.0000    0.7064
   18.0000   41.0000    2.0686
   19.0000   10.0000    0.5045
   20.0000   34.0000    1.7154
   21.0000   16.0000    0.8073
   22.0000   10.0000    0.5045
   23.0000    7.0000    0.3532
   24.0000   42.0000    2.1191
   25.0000   16.0000    0.8073
   26.0000    7.0000    0.3532
   27.0000   10.0000    0.5045
   28.0000   11.0000    0.5550
   29.0000    5.0000    0.2523
   30.0000   33.0000    1.6650
   ......

Observation

freq percentage value for 26 [red colored] is 0.3532 that is slightly lower than for 25 [pink colored] which has 0.8073. Similarly, for 13 [red colored] it is 1.7659, that is again slightly lower than for 15 [looks like pink colored], which has 2.3209.

To confirm, you can create another column to the "tabulated" one and mark different weights for each number from 1 to 100 based on their colors. Then, see if such a pattern continues across the entire board. Good luck and hope this would make sense!


jQuery click handlers to show one of four containers I have a navigation bar that when the list elements are clicked their respective body container appears and the other body containers disappear.

navigation

HOME

ABOUT

PROJECTS

CONTACT

body containers:

home

about

projects

contact

JQuery:

$(document).ready(function () {
    $("#home").click(function(){
        event.preventDefault();
        $("#aboutBodyContainer").hide();
        $("#projectsBodyContainer").hide();
        $("#contactBodyContainer").hide();
        $("#homeBodyContainer").fadeIn(1500);
    });
    $("#about").click(function(){
        event.preventDefault();
            $("#homeBodyContainer").hide();
            $("#projectsBodyContainer").hide();
            $("#contactBodyContainer").hide();
            $("#aboutBodyContainer").fadeIn(1500);
    });
    $("#projects").click(function(){
        event.preventDefault();
        $("#homeBodyContainer").hide();
        $("#aboutBodyContainer").hide();
        $("#contactBodyContainer").hide();
        $("#projectsBodyContainer").fadeIn(1500);
    });
    $("#contact").click(function(){
        event.preventDefault();
        $("#homeBodyContainer").hide();
        $("#projectsBodyContainer").hide();
        $("#aboutBodyContainer").hide();
        $("#contactBodyContainer").fadeIn(1500);
    });
});

As you can see the functions are almost identical. Is there a way I can reduce the amount of code here?

Here you can write a simple logic to identify container div on the basis of anchor id.

Please see below code:

put class="container" for all container div, like below :

home

about

projects

contact

And jQuery is :

$(document).ready(function () {
    $("li a").click(function(){
        event.preventDefault();
        // hide all container div
        $(".container").hide();

        // get id of clicked anchor and create its corresponding container id
        var anchorId = $(this).attr('id');
        var containerId = anchorId+"BodyContainer";
        $("#"+containerId).fadeIn(1500);
    });

});

Note : It would be better idea to assign same class to anchor, so that if you have some other anchor available in your HTML then also you can easily bind click event to all desired anchor.

Example:

Assign class="anchorToClick" to all desired anchor tags

and jQuery will be like

$(document).ready(function () {
        $(".anchorToClick").click(function(){
            // your stuff here
          });

    });


Display search results for TV shows I haven't been coding super long in this language so if someone could take a look and help me improve my code and make it more efficient, that would be great! The HTML is one input field that you can type a show and then you get the result on the screen. From the beginning you get the top ten shows with the highest rating from the API.

// from start show the tv shows with highest rating
fetch('https://api.tvmaze.com/shows')
    .then(blob => blob.json())
    .then(json => {
        const topTenShows = json
        .filter(show => show.rating.average)
        .sort((a, b) => a.rating.average > b.rating.average ? -1 : 1)
        .slice(0, 9) // tar element 0-9 i arrayen
         return topTenShows
  })
  .then(shows => {
      const app = document.getElementById('app')

      app.innerHTML = shows.map(show => `

                  ${show.image ? `<img src="${show.image.medium}">` : `<img class="fallbackImage"src="design/icons/No_image_available.svg">`}

${show.name}

      `).join(' ');
    })

// show the search results from user input
function searchTvShows ({ target }) {
    fetch(`https://api.tvmaze.com/search/shows?q=${target.value}`)
        .then(blob => blob.json())
        .then(shows => {
            const app = document.getElementById('app');

            app.innerHTML = shows.map(({ show }) => `

                        ${show.image ? `<img src="${show.image.medium}">` : `<img class="fallbackImage"src="design/icons/No_image_available.svg">`}

${show.name}

        `).join(' ');
    })
  }

  const inputSearchField = document.querySelector('.inputSearchField')

  inputSearchField.addEventListener('keydown', searchTvShows)

Since in both instances HTML is the same, it could be extracted to another function;
target.value appended to the URL needs to go through EncodeURIComponent() to avoid bugs, surprises and even XSS;
topTenShows has actually only 9 shows. Second argument of .slice() is exclusive;
It would be better to listen to input event instead of keydown. Right now, when you type, the last character doesn't make it into request.

Rewrite

const app              = document.querySelector('#app'),
      inputSearchField = document.querySelector('.inputSearchField'),
      apiEndpoint      = 'https://api.tvmaze.com',
      noImagePath      = 'design/icons/No_image_available.svg';

/**
 * For each object representing one show, creates HTML source and sets them all as content of #app
 * @param  {object} shows Array containing objects representing API results
 * @return {string}       HTML that got set as content of #app (unused)
 */
const buildShowsHTML = shows => {
  app.innerHTML = shows.map(obj => {
    const show = obj.show || obj;
    const img = show.image ? `<img src="${show.image.medium}"/>` : `<img class="fallbackImage" src="${noImagePath}"/>`;

    return `

          ${img}

${show.name}

`;
  }).join('');
};

/**
 * Gets top 10 shows from the input array of objects
 * @param  {object} arr Array containing objects representing API results
 * @return {object}     Array of top 10 shows
 */
const getTopTenShows = arr => arr
  .filter(show => show.rating.average)
  .sort((a, b) => a.rating.average > b.rating.average ? -1 : 1)
  .slice(0, 10); // tar element [0 – 10) i arrayen

// Show top 10 shows upon load
fetch(`${apiEndpoint}/shows`).then(resp => resp.json()).then(getTopTenShows).then(buildShowsHTML);

// Show the search results on user input
inputSearchField.addEventListener('input', event => {
  const input = encodeURIComponent(event.target.value);
  fetch(`${apiEndpoint}/search/shows?q=${input}`).then(resp => resp.json()).then(buildShowsHTML);
});
<!DOCTYPE html>

  <meta charset="utf-8"/>
  <meta name="viewport" content="width=device-width"/>
  <link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet" type="text/css"/>
  <title>Demo</title>

  <input class="inputSearchField"/>


Improve my copying of a CSV file I need to merge some large csv files but I feel that the way I am doing it is not optmized. It gets a number of csvfiles and creates one

public static void MergeFiles(IEnumerable<string> csvFileNames, string outputPath)
{
    var sb = new StringBuilder();
    bool hasHeader = false;
    foreach (string csvFileName in csvFileNames)
    {
        TextReader tr = new StreamReader(csvFileName);
        string headers = tr.ReadLine();
        if (!hasHeader)
        {
            sb.AppendLine(headers);
            hasHeader = true;
        }
        sb.AppendLine(tr.ReadToEnd());
    }
    File.WriteAllText(outputPath, sb.ToString());
}

Any suggestion or code snippets?

StreamReader is IDisposable and therefor the use of it should be wrapped in a using block like this:

using (TextReader tr = new StreamReader(csvFileName))
{
    ...
}

You are reading all files into memory and then writing it out. While this probably has a fairly good performance as it's first performing a bunch of (probably) sequential reads of all the files and then one big block write you could consider writing it out as you read it:

using (var writer = new StreamWriter(outputPath))
{
    foreach (var csvFileName in csvFileNames)
    {
        using (var reader = new StreamReader(csvFileName))
        {
            string headers = tr.ReadLine();

            if (!hasHeader)
            {
                writer.WriteLine(headers);
                hasHeader = true;
            }

            writer.Write(reader.ReadToEnd());
        }
    }
}

If the files are very big you even might want to consider reading the input line by line and writing it to the output line by line. This will be less performant but also use much less memory. In the end it's a trade off between speed and memory consumption (as it often is in software development).

The other advantage with the write as you go method is that you open the output file first - so if there is a problem with writing to the target you will know before you do any work at all.


Downloading 2 tables from db, does calculation and uploads resulting table I have written this script that downloads two tables from the db, preforms an intersection on them and adds 2 new columns to the resulting table, and uploads the resulting table to the db. It's a bit slow and I realize my code is messy (I'm new to Python and GIS). I suspect more steps can be done in parallel, for example downloading both tables from the database at once.

import arcpy, os, subprocess
import logging, shutil, sys

if __name__ == '__main__':
    #create logger
    logger = logging.getLogger(__name__)
    FORMAT = '%(name)s - %(levelname)s - %(message)s'
    logging.basicConfig(filename='py_intersection.log', level=logging.DEBUG, format=FORMAT)
    logger.info('Started shp intr arcpy')

    host = sys.argv[1]
    database = sys.argv[2]
    schema1 = sys.argv[3]
    schema2 = sys.argv[4]
    username = sys.argv[5]
    password = sys.argv[6]
    table1 = sys.argv[7]
    table2 = sys.argv[8]

    print 'program started'

    out_path = r'\\storage1\gis\temp\output.shp'
    new_dir = r'\\storage1\gis\temp'
    if not os.path.exists(new_dir):
        os.makedirs(new_dir)

    pgsql2shp = 'pgsql2shp -f %s\\%s -h %s -p 5432 -P %s -u %s %s %s.%s' % (new_dir, table1, host, password, username, database, schema1, table1)
    print pgsql2shp
    logger.info('Return code pgsql2shp invocation 1: '+str(subprocess.Popen(pgsql2shp, shell=True).wait()))
    pgsql2shp = 'pgsql2shp -f %s\\%s -h %s -p 5432 -P %s -u %s %s %s.%s' % (new_dir, table2, host, password, username, database, schema2, table2)
    print pgsql2shp
    logger.info('Return code pgsql2shp invocation 2: '+str(subprocess.Popen(pgsql2shp, shell=True).wait()))
    print('Argument:'+ new_dir+'\\'+table1+'.shp'+' , '+ new_dir+'\\'+table2+'.shp')
    arcpy.Intersect_analysis([new_dir+'\\'+table1+'.shp', new_dir+'\\'+table2+'.shp'], out_path, "ALL")

    arcpy.AddField_management(out_path, "intersected_area", "DOUBLE")
    arcpy.AddField_management(out_path, "dist_perct", "DOUBLE")
    arcpy.CalculateField_management(out_path, "intersected_area","!SHAPE.AREA@SQUAREMETERS!", "PYTHON_9.3")

    formula = """def findArea(area_inter, area):
                    return float((float(area_inter/area))*100.0)"""

    arcpy.CalculateField_management(out_path, "dist_perct", "findArea(!intersected_area!, !AREA!)", "PYTHON_9.3", formula)

    #export shapefiles to database
    shp2pgsql = r"shp2pgsql -d -s 48591 "+out_path+" johnsmith.intersected"
    psql = "psql -U johnsmith -h example.org -d exampledb"
    logger.info("Running shp2pgsql | psql")
    sts = subprocess.Popen(shp2pgsql +" | "+psql, shell=True).wait()
    logger.info("Remove shapefiles")
    shutil.rmtree(new_dir)
    print 'program finished'
    logger.info("Done shp intr arcpy")
"""!
@endcond
"""

I know, that you know, that your code is messy, but I'm still going to give some tips on your coding style. Here are a few tips I have on what can be improved there.

Don't use % for string formatting, as it is deprecated. You should be using str.format() instead. Here's an example: print "Hello {0}".format("world")
You can remove the docstring at the end of your file containing """!@endcond""". This does nothing, and serves no purpose.
Separate this out into different functions. In it's current state, it's really hard to read as one large block of code.
Add more comments. Comments will make your code much clearer, and easier to read. Functions and classes should use docstrings, over regular inline comments.

Don't import multiple modules on one line. If an error occurs with one module, it can be hard to distinguish where the error came from.
Some variable names could be better. For example, the names sts, or shp2pgsql provide no useful information. Try to find any other names with not so great names, and see how you can improve them.
I'm not an expert on asynchronous programming, or any of the modules provided in Python made for this, but if you want to do a task like this, Python 3.5 will include the async and await keywords built for asynchronous programming.

The official style guide for Python, PEP8, can be found here.


Finding a word with the most occurrences of a character I am new to PHP development. So Kindly, review my code and guide me make it better/optimize. Currently, it works well with inputs that I have tried.

<?php
// Program to find the word in a sentence with maximum specific character count
// Example: "O Romeo, Romeo, wherefore art thou Romeo?”
// Solution: wherefore
// Explanation: Because "e" came three times
$content = file_get_contents($argv[1]); // Reading content of file
$max = 0;
$arr = explode(" ", $content); // entire array of strings with file contents
for($x =0; $x<count($arr); $x++) // looping through entire array
{
$array[$x] = str_split($arr[$x]); // converting each of the string into array
}
for($x = 0; $x < count($arr); $x++)
{
    $count = array_count_values($array[$x]);
    $curr_max = max($count);
    if($curr_max > $max)
    {
        $max = $curr_max;
        $word = $arr[$x];
    }
}
echo $word;
?>

arr and array

These arrays have too similar names. It's better to avoid using too similar names, to avoid confusion and mistakes.

These names are also poor, as they tell nothing about what's in the arrays. $words would have been a more natural name.

There's no need for both of these arrays at the same time. When you loop over the words to create another array of chars-of-words, you could go one step further, skip the array creation and do the character counting, and save the extra storage of another array.

Code organization

It's good to break your program to multiple small functions, each with a single responsibility. It will make it possible to test smaller and bigger logical units alike independently. For example, you could have functions like:

read a file and return an array of words
find the count of the most frequent character in a letter
find the word with the most frequent character in an array of words

Naming

$x is a bit unusual the counter variable in loops. $i is more common. Some of the improvements I suggested above will hopefully help you replace the counting for loop with a foreach loop. That way instead of a counter variable, you will be able to use something more natural like $word.


Basic value comparisons I made a value comparison "programming language" similar to a previous one I made, except this one is based solely on value comparisons.

# Basic value comparison
from operator import *

# Main compare class
class Compare(object):
    def __init__(self):
        self.OpError = "OpError: Invalid operator or brace.\n"
        self.IntError = "IntError: Invalid integers.\n"
        self.StrError = "StrError: Invalid strings.\n"
        self.LstError = "LstError: Invalid list.\n"
        self.BoolError = "BoolError: Invalid boolean.\n"
        self.st_brace = "["
        self.end_brace = "]"
        self.OPERATORS = {
            ">=": ge,
            "<=": le,
            "==": eq,
            "!=": ne,
            ">": gt,
            "<": lt}

    # Compare two integers
    def compareint(self, command):
        if command[1] == self.st_brace and command[3] in self.OPERATORS and command[5] == self.end_brace:
            try:
                print self.OPERATORS[command[3]](
                    int(command[2]), int(command[4]))
            except ValueError:
                print self.IntError
        if command[3] not in self.OPERATORS:
            print self.OpError

    # Compare two strings
    def comparestr(self, command):
        if command[1] == self.st_brace and command[3] in self.OPERATORS and command[5] == self.end_brace:
            try:
                print self.OPERATORS[command[3]](
                    eval(command[2]), eval(command[4]))
            except SyntaxError:
                print self.StrError
        if command[3] not in self.OPERATORS:
            print self.OpError

    # Compare two lists
    def comparelst(self, command):
        if command[1] == self.st_brace and command[3] in self.OPERATORS and command[5] == self.end_brace:
            try:
                print self.OPERATORS[command[3]](
                    eval(command[2]), eval(command[4]))
            except SyntaxError:
                print self.LstError
        if command[3] not in self.OPERATORS:
            print self.OpError

    # Compare two booleans
    def comparebool(self, command):
        if command[1] == self.st_brace and command[3] in self.OPERATORS and command[5] == self.end_brace:
            try:
                print self.OPERATORS[command[3]](
                    eval(command[2]), eval(command[4]))
            except NameError:
                print self.BoolError
        if command[3] not in self.OPERATORS:
            print self.OpError

# Dict containing commands
COMMANDS = {
    "cmpbool": Compare().comparebool,
    "cmplst": Compare().comparelst,
    "cmpint": Compare().compareint,
    "cmpstr": Compare().comparestr,
}

# Read the inputted commands
def read_command(prompt):
    command = raw_input(prompt)
    split_cmd = command.split(" ")
    if split_cmd[0] in COMMANDS:
        COMMANDS[split_cmd[0]](split_cmd)
    if split_cmd[0] not in COMMANDS:
        print "CmdError: Invalid command.\n"

# Run the program
if __name__ == "__main__":
    while True: read_command(">}}>")

Here's how you use it.

>}}>cmpbool [ True == True ]
True
>}}>cmplst [ [""] == [""] ]
True
>}}>cmpint [ 2 == 2 ]
True
>}}>cmpstr [ "Hello" == "Hello" ]
True

What can be improved? How can I shorten the code? Any general improvements are welcome. Just don't change the syntax.

Removing duplicated code

The same code seems to be duplicated in various places. You can easily define a generic function that you'll be able to reuse in all your definitions.

Here's what I have done (not so tested) :

def generic_compare(self, command, func, error):
    if command[1] == self.st_brace and command[3] in self.OPERATORS and command[5] == self.end_brace:
        try:
            print self.OPERATORS[command[3]](
                func(command[2]), func(command[4]))
        except ValueError:
            print error
    if command[3] not in self.OPERATORS:
        print self.OpError

# Compare two integers
def compareint(self, command):
    self.generic_compare(command, int, self.IntError)

# Compare two strings
def comparestr(self, command):
    self.generic_compare(command, eval, self.StrError)

# Compare two lists
def comparelst(self, command):
    self.generic_compare(command, eval, self.LstError)

# Compare two booleans
def comparebool(self, command):
    self.generic_compare(command, eval, self.BoolError)

You don't need a class

I suggest you have a look at this Python talk called "Stop Writing Classes ".
In your situation, there is no need for a class at all :

Your code could be written :

from operator import *

OpError = "OpError: Invalid operator or brace.\n"
IntError = "IntError: Invalid integers.\n"
StrError = "StrError: Invalid strings.\n"
LstError = "LstError: Invalid list.\n"
BoolError = "BoolError: Invalid boolean.\n"
st_brace = "["
end_brace = "]"
OPERATORS = {
        ">=": ge,
        "<=": le,
        "==": eq,
        "!=": ne,
        ">": gt,
        "<": lt}

def generic_compare(command, func, error):
    if command[1] == st_brace and command[3] in OPERATORS and command[5] == end_brace:
        try:
            print OPERATORS[command[3]](
                func(command[2]), func(command[4]))
        except ValueError:
            print error
    if command[3] not in OPERATORS:
        print OpError

# Compare two integers
def compareint(command):
    generic_compare(command, int, IntError)

# Compare two strings
def comparestr(command):
    generic_compare(command, eval, StrError)

# Compare two lists
def comparelst(command):
    generic_compare(command, eval, LstError)

# Compare two booleans
def comparebool(command):
    generic_compare(command, eval, BoolError)

# Dict containing commands
COMMANDS = {
    "cmpbool": comparebool,
    "cmplst": comparelst,
    "cmpint": compareint,
    "cmpstr": comparestr,
}

# Read the inputted commands
def read_command(prompt):
    command = raw_input(prompt)
    split_cmd = command.split(" ")
    if split_cmd[0] in COMMANDS:
        COMMANDS[split_cmd[0]](split_cmd)
    if split_cmd[0] not in COMMANDS:
        print "CmdError: Invalid command.\n"

# Run the program
if __name__ == "__main__":
    while True: read_command(">}}>")

Use the logic and the usual programming structure

Instead of writing :

    if split_cmd[0] in COMMANDS:
        COMMANDS[split_cmd[0]](split_cmd)
    if split_cmd[0] not in COMMANDS:
        print "CmdError: Invalid command.\n"

Write :

    if split_cmd[0] in COMMANDS:
        COMMANDS[split_cmd[0]](split_cmd)
    else:
        print "CmdError: Invalid command.\n"

Also, you could rewrite :

    if command[1] == st_brace and command[3] in OPERATORS and command[5] == end_brace:
        try:
            print OPERATORS[command[3]](
                func(command[2]), func(command[4]))
        except ValueError:
            print error
    if command[3] not in OPERATORS:
        print OpError

in a way that hilight that sometimes something will be printed, sometimes not.

Define "pure" functions

By defining your functions in such a way that they have no side-effects (printing results for instance), you make them easier to test. In your case, it's quite simple, you can just return instead of printing.

Separe the concerns

You should split the part handling user input/output and the part computing results. This does hand in hand with previous comment.

At this stage, after adding simple tests in the main :

from operator import *

OpError = "OpError: Invalid operator or brace.\n"
IntError = "IntError: Invalid integers.\n"
StrError = "StrError: Invalid strings.\n"
LstError = "LstError: Invalid list.\n"
BoolError = "BoolError: Invalid boolean.\n"
st_brace = "["
end_brace = "]"
OPERATORS = {
        ">=": ge,
        "<=": le,
        "==": eq,
        "!=": ne,
        ">": gt,
        "<": lt}

def generic_compare(command, func, error):
    if command[3] in OPERATORS:
        if command[1] == st_brace and command[5] == end_brace:
            try:
                return OPERATORS[command[3]](
                    func(command[2]), func(command[4]))
            except ValueError:
                return error
    else:
        return OpError

# Compare two integers
def compareint(command):
    return generic_compare(command, int, IntError)

# Compare two strings
def comparestr(command):
    return generic_compare(command, eval, StrError)

# Compare two lists
def comparelst(command):
    return generic_compare(command, eval, LstError)

# Compare two booleans
def comparebool(command):
    return generic_compare(command, eval, BoolError)

# Dict containing commands
COMMANDS = {
    "cmpbool": comparebool,
    "cmplst": comparelst,
    "cmpint": compareint,
    "cmpstr": comparestr,
}

def evaluate_command(command):
    split_cmd = command.split(" ")
    if split_cmd[0] in COMMANDS:
        return COMMANDS[split_cmd[0]](split_cmd)
    else:
        return "CmdError: Invalid command.\n"

# Read the inputted commands
def read_command(prompt):
    print(evaluate_command(raw_input(prompt)))

# Run the program
if __name__ == "__main__":
    assert evaluate_command('cmpbool [ True == True ]')
    assert not evaluate_command('cmpbool [ True == False ]')
    assert evaluate_command('cmplst [ [""] == [""] ]')
    assert not evaluate_command('cmplst [ [""] == ["a"] ]')
    assert evaluate_command('cmpint [ 2 == 2 ]')
    assert not evaluate_command('cmpint [ 2 == 3 ]')
    assert evaluate_command('cmpstr [ "Hello" == "Hello" ]')
    assert not evaluate_command('cmpstr [ "Hello" == "HelloW" ]')
    #while True: read_command(">}}>")

Make things cleaner

It could be a good idea to feed the comparison functions only the information they need : the first element of the list is not relevant anymore at this stage.

You can just write :

def evaluate_command(command):
    split_cmd = command.split(" ")
    func, args = split_cmd[0], split_cmd[1:]
    if func in COMMANDS:
        return COMMANDS[func](args)
    else:
        return "CmdError: Invalid command.\n"

and then, you need to re-index generic_compare :

def generic_compare(command, func, error):
    if command[2] in OPERATORS:
        if command[0] == st_brace and command[4] == end_brace:
            try:
                return OPERATORS[command[2]](
                    func(command[1]), func(command[3]))
            except ValueError:
                return error
    else:
        return OpError

Don't import *

Import * is bad. You can just as easily write :

import operator
OPERATORS = {
        ">=": operator.ge,
        "<=": operator.le,
        "==": operator.eq,
        "!=": operator.ne,
        ">":  operator.gt,
        "<":  operator.lt}

Style

In Python, the good there is a style guide called PEP 8. You'll find various tools to check your code if you want : pep8, pylint, pychecker, pyflakes, etc.

Misc

Usually, using eval in any programming language is quite dangerous. What if I was to evaluate a massive chunk of code with unpredicted side-effects (removing files from my file system for instance) ?
Also, you should perform a lot more checks before accessing random elements from split_cmd as it might be shorter than you expect.


Represent number N (N>1) as N = x + y, where x * y is the maximum possible value My problem is the following: I have to find such x and y (x+y=N) where x * y is the maximum possible value.

I have written an algorithm (which I think works well) and I am looking for more efficient and faster way to solve this problem.

This is my algorithm:

static void Find(int N)
{
    int multiplication = 1;
    int maxMultiplication = 1;
    int desiredNumber = 1;

    for (int i = 1; i <= N / 2; i++)
    {
        multiplication = i * (N - i);
        if(multiplication > maxMultiplication)
        {
            maxMultiplication = multiplication;
            desiredNumber = i;
        }
    }

    Console.WriteLine("Desired presentation of number N is --> N = {0} + {1}",
        desiredNumber, N - desiredNumber);
}

$$\frac{\text{d}}{\text{d}x} x(N-x) = N - 2x$$
At a maximum, \$\frac{\text{d}f}{\text{d}x} = 0\$, so the maximum occurs when \$x = \frac{N}{2}\$. (Left as an exercise: show that it's a maximum and not a minimum).

Therefore you can skip the loop: desiredNumber = N / 2; is all you need. Note that if N is odd this gives the pair \$\left\lfloor \frac{N}{2} \right\rfloor, \left\lceil \frac{N}{2} \right\rceil\$, which is the correct solution in integers.


Doubly linked list in Cython I am implementing a BVH (Bounding volume hierarchy) in Cython and thought of using a doubly linked list to hold reference of the volumes that still need to be split and push new volumes at one end while popping others on the other side in a recursive manner.

But I am not sure if I got the code right, it gets confusing to me really fast.

Here AABB stands for Axis Aligned Bounding Box, the kind of bounding volume I want to use in my BVH.

    cdef struct AABB:
        double min_x, max_x
        double min_y, max_y
        double min_z, max_z
        AABB* next
        AABB* children
        int id

    cdef struct AABBListItem:
        AABB* box
        AABBListItem* next
        AABBListItem* prev

    cdef AABBList* aabb_list_create(AABB* start):
        cdef AABBList* lst = <AABBList *> malloc(sizeof(AABBList))
        cdef AABBListItem* item = <AABBListItem *> malloc(sizeof(AABBListItem))
        item.next = NULL
        item.prev = NULL
        item.box = start
        lst.first = item
        lst.last = item
        lst.length = 1
        return lst

    cdef void aabb_list_free(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABBListItem* next
        while not item == NULL:
            next = item.next
            free(item)
            item = next
        free(lst)

    cdef void aabb_list_push_last(AABBList* lst, AABB* box):
        cdef AABBListItem* item = <AABBListItem *> malloc(sizeof(AABBListItem))
        item.box = box
        item.prev = lst.last
        item.next = NULL
        lst.last.next = item
        lst.last = item
        lst.length += 1

    cdef void aabb_list_push_first(AABBList* lst, AABB* box):
        cdef AABBListItem* item = <AABBListItem *> malloc(sizeof(AABBListItem))
        item.box = box
        item.next = lst.first
        item.prev = NULL
        lst.first.prev = item
        lst.first = item
        lst.length += 1

    cdef AABB* aabb_list_pop_first(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABB* box = item.box
        lst.first = item.next
        lst.first.prev = NULL
        free(item)
        lst.length -= 1
        return box

    cdef AABB* aabb_list_pop_last(AABBList* lst):
        cdef AABBListItem* item = lst.last
        cdef AABB* box = item.box
        lst.last = item.prev
        lst.last.next = NULL
        free(item)
        lst.length -= 1
        return box

```

Empty Constraint

You do not allow to create an empty list.

cdef AABBList* aabb_list_create(AABB* start):

However, the pop methods don't check against the empty constraint. In fact, when popping the sole node, you end up with an error.

For instance,

 cdef AABB* aabb_list_pop_first(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABB* box = item.box
        lst.first = item.next     // <- if item.next is NULL
        lst.first.prev = NULL     // <- lst.first will be NULL, and .prev is an error
        free(item)
        lst.length -= 1
        return box

Single Remaining Item after Pop

Furthermore, when after pop a single item remains, it should be set as both first and last on the list.


Rule of Three for non-circular singly linked list Here is a non-circular, singly linked list data structure (with no headers). This is done using a pre-C++11 standard. Is there a more efficient way/shorter way of writing this (especially the copy assignment operator which contains duplicate code from the copy constructor and clear() method)?

template<typename T>
class linked_list{
    class node {
    public:
        T data;
        node *next;

        node() :
            data(T()),
            next(NULL)
            { }

        node(const T &data, node *next) :
            data(T(data)),
            next(next)
            { }
    }; // class node
protected:
    node *mFirst;
    size_t mSize;
public:
    /** Empty Constructor */
    linked_list():
        mFirst(NULL),
        mSize(0) {}

    /** Array Constructor */
    linked_list(T* others, size_t n) {
        for (int i = 0; i < n; i++) {
            mFirst = new node(*others, mFirst);
            others++;
        }
    }

    /** Copy Constructor*/
    linked_list(const linked_list &other):
        mFirst(NULL),
        mSize(other.mSize)
        {
        node *p = other.mFirst;
        while (p != NULL) {
            mFirst = new node(p->data, mFirst);
            p = p->next;
        }
        if (mFirst != NULL){
            node *q, *prev;
            p = mFirst;
            q = p->next;
            p->next = NULL;
            prev = p;
            p = q;
            for (int i = 1; i < mSize; i++) {
                q = p->next;
                p->next = prev;
                prev = p;
                p = q;
            }
            mFirst = prev;
        }
    }

    /** Destructor */
    ~linked_list(){
        clear();
    }

    /** Copy Assignment Operator*/
    linked_list &operator=(const linked_list &other) {
        if (this != &other) {
            // allocate and copy from other to r
            mSize = other.mSize;
            node *p = other.mFirst, *r = NULL;
            while (p != NULL) {
                r = new node(p->data, r);
                p = p->next;
            }
            if (r != NULL){
                node *q, *prev;
                p = r;
                q = p->next;
                p->next = NULL;
                prev = p;
                p = q;
                for (int i = 1; i < mSize; i++) {
                    q = p->next;
                    p->next = prev;
                    prev = p;
                    p = q;
                }
                r = prev;
            }

            // deallocate current
            node *q;
            p = mFirst;
            while(p != NULL) {
                q = p->next;
                delete p;
                p = q;
            }

            // replace
            mFirst = r;
        }
        return *this;
    }

    void clear() {
        node *q, *p = mFirst;
        while(p != NULL) {
            q = p->next;
            delete p;
            p = q;
        }
        mFirst = NULL;
        mSize = 0;
    }

Putting member variables in a protected block is a worry.

 protected:
    node *mFirst;
    size_t mSize;

I would put them into a private block and give limited accesses via members in the protected block that prevents derived classes from breaking the invariant on your members.

Personal preference here:

linked_list():
    mFirst(NULL),
    mSize(0) {}

I like to write it like this:

// Take it or leave it.
// Nobody should complain about your style just looks slightly different.
linked_list()
    : mFirst(NULL)
    , mSize(0)
{}

I would also change mFirst to mRoot. The use of m to mark member variables is an indicator that you are using bad member Vs local names and need a rule to allow people to distinguish between the two. I would prefer you improve the naming convention of your variables so that it si obvious from context the meaning.

Modify the array constructor to use members to do the real work and make the code more readable and thus self documenting.

linked_list(T* others, size_t n) {
    for (int i = 0; i < n; i++) {
        mFirst = new node(*others, mFirst);
        others++;
    }
}

// More Self documenting
linked_list(T* others, size_t n) {
    for (int i = 0; i < n; i++) {
        append(others[n]);         // Note this is inefficient with only
                                   // mFirst (you would need an mLast
                                   // to make it efficient. But alternatively
                                   // you could insert at the beginning and insert
                                   // in reverse order.
    }
}

Copy constructor

linked_list(const linked_list &other)
    : mFirst(NULL),
    , mSize(0)
{
    for(Node* tmp = other.mFirst; tmp; tmp = tmp->next) {
        append(tmp->data);   // Same comment as above.
    }
}

Copy  and Swap Idiom

linked_list& operator=(linked_list const& rhs)
{
     linked_list  copy(rhs);   // use copy constructor to copy.
     swap(copy);               // swap the content of this and copy.
     return *this;
}
// The object copy goes out of scope calling its destructor and
// thus cleaning up the original content of this object.


(How) should I avoid writing procedural code in Haskell? I'm trying to implement a left leaning red black tree as described here. This is their snippet for insert

private Node insert(Node h, Key key, Value value) {
    if (h == null) return new Node(key, value);

    if (isRed(h.left) && isRed(h.right)) colorFlip(h);

    int cmp = key.compareTo(h.key);
    if (cmp == 0) h.val = value;
    else if (cmp < 0) h.left = insert(h.left, key, value);
    else h.right = insert(h.right, key, value);

    if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);

    return h;
}

My attempt at a port in Haskell is... quite ugly, with a lot of repetition. I think it's because I'm still thinking procedurally. Any feedback on what I should do differently? Or is there no way around having many next-state variables (x', x'', x''')? Should I be approaching this completely differently?

data Colour = Red | Black deriving (Show)

data Tree a
    = Branch (Tree a) a (Tree a) Colour
    | Leaf
    deriving (Show)

add :: (Ord a) => Tree a -> a -> Tree a
add tree val
    = let
        (Branch left' node' right' _) = fix_up $ do_add tree val
    in (Branch left' node' right' Black) -- root always black

do_add :: (Ord a) => Tree a -> a -> Tree a
do_add (Branch left node right colour) val
    | val < node = (Branch (add left val) node right colour)
    | val > node = (Branch left node (add right val) colour)
    | otherwise = (Branch left node right colour)
do_add Leaf val = (Branch Leaf val Leaf Black)

get_left_node :: Tree a -> Tree a
get_left_node (Branch left _ _ _) = left
get_left_node Leaf = Leaf

fix_up :: Tree a -> Tree a
fix_up (Branch left node right colour)
    = let
        branch' = if ((not (is_red left)) && (is_red right)) then (rotate_left (Branch left node right colour)) else (Branch left node right colour)
        (Branch left' _ right' _) = branch'
        branch'' = if ((is_red left') && (is_red (get_left_node left'))) then (rotate_right branch') else branch'
        (Branch left'' _ right'' _) = branch''
        branch''' = if ((is_red left'') && (is_red right'')) then (flip_colours branch'') else branch''
    in branch'''

rotate_left :: Tree a -> Tree a
rotate_left (Branch left node (Branch right_left right_node right_right right_colour) colour)
    = let
        left' = (Branch left node right_left Red)
        centre' = (Branch left' right_node right_right colour)
    in centre'

rotate_right :: Tree a -> Tree a
rotate_right (Branch (Branch left_left left_node left_right left_colour) node right colour)
    = let
        right' = (Branch left_right node right Red)
        centre' = (Branch left_left left_node right' colour)
    in centre'

flip_colours :: Tree a -> Tree a
flip_colours (Branch (Branch left_left left_node left_right left_colour) node (Branch right_left right_node right_right right_colour) colour) = let
        left' = (Branch left_left left_node left_right (invert_colour left_colour))
        right' = (Branch right_left right_node right_right (invert_colour right_colour))
        centre' = (Branch left' node right' (invert_colour colour))
    in centre'

is_red :: Tree a -> Bool
is_red (Branch _ _ _ Red) = True
is_red _ = False

is_black :: Tree a -> Bool
is_black node = not $ is_red node

The code looks much better after refactoring!

Additionally I'd strongly suggest to keep line lengths within some limit. Usual choices are something between 72 and 80. There are two reasons for it:

People with smaller screens aren't able to see a piece code at once and have to scroll. This makes reading the code next to impossible (like when your snippet here on SO doesn't fit into its frame).
Even for a person with a wide screen it's difficult to read text with long lines. It's hard for eyes to focus where the next line starts.

Don't be afraid to use short identifiers, if theirs scope is limited to a short function. For example, in my opinion this

rotate_left :: Tree a -> Tree a
rotate_left (Branch l v (Branch rl rv rr _rc) c)
          = (Branch (Branch l v rl Red) rv rr c)

is more readable, and it's visually easy to spot what is going on.

One thing that will also help you make the code shorter more readable is using as-patterns (see also this question):

do_add :: (Ord a) => Tree a -> a -> Tree a
do_add branch@(Branch left node right colour) val
    | val < node = (Branch (add left val) node right colour)
    | val > node = (Branch left node (add right val) colour)
    | otherwise = branch -- HERE: we don't need to recreate the node
do_add Leaf val = (Branch Leaf val Leaf Black)

It also can give a small performance boost as we don't re-create objects identical to those we pattern match on.

Concerning fix_up: Let's try to factor out common and duplicate code. The common pattern is that we check some conditions on the sub-nodes of a node and if it's true, we apply a function or it. Otherwise we keep it intact. We can split this idea into two functions - one that is general, and other that is then specialized for branches:

fix_up :: Tree a -> Tree a
fix_up =
    onBr [is_red]                         [is_red] flip_colours .
    onBr [is_red, is_red . get_left_node] []       rotate_right .
    onBr [not . is_red]                   [is_red] rotate_left
  where
    -- Apply a function on a branch, if its left and right subnodes match
    -- given predicates.
    onBr :: [Tree a -> Bool] -> [Tree a -> Bool]
         -> (Tree a -> Tree a) -> (Tree a -> Tree a)
    onBr lps rps = on (\b -> all ($ get_left_node b) lps
                          && all ($ get_right_node b) rps)
    -- Apply a function on a value, if it matches a predicate.
    on :: (a -> Bool) -> (a -> a) -> (a -> a)
    on p f x | p x       = f x
             | otherwise = x

This allows us to represent the whole operation as the composition of several functions. And it localizes bindings of subnodes (l and r) to the predicates, which again helps readability.

I'd also like to draw your attention to AA trees. They have very similar performance as red-black trees, but are simpler and easier to implement.


Parser written in PHP is 5.6x faster than the same C++ program in a similar test (g++ 4.8.5) I'm absolutely dumbfounded by this. I was trying to demonstrate to myself how much faster C++ is than even modern PHP. I ran a simple CSV parsing program in both that have the same output. The CSV file is 40,194,684 parsed down to 1,537,194 lines.
EDIT: This sparked alot more conversation than I had anticipated, here's the hardware stats for the machine both programs were run on, however its actually a VM running on a nutanix server:
CPU: Intel(R) Xeon(R) Silver 4215R CPU @ 3.20GHz
RAM: 16GB
PHP code (runtime 42.750 s):
<?php
$i_fp = fopen("inFile.csv","r");
$o_fp = fopen("outFile.csv","w");

while(!feof($i_fp))
{
    $line = fgets($i_fp);
    $split = explode(';',$line);
    if($split[3] == 'E' || $split[3] == 'T')
    {
        fwrite($o_fp,join(',',[ $split[0], $split[1], $split[3], $split[4], $split[5], $split[6],
                                $split[10], $split[9],$split[11],$split[7],$split[32]])."\n");
    }
}
fclose($i_fp);
fclose($o_fp);

C++ code (runtime 3 m 59.074s) (compiled using g++ parse.cpp -o parse -O2 -std=c++1y)
#include <fstream>
#include <stdlib.h>
#include <string>
#include <vector>

using std::string;
using std::vector;

vector<string> splitStr(string line, const char delimiter = ',')
{
    vector<string> splitLine;
    string buf;
    for(size_t i=0; i<line.length(); i++)
    {
        if(line[i] == delimiter)
        {
            splitLine.push_back(buf);
            buf.clear();
        }else{
            buf += line[i];
        }
    }
    return splitLine;
}
string makeCSVLine(vector<string> splitLine)
{
    string line =
        splitLine[0] + ',' +
        splitLine[1] + ',' +
        splitLine[3] + ',' +
        splitLine[4] + ',' +
        splitLine[5] + ',' +
        splitLine[6] + ',' +
        splitLine[10] + ',' +
        splitLine[9] + ',' +
        splitLine[11] + ',' +
        splitLine[7] + ',' +
        splitLine[32] + '\n';
    return line;

}
int main(int argc, char* argv[])
{
    if(argc < 3)
    {
        exit(EXIT_SUCCESS);
    }
    string inPath = argv[1];
    string outPath = argv[2];

    std::ifstream inFile;
    std::ofstream outFile;

    inFile.open(inPath.c_str());
    outFile.open(outPath.c_str());

    string line;
    while(std::getline(inFile,line))
    {
        vector<string> split = splitStr(line, ';');
        if(split[3][0] == 'E' || split[3][0] == 'T')
        {
            outFile << makeCSVLine(split);
        }
    }
    inFile.close();
    outFile.close();
}

Both running on Red Hat Linux 8. I'm sure that it's some mistake I'm making in terms of C++ efficiency (possibly somewhere in how I'm using strings and vectors and whether they need to be re-sized repeatedly per loop), but I'm not sure what it could be. If anyone could help, shed some light. That would be great.
EDIT: Unfortunately, I cannot provide the input file as its a sensitive internal file.
Thanks to everyone for taking so much interest in this and all the advice provided. I've been extremely busy at work lately and unable to re-visit but look forward to doing so soon.

Always Profile Optimized Code.

https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rper-measure

Use -O3 optimisation: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

Use a profiler: https://github.com/KDAB/hotspot

https://en.wikipedia.org/wiki/List_of_performance_analysis_tools

Reduce the duplication
string inPath = argv[1];
string outPath = argv[2];

std::ifstream inFile;
std::ofstream outFile;

inFile.open(inPath.c_str());
outFile.open(outPath.c_str());

to
std::ifstream inFile(argv[1]);
std::ofstream outFile(argv[2]);

Avoid string operations and allocations as much as possible. Prefer std::string_view if the string is only being read.

Remove string makeCSVLine(vector<string> splitLine) and use a formatter library like {fmt} https://github.com/fmtlib/fmt. Just to make the code prettier in
  outFile << makeCSVLine(split);

, you're paying with a significant time penalty. OR use the good old (discussed below) fprintf if that turns out to be faster. If there is not a significant time gain, follow the guidelines and use fmt + streams.
 fmt::print(<FILE*>,
           "{},{},{},{},{},{},{},{},{},{},{}\n",
           vec[0],
           vec[1],
           vec[3],
           vec[4],
           vec[5],
           vec[6],
           vec[10],
           vec[9],
           vec[11],
           vec[7],
           vec[32]);

Make it a macro or a lambda, or a function with inline attribute set if you want to use it with other answers but in a separate block of code.
See speed tests by fmt also. source file

vector<string> splitStr(string line, const char delimiter = ',')
Avoid returning the vector and pass it by reference to fill it inside the function ( return type will be void). This makes it Return Value Optimisation independent. All compilers will treat it the same way.
Also, consider using .reserve(), and/or .emplace_back() for the vector. reserve() has been tested to improve performance.

Use stringstream + getline with a delimiter. If you doubt that this is time costly, profile. Don't guess the performance results, measure them.
void split_by_delim(const string &string, char delim, vector<string> &r_out)
{
  std::stringstream ss(string);
  string word{};   // reserve space if you can guess it right.
  while (std::getline(ss, word, delim)) {
    if (!word.empty()) {
       r_out.push_back(word);
    }
  }
}

Avoid fstreams iff the reader or writer are the biggest time sinks. fprintf has been 40% faster in my tests with no loss in flexibility (I used it for writing ints and floats, it may vary(edit: yes it varied and the gain is insignificant compared to the other benefits of streams (or with fmt) ) with strings.).
Re comments that Stream IO is as fast as printf family IO, take it from Herb Sutter & Bjarne Stroustrup:

It is often (and often correctly) pointed out that the printf() family has two advantages compared to iostreams: flexibility of formatting and performance. This has to be weighed against iostreams advantages of extensibility to handle user-defined types, resilient against security violations, implicit memory management, and locale handling.
If you need I/O performance, you can almost always do better than printf().

Emphasis mine.

https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Rio-streams

In the current code, the reading speed (getline()) is bound by splitting the string and the write speed. In other words, more lines cannot be read as long as file writer has not done its job. You're not using the disk's read speed to the full potential here.
Consider splitting them such that all reading is done at once and data is stored in memory and it is written out at once.
If you want to keep peak memory usage to minimum, make use of threads and separate the reader and the (splitter + writer) in asynchronous threads.

Addendum
Machine: MacBook Air 2017, macOS Mojave, MQD32LL https://en.wikipedia.org/wiki/MacBook_Air#Technical_specifications_2
Profiler: Instruments.app.
Compiler: Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Target: x86_64-apple-darwin18.7.0
Flags: -Ofast (and linking with {fmt} where required.)
PHP: 7.1.23 (cli) (built: Feb 22 2019 22:19:32) ( NTS )

Writer code to make CSV file, derived from Edward's answer for consistency: https://ideone.com/gkmUUN
Note that close enough timings should be considered the same due to fluctuations which can affect 3 to 5 seconds by a lot.
Matthew's code with the knowledge of line length and word length: 2.6s
Matthew's code as of rev 1 : 2.7s
Edward's algorithm with char array storage & {fmt}: https://ideone.com/Kfkp90. This depends on the knowledge that the incoming CSV has a maximum line length of 300 characters and a maximum word length of 20 characters. 2.8s.
Martin's code as of rev 7: 2.8s
For less bug-prone code, and dealing with unknown length strings: https://ideone.com/siFp3A. This is Edward's algorithm which uses {fmt}. 4.1s.
gdate +%s.%3N && php parser.php && gdate +%s.%3N where parser.php is in Edward's code as of rev 5 : 4.4s
Edward's code as of rev 1: 4.75s
Edward's code with fprintf https://ideone.com/0Lmr5P : 4.8
OP's code with basic optimisations, and fprintf https://ideone.com/5ivw9R : 5.6s
OP's C++ code posted in the question: 6.2s
OP's C++ code with -O2: 6.4s
OP's C++ code with -O0: 45s