Sum of orders per customer ID So, I have two tables, customers and orders and I want to get all orders associated with a customer.

The tables look like this:

Customers

customer_no   order_no
       1027       V327
       1027       V391
       1028       V400
etc..

Orders

order_no article1 article2 size order_date quantity
    V327    Jeans    Black   36   20150101        2
    V327    Shirt     Blue    L   20150101        1
    V327    Shirt    White    L   20150101        2
    V391    Jeans      Red   34   20150202        3
    V400    Shirt    Green   32   20150226        2
etc..

Now, I currently use the following query, but it is dog slow and I just know I'm approaching this wrongly. I feel like it should be possible to solve this with a join somewhere, but for the life of mine, I just cannot figure this one out.

SELECT article1, article2, size, order_date, SUM(quantity)
FROM orders
WHERE order_no IN (
    SELECT order_no
    FROM customers
    WHERE customer_no = '1027'
)
GROUP BY article1, article2, size, order_date, SUM(quantity)

The output for customer 1027 is (and should be):

article1 article2 size order_date SUM(quantity)
   Jeans    Black   36   20150101             2
   Shirt     Blue    L   20150101             1
   Shirt    White    L   20150101             2
   Jeans      Red   34   20150202             3

Does anyone have a better way of solving this? Performance is my main issue here.

Applying a JOIN sounds pretty easy

SELECT article1, article2, size, order_date, SUM(quantity)
FROM orders
INNER JOIN customers ON orders.order_no = customers.order_no
WHERE customers.customer_no = '1027'
GROUP BY article1, article2, size, order_date, SUM(quantity)

You should note that nested SELECT statements in a WHERE clause almost always lead to bad performance.

Also that kind of unnormalized data model looks weird, but there may be good reasons why to keep order_no and customer_no pairs in a single association table. May be its just bad naming, something like customers_orders might probably have been a better choice.


Optimizing graph analysis I've implemented the Floyd Warshall algorithm in this problem.  However, as this is my first time in handling with adjacency list, I was not able to make it memory efficient.

I used a 1000*1000 and another list of 1000 size but I have seen solutions of people getting accepted with 100*100 size.  How can I make my graph array size less, or perhaps what is the best possible way to accept input in the adjacency list in graph?

P.S.: I tried using vector and map/pairs STL, but since I am not good in STL, I will be more than happy if a non STL solution is presented.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
int graph[1000][1000], m[1001], n;  //this is the array which I want to decrease
int main(){
    int u, v, flag=0, testCase = 1;
    while(scanf("%d%d", &u, &v), u||v){

        n = 0;
        memset(m, 0, sizeof(m));

        for(int i = 0; i < 1000; i++)
            for(int j=0; j<1000; j++)
            graph[i][j] = INF;

        if(!m[u])
        m[u] = ++n;

        if(!m[v])
        m[v] = ++n;

        graph[m[u]][m[v]] = 1;
        graph[m[u]][m[u]] = 0;
        graph[m[v]][m[v]] = 0;

        while(scanf("%d%d", &u, &v), u||v){
            if(!m[u])
            m[u] = ++n;

            if(!m[v])
            m[v] = ++n;

            graph[m[u]][m[v]] = 1;
            graph[m[u]][m[u]] = 0;
            graph[m[v]][m[v]] = 0;
        }

        for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;

        for(int i = 1; i <= n; i++)
        for(int j=1; j<=n; j++)
        s += graph[i][j];
        //cout<<s<<endl;
        s /= (double)n*(n-1);
        //cout<<s<<endl;
        printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
    }
    return 0;
    }

Running here

Problem statement linked above says 'Page numbers will always be in the range 1 to 100', I don't understand why you need to keep size = 1000, size = 101 should work just fine. Correct me if I am missing something here.

I modified your code here

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

#define INF 1e9
#define MAX_SIZE 100

int graph[MAX_SIZE + 1][MAX_SIZE + 1], n, mapping[MAX_SIZE + 1];
int main() {
    int u, v, flag=0, testCase = 1;
    while(scanf("%d%d", &u, &v), u||v){
        for(int i = 1; i <= MAX_SIZE; i++) {
            for(int j = 1; j <= MAX_SIZE; j++) {
                graph[i][j] = INF;
            }
            graph[i][i] = 0;
        }
        int n = 0;
        memset (mapping, 0, sizeof(mapping));
        do {
            if (!mapping[u])
                mapping[u] = ++n;
            if (!mapping[v])
                mapping[v] = ++n;
            graph[mapping[u]][mapping[v]] = 1;
        } while(scanf("%d%d", &u, &v), u||v);

        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

        double s = 0.0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                s += graph[i][j];
        //cout<<s<<endl;
        s /= (double)n*(n-1);
        //cout<<s<<endl;
        printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
    }
    return 0;
}


Review Insert/Update stored procedure I am not a DBA nor do I play one on TV.

My application is retrieving information from Facebook and storing it into our own database.  I want to retrieve the Location Post information of Id and AuthorId.  AuthorId is a foreign key to another table.  I was told by a DBA that foreign keys should always use internal unique identifiers because you can never rely on external unique identifiers.  So I created the following table structure...

CREATE TABLE tblAuthor
(
    [MyAuthorId] INT NOT NULL PRIMARY KEY IDENTITY
    [FacebookAuthorId] BIGINT NOT NULL
    ...Additional Facebook information...
)

CREATE TABLE tblLocationPost
(
    [MyLocationPostId] INT NOT NULL PRIMARY KEY IDENTITY,
    [FacebookLocationPostId] BIGINT NOT NULL,
    [MyAuthorId] INT NOT NULL,
    ...Additional Facebook information...
    CONSTRAINT [FK_tblLocationPost_Author] FOREIGN KEY (MyAuthorId) REFERENCES tblAuthor(MyAuthorId)
)

The data I get back from Facebook when querying Location Post is LocationPostId and AuthorId.  So I have created the following stored procedure to insert/update the LocationPost information in the database...

CREATE PROCEDURE [dbo].[LocationPost_Save]
@facebookLocationPostId bigint,
@facebookAuthorId bigint
AS
BEGIN
     DECLARE @myAuthorId INT
     DECLARE @IdentityColumn TABLE ( IdentityId int )

     BEGIN TRANSACTION

     /* Locate out internal unique id using facebooks unique author id, insert it if necessary */
     IF EXISTS (SELECT * FROM tblAuthor WHERE FacebookAuthorId = @facebookAuthorId)
     BEGIN
         SELECT @myAuthorId = MyAuthorId FROM tblAuthor WHERE FacebookAuthorId = @facebookAuthorId
     END
     ELSE
     BEGIN
         INSERT INTO tblAuthor (FacebookAuthorId) VALUES (@facebookAuthorId)
         SELECT @myAuthorId = SCOPE_IDENTITY()
     END

     /* Insert/Update one row in LocationPost */
     MERGE tblLocationPost lp
     USING (SELECT @facebookId as FacebookId) fb
     ON (lp.FacebookId = fb.FacebookId)
     WHEN MATCHED THEN
         UPDATE SET
             MyAuthorId = @myAuthorId,
             ...Additional data...
     WHEN NOT MATCHED THEN
         INSERT
             (FacebookLocationPostId, MyAuthorId, ...Additional Columns...)
         VALUES
             (@facebookLocationPostId, @myAuthorId, ...Additional Values...)
     OUTPUT INSERTED.MyLocationPostId INTO @IdentityColumn;

     COMMIT TRANSACTION

     /* Return the identify column of Inserted/Updated row */
     SELECT IdentityId FROM @IdentityColumn
END

Is this the correct pattern to use for this scenerio or is there a better approach?
Is the MERGE command the appropriate approach to Insert/Update a record (I am using SQL Server 2008)?
Do I really need to put my own Author Unique Id in the LocationPost table, or can I simplify this by putting the Facebook Unique Id?

I'd rather use the FacebookAuthorId and FacebookLocationPostId as primary keys, because your logic ensures them to be unique. In case of your current solution you would still require (unique) indexes on these fields (in order for lookups to be efficient) so there is no reason not to use them as primary keys.
Given suggest optimization you don't need to check/insert an author record   LocationPost_Save, just use the merge to insert/update the data in the table, and create a separate Author_Save SP that will do the same job for Authors.

Having said that, assuming that you are using one of the high-level languages :) and you're developing a long-living solution I would actually recommend you to use one of the ORMs available for your language to interact with the database. It'll take a bit longer at the beginning, but you'll get a more flexible solution in a long term.


Find all attributes for each HTML tag This code outputs each tag followed by its attributes in the given HTML, both in lexicographic order. It must be possible to keep the spirit of the code without these many nested cycles and conditionals.

from bs4 import BeautifulSoup

htmlist = ['
',
     '
Print/export
',
     '
',
     '
',
     '
Create a book
',
     '
<a href="/w/index.php?title=Special:Book&amp;bookcmd=render_article&amp;arttitle=Main+Page&amp;oldid=560327612',
     '
Printable version
',
     '
',
     '
',
     '
']

soup = BeautifulSoup("\n".join(htmlist), "html.parser")

tags = sorted(set([tag.name for tag in soup.find_all()]))

for tag in tags:
    tags_keys = list()
    for line in htmlist:
        aux=BeautifulSoup(line, "html.parser").find(tag)
        if aux:
            tags_keys.extend(list(aux.attrs))
    print(tag+":"+",".join(sorted(set(tags_keys))))

I tried something along the lines of what's below (in place of the outermost for), but couldn't even get it to work.

for tag in tags:
    print(tag+":"+",".join(sorted(soup.find(tag).attrs.keys())))

Edit: There was a typo in the code, htmlist was supposed to be as follows.

htmlist = ['
',\
           '
Print/export
',\
           '
',\
           '
',\
           '
Create a book
',\
           '
Download as PDF
',\
           '
Printable version
',\
           '
',\
           '
',\
           '
',\
          ]

Notice in @alecxe's answer how he flipped the loops:
instead of iterating over tags and then lines,
he's iterating over lines and then tags.
This performs much better,
because only one BeautifulSoup is created per line,
in contrast with your implementation
where an instance is created for every tag and line pair,
which is many more instances of BeautifulSoup,
and wasted processing.

One more improvement over that could be using just one instance of BeautifulSoup,
if you can join all the lines into a single document,
instead of processing line by line:

soup = BeautifulSoup("\n".join(htmlist), "html.parser")

tags = defaultdict(set)
for tag in soup():
    tags[tag.name] |= set(tag.attrs)

for tag_name in sorted(tags):
    print("{name}:{attrs}".format(name=tag_name, attrs=",".join(sorted(tags[tag_name]))))

However this is not possible with the given lines,
because this line is invalid HTML and will mess up the document:

 '
<a href="/w/index.php?title=Special:Book&amp;bookcmd=render_article&amp;arttitle=Main+Page&amp;oldid=560327612',

If possible, I suggest to fix this line, and use the above approach.

 '

',


Python for HPC: Parse file, generate statistics, record output I have a program which is designed to be highly parallelizable. I suspect that some processors are finishing this Python script sooner then other processors, which would explain behavior I observe upstream of this code. Is it possible that this code allows some mpi processes to finish sooner than others?

comm = MPI.COMM_WORLD
rank = comm.Get_rank()
nam ='lcoe.coe'
csize = 10000
with open(dacout) as f:
    for i,l in enumerate(f):
        pass
numlines = i
dakchunks = pd.read_csv(dacout,  skiprows=0, chunksize = csize, sep='there_are_no_seperators')
linespassed = 0
vals = {}
for dchunk in dakchunks:
    for line in dchunk.values:
        linespassed += 1
        if linespassed < 49 or linespassed > numlines - 50: continue
        else:
            split_line = ''.join(str(s) for s in line).split()
        if len(split_line)==2:
              if split_line[0] == 'nan' or split_line[0] == '-nan':
                  continue

              if split_line[1] != nam:
                  continue
              if split_line[1] not in vals:
                  try:
                      vals[split_line[1]] = [float(split_line[0])]
                  except NameError:
                      continue
              else:
                  vals[split_line[1]].append(float(split_line[0]))
# Calculate mean and x s.t. Percentile_x(coe_dat)<threshold_coe
self.coe_vals = sorted(vals[nam])
self.mean_coe = np.mean(self.coe_vals)
self.p90 = np.percentile(self.coe_vals, 90)
self.p95 = np.percentile(self.coe_vals, 95)

count_vals = 0.00
for i in self.coe_vals:
    count_vals += 1
    if i > coe_threshold:
        break
self.perc = 100 * (count_vals/len(self.coe_vals))
if rank==0:
    print>>logf, self.rp, self.rd, self.hh, self.mean_coe
    print self.rp, self.rd, self.hh, self.mean_coe, self.p90, self.perc

I have a program which is designed to be highly parallelizable.

I can't see this, all I can see is a broken module level program.

As for improvements in your code.
There are quite a few ways you can improve your for-loop to make vals:

Put it in a function,
Use a defaultdict, this should result in something like:

if split_line[1] != nam:
    continue
vals[split_line[1]].append(float(split_line[0]))

This should make you realise that you'll only ever add to vals[nam].
And so change it to just a list.
slice dchunk.values.

for line in dchunk.values[:49] + dchunk.values[numlines - 50:]:
    split_line = ''.join(str(s) for s in line).split()

Alternately if this doesn't work use a comprehension with enumerate.

for line in (l for i, l in enumerate(dchunk.values) if i < 49 or i > numlines - 50):
    split_line = ''.join(str(s) for s in line).split()

Merge all the if statements into one.

if (len(split_line) != 2 or
    split_line[0] in ('nan', '-nan') or
    split_line[1] != nam):
    continue

You should change some of your variables to 'constants' using the UPPER_SNAKE_CASE convention.

And you can change count_vals into a single line with len and itertools.takewhile.

count_vals = float(len(takewhile(lambda i: i > coe_threshold, coe_vals)))

You can change the way you get numlines to len(list(f)).


Caching mechanism for saving a bitmap I needed a quick caching mechanism to save a bitmap (picture). There was no way I could get the bitmap to the class where I need to upload it to the server so for the sake of organization and code cleanliness I created this. I have never seen this before implemented this way but to me this not only fits the purpose but seems to be a good way to do this. I am unsure and definitely want to find the best way to do this.

The image in this cache would be accessed roughly around 30 seconds to 2 minutes after it is stored, so I am not worried about it being garbage collected soon. That is why I used a soft reference but I needed it to stay for awhile just in case the user wanted to delay or lag a while before uploading the image. I understand it could return null if it was garbage-collected, which is an edge case for now.

public class ImageCacheUtils {

    private static SoftReference<Bitmap> imageReference;

    public static void cache(Bitmap bitmap) {
        imageReference = new SoftReference<Bitmap>(bitmap);
    }

    @Nullable
    public static Bitmap getImage() {
        return imageReference.get();
    }
}

There was no way I could get the bitmap to the class where I need to upload it to the server so for the sake of organization and code cleanliness I created this

This is pretty concerning to me as it implies that your object model and dependency graph might be a little wonky, but as that's likely a lot more complicated than the question immediately at hand, I'd like to make the same suggestion as Eric Stein: use an existing cache library. Guava would likely be a good place to start. It has crazy flexible cache capabilities.

Even if you don't use a preexisting cache, a proper caching class that gets instantiated and injected would ease testing concerns, make thread safety easier to reason about, loosen coupling, and just all around be better.

Here are the current (obvious) limitations you have:

What if you want to store more than 1 bitmap?
What if you want to have more than 1 cache?
Have you considered the thread safety aspect of this? References are atomic on the JVM, but I'm not actually sure if this is threadsafe in the sense of up to date observation. It's possible that a thread could get a coherent, but out of date read.
Unit testing this could get a bit nasty.

Luckily since the class is so simple, it wouldn't be too bad, but it would be strange that your tests for a consumer of this class would essentially have to rely on the implementation of ImageCacheUtils.
If you had concurrent unit tests, thread safety is once again a concern.

Given all this though, I think you've already mentioned your main limitation: you have no control at all over the life time of the object in your cache. You're basically subjected to the whims of the garbage collector, and to me, that would be a little scary. Getting null may be an almost unthinkable edge case now, but what happens when you change Java versions? What happens if you run it on a server that's running low on memory?

In short, the little cache-like-thing that you've made is a clean, simple enough implementation of what little it does, but I'm afraid that a proper cache might do a lot more than as appears on the surface.

Caching is crazy complicated, and if you continue down this path, you'll likely realize that this isn't sufficient for your true requirements (though I'm still skeptical that this is the most proper solution).


Count chars, words and lines Any suggestions are welcome.

package je3.io;

import java.io.*;
import java.nio.charset.Charset;

/**
 * Created by IDEA on 30/01/15.
 */
public class CountCharsWordsLines {
    public static long[] count(String filename) throws IOException {
        long[] counts = new long[3];
        try(InputStream in = new FileInputStream(filename);
            Reader reader = new InputStreamReader(in, Charset.forName("UTF-8"));
            Reader buffer = new BufferedReader(reader)
        ) {
            int c;
            String newLineChar = System.lineSeparator();
            while((c = reader.read()) != -1) {
                char character = (char) c;
                if(character == '\n') {
                    counts[2]++;
                    counts[1]++;
                    counts[0]++;
                } else if(Character.isWhitespace(character)) {
                    counts[1]++;
                    counts[0]++;
                } else {
                    counts[0]++;
                }
            }
        }
        return counts;
    }

    public static void main(String[] args) throws IOException {
        if(args.length != 1) {
            throw new IllegalArgumentException();
        }
        long[] counts = count(args[0]);
        System.out.printf("Chars: %d; Words: %d; Lines: %d;\n", counts[0], counts[1], counts[2]);
    }
}

Bug

The program doesn't count words correctly,
for example in "a     text   like this",
because it counts every whitespace character as a word,
without handling consecutive whitespace characters.

Reading character by character is inefficient

Reading a file character by character is not very efficient.
It would be better to use a buffered reader and process the file line by line.
Here's an example of doing that, which also solves the bug with word counting:

long[] counts = new long[3];
try(InputStream in = new FileInputStream(filename);
    BufferedReader reader = new BufferedReader(new InputStreamReader(in, Charset.forName("UTF-8")))
) {
    String line;
    while ((line = reader.readLine()) != null) {
        counts[2]++;
        counts[1] += line.split("\\s+").length;
        counts[0] += line.length() + 1;
    }
}
return counts;

This might still not be accurate,
and probably there are corner cases where it will not count words correctly,
but it's still more accurate than the original.

Encapsulation

The implementation doesn't encapsulate well the results.
It returns a long[],
which is not great because you have to remember the array indexes that correspond to characters, words, lines, which is error prone.
Even if you add constants like CHARS_INDEX = 0, WORDS_INDEX = 1 to eliminate magic numbers,
it will not solve the encapsulation problem:
users of the function will know too much about the internal implementation,
that it uses a long[] for storage.
It would be cleaner to create a dedicated CountResult class to encapsulate the results.

For example:

private static class CountResult {
    private final long chars;
    private final long words;
    private final long lines;

    private CountResult(long chars, long words, long lines) {
        this.chars = chars;
        this.words = words;
        this.lines = lines;
    }
}

And then use it like this:

long chars = 0;
long words = 0;
long lines = 0;
while ((line = reader.readLine()) != null) {
    lines++;
    words += line.split("\\s+").length;
    chars += line.length() + 1;
}
return new CountResult(chars, words, lines);

Callers will not need to remember indexes,
the counts will be accessible intuitively by names.

Unused variables

You have some unused variables:

Reader buffer = new BufferedReader(reader)

String newLineChar = System.lineSeparator();

It would be better to remove them.


Extracting necessary records from LinkedIn I wanted to create a scraper in python which can fetch required data from LinkedIn. I tried with python in many different ways but I could not make it until I used selenium in combination with. However, I have created it and got it working as I wanted.

The most difficult part I had to face while making this crawler is that there are hundreds of profile pages which can be located with mostly three different XPath patterns. I somehow managed to cement the three different XPath patterns into one. Now it is working great.

This scraper firstly clicks on the view all recommendation tab in home page then parse 200 profiles [customized in this case] by going to the main page of each profile. I've tried to make it error-free. Here is what I've done:

from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.wait import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC

def producing_links(driver, wait):

    driver.get('https://www.linkedin.com/')

    driver.find_element_by_xpath('//*[@id="login-email"]').send_keys('someusername')
    driver.find_element_by_xpath('//*[@id="login-password"]').send_keys('somepassword')
    driver.find_element_by_xpath('//*[@id="login-submit"]').click()

    wait.until(EC.visibility_of_element_located((By.XPATH, "//a[contains(@class,'feed-s-follows-module__view-all')]")))
    driver.find_element_by_xpath("//a[contains(@class,'feed-s-follows-module__view-all')]").click()

    while True:
        driver.execute_script("window.scrollTo(0, document.body.scrollHeight);")

        wait.until(EC.visibility_of_element_located((By.XPATH, "//a[contains(@class,'feed-s-follow-recommendation-card__profile-link')]")))
        links = [item.get_attribute("href") for item in driver.find_elements_by_xpath("//a[contains(@class,'feed-s-follow-recommendation-card__profile-link')]")]
        if (len(links) == 200):
            break

    for link in links:
        get_docs(driver, wait, link)

def get_docs(driver, wait, name_link):

    driver.get(name_link)
    try:
        for item in driver.find_elements_by_xpath("//div[contains(@class,'pv-top-card-section__information') or contains(@class,'org-top-card-module__details') or (@class='org-top-card-module__main-column')]"):
            name = item.find_element_by_xpath(".//h1[@title]|.//h1[contains(@class,'pv-top-card-section__name')]").text
            title = item.find_element_by_xpath(".//span[contains(@class,'company-industries')]|.//h2[contains(@class,'pv-top-card-section__headline')]").text
    except Exception as e:
        print(e)

    finally:
        try:
            print(name, title)
        except Exception as ex:
            print(ex)

if __name__ == '__main__':

    driver = webdriver.Chrome()
    wait = WebDriverWait(driver, 10)

    try:
        producing_links(driver, wait)
    finally:
        driver.quit()

I would recommend a more modular design - having a LinkedInScraper class, initialized with a login and password and with separate methods for logging in and getting profile links.

Also, I think you are overusing the XPaths overall - whenever possible, first explore if you can use "by id", "by name" or "by css selector" locators and fall back to XPath only if you cannot get to the element with other locators.

Also note that wait.until combined with built-in expected conditions returns a WebElement instance - if you are waiting for a specific element and then clicking it - you can do it in one go without re-finding the element.

Unfortunately, cannot test the below code (for some reason, I don't see the recommendation link on the main page when logging in with my credentials), but hope this is still useful:

from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.wait import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC

class LinkedInScraper:
    def __init__(self, username, password):
        self.driver = webdriver.Chrome()
        self.wait = WebDriverWait(self.driver, 10)

        self.login(username, password)

    def __del__(self):
        self.driver.close()

    def login(self, username, password):
        self.driver.get('https://www.linkedin.com/')

        self.driver.find_element_by_id('login-email').send_keys(username)
        self.driver.find_element_by_id('login-password').send_keys(password)
        self.driver.find_element_by_id('login-submit').click()

    def links(self):
        follow_link = self.wait.until(EC.visibility_of_element_located((By.CSS_SELECTOR, "a.feed-s-follows-module__view-all")))
        follow_link.click()

        while True:
            self.driver.execute_script("window.scrollTo(0, document.body.scrollHeight);")

            self.wait.until(EC.visibility_of_element_located((By.CSS_SELECTOR, "a.feed-s-follow-recommendation-card__profile-link")))

            links = [item.get_attribute("href") for item in self.driver.find_elements_by_css_selector("a.feed-s-follow-recommendation-card__profile-link")]
            if len(links) == 200:
                break

        return links

    def profiles(self):
        for link in self.links():
            yield from self.profile(link)

    def profile(self, profile_link):
        self.driver.get(profile_link)

        for item in self.driver.find_elements_by_xpath("//div[contains(@class,'pv-top-card-section__information') or contains(@class,'org-top-card-module__details') or (@class='org-top-card-module__main-column')]"):
            name = item.find_element_by_xpath(".//h1[@title]|.//h1[contains(@class,'pv-top-card-section__name')]").text
            title = item.find_element_by_xpath(".//span[contains(@class,'company-industries')]|.//h2[contains(@class,'pv-top-card-section__headline')]").text

            yield (name, title)

if __name__ == '__main__':
    scraper = LinkedInScraper(username='username',
                              password='password')
    for profile in scraper.profiles():
        print(profile)

I am pretty sure we can also refactor the profile() method, but I cannot get to that page in order to see if locators can be simplified.


IniReader template overrides become ambiguous I was tasked with refactoring our existing IniReader class, which is Windows only compatible, to be cross-platform ( specifically UNIX compatible ). We decided that boost::property_tree was a good fit for this and a quick play with property_tree confirms this.

The original class had many readValue overloads for the various data types. During the refactoring I was happy to discover that boost::property_tree::get_value is templatized so it made it simple to declare the following new readValue functions:

// read and return a value from the inifile
// throws boost::property_tree:ptree_error if not found
template <class T>
T readValue( const std::string& section, const std::string& param ) const;

// read and return value from section.param in the inifile
// if the param does not exists in the section return |defaultValue|
template <class T>
T readValue( const std::string& section, const std::string& param, const T& defaultValue ) const;

However, I later discover there's a couple of special overridden readValue functions which accept an additional int index. This allows values to be read using param name appended with the index value like this:

[TextFileFilters]
count=3
filter1=*.txt
filter2=*.csv
filter3=*.log
num1=50
num2=20
num3=10

Originally I thought of adding two more readValue overrides which includes the index argument:

// read and return a value from the inifile
// throws boost::property_tree:ptree_error if not found
template <class T>
T readValue( const std::string& section, const std::string& param, const int index ) const;

// read and return value from section.param in the inifile
// if the param does not exists in the section return |defaultValue|
template <class T>
T readValue( const std::string& section, const std::string& param, const T& defaultValue, const int index ) const;

BUT, there's a problem. When using T = int it becomes ambiguous to the compiler:

// is 3 the default int value OR the index ?
int count = ini.readValue<int>( "TextFileFilters", "num", 3 );

What I've done, currently, is to remove the 3 parameter "indexed" override of readValue. Therefore mandating that all indexed readValue calls must be called with the default argument. This is not ideal.

The only thoughts around this I have was to introduce an new IniPath class, which attempts to replace the section, param or section, param, index combinations:

class IniPath
{
public:
  IniPath( const std::string& section, const std::string& path );
  IniPath( const std::string& section, const std::string& path, const int index );
};

...

template <class T>
T readValue( const IniPath& path ) const;

template <class T>
T readValue( const IniPath& path, T& defaultValue ) const;

but does that seems excessive? Too many temporaries?

int count = ini.readValue<int>( IniPath( "TextFileFilters", "count" ) );
int log_num = ini.readValue<int>( IniPath( "TextFileFilters", "num", 3 ) );

Do you have any suggestions or ideas?

I wouldn't worry too much about temporaries (shouldn't they be optimized away?), but I think you're focusing on the smaller problem. You fundamentally have the following options:

Disambiguate by disallowing certain combinations, like you say you've currently done (readValue<T>(string, string), readValue<T>(string, string, T), and readValue<T>(string, string, int, T) but no readValue<T>(string, string, int))
Disambiguate by changing parameters to the function (this could be by reordering non-template parameters e.g. readValue<T>(string, string, T) vs readValue<T>(string, int, string, T), or by the readValue<T>(IniPath, T) approach you describe where you make it someone else's problem)
Disambiguate by changing function names, e.g. readValue<T>(string, string, T) vs. readIndexedValue<T>(string, string, int) (and of course readIndexedValue<T>(string, string, int, T))
Disambiguate by changing function names the other way, e.g. readValue<T>(string, string) and readValue<T>(string, string, int) vs readValueDefault<T>(string, string, T) and readValueDefault<T>(string, string, int, T).

My opinion is that the first is too likely to create a pit of failure. Just like when you tried to add a non-defaulted readValue<T>(string, string, int) without immediately realizing the problem of doing so, users of your functions are likely to make the same mistake on the consumption side (hey, I've got readValue(sFoo, sBar) but now I need sBar 1, 2, and 3...) and wonder why things are compiling but not working correctly.

The second is okay; making it someone else's problem is a really good approach for some scenarios. Merely reordering the parameters like I mentioned can result in funky APIs like the deprecated parts of CRegKey::QueryValue where the order of parameters results in wildly different overloads that make the API hard to remember. I don't know whether this one is that bad, but I'm still predisposed against it.

The third is my favorite. It's simple, clean, and makes it easier to figure out what this extra int parameter is. The fourth is about as good, depending on whether indexes or defaults are more "natural", and of course you can combine both bullet's approaches.

But that's not the end of the story.

The bigger problem is this: You're migrating from existing usage with working code. You have to consider what the damage is, how to detect it, and how to fix it. Ideal case is things magically work 100%. Next best, in my opinion, is each call site either works the same as it used to or results in a compile-time error. Worse is a series of call sites you have to update, will find a pattern to do so, but sometimes the pattern is wrong (a change to IniPath might result in this). Worst by a long shot is call sites that change their meaning without any warning (you might be stuck here anyway if your call sites are ambiguous enough).

So do you have any call sites that will change meaning, and if so how will you address this? That will help determine how you disambiguate your function.


Integer to Roman Numeral converter I have implemented an Integer to Roman Numeral converter that converts any number in the range \$[1 \le x \le4999]\$ to its Roman number equivalent. Any comments on improving my code style or organization?

#include <string>
#include <iostream>

class Solution{
public:
    Solution () : IntVal {1,5,10,50,100,500,1000} , roman {'I', 'V' , 'X', 'L' ,'C', 'D' ,'M'} {}
    std::string intToRoman(int num);
private:
    int IntVal[7];
    char roman[7];
    int fslt(int num);
    std::string output;
    void helper(int num);
    void postProcess();
    void str_replace( std::string &s, const std::string &search, const std::string &replace);
};

#include "roman.hpp"

int Solution::fslt(int num){
    if (num>=50){
        if (num<100) return 3;
        else if (num>=100 && num < 500) return 4;
        else if (num>=500 && num < 1000) return 5;
        else return 6;
    }
    else{ // num < 50
        if (num>=10) return 2;
        else if (num>=5) return 1;
        else return 0;
    }
}

void Solution::helper (int num){
    int div = fslt(num);

    if (div == 0){
        for (int i = 0; i <num ;i++){
            output += roman[div];
        }
         return;
    }
    else {
        int rn = fslt(num);
        int numTimes = num/IntVal[rn];
        for (int i=0;i < numTimes; i++){
            output += roman[rn];
        }
        helper(num-numTimes*IntVal[rn]);
    }
}

void Solution::postProcess(){
    str_replace(output, "DCCCC", "CM");
    str_replace(output, "CCCC", "CD");
    str_replace(output, "LXXXX", "XC");
    str_replace(output, "XXXX", "XL");

    str_replace(output, "VIIII", "IX");
    str_replace(output, "IIII", "IV");
}

std::string Solution::intToRoman(int num){
    Solution::helper(num);
    Solution::postProcess();
    return output;
}

void Solution::str_replace( std::string &s, const std::string &search, const std::string &replace)
{
     for( size_t pos = 0; ; pos += replace.length() )
    {
         pos = s.find( search, pos );
         if( pos == std::string::npos ) break;

         s.erase( pos, search.length() );
         s.insert( pos, replace );
     }
}

int main(){
    Solution mySol;
    std::cout <<  mySol.intToRoman(4999) << std::endl;
    return 0;

}

Helper function too complex
Your helper function and the fslt function seem too complex for what they do (helper is even recursive!).  All you are really doing is adding roman numerals starting at the highest value first.  So something like this would suffice:
#define DIM(arr)        (sizeof(arr)/sizeof(arr[0]))

void Solution::helper (int num){
    for (int i = DIM(IntVal)-1; i >= 0; i--) {
        while (num >= IntVal[i]) {
            output += roman[i];
            num -= IntVal[i];
        }
    }
}


Date and time incrementation, using a fictional calendar / clock I created a simple clock & calendar system using a fictional system: everything from the number of seconds in a minute, down to the number of months in a year could be different from our accepted norms (i.e. the Gregorian Calendar). (For the purposes of testing the system I have declared that there are 2 seconds in a minute and the calendar uses Elder Scrolls naming for months and days of the week.)

Eventually I'd like to incorporate this into a game, so the function setInterval that currently increments the seconds is a simple stand-in for a more sophisticated kind of game loop.

The full code (with visual output) can be found at this JSFiddle.

I'm particularly interested in feedback on this method, which handles the incrementation of time:

function incrementOneSecond() {
  secondIndex++;
  currentSecond = secondIndex;
  if (secondIndex > secondsPerMinute) {
    secondIndex = 0;
    minuteIndex++;
    currentMinute = twoDigitFormat(minuteIndex);
    if(minuteIndex > minutesPerHour) {
        minuteIndex = 0;
      hourIndex++;
      currentHour = twoDigitFormat(hourIndex);
      if (hourIndex > hoursPerDay) {
        hourIndex = 0;
        dayIndex++;
            currentDay = weekdays[dayIndex];
        if (dayIndex >= weekdays.length) {
            dayIndex = 0;
          dateNumberIndex++;
          currentDateNumber = dateNumberIndex;
          if (dateNumberIndex > monthMaxDays) {
                    dateNumberIndex = 1;
            monthIndex++;
            currentMonth = months[monthIndex];
            if (monthIndex >= months.length) {
                        monthIndex = 0;
              yearIndex++;
              currentYear = yearIndex;
            }
            }
        }
      }
    }
  }

  updateTime(currentMinute, currentHour, currentDay, currentMonth, currentDateNumber, currentYear);
}

There's a lot of repetition, so it feels like I should be able to DRY it up, but because each if statement differs slightly, I haven't been able to come up with a way of rewriting the method in a way that is more efficient but also still readable.

Other methods used:

function twoDigitFormat(input) {
    formatted = ("0" + input).slice(-2)
    return formatted;
}

function updateTime(currentMinute, currentHour, currentDay, currentMonth, currentDateNumber, currentYear) {
    timeDisplay.innerHTML = currentHour + ':' + currentMinute;
    dateDisplay.innerHTML = currentDay + '<br/>' + currentMonth + ' ' + currentDateNumber + ', ' + currentYear;
}

Feedback

The code seems to work okay, though it appears that the counting is off because of the comparison operators used (i.e. >) and the initial value of the indexes (e.g. secondIndex = 0). Use Greater than Or equal to (i.e. >=) in order to accurately count with the correct number of seconds per minute, minutes per hour, etc.

Your code doesn't display the value of currentSecond but I added it (see code snippet below) and noticed it was going between values of 1, 2 and 3.

Suggestions

Pre-increment instead of post-increment and use immediately after

Instead of incrementing each value using the post-increment operator and then using it, use the pre-increment operator.

So lines like this:

secondIndex++;
currentSecond = secondIndex;

Can be converted to a single line like this:

currentSecond = ++secondIndex;

Parameter passing

function incrementOneSecond() references all variables defined with scope outside of it (e.g. currentSecond, currentMinute, etc.), so why pass those to updateTime()? For consistency, either pass them all to incrementOneSecond() when calling it, or just reference them the same way within updateTime().

var dateDisplay = document.getElementById('dateDisplay');
var btnNext = document.getElementById('next');

var weekdays = [
  'Morndas',
  'Tirdas',
  'Middas',
  'Turdas',
  'Fredas',
  'Loredas',
  'Sundas'
];
var months = [
  'Morning Star',
  'Sun\'s Dawn',
  'First Seed',
  'Rain\'s Hand',
  'Second Seed',
  'Midyear',
  'Sun\'s Height',
  'Last Seed',
  'Hearthfire',
  'Frostfall',
  'Sun\'s Dusk',
  'Evening Star'
];
var monthMaxDays = 30;
var yearStart = 1888;
var secondsPerMinute = 2;
var minutesPerHour = 30;
var hoursPerDay = 24;

var currentSecond = currentSecond || 0;
var currentMinute = currentMinute || twoDigitFormat(0);
var currentHour = currentHour || twoDigitFormat(0);
var currentDay = currentDay || weekdays[0];
var currentDateNumber = currentDateNumber || 1;
var currentMonth = currentMonth || months[0];
var currentYear = currentYear || yearStart;

var secondIndex = currentSecond;
var minuteIndex = currentMinute;
var hourIndex = currentHour;
var dayIndex = parseInt(weekdays.indexOf(currentDay), 10);
var dateNumberIndex = currentDateNumber;
var monthIndex = parseInt(months.indexOf(currentMonth), 10);
var yearIndex = currentYear;

var secondLoop = setInterval(incrementOneSecond, 500);

function twoDigitFormat(input) {
  return ("0" + input).slice(-2)
}

function incrementOneSecond() {
  currentSecond = ++secondIndex;
  if (secondIndex >= secondsPerMinute) {
    secondIndex = 0;
    currentMinute = twoDigitFormat(++minuteIndex);
    if (minuteIndex >= minutesPerHour) {
      minuteIndex = 0;
      currentHour = twoDigitFormat(++hourIndex);
      if (hourIndex >= hoursPerDay) {
        hourIndex = 0;
        currentDay = weekdays[++dayIndex];
        if (dayIndex >= weekdays.length) {
          dayIndex = 0;
          currentDateNumber = ++dateNumberIndex;
          if (dateNumberIndex > monthMaxDays) {
            dateNumberIndex = 1;
            currentMonth = months[++monthIndex];
            if (monthIndex >= months.length) {
              monthIndex = 0;
              currentYear = ++yearIndex;
            }
          }
        }
      }
    }
  }

  updateTime();
}

function updateTime() {
  timeDisplay.innerHTML = currentHour + ':' + currentMinute + ':' + currentSecond;
  dateDisplay.innerHTML = currentDay + '
' + currentMonth + ' ' + currentDateNumber + ', ' + currentYear;
}
html,
body {
  font-family: sans-serif;
  font-size: 1rem;
  line-height: 1.2rem;
}


Get all followers and friends of a Twitter user I'm trying to find my bug or any potential bottleneck that cause my program to be really slow. The script is to get all the followers and friends and save that in MongoDB.

import pymongo
import tweepy

consumer_key = ''
consumer_secret = ''
access_token = ''
access_token_secret = ''

from pymongo import MongoClient
client = MongoClient()

auth = tweepy.OAuthHandler(consumer_key, consumer_secret)
auth.set_access_token(access_token, access_token_secret)
api = tweepy.API(auth, wait_on_rate_limit=True, wait_on_rate_limit_notify=True, retry_count=3, retry_delay=60)

db = client.tweets

raw_tweets = db.raw_tweets
users = db.users

def is_user_in_db(user_id):
    return get_user_from_db(user_id) != None

def get_user_from_db(user_id):
    return users.find_one({'user.id' : user_id})

def get_user_from_twitter(user_id):
    return api.get_user(user_id)

def get_followers(user_id):
    users = []
    page_count = 0
    for user in tweepy.Cursor(api.followers, id=user_id, count=200).pages():
        page_count += 1
        print 'Getting page {} for followers'.format(page_count)
        users.extend(user)
    return users

def get_friends(user_id):
    users = []
    page_count = 0
    for user in tweepy.Cursor(api.friends, id=user_id, count=200).pages():
        page_count += 1
        print 'Getting page {} for friends'.format(page_count)
        users.extend(user)
    return users

def get_followers_ids(user_id):
    ids = []
    page_count = 0
    for page in tweepy.Cursor(api.followers_ids, id=user_id, count=5000).pages():
        page_count += 1
        print 'Getting page {} for followers ids'.format(page_count)
        ids.extend(page)

    return ids

def get_friends_ids(user_id):
    ids = []
    page_count = 0
    for page in tweepy.Cursor(api.friends_ids, id=user_id, count=5000).pages():
        page_count += 1
        print 'Getting page {} for friends ids'.format(page_count)
        ids.extend(page)
    return ids

def process_user(user):
    user_id = user['id']
    screen_name = user['screen_name']
    print 'Processing user : {}'.format(user['screen_name'])

    the_user = get_user_from_db(user_id)
    if the_user is None:
        follower_ids = get_followers_ids(user['screen_name'])
        friend_ids = get_friends_ids(user['screen_name'])

        user['followers_ids'] = follower_ids
        user['friends_ids'] = friend_ids

        users_to_add = []
        for follower in get_followers(screen_name):
            if not is_user_in_db(follower.id):
                users_to_add.append(follower._json)

        for friend in get_friends(screen_name):
            if not is_user_in_db(friend.id):
                users_to_add.append(friend._json)

        users.insert_many(users_to_add)
        users.insert_one(doc['user'])

if __name__ == "__main__":

    for doc in raw_tweets.find({'processed' : {'$exists': False}}):
        print 'Start processing'
        if 'user' in doc:
            process_user(doc['user'])

        if 'retweeted_status' in doc:
            process_user(doc['retweeted_status']['user'])

        raw_tweets.update_one({'_id': doc['_id']}, {'$set':{'processed':True}})

You should use is to compare to None, as that's faster.

def is_user_in_db(user_id):
    return get_user_from_db(user_id) is None

You can also use list concatenation rather than list.extend as it's slightly faster and there's no benefit to extend in this context. I also second the recommendation to use enumerate rather than having a manually incremented number in a for loop.

def get_followers(user_id):
    users = []
    page_count = 0
    for i, user in enumerate(tweepy.Cursor(api.followers, id=user_id, count=200).pages()):
        print 'Getting page {} for followers'.format(i)
        users += user
    return users

When you have a local variable here, use it instead of a dictionary call. It's quicker to access than a key.

screen_name = user['screen_name']
print 'Processing user : {}'.format(screen_name)

You can also collapse these lines by assing the results of the function calls directly.

    user['followers_ids'] = get_followers_ids(screen_name)
    user['friends_ids'] = get_friends_ids(screen_name)

You can make a list comprehension out of users_to_add, it's a single line of code that more efficiently creates a list based on a for loop-like construct. So this:

    users_to_add = []
    for follower in get_followers(screen_name):
        if not is_user_in_db(follower.id):
            users_to_add.append(follower._json)

    for friend in get_friends(screen_name):
        if not is_user_in_db(friend.id):
            users_to_add.append(friend._json)

Can be turned into this:

    users_to_add = [follower._json for follower in
            get_followers(screen_name) if not is_user_in_db(follower.id)]
    users_to_add += [friend._json for friend in
            get_friends(screen_name) if not is_user_in_db(friend.id)]

Also, it's more efficient to call dictionary keys, assuming they're there and handle the exception if they're not, like so:

try:
    process_user(doc['user'])
except KeyError:
    pass

try:
    process_user(doc['retweeted_status']['user'])
except KeyError:
    pass

You could replace pass with something else if you'd like, but this is more efficient as the if statement in your script would check the dictionary to see if a key exists, and then check it again to get the actual value attached to the key. The try except way only checks once, and moves on if it gets nothing.

One final note, you'd be surprised how expensive frequent print calls are. You have ones running in loops. I don't know how often the loops run, but if you are experiencing sluggishness, try removing them to see what difference it makes. Feedback is obviously important, but speed is also important.


Adding a course to one of 8 periods I have this rather ghastly if statement and I'm sure there is a way to condense it, but I don't really know how.  I was told a case statement would work but I've never used a case statement and I'm not sure.

public void add(int p, Course c)
{
    if (p == 1){
    if (course1.isFree() == true) {
        course1 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 2){
        if (course2.isFree() == true) {
        course2 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 3){
        if (course3.isFree() == true) {
        course3 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 4){
        if (course4.isFree() == true) {
        course4 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 5){
        if (course5.isFree() == true) {
        course5 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 6){
        if (course6.isFree() == true) {
        course6 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 7){
        if (course7.isFree() == true) {
        course7 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    } else if (p == 8){
        if (course8.isFree() == true) {
        course8 = c;
        System.out.println("Course " + c + "added to period " + p +".\n");
    } else {
        System.out.println("Unable to add class to a nonfree period.");
    }
    }

    totalcredits();
}

if (course3.isFree() == true) {
    course3 = c;
    System.out.println("Course " + c + "added to period " + p +".\n");
} else {
    System.out.println("Unable to add class to a nonfree period.");
}

...

} else if (p == 8){
    if (course8.isFree() == true) {
    course8 = c;
    System.out.println("Course " + c + "added to period " + p +".\n");
} else {
    System.out.println("Unable to add class to a nonfree period.");
}

Good thing there aren't 20.. 200... 2,000... 20,000 courses!
This code needs to DRY a bit. Don't repeat yourself.™
Programming is about abstractions - this code need one here, badly: there should be a concept of a bunch of courses in your program.
Then it would be possible to only write the block once. Given courses is an array of courses Course... of course:
public void add(int period, Course course) {
|
|---if (courses[period].isFree()) {
|   |
|   |---courses[period] = course;
|   |---System.out.println("Course " + course + "added to period " + period +".\n");
|   |
|---} else {
|   |
|   |---System.out.println("Unable to add class to a nonfree period.");
|---}
|
}

Notice the position of the scope-closing braces: by lining them up with the indentation of the line that opened the scope, you make the code much easier to follow, and avoid this:

    }
    }

Also notice the names I've used. Avoid single-letter identifiers, like p and c. Code is much easier to read when it's... readable.

This is too verbose:

if (course.isFree() == true) {

Since course.isFree() obviously returns a Boolean value, the Boolean value itself can serve as the expression of the condition, which means you don't need to compare it to true:
if (course.isFree()) {


Implementation in js to find if N can be written as X ^Y , N<100 From past year ,i have been mainly working on Js, and so have started implementing Algo Questions in js .can it be implemented in a better way.

/**
* Implementaion to find if a number can be expressed as x^y
* x is assumed to be >=0
*/

var canBeExpressedAsXraisedToY = function (n) {
if (n == 0 && n == 1) {
    console.log("Supplied 0 or 1");
    return true;
}
else if (n > 1) {
    var x = 2, prod = 1,y = 1;
    while (prod < n) {

        while (prod < n ) {

            prod = Math.pow(x,y);
            console.log('prod:',prod,'y:', y ,'x:',x)
            if (prod == n) {
                console.log('it can be expressed as x:', x, 'in terms of:', y);
                return true;
                break;
            }
          y++;
        }
        x++;
    }

    console.log("the number cannot be expressed as x ^ y ");
    return false;
}
else { // to handle negative cases .
    console.log('the number given is not supported ');
    return false;
}
}

console.log(canBeExpressedAsXraisedToY(4));
console.log(canBeExpressedAsXraisedToY(67));
console.log(canBeExpressedAsXraisedToY(64));

The algorithm is wrong. canBeExpressedAsXraisedToY(81) returns false.

Of course any n can have a trivial solution x=n and y=1.  I assume you want to require y>1. But you didn't state that anywhere, and in fact initialize y=1 in your code.

Initializing prod=1 is sloppy programming. You should structure the loops to compute prod before testing it.

That is pretty much a brute-force exhaustive search. For large n, a much better strategy would be to analyze the prime factors of n instead.


Shortest Path (BFS) through a maze Background

I have decided to use this year's Advent Of Code to learn Haskell. I feel like I vaguely understand the language and can solve most of the problems with relative ease. However, the code I produce is not the most readable and possibly has inefficiencies. Any suggestions on how to improve readability and performance would be much appreciated.

Problem

The problem is Day 13 of AoC. It consists of a maze where each cell (x,y) is either a wall or an empty space, dictated by the population count of the following equation:

x*x + 3*x + 2*x*y + y + y*y + key (where key is some arbitrary integer)

The cell is a wall if the population count is odd. The problem then comes in two parts:

Find shortest distance between (1,1) and (31,39).
Find number of cells that can be visited in 50 or less steps (from (1,1)).

Code

The code uses BFS for both parts. I am aware that A* may quicker for Part1.

import Data.Bits (popCount)
import qualified Data.Map as Map
import Debug.Trace

-- Define all types
type Index = (Int, Int)                         -- (x,y)
type Edges = [Index]                            -- list of connecting edges
type Prob  = (Int, Int, Int)                    -- (key, width, height)
type State = (Index, Int, Map.Map Index Bool)   -- (current, steps, visited)

-- Determine if a specific cell index represents a wall
isWall :: Int -> Index -> Bool
isWall key (x,y) = odd $ popCount num
    where num = x*x+3*x+2*x*y+y+y*y+key

-- Generate all edges of a specific cell
mkEdges :: Int -> Index -> Edges
mkEdges key (x,y) = filter (not.isWall key) adjs
    where adjs = wB [(x, y-1), (x+1, y), (x,y+1), (x-1,y)]
          wB   = filter (\(a,b) -> not (a<0 || b<0))

-- Find the shortest path length
bfsPathLength :: Int -> Index -> [State] -> Int
bfsPathLength key goal t@((curr, steps, visited):rest)  | goal==curr = steps
                                                        | otherwise  = bfsPathLength key goal newStates
    where newStates         = (filter (not.isQueued) $ filter (not.isVisited) $ map mkStates $ mkEdges key curr) ++ rest
          mkStates s        = (s, steps+1, Map.insert curr True visited)
          isVisited (s,_,_) = Map.member s visited
          isQueued  (s,_,_) = elem s $ map (\(x,_,_) -> x) t

-- Calculate the number of reachable nodes from a starting position
bfsReachableLocations :: Int -> [(Int, Index)] -> [Index] -> Int
bfsReachableLocations key a@((lim,curr):rest) visited | lim <  0  = 0
                                                      | otherwise = 1 + bfsReachableLocations key newNodes (visited++[curr])
    where neighbours = filter (not.isQueued) $ filter (not.(\x -> elem x visited)) $ mkEdges key curr
          isQueued n = elem n $ map (\(_,x) -> x) a
          newNodes   = rest ++ map (\x -> (lim-1, x)) neighbours

main = do
    print $ bfsPathLength           1362 (31,39) [((1,1), 0, Map.empty)]
    print $ bfsReachableLocations   1362 [(50, (1,1))] []

The code is not as readable as I'd like. There are probably easier ways of performing some of the steps that I have no yet encountered on my short Haskell journey. Any recommendations would be appreciated.

General Comments

mkEdges

I would probably just call this function edges.  mk (which I assume is short for make) has an imperative ring to it.

bfsPathLength :: Int -> Index -> [State] -> Int

You are forcing users of bfsPathLength to pass an initial state.  This forces them to be aware of the internal details of the algorithm, which is not a good design.  You could get rid of the [State] parameter and have bfsPathLength delegate to a helper function that takes the initial state.  Public interfaces should never expose details that aren't necessary.

bfsReachableLocations :: Int -> [(Int, Index)] -> [Index] -> Int

What's the purpose of this function?  It doesn't appear to be used for computation of the actual answer to the riddle.  If it's for debugging purposes, you should add a comment that says so (be sure to include what it actually does, and why it's useful for debugging as well).
Also, once again you force users to incorporate knowledge about the internal state of the algorithm.

Performance

You perform a linear search for nodes in the queue and the visited set.  You should use a more appropriate datastructure, such as a set, that can do the search in \$O(\log{n})\$, or even \$O(1)\$, time.

Abstraction

Consider separating the graph generation from the search algorithm.  This will allow you to use BFS search to solve other problems.  You have some options here, including:

Turn mkEdges into a parameter to the search function.
Use a typeclass.

For example, if you turn mkEdges into a parameter (and remove the internal state parameter), bfsPathLength might have the following type signature:

bfsPathLength :: (a -> [a]) -> a -> Int
bfsPathLength edgeGenerator goalLocation = ...

You should parameterize the start location:

bfsPathLength :: (a -> [a]) -> a -> a -> Int
bfsPathLength edgeGnerator startLocation goalLocation = ...

It seems like it would be useful to be able to find the actual path in most cases, rather than just the length:

bfsPath :: (a -> [a]) -> a -> [a]

Then you can write bfsPathLength as follows:

bfsPathLength :: (a -> [a]) -> a -> a-> Int
bfsPathLength edgeGenerator startLocation = length . (bfsPath edgeGenerator startLocation)


Validate if either or both of two fields has been provided, as a ValidationAttribute I have a binding model where at least one of two fields must be specified. I can't just set them both as [Required]. Here is what I came up with:

using System;
using System.ComponentModel.DataAnnotations;

namespace MyApp.Utils.DataAnnotations
{
    [AttributeUsage(AttributeTargets.Class, AllowMultiple = true)]
    public class EitherRequiredAttribute : ValidationAttribute
    {
        private readonly string _field1;
        private readonly string _field2;

        public EitherRequiredAttribute(string field1, string field2) => (_field1, _field2) = (field1, field2);

        protected override ValidationResult IsValid(object value, ValidationContext validationContext)
        {
            var property1 = validationContext.ObjectType.GetProperty(_field1);
            if (property1 == null)
                return new ValidationResult(string.Format("Unknown property: {0}", _field1), new[] { _field1 });
            var property2 = validationContext.ObjectType.GetProperty(_field2);
            if (property2 == null)
                return new ValidationResult(string.Format("Unknown property: {0}", _field2), new[] { _field2 });

            var value1 = property1.GetValue(validationContext.ObjectInstance);

            if (value1 != null)
                return ValidationResult.Success;

            var value2 = property2.GetValue(validationContext.ObjectInstance);

            if (value2 != null)
                return ValidationResult.Success;

            return new ValidationResult(string.Format("Either or both of \"{0}\" and \"{1}\" are required", _field1, _field2), new[] { _field1, _field2 });
        }
    }
}

Use case:

[EitherRequired("A", "B")]
public class SomeModel
{
    public int? A {get; set;}
    public int? B {get; set;}
}

Fields and properties are different things. You are mixing them up: the naming in the attribute code suggests that you want to operate on fields, but the use site is supplying property names. The naming of field1 and field2 should be changed to propertyName1 and propertyName2 respectively.

Don't forget your BindingFlags! Right now your code will look up any public property with the given name, including static properties. You probably only want public instance properties:

var property1 = validationContext.ObjectType.GetProperty(_field1, BindingFlags.Instance | BindingFlags.Public);

Depending on your performance constraints, reflection might be too slow for you. If so, it's common practice to cache the results of calls to GetProperty since that information is unchanging at runtime.

It's good practice to use nameof for getting string representations of identifiers, because if SomeModel.A gets renamed then the program won't compile until you also update the attribute argument.

[EitherRequired(nameof(A), nameof(B))]
public class SomeModel
{
    public int? A {get; set;}
    public int? B {get; set;}
}


Is it worth to compromise on speed to follow PEP 8 guidelines? I have this long line of code:

enc = encoder.predict(np.array([data[stock][4*i:4*(i+30)] for i in range(lens[stock]+days-30)]))

The problem is, the number of characters (97) exceed 79, which is not allowed by PEP 8. To follow the PEP 8 guideline I can

temp = [data[stock][4*i:4*(i+30)] for i in range(lens[stock]+days-30)]
enc = encoder.predict(np.array(temp))

But this creates a new variable that is stored in memory, rather then just a temporary storage in the first case. I'm assuming this takes slightly more time as well. The question is, is it worth compromising on speed to follow the guidelines/improve readability?

(PS: If there is a way to break down that one line of code into multiple lines, I would like to know)

A reasonable question to ask, maybe not for a single instance but if you end up with extremely performance-sensitive code. Black formats the code like this:

enc = encoder.predict(
    np.array(
        [
            data[stock][4 * i : 4 * (i + 30)]
            for i in range(lens[stock] + days - 30)
        ]
    )
)


Spliting string to array by number I have two functions to split string to array of strings.
Input string is: (1Letter E|V|R) + 8 number, last component of string (1Letter + V) + 8 or less numbers.

I'v got two functions advised to use, both of them are working properly. But I can't decide which one is better to use.

1st:

- (NSArray *) componentSaparetedByLength:(NSUInteger) length{
        NSMutableArray *array = [NSMutableArray new];
        NSRange range = NSMakeRange(0, length);
        NSString *subString = nil;
        while (range.location + range.length <= self.length) {
            subString = [self substringWithRange:range];
            [array addObject:subString];
            //Edit
            range.location = range.length + range.location;
            //Edit
            range.length = length;
        }

        if(range.location<self.length){
            subString = [self substringFromIndex:range.location];
            [array addObject:subString];
        }
        return array;
}

2nd:

NSMutableArray *brokenString=[NSMutableArray new];

int start=0;
for (; start<mainString.length-9; start+=9) {
     [brokenString addObject:[mainString substringWithRange:NSMakeRange(start, 9)]];
}
[brokenString addObject:[mainString substringFromIndex:start]];
NSLog(@"->%@",brokenString);

I would favor the first category approach, as it takes benefit of a great Objective-C feature: extend existing classes with new methods.

On the other hand probably both ways will fail if it comes to more advanced characters, like surrogate pairs, base characters plus combining marks, Hangul jamo, and Indic consonant clusters.

So here is my Category implementation:

@interface NSString (Split)
-(NSArray *)arrayBySplittingWithMaximumSize:(NSUInteger)size;
@end

@implementation NSString (Split)

-(NSArray *)arrayBySplittingWithMaximumSize:(NSUInteger)size
{
    NSMutableArray *letterArray = [NSMutableArray array];
    [self enumerateSubstringsInRange:NSMakeRange(0, [self length])
                                options:(NSStringEnumerationByComposedCharacterSequences)
                             usingBlock:^(NSString *substring,
                                          NSRange substringRange,
                                          NSRange enclosingRange,
                                          BOOL *stop) {
                                 [letterArray addObject:substring];
                             }];

    NSMutableArray *array = [NSMutableArray array];
    [letterArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        if (idx%size == 0) {
            [array addObject: [NSMutableString stringWithCapacity:size]];
        }
        NSMutableString *string = [array objectAtIndex:[array count]-1];
        [string appendString:obj];

    }];

    return array;
}

use it like:

NSArray *arraysWith9Letters = [letters arraysBySplittingWithMaximumSize:9];

This approach could be easily extended to split by words, sentences, lines too

@interface NSString (Split)
-(NSArray *)arrayBySplittingWithMaximumSize:(NSUInteger)size
                                     options:(NSStringEnumerationOptions) option;
@end

@implementation NSString (Split)

-(NSArray *)arrayBySplittingWithMaximumSize:(NSUInteger)size
                                     options:(NSStringEnumerationOptions) option
{
    NSMutableArray *letterArray = [NSMutableArray array];
    [self enumerateSubstringsInRange:NSMakeRange(0, [self length])
                                options:(option)
                             usingBlock:^(NSString *substring,
                                          NSRange substringRange,
                                          NSRange enclosingRange,
                                          BOOL *stop) {
                                 [letterArray addObject:substring];
                             }];

    NSMutableArray *array = [NSMutableArray array];
    [letterArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        if (idx%size == 0) {
            [array addObject: [NSMutableString stringWithCapacity:size]];
        }
        NSMutableString *string = [array objectAtIndex:[array count]-1];
        [string appendString:obj];

    }];

    return array;
}

Now use it like

NSString *letters = @"ABCDEFकट्रತ್ಯÖäüℝijgrvਉਤਸੁਕsasas";
NSArray *arraysWith9Letters = [letters arraysBySplittingWithMaximumSize:9 options:NSStringEnumerationByComposedCharacterSequences] ;
NSLog(@"%@", arraysWith9Letters);

NSString *lorem = @"Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam";
NSArray *loremArray = [lorem arraysBySplittingWithMaximumSize:9 options:NSStringEnumerationByWords];
NSLog(@"%@", loremArray);


Sort and Delete duplicate image files I'm trying to make a console application to sort and delete duplicate image files. I have a folder with about 20000 images which take up roughly 70GB of space.
I wrote the following script and it seems to work fine, but the issue is that my PC runs out of available RAM memory (it has 16GB) without reaching halfway through.
static void Main(string[] args)
{
    var uniqueData = new HashSet<string>();

    int progress = 0;
    int fileCount = Directory.GetFiles(imageFolderPath).Length;

    foreach (var file in Directory.GetFiles(imageFolderPath))
    {
        string data, year, month;

        using (var image = Image.FromFile(file))
        {

            using (var ms = new MemoryStream())
            {
                image.Save(ms, ImageFormat.Jpeg);
                data = Convert.ToBase64String(ms.ToArray());
            }

            try //try to get image date
            {
                var date = Encoding.UTF8.GetString(image.GetPropertyItem(36867).Value).Split(':');
                year = date[0];
                month = date[1];
            }
            catch
            {
                year = "Unknown";
                month = "Unknown";
            }
        }

        if (!uniqueData.Contains(data))
        {
            uniqueData.Add(data);

            string yearDirectory = Path.Combine(outputFolderPath, year);

            if (!Directory.Exists(yearDirectory))
            {
                Directory.CreateDirectory(yearDirectory);
            }

            string monthDirectory = Path.Combine(yearDirectory, (int.TryParse(month, out int i) && i > 0 && i < 14) ? CultureInfo.CurrentCulture.DateTimeFormat.GetMonthName(i) : month);

            if (!Directory.Exists(monthDirectory))
            {
                Directory.CreateDirectory(monthDirectory);
            }

            File.Move(file, Path.Combine(monthDirectory, Path.GetFileName(file)));
        }
        else
        {
            File.Delete(file);
        }

        progress++;
        Console.WriteLine($"{progress} / {fileCount}");
    }
}

You don't need to store the whole file contents, compute hash instead. Also converting each image to JPEG is not necessary, use image.RawFormat, it would be a bit faster.
using (SHA256 sha = SHA256.Create())
using (var ms = new MemoryStream((int)new FileInfo(file).Length))
{
    image.Save(ms, image.RawFormat);
    ms.Position = 0;
    data = Convert.ToBase64String(sha.ComputeHash(ms));
}

2nd option
if (!uniqueData.Contains(data))
{
    uniqueData.Add(data);
    // ...
}

Can be simplified to
if (uniqueData.Add(data))
{
    // ...
}

Also twice getting the directoriry files can be once
string[] files = Directory.GetFiles(imageFolderPath);
int fileCount = files.Length;

foreach (var file in files)
{
    // ...
}

And finally this one
if (!Directory.Exists(yearDirectory))
{
    Directory.CreateDirectory(yearDirectory);
}

Directory.CreateDirectory creates directory if it not exists, otherwise it does nothing. You can remove Exists check.
Directory.CreateDirectory(yearDirectory);


Merge sort on an Integer class This is a specific case in merge sort.  I'm trying to do a merge sort on an array that's created using the Java Integer class.  My implementation is slow and therefore needs some modifications for better performance.  I believe the process where I copy the original items to two new arrays over and over again is slowing it down.

How do I merge sort without copying?  The sorting must be stable and both methods should return Integer[].

private static Integer[] mergeSort(Integer[] a, int p, int q)
{
    if (a.length <= 1) return a;

    int mid = (int)Math.floor((q-p)/2);
    Integer[] left = new Integer[(mid - p) + 1];
    Integer[] right = new Integer[q - mid];
    int index = 0;

    for (int i = 0; i < left.length; i++)
    {
        left[i] = a[index++];
    }
    for (int i = 0; i < right.length; i++)
    {
        right[i] = a[index++];
    }

    left = mergeSort(left, 0, left.length-1);
    right = mergeSort(right, 0, right.length-1);
    return merge(left, right);
}

private static Integer[] merge(Integer[] a, Integer[] b)
{
    int i = 0; int j = 0; int k = 0;

    Integer[] result = new Integer[a.length+b.length];

    while (i < a.length || j < b.length)
    {
        if (i != a.length && j != b.length)
        {
            if (a[i].compareTo(b[j]) <= 0)
            {
                result[k++] = a[i++];
            }
            else
            {
                result[k++] = b[j++];
            }
        }
        else if (i < a.length)
        {
            result[k++] = a[i++];
        }
        else if (j < b.length)
        {
            result[k++] = b[j++];
        }
    }

    return result;

It was quite hard, but I figured it out. You can even pre-create the buffer with some value you know the mergesort will never exceed, and save some object creation overhead.

public class Mergesort
{
    public static void main(String[] args){
        int[] array = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        array = mergeSort(array, 0, array.length-1);
        for(int i = 0; i < array.length; i++){
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    private static int[] mergeSort(int[] a, int p, int q)
    {
        if (q-p < 1) return a;
        int mid = (q+p)/2;

        mergeSort(a, p, mid);
        mergeSort(a, mid+1, q);
        return merge(a, p, q, mid);
    }

    private static int[] merge(int[] a, int left, int right, int mid)
    {
        //buffer - in the worst case, we need to buffer the whole left partition
        int[] buffer = new int[a.length / 2 + 1];
        int bufferSize = 0;
        int bufferIndex = 0;
        int leftHead = left;
        int rightHead = mid+1;

        //we keep comparing unless we hit the boundary on either partition
        while(leftHead <= mid && rightHead <= right){
            //no data in the buffer - normal compare
            if((bufferSize - bufferIndex) == 0){
                //right is less than left - we overwrite left with right and store left in the buffer
                if(a[leftHead] > a[rightHead]){
                    buffer[bufferSize] = a[leftHead];
                    a[leftHead] = a[rightHead];
                    bufferSize++;
                    rightHead++;
                }
            }
            //some data in the buffer - we use buffer (instead of left) for comparison with right
            else{
                //right is less than buffer
                if(buffer[bufferIndex] > a[rightHead]){
                    //we overwrite next left value, but must save it in the buffer first
                    buffer[bufferSize] = a[leftHead];
                    a[leftHead] = a[rightHead];
                    rightHead++;
                    bufferSize++;
                }
                //buffer is less than right = we use the buffer value (but save the overwriten value in the buffer)
                else{
                    buffer[bufferSize] = a[leftHead];
                    a[leftHead] = buffer[bufferIndex];
                    bufferSize++;
                    bufferIndex++;
                }
            }
            leftHead++;
        }
        //now we hit the end of either partition - now we have only two of them (buffer and either left or right)
        //so we do traditional merge using these two
        while(leftHead <= right && (bufferSize - bufferIndex) > 0){
            if(rightHead <= right && a[rightHead] < buffer[bufferIndex]){
                a[leftHead] = a[rightHead];
                rightHead++;
            }
            else{
                if(leftHead <= mid){
                    buffer[bufferSize] = a[leftHead];
                    bufferSize++;
                }
                a[leftHead] = buffer[bufferIndex];
                bufferIndex++;
            }
            leftHead++;
        }
        return a;
    }
}

I did not extensively test it, nor did I measure it. You can try that and post the results.


As basic as routing in PHP can get I'd like to have neater URLs, no more and no less — I'd like to be able to write /page/subpage instead of something like ?p=page&s=subpage.

I've looked at various PHP frameworks and routing classes to see how they did it. Since most of them come with features I don't need, I wanted to try making my own system using only what's absolutely necessary — indeed, I think this is about as basic as routing can get.

Above all, I'd like to know if I've missed something. The code works, but I'm sure there are edge cases I didn't account for (or security issues; this is PHP after all).
On a side note, is there a difference betwen "routing" and "URL rewriting"? The terminology isn't all that clear to me.

.htaccess

RewriteEngine on

RewriteBase /routing_test/

RewriteCond %{REQUEST_FILENAME} !-l
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d

RewriteRule ^(.*)$ index.php [QSA,L]

inc/functions/routing.php

<?php

    define('DEFAULT_PAGE_NAME', 'default');

    function getPageName($level)
    {
        $requestParams = explode('/', $_SERVER['REQUEST_URI']);
        $scriptPath = explode('/', $_SERVER['SCRIPT_NAME']);

        // remove the base path
        while ($requestParams[0] === $scriptPath[0])
        {
            array_shift($requestParams);
            array_shift($scriptPath);
        }

        if ($level === 0)
        {
            return $requestParams[0] ?: DEFAULT_PAGE_NAME;
        }

        return isset($requestParams[$level]) ? $requestParams[$level] : '';
    }

As you can see, it's really only one function that does the work: getPageName($level) gives the name of the "directory" at the specified level.

What you do with those is up to you — in this case, I'm simply including a file with that name.

index.php

<?php

    define('BASE_PATH', '/routing_test');

    require_once 'inc/functions/routing.php';

?>

        <title>Routing Test</title>

            <?php

                $pageName = getPageName(0);
                $subpageName = getPageName(1);

                if (file_exists($file = 'inc/content/' . $pageName . '.php'))
                {
                    include $file;
                }
                else
                {
                    echo 'not found';
                }

            ?>

inc/content/default.php

This is the default page

inc/content/users.php

<?php

    if ($subpageName === '')
    {
        echo 'Displaying all users.' . '
';
    }
    else
    {
        $userId = $subpageName;
        echo 'Displaying user #' . $userId . '.
';
    }

?>

<a href="<?php echo BASE_PATH . '/' . DEFAULT_PAGE_NAME; ?>">go back

In this example, opening /routing_test/users would show Displaying all users., while /routing_test/users/123 would show Displaying user #123..

As I said, I'm mainly looking for advice on best practices, security issues and correctness (pretty much exactly the points on the tour page), though general feedback is always welcome.

On a side note, is there a difference betwen "routing" and "URL rewriting"? The terminology isn't all that clear to me.

Yes. Generally, "routing" describes the process of mapping URLs to code in some form. The standard example would be mapping a URL to a method of a controller.

On the other hand, "rewriting" doesn't map a URL to code, but maps a URL to a different URL.

[But both terms are often not 100% clearly defined, and are sometimes used interchangably]

Security: DOS

If I visit your index.php directly, without giving any parameters, I get an infinite loop in getPageName.

You shouldn't need a while loop here, replacing the script path without the index.php file name in the request parameter should do the same thing.

Security: Directory Traversal

Your index.php file is likely open to directory traversal and LFI in Windows (I don't have a Windows machine to test right now, but using \ should work). With current PHP versions, it is restricted to PHP files, but it should probably still be fixed.

Correctness: URL encoding

Because you use REQUEST_URI, the values you get will be URL encoded. So if I visit /users/foo"bar, I would get Displaying user #foo%22bar. instead of the expected result. For the example this may be fine, but it will likely cause bugs in the future.

Do note though that the URL encoding is currently all that protects you from XSS (and that the encoding happens client-side, so you should not necessarily trust it).

Approach

If it's just about mapping /page/subpage to ?p=page&s=subpage, I would probably use Apache URL rewriting exclusively (I'm no expert, but it should certainly be possible).

If you want the URL routing functionality, I would probably go with a more extended approach, which lets me define a whitelist of allowed URLs, and maps them to a controller method.


Dijkstra's Algorithm modified to take negative edge weights In the following Python implementation I have used color coded vertices to implement the Dijkstra's Algorithm in order to take negative edge weights.

G16 = {'a':[('b',3),('c',2)], 'b':[('c',-2)], 'c':[('d',1)], 'd':[]}
# the graph is a dictionary with they "key" as nodes and the "value" as a
# list of tuples
# each of those tuples represent an edge from the key vertex to the first
# element of the tuple
# the second element of the tuple is the weight of that edge.
# so, 'a':[('b',3),('c',2)] means an edge from a to b with weight 3
# and another edge from a to c with weight 2.

class minq:           #min_queue implementation to pop the vertex with the minimum distance
    def __init__(self,dist):
        self.elms = []

    def minq_len(self):
        return len(self.elms)

    def add(self,element):
        if element not in self.elms:
            self.elms.append(element)

    def min_pop(self,dist):
        min_cost = 99999999999
        for v in self.elms:
            min_cost = min(min_cost,dist[v])
        for key,cst in dist.items():
            if cst == min_cost:
                if key in self.elms:
                    v = key
        self.elms.remove(v)
        return v

def modified_dijkstras(graph,n):
    cost = {}
    color = {}            # color interpretation: w = white = unvisited, g = grey = to be processed, b = black = already processed
    for vertex in graph:
        cost[vertex] = 9999999     #setting cost of each vertex to a large number
        color[vertex] = 'w'        #setting color of each vertex as 'w'
    q = minq(cost)
    q.add(n)
    cost[n] = 0
    while q.minq_len() != 0:
        x=q.min_pop(cost)
        color[x] = 'g'
        for j,cost_j in graph[x]:
            temp = cost[j]
            cost[j] = min(cost[j],cost[x] + cost_j)
            if cost[j] < temp and color[j] == 'b':  #if the cost varries even when the vertex is marked 'b'
                color[j] = 'w'                      #color the node as 'w'
            if  color[j] != 'g':
                color[j] = 'g'
                q.add(j)                        #this can insert a vertex marked 'b' back into the queue.
        color[x] = 'b'
    return cost

The following is what is returned when you run the code on the Python interpreter with the graph defined on top:

>>>import dijkstra
>>>G16 = {'a':[('b',3),('c',2)], 'b':[('c',-2)], 'c':[('d',1)], 'd':[]}
>>>dijkstra.modified_dijkstras(G16,'a')
{'a': 0, 'b': 3, 'c': 1, 'd': 2}

Please let me know if this algorithm has a better runtime than Bellman Ford as I am not iterating through all the vertices repeatedly.

Please also report your analysis of the run time for this algorithm, if any.

I am afraid your implementation is in \$\Theta(EV)\$ in the worst case, and that is because in the outer while loop you iterate \$V\$ times and popping a node from your custom priority queue runs in \$n = V\$ steps, so we already have \$\Theta(V^2)\$. If your graph is really dense, the complexity will rise to \$\Theta(EV)\$.

In order to get it done efficiently without writing your (say, Fibonacci-) heap, you could import heapq

With it, you can come up with something like:

def sssp(graph, start_node):
    open = [(0, start_node)]
    closed = set()
    distance_map = {start_node: 0}
    while open:
        current_node = heapq.heappop(open)[1]
        if current_node in closed:
            continue
        closed.add(current_node)
        for child, arc_weight in graph[current_node]:
            if child in closed:
                continue
            tentative_distance = distance_map[current_node] + arc_weight
            if child not in distance_map.keys() or distance_map[child] > tentative_distance:
                distance_map[child] = tentative_distance
                heapq.heappush(open, (tentative_distance, child))
    return distance_map

The above runs in \$\Theta((E + V) \log V)\$. Also, the above version has a desirable property: it does not visit nodes that are disconnected from the source node. You might need to know which nodes are not reachable; to this end, you just make a lookup into distance_map: if a node is not there as a key, it is unreachable. This "pruning" may boost the performance if most graph nodes are not reachable from the source node.

About code

Note that PEP8 complains: you should have a single space after , and :. Also, in Python, it is customary to write the class names in CamelCase. Also, in line if  color[j] < temp and color[j] == 'b' you have two spaces after the the if; PEP8 requires one space only.

Hope that helps.

Post scriptum

On G16 = {'a': [('b': -1)], 'b': [('a': -1)]} your implementation goes into an  infinite loop; mine provides invalid results but does exit. If your graph has negative-weight cycles, I suggest you stick to Bellman-Ford; alright, its worst case running time is \$\Theta(EV)\$, but its constant factors are small, since it is just two nested loops.


JavaScript function for computing the checksum of a given number I've got to made a function which returns the checksum of an given integer.

Source code of my implementation so far:

function computeChecksum(num) {
  if (typeof num !== 'number' || isNaN(num)) {
    throw new Error('Number, which is not NaN, expected as Parameter.');
  }

  num = Math.floor(Math.abs(num)); // Make sure the computation is done based upon an positive Integer.

  if (num < 10) {
    return num;
  }

  let divisor = Math.pow(10, num.toString().length);
  let checksum = 0;

  while (divisor >= 10) {
    let quotient = Math.floor(num / divisor);
    let divisorAsString = divisor.toString(); // For avoiding calling .toString() two times later. Appropriated or exaggeration?

    checksum += quotient;
    num -= quotient * divisor;

    // Should I pass the return-value of .slice() through parseInt()?
    //  Or just keep the implicit casting which is done when using it as an arithmetic operand?
    divisor = divisorAsString.slice(0, divisorAsString.length - 1);
  }

  return checksum + num;
}

// -------- Just testing & demo-usage------------------
// -- Not important concerning question ! -------------
let testNumbers = [11, 111, 1111,
  1111, 11111, 111111,
  123, 468, 2510,
  2501, 123456789, 1
];
let biggestSize = Math.max.apply(null, testNumbers);
let pad = new Array(biggestSize.toString().length);

pad = pad.join(' ');

testNumbers.forEach((num) => {
  console.log('%s > %s',
    (pad + num).slice(-pad.length),
    computeChecksum(num));
});
// ----------------------------------------------------

Because not in a special hurry I've avoided to search the internet for other (already available) solutions.

So the code above is the solution which came to my mind.
It seems to work as expected. Please see the added testing.

Nevertheless I like to ask:

Are there a better algorithm for computing a checksum in JavaScript?
Could parts of my implementation been improved by using other patterns?
For example the pattern I used for creating an integer with a defined size. Perhaps there's a better way?

Two further questions I've put right into my code as comments. I think that way it is better understandable what I mean.

All comments, recommendations and hints concerning my question (and my code in general) appreciated.

Your approach is far too complicated.

How about just

function computeChecksum(num) {
  if (typeof num !== 'number' || isNaN(num)) {
    throw new Error('Number, which is not NaN, expected as Parameter.');
  }

  num = Math.floor(Math.abs(num));

  const sum = num.toString().split('').reduce(
                                  (acc, val) => acc + parseInt(val),
                                  0);
  return sum;
}

Or instead of converting between string and number you can use modulo:

function computeChecksum(num) {
  if (typeof num !== 'number' || isNaN(num)) {
    throw new Error('Number, which is not NaN, expected as Parameter.');
  }

  num = Math.floor(Math.abs(num));

  let checksum = 0;

  while (num > 0) {
    checksum += num % 10;
    num = Math.floor(num / 10);
  }

  return checksum;
}


Shipping calculator consisting of one field A made a shipping calculator, which consists of one field that is validated.

jsFiddle

HTML:

Калькулятор доставки

CSS:

.not_valid{
    border: 1px solid red;
}

.valid{
    border: 1px solid #ccc;
}

JS:

window.APP = window.APP || {};

APP.CityOfDepartureModel = Backbone.Model.extend({
  defaults: {
    cityName: undefined
  },

  validate: function(attrs) {
    var errorsArr = [];

    if($.trim(attrs.cityName).length == 0) {
        errorsArr.push('Это поле не может быть пустым')
    } else {
        if(isNaN(attrs.cityName) == false) { errorsArr.push('Это поле не может быть цифрой') };
    };

    if(errorsArr.length != 0) { return errorsArr };
  }
});

APP.CalculatorView = Backbone.View.extend({

  initialize: function() {
    this.cityOfDepartureModel = new APP.CityOfDepartureModel();
    this.cityOfDepartureWidjet = new APP.CityOfDepartureView({model: this.cityOfDepartureModel});
    this.render();
  },

  el: $('#contentContainer'),

  template: _.template($('#calculatorSubmitButtonTemplate').html()),

  render: function () {
    this.$el.append(this.cityOfDepartureWidjet.render().el);
    this.$el.append(this.template());
    return this;
  },

  events:{
    'click #calculatorSubmitButton' : 'submit'
  },

  submit: function() {
    var cityName = $('#fldCityOfDeparture').val();

    this.cityOfDepartureModel.set({'cityName': cityName});

    if(this.cityOfDepartureModel.isValid()) {
      this.cityOfDepartureWidjet.validMarkAdd();
    } else {
      var errorMessagesArr = this.cityOfDepartureModel.validationError;
      this.cityOfDepartureWidjet.notValidMarkAdd(errorMessagesArr);
      this.cityOfDepartureModel.set({'cityName': undefined});
    };

    console.log('-----------------------');
    console.log('city dep: ', this.cityOfDepartureModel.get('cityName'));
  }

});

APP.CityOfDepartureView = Backbone.View.extend({

  initialize: function() {

  },

  tagName: 'div',

  className: 'city_of_departure_container',

  id: 'cityOfDepartureContainer',

  template: _.template($('#cityOfDepartureTemplate').html()),

  render: function () {
    this.$el.html(this.template());
    return this;
  },

  notValidMarkAdd: function(errorMessagesArr) {
    this.$el.find('#fldCityOfDeparture').removeClass('valid').addClass('not_valid');

    this.$el.find('#errorMessageCityOfDeparture').html('');
    for(key in errorMessagesArr) {
      this.$el.find('#errorMessageCityOfDeparture').append(errorMessagesArr[key] + '
');
    };
  },

  validMarkAdd: function() {
    this.$el.find('#fldCityOfDeparture').removeClass('not_valid').addClass('valid');
    this.$el.find('#errorMessageCityOfDeparture').html('');
  }

});

var app = new APP.CalculatorView();

Getting rid of backbone, you can simplify this a lot.

HTML

Калькулятор доставки

Город отправления

          <input type="text" class="form-control" id="fldCityOfDeparture">

Рассчитать

JS

function validate(city) {
    return city.length == 0     ? 'Это поле не может быть пустым' :
           isNaN(city) == false ? 'Это поле не может быть цифрой' : '';
}
function showError(error) {
  document.getElementById('errorMessageCityOfDeparture').innerHTML = error;
}
document.getElementById('calculatorSubmitButton').onclick = () => {
  var city = document.getElementById('fldCityOfDeparture').value,
      error = validate(city);
  showError(error);
};

Here's a new fiddle, which shows the error messages on the page, rather than in the console.

https://jsfiddle.net/5uygd9s1/

NOTE: Currently I'm only using the not_valid class, since the border will not display when the error is empty.  If you want, you can change the class too depending on if there is an error or not.  The important point is finding a simple solution, especially when the problem is simple.  With all the available js frameworks today, it's easy to over-engineer.


Checking that an entered date is before the current date I want to write a function which returns true if a selected date is smaller than the current date, else return false.

This function is working as expected but I want to know the best possible way to do this.

private boolean isValidDate() {

    if(year<yearCurr)
    {
        //selected year is small date is small
        return true;
    }else
        if(year>yearCurr)
        {
            //selected year is greater date is greater
            return false;
        }else
        {
            //selected year is same as current year check month

            if(month<monthCurr)
            {
                //selected month is small date is small
                return true;
            }else
                if(month>monthCurr)
                {
                    //if selected month is greater date is greater
                    return false;
                }
                else
                {
                    // selected day of month is less than or equal to current date; date is valid
                    if(day<=dayCurr)
                        return true;
                    else
                        return false;
                }
        }
}

Just wanted to chime in:

Nobody mentioned this, but isValidDate() to determine whether 1 date is earlier than another date is frankly terrible. Call it isEarlierDate()
Where are the variables? Are those variables all defined outside of this function. That does not look good.
If there is one thing you learn today it is that this

if(day<=dayCurr)
    return true;
else
    return false;

should always be written as

return day<=dayCurr

As per @Heslacher, write out your variable names

This is my over-commented counter-proposal:

function isEarlierDate(){

  return year < currentYear || //Last year is in the past
         year == currentYear && month < currentMonth || //This year, earlier month is in the past
         year == currentYear && month == currentMonth && day < currentDay || //..
         false; //This is clearly not an earlier date
}


C# How to check if we've 'had' values from a method without having to re-call the method Currently I'm saving the values, gotten from a method, to a variable and using them later on.

This is the example code of how I do it:

var events = class.GetEvents();

if(events.Length > 0)
{
     foreach(var event in events)
     {
        // do something
     }
}
else
{
     // No events
     Console.Log("No Events");
}

But actually, What I'd like to achieve is something more like this:

foreach(var event in class.GetEvents()) // <-- If none, I'd like to know.
{
      // do something
}

However, I still need to log that there weren't any results. I'd have to do a check, and re-call the method to see if there are any results.. OR i++ in my loop, and if that's a 0 => log.

Is there a simpler way to do this?

I don't understand why you don't want to use a variable. However, one way is to provide an extension method for this:

public static void ForEachDo<T>(this IEnumerable<T> seq, Action<T> doWithEveryItem, Action doIfEmpty = null)
{
    bool isEmpty = true;
    foreach (T item in seq)
    {
        isEmpty = false;
        doWithEveryItem(item);
    }
    if (isEmpty && doIfEmpty != null)
        doIfEmpty();
}

Now you can use it with everything that implements IEnumerable<T> like a string:

"".ForEachDo(Console.WriteLine, () => Console.WriteLine("No Events")); // prints "No Events"