Thread-safe Singleton class I have created this class to simulate a thread-safe Singleton.

Have I missed anything?

#include <boost/thread/mutex.hpp>

class Singleton
{
public:
  static Singleton& GetInstance()
  {
    boost::mutex::scoped_lock lock(m_mutex);
    static Singleton instance;
    return instance;
  }

private:
  static boost::mutex m_mutex;

  Singleton() {}
  ~Singleton() {}

  Singleton(const Singleton&);
  const Singleton& operator=(const Singleton&);
};

As usual, when dealing with singletons, consider that you probably shouldn't be making a singleton at all.

Read this, for example. A singleton is almost certainly not what you actually need, even if it is implemented correctly and in a thread-safe manner.

A plain old global might be a better option, or perhaps you should simply pass a reference around to those who need it.


Setting unique code to model before creating (ruby/rails) I have a Table model that needs a unique code. I have a method creating the code (and making sure it's unique), but I have the same line self.code = rand.to_s[2..5] twice. Is there a neat way to only have that line once?

class Table < ActiveRecord::Base
  before_create :set_code

  private
  def set_code
    self.code = rand.to_s[2..5]
    while(Table.find_by(code: code) != nil)
      self.code = rand.to_s[2..5]
    end
  end
end

It's the same in Ruby as in other languages where you want a loop to always run at least once: Move the condition to the end.

begin
  code = ...
end until(Table.find_by(code: code).nil?)

Ruby's syntax is a little odd ("end until"), but it's the same as a do { ... } while() in C-like languages.

However, the overall system you're using is really strange. If all you want is a unique number for the new table, just use id. That's what it's for. It's set automatically at the database layer, so there'll be no collisions.

If you just want 4 random digits, don't make a random float (which may not have enough digits, e.g. 0.0), convert it to a string and pull out a section. Just call rand(1000..9999).to_s. Or rand(10_000).to_s.rjust(4, '0') to get a number padded with leading zeros if necessary.

However, anything you do in the application layer is vulnerable to race conditions! Between the time you check if a code already exists in the database, and the time you save your record, that code may have been added, giving you duplicates. E.g. 2 threads both check for the code 1234 at the same time, and both see that it's not in the database, so both then save records with that same code. Oops.

The proper way to avoid such things is to add a uniqueness constraint in the database itself, and rescue the resulting RecordNotUnique error that'll get raised.

Here's an article discussing other ways to generate unique tokens, and a follow-up on how to handle collisions.

However: just use id. Or find a gem that generates unique tokens for you.


Counting words in files - follow-up-3 Previous question:

Counting words in files - follow-up 2

For simplifying the code, I have implemented std::regex rather than templates.

How can I improve this code further?

//
//program name: WordCounter
//
//usage: C:\>WordCounter.exe test.txt test1.txt
//
#include <iostream>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
#include <regex>

using Words = std::unordered_map<std::string, std::size_t>;

template<typename T>
std::string getToken(T begin, T end, std::regex e = std::regex{ R"([^.,\n\r]+)" })
{
    std::smatch match{};

    std::string result{};

    if (std::regex_search(begin, end, match, e))
    {
        result.append(match.str());
    }

    return result;
}

bool loadFromFile(const std::string& fileName, Words& words)
{
    std::ifstream file(fileName);

    if (!file)
    {
        return false;
    }

    for (std::string word; file >> word;)
    {
        ++words[getToken(word.cbegin(), word.cend())];
    }

    return true;
}

template<typename T>
void showResult(const T& begin, const T& end)
{
    std::vector<T> words;

    words.reserve(std::distance(begin, end));

    for (auto i = begin; i != end; ++i)
    {
        words.push_back(i);
    }

    std::sort(words.begin(), words.end(),
        [&](const T& it1, const T& it2)
    {
        return it1->second > it2->second;
    });

    int x = 0;

    for (const auto& i : words)
    {
        if (x++ == 0)
        {
            std::cout << "\nThe most repeated element is: " << i->first << "\n\n";

            std::cout << " Word\tRepeated Times";

            std::cout << '\n' << std::setfill('-') << std::setw(23) << '\n';
        }

        std::cout << ' ' << std::setfill(' ')
            << std::setw(10) << std::left << i->first
            << std::setw(6) << std::internal << i->second << '\n';
    }
}

int main(int argc, char *argv[])
{
    Words words;

    for (int i = 1; i < argc; ++i)
    {
        if (!loadFromFile(argv[i], words))
        {
            std::cerr << "Can't open the file " << argv[i] << '\n';
        }
    }

    showResult(words.begin(), words.end());
}

Overall, this looks pretty nice. There are few minor things that can be improved though, about this part:

int x = 0;

for (const auto& i : words)
{
    if (x++ == 0)
    {
        std::cout << "\nThe most repeated element is: " << i->first << "\n\n";

        std::cout << " Word\tRepeated Times";

        std::cout << '\n' << std::setfill('-') << std::setw(23) << '\n';
    }

    // ...
}

i is customary for loop variables that are simple counters.
In this case it is a word (well, sort of),
so it would be better to name it as such.

The variable x is a bit confusing:

its name tells nothing of its purpose
it's important for the first iteration of the loop
... but it keeps counting during all iterations

It would be clearer and better this way:

bool first = true;

for (const auto& word : words)
{
    if (first)
    {
        std::cout << "\nThe most repeated element is: " << word->first << "\n\n";

        std::cout << " Word\tRepeated Times";

        std::cout << '\n' << std::setfill('-') << std::setw(23) << '\n';

        first = false;
    }

    // ...
}


Parallelizing an algorithm with OpenMP using a dynamic work queue I'm looking for comments on the design, correctness and performance (not so much style) of a dynamic work queue for OpenMP worker threads.

I have an algorithm that can be thought of in terms of some number of work items (how many is not known beforehand), each of which is executed and may then spawn two child work items. I start with a root work item and continue until there are no more tasks, then terminate. Tasks that are not ancestor and descendant are independent (and therefore can be run in parallel).

I want to use OpenMP to parallelize the work by having threads pop work from a queue. The difficult bit is:

waiting for work to become available in an efficient way
terminating when there are no work items left, and new ones can't be created any more, but not before

I'm most concerned about the correctness of the termination condition and of my use of the OpenMP functions.

In the version below, the work items are dummies, but the idea is that you could drop in arbitrary work (as long as mutually non-ancestral work is independent).

#include <mutex>
#include <condition_variable>
#include <stack>

#include "omp.h"

using namespace std;

// Dummy nlogn algorithm work item
class Work {
public:
    Work() : n() {}
    Work(int n) : n(n) {}

    // Returns true iff child work created
    bool go(Work& childA, Work& childB) {
        if (n > 1) {
            childA = Work(n - 1);
            childB = Work(n - 1);
            return true;
        }
        return false;
    }

    int n;
};

int main() {
    Work rootWorkItem(20);

    int numWaiting = 0;
    std::mutex m;
    std::condition_variable cv;
    std::stack<Work> workStack;

    workStack.push(rootWorkItem);

#pragma omp parallel
    while (true) {
        std::unique_lock<std::mutex> lock(m);

        if (workStack.empty()) {
            // Register as waiting for work
            numWaiting++;

            // If everybody is now waiting, it means that no one has more work to push
            if (numWaiting >= omp_get_num_threads()) {
                cv.notify_all();
                break;
            }

            // Wait for one of two things:
            //  a) more work has been pushed to the stack
            //  b) everything's done
            while (true) {
                cv.wait(lock);
                if ((numWaiting >= omp_get_num_threads()) || !workStack.empty()) break;
            }

            // If it was b), exit
            if (numWaiting >= omp_get_num_threads()) break;

            // Otherwise, tell everybody that we're no longer waiting
            numWaiting--;
        }

        // Pop a work item to start executing
        Work work = workStack.top();
        workStack.pop();

        lock.unlock();

        // Execute work and, if it spawned children, push them
        Work childA, childB;
        if (work.go(childA, childB)) {
            // Push child work items and tell somebody to get working on them
            lock.lock();
            workStack.push(childA);
            workStack.push(childB);
            cv.notify_one();
            lock.unlock();
        }
    }

    return 0;
}

Firstly, I know you said you're not so interested in a style review, but:

using namespace std;

Apart from being harmful, this isn't even bringing any benefit.  We can just drop it with no changes to the rest of the code.

And if OpenMP is correctly installed, the header should be on the include path (not in your source code location):

#include <omp.h>

The only thing we use from <omp.h> is omp_get_num_threads(); we can avoid needing that if we change the sense of the numWaiting variable, so we get to compare against zero instead:

    unsigned int num_working = 0;

#pragma omp parallel
{
#pragma omp single
    ++num_working;

    while (true) {
        std::unique_lock<std::mutex> lock(m);

        if (workStack.empty()) {
            --num_working;

            if (num_working == 0) {
                cv.notify_all();
                break;
            }

            while (true) {
                cv.wait(lock);
                if (num_working == 0 || !workStack.empty()) break;
            }

            if (num_working == 0) break;

            ++num_working;
        }

Instead of the #pragma omp single, we could make num_working be a std::atomic<unsigned> instead.

When we add two items to the work queue, we only wake up one worker thread.  We need to wake up a thread for each child, potentially:

        workStack.push(childA);
        cv.notify_one();
        workStack.push(childB);
        cv.notify_one();

Possibly a style issue, but the while (true) loop looks better as a do ... while:

            do {
                cv.wait(lock);
            } while (num_working > 0 && workStack.empty());


Custom strcat() with different arguments I am teaching myself C, and feel like I am just starting to get the hang of pointers and arrays (I come from Python, where everything is magic).  I'm looking for reviews, especially if I'm doing anything wrong.  In this code I wrote my own strcat() function, though it needs 3 args instead of the standard 2 (I couldn't figure out how to do it with just 2 without overrunning allotted memory).

#include <stdio.h>
#include <string.h>

char* cat(char *dest, char *a, char*b)
{
    int len_a = strlen(a);
    int len_b = strlen(b);
    int i;
    for(i = 0; i < len_a; i++)
    {
        dest[i] = a[i];
    }
    puts("");
    int j;
    for(j = 0;j < len_b; i++, j++)
    {
        dest[i] = b[j];
    }
    dest[i] = '\0';
    puts("FUNCTION FINISHED");
}

int main()
{
    char strA[] = "I am a small ";
    char strB[] = "cat with whiskers.";
    char strC[strlen(strA) + strlen(strB) + 1];
    printf("length A: %lu, B: %lu, C: %lu\n", strlen(strA), strlen(strB), strlen(strC));
    printf("sizeof A: %lu, B: %lu, C: %lu\n", sizeof(strA), sizeof(strB), sizeof(strC));
    printf("A: '%s'\nB: '%s'\n", strA, strB);
    cat(strC, strA, strB);
    printf("c: '%s'\n", strC);
    printf("length A: %lu, B: %lu, C: %lu\n", strlen(strA), strlen(strB), strlen(strC));

    return 0;
}

char* cat(char *dest, char *a, char*b)

Interface critique: You should have the caller specify a maximum size for the destination buffer, and error out when there is not enough space.  The mark of a good C programmer is to create interfaces which make this sort of condition unambiguous, rather than blasting away on the buffer, potentially past the allocation size.

for(i = 0; i < len_a; i++)
{
    dest[i] = a[i];
}

Strictly speaking this is fine, but it is rather un-C-like.  I would prefer:

while (*a)
   *dest++ = *a++;

With this you do not need to call strlen, either.

Assuming you added the parameter you should add in my interface critique (let's call the new parameter destsz), you could make sure you don't write more than this size with something like:

int cat(char *dest, size_t destsz, const char *a, const char *b)
{
    while (*a && destsz)
    {
       *dest++ = *a++;
       --destsz;
    }

    while (*b && destsz)
    {
       *dest++ = *b++;
       --destsz;
    }

    if (!destsz)
       return -1; // ran out of buffer; error condition

    *dest = 0;   // we have space, so write NUL
    return 0;
}


Enumeration of random trees I'm interested in recursive generation of trees in Python.  For my eventual application, it's important that the trees be represented as a list of nodes (rather than say a dictionary, or an edge list, or some other format).  Also, in my eventual application, each node of the tree will have between 0 and hundreds of children.  In this skeleton code, the number of children for each node is generated randomly.

The trees generated have a parameter-defined maximum depth, but because even nodes not at the maximum depth might have no children, some leaves will be closer to the root than others.

I wrote this function for the task:

import random

def generate_random_tree(nodelist=[], idx=0, parent=None, depth=0, max_children=2, max_depth=2):
    """Build a list of nodes in a random tree up to a maximum depth.
        :param:    nodelist     list, the nodes in the tree; each node is a list with elements [idx, parent, depth]
        :param:    idx          int, the index of a node
        :param:    parent       int, the index of the node's parent
        :param:    depth        int, the distance of a node from the root
        :param:    max_children int, the maximum number of children a node can have
        :param:    max_depth    int, the maximum distance from the tree to the root"""
    if depth < max_depth and depth >=0:
        # add a random number of children
        n = random.randint(0, max_children)
        nodelist.extend([[idx+i, parent, depth] for i in xrange(n)])

        # for each new child, add new children
        [generate_random_tree(nodelist, len(nodelist), idx+i, depth+1, max_children, max_depth) for i in xrange(n)]

    elif depth == max_depth:
        # add a random number of leaves
        n = random.randint(0, max_children)
        nodelist.extend([[idx+i, parent, depth] for i in xrange(n)])
        return

    else:  # this should never happen
        raise ValueError('Algorithm halted because depth > max_depth or depth < 0.')
        return

The function is used like this:

tree =[[0, None, 0]]  # the algorithm starts with a root node which has no parents and depth 0
random.seed(0)
generate_random_tree(nodelist=tree, idx=len(tree), parent=0, depth=1, max_children=3, max_depth=3)

[0, None, 0]
[1, 0, 1]
[2, 0, 1]
[3, 0, 1]
[4, 1, 2]
[5, 1, 2]
[6, 1, 2]
[7, 4, 3]
[8, 5, 3]
[9, 6, 3]
[10, 6, 3]
[11, 2, 2]
[12, 11, 3]
[13, 11, 3]
[14, 11, 3]
[15, 3, 2]
[16, 15, 3]

This function does the task, but I'm eager for feedback on the quality of this implementation.  Any feedback is welcome, of course, but particular questions I have include:

Are there any better ways to find appropriate indices for each new node other than calling len()?
Are there simple, recursive Python implementations that return values rather than relying on list mutability?
(This may be out of scope for se.cr; if so, please ignore)  Is there a way to get the enumeration to be depth-first rather than the breadth-first implementation I currently have?

Although this code isn't going to go into a production in environment or be worked on by teams of professional software engineers, high-level comments about readability, best practices, and hidden corner cases would be much appreciated.

This is really nicely written code! I do have a few small tips, and then I'll try to answer some of your small questions.

I noticed from looking at your code, that you only use the random.randint function from the random module/library. Rather than importing the entire random module, you can just do from random import randint.
In your else block at the very end of your function, you have a return after you raise an exception. Raising an exception will exit the program, so this return can be removed entirely.
You also mention in a comment by the else block, that this will never happen. If it never happens, then why do you need it? It can be removed as well.
I did find something odd about this function. Underneath the comment # for each new child, add new children you have an expression that's evaluated, but you don't return the value of the expression. Preferably, this line should be changed to return [ ... ].
Finally, using len to find the new appropriate indices is really the only good option, right now. You can always do tree[len(tree) - 1].index() + 1, but that's horridly unclear. Just stick with len.


Extract PNGs embedded in a file My approach was to find each occurrence of the PNG's file signature followed by its end of file (EOF) and write the bytes between to a new file whose name is simply a counter starting at zero.

use std::env;
use std::fs::File;
use std::io::prelude::*;

const SIGNATURE: [u8; 8] = [137, 80, 78, 71, 13, 10, 26, 10];
const EOF: [u8; 8] = [73, 69, 78, 68, 174, 66, 96, 130];

fn main() {
    let path = env::args().nth(1).unwrap();
    let mut f = File::open(path).unwrap();

    let mut buf = Vec::new();
    f.read_to_end(&mut buf).unwrap();

    let mut iter = buf.iter();
    let mut i = 0;

    while let Some(start) = iter.rposition(|&x| x == SIGNATURE[0]) {

        if buf[start..].starts_with(&SIGNATURE) {

            let mut iter = buf[start..].iter();

            let mut end = iter.position(|&x| x == 130).unwrap();

            loop {
                let slice = &buf[start..start + end + 1];
                if slice.ends_with(&EOF) {
                    let mut f = File::create(i.to_string() + ".png").unwrap();
                    f.write_all(slice).unwrap();
                    i += 1;
                    break;
                }

                end += match iter.position(|&x| x == 130) {
                    Some(x) => { x + 1 },
                    None => break,
                };
            }
        }
    }
}

The only reason I used rposition instead of position for start was because the file I was working with had all its PNG's embedded at the end.

I had attempted to replace some of the unwraps with try!s but realized that the macro needs to be called from a function that returns a Result, i.e. can't be used in fn main(), and couldn't figure out how best to break up the code.

Was wondering if there might be a better way to approach the problem. If not, how can I at least clean up this implementation?

Use expect instead of unwrap. This gives you and your users
a better chance at figuring out what went wrong. It's also one step closer
to good error reporting and handling.
Extract an inner_main that returns a Result and thus allows
you to use try!. main can call that method, pattern match on the
Result, print the failure message, have an exit code, etc.
To start with, return a Result<_, Box<Error>>. Box<Error> is an easy
type to build, and try! can convert to it automatically.
Once you are returning Results, theexpects can be transformed into a
ResultusingOption::ok_or`.
One Rust-specific way to think about splitting up functions is
to constrain mutability. Extracting out loading the file allows the
Vec to be mutable in the smallest possible scope.
It may be over engineering, but creating an iterator to handle
finding the embedded PNGs helps separate concerns. For example, I
didn't originally see that i wasn't part of the main finding
logic. It would also allow you to create more focused unit tests on
just this complicated functionality.
The search algorithm itself isn't super efficient; it doesn't
skip as much data as it could in certain places, it seems to always
scan through to the end of the file. What if your data was
something like SIG ... SIG ... SIG ... EOF?
The magic number 130 for the end position is duplicated.
Use a crate like twoway to do
the heavy lifting of searching for byte substrings. This takes care of a
lot of the annoying details.
The data is sliced for the same range multiple times. Any array access is a tiny bit expensive as it has to do range checks. Doing it once is good for both programmer sanity and for the tiny gain in speed.
Using format! to construct the file name may be more obvious than adding a string slice to a String.

extern crate twoway;

use std::error::Error;
use std::fs::File;
use std::io::prelude::*;
use std::path::Path;
use std::{env, process};

const SIGNATURE: [u8; 8] = [137, 80, 78, 71, 13, 10, 26, 10];
const EOF: [u8; 8] = [73, 69, 78, 68, 174, 66, 96, 130];

fn load_file<P>(path: P) -> Result<Vec<u8>, Box<Error>>
    where P: AsRef<Path>
{
    let mut f = try!(File::open(path));

    let mut buf = Vec::new();
    try!(f.read_to_end(&mut buf));
    Ok(buf)
}

struct EmbeddedPng<'a>(&'a [u8]);

impl<'a> Iterator for EmbeddedPng<'a> {
    type Item = &'a [u8];

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            match twoway::rfind_bytes(self.0, &SIGNATURE) {
                None => return None,
                Some(start_idx) => {
                    let (before, after) = self.0.split_at(start_idx);
                    self.0 = before;

                    if let Some(end_idx) = twoway::find_bytes(after, &EOF) {
                        let png_data = &after[..end_idx + EOF.len()];
                        return Some(png_data)
                    }
                }
            }
        }
    }
}

fn inner_main() -> Result<(), Box<Error>> {
    let path = try!(env::args().nth(1).ok_or("No filename provided"));
    let buf = try!(load_file(path));

    for (i, png_data) in EmbeddedPng(&buf).enumerate() {
        let fname = format!("{}.png", i);
        let mut f = try!(File::create(fname));
        try!(f.write_all(png_data));
    }

    Ok(())
}

fn main() {
    if let Err(e) = inner_main() {
        println!("{}", e);
        process::exit(1);
    }
}


Idiomatic IO in Haskell I'm working through Yet Another Haskell Tutorial. One of the exercises is to prompt the user to enters numbers, entering a 0 to quit. The program should then both sum and multiply all the given numbers, and then display the factorial of each.

It works, but it's obviously sloppy, with some functions doing more than what is obvious. My main concern is whether it's better to try to format output in the nonpure IO functions, or to do it in the pure functions. Should I separate out calculating the data and formatting the output? Any other tips for how I could tighten this up?

module Main
  where

import System.IO

main = do
  hSetBuffering stdin LineBuffering
  putStrLn "Enter a number, or 0 to quit: "
  numList <- getNumbers
  putStrLn (my_sum numList)
  putStrLn (my_product numList)
  putStrLn (factorial numList)

getNumbers = do
  number <- getLine
  let n = read number :: Int
  if n == 0
    then do
      return []
    else do
      numList <- getNumbers
      return (n : numList)

my_sum [] = "The sum is 0"
my_sum xs = "The sum is " ++ show (foldr (+) 0 xs)

my_product [] = "The product is 0"
my_product xs = "The product is " ++ show (foldr (*) 1 xs)

factorial (x:xs) = show x ++ " factorial is " ++ show (fac x) ++ "\n"
  ++ factorial xs
factorial [] = ""

fac 1 = 1
fac x = x * fac (x - 1)

You should definitely separate the calculation from formatting the output. One of Haskell's key strengths is being able to compose functions. By confounding the definition of your function with the presentation of it's return value, you lose the ability to reuse it elsewhere. For instance, if you wanted to use my_sum to sum all of the numbers you were given, and then find the factorial of the sum, you couldn't with your code as-is without reimplementing both functions! Here's a composable definition of my_sum.

my_sum xs = foldr (+) 0 xs

Now when you want to write out to the command line what operation your program has performed, you can format the output in IO, or call a formatting operation (that's what show is).

main = do
    ...
    putStrLn $ "The sum of the numbers you entered is " ++ show (sum numList)
    ...

Now more general advice, you should include a type signature for all of your top-level definitions. This is important for a few reasons. One, it acts as a check on your understanding of what your functions are doing, the compiler will complain if your signature doesn't match what your function really does. Two, it serves as a surprisingly powerful form of documentation for readers of your code. And three, it can help the compiler infer more of the types you use within functions without needing annotations.

As an example of that last point, look at how you had to annotate the line let n = read number with :: Int. If you had given the compiler enough information to go on elsewhere in your program, it would have been able to deduce that on its own. Here's how.

getNumbers :: IO [Int] -- 1) Type signature for the IO action
getNumbers = do
  number <- getLine
  let n = read number -- 3) The type checker sees that n is a part of the returned list, so it must be an Int
  if n == 0
    then do
      return []
    else do
      numList <- getNumbers
      return (n : numList) -- 2) Here's the list of Ints we're returning per the type signature

You shouldn't have to set stdin to LineBuffering mode at the start of main. getLine will work correctly by default.

getNumbers isn't properly tail-recursive, the recursive call to getNumbers is followed by that return action. In this example it won't make much of a difference, but in a real program where you can expect a large amount of data this would end up blowing up the stack.

Here's the version I ended up producing taking all of the above into account. Read closely and try to make note of all the differences between both versions!

module Main where

main :: IO ()
main = do
    putStrLn "Enter one number per line, or 0 to stop: "
    numbers <- getNumbers
    putStrLn "The sum of your numbers is " ++ show (my_sum numbers)
    putStrLn "The product of your numbers is " ++ show (my_sum numbers)
    forM_ numbers $ \n -> putStrLn "The factorial of " ++ show n ++ " is " ++ show (fac n)

getNumbers :: IO [Int]
getNumbers = do
    number <- getLine
    let n = read number
    if n == 0
        then return []
        else fmap (n:) getNumbers

my_sum :: [Int] -> Int
my_sum = foldr (+) 0

my_product :: [Int] -> Int
my_product = foldr (*) 1

fac :: Int -> Int
fac 1 = 1
fac n = n * fac (n - 1)


How can I optimize my code that uses nested for loops? I am working to solve a problem where I need to determine if a Point lies on a line connecting two other Points.  For example, if I have Point a, b, c, I want to determine if c is on the line segment connecting a and b.  In my code, I have a point, me (a in the example) and two lists of points, hits (b in the example) and reachable (c in the example).  For each point in hits, I want to determine if there is any point in reachable that is on the line segment that connects me and the point in hits. If there is a point on that line segment, then numHits needs to be decremented. Here is my code:

Point me; //Point a from the example above
ArrayList<Point> hits = new ArrayList<>();  //a list of Point b's from the example above
ArrayList<Point> reachable = new ArrayList<>();  //a list of point c's from the example above

for(Point hit : hits) {
    for(Point p : reachable) {
        if(!hit.equals(p) && !me.equals(p)) {
            //find the equation of a line from me to hit
            if(hit.x - me.x == 0) { //if the line has an undefined slope... if the line is vertical
                if( (((p.y <= hit.y) && (p.y >= me.y)) || ((p.y >= hit.y) && (p.y <= me.y))) && p.x - me.x == 0) {  //if there is any occupied point on that line in between me and the hit, that point blocks the hit
                    numHits--;
                    break;
                }
            } else {
                //create a line from me to the hit... if there is any occupied point on that line in between me and the hit, that point blocks the hit
                double deltaY = hit.y - me.y;
                double deltaX = hit.x - me.x;

                double m = deltaY / deltaX; //slope
                double b = me.y - (double)(m*me.x);  //y intercept

                if((double) p.y == ((double)(m * p.x) + b)) {  //if this point is on the same line
                    if( ((p.x <= hit.x && p.x >= me.x) && (p.y <= hit.y && p.y >= me.y)) ||
                                ((p.x <= hit.x && p.x >= me.x) && (p.y >= hit.y && p.y <= me.y)) ||
                                ((p.x >= hit.x && p.x <= me.x) && (p.y >= hit.y && p.y <= me.y)) ||
                                ((p.x >= hit.x && p.x <= me.x) && (p.y <= hit.y && p.y >= me.y))) {  //if the point is in between me and the hit
                        numHits--;
                        break;
                    }
                }
            }
        }
    }
}

My code works to determine if there is any point in reachable between me and each point in hits, it just gets incredibly slow the larger hits and reachable get.  For example, if hits has a size of 780,000 and reachable has a size of 1,500,000 the code takes a very long time to run.  I was wondering how I may be able to optimize this to run more quickly.  I'm not sure if the bottleneck issue lies in the loops themselves or in the code within the loops.  Any help or optimization ideas are greatly appreciated.  Thank you!

It is normally good to break code into several methods.
Everything that is inside your

if(!hit.equals(p) && !me.equals(p))

should be moved to a separate method taking as input those 3 points a,b and c

When coding problems of a mathematical flavor it is often very useful to support your code with some kind of theory.

In this case you might want to look up the mathematical terms "dot product" and "cross product". Once you understand those it becomes easy to implement your function.

And remember to make several functions (dotProduct() and crossProduct()) so you can reuse code later.

When it comes to performance you need to look at your algorithm.
There is no need to test all pairs of points (hit, p).
Maybe you should make a small method that computes the angle of a vector from me to p? If angle is the same they hit, otherwise they miss.

So the question becomes given a list of angles for points in hits and a list of angles in reachable, do they contain a common angle?


Wordpress RSS Parser Follow Up to my earlier question.

This is an RSS Parser intended only to parse the feed Wordpress provides (and even then, only what I actually want to display on my website). System.Linq.Xml and System.ServiceModel.Syndication are unavailable because I'm targeting .Net Core instead of the full framework.

I think I've achieved a more idiomatic implementation this time. Where can I improve? Are there opportunities to compose higher order functions that I'm missing?

Rss.fs

module Rss
    open System

    type Item = {
        Title: string
        Link: Uri
        Comments: Uri
        PublishDate: DateTimeOffset
        Description: string
    }

    type Channel = {
        Title: string
        Link: Uri
        Description: string
        LastBuildDate: DateTimeOffset
        Items: seq<Item>
    }

    type RssFeed = {
        Version: double
        Channel: Channel
    }

    open System.Xml
    let parse input =

        // Helper Functions
        let innerText (elementName: string) (node: XmlNode) =
            let element = node.Item elementName
            element.InnerText

        let titleText node =
            node |> innerText "title"

        let descriptionText node =
            node |> innerText "description"

        let elementAsDateTimeOffset elementName node =
            node |> innerText elementName |> DateTimeOffset.Parse

        let elementAsUri elementName node =
            node |> innerText elementName |> Uri

        let linkUri node =
            node |> elementAsUri "link"

        let itemNodeToItem node = {
            Title = node |> titleText
            Link =  node |> linkUri
            Comments = node |> elementAsUri "comments"
            PublishDate = node |> elementAsDateTimeOffset "pubDate"
            Description = node |> descriptionText
         }

        // Load the document and begin parsing
        let document = XmlDocument()
        document.LoadXml input

        let rss = document.DocumentElement
        let channelNode = rss.FirstChild

        let items =
            channelNode.ChildNodes
            |> Seq.cast<XmlNode>
            |> Seq.filter (fun node -> node.Name.Equals "item")
            |> Seq.map itemNodeToItem

        let channel = {
            Title = channelNode |> titleText
            Link = channelNode |> linkUri
            Description = channelNode |> descriptionText
            LastBuildDate = channelNode |> elementAsDateTimeOffset "lastBuildDate"
            Items = items
        }

        let version =
            (rss.Attributes.ItemOf "version").Value
            |> Double.Parse

        let rssFeed = {Version = version; Channel = channel}
        rssFeed

Controllers/BlogController.fs

namespace theupsyde.Controllers

open System
open System.Collections.Generic
open System.Linq
open System.Threading.Tasks
open Microsoft.AspNetCore.Mvc
open Rss
open System.Net

type BlogController () =
    inherit Controller()

    let fetchUrl url = async {
        let req = WebRequest.Create(Uri(url))
        use! resp = req.GetResponseAsync() |> Async.AwaitTask
        use stream = resp.GetResponseStream()
        use reader = new IO.StreamReader(stream)
        return reader.ReadToEnd()
    }

    let rssFeed =
        fetchUrl "https://christopherjmcclellan.wordpress.com/feed/"
        |> Async.RunSynchronously
        |> Rss.parse

    let recent =
        rssFeed.Channel.Items

    member this.Index () =
        this.View(rssFeed.Channel)

    member this.Recent() =
        this.PartialView("BlogPosts", recent)

    member this.Latest () =
        let latest =
            recent
            |> Seq.head

        this.PartialView("BlogPost", latest)

The Rss helper functions are inside the parse function, even though they don't use any of the state inside that scope. Consider moving these up to the module level, even though they are not used anywhere else. By doing this the main function is shorter and easier to follow. You could also make those functions private when you pull them out.
Seq.cast can throw an exception. Even though you know that every item will be an XmlNode in this case, it can be safer to filter out objects that are not of the required type while casting. Unfortunately, F# doesn't have a function for this in the Seq module but you can always use the one already in .NET: channelNode.ChildNodes |> System.Linq.Enumerable.OfType<XmlNode>

You fetch the RSS feed in the constructor of BlogController. This will happen once for each request. Using Async.RunSynchronously will block a thread, so you lose the benefit of using Async in the first place. You should avoid Async.RunSynchronously whenever you can. You can pull out the RSS fetching and parsing into another function that returns an async. Call this function from each controller method, do more async processing if necessary and then use Async.StartAsTask to return a task from the method. ASP.NET will then be able to run your code without unnecessary blocking.

EDIT:

I'm not too familiar with ASP.NET MVC, but based on this issue I think something like this should work:

let fetchRss() = async {
    let! content = fetchUrl "https://christopherjmcclellan.wordpress.com/feed/"
    return Rss.parse content }

type BlogController() =
    inherit Controller()

    member this.Index() = async {
        let! rss = fetchRss()
        return this.View(rss.Channel) }


Joining two IEnumerable I'm trying to merge two nodes. Basically, the idea is to take all children in left and new ones in right. Is there any way to get rid of toAdd variable and do it in a clean way?

I don't want to convert any IEnumerable<T> to List or Array in this merge process.

public IEnumerable<TChild> NodeMerge<TNode, TChild, TKey>(TNode left, TNode right,
Func<TNode, IEnumerable<TChild>> getChildren, Func<TChild, TKey> getKey)
{
    var lChildren = getChildren(left);
    var rChildren = getChildren(right);

    IEnumerable<TChild>[] toAdd = new IEnumerable<TChild>[2];

    // Common Keys between left and right
    toAdd[0] = lChildren.Where(s => rChildren.Select(p => getKey(p)).Contains(getKey(s)));

    // new keys added to right
    toAdd[1] = rChildren.Where(s => lChildren.Select(p => getKey(p)).Contains(getKey(s)) == false);

    return toAdd.SelectMany(s => s);
}

Little cleaner:

// Common Keys between left and right
var result = lChildren.Where(s => rChildren.Select(p => getKey(p)).Contains(getKey(s))).ToList();

// new keys added to right
result.AddRange(rChildren.Where(s => lChildren.Select(p => getKey(p)).Contains(getKey(s)) == false));

return result;

Without ToList():

public static IEnumerable<T> Merge<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
    foreach (var item in first)
        yield return item;

    foreach (var item in second)
        yield return item;
}

In your NodeMerge method:

return lChildren.Where(s => rChildren.Select(p => getKey(p)).Contains(getKey(s))).Merge(rChildren.Where(s => lChildren.Select(p => getKey(p)).Contains(getKey(s)) == false));


Delayed dispatcher invoke I knocked this up quickly to allow delayed Invoke on the dispatcher. Along with canceling the existing invocation and replacing with a new one, this allows throttling an action.

public static class DispatcherExtensions
{
    private static Dictionary<string, DispatcherTimer> timers = new Dictionary<string, DispatcherTimer>();
    private static object syncRoot = new object();

    public static void DelayInvoke(this Dispatcher dispatcher, string namedInvocation,
        Action action, TimeSpan delay, DispatcherPriority priority = DispatcherPriority.Normal)
    {
        lock (syncRoot)
        {
            DispatcherTimer timer = null;
            if (timers.TryGetValue(namedInvocation, out timer))
            {
                timer.Stop();
                timer.IsEnabled = false;
                timers.Remove(namedInvocation);
            }
            timer = new DispatcherTimer(priority,dispatcher)
            {
                Interval = delay
            };
            timer.Tick += (s, e)
                =>
                {
                    action();
                };
            timers.Add(namedInvocation, timer);
            timer.IsEnabled = true;

        }
    }
}

I'm not an expert on multithreading at all, but I've attempted refactoring your code a bit.
First of all, to code defensively, I suggest adding the readonly modifier to your lock object. It's not required but will prevent accidental assignments:

private static readonly object syncRoot = new object();

I'm against incurring the complexity of an out argument: let's just check if the timer exists. We can stop it and remove it if it does; setting DispatcherTimer.IsEnabled isn't necessary because DispatcherTimer.Stop() sets it to false anyway:

if (timers.ContainsKey(namedInvocation))
{
    timers[namedInvocation].Stop();
    timers.Remove(namedInvocation);
}

We can get rid of the object initializer because DispatcherTimer has the perfect constructor for us anyway; this has the added benefit of inlining the lambda:

var timer = new DispatcherTimer(delay, priority, (s, e) => action(), dispatcher);
timer.Start();
timers.Add(namedInvocation, timer);

Again, remember we don't need to set IsEnabled because DispatcherTimer.Start() sets it to true for us (alternatively, you can leave it in place but remove the call to Start(). But the method call seems more intuitive to me; setting a property doesn't make it obvious that the timer has been started).

You may have noticed I used var wherever it seemed appropriate; it's just as type safe as using the actual type but takes up less space, both on the page in in my brain.

That leaves us with the following end result:

public static class DispatcherExtensions
{
    private static Dictionary<string, DispatcherTimer> timers =
        new Dictionary<string, DispatcherTimer>();
    private static readonly object syncRoot = new object();

    public static void DelayInvoke(this Dispatcher dispatcher, string namedInvocation,
        Action action, TimeSpan delay,
        DispatcherPriority priority = DispatcherPriority.Normal)
    {
        lock (syncRoot)
        {
            if (timers.ContainsKey(namedInvocation))
            {
                timers[namedInvocation].Stop();
                timers.Remove(namedInvocation);
            }
            var timer = new DispatcherTimer(delay, priority, (s,e) => action(), dispatcher);
            timer.Start();
            timers.Add(namedInvocation, timer);
        }
    }
}

In case I introduced a bug or if you have improvements, let me know in the comments.

Edit: supporting cancellation

(@svick's suggestion)

To provide the possibility of cancelling your timers, you would factor out the timer removing logic (I inverted the condition to reduce nesting...) into a new method that is called at the beginning of DelayInvoke.

private static void RemoveTimer(string namedInvocation)
{
    if (!timers.ContainsKey(namedInvocation)) return;
    timers[namedInvocation].Stop();
    timers.Remove(namedInvocation);
}

Then, you'd create another extension method (first parameter is useless, but calling the method via the Dispatcher is consistent and convenient, so I left it there). Something like this:

public static void CancelNamedInvocation(this Dispatcher dispatcher, string namedInvocation)
{
    lock(syncRoot)
    {
        RemoveTimer(namedInvocation);
    }
}


Updating list of string while other threads are reading from it I have a logging solution that writes down the hashes of messages. I consider some of these hashes to be safe and I want to skip logging those. I have implemented a whitelist that is a directory containing whitelisted hashes. There is a timer task that updates that list every 10 minutes.

I have tried testing it from multiple angles, but experience shows that it is near to impossible to generate the load with the diversity that I see in the wild. So could someone point out any shortcomings in my approach, only relevant parts showed:

public class MyLogger {

    private volatile AtomicReference<List<String>> whitelist = new AtomicReference<List<String>>();

    private void startWhitelistListener() {
        new Timer().scheduleAtFixedRate(
                new TimerTask() {
                    @Override
                    public void run() {
                        updateWhitelist();
                    }
                }, 1000, 60 * 10 * 1000
        );
    }

    private void updateWhitelist() {
        try{
            ArrayList<String> tempList = new ArrayList<String>();
            for (File f : scriptWhitelistDirectory.listFiles()){
                tempList.add(f.getName());
            }
            whitelist.set(tempList);
        } catch (Throwable ignore){}
    }
....
}

Now there will be threads accessing the whitelist like:

if (whitelist.get().contains(hash)) return null;

Is the implementation thread safe?

Yes if you only read the whitelist.

You can guarantee this at runtime by wrapping it in Collections.unmodifiableList while setting.

whitelist.set(Collections.unmodifiableList(tempList));

However because you don't use any other feature of the AtomicReference other than get and set, you don't need AtomicReference at all (or if you do it should be final); just volatile is enough:

private volatile List<String> whitelist = Collections.emptyList();//empty dummy list

whitelist = Collections.unmodifiableList(tempList);

And check with if (whitelist.contains(hash)) return null;

That leads me to the list itself; if you only check whether a values is contained within the list then you should consider changing the list to a HashSet.

private volatile Set<String> whitelist = Collections.emptySet();

Set<String> tempList = new HashSet<String>();
for (File f : scriptWhitelistDirectory.listFiles()){
    tempList.add(f.getName());
}
whitelist = Collections.unmodifiableSet(tempSet);


Multithreaded log test I'm writing a logger extension that allows multiple threads to log a process, and then dump that log to the main log in one atomic operation. The point of it is to make the logs easier to read when many threads are executing. Is this test valid and clear or not?

/**
 * Test that thread logs do not interlace
 * @throws InterruptedException
 */
@Test
public void testDumpMultithreaded() throws InterruptedException {
    Thread t1 = new Thread() {
        @Override
        public void run() {
            logger.bufferedMessages.get().add("t1: One");
            logger.bufferedMessages.get().add("t1: Two");
            logger.bufferedMessages.get().add("t1: Three");
            logger.dump();
        }
    };

    Thread t2 = new Thread() {
        @Override
        public void run() {
            logger.bufferedMessages.get().add("t2: One");
            logger.bufferedMessages.get().add("t2: Two");
            logger.bufferedMessages.get().add("t2: Three");
            logger.dump();
        }
    };

    t1.start();
    t2.start();

    t1.join();
    t2.join();

    Iterator<String> i = logger.messages.iterator();
    boolean t1Correct = false;
    boolean t2Correct = false;

    while (i.hasNext()) {
        if (i.next().equals("t1: One")) {
            t1Correct = true;
            t2Correct &= i.next().equals("t1: Two");
            t2Correct &= i.next().equals("t1: Three");
        }
    }

    i = logger.messages.iterator();
    while (i.hasNext()) {
        if (i.next().equals("t2: One")) {
            t2Correct = true;
            t2Correct &= i.next().equals("t2: Two");
            t2Correct &= i.next().equals("t2: Three");
        }
    }

    assertEquals("Thread one's log not consecutive: ", true, t1Correct);
    assertEquals("Thread two's log not consecutive: ", true, t2Correct);
}

A barrier can ensure the threads execute in an interleaved fashion.

final CyclicBarrier rendezvous = new CyclicBarrier(2);
final CyclicBarrier conclusion = new CyclicBarrier(3);
Thread a = new Thread() {
    public void run() {
         try {
             rendezvous.await();
             // do your stuff
             // do your stuff
             rendezvous.await(); // if you want to be extra sure the ops are interleaved
             // do your stuff
         } catch (...) {}
         finally { conclusion.await(); }
    }
};

Thread b = new Thread() {
    public void run() {
         try {
             rendezvous.await();
             // do your other stuff
             // do your other stuff
             rendezvous.await(); // if you want to be extra sure the ops are interleaved
             // do your other stuff
         } catch (...) {}
         finally { conclusion.await(); }
    }
};

a.start();
b.start();
conclusion.await();

assertTrue instead of assertEquals(.., true, ..).

cut and paste error has you modifying t2Correct instead of t1Correct


String algorithms and locale I am trying to write some string algorithms which I want to work for any kinds of strings and/or locale. I managed to get some results that do work, but I am not sure that what I am doing is idiomatic or anything. Here is a function:

template<typename String>
auto upper(String str,
           const std::ctype<typename String::value_type>& f =
           std::use_facet<std::ctype<typename String::value_type>>(std::locale{}))
    -> String
{
    f.toupper(&str[0], &str[0]+str.size());
    return str;
}

I have problems getting around the way C++ works with locales and UTF-8. This algorithm is intended to take a string (well, a range of characters with a standard string interface) and returning a copy of it with all the characters converted to uppercase according to a given locale. If no locale (ctype facet) is given, the last used locale is used.

Is there anyway to improve this code (taking locale vs facet) for examples so that it would be the most useful?

I think I'd prefer to have the user pass a locale instead of a facet. In most typical cases, a user will deal only with locales, not with the individual facets that make up a particular locale. It's also relatively easy for a user to create a locale on demand, so the code looks something like:

std::string input{"Now is the time for every good man to come of the aid of his country."};

std::string result = upper(input, std::locale("en-us"));

or:

std::string result = upper(input, std::locale(""));

...though I suppose we can probably expect that the default parameter will be used a lot more often than not, in which case all of this is moot.

Anyway, using a locale as the parameter lets us move the use_facet call inside the function body and use auto for it instead of writing out its full type:

auto const& f = std::use_facet<std::ctype<typename String::value_type>>(locale);

Not a huge change, but somewhat simpler nonetheless. Given that you're depending on String being contiguous and supporting random access, it might be worth considering making use of that a little more explicitly, by replacing &str[0]+str.size() with &str[str.size()].

Although I'm somewhat on the fence about it, I'm also less than excited about the idea of using a trailing return type when it's not actually necessary. Maybe it's just a sign of my age, but I still tend to prefer the return type in its traditional location when possible.

Putting all those together, we'd end up with something on this order:

template<typename String>
String upper(String str, std::locale const &locale = std::locale())
{
    auto const& f = std::use_facet<std::ctype<typename String::value_type>>(locale);
    f.toupper(&str[0], &str[str.size()]);
    return str;
}

I'm not sure anybody could call that a huge improvement, but I do think it's at least a minor one, especially in convenience to the user.


Database design for an online learning application It is an online learning application with different types of learnable items, that different users learn.

The users learn by spaced repetition (once right, wait a couple days, ask again), success is mirrored in stages and mistakes made.

I intend to use this for scientific data collection in the near future, so there is one table especially, user_terms_answers where data amasses at a granularity not currently used by the application.

I especially had trouble with figuring out how to arrange my learnable types, and I'm not sure if I chose the optimal solution.

Since this is potentially not understood just from looking at the chart, the two basic types are:

known – unknown: What year did Thomas Edison die? – [1931] - one question & one answer
cloze tests or gap texts: Slow loris are of the genus [Nycticebus] and of the subfamily [Lorinae] - one question & many answers!

My schema

The part in gray ships with the TankAuth component of CodeIgniter and I'm hoping that this is properly done already.

Database schema

In response to a now-gone comment by l0bo, I visualized this in SchemaSpy as well.

Common queries

These the views that I have so far, they reflect quite well what the application will usually want.
They also reflect how I run into trouble with the way I chose to implement "languages".

CREATE VIEW `retrieve_user_term_or_gap` AS
SELECT
  u.id, u.learnable_id, u.user_id, u.stage, u.mistakes, u.time_due, u.added,
  terms.language, terms.field, terms.known, terms.unknown, terms.hint,
  gaps.cloze_id, gaps.gap,
  c.language AS cloze_language, c.field AS cloze_field, c.cloze,
  c.hint AS cloze_hint -- this is bad, not 3NF
FROM
  user_terms AS u
LEFT JOIN learnables AS l ON u.learnable_id = l.id
LEFT JOIN terms ON l.id = terms.learnable_id
LEFT JOIN gaps ON l.id =  gaps.learnable_id
LEFT JOIN clozetests AS c ON c.id = gaps.cloze_id

CREATE VIEW `how_many_due` AS
SELECT COUNT(id) FROM user_terms
WHERE stage < 5 AND DATE(time_due) <= CURDATE()

CREATE VIEW `due_terms` AS
SELECT
  u.id, u.learnable_id, u.user_id, u.stage, u.mistakes, u.time_due, u.added,
  terms.language, terms.field, terms.known, terms.unknown, terms.hint,
  gaps.cloze_id, gaps.gap,
  c.language AS cloze_language, c.field AS cloze_field, c.cloze,
  c.hint AS cloze_hint -- this is bad, not 3NF
FROM
  user_terms AS u
LEFT JOIN learnables AS l ON u.learnable_id = l.id
LEFT JOIN terms ON l.id = terms.learnable_id
LEFT JOIN gaps ON l.id =  gaps.learnable_id
LEFT JOIN clozetests AS c ON c.id = gaps.cloze_id
WHERE DATE(u.time_due) <= CURDATE() AND u.stage < 5
ORDER BY terms.language, terms.field, u.id

You do have the field languages several times as a string. I'd create a general table languages with all language-related informations and have 1:m or n:m relations to other tables.


Using Fibonacci sequence to generate musical melodies I recently started picking up the Haskell programming language. I've managed to learn other languages rather quickly, but I'm still having a difficult time grasping some of the basics of Haskell.

I decided to practice and wrote a program that calculates the Fibonacci Sequence (original, I know) a certain amount of times and adds the results to a list, then divides each number in the list by 7 and creates a new list of the remainders of that division. It then assigns a musical note letter based in A minor (A, B, C, D, E, F, and G), and prints out each letter. The idea was to give me new ideas for writing melodies.

The program works, but with how efficient Haskell is I feel like it's way too long for what it does. How would you guys suggest re-writing this and what are some shortcuts I can use to write better code?

Here's the program:

import Data.List
import System.IO

fibo a b = a:fibo b (a+b)
divBy7 x = x `mod` 7
calcNums = take 16 $ map divBy7(fibo 0 1)
returnNote :: Int -> String
returnNote n
  | (n == 0) = "A"
  | (n == 1) = "B"
  | (n == 2) = "C"
  | (n == 3) = "D"
  | (n == 4) = "E"
  | (n == 5) = "F"
  | (n == 6) = "G"
-- the number will never be higher than 6 due to the pisano period

output = map returnNote(calcNums)

I'm just running ghci and asking it to return output

fibo

fibo is a fine function, but I would suggest a more complete name like fibonacci just to make it 100% clear that it returns fibonacci numbers to someone that did not read your plaintext introduction.

divBy7

divBy7 is not a good function: it is trivial and most importantly does not do what it says. It returns the remainder of dividing by 7, not the result of dividing by 7. I would delete this function.

calcNums

calcNums is not general enough, I feel no need for the take 16 at the start of it, this function has the potential to calculate as many fibonacci mod 7 as you want, let the caller decide how many to take.

Incidentally fibonacciMod7 is a better name for the function as it says what it does: calcNums was way too general.

returnNote

returnNote is too verbose and fails badly (= with no meaningful error message) if I pass it anything bigger than 6.

returnNote n
  | n `elem` [0..6] = "ABCDEFG" !! n
  | otherwise = error "n will never be higher than 6 due to the pisano period. (And it must be positive)"

This implementation is more concise and incorporates the comment into the code so that it can be shown to the user when he uses the function incorrectly.


Template data types implementation I'm preparing for an exam on C++, as part of my preparation I want to implement a generic map without using anything from the STD for educational purposes.

Before jumping into implementation of everything, I want to know that the skeleton for my Map is solid and I use templates and template inheritance correctly.

Above is the skeleton of my Map.  I would like to get an opinion about that skeleton.

#ifndef  MAP_H_
#define MAP_H_

template <class K, class V>
class Map {
public:
    /*
        Map c'tors and d'tors.
    */
    Map(); //C'tor
    Map(const Map& map); //Copy c'tor
    ~Map(); //D'tor

    /*
        Map methods
    */
    void insert(const K& key, const V& value);
    bool isIn(const K& key) const;
    void remove(const K& key);
    void clear();
    bool isEmpty();
    int size() const;

    template <class F>
    Map filter(F& filterFunction);

    /*
        Map methods using Iterators
    */
    class Iterator;
    class ConstIterator;
    Map::ConstIterator begin() const;
    Map::ConstIterator end() const;
    Map::Iiterator begin();
    Map::Iterator end();

    /*
        Map operators
    */
    const DataType& operator[](const KeyType key) const;
    DataType& operator[](const KeyType key);
};

/*
    Map::Pair class
*/
template <class K, class V>
class Map<K,V>::Pair {

};

/*
    Map::Iterator class
*/
template <class K, class V>
class Map<K,V>::Iterator {
    //to do
};

/*
    Map::ConstIterator class
*/
template <class K, class V>
class Map<K,V>::ConstIterator : public Map<K,V>::Iterator {
    //to do
};

/*
    Map c'tors, methods and operators implementation
*/

//to do

#endif /*  MAP_H_  */

Here are some small things you could di in order to improve your design:

First of all, you have a typo: you wrote Map::Iiterator begin(); instead of Map::Iterator begin();.
You use KeyType and DataType but do not even declare them.
For client code that uses generic code, it would be great if the name of the functions and subtypes were consistent with the STL. That means that you should be using empty(), iterator, const_iterator, etc...
The STL also defines subtypes like value_type, reference_type, size_type, etc... It would be better if you provided those too :)
Since you are using C++11, you could also provide the member functions cbegin and cend, for the same reason (consistency with standard containers).
You could have used std::size_t for the size() function (or even better, Map<K, V>::size_type), but using such an unsigned type can also lead to some unexpected problems. I wasn't able to find any relevant article, otherwise I would have linked one.
operator[] should take its elements by const&. You probably don't want to copy entire std::string instances when using this function.
Last but not least, I have no idea what your function filter is supposed to do. My guess is that it returns a filtered version of the Map, in which case the name filtered may be more suitable. Otherwise, if it filters the current map in place, it should probably return a Map& instead of a Map. Anyway, you better document it to remove the potential ambiguities. Moreover, we don't know whether the filter function filters the Map on its keys or on its values.

Well, otherwise, I don't think there are obvious errors in the design. There are probably some other things that can be improved, but generally speaking it's not bad :)


Rust: calculating mean, median, and mode for numbers from stdin This quiz is on The Rust Programming Language online ebook.

  Given a list of integers, use a vector and return the mean (the average value), median (when sorted, the value in the middle position), and mode (the value that occurs most often; a hash map will be helpful here) of the list.

As a novice Rust programmer, I'd like get my code reviewed and learn more about programming Rust.

There are a couple of things I'd like to know:

getting input using io::stdin().read_line() is ok for this case,
if there's better looping (user-input) and quitting pattern,
handling user input errors with helpful error message (Your input is invalid. Please enter whitespace-separated integers.) then re-ask with prompt, instead of panicking,
whether type casting using as is commonly-used (ex: i32 -> f32),
implementation of get_median() and get_mode() can be simpler than now

Here's my code:

use std::collections::HashMap;
use std::io::{self, prelude::*};

fn main() {
    let stdin = io::stdin();

    'mainloop: loop {
        print!("Enter space-separated numbers (q for quit)> ");
        io::stdout().flush().expect("flush failed");

        let mut line = String::new();
        stdin.read_line(&mut line).expect("Failed to read line");

        if line == "q\n" {
            break 'mainloop;
        }

        // TODO: handling ParseIntError
        let nums: Vec<i32> = line
            .split_whitespace()
            .map(|s| s.parse::<i32>().unwrap())
            .collect();

        let mean = nums.iter().sum::<i32>() as f32 / nums.len() as f32;

        println!(
            "numbers: {:?}, mean: {}, median: {}, mode: {}",
            nums,
            mean,
            get_median(&nums),
            get_mode(&nums)
        );
    }
}

fn get_median(v: &Vec<i32>) -> f32 {
    if v.len() < 1 {
        return 0.0;
    }

    let mut vec = v.clone();
    vec.sort();
    if vec.len() % 2 == 1 {
        return *vec.get(vec.len() / 2).unwrap() as f32;
    }
    return (*vec.get(vec.len() / 2 - 1).unwrap() + *vec.get(vec.len() / 2).unwrap()) as f32 / 2.0;
}

fn get_mode(v: &Vec<i32>) -> i32 {
    let mut map = HashMap::new();
    for num in v {
        let count = map.entry(num).or_insert(0);
        *count += 1;
    }
    return **map.iter().max_by_key(|(_, v)| *v).unwrap().0;
}

This code is on GitHub also.
I found there are similar questions related to the same quiz on Code Review, but the implementations differ. So I think they're not duplicated question.

Good job! I'm sure there are problems with my take, but, for what it's worth, here's how I might suggest improving things a bit.

use std::collections::HashMap;
use std::io::{self, Write}; // Personal preference, but I prefer avoiding glob imports
use std::num::ParseIntError;

fn main() {
    let stdin = io::stdin();
    let mut stdout = io::stdout();

    // Allocate a String buffer once and keep reusing it, instead of allocating multiple times.
    let mut line = String::new();

    // No need to name the loop since it's the only one. Loop naming
    // isn't very idiomatic in rust; it's typically used only when there
    // are loops within loops and naming is needed to solve ambiguity.
    loop {
        print!("Enter space-separated numbers (q for quit)> ");
        // Unwrap here seems OK, since if flush() fails, something went terribly wrong.
        stdout.flush().unwrap();

        // Clear the String buffer to prepare for reuse.
        line.clear();
        // Unwrap here seems OK, for similar reasoning as above.
        stdin.read_line(&mut line).unwrap();

        if line == "q\n" {
            break;
        }

        // Let the closure passed to map return a Result, then collect into a
        // Result<Vec<_>, ParseIntError>, which will be Ok if all parsing succeeded
        // or Err if any parsing failed. After that, match on your Result to handle errors.
        let mut nums = match line
            .split_whitespace()
            .map(|s| s.parse::<i32>())
            .collect::<Result<Vec<i32>, ParseIntError>>()
        {
            Ok(vec) => {
                if vec.is_empty() {
                    // Error handling: If user didn't give you any input, try again.
                    continue;
                }
                vec
            }
            Err(_) => {
                // Error handling: If user gave you bad input, try again.
                println!("Invalid input. Only integer values are accepted. Please try again.");
                continue;
            }
        };

        // Casting i32 to f32 is fine.
        let mean = nums.iter().sum::<i32>() as f32 / nums.len() as f32;
        let median = get_median(&mut nums);
        let mode = get_mode(&nums);

        println!(
            "numbers: {:?}, mean: {}, median: {}, mode: {:?}",
            &nums, // No need to consume nums (even though in this case you never use it again)
            mean,
            median,
            mode,
        );

        break;
    }
}

// Avoid the clone by passing a mutable reference
fn get_median(vec: &mut Vec<i32>) -> f32 {
    // is_empty() is slightly more idiomtic than vec.len() < 1
    if vec.is_empty() {
        return 0.0;
    }

    vec.sort();

    // * `vec.len() / 2` is reusable code; so make it it's own varible
    // * Instead of using `vec.get(index).unwrap()`, use `vec[index]`,
    //   as we know our index is valid.
    let index = vec.len() / 2;

    if vec.len() % 2 == 1 {
        vec[index] as f32
    } else {
        (vec[index - 1] as f32 + vec[index] as f32) / 2.0
    }
}

// * Whenever you want to pass &Vec<_> as an argument to a function,
//   consider passing &[_] instead. It works with more types.
// * Mode is not necessarily unique; so return a Vec<i32>.
fn get_mode(slice: &[i32]) -> Vec<i32> {
    if slice.is_empty() {
        // bail early if the input is empty; so that we avoid
        // unnecessarily allocating a HashMap.
        return vec![];
    }

    // Waste a little space by allocating from the start a HashMap
    // of maximum possible size; this avoids the possibility of
    // having to rellocate once the size has grown bigger than
    // capacity. It's a micro optimization, but in general in rust
    // if you know how big a heap allocated thing (like Vec, String, HashMap)
    // etc. needs to be in advance; take advantage of that information.
    let mut map = HashMap::with_capacity(slice.len());
    for num in slice {
        let count = map.entry(num).or_insert(0);
        *count += 1;
    }

    // Unwrap is OK because we know the map is non-empty.
    let max_value = map.values().map(|v| *v).max().unwrap();

    // Use into_iter() as we don't need the map anymore and
    // that will more efficiently create the vec than
    // if we had used iter()
    let mut vec = map
        .into_iter()
        .filter_map(|(k, v)| if v == max_value { Some(*k) } else { None })
        .collect::<Vec<i32>>();

    // Sort because it makes the output deterministic
    vec.sort();

    vec
}
```


Publishing a description about a selected band This is a basic program I wrote that lets you select a band, and give a description about the band and publish what you wrote.

Are there ways I can apply concepts of OOP to improve this code?  Any help and tips would be greatly appreciated!

(I tried to put this on JSFiddle, but it was rendering differently.)

        <title>Foo</title>

        <form name="form1">
            <input type="radio" name="band" value="Led Zeppelin" />Led Zeppelin

            <input type="radio" name="band" value="Red Hot Chili Peppers" />Red Hot Chili Peppers

            <input checked="checked" type="radio" name="band" value="The Beatles" />The Beatles

            <input type ="text" name="description" value="Enter something"/>

        </form>
        <button onclick="addEntry()">Add row</button>

        <button onclick="removeEntry()">Remove most recent entry</button>

I have several comments on both your HTML and your JS.

We'll start with the HTML:

You can keep it much cleaner by separating Javascript from it completely. For example, instead of doing this:

<button onclick="addEntry()">Add row</button>

you would do this:

<button id="add-entry">Add row</button>

and in your script:

$('#add-entry').on('click', addEntry);  // binds addEntry() to the
                                        // click handler for that element

You don't need a form element as you aren't submitting anything. See my revised version below for how to access the checked radio option with jQuery.
I would use div elements instead of br to create new lines, because it will be much easier to go in later and change the style (for example, if you wanted to add padding, or increase the spacing between the radio options).
You can use an ol element to get a numbered list instead of manually inserting a number next to each new entry.

JS:

You included jQuery but you're not using it anywhere in your code (it makes it very easy to manipulate the DOM).
You can put these statements inside a $(document).ready() block, which means they will get executed when the document is guaranteed to be ready for manipulation.
In addEntry() you have a couple variables that you didn't use at all.

To answer your question, I wouldn't use an OO paradigm for this at all. You aren't doing anything that OOP would improve or make easier. Here is my revision of your code with the changes I mentioned above (demo on jsfiddle):

        <title>Foo</title>

<input type="radio" name="band" value="Led Zeppelin">Led Zeppelin</input>

<input type="radio" name="band" value="Red Hot Chili Peppers">Red Hot Chili Peppers</input>

<input checked="checked" type="radio" name="band" value="The Beatles">The Beatles</input>

<input id="description" type="text" value="Enter something"/>

        <button id="add-entry">Add row</button> <button id="remove-recent-entry">Remove most recent entry</button>


Java merge sort implementation Is this a good implementation?

static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }

    int[] left, right;

    left = Arrays.copyOfRange(arr, 0, arr.length / 2);
    right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

    left = mergeSort(left);
    right = mergeSort(right);

    return merge(left, right, arr);

}

private static int[] merge(int[] left, int[] right, int result[]) {

    int i = 0, j = 0, z = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[z++] = left[i++];

        } else {
            result[z++] = right[j++];

        }
    }

    while (i < left.length) {
        result[z++] = left[i++];

    }
    while (j < right.length) {
        result[z++] = right[j++];

    }
    printArr(result);
    return result;

}

static int[] mergeSort(int[] arr) {

If you want to call it array, please go ahead and write out the name.

Personally, I'd prefer data or numbers as names, but that may just be me.

    int[] left, right;

    left = Arrays.copyOfRange(arr, 0, arr.length / 2);
    right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

While this will work, consider

    int[] left = Arrays.copyOfRange(arr, 0, arr.length / 2);
    int[] right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

It's actually slightly shorter in this case, as int[] is shorter than left, right;.  But even if it were longer, it is easier to follow with the declaration and initialization on the same line.

    int midpoint = arr.length / 2;

This could make it clearer why you are passing around arr.length / 2 if you replace occurrences with midpoint.

    int i = 0, j = 0, z = 0;

I would find this easier to read as either

    int i = 0,
        j = 0,
        z = 0;

or

    int i = 0;
    int j = 0;
    int z = 0;

One initialization per line.

    printArr(result);

This looks like debugging code to me.  If so, it should have been removed before review.

I don't have any real comments on the algorithm itself beyond what people said in the comments.  You might be able to bring down the memory usage if you tried hard enough, but it shouldn't generally matter.  This is a more elegant version and less susceptible to bugs if you aren't memory bound.

You may be doing this just as an exercise (you can use the reinventing-the-wheel tag to indicate this) or for some other reason.  In practice, the standard Arrays.sort implementation is good enough for most needs.  You wouldn't normally need to roll your own.


C dynamic array and pointers I've written an implementation of a dynamic array in C, but I'm not sure if my implementation is correct... This is what I'm worried about: if I add an element, will it remain in the collection? This problem has arisen from my (apparently) limited knowledge on void pointers. I haven't found any answers to my question online...

The List struct is defined like this:

typedef struct list
{
    /**
     * C-style array containing the data in this list.
     */
    void** data;
    /**
     * Amount of elements currently present in this list.
     */
    unsigned int size;
    /**
     * Amount of elements that could be present in this list (i.e. size + number of empty spots).
     */
    unsigned int capacity;
} List;

So far so good?

Now, when I want to add an element to a list l, I call List_Add(&l, &element)...

void List_Add(List* list, void* element)
{
    if (list->data == NULL)
    {
        return;
    }

    if (list->size == list->capacity)
    {
        // Double the data array of list.
        list->data = realloc(list->data, 2 * list->capacity * sizeof(void*));
        list->capacity *= 2;
    }

    if (list->data != NULL)
    {
        list->data[list->size] = element;
        ++(list->size);
    }
}

By the way: yes, list->data is malloced before calling this function.

I've done some testing with adding elements, but I'm not sure if it's entirely correct. If I were to call this function with an element created on the stack (example below), would it continue to work for the entirety of the program's lifetime?

Example

List l;
List_Init(&l);
int i = 1;
List_Add(&l, &i);

If I were to call this function with an element created on the stack (example below), would it continue to work for the entirety of the program's lifetime?

No, it wouldn't:

i is created on the stack
pointer to i is saved in the list
i disappears and stack is reused when caller goes out of scope (now list is pointing to garbage)

Your List can be used to store:

Objects created on the heap (using malloc)
Global/static objects
Local stack objects, but only if they are removed again before they go out of scope.

For example:

List l;
List_Init(&l);
int i = 1;
int* ptr_i = (int*)malloc(sizof(int));
*ptr_i = i;
List_Add(&l, ptr_i);
// *ptr_i will remain until someone calls free(ptr_i)


Generating all size-k consecutive subsets in Haskell I am interested in splitting any list into consecutive subsets based on a k-value.  For example, [1,2,3,4,5] splits into [[1,2],[2,3],[3,4],[4,5]] when k=2.  If k is bigger than the entire list, then an empty list will be returned.

I am unhappy with my current solution and would like to have suggestions on how to improve it.  Specifically I would like to be able to code a more terse solution.  I find that terseness in functional programming languages, such as Haskell, is important to keep in mind.  I feel that there is a way of expressing my Haskell solution using a fold possibly, but I just cannot see how at this moment.

consSizeK :: Int -> [a] -> [[a]]
consSizeK _ [] = []
consSizeK k list@(_:tail)
    | k > length list = []
    | otherwise = (take k list) : consSizeK k tail

Each evaluation of length list will take time proportional to the length of the list, which will slow this down.

We know that there will be length xs - n + 1 sublists of xs of length n. We can use this to make the code much faster.

sublists n xs = take (length xs - n + 1) $ sublists' n xs
    where sublists' _ [] = [[]]
          sublists' n xs@(_:rest) = take n xs : sublists' n rest

For comparison, with

main = print $ sum $ map length $ sublists 2 [1 .. 100000]

I get the following timings on my machine, compiled with -O.

Original version:

$ time ./orig
199998

real    0m14.890s
user    0m0.015s
sys     0m0.015s

This version:

$ time ./new
199998

real    0m0.065s
user    0m0.015s
sys     0m0.015s


String similarity calculation For string similarity, it is defined as longest common prefix length. For example, "abc" and "abd" is 2, and "aaa" and "aaab" is 3.

The problem is calculate the similarity of string S and all its suffixes, including itself as the first suffix.

For example, for S="ababaa", suffixes are "ababaa", "babaa", "abaa","baa","aa"
and "a", the similarity are 6+0+3+0+1+1=11.

My code works and I am looking for smarter ideas to be more efficient.

# Complete the function below.
from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children=defaultdict(TrieNode)
        self.isEnd=False
class TrieTree:
    def __init__(self):
        self.root=TrieNode()
    def insert(self, word):
        node = self.root
        for w in word:
            node = node.children[w]
        node.isEnd = True
    def search(self, word):
        node = self.root
        count = 0
        for w in word:
            node = node.children.get(w)
            if not node:
                break
            else:
                count += 1
        return count

def  StringSimilarity(inputs):
    resultFormat=[]
    for word in inputs:
        # build Trie tree
        index = TrieTree()
        index.insert(word)
        result = 0
        # search for suffix
        for i in range(len(word)):
            result += index.search(word[i:])
        print result
        resultFormat.append(result)

    return resultFormat

One thing I'd suggest is to allow a word to be inserted inside __init__, rather than force the user to always call .insert(word). You can still allow for creating an empty TrieTree. Just make word an optional parameter, and ignore it if it's empty:

def __init__(self, word=''):
    self.root = TrieNode()
    if word:
        self.insert(word)

now you could create your tree in one line:

index = TrieTree(word)


Find median of two sorted arrays Problem statement

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be \$\mathcal{O}(\log (m+n))\$.

Implementation

 def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if j > 0 and i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and j < n and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect
            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

Concern

I suspect that it is safe to change this line of code

j > 0 and i < m and B[j-1] > A[i]

to

i < m and B[j-1] > A[i]

and also it is safe to change this line of code

i > 0 and j < n and A[i-1] > B[j]

to

i > 0 and A[i-1] > B[j]

I think remove the condition check of j is safe since we already making sure size of A is no bigger than size of B.

Sorry for being late, but had no time to study your code until today.
The results are the same which AmirHossein presented before.

After you conditionally swap the input arrays:

    if m > n:
        A, B, m, n = B, A, n, m

you have m <= n, so

    half_len = (m + n + 1) // 2

(after the fix by AmirHossein) is not less than m. That makes

    j = half_len - i

greater than zero if i < m, so j > 0 and i < m is redundant.

Of course half_len is also is not greater than n, so similary j < n if i > 0.

As for the complexity, the code bisects the A array in each iteration, so the complexity is actually \$\mathcal{O}(\log m)\$ where m is the length of A after the conditional swap, or \$\mathcal{O}(\log (\min(m,n)))\$ in terms of input values of m,n. And this can be bounded by \$\mathcal{O}(\log (m+n))\$.


Read files from a directory using Promises V2 Follow up to Read files from a directory using Promises

Removed exists() and replaced with stat() so I can check if the file is readable before proceeding.

console.log("Hi");
const fs = require('fs');
const { promisify } = require('util');

function mystat(file) {
    return new Promise(function(resolve, reject) {
        console.log(file);
        fs.stat(file, function(err, stat) {
            if (err) {
                reject(err);
            }
            else {
                console.log("Returning Obj");
                resolve({stat: stat, file: file});
            }
        });
    });
}

readdir     = promisify(fs.readdir);
readFile    = promisify(fs.readFile);
writeFile   = promisify(fs.writeFile);

readdir(".")
.then(files => mystat(files[0]))
.then(data  => {if (!(data.stat.mode | fs.S_IRWXO)) { throw "Not Readable";} return readFile(data.file)})
.then(content => writeFile('Test', content))
.then(() => console.log("It worked"))
.catch(err => console.log("Error: " + err));

To pass parameters through, eg the file passed through stat to the read function; I needed to define my own function so that I could pass the object on). Is there a better way of doing this?

First of all, async code is not a requirement for all Node.js code. It depends on the use case. Async code makes sense if you want to service multiple things concurrently (i.e. HTTP servers, test runners, etc.) but doesn't make sense for single-run script-y things (i.e. cli tool, scaffold generator, etc.).

The case above falls in the second category, a simple, single-run, non-concurrent, non-intensive operation. This means you can get away with the synchronous versions of the same operations, which will not require promises.

const { readdirSync, statSync, readFileSync, writeFileSync } = require('fs');

readdirSync('.')
  .slice(0, 1)
  .map(file => ({ stat: statSync(f), file }))
  // If you know it's not readable, just don't proceed.
  .filter(data => (data.stat.mode | fs.S_IRWXO))
  .map(data => readFileSync(data.file))
  .forEach(content => writeFileSync('test', content))

// If it made it all the way here, it worked. If something threw up,
// it should have halted the script somewhere in the middle.
console.log("It worked")

Now if you really want async code, Node supports async/await. It's essentially syntactic sugar to promises, where async functions return promises, values returned by async functions become the resolved value, errors throw become rejection values, and await makes code appear to wait for the promise to settle before proceeding. This means you can write the code much closer to the one above.

The one nice thing about async/await over regular promises is better scoping. You don't have to pass forward stuff from the previous then to the next then.

const { promisify } = require('util')
const fs = require('fs')
const readdir = promisify(fs.readdir)
const readFile = promisify(fs.readFile)
const writeFile = promisify(fs.writeFile)
const stat = promisify(fs.stat)

async function op(){
  const files = await readdir('.')
  const file = files[0]
  const data = await stat(file)

  if (!(data.stat.mode | fs.S_IRWXO)) throw "Not Readable"

  const content = await readFile(file)

  await writeFile('Test', content)
}

// Needed, since Node will warn you about unhandled rejections.
// Otherwise, the code above could have been an async iife.
op().then(() => {
  console.log("It worked")
}, (e) => {
  console.log("Error: " + e)
})


My solution to a competitive programming problem (UVA 10189, Minesweeper) This is one of my first competitive programming solutions. The problem it solves is described here; basically, you get a series of grids ("fields"), where . means "no mine" and * means "mine"; you have to compute how many mines are adjacent (8 adjacent squares) to each non-mine square. My solution is correct, but seems pretty complicated for such a simple problem. What could I have done better, taking into account that my only concern is to write the program as quickly and correctly as possible (readability/proper practices don't count here)? You may also separately critique readability/proper practices.

import sys
from itertools import *

data = sys.stdin.read().splitlines()

fields = []
import re
for i in range(0,len(data)):
    match = re.match('(\d+) (\d+)', data[i])
    if match:
        r = int(match.group(1))
        if r != 0:
            fields.append(data[i+1 : i+1+r])

for field in fields:
    for (x,y) in product(range(len(field)), range(len(field[0]))):

        if field[x][y] == '*':
            continue

        count = 0
        for (x_offset, y_offset) in product(range(-1,2), repeat=2):

            if x_offset == y_offset == 0 or x+x_offset < 0 or y_offset+y < 0:
                continue

            try:
                if field[x+x_offset][y+y_offset] == '*':
                    count += 1
            except IndexError:
                pass

        row = list(field[x])
        row[y] = str(count)
        field[x] = ''.join(row)

for i in range(0,len(fields)):
    print("Field #%i:" % (i+1))
    for row in fields[i]:
        print(row)

    if i < len(fields)-1:
        print()

Even in the case of timed contests, you should not sacrifice good practices for brievity. What you gain typing less is lost when debugging or re-reading code.

Using functions to separate logical units of code is the least you should do here as it help isolate, test and assert correctness of each step of the algorithm more easily.

You should take the habbit of starting to write/configure a template in your IDE:

# imports

def main():
    pass

if __name__ == '__main__':
    main()

Here you start by reading the entire input and then extract out tests cases afterwards. I see two issues with that:

you may run into memory issues if the number of tests cases and/or their length is huge;
you do not take advantage of the highly structured input spec.

I would define the following function:

def read_test_case(lines_amount):
    return [input() for _ in range(lines_amount)]

And call it like:

def main():
    while True:
        lines, columns = map(int, input().split())
        if not lines:
            return
        field = read_test_case(lines)
        # ...

You also perform a lot of for ... in range(len(...)) which is rather inefficient. Consider using direct iteration like you do with for field in fields or enumerate if you also need indices:

MINE = '*'

def build_hints(field, lines_max, columns_max):
    def count_mines(x, y):
        count = 0
        for x_offset, y_offset in itertools.product(range(-1,2), repeat=2):
            x_ = x + x_offset
            y_ = y + y_offset
            if x_offset == y_offset == 0 or not (0 <= x_ < columns_max and 0 <= y_ < lines_max):
                continue
            count += field[y_][x_] == MINE
        return count

    return [
        [
            MINE if square == MINE else str(count_mines(x, y))
            for x, square in enumerate(row)
        ]
        for y, row in enumerate(field)
    ]

All what is left is to put all pieces together and print elements. Which lead to:

import itertools

MINE = '*'

def build_hints(field, lines_max, columns_max):
    def count_mines(x, y):
        count = 0
        for x_offset, y_offset in itertools.product(range(-1,2), repeat=2):
            x_ = x + x_offset
            y_ = y + y_offset
            if x_offset == y_offset == 0 or not (0 <= x_ < columns_max and 0 <= y_ < lines_max):
                continue
            count += field[y_][x_] == MINE
        return count

    return [
        [
            MINE if square == MINE else str(count_mines(x, y))
            for x, square in enumerate(row)
        ]
        for y, row in enumerate(field)
    ]

def print_hints(hints):
    for row in hints:
        print(''.join(row))
    print()

def read_test_case(lines_amount):
    return [input() for _ in range(lines_amount)]

def main():
    for test_case in itertools.count(1):
        lines, columns = map(int, input().split())
        if not lines:
            return
        field = read_test_case(lines)
        hints = build_hints(field, lines, columns)
        print('Field #{}:'.format(test_case))
        print_hints(hints)

if __name__ == '__main__':
    main()


Direct to another folder with .htaccess file Lets say my folder structure looks like this

someproject/v5/.htaccess
someproject/5.0.1/lib.js
someproject/5.0.1/assets/img/png/anotherfolder/helloworld.png
someproject/5.0.2/lib.js
someproject/5.0.2/assets/img/png/anotherfolder/helloworld.png

When user enters url's like (and lets say I am the owner of google.com):

www.google.com/someproject/v5/lib.js
www.google.com/someproject/v5/assets/img/png/anotherfolder/helloworld.png

I want him to be redirected to version i want using the .htaccess file, example if i want to serve version 5.0.1, then the user will be redirected to this:

www.google.com/someproject/5.0.1/lib.js
www.google.com/someproject/5.0.1/assets/img/png/anotherfolder/helloworld.png

Only one thing may change the version number, this does not work (.htaccess file content):

AddType application/javascript .js
AddType text/css .css

AddOutputFilterByType DEFLATE text/css
AddOutputFilterByType DEFLATE application/javascript

Options +FollowSymLinks
RewriteEngine On
RewriteRule ^(.*)/(.*) "https://google.com/release/theme/5.0.1/$1/$2" [R=302,L]

How can I make it only change v5 with my version number (syntax) ?

The line you are using is telling the engine, redirect everything to the following URI. The reason for this is that you are using the pattern matching wildcard (.*).

The parenthesis is used for creating groups, the dot is telling the engine that every character is accepted and the star symbol is telling the engine that it can be of unlimited length. By using the forward slash followed by another wildcard group, you are redirecting every URI request to the following URI "https://google.com/release/theme/5.0.1/$1/$2".

Instead of using

RewriteRule ^(.*)/(.*) "https://google.com/release/theme/5.0.1/$1/$2" [R=302,L]

You should replace it with the following line

RewriteRule ^v5/(.*)$ https://google.com/release/theme/5.0.1/$1 [R=302,L]

Why append the 'v5' before the caret symbol (^)?
The caret symbol matches the start of a string. In our case, the string is the version.

Source : https://www.searchenginepeople.com/blog/htaccess-redirect-rewrite-rules.html


Password validation in Java I just wrote this password validation code function that checks to see if a password will be accepted in AD or not. I'm not sure this is the best way to do it, but for now it works fine. I would love some suggestions on how to make it better.

public String validateNewPass(String pass1, String pass2){
        StringBuilder retVal = new StringBuilder();

        if(pass1.length() < 1 || pass2.length() < 1 )retVal.append("Empty fields
");

        if (pass1 != null && pass2 != null) {

            if (pass1.equals(pass2)) {
                logger.info(pass1 + " = " + pass2);

                pass1 = pass2;
                boolean hasUppercase = !pass1.equals(pass1.toLowerCase());
                boolean hasLowercase = !pass1.equals(pass1.toUpperCase());
                boolean hasNumber = pass1.matches(".*\\d.*");
                boolean noSpecialChar = pass1.matches("[a-zA-Z0-9 ]*");

                if (pass1.length() < 11) {
                    logger.info(pass1 + " is length < 11");
                    retVal.append("Password is too short. Needs to have 11 characters
");
                }

                if (!hasUppercase) {
                    logger.info(pass1 + " <-- needs uppercase");
                    retVal.append("Password needs an upper case
");
                }

                if (!hasLowercase) {
                    logger.info(pass1 + " <-- needs lowercase");
                    retVal.append("Password needs a lowercase
");
                }

                if (!hasNumber) {
                    logger.info(pass1 + "<-- needs a number");
                    retVal.append("Password needs a number
");
                }

                if(noSpecialChar){
                    logger.info(pass1 + "<-- needs a specail character");
                    retVal.append("Password needs a special character i.e. !,@,#, etc.
");
                }
            }else{
                logger.info(pass1 + " != " + pass2);
                retVal.append("Passwords don't match
");
            }
        }else{
            logger.info("Passwords = null");
            retVal.append("Passwords Null
");
        }
        if(retVal.length() == 0){
            logger.info("Password validates");
            retVal.append("Success");
        }

        return retVal.toString();

    }

**Note: These lines are to ensure a different case to handle a null vs empty string

if(pass1.length() < 1 || pass2.length() < 1 )retVal.append("Empty fields
");

        if (pass1 != null && pass2 != null) {

Buggy behavior

First you're checking the length of the passwords, and then if they are null:

if(pass1.length() < 1 || pass2.length() < 1 )retVal.append("Empty fields
");

if (pass1 != null && pass2 != null) {

This is not going to work well: if any of the passwords were null, you would get a NullPointerException when you check length.

Also, a better way to check if a string is empty is using pass1.isEmpty().

Also, this is pointless and potentially confusing:

pass1 = pass2;

Simplify the validation logic

It would be better and more efficient to create private final Pattern members that are compiled regular expressions, and reusable multiple times:

private final Pattern hasUppercase = Pattern.compile("[A-Z]");
private final Pattern hasLowercase = Pattern.compile("[a-z]");
private final Pattern hasNumber = Pattern.compile("\\d");
private final Pattern hasSpecialChar = Pattern.compile("[^a-zA-Z0-9 ]");

For example, this returns true if pass1 contains an uppercase character:

hasUppercase.matcher(pass1).find()

Notice the patter for hasSpecialChar: match non-alphabetic, non-digit, non-space.

Suggested implementation

Based on the above tips, you can simplify your implementation like this:

private final Pattern hasUppercase = Pattern.compile("[A-Z]");
private final Pattern hasLowercase = Pattern.compile("[a-z]");
private final Pattern hasNumber = Pattern.compile("\\d");
private final Pattern hasSpecialChar = Pattern.compile("[^a-zA-Z0-9 ]");

public String validateNewPass(String pass1, String pass2) {
    if (pass1 == null || pass2 == null) {
        logger.info("Passwords = null");
        return "One or both passwords are null";
    }

    StringBuilder retVal = new StringBuilder();

    if (pass1.isEmpty() || pass2.isEmpty()) {
        retVal.append("Empty fields
");
    }

    if (pass1.equals(pass2)) {
        logger.info(pass1 + " = " + pass2);

        if (pass1.length() < 11) {
            logger.info(pass1 + " is length < 11");
            retVal.append("Password is too short. Needs to have 11 characters
");
        }

        if (!hasUppercase.matcher(pass1).find()) {
            logger.info(pass1 + " <-- needs uppercase");
            retVal.append("Password needs an upper case
");
        }

        if (!hasLowercase.matcher(pass1).find()) {
            logger.info(pass1 + " <-- needs lowercase");
            retVal.append("Password needs a lowercase
");
        }

        if (!hasNumber.matcher(pass1).find()) {
            logger.info(pass1 + "<-- needs a number");
            retVal.append("Password needs a number
");
        }

        if (!hasSpecialChar.matcher(pass1).find()) {
            logger.info(pass1 + "<-- needs a specail character");
            retVal.append("Password needs a special character i.e. !,@,#, etc.
");
        }
    } else {
        logger.info(pass1 + " != " + pass2);
        retVal.append("Passwords don't match
");
    }
    if (retVal.length() == 0) {
        logger.info("Password validates");
        retVal.append("Success");
    }

    return retVal.toString();
}

Support for unicode

If you want to allow unicode characters in the password, define the patterns using the special java character classes, as documented in the javadoc:

private final Pattern hasUppercase = Pattern.compile("\\p{javaUpperCase}");
private final Pattern hasLowercase = Pattern.compile("\\p{javaLowerCase}");
private final Pattern hasNumber = Pattern.compile("\\p{javaDigit}");
private final Pattern hasSpecialChar = Pattern.compile("[^\\p{javaLetterOrDigit} ]");