Merge sort implementation using iterators Here is my first try to implement merge sort using iterators -

#include <algorithm>
#include <iterator>
#include <vector>

namespace base {
namespace merge {

    template <typename Iterator, typename Compare>
    void mergeBack(Iterator begin, Iterator mid, Iterator end, Compare comp)
    {
        typedef typename std::iterator_traits<Iterator>::value_type ElemType;
        std::vector<ElemType> left, right;

        left.reserve(mid - begin);
        right.reserve(end - mid);

        std::copy(begin, mid, std::back_inserter(left));
        std::copy(mid, end, std::back_inserter(right));

        size_t j = 0, k = 0;
        auto i = begin;
        for (; i != end && j < left.size() && k < right.size(); ++i) {
            *i = comp(left[j], right[k]) ? left[j++] : right[k++];
        }

        while (j < left.size()) {
            *(i++) = left[j++];
        }

        while (k < right.size()) {
            *(i++) = right[k++];
        }
    }

    template <typename Iterator, typename Compare = std::less<>>
    void sort(Iterator begin, Iterator end, Compare comp = Compare())
    {
        if (end - begin > 1) {
            const auto middle = (end - begin) / 2;
            merge::sort(begin, begin + middle, comp);
            merge::sort(begin + middle, end, comp);
            mergeBack(begin, begin + middle, end, comp);
        }
    }
}
}

I'm open to advice/suggestions about the implementation and would love to hear how I could make it better.

You should prefer to move values whenever possible.

std::move(begin, mid, std::back_inserter(left));
std::move(mid, end, std::back_inserter(right));

size_t j = 0, k = 0;
auto i = begin;

for (; i != end && j < left.size() && k < right.size(); ++i) {
    *i = std::move(comp(left[j], right[k]) ? left[j++] : right[k++]);
}

while (j < left.size()) {
    *(i++) = std::move(left[j++]);
}

while (k < right.size()) {
    *(i++) = std::move(right[k++]);
}

Every call of mergeBack will end up allocating 2 new buffers. You can avoid that by preallocating the secondary buffer and flip flopping between them but that is tricky to do in the recursive version. Which is why I prefer the iterative version that goes bottom up.


Applying a formula to 2D numpy arrays row-wise The user has two 2D input arrays A and B, and a given matrix S. He wants to apply a
complicated formula to these arrays row-wise to get C. Something like: $$C_i = f(S, A_i, B_i)$$
where f is some complicated function, implemented by the user. That is, the user wants to supply his complicated formula in terms of the row vectors, and whatever additional data is necessary for that formula. The implementation of the formula must be a function.

For the sake of this example only, the complicated formula will be
the dot product, and the "additional data" for the formula will be the
identity matrix. The real application is a lot more complicated.

My question is: How can I express the line

 C = np.fromiter(map(partial(users_formula, S), A, B), dtype=np.float64)

in a cleaner way in Numpy? Speed or memory consumption is not a major concern, but code readability is. I suspect that there is a better way to do it in Numpy.

from __future__ import print_function
from functools import partial
import numpy as np

def main():
    # Some dummy data just for testing purposes
    A = np.array([[-0.486978,  0.810468,  0.325568],
                  [-0.640856,  0.640856,  0.422618],
                  [-0.698328,  0.628777,  0.34202 ],
                  [-0.607665,  0.651641,  0.45399 ]])
    B = np.array([[ 0.075083,  0.41022 , -0.908891],
                  [-0.025583,  0.532392, -0.846111],
                  [ 0.014998,  0.490579, -0.871268],
                  [-0.231477,  0.401497, -0.886125]])
    S = np.identity(3)
    #---------------------------------------------------------------
    # The problematic line is below. What is the proper way to
    # express this in Numpy?
    C = np.fromiter(map(partial(users_formula, S), A, B), dtype=np.float64)
    assert np.allclose(C, 0.0, atol=1.0e-6), C
    print('Done!')

def users_formula(S, a, b):
    # a == A_i, b == B_i
    # In the real application, the user gives his complicated
    # formula here. The matrix S stays the same, the A_i
    # and B_i are the row vectors of A and B, respectively.
    # We have no control over the implementation of the formula,
    # but it must be a function.
    return np.dot(a, np.dot(S, b))

if __name__ == '__main__':
    main()

Here's some alternatives using your arrays:

Yours, for reference:

In [19]: np.fromiter(map(partial(users_formula, S), A, B), dtype=np.float64)Out[19]:
array([  5.88698000e-07,  -1.11998000e-07,   1.87179000e-07,
         4.89032000e-07])

List comprehension with row indexing

In [20]: np.array([users_formula(S,A[i],B[i]) for i in range(A.shape[0])])
Out[20]:
array([  5.88698000e-07,  -1.11998000e-07,   1.87179000e-07,
         4.89032000e-07])

Make the row indexing a bit more explicit - longer, but clearer

In [21]: np.array([users_formula(S,A[i,:],B[i,:]) for i in range(A.shape[0])])
Out[21]:
array([  5.88698000e-07,  -1.11998000e-07,   1.87179000e-07,
         4.89032000e-07])

Replace indexing with good old Python zip (this my personal favorite for readability).

In [22]: np.array([users_formula(S,a,b) for a,b in zip(A,B)])
Out[22]:
array([  5.88698000e-07,  -1.11998000e-07,   1.87179000e-07,
         4.89032000e-07])

Even though I'm generally familiar with apply_along_axis I'm having problems with its application.  Even if I get it right, that's not a good sign.  It may be the most compact, but it clearly won't be the clearest.

In [23]: np.apply_along_axis(partial(users_formula,S),0,A,B)------------------    ...
ValueError: matrices are not aligned

There some other functions to explore, such as np.vectorize and np.frompyfunc.  But they'll have the same problem - I'd have to study the docs and experiment to get a working example.

The problem with apply_along_axis is that it's designed to iterate over one array, not several.

apply_along_axis(func1d,axis,arr,*args)
apply_along_axis(...,0, A, B)

This would iterate on the rows of A, but use the whole B.  S could be passed as *args.  But to use both A and B, I'd have to concatenate them into one array, and then change your function to handle 'rows' from that. MESSY.

Internally, apply_along_axis is just a generalization of:

outarray=np.empty(A.shape[0],A.dtype)
for i in range(A.shape[0]):
    outarray[i] = users_formula(S,A[i,:],B[i,:])


Find the largest sum of the GCD and LCM of two numbers in a range The program is supposed to get one number n as input, and output the max value of gcd + lcm of two numbers that range from 1 to n.

For example, if n == 3, the answer is 7 because gcd(3,2) == 1 and lcm(3,2) == 6.

The issue is that the code works really slowly and the double loop makes it so numbers above basically 1000 take forever to run. How do I make it run faster?

#include <iostream>

using namespace std;

int main()
{
    int n;

    cin >> n;

    int highest_value = 0,equation;
    int gcd,smaller;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i > j){smaller=j;}
            else{smaller=i;}

            for(int y = 1; y <= smaller; y++)
            {
                if(i%y==0 && j%y==0) gcd = y;
            }
            equation = gcd+((i*j)/gcd);
                if(equation > highest_value) highest_value = equation;
        }
    }
    cout << highest_value;

    return 0;
}

I decided to take a stab at this, and I ended up reducing your algorithm down to one line (tested for equality with the original algorithm from n = [0,500] :

highest_value = (n > 2) ? ( 1+n*(n-1) ) : ( 2*n );

If you would like to see the steps I took, then please see my steps below...

Let's start by removing the comparison in the 2nd loop by splitting up the 2nd loop into 2 parts:

for(int i = 1; i <= n; i++) {
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
    // smaller = i
    for(int j = i; j <= n; j++) {
        for(int y = 1; y <= i/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

Now let's extract the simple case where i == j by adding

// i == j
// gcd = i;
// equation = gcd+((i*j)/gcd);
// equation = i + (i*i)/i
equation = 2 * i;
if(equation > highest_value) highest_value = equation;

and changing the limits of the second loop to exclude i == j

for(int j = i+1; j <= n; j++) {

we now have

for(int i = 1; i <= n; i++) {
    // i == j
    equation = 2 * i;
    if(equation > highest_value) highest_value = equation;
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
    // smaller = i
    for(int j = i+1; j <= n; j++) {
        for(int y = 1; y <= i/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

we can observe that the second loop checks the same values (just mirrored with i and j), so we can get rid of the second loop entirely giving us:

for(int i = 1; i <= n; i++) {
    // i == j
    equation = 2 * i;
    if(equation > highest_value) highest_value = equation;
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j/*smaller*/; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

we can also observe that the maximum value for the i == j case will be where i == n, so we can get rid of that section and start our highest_value at 2*n :

int highest_value = 2*n;
int equation, gcd;

for(int i = 1; i <= n; i++) {
    // smaller = j
    for(int j = 1; j < i; j++) {
        for(int y = 1; y <= j; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd); //since lcm(x,y) = (x*y)/gcd(x,y)
        if(equation > highest_value) highest_value = equation;
    }
}

return highest_value;

Now let's look at the inner-most loop

for(int y = 1; y <= j; y++) {
    if(i%y==0 && j%y==0) gcd = y;
}

we know that y == 1 is a simple case where gcd = 1 and equation = 1 + i*j, so we can extract that from the loop:

equation = 1 + i*j;
if(equation > highest_value) highest_value = equation;

for(int y = 2; y <= j; y++) {
    if(i%y==0 && j%y==0) gcd = y;
}

let's also notice that the equation 1 + i*j has a maximum consistent with the maximum values of i and j where i = n and j = n-1 which gives us 1 + n*(n-1) or 1 + n*n - n. Now we can move this equation to the beginning of the function and check it against our initial highest_value of 2 * n. Don't forget to exclude the case where n == 0, because it is impossible to achieve a value of i or j == 0 inside the loop.

int highest_value = 2*n;
int gcd, equation;

if ( n > 0 ) {
    equation = 1 + n*(n-1);
    if(equation > highest_value) highest_value = equation;
}

We can notice that our new equation exceed our initial equation at a value of n >= 3

int highest_value, gcd, equation;

if ( n > 2 ) {
    highest_value = 1 + n*(n-1);
} else {
    highest_value = 2 * n;
}

We can notice that i == 1 and j == 1 will never be divisible by the initial value of y, so we can start them at 2. Then notice that the j loop never happens if i == 2, so we can start i at 3.

int highest_value, gcd, equation;

if ( n > 2 ) {
    highest_value = 1 + n*(n-1);
} else {
    highest_value = 2 * n;
}

for(int i = 3; i <= n; i++) {
    for(int j = 2; j < i; j++) {
        for(int y = 2; y <= j; y++) {
            if(i%y==0 && j%y==0) gcd = y;
        }
        equation = gcd+((i*j)/gcd);
        if(equation > highest_value) highest_value = equation;

    }
}

return highest_value;

Finally... We can notice a pattern where we can take this approach indefinitely where we can continue to factor our i and j, so I noticed a pattern where the initial highest_value is true for every i and j, so the final function is :

highest_value = (n > 2) ? ( 1+n*(n-1) ) : ( 2*n );


Kattis 'Driver's Dilemma' The full problem description can be found here, a slightly trimmed version below:

A car driver is travelling on an isolated road (no gas stations, houses, or cell phone coverage). The driver glances at their fuel gauge: there is exactly half a tank left. They stop and see that the fuel tank is leaking.
The driver cannot repair the leak. Using a container of known volume and a wristwatch, they measure the rate of fuel loss at  gallons per hour. They empty the container back into the tank.
The driver checks the manual and sees the fuel tank capacity is  gallons. There's also a table resembling the one below, showing declining fuel efficiency in miles per gallon (MPG) as driving speed in miles per hour (MPH) increases. They must trade one against the other in an attempt to reach the nearest gas station  miles away before nightfall.
Speed (MPH)  Fuel Efficiency (MPG)
         55                   22.0
         60                   21.3
         65                   20.2
         70                   18.3
         75                   16.9
         80                   15.8

The driver assumes manuals authors are experts, and has an aversion to interpolation (and extrapolation), they decide to drive at exactly one of the 6 speeds listed. That way, the distance travelled before running out of gas will be 100% predictable.
Can the driver reach the gas station before running out of fuel? If so, what is the maximum speed they can drive?

Examples:

Input
Output

18 0.5 16055 22.060 21.365 20.270 18.375 16.980 15.8
YES 60

16 0.07 16055 20.4960 18.4065 17.7870 17.1075 16.3880 15.60
NO

main.rs
use std::io::{self, BufRead};

#[derive(Debug)]
struct Car {
    capacity: f32,
    rate_of_loss: f32,
    remaining: f32,
    efficiancy: Vec<MPG>,
}

#[derive(Debug)]
struct MPG {
    mph: f32,
    mpg: f32,
}

impl Car {
    fn in_range(&self, distance: f32) -> f32 {
        let mut res: f32 = -1.0;
        let volume = self.capacity * self.remaining;
        for entry in &self.efficiancy {
            let time = distance / entry.mph;
            let total_loss = time * self.rate_of_loss;
            let max_distance = (volume - total_loss) * entry.mpg;
            if max_distance > distance {
                res = res.max(entry.mph);
            }
        }
        res
    }
}

fn main() {
    let remaining: f32 = 0.5;
    let mut c: f32 = 0.0;
    let mut x: f32 = 0.0;
    let mut m: f32 = 0.0;
    let mut efficiancies: Vec<MPG> = Vec::new();

    let stdin = io::stdin();
    for (i, line) in stdin.lock().lines().map(|x| x.unwrap()).enumerate() {
        let nums: Vec<f32> = line
            .split_whitespace()
            .map(|n| n.parse().unwrap())
            .collect();
        if i == 0 {
            c = nums[0];
            x = nums[1];
            m = nums[2];
        } else {
            efficiancies.push(MPG {
                mph: nums[0],
                mpg: nums[1],
            });
        }
    }
    let car = Car {
        capacity: c,
        rate_of_loss: x,
        remaining: remaining,
        efficiancy: efficiancies,
    };
    let y = car.in_range(m);
    if y > 0.0 {
        println!("YES {:.0}", y);
    } else {
        println!("NO");
    }
}

I did initially write a smaller version that did everything in the main function, but I wanted to try using struct and impl. I primarily use python, so I'm mostly looking for pointers on style/idiomatic rust and intermediate/advanced topics that I could try out. Any advice is welcome :)

Design
I applaud the goal of using struct and impl, but this is a good example of where object-oriented style can go wrong: it is not clear exactly what functionality Car and MPG encapsulate. Rather, these are just structs that carry some relevant data for the in_range function, but they do not seem to lead to a meaningful "separation of concerns" or make the code easier to understand as written.
For example, what is an MPG object? It carries a pair of a miles-per-hour and a miles-per-gallon, but why are these particular pieces of data grouped together and not with the other pieces of data? For Car, the primary problem is that it carries a lot of data but not enough functionality. If I were to reuse or extend your code, I would not be sure what to use a Car for, and whether and how I should extend Car with additional methods.
To improve your code, I would start by getting rid of MPG. Then, I would settle on a simple abstraction of a car that seems generalizable. We could start with this: a car is something that drives, given a certain amount of fuel, a fuel leak rate, a certain speed, and a certain fuel efficiency. Note that we no longer have efficiancy: Vec<MPG> as part of the car --- that muddles the meaning of a car, since it can then only drive at certain rates.
We might get something like the following design:
struct Car {
    fuel_remaining: f32, // Gallons
    fuel_leak_rate: f32, // Gallons/hour
    speed: f32, // Miles/hour
    efficiency: f32, // Miles/gallon
}
impl Car {
    fn new(
        fuel_remaining: f32,
        fuel_leak_rate: f32,
        speed: f32,
        efficiency: f32,
    ) -> Self {
        assert!(fuel_remaining >= 0);
        assert!(fuel_leak_rate >= 0);
        assert!(speed > 0);
        assert!(efficiency > 0);
        Self { fuel_remaining, fuel_leak_rate, speed, efficiency }
    }
    fn can_drive(&self, distance: f32) -> bool {
        let time = distance / self.speed;
        let fuel_req = time * self.fuel_leak_rate + distance / self.efficiency;
        fuel_req < self.fuel_remaining
    }
}

What I want to stress here is that the design is extensible:

First, we've articulated the requirements on our struct in the new function: which arguments must be greater than or equal to zero, possibly equal to zero, and so on.

Second, we've simplified the functionality to can_drive which just checks whether we can drive a given distance, but we could now imagine adding other functions, like fn drive(&mut self, distance: f32) to actually do the drive, fn out_of_gas(&self) -> bool to check if we are out of gas, fn fill_up(&mut self, new_gas: f32), and so on. These additional features would conceptually align with what the object is designed for.

A Note On Units
Although overkill for this example, another improvement to your design would be to make use of Rust's type system to keep different units separate at compile time. Here's how you would do that: first we define struct wrappers for each different kind of unit we are interested in:
struct Miles(f32):
struct Gallons(f32):
struct Hours(f32);
struct MPH(f32);
struct MPG(f32);

Then we can define operations like multiplication for the particular types which "make sense" to multiply. E.g.:
use std::ops::{Add, Mul};

impl Add for Hours {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        self.0 + other.0
    }
}
impl Mul<Hours> for MPH {
    type Output = Miles;
    fn mul(self, time: Hours) -> Miles {
        self.0 * time.0
    }
}

and so on.
The beauty of this approach is that we get a compiler error if we make any arithmetic mistakes, like adding Miles to Hours. And moreover, that comes for free: in the actual running code, Miles and Hours both compile to plain f32 values.
Minutae
In addition to what the other answer said, run cargo clippy! It usually gives very helpful suggestions. Here you can replace remaining: remaining with remaining.  It would also be great to see some unit tests.


Delete the node at index i from its current position and insert it after node at index j I was trying to create a function to delete the node at index i from its current position and insert it after node at index j from a std::vector<Node> nodes. These container is logically a circular container of nodes, that is there's no actual first or last node, i.e. after nodes.back() comes nodes[0].

I really need this function not to have bugs and to be as performant as possible, so I'm asking here your help to a further check and for eventual suggestions to improve its performance.

So, this is the function:

/*
 * Delete the node at index i from its current position
 * and insert it after node at index j.
 * */
void SimpleSolution::shift(const int i, const int j) {

    assert_not_out_of_bounds({i, j});

    int x;

    if (j < i) { // ranges [i, end] and [start, j]

        for (x = i; x < nodes.size() - 1; ++x) {
            std::swap(nodes[x], nodes[x + 1]);
        }

        std::swap(nodes[0], nodes.back());

        for (x = 0; x < j; ++x) {
            std::swap(nodes[x], nodes[x + 1]);
        }

    } else { // range [i, j]

        if (i != j) {

            for (x = i; x < j; ++x) {
                std::swap(nodes[x], nodes[x + 1]);
            }

        } else { // i == j

            // i and j are the last elements
            if (i == (nodes.size() - 1)) {
                std::swap(nodes[0], nodes.back());
            } else { // equivalent to std::swap(nodes[i], nodes[i + 1])
                std::swap(nodes[i], nodes[j + 1]);
            }
        }

    }

}

I'm not looking for "idiomatic" C++, but for correctness and performance, but if idiomatic also means correctness and performance, then perfect.

Here's the assert_not_out_of_bounds method:

void SimpleSolution::assert_not_out_of_bounds(const std::initializer_list<int> indices) const {
    for (int i : indices) {
        if (i < 0 || i >= nodes.size()) {
            throw std::out_of_range("i is out of the range");
        }
    }
}

This looks quite sane, is there a reason you do not work with iterators?

your assert doesnt use the reference but a copy, so you should use const std::initializer_list<int> &indices
In the equal case, i would make it actually explicit and do std::swap(nodes[i], nodes[i + 1]), which is the same pattern you used all over the code.
It might be ok if your assert is used multiple times, but it is rather confusing, that you pass it i and j and i read only i in the code. Maybe use better names like index1 index2
Any reason you declare x outside of the loops?


A prime number checker (Multi numbers).py so obviously this SIMPLE code checks if the number is prime or not. I need to make it more advanced, easier to use, fewer lines or any improvement.
while True:
    lista = []
    try:
        num = int(input("Enter the amount of numbers: "))
        for i in range(0, num):
            value = int(input("Enter the numbers one by one: "))
            lista.append(value)
    except:
        print(''';-;
    Bruh, make sure you are entering numbers.''')
    for i in lista:
        if i <= 1:
            print("Duh,", i, "is not a primal number.")
            continue
        for j in range(2, i):
            if i % j == 0:
                print("Duh,", i, "is not a primal number.")
                break
        else:
            print("SMH,", i, "is a primal number obviously.")

First improvement I see is mathematical: to check if a number n is prime, it's sufficient to verify that it's not divisible by any integer between 2 and math.ceil(math.sqrt(n)) (don't forget to import math at the top of your file). That's going to make your program more efficient.
Another improvement would be to split the code that deals with getting the list of numbers lista from the user, and the code that finds if a single number is prime or not, into two separate functions that you call from the main while True loop. This will aid readability and code reuse.
A third improvement is to rename the variable lista to a more expressive name like numbers or candidates or something else.


Hands of Straights (LeetCode) Arrange the card Tried this leetcode question Hands of Straights. https://leetcode.com/problems/hand-of-straights/
Description is
Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1.
Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2
Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

My attempt to solve it using Haskell is here. Can someone review it. The code returns the correct values for most of the test cases that I have tried.

import Data.List

{-
solve 3 [1,1,2,2,2,3,3,3,4]
True

solve 3 [1,1,2,2,2,3,3,3]
False

solve 4 [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]
True
-}

solve::Int -> [Int] -> Bool
solve v xss = helper v $ group $ sort xss

helper::Int ->[[Int]] -> Bool
helper v [] = True
helper v xss = let (a, b) = splitAt v xss
    in case verify a  && ((length a) `mod` v == 0)  of
        True -> helper v $ (removeHead a []) ++ b
        False -> False

verify::[[Int]] -> Bool
verify [] = True
verify (x:[]) = True
verify (x:y:zx)
    | head y == succ (head x) = verify $ y:zx
    | otherwise = False

removeHead::[[Int]] -> [[Int]]-> [[Int]]
removeHead [] acc = acc
removeHead (x:xss) acc = case null (tail x) of
    True -> removeHead xss acc
    False -> removeHead xss (acc ++ [tail x])

Lines like False -> False indicate that there is a better way.

helper :: Int -> [[Int]] -> Bool
helper v [] = True
helper v xss = let (a, b) = splitAt v xss
  in verify a && length a `mod` v == 0 -- length a <= v, so why not just length a == v?
  && helper v (removeHead a [] ++ b)

removeHead :: [[Int]] -> [[Int]] -> [[Int]]
removeHead [] acc = acc
removeHead (x:xss) acc = removeHead xss
  $ acc ++ [tail x | not $ null $ tail x]

Left folds like removeHead can often be turned into right folds:

removeHead :: [[Int]] -> [[Int]]
removeHead [] = []
removeHead (x:xss) = [tail x | not $ null $ tail x] ++ removeHead xss

removeHead needs no explicit recursion. Data.List.NonEmpty lets us avoid partial functions (and giving verify a name :) ).

import Data.List.NonEmpty

solve :: Int -> [Int] -> Bool
solve v = helper v . NE.group . sort

helper :: Int -> [NE.NonEmpty Int] -> Bool
helper v [] = True
helper v xss =
  let (a, b) = splitAt v xss
      (straight, a') = unzip $ map NE.uncons a
  in all (==1) (zipWith subtract straight (tail straight))
  && length a == v
  && helper v (catMaybes a' ++ b)


Most efficient way to check if user is allowed to update an object So I have an user which can create his own Locations.

I implemented a webservice in order to add and update locations. If the user is not the owner of the location i want to throw an appropriate exception so that the user knows whats wrong.

The current method looks like this:

private void updateLocation(String loginToken, MapLocation ml) throws Exception{
    String username = this.getUsernameBySingInToken(loginToken); //throws exception is wrong token, otherwise returns username

    PreparedStatement stmt = conn.prepareStatement("SELECT username FROM Location WHERE idLoc=?");
    stmt.setInt(1, ml.getLocationId());
    ResultSet rs = stmt.executeQuery();
    String actuallUsername = null;
    while (rs.next()) {
       actuallUsername=rs.getString("username");
    }
    if(actuallUsername==null)
        throw new Exception("no location found!!"); //appropriate exception

    if(!username.equals(actuallUsername) || !username.equals(ml.getUsername()))
        throw new Exception("you are not the creator of this location!"); //appropriate exception

    PreparedStatement stmtVerification = conn.prepareStatement("UPDATE Location SET positionX=?,positionY=?"
            + " WHERE idLoc=?");
    stmtVerification.setDouble(1, ml.getPosX());
    stmtVerification.setDouble(2, ml.getPosY());
    stmtVerification.setInt(3, ml.getLocationId());
    stmtVerification.executeUpdate();

    disconnectFromMySQL();
}

The second method I implemented is shorter but the errors are not clear:

private void updateLocationV2(String loginToken, MapLocation ml) throws Exception{
    String username = this.getUsernameBySingInToken(loginToken);
    if(!username.equals(ml.getUsername()))
        throw new Exception("username is not the same as username of maplocation object"); //not sure if neccesary

    PreparedStatement stmtVerification = conn.prepareStatement("UPDATE Location SET positionX=?,positionY=?"
            + " WHERE idLoc=? and username=?");
    stmtVerification.setDouble(1, ml.getPosX());
    stmtVerification.setDouble(2, ml.getPosY());
    stmtVerification.setInt(3, ml.getLocationId());
    stmtVerification.setString(4, username);

    int executeUpdate = stmtVerification.executeUpdate();
    if(executeUpdate==0)
        throw new Exception("update failed. either wrong username or idLocation is wrong"); //not clear what is the error BUT shorter
    disconnectFromMySQL();
}

So yeah, now I have two methods which update my location but I am not sure which of them is the best. The first method has the advantage that the errors are clear but its slower since I have two queries (select and update). the second method is faster but the errors are not clear. WHich one of them is better, or is there even a better solution?

EDIT: This is my webservice method which calls the update function:

@PUT
@Path("/update")
@Consumes({MediaType.APPLICATION_JSON})
public Response update(String token, MapLocation ml) {
    Response r = Response.status(Response.Status.OK).entity("location updated").build();
    try {
        isUpdated = db.updateLocation(token,ml);
    } catch (Exception ex) {
        r = Response.status(Response.Status.BAD_REQUEST).entity(ex.getMessage()).build();
    }
    return r;
}

Soo ... I'm not quite sure how to formulate this without it sounding brash, but... Both of these methods are less than ideal...

Let's follow the behavioural flow to see what issues this code has:

The webservice portion you provide only understands PUT requests.
Conventionally, PUT requests are used to create objects, not to update them.
Instead one would expect a POST endpoint for that.
You first create an OK response and then overwrite it in case something fails.
That's somewhat... annoying in comparison to the simpler direct return.

try {
    db.updateLocation(token, ml);
    return Response.status(Status.OK).entity("location updated").build();
} catch (Exception e) {
    return Response.status(Status.BAD_REQUEST).entity(ex.getMessage()).build();
}

All this code assumes that the user gets to see the Exception message.
This is a bad assumption. Your webservice method should be responsible for creating useful messages, not your business logic.
Considering that the webservice code does not compile (because the declaration for isUpdated is missing) I hope that you don't actually pretend that every Exception ever is the user's fault by throwing a HTTP 400 to them...

The root cause of your conundrum is that you're not using the power of widely used java sql abstractions. Instead of manually writing SQL statements and performing updates, you should really make use of JPA and Entities.

If you had these, all of this would boil down to the following simplified code:

private void updateLocation(String username, MapLocation update) {
    MapLocation stored = em.find(MapLocation.class, update.getLocationId());
    if (stored == null) {
        throw new LocationDoesNotExistException();
    }
    if (!stored.getUsername().equals(username)) {
        throw new IllegalLocationUpdateException();
    }
    em.persist(update);
}

Note that the codesample above makes some simplifying assumptions about transaction management and the class hierarchy of the Exceptions it throws.

Note that I'm suggesting to rewrite your webservice method to something like:

public Response update(String loginToken, MapLocation request) {
    final String username = getUsernameFromToken(loginToken);
    try {
        db.updateLocation(username, request);
        return Response.ok().build();
    } catch (LocationDoesNotExistException e) {
        return Response.status(Response.Status.NOT_FOUND).build();
    } catch (IllegalLocationUpdateException e) {
        return Response.status(Response.Status.FORBIDDEN).build();
    } catch (Exception e) {
        LOGGER.warn("Unexpected exception in updateLocation", e);
        return Response.serverError().build();
    }
}


Is this Josephus problem solution bad or really bad? I tried to make a python code that would answer the Joseph problem. I really had a hard time with this and the try blocks was the only thing I could come up with. Can anyone tell me if the way I did it is valid or I have to rewrite the code because its too bad?

The problem is:

  People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

  The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.

My solution:

class Game:
    def __init__(self, n):
        self.n = n
        self.ppl = []
        self.has_gun = 1

    def creating_list(self):
        for i in range(1, self.n+1):
            self.ppl.append(i)

    def kill(self):
            number = self.ppl.index(self.has_gun)
            try:
                print("{} shoots {}".format(self.has_gun, self.ppl[number + 1]))
                del self.ppl[number + 1]
            except IndexError:
                print("{} shoots {}".format(self.has_gun, self.ppl[0]))
                del self.ppl[0]
            try:
                print("{} gives his gun to {}".format(self.has_gun, self.ppl[number+1]))
                self.has_gun = self.ppl[number + 1]
            except IndexError:
                if len(self.ppl) > 1:
                    print("{} gives his gun to {}".format(self.has_gun, self.ppl[0]))
                else:

                    print("{} is the only one remaining person in the circle".format(self.ppl[0]))
                self.has_gun = self.ppl[0]
            print("*" * 40)

    def run(self):
        self.creating_list()
        while True:
            self.kill()
            if len(self.ppl) == 1:
                print("{} survives".format(self.ppl[0]))
                break

while True:
    try:
        question = int(input("How many people in the circle do you want to be?\n"))
        break
    except:
        print("Type a number\n")
cos = Game(question)
cos.run()

You can simplify the code if you use (number + 1) % len(self.ppl). This is as it loops back around to the front of the list for you.
If you remove the prints then the code is easier to understand.
You can change creating_list to list(range(...)).
You don't need creating_list to be its own function.
You can combine run into kill removing the class. Leaving:

def game(n):
    ppl = list(range(1, n+1))
    has_gun = 1
    while True:
        number = ppl.index(has_gun) + 1 % len(ppl)
        del ppl[number]
        if len(ppl) > 1:
            number = ppl.index(has_gun) + 1 % len(ppl)
            has_gun = ppl[number]
        if len(ppl) == 1:
            return ppl[0]

You can move the if len(ppl) == 1: check into the statement of the while loop. This makes it easier to see that the function will always return.
You should rename your variables to make it easier to understand things. people over ppl.
Rather than using people.index store the index.

def game(people):
    people = list(range(1, people+1))
    index = 0
    while len(people) >= 1:
        index = (index + 1) % len(people)
        del people[index]
    return people[0]

Error if there is less than one person.
Allow taking a custom skip.

And you'd get to the function that I wrote to test your code:

def josephus_problem(people, amount):
    if people < 1:
        raise ValueError("There has to be at least one person")
    people = list(range(1, people+1))
    index = 0
    while len(people) > 1:
        index = (amount + index) % len(people)
        people.pop(index)
    return people[0]


Printing the minuend and subtrahend in a Minimum Difference algorithm I have a Minimum Difference algorithm, and I wanted to expand on it by printing the actual elements that were subtracted. I'm just wanting to know if this is the best way to do it.

public static int findMinimumDifference(int[] arr) {

    int minuend = 0; //initialize them here
    int subtrahend = 0;
    Arrays.sort(arr); //sort the array first

    int difference = 0;

    if (arr.length == 1) {
        difference = arr[0];
    }
    if (arr.length > 1) {
        difference = Math.abs(arr[0] - arr[1]); //This will give only positive integers for difference - e.g. 6 - 7 = -1 = 1

        for (int i = 0; i <= arr.length; i++) {
            if (i + 1 < arr.length) { //as long as we're not at the end yet
                int temp = Math.abs(arr[i] - arr[i + 1]); // temp variable is assigned to difference of consecutive elements i and i + 1
                if (temp < difference) // if temp is the new minimum difference, assign difference to temp
                    difference = temp;
                if(arr[i + 1] - arr[i] == difference) {
                    minuend = arr[i + 1]; //Here's where I assign them
                    subtrahend = arr[i];
                }
            }
        }
    }
    if(arr.length == 1) { //If there's only one element it will
                          //display arr[0] - 0 = arr[0]
                          //e.g. 12 - 0 = 12
        System.out.print(arr[0] + " - " + minuend + " = ");
    }
    else { //otherwise, show the subtraction
        System.out.print(minuend + " - " + subtrahend + " = ");
    }
    return difference;
    }
}

This is the output for two arrays as an example:

int[] array1 = {5, 16, 3, 32, 6};
int[] array2 = {13, 22, 37, 40, 11, 99, 100, 222, 1000, 101, 9999, 10000};

The minimum differences in the arrays are:
6 - 5 = 1
10000 - 9999 = 1

NOTE: I understand that second array actually has another subset (99, 100) that will equal 1. I just haven't figured out how to display both sets yet. I will work on that later.

Sorting

Arrays.sort(int[]) performs an in-array sorting, which may not be desirable if the caller of your method isn't expecting so. You may want to make a copy of the input via Arrays.copyOf(int[]) first.

Calculation

int temp = Math.abs(arr[i] - arr[i + 1]);
if (temp < difference) /* ... */

Since you have sorted the array in ascending order, you have two possible approaches:

Leave temp as negative so that you're looking for the largest negative number, e.g. -1 to find the smallest difference.
Use arr[i + 1] - arr[i] so that the comparison afterwards can remain the same.

Using Math.abs() is therefore unnecessary.

Initializing values and array references

You treat arr.length = 1 differently from a multi-valued array when it comes to printing the value, but with some adjustment to how you initialize minuend and difference, you don't have to do so, e.g.:

int minuend = arr[0];
int difference = Integer.MAX;

In addition, consider storing just the difference and the array index where you have the smallest difference, so that you don't need to remember subtrahend.


Cycle in Directed graph to vector I created a class of a directed graph and a method for finding if graph has an Euler cycle and updating a vector accordingly.Is there any optimization or a nicer way to do this.

class Graph {
private:
    int V;          // No. of vertices
    list<int> *adj; // Pointer to array of lists
    bool cycleHelper(int v, bool visited[], bool *reStack, vector<int> &path) const; // Helper for cycle()

public:
    Graph(int V);                   // Constructor
    ~Graph();                       // De-constructor Who wants to live forever when love must Die
    void addEdge(int u, int w);     // function to add an edge to graph

    bool cycle(vector<int> &path) const; // Returns True if Graph has a circle, and sets path to its route
};

Graph::Graph(int V) {
    this->V = V;         // Set Graph nodes
    adj = new list<int>[V]; // V-dimention array of lists
}
Graph::~Graph() {
    delete[] adj;
}

void Graph::addEdge(int u, int w) {
    adj[u].push_back(w); // Add u to v's list.
}

bool Graph::cycleHelper(int v, bool visited[], bool *recStack, vector<int> &path) const {
    if (visited[v] == false) {
        // Mark the current node as visited and not in recursion stack
        visited[v] = true;
        recStack[v] = true;

        for (auto i : adj[v]) {
          if ( i == path[0]) return true;
          else if (!visited[i] && cycleHelper(i, visited, recStack, path)){
              path.push_back(i);
              return true;
            }
          else if (recStack[i]){
              path.push_back(i);
              return true;
            }
        }
    }
    recStack[v] = false; // remove from recursion stack, I don't need u any more
    return false;
}

bool Graph::cycle(vector<int> &path) const {
    // Mark all the vertices as not visited and not part of recursion stack
    bool *visited = new bool[V];
    bool *recStack = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
        recStack[i] = false;
    }
    // Call the  helper function

    for (int i = 0; i < V; i++){
        path.push_back(i);
        if (cycleHelper(i, visited, recStack, path)) {
            //path.push_back(i);
            reverse(path.begin(),path.end());
            //if (path.begin()[0] == path.end()[-1]) path.pop_back();
            return true;
        }
        path.clear();
    }
    path.clear();
    return false;
}

General stuff

#includes are missing
missing using namespace std; (which by itself is discouraged, especially in header files).
Graph::cycles path result contains not only the cycle, but alse the vertices that led there (e.g. in A -> B -> C -> B, A would be included in path though it is not part of the cycle). This might or might not be intended.
Inconsistency: Graph::cycleHelper takes visited as bool[], but recStack as bool *, even though the usage for both is the same.
if(visited[v] == false) can easily be rewritten to if(!visited[v])
Graph::cycle treats path as if it has full control over all elements already present. This behavior might be unexpected by users of the class and should at the very least be thouroughly documented.

Memory management

Graph::cycle leaks both visited and recStack.
Graph::addEdge never checks whether its parameters are in the valid range. If they aren't, there might be accesses to out-of-bounds memory.

These issues can be fixed by using appropriate data structures and error checking. Generally, prefer using RAII constructs (like std::unique_ptr or containers) for resource acquisition.

Data structures

Prefer std::array (if size is statically known) or std::vector (if not) over raw arrays. This also helps with memory cleanup.
Try to structure similarly used variables in their own class or struct.
Prefer std::vector (preferred) or std::deque (if constant time frontal insertion/removal is needed) over std::list, unless you absolutely need constant time random insertion/removal (and even then, you might want to measure std::vector as it is surprisingly efficient on modern hardware).

Class design

Some variables have very cryptic names and few (if any) documentation to their meaning.

Graph::V: Represents the number of vertices in the graph. Maybe rename to vertex_count or num_vertices or similar.
u and w in Graph::addEdge: There is not way to infer whether the edge is added from u to w or vice versa. Maybe rename to something like from and to?
Graph::cycle: cycle is an unfornate choice of name, as the verb cycle has a different meaning. hasCycle or findCycle better express the intention behind this member function.

There is an implicit assumption that "vertex index" == "vertex value". If there ever is a case where this assumption does not hold, the whole class will have to be redesigned.
Graph::cycle violates the Single Responsibility Principle (SRP). It does two things ("check whether there is a cycle" and "return the cycle"), which might benefit users of the class that want both operations, but hinders other users that only want one of the operations.
Graph is built upon the assumption that no more vertices will be added after construction. While this might be true in your specific use case, this won't be true in general.
A specific edge might be added multiple times, which might increase worst case runtimes (as iteration of the edges of a vertex can become greater than \$\mathcal{O}(n)\$

Amending all the points

If I had to implement this, the result would look like this:

#include <vector>
#include <algorithm>
#include <stdexcept>
#include <deque>

class graph {
    using node_type = int;

    class vertex {
        node_type value;
        std::vector<vertex *> edges;
        bool visited = false;
        bool marked = false;

    public:
        vertex(node_type name) : value{name}, edges{} {}

        node_type name() const { return value; }
        bool is_marked() const { return marked; }
        void clear_flags() { visited = false; marked = false; }

        bool has_edge(vertex *to) const {
            return std::find(std::begin(edges), std::end(edges), to) != std::end(edges);
        }
        void add_edge(vertex *to) {
            if(!has_edge(to)) edges.push_back(to);
        }

        vertex *find_first_marked_edge() {
            auto match = std::find_if(std::begin(edges), std::end(edges), [](auto& edge){ return edge->marked; });
            if(match == std::end(edges)) return nullptr;

            return *match;
        }

        bool is_part_of_cycle() {
            if(marked) return true;
            if(visited) return false;

            visited = true;
            marked = true;

            for(auto& edge : edges) {
                if(edge->is_part_of_cycle()) return true;
            }

            marked = false;
            return false;
        }
    };

    std::vector<vertex> vertices;

public:
    graph() = default;
    graph(std::initializer_list<node_type> init) : vertices{} {
        for(auto& name : init) {
            add_vertex(name);
        }
    }

    void add_vertex(const node_type& name) {
        if(std::find_if(std::begin(vertices), std::end(vertices), [&](auto& vert){ return vert.name() == name; }) != std::end(vertices)) {
            throw std::invalid_argument{"a vertex with this name already exists"};
        }
        vertices.emplace_back(name);
    }

    void add_edge(node_type from, node_type to) {
        auto& from_vert = find_vertex(from);
        auto& to_vert = find_vertex(to);

        from_vert.add_edge(&to_vert);
    }

    bool has_cycle() {
        for(auto& vert : vertices) {
            vert.clear_flags();
        }

        for(auto& vert : vertices) {
            if(vert.is_part_of_cycle()) return true;
        }

        return false;
    }

    std::deque<node_type> find_first_cycle() {
        auto cycle = std::deque<node_type>{};
        if(!has_cycle()) return cycle;

        auto cycle_iter = find_first_marked_vertex();

        while(std::find(std::begin(cycle), std::end(cycle), cycle_iter->name()) == std::end(cycle)) {
            cycle.push_back(cycle_iter->name());
            cycle_iter = cycle_iter->find_first_marked_edge();
        }

        while(cycle.front() != cycle_iter->name()) cycle.pop_front();

        return cycle;
    }

private:
    vertex& find_vertex(node_type name) {
        auto match = std::find_if(std::begin(vertices), std::end(vertices), [&](auto& vert){ return vert.name() == name; });
        if(match == std::end(vertices)) {
            throw std::invalid_argument{"vertex could not be found"};
        }

        return *match;
    }

    vertex* find_first_marked_vertex() {
        auto match = std::find_if(std::begin(vertices), std::end(vertices), [](auto& vert){ return vert.is_marked(); });
        if(match == std::end(vertices)) return nullptr;
        return &*match;
    }
};

Points to note:

graph::vertex encapsulates all information about a vertex. I changed recStack to marked, since many graph algorithms work with marked vertices.
No manual memory management (= no memory leaks). Everything is owned by containers.
I introduced some descriptive helper functions. This makes the code much more readable.
If the value of the vertices ever needs to be changed (or templated), only the definition of graph::node_type needs to be adjusted.
For a more deterministic performance, graph::vertex::edges could be kept sorted at all times.
Some functions have a first in their names, as there might be more results (in the general case).


What are my highest activity streaks? I have written the following query to figure out activity streaks on a per-user basis. I find it... Ugly... And would love to improve it!
Limitations
Those are explained as commented text at the very top of the query.
Problems

Can this be done without a loop?

Is there a better way to do this than #TempTables?

Bonus!
If it is possible to do this for multiple users, e.g., a top 10 or top 50, I'll award a 100 rep bounty to whoever solves it first!
/*
There are certain limitations to the usefulness of this query.
It cannot track if a user has just visited the site without "significant" activity
"Significant" would be defined as a Comment, Post, Suggest edit, Approve or Reject edit, Vote on suggested edit, Vote on a post
Also, Up-votes and Down-votes on Posts are anonymous, as such they cannot be included in the query
*/

DECLARE @UserId INT;
SET @UserId = ##UserId##;

-- Temp table to hold all relevant activity dates
CREATE TABLE #UserActiveDays
(
    UserId INTEGER
  , ActivityDate DATE
  , Source VARCHAR(50)
);

INSERT INTO #UserActiveDays
(
    UserId
  , ActivityDate
  , Source
)
  SELECT DISTINCT
      OwnerUserId
    , CAST(CreationDate AS DATE)
    , 'PostCreation'
  FROM Posts
  WHERE OwnerUserId = @UserId
UNION
  SELECT DISTINCT
      UserId
    , CAST(CreationDate AS DATE)
    , 'CommentCreation'
  FROM Comments
  WHERE UserId = @UserId
UNION
  SELECT DISTINCT
      UserId
    , CAST(CreationDate AS DATE)
    , 'PostHistoryCreation'
  FROM PostHistory
  WHERE UserId = @UserId
UNION
  SELECT DISTINCT
      OwnerUserId
    , CAST(CreationDate AS DATE)
    , 'SuggestedEditCreation'
  FROM SuggestedEdits
  WHERE OwnerUserId = @UserId
UNION
  SELECT DISTINCT
      OwnerUserId
    , CAST(ApprovalDate AS DATE)
    , 'SuggestedEditApproval'
  FROM SuggestedEdits
  WHERE OwnerUserId = @UserId
UNION
  SELECT DISTINCT
      OwnerUserId
    , CAST(RejectionDate AS DATE)
    , 'SuggestedEditRejection'
  FROM SuggestedEdits
  WHERE OwnerUserId = @UserId
UNION
  SELECT DISTINCT
      UserId
    , CAST(CreationDate AS DATE)
    , 'SuggestedEditVote'
  FROM SuggestedEditVotes
  WHERE UserId = @UserId
UNION
  SELECT DISTINCT
      UserId
    , CAST(CreationDate AS DATE)
    , 'VoteCreation'
  FROM Votes
  WHERE UserId = @UserId;

CREATE TABLE #ConsecDaysCount
(
    UserId INT
  , DaysCount INT
  , DateStreakEnded DATE
);

DECLARE @FirstDay DATE;
  SET @FirstDay = ( SELECT MIN(CreationDate) FROM Users WHERE Id = @UserId );
DECLARE @LastDay DATE;
  SET @LastDay = ( SELECT MAX(LastAccessDate) FROM Users WHERE Id = @UserId );
DECLARE @ConsecDaysCounter INT;
  SET @ConsecDaysCounter = 0;

WHILE (@FirstDay < @LastDay)
BEGIN
  IF ( SELECT DATEADD(DAY, 1, @FirstDay) ) IN (SELECT ActivityDate FROM #UserActiveDays)
    BEGIN
    SET @ConsecDaysCounter = @ConsecDaysCounter + 1;
    SET @FirstDay = DATEADD(DAY, 1, @FirstDay);
    END;
  ELSE
    BEGIN
    INSERT INTO #ConsecDaysCount (UserId, DaysCount, DateStreakEnded)
      VALUES (@UserId, @ConsecDaysCounter, @FirstDay);
    SET @ConsecDaysCounter = 0;
    SET @FirstDay = DATEADD(DAY, 1, @FirstDay);
    END;
END;

SELECT
    UserId AS [User Link]
  , DaysCount
  , DateStreakEnded
FROM #ConsecDaysCount
ORDER BY DaysCount DESC;

General
There are a few issues in here that cause inaccurate data, as well as some inefficiencies.

When a post is created it is also registered in PostHistory (three times, actually) There is no need to check for post creation at all since you already check for the same activity in the history.
You populate the Source column, but never use it. SQL is in large part dependent on data volume, and you are 'shifting' more data than you need to.
Your VoteCreation section is OK, but you realize you only pull out bounties and favourites from that, right (VoteType 5 and 8)? Other votes are anonymized, and are not possible to find...
Somehow you have 0-day streaks. How does that make sense?

SuggestedEdits requires a special section....
You have three sections for SuggestedEdits. One uses the Creation date, the others use the Approved and Rejected dates. The approval and rejection are not activities by the Owner of the suggested edit, but you are counting them as such.... Only the CreationDate indicates activity by the OwnerUserId in the SuggestedEdit.
The approval and rejection activity are recorded in the SuggestedEditVotes table (which you process from a different section).
Note, you are missing 'accepts an answer' which can be calculated from the Post/Votes combination.
As for your 'additional questions'....
Without the temp table
Yes, this can be done without the temp table, and without the loop.
You can do it all as a single query, if you use CTE expressions to hold the data.
With a CTE containing the 'activity' data, you can find the first day in a streak (Using a self-join, does the user have activity on the previous day, if they do not, then it's the first day of a streak)
Once you have identified the first day, you can also identify which activity belongs in which streak (the most recent start before the current activity must be the start...)
Finally, the streak is as long as the furthest date that belongs to each streak....
As it happens, this is efficient enough to be run for all users on the whole of Code Review.... the query is (Here in SEDE):
declare @userid integer = ##UserId:int?-1##;

with ActiveDays as (

    select Distinct
           UserId as UserId,
           Convert(Date, CreationDate) as Day
    from   PostHistory

  UNION

    select Distinct
           UserId as UserId,
           Convert(Date, CreationDate) as Day
    from   Comments

  UNION

    select Distinct
           OwnerUserId as UserId,
           convert(Date, CreationDate) as Day
    from SuggestedEdits

  UNION

    select distinct
           Q.OwnerUserId as UserId,
           Convert(Date, V.CreationDate) as Day
    from Posts Q inner join Votes V
      on Q.AcceptedAnswerId = V.PostId
      and V.VoteTypeId = 1

  UNION

     select distinct
            UserId as UserId,
            Convert(Date, CreationDate) as Day
     from SuggestedEditVotes

), StreakStarts as (

    select UserId, Start.Day
    from ActiveDays Start
    where not exists (
        select 1
        from ActiveDays
        where Start.UserId = UserId
          and DateAdd(dd, -1, Start.Day) = Day
    )

), StreakMerge as (

    select A.UserId, A.Day, Max(S.Day) as Start
    from ActiveDays as A inner join StreakStarts as S
      on A.UserId = S.UserId
      and A.Day >= S.Day
    group by A.UserId, A.Day

), LongStreaks as (

    select UserId, Start, 1 + max (DateDiff(dd, Start, Day)) as  Streak
    from StreakMerge
    group by UserId, Start
)

Select U.Id as [User Link], U.DisplayName, Start, S.Streak
from Users as U inner join LongStreaks as S
  on U.Id = S.UserId
where S.Streak > 1
  and (@userid = -1 OR U.Id = @userid)
order by S.Streak desc


The longest subsequence with specified difference between min and max As an input you have non-empty zero-indexed array of integers. The goal is to find the longest subsequence (any sequence obtained by removing some elements from A), where difference between min value and max value does not exceed 1.

For example, given array: 6,10,7,7,9,8 function should return 3, because 6,7,7 (or 7,7,8) is the longest qualifying subsequence.

Is this solution efficient?

    public int solution(int[] A) {
    Arrays.sort(A);
    int counter = 0;
    int res = 0;
    int val = -1;
    for (int i = 0; i < A.length - 1; i++) {
        if (val == -1 && A[i + 1] - A[i] < 2) {
            counter = 2;
            val = A[i + 1] - A[i];
        } else if (val == 0 && A[i + 1] - A[i] <= 1) {
            counter++;
            val = A[i + 1] - A[i];
        } else if (val == 1 && A[i + 1] - A[i] == 0) {
            counter++;
        } else {
            val = -1;
            res = Math.max(res, counter);
            counter = 0;
        }
    }
    return res;
}

Time complexity is linearithmic.

Bugs
The function doesn't handle the last series of numbers.  For example:
Input: 5 5 5       Output: 0
Input: 5 5 9 9 9   Output: 2

This can be fixed by modifying the end of the function:
    return Math.max(res, counter); // <-- Accounts for last series

Also, the function fails to consider a number as the lower of two numbers once it has used it as the upper of two numbers.  For example:
Input: 5 5 6 6 6 7 7 7 10    Output: 5 (should be 6)

Here, it groups 5 and 6 together but never considers that 6 and 7 can be grouped together.


Collect all items containing a word to a Multimap I have a simple class like

class Item {
    Set<String> wordSet() {...}
}

So each item has a set of words and I need the inverse relation, i.e., for each word find all items containing it. This gets used a lot, so I want an ImmutableSetMultimap allowing me to retrieve it quickly.

I'm using

ImmutableSetMultimap<String, Item> wordToItemsMultimap(Collection<Item> items) {
    Multimap<Item, String> itemToWords = items
        .stream()
        .collect(Multimaps.flatteningToMultimap(
             i -> i,
             i -> i.wordSet().stream(),
             HashMultimap::create));
    Multimap<String, Item> wordToItems =
             Multimaps.invertFrom(itemToWords, HashMultimap.create());
    return ImmutableSetMultimap.copyOf(wordToItems);
}

for creating the map and it works, but I find it too complicated. I'm looking for a simpler solution.

I don't care much about efficiency of the above snippet (as it gets called just once), but optimization hints are welcome as I'm doing a lot of similar things where speed matters.

Well, if your items has no null elements, you can use ImmutableSetMultimap#flatteningToImmutableSetMultimap collector and it's own inverse method instead of calling utility methods.

return items.stream()
        .collect(flatteningToImmutableSetMultimap(
                i -> i,
                i -> i.wordSet().stream()
        ))
        .inverse();

It's a bit more terse (note the static import, which in my team we agreed is acceptable, although we normally don't use static imports) as it repeats looong class name in method name) and gives you immutable multimap right away.

If some "flattening" version of Multimaps#index existed, you could have also used it, but there's no such method right now unfortunately.


Game sprite animation This code animates my main game sprite by increasing the animation frame. First I check if the character is moving, then I increase the animation counter until it reaches the desired speed, and then if so, I increase the animation frame.

How can I make it more elegant and optimised in terms of speed?

       if (moving){
        anispeed++;
        if (anispeed==animaxspeed){
            anispeed=0;
            animationframe++;
            if (animationframe==3) animationframe=0;
        }

Two small comments:

Naming:
The convention for variable names in Java is camelCase. Your animationframe should instead be animationFrame when going by that rule. Similar for your animaxspeed. You don't have to save characters in your code, write it out: animationMaxSpeed.
anispeed can also be written out: animationSpeed. This should make your code even more clear than it is ;)

Braces:
It's also convention to place all if-blocks in braces, disregarding whether they have to, or not. This is to decrease the possibility of bugs when changing such blocks and forgetting braces.

if (animationFrame == 3) {
    animationFrame = 0;
}

Also the Java-Coding-Standard is 4 spaces indentation. It might be, that the markup for SE broke yours, but either way, your first if-statement is too far in.


Print routes on the stairway when only 1 or 2 steps are possible Given a staircase with N steps, you can go up with 1 or 2 steps each
  time.  Output all possible ways you go from bottom to top.

I'm looking for code review, best practices, optimizations etc. Complexity: O(2n)

    public final class StairRoutes {

        private StairRoutes() {}

        /**
         * Given a staircase with N steps, you can go up with 1 or 2 steps each time.
         * Output all possible way you go from bottom to top.
         *
         * @param stepCount     The number of steps in the stairway
         * @return              A list containing all possible routes.
         */
        public static List<List<Integer>> stairClimbingRoutes(int stepCount) {
            if (stepCount <= 0) throw new IllegalArgumentException("The step count: " + stepCount + " should be positive.");

            /* a container containing all the possible routes */
            final List<List<Integer>> stairRoutes = new ArrayList<List<Integer>>();
            calcAllRoutes(stepCount, new LinkedList<Integer>(), stairRoutes);

            return stairRoutes;
        }

        private static void calcAllRoutes(int stepCount, LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {
            if (stepCount <= 1) {
                populateRoute (stepCount, tempList, stairRoutes);
                return;
            }

            processSteps(stepCount, 1, tempList, stairRoutes);
            processSteps(stepCount, 2, tempList, stairRoutes);
        }

        private static void populateRoute (int numStairs,  LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {
            if (numStairs == 0) {
                stairRoutes.add(new ArrayList<Integer>(tempList));
                return;
            }
            if (numStairs == 1) {
                tempList.add(1);
                stairRoutes.add(new ArrayList<Integer>(tempList));
                tempList.removeLast();
                return;
            }
        }

        private static void processSteps(int numStairs, int hopCount, LinkedList<Integer> tempList, List<List<Integer>> stairRoutes) {
            tempList.add(hopCount);
            calcAllRoutes(numStairs - hopCount, tempList, stairRoutes);
            tempList.removeLast();
        }

        public static void main(String[] args) {
            List<List<Integer>> stairRoutes = stairClimbingRoutes(5);
            for (List<Integer> route : stairRoutes) {
                for (Integer stair : route) {
                    System.out.print(stair + ":");
                }
                System.out.println();
            }
        }

}

In general, recursion is a complicated technique. It is often hard to understand the state of the system at any point in time because you have to add a dimension to your thinking.

I consider it to be bad practice to have a recursive process where the recursion is unnecessarily split across multiple methods. In your case, you have a 2-method split in your recursion.

calcAllRoutes calls processSteps
   processSteps calls calcAllRoutes
      calcAllRoutes calls processSteps
         processSteps calls calcAllRoutes
            ...

Sometimes this is not avoidable... but, in this case, it is unnecessary. By splitting the logic in to two methods, it becomes harder to 'grok' the recursion.

Additionally, your previous questions where you have had similar sorts of work, you have always 'defaulted' to using java.util.* collections instead of using simpler mechanisms like arrays of primitives. Arrays are much faster, and smaller, and tend to lead to better structured code. This is because the array is essentially a stack, and popping the stack is as easy as changing it's size.... you do not have to do as much manipulation of the stack head.

Finally, this problem is one which should have a more general solution. You have hard-coded this solution to only work with 1-step and 2-step 'strides'. The problem is actually simpler if you make the stride options a general thing....

Consider this alternative code... it:

has a single recursive method.
the recursive method has the standard layout:

check recursion-ending-conditions
initiate further recursion

it can use any number of positive-valued strides to get to the destination
it is just a single recursive method.
it uses an array of primitive ints to accumulate the current combination

So, this code is, in my opinion, preferable:

public class Stairway {

    /**
     * Calculate all possible ways to ascend `steps` stairs, using the different-sized strides provided.
     * @param strides the different number of steps that can be taken.
     * @param steps the number of steps to ascend.
     * @return a list of all step combinations.
     */
    public static final List<int[]> stairClimbingRoutes(int[] strides, int steps) {

        // create the combination stack.
        // Longest possible combination is 1 step each time.
        int[] combination = new int[steps];
        int comblength = 0;

        List<int[]> results = new ArrayList<>();

        recurseRoute(steps, strides, combination, comblength, results);
        return results;
    }

    private static void recurseRoute(final int remaining, final int[] strides,
            final int[] combination, final int comblength, final List<int[]> results) {
        if (remaining < 0) {
            // this combination takes us too far.
            return;
        }
        if (remaining == 0) {
            // this combination is just right.
            results.add(Arrays.copyOf(combination, comblength));
            return;
        }
        // need to go further.
        for (int s : strides) {
            combination[comblength] = s;
            recurseRoute(remaining - s, strides, combination, comblength + 1, results);
        }

    }

    public static void main(String[] args) {

        for (int[] combination : stairClimbingRoutes(new int[] {1, 2}, 10)) {
            int check = 0;
            for (int s : combination) {
                check += s;
            }
            System.out.println("Actual " + check + " using " + Arrays.toString(combination));
        }

    }

}


Move zeroes to the end of array For the problem of moving zeroes to the back of the array as detailed here. I did it like below in Erlang. I just think my way is very basic and probably there is a more elegant way to do it using recursion?

-module(move_zeroes).
-compile([export_all, debug_info]).

%% This is solving this problem:

%% API exports
-export([]).

move_zeroes(L) ->
    moving_zeroes(L, []).

moving_zeroes(L, _) ->
    Zeroes = lists:filter(fun(X) -> X == 0 end, L),
    Non = lists:filter(fun(X) -> X /= 0 end, L),
    Non ++ Zeroes.

This is a problem that's well suited to elementwise aggregation. Consider the following:

move_zeroes (L) ->
    case L of
       [0 | T] -> move_zeroes(T) ++ [0];
       [El | T] -> [El] ++ move_zeroes(T);
       _Else -> L
    end.

I am only blindly guessing at the syntax here, but this should clarify how one would write this without using lists:filter twice. It additionally avoids the helper function you created there, which seems to not serve a purpose ...


Excel VBA binary search class module I have a long list of sorted strings in a Workbook, and I have to find a lot of values in it. I was hoping to build a binary search Class Module that will find them for me faster than Excel's built-in search formulas/methods.

Can anyone think of a faster way, or maybe more bug proof?

Values() As String
Value2 as String
Upper As Integer
Lower As Integer
Middle As Integer
Private Function Move_Array() As Integer
    Middle = Round((Upper - Lower) / 2, 0)
    Move_Array = Compare(Values(Middle), Value2)
End Function
Function Search(Cells As Range, Value As String) As Integer
    If Cells.Count < 1 Then
        Values() = Cells.value
    End If
Value2 = Value
Again:
    Select Case Move_Array()
        Case -1
            Lower = Middle
        Case 1
            Upper = Middle
        Case 0
            Search = Middle
            Exit Function
    End Select
    GoTo Again
End Function

This is a Sub that would call this class. However, this is subject to change.

Sub Start_BINSearch()
    Dim Search_operation As BINSearch
    Dim Cells As Range
    Dim Value As String

    Set Search_operation = BINSearch
    Set Cells = Application.InputBox( _
        Prompt:="Enter Range to Search", _
        Type:=8)
    Value = Application.InputBox( _
        Prompt:="Enter value that you waant to look for")
    Position = Search_operation.Search(Cells, Value)
End Sub

Your code is quite difficult to manipulate into doing what you are trying to do.

Some specifics:

Don't use "goto" whenever possible

The following needs to be fixed:

   Dim Search_operation As BINSearch
   'Set Search_operation = BINSearch
   Set Search_operation = New BINSearch

When working with objects, you need to use New when using Set.

This is currently not handling any errors or anything for your input ranges.

Set Cells = Application.InputBox( _
    Prompt:="Enter Range to Search", _
    Type:=8)
Value = Application.InputBox( _
    Prompt:="Enter value that you waant to look for")
Position = Search_operation.Search(Cells, Value)

When you want to use global variables (which, while there are cases to use them, this is not one of them)  you need to dimension them still. Plus, the way you had them before won't compile anyways...

Public Value2 as String
Public Upper As Integer
Public Lower As Integer
Public Middle As Integer

I don't recommend this at all because it is hard to read.

The following does the random search the way you are looking for. I also added a comparison vs .Find to make it easier. I used the animal list here. This is the pastebin.

Public Declare Function GetTickCount Lib "kernel32.dll" () As Long

Private Function getRandomSearchArray(ByRef arr, wsRange As Range, ByVal numbAttempts As Long) As Variant

    ReDim arr(0 To numbAttempts)
    Dim wsArr
    wsArr = wsRange.Value

    Dim i As Long
    Dim rand As Double

    For i = LBound(arr) To UBound(arr)
        rand = Round(rnd() * (UBound(wsArr) - LBound(wsArr)), 0) + 1
        arr(i) = wsArr(rand, 1)
    Next i

End Function

Sub myBinarySearchExample()

    Dim searchRange As Range
    Dim sortedValues As Variant
    Dim searchValues As Variant
    Dim startTickCount As Double
    Dim numbAttempts As Long
    Dim i As Long
    Dim s As String
    Dim arrIndex As Integer

    Set searchRange = Worksheets("BinSearch").Range("A1:A141")
    numbAttempts = 100000

    sortedValues = searchRange.Value
    getRandomSearchArray searchValues, searchRange, numbAttempts

    startTickCount = GetTickCount

    'using Binary Search
    For i = 1 To numbAttempts
        s = searchValues(i)
        'Do this to simulate the "read into memory" each iteration
        sortedValues = searchRange.Value

        arrIndex = BinarySearch(sortedValues, s)
    Next i

    Debug.Print "It took: " & GetTickCount - startTickCount & " ms to run this with the Binary Search."

    'do with .Find
    startTickCount = GetTickCount

    For i = 1 To numbAttempts

        arrIndex = searchRange.Find(What:=searchValues(i), After:=Range("A1"), LookIn:=xlFormulas, _
            LookAt:=xlPart, SearchOrder:=xlByRows, SearchDirection:=xlNext, _
            MatchCase:=False, SearchFormat:=False).Row

    Next i

    Debug.Print "It took: " & GetTickCount - startTickCount & " ms to run this with the Excel Find."

End Sub

Function BinarySearch(searchArray As Variant, searchValue As String) As Integer

    'dimension these as long to avoid possible integer
    'overflow errors for large lists
    Dim curIndex As Long
    Dim firstIndex As Long
    Dim lastIndex As Long

    Dim nextMiddle As Long
    Dim strValue As String

    'set lower/upper bounds correctly initially for the search
    firstIndex = LBound(searchArray)
    lastIndex = UBound(searchArray)

    Do

        nextMiddle = Round((lastIndex - firstIndex) / 2 + firstIndex)

        strValue = searchArray(nextMiddle, 1)

        'check if it is before/after the current point
        If StrComp(searchValue, strValue, vbTextCompare) = -1 Then
            lastIndex = nextMiddle - 1
        ElseIf StrComp(searchValue, strValue, vbTextCompare) = 1 Then
            firstIndex = nextMiddle + 1
        Else
            BinarySearch = nextMiddle
            Exit Do
        End If

    Loop

End Function

It took: 3182 ms to run this with the Binary Search.
It took: 11763 ms to run this with the Excel Find.


Wrapper to translate text in wxPython widgets I am writing a wrapper for all widgets that contain text that needs to be translated for wxPython and make them handle the initial translation and the change of language on their own using gettext.

I already have a working prototype but I'm sure this is not the correct way to do it. Here is an example for all subclasses of wx.Control.

My Idea is to override the relevant methods of wx.Control and then merge the actual widgets (subclasses of wx.Control) together with my Control.

import wx
from wx.lib.pubsub import pub

class Control(wx.Control):
    def __init__(self, label):
        self.ml_label = label
        pub.subscribe(self.Update, 'language.changed')

    def Update(self):
        super().Update()
        super().SetLabel(_(self.ml_label))

    def SetLabel(self, label):
        self.ml_label = label
        super().SetLabel(_(self.ml_label))

class Button(wx.Button, Control):
    def __init__(self, parent, id=wx.ID_ANY, label=wx.EmptyString, pos=wx.DefaultPosition, size=wx.DefaultSize, style=0,
                 validator=wx.DefaultValidator, name=wx.ButtonNameStr):
        Control.__init__(self, label)
        wx.Button.__init__(self, parent, id, _(label), pos, size, style, validator, name)

class StaticText(wx.StaticText, Control):
    def __init__(self, parent, id=wx.ID_ANY, label=wx.EmptyString, pos=wx.DefaultPosition, size=wx.DefaultSize, style=0,
                 name=wx.StaticTextNameStr):
        Control.__init__(self, label)
        wx.StaticText.__init__(self, parent, id, _(label), pos, size, style, name)

Before I had the code from the Control class in Button and StaticText but as there are lots of widgets based on Control I wanted to move the duplicate code to one place.

It works, but I'm sure it's not the right way to do it especially as I don't call super().__init__ in the Control class, which can't be right.

Should I even be using multiple inheritance for what I am trying to do here?

After I posted this question and saw that I wrote that I try to write a Wrapper, I thought that this might be the solution...

import wx
from wx.lib.pubsub import pub

def multilingual(wrapped):

    class WrappedClass(wrapped):
        def __init__(self, *args, **kwargs):
            # Translate label parameter
            if len(args) >= 3:
                self.ml_label = args[2]
                args = list(args)
                args[2] = _(self.ml_label)
            else:
                self.ml_label = kwargs.get('label',wx.EmptyString)
                kwargs['label'] = _(self.ml_label)
            super().__init__(*args,**kwargs)
            pub.subscribe(self.Update, 'language.changed')

        def Update(self):
            print('update')
            super().Update()
            super().SetLabel(_(self.ml_label))

        def SetLabel(self, label):
            print('setlabel')
            self.ml_label = label
            super().SetLabel(_(self.ml_label))

    return WrappedClass

@multilingual
class Button(wx.Button):
    pass

@multilingual
class StaticText(wx.StaticText):
    pass


Proper way to validate from sub to sub I am using a public validating sub to help validate the other subs. Is this the most efficient way to do this?

Public Sub Validator(sender As Object, e As EventArgs) Handles GrossRevenueButton.Click, CPTCodesButton.Click, EstablishedVisitsButton.Click
    Dim validater As Integer = 0 'this is the variable that gets sent out from this sub
    If MonthSelectBox.Text = "" Then
        Label1.Text = "You didn't select a month!"
        validater = 1
    Else
        Label1.Text = ""
    End If
    If YearSelectBox.Text = "" Then
        Label2.Text = "You didn't select a year!"
        validater = 2
    Else
        Label2.Text = ""
    End If
    If FilepathTextBox.Text = "" Then
        Label3.Text = "You didn't select a file!"
        validater = 3
    Else
        Label3.Text = ""
    End If

    If MonthSelectBox.Text.Length > 1 And YearSelectBox.Text.Length > 1 And FilepathTextBox.Text.Length > 1 Then
        validater = 0
    End If
End Sub

'GROSS REVENUE
Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles GrossRevenueButton.Click
    Dim validater As Integer 'validater comes from the validate sub
    If validater > 0 Then
        Call Gross_Revenue()
    Else
        Label4.Text = "Something went wrong!"
    End If
End Sub

'CPT CODES
Sub Button3_Click(sender As System.Object, e As System.EventArgs) Handles CPTCodesButton.Click
    Dim validater As Integer 'validater comes from the validate sub
    If validater > 0 Then
        Call CPT_Totals()
    Else
        Label4.Text = "Something went wrong!"
    End If
End Sub

'ESTABLISHED VISTS
Sub Button4_Click(sender As System.Object, e As System.EventArgs) Handles EstablishedVisitsButton.Click
    Dim validater As Integer 'validater comes from the validate sub
    If validater > 0 Then
        Call Established_Visits()
    Else
        Label4.Text = "Something went wrong!"
    End If
End Sub

Your validation has a "major" flaw. You are validating each thing by itself, so If you user "creates" multiple validation errors, this provides a seriously bad UX. While we're at UX, your error messages could use some love: here's a little help from UX.SE
The easiest fix for this is to use binary flags, similar to the following:
[Flags]
Enum ValidatorFlags As Integer
   MonthSelect = 1 ' 0001
   YearSelect  = 2 ' 0010
   FilepathBox = 4 ' 0100
End Enum

Any combination of these flags is guaranteed to be backtraceable to the flags that are composing it (Sidenote: this is how linux permissions work).
As a sidenote: the Flags attribute as used in this enum and described more in depth in this SO question allows nice toString() magic (not that you'd need it). In the (currently) accepted answer there you also get a good lead on how you'd backtrace the original errors to the flags ;) The code also works fine without it though.
In addition to the mentined points and the very nice review by xDaevax (who also led me to the Flags question on SO), I want to mention that the names of your error message containers are gruesome.
Don't number your variables
Instead of Label1,2,3,... use descriptive names, just as you did in your InputFields
your code would then become somewhat like this:
Public Sub Validator 'leaving rest for brevity
    Dim Validator As ValidatorFlags
    If MonthSelectBox.Text = "" Then
       Validator |= ValidatorFlags.MonthSelect
       MonthErrorLabel.Text = "Please select a month."
    Else
       MonthErrorLabel.Text = ""
    End If

    If YearSelectBox.Text = "" Then
        Validator |= ValidatorFlags.YearSelect
        YearErrorLabel.Text = "Please select a year."
    Else
        YearErrorLabel.Text = ""
    End If

    If FilePathTextBox = "" Then
        Validator |= ValidatorFlags.FilepathBox
        FilepathErrorLabel.Text = "Please select a valid filepath."
    Else
        FilepathErrorLabel.Text = ""
    End If
    Return Validator
End Sub


Converting a ResourceSet of bitmaps into a sorted List I have a map. It can be zoomed-in and out. At first, I used one large image. Scrolling the mouse wheel defined the desired zoom level. Every scrolling created a new instance of the image in the desired dimensions. This approach was horribly slow.

So I gave up the possibility of zooming into any level, and created a list of predefined available zoom levels, ranging from 35% to 100% with 5% intervals, and then up to 300% with 50% intervals. For each zoom level, I have created a copy of the original image with the appropriate dimensions. The image name corresponds to its dimensions, so a 35% image is called "35.jpg". I added the images to the project's resources in a dedicated folder. Visual Studio automatically inserts an underline before the object's name because it starts with a number, so the object that represents the file is called "_35". So now, after the desired zoom level has been determined by the mouse wheel, the corresponding image is loaded from the resources. Performance has improved significantly.

Some of the application's components need a list of all available zoom levels. For example, for a ComboBox that allows the user to select a specific zoom level, rather than reach it through the mouse wheel. Therefore, when loading the form, a List<float> is initialized with all available zoom dimensions, so a 35% zoom is saved as 0.35 (a floating point representation is required by most components that uses the list) . The initialization is done by importing the names of the objects from the resources.

Here is the method that extracts file names and parse them into float. I feel it is not well written but I cannot point to a specific problem. I would love to hear your opinion. Thanks!

private static void InitializeZoomFactorsList()
{
    ResourceSet images = Properties.Resources.ResourceManager.GetResourceSet(CultureInfo.CurrentUICulture, true, true);
    List<string> names = images.Cast<DictionaryEntry>().Select(item => item.Key.ToString()).ToList();
    List<float> factors = names.ConvertAll<float>(delegate(string i) { return float.Parse(i.Substring(1, i.Length - 1)) / 100; });
    factors.Sort(); // because the list was strings, 300 came before 90, so after the parsing, I sort it by the value.
    zoomFactorsList = factors;
}

First of all let's try to make it more concise:

var zoomLevels = Properties.Resources.ResourceManager
    .GetResourceSet(CultureInfo.CurrentUICulture, true, true);
    .Cast<DictionaryEntry>()
    .Select(x => ParseZoomLevelAndNormalize(x.Key))
    .OrderBy(x => x);

Note that you do not need to create multiple temporary lists (not that you will ever note this waste) using ToList(). Also note that parsing code has been moved to a separate function. Let's talk about that...

static float ParseZoomLevelAndNormalize(object resourceName)
{
    string zoomLevel = Convert.ToString(resourceName).Substring(1);

    return Single.Parse(zoomLevel,
        NumberStyles.Number, CultureInfo.InvariantCulture) / 100;
}

If you do not thin it's clear enough then you should introduce separate functions to explain what it is doing:

var precalculatedMaps = new PrecalculatedMaps();
var zoomLevels = precalculatedMaps.ZoomLevels.Select(x => x / 100);

Where PrecalculatedMaps hides the implementation detail (now it's a resource file, in future might be a folder in file system). ZoomLevels property simply return a standard IEnumerable<float> of available zoom levels (in range [0...100]). Proof of concept:

sealed class PrecalculatedMaps
{
    public IEnumerable<float> ZoomLevels
    {
        get
        {
            if (_zoomLevels == null)
                _zoomLevels = ReadAvailableZoomLevels().OrderBy(x => x);

            return _zoomLevels;
        }
    }

    private IEnumerable<float> _zoomLevels;

    private static IEnumerable<float> ReadAvailableZoomLevels()
    {
        return Properties.Resources.ResourceManager
            .GetResourceSet(CultureInfo.CurrentUICulture, true, true);
            .Cast<DictionaryEntry>()
            .Select(x => ParseZoomLevel(x.Key));
    }

    private static float ParseZoomLevel(object resourceName)
    {
        string zoomLevel = Convert.ToString(resourceName).Substring(1);

        return Single.Parse(zoomLevel,
            NumberStyles.Number, CultureInfo.InvariantCulture);
    }
}

Note that here I made few assumptions which you can't ignore:

Resource names are valid numbers (otherwise Single.Parse() will throw an exception).
Numbers are formatted using en-US locale. In your code you're parsing using CultureInfo.CurrentCulture (the default if you do not specify any IFormatProvider). For integer numbers you will probably never have trouble but it's better to be sure, right?
There is always a leading underscore (that might be VS default but you can change resource name by hand). Do you want to handle the case? Change .Substring(1) with .TrimStart('_').
If you have only natural numbers then you can use NumberStyles.Integer instead of NumberStyles.Number (which allows decimals).

OK, that was about your actual code but let me say few words about the algorithm. Zooming an image is not an incredibly slow operation, I don't know how you did it and which technology you use for UI then I can't give you better ideas but:

You limit zooming to integer factors.
You can cache those generated images.
You can generate images only at special thresholds (for example 200%, 50%, 25%) leaving the exact scale in/out duty to UI controls (which are pretty good at this). This might not be applicable if your zoom algorithm is REALLY slow and undoubtedly better than canonical decimation/interpolation algorithms already in use.
You can debounce zoom requests to do not generate hundreds images when user is zooming from 100% to 10% and he's not interested in the intermediate images (leaving the duty to scale things to UI controls).


Binary search in functional-style Scala Curious to know how I can improve it, especially the pattern matching part seems a bit repetitive at the moment (lots of case x if ds(x))

  def binarySearch(ds: Array[Double], key: Double): Int = {
    @annotation.tailrec
    def go(low: Int, mid: Int, high: Int): Int = {
      mid match {
        case x if ds(x) == key => x
        case x if high <= low => -1
        case x if ds(x) < key => go(mid + 1, (high - mid + 1) / 2  + mid, high)
        case x if ds(x) > key => go(low, (mid - low) / 2 + low, mid - 1)
      }
    }
    ds.size match {
      case 0 => -1
      case _ => go(0, ds.size / 2, ds.size - 1)
    }
  }

the high <= low part does not involve x and could be pulled out of the case. The rest is fine IMHO.

One remark: the -1 return in the error-case is a bit of a smell - why not return Option[Int] instead?

And finally: I think you don't need mid as an argument - as you guard for low > high anyway you can as easily compute it inside your inner function and make the calls a bit more readable (only low and high)

Could look like this

  type Index = Int

  def binarySearch(ds: Array[Double], key: Double): Option[Index] = {
      @tailrec
      def go(lo: Index, hi: Index): Option[Index] = {
        if (lo > hi)
          None
        else {
          val mid: Index = lo + (hi - lo) / 2
          ds(mid) match {
            case mv if (mv == key) => Some(mid)
            case mv if (mv <= key) => go(mid + 1, hi)
            case _ => go(lo, mid - 1)
          }
        }
      }
      go(0, ds.size - 1)
  }


Simple Rock-Paper-Scissors to get more comfortable with OOP I'm trying to get a little more comfortable with using classes as they're meant to be used, instead of using them to decorate my code to make it look more legitimate. Can you see anything glaringly wrong/could be improved/possibly different implementations?

import random

class Player(object):

    def __init__(self,player):
        self.name = player
        self.score = 0
        self.choice = []

class Game(object):

    player_one,player_two = Player('player_one'),Player('player_two')

    def gameplay(self):
        choices = ['rock','paper','scissors']
        self.player_one.choice,self.player_two.choice = random.choice(choices),random.choice(choices)
        if self.player_one.choice == self.player_two.choice:
            print 'Tie!'
        elif self.player_one.choice == 'rock' and self.player_two.choice == 'paper':
            print '{0} is the winner with {1}!'.format(self.player_one.name,self.player_one.choice)
            self.player_one.score += 1
        elif self.player_one.choice == 'paper' and self.player_two.choice == 'rock':
            print '{0} is the winner with {1}!'.format(self.player_two.name,self.player_two.choice)
            self.player_two.score += 1
        elif self.player_one.choice == 'scissors' and self.player_two.choice == 'rock':
            self.player_two.score += 1
        elif self.player_one.choice == 'scissors' and self.player_two.choice == 'paper':
            self.player_one.score += 1
        elif self.player_one.choice == 'paper' and self.player_two.choice == 'scissors':
            self.player_two.score += 1
        elif self.player_one.choice == 'rock' and self.player_two.choice == 'scissors':
            self.player_one.score += 1
        print '{0}\'s score is {1}, and {2}\'s score is {3}'.format(self.player_one.name,self.player_one.score,self.player_two.name,self.player_two.score)

g = Game()
for i in range(0,10000):
    g.gameplay()

I think that one another class Choice will be useful. You have two functionality to move to this class:

make random choice. You can simple write def make_random(self):
compare two choices. You can define standard operators def __lt__(self, oth): and def __gt__(self, oth):. If you want handle ties than __eq__ operator will be useful also.

Then your gameplay function could be like

def gameplay(self):
    self.player_one.choice.make_random()
    self.player_two.choice.make_random()
    if self.player_one.choice > self.player_two.choice:
        self.player_one.score += 1
    elif self.player_one.choice < self.player_two.choice:
        self.player_two.score += 1


Password cracking commenting in Python I am having some difficulty with commenting my code for a Python password cracking application I have created. I have commented on the majority of the code. However, I was wondering if anyone could suggest anymore comments I need as my instructor is really stick on me commenting my code.

import time
import string

#Variables
max_attempts = 999999999 #the number of attempts the system makes for a brute-force attack
start       = time.time() #monitors the time length
chars       = list(string.printable) #all the possible ascii characters which the system uses to determine the password
base        = len(chars) #the base for conversion
n           = 0 #number of attempts
solved      = False
password    = input("Enter your password:") #the feature which allows the user to enter in their chosen password

print(chars) #record of previous password attempts

# converts number N base 10 to a list of digits base b
def numberToBase(n, b):
    digits = []
    while n: # takes n and the finds the modulus, the remainder of n % b
        digits.append(int(n % b)) # then it will append that to a list
        n //= b # following on it will then divide n into b
    return digits[::-1] #returns those digits into reverse order from -1, the end to the beginning

# checks if the user has inputted empty text/numbers/symbols
if password == '':

    print('Your password is empty')
    solved = True

elif password == chars[n]:
    print('Your password is ' + chars[n])
    solved = True

else:
    n = 1

#Begins systematically checking the password
if not solved:
    while n < max_attempts:
        list = numberToBase(n, base)
        print(list)
        word = ''
        for c in list: #loop through each of the characters in the list
            word += str(chars[c]) #adds the characters from the list to a word
        print(word)
        if password == word: #checks if the password equals to the word the system has generated
            solved = True # if the generation is correct the password will then commence to print statements
            print('***Results***')
            print('Password: ' + word)
            print('Attempts: ' + str(n))
            print('Time: ' + str((time.time() - start)) + ' sec')
            break #stops the loop
        else:
            n += 1 #however if the password generation isn't correct, we increment with n

# the password is beyond max_attempts
if not solved:
    print('Unsolved after ' + str(n) + ' attempts!')

1. The purpose of comments

Comments are a tool that you use in order to make code easier to understand and easier to maintain. But they are not the best tool to achieve that aim. Comments increase the amount of text that has to be read (you have to read the comment as well as the code) and there is a risk that when code is changed, a programmer will forget to change the nearby comments, leading to nonsense like the comments in this question.

So comments are a last resort when you can't make the code clear enough by other means. Before writing a comment you should ask these questions:

Do functions have documentation explaining their arguments and results? (In Python, do they have docstrings?)
Are there test cases (or documentation examples) demonstrating the correct behaviour of the code?
Do function names clearly describe what they do? And do variable names clearly indicate the meaning of their values?
Is the code written in the simplest, clearest way?

Only when the answers are all "yes", and the code is still not clear, should you consider writing a comment.

2. Worked example

Let's take the numberToBase function and ask these questions:

# converts number N base 10 to a list of digits base b
def numberToBase(n, b):
    digits = []
    while n: # takes n and the finds the modulus, the remainder of n % b
        digits.append(int(n % b)) # then it will append that to a list
        n //= b # following on it will then divide n into b
    return digits[::-1] #returns those digits into reverse order from -1, the end to the beginning

There's no documentation. Let's turn the first comment into a docstring:

def numberToBase(n, b):
    """Convert the number n to base b and return a list of digits."""
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return digits[::-1]

There are no examples. Let's add some:

def numberToBase(n, b):
    """Convert the number n to base b and return a list of digits.

        >>> numberToBase(1234, 10)
        [1, 2, 3, 4]
        >>> numberToBase(1023, 2)
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    """
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return digits[::-1]

These are in the form of doctests so that they can be automatically checked using the doctest module.
There are bunch of improvements we can make to the names. (i) Something like number_to_digits would be clearer than numberToBase since the result is a list of digits. (ii) base would be clearer than b. (iii) The built-in function divmod would make it clear that we are computing the division and modulus. (iv) The name digit for the modulus would make its meaning clear. (v) Using the built-in functions list and reversed would make it clear that we are computing a list in reverse order.

def number_to_digits(n, base):
    """Convert the number n to a list of digits in the given base.

        >>> number_to_digits(1234, 10)
        [1, 2, 3, 4]
        >>> number_to_digits(1023, 2)
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    """
    digits = []
    while n:
        n, digit = divmod(n, base)
        digits.append(digit)
    return list(reversed(digits))

The code seems clear and simple now: there is no need to add any comments.

3. Other review points

When n is 0, the result is an empty list. It might be better to return the list [0].
When b is 1, the function goes into an infinite loop. It might be better to raise an exception in this case.