Android recycler view adapter filter I am trying to optimize the filter method for RecyclerView Adapter in Android. The list is used as an ArrayList. I have seen this post but they are filtering from the original list every time. They are not using old results if a character is added.

Example: if there are 10 results for String 'a' then user type 'm' , 'am' results are subset of 'a' results.

Please suggest code optimizations for this method and any test-case where it fails.

public void filter(String s) {
    if (TextUtils.isEmpty(s)) {
        mList.clear();
        mList.addAll(copyList);
        notifyItemRangeRemoved(0, getItemCount());
        notifyItemRangeInserted(0, mList.size());
    } else {
        boolean isBackDirection = false;
        List<WeekWorkBean> tempList = null;
        if (s.length() < oldFilter.length()) {
            tempList = new ArrayList<>();
            tempList.addAll(mList);
            mList.clear();
            mList.addAll(copyList);
            isBackDirection = true;

        }
        for (int i = 0; i < mList.size(); i++) {
            WeekWorkBean bean = mList.get(i);
            if (!bean.getEmpName().toLowerCase().startsWith(s.toLowerCase())) {
                mList.remove(i);
                if (!isBackDirection) {
                    notifyItemRemoved(i);
                }
                i--;
            } else if (isBackDirection) {
                if (tempList.size() != 0) {
                    for (WeekWorkBean b : tempList) {
                        if (!bean.getEmpId().equals(b.getEmpId())) {
                            notifyItemInserted(i);
                        }
                    }
                } else {
                    notifyItemInserted(i);
                }
            }
        }

        oldFilter = s;
    }
}

Consider using iterator instead of for-looping. That will get rid of your index manipulation (decrement if element is removed).

Iterator iterator = mList.iterator();
while(iterator.hasNext()){
   Element e = iterator.next();
   if(shouldRemove(e)){
       iterator.remove();
   }
}

Is there a performance requirement that necessitate implementation of such algorithm? In most cases, implementing conventional interfaces make code readable and modular and you'll probably benefit from performance increase should the way Android perform filtering is optimised further down the road, without doing anything.

In any case, what makes you think that this implementation is faster? Your reliance on copying ArrayLists may prove wasteful if the unfiltered list is exceptionally large.


Find sub-list index with the closest to a given number sum The task that I have to perform is to take an array of a specific length, and figure out which sub-list has the closest sum to another given number. Then, I need to print the index of that sub-array.
For anyone that doesn't understand this problem, we add up indexes of the given list and the moment their sum exceeds or is equal to the required amount of power (the second number in the second line of the input), we append it to another list and then we append the index of the number we started to count from and the index of the number we stopped adding up to a third list. Afterwards, we start from the next index. For example, in this input, if we start counting from the list index 0, we will see that if we keep adding up until index 6, the sum will be 28. We keep repeating this, but this time from the index 1, then 2, 3, 4 etc. When we finish, we will realise that the number with the closest sum to 23 are the numbers 7, 8, 9 which range from 6 to 8 and have a sum of 24. So, we print: 6 8.
And if anyone is wondering, if we end up with multiple ranges that meet the criteria, we will choose, according to the problem statement, the nearest to the entrance, the one with the
lowest starting index and the lowest ending index. In our case we have looked out for it, because every time time we append the indexes sum in server_lst we append their indexes too at the same time in index_lst. So, the indexes that are printed are the first ones that have the best sum.
num_of_cases = int(input())
for case in range(num_of_cases):
    num_of_servers, c_power = map(int, input().split())
    server_lst = list(map(int, input().split()))
    server_total = []
    server_index = []
    j = 0
    total = 0
    k = 0

    def servers(lst, k):
        global total
        global j
        for i in range(k, len(lst)):
            if total < c_power:
                total += lst[i]
                j += 1
            else:
                server_total.append(total)
                j += k
                server_index.append([k, j-1])
                j = 0
                total = 0
                break

    def execute(server_lst, k):
        for i in range(len(server_lst)):
            k = i
            servers(server_lst, k)
        min_pow = min(server_total)
        winner = server_total.index(min_pow)
        mf = server_index[winner]
        print('Case #{}:'.format(case+1), *mf )

    execute(server_lst, k)

The problem that I am currently encountering is that, although it works, it takes around 10 minutes to run 10MB inputs. Is there anyway that I can improve it so it runs faster?
Here is a very simple input:
1
10 23
1 2 3 4 5 6 7 8 9 10

and the output to this is:
Case #1: 6 8

The constraints are:

1 ≤ num_of_cases ≤ 20.
1 ≤ servers ≤ 100 000.
1 ≤ amount of power required(c_power) ≤ 1 000 000 000.
1 ≤ power of every server(every index in server_lst) ≤ 1 000 000, for i = 0 … N − 1

Thanks in advance.

Ah ha!  Your example output showed the result 6 8.  Using 1-based indexes (common in certain programming challenges), server_lst had in that sub-list the values [6, 7, 8] whose sum is 21, which is close to the target value of 23.  I was looking at total < c_power, and thought I was looking at a bug since it would be ignoring a sub-list that totalled exactly 23 as too large.
Your "very simple input" is actually confusing, since server powers and indices are not distinct values.  Similarly, the sorted order gives no clear indication of whether 0-based or 1-based indices are returned.
The lack of good comments, an inaccessible problem statement, and confusing code made it hard to tell what the code was intended to do, which made "reviewing the code" a difficult and error-prone task.
Now that I understand what is going on, let's do both: review the code and optimize it.

Code Review
Naming
Your functions and variables are a mix of understandable names (num_of_cases, and num_of_servers) and completely opaque names that don't convey any meaning (execute, and mf).
Globals
Global variables have their place.  This isn't it.
The function servers returns nothing, but calls out total and j as global variables it will be reading and writing.  It turns out that it is actually modifying server_total and server_index as well.
More likely that not, the total and j variables need not have been global, and could simply have been initialized to zero at the start of the function.  Except that if the loop inside servers reaches the end of the loop without exceeding c_power, then j and total are not cleared, and the next call to servers will continue where they left off.  Was this intentional?  Some kind of wrap-around?  It doesn't seem likely, since the starting point k on the next call is not the start of the list, so odds are this is actually a bug.
Unnecessary parameters and variables
    def execute(server_lst, k):
        for i in range(len(server_lst)):
            k = i
            servers(server_lst, k)

What is the point of k?  Both of them.
The execute function requires a k argument, but whatever value is given will be ignored, overwritten by k = i before it is ever used.
Inside the for loop, the value of i is stored in k.  Then, neither I nor k is modified inside the body of the loop, nor used outside of the loop.  i == k remains true as long as both variables are in scope.  Which begs the question of: why use k instead of i?
Don't define functions inside of loops
This one can really result in strange behaviour.
for _ in range(2):
    try:
        f()
    except NameError:
        print("f() didn't exist")

    def f():
        print("Hello world")

Output:
f() didn't exist
Hello world

Write for testing
If you structured your code as a function which solved the problem, and used a main guard to run the code when submitted to the programming challenge site ...

def find_minimum_power_sublist(server_powers, required_power):
    # ... implementation omitted ...
    return start, end

def main():
    num_cases = int(input())

    for case in range(1, num_cases+1):
        num_servers, required_power = map(int, input().split())
        server_powers = list(map(int, input().split()))

        start, end = find_minimum_power_sublist(server_powers, required_power)
        print('Case #{}:'.format(case), start, end)

if __name__ == '__main__':
    main()

... then you could write a test program which runs sample cases, something like:
from solution import find_minimum_power_sublist

def test(test_name, powers, required_power, expected):
    actual = find_minimum_power_sublist(powers, required_power)
    if expected == actual:
        print(test_name, "passed.")
    else:
        print(test_name, "failed!  Expected:", expected, actual)

def run_tests():
    test("1-10", [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 23, (6, 8))
    # ... more test cases here ...

if __name__ == '__main__':
    run_tests()

There are test frameworks which make testing easier.  Look into pytest, unittest, and doctest.  Those will get you started, but there are many others you can try.
Optimization
Partial Sums
Whenever you see a problem where you are adding up a sequence of numbers, starting and ending at different points, you should stop and ask if there is a better way.
In your example, you have the numbers 1 2 3 4 5 6 7 8 9 10, and you first start with 1, then 1+2, then 1+2+3, and so on, until you arrive at the total of 1+2+3+4+5+6+7 or 28.  Then you reset and start 2, 2+3, 2+3+4, and so on until you reach 2+3+4+5+6+7 or 27.  Then you reset and start at 3 and compute 3+4, 3+4+5, 3+4+5+6, 3+4+5+6+7 or 25.  Then you reset and start 4, 4+5, 4+5+6, 4+5+6+7, 4+5+6+7+8 or 30.
How many times have you added 4 and 5 together?  Or phrased a better way, how many times have you added 5 to a previous sum that included the four term?  Only four times.  Not a lot.  But this is an example with only 10 servers.  You could have one hundred thousand servers and a fairly high power threshold to exceed.  You could be repeatedly add a specific server value to a previous total thousands of times, and since you can have thousands of individual server values, you've got an \$O(N^2)\$ algorithm.
Instead, consider a running total of the values: 1 3 6 10 15 21 28 36 45 55.  We've added the server value to the previous total exactly once.  From that list, you can get the sum of any sublist of servers.  For instance the sum of server values from index 6 to index 8 would be the sum of server values up to index 8, 45, less the sum of server values up to index 5, 21.  45-21=24.  After processing the list of N servers, doing a total of N additions, you can get the sum of any sublist with at most one subtraction!
As exciting as this sounds, this hasn't actually improved anything.  Using the same steps above, algorithm would still start with 1-0, 3-0, 6-0, 10-0, 15-0, 21-0, 28-0, then reset to 3-1, 6-1, 10-1, 15-1, 21-1, 28-1, and then reset to 6-3, up to 28-3, then reset to 10-6 up to 36-6, and so on.  Instead of doing one addition per loop step, we're doing one subtraction per loop step.
Why reset to the beginning?
After adding the server power values until you exceeded the requirement, why reset the sequence and walk up to the threshold again?  Why not simply advance the starting point of the sublist until the threshold is no longer reached?

We move the end-point forward until the difference is greater than or equal to the requirement: 1-0, 3-0, 6-0, 10-0, 15-0, 21-0, 28-0.
Then we walk the start-point forward until we dip below the requirement: 28-1, 28-3, 28-6.
Then we return to walking the end-point forward until the requirement is met again: 36-6.
Then we return to walking the start-point forward: 36-10, 36-15.
Walk end-point forward: 45-15.
Walk start-point forward: 45-21, 45-28.
Walk end-point forward: 55-28.
Walk start-point forward: 55-36
Walk end-point forward: end-of-list

More concisely,

While the total power requirement is not satisfied,

walk the end-point forward

While the total power requirement is satisfied,

If total power is smaller than the smallest found so far:

update the smallest found so far, and memorize the start and end points.

walk the start-point forward

Note we're only walking the start-point and end-point forward through the list once.  This is \$O(N)\$.
Running totals
You don't have to precompute and store the running totals.  You could just keep two running totals as you move the starting point and ending point forward.
You don't even need two totals.  Just add or subtract from a single running total.  Or consider the total a surplus, and initialize it with the negative of the power requirement.  When surplus >= 0, the power requirement is satisfied; when surplus < 0, the power requirement is not satisfied.


Generating Heighway dragons in Unity C# I'm basically looking for a general critique. I'm just starting out and would like to know if I should have done anything differently to make it faster or to make it much more readable. I don't know exactly what happened but I tried it with 14 iterations and it took about 3 minutes to complete. It crashed Unity at 15 and after a restart, completed 15 iterations in half a second. I have a feeling I should just cut the dragon list and add the vertices to the Line Renderer as they're generated but I feel like the way it is now might be easier to read.

Are there any more corners I could be cutting? I lost indentation on the body of the class when I pasted it into the codeblock.

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class HeighwayGenerator : MonoBehaviour {
private List<char> direction;
private List<Vector3> dragon;
private Stack <char> stack;
private LineRenderer line;
private float magnitude = 0.0f;

public int iterations = 4;

void Start () {
    direction = new List<char> ();
    stack = new Stack <char> ();
    dragon = new List<Vector3> ();
    line = GetComponent<LineRenderer> ();

    //generate turn list
    generateDirection (iterations);

    //set start direction. Vector3.forward is axis of rotation (0,0,1)
    transform.Rotate (Vector3.forward, (float)iterations * 45.0f);

    //find segment length of fully iterated list. magnitude of 0th iteration is 10 units from (-5,0) to (5,0)
    magnitude = 10.0f / (Mathf.Pow (Mathf.Sqrt (2), iterations));

    //generate vertices and fill dragon
    generateVertices ();

    //draw line
    line.SetVertexCount (dragon.Count);
    for (int i = 0; i < dragon.Count; i++) {
        line.SetPosition(i, dragon[i]);
    }
}

void generateDirection(int _iteration) {
    // Heighway dragon is generated from an initial direction and a list of turns.
    // This list is generated by:
    // 1.Pushing previous list into stack.
    // 2.Appending 'R'
    // 3.Appending reversed and 'negated?' previous list from stack.

    if (direction.Count == 0) {
        direction.Add ('R');
        _iteration -= 1;
    }
    if (_iteration <= 0) {
        return;
    }
    int _tempCount = direction.Count;
    direction.Add ('R');

    // Reverse and negate previous iteration
    for (int i = 0; i < _tempCount; i++) {
        stack.Push(direction[i]);
    }
    for (int i = 0; i < _tempCount; i++) {
        char _tempChar = stack.Pop ();
        if (_tempChar == 'R') {
            direction.Add ('L');
        }
        if (_tempChar == 'L') {
            direction.Add ('R');
        }
    }
    generateDirection (_iteration - 1);
}

void generateVertices() {
    //initial position
    dragon.Add (transform.position);
    //first translation
    transform.position += magnitude * transform.right;
    //second position
    dragon.Add (transform.position);

    // turn/translate/add -- transform.right is forward on XY plane. Vector3.forward is axis of rotation (0,0,1)
    for (int i = 0; i < direction.Count; i++) {
        if(direction[i] == 'R'){
            transform.Rotate (Vector3.forward, -90.0f);
            transform.position += magnitude * transform.right;
            dragon.Add (transform.position);
        }
        if (direction[i] == 'L') {
            transform.Rotate (Vector3.forward, 90.0f);
            transform.position += magnitude * transform.right;
            dragon.Add (transform.position);
        }
    }
}
}

Some quick coding style remarks:

I'm not a fan of K&R style brackets, and it's a style rarely seen in C# code.
I like to see access modifiers on everything. Makes things a lot clearer.
generateDirection, generateVertices etc: method names should be in PascalCase.
You use the opposite of the usual C# style of having underscores in front of private instance field names, instead you use them for parameters. This is very confusing.
'L' and 'R' are used repeatedly, so why not convert these into constants?
Why do you leave a space between your method name and the bracket, e.g. direction.Add ('R');?
direction and dragon are List<T>s, yet their names do not indicate that they are collections. Collection names should be plural, IMHO. I'd even argue this should be the case for Stack<char> stack, though that is a borderline case.
Comment should tell me why, not what. If the method call is generateVertices();, I shouldn't need to be informed //generate vertices and fill dragon -- unless your method name doesn't tell me everything I need to know.
generateDirection starts with a multi-line comment explaining what the method does. I'd expect such an explanation in the <summary>, not in the body of the method.
public int iterations = 4; Why is this public? Why isn't this a const? Is it your intention that this amount can be changed by code calling the HeighwayGenerator? If so, than it should be a property with a getter/setter, or perhaps you should keep iterations private and only allow it to be changed through a method.

Concerning this logic:

for (int i = 0; i < _tempCount; i++) {
    char _tempChar = stack.Pop ();
    if (_tempChar == 'R') {
        direction.Add ('L');
    }
    if (_tempChar == 'L') {
        direction.Add ('R');
    }
}

I fail to see how _tempChar (a badly named variable, by the way) can be anything other than 'L' or 'R', so the second if can just as well be an else.

But this code can be even simpler:

for (int i = 0; i < _tempCount; i++) {
    direction.Add((stack.Pop() == 'R') ? 'L' : 'R');
}

The same remark as the previous one can be said of this code:

if(direction[i] == 'R'){
    transform.Rotate (Vector3.forward, -90.0f);
    transform.position += magnitude * transform.right;
    dragon.Add (transform.position);
}
if (direction[i] == 'L') {
    transform.Rotate (Vector3.forward, 90.0f);
    transform.position += magnitude * transform.right;
    dragon.Add (transform.position);
}

You seem to have copy-pasted three lines which are almost identical for both cases, except for one parameter. If you're doing that, you should extract those lines into a method, or if you feel that's overkill you should simplify your code:

for (int i = 0; i < direction.Count; i++) {
    transform.Rotate (Vector3.forward, (direction[i] == 'R' ? -90.0f : 90.0f));
    transform.position += magnitude * transform.right;
    dragon.Add (transform.position);
}


Min sub array size with a given sum How can the time complexity of the following code be improved (assuming it's \$O(N^2)\$)? What about style and patterns?
This code is trying to find the minimum subarray size that adds up to given sum k. Elements should be adjacent.

/**
 * Created by mona on 5/24/16.
 */
public class MinSubArray {

    public static void minSubArray(int[] a, int k){

        int start=-1;
        int end=-1;
        int min=Integer.MAX_VALUE;

        for (int i=0; i<a.length; i++){
            int tmpSum=0;
            for (int j=i; j<a.length && (j-i+1)<min ; j++){
                tmpSum+=a[j];
                if (tmpSum==k){
                    start=i;
                    end=j;
                    min=end-start+1;
                    break;
                }
                if (tmpSum>k){
                    break;
                }
            }
        }

        if (start==-1 || end==-1){
            System.out.println("No such array exists with sum of "+k);
        }
        while (start<=end){
            System.out.print(a[start]+" ");
            start++;
        }

    }

    public static void main(String[] args){
        int a[] ={1,2,3,-1,2,4,8,9,5,6,-2,-3,10};
        minSubArray(a,5);

    }
}

1 Coding conventions

The Java coding conventions dictate that any for, if, while construct is preceded by a blank line. So instead of

int dummy = 10;
for (int i = 0; i < dummy; ++i) {
    ...
}

you should write

int dummy = 10;

for (int i = 0; i < dummy; ++i) {
    ...
}

Next, you have no space after the conditions of if statements: Instead of

if (testCondition()){
    ...
}

you should write

if (testCondition()) { // Note the space before '{'!
    ...
}

2 Algorithm

Printing to standard output in an algorithm is a no-no. Suppose you want to use your implementation in a real-world project. Apart from flooding the stdout, you waste time since calling System.out.print* goes down through the Java virtual machine straight to the OS, and is, thus, expensive. So, it would be nicer just return an integer whose value is the index of the leftmost element of the solution.

3 Summa summarum

All in all, I thought about this reimplementation:

public static int minSubArrayV2(final int[] array, final int targetSum) {
    if (targetSum == 0) {
        // Special case: return the index of the first array component whose
        // value is zero.
        for (int i = 0; i < array.length; ++i) {
            if (array[i] == 0) {
                return i;
            }
        }

        return -1;
    }

    if (targetSum > 0) {
        for (int startIndex = 0; startIndex < array.length; ++startIndex) {
            int sum = 0;

            for (int i = startIndex; i < array.length; ++i) {
                sum += array[i];

                if (sum > targetSum) {
                    break;
                } else if (sum == targetSum) {
                    return startIndex;
                }
            }
        }
    } else {
        for (int startIndex = 0; startIndex < array.length; ++startIndex) {
            int sum = 0;

            for (int i = startIndex; i < array.length; ++i) {
                sum += array[i];

                if (sum < targetSum) {
                    break;
                } else if (sum == targetSum) {
                    return startIndex;
                }
            }
        }
    }

    return -1;
}

Hope that helps.

A note

I spent about two hours thinking about how to improve the time complexity of your algorithm, and did not find any opportunity. However, you could spent \$\Theta(N^2)\$ for preprocessing the array, after which you can do queries in constant time. Consider the following:

public static Map<Integer, Integer> preprocessArray(final int[] array) {
    final Map<Integer, Integer> map = new HashMap<>();

    for (int startIndex = 0; startIndex < array.length; ++startIndex) {
        int sum = 0;

        for (int i = startIndex; i < array.length; ++i) {
            map.putIfAbsent(sum += array[i], startIndex);
        }
    }

    return map;
}

void foo(int[] array) {
    Map<Integer, Integer> map = preprocessArray(array);
    System.out.println(map.get(6));
}


IntArray implementation I need to write an IntArray implementation for college. I'm wondering if my code could be better and if it is efficient. In the header file are the methods listed that we need to write.

Header file:

 #ifndef INTARRAY_H_
 #define INTARRAY_H_

 #include <iostream>
 using namespace std;

 class IntArray{
 private:
     int length;
     int * data;
public:
    IntArray(int size = 0);
    IntArray(const IntArray& other);
    IntArray& operator=(const IntArray& original);

    int getSize() const { return length; };
    int& operator[](unsigned int i);
    void resize(unsigned int size);
    void insertBefore(int value, int index);

    friend ostream& operator<<(ostream& out, const IntArray& list);

    ~IntArray(){ delete[] data; };

 };
 #endif

Cpp file:

    IntArray::IntArray(int size){
        length = size;
        data = new int[size];
        for(int i = 0;i<size;i++){
             data[i] = 0;
        }
    }
    IntArray::IntArray(const IntArray& other){
        length = other.length;
        data  = new int[length];
        for(int i =0;i<length;i++){
        data[i] = other.data[i];
        }
    }

IntArray& IntArray::operator=(const IntArray& other){
    if(this = &other){
        return *this;
    }
    length = other.length;
    data = new int[length];
    for(int i = 0; i <length;i++){
        data[i] = other[i];
    }
    return *this;
}
void IntArray::resize(unsigned size){
      if (size <= length){
        length = size;
        return;
     }
     int * temparr = new int[size];
     // copy data
     for (int i = 0; i < length; ++i){
        temparr[i] = data[i];
     }
     delete [] data;
     data = temparr;
     length = size;
}

int& IntArray::operator [](unsigned i){
    if(i >= length || i < 0){
        throw "index out of bounds";
    }
    return data[i];
 }

 void IntArray::insertBefore(int d, int index){
     if(index >= length){
         throw "index out of bounds";
     }
     resize(length + 1);
     for(int i = length -1;i>index;i--){
          data[i] = data[i-1];
     }
     data[index] = d;
 }

Main changes:

Assuming you keep an int length, check for size >= 0 in constructor IntArray(int size = 0);, and in void IntArray::insertBefore(int d, int index)
You thought about delete[] data in the destructor. However, there are other places in your code where data needs to be deleted: each time you change data's value, you need to deallocate what used to be pointed by data. Ie, delete[] data before any data =

You added data = new int[length]; in the copy constructor, so you've solved the out of bound issue, but introduced a memory leak instead. You need to deallocate data first.
Same for the assignment constructor.
resize had an out-of-bound issue you've fixed

Code used to be:

void IntArray::resize(unsigned int size){
    for(int i=length; i<size; i++){
        data[i] = 0;
    }
    length = size;
}

(Note: you're not supposed to edit your code, or put your updated code in a separate section, at the bottom of your question)

Opinion-based

Maybe use an unsigned type (like std::size_t) instead of the signed int for the length.

Pros:

You enforce the invariant "the length can only be positive"

Cons:

Special values (like -1 for "Index not found") will look like regular values, higher risk of underflow.
(see Herb Sutter comment at 44:30)

Other

Superfluous this-> in operator[](int index)
Style: pick one of length or getSize()to get the data length, but don't mix the two (Here length is fine, in classes where you'd like to make a check before accessing the value, getSomething() is better.
Add a const version of operator[](int index)
Don't add an extra space at the end of operator<< (which you removed by mistake)

Going further

It depends on the assignment.

Optimization: Introducing capacity to reduce the number of allocations/deallocations
Add iterators
Add convenience methods (bool empty() const;, int& front();)
Add typedefs like typedef int value_type (useful for for metaprogramming)
Add relationship operators (at least == and !=)

@glampert made excellent points I forgot, check his answer.


Extracting top subreddits from an HTML table I'm scraping a table and am trying to get nested td tags down the tbody tree but the code seems kind of verbose.  Is there a more Pythonic way to do this?

def get_top_subreddits(url):

    r = urllib.request.urlopen(url).read()
    soup = BeautifulSoup(r, "lxml")

    body = soup.find_all('tbody')

    top_subreddits = []
    for i in body:
        trs = i.find_all('tr')
        for tr in trs:
            tds = tr.find_all('td')
            for td in tds:
                texts = td.get_text()
                if '/r/' in texts:
                    top_subreddits.append(texts)
    return top_subreddits

Yes, there is a more concise way to do it - using CSS selectors and a list comprehension:

top_subreddits = [
    td.get_text()
    for td in soup.select("tbody tr td")
    if '/r/' in td.text
]

tbody tr td would locate all td elements under tr elements which are under tbody.

I don't really like getting texts of td elements twice here, there is possibly a way to filter the desired information directly. E.g. if you were up to the subreddit links, we could've applied the /r/ check inside a selector:

top_subreddits = [
    a.get_text()
    for a in soup.select('tbody tr td a[href^="/r/"]')
]

^= here means "starts with".


Simple winform that randomizes images in a picturebox I wrote this code for a simple app that gives us random images. The code works, but I feel like I'm doing something wrong. And one thing I would love to know is instead of grabbing from a folder called "resources", we would actually grab from a custom folder inside my exe. So there's no need to add any folder to a different computer, all works inside the exe.

Is that possible to do ?

I'm slowly learning C#. Thank you for your time in reading my post.

P.S I'm very new in using the Lambda expression.

 public partial class Menu : Form
{
    private string[] files;
    private string[] files2;
    private string[] files3;
    private string[] files4;
    private int currentIndex = 0;
    private int currentIndex2 = 0;
    private int currentIndex3 = 0;
    private int currentIndex4 = 0;
    Random rnd = new Random();

    public Menu()
    {
        InitializeComponent();
    }

    private void initializeImages()
    {
        string appRoot = System.IO.Path.GetDirectoryName(Application.ExecutablePath);
        files = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files2 = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files3 = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files4 = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files = files.OrderBy(x => rnd.Next()).ToArray();
        files2 = files.OrderBy(x => rnd.Next()).ToArray();
        files3 = files.OrderBy(x => rnd.Next()).ToArray();
        files4 = files.OrderBy(x => rnd.Next()).ToArray();
    }

    private void setImage()
    {
        pictureBox1.ImageLocation = files[currentIndex];
        pictureBox2.ImageLocation = files2[currentIndex2];
        pictureBox3.ImageLocation = files3[currentIndex3];
        pictureBox4.ImageLocation = files4[currentIndex4];
    }

    private void nextImage()
    {
        currentIndex = currentIndex < files.Length - 1 ? currentIndex + 1 : files.Length - 1;
        setImage();
    }

    private void button1_Click(object sender, EventArgs e)
    {
        initializeImages();
        nextImage();
    }

}

private void initializeImages()
    {
        string appRoot = System.IO.Path.GetDirectoryName(Application.ExecutablePath);
        files = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files2 = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files3 = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files4 = System.IO.Directory.GetFiles(appRoot + @"\Resources");
        files = files.OrderBy(x => rnd.Next()).ToArray();
        files2 = files.OrderBy(x => rnd.Next()).ToArray();
        files3 = files.OrderBy(x => rnd.Next()).ToArray();
        files4 = files.OrderBy(x => rnd.Next()).ToArray();
    }

Here you load the same file names into four different arrays of strings. This is very memory inefficient and unnecessary. Instead only load them once into a single array and shuffle that when you want to change the images in the picture boxes.

In general: when you feel the need to add indices to the names of a set of variables like you do, you should reconsider your design - and you'll probably realize that an array or list or other kind of collection is the solution.

Random rnd = new Random();

In general: avoid abbreviated names of properties, fields, methods, object/classes etc. Provide descriptive names and let intellisense in the IDE do the work for you. Here random or randomGenerator would be descriptive names.

private void button1_Click(object sender, EventArgs e)
    {
        initializeImages();
        nextImage();
    }

Here you repeatedly reload the image file names. This makes sense if the number of images in the location changes - but you look in a sub folder to the installation folder which indicates that they are rather constant, so no need to do it other than when the form loads.

Below I've tried to refactor your code while implementing the above suggestions:

private string[] imageFileNames;
Random random = new Random();

public Menu()
{
  InitializeComponent();

  InitializeImages();
}

private void InitializeImages()
{
  imageFileNames = Directory.GetFiles(Path.Combine(Path.GetDirectoryName(Application.ExecutablePath), "Resources"));
}

private void ShuffleImages()
{
  Array.Sort(imageFileNames, (a, b) => random.Next(0, 3) - 1);
}

private void SetImages()
{
  var picturBoxes = new[] { pictureBox1, pictureBox2, pictureBox3, pictureBox4 };

  for (int i = 0; i < picturBoxes.Length; i++)
  {
    picturBoxes[i].ImageLocation = imageFileNames[i % imageFileNames.Length];
  }
}

private void button1_Click(object sender, EventArgs e)
{
  ShuffleImages();
  SetImages();
}

If the number of images is limited you can consider to load them all once into an list of Image objects and then shuffle these instead of the file names.

private void InitializeImages()
{
  images = Directory
    .GetFiles(Path.Combine(Path.GetDirectoryName(Application.ExecutablePath), "Resources"))
    .Select(fn => Image.FromFile(fn)).ToArray();
}


class and object in php i just wanted to confirm if my codes below is correct. Feel free to make corrections.

<?php
class createConnection
{
var $host="localhost";
var $username="root";
var $password="";
var $database="wilbert";
var $myconn;

function connectToDatabase()
{
$conn = mysql_connect($his->host,$this->username,$this->password);
if (!$conn)
{
    die ("Cannot connect to the database");
}

else
{
    $this->myconn = $conn;
    echo "Connection established!";
}
return $this->myconn;

}
function selectDatabase()
{
mysql_select_db($this->database);
if(mysql_error())
{

    echo "Cannot find the database ".$this->database;
}
else
{
echo "Database selected..";
}

}
function selectData()
{
mysql_select_db($this->database);

$result = mysql_query(" SELECT a.student_id, a.FirstName, b.First_Name FROM Student a        LEFT JOIN teacher b ON a.student_id = b.student_id");

echo "

Student_ID
First_Name
First_Name

";

while($row = mysql_fetch_array($result))
  {
  echo "
";
  echo "" . $row['student_id']. "	";
  echo "" . $row['FirstName'] . "	";
  echo "" . $row['First_Name'] . "	";
  //echo "" . $row['student_id'] . "	";
  echo "
";
  }
echo "
";
}

function closeConnection()
{
mysql_close($this->myconn);
echo "connection closed!";
}

}
?>

and here is my object.

<?php

include ('phpclass.php');

$connection = new createConnection(); //i created a new object

$connection->connectToDatabase(); // connected to the database

echo "
"; // putting a html break

$connection->selectDatabase();

echo "
";

$connection->selectData();
//$connection->closeConnection();// closed connection
?>

I am a fan of loose coupling so I would suggest that you take the values of host, username, password and database out of your class. Pass the values through the constructor and set them in the constructor. This makes it easier to reuse your code.

Second, in classes such as one that creates a connection to a database I would not "echo" stuff. You better throw exceptions on error or return meaningful values to the caller.

Last, I'd suggest other names. This might be nitpicking but this has more meaning to me:

$connection = new DatabaseConnection();
$connection->open();
$connection->connectDatabase();

So, wrapped up I would have something like:

<?php
class DatabaseConnection
{
    var $host;
    var $username;
    var $password;
    var $database;
    var $myconn;

    function __construct($dbhost, $user, $pass, $db)
    {
        $this->host = $dbhost;
        $this->username = $user;
        $this->password = $pass;
        $this->database = $db;
    }

    function open()
    {
        $conn = mysql_connect($his->host,$this->username,$this->password);
        if (!$conn)
            throw new Exception('Error establishing a connection.');
        else
            $this->myconn = $conn;

        return $this->myconn;
    }

    function connectDatabase()
    {
        mysql_select_db($this->database);
        if(mysql_error())
            throw new Exception("Cannot find the database " . $this->database);
    }

    function selectData($query)
    {
        mysql_select_db($this->database);
        $result = mysql_query($query);
        return $result;
    }

    function closeConnection()
    {
        mysql_close($this->myconn);
    }
}
?>

Usage:

$connection = new DatabaseConnection("localhost", "root", "", "wilbert");
$connection->open();
$connection->connectDatabase();
$connection->selectData("SELECT a.student_id, a.FirstName, b.First_Name FROM Student a LEFT JOIN teacher b ON a.student_id = b.student_id");

See how the other names make more sense? Try to avoid verbs as a classname. Methods can and most likely will be or contain verbs, but not classnames. Also, leaving the query out of the class leaves you the option to use the same code for other queries.

Note that this is no perfect code, I was only suggesting what might be changed. Hope this helps! :)

Edit:

You call the function selectData() and pass the query-string as a parameter. This changes nothing, it gives the same result as your code. Only in my case you can pass other queries to the function whereas your function is limited to the embedded query.

Now for the result. This has also to do with the decoupling of your connection-class and what will be shown to the user. I showed u the usage of the class, the code below is how you can process the result. Create a function (but not in the connection class!) that returns the result in a table:

function resultTable($sqlResult)
{
    $table = "
";
    $table .= "
Student_ID	First_Name	First_Name
";

    while($row = mysql_fetch_array($sqlResult))
    {
        $table .= "
" . $row['student_id']. "	";
        $table .= "" . $row['FirstName'] . "	";
        $table .= "" . $row['First_Name'] . "
";
    }
    $table .= "
";

    return $table;
}

And the usage:

$connection = new DatabaseConnection("localhost", "root", "", "wilbert");
$connection->open();
$connection->connectDatabase();
$result = $connection->selectData("SELECT a.student_id, a.FirstName, b.First_Name FROM Student a LEFT JOIN teacher b ON a.student_id = b.student_id");
echo resultTable($result);

You could create a new class in which you define all sorts of methods like these to process a result and return it to the view-file where you will show it on the screen. Hope this clarifies it. :)


Manipulating the browser history I created a table with the ability to edit with popup.

This part of the code, which includes:

the ability to send URL to other users with the subsequent opening of the same state (the popup window is empty or with data to be edited)
I get the current URL and then I get data from the server. And if the URL includes ID of the data to be editing, I open popup with this data or the empty popup.
the ability to work the browser using the buttons "back" and "forward".
I used the history.pushState method.

I use the Fetch API for requests to the server. To build the table and the popup, I used jQuery. But in the part of the code with browser history I can't find a way to use jQuery, only pure JS.

I will appreciate any advice about code.

const getLink = window.location.hash.slice(1) // to get the current URL witout hash

fetch('http://localhost:3000/names') // to get the data from the server
    .then((response) => response.json())
    .then((_names) => {
      names = _names //the data
      drawTable() // update table according to data
      if (getLink != 0 && getLink != 'add-new'){ //if URL includes ID of the data
        idEdit = getLink //assign ID from URL as an ID to edit
        addEditValue() // function for popup opening with the data to be editing
      }
    })

 if (getLink == 'add-new') {openAddForm()} //open the empty popup

 top.addEventListener('click', function(e){ // listen a click on the page
    if(e.target == $('#add-new') || e.target.className == 'edit-btn'){
    //if a click on the button for opening empty popup or popup with the data to be editing
    e.preventDefault()
    const data = e.target.id
    const url = "/#" + data
    e.target.setAttribute('href', url)
    history.pushState(data, null, url)
  } else if(e.target.className != 'input-form-body') {
    //if you click after closing the pop-up window, then clear the URL
    window.location.hash = ""
  }
  e.stopPropagation()
  }, false)

window.addEventListener('popstate', function(e){
  const character = e.state
  if(character == null){
    closeForm() // close popup
    } else {
      idEdit = character
      addEditValue() //open popup with the data to be editing
    }
  })

An appropriate term for this code is spaghetti code – it's tightly intertwined with other parts of the app, so one cannot easily take out a part of it and reason about it without thinking about the rest of the app. Just like it's hard to pull out one single spaghetti from a bowl.

It's not inherently bad, as long as the program is really small (< 10 lines). But as your program grows, you're bound to experience that it's getting harder and harder to reason about your program and make changes in it without breaking things. You might even reach a point where you're afraid to make any changes, as things are so likely to break.

I guess one needs to go through this to really start to look for better ways of organizing the code. So don't feel bad about yourself. Everybody starts out like this. If you want to improve, look out for books like "Pragmatic programmer" or "Clean code". Or search the web for "JavaScript style guide" and "Software engineering principles".

To answer in more detail...

I find it really hard to understand what this code does:

Seems that it's been extracted out of a larger file, that could give us some context.
It calls into various functions like drawTable(), addEditValue() which aren't defined in here.
It assigns to some global variables like names and idEdit, which are also not defined in here.

Several style issues make the code hard to read:

It's sloppily indented – sometimes 4, sometimes 2 spaces, sometimes no indentation at all.
Some lines end with semicolon, others don't.
The comments are sometimes misleading, like:

// to get the current URL witout hash
const getLink = window.location.hash.slice(1)

It actually does the opposite – it returns the hash-part of the URL.
At other times the comments state what's already obvious from the code:

// listen a click on the page
top.addEventListener('click', function(e){

The name getLink looks like a function name, but it's not a function. A good style is to only name functions with verbs (as they do things).
The name data is meaningless. All variables contain data. Naming a variable data is just as helpful as naming it variable.
The name character is very confusing. Previously you pushed e.target.id to the history state (naming it data). And then in popstate you get back the history state and call it character. If it's a character, then call it so consistently in both places. But it looks like it's not just a single character, because you assign it to idEdit – so it seems to be some sort of ID instead.

Regarding your question:

  But in the part of the code with browser history I can't find a way to use jQuery, only pure JS.

That's absolutely fine. jQuery is a library for doing DOM manipulations (for interacting with the HTML on the page). You shouldn't use it for other things besides that.


Parse a clean slug URL I have to implement a "user-friendly" URL for an employment website. The URL /jobs{parameters?} may be composed of up to three searching criteria separated by hyphens (i.e. -); each criterion is separated by a tilde (i.e. ~). The parameters string has the following structure: -keywords-employmentTypes-locations. keywords and employmentTypes are optional. location is mandatory unless there are no parameters, the route should handle all these cases:

/jobs

/jobs-canada     /jobs-canada~paris~usa

/jobs-full_time-canada  /jobs-full_time~part_time-canada~paris
/jobs-engineer-canada  /jobs-engineer~c++-canada~paris

/jobs-engineer-full_time-canada  /jobs-engineer~c++-full_time-canada~paris

The following class parses the string parameters and fill all criteria in variables:

class JobUrlBuilder
{
    const DEFAULT_LOCATION = 'france';

    public $keywords;
    public $employmentTypes;
    public $locations;

    public $allEmploymentTypes;

    function __construct($allEmploymentTypes = [])
    {
        $this->setAllEmploymentTypes($allEmploymentTypes);
    }

    /**
     * @param string $parameters
    */
    public function setParameters($parameters)
    {
        $parameters = explode('-', ltrim($parameters, '-'));
        if (empty($parameters[0])) {
            array_shift($parameters);
        }

        if (count($parameters) === 3) {
            $this->keywords  = $parameters[0];
            $this->employmentTypes = $parameters[1];
            $this->locations = $parameters[2];
        } else if (count($parameters) === 2) {
            $areEmploymentTypes = $this->areEmploymentTypes(explode('~', $parameters[0]));

            $this->keywords  = $areEmploymentTypes ? null : $parameters[0];
            $this->employmentTypes = $areEmploymentTypes ? $parameters[0] : null;
            $this->locations = $parameters[1];
        } else if (count($parameters) === 1) {
            $this->keywords  = null;
            $this->employmentTypes = null;
            $this->locations = $parameters[0];
        } else {
            $this->keywords  = null;
            $this->employmentTypes = null;
            $this->locations = self::DEFAULT_LOCATION;
        }

        $this->keywords = $this->keywords ? explode('~', $this->keywords) : [];
        $this->employmentTypes = $this->employmentTypes ? explode('~', $this->employmentTypes) : [];
        $this->locations = $this->locations ? explode('~', $this->locations) : [];

        return $this;
    }

    /**
    * @param array $items
    */
    public function areEmploymentTypes($items)
    {
        $jobTypes = array_map(function ($v)
        {
            return mb_strtolower($v);
        }, $this->allEmploymentTypes);

        return ! array_diff($items, $jobTypes);
    }

    /**
    * @param array $employmentTypes
    */
    public function setAllEmploymentTypes($employmentTypes)
    {
        $this->allEmploymentTypes = $employmentTypes;
    }

    public function hasDefaultLocation()
    {
        return in_array(self::DEFAULT_LOCATION, $this->locations);
    }
}

I don't like this code (spaghetti code, no separation of concerns...). I think there is a better implementation. I'm also open to other URL structures - I know I can simply use input parameters and call it a day, but I should implement a clean URL. I have added unit tests to handle all cases. I think it might help you understand the code.

The greatest problem with this is that you want to make these elements optional without actually marking whether they are present.  There are at least two alternatives to this or normal GET parameters that allow for all three to be optional.

Mark whether they are present

Consider a URI that looks like /jobs/keyword/engineer/c++/type/full_time/part_time/location/canada or /jobs-keyword-engineer-c++-type-full_time-part_time-location-canada (if you want everything in the first slot for search engine optimization).  You may prefer something like kword, etype, and loc to make those less likely to show up as keywords themselves.  I would dislike those as variable names, but the exigencies here may make them better as parameter names.  Ideally those would be things that make no sense as keywords.

This is still slug based.  It simply has some extra information to help you parse.

Look up everything

You currently have a PHP-based list of valid employment types.  Instead, put every valid employment type and location in a database table.  Then you can say something like

SELECT parameter_id, parameter_name, parameter_type
FROM parameters
WHERE parameter_name IN (?, ?, ?, ?, ?)

where you then pass (for example)

['engineer', 'c++', 'full_time', 'part_time', 'canada']

as the things to select.

I would prefer to store employment types in the database, as they are data to me.  Storing them in code is itself a spaghetti code problem in my opinion.

The results will be all the employment types and locations, which you can then easily represent by objects or IDs.  Whatever remains will be the keywords, which presumably aren't bounded in the same way that employment types and locations are.


Hidden Markov Model with Viterbi I have a Hidden Markov model class with basically a single method: getting the best parse of a sequence of input tokens based on Viterbi.

While I have no hardcore benchmarks, I'd love some pointers to make it even a bit faster, as it (expectedly) takes quite a long time when the number of states is over 2000.

from math import log10 as lg

class HMM(object):
    def __init__(self, states, start_probs, transition_probs, emission_probs):
        # set(str)
        self.states = states

        # map(str, float)
        self.start_probs = start_probs

        # map(str, map(str, float))
        self.transition_probs = transition_probs

        # map(str, map(str, float))
        self.emission_probs = emission_probs

    def best_parse(self, input_tokens):
        p, path = HMM.__viterbi(
            input_tokens, self.states, self.start_probs, self.transition_probs, self.emission_probs
        )
        return '{0} => {1}\t{2}'.format(' '.join(input_tokens), path, lg(p))

    @classmethod
    def __viterbi(cls, observations, states, start_probability, transitionable, emission_probability):
        trellis = [{}]

        path = {}

        for state in states:
            trellis[0][state] = \
                start_probability.get(state, 0.0)
            path[state] = [state]

        for i, e in enumerate(observations[0:-1], 1):
            trellis.append({})
            path_for_current_state = {}

            for state in states:
                (probability, candidate_state) = \
                    max((trellis[i - 1][s] *
                        transitionable.get(s, {}).get(state, 0.0) *
                        emission_probability.get(state, {}).get(observations[i], float('-inf')), s)
                    for s in states)

                trellis[i][state] = probability
                path_for_current_state[state] = path[candidate_state] + [state]

            path = path_for_current_state

        # trellis[n-1][state] is the most likely parse for state.
        (probability, state) = max(
            (trellis[len(observations) - 1][state], state)
            for state in states
        )

        return (probability, ' '.join(t for (t, _) in path[state]))

1. Bugs

No use is made of the last observation. For example, if we have this model:

A = 'A', None
B = 'B', None
states = [A, B]
initial = {A:.75, B:.25}
transition = {}
emission = {A:dict(a=1), B:dict(b=1)}

And then we give it the single observation b:

>>> print(HMM(states, initial, transition, emission).best_parse('b'))
b => A  -0.12493873660829995

The conclusion is that the most likely path was to start in state A. But this is impossible, because state A can't emit the observation b!

If you look at the Wikipedia description of the Viterbi algorithm, you'll see that the initial state probabilities have to take the first observation into account. So where the code in the post has:

trellis[0][state] = start_probability.get(state, 0.0)

it should instead be:

trellis[0][state] = (start_probability.get(state, 0.0)
    * emission_probability.get(state, {}).get(observations[0], 0.0))

and then the loop over observations[0:-1] should be over observations[1:].
If the emission table has no entry for an observation, then the probability defaults to \$−∞\$:

get(observations[i], float('-inf'))

But probabilities must be between 0 and 1, so \$−∞\$ is not a probability. This leads to wrong answers because the multiplication \$0 × −∞\$ is likely to turn up somewhere in the computation, and \$0 × −∞\$ is not a number:

>>> 0 * float('-inf')
nan

(Probably you were thinking "log-likelihood" when you wrote float('-inf'). See §2.5 below.)

2. Review

There are no docstrings. What do these methods do? What should I pass? What do they return?
When you have a "class with basically a single method" then what you are looking for is a function. Not everything needs to be a class!
The result of the best_parse method is returned as a formatted string. This is not likely to be useful for anything other than development and debugging. It would be more useful to return the highest probability path as a list.
It seems very limiting that states are required to be pairs whose first element is a string.
The code computes probabilities by multiplying. But over the course of a lengthy sequence of observations this is likely to underflow the range of double-precision floating-point numbers. To avoid this, it would be better to work with the logarithms of probabilities, and add them instead of multiplying.
Just as you only need to keep two copies of the path dictionary (one for the previous observation, one for the current observation), you only need to keep two copies of the trellis dictionary.
The paths are extended by concatenatation: path[candidate_state] + [state]. But this requires copying out the whole of path[candidate_state], and as the paths get longer this takes more and more time. It would be better to represent the paths as linked lists, so that they can be constructed in constant time. Then the best path can be reconstructed by following the links.
The code requires observations to be a sequence so that it can be sliced. This means that all observations have to be acquired before you can start running the Viterbi algorithm. But since observations may take time to acquire, it would be nice if the Viterbi algorithm could be interleaved with the acquisition of the observations. This would be easy to do in Python by iterating over observations instead of slicing it.
Every time around the inner loop, this code:

max((trellis[i - 1][s] *
    transitionable.get(s, {}).get(state, 0.0) *
    emission_probability.get(state, {}).get(observations[i], float('-inf')), s)
for s in states)

has to construct two empty dictionaries (that will most likely not be needed and just get discarded), do four dictionary lookups, and build a tuple. All of this work could be avoided if you pre-processed the data so that (i) states are represented by consecutive integers starting at zero; (ii) observables are also represented by consecutive integers starting at zero; (iii) transitionable and emission_probability are represented by NumPy arrays of logarithms of probabilities (instead of dictionaries of dictionaries of probabilities).

Now, the multiplications become additions, and using NumPy we can do all the additions simultaneously like this:

logprob[:, np.newaxis] + transition + emission[:, event]

3. Revised code

import numpy as np

def likeliest_path(initial, transition, emission, events):
    """Find the likeliest path in a hidden Markov Model resulting in the
    given events.

    Arguments:
    initial: arraylike(n) --- probability of starting in each state
    transition: arraylike(n, n) -- probability of transition between states
    emission: arraylike(n, e) -- probability of emitting each event in
        each state
    events -- iterable of events

    Returns:
    path: list(int) -- list of states in the most probable path
    p: float -- log-likelihood of that path

    """
    # Use log-likelihoods to avoid floating-point underflow. Note that
    # we want -inf for the log of zero, so suppress warnings here.
    with np.errstate(divide='ignore'):
        initial = np.log10(initial)
        transition = np.log10(transition)
        emission = np.log10(emission)

    # List of arrays giving most likely previous state for each state.
    prev = []

    events = iter(events)
    logprob = initial + emission[:, next(events)]
    for event in events:
        # p[i, j] is log-likelihood of being in state j, having come from i.
        p = logprob[:, np.newaxis] + transition + emission[:, event]
        prev.append(np.argmax(p, axis=0))
        logprob = np.max(p, axis=0)

    # Most likely final state.
    best_state = np.argmax(logprob)

    # Reconstruct path by following links and then reversing.
    state = best_state
    path = [state]
    for p in reversed(prev):
        state = p[state]
        path.append(state)
    return path[::-1], logprob[best_state]


Reverse C++11 range-based for loop I wrote this snippet:

template <typename ContainerT>
class ReverseIterator
{
public:
    ReverseIterator(ContainerT& iContainer) : m_container{iContainer}
    {

    }

    typename ContainerT::reverse_iterator begin()
    {
        return m_container.rbegin();
    }

    typename ContainerT::reverse_iterator end()
    {
        return m_container.rend();
    }

private:
    ContainerT& m_container;
};

template <typename ContainerT>
auto Reverse(ContainerT& iContainer)
{
    return ReverseIterator<ContainerT>(iContainer);
}

To be able to do something like this:

std::vector<int> myList{1, 2, 3};
for (auto& itr : Reverse(myList))
{
    ++itr;
}

First I'd like a feedback up to this point.

Then, I'd like to be able to write something like this:

for (auto itr : Reverse(std::vector<int>{1, 2, 3}))
{
    std::cout << itr << " ";
}

Without having a separate and near identical implementation of ConstReverse.

I thought about making everything with forwarding references but for some reason that didn't work out very well and I'm not exactly sure where I was mistaken. Could someone show me how it could be done?

Good clear template code - well done!

I'd consider changing the name, as the class itself isn't an iterator, it's an iterator pair, or range, that wraps a container and provides a reversed view of it.

Constructor should be explicit.

We should use free-function rbegin() and rend() to give us greater flexibility of container types (e.g. C-style arrays) - fall back to the std versions in <iterator> if argument-dependent lookup fails.

It could be improved by overloading Reverse with a version that accepts a const Container:

template <typename ContainerT>
auto Reverse(const ContainerT& iContainer)
{
    return ReverseIterator<const ContainerT>(iContainer);
}

For this to work properly, we need to change the return type of begin() and end() to auto, so that we get const_reverse_iterator back from them.  If you're really stuck with C++11, then we'll have to add the trailing return type: auto begin()-> decltype(m_container.begin()), for example.  For my own convenience, I'll work with C++17 from here onwards.

Applying these suggested changes gives us:

template <typename ContainerT>
class ReverseContainerView
{
public:
    explicit ReverseContainerView(ContainerT& iContainer)
      : m_container{iContainer}
    {
    }

    auto begin() {
        using std::rbegin;
        return rbegin(m_container);
    }
    auto end() {
        using std::rend;
        return rend(m_container);
    }

private:
    ContainerT&  m_container;
};

template<typename ContainerT>
auto Reverse(ContainerT& iContainer)
{
    return ReverseContainerView<ContainerT>(iContainer);
}

template<typename ContainerT>
auto Reverse(const ContainerT& iContainer)
{
    return ReverseContainerView<const ContainerT>(iContainer);
}

and demo:

#include <iostream>
#include <vector>
int main()
{
    auto list = std::vector<int>{1, 2, 3};
    for (auto& i: Reverse(list)) {
        std::cout << ++i << ' ';
    }
    std::cout << '\n';
    for (const auto& i: list) {
        std::cout << i << ' ';
    }
    std::cout << '\n';

    const auto const_list = std::vector<int>{1, 2, 3};
    for (auto i: Reverse(const_list)) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}

Note that the proposed usage for (auto i: Reverse(std::vector<int>{10, 20, 30})) (where the constructor argument is an xvalue) won't work with the above code.  That's because the temporary has gone out of scope after the ReverseContainer was constructed but before the for loop completes, leaving a dangling reference in the container.  We'll need a version that captures and stores any rvalue type passed to it.

The easiest way I know to do this is to split the class into its two responsibilities: a base class to capture the wrapped container and a subclass to access the reversed view (we might want to put some or all of these classes into an inner namespace to hide them from users; I'll leave that question open here).

#include <iterator>
#include <type_traits>
#include <utility>

template <typename T, bool CopyValue = !std::is_lvalue_reference_v<T>>
struct ContainerContainer;

template <typename T>
struct ContainerContainer<T, false>
{
    // lvalue version: contains a reference to the container
    T& container;
    explicit ContainerContainer(T& container)
      : container{container}
    {}
};

template <typename T>
struct ContainerContainer<T, true>
{
    // rvalue version: move-constructs a new copy of container
    const T container;
    explicit ContainerContainer(T container)
      : container{std::move(container)}
    {}
};

template <typename Container>
class ReverseContainerView : ContainerContainer<Container>
{
    using Base = ContainerContainer<Container>;
public:
    explicit ReverseContainerView(Container&& container)
        : Base{std::forward<Container>(container)}
    {}

    auto begin() {
        using std::rbegin;
        return rbegin(Base::container);
    }
    auto end() {
        using std::rend;
        return rend(Base::container);
    }
};

template<typename Container>
auto Reverse(Container&& container)
{
    return ReverseContainerView<Container>(std::forward<Container>(container));
}

// test program
#include <iostream>
#include <vector>
int main()
{
    int list[] = {1, 2, 3};
    for (auto& i: Reverse(list)) {
        std::cout << ++i << ' ';
    }
    std::cout << '\n';

    const auto const_list = {1, 2, 3}; // initializer_list
    for (auto& i: Reverse(const_list)) {
        // ++i; ERROR: 'i' is read-only
        std::cout << i << ' ';
    }
    std::cout << '\n';

    for (auto& i: Reverse(std::vector<int>{10, 20, 30})) {
        // ++i; ERROR: 'i' is read-only
        std::cout << i << ' ';
    }
    std::cout << '\n';
}

From C++17 onwards, we don't really need the Reverse() helper function: we can instead simply provide a template deduction guide:

template<typename Container>
explicit ReverseContainerView(Container&& container)
    -> ReverseContainerView<Container>;

We might want to choose a shorter name for the class now that it's more visible to the users.


Creating an input integer function I have 3 different functions I have tried in my programs. I want a function which continues to loop until an integer is entered. Which would be the best to  use? Or is there a better one?

def valid_int(question):
    """Creates a loop until an integer is entered"""
    py_version = find_version()
    if py_version == 3:
        response = input(question)
        while not response.isdigit():
            print("\nInvalid input! Input must be an integer")
            response = input(question)
        return int(response)
    else:
        response = raw_input(question)
        while not response.isdigit():
            print("\nInvalid input! Input must be an integer")
            response = raw_input(question)
        return int(response)

def valid_int(question):
    """Creates a loop until an integer is entered"""
    py_version = find_version()
    if py_version == 3:
        while True:
            response = input(question)
            try:
                return int(response)
            except ValueError:
                print("\nInvalid input! Input must be an integer")
    else:
        while True:
            response = raw_input(question)
            try:
                return int(response)
            except ValueError:
                print("\nInvalid input! Input must be an integer")

def valid_int(question):
    """Creates a loop until an integer is entered"""
    py_version = find_version()
    if py_version == 3:
        while True:
            response = input("Length of password: ")
            if response.isdigit()
                return int(response)
            print("\nInvalid input! Input must be an integer")
    else:
        while True:
            response = raw_input("Length of password: ")
            if response.isdigit()
                return int(response)
            print("\nInvalid input! Input must be an integer")

In Python, the standard approach is EAFP: it's Easier to Ask Forgiveness than Permission. So this:

response = raw_input(question)
try:
    return int(response)
except ValueError:
    print("\nInvalid input! Input must be an integer")

is definitely the way to go.

We can even go one step further. Regardless of which python version it is, we're running the same logic. The only difference is which input function to use. So let's just extract that logic outside of the loop so we don't have duplication of effort:

def valid_int(question):
    """Creates a loop until an integer is entered"""
    input_func = input if find_version() == 3 else raw_input

    while True:
        response = input_func(question)
        try:
            return int(response)
        except ValueError:
            print("\nInvalid input! Input must be an integer")


Testing input validation and an AJAX request with Javascript and QUnit I have a simple web page where the user enters the name and rank of a soldier and hits submit. If the input is invalid, an appropriate error message gets displayed. Otherwise, it adds the soldier to a database and adds it to a list of current Soldiers via AJAX request.

//Find elements on page
var rankField = $("input[name='rank']");
var nameField = $("input[name='name']");
var submit = $("input[type='submit']");
var list = $("ul");

//attach event-handler to submit button
submit.click(function() {
  var rank = rankField.val();
  var name = nameField.val();
  onSoldierSubmitted(rank, name);
});

function onSoldierSubmitted(rank, name) {
  clearErrors();

  var rankIsValid = isValidRank(rank);
  var hasErrors = false;

  if (!rankIsValid) {
    addError('rank is invalid');
    hasErrors = true;
  };

  if (!name) {
    addError('Please enter a name for your Soldier');
    hasErrors = true;
  };

  if (hasErrors) {return;}
  appendSoldier();
};

function clearErrors() {
  $('.alert-danger').empty();
};

function addError(errorText) {
  var errorDiv = $('.alert-danger');
  var currentError = errorDiv.html();

  if (currentError) {
    currentError += '
';
  };

  errorDiv.html(currentError + errorText);
};

function isValidRank(rank) {
  var ranks = ['GEN', 'LTG', 'MG', 'BG', 'COL', 'LTC', 'MAJ',
      'CPT', '1LT', '2LT', 'CW5', 'CW4', 'CW3', 'CW2', 'WO1',
      'SMA', 'CSM', 'SGM', '1SG', 'MSG', 'SFC', 'SSG', 'SGT',
      'CPL', 'SPC', 'PFC', 'PV2', 'PVT']
  normalizedRank = rank.toUpperCase();
  return ranks.indexOf(normalizedRank) != -1;
};

function appendSoldier() {
  $.get("/ajax/soldier",
  {
    rank: rankField.val(),
    name: nameField.val(),
  }).done(
    function(data) {
      soldiers = extractSoldiersFromList(data);
      renderHTMLListFromData(soldiers);
    }
  );

  clearInput();
};

function extractSoldiersFromList(data) {
  var soldierData = $.parseJSON(data);
  var soldiers = [];

  for (var i=0; i < soldierData.length; ++i) {
    var soldier = soldierToString(soldierData[i]);
    soldiers[i] = soldier;
  }

  return soldiers;
};

function renderHTMLListFromData(data) {
  list.empty();
  elements = data;
  addSoldiersToUL(elements);
}

function addSoldiersToUL(soldiers) {
  for (var i = 0; i < soldiers.length; ++i) {
    list.append("
" + soldiers[i] + "
");
  }
}

function clearInput() {
  rankField.val('');
  nameField.val('');
}

function soldierToString(soldierDict) {
  var rank = soldierDict.rank;
  var name = soldierDict.name;

  return rank + " " + name;
};

(Yes, I realize I am a horrible person for using GET instead of POST for this. I was having trouble getting POST to work with my back-end.)

I'm having trouble figuring out the right unit tests for the appendSoldier function:

test("appendSoldier makes request with correct args", function() {
  sinon.spy($, 'get');
  rankField.val('PVT');
  nameField.val('Snuffy');

  appendSoldier();

  ok($.get.calledWith("/ajax/soldier", {rank: 'PVT', name: 'Snuffy'}));
  $.get.restore();
});

test("UL of Soldiers populates correctly", function() {
  renderHTMLListFromData(soldierData);
  ok(list.has('li').text('PVT Snuffy'));
});

My reasoning here is that unit tests aren't supposed to test anything external, so I make sure the right request gets called, and that the proper thing is done with the response. I'm unhappy with this, because it still doesn't tell me that appendSoldier works like it's supposed to. I guess that's just something I leave to my functional tests?

I'm also not sure about my tests for the onSoldierSubmitted function, which displays appropriate errors, or calls appendSoldier if there aren't any errors.

Here is my test for valid input:

test("Get request called with valid input", function() {
  sinon.spy($, "get");
  onSoldierSubmitted('pvt', 'snuffy');
  ok($.get.called, "method called");
  $.get.restore();
});

I'm not sure whether I ought to be uncomfortable that this tests that appendSoldier sends the get request, rather than testing that appendSoldier gets called.

My reasoning here is that unit tests aren't supposed to test anything
  external

I agree with that. You can't test external things like an AJAX call anyway.

  I'm unhappy with this, because it still doesn't tell me that
  appendSoldier works like it's supposed to.

Actually, you CAN test the appendSoldier method. You need to refactor it in the following way:

function appendSoldier() {
    $.get("/ajax/soldier",
    {
       rank: rankField.val(),
       name: nameField.val(),
    }).done(
        function(data) {
            // Notice that I extracted these 2 lines of code into a separate method
            // soldiers = extractSoldiersFromList(data);
            // renderHTMLListFromData(soldiers);
            appendSoldierSuccess(data);
        }
    );

    clearInput();
};

// This is the extracted method
function appendSoldierSuccess(data) {
    soldiers = extractSoldiersFromList(data);
    renderHTMLListFromData(soldiers);
}

Now you can unit test the functionality in the following way (I will use Jasmine because I'm familiar with it but the concepts can be mapped to Sinon):

it("appendSoldierSuccess()", function() {
    var data = {};
    var soldiers = {};

    spyOn(window, 'extractSoldiersFromList').and.returnValue(soldiers);
    spyOn(window, 'renderHTMLListFromData');

    appendSoldierSuccess(data);

    expect(window.extractSoldiersFromList).toHaveBeenCalledWith(data);
    expect(window.renderHTMLListFromData).toHaveBeenCalledWith(soldiers);
});


Find palindrome in a string The purpose of this code is to find the largest palindrome in a string. It works fine when the string is short, but every time I test this code with 1000+ characters in a string, it takes forever to give me the palindrome in it.

PalindromeFinder::PalindromeFinder(){}

string PalindromeFinder::toString(){

stringstream ss;
ss << "largest palindrome seen so far is \"" << this->
           getLargestPalindromeFound();
ss << "\" with size " << this->getSizeOfLargestPalindromeFound();
return ss.str();
}

string PalindromeFinder::getLargestPalindromeFound(){
return this->largestPalindromeFound;
}

int PalindromeFinder::getSizeOfLargestPalindromeFound(){
return this->largestPalindromeFound.length();
}

string str="djclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjssssssevessssssfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjf";

truncateToLargestPalindrome(str);

void PalindromeFinder::truncateToLargestPalindrome(string& inputString){

string empty="";

inputString.erase(remove_if(inputString.begin(), inputString.end(), ::isspace), inputString.end());

inputString.erase(remove_if(inputString.begin(), inputString.end(), ::ispunct), inputString.end());

inputString.erase(remove_if(inputString.begin(), inputString.end(), ::isdigit), inputString.end());

for(int i = 0; i < inputString.length(); i++){
for (int j = inputString.length(); j>=i; j--) {
    string subStr = inputString.substr(i, j-i);
    if(isPalindrome(subStr) && subStr.length() > empty.length())

        empty = subStr;

}

   }

   }

How can I improve my code so it can handle large strings more quickly?

Let's see how your code computes out...

You loop for every position in the input string. Then, you find each possible string starting from there. So, for 1000 characters, that's 1000 + 999 + 998, etc. Which turns out to be \$\frac{1000^2}{2}\$ - or a half-million strings that you check.

Now, for each of those string values, you then check to see if they are a palindrome. Presumably, for each of those strings, in the isPlaindrome method, you compare the string to the reverse of the string, which means checking each character again.

That's another few iterations of each string, meaning your code ends up with a complexity in the order of cubic: \$O(N^3)\$.

Shavings

Now, there's ways to improve the code quite easily, for example, there's no point in checking (or even substringing) anything that's shorter than the current longest palindrome. In other words, why test 5 letter substrings if you've already found a 6 letter one? That will reduce the work you do, but, it will still be pretty slow.

Creating a string instance for each candidate is also not a great solution - you should find a way to do the palindrome checking on the original string, without making copies of sub-parts.

Still, I can't help but feel that the better solution is to reduce the computational complexity a lot, which makes scaling the code much better.

Algorithm

My suggestion is to change the algorithm. Your current one checks every possible substring in the input to find a palindrome. A better solution would be to only test strings which are "almost known" to be palindromes.

A palindrome is a word where the last half is a reflection of the first (in terms of letters). This implies that there is a middle of the reflection. If you can start at the middle of the reflection, and work outwards, until the reflection is broken, then you can compare what works with what you have already found, and move on.

Since there are even and odd sized palindromes, there are two types of "middle": two characters at the middle for even, and 1 character for odd sized palindromes.

There can be just one "middle" at each character in the input. If you can determine how wide the palindrome is spanning each middle, then you are one step ahead. At worst case, if the string is entirely 1 letter, like aaaaaaaaaaaaa, then you will have to check a lot of palindromes, and the worst-case performance is \$O(n^2)\$ (which is still a bunch better than your cubic approach). On the other hand, a reasonably random input will typically have mostly 1-letter palindromes, and they will test out very quickly, so a best-case complexity is just \$O(n)\$

I took the liberty of writing up a solution using the approach I describe:

std::string largestPalindrome(std::string input) {
    std::string largest = "";
    // offset is O or 1 for odd, and even sized palindromes.
    for (int offset = 0; offset <= 1; offset++) {

        for (int mid = 0; mid + offset < input.length(); mid++) {

            // max is the space between the mid and the end
            int max = input.length() - offset - mid;
            // ... unless the mid is closer to the beginning than the end.
            max = max > mid ? mid : max;

            for (int i = 0; i < max; i++) {
                if (input[mid - i] == input[mid + offset + i]) {
                    if (i + i + offset + 1 > largest.length()) {
                        largest = input.substr(mid - i, i + i + offset + 1);
                    }
                } else {
                    break;
                }
            }
        }
    }

    return largest;
}

Note, the mid-loop runs only twice (once for even, once for odd). The inner i loop will tend to be pretty small because it only runs while the strings centered on the mid point are actually palindromes.... and large palindromes will be the exception, not the rule.

There's only 1 big loop, in other words.

Additionally, substr is only called when there's a larger palindrome than previously seen... it's an uncommon call.

The above code runs the example str input in 3 milliseconds on my computer (and you can see it running in ideone too)


Palindrome from all the substrings This Problem is from https://www.codechef.com/problems/PRINCESS .

The Problem in brief - i am given a string of length N. I have to check among all the the substrings that whether a substring exist or not which is palindrome and having length greater than 1. If such a substring exists then print YES else print NO.

Input
The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing a string.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 100000

Subtasks

Subtask #1 (20 points), Time limit : 1 sec
1 ≤ T<=10, N<=1000

Subtask #2 (80 points), Time limit : 1 sec
1 ≤ T<=10, N<=100000

How Do I optimize the code? I am getting subtask #1 right , with this code.

int main()
{
    int T;
    string s,sub;
    int n,counter;
    int i,j,k;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
        cin>>s;
        n = s.length();
        counter=0;

        for(j=0;j<n-1;j++)
        {
          if(counter==1)
                    break;
                for(k=2;k+j<=n;k++)
                {
                   sub=s.substr(j,k);
                    if( equal(sub.begin(), sub.begin() + sub.size()/2, sub.rbegin()) )
                    {
                        counter++;
                        break;
                    }
                }
        }
        if(counter==0)
                printf("NO\n");
        else
                 printf("YES\n");
    }
    return 0;
}

There's a simple linear solution.

You don't have to check all substrings. If an [l, r] substring is a palindrome and r - l > 2, so is [l + 1, r - 1]. Thus, it's sufficient to check only substrings of length 2 and 3.

One can do with a single pass over the input string:

for i in [0 .. s.length() - 2]:
     if s[i] == s[i + 1]:
         return true
     if i != 0 and s[i - 1] == s[i + 1]:
         return true
return false


Escaped explode/implode function I had a somewhat interesting issue.  I had to take an array and turn it into a string with a set of delimiters; then later on take that string and turn it back into an array, splitting at the same delimiters.  The twist was the string could be contain anything (including the delimiters).

I feel like I over-engineered the solution, and am wondering what you guys can come up with as alternatives.

Here is my solution.  escapedImplode turns an array into a string, and escapedExplode turns that string back into its corresponding array.  The testEscapedIE function is a little test scaffolding to see if your solution works.

function escapedImplode ($glue, $array, $escapeChar = '\\')
{
    $array = array_map(function ($item) use ($escapeChar, $glue) {
        $item = str_replace($escapeChar, $escapeChar . $escapeChar, $item);
        $item = str_replace($glue, $escapeChar . $glue, $item);

        return $item;
    }, $array);

    return implode($glue, $array);
}

function escapedExplode ($delimiter, $string, $escapeChar = '\\')
{
    $characters = str_split($string);

    $isEscaped = false;

    $parts = array();
    $buffer = '';

    for ($i = 0; $i < count($characters); $i++)
    {
        $char = $characters[$i];

        // If is escaped, just add to the buffer and continue
        if ($isEscaped)
        {
            $buffer .= $char;
            $isEscaped = false;
            continue;
        }
        // If is a delimiter, which isn't escaped, set state and continue
        else if ($char == $escapeChar)
        {
            $isEscaped = true;
            continue;
        }

        // If not escaped and is the delimiter, break here
        if ($char == $delimiter)
        {
            $parts[] = $buffer;
            $buffer = '';
            continue;
        }

        // Doesn't match another special case, tack onto buffer
        $buffer .= $char;
    }

    // Add whatever is in the buffer to end of parts
    $parts[] = $buffer;

    return $parts;
}

function testEscapedIE ()
{
    $tests = array(
        array('test', 'cool', 'awesome'),
        array('some/thing', 'cool', '/isbrewing/'),
        array('with\\/asdf', '//other//', '\\/collness\\/'),
        array('////','//\\//','\\//\\//\\','\\\\'),
    );

    foreach ($tests as $test)
    {
        $imploded = escapedImplode('/', $test);
        $exploded = escapedExplode('/', $imploded);

        echo 'Testing: ' . implode(', ', $test) . ' -- ';
        echo $imploded . ' -- ';
        echo implode($exploded, ', ') . ': ';

        echo $test === $exploded ? 'Pass' : 'Fail';

        echo "
\n";
    }
}

testEscapedIE();

Not bad.  I just have a few nitpicks.

You can iterate over characters of a string directly without splitting it into an array first:

for ($i = 0; $i < strlen($string); $i++) {
    $char = $string[$i];
    ...
}

I believe that the PHP interpreter isn't smart enough to recognize that strlen($string) is invariant, so you might get better performance with

$strlen = strlen($string);
for ($i = 0; $i < $strlen; $i++) {
    $char = $string[$i];
    ...
}

I find the else if in escapedExplode() slightly jarring.  Either use if and continue everywhere, or if, else if, else if, else without continue.


SPOJ is giving TLE for this solution of ROCK I am solving ROCK problem on SPOJ. I have used bottom up dynamic programming approach for this problem. Time complexity for this is \$O(n^3)\$.

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 210
#define NEG_INFINITY -1000

int sellable(int a[MAX], int i, int j)
{
    int index,sweet=0,sour=0;
    for(index=i;index<=j;index++)
    {
        if(a[index])
            sweet++;
        else
            sour++;
    }
    if(sweet>sour)
        return 1;
    return 0;
}
int main()
{
    int test_cases,i,j,k,length,l;
    int number,cost;
    int a[MAX];
    int m[MAX][MAX];
    char buffer[MAX];

    for(scanf("%d",&test_cases);test_cases>0;test_cases--)
    {

        scanf("%d",&number);
        for(i=0;i<number;i++)
            for(j=0;j<number;j++)
                m[i][j]=NEG_INFINITY;
        scanf("%s",&buffer);
        for(i=0;i<number;i++)
        {
            a[i]=buffer[i]-'0';
            m[i][i]=a[i];
        }
        for(l=2;l<=number;l++)
        {
            for(i=0;i<number-l+1;i++)
            {
                j=i+l-1;
                for(k=i;k<j;k++)
                {
                    if(sellable(a,i,j))
                        cost=j-i+1;
                    else
                        cost=m[i][k]+m[k+1][j];
                    if(cost>m[i][j])
                    {
                        m[i][j]=cost;
                    }
                }
            }
        }
        printf("%d\n",m[0][number-1]);
    }
    return 0;
}

Can you please suggest an alternative approach for this problem, or if any changes can be made in my code?

The way you call sellable may amount to a 4-th degree complexity. The very smart compiler may notice that it is a pure function, and optimize it out of the inner loop, but I wouldn't rely on it. So, one obvious optimization is to rephrase it as

if (sellable(a, i, j)) {
    cost = j - i + 1;
} else {
    cost = m[i][j];
    for (k = i; k < j; k++) {
        cost = max(cost, m[i][k] + m[k+1][j]);
}
m[i][j] = max(m[i][j], cost);

Still, sellable contributes to the cubic complexity. With a one-time linear investment you can make it into a constant time. Collect accumulated sums [0, i) of the input array; then sellable becomes just

return (a[j] - a[i]) * 2 > (j - i);

The mandatory CR note on the variable names: one letter identifiers make it really hard to follow the code, even as simple as this. I would recommend to use length, seg_start, seg_end instead of l, i, j respectively. number is just meaningless; size sounds better.

Then, I'd highly recommend to interpret length as length (not length + 1 as your code does).

Finally, please don't be shy on spaces.


Splitting a list of strings into sublists where total of bytes of each sublist is <= N I'm given a list of strings and a length limit N. I have to write a function to accumulate consecutive strings in the list until the next string would exceed the N limit. I have to return a list of lists, where each list is the largest consecutive substring not to exceed N characters total. See the test case below for an example. Also, if any single string in the list is longer than N, I have to print a useful message and return.

My attempt to solve the problem has been this one:

def break_lst(lst, size):
    def len_lst(l):
        return len("".join(l))

    err = "Error: use a bigger size than " + str(size)
    result = []
    sublst = []

    for v in lst:
        sublst.append(v)
        ls = len_lst(sublst)

        if ls == size:
            result.append(sublst)
            sublst = []
        elif ls > size:
            prev_sublst = sublst[:-1]
            if not prev_sublst or len_lst(prev_sublst) > size:
                raise Exception(err)
            else:
                result.append(prev_sublst)
                sublst = [v]

    if sublst:
        if len_lst(sublst) > size:
            raise Exception(err)
        else:
            result.append(sublst)

    return result

if __name__ == "__main__":
    lst = ["1", "22", "333", "4444", "55555", "666666", "7777777", "88888888"]

    for i in range(17):
        try:
            print(i, break_lst(lst, size=i))
        except Exception as e:
            print(e)

Output:

Error: use a bigger size than 0
Error: use a bigger size than 1
Error: use a bigger size than 2
Error: use a bigger size than 3
Error: use a bigger size than 4
Error: use a bigger size than 5
Error: use a bigger size than 6
Error: use a bigger size than 7
8 [['1', '22', '333'], ['4444'], ['55555'], ['666666'], ['7777777'], ['88888888']]
9 [['1', '22', '333'], ['4444', '55555'], ['666666'], ['7777777'], ['88888888']]
10 [['1', '22', '333', '4444'], ['55555'], ['666666'], ['7777777'], ['88888888']]
11 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
12 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
13 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
14 [['1', '22', '333', '4444'], ['55555', '666666'], ['7777777'], ['88888888']]
15 [['1', '22', '333', '4444', '55555'], ['666666', '7777777'], ['88888888']]
16 [['1', '22', '333', '4444', '55555'], ['666666', '7777777'], ['88888888']]

Problems with the function:

The proposed algorithm is really ugly and unpythonic
The fact it's handling an special case when the loop has finished makes it even uglier

How would you proceed in order to make a cleaner algorithm out of it?

You can greatly reduce the size of your code by using a total integer and one result list.  You can access the last item in the list by using result[-1].  Additionally, you can reduce the number of times you raise an error by just checking the size of each grouping.

def break_lst(lst, size):
    total = 0
    result = [[]]
    for v in lst:
        total += len(v)
        if total <= size:
            result[-1].append(v)
        else:
            total = len(v)
            if total > size:
                raise Exception("Error: use a bigger size than {}".format(size))
            result.append([v])
    return result


memcpy() implementation I have tried to write a function like memcpy. It copies sizeof(long) bytes at a time.

What surprised me is how inefficient it is. It's just 17% more efficient than the naivest implementation with -O3. With optimizations off it's a lot faster than the naivest, so perhaps the compiler is doing this automatically?

It will copy 1 byte at a time until one of the addresses is aligned, then it will copy sizeof(long) and then 1 byte at a time to avoid writing beyond the bounds.

How can I make this faster?

#include <stdlib.h>

#define THRESHOLD sizeof(long)

static size_t min(size_t a, size_t b)
{
    return (a > b) ? a : b;
}

static void big_copy(void *dest, const void *src, size_t iterations)
{
    long *d = dest;
    const long *s = src;

    size_t eight = iterations / 8;
    size_t single = iterations % 8;

    while(eight > 0){
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        --eight;
    }

    while(single > 0){
        *d++ = *s++;
        --single;
    }
}

static void small_copy(void *dest, const void *src, size_t iterations)
{
    char *d = dest;
    const char *s = src;

    while(iterations > 0){
        *d++ = *s++;
        --iterations;
    }
}

void *copy_memory(void *dest, const void *src, size_t size)
{
    //Small size is handled here
    if(size < THRESHOLD){
        small_copy(dest, src, size);
        return dest;
    }

    //Start copying 8 bytes as soon as one of the pointers is aligned
    size_t bytes_to_align = min((size_t)dest % sizeof(long), (size_t)src % sizeof(long));
    void *position = dest;

    //Align
    if(bytes_to_align > 0){
        small_copy(position, src, bytes_to_align);
        position = (char *)position + bytes_to_align;
        src = (char *)src + bytes_to_align;
        size -= bytes_to_align;
    }

    //How many iterations can be done
    size_t safe_big_iterations = size / sizeof(long);
    size_t remaining_bytes = size % sizeof(long);

    //Copy most bytes here
    big_copy(position, src, safe_big_iterations);
    position = (char *)position + safe_big_iterations * sizeof(long);
    src = (char *)src + safe_big_iterations * sizeof(long);

    //Process the remaining bytes
    small_copy(position, src, remaining_bytes);

    return dest;
}

The last time I saw source for a C run-time-library implementation of memcpy (Microsoft's compiler in the 1990s), it used the algorithm you describe: but it was written in assembly. It might (my memory is uncertain) have used rep movsd in the inner loop.

Your code says, //Start copying 8 bytes as soon as one of the pointers is aligned. When you're performance-testing you should know (because that's when you might expect the best performance) whether both buffers are aligned.

On the subject of alignment there as an interesting (but unrelated to your question) question here on StackOverflow: Why speed of memcpy() drops dramatically every 4KB?

I vaguely understand what kind of an effect you're looking for in your code. I don't know what assembler your compiler is actually producing.

The accepted answer to this StackOverflow question demonstrates the kind of assembly that is used nowadays: Very fast memcpy for image processing?


Safe string formatting in Python I am a fan of f"{strings}" in Python,

However some situations could possibly be dangerous when doing f strings from user input, leaking API keys or even code execution!

So I decided to make something to mitigate these attacks. It works by searching with regex over the input string, and will return an empty string if it detects any evil piece of code.

It uses the fmt package

import fmt as f
import re
import os # This is for checking the system call

import doctest

# Setup
SECRET_GLOBAL = 'this is a secret'

class Error:
    def __init__(self):
        passs

def a_function():
    return SECRET_GLOBAL

# Here is where the code begins
DANGEROUS_CODES = [
                    re.compile(r'(\.system\(.*\))'),    # Any call to system
                    re.compile(r'(__[\w]+__)'),         # Any internals
                    re.compile(r'([\w\d]+\(\))')        # Functions
                  ]

def safe_format(st):
    '''
    Safe python f-string formatting
    this will detect evil code from fstring making formatting safe.

    args:
        st (str): The f-string

    returns:
        Empty string, if dangerous code is found
        Executes the fstring normally if no dangerous code is found

    Test globals acces
    >>> safe_format('{Error().__init__.__globals__[SECRET_GLOBAL]}')
    ''

    Test function acces
    >>> safe_format('a_function()')
    ''

    Test code execution via import
    >>> safe_format('{__import__("os").system("dir")}')
    ''

    Test code execution with imported os
    >>> safe_format('{os.system("dir")}')
    ''

    Test no stack trace
    >>> safe_format('{0/0}')
    ''

    Test acceptable fstring
    >>> safe_format('{6 * 6}')
    '36'
    '''
    if any(re.search(danger, st) for danger in DANGEROUS_CODES):
        return ''

    try:
        return f(st)
    except Exception as e:
        return ''

if __name__ == '__main__':
    doctest.testmod()

Did i miss anything?
Is this approach acceptable?

If you forbid function calls you cannot use getters which then is a big restriction. If you allow them it is hard to get it safe. Also your regexes will have collateral damages and filter legal expressions. So I think your approach is not so good. Don't allow users to mess with format strings. Use Template from string for that purpose.

to your regexes:

if you have a re for function you do not need one for system
[\w] includes [\d]
your re function catches only calls without arguments
re function and re system do not care about whitespaces and are vulnerable
all regexes do collateral damage when matching outside the format braces

here are some more test that currently fail

    '''
    some attacks
    >>> safe_format('a_function(666)')
    ''

    >>> safe_format('a_function ()')
    ''

    >>> safe_format('{os. system("dir")}')
    ''

    some collateral damage
    >>> safe_format('...system(left) {5}')
    '...system(left) 5'

    >>> safe_format('f() gives {5}')
    'f(g) gives 5'

    '''