Damage function for a game For my game I have a function that resolves FireOrders between units. The function is being called a ton of times and it's only being extended from various classes.

I have this: doDamage() for a Particle-Parent, a Matter-Parent and so on (5 in total).

The functions are the same, except for a very little if/else part that splits up a number into two different numbers.

It is very annoying to me to have this "long" function in every weapon class and I would like to somehow outsource the actual damage-determination part, because basicly this is what's different for the weapon classes and the remaining function is entirely the same.

However, I'm unable to come up with a way to outsource this tiny element. I tried to write two functions (getArmourDamage() and getStructDamage()), but it is not working since both values depend on each other, hence a single function return value won't suffice.

function doDamage($fire){
 // this is being called in context Particle::doDamage, Matter::doDamage, Explosive::doDamage etc

    for ($i = 0; $i < $fire->shots; $i++){
        if ($fire->rolls[$i] <= $fire->req){
            $destroyed = false;
            $shielDmg = 0;
            $armourDmg = 0;
            $structDmg = 0;
            $totalDmg = $this->getDamage($fire) * $this->getDamageMod(); // INT

            $armour = $fire->target->getStructureById($fire->hitSection);
            $hitSystem = $fire->target->getHitSystem($fire);
            $remInt = $hitSystem->getRemainingIntegrity();
            $negation = $armour->getRemainingNegation($fire) * $hitSystem->getArmourMod(); // INT

             // VARIABLE PART
                if ($totalDmg <= $negation/2){
                    $armourDmg = ceil($totalDmg/2);
                }
                else {
                    $armourDmg = ceil(min($totalDmg, $negation));
                    $structDmg = ceil($totalDmg - $armourDmg);
                }
             // ENDS HERE

            if ($remInt - $structDmg < 1){
                $destroyed = true;
                $hitSystem->destroyed = true;
                Debug::log("overkill for: ".($structDmg - $remInt));
            }

            $dmg = new Damage(
                -1,
                $fire->id,
                $fire->gameid,
                $fire->targetid,
                $armour->id,
                $hitSystem->id,
                $fire->turn,
                $fire->rolls[$i],
                $fire->weapon->type,
                $totalDmg,
                $shielDmg,
                $structDmg,
                $armourDmg,
                0,
                $negation,
                $destroyed,
                "",
                1
            );
            $fire->damages[] = $dmg;
            $hitSystem->damages[] = $dmg;
            $armour->damages[] = $dmg;
            Debug::log("armour rem: ".$armour->getRemainingIntegrity()." / ".$armour->integrity.", now adding: ".$armourDmg);
        }
    }
    return true;
}

For reference, these are the various differences per class:

   particle
                if ($totalDmg <= $negation/2){
                    $armourDmg = ceil($totalDmg/2);
                }
                else {
                    $armourDmg = ceil(min($totalDmg, $negation));
                    $structDmg = ceil($totalDmg - $armourDmg);
                }

   matter
                $armourDmg = $negation / 2;
                $structDmg = $totalDmg - $armourDmg;

   ballistic
                $armourDmg = min($totalDmg, $negation *2);
                $structDmg = $totalDmg - $armourDmg;

Please see comment above about thinking about broader review. My guess is that you might have a flawed approach to how you are modelling real-world items in your application. For example, a particle/matter/explosive doesn't really "doDamage" right? It "attacks" or "fires" or whatever you might want to call it.

"Damage" as a concept results from what the properties of the attack and the properties of the thing attacked are right?   So why would you model "damage" as a method on the different attacker entities, when it truly is something that needs to be determined based on the properties of both the attack and the target. Putting the actual calculation in the attacker class would not seem to make sense when you think about it.

You might look through another review I gave where the poster was having a similar problem in modelling application entities to match real world behavior. I hope this may give some insight into how you should be thinking about writing your code.

That being said, if you aren't looking to potentially refactor your application, your problem should actually be easy to solve.  Just break that "variable" area of code out into it's own function:

So base class might look like:

function doDamage($fire) {
    // all your code common to every class in hierarchy

    // call method (overridden with specific logic in each inheriting class
    // possibly this method returns your Damage object
    $dmg = $this->calculateDamage($someParam, $someOtherParam, ...);

    // other code common to all classes in hierarchy
}

And you only override such code in inheriting classes if logic totally varies from that execution path.

Why does this method always return true? Is it really even meaningful to have a return from a method is the value is always the same?


Export data from Python to spreadsheet I have written the following code to export to data to a spreadsheet with this result:

Please let me know how to improve it.

import numpy as np
import xlwt #THIS MAY BE GOOD
#from pandas import DataFrame

amin =2
amax=10
da = 2
names = ['amin', 'amax', 'da']
values = [amin, amax, da]

fname='EXPORTexample.xls'; sheetname = 'sheet 1'

book = xlwt.Workbook()
sh = book.add_sheet(sheetname)

col=0;
# FIRST WRITE THE VARIABLES AND THEIR VALUES INTO XLSX.
for row, (name, value) in enumerate(zip(names, values)):
    sh.write(row, col, name);
    sh.write(row, col+1, value);

t2 = np.arange(0.0, 5.0, 1)
amat= np.arange(amin,amax,da)

fn=np.zeros((np.shape(t2)[0],1))

col=3;
#row_eps =0;
#row_Dt += row_eps;

for a in amat:
    fn = a*t2

    names = ['eps_dot', 'Delta_t']
    values=[a*1., a*1.]
    #write specific a conditions on every data curve/set
    for row, (name, value) in enumerate(zip(names, values)):
        sh.write(row, col, name);
        sh.write(row, col+1, value);

    #write names such as strain, stress, d11s, d_dot, d11
    occ_rows = len(names)#no.of occupied rows.
    names = ['strain', 'stress', 'd11s', 'd_dot', 'd11']
    for cols,name in enumerate(names):
        sh.write(occ_rows+1, col+cols, name)

    ## WRITE actual numbers
    for rows, (strain_i,stress_i, d11s_i, d_dot_i, d11_i) in enumerate(zip(fn, t2, fn, t2, fn)):

        sh.write(occ_rows+1+rows+1, col, strain_i)
        sh.write(occ_rows+1+rows+1, col+1, stress_i)
        sh.write(occ_rows+1+rows+1, col+2, d11s_i)
        sh.write(occ_rows+1+rows+1, col+3, d_dot_i)
        sh.write(occ_rows+1+rows+1, col+4, d11_i)

    col+=6 #incremening column value to avoid overwriting and related error

book.save(fname)

First you should clean up your code - add whitespace, remove unnecessary comments, don't use semicolons, store repeated computations in variables, move repeated code fragments into functions, etc.

Second, if at all possible give them more descriptive names - I have no idea what this is about.  A good way to do this is to figure out the different sections (you have them labelled with comments) and then turn each section into a well-named, small function. This way you can clearly document what each section does and why, without having to add comments that clutter everything up. Prefer expressing yourself in code over in comments whenever possible.  Some people even consider writing comments a shameful act - I don't personally go that far, but here are some good articles about it:

https://blog.codinghorror.com/coding-without-comments/
https://visualstudiomagazine.com/articles/2013/06/01/roc-rocks.aspx

Robert C Martin talks a lot about this - I'd highly recommend reading his work.

  Comments are, at best, a necessary evil, nothing to celebrate
  The proper use of comments is to compensate for our failure
  to express ourself through the code itself
  http://www.cvc.uab.es/shared/teach/a21291/temes/coding_style/slides/comments.pdf

Third, use the right data structure for the job. Anytime you have name-value pairs and you aren't using a dictionary you're probably doing something wrong.  Whenever you have a list but you never mutate it, you should make it a tuple.

Fourth, if you use the start keyword argument to enumerate you can get rid of a lot of extra code. You can then compress your data curves section pretty easily.

Once you've moved things into some nice clean functions, you can then put your runtime code into an if __name__ == '__main__' block.

Last, I'd make a wrapper that turns your workbook into a context manager. This way you can make sure that the workbook is saved, and it makes things quite a bit cleaner.

You might also want to consider adding support for command line arguments, making it easier to generate a lot of sheets like this that operate on different parameters.

I ended up with something like this

import numpy as np
import xlwt
import contextlib

def write_to_sheet(sheet, row, column, name, value):
    sheet.write(row, column, name)
    sheet.write(row, column + 1, value)

def write_variables(sheet, variables):
    write_dict(sheet, 0, variables)

def write_conditions(sheet, column, conditions):
    write_dict(sheet, column, conditions)

def write_dict(sheet, column, dict_):
    for row, (name, value) in enumerate(dict_.items()):
        write_to_sheet(sheet, row, column, name, value)

def write_data_curve(sheet, data_curve, start_row, start_column):
    for column, (header, data) in enumerate(data_curve.items(), start=start_column):
        sheet.write(start_row, column, header)
        for row, value in enumerate(data, start=start_row + 1):
            sheet.write(row, column, value)

def write_data_curves(sheet, amin, amax, da):
    t2 = np.arange(0.0, 5.0, 1)
    amat = np.arange(amin, amax, da)
    col = 3

    for a, fn in ((a, a * t2) for a in amat):
        conditions = {
            'eps_dot': a * 1.,
            'Delta_t': a * 1.
        }
        write_conditions(sheet, col, conditions)

        data_curve = {'strain': fn, 'stress': t2,
                      'd11s': fn, 'd_dot': t2,
                      'd11': fn}
        write_data_curve(sheet, data_curve, len(conditions) + 1, col)

        col += 6

@contextlib.contextmanager
def open_book(filename):
    workbook = xlwt.Workbook()
    yield workbook
    workbook.save(filename)

if __name__ == '__main__':
    amin = 2
    amax = 10
    da = 2

    variables = {
        'amin': amin,
        'amax': amax,
        'da': da
    }

    with open_book('EXPORTexample.xls') as book:
        sh = book.add_sheet('sheet 1')
        write_variables(sh, variables)
        write_data_curves(sh, amin, amax, da))


Generate n^2 x n^2 Sudoku in poly-time Introduction

I have created an algorithm that generates n! Sudoku Grids in poly-time.I verified the correctness of my grids with a SAT solver up to 50x50. I'm awaiting a review for improvements. It seems that it's in \$O(n^3)\$ time. I am saying valid complete Puzzles can be generated in poly-time, not solving arbitrary puzzles in poly-time.

Working Code

Here's a link to my code. It's working and input should be like a list [1,2,3,4,5,6,7,8,9]. Brackets needed for input.

Input should be like a list. [1,2,3....] and no repeating elements.

There is input because 9 x 9 is not the only valid Sudoku it can generate. It can generate 50 x 50, 12 x 12, 10 x 10

tup = input()[1:-1].split(',')

x = input('Enter mapping to generate valid Sudoku eg. 3 for 9 x 9')
e = input('Enter 9 for 9 x 9 ...12 for 12 x 12')
f = input('Enter 3 if its a 9 x 9 and corresponding for n^2 x n^2')

x = int(x)
e = int(e)
f = int(f)

squares = []

for index in range(len(tup)):
  tup.append(tup.pop(0))
  squares.append(tup.copy())

#Everything below here is just printing

for s in range(x):
  for d in range(0,e,f):
    for si in range(s,e,f):
      for li in range(d,d+f):
        print(squares[si][li], end = '')
    print('')

Conclusion

Side note: If you want to create 12 x 12 or any larger Sudoku's, you'll need to edit the input so that the values are readable (e.g. ['[01]','[02]',....]).

Larger Valid Grid

I was wondering if you can point out my mistakes in the code?

tup = input()[1:-1].split(',')

It's really bad style to require interactive input without the slightest hint about the expected format.

x = input('Enter mapping to generate valid Sudoku eg. 3 for 9 x 9')
e = input('Enter 9 for 9 x 9 ...12 for 12 x 12')
f = input('Enter 3 if its a 9 x 9 and corresponding for n^2 x n^2')

These variable names are horrible. Do not use single-letter variable names unless you are using the exact names as they appear in a mathematical paper. And in that case, always provide a comment that links to the paper.

Why and how did you choose the variable name x?
Why and how did you choose the variable name e?
Why and how did you choose the variable name e?
What is the difference between x and f? For a 9×9 sudoku, both should be 3.
Why do you make the user of the program enter the value anyway? If there's only one valid value, there is no reason to annoy the user with unnecessary questions.

Continuing with your code:

x = int(x)
e = int(e)
f = int(f)

squares = []

for index in range(len(tup)):
  tup.append(tup.pop(0))
  squares.append(tup.copy())

It's unexpected that the code modifies tup here. The code can be written in an alternative form that doesn't modify tup:

for i in range(len(tup)):
    squares.append(tup[i:] + tup[:i])

To give the readers of the code some hints about the structure, you should define separate functions for the different tasks. In this case, these are:

reading the parameters from the input
generating the square
printing the square

By doing this, it becomes immediately clear which parameters are needed for generating the square, and which parameters are only needed for printing it. For example:

def generate_square(symbols):
    square = []
    for i in range(len(symbols)):
        square.append(symbols[i:] + symbols[:i])
    return square

Or, a little shorter:

def generate_square(symbols):
    return [symbols[i:] + symbols[:i] for i in range(len(symbols))]

I did a test run of your program:

1,2,3,4,5,6,7,8,9
Enter mapping to generate valid Sudoku eg. 3 for 9 x 93
Enter 9 for 9 x 9 ...12 for 12 x 1211
Enter 3 if its a 9 x 9 and corresponding for n^2 x n^23
2345678Traceback (most recent call last):
  File "a.py", line 28, in <module>
    main()
  File "a.py", line 24, in main
    print(squares[si][li], end = '')
IndexError: list index out of range

Doing that I noticed:

if I hadn't read the code before, I would not know what to type in the first line
in the second line, in 9 x 93, it is not clearly visible what is the prompt and what is the input. The prompt should end with 3 for 9 x 9:.
there is no input validation. As I said before, if there is only one valid input, the program should not ask for it.
because of the missing input validation, the program crashes.

Next test run:

1,2,3,4,5,6,7,8,9
Enter mapping to generate valid Sudoku eg. 3 for 9 x 93
Enter 9 for 9 x 9 ...12 for 12 x 129
Enter 3 if its a 9 x 9 and corresponding for n^2 x n^23
2345678
5678234
8234567
3456782
6782345
2345678
4567823
7823456
2345678

The program outputs 7×9 digits. That's not a sudoku. There is a bug in the printing part.  This bug is so obvious that it makes your question off-topic on this site. This site is only for code that is regarded as working.


Number of Paths (BackTracking) in Java Illustration

  You're testing a new driverless car that is located at the Southwest
  (bottom-left) corner of an n×n grid. The car is supposed to get to the
  opposite, Northeast (top-right), corner of the grid. Given n, the size
  of the grid’s axes, write a function numOfPathsToDest that returns
  the number of the possible paths the driverless car can take.

  For convenience, let's represent every square in the grid as a pair
  (i,j). The first coordinate in the pair denotes the east-to-west axis,
  and the second coordinate denotes the south-to-north axis. The initial
  state of the car is (0,0), and the destination is (n-1,n-1).

  The car must abide by the following two rules: it cannot cross the
  diagonal border. In other words, in every step the position (i,j)
  needs to maintain i >= j. See the illustration above for n = 5. In
  every step, it may go one square North (up), or one square East
  (right), but not both. E.g. if the car is at (3,1), it may go to (3,2)
  or (4,1).

Example

input:  n = 4

output: 5 # since there are five possibilities:
          # “EEENNN”, “EENENN”, “ENEENN”, “ENENEN”, “EENNEN”,
          # where the 'E' character stands for moving one step
          # East, and the 'N' character stands for moving one step
          # North (so, for instance, the path sequence “EEENNN”
          # stands for the following steps that the car took:
          # East, East, East, North, North, North)

My approach:

import java.io.*;
import java.util.*;

class Solution {

  static int numOfPathsToDest(int n) {
    // your code goes here
    //n = 2
    int startX = 0;
    int startY = 0;

    int numPoss = numPaths(startX,startY,n);

    return numPoss;

  }

  static private int numPaths(int startX, int startY, int n )
  {
    int destX = n - 1;
    int destY = n - 1;
    int numPoss = 0;

    //Base case
    if((startX == destX) && (startY == destY ))
      numPoss++;

    //Recursive condition
    else
      {
        if( (startX >= startY) && (startX < n) && ( startY < n ))
        {
          //East
          numPoss += numPaths(startX+1, startY,n);

          //North
           numPoss +=  numPaths(startX,startY + 1, n);
        }

        //Time complexity: O(2^n) -> O(n^2) in memoization
       //Space complexity: O(n^2)
      //Bottom up approach: O(n) space complexity
      //Time complexity: O(n)
      }

    return numPoss;
  }

  public static void main(String[] args) {
    System.out.println(numOfPathsToDest(2));
  }

}

//n = 4
//#squares = 4 + 3 + 2 + 1

//#squares = n + n-1 + n-2 + ... 1 = n(n + 1)/2

//square 0 - eastx 4/ n - 1

//square (1,0): up - 1, east -  3/(n - 1)

//square (2,0): up - 2, east: 2/(n - 2)

//east + north : n
//

I have the following questions with respect to the code:

What can I further improve my code in terms of space and time complexity?
Is there any smarter approach to solve this question?
Does my code violate any of the coding conventions?
Are there any other ways that I can further optimize the code?

Reference

I have a feeling there is a direct way to compute this amount, but I am not really into all the mathematics, you could possibly look it up. I'll talk about your code as is:

You should really remove all the superfluous white space, it hampers readability.
In Java, opening braces are not on a new line.
private before static.
Do not save te result of your recursive function in a variable, you can return at once.
The problem states you move from (0, 0) to (n,n). If you model your code the other way around, you can simplify it quite a bit. No need to pass n to your recursive function for example, as you can simply compare with 0.
Try to always use braces, even if you only have one line inside the block, as for example with the if part in your recursive function. It helps prevent unnoticed bugs due to formatting, and helps ease up modifying it later on.
In the else block, you do not need to check if x and y are valid, if you check for 0 up front.
In the recursive function, if the initial if succeeds, the result will always be 1. So you can return at once, it makes it more readable. Return early is a good thing in my opinion. The variable can then be put inside the else, reducing the scope.
You mention memoization, yet you do not seem to be using it. If you take the example, and the paths taken there:

“EEENNN”

“EEN|ENN”
“EEN|NEN”

“ENE|NEN”
“ENE|ENN”

Note that EEN will bring you to the same spot as ENE. You can see that each of those share the same second parts as well. This is duplication which we can use to speed up the algorithm.

If you think about it, there are generally multiple ways to get to some point (x,y). If you think of this as the starting point, the possible paths to the destination will obviously be the same, no matter how you get there. So what you can do is create a lookup table for a calculated location, so you calculate each one only once. This will give you an extreme amount of speedup I would think, on problems with a big amount of possible paths. Which you will get to quickly, even for small values of n.


NodeJS static file HTTP server I wrote a NodeJS HTTP server specifically for serving static files. I didn't bother much about security since the server is going to be used locally in my Electron application.

function buildStaticServer() {
    const fs = require("fs");
    const urlModule = require("url");
    return require("http").createServer(function(req, res) {
        var parsedUrl = urlModule.parse(req.url, true);
        var completePath = __dirname + parsedUrl.pathname;
        console.log(completePath);
        fs.stat(completePath, function(err, statObj){
            //we first check if the pathName exists
            if(err){
                res.writeHead(404);
                return res.end("404 Directory not found");
            }
            if(statObj.isDirectory()){
                //if the pathname is a directory, we're gonna try to send the index.html in that directory
                fs.readFile(completePath + "/index.html", function(err, data){
                    if(err){
                        res.writeHead(404);
                        return res.end("404 File Corrupt or Not Found");
                    }
                    res.writeHead(200);
                    res.write(data);
                    return res.end();
                })
            }
            fs.readFile(completePath, function(err, data){
                if(err){
                    res.writeHead(404);
                    res.end("404 File Corrupt or Not Found");
                    return;
                }
                res.writeHead(200);
                res.write(data);
                return res.end();
            })
        });
    });
}
var staticServer = buildStaticServer().listen(9000);

There are more efficient ways to do this. Now you are buffering the whole file content into memory, when you perform fs.readFile(...). I recommend that you use a readStream, that for example using fs.createReadStream(<path>), pipe it into res. This way you will begin sending the file content earlier, and stop wasting your node processes memory. Also consider moving require to the top of your code, it is a bad practice to call require from function body.


Game of Life in Haskell I wondering what people think of this game of life. I don't think it is working properly, but I am interesting in what people think of the general design.

module GameOfLife where
import Data.List

--Our types
type Coord = (Int, Int)
origin = (0, 0)

--Think of an image more like an infinite manifold
type DiscreteImage a = (Coord -> a)

--Cat is our "out of bounds"
data GamePiece = Alive | Dead | Cat
    deriving(Show, Eq)

type GameBoard = DiscreteImage GamePiece

type TransitionRule = (GameBoard -> GamePiece)

under_population = make_population_transition Alive Dead (<2)
overcrowding     = make_population_transition Alive Dead (>3)
birth            = make_population_transition Dead Alive (==3)

--Order is not important. Only one transition applies per peice,
--the others operate like id
transition_rule :: TransitionRule
transition_rule image = foldl (\image f -> f image) image
    [
        under_population,
        overcrowding,
        birth
    ] origin

--return a new gameboard that applies the transition rule to every
--spot on the gameboard
step :: TransitionRule -> GameBoard -> GameBoard
step trans gb = trans . offset gb

--apply the tranisition rule n number of times
simulate :: Int -> TransitionRule -> GameBoard -> GameBoard
simulate count trans gb = foldl apply_step gb steps where
  steps = replicate count (step trans)
  apply_step gb s = s gb

--translate the image
offset :: DiscreteImage a -> Coord -> Coord -> a
offset image (offsetX, offsetY) (x, y) = image (offsetX + x, offsetY + y)

--make a square of coords
square_coords :: Int -> [Coord]
square_coords radius = [(x, y) | x <- diameter_list, y <- diameter_list] where
        diameter_list = [(negate radius) .. radius]

--return a neighborhood with the center missing
punctured_neighborhood :: Int -> DiscreteImage a -> [a]
punctured_neighborhood size image = map image $ filter (not . (==origin)) $ square_coords size

--a little test
main = do
    let (width, height) = get_bounds test_list
    let board1 = simulate 1 transition_rule test_board
    putStr $ unlines [ unwords [ ppr_peice $ board1 (x, y) | x <- [0..(width -1)]] |
                y <- [0..(height - 1)]]

test_list =
    [
        [Alive, Dead, Alive, Dead],
        [Alive, Dead, Dead, Alive],
        [Dead, Alive, Dead, Alive],
        [Dead, Alive, Alive, Alive]
    ]

test_board = image_from_lists test_list Cat

--helpers
population_count = length . filter is_Alive . punctured_neighborhood 1

--does nothing if the origin peice /= from, otherwise test for replacement
make_population_transition from to condition image | image origin == from =
    if (condition . population_count) image
            then replace image origin to
            else image
make_population_transition from to test image | otherwise = image

replace image coord_to_replace value coord = if coord_to_replace == coord
                                                 then value
                                                 else image coord

bi f g h x = f x `h` g x

is_Alive Alive = True
is_Alive _ = False

from_Bool True = Alive
from_Bool False = Dead

image_from_lists xs default_value coord@(x, y) = if is_in_bounds1 coord
    then (xs !! x) !! y
    else default_value where
      bounds = get_bounds xs
      is_in_bounds1   = is_in_bounds bounds

get_bounds xs = if null xs
    then (0, 0)
    else (length xs, length $ head xs)

is_in_bounds (xb, yb) (x, y) = (y < yb && y > -1) && (x < xb && x > -1)

ppr_peice Dead = "O"
ppr_peice Alive = "X"
ppr_peice Cat = "C"

Refactor's answer is excellent and captures most points. One thing in your code which sticks out is the overuse of if. E.g. consider

get_bounds xs = if null xs
    then (0, 0)
    else (length xs, length $ head xs)

I think

getBounds [] = (0,0)
getBounds xs = (length xs, length $ head xs)

is much clearer. Or this, which looks really strange:

make_population_transition from to condition image | image origin == from =
    if (condition . population_count) image
            then replace image origin to
            else image
make_population_transition from to test image | otherwise = image

You should write

make_population_transition from to condition image
     | image origin == from &&
       (condition . population_count) image = replace image origin to
     | otherwise = image


Check if a linked list is a palindrome in Scala The problem: Palindrome: Implement a function to check if a linked
  list is a palindrome

If it's a palindrome, the list must be the same backwards and forwards

Below is the code I wrote:

  def isPalindrome[A](list:List[A]):Boolean= (list.head, list.last)match{
    case (a,b) if a==b&&list.size>2 => isPalindrome[A](list.tail.dropRight(1))
    case (a,b) if a==b&&list.size<=2 => true
    case (a,b) if a!=b =>false
  }

May I know is there any way to improve it?

What you do is very inefficient. You check if the elements of the list are similar from the outside in, and that too utilising both very unintuitive pattern matching and guard clauses.

Note: You do not need to specify the type parameter A in the recursive call to isPalindrome(), as the compiler can infer that.

Your code, on simple singly linked lists, is O(n2), thanks to the repeated O(n) calls to list.last. The code that I explain and provide below runs in O(n), as reversing a list is O(n) and subsequently checking for equality is also O(n).

What is the definition of a palindrome?

While what you have mentioned is absolutely correct, there's an easier way to think about it.

A sequence is a palindrome whenever it is equal in every way to a sequence that contains the elements of the first sequence in reverse order.

That is, a list is a palindrome if and only if it is equal to its reverse.

I think that as your code already uses enough library functions, why not try this:

def isPalindrome[A](list: List[A]) = list == list.reverse

Simple, succinct, and to the point.

I'm absolutely sure your code is overcomplicated for its intended purpose, and functional programming is not just about pattern matching and recursion, it's about being able to create greater functionality from pre-existing functions.


Collecting magical berries Here is the link of the problem for which I need your help.

I came up with solution and it is working fine for all cases, but it takes more time. I need your help in reducing the runtime of code. I unable to optimised it more.

#include <iostream>
#include <string>
using namespace std;

long nChoosek( unsigned n, unsigned k )
{
    if (k > n)
        return 0;
    if (k * 2 > n)
        k = n-k;
    if (k == 0)
        return 1;
    long result = n, temp;
    for( int i = 2; i <= k; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}

int main()
{
    int n,q,i,j,left,right;
    cin>>n;
    int arr[n];
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    cin>>q;
    string s;
    while(q--)
    {
        int b=0,r,q,re;
        long res=1;
        cin>>s >>left >>right;
        if(s=="change")
        {
            arr[left-1]=right;
        }
        else
        {
            for(i=left-1;i<right;i++)
            {
                b+=arr[i];
            }
            r=(right-left+1);
            q=(b/r);
            re=(b%r);
            res*=nChoosek(r,re);
            for(i=0;i<re;i++)
            {
                res*=nChoosek((b-(i*(q+1))),(q+1));
            }
            i=0;
            while((r-re-i) > 1)
            {
                res*=nChoosek(((r-re-i)*q),q);
                i++;
            }
                            res%=3046201;
            cout<<res<<endl;
        }
    }
    return 0;
}

I also tried to replace the function nChoosek

long nChoosek( unsigned n, unsigned k )
{
    if (k > n)
        return 0;
    if (k * 2 > n)
        k = n-k;
    if (k == 0)
        return 1;
    long result = n, temp;
    for( int i = 2; i <= k; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}

By new recursive function ncr but no change in result:

long ncr(int n,int r)
{
    if((r==0)||(n==r))
        return 1;
    else
        return (ncr(n-1,r-1)+ncr(n-1,r));
}

No optimisation so far but a few comments to make your code easier to read/improve :

1 Don't do "using namespace std;"

2 Give your variables meaningful names.

3 Declare your variables in the smallest possible scope. Also, you should declare and define in the same times when it's possible. That would make things much easier (such as int res = nChoosek(r,re); instead of res*=nChoosek(r,re);).

4 Be consistent. You use for(i=0;i<re;i++) {foo;} and then, a few lines later i=0; while((r-re-i) > 1){foo; i++;}. Using another for loop would have have been a better option : for (i=0; i<r-re-1; i++) {foo;}

5 Enable the warnings in your compiler. A few weird things such as the useless statement in for(i-0;i<n;i++) should be detected.

6 Add a comment about the algorithm you've used.

Once this is done, we'll be in better conditions to start thinking about optimisations.


2D counterpart of std::array in C++17 I implemented a 2D counterpart of std::array named array2d in C++17. It is an aggregate like std::array, and provides similar interface. The goal is that if you know how to use std::array, then you will find yourself at home using array2d. Any comments are welcome :) For better viewing experience with highlighting, you can refer to this GitHub page.

#include <cstddef>
#include <array>
#include <iterator>

template <typename T, std::size_t N0, std::size_t N1>
struct array2d {
  using row_t = std::array<T, N1>;
  inline static constexpr std::array sizes{ N0, N1 };

  static constexpr std::size_t size() noexcept { return N0 * N1; }
  static constexpr bool empty() noexcept { return !size(); }

  T& at(std::size_t i, std::size_t j) { return data_.at(i).at(j); }
  const T& at(std::size_t i, std::size_t j) const { return data_.at(i).at(j); }

  row_t& operator[](std::size_t i) noexcept { return data_[i]; }
  const row_t& operator[](std::size_t i) const noexcept { return data_[i]; }

  T& front() { return data_.front().front(); }
  const T& front() const { return data_.front().front(); }

  T& back() { return data_.back().back(); }
  const T& back() const { return data_.back().back(); }

  T* data() noexcept { return data_.data()->data(); }
  const T* data() const noexcept { return data_.data()->data(); }

  T* begin() noexcept { return data(); }
  const T* begin() const noexcept { return data(); }

  T* end() noexcept { return data() + size(); }
  const T* end() const noexcept { return data() + size(); }

  auto rbegin() noexcept { return std::make_reverse_iterator(end()); }
  auto rbegin() const noexcept { return std::make_reverse_iterator(end()); }

  auto rend() noexcept { return std::make_reverse_iterator(begin()); }
  auto rend() const noexcept { return std::make_reverse_iterator(begin()); }

  void fill(const T& v) {
    for (auto& row : data_) {
      row.fill(v);
    }
  }

  friend void swap(array2d& a, array2d& b) { a.data_.swap(b.data_); }

  std::array<row_t, N0> data_;
};

Let me collect a couple of thoughts here.

Aggregate initialization currently works like this:

array2d<int, 2, 2> a{{1, 2, 3, 4}};

but wouldn't it be favorable to allow for

array2d<int, 2, 2> a{{1, 2}, {3, 4}};

std::array::at performs bound checking and throws upon an out of bounds index. When your intention is to stick with the std::array interface, you should do the same.
If you want the container to be standard-compliant, there are some type aliases missing and maybe more. In particular, there are no cbegin(), cend(), crbegin(), crend() member functions. Is this intended?
You implicitly use row-major order. Are you sure everyone expects this? Users familiar with Eigen and their fixed size matrices might at least want to customize row-/column-major ordering, e.g. Eigen::Matrix<int, 2, 2, Eigen::ColMajor> m;
A range based for loop will considerably differ from a manual loop over rows and columns. Example:

// Loop over elements, transposed access. Requires nested loop.
for (std::size_t i = 0; i < 2; ++i)
   for (std::size_t j = 0; j < 2; ++j)
      std::cout << a[j][i] << "\n";

// Loop over elements, tranposed access impossible. Only one loop.
for (const auto& i : d)
    std::cout << i << "\n";

This is slightly unintuitive. Shouldn't the range based for loop require a nested loop as well?
The static data member sizes is not used anywhere.

Getting a two-dimensional array to work is not that much of an effort. Getting the semantics right is hard. Sticking to the std::array interface is a good goal when ease of use is intended for those familiar with the std::array template. But the additional dimension pulls in requirements that can't be tackled with the concepts of std::array. I would recommend having a look at established linear algebra libraries and their fixed size matrices. Also, the mdspan proposal for a multi-dimensional view on array types might be a good read.


Project Euler #1 in Ruby with duration I have done #1 of Project Euler's in Ruby. Using two different approaches. One uses set, another uses reduce.

require 'set'

start = Time.now

s1 = Set.new (1..1000/3.floor).map { |x| 3 * x }
s2 = Set.new (1..1000/5.floor).map { |x| 5 * x }
sum = s1.merge(s2).to_a.inject(:+)

duration = Time.now - start

puts "Sum: #{sum}, time elapsed #{duration} s"

Second method

start = Time.now
sum = (1..1000).select{ |x| x % 3 == 0 || x % 5 == 0 }.reduce(:+)
duration = Time.now - start

The second method consistently performs better than first method:

method 1: time elapsed 0.000364 s

method 2: time elapsed 0.000198 s

I wonder if it is a correct way to time how long the process takes. And whether it is considered to be performant. Also curious how other languages performs compares to this two algo. Any advice are welcomed~

Performing benchmarks with such small values is pretty much meaningless, you will usually be concerned with larger values. And this is how you  tipically compare the time performance of different snippets:

require 'benchmark'
require 'set'

n = 1_000_000
Benchmark.bm do |b|
  b.report("sets") do
    s1 = Set.new (1..n/3.floor).map { |x| 3 * x }
    s2 = Set.new (1..n/5.floor).map { |x| 5 * x }
    sum = s1.merge(s2).inject(0, :+)
  end

  b.report("select") do
    sum = (1..n).select { |x| x % 3 == 0 || x % 5 == 0 }.reduce(0, :+)
  end
end

Output:

         user     system      total        real
sets    0.550000   0.020000   0.570000 (  0.580492)
select  0.200000   0.000000   0.200000 (  0.207238)


Preparing and executing MySQL SELECT query from parameters I am trying to make a function for Select statements. It will give result based from the parameters passed. I tried using it and it gives the results I am expecting.

I know that it is still unpolished but I would like to know what are the critical things in it that should be fixed or improved so that it would be ready for usage.

Below is the parameter passed:

 $parameters = array(
    'select' => 'user_id, username, password',
    'type' => 'i',
    'from' => 'users',
    'where_column' => 'user_id',
    'where_row' => '4'
);

And here is the function:

function select_query($parameter){
    require('database.php');

    $select = $parameter['select'];
    $type = $parameter['type'];
    $from = $parameter['from'];

    $columns = '';
    $column_array = explode(', ', $select);
    foreach ($column_array as $value) {
        $columns .= '$'. $value .', ';
    }

    //prepares the WHERE section of the SQL statement if the WHERE parameter exist
    $where = '';
    $wc = '';
    $wr = '';

    if(isset($parameter['where_column']) && isset($parameter['where_row'])){
        $wc = $parameter['where_column'];
        $wr = $parameter['where_row'];

        $where = " WHERE $wc = ?";
    }

    /* create a prepared statement */
    if ($stmt = $conn->prepare("SELECT $select FROM $from". $where)) {

        if($where != ''){
            /* bind parameters for markers */
            $stmt->bind_param($type, $wr);
        }

        /* execute query *Returns TRUE on success or FALSE on failure. * */
        $stmt->execute();

        /* bind result variables *Returns a resultset or FALSE on failure.* */
        $res = $stmt->get_result();

        /* fetch value */
        if($res->num_rows > 0){
            while($row = $res->fetch_assoc()){ // fetch_assoc *returns NULL if there are no more rows in resultset.*
                $results[] = $row;
            }
            return $results;
        }else{
            return false;
        }

        /* close statement */
        $stmt->close();
    }

    /* close connection */
    $conn->close();
}

Right off the bat, there are a couple of things about your code that make me feel uneasy. I'll start by running through your code, almost line by line, explaining what I feel could be done to improve on what you have right now:

function select_query($parameter){
    require('database.php');

    $select = $parameter['select'];
    $type = $parameter['type'];
    $from = $parameter['from'];

For starters, you declare a function, that takes just one single argument. What type the function expects is an unknown, unless you actually bother to check the code of the function itself. $parameter (not the best name for the argument, IMHO), is expected to be an array, so your function signature should reflect that:

function selectQuery(array $parameter)
{
}

That would tell anyone who wants to use your function that they need to pass an array, not a string or object. If they pass anything else, they'll get a fatal error.

Next up, your function starts by require-ing a file. Not require_once, or checking if the file has already been processed by PHP, it just requires it. The result will probably be a lot of disk IO (which is bad for performance), and a function with an external dependency. Suppose someone opened the database.php file, and decided to change a thing or two. The variables declared within that file might change names, and you're left with a function that doesn't work anymore, for no apparent reason. To me, it seems like all you really need from that database.php file, is a mysqli connection object (or PDO, but since you've tagged your question mysqli, I'm assuming that that's what $conn is).

A far more common (and all-round better) way to obtain a DB connection would be to have the caller pass the connection of their choice to your function, again, as an argument. Here, you can use type-hints, too, to ensure the argument is indeed a mysqli instance/resource:

function selectQuery(mysqli $conn, array $parameter)
{}

That way, the caller can choose what DB should be used to query, what user, and -crucially- the caller can decide to re-use the connection for other tasks (other queries), and your function is no longer responsable for closing the connection, that falls to the caller.

The last thing about this piece of code that I'd change is this:

    $select = $parameter['select'];
    $type = $parameter['type'];
    $from = $parameter['from'];

Yes, using type-hints, you can ensure that the caller can only pass an array to your function, but an array is actually a rather vague thing, especially in PHP. Consider this:

function needsArray(array $argument)
{
    return $argument['total'] - $argument['costs'];
}

Now, these attempts at calling this function will fail:

needsArray(123);
needsArray(null);
needsArray('string');
needsArray(new stdClass);

But these are, going by the signature, correct invocations of the function:

needsArray([]);
needsArray((array) new stdClass);
needsArray(['total' => 'some string', 'costs']);
needsArray(['total' => 123456, 'costs' => 60]);

Yet, only the last call is actually valid, the others will emit notices (undefined index), or won't do anything even remotely meaningful.
At the very least, you'll have to check for every expected key in the $parameter array using isset or array_key_exists, and then you'll still have to ensure that the value of each key is what you expect it to be. That's going to add a lot of silly-looking if's and else's to the code. What's more: if one of the keys doesn't exist, or doesn't contain the type of data you expect it to contain, what do you do? You'll probably have to throw an exception. Let's take our dummy needsArray function, and re-write it in a safe way. Note that we're only expecting a 1D array, with just 2 keys, but just look at the amount of added code we need to add to ensure the array looks the part:

function needsArray(array $argument)
{
    if (!isset($argument['total']) || !is_numeric($argument['total']))
    {
        throw new InvalidArgumentException(
            sprintf(
                '%s expects array argument with key "total" set to a numeric value'
                __FUNCTION__
            )
        );
    }
    if (!isset($argument['costs']) || !is_numeric($argument['costs']))
    {
        throw new InvalidArgumentException(
            sprintf(
                '%s expects array argument with key "costs" set to a numeric value'
                __FUNCTION__
            )
        );
    }
    return $argument['total'] - $argument['costs'];
}

That's just an awful lot of clutter. Especially if you consider the fact that it's more than likely that the array you're passing to this function will be passed to several other functions, each of which might perform the same checks over and over.

TL;TR

If your function requires something (like a DB connection), don't have your function literally require a file to resolve its dependencies: force the caller to supply it by means of arguments.

If you need complex arguments, like your $parameter argument, either split that argument up into hintable, simple arguments:

function selectQuery(mysqli $conn, array $select, $from, ...)

Or create a class. The getters can validate the data, and you can write the setters to return the data in whatever format you like. Then, just type-hint that class where you need it:

class SelectParam
{
    protected $select = ['*'];//default value
    public function setSelect(array $select)
    {
        $this->select = $select;
        return $this;
    }
    public function getSelect($asString = false)
    {
        $select = $this->select;
        if ($asString)
            $select = implode(', ', $select);
        return $select;
    }
}
function selectQuery(mysqli $conn, SelectParam $param)
{}

Other issues have been covered by other answers. Issues like

Unused vars: $columns -> it's never used, and what it contains just doesn't seem to make much sense, IMHO
Weird variable names: $wr, $wc are meaningless. It's only because of the context in which they are used that we can deduce wr means "whereRow". But if the code gets any bigger, and I have to start scrolling to where the vars are first used to figure out what they actually are, that maintaining the code will be a pain. Even if the maintainer is the one who wrote the code in the first place
Lack of comments. Yes, I've not commented my code snippets here to save space, but if you haven't added the actual comments in your real-life code either, you should do so ASAP. Any half-decent API uses the doc-blocks of functions/methods for auto-completion and provides you with information about the method you're calling:

/**

Executes a SELECT query on the connection, returns the results as an array of assoc arrays
@param mysqli $conn
@param SelectParam $param
@return array
*/
function selectQuery(mysqli $conn, SelectParam $param)
{}

With that doc-block, an editor like PHPStorm will display the description text when you've typed selectQuery, and it'll notify the developer if any of the arguments you're passing is of an incompatible type:

$conn = new PDO();
selectQuery($conn, 123);//PHPStorm will pick up on the wrong types

These kinds of features IDE's have can, and often do, significantly reduce the time spent debugging, and prevent countless bugs from ever being committed in the first place.


Filter column and row according to regex in header I'm writing a script that can grep the rows and columns from a text file that match a regex. I have an implementation but I'm looking to make it more elegant.

input.tsv

        a       b       c       d
a       2       9       6       1
b       6       4       7       0
c       3       7       2       0
d       5       8       2       2

I want to do something like this:

$ grep-row-column.py -E "[a|c]" input.tsv
         a       c
a        2       6
c        3       2

The solution should be able to stream a file (i.e. not read the entire thing into memory).

from __future__ import print_function
import sys,re

filename="input.tsv"
regex="[a|c]"

prog=re.compile(".*"+regex+".*")
with open(filename) as tsv:
    #find the appropriate columns in the header that match the regex
    line=tsv.readline()
    header=line.split("\t")
    count=0
    cols=[]
    print(header[0], end='')
    for token in header:
        if prog.match(token):
            #add the column indices to a list for use later
            cols.append(count)
            print("\t",token, end='')
        count+=1
    print()
    #in the rest of the line, find the matching rows and
    #print the columns that match the indices found above
    while line!="":
        line=tsv.readline()
        if line.strip()=="":
            continue
        tokens=line.split()
        if prog.match(tokens[0]):
            print(tokens[0], end='')
            for col in cols:
                print("\t",tokens[col], end='')
            print()

Is there a more 'pythonic' way to do this? I couldn't figure out how to avoid all the for loops and if statements.

(Cross-posted from here)

Your approach is basically reasonable, but you aren't taking advantages of Python's more powerful features, or any of the more interesting parts of the standard library.

re.search

A minor point to start with. You're making a regex like so:

prog=re.compile(".*"+regex+".*")

Presumably so that you get an unanchored match (i.e., one which can start at any point in the string).

re has a method re.search which will do unanchored matching by default; you can anchor the match to the start of the string with ^, as you would expect. See search() vs. match() in the documentation.

Manipulating whole data structures

There are a number of specific points below, but the broad thrust of them is that you will have a much nicer time doing large-scale operations on whole data structures, rather than fiddling around with indexes and individual elements. This is true in most languages, but one of the strengths of Python is the rich set of data structures and operations which are available built-in or in the standard library.

itertools.compress

There is a wonderful module in the standard library called itertools. This library is my first thought in Python whenever I want to do something involving sequences of any kind, and it contains a little function called compress which will do a lot of the work for your program.

Basically, you give compress a sequence of data items and a sequence of selectors, and you get back a sequence of those data items for which the selector is true. So in your example, matching your regex against the columns would give you the "selector":

[False, True, False, True, False]

(I'll mention how to generate this simply in a moment). You would then want to modify this to also pass through the row header, so you have the selector:

[True, True, False, True, False]

then, doing itertools.compress for a randomly-selected row:

itertools.compress(['a', 2, 9, 6, 1], [True, True, False, True, False])

=> ['a', 2, 6]

you can then just print that list to print the (filtered) row.

Note that you could also do this filtering yourself, using a list comprehension; however, itertools has the twin advantages of being common (hence readable) and carefully optimized (hence fast).

join

Once you can easily generate lists containing exactly the elements you want to output, you don't have to fiddle around doing print('\t', tokens[col], end='') and similar; you can just do:

print('\t'.join(tokens))

(assuming you have already filtered your tokens using compress or similar).

List comprehensions

List comprehensions are one of Python's most pleasant features. They're far too large a topic for me to sensibly explain in an answer here; that link will give you a good introduction, and there are many other articles and introductions around.

Roughly speaking, list comprehensions (and their cousins, generator expressions) are a nice syntax for creating sequences from sequences, doing "something" (transforming, selecting, etc.) on the way.

For example, you could write a list comprehension like this:

[reg.search(t) for t in tokens]

If reg is [a|c], and tokens is ['', 'a', 'b', 'c', 'd'], this will produce:

[False, True, False, True, False]

which you will recall is exactly what you need to feed to compress to filter to just those columns. (Actually, it will produce a list of Nones and regex match objects, but those evaluate to False/True in a boolean context, so don't worry too much about that).


Alternative way for checking an anagram pair I'm writing a program to check whether a pair of Strings (entered by the user) are anagrams. I've already did with the standard way to sort both of the strings using Arrays.sort() but I also thought of an alternative version not requiring any sorting and ended up with this:

import java.util.Scanner;

public class Anagrams {
    public static void main(String[] args) {
        String s1, s2;
        try (Scanner sc = new Scanner(System.in)) {
            System.out.println("Enter the two words: ");
            s1 = sc.nextLine().toLowerCase().replace(" ", "");
            s2 = sc.nextLine().toLowerCase().replace(" ", "");
        }
        if (s1.length() == s2.length() && isAnagram(s1, s2)) {
            System.out.format("%s is an anagram of %s.", s1, s2);
        } else {
            System.out.format("'%s' and '%s' are not anagrams.", s1, s2);
        }
    }

    public static boolean isAnagram(String s1, String s2) {
        return (sumOfChars(s1) == sumOfChars(s2));
    }

    public static int sumOfChars(String s) {
        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += c;
        }
        return sum;
    }
}

I know this isn't perfect but it does work with most of the anagram pairs that exist in the dictionary (that I've tested). Can I improve anything here or should I forgo this?

This wont ever work entirely correctly. What you did here can also be seen as calculating the hash of the 2 Strings. And just like you cannot use a hash to compare equality of 2 objects, you can't use your sumOfChars to compare if 2 strings are anagrams or not. (Simple counter example are the strings "ac" and "bb".)

On the other hand, that doesn't mean this idea is useless for exactly the same reasons as why we still provide a hashCode method when implementing equals.

If the 2 strings are more often NOT anagrams then they ARE anagrams, it can be a lot cheaper to first check if the sums are equal, and after that check for actual "anagram equality".

I suggest to update your isAnagram method to something like this:

public static boolean isAnagram(String s1, String s2) {
    if(s1.length() != s2.length() return false;
    if(sumOfChars(s1) != sumOfChars(s2)) return false;
    return sameLetterCount(s1, s2);
}

Notice that I also put the length() check in this method as well. The idea is actually the same. You start with a really cheap test that returns early in certain cases (strings of different length). Then you do a bit more expensive test that takes out most (but still not all) cases to return early again.
When those tests didn't fail, you got some good candidates to do the expensive actual checking for containing the same letters.

I have written it in my example so that it calls a different method. But you might as well just implement some letter counting algorithm right after the 2 if checks.


Using the XOR operator to calculate a checksum As part of a Google Foobar challenge, I'm trying to answer a rather difficult problem that involves the use of the XOR operator to calculate a checksum. While my solution works, my algorithm works in O(n) time, while the desired solution seems to need to be faster.

You can see the text of the challenge here.

While I know the help presented in that thread is valid, the solution is in Python, and I'm working in Java. Could someone explain why my solution is inefficient, and how it could be improved? I'm a self-taught coder, so some of the arcana of compsci is a mystery to me.

static int answer(int start, int length) {
    int checksum = 0;
    int dividerPos = length;
    int count = start;
    int idx = 0;

    while(true) {
        if(dividerPos == 0)
            return checksum;
        else if (idx == dividerPos) {
            count += (length - dividerPos);
            --dividerPos;
            idx = 0;

            continue;
        }

        checksum ^= count;

        ++idx;
        ++count;
    }
}

There are situations where an infinite loop while (true) is warranted, this is not one of them. The code implies that the loop shall be broken when dividerPost reaches zero. Say it explicitly:

        while (dividerPos > 0) {
            if (idx == dividerPos) {
                count += (length - dividerPos);
                --dividerPos;
                idx = 0;
                continue;
            }

            checksum ^= count;

            ++idx;
            ++count;
        }
        return checksum;

Now it is easy to see that the body of the loop is another loop in disguise. Again, be explicit:

        while (dividerPos > 0) {
            for (idx = 0; idx < dividerPos; idx++, count++) {
                checksum ^= count;
            }
            count += (length - dividerPos);
            --dividerPos;
        }

Now it is clear what the code is doing, and what it is doing inefficiently. An immediately identified bottleneck is an inner loop. What it does, it compute an xor of a range of numbers The first hit for a xor of a range query is this discussion. Study it, and see how it is applicable here. That itself will give your code a boost. Then try to optimize the outer loop.

PS: It is crucial to understand that the language doesn't matter.

PPS: Sorry if I sound harsh, but when I say study, I mean study. Don't skim. Understand how it works. Prove that it works correctly.

PPPS: Both answers in the page you've linked miss the point.


Generating a large task queue I've written a function to call with the deferred library to generate a large task queue, and at first without the recursion it timed out (deadlineexceeded) so now I'm trying with a recursion but is it safe that the function will terminate? I actually ran it with GAE and it did the correct task - deleted all the empty blobs that were written previously because of a bug. (It seems that empty blobs with 0 bytes get written several times a day and the code is to delete those blobs.)

def do_blobs_delete(msg=None, b=None, c=None):
    logging.info(msg)
    edge = datetime.now() - timedelta(days=750)
    statmnt = "WHERE size < 1" # size in bytes
    logging.debug(statmnt)
    try:
        gqlQuery = blobstore.BlobInfo.gql(statmnt)
        blobs = gqlQuery.fetch(999999)
        for blob in blobs:
            if blob.size < 1 or blob.creation < edge:
                blob.delete()
                continue
    except DeadlineExceededError:
        # Queue a new task to pick up where we left off.
        deferred.defer(do_blobs_delete, "Deleting empty blobs", 42, c=True)
        return
    except Exception, e:
        logging.error('There was an exception:%s' % str(e))

Yes, that function terminate (unless the semantics of blobstore are stranger than expected and blobs is an infinite generator). One thing to be concerned about might be that, should your query take a very long time, you would not delete a single blob before a DeadlineExceededError is thrown, and so schedule another task without doing any work. This is a bad thing, as you may end up with many jobs that simply get half way through a query, give up and then schedule themselves to run again. The worst part is that your only indication would be that your log would be full of info level messages (i.e. messages that will be ignored), giving you no idea that this travesty was unfolding in your task queue.

I would recommend you add some kind of limit to make sure you are decreasing the number of blobs towards zero each time. You could think of it as an inductive proof almost; see Burstall's 69 paper on structural induction if you feel like formulating a mathematical proof. However, that is probably not necessary in this case. My suggested rewrite would be something like:

# The number of times one call to do_blobs_delete may `recurse`, should probably be
# made a function of the count of all blobs
MAX_ATTEMPTS = 10

def do_blobs_delete(msg=None, b=None, c=None, attempt=0):
    logging.info(msg)
    edge = datetime.now() - timedelta(days=750)
    statmnt = "WHERE size < 1" # size in bytes
    logging.debug(statmnt)
    try:
        gqlQuery = blobstore.BlobInfo.gql(statmnt)
        blobs = gqlQuery.fetch(999999)
        for blob in blobs:
            if blob.size < 1 or blob.creation < edge:
                blob.delete()
    except DeadlineExceededError:
        if MAX_ATTEMPTS <= attempt:
            logging.warning("Maximum blob delete attempt reached")
            return
        # Queue a new task to pick up where we left off.
        attempt++
        deferred.defer(do_blobs_delete, "Deleting empty blobs",
                       42, c=True,
                       attempts=attempt)
        return
    except Exception, e:
        logging.error('There was an exception:%s' % str(e))

Note that this does not explicitly address the lack of an inductive variable, though it does limit any damage done.

Another thing to note is that you have a race condition on the .delete. Should the method be called concurrently, say by process A and B, then the call to .fetch could return the same set of bobs to each. They would then attempt to delete the elements twice, which would raise an error on the .delete call, leading to fewer blob deletions than expected. This problem gets a lot worse when we consider more processes and things like unspecified ordering. The correct way to handle this is to treat any exceptions thrown by the .delete in a more nuanced way than you are currently, and accommodate multiple attempted deletes without prejudice.

Your current code will work fine at the moment, the problems will manifest themselves when things get more complicated. While I am sure Google's infrastructure can handle these upsets, your bottom line may be less flexible.


Scheduling a task into a period within a day, depending on whether or not it is a weekend I have a function which needs to detect part of the day depending on whether it's the weekend or not (the weekend affects the lunch time indication). The method is quite long and I'd like to know how it can be better.

double PartOfDayRule::ExtractFeature(dto::ActionableItem & item) {
                double morning, firstWorkPart, lunch, secondWorkPart, afterWork, beforeSleep, sleepTime;
                morning = 0;
                firstWorkPart = 1;
                lunch = 2;
                secondWorkPart = 3;
                afterWork = 4;
                beforeSleep = 5;
                sleepTime = 6;

                double result = -1;
                dto::DateTime itemTime = item.scheduledStart;
                if(util::time::inRange(item.ctx->sleepTimeEnd, item.ctx->workTimeStart, itemTime)){
                    result = morning;
                    goto result;
                }

                dto::DateTime lunchStart;
                dto::DateTime lunchStop;
                if(!item.ctx->isWorkingDay){
                    lunchStart = item.ctx->workTimeStart;
                    lunchStop = item.ctx->workTimeFinished;
                }else{
                    long firstWorkPartLength = util::time::between<std::chrono::hours>(item.ctx->workTimeStart, item.ctx->workTimeFinished) / 2;
                    lunchStart = item.ctx->workTimeStart + std::chrono::hours{firstWorkPartLength};
                    lunchStop = lunchStart + std::chrono::hours{1};
                }
                if(util::time::inRange(lunchStart, lunchStop, itemTime)){
                    result = lunch;
                    goto result;
                }

                if(util::time::inRange(item.ctx->workTimeStart, lunchStart, itemTime)){
                    result = firstWorkPart;
                    goto result;
                }

                if(util::time::inRange(lunchStop, item.ctx->workTimeFinished, itemTime)){
                    result = secondWorkPart;
                    goto result;
                }

                dto::DateTime sleepPreparationTime = item.ctx->sleepTimeStart - std::chrono::hours{1};
                if(util::time::inRange(item.ctx->workTimeFinished, sleepPreparationTime, itemTime)){
                    result = afterWork;
                    goto result;
                }

                if(util::time::inRange(sleepPreparationTime, item.ctx->sleepTimeStart, itemTime)){
                    result = beforeSleep;
                    goto result;
                }

                result = sleepTime;
                result:
                return result;

            }

You return what is effectively an enum as a double. Why? create the enum and return that it's much clearer that way wat the return value means:

If you still want a single point of return (for whatever reason) then you can use an if-else chain:

enum PartOfDay{
    morning = 0,
    firstWorkPart = 1,
    lunch = 2,
    secondWorkPart = 3,
    afterWork = 4,
    beforeSleep = 5,
    sleepTime = 6
}

PartOfDay PartOfDayRule::ExtractFeature(dto::ActionableItem & item) {

    dto::DateTime lunchStart;
    dto::DateTime lunchStop;
    if(!item.ctx->isWorkingDay){
        lunchStart = item.ctx->workTimeStart;
        lunchStop = item.ctx->workTimeFinished;
    }else{
        long firstWorkPartLength = util::time::between<std::chrono::hours>(item.ctx->workTimeStart, item.ctx->workTimeFinished) / 2;
        lunchStart = item.ctx->workTimeStart + std::chrono::hours{firstWorkPartLength};
        lunchStop = lunchStart + std::chrono::hours{1};
    }

    dto::DateTime itemTime = item.scheduledStart;
    dto::DateTime sleepPreparationTime = item.ctx->sleepTimeStart - std::chrono::hours{1};
    PartOfDay result = sleepTime;

    if(util::time::inRange(item.ctx->sleepTimeEnd, item.ctx->workTimeStart, itemTime)){
        result = morning;
    } else if(util::time::inRange(item.ctx->workTimeStart, lunchStart, itemTime)){
        result = firstWorkPart;
    } else if(util::time::inRange(lunchStart, lunchStop, itemTime)){
        result = lunch;
    } else if(util::time::inRange(lunchStop, item.ctx->workTimeFinished, itemTime)){
        result = secondWorkPart;
    }else if(util::time::inRange(item.ctx->workTimeFinished, sleepPreparationTime, itemTime)){
        result = afterWork;
    }else if(util::time::inRange(sleepPreparationTime, item.ctx->sleepTimeStart, itemTime)){
        result = beforeSleep;
    }else {
        result = sleepTime;
    }
    return result;

}

Or you can sort the ranges and then use std::find to get the range you want.


Validating UTF-8 byte array I'm writing a validator function that receives a byte[] and checks whether it represents a valid UTF-8 byte sequence, according to this table.

Is my approach correct?  So far it has worked fine with my tests, but I'm worried that I might be missing some edge case, or that the way I'm handling bytes is off.

And more importantly, how can I improve the conditions using bit-twiddling? I'm a bit rusty here, and I think that a comparison such as this:

if ((b & 0xFF) >> 1 == (byte) 0b1111110)

can be expressed in a simpler, more idiomatic way.

public static boolean validate(byte[] bytes) {

    int length = bytes.length;

    if (length < 1 || length > 6)
        return false;

    byte b = bytes[0];

    if (length == 1)
        return (b & (1 << 7)) == 0;

    int n;

    if ((b & 0xFF) >> 1 == (byte) 0b1111110)
        n = 5;
    else if ((b & 0xFF) >> 2 == (byte) 0b111110)
        n = 4;
    else if ((b & 0xFF) >> 3 == (byte) 0b11110)
        n = 3;
    else if ((b & 0xFF) >> 4 == (byte) 0b1110)
        n = 2;
    else if ((b & 0xFF) >> 5 == (byte) 0b110)
        n = 1;
    else
        return false;

    if (length-1 != n)
        return false;

    for (int i = 1; i < length; i++)
        if ((bytes[i] & 0xFF) >> 6 != (byte) 0b10)
            return false;

    return true;

}

And these are some tests to try it out:

byte[] bytes1 = {(byte) 0b11001111, (byte) 0b10111111};
System.out.println(validate(bytes1)); // true

byte[] bytes2 = {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b10111111};
System.out.println(validate(bytes2)); // true

byte[] bytes3 = {(byte) 0b10001111, (byte) 0b10111111};
System.out.println(validate(bytes3)); // false

byte[] bytes4 = {(byte) 0b11101111, (byte) 0b10101010, (byte) 0b00111111};
System.out.println(validate(bytes4)); // false

Logic

Never omit the optional braces like that.  Think of yourself as a contributing factor to a future coding accident.  If you really want to omit braces, then put the statement on the same line, so that there is no possibility of misinterpretation.

The function does not check for overlong encodings, invalid byte sequences, or invalid code points.  Those caveats should be declared in JavaDoc.

I would eliminate the length > 6 check, as 6 is a magic number.  You don't need that special case anyway.

I would also incorporate the length == 1 special case into the regular logic.

In general, text is more likely to contain shorter UTF-8 sequences than longer ones, so you might as well handle the shorter cases first to save a few CPU cycles.

Rather than setting n to be the number of trailing bytes, set it to be the expected length of the array.  I'd rename n → expectedLen to be more descriptive.  That makes the code more readable (and saves one pointless subtraction).

Eliminate the bit-shifting.  Just AND with the bitmask to specify which bits you are interested in inspecting.

public static boolean validate(byte[] bytes) {
    int expectedLen;
    if      (bytes.length == 0)                     return false;
    else if ((bytes[0] & 0b10000000) == 0b00000000) expectedLen = 1;
    else if ((bytes[0] & 0b11100000) == 0b11000000) expectedLen = 2;
    else if ((bytes[0] & 0b11110000) == 0b11100000) expectedLen = 3;
    else if ((bytes[0] & 0b11111000) == 0b11110000) expectedLen = 4;
    else if ((bytes[0] & 0b11111100) == 0b11111000) expectedLen = 5;
    else if ((bytes[0] & 0b11111110) == 0b11111100) expectedLen = 6;
    else    return false;

    if (expectedLen != bytes.length) return false;

    for (int i = 1; i < bytes.length; i++) {
        if ((bytes[i] & 0b11000000) != 0b10000000) {
            return false;
        }
    }

    return true;
}

Interface design

It's rarely useful to validate a single character: usually, you'll want to validate a whole string.  You should name your function to avoid giving the impression that it checks for multi-character strings.

In Java, functions that perform a test and return a boolean are conventionally named isSomething() or hasSomething().  A function named validate() suggests that it performs an action as a side-effect, perhaps throwing an exception on failure.

Therefore, I'd rename your function to isValidChar(byte[] bytes).

So, what if I need to validate a string?  I'd have to somehow chunk it up into right-sized byte arrays first.  That's not really possible without examining the string using similar logic to what is in the function itself.  Even then, it would be wasteful to construct a byte array just for the function call.  Therefore, I think that it would be more useful to provide a function that validates a string.  To go further, you could make such a function return something more informative than just a boolean.

/**
 * Returns the number of UTF-8 characters, or -1 if the array
 * does not contain a valid UTF-8 string.  Overlong encodings,
 * null characters, invalid Unicode values, and surrogates are
 * accepted.
 */
public static int charLength(byte[] bytes) {
    int charCount = 0, expectedLen;

    for (int i = 0; i < bytes.length; i++) {
        charCount++;
        // Lead byte analysis
        if      ((bytes[i] & 0b10000000) == 0b00000000) continue;
        else if ((bytes[i] & 0b11100000) == 0b11000000) expectedLen = 2;
        else if ((bytes[i] & 0b11110000) == 0b11100000) expectedLen = 3;
        else if ((bytes[i] & 0b11111000) == 0b11110000) expectedLen = 4;
        else if ((bytes[i] & 0b11111100) == 0b11111000) expectedLen = 5;
        else if ((bytes[i] & 0b11111110) == 0b11111100) expectedLen = 6;
        else    return -1;

        // Count trailing bytes
        while (--expectedLen > 0) {
            if (++i >= bytes.length) {
                return -1;
            }
            if ((bytes[i] & 0b11000000) != 0b10000000) {
                return -1;
            }
        }
    }
    return charCount;
}

That's a more versatile function, for about the same amount of code.


Leetcode: Subtree of Another Tree My solution to the LeetCode's Subtree of Another Tree passes all the test cases, but the code feels and looks ugly. Would appreciate an advice on how to improve it.

The problem:

  Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example:

  Given tree s:

     3
    / \
   4   5
  / \
 1   2

  Given tree t:

   4
  / \
 1   2

  Return true, because t has the same structure and node values
  with a subtree of s.

My solution:

class Solution {
private:
    bool isSame(TreeNode* root_s, TreeNode* t) {

        if (!root_s && !t) return true;
        if (root_s && !t) return false;
        if (!root_s && t) return false;

        if (root_s->val != t->val) return false;

        return isSame(root_s->left, t->left) &&
            isSame(root_s->right, t->right);
    }

    void preorder (TreeNode* s, TreeNode* t, bool& is_subtree) {
        if (!s) return;

        if (s->val == t->val) {
            if (isSame(t,s)) {
                is_subtree = true;
                return;
            }
        }
        preorder (s->left, t, is_subtree);
        preorder (s->right, t, is_subtree);
    }

public:
    bool isSubtree(TreeNode* s, TreeNode* t) {

        bool is_subtree = false;
        preorder (s, t, is_subtree);

        return is_subtree;
    }
};

For context, here's the definition of TreeNode given by LeetCode:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Your code doesn't look that ugly!  Here are some suggestions to make it better.  Note that LeetCode makes significantly more mistakes than you when it comes to code quality; I have listed the suggestions for LeetCode-provided stuff too, so that you don't make the same mistakes when you are writing real code — you don't have to force LeetCode to accept them (i.e., some of them can be compromised for the purpose of passing their tests).

General design

The Solution class is very Java-style AFAIK, but it is not idiomatic in C++.  It should be replaced by a namespace, or removed altogether.  In C++, it is preferred to create a separate Tree class for the binary trees, instead of operating directly on the nodes.  Also, the value type should be a template parameter for reusability.

Naming

In C++, functions and variables are generally named in snake_case, with CamelCase names reserved for classes.

The name of the function is misleading — to me, isSubtree(s, t) means "s is a subtree of t," rather than the reverse.  contains_subtree may be better.  The parameters s and t are also non-descriptive and thus unreadable; I recommend tree and subtree.

The parameters to isSame (or maybe just same), on the other hand, can be named as simply as tree_a and tree_b, because the semantics is unambiguous.

Logic

(Note: the code snippets presented are intended to help you understand the review.  They are not tested; in other words, they and may contain mistakes and are not guaranteed to work.)

The logic of same can be simplified:

if both arguments are non-null, then they are identical if and only if

their values are equal; and
their left subtrees are identical; and
their right subtrees are identical;

otherwise, they are identical if and only if they are both null.

bool same(TreeNode* tree_a, TreeNode* tree_b)
{
    if (tree_a && tree_b) {
        return tree_a->val == tree_b->val
            && same(tree_a->left, tree_b->left)
            && same(tree_a->right, tree_b->right);
    } else {
        return !tree_a && !tree_b;
    }
}

This presents your logic in a way that is (hopefully) more readable.

Similarly,

if tree is non-null, then tree contains subtree if and only if

same(tree, subtree); or
tree->left contains subtree; or
tree->right contains subtree;

otherwise, tree contains subtree if and only if subtree is null as well.

bool contains_subtree(TreeNode* tree, TreeNode* subtree)
{
    if (tree) {
        return same(tree, subtree)
            || contains_subtree(tree->left, subtree)
            || contains_subtree(tree->right, subtree);
    } else {
        return !subtree;
    }
}

This refactoring eliminates the unnatural non-local control flow (i.e., writing to the bool& argument instead of using the return value).  It also ensures that the function returns as soon as a match is found.


Moving average function in C++ for use with R I am trying to improve the code and speed up in C++ (Rcpp) a (centered) weighted moving average function I coded.

An example of what the roll_mean function does. Note that the function works no matter what the size of x is and adapts to both tails of my data

w=c(1/2,1,1/2)
x=c(4,2,6,12)
res=c(2,5,7,3)
res=c((x[1:2]*w[2:3])/sum(w[2:3]),x[1:3]*w[1:3]/sum(w[1:3]),x[2:4]*w[1:3]/sum(w[1:3]),x[3:4]*w[1:2]/sum(w[1:2]))

The file PartialMA.cpp

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]
NumericVector roll_mean(const NumericVector& x,
                        const NumericVector& w) {

  int n = x.size();
  int w_size = w.size();
  int size = (w_size - 1) / 2;

  NumericVector res(n);
  int i, ind_x, ind_w;

  double tmp_wsum, tmp_xwsum, tmp_w;

  for (i = 0; i < n; i++) {
    tmp_xwsum = 0;
    tmp_wsum = 0;
    for (ind_x = i - size, ind_w = 0; ind_x < i + size; ind_x++, ind_w++) {
      if((ind_x >= 0) & (ind_x < n)){
      tmp_w = w(ind_w);
      tmp_xwsum += x(ind_x) *  tmp_w;
      tmp_wsum += tmp_w;
      }
    }
    res[i] = tmp_xwsum / tmp_wsum;
  }

  return res;
}

I tried to replace the loop + if statement with this to minimize the number of iteration:

for (ind_x = std::max(0, i - size), ind_w = std::max(0, size-1); ind_x < std::min(n, i + size); ind_x++, ind_w++) {

I feel like I am not rigorous enough and I would be very grateful if someone could help me improving my code and eventually speed up the function as much as possible.

Overall your code is not bad, but we can do better. Let's start with the coding style.
Your variables are clearly named and your code is easy to follow, however the use of & is not necessary.
const NumericVector &x

R objects are always passed by reference in Rcpp even without the &. Dirk has some slides (see 29,30) with more information about this topic here. It is also in the Rcpp FAQ. The point is, is that we can safely drop these ampersands.
Now, let's talk about how we can improve the performance of your code. We first note that there are many unnecessary checks in the inner for loop.
if((ind_x >= 0) & (ind_x < n))

This can be avoided outside of the loop like so :
// [[Rcpp::export]]
NumericVector roll_meanReduceChecks(const NumericVector x,
                                    const NumericVector w) {

    int n = x.size();
    int w_size = w.size();
    int size = (w_size - 1) / 2;

    NumericVector res(n);
    int i, ind_x, ind_w, strt, endx;

    double tmp_wsum, tmp_xwsum, tmp_w;

    for (i = 0; i < n; i++) {
        tmp_xwsum = 0;
        tmp_wsum = 0;

        if ((i - size) <= 0) {
            strt = 0;
            ind_w = size - i;
        } else {
            strt = i - size;
            ind_w = 0;
        }

        endx = ((i + size) >= n) ? n : (i + size);

        for (ind_x = strt; ind_x < endx; ind_x++, ind_w++) {
            // This check is no longer necessary
            // if((ind_x >= 0) & (ind_x < n)){
            tmp_w = w(ind_w);
            tmp_xwsum += x(ind_x) * tmp_w;
            tmp_wsum += tmp_w;
        }

        res[i] = tmp_xwsum / tmp_wsum;
    }

    return res;
}

With this modification, we get about 10% faster timings:
set.seed(42)
x <- sample(10^3, 10^4, TRUE)
w <- sample(100, 10^3 , TRUE) / 100

## Gives the same result
all.equal(roll_mean(x, w), roll_meanReduceChecks(x, w))
[1] TRUE

library(microbenchmark)
microbenchmark(roll_mean(x, w), roll_meanReduceChecks(x, w),
               times = 50, unit = "relative")
    Unit: relative
                       expr      min       lq     mean   median       uq      max neval
            roll_mean(x, w) 1.138508 1.135057 1.119695 1.132882 1.123308 1.149893    50
roll_meanReduceChecks(x, w) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    50

We can still do better. The real savings comes into play with the use of iterators. There is a lot of good information out there regarding this topic and here is just one resource written by Hadley Wickham that is a good starting place.
Putting it all together we have:
// [[Rcpp::export]]
NumericVector roll_meanIterator(const NumericVector x,
                                const NumericVector w) {

    int n = x.size();
    int w_size = w.size();
    int size = (w_size - 1) / 2;

    NumericVector res(n);
    NumericVector::const_iterator itw, itx, itEnd;
    double tmp_wsum, tmp_xwsum;

    for (int i = 0; i < n; i++) {
        tmp_xwsum = 0;
        tmp_wsum = 0;

        if ((i - size) <= 0) {
            itx = x.begin();
            itw = w.begin() + size - i;
        } else {
            itx = x.begin() + i - size;
            itw = w.begin();
        }

        itEnd = ((i + size) >= n) ? x.end() : x.begin() + i + size;

        for (; itx < itEnd; itx++, itw++) {
            tmp_xwsum += (*itx) * (*itw);
            tmp_wsum += (*itw);
        }

        res[i] = tmp_xwsum / tmp_wsum;
    }

    return res;
}

Here is a sanity check:
all.equal(roll_mean(x, w), roll_meanIterator(x, w))
[1] TRUE

And here are the benchmarks:
microbenchmark(roll_mean(x, w), roll_meanIterator(x, w),
                          times = 50, unit = "relative")
Unit: relative
                   expr      min       lq     mean   median       uq      max neval
        roll_mean(x, w) 8.480686 8.458674 8.493975 8.894612 8.548443 8.453865    50
roll_meanIterator(x, w) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    50

That is nearly 9x faster. Not bad, considering we didn't have to change the code that much.
Update
Below is an example of over optimizing and a lesson on "when to stop" as the code appears to be more efficient but is much messier than the code above with little to no trade-off in efficiency.
If we examine tmp_wsum more closely, we will find that on every iteration, it is only changing at the endpoints. In roll_meanReduceChecks above, if we insert std::cout << ind_w << ' '; just before the inner for loop and std::cout << ind_w << std::endl; just after it, here is the output for the first 5 iterations:
499 998
498 998
497 998
496 998
495 998

And the last 5 iterations:
0 504
0 503
0 502
0 501
0 500

This seems like an opportunity for even further optimizing our code as we can alter our code such that we won't have to reconstruct tmp_wsum from scratch every time. However, in order to implement this, we must add two extra variable, and two extra checks to every iteration. Observe:
NumericVector roll_meanOverOptimized(const NumericVector x,
                                     const NumericVector w) {

    int n = x.size();
    int w_size = w.size();
    int size = (w_size - 1) / 2;

    NumericVector res(n);    // must add variables for checks below
    NumericVector::const_iterator itw, itwBeg, itwEnd, itx, itxEnd;
    double tmp_wsum = 0, tmp_xwsum = 0;

    // We must first initialize tmp_wsum, itwBeg,
    // itwEnd, as well as populate res[0]
    itx = x.begin();
    itwBeg = itw = w.begin() + size;
    itxEnd = (size >= n) ? x.end() : x.begin() + size;

    for (; itx < itxEnd; itx++, itw++) {
        tmp_xwsum += (*itx) * (*itw);
        tmp_wsum += (*itw);
    }

    res[0] = tmp_xwsum / tmp_wsum;
    itwEnd = itw;

    // Start i @ 1 instead of 0 as the first
    // iteration was taken care of above
    for (int i = 1; i < n; i++) {
        tmp_xwsum = 0;

        if ((i - size) < 0) {
            itx = x.begin();
            itw = w.begin() + size - i;
        } else {
            itx = x.begin() + i - size;
            itw = w.begin();
        }

        // first check
        if (itw != itwBeg)
            tmp_wsum += (*itw);
        itwBeg = itw;

        itxEnd = ((i + size) > n) ? x.end() : x.begin() + i + size;

        // N.B. only one variable is being updated now
        for (; itx < itxEnd; itx++, itw++)
            tmp_xwsum += (*itx) * (*itw);

        // second check
        if (itw != itwEnd)
            tmp_wsum -= (*itw);
        itwEnd = itw;

        res[i] = tmp_xwsum / tmp_wsum;
    }

    return res;
}

Let's see if this extra optimization paid off:
## Gives the same results
all.equal(roll_meanIterator(x, w), roll_meanOverOptimized(x, w))
[1] TRUE

microbenchmark(roll_mean(x, w),
               roll_meanIterator(x, w),
               roll_meanOverOptimized(x, w),
               times = 50, unit = "relative")
               Unit: relative
                        expr      min       lq     mean   median       uq      max neval
             roll_mean(x, w) 8.679318 8.751559 8.605352 8.796965 8.509649 7.683454    50
     roll_meanIterator(x, w) 1.015420 1.028507 1.041876 1.019177 1.017208 1.133470    50
roll_meanOverOptimized(x, w) 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    50

Virtually identical results as roll_meanIterator. IMO, the ~2% efficiency gain is not worth it as we have made our code more difficult to read.
Update 2 (Many thanks to @HongOoi)
In the comments @HongOoi states, "the speedup isn't because of iterators per se, but because OP is using bounds-checked array access via the operator (). Switching to the regular [] should give you the same result as iterators. Let us test!!!
// [[Rcpp::export]]
NumericVector roll_meanBrackets(const NumericVector x,
                                const NumericVector w) {

    int n = x.size();
    int w_size = w.size();
    int size = (w_size - 1) / 2;

    NumericVector res(n);
    double tmp_wsum, tmp_xwsum;
    unsigned long int ind_x, ind_w, xEnd;

    for (int i = 0; i < n; i++) {
        tmp_xwsum = 0;
        tmp_wsum = 0;

        if ((i - size) < 0) {
            ind_x = 0;
            ind_w = size - i;
        } else {
            ind_x = i - size;
            ind_w = 0;
        }

        xEnd = ((i + size) > n) ? x.size() : i + size;

        for (; ind_x < xEnd; ind_x++, ind_w++) {
            tmp_xwsum += x[ind_x] * w[ind_w];
            tmp_wsum += w[ind_w];
        }

        res[i] = tmp_xwsum / tmp_wsum;
    }

    return res;
}

And here are the benchmarks:
microbenchmark(roll_mean(x, w),
               roll_meanIterator(x, w),
               roll_meanBrackets(x, w),
               times = 50, unit = "relative")
Unit: relative
                   expr      min       lq     mean   median        uq      max neval
        roll_mean(x, w) 8.596342 8.425527 8.374452 8.414136 8.3626927 7.479161    50
roll_meanIterator(x, w) 1.012213 1.007219 1.007606 1.000564 0.9973372 1.177148    50
roll_meanBrackets(x, w) 1.000000 1.000000 1.000000 1.000000 1.0000000 1.000000    50

As predicted by @HongOoi, the efficiency is nearly identical. This begs the question

Which method should you use? Iterators or C-style indexing?

Fortunately for us, there is some great information out there addressing this very topic. In fact, I found the answer to the stackoverflow question Iterator Loop vs Index Loop extremely helpful. Here is the summary by @TemplateRex:

"if you really need the index (e.g. access the previous or next element, printing/logging the index inside the loop etc.) or you need a stride different than 1, then I would go for the explicitly indexed-loop, otherwise I'd go for the range-for loop.
For generic algorithms on generic containers I'd go for the explicit iterator loop unless the code contained no flow control inside the loop and needed stride 1, in which case I'd go for the STL for_each + a lambda."


A Simple Async Task in Clojure Purpose of Code: To simulate scraping the web and updating a db, by, presently, adding randomly generated numbers to a "database".

Have I wired up the followin async code properly? Is there a simpler, more composable way to pass objects around? Or some more idiomatic way?

I have added comments to self-explanatory code to hopefully make it a titch easier on reviewers.

Note: the following mocks what will become a web scraper. So just be aware that the "db" isn't a real db, and "fetching urls" refers to a mock up that will eventually get swapped out, but I hope you see the semantics I intend to sub in.

(ns clj-scraper.core
  (:require [clojure.core.async :as a :refer [>! <! >!! <!! go go-loop chan
                                              buffer close! thread alts!
                                              alts!! timeout
                                              put! take!
                                              pipe pipeline pipeline-async pipeline-blocking]]))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Database - a mockup of what could be a db

(def test-db (agent {:1 {:url  "abc"
                         :vals []}
                     :2 {:url  "bac"
                         :vals []}
                     :3 {:url  "pg"
                         :vals []}))

; append to a path in the test-db
(defn test-append [path x] (send test-db update-in path (partial cons x)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Load from DB

; objects start their journey on this channel
(def db-objs> (chan 1))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Fetch URLs

; test-data mocks fetching a url by returning the string of a random int
(defn test-data [_] (str (rand-int 100)))

(def pages> (chan 1))
(pipeline 4
          pages>
          ; add the fetched page to the object getting passed around
          (map (fn [{:keys [url] :as obj}]
                 (conj obj {:page (test-data url)})))
          db-objs>)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; CSS Select Page

; this mock up simply converts a String -> Int
(defn test-select [x] (Integer. x))

(def selections> (chan 1))
(pipeline 4
          selections>
          ; add the converted String to the object getting passed around
          (map (fn [{:keys [page] :as obj}]
                 (conj obj {:scraped (test-select page)})))
          pages>)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Update DB

; add the "scraped value" to the "db"
(go-loop []
  (let [{:keys [id scraped]} (<! selections>)]
    (test-append [id :vals] scraped))
  (recur))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Run Things in Debugging

(doseq [[id data] @test-db] (go (>! db-objs> (conj data {:id id}))))
@test-db ; won't show expected results until async ops are done

Commenting on this section:

; test-data mocks fetching a url by returning the string of a random int
(defn test-data [_] (str (rand-int 100)))

(def pages> (chan 1))
(pipeline 4
          pages>
          ; add the fetched page to the object getting passed around
          (map (fn [{:keys [url] :as obj}]
                 (conj obj {:page (test-data url)})))
          db-objs>)

In real-life, test-data will either do blocking I/O or be asynchronous.
Therefore, you should use pipeline-blocking or pipeline-async instead, otherwise you'll exhaust the "go thread pool".

Commenting on this part:

(go-loop []
  (let [{:keys [id scraped]} (<! selections>)]
    (test-append [id :vals] scraped))
  (recur))

You should account for the fact that the selections> channel may close, in which case the object will be nil and you should stop the loop.

(go-loop []
  (when-let [{:keys [id scraped]} (<! selections>)]
    (test-append [id :vals] scraped)
    (recur)))

Commenting on this part:

(doseq [[id data] @test-db] (go (>! db-objs> (conj data {:id id}))))

Because go is asynchronous, this consists of putting all the objects in test-db at once into the processing pipeline, which potentially consumes a lot of memory. Core.async channels are designed to give you back-pressure, you should use it.

How about instead:

(go (doseq [[id data] @test-db] (>! db-objs> (conj data {:id id}))))

Which you can express at a higher-level using onto-chan

(onto-chan db-objs (map (fn [data] (conj data {:id id})) @test-db) false)


Using the wildcard when importing packages I am learning java and browsing posts on CodeReview and StackOverflow.

In my text Introduction to Java Programming- Y Daniel Liang it states:

  The wildcard import imports all classes in a package by using ...
  The information for the classes in an imported package is not read in
  at compile time or runtime unless the class is used in the program.
  The import statement simply tells the compiler where to locate the
  classes. There is no performance difference between a specific and a
  wildcard import declaration.

These are two examples:

This question:  (1)

import java.util.ArrayList;
import java.util.List;
import javafx.beans.value.ChangeListener;
import javafx.beans.value.ObservableValue;
import javafx.collections.FXCollections;
import javafx.collections.ObservableList;
import javafx.geometry.Bounds;
import javafx.scene.Group;
import javafx.scene.Scene;
import javafx.scene.control.ListCell;
import javafx.scene.control.ListView;
import javafx.scene.control.ScrollPane;
import javafx.scene.control.TitledPane;
import javafx.scene.layout.AnchorPane;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;
import javafx.util.Callback;

This answer: (2)

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

Could these be written as:

(1)

import java.util.*
import javafx.beans.*
import javafx.collections.*
import javafx.geometry.*
import javafx.scene.*
import javafx.stage.*

and

(2)

import java. util.*

Are there exceptions to using the wildcard for importing?
What is considered the best practice when specifying imports?

I am not sure if this is best posted on code review or stackoverflow

First, let's acknowledge that this is a subjective question.  However, in my opinion, it is constructive enough to be on topic for this site.

I would treat the standard Java library differently than your own packages or third-party packages.  Everyone recognizes classes from the standard Java library, such as BufferedReader, PrintWriter, and IOException.  There is therefore no value in importing those individually; it just clutters the code.  Everyone who has worked with Java will know that those classes belong to the java.io package, unambiguously.  Anyone who writes classes whose names conflict with those well known classes will be soundly beaten up, so name conflicts with java. classes just don't happen in practice.

With third-party libraries, it makes sense to import more specifically.  Programmers encountering those classes could use some help to figure out which packages they belong to.  Name clashes could happen.  That said, star imports for third-party libraries would be a judgement call.  I would suggest importing individual classes up to some number of classes (around 4) per package; beyond that, a star import might be sensible.  I would try to avoid star-importing more than one such package, though, to mitigate against the documentation-searching and name clash concerns.  (If you feel the urge to star-import multiple packages, your class is probably doing too much anyway and should be split up.)

With code that you have written yourself for the same or a closely related project, go ahead and star-import related packages, judiciously.  If you're working with the source code, you'll be familiar with the related code in neighbouring packages anyway.  If it fails to compile because of a name clash, you can fix it yourself.


Indenting a function to recursively find filenames I wrote this function that recursively traverses a given directory resolves
the relative file-names to absolute file-names and yields the resolved file-name if it matches a given pattern. You can specify a callback function as well.

The first issue I have with this function is that it is a bit hard to comprehend, I think this problem can be reduced with proper indentation of the generator expressions.

The second thing I would like help with is, How do i reduce the repeated block of code?

import fnmatch
import os
import sys

def find(root, pattern, *callback):
    if not callback:
        for _, _, files in  ((root, _, (os.path.join(root, filename)
        for filename in files if fnmatch.fnmatch(filename, pattern)))
        for (root, _, files) in os.walk(root)):
            for filename in files:
                yield filename

    callback = callback[0]
    for _, _, files in  ((root, _, (os.path.join(root, filename)
    for filename in files if fnmatch.fnmatch(filename, pattern)))
    for (root, _, files) in os.walk(root)):
        for filename in files:
            yield callback(filename)

def cb(filename):
    print filename

for filename in find('/home/dwilson', '*.py', cb):
    pass

A good way would be to eliminate duplicate using a default callback that does nothing:

def walker(root, pattern):
    for _, _, files in  ((root, _, (os.path.join(root, filename)
        for filename in files if fnmatch.fnmatch(filename, pattern)))
        for (root, _, files) in os.walk(root)):
            for filename in files:
                yield filename

def find(root, pattern, callback=lambda v:v):
    for filename in walker(root, pattern):
        yield callback(filename)

Afterwards, we simplify the walker to

def walker(root, pattern):
    for (root, _, files) in os.walk(root):
        for filename in files:
            if fnmatch.fnmatch(filename, pattern):
                yield os.path.join(root, filename)

and have a much more readable thing than before.