Midpoint of a segment From SICP:

  Exercise 2.2

  Consider the problem of
  representing line segments in a plane.
  Each segment is represented as a pair
  of points: a starting point and an
  ending point. Define a constructor
  make-segment and selectors
  start-segment and end-segment that
  define the representation of segments
  in terms of points. Furthermore, a
  point can be represented as a pair of
  numbers: the x coordinate and the y
  coordinate. Accordingly, specify a
  constructor make-point and selectors
  x-point and y-point that define this
  representation. Finally, using your
  selectors and constructors, define a
  procedure midpoint-segment that takes
  a line segment as argument and returns
  its midpoint (the point whose
  coordinates are the average of the
  coordinates of the endpoints). To try
  your procedures, you'll need a way to
  print points:

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

I wrote the following solution:

(define (make-segment a b) (cons a b))
(define (start-segment l) (car l))
(define (end-segment l) (cdr l))

(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))

(define (sum . l) (if (zero? (length l)) 0 (+ (car l) (apply sum (cdr l)))))
(define (average . l) (/ (apply sum l) (length l)))

(define (midpoint seg)
  (make-point (average (x-point (start-segment seg))
                       (x-point (end-segment seg)))
              (average (y-point (start-segment seg))
                       (y-point (end-segment seg)))))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

(define seg-1 (make-segment (make-point 3 4)
                            (make-point 8 10)))
(print-point (midpoint seg-1))

What do you think?

Your definitions of make-segment and make-point can be simply bound to cons; you may do the same for accessors.

(define make-segment cons)
(define start-segment car)
(define end-segment cdr)

(define make-point cons)
(define x-point car)
(define y-point cdr)

Your definition of sum is similar to how + works.  You may use + instead in your definition of average.

(define (average . l) (/ (apply + l) (length l)))

Notice the repetition of code in your definition of midpoint--you create a new point out of the averages of each coordinate of the two end-points that describe the line segment.  You may abstract out the calculation of averages either by writing your own helper function or by using the built-in map function, like so:

(define point->coordinate-accessors (list x-point y-point))
(define (midpoint seg)
  (apply make-point (map (lambda (point->coordinate)
                           (average (point->coordinate (start-segment seg))
                                    (point->coordinate (end-segment seg))))
                         point->coordinate-accessors)))

This definition is general enough to handle midpoint calculation in as many dimensions as handled by make-point and point->coordinate-accessors.


Project Euler 30 -- Digit fifth powers Here's my solution for Project Euler Problem 30. Any optimizations in time, space, or style would be greatly appreciated.

from timeit import default_timer as timer

def digit_powers(exponent):
    def power(k):
        return int(k) ** exponent
    if exponent <= 1:
        return "The exponent must be at least 2."
    else:
        total_sum = 0
        upper_bound = (exponent + 1) * (9 ** exponent)
        for number in range(10, upper_bound + 1):
            digits = [x for x in str(number)]
            if number == sum(map(power, digits)):
                total_sum += number
        return total_sum

start = timer()
ans = digit_powers(5)
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

In looking at your code, it seems well written and solves the problem in a straight forward manner.  The one thing I would do is to remove the else after your argument check and remove a level of indent.  That just helps to keep things flat... Flat is better than nested.

Now onto optimization and potentially making it more complex than it needs to be in order to make it faster.  In these problems it seems like a reasonable thing to do even though....Simple is better than complex.

Here are a couple things I looked at as potential issues:

When doing the sum(map(power, digits)), you are calculating the power of each digit many times.  If this was a much more expensive calculation then only calculating 1 time is even more important.
In this problem there is a conversion from int->str->int.  If you can breakdown the digits without converting them it saves some time.  It seems like a good thing to know how to do just in case your ever trying a different language where skipping those transitions may be even faster.

To address these, I did two things:

Pre-calculate 1-9 powers and store the results in a dictionary so they don't get recalculated (Memoization).  It lets me look them up very quickly without calculating each time.
Separate the digits using math.log10 as to avoid the int->str->int conversion.

The first item is fairly straight forward, calculating for each digit:

powers = {}
for a in range(10):
    powers[a] = a ** exponent

The second part is a little trickier, what it does is uses math.log10 which gives a count of the digits, then it does a mod 10 to get the right most digit, looks up that power to add to the total and then finally does integer division to divide by 10 effectively moving the decimal place 1 position to the left (dropping the right most digit we just dealt with).  This is probably a little different between Python 2/3 due to changes in int/float division.  It is basically doing what you are using [x for x in str(number)] to do but without converting to string and adding the power of 5 dict lookup as it goes along:

savei = i
for _ in range(int(math.log10(i)) + 1):
    digit = i % 10
    total += powers[digit]
    i //= 10

Applying those changes to the code make it about twice as fast.  Here is what I end up with for the function:

import math

def digit_powers(exponent):
    if exponent <= 1:
        return "The exponent must be at least 2."

    powers = {}
    answer = 0
    # Get the powers
    for a in range(10):
        powers[a] = a ** exponent

    limit = (exponent + 1) * (9 ** exponent)

    # Search for them
    for i in range(10, limit):
        savei = i
        total = 0

        for _ in range(int(math.log10(i)) + 1):
            digit = i % 10
            total += powers[digit]
            i //= 10

        if (total == savei):
            answer += total

    return answer


Appending a trailing slash if needed I like to overcomplicate things, this is fairly simple though but I would like to keep it simpler without lowering readability. Not just to improve my code but also my self.

private String checkTrailingSlash(String website) {
    if(!website.endsWith("/")){
        website = website + "/";
    }
    return website;
}

You could use a ternary operator to inline the condition into a single return statement:

private String checkTrailingSlash(String website) {
    return website.endsWith("/") ? website : website + "/";
}


Table cell map engine I'm designing a table cell based map design for a little game I'm building, and I was hoping I could get some cleanup pointers or design tips to "perfect" my engine's design. Basically, in the end result, you'll walk around the map one tile at a time. On any visible tile you can walk to it, but only the tile you're on will have "actions" (randomly generated).

Here is my prototype design:

function Map() {
    this.x;
    this.y;
}

Map.prototype = {
    move:function() {
        var new_x = this.x - 1;
        var new_y = this.y - 1;
        Map.prototype.render(new_x, new_y);
    },
    render:function(p_x,p_y) {
        //check for map boundaries
        var max_divs = 2;
        if(!p_x) p_x = 1;
        if(!p_y) p_y = 1;
        if(p_x >= 99) p_x--;
        if(p_y >= 99) p_y--;

        divs_x = max_divs + p_x;
        divs_y = max_divs + p_y;
        //create new table
        var root = document.createElement("table");
        root.id = 'root_table';
        //loop coordinates and generate surrounding cells
        for (var x = p_x; x <= divs_x; x++) {
            var row = document.createElement("tr");
            for (var y = p_y; y <= divs_y; y++) {
                var cell = document.createElement("td");
                if (x <= 0 || y <= 0 || x >= 101 || y >= 101) {
                    cell.textContent = "";
                }
                else {
                    this.x = x; this.y = y;
                    cell.textContent = "("+this.x+","+this.y+")";
                    //add event handler for the click event (move)
                    cell.addEventListener("click", this.move, false);
                    cell.x = x; cell.y = y;
                    cell.className = 'map';
                }
                //add cell to row
                row.appendChild(cell);
            }
            //add row to table
            root.appendChild(row);
        }
        var main = document.getElementById("container");
        var old_table = document.getElementById('root_table')
        if(old_table) main.removeChild(old_table);
        //remove old table, add new one
        main.appendChild(root);
    }
}

var map = new Map();
map.render();

And here is a current working link to my map: zombiesss ahhhh

I'm afraid your code is very hard to understand.  Part of the problem is your variable naming: I'm not sure what exactly p_x is and what distinguishes it from the x that's part of the Map object, for example.  It also doesn't help that your comments mostly just describe the behaviour of entirely obvious single lines of code but don't describe any of the unclear aspects of your code, for instance why it is doing what it is doing.

On to more specific comments, this line of code is confusing:

Map.prototype.render(new_x, new_y);

Is there a reason you aren't using this.render(new_x, new_y) here, but instead calling the method directly on the prototype object?  If so, it would be best to explain it with a comment, as this is quite unusual behaviour.  Also, what are new_x and new_y, and why are they calculated in the way they are?  As far as I can see, Map.x and Map.y are never set to anything that has any particularly useful meaning.

In your inner loop in the render method, you repeatedly update this.x and this.y, but the values stored here are never read by code outside of the method, because they are overwritten by the next iteration of the loop before anything else can touch it.  It is unclear why you are doing this, but generally it would be better to only update them once, and to use local variables when you are calculating values for use only within a single method.

You have a number of values in your code that are seemingly related, i.e. 99 and 101 used in two different places.  It may be best to use a variable to store one of these values (I think 100 cells is the size of your map?) and derive one from the other as necessary.

Update after clarification in comments

Having move be part of the Map object when it isn't called in that context is confusing.  Also referring to Map.prototype is unlikely to be what you want to do, as it basically prevents you from ever having more than one Map, thus negating a key benefit of using objects at all.

Here's how I would handle it: I wouldn't declare the event handler as a separate function at all, but instead declare it inline when I set the event handler.  I would also make sure it had a variable in scope that refers to the Map object, so it doesn't need to access the prototype.  Then I'd have it call back to an event-handling function that's actually properly part of the Map object.  Here's what that might look like:

in the inner loop of the render function:

                var map = this;
                cell.addEventListener("click", function () {
                     map.cellClicked (this);
                }, false);
                cell.x = x; cell.y = y;

and the new cellClicked function:

Map.prototype = {
   cellClicked: function (cell) {
      this.render (cell.x - 1, cell.y - 1);
   },


Improvements to simple Hangman Game in Python I created this hangman game today as my first stand alone project. It is a quite basic and simplified approach. How could I improve the game to make it more interesting?
    import random
    words = ["abductions", "abridgment", "admixtures"
    ,"backfields", "blueprints", "chivalrous", "complexity", "cyberpunks", "desolating",
    "duplicator","earthlings",
    "fluoridate","flustering","fornicates","godfathers","humanizers","ideographs","journalism",
    "languished","logarithms","mendacious","neighborly","outlandish","palindrome","philanders"
    ,"proclaimed","randomizes","shrinkable","sublimated",
     "truckloads","upholstery","vanquished","vulcanizes","wanderlust","womanizers" ]

      i = random.randint(0, len(words) - 1)

      word = words[i]
      guesses = "_"*len(word)
      print(guesses)
      lives = 0
      while lives < 5:
         character_check = input("")
           if character_check in word and character_check != word:
               a = word.index(character_check)
               guesses = guesses[:a] + word[a] + guesses[a+1:]
               print(guesses)
           if guesses == word or character_check == word:
               print("Winner!")
               break
           elif character_check not in word:
               print(lives)
               lives += 1
    if lives == 5:
      print("You lose! It was {}".format(word))

This is a great start. Let me point out a few things you should consider.
Make it interactive
When I ran the code, it produces some numbers whenever I lose a guess, it took a while to figure out that it was my guess count incrementing. A nice prompt message would be helpful. Also the guess count should reduce for each guess made.
Avoid hardcorded values
What is 5 in the following statement
while lives < 5:. it can be written as follow
MAX_LIVES = 5
while lives <= MAX_LIVES:

Misleading names
character_check is just too misleading, promises one thing(to check a character) and does another thing(recieves input from the user). This can rewritten as user_input
Features worth adding

You could make the game a class,implement a board class to nicely draw the man being hung.
You could also implement a hint package interface, user might want to buy and use hints when they are stuck.


Assigning defaults for Smarty using object-oriented style I have a custom class for Smarty that was partially borrowed. This is how the only example reflects the basic idea of using it across my current project:

class Template {

    function Template() {
        global $Smarty;
        if (!isset($Smarty)) {
            $Smarty = new Smarty;
        }
    }

    public static function display($filename) {
        global $Smarty;
        if (!isset($Smarty)) {
            Template::create();
        }
        $Smarty->display($filename);
    }

Then in the PHP, I use the following to display templates based on the above example:

Template::display('head.tpl');
Template::display('category.tpl');
Template::display('footer.tpl');

I made the following example of code (see below) work across universally, so I wouldn't repeat the above lines (see 3 previous lines) all the time in each PHP file.

I would just like to set, e.g.:

Template::defauls();

that would load:

Template::display('head.tpl');
Template::display('template_name_that_would_correspond_with_php_file_name.tpl');
Template::display('footer.tpl');

As you can see Template::display('category.tpl'); will always be changing based on the PHP file, which name is corresponded with the template name, meaning, if for example, PHP file is named stackoverflow.php then the template for it would be stackoverflow.tpl.

I've tried my solution that have worked fine but I don't like it the way it looks (the way it's structured).

What I did was:

Assigned in config a var and called it $current_page_name (that derives the current PHP page name, like this: basename($_SERVER['PHP_SELF'], ".php"); ), which returned, for e.g.: category.
In my PHP file I used Template::defaults($current_page_name);.
In my custom Smarty class I added the following:

public static function defaults($template) {
    global $Smarty;

    global $msg;
    global $note;
    global $attention;
    global $err;

    if (!isset($Smarty)) {
        Templates::create();
    }

    Templates::assign('msg', $msg);
    Templates::assign('note', $note);
    Templates::assign('attention', $attention);
    Templates::assign('err', $err);

    Templates::display('head.tpl');
    Templates::display($template . '.tpl');
    Templates::display('footer.tpl');
}

Is there a way to make it more concise and well structured?

Well, there's a few things wrong here, but let's go over it together and I'll try to steer you in the right direction. Let's start with globals. Globals are extremely bad and should be avoided at all costs. If you have a variable that needs to be available in multiple parts of your script, then you should pass that variable as a parameter to whichever function needs it, and return the modified version if applicable. Why? Well globals are an old feature that have been proven to be full of all kinds of security issues. Not to mention they are just plain impossible to track. Sure, I know where $Smarty came from because I saw you define it in your constructor, but lets say I'm pages into your code and see that for the first time. How am I to know where this came from? Hopefully PHP will deprecate this soon, but until then, just take my word, and that of the entire community's, and don't use globals.

Lets take a look at your constructor. First you should know that the access parameter (public, private, or protected) should be used on every function, more accurately known as a method. This includes the constructor. By default it uses the public status, but I've heard rumors of this getting deprecated soon and it is better to go ahead and assume the default won't always be there for you. Besides, its always a good idea to explicitly define what you expect a method or property's access type to be. Second, the proper way to make a constructor is no longer to create a method with the same name as the class. This used to be the case in PHP 4 I think, but it is now deprecated. It still exists for backwards compatibility, but there's no saying how long that will last. Use the magic method __construct() instead. Magic meaning reserved.

So, let's review. Globals are bad, constructors are built with __construct(). How then do we create a class where we have a "global" variable created in the class contructor? Well like this:

private $smarty;

public function __construct() {
    $this->smarty = new Smarty();
}

You'll notice there's a couple of new things going on here. Hopefully you'll also notice how much cleaner this is. So, what's private $smarty? Its pretty much the same as global $smarty, except the variable isn't available globally, only within the class scope ($this->smarty). If we set the access parameter to public, it would be a little more like a global in that we could access it outside of the class, but in order to do so we would have to use an instance of the class like so: $template->smarty. That's because the variable, or, more accurately property, is associated with that class. The reason we are using a private access type her is because $smarty defines an interior "property" that should only be accessed from within the scope of the class. Sorry I can't explain that any better. Look at it like this. If I created a user class, I wouldn't want the password database to be "public" and available outside of the class. It is sort of the same here, except without sensitive data in the mix.

Let's continue. Next is a static display() method. Static methods exist for no other purpose than to defy OOP. Some might argue that I'm wrong here, but let's break down that acronym. Object Oriented Programming. About the only thing static still has in common with OOP is that it is vaguely related to an object. The inner principles of OOP (encapsulation, inheritance, and polymorphism) are simply ignored by static methods. In a lot of cases you'd be better off with just a normal helper function. Assume you won't ever need static methods for the time being. It is an advanced feature of classes and isn't likely to be necessary until you have a better grasp on the whole concept. Instead, what you should do is drop the static keyword and use the class property like it was meant to be.

public function display( $filename ) {
    $this->smarty->display( $filename );
}

Now, you may have started noticing a pattern here. Each of these new methods I have showed you are simply wrappers for the Smarty class. And that is because you are not doing anything yet that requires "extending" the Smarty class. From what I can see, you would be better of just using the smarty class directly and dropping classes altogether. But hopefully the above helped explain some of the basic concepts for you so that when you do decide to start using OOP, you have a better grasp of it.

EDIT

Oh, and about your problem. The above should help you with the structure, but until you start getting into the more advanced stuff (frameworks and autoloading), this is the best solution. At least as far as I know. The only improvement I would make is to use an absolute path name instead of relative, and you can do that using the magic constant __FILE__.


Implementing a dictionary and thesaurus in Python Write code that functions as both a dictionary and a thesaurus.
  Supported operations:

  Add a word and its definition to the dictionary
  Add a synonym to a word in the dictionary
  Look up the definition of a word in the dictionary
  Look up the synonym of a word in the dictionary
  Synonyms should be considered both commutative and transitive

Hello All,

I was just asked this question in a coding interview and I was wondering how I could do better. I wrote code to the point where I had completed all of the methods of the question, except the final of commutative and transitive properties weren't working for synonyms.  Here's my code so far:

dict = defaultdict(list)
thes = defaultdict(list)

def add_word(word, definition):
    dict[word].append(definition) #add word and definition to dict

def add_synonym(word, syn):
    thes[word].append(syn)
    thes[syn].append(word)

# add the synonym as a second value in the dict
def lookup_word(word):
    if(dict[word]):
       print dict[word] #prints the word and the definition

def lookup_synonym(word):
    if(thes[word]):
        print thes[word]

add_word("cat", "a furry creature")
add_word("feline","a cat")
add_synonym("cat", "feline")

lookup_word("cat")
lookup_synonym("cat")
lookup_synonym("feline")

I realize that it might be better to create either a word object or a dictionary object and then pass in the values as data members, but I'm not sure how to model it and where I could improve the add_synonym function in order to make it commutative.

Thanks!

I find it really strange that you have a list of definitions, personally. I know that there are often multiple definitions for a word, but given that isn't a requirement I wouldn't include it (but this is a great place to practice asking your interviewer questions!).

If I had to include it, I would also want to provide a way to add multiple definitions at once, e.g.

add_word("cat", ["def1", "def2", "def3"])

Additionally, you don't handle the case of a word not being present or synonym not being present - the user should be informed of this in some way.

Other than that, I think that your code is straightforward and successfully meets all of the requirements except for transitivity (if a=b and b=c then a=c).

Transitivity

The obvious way to implement transitivity is to have every word in your thesaurus map to a set, and when you add a synonym iterate over that set and add the new synonym to every one of those words' sets. At this point you can associate all of the words together, but looking up definitions could be annoying (unless you repeat the trick of adding the definition to every synonym).

This solution is not ideal - if you have n words that are synonyms to one another, then it takes O(n^2) space to hold the synonym list1, and O(n*m) space2 to hold the definitions. Wouldn't it be nice if we used O(n) space for the synonyms and O(m) space for the definition3?

I think the best solution here would be a disjoint-set or union-find data structure. Taken from that Wikipedia article:

  A disjoint-set forest consists of a number of elements each of which
  stores an id, a parent pointer, and, in efficient algorithms, a value
  called the "rank".

  The parent pointers of elements are arranged to form one or more
  trees, each representing a set. If an element's parent pointer points
  to no other element, then the element is the root of a tree and is the
  representative member of its set. A set may consist of only a single
  element. However, if the element has a parent, the element is part of
  whatever set is identified by following the chain of parents upwards
  until a representative element (one without a parent) is reached at
  the root of the tree.

  Forests can be represented compactly in memory as arrays in which
  parents are indicated by their array index.

A cool thing about this data structure is that if implemented efficiently, it takes O(a(n)) time to perform both the search and merge operations, which for any real problem (i.e. numbers which can be written in our physical universe) is O(1). If the two primary optimizations aren't implemented you'll hit O(n).

I'm not going to show a full implementation here - its pretty straightforward, and the Wikipedia link gives a good rundown of how it works. The general process would be as follows:

Add a word. Add it to your set with no parent, and associate the definition with this word
Add a synonym of this word. Add it to your set with the word as a parent
Looking up the definition of a word. Look it up in the set, then find the parent which should have the definition with it.
Looking up the synonyms of a word. This one is a bit hard if you don't have back pointers, which you can add without asymptotically increasing the space taken or time taken
Synonyms are commutative. It doesn't matter which is the synonym of the other with back pointers
Synonyms are transitive. You can follow the pointer to the parent or back-pointers to the child.

One thing that is unclear is what happens if you had two existing words in the dictionary and then decided to make them synonyms - this would be another place for your clarifying questions.

I'm assuming that a set of size n takes n space, which depending on implementation may not be true
Assume m is the length of the definition and is proportional to the space it takes to hold it.
This is just to store the single definition of these n synonyms, not of the whole data structure which may have many groups of synonyms, each with their own definition


Merging two lists from dictionary. How to do this in a better way? I have the following code:

print o
# {'actor_name': [u'Keanu Reeves', u'Laurence Fishburne', u'Carrie-Anne Moss', u'Hugo Weaving', u'Glor
# ia Foster', u'Joe Pantoliano', u'Marcus Chong', u'Julian Arahanga', u'Belinda McClory', u'Matt Doran
# '], 'played': [u'Neo (Thomas Anderson)', u'Morfeusz', u'Trinity', u'Agent Smith', u'Wyrocznia', u'Cy
# pher', u'Tank', u'Apoc', u'Switch', u'Mouse']}
li = list(o.itervalues())
for index, value in enumerate(li[0]):
    print [value, li[1][index]]
# [u'Keanu Reeves', u'Neo (Thomas Anderson)']
# [u'Laurence Fishburne', u'Morfeusz']
# [u'Carrie-Anne Moss', u'Trinity']
# [u'Hugo Weaving', u'Agent Smith']
# [u'Gloria Foster', u'Wyrocznia']
# [u'Joe Pantoliano', u'Cypher']
# [u'Marcus Chong', u'Tank']
# [u'Julian Arahanga', u'Apoc']
# [u'Belinda McClory', u'Switch']
# [u'Matt Doran', u'Mouse']

I'm curious how I could write this thing in a more Pythonic way without losing its readability.

You're looking for zip().

print zip(o['actor_name'], o['played'])

or to make it look like your output

for entry in zip(o['actor_name'], o['played']):
    print entry


Finding the sum of all the multiples of 3 or 5 below 1000, using list comprehension I'm trying to compare my own implementation with another solution of Project Euler problem #1, which uses a list comprehension:

module Progression1 (sumProgressions) where
    import Prelude

    sumProgressions :: Integer -> Integer -> Integer -> Integer
    sumProgressions d1 d2 limit =
        sum [n | n <- [1 .. limit], (n `mod` d1) == 0 || (n `mod` d2) == 0]

Mine is directly inspired by user nicocarlos' PHP solution on the PE site. It avoids using hard-coded constants, instead computing most of the values (with as much algebraic simplification as possible):

module Progression2 (sumProgressions2) where
    aN               :: Integer -> Integer -> Integer -> Integer
    pSum             :: Integer -> Integer -> Integer -> Integer
    sumProgressions2 :: Integer -> Integer -> Integer -> Integer

    aN a1 d n = a1 + (n - 1) * d  -- Calculating the value of the Nth term

    pSum 0  d lim  = pSum d d lim -- a1 == 0 produces invalid pSum() result
    pSum a1 d lim =
        let n1 = (lim `div` d)            -- Using simplified method for finding n
            n2 = ((lim - a1) `div` d + 1) -- Use non-simplified formula for calculation
        in if (a1 == d)
            then (d * n1 * (n1 + 1)) `div` 2      -- Assumes n1 is simplified
            else (n2 `div` 2) * (a1 + aN a1 d n2) -- Non-simplified calculation

    sumProgressions2 d1 d2 lim = let d3 = d1 * d2
        in (pSum d1 d1 lim) + (pSum d2 d2 lim) - (pSum d3 d3 lim)

I'm new to Haskell and inexperienced with functional programming; I'd like suggestions for improving this code's performance and style.

Currently criterion is showing similar mean benchmark times for each solution, calculated for d1 = 3, d2 = 5, limit = 100000-1.

Updated with current code:

This solves the bug mentioned in the accepted answer, and takes much of its advice on style (as well as discarding the simplified algebra.)

-- Using arithmetic progression formula for the Nth element aN, we can determine
-- the value aN = a1 + (N - 1) * d. Rearranging yields N = (aN - a1) / d + 1.
-- Calculates N, then the last aN, and uses it to find S = (N / 2) * (start + last)
pSum 0     diff limit = pSum diff diff limit
pSum start diff limit = truncate ((fromIntegral n / 2) * fromIntegral(start + last))
    where n    = (limit - start) `div` diff + 1
          last = start + (n - 1) * diff

-- Add the sums of two progressions and subtract sum of similar elements
sumProgressions2 :: Integer -> Integer -> Integer -> Integer
sumProgressions2 diff1 diff2 limit =
    (pSum 0 diff1 limit) + (pSum 0 diff2 limit) - (pSum 0 diff3 limit)
        where diff3 = lcm diff1 diff2

Correctness:

Many reviewers will not bother to comment on code that is not correct.
I might have kept this brief, myself, except that it was only in the process of considering optimization that I discovered that this code contains two bugs that prevent correct answers.

It shares one of those bugs with the simpler sumProgressions. The benefit of the simplicity of sumProgressions is that the bug has fewer places to hide there.
Hint: Why does sumProgressions 3 5 1000 give the same answer as sumProgressions 3 5 1001?

Nothing about this bug changes my comments below about style or optimization, so I might have pointed it out and moved on, even if I had caught it up front.

The more serious bug is unique to sumProgressions2.
Hint: Why does sumProgressions 3 6 20 give a different answer from sumProgressions2 3 6 20?

If I had noticed this earlier, my answer might have ended here.

But it seemed a shame to throw the rest of this away, so, (mostly) ignoring the cases in which the code fails...

Style:

I don't see the benefit to the function type declarations all at the top separated from their implementations where they could have had some minor self-documentation effect.

You seem to be following the Haskell tradition of using one-letter symbols and minimal explanatory comments, as if it was obvious from the context that a1 is the first element of a progression and d is its delta and n is the number of elements.  To me, these things were not all obvious, especially when n is either n1 or n2 and the '1' in n1 has nothing to do with the '1' in a1.  I think that n' and n would have been a more idiomatic naming than n1 and n2, since they are variants of each other. Function header comments describing the input arguments would not have been out of place, nor would spelling out "delta" and "limit", but that may be an "m o" (meaning "minority opinion" -- obviously).

The formulas used in pSum are sufficiently complicated and their syntax not quite algebraic, so their intent is obscured. A comment explaining the intent in plain language like "multiplying ... first and last elements..." or pure algebra would help.

Since both aN and pSum are short and used only within pSum and sumProgressions2, respectively, I'd have opted for defining them under a where clause. In the case of pSum, that allows lim to be referenced in the parent scope so it doesn't need to be explicitly passed. This makes the structure of the code more readable, making it clear that aN and pSum serve sumProgressions2 and sumProgressions2 only. I'm guessing (mostly from the presence of a1) that this may not have been your intent, in which case you should have made that intent clear by exporting these functions or showing other uses within the module.

In fact, the purpose of a1 is confounded by the fact that a1 is only ever passed the same value as d by the 3 callers of pSum, and since pSum isn't exported from the module, those seem to be the only cases. From that perspective, a1 is only used once, in an equality test that always passes, so it seems that you could eliminate it and with it half the complexity of pSum.

Even if your intent is to provide pSum as a useful function outside of sumProgressions2, the usage of pSum in sumProgressions2 is so specialized and falls so cleanly into the "simplified" case that it still warrants its own separate truly simplified pSum function that takes no a1 argument.

Whether the existence of another more general pSum implementation is justified and whether its a1 == d case is worth optimizing -- or (as I suspect) similar simplification applies equally to the general case -- is outside the scope of the current problem.

Yet I think that there is a point to be made here about over-generalization.
You could argue that you are doing a good thing by providing and using a more general solution that does not require a1 to equal d, but I don't think that argument holds up. It sounds like the same argument that justifies writing sumProgressions2 as a general solution that does not depend on the values 3, 5, and 1000. But consider the following:

sumProgressions3_5_1000 3   5 1000 = correctAnswerForEuler1
sumProgressions3_5_1000 d1 d2 lim   = let d3 = d1 * d2
    in (pSum d1 d1 lim) + (pSum d2 d2 lim) - (pSum d3 d3 lim)

or even

sumProgressions3 3  d2 lim = specialCaseOptimizedFor3 d2 lim
sumProgressions3 d1 d2 lim = let d3 = d1 * d2
    in (pSum d1 d1 lim) + (pSum d2 d2 lim) - (pSum d3 d3 lim)

Do you consider these to have the same benefits of generality as your original solution?
To me, if (a1==d) in pSum defeats the purpose of the generalized solution just as much as this last example does. Your pSum just hard-codes for an arbitrary argument relationship rather than for an arbitrary argument value, but it's still arbitrary hard-coding for an arbitrary case.

There is danger in over-generalization. Testing and correctness is more difficult for a general function than for a more constrained or hard-coded function. Case in point,  the bug triggered by arguments 3 6 20 does not effect cases like 3 5 1000.  Also, optimization may be completely different when targeting all cases vs. average or typical cases vs. the special case that is going to be exercised in the benchmark.  Case in point, it was only in considering an optimization that would benefit cases like 3 6 20 while slightly penalizing cases like 3 5 1000 that I discovered that I wasn't really optimizing this new case at all -- I was correcting it. And given the context/contest, I wasn't sure that optimizing or correcting the 3 6 20 case was really "in scope". I decided that what was in scope was a style critique along the lines of:

  The good work of substituting code that works in many general cases for code that only needs to handle a specific case may not be worthwhile unless the code is correct for the general case or guards against the cases it does not handle correctly.

You've got a good solution to the problem of sumProgressions2 3 5 1000 disguised as a faulty solution to the problem of sumProgressions2 d1 d2 limit. So, technically, you'd be in better shape if you had been less ambitious.

Optimization:

There's not much to say here, except that the correction for the 3 6 20 case (arguably out of scope and counter-productive to the optimization of the 3 5 1000 solution) was originally mis-identified as a missing optimization. As it turns out, there seem to be multiple edge cases that require either more processing or less processing than 3 5 1000.

Eliminating a1 from pSum would help to focus the effort on the calculation of n1 and its use rather than on dead code.
As far as I can see, there's no better formulation -- no reason to prefer (n*n+n) over n*(n+1) or to prefer (lim - (lim `mod` d))*(n+1) over d*(lim `div` d)*(n+1), given that n+1 requires (lim `div` d) to be calculated in either case. But I could be wrong, and easily proven wrong by some quick benchmarks. So, your solution seems optimal within the current structure of sumProgressions2 as 3 calls to pSum.

The only other way I could see to further optimize the code would be IF there was an alternative way of expressing the third call to pSum so that it eliminated some operations in favor of re-using sub-expressions from the first two pSum calls. I don't know if this is possible. What I'm imagining is something like a reformulation of the pSum functions, especially the one used in the 3rd call, that took advantage of a fact like (d1*d2)*(d1*d2) == (d1*d1)*(d2*d2) (assuming that result to be useful) to reuse (d1*d1) and (d2*d2) values calculated already in the first two (reformulated) pSum calls.  I don't know enough about Haskell internal optimizations to know if it can access function results "recently memoized" in called "sibling" functions. If not, I'd guess you would pass the useful sub-expressions like (d1*d1) from sumProgressions2 into the pSum calls. This whole idea could turn out to be too ugly for serious consideration, so you might be better off where you are.


Simple Random TicTacToe Generator I just finished building a simple random Tic Tac Toe generator. The program will display 3 rows of a random numbers 0-1 and will print a message when 3 of the same numbers align. The program works perfectly, to my knowledge.

I am posting this code here in hopes that I can gain some advice/tips in regards to optimization and/or simplification.

import random

row1 = [round(random.uniform(0, 1)), round(random.uniform(0, 1)), round(random.uniform(0, 1))]
row2 = [round(random.uniform(0, 1)), round(random.uniform(0, 1)), round(random.uniform(0, 1))]
row3 = [round(random.uniform(0, 1)), round(random.uniform(0, 1)), round(random.uniform(0, 1))]

print(row1)
print(row2)
print(row3)

# If statements for all 3 rows
if (row1[0] == row1[1]) and [row1[1] == row1[2]] and (row1[2] == row1[0]):
    print("All " + str(row1[0]) + "'s in top row!")
if (row2[0] == row2[1]) and [row2[1] == row2[2]] and (row2[2] == row2[0]):
    print("All " + str(row2[0]) + "'s in middle row!")
if (row3[0] == row3[1]) and [row3[1] == row3[2]] and (row3[2] == row3[0]):
    print("All " + str(row3[0]) + "'s in bottom row!")

# If statements for all 3 columns
if (row1[0] == row2[0]) and [row2[0] == row3[0]] and (row3[0] == row1[0]):
    print("All " + str(row1[0]) + "'s in left column!")
if (row1[1] == row2[1]) and [row2[1] == row3[1]] and (row3[1] == row1[1]):
    print("All " + str(row1[1]) + "'s in middle column!")
if (row1[2] == row2[2]) and [row2[2] == row3[2]] and (row3[2] == row1[2]):
    print("All " + str(row1[2]) + "'s in right column!")

# If statements for diagonals
if (row1[0] == row2[1]) and (row2[1] == row3[2]) and (row3[2] == row1[0]):
    print("All " + str(row1[0]) + "'s in diagonal!")
if (row1[2] == row2[1]) and (row2[1] == row3[0]) and (row3[0] == row1[2]):
    print("All " + str(row1[2]) + "'s in diagonal!")

Some suggestions:

There’s a lot of repetition in the code for generating each of the rows. Repetition is generally a bit of a code smell; you could improve this by using a list comprehension for each row, for example:

row1 = [round(random.uniform(0, 1)) for _ in range(3)]
row2 = [round(random.uniform(0, 1)) for _ in range(3)]
row3 = [round(random.uniform(0, 1)) for _ in range(3)]

By nesting the list comprehension and using tuple unpacking, we can reduce repetition further:

row1, row2, row3 = [
    [round(random.uniform(0, 1)) for _ in range(3)]
    for _ in range(3)
]

Your code uses 1.0 and 0.0 for the two values, whereas convention is usually to use O and X. If you use random.choice instead of random.uniform, you can get this instead:

row1, row2, row3 = [
    [random.choice(['O', 'X']) for _ in range(3)]
    for _ in range(3)
]

It’s good that the rest of your code copes with this gracefully – it doesn’t actually care what values you’re putting in the cells.

Once you’ve done that, you can tidy up the printing of the rows so you don't see the square brackets/commas from Python’s list syntax.
There are lots of if statements with multiple conditions and repetition, which is a bit messy. It would be cleaner if you defined a function that checks if a group of values are all equal. Then you could write:

if all_equal(row1[0], row2[0], row3[0]):
    print("All %s's in top row!" % row1[0])

That makes the conditions both shorter and easier to read.
Your script says “All X's in diagonal”, regardless of which diagonal it actually is. That’s less clear than it could be, and means it could potentially print the same sentence twice. I’d recommend using different terms to describe each diagonal – perhaps primary and secondary diagonal?


Implementation of Dijkstra's algorithm in C++ This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I store -1 if there weren't any edges found yet. I am not sure if it is okay.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define MAX_LENGTH 10000

int dijkstra(vector<vector<int>> graph, int source, int target) {
    size_t number_of_nodes = graph.size();
    vector<int> visited;
    map<int, int> lengths_to_nodes; // keeps pairs of lengths like 0:0, 1:20, 2:40

    //fill with max lengths and set source as 0 eg. 0:0 1:10000, 2:10000...
    for (int i = 0; i < number_of_nodes; ++i) {
        lengths_to_nodes.insert(make_pair(i, MAX_LENGTH));
    }
    lengths_to_nodes[source] = 0;

    //set actual node we look path from
    int actual_node = source;

    while (visited.size() < number_of_nodes) {
        //keep track of the shortest path found from this node because it will be
        //the next one we will looking for path from
        //if there was no paths from this node then go back
        int the_shortest_found_now = -1;    /***  IS IT OKEY?  ***/
        int the_shortest_found_now_length = MAX_LENGTH;

        for (int actual_target = 0; actual_target < number_of_nodes; ++actual_target) {
            if (graph[actual_target][actual_node] > 0) {
                int new_length = graph[actual_target][actual_node] + lengths_to_nodes.find(actual_node)->second;
                if (lengths_to_nodes.find(actual_target)->second > new_length) {
                    lengths_to_nodes.find(actual_target)->second = new_length;
                }
                if (new_length < the_shortest_found_now_length) {
                    the_shortest_found_now_length = new_length;
                    the_shortest_found_now = actual_target;
                }
            }
        }
        if (the_shortest_found_now == -1) {
            //if there was no outgoing edges
            actual_node = *(visited.end() - 1);
            visited.erase(visited.end() - 1, visited.end());
        }
        else {
            actual_node = the_shortest_found_now;
            visited.push_back(the_shortest_found_now);
        }
    }
    return lengths_to_nodes.find(target)->second;
}

int main() {
    vector<vector<int>> graph =
            {{{0, 0, 0, 0, 0, 0, 20, 0,},
                     {20, 0, 0, 0, 50, 50, 0, 0,},
                     {0, 0, 0, 10, 0, 0, 0, 0,},
                     {80, 0, 10, 0, 0, 40, 0, 0,},
                     {0, 0, 0, 0, 0, 0, 0, 0,},
                     {0, 10, 10, 0, 30, 0, 0, 0,},
                     {90, 0, 0, 20, 0, 0, 0, 0,},
                     {0, 0, 20, 0, 0, 0, 0, 0,},
             }};

    cout << dijkstra(graph, 0, 7) << endl;

    return 0;
}

Design

So not really Dijkstra algorithm.

while (visited.size() < number_of_nodes)

This condition may not be met in all graphs (if there is a subset of nodes not connected to other nodes).

Also Dijkstra uses two lists.

List of nodes that have been visited. (starts empty)
A sorted frontier list.

You have the 1st list but seem to cobbling the second list out of thin air each iteration.

Code Review.

int dijkstra(vector<vector<int>> graph, int source, int target) {

Sure. You are returning the shortest length from source to target. But would it not be more interesting to return the path most of the time.

Also a graph being a vector of vector of int is a bit restrictive. You could have created a concept of a graph. Then templatized the algorithm based on the concept. Then writing a wrapper for vector of vector of int to implement the concept would have been trivial.

// Concept.
Graph
    Node const& getNode(int id) const // returns a reference to a node.

Node
    int edgeCount() const             // returns number of outbound edges
    Edge const& getEdge(int id) const // returns a reference to an edge

Edge
    int getDst() const               // returns the id of the dst vertices.
    int getCost() const              // returns the cost from this node to dst.

Algorith for Dijkstra

template<typename Graph>
vector<int> dijkstra(Graph const& graph, int start, int end)
{
    std::vector<int>                seen;
    std::priority_queue<Frontier>   frontierList;

    frontierList.push({start, 0, {start}});

    while(!frontierList.empty())
    {
        Frontier  head = frontierList.top();
        frontierList.pop();

        if (head.location == end) {
            return head.path.append(end);
        }

        if (std::find(std::begin(seen), std::end(seen), head.location) != std::end(seen)) {
            continue;
        }

        for(int loop=0;loop < graph.getNode(head.location).edgeCount(); ++loop) {
            auto const& edge = graph.getNode(head.location).getEdge(loop);
            frontierList.push({edge.getDst(),
                                 head.cost + edge.getCost(),
                                 head.path.append(head.location)});
        }
    }
    return {}; // empty path as none was found.
}


String compression implementation in C# I wrote a method that reduces a string like aabcccccaaa to a2b1c5a3

My implementation:

string Compress(string str)
{
    StringBuilder builder = new StringBuilder();
    using(TextReader reader = new StringReader(str))
    {
        while(reader.Peek() != - 1){
            char c = (char)reader.Read();
            int n = 1;
            while(reader.Peek() == c) {
                reader.Read();
                n++;
            }
            builder.AppendFormat("{0}{1}",c,n);
        }
    }
    return builder.ToString();
}

What do you think about this, is there a better way to do this?

You can use a regular expression to match a range of repeated characters and replace it with the character and the count:

public static string Compress(string str) {
  return Regex.Replace(str, @"(.)\1*", m => m.Groups[1].Value + m.Value.Length);
}

If that is better or not is up for debate, but it is at least a lot shorter.

You can also make it simpler using a regular loop and access the characters by index instead of using a StringReader. That makes it easier to compare the characters next to each other:

public static string Compress(string str) {
  StringBuilder builder = new StringBuilder();
  for (int i = 1, cnt = 1; i <= str.Length; i++, cnt++) {
    if (i == str.Length || str[i] != str[i - 1]) {
      builder.Append(str[i - 1]).Append(cnt);
      cnt = 0;
    }
  }
  return builder.ToString();
}


Return union and complement of three sets I would be especially happy to hear opinions about complement_union.
The rest of the code is just there to test the output.

program test_complement_union
    implicit none(type, external)

    call assert(all([3, 5] == complement_union([1, 2, 3], [1, 2], [5])))
    call assert(all([2, 3, 4] == complement_union([1, 2, 3], [1], [4])))
    call assert(all([1, 3, 5] == complement_union([1, 2, 3], [2], [5])))
contains
    !> Merge C into A and remove values that are in B.
    !> The result can be written with set notation as A ∪ C / B.
    !> Preconditions (not tested!):
    !>      1. B is a subset of A
    !>      2. A and C are disjoint
    !>      3. B and C are disjoint
    !>      4. A, B, and C are sorted.
    pure function complement_union(A, B, C) result(D)
        integer, intent(in) :: A(:), B(:), C(:)
        integer :: D(size(A) + size(C) - size(B))

        ! We will index as A(i), B(j), C(k), D(l)
        integer :: i, j, k, l

        i = 1
        j = 1
        k = 1
        l = 1
        do while(l <= size(D))
            ! Only indices from C have to be added to A
            ! We use assumption that B is a subset of A
            if (i > size(A)) then
                D(l) = C(k)
                k = k + 1
                l = l + 1
            ! Neither indices from B have to be deleted in A
            ! nor indices from C have to be added from C to A.
            else if (j > size(B) .and. k > size(C)) then
                D(l) = A(i)
                i = i + 1
                l = l + 1
            ! No more indices from B have to be deleted in A
            else if (j > size(B)) then
                if (A(i) < C(k)) then
                    D(l) = A(i)
                    i = i + 1
                    l = l + 1
                else if (A(i) > C(k)) then
                    D(l) = C(k)
                    k = k + 1
                    l = l + 1
                end if
            ! No more indices have to be added from C to A
            else if (k > size(C)) then
                if (A(i) /= B(j)) then
                    D(l) = A(i)
                    i = i + 1
                    l = l + 1
                else
                    i = i + 1
                    j = j + 1
                end if
            ! Normal case:
            ! Merge C sorted into A excluding values from B.
            else if (A(i) < C(k)) then
                if (A(i) /= B(j)) then
                    D(l) = A(i)
                    i = i + 1
                    l = l + 1
                else
                    i = i + 1
                    j = j + 1
                end if
            else if (A(i) > C(k)) then
                if (A(i) /= B(j)) then
                    D(l) = C(k)
                    k = k + 1
                    l = l + 1
                else
                    D(l) = C(k)
                    i = i + 1
                    j = j + 1
                    k = k + 1
                    l = l + 1
                end if
            end if
        end do
    end function

    pure subroutine assert(cond)
        logical, intent(in) :: cond
        if (.not. cond) error stop
    end subroutine
end program
```

This code has two limitations, as I see it:

in treating in a single go the combination of three sets, it gives rise to a high cyclomatic complexity: a dozen if statements (including the while) in a single function. This circumstance limits the readability and maintainability of the code. It also makes it less extensible to more general cases.
the assumption that B is a subset of A and C is disjoint from either is very particular, and likely to limit the reuse of the code elsewhere.

As a minor point, the assertions stop the program in case a problem is detected but they do not indicate which test fails, or if other tests would have failed, which comes in handy in debug.
The input vectors are assumed to be sorted in increasing order. If that were not the case, one could do that first, and increase the generality of the code further.
Leaving aside for a moment the possible generalization of the code, by splitting the operation into a subtraction of B from A and a subsequent addition of C, the complexity drops drastically. Instead of a single pure function with 55 lines of code (header and declarations excluded) and 12 branching points (if and while), one can write three pure functions, with 2, 11, and 21 lines of code and only 0, 2, and 3 branching points, respectively:
program test_complement_union

    implicit none(type, external)

    call assert( "t1", all([3, 5]       == complement_union([1, 2, 3], [1, 2], [5]      )))
    call assert( "t2", all([2, 3, 4]    == complement_union([1, 2, 3], [1]   , [4]      )))
    call assert( "t3", all([1, 3, 5]    == complement_union([1, 2, 3], [2]   , [5]      )))
    call assert( "t4", all([1, 4, 5, 6] == complement_union([1, 2, 3], [2, 3], [4, 5, 6])))

  contains

    !> Merge C into A and remove values that are in B.
    !> The result can be written with set notation as A ∪ C / B.
    !> Preconditions (not tested!):
    !>      1. B is a subset of A
    !>      2. A and C are disjoint
    !>      3. B and C are disjoint
    !>      4. A, B, and C are sorted.
    pure function complement_union(A, B, C) result(D)
      integer, intent(in) :: A(:), B(:), C(:)
      integer :: A_B( size(A) - size(B) )
      integer :: D  ( size(A) + size(C) -size(B) )
      A_B  = subtract_subset(A,B)
      D    = union_disjoint_sets(A_B,C)
    end function complement_union

    !> Subtract a proper ordered subset from a given ordered set
    pure function subtract_subset( A, B ) result( C )
      integer, intent(in) :: A(:), B(:)
      integer :: C ( size(A) - size(B) ), iA, iB, iC
      iC = 0
      iA = 1
      !.. All elements of B are expected to be found in A
      do iB = 1, size(B)
         !.. Copies the elements of A between consecutive
         !   occurrences of B elements
         do while( A(iA) /= B(iB) )
            iC = iC + 1
            C(iC) = A(iA)
            iA = iA + 1
         enddo
         !.. Skips the B element
         iA = iA + 1
      enddo
      !.. Copies the elements of A past the last element of B
      if( iA <= size(A) ) C(iC+1:) = A(iA:)
    end function subtract_subset

    !> Computes the union of non-empty disjoint ordered sets
    pure function union_disjoint_sets( A, B ) result( C )
      integer, intent(in) :: A(:), B(:)
      integer :: C( size(A) + size(B) )
      integer :: iA, iB, iC, nA, nB
      nA = size(A)
      nB = size(B)
      iA = 1
      iB = 1
      iC = 0
      C  = 0
      !.. Takes an element from either A or B
      !   until one of the sets is empty
      do while( iA <= nA .and. iB <= nB )
         iC = iC + 1
         if( A(iA) <= B(iB) )then
            C(iC) = A(iA)
            iA = iA + 1
         else
            C(iC) = B(iB)
            iB = iB + 1
         endif
      end do
      !.. Copies to C the residual elements in
      !   the remaining non-empty set
      if( iA <= nA )then
         C(iC+1:)=A(iA:)
      else
         C(iC+1:)=B(iB:)
      endif
    end function union_disjoint_sets

    subroutine assert(msg,cond)
      use, intrinsic :: iso_fortran_env, only : OUTPUT_UNIT
      character(len=*), intent(in) :: msg
      logical         , intent(in) :: cond
      write(OUTPUT_UNIT,"(a)",advance="no") msg//" - "
      if( cond )then
         write(OUTPUT_UNIT,"(a)") "passed"
      else
         write(OUTPUT_UNIT,"(a)") "FAILED"
      endif
    end subroutine assert

  end program test_complement_union

If the restrictions on the three sets, A, B, and C are removed, except for their being ordered, in general, the size of ( A U C ) / B will be different from size(A)-size(B)+size(C). Furthermore, ( A / B ) U C /= ( A U C ) / B. Let's consider the latter operation, which is a bit more challenging. If one does not want give up automatic arrays, then I think there is no alternative to having trailing "empty" entries in the result (e.g., zeros). Even in this case, it is best to split the work into functions that provide two disjoint sets to be merged. The subtraction here is more complicated because in general B would not be a subset of A and C may have elements in common with both B and A. Therefore, one must first figure out the A/B, C/B and C/B/A, by means of a difference function, and then merge the result, which is simple, since the sets are disjoint :
$$( A \cup C ) / B = ( A / B ) \cup ( ( C / B ) / A ) $$
where $$( A / B ) \cap ( ( C / B ) / A ) = \varnothing$$
Here's a sketch of the idea
program test_complement_union

    implicit none(type, external)

    call assert( "t1", all([3, 5, 0, 0]       == complement_union([1, 2, 3], [1, 2], [5]      )))
    call assert( "t2", all([2, 3, 4, 0]       == complement_union([1, 2, 3], [1]   , [4]      )))
    call assert( "t3", all([1, 3, 5, 0]       == complement_union([1, 2, 3], [2]   , [5]      )))
    call assert( "t4", all([1, 3, 5, 0, 0, 0] == complement_union([1, 2, 3], [2, 9], [1, 2, 5])))

  contains

    !.. Assumes input vectors are sorted (!)
    !   If that is not the case, the vectors should
    !   be sorted into auxiliary arrays
    !..
    function complement_union(A, B, C) result(D)
      integer, intent(in) :: A(:), B(:), C(:)
      integer :: A_B(size(A))
      integer :: C_B(size(C))
      integer :: C_AB(size(C))
      integer :: D (size(A) + size(C))
      A_B  = difference(A,B)
      C_B  = difference(C,B)
      C_AB = difference(C_B,A_B)
      D    = union_disjoint_sets(A_B,C_AB)
    end function complement_union

    !.. Computes the difference between the two sets,
    !   generating a set with the same size as the first
    !   with trailing zeros for the erased fields.
    function difference( A, B ) result( C )
      integer, intent(in) :: A(:), B(:)
      integer :: C ( size(A) ), iA, iB, iC, nA, nB, nC
      nA=count(A/=0)
      nB=count(B/=0)
      if(nB==0)then
         C=A
         return
      endif
      iC=0
      iB=1
      nC=nA
      outer: do iA = 1, nA
         do while( B(iB) < A(iA) )
            iB = iB + 1
            if( iB > nB) exit outer
         end do
         if( B(iB) == A(iA) )then
            nC=nC-1
            cycle outer
         endif
         iC = iC + 1
         C(iC) = A(iA)
      enddo outer
      if( iB > nB ) C(iC+1:nC) = A(iA:nA)
      if( nC < size(A) ) C(nC+1:) = 0
    end function difference

    !.. Computes the union of disjoint sets
    pure function union_disjoint_sets( A, B ) result( C )
      integer, intent(in) :: A(:), B(:)
      integer :: C( size(A) + size(B) )
      integer :: iA, iB, iC, nA, nB, nC
      nA = count( A /= 0 )
      nB = count( B /= 0 )
      nC = nA + nB
      iA = 1
      iB = 1
      iC = 0
      C  = 0
      do while( iA <= nA .and. iB <= nB )
         iC = iC + 1
         if( A(iA) <= B(iB) )then
            C(iC) = A(iA)
            iA = iA + 1
         else
            C(iC) = B(iB)
            iB = iB + 1
         endif
      end do
      if( iA <= nA )then
         C(iC+1:nC)=A(iA:nA)
      else
         C(iC+1:nC)=B(iB:nB)
      endif
    end function union_disjoint_sets

    subroutine assert(msg,cond)
      use, intrinsic :: iso_fortran_env, only : OUTPUT_UNIT
      character(len=*), intent(in) :: msg
      logical         , intent(in) :: cond
      write(OUTPUT_UNIT,"(a)",advance="no") msg//" - "
      if( cond )then
         write(OUTPUT_UNIT,"(a)") "passed"
      else
         write(OUTPUT_UNIT,"(a)") "FAILED"
      endif
    end subroutine assert

  end program test_complement_union

PS:
For folks not familiar with the simple syntax of modern Fortran, I suggest the following quick modern Fortran tutorial.


Getting a value from shared preferences I use this code to get values from SharedPreferences.

public static String getSharedPreferenceValue(Context context, String key) {
    SharedPreferences sp = context.getSharedPreferences(
    Utility.PREFERENCES_NAME, Context.MODE_PRIVATE);
    String value = sp.getString(key, Utility.EMPTY_STRING);
    return value;
}

Will this static method keep context (Activity) all time and are there memory leaks?

Is there a better way to get values from SharedPreferences?
I'm looking for the best way to do this.

Will this static method keep context (Activity) all time and are there memory leaks?

A memory leak in Java is a situation where some objects are not used by application any more, but GC fails to recognize them as unused. As a result, these objects remain in memory indefinitely reducing the amount of memory available to the application.

  Will this static method keep context (Activity)

SharedPreference could fail:

  Unlike commit(), which writes its preferences out to persistent storage synchronously, apply() commits its changes to the in-memory SharedPreferences immediately but starts an asynchronous commit to disk and you won't be notified of any failures. If another editor on this SharedPreferences does a regular commit() while a apply() is still outstanding, the commit() will block until all async commits are completed as well as the commit itself.

http://developer.android.com/reference/android/content/SharedPreferences.Editor.html

  Are there memory leaks ?

No.

  Is there a better way to get values from SharedPreferences? I'm looking for the best way to do this.

SharedPreferences - Best method

Java provides many ways of storing application data. One of those ways leads us to the SharedPreferences object which is used to store private primitive data in key-value pairs.

All logic are based only on three simple classes:

SharedPreferences
SharedPreferences.Editor
SharedPreferences.OnSharedPreferenceChangeListener

SharedPreferences

SharedPreferences is main of them. It's responsible for getting (parsing) stored data, provides interface for getting Editor object and interfaces for adding and removing OnSharedPreferenceChangeListener

To create SharedPreferences you will need Context object (can be an application Context)
getSharedPreferences method parses Preference file and creates Map object for it
You can create it in few modes provided by Context, it's strongly recommended to use MODE_PRIVATE because creating world-readable/writable files is very dangerous, and likely to cause security holes in applications.

Editor

SharedPreferences.Editor is an Interface used for modifying values in a SharedPreferences object. All changes you make in an editor are batched, and not copied back to the original SharedPreferences until you call commit() or apply()

Use simple interface to put values in Editor
Save values synchronous with commit() or asynchronous with apply which is faster. In fact of using different threads using commit() is safer. Thats why I prefer to use commit().
Remove single value with remove() or clear all values with clear()

Performance & Tips

SharedPreferences is a Singleton object so you can easily get as many references as you want, it opens file only when you call getSharedPreferences first time, or create only one reference for it.
As SharedPreferences is a Singleton object you can change any of It's instances and not be scared that their data will be different
Remember the larger the Preference object is the longer get, commit, apply, remove and clear operations will be. So it's highly recommended to separate your data in different small objects.
Your Preferences won't be removed after Application update. So there are cases when you need to create some migration scheme. For example you have Application that parse local JSON in start of application, to do this only after first start you decided to save boolean flag wasLocalDataLoaded. After some time you updated that JSON and released new application version. Users will update their applications but they will not load new JSON because they already done it in first application version.
SharedPreferences are stored in an xml file in the app data folder


Random Coin Toss in Haskell Learn You a Haskell gives an exercise to implement the following function:

-- make a function that simulates tossing a function 3 times
import System.Random

tossCoin3 :: Int -> (Bool, Bool, Bool)
tossCoin3 x =
    let (num1, gen1) = random (mkStdGen x)   :: (Int, StdGen)
        (num2, gen2) = random (gen1)         :: (Int, StdGen)
        (num3, _)    = random (gen2)         :: (Int, StdGen)

    in (convertToBool num1, convertToBool num2, convertToBool num3)
    where convertToBool y = if y `mod` 2 == 0 then True else False

I would've mapped a list of [num1, num2, num3] with the convertToBool, and then convert to a 3-tuple. But then I saw this post.

Please critique my implementation.

Converting a Bool to a Bool with an if

if tests Bool values and returns results. You’re using it to return True if the input is True, and False if the input is False:

convertToBool y = if y `mod` 2 == 0 then True else False

But that’s just the identity function. You can remove the if:

convertToBool y = y `mod` 2 == 0

Useless parentheses

random (gen1)
random (gen2)

Generating random Ints rather than the type you wish to get directly

You’re using random to generate an Int. That’s fine if you want an Int—but you want a Bool. Sure, you can calculate a Bool out of one, but random can also give you a Bool directly. This would simplify your implementation.

I feel it’s necessary to point out the dangers of limiting random numbers to a range with modulo. In this case, it’s not actually a problem, but pretend you want to generate a number between 0 and 6, and the random number generator you have gives you numbers between 0 and 9. If you used modulo, you’d map:

0, 6 --> 0
1, 7 --> 1
2, 8 --> 2
3, 9 --> 3
4    --> 4
5    --> 5
6    --> 6

That’s not a very even distribution. The problem arises because 7 and 10 do not share a factor. It’s not relevant to you because you’re trying to generate something in the range 0 to 1 (two values) and two is a factor of the number of values in Int, but it’s something to be aware of nonetheless.

Dependence on mkStdGen

Right now, you let the user pass in a seed that is then passed to mkStdGen. That works, I suppose, but it would be more flexible if you pushed that responsibility to the user, because then the user can create an StdGen however they desire (with, say, getStdGen). Your signature would then look like this:

coinToss3 :: StdGen -> (Bool, Bool, Bool)

You could even change your definition to allow any RandomGen instance:

coinToss3 :: (RandomGen g) => g -> (Bool, Bool, Bool)

Potential cleanup with MonadRandom and Applicative

At your current point in Learn You A Haskell, you haven’t learned about Monad or Applicative yet, so you may want to ignore this for now and take a look at it later, but using MonadRandom and Applicative, your code can be considerably shortened:

import Control.Applicative
import Control.Monad.Random

coinToss3 :: (RandomGen g) => g -> (Bool, Bool, Bool)
coinToss3 = evalRand $ (,,) <$> random <*> random <*> random


PowerShell script to Find and Replace in Word Document, including Header, Footer and TextBoxes within I have written a PowerShell script to find and replace text within the whole document, including in the Headers and Footers as well as inside TextBoxes within the Headers.
There was lots of trial and error to get this to work and it is a bit cumbersome and probably not very efficient.
Any suggestion as to how make it better and go faster would be very much appreciated.
In particular, I'm sure there should be a better approach to get to the Headers TextBoxes but I couldn't figure it out so far.
In case it wasn't obvious, I'm not a professional coder, so please excuse the style or lacking thereof... :-)
Thanks!

$folderPath = "C:\Users\User\Folder\*" # multi-folders: "C:\fso1*", "C:\fso2*"
$fileType = "*.doc" # *.doc will take all .doc* files

$word = New-Object -ComObject Word.Application
$word.Visible = $false

Function findAndReplace($Text, $Find, $ReplaceWith) {
    $matchCase = $true
    $matchWholeWord = $true
    $matchWildcards = $false
    $matchSoundsLike = $false
    $matchAllWordForms = $false
    $forward = $true
    $findWrap = [Microsoft.Office.Interop.Word.WdReplace]::wdReplaceAll
    $format = $false
    $replace = [Microsoft.Office.Interop.Word.WdFindWrap]::wdFindContinue

    $Text.Execute($Find, $matchCase, $matchWholeWord, $matchWildCards, `
                  $matchSoundsLike, $matchAllWordForms, $forward, $findWrap, `
                  $format, $ReplaceWith, $replace) > $null
}

Function findAndReplaceWholeDoc($Document, $Find, $ReplaceWith) {
    $findReplace = $Document.ActiveWindow.Selection.Find
    findAndReplace -Text $findReplace -Find $Find -ReplaceWith $ReplaceWith
    ForEach ($section in $Document.Sections) {
        ForEach ($header in $section.Headers) {
            $findReplace = $header.Range.Find
            findAndReplace -Text $findReplace -Find $Find -ReplaceWith $ReplaceWith
            $header.Shapes | ForEach-Object {
                if ($_.Type -eq [Microsoft.Office.Core.msoShapeType]::msoTextBox) {
                    $findReplace = $_.TextFrame.TextRange.Find
                    findAndReplace -Text $findReplace -Find $Find -ReplaceWith $ReplaceWith
                }
            }
        }
        ForEach ($footer in $section.Footers) {
            $findReplace = $footer.Range.Find
            findAndReplace -Text $findReplace -Find $Find -ReplaceWith $ReplaceWith
        }
    }
}

Function processDoc {
    $doc = $word.Documents.Open($_.FullName)
    findAndReplaceWholeDoc -Document $doc -Find "THIS" -ReplaceWith "THAT"
    $doc.Close([ref]$true)
}

$sw = [Diagnostics.Stopwatch]::StartNew()
$count = 0
Get-ChildItem -Path $folderPath -Recurse -Filter $fileType | ForEach-Object {
  Write-Host "Processing \`"$($_.Name)\`"..."
  processDoc
  $count++
}
$sw.Stop()
$elapsed = $sw.Elapsed.toString()
Write-Host "`nDone. $count files processed in $elapsed"

$word.Quit()
$word = $null
[gc]::collect()
[gc]::WaitForPendingFinalizers()

COM Automation (which is what you are using) is always going to be slow. There's not much you can do about that except to try find new ways to do what you want with as few operations as possible.

An alternative you could investigate is the Open XML SDK. I've never tried it myself, but it is supposed to be a lot faster than COM Automation.

The Open XML SDK is a .NET library, so there should be no problem calling it from PowerShell, but you will have to translate the example code from C# or VB.NET into PowerShell.

Here's an example for Excel which you could adapt. Or maybe you could find an actual Word example. I didn't search very hard.

You should also check out Open-XML-PowerTools. This is a PowerShell wrapper for the Open XML SDK. Maybe it will do what you want already.

Here's a screencast that shows searching and replacing using  Open-XML-PowerTools.


Decrypt multiple 10Mb files with defined password One operation of my Android project is to decrypt one file (chosen in a set of ~30 files for pagination1) of ~10 Mb each and I do this with the following:

fun InputStream.cipherDecryptWithSessionPwd(password: String): String {
    var payloadArray: List<Byte>? = this.readBytes().toList()
    var salt = payloadArray?.subList(0,32)
    var spec: Rfc2898DeriveBytes? = Rfc2898DeriveBytes(password, salt?.toByteArray(), 50000)
    var realData = payloadArray?.subList(32, payloadArray.size)

    val keyBytes = spec?.getBytes(256 / 8)
    val ivBytes = spec?.getBytes(128 / 8)

    var cipher: Cipher? = Cipher.getInstance("AES/CFB/PKCS7Padding")
    var secretKey: SecretKeySpec? = SecretKeySpec(keyBytes, "AES")
    var ivSpec: IvParameterSpec? = IvParameterSpec(ivBytes)
    cipher?.init(Cipher.DECRYPT_MODE, secretKey, ivSpec)
    var byteArrayInputStream: ByteArrayInputStream? = ByteArrayInputStream(realData?.toByteArray())
    var decipherStream: CipherInputStream? = CipherInputStream(byteArrayInputStream, cipher)

    val d = BufferedReader(InputStreamReader(decipherStream, Charsets.UTF_8), 0xFFFF)
    return d.readLine()
}

The problem with this is that at around the 72nd time2 I repeat the operation Android kills my application because it runs out of memory3.

This is the second version of the decryption function, the first one caused the OOM error around the 25th time the operation was made. The problem here clearly is the number of conversions done (InputStream -> ByteArray -> List<Byte> and others).

I don't know how to optimize more, the first version of the method was not mine and I never did encryption (and optimization) before.

Scenario (and what have been tried):
 1 - Files are stored encrypted on the device, can't have them decrypted but at runtime
 2 - With the decrypted result (JSON) I fill a model using [Gson] (https://github.com/google/gson), but the OOME seem to be thrown when my function is running (the exception points at the first line of the function)
 3 - Calculations are done and the model is disposed of when the next page is shown, then the whole operation has to be repeated
 # - We tried reducing the number of JSON "records" inside each file from 5000 per file to 1000 per file reducing the file size to 2 Mb but the problem persists

Notes:
 1 - We event tried reducing the pagination reaching files size to 2 Mb but the problem persists
 2 - This has to be done at least 130 times per session
 3 - With, Knox my application is the only one allowed to run on the device

I can't help too much as I don't have running code, but I can at least get rid of all List and Array conversions, that will make it run faster and reduce lot of memory garbage. I also removed all the optionals as immutability is our best friend :)

Is it ran once per stream and then it is closed or more than once per stream? There is no information about how stream is being handled and if it is closed properly. That can be issue.

fun InputStream.cipherDecryptWithSessionPwd(password: String): String {
    val payloadArray: ByteArray = this.readBytes()
    val salt = payloadArray.sliceArray(0 until 32)
    val spec = Rfc2898DeriveBytes(password, salt, 50000)
    val realData = payloadArray.sliceArray(32 until payloadArray.size)

    val keyBytes = spec.getBytes(256 / 8)
    val ivBytes = spec.getBytes(128 / 8)

    val cipher = Cipher.getInstance("AES/CFB/PKCS7Padding")
    val secretKey: SecretKeySpec? = SecretKeySpec(keyBytes, "AES")
    val ivSpec: IvParameterSpec? = IvParameterSpec(ivBytes)
    cipher.init(Cipher.DECRYPT_MODE, secretKey, ivSpec)
    val byteArrayInputStream = ByteArrayInputStream(realData)
    val decipherStream = CipherInputStream(byteArrayInputStream, cipher)

    val d = BufferedReader(InputStreamReader(decipherStream, Charsets.UTF_8), 0xFFFF)
    return d.readLine()
}

Edit:

I was thinking what you could cache and only possible variable is I guess cipher:

val cipher = Cipher.getInstance("AES/CFB/PKCS7Padding")

It probably won't speed up performance as I expect it to be cached factory method, but you can try putting variable outside of function anyway :)


Printing star greater symbol in Java I need to print this in Java, but I feel that my code is too big:

*
**
***
****
***
**
*

public static void main(String[] args) {

    for(int i=0; i<=3; i++) {
        for(int j=0; j<=i; j++) {
            System.out.print("*");
        }
        System.out.println();
    }

    for(int j=1; j<=3; j++) {
        for(int i=3; i>=j; i--) {
            System.out.print("*");
        }
        System.out.println();
    }
}

Here is a lovely way to do it using only one nested for-loop:
for (int i = 0; i < 7; i++) {
    for (int numStars = 0; numStars < 4 - Math.abs(3 - i); numStars++) {
        System.out.print("*");
    }
    System.out.println();
}

This uses the Math.abs function to perform the calculation of how many stars to print.
If we take a look at a plot of the classic Math.abs we can see that it looks useful. We need to flip it upside-down though, this is done by taking 4 - abs(x) which would look like this. Finally, we need to switch it to the right a bit, so we modify the input to the function call and end up with this: 4 - abs(3 - x)
Images courtesy of wolframalpha.com
4-abs(x)

4-abs(3 - x)

Finally, here is a very flexible solution, which also works with even numbers:
int rows = 20;
double maximumValue = Math.ceil(rows / 2.0);
double shifted = maximumValue - 1;
for (int i = 0; i < rows; i++) {
    int count = (int) (maximumValue - Math.abs(shifted - i));
    if (i >= rows / 2 && rows % 2 == 0) // slight fix for even number of rows
        count++;

    for (int numStars = 0; numStars < count; numStars++) {
        System.out.print("*");
    }
    System.out.println();
}

This will output:
*
**
***
****
*****
******
*******
********
*********
**********
**********
*********
********
*******
******
*****
****
***
**
*


Timestamp function with millisecond precision I want to be able to print timestamps with milliseconds precision and time_t doesn't provide this.  I also want the code to be portable, so operating specific functions are out.  ftime seems to be deprecated but there doesn't seem to be a general-purpose alternative to using ftime.

How could this be improved?

#include <stdio.h>
#include <string.h>
#include <sys\timeb.h>
#include <time.h>

static char* get_timestamp(char* buf) {
    struct timeb start;
    char append[100];
    if (buf) {
        ftime(&start);
        strftime(buf, 100, "%H:%M:%S", localtime(&start.time));

        /* append milliseconds */
        sprintf(append, ":%03u", start.millitm);
        strcat(buf, append);
    }
    return buf;
}

int main()
{
    char tmp[100];
    int countdown = 0;
    for (int i = 0; i < 10; i++, countdown = 0) {
        printf("%s\n", get_timestamp(tmp));
        while (countdown++ < 1000000)
            ;
    }
}

You state that operating specific functions are out, which I assume means that you don't want to use operating system specific system functions. However in this particular case that is actually hindering you from actually solving your task, as POSIX-based systems and Windows-based systems has two different ways of handling this.

Although the ftime is present in various operating system, it has been marked as obsolete as of POSIX.1-2008:

  4.2BSD, POSIX.1-2001.  POSIX.1-2008 removes the specification of ftime().

  This function is obsolete.  Don't use it.  If the time in seconds
  suffices, time(2) can be used; gettimeofday(2) gives microseconds;
  clock_gettime(2) gives nanoseconds but is not as widely available.

Further is the gettimeofday() also obsolete as of POSIX.1-2008, leaving only the clock_gettime() alternative, which is not as widely available. Most notably not present in Windows, as indicated in "Porting clock_gettime to windows".

On Windows there are some other options, but seems that most fall back to using QueryPerformanceCounter & co (referred to as QPCs) as indicated in "Acquiring high-resolution time stamps". Some of my search findings also indicate that the QPCs are not be trusted in SMP (Symmetric MultiProcessing environments).

In other words, if you want to do this correctly for use in various operating systems, you do need to make it operating system dependent. If you choose to carry on with your solution using the obsolete ftime() more could surely be said, but here are some comments on your actual code:

Loose the append variable – You already have room in buf for the result, and know how much you've already used. I.e. replace it with something like either sprintf(&buf[8], ":%03u", start.millitm); or sprintf(buf + 8, ":%03u", start.millitm);1, and you can return without doing the strcat at the end.
Avoid busy loops – Your while loop is called a busy loop as it does nothing excepting counting. It is usually better to trigger a sleep function or similar, allowing the processor to do other work in between.
Strange reset of countdown – Instead of resetting the countdown in the for loop, it would be clearer code to reset it just before the while loop, or even better (if persisting to use the busy loop) to make it into a locally scoped for loop, i.e for (int countdown = 0; countdown < 1000000; countdown++) ;
Decide on one style of bracing – Decide whether you want to have opening braces on the start of the line, or end of preceding line, and stick to it. Mixing like you've done here make your code somewhat harder to read, and when mixing with empty block (aka the busy loop) with missing braces, it is not good.

Some guys advocate a different opening brace style for functions versus other blocks, but I would suggest using the same style for everything making it more consistent.

Addendum: C11 and xtime_get or rather timespec_get

Jerry Coffin refers to a xtime_get() with potential nanoseconds precision (albeit still dependent on operating system precision). This is part of the C++ boost library. It was proposed to be included in C11 (see N1548.pdf, 7.25.7, p 383. This was revised in N1570, 7.27.2.7, into a timespec_get() function. N1570 is the latest draft available, before the standard was defined (and made commercially available). From this I quote:

  3 If base is TIME_UTC, the tv_sec member is set to the number of seconds since an implementation defined epoch, truncated to a whole value and the tv_nsec member is set to the integral number of nanoseconds, rounded to the resolution of the system clock.321)
  ...
  321) Although a struct timespec object describes times with nanosecond resolution, the available resolution is system dependent and may even be greater than 1 second.

This does however seem to have made it into C11 (also known as ISO/IEC 9899:2011), according to the table of contents listed here, see section 7.27.2.5. So if your compiler and libraries is compliant to C112, you might use timespec_get() and possibly get a system dependent precision up to nanoseconds (or even greater than 1 second).

1 Thanks to 200_success for pointing out error in code related to buf[8] not being an acceptable target for sprintf()
2 For the gcc family this seems to be gcc ver 4.6 and glibc ver 2.16, or newer


Project Euler #6 (Sum square difference) in Swift import Foundation

func printTimeElapsedWhenRunningCode(title:String, operation:()->()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed for \(title): \(timeElapsed) s")
}

func squaresSummed(first: Int, second: Int) -> Int {
    return (first + (second * second))
}

func solution6() {
    let firstHundredInts = [Int](1 ... 100)
    let summed = firstHundredInts.reduce(0) { $0 + $1 }
    let summedSquared = summed * summed

    let squaredSummed = firstHundredInts.reduce(0, combine: squaresSummed)

    let answer = summedSquared - squaredSummed

    println(String(answer))
}

printTimeElapsedWhenRunningCode("Sum square difference", solution6)

Some of the built in Swift stuff made this quite nice.  The syntax for declaring an array which is a simple list of integers is very convenient.  It runs faster than iterating through a loop to set all the values, types faster and reads better than typing all the values out by hand.

I quite like the reduce function on Swift arrays.

What could make this more Swift...-onic?  What needs improvement?

First, I would suggest that the solution6() function takes a parameter for
the upper bound, and returns the result instead of printing it (as also
suggested by @user16547 while I was writing this answer):

func solution6(upper : Int) -> Int {
    let firstInts = [Int](1 ... upper)
    let summed = firstInts.reduce(0) { $0 + $1 }
    let summedSquared = summed * summed
    let squaredSummed = firstInts.reduce(0, combine: squaresSummed)
    return summedSquared - squaredSummed
}

printTimeElapsedWhenRunningCode("Sum square difference") {
    let answer = solution6(10_000)
    println(answer)
}

Then you use an auxiliary function squaresSummed for computing the second
sum, but not for the first (and the name of that function is not very descriptive). In my opinion it is easier to understand if the shorthand notation is used
for both summations:

func solution6(upper : Int) -> Int {
    let firstInts = [Int](1 ... upper)
    let summed = firstInts.reduce(0) { $0 + $1 }
    let squaredSummed = firstInts.reduce(0) { $0 + $1 * $1 }
    return summed * summed - squaredSummed
}

For an upper bound of 10,000, this took about 0.001 seconds on my MacBook Pro in Release mode.

But [Int](1 ... upper) creates an array of all that numbers, which costs time
and memory. If you use a range instead

func solution6(upper : Int) -> Int {
    let firstInts = 1 ... upper
    let summed = reduce(firstInts, 0) { $0 + $1 }
    let squaredSummed = reduce(firstInts, 0) { $0 + $1 * $1 }
    return summed * summed - squaredSummed
}

the time is reduced to about 0.0002 seconds. This is about the same
time needed for a simple loop

func solution6(upper : Int) -> Int {
    var summed = 0
    var squaredSummed = 0
    for i in 1 ... upper {
        summed += i
        squaredSummed += i * i
    }
    return summed * summed - squaredSummed
}

which would be the most straightforward implementation of the algorithm.

Of course the fastest and shortest solution to the PE problem would be to

   Find the closed formula for 1 + 2 + ... + n and 1^2 + 2^2 + ... + n^2 and use that instead of a loop.


Using model relationships to find number of responses by a user, to posts of a certain topic type I have a user, a micropost and a response model.

The user has many microposts and has many responses.

Microposts have tags using the acts as taggable gem.

I need to find the number of responses a user has, to microposts that are tagged with a specific tag. To be clear, for example, how many responses has user 1 given to microposts on "exercise"

There is some basic ruby syntax and relationship logic I am missing. This is what I have in my user

This works as a User model method

   def user_responses_on_topic(interest)
        microposts = Micropost.tagged_with(interest, :on => :tags )
         count = 0
         microposts.each do |micropost|
         responses =  micropost.responses.size
         count = count + responses
      end
    count
   end

But there's got to be a better rails way?

Try something like this, it would work if the #tagged_with method returns an ActiveRecord::Relation object, I don't know if you need a :user_id in there, but your code didn't hint on any, so I did the same.

Response.joins(:micropost).merge(
  Micropost.tagged_with(interest, on: :tags)
).count


Models in a Simple PyMongo-based Blogging Web App without ORM/ODM I am currently using PyMongo + Flask for building a simple blogging application. I am not using any kind of ODM, instead I decided to use PyMongo directly. I need to know how to improve my code since learning is my main motivation for building this application.

This portion of code is implemented in a view controller called post.py and it is used to edit a post:

@posts.route('/<_id>/edit', methods=['GET', 'POST'])
def edit(_id):
    post = Post()
    post.get(_id)
    if request.method == 'POST':
        post.title = request.form.get('title')
        post.tags = [tag.strip() for tag in
                     request.form.get('tags').split(',')]
        post.body = request.form.get('body')
        post.update()
    return render_template('posts_edit.html', post=post)

The Post model looks something like this:

class Post:
    def __init__(self, _id=None, title=None, status=None, tags=None,
                 body=None, date=None, author=None):
        self._id = _id
        self.title = title
        self.status = status
        self.tags = tags
        self.body = body
        self.date = date
        self.author = author

    def save(self):
        mongo.db.posts.insert_one({
            "_id": ObjectId(),
            "title": self.title,
            "status": self.status,
            "tags": self.tags,
            "body": self.body,
            "date": datetime.utcnow(),
            "author": self.author
        })

    def update(self):
        mongo.db.posts.update({
            '_id': self._id
        },
            {
                "title": self.title,
                "status": self.status,
                "tags": self.tags,
                "body": self.body,
                "date": self.date,
                "author": self.author
        })

    def get(self, _id):
        post = mongo.db.posts.find_one({'_id': ObjectId(_id)})
        if post:
            self.__init__(**post)
            return self
        return None

    @classmethod
    def get_all(cls):
        return mongo.db.posts.find()

Is this the right direction?

For the route I'd probably use fewer temporary variables, not that it
hurts a lot, but it can be more compact.  Additionally if Post
implemented some sort of dict-like update function it could be even
more compact, but that's splitting hairs.

@posts.route('/<_id>/edit', methods=['GET', 'POST'])
def edit(_id):
    post = Post()
    post.get(_id)
    if request.method == 'POST':
        post.title = request.form.get('title')
        post.tags = [tag.strip()
                     for tag in request.form.get('tags').split(',')]
        post.body = request.form.get('body')
        post.update()
    return render_template('posts_edit.html', post=post)

With the latter point I mean something like this (implemention left as
an exercise for the reader):

@posts.route('/<_id>/edit', methods=['GET', 'POST'])
def edit(_id):
    post = Post()
    post.get(_id)
    if request.method == 'POST':
        post.update({
            "title": request.form.get('title'),
            "tags": [tag.strip()
                    for tag in request.form.get('tags').split(',')]
            "body": request.form.get('body')
        })
    return render_template('posts_edit.html', post=post)

For the other file I'd suggest looking at the usual 80 character limit,
meaning wrapping the longer lines a bit.

In save the date and _id attributes of the object aren't being
used - that looks inconsistent, either self.date and self._id
should be updated too, or neither, right?  That should probably also
be documented clearly.
With get and the __init__ call, AFAIK that's probably safe, but
coming from any background where constructors are, well, that, this
looks fishy.  Consider making that a class method too:

@classmethod
def get(cls, _id):
    return cls(**mongo.db.posts.find_one({'_id': ObjectId(_id)}))

get_all doesn't use it's argument, so it's actually more of a
staticmethod right now.  If you're no going to use inheritance make
it one then.  If you are, possibly make move mongo.db.posts into a
class variable so that you could override it for subclasses and the
methods would keep on working with the correct tables.


VBA function to extract worksheets with numeric names I have written some code to extract a list of worksheets in the ActiveWorkbook, but only for sheets that have a numeric name.

This works, but I would like to know the Code Review community's thoughts on my methods used here.

Public Sub listNumberedSheets()

    Dim sheetNumberArray As Variant
    ReDim sheetNumberArray(0)

    Dim x As Long
    x = 0

    Sheets(1).Columns(1).ClearContents

    Dim sht As Worksheet
    For Each sht In ActiveWorkbook.Sheets
        If IsNumeric(sht.Name) Then
            ReDim Preserve sheetNumberArray(x)
            sheetNumberArray(x) = sht.Name
            x = x + 1
        End If

    Next

    Sheets(1).Cells(1, 1).Resize(x, 1).Value = Application.Transpose(sheetNumberArray)

End Sub

Sheets(1).Columns(1).ClearContents

It's not a big deal in this case since the macro is always meant to work with the active workbook, but generally you want to preface a "Sheets" reference with an explicit reference to the workbook.

It's also generally not a good idea to refer to sheets by number. Using sheet names tends to be easier to read/debug.

My recommendation would be to add some parameters to the macro so that you can explicitly specify both a) the workbook whose sheets' names you want to check, and b) the worksheet on which to print the results. You can make the parameters optional if you'd like, and set them to "ActiveWorkbook" and "ActiveWorkbook.Sheets(1)" if they're missing from the call.

  Application.Transpose(sheetNumberArray)

Once again, this isn't a huge deal in this particular macro, but Application.Transpose has some significant limitations (it doesn't work with very large arrays) and should be avoided if possible. In your case, since you're eventually just writing the results of your routine to the worksheet, ideally you'd just make your array two-dimensional:

ReDim resultsArr(1 To wb.Sheets.Count, 1 To 1) As Double

But currently that won't work because you're using...

  ReDim Preserve sheetNumberArray(x)

Which brings me to my final recommendation: ReDim Preserve has high performance costs, and should be avoided if possible (especially uses like this in which it's called repeatedly). In your case, it's pretty easy to avoid, as you should be able to see in my revised code below.

Sub exampleMacro()

    'Checks sheets in specified workbook, prints to specified worksheet
    Call listNumberedSheets(ThisWorkbook, ThisWorkbook.Sheets("Results"))

    'Checks sheets in active wb, prints to Sheets(1) of active wb
    Call listNumberedSheets

End Sub
Sub listNumberedSheets(Optional wbToCheck As Workbook = Nothing, Optional resultsWS As Worksheet = Nothing)

    If wbToCheck Is Nothing Then
        Set wbToCheck = ActiveWorkbook
    End If

    If resultsWS Is Nothing Then
        Set resultsWS = ActiveWorkbook.Sheets(1)
    End If

    ReDim resultsArr(1 To wbToCheck.Sheets.Count, 1 To 1) As Double
    Dim i As Long
    Dim j As Long
    j = 1
    For i = 1 To wbToCheck.Sheets.Count
        Dim shtName As String
        shtName = wbToCheck.Sheets(i).Name
        If IsNumeric(shtName) Then
            resultsArr(j, 1) = shtName
            j = j + 1
        End If
    Next

    With resultsWS
        .Columns(1).ClearContents
        If j > 1 Then
            .Range(.Cells(1, 1), .Cells(j - 1, 1)).Value = resultsArr
        End If
    End With

End Sub

For maximum flexibility/reusability, I'd probably make it a function instead of a sub. That way it can either write the results to a worksheet OR return the results as an array. I'd also probably change it so that it could check multiple workbooks simultaneously. That definitely complicates the code a bit, but potentially makes it useful in more situations.

Sub exampleMacro()

    'Checks sheets in specified workbooks, prints to specified worksheet
    Call listNumberedSheets(Array(ThisWorkbook, Workbooks("Example workbook.xlsx")), ThisWorkbook.Sheets("Results"))

    'Checks sheets in specified workbook, returns 1d array
    Dim arr As Variant
    arr = listNumberedSheets(ThisWorkbook)

End Sub
Function listNumberedSheets(wbToCheck As Variant, Optional resultsWS As Variant) As Variant

    Dim wbArr As Variant
    If Not IsArray(wbToCheck) Then
        wbArr = Array(wbToCheck)
    Else
        wbArr = wbToCheck
    End If

    Dim sheetCount As Long
    Dim i As Long
    For i = LBound(wbArr) To UBound(wbArr)
        If Not TypeName(wbArr(i)) = "Workbook" Then
            MsgBox "Error: wbToCheck must be either workbook or array of workbooks"
            Stop
            Exit Function
        Else
            sheetCount = sheetCount + wbArr(i).Sheets.Count
        End If
    Next

    ReDim resultsArr(1 To sheetCount, 1 To 1) As Double
    Dim j As Long
    Dim counter As Long
    counter = 1
    For i = LBound(wbArr) To UBound(wbArr)
        For j = 1 To wbArr(i).Sheets.Count
            Dim shtName As String
            shtName = wbArr(i).Sheets(j).Name
            If IsNumeric(shtName) Then
                resultsArr(counter, 1) = shtName
                counter = counter + 1
            End If
        Next
    Next

    If IsMissing(resultsWS) Then
        If j = 1 Then
            listNumberedSheets = ""
        Else
            ReDim finalArr(1 To counter - 1) As Double
            For i = LBound(finalArr) To UBound(finalArr)
                finalArr(i) = resultsArr(i, 1)
            Next
            listNumberedSheets = finalArr
        End If
    ElseIf TypeName(resultsWS) = "Worksheet" Then
        If j > 1 Then
            With resultsWS
                .Columns(1).ClearContents
                .Range(.Cells(1, 1), .Cells(counter - 1, 1)).Value = resultsArr
            End With
        End If
    End If

End Function