Moving certain items in a list to the end I am learning Python and would like to know if there's a better way to rewrite it.

What I am trying to do is to match list A that is passed to a method against a predefined list B. If an item in list A contains an item in list B, I'd like to move it to the end of list A.

# example 1
a = [1, 2, 3, 4, 5]
sanitized_list = sanitize(a) # [3, 4, 5, 1, 2]

# example 2
a = [3, 6, 1, 7, 4]
sanitized_list = sanitize(a) # [3, 6, 7, 4, 1]

def sanitize(arg):
    # predefined list
    predefined_list = [1, 2]

    for item in predefined_list:
        try:
            # check to see if 'arg' contain any item
            # in the predefined list
            i = arg.index(item)

            # save the value of arg[i]
            j = arg[i]

            # remove "j" from "arg"
            arg.pop(i)

            # append item to end of "arg"
            arg.append(j)
        except ValueError:
            pass

    return arg

Notice that what you are trying to do is a reordering of your list to put the elements of predefined_list at the end. Hence your function can be as simple as:

   def sanitize(arg):
      predefined_list = [1, 2]
      # Note that False<True and sort algorithm is stable, so:
      return sorted(arg, key=lambda x: x in predefined_list)

As an alternative to the lambda, you can use predefined_list.__contains__.

In fact the sorting key is False for elements which are not in predefined_list and True for elements which are contained. Since False<True the latter elements will be moved at the end of the list.

For this to work it is important to know that (at least from Python 2.2) the sort algorithm is guaranteed to be stable, i.e., it does not change the order of elements with the same key.

If you want to implement the algorithm yourself I would suggest, as @janos already did, to iterate first on the array to be sorted. This is better for performance and solves the issue of repeated elements.

A possible implementation could be:

def sanitize(arg):
    predefined_list = [1,2]
    pop_count = 0
    for i in range(len(arg)):
       if arg[i-pop_count] in predefined_list:
           arg.append(arg.pop(i-pop_count))
           pop_count += 1

About your code: I don't like the use of Exceptions to handle non exceptional situations... however the index method seems to force you to use exceptions so I see no alternative. Anyway I would keep the code inside the try...except block to the minimum, because otherwise you run the risk to hide exceptions caused by some other issue.

Another point is the fact that your algorithm does not handle repeated elements in the original list. You could handle them easily, see below.

Here is a possible cleaning of your implementation:

def sanitize(lst,predefined):
    """
    reorder elements of @lst by moving the elements which also
    belong to @predefined at the end of the list
    """
    for item in predefined:
        while True:
            try:
                i = lst.index(item)
            except ValueError:
                # lst does not contain any occurence of item
                break
            # move the i-th element to the end of the list
            lst.append(lst.pop(i))

    return lst

Only now I notice that the choice of the algorithm changes the resulting list. In fact you have to decide wether the elements moved at the end must keep the original order in the list (as in my suggested implementations) or must keep the order in the list of items to be removed (as in yours).


Adapting new design pattern with post handler I'm currently using this pattern in my JavaScript code. Somewhere in my code I use Dnianas.Post.init. init fires and it will bind DOM events.

At first everything was OK. But then, when you look at likePost method you will see that, I'm not using the var keyword to declare my variables. Because I if do that, then it won't be available to renderCreatedPost method. So basically I'm forced to do that.

I'm trying to adapt a new pattern and refactor my code that allow for that.

As you may know, defining variables without the var keyword is a bad practice and will result in errors in strict mode.

Dnianas.Post = {

    init: function () {
        this.bindEvents();
    },

    bindEvents: function () {
        $(document).on('submit', '#postForm', this.createPost);
        $(document).on('click', '#likePost', this.likePost);
    },

    createPost: function (event) {
        var self = Dnianas.Post;

        var request = $.ajax({
            url: '/posts/create',
            data: $(this).serialize(),
            beforeSend: function () {
                $loading.show();
            },
            complete: function () {
                $loading.hide();
            }
        });

        request.done(function (data) {
            self.renderCreatedPost(data);
        });

        event.preventDefault();
    },

    renderCreatedPost: function (data) {
        if (data.success == 'false') {
            $('.error').empty().append(data.message).slideDown(100).delay(3000).slideUp(250);
        } else {
            this.postForm[0].reset();
            $(data.post_html).insertAfter(this.postForm).hide().delay(100).slideDown(400);
            $('.no-posts').hide();
        }
    },

    likePost: function () {
        self = Dnianas.Post;
        $likePostEl = $(this);
        $postLikeCountEl = $likePostEl.children('#likeCount');
        postLikeCount = $postLikeCountEl.data('count');

        var request = $.ajax({
            url: '/posts/like',
            data: {
                post_id: $likePostEl.parents().get(2).dataset.id,
                user_id: $likePostEl.parents().get(2).dataset.userid,
                like_count: postLikeCount,
                _token: token
            }
        });

        request.done(function (data) {
            self.renderPostLike(data);
        });
    },

    renderPostLike: function (data) {
        if (data.like) {
            $likePostEl.children('.likeIcon').addClass('liked');
            $postLikeCountEl.addClass('liked');
        } else {
            $likePostEl.children('.likeIcon').removeClass('liked');
            $postLikeCountEl.removeClass('liked');
        }
        $postLikeCountEl.text(data.like_count);
    },

    getMaxId: function($element) {
        // Filter through the ids
        var ids = $element.map(function () {
            return +$(this).data('id') || 0;
        });

        // Get the highest id attribute
        last_id = Math.max.apply(Math, ids);

        // Return the maximum id.
        return last_id;
    },

    getNewPosts: function () {
        var self = Dnianas.Post;
        var ids = [];
        var $postEl = $('.poster_memb .tab_post');
        last_id = 0;

        // If there was posts.
        if ($postEl.length > 0) {
            self.getMaxId($postEl);
        }

        var request = $.ajax({
            url: '/posts/latest/' + last_id,
            type: 'GET',
            dataType: 'JSON'
        });

        request.done(function (data) {
            self.renderLatestPost(data);
        });
    },

    renderLatestPost: function (data) {
        if (data && data.is_new == 'true' && data.html) {
            $('.no-posts').hide();
            $(data.html).insertAfter('#postForm').hide().slideDown(500);
        }

        // Run the function every 10 seconds.
        setTimeout(this.getNewPosts, 10000);
    }
};

@GaryStorey hit on the simplest solution: Just pass your variables to the function:

// ...

likePost: function () {
    var $likePostEl = $(this),
        $postLikeCountEl = $likePostEl.children('#likeCount'),
        postLikeCount = $postLikeCountEl.data('count');

    var request = $.ajax({
        url: '/posts/like',
        data: {
            post_id: $likePostEl.parents().get(2).dataset.id,
            user_id: $likePostEl.parents().get(2).dataset.userid,
            like_count: postLikeCount,
            _token: token
        }
    });

    request.done(function (data) {
        Dnianas.Post.renderPostLike(data, $likePostEl);
    });
},

renderPostLike: function (data, $postEl) {
    var $likeCountEl = $postEl.children('#likeCount'),
        $likeIconEl = $postEl.children('.likeIcon');

    $postEl.toggleClass('liked', data.like);
    $likeIconEl.toggleClass('liked', data.like);
    $likeCountEl.text(data.like_count);
},

// ...

You'll note a few more changes:

There's no real need to pass all the variables. It seems everything can be found via the post element. So just find 'em.
Using .toggleClass() with a boolean as its 2nd argument is simpler than if/else branching
I've removed self for 2 reasons:

it's confusing that self isn't used to make a closure reference to this but to something else entirely
It's not that hard to just write Dnianas.Post. instead of self.

Looking at your code though, I suspect you have some flaky HTML and CSS too.

Why is it necessary to set the class liked on both the post element, and one of its children (the like icon)? Your CSS should just have a rule like post.liked .likeIcon { ... } so you only need to set the class on the post element, and the icon automatically changes.
The like-count element should probably not have that ID. Element IDs are meant to be unique across the whole page. I imagine you probably have several posts on a page, which would mean you have multiple elements with the ID #likeCount - and that's bad! You're doing the right thing with the like icon: It has a class name. And, contrary to IDs, class names are meant to be repeated.

Also, this stuff:

$likePostEl.parents().get(2).dataset.id

is just very, very fragile and opaque. You're getting the... um, the id property of the dataset of the great-grandparent of the post-like-widget element? That's pretty abstract. What is that element? I'm guessing it's the overall post container element, but it might be <body> or some random <div> used for layout. Are you sure the great-grandparent will always be the right element? What if the like-widget is wrapped in a different structure, and the great-grandparent is no longer what you expect it to be? And why does the great-grandparent have that data?

If I'm not mistaken, the two pieces of data you're fetching are the post author's ID, and the post's own ID. Those should rather be set on the like-button element itself, so it's where it's needed.

Or you should use a selector with .parents(), like .parents(".postContainer") or something. That would make the code a lot more understandable, and make the markup more flexible.

And why are you using dataset instead of jQuery's .data() which has better browser support and does the same thing? Edit: Oh, right, it's using .get() which returns a "naked" DOM element without the jQuery wrapper. The alternative would be ....eq(2).data("id"), since .eq() returns jQuery-wrapped elements.

But I'm also wondering why you're sending the like-count to the server. The server presumably knows the count, and is sure to be up-to-date unlike the page you're looking at. The server presumably also knows the user ID (whether it's the current user's ID, or the post author's ID). All you should need to send is the post's ID.


Object Oriented Console menu in Java I am a Spanish programming teacher in a vocational training course and I want my students to make a CRUD exercise on arrays.
I want them to start using OOP as well and as an example, I'm going to give them this example of OO Console Menu. We haven't seen Java 8 so far.
Any comments or improvements would be very appreciate.

MenuOption.java

package es.primerok.menu;

/**
* Created by Miguel-David Orrico on 18/02/2017.
*/
public abstract class MenuOption {
private String option;
private String menuLine;

public MenuOption(String option, String menuLine) {
    this.option = option;
    this.menuLine = menuLine;
}

@Override
public String toString() {
    return this.option+" - "+this.menuLine;
}

public String getOption() {
    return option;
}

public abstract void doAction();

}

Menu.java

package es.primerok.menu;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Miguel-David Orrico on 18/02/2017.
 */
public class Menu {
private static final String OPTION_EXIT="0";
private static final String LEVEL_INDENTATION ="    ";
private List<MenuOption> menuOptions=new ArrayList<>();
private int level=0;

public Menu(){}

public Menu(int level){
    this.level=level;
}

public void add(MenuOption m){
    this.menuOptions.add(m);
}

public void loopUntilExit(){

    String input;
    try(Scanner sc=new Scanner(System.in)) {
        while (true) {
            System.out.println(this);
            input = sc.nextLine();
            if (input.equals(OPTION_EXIT)) {
                return;
            }
            boolean foundOption = false;
            for (MenuOption m : menuOptions) {
                if (m.getOption().equalsIgnoreCase(input)) {
                    m.doAction();
                    foundOption = true;
                }
            }
            if (!foundOption) {
                System.out.println("Sorry, unrecognized option");
            }
        }
    }
}

@Override
public String toString(){
    StringBuilder sb = new StringBuilder();
    sb.append("Choose an option, "+OPTION_EXIT+" to exit.\n");
    for(MenuOption m:menuOptions){
        for(int i=0;i<level;i++){
            sb.append(LEVEL_INDENTATION);
        }
        sb.append(m).append("\n");
    }
    return sb.toString();
}
}

MenuTest.java

package es.primerok.menu;

/**
 * Created by Miguel-David Orrico on 18/02/2017.
 */
public class MenuTest {
public static void main(String[] args){

    System.out.println("es.primerok.menu.Menu Test");
    Menu mainMenu=new Menu();
    Menu subMenu=new Menu(1);

    subMenu.add(new MenuOption("+","Add numbers") {
        @Override
        public void doAction() {
            System.out.println("5+7=12");
        }
    });

    subMenu.add(new MenuOption("-","Subtract some numbers") {
        @Override
        public void doAction() {

            System.out.println("we're subtracting 6 and 5. The result is 1");
        }
    });
    mainMenu.add(new MenuOption("1","Option number 1") {
        @Override
        public void doAction() {
            System.out.println("This is number one");
        }
    });
    mainMenu.add(new MenuOption("A","Print an A") {
        @Override
        public void doAction() {
            System.out.println("I'm in Option A");
        }
    });
    mainMenu.add(new MenuOption("sub","This has a submenu") {
        @Override
        public void doAction() {
            subMenu.loopUntilExit();
        }
    });

    mainMenu.loopUntilExit();
}
}

Consistent style

As a teacher, try to lead by example. Sometimes you put whitespace around operators (which is the norm), sometimes you don't, sometimes you prefix an opening brace with space, sometimes you don't. Whatever you do, make sure it is consistent (or configure a code format in your IDE and run the formatter over the whole code.)

Non-OO menu decision

In OO you don't just rip information out of an object to base your decision on it. Instead of

 if (m.getOption().equalsIgnoreCase(input))

add a method to the MenuOption, to let the option decide, whether it is suited for the input

 if(m.matchesInput(input))

Variable scope

In your loopUntilExit(), you declare the input String outside the loop - why? This should go to the minimal acceptable scope, that is in the line where you call sc.nextLine().

Law of least surprises

I don't like abusing the toString() method to create a multi-line screen menu. This is not what I'd expect of toString(). Thus, I suggest you create another method to do this, and call it explicitly.

One afterthought

In 20 years of programming Java, I have never seen the use of Scanner in real life (TM). Is it really necessary, that every teacher seems to love this object and base their classes on it? Yes, it is simple, straightforward to use, and probably an easy-to-explore way to teach other principles without the input getting in your way, but it does not hold any practical relevance (at least as far I am concerned.)


Loop through a list of URLs multi-threading and check return code in python I have to loop through a list of over 4000 urls and check their http return code in python.

Url.txt: Contains a list of 4000 urls with one url per line.

The script takes a long time to run and I wanted to incorporate multi-threading to improve speed but not sure if I have done it properly.

It sure doesn't seem like it is working fast enough.

#! /usr/bin/python

# To just check a site and get the URL code
#import urllib.request
#print(urllib.request.urlopen("http://www.stackoverflow.com").getcode())
#############################################################################

import time
import requests

start = time.time()

from multiprocessing.dummy import Pool
pool = Pool(8) # Number of concurrent threads

#input file
URLS = open("url.txt","r")

#output file
file = open('output.csv', 'w')

#############################################################################

GREEN = '\033[92m'
YELLOW = '\033[93m'
RED = '\033[91m'
ENDC = '\033[0m'

def main():
    with open('url.txt') as f:

        url = f.read().splitlines()
        print( "\nTesting URLs.", time.ctime())

        all_text = pool.map(checkUrls,url)
        print("closing p")
        pool.close()
        pool.join()
            #checkUrls()
        print("Press CTRL+C to exit")
        #I don't need this sleep any longer. Can I remove the next line?
        time.sleep(100000) #Sleep 10 seconds

def checkUrls(url):
    count = 0
    status = "N/A"
    try:
        status = checkUrl(url)
    except requests.exceptions.ConnectionError:
        status = "DOWN"
    except requests.exceptions.HTTPError:
        status = "HttpError"
    except requests.exceptions.ProxyError:
        status = "ProxyError"
    except requests.exceptions.Timeout:
        status = "TimeoutError"
    except requests.exceptions.ConnectTimeout:
        status = "connectTimeout"
    except requests.exceptions.ReadTimeout:
        status = "ReadTimeout"
    except requests.exceptions.TooManyRedirects:
        status = "TooManyRedirects"
    except requests.exceptions.MissingSchema:
        status = "MissingSchema"
    except requests.exceptions.InvalidURL:
        status = "InvalidURL"
    except requests.exceptions.InvalidHeader:
        status = "InvalidHeader"
    except requests.exceptions.URLRequired:
        status = "URLmissing"
    except requests.exceptions.InvalidProxyURL:
        status = "InvalidProxy"
    except requests.exceptions.RetryError:
        status = "RetryError"
    except requests.exceptions.InvalidSchema:
        status = "InvalidSchema"

    printStatus(url, status, count)

    count+=1
    time_elapsed = datetime.now() - start_time

def checkUrl(url):
    r = requests.get(url, timeout=5)
    #print r.status_code
    return str(r.status_code)

def printStatus(url, status, count):
    color = GREEN

    count= count+1
    if status != "200":
        color=RED

    #print(color+status+ENDC+' '+ url)
    print(str(count)+'\t' + color+status+ENDC+' '+ url)
    file.write(str(count)+'\t' + color+status+ENDC+' '+ url +'\n')

    #print('Time elapsed (hh:mm:ss.ms) {}'.format(time_elapsed))

end = time.time()
print(end - start)

# Main app
#
if __name__ == '__main__':
    main()

Here is what I decided to change the code to this version, which runs a lot faster:

import urllib.request
import urllib.error
import time
from multiprocessing import Pool

start = time.time()

file = open('url10.txt', 'r', encoding="ISO-8859-1")
urls = file.readlines()

print(urls)

def checkurl(url):
    try:
        conn = urllib.request.urlopen(url)
    except urllib.error.HTTPError as e:
        # Return code error (e.g. 404, 501, ...)
        # ...
        print('HTTPError: {}'.format(e.code) + ', ' + url)
    except urllib.error.URLError as e:
        # Not an HTTP-specific error (e.g. connection refused)
        # ...
        print('URLError: {}'.format(e.reason) + ', ' + url)
    else:
        # 200
        # ...
        print('good' + ', ' + url)

if __name__ == "__main__":
    p = Pool(processes=20)
    result = p.map(checkurl, urls)

print("done in : ", time.time()-start)

Url.txt file contains a list of urls

http://yahoo.com
http://www.google.com

I have about a 1000 urls to check and it seems to work. Any suggestions to improve the functionality?


jQuery Lifestream Plug-in This is a plug-in which tracks your online activity aka a lifestream. You're currently able to use feeds like:

Delicious
Flickr
Github
Google Reader
Last.fm
Stackoverflow
Twitter
Youtube

At first I decided to load all the feeds at the end of all the asynchronous requests. This only required one DOM request at the end.

The problem with that approach is that it just takes too long to load. Some requests timed-out and others just took a while.

What I'm doing right now is changing the DOM after each feed request (e.g. twitter). At the moment this means 8 DOM changes.

What would be the best practice in this situation? Doing a setTimeout and accessing the dom after e.g. 400ms? Or would you leave it as it is now?

If you have any other remarks or suggestions, those would be appreciated as well.

/**
* Initializes the lifestream plug-in
* @param {Object} config Configuration object
*/
$.fn.lifestream = function(config){

var outputElement = this;

// Extend the default settings with the values passed
var settings = jQuery.extend({
  "classname": "lifestream",
  "limit": 10
}, config),
data = {
  "count": settings.list.length,
  "items": []
};

var finished = function(inputdata){

  $.merge(data.items, inputdata);

  data.items.sort(function(a,b){
      if(a.date > b.date){
          return -1;
      } else if(a.date === b.date){
          return 0;
      } else {
          return 1;
      }
  });

  var div = $('
');

  var length = (data.items.length < settings.limit)
    ? data.items.length
    : settings.limit

  for(var i = 0, j=length; i<j; i++){
    if(data.items[i].html){
      div.append('
'
        + data.items[i].html + "
");
    }
  }

  outputElement.html(div);

}

var load = function(){

  // Run over all the items in the list
  for(var i=0, j=settings.list.length; i<j; i++) {
    var item = settings.list[i];
    if($.fn.lifestream.feeds[item.service] &&
        $.isFunction($.fn.lifestream.feeds[item.service])){

      $.fn.lifestream.feeds[item.service](item, finished);
    }
  }
}

load();

};

Complete code:

https://github.com/christianv/jquery-lifestream/blob/master/jquery.lifestream.js

Documentation:

https://github.com/christianv/jquery-lifestream#readme

At first I decided to load all the feeds at the end of all the asynchronous requests. This only required one DOM request at the end. The problem with that approach is that it just takes too long to load. Some requests timed-out and others just took a while.

It's unclear to me why the requests are timing out, but you could simply store the results of the responses in memory as opposed to what you might be doing; synchronization logic is not necessary, you only need to know when all requests ended. However, the downside of this approach is that time outs can make your application show nothing to your visitors, which is something you really don't want to do...

  What I'm doing right now is changing the DOM after each feed request (e.g. twitter). At the moment this means 8 DOM changes.

It feels to me that 8 DOM changes are trivial to do by your browser; but the thing to do here is to actually figure out how many requests your code needs to be capable of handling.

A bad option would be to update the DOM on each X-th response, because you are introducing the timed-out problem again. So, a better option is adding your responses to a queue and updating the DOM each X ms. That way you have the best of both worlds, and it doesn't matter how much feeds you'll be adding because it scales pretty well. There might probably be other problems at the high end, like updating too much DOM at once, but that's out of the question here...


Administration Elevation I'm looking into Administration Elevation and I've come up with a solution that seems like it's perfectly sane, but I'm still in the dark about the professional methods to accomplish this.

Is there a better way to do this or is this fine?

using System;
using System.Diagnostics;
using System.Security.Principal;
using System.Windows.Forms;

namespace MyVendor.Installation
{
    static class Program
    {
        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);

            if (!IsRunAsAdmin())
            {
                Elevate();
                Application.Exit();
            }
            else
            {
                try
                {
                    Installer InstallerForm = new Installer();
                    Application.Run(InstallerForm);
                }
                catch (Exception e)
                {
                    //Display Exception message!

                    Logging.Log.Error("Unrecoverable exception:", e);
                    Application.Exit();
                }
            }
        }

        internal static bool IsRunAsAdmin()
        {
            var Principle = new WindowsPrincipal(WindowsIdentity.GetCurrent());
            return Principle.IsInRole(WindowsBuiltInRole.Administrator);
        }

        private static bool Elevate()
        {
            var SelfProc = new ProcessStartInfo
                {
                    UseShellExecute = true,
                    WorkingDirectory = Environment.CurrentDirectory,
                    FileName = Application.ExecutablePath,
                    Verb = "runas"
                };
            try
            {
                Process.Start(SelfProc);
                return true;
            }
            catch
            {
                Logging.Log.Error("Unable to elevate!");
                return false;
            }
        }
    }
}

You can create a manifest file and set the app to require administrative privileges. This will trigger the UAC user prompt with the dimmed screen when your application is run without requiring any code on your part.

See MSDN for the gory details:

  This file can be created by using any text editor. The application manifest file should have the same name as the target executable file with a .manifest extension.

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<assembly xmlns="urn:schemas-microsoft-com:asm.v1" manifestVersion="1.0">
  <assemblyIdentity version="1.0.0.0"
     processorArchitecture="X86"
     name="<your exec name minus extension>"
     type="win32"/>
  <description>Description of your application</description>
  <!-- Identify the application security requirements. -->
  <trustInfo xmlns="urn:schemas-microsoft-com:asm.v2">
    <security>
      <requestedPrivileges>
        <requestedExecutionLevel
          level="requireAdministrator"
          uiAccess="false"/>
        </requestedPrivileges>
       </security>
  </trustInfo>
</assembly>


Rabin-Karp String matching I am learning algorithms and have implemented the Rabin-Karp string search algorithm.   I didn't implement a rolling HashCode, but it's judged correct by this online judge.

It's slower than the str.indexOf() implementation (7ms, compared to 4 ms). Can this be improved? What is the time complexity for this?

class Solution {
public int strStr(String haystack, String needle) {
    if (haystack == null || needle == null)
        return -1;
    int needleHash = hashCode(needle);
    int plen = needle.length();
    boolean t = true;
    int tlen = haystack.length() - needle.length() + 1;
    for (int i = 0; i < tlen; i++) {
        String sub = haystack.substring(i, plen + i);
        int haystackHash = hashCode(sub);
        if (haystackHash == needleHash) {
            for (int j = 0; j < plen; j++) {
                char[] charN = needle.toCharArray();
                char[] charH = sub.toCharArray();
                if (charN[j] != charH[j]) {
                    t = false;
                }
            }
            if (t == true) {
                return i;
            }
        }
    }
    return -1;
}

public int hashCode(String value) {
    int h = 777;
    if (value.length() > 0) {
        char val[] = value.toCharArray();

        for (int i = 0; i < val.length; i++) {
            h = 31 * h + val[i];
        }
    }
    return h;
  }
}

You're missing the essential benefit of using a rolling hash:
for (int i = 0; i < tlen; i++) {
    String sub = haystack.substring(i, plen + i);
    int haystackHash = hashCode(sub);

Here, we examine plen characters of haystack at every character position, which is O(mn) where m is the haystack length and n the needle length.
By using a rolling hash, we only need to examine two characters each time around the loop (one to add to the hash, and one to remove from it).  That is of course O(m), which greatly improves the efficiency when n is large.
Only inspect the substring when there's a hash match, which should be infrequent.

Other issues:

Why convert needle and sub to char arrays to compare them?  You certainly don't want to do that every time around the j loop; you don't even need that loop if you write if (sub == needle) return i;.

if (t == true) is more simply written if (t) since that's the only true value that t can hold.  Again, not needed when you eliminate the j loop.

Improved code
You meant to write something more like this:
public int strStr(final String haystack, final String needle)
{
    if (haystack == null || needle == null)
        return -1;

    final int nlen = needle.length();
    final int hlen = haystack.length();
    if (nlen > hlen)
        return -1;

    int needleHash = 0;
    int hash_remove = 1;
    for (char c: needle.toCharArray()) {
        needleHash = addHash(needleHash, c);
        hash_remove = addHash(hash_remove, '\0');
    }

    int haystackHash = 0;
    for (int i = 0;  i < nlen - 1;  ++i) {
        haystackHash = addHash(haystackHash, haystack.charAt(i));
    }

    for (int i = 0;  i + nlen < hlen;  ++i) {
        haystackHash = addHash(haystackHash, haystack.charAt(i + nlen));
        if (haystackHash == needleHash && haystack.substring(i, i+nlen) == needle)
            return i;
        haystackHash -= haystack.charAt(i) * hash_remove;
    }

    return -1;
}

private int addHash(int h, char c)
{
    // calculation may overflow, but that's fine
    return 31 * h + c;
}

The only magic in there is the computation and use of hash_remove, to undo the effect of characters that have moved out of the match window.


Simplified board for X's and O's using Tkinter Recently I am learning to program in Python and in order to practice I tried to program a little game which consists in a board with 9 cells. In this board each player draw an 'X' or 'O' with left or right mouse button. The next code is a simplification with only 3-cell board.
Code 1: View
from tkinter import *
import numpy as np
from line3 import *

juego = Tablero()

root = Tk()

def leftClick1(event):
    canvas1.create_line(0,0,50,50)
    canvas1.create_line(0, 50, 50, 0)
    juego.ponerFicha(0,0,1)

def leftClick2(event):
    canvas2.create_line(0,0,50,50)
    canvas2.create_line(0, 50, 50, 0)
    juego.ponerFicha(0,1,1)

def leftClick3(event):
    canvas3.create_line(0,0,50,50)
    canvas3.create_line(0, 50, 50, 0)
    juego.ponerFicha(0,2,1)

def rightClick1(event):
    create_circle(24, 24, 20, canvas1)
    juego.ponerFicha(0,0,2)

def rightClick2(event):
    create_circle(24, 24, 20, canvas2)
    juego.ponerFicha(0,1,2)

def rightClick3(event):
    create_circle(24, 24, 20, canvas3)
    juego.ponerFicha(0,2,2)

topFrame = Frame(root)
topFrame.pack()
middleFrame = Frame(root)
middleFrame.pack()
bottomFrame = Frame(root)
bottomFrame.pack()

canvas1 = Canvas(topFrame, width=50, height=50)
canvas2 = Canvas(topFrame, width=50, height=50)
canvas3 = Canvas(topFrame, width=50, height=50)

canvas1.bind("<Button-1>", leftClick1)
canvas2.bind("<Button-1>", leftClick2)
canvas3.bind("<Button-1>", leftClick3)

canvas1.bind("<Button-3>", rightClick1)
canvas2.bind("<Button-3>", rightClick2)
canvas3.bind("<Button-3>", rightClick3)

canvas1.pack(side=LEFT)
canvas2.pack(side=LEFT)
canvas3.pack(side=LEFT)

canvas1.create_line(50,50,0,50)
canvas1.create_line(50,50,50,0)
canvas2.create_line(50,50,0,50)
canvas2.create_line(50,50,50,0)
canvas3.create_line(50,50,0,50)
canvas3.create_line(50,50,50,0)

root.mainloop()

Code 2: Classes and utils
import numpy as np

class Tablero:
    def __init__(self):
        self.tablero = np.zeros((3,3))

    def ponerFicha(self, x, y, tipoFicha):
        if (self.tablero[x][y] == 0):
            self.tablero[x][y] = tipoFicha
            print(self.tablero)

# Taken from StackOverFlow question
def create_circle(x, y, r, canvasName): #center coordinates, radius
    x0 = x - r
    y0 = y - r
    x1 = x + r
    y1 = y + r
    return canvasName.create_oval(x0, y0, x1, y1)

I feel I am repeating a lot of code when I programmed two events for each cell.

Is it possible to have one listener for all the cells?
How could I avoid repeat so much code?

Is it possible to have one listener for all the cells?

You still have to bind to each canvas but we can bind to one function that can handle all your conditions. The best way to do this is to put your canvas widgets into a list and then reference them by index.

  How could I avoid repeat so much code?

Its good to try and reduce your code. Try to keep it DRY (Don't Repeat Yourself) is something to strive for and in this case the bast way to do this is to build a single function that can handle all your conditions based on the event being passed and an index value.

Another helpful way to stay DRY is to know when to use a for loop to managed creations of widgets or variables needed. Here I have changed your code to use a for loop to build a list with your canvas widgets and apply the binds and pack all at once.

I have also added a check to see if something has already been written to your canvas so it cannot be overwritten.

By utilizing a list to and building our functionality around that list we can reduce the amount of code we need and at the same time make the boxes infantry scalable.

I have added a variable called np_tuple. All you have to do is change the numbers to change the size of your game.

I have combined all your code into one .py file but you can easily move your Tablero class back out.

from tkinter import *
import numpy as np

class Tablero:
    def __init__(self, np_tuple):
        self.tablero = np.zeros(np_tuple)

    def poner_ficha(self, x, y, tipo_ficha):
        if self.tablero[x][y] == 0:
            self.tablero[x][y] = tipo_ficha
            # print(self.tablero)

root = Tk()
clist = []
np_tuple = (3, 3)
juego = Tablero(np_tuple)

def create_circle(x, y, r, canvas_name):
    canvas_name.create_oval(x - r, y - r, x + r, y + r)

def click(event, xdex, ydex):
    if clist[xdex][ydex][1] == '':
        if event.num == 1:
            clist[xdex][ydex][1] = 'X'
            clist[xdex][ydex][0].create_line(0, 0, 50, 50)
            clist[xdex][ydex][0].create_line(0, 50, 50, 0)
            juego.poner_ficha(xdex, ydex, 1)

        else:
            clist[xdex][ydex][1] = 'O'
            create_circle(24, 24, 20, clist[xdex][ydex][0])
            juego.poner_ficha(xdex, ydex,  2)

box_frame = Frame(root)
box_frame.pack()

for x in range(np_tuple[0]):
    prep_list = []
    for y in range(np_tuple[1]):
        prep_list.append([Canvas(box_frame, width=50, height=50), ''])
        prep_list[y][0].create_line(50, 50, 0, 50)
        prep_list[y][0].create_line(50, 50, 50, 0)
        prep_list[y][0].bind("<Button-1>", lambda e, xdex=x, ydex=y: click(e, xdex, ydex))
        prep_list[y][0].bind("<Button-3>", lambda e, xdex=x, ydex=y: click(e, xdex, ydex))
        prep_list[y][0].grid(row=x, column=y)
    clist.append(prep_list)

root.mainloop()


Check Permutation in Scala The problem is: Given two strings, write a method to decide if one is a permutation of the other. I wrote the following code in scala, may I know any other optimization one?

def checkpermutation(str1:String, str2:String): Boolean=(str1, str2) match {
   case (a,b) if a==b => true
   case (a,b) if a.length() !=b.length() =>false
   case (a,b) if a.toList.sorted.mkString== a.toList.sorted.mkString => true
   case _ =>false
 }

There is no need to use matchers for this check. A logical expression would be enough:

def checkpermutation2(a:String, b:String): Boolean = {
  def sorted(s: String) = s.sorted.mkString
  (a == b) || (a.length == b.length && sorted(a) == sorted(b))
}


A PHP MVC controller to display a form and add an item to the database I am creating a controller that will display a form and once the form has been submitted to store the item in the database. After the item has been stored the user will be redirected back to the main page of the site. I am calling this controller with:

require_once("../app/controller/AddController.php");
new AddController();

The AddController.php file looks like this:

<?php

class AddController {

    public function __construct(){

        //Display our form
        if (empty($_POST['category']) || empty($_POST['description'])){

            require_once("../app/view/AddView.php");
            new AddView(array('title' => "Add an Item"));

        }

        //Add our new item to the database
        else {

            require_once("../app/model/AddModel.php");
            $add = new AddModel($_POST);

            if ($add->success())
                $_SESSION['message']['success'] = "The item has been added.";
            else
                $_SESSION['message']['error'] = "There was a problem adding your item.";

            header("Location: /");
            exit;

        }
    }
}

My main question is whether it is bad practice to place everything in the __construct() method like this since it is not really instantiating any variables or if I should get rid of __construct() and create a different method. The main reason I was doing this was to eliminate the third line when calling this class:

require_once("../app/controller/AddController.php");
$add = new AddController();
$add->someFunction();

If we talk about good practice then "Better not to do much in __constructor()".
Constructors are built to instantiate a class. They must not be overloaded with huge code. For providing variant functionalities, use methods instead. This is how to work in modules. For a specific kind of task, it is better to call the specific function instead of overloading the same method.

However, you can do so (and you are doing), but it is not a good approach.
Consider an example,

You have to perform 10 actions for a given event. You can do so in same function. But it would one day become much complex to add new functionalities in future. However if you are dividing the whole task in modules, you can and will be able to add new functionalities with no overhead. Also this makes your code:

General
Flexible
Easily understandable
Easily modifiable
Clean
Best practice

Also not all frameworks follow complete MVC but you can see in any one of them, separate functions and classes are there for specific task/action. This may cause to write more lines of code but since this is a good practice, almost all the developers follow the same mechanism.

However, it is user specific opinion. At last, you can do anything you want to do cos you are developing & may be this approach is somehow good in your context. Choice is yours.


Python methods to reduce running times KTNS algorithm I have been trying to develop an algorithm called keep the tool needed soonest (for more information about the KTNS explanation (page 3)) but during the simulations, I have realized that it takes too much time to run.

I want to decrease the running times and checking other previous questions about how to fast python coding Is Python slower than Java/C#? [closed] I have found several solutions, but I don't know how to implement them in my code.

On my computer it takes 0.004999876022338867 seconds, but the main problem is that for the whole program this function is called 13,000 times. I would like to reduce as much as possible the times but I don't know how. The fact of adapting the dictionaries to list is a good idea, but I don't know how to keep doing the same calculations. I have tried to ask in StackOverFlow but I've been said that here is a suitable place to do this kind of question. Here I attach my whole code, if you have any suggestion to improve it please don't hesitate to share with me.

import sets
import numpy
import copy
import time

J= {1: [6, 7],2: [2, 3], 3: [1, 6, 9], 4: [1, 5, 9], 5: [5, 8, 10], 6: [1, 3, 6, 8], 7: [5, 6, 8, 9], 8: [5, 7, 8], 9: [1, 4, 5, 8], 10: [1, 2, 4, 10]}

def KTNS(sigma=[10, 9, 4, 1, 6, 3, 7, 5, 2, 8], Jobs=J,  m=10 ,capacity=4 ):
    t0=time.time()
    Tools = {}
    Lin={}
    n=len(sigma)
    for i in range(1,m+1):
        for e in sigma:
            if i in Jobs[e]:
                Tools[i]=sets.Set([])

    count = 1
    available_tools=sets.Set()
    for e in sigma:
        for i in Jobs[e]:
            Tools[i].add(count)
            available_tools.add(i)
        count+=1
    Tin=copy.deepcopy(Tools)
    for e in Tin:
        Lin[e]=min(Tin[e])
    count=1
    J = numpy.array([0] *m)
    W = numpy.array([[0] * m] * n)
    while count<=len(sigma):
        for e in Tools:
            if len(available_tools)<capacity:
                reference=len(available_tools)
            else:
                reference=capacity
            while numpy.count_nonzero(J == 1) <reference:
                min_value = min(Lin.itervalues())
                min_keys = [k for k in Lin if Lin[k] == min_value]
                temp = min_keys[0] #min(Lin, key=Lin.get)
                if min_value>count:
                    if len(min_keys)>=2:
                        if count==1:
                            J[temp - 1] = 1
                            Lin[temp] = '-'
                        else:
                            J0=W[count-2]
                            k=0
                            for elements in min_keys: #tested
                                if numpy.count_nonzero(J == 1) < reference:
                                    if J0[elements-1]==1:
                                        J[elements-1]=1
                                        Lin[elements]='-'
                                        k=1
                                    else:
                                        pass
                                else:
                                    pass
                            if k==0:
                                J[temp - 1] = 1
                                Lin[temp] = '-'
                    else:
                        J[temp - 1] = 1
                        Lin[temp] = '-'
                else:
                    J[temp-1]=1
                    Lin[temp] = '-'
            Tin[e].discard(count)
            for element in Tin:
                try:
                    Lin[element] = min(Tin[element])
                except ValueError:
                    Tin[element]=sets.Set([len(sigma)+1])
                    Lin[element]=len(sigma)+1
        W[count-1]=J
        J= numpy.array([0] *m)
        count+=1
    Cost=0
    for e in range(1,len(sigma)):
        temp=W[e]-W[e-1]
        temp[temp < 0] = 0
        Cost+=sum(temp)

    return Cost+capacity,time.time()-t0

1. Bug

The code in the post does not compute the correct sequence of tool insertions for the Keep Tool Needed Soonest (KTNS) algorithm.

This is easiest to see if we print out the tools in the machine at each stage, by adding a line like

print(numpy.nonzero(J)[0] + 1)

near the end of the main loop. The first three lines of output are:

[ 1  2  4 10]
[1 4 5 8]
[1 5 6 9]

The third job in the schedule is job 4, which requires tools number 1, 5, and 9. So why did the code insert tool number 6? This is not needed by job 4, and so according to the KTNS algorithm it should not be inserted into the machine. Something has gone wrong.

This bug causes KTNS to return the wrong result for the example: it returns a cost of 17, but the KTNS algorithm only requires 16 tool insertions for this schedule.

2. Argument

I started to write a review of the code in the post, but the major problem is that the wrong data structures have been selected, so I think it will be more helpful to explain how to approach this kind of problem from first principles.

Tang and Denardo (1986) give a mathematical description of KTNS procedure in section 3 of their paper. Mathematical notation is used in scientific papers because of its compactness and lack of ambiguity. But that doesn't mean that it is a good idea to translate the notation directly into source code. Before writing code, you need to solve two problems:

Choosing good names for variables. In the context of a paper, if you don't know what \$L(i, n)\$ is supposed to mean, then you can refer to its formal definition

  \$L(i, n) = \min\left\{m:m∈T(i, n)\right\}\$

or to its informal description:

  the integer \$L(i, n)\$ is the first instant at or after instant \$n\$ at which tool \$i\$ is needed.

But in the context of source code it is not so easy to refer to these definitions, and so naming a variable Lin is only helpful to the reader who is following along with a copy of the paper. It is better to choose variable names that directly communicate the meaning, and to add comments (if necessary) to make that meaning unambiguous, for example:

# Mapping from tool to the next instant at which it will be needed.
next_needed = { ... }

Choosing data structures. The mathematical notation \$L(i, n)\$ doesn't give any clues as to how this should be implemented. Should you precompute a table of values for all tools \$i\$ and instants \$n\$? Or should you store for each tool the instants where that tool is needed in a sorted list and use bisection to find the first instant at or after \$n\$? Or should you store for each tool the instants where that tool is needed in a sorted queue, and pop its queue when a tool is used, so that the first element of queue is always the next instant when the tool will be needed? Or what? The choice of data structure is vital both in getting the most efficient implementation and in making the code simple and clear to the reader.

3. Decode

The key to finding the best data structures is to have a high level understanding of the algorithm, so that you are not trapped by the notation. The idea is to read the mathematics and decode it into concepts that you can work with. So when the paper says "Set \$J_i = 1\$" you figure out that this means "Insert tool \$i\$ into the machine".

This is the procedure:

  Step 1. Set \$J_i = 1\$ for \$C\$ values of \$i\$ having minimal values of \$L(i, 0)\$. Break the ties arbitrarily. Set \$J_i = 0\$ for the remaining \$M - C\$ values of \$i\$. Set \$n = 1\$.

  Step 2. Set \$W_n = J\$. Stop if \$n = N\$.

  Step 3. If each \$i\$ having \$L(i, n) = n\$ also has \$J_i = 1\$, set \$n = n + 1\$ and go to Step 2.

  Step 4. Pick \$i\$ having \$L(i, n) = n\$ and \$J_i = 0\$. Set \$J_i = 1\$.

  Step 5. Set \$J_k = 0\$ for a \$k\$ that maximizes \$L(p, n)\$ over \$\{p: J_p = 1\}\$. Go to Step 3.

Here are my thoughts as I read the procedure:

Steps 2 to step 5 are a loop over \$n\$.
\$n\$ represents the current instant (job) in the schedule.
\$n\$ starts at 1 (the first job) and goes up to \$N\$ (the last job). When implementing this in code, we will need to change this so that instants run from 0 up to (but not including) \$N\$, to avoid having to subtract 1 all the time.
Step 1 is initialization: we fill the machine with the tools that will needed the soonest.
In step 2, \$W_n = J\$ is just recording the set of tools that are now in the machine, which we don't care about since we are only going to be computing the cost.
Step 3 is asking "does the machine contain every tool that is needed by the current job?" If so, it can go on to the next job.
Step 4 only gets run if the machine lacks some tools that are needed. So we pick one of them, tool \$i\$, and insert it into the machine.
Step 5 picks a tool in the machine that is not currently needed and removes it from the machine. The tool is the one that won't be needed for the longest.

4. Pseudo-code

Now that you have a good high-level understanding of the algorithm, the next step is to describe it in pseudo-code. Something like this:

While the machine is under capacity:

Insert the tool that is needed soonest.

For each job in the schedule:

For each tool needed by the job:

Insert the tool into the machine.

While the machine is over capacity:

Remove the tool that won't be needed for the longest.

5. Data structures

Now examine the pseudo-code and figure out the data structures that are needed.

During initialization (but not afterwards), we need to be able to find the tool that is needed soonest.
We need to store the collection of tools that are currently in the machine.
We need to be able to find the size of this collection, so that we can determine whether the machine is over or under capacity.
This collection needs to support efficient insertion and deletion.
We need to be able to efficiently find the tool in the machine that won't be needed for the longest.

Point 1 is easy enough: for each tool, we can find the jobs that require that tool, and so find the first job for each tool, and use heapq.nsmallest to pick the tools we want.

But points 2 to 5 are hard to satisfy. Here are three alternative implementation strategies:

The requirement to repeatedly and efficiently extract the minimum or maximum element (point 5) suggests some kind of priority queue. In the Python standard library the closest thing we have to a priority queue is a heap and heaps don't support efficient deletion. However, there is a workaround for deleting items from heaps, namely to leave the item in the heap but mark it as deleted, and ignore deleted items when they are extracted. But in order to satisfy point 3 we would need to ignore the deleted items so we would need to maintain a separate count.
Use a data structure from a third-party library. It looks as if a SortedSet from the sortedcontainers library would meet our requirements.
Use an ordinary data structure like a set, and accept some inefficiency in point 5 by calling max (taking time proportional to the capacity of the machine). When the capacity is small, this is acceptable.

I'm going to use strategy 3 because it's the simplest and because in your example the capacity is 4, which is small enough for the inefficiency not to matter.

6. Implementation

from collections import defaultdict, deque
from heapq import nsmallest

def schedule_cost(schedule, requirements, capacity):
    """Return the cost of the schedule, that is, the number of tool insertions.

    Parameters:
    schedule -- Sequence of jobs.
    requirements -- Mapping from job to iterable of required tools.
    capacity -- Number of tools that the machine can hold at once.

    Jobs and tools may be any hashable objects.

    """
    # Mapping from tool to deque of instants when the tool will be needed.
    tool_instants = defaultdict(deque)
    for i, job in enumerate(schedule):
        assert len(requirements[job]) <= capacity
        for tool in requirements[job]:
            tool_instants[tool].append(i)
    for instants in tool_instants.values():
        instants.append(len(schedule))

    # Point in schedule when tool will next be needed.
    def next_needed(tool):
        return tool_instants[tool][0]

    # Set of tools in the machine.
    machine = set(nsmallest(capacity, tool_instants, key=next_needed))

    cost = len(machine)
    for job in schedule:
        # Set of tools that need to be inserted.
        new_tools = {tool for tool in requirements[job] if tool not in machine}
        if new_tools:
            cost += len(new_tools)
            # Remove tools if necessary to avoid going over capacity.
            for _ in range(len(machine) + len(new_tools) - capacity):
                machine.remove(max(machine, key=next_needed))
            machine.update(new_tools)
        for tool in requirements[job]:
            tool_instants[tool].popleft()

    return cost

7. Performance

The revised code in §6 is about 20 times faster than the code in the post:

>>> test = lambda:schedule_cost([10, 9, 4, 1, 6, 3, 7, 5, 2, 8], J, 4)
>>> from timeit import timeit
>>> KTNS()[1] / timeit(test, number=1)
20.335097001763668

8. Tool decisions

If you also want to return the decisions about which tools to insert (in addition to the cost), then that's easy. The newly inserted tools at each instant are in the new_tools set, and the tools in the machine at each instant are in the machine set. Take a copy of whichever one of these you need to keep.

For example, if you want to keep copies of machine then you would start with something like:

machine_record = []

and then at the end of each loop, append a copy of machine to the record:

machine_record.append(set(machine))

and findally return the record along with the cost:

return cost, machine_record


Dependency injection/dependency injection containers in MVC web app I just learned about dependency injection/dependency injection containers, and I realize that the controller in my MVC web application is hard to test.

My original controller class:

class Controller
{
    protected $db;
    private $article;
    private $nav;

    public function __construct($db)
    {
        $this->db = $db;
        $this->article = new Article($this->db);
        $this->nav = new Nav($this->db);
    }

    public function render($template)
    {
        var_dump($this->article->getRow());
        var_dump($this->nav->getRows());
    }

}

This is my test using DI/DIC in my MVC app:

Controller

class Controller
{
    private $container;

    public function __construct()
    {
    }

    public function render($container,$template)
    {
        $this->container = $container;
        var_dump($this->container->getArticle($url = 'home'));
        var_dump($this->container->getNav());
    }

}

Container: holds all objects which generate data from the database

class Container
{
    protected $db;
    private $article;
    private $nav;

    public function __construct($db)
    {
       $this->db = $db;
    }

    public function setArticle()
    {
        if (is_null($this->article))
        {
            $this->article = new Article($this->db);
        }
        return $this->article;
    }

    public function setNav()
    {
        if (is_null($this->nav))
        {
            $this->nav = new Nav($this->db);
        }
        return $this->nav;
    }

    public function getArticle($url)
    {
        return $this->setArticle()->getRow($url);
    }

    public function getNav()
    {
        return $this->setNav()->getRows();
    }
}

Models

class Article
{
    public function __construct($db)
    {

    }

    public function getRow($url)
    {
        return "row 1";
    }
}

class nav
{
    public function __construct($db)
    {

    }

    public function getRows()
    {
        return "rows nav";
    }
}

Usage

$db = 'pdo connection';
$template = 'template.phtml';
$container = new Container($db);
$controller = new Controller();
$controller->render($container,$template);

Questions:

Am I doing it correctly or not?
Do the improved Controller and Container above make sense to you if you were a developer going to pick up  this application's development?
Do I need any interfaces or traits as part of the app? If so, why?

You are not even doing Dependency Injection here. In your controller constructor for example

public function __construct($db)
{
    $this->db = $db;
    $this->article = new Article($this->db);
    $this->nav = new Nav($this->db);
}

sure you are injecting the $db but that is not a dependency for as long as it does not enforce the type of object required. In this case I can inject anything, say, a string, a number, an object of some other class, array or pretty much everything else. How is constructor going to control the behaviour of this object ?

Furthermore, you are 'newing' up the objects in constructor. Don't you think the objects you are initialising inside the constructor should instead be injected into it ? That is what IoC does.

The solution to first problem is Type Hinting. What you do here is you define the type of argument and only defined type can be passed to the constructor as argument. For more flexibility (which you'd more likely want in case of database connection) you can define an interface and inject an implementation of it into the constructor. So for example you define an interface DatabaseConnection like this:

interface DatabaseConnection {
    public function prepareQuery($queryString);
    public function addQueryBindings(array $queryBindings);
    public function run();
}

Now you can create multiple implementations of this interface and have IoC inject them into constructor. So now you can have MySQLDatabaseConnection, PostgreDatabaseConnection, MSSQLDatabaseConnection, SQLiteDatabaseConnection each one implementing DatabaseConnection and then you type hint the constructor of controller to accept DatabaseConnection

public function __construct(DatabaseConnection $db)
{
    $this->db = $db;
    $this->article = new Article($this->db);
    $this->nav = new Nav($this->db);
}

This constructor will allow any object which implements the DatabaseConnection interface and throw error if you try to inject anything else that is not a descendent of this interface.

Now that type hinting and interface is out of the way, I hope you can already see this but let me point it out.
The objects you are initialising inside controller constructor can be injected by IoC, this will also eliminate the need to have DatabaseConnection injected into a controller (which looks a terrible idea to me). So here is the controller constructor freshen up

public function __construct(Article $article, Nav $nav)
{
    $this->article = $article;
    $this->nav = $nav;
}

and you'll also need to change the constructor of both Article and Nav class to type hint the DatabaseConnection so that IoC can do its things

class Article
{
    public function __construct(DatabaseConnection $db)
    {
        //...
    }
}

and

class Nav
{
    public function __construct(DatabaseConnection $db)
    {
        //...
    }
}

The container, as you call it, is also not an IoC container (Inversion Of Control), It is not doing dependency injection just holding pre-initialised objects into itself. If you want Dependency Injection you need an IoC Container for that.
I dont think I can explain the architecture of an IoC container in a post here but with IoC in place you'll be able to initialise objects auto-magically with proper dependency already injected into it. So for example when you initialise our new controller from IoC container you will have an object of Controller with Article and Nav injected into it and both of them will have DatabaseConnection injected into them.

There are many IoC containers available on Github, some standalone and some as a part of a framework.


Convert ISO 8601 week to American-formatted date Requirements:

Implement a function that, given a standard date and an indicator
whether or not the output should be in american standard (weeks start
on sundays, the first week of the year is the week containing the
first day of the year) or in ISO8601 standard (weeks start on mondays,
the first week of the year is the week containing the first thursday
of the year) outputs the calendar week and year of the input date in
the following format as a string.
[calendar week] / [year]

Further requirements:

camelCase is to be used for function names
variables are to be underscore-seperated / lower_snake_case
option explicit is mandatory

This is my implementation:
Option Explicit
Public Function convertDateToFormattedCalendarWeek(input_date As Date, mode As Integer) As String

Dim week As String
Dim year As String
If mode = 0 Then 'mode 0 = standard american timekeeping
    week = CStr(DatePart("ww", input_date, vbSunday, vbFirstJan1))
    year = CStr(DatePart("yyyy", input_date, vbSunday, vbFirstJan1))
ElseIf mode = 1 Then 'mode 1 = ISO8601 business timekeeping
   'using the thursday in the given week instead for calculation to avoid the datepart leap year bug
    week = CStr(DatePart("ww", input_date - Weekday(input_date, vbMonday) + 4, vbMonday, vbFirstFourDays))
    year = CStr(DatePart("yyyy", input_date - Weekday(input_date, vbMonday) + 4, vbMonday, vbFirstFourDays))
Else
    convertDateToFormattedCalendarWeek = "error"
    Debug.Print ("function convertDateToFormattedCalendarWeek called with invalid parameter mode " & mode)
    Exit Function
End If

convertDateToFormattedCalendarWeek = week & " / " & year

End Function

Runs fine from what I've tested (a lot of dates)

convertDateToFormattedCalendarWeek = "error"
Debug.Print ("function convertDateToFormattedCalendarWeek called with invalid parameter mode " & mode)

Bad idea. A bad function call involving invalid parameters is a programming bug, and should be a serious run-time error that takes down the whole thing. By returning a String you're forcing the caller to systematically verify that it's not getting the "error" magic string literal.

The function has one job. If it can't do it, it should blow up: there's a run-time error specifically for this:

Err.Raise 5, "ConvertDateToFormattedCalendarWeek", _
             "Invalid 'mode' parameter value: " & mode

Run-time error 5 is essentially your ArgumentException. If I consume your function and pass an invalid parameter, I'm expecting that error to be raised.

But what's that mode anyway?

Public Function convertDateToFormattedCalendarWeek(input_date As Date, mode As Integer) As String

From the signature, I've no idea. [Seriously] consider using an enum instead:

Public Enum WeekFormattingMode
    WFM_AmericanStandard
    WFM_ISO8601
End Enum

And now your signature can be (note, member names should be PascalCase):

Public Function ConvertDateToFormattedCalendarWeek(input_date As Date, mode As WeekFormattingMode) As String

Now the caller gets auto-completion when calling the function, and has to work very hard to supply an invalid parameter value.

This also eliminates magic constants in your implementation, and replaces the otherwise needed comments, which makes the code more self-descriptive:

Select Case mode
    Case WFM_AmericanStandard
        'handle American Standard formatting

    Case WFM_ISO8601
        'handle ISO-8601 formatting

    Case Else
        Err.Raise 5, "ConvertDateToFormattedCalendarWeek", _
                     "An invalid 'mode' parameter was supplied"
End Select

The parameters are implicitly passed ByRef, but they're not assigned and the caller doesn't need to use them - they're really read-only inputs that the function needs in order to work with; such parameters should be passed ByVal.

I don't agree with all your naming conventions, but as long as it's consistent, it should be good. I like that you're not using the very commonly abused Systems Hungarian notation. Option Explicit shouldn't be part of a convention though - it should be mandatory for any VBA code that isn't toy code - and heck, even toy code should have it.

Since you're using underscores in identifiers, I need to mention that it's important that this convention isn't applied to member names, especially public ones. This is simple code and there's no harm, but in more complex object-oriented code, an underscore in a procedure name can mean code that can't compile: VBA is reserving the underscore for a very specific meaning in member names.

I like that your function is pure, and therefore easily testable. But where are the tests?

With Rubberduck (a free, open-source VBE add-in I'm working on with a bunch of fellow VBA reviewers) you could document your requirements - and have tests that you can run anytime you make a change, as simple as this:

Option Explicit
Option Private Module

'@TestModule
'@Folder("Tests")

Private Assert As New Rubberduck.AssertClass

'@TestMethod
Public Sub AmericanStandardOutputContainsSlashSpacer()
    On Error GoTo TestFail

    Const splitter As String = " / "
    Dim actual As String

    actual = ConvertDateToFormattedCalendarWeek(Date, WFM_AmericanStandard)
    Assert.IsTrue InStr(expected, splitter) > 0

TestExit:
    Exit Sub
TestFail:
    Assert.Fail "Test raised an error: #" & Err.Number & " - " & Err.Description
End Sub

And so on:

ISO standard weeks start on Monday
American standard weeks start on Sunday
...

Every part of the specifications should have at least one test that covers it. And then you'll want tests to document behavior for invalid inputs, too:

'@TestMethod
Public Sub RaisesErrorGivenInvalidMode()
    Const ExpectedError As Long = 5
    On Error GoTo TestFail

    Const InvalidMode As Long = -1
    If InvalidMode = WFM_AmericanStandard Or InvalidMode = WFM_ISO8601 Then
        Assert.Inconclusive "InvalidMode must be an invalid parameter value."
    End If

    Dim actual As String
    actual = ConvertDateToFormattedCalendarWeek(Now, InvalidMode)

Assert:
    Assert.Fail "Expected error was not raised."

TestExit:
    Exit Sub
TestFail:
    If Err.Number = ExpectedError Then
        Resume TestExit
    Else
        Resume Assert
    End If
End Sub

Arguably, that "mode" parameter indicates that the function is doing too many things. If you split it into FormatDateAmericanStandard and FormatDateISO8601 there would be no ambiguity whatsoever about how a date is formatted when you look at the calling code. Compare to:

foo = convertDateToFormattedCalendarWeek(someDate, 0)

Is foo formatted per the American standard or ISO-8601? The enum certainly helps, but then if I have to pick between this:

foo = ConvertDateToFormattedCalendarWeek(someDate, WFM_AmericanStandard)
bar = ConvertDateToFormattedCalendarWeek(someDate, WFM_ISO8601)

And this:

foo = FormatDateAmericanStandard(someDate)
bar = FormatDateISO8601(someDate)

I pick the latter without hesitation - note how it completely eliminates the whole discussion about raising an error vs. returning "error", and eliminates the need to test/document what happens given an invalid mode parameter. And it makes the code much more explicit and self-descriptive, too.

A note about the name: you're not "converting a date" - you're "formatting a date" per a specified standard; I'd make the function name start with FormatDate.


Tiny function to ensure a node of a BST has a valid relationship with its children I need to write a method to ensure that all of the nodes of a BST (Binary Search Tree) are valid. For a node to be valid, 2 things must hold:

The left child must be less than the current node's value
The right child must be greater than the current node's value.

I decided to write a helper method that checks an individual node. Conceptually, it's easy enough, but the end result looks clumsy. I started out with:

//Returns true if the left node is less than the current node, and the right
// node is greater than the current node.
private boolean nodeIsValid() {
    if (hasLeft() && left.compareTo(this) > 0) return false;
    if (hasRight() && right.compareTo(this) < 0) return false;

    return true;
}

Then I realized I could combine the 2 guards into a single check:

private boolean nodeIsValid2() {
    if (hasLeft() && left.compareTo(this) > 0 ||
        hasRight() && right.compareTo(this) < 0)
            return false;

    return true;
}

But it seems pretty bulky still. Plus, given I'm just returning true or false based on a condition, I imagine this could be compacted down into a single statement (although I don't know if that would help readability).

Which of my two versions is more pleasant and readable?

Can the check be cleanly reduced to a single statement?

Which of my two versions is more pleasant and readable?

The second is just bad as said in the comment by JK01.

It should be just

return !(hasLeft() && left.compareTo(this) > 0 ||
    hasRight() && right.compareTo(this) < 0);

and then you could use De-Morgan rule to get rid of the outer negation. However, something like

return (!hasLeft() || left.compareTo(this) <= 0) &&
    (!hasRight() || right.compareTo(this) >= 0);

has nothing to do with the idea it represents. Sticking with the original and adding braces is best:

private boolean nodeIsValid() {
    if (hasLeft() && left.compareTo(this) > 0) {
        return false;
    }
    if (hasRight() && right.compareTo(this) < 0) {
        return false;
    }
    return true;
}

It's easily extensible: Just add another condition.
It's structured: 2 simple expressions instead of a multiline monster.
It corresponds exactly with what could go wrong.


Console autocomplete for complex names I am currently writing a C# console application. Part of it is, that the user needs to enter a fairly complex system name. To make it easier I wrote a function that uses a string[] keywords and auto completes the string the user is typing in - on the run (which makes it different to this post in my opinion)

The code is working and acts as expected, but I am curious how the code could be improved (e.g. usability, efficiency). Also, what functionalities are missing, which you'd expect?

Thank you for the feedback!

    class Program
    {
        static void Main(string[] args)
        {
            string[] Keywords = new string[4] { "aX1223", "aE_334", "L_test1", "L_test2" };
            if (Keywords.Length == 0)
                throw new ArgumentException(nameof(Keywords), "No Keywords set!");

            bool searching = true;                 // true while looking for the keyword
            Console.CursorVisible = true;                 // To help users understand where they are typing
            string userInput = "";                   // Initialization of output
            string suggestion = Keywords[0];          // Initialization of default suggestion
            int toClear = suggestion.Length;    // Get the length of the line that needs to be cleared

            while (searching)
            {
                Console.Write(new String(' ', toClear));    // Clear line
                Console.CursorLeft = 0;                     // Relocate cursor to line start
                Console.Write(userInput);                      // Write what has been written previously

                if (suggestion != "")                        // If there is a suggestion fitting the entered string,
                {                                           // complete the string in color and reset the cursor
                    int col = Console.CursorLeft;
                    Console.ForegroundColor = ConsoleColor.Magenta;
                    Console.Write(suggestion.Substring(userInput.Length));
                    Console.ForegroundColor = ConsoleColor.White;
                    Console.CursorLeft = col;
                }

                string tempInput = Console.ReadKey().KeyChar.ToString();

                if (tempInput.Equals("\r"))                 // Evaluate input:
                {                                           //  -> Enter
                    if (!suggestion.Equals(""))             //     Valid entry?
                    {
                        searching = false;
                        userInput = suggestion;           //      -> use suggestion
                    }
                }
                else if (tempInput.Equals("\b"))            // Deleting last sign
                {
                    if (userInput.Length > 0)
                        userInput = userInput.Substring(0, userInput.Length - 1);
                }
                else                                        // Any other sign is added to the string
                    userInput += tempInput;

                // Set length to clear, if suggestion == "", the system string length needs to be cleared
                toClear = (userInput.Length > suggestion.Length) ? userInput.Length : suggestion.Length;

                // Reset suggestion. If no match is found, suggestion remains empty
                suggestion = "";

                // Check keywords for suggestion
                for (int i = 0; i < Keywords.Length; i++)
                {
                    if (Keywords[i].StartsWith(userInput))
                    {
                        suggestion = Keywords[i];
                        break;
                    }
                }
            }

            // reset cursor visibility
            Console.CursorVisible = false;
        }
    }

A few minor comments:

Don't mix equality types.

You use suggestion != "" in one place, then !suggestion.Equals(""). Don't. Use the same type of equality (either using .Equals or not using .Equals) everywhere.
Only use non-braced statements in the case of guard clauses, and even then be careful.

Basically, this is OK:

if (Keywords.Length == 0)
    throw new ArgumentException(nameof(Keywords), "No Keywords set!");

This is not:

if (userInput.Length > 0)
    userInput = userInput.Substring(0, userInput.Length - 1);

Try to use built-ins (especially System.Math) when possible.

I.e. take toClear = (userInput.Length > suggestion.Length) ? userInput.Length : suggestion.Length; and convert it to toClear = Math.Max(userInput.Length, suggestion.Length). They're functionally equivalent and the Math.Max reads nicer.

The rest of it looks good, I think you did a pretty good job implementing the idea here. I might suggest building functions out, but this is a small enough program it's probably not necessary.


A* Search in JavaScript I just implemented a version of A* search in JavaScript for educational purposes. I'd really love it if you could take a look and tell me how to improve my code.

The grid passed in is just a multidimensional array (2-D array) where each slot in the inner array is an object with property weight.

The point of this function is to build an "algorithm visualizer", where I have all the nodes that were visited by A* (visited) and all the nodes that A* eventually selected to be part of the shortest path (path). I later take this and display this to the user with my UI logic.

In terms of the heuristic, I use Euclidean Distance.

import PriorityQueue from "./data structures/priorityqueue";

export default function astar(grid, startNode, endNode) {
  function isValid(r, c) {
    if (r < 0 || c < 0) {
      return false;
    }
    if (r < grid.length && c < grid[r].length) {
      return true;
    }
    return false;
  }

  function calculateHeuristic(r, c) {
    let row = (endNode[0] - r) ** 2;
    let col = (endNode[1] - c) ** 2;
    return (row + col) ** (1 / 2);
  }

  let dist = [], // represents distances from start to node
    visited = [], // list of all the nodes A* visits
    ordering = []; // final ordering

  for (let r = 0; r < grid.length; r++) {
    let row = [],
      orderingRow = [];
    for (let c = 0; c < grid[r].length; c++) {
      row.push(Number.MAX_VALUE);
      orderingRow.push(null);
    }
    dist.push(row);
    ordering.push(orderingRow);
  }
  let d = 0;
  let pqueue = new PriorityQueue();
  let priority = calculateHeuristic(startNode[0], startNode[0]) + d;
  pqueue.enqueue([startNode[0], startNode[1], startNode, d], priority);
  let cur,
    neighbors = [
      [1, 0],
      [-1, 0],
      [0, 1],
      [0, -1]
    ];

  while (!pqueue.isEmpty()) {
    cur = pqueue.dequeue();
    let r = cur.element[0],
      c = cur.element[1],
      origin = cur.element[2],
      d = cur.element[3];

    visited.push([r, c]);

    if (dist[r][c] <= d) {
      continue;
    }

    ordering[r][c] = origin;
    dist[r][c] = d;

    if (r === endNode[0] && c === endNode[1]) {
      break;
    }

    for (let n of neighbors) {
      let rr = r + n[0];
      let cc = c + n[1];
      if (!isValid(rr, cc)) {
        continue;
      }
      let dd = d + grid[rr][cc].weight;
      if (dd < dist[rr][cc]) {
        priority = dd + calculateHeuristic(rr, cc);
        pqueue.enqueue([rr, cc, [r, c], dd], priority);
      }
    }
  }

  let path = [endNode];

  let r = endNode[0],
    c = endNode[1];

  while (r !== startNode[0] || c !== startNode[1]) {
    path.push(ordering[r][c]);
    [r, c] = ordering[r][c];
  }
  path.reverse();
  return { visited, path };
}

Thank you for reading and I look forward to your critiques.

Having 3 parallel 2D arrays in javascript for simple data is a bit overkill. Put those in a single 2D array or you can fold it into the grid's nodes.

If you want step by step visualization then you'll need to break up your function into sections: init, step and finalize.

init is everything before the main while loop.

step is the while loop body

finalize is only triggered when the loop otherwise breaks or exits.

Whether you group all the data it needs (like pqueue, dist, etc.) into an object that gets passed in or become globals doesn't really matter when it's for educational reasons. But if they are in a single object then it's easier for the visualizer to get that as well.


Simulating a scale, balancing weight from lists I have simulated balancing a scale by having each side total the same weight.

The scale has two weights (left and right side) and some spare weights:

weights = [3, 4]
spare_weights = [1, 2, 7, 7]

A maximum of two weights can be used from the spare weights to balance the scale. The spare(s) may be on a single side or split between both.

The output should be the minimum number of weight needed to balance the scale.

import itertools

weights = [3, 4]
spare_weights = [1, 2, 7, 7]
c = enumerate([subset for l in range(0, 3) for subset in itertools.combinations(spare_weights, l)])

cc = cc = list(itertools.combinations(c, 2))

left, right = weights
qualifying_combos = []
for c in cc:
    l, r = c
    if sum(l[1]) + left == sum(r[1]) + right:
        qualifying_combos.append(list(l[1]) + list(r[1]))
    elif sum(l[1]) + right == sum(r[1]) + left:
        qualifying_combos.append(list(l[1]) + list(r[1]))
print(min(qualifying_combos, key=len))

output:

[1]

Is there a more elegant way to code this?

Write functions. Make this a balance_scale function, that returns the minimum.
Your variable names are pretty poor, single letter variable names leave people guessing at what they mean.
You should change cc = cc = ... to just one assignment.

Since you can use a maximum of two spare weights the solution can be a lot simpler than you've produced.

\$W_1\$ is the smaller weight in weights and \$W_2\$ is the larger.
If \$W_1 = W_2\$ then you return an empty list.
We can determine what weight is needed when only one weight can be used.

\$S = W_2 - W_1\$

Therefore if \$S\$ is in spare_weights then we can return \$S\$.
For each \$S_1\$ in spare_weights we can determine the weight needed, \$S_2\$.

\$S_2 = |W_2 - W_1 - S_1|\$

We take the absolute as this weight can be on either side of the scale. If the non-absolute value of \$S_2\$ is positive then we add it to \$W_1 + S_1\$ if it's negative then we add it to \$W_2\$.

If we add \$0\$ twice to spare_weights, then we can see that (4), (3) and (2) are all roughly the same equation.

We don't need to check if \$S_1\$ and \$S_2\$ both exist in spare_weights, as the only time they are the same is if \$W_1 = W_2\$, and so they would both be 0. We however have to assign \$S_1\$ to 0 first.

def balance_scale(scale, spares):
    w1, w2 = sorted(scale)
    spare_set = set(spares) | {0}
    for s1 in [0] + spares:
        s2 = abs(w2 - w1 - s1)
        if s2 in spare_set:
            return [i for i in [s1, s2] if i]
    return None

print(balance_scale([4, 3], [1, 2, 7, 7]))

[1]


C++ bitset implementation What are the issues/better ways to do this? I was just trying to implement this for practice and learn C++. Can anyone suggest efficient implementations of other functions such as count, size, all, none, etc?

#define NO_OF_BITS (8 * sizeof(unsigned int))

#include <iostream>
#include <assert.h>

template<ssize_t n>
class BitArray {
  private:
    int array[n];

  public:
    BitArray();
    void set(unsigned int);
    void reset(unsigned int);
    void flip(unsigned int);
    int test(unsigned int);
};

template<ssize_t n>
BitArray<n>::BitArray() {
  memset(array, 0, sizeof(array));
}

template<ssize_t n>
void BitArray<n>::set(unsigned int k) {
  array[k/NO_OF_BITS] |= (1U << (k%NO_OF_BITS));
}

template<ssize_t n>
void BitArray<n>::reset(unsigned int k) {
  array[k/NO_OF_BITS] &= ~(1U << (k%NO_OF_BITS));
}

template<ssize_t n>
int BitArray<n>::test(unsigned int k) {
  return ( (array[k/NO_OF_BITS] & (1U<<(k%NO_OF_BITS))) != 0 );
}

template<ssize_t n>
void BitArray<n>::flip(unsigned int k) {
  array[k/NO_OF_BITS] ^= (1U <<(k%NO_OF_BITS));
}

int main() {
  BitArray<10>* bs = new BitArray<10>();
  bs->set(100);
  assert(bs->test(100)>=1);
  bs->reset(100);
  assert(bs->test(100)==0);
  bs->flip(100);
  assert(bs->test(100)>=1);
}

Prefer typed constants over #defines:

NO_OF_BITS should be a const unsigned int or const size_t and should also be a private member of BitArray, since it is not used elsewhere.

Also, NO_OF_BITS is a bad name for the constant. Num of bits in what? Num of bits in an integer. So named it accordingly.

As it was already suggested, use CHAR_BIT from <climits>. Also, adding unsigned to the sizeof call doesn't really make a difference.

The ALL_UPPERCASE notation should be reserved for macros and macro constants, to differentiate those from actual C++ entities (the preprocessor is like a mini-language inside C++ that doesn't live by the same rules). PascalCase or even camelCase are more modern notations for typed constants.

Summing up, it could look something like this:

    class BitArray {
    private:
        static const unsigned int IntBits = CHAR_BIT * sizeof(int);
    ...
    };

Side note: constexpr would have been my choice over const if this was C++11.

Use unsigned types if a value should never be negative:

ssize_t is the "signed" variant of size_t. You are using ssize_t as the template parameter for the size of your bit array. The message you pass to readers of your code with this is that the size of a bit array could be negative. I don't think this would make any sense. Either use std::size_t or a plain unsigned int.

Make consistent use of const and bool:

BitArray<n>::test() does not modify the bit array, so it should be a const method. E.g.:

int test(unsigned int) const;
                       ^^^^^

The const will also go in the method definition.

Also, test() has no business returning an int. It is a true or false query, so it should return a bool.

You don't need memset to zero init an array:

C++ has always had the ability to zero initialize arrays in an object constructor. Most people are not aware of it an still use the verbose and error prone memset. Read the entry about zero initialization on cppreference. Also a related question on SO. You can rewrite your constructor like this:

template<ssize_t n>
BitArray<n>::BitArray()
    : array()
    // zero initialized
{ }

Don't use dynamic allocations where a static will do:

BitArray<10>* bs = new BitArray<10>();

Sure that code is just a usage sample, but still, there is no real need to dynamically allocate the object. The ability to declared objects by value is one of the nicest features of C++, so use it instead of a dynamic alloc when it makes sense.

// No need to 'new' it in this case.
BitArray<10> bs;

Pointers/dynamic memory are normally only used when you need to extend the lifetime of an object beyond its scope of declaration. This is not the case in your example.

Not to mention, of course, that the object in your sample code is never deleted and thus leaks memory.


Euler 12: counting divisors of a triangle number This is the question:

  The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

  1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

  Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

  We can see that 28 is the first triangle number to have over five divisors.

  What is the value of the first triangle number to have over five hundred divisors?

import math
def triangulated(num):
    x = 0
    for num in range(1, num + 1):
        x = x + num
    return x

l = []

def factors(g):
    for n in range(1, triangulated(g) + 1):
        if triangulated(g) % n == 0:
            l.append(n)
    if len(l) > 500:
        print(triangulated(g))
        print(l)
    l.clear()

for k in range(1, 10000000000):
    factors(k)
    print(k)

Help optimise this problem.

This is not a review, but an extended comment.

Project Euler problems are about math, not programming. To optimize, you need to do the math homework first:

The \$n\$'th triangular number is \$\dfrac{n (n+1)}{2}\$.
A number of divisors, aka \$\sigma_0\$, is a multiplicative function. The link to divisor function may also be interesting.
\$n\$ and \$n+1\$ are coprime.

That should be enough to get you started with optimization.


Are 2 streams really needed? I have a simple text file setup as a Resource through my application's Properties as a byte[]. In order to access a "Stream.ReadLine" function, I believe I need to make it into a StreamReader. Is there a way to get the following result using only 1 Stream, or else, any tricks to make it better?

List<string> list = new List<string>();

using (Stream s = new MemoryStream(myFile))
{
    using (StreamReader sr = new StreamReader(s))
    {
        while (!sr.EndOfStream)
        {
            list.Add(sr.ReadLine());
        }
    }
}

Not without having to reinvent a lot of other things and make it more complex, no. This solution looks to be the best to me. You even use using correctly, which is one of my frequent nitpicks. However, if you want to simplify that bit of code, you might be able to help it with an extension method like so:

        List<string> list;

        using (var s = new MemoryStream(myFile))
        {
            list = s.ReadLines().ToList();
        }

...

    public static IEnumerable<string> ReadLines(this Stream s)
    {
        using (var sr = new StreamReader(s))
        {
            while (!sr.EndOfStream)
            {
                yield return sr.ReadLine();
            }
        }
    }


C# Class of client methods for interacting with web servers I'm in QA Automation, and C# isn't my first language. I've written a small class of methods for GETting and POSTing to web URLs. I use these when I want to test certain things that really fall outside the jurisdiction of Selenium, but are still roughly "black box" type testing. Link scanning, and culling data from POSTBIN, are a few examples.

I was wondering if you C# gurus might like to look the code over, and let me know if there are better ways to do what I've done, or if there's any potential gotcha's I haven't thought of:

public class RawHttp
{
    public static string Url = null;

    public RawHttp(string url)
    {
        Url = url;
    }

    public HttpStatusCode GetStatusCode(string url = null)
    {
        HttpStatusCode result = default(HttpStatusCode);
        string activeUrl = url ?? Url;

        var request = WebRequest.Create(activeUrl);
        request.Method = "HEAD";
        using (var response = request.GetResponse() as HttpWebResponse)
        {
            if (response != null)
            {
                result = response.StatusCode;
                //var headers = response.Headers;
                response.Close();
            }
        }
        return result;
    }

    public string GetBody(string url = null)
    {
        string activeUrl = url ?? Url;

        var request = (HttpWebRequest)WebRequest.Create(activeUrl);
        request.Method = "GET";
        // Set some reasonable limits on resources used by this request
        request.MaximumAutomaticRedirections = 4;
        request.MaximumResponseHeadersLength = 4;
        // Set credentials to use for this request.
        request.Credentials = CredentialCache.DefaultCredentials;
        var response = (HttpWebResponse)request.GetResponse();

        //Console.WriteLine("Content length is {0}", response.ContentLength);
        //Console.WriteLine("Content type is {0}", response.ContentType);

        // Get the stream associated with the response.
        Stream receiveStream = response.GetResponseStream();
        // Pipes the stream to a higher level stream reader with the required encoding format.
        var readStream = new StreamReader(receiveStream, Encoding.UTF8);
        var body = readStream.ReadToEnd();
        response.Close();
        readStream.Close();
        return body;
    }

    public string Post(string url = null, string parameters = "")
    {
        string activeUrl = url ?? Url;

        var req = WebRequest.Create(activeUrl);
        req.ContentType = "application/x-www-form-urlencoded";
        req.Method = "POST";
        byte[] bytes = Encoding.ASCII.GetBytes(parameters);
        req.ContentLength = bytes.Length;
        Stream os = req.GetRequestStream();
        os.Write(bytes, 0, bytes.Length); //Push it out there
        os.Close();
        var resp = req.GetResponse();
        //if (resp == null) {return null;}
        var sr = new System.IO.StreamReader(resp.GetResponseStream());
        return sr.ReadToEnd().Trim();
    }
}

Thanks!

It's probably fine for test code. There are a few things I noticed. None of these are necessarily a problem. They may never affect your tests. But they're not ideal either.

You're not calling Dispose() on everything that you strictly should (eg, Streams).
You're always encoding your post parameters in ASCII, but reading the responses in UTF8. If you're sticking to basic English characters that'll be fine, but if you try other languages/character sets it may be problematic.
the GetStatusCode() function is using the HEAD method. Not all endpoints will respond properly to the HEAD method, or is the same way that they would to GET or POST.

If you're going to be doing a lot of this then you may want to look at the WebClient class. It's a little bit simpler to use, and may be sufficient for your needs.


Node AWS lambda with pg-promise I've written a lambda to perform simple steps to a redshift database. It runs multiple queries with transaction. I use pg-promise.

'use strict';
const config = require('./redshift_config_from_env');
const redshiftConn = `pg://${config.user}:${config.password}@${config.host}/${config.database}`;
const pgp = require('pg-promise')();

var tableCopyQuery = function(tableName) {
  return `
      ALTER TABLE ${tableName}_temp
      RENAME TO ${tableName}_process;
      CREATE TABLE ${tableName}_temp (LIKE ${tableName}_process);`;
};
var insertQuery = function(tableName) {
  return `
      INSERT INTO ${tableName}
      SELECT DISTINCT ${tableName}_process.*
        FROM ${tableName}_process
        LEFT JOIN ${tableName} USING (id)
       WHERE ${tableName}.id IS NULL
       ORDER BY ${tableName}_process.id;
      DROP TABLE ${tableName}_process;`;
};

exports.handler = function(event, context) {
  const client = pgp(redshiftConn);

  client.tx(function (t) {
    return t.batch([
      t.none(tableCopyQuery('active_connections')),
      t.none(insertQuery('active_connections')),
      t.none(tableCopyQuery('active_downloads')),
      t.none(insertQuery('active_downloads'))
    ]);
  })
    .then(function () {
      context.succeed(`Successfully Refreshed.`);
    })
    .catch(function (error) {
      context.fail(`Failed to run queries : ${JSON.stringify(error)}`);
    });
};

I think I may move sql queries into .sql file outside of the function.

Maybe the var could be turned into let because the scope will fit?

You shouldn't create the database object on every function call. Read this answer (and its question) for an example of this.


PHP performance considerations of passing variable into a function Example code:

<?php
class MyClass {
    public $bar = array('a', 'b', 'c');
    public function getBar() {return $this->bar;}

    public function execute(array $fooArray) {
        foreach ($fooArray as $foo) {
            echo $foo.":".$this->checkBar($foo, $this->getBar())." ";// PASSED IN//
            //echo $foo.":".$this->checkBar($foo)." ";// RETRIEVED //
        }
    }

    // PASSED IN //
    public function checkBar($foo, array $fooCheck) {
        return in_array($foo, $fooCheck);
    }

    // RETRIEVED //
    /*public function checkBar($foo) {
         $fooCheck = $this->getBar();
         return in_array($foo, $fooCheck);
    }*/
}

$someClass = new MyClass();
$someClass->execute(array('a','f','c','g'));
?>

Are there any performance considerations to passing $fooCheck in as a variable into checkBar vs having MyClass::checkBar() handle calling the function itself?

Having (1)

public function execute(array $fooArray)
{
    foreach ($fooArray as $foo) {
        echo $foo . ":" . $this->checkBar($foo, $this->getBar()) . " ";
    }
}

public function checkBar($foo, array $fooCheck)
{
    return in_array($foo, $fooCheck);
}

is the exact same thing (performance wise) as (2)

public function execute(array $fooArray)
{
    foreach ($fooArray as $foo) {
        echo $foo . ":" . $this->checkBar($foo) . " ";
    }
}

public function checkBar($foo)
{
    return in_array($foo, $this->getBar());
}

In example (1), if you needed checkBar() to handle several different array inputs, then you would be able to differentiate them in execute(). Whereas example (2) would be better if you knew you would only be checking against a single array.

It's easier to expand code that's written like example (1).


db access wrapper for Go project I'm adding db access to my go program, it looks like this:

package db_access

import (
    "database/sql"
    "fmt"
    "my_database"
)

type TheType struct {
    Name string
}

func LoadTheTypeFromDb(db *sql.DB, id uint) (*TheType, error) {
    query := fmt.Sprintf(
        "SELECT %s FROM %s WHERE %s = ?",
        my_database.NAME,
        my_database.TABLE,
        my_database.ID,
    )

    var theType TheType

    err := db.QueryRow(query, id).Scan(&theType.Name)

    switch {
    case err == sql.ErrNoRows:
        n := my_database.NewNotFoundError(err)
        return nil, &n
    case err != nil:
        return nil, err
    default:
        return &theType, nil
    }
}

And some part of the my_database package:

package my_database

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
)

func GetDatabaseInstance(connectionString string) (*sql.DB, error) {
    db, err := sql.Open("mysql", connectionString)

    if err != nil {
        c := newConnectionError(err)
        return nil, &c
    }

    err = db.Ping()

    if err != nil {
        c := newConnectionError(err)
        return nil, &c
    }

    return db, nil
}

And the custom errors:

package my_database

import (
    "fmt"
    "reflect"
)

type ConnectionError struct {
    errorMessage string
}

func newConnectionError(err error) ConnectionError {
    return ConnectionError{fmt.Sprintf("Connection error %s %s", reflect.TypeOf(err), err)}
}

func (e *ConnectionError) Error() string {
    return e.errorMessage
}

type QueryError struct {
    errorMessage string
}

func newQueryError(err error) QueryError {
    return QueryError{fmt.Sprintf("Query error %s %s", reflect.TypeOf(err), err)}
}

func (e *QueryError) Error() string {
    return e.errorMessage
}

type NotFoundError struct {
    errorMessage string
}

func NewNotFoundError(err error) NotFoundError {
    return NotFoundError{fmt.Sprintf("Not found - %s", err)}
}

func (e *NotFoundError) Error() string {
    return e.errorMessage
}

I add a custom NotFound error, because when the row is not found, I don't want to leak sql.ErrNoRows outside, is that ok? I don't like that the constructor for NotFound error is public, unlike all other custom errors, furthermore, I think I would need to add that switch statement to every Load* method … also not so good.
The custom error code is very repetitive, is there a way to clean that up?
Any other comments are much appreciated.

Why don't you want to leak sql.ErrNoRows outside? I find it quite explicit.

It seems that you are wrapping your errors with some context: there is a very nice package for this: https://godoc.org/github.com/pkg/errors

Using it, your code would look like this:

package db_access

import (
    "database/sql"
    "fmt"
    "my_database"
)

type TheType struct {
    Name string
}

// uses named returns
func LoadTheTypeFromDb(db *sql.DB, id uint) (row TheType, err error) {
    query := fmt.Sprintf(
        "SELECT %s FROM %s WHERE %s = ?",
        my_database.NAME,
        my_database.TABLE,
        my_database.ID,
    )

    err = db.QueryRow(query, id).Scan(&row.Name)
    return
}

And your "my_database"

package my_database

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
    "github.com/pkg/errors"
)

func GetDatabaseInstance(connectionString string) (db *sql.DB, err error) {
    db, err = sql.Open("mysql", connectionString)

    if err != nil {
        err = errors.Wrap("open failed", err)
        return
    }

    err = db.Ping()
    // if err is nil, errors.Wrap returns nil
    err = errors.Wrap("ping failed", err)

    return
}

Your custom error file should not be needed anymore!


Partitioning comments by date I have a list of Comment objects comments. Each Comment has several properties, one of which is the date the comment was posted. I've sorted this list by date and there is at least 1 comment per date in a range.

I would like to loop over comments and for every date, create a new list of comments just for that day. However, the way I'm currently doing it feels very inefficient. Is there a more pythonic or efficient way to do this? (I've implemented a daterange(start_date, end_date) generator function according to this answer):

comment_arrays = [] #array of arrays
for d in date_range(date(2015,1,1), date(2016,1,1)):
    day_comments = []
    for c in comments:
        if c.date == d:
            day_comments.append(c)
        else if c.date > d:
            comment_arrays.append(day_comments)

I think this would a great situation to use itertools.groupby in.

datekey = lambda x: x.date
comments.sort(key=datekey)
date_comments = [list(group) for date, group in itertools.groupby(comments, datekey)]

This of course groups all your comments, not only the ones in your date range. I'd use filter to skip the ones out of your range if you can't make use of the extra days comments.