script that imports only data that is not in the database yet I want to write a script that imports data into a database (in django). The database has a Company class with a name (CharField) instance. Additionally, it has a Person class with name (CharField), email address (CharField) and a company which is a reference to the Company class (ForeginKey).

The database already has entries.

The script is importing the data from a csv file with the following format:

Company Name | Email Address | First Name | Last Name

While importing the data I want the script to go through the database and check if the same people only exist once (no duplicates) and also make sure that the email address is unique. So one email address can only belong to one person not multiple. Incorrections that are already in the database can be ignored.

def handle(self, *args, **options):
        with open('/path/to/myFile.csv') as f:
            reader = csv.reader(f)
            next(f)
            for row in reader:
                company_in_list = row[0].strip()        ###reading the company name from the file
                visitor_company = ''
                company_in_db = Company.objects.filter(name=company_in_list)        ###searching for this company name in the db
                time.sleep(0.05)
                if len(company_in_db) == 1:
                    visitor_company = company_in_db[0]
                    print "company already created", visitor_company
                elif len(company_in_db) == 0:                                       ###if the company doens't exist it will create one
                    print "created a new company"
                    visitor_company = Company.objects.create(name=company_in_list)
                else:
                    raise NameError("Multiple Companies with the same name, please fix the database")
                visitor_name = row[2].strip() + ' ' + row[3].strip()                ###reading the name of the person from the file
                email = row[1].strip()                                              ###reading the email address from the file
                person_in_db = Person.objects.filter(email=email)                   ###searching for this email address in the db
                if len(person_in_db) == 0 :
                    Person.objects.create(company=visitor_company,name=visitor_name,email=email)    ###if email doesn't exist, create the person
                    print "new Person created", visitor_name
                if len(person_in_db) > 0 :
                    for p in person_in_db:
                        if p.name == visitor_name and p.company == visitor_company:                 ###if the person does exist, if it's not the same one (different name or company) stop and raise an error
                            print "Person already created"
                            pass
                        else:
                            raise NameError('multiple people with the same email address, please fix this. Row:', row, p)
        print 'done commands'

My script opens the file, ignores the header row next(f), then for each row it searches the name of the company in the database. If it already exists, it will take that instance. If not, it will create that company. If there are multiple companies with the same name, the script throws an error.

Then it reads the email address and name from the file. It searches for the email address in the database. If it doesn't exist it creates an this person with the previously gathered infos (name and company). If it exists, it checks if the person in the database has the same name and company. If the info matches it will pass as the person is already in the database, if not it will raise an error saying there are multiple persons in the database.

The time.sleep() are in there so that the database won't get locked.

Is there any way to make this faster or write this better?

You don't specify how many new records you're adding. But you did mention in comments some trouble with the "database getting locked", which I'll interpret as "database bogging down because you were hammering it with this script", and so I'll assume you're inserting a lot of records.

If you're doing that, and you're not stuck on an old version of Django, there are some bulk data commands to help you. More on that later.

First, though, let's talk about your constraints. You are applying a very strict uniqueness constraint to company names: a company name is assumed to be totally distinct.

I don't know your context, but I'm from the United States. In the US, corporations are managed at the state level: you'll hear things like "ExampleCorp, a Delaware corporation, ..."

Also, businesses other than corporations are managed at the county or city level (depending on the state, and the size of the city). So I can go down to my "county seat" (the town where the business of the county is conducted, usually containing the jail and the county courthouse) and register a "DBA form" (DBA means "doing business as") that creates a "name" for my business.

So you might go to your county seat in county 1, and register "TomCo". And someone else named Tom might go to the county seat in county 2 and register "TomCo". And they would be totally legit.

So, again, I don't know your use case. But you might need to re-think the whole "company names are distinct" thing. Perhaps you could attach an email domain, which is guaranteed to be globally unique, to the company record?

Regardless, there's also the chance that your batch of users might include the same company multiple times. For example, if your Django app is some sort of SaaS and you are bulk-loading a new customer, maybe all the new people are from the same company. So I think it behooves you to cache that information.

Next, there's the chance that your users are in the input file more than once. So you might as well filter those out.

Next, there's the concept that your users must have a "first name" and a "last name" and that's it. Seriously? That's very Anglo-centric, but not very realistic. What about people from Brazil, who generally go by a single name, like "Ronaldinho"? (Although they come from the Portuguese tradition, so they might have 4 names if they get formal: "Ronaldo de Assis Moreira"?) What about my all-time favorite bandit, "Tuco Benedicto Pacifico Juan Maria Ramirez"? At least your database uses a single name field, so that's good.

And finally, you should process the new user creations in bulk if possible, to minimize the number of database calls and the number of transactions.

Let's take a look:

def handle(self, *args, **options):
    with open('/path/to/myFile.csv') as f:
        reader = csv.reader(f)
        next(f)

The only problem with the first few lines is the hard-coding of the csv file. Is there no way to get that into a command line argument, or configuration setting?

        for row in reader:
            company_in_list = row[0].strip()        ###reading the company name from the file
            visitor_company = ''
            company_in_db = Company.objects.filter(name=company_in_list)        ###searching for this company name in the db
            time.sleep(0.05)

This section I object to because you're doing things in a scattershot order. There are several places where you pull out fields from the csv row, and you always use the all the fields, except when you raise an exception and abort. So let's put all the fields together:

for row in reader:
    company = row[0].strip()
    email   = row[1].strip()
    first   = row[2].strip()
    last    = row[3].strip()

But we can do better! That's just looping over a bunch of things, performing the exact same computation for each: we could use a list comprehension or a generator expression, like so:

for row in reader:
    (co_name, email, first, last) = (field.strip() for field in row)

Your CSV file may actually have more columns than 4, so you might have to use row[:4] instead.

First, let's deal with the name. And let's support mononymy! I'm doing this because an invalid name seems like a good reason to skip the record, which we should do as early as possible:

    name = last if not first
        else first if not last
        else first + ' ' + last

    if not name:
        print("Skipping bad names first={!r}, last={!r}".format(first, last))

Next, you check if the company is already in the database. If it's in the database, great. If it's not in the database, you create it. If it's in the database more than once, you raise an exception.

I don't think that last case is really the job of this script. That condition - that the company name should be unique in the table - is properly the job of a database constraint rather than a "create users" script. (It's not even a "create companies" script, which would at least be on-topic.)

So I'm going to suggest you ignore that case. Let's just have the script either create the company if it doesn't exist, or use the existing company if there is already a record.

One thing you don't do, is check if the company name is empty. I don't know if this is a valid case or not, so I'm going to leave that alone (after bringing it to your attention).

Our first step will be to separate out the company names (because there could be M:N of them versus the people), and the email addresses (because that is your key, apparently).

Let's put the company names into a set, in order to make them unique. And we'll put the entire record into a dictionary keyed by the email addresses:

companies = set()
visitors = {} # email -> tuple

for row in ...

    # ...

    companies.add(co_name)

    v = (email, name, co_name)

    if email in visitors:
        print('''Duplicate emails found:
{email} -> {old}
and
{email} -> {new}'''
            .format(email=email, old=visitors[email], new=v))

     visitors[email] = v

At this point, after looping through all the records, you will have a set of company names and a dictionary of visitors, with all the duplicate company names merged in the set, and all the duplicate emails merged in the dictionary.

Now you can process your companies as a single query:

existing_companies = Company.objects.filter(name__in=companies)

That should be a single database call.

You'll want to compute the set of companies that are not in the existing_companies result set, and then bulk_create them:

new_companies = ...

Company.objects.bulk_create([Company(name=cn) for cn in new_companies])

That should be a single database call.

Finally, you have to deal with the users. You existing code doesn't seem to allow for changing jobs: if you have Fred.Flintstone@yahoo.com working at Slate Rock and Gravel, there's no way for him to change jobs to Spacely Sprockets. Trying to change the company associated with a visitor's email will result in an error. I don't know if that's because of what you're doing, or if it's an oversight. You'll have to make the call.

At any rate, you can do a similar thing with querying for email addresses already in the Person table, computing the set of emails not in the table, and doing a bulk_create on those records. (You'll want to create a dictionary to map company names to records, first, using the existing_companies results, plus maybe another query after the bulk create, or a rerun of the whole companies query.)

Again, that should be a single database call. But this depends on your underlying database. The Django docs warn that there are limits on SQLite, so you may have to do your bulk creates in batches.

Summary

I believe you can improve your database availability, and the script performance, by doing the following:

Read all the CSV records into memory (companies, visitors). Do some basic consistency checking during this part.
Make a single bulk query for existing companies.
Perform a single bulk create for new companies.
Refresh the companies query.
Perform a bulk query for existing visitors.
Perform a bulk create for new visitors.

That's potentially only 5 database calls.


Exception based on std::exception but easy to modify and rethrow I've looked at boost::exception and realized it is too advanced for my project, as my colleagues mostly have legacy C background. I do not need arbitrarily complex information in exception, just some error messages and trace info that can be written to process log.

Someone on Stack Overflow wrote such code as an example, but his solution can throw while trying to insert additional exception info (looks dangerous to me, correct me if I am wrong).

I tried to avoid using anything that can throw (vector of strings) inside the exception object. See: usage example.

Your feedback in term of correctness, ease of use, and required additional functionality is welcome.

const unsigned int long_enough = 512;
class my_exception : public exception {
    std::array<char, long_enough> err;
    std::array<char, long_enough>::iterator insertion_point;
public:
    template <typename Iter>
    void append(Iter first, Iter last) noexcept {
        //Remember null terminator!
        auto space_left = std::distance(insertion_point, err.end());
        if (std::distance(first, last)>=space_left){
            last = first + (space_left - 1);
        }
        insertion_point = copy(first, last, insertion_point);
    }
    void append(const char msg[]) noexcept {
        append(msg, msg+strlen(msg));
    }
    my_exception(const char msg[]) noexcept {
        insertion_point = err.begin();
        append(msg, msg+strlen(msg));
    }
    virtual const char* what() const noexcept override{
        return err.data();
    }
};

A note on the the link you posted; the OP was asking a hypothetical question in regards to what happens ('under the hood') to the call stack/exception/etc. if the exception that is caught is of a reference type (i.e. catch (std::exception& e) vs catch (const std::exception& e)). As was answered there, yes it is not a good idea to modify the exception within a catch (though completely legal code, still not advised).

Per your code, there are a couple of things worth noting:
changing your err type from a  std::array<char, long_enough> to a std::string would simplify all of your code, also, while you can pass a const char[] into functions, it decays into a pointer (pointing to the first element in the array), so it's similar to just const char*, if you're intent WAS to pass in a reference to a char[], it's recommended you pass a const size, as in template<int N> someFn(const char (&x)[N]), otherwise stack issues can occur. As well, if you're working with C++, unless you have a specific need to use a char[] (which is possible) it's advised to use a std::string over a char[].

Lastly, while having an append function to add aditional information into your exception object could be useful, it's usually better to derive a specific exception from your base exception with specific information in it (or otherwise just put the needed information in your throw exception...). Here's you're exception class with the err variable being a std::string

class my_exception : virtual public std::exception {
private:
    std::string err;
public:
    void append(std::string::iterator first, std::string::iterator last) {
        err.append(first, last);
    }
    void append(const char* msg) {
        err.append(msg);
    }
    my_exception(const char* msg) noexcept : err(msg) {}
    virtual const char* what() const throw() {
        return err.c_str();
    }
};

Use it like such:

try {
    throw my_exception("here's a simple message");
} catch (std::exception e) {
     e.append("...added some text");
     std::cout << "error: " << e.what() << std::endl;
     // or printf("error: %s\n", e.what()) for your C friends
}

As a side note (and for reference), here is the exception code from part of an open source framework I'm working on (just in a single header file exception.hpp):

#include <iostream>
#include <exception>
#include <string>

namespace your_namespace {
    class exception : virtual public std::exception {
        public:
            exception() throw() : m_what("general exception") {}
            exception(const char *reason) throw() : m_what(reason) {}
            exception(const std::string& reason) throw() : m_what(reason) {}
            virtual ~exception() throw() {}
            virtual const char* what() const throw() { return m_what.c_str(); }
            virtual void seterr(const char *err) { this->m_what = std::string(err); }
            virtual void seterr(const std::string &err) { this->m_what = err; }
            friend std::ostream& operator<<(std::ostream& s, const omni::exception& e)
            { s << e.m_what; return s; }
            friend std::basic_ostream<wchar_t>& operator<<(std::basic_ostream<wchar_t>& s, const omni::exception& e) {
                s << e.m_what.c_str();
                return s;
            }
        protected:
            std::string m_what;
    };

    class some_other_exception : public your_namespace::exception {
        public:
            some_other_exception() : exception("some other exception happened") {}

    };
}

To use:

try {
    throw your_namespace::exception();
} catch (std::exception e) { // or const std::exception&
    std::cout << "error: " << e << std::endl;
    // or printf("error: %s\n", e.what()) for your C friends
}

try {
    throw your_namespace::exception("Here's an exception for you");
} catch (std::exception e) {
    std::cout << "error: " << e << std::endl;
}

try {
    throw your_namespace::some_other_exception();
} catch (std::exception e) {
    std::cout << "error: " << e << std::endl;
}

I hope that can help


Async Check for Domain Fullname With WPF and Caliburn.Micro I have a small WPF program built using Caliburn.Micro which checks Active Directory for a user with the current username of the logged-on user. I have a Bootstrapper method:

protected async override void OnStartup(object sender, StartupEventArgs e)
{
    await ShellViewModel.CollectFullnameAsync();
    DisplayRootViewFor<ShellViewModel>();
}

This starts the ShellViewModel and kicks off an async method to start looking for the currently logged on user on the domain

My ShellViewModel looks like this:

public ShellViewModel()
{
    Computername = EnvironmentHelpers.ComputerName;
    Fullname = _fullnameplaceholder;
}

public static async Task CollectFullnameAsync()
{
    _fullnameplaceholder = ADHelpers.GetFullADName();

    while(_fullnameplaceholder == "Failed" && _attemptsToCollectFullName < 5)
    {
        _attemptsToCollectFullName++;
        await Task.Delay(2000);
        _fullnameplaceholder = ADHelpers.GetFullADName();
    }
}

So my code is meant to:

Look for the user on the domain
Check 5 times for the user, waiting 2 seconds between each attempt.
Display the ShellView with either "Failed" or the Fullname returned from the domain

Can I please get some insight into how I am performing this task? Is this the correct way to do this or am I barking up the wrong tree?

I'll start off by saying I don't have Caliburn.Micro experience but do have other MVVM experience.

I'm going to assume the ShellView is the shell for your entire application.  I don't know what other code that is running but I can tell you as a user I would not want to fire off your application and wait for over 10 seconds, because we are waiting for 10 seconds plus the time it takes for the other calls to come back, to be able to use the application.  Worst yet is even if the screen hasn't shown.  Then I'm likely to fire it off multiple times thinking it stuck or I didn't double click it.

In general it's not best practice to do async void, so I would question why Task.Delay instead of Thread.Sleep since the delay is the only async code.

If we are leaving it as async it should be wrapped in a try/catch otherwise if there is an exception you will need to handle it in Application.DispatcherUnhandledException or AppDomain.UnhandledException.  Which brings up a point if there is an exception I assume you want just Failed as the user name?

Now to a different idea.  You could remove this from startup, or try once to get it in startup,  Then setup a timer to recheck if it failed.  The application state could be based on if it has a name yet or not.  For Example:  The user can start entering data but can't save it until we retrieved the AD user.

If just want to wait until there is user name or not it still better to give the user an idea what's going on so they can see the application isn't just hung and that's it's checking network activity.  Create an initial view of just gather application information and part of that is gathering network user information.


Laravel Single Page Application Using Angular Js I have created a Laravel Single Page Application using Angular Js 1.3.14 by learning tutorials in the websites.

index.php:

         Company Name

Home

About Us

web.php:

Route::get('/', function () {
   return view('welcome');
});
Route::get('/home', function () {
   return view('home');
});
Route::get('/aboutus', function () {
    return view('aboutus');
});
Route::get('getusers', 'UserController@users');

UserController.php:

class UserController extends Controller
{
    public function users(Request $request)
    {
        $users = DB::table('users')->get();
        return response()->json($users);
    }
}

aboutus.blade.php:

      Id
      Name
      Email
      Created At

      @{{ data.id }}
      @{{ data.name }}
      @{{ data.email }}
      @{{ data.created_at }}

controller.js:

 var mainApp = angular.module("mainApp", ['ngRoute']);
 mainApp.config(['$routeProvider', function($routeProvider) {
    $routeProvider.

    when('/home', {
       templateUrl: '/home',
    }).

    when('/aboutus', {
       templateUrl: '/aboutus',
       controller: 'AddStudentController'
    }).

    when('/services', {
       templateUrl: '/services',
    }).
 }]);

  mainApp.controller('AddStudentController', function($scope, $http) {
    $http.get('getusers').then( function(response) {
      $scope.datas = response.data;
    });
  });

The SPA which i have created working correctly, i have developed this project of my own. Is there any thing i want to change or any mistake in routing or any thing in this project.

This code seems okay for the most part - I don't see any major flaws with the code, just a few things that I will critique below.

Despite being spread across quite a few files, this code seems pretty simple. Not that it is by any means wrong, but it is a bit unique to see AngularJS code paired with Laravel code.

  While Laravel does not dictate which JavaScript or CSS pre-processors you use, it does provide a basic starting point using Bootstrap and Vue that will be helpful for many applications.1

The biggest thing I would critique is the lack of request failure handling. While it may be very unlikely that the AJAX requests to get the list of users would fail, due to the simplicity of the controller method and the fact that if that fails it might also be the case that the page wouldn't have loaded in the first place, it is wise to handle such cases gracefully. Typically when calling .then() on a Promise, the second argument should be supplied for the case when the promise is rejected.

$http.get('getusers').then( function(response) {
  $scope.datas = response.data;
},
function(rejectionReason) {
  //handle case when request fails here
});

Or instead of passing the rejection handler as a second argument, it could be passed in a subsequent call to .catch()

Other than that, I would bring up the naming of $scope.datas in the controller:

$http.get('getusers').then( function(response) {
  $scope.datas = response.data;
});

datas is a very generic term. Somebody reading that response could think "After getting the response from getusers, Do we need to abstract the users from response.data? A more appropriate name might just be users:

$http.get('getusers').then( function(response) {
  $scope.users = response.data;
});

Then the markup can be updated accordingly:

   @{{ user.id }}
   @{{ user.name }}
   @{{ user.email }}
   @{{ user.created_at }}

Other than that, I would suggest conditionally showing the table - only if there are entries in the data array. For that, ng-if and/or ng-show can be used. See the snippet below for an example

var mainApp = angular.module("mainApp", []);
mainApp.controller('AddStudentController', function($scope, $http) {
  $scope.requestSent = false;
  updateUsers = function() {
    $http.get('https://jsonplaceholder.typicode.com/users').then(function(response) {
      $scope.users = response.data;
    }, function(rejectionReason) {
      //display error message?
      $scope.error = rejectionReason;
    })
    .finally(function() {
      $scope.requestSent = true;
    });
  };
  setTimeout(updateUsers, 2000); //wait 2 seconds to simulate network latency
});

         Company Name

Home

About Us

          Id
          Name
          Email
          Created At

          @{{ user.id }}
          @{{ user.name }}
          @{{ user.email }}
          @{{ user.created_at }}

1https://laravel.com/docs/5.7/frontend


Scrolling game very slow I am trying to make a scrolling game in Tkinter. However, with all my for loops and functions it is extremely slow.

I am reading the tutorial from Khan Academy's advanced JS. In their JS game everything is fine, so is it just a problem of python is slow or am I doing things inefficiently.

import tkinter as tk
import random
import time
win = tk.Tk()
win.title("Beaver Game")
win.wm_attributes("-topmost", 1)#Makes it stay on top of other windows
canvas = tk.Canvas(win, width=300, height=300, bg='#97FEFF', bd = 0, highlightthickness = 0)
canvas.pack()
canvas.create_rectangle(0, 270,300, 300, fill = "brown")
win.update()

class Beaver:
    def __init__(self, canvas, color):
        self.canvas = canvas
        self.id = self.canvas.create_rectangle(150,150, 100, 100, fill = color)
        self.y = 0
        self.canvas_height = self.canvas.winfo_height()
        self.canvas_width = self.canvas.winfo_width()
        self.canvas.bind_all('<KeyPress-Up>', self.turn_left)
        self.canvas.bind_all('<KeyPress-Down>', self.turn_right)
        self.sticks = 0
    def draw(self):
        self.canvas.move(self.id, 0, self.y)
        pos = self.canvas.coords(self.id)
        if pos[1] <= 0:
            self.y = 0
        if pos[3] >= self.canvas_height:
            self.y = 0
    def turn_left(self, evt):
        self.y = -3
    def turn_right(self,evt):
        self.y = 3
class Stick:
    def __init__(self, canvas, color, x, y):
        self.canvas = canvas
        self.color = color
        self.x = x
        self.y = y
    def draw(self):
        canvas.create_rectangle(self.x, self.y, 5, 40, fill = self.color)
beaver = Beaver(canvas, "pink")

grassXs = []
for i in range(25):
     grassXs.append(i * 25)

sticks = []
for i in range(40):
    sticks.append(Stick(canvas, "black", i * 4 + 100, random.randint(20, 26)))

while 1:
   for i in range(len(grassXs)):
      canvas.create_rectangle(grassXs[i], 250, 270, 270, fill = "green")
      grassXs[i] -= 1
      if (grassXs[i] <= -20):
         grassXs[i] = canvas.winfo_width()
   for i in range(len(sticks)):
       sticks[i].draw()
       sticks[i].x -= 1
   beaver.draw()
   win.update_idletasks()
   win.update()

You are doing animation wrong. As a rule of thumb you shouldn't have your own infinite loop in a Tkinter program. Tkinter already has an efficient infinite loop — the mainloop function.

Here are a few Stack Overflow questions dealing with Tkinter animation:

simple animation using tkinter
Moving balls in Tkinter Canvas
Python Tkinter wireworld animation slowing down over time

I will say that the canvas has performance issues when there are hundreds of thousands of objects on the canvas, and it may start appearing when there are tens of thousands.

In your case, by my estimation you're creating a couple thousand canvas objects per second, and that's just way too many to expect good performance. Considering you're making a side-scroller, you simply don't need to create all those objects every second.


Using Data.Array to solve Sierpinski in Haskell Here is an earlier attempt to solve the original problem:
Solving Sierpinski Triangle in Haskell

I was never satisfied with my solution and found it was awkward and twisty. Here is another attempt to solve the same problem using Data.Array and I found that by using mutable arrays the solution becomes much shorter and easy to read.

import qualified Data.Array as DA (Array, listArray, (//), assocs)
import qualified Data.List as DL (groupBy, intercalate)
import qualified Data.Function as DF (on)

type Point = (Int, Int)
data Triangle = Triangle { up :: Point, height :: Int } deriving Show
type Canvas = DA.Array Point Char

emptyCanvas maxLevel = DA.listArray ((0, 1-h), (h-1, h-1)) $ repeat '_'
  where
    h = 2^maxLevel -- 1*(2^maxLevel)

drawTriangle :: Triangle -> Canvas -> Canvas
drawTriangle (Triangle (r, c) h) canvas = foldr drawLine canvas $ map line [1..h]
  where
    line h = let h' = h-1 in [(r+h', j) | j <- [c-h'..c+h']]
    drawLine l c = c DA.// map (\p -> (p, '1')) l

drawCanvas :: Canvas -> IO ()
drawCanvas canvas = putStrLn pic
  where
    rows = DL.groupBy ((==) `DF.on` (fst . fst)) . DA.assocs
    pic = DL.intercalate "\n" $ map (map snd) (rows canvas)

split hLvl (r, c) = let w = 2^(hLvl-1) in [(r, c), (r+w, c-w), (r+w, c+w)]

splitSier maxLevel (sierLevel, ts) = (sierLevel+1, ts')
  where
    ts' = ts >>= (split (maxLevel-sierLevel))

mkSierpinski :: Int -> Int -> Canvas
mkSierpinski maxLevel sierLevel
  | maxLevel >= sierLevel = foldr drawTriangle c $ allTriangles
  | otherwise = c
  where
    c = emptyCanvas maxLevel
    (l', ts') = head $ drop sierLevel $ iterate (splitSier maxLevel) (0, [(0, 0)])
    allTriangles = map (\p -> Triangle p (2^(maxLevel-l'))) ts'

main = do
    sierLevel <- readLn
    drawCanvas $ mkSierpinski 5 sierLevel

The idea is to model the canvas by a 2-D array of Characters and attempt to draw easy individual triangles on top of the empty canvas. In this solution it starts with one big triangle and keep splitting to generate Sierpinski pattern. Another solution that I didn't post here attempts to solve it by starting with the smallest triangle at the top, and repeatedly copy what is current on canvas to its lower left corner and lower right corner. Both solutions look very similar at the end.

Please let me know if you have suggestions. Thank you in advance.

// is best called with one bulk list because each call incurs one O(n) array copy.

Folds over iterates when you need an index and know its range, it's like for vs. while.

drawCanvas :: Canvas -> IO ()
drawCanvas = putStrLn . unlines . map (map snd)
  . DL.groupBy ((==) `DF.on` fst . fst) . DA.assocs

mkSierpinski :: Int -> Int -> Canvas
mkSierpinski maxLevel sierLevel = emptyCanvas maxLevel DA.//
  [ ((r+h, j), '1')
  | maxLevel >= sierLevel
  , (r, c) <- DF.foldrM split (0, 0) [maxLevel-sierLevel+1..maxLevel]
  , h <- [0..2^(maxLevel-sierLevel)-1]
  , j <- [c-h..c+h]
  ]


Decimal to binary transformation in c Input:
    Enter a decimal number: 101

Output:
    The binary number is : 1100101

I have solved this way->
#include <stdio.h>
int main(void){

int input=get_input();
long long complete_integer=binary_conversion(input);
reverse_digits(complete_integer);
}
int get_input() {
int number = 0;
printf("Enter a decimal number: ");
scanf("%d",&number);
return number;
}
int binary_conversion(int number) {
long long complete_integer = 0;
int base=2;

while (number != 0) {
//Take the last digit from the integer and push the digit back of complete integer
complete_integer = complete_integer * 10 + number%base;
number /= base;
}
printf("Completed integer number : %d\n",complete_integer);
return complete_integer;
}

int reverse_digits(long long complete_integer) {
    int binary = complete_integer;
    int last_digit = 0;

    while(binary != 0) {

        last_digit = last_digit * 10 + binary % 10;
        binary /= 10;
    }
    printf("The binary number is: %d",last_digit);
}

I am here for: What about my comments and indentations? Will I face any problem for some conditions? Would you propose a better simplification by using my program?

There is no indentation except in the function revers_digits(). The indentation within that function is fine, you should correct the rest of the program because it is basically unreadable.
While this may compile in a free online compiler, the code is broken for 2 reasons. The first is that in a one file program such as this one for the C programming language main() should be the last function in the file so that all of the other functions are defined previously. There is a workaround for this using function prototypes.
The second reason the code is broken is that binary_conversion(int number,int value) is declared with 2 variables, but is only called with one (remove value since it doesn't seem to be necessary).


Mutual conversion operators What is more readable? value / 60 / 60, value / 3600, or Hours{static_cast<Minutes>(*this).value / 60}? Should I use constants, i.e. SECONDS_IN_HOURS.
Should I use the explicit keyword? Would it actually prevent stupid mistakes/silent bugs? Or would it become annoying to have to cast everything?
It is easy to "glaze" over the following code and miss mistakes (for example, mixing up multiplication and dividing, using 24 instead of 60 when converting hours to minutes). How should it be refactored? I'm not sure if toSeconds, toMinutes is better than Second::operator Minutes() in terms of clarity.
What happens if I add days, and then weeks, and so on? It would require duplicating code and keeping track of what I have already and haven't already implemented. This is basically an extension to number 3 in terms of refactoring: how should I define them in terms of the other to avoid duplication?

#include <iostream>

struct Seconds;
struct Minutes;
struct Hours;
struct Seconds
{
    int value;
    operator Minutes() const;
    operator Hours() const;
};
struct Minutes
{
    int value;
    operator Seconds() const;
    operator Hours() const;
};
struct Hours
{
    int value;
    operator Minutes() const;
    operator Seconds() const;
};
Seconds::operator Minutes() const
{
    return Minutes{value / 60};
}
Seconds::operator Hours() const
{
    return Hours{static_cast<Minutes>(*this).value / 60};
}
Minutes::operator Seconds() const
{
    return Seconds{value * 60};
}
Minutes::operator Hours() const
{
    return Hours{value / 60};
}
Hours::operator Minutes() const
{
    return Minutes{value * 60};
}
Hours::operator Seconds() const
{
    return Seconds{static_cast<Minutes>(*this).value * 60};
}

int main()
{
    Minutes m{60};
    Seconds s{3600};
    Hours h{1};
    std::cout << (static_cast<Seconds>(m).value == s.value);
    std::cout << (static_cast<Seconds>(h).value == s.value);
    std::cout << (static_cast<Minutes>(s).value == m.value);
    std::cout << (static_cast<Minutes>(h).value == m.value);
    std::cout << (static_cast<Hours>(s).value == h.value);
    std::cout << (static_cast<Hours>(m).value == h.value);
    return 0;
}

What you done looks good but I am wondering if it is not a bit over-engineered.

Here's what I would have done (which is probably under-engineered) :

#include <iostream>

enum TimeUnit
{
    Second = 1,
    Minute = Second*60,
    Hour   = Minute*60,
    Day    = Hour*24,
    Week   = Day*7
};

class Time
{
    public:
        Time(int n = 0, TimeUnit unit = Second) :
            value(n*unit) {};

        bool operator==(const Time& other) const {
            return (value==other.value);
        }

        int convert(TimeUnit unit = Second) const { return value/unit; }

    private:
        const int value; // Assumed to be in seconds.
};

int main()
{
    Time s0;
    Time h0(0,Hour);
    std::cout << (s0 == h0);

    Time s3600(3600);
    Time s3600bis(3600, Second);
    Time m60(60, Minute);
    Time h1(1, Hour);
    std::cout << (s3600 == s3600bis && s3600bis == m60 && m60 == h1);

    return 0;
}

My point is to just take into account the fact that a time is just a value and a unit. We store the value in the easiest format and we convert it on demand. No conversion is actually required for comparison. Adding a new Unit is straightforward (assuming there is a constant factor to multiply - month and year wouldn't work because they do not always last the same time).


Leetcode: Flatten binary tree to linked list C# https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Please comment on performance

  Given a binary tree, flatten it to a linked list in-place.

  For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

  The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace LinkedListQuestions
{
    [TestClass]
    public class FlattenBinaryTree2LinkedList
    {
        [TestMethod]
        public void FlattenBinaryTree2LinkedListTest()
        {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(5);
            root.left.left = new TreeNode(3);
            root.left.right = new TreeNode(4);
            root.right.right = new TreeNode(6);
            Flatten(root);
            Assert.AreEqual(1, root.data);
            Assert.AreEqual(2, root.right.data);
            Assert.AreEqual(3, root.right.right.data);
            Assert.AreEqual(4, root.right.right.right.data);
            Assert.AreEqual(5, root.right.right.right.right.data);
            Assert.AreEqual(6, root.right.right.right.right.right.data);

        }
        public void Flatten(TreeNode root)
        {
            if (root == null || (root.left == null && root.right == null))
            {
                return;
            }
            Stack<TreeNode> stack = new Stack<TreeNode>();
            var head = root;
            stack.Push(root);
            while (stack.Count > 0)
            {
                var curr = stack.Pop();
                if (curr != root) // in the first iteration, we don't want to move the head to the next item
                {
                    head.right = curr;
                    head = curr;
                }
                if (curr.right != null)
                {
                    stack.Push(curr.right);
                    curr.right = null;
                }
                if (curr.left != null)
                {
                    stack.Push(curr.left);
                    curr.left = null;
                }
            }
        }
    }
}

The first condition is a bit conservative:

if (root == null || (root.left == null && root.right == null))

Just if (root == null) would be enough, the rest of the implementation naturally handles the cases of root.left == null && root.right == null.

Evaluating curr != root for every node, when it's only useful for the first node is a bit ugly.
You could get rid of that by not adding root itself on the stack, but its children. (In the right order, and when not null.)

head is a misleading name for a variable that traverses all the nodes,
especially since the end result is effectively a linked list,
where "head" usually means the first element.
I'd rename this to node.

All the curr.right = null; can be safely dropped,
because curr.right will either get overwritten with the intended value,
or it's null to begin with (in the very last node).

An \$O(n)\$ solution exists without using a stack:

When left is null and right is not, advance over right
When right is null and left is not, move left to right and advance over right
When both not null of node, then:

traverse through all the right descendants of node.left, and append at the end node.right
move node.left to node.right and advance over it


Single word CAS tagged pointer for algorithms susceptible to the ABA problem I've been looking for a solution to the ABA problem for a lock-free stack. Searching the Web revealed patented and complicated hazard pointers and tagged pointers using double compare-and-swap (DCAS, CAS2). I would settle for the DCAS, but it's not available on some older AMD CPUs. So I came up with this helper class:

class TaggedPtrBase {
    typedef unsigned int tag_t;
    static const tag_t INVALIDATED = 1;
public:
    TaggedPtrBase() {
        tag.store(0, std::memory_order_relaxed);
        ptr = 0;
    }
    TaggedPtrBase & operator=(const TaggedPtrBase & other) {
        tag.store(other.tag.load(std::memory_order_acquire), std::memory_order_relaxed);
        ptr = other.ptr;
        return *this;
    }
    operator void *() const {
        return get();
    }
    void * get() const {
        return ptr;
    }
    bool compare_and_swap(const TaggedPtrBase & oldval, void * newptr) {
        uintptr_t old_tag = oldval.tag.load(std::memory_order_relaxed);
        if (old_tag & INVALIDATED) {
            return false;
        }
        if (tag.compare_exchange_strong(old_tag, old_tag | INVALIDATED, std::memory_order_acquire)) {
            ptr = newptr;
            tag.store(old_tag + 2, std::memory_order_release);
            return true;
        } else {
            return false;
        }
    }
private:
    std::atomic<tag_t> tag;
    void * ptr;
};
...
void push(Node * node) {
    void * newptr = reinterpret_cast<void *>(node);
    TaggedPtrBase old;
    do {
        old = ptr;
        node->next = static_cast<Node *>(old.get());
    } while (!ptr.compare_and_swap(old, newptr));
}

It appears to be working, but it's simplicity suggests that I'm missing something.
So I wonder if this is a proper solution, or is it just a glorified spin-lock? Any issues on non-x86 platforms?

It's just a spin lock. If the thread that invalidated of the tag got suspended right after, no other thread can make progress till the thread is resumed and releases the tag.

if (old_tag & INVALIDATED) {
    return false; // no thread can go further if ...
}
if (tag.compare_exchange_strong(old_tag, old_tag | INVALIDATED,
                                std::memory_order_acquire)) {
    ptr = newptr; // <-- ... a thread is preempted here
    tag.store(old_tag + 2, std::memory_order_release);
    return true;
}

So the solution is not lock-free.


Best way convert byte array to hex string Is it possible to write this method in a prettier way?

public static string ByteArrayToString(byte[] byteArray)
{
  var hex = new StringBuilder(byteArray.Length * 2);
  foreach (var b in byteArray)
    hex.AppendFormat("{0:x2}", b);
  return hex.ToString();
}

There are popular topics on StackOverflow that cover this exact question:

How do you convert Byte Array to Hexadecimal String, and vice versa?
byte[] to hex string


LockGuard for MFC CMutex I upgrade an old MFC multi-threaded C++ project (from year 2002) to VS2017 Windows 10 x64. I rewrote the mutex sections (MFC's CMutex m_mu). I preferred, of course, to use C++11 std::mutex m_mutex and std::lock_guard<std::mutex> guard(m_mutex) but it throws an exception. I decided to add my own CLockGuard class (code below).

Example: (m_mutex is a protected MFC CMutex member of CMonitorsManager)

void CMonitorsManager::OnMonitorLoginMessageArrive
                        (CMonitorLoginMessage* pMessage)
{
    CLockGuard LockGuard(&m_mutex);

    m_MonitorId2IPMap.SetAt(pMessage->GetDeviceAddress(),
                            pMessage->GetPeerAddress());
};

LockGuard.h file:

#pragma once

#include <afxmt.h>//for CMutex

class CLockGuard
{
public:
    CLockGuard(CMutex* rMutex);
    ~CLockGuard();

    void Unlock();

protected:
    CMutex* m_pMutex = nullptr;
};

LockGuard.cpp file:

#include "stdafx.h"
#include "LockGuard.h"

CLockGuard::CLockGuard(CMutex* pMutex)
{
    pMutex->Lock();

    m_pMutex = pMutex;
}

void CLockGuard::Unlock()
{
    m_pMutex->Unlock();
    m_pMutex = nullptr;
}

CLockGuard::~CLockGuard()
{
    if (m_pMutex)
        m_pMutex->Unlock();
}

Instead of writing your own lock_guard-like object specifically to use with a CMutex, I'd write a wrapper for CMutex to give it the Lockable interface, then just use it with a normal std::lock_guard:

namespace mfc {
class mutex {
    CMutex m;
public:
    mutex(BOOL bInitiallyOwn = FALSE,
          LPCTSTR lpszName = NULL,
          LPSECURITY_ATTRIBUTES lpsaAttribute = NULL)
        : m(bInitiallyOwn, lpszName, lpsaAttribute)
    {}

    void lock() { m.Lock(); }
    void unlock() { m.Unlock(); }
};

Then you can just lock it like you would an std:mutex:

// Define the mutex
mfc::mutex m;

void foo() {
    std::lock_guard<mfc::mutex> L(m);
    // use whatever m is protecting
}

You may not even need that though. You may have run into the fact that a Windows-native mutex is always a recursive mutex, and a std::mutex is not. If you replace it with std::recursive_mutex instead of std::mutex, it may work just fine (or depending on how you do your locking, you may need a recursive_timed_mutex).


Maximum sub-array of non-negative numbers This is the "Maximum sub-array" problem from CodeChef:

  Find out the maximum sub-array of non negative numbers from an
  array.

  The sub-array should be continuous. That is, a sub-array
  created by choosing the second and fourth element and skipping the
  third element is invalid.

  Maximum sub-array is defined in terms of the
  sum of the elements in the sub-array. Sub-array A is greater than
  sub-array B if sum(A) > sum(B).

  NOTE 1: If there is a tie then compare the segment length's and return
  segment which has maximum length.

  NOTE 2: If there is still a tie, then return the segment with minimum starting index.

This is my solution:

def maxset(array):
    """Returns maximum sub array of non-negative numbers"""
    max_sum = 0
    current_sum = 0
    start = 0
    stop = 0
    max_array = array[0]
    for i in range(len(array)):
        if array[i] >= 0:

            current_sum +=  array[i]
            stop += 1

            if max_sum < current_sum:
                max_sum = current_sum
                if max_array < array[start:stop]:
                    max_array = array[start:stop]

            elif max_sum == current_sum:
                if len(max_array)< len(array[start:stop]):
                    max_array = array[start:stop]

        else :

            start = i+1
            stop = start
            current_sum = 0

    return max_array

Test cases :

def main():
    print maxset( [ 1, 2, 5, -7, 2, 5 ] )
    print maxset( [ 1,-1, 1, -1, 1, -1])
    print maxset( [ 1, 2, 5, 7, 2, 5 ] )
    print maxset( [ 222])
    print maxset( [ 1, 1])
    print maxset( [  3, -1, 1, 1, 1, -1, 3])
    print maxset( [ 5, -1, 1, 1, 1, 1, -1, 5 ])
    print maxset([ 3, -1, 1, 1, 1, -1, 2 ])
    print maxset([ 3,-3, -1, 1, 1, 1, -1, 2 ])
if __name__ == '__main__':
    main()

How can I improve this code ?

1. Bugs

maxset returns the wrong answer for some inputs. For example:

>>> maxset([2, 1, -1, 1, 3])
[2, 1]

The correct answer is [1, 3]. The cause of this bug is the line:

if max_array < array[start:stop]:

which causes the sub-array with the higher sum (here, [1, 3]) to be ignored because it lexicographically precedes max_array (here, [2, 1]).
maxset goes wrong when all the elements of the input are negative:

>>> maxset([-1, -2])
-1

The number -1 is not a valid result: it's not the maximum sub-array, it's just a number.

It also goes wrong when the input is empty:

>>> maxset([])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr193902.py", line 7, in maxset
    max_array = array[0]
IndexError: list index out of range

To fix these two problems, instead of this initialization:

max_array = array[0]

start with an empty list:

max_array = []

2. Review

The code in the post uses the print statement and so only runs on Python 2.7. But support for Python 2.7 is scheduled to end in 2020. It is long past the time when it was a good idea to start writing new projects in Python 2.7. If you really can't use Python 3 then use:

from __future__ import print_function

so that your code is portable to Python 3.
The name maxset is misleading since it does not return a set.
When you take a slice of a list, for example array[start:stop], Python has to copy out all the elements of the slice in order to construct a new list. This is a waste unless you are actually going to need the new list. So instead of:

len(array[start:stop])

(which creates a list and then throws it away again) you could write:

stop - start

This line copies out a slice of the list each time you find a new maximum sub-array:

max_array = array[start:stop]

but in many cases you are never going to need this list, because later on you will find an even bigger sub-array. So instead of copying out a slice, you could remember the location of the maximum sub-array found so far:

max_start = start
max_stop = stop

and at the end of the function

return array[max_start:max_stop]

The code has a loop over the indexes into array:

for i in range(len(array)):

and then within the loop it looks up the element at that index using array[i]. Whenever you see this pattern, you can simplify it using the built-in function enumerate. In this case the loop becomes:

for i, element in enumerate(array):

and wherever you had array[i] you now have element.
The two branches of the if: ... elif: ... both have the line:

max_array = array[start:stop]

This duplication could be avoided by combining the two conditions into one:

if (max_sum < current_sum
    or (max_sum == current_sum
        and max_stop - max_start < stop - start)):

and this can be further simplified by comparing tuples:

if (max_sum, max_stop - max_start) < (current_sum, stop - start):

There's no need to maintain a running variable stop since it always has the value i + 1.
The test cases don't check the results. When I run it, I get the output:

>>> main()
[1, 2, 5]
[1]
[1, 2, 5, 7, 2, 5]
[222]
[1, 1]
[1, 1, 1]
[5]
[1, 1, 1]
[1, 1, 1]

Is this right? The usual way to write a test case is to raise an exception if the result is incorrect. There are various ways to do this. You could use the assert statement and write:

assert maxset([ 1, 2, 5, -7, 2, 5 ]) == [1, 2, 5]

or you could use the unittest module from the Python standard library.

3. Revised code

def max_sub_array(array):
    """Return maximum sub-array of non-negative numbers."""

    start = 0                   # Start of current sub-array
    current_sum = 0             # Sum of current sub-array
    max_start = 0               # Start of maximum sub-array
    max_stop = 0                # Stop of maximum sub-array
    max_sum = 0                 # Sum of maxium sub-array

    for stop, element in enumerate(array, start=1):
        if element >= 0:
            current_sum += element
            if (max_sum, max_stop - max_start) < (current_sum, stop - start):
                max_sum = current_sum
                max_start = start
                max_stop = stop
        else:
            start = stop
            current_sum = 0

    return array[max_start:max_stop]

import unittest

class TestMaxSubArray(unittest.TestCase):
    CASES = [
        # array, expected result
        ([], []),
        ([-1, -2], []),
        ([2, 1, -1, 1, 3], [1, 3]),
        ([1, 2, 5, -7, 2, 5], [1, 2, 5]),
        ([1,-1, 1, -1, 1, -1], [1]),
        ([1, 2, 5, 7, 2, 5] , [1, 2, 5, 7, 2, 5]),
        ([222], [222]),
        ([1, 1], [1, 1]),
        ([3, -1, 1, 1, 1, -1, 3], [1, 1, 1]),
        ([5, -1, 1, 1, 1, 1, -1, 5], [5]),
        ([3, -1, 1, 1, 1, -1, 2], [1, 1, 1]),
        ([3, -3, -1, 1, 1, 1, -1, 2], [1, 1, 1]),
    ]

    def test_max_sub_array(self):
        for array, expected in self.CASES:
            self.assertEqual(expected, max_sub_array(array))

4. A different approach

The single responsibility principle say that each piece of code should do just one thing. By splitting code into pieces with single responsibilities, the individual pieces become easier to understand, check and test.

So for this problem we could split the code into two parts:

find all the sub-arrays of non-negative numbers in array;
find the maximum sub-array in the results of step 1.

For part 1 the Python standard library has a useful function itertools.groupby for splitting an iterable into groups based on a key function. In this case the key function needs to be "is the element non-negative". Then for part 2 we can use the built-in max function, again using a key function.

from itertools import groupby

def max_sub_array(array):
    """Return maximum sub-array of non-negative numbers."""
    sub_arrays = [list(group)
                  for non_negative, group in groupby(array, lambda e: e >= 0)
                  if non_negative]
    if sub_arrays:
        return max(sub_arrays, key=lambda a: (sum(a), len(a)))
    else:
        return []

In Python 3.4 or later, max has a default keyword argument to handle the case where there are no items, and so we can combine this into a single expression:

from itertools import groupby

def max_sub_array(array):
    """Return maximum sub-array of non-negative numbers."""
    return max((list(group)
                for non_negative, group in groupby(array, lambda e: e >= 0)
                if non_negative),
               key=lambda a: (sum(a), len(a)),
               default=[])


Iterative depth first search using adjacency matrix I have written code for graph traversal using adjacency matrices in an iterative approach. The code should print the graph in a DFS way.

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int c[n][n];
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            cin>>c[i][j];
        }
    }
    int dfs[n];
    for(i=0;i<n;i++){
        dfs[i]=-1;
    }
    dfs[0]=1;
    j=1;
    for(i=0;i<n;i++){
        if(dfs[i]==1&&i>j)
        cout<<i;
        dfs[i]=1;
        while(c[i][j]!=0&&j<n&&i<n){
            if(dfs[j]==-1)
            {
                dfs[j]=1;
            }
            if(dfs[j]==1){
                cout<<j;
                j++;
            }
        }
    }
}

Is my code correct? If not, correct me. Can we decrease time complexity?

It's nearly impossible to tell what your code does because:

The variable names are meaningless
There are no prompts for the user to tell them what the inputs mean
The output appears to just be a string of numbers with no apparent meaning

I can't tell you if it's correct or not (which is beyond the scope of Code Review anyway) because I can't tell what it's trying to do. In terms of trying to improve your code, I recommend changing the variable names from single letters or cryptic acronyms to full words, such as adjacencyMatrix and traversalList, or whatever they actually represent.

I recommend outputting some strings to tell the user what to input. Alternately, if this code is supposed to read its input from a file, then you should write code to read from a file instead of assuming it will come from standard in.

Finally, your output should say what it's outputting and have some sort of separators between the values, such as commas, spaces, or line endings. Again, if it's meant to be outputting to a file, then you should write code to write to a file rather than standard out.


Roman numerals to decimal This is a program for converting Roman numerals to their decimal equivalents. There must be a better way of distinguishing between, for example, 'IV' and 'VI', than what I have currently written.

#include <iostream>
#include <string>
using namespace std;

class romanType{
public:
    romanType();
    romanType(string s);
    ~romanType();

        void setRoman(string); //Set the Roman numeral from user entries.
        int romanToDecimal(); //Convert the Roman numeral(string) to Decimal value.
        void printDecimal(); //Display the decimal value.
        void printRoman(); //Display the Roman numeral value.
private:
    string romanNum;
    int decimalNum = 0;

};

romanType::romanType()
{
    romanNum = 1;
}

romanType::~romanType()
{
}

void romanType::setRoman(string troll)
{
    romanNum = troll;
}

int romanType::romanToDecimal()
{
    for (int i = 0; i < romanNum.length(); i++)
    {
        if (romanNum[i] == 'I')
            decimalNum++;
        if (romanNum[i] == 'V')
        {
            if (i > 0 && romanNum[i - 1] == 'I')
                decimalNum -= 2;
            decimalNum += 5;
        }
        if (romanNum[i] == 'X')
        {
            if (i > 0 && romanNum[i - 1] == 'I')
                decimalNum -= 2;
            decimalNum += 10;
        }
        if (romanNum[i] == 'L')
        {
            if (i > 0 && romanNum[i - 1] == 'X')
                decimalNum -= 20;
            decimalNum += 50;
        }
    }
    cout << decimalNum << endl;
    return decimalNum;
}

int main()
{
    string numerals;
    do{
        cout << "Enter roman numerals: ";
        cin >> numerals;

        romanType Rom;
        Rom.setRoman(numerals);
        Rom.romanToDecimal();

    } while (true);
    system("PAUSE");

}

Sample output:

Enter roman numerals: IX
9
Enter roman numerals: XI
11
Enter roman numerals: XIX
19
Enter roman numerals: XX
20
Enter roman numerals: LVIII
58
Enter roman numerals: LXXXVIII
88
Enter roman numerals: LXVI
66
Enter roman numerals: LXIV
64
Enter roman numerals:

Try not to use using namespace std and system("PAUSE").

The former is okay for shorter programs or toy programs, or when used in local scope as opposed to global (such as within a function).

The latter is best avoided as it is problematic while safer and more portable alternatives are in existence, such as std::cin.get().  It's also non-portable and only works with Windows.
In certain environments (or depending on personal preference), new user-defined types should be capitalized and objects should be lowercase.

NewType objOfNewType;

Prefer an initializer list here:

NewType::NewType() : dataMember1(/* value */) {}

Although this may not make a huge difference in your code, it's still good to know about it when writing larger programs.  It is best when initializing objects (especially when the arguments are of the same name) and necessary when initializing constants.
As you're not using the destructor, you can leave it out.  The compiler will make one for you that does any of the default cleanup.
You shouldn't do this in the class declaration:

int decimalNum = 0;

You should instead put that into the initializer list as mentioned above:

// entries are separated by commas
// can also be listed on separate lines
className::className() : member1(0), member2(0) {}

You have declared printRoman(), but have not defined it.  Better yet, overload operator<< for your class and leave out that empty declaration.

Declare in header:

friend std::ostream& operator<<(std::ostream&, Class const&);

Define in source:

std::ostream& operator<<(std::ostream& out, Type const& obj)
{
    return out << obj.typeMember;
}

Print it out:

NewType objOfNewType;
std::cout << objOfNewType;

int is not a good loop counter type here:

for (int i = 0; i < romanNum.length(); i++) {}

romanNum is of type std::string, so you should use std::string::size_type.  This will ensure that you can loop through any string size while not being limited by int's size.

Better yet, use its iterators instead (using a range-based for-loop in C++11):

for (auto& iter : romanNum)
{
    if (iter == 'I')
        decimalNum++;
}

Another alternative (if you don't have C++11 and cannot use the above):

for (std::string::iterator = romanNum.begin(); iter != romanNum.end(); ++iter)
{
    if (*iter == 'I')
        decimalNum++;
}

Prefer not to pass-by-value here:

void romanType::setRoman(string troll)
{
    romanNum = troll;
}

As you're not modifying troll, prefer to pass by constant reference (const and &).  This will avoid unneeded copying, thereby also increasing performance.  It's best only for non-native types (such as std::string), so disregard it for any of the native ones.

Example (in different forms):

void func(const std::string& str) {}

void func(std::string const& str) {}

do-while loops are usually considered less-readable than while loops.  However, you don't need a while loop here as that would require adding another user input before the loop.

Instead, I'd recommend the "infinite loop" for (;;):

for (;;)
{
    std::cout << "This message will print forever!\n";
    std::cout << "But please do end this eventually!\n\n";

    bool keepGoing = true;
    if (!keepGoing) break; // or return
}

As described, this will keep looping until the loop is ended (usually with a break, return, or return X if non-void).  You'll just need a conditional that will decide when the loop should end.
Prefer to use variables as close in scope as possible:

std::cout << "Input: ";
int input;
std::cin >> input;

This is unneeded:

romanType Rom;
Rom.setRoman(numerals);

You're invoking the default destructor (no arguments) while calling the mutator.

Instead, the object should be constructed right away with numerals:

romanType Rom(numerals);

Beyond that, you won't need a mutator in your program.  They can also be bad for encapsulation, but that's another topic.  For now, focus on proper object construction while only using necessary implementations.  Keep your code as concise as possible.

Note that my previous point about the initializer list was for example purposes.  In this case, you'll need to add an argument to the list.

NewType::NewType(ArgType arg) : member1(arg) {}

With this in place:

NewType objOfNewType(5); // will compile
NewType objOfNewType;    // will not compile

In your program, the latter should still happen as the conversion process shouldn't work with no input given to the object.  You can also keep your existing default constructor, allowing the latter to still work.  But there may be no need for a default value if you want the user to give input.


Haskell network connection graceful handler Just trying to work out some simple graceful connection handling code in Haskell to get my head around some of the IO/Networking/Threading stuff, some tips where I'm doing things poorly would be appreciated! I'm sure I could just use a module like network pipes that would handle all the graceful stuff for me out of the box, but this was just an exercise to try and understand basic network/multithreaded IO handling in haskell.

import Network
import Control.Concurrent
import Control.Concurrent.STM
import Control.Exception
import System.IO

type Connection = (Handle, HostName, PortNumber)
type ConnectionHandler = Connection -> IO ()
type Pool = [(ThreadId, Connection)]

main = runConn

fst' (a,b,c) = a
connFromPool (a,(b,c,d)) = b

runConn = withSocketsDo $ do
  s <- (listenOn (PortNumber 1234))
  p <- atomically (newTVar ([]::Pool))
  t <- forkIO (repeatAccept s p)
  repeatUntilExit stdin stdout putChar ""
  p' <- atomically $ readTVar p
  mapM_ killThread (t:map fst p')
  sClose s
  putStrLn "Enter to exit." >> getLine

repeatAccept s p = do
  c <- accept s
  t <- forkFinally (echoHandler c) (exitPool p)
  atomically $ do
    p' <- readTVar p
    writeTVar p ((t,c):p')
  repeatAccept s p

exitPool :: TVar Pool -> a -> IO ()
exitPool pool = \_ -> do
  tid <- myThreadId
  print $ "Exiting: " ++ (show tid)
  p <- (atomically $ readTVar pool)
  h <- hdl p tid
  open <- hIsOpen h
  if open then do hPutStrLn h "bye\n" >> hFlush h >> hClose h else return ()
  atomically $ do
    pool' <- readTVar pool
    writeTVar pool $ filter ((/=tid).fst) pool'
    return ()
  where hdl p tid = return.connFromPool $ head $ filter ((==tid).fst) p

echoHandler :: ConnectionHandler
echoHandler a@(hdl,_,_) = repeatUntilExit hdl hdl echoToHandleAndStdout ""
  where echoToHandleAndStdout x = hPutChar hdl x >> putChar x

repeatUntilExit :: Handle -> Handle -> (Char -> IO ()) -> [Char] -> IO ()
repeatUntilExit hIn hOut f "exit\n" = return ()
repeatUntilExit hIn hOut f x = do
  c <- hGetChar hIn
  f c
  repeatUntilExit hIn hOut f (appendToLastFive c)
  where appendToLastFive a = (reverse . (:)a . take 4 . reverse) x

-- this is just here because I'm using an older version of base which doesn't have it yet
forkFinally :: IO a -> (Either SomeException a -> IO ()) -> IO ThreadId
forkFinally action and_then =
  mask $ \restore ->
    forkIO $ try (restore action) >>= and_then

Just one remark: When handling IO resources, I'd strongly suggest using bracket for resources that are obtained at some point and later released. Not only it makes your code much safer, it clearly demarcates which resource is used in which parts. And that also prevents separating opening and closing of resources, which is often a hard-to-find error.


Recursive Mergesort using goroutines When learning a new language, one of my first tasks I like to go through is writing a few different sorting algorithms in that language to help familiarize myself with the syntax and see if there are creative ways that algorithm can be conceived in the language.

In Go, I wanted to use this as an opportunity to work with Goroutines and see if there are other interesting functions/uses that I had missed while writing this out. Effectively, my goal is to have the divide-and-conquer portion of the algorithm happen concurrently.

One possible area of improvement would be to have the combination of the left and right sides also happen concurrently, rather than wait for the left and right sides to complete before moving on to combining. Overall, my concerns boil down to:

1) How could I, if possible, use concurrency inside/around the for loops from the mergesort function to speed up the end portion of the algorithm?

2) Other than the algorithm itself which, to my understanding, already is in the "sort" package, are there any other Go-specific problems with my code that could be made more..."Go-thic"?

package main

import (
    "crypto/rand"
    "fmt"
    "os"
    "strconv"
)

var (
    nums    []byte //The slice of numbers we want to sort
    numVals int    = -1
)

//User can optionally add a parameter that determines how many random numbers will be sorted
//If none are provided, 100 will be used
func main() {
    if len(os.Args) >= 2 {
        numVals, _ = strconv.Atoi(os.Args[1])
    } else {
        numVals = 100
    }
    nums = initSlice()
    ms := make(chan []byte)
    go mergeSort(nums, ms)
    nums = <-ms
    for _, value := range nums {
        fmt.Printf("%d\n", value)
    }
}

func initSlice() []byte {
     vals := make([]byte, numVals)
     _, err := rand.Read(vals)
     if err != nil {
        panic(err)
     }
     return vals
}

func mergeSort(arr []byte, ms chan []byte) {
    if len(arr) <= 1 { //base case
        ms <- arr
        return
    }
    leftMS := make(chan []byte)
    go mergeSort(arr[:len(arr)/2], leftMS)
    rightMS := make(chan []byte)
    go mergeSort(arr[len(arr)/2:], rightMS)
    left, right := <-leftMS, <-rightMS
    sortArr := make([]byte, len(arr))
    lIndex, rIndex := 0, 0
    //Combine both sides
    for lIndex < len(left) && rIndex < len(right) {
        leftLeast := left[lIndex] <= right[rIndex]
        if leftLeast {
            sortArr[lIndex+rIndex] = left[lIndex]
            lIndex++
        } else {
            sortArr[lIndex+rIndex] = right[rIndex]
            rIndex++
        }
    }
    //Fill in whichever 'pile' is empty
    if lIndex < len(left) {
        for ; lIndex < len(left); lIndex++ {
            sortArr[lIndex+rIndex] = left[lIndex]
        }
    }
    if rIndex < len(right) {
        for ; rIndex < len(right); rIndex++ {
            sortArr[lIndex+rIndex] = right[rIndex]
        }
    }
    ms <- sortArr
}

Of course, please feel free to add any other suggestions. Thanks!

Keep your global environment clean - no need to define nums and numVals globally. Just create them in the main function and pass them to the appropriate functions.

nums := initSlice(size)

You can save on memory by creating the sortArr array at the initialization phase, and pass it along with arr.

go mergeSort(arr[:len(arr)/2], res[:len(sortArr)/2], leftMS)
go mergeSort(arr[len(arr)/2:], res[len(sortArr)/2:], rightMS)

You can init numVals to 100 and then change it if an arg was provided:

size := 100
if len(os.Args) >= 2 {
    size, _ = strconv.Atoi(os.Args[1])
}

Add a buffer to leftMS and rightMS. This way their goroutines will be closed when they are done. Currently if the right side is done before the left, then it will have to wait because you are reading leftMS first.

leftMS, rightMS := make(chan []byte, 1), make(chan []byte, 1)

Comments always start with an empty space: //Combine both sides -> // Combine both sides


Animals, inheritance and interfaces I am trying to fully understand interfaces and abstract classes in Java and from what I understood, I created a sample console application. Is there an error in the design or is this basically what interfaces and abstract classes are?

Animals.java (interface):

interface Animals {

    void callSound();
    int run();

}

Feline.java (abstract class):

abstract class Feline implements Animals {

    @Override
    public void callSound() {
        System.out.println("roar");
    }

}

Canine.java (abstract class):

abstract class Canine implements Animals {

    @Override
    public void callSound() {
        System.out.println("howl");
    }

}

Lion.java (class):

class Lion extends Feline {

    @Override
    public void callSound() {
        super.callSound();
    }

    @Override
    public int run() {
        return 40;
    }

}

Cat.java (class):

class Cat extends Feline {

    @Override
    public void callSound() {
        System.out.println("meow");
    }

    @Override
    public int run() {
        return 30;
    }

}

Wolf.java (class):

class Wolf extends Canine {

    @Override
    public void callSound() {
        super.callSound();
    }

    @Override
    public int run() {
        return 20;
    }

}

Dog.java (class):

class Dog extends Canine {

    @Override
    public void callSound() {
        System.out.println("woof");
        super.callSound();
    }

    @Override
    public int run() {
        return 10;
    }

}

Main.java:

public class Main {

    public static void main(String[] args) {
        Animals[] animals = new Animals[4];
        animals[0] = new Cat();
        animals[1] = new Dog();
        animals[2] = new Wolf();
        animals[3] = new Lion();

        for (int i = 0; i < animals.length; i++) {
            animals[i].callSound();
        }
    }

}

Overall, it seems like your implementation is fine and accurately represents the relationships between the different classes and interface.  You could improve on your design however if you would consider some style guides.

Explicitness

The default modifier for your classes / interfaces will make them only visible from within your package.  While this may be what you intended, it's always better to be explicit and state the level of access you intend each portion of your code to have.  This reduces guess-work made by others who work with your code (which can help to reduce bugs made based on assumptions) and it improves the readability.

This has the additional benefit of making the rest of your code more consistent (since you do not use default modifiers for your methods).

Naming

EDIT

In the following section I borrow wisdom from .NET Land.  This would appear to be contrary to the style guide used by most JAVA developers. As illustrated in the links below:

https://stackoverflow.com/questions/541912/interface-naming-in-java
https://stackoverflow.com/questions/2814805/java-interfaces-implementation-naming-convention

That being said, it used to be convention to not have to dial an area code in the U.S. but after seeing the shortcomings, it was changed to always require area code.  My point is that conventions often change (and usually for pragmatic reasons in the programming community) and as a result be open to other schools of thought.  I think you'll find if you take both pieces of advice (creating interfaces based on attributes / behaviors) along with the "I" prefix, it makes the most sense.  Ultimately this is a SMALL piece of the review and as with the rest of it, feel free to take or not take the input.

END EDIT

Typically (in .NET and Eclipse) interfaces begin with the letter "I" to denote this fact.  So your interface Animals would be better named IAnimal (also without the plural unless you intend the interface to handle multiple animals).

Separation of Concerns

This is more of an esoteric critique, but generally speaking you'll want your interfaces to be well-segregated and more specific.  The current Animals interface doesn't really communicate what the interface is used for.  If I were making an application for example that only showed pictures of various animals, it is unclear whether or not I should use your interface on my new class.
Rather, it is better to split interfaces (usually) based on the behavior they add.  This forces them to be very targeted and succint, which in turn produces code that is more stable and typically easier to maintain since changes are very isolated.

For example, instead of:

interface Animals {

    void callSound();
    int run();

}

You might have:

interface IMakesSound {
    void callSound();
}

interface ICanMove {
    int move();
}

interface IWarmBlooded {
    int currentBodyTemperature();
    bool isOverheated();
}

abstract class Animal implements IMakesSound, ICanMove {
    abstract void callSound();
    abstract int move();
}

abstract class Mammal extends Animal implements IWarmBlooded {
    private int _bodyTemp;
    abstract void callSound(); // We don't know what ALL mammals sound like
    abstract int move(); // Some mammals run, others walk, some swim, and some do all of the above.
    public int currentBodyTemperature() {
        return _bodyTemp;
    }

    public bool isOverheated() {
        return _bodyTemp > 98; // This can be overridden based on the child class if needed
    }
}

// Other classes here that inherit either from `Animal` or `Mammal`.

In the above example, I have separated out your interface into two separate interfaces and an abstract base type that combines them.  Using this structure, I can create something that makes a sound but isn't an animal (for example, a robot toy dog) that can still have all of the attributes of a "real" dog, but none of the inherited animal features.

This allows your code to be more flexible and more loosely coupled (which is the point of using an interface).  By having code dependent on these loosely typed constructs, it allows for more flexibility.

For example:

public class Main {

    public static void main(String[] args) {
        Animals[] animals = new Animals[4];
        animals[0] = new Cat();
        animals[1] = new Dog();
        animals[2] = new Wolf();
        animals[3] = new Lion();

        for (int i = 0; i < animals.length; i++) {
            animals[i].move();
        }

        ShowPetSounds(animals);
    }

    public static void ShowPetSounds(IMakesSound[] petNoises) {
        for (int i = 0; i < petNoises.length; i++) {
            petNoises[i].callSound();
        }
    }

}

This allows us to write code that only knows about pet sounds without having to worry about what kind of animal it is (or indeed that it is an animal).  This allows us to have imaginary pets like dragons (which we all love) or unicorns that would defy the "normal" inheritance hierarchy of an Animal type.

Ultimately both abstract classes and interfaces should be designed to be helpful abstractions, not abstraction for that sake of abstraction.  When you do this, you will find that as your code-base grows over time, it will respond much better to additional requirements and changes in the system.


Squeezing decorators into functional extensions When you try to use several decorators it can get ugly pretty quickly and you'll end up with:

new RelativeFileProvider(
  new SystemVariableFileProvider(
      new PhysicalFileProvider()
  ),
  "%TEMP%"
);

or if you prefer one-liners then like that:

new RelativeFileProvider(new SystemVariableFileProvider(new PhysicalFileProvider()), "%TEMP%");

I thought I turn them into extensions and make them play along nicer in a functional way so I created a couple of helper methods that allow me to do this:

new PhysicalFileProvider()
    .DecorateWith(SystemVariableFileProvider.Create())
    .DecorateWith(RelativeFileProvider.Create("%TEMP%"));

Don't be confused about the empty classes. To be able to experiment without being distracted by the implementations I extracted the interface and the classes from my question about Multiple file access abstractions
 that I'm going to use this pattern for. They all have implementations that have been already reviewed there. This question is about the additional decorator helper APIs and they are implementation-netural.

Here are the types I used:

Version 1 - with an exntesion

interface IFileProvider
{

}

class PhysicalFileProvider : IFileProvider
{
    public static PhysicalFileProvider Create()
    {
        return new PhysicalFileProvider();
    }
}

class RelativeFileProvider : IFileProvider
{
    public RelativeFileProvider(IFileProvider fileProvider, string basePath)
    {

    }

    public static Func<IFileProvider, RelativeFileProvider> Create(string basePath)
    {
        return decorable => new RelativeFileProvider(decorable, basePath);
    }
}

class SystemVariableFileProvider : IFileProvider
{
    public SystemVariableFileProvider(IFileProvider fileProvider)
    {

    }

    public static Func<IFileProvider, SystemVariableFileProvider> Create()
    {
        return decorable => new SystemVariableFileProvider(decorable);
    }
}

static class FileProviderExtensions
{
    public static IFileProvider DecorateWith(this IFileProvider decorable, Func<IFileProvider, IFileProvider> createDecorator)
    {
        return createDecorator(decorable);
    }
}

Version 2 - with an interface

This API forces each type to implement the DecorateWith method instead of relying on an extension.

interface IDecorable<T>
{
    T DecorateWith(Func<T, T> createDecorator);
}

interface IFileProvider : IDecorable<IFileProvider>
{

}

class PhysicalFileProvider : IFileProvider, IDecorable<IFileProvider>
{
    public static PhysicalFileProvider Create()
    {
        return new PhysicalFileProvider();
    }

    public IFileProvider DecorateWith(Func<IFileProvider, IFileProvider> createDecorator)
    {
        return createDecorator(this);
    }
}

class RelativeFileProvider : IFileProvider, IDecorable<IFileProvider>
{
    public RelativeFileProvider(IFileProvider fileProvider, string basePath)
    {

    }

    public static Func<IFileProvider, RelativeFileProvider> Create(string basePath)
    {
        return decorable => new RelativeFileProvider(decorable, basePath);
    }

    public IFileProvider DecorateWith(Func<IFileProvider, IFileProvider> createDecorator)
    {
        return createDecorator(this);
    }
}

class SystemVariableFileProvider : IFileProvider, IDecorable<IFileProvider>
{
    public SystemVariableFileProvider(IFileProvider fileProvider)
    {

    }

    public static Func<IFileProvider, SystemVariableFileProvider> Create()
    {
        return decorable => new SystemVariableFileProvider(decorable);
    }

    public IFileProvider DecorateWith(Func<IFileProvider, IFileProvider> createDecorator)
    {
        return createDecorator(this);
    }
}

And these are the whys about the factories:

I chose static factory methods over free arguments to keep parameter names and their order.
I chose them also to avoid new.

What do you think of this system? Do you prefer one version over the other? Can this be made even more convinient? Or would you say this is madness?

IMO the first version is easier to maintain, and I don't see from the shown code, what you gain by the second.

In the second version:

Each FileProvider class doesn't need to explicitly inherit IDecorable<IFileProvider> because that is inherited via IFileProvider.

I maybe overlooking something or you may find it too obvious to show, but I don't like that you implement the interface IFileProvider in all the provider classes, because they then are forced to implement all (I can see there aren't any (yet)) possible common members, which could be taken care of in a base class. Therefore I would create an abstract base class for the providers like:

  interface IDecorable<T>
  {
    T DecorateWith(Func<T, T> createDecorator);
  }

  interface IFileProvider : IDecorable<IFileProvider>
  {

  }

  abstract class FileProvider : IFileProvider
  {
    public virtual IFileProvider DecorateWith(Func<IFileProvider, IFileProvider> createDecorator)
    {
      return createDecorator(this);
    }
  }

  class PhysicalFileProvider : FileProvider
  {
    public static PhysicalFileProvider Create()
    {
      return new PhysicalFileProvider();
    }
  }

  class RelativeFileProvider : FileProvider
  {
    public RelativeFileProvider(IFileProvider fileProvider, string basePath)
    {

    }

    public static Func<IFileProvider, RelativeFileProvider> Create(string basePath)
    {
      return decorable => new RelativeFileProvider(decorable, basePath);
    }
  }
  ...

In this way you gain both the benefits of normal OOP inheritance/polymorphic behavior and the decorator pattern and at the same time are still free to chain .DecorateWith(...) with other implementers of IFileProvider

Madness is a strong word. The shown chain looks a little nicer than a chain of new xx() statements, and you explicitly "explain" the pattern and behavior. And the first version doesn't need much attention when first written, so no harm done at least.


Irregular perimeter in Ruby code I came across a situation where I'd like to improve my code, but don't really have a clue about what I could do... It's for a game I'm making, I want to get a perimeter surrounding a unit, but I don't want tiles inside the perimeter. I'm pretty sure there is a better way to do this. (@x and @y are the unit's coordinates)

r = 4
radius = []
for x in @x-r..@x+r
  for y in @y-r..@y+r
    radius.push([x, y]) if $game_map.passable?(x, y)
  end
end
radius.delete_if {|a|
  radius.include?([a[0] + 1, a[1]]) &&
  radius.include?([a[0] - 1, a[1]]) &&
  radius.include?([a[0], a[1] + 1]) &&
  radius.include?([a[0], a[1] - 1])
}

There are some things that I simplified here to focus on the problem, like the local variable 'r' that would not be constantly 4. What matters is how to handle radius so it gives the same result without having to add the coordinates that will be removed.

Performance is important as this function is called frequently by many units.

Better late than never - Anon
first make it work, then make it right, and, finally, make it fast. -
Kernighan & Johnson
Rules of optimization:
(1) Don't.
(2) (for experts only) Don't yet.
(3) Profile before optimizing

First make it work, then make it right
There's a bug.  If $game_map#passable? always returns true, the
coordinates returned by this code are in this pattern:
XXXXXXXXX
X-X-X-X-X
XX-X-X-XX
X-X-X-X-X
XX-X-X-XX
X-X-X-X-X
XX-X-X-XX
X-X-X-X-X
XXXXXXXXX

Based on your description, you are (or were) looking for this pattern:
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXX---XXX
XXX---XXX
XXX---XXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

The trouble is here:
  radius.delete_if {|a|
    radius.include?([a[0] + 1, a[1]]) &&
      radius.include?([a[0] - 1, a[1]]) &&
      radius.include?([a[0], a[1] + 1]) &&
      radius.include?([a[0], a[1] - 1])
  }
  radius

One fix is to replace those lines with:
  radius.reject do |x, y|
    x.between?(@x - 1, @x + 1) && y.between?(@y - 1, @y + 1)
  end

and finally, make it fast
With the above fix, the code works, so let's benchmark it.  10,000
iterations of it take 0.600 seconds on my box.
We can do better.  Instead of adding coordinates just to remove them
later, how about not adding them in the first place?
    r = 4
    radius = []
    for x in @x-r..@x+r
      for y in @y-r..@y+r
        next if x.between?(@x - 1, @x + 1) && y.between?(@y - 1, @y + 1)
        radius.push([x, y]) if $game_map.passable?(x, y)
      end
    end
    radius

This is simpler, but is it faster?  Just a bit.  10,000 iterations now
take 0.500 seconds instead of 0.600.  More important, though, it's
simpler.
There doesn't seem to be much room for optimization here, which leads
to these questions:

Is the program fast enough?
If not, which part of the program is the bottleneck?

You can't answer those questions without profiling.  That's why the
first code you write should be clear and correct.  Then, only if it isn't
fast enough, profile to learn where it's too slow, and optimize that
part.  Repeat until it's fast enough, then stop.
The reason to optimize later rather than earlier is because
optimization has a cost.  It increases the complexity of the code,
often leading to code that's harder to read and maintain.  It's no
good to pay that cost unless you're getting actual benefit from it.
An OOP issue
This code should probably be in GameMap:
class GameMap
  ...

  def passable_coords_near(x, y)
    r = 4
    radius = []
    for x in (x - r)..(x + r)
      for y in (y - r)..(y + r)
        next if x.between?(x - 1, x + 1) && y.between?(y - 1, y + 1)
        radius.push([x, y]) if passable?(x, y)
      end
    end
    radius
  end

  ...
end


Best practice of HTML DOM template in javascript Of course the when this select is comes with less options it will be better to leave it like this, and when it comes more then this it better to make it via loop.
The question is that if I should make it loop or leave it as it is ?
which way is the best and why ?

var htmlTemplate =
    "<select class='action cycle' auto='1' value='24'>" +
        "<option value='6'>6 hours</option>" +
        "<option value='12'>12 hours</option>" +
        "<option value='24' selected=''>24 hours</option>" +
        "<option value='48'>48 hours</option>" +
        "<option value='72'>72 hours</option>" +
    "</select>";

Also, in my current project I'm making 'Add' button which creates some html dom elements.
My question is if I should leave the code inside string or create it via javascript (createElement) and again, I would like to know what is the best way and why :)

var htmlTemplate = "class='target-unit' identify='blahblah'";
htmlTemplate = "
" +
                    "" + targetPlace + "" +
                    "<select class='action campaign'>" + targetOptions + "</select>" +
                    "5000" +
                    "<select class='action cycle' auto='1' value='24'>" +
                    "<option value='6'>6 hours</option>" +
                    "<option value='12'>12 hours</option>" +
                    "<option value='24' selected=''>24 hours</option>" +
                    "<option value='48'>48 hours</option>" +
                    "<option value='72'>72 hours</option>" +
                    "</select>" +
                    "<button class='action small button-icon add flr no-title' identify='target-add'></button>" +
                "
";

Personally I would create loops for this, it's very unreadable at the moment and you are repeating yourself a lot. Remember the DRY rule (don't repeat yourself). Also if you do it via loops it's easier to maintain and change in the future.


Two sum with two lists Suppose we have two sorted lists, and we want to find one element from the first, and the other element from the 2nd list, where the sum of the two elements equal to a given target. If there are multiple combinations, need to find all the combinations.

Any bugs, performance improvement ideas in terms of algorithm time complexity or code style advice is highly appreciated. My basic idea is to scan the first list from the beginning, and scan the second list from the end, a similar approach to how we resolve the 2-sum classic problem in one list.

def two_sum(list1, list2, target, result):
    i = 0
    j = len(list2) - 1
    while i < len(list1) and j >= 0:
        if list1[i] + list2[j] == target:
            result.append((list1[i], list2[j]))
            i += 1
            j -= 1
            while i < len(list1) and list1[i] == list1[i-1]:
                i += 1
            while j >= 0 and list2[j] == list2[j+1]:
                j -= 1
        elif list1[i] + list2[j] > target:
            j -= 1
        else:
            i += 1
if __name__ == "__main__":
    list1 = [1,3,5,7]
    list2 = [2,3,4,5]
    result = []
    two_sum(list1, list2, 6, result)
    print result

Assuming that your lists are sorted and this is something that comes out of problem description and the part where you need to find something in 99% of that kind of questions you want to use binary search. So basically all your code could be written like this:

from bisect import bisect_left

def binary_search(a, x):
    pos = bisect_left(a, x)
    return pos if pos != len(a) and a[pos] == x else -1

def two_sum(a, b, target):
    result = []
    for num in a:
        index = binary_search(b, target-num)
        if index != -1:
            result.append((num, b[index]))
    return result

Now if you want to save some memory, you might want to make two_sum a generator, which will make it look like this:

def two_sum(a, b, target):
    result = []
    for num in a:
        index = binary_search(b, target-num)
        if index != -1:
            yield num, b[index]

I cannot really call my answer a review to your code because I completely overwrote a solution for this. But as I mentioned in the beginning whenever a problem says something about sorted lists and searching on it, most likely you will use bsearch in your solution.


C++ Trie using std::map and std::unique_ptr I'm learning C++ and whilst trying to write in modern C++, I've made an attempt to rewrite a trie implementation written in C found here: http://www.geeksforgeeks.org/trie-insert-and-search/

It uses arrays to hold the branches in each node and because it's C it was done using malloc() and no freeing of memory was done in the example.

Is this an efficient approach of representing a trie in C++11? what other ways can I store children in trie nodes?

#include <iostream>
#include <map>
#include <algorithm>
#include <memory>

class Trie {
    struct Node;
    typedef std::unique_ptr<Node> spNode;
    struct Node {
        std::map<char, spNode> children;
        bool isLeaf;
        Node() : isLeaf{false} {}
    };

    spNode root;
public:
    Trie();
    void insert(const std::string& str);
    bool search(const std::string& str);
};

Trie::Trie():root{nullptr}{}

void Trie::insert(const std::string& str) {
    if (root == nullptr) {
        std::unique_ptr<Node> node(new Node());
        root = std::move(node);
    }

    Node *temp = root.get();
    for (const char& c : str) {
        if (temp->children.find(c) == temp->children.end()) {//if char not in map
            std::unique_ptr<Node> node(new Node());
            temp->children[c] = std::move(node);
        }

        temp = temp->children[c].get();
    }

    temp->isLeaf = true;
}

bool Trie::search(const std::string &str) {
    if (root == nullptr) return false;

    Node *temp = root.get();
    for (const char& c : str) {
        if (temp->children.find(c) == temp->children.end())
            return false;
        temp = temp->children[c].get();
    }
    return (temp->isLeaf);
}

int main (void) {
    std::string words[] = { "Hello", "hi", "hey", "howdy", "ho"};
    Trie test;

    for (const auto& str : words) {
        test.insert(str);
    }

   if (test.search("Hello"))
       std::cout << " 'Hello' is found in the trie\n";
    else
       std::cout <<" 'Hello' is not found in the trie\n";

   if (test.search("yo"))
       std::cout << " 'yo' is found in the trie\n";
    else
       std::cout << " 'yo' is not found in the trie\n";

}

I don't see the need for unique_ptr for the root node.

spNode root;

I would just make this a node.

Node root;

The use of std::map is fine. But it does have O(log(n)) lookup. If you switch back to an array its O(1). Its a time for space thing. Pick the one you want.

I don't like the two line creation of nodes.

        std::unique_ptr<Node> node(new Node());
        temp->children[c] = std::move(node);

Just use reset:

        temp->children[c].reset(new Node());

Or if you have C++14 use std::make_unique()

        temp->children[c] = std::make_unique<Node>();

Personally search() does not seem quite the correct verb.

bool search(const std::string& str);

What is wrong with find()?


Function that reorders the columns of a matrix The objective: Given an m by n matrix, I have written a function in Matlab that reorders the columns of the matrix to output linearly independent columns; other/redundant columns. Basically, it just pushes the redundant columns to the end of the matrix.

Here is my attempt at the code (which produces correct results):

function result = find_redundant_assets(A)

if (rank(A) == size(A, 2)) % if the rank is the same as the number of columns => full rank
    result = A;
else % there exists at least one linearly dependent column
    A_red = [];
    for n = 1:(size(A,2)-1) % fix a column and compare to all neighbors to the right
        for p = n+1:size(A,2) % loop through comparison columns

            if ( isequal( A(:,p)' * round(A(:, n)'/ A(:,p)') == A(:,n)', ones(1, size(A,1)))) % TRUE iff the nth column is a scalar multiple of the pth column
                A_red = [A_red, A(:,n), A(:,p)]; % add the linearly depedent rows
            end

            if (isequal(A(:,n)' * round(A(:, p)'/ A(:,n)') == A(:,p)', ones(1, size(A,1)))) % TRUE iff the pth column is a scalar multiple of the nth column
                A_red = [A_red, A(:,p), A(:,n)]; % add the linearly depedent row
            end

        end
    end
   A_red = unique(A_red.', 'rows', 'stable')';
   result = fliplr([A, A_red]);
   result = unique(result.', 'rows', 'stable')';
   result = fliplr(result);
end
end

This function gets pretty complicated, but it makes sense to me.

How can I improve my code? Does anyone know a better way to accomplish this task?

Also, I know this is not efficient code because I am constantly re-sizing the matrix.

I don't have Matlab here, and Octave's unique doesn't have the same options as Matlab's, so I can't run the entire code.

So I'll just point out a few things:

isequal( A(:,p)' * round(A(:, n)'/ A(:,p)') == A(:,n)', ones(1, size(A,1)));

Can be written:

all( A(:,p).' * round(A(:,n).'/A(:,p).') == A(:,n).');

You don't need to compare it to a vector of ones, you can just check if all entries are true. Also, conventiently, if [a, b, c, d] will only evaluate to true if all elements a, b, c, d are true. So, the if statement can simply be written:

if (A(:,p).' * round(A(:,n).'/A(:,p).') == A(:,n).');

Notice that I've added a dot . in front of all the '. That's because ' is the complex conjugate transpose, not the regular one.

You have initialized A_red = [], instead of giving it a size, most likely since you don't know the size. Luckily, you do know other things. For instance the maximum possible size, and the any zero-columns can be deleted in the end.

Initialize A_red like this (select an appropriate num_rows:

A_red = zeros(size(A,1), num_rows);`

And do this in the end to remove all the zero-columns:

result = result(:, all(result));

The code can probably be written a lot faster, cleaner and smoother. I'll leave that to someone else for now. This should at least improve the code =)


Weighted graph from a matrix (list-of-lists) I created this code while solving the Euler Project problem 83.

  In the 5 by 5 matrix below, the minimal path sum from the top left to
  the bottom right, by moving left, right, up, and down, is indicated in
  bold red and is equal to 2297.

  Find the minimal path sum, in matrix.txt (right click and "Save
  Link/Target As..."), a 31K text file containing a 80 by 80 matrix,
  from the top left to the bottom right by moving left, right, up, and
  down.

I have a matrix with weights stored as a list-of-lists. The task is to traverse the matrix from the top-left element to the bottom right element. At every point, I can go up, down, left or right. The problem is to find the path with the minimal summed weights.

To answer this, I converted the matrix to a graph (Make_Graph), represented as a dictionary in Python. The key in the dictionary is the string row_index, column_index (Name_Name). My next step in solving the Euler problem (not shown here) is to use Dijkstra's algorithm to find the shortest path.

I'm an amateur Python enthusiast, not a professional programmer. I have the feeling that Make_Graph can be made more Pythonic, but I don't know how. It looks a bit messy to me.

def node_name(row_index, col_index):
    return str(row_index)+","+str(col_index)

def make_graph(matrix):
    graph={}
    for rowindex,row in enumerate(matrix):
        for colindex,value in enumerate(row):
            graph[node_name(rowindex,colindex)]={}
            # Up
            if rowindex>0: graph[node_name(rowindex,colindex)][node_name(rowindex-1,colindex)]=matrix[rowindex-1][colindex]
            # Down
            if rowindex<len(matrix)-1: graph[node_name(rowindex,colindex)][node_name(rowindex+1,colindex)]=matrix[rowindex+1][colindex]
            # Left
            if colindex>0: graph[node_name(rowindex,colindex)][node_name(rowindex,colindex-1)]=matrix[rowindex][colindex-1]
            # Right
            if colindex<len(row)-1: graph[node_name(rowindex,colindex)][node_name(rowindex,colindex+1)]=matrix[rowindex][colindex+1]
    return graph

print make_graph([[1,2],[3,4],[5,6]])

Well, both node_name and make_graph can be a bit smaller, yes.

def node_name(row_index, col_index):
    return "{},{}".format(row_index, col_index)

format will do the string conversion automatically, no need to call str.

I'd also give everything a bit more space to make it more readable.

def make_graph(matrix):
    graph = {}

    width, height = len(matrix[0]), len(matrix)

    columns = range(width)
    for rowindex in range(height):
        for colindex in columns:
            graph[node_name(rowindex, colindex)] = x = {}

            # Up
            if rowindex > 0:
                x[node_name(rowindex - 1, colindex)] = matrix[rowindex - 1][colindex]
            # Down
            if rowindex < height - 1:
                x[node_name(rowindex + 1, colindex)] = matrix[rowindex + 1][colindex]
            # Left
            if colindex > 0:
                x[node_name(rowindex, colindex - 1)] = matrix[rowindex][colindex - 1]
            # Right
            if colindex < width - 1:
                x[node_name(rowindex, colindex + 1)] = matrix[rowindex][colindex + 1]

    return graph

Except caching more things this would look okay to me.  Relying a
rectangular matrix seems obvious to me, so width and height can be
precomputed.  Using range also makes it more clear that you really
want the coordinates, not the row or column values.

In the interest of verbosity I'd also just i and j for indexes, but
that's your choice obviously.

Also, you know that {(1, 1): 1} works, right?  Because there doesn't
seem to be a pressing reason to use node_name at all.  In contrast to
a list a tuple is immutable and can be used as a dictionary key, see
also this wiki page for a more thorough discussion on that.