Polishing partitions - Reimplementing a partitionOn So I've read an F# question on partitioning a list in F# and wondered whether I could cleanly write the concept down in haskell and if that would help me review the code ...

Now I have a haskell implementation of this "not-quite partition, not-quite group" and noticed it seems somewhat clumsy

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn pred list = go pred [] list
    where
        go :: ([a] -> Bool) -> [a] -> [a] -> [[a]]
        go _ working [] = [working]
        go pred working l@(x:xs) = if pred working
                then (working:(go pred [] l))
                else go pred (working++[x]) xs

A few questions:

The compiler gets very annoyed with me when I try to express the else-branch as a concatenation with : instead of ++. Would it be cleaner to use the following go?

go _ working [] = [reverse working]
go pred working l@(x:xs) = if pred working
    then ((reverse working):(go pred [] l))
    else go pred (x:working) xs

Am I missing a special case of groupBy here? It feels like there should be a simple standard function to do this

The code can be written cleaner if one removes the pred from go. go has access to all bindings in its context, including the ones in partitionOn pred list.

A first step to declutter partitionOn is therefore to get rid of duplication and get rid of unnecessary parentheses:

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn pred list = go pred [] list
    where
        go working [] = [working]
        go working l@(x:xs) = if pred working
                then working : go [] l
                else go (working ++ [x]) xs

Note that I've removed go's type signature. This is somewhat controversial, but the general rule-of-thumb is that you want type signatures at the top-level and usually leave the type-signatures at the not-top level, unless GHC gets confused.

The (small) problem with type signatures in where and let is that the type parameter a in parititionOn is not the same as the one in go. -XScopedTypeVariables is necessary for that. So lets get rid of that.

  Would it be cleaner to use the following go?

No. Or rather: it would be slightly cleaner, but pred also needs to work on the reversed list. This is more obvious if we don't use a position-independent predicate:

notInOrder []           = False
notInOrder (x:xs@(y:_)) = x > y || notInOrder xs

Your old version returns [1..10] on partitionOn notInOrder [1..10], but your new one returns [[1],[2],[3],…,[10]], unless you also check pred (reverse working).

Therefore—At least in the sense of asymptotic analysis—both variants will have the same performance.

  Am I missing a special case of groupBy here? It feels like there should be a simple standard function to do this.

The standard functions for splitting lists at some point are span, break, splitAt, take(While), drop(While(End)), group(By), inits and tails. They all are concerned with a single element in their predicate, so they are not candidates for our problem, unless we already have our splits:

splits :: [a] -> [([a],[a])]
splits xs = zip (inits xs) (tails xs)

That function does not exist, though. A perfect building block for partitionOn would have the type signature ([a] -> Bool) -> [a] -> ([a],[a]), but that's missing from the standard library. Others packages provide functions with that signature, but none does provide our needed functionality.

But we can write that function ourself:

breakAcc :: ([a] -> Bool) -> [a] -> ([a],[a])
breakAcc p = go []
  where
    go ys []     = if p ys then (ys,[]) else ([],ys)
    go ys (x:xs) = if p ys then (ys, xs)
                           else go (ys ++ [x]) xs

-- or, using `splits` above:

breakAcc p xs = case find (p . fst) (splits xs) of
                 Just ys -> ys
                 Nothing -> ([], xs)

Note that the first variant still has the somewhat awkward ++ [x] there. A partition that starts from the right wouldn't have that problem, but we're stuck with that.

Now partitionOn is just

-- feel free to use a worker wrapper approach here
partitionOn p xs = case spanAcc p xs of
              ([],bs) -> [bs]
              (as,bs) -> as : partitionOn p bs

Note that this will add the empty list at the end if our partition works for all elements, e.g. partitionOn ((0 <) . sum) [1..4] == [[1],[2],[3],[4],[]]. But that's easy to get rid of.

All at once:

import Data.List (inits, tails, find)

splits :: [a] -> [([a],[a])]
splits xs = zip (inits xs) (tails xs)

breakAcc :: ([a] -> Bool) -> [a] -> ([a],[a])
breakAcc p xs = case find (p . fst) (splits xs) of
                  Just ps -> ps
                  Nothing -> ([],xs)

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn p xs = case breakAcc p xs of
                     ([],bs) -> [bs]
                     (as,bs) -> as : partitionOn p bs

-- for QuickCheck
partitionOnResult_prop :: ([a] -> Bool) -> [[a]] -> Bool
partitionOnResult_prop p xs = all p (init xs)

partitionOn_prop :: ([a] -> Bool) -> [a] -> Bool
partitionOn_prop p xs = partitionOnResult_prop p (partitionOn p xs)

-- quickCheck $ \(Blind p) -> partitionOn_prop p

Now that we have all of this code, let's compare it again with your (almost) original variant:

partitionOn :: ([a] -> Bool) -> [a] -> [[a]]
partitionOn pred list = go pred [] list
    where
        go working [] = [working]
        go working l@(x:xs) = if pred working
                then working : go [] l
                else go (working ++ [x]) xs

If we quint our eyes, both codes look the same (if we use the first breakAcc variant). However, I wouldn't call a list l, since lists are usually identified with a suffix s called e.g. ls. Also, working is somewhat of a misnomer: are we working with that list? Or does that list fulfill some requirement? As we currently accumulate elements in there, the usual acc or accs might be better, but naming is hard and left as an exercise.

Other than that, unless you want to have little, test-able functions, your original variant was therefore fine to begin with, but contained some functions that can be re-used.


Subclassing `int` to make colors In the ROOT framework (originally a C++ framework, but python bindings are also supplied), colors are objects (ROOT.TColor) identified with an integer index.

This short class creates a new such color, given the r, g, b values which stores the object inside an int sub-type (to prevent the gc from deleting it).

#colors.py
import ROOT

class Color(int):
    """Create a new ROOT.TColor object with an associated index"""
    __slots__ = ["object"]

    def __new__(cls, r, g, b):
        """Constructor. r, g, b are in [0, 1]"""
        self = int.__new__(cls, ROOT.TColor.GetFreeColorIndex())
        cls.set_rgb(self, r, g, b)
        return self

    def set_rgb(self, r, g, b):
        self.object = ROOT.TColor(self, r, g, b)

black = Color(0, 0, 0)
orange = Color(0.9, 0.6, 0)
sky_blue = Color(0.35, 0.7, 0.9)
bluish_green = Color(0, 0.6, 0.5)
yellow = Color(0.95, 0.9, 0.25)
blue = Color(0, 0.45, 0.7)
vermillion = Color(0.8, 0.4, 0)
reddish_purple = Color(0.8, 0.6, 0.7)

colors = [black, orange, sky_blue, bluish_green,
          yellow, blue, vermillion, reddish_purple]

Usage example:

#draw_histograms.py
from colors import colors
import ROOT

names = "hist 1", "hist 2", "hist 3"
histograms = []
for name, color in zip(names, colors):
    hist = ROOT.TH1D(name, name, 100, -50, 50)
    hist.FillRandom("gaus", 1000)
    hist.SetLineColor(color)
    histograms.append(hist)

histograms[1].Draw()
...

I'm looking for comments on the class itself as well as recommendations regarding making the initialization of all the colors easier.

Further explanation:

The need for this class arose, because ROOT cannot convert a ROOT.TColor object directly to an int. It needs the global color index in functions such as hist.SetLineColor(1).

Otherwise it raises errors such as:

...
  File "test.py", line 43, in plot_2D_stacked
    h.SetLineColor(color)
TypeError: void TAttLine::SetLineColor(short lcolor) =>
    could not convert argument 1 (short int converion expects an integer object)

As suggested by @JoeWallis in the comments, you could use the "fast" TColor constructor. This let you simplify the color creation by not having to manually deal with the color number:

import ROOT

class Color(int):
    """Create a new ROOT.TColor object with an associated index"""
    __slots__ = ["object"]

    def __new__(cls, r, g, b, a=1.0):
        """Constructor. r, g, b and a are in [0, 1]"""
        # Explicitly use floats here to disambiguate
        # between the two TColor constructors
        color = ROOT.TColor(float(r), float(g), float(b), float(a))
        self = int.__new__(cls, color.GetNumber())
        self.object = color
        return self

Or you could use plain ROOT.TColor and use color.GetNumber() whenever you need an int instead of a TColor. An other, untested (and probably not working), would be to define an __int__ method:

class Color(ROOT.TColor):
    def __int__(self):
        return self.GetNumber()

If SetLineColor and others accept that, this would be the best alternative.

Depending on the need, it may also be a good idea to define properties to get/set color components, such as:

    @property
    def red(self):
        return self.GetRed()

    @red.setter
    def red(self, red_value):
        self.SetRGB(red_value, self.green, self.blue)

Change self to self.object if you use the int subclass.

Now, as regard to style, you define a bunch of constants whose names should be UPPER_SNAKE_CASE. And I would probably use red, green, blue and alpha instead of one letter variable names, even though in "color" context, these letters are pretty obvious.


A little next combination program in C++ An implementation of next combination function at Discrete Mathematics and Its Applications, Rosen p.438.

How it works:

Input:

The size n of a integer set {1, 2, ..., n}, which is where you choose objects from.
The size r of the subset of the integer set you currently have.
A pointer to the subset you currently have.

Output: The next subset in lexicographic order.

If you want to play around here is a link to ideone.com.

#include <iostream>
using std::cout;

// C(n, r) and provide the current subset a of size r.
bool nextCombination(int n, int r, int *a);
void printArray(int *a, int n);

int main() {
    int a[] = {1,2,3}; // So the current subset is {1,2,3} of size 3.
    int length = sizeof(a)/sizeof(*a);
    int count = 0;
    // The following example is C(7,3), start at {1,2,3}
    do {
        printArray(a, length);
        count++;
    } while (nextCombination(7, length, a));
    cout << "Total: " << count << '\n'; // Since we start from {1,2,3}, all C(7,3) subsets are generated and counted. The answer should be 7!/(3!4!)=35
    return 0;
}

bool nextCombination(int n, int r, int *a) {
    int lastNotEqualOffset = r-1;
    while (a[lastNotEqualOffset] == n-r+(lastNotEqualOffset+1)) {
        lastNotEqualOffset--;
    }
    if (lastNotEqualOffset < 0) {
        cout << "the end\n";
        return false;
    }
    a[lastNotEqualOffset]++;
    for (int i = lastNotEqualOffset+1; i<r; i++) {
        a[i] = a[lastNotEqualOffset]+(i-lastNotEqualOffset);
    }
    return true;
}

void printArray(int *a, int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << '\n';
}

The overview of its output:

1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 4
...
4 5 6
4 5 7
4 6 7
5 6 7
the end
Total: 35

using std::cout;, while better than including the entire namespace, is still worse than simply using the std:: prefix. If typing it annoys you too much, you can just make a macro in your editor to type it for you when you press a certain key combo.

Overall this looks much more like a C program than a C++ one. Assuming your algorithm works as intended you can take some steps to make this more C++ idiomatic?

Replace the array with a vector and get rid of raw pointers.
Enforce const when possible.
Drop return 0 from main because the compiler will generate it for you. This refers excplicitly to the return 0 at the end of main. Exiting from main by reaching the end automatically returns 0. So adding the return statement is just duplicate code.
Prefer prefix over postfix operator.
Move the logic into a class so you don't have to pass everything on every call to nextCombination.
You can overload operator<< to print the current line.
Eliminate magic numbers.

Keeping all this in mind, the rewrite could look something like this:

#include <iostream>
#include <iterator>
#include <vector>

class Combinatorics {
public:
    Combinatorics(std::vector<int> const& v, int const& n, int const& r)
        : elements{v}
        , n{n}
        , r{r}
    {}

    friend std::ostream& operator<<(std::ostream& os, Combinatorics const& obj);

    bool next() {
        int lastNotEqualOffset = r - 1;
        while (elements[lastNotEqualOffset] == n - r + (lastNotEqualOffset + 1)) {
            --lastNotEqualOffset;
        }
        if (lastNotEqualOffset < 0) {
            return false;
        }
        ++elements[lastNotEqualOffset];
        for (int i = lastNotEqualOffset + 1; i < r; ++i) {
            elements[i] = elements[lastNotEqualOffset] + (i - lastNotEqualOffset);
        }
        return true;
    }

private:
    std::vector<int> elements;
    int n;
    int r;
};

std::ostream& operator<<(std::ostream& os, Combinatorics const& obj) {
    std::copy(obj.elements.begin(), obj.elements.end(), std::ostream_iterator<int>(os, " "));
    return os;
}

int main() {
    constexpr int n = 7;
    constexpr int r = 3;
    int total = 0;
    Combinatorics combinatorics{{1, 2, 3}, n, r};
    do {
        std::cout << combinatorics << "\n";
        ++total;
    } while (combinatorics.next());
    std::cout << total << "\n";
}

You simply pass all your data into the constructor upfront and then call next until every repetition has been done. (I kept n and r because they are used in the math context, normally you should try to avoid short variable names like that).


Python Export Decorator In Python, we use __all__ to explicitly denote the public API of a module or package. That looks like this:

__all__ = ['Foo', 'bar', 'BAZ_CONSTANT']

BAZ_CONSTANT = None

class Foo:
    pass

def bar():
    pass

... except that modules can go on for thousands of lines, and then it is not immediately apparent, without revisiting the heading of the file, which objects are for external use, and which are not.

We are also required to write the names of the objects twice for each of these objects. (At a minimum. Even more for unittests - and we write our tests first, don't we?)

What I want is a decorator that allows me to shift the declaration of the public API away from the heading and to the object and constant definitions, where we, in most cases, can only write the name to be exported once.

Here's a serviceable preliminary draft, targeted to Python 3.6+ - perhaps the simplest thing that could possibly work:

import sys

class ExportError(Exception):
    """Exception if redundant names attempted exporting"""

def export(obj, global_namespace: dict=None) -> 'obj arg':
    """export adds names of functions and classes via decorator
    and module level variables via call (with globals() argument)
    to __all__.
    Usage:
    from exportlib import export

    export("BAZ_CONSTANT", globals()) # I don't like globals() call...
    BAZ_CONSTANT = None

    @export
    class Foo:
        pass

    @export
    def bar():
        pass
    """
    name = obj if isinstance(obj, str) else obj.__name__
    if global_namespace is None:
         try:
             global_namespace = obj.__globals__
         except AttributeError as error:
             raise AttributeError(
               f'no globals, try export({name!r}, globals())')
    __all__ = global_namespace.setdefault('__all__', [])
    if name in __all__: # Do we care if redundant exports? Assuming so:
        raise ExportError(f'{name} already exported')
    __all__.append(name)
    return obj

Ok, could probably be a little simpler with fewer features. I do like the documenting features of the annotations. I couldn't identify a more appropriate Exception to subclass or use directly than Exception.

I don't like the globals() call required when adding a module level variable that doesn't know its own name or module, but the only alternative, that I can think of, is to do what super does and climb a stackframe up and get the globals there, or pass in __all__ instead (which would require creating it explicitly). Stackframe climbing would preclude export from being wrapped/extended.

But I think this makes a sufficiently sophisticated starting point.

Personally, I'd prefer to use @export() or @export(globals()), rather than manually perform the @ sugar.
I don't like using __globals__, even if it is writeable.
Honestly, I think the cleanest solution would be to abuse lists, and use a closure.
I do however agree that inheriting from Exception, is the best parent to inherit from.

And so I'd personally use something more like:

class ExportError(Exception):
    """Exception if redundant names attempted exporting"""

def build_export(__all__=None):
    if __all__ is None:
        __all__ = []
    def export(obj):
        name = obj if isinstance(obj, str) else obj.__name__
        if name in __all__:
            raise ExportError(f'{name} already exported')
        __all__.append(name)
        return obj
    return __all__, export

__all__, export = build_export()

@export
class Foo:
    pass

@export
def bar():
    pass


Balanced parentheses Given an expression string exp, write a program to examine whether the
  pairs and the orders of

"{","}","(",")","[","]"

  are correct in exp.

  For example, the program should print true for

exp = "[()]{}{[()()]()}"

  and false for

exp = "[(])"

Complexity:

Time complexity: \$O(n)\$ where \$n\$ is length of string
Space complexity: \$O(\frac{n}{2})\$ where \$n\$ is length of string

I saw the Java version and thought "I want to submit a JavaScript version." Looking for code review, optimizations, and best practices.

In my version, the string can contain other characters than parentheses, "" is accepted as input, and I did not care about short circuiting odd length strings.

function parenthesesAreBalanced(s)
{
  var parentheses = "[]{}()",
    stack = [], //Parentheses stack
    i, //Index in the string
    c; //Character in the string

  for (i = 0; c = s[i++];)
  {
    var bracePosition = parentheses.indexOf(c),
      braceType;
    //~ is truthy for any number but -1
    if (!~bracePosition)
      continue;

    braceType = bracePosition % 2 ? 'closed' : 'open';

    if (braceType === 'closed')
    {
      //If there is no open parenthese at all, return false OR
      //if the opening parenthese does not match ( they should be neighbours )
      if (!stack.length || parentheses.indexOf(stack.pop()) != bracePosition - 1)
        return false;
    }
    else
    {
      stack.push(c);
    }
  }
  //If anything is left on the stack <- not balanced
  return !stack.length;
}

console.log('{}([]) true', parenthesesAreBalanced('{}([])'));
console.log('{{ false', parenthesesAreBalanced('{{'));
console.log('[(]) false', parenthesesAreBalanced('[(])'));
console.log("{}([]) true", parenthesesAreBalanced("{}([])"));
console.log("([}]) false", parenthesesAreBalanced("([}])"));
console.log("([]) true", parenthesesAreBalanced("([])"));
console.log("()[]{}[][]", parenthesesAreBalanced("()[]{}[][]"));

This is almost all style suggestions; the code itself looks great.

Personally, I prefer the brace-on-same-line style for everything in JS, and I prefer proper blocks instead of inlining expressions. But those are just preferences. I've also skipped the bitwise trick, added some strict comparisons instead of !stack.length etc., moved the i++ over to its "usual" place, and lengthened a few variable names, just for clarity.

Again: This is all basically pointless, but I just like spelling things out.

The only real difference is that rather than push the opening brace onto the stack, I push the position of the expected closing brace. It just makes the conditional a bit cleaner later on.

function parenthesesAreBalanced(string) {
  var parentheses = "[]{}()",
    stack = [],
    i, character, bracePosition;

  for(i = 0; character = string[i]; i++) {
    bracePosition = parentheses.indexOf(character);

    if(bracePosition === -1) {
      continue;
    }

    if(bracePosition % 2 === 0) {
      stack.push(bracePosition + 1); // push next expected brace position
    } else {
      if(stack.length === 0 || stack.pop() !== bracePosition) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Update: Actually, you can skip one stack.length check in the inner conditional; stack.pop() will just return undefined if the stack's empty, so this is enough:

if(stack.pop() !== bracePosition) {
  return false;
}


Which is a better implementation of a stack data structure (based on an array)? This is a version I made:

#include <stdio.h>
#include <stdbool.h>

#define MAX_STACK_SIZE 255

typedef struct
{
    int array[MAX_STACK_SIZE];
    unsigned int count;
    unsigned int max;
} Stack;

void initialize(Stack*);
void push(Stack*, int value);
int* pop(Stack*);
bool isEmpty(Stack*);
bool isFull(Stack*);

int main()
{
    Stack s1;
    initialize(&s1);
    for(int i = 0; i < 7; i++)
    {
        push(&s1, i);
    }
    pop(&s1);
    push(&s1, 88);
    push(&s1, 6);
    int *top;
    while((top = pop(&s1)) != NULL)
    {
        printf("Popping %d from the top of the stack.\n", *top);
    }
    return 0;
}

void initialize(Stack *p)
{
    p->count = 0;
    p->max = MAX_STACK_SIZE;
}

void push(Stack *p, int value)
{
    if(!isFull(p))
    {
        p->array[p->count] = value;
        p->count++;
    }
}

int* pop(Stack *p)
{
    if (!isEmpty(p))
    {
        p->count--;
        return p->array + p->count;
    }
    return NULL;
}

bool isEmpty(Stack *p)
{
    return p->count == 0;
}

bool isFull(Stack *p)
{
    return p->count == p->max;
}

This is a version of how it was done from the source I'm learning from:

#include <stdio.h>

#define MAX_STACK_SIZE 255
#define true 1
#define false 0
#define bool unsigned short int

struct stack
{
    int *topOfStack;
    int *pointer;
    int count;
    int max;
    int theStack[MAX_STACK_SIZE];
};

void initStack(struct stack *stackStruct)
{
    stackStruct->topOfStack = stackStruct->theStack;
    stackStruct->pointer = stackStruct->theStack;
    stackStruct->max = MAX_STACK_SIZE;
    stackStruct->count = 0;
}
bool pushStack(struct stack *stackStruct, int inputValue)
{
    if(stackStruct->count < stackStruct->max)
    {
        *stackStruct->pointer = inputValue;
        stackStruct->count++;
        stackStruct->pointer++;
        return true;
    }
    else
        return false;
}
int* popStack(struct stack *stackStruct)
{
    if(stackStruct->count > 0)
    {
        stackStruct->pointer--;
        stackStruct->count--;
        return stackStruct->pointer;
    }
    return NULL;
}

I think there's not so much of a difference between theb, but I just wanted to be sure.  In their version, they've used 2 additional pointers in their Stack struct and I removed them because I thought it was not necessary because we could use the array address + count to get the pointer address in their example.  I think they used it for convenience reasons.  More differences are that I included <stdbool.h> instead of using macros (not really important).

On top of that, I've implemented isEmpty() and isFull() methods just for convenience, but don't take it into account when comparing the two implementations since I'm sure they could do the same.  I just chose to show the 2 main functions that could be used on a stack.

Other than that, since it's an array-based implementation of a stack, I think it was possible to not include the max field in the struct since we define in a macro the stack maximum size, but I added it as well to my implementation for the heck of it.

Is there any differences between our implementations? Since I chose to do my own implementation I just want to make sure I that I did implemented it correctly and efficiently.

push() and pop() have an asymmetry that should be reconciled.  push() does not indicate any thing special when the stack is full and a push is attempted.  It silently does not do the push.  Yet when an pop of an emty stack occurs, a NULL is returned (versus a pointer to int) allowing the calling routine to take evasive action.  A symmetric solution would both do something special - or not - on full/empty.
A function to inspect the top of stack, without popping, could be added.  This IMO would be useful.  Additional routines to report current stack depth or stack space left are something to consider.
Using unsigned int is OK, especially if the fixed array size is known to always be less than UINT_MAX.  I favor size_t for array indexing as it has better portability for large arrays.
A way to deal with popping or inspecting an empty stack is, as part of initialize(), to pass an int as the bottom-of-stack.  This value does not actually ever get "popped off".
The names of the functions are too generic ("initialize") and could well collide with other code.  Suggest something like Stack_initialize(), and Stack_push().
The OO part of me wants to see a copy and destructor function too.  The destructor could simple do count = max = 0;


Code to calculate similarity between strings - R I have a large datafile with names and I want to create a similarity distance matrix. With this matrix I want to get similar names that could be the same person (or not) and that I could compare these rows and check whether more variables match or not.

However the code I have is quite slow. The dataframe has 58797 rows and some of them are repeated names. I was wondering for other options or a better way to get the information I'm looking for.

This is the code I have so far:

similar <- list()
for (i in 1:dim(data)[1]) {
    ids <- which(levenshteinSim(data$nomeAlt[i], data$nomeAlt) != 1 &
                 levenshteinSim(data$nomeAlt[i], data$nomeAlt) > 0.85)
    # ifelse only returns first element of list, instead use separate if else
    similar[[i]] <- if (length(ids) == 0) NA else ids
    print(i) # to get an update of the progress
}

Basically, the output returns rownames which I can get the names. In a working exemple I got names such as "ABEL MACEDO ALVES" and "ABEL MACHADO ALVES".

Any suggestion would be appreciated. Thank you!

Here is an implementation of the ideas I had suggested in the comments: to store the output of levenshteinSim so it is only called once, and to limit the expensive name comparisons to individuals that share the same initials. I hope it helps.

names_vec <- data$nomeAlt
initials  <- gsub("\\b(.).*?\\b", "\\1", x)

similar <- list()
for (i in 1:length(names_vec)) {
   ini <- initials == initials[i]
   sim <- levenshteinSim(names_vec[i], names_vec[ini])
   idx <- which(sim > 0.85 & sim != 1)
   similar[[i]] <- if (length(idx) == 0) NA else ini[idx]
   print(i) # to get an update of the progress
}


Drawing a grid-based particle system For some time now, I've been working on a game which is superficially similar in appearance to this one. A world is filled with particles that move and change state frequently (per frame, often). Drawing is achieved by finding the locations of particles within the camera's viewport, calculating lighting for the grid locations within the viewport, and then tinting a 1x1 white texture with the appropriate color, based on the particle and the lighting present in the particle's grid space:

public void drawParticles(ParticleBoard particle_board) {
    final int cam_min_x = camera.getCameraMinX();
    final int cam_min_y = camera.getCameraMinY();
    final int cam_max_x = camera.getCameraMaxX();
    final int cam_max_y = camera.getCameraMaxY();
    final float[][] light = light_manager.calculateLighting();

    for (int y = cam_min_y; y < cam_max_y; y++) {
        for (int x = cam_min_x; x < cam_max_x; x++) {
            final float l = light[x - cam_min_x][y - cam_min_y];
            if (l <= 0.05f) continue; // don't draw if it's too dark.

            final Particle p = particle_board.getParticle(x, y);

            if (p != null) {
                final Color c = p.getProperty().getColor();
                sprite_batch.setColor(new Color(c.r, c.g, c.b, l));
                sprite_batch.draw(texture, x, y);
            }
        }
    }
}

Light calculations are done within an array of floats the size of the current viewport. The approach is somewhat flood-fill-y, in that initial light values are placed at the 'top' of the array and then spread across the rest of the array, changing based on the presence of blocks:

float[][] calculateLighting() {
    final int cam_min_x = camera.getCameraMinX();
    final int cam_min_y = camera.getCameraMinY();
    final int cam_max_x = camera.getCameraMaxX();
    final int cam_max_y = camera.getCameraMaxY();
    final int light_width = cam_max_x - cam_min_x + 1;
    final int light_height = cam_max_y - cam_min_y + 1;
    final float[][] ambient_light = new float[light_width][light_height];

    for (int y = light_height - 1; y >= 0; y--) {
        for (int x = 0; x < light_width; x++) {
            final float max = getMaxNeighboringLight(ambient_light, x, y, light_width, light_height);

            if (particle_board.getParticle(x + cam_min_x, y + cam_min_y) != null) {
                ambient_light[x][y] = max * 0.75f; // TODO: add constant to particle properties for transparency -- use that here.
            } else {
                ambient_light[x][y] = max;
            }
        }
    }

    return ambient_light;
}

Here's how the max neighboring light level is found:

private float getMaxNeighboringLight(float[][] l, int x, int y, int light_width, int light_height) {
    float left = 0f, right = 0f, top = 0f, bottom = 0f;

    if (x == 0) {
        left = 0f;
    } else if (x == light_width - 1) {
        right = 0f;
    } else {
        left = l[x - 1][y];
        right = l[x + 1][y];
    }

    if (y == 0) {
        bottom = 0f;
    } else if (y == light_height - 1) {
        top = 1f;
    } else {
        bottom = l[x][y - 1];
        top = l[x][y + 1];
    }

    return Math.max(left, right, top, bottom);
}

Here's the result:

It would be very interesting to hear suggestions as to how these approaches to rendering and lighting calculations could be improved. It seems rather inefficient to create a new lighting array each frame, but I'm not sure how I could do much better, since many of the particles shift around frequently. Similarly, it seems that drawing could be improved, but I lack the knowledge to do so. If any clarification would be useful, please let me know. The approach used to draw particles is based in part on the responses that I got from this question.

From where I sit, this seems to be implemented backwards. You're iterating over every pixel in the viewport and checking to see if it has a particle, then doing something with the particle. It seems like it would be way more efficient to iterate over the particles and calculate the values needed for each particle. You're doing n * m operations for the lighting, then another n * m operations for drawing the textures (so it's essentially O(2n2)). You could do the operations only for the particles and cut it down to O(2q) operations (where q is the number of particles, which looks to always be smaller than m * n).

If instead, a particle held an (x,y) position, and a lighting value, you could simply iterate over the particles and calculate the new lighting value and then draw them.

You say:

  One of the difficulties with just doing the operations for all the particles is that the world is rather large. There are many more particles than those just displayed in the viewport. It would be prohibitively slow to calculate lighting and render every particle (> 10,000,000).

The solution to this is to use an appropriate data structure. In this case a k-d tree in 2D might be a good place to start. You would check only particles whose segment of the tree intersected the viewport, and leave out all other particles.


Reading in data from a file and then assigning vals and then creating object So I have some code which I created from the top of my head. But in all honesty I know it can't be the most efficient way of doing it.

I have some data in a file all positioned 5 values per line separated by commas (one line will be a specific object) dependent on the name of the item.

I know this can't be the best way of doing it as I have done the exact same code in java with less than half the lines.

PS: I started learning C++ this week, so don't be too hard on me!

Here is my code:

ifstream inFile;
inFile.open("inventory.txt");

// check for error
if(inFile.fail()){
    cerr << "Error opening file" << endl;
    exit(1);
}

InventoryLinkedList list;
string line;
int counter =0;
while(getline(inFile, line)){
    stringstream linestream(line);
    string value;
    int i = 0;
    string type;
    string code;
    int count;
    int price;
    string other;
    while(getline(linestream,value,',')){
        if(i==0){
            cout<< "Type " << value << endl;
            type = value;
        }
        else if(i==1){
            cout<< "Code " << value << endl;
            code = value;
        }
        else if (i==2){
            cout << "Count " << value << endl;
            count = atoi(value.c_str());
        }
        else if (i ==3){
            cout << "Price " << value << endl;
            price = atoi(value.c_str());
        }
        else if(i ==4){
            cout << "Other " << value << "\n"<< endl;
            other = value;
        }
        i++;
        if(i ==5){
            StockItem *t;
            if(type == "transistor"){
                t = new Transistor(code,count,price,other);
            }else if (type == "IC"){
                t = new IC(code,count,price,other);
            }else if (type == "resistor"){
                t = new Resistor(code,count,price,other);
            }else if (type == "capacitor"){
                t = new Capacitor(code,count,price,other);
            }else{
                t = new Diode(code,count,price,other);
            }
            list.tailAppend(t);
            //counter++;

        }
    }
}

Code Review

You don't check for failures in the read. When you read from a stream it can fail. All the read operations return a stream object as a result. This allows two things. 1) Chaining of read operations 2) Ability to check if it works. When you use a stream object in a boolean context it converts itself to bool that indicates its state. Thus each read operation can be tested to see if it works.

std::ifstream   data('mydata.txt');

int  value;
if (data >> value) {
    // The read worked.
}

std::string line;
while(std::getline(data, line)) {
    // Successfully read a line.
}

Each read operation should be checked to make sure it worked correctly.

int a,b;
if (data >> a >> b) {
    // Both a and b were read correctly.
}

You are not using operator>>. You get everything as a string then convert it. All the built in types have operator>> defined so you can simply read them (If the value read is not the correct type the stream is set bad and your code will automaically stop reading).

Also you can define operator>> fro user defined types so that you can use this simpler technique for nearly any object type (I provide an example below).

In modern C++ code you never see new/delete operations. That's because these return pointers and pointers have no ownership semantics. You should be using smart pointers so that ownership and thus lifetime are well defined.

std::unique_ptr<StockItem>  item(new Transistor(code,count,price,other));

Even better (if you have C++14/C++17)

std::unique_ptr<StockItem>  item  = std::make_unique<Transistor>(code,count,price,other);

How I would do it

Since operator>> for strings reads things that are space separated I would write a helper class for reading comma separated strings. Thus I can use read chaining to read all the things on a line in a single read operation.

struct CommaValueRef
{
    std::string& data;
    CommaValueRef(std::string& data) : data(data) {}
    friend std::istream& operator>>(std::istream& str, CommaValueRef& value) {return std::getline(str, value.data, ",");}
};

Since you are reading a file called "inventory.txt" I am going to assume that each line is a line of inventory. So I would define a class to hold the inventory and an operator>> that knows how to read a line of inventory.

class Inventory
{
    std::string type;
    std::string code;
    int         count;
    int         price;
    std::string other;

    friend std::istream& operator>>(std::istream& str, Inventory& value);
};

Now define the read like this:

    std::istream& operator>>(std::istream& str, Inventory& value)
    {
        std::string line;
        if (std::getline(str, line))
        {
            Inventory         tmp;
            std::stringstream linestream(line);

            char c1, c2;
            linestream >> CommaValueRef(tmp.type)
                       >> CommaValueRef(tmp.code)
                       >> tmp.count >> c1
                       >> tmp.price >> c2
                       >> CommaValueRef(tmp.other);

            // A lot of developers would have combined the above
            // line and this if statement into a single expression
            // I separated them as I though it looked neater.
            if (linestream && c1 == ',' && c2 == ',')
            {
                // All the read's worked so put the data
                // into the actual value.
                value = std::move(tmp);
            }
            else
            {
                 // Something failed to read correctly.
                 // So force the stream into a bad state
                 // So the controlling loop can generate a message
                 // and exit.
                 str.setstate(std::ios::failbit);
            }
        }
        return str;
    }

Now reading the file looks like this:

Inventory   data;
while(inFile >> data)
{
    list.push_back(StockItemFactory::createItemFromInventory(data));
}


Optimizing a distinction code List<int> types = new List<int>();
foreach (var d in myTableList)
{
    if (!types.Contains((int)d.item_type))
        types.Add((int)d.item_type);
}

I have a table in db called myTable. There is a column in it called item_type. It is integer.

I want to make a list which would have all item_type which are in myTableList, but there shouldn't be duplicates.

I tried:

types = myTableList.Distinct(x => x.item_type)

but I want types to be list of integers, not items of type myTable.

Try

types = myTableList
    .Select(x => (int)x.item_type)
    .Distinct();

You may also want to add .ToList() at the end if you want to match original code


One character diff - string comparison The question was:

  Create an algorithm to check if two strings differ by one character.

This wasn't my interview, so I tried to understand the question.

Options:

just compare the chars one by one, I assume the lower case and uppercase isn't the same.
compare the chars in any given order meaning "tube" and "bute" are the same...

Please be as strict as you can and find my bugs.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication2
{

    public class Program
    {
        public static void Main()
        {
            Console.WriteLine("Please Enter some text");
            string stringToCheck1 = "Out";
            string stringToCheck2 = "tuo";

            bool result = CompareStrings(stringToCheck1, stringToCheck2);
            PrintMessage(result);
            result = CompareAllLetters(stringToCheck1, stringToCheck2);
            PrintMessage(result);
        }
        public void PrintMessage(bool result)
        {
            if (result)
            {
                Console.WriteLine("Strings are less than one letter apart");
                return;
            }
            Console.WriteLine("Strings are more than one letter apart");
        }

        //checks if the letters one by one
        public static bool CompareStrings(string stringToCheck1, string stringToCheck2)
        {
            //check if strings are not the same size
            if (Math.Abs(stringToCheck2.Length - stringToCheck1.Length) > 2)
            {
                return false;
            }

            int counter = 0;
            for (int i = 0; i < stringToCheck1.Length; i++)
            {
                if (stringToCheck1[i] != stringToCheck2[i])
                {
                    counter++;
                }
            }
            if (counter > 1)
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        //checks if the letters in any order
        public static bool CompareAllLetters(string stringToCheck1, string stringToCheck2)
        {
            //check if strings are not the same size
            if (Math.Abs(stringToCheck2.Length - stringToCheck1.Length) > 2)
            {
                return false;
            }

            List<char> string1LettersList = new List<char>();
            List<char> string2LettersList = new List<char>();
            foreach (var c in stringToCheck1)
            {
                string1LettersList.Add(c);
            }

            foreach (var c in stringToCheck2)
            {
                string2LettersList.Add(c);
            }

            for (int i = 0; i < string1LettersList.Count; i++)
            {
                if (string2LettersList.Contains(string1LettersList[i]))
                {
                    string2LettersList.Remove(string1LettersList[i]);
                }
            }
            if (string2LettersList.Count > 2)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    }
}

Naming

CompareStrings() and CompareAllLetters are poorly named. You need a comment to explain what the methods should achieve.

The input parameters string stringToCheck1, string stringToCheck2 are also poorly named using some kind of hungarian style.

The input parameter of the PrintMessage() method is also poorly named. It is just not obvious what result should mean.

The same is true for the local variables string1LettersList and string2LettersList.

Comments

Comments should describe why something is done. The code should describe what is done.
This is especially true if the comment is plain wrong like //check if strings are not the same size. The check in question is not if they have a different size or not, it checks if the difference in length is greater than 2.

Simplifications

Use built in methods to simplify things.

Like this

List<char> string1LettersList = new List<char>();
foreach (var c in stringToCheck1)
{
    string1LettersList.Add(c);
}

can be simplified to

List<char> string1LettersList = stringToCheck1.ToList<char>();

returning booleans

Like already mentioned in vnp's answer you can simplify the returning of booleans. This is true for both of your methods.

The condition in the CompareStrings() method is obviously flawed. If both strings are equal, it  would return true, so better change it to

return (counter == 1);

exit early

You already do a check at the top of the methods (also it is done wrong), you can add another check for checking if both strings are the same.

In the CompareStrings() method you can exit early if before the incremention counter == 1 like

for (int i = 0; i < stringToCheck1.Length; i++)
{
    if (stringToCheck1[i] != stringToCheck2[i])
    {
        if (counter == 1) { return false; }
        counter++;
    }
}

Code duplication

In both methods you have the same (wrong) check about the size difference of the strings. You should extract this check to a separate method in which you also can integreate the check if both strings are the same.

private bool IsComparisonNeeded(String first, String second)
{
    if (first == second) { return false; }
    if (first == null || second == null) { return false; }

    return (Math.Abs(first.Length - second.Length) < 2);
}

Bugs

if strings are same, both methods returns true
if one or both of the strings is null the application crashes
if the difference in CompareAllLetters() is 2 it returns true

Refacoring

Can't be done right now, because

the code isn't producing the expected output
it is not clear for which input which output should be expected.

Suggestion

For a problem like this, you should first write tests defining the expected behaviour.


Find the largest sum of any slice inside an array This is the 26th exercise I solved from Codility. It scores 100%. I think I improved a lot since I started with this lessons, around 2 months ago, but still every post I made had things to be improved. What do you think about this code?

  Task description

  A non-empty array A consisting of N integers is
  given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a
  slice of array A. The sum of a slice (P, Q) is the total of A[P] +
  A[P+1] + ... + A[Q].

  Write a function:

  class Solution { public int solution(int[] A); }

  that, given an array A consisting of N integers, returns the maximum
  sum of any slice of A.

  For example, given array A such that:

  A[0] = 3  A[1] = 2  A[2] = -6 A[3] = 4  A[4] = 0 the function should
  return 5 because:

  (3, 4) is a slice of A that has sum 4, (2, 2) is a slice of A that has
  sum −6, (0, 1) is a slice of A that has sum 5, no other slice of A has
  sum greater than (0, 1). Write an efficient algorithm for the
  following assumptions:

  N is an integer within the range [1..1,000,000]; each element of array
  A is an integer within the range [−1,000,000..1,000,000]; the result
  will be an integer within the range [−2,147,483,648..2,147,483,647].

[PS: I'll upvote suggestions about sites that can help me get better at databases that follow a similar approach to codility]

using System;

class Solution {
    public int solution(int[] A) {
        var lastAddend = 0;
        var accumulator = 0 ;
        var maxSliceSum = A.Length > 0 ? A[0] : 0 ;
        foreach(var addend in A)
        {
            var maxLastPair = Math.Max(addend, lastAddend + addend);
            accumulator = maxLastPair > accumulator + addend ? maxLastPair : accumulator + addend;
            maxSliceSum = Math.Max(maxSliceSum, accumulator);
            lastAddend = addend;
        }
        return maxSliceSum;
    }
}

Two minor remarks:

For consistency sake, this

accumulator = maxLastPair > accumulator + addend ? maxLastPair : accumulator + addend;

can be implemented similar to the other statements as

accumulator = Math.Max(maxLastPair, accumulator + addend);

Some comments would be welcome in the loop. What exactly is the idea behind the different variables you keep. It took me a while to convince myself that your method was working as it should.


C++ performance: Linear regression in other way Here is the code that can be used for calculation of mathematical function, like ax^2 + bx + c.
It is fast enough if you choose small length, otherwise if programmer don't know the small range, that code can be really slow. I've made it specially on C++ to be more fast.
#include <iostream>
#include <vector>

using namespace std;

template<class var>
var Module(var x){
    if (x >= 0)
        return x;
    else
        return x*-1;
}

class Linear {
public:
    float resA, resB, resC;
    float err;

    float Predict(float a, float b, float c, float x) {
        return ((a * (x*x)) + (b*x) + c);
    }

    float Predict(float x) {
        return ((resA * (x * x)) + (resB * x) + resC);
    }

    float ErrorAv(float a, float b, float c, vector<float> input, vector<float> output) {
        float error = Module(Predict(a, b, c, input[0]) - output[0]);
        for (int i = 1; i < input.size(); i++)
            error = (Module(Predict(a, b, c, input[i]) - output[i]) + error)/2;
        return error;
    }

    void LinearRegr(vector<float> input, vector<float> output, float maximum, float minimum = 0, float step = 1) {
        if (step == 0)
            step++;
        float a, b, c;

        float lastError = INFINITY;
        for (a = minimum; a <= maximum; a += step)
            for (b = minimum; b <= maximum; b += step)
                for (c = minimum; c <= maximum; c += step) {
                    float error = ErrorAv(a, b, c, input, output);
                    if (error < lastError) {
                        lastError = error;
                        resA = a;
                        resB = b;
                        resC = c;
                        err = lastError;

                        if (!lastError)
                            return;
                    }
                }

    }
};

#include <ctime>
int main(){
    vector<float> input; //Input example.
    vector<float> output; //Output example.

    float a = 10.5, b = -7, c = 5.5; //Variables as search values.

    //Fill dataset:
    for (int i = 0; i < 100; i++) {
        input.push_back(i);
        output.push_back((a * (i * i)) + (b * i) + c);
    }

    clock_t begin = clock(); //Start clock while searching a, b, c values
    Linear linear;
    linear.LinearRegr(input, output, 15, -10, 0.5); //Start searching.
    cout << "Time: ~" << double(clock() - begin) / CLOCKS_PER_SEC << " seconds." << endl;

    cout << linear.resA << "*x^2 + " << linear.resB << "x + " << linear.resC << endl; //Enter results.
}

As can see, Linear.LinearRegr function can get from 3 to 5 parameters.
I dont need make the code super prettier(for me its already pretty), just want to work it faster.
How to optimize and make it faster?

Optimizing the algorithm
If \$M\$ is the number of steps between minimum and maximum, and \$N\$ is the size of the input and output vectors, then your algorithm has complexity \$\mathcal{O}(N \cdot M^3)\$. Also, it likely doesn't find the optimal solution unless you use a very small step size, and you have to choose minimum and maximum correctly. There are other algorithms that will both give you a guaranteed optimal solution without having to specify a range and a step size, and which have complexity \$\mathcal{O}(N)\$. This is possible since the problem of linear least squares can be solved analytically, and can be implemented efficiently on a computer.
If you don't want to go for the exact mathematical approach, and perhaps want to perform regressions of more complex functions that don't have an exact solution, then you might want to look into algorithms that approach the problem in a smarter way than just brute-forcing all possible values of the parameters. A typical solution to this kind of problem is to implement a gradient descent algorithm.
Choosing the right error function
The way you calculate the error (or rather the residual to be more precise) is quite strange. Normally one would try to minimize the sum of the squares of the difference between a data point and the predicted value. However, your error function is using the linear difference, and weighting it such that the first datapoint has the least weight, and the last datapoint weighs as much as all the other datapoints combined:
float error = Module(Predict(a, b, c, input[0]) - output[0]);
for (int i = 1; i < input.size(); i++)
    error = (Module(Predict(a, b, c, input[i]) - output[i]) + error)/2;

Unless this is really the intended function, you should probably replace this with a function that calculates the least squares residual.


Machine independent C library for printing the binary representation of data types to stdout I'm curious as to peoples thoughts on this small library I have made. I noticed there are no functions in the C standard library to accomplish this task.

I have tried to make the code machine independent. If anyone has access to machines where short != 2 byte, int != 4 byte, long != 8 byte or where bytes themselves are not 8 bits. I would be curious as to the test results.

GitHub

The current functions for printing the binary representations are all slight modifications of the below:

#include <limits.h>
#include <stdio.h>

void printcb(char n)
{
    int i;
    int type_bits = CHAR_BIT;
    int mask = 1 << type_bits - 1;

    for (i = 0; i < type_bits; ++i) {
        if (n & mask)
            putc('1', stdout);
        else
            putc('0', stdout);
        n <<= 1;
    }
    putc('\n', stdout);
}

You can just call putchar(), which automatically prints to stdout:

putchar('1');

The conditionals can instead be a ternary statement within putchar():

putchar(n & mask ? '1' : '0');

putchar is often better suited for single-character output. putchar only has to pass a character directly to the output. This particular code isn't exactly performance-critical but it's useful to acquire good coding habits from the beginning.


Rust, compute gcd: modularity, references This is my first time trying Rust. I wrote this code to compute the greater common divisor of 2 integers. Any advice to improve it? Am I using modularity/reference/borrow/dereference the correct way?

File src/gcd.rs:

// calculate the gcd of two integers
// https://en.wikipedia.org/wiki/Greatest_common_divisor

pub fn gcd(a: &i64, b: &i64) -> i64 {
    let mut _a = *a;
    let mut _b = *b;
    while _b != 0 {
        let tmp = _a;
        _a = _b;
        _b = tmp % _b;
    }
    _a
}

#[cfg(test)]
mod tests {
    use ::gcd;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd::gcd(&60, &168), 12);
        assert_eq!(gcd::gcd(&1071, &1029), 21);
    }
}

File src/main.rs:

mod gcd;

fn main() {
    println!("gcd({}, {}) = {}", 60, 168, gcd::gcd(&60, &168));
}

Directory structure:

$ tree
.
├── Cargo.lock
├── Cargo.toml
├── src
│   ├── gcd.rs
│   └── main.rs
└── target
    ├── ...

You do not need to take the numbers by reference.
Do not put an underscore at the beginning of the variable name. A variable name beginning with _ is used to say to the compiler that the variable is unused.

Otherwise, I see no issues in your code. Here is the solution taking account of my comments:

pub fn gcd(mut a: i64, mut b: i64) -> i64 {
    while b != 0 {
        let tmp = a;
        a = b;
        b = tmp % b;
    }
    a
}

#[cfg(test)]
mod tests {
    use ::gcd;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(60, 168), 12);
        assert_eq!(gcd(1071, 1029), 21);
    }
}

Further explanations:

  Why do I need to use let a = instead of let mut a = when calling it?

Not sure if my explanation is legit, but when you give a thing to another function, this function can do whatever it wants to this thing: it can take it as mutable or not. That is not anymore the problem of the previous owner.

  Which type of variables should and should not be passed by reference?

This is a very broad question. I advice you to think things differently. In Rust, you can give a thing, or only lend it (the thing is borrowed). The general answer is: if you do not need anymore the thing, or if the receiver needs a full control on it, give it away.

In this specific case, the thing is copyable and small (as small as a reference, in fact). So, borrow it does not give any advantage: just take it (or take a copy) and do not bother with references.


A program with a function that converts a string of digits into an integer value Here is a programming task:

Write a program with a function that converts a string of digits into an integer value. Do not use the strtol() function or any other standard C library function. Write your own!

I wanted this program to work perfectly with no errors. First I did the power function (power) and then next is function that return the length of a string (lent) and lastly is function that gives the value of asciicode (ascton).
In the main function there is a loop for the string where it multiple the value of how much zeros in has after it. For example, the string is "1100" so the first 1 is 1000 then this value is stored in variable z, and then this works for the other character and add it to variable z. At the end it return z as an integer of the string.
Is this code efficient, or did I use the "long way"? Please give me some hints how I can write better, cleaner and more readable code. Any feedback is appreciated.
#include <stdio.h>
#include <math.h>

int powe(int ex , int po)
{
  int z = 1;
  for (int i = 0; i < po; i++)
  {
    z = z * (10 * 1);
  }
  return z;
}

int lent (char a [20])
{
  int i=0;
  int l = 0;
  for(i=0 ; a[i] != '\0';i++)
  {
    l++;

  }
  return l;
}

int ascton (int a)
{
  int asciicode[10] = {48,49,50,51,52,53,54,55,56,57};
  for(int i = 0; i < 10; i++)
  {
    if (a == asciicode[i])
    {a = i;
     break;}
    else continue;
  }
  return a;
}

int main(void) {

  int z = 0;
  char sn[20];
  printf("enter your string number!:");
  scanf("%s",sn);

  int s = lent(sn);

  for(int i = 0; sn[i] != '\0';i++)
  {
    int k = 0;
    k = ascton(sn[i]);
    z = z + (k * powe(10, s-1));
    s = s-1;

  }
 printf("%d",z);
}
```

is this code efficient ?

No.  Rather than using the unnecessary powe(), lent(),

simply scale by 10 each operation; and
use - '0'.

.
char sn[20];
//scanf("%s",sn);
if (scanf("%19s", sn) == 1) {
  int z = 0;
  for (int i = 0; sn[i] >= '0' && sn[i] <= '9'; i++) {
    z = z*10 + (sn[i] - '0');
  }
  printf("%d",z);
}

Even better code would detect overflow and maybe use unsigned and/or wider types.


Comparing two shuffling methods I'm trying to randomly shuffle an collection of integers within a List and I have came up with two shuffling method that does the job. However, I'm not sure which one works better. Does any one have any comments or suggestions?

public class TheCollectionInterface {

    public static <E> void swap(List<E> list1, int i, int j){
        E temp = list1.get(i);
        list1.set(i, list1.get(j));
        list1.set(j, temp);
    }

//alternative version
//    public static void shuffling(List<?> list, Random rnd){
//        for(int i = list.size(); i >= 1; i--){
//            swap(list, i - 1, rnd.nextInt(i));
//        }
//    }

    public static <E> void shuffling(List<E> list1, Random rnd){
        for(int i = list1.size(); i >= 1; i--){
            swap(list1, i - 1, rnd.nextInt(list1.size()));
        }
    }

    public static void main(String[] args) {

        List<Integer> li2 = Arrays.asList(1,2,3,4,5,6,7,8,9);

        Random r1 = new Random();

        TheCollectionInterface.shuffling(li2, r1);

        System.out.println(li2);
    }
}

Your algorithm doesn't have simple uniform distribution over !n. Your alternative do has it, is actually a known algorithm named Fisher–Yates shuffle.


"mirror" elements in a list Write a method mirror that doubles the size of a list of integers by
  appending the mirror image of the original sequence to the end of the
  list. The mirror image is the same sequence of values in reverse
  order. For example, if a variable called list stores this sequence of
  values:

  [1, 3, 2, 7]

  and we make the following call:

  list.mirror();

  then it should store the following values after the
  call:

  [1, 3, 2, 7, 7, 2, 3, 1]

  Notice that it has been doubled in size by
  having the original sequence appearing in reverse order at the end of
  the list. You may not make assumptions about how many elements are in
  the list. Because adding these elements might overrun the capacity of
  the underlying array, you may need to call ensureCapacity to enlarge
  this array.

  Assume you are adding to the ArrayIntList class with following fields:

public class ArrayIntList {
    private int[] elementData;
    private int size;

    public void add(int value) { ... }
    public void add(int index, int value) { ... }
    public void ensureCapacity(int capacity) { ... }
    ...

    // your code goes here
}

What improvements can I make to help on my future coding? Interested in knowing if there are other ways to tackle this question, and if the way I solved the problem is safe? This code interacts with the ArrayIntList.java class.

public void mirror() {
    if (size != 0) {
        int limit = size * 2;
        this.ensureCapacity(limit);
        size = limit;
        for (int i = 0; i < size; i++) {
           elementData[(limit - 1) - i] = elementData[i];
        }
    }
}

This is good code, because it does what it says on the tin. I do have two remarks:

The this. in this.ensureCapacity(limit) isn't necessary. Some people swear by adding it anyway, so it's a matter of style.

The other remark is that you loop over twice as many elements as needed because you set size to limit before looping. You can hold off until after:

public void mirror() {
    if (size != 0) {
        int limit = size * 2;
        this.ensureCapacity(limit);
        //size = limit; // [!] moved to below >>>
        for (int i = 0; i < size; i++) {
           elementData[(limit - 1) - i] = elementData[i];
        }
        size = limit; // [!] <<< moved from above
    }
}

That's all. Good code.


How skinny should controllers be, how fat should models be in CakePHP? I know it's a good idea to put all data-related logic in your models in CakePHP, but what would you say about keeping every Model::find() and its particular params in the model? Is this good practice, or just taking things too far?

For example, is this:

PostsController:

function index() {
    $posts = $this->Post->getLatest();
    $this->set(compact('posts'));
}

Post model:

function getLatest() {
    $params = array(
        'conditions' => array('published' => 1),
        'limit' => 5,
        'order' => 'publish_date DESC'
    );
    return $this->find('all', $params);
}

Better than this:

PostsController:

function index() {
    $params = array(
        'conditions' => array('published' => 1),
        'limit' => 5,
        'order' => 'publish_date DESC'
    );
    $posts = $this->Post->find('all', $params);
    $this->set(compact('posts'));
}

Any thoughts? Which is better architecturally?

It's totally egilable to write shorthand-find functions. This way the controller is not depended of the model's parameters. I tend to go that far, that I don't use any fields directly in my controllers (and thus, not using find in controllers at all).
You could save a variable by defining the array in your find-call aswell ;).


Detecting existence of a class member I wanted to detect if I have a member in a simple POD struct and after some searching and merging some methods I found on the web I've come up with this solution:

#include <iostream>

template<class...Fs>
struct funcs_t{};

template<class F0, class...Fs>
struct funcs_t<F0, Fs...>: F0, funcs_t<Fs...> {
    funcs_t(F0 f0, Fs... fs):
    F0(std::move(f0)), funcs_t<Fs...>(std::move(fs)...)
    {}
    using F0::operator();
    using funcs_t<Fs...>::operator();
};

template<class F>
struct funcs_t<F>:F {
    funcs_t(F f) : F(std::move(f)) {};
    using F::operator();
};

template<class...Fs>
funcs_t<std::decay_t<Fs>...> funcs(Fs&&...fs) {
    return {std::forward<Fs>(fs)...};
}

#define HAS_MEMBER(cls, memb)\
    [](){\
        auto with_memb = [](auto &&A, int x)\
                -> decltype(typename std::remove_reference<decltype(A)>::type().memb, std::true_type())\
        {\
            return std::true_type();\
        };\
        auto with_no_memb = [](auto &&A, float x) -> std::false_type {\
            return std::false_type();\
        };\
        auto has_memb = funcs(with_memb, with_no_memb);\
        return has_memb(cls(), 1);\
    }()

struct A {
    int a;
    int b;
};

int main(int argc, char const *argv[])
{
    std::cout << HAS_MEMBER(A, b) << std::endl;
    return 0;
}

Your detector fails in the face of overloading and templating. Also, it will only detect (static) member-variables and (static) member-functions. While you can extend it to types (and type-aliases), accepting templates and overloading would need better language-provided reflection-facilities.

Anyway, pure existence is generally uninteresting, supported operations count.
funcs() and funcs_t are nearly a generally useful abstraction.

Just use perfect forwarding instead of by-value and std::move(). Allowing for all callables, including final classes, function-pointers, member-function-pointers, and the same wrapped in a std::reference_wrapper would admittedly add significant amounts of code.

A good name would be overloaded.
HAS_MEMBER needlessly depends on default-constructing the passed class. Fix that by using decltype, std::declval() and unevaluated contexts.
If you don't use an argument, don't name it. Specifically for main(), just don't ask for it.
Don't use std::endl. In the rare cases you actually need to flush manually, be explicit and use std::flush. Nearly always you are just crippling performance.
return 0; is implicit for main(). Make of that what you will.


Java8: Stream filter, map and joining with an alternative result if the stream is empty Given a list of integers, I would like to:

filter odds numbers
produce a list inside brackets: [n1, n2, n3]
if the list is empty it should be a dash -

My current implementation is:

private static String doIt(List<Integer> list) {
    List<String> l = list.stream()
            .filter(i -> (i % 2 == 0))
            .map(Object::toString)
            .collect(Collectors.toList());

    if (l.isEmpty()) {
        return "-";
    }
    return l.stream()
            .collect(Collectors.joining("; ", "[", "]"));
}

I am wondering if it is possible to do it without the intermediate list result l.

There is a problem with following implementation:

private static String doIt(List<Integer> list) {
    return list.stream()
            .filter(i -> (i % 2 == 0))
            .map(Object::toString)
            .collect(Collectors.joining("; ", "[", "]"));
}

The result in case of empty list is [] (expected is -)

Test method:

public static void main(String[] args) {
    System.out.println(doIt(Arrays.asList(1, 2, 3)));
    System.out.println(doIt(Arrays.asList(2, 3, 4)));
    System.out.println(doIt(Arrays.asList(1, 3)));
}

Expected Result:

[2]
[2; 4]
-

You can use reduce, it returns an Optional that is empty if the stream is empty. You can use map to create the csv (or reduce) and add the brackets and orElse to return "-".

private static String doIt(List<Integer> list) {
    return list.stream()
            .filter(i -> (i % 2 == 0))
            .map(Object::toString)
            .reduce((left, right)-> left+"; "+right)
            .map(csv -> "["+csv+"]")
            .orElse("-");
}


Find substrings in string I'm self-learning C now, and I want to find out if my code is good and clean or kinda messy.
For this exercise, the program tells if the text which was inserted has the keyword "asd", without using functions from string.h. If so, it returns how many times it was found.
it's not a big program, but I want to make sure it's clean and good so I don't pick up any bad practices.

#include "stdafx.h"
#include <stdio.h>

char findInStr(char *str, char *find) {
    unsigned char howMany = 0, strCounter = 0, findCounter = 0;
    do {
        if (findCounter == 3)
            howMany++;
        if (str[strCounter] == find[findCounter])
            findCounter++;
        else
            findCounter = 0;
        strCounter++;
    } while (str[strCounter-1] != '\0');
    return howMany;
}

int main() {
    char str[60];
    char find[5] = "asd";
    char found;

    printf("enter text: ");
    gets_s(str, 60);

    found = findInStr(str, find);
    if (found)
        printf("found!!! %d\n times", found);
    else
        printf("not found\n");

    return 0;
}

The problem statement

There's an ambiguity in the requirements, because you don't specify how to handle overlapping substrings.  For example, should findInStr("ababa", "aba") return 1, or 2?  Either of those may be useful, but be clear which interpretation is needed.  This code appears to count non-overlapping substrings.

Non-standard header

Despite its name, stdafx.h is not a standard header, so you can't use it in portable code.  Thankfully this program can easily become standard C, if you replace gets_s() with the equivalent fgets() call:

if (!fgets(str, sizeof str, stdin)) {
    perror("gets");
    return 1;
}

Note: this is not quite equivalent (thanks to Martin R for the comment), as get_s() discards the final newline; that won't make a difference unless we specifically look for a string ending in newline (which could now match once, rather than never).

Naming

I like the variable names you've used - I found it easy to understand your algorithm with the clear names.  (They do need to be a more suitable type - see Martin's answer for a very clear explanation).

I think they would be even clearer if you give them a line each for their declarations.

Bug (or undocumented constraint)

This test assumes that find will always be three characters long:

    if (findCounter == 3)
        howMany++;

We can make more versatile by counting until we see the NUL character at the end of find, like this:

    if (find[findCounter] == '\0') {
        howMany++;
        findCounter = 0;
    }

Bug

If a character is repeated in find, we don't start looking again in the right place.  We can test this with findInStr("ababaca", "abac") - this doesn't find the string because when we reach the second b, that doesn't match c and we start again from there (instead of going back to the start of the potential match).

The fix for this to subtract findCounter from strCounter before we reset it to zero, so we resume searching from the right place:

        if (str[strCounter] == find[findCounter]) {
            findCounter++;
        } else {
            strCounter -= findCounter;
            findCounter = 0;
        }

Modified version

Keeping your algorithm, but incorporating the fixes from this and other answers, I get:

#include <stdio.h>

/* Count the number of non-overlapping occurrences of find in str.
 * Returns zero if either string is empty.
 */
size_t findInStr(const char *str, const char *find)
{
    size_t howMany = 0;
    size_t strCounter = 0;
    size_t findCounter = 0;

    do {
        if (find[findCounter] == '\0') {
            ++howMany;
            findCounter = 0;
        }
        if (str[strCounter] == find[findCounter]) {
            ++findCounter;
        } else {
            strCounter -= findCounter;
            findCounter = 0;
        }
    } while (str[strCounter++] != '\0');

    return howMany;
}

I changed the test program to accept command-line arguments; this makes for easier testing.  I hope that this is educational reading (note that I check the arguments before attempting to use them).

int main(int argc, char **argv)
{
    if (argc != 3) {
        fprintf(stderr, "Usage: %s haystack needle\n", argv[0]);
        return 1;
    }

    const char *const haystack = argv[1];
    const char *const needle = argv[2];

    const size_t found = findInStr(haystack, needle);

    switch (found) {
    case 0:
        printf("'%s' was not found in '%s'.\n", needle, haystack);
        break;
    case 1:
        printf("'%s' was found once in '%s'.\n", needle, haystack);
        break;
    default:
        printf("'%s' was found %zd times in '%s'.\n", needle, found, haystack);
        break;
    }

    return 0;
}

Pointer version

This is a bit more advanced, and harder to get right, but I'll show you what this looks like when converted to use pointers rather than indexes.  A good optimizing compiler will likely generate the same code for both, but you'll want to be able to study and work with pointer code when you come across it.

size_t findInStr(const char *str, const char *const find)
{
    size_t howMany = 0;

    for (const char *find_pos = find;  *str;  ++str) {
        if (*str == *find_pos) {
            /* matched this char */
            if (!*++find_pos) {
                /* reached the end of find; count it and reset */
                ++howMany;
                find_pos = find;
            }
        } else {
            /* not matched - back up and continue */
            str -= find_pos - find;
            find_pos = find;
        }
    }

    return howMany;
}

Here, I've also used simply *str rather than the longer, but equivalent *str != '\0'.

Self-test program

An alternative main() can run a test suite, which can be useful in to avoid introducing bugs as you modify the code.  Here's what I accumulated when writing the above:

/* return failure count (0 or 1) */
static int test(const char *haystack, const char *const needle, size_t expected)
{
    const size_t actual = findInStr(haystack, needle);
    if (actual == expected) {
        return 0;
    }
    /* incorrect result */
    fprintf(stderr,
            "FAIL: findInStr(\"%s\", \"%s\") returned %zd instead of %zd\n",
            haystack, needle, actual, expected);
    return 1;
}

int main(void)
{
    return
        + test("abc", "", 0)
        + test("abc", "d", 0)
        + test("abc", "cd", 0)
        + test("abc", "ac", 0)
        + test("abc", "ab", 1)
        + test("ab", "abc", 0)
        + test("abab", "ab", 2)
        + test("ababa", "aba", 1)
        + test("ababac", "bac", 1)
        ;
}

You might choose to use a preprocessor #ifdef/#else to be able to compile the test or interactive version from one source, or you might write two programs sharing a single findInStr() implementation.


Netstring parser in common lisp Below is a netstring parser I wrote in Common Lisp. The docstring contains the usage and return.

(defun parse-netstring (netstring acc)
  "recursively parses netstring of the form
   size1:string1,size2:string2,size3:string3,
   acc can be any list, or nil
   returns -> (string3 string2 string1)"
  (if (equalp netstring "")
      acc
      (let* ((netstring-split
          (split-on-first-char #\: netstring))
         (comma-index
          (parse-integer (first netstring-split)))
         (netstring-body
          (second netstring-split)))
    (if (not (char= #\, (aref netstring-body comma-index)))
      (error 'malformed-netstring-error :netstring netstring)
      (parse-netstring
       (subseq netstring-body (1+ comma-index))
       (cons (subseq netstring-body 0 comma-index) acc))))))

First a few minor points:

You should give the definition of split-on-first-char since it is an important function in this context.
You should use equal instead of equalp to compare a value with a string (assuming that you cannot use string= to allow the first argument not to be a string).
The second parameter of parse-netstring could be defined as &optional, so that the function could be called with only the first parameter, and the second is automatically initialized with the empty list.

Then, let’s go to the main point: your function does not check many error conditions, and this is very bad for a function like this, that could get its input from the outside of the system (for instance, from a stream or a file). So, I think that you should do much more checks, for instance:

when the string does not start with a number,
when the first string part is less than the size,
when the size is greater than the whole string, etc.

The objective is to catch all the possible errors arising from calling primitive functions.

So I propose to rewrite the function in the following way, and in rewriting it I propose also a different approach to the recursion: use an auxiliary function, and recur only on the start index of the string, this make the code simpler and avoid a lot of costly subseq calls. Moreover, working with the indexes allow to get rid of the function split-on-first-char (again, with costly subseq calls). This is made possible also by the use of parse-integer with the junk-allowed parameter, which stops on the first non-numeric character, and by the fact that parse-integer returns two values, the number (which is NIL if it is not present), and the first position after the number. Here is the function:

(defun parse-netstring (netstring &optional acc)
  "recursively parses netstring of the form
   size1:string1,size2:string2,size3:string3,
   acc can be any list, or nil
   returns -> (string3 string2 string1)"
  (check-type netstring string "a string")
  (check-type acc list "a list")
  (let ((end (length netstring)))
    (labels ((parse-aux (start acc)
               (if (= start end)
                   acc
                   (multiple-value-bind (string-size semicolon-position)
                       (parse-integer netstring :start start :junk-allowed t)
                     (let ((comma-position
                             (when string-size (+ string-size semicolon-position 1))))
                       (unless (and string-size
                                    (< comma-position end)
                                    (<= string-size end)
                                    (char= (char netstring semicolon-position) #\:)
                                    (char= (char netstring comma-position) #\,))
                         (error  'malformed-netstring-error :netstring netstring))
                       (parse-aux
                         (1+ comma-position)
                         (cons (subseq netstring (1+ semicolon-position) comma-position) acc)))))))
      (parse-aux 0 acc))))


Splitting a CAN bus log in .asc format I've written a quick script for a coworker to split a large CAN log into smaller chunks.  (If you're not familiar with CAN, it's a communication protocol used by the ECUs in many cars.)  I know where to split because I've inserted dummy CAN messages (with ID 0x00) at the start of each section, and one at the end of testing (which may be somewhere in the middle of the log) to tell me when to stop reading.

The log is in .asc or .csv format, and can be several gigabytes in size.  Currently I can process a 1.5GB file in about 40 seconds, but I'm sure that can be improved.  I'm looking more for advice on how to speed this up than to make it more Pythonic, but of course criticism is welcome in both areas.

Note: titles is a dictionary mapping section numbers to a particular string that needs to be added to the filename before saving.  I can add the code for generating these, but I don't believe it's as relevant.

def split_asc_file(target_file, target_dir, titles):

    import os
    import time

    start_time = time.time()

    if not os.path.isdir(target_dir):
        os.mkdir(target_dir)
    os.chdir(target_dir)

    section = None

    def create_title(message_string):
        req_num = int(message_string[0:8])
        obj_num = int(message_string[8:16])

        if req_num == 0 and obj_num == 0:
            print "Splitting completed in {} seconds".format(time.time() - start_time)
            quit()  # final test has been executed
        else:
            at = "AT{}_{}".format(req_num, obj_num)
            title_prefix = titles[at]
            title_string = "{}_{}.asc".format(title_prefix, at)
            return title_string

    def can_traffic_only(f):
        # iterate only over lines that contain messages
        for line in f:
            if len(line.split()) == 14:
                yield line

    with open(target_file) as log:
        print "Opening {}...".format(target_file)
        for message in can_traffic_only(log):
            values = message.split()
            can_id = values[2]
            can_data = "".join(values[6:])

            if can_id == "0":
                if section:
                    section.close()
                title = create_title(can_data)
                if title:
                    print "Creating {}".format(title)
                    section = open(title, "w")
            else:
                if section:
                    section.write(message)

    print "Splitting completed in {} seconds".format(time.time() - start_time)

That looks like it's close to what you're going to get with Python I think.

I'd suggest taking a profiler and optimising according to that; e.g. I can imagine that doing less work using split and instead just counting the number of spaces (instead of allocating all the results) should be a bit faster (in can_traffic_only).

can_data can be delayed till the condition for the if block is true, but again, depends on how often that's the case.

If there's nothing else you could inline can_traffic_only and see if that makes a difference.


Modern C++ compliant insertion sort This is a kind of follow up to my previous sort implementation question with specific questions to insertion sort, and Modern C++ idioms. Anybody seeing this post can see how I got to this modern equivalent of a typical C-style sort you can find everywhere on the web by visiting my prior sorting review.

I am writing, as review for an interview, Modern C++ compliant versions of sorting algorithms I previously have seen. This post is about insertion sort, and insertion sort only.

// Shift/bubble each element toward the front into a sorted sub-array
template<typename BdIterator, typename Comparator = std::less<typename std::iterator_traits<BdIterator>::value_type>>
void sort_insertion(BdIterator beg, BdIterator end, Comparator cmp = Comparator())
{
    BdIterator front, cur, prev;
    // Assume the first element is sorted.
    for (front = beg + 1u; front != end; ++front)
    {
        cur = front;
        prev = cur - 1u;
        // Bubble the "next" element towards the front by swapping it with its
        // "prev" neighbor until it is in its sorted position.
        while (cur != beg && cmp(*cur, *prev))
            std::iter_swap(cur--, prev--);
    }
}

As before, I am looking for any performance optimizations I may have missed in the algorithm itself, as well as Modern C++ constructs I may not be abiding by for this example.

One specific question I have deals with the unsigned integer I am adding and subtracting from the iterators to move to the next and previous values in the container. Since there is no way to get the type of container for the provided iterators, I do not see a way to get the size_type of the assumed container to add and subtract the correct types rather than just unsigned/signed integers.

The fact that I am subtracting prevents me from declaring the minimal Iterator template type as forward iterators (We are moving the iterator backwards). Is there a better way around this or should I just stick to making the minimum BiDirectionalIterators?

"One specific question I have deals with the unsigned integer I am adding and subtracting from the iterators to move to the next and previous values in the container. Since there is no way to get the type of container for the provided iterators, I do not see a way to get the size_type of the assumed container to add and subtract the correct types rather than just unsigned/signed integers."

I just found std::prev and std::next defined in #include <iterator> which I think would handle some cases of signed/unsigned mismatch I was talking about.

For other cases where you would need to perform more complicated arithmetic, such as division or multiplication, you would use:

std::iterator_traits<BdIterator>::difference_type

std::distance returns std::iterator_traits<BdIterator>::difference_type.

std::next and std::prev take std::iterator_traits<BdIterator>::difference_type as parameters.
Arithmetic on bidirectional iterator may go backwards.

"The fact that I am subtracting prevents me from declaring the minimal Iterator template type as forward iterators (We are moving the iterator backwards). Is there a better way around this or should I just stick to making the minimum BiDirectionalIterators?"

I failed to realize that regardless of whether I use std::prev or not, the algorithm itself relies on moving the iterators both forwards and backwards, and therefore requires BiDirectional Iterators.

There is a more efficient solution that relies on finding a hole and bubbling up the hole to then insert the value into its sorted hole.

// Shift/bubble each element toward the front into a sorted sub-array
template<typename BidirIt, typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_insertion(BidirIt first, BidirIt last, Comparator cmp = Comparator())
{
    using category = typename std::iterator_traits<BidirIt>::iterator_category;
    static_assert(std::is_base_of<std::bidirectional_iterator_tag, category>::value, "This algorithm requires bidirectional iterators.");

    // 1 element containers are sorted; 2 duplicate element containers are sorted.
    if (first != last)
    {
        // Make a hole by removing the element you are checking,
        // and move elements up to that hole until you find the correct position of the element removed.
        // ++cur: Assume the first element is sorted.
        for (BidirIt cur = first; ++cur != last;)
        {
            auto val = std::move(*cur);
            BidirIt next = cur, prev = std::prev(next);
            while (cmp(val, *prev))
            {
                *next = std::move(*prev);
                next = prev;
                if (prev != first) --prev;
                else break;
            }
            // insert value in its sorted hole.
            *next = std::move(val);
        }
    }
}


Dynamically-sized stack - follow-up 3 Follow up of - Dynamically-sized stack - follow-up 2

I've took the tips given to me, and what I did now is:

Use same case type for type stack and it's functions
Returning 1 if push failed due to an OOM exception otherwise return 0 if succeeded.
push could now only return a pointer to null due to OOM exception and not because of allocating 0 bytes, in stack_initialize capacitiyIncrement is set to 1 if it's 0 preventing newStackSize being 0 if trying to push elements. Only occurrence where newStackSize will be 0 is if trying to shrink the stack size and there're no elements left in the stack.
Made a stack_realloc() function to deal with all stack reallocations.
stack_destroy() function is now freeing the memory of the elements saved in the stack and not the actual stack object.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct
{
    int *elementData;
    unsigned int stackSize;
    unsigned int capacityIncrement;
    unsigned int elementCount;
} stack;

void stack_initialize(stack*, unsigned int);
int stack_push(stack*, int);
void stack_pop(stack*);
int stack_peek(const stack*);
static int stack_realloc(stack*, unsigned int);
void stack_destroy(stack*);
bool stack_isEmpty(const stack*);
void stack_setCapacityIncrement(stack*, unsigned int);
unsigned int stack_getCapacityIncrement(const stack*);
unsigned int stack_getNumberOfElements(const stack*);
unsigned int stack_getSize(const stack*);

int main()
{
    stack s;
    stack_initialize(&s, 4);
    for(int i = 0; i < 25; i++)
    {
        stack_push(&s, i + 1);
    }
    stack_pop(&s);
    stack_push(&s, 88);
    stack_push(&s, 25);
    while (!stack_isEmpty(&s))
    {
        printf("The top of the stack is %d.\n", stack_peek(&s));
        stack_pop(&s);
        printf("The size of the stack is %u.\n", s.stackSize);
    }
}

void stack_initialize(stack *p, unsigned int capacityIncrement)
{
    p->elementData = NULL;
    p->stackSize = 0;
    if (capacityIncrement == 0)
    {
        capacityIncrement++;
    }
    p->capacityIncrement = capacityIncrement;
    p->elementCount = 0;
}

int stack_push(stack *p, int value)
{
    if(p->elementCount == p->stackSize)
    {
        if(stack_realloc(p, p->stackSize + p->capacityIncrement) == 1)
        {
            return 1;
        }
    }
    p->elementData[p->elementCount] = value;
    p->elementCount++;
    return 0;
}

void stack_pop(stack *p)
{
    if(!stack_isEmpty(p))
    {
        p->elementCount--;
        if(p->elementCount == 0 || p->stackSize - p->elementCount >= p->capacityIncrement / 2 + p->capacityIncrement)
        {
            stack_realloc(p, p->stackSize - p->capacityIncrement);
        }
    }
}

int stack_peek(const stack *p)
{
    if(!stack_isEmpty(p))
    {
        return p->elementData[p->elementCount - 1];
    }
    return 0;
}

static int stack_realloc(stack *p, unsigned int newStackSize)
{
    if (newStackSize > 0)
    {
        void *temp = realloc(p->elementData, sizeof(*p->elementData) * newStackSize);
        if(temp == NULL)
        {
            return 1;
        }
        p->elementData = temp;
    }
    else
    {
        stack_destroy(p);
    }
    p->stackSize = newStackSize;
    return 0;
}

void stack_destroy(stack *p)
{
    free(p->elementData);
    p->elementData = NULL;
}

bool stack_isEmpty(const stack *p)
{
    return p->elementCount == 0;
}

void stack_setCapacityIncrement(stack *p, unsigned int capacityIncrement)
{
    p->capacityIncrement = capacityIncrement;
}

unsigned int stack_getCapacityIncrement(const stack *p)
{
    return p->capacityIncrement;
}

unsigned int stack_getNumberOfElements(const stack *p)
{
    return p->elementCount;
}

unsigned int stack_getSize(const stack *p)
{
    return p->stackSize;
}

Its not a problem but this seems strange:

stack_realloc(p, p->stackSize - p->capacityIncrement);

Decreasing the size of the stack when you take elements out. This may cause a lot of work (in your code) if you are near a boundary and do a lot of push/pop combinations. It is unlikely that the memory is actually released by realloc() when shrinking anyway.


Increase performance of removing character from String I wrote this function as part of interview practice. This method removes a character from a given string.

I was wondering how I could make this code more efficient when it comes to runtime/space. I think my code is O(n) and I'm not sure if I can increase the efficiency. However, perhaps using things such as StringBuffer or StringBuilder would increase it a bit? I'm not sure as I'm still a bit new to Java.

public static String takeOut(String str, char c) {
    int len = str.length();
    String newstr = "";
    for (int i = 0; i < len; i++) {
        if (str.charAt(i) != c) {
            newstr = newstr + str.charAt(i);
        }
    }
    return newstr;
}

Learn from existing implementations, they usually have solutions to corner cases, common pitfalls and performance bottlenecks. For example, Apache Commons Lang StringUtils also has a remove function. It's implementation is quite simple and similar to yours:

public static String remove(final String str, final char remove) {
    if (isEmpty(str) || str.indexOf(remove) == INDEX_NOT_FOUND) {
        return str;
    }
    final char[] chars = str.toCharArray();
    int pos = 0;
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] != remove) {
            chars[pos++] = chars[i];
        }
    }
    return new String(chars, 0, pos);
}

Anyway, there are some differences:

It uses char array. Strings are immutable, the following concatenation creates a new String object:

newstr = newstr + str.charAt(i);

I guess it's slower than changing a value in an array.

  Using the string concatenation operator
  repeatedly to concatenate n strings requires time quadratic in n.

Source: Effective Java, 2nd edition, Item 51: Beware the performance of string concatenation
At the first line it checks whether the String contains the removed character at all. If it doesn't contain it remove saves the creation the char array. It might help but it depends on your input.
The code in the question calls String.charAt() in the comparison which checks the given index:

public char charAt(int index) {
    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

The StringUtils implementation skips this test since it knows that the index is valid.

(See also: Effective Java, 2nd edition, Item 47: Know and use the libraries)


RockPaperScissor in Python This is a simple Rock - Paper - Scissor game. I'm trying to find a better way to write the algorithm and keeping the scoreboard.

#!/usr/bin/python
#
import random
import os
import json
import pprint
#-------------------------------------------------#
def main():
    user, sys = 0, 0
    name = os.getlogin()
    while True:
        dictionary  = {1:'Rock', 2:'Paper', 3:'Scissors'}
        sysChoice   = random.choice(dictionary.keys())
        try:
            userChoice  = int(raw_input("Select One [1:Rock, 2:Paper, 3:Scissors, 0:Exit] : "))
            if (userChoice in (1,2,3)):
                print "Computer Choice is   : ", sysChoice,  dictionary[sysChoice]
                print "Your Choice is       : ", userChoice, dictionary[userChoice]
                result = rockPaperScissors(sysChoice, userChoice)
                print "Result               : ", result
                if (result == 'Win'):
                    user    = user + 1
                    sys     = 0
                    scoreBoard(user, sys, name)
                elif (result == 'Lose'):
                    user    = 0
                    sys     = sys + 1
                    scoreBoard(user, sys, name)
                else:
                    sys, user = 0, 0
                    scoreBoard(user, sys, name)
            elif(userChoice == 0):
                topScore()
                break
            else:
                continue
        except ValueError:
            continue
#-------------------------------------------------#
def rockPaperScissors (a, b):
    if ((a) % 3 + 1 == b):
        return "Win";
    elif ((b) % 3 + 1 == a):
        return "Lose"
    else:
        return "Draw"
#-------------------------------------------------#
def scoreBoard(u, s, name):
    if (os.path.isfile("score.json")):
        jsonFile = open("score.json", "r")
        data     = json.load(jsonFile)
        jsonFile.close()
        if name in data:
            print "Current Score        : ", u, s
            print "Top Score            : ", data[name]["user"], data[name]["sys"]
            if (u > (data[name]["user"])):
                data[name]["user"] = u
            if (s > (data[name]["sys"])):
                data[name]["sys"] = s
        else:
            data.update({name:{'user':0,'sys':0}})
        jsonFile = open("score.json", "w+")
        json.dump(data, jsonFile, indent=4)
        jsonFile.close()
    else:
        data = {name:{"user":0, "sys":0}}
        jsonFile = open("score.json", "w")
        json.dump(data, jsonFile, indent=4)
        jsonFile.close()
        os.chmod("score.json", 0666)
#-------------------------------------------------#
def topScore():
    if (os.path.isfile("score.json")):
        jsonFile = open("score.json", "r")
        data     = json.load(jsonFile)
        jsonFile.close()
        dicts = [{k: v} for (k,v) in data.items()]
        dicts.sort(key=lambda d: (d.values()[0]['user'], d.values()[0]['sys'],))
        dicts.reverse()
        print "Top Score : "
        for item in dicts:
            for key in item:
                print '{0:<10} {1:>2} {2:>2}'.format(key, item[key]['user'], item[key]['sys'])
#-------------------------------------------------#
if __name__ == '__main__':main()
#-------------------------------------------------#
# EOF

JSON file for keeping score:

    {
        "user1": {
            "sys": 2,
            "user": 2
        },
        "user2": {
            "sys": 3,
            "user": 3
        },
        "user3": {
            "sys": 0,
            "user": 6
        }
    }

You use a variable named dictionary. This is not helpful, as it's just the variable's type. Use meaningful variable names, how about handsigns or shapes or commands.

There are really three things being associated: the move names, the user input, and whatever internal representation you use. You currently have the user input being equivalent to the internal representation; that's okay. Initially I was against the idea of using a dictionary, but doing so allows you to use any user input.

Whatever variable name and type you use, the data structure does not need to be reinitialized in each loop. Set it once and leave it (though this may not affect your speed)

userChoice  = int(raw_input("Select One [1:Rock, 2:Paper, 3:Scissors, 0:Exit] : ")) I don't like this, because it duplicates the contents of your dictionary structure. You should just have one copy of the mapping, and refer to it here.

if (userChoice in (1,2,3)): same thing with this. You should just check if it's one of the keys.

           print "Computer Choice is   : ", sysChoice,  dictionary[sysChoice]
           print "Your Choice is       : ", userChoice, dictionary[userChoice]

This is duplicated code. Factor it out into a new function.

user and sys are poor variable names. It took a while before I realized that they meant the length of the user's and computer's current winning streaks. The variable name should reflect its purpose.

Why do you have else and except blocks that do literally nothing?