Web scraping google trends in python Question

Recently I have tried to create a web scraping program to get data from google trends. It uses an RSS feed to do so. My question is as follows:

How can I improve my code such that it is more concise, efficient, and pleasing to a programmers eye? I would like to emphasise that I'm most concerned about if I've misused any functions, methods, or syntax in my code and if it could be 'cleaner'

Context

I'm not experienced at all. I'm doing this to learn.
Security isn't an issue since the program is running locally.

The code

"""Uses webscraping to retrieve html information from Google Trends for
parsing"""

# Imports

import time
import ssl
from requests import get
from bs4 import BeautifulSoup

# Url for request

url = "https://trends.google.com/trends/trendingsearches/daily/rss?geo=US"

# Used to create an unverified certificate.

ssl._create_default_https_context = ssl._create_unverified_context

class connection(object):

    def __init__(self, f):
        self.f = f

    def __call__(self):
        """Calculates the time taken to complete the request without any errors"""
        try:
            # Times the amount of time the function takes to complete
            global html
            start = time.time()
            html = get(url)
            self.f()
            end = time.time()
            time_taken = end - start
            result = print("the function {} took {} to connect".format(self.f.__name__, time_taken))
            return result
        except:
            print("function {} failed to connect".format(self.f.__name__))

@connection
def html_parser():
    """Parses the html into storable text"""
    html_unparsed = html.text
    soup = BeautifulSoup(html_unparsed, "html.parser")
    titles_unformatted = soup.find_all("title")
    traffic_unformatted = soup.find_all("ht:approx_traffic")
    # Indexes through list to make data readable
    titles = [x.text for x in titles_unformatted]
    traffic = []
    for x in traffic_unformatted:
        x = x.text
        x = x.replace("+","")
        x = x.replace(",", "")
        traffic.append(x)
    print(traffic, titles)
html_parser()

Output

['100000', '2000000', '2000000', '1000000', '1000000', '1000000',
'1000000', '500000', '500000', '500000', '200000', '200000', '200000',
'200000', '200000', '200000', '200000', '200000', '200000', '200000']
['Daily Search Trends', '23 and Me', 'NFL scores', 'Best Buy', 'Walmart
Supercenter', 'NFL', 'Saints', 'GameStop', 'JCPenney', 'Lion King 2019',
'Starbucks', 'Dollar General', 'Amazon Black Friday', 'Mike Posner',
'NFL games On Thanksgiving', 'McDonalds', 'Bath And Body Works Black
Friday', 'Old Navy Black Friday 2018', 'Kroger', 'NFL standings',
'Safeway']
the function html_parser took 1.0186748504638672 to connect

Concerns

Makes programmers cringe.

As someone relatively new to python and programming in general my worst fear is that this code gives someone else a headache or a laugh to look at. At the end of the day I just want to improve, so to reiterate: how can I make this code look better? Have I misused any functions?

The idea behind your script is pretty cool and there's a couple ways to polish it up! While it certainly wouldn't cause a headache, I think that creating an entire class just to measure how long the request is going to take to complete is a little overkill.

Within the class itself, let's look at 2 things which aren't the best practice.

Use of a global variable
Use of the try/except block

Global variables

There's a brilliant StackOverflow question with really good answers as to why using global variables should be discouraged. While in the scope of your script it is not harmful, imagine you had many functions and methods in your script. Using the global variable could decrease readability and potentially alter the behaviour of your code. Mind you, global variables aren't the same as global constants (also discussed in the StackOverflow question).

Exception handling

Using a bare except statement will handle all exceptions, even the ones you might not anticipate. Catch errors explicitly, otherwise you might cause unexpected behaviour in your code, should it become more complex. In this scope, your bare except statement should become more like this:

try:
    ...
except requests.exceptions.ConnectionError:
    print("failed to connect")

This way, you are handling the case where your request actually fails and you let other errors happen in their intended way. Otherwise, a different exception could have been raised and you won't know what caused it.

Additionally, on this class:

Following naming conventions, class names should use CapWords.
In Python 3+, classes no longer need to be inherited from object.

Instead of the class, you could just define a simple function which retrieves the XML document from the RSS feed, declare your timing functionality within it and returns the XML document. Seeing as the URL query takes in what's seemingly an ISO 3166-2 country code as one of the parameters, you could pass the country code into this function and have the ability to fetch search trends for so many different countries! Please note that in the following snippet I am using f-strings which were introduced since Python 3.6.

def fetch_xml(country_code):
    url = f"https://trendse.google.com/trends/trendingsearches/daily/rss?geo={country_code}"
    start = time.time()
    response = requests.get(url)
    response_time = time.time() - start
    print(f"The request took {response_time}s to complete.")
    return response.content`

Parser

Looking at the docstring of your parser, one might argue it's a little misleading. You're mentioning "storable text" while you're only printing your output! To come closer to the intention of the docstring, it would be better to return the parsed data and decide what to do with it later. I think in this case, a dictionary would a very fitting data structure. Dictionaries store key-value pairs, so lets use the trend title as the key and the traffic approximation as the value.

Using re.sub() will allow you to remove different characters from a string in a single line, rather than replacing each character separately! This piece of code here:

for x in traffic_unformatted:
    x = x.text
    x = x.replace("+","")
    x = x.replace(",", "")

Can now become:

    for x in traffic_unformatted:
        x = re.sub("[+,]", "", x.text)

Zip the two lists of titles and traffic approximations together and iterate over them to create the dictionary. I am going to use a dictionary comprehension in the final script, however it works identically to the following.

titles = soup.find_all("title")
approximate_traffic = soup.find_all("ht:approx_traffic")
trends = {}
for title, traffic in zip(titles[1:], approximate_traffic):
    trends[title.text] = re.sub("[+,]", "", traffic.text)
return trends

Please pay attention to the titles function having its first element sliced off - this is because BeautifulSoup picked up the title of the entire XML document together with titles of the trends.

Finally, I am using an if __name__ == "__main__" guard to separate functions from the block of code where I am calling the functions from.

Entire script:

import time
import re
import requests
from bs4 import BeautifulSoup

def fetch_xml(country_code):
    url = f"https://trends.google.com/trends/trendingsearches/daily/rss?geo={country_code}"
    start = time.time()
    response = requests.get(url)
    response_time = time.time() - start
    print(f"The request took {response_time}s to complete.")
    return response.content

def trends_retriever(country_code):
    """Parses the Google Trends RSS feed using BeautifulSoup.

    Returns:
        dict: Trend title for key, trend approximate traffic for value.
    """
    xml_document = fetch_xml(country_code)
    soup = BeautifulSoup(xml_document, "lxml")
    titles = soup.find_all("title")
    approximate_traffic = soup.find_all("ht:approx_traffic")
    return {title.text: re.sub("[+,]", "", traffic.text)
            for title, traffic in zip(titles[1:], approximate_traffic)}

if __name__ == '__main__':
    trends = trends_retriever("US")
    print(trends)

Output:

The request took 0.2512788772583008s to complete.
{'Tiger vs Phil': '2000000', 'McKenzie Milton': '200000', 'Costco Black Friday': '200000', 'Nebraska Football': '200000', 'Patagonia': '100000', 'Michael Kors': '100000', 'Jcrew': '100000', 'finish line': '100000', 'WVU football': '100000', 'Texas football': '100000', 'Shoe Carnival': '100000', 'J Crew': '100000', 'Llbean': '100000', 'Cards Against Humanity': '100000', 'Bleacher Report': '100000', 'Steph Curry': '50000', 'Apple Cup': '50000', 'Bob McNair': '50000', 'Virginia Tech football': '50000', 'Glossier': '50000'}


Find the Percentage from HackerRank I am learning python by solving python module from HackerRank. This problem is Find the Percentage.

  You have a record of N students. Each record contains the student's
  name, and their percent marks in Maths, Physics and Chemistry. The
  marks can be floating values. The user enters some N integer followed
  by the names and marks for N students. You are required to save the
  record in a dictionary data type. The user then enters a student's
  name. Output the average percentage marks obtained by that student,
  correct to two decimal places.

  Sample Input 0

3
Krishna 67 68 69
Arjun 70 98 63
Malika 52 56 60
Malika

  Sample Output 0

56.00

I need to improve this code by using better functions available in python.

def percentage(name):
    """
    Find percentage of marks of the student
    """

    marks = student_marks[name]
    total_marks = 0
    for mark in marks:
        total_marks += mark

    return format(total_marks/len(marks), '.2f')

if __name__ == '__main__':
    n = int(input())
    student_marks = {}
    for _ in range(n):
        name, *line = input().split()
        scores = list(map(float, line))
        student_marks[name] = scores
    query_name = input()
    print(percentage(query_name))

For a beginner this is some good code. I would make some additional adjustments.

One-line docstrings should be on one line, not over 3. And should end with a period.
You should only pass the marks to percentage and not rely on a global student_marks.
You can use sum to compute total_marks.
I'm not a fan of having format in the percentage function.
You should move all the main code into a main function, if __name__ == '__main__': should really only call this.
It's more idiomatic to use comprehensions than map, even more so when you have list(map(...)).
It's pretty rude to call a student a query. You can just use name.

def percentage(marks):
    """Find percentage of marks of the student."""
    return sum(marks) / len(marks)

def main():
    """Main code."""
    n = int(input())
    student_marks = {}
    for _ in range(n):
        name, *scores = input().split()
        student_marks[name] = [float(score) for score in scores]
    name = input()
    result = percentage(student_marks[name])
    print(format(result, '.2f'))

if __name__ == '__main__':
    main()

You can use statistics.mean rather than a custom made percentage.
You can change the for loop into two comprehensions, a generator and dictionary comprehension.

Note: I don't think comprehensions are better here, but are an 'as good' alternate.

import statistics

def main():
    """Main code."""
    _marks = (input().split() for _ in range(int(input())))
    student_marks = {
        name: [float(score) for score in scores]
        for name, *scores in _marks
    }
    result = statistics.mean(student_marks[input()])
    print(format(result, '.2f'))

if __name__ == '__main__':
    main()


Simulation of an alien population Background

I've come across a puzzle (Problem 10 from this list of sample interview questions):

  One day, an alien comes to Earth. Every day, each alien does one of four things, each with equal probability to:

  Kill himself
  Do nothing
  Split himself into two aliens (while killing himself)
  split himself into three aliens (while killing himself)

  What is the probability that the alien species eventually dies out entirely?

Unfortunately, I haven't been able to solve the problem theoretically. Then I moved on to simulate it with a basic Markov Chain and Monte Carlo simulation in mind.

This was not asked to me in an interview. I learned the problem from a friend, then found the link above while searching for mathematical solutions.

Reinterpreting the question

We start with the number of aliens n = 1. n has a chance to not change, be decremented by 1, be incremented by 1, and be incremented by 2, %25 for each. If n is incremented, i.e. aliens multiplied, we repeat this procedure for n times again. This corresponds to each alien will do its thing again. I have to put an upper limit though, so that we stop simulating and avoid a crash. n is likely to increase and we're looping n times again and again.

If aliens somehow go extinct, we stop simulating again since there's nothing left to simulate.

After n reaches zero or the upper limit, we also record the population (it will be either zero or some number >= max_pop).

I repeat this many times and record every result. At the end, number of zeros divided by total number of results should give me an approximation.

The code

from random import randint
import numpy as np

pop_max = 100
iter_max = 100000

results = np.zeros(iter_max, dtype=int)

for i in range(iter_max):
    n = 1
    while n > 0 and n < pop_max:
        for j in range(n):
            x = randint(1, 4)
            if x == 1:
                n = n - 1
            elif x == 2:
                continue
            elif x == 3:
                n = n + 1
            elif x == 4:
                n = n + 2
    results[i] = n

print( np.bincount(results)[0] / iter_max )

iter_max and pop_max can be changed indeed, but I thought if there is 100 aliens, the probability that they go extinct would be negligibly low. This is just a guess though, I haven't done anything to calculate a (more) proper upper limit for population.

This code gives promising results, fairly close to the real answer which is approximately %41.4.

Some outputs

> python aliens.py
0.41393
> python aliens.py
0.41808
> python aliens.py
0.41574
> python aliens.py
0.4149
> python aliens.py
0.41505
> python aliens.py
0.41277
> python aliens.py
0.41428
> python aliens.py
0.41407
> python aliens.py
0.41676

Aftermath

I'm okay with the results but I can't say the same for the time this code takes. It takes around 16-17 seconds :)

How can I improve the speed? How can I optimize loops (especially the while loop)? Maybe there's a much better approach or better models?

There are some obvious possible simplifications for elegance, if not necessarily for speed.

The while condition should be written as a double-ended inequality:

while 0 < n < pop_max:
    …

The variable j is unused.  The convention is to use _ as the name of a "throwaway" variable.

The if-elif chain can be eliminated with a smarter randint() call:

for j in range(n):
    n += randint(-1, 2)

NumPy is overkill here, when all you want to know whether the population went extinct.  The built-in sum() function can do the counting for you.

Each simulation run is independent.  I'd put the code in a function for readability.

from random import randint

def population(pop_max=100):
    n = 1
    while 0 < n < pop_max:
        for _ in range(n):
            n += randint(-1, 2)
    return n

iterations = 100000
print(sum(population() == 0 for _ in range(iterations)) / iterations)


Grouping over a list of dictionaries I am consuming data from an API that reads from a SharePoint list. The API is basically this:

IList<Dictionary<string,string>> GetListData(string listName);

So the data is a list of dictionaries - each dictionary containing value-pairs (column name, column value) for a "row" in the list.

I need to group over the results, doing a sum over one column.

I have made code that does exactly that - but I am not entirely happy with it.

The code is this:

[Test]
public void TestOfSharePointResult()
{
    //Arrange
    IList<Dictionary<string, string>> sharePointResult = new List<Dictionary<string, string>>
    {
        new Dictionary<string, string> { {"TO", "101"}, { "PA", "123" } },
        new Dictionary<string, string> { {"TO", "202"}, { "PA", "456" } },
        new Dictionary<string, string> { {"TO", "404"}, { "PA", "123" } }
    };

    //Act
    var valuePairs = sharePointResult
        .Select(dict => new KeyValuePair<string, int>(dict["PA"], dict["TO"].FromProjectValueToInt()))
        .GroupBy(d => d.Key)
        .Select(g => new { PA = g.Key, Sum = g.Sum(f => f.Value) })
        ;

    //Assert

    // Result must be:
    //  PA  Sum
    //  --------
    //  123 505
    //  456 202
    var TOValueFor123 = valuePairs.First(i => i.PA == "123").Sum;
    var TOValueFor456 = valuePairs.First(i => i.PA == "456").Sum;
    Assert.AreEqual(505, TOValueFor123);
    Assert.AreEqual(202, TOValueFor456);
}

The "FromProjectValueToInt()" extension basically converts a string to an int.

The reason I am not entirely happy with this code is line 14, where I am doing an explicit extraction of values from the dictionary entries to a KeyValuePair struct.

Is there a more implicit way of looping over the list of dictionaries that I am missing?

You don't need neither Select and can get the same result by using only GroupBy:

var valuePairs = sharePointResult
    .GroupBy(
        dict => dict["PA"],
        dict => int.Parse(dict["TO"]),
        (key, items) => new
        {
            PA = key,
            Sum = items.Sum(f => f)
        });

where the parameters are respectively:

.GroupBy(keySelector, elementSelector, resultSelector);

I used int.Parse for testing - it's not a part of my review ;-)


C# asp.net project functionalities I just started working in a project that wasn't developed by me, I'm worried about some of the functionalities and I would like some suggestions.

After the login validations, the login procedure is made like this:

var _ticket = new FormsAuthenticationTicket(1, user.ID, DateTime.Now, DateTime.Now.AddDays(30), true, user.ID);

string encTicket = FormsAuthentication.Encrypt(_ticket);
HttpContext.Current.Response.Cookies.Add(new HttpCookie(FormsAuthentication.FormsCookieName, encTicket));

As we can see, there is a user object which stores the details of the logged in user (Id, name, e-mail...)

The first problem that I see is that on the FormsAuthenticationTicket the user ID is passed as the name. And every time I want to get any info from the user I have to do this:

Item user = Framework.Business.Item.Load(HttpContext.Current.User.Identity.Name);

The project uses master page, and on every page I have to do this to get the ID/name/picture of the logged user

By the way, at least the load method gets the user date from a collection, BUT, this collection stores not only the users data but all the data that needs to be cached (since ID's are GUIDs) ids won't be duplicated and I think because of this reason, there is only one Collection for everything.

I would like to know if this is right, or what should I do to make it better

I think you can simply create a method (or even a property) in your master page, and use it in your pages to follow and adhere to the principal of DRY (Do not repeat yourself). Also in master page function (or property), you can use caching by a hidden class field, to make the performance even better. For example in your master page:

private User user;
public User User
{
   get
   {
       if (user == null)
       {
          // Load user and assign it to the user field
          user = LoadUser(HttpContext.Current.User.Identity.Name);
       }
       return user;
   }
}

Then in your pages, you can refer to your master page, by casting it to the type of your master page. For example, if the name of the master page class is GeneralMaterPage, then in a page using that master page, you can write:

public Page_Load(Object sender, EventArts e)
{
    User user = (MasterPage as GeneralMasterPage).User;
}

This way, you've implemented user extraction and loading code in one place. However, there is a better method for that.

You can write an HTTP Module and bind to AuthenticateRequest event, and do the authentication mechanism yourself. Then, if the user is valid, you can simply create a GeneralPrincipal including the real user name and populate HttpContext.Current.User with that principal.

Take a look at this link.


Verify string format with given pattern I'm implementing an auxiliary global function which has to check whether a given string has correct format (i.e., it begins with a letter and only contains letters, numbers or the "_" character).

This function, named ok_tret, will be used in the methods of a couple classes and will help ensure that the attributes are initialized with correct words and the rest of the methods are getting correct words as parameters.

The classes will be used in situations in which incorrect inputs are not frequent. They'll only happen when the user misspells the word, or by ignorance. So my guess is there will be two errors per read at worst.

My first ok_tret proposal returns a bool that tells us whether the given word is correct. This means we'll have to do the cin in the class method and then pass the word to the function. If there's error, then we'll have various function calls, until eventually the functions returns true.

const char *err4 = "ERROR. Init again.";

// Check correctness, return corresponding bool.
bool ok_tret(const string& nom) {
    if (not ((nom[0] >= 'a' and nom[0] <= 'z') or
        (nom[0] >= 'A' and nom[0] <= 'Z'))) {
        cout << err4 << endl;
        return false;
    }
    for (unsigned int i = 1; i < nom.length(); ++i) {
        if (not ((nom[i] >= '0' and nom[i] <= '9') or
            (nom[i] >= 'A' and nom[i] <= 'Z') or
            (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_')) {
                cout << err4 << endl;
                return false;
        }
    }
    return true;
}

The next proposal also does the cin, so in order to get a correct word there's no need for various function calls.

// Check correctness and cin until nom contains a correct word. Iterative.
void ok_tret(string& nom) {
    bool P = true;
    while (P) {
        if ((nom[0] >= 'a' and nom[0] <= 'z') or
            (nom[0] >= 'A' and nom[0] <= 'Z')) {
            for (unsigned int i = 1; P and i < nom.length(); ++i)
                if (not ((nom[i] >= '0' and nom[i] <= '9') or
                    (nom[i] >= 'A' and nom[i] <= 'Z') or
                    (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_'))
                    P = false;
        } else P = false;
        P = !P;
        if (P) {
            cout << err4 << endl;
            cin >> nom;
        }
    }
}

Finally a recursive solution, obviously there will be multiple function calls:

// Check correctness and cin until nom contains a correct word. Recursive.
void ok_tret(string& nom) {
    if (not ((nom[0] >= 'a' and nom[0] <= 'z') or
        (nom[0] >= 'A' and nom[0] <= 'Z'))) {
            cout << err4 << endl;
            cin >> nom;
            ok_tret(nom);
            return;
    }
    for (unsigned int i = 1; i < nom.length(); ++i) {
        if (not ((nom[i] >= '0' and nom[i] <= '9') or
            (nom[i] >= 'A' and nom[i] <= 'Z') or
            (nom[i] >= 'a' and nom[i] <= 'z') or nom[i] == '_')) {
                cout << err4 << endl;
                cin >> nom;
                ok_tret(nom);
                return;
        }
    }
}

I wanted to know:

Which proposal looks more natural?
Given the context in which the code will be used, there's no meaningful runtime difference between proposals. But... come on, which one would you choose and why?
If number of errors could be arbitrary (0 to a billion), which one would you choose and why?

I'd instead use the std::isalpha() to check for the alphabets, and for the rest; use isalnum() plus an or condition for the _ character.

Another check, I'd put is whether the input's length is indeed \$ \gt 0 \$. The code then becomes:

// Check correctness, return corresponding bool.
bool ok_tret(const string& nom) {
    if (nom.length() < 1) {
        // handle null strings
        return false;
    }
    if (not (bool) std::isalpha(nom[0])) {
        cout << err4 << endl;
        return false;
    }
    for (unsigned int i = 1; i < nom.length(); ++i) {
        if (not ((bool) std::isalnum(nom[i]) or nom[i] == '_')) {
                cout << err4 << endl;
                return false;
        }
    }
    return true;
}


Using a Wrapper Promise I wrote some code for an application that uses the following pattern:

function _getData() {
    return new Promise(function(resolve, reject) {
        if(_hasDataTypeA()) {
            SomeBackendAccessObject.getTypeAData().then(resolve, reject);
        } else {
            SomeBackendAccessObject.getTypeBData().then(_convertToTypeA).then(resolve, reject);
        }
    });
}

My rationale for writing the code this way is that if _hasDataTypeA throws an exception, we're still able to return a Promise. This means the caller doesn't have to do a try block and a Promise .catch; but this code feels smelly to me. Is there a better way to write it?

First thing I noticed is that your fulfilling the wrapper promise by way of other promises inside it. Seems like and extra step that isn't needed. Especially the final .then(resolve, reject) feels like a big anti-pattern especially since it is a repeated pattern. So the rational is to catch the exception. My take on this is to wrap only _hasDataTypeA in it's own promise and then use that result to manage the following promises:

function _hasDataTypeAPromised() {
  try {
    return Promise.resolve(_hasDataTypeA());
  } catch (e) {
    return Promise.reject(e);
  }
}

function _getData() {
  return _hasDataTypeAPromised()
    .then(function(hasDataTypeA) {
      if(hasDataTypeA) {
        return SomeBackendAccessObject.getTypeAData();
      } else {
        return SomeBackendAccessObject.getTypeBData();
      }
    });
}

You could even ternary-ize the method with:

var method = hasDataTypeA ? 'getTypeAData' : 'getTypeBData';
return SomeBackendAccessObject[method]();


Check of a traffic light sequence using an array and if statements I have create a functioning automated traffic light sequence using an array and if statements. It all work correctly but I am wondering if there is anything more I can do to improve my code without changing to structure or way it works, so without the use of dictionary's etc.

<!DOCTYPE html>

    <title> Traffic Light</title>

Traffic Light

    <canvas id="myCanvas" width="200" height="300"
    style="border:1px solid #000000;">
    Your browser does not support the HTML5 canvas tag.
    </canvas>

    <button onclick="changelight()">Click</button>

you don't ever use the strings in colors, but use them only as kind of id, what you are showing: an index would be sufficient, even the better solution.
you don't use the order in colors but instead you jump manually; sub-optimal, especially since you don't have any logic in there but just run a simple loop
And you repeat yourself excessively.

You have three lights, that are either on or off. To me this screams for the use of a bit-mask: The State is represented by an integer, and each bit of this integer represents one of the lights: it's either 1 or 0.

var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
ctx.rect(0, 0, 200, 300);
ctx.fillStyle = "grey";
ctx.fill();

//an array of the states, the code loops through
var activeLights = [0b100, 0b110, 0b001, 0b000, 0b010];
//var activeLights = [4, 6, 1, 0, 2];   //if your browser doesn't get the binary-notation
var currentIndex = 0;

function drawLight(index, color){
    ctx.beginPath();
    ctx.arc(95,50+index*100,40,10,12*Math.PI);
    ctx.fillStyle = color;
    ctx.fill();
    ctx.stroke();
}

function changelight(){
    var state = activeLights[currentIndex];

    //check the bit and draw the respective light
    drawLight(0, state & 0b100? "red": "black");
    drawLight(1, state & 0b010? "yellow": "black");
    drawLight(2, state & 0b001? "green": "black");
    //drawLight(0, state & 4? "red": "black");
    //drawLight(1, state & 2? "yellow": "black");
    //drawLight(2, state & 1? "green": "black");

    //the loop
    if(++currentIndex === activeLights.length) currentIndex = 0;
}

setInterval(changelight, 1000);


Find magnitude pole of an array Please review this code, considering I put emphasis on constraining space complexity at the expense of execution speed (accepting additional branching).

Can you see cases that prove the algorithm incorrect?
Could you improve its execution speed without increasing space complexity?
Could you make it more readable?

Method signature from Codility (i.e. strange capitalised parameter name).

Definition of "magnitude pole": available online (e.g. https://stackoverflow.com/questions/15397637/interview-find-magnitude-pole-in-an-array)

import java.util.Arrays;
public class MagnitudePole {
  public int solution(int[] A) {
    final int notFound = -1;
    final int minimumArrayLength = 2;
    if (A.length < minimumArrayLength) {
      return notFound;
    }
    int magnitudePole = 0;
    boolean isPoleValid = true;
    int highestSeen = A[magnitudePole];
    for (int i = 1; i < A.length; i++) {
      final int currentValue = A[i];
      if (currentValue < A[magnitudePole]) {
        isPoleValid = false;
      } else if (currentValue > A[magnitudePole]) {
        if (currentValue > highestSeen && !isPoleValid) {
          isPoleValid = true;
          magnitudePole = i;
        }
      } else {
        if (currentValue < highestSeen) {
          isPoleValid = false;
        } else {
          isPoleValid = true;
          magnitudePole = i;
        }
      }
      highestSeen = Math.max(currentValue, highestSeen);
    }
    return isPoleValid ? magnitudePole : notFound;
  }
}

Style

final int notFound = -1;
final int minimumArrayLength = 2;

These two fields can be better placed as private static final fields, instead of inside the method. On a related note, you may also want to consider turning this into an "utility class" and have the method as static too:

public class MagnitudePole {

    private static final int notFound = -1;
    private static final int minimumArrayLength = 2;

    private MagnitudePole() {
        // empty
    }

    // using an arguably better-sounding name... MagnitudePole.solveFor(int[])
    public static int solveFor(int[] A) {
        // ...
    }
}

For the currentValue > A[magnitudePole] else-if condition, you can join that with the inner if:

There's a bug here all right... The else should only be done on the original outer condition, so if the inner ifconditions fail it shouldn't reach there. Slightly edited the code block so as not to invalidate the comments on this part. :)

if (currentValue < A[magnitudePole]) {
    isPoleValid = false;
} else if (currentValue > A[magnitudePole] && currentValue > highestSeen && !isPoleValid) {
    isPoleValid = true;
    magnitudePole = i;
} else {
    /* this should only be reached when
        currentValue <= A[magnitudePole],
        bug in preceding else-if! */
}

Finally, in the else part, you can also re-order the conditions around as such:

} else {
    isPoleValid = currentValue >= highestSeen;
    if (isPoleValid) {
      magnitudePole = i;
    }
}

Logic + unit testing

You perform a check for the array to contain at least two elements, which means single-element arrays are conveniently bypassed. Do you actually want to consider them as magnitude poles, since all the LHS and RHS elements ("none", or \$\emptyset\$) are equal to it? :)

I will also suggest writing unit tests as a means of documenting what are the expected outputs for various inputs - valid, invalid, and edge cases in all. The slight benefit is that you can safely optimize your logic later on, and have a safety mechanism to ensure the modifications still work per expectation.


Python generator to produce lattice points on an n-simplex. Looking for a code review, and hopefully to learn something if someone has a nicer solution.  Here's what I wrote:

from __future__ import division, print_function
from future_builtins import *
import numpy as np

def _walk(num_dims, samples_per_dim, max_):
    if num_dims == 0:
        yield np.array([(max_ - 1) / (samples_per_dim - 1)])
    else:
        for i in range(max_):
            for rest in _walk(num_dims - 1, samples_per_dim, max_ - i):
                yield np.concatenate((np.array([i]) / (samples_per_dim - 1),
                                      rest))

def walk(num_dims, samples_per_dim):
    """
    A generator that returns lattice points on an n-simplex.
    """
    return _walk(num_dims, samples_per_dim, samples_per_dim)

So, list(walk(2, 3)) yields:

[array([ 0.,  0.,  1.]),
 array([ 0. ,  0.5,  0.5]),
 array([ 0.,  1.,  0.]),
 array([ 0.5,  0. ,  0.5]),
 array([ 0.5,  0.5,  0. ]),
 array([ 1.,  0.,  0.])]

Concatenating numpy arrays isn't a really good idea because that's not how they were designed to be used.

A better way might be this:

def walk(num_dims, samples_per_dim):
    """
    A generator that returns lattice points on an n-simplex.
    """
    values = np.arange(samples_per_dim) / (samples_per_dim - 1)
    for items in itertools.product(values, repeat = num_dims+1):
        if sum(items) == 1.0:
            yield items

Basically, we iterate over all possible combinations of those points, and filter out the invalid ones. This may seem wasteful, but since itertools is written in C, its probably actually faster then your solution. It produces tuples rather then numpy arrays.


Calling many web services asynchronously I need to process a bunch of completed orders (thousands). To make it faster, I'm using a SemaphoreSlim to schedule a number of orders to be processed in parallel. Every order goes through multiple web service calls to various APIs (SOAP, REST). Then I need to take the returned data and process it into a PDF. Here is what I am doing currently (note that this is in an ASP.NET app):

private async Task ProcessOrders(List<Orders> orders)
{
    var allTasks = new List<Task>();
    var throttler = new SemaphoreSlim(initialCount: 5);

    foreach (var order in orders.Where(x => !x.HasError))
    {
        // do an async wait until we can schedule again
        await throttler.WaitAsync();

        // using Task.Run() to run the lambda in its own parallel
        // flow on the thread pool
        allTasks.Add(Task.Run(async () =>
        {
            try
            {
                // Call external web service here
                // Build order report PDF here
            }
            finally
            {
                throttler.Release();
            }
        }));
    }

    await Task.WhenAll(allTasks);
}

However, I'm new to TPL and I don't know if this is the right way to do something like this. If it's relevant, this app is hosted on Amazon's AWS cloud.

I'm not all that familiar with async/await (I really need to get going on this), but I find your code pretty clear, except why the magic number  5 is being used for an initialCount.

I like your usage of var, but the comments are a little redundant, they say nothing much that the code doesn't already tell.

It would have been nice to see the actual code in place of the placeholder comments in the try block - I'd expect to see a method call here; if that comment stands for code that actually implements what's described, you need to factor it out.

Also I would have indented the async task's body, but that's more of a nitpick.

I would probably also have introduced a var validOrders = orders.Where(order => !order.HasError); to make the foreach loop clearer. Not sure I like x for a name in the lambda: try to use meaningful names everywhere.


Printing all prime factors of a number input by the user I just started teaching myself to code a few days ago using the Euler problems. I finished a variant of problem 3: print the prime factors of a number input by the user. I just want feedback and code cleaning from someone who knows better than I do to help me progress.

import math

#What is the largest prime factor of the number 600851475143?

n=raw_input('Enter the integer you wish to find the prime factors of: ')

n = int(float(n))
L=[]

def too_small():
        """to be called for int < 4"""
        L.append(n)
        if n>0:
                L.append(1)
        return L

if n < 4: #alg only works for int > 4
        L = too_small()
        print L
        exit()

if n == 4: #because I'm lazy
        L.append(2)
        L.append(2)
        print L
        exit()

def primefactor():
        """prints list of all prime factors for int > 4"""
        test=True
        b=n
        while(test):
                i=2
                while((b%i!=0)&(i<(b/2))): #find next prime
                        i=i+1
                if i>=(b/2): #number is prime
                        L.append(b)
                        L.append(1)
                        test=False
                else: #number is not prime
                        a=(b/i)
                        L.append(i)
                        b=a
        return L

L = primefactor()
print L

exit()

Consistency

Why is there sometimes a 1 at the end of the results?  Should it even be there, considering that 1 is not a prime number?  If you do include it in the results, why is it at the end instead of at the beginning of the list?

Enter the integer you wish to find the prime factors of: 60
[2, 2, 3, 5, 1]

Enter the integer you wish to find the prime factors of: 5
[5, 1]

Enter the integer you wish to find the prime factors of: 4
[2, 2]

Lint

PEP 8, the official style guide, specifies 4 spaces per level of indentation.  This is a strong convention for Python, where whitespace is significant.

Also, by PEP 8, primefactor() would be better named prime_factors().

It makes no sense to convert n to a float, then convert it again to an int.

import math is pointless; you never use anything in the math module.

Some of your comments are unclear.  For example:

if i>=(b/2): #number is prime

… would be better written as # b is prime.

Since this is all integer arithmetic, you can prepare your code for use with Python 3 by using the // operator rather than /.

Counting loops in Python are better written using some kind of for loop in conjunction with an iterator.  Here, I recommend itertools.count(2).

Generality and organization

primefactor() would be better as a function that accepts a parameter, rather than using the global variable n.  It should definitely return a list that it created, rather than modifying a global L as a side-effect.

Why doesn't primefactor() also work for n ≤ 4?  If you organized the code properly, the caller wouldn't be responsible for handling special cases (which aren't even necessary in the first place).  There would be no need to call exit() — which you should almost never need in a properly structured program.

Flag variables, especially poorly named ones like test, are rarely desirable or necessary.  Here, you can easily eliminate the test variable by changing test=False to return L.

First rewrite

Incorporating the remarks above, and more…

from itertools import count

def prime_factors(n):
    factors = []
    for i in count(2):
        while n % i == 0:
            factors.append(i)
            n //= i
        if 2 * i > n:
            return factors

n = int(raw_input('Enter the integer you wish to find the prime factors of: '))
print(prime_factors(n))

Yielding results

You can stream the results back to the caller by yielding prime factors as you find them, rather than building the entire list.

As an optimization, you can avoid considering even factors other than 2.

from itertools import chain, count

def prime_factors(n):
    for i in chain([2], count(3, 2)): # Try 2, 3, 5, 7, 9, 11, 13, 15...
        while n % i == 0:
            yield i
            n //= i
        if 2 * i > n:
            return

n = int(raw_input('Enter the integer you wish to find the prime factors of: '))
print(', '.join(prime_factors(n)))


Find-grep-sed for project-wide search & replace I always forget how to do this efficiently with Vim's arglist. Drawing inspiration from a post over at Stack Overflow, I wrote a Bash function to perform a project-wide search & replace.

It does the following:

find files matching a file-pattern
narrow down to those files containing a search-pattern
within those files, replace all occurrences of the search-pattern

Example usage: greplace **.rb old_method new_method

greplace() {
  if [ "${#}" != 3 ]; then
    echo "Usage: greplace file_pattern search_pattern replacement"
    return 1
  else
    file_pattern=$1
    search_pattern=$2
    replacement=$3

    find . -name "${file_pattern}" |
    xargs grep -rwl "${search_pattern}" |
    xargs sed -i '' "s/[[:<:]]${search_pattern}[[:>:]]/${replacement}/g"
  fi
}

I'm on OSX, so unfortunately I had to use the ugly (and I assume non-portable) [[:<:]] word-boundaries for sed. I tried \b and \<, with and without -E (for extended regular expressions), but still no dice.

I also debated whether to bake the word-boundaries in or leave them up to the caller (my poor little fingers). But I can't imagine wanting use this without word boundaries. I'd much rather miss a replacement because it's a variation on the search term than accidentally mangle a word happens to contain the search term.

Another potential issue is the fact that I'm using sed -i '' to perform the in-place replacements without making any backup files. This seems fine for my use, since I'm invariably using Git for version control. I'm curious how big a risk this is though.

Update Props to janos for his pointers and improvements. Here's an updated version:

greplace() {
  if [ "$#" != 3 ]; then
    echo "Usage: greplace file_pattern search_pattern replacement"
    return 1
  else
    file_pattern=$1
    search_pattern=$2
    replacement=$3

    # This works with BSD grep and the sed bundled with OS X.
    # GNU grep takes `-Z` instead of `--null`.
    # Other versions of sed may not support the `-i ''` syntax.

    find . -name "$file_pattern" -exec grep -lw --null "$search_pattern" {} + |
    xargs -0 sed -i '' "s/[[:<:]]$search_pattern[[:>:]]/$replacement/g"
  fi
}

Not bad so far!

You seem to like ${name} instead of $name. That's fine, but it's not needed anywhere in the posted code. Usually it's needed in situations like ${name}_suffix, where without the ${...} the "_suffix" would become part of the variable name.

In general, the best way to find files and do something to them is using the -exec flag of find, for example:

find . -name "$file_pattern" -exec grep -rwl "$search_pattern" {} \;
# or end with + to run on a single line
#find . -name "$file_pattern" -exec grep -rwl "$search_pattern" {} +

The second best way is to pipe to xargs -0, and use -print0, for example:

find . -name "$file_pattern" -print0 | xargs -0 grep -rwl "$search_pattern"

Your case has an added twist: you also want to pipe the matched filenames from grep, and like find, the proper way is to use NUL character as the filename separator. In GNU grep the flag to achieve this is -Z. Putting the above together, the safest way to write your chained command:

find . -name "${file_pattern}" -exec grep -Zrwl "${search_pattern}" \; |
xargs -0 sed -i '' "s/[[:<:]]${search_pattern}[[:>:]]/${replacement}/g"

As for [[:<:]], I don't know another way on OSX. In any case, the sed -i '' filaname usage won't work with GNU sed, so this script is not portable.
It would be good to add comments near the top of the file to highlight this fact to whoever will inherit this script from you at some point in the future.
(Uhm, or in any case, for the "future you" ;-)

Lastly, I'm wondering if the -r flag for grep is intentional.
It's for recursive search in sub-directories, not only files.
If that's not intended, then drop that flag.


Using pointers for string manipulation I'm taking a sentence and determining whether or not it is a palindrome. I'm doing this while learning about stacks.

Is there a way I can use pointers instead of char array 'sent' so that the number of input characters need not be constrained to 20 in the following code?
The code is working fine, but should there be any improvements in terms of performance or anything else?
Is there anything important about pointers I should remember while using stacks, like initializing it to NULL?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct node
{
    char data;
    struct node *link;
}StackNode;

void insertData(StackNode **);
void push(StackNode **, char);
void checkData(StackNode **);
bool pop(StackNode **,char *);

char sent[20] = "";

void main()
{
   StackNode *stackTop;
   stackTop = NULL;
   insertData(&stackTop);
   checkData(&stackTop);
   printf("\n");
   return;
}

void insertData(StackNode **stackTop)
{
    char c;
    int len;

    printf("Enter the Sentence\n");
    while( ( ( c = getchar() ) != '\n'))
    {
        if( ( ( c>='a' &&c<='z') || (c>='A' && c<='Z')))
        {
            if((c>='A' && c<='Z'))
            {
                int rem;
                rem = c-'A';
                c='a' + rem;
            }
            push(stackTop,c);
            len = strlen(sent);
            sent[len++]=c;
            sent[len]='\0';
        }
    }
    printf("Letters are %s\n\n",sent);
}

void push(StackNode **stackTop,char c)
{
    StackNode *pNew;
    pNew = (StackNode*) malloc(sizeof(StackNode));
    if(!pNew)
    {
        printf("Error 100:Out of memory\n");
        exit(100);
    }
    pNew->data = c;
    pNew->link = *stackTop;
    *stackTop = pNew;
}

void checkData(StackNode **stackTop)
{
    char c;
    int i=0;
    while(pop(stackTop,&c))
    {
        if( c !=sent[i++])
        {
            printf("Not palindrome");
            return;
        }
    }
    printf("Palindrome");
}

bool pop(StackNode **stackTop,char *c)
{
    StackNode *pNew;
    pNew = *stackTop;
    if(pNew == NULL)
        return false;
    *c = pNew->data;
    *stackTop = pNew->link;
    printf("char poped %c\n",*c);
    free(pNew);
    return true;
}

One MAJOR problems here.

char sent[20] = "";

Don't use global variables. Globally mutable state makes your code hard to debug/test and generally behave correctly. You not only need to know what a function does but also what external state the function depends on. Pass all state into functions via the parameters (that way you know exactly what it depends on).

Note: Global constants are fine.

This is not a valid declaration of main() even in C

void main()

/* TRY */

int main(void)
/* OR */
int main(int argc, char* argv[])

Lets declare and initialize variables on the same line:

   StackNode *stackTop;
   stackTop = NULL;

   /* Try */
   StackNode *stackTop = NULL;

Note if you correct main you will also need to correct the return statement so it returns a value.

   return;

But when the function is void there seems little point in putting a return statement.

OK. This reads a line.

void insertData(StackNode **stackTop)

But there are already functions that do that.
You can use the scanf series of commands. Your code drops any non alphabetic characters (but you could read a line then post processes to remove and invalid characters).

You should read up on the functions for handling characters.

isalpha()       /* Note it is locale aware and thus will return true
                   for characters other than a-z A-Z if your locale is
                   not set to the default (which is C)
                 */

tolower()       /* Lowercases letters. No affect on anything else */

I would have done:

char  data[50]; /* You wanted a max of 20 letters.
                   But if the user types a space between every word
                   it can get longer and we post processes to remove
                   space so. So we will cut off at 50.
                */

fscanf(stdin, "%50[^\n]", data); /* read upto 50 characters
                                    that are not '\n'
                                    into data
                                 */
fscanf(stdin, "%*[^\n]");        /* Read the rest of the line if
                                    the user types more than 50 and
                                    throw it away
                                 */
fscanf(stdin, "\n");             /* Read the '\n' off the input */

/* Now remove any non letter characters and lowercase at the same time */
int removed = 0;
for(int loop = 0; data[loop]; ++loop)
{
    if (!isalpha(data[loop]))
    {
        removed++;
        continue;       // starts next iteration.
    }
    data[loop-removed] = tolower(data[loop]);
}
data[loop-removed] = '\0';  /* Add string terminator */

Back to reviewing your version.

This is going to enter an infinite loop if you hit an error or end of file before you hit '\n'.

    while( ( ( c = getchar() ) != '\n'))

Then end of file is a real possibility if somebody pipes a file into your command from the command line.

    cat file | ./palindromeCommand

This check:

        if( ( ( c>='a' &&c<='z') || (c>='A' && c<='Z')))

Is really covered by: isalpha()

This check:

            if((c>='A' && c<='Z'))
            {
                int rem;
                rem = c-'A';
                c='a' + rem;
            }

Is the same as:  c = tolower(c);

This string append:

            len = strlen(sent);
            sent[len++]=c;
            sent[len]='\0';

Can be achieved with: strncat(sent, &c, 1);

Normally I don't want checking functions to mutate the state of any objects. The name "check" implies I am looking not modifying.

void checkData(StackNode **stackTop)

Also you are mixing business logic and presentation logic into a single function. Make this function check to see if it a palindrome and return an appropriate value (0 for false and non zero for true (for example)). The code can then use this function to check for a palindrome and take appropriate action (like display text) in the display logic:

Initialize and declare in the same line:

    StackNode *pNew;
    pNew = *stackTop;

    /* Easier to read as */
    StackNode *pNew = *stackTop;

Overall I think you overcomplicated the processes with your StackNode concept. But it works. It would have been much simpler to use pointers to either end of the sent array and work towards the middle checking letters.

int checkForPalindrome(char* sent, int length)
{
     char*    st   = sent;
     char*    ed   = sent + length - 1;

     int   result = true;

     while(st < ed && result)
     {
         if (*st != *ed) { result = false;}
         ++st;
         --ed;
     }
     return result;
}


Handling name variants Part of my standard modules deal with my company's employees and linking them to/from various data sets.

The following are a series of enums/functions to handle peoples' names, namely an Enum for advisers and functions to:

Provide a collection of names associated to each adviser (e.g. their name before/after getting married)
Provide the current name of each adviser
Determine which adviser's name appears in a given string

Is this a good, maintainable, extensible system? Especially considering the possibility of new employees over time?

Option Explicit

Public Enum LuminAdviser
    MartinCotter = 1
    JonHussey = 2
    JeremySmith = 3
    JonathanBlair = 4
    JohnCusins = 5
    SarahCotter = 6
    MickyMahbubani = 7
End Enum

Public Function NameStringsFromAdviser(ByVal adviser As LuminAdviser) As Collection

    Dim coll As Collection
    Set coll = New Collection

    Select Case adviser

        Case JonHussey
        AddNameVariations coll, "Jon", "Hussey"

        Case MartinCotter
        AddNameVariations coll, "Martin", "Cotter"

        Case JeremySmith
        AddNameVariations coll, "Jeremy", "Smith"

        Case JonathanBlair
        AddNameVariations coll, "Jonathan", "Blair"

        Case SarahCotter
        AddNameVariations coll, "Sarah", "Cotter"
        AddNameVariations coll, "Sarah", "Oluwole"

        Case JohnCusins
        AddNameVariations coll, "John", "Cusins"

        Case MickyMahbubani
        AddNameVariations coll, "Micky", "Mahbubani"

    End Select

    Set NameStringsCollectionFromAdviser = coll

End Function

Public Sub AddNameVariations(ByRef coll As Collection, ByVal forename As String, ByVal surname As String)

    coll.Add forename & " " & surname
    coll.Add surname & ", " & forename

End Sub

Public Function CurrentNameStringFromAdviser(ByVal adviser As LuminAdviser) As String

    Dim nameString As String

    Select Case adviser

        Case JonHussey
        nameString = "Hussey, Jon"

        Case MartinCotter
        nameString = "Cotter, Martin"

        Case JeremySmith
        nameString = "Smith, Jeremy"

        Case JonathanBlair
        nameString = "Blair, Jonathan"

        Case SarahCotter
        nameString = "Oluwole, Sarah"

        Case JohnCusins
        nameString = "Cusins, John"

        Case MickyMahbubani
        nameString = "Mahbubani, Micky"

    End Select

    CurrentNameStringFromAdviser = nameString

End Function

Public Function AdviserFromString(ByVal str As String) As LuminAdviser

    Dim foundAdviser As Boolean
    foundAdviser = True

    Dim adviser As LuminAdviser

    If AdviserNameInString(JeremySmith, str) Then
        adviser = JeremySmith

    ElseIf AdviserNameInString(JohnCusins, str) Then
        adviser = JohnCusins

    ElseIf AdviserNameInString(JonathanBlair, str) Then
        adviser = JonathanBlair

    ElseIf AdviserNameInString(JonHussey, str) Then
        adviser = JonHussey

    ElseIf AdviserNameInString(MartinCotter, str) Then
        adviser = MartinCotter

    ElseIf AdviserNameInString(MickyMahbubani, str) Then
        adviser = MickyMahbubani

    ElseIf AdviserNameInString(SarahCotter, str) Then
        adviser = SarahCotter

    Else
        foundAdviser = False

    End If

    If Not foundAdviser Then PrintErrorMessage "Could not find any adviser in string: " & str

    AdviserFromString = adviser

End Function

Public Function AdviserNameInString(ByVal adviser As LuminAdviser, ByVal str As String) As Boolean

    Dim foundAdviser As Boolean
    foundAdviser = False

    Dim nameColl As Collection
    nameColl = NameStringsFromAdviser(adviser)

    Dim i As Long
    For i = 1 To nameColl.Count
        If InStr(1, str, nameColl(i)) > 0 Then
            foundAdviser = True
            Exit For
        End If
    Next i

    AdviserNameInString = foundAdviser

End Function

First, I thought I'd mention that your code is stylistically really good - variable and function names make sense, indentation is great (with one small exception noted below), and the functions are focused and readable.  Just one minor point:

The code under each Case in a Select Case is typically indented one more level:

Select Case adviser
    Case JonHussey
        AddNameVariations coll, "Jon", "Hussey"
    Case MartinCotter
        '...

As far as your specific question goes, this actually looks like it would be quite a chore to maintain.  Adding a new name to an existing advisor is easy with your set-up.  For example, if John Cusins decided to change his name to Jim Nasium, all you would have to do is add AddNameVariations coll, "Jim", "Nasium" under his Case in NameStringsFromAdviser and change his Case in CurrentNameStringFromAdviser to NameString = "Nasium, Jim".

But, this points to the next issue - your Enum isn't really serving much use as much other than a place-holder.  On the one hand you could change the JohnCusins element to JimNasium everywhere in your code, but this kind of defeats the purpose of having a named identifier.  On the other hand you could leave it as JohnCusins, but this now means that it isn't appropriately named - why should the Enum element associated with a person be different from their name? If I was only looking at the CurrentNameStringFromAdviser function and not the entire module, I'd be wondering "why is the SarahCotter case returning Oluwole, Sarah?"

This also points to the main issue in maintainability and extensibility - to add an advisor, you need to change the code in 3 different functions and add a value to the enumeration.  At the same time, you need to make sure that those changes are all consistent with each other. The urge to copy and paste will be very hard to resist...

...which leads to the last point - you're repeating code all over the place. This gives me a whiff of code smell. Wouldn't it be nice if you didn't have to type If AdviserNameInString(FooBar, str) Then again and again and again?  It would be much better to approach this problem with the mantra Don't Repeat Yourself in mind.  This is a problem begging for an OO solution.

You have 2 distinct things you care about - advisors and names. So make an advisor class and a name class.  Make them responsible for the things that advisors and names care about.  I.e.:

Name.cls

Option Explicit

Private mFirst As String
Private mLast As String

Public Property Let FirstName(first As String)
    mFirst = first
End Property

Public Property Get FirstName() As String
    FirstName = mFirst
End Property

Public Property Let LastName(last As String)
    mLast = last
End Property

Public Property Get LastName() As String
    LastName = mLast
End Property

Public Property Get NameString() As String
    NameString = mLast & ", " & mFirst
End Property

Public Function Matches(test As String) As Boolean
    Matches = InStr(1, test, mFirst) Or InStr(1, test, mLast)
End Function

Advisor.cls:

Option Explicit

Private mNames As New Collection
Private mPreferred As Name

Public Sub AddName(inValue As Name)
    mNames.Add inValue
End Sub

Public Property Set PreferredName(inValue As Name)
    Set mPreferred = inValue
    mNames.Add inValue
End Property

Public Property Get PreferredName() As Name
    Set PreferredName = mPreferred
End Property

Public Function NameMatches(test As String) As Boolean
    Dim candidate As Variant
    For Each candidate In mNames
        If candidate.Matches(test) Then
            NameMatches = True
            Exit For
        End If
    Next candidate
End Function

Note, it isn't clear from your question if the numbers in the Enum have meaning outside of the code that you posted. If they are, just make them a property of Advisor. Throw in a couple factory functions to easily generate objects (curse you VBA for not having constructors)...

'Name factory.
Public Function NewName(first As String, last As String) As Name
    Set NewName = New Name
    NewName.FirstName = first
    NewName.LastName = last
End Function

'Advisor factory
Public Function NewAdvisor(preferred As Name, _
                           ParamArray names() As Variant) As Advisor
    Dim variation As Variant

    Set NewAdvisor = New Advisor
    Set NewAdvisor.PreferredName = preferred

    For Each variation In names
        Dim cast As Name
        Set cast = variation
        NewAdvisor.AddName cast
    Next variation
End Function

...and you get something to maintain that looks like this:

Option Explicit

Private Advisors As Collection

Public Sub InitializeAdvisors()
    Set Advisors = New Collection

    Advisors.Add NewAdvisor(NewName("Jon", "Hussey"))
    Advisors.Add NewAdvisor(NewName("Martin", "Cotter"))
    Advisors.Add NewAdvisor(NewName("Jeremy", "Smith"))
    Advisors.Add NewAdvisor(NewName("Jonathan", "Blair"))
    Advisors.Add NewAdvisor(NewName("Sarah", "Oluwole"), _
                            NewName("Sarah", "Cotter"))
    Advisors.Add NewAdvisor(NewName("John", "Cusins"))
    Advisors.Add NewAdvisor(NewName("Micky", "Mahbubani"))
End Sub

Public Function FindAdvisor(inValue As String) As Advisor
    Dim candidate As Variant
    For Each candidate In Advisors
        If candidate.NameMatches(inValue) Then
            Set FindAdvisor = candidate
            Exit Function
        End If
    Next candidate
End Function

Example usage:

Private Sub ExampleUsage()
    InitializeAdvisors
    Debug.Print FindAdvisor("Someone named Sarah").PreferredName().NameString
End Sub

Add an advisor? One line of code. Add an alias? Change one line of code. Remove an advisor? Delete one line of code. Change from "Last, First" format to "First Last" format? Change one line of code. An advisor has 42 aliases? No problem - just add them all in one place. Now that is easy to maintain.


GCD using Euclid algorithm Below is the problem taken from here.

  Question 10: GCD*

  The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of a and b is one of the following:

  the smaller value if it evenly divides the larger value, OR
  the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value
  In other words, if a is greater than b and a is not divisible by b, then

  gcd(a, b) == gcd(b, a % b)

  Write the gcd function recursively using Euclid's algorithm.

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"

Solution:

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    if b > a:
        if b % a == 0:
            return a
        else:
            return gcd(b % a, a)
    else:
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)

How can I improve this nested if block?

One of the nice things with recursion is that you can use it for argument handling.

Where you have a conditional to handle the b > a condition, you could instead use recursion.....

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    if b > a:
        return gcd(b, a)

    if a % b == 0:
        return b

    return gcd(b, a % b)


Thread safe log class which creates log files according to the current date when entry was added From this question and some help I created a thread safe logging class on which the name of the log file is same as the current date (short date) when the log entry was added. e.g. If I create ten entries today say they will all get written to log file named "07.10.2015.txt". I want to use this class from DLL.
I am curious on your opinion if this is reasonable and thread safe class?

public static class Logger
{
    static readonly object _syncObject = new object();

    public static void Write(string logMessage)
    {
        try
        {
            var todaysLogFilePath = Path.Combine(ConfigManager.GetAppSetting("logPath"),
                                                    ("Log" + DateTime.Now.ToString("yyyy-MMMM-dd") + ".txt"));
            Log(logMessage, todaysLogFilePath);
        }
        catch (IOException e)
        {
            //log somewhere else if required
        }
    }

    static void Log(string logMessage, string logFilePath)
    {
        lock (_syncObject)
        {
            File.AppendAllText(logFilePath,
                        string.Format("{0} {1} {2}",
                        DateTime.Now.ToLongTimeString(), DateTime.Now.ToLongDateString(), logMessage));
        }
    }
}

PS. I don't want third party classes because they have some requirements sometimes if used from DLL which is my requirement, and in some cases I don't know directly how to enable in those classes ability to name the log entries same as the current date when log was added.

static readonly object _syncObject = new object();

You should always add a scope identifier because it increases readability.

var todaysLogFilePath = Path.Combine(ConfigManager.GetAppSetting("logPath"),
                                        ("Log" + DateTime.Now.ToString("yyyy-MMMM-dd") + ".txt"));
Log(logMessage, todaysLogFilePath);

Each time the Write() method is called you are

reading from the config to get the logging path
construct a new filepath

I know why you are doing this, but it could be done in a better way. You could add a field

private static DateTime currentDate = DateTime.Now.Date;

so it is initialized at startup.

Next you could add a field

private string logFilePath;

and a method ComposeLogFilePath(DateTime) like so

private static string ComposeLogFilePath(DateTime date)
{
    return Path.Combine(ConfigManager.GetAppSetting("logPath"),
                             ("Log" + date.ToString("yyyy-MMMM-dd") + ".txt"));
}

which you then call from this constructor

static Logger()
{
    logFilePath = ComposeLogFilePath(currentDate);
}

By adding a method which checks if a change in the date has happened and if a new logFilePath needs to be composed like so

private static void CheckLogFileAndCreateIfNeeded()
{
    if (currentDate >= DateTime.Now.Date) { return; }

    currentDate = DateTime.Now.Date;
    logFilePath = ComposeLogFilePath(currentDate);
}

The method name is not the best, maybe you or some answerer will come up with a better one.

So each time the Write() method is called you call this method like so

public static void Write(string logMessage)
{
    try
    {
        CheckLogFileAndCreateIfNeeded();

        Log(logMessage, logFilePath);
    }
    catch (IOException e)
    {
        //log somewhere else if required
    }
}

which leads to the next point: Usually a Logger will log something so better change the names Write()-> Log() and Log() -> Write().

static void Log(string logMessage, string logFilePath)
{
    lock (_syncObject)
    {
        File.AppendAllText(logFilePath,
                    string.Format("{0} {1} {2}",
                    DateTime.Now.ToLongTimeString(), DateTime.Now.ToLongDateString(), logMessage));
    }
}

Here you should store DateTime.Now inside a variable to have the calls ToLongTimeString() and ToLongTimeString() using the same DateTime like so

static void Log(string logMessage, string logFilePath)
{
    lock (_syncObject)
    {
        DateTime date = DateTime.Now;
        File.AppendAllText(logFilePath,
                    string.Format("{0} {1} {2}",
                    date.ToLongTimeString(), date.ToLongDateString(), logMessage));
    }
}

Threadsafety is no issue here because of the lock but you could do this in a much better way by having a ConcurrentQueue in which you store the formatted message to log.

Then add a method to query the queue which ideally should spawn a thread to do the work. If there is already a thread running, you can just return from this method. If there is no thread running, start it and return.

By using a ConcurrentQueue you could get rid of the lock and you wouldn't need for each message to open the file.


(Leetcode) Perfect Rectangle This is a Leetcode problem -

  Given \$N\$ axis-aligned rectangles where \$N\$ \$>\$ 0, determine if
  they all together form an exact cover of a rectangular region.

  Each rectangle is represented as a bottom-left point and a top-right
  point. For example, a unit square is represented as [1, 1, 2, 2].
  (coordinate of the bottom-left point is (1, 1) and the top-right
  point is (2, 2)).

  Example 1 -

rectangles = [
  [1, 1, 3, 3],
  [3, 1, 4, 2],
  [3, 2, 4, 4],
  [1, 3, 2, 4],
  [2, 3, 3, 4]
]

# Explanation - Return True. All 5 rectangles together form an exact cover of a rectangular region.

  Example 2 -

rectangles = [
  [1, 1, 2, 3],
  [1, 3, 2, 4],
  [3, 1, 4, 2],
  [3, 2, 4, 4]
]

# Explanation - Return False. Because there is a gap between the two rectangular regions.

  Example 3 -

rectangles = [
  [1, 1, 3, 3],
  [3, 1, 4, 2],
  [1, 3, 2, 4],
  [3, 2, 4, 4]
]

# Explanation - Return False. Because there is a gap in the top center.

  Example 4 -

rectangles = [
  [1, 1, 3, 3],
  [3, 1, 4, 2],
  [1, 3, 2, 4],
  [2, 2, 4, 4]
]

# Explanation - Return False. Because two of the rectangles overlap with each other.

Here is my solution to this challenge -

def is_rectangle_cover(rectangles):

    if len(rectangles) == 0 or len(rectangles[0]) == 0:
        return False
    x1 = float("inf")
    y1 = float("inf")
    x2 = 0
    y2 = 0
    rect = set()
    area = 0
    for points in rectangles:
        x1 = min(points[0], x1)
        y1 = min(points[1], y1)
        x2 = max(points[2], x2)
        y2 = max(points[3], y2)
        area += (points[3] - points[1]) * (points[2] - points[0])
        rect.remove((points[0], points[3])) if (points[0], points[3]) in rect else rect.add((points[0], points[3]))
        rect.remove((points[0], points[1])) if (points[0], points[1]) in rect else rect.add((points[0], points[1]))
        rect.remove((points[2], points[3])) if (points[2], points[3]) in rect else rect.add((points[2], points[3]))
        rect.remove((points[2], points[1])) if (points[2], points[1]) in rect else rect.add((points[2], points[1]))
    if (x1, y2) not in rect or (x2, y1) not in rect or (x1, y1) not in rect or (x2, y2) not in rect or len(rect) != 4:
        return False
    return area == (y2 - y1) * (x2 - x1)

Here are the times taken for each example output -

Example 1 -

# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]])

14.9 µs ± 117 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Example 2 -

# %timeit is_rectangle_cover([[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2],[3, 2, 4, 4]])

12.5 µs ± 494 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Example 3 -

# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4]])

12.4 µs ± 195 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Example 4 -

# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]])

12 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Here is my Leetcode result for 46 test cases -

Therefore, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Use tuples

...instead of lists when your data are immutable. There are a few advantages, including marginal performance increases in some scenarios, and catching "surprises" where code is attempting to modify your data where it shouldn't.

Unpack your tuples

Indexing points is nasty.

Use more sets

I think my rewritten code with set operators is equivalent. Peruse the documentation for info on the symmetric difference ^ and subset < operators.

Edit: you don't even need the subset test; all you need is set equality.

Don't "ternary instead of if"

Even if you didn't do the symmetric set operation and kept your add/remove code, just... don't do this. It's the worst mix of "too clever", "too illegible" and "difficult to maintain".

Coalesce your returns

...into one boolean statement, for simplicity.

Proposed

def is_rectangle_cover_orig(rectangles):
    if len(rectangles) == 0 or len(rectangles[0]) == 0:
        return False
    x1 = float("inf")
    y1 = float("inf")
    x2 = 0
    y2 = 0
    rect = set()
    area = 0
    for points in rectangles:
        x1 = min(points[0], x1)
        y1 = min(points[1], y1)
        x2 = max(points[2], x2)
        y2 = max(points[3], y2)
        area += (points[3] - points[1]) * (points[2] - points[0])
        rect.remove((points[0], points[3])) if (points[0], points[
            3]) in rect else rect.add((points[0], points[3]))
        rect.remove((points[0], points[1])) if (points[0], points[
            1]) in rect else rect.add((points[0], points[1]))
        rect.remove((points[2], points[3])) if (points[2], points[
            3]) in rect else rect.add((points[2], points[3]))
        rect.remove((points[2], points[1])) if (points[2], points[
            1]) in rect else rect.add((points[2], points[1]))
    if (x1, y2) not in rect or (x2, y1) not in rect or \
            (x1, y1) not in rect or (x2, y2) not in rect or len(rect) != 4:
        return False
    return area == (y2 - y1) * (x2 - x1)

def is_rectangle_cover_new(rectangles):
    if len(rectangles) == 0 or len(rectangles[0]) == 0:
        return False
    x1, y1 = float("inf"), float("inf")
    x2, y2 = 0, 0
    rect = set()
    area = 0
    for xr1, yr1, xr2, yr2 in rectangles:
        x1 = min(xr1, x1)
        y1 = min(yr1, y1)
        x2 = max(xr2, x2)
        y2 = max(yr2, y2)
        area += (yr2 - yr1) * (xr2 - xr1)
        rect ^= {(xr1, yr2), (xr1, yr1), (xr2, yr2), (xr2, yr1)}
    return (
        rect == {(x1, y2), (x2, y1), (x1, y1), (x2, y2)} and
        area == (y2 - y1) * (x2 - x1)
    )

def test():
    for i, rects in enumerate((
        (
            (1, 1, 3, 3),
            (3, 1, 4, 2),
            (3, 2, 4, 4),
            (1, 3, 2, 4),
            (2, 3, 3, 4)
        ),
        (
            (1, 1, 2, 3),
            (1, 3, 2, 4),
            (3, 1, 4, 2),
            (3, 2, 4, 4)
        ),
        (
            (1, 1, 3, 3),
            (3, 1, 4, 2),
            (1, 3, 2, 4),
            (3, 2, 4, 4)
        ),
        (
            (1, 1, 3, 3),
            (3, 1, 4, 2),
            (1, 3, 2, 4),
            (2, 2, 4, 4)
        )
    ), 1):
        old_ans = is_rectangle_cover_orig(rects)
        new_ans = is_rectangle_cover_new(rects)
        print(f'Example {i}: {old_ans}')
        assert old_ans == new_ans

test()


Simple Python Benchmark The following is a quick attempt at testing some limits of my computer:
import multiprocessing
import time

def main():
    numbers = tuple(multiprocessing.Value('Q', 0, lock=False) for _ in range(multiprocessing.cpu_count()))
    processes = tuple(multiprocessing.Process(target=count, args=(number,)) for number in numbers)
    for process in processes:
        process.start()
    time.sleep(10)
    for process in processes:
        process.terminate()
    print(sum(number.value for number in numbers))

def count(number):
    while True:
        number.value += 1

if __name__ == '__main__':
    main()

Without changing the overall design (adding one to a variable as many times as possible within a certain time limit), is there a way to improve the performance of the code? In this case, having a higher number printed out on the same computer is better.

Yes, there is at least one way to increase the performance of the adding loop. You should have as few bytecode instructions in that loop as possible. Right now, you are accessing the attribute of a variable. Such an operation can be eliminated by only assigning to that attribute once all of the additions have been run in the given time limit. By starting another thread waiting on a barrier, you can signal the main threading with a keyboard interrupt when the time limit has expired. When handling the exception, that is when you can assign the total number of addition operations to the number's value attribute.
import _thread
import multiprocessing
import threading
import time

def main():
    numbers = tuple(multiprocessing.Value('Q', 0, lock=False) for _ in range(multiprocessing.cpu_count()))
    signal = multiprocessing.Barrier(len(numbers) + 1)
    processes = tuple(multiprocessing.Process(target=count, args=(number, signal)) for number in numbers)
    for process in processes:
        process.start()
    time.sleep(10)
    signal.wait()
    for process in processes:
        process.join()
    print(sum(number.value for number in numbers))

def count(number, signal, temp=0):
    threading.Thread(target=terminate, args=(signal,)).start()
    try:
        while True:
            temp += 1
    except KeyboardInterrupt:
        number.value = temp

def terminate(signal):
    signal.wait()
    _thread.interrupt_main()

if __name__ == '__main__':
    main()


Query the Max Nth per group I'm trying to write the most efficient query I can to pull the relevant data I need for retrieving the latest conversations for a user, ordering groupings of conversations by most recent message in that conversation.

I don't like the idea of using a subselect to match the max timestamp. Is there a better or more efficient way to do this?

SELECT c.id, c.fromUserId, c.toUserId, m.userId, m.message, m.timestamp, pm.filename AS thumbnail, u.username
FROM conversations c, messages m, productmedia pm, users u
WHERE (c.fromUserId = '9' OR c.toUserId = '9')
AND c.id = m.conversationId
AND m.timestamp = (SELECT MAX(m.timestamp) FROM messages m WHERE m.conversationId = c.id)
AND c.productId = pm.productId
AND pm.sortOrder = '0'
AND m.userId = u.id
GROUP BY c.id
ORDER BY m.timestamp DESC

This SQL of yours has three issues I want to address before looking at the performance...
Formatting:
SELECT c.id,
       c.fromUserId,
       c.toUserId,
       m.userId,
       m.message,
       m.timestamp,
       pm.filename AS thumbnail,
       u.username
FROM conversations c,
     messages m,
     productmedia pm,
     users u
WHERE (c.fromUserId = '9' OR c.toUserId = '9')
  AND c.id = m.conversationId
  AND m.timestamp = (
           SELECT MAX(m.timestamp)
           FROM messages m
           WHERE m.conversationId = c.id)
  AND c.productId = pm.productId
  AND pm.sortOrder = '0'
  AND m.userId = u.id
GROUP BY c.id
ORDER BY m.timestamp DESC

I am not advocating the above as the right way to indent SQL, but, it is consistent, and it allows you to more easily see what is what in the query. What's nice is that you have consistently capitalized the keywords, etc. so that's good.
I am familiar with the above indenting/layout, so, I can now more easily see the next two issues....
Aliases:
You have the table messages twice in your query, once in the sub-select, and again in the main query. Both of these instances of the table have the alias m.... <sarcasm>this is not at all confusing... </sarcasm>
Group By:
Your group by clause is one of those things that will never be resolved to my satisfaction. MySQL has what I consider to be a bug.....(they call it a feature) ..... a massive, oh-my-god, how-could-they-do-that, what-were-they-thinking bug.
What does this mean practically? It means that your query makes no sense to anyone other than a MySQL expert. Your query makes no sense to me.... I can't help. I don't know what the expected behaviour is in your code. Your query does not even contain any aggregated values? Huh!
Next steps:

Figure out what you are grouping by (or even if the group-by is needed).
pull an explain-plan from the database when it runs the query.


Sorting with different Algorithms I'm new to Go, so I implemented a few sorting algorithms for practice. For example, I have an in-place insertion sort, and a bubble sort:

func bubbleSort(arr []int) {
   for i := 1; i < len(arr); i++ {
      if arr[i] < arr[i - 1] {
            tmp := arr[i - 1]
            arr[i - 1] = arr[i]
            arr[i] = tmp
            i = 0
      }
   }
}

func insertionSort(arr []int) {
   for i := 0; i < len(arr); i++ {
      for j := 0; j < i; j++ {
         if arr[j] > arr[i] {
           tmp := arr[j]
           arr[j] = arr[i]
           arr[i] = tmp
         }
      }
   }
}

However, when I went to implement merge sort, I found it most natural to use return values, because I couldn't seem to find a clean way to merge the results in place. Is there a good way to do this in Go, and would it even make sense to do so in-place? Or would it lead to difficulties when attempting to move to a concurrent implementation using goroutines? Code:

func merge(pt1 []int, pt2 []int) []int {
   totalLen := len(pt1) + len(pt2)
   arr := []int{}

   for i := 0; i < totalLen; i++ {
      // remove the smallest from the 2 slices and add it to the final
      if pt1[0] < pt2[0] {
         arr = append(arr, pt1[0])
         pt1 = pt1[1:]
      } else {
         arr = append(arr, pt2[0])
         pt2 = pt2[1:]
      }

      // break if a slice has been emptied
      if len(pt1) == 0 || len(pt2) == 0 {
         break
      }
   }

   arr = append(arr, pt1...)
   return append(arr, pt2...)
}

// merge sort algorithm
func mergeSort(arr []int) []int {
   arrLen := len(arr)

   if arrLen > 1 {
      pt1 := mergeSort(arr[arrLen/2:])
      pt2 := mergeSort(arr[:arrLen/2])
      arr = merge(pt1, pt2)
   }

   return arr
}

Any general style tips are also greatly appreciated (link to full code).

I'm not pretend to full review, but I guess better so than nothing.

Golang allow swapping in one-line, so you can just do so:

arr[i-1],arr[i] = arr[i],arr[i-1]
Go does not have optional parameters nor does it support method overloading.So if you want implement more "usually" version of this sort - provide utility function which will take arguments for range:

// merge sort algorithm
func merge_sort(arr []int, l, r int) {
    if l < r {
        m := (l + r) / 2
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
    }
}

func mergeSort(arr []int) {
    merge_sort(arr, 0, len(arr)-1)
}

In your current code very often used function append, it's not very effective. As example I just re-write C code from here and get:

func merge(arr []int, l, m, r int) {

    i := 0
    j := 0
    k := 0

    n1 := m - l + 1
    n2 := r - m
    L := make([]int, n1)
    R := make([]int, n2)
    for i < n1 {
        L[i] = arr[l+i]
        i++
    }
    for j < n2 {
        R[j] = arr[m+1+j]
        j++
    }

    i = 0
    j = 0
    k = l

    for i < n1 && j < n2 {
        if L[i] <= R[j] {
            arr[k] = L[i]
            i++
        } else {
            arr[k] = R[j]
            j++
        }
        k++
    }

    for i < n1 {
        arr[k] = L[i]
        i++
        k++
    }

    for j < n2 {
        arr[k] = R[j]
        j++
        k++
    }
}

About concurrent implementation - read this question and answers
and this one.


Naive implementation of Burst Balloon As part of learning Haskell, I'm solving few problems, usually solved imperatively.

I've come up with a naive solution for the problem described here, which is to find a sequence in which to burst a row of balloons that will earn the maximum number of coins. Each time balloon \$i\$ is burst, we earn \$C_{i-1} \cdot C_i \cdot C_{i+1}\$ coins, then balloons \$i-1\$ and \$i+1\$ become adjacent to each other.

I would like to get few comments on the naive implementation below before solving it using dynamic programming.

What I'm looking for is:

Correctness
Program structure
Idiomatic Haskell
Any other higher order functions that can be used
Other optimizations that can be done

import qualified Data.List as List (permutations)

burst :: [Int] -> (Int, [Int])
burst = burstNaive

burstNaive :: [Int] -> (Int, [Int])
burstNaive = foldl (\a@(aVal,_) e@(eVal,_) -> if eVal > aVal then e else a) (0, []) . allOrders

allOrders :: [Int] -> [(Int, [Int])]
allOrders []       = []
allOrders l@(x:xs) = map (\p -> (flip withOrder l p, p))$ List.permutations [0..length l - 1]

type IndexOrder = [Int]
withOrder :: IndexOrder -> [Int] -> Int
withOrder []     _  = 0
withOrder (i:is) xs = left * (xs !! i) * right + withOrder adjust xss
  where
    xss = remAt i
    adjust = map (\index -> if index > i then index - 1 else index) is
    left  = if i == 0 then 1 else xs !! (i-1)
    right = if i == (length xs - 1) then 1 else xs !! (i+1)
    remAt index = let (f,s) = splitAt index xs in f ++ drop 1 s

Sample Output:

Prelude> :l Balloon.hs
[1 of 1] Compiling Balloon          ( Balloon.hs, interpreted )
Ok, one module loaded.
*Balloon> burst [3,1,5,8]
(167,[1,2,0,3])
*Balloon>

First of all, it's great that you've used type signatures for all your functions. Also, all used functionality is hidden away in helpers, which is also a plus.

We can rewrite burstNative with  maximumBy and comparing:

import Data.List (maximumBy)
import Data.Ord (comparing)

burstNaive :: [Int] -> (Int, IndexOrder)
burstNaive [] = (0, [])
burstNaive xs = maximumBy (comparing fst) . allOrders $ xs

While it's possible to use ((0, []) . allOrders instead of the pattern matching, matching makes the base case more visible.

Also, this is a perfect spot to use IndexOrder instead of [Int].

In withOrder we traverse the list too often. Since lists are just forward linked lists in Haskell, we have to walk through the list four times, once for left, once for right, once for xs !! i and once for splitAt. That's a handful. So instead let's do that only once:

-- def: default value if list is too short/at end
moveAtStencil3 :: a -> Int -> [a] -> ((a,a,a), [a])
moveAtStencil3 def i xs
   | i < 1     = let (m:r:_) = xs in ((def, m, r), drop 1 xs)
   | otherwise = let (as,bs) = splitAt (i - 1) xs
                     (l:m:r) = take 3 (bs ++ repeat def)
                 in ((l,m,r), as ++ (l : r : drop 3 bs)

withOrder :: IndexOrder -> [Int] -> Int
withOrder []     _  = 0
withOrder (i:is) xs = left * middle * right + withOrder adjusted xss
  where
    ((left, middle, right), xss) = moveAtStencil3 1 i xs
    adjusted = map (\index -> if index > i then index - 1 else index) is

While we're at it, I renamed adjust to adjusted. Verbs (adjust) are usually functions, whereas adjusted is a list.

We could replace permutations in allOrders with recursion, but that wouldn't change much.


C string parser criticism I have written a program to parse a string depending on the string the user provides.
Any advise/criticism is appreciated.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define DEFAULT_SIZE 10
#define RESIZE_MULTI 2

/*compares value to see if it exists in parse. return 0 if exists*/
static uint8_t compare(const char value, const char *parse)
{
   size_t i;

   i = 0;
   while(*(parse + i) != '\0')
   {
      if(*(parse + i) == value)
         return 0;
      i++;
   }
   return 1;
}

/*string must be null terminated. the string that needs to be split*/
/*parse must be null terminated. contains value that the string will be split at*/
/*matrix contains all the string that was split based on parse. the function return how how many string there are*/
size_t parse_string(const char *string, const char *parse, char *** const user_matrix)
{
   /*how many spots there are*/
   size_t temp_matrix_size;
   /*how many acctually string there are*/
   size_t temp_matrix_length;
   char **temp_matrix;
   size_t i;
   size_t counter;

   /*allocate initial memory. array of pointers*/
   temp_matrix = malloc(sizeof(*temp_matrix) * DEFAULT_SIZE);
   if(temp_matrix == NULL)
      goto FAIL0;
   temp_matrix_size = DEFAULT_SIZE;
   /*since right now there 0 string aka pointers to strings*/
   temp_matrix_length = 0;

   i = counter = 0;
   while(*(string + i) != '\0')
   {
      /*resize array of pointers*/
      if(temp_matrix_length >= temp_matrix_size)
      {
         char **temp = realloc(temp_matrix, sizeof(*temp_matrix) * temp_matrix_size * RESIZE_MULTI);
         if(temp == NULL)
            goto FAIL0;
         temp_matrix = temp;
         temp_matrix_size = temp_matrix_size * RESIZE_MULTI;
      }

      if(compare(*(string + i), parse) == 0)
      {
         char *temp;
         if(counter > 0)
         {
            /*need the plus 1 for terminating char*/
            temp = malloc(sizeof(*temp) * (counter + 1));
            if(temp == NULL)
               goto FAIL0;

            /*setting terminating char*/
            *(temp + counter) = '\0';
            /*copy over the string before the parsing char*/
            memcpy(temp, string + (i - counter), counter);

            /*store the string*/
            *(temp_matrix + temp_matrix_length) = temp;
            temp_matrix_length++;
         }

         /*store only the parsing char with null terminated char*/
         temp = malloc(sizeof(*temp) * 2);
         if(temp == NULL)
            goto FAIL0;
         *(temp + 0) = *(string + i);
         *(temp + 1) = '\0';

         *(temp_matrix + temp_matrix_length) = temp;
         temp_matrix_length++;

         i++;
         counter = 0;
      }
      else
      {
         i++;
         counter++;
      }
   }

   /*special case*/
   if(counter != 0)
   {
      char *temp = malloc(sizeof(*temp) * (counter + 1));
      if(temp == NULL)
         goto FAIL0;

      /*setting terminating char*/
      *(temp + counter) = '\0';
      /*copy over the string before the parsing char*/
      memcpy(temp, string + (i - counter), counter);

      /*store the string*/
      *(temp_matrix + temp_matrix_length) = temp;
      temp_matrix_length++;
   }

   *user_matrix = temp_matrix;

   return temp_matrix_length;

   FAIL0:
   if(temp_matrix != NULL)
   {
      /*free all the strings*/
      for(i = 0; i < temp_matrix_length; i++)
      {
         free(*(temp_matrix + i));
      }
      /*free the array of pointers*/
      free(temp_matrix);
   }
   *user_matrix = NULL;
   return 0;
}

int main(void)
{
   char **matrix;
   size_t size;

   /*can have anything you want*/
   char *str = "Hello Word!!!";
   /*can have any char you want*/
   char *parse = "! ";

   size = parse_string(str, parse, &matrix);

   for(size_t i = 0; i < size; i++)
   {
      printf("%s\n", *(matrix + i));
   }

   for(size_t i = 0; i < size; i++)
   {
      free(*(matrix + i));
   }
   free(matrix);

   return 0;
}

Major remark of the code as whole: for some reason you write the unreadable version of array access *(arr+i) all over the place. Don't do that! This makes your code look needlessly obscure and hard to read. Instead use the much more readable arr[i].

Your compare is just a naive implementation of strchr. It would be much more efficient to use strchr.

Don't write while loops when you can write for loops, the latter is easier to read and often optimizes better too.

There is no point in const qualifying parameters passed by value - it only confuses the caller. Though this is a bit subjective and coding style.

The "correct naive" implementation of strchr would rather look like this:
  static const char* compare (char value, const char *parse)
  {
    for(size_t i=0; parse[i] != '\0'; i++)
    {
      if(parse[i] == value)
      {
        return &parse[i];
      }
    }
    return NULL;
  }

Since you don't use the above version but just return 1 or 0, you end up calling compare over and over on the same data, which is inefficient. If you had a version returning a pointer or index, you could continue searching from that location at next iteration, instead of starting over.

You can get rid of the "on error goto" pattern and leave all clean-up to a wrapper function. It's a bit more readable and you don't have to suffer the old "goto considered harmful" debate yet again:
  size_t parse_string (/* params */)  // wrapper function
  {
    // declare all resources potentially needing clean-up here:
    char **temp_matrix = NULL;
    ...

    bool ok;
    ok = actual_function (/* params */); // the algorithm, private static inline

    if(!ok)
    {
      if(temp_matrix != NULL)  // the clean-up code from your FAIL0 label here
      ...
    }
  }

Upon failure, "actual_function" just return false; and then the wrapper function can worry about clean-up.
(For more intricate scenarios like some opaque struct allocated by your lib, you can move the whole clean-up code into yet another public "destructor" function.)

Generally, more than 2 levels of indirection is bad practice, but your scenario here is one of the very few cases where three *** is actually motivated. However, char *** const means that the outer-most pointer is const-qualified, which is just weird. The caller doesn't care if you change that local variable internally or not, it just serves to confuse the user. Again, just drop const of parameters passed by value. In this case the char*** passed by value.

Don't name your variables with identifiers used by C++ keywords, functions, libraries etc. Like string. Even if you never intend to use the code with C++, many IDE use same code formatting and color coding for C and C++, like this site for example.


Name for mconcat implementation for applicative monoid I have implemented a function mcollect which is effectively mconcat only for applicative monoids:

mcollect
  :: Applicative f
  => Monoid (f a)
  => [a]
  -> f a
mcollect = mconcat . fmap pure

However I am not overly keen on the name mcollect, an alternative name in the spirit of mconcat is amconcat which I am not keen on either. Looking on Hoogle there does not appear to be anything like this in any libraries, that I can find. Does something like this exist somewhere already, I've just missed it? Is there a better name for this function?

I wouldn't give this a name. It is equal to foldMap pure and feels to me like it might be refactored away with more context.


Reorganizing a PHP array structure (arrays within arrays) I have this array within array which contains a lot of values:

  183 =>
    array (size=3)
      0 => string 'DE' (length=2)
      1 => string '2015-06-09' (length=10)
      2 => string 'GK' (length=2)
  184 =>
    array (size=3)
      0 => string 'DE' (length=2)
      1 => string '2015-06-08' (length=10)
      2 => string 'GL' (length=2)
  185 =>
    array (size=3)
      0 => string 'FR' (length=2)
      1 => string '2015-06-09' (length=10)
      2 => string 'GN' (length=2)
  186 =>
    array (size=3)
      0 => string 'FR' (length=2)
      1 => string '2015-09-08' (length=10)
      2 => string 'GO' (length=2)

0 is the country code. 1 is a date. 2 is a column on an Excel file.

I want to organize it in this way:

2015-06-09 =>
  array (size=3)
    DE =>
      array (size=2)
        column => GK
        download => 666
    FR =>
      array (size=2)
        column => GN
        download => 777

2015-06-08 =>
  array (size=3)
    DE =>
      array (size=2)
        column => GL
        download => 666
    FR =>
      array (size=2)
        column => GO
        download => 777

So the same date can show up more than once. if it gets to an array value with the same date - it inserts in it the country code with and its' column.

if it has more than 1 country - it adds a new country. (with the 'download' and column values).

I have this function:

function get_cols_to_array_by_date($array) {

    $mainarr = array();

    $last_in_arr = count($array);

    for ($i=0; $i<$last_in_arr; $i++){

            $mainarr[$array[$i][1]] = array( $array[$i][0]=> array('downloads'=> 666, 'col'=>$array[$i][2]) );

    }

    return $mainarr;

}

which outputs an array that runs over the country when it gets to the same date and doesn't give me an array of countries.

What part am I missing in my code?
Is there a simpler way to do it? ( PHP syntax shortcuts ;) )

Why

You're replacing the indexed item for the date when you declare a new array in the line:

$mainarr[$array[$i][1]] = array( $array[$i][0]=> array('downloads'=> 666, 'col'=>$array[$i][2]) );

See it as $array[$index] = array(...) -- running it again over the same index would replace the value at that index.

Quick Fix

You could simply replace that line with (considering that there'll not be more than one line for a given country, for the same date, as in: no two DE for 2015-06-08):

if (!isset($mainarr[$array[$i][1]])) { $mainarr[$array[$i][1]] = array(); }
$mainarr[$array[$i][1]][$array[$i][0]] = array('downloads'=> 666, 'col'=>$array[$i][2]);

Note that $array[$i][0] (aka the country) moved to the left site of =, and the outer array on the right side of it was removed.

How would I do

I refactored the code to be more legible and easier to understand, and also use better practices IMHO:

function get_cols_to_array_by_date($array) {
    // set the name of the variable to a more meaningful one
    $result = array();

    foreach ($array as $i => $data) {
        // shortcuts to prevent having to remember which index they are (you could change them for constants)
        $country = $data[0];
        $date = $data[1];
        $col = $data[2];

        $download = 123; // don't know where 'download' value comes from, put it here

        // you need to check if the date index already exists
        // if not, create the empty array for the date
        if (!isset($result[$date])) {
            $result[$date] = array();
        }

        // considering that country will NOT repeat for a given date
        $result[$date][$country] = array(
            'column' => $col,
            'download' => $download,
        );
    }

    return $result;
}