Finding Pythagorean triplet in array We have an integer array as:

private int[] arr = {1, 3, 5, 14, 18, 29, 78};

We have a function which takes three inputs of the array and checks whether:

a * a = b * b + c * c

If the function returns true then those 3 inputs are stored in an ArrayList:

private boolean findTriplet(int a, int b, int c) {
    int squareA = a * a;
    int squareB = b * b;
    int squareC = c * c;
    int sum = squareB + squareC;
    if (squareA == sum) {
        return true;
    }
    return false;
}

Iterating through the array:

 private void getTriplets(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 1; j < arr.length; j++) {
            if (i != j) {
                for (int k = i+j; k < arr.length; k++) {
                    if ((i != k) || (j != k)) {
                        boolean tripResult = findTriplet(arr[i], arr[j], arr[k]);
                        if (tripResult) {
                            tripList.add(new Triplet(arr[i], arr[j], arr[k]));
                        }
                    }
                }
            }
        }
    }
}

According to the above solution the complexity of the program is \$O(n^3)\$.

How can I optimise this solution or get a more flexible complexity?

A couple of notes on your code before going into alternative solutions.

In your findTriplet method, you are doing:

if (squareA == sum) {
    return true;
}
return false;

which is more concisely expressed as

return squareA == sum;

Your main getTriplets method checks whether (i != k) || (j != k), but this isn't possible by construction: k starts at i+j so it cannot be equal to i or j; thus this check can be removed. Also j starts at 1 when you could make it start at j + 1, which would also get rid of the i != j check.

You can do this in O(n²) by utilizing a TreeSet.

The idea is the following:

Transform the array into a TreeSet<Integer>, where each element will be the squared value of the element in the array. Using a TreeSet has the advantage that it sorts the elements ascendingly and allows for fast look-up.
For each element in the set, get all the elements greater than it and see if the set contains a third value equal to the sum of those two. This is because, if we look for 3 numbers a, b and c where a + b = c, then having both a and b only leaves the question: does the set contains a + b?

A possible implementation is the following:

private void getTriplets(int[] arr) {
    NavigableSet<Integer> set = new TreeSet<>();
    for (int element : arr) {
        set.add(element * element);
    }
    for (Integer a : set) {
        for (Integer b : set.tailSet(a, false)) {
            if (set.tailSet(b, false).contains(a + b)) {
                tripList.add(new Triplet(a, b, a + b));
            }
        }
    }
}

The method tailSet(element, false) will return a view of the set with all the elements strictly greater than the passed element. This method runs in constant-time. In the code above, a will loop through all the values of the set, b will loop over the values greater than a and we see if the set contains a + b. If it does then we have found a Pythagorian triplet.

This solution does have the overhead of creating a Set (so O(n) memory) but it is simple to write.

Another approach with O(1) memory is to keep an array but the approach is very similar:

  Sort the array in ascending order. This takes O(n log n).
  Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i.

  To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that's one of the answers, print it, and shift both indexes.

  This takes O(i) operations.
  Repeat step 2 for each index i. This way you'll need totally O(n²) operations, which will be the final estimate.

Step 2 is similar to finding a given number by summing up integers from 2 sorted arrays.

In terms of code, you could have the following:

private void getTriplets(int[] arr) {
    int[] squaredArray = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        squaredArray[i] = arr[i] * arr[i];
    }
    Arrays.sort(squaredArray);
    for (int i = arr.length - 1; i >= 0; i--) {
        int j = 1, k = i;
        while (j < k) {
            int sum = squaredArray[j] + squaredArray[k];
            if (sum < squaredArray[i]) {
                j++;
            } else if (sum > squaredArray[i]) {
                k--;
            } else {
                tripList.add(new Triplet(squaredArray[j], squaredArray[k], squaredArray[i]));
                j++;
                k--;
            }
        }
    }
}

The main loop on i is performed descendingly since we're looking for two elements whose sum is squaredArray[i] (and the array is sorted ascendingly).


Count number of registers in interval & location Recently I asked how one could count the number of registers by the interval as answered in https://stackoverflow.com/questions/49240140/count-number-of-registers-in-interval.

The solution works great, but I had to adapt it to also take into account some localization key.

I did it through the following code:

def time_features(df, time_key, T, location_key, output_key):
    """
    Create features based on time such as: how many BDs are open in the same GRA at this moment (hour)?
    """
    from datetime import date
    assert np.issubdtype(df[time_key], np.datetime64)
    output = pd.DataFrame()

    grouped = df.groupby(location_key)
    for name, group in grouped:
        # initialize times registers open as 1, close as -1
        start_times = group.copy()
        start_times[time_key] = group[time_key]-pd.Timedelta(hours=T)
        start_times[output_key] =  1

        aux = group.copy()
        all_times = start_times.copy()
        aux[output_key] = -1
        all_times = all_times.append(aux, ignore_index=True)

        # sort by time and perform a cumulative sum to get opened registers
        # (subtract 1 since you don't want to include the current time as opened)
        all_times = all_times.sort_values(by=time_key)
        all_times[output_key] = all_times[output_key].cumsum() - 1

        # revert the index back to original order, and truncate closed times
        all_times = all_times.sort_index().iloc[:len(all_times)//2]
        output = output.append(all_times, ignore_index=True)
    return output

Output:

time    loc1    loc2
0   2013-01-01 12:56:00 1   "a"
1   2013-01-01 12:00:12 1   "b"
2   2013-01-01 10:34:28 2   "c"
3   2013-01-01 09:34:54 2   "c"
4   2013-01-01 08:34:55 3   "d"
5   2013-01-01 08:34:55 5   "d"
6   2013-01-01 16:35:19 4   "e"
7   2013-01-01 16:35:30 4   "e"

time_features(df, time_key='time', T=2, location_key='loc1', output_key='count')

This works great for small data, but for longer data (I using it with a file with 1 million rows) it takes "forever" to run. I wonder if I could optimize this computation somehow.

Consider not expanding a dataframe inside the for loop but build a list or dictionary and then concatenate all dataframe elements outside loop.

Expanding objects within a loop causes substantial memory resources to allocate before and after blocks with lots of copying of objects to do so. Running one call on outside should substantially run faster as virtually no copying is done.

Specifically change:

output = pd.DataFrame()

To a list:

output = []

And then append to list inside loop and then pd.concat(list) outside loop.

def time_features(df, time_key, T, location_key, output_key):
    """
    Create features based on time such as: how many BDs are open in the same GRA at this moment (hour)?
    """
    from datetime import date
    assert np.issubdtype(df[time_key], np.datetime64)
    output = []

    grouped = df.groupby(location_key)
    for name, group in grouped:
        # initialize times registers open as 1, close as -1
        start_times = group.copy()
        start_times[time_key] = group[time_key]-pd.Timedelta(hours=T)
        start_times[output_key] =  1

        aux = group.copy()
        all_times = start_times.copy()
        aux[output_key] = -1
        all_times = all_times.append(aux, ignore_index=True)

        # sort by time and perform a cumulative sum to get opened registers
        # (subtract 1 since you don't want to include the current time as opened)
        all_times = all_times.sort_values(by=time_key)
        all_times[output_key] = all_times[output_key].cumsum() - 1

        # revert the index back to original order, and truncate closed times
        all_times = all_times.sort_index().iloc[:len(all_times)//2]
        # APPEND TO LIST
        output.append(all_times)

    # CONCATENATE ALL DF ELEMENTS
    final_df = pd.concat(output, ignore_index=True)

    return final_df


Gradient descent for linear regression using numpy/pandas I currently follow along Andrew Ng's Machine Learning Course on Coursera and wanted to implement the gradient descent algorithm in python3 using numpy and pandas.

This is what I came up with:

import os
import numpy as np
import pandas as pd

def get_training_data(path):    # path to read data from
    raw_panda_data = pd.read_csv(path)

    # append a column of ones to the front of the data set
    raw_panda_data.insert(0, 'Ones', 1)

    num_columns = raw_panda_data.shape[1]                       # (num_rows, num_columns)
    panda_X = raw_panda_data.iloc[:,0:num_columns-1]            # [ slice_of_rows, slice_of_columns ]
    panda_y = raw_panda_data.iloc[:,num_columns-1:num_columns]  # [ slice_of_rows, slice_of_columns ]

    X = np.matrix(panda_X.values)   # pandas.DataFrame -> numpy.ndarray -> numpy.matrix
    y = np.matrix(panda_y.values)   # pandas.DataFrame -> numpy.ndarray -> numpy.matrix

    return X, y

def compute_mean_square_error(X, y, theta):
    summands = np.power(X * theta.T - y, 2)
    return np.sum(summands) / (2 * len(X))

def gradient_descent(X, y, learning_rate, num_iterations):
    num_parameters = X.shape[1]                                 # dim theta
    theta = np.matrix([0.0 for i in range(num_parameters)])     # init theta
    cost = [0.0 for i in range(num_iterations)]

    for it in range(num_iterations):
        error = np.repeat((X * theta.T) - y, num_parameters, axis=1)
        error_derivative = np.sum(np.multiply(error, X), axis=0)
        theta = theta - (learning_rate / len(y)) * error_derivative
        cost[it] = compute_mean_square_error(X, y, theta)

    return theta, cost

This is how one could use the code:

X, y = get_training_data(os.getcwd() + '/data/data_set.csv')
theta, cost = gradient_descent(X, y, 0.008, 10000)

print('Theta: ', theta)
print('Cost: ', cost[-1])

Where data/data_set.csv could contain data (model used: 2 + x1 - x2 = y) looking like this:

x1, x2, y
0, 1, 1
1, 1, 2
1, 0, 3
0, 0, 2
2, 4, 0
4, 2, 4
6, 0, 8

Output:

Theta:  [[ 2.  1. -1.]]
Cost:  9.13586056551e-26

I'd especially like to get the following aspects of my code reviewed:

Overall python style. I'm relatively new to python coming from a C background and not sure if I'm misunderstanding some concepts here.
numpy/pandas integration. Do I use these packages correctly?
Correctness of the gradient descent algorithm.
Efficiency. How can I further improve my code?

Without having the insight (or, honestly, time) to verify your actual algorithm, I can say that your Python is pretty good.

Only minor stuff - this kind of comment - # path to read data from - should be turned into a PEP257-style docstring.

You should add a shebang at the top of your file, probably #!/usr/bin/env python3.

Otherwise, you're off to a good start.


Replacing tokens in a text file with replaced text This code parses a text file, replacing special tokens marked as $(token) with some replaced text.  The $ symbol can be escaped by entering a double $$.  In the example a user enters a text file containing tokens to replace and a separate mapping file with, for instance, colour:red to denote how to replace a token.

Some remarks I have is that is is not using any OO really.  Does it need to be?

#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <string>

static void readToken(std::istream& strm, std::vector<char>& token)
{
   while(strm) {
      int c (strm.get());
      token.push_back(c);
      if(')' == c) break;
   }
}

static void lookup_replacement(const std::map<std::string,std::string>& token_map,
                               const std::vector<char>& key, std::vector<char>& value) {
    if(key.size() > 3) {  //3 chars min are '$', '(' and ')'
        std::map<std::string,std::string>::const_iterator it = token_map.find(std::string(key.begin()+2, key.end()-1));
        if(it != token_map.end())
           value.insert(value.end(), it->second.begin(), it->second.end());
    }
}

static bool readTo(std::istream& strm, std::vector<char>& buf, const char term[])
{
   bool ret(false);
   while(strm) {
      int c (strm.peek());
      if(strchr(term, c)) {
         strm.get();
         int c2(strm.peek());
         if(c != c2) {
           strm.unget();
           ret = true;
           break;
         }
      }
      strm.get();
      buf.push_back(c);
   }
   return ret;
}

static void create_mapping(std::ifstream& strm, std::map<std::string,std::string>& tokens) {
   if(strm.good()) {
      std::string line;
      while(std::getline(strm, line)) {
         std::string::size_type pos = line.find_first_of(':');
         if(pos != std::string::npos)
            tokens.insert(std::make_pair<std::string, std::string>(line.substr(0, pos), line.substr(pos+1)));
      }
   }
}

int main() {
   std::map<std::string,std::string> token_map;

   typedef std::map<std::string,std::string>::iterator map_iter;

   std::cout << "Enter path to text file to replace\nTokens to be replaced should be of form: $(token)\n";
   std::string file;
   std::cin >> file;

   std::cout << "Enter path to file with target token <-> replacement token in format:\n"
                "<toreplace1>:<replacement1>\n<toreplace2>:<replacement2>\netc\n";
   std::string mapfile;
   std::cin >> mapfile;

   std::ifstream strmmap(mapfile.c_str());
   create_mapping(strmmap, token_map);

   // replaced text
   std::vector<char> replaced;

   std::ifstream strm(file.c_str());
   if(!strm.bad()) {
      while(!strm.eof()) {
         if(readTo(strm, replaced, "$")) {
            std::vector<char> token;
            readToken(strm, token);
            std::vector<char> replace_tok;
            lookup_replacement(token_map, token, replace_tok);
            if(!replace_tok.empty())
                replaced.insert(replaced.end(), replace_tok.begin(), replace_tok.end());
         }
      }
   }

   //print out replaced text
   std::cout << "your replaced text file\n";
   std::vector<char>::iterator pit = replaced.begin();
   while(pit != replaced.end())
      std::cout << *pit++;

   return 0;
}

The example input file I was using:

  Once upon a $(place1) there was a $(adjective1) $(colour) $(animal).

  Do you have a $$

  You have enemies? Good. That means you've stood up for something,
  sometime in your life. by $(author) on $(date)

  A fanatic is one who can't change his mind and won't change the
  subject. By $(author)

And the mapping file:

place1:time
adjective1:cunning
colour:brown
animal:fox
author:Winston Churchill
date:06/06/2013

Its a little heavy on the code side.

Your definition of a token still leaves possibilities that you have not defined.

$$          :  Replace with $                                         Fine
$(<X>)      :  Replace with the mapped `<X>`                          Fine.

$(<stuff>\n : No closing ')'                                          Error
$()         : What happens with no identifier.                        Error
$<X>        : Some other character after '$' that is not '(' or '$'   Error

Especially your stream handling.
Its usually bad practice to test for .good(), .bad() or .eof() during normal processing. You want to test these after things go wrong to generate the appropriate error message or not. Usually stream code looks like this:

while(std::getline(stream, line))
{
    // correctly read a line
}

// or

while(stream >> value >> value2 >> value3 >> etc)
{
    // correctly read a value from the stream
}

You can use OO to compartmentalize your mapping.
Personally I would combine your mapper and mapped class into a single class.

class Mapper
{
    // Class contains a map from tokens => value
    // used via replace() to replace all tokens $(<X>) in string
    // with the values contained in the map.

    std::map<std::string, std::string>  replaceMap;
    public:
        Mapper(std::string const& fileName)
        {
            // Read all the mapping values from the file.

            std::ifstream   mapFile(fileName.c_str());
            std::string     line;

            while(std::getline(mapFile, line))
            {
                // Each line in the file contains a token/value mapping
                std::stringstream   linestream(line);

                std::string         token;
                std::string         value;

                std::getline(linestream, token, ':');
                std::getline(linestream, value);

                // Save the token and value
                replaceMap[token]  = value;
            }
        }

        std::string replace(std::string const& line)
        {
            std::string result;
            std::size_t last = 0;

            // Search for the '$' char repeatedly.
            for(std::size_t find = line.find('$');find != std::string::npos;last=find, find=line.find('$', find))
            {
                // Copy the inert text from line
                // into the result
                result  += line.substr(last, (find-last));

                // If the next character is a '(' then search for the closing ')'
                //
                // If we don't find a token `$(<X>)` then ignore the '$' and treat
                // it like a normal character. Note If <X> has no mapping then
                // we replace it with the empty string. Note if <X> is empty it is
                // is still value.

                bool hit = false
                if ((find + 1 < line.size()) && line[find + 1] == '(')
                {
                    std::size_t end = line.find(')', find);
                    if (end != std::string::npos)
                    {
                        std::string key = line.substr(find+2, end-find-2);
                        result += replaceMap[key];
                        find = end + 1;
                        hit  = true;
                    }
                }

                if (!hit)
                {
                    // Token was not found.
                    // Put the '$' on the output and move on.
                    result  += '$';
                    find++;
                }
            }
            // Add the rest of the inert string to the output
            result  += line.substr(last);

            return result;
        }
};

This makes it easy to use:

int main(int argc, char* argv[])
{
    Mapper  mapper(argv[1]);

    std::ifstream   input(argv[2]);
    std::string     line;
    while(std::getline(input, line))
    {
        std::string result = mapper.replace(line);
        std::cout << result << "\n";
    }
}


Color string from object (random if empty, deterministic else) from random import random

def to_color(obj=None):
    """Determine a color (string 000000-ffffff) from the hash of any object

    If no argument is passed, a random color is returned.

    Args:
        obj: any hashable object; string, tuple, ...

    Returns:
        a color string in range '000000' to 'ffffff'
    """
    obj = obj if obj else random()
    return "{0:06x}".format(abs(hash(obj)))

My questions:

Is the line obj = obj if obj else random() idiomatic?
Is hash(obj) the "proper" way to get a deterministic yet scrambled string for my purpose?
The abs takes care of negative hash values (e.g. from hashing negative integers). Is there a better way which doesn't collide so easily for small (absolute) integer values? (Right now, to_color(500) is equal to to_color(-500).)

From PEP 8:

  Comparisons to singletons like None should always be done with is or
  is not, never the equality operators.

  Also, beware of writing if x when you really mean if x is not None --
  e.g. when testing whether a variable or argument that defaults to None
  was set to some other value. The other value might have a type (such
  as a container) that could be false in a boolean context!

What you should do in your case is : obj = obj if obj is not None else random().

Then, even though I like the ternary operator, I reckon its usage is not required/idiomatic here. The usual way to handle default parameter is more like

if arg is None:
    arg = default()

As far as I can tell, using hash like you did is ok. However, I guess you should handle values that could be out of the range you are expecting (I couldn't find easily something telling which range of values can be returned).


Plotting terrain pixels with PyGame based on random NumPy array I am experimenting with Perlin Noise and random map generation. I have a 2D numpy ndarray full of 16-bit floats called map_list that I call from the singleton ST. It has 900 rows with 1600 elements each. I am iterating through it to display different colored pixels to represent terrain at different points in the map. Array values in different ranges produce pixels of different colors. The total possible range is [0, 1] because I am normalizing the values.

Is there a way to display the aforementioned pixels faster than I am capable of now?

"""

This file holds functions that modify pyGame surfaces.

"""

from __future__ import division
from singleton import ST
from pygame import gfxdraw

def display_map(surface):
    """
    This takes in a pyGame surface, and draws colored tiles on it according to
    the values in ST.map_list. The higher the value, the lighter the shade of
    the tile.

    :param surface: A pyGame surface.
    """

    x_pos = 0
    y_pos = 0

    for y in range(len(ST.map_list)):

        for x in range(len(ST.map_list[y])):
            noise_value = ST.map_list[y][x]
            shade = int(noise_value * 255)
            color = __color_tiles(noise_value, shade)

            gfxdraw.pixel(surface, x_pos, y_pos, color)
            x_pos += ST.TILE_SIZE

        x_pos = 0
        y_pos += ST.TILE_SIZE

def __color_tiles(noise_value, shade):
    """
    Treat this function as private. It should only be called by functions and
    methods within this file. It returns a 3-element 1D tuple that represents
    the rgb color values to display the tile as.

    :param noise_value: The noise value at a specific point in ST.map_list.
    :param shade: How dark or light the tile should be.
    :return: tuple
    """

    if noise_value < ST.WATER_LEVEL:
        rgb = (shade, shade, 255)
    elif noise_value > ST.MOUNTAIN_LEVEL:
        rgb = (shade, shade, shade)
    else:
        rgb = (shade, 255, shade)

    return rgb

What it generates

If you have a lot of data in a rectangle, and you need to go fast, the answer is always the same: import numpy as np

Pygame has added some functions that support numpy arrays for exactly this reason. So you can fairly painlessly convert from an appropriately sized numpy array to a surface. You could even go back again, if you wanted.

Here's some code that does something similar to what you appear to be doing. I stripped out the stuff that you didn't provide source for, and focused on just doing the high/low/mid cutoff you seem to want. Also note, I'm using python 3, so there will likely be some slight gotchas in the syntax:

# https://codereview.stackexchange.com/questions/215575/plotting-terrain-pixels-with-pygame-based-on-random-numpy-array
"""

This file holds functions that modify pyGame surfaces.

"""

import numpy as np
import pygame

screen_size = (180, 320)

def display_map(noise):  # NOTE: I expect noise to be a 2-d np.ndarray
    ''' Return a surface with terrain mapped onto it. '''

    CHANNELS = 3  # use 4 for alpha, I guess
    RED = 0
    GREEN = 1
    BLUE = 2
    WATER_LEVEL = 0.20
    MOUNTAIN_LEVEL = 0.75

    # NOTE: numpy automagically "vectorizes" things like this.
    # array times scalar means a[i,j] * scalar, for all i,j
    shade = (noise * 255).astype(np.ubyte)

    # NOTE: dstack "stacks" however-many 2d arrays along the "depth" axis
    # producing a 3d array where each [i,j] is (X,X,X)
    rgb = np.dstack([shade] * 3)

    # NOTE: (WATER_LEVEL <= noise) produces a 2d boolean array, where
    # result[i,j] = (WATER_LEVEL <= noise[i,j]), kind of like the scalar
    # multiply above. The '&' operator is overloaded for boolean 'and'.
    # The upshot is that this assignment only happens where the boolean
    # array is 'True'
    rgb[(WATER_LEVEL <= noise) & (noise <= MOUNTAIN_LEVEL), GREEN] = 255
    rgb[(noise < WATER_LEVEL), BLUE] = 255

    # NOTE: pygame.surfarray was added mainly to talk to numpy, I believe.
    surf = pygame.surfarray.make_surface(rgb)
    return surf

pygame.init()
running = True
display = pygame.display.set_mode(screen_size)

noise = np.random.random_sample(screen_size)
terrain = display_map(noise)

while running:
    for ev in pygame.event.get():
        if ev.type == pygame.QUIT:
            running = False

    display.blit(terrain, (0, 0))
    pygame.display.update()


Fundamental Polygon in Python I am writing a python class to implement a object moving along a Fundamental Polygon.  It takes in a size of the square and config option with three booleans enumerating the 8 possibilities, the first bit indicates whether connected sides are opposite or adjacent, the second indicates if the primary sides are parallel or antiparallel, and the third indicates if the secondary sides are parallel or antiparallel.

For example to denote a torus the config would be:

 (False, False, False)

My implementation of the wraparound (when the pointer moves off the edge of the square), is quite messy.  I'm not sure what I should do to make the code more readable and straight forward.

class Topology(object):
    def __init__(self,dim,config):
        self.dim = dim
        self.direction = [0,1]
        self.location = [0,0]
        # (matching, primary twist, secondary twist)
        self.config = config
    def move(self):
        self.location = [
            self.location[0]+self.direction[0],
            self.location[1]+self.direction[1]
        ]
        #Important bit
        if self.location[0] >= self.dim[0]:
            if config[1]:
                self.location[1] *= -1
            if config[0]:
                self.location = self.location[::-1]
                self.direction = self.direction[::-1]
        if self.location[1] >= self.dim[1]:
            if config[2]:
                self.location[0] *= -1
            if config[0]:
                self.location = self.location[::-1]
                self.direction = self.direction[::-1]
        if self.location[0] < 0:
            if config[2]:
                self.location[1] *= -1
            if config[0]:
                self.location = self.location[::-1]
                self.direction = self.direction[::-1]
        if self.location[1] < 0:
            if config[1]:
                self.location[0] *= -1
            if config[0]:
                self.location = self.location[::-1]
                self.direction = self.direction[::-1]
        self.location[0] %= self.dim[0]
        self.location[1] %= self.dim[1]

First thing first, make config a named tuple. This would seriously improve readability, and obviate the (really unclear) comment.
Factored out the repeated code into a function, e.g.:

def wraparound(coord, matching, twist):
    if 0 < self.location[coord] < self.dimension[coord]:
        return
    if twist:
        self.location[1 - coord] *= -1
    if matching:
        self.location = self.location[::-1]
        self.direction = self.direction[::-1]


Low C performance for TSP heuristic I've been recently doing classes on the traveling salesman problem. I've been tackling the nearest neighbor heuristic for the problem and seeing that the algorithm was simplistic, I've decided to see how fast would be solutions implemented in different languages. I've implemented several versions of the solution using different lua extensions, of those most importantly, luajit. I've also done the same algorithm in C.

What surprised me is that luajit solution using C data structures actually beats the pure C implementation significantly (5-6 times faster) C was compiled with gcc -o3 and the problem size was such that completion times were on the order of a few seconds.

I'm not very well versed in the ways of the language, so I wonder if I didn't do something right in C code:

#include <math.h>

typedef struct city {double x; double y; double ind;} city;

double tsp(city* cities, int N){
    city current=cities[0];
    double S=0;
    for (int i=N-1; i>0; i--){
        int pos=i;
        city  viewing= cities[i];
        double d2=pow((current.x-viewing.x),2)+pow((current.y-viewing.y),2);
        double ind=viewing.ind;
        for (int j=1; j<i; j++){
            viewing=cities[j];
            double D2=pow((current.x-viewing.x),2)+pow((current.y-viewing.y),2);
            if ((D2 < d2)||((D2==d2)&&(viewing.ind<ind))){
                pos=j;
                d2=D2;
                ind=viewing.ind;
            }
        }
        S+=sqrt(d2);
        current=cities[pos];
        cities[pos]=cities[i];
    }
    return S+sqrt(pow((cities[0].x-cities[1].x),2)+pow((cities[0].y-cities[1].y),2));
}

The function implements the following algorithm: start at city[0], find nearest city, go there, find nearest unvisited city, go there, repeat until no cities left, go to city[0].

Well, the first thing to do is extracting the distance-calculation and replacing the costly call to pow():

inline static double distance2(city* a, city* b) {
    double dx = a->x - b->x;
    double dy = a->y - b->y;
    return dx * dx + dy * dy;
}

Next, let's stop always copying the cities when not really needed.

Optionally, use a sentinel value (INFINITY) so we don't need to single out any candidate for nearest city.

Another nearly gratuitious change I did was starting with the last city given.

I suggest you also invest in slightly more spaces, they make things more readable, especially around operators.

The changed function:

double tsp(city* cities, int N) {
    double S = 0;
    for (int i = N; --i > 0;) {
        double best_d2 = distance2(cities + i, cities + 0);
        int best_pos = 0;
        for(int j = i; --j > 0;) {
            double d2 = distance2(cities + i, cities + j);
            if(d2 < best_d2 || d2 == best_d2 && cities[j].ind < cities[best_pos].ind) {
                best_d2 = d2;
                best_pos = j;
            }
        }
        S += sqrt(best_d2);
        city temp = cities[best_pos];
        cities[best_pos] = cities[i - 1];
        cities[i - 1] = temp;
    }
    return S + sqrt(distance2(cities, cities + N - 1));
}


Dice roll program with statistics This is a working program I made to roll dice a specified number of times, show how many times each number (2-12) occurred, and the percentage of the total rolls that each number got.

I'm trying to make improvements to the efficiency of my code. I've already found one, as noted beside int[] results on line 15. Are there any tools I could have used to make this code more efficient in terms of performance, or that could have saved me time? (Such as ArrayList, case/switch etc)

import java.util.Random;
import java.util.Scanner;
import java.text.DecimalFormat;
public class Dice {
    public static void main(String[] args){
        DecimalFormat df = new DecimalFormat("#.#"); //how to display percentage of results
        Scanner sc = new Scanner(System.in);
        System.out.println("How many times would you like to roll the dice?");
        int rolls = sc.nextInt();
        int[] counts = new int[rolls]; //creates an array of user-specified length (rolls)
        sc.close();
        for(int i = 0; i < counts.length; i++){ //populates said array with each roll of the dice
            counts[i] = diceRoll();
        }
        int[] results = counters(counts); /*creates a new array with the returned array that counters(counts) gave us.
                                        Seems redundant, but it is noticeably faster at high numbers to iterate through this array
                                        than it is to access the counters method 3 times in the loop below (by using counters(counts) instead of results).*/

        System.out.println("Roll\t\tCount\t\tFrequency"); //Headers for the results table
        for(int i = 0; i < results.length; i++){ //iterates through our results array, prints how many times each number was rolled, along with its percentage of the total rolls
            System.out.println((i+2)/*to start the table at 2, since rolling a 0 is not possible*/+"\t\t" + (results[i]) + "\t\t"+df.format(100.0*(results[i])/counts.length)+ "%");
        }
    }
    public static int diceRoll(){ //rolls 2 6-sided dice and returns their sum
        Random rand = new Random();
        int dice1 = rand.nextInt(6)+1;
        int dice2 = rand.nextInt(6)+1;
        int roll = dice1+dice2;
        return roll;
    }
    public static int[] counters(int[] arr){ //keeps track of how many times each possible number is rolled, puts the results into an array and returns the array
        int c2=0;
        int c3=0;
        int c4=0;
        int c5=0;
        int c6=0;
        int c7=0;
        int c8=0;
        int c9=0;
        int c10=0;
        int c11=0;
        int c12=0;
        for(int i = 0; i < arr.length; i++){
            if(arr[i]==2)
                c2++;
            else if(arr[i]==3)
                c3++;
            else if(arr[i]==4)
                c4++;
            else if(arr[i]==5)
                c5++;
            else if(arr[i]==6)
                c6++;
            else if(arr[i]==7)
                c7++;
            else if(arr[i]==8)
                c8++;
            else if(arr[i]==9)
                c9++;
            else if(arr[i]==10)
                c10++;
            else if(arr[i]==11)
                c11++;
            else if(arr[i]==12)
                c12++;
        }
        int[] rollCounts = new int[] {c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12};
        return rollCounts;
    }
}

It is nice that you have separate methods for throwing the dice and computing the counts. However, diceRoll can be simplified and counters supersimplified; like this

    public static int diceRoll() {
        Random rand = new Random();
        return rand.nextInt(6) + rand.nextInt(6) + 2;
    }

    public static int[] counters(int[] arr) {
        int[] counterArray = new int[11];

        for (int dice : arr) {
            counterArray[dice - 2]++;
        }

        return counterArray;
    }

(Edit Also, the name of each method should (preferably) begin with a verb: counters \$\rightarrow\$ countResults and diceRoll \$\rightarrow\$ rollDice.)

Hope that helps.


Quick estimation for empirical permutation and correlation test in R I have two matrices (a, b), each including 3 genes and 6 observations. I have estimated the Spearman correlation for gene pairs (rcorr.observed). Then I want to do an empirical permutation (1000 times) and estimate the correlation for each time, then achieve a Pval_estim file. Since I have a very huge datasets (23000*23000), the script is very slow. I wonder if you could help me to speed it up. I have also used some code from (+).

a<-structure(c(7.284640193, 8.386102403, 10.27187091, 6.56612737,
8.969982518, 10.03221978, 7.193522121, 7.358283395, 10.92117745,
7.162802801, 8.297228578, 11.36980277, 7.865611714, 7.999185693,
10.33028086, 6.831671275, 8.953536984, 8.826461297), .Dim = c(3L,
6L), .Dimnames = list(c("DDR1_MIR4640", "RFC2", "HSPA6"), c("a_1", "a_2", "a_3",     "a_4", "a_5", "a_6")))

b<-structure(c(9.1048886, 6.4114527, 5.7281808, 9.4302985, 6.2576226,
4.871274, 9.187927, 5.9036324, 4.3635891, 8.6896685, 6.6680496,
5.5445622, 8.9274641, 6.4394849, 5.5175364, 7.8629553, 8.4304969,
6.1402062), .Dim = c(3L, 6L), .Dimnames = list(c("FAM174B", "SV2B",
"RBPMS2"), c("b_1", "b_2", "b_3", "b_4", "b_5", "b_6")))

rcorr.observed<- structure(c(0.00309597514569759, -0.0526315793395042,                 -0.108359135687351,
NA, -0.0567595474421978, -0.0299277603626251, NA, NA, -0.116615064442158
), .Dim = c(3L, 3L))

library(Hmisc)
Pval_estim<-matrix(nrow = 3, ncol = 3)
number_of_permutations = 1000
diff.random = NULL
for(i in 1:nrow(a))
  {
  for(j in 1:nrow(b))
  {
    if(i>=j)#selecting only lower part of the symmetric matrix
      {
    combined<-as.numeric(t(c(a[i,], b[j,])))
for (k in 1 : number_of_permutations)
  {
    shuffled = sample (combined, length(combined))
    a.random = shuffled[1 : 6]
    b.random = shuffled[7 : length(combined)]
    diff.random[k] = rcorr(a.random, b.random, type="spearman")$r[1,2]
}
Pval_estim[i,j] = sum(abs(diff.random) >= abs(rcorr.observed[i,j])) /             number_of_permutations
}}
print(i)
}

Using apply and replicate, you can get a slight speedup (below). Setting a seed, you can check that it gives the same result as your version. In my benchmark test, it's about 10% faster. For further speedup, you could consider using clusterApply and parLapply from the parallel package.

# combining matrices into one to use apply
combinedMat <- cbind(a[rep(1:nrow(a), each=3), ], b[rep(1:nrow(b), times=3), ])
combinedMat <- cbind(combinedMat, obs = as.numeric(t(rcorr.observed)))
# using apply instead of loop
Pval_estim <- t(matrix(apply(combinedMat, 1, function(combined) {
  obs <- combined['obs']
  if (is.na(obs)) return(NA)
  combined <- as.numeric(combined[names(combined) != 'obs'])
  # using replicate instead of loop
  diff.random <- replicate(number_of_permutations,
  {
    shuffled = sample(combined)
    # you only use the correlation, so there is no need to use rcorr.
    diff.random = cor(shuffled[1 : 6],
                      shuffled[7 : length(combined)],
                      method="spearman")
  })
  sum(abs(diff.random) >= abs(obs)) / number_of_permutations
}), nrow = 3, ncol = 3))


Function to create an array of images I guess I made the mistake of creating UIImage *image1 to UIImage *image11. Can an one advise me on how to improve it?

+(NSArray *)stampImages{
        UIImage *image1 = [UIImage imageNamed:@"abcd.png"];
        UIImage *image2 = [UIImage imageNamed:@"fron.png"];
        UIImage *image3 = [UIImage imageNamed:@"amule.png"];
        UIImage *image4 = [UIImage imageNamed:@"dog2_trans.png"];
        UIImage *image5 = [UIImage imageNamed:@"dolphin.png"];
        UIImage *image6 = [UIImage imageNamed:@"hit.png"];
        UIImage *image7 = [UIImage imageNamed:@"abcd.png"];
        UIImage *image8 = [UIImage imageNamed:@"qw.png"];
        UIImage *image9 = [UIImage imageNamed:@"rewq.png"];
        UIImage *image10 = [UIImage imageNamed:@"rac.png"];
        UIImage *image11 = [UIImage imageNamed:@"gs.png"];
        UIImage *image12= [UIImage imageNamed:@"acb3.png"];
        NSMutableArray *stampList = [NSMutableArray arrayWithObjects:image1,image2,image3,image4,image5,image6,image7,image8,image9,image10,image11,image12,nil];
        return stampList;
    }

If you have the list of files you want to add to the array, then you can fast enumerate through them:

NSArray *fileArray; //List of file name here
NSMutableArray *stampList = [NSMutableArray array];
for (NSString *fileName in fileArray)
{
    [stampList addObject:[UIImage imageNamed:fileName]];
}


Optimizing Dijkstra implementation using PriorityQueue in Java I am trying to make Dijkstra implementation more efficient. Below is the code for class Node which implements Comparable so it can be used in PriorityQueue.

public class Node implements Comparable<Node> {

private final char label;
private int distanceFromSource;
private final Map<Node, Integer> neighbourList;

public Node(char label, int distanceFromSource) {
    this.label = label;
    this.distanceFromSource = distanceFromSource;
    this.neighbourList = new LinkedHashMap<>();
}

public void addNeighbourer(Node node, int distance) {
    neighbourList.put(node, distance);
}

public char getLabel() {
    return label;
}

public Map<Node, Integer> getNeighbourerList() {
    return neighbourList;
}

public int getDistanceFromSource() {
    return distanceFromSource;
}

public void setDistanceFromSource(int distanceFromSource) {
    this.distanceFromSource = distanceFromSource;
}

@Override
public int compareTo(Node o) {
    return Integer.compare(this.getDistanceFromSource(), o.getDistanceFromSource());
}

}

Adding Node to PriorityQueue and calling the Dijkstra method to find shortest distances:

PriorityQueue<Node> nodePriority = new PriorityQueue<>();
    nodePriority.add(nodeA);
    nodePriority.add(nodeB);
    nodePriority.add(nodeC);
    nodePriority.add(nodeD);
    nodePriority.add(nodeE);
    nodePriority.add(nodeF);
    Dijkistra dijkistra = new Dijkistra();
    dijkistra.findShortestDistances(nodePriority, 6);

Below is the algorithm for Dijkstra:

public void findShortestDistances(PriorityQueue<Node> nodePriority, int noOfVertices) {

    Set<Node> MST = new LinkedHashSet<>();
    while (MST.size() < noOfVertices) { // time complexity: O(n)

        Node minNode = nodePriority.poll();
        MST.add(minNode);

        /* list of nodes to be updated in nodePriority after iteration finishes. */
        List<Node> nodesToAdd = new ArrayList<>();
        Iterator<Node> nodePriorityIterator = nodePriority.iterator();
        while (nodePriorityIterator.hasNext()) {  // time complexity: O(n)

            Node node = nodePriorityIterator.next();
            if (minNode.getNeighbourerList().containsKey(node)) { // time complexity: O(log(n))

                int adjacentNodeDistanceFromSource = minNode.getDistanceFromSource() + minNode.getNeighbourerList().get(node);
                if (node.getDistanceFromSource() > adjacentNodeDistanceFromSource) {

                    Node updatedCopy = node; // original node copied.
                    updatedCopy.setDistanceFromSource(adjacentNodeDistanceFromSource); // node copy updated with new value.
                    nodesToAdd.add(updatedCopy); // updated node added to list.
                    nodePriorityIterator.remove();  // time complexity: O(logn(n))
                }
            }
        }
        nodePriority.addAll(nodesToAdd); // all updated nodes added to priority Queue.
    }
    /* display final shortest distances for all vertices from source */
    for (Node node : MST) {
        System.out.println(node.getLabel() + " : " + node.getDistanceFromSource());
    }
}

I think the time complexity is \$O(n^2)\$. How can we improve on it?

This works, but there's definitely room for improvement.

Node class

A Node has a distanceFromSource, which means it's tied to the dijkstra algorithm, and the nodes can't be reused in other runs of the algorithm. This is not great and results in a relatively awkward interface, but we'll leave it for now.

private final char label;
private int distanceFromSource;
private final Map<Node, Integer> neighbourList;

You made label and neighbourList final, and I always love to see that! label should probably be a String, though, to make it a little more usable. (If you want to go the extra mile, you could use generics, which will make it a lot easier for any library that wants to use it.) Also, I don't see why the distances need to be integer; Dijkstra's algorithm doesn't require it, and it might be a pretty limiting factor in some applications. Also, distanceFromSource should probably be tentativeDistanceFromSource. The Node should also have a boolean visited set initially to false.

this.neighbourList = new LinkedHashMap<>();

Nice use of the diamond, but why does neighborList need to be a LinkedHashMap? We really don't care about the order of neighborList at all, so it could just be a HashMap.

public void addNeighbourer(Node node, int distance)
public Map<Node, Integer> getNeighbourerList()

It might just be me, but misspellings bug the hell out of me. The word you're looking for is neighbour (neighbor in the US).

Algorithm

public void findShortestDistances(PriorityQueue<Node> nodePriority, int noOfVertices) {

This raises a lot of questions. Why isn't this static? The Dijkstra class seems to be empty except for this, so it should be fine being static. Why don't I get the shortest distances back? If I'm using this program, I probably want the result to be returned. If I want to print it to the console, I can do that myself. Why should I have to give you a PriorityQueue to start with, instead of just a starting node? What is noOfVertices, and why do I have to supply it? As a consumer of this program, I probably want a function signature that looks more like

public static int findShortestDistance(Node start, Node final)

or, if I want to find the distances to multiple nodes at the same time, it might look like

public static Map<Node, Integer> findShortestDistances(Node start, Set<Node> destinations)

where the returned map will have all the elements of destinations as its keys.

Set<Node> MST = new LinkedHashSet<>();

What's MST? Why does it need to be a LinkedHashSet instead of just a HashSet? Luckily we can actually get rid of MST by changing the signature.

// list of nodes to be updated in nodePriority after iteration finishes.
List<Node> nodesToAdd = new ArrayList<>();
Iterator<Node> nodePriorityIterator = nodePriority.iterator();
while (nodePriorityIterator.hasNext()) {  // time complexity: O(n)
    Node node = nodePriorityIterator.next();
    if (minNode.getNeighbourerList().containsKey(node)) { // time complexity: O(log(n))
        //...
    }
}
nodePriority.addAll(nodesToAdd); // all updated nodes added to priority Queue.

This is a major issue. You should not be iterating through all the other nodes in the list and testing if the other node is in this node's neighbor list. (Also, that's O(1), not O(n), to check if a key exists in a hashmap.) Instead, iterate through the neighborList, possibly testing to see if the node is visited yet.

    Node updatedCopy = node; // original node copied.
    updatedCopy.setDistanceFromSource(adjacentNodeDistanceFromSource); // node copy updated with new value.
    nodesToAdd.add(updatedCopy); // updated node added to list.
    nodePriorityIterator.remove();  // time complexity: O(logn(n))

Whoa! Node updatedCopy = node; does not copy the node! Java passes objects by pointer! Luckily, this still works. Also, removing the node isn't quite necessary.

Result

public static int findShortestDistance(Node from, Node to) {
    Queue<Node> toVisit = new PriorityQueue<>();
    toVisit.add(from); // We have to populate the queue at the start. Thanks to nclark for pointing this out to me.

    while (!toVisit.isEmpty()) {
        Node min = toVisit.remove();
        if (min == to) {
            return min.getDistanceFromSource();
        }
        if (min.isVisited()) {
            continue;
        }
        min.setVisited(true);
        for (Map.Entry<Node, Integer> neighborEntry : min.getNeighborList().entrySet()) {
            int adjacentDistance = min.getDistanceFromSource() + neighborEntry.getValue();
            Node neighbor = neighborEntry.getKey();
            if (neighbor.getDistanceFromSource > adjacentDistance && !neighbor.isVisited()) {
                neighbor.setDistanceFromSource(adjacentDistance);
                toVisit.add(neighbor);
            }
        }
    }

    throw new RuntimeException("'to' node unreachable");
}

Nodes will be duplicated in the queue, but that's not that bad.


Simple navbar in pure HTML5 and CSS3 With some effort I've managed to build a very simple (maybe too simple haha) navigation bar for a website.

Is it possible to make a transition on the dropwdown list from height:0 to some suitable height? I've tried and it seems not to be possible. No javascript for now

Any advice or extra tweak I could add? All is greatly welcome!

        /* reset */
        ul {
            list-style: none;
            margin: 0;
            padding: 0;

        }

        /* automatically take height of the elements */
        .main {
            background-color: brown;
            overflow: auto;
            /* automatically adjusts height to anchors */
        }

        .main__lis {
            margin-left: 20px;
            float: left;
            /* float the list items of the main ul */
        }

        a {
            display: block;
            padding: 10px;
            text-decoration: none;
        }

        .dropdown ul {
            width: 120px;
            text-align: left;
            position: absolute;
            background-color: pink;
            display: none;
            box-shadow: 0px 8px 16px 0px rgba(0, 0, 0, 0.2);
        }

        .dropdown:hover ul {
            display: block;
        }
<!DOCTYPE html>

    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>

Home

News

                Dropdown

link 1

link 2

link 3

You probably want to reset the margin and padding of li items, too.

Using float to layout elements horizontally is outdated. Using flexbox should be preferred nowadays. That would also make overflow: auto redundant.

Prefer a child combinator instead of a descendant combinator if possible: .dropdown > ul.

A dropdown on hover isn't usable on a touch screen.


Implementing movement in a Pacman game I am making a Pacman Player vs Player game in Java, and I am wondering if I am implementing movement in the game in a good manner. Anything that will reduce the code size or make the program faster is wanted.

Note that the game is not complete, and I have only worked on player one (Pacman). I have not started on player two (ghost) or the maze or pellets.

Movable Interface

public interface Movable {
void move();
}

Pacman / Player One Class

This class represents player one, or the Pacman character. It implements Movable.

@Override
public void move() {
    if (this.direction == Direction.UP) {
        y -= 5;
    } else if (this.direction == Direction.DOWN) {
        y += 5;
    } else if (this.direction == Direction.RIGHT) {
        x += 5;
    } else if (this.direction == Direction.LEFT) {
        x -= 5;
    }
    create();
}

Game Class

In this class, I make a global type of my Pacman class, and I instantiate it in the Game's initialize method.

Pacman pacman;

I also make a global array of my Movable interface with a size of one (for now) which will hold my pacman instance.

private Movable mover[] = new Movable[1];

Then:

@Override
public void actionPerformed(ActionEvent e) {

    if (running) {
        moveEntities();
    }

    this.repaint();
}

private void moveEntities() {

    initializeMovement();

    for (Movable m : mover) {
        m.move();
    }
}

private void initializeMovement() {
    mover[0] = pacman;
}

Initial thoughts are:

Why is move calling create?  I don't know what create does, but this seems like a strange way for move to work.
You're using 5 for all four directions, this seems like it should probably be a constant.
It's unclear how you're going to implement collision detection at the moment, but it's something to consider when defining the interface for moving items.

From your comments, it seems that create draws Pacman.  If this is the case, then I'd still say that you don't want to be calling it from within your move method.  You want to try to decouple your game mechanics + movement/collision logic from your drawing/rendering logic, they are different concerns and may well move at different speeds.  One of the things you've said that you are looking for is to improve the speed that your code runs at.  If you think about running games on different hardware, one of the things to consider is that you need to start thinking about using that hardware effectively.  To give a concrete example, if your current computer processes your move method 10 times a second, that's going to move your Pacman 50 units.  Another computer may only run it 5 (moving 25 units) or may run it 50 (moving 250 units) that's a lot of variability that's usually ironed by linking the distance moved to the amount of elapsed time, which may be detached from the render time.

I haven't read the whole thing (and it seems to be aimed at the mobile market), but this seems like a fairly good introduction to game loop mechanics.


Approximating sines and cosines using up to five terms of the Taylor series I have one programming question:

  The sine and cosine of \$x\$ can be computed as follows:

    \$\sin(x) = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \frac{x^9}{9!} - \dots\$

    \$\cos(x) = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \frac{x^8}{8!} - \dots\$

  Your task is to compute the sine and cosine for given values of \$x\$ (where \$x\$ is in radians) using the above series up to 5 terms.

  Input Format

  First line will contain \$N\$, the number of test cases. Next \$N\$ lines will contain the input values of \$x\$:

    \$1 \le N \le 50\$

    \$0 \lt x \lt 10\$

  Each value of \$x\$ can contain up to 2 places of decimal in radians.

  Output Format

  2 \$N\$ lines, corresponding to the \$N\$ input values of \$x\$.  For each input, you will output 2 lines. First line will be the sine and the second line will be the cosine of \$x\$.  An error margin of \$\pm\$0.001 will be tolerated while evaluating the answers.  Please round off your answer to 3 decimal places.

  Sample Input

5
2.83
3.24
0.99
2.74
5.04

  Sample Output [sic]

 0.309
-0.943
-0.089
-0.963
 0.836
 0.549
 0.392
-0.914
 0.195
 2.746

and what I have tried:

public class Trigonometric_Ratios
{
  int factorial(int number)
  {
    int result = 1;
    for (int i = 1; i <= number; i++)
    {
      result = result * i;
    }
    return result;
  }

  void calc(double x)
  {
    double sinx=0,cosx=0;

    int i,j = 0;

    int c;
    for(i=1;i<10;i+=2)
    {
      c=i;
      sinx += Math.pow(-1,j++)*Math.pow(x,i) / factorial(i);
      if(i>0)
      cosx+=Math.pow(-1,j)*Math.pow(x,c-1)/factorial(c-1);
    }
    sinx=Math.round( sinx * 1000.0 ) / 1000.0;

    cosx=-cosx;
    cosx=Math.round( cosx * 1000.0 ) / 1000.0;
    System.out.println(sinx+" \n"+(cosx));
  }

  public static void main(String [] args)
  {
    int n;
    Trigonometric_Ratios tr=new Trigonometric_Ratios();

    Scanner sc=new Scanner(System.in);

    n=sc.nextInt();

    double a[]=new double[n];
    for(int i=0;i<n;i++)
    {
      a[i]=sc.nextDouble();
    }

    for(int i=0;i<n;i++)
    {
      tr.calc(a[i]);
    }
  }
}

Please review my code.  In particular, I am concerned about performance, and would appreciate suggestions on reducing the time complexity.

Instead of computing Math.pow() from scratch, multiply the previous numerator by x2.  (I suspect that Math.pow() uses logarithms so that it can handle the general case.)  Also, instead of computing the factorial from scratch, multiply the previous denominator by the next two numbers.


Converting a 32bit number in a proprietary timestamp with PHP This is a copy of a posting I made on SO, it was suggested I post it here all I've changed from that post is I'm now doing the bitwise AND using a decimal number rather than using bindec("111") to create the mask. The output is identical.

I have a 32 bit number represented as a HEX string that I need to convert to a timestamp following these rules:

What I want to check is that I'm not doing something glaringly stupid? Does my conversion look sane given the timestamp specification?

I've put together the following code to do this. I know PHP isn't the best for this sort of work but it's part of a larger legacy application all written in PHP.

$t is taken from an XML file of readings, one every 5 mins.

    // convert the hex string to a string representation of the binary number
    // sprintf pads leading zeros, for debugging only
    $binStr = sprintf('%032s', base_convert($t, 16, 2));

    //get a decimal representation so we can use the bitwise operator on it
    $decimal = base_convert($t, 16, 10);

     // get the first 6 bits
    $min = $decimal & 63; // 111111 in binary

    // drop the first 8 bits then apply a mask to the next 5
    $hour = ($decimal >> 8) & 31; // 11111 in binary

    // drop the first 15 bits then apply a mask to the next 1
    $daylightSaving = ($decimal >> 15) & 1;

    // etc
    $day  = ($decimal >> 16) & 31; // 11111
    $yearLsb  = ($decimal >> 21) & 7; //111
    $month = ($decimal >> 24) & 15; //1111
    $yearMsb  = ($decimal >> 28) & 15; //1111

    Logger::debug(
        "Incoming timestamp " . $t . " \n" .
        " (as binary " . $binStr . ") converted to: \n" .
        " Day: " . $day . "\n" .
        " Month: " . $month . "\n" .
        " Year: " . $yearMsb . $yearLsb . "\n" .
        " Hour: " . $hour . "\n" .
        " Min: " . $min . "\n" .
        " Daylight saving: ". $daylightSaving
    );

The output for the last entry in the file is:

Incoming timestamp 2DAC1B0A
 (as binary 00101101101011000001101100001010) converted to
 Day: 12
 Month: 13
 Year: 25
 Hour: 27
 Min: 10
 Daylight saving: 0

I know the file was created at 11:25am on the 12th Nov 2013, the readings are for 11:10 to 11:25 with the last one in the file being the 11:10am one.

The mins match those in the file I get 10 through 25 in 5 min increments. The day is also accurate if I run it against other files.

There's a chance that the equipment manufacturer who wants us to purchase some expensive software to do this parsing has munged the timetamp specification but that being an option I've played with lots of possible combinations in that 32bit integer and I can't see how I can get all the numbers I require from the supplied timestamps.

Not being a PHP expert, but messing with bitwise operations a lot, I have some advice for you:

First, the specification for your operations should be embedded with the code as a comment. Having to look up a specification that may or may not be the same as the one you used when programming it, is not useful... and changing between screens/pages to inspect the code vs. the specification is also not much fun. Something like:

// Input data is 4 bytes with following bit-specification:
// Byte0  (least significant)
//     0-5 : minutes
//     6   : reserved
//     7   : valid
// Byte1
//     0-4 : hours
//    ........

This makes it easier to compare/validate your code.

My next suggestion is to shift the data as you pull values off... This way you don't need to do 'brain-mushing' thinking when doing the manipulation.

// get the first 6 bits
$min = $decimal & 63; // 111111 in binary
$decimal = $decimal >> 6; // get rid of those 6 bits,
                          // now we only need to worry about low bits.

Then, the next suggestion is to set up some 'constants' for your masks:

$mask6bits = (1 << 6) - 1; // 00111111 in binary.

Now, the example above becomes:

// get the first 6 bits
$min = $decimal & mask6bits;
$decimal = $decimal >> 6; // shift off minutes

Then, I recommend you process the fields you don't need, and it helps you keep track of the specification:

// get the first 6 bits
$min = $decimal & mask6bits;
$decimal = $decimal >> 6; // shift off minutes

$decimal = $decimal >> 1; // shift off reserved

$decimal = $decimal >> 1; // shift off valid

$hours = $decimal & mask5bits;
$decimal = $decimal >> 5; // shift off the hours.

Follow the same pattern for the other bits...

This is a relatively concise way to do things, actually, and you only need to keep one 'dimension' (the length of each data value) of the problem in your head, and you can ignore the offset.

This leads to fewer bugs, and better understanding and readability.

I cannot find a definitive reference whether PHP supports a definitive >>= assignment operator. If it does, the lines $decimal = $decimal >> 5 can be replaced with $decimal >>= 5


Dictionary of names and birthdays This code is to have a dictionary of names and birthdays.

It will ask who's birthday it is that you're looking for. Then if it is in the dictionary, it will print back what that birthday is. If not, it will ask if you want to add it then have you insert the birthday as the value and use the name that you input before as the key. Then finally print the full dictionary.

I am pretty new to coding in Python and feel like there is a better way to type this code. Was thinking I could use return but I'm still not quite sure what the difference between return and print is. Is there a way to make this shorter or more efficient?

birthdays = {'Jon': 'July 17', 'Shauna': 'Jan 27', 'Lynette': 'July 10'}

while True:
    print("Who's birthday is it that you are looking for? To cancel, press enter!")
    name = input()
    if name == '':
        break

    if name in birthdays:
        print(birthdays[name] + ' is the birthday of ' + name)
    else:
        print("I don't have that person's name in my archives. Would you like to add it? Press Y or N")
        answer = input()
        if answer == 'Y':
            new_name = name
            print("Please enter their birthday")
            new_birthday = input()
            birthdays[name] = new_birthday
            print('It has been added')
            print(new_name + "'s birthday has been added as " + new_birthday)
            print('Here is a list of birthdays you have saved...')
            print(birthdays)
        else:
            print('Alrighty Then')

return returns the value, in this case the dictionary birthdays, whereas print just prints the value to the terminal. Your printing might be improved by using f-strings. This is usually a bit easier than having to use "+" inside your print statements. So for example, instead of

print(new_name + "'s birthday has been added as " + new_birthday)

You could write:

print(f"{new_name}'s birthday has been added as {new_birthday}")

This combined with a generator could also make your dictionary printing a little neater:

print("\n".join([f"{name}'s birthday is {bday}" for name,bday in birthdays.items()]))

The generator creates a list of strings for each item in the birthdays dictionary, so in this case, it would generate the list ["Jon's birthday is July 17","Shauna's birthday is Jan 27", "Lynette's birthday is July 10"]. The join() function is used to combine each element of this list into a new string, separated by the newline character \n. So the final result would produce:

Jon's birthday is July 17
Shauna's birthday is Jan 27
Lynette's birthday is July 10

If you want to further extend this code, I'd recommend representing the birthday as a date object, from the Python built-in library datetime. Then you could also add the functionality of easily telling how many days until someone's birthday and other features like that.


Mapping values. Should a single use variable be declared as a variable at all? Where I have, let us say an object, that I will only use once, what is considered general best practice in terms of declaring it as var vs. simply putting the object directly into the method it will be used in? I'm thinking this is going to come down to "which do you think is more readable", but given my lack of experience thought I'd see if there was a consensus.
This came about when looking at the following code:
      var aiPersonalities = model.aiPersonalities();

      var newPersonalities = {
        qCasual: {
          ai_path: "/pa/q_casual",
          display_name: "!LOC:Q-Casual",
          metal_drain_check: 0.64,
          energy_drain_check: 0.77,
          metal_demand_check: 0.95,
          energy_demand_check: 0.92,
          micro_type: 0,
          go_for_the_kill: false,
          priority_scout_metal_spots: true,
          enable_commander_danger_responses: false,
          neural_data_mod: 2,
          adv_eco_mod: 0.5,
          adv_eco_mod_alone: 0,
          factory_build_delay_min: 0,
          factory_build_delay_max: 12,
          per_expansion_delay: 60,
          personality_tags: ["queller"],
          min_basic_fabbers: 10,
          min_advanced_fabbers: 3,
        },
        // imagine another 11 objects of the same size here
      };

      var baseline = aiPersonalities.Absurd;

      newPersonalities = _.mapValues(
        newPersonalities,
        function (personality, name) {
          var result = _.assign(_.clone(baseline), personality);
          result.name = name;
          return result;
        }
      );

      _.assign(aiPersonalities, newPersonalities);

      model.aiPersonalities.valueHasMutated();

This could be written in a way which removes aiPersonalities, baseline, and avoids newPersonalities referencing itself:
      var newPersonalities = _.mapValues(
        {
          qCasual: {
            ai_path: "/pa/q_casual",
            display_name: "!LOC:Q-Casual",
            metal_drain_check: 0.64,
            energy_drain_check: 0.77,
            metal_demand_check: 0.95,
            energy_demand_check: 0.92,
            micro_type: 0,
            go_for_the_kill: false,
            priority_scout_metal_spots: true,
            enable_commander_danger_responses: false,
            neural_data_mod: 2,
            adv_eco_mod: 0.5,
            adv_eco_mod_alone: 0,
            factory_build_delay_min: 0,
            factory_build_delay_max: 12,
            per_expansion_delay: 60,
            personality_tags: ["queller"],
            min_basic_fabbers: 10,
            min_advanced_fabbers: 3,
          },
        // imagine another 11 objects of the same size here
        },
        function (personality, name) {
          var result = _.assign(
            _.clone(model.aiPersonalities().Absurd),
            personality
          );
          result.name = name;
          return result;
        }
      );

      _.assign(model.aiPersonalities(), newPersonalities);

      model.aiPersonalities.valueHasMutated();

I'm just interested in how people would approach this. My instinct is that aiPersonalities and baseline could be ditched, per approach 2, but that keeping the initial declaration of the newPersonalities object may make it easier to see what the _.mapValues bit is doing.
There aren't any style guidelines or anything, this is a purely me project.

In this specific scenario, I would definitely go with your first approach. Putting a large amount of data right in the middle of your logic makes it extremely difficult to follow the logic.
To answer the general question of "should data associated with a specific function go inside its body or outside?" - there's never one right answer. I like to think of it as though there are various pressures going on. If your function is pretty cluttered but your module is pretty empty, then moving some stuff out of the function and into the module helps improve the readability of that function without sacrificing much. On the other hand, if there's already a whole lot of stuff in that module, and the function is really simple to follow then it might be worth it to move stuff into the function (or split the module up into multiple modules, if the containing folder isn't too cluttered). One important task of a programmer is to know when and how to shuffle clutter around to prevent any one spot from feeling too overwhelming.


Is this recursion a bad idea and does it make for clean code? This is a program I made to bounce the letter a across the screen.  I made a few others, but this one I made with a recursive bounce() method.  I know main() is a bit empty, but I intend to make an input menu that main refrences, so it seemed better to put the code in another method.

Is my code clean (probably far from it)?  Easy to read?  Am I overdoing the comments, or not specifing the code well enough?
Is it a bad idea using a recursive method for this as it has to keep memory for 80 recursions?  It seemed like a good idea, because I was condensing so much more code into a smaller space.

/**
 * This code is designed for use with CMD with an 80
 * ASCII character width space.
 * It adds and subtracts a space to a string and out prints
 * the line.
 * It uses recursion to create one full Right-Left cycle,
 * then uses an infinite while loop to repeat.
 */

class Wave8 {

  static String spaces = "";            // Holds the spaces
  static boolean direction = true;      // True is right, false is left

  // Bouncing loop
  public static void bounce() {

    if (spaces.length() == (80 - 1)) {        // Width minus the string after lead
      System.out.print(spaces + "a");

      direction = false;                      // Change direction
    }
    else
      System.out.println(spaces + "a");

    if (direction) {          // If going right
      spaces += " ";
      bounce();               // Recursion
    }

    if (!direction) {         // If going left
      spaces = spaces.substring(1);

      if (spaces.isEmpty()) {
        direction = true;
        return;
      }
      else System.out.println(spaces + "a");       // Normal routine

    }
  }

  public static void main(String args[]) {

    while (true) {
      bounce();
    }
  }
}

Also, is there a way to test for efficiency?  That would help greatly.

Before explaining why I think recursion might be a bad idea here, let me show you the solution I came up with.

class Wave8 {

  public static void bounce() {
    String spaces = "";
    for (int i=0; i<80; i++, spaces += " ")
    {
        System.out.println(spaces + "a");
    }
    for (int i=0; i<80; i++, spaces = spaces.substring(1))
    {
        System.out.println(spaces + "a");
    }
  }

  public static void main(String args[]) {
      bounce();
  }
}

The advantage of this solution against the recursive one :

clarity : one can clearly see what was intended.
termination : there is no doubt on the fact that this solution will eventually return
no use of object members : if I call bounce() twice, I expect it to behave the same way twice.
performance : I'd expect this solution to be much faster.

On the other hand, many functions are much better when written in a recursive way. This is the case when it's easy to see that we call the function on a "smaller" problem.


Exercise 1-22 from K and R: line folding I'm currently learning C with K&R, i'm right now in the exercise 1-22, but it's a little... hard to understand (at least for me). It says:

  Write a program to "fold" long input lines into two or more shorter lines after the last non-blank character that occurs before the n-th column of input. Make sure your program does something intelligent with very long line, and if there are no blanks or tabs before the specified column.

I've done this:

#include <stdio.h>

void seccionar(char to[], char from[])
{
     int a = 0,b = 0, i = 0;
     int max = 0;

     while(from[i] != '\0'){
                   if(max <= 80)
                          to[a] = from[i];
                   if(max == 80){
                          if(to[a] == ' ')
                          to[a] = '\n';
                          else {
                               for(;to[a] != ' '; --a)
                                          ++b;
                               to[a] = '\n';
                               max = 0;
                               a = a + b;}
                               b = 0;
                               }
                   ++a;
                   ++i;
                   ++max;}
     to[a] = '\0';
}
int getline(char s[])
{
    int c, i;

    for(i=0; (c=getchar()) != EOF; ++i){
             s[i] = c;
             if(c == '\n')
             break;}
    ++i;
    s[i] = '\0';
    return i;
}
int main()
{
    char from[10];
    char to[10];
    while(getline(from) > 1){
                       seccionar(to, from);
                       printf("%s", to);}
    return 0;
}

Does this matches with the exercise?

Potential Buffer Overflows

You've defined from and to to hold only 10 characters apiece, but none of the code actually enforces that, and it appears that you plan on them holding 80 characters or so. You should probably pass the array size to getline, for example, so that it can stop reading either when it reaches a new-line or when it runs out of space in the destination buffer.

Formatting

Your indentation is inconsistent and in places seems rather excessive.

Variable names

Many of your variable names could use some work. Names like a, b and max (that doesn't seem to hold a maximum) could be replaced with much more meaningful names.

Inefficiency

Depending on your viewpoint, there's a fair argument to be made that your code is less efficient than there's any real need for. In particular, it works by reading data into one buffer, then copying all that data to another buffer.

I'd consider a strategy something on this general order:

Read in a line
If it's shorter than the maximum, print it out and go back to 1
Starting from line[max_width], search backward in the string to find a space.
Change that space to a new-line.
Repeat from 2, using the string following the newline you just inserted.


If a regex match is found assign it to a variable I am searching a string for a pattern that matches Material=. Some examples are Material=ABC123,Color=444555, Material=332212,Color=192929
I am new to C# and I learned about capture groups but I am wondering if its possible to do it in a cleaner way?

var pattern = new Regex("(?<label>Material)=(?<value>[^,]+)");
Match match = pattern.Match(Row2.Attributes);
var materialCode = (match.Success) ? match.Groups["value"].Value : "NA";

Edit:

I store materialCode into a database so it can't be null. If a value isn't found it has to be "NA". Also there are lots of combos which is why I specify I need whatever value after the = but before the , in the regex

Do not set the materialCode to another string. I am not sure, but NA might also be a valid choice for Material=<value>. Instead, just set it to null.

As for the pattern itself, instead of searching for [^,] (anything except ,), you should look for only the valid values. Based on the given examples, I'd assume that only alphanumericals are accepted. If there is a limit on the length, then you should specify that as well.

Since, you are only looking for values assigned to Material property; no need to store the word Material as a matched-group result.

For eg.

Material=(?<value>[A-Z\d]{6})


Templated Tokenizer Functions I wanted to be able to tokenize a few different containers so I created a generic way to do it. I originally wrote this in Visual Studio 2012, but I had to modify it to get it to compile on Ideone.

Here is a brief description of my tokenizer functions:

Tokenize (): Tokenizes a container based on a single delimiter.

TokenizeIf (): Tokenizes a container based on a single delimiter and a condition.

BackInsertTokenize () and BackInsertTokenizeIf (): Wrapper for containers that can use a std::back_inserter iterator.

A specialized BackInsertTokenize () for character types (char, wchar, etc).

Here are my generic tokenizer functions:

#include <algorithm>
#include <iterator>
#include <string>
#include <utility>

template <typename Token, typename Iter, typename OutIter, typename Condition>
auto TokenizeIf (Iter begin, Iter end, OutIter out, typename std::iterator_traits <Iter>::value_type delimiter, Condition condition) -> OutIter
{
    if (begin == end) {
        return out ;
    }

    auto current = begin ;
    auto next = begin ;

    do {
        next = std::find (current, end, delimiter) ;
        Token token (current, next) ;

        if (condition (token) == true) {
            *out++ = std::move (token) ;
        }
        current = next ;

    } while (next != end && ++current != end) ;

    if (next != end) {
        Token token ;
        if (condition (token) == true) {
            *out++ = std::move (token) ;
        }
    }

    return out ;
};

template <typename Token, typename Iter, typename OutIter>
auto Tokenize (Iter begin, Iter end, OutIter out, typename std::iterator_traits <Iter>::value_type delimiter) -> OutIter
{
    if (begin == end) {
        return out ;
    }

    auto current = begin ;
    auto next = begin ;

    do {
        next = std::find (current, end, delimiter) ;
        *out++ = Token (current, next) ;
        current = next ;

    } while (next != end && ++current != end) ;

    if (next != end) {
        *out++ = Token () ;
    }

    return out ;
};

template <class ContainerOut, class ContainerIn, class Condition>
auto BackInsertTokenizeIf (ContainerIn const &in, typename ContainerIn::value_type delimiter, Condition condition) -> ContainerOut
{
    typedef typename ContainerOut::value_type Token ;

    ContainerOut out ;
    TokenizeIf <Token> (std::begin (in), std::end (in), std::back_inserter (out), delimiter, condition) ;
    return out ;
}

template <class ContainerOut, class ContainerIn>
auto BackInsertTokenize (ContainerIn const &in, typename ContainerIn::value_type delimiter) -> ContainerOut
{
    typedef typename ContainerOut::value_type Token ;

    ContainerOut out ;
    Tokenize <Token> (std::begin (in), std::end (in), std::back_inserter (out), delimiter) ;
    return out ;
}

template <class ContainerOut, class CharT>
auto BackInsertTokenize (const CharT *in, CharT delimiter) -> ContainerOut
{
    typedef typename ContainerOut::value_type Token ;

    ContainerOut out ;
    Tokenize <Token> (in, in + std::char_traits<CharT>::length (in), std::back_inserter (out), delimiter) ;
    return out ;
}

These are the test cases that I was interested in:

#include <vector>

int main ()
{
    std::string const s1 = ",hello,5,cat,192.3," ;
    auto const t1 = BackInsertTokenize <std::vector <std::string>> (s1, ',') ;

    std::vector <char> v1 = {'S', '1', '\0', 'S', '2', 'I', 'N', '\0', 'S', '3', '\0', '\0'} ;
    auto const t2 = BackInsertTokenizeIf <std::vector <std::string>> (v1, '\0', [] (const std::string &s) {
        return !s.empty () ;
    }) ;

    auto const t3 = BackInsertTokenize <std::vector <std::string>> ("C:\\Some\\Path\\To\\Nowhere", '\\') ;

    return 0 ;
}

The code generally looks good to me.  It is clear, complete and working.  The naming and formatting are clear and consistent (although I prefer to read code that does not have the space before each statement-terminating semicolon) but I did see a few things that may help you improve your code.

Consider using {} style initializers

There are a few places where  a Token is constructed, such as this:

Token token (current, next_) ;

However, this might be misconstrued as a function call. Assuming that you're using C++11 or better, it may be worth considering using the {} style for the constructor:

Token token {current, next} ;

This can't be misconstrued as a function call and may be slightly less ambiguous.

Consider alternative usage

The code works well for the use cases you've said you're interested in addressing.  That's good, and it may be all you ever need, but when I first saw the code, I thought it might be useful to be able to use it like this:

std::string const s2 = "55,33,1,7,42";
auto const t4 = BackInsertTokenize <std::vector <int>> (s2, ',') ;

The intent was to create a vector of integers from the const string, but this code doesn't actually compile.  The problem is essentially this line:

*out++ = Token (current, next) ;

That works fine for any Token type that can be constructed from an iterator range like this, but not for a primitive type like int.  One way to address that might be to provide another template that additionally takes an operator to explicitly perform this conversion with the given types.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.


Is My Function to Find Triplets in Scala running in O(N^2) Given the classical problem to find triplets that sum to zero in an array. Is my Scala implementation correct and executed in O(N^2)? If yes, why? Can someone make a running time analysis.
What other ways could we solve this issue? With duplicated elements and not using the two pointer technique?
def tripletsFromArrayThatSumZero(input: Array[Int]): Array[Array[Int]] = {
    val target = 0 // the target is the number after the sum
    val sortedArray = input.sorted
    var resultsArrayOfTriplets = Array[Array[Int]]()

    for (i <- sortedArray.indices) {
      var j = i + 1
      var k = sortedArray.length - 1
      val twoSum = target - sortedArray(i)

      Breaks.breakable {
        while (j < sortedArray.length) {
          val sum = sortedArray(j) + sortedArray(k)
          if (k == j) Breaks.break()
          if (sum > twoSum) {
            k -= 1
          } else if (sum < twoSum) {
            j += 1
          } else if (sum == twoSum) {
            val triplet = Array(sortedArray(i), sortedArray(j), sortedArray(k) )
            resultsArrayOfTriplets = resultsArrayOfTriplets :+ triplet
            Breaks.break()
          }
        }
      }
    }
    resultsArrayOfTriplets
  }

I have a few issues with the posted code. We'll start with the trivial.
Code posted on Code Review should be complete. You forgot to include the necessary import to make this compile.
val target = 0 - I find this somewhat redundant. If target isn't zero then you also need to change the name of the method. On the other hand, we're not supposed to bury "magic numbers" in our code, so it's debatable.
But the real problem here is that you're writing imperative code in a functional language. You've written C code in Scala.
Imperative : Create an empty mutable collection. Run code with a side-effect of filling the collection. Return the collection.
Functional : Start with one or more populated collections. Filter, collect, and transform them, without mutation, into the resulting collection.
Here's an implementation that's similar in that the i index starts at zero, the j index starts at i+1, and the k index searches the remaining space for the result.
def zeroSumTriples(input: Array[Int]): Array[Array[Int]] = {
  val sortedInput = input.sorted

  sortedInput.takeWhile(_ < 1).indices.flatMap{ i =>
    (i+1).until(input.length-1).flatMap{ j =>
      val (a, b) = (sortedInput(i), sortedInput(j))
      Iterator.from(j+1).take(input.length-j-1)
              .dropWhile(a + b + sortedInput(_) < 0)
              .takeWhile(a + b + sortedInput(_) == 0)
              .map(k => Array(a, b, sortedInput(k)))
    }
  }
}.toArray


Basic shell implementation Here is a small project to implement a basic shell. It is a personal ongoing project to keep system call usage fresh. It currently does background processes and some basic signal handling.

I am actually looking for code feedback in regards to professionalism. I want to know if my code is clear and easy to understand. I know my main function is currently doing too much and that I will handle in the short future.

/*
Description: This is a light implementation of a Linux shell
*/

#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/wait.h>

#define MAX_LEN 4096
#define MAX_ARGS 256

struct proc_st {
    int bg;
    int exec;
    int commc;
    int fd_out;
    int fd_in;
    pid_t pid;
    char pbuff[MAX_LEN];
    char *commv[];
};

/* function prototypes */
void error_msg(char *);
void sig_handler(int);
void comm_identi(struct proc_st *, char *);

int main()
{
    struct proc_st *proc;
    char buff[MAX_LEN];
    pid_t pid;
    int status;

    /* initialize signal handlers */
    signal(SIGINT, SIG_IGN);
    signal(SIGQUIT, SIG_IGN);
    signal(SIGCHLD, sig_handler);

    printf("[SHELL]> ");
    for (;;) {

        while (fgets(buff, MAX_LEN, stdin) != NULL) {

            proc = malloc(sizeof(struct proc_st) + MAX_ARGS);

            /*initialize to zero */
            memset(proc, 0, sizeof(struct proc_st));
            proc->exec = 1;
            comm_identi(proc, buff);

            if (proc->exec == 1) {
                if ((pid = fork()) < 0 ) {
                    printf("fork error");
                } else if (pid == 0) { /* child */
                    if (execvp(*(proc->commv),
                        proc->commv) < 0 )
                        error_msg("could not execute");
                    free(proc);
                }

                /* parent */
                if (proc->bg == 0) {
                    if ((pid = waitpid(pid, &status, 0))
                            < 0)
                        error_msg("waitpid error");
                } else
                    printf("PID %d %s\n", pid, proc->pbuff);
            }
            free(proc);
            printf("[SHELL]> ");
        }
    }
    exit(0);
}

void sig_handler(int signal)
{
    pid_t pid;

    while ((pid = waitpid(-1, NULL, WNOHANG | WUNTRACED)) > 0) {
        printf("Child Process [%d]: Terminated", (int)pid);
    }
    if (errno != ECHILD)
        error_msg("waitpid() error");
}

void error_msg(char * msg)
{
    fprintf(stderr, "%s: %s\n", msg, strerror(errno));
    exit(0);
}

void comm_identi(struct proc_st *proc, char *buffer)
{
    char *tmp;

    /* replace newline with null */
    if (buffer[strlen(buffer) - 1] == '\n')
        buffer[strlen(buffer) - 1] = 0;
    strncpy(proc->pbuff,buffer,MAX_LEN);

    tmp = strtok(buffer, " ");
    while (tmp != NULL) {
        proc->commv[(proc->commc)++] = tmp;
        tmp = strtok(NULL, " ");
    }

    proc->commv[proc->commc] = NULL;

    /* check for built-in functions */
    if (proc->commc >= 1) {
        if(!strcmp(proc->commv[0], "exit")) {
            free(proc);
            exit(EXIT_SUCCESS);
        }

        if(!strcmp(proc->commv[0], "cd")) {
            proc->exec = 0;
            if (chdir(proc->commv[1]) != 0)
                error_msg("chdir() error");
        }

        /* check if it is a background process */
        if (*proc->commv[(proc->commc) - 1] == '&') {
            proc->bg = 1;
            proc->commv[(proc->commc) - 1] = NULL;
        }
    }

    return;
}

This code and updates are available in the github repo.

Allocation and freeing

In the while loop of your infinite loop, you are allocating memory for proc only to be completely freeing it by the end of the loop. Why? Considering every loop you reset with memset, why not keep the same allocated memory for the entire time?

Your code would be much faster if you moved the allocation of proc out of both loops, and if you did not free the memory every iteration, too. Also, you seem to be freeing proc in a few other places in the loop; see if you can remove those, too.

Refactor built-in functions

Here you are checking for commands that require special attention:

if(!strcmp(proc->commv[0], "exit")) {
    free(proc);
    exit(EXIT_SUCCESS);
}

if(!strcmp(proc->commv[0], "cd")) {
    proc->exec = 0;
    if (chdir(proc->commv[1]) != 0)
        error_msg("chdir() error");
}

What if you need to add another command to this list for whatever reason? Now, you could just add another if, but then your code starts to look a little  more messy.

To make your code more flexible here, you could try splitting these built-in functions into a struct which stores the name of the built-in function and a pointer to a function to execute if this is come across.

Then, you could create a function that checks if the command entered is a built-in function. If it is, then the function can easily handle the situation using the built-in function's struct.

Here is a short snippet of what I mean:

struct builtin {
    char *name;
    function pointer;
} builtins = {
    "exit", builtin_exit,
    ...
};

Then, all you need is a function to check through builtins to see if the command entered is a built-in function.

From there, if you ever need to add another built-in function, you simply add another one to the array (and create its respective function), and you don't even have to touch the shell's main code.

Exit number

In your error_msg function, you have this:

exit(0);

Well, that doesn't make much sense; if there's an error, the code needs to return a non-zero number to indicate failure. Other than that, the environment in which this program was run will not be able to tell that there was an error.

const int or #define

#define MAX_LEN 4096
#define MAX_ARGS 256

It would be better to use a const int here because that will actually define a type for the variable, where #define simply sticks that literal string after the macro name into the code and leaves it up to the compiler to determine a type for it.


Given a word, find other words in an array with same length and same characters I tried solving the problem in the following manner; I am just a beginner and wanted to know my mistakes and a more efficient way with better time complexity (if any).

    public class d3 {
    public static void main(String[] args){
    String Search="loop";
    String[] letters = Search.split("") ;
    int counter;

    String[] words={"pole","pool","lopo","book","kobo"};

    for(int i=0;i<words.length;i++)
    {
        counter=0;
        String ssplit[] = words[i].split("");
        for(int j=0;j<words[i].length();j++)
        {

            if(letters.length==ssplit.length)
            {
            for(int k=0;k<letters.length;k++)
            {
                    if(letters[j].equals(ssplit[k]))
                        {counter++;
                        ssplit[k]="*";
                break;

                        }

            }
            if (counter == 4)
            {
                System.out.println(words[i]);

            }

        }
            }

    }

}
}

Whitespace is very important for readability. For posting to Stack Exchange sites I recommend replacing tabs with spaces, because otherwise the site does that for you and the tabstops might not match. Here, though, the whitespace is so crazy that I think you need to look at configuring your IDE to pretty-print the code. Reformatting so that I can understand the structure:

public class d3 {
    public static void main(String[] args){
        String Search="loop";
        String[] letters = Search.split("") ;
        int counter;

        String[] words={"pole","pool","lopo","book","kobo"};

        for(int i=0;i<words.length;i++)
        {
            counter=0;
            String ssplit[] = words[i].split("");
            for(int j=0;j<words[i].length();j++)
            {
                if(letters.length==ssplit.length)
                {
                    for(int k=0;k<letters.length;k++)
                    {
                        if(letters[j].equals(ssplit[k]))
                        {
                            counter++;
                            ssplit[k]="*";
                            break;
                        }
                    }
                    if (counter == 4)
                    {
                        System.out.println(words[i]);
                    }
                }
            }
        }
    }
}

Names

Java convention is that camel-case names which start with a capital letter are types (classes, interfaces, etc), so Search as the name of a variable is unexpected.

counter is not entirely uninformative, but a better name would tell me what it counts. Similarly, it would be helpful to distinguish which variables relate to the search query and which to the items searched. The best convention I've seen there is PHP's needle and haystack, so I would suggest needleLetters and haystackWords.

foreach statement

Instead of for(int i=0;i<words.length;i++) ... words[i] you can use for (String word : words) ... word. This removes a variable and simplifies the naming, making it easier to see what the code does.

Decomposing strings

String has a method toCharArray(). I think it would make more sense to use that than split("").

Don't put something in a loop which can go outside it

            for(int j=0;j<words[i].length();j++)
            {
                if(letters.length==ssplit.length)
                {
                    ...
                }
            }

could be rewritten

            if(letters.length==ssplit.length)
            {
                for(int j=0;j<ssplit.length;j++)
                {
                    ...
                }
            }

Executing the test once is more efficient, and it's also easier to understand because the maintainer doesn't have to reason about loop invariants to work out what might have changed the second time the test is executed.

Since there's nothing after this test in the loop body, an alternative would be

            if(letters.length!=ssplit.length)
            {
                continue;
            }

            for(int j=0;j<ssplit.length;j++)
            {
                ...
            }

Beware hard-coded constants

Why

                    if (counter == 4)
                    {
                        System.out.println(words[i]);
                    }

? That's a bug. The comparison should be with letters.length. Also, it would make more sense to move the test outside the loop over j.

Use advanced data structures

            for(int j=0;j<words[i].length();j++)
            {
                for(int k=0;k<letters.length;k++)
                {
                    if(letters[j].equals(ssplit[k]))
                    {
                        counter++;
                        ssplit[k]="*";
                        break;
                    }
                }
            }

takes time proportional to words[i].length() * letters.length. If you use java.util.HashMap<Character, Integer> to store a per-character count, you can generate a representation for each word in time proportional to the length of the word, and you can compare the representations of two words in time proportional to the length of each word. In this toy example it doesn't matter, but for real applications the difference between \$O(n^2)\$ and \$O(n)\$ can be the difference between a project being feasible and not. The first place to look for optimisations is always the algorithm.


Project Euler problem 86 taking a long time I'm trying to solve problem 86 in Project Euler. After some tinkering, I managed to unroll the DP solution into a loop. But still the solution takes >150s to complete. What can I do to improve the performance of this algorithm?

(defn- square [n]
  (* n n))

(defn- is-perfect-square? [n]
  (let [sq (int (Math/sqrt n))]
    (= n (* sq sq))))

;; See: https://math.stackexchange.com/a/1189884/7078 (Second case)
;; So lengths = [sqrt(l^2 + b^2 + h^2 + 2bh), sqrt(l^2 + b^2 + h^2 + 2lb), sqrt(l^2 + b^2 + h^2 + 2lh)]
;; Shortest length is the smallest of the above. == sqrt(l^2 + b^2 + h^2 + min(2bh, 2lb, 2lh))
(defn- shortest-cuboid-dist-has-int-length?
  ([a b c]
   (->> (min (* a b) (* b c) (* c a))
        (* 2)
        (+ (square a) (square b) (square c))
        (is-perfect-square?)))
  ([[a b c]]
   (shortest-cuboid-dist-has-int-length? a b c)))

;; if F(n) denotes number of integer shortest lengths for cuboids with dimensions equal to or less than (n,n,n),
;; F(i+1) = F(i) + int_lengths(cuboids with at least one side dimension of i+1)

(defn- get-int-dist-above [lim]
  (loop [dim 0 c 0 i 1 j 1]
    (cond (> c lim) dim
          (= i (inc dim)) (recur (inc dim) c 1 1)
          (= j (inc i)) (recur dim c (inc i) 1)
          :else (recur dim (if (shortest-cuboid-dist-has-int-length? dim i j) (inc c) c) i (inc j)))))

(defn problem-86 []
  (get-int-dist-above 1000000))

(time (problem-86))  ;; Takes 150s

Given: 1 ≤ a ≤ b ≤ c = M,

then, min(a*b, b*c, a*c) == a*b

This means, you can remove 2 multiplications and the min operation from shortest-cuboid-dist-has-int-length? as long as you pass your room’s length, width, and height in the proper order.