Return the indexs of two numbers that total a given number I attempted an online Python test the other day. The function I wrote works fine however takes too long to complete.
Question:

From a list of numbers find the indexes of two numbers that total n and return as a tuple.

I tried using itertools but I don't know if there is a function that would out perform my original. I thought itertools.combinations may be able to.
Any suggestions as the best way to tackle this problem?
import numpy as np
from itertools import combinations

numbers = np.random.randint(1, 100, 1000000)

# used to time function run time
def timer_func(orig):
    import time
    def wrapper_func(*args):
        t1 = time.time()
        result = orig(*args)
        t2 = time.time() - t1
        print(f"{orig.__name__} ran in {t2}")
        return result

    return wrapper_func

# new combination test
@timer_func
def find_two_sum(numbers, target_sum):
    """
    :param numbers: (list of ints) The list of numbers.
    :param target_sum: (int) The required target sum.
    :returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
    """
    for perm in combinations(numbers, 2):
        if sum(perm) == target_sum:
            first = np.where(numbers == perm[0])
            second = np.where(numbers == perm[1])
            return (first[0][0], second[0][0])

# original function
@timer_func
def find_two_sum_original(numbers, target_sum):
    """
    :param numbers: (list of ints) The list of numbers.
    :param target_sum: (int) The required target sum.
    :returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
    """
    for i, x in enumerate(numbers):
        for ii, y in enumerate(numbers):
            if i != ii and x + y == target_sum:
                return (i, ii)

if __name__ == "__main__":
    print(find_two_sum(numbers, 25))
    print(find_two_sum_original(numbers, 25))

find_two_sum ran in 1.341470718383789
(2, 307)
find_two_sum_original ran in 1.0022737979888916
(2, 307)

Your solutions might have to try all pairs, so you have up to quadratic runtime.
Let's use an allegedly not adequate set to keep track of the numbers we've already seen, so that for each number, we can check in constant time whether we've seen the needed partner:
def find_two_sum(numbers, target_sum):
    """
    :param numbers: (list of ints) The list of numbers.
    :param target_sum: (int) The required target sum.
    :returns: (a tuple of 2 ints) The indices of the two elements whose sum is equal to target_sum
    """
    seen = set()
    for number in numbers:
        needed = target_sum - number
        if needed in seen:
            i = numbers.index(needed)
            j = numbers.index(number, i + 1)
            return i, j
        seen.add(number)

This only takes linear time.
Other points:

Your function signature seems a bit inappropriate. The question called the target sum "n", not "target_sum". Even your whole program doesn't use "n" anywhere. I always follow the specification (maybe unless the specification is really bad). A middle ground would be to define/read the input into variable n and then name your function parameter like you did. This way, a reader of the question and your code can see the connection.
The question says list of numbers (your docstring even repeats that), not a NumPy array. My code assumes it's indeed a list (I find using list.index a lot better here.)
Your benchmark can be improved. The test case contains a million ints from 1 to 100, and your target sum is 25. You're almost guaranteed to find something quickly, despite the large size and despite your quadratic runtime. Better test a worst case, like list(range(1000)) with target 1997 (the sum of the last two numbers).

Motivated by the comments, here's a benchmark comparing this set+index solution and a dict+enumerate solution (numbers are times, so lower=faster):
Round 1:
2.10 twosum_set
1.77 twosum_set_optimized
2.11 twosum_dict

Round 2:
2.05 twosum_set
1.75 twosum_set_optimized
2.08 twosum_dict

Round 3:
2.14 twosum_set
1.83 twosum_set_optimized
2.11 twosum_dict

They look about equally fast, although the optimized set solution is clearly faster.
That was with my above-mentioned list(range(1000)). Let's use a million instead (and fewer repetitions):
Round 1:
2.64 twosum_set
2.31 twosum_set_optimized
2.84 twosum_dict

Round 2:
2.70 twosum_set
2.36 twosum_set_optimized
2.88 twosum_dict

Round 3:
2.68 twosum_set
2.38 twosum_set_optimized
2.87 twosum_dict

Here the set solution does seem faster than the dict solution, and the optimized set solution is again clearly faster.
Benchmark code:
from timeit import repeat

def twosum_set(numbers, target_sum):
    seen = set()
    for number in numbers:
        needed = target_sum - number
        if needed in seen:
            i = numbers.index(needed)
            j = numbers.index(number, i + 1)
            return i, j
        seen.add(number)

def twosum_set_optimized(numbers, target_sum):
    seen = set()
    add = seen.add           # This is the optimization
    for number in numbers:
        needed = target_sum - number
        if needed in seen:
            i = numbers.index(needed)
            j = numbers.index(number, i + 1)
            return i, j
        add(number)          # This is the optimization

def twosum_dict(numbers, target_sum):
    index = {}
    for i, number in enumerate(numbers):
        needed = target_sum - number
        if needed in index:
            return index[needed], i
        index[number] = i

numbers = list(range(10**3))
repeat_number = 10**4

numbers = list(range(10**6))
repeat_number = 10**1

target_sum = sum(numbers[-2:])

for r in range(3):
    print(f'Round {r+1}:')
    for twosum in twosum_set, twosum_set_optimized, twosum_dict:
        t = min(repeat(lambda: twosum(numbers, target_sum), number=repeat_number))
        print('%.2f' % t, twosum.__name__)
    print()


Reduce Prime Sieve Memory Consumption 2 I've made a prime number generator (for Project Euler).  It uses Euler's Sieve (a modified Sieve of Eratosthenes), with a mod 30 step.  I'd like to reduce the memory consumption to 4/15 what it currently is by keeping a boolean array only for the possibly prime remainders of 30.  I can't get it to work and also fear that this will slow down the program.

I've used

n[f/30*8+[zeroes, except 1,2,3,4,5,6,7 at 7,11,13,17,19,23,29][f%30]]

which seemed to not filter out any composite numbers.  How can I make this work and what other optimizations (aside from increasing the mod) can you suggest?  I need the primes up to about two billion.

//pes30.cxx
#include <vector>
#include <algorithm>
#ifndef _pes30_cxx_
#define _pes30_cxx_

typedef unsigned long long big;

const int offsets[]={6,4,2,4,2,4,6,2};

//fill a given vector with all primes under some value:
void sievePrimes(big max, std::vector<big> &p){
    big multiple;
    bool n[max];//array of whether or not each number is prime (30/8 too big!)
    p={2,3,5};//because the sieve skips all multiples of 2,3, and 5, start with them.
    for(big i=0; i<max; ++i)//initialize the array
        n[i]=true;
    //for every number marked prime less than max, mark its multiples with
    //    every number still marked prime over it as composite.
    for(big i=7, step=1; i<=max; i+=offsets[step], ++step==8?step=0:0){
        if(!n[i])//if i is not prime
            continue;
        p.push_back(i);//add i to the list of primes
        //finds every multiple of i and a (still marked) prime greater than i
        for(big j=i, step2=step; j<=max/i; j+=offsets[step2], ++step2==8?step2=0:0){
            if(!n[j])//skip nonprimes
                continue;
            multiple=j*i;//begin at i^2
            do{
                n[multiple]=false;
            }while((multiple*=j) <= max);
        }
    }
}
//test if a number is prime by searching a given list of primes for it:
inline bool isPrime(big n, std::vector<big> p){
    return std::binary_search(p.begin(), p.end(), n);
}
#endif

Note that this is a re-post with ... proper formatting, and while I appreciate  critiques of my coding style, I would also appreciate some advice about improving the array as well (storing only numbers n with n mod 30 prime or 1, but not 2, 3, or 5).

You've posted some code, which shows what you told the computer to do.
And it even has some comments.
Honestly, that's a lot better than the average question.

Then you realize that we aren't going to understand this blob of code, so you use phrases like "I made" and "It uses Euler's Sieve" and "I need the primes up to about two billion".
Look, that's super-useful information, and I'm glad you told me that, but I'm going to suggest that in the future you put information about who wrote the program, the name of the algorithm you use, etc.
into comments embedded in the program:

// pes30.cxx
// prime number generator for Project Euler
// Print all the primes up to 2x10^9.
// 2014-05-08: started by hacatu
// implementation of Euler's sieve (a modified Sieve of Eratosthenes)
// http://en.wikipedia.org/wiki/Euler%27s_sieve
// using wheel factorization with a wheel of size 30 to reduce memory requirements
// http://en.wikipedia.org/wiki/wheel_factorization

So is there some reason not to use http://primesieve.org/ ?
Have you gotten it working without the wheel factorization optimization?
Have you tried looking at only odd prime candidates (wheel of size 2) or a small wheel of size 6 or 12 ?

I am mystified by the 3 lines

bool n[max];//array of whether or not each number is prime (30/8 too big!)
for(big i=0; i<max; ++i)//initialize the array
    n[i]=true;

The "max" is the largest number you want to check for possibly being prime during this run of the program, right?
So that line eats a bunch of memory -- one bool per each number from 0 to max, perhaps 2 million bool values.

I thought you were going to use wheel factorization to reduce memory requirements?

I think you want to replace those 3 lines with something more like the following 2 lines of code:

big blocks_of_30_values = (max/30)+1;
// For example, when max is 38, max/30 gives 1, but we need 2 blocks: 0..29 and 30..59.
// In each block of 30 values under consideration
// (i.e, the block 30..59, the block 60..89, the block 90..119, etc.),
// after using the wheel factorization to eliminate multiples of 2 and 3 and 5,
// there are only 8 potential candidates left in each block.
// So store each block in a single unsigned char:
// and initialize the array to all 1 bits (1=candidate prime, 0=definitely composite)
std::vector<unsigned char> candidatePrime( blocks_of_30_values, 0xFF );

So when max is 2 billion, we only allocate (max/30) = under 70 million chars, or roughly 533 million bits.

It might make your program easier to read if you have named functions for converting a bit in the array to the integer value it represents and vice versa:

// the bit at the n'th bit of the m'th byte of the candidatePrime array
// represents what value?
big the_value( big block_number, int bit_number ){
    const int offset[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
    int this_offset = offset[bit_number];
    return( (30*block_number) + this_offset );
}
// the given integer value n corresponds to
// what (block_number, bit_number) of the candidatePrime array?
// assumes that n is *not* a multiple of 2, 3, or 5.
big block_number( big integer_value ){
    return (integer_value/30);
}
int bit_number( big integer_value ){
    // as long as the integer_value is not a multiple of 2, 3, or 5,
    // this function should never return '9'.
    // translate a value 0..29 into the corresponding bit number 0..7
    const int bit_offset[] = {
        9, 0, 9,  9, 9, 9,
        9, 1, 9,  9, 9, 2,
        9, 3, 9,  9, 9, 4,
        9, 5, 9,  9, 9, 6
        9, 7, 9,  9, 9, 7
    };
    return bit_offset[ integer_value % 30 ];
}


Using a DependencyProperty ChangedCallback as a validation measure I have an UserControl where I declare two DependencyProperties

int? Level;
CardBase SelectedCardBase;

A non-null CardBase object will always have 2 read-only integers: MinLevel and MaxLevel.

The UserControl allows the user to change as he desires both DPs, and the internal logic must ensure that both DPs have valid values following these rules:

If SelectedCardBase is null, then Level must be null.
If SelectedCardBase is not null, then Level must be between MinLevel and MaxLevel.
When SelectedCardBase changes to anything but null, Level is set to MaxLevel.

This is the code:

    public CardBase SelectedCardBase
    {
        get { return (CardBase)GetValue(SelectedCardBaseProperty); }
        set { SetValue(SelectedCardBaseProperty, value); }
    }

    public static readonly DependencyProperty SelectedCardBaseProperty =
         DependencyProperty.Register("SelectedCardBase", typeof(CardBase), typeof(MyUserControl),
         new PropertyMetadata(null, new PropertyChangedCallback(SelectedCardBaseChanged)));

    private static void SelectedCardBaseChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
    {
        if (e.NewValue == null)
            d.SetValue(LevelProperty, null);
        else
            d.SetValue(LevelProperty, ((CardBase)e.NewValue).MaxLevel);
    }

    public int? Level
    {
        get { return (int?)GetValue(LevelProperty); }
        set { SetValue(LevelProperty, value); }
    }
    public static readonly DependencyProperty LevelProperty =
        DependencyProperty.Register("Level", typeof(int?), typeof(MyUserControl),
        new PropertyMetadata(null, new PropertyChangedCallback(LevelChanged)));
    private static void LevelChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
    {
        CardBase card = (CardBase)d.GetValue(SelectedCardBaseProperty);

        if (card == null)
        {
            if (e.NewValue != null)
                d.SetValue(LevelProperty, null);
        }
        else if (e.NewValue == null)
        {
            d.SetValue(LevelProperty, e.OldValue);
        }
        else
        {
            int level = (int)e.NewValue;

            if (level < card.MinLevel)
                d.SetValue(LevelProperty, card.MinLevel);
            else if (level > card.MaxLevel)
                d.SetValue(LevelProperty, card.MaxLevel);
        }
    }

I don't fully get how CoerceValueCallbacks work, and I've read (or misunderstood) that both Coerce and Changed callbacks can be overwritten because they are metadata, so my questions are:

What problems (if they exist) will I have when something subscribes to the OnValueChanged of one of those DP?
Should I use CoerceValueCallbacks instead of this?
If so, what is the correct way of doing this using CoerceValueCallbacks?
And of course, with the given rules at the beginning, there is any mistake on the  code that would cause strange behaviour, or anything that could be improved?

Yes, you should use CoerceValueCallback instead to coerce your Level property (what you are trying to do is not "validation" strictly speaking).

private static object CoerceLevel(DependencyObject d, object value)
{
    var control = (MyUserControl)d;
    if (control.SelectedCard == null) return null;
    var level = (int?)value;
    if (level.HasValue)
    {
        return Math.Min(Math.Max(level.Value, control.SelectedCard.MinLevel), control.SelectedCard.MaxLevel);
    }
    else
    {
        return control.Level;
        //or
        //return DependencyProperty.UnsetValue;
    }
}


jQuery-like library for learning purposes I am attempting to build a small JavaScript library (similar to jQuery)

The purpose behind this is mostly a learning exercise, so asking why I don't just use an existing library is moot.

So far I have just got my basic constructor, a 'caller' function to invoke a new object, and some basic functions for an example.

var lemon = function() {
    var prop = {
        collection: []
    };
    var fn = {
        init: function(selector, context) {
            context = context || document;
            if (!selector) {
                return;
            } else if (typeof selector == "string") {
                prop.collection = fn.toArray(context.querySelectorAll(selector));
            } else if (selector instanceof Array || selector instanceof NodeList) {
                fn.toArray(selector).forEach(function(obj) {
                    prop.collection.push(obj);
                });
            } else if (selector instanceof Element) {
                prop.collection.push(selector);
            }
            prop.length = prop.collection.length;
            fn.extend.apply(this, [this, prop, fn]);
        },
        toArray: function(target) {
            var array = [];
            for (var i = target.length >>> 0; i--;) {
                array[i] = target[i];
            }
            return array;
        },
        extend: function(target) {
            var objects = Array.prototype.slice.call(arguments, 1);
            objects.forEach(function(obj) {
                var props = Object.getOwnPropertyNames(obj);
                props.forEach(function(key) {
                    target[key] = obj[key];
                });
            });
            return target;
        },
        addClass: function(klass) {
            for (var i = 0, l = this.length; i < l; i++) {
                this.collection[i].className += " " + klass;
            }
            return this;
        }
    };
    fn.init.apply(this, fn.toArray(arguments));
};
var $ = function(selector, context) {
    return new lemon(selector, context);
};

There is quite a performance problem with your code: it will rebuild the fn object and all its methods every time the lemon(selector, context) constructor gets called. You can avoid that behavior by using the module design pattern:

this.lemon = (function () {

    var fn = {
    /* The code for the fn object here
        init: function (selector, context) {
            var prop = this.prop;
            ...
    */

    return function lemon() {
        this.prop = {
            collection: []
        };
        fn.init.apply(this, fn.toArray(arguments));
    };

 })();

However, you will have to add a line var prop = this.prop; in the beginning of every method of the fn object that requires prop.

Also, when introducing a new global variable, it is better for the readability of your code to use this.myVar = myValue; or window.myVar = myValue;. In fact, the var keyword should only be used for local variables.

Finally, it is often recommended to put a space between the function keyword and the following parenthesis, but that's not mandatory.


C: Sieve of Eratosthenes and next twin prime I am wondering if I can get some feedback for my implementation of "Sieve of Eratosthenes" and twin prime. I followed this pseudocode.
Few notes:

I added MAX(primes.size << 1, (x << 1) + 1) to make I resize the table large enough to find the next twin prime.
Use a struct to keep track of the size of the dynamic array

Things I am concerned about:

Using POW
goto statement

Only playground to test the code: https://www.onlinegdb.com/HydogHGxw
Thank you.
#include "prime.h"
#include <math.h>
#include <stdbool.h>
#include "stdlib.h"
#include "string.h"

#define INITIAL_TABLE_SIZE 9973
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

typedef struct
{
  bool *array;
  unsigned int size
} PRIMES;

PRIMES primes = {NULL, 0};

/**
 * Create a boolean array "prime[0..n]" and initialize
 * all entries it as true. A value in prime[i] will
 * finally be false if i is Not a prime, else true.
 */
void sieve_of_eratosthenes(int n)
{
  if (primes.array != NULL)
  {
    free(primes.array);
  }

  primes.size = n;
  primes.array = malloc(n * sizeof(bool));
  memset(primes.array, true, n * sizeof(bool));

  primes.array[0] = false;
  primes.array[1] = false;

  int i, j;
  for (i = 2; i < (int)sqrt((double)n); i++)
  {
    // If primes[p] is not changed, then it is a prime
    if (primes.array[i] == true)
    {
      // Update all multiples of p
      for (j = (int)pow((int)i, 2); j < n; j += i)
      {
        primes.array[j] = false;
      }
    }
  }
}

/**
 * Return the next prime greater than parameter such that -2 is also a prime
 */
int next_twin_prime(int x)
{
  if (primes.array == NULL)
  {
    sieve_of_eratosthenes(INITIAL_TABLE_SIZE);
  }

resize:

  if (x >= primes.size)
  {
    int new_size = MAX(primes.size << 1, (x << 1) + 1);

    sieve_of_eratosthenes(new_size);
  }

  int i;
  for (i = x; i < primes.size; i++)
  {
    if (primes.array[i] == true && primes.array[i - 2] == true)
    {
      return i;
    }
  }

  goto resize;
}

Your Concerns
The use of pow(i, 2) is unnecessary; you should simply use i*i.
The goto statement is also unnecessary.  You could wrap the code in while(true) { ... }.
Other Concerns
The cast (int) i is also unnecessary, as i is already an integer.  Perhaps you meant to cast to a double?
Computing sqrt(n) in the for loop termination condition is inefficient; you should compute it once outside the loop.
The primes global should probably be declared static, so it isn’t visible outside the module.  Then the “helper” function sieve_of_eratosthenes should also be static.
Your overflow and resizing of the sieve does not preserve any previous work; perhaps you could use realloc?
No twin prime pair would ever be even, so you could optimize the sieve to skip even numbers.
This statement memset(primes.array, true, n * sizeof(bool)); is questionable.  If a bool is larger than 1 byte, then what are you storing in the array?  For instance, if each sizeof(bool) == 2, then primes.array[0] would be 0x0101, which is not the same as true.


Suffix Tree in Python I was wondering why the following implementation of a Suffix Tree is 2000 times slower than using a similar data structure in C++ (I tested it using python3, pypy3 and pypy2). I know the bottleneck is the traverse method, do you spot chance of optimisation in the following code? Thanks!

from sys import stdin, stdout, stderr, setrecursionlimit
setrecursionlimit(100000)

def read():
    return stdin.readline().rstrip()

def readint():
    return int(read())

def make_node(_pos, _len):
    global s, n, sz, to, link, fpos, slen, pos, node
    fpos[sz] = _pos
    slen[sz] = _len
    sz += 1
    return sz-1

def go_edge():
    global s, n, sz, to, link, fpos, slen, pos, node
    while (pos > slen[to[node].get(s[n - pos], 0)]):
        node = to[node].get(s[n - pos], 0)
        pos -= slen[node]

def add_letter(c):
    global s, n, sz, to, link, fpos, slen, pos, node
    s[n] = c
    n += 1
    pos += 1
    last = 0
    while(pos > 0):
        go_edge()
        edge = s[n - pos]
        v = to[node].get(edge, 0)
        t = s[fpos[v] + pos - 1]
        if (v == 0):
            to[node][edge] = make_node(n - pos, inf)
            link[last] = node
            last = 0
        elif (t == c):
            link[last] = node
            return
        else:
            u = make_node(fpos[v], pos - 1)
            to[u][c] = make_node(n - 1, inf)
            to[u][t] = v
            fpos[v] += pos - 1
            slen[v] -= pos - 1
            to[node][edge] = u
            link[last] = u
            last = u
        if(node == 0):
            pos -= 1
        else:
            node = link[node]

def init_tree(st):
    global slen, ans, inf, maxn, s, to, fpos, slen, link, node, pos, sz, n

    inf = int(1e9)
    maxn = len(st)*2+1 #int(1e6+1)
    s = [0]*maxn
    to = [{} for i in range(maxn)]
    fpos, slen, link = [0]*maxn, [0]*maxn, [0]*maxn

    node, pos = 0, 0
    sz = 1
    n = 0

    slen[0] = inf
    ans = 0
    for c in st:
        add_letter(ord(c))

text = "TTTTTTTTTT" + 1777*"A" + "$"
query = 1750*"A"

def traverse_edge(st, idx, start, end):
    global len_text, len_st
    k = start
    while k <= end and k < len_text and idx < len_st:
        if text[k] != st[idx]:
            return -1
        k += 1
        idx += 1
    if idx == len_st:
        return idx
    return 0

def edgelen(v, init, e):
    if(v == 0):
        return 0
    return e-init+1

def dfs(node, leafs, off):
    if not node:
        return
    k, tree = node
    if not isinstance(tree, int): # it is a node pointing to other nodes
        for kk, value in tree.items():
            if slen[value] > 190000000:
                leafs.append(fpos[value]-off)
            else:
                dfs((kk, to[value]), leafs, off+slen[value])

def traverse(v, st, idx, depth=0):
    global len_st
    result = cache.get((v, st), -2)
    if result != -2:
        return result
    r = -1
    init = fpos[v]
    end = fpos[v]+slen[v]
    e = end-1
    if v != 0:
        r = traverse_edge(st, idx, init, e)
        if r != 0:
            if r == -1:
                cache[(v, st)] = []
                return []
            depth += r
            # Here is when we found a match
            leafs = []
            dfs((v, to[v]), leafs, depth)
            #return reversed(leafs)
            return leafs
    idx = idx + edgelen(v, init, e)
    if idx > len_st:
        cache[(v, st)] = []
        return []
    k = ord(st[idx])
    children = to[v]
    if k in children:
        vv = children.get(k, 0)
        matches = traverse(vv, st, idx, depth)
        cache[(v, st)] = matches
        return matches
    return []

def main():
    global text, len_st, len_text, cache
    init_tree(text)
    len_text = len(text)
    len_st = len(query)
    r = []
    #cache = {}
    for runs in range(1000):
        cache = {}
        matches = traverse(0, query, 0)
        r.append("\n".join(str(m) for m in matches))
    stdout.write("\n".join(r)+"\n")

main()

So, about all those globals. They make your code really hard to read, I have almost no idea what is going on (after having read it twice). The general recommendation is to only use global objects if you really have to. Otherwise pass the objects either as arguments to the function, or write a class which has the relevant variables as attributes and keep the state like this.

Another thing that makes your code a lot easier to understand (both for other people and for yourself in two months time), are docstrings, which document what each function does, the parameters it takes and what it returns or modifies.


HackerRank - The Grid Search Was playing around tonight and thought this problem was interesting enough to post here.

  Given a 2D array of digits, try to find the location of a given 2D
  pattern of digits.

  Input Format

  The first line contains an integer, T, which is the number of test
  cases.

  T test cases follow, each having a structure as described below:
  The first line contains two space-separated integers, R and C,
  indicating the number of rows and columns in the grid G,
  respectively.

  This is followed by R lines, each with a string of C digits, which
  represent the grid G.

  The following line contains two space-separated integers, r and c,
  indicating the number of rows and columns in the pattern grid P.

  This is followed by r lines, each with a string of c digits, which
  represent the pattern P.

  Output Format

  Display YES or NO, depending on whether (or not) you find that the
  larger grid G contains the rectangular pattern P. The evaluation
  will be case sensitive.

Taken from HackerRank challenge "The Grid Search." Much more detailed explanation there. I borrowed this writeup from a similar question.

Any feedback appreciated - this passes all the tests. I did not really try to optimize beyond passing the test cases and making it fairly simple in order to do that.

Specifically am curious about:

Ability to streamline the nested if statements and loops
All the match/find stuff seems clunky
I don't like all the break statements and my cont boolean, is there a better way to early exit this?

Anything else would be appreciated too. the initial chunk is all system input stuff which I did not change but pasted here in case anyone wants to run it on HackerRank.

#!/bin/python3

import sys

t = int(input().strip())
for a0 in range(t):
    R,C = input().strip().split(' ')
    R,C = [int(R),int(C)]
    G = []
    G_i = 0
    for G_i in range(R):
       G_t = str(input().strip())
       G.append(G_t)
    r,c = input().strip().split(' ')
    r,c = [int(r),int(c)]
    P = []
    P_i = 0
    for P_i in range(r):
       P_t = str(input().strip())
       P.append(P_t)

    # everything above here is auto generated by the site for parsing input

    result = 'NO'

    # search each potential matching row
    for y in range(R - r + 1):
        match_index = -1
        cont = True

        # search vertically for every time that the first row in the search matrix matches
        while cont:
            match_index = G[y].find(P[0], match_index + 1)
            if match_index < 0:
                cont = False

            # check to ensure row in outcome matches input
            for y_p in range(r):
                G_sub = str(G[y + y_p][match_index : match_index + c])
                P_sub = str(P[y_p])
                if G_sub != P_sub:
                    break

                if y_p == r - 1:
                    result = 'YES'
                    break

    print(result)

Being given some generated code doesn't mean you can't criticize it. Unused imports, unused variables, meaningless variable names, unpythonic constructs… To organize things a bit more, you should also
Use functions
This is to separate the parsing of the input from the core of the computation. It can help you further test your logic without rellying on the input being fed through stdin. A basic layout could be:
def find_pattern_in_grid(grid, pattern, pattern_height=None, pattern_width=None):
    if pattern_height is None or pattern_width is None:
        pattern_height = len(pattern)
        pattern_width = len(pattern[0])

    return False  # Placeholder

def run_test_case():
    grid_height = int(input().split()[0])  # Dropping grid width, we don't use it
    grid = [input() for _ in range(grid_height)]
    pattern_height, pattern_width = map(int, input().split())
    pattern = [input() for _ in range(pattern_height)]

    return find_pattern_in_grid(grid, pattern, pattern_height, pattern_width)

def main():
    test_cases = int(input())
    for _ in range(test_cases):
        if run_test_case():
            print('YES')
        else:
            print('NO')

if __name__ == '__main__':
    main()

A few things to note here:

input() does not return the end-of-line character, so there is no need to strip() it;
even if it didn't, split() without argument have special logic to remove extraneous whitespace around words;
when building the grid or pattern you don't need to split since there is no whitespace in the rows. Even if it had, working with strings and sub-strings can be more efficient as you already do;
find_pattern_in_grid accept optional pattern_height and pattern_width so you can easily drop into an interactive session, import your file and feed this function with any pre-formatted input you want without having to bother computing the number of rows and columns beforehand;
dropping in an interactive session like that is the reason why it's a good habit to have an if __name__ == '__main__' clause that wraps all your top-level code.

As a bonus, having functions will let you return early so you might be able to remove flag variables.
Iterate over rows
Python makes it easy to iterate over content rather than using indexes to access the content. It is both faster and more pythonic. In case you need the indexes too, use enumerate:
def find_pattern_in_grid(grid, pattern, pattern_height, pattern_width):
    # search each potential matching row
    for y, row in enumerate(grid[:1-pattern_height]):  # [:-pattern_height+1]
        reduced_grid = grid[y:]  # Keep only the remaining row for further comparison

        # search vertically for every time that the first row in the search matrix matches
        match_index = row.find(pattern[0])
        while match_index != -1:
            # check to ensure row in outcome matches input
            for pattern_row, grid_row in zip(pattern, reduced_grid):
                grid_sub = grid_row[match_index:match_index+pattern_width]
                if grid_sub != pattern_row:
                    break
            else:
                return True

            # We didn't find the pattern, try another match
            match_index = row.find(pattern[0], match_index + 1)

    # Remaining of the grid turned out to be less than the pattern height
    return False

Here I used:

slicing (grid[y:]) and zip to iterate over both the remaining rows of the grid and the rows of the pattern at the same time;
for .. else to execute the else clause if (and only if) no break were reached within the for loop. Meaning no mismatch were found between the grid and the pattern.

I also incorporated the "match" condition directly within the while loop. But it lead to somewhat duplicated find as you can see, so not that ideal. And I removed the call to str since slicing a string already returns a string.


A Java class that prints a matrix I am trying to learn some generic programming with Java:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by PACKAGE_NAME on 15/11/14.
 */
public class PrintMatrix {
    public static <T> void printma(ArrayList<ArrayList<T>> matrix) {
        ArrayList<Integer> sizes = new ArrayList<>();
        for(ArrayList<T> row : matrix) {
            sizes.add(row.size());
        }
        Set<Integer> sizesSet = new HashSet<>(sizes);
        Integer[] sizesArray = sizesSet.toArray(new Integer[0]);
        Integer nCol = sizesArray[0];
        Integer nRow = matrix.size();

        if(sizesSet.size() > 1) {
            System.err.println("This is not a matrix.");
            return;
        }

        for(int i=0; i<nRow; i++) {
            for(int j=0; j<nCol; j++) {
                System.out.printf("%s\t", matrix.get(i).get(j).toString());
            }
            System.out.println();
        }
    }

    public static <T> void printmb(ArrayList<T[]> matrix) {
        ArrayList<Integer> sizes = new ArrayList<>();
        for(T[] row : matrix) {
            sizes.add(row.length);
        }
        Set<Integer> sizesSet = new HashSet<>(sizes);
        Integer[] sizesArray = sizesSet.toArray(new Integer[0]);
        Integer nCol = sizesArray[0];
        Integer nRow = matrix.size();

        if(sizesSet.size() > 1) {
            System.err.println("This is not a matrix.");
            return;
        }

        for(int i=0; i<nRow; i++) {
            for(int j=0; j<nCol; j++) {
                System.out.printf("%s\t", matrix.get(i)[j].toString());
            }
            System.out.println();
        }
    }
}

Your two print methods are odd in the sense that they are inconsistent with how you present them. A 'classic' matrix consists of primitive arrays (like int[][]), and not nested containers (like ArrayList<ArrayList<T>>). I can understand why you have one and also the other, but the mix of them is bizarre, ArrayList<T[]>. Remove the second print method.

Let's go through some other items first though. Let's narrow the ArrayList down to the interface level, just List. There is no reason to constrain the method to the concrete implementation because that severely restricts the applicability. I would actually go further and constrain it to Iterable. This produces the signature:

public static <T, R extends Iterable<T>, M extends Iterable<R>> void printMatrix(M matrix) {
    ....
}

What am I saying there? I am saying that the Matrix can consist of any combination of values that may have an Iterator. The mnemonics I use there are that:

T is the type of the cell data
R is the type of each row (which can be anything that is of type Iterable<T>)
M is the combined Matrix, which can be any Iterable of <R> (i.e. it's a collection of rows)

This is a generic method. You can throw pretty much anything at it from any collection structure.

An implementation of the method would look something like:

public static <T, R extends Iterable<T>, M extends Iterable<R>> void printMatrix(M matrix) {
    int size = -1;
    for (R row : matrix) {
        int s = 0;
        for (@SuppressWarnings("unused") T value : row) {
            s++;
        }
        if (size < 0) {
            size = s;
        } else if (size != s) {
            System.err.println("This is not a matrix.");
            return;
        }
    }

    StringBuilder sb = new StringBuilder();
    for (R row : matrix) {
        sb.setLength(0);
        for (T value : row) {
            sb.append(value).append('\t');
        }
        if (sb.length() > 0) {
            sb.setLength(sb.length()-1);
        }
        System.out.println(sb);
    }
}

and this could be used, for example, like:

public static void main(String[] args) {
    List<Collection<Object>> data = new ArrayList<>();
    data.add(System.getProperties().keySet());
    data.add(System.getProperties().values());
    printMatrix(data);
}

You should note a few things here:

The only reference to any concrete class here is the new ArrayList<>() in the main method. Everything else is treated at the lowest usable interface level (Collections, Lists, Iterables).
I use StringBuilder to build things 1 line at a time. This improves performance because each print is expensive, so you do fewer prints.
Java8 has a better way of counting the members, and also joining the Strings with the \t character:

for (R row : matrix) {
    long s = StreamSupport.stream(row.spliterator(), false).count();
    if (size < 0) {
        size = s;
    } else if (size != s) {
        System.err.println("This is not a matrix.");
        return;
    }
}

for (R row : matrix) {
    StringJoiner sj = new StringJoiner("\t");
    row.forEach(v -> sj.add(String.valueOf(v)));
    System.out.println(sj);
}

There is no need for the array-of-Integer to count the number of values in each line.
By putting the complexity of the generic types in the static method generics declaration area, the actual parameter has the simple type M.


Applying Function to `Seq[B]` in `Seq[Either[A, B]]` Given:

  def rights[A, B](xs: Seq[Either[A, B]]): Seq[B] =
    xs.flatMap {
      case Right(x) => List(x)
      case Left(_)  => List.empty
    }

  def lefts[A, B](xs: Seq[Either[A, B]]): Seq[A] =
    xs.flatMap {
      case Right(_) => List.empty
      case Left(x)  => List(x)
    }

  def combine[A, B](xs: Seq[A], ys: Seq[B]): Seq[Either[A,B]] = {
    val l: Seq[Either[A, B]] = xs.map(Left[A,B](_))
    val r: Seq[Either[A, B]] = ys.map(Right[A,B](_))
    l ++ r
  }

Is there a better way to do the following, i.e. apply distinct to the Right[Int] in the Seq[Either[String, Int]].

Look to res1 in the below output as the desired output.

scala> val xs: Seq[Either[String, Int]] = List( Left("foo"), Right(42), Right(6), Right(42) )
xs: Seq[Either[String,Int]] = List(Left(foo), Right(42), Right(6), Right(42))

scala> val distinct = rights(xs).distinct
distinct: Seq[Int] = List(42, 6)

scala> combine(lefts(xs), distinct)
res1: Seq[Either[String,Int]] = List(Left(foo), Right(42), Right(6))

The problem with @hayden.sikh's answer (the one that preserves order) is that it has a suboptimal complexity, and is especially inefficient if the Seq is a List (which it is in your REPL session). Appending an element to a list with :+ has linear complexity. Calling contains on a sequence too. So this is O(n^2).

It would be easy to adapt the answer by using a Set in the foldLeft accumulator, appending with +: and reversing the list at the end.
Or, to avoid the complexity and the cost of maintaining an immutable Set, simply use a mutable one and a flatMap:

val seen = mutable.HashSet[Int]()
xs flatMap { case Right(x) => if (seen(x)) None else { seen += x; Some(Right(x)) }
             case x => Some(x) }

Mutability is fine as long as it's kept local, for example as a detail in an algorithm's implementation (most of the algorithms of the Scala standard library use mutability too, including distinct!).


Graph coloring in Java I'm solving the m-coloring problem using java. and I have following code that uses concept of recursion and backtracking.

import java.util.Arrays;

public class GraphColoring {

    static void graphColor(int k, int m, int n, int colors[], int graph[][]) {
        for (int c = 1; c <= m; c++) {
            if (isSafe(k, c, n, colors, graph)) {
                colors[k] = c;
                if (k + 1 < n)
                    graphColor(k + 1, m, n, colors, graph);
            }
        }
    }

    static boolean isSafe(int k, int c, int n, int[] colors, int graph[][]) {
        for (int i = 0; i < n; i++) {
            if (graph[k][i] == 1 && c == colors[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {

        int n = 4, m = 3;
        int[] colors = new int[n];
        int graph[][] = { { 1, 1, 0, 1 }, { 1, 1, 1, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 } };
        graphColor(0, m, n, colors, graph);
        System.out.println(Arrays.toString(colors));

    }
}

  OUTPUT

1 2 1 3

I would like review about its performance, time complexity and improvements. Also If I'm missing any corner cases please let me know as this code is tested on very few examples as I didn't find any online problem that checks its appropriate output.

Also If I'm missing any corner cases please let me know as this code is tested on very few examples as I didn't find any online problem that checks its appropriate output.

[emphasis mine]

Graph colouring is a relatively nice problem in that regard: you can easily check the validity of the result. The only conditions are that every vertex must have a color, the number of colors must be less-than-or-equal-to m, and neighboring vertices don't share a color. So as a test you could generate random graphs (or for small graphs, enumerate all symmetric graphs without self-loops), color them, and theck the results. Any valid coloring is appropriate. The main problem is testing whether graphs that your algorithm decides are not m-colorable are actually not m-colorable.

I suspected there was such an issue (as this algorithm never "uncolors" a vertex, it should be possible for it to get stuck) so I enumerated some graphs to find a concrete breaking test-case:

int n = 6, m = 3;
int[][] graph = {
    {0, 1, 0, 0, 1, 1},
    {1, 0, 1, 1, 0, 1},
    {0, 1, 0, 1, 0, 0},
    {0, 1, 1, 0, 0, 1},
    {1, 0, 0, 0, 0, 0},
    {1, 1, 0, 1, 0, 0}};

This algorithm results in [1, 2, 1, 3, 3, 0], the zero indicating that no valid coloring was found, but there actually are valid colorings, for example [1, 2, 3, 1, 2, 3]. Just to confirm that it's a valid coloring, here it is as a drawing:

Keep in mind though that if there is one valid coloring, there are almost always many more. Even if there are no fundamentally different colorings, the color-names can be permuted to yield a superficially different-looking coloring. So test-cases should not compare for equality with some coloring found by a different solver, that's too strict.

To find that case I had to implement an other graph colorer that is capable of coloring the graph above, I used this small rewrite of your code:

static int[] graphColor(int m, int[][] graph) {
    int[] colors = new int[graph.length];
    // the color of the first vertex is a free pick
    colors[0] = 1;
    if (graphColorInternal(1, m, colors, graph))
        return colors;
    else
        return null;
}

static boolean graphColorInternal(int k, int m, int colors[], int graph[][]) {
    for (int c = 1; c <= m; c++) {
        if (isSafe(k, c, colors, graph)) {
            colors[k] = c;
            if (k + 1 < colors.length) {
                if (graphColorInternal(k + 1, m, colors, graph))
                    return true;
                colors[k] = 0;
            }
            else
                return true;
        }
    }
    return false;
}

static boolean isSafe(int k, int c, int[] colors, int graph[][]) {
    for (int i = 0; i < colors.length; i++) {
        if (graph[k][i] == 1 && c == colors[i])
            return false;
    }
    return true;
}

In addition to the line colors[k] = 0; which gets the solver "unstuck" after backtracking, there are some more changes that I would like to highlight:

The function graphColor that is supposed to be called returns its result, rather than modifying a function argument. Generally you should prefer that. Output-parameters should be avoided, unless there is a good enough reason not to.
graphColor does not take redundant parameters (n, which it knows from the graph itself).
The search indicates explicitly whether it found something or failed, so the wrapper does not have to inspect the coloring to find that out.
The search returns immediately after finding a valid coloring. The original algorithm does not return immediately, it tries to fill in different colors though most of it fails because isSafe returns false a lot when given a filled coloring.

  I would like review about its performance, time complexity and improvements.

Not much can be done about the time complexity, not for the worst case anyway: graph coloring is NP-complete after all.

But there are things that can be done.

Rather than coloring the vertices simple in order of their index, color them in order of Most Constrained Variable (MCV) first, that is, color the vertex with the most colored neighbors first.
Maintain a set of "possible colors" for every vertex. This makes it easy to detect early that the current partial-coloring is no good (if any vertex has an empty set of colors left, backtrack), and easy to find the MCV (uncolored vertex with the smallest set of possible colors). It also means that rather than checking isSafe for every color, the solver already has a list of possible colors - though of course it pays for that by maintaining those sets every time the color of a vertex is changed.
Advanced: improve those sets of possible colors with the AC-3 Algorithm or similar.


Find most occurred number in sorted array of numbers I was asked in an interview to find the a number in an sorted array of numbers which has occurred maximum number of times. Also find the count of occurrence of that number.

I solved it in javascript, please follow the code

var numArray = [];

// takes the space separated numbers from commanline
// and inserts in array numArray.
process.argv.forEach(function(val, index, array){
   if(index > 1){
      numArray.push(parseInt(val));
   }
});

(findMaxOccuredNum)(numArray);

function findMaxOccuredNum(nums){
   var currentCount = 0,
       prevCount = 0,
       currentNum = 0,
       prevNum = 0;

   for(var i = 0; i < nums.length; i++){
       if((nums[i] === 0 && i === 0) || (i === 0 && nums[i] !== 0)){
          currentNum = nums[i];
          currentCount++;
       }else if(nums[i] === currentNum){
          currentCount++;
       }else {
          if(prevCount < currentCount){
              prevNum = currentNum;
              prevCount = currentCount;
              currentNum = nums[i];
              currentCount = 1;
          }else{
              currentNum = nums[i];
              currentCount = 1;
          }

       }//else
   }// for

   if(prevCount < currentCount){
      console.log("NUM "+currentNum+" occurred "+currentCount+" times");
   }else{
      console.log("NUM "+prevNum+" occurred "+prevCount+" times");
   }
} //findMaxOccuredNum

Below are some outputs

rahul@rahul:~/myPractise/Algo$ node NumCount.js 1 1 1 2 3 4 9 9
NUM 1 occurred 3 times

rahul@rahul:~/myPractise/Algo$ node NumCount.js 1 2 2 2 3 3 6 6
NUM 2 occurred 3 times

rahul@rahul:~/myPractise/Algo$ node NumCount.js 0 0 1 1 3 3 3 5 5
NUM 3 occurred 3 times

rahul@rahul:~/myPractise/Algo$ node NumCount.js 0 0 0 1 1 3
NUM 0 occurred 3 times

Requesting to please review my code and give your valuable comments on whether my code is the perfect solution for the above problem or it can be solved in better way.

You should always question the question when given problems like this. For example, what if the input data is empty? What if there are two different values that appear the same number of times? etc. What if there are negative values?

Also, when dealing with problems like this its often best to separate the function doing the work, from the code presenting the result.

I would return an object from the function so that the "calling" code can look like:

var result = maxVal(data)
if (result.count) {
    console.log("NUM "+result.value+" occurred "+result.count+" times");
} else {
    console.log("No values in the data");
}

Then, I would also simplify your logic a whole bunch. You don't need to keep all those nested if statements.... You need just one test condition, and then an if/else condition...

function findMaxOccuredNum(nums){
    var result = {
        count: 0,
        value: 0
    };

    if (!nums) {
        return result;
    }

    var value = 0;
    var count = 0;

    for (var i = 0; i < nums.length; i++) {
        if (nums[i] != value) {
            count = 0
            value = nums[i];
        }
        count++;
        if (count > result.count) {
            result.count = count;
            result.value = value;
        }
    }
    return result;
}

function findMaxOccuredNum(nums){
        var result = {
            count: 0,
            value: 0
        };

        if (!nums) {
            return result;
        }

        var value = 0;
        var count = 0;

        for (var i = 0; i < nums.length; i++) {
            if (nums[i] != value) {
                count = 0
                value = nums[i];
            }
            count++;
            if (count > result.count) {
                result.count = count;
                result.value = value;
            }
        }
        return result;
    }

    function format(result) {
        return `Value ${result.value} & Count ${result.count}`;
    }
Result: <input id="output" type="text" cols="90">
<p>
<input type="button" onClick="alert(format(findMaxOccuredNum([0,1,2,3,4,4,5])));" value="[0,1,2,3,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([0,0,0,0,,1,2,3,4,4,5])));" value="[0,0,0,0,,1,2,3,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([-1,-1,-1,0,1,2,4,4,5])));" value="[-1,-1,-1,0,1,2,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([0,1,2,3,4,5])));" value="[0,1,2,3,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([0,1,2,3,4,4,5])));" value="[0,1,2,3,4,4,5]">
<input type="button" onClick="alert(format(findMaxOccuredNum([])));" value="[]">
<input type="button" onClick="alert(format(findMaxOccuredNum()));" value="null">


Fetching a post from the database based on a query parameter I get an id via Get request to fetch an object from the database.

I have used mysqli prepared statements to avoid any security problems. As I am new to these stuff I would like a confirmation that implemented the logic correctly and safe.

User goes to

website.com/post.php?post=130

In post.php i do the following:

Check if user sent a value in "post" parameter, otherwise redirect to the start page:

if(strlen($_GET["post"]) == 0){
    header("Location: index.php");
    exit();
}

then i use the paramter to fetch the object from the database:

$requestedID = $_GET["post"];
if(is_numeric($requestedID)){
  if($stmt = $mysqli->prepare("SELECT * FROM posts WHERE id =?")) {
     $stmt->bind_param('s', $requestedID);
     $stmt->execute();
     $result = $stmt->get_result();

     if($result->num_rows > 0) {
        $row = $result->fetch_assoc();
        // logic for the content
     }else{
        header("Location: index.php");
        exit();
     }

   } else {
     header("Location: index.php");
     exit();
   }
 }else {
    header("Location: index.php");
    exit();
 }

Is my mysqli code secure?  Is my handling of GET parameter secure enough? Do you see anything that concerns you?

There are two things that jump out at me:

You assume $_GET['post'] exists.

If someone just goes to post.php without specifying a parameter, $_GET['post'] is not set -- and any attempt to read it would trigger a notice like "Undefined index: post". Checking the length won't make that notice go away; even the act of getting the length starts with the assumption that your parameter exists.

You really ought to put that variable into a known state before you make any assumptions about it. It might be as simple as, say:

$requestedID = isset($_GET['post']) ? $_GET['post'] : null;

You don't even need the strlen check; null and '' aren't numeric, so they'd both fail the is_numeric check.

(Course, the bigger issue is that you have error reporting set to ignore notices. You should generally be developing with error reporting turned all the way up, even if you turn it back down for production.)
You repeat the same error-case code three times.  If you ever want to change how you handle nonexistent or unspecified post IDs, you have to change the code in three places.

That could be fixed by changing the flow a bit.

$requestedID = isset($_GET["post"]) ? $_GET['post'] : null;
$row = null;

if (is_numeric($requestedID)) {
  if ($stmt = $mysqli->prepare("SELECT * FROM posts WHERE id =?")) {
    $stmt->bind_param('s', $requestedID);
    $stmt->execute();
    $result = $stmt->get_result();

    # oh...this too.  $result can be false if something went wrong.
    if ($result && $result->num_rows > 0) {
      $row = $result->fetch_assoc();
    }
  }
}

// $row is only set (and truthy!) if you succeeded
if ($row) {
  // logic for the content
}
else {
  header("Location: index.php");
  // exit(); not necessary if this is the last line of the script
}


Truncate String Method I have 2 Truncate string methods.

First:

public static string Truncate(string source, int length)
    {
    if (source.Length > length)
    {
        source = source.Substring(0, length);
    }
    return source;
    }

Second:

public static string Truncate2(string source, int length)
    {
    return source.PadRight(length).Substring(0, length).Trim();
    }

Which of these methods is better, faster?

The question is moot, as the methods give different results. It doesn't matter if a method is faster, better, simpler, nicer, fancier or cooler if it doesn't work properly.

The first method works as expected. It always truncates the string to the desired length, if the string is long enough to truncate. (Note though that this could break a combination of unicode characters used to compose a character, but that's a whole different level of expectations.)

The second method will behave badly if the string that you try to truncate contains whitespace characters in the "wrong" place.

For example, Truncate2("A   B", 3) returns "A" instead of "A  ".

The method will even crash in some situations where it should just return the input unchanged. To get an OutOfMemoryException you can call Truncate2("", Int32.MaxValue).


Reserving seats in a movie theater I'm writing a C program to reserve seats in a movie theater. I am validating the selection of seats:

const int TOTAL_ROWS = 10;            // 1 to 26 -> 'A' to 'Z'
const int SEATS_PER_ROW = 5;          // 1 to 9
int seats[TOTAL_ROWS][SEATS_PER_ROW]; // reserved seats, reserved seat == 1
char codes[TOTAL_SEATS][2];           // selected seats, e.g. A1, ..., Z9
...
for (i = 0; i < required_seats; i++) {
    printf("Enter the code for the seat: %i: ", i + 1);
    scanf("%s", codes[i]);
    if (codes[i][0] >= 'A' &&
        codes[i][0] <= 'A' + TOTAL_ROWS - 1 &&
        codes[i][1] >= '1' &&
        codes[i][1] <= '1' + SEATS_PER_ROW - 1) {

        if (seats[codes[i][0] - 'A'][codes[i][1] - '1'] == 1) {
            printf("Reserved seat. Select other.\n");
            i--;
        }
        for (j = 0; j < i; j++) {
            if (codes[j][0] == codes[i][0] && codes[j][1] == codes[i][1]) {
                printf("Repeated selection. Select other.\n");
                i--;
                break;
            }
        }
    } else {

        printf("Invalid code for seat.\n");
        i--;
    }
}

This code works fine. However, how can I refactor the code for this loop? In my opinion, using i-- does not look professional.

* By the way, you may want to see the full code —originally, in Spanish.

I/O

You want to read 2 characters although you use scanf("%s", codes[i]) this can have the effect you are overwriting the end of the buffer when you read scanf("%s", codes[required_seats-1]); since there is always an \0 added to your two characters.

Either increase the buffer, change the format specifier or use an alternative method of reading from keyboard e.g. fgets() followed by sscanf() or simply read the characters one by one using fgetc(). The latter method has the advantage that you could prevent the user from entering invalid characters while he types.

You may also want to convert the characters to upper case just to be a bit more flexible towards the user (toupper())

structure

I think the code could do with some more functions to clarify the purpose.

E.g.

int isCodeValid(char* code)
{
  return code[0] >= 'A' && code[0] <= 'A' + TOTAL_ROWS - 1 &&
     code[1] >= '1' &&  code[1] <= '1' + SEATS_PER_ROW - 1;
}

int isRepeatedSelection(char* codes);
...

loop

What other suggested and as you mentioned already decrementing i in the for loop may be a bit confusing for the reader (well it was for me at least), having a do..while loop feels more natural here where the while condition is false until user enters correct code (or changes his mind and gives up).


Generic Singly-Linked List implementation I'm looking for some feedback regarding my implementation of a generic singly-linked list in C#. I'm also looking for some tips on how to implement other techniques such as using IEnumerable or other .NET interfaces I'm currently not aware of.

Node.cs

using System;
namespace SinglyLinkedLists
{
    public class Node<T>
    {
        private Node<T> _next;
        private T _data;

        public Node<T> next{
            get { return _next; }
            set { _next = value; }
        }

        public T data{
            get { return _data; }
            set { _data = value; }
        }

        public Node(T newData){
            this._data = newData;
            this._next = null;
        }

        public static void printNodes(Node<T> head){
            Node<T> currentNode = head;
            while (currentNode != null){
                Console.WriteLine(currentNode.data);
                currentNode = currentNode.next;
            }
        }
    }
}

SinglyLinkedLists.cs

using System;
namespace SinglyLinkedLists
{
    public class SinglyLinkedLists<T>
    {
        private Node<T> head;
        private Node<T> previous;
        private Node<T> current;
        private Node<T> tail;

        private int numberOfNodes = 0;

        public SinglyLinkedLists()
        {
            head = null;
            previous = null;
            current = null;
            tail = null;
        }

        public void PrintList(){
            Node<T> current = head;
            while (current != null){
                Console.WriteLine(current.data);
                current = current.next;
            }
        }

        public void AddLast(T data){
            Node<T> newNode = new Node<T>(data);
            if (tail == null){
                head = tail = newNode;
            }
            else{
                tail.next = newNode;
                tail = newNode;
            }
            numberOfNodes++;
        }

        public void AddLastTwo(T data){
            Node<T> newNode = new Node<T>(data);

            if (head == null){
                head = newNode;
            }
            else{
                current = head;
                while (current.next != null){
                    current = current.next;
                }
                current.next = newNode;
            }
            numberOfNodes++;
        }

        public void RemoveNode(T data){
            Node<T> nodeToRemove = new Node<T>(data);
            current = head;

            if(head.data.Equals(nodeToRemove.data)){
                current = head.next;
                head = current;
            }
            else{
                while (current != null){
                    if (current.data.Equals(nodeToRemove.data)) {
                        previous.next = current.next;
                        current = previous;
                    }
                    else{
                        previous = current;
                        current = current.next;
                    }
                }
            }
            numberOfNodes--;
        }

        public int ListSize(){
            return numberOfNodes;
        }

        public bool InList(T data){
            Node<T> nodeToLookFor = new Node<T>(data);
            Node<T> current = head;
            while (current != null){
                if (current.data.Equals(nodeToLookFor.data)){
                    return true;
                }
                current = current.next;
            }
            return false;
        }

    }
}

A few things that stuck out to me:

You don't gain anything by having the Node class public.  The user of your linked list should only need to be concerned about the data.

It seems very illogical to me to have the Node class printing the LinkedList.  This should more properly be only part of the LinkedList itself.  It would probably be advantageous though for the Node class to override the ToString() method to make it easier to print the data.

From a quick perusal, I couldn't see any use for the previous property except in the RemoveNode method.  I would suggest keeping it local to that method.

A comment explaining the purpose of the AddLastTwo method.  To me it appears to iterate over the list to find the last node, instead of using the last property of the class, like the AddLast.

To me names like AddLast and RemoveNode are over complicated.  If a node isn't being added to the end then it would be an insert operation not an add.  It shouldn't be necessary to tell the user that it's being added to the end.  Likewise the user doesn't need to know that the data is stored in a node, they are simply concerned with removing the data.

When you are using default get and set methods it's much easier to use the default syntax:

public Node<T> next{get;set;}


Creating default parameters for a TestResultDefinition I have a method which creates some default values in an ObservableCollection, nothing too fancy, but I'm trying to decide how to write the if statement.

private void CreateDefaultParameters()
    {
        //If there are no parameters, then create default ones.
        if (this.Parameters == null || this.Parameters.Count == 0)
        {
            this.Parameters = new ObservableCollection<TestResultDefinitionParameter>();

            this.Parameters.Add(new TestResultDefinitionParameter()
            {
                ParameterType = TestResultDefinitionParameter.ParameterTypes.Name
            });

            this.Parameters.Add(new TestResultDefinitionParameter()
            {
                ParameterType = TestResultDefinitionParameter.ParameterTypes.Axis,
                Value = "X"
            });

            //And so on.
        }
    }

The logic is essentially: If it's a new TestResultDefinition, then create default parameters, otherwise load the existing paramters from the database.

public TestResultDefinitionWithParameters(TestResultDefinition resultDefinition)
    {
        this.ResultDefinition = resultDefinition;

        //If it's a new result definition, create the default parameters.
        if (resultDefinition.ID == 0)
            CreateDefaultParameters();
        else
            RefreshParameters();
    }

The if statement could become very large, and I'm wondering if something like this would be better:

private void CreateDefaultParameters()
    {
        if (this.Parameters != null || this.Parameters.Count > 0)
            return;

        //Create parameters here

Would this help readability? Any suggestions?

if (this.Parameters == null || this.Parameters.Count == 0)

Is a check this complex actually necessary? It's hard to say for sure without seeing the rest of the class, but it seems like "Parameters is never null" is an invariant that the class could guarantee. For example by initializing to an empty collection in the constructor, making sure nothing else in the class sets it to null, and not exposing a public (or protected) setter so that nothing else can set it to null.

Doing this isn't always possible, but when it is, it does a good deal for reducing the potential of bugs and decreasing cognitive load by reducing the number of possible states you have to worry about the system being in.

As for your potential alternative- yes, it probably is better! In fact if you had ReSharper, it would recommend you did exactly that. It calls it "inverting if statement to reduce nesting".

This probably isn't a completely uncontroversial opinion though, so I'll try to sum up the pros and cons of each:

Pro inversion

Deeper nesting is generally harder to read
When reading into a nested if statement, you have to keep a "mental stack" of the conditions that each set of curly braces corresponds to. It has to be a stack so that you can readily "pop" off the last conditional once a set of curly braces ends. By contrast, when an if statement returns, you simply know that that condition is never true for the rest of the method, rather than having to be ready to jump between the true and false case. Cognitively this is much easier.

Anti-inversion

There's a style point that has lost popularity recently but some people still adhere to that a method should only have one exit point. I guess the reasoning is that having a single exit point corresponds to a single "path" through the code- even if conditionals mean that path can fork. There's some more analysis of this here.
Your conditional is probably slightly more likely to be a negative one if you do this. So instead of saying "if X then do Y", you're saying "if not X then don't do Y", which is mentally a bit harder to understand. The "don't do Y" part is unavoidable, but the "if not X" bit can be avoided by extraction of your conditional into a well-named method. For example:

private bool HasParameters()
{
    return this.Parameters != null && this.Parameters.Count > 0;
}

Some misc points:

You may have noticed HasParameters has slightly different logic than the line in your second snippet. That's because your one has a bug! In your case, a non-null but empty value for Parameters would have a value of true for this conditional, but it should have false.
Assuming you're using standard naming conventions, you shouldn't have anything method-scoped whose name starts with a capital letter. So no need to keep writing this.Parameters. Just Parameters would be equally unambiguous.


List directories, subdirectories and files, while ignoring some dirs In my application, the user may or may not want to ignore some directories. I can do that, but it seems like I am repeating myself. Does anyone have an idea to refactor that?

from os import walk, path
exclude = ['dir1/foo']
for root, dirs, files in walk('.', topdown=True):
    if exclude != None:
        dirs[:] = [d for d in dirs if d not in exclude]
        for name in files:
            for excluded in exclude:
                if excluded not in root:
                    print path.join(root, name)
    else:
        for name in files:
            print path.join(root, name)

exclude is None when there are no dirs to exclude. I thought of setting it to an empty list, but then, this loop for excluded in exclude: won't execute at all. My ambition was to avoid such a big if/else. Any ideas?

Example:

gsamaras@pc:~/mydir$ ls */*
dir1/bar:
test.txt

dir1/foo:
test.txt

dir2/bar:
test.txt

dir2/foo:
test.txt

I am getting:

./dir2/foo/test.txt
./dir2/bar/test.txt

./dir1/bar/test.txt

If I want, I can do an exclude = ['foo'], and then get:

./dir2/bar/test.txt
./dir1/bar/test.txt

meaning that I ignored all directories named "foo".

You are already modifiyin the list of directories, so that should be enough. But your exclude includes the full path, so your check in the list comprehension does not actually filter the excluded directories, you only do that in the for loop below when already having descended into those excluded directories (wasting time).

So, this should work:

from os import walk, path

exclude = {'./dir1/foo'}

for root, dirs, files in walk('.'):
    if exclude is not None:
        dirs[:] = [d for d in dirs if path.join(root, d) not in exclude]
    for name in files:
        print path.join(root, name)

Note that exclude needs to contain paths starting with the starting point of os.walk, so in this case ..

I also made exclude a set (\$\mathcal{O}(1)\$ in lookup), used the fact that topdown=True by default and used is not instead of != for comparison to None.

If you want to instead exclude folder names (regardless of their position in the directory tree), you can do that as well like this:

from os import walk, path

exclude = {'foo'}

for root, dirs, files in walk('.'):
    if exclude is not None:
        dirs[:] = [d for d in dirs if d not in exclude]
    for name in files:
        print path.join(root, name)

What is not possible with either of these two approaches is to include foo only in sub-directories of dir1, like in your example. However, I think this is more consistent behaviour, so you should choose one of the two, IMO.

As a last point, you should probably switch to Python 3 sooner rather than later if at all possible, because support for Python 2 will end in a bit more than a year (at the time of writing this).


"The broken pedometer" optimizations This is a solution to the problem: "The Broken Pedometer" on the UVA online judge. (Note: I can not use anything beyond what is in g++ 4.6 which is what is used for the competition I'm training for.)

Algorithmic approach (pretty simple, but fast enough, not needed to understand to comment on the code):

possible_led_removals recursively attempts to remove one integer from all the strings in leds while maintaining a unique array of strings (leds):
If removing an integer leads to duplicates in leds, return (base case)
Otherwise, return the maximum amount of possible removals (depth) at the same index from the strings in leds, while maintaining leds to be an array of unique strings (recursion)

My C++ is /very/ rough, and I mostly use C++ because of the STL. However, I'd like to improve my C++ to improve my contest performance, so any help, algorithmic as well as code-wise is much appreciated! Thanks!

#include<iostream>
#include<cstdlib>
#include<vector>
#include<sstream>
#include<algorithm>
using namespace std;

size_t n_leds, n_symbols;

bool any_duplicates(vector<string> &leds)
{
  for(size_t i = 0; i < (int)leds.size(); ++i)
    for(size_t j = i + 1; j < (int)leds.size(); ++j)
      if(leds[i] == leds[j]) return true;

  return false;
}

int possible_led_removals(size_t erase_index, vector<string> leds, size_t depth)
{
  for(vector<string>::iterator it = leds.begin(); it != leds.end(); ++it) {
    string::iterator string_it;
    string_it = (*it).begin() + erase_index;
    (*it).erase(string_it);
  }

  int max_depth = 0;

  if (any_duplicates(leds)) {
    return depth;
  } else {
    for(size_t i = 0; i < (int)leds[0].length(); ++i)
      max_depth = max(possible_led_removals(i, leds, depth + 1), max_depth);
  }

  return max_depth;
}

int main()
{
  size_t problems;
  cin >> problems;

  for(size_t i = 0; i < problems; ++i) {
    cin >> n_leds >> n_symbols;

    vector<string> symbols;

    for(size_t j = 0; j < n_symbols; j++) {
      ostringstream led;

      for(size_t k = 0; k < n_leds; k++) {
        bool on;
        cin >> on;
        led << on;
      }

      symbols.push_back(led.str());
    }

    int max_removals = 0;
    for(int i = 0; i < n_leds; ++i)
      max_removals = max(max_removals, possible_led_removals(i, symbols, 0));

    cout << n_leds - max_removals << endl;
  }

  return 0;
}

Just some hints to improve your C++ code if not the algorithm logic:

Use const references for passing big objects like vectors to functions. For example, replace vector<string> leds by const vector<string>& leds in any_duplicates. Otherwise, it will perform a full copy of the vector and its elements. Here, const reference is right since the vector is not modified.
You could add std::ios_base::sync_with_stdio(false); at the beginning of your code. Default thing for streams is to call C functions from cstdio. Putting that line allow streams not to use those functions and then to be faster.
For readability, you could replace (*it).stuff by it->stuff everywhere.
vector::size() returns a size_t and that's what you use in your loops. No need to cast the result to an int.
I may be wrong, but I don't see any functions from cstdlib used here. You could get rid of that header.

You could also probably improve readability and performance by using features from C++11 (usable with the option -std=c++0x with gcc). I don't know if your contest allows it or not.


PHP DAO classes inherit from a generic DAO classes and only change the table name I am building a web app that needs to access various tables in a given MySQL db.  To do that, I have created a generic class, see DAO_DBRecord.php below, and I create children classes for each table I want to access, e.g., DAO_User.php is used to access the users table.  The only difference in the children classes is that I change the value of the variable which contains the name of the table I wish to access.

My questions are:
1 - Should I make the DAO_DBRecord.php class abstract?  I'm not planning to instantiate it, and in fact as it is written I cannot access any table with it.
2 - Should I use constants in the DAO_DBRecord.php class (e.g., const USER_TABLENAME = 'users';  const ARTICLE_TABLENAME = 'articles';) and reference them in the children classes (e.g., private Stable = USER_TABLENAME;)?
3 - Anything else I should do?

Class_DB.php:

<?php
    class DB {
        private $dbHost;
        private $dbName;
        private $dbUser;
        private $dbPassword;

        function __construct($dbHost, $dbName, $dbUser, $dbPassword) {
            $this->dbHost=$dbHost;
            $this->dbName=$dbName;
            $this->dbUser=$dbUser;
            $this->dbPassword=$dbPassword;
        }

        function createConnexion() {
            return new PDO("mysql:host=$this->dbHost;dbname=$this->dbName",
                        $this->dbUser, $this->dbPassword);
        }
    }
?>

DAO_DBRecord.php

<?php
    require_once('Class_DB.php');

    class DAO_DBrecord {
        private $dbh; // This is an instance of Class_DB to be injected in the functions.
        private $table=NULL;

        function __construct($dbh){
            $this->dbh=$dbh;
        }
        function dbConnect(){
            $dbConnection=$this->dbh->createConnexion();
            return $dbConnection;
        }
        function checkRecordExists($recordIdentifier, $tableColName){
            $dbConnection=$this->dbConnect();
            $query=$dbConnection->prepare("SELECT COUNT(*) FROM $table "
                . "WHERE $tableColName = :recordIdentifier");
            $query->bindParam(":recordIdentifier", $recordIdentifier);
            $query->execute();
            $result=$query->fetch(PDO::FETCH_ASSOC);
            if ($result["COUNT(*)"]>0){
                return true;
            } else return false;
        }
    }
?>

DAO_Users.php

<?php
    class DAO_User extends DAO_DBRecord {
        private $table='users';
    }
?>

If the only difference between subclasses of DAO_DBRecord is the table name I wouldn't use subclasses. I'd just pass the table name to to the constructor of DAO_DBRecord and use different instances for different tables.

If the only difference between subclasses of DAO_DBRecord is the table name I would pass the name of the table to the constructor of the parent class:

class UserDao extends DAO_DBRecord {

    public function __construct($db) {
        parent::__construct($db, 'users');
    }
}

Having different classes improves type safety. In Java you can't pass a UserDao to a method with an ArticleDao parameter(1), it does not compile. I don't know whether this kind of type safety exists in PHP or not, but it could be a good practice and could results more readable code.

(1) Of course except if UserDao is a subclass of ArticleDao

I don't feel that making DAO_DBRecord class abstract would make a big difference. If your clients wants to misuse the class they can create a dummy (non-abstract) subclass for that:

class AnyDao extends DAO_DBRecord {

    public function __construct($db, $tableName) {
        parent::__construct($db, $tableName);
    }
}

If you want to protect DAO_DBRecord from instantiation with unknown table names make its constructor private and create static factory functions for your tables inside the DAO_DBRecord:

class DAO_DBrecord {
        private $db;
        private $tableName;

        private function __construct($db, $tableName) {
            $this->db = $db;
            $this->tableName = $tableName;
        }

        public static function createUserDao($db) {
            return new DAO_DBrecord($db, 'users');
        }

        public static function createArticleDao($db) {
            return new DAO_DBrecord($db, 'articles');
        }
        ...
}

So, DAO_DBrecord cannot be used with other tables.

If you use your table names only once creating constants for them looks unnecessary in this case.


OOP refactoring technique I'm teaching myself Object Oriented Programming in JavaScript and I'm looking over this small P5 code of CodingTrain's No.78, which deals with flying particles in the canvas, as a material.
The full code is below:
// Daniel Shiffman
// http://codingtra.in

// Simple Particle System
// https://youtu.be/UcdigVaIYAk

const particles = [];

function setup() {
  createCanvas(600, 400);
}

function draw() {
  background(0);
  for (let i = 0; i < 5; i++) {
    let p = new Particle();
    particles.push(p);
  }
  for (let i = particles.length - 1; i >= 0; i--) {
    particles[i].update();
    particles[i].show();
    if (particles[i].finished()) {
      // remove this particle
      particles.splice(i, 1);
    }
  }
}

class Particle {

  constructor() {
    this.x = 300;
    this.y = 380;
    this.vx = random(-1, 1);
    this.vy = random(-5, -1);
    this.alpha = 255;
  }

  finished() {
    return this.alpha < 0;
  }

  update() {
    this.x += this.vx;
    this.y += this.vy;
    this.alpha -= 5;
  }

  show() {
    noStroke();
    //stroke(255);
    fill(255, this.alpha);
    ellipse(this.x, this.y, 16);
  }

}

Wanting to train my OOP skill, I'm trying to refactor this code into more sophisticated one in the OOP point of view. So I refactored it by adding Particles_Manipulation class and moving the process written in draw function into the Particles_Manipulation class as action method.
The code is below:
// Daniel Shiffman
// http://codingtra.in

// Simple Particle System
// https://youtu.be/UcdigVaIYAk

class Particle {

  constructor() {
    this.x = 300;
    this.y = 380;
    this.vx = random(-1, 1);
    this.vy = random(-5, -1);
    this.alpha = 255;
  }

  finished() {
    return this.alpha < 0;
  }

  update() {
    this.x += this.vx;
    this.y += this.vy;
    this.alpha -= 5;
  }

  show() {
    noStroke();
    //stroke(255);
    fill(255, this.alpha);
    ellipse(this.x, this.y, 16);
  }

}

class Particles_Manipulation{
  constructor(){
    this.particles = [];
  }

  push_particles(_n){
    for (let i = 0; i < _n; i++) {
      let p = new Particle();
      this.particles.push(p);
    }
  }

  action(){
    for (let i = this.particles.length - 1; i >= 0; i--) {
      this.particles[i].update();
      this.particles[i].show();
      if (this.particles[i].finished()) {
        // remove this particle
        this.particles.splice(i, 1);
      }
    }
  }
}

const my_Particles_Manipulation = new Particles_Manipulation();

function setup() {
  createCanvas(600, 400);
}

function draw() {
  background(0);
  my_Particles_Manipulation.push_particles(5);
  my_Particles_Manipulation.action();
}

Could you evaluate my refactoring is nice or not?

Magic numbers
Avoid magic numbers. Magic numbers are just numbers in your code that represent some abstract data value. The problem is that they are spreed within the code. To make changes to these values requires searching the code and often the same values are repeated making the task even more difficult.
Defining the magic numbers as named constants makes making changes very easy. See rewrite
Using native API's
P5 is great but using it to create such a simple rendering task is not worth the need to load a huge chunk of code to do what the native API will do quicker (No need for the P5's overhead)
Naming
There are a lot of problems with your naming style.
JS naming convention
The naming convention for JavaScript is to use lowerCamelCase for all names with the exception of objects created with the new token which uses UpperCamelCase (Static objects and object factories can also use UpperCamelCase). For constants you can use UPPER_SNAKE_CASE
_underscoredNames
Use underscore to avoid possible naming classes in systems where you have no control of names.
Using underscore should only ever be a very last option and should never be used if there is no need. Eg the argument _n in push_particles(_n) { should be pushParticles(n)
Avoid redundancy
It is easy to add too much to a name. Keep names short and use as few words as possible. Names are never created in isolation and like a natural language requires context to have meaning.
Eg

Particles_Manipulation is overkill when Particles is all that is needed

my_Particles_Manipulation Never use my (unless its instructional code) This name can just be particles, or smoke

push_particles (don't repeat names) What does this function do? "Adds particles". push becomes add. What does it add particles to? "The Particles object", thus particlescan be inferred. The nameaddis all that is needed. If you were adding monkeys then maybeaddMonkeys`

Avoid repeated long references
Avoid doing the same long reference path and array indexing by store the object reference in a variable.
      this.particles[i].update();
      this.particles[i].show();
      if (this.particles[i].finished()) {
        // remove this particle
        this.particles.splice(i, 1);
      }

Becomes
      const p = this.particles[i];
      p.update();
      p.show();
      if (p.finished()) {
          this.particles.splice(i, 1);
      }

Keep an eye on Logic
The render system reduces the particle alpha each step. You use the alpha value to check when to remove particles alpha < 0. However you reduce the alpha, then render, then remove. That means than once going every frame you are trying to render 5 invisible particles. Remove befor rendering.
JS and Memory
Javascript is a managed language. Meaning that it manages memory for you.
This is great in most cases but it comes with a serious performance hit in applications like particle systems where many small independent objects are frequently being created and destroyed .
Object pool
To avoid the memory management overhead we use object pools.
An object pool is just an array of objects that are not being used. When an object is no longer needed we remove it from the main array and put it in the pool. When a new object is needed we check the pool, if there are any object in the pool we use it rather than create a new one.
This means that the particle object will need a function that resets it.
See rewrite
Note you can also pool the particles in the one array by using a bubble iterator to avoid the expensive @MDN.JS.OBJ.Array.slice@. Dead particle bubble to one end of the array. This is even faster but makes the inner update loop a lot more complex. You would only do this if you where using 10K+ particles.
JavaScript OO design
Many believe that using class is how to write good OO JavaScript. Sorry to say it is not and is in fact the worst way to write OO JavaScript. The class syntax does not provide a good encapsulation model, its only plus is easy inheritance, which is kind of redundant in lieu of JavaScript's lose polymorphism
In this case factory functions (a function that creates Object AKA Object factory) is best suited. Because we use an object pool when need not even bother with assigning a prototytpe for particle functions.
Some advantages of factory functions

This eliminates the need to use this and new.

Lets you define private properties without the need to #hack names

Lets you create objects before the first execution pass has completed (move the init and setups to the top where it belongs)

Some disadvantages of factory functions

Requires a good understanding of closure and Scope both of which are a difficult subjects to get a good understanding of.

Does not work well with object prototypes.

Rewrite
The rewrite uses the CanvasRenderingContext2D API to avoid the overhead of P5, Some replacement functions are at the bottom.
Note that when defining constants it is always a good idea to include unit types, ranges, and or a description  as a comment

animate();
;(() => {
    const CANVAS_WIDTH = 600;       // in CSS pixels
    const CANVAS_HEIGHT = 400;
    const PARTICLE_SPREAD = 1;      // max x speed in canvas pixels
    const PARTICLE_POWER = 3;       // max y speed in canvas  pixels
    const PARTICLE_RADIUS = 12;     // max y speed in canvas pixels
    const MAX_PARTICLES = 1000;     // Approx max particle count
    const PARTICLES_RATE = 3;       // new particle per frame
    const SMOKE_PARTICLES_PATH = new Path2D;  // circle used to render particle
    const PARTICLE_COLOR = "#FFF";  // any valid CSS color value
    const START_ALPHA = 1;          // particle start alpha max
    const START_ALPHA_MIN = 0.5;    // particle start alpha

    // Rate particle alpha decays to match MAX_PARTICLES. The life time in seconds
    // can be calculates as  Math.ceil(1 / ALPHA_DECAY_SPEED) * 60
    const ALPHA_DECAY_SPEED = 1 / (MAX_PARTICLES / PARTICLES_RATE);

    SMOKE_PARTICLES_PATH.arc(0, 0, PARTICLE_RADIUS, 0, Math.PI * 2);
    const canvas = createCanvas(CANVAS_WIDTH, CANVAS_HEIGHT);
    const smoke = new Particles(canvas);
    animate.draw = function() {
        canvas.ctx.setTransform(1, 0, 0, 1, 0, 0);
        canvas.ctx.clearRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);
        smoke.add(PARTICLES_RATE);
        smoke.update();
    }

    function Particle() {
        var x, y, vx, vy, alpha;
        const PARTICLE = {
            init() {
                x = CANVAS_WIDTH / 2;
                y = CANVAS_HEIGHT;
                vx = random(-PARTICLE_SPREAD, PARTICLE_SPREAD);
                vy = random(-PARTICLE_POWER, -PARTICLE_POWER);
                alpha = random(START_ALPHA_MIN, START_ALPHA);
                return PARTICLE;
            },
            update() {
                x += vx;
                y += vy;
                alpha -= ALPHA_DECAY_SPEED;
                return alpha < 0;
            },
            draw(ctx) {
                ctx.globalAlpha = alpha;
                ctx.setTransform(1, 0, 0, 1, x, y);
                ctx.fill(SMOKE_PARTICLES_PATH);
            },
        };
        return Object.freeze(PARTICLE.init());
    }
    function Particles(canvas) {
        const particles = [];
        const pool = [];
        const ctx = canvas.ctx;
        return Object.freeze({
            add(n) {
                while (n-- > 0) {
                   pool.length ?
                        particles.push(pool.pop().init()) :
                        particles.push(Particle());
                }
            },
            update() {
                var i = 0;
                ctx.fillStyle = PARTICLE_COLOR;
                while (i < particles.length) {
                    const p = particles[i];
                    p.update() ?
                        pool.push(particles.splice(i--, 1)[0]) :
                        p.draw(ctx);
                    i++;
                }
            }
        });
    }
})();

// functions to replace P5
function createCanvas(width, height) {
    const canvas = Object.assign(document.createElement("canvas"), {width, height, className: "renderCanvas"});
    document.body.appendChild(canvas);
    canvas.ctx = canvas.getContext("2d");
    return canvas;
}
function random(min, max) { return Math.random() * (max - min) + min }

function animate() {
    animate.draw?.();
    requestAnimationFrame(animate);
}
.renderCanvas {
    background: black;
}


Determining if the movement of a robot is possible in a row A robot can move in one step from cell X to cell Y if and only if the distance between the centers of the cells X and Y measured in meters is equal to the sum of integers contained in X and Y. It then returns the index of the cell which the above condition does not meet which is the index only [0, 1, 4] and its value is [3, 1, 0].

How can I improve my code and reduce the time complexity?

def row_walk(matrix):

    result = []
    x = []
    y = []
    for i, r1 in enumerate(matrix):
        y.append(i)
        for j, r2 in enumerate(matrix):
            if r1+r2 == abs(i-j) and not j <= i:
                x.append((i, j))
    result.append((list({el for tup in x for el in tup})))

    z = []
    for t1 in y:
        if t1 not in result[0]:
            z.append(t1)
    return z

if __name__=="__main__":
    matrix = [3, 1, 3, 2, 0, 0]
    print(row_walk(matrix))

First, you are defining too many variables.  Instead of making a list of tuples and then converting it to a flattened list with a different name, you should make the list out of numbers in the first place.  It would also be better to use a set instead of a list.  Your if statement is a little odd.  not j <= i is the same as j > i, but harder to read.  If j must be greater than i, why does your first check include abs()?  Since j > i is an easier operation than the other check, it should come first.  That way, if it is False, the other check won't even be evaluated and the whole thing is more efficient.  You could also use a comprehension instead of a four-line for loop:

def row_walk(matrix):
    used = set()
    for i, r1 in enumerate(matrix):
        for j, r2 in enumerate(matrix):
            if j > i and r1+r2 == j-i:
                used.update((i, j))
    return [x for x in range(len(matrix)) if x not in used]

If you can use a set instead of a list, you can use a better return statement:

return used.symmetric_difference(range(len(matrix))

This all assumes that you are using Python 3.  If you are using Python 2, use xrange() instead of range().  Although range() still exists in Python 2, it creates a list instead of an iterator.


Quick Sort Implementation C++11 Here is qsort implementation using iterators as it is in std::sort

// iterator check
template <typename It, typename T>
constexpr bool is = std::is_same<std::iterator_traits<It>::iterator_category, T>::value;

// quick sort
template <typename BidIt, typename Pred>
void qsort(BidIt first, BidIt last, Pred compare) noexcept
{
    static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
        "bidirectional iterator required");

    auto size = std::distance(first, last);

    if (size > 1) {
        using content_type = std::iterator_traits<BidIt>::value_type;

        content_type pivot = *first;
        std::vector<content_type> left(size), right(size);
        auto left_end = left.begin();
        auto right_end = right.begin();

        for (BidIt i = std::next(first); i != last; ++i) {
            compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
        }

        qsort(left.begin(), left_end, compare);
        qsort(right.begin(), right_end, compare);

        std::copy(left.begin(), left_end, first);
        *std::next(first, std::distance(left.begin(), left_end)) = pivot;
        std::copy(right.begin(), right_end, std::next(first, std::distance(left.begin(), left_end) + 1));
    }
}

Your thoughts?

Advice 1

You can save some indentation space:

if (size > 1) {
    ... // Lots of code.
}

to

if (size < 2) {
    return;
}
... // Lots of code here.

Advice 2

You can do the partitioning in-place; there is no need for asking for more memory. The pseudocode in Wikipedia is rather detailed, uses no auxiliary memory (except for the recursion stack, of course) and is easy to follow.


DRYing out my Sass, looping through selectors Need help with DRYing out my Sass... there is just so much repetition in here:

.cta_foo {      @include linear-gradient(#f69c28,#b75d00,#b75d00); text-shadow: -1px -1px 0 #b85e00;
    &:hover {   @include linear-gradient(#FFAC41,#E77500,#E77500); } }
.cta_bar {      @include linear-gradient(#17b629,#0e831c,#0e831c); text-shadow: -1px -1px 0 #008A0F;
    &:hover {   @include linear-gradient(#25CF39,#179F27,#179F27); } }
.cta_baz {      @include linear-gradient(#67a9e4,#3a7ab2,#3a7ab2); text-shadow: -1px -1px 0 #4477a5;
    &:hover {   @include linear-gradient(#72B4EF,#448BCA,#448BCA); } }

I started out with an @each directive but just got confused quickly. I ask not just for this one instance but because I'm trying to wrap my head around maps and lists and loops and such.

Update

@mixin linear-gradient just generates a linear-gradient with fallback color:

@mixin linear-gradient($start,$end,$fallback) {
    background-color: $fallback; background-image: linear-gradient($start,$end);
    @include ms-filter($start,$end);
}

Well I finally figured out a way to do what I had in my mind:

@each $a, $b, $c, $d in (
    (foo,   (#f69c28,#b75d00,#b75d00), #b85e00, (#FFAC41,#E77500,#E77500)),
    (bar,   (#FFAC41,#E77500,#E77500), #008A0F, (#25CF39,#179F27,#179F27)),
    (baz,   (#67a9e4,#3a7ab2,#3a7ab2), #4477a5, (#72B4EF,#448BCA,#448BCA))
    ) {
    .foo_#{$a} {
        @include linear-gradient(nth($b,1),nth($b,2),nth($b,3)); text-shadow: -1px -1px 0 $c;
        &:hover { @include linear-gradient(nth($d,1),nth($d,2),nth($d,3)); }
    }
}

But really it doesn't look like it's any clearer (likely it's worse) and it only dropped from 493 characters to 420. I guess my intention, though, was just knowing HOW to do it. Perhaps this is one case where I don't need to be DRY if it makes the code harder to understand.


Sum of Look and Say Sequence I'm still learning c#, and I need my code to only run less than 2 seconds to be accepted.
I have a look and say sequence and after the last number is found, the code sums it all up, and it takes so long if the element in the sequence is big.

Example:

Input: 2

Output: takes less than a second

Input: 50

Output: takes 4 or so seconds.

I have only tried doing is changing foreach loops into for loops. I don't know what else to change.
Anyone can point me in the right direction? Thanks all.

namespace SumOfLookAndSaySequence
{
    class Program
    {

        static void Main(string[] args)
        {
            string input = Console.ReadLine();

            if (Int32.TryParse(input, out int nthTerm) && nthTerm > 0)
            {
                string lastSequence = GetSequence(nthTerm).Last();
                char[] digits = lastSequence.ToCharArray();
                int[] itemToSum = new int[digits.Length];
                int result = 0;
                for(int i = 0; i < digits.Length; i++)
                {
                    itemToSum[i] = int.Parse(digits[i].ToString());
                    result = result + itemToSum[i];
                }
                Console.WriteLine(lastSequence);
                Console.WriteLine(result);
            }

        }

        static IEnumerable<string> GetSequence(int nthTerm)
        {
            List<string> sequence = new List<string>() { "1" };

            for(int i = 1; i < nthTerm; i++)
            {
                sequence.Add(GetNextNumberSequence(sequence[i - 1]));
            }

            return sequence;
        }

        static string GetNextNumberSequence(string number)
        {
            StringBuilder stringBuilder = new StringBuilder();

            int count = 1;
            char digit = number[0];

            for(int i = 1; i < number.Length; i++)
            {
                if(number[i] == digit)
                {
                    count++;
                }
                else
                {
                    stringBuilder.Append(string.Concat(count, Char.GetNumericValue(digit)));

                    count = 1;
                    digit = number[i];
                }
            }

            stringBuilder.Append(string.Concat(count, digit));

            return stringBuilder.ToString();
        }
    }
}

I'd have to ask - do you have to Console.WriteLine() the output? Most code testing sites want a return value from a method rather than looking at the console output and clearly, the console output is going to be the vast majority of the time spent in the application.

Secondly, I have a few quick and easy tips for increasing performance:

Ditch the string.Concats - you have the StringBuilder in hand and can just
.Append() each of those items in turn:

stringBuilder.Append(count);
stringBuilder.Append(char.GetNumericValue(digit));

in the loop and

stringBuilder.Append(count);
stringBuilder.Append(digit);

after the loop.

Pre-allocate list size: List<string> sequence = new List<string>(nthTerm + 1) { "1" }; This will reduce reallocations as the list grows (it starts at 4 and then increases by twice the size as necessary).
Measure with precision - surround your processing code in Main with var SW = Stopwatch.StartNew(); and Console.WriteLine(sw.Elapsed);. This will show you the time your code actually took.

After I did these all the things listed above, 2 ran in 00:00:00.0006395 and 50 ran in 00:00:00.5806011.