Extracting file names from text file I need to extract file names with their extension from an input text file to a string vector.
The input text file is quite messy and serves as configuration file for some application.

What I know about the file names I am trying to extract is they are preceded by a file = mention, the filename is quoted between ' ' or " ".

Example : file="name.abc". I also have no guarantee of how spacing is : It may be file="name.abc", file = "name.abc" , file= "name.abc"... And extension can be of different lengths.

So I tried the following code:

std::vector<std::string> attachment_names;
std::istringstream words(text_content);
std::string word;
std::string abc_extension(".abc"); // My code should support any extension
while (words >> word)
{
    auto extension_found = word.find(abc_extension);
    if (extension_found != word.npos)
    {
        auto name_start = word.find("'") + 1;
             //I am not even sure the file is quoted by ''

        std::string attachment_name = word.substr(name_start, (extension_found + 3) - name_start + 1);
             //Doing this annoys me a bit... Especially that the extension may be longer than 3 characters

        attachment_names.push_back(attachment_name);
    }
}

Is there a nicer way of doing this? Is there a possibility to rely more on the file caption to support any extension?

Here are a number of things that may help you improve your code.

Use the required #includes

The code uses std::vector which means that it should #include <vector>.  It was not difficult to infer, but it helps reviewers if the code is complete.  This code appears to require the following:

#include <vector>
#include <sstream>
#include <string>
#include <iostream>

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people.  Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code.  This affects not only code reviews, but also maintenance of the code in the future, by you or by others.  One good way to address that is by the use of comments.  Another good technique is to include test code showing how your code is intended to be used and the expected results.  The code, as posted, is just a program fragment, so I turned it into a function for testing:

std::vector<std::string> fetch_names(const std::string &text_content, const std::string &ext) {
    std::vector<std::string> attachment_names;
    std::istringstream words(text_content);
    std::string word;
    while (words >> word) {
        auto extension_found = word.find(ext);
        if (extension_found != word.npos) {
            auto name_start = word.find("'") + 1;
            std::string attachment_name = word.substr(name_start, (extension_found + 3) - name_start + 1);
            attachment_names.push_back(attachment_name);
        }
    }
    return attachment_names;
}

Fix the bugs

As posted, the extension was named pst_extension but was used as abc_extension so it wouldn't compile without some alteration.  More serious, however, is that the matching appears to be flawed.  It purports to look for a filename surrounded by single quotes but that's not what it actually does.  I wrote a small test program:

int main(int argc, char *argv[]) {
    if (argc != 2) {
        std::cout << "Usage: getfile filename\n";
        return 0;
    }
    std::ifstream in{argv[1]};
    for (std::string fn; std::getline(in, fn); ) {
        auto names = fetch_names(fn, ".abc");
        unsigned i=0;
        for (const auto &file : names) {
            std::cout << ++i << "\t[" << file << "]\n";
        }
    }
}

I then used it with this file:

file = "one.abc"
file='two.abc"
file   == three.abcd
file=four.ab
file='five.abcd'  file2='six.abcd'
file='seven.abc' file='eight.abc'

I would expect the output to be this:

1   [seven.abc]
2   [eight.abc]

But what it actually reported was this:

1   ["one.abc]
1   [two.abc]
1   [three.abc]
1   [five.abc]
2   [six.abc]
1   [seven.abc]
2   [eight.abc]

Consider regular expressions

First, it appears that the "file=" portion of the line is ignored.  The code actually acts on any matchine string within single quotes.  Assuming that's intentional, we can use regular expressions very easily for this:

#include <regex>
#include <iterator>

std::vector<std::string> fetch_names(const std::string &text_content,
            const std::string &ext) {
    std::vector<std::string> file;
    std::regex file_regex{"'(\\S+"+ext+")'"};
    auto begin = std::sregex_iterator{text_content.begin(),
              text_content.end(), file_regex};
    auto end = std::sregex_iterator{};
    for (auto it = begin; it != end; ++it) {
        file.push_back((*it)[1]);
    }
    return file;
}

This works with a fairly simple regular expression that looks for opening and closing single quote characters and assumes the filename is made of non-whitespace characters only.  If that's not the case for your program (e.g. if you wish to accept spaces within the file name), then you can adjust the regex accordingly.  For example, if you wish to allow either single or double quotes (but they must match) and the filename can include alphanumeric plus spaces and underscores, we can use this:

std::regex file_regex{"('|\")([ _[:alnum:]]+"+ext+")\\1"};

In this case, the actual filename portion is in the second grouping, so we would account for that by changing the loop:

for (auto it = begin; it != end; ++it) {
    file.push_back((*it)[2]);
}

If you want the code to explicitly look for the "file = " portion of the line as well, it's as simple as changing the regex to this:

std::regex file_regex{"file\\s*=\\s*('|\")([ _[:alnum:]]+"+ext+")\\1"};

Note that using a regex is often slower than alternatives, such as writing your own state machine, but is often fast enough and is extremely flexible.  Note for example, that we actually construct the regex at runtime from a passed parameter.  This is both very flexible and potentially dangerous, so any user input should be sanitized before use.


Sudoku Grid special purpose Iterators Please have a look at these iterators which I use for my Sudoku solver. They behave slightly different from STL iterators and don't implement all functionality that would be needed to use them in a stl context. But the basic idea behind them was to clean up the code in the Sudoku program that makes heavy use of the three access patterns (row, col, block) that I implemented.

The most "important" iterator is the BlockIterator, since without that iterating over all nine fields in a block looked quite ugly. Iterating rows and columns wasn't that bad, but since I started writing the stuff I decided to create a complete set.

Some technical details:

The grid class holds an (evil) array of pointers to Field objects, that's one dimensional (I could have used a two dimensional array as well, but I often do it this way and feel quite comfortable with modulo operations). Maybe I will replace this with a vector later.

The grid class adds a few static functions to calculate offsets in the array based on row, col or block positions.

class Grid {
public:
    Grid();
    Grid(std::string s);

    class Iterator {
    public:
        Iterator(Grid* g) : grid(g), it(0){}
        Field* operator*(){return field;}
        void operator++(){
            ++it;
            if(it < 9) field = calc_field();
            else field = NULL;
        }
    protected:
        virtual Field* calc_field() = 0;
        Field* field;
        Grid* grid;
        int it;
    };

    class RowIterator : public Iterator {
    public:
        RowIterator(Grid* g, int row) : Iterator(g){
            row_offset = row * size; //Grid::block_offset(block);
            field = calc_field();
        }
        Field* calc_field(){
            int field_index = row_offset + it;
            return grid->field[field_index];
        }
    protected:
        int row_offset;
    };

    class ColIterator : public Iterator {
    public:
        ColIterator(Grid* g, int col) : Iterator(g){
            col_offset = col;
            field = calc_field();
        }
        Field* calc_field(){
            int field_index = it * size + col_offset;
            return grid->field[field_index];
        }
    protected:
        int col_offset;
    };

    class BlockIterator : public Iterator {
    public:
        BlockIterator(Grid* g, int block) : Iterator(g){
            block_offset = Grid::block_offset(block);
            field = calc_field();
        }
        Field* calc_field(){
            int field_index = block_offset + ((it / 3) * size) + (it % 3);
            return grid->field[field_index];
        }
    protected:
        int block_offset;
    };

    RowIterator& row_iter(int row){return *(new RowIterator(this, row));}
    ColIterator& col_iter(int col){return *(new ColIterator(this, col));}
    BlockIterator& block_iter(int block){return *(new BlockIterator(this, block));}

(...)

    static int block_offset(int block){return ((block / 3) * size * 3) + ((block % 3) * 3);}

protected:
        Field* field[grid_size];

Sample usage:

This function is called, when I set a value in a field. It goes through all fields, that would possibly be influenced by this field (same row, col or block)

void Field::do_exclusions(){
    // row
    for(Grid::RowIterator it = grid->row_iter(row); *it; ++it)
        (*it)->set_excluded(value);
    // col
    for(Grid::ColIterator it = grid->col_iter(col); *it; ++it)
        (*it)->set_excluded(value);
    // block
    for(Grid::BlockIterator it = grid->block_iter(block); *it; ++it)
        (*it)->set_excluded(value);
}

So please tell me, if something like this would be "acceptable" (not to mention "best practices"), even if it somehow takes a very free view on the iterator concept.

And of course every idea how this could be improved is welcome.

PS: I tried to add a tag "iterator" but I'm not allowed for too few reputation.

In my first quick scan through, here are some things I want to bring up:

If you are going to overload operators, do it the way the users of the language expect, or don't do it at all.  I expect operator++ to return something, not be a void.
Does block_offset really need to be public?
On that same note, do your actual concrete implementations of the iterators need to be public, since you have methods to create them that are public?  Would it make sense for anyone to ever want to create them a different way?


Python script to delete sections of text I've been writing a python script to help me clear up some files that contain outdated code, while also serving as a way to learn python. These files have sections of code surrounded with tags on their own lines, I need it to remove both the tags and everything within. While this largely applies to XML documents I am also using this script for several other file types, so XML specific solutions aren't suitable.

I have a working script already but it doesn't look like the most elegant or efficient solution by far, so I would like to see how I can improve it.

Script is called as python cleanup.py startDeleteTag stopDeleteTag where the last two arguments are the locations where the code should be deleted and stop being deleted respectfully.

import os, sys

def clearFile(path, beginDelete, stopDelete):

  path = os.path.join(path, "fileName.xml")
  input = open(path, "r")
  lines = input.readlines()
  input.close()

  currentFlag = False
  nextFlag = False

  output = open(path, "w")

  for line in lines:
    if nextFlag == True:
      nextFlag = False
      deleteFlag = False

    if beginDelete in line:
      deleteFlag = True
    elif stopDelete in line:
      nextFlag = True

    if deleteFlag == False:
      output.write(line)

thisDirectory = os.getcwd()
for start, dirs, files in os.walk(thisDirectory):
  for f in files:
    if f == "fileName.xml":
      clearFile(thisDirectory, sys.argv[1], sys.argv[2])

This is the part of the script that checks each line for the start of the section to be deleted (beginDelete to stopDelete). Because this would leave the end tag in the file I have to use a couple of booleans to specify when the current line needs to be removed but the next line shouldn't be. As an extra, is there a way to improve this to further check for tags that may be on the same line as body of the code? This isn't currently an issue but I'm curious how I would do it if I needed to in future.

As requested, and example file input would look like this:

<good>
  keep this
</good>

<bad>
  delete this
</bad>

<good>
  keep this
  <bad>
    delete this
  </bad>
</good>

And this would produce the output:

<good>
  keep this
</good>

<good>
  keep this

</good>

Program flow

You have a lot of booleans being thrown around and you could clear out a lot. if nextFlag == True is the same as if nextFlag, and the latter looks neater so stick with it.

For the main flow, you have it in a bit of a mess. You should have only one flag, which denotes lines should be deleted or skipped. Your two flags are entirely confusing the process. Think about it this way, you need a flag to indicate that a part should be skipped. You don't need two values indicating the same thing. So how does that work?

Well obviously you start with looking for beginDelete. We need to first check if deleteFlag is True or False. If it's True we want it to remain as it is until stopDelete is found and skip. So if deleteFlag isn't True, then we set it to be the result of beginDelete in line. You can assign expressions to variables, even if it's a boolean expression. So on this basis we don't need another if check, we can just set deleteFlag to equal this result directly. Obviously this means the flag is now True if we've found beginDelete but False otherwise.

for line in lines:
    if not deleteFlag:
        deleteFlag = beginDelete in line

Now, we also need to find stopDelete to turn the flag False when it's found. This only needs to run if deleteFlag is True, so it should be an else condition:

for line in lines:
    if not deleteFlag:
        deleteFlag = beginDelete in line
    else:
        deleteFlag = stopDelete not in line
        continue

Now you can see that deleteFlag is being set based on whether or not stopDelete has been found yet. We're using not so that deleteFlag remains True until stopDelete is found. Once that happens, deleteFlag is once again False. However, since you don't want to write the line where you've just found stopDelete then you should use continue to skip to the next iteration of the line. continue is a keyword that tells a loop to immediately go to the next iteration, ignoring any remaining code in the loop's block.

Now, writing to the file is easy. You just want to write if not deleteFlag, ie. if the flag isn't True.

    if not deleteFlag:
        output.write(line)

Style Notes

Stick to 4 space indentation. It's the Python standard and far more readable for people. Speaking of standards, Python naming uses snake_case, so beginDelete should be begin_delete etc.

Your names could be better too. You're not really deleting anything. You're 'skipping' or 'ignoring'. You don't really need to include flag in the name, using ignore would be pretty clear. Also avoid using input as that shadows the builtin Python method of the same name. Instead input_file or in_file. With such a brief usage, you can also use f.

Speaking of files, you should use with when opening files. It's a context manager that makes file manipulation safer. When using open you can easily run into trouble if you don't close the file. Sometimes that can happen due to errors, or if you forget to. Which it looks like you actually did with output. Using with means that a file is always automatically closed, even in the case of errors or exceptions, so it's a more reliable method. This is how you'd use it for lines.

with open(path, "r") as f:
    f.readlines()

The indentation signals how long to leave the file open, and then it's closed once you move out of that block. You should do the same for output, also open defaults to opening in "r" mode so you don't need to specify the argument there.

Also in your final os.walk loop you assign start and dirs but don't seem to use them. If you don't need those values, consider using the names _ and __. That's a Python way of saying that variables are unused throwaways, so people reading your code know they don't matter.


UnitTest strong exception guarantee I want to properly test the strong exception guarantee of a method.

The method in question is SetFiles. It does not have side-effects (it only modifies the object it is called upon). It is expected to change some object fields and to modify the elements of FileList field - a collection. In case the argument is invalid then it throws ArgumentException and it is expected to not modify the object.

This is what I have:

[TestClass]
public class UnitTest_Files
{
    [TestMethod]
    public void TestFiles1()
    {
        var fs = new Files();

        // 1st call to SetFiles. valid

        fs.SetFiles(new string[]
            {
                @"C:\work\file1.txt",
                @"C:\work\file2.avi",
                @"C:\work\file3",
            });
        Assert.AreEqual(@"C:\work", fs.ParentFolder);
        Assert.AreEqual(3, fs.FileList.Count);

        Assert.AreEqual(@"C:\work\file1.txt", fs.FileList[0].Path);
        Assert.AreEqual(@"C:\work\file2.avi", fs.FileList[1].Path);
        Assert.AreEqual(@"C:\work\file3", fs.FileList[2].Path);

        // 2nd call to SetFiles. valid

        fs.SetFiles(new string[]
            {
                @"C:\muzică\Diabulus in Musica\poze\membri\Zuberoa Aznárez.jpg",
                @"C:\muzică\Diabulus in Musica\poze\membri\Gorka Elso.jpg",
            });

        Assert.AreEqual(@"C:\muzică\Diabulus in Musica\poze\membri", fs.ParentFolder);
        Assert.AreEqual(2, fs.FileList.Count);

        Assert.AreEqual(@"C:\muzică\Diabulus in Musica\poze\membri\Zuberoa Aznárez.jpg", fs.FileList[0].Path);
        Assert.AreEqual(@"C:\muzică\Diabulus in Musica\poze\membri\Gorka Elso.jpg", fs.FileList[1].Path);

        // 3rd call to SetFiles. Invalid

        // set to invalid structure (files not in same folder)
        // and expect throw
        // and no change
        try
        {
            fs.SetFiles(new string[]
                {
                    @"C:\muzică\folder1\file2.txt",
                    @"C:\muzică\folder2\file2.txt"
                });

            Assert.Fail("expected exception");
        }
        catch
        {
        }

        // test that fs was not modified

        Assert.AreEqual(@"C:\muzică\Diabulus in Musica\poze\membri", fs.ParentFolder);
        Assert.AreEqual(2, fs.FileList.Count);

        Assert.AreEqual(@"C:\muzică\Diabulus in Musica\poze\membri\Zuberoa Aznárez.jpg", fs.FileList[0].Path);
        Assert.AreEqual(@"C:\muzică\Diabulus in Musica\poze\membri\Gorka Elso.jpg", fs.FileList[1].Path);
    }
}

This is my first dive into C# unit testing and the code I wrote seems very cumbersome. I particularly don't like the copy-pasted last tests. The object is not clonable/copyable and I don't have any other reason to implement that. So I don't know how other way to test that object after is the same as before. Also the entire test doesn't seem very scalable.

Do not attempt to put all the test criteria in one test.
Make seperate (small) tests, which each cover one specific scenario.

If all tests pass, you know it is ok.
But make sure the tests do not depend on each other: that they can run in any order.

For the exception assert, it is better to use an Attribute on the test method:

Update:

As Roland Illig mentioned, it is good to check that nothing was modified.

Updated code fragment:

[TestMethod]
[ExpectedException(typeof(ArgumentException))]
public void SetFiles_FilesNotInTheSameFolder_ExpectedException()
{
    // 3rd call to SetFiles. Invalid

    // set to invalid structure (files not in same folder)
    // and expect throw
    // and no change

    var validParentFolder = @"c:\C:\muzică\folder1";
    var validFile1 = @"c:\C:\muzică\folder1\file1.txt";

    var invalidFile1 = @"C:\muzică\folder1\file2.txt";
    var invalidFile2 = @"C:\muzică\folder2\file2.txt";

    var fs = new Files();
    fs.SetFiles(new string[]
    {
        validFile1
    });

    fs.SetFiles(new string[]
        {
            invalidFile1,
            invalidFile2
        });

    // test that fs was not modified

    Assert.AreEqual(1, fs.FileList.Count);
    Assert.AreEqual(validParentFolder, fs.ParentFolder);

    Assert.AreEqual(validFile1, fs.FileList[0].Path);
}

Last remark, if this is working with real files, try to use stubs or mocks.

Update:

Below is compete test file, with the separated tests

[TestClass]
public class UnitTest_Files
{
    private string expectedFile1;

    [TestMethod]
    public void SetFiles_Valid()
    {
        var fs = new Files();

        // 1st call to SetFiles. valid

        var expectedParentFolder = @"C:\work";
        var expectedFile1 = $@"{expectedParentFolder}\file1.txt";
        var expectedFile2 = $@"{expectedParentFolder}\file2.avi";
        var expectedFile3 = $@"{expectedParentFolder}\file3";

        fs.SetFiles(new string[]
            {
                expectedFile1,
                expectedFile2,
                expectedFile3
            });

        Assert.AreEqual(3, fs.FileList.Count);
        Assert.AreEqual(@"C:\work", fs.ParentFolder);
        Assert.AreEqual(expectedFile1, fs.FileList[0].Path);
        Assert.AreEqual(expectedFile2, fs.FileList[1].Path);
        Assert.AreEqual(expectedFile3, fs.FileList[2].Path);
    }

    [TestMethod]
    public void SetFiles_Specialchars_Valid()
    {
        // 2nd call to SetFiles. valid
        var expectedParentFolder = @"C:\muzică\Diabulus in Musica\poze\membri";
        var expectedfile1 = $@"{expectedParentFolder}\Zuberoa Aznárez.jpg";
        var expectedfile2 = $@"{expectedParentFolder}\Gorka Elso.jpg";

        var fs = new Files();
        fs.SetFiles(new string[]
            {
                expectedfile1,
                expectedfile2
            });

        Assert.AreEqual(expectedParentFolder, fs.ParentFolder);
        Assert.AreEqual(2, fs.FileList.Count);

        Assert.AreEqual(expectedFile1, fs.FileList[0].Path);
        Assert.AreEqual(expectedFile2, fs.FileList[1].Path);
    }

    [TestMethod]
    [ExpectedException(typeof(ArgumentException))]
    public void SetFiles_FilesNotInTheSameFolder_ExpectedException()
    {
        // 3rd call to SetFiles. Invalid

        // set to invalid structure (files not in same folder)
        // and expect throw
        // and no change

        var validParentFolder = @"c:\C:\muzică\folder1";
        var validFile1 = @"c:\C:\muzică\folder1\file1.txt";

        var invalidFile1 = @"C:\muzică\folder1\file2.txt";
        var invalidFile2 = @"C:\muzică\folder2\file2.txt";

        var fs = new Files();
        fs.SetFiles(new string[]
        {
            validFile1
        });

        fs.SetFiles(new string[]
            {
                invalidFile1,
                invalidFile2
            });

        // test that fs was not modified

        Assert.AreEqual(1, fs.FileList.Count);
        Assert.AreEqual(validParentFolder, fs.ParentFolder);

        Assert.AreEqual(validFile1, fs.FileList[0].Path);
    }
}


Thread-safe lock-free counter I was using such code:

class Counter
{
    private int i = 0;

    public int Next()
    {
        lock (this)
        {
            return i++;
        }
    }

    public void Reset()
    {
        lock (this)
        {
            i = 0;
        }
    }

}

I refactored it such a way:

class Counter
{
    private int i = 0;

    public int Next()
    {
        return Interlocked.Increment(ref i);
    }

    public void Reset()
    {
        i = 0;
    }

}

Will that work?

I'm using .NET 4.5 if this matters.

It should also be fine in earlier versions of .NET as you are not using any 4.5 specific classes or language features.

The reset is fine as the assignment is atomic as you mentioned, however if you were using a long then you would want to use Interlocked.Exchange because the assignment of a 64bit number is not atomic on a 32bit operating system (as it is stored as 2 32bit values).

The only changes I would suggest are purely from a coding standards perspective:

// seal the class as it's not designed to be inherited from.
public sealed class Counter
{
    // use a meaningful name, 'i' by convention should only be used in a for loop.
    private int current = 0;

    // update the method name to imply that it returns something.
    public int NextValue()
    {
        // prefix fields with 'this'
        return Interlocked.Increment(ref this.current);
    }

    public void Reset()
    {
        this.current = 0;
    }
}


Check if two strings are one 'edit' apart using Python The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview.  I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding style.  I think the time and space complexity of the code below is \$O(n^{2})\$ and \$O(n)\$ respectively.

The exercise statement is as follows:

  Given 2 Strings write a function to check if they are 1 edit away.  There are three type of edits

  1) Insert a character

  2) Remove a character

  3) Replace a character

I wrote the code in Python 3.5 and confirmed that it passed a small unit test.  For this problem I am particularly interested in feedback on where in my code (if at all) I should include more comments.

import unittest

def is_one_away(first: str, other: str) -> bool:
    """Given two strings, check if they are one edit away. An edit can be any one of the following.
    1) Inserting a character
    2) Removing a character
    3) Replacing a character"""
    if len(first) < len(other):
        first, other = other, first

    if len(first) - len(other) > 1:
        return False

    elif len(first) - len(other) == 1:
        for pos in range(len(first)):
            if first[:pos] + first[pos+1:] == other:
                return True
        return False

    else:
        num_different_chars = sum(1 for pos in range(len(first)) if first[pos] != other[pos])
        return num_different_chars < 2

class MyTest(unittest.TestCase):
    def test_is_one_away(self):
        self.assertEqual(is_one_away('pale', 'ale'), True)
        self.assertEqual(is_one_away('pales', 'pale'), True)
        self.assertEqual(is_one_away('pale', 'bale'), True)
        self.assertEqual(is_one_away('pale', 'bake'), False)
        self.assertEqual(is_one_away('ale', 'pale'), True)
        self.assertEqual(is_one_away('aale', 'ale'), True)
        self.assertEqual(is_one_away('aael', 'ale'), False)
        self.assertEqual(is_one_away('motherinlaw', 'womanhitler'), False)
        self.assertEqual(is_one_away('motherinlaw','motherinlow'), True)

All three cases are the same: you iterate over both string until there is a difference, you skip that difference and you check that the remaining of the strings are the same.

The only difference being how you skip the difference: you can store that in a dictionnary to also help short circuit in cases the length difference is 2 or more:

def is_one_away(first: str, other: str) -> bool:
    """Given two strings, check if they are one edit away. An edit can be any one of the following.
    1) Inserting a character
    2) Removing a character
    3) Replacing a character"""

    skip_difference = {
        -1: lambda i: (i, i+1),  # Delete
        1: lambda i: (i+1, i),  # Add
        0: lambda i: (i+1, i+1),  # Modify
    }
    try:
        skip = skip_difference[len(first) - len(other)]
    except KeyError:
        return False  # More than 2 letters of difference

    for i, (l1, l2) in enumerate(zip(first, other)):
        if l1 != l2:
            i -= 1  # Go back to the previous couple of identical letters
            break

    # At this point, either there was no differences and we exhausted one word
    # and `i` indicates the last common letter or we found a difference and
    # got back to the last common letter. Skip that common letter and handle
    # the difference properly.
    remain_first, remain_other = skip(i + 1)
    return first[remain_first:] == other[remain_other:]


Queue with O(1) enqueue and dequeue with JS arrays If you simply implement it with .push() to .enqueue() and .shift() to .dequeue() that's easy but the the time complexity of .enqueue() is O(1) and .dequeue() is O(n).
While still using arrays, I have come come up with a nice solution to make both .enqueue() and .dequeue() in O(1). I am using sparse arrays. It turns out to be super efficient but only when the Queue size is larger than 25000. My benchmarks are like this;
Queue size 100
Queue: 0.12999999523162842
Array: 0.03999999910593033

Queue size 1000
Queue: 1.1049999967217445
Array: 0.5250000059604645

Queue size 10000
Queue: 3.0750000029802322
Array: 1.7799999937415123

Queue size 100000
Queue: 13.944999992847443
Array: 887.390000000596

OK Queue becomes much faster than Array as the size grows but i can not tell what to improve so that Queue doesn't fall behind Array at smaller scales. Is there anything that you can suggest in the below code?

class Queue extends Array {
  constructor(){
    super();
    Object.defineProperty(this,"head",{ value   : 0
                                      , writable: true
                                      });
  }
  enqueue(x) {
    this.push(x);
    return this;
  }
  dequeue() {
    var first;
    return this.head < this.length ? ( first = this[this.head]
                                     , delete this[this.head++]
                                     , first
                                     )
                                   : void 0;
  }
  peek() {
    return this[this.head];
  }
}

var p = Array(100000).fill().map(_ => ~~(Math.random()*1000)),
    q = p.reduce((r,e) => r.enqueue(e), new Queue());

var s,e;

s = performance.now();
for (i=0; i < 100000; i++){
  q.dequeue();
}
e = performance.now();
console.log("Queue:", e-s);

s = performance.now();
for (i=0; i < 100000; i++){
  p.shift();
}
e = performance.now();
console.log("Array:", e-s);

Edit:
After some research, now i understand that what many of us have been told is in fact not correct. .shift() is not O(n). It's been optimized to O(1) many years ago and i think last ones to optimize were the Firefox guys in 2017. Here the guys are discussing how to implement the optimization and it turns they do a very similar thing to what i implemented here. Unlike me, they just skip the "delete out the dequeued item" part since they write it in C++ and can move the pointer (head in above code) by leaving out freed spaces to GC. But in JS we have to delete them either in each .dequeue() operation or wait for (this.length - this.head) > 50000 and make a .splice(0,this.head)  in order to prevent memory leak. This is inline with what i see with Chrome and new Edge (Chromium). Up until 50000 items .shift() works O(1) but then they switch to non optimized code. In Firefox this seems to be not the case as mentioned in a developer's comment.
Verdict:
You may safely and simply implement efficient Queues with .push() and .shift().

Review
I find your indentations and line breaks rather difficult to read.

Object.defineProperty(this,"head",{ value   : 0
                                  , writable: true
                                  });

I would suggest you use the idiomatic style.
After { move to the next line and indent once. Place the comma at the end of lines and spaces after commas if not at end of line
Object.defineProperty(this, "head", {
    value: 0,
    writable: true
});

or if the line is short
Object.defineProperty(this, "head", {value: 0, writable: true});

or
Object.defineProperty(
    this,
    "head", {
        value: 0,
        writable: true
    }
);

Same again with the ternary.

return this.head < this.length ? ( first = this[this.head]
                                 , delete this[this.head++]
                                 , first
                                 )
                               : void 0;

Why use the operator void that requires the additional expression 0 when you can just express undefined.
I understand the reasoning for breaking up the group, but the indent is way to great. The idiomatic style is far more readable.
return this.head < this.length ? (
        first = this[this.head],
        delete this[this.head++],
        first
    ) :
    undefined;

or
return this.head < this.length ?
    (first = this[this.head], delete this[this.head++], first) :
    undefined;

Unsafe encapsulation
Extending the Array with the behaviors enqueue and dequeue is just asking for bugs as any of the existing functions can damage state.
Rules of code: "If it is there it will be used."
Good code enforces the rules by not exposing properties and behaviors that can damage state.
Even just the basic use of Queue is un-trusted because you expose head.
JS Queue
Complexity and performance are two side of the same coin. Though linked they are vastly difference. With shift at \$O(1)\$ its performance is still 10 times slower than pop
However you use delete to remove items. Again it is \$O(1)\$ but it is even slower than shift.
Linked list
I have found that a simple linked list is the most effective and performant solution for a queue in JS
Implementing it as a factory function allows closure to hold its state safely isolated from the code using the queue.
function Queue() {
    var head, tail;
    return Object.freeze({
        enqueue(value) {
            const link = {value, next: undefined};
            tail = head ? tail.next = link : head = link;
        },
        dequeue() {
            if (head) {
                const value = head.value;
                head = head.next;
                return value;
            }
        },
        peek() { return head?.value }
    });
}

This style offers robust encapsulation, maintains the ideal \$O(1)\$ for enqueue and dequeue without sacrificing performance.
Test
The test compares the execution time of your Queue against a linked list version of a queue.
There are two test cycles, First for 1000 items, then when done click the button for 500,000 items.
I Have made minor changes to your code to favor performance. Not using define property and not returning the array in enqueue.

var size = 1000;
const COOL = 200;

class Queue extends Array {
  constructor(){
    super();
    this.head = 0;
  }
  enqueue(x) { this.push(x) }
  dequeue() {
    var first;
    return this.head < this.length ?
        (first = this[this.head] , delete this[this.head++] , first) :
        void 0;
  }
  peek() { return this[this.head] }
}

function QueueLinked() {
    var head, tail;
    return Object.freeze({
        enqueue(value) {
            const link = {value, next: undefined};
            tail = head ? tail.next = link : head = link;
        },
        dequeue() {
            if (head) {
                const value = head.value;
                head = head.next;
                return value;
            }
        },
        peek() { return head?.value }
    });
}

function fillQueue(queue, count = size) {
    while (count--) { queue.enqueue(count) }
    return queue;
}
function testOPQueue() {
    const q = fillQueue(new Queue());
    var ii = 0, val = 0;
    do {
        ii += val;
        val = q.dequeue();
    } while (val !== undefined);
    return ii;
}
function testLinkedQueue() {
    const q = fillQueue(QueueLinked());
    var ii = 0, val = 0;
    do {
        ii += val;
        val = q.dequeue();
    } while (val !== undefined);
    return ii;
}

if (testOPQueue() !== testLinkedQueue()) { throw new Error("Test results differ") }

const funcTest = (name, call, bias = 1) => ({name, call, time: 0, cycles: 0, bias});

timeFunctions(50, 500, "1000 items:",
    funcTest("Array Queue", testOPQueue),
    funcTest("Linked Queue", testLinkedQueue),
).then(() => {
    test2.classList.remove("hide");
    test2.addEventListener("click", () => {
        test2.classList.add("hide");
        size = 500000;
        timeFunctions(50, 3, "500,000 items:",
            funcTest("Array Queue", testOPQueue),
            funcTest("Linked Queue", testLinkedQueue),
        );
    });
});

function timeFunctions(testCount, cycles, name, ...functions) {
    return new Promise(done => {
        const testGroup = () => {
            var i;
            for (const func of functions) {
                i = cycles;
                const now = performance.now();
                while (i--) { func.call() }
                func.time += performance.now() - now;
                func.cycles += cycles;
            }
        }
        const test = () => {
            testGroup();
            console.clear();
            console.log(name + " " + (testCount - count + 1) + " of " + testCount);
            for (const func of functions) {
                console.log(
                    func.name.padEnd(maxNameLen + 2,".") + ": " +
                    (((func.time / func.cycles) / func.bias).toFixed(3) + "ms").padStart(9," ") +
                    (" Total: " + func.time.toFixed(3) + "ms")
                );
            }
            if (--count) { setTimeout(test, COOL) }
            else { done() }
        }
        var count = testCount;
        var maxNameLen = 0
        for (const func of functions) {
            func.time = 0;
            func.cycles = 0;
            maxNameLen = Math.max(maxNameLen, func.name.length);
        }
        setTimeout(test, COOL);
    });
}
.hide { display: none }
<button id="test2" class="hide">Test 500000 items</button>


Using visual themes in a game In my small application, I need to use a variety of visual themes.

The simplified structure of this class:

Theme
  |
  .__ menu
  |     |
  |     .__ screenBackground
  |     .__ itemsColor
  |     .__ getRandomItemAnimation()
  |
  .__ game
  |     |
  |     .__ screenBackground
  |     .__ gameBoardBackground
  |     .__ getRandomMoveSound()
  |
  .__ getRandomStartScreenImage()

I want to write code like this:

setBackground(theme.game.screenBackground)

instead of

setBackground(theme.game().screenBackground())

But in addition to that, I want to use inheritance. However, Java does not seem to allow to override public fields of the parent class in the descendant classes.

So I've decided to use the following implementation:

Basic classes:

// All constructors (in the next 3 classes) used to set final class-members by descendants

public abstract class Theme {
    public final MenuTheme menu;
    public final GameTheme game;

    public abstract Image getRandomStartScreenImage();

    public Theme(MenuTheme menuTheme, GameTheme gameTheme) {
        this.menuTheme = menuTheme;
        this.gameTheme = gameTheme;
    }
}

public abstract class MenuTheme {
    public final Image screenBackground;
    public final Color itemsColor;

    public abstract Animation getRandomItemAnimation();

    public MenuTheme(Image screenBackground, Color itemsColor) {
        this.screenBackground = screenBackground;
        this.itemsColor = itemsColor;
    }
}

public abstract class GameTheme {
    public final Image screenBackground;
    public final Image gameBoardBackground;

    public abstract Sound getRandomMoveSound();

    public GameTheme(Image screenBackground, Image gameBoardBackground) {
        this.screenBackground = screenBackground;
        this.gameBoardBackground = gameBoardBackground;
    }
}

Using:

public class Menu {
    public void setUp() {
        Theme theme = GameContext.getCurrentTheme();
        setBackground(theme.menu.screenBackground);
        setItemsColor(theme.menu.itemsColor);
    }

    public void onClickItem(Item clickedItem) {
        Theme theme = GameContext.getCurrentTheme();
        clickedItem.startAnimation(theme.menu.getRandomItemAnimation());
        // Action action = getActionByItem(clickedItem);
        // action.start();
    }
}

How to add theme:

public class DarkTheme extends Theme {
    private Image[] startScreenImages = getStartScreenImages();

    public Image getRandomStartScreenImage() {
        return startScreenImages[getRandomIndex()];
    }

    public DarkTheme() {
        super(new DarkMenuTheme(), new DarkGameTheme());
    }
}

public class DarkMenuTheme extends MenuTheme {
    private Animation[] itemAnimations = getItemAnimations();

    public Animation getRandomItemAnimation() {
        return itemAnimations[getRandomIndex()];
    }

    public DarkMenuTheme() {
        super(getDarkMenuScreenBackground(), getDarkMenuItemsColor());
    }
}

public class DarkGameTheme {
    private Sound[] moveSounds = getMoveSounds();

    public Sound getRandomMoveSound() {
        return moveSounds[randomIndex()];
    }

    public DarkGameTheme() {
        super(getDarkGameScreenBackground(), getDarkGameBoardBackground());
    }
}

What do you think about the structure of Theme?  Does it look like a good implementation?

The structure of Theme does not expect to be changed. There will only be the addition of new themes. Given this, what are the drawbacks and benefits of this code?  What improvement or other implementation can you recommend?

I want to write code like this:
  setBackground(theme.game.screenBackground) instead of
  setBackground(theme.game().screenBackground())

Read this : http://c2.com/cgi/wiki?AccessorsAreEvil

The URL is misleading, it is a 'balanced' article, the part I want you to pay particularly attention is this:

  The examples [...] they are really structures (data), not quite
  objects.

Your theme class should really be a structure, and be too simple to have getters.

In response to @bowmore, the Theme should not be responsible for loading resources, the theme should really return resource identifiers.

If it were me, by the way, I would probably go for

game.drawBackground()

where game knows what the theme is, and gets from theme the resource name for the background which a loader class then loads and a UI class then displays.


Adjoin-set for an ordered set representation From SICP:

  Exercise 2.61

  Give an implementation
  of adjoin-set using the ordered
  representation. By analogy with
  element-of-set? show how to take
  advantage of the ordering to produce a
  procedure that requires on the average
  about half as many steps as with the
  unordered representation.

(define (adjoin-set x set)
  (define (rec subset)
    (cond ((null? subset) (list x))
          ((> x (car subset)) (cons (car subset) (rec (cdr subset))))
          (else (cons x subset))))
  (if (element-of-set? x set)
      set
      (rec set)))

Can this be improved?

Calling element-of-set? from adjoin-set introduces unnecessary redundancy.  One may incorporate this test within the adjoin-set function (in your case, rec should be the main body of your function, with an = test added):

(define (adjoin-set x set)
  (cond
    ((null? set) (cons x set))
    ((= x (car set)) set)
    ((< x (car set)) (cons x set))
    (else (cons (car set) (adjoin-set x (cdr set))))))

This function performs fewer steps since it does not call element-of-set?.  However, its complexity is still O(n), which is the same as your implementation's complexity, as well as the complexity of element-of-set?.


Simple Binary to Decimal Converter I just recently began going over number systems again, granted I didn't pay very much attention to it the first time for lack of understanding its importance (I've only been coding for a year and some change). Below this paragraph of text I have a simple Binary to Decimal converter, and I was wondering if there's a better way to do this, or if my algorithm is okay:

import java.util.Scanner;

public class BinaryToDecimal {

public static void main(String[] args) {
    Scanner scan1 = new Scanner(System.in);
    System.out.println("Enter a binary number: ");
    String Binary = scan1.next(); // 11011
    double power = 0;
    double sum = 0;

    for (int i = Binary.length() - 1; i >= 0; i--) {
        char TempHold = Binary.charAt(i);
        double num = Character.getNumericValue(TempHold);
        sum = (sum + (num * (Math.pow(2, power))));
        power++;
    }

    System.out.println(sum + "(10)");

}

}

My process:

The first step was to, of course, allow the user to input their own binary number for testing purposes with a scanner and a variable of String called Binary for the initialization of this input (I chose to make this a String vs an Integer for looping purposes).
Next I created a variable of type double called power that will start off at 0 and be utilized in the for loop later.
Lastly, as far as preliminary variable declarations go, I created a sum variable to hold the sum of the binary-decimal conversion.
Within the for loop I ensured that my iterator traversed the String backwards in respect to my method of conversion.
After setting up the for loop, I created a variable of type Character called TempHold to seize and store the character of the Binary variable that corresponds to the current iteration of the loop.
My next step was to parse the TempHold Character variable into a String so that I could utilize it arithmetically in my conversion method.
At the end of this for loop I incremented the power variable so that I could increase the value of the exponent being used in the conversion method.

Your algorithm is ok, there are only a few minor hints for improvement:

You're using double-typed variables. Although in your case the computations will be exact up to fairly large numbers, it's generally safer to use int or long if you don't need the fractional part.

Two of your variable names begin with an upper-case letter (Binary and TempHold). That's unusual for Java code, as the vast majority of programs follows the naming conventions, so much that I find it irritating to read non-conforming code.

Your variable power has a name that confused me first. I'd call it exponent (in mathematics, "power" is the result of exponentiation). And I'd rename TempHold to digitChar and num to digitVal.

Math.pow() isn't really fast, so I recommend a different approach. With every iteration, the power grows by a factor of two, so I'd use something like power = power * 2; inside the loop.

For production code, you should separate input/output from computation, e.g. by putting the conversion part into a method of its own.

It's good style to close Scanners when they are finished (although that will eventually be done by Java's garbage collector if you don't do it explicitly).

So, my version of your program would be:

import java.util.Scanner;

public class BinaryToDecimal {

    public static void main(String[] args) {
        Scanner scan1 = new Scanner(System.in);
        System.out.println("Enter a binary number: ");
        String binary = scan1.next(); // 11011

        String decimal = toDecimal(binary);

        System.out.println(decimal + "(10)");
        scan1.close();
    }

    public static String toDecimal(String binary) {
        long power = 1;
        long sum = 0;

        for (int i = binary.length() - 1; i >= 0; i--) {
            char digitChar = binary.charAt(i);
            int digitVal = Character.getNumericValue(digitChar);
            sum = sum + digitVal * power;
            power = power * 2;
        }
        return String.valueOf(sum);
    }
}


Optimize Game of Life I'm a beginner at coding and the past days I tried to write the famous "Conway's Game of Life" in Angular.js. Right now I'm done with the code and the game works. But if the size of the playground grid gets too big (e.g. 100x100 cells), my program is kind of slow. I wanted to ask you where I could improve my code to make it run more quickly. It would be great for me to see what I have could done in a better way to learn from it.

The following code creates the grid for the playing field and gives the cells their coordinates and alive status:

$scope.createGrid = function(width,height){ // Spielfeld erzeugen
    $scope.playingField = {
        width:width,
        height:height,
        data:[]
    };
    for( var r = 0 ; r < width; r++){
        $scope.playingField.data.push([]);
        for( var c = 0 ; c < height; c++){
            $scope.playingField.data[r].push({ x:c, y:r, alive:false });
        }
    }
    $(".grid").width("600px");
    $(".grid").height("600px");
};

Changes color and live status of a cell when clicked on it:

$scope.clickCell = function(cell){ // Zellen Status ändern. tot / leben
    cell.alive = !cell.alive;
};
$scope.style = function(value) { // Einen Style zuweisen
    return { "background-color": value };
};

This is the part where I think the program gets slowed down. It checks all the cell neighbours and copies a new grid after it; I would be very curious about other solutions to this problem:

$scope.startRound = function(){ // Runde durchlaufen
    console.time("Benchmark für das kopieren");
    // TODO: Kopieren ist zu langsam, muss anders erfolgen!
    var newData = angular.copy($scope.playingField.data);
    console.timeEnd("Benchmark für das kopieren");
    angular.forEach($scope.playingField.data, function(cells,r){
        angular.forEach(cells, function(cell,c){
            var alive = 0;
            //Nachbarn überprüfen
            for(var i = r-1 ; i<=r+1;++i){
                for(var j = c-1; j<= c+1 ; ++j){
                    if($scope.getCell(j,i).alive){
                        alive++;
                    }
                }
            }

            if(cell.alive){
                alive -=1;
            }

            // Regeln überprüfen
            if(cell.alive == true && (alive < 2 || alive > 3)){
                newData[r][c].alive = false;
            }
            if(cell.alive == true && (alive == 2 || alive == 3)){
                newData[r][c].alive = true;
            }
            if(cell.alive == false && alive == 3){
                newData[r][c].alive = true;
            }
        });
    });

    $scope.playingField.data = newData;
};

Checks if an alive cell is at the edge of the playing field. If yes, then a new neighbour will be set.

 $scope.getCell = function(x,y){ // Nachbarn überprüfen
    // Wenn das Spielfeld verlassen wird, wird der Nachbar neu bestimmt (auf der anderen Seite)
    var h = $scope.playingField.height-1;
    var w = $scope.playingField.width-1;
    return $scope.playingField.data[(y+h) % h][(x+w) %w];
};

Functions to start the game, stop the game and to refresh the grid.

$scope.startGame = function(){ // Spiel starten
    console.log("Game started");
    $scope.stopInterval = $interval($scope.startRound, 10);
};
$scope.stopGame = function(){ // Spiel beenden
    console.log("Game stopped");
    $interval.cancel($scope.stopInterval);
};
$scope.refreshGameField = function(){ //Sspielfeld zurücksetzen
    console.log("Game refreshed");
    $scope.createGrid($scope.playingField.width, $scope.playingField.height);
};

The problem is that angular.copy is a really slow function (discussion here: https://github.com/angular/angular.js/issues/11099), in order to copy the array without references you could also do something like this:

var newData = JSON.parse(JSON.stringify($scope.playingField.data));

This should be a big improvement in speed.


Exercism: determine if a word or phrase is an isogram The task:

Determine if a word or phrase is an isogram.
An isogram (also known as a "nonpattern word") is a word or phrase without a repeating letter, however spaces and hyphens are allowed to appear multiple times.

Examples of isograms:

lumberjacks
background
downstream
six-year-old

The word isograms, however, is not an isogram, because the s repeats.
Even though I'm aware that questions about isograms have already been posted, in this variation of the problem spaces and hyphens are allowed to appear multiple times so that you can not use a solution such as len(string) == len(set(string))
What bothers me about my solution is hardcoding bounds of ascii character ranges and using collections library for such a small problem. I'm wondering if there is a better way to do it.
Here is my code:
from collections import Counter

ASCII_LOWER_BOUND = 97
ASCII_UPPER_BOUND = 123

def is_isogram(string):
    char_counts = Counter(string.lower())
    return all(
        char_counts[char] == 1
        for char in char_counts
        if ord(char) in range(ASCII_LOWER_BOUND, ASCII_UPPER_BOUND + 1)
        )

And a test suite provided by exercism:
import unittest

from isogram import is_isogram

# Tests adapted from `problem-specifications//canonical-data.json` @ v1.7.0

class IsogramTest(unittest.TestCase):
    def test_empty_string(self):
        self.assertIs(is_isogram(""), True)

    def test_isogram_with_only_lower_case_characters(self):
        self.assertIs(is_isogram("isogram"), True)

    def test_word_with_one_duplicated_character(self):
        self.assertIs(is_isogram("eleven"), False)

    def test_word_with_one_duplicated_character_from_the_end_of_the_alphabet(self):
        self.assertIs(is_isogram("zzyzx"), False)

    def test_longest_reported_english_isogram(self):
        self.assertIs(is_isogram("subdermatoglyphic"), True)

    def test_word_with_duplicated_character_in_mixed_case(self):
        self.assertIs(is_isogram("Alphabet"), False)

    def test_word_with_duplicated_character_in_mixed_case_lowercase_first(self):
        self.assertIs(is_isogram("alphAbet"), False)

    def test_hypothetical_isogrammic_word_with_hyphen(self):
        self.assertIs(is_isogram("thumbscrew-japingly"), True)

    def test_hypothetical_word_with_duplicated_character_following_hyphen(self):
        self.assertIs(is_isogram("thumbscrew-jappingly"), False)

    def test_isogram_with_duplicated_hyphen(self):
        self.assertIs(is_isogram("six-year-old"), True)

    def test_made_up_name_that_is_an_isogram(self):
        self.assertIs(is_isogram("Emily Jung Schwartzkopf"), True)

    def test_duplicated_character_in_the_middle(self):
        self.assertIs(is_isogram("accentor"), False)

    def test_same_first_and_last_characters(self):
        self.assertIs(is_isogram("angola"), False)

if __name__ == "__main__":
    unittest.main()
```

You can iterate once over text and short-circuit right away if any character is not unique.
import string

def is_isogram(text):
    seen = set()
    for char in text:
        if (lower := char.lower()) in string.ascii_lowercase:
            if lower in seen:
                return False
            else:
                seen.add(lower)
    return True


Remove, Append, and Resize Using jQuery I'm trying to essentially replace an element and make it transition smoothly to the new size... I started off trying to work with the appended element itself, but the padding and margins made that difficult, so I switched to using a container.

var template = "
I've replaced the button
and in a very smooth
fashion!
";

var doAnimation = function(e) {
    var parent = $(this).parent();
    var oldHeight = parent.height();

    $(this).fadeOut(400, function() {
        this.remove();

        var paragraph = $(template).appendTo(parent);
        var newHeight = parent.height();

        paragraph.hide().fadeIn();
        parent.height(oldHeight).animate({height: newHeight});
    });
}

$(document).on('click', 'button', doAnimation);

Here is the demo on jsFiddle: first attempt, second attempt

Is there a better way to go about doing this and how would I extract it to something that's reusable?

Edits:

3rd attempt - simply extracted the template to the HTML...

4th attempt - added some data attributes and string replacements.

If i'm understanding your question correctly what you have is pretty much there already. The only change I can suggest is to let your HTML establish the relationship between your trigger button and the template containing your new HTML like so:

http://jsfiddle.net/vax6hp28/5/

HTML

    <button data-target="#template-addText">Click Me</button>

Javascript

var appendResize = function(e) {
    var parent = $(this).parent();
    var oldHeight = parent.height();
    var templateRef = $($(this).data('target'));

    $(this).fadeOut(400, function() {
        this.remove();

        var template = templateRef.html();
        var paragraph = $(template).appendTo(parent);
        var newHeight = parent.height();

        paragraph.fadeIn(2000);
        parent.height(oldHeight).animate({height: newHeight});
    });
}

$(document).on('click', 'button', appendResize);

This allows you to create as many buttons/template combinations as you like without having to change the javascript.


TapeEquilibrium - codility - JavaScript Problem
A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.
Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between the sum of the first part and the sum of the second part.
For example, consider array A such that:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

We can split this tape in four places:
P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

Write a function:
function solution(A);
that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.
For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
My solution:

A = []
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)

  if (A.length > 0) {
    let defArr = [];
    let l = [];
    let all = A.reduce((a, b) => {
      l.push(a)
      return a + b
    })

    l.forEach((item) => {
      defArr.push(Math.abs(all - (item + item)))
    })
    return Math.min(...defArr)
  }

  return 0;

}
console.log(solution(A))

Logically, the code looks correct but from performance perspective, there are few things that can be improved. Let's look at the 2 points:

Time Complexity: O(n) - 1 loop, 1 reduce and 1 Math.min. All run in O(n) time.
Space Complexity: O(n) - Two arrays - defArr and l which have size n

There is nothing can be done for time complexity but space complexity can be reduced to constant space. No need to have additional arrays. One can simply loop and store intermediate values in temporary variables.

I have re-written the same. Inside the loop, at each index, the difference is calculated and compared to a min variable. If the new min is lesser than existing one; then update min otherwise do next iteration.

A = []
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

function solution(A) {
  let sum = A.reduce((total, value) => total + value, 0)
  let min = Number.POSITIVE_INFINITY
  let cumulativeSum = 0
  for (let i = 0; i < A.length - 1; ++i) {
    cumulativeSum = cumulativeSum + A[i]
    sum = sum - A[i]
    diff = Math.abs(sum - cumulativeSum)
    if (diff < min) {
      min = diff
    }
  }
  return min
}

console.log(solution(A))

Hope it helps. Revert for any doubts/clarifications.


Adding values from DictReader to empty dictionary I made a rock climbing simulator game for fun.  Below is a function from the program, which works. But I can't help but think it could be refactored or more pythonic.

Namely, I open the data with csv.DictReader and read through the data, which add to a blank dictionary called route_info.  Is this step necessary?

The function has a with-open block, which opens a .csv file, but a link to the data is here.

import csv
import time

routes_climbed = []
pitches_climbed = 0

def choose_route():
    """After deciding about the weather, you come here and choose a
    route to climb. Reads list of routes from .csv file with names,
    grades, and pitches."""

    global routes_climbed, pitches_climbed

    route_info = {}

    with open('seneca_routes.csv', 'r', encoding='utf-8-sig') as f:     #weird encoding from excel?
        reader = csv.DictReader(f, ('route_name', 'route_grade', 'pitches'))
        print("Choose a route to climb from the following list of classics.")
        print()

        for row in reader:
            print(row['route_name'],row['route_grade'])
            route_info[row['route_name']] = row['pitches']

    route_choice = input("Which route do you want to climb? : ")

    if route_choice in route_info.keys():
        routes_climbed.append(route_choice)
        pitches_climbed += int(route_info[route_choice])
        climb_route(route_choice)
    else:
        print("Incorrect route name")
        time.sleep(3)
        choose_route()

choose_route()

Some suggestions:

Pass the code through at least one linter such as pycodestyle or flake8 to get more idiomatic Python.
Don't use global. Returning two values, while ugly, is preferable to having global state.
You can add \n to the end of a string to print a newline, avoiding empty print()s.
Use argparse to rather than input() to make the script … well, scriptable.
Each route should probably be an object rather than a disparate set of just stuff, even though these objects will have no methods for now.
Using a main method as the entry point for the functionality would make the script usable by other scripts.


Business program for a computer shop Any advice would be great. I watched a few videos over the last 3 weeks and made a program up; what do you think?

The program is a business ideal for a few computers in a shop, some computers with training and the rest of the computers without. (for gaming, etc.)

import java.util.Scanner;

public class n_com {

    public static void main (String args []){

        Scanner input = new Scanner (System.in);

    double training,p_h,computer_training,computers,open;

    double max,two,thre,four,five;
    double two2,thre3,four4,five5,p;

    System.out.print("please enter cost of training people up on the computer p/h £ ");
        training =input.nextDouble();

    System.out.print("please enter cost to use the pc p/h for general use £");
             p_h=input.nextDouble();

    System.out.print("please enter number of computer in the shop for training :");
             computer_training =input.nextInt();

    System.out.print("please enter number of computer in the shop for general use :");
            computers =input.nextInt();

    System.out.print("please enter hours open per week :");
             open=input.nextDouble();

    training = training * computer_training * open; //max income per week w/training
       p_h = p_h * computers * open;  //max income per week (gamers ect)

    max = training + p_h;

            two  =0.2 * max;    // 20%  max total
            thre =0.3 * max;    // 30%  max total
            four =0.4 * max;
            five =0.5 * max;

            p = 0.45;  // % of shop taking paid per week as wages

            two2  = p * two;  // 45% of the estimated shop taking (two = 0.20% of max)
            thre3 = p * thre;
            four4 = p * four;
            five5 = p * five;

            max = (max * 52 / 12);
            System.out.println();

       System.out.println ("maxim monthly income from the computers £ "+ max);

            System.out.println();

       System.out.println ("total income estimated over the next 2 years");

       System.out.println();

       System.out.println("estimated monthly income at mouth 1-3 \t:"+ two );
       System.out.println("estimated monthly income at mouth 3-6 \t:"+ thre);
       System.out.println("estimated monthly income at mouth 6-12\t:"+ four);
       System.out.println("estimated monthly income at year  1-2 \t:"+ five);

            System.out.println();

        System.out.println("wages will be 45% of total income at the end of each mouth" );

            System.out.println();

       System.out.println("estimated monthly wages for mouth 1 - 3  £ "+ two2  );
       System.out.println("estimated monthly wages for mouth 4 - 6  £ "+ thre3 );
       System.out.println("estimated monthly wages for mouth 7 - 12 £ "+ four4 );
      System.out.println("estimated monthly wages after the first year £"+five5);
     }
 }

Wording

First, the terminology you chose seems a bit off.  I believe that you are writing this program from the point of view of an entrepreneur or investor in a business, looking to earn income by making computers available for training and general use.  Instead of "cost", you should be talking about price.

There are also some spelling mistakes ("Maximum" → "maxim", "number of computers" → "number of computer", and "month" → "mouth").

Misuse of variables

This program is basically a textual spreadsheet that accomplishes this (inputs in italic, outputs in bold):

As such, there are many variables to track, and therefore proper naming is critical to keep track of all of those numbers.  More importantly, you should not repurpose a variable midway through the program, as you have done here:

training = training * computer_training * open;

and

max = (max * 52 / 12);

Such reassignments prevent you from naming the variable appropriately, and from reasoning about the code.  In fact, the resulting confusion has led to a bug.  The assignment two = 0.2 * max is based on max as a weekly amount.  You subsequently reassigned max = (max * 52 / 12) as a monthly amount.  You then report two as a monthly amount:

System.out.println("estimated monthly income at mouth 1-3 \t:"+ two );

You would be better off with fewer variables, by eliminating variables two, etc.

Style

Nobody likes to read huge declaration blocks:

double training,p_h,computer_training,computers,open;

double max,two,thre,four,five;
double two2,thre3,four4,five5,p;

Instead, declare the variables at the assignment point.

You can make use of import static to avoid writing System.out everywhere.

import java.util.Scanner;
import static java.lang.System.out;

public class BusinessEstimator {
    public static void main (String args []) {
        try (Scanner input = new Scanner(System.in)) {
            out.print("please enter price of training people up on the computer p/h: £");
            double trainingPrice = input.nextDouble();

            out.print("please enter price to use the pc p/h for general use: £");
            double generalPrice = input.nextDouble();

            out.print("please enter number of computers in the shop for training: ");
            double trainingComputers = input.nextInt();

            out.print("please enter number of computers in the shop for general use: ");
            double generalComputers = input.nextInt();

            out.print("please enter hours open per week: ");
            double hoursPerWeek = input.nextDouble();

            double trainingWeeklyIncome = trainingPrice * trainingComputers * hoursPerWeek;
            double generalWeeklyIncome = generalPrice * generalComputers * hoursPerWeek;
            double maxWeeklyIncome = trainingWeeklyIncome + generalWeeklyIncome;
            double maxMonthlyIncome = maxWeeklyIncome * 52 / 12;

            double WAGES_PCT = 0.45;  // % of shop taking paid as wages

            out.println();

            out.println ("maximum monthly income from the computers £ "+ maxMonthlyIncome);
            out.println();

            out.println ("total income estimated over the next 2 years");
            out.println();

            out.println("estimated monthly income at month 1-3 \t:"+ 0.2 * maxMonthlyIncome);
            out.println("estimated monthly income at month 3-6 \t:"+ 0.3 * maxMonthlyIncome);
            out.println("estimated monthly income at month 6-12\t:"+ 0.4 * maxMonthlyIncome);
            out.println("estimated monthly income at year  1-2 \t:"+ 0.5 * maxMonthlyIncome);
            out.println();

            out.println("wages will be 45% of total income at the end of each month" );
            out.println();

            out.println("estimated monthly wages for month 1 - 3  £ "+ 0.2 * WAGES_PCT * maxMonthlyIncome);
            out.println("estimated monthly wages for month 4 - 6  £ "+ 0.3 * WAGES_PCT * maxMonthlyIncome);
            out.println("estimated monthly wages for month 7 - 12 £ "+ 0.4 * WAGES_PCT * maxMonthlyIncome);
            out.println("estimated monthly wages after the first year £"+ 0.5 * WAGES_PCT * maxMonthlyIncome);
        }
    }
}


Finding the minimum and maximum sums For this HackerRank warmup challenge, I was wondering if there was a way I could improve the selection of my indices for the minSum:

Here is the problem:

  Print two space-separated long integers denoting the respective minimum and maximum values that can be calculated by summing exactly four of the five integers. (The output can be greater than 32 bit integer.)

  Sample Input

1 2 3 4 5

  Sample Output

10 14

Here is the solution:

function miniMaxSum(inArr) {
    // Complete this function

    let maxSum = 0,
        minSum = 0;
   inArr.sort();

    for (var i = arr.length - 1, o = 0; i >= arr.length - 4, o < 4; i--, o++){
       maxSum += arr[i];
       minSum += arr[o];
    }
    console.log(minSum, maxSum)
}

Is there a way I could have avoided the o counter in my for loop and instead selected the array in a different way? Like minSum += arr[some math computation].

Also, any performance optimizations are welcome too.

Instead of calculating two sums, you could just calculate one: the sum of all elements. Then, the min sum is the sum minus the maximum element, and max sum is the sum minus the minimum element.
Note that sorting just to find the minimum and maximum elements is inefficient, because sorting is generally an \$O(n \log n)\$ operation,
and finding the minimum and maximum (and the sum) is possible in a single pass, which would be \$O(n)\$.

Hard-coding the number 4 makes the solution very rigid, applicable to only this specific problem. In your implementation you could use the length of the array instead in a way to make that number 4 unnecessary, and easily make your implementation applicable to a more general set of problems. The number 4 is an artificial restriction; it's wise to get rid of it.


Histogram of letters in string I'm pretty new to Java and I've been trying to use top-down design and make my code very readable, so I would appreciate any comments as to the clarity and efficiency of this program.

Looking for feedback on: readability (spacing, comments, etc) and just overall quality of code!

The task is to produce a histogram that shows how many times a certain letter appears in a string.

import java.util.Scanner;

/** This class creates a histogram of the letters in a string. Ie outputs
 ** how many times the letter a appears in the string, the letter b... and so on
 ** until z. Extra challege: only traversing the string once
 **/

public class Histogram{
  public static void main(String[] args){

    Scanner kb = new Scanner(System.in);
    final int LETTERS_IN_ALPHABET = 26;
    int[] letterCounter = new int[LETTERS_IN_ALPHABET]; //holds info on how many
    //times a letter appears. eg letterCounter[0] -> how many times a appears

    System.out.print("Enter string: ");
    String string = kb.nextLine();

    for(int i = 0; i < string.length(); i++){//traversing string
      char letterThere = string.charAt(i);//reads what character is at index
      int placeInLetterCtr = whereInLetterCtr(letterThere);//determining where it should go in array

      letterCounter[placeInLetterCtr] ++;//increasing corresponsing index
    }

    printNumbers(letterCounter);
    printLetters();

  }//end main

/* given a char, determines at what index of the character storage array the
 * char belongs to. Eg, if given the char 'c', it should return int 2
 */
  public static int whereInLetterCtr(char letter){
    int i =0 ;
    for(char comparisonLetter = 'a'; comparisonLetter <= 'z'; comparisonLetter++){
      if(letter == comparisonLetter){
        return i;
      }
      i++;
    }
    return i;
  }//end whereInLetterCtr

/* prints row of numbers */
  public static void printNumbers(int[] array){
    for(int i=0; i<array.length; i++){
      System.out.printf("%4d", array[i]);
    }

    System.out.println();
  }//end printNumbers

/* prints row of letters */
  public static void printLetters(){

    for(char letter ='a'; letter <='z'; letter++){
      System.out.printf("%4c", letter);
    }
  }//end printLetters

}//end class

Throughout your code you use for loops.  Java 8 has been around for 4 years now. It is time you start using the new (now quite old) collection streams. Here are some snipets to get you started:

string.chars().forEach(letterThere -> {
  ...
})

IntStream.rangeClosed('a', 'z').forEach(i -> {
  ...
})

regarding whereInLetterCtr() : you advance comparisonLetter from 'a' to 'z' with the ++ operator so you realize that the letters form a sequence of numbers and that you can apply mathematical operations on them.
so...
instead of the whole loop you can get the result by doing letter - 'a'


Print words in decreasing order of frequency in Scala Given a string print its words in decreasing order of frequency.

  Example:

i/p - "aa bbb  ccc aa ddd aa ccc"
o/p - aa,ccc,ddd,bbb

Scala:

import collection.mutable.PriorityQueue
import collection.mutable.HashMap

object FindWordFreq extends App {
  case class wordFreq(w: String, c: Int) extends Ordered[wordFreq] {
    override def compare(that: wordFreq): Int = c compareTo(that.c)
  }
  val words = "aa bbb  ccc aa ddd aa ccc" split " +"
  val wordCount = HashMap[String, Int]()
  for  (word <- words)  {
    wordCount += (word -> (wordCount.getOrElse(word,0) + 1))
  }
  val myHeap = PriorityQueue[wordFreq]()
  wordCount.toSeq foreach { case (w,c) => myHeap.enqueue(wordFreq(w,c))  }
  println(myHeap.dequeueAll.map(_.w).mkString(","))
}

I do think that we can just do with Priority Queue (and get rid of map), but could not come up with very clean code with that.

Using just a priority queue

Yes, it's possible, although you would need a special implementation of priority queue, which internally is a hash map + a heap. This trick is commonly used in Dijkstra's algorithm. See https://stackoverflow.com/a/17581306/1370445.

Unlike in Dijkstra's algorithm, in your task, you don't need to be able to alternately update values on the heap and remove the top element. So I would discourage you from using this data structure, and encourage to instead focus on achieving high code quality (including low code volume), using the data structures and operations available in Scala's standard library.

Here are my recommendations regarding possible improvements to the code, some of them obsolete the others in the context of this specific piece of code, but I think it's worth to mention them anyway:

Use UpperCamelCase for class names

Scala has an official naming convention (https://docs.scala-lang.org/style/naming-conventions.html) which recommends to name classes with UpperCamelCase, so wordFreq should be WordFreq.

Use Scala syntax consistently

Scala let's you replace the dot and parentheses with a space in some case. x method param is equivalent to x.method(param). In the snippet of code you've provided you sometimes use that feature ("aa bbb  ccc aa ddd aa ccc" split " +"), sometimes use just part of it c compareTo(that.c) and sometimes you don't use it (myHeap.enqueue(wordFreq(w,c))). I would recommend you to decide which style of code you prefer (I prefer dots and parentheses) and use it consistently, at least within a single source file.

Embrace immutability

Scala provides two sets of collections, mutable and immutable. In most cases it's preferable to use immutable collection as they make reasoning easier and eliminate whole class of bugs. I won't dive deeper into that topic, as it is covered in detail by many articles on the internet, for example:

https://www.quora.com/What-are-the-advantages-and-disadvantages-of-immutable-data-structures
https://www.yegor256.com/2014/06/09/objects-should-be-immutable.html

Prefer Ordering over Ordered

Ordered binds together the data structure and the way of ordering/comparing them. This is reasonable for thing which have some notion of "natural order" like Strings, or Integers. Ordering lets you deliver the way of ordering separately from the data structure declaration, resulting in more composable code.

So instead of

case class wordFreq(w: String, c: Int) extends Ordered[wordFreq] {
  override def compare(that: wordFreq): Int = c compareTo(that.c)
}

I would write

case class WordFreq(w: String, c: Int)
val mostFrequentFirstWordFreqOrdering: Ordering[WordFreq] =
  (x: WordFreq, y: WordFreq) => y.c.compareTo(x.c)

you could make the mostFrequentFirstWordFreqOrdering implicit so that the compiler will pick it up automatic, but since there's more than one reasonable way to sort WordFreq I would prefer to stay explicit and pass the ordering by-hand.

Use sorted/sortBy instead of hand-crafting a heap sort

val myHeap = PriorityQueue[wordFreq]()
wordCount.toSeq foreach { case (w,c) => myHeap.enqueue(wordFreq(w,c))  }
myHeap.dequeueAll

Is basically a heap sort implementation.  It could be replaced by the sorted or the sortBy methods of SeqLike. It could look like

wordCount.toSeq.sortBy{case (word, count) => -count}

or if you find the - and inelegant way of reversing the order, alternatives are:

wordCount.toSeq.sorted(Ordering.by[(String, Int), Int]{case (word, count) => count}.reverse)

or

wordCount.toSeq.sortBy{case (word, count) => count}.reverse

the last one being less efficient in terms of allocations.

countBy

val wordCount = HashMap[String, Int]()
for  (word <- words)  {
  wordCount += (word -> (wordCount.getOrElse(word,0) + 1))
}

can be replaced with

words.groupBy(x => x).mapValues(_.length)

In fact I observe this pattern so often, that in some project I have an "extension method" countBy added to Traversable like this:

implicit class RichTraversable[+A](val traversable: Traversable[A]) extends AnyVal {
  def countBy[K, That](accessor: A => K): Map[K, Int] =
    traversable.groupBy(accessor).mapValues(_.length)
}

Separate calculations from making side effects

The line println(myHeap.dequeueAll.map(_.w).mkString(",")) does two things. It finishes the process of sorting the results myHeap.dequeueAll.map(_.w) and prints them in human readable format println(results.mkString(",")). Two things should be done in two lines, or better, two methods, or better functions (..., but functional IO is a longer topic).

Split by more than just spaces
In real-world text words may be separated by more than just spaces - new-lines, commas, semicolons, etc.. \W is a regex pattern for "non-word character" (see https://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html). Using "\\W+" would be better than " +", although most likely there would still be some edge-cases where it would go wrong.

Final result

After all the suggested modifications the code could look like this:

object FindWordFreq extends App {
  val words = "aa bbb  ccc, aa ddd\naa\rccc" split "\\W+"
  val wordCounts = words.groupBy(x => x).mapValues(_.length)
  val wordsByDescendingNumberOfOccurrences = wordCounts.toSeq.sortBy{case (_, count) => count}.reverse
  println(wordsByDescendingNumberOfOccurrences.mkString(","))
}


Contest Solution: Super Freq The Problem

  A character is known to its homeboys as a super freq if it occurs with frequency greater than 15% in a given passage of text. Write a program that reads an ASCII text file and identifies all the English alphabet (A-Z, a-z) super freqs in that text file. Your program should be case insensitive.

  Sample Input

  Your program should take its input from the text file prob2.in. Three examples (A, B and C) of the possible content of this file are shown below:

(A) Sally sells sea shells by the sea shore.
(B) How now brown cow.
(C) Hey Sam!

  Sample Output

  Your program should direct its output to the screen. Appropriate output for the sample inputs (A, B and C) is shown below:

(A) S is a super freq.
(B) O is a super freq.
    W is a super freq.
(C) There are no super freqs.

superfreq.py

import re
from collections import Counter

with open('prob2.in') as f:
    for line in f:
        s = re.sub(r"[^a-z]+", '', line.lower())
        d, c = Counter(s), 0
        for e in d:
            if d[e] / len(line) > 0.15:
                print('{0} is a super freq.'.format(e.upper()))
                c += 1
        if (c == 0):
            print('There are no super freqs.')

Any advice on performance enhancement and solution simplification or that is topical is appreciated!

The variable names c, d, and e are too cryptic.  (f is fine, because it's a customary variable for a file.  In my solution below, I use c consistently for characters during iteration, which is also acceptable.)

Why do you normalize the case using line.lower(), when the sample output suggests that uppercase output is preferred?

In my opinion, the regular expression is overkill here.

The challenge is ambiguous as to what exactly constitutes "15% in a given passage of text".  Does the denominator include the spaces and punctuation?  That's debatable.  Should the denominator include the trailing newline?  Probably not, but you should be aware that you did.

Personally, I'd prefer to collect all of the super freqs using a list comprehension, instead of checking for the if (c == 0): … case.  In any case, there shouldn't be parentheses there in standard Python style.

from collections import Counter

with open('prob2.in') as f:
    for line in f:
        counts = Counter(c for c in line.upper() if 'A' <= c <= 'Z')
        super_freqs = [c for c, n in counts.items() if n / len(line) > 0.15]
        if not super_freqs:
            print('There are no super freqs.')
        else:
            for c in super_freqs:
                print('{0} is a super freq.'.format(c))


HTML and CSS word styling and screen reader usability I’m trying to target three words in a h1 for the organization name using  to wrap each word and a unique ID to style each word via css.

It looks like this:

        The
        Community
        Space

However by using span and an ID for each work in the h1, I am causing the screen reader to pause after each word instead of speaking the organization name as a whole. Does anyone have any ideas to solve this issue?

You could try using a formating tag such as  or  instead of .

        The
        Community
        Space


Allocate N-dimensional array in C++ I need to allocate n-dimensional arrays of type T, currently I am using the following functions. Is there a better way to do this? Also, ideally I would like to allocate a 1-D array and access that as a N-D array but I could not figure out a better way of doing that. Using existing matrix library is not an option as I want access to raw pointers.

template <class T, class Ti>
T*** allocate_3d_array(Ti nx, Ti ny, Ti nz){
    T*** A = new T**[nx];
    for(Ti i(0); i < nx; ++i){
            A[i] = new T*[ny];
            for(Ti j(0); j < ny; ++j){
                A[i][j] = new T[nz];
                for(Ti k(0); k < nz; ++k){
                    A[i][j][k]= 0.;
                }
            }
    }
    return A;
}
template <class T, class Ti>
void release_3d_array(T*** A, Ti nx, Ti ny, Ti nz){
    for (Ti i = 0; i < nx; ++i){
            for (Ti j = 0; j < ny; ++j){
                delete[] A[i][j];
            }
            delete[] A[i];
    }
    delete[] A;
}

template <class T, class Ti>
T** allocate_2d_array(Ti nx, Ti ny){
    T** A = new T*[nx];
    for(Ti i(0); i < nx; ++i){
        A[i] = new T[ny];
    }
    return A;
}

template <class T, class Ti>
void release_2d_array(T** A, Ti nx, Ti ny){
    for (Ti i = 0; i < nx; ++i){
        delete[] A[i];
    }
    delete[] A;
}

template <class T, class Ti>
T* allocate_1d_array(Ti nx){
    T *A = new T[nx];
    return A;
}

template <class T, class Ti>
    void release_1d_array(T* A, Ti nx){
    delete[] A;
}

Answering Questions.

I need to allocate n-dimensional arrays of type T, currently I am using the following functions. Is there a better way to do this?

Yes. Create a class that wraps the 2/3 D array in such a way that memory management is done correctly in an exception safe manner.
You may need the raw pointer for interfacing with other libraries but that does not need to mean you should actively manage the pointer. You need to wrap these in a class so all the memory management for you but provide access to the RAW pointer for situations when you need it.
Example:
template<typename T>
class Array3D
{
    private:
    static T*** allocate_3d_array(std::size_t nx, std::size_t ny, std::size_t nz)
    {
        T*** A = new T**[nx];
        for(std::size_t i = 0; i < nx; ++i)
        {
            A[i] = new T*[ny];
            for(std::size_r j(0); j < ny; ++j)
            {
                A[i][j] = new T[nz];
                for(std::size_t k(0); k < nz; ++k)
                {
                    A[i][j][k]= 0.;
                }
            }
        }
        return A;
    }
    static void release_3d_array(T*** A, std::size_t nx, std::size_t ny, std::size_t nz)
    {
        for (std::size_t i = 0; i < nx; ++i)
        {
            for (std::size_t j = 0; j < ny; ++j)
            {
                delete[] A[i][j];
            }
            delete[] A[i];
        }
        delete[] A;
    }
    T*** data;
    std::size_t  xSize;
    std::size_t  ySize;
    std::size_t  zSize;
public:
    Array3D(std::size_t xSize, std::size_t ySize, std::size_t zSize)
        : data(allocate_3d_array(xSize, ySize, zSize)
        , xSize(xSize)
        , ySize(ySize)
        , zSize(zSize)
    {}
    ~Array3D()
    {
        release_3d_array(data, xSize, ySize, zSize);
    }

    // Disable Copy for now
    Array3D(Array3D const&)            = delete;
    Array3D& operator=(Array3D const&) = delete;

    // Disable Move for now
    Array3D(Array3D&&)                 = delete;
    Array3D& operator=(Array3D&&)      = delete;

    // Allow access to the underlying data when calling C function.
    operator T***()
    {
        return data;
    }
};

Now you can create a 3D array where the memory is correctly managed at all times (so no leaks). When you pass the data to a C function it will convert itself to a T*** so that it can be used (I am assuming that the C functions are non owning and will thus not destroy the array and the object is in the same thread and will thus live as long as the function call).
If you want to use operator[] to access the object See below were I have linked to a stackoverflow article.
Copy is probably not something you want with a 3D array. But if you need it you will need to implement the appropriate functions above.
Move is an advanced form of copy. don't use until you understand move semantics. Again you will need to implement the above functions.

Also, ideally I would like to allocate a 1-D array and access that as a N-D array but I could not figure out a better way of doing that.

Yes this would makes memory usage more effecient so would be the preferred technique to implement a multidimensional arrya. I refer you to an article I have written on SO that points you in the correct direction.
See: How to overload array index operator for wrapper class of 2D array? for an example.

Using existing matrix library is not an option as I want access to raw pointers.

To be honest I am bit surprised by this statement. In my mind this is a requirement of any library that wants to interface with C libraries. Not having this ability is shocking. Maybe you missed it. What library were you thinking of using?
Your current style is definitely lacking in relation to C++. The way you have implemented this provides no benefits to using C++ over C.
Generic Review
I see no need for the template type Ti
template <class T, class Ti>
T*** allocate_3d_array(Ti nx, Ti ny, Ti nz){

In my mind this is always an integer type. Pick one. If you did this for some specific reason that I have not deduced then this should be pointed out in the comments of the code (if it is not obvious to me then I don't think anybody else got it).
Use zero initialization.
new T;  // Alocates memory for T but does default initialization.
        // for POD types this means nothing is done and the value is
        // indeterminate.

new T();// Allocates memory for T but does zero initialization.
        // for pod types it means the values have zero.

            A[i][j] = new T[nz];
            for(Ti k(0); k < nz; ++k){
                A[i][j][k]= 0.;
            }

            // Can be replaced with:
            A[i][j] = new T[nz]();


Langton's Ant simulation I created a simple program to simulate the Ant's path.  The Ant moves north, west, east and south. Each time the Anth moves to an "uncharted" location, I build a Square and give it a color. Each time the Ant steps in a square, the square changes color and the Ant rotates 90° and keeps her track. I use a Stack where I push my Squares. The steps list is something I need to keep track of the path of the Ant. I need to find when the Path stabilizes (Roughly after 10000 steps) and the Ant moves in a uniform manner.

It works great until 106 (takes 5 minutes to run). After that it takes more than 14 hours to get to the 107 mark. I don't get why it takes so much more time, shouldn't it just take 10 × time it took to get to 106 iterations assuming my algorithm is o(n)?

I would like to keep the approach single threaded.  What can I optimize?

enum Orientation{
  NORTH, WEST, SOUTH, EAST
}

public class Square {
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}

int color = 0;
int x = 0, y = 1;
Stack<Square> squares = new Stack<Square>();
Orientation orientation = Orientation.NORTH;
List<Orientation> steps = new List<Orientation>();
for (int i = 0, counter = 0; i < 10000000; ++i, ++counter)
{

    // First
    if(i == 0)
    {
        squares.Push(new Square() { x = 0, y = 1, color = 1 });
        // Rotate
        orientation = Rotate(orientation, color == 0 ? true : false);
        steps.Add(orientation);
        continue;
    }
    // Move step
    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;

    // Check what the step has
    Square s = squares.Where(square => square.x == x && square.y == y).DefaultIfEmpty(null).FirstOrDefault();

    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }

    // 10^6 mark
    if (i == 999999)
    {
            blackSquaresAt100k = squares.Where(sqa => sqa.color == 1).Count();
            Console.WriteLine(blackSquaresAt100k);
    }

    // 10^7 mark
    if (i == 9999999)
    {
        blackSquaresAt1M = squares.Where(sqa => sqa.color == 1).Count();
        int totalNrOfBlackSquares = (blackSquaresAt1M - blackSquaresAt100k) * 12 + blackSquaresAt1M;
        Console.WriteLine(totalNrOfBlackSquares);
    }
}

Optimisation

  I use a Stack where I push my Squares.

A stack is the correct data structure when you want last-in-first-out behaviour. Is that the behaviour you need here?

  It works great until 106 (takes 5 minutes to run).

That is a long way from "great". 106 shouldn't take 10 seconds. Use the right data structure for the task, which here is something with amortised constant time insertion and lookup.

Other notes

public class Square {
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}

Why are all of the fields mutable? Why is there no explicit constructor? Rather than using a 32-bit type to store a single bit and needing to document the legal values, why not use a 1-bit type (i.e. bool isBlack)?

int color = 0;

Does this need such a wide scope?

for (int i = 0, counter = 0; i < 10000000; ++i, ++counter)

What is the purpose of counter? As far as I can tell, it isn't used anywhere.

        squares.Push(new Square() { x = 0, y = 1, color = 1 });

...

        squares.Push(CreateSquare(x, y, 1));

Why the discrepancy?

        orientation = Rotate(orientation, color == 0 ? true : false);

condition ? true : false is an unnecessarily long way of writing condition.

    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;

This is precisely the kind of thing that switch statements were invented to handle.

    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }

Don't repeat yourself. This could be refactored as

    if (s == null)
    {
        s = new Square { x = x, y = y, color = 0 };
        squares.Push(s);
    }

    orientation = Rotate(orientation, s.color == 0);
    steps.Add(orientation);
    s.color = 1 - s.color;

            blackSquaresAt100k = squares.Where(sqa => sqa.color == 1).Count();

Count has an overload which takes a condition, so enumerable.Where(foo).Count() can be refactored to enumerable.Count(foo).


Suggestions for improving collection of related PHP functions? I am working on a Web chat application. In the app, users can run commands (such as /nick, /msg, etc) by starting with a / and then typing the command followed by parameters. For example, if someone wanted to change their username to "foobar", they would enter this in:

/whois foobar

However, I cannot think of a good way to organize the code for this. This is what I have so far:

In User.php

function User_command(array $args)
{
   $command = $args['command'];
   list($command_name, $command_parameters) = explode(' ', $command, 2);
  $command_name = str_replace('/', '', strtolower($command_name));

$result = Command::process($command_name, $command_parameters);

if (!$result)
    return responseFailure();

addQueueEntry($result['json'], $result['user_id'], $result['room_id'], $result['added_by']);
return responseSuccess();
}

* In Command.php *

class Command
{
public function process($command, $parameters)
{
    $method = 'MinteCommand_' . $command;

    if (function_exists($method))
        return $method($parameters);

    return null;
}
}

/* Note: When implementing commands, you must specify all fields for $response */
/*       If you don't, then they might not work correctly or as intended. */

function MinteCommand_notice($message)
{
$response = array();
$response['json'] = array('addChatNotice' => $message);
$response['user_id'] = null;
$response['room_id'] = MINTE;
$response['added_by'] = SYSTEM;

return $response;
}

function MinteCommand_announce($message)
{
$response = array();
$response['json'] = array('addChatAnnouncement' => $message);
$response['user_id'] = null;
$response['room_id'] = MINTE;
$response['added_by'] = SYSTEM;

return $response;
}

function MinteCommand_announcement($message)
{
// Command "announcement" is an alternative spelling for command "announce"
return MinteCommand_announce($message);
}

function MinteCommand_clear($message)
{
$response = array();
$response['json'] = array('clearChat' => $message);
$response['added_by'] = SYSTEM;
$response['user_id'] = MINTE;
$response['room_id'] = null;

return $response;
}

function MinteCommand_whois($username)
{
$response = array();
$response['added_by'] = 'SYSTEM';
$query = DB::query('SELECT ip_address, user_agent, last_activity, room_id FROM mt_users
    WHERE username = ? LIMIT 1', $username);

$exists = $query['num_rows'] > 0;
$ip_address = $user_agent = $last_activity = $room_id = "";

if ($exists)
{
    $row = $query['rows'][0];
    $ip_address = $row['ip_address'];
    $user_agent = $row['user_agent'];
    $last_activity = $row['last_activity'];
    $room_id = $row['room_id'];
}

$response['json'] = array('addChatNotice' => !$exists ? 'User ' . $username . ' does not exist' :
    '[' . $username . '] ' . $ip_address . '/' . $user_agent . ', last_activity=' . $last_activity . ', room_id=' . $room_id);

$response['added_by'] = SYSTEM;
$response['user_id'] = MINTE;
$response['room_id'] = null;

return $response;
}

function MinteCommand_msg($args)
{
    list($username, $message) = explode(' ', $args, 2);
}

How can I go about improving the code and making it more organized and elegant? In total there will be around 30 commands.

Just an idea, but maybe this will help you from a manageability point of view:

 public function process($command, $parameters) {
      $method = 'MinteCommand_' . $command;
      $methodFile = dirname(__FILE__) . 'commands/' . $method . ".php";
      if (file_exists($methodFile)) {
            require_once($methodFile);
            if (function_exists($method)) {
                 return $method($parameters);
            } else {
                 throw "invalid function";
            }
      } else {
            throw "invalid function file";
      }
 }

The only benefit to this is that you simply create a new file with the new command (function) inside of that file and it'll automatically search for it if the command is issued.  One caveat will be the limit on the number of commands you can have is a limit on the number of files you can have in a single directory on the filesystem...

Note The code may not be perfect from a syntax point of view.  It's just to give you the general idea / concept.