Remove duplicate characters in a string This is a question from the book "Cracking the Coding Interview".

  Design an algorithm and write code to remove the duplicate characters
  in a string without using any additional buffer NOTE: One or two
  additional variables are fine An extra copy of the array is not

This is not the efficient code, but I want to preserve the order of characters after deleting duplicate characters.

#include <iostream>
#include <string>
#include <cctype> //std::toupper, std::tolower

void removeDuplicates(std::string& str)
{
    int flag = 0;
    int len = str.length();
    for (int i = 0; i < len - 1; ++i)
    {
        for (int j = i + 1; j < len - 1; ++j)
        {
            if (str[i] == std::toupper(str[j])
                || str[i] == std::tolower(str[j]))
            {
                str.erase(str.begin() + j);
                flag = 1;
            }
        }
    }
    if (flag == 0)
    {
        std::cout << "There are no duplicate characters\n";
    }
    else
    {
        std::cout << "There are duplicate characters\n";
    }
}

int main()
{
    std::string str;
    std::cout << "Enter String\n";
    std::getline(std::cin, str);
    removeDuplicates(str);
    std::cout << "New String\n";
    std::cout << str << '\n';
}

Help me optimize this code.

Clarify the requirement

You state 'remove duplicate characters' but then your code checks for upper and lower case matches - is the requirement to check for distinct letters, or distinct characters?

Sort out the bugs

I sense premature optimisation here, and it is the root of some evil:

int len = str.length();
for (int i = 0; i < len - 1; ++i)
{
    for (int j = i + 1; j < len - 1; ++j)
    {
        if (str[i] == std::toupper(str[j])
            || str[i] == std::tolower(str[j]))
        {
            str.erase(str.begin() + j);
            flag = 1;
        }
    }
}

What is the value of len? The length of the original string. And what is the value of len after we have erased a duplicate character? Still the same. So if we do find some duplicates, we will then happily run out of bounds in both loops. You can manually update len, or you could just call length() - it is constant complexity so you aren't rescanning the string each time. I would opt for comparing to length() until a profiler tells you otherwise.

Getting an idea of computational complexity

The complexity of the pair of loops is O(n2). But inside that, you do an erase - imagine we erase from the middle of the string (which is the average case); then we will need to copy about n/2 characters into the previous positions. This gives us O(n3).

There are things we can do to improve a bit - we can continue scanning for further duplicates before erasing, so that abccccccccd only required one copy, collecting all the duplicate c in one go.

Without preserving order, we can do O(n log n)

The easy way to improve the complexity is just to sort the characters in the string:

std::sort(str.begin(), str.end());

And then run through removing adjacent duplicates.

Is it possible to remove duplicates with O(n log n) (or better) complexity whilst maintaining order?

Consider the decision whether to elide some character halfway through the string. This character could be any of (assuming 1 byte chars) 256 values, so the bare minimum storage needed to make the decision is 256 bits. The requirements are not clear - 'one or two additional variables' could easily cover a 256 element std::bitset (should be 64 bytes), but could also not cover it if they are angling for a specific solution.

If we can keep that std::bitset, then we can mark each byte value that we've seen in the array and erase any contiguous blocks of duplicates we see. Marking a value in a fixed size array is constant time (O(1)), so the cost of detecting whether each character is a duplicate is still only O(n). But if we erase them each time we find them, we will end up in O(n2) land again, copying the last character in the string into successive locations.

Remove_if to the rescue

There is a way to remove all those duplicates without copying each later character more than once; imagine two position markers, one to the character we are assessing, and one to an earlier position at the end of the deduplicated string. If we copy each character directly into it's final position then the space left by duplicate characters will bubble to the end:

abcdeaafg_
    ^^
abcdeaafg_
    ^ ^
abcdefafg_
     ^ ^
abcdefgfg_
      ^ ^
abcdefg_

But instead of having to cope with all the details, we can call remove_if, which does just that job for us, at a cost of n calls to the predicate. The predicate (boolean test function) will look up the character value in the bitset:

static_assert((CHAR_MAX - CHAR_MIN <= 256), "Implementation requires 8 bit char");
std::bitset<256> seenChars;
auto newEnd = remove_if(str.begin(), str.end(),
   [&seenChars](auto & c) {    // capture seenChars so we can use it
       if(seenChars[c%256])   // have seen it before, so remove
           return true;
       seenChars[c%256] = true; // we have seen it now
       return false;             // but we won't remove this one
    });

(Edited this after replacing array with bitset)

To unpack that a little: we are removing any character for which the predicate returns true. The predicate simply checks whether the character has been seen (by casting the character to int and using it modulo 256 as the index into the bitset), and either returns true or marks this character value for next time and returns false. The [&seenChars] captures the bitset so that we can use it inside the predicate without having to pass it in; it forms part of the context of the function body.

The hardcoded 256 is not ideal, perhaps, although I wouldn't want to make it general to larger numbers (instead just failing a static_assert) because of the implication for storage.

remove_if itself returns an iterator to the new end position of the string; it has copied the latter values into the earlier positions, but not resized the string. We resize, then:

str.resize(std::distance(str.begin(), newEnd));

Et voila, we have removed duplicates, in place, with a space requirement of 256 bits and a time complexity of O(n). Not too shabby.

By the way, you can detect the removal of duplicates by comparing the original string length with the final string length. If they differ, duplicates were indeed found.


(Leetcode) K-similar strings in Python This is a Leetcode problem -

  Strings A and B are K-similar (for some non-negative integer
  K) if we can swap the positions of two letters in A exactly K
  times so that the resulting string equals B.

  Given two anagrams A and B, return the smallest K for which A
  and B are K-similar.

  Note -

  1 <= A.length == B.length <= 20
  A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

Here is my solution to this challenge -

import collections

class Solution:

    def find_first_mismatch(self, A, B):
        for i in range(len(A)):
            if A[i] != B[i]:
                return i

    def find_candidates(self, A, B, mismatch):
        for i in range(mismatch + 1, len(A)):
            if A[i] != B[i] and A[i] == B[mismatch]:
                yield Solution.swap(A, mismatch, i)

    def swap(A, i, j):
        chars = list(A)
        chars[i], chars[j] = chars[j], chars[i]
        return "".join(chars)

    def k_similarity(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        q = collections.deque([A])
        distance = 0
        seen = set([A])
        while q:
            for _ in range(len(q)):
                current = q.pop()
                if current == B:
                    return distance
                mismatch = self.find_first_mismatch(current, B)
                for candidate in self.find_candidates(current, B, mismatch):
                    if candidate not in seen:
                        seen.add(candidate)
                        q.appendleft(candidate)
            distance += 1

Here is my idea of how to solve the challenge -

The problem can be modeled as a graph problem of finding the shortest path between A and B where intermediate nodes are anagrams that can be formed by swapping 2 characters in a node having an edge to it. In other words, there is an edge between node X to node Y if Y can be formed by swapping 2 characters in X and vice-versa.

Here are some example outputs -

Example 1 -

Input: A = "ab", B = "ba"
Output: 1

Example 2 -

Input: A = "abc", B = "bca"
Output: 2

Example 3 -

Input: A = "abac", B = "baca"
Output: 2

Example 4 -

Input: A = "aabc", B = "abca"
Output: 2

Here is my Leetcode result (54 test cases) -

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Adding a few tests

Before performing any chance, it can be a good idea to add a few tests. This is especially relevant if we plan to perform optimisations as we'll be able to measure times. In that, case, it is also great when we are able to generate arbitrarily large inputs to infer the complexity of the solution (or at least be able to compare 2 solutions).

Here is what I wrote:

import time

start = time.time()
for i in range(2):
    # Examples provided
    assert Solution().kSimilarity("ab", "ba") == 1
    assert Solution().kSimilarity("abc", "bca") == 2
    assert Solution().kSimilarity("abac", "baca") == 2
    assert Solution().kSimilarity("aabc", "abca") == 2
    # Arbitrary examples
    assert Solution().kSimilarity("abcdefg", "gabdcef") == 5
    assert Solution().kSimilarity("abcbcdefg", "gcbabdcef") == 6
    # Big examples inspired from smaller ones
    n = 10
    assert Solution().kSimilarity("ab" * n, "ba" * n) == 1 * n
    assert Solution().kSimilarity("abc" * n, "bca" * n) == 2 * n
    assert Solution().kSimilarity("abac" * n, "baca" * n) == 2 * n
    assert Solution().kSimilarity("aabc" * n, "abca" * n) == 2 * n
    assert Solution().kSimilarity("abcdefg" * n, "gabdcef" * n) == 5 * n
print(time.time() - start)

Playing with the different values of n below, we can see that the Solution becomes very slow very quickly (I stopped at n = 4).

The timing suggest an exponential complexity.

Maybe there's something we can do about it with a different algorithm. We'll see this at the end but in the meantime, let's try to improve the already existing code.

Code review

The code looks good and uses great ideas that I've seen in other places.

A few details can be improved.

I'd call find_first_mismatch directly from find_candidates.

Actually, you could also merge the 2 functions to have a single loop and avoid messing with indices.

With a simple rewriting we get something equivalent which could be considered less elegant but is slightly faster:

def find_candidates(self, A, B):
    mismatch = None
    for i, (a, b) in enumerate(zip(A, B)):
        if a != b:
            if mismatch is None:
                mismatch = i
            elif a == B[mismatch]:
                yield Solution.swap(A, mismatch, i)

Another optimisation could be to avoid converting A to list many times by inlining the code for swap. This is not great as far as code organisation goes but...

def find_candidates(self, A, B):
    mismatch = None
    chars = list(A)
    for i, (a, b) in enumerate(zip(A, B)):
        if a != b:
            if mismatch is None:
                mismatch = i
            elif a == B[mismatch]:
                # Swap, yield and revert swap
                chars[i], chars[mismatch] = chars[mismatch], chars[i]
                yield "".join(chars)
                chars[i], chars[mismatch] = chars[mismatch], chars[i]

Renaming and reusing known values, we'd get:

def find_candidates(self, A, B):
    mismatch = None
    A_lst = list(A)
    for i, (a, b) in enumerate(zip(A, B)):
        if a != b:
            if mismatch is None:
                mismatch = i
            elif a == B[mismatch]:
                # Swap, yield and revert swap
                c = A_lst[mismatch]
                A_lst[i], A_lst[mismatch] = c, a
                yield "".join(A_lst)
                A_lst[i], A_lst[mismatch] = a, c

Instead of having q via different ways (len, pop, appendleft), we could just use list and iterate over it while filling another list that will be used at next iteration. We'd get something like:

    q = [A]
    distance = 0
    seen = set([A])
    while q:
        new_q = []
        for current in q:
            if current == B:
                # print("Return:", distance)
                return distance
            for candidate in self.find_candidates(current, B):
                if candidate not in seen:
                    seen.add(candidate)
                    new_q.append(candidate)
        q = new_q
        distance += 1

Instead of maintaining distance at each iteration, you could use itertools.count.

At this stage, the code looks like:

    def find_candidates(self, A, B):
        mismatch = None
        A_lst = list(A)
        for i, (a, b) in enumerate(zip(A, B)):
            if a != b:
                if mismatch is None:
                    mismatch = i
                elif a == B[mismatch]:
                    # Swap, yield and revert swap
                    c = A_lst[mismatch]
                    A_lst[i], A_lst[mismatch] = c, a
                    yield "".join(A_lst)
                    A_lst[i], A_lst[mismatch] = a, c

    def kSimilarity(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        # print("kSimilarity:", A, B)
        q = [A]
        seen = set([A])
        for distance in itertools.count():
            new_q = []
            for current in q:
                if current == B:
                    return distance
                for candidate in self.find_candidates(current, B):
                    if candidate not in seen:
                        seen.add(candidate)
                        new_q.append(candidate)
            q = new_q

Different algorithm

Generating so many intermediate strings is expensive and not so efficient.

An observation is that whenever we have elements so that: x1 should become x2, x2 should become x3, ..., xn should become x1, there is a trivial manipulation involving n - 1 swaps which put n elements in their correct position. It is easy to see that things can't get more efficient that this.

Now, the initial problem can be rewritten in a different problem where we want to find such cycles in our original strings.

This can be done by reorganising data from our strings into a graph and writing the proper loop to visit nodes to find cycles.

class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        # Building a graph where c1 -> c2 means we want to change c1 for c2
        # The problem becomes a graph problem: finding cycles
        changes = dict()
        for i, (c1, c2) in enumerate(zip(A, B)):
            if c1 != c2:
                changes.setdefault(c1, []).append(c2)
        ret = 0
        while changes:
            # Find cycle
            visited = []
            node = next(iter(changes))
            while node not in visited:
                visited.append(node)
                node = changes[node][0]
            # Cycle is found - starting from node
            beg = visited.index(node)
            loop = visited[beg:]
            # print("Loop:", loop)
            ret += len(loop) - 1
            # Remove corresponding elements
            for c1, c2 in zip(loop, loop[1:] + [loop[0]]):
                l = changes[c1]
                l.remove(c2)
                if not l:
                    del changes[c1]
        # print("Return:", ret)
        return ret

It seems like this behaves in a linear time or something that look similar enough.
I was able to run the tests above with n = 3000 in very small time.

Note: things are not as good as expected. Trying to run the code on the leetcode tool, a test case is not handled properly

assert Solution().kSimilarity("aabbccddee", "cdacbeebad") == 6  # Returns 7

I guess I based the algorithm on a wrong assumption. It seems like the cycles can't be chosen randomly as I assumed.

For instance, in that case, we should choose:

[bc] + [de] + [bad] + [cea] (with cost 6)

over combinations like

[acb] + [ade] + [cebd] (with cost 7) or
[acedb] + [ade] + [bc] (with cost 7)

At the end of the day, we want to maximise the number of cycles: the final cost will be number of characters in the wrong space - number of cycles.

I have no clue how to handle this...


Credit card checking I am practicing test-driven development in Python. Feedback about both the tests and the code is appreciated. I'm using luhn algorithm and regex to check credit card numbers for validity.

Here are the tests:

from unittest import TestCase
import luhn_check

class TestLuhnCheck(TestCase):

    def setUp(self):
        pass
    def test_known_sum(self):
        self.assertEquals(67, luhn_check.check_sum("7992739871"))

    def test_check_digit(self):
        self.assertEquals(3, luhn_check.find_check_digit("7992739871"))

    def test_check_valid(self):
        self.assertFalse(luhn_check.is_luhn_valid("abcdefg"))
        self.assertTrue(luhn_check.is_luhn_valid("79927398713"))

    def test_check_invalid(self):
        self.assertFalse(luhn_check.is_luhn_valid("79927398714"))

    def test_regex(self):
        self.assertTrue(luhn_check.check_regex("346340033233241"))
        self.assertFalse(luhn_check.check_regex("996340033233241"))

    def test_check_cc(self):
        #amex
        self.assertTrue(luhn_check.is_valid_cc("346340033233241"))
        #discover
        self.assertTrue(luhn_check.is_valid_cc("6011066253550425"))
        #visa
        self.assertTrue(luhn_check.is_valid_cc("4485332611430235"))
        #mc
        self.assertTrue(luhn_check.is_valid_cc("5463393720504875"))
        #bad:
        self.assertFalse(luhn_check.is_valid_cc("abcdefg"))
        self.assertFalse(luhn_check.is_valid_cc("11abcdefg"))
        self.assertFalse(luhn_check.is_valid_cc("946340033233241"))
        self.assertFalse(luhn_check.is_valid_cc("546339372050487500"))

and here is the module:

import re

def sum_digits(numeric_string):
    return sum([int(d) for d in numeric_string])

def valid_length_cc(cc_candidate):
    return len(cc_candidate) == 16 or len(cc_candidate) == 15

def check_sum(numeric_string):
    odds = numeric_string[:-1][::-2]
    evens = numeric_string[::-2]
    return sum([int(i) for i in odds]) + sum([sum_digits(str(int(i) * 2)) for i in evens])

def find_check_digit(numeric_string):
    return (check_sum(numeric_string) * 9) % 10

def is_luhn_valid(candidate):
    if candidate.isdigit():
        check_digit = int(candidate[-1:])
        return (check_sum(candidate[:-1]) + check_digit) % 10 == 0
    else:
        return False

def is_valid_cc(candidate):

    return check_regex(candidate) and valid_length_cc(candidate) and is_luhn_valid(candidate)

def check_regex(candidate):
    # are the digits correct?
    pattern = "^((4\d{3})|(5[1-5]\d{2})|(6011)|(7\d{3}))-?\d{4}-?\d{4}-?\d{4}|3[4,7]\d{13}$"
    r = re.compile(pattern)
    return bool(r.match(candidate))

Deprecation warning

This code works in both Python 2 and 3.  However, in Python 3, unittest.assertEquals() is deprecated in favour of .assertEqual(), so use .assertEqual() for better compatibility.

Length check

valid_length_cc would be better written as return 15 <= len(cc_candidate) <= 16.  It should also be moved further down, near the definition of is_valid_cc, since it has nothing to do with the Luhn algorithm code.

However, I recommend dispensing with the function altogether.  The expected length varies according to the card type.  You could just use the regex check to do the length validation for you.

Regex check

Your regex allows optional hyphens, but nowhere else in the code do you handle hyphens gracefully.

You incorrectly allow the second character of a card number that starts with 3 to be a comma.

Support for Discover cards appears to be incomplete.

The leading ^ anchor is redundant if you use re.match().

As previously mentioned, the regex should vary completely according to the card type.  I would therefore write it this way for clarity:

def check_regex(candidate):
    PATTERN = re.compile(r'(4(?:\d{12}|\d{15})'   # Visa
                         r'|5[1-5]\d{14}'         # Mastercard
                         r'|6011\d{12}'           # Discover (incomplete)
                         r'|7\d{15}'              # Petroleum and misc.
                         r'|3[47]\d{13}'          # American Express
                         r')$')
    return bool(PATTERN.match(candidate))

Luhn algorithm check

In my opinion, is_luhn_valid() would be better named check_luhn(), to be consistent with check_regex().

find_check_digit() would be better named compute_check_digit().  You'll never "find" the check digit by looking for it.  I'm not sure that it's a useful function to have at all, though, as is_luhn_valid() should be good enough.

Rather than slicing the string in is_luhn_valid(), I recommend feeding it intact to check_sum(), since it's really part of the same checksumming kind of operation.  For compatibility with your existing code, I've introduced an includes_check_digit mode to check_sum() that defaults to False.

For simplicity, the sum_digits() function could be replaced by a lookup table.

When calling sum(), you only need a generator expression, not a list comprehension.  You can therefore write sum(… for …) instead of sum([… for …]).

Suggested implementation

import re

def check_sum(numeric_string, includes_check_digit=False):
    if not includes_check_digit:
        numeric_string += '0'
    EVEN_VALUES = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
    evens = numeric_string[:-1][::-2]
    odds = numeric_string[::-2]
    return sum(int(i) for i in odds) + sum(EVEN_VALUES[int(i)] for i in evens)

def find_check_digit(numeric_string):
    return 9 * check_sum(numeric_string) % 10

def check_luhn(candidate):
    return candidate.isdigit() and check_sum(candidate, True) % 10 == 0

def check_regex(candidate):
    PATTERN = re.compile(r'(4(?:\d{12}|\d{15})'      # Visa
                         r'|5[1-5]\d{14}'            # Mastercard
                         r'|6011\d{12}'              # Discover (incomplete?)
                         r'|7\d{15}'                 # What's this?
                         r'|3[47]\d{13}'             # American Express
                         r')$')
    return bool(PATTERN.match(candidate))

def is_valid_cc(candidate):
    return check_regex(candidate) and check_luhn(candidate)


Turning relativenumber option off/on when opening/closing the gdb terminal window When I was not sure about how to do this, I asked this question on StackOverflow, the body of which is the following:

  As regards line numbers, when doing normal file editing, I prefer to
  have the following setting

set number
set relativenumber

  because the former tells me where I am, the latter helps me using
  j and k effectively.

  However, when debugging with
  gdb,
  using the termdebug package and the :Termdebug command, I often
  want to set breakpoints; hence, I'd like to turn the latter option
  off, executing the set norelativenumber command on a global scope,
  so that all files I'm editing show the actual line numbers.

Reading the answer, and Vim help pages a bit more, I ended up with the following solution, which is now part of my ~/.vimrc file:

" Source the termdebug plugin
packadd termdebug

" Add mapping to load termdebug
noremap <silent> <Leader>td :call MyTermdebug()<CR>

" turn off relativenumber,
" start Termdebug,
" and create autocmd to turn relativenumber back on
function! MyTermdebug()
  call SetRelNumInAllWin(v:false)
  augroup ClosingDebugger
    au!
    autocmd BufUnload !gdb call SetRelNumInAllWin(v:true)
  augroup END
  Termdebug
endfunction

" set/unset relativenumber in all windows if flag is v:true/v:false
function! SetRelNumInAllWin(flag)
  let current_win_id = win_getid()
  tabdo windo call SetRelNum(a:flag)
  call win_gotoid(current_win_id)
endfunction

" set/unset relativenumber in current window if flag is v:true/v:false
function! SetRelNum(flag)
  if &number
    if a:flag
      set relativenumber
    else
      set norelativenumber
    end
  end
endfunction

Two things off the top of my head:

Use mode-specific mappings, so nnoremap limits the mapping to normal mode. (Great job on the use of non-recursive mappings.)

You can access options as vimscript variables with &relativenumber. SetRelNum is sort of unecessary: I would have written

tabdo windo let &relativenumber = a:flag

(And if that doesn’t work because of some odd scope rule, you can exec it with everything but a:flag in quotes. You may have to pass 0/1 instead of v:false/v:true etc.)


Changing a character in a string at a specified index position Could you please tell me what you liked or may have disliked about this code? What can be made better?

#!/usr/bin/python3

def change_char_at(ch, s, indx):
    """
    Strings in Python are immutable objects. So, it is not possible to change a
    certain character in a string in place. For example, an attempt to run the
    following code will fail with a TypeError:

        s = "spam"
        s[1] = "z" # TypeError: 'str' object does not support item assignment

    What this function does is it provides you with a nice interface when you
    want to change a character in a string at a certain index position. So, use
    this function instead of doing everything manually which can sometimes be
    tricky. Notice that the character parameter does not necessarily have to be
    one character long. It can be an empty string which means that a character
    at a certain position will effectively be deleted from the string. If it's
    more than one character long, then they all will be inserted into the string
    starting at the specified index position.

    Parameters:
    ch:   character to insert
    s:    string to insert into
    indx: index position where to insert the character
    """
    # Error handling
    if type(ch) is not str:
        raise TypeError("first argument must be a string")
    if type(s) is not str or not len(s) > 0:
        raise TypeError("second argument must be a non-empty string")

    length = len(s) - 1
    if not(indx >= 0 and indx <= length):
        msg  = "string index out of range; "
        msg += "attempt to access index at {0}; ".format(indx)
        msg += "allowable index range 0 to {0}".format(length)
        raise IndexError(msg)

    # Actual function logic
    return s[:indx] + ch + s[indx + 1:]
    """
    Another possible implementation:

        ls       = list(s)
        ls[indx] = ch
        return ''.join(ls)

    This works well too and is equally good, but might be conspired unpythonic
    by some compared to the one right above it.
    """

def main():
    my_string = "spam"
    my_string = change_char_at("z", my_string, 1)
    print(my_string) # prints "szam"

if __name__ == "__main__": main()

The fact that your function is named change_char_at and the first parameter is named ch both suggest that ch should be a single character.  However, the function could easily be abused to splice in any number of characters at that location, including zero.  So, you might as well make it obvious and rename the function to string_splice() or something.

I'm not a fan of this function, though.  Basically, it's a long-winded way to do s[:indx] + ch + s[indx + 1:] with some validation.

if type(ch) is not str seems pointless.  If ch is not a string, it would naturally fail with a TypeError anyway during concatenation.
if type(s) is not str might be useful validation, but it also goes against Python's duck-typing philosophy.
if … not len(s) > 0 is an unjustified special case.  If you're going to allow splicing in an arbitrary number of characters, then why shouldn't one be allowed to add something to an empty string?  As a consequence of this failure case, the caller will also need to put in a special case to work around this restriction.
if not(indx >= 0 and indx <= length) is weird because length isn't actually the length of the string; it's one less than that.  It could be more succinctly written as if not 0 <= indx < len(s).  But Python's negative indexing is a feature, not a bug.  Why would you want to defeat the convenience?

In summary, if you want to do s[:indx] + ch + s[indx + 1:], then it's probably best to just write that.  If you want to write this function anyway, I recommend dropping most, if not all, of the validation.

If you want to do a lot of single-character replacements, then you would probably want to convert the string to a list or bytestring instead.


Project Euler 92: sum of squares of digits until a loop is encountered This is my solution to Project Euler #92:

  A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

  For example,

  44 → 32 → 13 → 10 → 1 → 1
  85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

  Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

  How many starting numbers below ten million will arrive at 89?

I was wondering how the code looks from a Pythonic perspective: is there anything that could be better? Cleaner? Is there anything that can be improved upon from a performance perspective?

from itertools import (
    islice,
    combinations_with_replacement,
    groupby
)
import operator

def get_digits(num):
    for c in str(num):
        yield int(c)

def sum_sq_digits(d):
    return sum(i*i for i in d)

def memoize(f):
    cache = {}
    def wrapped(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return wrapped

@memoize
def sum_sq_chain(num):
    if num in (1, 89):
        return num

    return sum_sq_chain(sum_sq_digits(get_digits(num)))

def fact(i):
    return reduce(operator.mul,
        xrange(1, i+1),
        1)

count = 0
for digits in islice(
        combinations_with_replacement(range(10), 7),
        1,
        None):

    if sum_sq_chain(sum_sq_digits(digits)) == 89:
        cur = fact(7)
        for _, v in groupby(digits):
            cur //= fact(len(list(v)))
        count += cur

print count

Prefer integer arithmetic

def get_digits(num):
    while n:
        yield n % 10
        n //= 10

Integer arithmetic is way faster than string convertion and manipulation, so this alternate version improves the efficiency of the code.

Give names appreciating the generality of your functions

sum_sq_digits works on any integer list. It works on any integer sequence, not just digits, but your name hints that it only works on a list of digits. I would rename it: sum_squared

Make a final function

I like that you wrote many small functions, it really helps readibility, I suggest going the last step and writing a function to solve the problem:

def chain_ending(limit, target)
   for digits in islice(
      combinations_with_replacement(range(10), limit),
      1,
      None):

      if sum_sq_chain(sum_sq_digits(digits)) == target:
          cur = fact(limit)
          for _, v in groupby(digits):
              cur //= fact(len(list(v)))
          yield curr

This way testing it is simpler and you may reuse it with different parameters. To get the final answer, just sum the generator this function yields.

Re-use

You will want to reuse as much as possible of your logic, to avoid duplicating work and possible errors.

The factorial function makes use of an in-place-defined product, I think that a separate product function will make code a little more English-like and will save you effort from re-writing it as getting the product of a sequence is a common task.

By the same point of view, using if __name__ == "__main__" allows you to import the script without running it, enabling re-use.

Comments for non-obvious algoritmhs

You do not use plain bruteforce to solve the problem, that is good, but you should leave a comment whenever you use a non-obvious algoritmh, or a link to an explanation of it.

Good

Overall this is good, clear, modular code.


Maze path finder using Depth-First Search algorithm I'm trying to resolve this kata from CodeWars.
Kata exercise

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return true if you can reach position [N-1, N-1] or false otherwise.
Empty positions are marked .. Walls are marked W. Start and exit positions are empty in all test cases.

I made a simple depth first search algorithm to solve the maze and check if there exists an exit.
But I noticed that my code is too slow and so it produces Execution Timed Out error.
I'm quite sure that changing this algorithm to an heuristic one could fix this, but I don't want to do that. I want to solve this using a Deep Search Algorithm. Is possible to improve the performance of this code?
I think the problem may be in the set, which don't have a pop method, so removing an item from them is quite difficult. But using an array would even require more time to check if the item already exists there.

function pathFinder(maze) {
  // Turn maze from string to nested array
  let chart = [];
  for (let c of maze.split("\n")) {
    chart.push([...c]);
  }

  let size = chart.length;

  // Make toVisit frontier
  let toVisit = new Set();
  toVisit.add([0, 0]);

  // Check if we already are in the exit
  let end = size - 1;
  // Size 1 maze
  if (end == 0)
    return true;

  while (toVisit.size > 0) {
    // Pop value from set
    let pos = toVisit.values().next().value;
    toVisit.delete(pos);

    let [x, y] = pos;
    chart[x][y] = "*"; // Mark as visited

    // Iterate over adjancets
    for ([x, y] of [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]) {
      // Check exit
      if (end == x && end == y)
        return true;
      // Check array out of boundary
      if (x < 0 || y < 0 || x >= size || y >= size)
        continue;
      // Check if wall or already visited
      let value = chart[x][y];
      if (value != "W" && value != "*")
        toVisit.add([x, y]);
    }
  }
  return false;
}

Set makes for a slow stack
Your use of a Set rather than a stack (array) is slowing everything down. The hashing function needed for Set to add delete and check items is expensive compared to pushing and popping from a stack.
JS does not like managing memory, allocations are expensive. If you use a stack you don't need to shrink it, rather just keep a pointer to the current stack position. That way if it shrinks below half its size it does not need relocation. You only get reallocation of the array each time it grows over double its size and never repeated.
Creating complex object, like arrays is far slower than creating primitive types. The for loop you use needs to create a new array for each position moved to. Every time you add to the toVisit set you create a new array. This all adds up.
Even creating the array chart populating it with characters from from the maze string is overly complex and can be avoided.
Example
The example avoids creating anything by basic types in the while loop. Avoids repeated calculations. Uses stackPos to track the size of the stack rather than push and pop from the stack. For quicker indexing the map is a flat array and coordinates are handled as triplets {x, y, idx}
I would guess its about 10 times faster (depending on the maze complexity) I did not have a maze to test it on so I hope it works :)
function pathFinder(maze) {
    const stack = [], rows = maze.split("\n");
    const size = rows.length, size2 = size * 2, exit = size - 1;
    const map = new Array(size * size);
    const checkMove = (x, y, idx) => {
        if (x === exit && y === exit) { return foundExit = true }
        if (x < 0 || x > exit || y < 0 || y > exit || rows[y][x] === "W") { return false }
        if (map[idx] === undefined) {
            map[idx] = 1;
            stack[stackPos++] = x;
            stack[stackPos++] = y;
        }
        return false;
    }
    var x, y, idx, stackPos = 0, foundExit = false;

    checkMove(0, 0, 0)
    while (stackPos) {
        y = stack[--stackPos];
        x = stack[--stackPos] + 1;  // add one to check next position
        idx = x + y * size;
        if (checkMove(x, y, idx)) { break }
        x -= 2;
        idx -= 2;
        if (checkMove(x++, y, idx++)) { break }
        y += 1;
        idx += size;
        if (checkMove(x, y, idx)) { break }
        if (checkMove(x, y - 2, idx - size2)) { break }
    }
    return foundExit;
}


Controller code with exception handling I am writing this code in the controller. I want to know is this the right way to write it or not. Because I don't want to write If else conditions and then either redirect or render the pages.

Here is my sample code :

def create
    @stud = Student.new params[:student]
    @stud.save!
    redirect_to students_path(@stud)
  rescue
    render 'new'
end

I know you wanted to avoid if / else, but I think i would probably write it like this:

def create
  @stud = Student.new params[:student]

  if @stud.save
    redirect_to @stud
  else
    render :action => :new
  end
end

Which is the same amount of code but has two advantages:

it is more readable by a human.  Rescue is not a human concept in logic, whereas if / else is clearly understood.
when you rescue here, you rescue from anything.  if @stud.save is specific, if that fails it won't throw an exception, but will return false.  So you are responding to the appropriate condition.

One other note: if you want to stick with the rescue pattern, you could shorten the function by a single line by writing

@stud = Student.create! params[:student]

which is the same as writing:

@stud = Student.new params[:student]
@stud.save!

ian.


Finding valid path on 2D Grid I got a 2D grid (n x n matrix). The user selects his player in this 2D grid and after that selects another node in this grid to mark his destination position. The player is allowed to move horizontally, vertically or if the player is standing in one of the 4 corners of this grid also diagonally. Also the player can only reach the selected destination if there are no other nodes in the grid blocking the way.

I need to know whether the player can reach the destination or not. To summarize the following needs to be solved:

  Input:

  Start (row: Int, column: Int)
  Destination (row: Int, column: Int)
  func isValidMove(from: Start, to: Destination) -> Bool

I have a working implementation however I am more than unhappy with the current state. I think there should be a way more declarative and mathematically correct way to achieve that.

This is what I came up with:

private func isValidHorizontal(move: GameMove, board: GameBoard) -> Bool {
    guard let start = move.start else { return false }
    guard start.row == move.end.row else { return false }

    var from: Int = start.column
    var to: Int = move.end.column + 1
    if start.column < move.end.column {
        from += 1
    } else {
        from = move.end.column
        to = start.column
    }

    for column in from..<to {
        if board.tileType(at: GameBoardPosition(row: start.row, column: column)) != .empty {
            return false
        }
    }
    return true
}

private func isValidVertical(move: GameMove, board: GameBoard) -> Bool {
    guard let start = move.start else { return false }
    guard start.column == move.end.column else { return false }

    var from: Int = start.row
    var to: Int = move.end.row + 1
    if start.row < move.end.row {
        from += 1
    } else {
        from = move.end.row
        to = start.row
    }

    for row in from..<to {
        if board.tileType(at: GameBoardPosition(row: row, column: start.column)) != .empty {
            return false
        }
    }

    return true
}

private func isValid(position: GameBoardPosition, on board: GameBoard) -> Bool {
    return position.row >= 0 && position.row <= board.rows - 1 && position.column >= 0 && position.column <= board.columns - 1
}

private func isValidDiagonal(move: GameMove, board: GameBoard) -> Bool {
    guard let start = move.start else { return false }
    var currentPosition = start

    var walkingIncrement: WalkingIncrement!
    if start.row == 0 && start.column == 0 {
        walkingIncrement = WalkingIncrement(dx: 1, dy: 1)
    } else if start.row == 0 && start.column == board.columns - 1 {
        walkingIncrement = WalkingIncrement(dx: -1, dy: 1)
    } else if start.row == board.rows - 1 && start.column == 0 {
        walkingIncrement = WalkingIncrement(dx: 1, dy: -1)
    } else if start.row == board.rows - 1 && start.column == board.columns - 1 {
        walkingIncrement = WalkingIncrement(dx: -1, dy: -1)
    } else {
        return false
    }

    currentPosition = currentPosition.walk(increment: walkingIncrement)
    while(isValid(position: currentPosition, on: board) && currentPosition != move.end) {
        if board.tileType(at: currentPosition) != .empty {
            return false
        }

        currentPosition = currentPosition.walk(increment: walkingIncrement)
    }

    return true
}

Do you have any advice for me to solve this more practical ?

As asked in the comments I provided a sample playground with a self contained example to better understand the problem and to get a compilable example:Playground Gist

At several places in your code the explicit type annotation is not
needed, for example

var from: Int = start.column
var to: Int = move.end.column + 1

can be simplified because the compiler infers the type automatically:

var from = start.column
var to = move.end.column + 1

Checking for empty fields along the move can be simplified if you iterate
over a stride(), that allows stepping both in increasing and decreasing
order. In func isValidHorizontal() that would be

let direction = (move.end.column - start.column).signum()
for column in stride(from: start.column + direction,
                     to: move.end.column,
                     by: direction) {
    if board.tileType(at: GameBoardPosition(row: start.row, column: column)) != .empty {
        return false
    }
}
return true

This can further be shortened to

return stride(from: start.column + direction,
                to: move.end.column,
                by: direction).allSatisfy {
    board.tileType(at: GameBoardPosition(row: start.row, column: $0)) == .empty
}

using the allSatisfy(_:)
method introduced in Swift 4.2.

This approach can be applied to the other methods as well.

In func isValidDiagonal() you can check if a destination position can
be reached before walking along the diagonal. For example, if the start position
is (0, 0) then an end position (x, y) can be reached only if x == y.

Further remarks:

You have defined the start property in GameMove as optional
(in contrast to the end property). Does it really make sense to specify
only the end position in a move? If not then make that property non-optional,
that would also make several guard statements like

guard let start = move.start else { return false }

obsolete.


Determining orthogonal polygons in a 3D integer lattice The last couple of days I've been trying to get a simple algorithm for uniquely determining orthogonal polygons in 3D integer space, having already determined coplanar points.
By the time we got here we know each point is unique and there are no collinear points.
For example, given the coplanar points pts (lists or tuples)
    pts = [
        [0, 0, 0], [4, 0, 0],
        [1, 1, 0], [2, 1, 0], [3, 1, 0], [4, 1, 0],
        [1, 2, 0], [2, 2, 0], [3, 2, 0], [4, 2, 0],
        [0, 3, 0], [4, 3, 0]
    ]

# Generate orthogonal polygons
# 3 +-----------+
#   |           |
# 2 |  +__+  +--+
#   |  |  |  |
# 1 |  +--+  +__+
#   |           |
# 0 +-----------+
#   0  1  2  3  4

#    result = [
#       [
#         [0, 0, 0], [0, 3, 0], [4, 3, 0], [4, 2, 0],
#         [3, 2, 0], [3, 1, 0], [4, 1, 0], [4, 0, 0]
#       ], [
#         [1, 1, 0], [1, 2, 0], [2, 2, 0], [2, 1, 0]
#       ]
#    ]

I found the basis of an algorithm for this in a paper as authored by Joseph O'Rourke
The following seems to work for the few tests I set up (however it doesn't deal with orientation).

def polygonise(pts: list) -> list:
    # axes gives us the varying columns (we can ignore z for this)
    axes = {i:set(c) for i,c in enumerate(zip(*pts)) if len(set(c))!=1}
    a, b = axes.keys()

    # construct dicts of axis-columns
    pts_by_axis = {axis: {col: [] for col in cols} for axis,cols in axes.items()}
    for pt in pts:
        for axis in axes:
            pts_by_axis[axis][pt[axis]].append(pt)

    # each axis-column (sorted by the other dimension)
    # will now be paired off into edges, and constructed into axis-edge-dicts
    edges = {}
    for axis in axes:
        other = a if axis != a else b
        for col,pt_list in pts_by_axis[axis].items():
            pt_list.sort(key=lambda p:p[other])
            for i in range(0,len(pt_list),2):
                v1 = tuple(pt_list[i])
                v2 = tuple(pt_list[i + 1])
                edges[tuple((axis,v1))] = other, v2
                edges[tuple((axis,v2))] = other, v1

    # now derive the polygons, starting at any point.
    axis, edge = next(iter(edges.keys()))
    result, poly = [], [edge]

    while edges:
        if (axis, edge) not in edges:
            # This polygon is now closed. keep it, and move to the next one.
            result.append(poly[:-1])  # if wanted looped, don't slice
            poly = []
            axis, edge = next(iter(edges.keys()))
        else:
            # Get the next edge. change the axis (edge is on a different axis)
            axis, new_edge = edges.pop((axis,edge))
            # delete any old reversed edge.
            del edges[(axis, edge)]
            edge = new_edge

        # add the edge to the existing polygon
        poly.append(edge)
    # capture the final polygon.
    result.append(poly[:-1]) # if wanted looped, don't slice.
    return result

if __name__ == "__main__":
    from mpl_toolkits.mplot3d.art3d import Poly3DCollection
    import matplotlib.pyplot as plt
    from random import shuffle
    pts = [
        (0, 0, 0), (4, 0, 0),
        (1, 1, 0), (2, 1, 0), (3, 1, 0), (4, 1, 0),
        (1, 2, 0), (2, 2, 0), (3, 2, 0), (4, 2, 0),
        (0, 3, 0), (4, 3, 0)
    ]
    # shuffle just to make it different.
    shuffle(pts)
    result = polygonise(pts)
    # all the below is just to show the result
    fig = plt.figure()
    subplot = fig.add_subplot(111, projection='3d')
    subplot.axis('off')
    subplot.scatter([0.6, 3.1], [0.7, 3.3], [0, 0], alpha=0.0)
    subplot.add_collection3d(Poly3DCollection(result, edgecolors='k', facecolors='b', linewidths=1, alpha=0.2))
    fig.tight_layout()
    plt.show()

I think that the loops could be easier, and I'm not convinced that I need to store edges twice, (which means I have to delete the unused one).
Any ideas for tidying the polygonise() method would be welcome.
J. O'Rourke, "Uniqueness of orthogonal connect-the-dots", Computational Morphology, G.T. Toussaint (editor), Elsevier Science Publishers, B.V.(North-Holland), 1988, 99-104. found here

Type Hints
+1 for using type hints.  But they could be a little more informative.
def polygonise(pts: list) -> list:
Ok.  The function takes a list of pts, but what are pts?  It returns a list, but a list of what?
from typing import Sequence

Point = Sequence[int]
Polygon = list[Point]

def polygonise(points: list[Point]) -> list[Polygon]:
    ...

Now we're giving the reader a lot of information.  A point is a sequence of integers.  Could be a tuple, could be a list.  Not important.  Instead of pts, we're a bit more explicit and say points.  Finally, the function returns a specific kind of list: a Polygon list.
You can help the reader out even more by including a nice """docstring""" for the function.
Axes
axes = {i:set(c) for i,c in enumerate(zip(*pts)) if len(set(c))!=1}
I really, really hate this statement.  It takes the list of points, and explodes each point as an argument for zip.  Then, it takes the first coordinate of each of those points, and returns it as a tuple.  enumerate adds an index to this, to keep track of which coordinate axis we are processing.  Then, we assign those to things to i, c ... really opaque variable names.  axis, coordinates might be clearer.  Then we turn the coordinates into a set, determine the len of the set, and if that is not 1, we turn the coordinates into a set again, for construction the dictionary.
Yikes!  That's a lot to unpack.
Then we take the axes, and assign it into to variables a and b, hoping there are exactly 2 axis.
Perhaps we should add some error checking.
    num_coord = len(points[0])
    if any(len(pt) != num_coord for pt in points):
        raise ValueError("All points should have the same number of coordinates")

    axes = ...

    if len(axes) != 2:
        raise ValueError("All coordinates must be in an orthogonal 2D plane")

    a, b = axes.keys()

That gives me a lot more confidence in the code.
I still don't like the axes = ... statement.  I would re-write it, and maybe use the walrus operator (:=) to avoid creating the set twice, but I'm about to significantly change it.
Useless code
edges[tuple((axis,v1))] = other, v2
Here, (axis, v1) is creating a tuple, to pass to the tuple(...) function.  That seems ... odd.  You could simplify it to:
edges[axis, v1] = other, v2
Alternate implementation
Axes
Instead of a dictionary, let's just extract a list of axis which have varying coordinate data.  A simple comparison of each coordinate of all points with the coordinate of the first point, for each coordinate, will tell us if that axis is important or not.
    axes = [axis for axis, first in enumerate(points[0])
            if any(pt[axis] != first for pt in points)]

    if len(axes) != 2:
        raise ValueError("All coordinates must be in an orthogonal 2D plane")

    a, b = axes

This is a much simpler concept.  No sets are being created (twice).  No dictionaries.
Sorted Edges
The pts_by_axis is very complex, a dictionary of dictionaries of arrays.
Let's rework this, by simply sorting the points list.  We'll sort it two ways, first by the (a, b) coordinate, then by the (b, a) coordinate.  We'll use a helper function to generate the sort keys:
def point_key(first: int, second: int):
    def key(pt):
        return pt[first], pt[second]
    return key

Now we can say sorted(points, key=point_key(a, b)), and we'll have the points sorted in one direction.  sorted(points, key=point_key(b, a)) will sort it in the other direction.
Since the points always come in pairs, to form edges, let's add another helper function, to extract pairs of points from the sorted array.
def in_pairs(iterable):
    it = iter(iterable)
    return zip(it, it)

With these, we can build our sorted edge structure.  But instead of keying the edges dictionary with a tuple to encoding the axis of the edge, let's just use two dictionaries:
    a_edge = {}
    for v1, v2 in in_pairs(sorted(points, key=point_key(a, b))):
        a_edge[v1] = v2
        a_edge[v2] = v1

    b_edge = {}
    for v1, v2 in in_pairs(sorted(points, key=point_key(b, a))):
        b_edge[v1] = v2
        b_edge[v2] = v1

The loop at the end does some check to close a polygon and start the next one.  Really, you have two loops.  Loop while there are still edges.  Inside that loop, loop until you've made a polygon.  With that structure, the code reads much better:
    result = []
    while a_edge:
        v1 = next(iter(a_edge.keys()))
        poly = []

        while v1 in a_edge:
            v2 = a_edge.pop(v1)
            v3 = b_edge.pop(v2)
            a_edge.pop(v2)
            b_edge.pop(v1)
            poly.extend((v1, v2))
            v1 = v3

        result.append(poly)

    return result

Note that I use poly = [] instead of poly = [v1], which means no slice is required at the end to remove the extra point.
Also, I'm popping v2 out of the a_edge dictionary, not a edge, since what is popped out is just a vertex.  I find that much clearer.


Bit compressing in JavaScript I have an bit array var data = []; ... and I have the following function:

jsPerf

function getBit(n) {
    return (data[~~(n / 32)] >> (n % 32)) & 1;
}

Because this is a bottleneck, I need the fastest cross-browser solution in my code, can anybody help make it any faster?

Also, ~~(n / 32) === Math.floor(n / 32)

It can be algorithm optimization or syntax optimization (such as asm.js) or something else.  Should I change the array type (typedArray or similar)?

I tried to speed up your formula :

return (data[n >> 5] >> (n & 31)) & 1;

.... All results are very close anyway : jsperf.com/fastest-bit-compressing/7.

• notice that you can inline the function by yourself (replace function call by direct computation).

• you might wan to cache latest array access by yourself during your computations.

• Or you might want to do the caching in the function. Efficiency will depends on the 'randomness' of your
use of the bits.

function getBit(n) {
    var itemIndex = n >> 5;
    if (itemIndex != lastItemIndex ) {
        lastItem = data[itemIndex];
        lastItemIndex = itemIndex ;
    }
    return lastItem >> (n & 31)) & 1;
}
var lastItemIndex = -1, lastItem = 0;


Takes a string array and searches for two words that are anagrams of each other Looking for some advice on whether or not this can be improved in terms of efficiency and speed, it would need to work on large data sets.

public class Anagrams {

    public static boolean isAnagram(String str1, String str2) {
    String s1 = str1.replaceAll("\\s", "");
    String s2 = str2.replaceAll("\\s", "");
    boolean status = true;
    if (s1.length() != s2.length()) {
        status = false;
    } else {
        char[] ArrayS1 = s1.toLowerCase().toCharArray();
        char[] ArrayS2 = s2.toLowerCase().toCharArray();
        Arrays.sort(ArrayS1);
        Arrays.sort(ArrayS2);
        status = Arrays.equals(ArrayS1, ArrayS2);
    }
    if (status) {
        return true;
    } else {
        return false;
    }
    }

    public static String searchAnagram(String[] array)
    {

        String anagramsList = "";
        Arrays.sort(array, (str1, str2) -> str1.length() - str2.length());
        for(int i=0;i<(array.length -1); i++)
        {
            int j=0;
            while(array[i].length() == array[i+j].length())
            {

                if(isAnagram(array[i],array[i+j]))
                {
                    anagramsList += (array[i] + " " + array[i+j] + ", ");
                    System.out.println(array[i] + " " + array[i+j] + ", ");
                }
                j++;
            }

        }
        if(anagramsList == "")
        {
            anagramsList = "No anagrams foud";
        }
        return anagramsList;
    }

}

In isAnagram one should start local variables with a small letter (just a convention).
Do not use if-else to return a boolean.

public static boolean isAnagram(String str1, String str2) {
    String s1 = str1.replaceAll("\\s", "");
    String s2 = str2.replaceAll("\\s", "");
    boolean status = true;
    if (s1.length() != s2.length()) {
        status = false;
    } else {
        char[] arrayS1 = s1.toLowerCase().toCharArray();
        char[] arrayS2 = s2.toLowerCase().toCharArray();
        Arrays.sort(arrayS1);
        Arrays.sort(arrayS2);
        status = Arrays.equals(arrayS1, arrayS2);
    }
    return status;
}

However if you think of an anagram as a form of sorted string, one could introduce either a type Anagram, or - here - a function deriving such a sorted string: here canonicalForm.

public static boolean isAnagram2(String str1, String str2) {
    return canonicalForm(str1).equals(canonicalForm(str2));
}

public static String canonicalForm(String s) {
    String cleaned = s.replaceAll("\\s", "");
    char[] chars = cleaned.toLowerCase().toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}

Most important searching for anagrams can use a map from canonical value to string(s).
For ease of mapping to the original algorithm. the mapped-to value is a concatenation of anagrams:

public static String searchAnagram(String[] strings) {
    Map<String, String> canonicalToValue = new HashMap<>();
    for (String s : strings) {
        s = s.replace('\t', ' '); // Omit tabs, reserve them for our usage.
        String canonical = canonicalForm(s);
        canonicalToValue.merge(canonical, s, (oldS, s) -> oldS + "\t" + s);
    }
    return canonicalToValue.values().stream()
            .filter(s -> s.contains('\t'))
            .collect(Collectors.joining(", "));
}

I use a tab (\t) as it seems that spaces might occur in strings.
One could also use a slash (" / ").

Better yet would be to return a List<String> of anagrams, and keep a List<String> or Set<String> as map value. A TreeSet<String> would remove duplicates and is sorted.

Instead of isAnagram one only needs canonicalForm (better anagramForm?).

The complexity is reduced in code complexity, faster.
Your attempt to optimize sorting on length is just a partial optimizing, needing extra checks / not fitting entirely. By using a HashMap on the canonical form of a string,
one has exactly an immediate search result.

The solution could give "malmodera malordema marmelado melodrama, gasometro gasometro somertago".

No result as String would better be an empty String. Again a List seems more usable.


Shortest and most efficient way for an endless image/content rotation in Vanilla JS and jQuery I wanted to create the most shortest JavaScript code for an endless rotation of elements, without any controls. The elements can be images or SVG-elements (only the Vanilla JS version will work here) or text-container. It doesn't matter. I came up with this:

HTML

CSS

.container > img {
    opacity: 0;
    position: absolute;
     -webkit-transition: all 1s linear;
    transition: all 1.5s linear;
}

.container > img.active {
    opacity: 1;
}

Vanilla JS

var e = document.getElementById('container');
if (e) {
    setInterval(function() {
        var current = container.getElementsByClassName('active')[0];
        current.classList.remove('active');
        var next = current.nextElementSibling || container.firstElementChild;
        next.classList.add('active');
    }, 2000);
}

Try it here

jQuery

var images = $('.container > img');

if (images.length) {
    setInterval(function() {
        var current = images.filter('.active');
        current.removeClass('active');
        var next = ( current.next().length ? current.next() : images.eq(0) );
        next.addClass('active');
    }, 2000);
}

Try it here

Is there anything that can be improved? I'm especially curious about the first line within each interval which involve a request (getElementsByClassName, Vanilla JS) or a loop (.filter, jQuery).

Eliminating functional differences between Vanilla JS and jQuery versions

Your vanilla script and your jQuery script are not functionally equivalent. Your vanilla is selecting the container by its ID, while the jQuery is selecting the container by its class and then selecting the images. Your vanilla script would more closely resemble the jQuery by using document.querySelector() and/or document.querySelectorAll().

e.g.: var images = document.querySelectorAll('.container > img');

Making it work for multiple containers

Your code will function strangely if more than one image rotator container is on the page: the jQuery will grab image elements from all the containers and only set one to active at a time, while the vanilla javascript will only change elements in the first container it grabs.

(EDIT: As you noted in the comments, you can work around this by selecting the different containers by ID before passing them to your function, but that approach requires manually specifying IDs both in the HTML and in the JavaScript. Ideally, you'd be able to just add more elements with the appropriate classes in the HTML to take advantage of the existing image rotator  functionality.)

With a little tweaking, you can ensure your code processes each container separately (allowing each container to have its own active image).

var containers = document.querySelectorAll('.container');
for (var i = 0; i < containers.length; i++) {
  beginRotation(containers[i]);
}
function beginRotation(container){
    setInterval(function() {
        var current = container.querySelector('.active');
        current.classList.remove('active');
        var next = current.nextElementSibling || container.firstElementChild;
        next.classList.add('active');
    }, 2000);
}

The above code first grabs all the elements with the container class, then sets the interval to run on each of them.

Minor nitpick(s)

You don't need that semicolon at the end of your if(e){ ... } statement in your vanilla js example.

Supporting older browsers (if you have to)

IE9 and below do not support classList, so if you want to support them you'll have to use the className property.

To remove a class, something like this would work:

current.className = current.className.replace("active", "").trim();

and its complement to add a class:

next.className = (next.className + " active").trim();

Note that this only really works because we know what to expect in the class names. This would break, for example, if you had an element with a class my-active-class because it would replace the substring active. A better (but more tedious) approach would be to split className into an array (using element.className.split(" ")) and check each array element for the desired class.

You'd also want to be aware that although IE9 supports CSS opacity, it doesn't support CSS transitions. The end result is that the images will transition promptly instead of fading in and out for IE9 users.

Working Example

var containers = document.querySelectorAll('.container');
for (var i = 0; i < containers.length; i++) {
  beginRotation(containers[i]);
}

function beginRotation(container) {
  setInterval(function() {
    var current = container.querySelector('.active');
    current.className = current.className.replace("active", "").trim();
    var next = current.nextElementSibling || container.firstElementChild;
    next.className = (next.className + " active").trim();
  }, 2000);
}
.container > img {
  opacity: 0;
  position: absolute;
  -webkit-transition: all 1s linear;
  transition: all 1.5s linear;
}
.container > img.active {
  opacity: 1;
}

&nbsp;

EDIT: Efficiency Suggestion(s)

Caching DOM Queries

You can make the code in setInterval more efficient by getting all the necessary DOM operations out of the way beforehand.

If you want to reduce the number of DOM queries (which are typically expensive operations) you can cache an array of references to all the relevant  elements and then reference that array in the setInterval function.

I know you're hoping for the "shortest and most efficient way", but this would be for efficiency at the expense of brevity, since you'd need to set up an extra variable to track the index of the active image. Using this index would save your code from having to read the current classLists of the images, requery the container element to get the active image, and traverse the DOM for the next sibling or first child.

var containers = document.querySelectorAll('.container');
for (var i = 0; i < containers.length; i++) {
    beginRotation(containers[i], containers[i].querySelectorAll('img'));
}
function beginRotation(container, imgs) {
    var i = getIndexOf(container.querySelector('.active'), imgs);
    setInterval(function () {
        imgs[i++].classList.remove('active');
        imgs[(i == imgs.length ? i = 0 : i)].classList.add('active');
    }, 2000);
}
function getIndexOf(target, arr) {
    var len = arr.length;
    while (len--) {
        if (target == arr[len]) {
            return len;
        }
    }
}


Conversion between enum and string in C++ class header I have the following redundant-feeling design to convert between enums and strings regarding a class that stores enums. The approach doesn't scale if there are more enums and in any event, less-redundant code is also better.

Questions

If there will be more enums, would it be possible to avoid defining two explicit conversion functions per enum type and device a system where the caller sees just one (i.e. convert) or two different function names (i.e. convertto/convertfrom for all the enums, not just per enum type)? Perhaps using some kind deduction magic with auto and decltype? It looks like ambiguity sets in since only the return value can be used to separate the different functions overloads (even if done with function templates).
Is the following design of separating the conversion functions and putting them to an anonymous namespace good design (I've thought about putting the conversion functions to a file, say conversions.incl and including it)?

The idea would be make the multiple (i.e. more enums than the one presented here) conversions as implicit as possible

The conversions would be used like this:

random.cpp

string token_string = "none"; //In reality this will be externally, user, generated.
some_class_instance->set_type(enum_conversion(token_string));
token_string = enum_conversion(some_class_instance->get_type());

And to present one enum and related conversions (but there could be more):

some_class.h

class some_class
{
    public:
         enum class enum_type
         {
             none   = 0,
             type1  = 1,
             type2  = 2
         }

     void set_type(enum_type);
     enum_type get_type() const;

   private:
       enum_type type_;
};

namespace
{
    std::array<std::pair<std::string, some_class::enume_type>, 3> type_map;

    bool initialize_map()
    {
       type_map[0] = std::make_pair("none", some_class::enum_type::none);
       type_map[1] = std::make_pair("type1", some_class::enum_type::type1);
       type_map[2] = std::make_pair("type2", some_class::enum_type::type2);
    }

    bool initialization_result = initialize_map();

    some_class::enum_type enum_conversion(std::string const& enum_type)
    {
        for(auto val: type_map)
        {
            if(val.first == enum_type)
            {
                return val.second;
            }
        }

        return type_map[0].second;
    }

    std::string enum_conversion(some_class::enum_type enum_type)
    {
        for(auto val: type_map)
        {
            if(val.second == enum_type)
            {
                return val.first;
            }
        }

        return type_parameter_map[0].first;
    }
}

I would use some template logic to achieve the affect in a more scalable way:

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

// This is the type that will hold all the strings.
// Each enumeration type will declare its own specialization.
// Any enum that does not have a specialization will generate a compiler error
// indicating that there is no definition of this variable (as there should be
// be no definition of a generic version).
template<typename T>
struct enumStrings
{
    static char const* data[];
};

// This is a utility type.
// Created automatically. Should not be used directly.
template<typename T>
struct enumRefHolder
{
    T& enumVal;
    enumRefHolder(T& enumVal): enumVal(enumVal) {}
};
template<typename T>
struct enumConstRefHolder
{
    T const& enumVal;
    enumConstRefHolder(T const& enumVal): enumVal(enumVal) {}
};

// The next two functions do the actual work of reading/writing an
// enum as a string.
template<typename T>
std::ostream& operator<<(std::ostream& str, enumConstRefHolder<T> const& data)
{
   return str << enumStrings<T>::data[data.enumVal];
}

template<typename T>
std::istream& operator>>(std::istream& str, enumRefHolder<T> const& data)
{
    std::string value;
    str >> value;

    // These two can be made easier to read in C++11
    // using std::begin() and std::end()
    //
    static auto begin  = std::begin(enumStrings<T>::data);
    static auto end    = std::end(enumStrings<T>::data);

    auto find   = std::find(begin, end, value);
    if (find != end)
    {
        data.enumVal = static_cast<T>(std::distance(begin, find));
    }
    return str;
}

// This is the public interface:
// use the ability of function to deduce their template type without
// being explicitly told to create the correct type of enumRefHolder<T>
template<typename T>
enumConstRefHolder<T>  enumToString(T const& e) {return enumConstRefHolder<T>(e);}

template<typename T>
enumRefHolder<T>       enumFromString(T& e)     {return enumRefHolder<T>(e);}

Then you can use it like this:

// Define Enum Like this
enum X {Hi, Lo};
// Then you just need to define their string values.
template<> char const* enumStrings<X>::data[] = {"Hi", "Lo"};

int main()
{
    X   a=Hi;

    std::cout << enumToString(a) << "\n";

    std::stringstream line("Lo");
    line >> enumFromString(a);

    std::cout << "A: " << a << " : " << enumToString(a) << "\n";
}


Configuration Handler I have below coded a class that loads information from a file that I select. The file then loads the content of that file in the INI format.

The INI format usually works when each line contains key=value and then each line is split by the  = character in the code. It also contains a method for getting the item by key from the dictionary of stored items previously loaded from the file. I wondered if anyone could help me out in finding any way to improve this?

I think its pretty well coded in my eyes, but of course there is always room for improvement.

namespace Hariak_Emulator.Emulator.Core.Config
{
    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    using NLog;
    using Utilities;

    internal sealed class ConfigManager : IDisposable
    {
        private static readonly ILogger Logger = LogManager.GetCurrentClassLogger();

        private Dictionary<string, string> _configItems;
        private string _configFile;

        public ConfigManager()
        {
            _configItems = new Dictionary<string, string>();
            _configFile = "assets/config/hariak_config.ini";

            LoadConfig();
        }

        private void LoadConfig()
        {
            try
            {
                if (!File.Exists(_configFile) || Utilities.IsFileLocked(new FileInfo(_configFile)))
                {
                    Logger.Error("Either your config file couldn't be found, or its open somewhere else.");

                    Console.ReadKey(true);
                    Environment.Exit(0);
                }

                _configItems = File.ReadLines(_configFile).Where(IsConfigurationLine).Select(line => line.Split('=')).ToDictionary(line => line[0], line => line[1]);
            }
            catch (Exception exception)
            {
                Logger.Fatal("Error while loading config: " + exception.Message);
                Logger.Fatal(exception.StackTrace);

                Console.ReadKey(true);
                Environment.Exit(0);
            }
        }

        private static bool IsConfigurationLine(string line)
        {
            return !line.StartsWith("#") && line.Contains("=");
        }

        internal string GetConfigValueByKey(string key)
        {
            string value;

            if (!_configItems.TryGetValue(key, out value))
            {
                Logger.Warn("Missing configuration key `" + key + "`");
            }

            return value;
        }

        public void Dispose()
        {
            if (!disposing)
            {
                return;
            }

            _configItems.Clear();
            _configItems = null;
            _configFile = "";
        }
    }
}

IMHO the code looks fine so far.

However, I see few improvements:

Class Design

The instance variables _configItems and _configFile should be readonly
There is no need to implement IDisposable because you don't reference resources that must be disposed.
It makes sense to pass the file as constructor argument to make the class reusable for any ini files.
Maybe it makes sense to provide also a constructor that receives a stream, so that the class can be used with embedded resource ini files and so on.
In method LoadConfig you could create the FileInfo object once and use it subsequently (File.Exists and IsFileLocked)

Behavior

The method IsConfigurationLine could be turned into a more tolerant version when trimming the line string before (to support comments where the '#' is not on the first position)
If the value contains also '=' characters, your method returns only the part between the '=' that separates the key and the value and the first occurring '=' in the value.
The class kills the application if loading the configuration file fails. That may be a valid behavior for your application, but it is nothing that should be decided by the method that loads the configuration code. IMHO a better approach is to throw the exception and let the calling code handle the behavior.
The key is case sensitive. I am not sure if that is desired, otherwise you can simply change that by defining the comparer when initializing the dictionary: _configItems = new Dictionary<string, string>(StringComparer.InvariantCultureIgnoreCase);


Select evenly spaced subset from array Say I have an array with 60 elements, and I want to select 40 elements from this array. The subset should consist of elements with evenly spaced indices. In theory I would need to select every 1.5th point, which is obviously not possible.

I tried doing it with a recursive function, kind of a divide & conquer approach. It selects the point in the middle between two boundaries and adds it to the result, then it splits this range up into two sub-ranges and executes the function again for these ranges:

Private Sub AddMiddlePoint(ByRef data() As Double, ByRef Result As List(Of Double), Lowerindex As Integer, Upperindex As Integer, MaxVals As Integer, MinSize As Integer)
    Dim middle As Integer = CInt((Upperindex + Lowerindex) / 2)
    Dim newBorderLower1 As Integer = Lowerindex
    Dim newBorderUpper1 As Integer = middle
    Dim newBorderLower2 As Integer = middle + 1
    Dim newBorderUpper2 As Integer = Upperindex
    If Result.Count < MaxVals Then
        Result.Add(data(middle))
        If newBorderUpper1 - newBorderLower1 > MinSize Then AddMiddlePoint(data, Result, newBorderLower1, newBorderUpper1, MaxVals, MinSize)
        If newBorderUpper2 - newBorderLower2 > MinSize Then AddMiddlePoint(data, Result, newBorderLower2, newBorderUpper2, MaxVals, MinSize)
    End If
End Sub

I call this function like this:

Private Function ThinOutData(source() As Double, Percentage As Integer) As Double()
    Dim newData As New List(Of Double)
    Dim amount As Integer = CInt(Percentage / 100 * source.Count)
    AddMiddlePoint(source, newData, 0, source.Count - 1, amount, CInt(Int(1 / Percentage) + 1))
    Return newData.ToArray
End Function

It basically works, but the subset that is selected isn't very evenly spaced. Some huge gaps, some small gaps and so on.

Does anyone have a suggestion how this can be improved? I am of course aware that you can't get perfectly even spacing for fractional steps, but my method returns uneven points even if it needs to pull every second or third value from the array.

My code is in VB.NET but feel free to use other languages that you are familiar with. It shouldn't be too hard to translate, I guess.

Your math was wrong, but don't worry it was a simple fix. And I have provided an easier way to do it on top of that.

The key to this review is that we're going to take advantage of the .Net libraries, which you should remember can practically do anything you want them to. That is IF you know how to use them.

in C#.Net

double percent = 40d / 60d;
var newValues = myList.Where((value, index) => index % (1 / percent) < percent).ToList();

in VB.Net

Dim percent As Double = 40.0 / 60.0
Dim newValues = myList.Where(Function(value, index) index Mod (1 / percent) < percent).ToList()

They are practically the same. But now let me explain how this works a bit now.

List<T> in .Net inherits from the IEnumerable<T> class which has the Where()  overloaded extension method from the Linq library. Using linq in combination with a lambda expression Function(value, index) index Mod (1 / percent) < percent I was able to specify to the Where method exactly what values to give back. I specifically did this with some math involving the index of the item that was being iterated over internally. Suffice to say, the Where method loops over given list, and returns all values which meet the criteria given in that lambda expression. At the end I convert the IEnumeral<double> to a List<double> to work like the data you had before.


Combining two clock tick vectors with NumPy I have two long (7683200 length) 1D arrays corresponding to two clock cycles, that I wish to combine into single 1D array. The clock_ticks_fine cycles between 0-255, and corresponds to a coarse division of 7.5 msec, with the reset to 0 signified by a 1 in the clock_ticks_coarse array.

I would like this to be much much faster (I have many of these files), but I can't work out how to vectorise the code. I don't care about the clock_ticks_fine value when clock_ticks_coarse is equal to 1.

First 100 datapoints in both arrays using a basic for loop:

corse_div = 7.5 # in msec
fine_div = 7.5/255.0

clock_ticks_fine = np.array([ 36,   1,  11,  22,  39,  66,  71,  78, 107, 121, 137, 142, 163,
       190, 211, 212, 239, 246,  36,   7,  13,  47,  56,  73,  78, 110,
       128, 143, 146, 175, 192, 203, 204, 239,  36,   0,  13,  19,  43,
        58,  74,  81, 111, 130, 139, 139, 175, 189, 208, 209, 238,  36,
         2,  19,  22,  39,  66,  76,  79, 101, 130, 145, 146, 163, 184,
       201, 214, 227, 255,  36,   9,  20,  45,  64,  75,  78, 103, 122,
       143, 144, 175, 184, 205, 208, 235, 250,  36,  14,  17,  46,  62,
        71,  72, 103, 119, 143, 144, 175, 186, 200])

clock_ticks_coarse = np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0])

count = -1
for i,boolean in enumerate(clock_ticks_coarse):
    if boolean == 1:
        count +=1
        clock_ticks_coarse[i] = count
    else:
        clock_ticks_coarse[i] = boolean+count

fine_time_array = clock_ticks_fine*fine_div
coarse_time_array = clock_ticks_coarse*corse_div
time_array = fine_time_array+coarse_time_array

np.set_printoptions(precision=3, suppress = True)
print time_array

Output:

[  1.059   0.029   0.324   0.647   1.147   1.941   2.088   2.294   3.147
   3.559   4.029   4.176   4.794   5.588   6.206   6.235   7.029   7.235
   8.559   7.706   7.882   8.882   9.147   9.647   9.794  10.735  11.265
  11.706  11.794  12.647  13.147  13.471  13.5    14.529  16.059  15.
  15.382  15.559  16.265  16.706  17.176  17.382  18.265  18.824  19.088
  19.088  20.147  20.559  21.118  21.147  22.     23.559  22.559  23.059
  23.147  23.647  24.441  24.735  24.824  25.471  26.324  26.765  26.794
  27.294  27.912  28.412  28.794  29.176  30.     31.059  30.265  30.588
  31.324  31.882  32.206  32.294  33.029  33.588  34.206  34.235  35.147
  35.412  36.029  36.118  36.912  37.353  38.559  37.912  38.     38.853
  39.324  39.588  39.618  40.529  41.     41.706  41.735  42.647  42.971
  43.382]

Everything apart from the for loop in your code is already vectorized which leaves only the for loop to be optimized.

You define a counter which is raised by 1 every time the entry of clock_ticks_coarse is 1. There exists a function cumsum in numpy which sums all entries of the argument like this:

import numpy as np

x = np.array([1,3,0,5,7])

np.cumsum(x)
# array([ 1,  4,  4,  9, 16])

It is a vectorized function, so it is very fast. Furthermore, it allows you to replace the for loop completely which should significantly boost the speed of your program. The if else condition can entirely be droped (if boolean is always zero in the else statement).

# This line replaces your whole for-loop and is vectorized
clock_ticks_coarse = np.cumsum(clock_ticks_coarse)-1

# the following lines are already vectorized, so they are fine
fine_time_array = clock_ticks_fine*fine_div
coarse_time_array = clock_ticks_coarse*corse_div
time_array = fine_time_array+coarse_time_array

np.set_printoptions(precision=3, suppress = True)
print time_array

# output

[  1.059   0.029   0.324   0.647   1.147   1.941   2.088   2.294   3.147
   3.559   4.029   4.176   4.794   5.588   6.206   6.235   7.029   7.235
   8.559   7.706   7.882   8.882   9.147   9.647   9.794  10.735  11.265
  11.706  11.794  12.647  13.147  13.471  13.5    14.529  16.059  15.
  15.382  15.559  16.265  16.706  17.176  17.382  18.265  18.824  19.088
  19.088  20.147  20.559  21.118  21.147  22.     23.559  22.559  23.059
  23.147  23.647  24.441  24.735  24.824  25.471  26.324  26.765  26.794
  27.294  27.912  28.412  28.794  29.176  30.     31.059  30.265  30.588
  31.324  31.882  32.206  32.294  33.029  33.588  34.206  34.235  35.147
  35.412  36.029  36.118  36.912  37.353  38.559  37.912  38.     38.853
  39.324  39.588  39.618  40.529  41.     41.706  41.735  42.647  42.971
  43.382]


Collecting data from different positions in a given array I'm writing a PHP function to collect data from different positions in a given array.  I've done it as follows which gives me what I require.

for ($a=9; $a < 13; $a++) {
     $n = $arr[$a][2];
     $p = $arr[$a][3];
     $c = $p;
     $v1[] = array($n,$p,$c);
}

for ($b=3; $b < 16; $b+=4) {
 $h = $arr[6][$b];
     $m = $arr[5][$b];
     $l = $arr[4][$b];
     $v2[] = array($h,$m,$l);
}

foreach ($v1 as $k=>$o) {
    $r[] = array( 'na'=> $o[0], 'pr'=> $o[1], 'cu' => $o[2], 'val1' => $v2[$k][0], 'val2' => $v2[$k][1], 'val3' => $v2[$k][2]);
}

To get the output in this format, without repeating the fields:

[0] = > Array
           [na] => Text
           [pr] => 1
           [cu] => Text
           [val1] => 1
           [val2] => 2
           [val3] => 3

[1] = > Array
           ....
           ....

[3] = > Array
           [na] => Text3
           [pr] => 1-3
           [cu] => Text-22
           [val1] => 101
           [val2] => 22
           [val3] => 34

Is there a better, more efficient way to do this?

Should work (at least it doesn't look like a riddle anymore:)

for ($i = 0; $i < 4; $i++) {
    $a = $i + 9;
    $b = 3 + $i * 4;

    $r[] = array(
        'na'   => $arr[$a][2],
        'pr'   => $arr[$a][3],
        'cu'   => $arr[$a][3],
        'val1' => $arr[6][$b],
        'val2' => $arr[5][$b],
        'val3' => $arr[4][$b]
    );
}

if $r[..]['cu'] is some function result assign to function call directly.


Subset sum simple iterative implementation Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem:

using System;
using System.Linq;

namespace Exercise
{
class SubsetSumBinaryNumber
{
    static void Main(string[] args)
    {
        int[] arr = { 2, 3, 1, -1 };
        PrintSet(arr, "Initial Set:");

        int wantedSum = 4;
        Console.WriteLine("Wanted sum = {0}", wantedSum);

        FindSubsetSum(arr, wantedSum);
    }
    //-----------------------------------------------------------------------
    /* Method: FindSubsetSum(int[] arr, int sum) */
    private static void FindSubsetSum(int[] arr, int targetSum)
    {
        // convert to base
        int toBase = 2;
        // length of binary number
        int length = arr.Length;
        // max value of binary number with "arr.Length" digits
        int iEnd = (int) Math.Pow(length, 2);

        for (int number = 0; number < iEnd; number++)
        {
            // convert current number to binary array
            bool[] binaryNumber = Enumerable.Range(1, length).Select(i => number / (1 << (length - i)) % 2 == 1).ToArray();

            // sum all elements with "true" indexes
            int currentSum = 0;
            for (int j = 0; j < binaryNumber.Length; j++)
            {
                if(binaryNumber[j] == true)
                {
                    currentSum += arr[j];
                }
            }

            // check for sum and print if equal
            if (currentSum == targetSum)
            {
                PrintSubSet(arr, binaryNumber);
            }
        }
    }
}
}

Input:

  -

Output:

  Initial Set.
                      {2 ,3 ,1 ,-1}
                      Wanted sum = 4
                      (1 ,3,)
                      (-1 ,3 ,2)

The algorithm is based on viewing all the combination of indexes of the initial set as a binary number (0's and 1's), then in order to go through all the combinations we simply increment through all the consecutive binary values from 0 to 2set cardinality and sum the set elements that match the 1's in the binary value, check the sum and print them if sum matches the wanted value.

Could the for loop be reduced in half if both current binary and its complement are checked simultaneously?

What is the complexity of this algorithm?

Any remarks regarding style and optimization will be appreciated.

Helper functions:

    /* Method: PrintSubSet(int[] arr, bool[] subSet) */
    private static void PrintSubSet(int[] arr, bool[] subSet)
    {
        Console.Write("(");
        for (int i = 0; i < arr.Length; i++)
        {
            if (subSet[i] == true)
            {
                Console.Write(arr[i]);

                if (i < arr.Length - 1)
                {
                    Console.Write(" ,");
                }
            }
        }
        Console.WriteLine(")");
    }
    //----------------------------------------------------------------------
    /* Method: PrintSet(int[] arr, string label = "") */
    private static void PrintSet(int[] arr, string label = "")
    {
        Console.WriteLine(label);

        Console.Write("{");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);

            if (i < arr.Length - 1)
            {
                Console.Write(" ,");
            }
        }
        Console.WriteLine("}");
    }

1. The most of the algorithms (that I could find) use recursion, dynamic programming and other fairly complex iterative approaches.

Again has \$O(n*2^n)\$ complexity

This program, like the recursive solution in the previous question, has \$O(n*2^n)\$ complexity.  It is simple to see that you iterate \$2^n\$ times, and on each iteration you compute the sum in \$O(n)\$ time.

Using Gray code to achieve \$O(2^n)\$ time

The key to reducing the run time of this iterative solution is to remove the \$O(n)\$ summation loop.  You can only do this if you can compute the next sum from the previous sum in \$O(1)\$ time.  Unfortunately, between one iteration and the next, up to \$n\$ numbers might need to be added/subtracted.  For example, if you were on this bit pattern:

0 1 1 1 1 = arr[0] + arr[1] + arr[2] + arr[3]

The next bit pattern would be:

1 0 0 0 0 = arr[4]

You would need to add one number and subtract 4 numbers to get from the previous sum to the next sum.  This is where the Gray code comes in to play.  The Gray code is a numerical sequence where each number in the sequence differs from the previous by only 1 bit.  So if you counted upwards using a Gray code sequence, then the next sum can be computed from the previous sum by only adding/subtracting one number.

Luckily, it is easy to count upwards in a Gray code sequence.  You can just count upwards in the normal way and then convert your normal number to the corresponding Gray code number using the formula:

grayCode = n ^ (n >> 1)

Then to find the bit that changed, you can xor the new gray number with the previous one:

bitChanged = oldGray ^ newGray;

One tricky part is that you need to know the bit number of the bit that changed.  Normally, I would do:

bitIndex = 31 - CLZ(bitChanged);

where CLZ() is a builtin "count leading zeros" function.  I couldn't find a builtin function in C# for that though, so I wrote my own.  There are fast versions of CLZ() that can be done in constant time using a lookup table, but I decided to use a looping version.  In the case of counting upwards using Gray numbers, bitChanged will be 0x1 50% of the time, 0x2 25% of the time, 0x4 12.5% of the time, etc.  Because of this, the looping variant will take amortized constant time since it operates faster on smaller bit numbers.

Sample Gray code implementation

I took your program and changed two functions: FindSubsetSum() and PrintSubset().  I also added my own clz() function.  Here is the modified parts of your code:

    private static void FindSubsetSum(int[] arr, int targetSum)
    {
        int length     = arr.Length;
        int iEnd       = 1 << length;
        int currentSum = 0;
        int oldGray    = 0;

        for (int i = 1; i < iEnd; i++)
        {
            int newGray    = i ^ (i >> 1);
            int bitChanged = oldGray ^ newGray;
            int bitNumber  = 31 - clz(bitChanged);

            if ((newGray & bitChanged) != 0)
            {
                // Bit turned to 1 = Add element.
                currentSum += arr[bitNumber];
            }
            else
            {
                // Bit turned to 0 = Subtract element.
                currentSum -= arr[bitNumber];
            }
            // Check for sum and print if equal
            if (currentSum == targetSum)
            {
                PrintSubSet(arr, newGray);
            }
            oldGray = newGray;
        }
    }

    private static void PrintSubSet(int[] arr, int bits)
    {
        Console.Write("(");
        for (int i = 0; i < arr.Length; i++)
        {
            if ((bits & (1 << i)) != 0)
            {
                Console.Write(arr[i]);

                if (i < arr.Length - 1)
                {
                    Console.Write(" ,");
                }
            }
        }
        Console.WriteLine(")");
    }

    // This can be replaced with a better variant, but this variant
    // will do the job for the Gray code sequence since the low
    // bit numbers will appear the vast majority of the time.
    private static int clz(int x)
    {
        int lz = 32;

        while (x != 0) {
            x >>= 1;
            lz--;
        }
        return lz;
    }


Optimize performance of flatten function in python I have to flatten a large number (>300k) dicts to write them to a csv file.

Example:

dict = {
    a: b,
    c: [
       {
           d:e
       },
       {
           f:g
       }
    ]
}

becomes:

a, c.0.d, c.1.f
b, e, g

The dicts can be really big with a lot of dicts as values.

My function to flatten them generically is:

def flatten(self, d, parent_key='', sep='.'):
        items = []
        for k, v in d.items():
            new_key = parent_key + sep + k if parent_key else k
            if isinstance(v, collections.MutableMapping):
                items.extend(self.flatten(v, new_key, sep=sep).items())
            elif isinstance(v, list):
                if isinstance(v[0], dict):
                    counter = 0
                    for entry in v:
                        new_count_key = new_key + sep + str(counter)
                        items.extend(self.flatten(entry, new_count_key, sep=sep).items())
                        counter += 1
                else:
                    items.append((new_key, v))
                    if new_key not in self.key_list:
                        self.key_list.append(new_key)
            else:
                items.append((new_key, v))
                if new_key not in self.key_list:
                    self.key_list.append(new_key)
        return dict(items)

When I meassure the time needed for exceution I found out the highest amount of time is caused by the instance checks. With 2500 dicts for example, the instance checks need around 6 seconds out of 12 seconds total.

Is there any way, I can speed up this function?

One avenue to try improve your speed is to use the Pythonic principle that it's Easier to Ask Forgiveness than beg Permission. This means that instead of testing your data every single time, you should just assume that it's in the correct form and catch the errors when you've gotten it wrong.

For instance, you test your dictionary here:

if isinstance(v[0], dict):
    counter = 0
    for entry in v:
        new_count_key = new_key + sep + str(counter)
        items.extend(self.flatten(entry, new_count_key, sep=sep).items())
        counter += 1
else:
    items.append((new_key, v))
    if new_key not in self.key_list:
        self.key_list.append(new_key)

What if instead you just assume that you have a list, and then work with the dictionary if you don't:

try:
    items.append((new_key, v))
    if new_key not in self.key_list:
        self.key_list.append(new_key)

except AttributeError:  # Is a dict, not a list
    counter = 0
    for entry in v:
        new_count_key = new_key + sep + str(counter)
        items.extend(self.flatten(entry, new_count_key, sep=sep).items())
        counter += 1

What you're doing here is attempting to append to items with the assumption that it's a list. If items is a dictionary and not a list, then your except catches the AttributeError that's raised and it will run the code for the dictionary format instead.

The advantage to this, is that you're not detecting the type, you're just catching when it's not a list. That means you spend no time calculating the datatype, you only need to spend time catching the exception when it comes up. This works best if the except catches the rarer datatype. So with my proposed solution, if most items will be lists then you'll save a lot more time than if most items end up being dictionaries.