Conversion Helper with support for enumerations and Nullable - The Remix I recently wrote this code as a more versatile stand-in for Convert.ChangeType. I very recently posted an earlier version, for which I received some good feedback. I've incorporated that feedback and further refactored in an attempt to streamline the flow of the method.

    /// <summary>
    ///     Returns an object of type <typeparamref name="T"/> whose value is equivalent to that of the specified
    ///     object.
    /// </summary>
    /// <param name="value">
    ///     An object that implements <see cref="IConvertible"/> or is <see cref="Nullable{T}"/> where the underlying
    ///     type implements <see cref="IConvertible"/>.
    /// </param>
    /// Other XML comments removed for brevity's sake.
    internal static T ChangeType<T>(object value) {

        Type originalType = typeof(T);
        Type nullableType = Nullable.GetUnderlyingType(originalType);

        if (value != null && value.GetType() == originalType)
        {
            return (T)value;
        }

        if (value == null || DBNull.Value.Equals(value))
        {
            if (nullableType != null || !originalType.IsValueType)
            {
                return default(T);
            }

            throw new InvalidCastException(string.Format("Cannot convert null to {0} because it is a non-nullable value type.", originalType.Name));
        }

        Type conversionType = nullableType ?? originalType;

        if (!conversionType.IsEnum)
        {
            return (T)Convert.ChangeType(value, conversionType);
        }

        object result = (value is string) ? Enum.Parse(conversionType, (string)value) : Enum.ToObject(conversionType, value);

        if (!Enum.IsDefined(conversionType, result))
        {
            throw new ArgumentException("The specified value is not defined by the enumeration.", "value");
        }

        return (T)result;
    }

As a good bit of time has passed, and no additional feedback seems to be incoming, I'm posting this answer so that I can close the loop on this question.

The only feedback I might give -- and it's a small optimization -- is to move this code:

Type nullableType = Nullable.GetUnderlyingType(originalType)

I think it would be slightly better to put it after the check to see if the value parameter's type equals the generic type parameter's type, as there exists a chance that the method will not need that variable at all if the types are equal.


A-maze-ing maze entry point guessing You're a blind adventurer (bad luck eh). To go through the maze that'll lead you to freedom, you must first find the maze's wall, then follow this wall to find the maze's entry. Then, to get an idea about the size of the maze, you want to see how large is the said entry, so you walk until you touch another wall, which is the other border of the entrance. Still following? If not, here's a boolean[][] that'll show my example :

  1,1,1,1,1,0,0,0,1,1,1,1,1

  0,0,0,1,1,0,0,0,1,1,0,0,0

Zeros implies there is no wall
Ones implies there is a wall.

The entry of the maze can be found on the last index of the array, meaning :

maze[x,maze.length-1]

In my example, the entrance is found at [6,1]. As it is a first iteration, the maze is expected to have only one entry, which is valid, which will be situated on the last row of the array. @DoubleDouble already pointed out a flaw of my algorithm in his answer.

If the maze contained an even number of "columns", the entrance could be either the "left" or "right", it doesn't matter.

To find the entrance to my maze, I wrote the function guessEntry, in my Maze class :

package com.mazr.domain;

import java.awt.Point;

public class Maze {
    private boolean[][] content;

    public Maze(boolean[][] content) {
        this.content = content;
    }

    public Point guessEntry() throws InvalidMazeException {

        int openingBorder, closingBorder;
        int xIndex = 0;
        final int bottomYIndex = content[0].length-1;

        try {
            //Find the wall
            while (!content[xIndex][bottomYIndex])
                xIndex++;

            //Follow the wall to the entry
            while (content[xIndex][bottomYIndex])
                xIndex++;

            openingBorder = xIndex;

            //Follow the entry until the end of it
            while (!content[xIndex][bottomYIndex])
                xIndex++;

            closingBorder = xIndex;

            return new Point((closingBorder - openingBorder) / 2, bottomYIndex);
        }
        catch(IndexOutOfBoundsException e){
            throw new InvalidMazeException("The maze has no guessable entry", e);
        }
    }
}

To make the example even clearer, I will show how the algorithm behaves to find an entrance (Don't forget that it only works on the bottom row of the array, which is assumed to contain some walls.):

//Find the wall
while (!content[xIndex][bottomYIndex])
    xIndex++;

  0,0,0,1,1,0,0,0,1,1,0,0,0

  ------^
  xIndex is now at this position, since it went through all the left zeroes.

//Follow the wall to the entry
while (content[xIndex][bottomYIndex])
    xIndex++;

  0,0,0,1,1,0,0,0,1,1,0,0,0

  ----------^
  xIndex is now there, since it went through the first wall.
  We set openingBorder to xIndex since this is the beginning of the entrance "hall".

//Follow the entry until the end of it
while (!content[xIndex][bottomYIndex])
    xIndex++;

  0,0,0,1,1,0,0,0,1,1,0,0,0

  ----------------^
  xIndex went to the next wall, which marks the end of the entrance "hall".
  We set the closingBorder to xIndex so we can know where is the hall situated.

Then, averaging (sorry if that's not a word) the closing and opening border, we can figure out where is the middle of the hall, so we can start solving it (in an upcoming question).

The jagged array is rectangular, meaning that wether we talk about index 0 or 1732, the jagged array will have the same length.

Now, it is easy to seek why I need a review. The function works, it is arguably easy to understand. But I can't stand these following while loops..

I'm using Java 1.8.

I know I'm providing only one method, but I feel like it is already hard to explain briefly and to be clear about the cases.

I believe the while() loops are the best way to accomplish your task with how your code is now, so I'm not sure why you "can't stand" them.
You could use a for() loop, and break out of it using an if statement to check the same thing that your while loops are doing, but I would prefer the while loops myself.

One other thing I'd like to mention: if your input is always going to be similar to your example you have nothing to worry about, but your code might not work correctly on the following examples:

Extra line of blank space:
1,1,1,1,1,0,0,0,1,1,1,1,1
0,0,0,1,1,0,0,0,1,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0
No wall separator before the entrance:
1,1,1,1,1,0,0,0,1,1,1,1,1
0,0,0,0,0,0,0,0,1,1,0,0,0
No wall separator before the entrance #2:
0,0,0,1,1,1,1,1,1,1,1,1,1
0,0,0,1,1,1,1,1,1,1,1,1,1

You'd catch the ArrayIndexOutOfBounds exception as an "unguessable entry", which I assume is the intentional response - but thought I'd put this here just in case.


Simple VisitorCounter class I am trying to learn the absolute best way to program/design classes in PHP. I am hoping that you would be able to review and critique this simple class.

Note: I know that there aren't any comments. Please don't critique me on that.

<?php
class VisitorCounter
{
    protected $numVisits;
    protected $db;

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

    public function updateNumVisits()
    {
        if(!$this->getNumVisits() || !$this->firstTimeHere()){ return false; }

        $_SESSION['new_visitor'] = 1;

        $sql = "UPDATE stats SET visits=". ++$this->numVisits ." WHERE id=2";
        if(!$this->db->query($sql)){
            $sql = "INSERT INTO stats (visits) VALUES (". ++$this->numVisits .")";
            return $this->db->query($sql)? true : false;
        }
        return true;
    }

    protected function firstTimeHere()
    {
        if(isset($_SESSION['new_visitor'])){
            return false;
        }
        return true;
    }

    protected function getNumVisits()
    {
        $result = $this->db->query("SELECT * FROM stats");
        if($row = $this->db->fetch_array($result)){
            return $this->numVisits = $row['visits'];
        }
        return false;
    }

}

Implementation

$Counter = new VisitorCounter($db);
$Counter->updateNumVisits();

Questions

Is it ever ok to "for example", to move the $Counter->updateNumVisits() directly into the constructor? Or is that NEVER good to do, even in the simplest of scenarios? I'm reading that it is best only to do simple assignments in the constructor.
Inside the function updateNumVisits(), I have a conditional that runs a function getNumVisits(). If this is not advisable, when should I call this function so that updateNumVisits() will have access to the latest visit count?
I read many Code Review posts about not using globals, and so I got rid of my $db global out of the class, and injected it in the constructor. What about $_SESSION and $_POST values? Is it ok to have them inside your class?
How would you write this class?
I was also hoping that you might know of a very simple open source PHP project that someone built that I can study and learn from. One that follows all the best practices mentioned here on this website. For instance that uses DI, and follows all the principles of good coding practices. I downloaded the Zend framework and CodeIgnitor but they are too complex and too big for my current understanding.

First of all, I started rewriting your class but found many implementation problems design wise that stopped me from rewriting it (because it would be to much for you to learn in one go and would take me a long time to design, code and explain). So I have done a small portion.

Problems Are

No type casting so ANY object could be passed to the constructor
What if the database object changes? The method calls on the db object inside the VisitorCounter class will break
You are doing two roles inside the VisitorCounter class, you are both keeping a global visitor count using the database AND trying to keep track of the users visits. Also, you are hard coding it to the $_SESSION! What if you want to use APC or Memcache for example!? Code changes would occur.
You are not programming to interfaces but instead to concrete classes (and globals i.e. $_SESSION)

Solution

This is a semi pseudo (not complete but will show for demonstration purposes) PHP example just to demonstrate many things for you to learn but i have only taken out the site counter part of your visitorcounter class. You can implement thevisitorcounter in exactly the same way I have done for the DB & Site Counter, but instead for Session & Visitor Counter which would be brilliant practice for you! ;)

Read the comments in the comment.

/**
* by programming to this db interface, you can CHANGE the db class to ANY class you want at any time. As long as the new class
* implements this interface, the rest of the code will no how to handle the class :) this demonstrates programming to implementations
* and not to (concrete) classes
*/
interface db_connection {
    public function connected();
    public function query($sql);
}

/**
* this will be where the database specific database calls will be made. I have named this one mysql, but I only
* did this because it means I could have db_oracle (and others), and if I were to pass a db_oracle instace to the visitor counter construct
* it would still work :D as long as the db_oracle class implemented db_connection. You can then interchange db_mysql and db_oracle as you wish
*/
class db_mysql implements db_connection {
    public function connected() {
        //returns true or false depending on if connected
    }
    public function query($sql) {
        //actually makes the query, returns the result resource if ok, false if it failed
    }
    public function escape($string) {
        //escapes the string to protect from sql injection attacks
    }
    public function result($sql_resource) {
        //if the resource contains results, will return the first field from the first row of the result, FALSE otherwise
    }
    //... and all the other methods you want such as connect() disconnect() ping() etc...
}
/**
* site counter
*/
class site_counter {

    private $db = null;
    private $total = 0;

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

    /**
    * increments the site counter
    */

public function increment($step = 1) {

    //ensure the step is numeric
    if ( ! is_numeric($step)) {
        throw new Exception("Expected a number, got something else!");
        return false; //didn't work
    }

    //notice the limit clause, use this to indicate to SQL that it no longer has to keep searching for more to update
    //you can increment existing fields by using SQL directly, don't do things the long way around as you did as you will also have concurrency issues (another poster I believe explained it)
    $step = $this->db->escape($step); //just to be safe ;)
    if ($this->db->query("UPDATE stats SET visits=visits+{$step} LIMIT 1;")) {
        return true; //worked ok
    }

    return false; //didn't work

}

    /**
    * resets the counter in the database and session
    */
    public function reset($to = 0) {
        if (is_numeric($to)) {
            $to = $this->db->escape($to); //just to be safe ;)
            //notice the limit clause, use this to indicate to SQL that it no longer has to keep searching for more to update
            return $this->db->query("UPDATE stats SET visits={$to} LIMIT 1;");
            } else {
            throw new Exception("Expected a number, got something else!");
        }
        //something went wrong
        return false;
    }

    /**
    * resets the counter in the database and session
    */
    public function get_total_hits() {
        //the (int) is called type casting, so false (if the query fails for example) will return 0
        return (int) $this->db->result($this->db->query("UPDATE stats SET visits={$to} LIMIT 1;"));
    }

}


Summation and multiplication of digits of a number This program takes digits of a number and calculate summation and multiplication of its digits .How can I make this code more OOP ?

//Calculate Sum and multiplication of digits of a number .

#include "stdafx.h"
#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;

int main()
{
    int number , sum = 0 , multp = 0 ;
    vector<int> digits;

    cout << "Calculate Sum and multiplication of digits of a number ." << "\n" << "\n";
    cout << "------------------------------------" << "\n";
    cout << "Enter a whole number : ";

    cin >> number;

    if (number > 0)         //Condition for inputed number
    {

        while (number)
        {
            digits.push_back(number % 10);
            number /= 10;
        }

        for (int i = 0; i < digits.size(); i++) // summation
        {
            sum += digits[i];
        }
        cout << "sum of digits = " << sum << "\n";

        for (int j = 0; j < digits.size(); j++) //multiplication
        {
            multp *= digits[j];
        }

        cout << "Multiplication of digits = " << multp << "\n";
    }

    else
    {
        cout << "Pleas enter a positive number ." << "\n";
    }

    cout << "\n" << "\n" << "------------------------------------" << "\n";
    system("pause");
    return 0;
}

Thanks in advance.

Using std::accumulatewould be more idiomatic. Also use auto whenever possible.

#include <algorithm>
#include <functional> // requires C++14, else use a lambda for the predicate
auto sum = std::accumulate( digits.cbegin(), digits.cend(), 0 );
auto prod = std::accumulate( digits.cbegin(), digits.cend(), 1, std::multiplies<>);

Comment on the accepted answer, which I at first mistook for an edit of the question:

Class names should be nouns, function names should be verbs. As in DigitsCalculator.
Your no argument constructor can be written as CalcDigits = default.
Having a setter and getter for a private variable effective eliminates the encapsulation. There are divergent opinions on this topic. Some say a setter is better, because you can add logic for accessing the variable later. I, personally, have never "added logic" to a setter, and would just make the variable public.
You have an invariant: CalcDigits c; c.SetNumber(42); c.GetSum(); c.GetMul();. Interfaces should be "easy to use correctly, difficult to use incorrectly.
Overall, I like the new look better. You have separation of concerns (command line communication and actual calculation). You also have an encapsulated object, that you can pass around with clear intent.


Formatting an ID string I'm working with an API which gives me 19-digit ID numbers, formatted in blocks of four except for the last 3 digits. While I tried a for loop, I thought it would be most efficient to simply use a StringBuilder and substrings as the length of the ID will never change (documentation is omitted for privacy reasons):

public String getFormattedId() {
    return new StringBuilder()
            .append(id.substring(0, 4))
            .append(" ")
            .append(id.substring(4, 8))
            .append(" ")
            .append(id.substring(8, 12))
            .append(" ")
            .append(id.substring(12, 16))
            .append(" ")
            .append(id.substring(16, 19))
            .toString();
}

This transforms IDs like 1234567890000000123 into the more readable 1234 5678 9000 0000 123, which is also the format used throughout the documentation and website.

I should mention I come from a C# background, and I've heard Java's string + operator is just syntactic sugar for the StringBuilder method like I'm using here.

It is things like this which drive me nuts, and I agree with you, your solution is good, but ugly. Your solution is also probably close to being as efficient as possible in Java, using the StringBuilder, etc.

There are a couple of things through that you can do to xhange the way you code it. Note that your solution may well be the fastest.... (well, it would be the fastest if you specified a starteing capactity of 23 for the StringBuilder like new StringBuilder(23) ...

How about a for-loop:

private static String formatID(String id) {
    StringBuilder sb = new StringBuilder(25);
    for (int i = 0; i < id.length(); i += 4) {
        sb.append(id.substring(i, Math.min(i + 4, id.length())));
        sb.append(" ");
    }
    sb.setLength(23);
    return sb.toString();
}

The last setLength(23) removes the trailing space on the output.

The actual suggestion I prefer, though, is using a format String, like:

private static String formatFID(String id) {
    return String.format("%s %s %s %s %s", id.substring(0, 4), id.substring(4,  8),
            id.substring(8,  12), id.substring(12,  16), id.substring(16, 19));
}

Finally, for completeness, you can actually use a regex to split the input string at 4-char boundaries. Then, in Java 8, stream the results, and join them with a space:

private static final Pattern FOUR = Pattern.compile("(?<=\\G.{4})");

private static String formatRID(String id) {
    return Stream.of(FOUR.split(id)).collect(Collectors.joining(" "));
}

That's a concise way of doing it.....


Optional argument for which None is a valid value I have the following function:

def item_by_index(iterable, index, default=Ellipsis):
    """Return the item of <iterable> with the given index.

    Can be used even if <iterable> is not indexable.

    If <default> is given, it is returned if the iterator is exhausted before
    the given index is reached."""

    iterable_slice = itertools.islice(iterable, index, None)
    if default is Ellipsis:
        return next(iterable_slice)
    return next(iterable_slice, default)

It should (and does) throw an exception if the default is not given and the iterator is exhausted too soon.  This is very similar to what the built-in function next does.

Usually, one would probably use None as default value to make an argument optional. In this case, however, None is a valid value for default and should be treated differently from no argument.  This is why I used Ellipsis as a default value.  It sort of feels like an abuse of the Ellipsis object, though.

Is there a better way of doing this or is Ellipsis a good tool for the job?

I would argue the best option is to make an explicit sentinel value for this task. The best option in a case like this is a simple object() - it will only compare equal to itself (aka, x == y only when x is y).

NO_DEFAULT = object()

def item_by_index(iterable, index, default=NO_DEFAULT):
    ...

This has some semantic meaning, and means there is no potential overlap between a value a user wants to give and the default (I imagine it's highly unlikely they'd want to use Ellipses, but it's better to make as few assumptions as possible about use cases when writing functions). I'd recommend documenting it as such as well, as it allows the user to give a default/not using a variable, rather than having to change the call.

try:
    default = get_some_value()
except SomeException:
    default = yourmodule.NO_DEFAULT

item_by_index(some_iterable, index, default)

As opposed to having to do:

try:
    default = get_some_value()
except SomeException:
    item_by_index(some_iterable, index)
else:
    item_by_index(some_iterable, index, default)

The only downside it's not particularly clear what it is if you are looking at the object itself. You could create a custom class with a suitable __repr__()/__str__() and use an instance of it here.

As of Python 3 enums have been added - the default type of enum only compares equal on identity, so a simple one with only the one value would also be appropriate (and is essentially just an easy way to do the above):

from enum import Enum
class Default(Enum):
    no_default = 0

Thanks to metaclass magic, Default.no_default is now an instance of a Default, which will only compare equal with itself (not 0, by default, enums are pure).


Trie implementation with Python 3 This is just a classic implementation of a trie using python 3.6, with types. I am a PHP developer, so these are my first attempts with Python.

I know I can improve the readability of my code, it's a bit messy, but I am struggling finding the right way of doing it. I'm sure I am missing a lot of the Pythonic ways in here :-)

from typing import Optional

class Trie:
    def __init__(self):
        self.root = Node(char=None, is_word=False)

    def add(self, word: str) -> None:
        current = self.root
        is_end_of_word = False

        for i in range(0, len(word)):
            char = word[i]
            if i == len(word) - 1:
                is_end_of_word = True

            if not current.children:
                node_to_insert = Node(char, is_end_of_word)
                current.add_child(node_to_insert)
                current = node_to_insert
                continue

            if char not in current.children:
                node_to_insert = Node(char, is_end_of_word)
                current.add_child(node_to_insert)
                current = node_to_insert
            else:
                current = current.children[char]

    def contains(self, word: str) -> bool:
        current = self.root

        for char in word:
            if not current.children:
                return False

            if char in current.children:
                current = current.children[char]
                continue
            else:
                return False

        if not current.is_word:
            return False

        return True

    def remove(self, word: str) -> None:
        current = self.root

        for i in range(0, len(word)):
            char = word[i]
            is_end_of_word = False

            if i == len(word) - 1:
                is_end_of_word = True

            if char in current.children:
                if current.children[char].is_word and is_end_of_word:
                    current.children[char].is_word = False
                    return
                current = current.children[char]
            else:
                return

    def retrieve_all_words(self) -> list:
        return self._retrieve_all_words(self.root, '', [])

    def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
        for child in current.children.values():
            word = word + child.char
            if child.is_word:
                words.append(word)

            if child.children:
                self._retrieve_all_words(child, word, words)
                word = word[:-1]
                continue

            word = word[:-1]

        return words

class Node:
    def __init__(self, char: Optional[str], is_word: bool):
        self.char = char
        self.is_word = is_word
        self.children = {}

    def add_child(self, node: 'Node'):
        self.children[node.char] = node

Your code looks very good and the type annotation is a really nice touch
Also, your code is well organised and easy to understand. Some documentation could be a good idea (but it's better to have no doc rather than bad doc). Also, you could consider writing unit tests.

Let's try to see what could be improved/made more Pythonic.

Loop like a native

I highly recommand Ned Batchelder's excellent talk "loop like a native". One of the idea is that whenever you are using for i in range(len(iterable)), you are probably doing it wrong. In your case, you could use for i, char in enumerate(word):.

End of word

The end-of-word detection could be done in a single statement: is_end_of_word = i == len(word) - 1. Also, you can get rid of the definition before the loop and even in the loops, sometimes, you could define it only behind the if char in current.children: because you use it only there.

Reorganise the logic

Sometimes, you check if something is empty and then if it contains a particular element. This can be factorised out:

Also, simplifying the code if (cond) return False else return True, you could rewrite contains:

def contains(self, word: str) -> bool:
    current = self.root
    for char in word:
        if char not in current.children:
            return False
        current = current.children[char]
    return current.is_word

Then in _retrieve_all_words, you can get rid of continue by using a simple else which makes things more explicit. Then, you can actually factorise out the common code at the end of the 2 branches and get the more simple:

        if child.is_word:
            words.append(word)
        if child.children:
            self._retrieve_all_words(child, word, words)
        word = word[:-1]

Finally, you can use += to simplify word = word + child.char into word += child.char.

At this stage, the code looks like:

from typing import Optional

class Trie:
    def __init__(self):
        self.root = Node(char=None, is_word=False)

    def add(self, word: str) -> None:
        current = self.root

        for i, char in enumerate(word):
            if char in current.children:
                current = current.children[char]
            else:
                is_end_of_word = i == len(word) - 1
                node_to_insert = Node(char, is_end_of_word)
                current.add_child(node_to_insert)
                current = node_to_insert

    def contains(self, word: str) -> bool:
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_word

    def remove(self, word: str) -> None:
        current = self.root
        for i, char in enumerate(word):
            if char not in current.children:
                return
            is_end_of_word = i == len(word) - 1
            if current.children[char].is_word and is_end_of_word:
                current.children[char].is_word = False
                return
            current = current.children[char]

    def retrieve_all_words(self) -> list:
        return self._retrieve_all_words(self.root, '', [])

    def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
        for child in current.children.values():
            word += child.char
            if child.is_word:
                words.append(word)
            if child.children:
                self._retrieve_all_words(child, word, words)
            word = word[:-1]
        return words

class Node:
    def __init__(self, char: Optional[str], is_word: bool):
        self.char = char
        self.is_word = is_word
        self.children = {}

    def add_child(self, node: 'Node'):
        self.children[node.char] = node

t = Trie()
t.add("toto")
t.add("tutu")
t.add("foobar")
print(t)
print(t.retrieve_all_words())
print(t.contains("tot"))
print(t.contains("toto"))
print(t.contains("totot"))

Storing things in a different format

Instead of maintaining a is_word attribute, maybe you could add store a sentinel like None to say that we have a full word here. This could be written like this:

from typing import Optional

class Trie:
    def __init__(self):
        self.root = Node(char=None)

    def add(self, word: str) -> None:
        current = self.root

        for char in list(word) + [None]:
            if char in current.children:
                current = current.children[char]
            else:
                node_to_insert = Node(char)
                current.add_child(node_to_insert)
                current = node_to_insert

    def contains(self, word: str) -> bool:
        current = self.root
        for char in list(word) + [None]:
            if char not in current.children:
                return False
            current = current.children[char]
        return True

    def remove(self, word: str) -> None:
        current = self.root
        for char in list(word) + [None]:
            if char not in current.children:
                return
            elif char is None:
                del current.children[char]
            else:
                current = current.children[char]

    def retrieve_all_words(self) -> list:
        return self._retrieve_all_words(self.root, '', [])

    def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
        for child in current.children.values():
            if child.char is None:
                words.append(word)
            else:
                word += child.char
                if child.children:
                    self._retrieve_all_words(child, word, words)
                word = word[:-1]
        return words

class Node:
    def __init__(self, char: Optional[str]):
        self.char = char
        self.children = {}

    def add_child(self, node: 'Node'):
        self.children[node.char] = node

t = Trie()
t.add("toto")
t.add("tutu")
t.add("foobar")
print(t)
print(t.retrieve_all_words())
print(t.contains("tot"))
print(t.contains("toto"))
print(t.contains("totot"))
t.remove("toto")
print(t.retrieve_all_words())
print(t.contains("toto"))

Back to word = word + child.char

Something I should have mentionned earlier but spotted on the late.

In _retrieve_all_words, you add a char to word only to remove it afterward. It is much clearer (and more efficient?) to just write word + char in the places where you actually need to word with the added character.

Then, the code becomes:

def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
    for child in current.children.values():
        if child.char is None:
            words.append(word)
        elif child.children:
            self._retrieve_all_words(child, word + child.char, words)
    return words


Is there a more efficient way to simulate in R, by exposition factor, gender and disease profile? I started working with R recently and need to do a simulation for 100 000 people that
divides them in exposition factor for a disease, gender and presence or absence of
disease.
My background info is that the probability of being exposed to this risk factor is 0.15 in this population. The probability of being a woman, among exposed people is 0.2 and among non exposed people is 0.5. I also know that there are 4 gamma distributions - divided by gender and exposition factor - that characterize the disease. If X> 35, from each gamma, then you have the disease. I used the following code to answer this question:

n<-100000
exposition<-rep(0,n)
#vector that represents non exposed ("non exposed" = 1, "exposed" = 0)
gender<-rep(0,n) #vector that reprsents gender ("women" = 1, "men" = 0)
disease<-rep(0,n)
#vector that represents disease ("with disease" = 0, "without disease" = 1)
u<-runif(n,0,1)
b<-runif(n,0,1)
c<-runif(n,0,1)

#in 100 000 cases atributes non expostion
for(i in 1:n){if(u[i]>0.15)exposicao[i]<-1}

#cycle that determines the gender of the subjects
for(j in 1:n){{if(exposicao[j]==1 & b[j]>0.5)genero[j]<-1}
{if(exposicao[j]==0 & b[j]<0.2)genero[j]<-1}}

#Cycle that determines the state of disease from the subjects. I define people with
disease as people with c[x] inferior to the probability of having the disease
(P(X>35)), according to their gamma distribution. I used the results from that
calculation.

     for(x in 1:n){{if(expositon[x]==1 & gender[x]==1 & c[x]<0.06840084)doentes[x]<-1}
 #if the person is non exposed and woman X2~G(12,2)
 {if(exposition[x]==0 & gender[x]==1 & c[x]<0.1698673)doentes[x]<-1}
 #if it's exposed and woman X3~G(14,2)
 {if(exposicao[x]==1 & genero[x]==0 & c[x]<0.02010428)doentes[x]<-1}
 #if it's non exposed and man X1~G(10,2)
 {if(exposicao[x]==0 & genero[x]==0 & c[x]<0.3275424)doentes[x]<-1}}
 #if it's exposed and man X4~G(16,2)

There are a few improvements to your (I'm assuming that genero and gender are the same variable).

Very important. Use a space around the assignment operator! x<-5 Does this mean assign 5 to x to is x less than -5
Rather then rep(0,n) just use numeric(n)
Your loops should be rewritten. For example:

##I presume that exposicao is exposition.
for(i in 1:n){if(u[i]>0.15)exposicao[i]<-1}

can be written as:

exposition[runif(n) > 0.15] = 1

and

for(j in 1:n){{if(exposicao[j]==1 & b[j]>0.5)genero[j]<-1}
{if(exposicao[j]==0 & b[j]<0.2)genero[j]<-1}}

can be written as:

genero[exposicao==1 & b>0.5] = 1
genero[exposicao==0 & b>0.2] = 1


Gimme some random passwords pwgen is a nice password generator utility.
When you run it, it fills the terminal with a bunch of random passwords,
giving you many options to choose from and pick something you like,
for example:

lvk3U7cKJYkl pLBJ007977Qx b9xhj8NWPfWQ
pMgUJBUuXwpG OAAqf6Y9TXqc fJOyxoGYCRSQ
bpbwp6f2MxEH fUYTJUqg0ZMB GjVVEQxuer0k
oqTEvV1LmdJu si47MkHNRpAw 3GKV8NdGMvwf

Although there are ports of pwgen in multiple systems,
it's not so easy to find in Windows.
So I put together a simple Python script that's more portable,
as it can run in any system with Python.

I added some extra features I often want:

Skip characters that may be ambiguous, such as l1ioO0Z2I
Avoid doubled characters (slow down typing)

Here it goes:

#!/usr/bin/env python

from __future__ import print_function

import random
import string
import re

from argparse import ArgumentParser

terminal_width = 80
terminal_height = 25

default_length = 12

alphabet_default = string.ascii_letters + string.digits
alphabet_complex = alphabet_default + '`~!@#$%^&*()_+-={}[];:<>?,./'
alphabet_easy = re.sub(r'[l1ioO0Z2I]', '', alphabet_default)

double_letter = re.compile(r'(.)\1')

def randomstring(alphabet, length=16):
    return ''.join(random.choice(alphabet) for _ in range(length))

def has_double_letter(word):
    return double_letter.search(word) is not None

def easy_to_type_randomstring(alphabet, length=16):
    while True:
        word = randomstring(alphabet, length)
        if not has_double_letter(word):
            return word

def pwgen(alphabet, easy, length=16):
    for _ in range(terminal_height - 3):
        for _ in range(terminal_width // (length + 1)):
            if easy:
                print(easy_to_type_randomstring(alphabet, length), end=' ')
            else:
                print(randomstring(alphabet, length), end=' ')
        print()

def main():
    parser = ArgumentParser(description='Generate random passwords')
    parser.add_argument('-a', '--alphabet',
                        help='override the default alphabet')
    parser.add_argument('--complex', action='store_true', default=False,
                        help='use a very complex default alphabet', dest='complex_')
    parser.add_argument('--easy', action='store_true', default=False,
                        help='use a simple default alphabet, without ambiguous or doubled characters')
    parser.add_argument('-l', '--length', type=int, default=default_length)
    args = parser.parse_args()

    alphabet = args.alphabet
    complex_ = args.complex_
    easy = args.easy
    length = args.length

    if alphabet is None:
        if complex_:
            alphabet = alphabet_complex
        elif easy:
            alphabet = alphabet_easy
        else:
            alphabet = alphabet_default
    elif len(alphabet) < length:
        length = len(alphabet)

    pwgen(alphabet, easy, length)

if __name__ == '__main__':
    main()

How would you improve this? I'm looking for comments about all aspects of this code.

I know that the terminal_width = 80 and terminal_height = 25 variables don't really reflect what their names imply. It's not terribly important, and good enough for my purposes, but if there's a way to make the script detect the real terminal width and height without importing dependencies that reduce portability, that would be pretty awesome.

Looking at the following:

terminal_width = 80
terminal_height = 25

default_length = 12

alphabet_default = string.ascii_letters + string.digits
alphabet_complex = alphabet_default + '`~!@#$%^&*()_+-={}[];:<>?,./'
alphabet_easy = re.sub(r'[l1ioO0Z2I]', '', alphabet_default)

double_letter = re.compile(r'(.)\1')

you never change them, so they are constants. Constants are written ALL CAPS in Python as a convention.

elif len(alphabet) < length:
    length = len(alphabet)

Are you sure the user really wants what you are doing here? Maybe he wants a 20 character password using only the 10 digits, with this you are silently not doing what he expects.


Solving the coin change algorithm using 10 coins I'm solving the coin change problem having target of n and upper bound as n.

Also the maximum number of coins is 10.

For example. if the target is 11. then the possible outcomes are -

11
10,1
9,2
9,1,1
....
....
....
2,1,1,1,1,1,1,1,1,1

So the last iteration having eleven 1's are not allowed as the max coins is 10.

I have written code for solving the problem, but that is too complicated and cumbersome and I think it can be optimized for better performance.

The code as in this link and below:

import java.util.ArrayList;

public class Numbers {

/**
 * @param args the command line arguments
 */
static ArrayList<Integer> list;
static int target;
static boolean bl;
static boolean ex;
static int rpl;
public static void main(String[] args) {

    Numbers nm = new Numbers();
    /*
    nm.list = new ArrayList();
    new Numbers().test1();
    */
    list = new ArrayList<Integer>();
    bl = false;
    ex = false;
    target = 24;
    nm.test(24);
}

public void test(int k) {
    int r = 0;
    for (int i = k; i>0; i--) {
        if(!ex) {
            if(sum(list) + i > target) {
                test(i-1);
            }
            else if(list.size() == 10) {
                /*
                list.add(target - sum(list));
                printFill(list); */
                int p = list.get(0);
                if(p*10>=target) {
                    i = p;
                    list.clear();
                }

            } else {
                list.add(i);
                if(sum(list) == target) {
                    printFill(list);
                    if(bl)
                        i = rpl;
                    bl = false;
                } else {
                    test(i);
                }
            }
        } else {
            System.out.print("t");
        }
    }
}

public void printFill(ArrayList lt) {
    int i = 0;
    for ( i = 0; i< lt.size()-1; i ++) {
        System.out.print(lt.get(i)+",");
    }
    System.out.print(lt.get(i));
    System.out.println("");

    i = list.get(list.size()-1);
    if(i > 1) {
        list.remove(list.size()-1);
        if(list.size()>0) {
            try {
                while (list.get(list.size()-1) == 1) {
                    list.remove(list.size()-1);
                }
            } catch(Exception e ) { }
            /*if(list.size()==0) {
                System.out.println("test");
                ex = true;
            }*/
        }
    } else if(i == 1 ) {
        try {
            while (list.get(list.size()-1) == 1) {
                list.remove(list.size()-1);
            }
        } catch(Exception e ) { }
        if(list.size()>0) {
            bl = true;
            rpl = list.remove(list.size()-1);
        } else {
            ex = true;
        }
    }
}

public int sum(ArrayList<Integer> lt) {
    int k = 0;
    for ( int i = 0; i< lt.size(); i ++) {
        k = k + lt.get(i);
    }
    return k;
}

public void test1() {
    for(int i=1; i<= 4; i++) {
        if(!list.contains(i)) {
            list.add(i);
            test1();
            list.remove(list.indexOf(i));
        }
    }
    if(list.size() == 4)
    {
        for(int i=0; i< 4; i++) {
            System.out.print(list.get(i));
        }
        System.out.println("");
    }
}
}

I'm really struggling to read your code, but I'm trying to take a crack at it. In the mean time, here are some things about your code in general – not about the algorithm you use.

Static fields. You do not want to use static fields for bl, ex etc. My guess is you added them because you set them in the main method, which is static by definition. static means that bl etc. will be shared by all objects of that class – you do not want that.

The best way to fix this is to initialize the field directly or in a constructor, not externally. In other words, something like private boolean bl = false; will do, or put all the default values in a constructor:

public Numbers() {
    bl = false;
    list = new ArrayList<Integer>();
    // etc.
}

Aside from the static problem, think of code re-usage: someone who just wants to use your Numbers class shouldn't have to care about what bl and ex (etc.) do, so they shouldn't have to initialize them. It's not only inconvenient for another user, but it's also dangerous to let the inner workings of your class at the mercy of the user.

Mixing fields and parameters

Two examples:

public void test(int k) {
    int r = 0;
    for (int i = k; i>0; i--) { // use of k
        if(!ex) {
            if(sum(list) + i > target) { // use of target

public void printFill(ArrayList lt) {
    int i = 0;
    for ( i = 0; i< lt.size()-1; i ++) {
        System.out.print(lt.get(i)+","); // use of lt
    }
    // ...
    i = list.get(list.size()-1); // use of list

k and target in the first example, lt and list in the second example are the same, and this is very dangerous. You want to either stick with the parameter or the field only, but please avoid using a class field and a parameter interchangeably.

The most important point here is to decide whether to use a parameter or the field. printFill seems to be an important part of your algorithm, so I would personally tend to use the field rather than the parameter here, because the code is so specific that it will hardly be re-usable for something else.

As for test(), I would remove the target field altogether as it's only used interchangeably with the parameter k in test(int k). I don't see much sense in keeping the value after test() returned its result. It is more convenient for a user to do numbers.test(25) than numbers.setTarget(25); numbers.test();.

Further issues. The spacing one is somewhat minor, so please take it with a grain of salt.

Naming. Your code is hard to understand because I have no idea what bl stands for. test and test1 also don't hint at what the methods do, either. printFill doesn't fill anything but removes elements from the list.
Structure. If you're finding yourself getting lost in your own code, it's probably a good idea to restructure your code a little. Particularly, I would suggest abstracting the printing and "filling" (removing) sections of printFill into individual methods. You generally want methods that have one purpose only, and then you combine them later on.
Exception handling. Exception handling is a complex subject and it's hard to keep one's solutions elegant and sensible. The first steps for that are not to catch the general exception Exception but the specific one, and to actually handle it once it occurs. In your case, you're catching some of the type IndexOutOfBoundsException, which can be prevented by doing appropriate checks in your loops.
Spacing/coding style. Some people use for (int i = 0; i < 5; i++) {, others for(int i=0; i<5; i++){ (among other variants) – there have always been heated debates about which is the "best way." Regardless of what you prefer, what is important is that you're consequent. This is maybe petty, but I feel that a consequent coding style seems more professional and it shows that care has been put into creating the code. However, that may just be my personal opinion.

Edit. There's one somewhat confusing feat in the code, namely that test() uses recursion but a loop as well. Generally, for clean recursion or looping, one would want to shy away from combinations. This seems to be an efficient solution to output the solutions, since you never store a lot in a list and output as soon as possible. I do believe that this would not be a recommendable approach if one wanted to store the solutions in a list, for instance.

I have split printFill(), I've renamed a lot of the variables and I've put the actual implementation of test() into a private method. A user can call test(24) or test(24, 5) for a maximum of five number in the combination and we'll take care of the rest from there.

As to optimization, look out especially for the line i = mainTarget - sum(list) + 1; which had unnecessary recursion calls, as well as if(ex) { return; } which looped unnecessarily but did nothing previously.

List<Integer> l = new ArrayList<Integer>(); – it is good practice to use an interface type as main type (List) and the implementation type (ArrayList) only for the actual initialization. But that's not a big thing and I think you'll want to care about that a little further down the road. :)

I have added some Javadoc but not consequently to all methods.

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

public class Numbers {
    private List<Integer> list;
    private boolean setNewStart;
    private boolean ex;
    private int newStart;

    public static void main(String[] args) {
        Numbers numbers = new Numbers();
        numbers.test(24);
    }

    public Numbers() {
        list = new ArrayList<Integer>();
        setNewStart = false;
        ex = false;
    }

    /**
     * Outputs all possible combinations for a number
     * @param target The number to compute combinations for
     */
    public void test(int target) {
        list = new ArrayList<Integer>();
        test(target, target, 10);
    }

    /**
     * Outputs all possible combinations for a number
     * @param target The number to compute combinations for
     * @param maxSize The maximum number of numbers for the combination
     */
    public void test(int target, int maxSize) {
        list = new ArrayList<Integer>();
        test(target, target, maxSize);
    }

    private void test(int tempTarget, int mainTarget, int maxSize) {
        for(int i = tempTarget; i > 0; i--) {
            if(ex) {
                return;
            }

            if(sum(list) + i > mainTarget) {
                // +1 because of the loop's i--
                i = mainTarget - sum(list) + 1;
                continue;
            }
            else if(list.size() >= maxSize) {
                int firstElem = list.get(0);
                if(firstElem * maxSize >= mainTarget) {
                    i = firstElem;
                    list.clear();
                }
            }
            else { /* sum(list) + i <= mainTarget && list.size() < maxSize */
                list.add(i);
                if(sum(list) == mainTarget) {
                    printList(list);
                    emptyList();

                    if(setNewStart) {
                        i = newStart;
                        setNewStart = false;
                    }
                }
                else {
                    test(i, mainTarget, maxSize);
                }
            }
        }
    }

    // Change helper functions to private

    /**
     * Empty the list appropriately to prepare
     * for the next possibility.
     */
    private void emptyList() {
        int lastElem = list.get(list.size()-1);

        if(lastElem > 1) {
            list.remove(list.size()-1);
            // commented out loop as it never happened
        }
        else if(lastElem == 1) {
            while(list.size() > 0 && list.get(list.size()-1) == 1) {
                list.remove(list.size()-1);
            }

            if(list.size() > 0) {
                setNewStart = true;
                // No -1 because of loop in test()
                newStart = list.remove(list.size()-1);
            }
            else {
                ex = true;
            }
        }
    }

    private int sum(List<Integer> list) {
        int sum = 0;
        for(int i = 0; i < list.size(); i++) {
            sum = sum + list.get(i);
        }
        return sum;
    }

    private void printList(List<Integer> list) {
        for(int i = 0; i < list.size()-1; i++) {
            System.out.print(list.get(i) + ",");
        }
        System.out.println(list.get( list.size()-1 ));
    }
}


DeepPtr: a deep-copying unique_ptr wrapper in C++ When using the pimple idiom it is necessary to represent your "impl" as a forward declared pointer in the header file.  This necessitates a lot of boilerplate code to implement the rule of five.

Instead, I want to wrap std::unique_ptr with a template class DeepPtr which automatically deep copies on copy construction, assignment, and "deep" swaps on move construction and move assignment.  The resulting class could also be convenient for "value-like" objects that need to be passed by handle due to polymorphism.

Areas of concern are:

Correct use of the swap idiom (should the local swap function be private/public or done some other way)?
Const correctness of the dereferencing operator overloads
Signature of the assignment operator function (const DeepPtr& other) which uses this const ref only to copy to temp.  This seems strange, but correct.
Any other pitfalls that could be caused by this class.

#pragma once
#include <iostream>
#include <memory>

template <typename T>
class DeepPtr
{
public:
    DeepPtr() :myPtr( nullptr ) {}

    DeepPtr( const T& value ) :myPtr( new T{ value } ) {}

    DeepPtr( const DeepPtr& other )
    :myPtr( nullptr )
    {
        if ( other )
        {
            myPtr = std::unique_ptr<T>{ new T{ *other } };
        }
    }

    DeepPtr( DeepPtr&& other )
    :myPtr( nullptr )
    {
        if ( other )
        {
            myPtr = std::unique_ptr<T>{ new T{ *other } };
        }
    }

    DeepPtr& operator=( const DeepPtr& other )
    {
        DeepPtr temp{ other };
        swap( *this, temp );
        return *this;
    }

    DeepPtr& operator=( DeepPtr&& other )
    {
        swap( *this, other );
        return *this;
    }

    static void swap( DeepPtr& left, DeepPtr& right ) { std::swap( left.myPtr, right.myPtr ); }

    T& operator*() { return *myPtr; }

    const T& operator*() const { return *myPtr; }

    T* const operator->() { return myPtr.operator->(); }

    const T* const operator->() const { return myPtr.operator->(); }

    const T* const get() const { return myPtr.get(); }

    operator bool() const { return (bool)myPtr; }

private:
    std::unique_ptr<T> myPtr;
};

You already accepted Loki's answer (and he made good points) but there is one comment I wanted to add regarding this:

  •Any other pitfalls that could be caused by this class.

Your class has no information on the concrete type held within, causing slicing in the presence of derived classes;

Consider this scenario:

class Base { ... }; // not abstract (can be instantiated)
class Derived: public Base { ... };

auto ptr1 = DeepPtr<Base>(new Derived{});
auto ptr2 = ptr1;

The last line will populate ptr2 with a Base instance that has all the sliced values from ptr2's Derived instance (because ptr2's constructorr calls new T, which resolves to new Base - not new Derived).

You have two possible solutions for this:

intrusive cloning (your class hierarchy rooted in Base needs to implement a virtual Base* clone() = 0 where each specialization of Base returns it's own instance); this cloning implementation would be then used for deep copy;
transparent cloning, based on template specialization of a factory function, by the derived type. I needed to implement something similar for the same reason (deep copy of polymorphic pointers). You can see here my implementation.

See the use of to_polymorphic functions in my question, and how they instantiate the correct cloning function, transparently.


Path Finding using Dynamic Programming I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I could. But I was not able to figure out which one is better, so please help. And if there is a way to improve my algorithm please tell me how I can do so.
Solution in tutorial

Author's solution uses dynamic programming. Let dpi, j be the minimum time required to arrive at the vertex i, if we visit j vertices (including vertices 1 and i). We have a DAG (directed acyclic graph), so we can compute it recursively (and memory constraints were a bit strict in this problem, so it's better to use recursion to compute it). Let's store the transposed version of the graph: if we had an edge (u, v) in the input, we will store (v, u). Then our function calc(i, j), which will compute the answer for dpi, j, will be like that: the base of dynamic programming is dp1, 1 = 0, all other states are equal to «-1». If we call calc(i, j), then it will work like that: if the state we want to compute is incorrect (j < 0), we return a very large integer number (any number that is greater than 109, because T ≤ 109). If the answer for this state has already been calculated, then we return dpi, j (it is easy do determine: if dpi, j ≠  - 1, then it has already been calculated). Else we begin to calculate the state. Firstly, let's put INF (a number greater than 109) into dpi, j. Then look at all the edges beginning in i and try to update dpi, j with the value of calc(to, j - 1) + w (to is the vertex at the endpoint of current edge, w is the weight of this edge). If this value is less than dpi, j, then we update dpi, j and store the information that our last update in dpi, j was from the vertex to. If we try to go by path which doesn't end in the vertex 1, then we get a value which is greater than 109, that's because that the only value we didn't denote as  - 1 is dp1, 1. So, now we have our calc function, let's compute the answer. We will iterate on the number of vertices in the path from n to 1 in descending order, and if calc(n, i) ≤ T, then we have found the answer, now we iterate on the parent vertices we stored while calculating our dp, until we come to vertex 1 (it's important because some participants sent solutions that continued even past vertex 1!) and print the answer.

My implementation of problem
#include<iostream>
using namespace std;

#define INT_MAX 5000

int getAns(int,int);
int n,a[INT_MAX][INT_MAX],dp[2][INT_MAX];
int main(){
    int m,t,u,v,time;
    cin>>n>>m>>t;
    for(int i=0;i<m;i++){
        cin>>u>>v>>time;
        a[u][v]=time;
    }
    cout<<1+getAns(t,1)<<endl;
    int i=1;
    while(dp[1][i]!=0){
        cout<<i<<" ";
        i=dp[1][i];
    }
    cout<<i;
}

int getAns(int time,int curr){
    if(time<0)
        return 0;

    for(int i=1;i<=n;i++){
        if(a[curr][i]!=0&&a[curr][i]<=time){
            int x=1+getAns(time-a[curr][i],i);
            if(dp[0][curr]<x){
                dp[0][curr]=x;
                dp[1][curr]=i;
            }
        }
    }
    return dp[0][curr];
}

How to compare the the Algorithms:

Either determine the complexity of your algorithm and the complexity of the solution in the tutorial.

If you want to avoid to determine the complexity based on the source code you can simply implement the tutorial solution and compare the runtime of your algorithm and the runtime of the of the tutorial-algorithm.
To get a good idea of the complexity behavior of both algorithms you need inputs of different lengths to approximate the runtime related to the size of the input.

How to improve yours
If your approach is very different you might not be able to improve your algorithm by looking on the tutorial-algorithm because they are too different.
If the Tutorial-algorithm is better at all, you can try to understand the steps it does and try to memorize the general idea of this steps for your next algorithms that address similar problems.


The Substring Game! challenge This is the Substring Game! challenge from HackerEarth:

  Watson gives Sherlock a string (let's denote it by S). Watson calculates all the substrings of S in his favourite order.

  According to the Watson's favourite order, all the substrings starting from first character of the string will occur first in the sorted order of their length, followed by all the substrings starting from the second character of the string in the sorted order of their length, and so on.

  For example, suppose S = abc. Then, all the substrings of S as per Watson's favourite order are:

  a
  ab
  abc
  b
  bc
  c

  Watson will ask Sherlock 'q' questions. In each question, Watson will give Sherlock a number and Sherlock has to speak the substring on that number. If there is no possible substring, then Sherlock has to speak -1.

Can the below code be improved to run in \$o(n^2)\$ complexity?

str=raw_input()
q=int(raw_input())
num=raw_input().split(' ')
substr=[]
for i,s in enumerate(str):
    #print i,s
    for j in range(i+1,len(str)+1):
        #print j
        substr.append(s+str[i+1:j])
#print substr
for i in range(0,q):
    try:
       print substr[int(num[i])-1]
    except IndexError:
       print -1

Sample Input
First line is the string - abc
Second line is the number of substrings asked- 2
Third line is the position of the substrings to return from the list of substrings- 2 5

The list of substrings would be ['a','ab','abc','b','bc','c']
Sample Output
ab
bc

Don't name things str.
Use a list comprehension to build substr.
s+str[i+1:j] would be simpler as str[i:j].
Iterate through num, rather than the range(q)
Your can wrap your print keywords with (), so this is a bit more Python 3 compatible.

This can get:

S = raw_input()
q = int(raw_input())
nums = map(int, raw_input().split(' '))

substr = [
    S[i:j+1]
    for i in range(len(S))
    for j in range(i, len(S))
]

for i in nums:
    try:
        print(substr[i-1])
    except IndexError:
        print(-1)

However this uses \$O(S^3)\$ of memory. So about \$10^{15}\$, or 1 petabyte of storage. So your code doesn't feasibly work.
Instead work things in the reverse order.

If you have the number \$5\$, you know it's \$5 \gt 3\$, \$5-3 = 2\$, \$2 \le 2\$, and so is S[1:1+2]. And so I'd use:

S = raw_input()
q = raw_input()
nums = map(int, raw_input().split(' '))

for num in nums:
    for i, s in enumerate(reversed(range(1, len(S)+1))):
        if num <= s:
            print(S[i:i+num])
            break
        num -= s
    else:
        print(-1)

Which is still better than yours in terms of time complexity, as it's \$O(nS)\$, \$~10^8\$, rather than \$O(n + S^2)\$, \$10^3 + 10^{10}\$.


Vba to create a new column and insert array formula My below code is the slowest sub in my workbook. I can't set it to put the Array in immediatley, because the mode is calculated incorrectly (calculates for just one site no)

Is there a way to cut this down without breaking the fully functioning code?

Sub ModeColumn()

Dim wb As Workbook, ws As Worksheet, LastRow As Long, rng As Range

Set wb = ThisWorkbook
Set ws = Worksheets("Data")
Set rng = ws.Cells(2, 15)
    ws.Cells(1, 15) = "MODE"
    LastRow = ws.Cells(ws.Rows.Count, 1).End(xlUp).Row                  'Finds the bottom populated row

    With ws.Range(ws.Cells(2, 15), ws.Cells(LastRow, 15))
           .Formula = "=IFERROR(MODE(IF(RC[-2]=AllSites,R2C12:R" & LastRow & "C12)),""N/A"")"
           .FormulaArray = .FormulaR1C1
    End With

End Sub

Here's what it looks like working

So above we can see that the selection works perfectly, but if I use the array formula right away, I get a lot of errors - so my time saving, breaks the expected result
And here's what it looks like if I just use "array" straight away

This is based on the following code

With ws.Range(ws.Cells(2, 15), ws.Cells(LastRow, 15))
       .FormulaArray = "=IFERROR(MODE(IF(RC[-2]=AllSites,R2C12:R" & LastRow & "C12)),""N/A"")"
End With

P.S I cannot (by request) use Excel Tables to make this easier

Usually with mass-Formula, I would recommend judicious use of the Application.Calculation property to ensure that you don't recalculate for every cell (3773 times in your example!) - but, in this case I am also going to recommend using the Range.FillDown method instead of assigning the Array Formula to every cell in the range.

(Also the MODE function is only included for Legacy Support, and has been replaced by the MODE.SNGL and MODE.MULT functions)

Application.Calculation = xlCalculationManual 'Do not recalculate formula until we say so!
With ws.Range(ws.Cells(2, 15), ws.Cells(LastRow, 15))
       .Cells(1,1).FormulaArray = "=IFERROR(MODE.SNGL(IF($M2=AllSites,$L$2:$L$" & LastRow & ")),""N/A"")" 'Set the Array Formula for the first cell
       '.Cells(1,1).FormulaArray = "=IFERROR(MODE.SNGL(IF(RC[-2]=AllSites,R2C12:R" & LastRow & "C12)),""N/A"")"'In R1C1 Notation
       .FillDown 'Copy the Array Formula down to the end
End With
Application.Calculation = xlCalculationAutomatic 'Reset Calculation Mode

(For comparison - running your method on 99999 rows of junk data took me 105 seconds.  Using the .Filldown method on the same data took 29 seconds, and 99% of that was just waiting for Excel to finish calculating the Worksheet after the functions where in!)


Rocket controller for a Unity game I'm currently learning C# so I can make real games with Unity. This is the first C# program I've built in Unity. Essentially what is does is control the thrust, and rotation of a GameObject shaped like a rocket. It may not necessarily be "real physics" but for my first program, it's good enough.

using UnityEngine;
using System.Collections;

public class RocketController : MonoBehaviour
{
    public float thrustMultiplier;
    public float rotationSpeed;
    private bool applyThrust = false;

    void Start () { transform.forward = transform.up; }

    // Check for misc keypresses
    void CheckMiscKeys ()
    {
        // Start applying thrust
        if (Input.GetKey (KeyCode.Space))
        {
            applyThrust = true;
        }

        // Stop applying thrust
        if (Input.GetKey (KeyCode.LeftShift))
        {
            applyThrust = false;
        }
    }

    // Check for rotation keypresses
    void CheckRotationKeys ()
    {
        // Rotate forward
        if (Input.GetKey (KeyCode.W))
        {
            transform.Rotate (rotationSpeed * new Vector3 (1, 0, 0));
        }

        // Rotate backwards
        if (Input.GetKey (KeyCode.S))
        {
            transform.Rotate (rotationSpeed * new Vector3 (-1, 0, 0));
        }

        // Rotate left
        if (Input.GetKey (KeyCode.A))
        {
            transform.Rotate (rotationSpeed * new Vector3 (0, -1, 0));
        }

        // Rotate right
        if (Input.GetKey (KeyCode.D))
        {
            transform.Rotate (rotationSpeed * new Vector3 (0, 1, 0));
        }
    }

    // Apply thrust to the rocket's rigidbody
    void ApplyRocketThrust ()
    {
        if (applyThrust)
        {
            Vector3 force = transform.forward * thrustMultiplier;
            rigidbody.AddForce(force);
        }
    }

    // Run physics calculations and misc events
    void FixedUpdate ()
    {
        CheckMiscKeys ();
        CheckRotationKeys ();
        ApplyRocketThrust ();
    }
}

What can be improved? Is there anything I'm doing wrong here?

UPDATE: Unity has built-in support for rebindable keys. I still urge you to setup rebindable keys, but a better way to do so would be through the system described by https://codereview.stackexchange.com/a/85568/35495.

One thing I really see happening with your code is that some poor gamer using a non-qwerty keyboard (like azerty or dvorak) will have an unplayable game because their keyboard has a different layout. for example, as an azerty-player I use ZQSD instead of WASD, and the W key is on the bottom line. In addition, there are players that use ESDF so they have a larger keyspace available for hotkeys.

The usual way of handling this is:

Make a .cfg or .ini file (basically a text file) in a config folder in your game

Put this code in there:

[Input]
button_W = forward;
button_S = back;
button_A = left;
button_D = right;
//any other buttons you need;

Then you load this into a dictionary when the game loads using a text file parser (plenty of examples for that online).

When the user then does any input, you check which button they pushed. Is it one of the configured buttons? then do the corresponding action. Is it a non-configured button? then return.

You can then use the default Unity launcher to configure these buttons, or you can configure these buttons using a custom config menu ingame.


Check if a given integer is power of two Given an integer, check if it's the power of two.

class Main {
  static class Solution {
    private final boolean answer;

    Solution(int num) {
      if (num <= 0) {
        answer = false;
      }
      else if ((num & (num - 1)) == 0) {
        answer = true;
      }
      else {
        answer = false;
      }
    }

    public boolean isPowerOfTwo() {
      return answer;
    }
  }

  public static void runTests() {
    // Falsy
    System.out.println(new Solution(-1).isPowerOfTwo());
    System.out.println(new Solution(0).isPowerOfTwo());
    System.out.println(new Solution(Integer.MAX_VALUE).isPowerOfTwo());
    System.out.println(new Solution(Integer.MIN_VALUE).isPowerOfTwo());

    //Truthy
    System.out.println(new Solution(1).isPowerOfTwo());
    System.out.println(new Solution(128).isPowerOfTwo());
    System.out.println(new Solution(1024).isPowerOfTwo());
  }

  public static void main(String[] args) {
    runTests();
  }
}

Code organization

There is nothing in the description and the posted code to justify storing the result of the "is power of 2" calculation in a class.
It would be better to simply return it.
The code is also simple enough that you could collapse the if-else chain to a single line:

public static boolean isPowerOfTwo(int num) {
    return num > 0 && (num & (num - 1)) == 0;
}

Testing

I suggest to look into proper unit testing methods,
for example JUnit4 which comes bundled in most IDEs.
The tests you wrote in main would look like this using JUnit4:

private boolean isPowerOfTwo(int num) {
    return Solution.isPowerOfTwo(num);
}

@Test
public void minus1_should_not_be_power_of_2() {
    assertFalse(isPowerOfTwo(-1));
}

@Test
public void zero_should_not_be_power_of_2() {
    assertFalse(isPowerOfTwo(0));
}

// ... and so on


Make the tree from a database into a tree of Java There is a task to get the data from the database (tree) and translate them into Java. They must maintain their properties (each entry has parent and descendants).

I'm taking data from database using Statement and ResultSet. The output is an arraylist of RowNode:

public class RawNode {
    int id;
    int parentId;
    String text;
//getters&setters here
}

Now we need to convert this array into the likeness of a tree.

How I do it:

public  List<Node> makeNewTree(ArrayList<RawNode> _rawNode) {
    List<Node> nodes = new ArrayList<>(_rawNode.size());
    Map<Node, RawNode> rawNodesByNodes = new HashMap<>(_rawNode.size()+10, 0.98f);
    Map<Integer, Node> nodesById = new HashMap<>(_rawNode.size()+10, 0.98f);

    try {
        for (RawNode rawNode : _rawNode) {
            Node node = new Node();
            node.setId(rawNode.getId());
            node.setText(rawNode.getText());
            rawNodesByNodes.put(node, rawNode);
            nodesById.put(rawNode.getId(), node);
            nodes.add(node);
        }

        for (Node node : nodes) {
            RawNode rawNode = rawNodesByNodes.get(node);
            Integer parentId = rawNode.getParentId();

            if (parentId == null) {
                node.setParent(null);
            } else {
                Node parent = nodesById.get(parentId);
                node.setParent(parent);
            }
        }

        for (Node node : nodes) {
            Node parentNode = node.getParent();
            if (parentNode == null) {
                continue;
            }
            parentNode.addChild(node);
        }
    } catch (Exception ex) {...}
    return nodes;
}

Where Node is:

  public class Node {
    private int id;
    private Node parent;
    private String text;
    private List<Node> children = new ArrayList<>();
}

Isn't that code redundant? Is there a more elegant solution?

OR-mapping

You fall into the object-relational impedance problem.

RawNode seems to be the same as Node but they are totally different in purpose. This doesn't even change if you use an OR-Mapper like Hibernate.

The following definitions assume you do not want to have an anemic domain model.

RawNode (mapping object)

It provides a concrete representation what came from the database. It is a datastructure only with no logic. It abstracts from the raw resultset where you access columns via column names or indices.

A RawNode is used as a datastructure to communicate with the database through the DAOs in both ways. A RawNode object is a value object. It has no assertion to consistency. You may check the values for consistency (e.g. Java Validation API) and get a list of constraint violations. But the current state of the object may be inconsistent. OR-Mapper can do validations but as they are not able to enforce business rules I would not rely on this.

Equality of these type of objects should be checked either be on all values or on none.

Node (business object)

Equality of a business object is checked on a global unique id.

This is a real business object. It has the assertion to be immutable in the current version. If the non unique values are different but the id is the same you have a different version of the business object. But it is the same object. A business object is ALWAYS consistent in respect to the information it provides. If it is not this is an error. Business objects enforce business rules and consistency when you try to make a change. They will process validation and structural checks to keep the whole system consistent.

Useful assertions

As you remap the business object to the mapping object in the DAO you can be sure that the communication object is consistent as the business object was consistent.

As you remap an unmodified mapping object from the database to a business object you can assume consistency.

Your code

Avoid continue

multiple return, break and continue are not refactring-friendly. They make it hard to extract methods if you want to sub divide a method.

What kind of exception do you expect?

You have all transient datastructure available. Do you expect a NullPointerException because a parent that was defined could not be found? If that is the case you should fix the algorithm that produces that inconsistency and not try to straighten it for further algorithms. The decision to fix the data is depending on your influence on the data holder of course.

Extract methods

Extract the following responsibilities into separate methods:
 1. Build Nodes without parents and children from RawNodes
 2. Build a temporaray map with Node by Id
 3. Set parent child relationship


Producing a sorted wordcount with Spark I'm currently learning how to use Apache Spark. In order to do so, I implemented a simple wordcount (not really original, I know). There already exists an example on the documentation providing the needed code. However, I tried to go one step further and to produce the result as a sorted list (by frequence) by using the spark modules.

A use case would be sortedWordcount("I fish a fish") ->  [(fish, 2), (I,1), (a,1))]

Here is how I proceed:

public List<String> sortedWordcount() {
    SparkConf conf = new SparkConf().setAppName("wordcount").setMaster("local");
    JavaSparkContext sc = new JavaSparkContext(conf);

    JavaRDD<String> lines = sc.textFile("myFile.txt");

    // classical wordcount, nothing new there
    JavaRDD<String> words = lines.flatMap(new FlatMapFunction<String, String>() {
                public Iterable<String> call(String s) {
                    return Arrays.asList(s.split(" "));
                    }
                });
    JavaPairRDD<String, Integer> pairs = words.mapToPair(new PairFunction<String, String, Integer>() {
                public Tuple2<String, Integer> call(String s) {
                    return new Tuple2<String, Integer>(s, 1);
                }
            });
        JavaPairRDD<String, Integer> counts = pairs.reduceByKey(new Function2<Integer, Integer, Integer>() {
                public Integer call(Integer a, Integer b) {
                    return a + b;
                }
            });

    // to enable sorting by value (count) and not key -> value-to-key conversion pattern
    JavaPairRDD<Tuple2<Integer, String>, Integer> countInKey = counts.mapToPair(a -> new Tuple2(new Tuple2<Integer, String>(a._2, a._1), null)); // setting value to null, since it won't be used anymore

    List<Tuple2<Tuple2<Integer, String>, Integer>> wordSortedByCount = countInKey.sortByKey(new TupleComparator(), false).collect();

    List<String> result = new ArrayList<>();
    IntStream.range(0, wantedSize).forEach(i -> result.add(wordSortedByCount.get(i)._1._2));
    return result;
}

private class TupleComparator implements Comparator<Tuple2<Integer, String>>, Serializable {
    @Override
    public int compare(Tuple2<Integer, String> tuple1, Tuple2<Integer, String> tuple2) {
        return tuple1._1 < tuple2._1 ? 0 : 1;
    }
}

To sum up on this code work:

it stores the text as a list of word
it changes this list of word into a list of tuple, each tuple being (word, 1) with word as key
it combine tuples with the same key and counts them, tuples are now (word, freqWord)
it changes the way tuples are displayed, they now become ((freqWord, word), null)
tuples are sorted by key (see the Comparator implementation)

My main concern is about performances, but I'll gladly welcome any critiques on any aspects of this code. Is there any way to achieve the same goal in less / more efficient steps?

I'll review this code with keeping in mind that you want to leave Apache Spark intact, as you intend to use it in the future for purposes it is intended to do.
I strongly believe that your current code can be written in pure Java 8, though that is not the point of the question.

Use lambdas wherever you can!

This will greatly enhance readability of your code.

As an example:

JavaRDD<String> words = lines.flatMap(new FlatMapFunction<String, String>() {
            public Iterable<String> call(String s) {
                return Arrays.asList(s.split(" "));
                }
            });

could be rewritten as the following (I checked and FlatMapFunction is indeed an interface that qualifies to be a functional interface):

JavaRDD<String> words = lines.flatMap(str -> Arrays.asList(s.split(" ")));

Similarly it holds that:

JavaPairRDD<String, Integer> pairs = words.mapToPair(new PairFunction<String, String, Integer>() {
            public Tuple2<String, Integer> call(String s) {
                return new Tuple2<String, Integer>(s, 1);
            }
        });

can be rewritten as:

JavaPairRDD<String, Integer> pairs = words.mapToPair(str -> new Tuple2<>(s, 1));

If type inference is not strong enough, then you need to write: new Tuple2<String, Integer>(s, 1).

Lastly it also holds for:

    JavaPairRDD<String, Integer> counts = pairs.reduceByKey(new Function2<Integer, Integer, Integer>() {
            public Integer call(Integer a, Integer b) {
                return a + b;
            }
        });

can be written as:

JavaPairRDD<String, Integer> counts = pairs.reduceByKey((a, b) -> a + b);

or even better:

JavaPairRDD<String, Integer> counts = pairs.reduceByKey(Integer::sum);

Use the new way to write comparators

You can much much easier write comparators in Java 8, it works via key extraction, you can turn this code:

private class TupleComparator implements Comparator<Tuple2<Integer, String>>, Serializable {
    @Override
    public int compare(Tuple2<Integer, String> tuple1, Tuple2<Integer, String> tuple2) {
        return tuple1._1 < tuple2._1 ? 0 : 1;
    }
}

into this code:

Comparator<Tuple2<Integer, String>> tupleComparator = Comparator.comparing(tuple2 -> tuple2._1);

This will automatically and automagically create a working comparator that works by comparator the _1 field of tuple2, which is inferred to be Tuple2<Integer, String>.

Now this line:

List<Tuple2<Tuple2<Integer, String>, Integer>> wordSortedByCount = countInKey.sortByKey(new TupleComparator(), false).collect();

can become:

List<Tuple2<Tuple2<Integer, String>, Integer>> wordSortedByCount =
countInKey.sortByKey(Comparator.comparing(tuple2 -> tuple2._1, false).collect();

Normally one would use method references in case of Comparator.comparing, if Tuple2 had a get1() method, then you would write it as Comparator.comparing(Tuple2::get1).

Upon further inspecting your code I see that you possibly intentionally have made your comparator serializable, if you need that for Apache Spark, then you can do that as well, though the solution does get a fair bit uglier then:

List<Tuple2<Tuple2<Integer, String>, Integer>> wordSortedByCount =
countInKey.sortByKey((Comparator<Tuple2<Integer, String>> & Serializable)Comparator.comparing(tuple2 -> tuple2._1, false).collect();

Via this mechanism it is possible to make a type implement a wrapper interface without writing boilerplate. It is more common in the form of (Runnable & Serializable)someRunnable than in this form though.

Final words

Lastly your code formatting is in need for some improvements with respect to indenting the anonymous classes, but it may be an oversight and the rest of the code looks great.

When I have some time I'd be eager to show you a pure Java 8 solution as I strongly believe that Apache Spark is making a mess of your code currently. I do understand however that you need to operate with Apache Spark at some point and for that you may be forced to use Apache Spark's classes.

My method using Java 8

As addendum I'll show how I would identify your problem in question and show you how I would do it.

Input: An input file, consisting of words.
Output: A list of the words sorted by frequency in which they occur.

Map<String, Long> occurenceMap = Files.readAllLines(Paths.get("myFile.txt"))
        .stream()
        .flatMap(line -> Arrays.stream(line.split(" ")))
        .collect(Collectors.groupingBy(i -> i, Collectors.counting()));
List<String> sortedWords = occurenceMap.entrySet()
        .stream()
        .sorted(Comparator.comparing((Map.Entry<String, Long> entry) -> entry.getValue()).reversed())
        .map(Map.Entry::getKey)
        .collect(Collectors.toList());

This will do the following steps:

Read all lines into a List<String> (care with large files!)
Turn it into a Stream<String>.
Turn that into a Stream<String> by flat mapping every String to a Stream<String> splitting on the blanks.
Collect all elements into a Map<String, Long> grouping by the identity (i -> i) and using as downstream Collectors.counting() such that the map-value will be its count.
Get a Set<Map.Entry<String, Long>> from the map.
Turn it into a Stream<Map.Entry<String, Long>>.
Sort by the reverse order of the value of the entry.
Map the results to a Stream<String>, you lose the frequency information here.
Collect the stream into a List<String>.

Beware that the line .sorted(Comparator.comparing((Map.Entry<String, Long> entry) -> entry.getValue()).reversed()) should really be .sorted(Comparator.comparing(Map.Entry::getValue).reversed(), but type inference is having issues with that and for some reason it will not compile.

I hope the Java 8 way can give you interesting insights.


Implementation of linear regression in Python I wrote an implementation for multivariate linear regression in Python, for data in this link: http://www-bcf.usc.edu/~gareth/ISL/Advertising.csv

My main focus is to avoid loops as much as possible by using vectorization, and letting numpy's functions do all the work.

How can I improve my code for performance and enhanced vectorization?

This is my code:

import numpy as np
import matplotlib.pyplot as plt

# read data matrix
data = np.genfromtxt('Advertising.csv', delimiter=',',dtype=float, skiprows=1)
m, n = data.shape

X = data[:, 0:n-1]
Y = data[:, n-1].reshape((m, 1))

# add unity vector column with size m to the X matrix, to account for theta_0
ones = np.ones((m, 1))
X = np.hstack((ones, X))

iterations = 500        # gradient descent iterations count
alpha = 0.01            # learning rate

theta = np.random.rand(n, 1)

def plotData():
    # get rid of X_0 constants column
    features = X[:, 1: n]
    plt.figure(1)

    plt.subplot(131)
    plt.plot(features[:, 0], Y, 'bo')
    plt.title('Ad dollars spent on TV')
    plt.ylabel('Sales')

    plt.subplot(132)
    plt.plot(features[:, 1], Y, 'ro')
    plt.title('Ad dollars spent on Radio')
    plt.ylabel('Sales')

    plt.subplot(133)
    plt.plot(features[:, 2], Y, 'yo')
    plt.title('Ad dollars spent on Newspaper')
    plt.ylabel('Sales')

    plt.show()

def computeCost():
    hypothesis = np.dot(X, theta);
    delta = np.dot((hypothesis - Y).transpose(), (hypothesis - Y))
    return (1 / m) * delta

# normalizeFeatures: scale-normalize all features to speed up gradient descent convergence
def normalizeFeatures():
    # 1) generate Average vector mu, contains the average of each feature in the X matrix
    # 2) generate Std. deviation vector sigma, contains the std. dev. of each feature in the X matrix
    # 3) subtract average value and divide by the standard deviation, for each feature column
    mu = np.ones((1, n))
    sigma = np.ones((1, n))

    # range() starts from 1 not 0, to skip the first all-ones constants column in the features matrix
    for i in range(1,n):
        mu[0][i] = np.mean(X[:, i])
        sigma[0][i] = np.std(X[:, i])
        X[:, i] = (X[:, i] - mu[0][i]) / sigma[0][i]

    return mu, sigma;

# gradientDescent() calculates hypothesis equation coefficients using gradient descent algorithm
def gradientDescent(theta):
    # vector to keep track of progression of cost function with each iteration
    J_history = np.ones((iterations, 1))

    for i in range(iterations):
        delta = np.dot((np.dot(X,theta) - Y).transpose(), X).transpose()
        theta -= (alpha/m) * delta
        J_history[i, 0] = computeCost()

    plt.plot(np.linspace(0, iterations, iterations), J_history)
    plt.title('Cost function against number of iterations')
    plt.xlabel('Number of iterations')
    plt.ylabel('Cost function J(theta)')
    plt.show()
    return

# normalEquation() calculates hypothesis equation coefficients analytically
def normalEquation():
    A = np.linalg.pinv(np.dot(X.transpose(), X))
    B = np.dot(X.transpose(), Y)
    theta = np.dot(A, B)

    return theta

def predict(x_vector, mu, sigma):
    # scale feature vector
    for i in range(1, n):
        x_vector[0][i] = (x_vector[0,i]- mu[0][i]) / sigma[0][i]

    return np.dot(x_vector, theta)

if __name__ == '__main__':
    plotData()
    mu, sigma = normalizeFeatures()
    gradientDescent(theta)
    print('Hypothesis coefficients from gradient descent:\n {}'.format(theta))
    print('Hypothesis coefficients from normal equation:\n {}'.format(normalEquation()))

    prediction_vector = np.array([1, 40, 40, 48]).reshape(1,4)
    print('Prediction for values [1, 40, 40, 48] is {}'.format(predict(prediction_vector, mu, sigma)))

Just reviewing normalizeFeatures.

Instead of a comment explaining what the function does, write a docstring. (Docstrings are available from the interactive interpreter via the help function.)
The function operates on the global variable X. This makes the function inflexible (you can't use it for anything other than modifying the particular variable X), and hard to test. It would be better if the function received the array as an argument, so that it could be used on any array:

def normalize_features(a):
    """Given array a with shape (m, n), update it so that each column
    (except column 0) has mean 0 and standard deviation 1. Return
    arrays mu, sigma with shape (1, n) where mu[0,i] is the original
    mean of a[:,i] and sigma[0,i] is the original standard deviation
    of a[:,i].

    """

This complicated specification can be simplified. First, we can avoid the "(except column 0)" bit and let the caller pass X[:,1:] if they want to leave column 0 alone. Second, we can return mu and sigma with shape (n,) instead of (1, n) and let the caller reshape if necessary (which it probably isn't).

def normalize_features(a):
    """Given array a with shape (m, n), update it so that each column has
    mean 0 and standard deviation 1. Return arrays mu, sigma giving
    the original mean and standard deviation of each column of a.

    """

The loop over the columns is unnecessary because numpy.mean and numpy.std take an axis argument. So the body of the function can be:

mu = a.mean(axis=0)
sigma = a.std(axis=0)
a[...] = (a - mu) / sigma
return mu, sigma

It might be better not to update the array X, but to compute a new array containing the normalized data (this uses twice the memory, but that's only a concern if X is really big). If you did this, then you wouldn't need to remember the original mean and standard deviation (because you still have the original data) and so the normalization becomes a one-liner:

def normalize_features(a):
    """Return copy of a with each column normalized so that it has mean 0
    and standard deviation 1.

    """
    return (a - a.mean(axis=0)) / a.std(axis=0)

Consider using scipy.stats.zscore instead of writing your own.


Project Euler #10 in Swift - Summation of primes I just finished Project Euler #10 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.

I hope I learned some from the previous code reviews :).

  The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

  Find the sum of all the primes below two million.

import Foundation

func summationOfPrimesBelow(var n:Int) -> Int {

    assert(n > 0, "argument must be positive")

    var composite = [Bool](count: n, repeatedValue: false)

    var x = 2
    let maxPrime = Int(ceil(sqrt(Double(n))))

    while x <= maxPrime {
        if composite[x] == false {
            for y in stride(from: x * x, through: n - 1, by: x) {
                composite[y] = true
            }
        }
        x++
    }

    var result = 0
    for i in stride(from: 2, through: composite.count - 1, by: 1) {
        if composite[i] == false {
            result += i
        }
    }

    return result
}

func euler10() {
    let number = summationOfPrimesBelow(2_000_000)

    println(number)
}

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

printTimeElapsedWhenRunningCode(euler10)

The code executes in 0.012s in Release mode.

Since we know that primes can be represented by 6x+1 or 6x-1 except for 2,3, we could skip them as follows:

//Handle explicitly for n<5 i.e for n = 0,1,2,3,4 and proceed otherwise.
if n<3 { // n=0,1,2
    return 0
}
if n<5 {// n = 3,4
    return (n==3)?2:5
}

var x = 5
while x <= maxPrime {
    if composite[x] == false {
        for y in stride(from: x * x, through: n - 1, by: x) {
            composite[y] = true
        }
    }
    x+=2
    if x<n && composite[x] == false {
        for y in stride(from: x * x, through: n - 1, by: x) {
            composite[y] = true
        }
    }
    x+=4
}

var result = 5 // 2 + 3
for i in stride(from: 5, through: composite.count - 1, by: 4) {
    if composite[i] == false {
        result += i
    }
    i+=2
    if i<n && composite[i] == false {
        result += i
    }
}

Results: With your code it took me 33ms with mine its down to 23ms.


Counting different kinds of line terminator characters in files Can someone take a look if this code piece is ok. I'm most interested whether the goroutines are used correctly, but also general Go best practices.

package main

import (
    "fmt"
    "io/ioutil"
    "os"
    "path/filepath"
    "regexp"
)

type Endings struct {
    crlf, lf uint
}

func check(e error) {
    if e != nil {
        panic(e)
    }
}

func getFileList(searchDir string) []string {
    fileList := []string{}
    filepath.Walk(searchDir, func(path string, f os.FileInfo, err error) error {
        if !f.IsDir() {
            fileList = append(fileList, path)
        }
        return nil
    })

    return fileList
}

func getFileEndings(filename string, c chan Endings) {
    fileContent, err := ioutil.ReadFile(filename)
    check(err)
    c <- countEndings(string(fileContent))
}

func countEndings(s string) Endings {
    crlf := regexp.MustCompile("\r\n")
    lf := regexp.MustCompile("\n")

    x := len(crlf.FindAllStringIndex(s, -1))
    y := len(lf.FindAllStringIndex(s, -1))

    return Endings{uint(x), uint(y - x)}
}

func splitIntoChunks(arr []string, chunkSize int) [][]string {
    if chunkSize <= 0 {
        panic("chunk size too small")
    }

    if len(arr) <= chunkSize {
        return [][]string{arr}
    }

    numChunks := int(len(arr)/chunkSize) + 1
    chunks := make([][]string, numChunks)

    for i := 0; i < numChunks; i++ {
        l := i * chunkSize
        u := l + chunkSize

        if u > len(arr) {
            u = len(arr)
        }

        chunks[i] = arr[l:u]
    }

    return chunks
}

func main() {
    searchDir := os.Args[1]
    c := make(chan Endings)
    chunkSize := 1000

    fileList := getFileList(searchDir)

    count := Endings{0, 0}
    for _, chunk := range splitIntoChunks(fileList, chunkSize) {
        for _, file := range chunk {
            go getFileEndings(file, c)
        }

        for _ = range chunk {
            result := <-c

            count.crlf += result.crlf
            count.lf += result.lf
        }
    }

    fmt.Printf("crlf: %d, lf: %d\n", count.crlf, count.lf)
}

Your program works fine and you are correctly using goroutines, but the code isn't very idiomatic.

Producer/Consumer architecture

What we have here is a typical producer/consumer scenario. The producer is filepath.Walk() wich returns a list of files, and the consumers are goroutines executing regex on file content.

So instead of the splitIntoChunks() method, we could just have a chan string: the producer sends file names to the channel, and the consumers loop over it and parse the file content.

This have two main advantages:

code is easier to read
producer and consumer can work in parallel

So the code would looks like

results := make(chan Endings, 2) // chan to get the results of each worker
var wg sync.WaitGroup
wg.Add(2)
files := make(chan string, 1000) // channel containing file list
for i := 0; i < 2; i++ {
    go run(files, results, &wg) // start the producers
}
filepath.Walk(searchDir, func(path string, f os.FileInfo, err error) error {
    if !f.IsDir() {
        files <- path // feed the channel
    }
    return nil
})
close(files)
wg.Wait()
close(results)

Work on []byte rather than on string

This is a general advice regarding performances: always prefer working on []byte instead of working on string to avoid extra allocations.
The regex package has methods to work on string or on byte slice, so instead of

fileContent, err := ioutil.ReadFile(filename)
c <- countEndings(string(fileContent))
...
x := len(crlf.FindAllStringIndex(s, -1))

we can just use

fileContent, err := ioutil.ReadFile(fileName)
...
x := len(crlf.FindAllIndex(fileContent, -1))

Don't panic

The code shouldn't panic on every error. For example, if the user running the program don't have the permission to read a file in searchDir, the program should not crash but rather log the error

so avoid method like this:

func check(e error) {
    if e != nil {
        panic(e)
    }
}

instead handle the error localy:

fileContent, err := ioutil.ReadFile(fileName)
if err != nil {
    fmt.Printf("fail to read file %s: %v\n", fileName, err)
}

Other consideration

It's better to define regex as global var:

var (
    crlf = regexp.MustCompile("\r\n")
    lf   = regexp.MustCompile("\n")
)

It's also better to use the flag package to parse arguments instead of relying on os.Args

Here is the final version of the code:

package main

import (
    "flag"
    "fmt"
    "io/ioutil"
    "os"
    "path/filepath"
    "regexp"
    "sync"
)

var (
    crlf = regexp.MustCompile("\r\n")
    lf   = regexp.MustCompile("\n")
)

type Endings struct {
    crlf, lf uint
}

func (e *Endings) countEndings(fileName string) {
    c, err := ioutil.ReadFile(fileName)
    if err != nil {
        fmt.Printf("fail to read file %s: %v\n", fileName, err)
    }
    x := len(crlf.FindAllIndex(c, -1))
    y := len(lf.FindAllIndex(c, -1))

    e.crlf += uint(x)
    e.lf += uint(y - x)
}

func run(files <-chan string, results chan<- Endings, wg *sync.WaitGroup) {
    e := &Endings{}
    for f := range files {
        e.countEndings(f)
    }
    results <- *e
    wg.Done()
}

func main() {

    searchDir := flag.String("dir", "dir", "directory to search")
    nWorker := flag.Int("n", 2, "number of worker")
    flag.Parse()

    results := make(chan Endings, *nWorker)

    var wg sync.WaitGroup
    wg.Add(*nWorker)
    files := make(chan string, 1000)
    for i := 0; i < *nWorker; i++ {
        go run(files, results, &wg)
    }
    filepath.Walk(*searchDir, func(path string, f os.FileInfo, err error) error {
        if !f.IsDir() {
            files <- path
        }
        return nil
    })
    close(files)
    wg.Wait()
    close(results)

    count := &Endings{}
    for e := range results {
        count.crlf += e.crlf
        count.lf += e.lf
    }
    fmt.Printf("crlf: %d, lf: %d\n", count.crlf, count.lf)
}

Performance

The new code is slightly faster:

old:

$ time ./test ~/go/src/golang.org
crlf: 6231, lf: 1589462
./test ~/go/src/golang.org  1,78s user 0,23s system 167% cpu 1,201 total

new:

$ time ./test -dir ~/go/src/golang.org -n 6
crlf: 6231, lf: 1589462
./test -dir ~/go/src/golang.org -n 6  1,48s user 0,18s system 181% cpu 0,911 total