Programming Challenge from Kattis: Apparatus I am trying to solve apparatus problem, paraphrased below.

  There is an apparatus with n on/off switches with a one-to-one correspondence to n lights (but with an unknown permutation).
  We have several different photographs of the apparatus showing different configurations of the switches and lights. Are these photos sufficient to fully describe the device?

  Input

  First line contains two integers: n (the number of switches, 1 ≤ n ≤ 1000) and m (the number of photographs, 0 ≤ m ≤ 1000).

  Each subsequent pair of lines describes the switches and the lights as a string of 1 (on) and 0 (off).

  Output

  Write the number of possible different wirings, modulo 1000003.

I have a solution but it takes longer than 2 seconds which is the time limit. I've tried to optimize my code for speed but can't get it within the 2 second limit.

import sys
import math

for line in sys.stdin:

    line = line.strip("\n").split(" ")
    numSwitches = int(line[0])
    numPics = int(line[1])

    wiring = {}
    inValid = False
    for i in range(numPics):
        if (inValid):
            break
        x = sys.stdin.readline().strip("\n")
        f_x = sys.stdin.readline().strip("\n")

        x_ones = 0
        f_x_ones = 0

        digit = 0
        for i in range(numSwitches):
            if f_x[i]=='1':
                digit += 2**(numSwitches-i-1)
                f_x_ones += 1

        for switch in range(numSwitches):
            if (x[switch]=='1'):
                x_ones += 1
                if not (switch in wiring.keys()):
                    wiring[switch] = digit
                else:
                    wiring[switch] &= digit

        if x_ones != f_x_ones:
            inValid = True
            break

    if not inValid:
        for i in wiring.values():
            if i==0:
                inValid = True
                break

    for possibilities in set(wiring.values()):
        frequency = wiring.values().count(possibilities)
        if frequency>1:
            oneBits = 0
            while (possibilities>0):
                oneBits += (possibilities%2==1)
                possibilities /= 2
            if oneBits < frequency:
                inValid = True
                break

    if not inValid:
        print math.factorial(numSwitches-numPics)%1000003
    else:
        print 0

I'm looking for suggestions of ways I should have approached the problem or input on how I can optimize my current code.

Note:
Consider the following test case:

3 2
110
011
011
011

My code finds that is invalid in the following manner. First, upon encountering the first photograph (110, 011). The wiring dictionary gets assigned the following keys and values:

wiring[0] = 011
wiring[1] = 011

This means that the first and second switch can light up either the second or third lights. Upon encountering the second photograph (011, 011). wiring is updated as follows:

wiring[1] = 011 & 011 = 011
wiring[2] = 011

Now observe that the state of wiring indicates that all three switches can light up either the second and third lights. This is an inconsistency since 3 switches have to light up three lights, here we have three switches lighting up 2 lights.

Disclaimer: I won't try and provide a different algorithm to improve the time complexity of the approach. Instead I’ll rather focus on introducing python constructs that will cleanup the code and may help gain speed a bit.
Reading data from standard input
I had trouble running your script from both IDLE and windows command prompt. Neither of them were good at handling sys.stdin as a file. But we can improve things by using the builtin input (raw_input in Python 2) since we just want to read lines one by one.
Converting back and forth between integers and their binary representation
One of the way to improve your computation of oneBite would be to use the divmod builtin. But it is even more easier when using bin and counting the number of '1' in the returned string.
Same when computing digit: the int builtin accept a second argument which is the base in which the number is represented.
Use functions
You could make the code easier to read and understand by using functions: one to parse two lines (one photo) and one to iterate over the whole set of photos and interpret the results.
Functions will also allow you to import your file into an interactive session and test things more easily. If you want to have code at the top-level to be run when invoking your script from the command line, it is recommended to put it under an if __name__ == "__main__" clause.
collections
The last part of your code count the frequency for a certain possibility in a bizarre way. Time for you to learn about collections.Counter.
PEP8

Use snake_case instead of camelCase for your variable names.
Use spaces around most of your operators (frequency > 1, possibilities%2 == 1, possibilities > 0…)
Remove parenthesis around your tests

EAFP
While
    if not (switch in wiring.keys()):
        wiring[switch] = digit
    else:
        wiring[switch] &= digit

is correct, I would first write it
    if switch in wiring:
        wiring[switch] &= digit
    else:
        wiring[switch] = digit

for readability (and less computation) but then change it to
    try:
        wiring[switch] &= digit
    except KeyError:
        wiring[switch] = digit

It is not necessarily faster in this case (it is when failures are much less than success) but I find it clearer.
Putting it all together
In Python 2 use raw_input, xrange and itervalues instead of input, range and values.
from math import factorial
from collections import Counter

def parse_photo(wiring):
    switches = input()
    lights = input()

    if switches.count('1') != lights.count(1):
        return False # invalid data

    # Convert binary value to integer
    lights_value = int(lights, 2)

    for switch, switch_value in enumerate(switches):
        if switch_value == "1":
            try:
                wiring[switch] &= lights_value
            except KeyError:
                wiring[switch] = lights_value

    return True

def wiring_possibilities():
    wiring = {}
    num_switches, num_photos = map(int, input().split())

    for _ in range(num_photos):
        if not parse_photo(wiring):
            return 0

    frequencies = Counter(wiring.values())
    if 0 in frequencies:
        # Same as if 0 in wiring.values()
        return 0

    for possibility, frequency in frequencies.items():
        switched_on_bits = bin(possibility).count('1')
        if switched_on_bits < frequency:
            return 0

    return factorial(num_switches - num_photos) % 1000003

if __name__ == "__main__":
    print(wiring_possibilities())


Alternate letters to UpperCase As an exercise I repeated this Java question, but in Go: Convert string to mixed case

The objective is for every second letter to be converted to uppercase.

Go string processing is relatively new to me, and I am looking for feedback on the use of the unicode package, any other go language or library features I should be using, and of course, issues with style, convention, or possible bugs.

I have put the following in the playground as well.

package kata

import (
    "unicode"
)

// AlternateCase will return the input string modified such that alternate letters are transformed to uppercase.
//
// Note that non-letters are ignored, so in the input string `a!b` the `!` is ignored, so `b` is the second letter.
// The result of AlternateCase on `a!b` is `A!b`.
func AlternateCase(input string) string {
    runes := make([]rune, 0, len(input))
    var upper bool
    for _, c := range input {
        if unicode.IsLetter(c) {
            upper = !upper
            if upper {
                c = unicode.ToUpper(c)
            }
        }
        runes = append(runes, c)
    }
    return string(runes)
}

I have also written some test cases, and a documentation example:

package kata

import (
    "fmt"
    "testing"
)

func TestAlternateCase(t *testing.T) {
    cases := []struct{ input, output string }{
        {"hello, world!", "HeLlO, wOrLd!"},
        {"a!b", "A!b"},
        {"AAAA", "AAAA"},
        {"", ""},
        {"h", "H"},
        {"!h", "!H"},
        {"日本語", "日本語"},
        {"f日u本b語ar", "F日U本B語Ar"},
    }
    for _, c := range cases {
        got := AlternateCase(c.input)
        if got != c.output {
            t.Errorf("For input '%v' expect '%v' but got '%v'", c.input, c.output, got)
        }
    }
}

func ExampleAlternateCase() {
    hi := "hello, world!"
    fmt.Printf("The AlternateCase of '%v' is '%v'\n", hi, AlternateCase(hi))
    // Output: The AlternateCase of 'hello, world!' is 'HeLlO, wOrLd!'
}

I am looking for feedback on the test mechanisms as well.

I think both your solution and your testing are fine.

A couple of test cases I would add (but your solution also passes them):

a string starting with BOM, e.g. {"\xef\xbb\xbfhi", "\xef\xbb\xbfHi"}
a string which is not a valid UTF-8 string, e.g. {"h\xffi", "H\xef\xbf\xbdi"}
a string with multiple invalid UTF-8 bytes, e.g. {"h\xff\xffi", "H\xef\xbf\xbd\xef\xbf\xbdi"}

Explaining the invalid UTF-8 strings: Since you are converting your input string to runes, invalid UTF-8 bytes are reported as a value of 0xfffd (the Unicode replacement character), which when encoded as UTF-8 (happens when you convert []rune back to string) results in a sequence of []byte{0xef, 0xbf, 0xbd}; this is what the invalid 0xff byte is compared to in the test case.

Performance wise I would use a string => []rune conversion as you not only need the runes, but you also want to convert them back to a string. Using append() is slower, and it has to assign a slice value (a descriptor) at each rune.

Also note that if we convert the string to []rune, we only need to assign (overwrite) new runes which are converted to their upper case:

This is how I would do it:

func AlternateCase(s string) string {
    rs, upper := []rune(s), false
    for i, r := range rs {
        if unicode.IsLetter(r) {
            if upper = !upper; upper {
                rs[i] = unicode.ToUpper(r)
            }
        }
    }
    return string(rs)
}


Computing the largest substring starting with a substring Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length.

sub_sandwich("catcowcat", "cat") → 9
sub_sandwich("catcowcat", "cow") → 3
sub_sandwich("cccatcowcatxx", "cat") → 9

I'm not very satisfied with my code and I'm not sure how I can improve it.

def subSandwich(word, char, pos, start, end):
    if pos == len(word)-1:
        if end == 0:
            return len(char)
        return end - (start-2)

    if word[pos:pos+len(char)] == char:
        if start != 0:
            end = pos + len(char) - 1
        else:
            start = pos+1

    return subSandwich(word, char, pos + 1, start, end)

def main():
    print subSandwich("catcowcat", "cow",0,0,0)

if __name__ == "__main__":
    main()

Revise the sub for simplicity with only 2 parameters, reducing 1 char from both                                           end at 1 loop.

#!/usr/bin/python
import unittest
import sys
import os

def subSandwich_new(word, char):
    num = word.count(char)
    if num ==0:
        return 0
    elif num ==1:
        return len(char)
    else:
        # first string with length of char
        first = word[:len(char)]

        match = 0
        if first == char:
            match = match + 1
        else:
            # remove 1 char from word
            word = word[1:]
        # string from end with the length of char
        last = word[-len(char):]
        if last == char:
            match = match + 1
        else:
            # removing 1 char from word
            word = word[:-1]
        if match ==2:
            # first and last both match
            return len(word)
        else:
            return subSandwich_new(word, char)

class SandwichTestNew(unittest.TestCase):
    def test_subSandwich_new(self):
        result = subSandwich_new('catcowcat', 'cat')
        self.assertEqual(result, 9)

    def test_subSandwich_new2(self):
        result = subSandwich_new('catcowcat', 'cow')
        self.assertEqual(result, 3)

    def test_subSandwich_new3(self):
        result = subSandwich_new('ccatcowcatxx', 'cat')
        self.assertEqual(result, 9)

    def test_subSandwich_new4(self):
        result = subSandwich_new('cat', 'cat')
        self.assertEqual(result, 3)

    def test_subSandwich_new5(self):
        result = subSandwich_new('cat', 'cow')
        self.assertEqual(result, 0)


Criticize C argument parsing method On an IRC channel I'm a member of, one particular person mocks every piece of code I post, even if it's a rough draft or if I haven't coded in months. I am pretty well versed with computer theory and knowledge, but my skills with programming lack due to little practice.
 This particular code was from a project I was starting and I was putting down some ideas/structure on GitHub, when he pointed out this particular snippet.

So, after a couple months of trying to get the discipline to start coding again, I coded this and my question is: If indenting like this is bad, what other things did I do wrong here, assuming the logic is sound (I never tested it, I went on hiatus)?  Also, what would you do to avoid the indenting?

void parse_arguments(int count, char * arguments[]){//probably add file pointer here  to pass to load, change return type when an API is decided.
    int currentArg, paramIndex;

    for(currentArg = 1; currentArg <= count; currentArg++){
        if(arguments[currentArg][0] == '-'){
            for(paramIndex = 0; paramIndex < PARAMMAX; paramIndex++){
                if(strcmp(arguments[currentArg][1], arglist[paramIndex]) == 0){
                    switch(paramIndex){
                        case 0:
                            //load(currentArg + 1);
                            currentArg++;
                            break;
                        default:
                            break;
                    }
                    break;
                }
            }
        }
    }
}

Note: arglist is a statically declared array of chars.

void parse_arguments(int count, char * arguments[]){//probably add file pointer here  to pass to load, change return type when an API is decided.
    int currentArg, paramIndex;

    for(currentArg = 1; currentArg <= count; currentArg++){

Why are you counting from zero? In C arrays start from zero, but you are starting from 1. As it stands it looks like you skip the first argument and then read one past the end

        if(arguments[currentArg][0] == '-'){
            for(paramIndex = 0; paramIndex < PARAMMAX; paramIndex++){
                if(strcmp(arguments[currentArg][1], arglist[paramIndex]) == 0){

Isn't arguments[currentArg][1] a char? How are you passing it to strcmp?

                    switch(paramIndex){
                        case 0:
                            //load(currentArg + 1);
                            currentArg++;

I recommend against manipulating loop counters inside your loop. It makes it harder to follow whats going on.

                            break;
                        default:
                            break;
                    }
                    break;
                }
            }
        }
    }
}

So much indentation suggests that you should break this down into smaller functions. I'd also suggest that you store the results of the arguments into a struct.

A general sketch of how I'd do this:

struct options
{
    char * filename;
    int numberOfRabbits;
};

struct parameter
{
    char * name; // 'x' for option '-x'
    bool requiresOption; // whether or not we should have an option
    void (*handler)(struct options * options, char * argument);
};

void parse_arguments(int count, char * arguments[], struct options * options)
{
    char * argument;
    int position = 0;
    while(position < count)
    {
         struct parameter * param = determine_parameter(arguments[position++]);
         if(!parameter)
         {
              panic(); // don't know this parameter
         }
         if(param.requiresOption)
         {
               argument = arguments[position++];
         }else{
               argument = NULL;
         }
         param.handler(options, argument);
    }
}


Income tax rate calculator in c++ I have been trying to learn c++ for the sake of being comfortable with a second language. I found a project that seemed relatively easy, although it may not be implemented perfectly, it was a simple project.
I create a std::map<double, std::string>, which will represent the tax rate as a double, and the required income as a string. A user will input their income and the maximum amount of taxes to be paid in dollars will be returned. Here is the code:
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <map>
#include <iomanip>

double TaxesDue(double &income);
double HighestRate(double &income);

std::map<double, std::string> taxRate =
{
    {  0.35, "499999" },
    {0.31, "349999"},
    {0.25,"249999"},
    {0.21,"169999"},
    {0.18,"119999"},
    {0.14,"79999"},
    {0.10,"44999"},
    {0.05,"29999"}
};

int main()
{
    double income;

    std::cout << "Enter your income: " << std::endl;
    std::cin >> income;

    double taxesDue = TaxesDue(income);
    std::cout << taxesDue << std::endl;
}

double TaxesDue(double &income)
{
    double totalTaxes = 0.0;
    double taxDiff = 0.0; //as taxes are calculates, subtract the income

    double highestRate = HighestRate(income);

    for (double i = income; i > 29999; )//knowing the lowest tax rate is 0.05
    {
        taxDiff = (income - std::stod(taxRate[highestRate]));
        totalTaxes += (highestRate * taxDiff);
        i -= taxDiff;
        highestRate = HighestRate(i);
    }

    return totalTaxes;
}

double HighestRate(double &income)
{
    /*
    std::map<double, std::string> taxRate =
    {
        {  0.35, "499999" },
        {0.31,"349999"},
        {0.25,"249999"},
        {0.21,"169999"},
        {0.18,"119999"},
        {0.14,"79999"},
        {0.10,"44999"},
        {0.05,"29999"}
    };
    */

    if (income > std::stod(taxRate[0.35]))
    {
        return 0.35;
    }
    if (income > std::stod(taxRate[0.31]))
    {
        return 0.31;
    }
    if (income > std::stod(taxRate[0.25]))
    {
        return 0.25;
    }
    if (income > std::stod(taxRate[0.21]))
    {
        return 0.21;
    }
    if (income > std::stod(taxRate[0.18]))
    {
        return 0.18;
    }
    if (income > std::stod(taxRate[0.14]))
    {
        return 0.14;
    }
    if (income > std::stod(taxRate[0.10]))
    {
        return 0.10;
    }
    if (income > std::stod(taxRate[0.05]))
    {
        return 0.05;
    }

    return 0.0;
}

My biggest thing is trying to improve the HighestRate(double &income) method. How should I convert the if (income > std::stod(taxRate[x])) to make the code better? Meaning, are there any libraries that I could use to find 'where value > then this std::map value'?
Also I think that I should probably change the std::map<double, std::string> to std::map<double, double>.

This isn’t a bad idea for a learning project, and I’d say it’s implemented quite well.
Before I dive into the code itself, I’m going to do a high-level design review.
Design review
You’re using std::map backwards
So you want a list of pairs of values, where one value is the tax rate and the other income lower bound for that tax rate. In your code you made the tax rate the lookup key, and the lower income bound the value.
The problem with that is that what you want to do is use the income to lookup the tax rate. Since the tax rate is the key in your map, that means you actually have to manually go through the map, checking each entry and inspecting the value.
If your map were the other way around—with the thing you actually want to lookup, the income, as the key—the lookup code would be trivial:
// income lower bound is the key, tax rate is the value
auto const taxRate = std::map<double, double>{
    {499'999, 0.35},
    {349'999, 0.31},
    // and so on
};

double HighestRate(double income)
{
    // lower_bound() finds the key that is NOT LESS than the argument given
    // (in other words, the key that is greater or equal). So whatever income
    // you give it, it will give you the NEXT greater tax bracket. That means
    // we have to BACKWARDS one tax bracket to get the proper answer.
    //
    // If the data were encoded differently, this could be much simpler, but
    // you have to be careful not to change the logic.

    auto p = taxRate.lower_bound(income);

    // If we got the first tax bracket, there is no lower tax bracket... so
    // no taxes due.
    if (p == taxRate.begin())
        return 0.0;

    // Go backwards one tax bracket.
    --p;

    // Now just return the rate.
    return p->second;
}

Actually, the code is even simpler if you don’t use HighestRate():
double TaxesDue(double income)
{
    double totalTaxes = 0.0;

    // Starting tax bracket:
    auto p = taxRate.lower_bound(income);

    // Convert the starting tax bracket iterator to a REVERSE iterator so we
    // can go backwards (from highest tax bracket down to lowest).
    for (auto r = std::map<double, double>::reverse_iterator{p}; r != taxRate.rend(); ++r)
    {
        // For each tax bracket:

        // 1) subtract the lower bound from the income to get the amount
        //    taxable in that bracket
        auto taxable_amount = income - r->first;

        // 2) calculate the taxes, and add to the total
        totalTaxes += taxable_amount * r->second;

        // 3) the remaining income is everything not yet taxed... which is
        //    the same as the lower bound of the bracket
        income = r->first;
    }

    return totalTaxes;
}

Don’t take the two functions above too seriously; I didn’t test them, and I didn’t really think too hard writing them, so there may be mistakes.
The point I want to make here is about the shape of your map. You should ask what you’re using the map for; what are you using to search? In your case, you are using the income to search the map (to find the tax rate). That means the income should be the key… not the tax rate.
An extra map tip
Notice in the functions I wrote above that I had to go backwards and use reverse iterators, all of which increased the complexity quite a bit. Well, the cause of that is that std::map will store its elements in increasing order, starting from the lowest to the highest. But when you’re calculating taxes, you want to go the opposite way: you want to start at the highest tax bracket, and work your way down. That’s the way you wrote the data, too: from the largest to smallest tax bracket.
There is way to flip the order of std::map. std::map has 3 template parameters (well, actually 4, including the allocator). The third template parameter is the comparator function, which defaults to std::less. So to flip the order, all you got to do is use std::greater instead.
Observe:
auto const taxRate = std::map<double, double, std::greater<>>{
    {499'999, 0.35},
    {349'999, 0.31},
    // and so on
};

double TaxesDue(double income)
{
    double totalTaxes = 0.0;

    // Easy peasy.
    //
    // (Just note we switched to upper_bound() because the
    // greater-than/less-than logic is reversed.)
    for (auto p = taxRate.upper_bound(income); p != taxRate.end(); ++p)
    {
        auto taxable_amount = income - p->first;

        totalTaxes += taxable_amount * p->second;

        income = p->first;
    }

    return totalTaxes;
}

One more thing I should mention: I noticed you used the tag “hash map”. You’re not actually using a hash map; you’re using a normal map. In the standard library, the hash map is named std::unordered_map… but you do not want to use that for this case, because it is—as the name says—unordered… and you want ordering to make searching and doing calculations easier.
A note about money and floating point values
While it’s fine for practice code, you should never, ever use floating point types like double for currency.
To see why, try running this simple program:
#include <iostream>

auto main() -> int
{
    auto my_cash = 100.0;

    // Set up cout to print cash values nicely:
    std::cout.setf(std::ios_base::fixed, std::ios_base::floatfield);
    std::cout.precision(2);

    std::cout << "I have in my account: " << my_cash << "\n\n";

    my_cash += 1e24;
    std::cout << "The bank screwed up and deposited a septillion dollars!\n";
    std::cout << "I have in my account: " << my_cash << "\n\n";

    my_cash -= 1e24;
    std::cout << "The bank took their septillion dollars back.\n";
    std::cout << "I have in my account: " << my_cash << "\n\n";

    std::cout << ":(\n";
}

Example output:
I have in my account: 100.00

The bank screwed up and deposited a trillion dollars!
I have in my account: 999999999999999983222784.00

The bank took their trillion dollars back.
I have in my account: 0.00

:(

A better idea is to use an integer type fixed to the smallest money fraction you could want to work with. For example, instead of using a double value of 100.0 dollars, you might use an int value of 10000 cents. Or if you need more precision, you might use millionths of a dollar, so $100 would be an int with value 100'000'000. If int is too small, you’d use long or long long or std::int_fast64_t instead.
Then what you’d do is make a class for monetary values, to make working with them painless and transparent. The class would simply wrap your integer type, and then provide a nice interface so you could write code like:
class money_t
{
    // ...

private:
    std::int_fast64_t _value;
};

constexpr auto calculate_taxes(money_t income)
{
    return income * 0.05; // 0.05 is the tax rate
}

auto income = 100_dollars;

auto taxes = calculate_taxes(income);

std::cout << "you pay " << taxes << " in tax.\n";
std::cout << "you have " << (income - tax) << " left over.\n";

// the output is automatically nicely formatted as:
//      you pay $5.00 in tax.
//      you have $95.00 left over.

I would recommend starting with something as simple as:
using money_t = std::int_fast64_t; // or "= long long;" or whatever

… then building up to a proper money_t class. That could be your next project! C++ is a strongly-typed language, and I always tell my students that if you get the types right in C++, then everything else because easy. Making a monetary value type isn’t hard, but doing it well will take some work, and teach you a lot about the language along the way.
Code review
#include <stdio.h>

This is not a C++ header. The proper header here would be <cstdio>… but honestly, I can’t see why you need it.
You also don’t use anything from <cmath> or <iomanip> so far as I can tell.
But you do use std::stod()… which is in <string>… which you don’t include. It “works” probably because <string> is being included by something else… but you can’t count on that.
double TaxesDue(double &income);
double HighestRate(double &income);

It is very rare to take function parameters by non-const lvalue reference. There are only a few special cases where that’s normally done.
When you take an argument by a non-const reference, you are telling the people reading your code that you intend to change that value. So when I see TaxesDue(income), I assume income’s value is going to change after the function call. The compiler will also assume that, which can prevent optimizations.
If you’re not going to change the value of the argument, it should be const:
double TaxesDue(double const& income);
double HighestRate(double const& income);

However, double is a fundamental type, so you don’t really need to take it by reference at all. It doesn’t hurt, though.
Also, note that the standard practice in C++ is to put the type modifier with the type:

double &income: this is C style.
double& income: this is C++ style.

std::map<double, std::string> taxRate =

You might want to make this const.
    double income;

    std::cout << "Enter your income: " << std::endl;
    std::cin >> income;

Couple things here. You should put the variable declaration as close as possible to the point of initialization. This is better:
    std::cout << "Enter your income: " << std::endl;

    double income;
    std::cin >> income;

It’s also wise to avoid uninitialized variables. It’s kinda okay if you do what I did just above, and put the double income; RIGHT above the std::cin that actually initializes it. But the way you wrote it, with the double income; several lines away from where it’s initialized… that’s dangerous.
One way to avoid initialized variables is to use the more modern practice of “always auto”:
// double income;       // <- bad, uninitialized
auto income = double{}; // <- better, cannot possibly be uninitialized

Finally, avoid std::endl. I know lots of tutorial code shows to use it, but it’s almost always wrong (or more charitably: unnecessary). Every use of std::endl in your code is wrong; in every case it forces a flush of the output stream unnecessarily.
If you want a newline, don’t use std::endl. Just use \n:
int main()
{
    std::cout << "Enter your income: \n";

    auto income = double{};
    std::cin >> income;

    auto taxesDue = TaxesDue(income);
    std::cout << taxesDue << '\n';
}

TaxesDue() is cool. It could be simplified and made much more efficient, but the problems aren’t actually in the function, they’re in the way the data is structured, as I mentioned in the design review.
The only big problem in TaxesDue() is the magic number 29999. You shouldn’t hard code that in the function. You should use the tax rate map; just get the income lower bound from the lowest tax bracket… which, with your current design, is just std::stod(taxRate.begin()->second). (But if you swapped the map key and value, and used doubles, it would be taxRate.begin()->first.)
So that leaves HighestRate():
double HighestRate(double &income)
{
    /*
    std::map<double, std::string> taxRate =
    {
        {  0.35, "499999" },
        {0.31,"349999"},
        {0.25,"249999"},
        {0.21,"169999"},
        {0.18,"119999"},
        {0.14,"79999"},
        {0.10,"44999"},
        {0.05,"29999"}
    };
    */

    if (income > std::stod(taxRate[0.35]))
    {
        return 0.35;
    }
    if (income > std::stod(taxRate[0.31]))
    {
        return 0.31;
    }

    // ...

There is a lot of unnecessary repetition here. Take the tax rate for example: 0.35 is repeated three times, once in the tax rate map (which is fine), then twice in HighestRate().
Unfortunately, this can’t be simple, because you have the map backwards. If the income were the key, no problem, you just do a normal map lookup with lower_bound() (like I demonstrated in the design review section). But because the income is the value, and the rate is the key, you have to do this the hard way.
What you have to do is iterate through the map, checking the value. Not only that, you also have to make sure you get the largest value. Something like:
double HighestRate(double income)
{
    auto highest_amount = 0.0; // or "= std::numeric_limits<double>::lowest();"
    auto result = 0.0;

    for (auto&& [rate, amount_s] : taxRate)
    {
        auto amount = std::stod(amount_s);

        if ((income > amount) and (amount < highest_amount))
            result = rate;

    }

    return result;
}

Which, as you can see, is pretty complicated. That’s why you really want the income to be the key.


Arhitecture of Angular 7 online shop I created online shop with angular 7 and I am not sure is good architecture. I created 5 modules:

main module
products
shop-cart
core
admin

I have service :

admin.service.ts
products.service.ts
data-storage-service.ts
message-data.service.ts
shop-cart.service.ts

I have module for routing:

app-routing.module.ts
products.service.ts

In main module I include all others module:

@NgModule({
  declarations: [
    AppComponent

  ],
  imports: [
    BrowserModule,
    AppRoutingModule,
    CoreModule,
    AdminModule,
    SharedModule,
    ShopCartModule,
    ProductsModule,
    HttpClientModule,
    FormsModule,
    ModalModule.forRoot(),

    HttpClientInMemoryWebApiModule.forRoot(
      InMemoryDataService, { dataEncapsulation: false }
    )

  ],
  providers: [,
    InMemoryDataService],
  bootstrap: [AppComponent]
})
export class AppModule { }

This is my core module where I include all service:

@NgModule({

  imports: [
    CommonModule,
    AppRoutingModule
  ],
  exports: [
    AppRoutingModule,
    HeaderComponent,
    FooterComponent

  ],
  declarations: [
    HeaderComponent,
    HomeComponent,
    FooterComponent
  ],
  providers:[
    DataStorageServiceService,
    ProductsService,
    ShopCartService,
    AdminSerivice,
    MessageService
  ]
})
export class CoreModule { }

I using data-storage-service.ts for communication with server. In my admin.service.ts and products.service.ts I have methods for  calling method form data-storage-service.ts  and store data in list.
Example:
data-storage-service.ts have method :

 /** GET Category from the server */
  getCategory(): Observable<CategoryModel[]> {
    return this.http.get<CategoryModel[]>(this.cateogryUrl).pipe(

      catchError(this.handleError('getProduct', []))
    )
  }

admin.service.ts have method:

getCategoryFromServer() {
        this.dataStorageServiceServiceta.getCategory().subscribe((category: CategoryModel[]) => {
            this.categoryList = category;
            this.cateogoryChanged.next(this.categoryList.slice())
        })
    }

And in componentadmin.componenet.ts in ngOnInit I have

 ngOnInit() {
    this.admin.getCagegoryFromServer();
  }

Are is this correct ?

It seems to me more logical that the declaration of all services is done in your "main" rather than in "core". It is better to separate as much as possible the dependencies between modules of the same level.

In addition, the module "core" and "shared" are quite close in philosophy, they allow to share basic code in your project. I think that in the future it will be confusing.

Maybe renamed core to "home" or just a part of your application and just use "shared" to share modules.

Then, personally I will pass the definition of routes in the module file.


Extracting some names from a webpage I've written some code in python in combination with selenium to collect photo shoot spaces in different locations in Paris.

My scraper is harvesting the names successfully at this moment. However, is it possible to do this any better way cause it looks repetitive?

Any input to improve this script will be highly appreciated. Here is what I've written:

from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC

driver = webdriver.Chrome()
driver.get("https://www.peerspace.com/")
wait = WebDriverWait(driver, 10)

wait.until(EC.visibility_of_element_located((By.ID, "activity-input"))).click()
wait.until(EC.visibility_of_element_located((By.XPATH, "//div[contains(@class,'ellipsis')]/a"))).click()
wait.until(EC.visibility_of_element_located((By.XPATH, "//div[contains(@class,'col-xs-12')]/li/a[@data-name='Photo Shoot']"))).click()

wait.until(EC.visibility_of_element_located((By.ID, "searchbar-input"))).send_keys("Paris")
wait.until(EC.visibility_of_element_located((By.ID,"searchbar-submit-button"))).click()

for items in wait.until(EC.presence_of_all_elements_located((By.XPATH, "//div[@class='col-xs-12 ']/h6[contains(@class,'title')]"))):
    print(items.text)
driver.quit()

Inputbox to be filled in before pressing the search button are with:

First one : Photo Shoot
Second one : Paris

Overall, it looks clean, but here are some potential improvements:

XPaths, generally, don't handle multi-valued class attributes well - you would have to workaround it with concat to make reliable. A better way would be a CSS selector - here are all 3 XPaths replaced with a relevant CSS selector:

wait.until(EC.visibility_of_element_located((By.CSS_SELECTOR, ".ellipsis > a"))).click()
wait.until(EC.visibility_of_element_located((By.CSS_SELECTOR, "li > a[data-name='Photo Shoot']"))).click()

# items
wait.until(EC.presence_of_all_elements_located((By.CSS_SELECTOR, "h6.title")))

avoid using layout-oriented classes like col-xs-12 in your locators
I would rename items to title
since you are using lengthy expected condition names - what if you would extract them into more concise variable names, e.g.:

from selenium.webdriver.support.expected_conditions import visibility_of_element_located as is_visible
from selenium.webdriver.support.expected_conditions import presence_of_all_elements_located as all_present

it might be a good idea to use try/finally to quit the browser in case the driver fails
you can also submit the search by appending a \n to the search input - this will remove the need to look for the submit button and clicking it:

wait.until(is_visible((By.ID, "searchbar-input"))).send_keys("Paris\n")

All the above mentioned changes applied:

from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support.expected_conditions import visibility_of_element_located as is_visible
from selenium.webdriver.support.expected_conditions import presence_of_all_elements_located as all_present

driver = webdriver.Chrome()

try:
    driver.get("https://www.peerspace.com/")
    driver.maximize_window()

    wait = WebDriverWait(driver, 10)

    wait.until(is_visible((By.ID, "activity-input"))).click()
    wait.until(is_visible((By.CSS_SELECTOR, ".ellipsis > a"))).click()
    wait.until(is_visible((By.CSS_SELECTOR, "li > a[data-name='Photo Shoot']"))).click()

    wait.until(is_visible((By.ID, "searchbar-input"))).send_keys("Paris\n")

    titles = wait.until(all_present((By.CSS_SELECTOR, ".title")))
    for title in titles:
        print(title.text)
finally:
    driver.quit()

We can further improve on following the DRY principle and extract the common wait.until(is_visible(...)) part into a separate function.


Peterson's Algorithm (Mutual Exclusion) A simple algorithm that can be run by two processes to ensure mutual exclusion for one resource.Shared variables are created and initialized before either process starts. The shared variables flag[0] and flag[1] are initialized to FALSE because neither process is yet interested in the critical section. The shared variable turn is set to either 0 or 1 randomly (or it can always be set to say 0)

# include <stdio.h>
# include <unistd.h>
# include <sys/types.h>
# include <sys/mman.h>

    //Shared Global variables to control processes
    static int *flag0;
    static int *flag1;
    static int *turn;

int main(int argc, char const *argv[])
{

    flag0 = mmap(NULL, sizeof *flag0, PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, -1, 0);

    flag1 = mmap(NULL, sizeof *flag1, PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, -1, 0);

    turn = mmap(NULL, sizeof *turn, PROT_READ | PROT_WRITE,
                    MAP_SHARED | MAP_ANONYMOUS, -1, 0);

    *flag0 = 0;
    *flag1 = 0;
    *turn;

    // creates child process
    pid_t pid = fork();

    //prcess 1 (parent):
    if(pid > 0){

        //process ready
        *flag0 = 1;
        // turn selector
        *turn = 1;
        int counter = 0;
        //while to wait for turn change
         while (*flag1 && *turn == 1)
         {
             // busy wait
            printf("Parent waiting: %d sec.\n", counter);
            sleep(1);
            counter++;

         }
         // critical section
         printf("PARENT: critical section\n");
         sleep(5);
         // end of critical section
         *flag0 = 0;

    }

    //process 2 (child):
    if(pid == 0){

        //process ready
        *flag1 = 1;
        // turn selector
        *turn = 0;
        //while to wait for turn change
        int counter = 0;
         while (*flag0 == 1 && *turn == 0)
         {
             // busy wait
            printf("Child waiting: %d sec.\n", counter);
            sleep(1);
            counter++;

         }
         // critical section
         printf("CHILD: Critical section\n");
         sleep(5);
         // end of critical section
         *flag1 = 0;

    }

    wait(); // wait for child
    return 0;
}

Cosmetic issues
# include <foo.h>

This is ok but unusual, don't put a space between the # and include unless you have a good reason to (sometimes used to show some "indentation" with conditional includes).
//Shared Global variables to control processes

Those are only used inside main, so no need to make them global. Better would be to separate the two main parts (parent vs child) in two functions, and pass the required data as arguments to those (possibly creating a nice struct to wrap the up).
*turn;

This does nothing. Remove it. Instead, add some code to check that mmap didn't fail before you proceed.
while (*flag1 && *turn == 1)
while (*flag0 == 1 && *turn == 0)

This isn't consistent, so the reader wonders if there is a semantic difference between the two tests. Better be explicit in both, e.g.:
while (*flag1 == 1 && *turn == 1)
while (*flag0 == 1 && *turn == 0)

Also your indentation is out of whack in the child part (and for the global statics), and you have extraneous empty lines in both parts.
wait(); // wait for child

The child also runs this. Not really a bug, but a bit suspicious. Move that to parent-only code.
Big issue
You have no synchronization. The reads and writes to shared memory all race. So your program might work by sheer luck, but that's not what you want in a demo for concurrent programming. Peterson's algorithm only works if the reads and writes to the flags and turn variables propagate immediately and atomically, and you have no such guarantee here. In particular, the initial writes to turn race with each other, and all the reads of flag1 for the parent race with the writes to flag1 in the child (and vice-versa). This doesn't give you that "turn is set to either 0 or 1 randomly", it gives you undefined behavior.
You'll need to use some form of interprocess synchronization method to achieve correct concurrency control. POSIX named semaphores, or a pthread_mutex with the process-shared attribute set, could work (see the POSIX page for pthread_mutexattr_init for an example).


C++ Read/write (shared) spinlock implementation Here is my implementation of std compatible RWSpinLock using 2 atomics.

I think in cases when spinlock is free, it should take just 1 atomic write operation.

class RWSpinLock{
    std::atomic<int> readers_count{0};
    std::atomic<bool> write_now{false};
public:
    void lock() {
        while (!write_now.exchange(true, std::memory_order_acquire)){
            std::this_thread::yield();
        }

        // wait for readers to exit
        while (readers_count != 0 ){
            std::this_thread::yield();
        }
    }
    void unlock() {
        write_now.store(false, std::memory_order_release);
    }

    void lock_shared() {
        // unique_lock have priority
        while(true) {
            while (write_now) {     // wait for unlock
                std::this_thread::yield();
            }

            readers_count.fetch_add(1, std::memory_order_acquire);

            if (write_now){
                // locked while transaction? Fallback. Go another round
                readers_count.fetch_sub(1, std::memory_order_release);
            } else {
                // all ok
                return;
            }
        }
    }
    void unlock_shared() {
        readers_count.fetch_sub(1, std::memory_order_release);
    }
};

On unique_lock wait for write_now flag, then wait for readers_count.

On shared_lock wait for write_now flag, then increase readers_count. If during incrementation write_now flag becomes true, decrease readers_count and wait again for write_now (this should be relativley rare case).

P.S. I'm not sure though, about memory_order, and overall correctness (but seems fine to me).

I'm fairly certain that you have a one-character typo-bug here:

    while (!write_now.exchange(true, std::memory_order_acquire)){

This should read

    while (write_now.exchange(true, std::memory_order_acquire)) {

— that is, "Put true into the write_now bit; and if it was already true, then wait. Only proceed if the old value was actually false."

What you have with the ! is "Put true into the write_now bit; and if it was already true, then continue (oops!). Otherwise, yield once, and then continue anyway because now it'll be true for sure." ["For sure" here being a relative term. Obviously it won't be true if the old writer managed to finish and release the lock in the time we spent yielding.]

Performance nitpick: I've heard that it is useful to put one cache-line's worth of padding in between your two atomic variables, to eliminate false sharing. Of course if you do that then your shared_spinlock class gets much bigger.

But if you don't do that, then all this fiddling with memory orders is useless, because your few seq_cst accesses to the shared cache line in lock and lock_shared will effectively seq_cst all your accesses in those functions.

As usual, I advise staying away from memory orders unless you're sure that you know what you're doing. That said, I think you're using them correctly here.

            if (write_now){

You might consider making this

            if (write_now.load(std::memory_order_seq_cst)) {

and likewise every other time you load an atomic variable without a memory order. As I said, normally I advise not to use memory orders other than seq_cst at all; but since you are using them, maybe it would be a good idea to mark every single load and store, consistently?

I also suspect that that particular load could be memory_order_acquire maybe, but seriously don't quote me on that. I have no idea.

    // unique_lock have priority

This comment should say lock have priority, or simply writers have priority.

C++ nitpick: Consider marking all of these member functions noexcept.

Functionality suggestion: Consider providing a way for a writer to atomically demote itself to a reader, without releasing the lock (i.e., without allowing some other writer B to sneak in and change the value that A just wrote). This should be possible, I think; and it's definitely not possible for anyone but you, the author of the mutex, to provide this functionality.

I think it's as simple as this:

void unlock_and_lock_shared() {
    readers_count.fetch_add(1, std::memory_order_acquire);
    write_now.store(false, std::memory_order_release);
}

The naming convention comes from Boost.


Project Euler 18/67: Maximum Path Sum The complete problem definition can be summarized as "find the largest sum of for paths from the top to the bottom of a triangle of integers".  I decided to read the triangle in from a file which can be found here.

My solution

#!/usr/bin/python
"""chicks' answer to Euler Project problem #18"""

import sys
import string
import re
import pprint

# read command line
argcount = len(sys.argv)
if argcount <= 1:
    raise ValueError("missing filename on command line")
triangle_filename = sys.argv[1]
print str(argcount) + " arguments: " + triangle_filename

# read file
with open(triangle_filename, "r") as triangle_file:
    lines = triangle_file.readlines()
    print str(len(lines)) + " lines read"

triangle = []
for y in lines:
    y = string.strip(y)
    fields = re.split(r'\s+', y)
    int_fields = []
    for f in fields:
        int_fields.append(int(f))
    triangle.insert(0, int_fields)
    c = len(fields)

pretty = pprint.PrettyPrinter(indent=4)
#pretty.pprint(triangle)

rows = len(triangle) - 1
for z in range(0, rows):
    row = triangle[z]
    pretty.pprint(row)

    entries = len(row) - 1
    for y in range(0, entries):
        a = row[y]
        b = row[y + 1]
        #print "comparing " + str(a) + " and " + str(b)
        adder = 0
        if a >= b:
            adder = a
        else:
            adder = b

        triangle[z + 1][y] += adder

answer = str(triangle[rows][0])
print "ANSWER:" + answer

Desired Focus

I left performance out because I'm more interested in having pythonicly correct and maintainable code than squeezing out a few ms.  I have run this through pylint and fixed everything it suggested.  I am still a beginner at python so I'm presuming there are more pythonic ways to do some of this.

High-level comments:

There are several print statements left in this file which look like they were in for debugging purposes. Maybe useful to you, but means nothing to me when I’m running the file. These should be commented out, or (since you’re using source control) removed entirely.
There are no comments in this file. That makes it quite hard to follow what’s going on – even if this is a simple problem that you understand well, that won’t be the case when you come to re-read this in six months.

Explain why the code is written this way, and how the program structures relate back to the original problem. It makes it much easier to review and improve.
Everything runs at the top-level. You should break some of this down into functions – it will make the code easier to reuse and follow.

A few smaller suggestions:

On line 24, you’re using regexes to split a line on whitespace, but Python already has a string method split() that does this for you.

You can rewrite these few lines as:

for line in lines:
    fields = line.strip().split()

Notice that I’m also calling the strip() method directly on line, and I’ve renamed the loop variable to make it clearer what I’m doing.
On lines 25–7, a common antipattern:

int_fields = []
for f in fields:
    int_fields.append(int(f))

It’s cleaner and more Pythonic to do this with a list comprehension:

int_fields = [int(f) for f in fields]

Note also that you store the value of len(fields) in a variable here – but then never actually use it.
In lines 35-6, you have a common Python antipattern:

for z in range(0, rows):
    row = triangle[z]

It’s always better to iterate over the items directly, i.e. for row in triangle. In this case you’re actually using z further down, so you should use enumerate():

for idx, row in enumerate(triangle):
    # do stuff with idx and row

On lines 40–50, there are several problems:

You don’t need to initialise the variable adder to 0.
You can get its value in a single line:

adder = max(a, b)

The names a and b are not very meaningful, and are only used once. It would be cleaner to write this as:

triangle[z+1][y] += max(row[y], row[y+1])

You should also rename y and z to be more meaningful.

You’re calling range(0, x) in several places. Since it defaults to a start of 0, you can drop the first argument to reduce visual noise: range(x).


LeetCode Reverse Words in a String without using any java library The following problem is from LeetCode:

  Given a string, you need to reverse the order of characters in each
  word within a sentence while still preserving whitespace and initial
  word order.

  Example 1: Input: "Let's take LeetCode contest"

  Output: "s'teL ekat edoCteeL tsetnoc"

The following code is working correctly, but its runtime is 8 ms, which is only faster than 42.44% of Java online submissions. How to make the following code faster?

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int length = s.length();
        int start = 0;
        int end = 0;
        while(start < length){
            while( (end < length) && (s.charAt(end) != ' ')){
                end++;
            }
            doReverse(s, start, end -1, sb);
            start = ++end;
        }
        return sb.toString();
    }

    private void doReverse(String s, int start, int end, StringBuilder sb){
        if(start >0)
            sb.append(" ");
        while(end >= start){
            sb.append(s.charAt(end));
            end--;
        }
    }
}

First: if you look into StringBuilder.reverse() you'll encounter some extra work for some Unicode symbols needing two chars for a symbol (called a surrogate pair), which should not be reversed.

But let's not consider that.

Provide exactly the needed capacity for StringBuilder.
sb.append(' ') is faster than for " ".
end - 1 not needed.

So:

public String reverseWords(String s) {
    int length = s.length();
    if (length <= 1) {
        return s;
    }
    StringBuilder sb = new StringBuilder(length);
    int start = 0;
    int end = 0;
    while (start < length) {
        while (end < length && s.charAt(end) != ' ') {
            ++end;
        }
        doReverse(s, start, end, sb);
        start = ++end;
    }
    return sb.toString();
}

private void doReverse(String s, int start, int end, StringBuilder sb) {
    if (start > 0)
        sb.append(' ');
    while (end > start){
        --end;
        sb.append(s.charAt(end));
    }
}

In general using toCharArray could be faster:

public String reverseWords(String str) {
    char[] s = s.toCharArray();
    int length = s.length;
    if (length <= 1) {
        return s;
    }
    int start = 0;
    int end = 0;
    while (start < length) {
        while (end < length && s.charAt(end) != ' ') {
            ++end;
        }
        doReverse(s, start, end);
        start = ++end;
    }
    return new String(s);
}

private void doReverse(char[] s, int start, int end) {
    while (--end > start){
        char ch = s[start];
        s[start] = s[end];
        s[end] = ch;
        ++start;
    }
}

If you would inline doReverse for extra speed, you would need a copy of the changing parameters.

    // doReverse(char[] s, int start, int end)
    int end2 = end;
    while (--end2 > start){
        char ch = s[start];
        s[start] = s[end2];
        s[end2] = ch;
        ++start;
    }

Now we should be twice as fast (wild guess).


Reading a line from a text file and splitting its contents I have this kind of file structure

MALE:FooBar:32
FEMALE:BarFoo:23

Where I would want to identify the gender and age of person, <Gender>:<Name>:<age>

try{
    BufferedReader in = new BufferedReader(new FileReader("people.ser"));
    String s;

    while((s = in.readLine()) != null){

        String[] var = s.split(":");
             //var[0]=MALE etc etc
        addGender.add(var[0]);
    }

}catch(Exception e){
    e.printStackTrace();
}

Is using a delimiter (like a : in this case) to split string considered a bad practice?
What about using the array from the splitted string to store it in some place?
Are there any alternatives and better file structure?

I don't think that using : is a bad practice but you have to escape it somehow if it occurs inside your data. Anyway, I'd consider using XML or JSON here.

Some notes about the code:

You should close the stream (in a finally block). See Guideline 1-2: Release resources in all cases in Secure Coding Guidelines for the Java Programming Language
The .ser file extension is often used for serialized Java objects. I'd use something else to avoid the possible confusion.
It's a good practice to set the character set when you read a text file. The used FileReader always uses the default charset which could vary from system to system. Consider using InputStreamReader and FileInputStream as the documentation of FileReader says. Here is an example:

FileInputStream fileInputStream = null;
InputStreamReader inputStreamReader = null;
BufferedReader bufferedReader = null;
try {
    fileInputStream = new FileInputStream("people.dat");
    inputStreamReader = new InputStreamReader(fileInputStream, "UTF-8");
    bufferedReader = new BufferedReader(inputStreamReader);

    // use BufferedReader here
} finally {
    IOUtils.closeQuietly(bufferedReader);
    IOUtils.closeQuietly(inputStreamReader);
    IOUtils.closeQuietly(fileInputStream);
}

It uses IOUtils from Apache Commons IO and closes the FileInputStream even if the constructor of InputStreamReader or BufferedReader throws an exception.


Read Twitter direct messages and check messages for links I'm learning Clojure and I'm doing a little thing that reads direct messages from Twitter using twitter-api wrapper. The code doing that is below.

(ns twitterbot.my-twitter
    (:require [twitter.oauth :refer [make-oauth-creds]]
              [twitter.api.restful :refer [direct-messages]]
              [clojure.edn :as edn]
              [clojure.string :as string]))

(defn- load-credentials [filename]
  (edn/read-string (slurp filename)))

(def ^:private credentials-from-file (load-credentials "credentials.edn"))

(def ^:private oauth-credentials
  (make-oauth-creds (credentials-from-file :consumerkey)
                    (credentials-from-file :consumersecret)
                    (credentials-from-file :usertoken)
                    (credentials-from-file :usersecret)))

(defn- has-url? [message]
  (seq (:urls (:entities message))))

(defn- trusted-user? [message]
  (= (credentials-from-file :trusteduser) (:sender_screen_name message)))

(defn- get-url [message]
  (:expanded_url (nth (:urls (:entities message)) 0)))

(defn links-from-direct-messages []
  (let [messages (direct-messages :oauth-creds oauth-credentials)]
    (map get-url (filter has-url? (filter trusted-user? (:body messages))))))

As I'm new to Clojure, I would like to know whether I'm doing things in the correct way and how to do them better. I feel like the coding style and layout is off at least in links-from-direct-messages, but I even though I tried to follow this style guide, I'm not sure how it should be. Also as the data structure from Twitter is quite nested, I wonder how I should be going through them.

Your get-url function could just use get-in:

(defn- get-url [message]
  (get-in message [:entities :urls 0 :expanded_url]))

links-from-direct-messages has quite a lot of nested calls.  When you've got a bunch of nested operations like that it can be nice to re-write them using one of the threading macros (-> and ->>).  These take an input, and then "thread" it through a series of forms as the first (in the case of ->) or last (in the case of ->>) argument.  By doing this, they allow you to rewrite nested calls sequentially.

This is mentioned in the style guide you linked.

In the case of links-from-direct-messages you're calling map and filter, which both accept the collection as their last argument, so you can use ->>:

(defn links-from-direct-messages []
  (->> (direct-messages :oauth-creds oauth-credentials)
       :body
       (filter trusted-user?)
       (filter has-url?)
       (map get-url)))


Accessing nested data properties in Handlebars I am using HandlebarsJS for my templating needs.

I have a nested object:

{
    "amount": {
        "preTax": 15.99,
        "tax": 0.0,
        "currencyCode": "USD",
        "total": 15.99
    }
}

And I have the following template:

{{#amount}}

PreTax is {{preTax}}. Tax is {{tax}}. Currency Code is {{currencyCode}} and total is {{total}}

{{/amount}}

Is this the best practice for accessing nested properties within a property? Like declaring the block for the data property or I need to use with?

Like so:

{{#with amount}}

PreTax is {{preTax}}. Tax is {{tax}}. Currency Code is {{currencyCode}} and total is {{total}}

{{/with}}

I know that both approaches work. And in mustache-js I always used the former approach.

Kevin Decker (one of the contributors Handlebars on Github) answered on the GitHub issue I had created.

  The with form will be slightly faster than the generic block form due
  to some optimizations that can be made for known cases like that. You
  also have the option of making pathed lookups, {{amount.preTax}} for
  example. All work and unless you have extremely hot code I wouldn't
  worry too much about the performance of one vs. the other and leave to
  to which feels stylistically the best for you.

So I guess there is no real winner, unless as Kevin points out, you have an extremely used template then with might be a better option.


Protocol to parse packets I coded this simple protocol but I'm sure that it can be better, this is the process:

Reads incoming data
Waits until payload size can be read
Reads the full message
Checks if there are mixed messages
Reads incoming data again

Code:

private async void ReadPackets(StreamSocket socket, SocketInformation socketInformation)
{
    byte[] data = new byte[BufferSize];

    IInputStream inputStream = socket.InputStream;
    IBuffer buffer = data.AsBuffer();

    while (socketInformation.open)
    {
        IBuffer bytesRead;

        try
        {
            bytesRead = await inputStream.ReadAsync(buffer, BufferSize, InputStreamOptions.Partial);

            if (bytesRead.Length > 0)
            {
                PrintByteArray("Data", data);
            }
        }
        catch (Exception)
        {
            break;
        }

        // Wait for payload size
        if (buffer.Length >= 4)
        {
            int commandType = (int)BitConverter.ToInt16(data, 0);
            int payloadSize = (int)BitConverter.ToInt16(data, 2);
            int packetSize = PacketHeaderSize + payloadSize;

            // Wait for full packet
            if (buffer.Length >= packetSize)
            {
                byte[] packet = new byte[packetSize];
                System.Buffer.BlockCopy(data, 0, packet, 0, packetSize);

                Debug.WriteLine("Packet received.");

                ConcurrentQueue<byte[]> packetReceiveQueue = socketInformation.GetPacketReceiveQueue();

                packetReceiveQueue.Enqueue(packet);

                if (buffer.Length > packetSize)
                {
                    int bufferLength = (int)buffer.Length - packetSize;

                    byte[] newData = new byte[BufferSize];
                    System.Buffer.BlockCopy(data, packetSize, newData, 0, bufferLength);
                    data = newData;

                    buffer.Length = (uint)bufferLength;
                }
            }
        }
    }

    Debug.WriteLine("Socket closed.");
    inputStream.Dispose();
    socket.Dispose();
}

I'm going to preface this with "I didn't actually try this, and the code may not even compile.", but I think you can greatly simplify your code by utilizing the DataReader class instead of parsing everything "by hand".

I'm imagining your routine looking something like this.

using (var dataReader = new Windows.Storage.Streams.DataReader(input.InputStream))
{
    // use network order to read the packet
    dataReader.ByteOrder = Windows.Storage.Streams.ByteOrder.BigEndian;

    //load the 2 byte command and 2 byte payload size into the buffer
    await dataReader.LoadAsync(4);

    short command = dataReader.ReadUint16();
    short payloadSize = dataReader.ReadUint16();

    // now we know how big the payload is, and can load it in full into the buffer.
    await dataReader.LoadAsync(payloadSize);

    byte[] data;
    dataReader.ReadBytes(out data);

    // package the whole shebang into a struct
    var myStruct = new MyStruct(command, payloadSize, data);

    // raise packet received event.
    Invoke?.PacketReceived(this, new PacketReceivedEventArgs(myStruct);

}

There are a couple of benefits to this approach.

Relies on existing abstractions and framework code instead of rolling your own.
We've defined an actual data structure for your packets. Client code can use this higher level abstraction without knowing all the knitty gritty details of how the packet was passed over the network.
Removes the need for the "other" infinite loop on a separate thread that's reading your data. It can listen for the PacketReceived event and react to it and the explicitly passed packet instead. This should lower the risk of race conditions.

One last note, don't use an infinite loop to receive the packets either.
It's much nicer (and user less CPU) to use a System.Threading.Timer to do this kind of work. It has a 15ms resolution but, then again, so does Task.Delay. You're waiting longer than that resolution anyway.


Determining winning line in TicTacToe game I am trying to write code to determine a win in tic-tac-toe game. In this question, I am not focusing on the whole game, I am only interested in the question of how to determine that the game ended with the victory of one of the players. So I made a synthetic example to test different approaches.
My guess is that a winning line on the board can only appear after the current player has made his move. Therefore, it makes no sense to check all the lines on the board. I only consider those that include the last move made. I assume that the board can be of any size (but only square) and the winning line has the same size. Thus, it is one of the rows, or one of the columns, or one of the two diagonals.
After several attempts, I ended up with the code below:
import java.util.List;
import java.util.function.Predicate;

enum Cell {
    X,
    O,
    B // blank cell
}

public class Board {

    private final int size = 3;
    private final Cell[][] board;

    public Board(Cell[][] board) {
        this.board = board;
    }

    private boolean isLineCompleted(Predicate<Integer> predicate) {
        boolean result = true;
        int i = 0;
        while (result && i < size) {
            result = predicate.test(i);
            i++;
        }
        return result;
    }

    public boolean hasWinningLine(int row, int col) {
        if (board[row][col] == Cell.B) return false;

        Cell base = board[row][col];
        List<Predicate<Integer>> checks = List.of(
                i -> board[row][i] == base, //columns
                i -> board[i][col] == base, //rows
                i -> board[i][i] == base,   //top-down diagonal
                i -> board[size - i - 1][i] == base //down-top diagonal
        );

        boolean lineCompleted = false;
        for (var check : checks) {
            if (!lineCompleted) {
                lineCompleted = isLineCompleted(check);
            }
        }

        return lineCompleted;
    }
}

And I wrote some tests that use this code something like this:
Cell[][] xWins = {
    {Cell.X, Cell.O, Cell.X},
    {Cell.O, Cell.X, Cell.O},
    {Cell.X, Cell.B, Cell.B}};

board = new Board(xWins);
AssertTrue(board.hasWinningLine(0, 2));

I have several questions:

How easy is this code to read and understand? How can you improve it in this sense?

I try not to make unnecessary checks. The algorithm should return false as soon as it finds an unsuitable cell. Should I handle the loop like this

for (var check : checks) {
            if (!lineCompleted) {
                lineCompleted = isLineCompleted(check);
            } else break; // That's better?
        }

Is it possible to rewrite this loop using a stream API?

When checking each line, this code can compare the cell to itself. How can i avoid this without complicating the code? Should I even think about it?

I am new to programming and would appreciate any advice that would help me code better.
EDITED:
The predicate checking loop can be rewritten as
return checks.stream()
    .map(this::isLineCompleted)
    .filter(b -> b == true)
    .findFirst()
    .orElse(false);

What are the disadvantages of this approach?

First off, considering the small number of lines and items in a line, your (and my following) optimizations are probably not really worth it. That said, as you have noticed, your loops run through all all items, even when not necessary, and that would be bad in more complex situations.
Generally your code tends to be a bit too complex/verbose. For example, isLineCompleted would be much simpler using a regular for loop and early exit:
private boolean isLineCompleted(Predicate<Integer> predicate) {
    for (int i = 0; i < size; i++) {
         if (predicate.test(i)) {
             return true;
         }
    }
    return false;
}

By extracting the checks loop into a separate method, the same pattern could be used there.
Or Java's Stream has the .anyMatch() method, which simplifies it even more:
return checks.stream().anyMatch(this::isLineCompleted);

Using a IntStream allows isLineCompleted to do simular using .allMatch():
private boolean isLineCompleted(Predicate<Integer> predicate) {
    return IntStream.range(0, size).allMatch(predicate);
}

One final point: The value B in the Cell enum is badly named considering you need to add the comment "blank cell". Call it BLANK instead. Also it would seem more logical to put it first in the enum, where it would have the cardinal value 0. Or you may even want to drop it all together and just use null.


BFA protected phpmyadmin I use a Ubuntu 16.04 Nginx server environment with phpmyadmin (PMA). All my ports are closed besides 22, 25, 80, 443, 9000 (for PHP-FPM).

A common criticism of the good software (PMA) as of 2018, is that it doesn't have good defense from Brute Force Attacks (BFAs). There are different common ways to cope with this and I admit I dislike all of them:

Changing the PMA path to something unintuitive and likely uncomfortable (instead of /var/www/html/phpmyadmin).
Using a permanent IP (what if you're traveling between countries)?
Login through a recognized VPN. What if you don't have a free time to seriously learn VPN basics in some era of your life?
Loging with some kind of authentication certificate. What if don't have one?
Using mod_security for Apache users. What if you don't use Apache?
Using a captcha. What if you login frequently? This might be a bit annoying.
Future PMA versions starting from V 4.8.0 are planned to include support for IPSs like Fail2ban, via uthentication logging.
Future PMA versions starting from V 4.8.0 are also planned to include 2factorAuthentication.

I found myself another way which is personal and comfortable (I don't recommend any company with customers to use this way in the form I'll describe below):

SSH tunneling through port 80 to port 80 via Putty/OpenSSH, and use PMA securely and temporarily for 2 hours in a tmux session (It is extremely unlikely that anyone could BFA PMA with a decent varied password in just 2 hours).

Each time I want to use PMA I run this code:

#!/bin/bash

find  ${drt}/ -iname '*phpmyadmin*' -exec rm -rf {} \;
wget -P ${drt}/ https://www.phpmyadmin.net/downloads/phpMyAdmin-latest-all-languages.zip
find  ${drt}/ -type f -iname '*phpmyadmin*.zip' -exec unzip {} \;
find  ${drt}/ -type d -iname 'phpmyadmin-*' -exec mv {} phpmyadmin \;

sleep 2h

find  ${drt}/ -iname '*phpmyadmin*' -exec rm -rf {} \;
tmux kill-session

I run it this way tmux new-session -d 'bash ~/pma.sh', or with a Bash alias pma.

Note: ${drt} stands for document root, which is in my case /var/www/html and defined in /etc/bash.bashrc.

I'd like to know what you think of the code I've written (especially, do you see any way to shorten it)?.

One potential security issue: what if ${drt} is not set before this is run?  A safety check will be very useful.

As for your wider issue, rather than having to download it every time, would it not be just as effective to remove the permissions on the phpmyadmin directory?  If you set it to 000, then nobody should be able to access it nor its contents.


Is this C++ naive primality test done right? Here's my C++ code:

bool isPrime(double value) {
    if (value == 2)                    // ensure 2 returns true
        return true;
    else if (value <= 1)               // eliminate 1 and all negative numbers
       return false;
    else if (fmod(value, 2) == 0)      // eliminate all even numbers
       return false;

    for (int i = 3; i < sqrt(value); i++) {
        if (fmod(value, i) == 0) {
            return false;
        }
    }

    return true;
}

This function should return true if a number given by value is a prime, and false if a number given by value is a composite. First off, I just want to make sure it works correctly, is fairly efficient (it doesn't have to be the best, but I would like it to be decent for a naive approach), and that the code looks nice.

Thanks!

Is there such a thing as a prime real number?

If not then the function signature should use integer (preferably unsigned as there are no negative primes).

Then you should be able to use % rather than fmod() which I would suspect is a tad faster but, more importantly, easier to read.

Since you have already checked for all even primes:

for (int i = 3; i < sqrt(value); i+=2) {
                            //   ^^^^  No need to increment by 1;
                            //         All evens already checked already so inc by 2
                            //         So just check 3/5/7/9 etc

Here is a link to cool but not obvious optimization (That allows you to avoid checking all multiples of 3 as well as 2): https://codereview.stackexchange.com/a/7342/507


Minimum priority queue using Singly Linked LIst I have written this code for Priority Queue using Singly Linked List. I want to improve this code. Is there any other method to write program for priority queue?

#include <iostream>

template<typename T>
class priorityQueue
{
  struct Node
  {
    int priority;
    T info;
    Node* next;
    Node(T item) : info(item), next(nullptr) {}
  };
  Node* front;

public:
  priorityQueue() : front(nullptr) {}
  ~priorityQueue()
  {
    Node *tmp = nullptr;
    while (front){
      tmp   = front;
      front = front->next;
      delete tmp;
    }
  front = nullptr;
  }

  priorityQueue(const priorityQueue<T> & pq)     = delete;
  priorityQueue& operator=(priorityQueue const&) = delete;

  void insert(T item, int priority)
  {
    Node* tmp;
    Node* node     = new Node(item);
    node->priority = priority;

    if(front == nullptr || priority < front->priority)
    {
      node->next = front;
      front = node;
    }
    else
    {
      tmp = front;
      while(tmp->next != nullptr && tmp->next->priority <= priority)
        tmp = tmp->next;

      node->next  = tmp->next;
      tmp->next   = node;
    }
  }

  void deleteItem(T item)
  {
    Node* find = search(item);
    Node* node = front;
    if(node == find)
      front = node->next;
    else
    {
      while(find != nullptr)
      {
        if(node->next == find)
        {
          node->next = find->next;
          delete find;
          return;
        }
        node = node->next;
      }
    }
  }

  friend std::ostream & operator<<(std::ostream & os, const priorityQueue<T> & pq)
  {
      pq.display(os);
      return os;
  }

private:
  Node *search(T item)
  {
    Node *node = front;
    while(node != nullptr)
    {
    if(node->info == item)
      return node;
    node = node->next;
    }
    std::cerr << "No such element in the list \n";
    return nullptr;
   }

   void display(std::ostream& out = std::cout) const
   {
     Node *node = front;
     out << "\nItem \tPriority \n";
     while(node != nullptr)
     {
       out << node->info << "\t" << node->priority <<"\n";
       node = node->next;
     }
    }
};

int main()
{
  priorityQueue<std::string> pq1;
  pq1.insert("code", 1);
  pq1.insert("sleep", 3);
  pq1.insert("food", 2);
  pq1.insert("date", 4);
  std::cout << pq1;
}

Data structures

Although the name "priority queue" is technically correct,
I find it a bit misleading,
because priority queues are usually implemented using a heap data structure,
with insert and find operations in \$O(\log n)\$ time.
Your implementation is practically a sorted linked list,
with insert and find operations in \$O(n)\$ time.
I'd clarify as "naive priority queue" to avoid confusion.

Memory leak

Watch out for memory leaks.
When deleting the first item,
the deleteItem function simply advances the pointer of front,
without actually deleting the item,
leaving allocated memory behind.

Performance

deleteItem is inefficient,
because it iterates to the node to delete twice:
once to find the node to delete,
and then one more time to actually delete it.


Testing input integers for the palindrome property 3.23 Palindromes

  A palindrome is a number that reads the same forwards
  and backwards, like 12321. Write a
  program that tests input integers for
  the palindrome property.

  Hint: This should not be done with the numbers in
  their input (character) format.

For the task above, I have written the following program.  Rather than converting the number to a string, I recursively divide the number to create a list of individual digits and then compare the digits from outside to in to determine if it's a palindrome.  What do you think of my strategy and of my code in general?  I understand that tail recursion is not guaranteed to work in Common Lisp - should I rewrite this code to use loops instead?

(defun collect-digits (candidate &OPTIONAL (digit-list ()))
  ; make a list out of the digits of the number
  ; example: (= (collect-digits 12321) (1 2 3 2 1)) is true
  (if (< candidate 10)
    (cons candidate digit-list)
    (multiple-value-call
      (lambda (sub-candidate onesdigit)
        (collect-digits sub-candidate (cons onesdigit digit-list)))
      (floor candidate 10))))

(defun reflection-p (candidate-list &OPTIONAL (len (length candidate-list)))
  ; if c-l[first] = c-l[last]
  (and (= (car candidate-list) (car (last candidate-list 1)))
       ; and the list is 3 or smaller ex. (3 1 3), it is a reflection
       (if (<= len 3) t
     ; if longer, keep looking
     (reflection-p (subseq candidate-list 1 (1- len)) (- len 2)))))

(defun palindrome-p (candidate)
    (reflection-p (collect-digits candidate)))

(format t "12321: ~a ~%3456789 ~a ~%" (palindrome-p 12321) (palindrome-p 3456789))

This one is easy! Remember the reverse-digits function? If a number is the same as its reverse, then it's a palindrome.


Am I using pointers correctly? I'm a newb at C++ and I was wondering whether I used pointers correctly and whether it was appropriate to use them in this context.

Any other tips/information would be appreciated.

#include <iostream>

using namespace std;

int euclideanAlgorithm(int *a, int *b);

int main() {
    int x, y, a, b;
    cin >> a;
    cin >> b;
    x = a;
    y = b;
    cout << x / euclideanAlgorithm(&a, &b) * y << endl;
    return 0;
}

int euclideanAlgorithm(int *a, int *b) {
    if (*b == 0) {
        return *a;
    }
    while (*a >= *b) {
        *a -= *b;
    }
    euclideanAlgorithm(b, a);
}

If you come from C and you start using C++, you might be use to have pointers whenever you want a function to be able to update one of its parameter.
In C++, if you want to do so, you can use references which gives you a clearer and slightly safer result. Please refer to the wiki page for more details.

However, I'd like to point out that whenever you compute the lowest common multiple of the two integers, you probably don't want to change the value of this integers.

Thus, I'd expect the following code to do what you are trying to achieve (not tested, not even compiled):

#include <iostream>

using namespace std;

int euclideanAlgorithm(int a, int b);

int main() {
    int a, b;
    cin >> a;
    cin >> b;
    cout << a / euclideanAlgorithm(a, b) * b << endl;
    return 0;
}

int euclideanAlgorithm (int a, int b) {
    return (b == 0) ?
        a :
        euclideanAlgorithm(b, a % b);
}

Then, regarding the style : you can avoid forward declaration by changing the order of the functions. Also, it would probably be better to call you function with a shorter but still more explicit name such as gcd (hiding the implementation details : whether you use Euclid's algorithm or Wk_of_Angmar's algorithm shouldn't make any big difference for the one who is using the function).


Autotools pull in standard build system I have been updating my build tools to optionally us autotools (autoconfig/automake/libtool etc.).

As part of this change I have written a couple of M4 macros. This not being something I have done before, any input appreciated on style or if things can be done better.

AC_DEFUN(
    [AX_FUNC_THOR_BUILD],
    [
        AC_CHECK_PROGS([WGET], [wget], [:])
        if test "$WGET" = :; then
            AC_MSG_ERROR([This package needs wget.])
        fi

        AC_CHECK_PROGS([UNZIP], [unzip], [:])
        if test "$UNZIP" = :; then
            AC_MSG_ERROR([This package needs unzip.])
        fi

        AC_PROG_CXX

        git submodule init
        git submodule update
        pushd build/third
        ./setup "$CXX" || AC_MSG_ERROR([Failed to set up the test utilities], [1])
        popd
    ]
)

Should I pull the setup script into this macro or leave it separate?

#!/bin/bash
set -e
CXX=$1
#
# Change this as required to point at the root of ThorsAnvil code
ROOT=$(pwd)
THORSANVIL_ROOT=$(dirname ${ROOT})
if [[ -e ${THORSANVIL_ROOT}/lib/libgtest.a ]]; then
    exit 0
fi

echo "Un-archiving google test"
GTEST_ARCHIEVE=`ls gtest-*.zip 2>/dev/null | tail -n 1`
if [[ ${GTEST_ARCHIEVE} == "" ]]; then
    echo "Retrieving: gtest-1.7.0"
    wget http://googletest.googlecode.com/files/gtest-1.7.0.zip
    GTEST_ARCHIEVE=`ls gtest-*.zip 2>/dev/null | tail -n 1`
fi

GTEST_ARCHIEVE_DIR=${GTEST_ARCHIEVE%.zip}
if [[ ! -d ${GTEST_ARCHIEVE_DIR} ]]; then
    unzip ${GTEST_ARCHIEVE}
fi

echo "Building google test"
GTEST_DIR=${ROOT}/${GTEST_ARCHIEVE_DIR}
pushd ${GTEST_DIR}
${CXX} -I${GTEST_DIR}/include -I${GTEST_DIR} -c ${GTEST_DIR}/src/gtest-all.cc
${CXX} -I${GTEST_DIR}/include -I${GTEST_DIR} -c ${GTEST_DIR}/src/gtest_main.cc
ar -rv libgtest.a gtest-all.o gtest_main.o
popd

echo "Installing google test"
pushd ${THORSANVIL_ROOT}
mkdir -p bin include include3rd lib
rm -f lib/libgtest.*
cp ${GTEST_DIR}/libgtest.a lib/
rm -f include3rd/gtest
ln -s ${GTEST_DIR}/include/gtest include3rd/gtest
popd

The main M4 file

  Should I pull the setup script into this macros or leave it separate?

I think it's good you separated.
For the same reason that it's good to decompose a large function doing many things to smaller functions.

If it doesn't make sense to ever run the setup script independently,
then an alternative is to put it in a function,
if that's possible in M4.

This may be a matter of taste,
I avoid pushd and popd in shell scripts for fear that I might forget to do popd, or that later I delete one of them by mistake.
An alternative is a (...) subshell, for example:

    (
        cd build/third
        ./setup "$CXX" || AC_MSG_ERROR([Failed to set up the test utilities], [1])
    )

The subshell has its own environment, its own $PWD,
so directory changes will not affect the encapsulating shell process.
Forgetting one of the parens in (...) is impossible as that would be a blatant syntax error.

The setup script

It would be better to give the setup script a .sh extension to indicate it's a shell script.

Some variables containing filenames are not carefully quoted, for example:

THORSANVIL_ROOT=$(dirname ${ROOT})

This will break down if the path contains spaces.

Maybe on your computer you have the good sense to avoid spaces in paths of your dev stuff,
but others cloning your project might not,
and annoy you with dumb questions when something doesn't work.
It's better to quote such variables.
Paste your script on shellcheck.net and review all similar cases.

if [[ -e ${THORSANVIL_ROOT}/lib/libgtest.a ]]; then
    exit 0
fi

Instead of -e, which gives true for directories too,
I'd use -f that more explicitly requires regular files.
(It will match symlinks pointing to regular files too.)
Sure, it's unlikely that a .a file would be a directory,
but if that ever happens, it will really suck.

GTEST_ARCHIEVE=`ls gtest-*.zip 2>/dev/null | tail -n 1`
if [[ ${GTEST_ARCHIEVE} == "" ]]; then
    echo "Retrieving: gtest-1.7.0"
    wget http://googletest.googlecode.com/files/gtest-1.7.0.zip
    GTEST_ARCHIEVE=`ls gtest-*.zip 2>/dev/null | tail -n 1`
fi

Always prefer the modern $(...) subshells instead of the old and troublesome ``...`` style.

Also, since you're duplicating that ls ... command,
it would be better to put that in a helper function.
Even though it's just one line,
it's not exactly trivial,
and copy-pasted code very often comes back to haunt you.

Btw I guess you meant to name that variable GTEST_ARCHIVE instead of GTEST_ARCHIEVE.

As in the other script, I would wrap the pushd/popd in (...) instead.


Efficient Binary Search My implementation:

Array.prototype.binarySearchFast = function(search) {

  var size = this.length,
      high = size -1,
      low = 0;

  while (high > low) {

    if (this[low] === search) return low;
    else if (this[high] === search) return high;

    target = (((search - this[low]) / (this[high] - this[low])) * (high - low)) >>> 0;

    if (this[target] === search) return target;
    else if (search > this[target]) low = target + 1, high--;
    else high = target - 1, low++;
  }

  return -1;
};

Normal Implementation:

Array.prototype.binarySearch = function(find) {
  var low = 0, high = this.length - 1,
      i, comparison;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    if (this[i] < find) { low = i + 1; continue; };
    if (this[i] > find) { high = i - 1; continue; };
    return i;
  }
  return null;
};

The difference being my implementation makes a guess at the index of the value based on the values at the start and end positions instead of just going straight to the middle value each time.

I wondered if anyone could think of any case scenarios where this would be slower than the original implementation.

UPDATE:
Sorry for the bad examples. I have now made them a little easier to understand and have setup some tests on jsPerf. See here:

http://jsperf.com/binary-search-2

I'm seeing about 75% improvement by using my method.

My advice is to not mess about with something that's been well and truly tested :-)

No, not really: if you find an algorithm that's better then, by all means, use it. However, in this case, for general data, this isn't going to be an improvement.

The power of binary search, and other O(log N) type algorithms, lies in the fact that you dispose of half the remaining search space with each iteration. In other words, if the initial search space (array size) was 1000, the first iteration removes 500 of them.

Any change to the "midpoint" (the divider between what you're keeping in the search space and what you're disposing of) that you select during an iteration has the potential to improve or degrade the performance. For example, putting the midpoint at 25% has the potential to reduce the search space even faster (if you're right) or slower (if you're wrong).

Now, if you know of some property of the data, you can use that to your advantage to improve an algorithm. In fact, it's the "extra" knowledge about your list (the fact that it's sorted) that allows you to optimise what would normally be a sequential search into a binary one.

So it all comes down to how good your extra information is. In this case, the values of the two end nodes alone are not really indicative of where the midpoint should be. You only have to look at the list:

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 500, 1000]

to see this in action.

If you were looking for 500 in that list, you might decide that, based on the first and last elements being 1 and 1000, it would be in the middle somewhere, which is clearly not the case.

Similarly, if you were looking for 14, you might first check elements around the 1.4% mark (14/1000) which would probably be the first element, despite the fact it's right up at the other end.

Of course, that's not to say that other extra information would not help. If you knew that the data was fairly evenly distributed over the range, then your improvement may be worth it.

You also need to be aware that it's usually only going to be important with large data inputs, so it may not necessarily be worth it even if it turns out to be much better. Even bubble sort is blindingly fast for 100 elements :-)


Balanced Binary Tree There are some things that smell about this code, for instance multiple checking, length both returning value and changing some other variable. But I can't for the moment figure how to make it nicer, or if that's even possible. Converting it to stack-based solution seems to be making it a bit too-complicated.

Please provide a review of this code, what do you think could be improved, if possible, both in terms of readability and performance or possible problems.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    boolean isBalanced = true;

    public boolean isBalanced(TreeNode root) {
        length(root);
        return isBalanced;
    }

    public int length(TreeNode a) {
        if (a == null) {
            return 0;
        }
        if (isBalanced == false) {
            return 0;
        }
        int x = length(a.left);
        if (isBalanced == false) {
            return 0;
        }
        int y = length(a.right);
        if (isBalanced == false) {
            return 0;
        }
        if (Math.abs(x - y) > 1) {
            isBalanced = false;
            return 0;
        }
        return Math.max(x, y) + 1;
    }
}

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

What really hurts this code is that the length method wants to return two things at once: the branch depth, and a global isBalanced status.

To do that, the author returned branch depth directly, and isBalanced as a global variable. I'm all against global variables, but I must admit this does work. I think there's a useless line of code, though:

public int length(TreeNode a) {
    if (a == null) {
        return 0;
    }
    if (isBalanced == false) { // <-- Useless
        return 0;              // <-- Useless
    }                          // <-- Useless

Otherwise, it's not all too bad. It uses a magic value to early return from recursion.

Another possibility is to throw a UnbalancedException - don't kill me right away, throwing exceptions upon rencountering abnormal situations is not evil! If it's not happening too often, it's quite reasonable, and makes for a much cleaner design:

public class Solution {
    public boolean isBalanced(TreeNode root) {
        try{
            length(root);
            return true;
        } catch(UnbalancedException unbalanced){
            return false;
        }
    }

    public int length(TreeNode a) throws UnbalancedException{
        if (a == null) {
            return 0;
        }
        int x = length(a.left);
        int y = length(a.right);
        if (Math.abs(x - y) > 1) {
            throw new UnbalancedException();
        }
        return Math.max(x, y) + 1;
    }
}

With this design, you've gained a length method that actually works!

The most JAVA possibility - suposedly cleaner, but that I like the least - is to create a ad-hoc Response object like a BalancedStatus:

public class BalancedStatus {
     private final boolean isBalanced;
     private int depth;
     // Getters, and constructors here
}

And :

public class Solution {
    public boolean isBalanced(TreeNode root) {
        BalancedStatus rootStatus = length(root);
        return rootStatus.isBalanced();
    }
    public BalancedStatus length(TreeNode a) {
        if (a == null) {
            return new BalancedStatus();
        }
        BalancedStatus x = length(a.left);
        if(!x.isBalanced()){
             return new BalancedStatus(false);
        }
        BalancedStatus y = length(a.right);
        if(!y.isBalanced()){
             return new BalancedStatus(false);
        }
        if (Math.abs(x - y) > 1) {
             return new BalancedStatus(false);
        }
        return new BalancedStatus(Math.max(x, y) + 1);
    }
}

But I don't like this because it instantiates two Objects per recursion level...

Finally, we could axe the recursion and use iteration instead, but since this is a branching recursion we'd need a List (Queue?) to track the progress.
Pros:

No recursion (no stack overflow etc.)
Easy early exit (just return)

Cons:

Requires to setup a List of nodes to do
Requires to be able to link back from node to parent (Map?) to propagate depth


Reversing the lines of a file I am trying to reverse the lines of a file by reading the file through an array.

Is there a more efficient and quicker way of achieving this?

import java.util.Scanner;
import java.io.*;

class ReverseNumbers {

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

        File file = new File("numbers.txt");
        Scanner Scan = new Scanner(file);

        int numoflines = 0;
        while(Scan.hasNextLine()) {
            Scan.nextLine();
            numoflines++;
        }
        Scan.close();
        Scan = new Scanner(file);

        int buffer[] = new int[numoflines]; //size

        for(int i=0; i<buffer.length; i++) {
            buffer[i] = Scan.nextInt();
        }

        for(int i=buffer.length-1; i>=0; i--) {
            int reverse = buffer[i];
            System.out.println(reverse);
        }
    }
}

The posted code does the following:

Read all lines, just for counting
Create an array with the right size
Read all lines again, this time for storing
Print all lines in reverse order

It's wasteful to read a file completely just to find the number of lines, and then need to read the file again to store the content.
It would be better to store the lines in a data structure that can grow its capacity as needed, to eliminate the need to know the number of lines in advance. That is, use any List implementation.

Possible bug

The description doesn't mention that there is precisely one integer per line in the input.
It must be the case, otherwise this code may not work well:

for(int i=0; i<buffer.length; i++) {
    buffer[i] = Scan.nextInt();
}

That is, if there are multiple numbers per line, then you will not read the entire file,
only the first \$N\$ numbers.
Similarly, if there are empty lines, then there may not be enough numbers,
and then the .nextInt call will throw a NoSuchElementException.

The thing is, since there program doesn't use any integer operation,
only read and print,
there's no point reading integers.
Keep in mind that when you read integers,
you also incur a parsing step.
It would make more sense to read the lines as strings,
it would be simpler, and it seems that's all you really need anyway.

Suggested implementation

Here's an alternative, more efficient solution,
that also simplifies the reversing logic using a LinkedList, with a descendingIterator:

LinkedList<String> lines = new LinkedList<>();
while (scanner.hasNextLine()) {
    lines.add(scanner.nextLine());
}
scanner.close();

Iterator<String> iterator = lines.descendingIterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}


Mergesort through recursion Could someone kindly have a look at the recursive merge sort below and let me know if there are any improvements? I'm mainly interested in either improving the code speed or making the code shorter.

def mergesort(alist):
    if len(alist) > 1:
        mid = len(alist)/2
        left = alist[:mid]
        right = alist[mid:]

        mergesort(left)
        mergesort(right)

        i = 0
        j = 0
        k = 0

        while i < len(left) and j < len(right):
            if left[i] > right[j]:
                alist[k] = right[j]
                j = j + 1

            elif left[i] < right[j]:
                alist[k] = left[i]
                i = i + 1

            k = k + 1

        while i < len(left):
            alist[k] = left[i]
            i = i + 1
            k = k + 1

        while j < len(right):
            alist[k] = right[j]
            j = j + 1
            k = k + 1

A = [4, 3, 1, 2, 6, 8, 10]

mergesort(A)
print(A)

Slicing a list makes a copy of it, e.g.:

>>> a = list(range(10))
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> b = a[:5]
>>> b
[0, 1, 2, 3, 4]
>>> b[2] = 0
>>> b
[0, 1, 0, 3, 4]
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

So each of your recursive calls is creating a copy of half of the list before passing it down, which is not the best use of time. I think it is a much better approach to pass around the whole list, which simply passes a reference to it around, no copies involved, and a couple of indices marking the range you want to work on:

def mergesort(alist, lo=0, hi=None):
    if hi is None:
        hi = len(alist)
    if hi - lo <= 1:
        return
    mid = lo + (hi - lo) // 2  # mid = (lo + hi) // 2 can overflow
    mergesort(alist, lo=lo, hi=mid)
    mergesort(alist, lo=mid, hi=hi)
    # Copy out the left side, which may be overwritten by the merge
    temp = alist[lo:mid]
    read_left = 0  # index into temp, copy of left subarray
    read_right = mid  # index into alist's right subarray
    write = lo  # index into alist
    while read_left < len(temp) and read_right < hi:
        if alist[read_right] < temp[read_left]:
            alist[write] = alist[read_right]
            read_right += 1
        else:
            alist[write] = temp[read_left]
            read_left += 1
        write += 1
    # Copy any unprocessed items in temp back to alist
    alist[write:write+len(temp)-read_left] = temp[read_left:]
    # Any unprocessed items in right subarray are already in place!
    # Nothing returned: the list gets sorted in-place


How to sort two array of objects using Underscore.js? I am sorting 2 arrays of object like this, but I know this is very bad.  Any good approach, like using each method like so? ( I tried, but using each, I am unable to return the object )

var O1 = [{'name':'one'}, {'name':'two'}, {'name':'three'}, {'name':'four'}, {'name':'five'}, {'name':'six'}];
var O2 = [{'name':'rat'}, {'name':'cat'}, {'name':'lion'}, {'name':'tiger'}, {'name':'dog'}, {'name':'horse'}];

var sorted1 = _.sortBy(O1, function(item){
    return item.name;
})

var sorted2 = _.sortBy(O2, function(item){
    return item.name;
})

console.log(sorted1, sorted2);

Demo

Or you can do it without a function at all:

sortBy   _.sortBy(list, iterator, [context])
Returns a (stably) sorted copy of list, ranked in ascending order by the results of running each value through iterator.  Iterator may also be the string name of the property to sort by (eg. length).

var sorted1 = _.sortBy(O1, 'name'),
    sorted2 = _.sortBy(O2, 'name');