Multifunctional Monty Hall Simulator Based on this question on math.SE regarding probabilities in variations on the Monty Hall problem, I cobbled up a simulator in Ruby to give myself an introduction to the language.

Since this is my first Ruby program, I'm especially looking for feedback regarding Ruby style, but I would love any general code improvement suggestions as well (all the results seem correct, so I think the math is good). I'm more comfortable with Python and shell scripting, so I'm sure my preferences show through here.

Current functionality:

The program allows simulations of the following scenarios:

The host (Monty Hall) opens all but 1 door and the player switches to the door Monty left closed (the classic version)
Monty opens 1 extra door, leaving the rest closed, and you decide to switch to a different closed door (the premise of the math.SE question)
You pick a door and don't switch no matter what Monty does

Currently, it's hard-coded to simulate scenario #2 with 5 doors 1000 times, but that can be changed by switching the comment on the second-to-last line.

puts "Hello Monty!"

$wins = 0.0
$goats = 0.0

def choose_doors(num_doors)
  door_range = (1..num_doors)

  winning_door = rand(door_range)
  player_choice = rand(door_range)

  losing_doors = door_range.to_a - [winning_door] - [player_choice]
  monty_open = losing_doors.sample  # used when Monty opens 1 non-winning door

  return player_choice, monty_open, winning_door
end

def switch_door_multiple(choice, revealed, num_doors)
  # Monty revealed only 1 other door
  door_range = (1..num_doors)
  door_choices = door_range.to_a - [choice] - [revealed]

  new_choice = door_choices.sample
end

def count_result(final_choice, winning_door)
  if final_choice == winning_door
    $wins += 1
  else
    $goats += 1
  end
end

def simulate(num_doors, runs, strategy)
  for i in 1..runs
    player_door, open_door, winning_door = choose_doors(num_doors)
    if strategy == 1 # switch, 1 choice
      if player_door != winning_door
        player_door = winning_door
      else
        player_door = -1
      end
    elsif strategy == 2 # switch, multiple choice
      player_door = switch_door_multiple(player_door, open_door, num_doors)
    else
      # keep initial door
    end
    count_result(player_door, winning_door)
  end

  puts "wins: " + $wins.to_s
  puts "goats: " + $goats.to_s
  puts "win percentage: " + (100 * ($wins / ($wins + $goats))).to_s + "%"
end

def prompt_user
  print "Number of doors: "
  input_num_doors = gets.chomp.to_i
  while input_num_doors < 3
    puts "This only works with 3 or more doors"
    print "Number of doors: "
    input_num_doors = gets.chomp.to_i
  end

  print "Number of runs: "
  input_runs = gets.chomp.to_i
  while input_runs < 1
    puts "Need 1 or more runs"
    print "Number of runs: "
    input_runs = gets.chomp.to_i
  end

  puts "Simulation: "
  puts "[1]: Monty opens all but 1 door and you decide to switch"
  puts "[2]: Monty opens 1 door and you switch to a different closed door"
  puts "[3]: Keep your door - you don't switch no matter what Monty does"
  print "Choose a game type (1/2/3): "
  input_strategy = gets.chomp.to_i

  while ![1, 2, 3].include? input_strategy
    print "Choose a game type (1/2/3): "
    input_strategy = gets.chomp.to_i
  end

  return input_num_doors, input_runs, input_strategy
end

# num_doors, num_runs, strategy = prompt_user
num_doors, num_runs, strategy = 5, 1000, 2

simulate(num_doors, num_runs, strategy)

Style is generally ok, but I'd recommend a more object-oriented approach - especially if you want to learn Ruby, since Ruby is thoroughly object-oriented.

Things I noticed:

Global variables (apart from built-in ones like $ARGV) are rare in Ruby. They're rare because you'll usually want to encapsulate your data in objects.
No need to write return at the end of methods; the result of the last expression is always implicitly returned.
You've quite a few methods that take 3 arguments, and some that return tuples. This is a general code-smell, in my opinion, because it's not very descriptive. Long parameter lists aren't easy to remember or parse, and multiple return values are also a fairly opaque data structure.
Overall structure is indeed very script'y and procedural.

Basically, you're passing all your data around, letting the methods modify them. A bit of basic object modelling could make your code better by encapsulation all that.

For instance, here's one way to model the game itself (not the full simulation). Just to give you something to chew on.

# A really simple Door class
class Door
  def initialize
    @open = false
  end

  def open?
    @open
  end

  def open!
    @open = true
  end
end

# This class models 1 instance/round of the game
class Game
  attr_reader :doors

  # Init a new game with +door_count+ doors, and randomly
  # picks one of them to be the winning door.
  # Raises an exception if door count is less than 3
  def initialize(door_count)
    raise ArgumentError, "There must be at least 3 doors" if door_count.to_i < 3
    @doors = Array.new(door_count.to_i) { Door.new }
    @winning_door = @doors.sample
  end

  # Set a random door as the player's pick
  # Raises an exception if there are no doors left to pick
  def pick_door
    raise "No doors to pick" if pickable_doors.empty?
    @picked_door = pickable_doors.sample
  end

  # open +count+ number of doors
  def open_doors(count)
    shuffled = openable_doors.shuffle
    [count, shuffled.count].min.times do
      shuffled.pop.open!
    end
  end

  # Returns true if the player's pick is the winning door
  def won?
    @picked_door == @winning_door
  end

  # Array of doors that an be picked by the player
  def pickable_doors
    closed_doors - [@picked_door]
  end

  # Array of doors that can be safely opened by Monty
  def openable_doors
    closed_doors - [@picked_door, @winning_door]
  end

  # Array of closed doors
  def closed_doors
    @doors.reject(&:open?)
  end
end

The Door class may seem sort of pointless (and indeed there are many ways to do things), but instead of using, say, an array of plain booleans, an array of door objects allows us to reference specific doors. Not as array indices, but as the doors themselves.

Again, I'm not saying this is the only - or even a particularly great - way of doing things. But it reads pretty well, and is easy to use.

For instance, this code will play a basic game with 3 doors, of which 1 will be revealed, and the player changes their pick:

game = Game.new(3)
game.pick_door     # initial pick
game.open_doors(1) # reveal what's behind a door
game.pick_door     # change pick
game.won?          # => (~67% chance of a win)

You could make classes for Choice, Prize, or, heck, even Goat, if you want to completely model everything. But I'd at least make a SimulationRun (or similar) class.

This would encapsulate the notion of "a run" as in "N rounds of the game", and keep state out of the global scope.

I'd also consider modelling the actors (the player and Monty), and inject them into the simulation.

For instance, imagine being able to say something like:

sim = Simulation.new(3, Monty::Classic, Player::Fickle)
win_ratio = sim.run(1000)

i.e. create a simulation using 3 doors, run it 1000 times, using the "classic" Monty rules that leave two doors unrevealed, and a player that'll always pick a different door second time around.

Monty and the player could be classes or simply lambdas. For instance, the player can simply be a lambda that returns true/false when asked whether to change the pick. And "the Monty" could simply return the number of doors to open. Or you could make them a lot more complex, letting the player's reaction depend on, say, the phase of the Moon or something.

Again, I'm not saying that the above is the only way - or even a particularly great way - to do things, but I'd certainly encourage you to try doing object modelling of some kind.

All of this is of course presuming you don't just want to do the math, but actually want to be empirical :)


"Lowest unique number" challenge Again, out of fun on Saturday night, I decided to solve the following problem from CodeEval.

  The challenge is finding the index of the lowest unique number.

  There is a game where each player picks a number from 1 to 9, writes
  it on a paper and gives to a guide. A player wins if his number is the
  lowest unique. We may have 10-20 players in our game.

  Input sample:

  Your program should accept as its first argument a path to a filename.

  You're a guide and you're given a set of numbers from players for the
  round of game. E.g. 2 rounds of the game look this way:

3 3 9 1 6 5 8 1 5 3
9 2 9 9 1 8 8 8 2 1 1

  Output sample:

  Print a winner's position or 0 in case there is no winner. In the
  first line of input sample the lowest unique number is 6. So player 5
  wins.

5
0

  Suppose you're given a set of numbers from players for the round of
  game. E.g. 2 rounds of the game look this way:

3 3 9 1 6 5 8 1 5 3
9 2 9 9 1 8 8 8 2 1 1

  The output is the winner's position, or 0 in case there is no winner.
  In the first line of input sample the lowest unique number is 6, so
  player 5 wins (it was player number 5 who threw number 6). And in the
  second set there is no unique number, so the output will be 0.

  So, the overall output will be:

5
0

I solved this problem correctly using Linq in the following code, but the performance is not that great at 255 ms for about 100 data points. Any suggestion for improving performance or perhaps another novel solution? The data have to be read from a text file in CodeEval, so my code is structured around that way.

static void Main(string[] args)
{
   using (StreamReader reader = File.OpenText(args[0]))
        {
            while (!reader.EndOfStream)
            {
                var linevalue = reader.ReadLine();
                if (!string.IsNullOrEmpty(linevalue))
                {
                    var numbers = linevalue.Split(' ');
                    var groups = numbers.GroupBy(x => x).Select(g => new
                    {
                        number = g.Key,
                        freq = g.Count()
                    });

                    var nonRepeated = groups.Where(x => x.freq == 1).ToList();
                    if (nonRepeated.Count() != 0)
                    {

                            var singles = nonRepeated.Select(x => x.number).ToList();
                            var smallest = singles.Min();
                            var playerNumber = Array.IndexOf(numbers, smallest);
                            Console.WriteLine(playerNumber + 1);

                    }
                    else
                    {
                        Console.WriteLine("0");
                    }
                }
            }
        }
}

I threw your code through a profiler and it told me that ToList was responsible for quite a bit of your execution time. So why is that?

You have 2 ToList calls in your code::

var nonRepeated = groups.Where(x => x.freq == 1).ToList();
if (nonRepeated.Count() != 0)
{
    var singles = nonRepeated.Select(x => x.number).ToList();
    var smallest = singles.Min();

So what happens here? You start by iterating through groups to find those with freq equal to 1. Count is optimized to lists, so that one should be constant time. Then you iterate through nonRepeated to select number and then finally you iterate through it to select the minimum value. That's a lot of iterations. Let's try to cut that down:

var nonRepeated = groups.Where(x => x.freq == 1)
                        .Min(x => x.number);
if (nonRepeated != null)
{
    var playerNumber = Array.IndexOf(numbers, nonRepeated);

By comparing the execution time of this and the other one (on my system) it seems we have achieved a small improvement. Not enough to brag about though. Since we don't have any ToList calls anymore, I profiled the code once again. This time it is Min that takes up the time (not really surprising - It is forcing the GroupBy, Select and Where to be evaluated). So our bottleneck is (still) the LINQ queries. Can we speed it up?

  Hint: LINQ usually have a slight overhead compared to doing things 'manually'.

Let's try to do these things ourselves, instead of relying on LINQ. Let's replace that GroupBy and Select stuff:

var values = new Dictionary<string, int>();
foreach (var number in numbers)
{
    if (values.ContainsKey(number)) //No curly-brackets to keep it short.
        values[number]++;
    else
        values.Add(number, 1);
}

A benchmark of the code told me that was a clear improvement. Nice! But the profiler still says that Where and Min are expensive. Let's do those manually too.

string minValue = null;
foreach (var value in values)
{
    if (value.Value == 1)
    {
        if (minValue == null || String.Compare(value.Key, minValue, StringComparison.InvariantCulture) == -1)
            minValue = value.Key;
    }
}

if (minValue != null)
    ...

Once again, it seems we got an overall improvement in performance. Interestingly now the bottlenecks seem to be WriteLine and OpenText. We could try to experiment with other ways of reading from file/writing to console, but I don't really feel like doing that right now (and I don't think the 'easy' methods like File.ReadAllLines and File.ReadLines is much faster than your way, if at all). You could try to play with StringBuilder and only write to console once, but in my experience it is rarely an improvement when the method is only executed once.

But maybe you can do some other things to squeeze just a little bit more out of your method.

First of all, is the IsNullOrEmpty really necessary? It's a safety mechanism and in real life we would probably want to have it. But this is a coding exercise and we are all about performance right now.

Another thing you might want to consider is that strings are expensive. As it is, you are currently working with all your numbers as strings. Split creates a bunch of new strings and every time we compare values we do a string comparison. It might be worth to convert your values to int or char instead.

  HINT: If you try to convert to int values, it can be done by using char ASCII values. You know that the values will always be in the range [1-9]. The ASCII value for '1' is 49, '2' is 50, etc. So if you do value[0] - 48, you can convert you strings to ints with very little overhead.

When you want to optimize something it is always a good idea to measure and profile it and see just where the time is spent. Sometimes you can get big improvements with very few changes.. But you can also make things worse with very few changes.

After the changes mentioned in this post (except the string to int conversion) is applied, the code will look something like this:

using (StreamReader reader = File.OpenText(args[0]))
{
    while (!reader.EndOfStream)
    {
        var linevalue = reader.ReadLine();
        var numbers = linevalue.Split(' ');

        var values = new Dictionary<string, int>();
        string minValue = null;
        foreach (var number in numbers)
        {
            if (values.ContainsKey(number))
                values[number]++;
            else
                values.Add(number, 1);
        }

        foreach (var value in values)
        {
            if (value.Value == 1)
            {
                if (minValue == null || String.Compare(value.Key, minValue, StringComparison.InvariantCulture) == -1)
                    minValue = value.Key;
            }
        }

        if (minValue != null)
        {
            var playerNumber = Array.IndexOf(numbers, minValue);
            Console.WriteLine(playerNumber + 1);
        }
        else
        {
            Console.WriteLine("0");
        }
    }
}

As you can see, you have 2 loops within the while now. It might be possible to merge them into one by doing something clever.

I tried the code on CodeEval and got a 181ms execution time. That is a 74 ms improvement. To motivate you a bit, I know it can be done (at least a little) faster. ;)


Extract three letter pattern from a given list The code takes a list of names and extracts the three letter pattern from the names. Then return the list of names as a value in the dictionary with key as a pattern.  The list name has a fixed naming pattern like three letter Spp in the example. It can extent like App, Bpp, Cpp etc..

How can I improve this code?

import sys
import re

def uniquelist(scaffold_names_list):
    unique_names = []
    for name in scaffold_names_list:
        pattern_name = re.search(r"[A-Z]{1}[a-z]{2}", name)
        unique_names.append(pattern_name.group())
    unique_names = list(set(unique_names))
    return unique_names

def uniquepattern(scaffold_names_list):
    unique_names = uniquelist(scaffold_names_list)
    dct = {}

    for singlepattern in unique_names:
        dct['%s' % singlepattern] = []

    for singelelist in scaffold_names_list:
            number = re.search(r"[A-Z]{1}[a-z]{2}", singelelist)
            number = number.group()

            for singlepattern in unique_names:
                if number == singlepattern:
                    dct[singlepattern].append(singelelist)

    return dct

scaffold_names_list = ['Spp1Aa1', 'Spp1Aa1', 'Spp2Aa1', 'Spp3Aa1', 'Spp4Aa1', 'Spp5Aa1']
patterns = uniquepattern(scaffold_names_list)
print(patterns)

{'Spp': ['Spp1Aa1', 'Spp1Aa1', 'Spp2Aa1', 'Spp3Aa1', 'Spp4Aa1', 'Spp5Aa1']}

Naming

I have two problems with your naming:

First, you don't use underscores to separate words. Instead of uniquepattern, use unique_pattern.

Second, your names don't actually tell me anything! Functions, particularly non-method functions, should include a verb unless the verb is implicitly get or is. And implicit is needs to be used with some caution.

So rather than unique_pattern, the name should be some phrase reflective of what your function does. Since you mention "scaffold names", perhaps that function should be group_scaffold_names_by_unique_pattern?

Or maybe the unique pattern has another name? Like prefix? (See my question in the comments.) So perhaps it should be group_scaffold_names_by_prefix?

Is that long? Yes. Does it says what happens? Also, yes. Clarity for the win!

Redundancy. Repetition. Duplication. Multiple Copies.

In coding, if you find yourself typing something for the second time, STOP! Whatever this is needs to be stored once and referenced from different places. Write a function. Store text in a variable. Create a class. Do whatever it takes, but DON'T REPEAT YOURSELF. (This is called the "DRY" principle.)

This code is repeated:

    pattern_name = re.search(r"[A-Z]{1}[a-z]{2}", name)

What does it do? Well, it appears to be used to extract the first matching pattern as the "key" for each name in the list.

So let's write a function for this:

def extract_key(name):
    """ Extract unique pattern from a scaffold name.
        Apparently, patterns are just the first three characters,
        so don't use regexes, just grab the substring.
    """
    return name[:3]

Use the standard library

You have a separate function that pulls out the keys (unique patterns) from the names, and returns a uniquified list of them, which you apparently use only to initialize the keys of a dictionary.

Instead of doing that, just use collections.defaultdict to create a dictionary that starts with empty lists:

import collections

groups = collections.defaultdict(list)

With that code, you can be sure that groups[key] is a list (unless you explicitly override it with some non-list value). So let's write your function again:

import collections
from typing import Dictionary, Iterable, List

def group_scaffold_names_by_prefix(names: Iterable[str]) -> Dictionary[str, List[str]]:
    """ Given a list of scaffold names, return a dictionary that
        groups them together by their prefix.
    """
    groups = collections.defaultdict(list)

    for name in names:
        groups[extract_key(name)].append(name)

    return groups


Stochastic gradient descent squared loss I have implemented stochastic gradient descent in matlab and I would like to compare my results with another source but the error I am getting is higher (I am using squared error). I am worried I am misunderstanding the algorithm or have a bug. I have done trial and error parameter tuning, and am quite confident I have appropriate value for B, and know that I am working with the same data as my comparison. Please let me know what can be improved and if there is a mistake.

    % [w] = learn_linear(X,Y,B)
    %
    % Implement the online gradient descent algorithm with a linear predictor
    % and minimizes over squared loss.
    % Inputs:
    %     X,Y - The training set, where example(i) = X(i,:) with label Y(i)
    %     B - Radius of hypothesis class.
    % Output:
    %     w - predictor (as a row vector) from the hypothesis class (norm(w) <= %B)

    function [w] = learn_linear_sq_error(X, Y, B)
        [r c] = size(X);
        w = zeros(1, c);
        sum_w = zeros(1, c);
        % number of iterations
        T = 1000;

        % Run T iterations of online gradient descent:
        for t = 1:T,
            % Calculate step size for the current iteration.
            eta_t = 1 / sqrt(t);

            % Choose a random sample, and calculate its gradient.
            i_t = round(rand(1) * (r - 1)) + 1;
            g_t = calc_g_t(X(i_t, :), Y(i_t), w);

            % Apply the update rule/projection using the chosen sample, by %finding
            % the w that minimizes '|w - (w_t - eta_t * g_t)|' while          %maintaining norm(w) <= B.
            pw = w - eta_t * g_t;
            norm_pw = norm(pw);
            if norm_pw <= B
                w = pw;
            else
                w = B * pw / norm_pw;
            end

        % accumulate the sum in preparation for calculating the final average.
            sum_w = sum_w + w;

        end

        % Return the average of all intermediate w's.
        w = sum_w / T;
    end

    %
    % Calculate the sub gradient, with respect to squared loss, for a given sample
    % and intermediate predictor.
    % Inputs:
    %     x,y - A sample x (given as a row vector) and a tag y in R.
    %     w - our current predictor.
    % Output:
    %     g_t - the gradient (as a row vector) for the given values of x, y, w.

    function g_t = calc_g_t(x, y, w)

        g_t = 2 * (w*x' - y) * x;

    end

You probably do not need help with this question anymore (looks like it's been a year), but I thought I'd point something out in case someone else finds it useful. I think your squared loss expression should be \$(w'*x - y)^2\$ and the derivative of that with respect to \$x\$ is: \$2*(w'*x-y)*w\$. What you have is the outer product which results in a matrix minus a scalar. So I noticed two errors:

You need an inner product instead of an outer product.
You applied the chain rule wrong when you took the derivative w.r.t x.


Find contiguous integers with a given sum Introduction

This question was asked in a technical interview, I am looking for some feedback on my solution.

Given a list of integers and a number K, return which contiguous
elements of the list sum to K.  For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it
should return [2, 3, 4].

The Ask

My solution works with my test cases, but I would like feedback on how others would approach the problem and where my code could be altered to improve efficiency and runtime.  Currently, I have a nested for loop and I believe my solution is O(n2).

Solution

def contigSum(nums, k):

    for i, num in enumerate(nums):
        accum = 0
        result = []
        # print(f'Current index = {i}')
        # print(f'Starting value = {num}')

        for val in nums[i:len(nums)]:
            # print(f'accum = {accum}')
            result.append(val)
            # print(f'accum = {accum} + {val}')
            accum += val

            if accum == k:
                print(f'{result} = {k}')
                return 0
            # else:
                # print(f'accum = {accum}')

    print('No match found')
    return 1

Test Cases

nums0 = []
k0 = None
contigSum(nums0, k0)

nums6 = [1, 2, 3]
k6 = 99
contigSum(nums6, k6)

nums1 = [1, 2, 3, 4, 5]
k1 = 9
contigSum(nums1, k1)

nums2 = [-1, -2, -3]
k2 = -6
contigSum(nums2, k2)

nums4 = [5, 2, 6, 11, 284, -25, -2, 11]
k4 = 9
contigSum(nums4, k4)

nums5 = [10, 9, 7, 6, 5, 4, 3, 2 ,1]
k5 = 20
contigSum(nums5, k5)

Unused code
 for i, num in enumerate(nums):, the i variable is used in your commented code, but commented code shouldn't exist, so i shouldn't exist either.
To come back on the commented code, I hope you didn't submit your solution with these comments as this is a (in my opinion) very bad practice. What does commented code mean after all? These comments could all be replaced by any debugging tool.
Running time
I believe your solution is actually running on \$O(n*\log(n))\$  time as the nested loop doesn't restart at index 1 every time it runs (which is a good thing). Seems like this is wrong.
Code structure
Usually, in an interview question code structure is pretty important. Right now you have one method that does everything. You should at least have a method that returns your result and one that prints it. Something like :
def main():
    nums = ...
    k = ...
    print(contigSum(nums, k))

def contigSum(nums, k):
    ...

and contigSum should return the result, not print it.


Ranking players in a league by sorting the contents of an OrderedDict I'm new to python.  I'm having second thoughts on my approach to this problem:

The LeagueTable class tracks the score of each player in a league. After each game, the player records their score with the record_result function.
The player's rank in the league is calculated using the following
logic:

The player with the highest score is ranked first (rank 1). The player with the lowest score is ranked last.
If two players are tied on score, then the player who has played the fewest games is ranked higher.
If two players are tied on score and number of games played, then the player who was first in the list of players is ranked higher.

Implement the player_rank function that returns the player at the
given rank.
example:
table = LeagueTable(['Mike', 'Chris', 'Arnold'])
table.record_result('Mike', 2)
table.record_result('Mike', 3)
table.record_result('Arnold', 5)
table.record_result('Chris', 5)
print(table.player_rank(1))

All players have the same score. However, Arnold and Chris have played fewer games than Mike, and as Chris is before Arnold in the list of players, he is ranked first. Therefore, the code above should display "Chris".

I have a solution, but I want to know if there is a more optimised approach to this.
from collections import Counter
from collections import OrderedDict

class LeagueTable:
    def __init__(self, players):
        self.standings = OrderedDict([(player, Counter()) for player in players])
    def record_result(self, player, score):
        self.standings[player]['games_played'] += 1
        self.standings[player]['score'] += int(score)# print(self.standings)# print("")
    def player_rank(self, rank): #res = OrderedDict()
        x=self.standings
        d=self.standings
        def swap_list(xl,co):
            xl[co],xl[co+3]=xl[co+3],xl[co]
            xl[co+1],xl[co+4]=xl[co+4],xl[co+1]
            xl[co+2],xl[co+5]=xl[co+5],xl[co+2]
            return(xl,co)

        player_list=[]
        lc=len(x)
        lc1=lc
        lc=lc*3
        for p,c in x.items():
            player_list.append(p)
            player_list.append(c["score"])
            player_list.append(c["games_played"])
        for j in range(lc1):
            for i in range(0,lc-3,3):
                # print(i+4)
                if (player_list[i+1] < player_list[i+4]):
                    swap_list(player_list,i)
                elif (player_list[i+1]==player_list[i+4]):
                    if(player_list[i+2]>player_list[i+5]):
                        swap_list(player_list,i)
                    elif(player_list[i+2]==player_list[i+5]):
                        pass

        return(player_list[(rank-1)*3])

table = LeagueTable(['Mike', 'Chris', 'Arnold'])
table.record_result('Mike', 2)
table.record_result('Mike', 3)
table.record_result('Arnold', 5)
table.record_result('Chris', 5)
rk=int(input("enter rank \n"))
print(table.player_rank(rk))

First of all, your entire def player_rank: is way over-engineered.. and with the correct standard modules this practically becomes a one-liner

Review

Use better variable names (naming is hard), but to me names like c, x makes no sense. I don't know what they do at all.
Use built in methods, like sort() this greatly reduces complexity.
With the full powers of sorted() you can sort multiple items at once.
With a - before the item we are sorting you can reverse the order, that makes it easier to sort multiple items on different orders.

With my changes I get the following code.

from collections import OrderedDict, Counter

class LeagueTable:
    def __init__(self, players):
        self.standings = OrderedDict([(player, Counter()) for player in players])

    def record_result(self, player, score):
        self.standings[player]['games_played'] += 1
        self.standings[player]['score'] += score

    def player_rank(self, rank):
        return sorted(self.standings, key=lambda p: (-self.standings[p]['score'],
                                                     self.standings[p]['games_played']))[rank-1]


MySQL statements to update overlapping database entries and insert new data into various tables As I've mentioned in previous questions, I am writing MySQL statements to update overlapping database entries and insert new data into various tables. My database design looks something like this, where there's one parent table (hash is the primary key and id is indexed):

+---------------+
| hashes        |
+---------------+
| hash  | id    |
+---------------+
| hash1 | id1   |
| hash2 | id1   |
| hash3 | id1   |
| hash4 | id2   |
+---------------+

And many child tables (id is indexed, there are no primary or unique keys):

+-------------------------+
| other_table             |
+-------------------------+
| id  | group_id  | value |
+-------------------------+
| id1 | groupid1  | val1  |
| id1 | groupid1  | val2  |
| id2 | groupid2  | val3  |
| id2 | groupid3  | val4  |
+-------------------------+

There are foreign key constraints on the child table id columns, so that if any ids in the hashes table are updated, all child tables update with the new information. The ids change when any inserted hashes are overlapped somewhere in the hashes table.

To achieve all this, I wrote the following statement:

START TRANSACTION;

    /* Generated with PHP */
    SET @id = '610de097-26d0-41b2-839b-1bd8c0d05dea';
    SET @group_id = '54c41b95-5897-4984-961c-cc8fc97fc586';

    /* Insert new data */
    INSERT INTO hashes
        (id, hash)
    VALUES
        (@id, 'hash1'), (@id, 'hash2')
    ON DUPLICATE KEY UPDATE
        repeat_count = repeat_count + 1;

    INSERT IGNORE INTO categories
        (id, group_id, value)
    VALUES
        (@id, @group_id, 'some value');

COMMIT;

And a collection of updates to run after everything is inserted:

/* Update all parent table ids for any overlapping hashes */
UPDATE hashes
SET id=@id
WHERE id IN (
    SELECT id
    FROM (SELECT id, hash FROM hashes ORDER BY id) as temp
    WHERE hash IN ('hash1', 'hash2')
    ORDER BY id ASC
);

This works, and with around 950 entries to insert, it takes around 25 seconds to run. The slowest part, by far, is the many update statements since it needs to search over the entire hash table and update rows accordingly.

Consequently, if I want to see any speed improvements, I need to modify those update statements. Any ideas?

I was going in circles looking at your query and then I thought
... it looks like you're just updating the one table form the same table

Why can't you just use

UPDATE hashes
SET id=@id
    WHERE hash IN ('hash1', 'hash2');

Or is this a typo?

UPDATE hashes


C# API Wrapper with Static Function Calls I'm creating a wrapper library for an API, and I hit a block on how to redesign it. The entire library is static, and I'd like to change it to make it more testable.

The library's goal is to make rest api requests and return C# objects. There is a networking class, which makes the requests. And there is a class for each endpoint which abstracts the parameters for the request and supplies the relative url.

Networking class: build url, create headers, and return results from request

public class APIClient{

private static string url = null;
private static string apiKey = null;

public static void Initialize(string key,string url)
    {
        APIClient.url = url;
        APIClient.apiKey = key;
    }

public static async Task<T> GetAsync<T>(string path, Dictionary<string, string> parameters)
    {
        var client = CreateHttpClientFromApiCredentials();

        //build url with parameters from the dictionary
        var builder = new UriBuilder("", path);
        builder.Port = -1;

        if (parameters != null)
        {
            var query = HttpUtility.ParseQueryString("");
            foreach (var key in parameters.Keys)
                query[key] = parameters[key];

            builder.Query = query.ToString();
        }

        var response = await client.GetAsync(builder.ToString());

        if (!response.IsSuccessStatusCode)
            throw new HttpException((int)response.StatusCode, response.ReasonPhrase);

        //evaluate API specific data
        return await EvaluateResponseContent<T>(response);
    }
}

Sample endpoint class: provide relative url and arguments to networking class

public class APIObject
{
    public static async Task<List<APIObject>> Get()
    {
        return await APIClient.GetAsync<List<APIObject>>("objectendpoint",null);
    }

}

This design allows for very simple use, with calls like APIObject.Get().

With that said, I have a redesign in mind that will maintain the simplicity of the static functions while also allowing for easy testing. The APIClient will be refactored to be an object, and each of the API object classes will be a nested class inside the APIClient.

A brief example (untested):

public class APIClient
{
    public ApiObjectSender ApiObjectEndpoint;

    public APIClient() {
        ApiObjectEndpoint = new ApiObjectSender(this);
    }

    public class ApiObjectSender
    {
        APIClient apiClient;

        public ApiObjectSender(APIClient cl)
        {
            apiClient = cl;
        }

        public List<APIObject> Get()
        {
            return apiClient.Get("apiobjectendpoint");
        }
    }
}

This allows for similar function calls, like clientVar.ApiObjectEndpoint.Get(). However, I can't help but feel like this approach is... janky.

public static void Initialize(string key,string url)
    {
        APIClient.url = url;
        APIClient.apiKey = key;
    }

This is a dead give away that this class shouldn't be a bunch of static methods. I have to call this initialize method before using it or it'll blow up with null reference exceptions.

Worse, let's say I parallelize the main process and have multiple processes using this class. What happens when one of processes changes the uri? That's right, now all the processes are hitting that other uri. You'll get results, they'll just be the wrong one.

Thankfully, it's a simple fix. Just turn your Initialize method into a constructor and remove all instances of the static keyword.

public class APIClient
{
    private readonly string url;
    private readonly string apiKey;

    public APIClient(string key,string url)
    {
        this.url = url;
        this.apiKey = key;
    }


Takes a list and return a dict of distinct values pointing to a list of index locations of each value I came up with a way to get a dict of distinct elements in a list pointing to the location of each element; it works, but I feel pretty awful about this code, it's very ugly. Is there a more natural/pythonic way to do this?
from itertools import groupby
sample_data = [1,2,3,3,1,0,5]
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in itertools.groupby(list(enumerate(dta)), lambda x:x[1])}
print(give_groups(sample_data))

{1: [4], 2: [1], 3: [2, 3], 0: [5], 5: [6]}

The performance is also bad.
Created this alternate that does work, but is kinda slow:
def alt_grouping(dta):
    retdict = defaultdict(list)
    for position, item in enumerate(dta):
        retdict[item].append(position)
    return retdict

The first try :
from itertools import groupby
sample_data = [1,2,3,3,1,0,5]
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in itertools.groupby(list(enumerate(dta)), lambda x:x[1])}
print(give_groups(sample_data))

Have to be corrected to:
from itertools import groupby # --> you don't have to call itertools.groupby just groupby
sample_data = [1,2,3,3,1,0,5]
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in groupby(list(enumerate(dta)), lambda x:x[1])}
print(give_groups(sample_data))

But seems to be replacing items and not appending them, don't see why.

In the alt_grouping function, defaultdict doesn't exists:
def alt_grouping(dta):
    retdict = defaultdict(list) # don't know what is defaultdict
    for position, item in enumerate(dta):
        retdict[item].append(position)
    return retdict

Then I found a solution that works, it's based on your function alt_grouping:
sample_data = [1,2,3,3,1,0,5]

retdict = {}
for position, item in enumerate(sample_data):
        if item in retdict.keys():
            retdict[item].append(position)
        else:
            retdict[item] = [position]

print(retdict)

I take some execution & times testing in the first try and my alternative with a bigger sample a list of two range(100).
Sample Data:
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76,
77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

First Function:
{0: [100], 1: [101], 2: [102], 3: [103], 4: [104], 5: [105], 6: [106], 7: [107], 8: [108], 9: [109], 10: [110], 11: [111], 12: [112], 13: [113], 14: [114], 15: [115], 16: [116], 17: [117], 18: [118], 19: [119], 20: [120], 21: [121], 22: [122], 23: [123], 24: [124], 25: [125], 26: [126], 27: [127], 28: [128], 29: [129], 30: [130], 31: [131], 32: [132], 33: [133], 34: [134], 35: [135], 36: [136], 37: [137], 38: [138], 39: [139], 40: [140], 41: [141], 42: [142], 43: [143], 44: [144], 45: [145], 46: [146], 47: [147], 48: [148], 49: [149], 50: [150], 51: [151], 52: [152], 53: [153], 54: [154], 55: [155], 56: [156], 57: [157], 58: [158], 59: [159], 60: [160], 61: [161], 62: [162], 63: [163], 64: [164], 65: [165], 66: [166], 67: [167], 68: [168], 69: [169], 70: [170], 71: [171], 72: [172], 73: [173], 74: [174], 75: [175], 76: [176], 77: [177], 78: [178], 79: [179], 80: [180], 81: [181], 82: [182], 83: [183], 84: [184], 85: [185], 86: [186], 87: [187], 88: [188], 89: [189], 90: [190], 91: [191], 92: [192], 93: [193], 94: [194], 95: [195], 96: [196], 97: [197], 98: [198], 99: [199]}
--- 0.001995563507080078 seconds ---
My Function:
{0: [0, 100], 1: [1, 101], 2: [2, 102], 3: [3, 103], 4: [4, 104], 5: [5, 105], 6: [6, 106], 7: [7, 107], 8: [8, 108], 9: [9, 109], 10: [10, 110], 11: [11, 111], 12: [12, 112], 13: [13, 113], 14: [14, 114], 15: [15, 115], 16: [16,
116], 17: [17, 117], 18: [18, 118], 19: [19, 119], 20: [20, 120], 21: [21, 121], 22: [22, 122], 23: [23, 123], 24: [24, 124], 25: [25, 125], 26: [26, 126], 27: [27, 127], 28: [28, 128], 29: [29, 129], 30: [30, 130], 31: [31, 131], 32: [32, 132], 33: [33, 133], 34: [34, 134], 35: [35, 135], 36: [36, 136], 37: [37, 137], 38: [38, 138], 39: [39, 139], 40: [40, 140], 41: [41, 141], 42: [42, 142], 43: [43, 143], 44: [44, 144], 45: [45, 145], 46: [46, 146], 47:
[47, 147], 48: [48, 148], 49: [49, 149], 50: [50, 150], 51: [51, 151], 52: [52, 152], 53: [53, 153], 54: [54, 154], 55: [55, 155], 56: [56, 156], 57: [57, 157], 58: [58, 158], 59: [59, 159], 60: [60, 160], 61: [61, 161], 62: [62,
162], 63: [63, 163], 64: [64, 164], 65: [65, 165], 66: [66, 166], 67: [67, 167], 68: [68, 168], 69: [69, 169], 70: [70, 170], 71: [71, 171], 72: [72, 172], 73: [73, 173], 74: [74, 174], 75: [75, 175], 76: [76, 176], 77: [77, 177], 78: [78, 178], 79: [79, 179], 80: [80, 180], 81: [81, 181], 82: [82, 182], 83: [83, 183], 84: [84, 184], 85: [85, 185], 86: [86, 186], 87: [87, 187], 88: [88, 188], 89: [89, 189], 90: [90, 190], 91: [91, 191], 92: [92, 192], 93:
[93, 193], 94: [94, 194], 95: [95, 195], 96: [96, 196], 97: [97, 197], 98: [98, 198], 99: [99, 199]}
--- 0.0009963512420654297 seconds ---

Seems to be pretty similar then I try with list(range(10000)):
First Function:
--- 0.015984535217285156 seconds ---
My Function:
--- 0.005953311920166016 seconds ---

Here we see a difference.
There is the code for tests - EDITED :
import time
sample_data = list(range(1000000)) + list (range(1000000))
# print ("Sample Data:\n",sample_data, "\n")

print("First Function:")
start_time = time.time()

from itertools import groupby
give_groups = lambda dta: {item: list(map(lambda z: z[0], list(item_group))) for item, item_group in groupby(list(enumerate(dta)), lambda x:x[1])}
# print(give_groups(sample_data))
give_groups(sample_data)

print("--- %s seconds ---" % (time.time() - start_time))

print("My Function:")
start_time = time.time()
retdict = {}
for position, item in enumerate(sample_data):
        if item in retdict.keys():
            retdict[item].append(position)
        else:
            retdict[item] = [position]

print("--- %s seconds ---" % (time.time() - start_time))

print("Other Function:")

from collections import defaultdict

start_time = time.time()
def dict_with_indices(dta):
    """ Returns a dictionary with a list of indices for each item in dta

    Args:
        dta (list): list of data to be indexed

    Returns:
        dict: dict with list of indices as values

    Examples:
        >>> dict_with_indices([1,2,3,3,1,0,5]]
        {1: [0, 4], 2: [1], 3: [2, 3], 0: [5], 5: [6]}
    """
    result = defaultdict(list)
    for idx, val in enumerate(dta):
        result[val].append(idx)
    return result

dict_with_indices(sample_data)

print("--- %s seconds ---" % (time.time() - start_time))

Times for this new tests:
First Function:
--- 1.9537413120269775 seconds ---
My Function:
--- 0.7061352729797363 seconds ---
Other Function:
--- 0.6053769588470459 seconds ---

New Solution seems to be the better one, thanks to @agtoever :
from collections import defaultdict

    def dict_with_indices(dta):
        """ Returns a dictionary with a list of indices for each item in dta

        Args:
            dta (list): list of data to be indexed

        Returns:
            dict: dict with list of indices as values

        Examples:
            >>> dict_with_indices([1,2,3,3,1,0,5]]
            {1: [0, 4], 2: [1], 3: [2, 3], 0: [5], 5: [6]}
        """
        result = defaultdict(list)
        for idx, val in enumerate(dta):
            result[val].append(idx)
        return result

    dict_with_indices(sample_data)


Haskell - Different log methods I'm pretty new to Haskell and was playing around with some number manipulation in different bases when I had to write an integer logarithm function for my task.

I don't mean discrete/modular logs, but simply greatest x s/t b^x <= n

I developed a few versions and can't decide which I like best.  Was hoping to hear what some of you think, or if you have other alternatives to suggest

All have signature: intlog :: (Integral a) => a -> a -> a

intlog :: (Integral a) => a -> a -> a
intlog n b
    | n < b = 0
    | otherwise = succ (intlog (div n b) b)

intlog' :: (Integral a) => a -> a -> a
intlog' n b = maximum [i | i<-[0..n], b^i <= n]

logg = log . fromIntegral
intlog'' :: (Integral a) => a -> a -> a
intlog'' intlog n b = floor $ logg n / logg b

The 'best' one relies on haskell's standard natural log function which I was hoping to avoid (as an exercise) and somewhat messy type conversion.  Of the remaining two, one is probably fastest but seems nearly procedural in nature.  The other feels very functional and 'haskelly' (looking for word analogous to pythonic, meaning in haskells best style) but i cant see it being too efficient unless there is really really good optimization under the hood.

Would love to hear what you guys think.

BTW - i know that for the second one, intlog' i could find a better upperbound than n but im looking for feedback and/or different way to code it.  not incremental improvement like that

The problem with your intLog' function is definitely that it goes through all n numbers in the list. As a result of this it takes ages for large n (for n = 2^130 it ran until I killed it, while your other solutions all returned the result instantly).

The reason that it has to go through all the numbers is of course that using a condition in a list comprehension is like using filter and does not make use of the fact that once the condition is false for the first time, it will always be false thereafter. What you should use instead is takeWhile which takes elements from the list while the condition is true and then stops the first time the condition is false. This way the code would look like this:

intlog n b = maximum $ takeWhile (\i -> b^i <= n) [0..]

Since it will no longer go through the list to its end, we also no longer need to pick an upper bound and can just leave it off. This function will instantly return a result like the other solutions.

Of course, except for learning purposes, the best solution is still to just use the built-in functionality with conversion as there is no point reinventing the wheel. Regarding that you should note that you can use the prelude function logBase instead of dividing the logs of n and b.


Unit Testing Search and Sort method(s) I just decided to write a unit test, and see how to do it.  This is my unit test:

[TestMethod]
public void TestSearchSort()
{
    System.IO.File.WriteAllText(@"C:\Users\Hosch250\Documents\Visual Studio 2013\Projects\ConsoleApplication14\ConsoleApplication14\TestFile.cs", string.Empty);

    var TestInstance = new Program();
    var titles = new List<string>();
    string[] query = { "main", "menu" };

    Program.Search(ref titles, ref query);

    var expectedTitles = new List<string>();
    string[] expectedTitleStrings = { "The Main Menu", "OneNote", "The Text Menu",
                                    "The Text Block Menu", "The Table Menu", "The Table Cells Menu",
                                    "The Draw Menu", "The Drawn Items Menu", "The Picture Menu",
                                    "The File Menu", "Draw", "Windows Phone Notebooks",
                                    "Windows Phone Sections", "Windows Phone Pages" };
    expectedTitles.AddRange(expectedTitleStrings);

    using (var file = new System.IO.StreamWriter(@"C:\Users\Hosch250\Documents\Visual Studio 2013\Projects\ConsoleApplication14\ConsoleApplication14\TestFile.cs", true))
    {
        file.WriteLine("Expected Count: " + expectedTitles.Count);
        file.WriteLine("Actual Count: " + titles.Count);
    }

    Assert.AreEqual(expectedTitles.Count, titles.Count);
    for (var i = 0; i < titles.Count; i++)
    {
        using (var file = new System.IO.StreamWriter(@"C:\Users\Hosch250\Documents\Visual Studio 2013\Projects\ConsoleApplication14\ConsoleApplication14\TestFile.cs", true))
        {
            file.WriteLine("Expected Title: " + expectedTitles[i]);
            file.WriteLine("Actual Title: " + titles[i]);
        }
        Assert.AreEqual(expectedTitles[i], titles[i]);
    }
}

This is the method it tests:

public static void Search(ref List<string> resultTitles, ref string[] query)
{
    List<int> weight = new List<int>();

    int position = -1;

    foreach (string[] array in SearchKeys.Keys)
    {
        position++;
        int length = array.Length;
        int middle = length / 2;
        char firstCharMidArray = array[middle][0];

        foreach (string s in query)
        {
            int min = array[middle][0] < s[0] ? middle : 0;
            int max = array[middle][0] <= s[0] ? array.Length : middle + 1;

            for (int i = min; i < max; i++)
            {
                weight.Add(0);

                if (array[i] == s)
                {
                    if (weight[position] == 0)
                    {
                        resultTitles.Add(array[0]);
                    }
                    weight[position]++;

                }
            }
        }
    }

    StableSort(ref resultTitles, ref weight);
}

I write to the file in the test method so I can see where/how it failed.  How did I do?  Should I be doing anything different?  Should I have more tests?  I most certainly cannot run every possible combination of search terms.

I write to the file in the test method so I can see where/how it failed.

Don't do that. This:

using (var file = new System.IO.StreamWriter(@"C:\Users\Hosch250\Documents\Visual Studio 2013\Projects\ConsoleApplication14\ConsoleApplication14\TestFile.cs", true))
{
    file.WriteLine("Expected Count: " + expectedTitles.Count);
    file.WriteLine("Actual Count: " + titles.Count);
}

Has just become a possible reason for your test to fail that has nothing to do with your test. For example, if this was part of a test suite in a repo on GitHub, I couldn't run this test successfully. It's important that tests be portable and deal only with the code under test.

If you really want to know exactly which item caused your test to fail, use the overload that takes a message string.


Reversing a domain name string in Java Given a dot separated domain name, reverse the domain elements.

Example:

codereview.stackexchange.com -> com.stackexchange.codereview
google.com -> com.google

I just wanted some suggestions to improve my code. Or if you can suggest a better way, please do so.

package practice;

import java.util.Scanner;
import java.util.StringTokenizer;

public class ReverseDomainName
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the domain name to be reversed");
        String domain = sc.nextLine();
        sc.close();
        ReverseDomainName obj = new ReverseDomainName();
        String reversedDomainName = obj.reverseDomainNameString(domain);
        System.out.println("The reversed Domain Name = "+reversedDomainName);
    }

    public String reverseDomainNameString(String s)
    {
        String reverse1 = "",word ="" ;
        int i;

        StringTokenizer st = new StringTokenizer(s,".");
        int len = st.countTokens();

        /*
         * The check is performed so that instead of com.stackexchange.codereview.
         * we can get the proper com.stackexhange.codereview  so no
         * extra dot
         */

        word  = st.nextToken();
        reverse1 = word+reverse1;

        for(i=1;i<len;i++)
        {
            word = st.nextToken();
            reverse1 = word +"."+reverse1;

        }

        return reverse1;
    }

}

StringTokenizer is an OK solution, but I think that String.split() would lead to a less verbose solution.

Here is a Java 8 solution that uses split():

public static String reverseDomainNameString(String s) {
    List<String> components = Arrays.asList(s.split("\\."));
    Collections.reverse(components);
    return String.join(".", components.toArray(new String[0]));
}

Without Java 8's String.join(), though, the solution would be more tedious.  Note that it might be a good idea to ensure that the string is non-empty, otherwise components[0] (or st.nextToken() in your original solution) would crash.

public static String reverse(String s) {
    if (s == null || s.isEmpty()) return s;
    String[] components = s.split("\\.");
    StringBuilder result = new StringBuilder(s.length());
    for (int i = components.length - 1; i > 0; i--) {
        result.append(components[i]).append(".");
    }
    return result.append(components[0]).toString();
}


Read and convert binary files to ASCII text This is my code which receives a file to read and converts binary values to ASCII text.

The code works fine, so I am looking for a review on what I have written, and suggestions on how I could do it better, perhaps without the use of a StringBuffer.

import java.io.File;
import java.util.Scanner;

/**
 *
 * @author Tumpi
 */
public class DN6 {

public static void main(String[] args)
        throws Exception {

    File file = new File("sporocilo.txt");

    Scanner sc = new Scanner(file);
    String lastString = "";

    while (sc.hasNextLine()) {
        String line = sc.nextLine();
        lastString = lastString + line;
    }
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < lastString.length(); i += 8) {
            result.append((char) Integer.parseInt(lastString.substring(i, i + 8), 2));
        }
        System.out.println(result);
    }

}

Aside from turning StringBuffer into StringBuilder, there are a few more things I'd like to note about your code.

Compound assignment operator

This line:

 lastString = lastString + line;

Can be rewritten as this one:

 lastString += line;

It's short and it complies with what many people would expect: a concatenation. By explicitly mentioning the original variable again, many people might think it is a different variable before looking at it more closely.

Additionally, you might also want to add a StringBuilder to the reading of the file. Even if the inputfile isn't that big, it would still be consistent.

Magic values

Consider this code:

for (int i = 0; i < lastString.length(); i += 8) {
     result.append((char) Integer.parseInt(lastString.substring(i, i + 8), 2));
}

Can someone other than the authro tell with certainty what the value 8 is? An educated guess would lead to the bit representation of 2 bytes, but we shouldn't have to guess that. Get rid of this so called "magic value" by adding a variable which clears it up:

int amountOfBits = 8;
for (int i = 0; i < lastString.length(); i += amountOfBits ) {
     result.append((char) Integer.parseInt(lastString.substring(i, i + amountOfBits ), 2));
}

Exception handling

You're completely bypassing exception handling. I'm assuming this is just so this contrived sample wouldn't get cluttered with code, but just in case it isn't:

throws Exception

is always a bad idea in an actual program. You should catch the exact exception and handle it appropriately.


Difference in days between two dates I've been trying to write a really basic function to determine the difference (in days) between two dates. I am very new to C++ so as you can imagine I am very happy with my work.
This function is part of a much larger code so I have missed off my includes, but the function does compile without warnings.

Just looking for some constructive criticism that a reasonable beginner can take on board.

I should add, this function takes two dates as strings in British format DD/MM/YYYY.

int dateDiffs(std::string date1, std::string date2){

    int startYear, endYear;
    int startMonth, endMonth;
    int startDay, endDay;

    int startInDays, endInDays;

    std::map<int,int> daysInMonth;

    daysInMonth[1]=31;
    daysInMonth[2]=28;
    daysInMonth[3]=31;
    daysInMonth[4]=30;
    daysInMonth[5]=31;
    daysInMonth[6]=30;
    daysInMonth[7]=31;
    daysInMonth[8]=31;
    daysInMonth[9]=30;
    daysInMonth[10]=31;
    daysInMonth[11]=30;
    daysInMonth[12]=31;

    startYear = atoi(date1.substr(6,4).c_str());
    startMonth = atoi(date1.substr(3,2).c_str());
    startDay = atoi(date1.substr(0,2).c_str());

    endYear = atoi(date2.substr(6,4).c_str());
    endMonth = atoi(date2.substr(3,2).c_str());
    endDay = atoi(date2.substr(0,2).c_str());

    startInDays = (startYear * 365) + (startMonth * daysInMonth[startMonth]) + startDay;
    endInDays = (endYear * 365) + (endMonth * daysInMonth[endMonth]) + endDay;

    return (endInDays - startInDays);
}

@Snowbody has addressed many important points.  I'll just talk about the std::map.

The function initializes daysInMonth each time, which is just unnecessary.  You should have it initialized only once elsewhere, and it should also be const since it's not to be modified within the code.

If you have C++11 (which you should), you can initialize the map with an initializer list:

const std::map<int, int> daysInMonth = { {1, 31},
                                         {2, 28},
                                         {3, 31},
                                         {4, 30},
                                         {5, 31},
                                         {6, 30},
                                         {7, 31},
                                         {8, 31},
                                         {9, 30},
                                         {10, 31},
                                         {11, 30},
                                         {12, 31} };

(it can be formatted in any way you'd like)

You should also use an unsigned type for dates since they cannot be negative.


Request rate limiter I'm looking for feedback on ways to improve the maintainability and readability of my code.  I'm especially interested in hearing about ways I could improve the code's adherence to good object oriented practices.  Thank you!

Purpose of the code:

Reject a client's requests if that client has already made 100 requests in the last second.  The client who sent a request is identified on the request with a clientID.

Usage:

let rateLimiter = new RateLimiter();

let request = { clientID: 1, time: 0 };

let isRequestAllowed = rateLimiter
  .addRequestAndCheckIsAllowed(request);

Implementation:

const MAX_REQUESTS_IN_TIME_FRAME = 100;
const REQUEST_MAX_AGE = 1000;

class RateLimiter {
  constructor () {
    this._clientRequests = {};
  }

  addRequestAndCheckIsAllowed (request) {
    this._storeRequest(request);

    return this._clientRequestCount(request.clientID) <=
      MAX_REQUESTS_IN_TIME_FRAME;
  }

  _storeRequest (request) {
    const clientID = request.clientID;

    this._clientRequests[clientID] =
      this._clientRequests[clientID] ||
      new RequestBuffer(REQUEST_MAX_AGE);

    this._clientRequests[clientID].store(request);
  }

  _clientRequestCount(clientID) {
    if (this._clientRequests[clientID] === undefined) {
      return 0;
    }

    return this._clientRequests[clientID].count();
  }
};

class RequestBuffer {
  constructor (requestMaxAge) {
    this._requestMaxAge = requestMaxAge;
    this._requests = [];
  }

  store (request) {
    this._requests.push(request);

    const maxTime = Date.now() - this._requestMaxAge;

    this._requests =
      this._requests.filter(request => request.time > maxTime);
  }

  count () {
    return this._requests.length;
  }
};

Object Oriented Javascript

Many people think that to write OO javascript you need to use the class syntax. This is not at all true. You can write very good OO javascript without ever using the class syntax, including inheritance, encapsulation (private and protected states), static properties, and polymorphism (JS is the polymorphic king)

Style and code

I can't help but feel there is a lot missing from your code.

Problems I see

It drops requests if they timeout but only when a new request is added by the same client. The object ignores all existing client requests if the client makes no more requests.
You have a const MAX_REQUESTS_IN_TIME_FRAME but the code keeps on adding requests irrespective of this value when addRequestAndCheckIsAllowed is called.
There is no easy way to know that the limit has been reached without creating and adding a new request. To me it seems like you may use the two objects to deduce this state, if so that would violate encapsulation rules, as that is for the object to do not external code.

Some points on you code.

Id is an abbreviation and as such is named with a lower case "d"  ie clientId not clientID
Using Array.filter to remove items from an array is easy, but it generates lots of unused arrays for GC to clean up. Splicing items is far more efficient.
It is good to break long lines into multiple lines to stop them going past the right of screen. However doing so for short lines just makes the code harder to read. You have done this in 3 places for lines that fit even the stack's snippets thin format. More thought on good names can help reduce line lengths.
addRequestAndCheckIsAllowed that is a mouth full, maybe addRequestValidate is a better option?

OO points

Underscore does not make a private variable, avoid its use as its just noise
The constants MAX_REQUESTS_IN_TIME_FRAME and REQUEST_MAX_AGE also are public, and just add to the global scope. Put them inside the objects that use them.
RequestBuffer is only used by RateLimiter, it should not be visible outside RateLimiter
RequestBuffer need only expose a way to store requests and a way to see if a request is valid. This can be done via a getter allowed and a setter store
RequestLimiter should only expose the function addRequestAndCheckIsAllowed all the rest should be protected as private functions and properties.
You create a client request ad hoc, should be an object created via a function. Better yet as it is strongly associated with the RequestLimiter you can add it as a static such as RequestLimiter.Request In the example I add it using define property to ensure it is protected

Encapsualtion and private state

An important part of OO code is that you can protect the object's state by limiting access. In many languages this is done by declaring private variables and methods. Javascript does have a way to define private objects properties but it is very new, and personally because it adds a prefix to the variable name I can not agree with its use. There is a better way.

If you use function syntax to define objects. You can protect state via closure. You can protect object properties using Object.freeze or use Object.defineProperty. You can add statics directly to the function or via Object.defineProperty to protect them.

Getters and Setters

Additionally to help protect an object's state, objects use functions to access properties. These are called getters and setters and allow the objects to ensure only valid states can be set, or read. It also allows you to easily define read or write only properties.

Rewrite

The rewrite uses function syntax to create the same objects as your code. It includes examples of a getter, a setter, a static and private properties and objects via closure. I renamed RequestBuffer to just Buffer as it is inferred by context what it holds and the name no longer lives in the global scope.

The code feels like its missing functionality, but I can only go by what you have supplied.

function RateLimiter() {
    const buffers = {}, MAX_IN_TIME_FRAME = 100, MAX_AGE = 1000;
    function Buffer(maxAge = MAX_AGE) {
        const requests = [];
        function update() {
            var i = requests.length;
            const maxTime = Date.now() - maxAge;
            while (i--) {
                if (requests[i].time >= maxTime) {  requests.splice(i, 1) }
            }
        }
        return {
            set store(request) {
                requests.push(request);
                update();
            },
            get allowed() { return requests.length <= MAX_IN_TIME_FRAME }
        };
    }
    function addClient(id) {
        if (buffers[id]) { return buffers[id] }
        return buffers[id] = Buffer();
    }
    return Object.freeze({   // freeze the interface to protect state
        addRequestValidate(request) {
            const buffer = addClient(request.clientId);
            buffer.store = request;
            return buffer.allowed;
        },
        canClientRequest(id) { return buffers[id] ? buffers[id].allowed : true }
    });
}
Object.defineProperty(RateLimiter, 'Request', { // Request constructor as a static of RateLimiter
    enumerable: false, configurable: false, writable: false,
    value: function(clientId) { return { clientId, time: Date.now() } }
});

Using function syntax to define object makes the new token optional.

const rateLimiter = new RateLimiter();
//const rateLimiter = RateLimiter();//  works the same

const request = RateLimiter.Request(1);
// or
// const request = new RateLimiter.Request(1);

const isRequestAllowed = rateLimiter.addRequestValidate(request);

The state of this

I personally believe that good OO JavaScript rarely uses the this token. You will notice that this is not used at all in the above code.

The token this can be so ubiquitous that it occurs multiple times on almost every line of code, it becomes noise, detracting from the overall readability. You used the token 'this' 15 times and your code contains 15 lines of expressions and statements.

More importantly this is JavaScript's achilles heel as it can be easily hijacked. Many people do this as standard practice via Function.call. This means that no matter how much effort you put into protecting an object's state you can never fully trust the state of this

Example using Function.call to change object's state

class ObjA1 {
    constructor() { this.a = "A" }
    log() { console.log(this.a) }
}
const a = new ObjA1();
a.log(); // State is correct

// Hijacking the state.
a.log.call({get a(){console.log("Hijacked and running external code"); return "Boo"; }});

What is even more worrying is if you have code running on a public page (ie you have 3rd party advertising scripts) this can be hijacked by malicious 3rd parties and used to gain access to secure content.

The class syntax encourages you to use the token this while function syntax is more conducive to defining a trusted named state.

function ObjA1() {
     const obj = {  // this is replaced by obj
         a : "A",
         log() { console.log(obj.a) }
     }
     return obj;
}


Finding unique/obsolete binary Debian packages I have a script I use to prune packages that have gone stale from my custom Debian repository (i.e. they no longer exists on any of the official repositories):

import apt_pkg
import gzip
import subprocess

CUSTOM_REPO = ("/home/tshepang/.custom_repo/dists/tshepang/main/"
               "binary-amd64/Packages.gz")
TEMPLATE = ("/var/lib/apt/lists/http.debian.net_debian_dists_{}_{}_"
            "binary-amd64_Packages")
CODENAMES = 'jessie sid experimental'.split()
ARCHIVE_AREAS = "main contrib non-free".split()

def main():
    custom_repo = apt_pkg.TagFile(gzip.open(CUSTOM_REPO))
    wheezy_packages = list()
    for codename in CODENAMES:
        for archive_area in ARCHIVE_AREAS:
            repo = TEMPLATE.format(codename, archive_area)
            repo = apt_pkg.TagFile(gzip.open(repo, "rb"))
            wheezy_packages.extend([pkg["Package"] for pkg in repo])
    for package in custom_repo:
        package_name = package["Package"]
        if package_name not in wheezy_packages:
            cmd = "apt-cache policy " + package_name
            subprocess.call(cmd.split())
            choice = raw_input("remove from cache [Y/n]? ")
            if not choice or choice.lower().startswith("y"):
                cmd = ("reprepro -vv --basedir /home/tshepang/.custom_repo/ "
                       "remove tshepang " + package_name)
                subprocess.call(cmd.split())

if __name__ == "__main__":
    main()

I strongly suspect the code can be better.

As a sidenote, here is sample UI:

apache2.2-common:
      Installed: (none)
      Candidate: 2.2.22-13
      Version table:
         2.2.22-13 0
            500 file:/home/tshepang/.custom_repo/ tshepang/main amd64 Packages
    remove from cache [Y/n]?
    removing 'apache2.2-common' from 'tshepang|main|amd64'...
    Exporting indices...
    Deleting files no longer referenced...
    deleting and forgetting pool/main/a/apache2/apache2.2-common_2.2.22-13_amd64.deb

Your code looks very good, so I'll just propose some minor (and subjective) improvements:

Imports: PEP8 has some recommendations about grouping imports that sound pretty reasonable.
("s1" "s2"): I don't know what the orthodoxy says, but I prefer an explicit + in between.
list(): Why not []?
wheezy_packages.extend([pkg["Package"] for pkg in repo]) -> wheezy_packages.extend(pkg["Package"] for pkg in repo).
repo = a, then repo = f(repo). IMHO this is as common a pattern as is undesirable. Different values deserve different variable names (key point of functional programming).
Function too long: I'd split the code in at least two auxiliary functions, one to get wheezy_packages and another to run the commands.


Monte-Carlo method to estimate Pi runs slower in multiple threads, than in single thread I'm learning Scala, and I wrote a program to estimate the value of Pi. When I'm using multiple threads, it takes 5-6 times longer to calculate the same iterations. I wrote a similar program in Java, with plain old threads, and with ExecutorService , and the results are the same.

Why is this the case?

(I have 4 cores in my processor, and during the multithreading calculation, the processor usage goes up to 100%.)

import java.util.Random
import java.util.concurrent.Executors
import java.util.concurrent.Callable

object Main {
  def main(args: Array[String]): Unit = {
    println("Calculating PI using the Monte-Carlo method")
    val n = 10000000
    evaluatePiCalculator(new SimplePiCalculator(n))
    evaluatePiCalculator(new ThreadedPiCalculator(n))
  }
  def evaluatePiCalculator(calc: PiCalculator) = {
    val pi = time { calc.calculate() }
    println(pi)
    val d = Math.abs(Math.PI - pi)
    println(d)
  }
  def time[R](block: => R): R = {
    val t0 = System.nanoTime()
    val result = block // call-by-name
    val t1 = System.nanoTime()
    val tdiff = t1 - t0
    println("Elapsed time: " + tdiff + "ns" + " " + (tdiff / 1000000) + "ms")
    result
  }
}
object Circle {
  class Point(val x: Double, val y: Double) {
    def isInside: Boolean = Math.sqrt(x * x + y * y) < 1.0
  }
  val random = new Random()
  private def randomPoint(): Point = {
    def generate() = random.nextDouble() * 2 - 1
    new Point(generate(), generate())
  }
  def tryToHit(): Boolean = randomPoint().isInside
}

abstract class PiCalculator() {
  def calculate(): Double
}

class SimplePiCalculator(n: Int) extends PiCalculator with Callable[Int] {
  override def call(): Int = calculateHits()
  def calculateHits(): Int = {
    var hits = 0
    for (i <- 1 to n) {
      if (Circle.tryToHit()) hits += 1
    }
    hits
  }
  def calculate(): Double = 4.0 * calculateHits / n
}
class ThreadedPiCalculator(n: Int) extends PiCalculator {
  val threads = 4
  val pool = Executors.newFixedThreadPool(threads)

  def calculate(): Double = {
    val f1 = pool.submit(new SimplePiCalculator(n / threads))
    val f2 = pool.submit(new SimplePiCalculator(n / threads))
    val f3 = pool.submit(new SimplePiCalculator(n / threads))
    val f4 = pool.submit(new SimplePiCalculator(n / threads))

    val (h1, h2, h3, h4) = (f1.get, f2.get, f3.get, f4.get)
    pool.shutdown()
    4.0 * (h1 + h2 + h3 + h4) / n
  }
}

Here are the results of the run:

Calculating PI using the Monte-Carlo method
Elapsed time: 473156580ns 473ms
3.1405192
0.0010734535897931607
Elapsed time: 3413799647ns 3413ms
3.1424036
8.109464102070696E-4

Update:

If I change the Circle object to a class, and create an instance inside of  SimplePiCalculator, and use that instance to calculate the hits, the expected performance discrepancy disappears. The calculation takes half the time of the single threaded implementation.

So the cause of this was using a common object from multiple threads.

However, when I tried to apply the same with the Java solution (i.e. change the tryToHit method from static to instance call), it did not work.

Can I ask, how to debug multithreaded code? What are the tools, methods, guidelines? How to determine the cause of slowdowns?

The cause of the long execution times in the multithreaded case were the use of static methods, fields, objects.
In the scala code code above, if I change the Circle class to object:

class Circle {
  class Point(val x: Double, val y: Double) {
    def isInside: Boolean = Math.sqrt(x * x + y * y) < 1.0
  }
  val random = new Random()
  private def randomPoint(): Point = {
    def generate() = random.nextDouble() * 2 - 1
    new Point(generate(), generate())
  }
  def tryToHit(): Boolean = randomPoint().isInside
}

And then create a Circle instance inside of the PiCalculator class:

class SimplePiCalculator(n: Int) extends PiCalculator with Callable[Int] {
  override def call(): Int = calculateHits()
  val circle = new Circle
  def calculateHits(): Int = {
    var hits = 0
    for (i <- 1 to n) {
      if (circle.tryToHit()) hits += 1
    }
    hits
  }
  def calculate(): Double = 4.0 * calculateHits / n
}

Then execution times are as follows:

Calculating PI using the Monte-Carlo method
Elapsed time: 481745137ns 481ms
3.142086
4.933464102068186E-4
Elapsed time: 219407150ns 219ms
3.1410116
5.810535897929903E-4

Also in the Java solution, I've found, that the Circle class was using a public static final Random RANDOM static variable to generate random points, and this was the cause of the slowdown.

So it looks like, when writing multithreaded code, one must avoid using common objects, and static methods/variables.


Extending DOM elements with prototype for easier function execution I've creating a small library of JavaScript functions that I will be using. Some are for UI functions others are to return something.

I am wondering if this method is ok and not a bad move before going any further with this library. Also, please do not mention jQuery as this is all JavaScript!

HTMLElement.prototype.drag = function(bool) {
var self = this;
self.classList.add('draggable');
    event.stopPropagation();
    event.preventDefault();
    var origLeft= parseInt(self.offsetLeft,10);
    var origTop = parseInt(self.offsetTop,10);
    var mdX = event.clientX;
    var mdY = event.clientY;
    var elements = [];
    if(bool === true){
      var j = window.localStorage.getItem('userSettings');
      if(j){
        self.style.left= j.left;
        self.style.top = j.top;
      }
    }
      function drag(bool) {
        self.style.position="absolute";
        self.style.zIndex=999;
        self.style.left = origLeft + event.clientX - mdX + "px";
        self.style.top = origTop + event.clientY - mdY + "px";
        event.stopPropagation();
      }
      function stop(bool){
        self.classList.remove('draggable');
        self.style.zIndex=0;
        document.removeEventListener('mousemove',drag,true);
        document.removeEventListener('mouseup',stop,true);
           if(bool === true){
            var settings = {
              left: self.style.left,
              top: self.style.top
            };
            var b = JSON.stringify(settings);
            window.localStorage.setItem('userSettings',b);
            console.log(b);
            }
        event.stopPropagation();
      }
       document.addEventListener('mousemove',drag,true);
       document.addEventListener('mouseup',stop,true);
};

The above code is of course for a draggable function. Here is a getClientRects() sort of function but better:

HTMLElement.prototype.getRect = function(){
     var a = this.offsetLeft;
     var b = this.offsetTop;
     var c = this.offsetHeight + b;
     var d = this.offsetWidth + a;
     var f = this.offsetHeight;
     var g = this.offsetWidth;
     var obj = { };
     obj.left = a;
     obj.right=d;
     obj.top=b;
     obj.bottom=c;
     obj.width = g;
     obj.height=f;
  return obj;
};

The purpose of showing you all this is to get your thoughts and maybe advise about prototype or should I not do it this way. I just like the method execution like this:

document.getElementById('div').getRect();

instead of doing it with a function getRect('div');.

The problem is for one not sure what enumerable is as I've self taught everything, and never really read on the terminology. I know what one of the users means when he says iterating them using a for in loop though not sure how to make it non-enumerable. Nor how to go about this any better way as I don't want my users (who use jQuery a lot) though the library is huge and honestly I'd rather them use a vanilla JavaScript library in the sense that is minimized for purposes of what I am doing (making a huge plug-in with a library and other coding options they can have their hands on).

I don't have any insight on extending host objects, because I've never done it, and quite frankly this scares me a little bit.

That said, I can shed a bit of light on that "enumerable" problem.

Objects in javascript are traversable, much like arrays. This means that when you do :

var o = {foo: "bar", baz: "buzz"};
for(var property in o){
  console.log(o[property]);
}

you get "bar" and "buzz" in the console.

Now in a for-in loop, the only properties that you get are those who are enumerable. What does this mean ? Basicly, this means that you only get properties for which o.propertyIsEnumerable('propertyName') is true (and by extension, for which o.hasOwnProperty('propertyName') is true).

When you create a property on an object, by default it is enumerable, and hasOwnProperty returns true for it. But it is possible to define properties with modifiers :

   o = {};
   Object.defineProperty(o, 'foo', {
     value:      function(){ console.log('foo'); },
     enumerable: false
   });

   o.foo();                      // "foo"
   o.propertyIsEnumerable('foo') // false
   o.hasOwnProperty('foo')       // false
   for(property in o){
     console.log(property); // this will never be reached - o has no enumerable property yet
   }

One reason to mark certain properties as not enumerable is that when extending an object, one usually copies all enumerable properties from a source object using a for-in loop. When writing a lib, you have to care about this, because if you don't your users will have to deal with properties they probably are not aware of or don't care about.

Also note that every fresh object already has non enumerable properties : prototype, hasOwnProperty, etc...

Hope this helps. For more info, see Object.defineProperty


Join a collection of strings until character limit is reached Question

I wrote a function which will take a collection of strings — and return a comma-separated string which doesn't exceed the specified character limit.

It essentially works by joining the collection of strings over and over again, and removing the last item in the collection each time, until the comma-separated string doesn't exceed the specified character limit.

private static string Join(IEnumerable<string> collection, int characterLimit)
{
    var values = new List<string>(collection);
    var joined = string.Join(", ", values);
    while (joined.Length > characterLimit)
    {
        values.RemoveAt(values.Count - 1);
        joined = string.Join(", ", values);
    }
    return joined;
}

I feel like there must more efficient way of doing this ... and that's what I'd love some help with.

Example

private string[] words =
{
    "able", "acid", "angry", "automatic", "awake", "bad", "beautiful", "bent", "bitter",
    "black", "blue", "boiling", "bright", "broken", "brown", "certain", "cheap", "chemical", "chief", "clean",
    "clear", "cold", "common", "complete", "complex", "conscious", "cruel", "cut", "dark", "dead", "dear",
    "deep", "delicate", "dependent", "different", "dirty", "dry", "early", "elastic", "electric", "equal",
    "false", "fat", "feeble", "female", "fertile", "first", "fixed", "flat", "foolish", "free", "frequent",
    "full", "future", "general", "good", "gray", "great", "green", "hanging", "happy", "hard", "healthy", "high",
    "hollow", "ill", "important", "kind", "last", "late", "left", "like", "living", "long", "loose", "loud",
    "low", "male", "married", "material", "medical", "military", "mixed", "narrow", "natural", "necessary",
    "new", "normal", "old", "open", "opposite", "parallel", "past", "physical", "political", "poor", "possible",
    "present", "private", "probable", "public", "quick", "quiet", "ready", "red", "regular", "responsible",
    "right", "rough", "round", "sad", "safe", "same", "second", "secret", "separate", "serious", "sharp",
    "short", "shut", "simple", "slow", "small", "smooth", "soft", "solid", "special", "sticky", "stiff",
    "straight", "strange", "strong", "sudden", "sweet", "tall", "thick", "thin", "tight", "tired", "true",
    "violent", "waiting", "warm", "wet", "white", "wide", "wise", "wrong", "yellow", "young"
};

private void joinButton_Click(object sender, EventArgs e)
{
    var characterLimit = 500; // the joined string's length will be <= 500
    var joined = Join(words, characterLimit); // the joined string
    Console.WriteLine("joined: " + joined);
    Console.WriteLine("joined.Length: " + joined.Length);
}

Output

joined: able, acid, angry, automatic, awake, bad, beautiful, bent, bitter, black, blue, boiling, bright, broken, brown, certain, cheap, chemical, chief, clean, clear, cold, common, complete, complex, conscious, cruel, cut, dark, dead, dear, deep, delicate, dependent, different, dirty, dry, early, elastic, electric, equal, false, fat, feeble, female, fertile, first, fixed, flat, foolish, free, frequent, full, future, general, good, gray, great, green, hanging, happy, hard, healthy, high, hollow, ill
joined.Length: 495

Although @TopinFrassi's solution is death plain and simple, I would separate the fetching of the values which fit in the limit and the actual joining with the separator like so

private static IEnumerable<string> FetchInRange(IEnumerable<string> collection, int characterLimit, int separationLength)
{

    int currentlength = -separationLength;

    foreach (var value in collection)
    {
        int length = value.Length + separationLength;
        currentlength += length;
        if (currentlength  > characterLimit)
        {
            yield break;
        }

        yield return value;
    }

}
private static string Join(IEnumerable<string> collection, int characterLimit, string separator = ", ")
{
    return string.Join(separator, FetchInRange(collection, characterLimit, separator.Length));
}

Each method has only one responsibility and they can be used for a wider range of separators as well.


C++ identity function I've implemented an identity function (well, actually a functor struct) in C++. The goal is that every occurrence of an expression expr in the code can be substituted by identity(expr) without changing the semantics of the program at all.

I make it a struct with a templated operator() instead of simply a function template because this enables us to pass identity as an argument to other functions (say std::transform) without needing to specify the type (e.g., identity<std::pair<std::vector<int>::const_iterator, std::vector<double>::const_iterator>>).

The code is written in C++14.

#include <utility>

static constexpr struct identity_t {
    template<typename T>
    constexpr decltype(auto) operator()(T&& t) const noexcept
    {
        return std::forward<T>(t);
    }
} identity{};

Usage:

int x = 42;
identity(x) = 24;

constexpr int size = 123;
int arr[identity(size)] = {};

vector<int> v1 = {1, 2, 3, 4}, v2;
v2.reserve(v1.size());
transform(v1.cbegin(), v1.cend(),
          back_inserter(v2),
          identity);

template<typename T>
class my_container {
public:
    template<typename F>
    auto flat_map(F&& f) const { ... }

    auto flatten() const { return flat_map(identity); }

    ...
};

Since identity(expr) is nothing more than a cast, performance should not be a problem. I'm concerned whether there are cases in which this implementation fails to keep the program's behavior unchanged. If there are, how can I fix the implementation?

EDIT: I changed "a variable x" in the first paragraph to "an expression expr". The latter is more accurate.

Well, that looks like a straightforward use of perfect forwarding in the parameter (T&&, std::forward<T>) and in the return type (decltype(auto)). So yep, you've got it.

There are plenty of places in C++ where x and identity(x) don't do the same thing, either because x is a name as well as an expression, or because x is a construct that looks like an expression but technically is not one. (Personally, I consider almost all of these places to be mistakes in the design of C++.) Here are the ones I can think of.

Replacing identity(x) with x in all of the following examples changes the behavior of the code sample.

As mentioned in the comments on the question, the name of a function template can deduce what kind of function pointer to decay to:

template<class T> void f(T) {}
void (*fp)(int) = identity(f);

The name of a local variable gets copy elision (a.k.a. Named Return Value Optimization, or NRVO):

struct S {
    S() {}
    S(const S&) { puts("copy"); }
    S(S&&) { puts("move"); }
};
S f() {
    S s;
    return identity(s);
}
int main() { f(); }

The name of a local variable is treated as an rvalue in the context of return:

struct S {
    S() {}
    S(const S&) { puts("copy"); }
    S(S&&) { puts("move"); }
};
std::any f() {
    S s;
    return identity(s);
}
int main() { f(); }

Lifetime extension applies to temporaries whose construction is "visible" in some sense that is extremely subtle when I start thinking hard about it. Interposing the call to identity disables lifetime extension.

struct S {
    S() { puts("ctor"); }
    S(const S&) = delete;
    S(S&&) = delete;
    ~S() { puts("dtor"); }
};
int main() {
    const S& x = identity(S());
    puts("done");
}

Braced initializers and string literals look like expressions, but in the context of an initializer, they're special cases:

const char x[] = identity("hello");
int y = identity({5});

Now, I can't imagine how you'd use identity in your codebase where any of these quirks might matter; but then, I don't quite see how you plan to use identity at all. Your only fleshed-out example is just using std::transform(..., identity) as a verbose way of writing std::copy(...), which doesn't seem very useful.


Check if a Binary Tree is full Problem statement

Given a node check whether the sub-tree rooted at given node is full binary tree or not.

Definition

  A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.

Solution

class TreeNode(object):
  """Node of a Binary tree."""
  def __init__(self, key, left=None, right=None):
    self.key = key
    self.left = left
    self.right = right

  def __str__(self):
    return "{0}".format(self.key)

def insert_left(parent, node):
  parent.left = node
  return parent

def insert_right(parent, node):
  parent.right = node
  return parent

def is_leaf(node):
  """Checks whether given node is leaf."""
  return node.left is None and node.right is None

def is_full(node):
  """Checks if the subtree rooted at the given node is full.

  A Binary tree is full when every node other than leaves
  has two children.
  """
  if node is None:
    return True
  if is_leaf(node):
    return True
  if node.left is not None and node.right is not None:
    return is_full(node.left) and is_full(node.right)
  return False

def build_tree(inorder, preorder):
  """Builds a Binary Tree from given inorder and preorder traversal.
  Steps:
    1. Take the first element from the preorder list.
    2. Get the index of the element from inorder list.
    3. Set the element as root.
    4. Take all elements left to root from inorder list.
    5. Take all elements right to root from inorder list.
    6. Calculate preorder list for left and right subtree respectively.
    7. Repeat from step 1 for each subtree.
  """
  def recurse(node, inorder, preorder):
    if len(preorder) == 1:
      return TreeNode(preorder)
    key  = preorder[0]
    root_index    = inorder.find(key)
    inorder_left  = inorder[:root_index]
    inorder_right = inorder[root_index+1:]
    preorder_left = preorder[1:len(inorder_left)+1]
    preorder_right = preorder[root_index+1:]
    node = TreeNode(key)
    if len(inorder_left):
      insert_left(node, recurse(None, inorder_left, preorder_left))
    if len(inorder_right):
      insert_right(node, recurse(None, inorder_right, preorder_right))
    return node
  return recurse(None, inorder, preorder)

import unittest

class TestBinaryTree(unittest.TestCase):

  def test_isFull(self):
    root = build_tree('DBEAFIC', 'ABDEICF')
    self.assertTrue(is_full(root))

    root = build_tree('DBEAFC', 'ABDECF')
    self.assertFalse(is_full(root))

if __name__ == '__main__':
  unittest.main()

Time Complexity

It seems its a \$O(N)\$ where \$N\$ is the number of nodes in the given Binary Tree.

I am also interested in mathematical approach for estimating complexity of these kind of problems. So, here is my initial approach:
\$T(n) = T(n/2) + T(n/2) + 2\$

Is there more cleaner way? Also, the above solution uses a DFS approach i.e. checking every node in a tree. Can we optimize it?

Note

I have extracted away the definition of build_tree as its not important here.

The binary tree here consists of either None or TreeNode, so all
functions should accept both of these objects as arguments, but
is_leaf currently breaks when passed a None node.  This
representation is also a bit problematic, because if you get a None
somewhere, how do you know it's meant to be a tree?

If that case is included, then the first check in is_full can be
removed.  Otherwise I don't see anything else to optimise, though the
results for checking the variables against for None could possibly be
cached so the code is minimally faster for huge trees.

Also,

the indentation is inconsistent, TreeNode has four spaces in
__init__.  You know,
PEP8.
if len(x): is less clear than, e.g. if x:, but in both cases it's
relying on conversions from int/list to bool, so not very clear.


Print every line of file, last to first, with recursion Had a discussion with a friend to solve this extra credit problem, and we came up with two separate solutions. What are the differences between these two? Is one better than the other? How can I make this code better?

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;

public class ExtraCredit {

    public static void main(String[] args) throws FileNotFoundException {
        int count = 0;
        Scanner scan = new Scanner(new File("src/ExtraCredit.java"));
        recursiveCountEveryOtherLine(count, scan);
        scan = new Scanner(new File("src/ExtraCredit.java"));
        System.out.println("***SECOND METHOD***");
        recursiveScannerExploit(scan);
    }
    // Write a method called from main that prints
    // every other line of this file from last to first
    // use recursion NO LOOPS!!
    // print line 10, 8, 6, 4, 2

    public static void recursiveCountEveryOtherLine(int count, Scanner scan) {
        count++;
        if (!scan.hasNextLine()) {
            scan.close();
            return;
        } else if (count % 2 == 0) {
            String temp = scan.nextLine();
            recursiveCountEveryOtherLine(count, scan);
            System.out.println(count + " " + temp);

        } else {
            scan.nextLine();
            recursiveCountEveryOtherLine(count, scan);
        }
    }

    public static void recursiveScannerExploit(Scanner scan) {
        if (closeScanner(scan)) {
            return;
        }
        String tempGarbage = scan.nextLine(); // Used to pop an element off the scanner
        if (closeScanner(scan)) {
            return;
        }
        String temp = scan.nextLine();
        recursiveScannerExploit(scan);
        System.out.println(temp);
    }

    public static boolean closeScanner(Scanner scan) {
        if (!scan.hasNextLine()) {
            scan.close();
            return true;
        } else {
            return false;
        }
    }
}

As I get started I just want to mention that you have two unused imports:

import java.io.FileInputStream;
import java.io.InputStream;

Now I'll address your questions:

  What are the differences between these two?

Virtually nothing other than the obvious:

Method #1 depends on a counter parameter to decide whether or not the line should be printed whereas the method #2 does not. This makes method #1 a little awkward to read, but anyone who understands recursion (which is any good programmer) should catch on to what you're doing. Having the counter could use slightly more memory but it's unlikely something this small would have any impact on overall performance and it's generally not worthwhile to optimize something like this unless you have measured your program's performance and determined there is a trouble spot.

Method #2 depends on calling the closeScanner method twice, and invoking a method may carry a bit of overhead cost. However you really don't need to concern yourself with this unless you have measured the performance of your code and find that there is a problem. (See the answer to this question)

  Is one better than the other?

Again, the two are so similar there isn't really an objective way to say with certainty which is "better". If I had to select one I would probably prefer method #2 as I think it would more straightforward for someone else to use. It doesn't require knowledge of recursion or passing a counter initialized to the correct value.

  How can I make this code better?

In general comment your code so that others recognize its intended purpose and expected inputs and outputs. Javadoc is a good way to do this. Something else you can do is modify your method(s) to return something (e.g. String) rather than printing to System.out so that you can write automated tests against them more easily.

Method #1:

else if (count % 2 == 0) { does not need to have the else since you would have returned from the method if there is no next line.

When you call this method you don't need a counter reference in main, so instead just directly pass the value of count like this:

recursiveCountEveryOtherLine(0, scan);

Method #2:

Replace this line: String tempGarbage = scan.nextLine();
with this: scan.nextLine(); as you have no reason to keep a reference to the lines you aren't going to print.

Inside of the closeScanner method you have:

else {
    return false;
}

you can simply write return false without the else since you would have returned true earlier if there is no next line.


Simple Command Line Password Manager Kruptos is a simple tool that encrypts and decrypts the ~/.kruptos directory with the password that is stored in ~/.kruptos/.phrazein. There are 3 commands:

e - Encrypt
d - Decrypt
i - Initialize

Goal
I have a couple main goals:

Design: How could I make this more resilient to change?
Readability: How could I make this more readable?
Best Practices: Are there aspects of a bash command that I am missing?

# Minimalist password manager
function kruptos
{
    # Decipher the flag
    if [[ $# -eq 1 ]]; then
        DOWHAT="$1"
    else
        DOWHAT="d"
    fi

    # Perform an action
    if [[ $DOWHAT == "d" ]]; then
        #Decrypt
        pushd . &>/dev/null
        cd ~/
        openssl aes-256-cbc -d  -in .kruptos.tar.gz.aes | tar -xz -f - --strip-components=2 && rm ~/.kruptos.tar.gz.aes
        popd &>/dev/null
    elif [[ $DOWHAT == "e" ]]; then
        #Encrypt
        tar -zcf - ~/.kruptos | openssl aes-256-cbc -out ~/.kruptos.tar.gz.aes -kfile ~/.kruptos/.phrazein && rm -r ~/.kruptos
    elif [[ $DOWHAT == "i" ]]; then
        #Initialize
        mkdir ~/.kruptos
        echo pswd > ~/.kruptos/.phrazein
    else
        echo "$DOWHAT is not an acceptable flag"
    fi
}

I'll not address the security analysis; I'll assume you've done threat modelling and are happy with the overall approach.

Instead of a chain of if/elif all testing the same variable, the natural approach is a switch.  I'll also take advantage of ${:-} to default the argument:

case "${1:-d}" in
    d)
        # Decrypt
        # (commands)
        ;;
    e)
        # Encrypt
        # (commands)
        ;;
    i)
        # Initialize
        # (commands)
        ;;
    *)
        # invalid
        exec >&2
        echo "Usage: $0 [option]"
        echo "Options:"
        echo "  d - decrypt [default]"
        echo "  e - encrypt"
        echo "  i - initialize"
        exit 1
        ;;
esac

Note that I've sent the error message to error output (&2) and exited with an error code.  Actually, this should really be return 1 since it's a function rather than a complete script.

In the decrypt code, you use pushd and popd.  These are suited to interactive use, but are best left alone in scripts or functions (that's why you discovered that you need to redirect their output).  Instead, you can use a sub-shell:

(cd ~; commands... )

or use full paths.  In this case, we want tar to output to ~, and we can tell it to do so, using its -C option:

openssl -in ~/.kruptos.tar.gz.aes | tar -C ~ -xz -f -

Finally, you can avoid duplication by putting paths that are used more than once into variables.  This protects you against mis-typing any of them, and makes it easier if you should ever want to change them.

Modified code

Here's what I have, after applying the above changes:

function kruptos
{
    local dir=~/.kruptos
    local file=~/.kruptos.tar.gz.aes
    local keyfile="$dir/.phrazein"

    case "${1:-d}" in
        d)
            # Decrypt
            openssl aes-256-cbc -d  -in  \
                | tar -C "$dir" xfz - \
                && rm "$file"
            ;;
        e)
            # Encrypt
            tar -C "$dir" cfz - . \
                | openssl aes-256-cbc -out "$file" -kfile "$keyfile" \
                && rm -r "$dir"
            ;;
        i)
            # Initialize
            mkdir "$dir"
            echo pswd >"$keyfile"
            ;;
        *)
            # invalid
            exec >&2
            echo "Usage: $0 [option]"
            echo "Options:"
            echo "  d - decrypt [default]"
            echo "  e - encrypt"
            echo "  i - initialize"
            return 1
            ;;
    esac
}