External / File-based mergesort I've implemented an external mergesort to sort a file consisting of Java int primitives, however it is horribly slow (fortunately it does at least work).

Very little happens in the sort method: it just recursively calls merge with blockSize doubling each call and swapping input and output files each time.

How could I be losing so much time here?

//Merge stage of external mergesort
//Read from input file, already sorted into blocks of size blockSize
//Write to output file, sorted into blocks of 2*blockSize
public static void merge(String inputFile, String outputFile, long blockSize)
    throws IOException
{
  //readers for block1/2
  FileInputStream fis1 = new FileInputStream(inputFile);
  DataInputStream dis1 = new DataInputStream(fis1);
  FileInputStream fis2 = new FileInputStream(inputFile);
  DataInputStream dis2 = new DataInputStream(fis2);

  //writer to output file
  FileOutputStream fos = new FileOutputStream(outputFile);
  DataOutputStream dos = new DataOutputStream(fos);

  // merging 2 sub lists
  // go along pairs of blocks in inputFile
  // continue until end of input

  //initialise block2 at right position
  dis2.skipBytes((int) blockSize);

  //while we haven't reached the end of the file
  while (dis1.available() > 0)
    {
      // if block1 is last block, copy block1 to output
      if (dis2.available() <= 0)
        {
          while (dis1.available() > 0)
            dos.writeInt(dis1.readInt());
          break;
        }
      // if block1 not last block, merge block1 and block2
      else
        {
          long block1Pos = 0;
          long block2Pos = 0;
          boolean block1Over = false;
          boolean block2Over = false;

          //data read from each block
          int e1 = dis1.readInt();
          int e2 = dis2.readInt();

          //keep going until fully examined both blocks
          while (!block1Over | !block2Over)
            {
              //copy from block 1 if:
              //  block1 hasnt been fully examined AND
              //  block1 element less than block2s OR block2 has been fully examined
              while ( !block1Over & ((e1 <= e2) | block2Over) )
                {
                  dos.writeInt(e1); block1Pos += 4;
                  if (block1Pos < blockSize & dis1.available() > 0)
                    e1 = dis1.readInt();
                  else
                    block1Over = true;
                }
              //same for block2
              while ( !block2Over & ((e2 < e1) | block1Over) )
                {
                  dos.writeInt(e2); block2Pos += 4;
                  if (block2Pos < blockSize & dis2.available() > 0)
                    e2 = dis2.readInt();
                  else
                    block2Over = true;
                }
            }
        }
      // skip to next blocks
      dis1.skipBytes((int) blockSize);
      dis2.skipBytes((int) blockSize);
    }
  dis1.close();
  dis2.close();
  dos.close();
  fos.close();
}

Steve is absolutely right that adding a buffered layer between the Data input/output streams and the File input/output streams, will make things work a whole lot better. I would also suggest changing to use a try-with-resources system, which will also close, and otherwise manage the files in a better way:

try (DataInputStream dis1 = new DataInputStream(new BufferedInputStream(new FileInputStream(inputFile)));
     DataInputStream dis2 = new DataInputStream(new BufferedInputStream(new FileInputStream(inputFile)));
     DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(outputFile))); ) {

    //initialise block2 at right position
    dis2.skipBytes((int) blockSize);

    ... do other work ...

}

Now, your input/output is buffered, and it's closed cleanly, and there are no leaks. The input/output is also buffered, leading to fewer IO's, and more efficient processing.

This will likely make a huge difference in performance, but, I suspect that using NIO (ByteBuffer) operations (especially with memory-mapped IO) will be faster again. Consider using FileChannel operations that reduce the amount of memory copies that are made of the data in the file.

UPDATE:

I have taken some time to run some tests and use some strategies that I am familiar with from high-performance systems. As I suspected, a FilChannel with Memory-mapped IO is far faster.

On my computer, a file with 400,000 int values takes about 15 seconds to sort using your system. When I used Buffered IO, it took 1.5 seconds (10 times faster).

I then rewrote the system using a couple of tricks:

use small sorts for blocks of 32 integers.
then use merging for larger, and larger blocks.
use memory mapped IO to do the file accesses

The result was a sort in 0.096 seconds, or 150 times faster than your code.

Now, this code is not exactly simple, so, be warned that it is a little obscure.

The first thing I did though, was create a class to abstract away the low-level IO:

private static final class FastFile implements AutoCloseable {
    private final Path path;
    private final FileChannel channel;
    private final long size;
    private MappedByteBuffer buffer = null;
    private long mapPosition = -1;

    public FastFile(final Path folder, final long size) throws IOException {
        this.size = size;
        this.path = Files.createTempFile(folder, "tmpdata", ".dat");
        this.channel = FileChannel.open(path, StandardOpenOption.TRUNCATE_EXISTING, StandardOpenOption.WRITE, StandardOpenOption.READ);
        // Create the file with the right size.
        channel.write(ByteBuffer.allocate(1), size - 1);
        resetFile();
    }

    @Override
    public void close() throws Exception {
        channel.force(true);
        channel.close();
        buffer = null;
    }

    private final void relocate(final long filepos) throws IOException {
        if (filepos >= size) {
            throw new IllegalArgumentException("Illegal file position " + filepos + " in file of size " + size);
        }
        final long mappos = filepos >>> MAPPEDSHIFT;
        if (mappos != mapPosition) {
            final long pos = mappos << MAPPEDSHIFT;
            final long len = Math.min(size - pos, MAPPEDSIZE);
            buffer = channel.map(MapMode.READ_WRITE, pos, len);
            buffer.load();
            System.out.println("Move to position " + pos + " and length " + len);
            mapPosition = mappos;
        }
    }

    public void resetFile() throws IOException {
        relocate(0);
    }

    public int getInt(final long intPosition) throws IOException {
        final long filepos = intPosition << 2;
        final int offset = (int)(filepos & MAPPEDMASK);
        relocate(filepos);
        return buffer.getInt(offset);
    }

    public void putInt(final long intPosition, final int intValue) throws IOException {
        final long filepos = intPosition << 2;
        final int offset = (int)(filepos & MAPPEDMASK);
        relocate(filepos);
        buffer.putInt(offset, intValue);
    }

    public void rename(String targetName) throws IOException {
        Files.move(path, Paths.get(targetName));
    }

    public void delete() throws IOException {
        Files.delete(path);
    }

}

The above class can take a file, and read/write ints at any particular place. It first creates the file, and sets it to be the right size.

It is read/write and random-access. It can write an int at any position. The expensive part of the operation is relocating the buffer, but, that will happen seldom.

Using that file class, I have the following sort code:

private static void mergeSortSmart(String sourceName, String targetName) throws IOException {
    long start = System.currentTimeMillis();
    Path source = Paths.get(sourceName);
    final long size = Files.size(source);
    final long intvals = size >>> 2; // number of actual integer values (4 bytes per int).

    Path target = Paths.get(targetName).toAbsolutePath();
    if (Files.exists(target)) {
        Files.delete(target);
    }
    Path tdir = target.getParent();
    FastFile filea = new FastFile(tdir, size);
    FastFile fileb = new FastFile(tdir, size);

    int blockSize = 32;

    // copy the source data to a fast file, but do 32-size block int sorts
    // before merge-sorting.
    copyAndMicroSort(source, size, filea, blockSize);

    // then do iterative merge sorts.
    for (long bs = blockSize; bs < size; bs *= 2) {
        mergeFast(filea, fileb, intvals, bs);
        FastFile tmp = filea;
        filea = fileb;
        fileb = tmp;
    }
    // rename the sorted file.
    filea.rename(targetName);
    // delete the temp file.
    fileb.delete();
    System.out.printf("Sorted in %.3fs%n", (System.currentTimeMillis() - start)/ 1000.0);
}

The copyAndMicroSort is simple:

private static void copyAndMicroSort(Path source, long size, FastFile filea, final int batchSize) throws IOException {
    try (DataInputStream di = new DataInputStream(new BufferedInputStream(new FileInputStream(source.toFile())))) {
        long pos = 0;
        int cnt = 0;
        long vcount = 0;
        int[] data = new int[batchSize];
        while (pos < size) {
            if (cnt == data.length) {
                appendSortedInts(data, cnt, filea, vcount);
                vcount += cnt;
                cnt = 0;
            }
            data[cnt++] = di.readInt();
            pos += 4; // size of int;
        }
        appendSortedInts(data, cnt, filea, vcount);
    }

}

private static void appendSortedInts(final int[] data, final int cnt, final FastFile filea,
        final long vcount) throws IOException {
    Arrays.sort(data, 0, cnt);
    for (int i = 0; i < cnt; i++) {
        filea.putInt(vcount + i, data[i]);
    }
}

And the individual merge sorts are:

private static void mergeFast(final FastFile infile, final FastFile outfile, final long intCount, final long bs) throws IOException {
    long apos = 0;
    long bpos = bs;
    long outpos = 0;

    while (apos < intCount) {
        long alimit = Math.min(bpos, intCount);
        long blimit = Math.min(alimit + bs, intCount);
        while (apos < alimit && bpos < blimit) {
            int aval = infile.getInt(apos);
            int bval = infile.getInt(bpos);
            if (aval <= bval) {
                outfile.putInt(outpos++, aval);
                apos++;
            } else {
                outfile.putInt(outpos++, bval);
                bpos++;
            }
        }
        while (apos < alimit) {
            outfile.putInt(outpos++, infile.getInt(apos++));
        }
        while (bpos < blimit) {
            outfile.putInt(outpos++, infile.getInt(bpos++));
        }
        apos += bs;
        bpos += bs;
    }

}


Command manipulation functions for a toy shell program I am writing a small program that is supposed to act as a shell of some sorts. It operates off of a few basic structures, one of them being a command, a command_list, and a command_history.

typedef struct command command;

typedef struct
{
    char** list;
    int len;
} command_history;

typedef struct
{
    command** list;
    int len;
    command_history* history;
} command_list;

typedef struct command
{
    char* alias;
    void (*function)(command_list*);
} command;

I have written functions to add new commands, add new history, find aliases in a list and return its index, among other things, but I have a feeling that the command for adding commands, addcommand is leaking memory. I am not very experienced with C and this is just an experiment to acquaint me with pointers. I would appreciate some feedback on the code I have written and how I can improve it.

Command manipulation functions:

void addcommand(char* str, void* fun, command_list* srclist)
{
    printdebug("Adding command \"%s\" pointing to function at %p in command list located at %p... ", str, fun, srclist);
    srclist -> list = realloc(srclist -> list, sizeof(command*) * (srclist -> len + 1));
    srclist -> list[srclist -> len] = malloc(sizeof(command));
    srclist -> list[srclist -> len] -> alias = malloc(sizeof(char) * (strlen(str) + 1));
    srclist -> list[srclist -> len] -> function = malloc(sizeof(void*)); // problems here and |
    memcpy(srclist -> list[srclist -> len] -> alias, str, sizeof(char) * (strlen(str) + 1)); //       |
    srclist -> list[srclist -> len] -> function = fun; //                                    <|
    srclist -> len++;
    printdebug("Command added.\n");
}

void addhistory(char* str, command_list* srclist)
{
    printdebug("Adding \"%s\" to history list located at %p...", str, srclist -> history);
    srclist -> history -> list = realloc(srclist -> history -> list, sizeof(char*) * (srclist -> history -> len + 1));
    srclist -> history -> list[srclist -> history -> len] = malloc((strlen(str) + 1) * sizeof(char));
    memcpy(srclist -> history -> list[srclist -> history -> len], str, (strlen(str) + 1) * sizeof(char));
    srclist -> history -> len++;
    printdebug(" String added to history.\n");
}

void renamecommand(char* str, command* srccom, command_list* srclist)
{
    if(!srccom -> alias || !srccom -> function)
        return;
    printdebug("Renaming \"%s\" to \"%s\" in command list located at %p... ", srccom -> alias, str, srclist);
    free(srccom -> alias);
    srccom -> alias = malloc((strlen(str) + 1) * sizeof(char));
    memcpy(srccom -> alias, str, (strlen(str) + 1) * sizeof(char));
    printdebug("Renamed command.\n");
}

void deletecommand(command* srccom)
{
    printdebug("Deleting command \"%s\" pointing to function %p located at %p... ", srccom -> alias, srccom -> function, srccom);
    srccom -> alias = "[REMOVED]";
    srccom -> function = NULL;
    printdebug("Command deleted.\n");
}

command_list* newcommandlist()
{
    printdebug("Making new command list... ");
    command_list* new_list = malloc(sizeof(command_list));
    new_list -> list = NULL;
    new_list -> len = 0;
    new_list -> history = malloc(sizeof(command_history));
    new_list -> history -> list = NULL;
    new_list -> history -> len = 0;
    printdebug(" Made new command list located at %p.\n", new_list);
    return new_list;
}

You indeed have a memory leak in your addcommand function, at this line:

srclist -> list[srclist -> len] -> function = malloc(sizeof(void*));

The reason is that the pointer that you obtained from malloc stored into function gets overwritten later by the following line:

srclist -> list[srclist -> len] -> function = fun;

After this point, the pointer to the memory returned by malloc is lost and you cannot free it, hence the memory leak.

In fact, you don't need to malloc anything for that function, since the memory for the function pointer was already allocated by this line:

srclist -> list[srclist -> len] = malloc(sizeof(command));

The command struct already contains the memory for the field function. So you can just set function to the fun pointer.

Note also that the fun is not a void pointer, but rather a function pointer, so you should declare it as void (*fun)(command_list *) instead of void *fun.

Another comment: why do you keep a command** list instead of command* list? You are currently allocating memory twice, once for the command * pointer, and then for the actual command struct. A simpler (and less memory-hungry) solution would be to have:

typedef struct
{
    command* list; // changed command **list to command *list
    int len;
    command_history* history;
} command_list;

and adding a new command in the list would look like:

void addcommand(char* str, void (*fun)(command_list*), command_list* srclist)
{
    printdebug("Adding command \"%s\" pointing to function at %p in command list located at %p... ", str, fun, srclist);
    srclist -> list = realloc(srclist -> list, sizeof(command) * (srclist -> len + 1));
    srclist -> list[srclist -> len] -> alias = malloc(sizeof(char) * (strlen(str) + 1));
    memcpy(srclist -> list[srclist -> len] -> alias, str, sizeof(char) * (strlen(str) + 1)); //       |
    srclist -> list[srclist -> len] -> function = fun; //                                    <|
    srclist -> len++;
    printdebug("Command added.\n");
}

Additionally, you should check the return value for malloc and realloc. They may return a NULL pointer if there is insufficient memory, and the code that dereferences these pointers will cause a segmentation fault and crash the program.


Find free username based on schema Hopefully this is not too complicated. I have this code that will generate a username based on the pre-configured schema the admin types in. The fields they can use are:

<first_initial>
<last_initial>
<first_name>
<last_name>
<role>

So, if my name were John Doe, and I had the role of "author" in the system, the function would translate these UsernameSchema thusly:

<first_name>.<last_name>         = john.doe
<first_intitial><last_name>      = jdoe
<first_name>.<last_name>-<role>  = john.doe-author
<last_initial>                   = d

Obviously, it needs to check for duplicates. Below is the working code I have (will be called either after_initialize or before_create (not sure which at this point):

  def set_username
    schema = UsernameSchema.where(:active => true).first! || "<first_initial><last_name>"
    fname = self.first_name
    lname = self.last_name
    finit = fname[0]
    linit = lname[0]
    urole = self.role
    # Question 2:
    replacement_dict = {"<first_initial>" => finit, "<last_initial>" => linit, "<first_name>" => fname, "<last_name>" => lname, "<role>" => urole}
    replacement_regex= /(<first_initial>)|(<last_initial>)|(<first_name>)|(<last_name>)|(<role>)/
    proposed_username = schema.gsub(replacement_regex, replacement_dict).downcase
    self.username = find_free_name(proposed_username)
  end

  # Question 3, IDE complains about next line
  def find_free_name(un)
    user = User.find_by_username(un)
    if user
      num = user.scan(/\d+$/).first
      if num
        new_num = num.to_i + 1
        next_user = un.gsub(num, new_num.to_s)
      else
        next_user = un + "1"
      end
      find_free_name(next_user)
    else
      un
    end
  end

I guess I have these concerns with my code:

Is this a dumb way of doing it?
Where my "Question 2" comment is in the above code, that seems redundant... is there a more succinct way?
My IDE says I'm doing it wrong (and I don't know what it wants):

  All custom “finds” accessed from more than one place in the code use
  named_scope instead of a custom method.

The code here seems a bit over complicated for its intended purpose.

Would there be some issue with just appending a random number or hash to the end of each user name? something like taking all the user provided information and creating a sha-1 hash then just using the first 3 or so characters?

data = [fname,lname,fint,lint,urole]
Digest::SHA1.base64digest(data.join(''))
#=> f1ed8d7c48b27af459240984574c7bcd8b14fe4b

This would give you a very unique string to add to each username.


FIFO for embedded systems I wrote a simple FIFO based on pieces of code I found online.
It's intended for embedded systems with very restricted RAM.
It's supposed to be very simple and efficient.
The size is always power of 2 (8, 16, 32, 64, 128 etc).
fifo.h
    #ifndef FIFO_H
    #define FIFO_H

    struct fifo
    {
        volatile uint8_t * data_ptr;
        volatile uint16_t size;
        volatile uint16_t write_index;
        volatile uint16_t read_index;
        volatile uint16_t elements;
    };

    #endif

fifo.c
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include "fifo.h"

void fifo_init(struct fifo * fifo)
{
    memset(fifo->data_ptr, (uint8_t)0, fifo->size);
    fifo->write_index = 0;
    fifo->read_index = 0;
}

bool fifo_is_full(struct fifo * fifo)
{
    if (fifo->elements == fifo->size)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

bool fifo_is_empty(struct fifo * fifo)
{
    if (fifo->elements == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

bool fifo_add_byte(struct fifo * fifo, uint8_t newbyte)
{
    if (fifo_is_full(fifo))
    {
        return 0;
    }
    else
    {
        if (fifo->data_ptr == NULL)
        {
            return 0;
        }
        const uint16_t MASK = fifo->size - 1;
        fifo->data_ptr[fifo->write_index] = newbyte;
        fifo->write_index = (++fifo->write_index) & MASK;
        fifo->elements++;
        return 1;
    }
}

bool fifo_get_byte(struct fifo * fifo, uint8_t * output)
{
    if (fifo_is_empty(fifo))
    {
        return 0;
    }
    else
    {
        if (fifo->data_ptr == NULL)
        {
            return 0;
        }
        const uint16_t MASK = fifo->size - 1;
        *output = fifo->data_ptr[fifo->read_index];
        fifo->read_index = (++fifo->read_index) & MASK;
        fifo->elements--;
        return 1;
    }
}

The actual buffer is implemented at other source files like:
uint8_t rx_buffer[RX_BUFFER_SIZE];
struct fifo fifo = {
    .data_ptr = rx_buffer,
    .size = RX_BUFFER_SIZE,
};

Return the condition
When we test for equality, a == b is either 1 if they're equal or 0 if they're not (see C11 §6.5.8 Relational operators). Therefore we can simply return the expression instead of an if-else construct:
bool fifo_is_full(struct fifo * fifo)
{
    return fifo->elements == fifo->size;
}

bool fifo_is_empty(struct fifo * fifo)
{
    return fifo->elements == 0;
}

Feel free to add parentheses around the expression to make it more readable. Alternatively we can use a ternary expression, but that just adds noise and has no additional benefit.
Interrupt safety
fifo_add_byte and fifo_get_byte are not interrupt safe.
Let's say we're using fifo_add_byte somewhere in our usual code but also in an interrupt handler, for example to queue jobs. In main we check current GPIO pin states, and the interrupt comes from some kind of bus.
For the sake of simplicity, let's assume fifo->write_index == 0 and fifo->elements == 0.
We enter fifo_add_byte in main:
// in main:
fifo_add_byte(job_fifo, GPIO_PIN4_STATE);

and follow its definition:
bool fifo_add_byte(struct fifo * fifo, uint8_t newbyte)
{
    if (fifo_is_full(fifo))
    {
        return 0;
    }
    else
    {
        if (fifo->data_ptr == NULL)
        {
            return 0;
        }
        const uint16_t MASK = fifo->size - 1;
        fifo->data_ptr[fifo->write_index] = newbyte;
...

And then an interrupt occurs. We already wrote fifo->data_ptr[0] = GPIO_PIN4_STATE so our data is safe, right?
Well, inside the interrupt handler, we have the following line:
// in interrupt_handler_i2c:
fifo_add_byte(job_fifo, i2c_read_data);

fifo->write_index didn't get updated in our main yet, so our fifo->data_ptr[0] will now be set to i2c_read_data. Afterwards, fifo->write_index gets incremented before we exit the interrupt handler and then again after we enter main again:
// ... back in main:
        fifo->write_index = (++fifo->write_index) & MASK;
        fifo->elements++;
        return 1;
    }
}

Our fifo->data_ptr now contains { i2c_read_data, 0, ... }, fifo->write_index = fifo->elements = 2. However, GPIO_PIN4_STATE's value is lost.
Depending on the plattform, fifo->elements++ or another increment operation might get interrupted and even that operation won't work. And no, volatile isn't a proper solution for interrupts.
We have some ways to remedy this:

we could use critical sections in our index-logic to prevent interrupts
we could use atomic indices/sizes, if our platform supports those
we could mark the fifo "in use" and just return false during an interrupt, but that hinders functionality (it's also very error prone and subject to similar issues)
we could do nothing and simply state that the FIFO isn't safe to be written to from both the usual program and interrupt handlers (same for reading from both locations)

And that's the least we can do to fix this issue: add documentation.
Documentation
None of our code is documented. At least fifo_init needs a documentation, and it needs a very large warning about using a power-of-two size. Otherwise, our MASK logic will yield most interesting behaviours.
The documentation is also the perfect place to state interrupt safety. The FIFO is safe to use within interrupts*, as long as its only written to from within those and only read from outside of an interrupt context.
Usual C-style comments (or Doxygen comments for fancy exports) can be used within our code:
/**
 * \file fifo.c
 *
 * \warning When you use a FIFO in the context of ISRs, make sure that the information
 *          flows only in one direction, e.g. use fifo_add_byte only in ISRs and
 *          fifo_get_byte only in the rest of your program or vice versa.
 *
 *          Using fifo_add_byte in both ISRs and the rest of your program might
 *          yield unexpected results.
*/

...

/**
 * Adds the given byte to the fifo.
 *
 * \returns false if the fifo is full or the data pointer is invalid
 *
 * \warning This function MUST be either used exclusively from ISRs OR the rest
 *          of your program and MUST NOT be used in a recursive ISR context.
*/
bool fifo_add_byte(struct fifo * fifo, uint8_t newbyte)
...

Now, you might think that this is a little bit too much, and you're completely right. The following documentation might prove enough:
/** WARNING WARNING WARNING
 * Only push bytes in interrupt routines and only pull bytes in your `main`
 * (or the other way round)!
*/

However, there should be at least something, even if it will be only read by a future version of you. But that future version will be glad to have some hint why data might get lost or duplicated.
*: Truth be told: that depends whether elements++ and elements-- are atomic operations on our platform.
Parting words
Interrupt safety, code brevity and missing documetation aside: well done. Your code is well-formatted, the overall ring-buffer FIFO design is sound, and it's something I'd write in a similar way. I'm not a fan of the & MASK logic, to be honest, but that's personal preference. Also keep in mind that volatile does not mean thread- or interrupt-safe, so better have a look at the keyword and atomics.
Other than that: Well done.


Pattern finding function for years between 1998 and 2017 with several test cases Pattern matching for years, I need to be able to return all years from a string.

When there is a dash "-" I need to return all numbers between. For example, '2004-2006' should return an array of numbers [2004,2005,2006];
If the number at the beginning of the dash is larger than the number following it, nothing should be printed out. For example '2006-2005' should return [].
years between commas should simply be returned as long as they do not exceed the current year, and are not less than 1999. For example '1998,2020' should return an empty array [].
There should be no duplicates and the values should be ordered.

I believe my code could be written in a more elegant and consise way.

Here are my test cases:

assert.deepEqual(parseRange('2002-2005, 2002-2005, 2002 - 2005'), [2002, 2003, 2004, 2005]);
assert.deepEqual(parseRange('2017'), [2017]);
assert.deepEqual(parseRange('2017 - 2015'), []);
assert.deepEqual(parseRange('2015 - 2015'), [2015]);
assert.deepEqual(parseRange('1999 , 2000,    , 2008'), [1999, 2000, 2008]);
assert.deepEqual(parseRange('2015, 2014, 2010'), [2010, 2014, 2015]);
assert.deepEqual(parseRange('1999, 3000'), [1999]);
assert.deepEqual(parseRange('1998, 2020'), []);

Here is my working Code

function parseRange(string) {
  return [...new Set(string.split(',').map(range => range.includes('-') ? range.split('-').map(num => +num) : +range)
    .filter(set => Array.isArray(set) ? set[0] <= set[1] : set > 1998 && set <= new Date().getFullYear()).reduceRight((arr, val) =>
      arr.concat(Array.isArray(val) ? Array(val[1] - val[0] + 1).fill().map((_, num) => val[0] + num) : val), []))].sort();
}

console.log(parseRange('2002-2005, 2002-2005, 2002 - 2005'));
console.log(parseRange('2017'));
console.log(parseRange('2017 - 2015'));
console.log(parseRange('2015 - 2015'));
console.log(parseRange('1999 , 2000,    , 2008'));
console.log(parseRange('2015, 2014, 2010'));
console.log(parseRange('1999, 3000'));
console.log(parseRange('1998, 2020'));

You're asking for elegance and conciseness. Elegance doesn't always mean short/hackish, and neither does conciseness. You should never sacrifice readability for brevity unless you're codegolfing. As per your comment, just because you can read it doesn't mean the next maintainer or developer can. Someone (maybe you) revisiting this in 5 years should know what the code does without having to pick through it. Let's start by breaking apart the code into its components.

function parseRange2(string) {
  var expr = string.split(',').map(range => range.includes('-') ? range.split('-').map(num => +num) : +range)
  expr = expr.filter(set => Array.isArray(set) ? set[0] <= set[1] : set > 1998 && set <= new Date().getFullYear())
  expr = expr.reduceRight((arr, val) =>
      arr.concat(Array.isArray(val) ? Array(val[1] - val[0] + 1).fill().map((_, num) => val[0] + num) : val), [])
  return [...new Set(expr)].sort()
}

This looks a little more readable. However, someone reading this for a production codebase would have to actually figure out what each expression did. Let's rename some variables and make this easier to digest.

function parseRange2(string) {
  // This expression is still kind of pushing it in terms of readability.
  // Split string in ranges and values
  var ranges = string.split(',').map(range => range.includes('-') ? range.split('-').map(num => +num) : +range)
  // Remove invalid ranges
  var validRanges = ranges.filter(set => Array.isArray(set) ? set[0] <= set[1] : set > 1998 && set <= new Date().getFullYear())
  // Expand range arrays
  var expandedRanges = validRanges.reduceRight((arr, val) =>
      arr.concat(Array.isArray(val) ? Array(val[1] - val[0] + 1).fill().map((_, num) => val[0] + num) : val), [])
  // Return sorted and unique years
  return [...new Set(expandedRanges)].sort()
}

Now let's refactor some of this stuff into helper functions.

const getYearRange = (start, end) => {
  return Array(end - start + 1).fill().map((_, num) => start + num)
}

const isValidEntry = entry => {
  return Array.isArray(entry) ? entry[0] <= entry[1] : entry > 1998 && entry <= new Date().getFullYear()
}

const parseRange2 = string => {
  // This expression is still kind of pushing it in terms of readability.
  // Split string in ranges and values
  var ranges = string.split(',').map(range => range.includes('-') ? range.split('-').map(num => +num) : +range)
  // Remove invalid ranges
  var validRanges = ranges.filter(isValidEntry)
  // Expand range arrays
  var expandedRanges = validRanges.reduceRight((arr, val) =>
      arr.concat(Array.isArray(val) ? getYearRange(val[0], val[1]) : val), [])
  // Return sorted and unique years
  return [...new Set(expandedRanges)].sort()
}

You get the point. You should refactor further to make the code easier to maintain and develop.

Now on the other hand, if you're looking to use every JavaScript hack in the book to golf your code, you could use reduce() instead of reduceRight().

For -2 characters, you could use the following to generate your date range:

[...Array(val[1] - val[0] + 1)].map((_, num) => val[0] + num)

as opposed to:

Array(val[1] - val[0] + 1).fill().map((_, num) => val[0] + num)

You can use the truthiness of arr[0] instead of Array.isArray(arr) to check if an object is an array, which yields the following code:

function parseRange2(string) {
  return [...new Set(string.split(',').map(range => range.includes('-') ? range.split('-').map(num => +num) : +range)
    .filter(set => set[0] ? set[0] <= set[1] : set > 1998 && set <= new Date().getFullYear()).reduce((arr, val) =>
      arr.concat(val[0] ? [...Array(val[1] - val[0] + 1)].map((_, num) => val[0] + num) : val), []))].sort();
}

Addendum: Have you tried '1-10, 1999, 2002-2005, 2002-2005, 2002 - 2005, 2010' as a test case?

Result: [ 1, 10, 1999, 2, 2002, 2003, 2004, 2005, 2010, 3, 4, 5, 6, 7, 8, 9 ]


Accessing multiple data members in Blackjack classes In my Blackjack game so far, I have multiple classes that access each other frequently.  For example, this is my hit() function for the Game class:

void Game::hit(unsigned playerNum)
{
    Card newCard = deck.deal();
    players[playerNum].getPlayerHand()[0].getHandCards().push_back(newCard);
}

First, a new Card object is assigned a new card from the Deck object.  However, the next line gets more complicated.  Essentially:

The specified player's Hand object vector is accessed.  As such, it needs an index.  I'm doing this so that I can easily destroy hands without looping.

players[playerNum].getPlayerHand()[0]

In that one Hand object in the vector, its card vector is accessed.

players[playerNum].getPlayerHand()[0].getHandCards()

That aforementioned card is pushed onto the player's hand card vector.

players[playerNum].getPlayerHand()[0].getHandCards().push_back(newCard);

Again, I'm using a Hand object so that I can easily destroy a player's cards at the end of each turn.  In the game, different players can end up with a different number of cards at the end of each turn.  If I assign each player a vector of cards instead, I would have to loop through the vector and pop each card.  With a Hand, I can just pop the Hand and push a new one.  However, using a Hand class here means more accessing, which complicates the code's flow.

What would be a good solution to this?  I'm okay with either method (preferably the one with Hand), but they do have their pros and cons.  If there is a better solution, I'd like to know about it.

Here are snippets of the relevant class' headers:

Game.h

class Game
{
private:
    std::vector<Player> players;
    Deck deck;

public:
    Game();
    ~Game();
};

Player.h

class Player
{
private:
    std::vector<Hand> playerHand;

public:
    Player();
    ~Player();
    std::vector<Hand>& getPlayerHand() {return playerHand;}
};

Hand.h

class Hand
{
private:
    std::vector<Card> cards;

public:
    Hand();
    ~Hand();
    std::vector<Card>& getHandCards() {return cards;}
};

Card.h

class Card
{
private:
    int rankValue;
    char rank;
    char suit;
    std::string card;

public:
    Card();
    Card(char, char);
    ~Card();
};

This code:

void Game::hit(unsigned playerNum)
{
    Card newCard = deck.deal();
    players[playerNum].getPlayerHand()[0].getHandCards().push_back(newCard);
}

should read:

void Game::hit(unsigned playerNum)
{
    Card newCard = deck.deal();
    players[playerNum].hit(newCard);
}

The thing is, your classes shouldn't access each other like that. You shouldn't have getter methods that return the internal vectors. You should have methods that perform operations. If you do that, I think your question won't even come up.


Parsing a CSV file in node.js and express.js I want to import a CSV file and do some operation on it.

The following is the code I'm using and it is working fine:

 return function (req, res) {
    var rl = require('readline').createInterface({
        input: fs.createReadStream(myFile.csv)
    });

    var lineNumber = 1;
    rl.on('line', function (line) {

        // Validate the first line
        if (lineNumber === 1) {
            if (firstLineIsInvalid()) {
                res.send({
                    status: 'error',
                    message: 'This file deos not have a proper header'
                });
                rl.close();
            }
            lineNumber++;
            return;
        }

        // Validate the 2nd line
        if (isSecondLineInvalid()) {
            res.send({
                status: 'error',
                message: '2nd line must be blank'
            });
            rl.close();
            lineNumber++;
            return;
        }

        // Skip 3rd line
        if (lineNumber === 3) {
            lineNumber++;
            return;
        }

        // Skip the last line, we do not need aggregations
        if (line.indexOf('Total') > -1) {
            lineNumber++;
            return;
        }

        // Start processing
        processLine(line);

        lineNumber++;
    });

    rl.on('close', function () {
        if (!res.headersSent) {
            fs.rename(myFile.csv, archivedFile.csv, function (err) {
                if (err) {
                    res.send({status: 'error',  message: 'Archiving failed, '+ JSON.stringify(err)});
                } else {
                    res.send({status: 'ok'});
                }
            })
        } else {
            fs.rename(myFile.csv, rejectedFile.csv)
        }
        res.end();
    });
}

But I am wondering if there is a better approach for:

Counting the line numbers and validating the lines based on their position in the file.
Reacting to the errors, especially those I get in the validation of the first and second lines.

Your code is fine and the approach will work. However, I do have the following comments based on my own experience.

In the case of error response, why not use the error object to capture the error details and pass return next(err), something to the effect of:

//handling errors in your code woud look like
if(somethingisntright()){

    err.message = 'Something is wrong';
   next(err);
}

//error handler presumably in your app.js
app.use(function(err, req, res){
//if you have multiple errors you could articulate based on assigning err.status
    res.json({
        status: 'error'
        message: err.message,
    });
});

This will reduce the amount of error handling code in the current module and centralize error handling thus reducing maintenance effort in the future.
I'm not sure if it is worth it but you may want to consider short circuiting your logic so that the code handling line numbers >= 3 are handled first. It saves some cycles having to evaluate the first two scenarios for every other line regardless.


Approach for one class to safely refer to another, with both having unknown lifetimes It is not always possible to simplify program design by strictly managing the lifetimes of objects. If two objects have unpredictable lifetimes, but one of them needs to refer to the other, a simple pointer or reference is a segmentation fault waiting to happen.

The approach that I tried first was to have both objects contain a pointer to the other, and code in the destructors of both objects that would set the other object's pointer to null:

#include <iostream>

class Manager;

class Tracked
{
public:
    ~Tracked();
    void act() {std::cout << "hello world!\n";}
    void setManager(Manager *manager) {manager_ = manager;}
    void markManagerInvalid() {manager_ = nullptr;}
private:
    Manager *manager_;
};

class Manager
{
public:
    void attach(Tracked &tracked)
    {
        tracked_ = &tracked;
        tracked_->setManager(this);
    }
    void detach()
    {
        if(tracked_ != nullptr)
        {
            tracked_->markManagerInvalid();
            tracked_ = nullptr;
        }
    }
    void invoke()
    {
        if(tracked_ != nullptr)
            tracked_->act();
    }
private:
    Tracked *tracked_;
};

Tracked::~Tracked()
{
    if(manager_ != nullptr)
        manager_->detach();
}

int main()
{
    Manager manager;
    {
        Tracked tracked;
        manager.attach(tracked);
        manager.invoke(); //output: hello world!
    }//"tracked" goes out of scope: the pointer in "manager" is now invalidated.
    manager.invoke();
}

This works and sounds very simple but in practice it has serious drawbacks:

There is not only tight coupling but also a circular dependency between Tracker and Manager.
In order to have many Manager instances link to the same Tracked instance, the Tracked class would have to incorporate a list of Manager pointers to instances that are linking to it.
The code is complex and error prone, and would get even worse with multiple instances linking to each other.

To get around this I devised a different solution: A dynamically allocated pointer to the Tracked instance. The pointer would be set to nullptr by the pointed Tracked instance in the insance's destructor to mark the instance as expired. The same pointer instance is shared using std::shared_ptr with all objects requiring safe access to the Tracked instance.

#include <iostream>
#include <memory>

class Tracked
{
public:
    using Handle = std::shared_ptr<Tracked*>;
    Tracked() : handle_(new Tracked*(this)) { }
    ~Tracked() {*handle_ = nullptr;}
    void act() {std::cout << "hello world!\n";}
    Handle getHandle() {return handle_;}
private:
    Handle handle_;
};

class Manager
{
public:
    void attach(Tracked &tracked) {handle_ = tracked.getHandle();}
    void detach() {handle_.reset();}
    void invoke()
    {
        if(handle_ != nullptr)
        {
            if(*handle_ != nullptr)
                (*handle_)->act();
        }
    }
private:
    Tracked::Handle handle_;
};

int main()
{
    Manager a, b, c;
    {
        Tracked tracked;
        a.attach(tracked);
        b.attach(tracked);
        a.invoke(); //output: hello world!
    } //"tracked" goes out of scope: the handles in "a" and "b" are now invalidated.
    b.invoke();
    c.invoke();
}

I have found surprisingly little information on this, is this a known idiom or design pattern?

Edit:
At the conclusion of writing this question I realized that I could just allocate the Tracked object with new and manage the object with a std::shared_ptr, distributing a std::weak_ptr to each Manager. If std::weak_ptr::lock() would return a null shared_ptr, the Tracked instance would be expired.

I think using a bit of dynamic allocation std::shared_ptr and std::weak_ptr makes sense as they provide a solid implementation of the tracking behaviour you need.

Your original though has a nice property of not using any dynamic allocation.
If the tracking logic could be refine and made more general if might be a handy bit of library code to have around.

This is my attempt so far:

template <typename T>
class SafeRefTo;

template <typename T>
class Tracked : public T
{
public:
    using T::T;
    ~Tracked();
    void addReferee(SafeRefTo<T> *manager) {safeRefToThis = manager;}
    void markSafeRefInvalid() {safeRefToThis = nullptr;}
private:
    SafeRefTo<T> *safeRefToThis;
};

template <typename T>
class SafeRefTo
{
public:
    template <typename... Args>
    Tracked<T> makeTracked(Args... args)
    {
        Tracked<T> tracked{args...};
        attach(tracked);
        return tracked;
    }

    void attach(Tracked<T> &tracked)
    {
        tracked_ = &tracked;
        tracked_->addReferee(this);
    }
    void detach()
    {
        if(tracked_ != nullptr)
        {
            tracked_->markSafeRefInvalid();
            tracked_ = nullptr;
        }
    }
    template <typename TrackedMemFun, typename... Args>
    void invoke(TrackedMemFun fun, Args... args)
    {
        if(tracked_ != nullptr)
            (tracked_->*fun)(args...);
    }
private:
    Tracked<T> *tracked_;
};

template <typename T>
Tracked<T>::~Tracked()
{
    if(safeRefToThis != nullptr)
        safeRefToThis->detach();
}

Then the client code is simply:

#include <iostream>

class Actor
{
public:
    Actor() = default;
    Actor(std::string extraText)
    :
    extraText(extraText)
    {}

    void act(unsigned int times) {
        for(; times; --times)
        {
            std::cout << "hello world!" << extraText << "\n";
        }
    }

private:
    std::string extraText;
};

int main()
{
    SafeRefTo<Actor> manager;
    {
        auto tracked(manager.makeTracked());
        manager.invoke(&Actor::act, 1); //output: hello world!
    }//"tracked" goes out of scope: the pointer in "manager" is now invalidated.
    manager.invoke(&Actor::act, 1);
}


HTTP Response/Request Class This is just a simple class that you can you use to send requests and get the HTML code. I would like to get feedback on this.

For your request you can set:

URL
Request method: GET or POST
Request parameters: if you need to pass parameters
Request cookie

As a response you will get:

HTML
Response cookie

Request

class Request
{
    public string Url { get; set; }
    public string RequestMethod { get; set; }
    public string RequestParameters { get; set; }
    public string RequestCookie { get; set; }
    public string ResponseCookie { get; private set; }

    /// <summary>
    /// Send Request To URL
    /// </summary>
    /// <returns>HTML Text of URL</returns>
    public string SendRequest()
    {
        try
        {
            HttpWebRequest request = (HttpWebRequest)WebRequest.Create(Url);

            request.Method = RequestMethod;
            request.UserAgent = "Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.0.4) Gecko/20060508 Firefox/1.5.0.4";

            if (RequestCookie != null)
            {
                request.Headers["Cookie"] = RequestCookie;
            }

            WebProxy myProxy = new WebProxy("localhost", 8888);
            request.Proxy = myProxy;

            if (RequestParameters != null)
            {
                byte[] bytes = Encoding.UTF8.GetBytes(RequestParameters);
                request.ContentLength = bytes.Length;

                Stream requestStream = request.GetRequestStream();
                requestStream.Write(bytes, 0, bytes.Length);
            }

            HttpWebResponse response = (HttpWebResponse)request.GetResponse();
            response.Headers["Set-Cookie"] = ResponseCookie;

            StreamReader reader = new StreamReader(response.GetResponseStream());

            return reader.ReadToEnd();
        }
        catch (WebException ex)
        {
            StreamReader streamReader = new StreamReader(ex.Response.GetResponseStream());

            return streamReader.ReadToEnd();
        }
    }
}

Example

static void Main(string[] args)
    {
        Request myRequest = new Request();

        myRequest.Url = "https://google.com";
        myRequest.RequestMethod = "GET";

        string html = myRequest.SendRequest();

        Console.WriteLine("REQUEST DONE !");

        Console.WriteLine(html);

        Console.ReadKey();
    }

I don't quite see the purpose of your class. You are basically taking an existing class from the .NET Framework and wrapping it up in something that only exposes a fraction of the functionality.

The code also relies on a lot of hard-coded settings. While specifying a specific user-agent might not cause too much concern, always using a specific HTTP proxy will.

You provide the results of the request in two ways. The actual HTML is returned as a string from the method (what if the site returns binary content?), while the cookies are set in a property. It's strange to have a class called Request that contains a property starting with Response. The approach taken by the HttpWebRequest is much cleaner as it returns a whole class that contains all the information of the reply.


Project Euler #3 solution I'm trying to solve Project Euler problem #3, which asks:

  The prime factors of 13195 are 5, 7, 13 and 29.
  What is the largest prime factor of the number 600851475143 ?

Can you please review the code and suggests improvements?

namespace FullPractice
{
  public class PrimeFactorFinder
  {
    private readonly HashSet<int> _myPrimeFactors = new HashSet<int>();
    private long _myNumber;

    public void PrimeFactors(long number)
    {
        _myNumber = number;
        FindPrimeFactors();
        DisplayAllPrimeFactors();
        ShowLargestPrimeFactor();
    }

    private void ShowLargestPrimeFactor()
    {
        Console.WriteLine("\nLargest Prime Factor = {0}",_myPrimeFactors.Last());
    }

    private void FindPrimeFactors()
    {
        long temp = _myNumber;
        int primeNumber = 2;
        while (temp != 1)
        {
            if (temp%primeNumber == 0)
            {
                _myPrimeFactors.Add(primeNumber);
                temp = temp/primeNumber;
            }
            else
            {
                primeNumber = GetPrimeNumberAfter(primeNumber);
            }
        }
    }

    private void DisplayAllPrimeFactors()
    {
        Console.WriteLine("All prime factors of {0} are : ", _myNumber);
        foreach (var primeFactor in _myPrimeFactors)
        {
            Console.Write("{0},", primeFactor);
        }
    }

    private int GetPrimeNumberAfter(int primeNumber)
    {
        var next = primeNumber + 1;
        while (true)
        {
            if (IsPrime(next))
            {
                return next;
            }
            next++;
        }
    }

    private bool IsPrime(int number)
    {
        if (number%2 == 0)
        {
            return false;
        }
        var sqaureRoot = (int)Math.Sqrt(number);
        for (int divisor = 3; divisor < sqaureRoot; divisor += 2)
        {
            if (number%divisor == 0)
            {
                return false;
            }
        }
        return true;
    }
}
}

PrimeFactors why do you do output there? It would be much better if you return an IEnumerable<long> with all the prime factors of the number passed as input. Let the client decide what it needs to do with the result. It might need to output it but it might need to do something with all the prime factors instead.

Why do you create an object for that class? It should not hold any state. What you need is a static method. It should be something purely functional. static IEnumerable<long> PrimeFactors(long number).
With your code, the client of your code has to instantiate a new PrimeFactors instance, which is useless.

Holding the state also causes it to produce wrong results in cases such as the following:

var primeFactorFinder = new PrimeFactorFinder();
primeFactorFinder.PrimeFactors (33);
primeFactorFinder.PrimeFactors (5);

which outputs:

All prime factors of 33 are :
3,11,
Largest Prime Factor = 11
All prime factors of 5 are :
3,11,5,
Largest Prime Factor = 5

clearly something went wrong because _myPrimeFactors, which should really be local to FindPrimeFactors never got cleared between the first and the second invocation of PrimeFactors.

Your algorithm looks ok. If you need more performances you probably need to trade some memory for a better execution time and adopt a solution based on a Sieve of Eratosthenes-like approach.


Beating built-in timsort with own count sort function I am trying to write a count sort in Python to beat the built-in timsort in certain situations. Right now it beats the built-in sorted function, but only for very large arrays (1 million integers in length and longer, I haven't tried over 10 million) and only for a range no larger than 10,000. Additionally, the victory is narrow, with count sort only winning by a significant margin in random lists specifically tailored to it.

I have read about astounding performance gains that can be gained from vectorizing Python code, but I don't particularly understand how to do it or how it could be used here. I would like to know how I can vectorize this code to speed it up, and any other performance suggestions are welcome.

def countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1

    sorted_list = []
    for num in xrange(min(unsorted_list), max(unsorted_list) + 1):
        if num in counts:
            for j in xrange(counts[num]):
                sorted_list.append(num)

    return sorted_list

GitHub

Additional info:

All that counts is raw speed here, so sacrificing even more space for speed gains is completely fair game.
I realize the code is fairly short and clear already, so I don't know how much room there is for improvement in speed.
If anyone has a change to the code to make it shorter, as long as it doesn't make it slower, that would be awesome as well.
After doing some more precise timing, it is clear that the first for loop takes about 2/3 of the execution time, with the second, constructor, loop taking just 1/3 of the time.

I did some benchmarks using the timeit module and this test data:

random.seed(1)
data = [random.randint(0,10000) for _ in xrange(1000000)]

Original version clocks in at 411 ms, and the builtin sorted at 512 ms.

Using counts = defaultdict(int) that allows unconditional counts[num] += 1 takes it to 330 ms.

Using sorted_list.extend(counts[num] * [num]) instead of the inner loop improves to 250 ms, or 246 ms when also omitting the second if.

Using min(counts), max(counts) instead of min(unsorted_list), max(unsorted_list) improves further to 197 ms.

Using chain and repeat from itertools to construct the result takes 182 ms (though repeat does not make much difference).

Code looks like this after the changes:

from collections import defaultdict
from itertools import chain, repeat

def countsort(unsorted_list):
    counts = defaultdict(int)
    for num in unsorted_list:
        counts[num] += 1

    return list(
            chain.from_iterable(
                repeat(num, counts[num])
                for num in xrange(min(counts), max(counts) + 1)))


Am I being too redundant in this Django view (or can I reduce the repetition in my code)? I'm new to Django and learning my ways around it. I'm writing a fake basic CRUD app to get me started. In the following code I pretty much copy and paste the same code four times with minor adjustments between each. I only pasted it here twice for the Bands and Album models.

Am I doing this right?

from django.shortcuts import render, get_object_or_404, redirect
from django.contrib.auth.decorators import login_required
from django.template import RequestContext

from models import Band, Album, Song, Instrument

from forms import BandForm, AlbumForm

# Bands Functions:

def bands_index(request):
    latest_band_list = Band.objects.all().order_by('-added_on')[:5]
    return render(request,
                  "bands/index.html", {
                  'latest_band_list': latest_band_list
                  })

def band_detail(request, band_id):
    b = get_object_or_404(Band, pk=band_id)
    return render(request, 'bands/detail.html', {'band': b})

@login_required
def band_add(request):
    form = BandForm(request.POST or None)

    if request.method == 'POST' and form.is_valid():
        instance = form.save(commit=False)
        instance.added_by = request.user
        instance.save()

        return redirect('/bands/')
    else:
        return render(request, 'bands/add.html',
            {'form': form},
            context_instance=RequestContext(request))

@login_required
def band_remove(request, band_id):
    b = get_object_or_404(Band, pk=band_id)
    b.delete()

    return redirect('/bands/')

@login_required
def band_edit(request, band_id):
    b = get_object_or_404(Band, pk=band_id)

    form = BandForm(request.POST or None, instance=b)

    if request.method == 'POST' and form.is_valid():
        instance = form.save(commit=False)
        instance.save()

        return(redirect('/bands/'))
    else:
        return render(request, 'bands/edit.html',
            {'form': form, 'band_id': band_id},
            context_instance=RequestContext(request))

# Album Functions

def albums_index(request):
    latest_album_list = Album.objects.all().order_by('-added_on')[:5]
    return render(request, "albums/index.html", {
        'latest_album_list': latest_album_list
        })

def albums_detail(request, album_id):
    a = get_object_or_404(Album, pk=album_id)
    return render(request, 'albums/detail.html', {'album': a})

@login_required
def album_add(request):
    form = AlbumForm(request.POST or None)

    if request.method == 'POST' and form.is_valid():
        instance = form.save(commit=False)
        instance.added_by = request.user
        instance.save()

        return redirect('/albums/')
    else:
        return render(request, 'albums/add.html',
            {'form': form},
            context_instance=RequestContext(request))

@login_required
def album_remove(request, album_id):
    a = get_object_or_404(Album, pk=album_id)
    a.delete()
    return redirect('/albums/')

@login_required
def album_edit(request, album_id):
    a = get_object_or_404(Album, pk=album_id)

    form = AlbumForm(request.POST or None, instance=a)

    if request.method == 'POST' and form.is_valid():
        instance = form.save(commit=False)
        instance.save()

        return(redirect('/albums/'))
    else:
        return render(request, 'albums/edit.html',
            {'form': form, 'album_id': album_id},
            context_instance=RequestContext(request))

I'd say the best way to be "less redundant" would be to use the already-existing generic views - e.g. DetailView instead of your band_detail.

(I assume you're looking for "the right way to do things" rather than "I'm reinventing the wheel to learn"...)


Hackerrank New Year Chaos My code given below will produce the correct output but it tends to take way too much time with larger data thus timing out for some of the test cases. I've linked to the problem description here:

  It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride!

  There are n people queued up, and each person wears a sticker indicating their initial position in the queue (i.e. 1, 2, ..., n - 1, n: with the first number denoting the frontmost position).

  Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original place in line. One person can bribe at most two other persons.

  That is to say, if n = 8 and Person 5 bribes Person 4, the queue will look like this:
  1, 2, 3, 5, 4, 6, 7, 8.

  Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

  Note: Each Person X wears sticker X, meaning they were initially the Xth person in queue.

  Input Format

  The first line contains an integer, T, denoting the number of test cases.
  Each test case is comprised of two lines; the first line has n (an integer indicating the number of people in the queue), and the second line has n space-separated integers describing the final state of the queue.

  Constraints

  $$ 1 \leq T \leq 10 $$
  $$ 1 \leq n \leq 10^5 $$

  Subtasks

  For 60% score $$1 \leq n \leq 10^3$$
  For 100% score $$1 \leq n \leq 10^5$$

  Output Format

  Print an integer denoting the minimum number of bribes needed to get the queue into its final state; print Too chaotic if the state is invalid (requires Person X to bribe more than 2 people).

  Sample Input

  2
5
2 1 5 3 4
5
2 5 1 3 4

  Sample Output

  3
Too chaotic

Any help/advice/suggestion is welcome.

#!/bin/python3

import sys

inp0 = sys.stdin.read()
inp1 = inp0.split('\n')
T = int(inp1[0])
del inp1[0]

# Swaps the i'th and (i-1)'th elements and returns the list
def swap(intermediate_q,i):
    intermediate_q[i],intermediate_q[i-1] = intermediate_q[i-1],intermediate_q[i]
    return(intermediate_q)

# Increment bribes and total_bribes
def compute_bribes(bribes,total_bribes):
    if(bribes+1==3):
        return (-1,-1)
    return (bribes+1,total_bribes+1)

for i in range(0,(2*T)-1,2):
    n = int(inp1[i])
    final_q = list(int(i) for i in inp1[i+1].split(' '))
    initial_q = list(i+1 for i in range(n))
    total_bribes,chaos_flag=0,0
    for i in range(n):
        bribes = 0
        # If the position in the initial/transition queue is not equal to the position in the final queue
        # final_q is the input against which swaps are made in my initial_q.
        if(final_q.index(initial_q[i]) != initial_q.index(initial_q[i])):
            index_in_initial_q = initial_q.index(final_q[i])
            index_in_final_q = final_q.index(final_q[i])
            while(index_in_initial_q != index_in_final_q):
                initial_q = swap(initial_q,index_in_initial_q)
                bribes,total_bribes = compute_bribes(bribes,total_bribes)
                if(bribes == -1):
                    print("Too chaotic")
                    chaos_flag=1
                    break
                index_in_initial_q-=1
        if(chaos_flag == 1):
            break
    if (chaos_flag == 1):
        continue
    print(total_bribes)

Code organisation

You've tried to split your logic into smallish functions which is a good idea but you could go further. You should try to write a function that handles the input/output part and a function which takes a well defined input (with the most relevant data types as an argument) and computes whatever needs to be computed before returning it (such a function should not do any input parsing or print anything except for debug purposes).

In you case, the most logical input such a function would take is the queue. The corresponding data type would be a list of int and the return type would be an integer (or None).

If you do so, you have smaller independant logical parts which are easier to understand, to maintain and to tests. Among other things, you can write unit tests based on the examples provided to ensure the computation works well.

In you case, moving the different pieces of logic around, you get something like:

#!/bin/python3

import sys

# Swaps the i'th and (i-1)'th elements and returns the list
def swap(intermediate_q,i):
    intermediate_q[i],intermediate_q[i-1] = intermediate_q[i-1],intermediate_q[i]
    return(intermediate_q)

# Increment bribes and total_bribes
def compute_bribes(bribes,total_bribes):
    if(bribes+1==3):
        return (-1,-1)
    return (bribes+1,total_bribes+1)

def get_number_brides(queue):
    """Take a queue (list of int) as a parameter and return the number of brides or None."""
    n = len(queue)
    initial_q = list(i+1 for i in range(n))
    total_bribes = 0
    for i in range(n):
        bribes = 0
        # If the position in the initial/transition queue is not equal to the position in the final queue
        # queue is the input against which swaps are made in my initial_q.
        if(queue.index(initial_q[i]) != initial_q.index(initial_q[i])):
            index_in_initial_q = initial_q.index(queue[i])
            index_in_queue = queue.index(queue[i])
            while(index_in_initial_q != index_in_queue):
                initial_q = swap(initial_q,index_in_initial_q)
                bribes,total_bribes = compute_bribes(bribes,total_bribes)
                if(bribes == -1):
                    return None
                index_in_initial_q-=1
    return total_bribes

def test_stdio():
    inp0 = sys.stdin.read()
    inp1 = inp0.split('\n')
    T = int(inp1[0])
    del inp1[0]
    print("inp1", inp1)
    for i, val in enumerate(inp1):
        if i % 2 == 1:
            ret = get_number_brides([int(v) for v in val.split(' ')])
            print('Too chaotic' if ret is None else ret)

def unit_tests():
    assert get_number_brides([2, 1, 5, 3, 4]) == 3
    assert get_number_brides([2, 5, 1, 3, 4]) is None

if __name__ == "__main__":
    unit_tests()
    # test_stdio()

Among the nice benefits, because the function is now used for a single test case, I can return directly from the most relevant place and this is no need for a chaos_flag anymore (if you were to keep such a flag, it'd be a good idea to use the Boolean type).

Style

Python has a Style Guide called PEP 8 which is definitly worth having a look at and following. In your case, the spacing (both vertical and horizontal) is not quite perfect and so is the usage of useless parenthesis.

Fixing this, you get:

#!/bin/python3

import sys

# Swaps the i'th and (i-1)'th elements and returns the list
def swap(intermediate_q, i):
    intermediate_q[i], intermediate_q[i-1] = intermediate_q[i-1], intermediate_q[i]
    return(intermediate_q)

# Increment bribes and total_bribes
def compute_bribes(bribes, total_bribes):
    if bribes + 1 == 3:
        return (-1, -1)
    return (bribes + 1, total_bribes + 1)

def get_number_brides(queue):
    """Take a queue (list of int) as a parameter and return the number of brides or None."""
    n = len(queue)
    initial_q = list(i + 1 for i in range(n))
    total_bribes = 0
    chaos_flag = False
    for i in range(n):
        bribes = 0
        # If the position in the initial/transition queue is not equal to the position in the final queue
        # queue is the input against which swaps are made in my initial_q.
        if queue.index(initial_q[i]) != initial_q.index(initial_q[i]):
            index_in_initial_q = initial_q.index(queue[i])
            index_in_queue = queue.index(queue[i])
            while index_in_initial_q != index_in_queue:
                initial_q = swap(initial_q, index_in_initial_q)
                bribes, total_bribes = compute_bribes(bribes, total_bribes)
                if bribes == -1:
                    return None
                index_in_initial_q -= 1
    return total_bribes

def test_stdio():
    inp0 = sys.stdin.read()
    inp1 = inp0.split('\n')
    T = int(inp1[0])
    del inp1[0]
    print("inp1", inp1)
    for i, val in enumerate(inp1):
        if i % 2 == 1:
            ret = get_number_brides([int(v) for v in val.split(' ')])
            print('Too chaotic' if ret is None else ret)

def unit_tests():
    assert get_number_brides([2, 1, 5, 3, 4]) == 3
    assert get_number_brides([2, 5, 1, 3, 4]) is None

if __name__ == "__main__":
    unit_tests()
    # test_stdio()

I have no time to go any further but I hope this will help you, another reviewer and future me to take over.


Splitting an array at commas I was given a file of size 46KB full of names (around ~5000), in the format as shown below:

"MARY","PATRICIA","LINDA","BARBARA","ELIZABETH"..."DARRELL","ALONSO"

I wonder if my code below is optimal in doing what I want, which is to translate this txt file into an array of names.

array = []
File.readlines('names.txt').each do |l|
  array << l.delete("\"").split(",")
end

array.flatten

Yes it is, it takes 0.372798 seconds to run on my computer for a 50 MB file, for a 46KB file this runs in the blink of an eye.

Anyway as this is Codereview I suggest an equally fast but higher level version of your code:

def get_names(filename)
    File.read(filename).tr('"', '').split(',')
end


Weighted Probability Problem in Swift I was asked a weighted probability question in a technical interview a few months ago that went something like this:

  Given an input of colors and an integer "weight" value, randomly return a color based on its weight.

The sample input would be something like this:

[("Red", 20), ("Blue", 50), ("Green", 70)]

The probability that each color would be returned would be something like:

Red: 20/140

Blue: 50/140

Green: 70/140

(where 140 is the sum of the weight of the input colors)

I was thinking about this recently and decided to give it another go in Swift.

My first pass was:

func weightedColor(input: [(String, Int)]) -> String {

    var total = 0

    for tuple in input {
        total += tuple.1
    }

    let rand = Int(arc4random_uniform(UInt32(total)))

    var sum = 0
    for tuple in input {
        let range = sum + tuple.1

        if rand <= range {
            return tuple.0
        } else {
            sum += tuple.1
        }
    }

    return ""
}

Then I realized I could optimize the total weight calculation with map-reduce:

let total = UInt32(input.map { $0.1 }.reduce(0, combine: +))

My current implementation is as follows:

func weightedColor(input: [(String, Int)]) -> String {

    let total = UInt32(input.map { $0.1 }.reduce(0, combine: +))

    let rand = Int(arc4random_uniform(total))

    var sum = 0
    for tuple in input {
        let range = sum + tuple.1

        if rand <= range {
            return tuple.0
        } else {
            sum += tuple.1
        }
    }

    return ""
}

I don't like the for tuple in input loop and feel it can be optimized further.  How can I improve this answer?

There is one error in your implementation: The test
if rand <= range must be if rand < range, otherwise the returned
values are not correctly distributed according to the given weights.
You can check that with the input list

[("Red", 1), ("Blue", 1)]

which returns only "Red" without this fix.

Apart from that, your code looks correct, but there are some
possible improvements.

The final return "" is never reached unless you made a programming
error. Instead of returning some value (in order to satisfy the compiler), replace it by

fatalError("This should never be reached")

This will stop the program execution immediately, and
fatalError() has the @noreturn attribute, so the compiler won't
complain about a missing return value.
Replace for tuple in input { } by for (color, weight) in input,
that allows you to get rid of the non-descriptive tuple.0 and tuple.1
in the loop body.
Add the current weight to the sum before testing against rand,
that makes the range variable obsolete.

The function does then look like this:

func weightedColor(input: [(String, Int)]) -> String {

    let total = UInt32(input.map { $0.1 }.reduce(0, combine: +))
    let rand = Int(arc4random_uniform(total))

    var sum = 0
    for (color, weight) in input {
        sum += weight
        if rand < sum {
            return color
        }
    }

    fatalError("This should never be reached")
}

The next step is to make the function generic.
There is nothing which is special to colors or strings,
so you can simply replace String by a generic type T:

func weightedRandomElement<T>(items: [(T, Int)]) -> T {

    let total = UInt32(items.map { $0.1 }.reduce(0, combine: +))
    let rand = Int(arc4random_uniform(total))

    var sum = 0
    for (element, weight) in items {
        sum += weight
        if rand < sum {
            return element
        }
    }

    fatalError("This should never be reached")
}

Then the same function can be used to get a random color:

let colors = [("Red", 20), ("Blue", 50), ("Green", 70)]
let color = weightedRandomElement(colors)

or a random number:

let numbers = [(3.1415, 20), (2.71827, 50)]
let number = weightedRandomElement(numbers)

or anything else.

Update: As @hashemi correctly said, the fatalError() point would
also be reached if the function is called with an empty array.
Actually that would also happen if the function is called with a non-empty array but the sum of the given weights is zero. These
situations could be considered as a programming error on the caller's side and can be checked with a  precondition().

@hashemi also suggested to use UInt instead of Int as data type
for the weights. This is more natural because the weights must not
be negative (and unexpected results would happen for negative input).

Then the function looks like this:

func weightedRandomElement<T>(items: [(T, UInt)]) -> T {

    let total = items.map { $0.1 }.reduce(0, combine: +)
    precondition(total > 0, "The sum of the weights must be positive")

    let rand = UInt(arc4random_uniform(UInt32(total)))

    var sum = UInt(0)
    for (element, weight) in items {
        sum += weight
        if rand < sum {
            return element
        }
    }

    fatalError("This should never be reached")
}

and is called like

let colors : [(String, UInt)] = [("Red", 20), ("Blue", 50), ("Green", 70)]
let color = weightedRandomElement(colors)


Checking if each char in a string is a decimal digit I had to write a program that would verify that a string contains any digits beside numbers 0-9 and the first '-' sign to indicate if pos/neg. The algorithm works like I want it to, but is there a better way of writing it, e.g. streamlining it, making it shorter?

bool isNum(string number) {
    // Checks if first char in buffer contains invalid digits
    // Needed because any negative sign after the one used to indicate negative sign.
    if (!((number[0] >= '0' && number[0] <= '9') || number[0] == '-' || number[0] == '+'))
        return false;

    // Checks if each digit after the first is anything but 0-9
    for (int i = 1; number[i] != '\0'; i++) {
        if (number[i] < '0' || number[i] > '9')
            return false;
    }
    // If neither statement returns false, returns true by default
    return true;
}

In the cctype header, you have the std::isdigit(int) function. You can use this instead of your conditions that check if the character is between '0' and '9'.
You index into a std::string with an int inside the for loop. Use std::string::size_type as that is the proper type that can index into a std::string (int might be too small).
Mark the function as noexcept.
Consider passing the std::string parameter by reference if you're planning on using large number strings (~20 character numbers). This prevents unnecessary copying from dynamically allocated strings.
Check vs. the size instead of indexing into the string and checking if the current character is '\0'.
Qualify standard types with std::. Don't use using namespace std;.
There is no need to negate that first condition.
Bug: isNum("-") and isNum("+") return true. An additional check is required if the first character is '+' or '-'.
Naming is important. Your function is called isNum(), but I believe that isInt() better describes it; the function does not detect floating point numbers. Please also consider this comment by Toby Speight in regards to naming.

After changes are applied:

#include <string>
#include <cctype>

bool isinteger(std::string const& n) noexcept
{
    if (std::isdigit(n[0]) || (n.size() > 1 && (n[0] == '-' || n[0] == '+')))
    {
        for (std::string::size_type i{ 1 }; i < n.size(); ++i)
            if (!std::isdigit(n[i]))
                return false;

        return true;
    }
    return false;
}

Note 1: I've renamed the function to isinteger() to keep consistency with other similar functions such as isdigit(). I've also reordered the initial condition to take advantage of boolean short circuiting.

Note 2: As Rakete1111 points out, if your compiler hasn't caught up to C++11 yet, accessing the first character of an empty string is undefined behaviour.

The condition should be modified like so:

// check that the string is not empty, only if we're working with < C++11
if ((!n.empty() && std::isdigit(n[0])) || (n.size() > 1 && (n[0] == '-' || n[0] == '+')))
{
    // ...
}

However, if your compiler is C++11 (or later) compliant, you can safely leave it; accessing the first character of empty strings returns '\0' in that case.

See here for more information: http://en.cppreference.com/w/cpp/string/basic_string/operator_at


C++ latch implementation Since std::latch is not in many standard C++ libraries, I tried implementing my own, is it OK from memory ordering perspective or yielding?

class Latch {
    std::atomic<unsigned> count;

public:
    explicit Latch(unsigned cnt)
        : count(cnt)
    {
    }

    void arrive_and_wait()
    {
        assert(count > 0);

        count.fetch_sub(1, std::memory_order_release);
        while (count.load(std::memory_order_acquire) > 0) {
            std::this_thread::yield();
        }
    }
};
```

First the obvious stuff: the real std::latch::arrive_and_wait is specified to take a ptrdiff_t parameter that defaults to 1, but would also support e.g. myLatch.arrive_and_wait(2). Also, there are more member functions than just arrive_and_wait.

I'd call your thing a "spinlatch" (by analogy to "spinlock"), because it doesn't actually put the thread to sleep — it has an operation named arrive_and_wait that doesn't actually do any waiting! It just keeps loading and loading the atomic variable until it sees zero.

To make it actually wait, you could use the also-new-in-C++20 futex facilities of std::atomic, like this:

void arrive_and_wait(int n = 1) {
    int current = (count -= n);
    if (current == 0) {
        count.notify_all();
    } else {
        while (current != 0) {
            count.wait(current);
            current = count.load();
        }
    }
}

No comment on the memory orders.


Dice sums comparison probability I was playing a fun little board game called U.S. Patent No. 1 about time traveling to register your time machine as the first U.S. patent. I started to wonder what the dice probabilities were for basic attacks. In the game, you rolls 2 dice to attack, and your opponent rolls 1 die for defense. If the attack result is greater than the defense, then a time machine part is "disabled", and if it is greater by 5 or more, than it is "destroyed"; otherwise it "misses". However, this is not the end: players can also have attack and defense bonuses ranging from 0-12, which are added to the roll result before making the comparison.

To begin my program, I first did a straightforward brute force calculation, where each number in the array was a probability out of 216, and attack and defense bonus from 0 through 12 were cycled through.

But this was a bit slower than I wanted (~500ms, not terrible), so I decided to utilize a bit more math and hardcode the probability distribution of two dice to use multiplication instead of addition. I also replaced the dict with enum keys with a list where 0 is "MISSED", 1 is "DISABLED", and 2 is "DESTROYED", which seemed to significantly reduce overhead by my timings (from ~200ms to ~50ms).

But then I looked more carefully at my results and realized something that is in retrospect obvious about probability distributions of this nature: adding one to both the attack and defense bonus means the bonuses have no affect on the distribution. Represented symbolically, the distribution for A, D is always going to be the same as the distribution for A + N, D + N for integers N. So instead of calculating separate values for attack and defense bonuses, I can just calculate a raw value for attack shift (which also reformatted my array to be smaller and have different dimensions):

from itertools import product
import numpy as np

def calculate():
    two_dice_prob = [0, *range(6), *range(6,0,-1)]
    result = np.zeros((25,3))
    for attack_shift in range(-12, 13):
        result_counts = [0] * 3
        for defense, attack in product(range(1,7), range(2,13)):
            base_attack = attack
            attack += attack_shift
            if attack - 5 >= defense:
                result_counts[2] += two_dice_prob[base_attack]
            elif attack > defense:
                result_counts[1] += two_dice_prob[base_attack]
            else:
                result_counts[0] += two_dice_prob[base_attack]
        result[attack_shift+12] = result_counts
    return result

if __name__ == '__main__':
    print("Result:")
    print(calculate())

The result is a numpy array where the top is an attack with a penalty of -12, and the bottom is the attack with a bonus of 12, and every other row has an attack bonus of 1 more than the previous row. By merit of processing less cases, it now only takes ~6ms.

I was wondering how I could optimize the calculate function even more. I suspect I am not utilizing numpy's efficiency fully, since I am still not completely familiar with it.

1. Review

The name calculate is vague. Something like attack_freq would be more specific.
There's no docstring. What does calculate do? What does it return?
The values in two_dice_prob are not probabilities, they are counts or frequencies. (To get probabilities, you'd have to divide by 36.) I would use a name like two_dice_freq.
By default numpy.zeros gives you an array of floats, but the result array only contains integers, so you could specify dtype=int when creating it. (Alternatively, by constructing the result using NumPy throughout, it can be arranged that it has the right data type.)
When working with NumPy it's nearly always fastest if you structure the code to consist of a sequence of whole-array operations, rather than looping over the elements in native Python.

In this case we can use numpy.mgrid to construct arrays containing all possibilities for attack shift, defence roll and attack roll:

shift, defence, attack = np.mgrid[-12:13, 1:7, 2:13]

Then we can find the difference between attack and defence simultaneously for all possibilities:

diff = attack + shift - defence

The three outcome classes can now be computed by comparing the difference against 0 and 5 to get arrays of Booleans, and then assembling the outcomes into a single array using numpy.stack:

missed = diff <= 0
destroyed = diff >= 5
disabled = ~(missed | destroyed)
outcome = np.stack((missed, disabled, destroyed), axis=1)

The reason for choosing to stack along axis=1 is so that the outcome array has the right shape, that is, (25, 3, 6, 11). We multiply the last axis by the two-dice frequencies, and then sum over the last two axes. This leaves us with an array of frequencies with shape (25, 3) as required:

return (outcome * two_dice_freq).sum(axis=(2, 3))

If we had chosen to stack along axis=0, then at this point we would have an array with shape (3, 25) and we'd have to transpose it before returning. By choosing the right axis to stack along we avoided this transposition.

2. Revised code

import numpy as np

def attack_freq():
    """Return array with shape (25, 3), whose (i + 12)'th row contains the
    frequencies of the three outcome classes (missed, disabled,
    destroyed) when attack bonus minus defense bonus is i.

    """
    two_dice_freq = [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
    shift, defence, attack = np.mgrid[-12:13, 1:7, 2:13]
    diff = attack + shift - defence
    missed = diff <= 0
    destroyed = diff >= 5
    disabled = ~(missed | destroyed)
    outcome = np.stack((missed, disabled, destroyed), axis=1)
    return (outcome * two_dice_freq).sum(axis=(2, 3))

This computes the same results as the code in the post:

>>> np.array_equal(calculate(), attack_freq())
True

but it's roughly four times as fast:

>>> from timeit import timeit
>>> timeit(calculate, number=1000)
0.38954256599993187
>>> timeit(attack_freq, number=1000)
0.09676001900004394

The actual runtimes are so small, less than a millisecond, that this speedup doesn't really matter in practice, since you'd only need to build this table once. However, the general technique, of applying a series of whole-array NumPy operations instead of looping in native Python, can make practical differences in other kinds of program, so it's worth practicing the technique even in small cases like this.


Revealing module implicity calling an internal function - is this a “smell” I'm trying to improve my javascript and have been using the revealing module pattern to good effect but I noticed that code in the module not in a function or the return is executed on creation have utilised this, such as:

var MyModule = function ($) {

    setUp();

    function setUp() {
        // execute code to be run when module created
    }

    function doStuff() {
    }

    return {
        doStuff: doStuff
    }
}

I can see this is creating a form of constructor for the function which relies on it being called by var myModule = new MyModule(jQuery).

Any feedback on the rights or wrongs of this appreciated.

In this case, you don't actually use the new keyword. It's valid to return something from a constructor, since constructors are functions as well. But when you use new to construct objects, it should return an instance of that constructor. In your case, you are returning an object, one that is not tied in any way to the constructor.

Here's the revealing module pattern and how it's used:

function createModule(name){

  //your private members, enclosed in createModule
  var privateVar = name;

  function privateFn(){
    console.log(privateVar);
  }

  //return a newly created object as the module
  return {
    //here, we have a function
    //since we live in the same scope as the privates, we can
    //also emulate getters and setters, classical OOP style
    getName : function(){
      privateFn();
    },
    setName : function(name){
      privateVar = name;
    }
  }
}

var newModule = createModule('mymodule');
newModule.getName(); //mymodule
newModule.setName('newname');
newModule.getName(); //newname

Now there are issues with this pattern, especially in usage:

Pros

It emulates private members. This would be an easy start for developers coming from Classical OOP.
Since the members are directly attached in the module, or at least only one scope above in the closure, they are fast.
No prototype chains to worry about.

Cons

Creating multiple modules mean creating multiple objects, each with it's own scope and functions. One module's getName function is not the same as another module's getName(). Although perfectly fine (And that's how classical OOP works, as far as I know), it's bad for the browser since it uses too much memory.
You can't use instanceof to determine the modules since they all are instances of the Object object, and they are all object literals ({}) to begin with.

Best use

Single global modules, like libraries.

For spawning many modules, I suggest the native way of doing it, and would be creating instances using constructors and prototypes.

function Module(name){
  this.name = name;
}

createModule.prototype.getName = function(){
  console.log(this.name);
}

var newModule = new Module('mymodule');
newModule.getName(); //mymodule
newModule.name = 'newname';
newModule.getName(); //newname

It has its own issues as well:

Pros

Smaller memory footprint. Anything attached to the constructor's prototype is shared, not duplicated, across instances. This means one instance's getName is the same function as another instance's getName. This is because of the prototype chain (think of it as inheritance chain), where instances "inherit" the same object.

Cons

No private scope
A long prototype chain is a performance penalty, especially if the method lives far up the chain.
Overkill for a single module. It was meant to spawn multiple instances.

Best Use

Spawning multiple instances of the same kind, like elements in a game (units, enemies, bullets).

What should you use:

Depends. Libraries usually use a mix as well.

Take for instance, jQuery. The library itself is a module. They are revealed into the global scope using a modified revealing module pattern called "exports/expose pattern". Creation of instances of the jQuery object uses new, hidden behind the jQuery function.

(function(window,undefined){

  jQuery = function( selector, context ) {
    //creating a new instance here
    return new jQuery.fn.init( selector, context, rootjQuery );
  }

  //...tons of library code here...

  //Expose, assign to window, basically creating the globals
  window.jQuery = window.$ = jQuery;

}(window));

When using jQuery as an object, it hosts exposed functions. This is when the module pattern is good at - singe direct fast global access.

$.ajax
$.noConflict
$.each

But when you use jQuery to wrap elements, wrap objects etc., it creates an instance of the constructor. This is where the constructor pattern is good at - creating multiple objects of the same kind.

//methods on these selectors are basically the same function, shared
// where in this case, each is shared
$('html').each(...
$('body').each(...
$('head').each(...

$('head').each === $('body').each //true


Multiple numbers calculator This is my first ever Python program so I would really like to know if it's any good (I mean if it is well writen), and if not then how to make it better.
I would also like to know if there is a way to get all the veriables in one line without a space between them.

This calculator is basicly this calculator which I wrote in C++ upgraded and writen in Python.

def calculate(num1, num2, act):
    if(act=='+'):
        total=num1+num2
    elif(act=='-'):
        total=num1-num2
    elif(act=='*'):
        total=num1*num2
    elif(act=='/'):
        total=num1/num2
    else:
        print("input not recognized")
    return total

def calc2():
    user_input=input("Enter a num1 act num2 (with a space between them): ")   #Gets the values
    var1, action, var2=user_input.split()     #assigns the values into the variables
    if(action=='/' and var2==0):      #checks for division by 0
        print("YOU CAN'T DIVIDE BY ZERO!!!")
    else:
        print(calculate(float(var1), float(var2), action))     #calls the 'calculating' function, recives and prints the total of act

def calc3():
    user_input=input("Enter a num1 act1 num2 act2 num3 (with a space between them): ")      #Gets the values
    var1, action1, var2, action2, var3=user_input.split()           #assigns the values into the variables
    if(action1=='/' and var2==0 or action2=='/' and var3==0):      #checks for division by 0
        print("YOU CAN'T DIVIDE BY ZERO!!!")
    elif((action2=='*' or action2=='/') and (action1=='+' or action2=='-')):    #checks if act2 should be done before act1 (order of operation)
        total=calculate(float(var2), float(var3), action2)     #calls the 'calculating' function, recives the total of act2
        print(calculate(float(var1), float(total), action1))     #calls the 'calculating' function, assigns the total of act2 as num2, recives and prints the total of act1
    else:                                                             #act1 is done before act2 (order of operation)
        total=calculate(float(var1), float(var2), action1)         #calls the 'calculating' function, recives the total of act1
        print(calculate(float(total), float(var3), action2))     #calls the 'calculating' function, assigns the total of act1 as num1, recives and prints the total of act2

def main():
    amount=float(input("How many numbers? (2-3 numbers) "))
    if(amount==2):
        calc2()
    elif(amount==3):
        calc3()
    else:
        print("I SAID TWO OR THREE NUMBERS")

main()           #starts program

Input/Output

  Input:2 + 3 * 4
  Output:14

There are some places where you can dictionaries instead of if/elif/else statements, I will analyze one here:

if(act=='+'):
    total=num1+num2
elif(act=='-'):
    total=num1-num2
elif(act=='*'):
    total=num1*num2
elif(act=='/'):
    total=num1/num2
else:
    print("input not recognized")

Is often re-written as a dictionary. So, you could create a dictionary called OPS and write:

import operator

OPS = {
    '+' : operator.add,
    '-' : operator.sub,
    ...
}
ERROR = lambda arg1, arg2: print("input not recognized")

You can then you can do:

def calculate(num1, num2, act):
    return OPS.get(act, ERROR)(num1, num2)

This tries getting the particular key which is a function. It then calls it. If the operator is not found, it defaults to the ERROR.


Switch case reviews, finding days of the week that coresponds to a number given Given a number between 1 and 7, this will display which day of the week corresponds to that number, starting with Monday. This is pretty simple and pretty easy, but it seems that there would be a much better way to do this, where I wouldn't have to write out each day of the week, and possibly iterate through an array..?

using System;

namespace FindDay
{
    class Program
    {
        static void Main(string[] args)
        {
            //This program will provide you the day of the week
            //through a given number that coresponds to that day
            //of the week, IE: Monday => 1st day of the week

            int num;
            string result;

            label:

            Console.Write("Enter a number between 1 and 7: ");
            num = Convert.ToInt32(Console.ReadLine());

            switch (num)
            {
                case 1:
                    result = "Monday";
                    Console.WriteLine("{0} => {1}st day of the week", result, num);
                    break;
                case 2:
                    result = "Tuesday";
                    Console.WriteLine("{0} => {1}nd day of the week", result, num);
                    break;
                case 3:
                    result = "Wednesday";
                    Console.WriteLine("{0} => {1}rd day of the week", result, num);
                    break;
                case 4:
                    result = "Thursday";
                    Console.WriteLine("{0} => {1}th day of the week", result, num);
                    break;
                case 5:
                    result = "Friday";
                    Console.WriteLine("{0} => {1}th day of the week", result, num);
                    break;
                case 6:
                    result = "Saturday";
                    Console.WriteLine("{0} => {1}th day of the week", result, num);
                    break;
                case 7:
                    result = "Sunday";
                    Console.WriteLine("{0} => {1}th day of the week", result, num);
                    break;
                default:
                    Console.WriteLine("That's not a day..");
                    goto label;

            }

        }
    }
}

Would it be better to iterate through an array within this instead of writing out each day separately, how can I improve this little program?

I would add to forsvarir's good answer: start thinking now about the power of abstraction.  Programming is all about building abstractions.  Make your abstractions solve one problem and solve it well.  For instance, here's a problem to solve:

static string Ordinal(int n)
{
    // You fill this in. The method takes an integer and returns
    // 1st, 2nd, 3rd, 4th, etc.
}

Heres another one:

static string WeekdayName(int w)
{
  // To do: Return the name of the day of the week.
}

And here's another:

static int GetIntegerFromConsole(int low, int high)
{
    // to do: prompt the user, sit in a loop until they give
    // a response in the right range, and return it.
}

Once you have those methods then your program becomes trivial.

int weekdayNumber = GetIntegerFromConsole(1, 7);
string weekdayName = WeekdayName(weekdayNumber);
string ordinal = Ordinal(weekdayNumber);
Console.WriteLine($"{weekdayName} => {ordinal} day of the week");

You know what I like? Four-line-long programs, that's what I like. Move the mechanisms to their own helper methods, debug those methods, and then rely on them to do their jobs.


A Brushfire algorithm to generate a distance map in a grid I'm working on implementing a goal-based pathfinding.
first step is to set a goal and calculate the shortest walkable distance between the goal and all points in the grid, using a brushfire algorithm.

I'm worried about two things here, readability and efficiency, since this is for an RTS game.

    int[] GenerateHeatMap(IGrid grid, GridPoint goal)
    {
        var heatMap = new int[grid.Cells.Length];
        var unexploredPoints = new List<GridPoint>();
        var openPoints = new List<GridPoint>();
        for (int i = 0; i < grid.Width; i++)
        {
            for (int j = 0; j < grid.Height; j++)
            {
                unexploredPoints.Add(new GridPoint(i, j));
            }
        }

        var currentDistance = 0;
        heatMap[grid.IndexOf(goal)] = currentDistance;
        openPoints.Add(goal);
        unexploredPoints.Remove(goal);
        while (openPoints.Count > 0)
        {
            currentDistance++;
            var newOpenPoints = new List<GridPoint>();
            foreach (var currentPoint in openPoints)
            {
                for (int i = -1; i < 2; i++)
                {
                    for (int j = -1; j < 2; j++)
                    {
                        var point = new GridPoint(currentPoint.x + i, currentPoint.y + j);
                        if ((i == 0 && j == 0) || !unexploredPoints.Contains(point) || newOpenPoints.Contains(point) || !grid.PointToCell(point).CanCross) continue;
                        heatMap[grid.IndexOf(point)] = currentDistance;
                        newOpenPoints.Add(point);
                        unexploredPoints.Remove(point);
                    }
                }
            }
            openPoints.Clear();
            openPoints.AddRange(newOpenPoints);
        }
        return heatMap;
    }

For clarity here the definition of GridPoint

public struct GridPoint
{
    public GridPoint(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    public readonly int x;
    public readonly int y;
}

What can I do to improve this?

I would suggest to implement a HeatMapGridPoints class and inside this class, create two separate methods for GetUnexploredPoints and GetOpenPoints which will return list of GridPoint. This way, you can expand and also reuse the HeatMap. Also, it would be more readable than just gathering them into one method.

Example :

public class HeatMapGridPoints
{

    public IList<GridPoint> GetUnexploredPoints(IGrid grid)
    {
        var points = new List<GridPoint>();

        for (int i = 0; i < grid.Width; i++)
        {
            for (int j = 0; j < grid.Height; j++)
            {
                points.Add(new GridPoint(i, j));
            }
        }

        return points;

    }

    public IList<GridPoint> GetOpenPoints(IGrid grid, GridPoint goal)
    {
        // rest of the code
    }

}

you can also do something like this :

public class HeatMapGridPoints
{
    private readonly IGrid _grid;

    private readonly GridPoint _gridPoint;

    public IList<GridPoint> OpenPoints { get; private set; }

    public IList<GridPoint> UnexploredPoints { get; private set; }

    public HeatMap(IGrid grid, GridPoint goal)
    {
        _grid = grid;

        _gridPoint = goal;

        OpenPoints = GetOpenPoints();

        UnexploredPoints = GetUnexploredPoints();
    }

    private IList<GridPoint> GetUnexploredPoints()
    {
        ...
    }

    private IList<GridPoint> GetOpenPoints()
    {
        ...
    }

}

usage :

var heatMap = new HeatMapGridPoints(grid, goal);

foreach(var point in heatMap.OpenPoints)
{
    ....
}

this would make it much easier to maintain and also more readable.