Transpose a large matrix in Python3 I want to transpose this matrix input:

1.000 2.00 3.0 4.00
5.00 6.000 7.00000 8.0000000
9.0 10.0 11.0 12.00000

And get this output:

1.000 5.00 9.0
2.00 6.000 10.0
3.0 7.00000 11.0
4.00 8.0000000 12.00000

I have a matrix in a file with thousands of lines and millions of columns, so I can't read it into memory (i.e. numpy.transpose is not an option). I have written the solution below, which is very memory efficient, but terribly slow.

import sys
import os

def main():

    path_in = sys.argv[-1]
    path_out = os.path.basename(path_in)+'.transposed'
    separator = ' '

    d_seek = {}
    with open(path_in) as fd_in:
        i = 0
        print('indexing')
        while True:
            tell = fd_in.tell()
            if fd_in.readline() == '':
                break
            d_seek[i] = tell
            i += 1
        print('indexed')
    cols2 = rows1 = i

    with open(path_in) as fd_in:
        line = fd_in.readline()
    rows2 = cols1 = len(line.split(separator))
    del line

    with open(path_in) as fd_in, open(path_out, 'w') as fd_out:
        print('transposing')
        for row2 in range(rows2):
            print('row', row2)
            for row1 in range(rows1):
                fd_in.seek(d_seek[row1])
                s = ''
                while True:
                    char = fd_in.read(1)
                    if char == separator or char == '\n':
                        break
                    s += char
                d_seek[row1] += len(s)+1
                if row1+1 < rows1:
                    fd_out.write('{} '.format(s))
                else:
                    fd_out.write('{}\n'.format(s))

    return

if __name__ == '__main__':
    main()

How can I make it faster? The slow parts are seek and read.

Additional information:

The fields do not have fixed widths, but I know that a field is always an integer or a float and always between 1 and 5 characters and always belonging to the closed interval [0:2]. The field widths differ between lines.

Fixed size value in binary file

It is not a problem if you have binary file with fixed size data.

In this case all you need is to copy your input file into output (or any other way of allocation equal amount of data) and then make file.seek to next value you need to write.

Maybe it will be faster to change reading curstor instead of writing cursor, it this case you have no need to preallocate large sized file, just add to the end off file.

Varies size value in text file

Have no idea how to implement than in memory and perfomance efficient way.

So if you can make some restrictions on input data, let it be binary file, in other case try to find out some other restrictions that, perheps, give you some advatages.

BTW: if it wont be critical you can try converting file from text to binary for transposing and back to text after that.

Explaining

Lets look at the followig matrix

$$
A = \left[ \begin{array}{ll}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{array}\right] $$

$$
A^T = \left[ \begin{array}{ll}
a_{11} & a_{21} \\
a_{12} & a_{22}
\end{array}\right]
$$

Your source file contain matrix \$A\$, while your destination file should contain \$A^T\$.

To write data into destination file in direct order you should jump over source file to read each element from current column.

# ROW_OFFSET length of row in binary file
# NUMBER_OF_ROWS in source file
# DATA_TYPE_SIZE
# current_column while looping all columns
for current_line in range(NUMBER_OF_ROWS):
    sourceFile.seek(current_column * DATA_TYPE_SIZE + ROW_OFFSET * current_line)
    destinationFile.write(sourceFile.read(DATA_TYPE_SIZE))


Detecting Tic-Tac-Toe win: Enumerate all possibilities or use nested loops? Currently I have a game that does this and then checks for victory conditions in victoryTable

victoryTable[0] = rows[0][0] + rows[0][1] + rows[0][2];
victoryTable[1] = rows[1][0] + rows[1][1] + rows[1][2];
victoryTable[2] = rows[2][0] + rows[2][1] + rows[2][2];
victoryTable[3] = rows[0][0] + rows[1][0] + rows[2][0];
victoryTable[4] = rows[0][1] + rows[1][1] + rows[2][1];
victoryTable[5] = rows[0][2] + rows[1][2] + rows[2][2];
victoryTable[6] = rows[0][0] + rows[1][1] + rows[2][2];
victoryTable[7] = rows[0][2] + rows[1][1] + rows[2][0];

But I am considering changing it to read this way:

for (int i = 0; i < 8; i++ ) {
    for (int n = 0; n < 3; n++) {
        for (int t = 0; t < 3; t++) {
            victoryTable[i] = rows[n][t] + // based on some combination of n,t and
                                       // if statement to filter out garbage/duplicates,
                                       // the more I think about this implementation the
                                       // more complicated it seems.
        }
    }
}

Would this be a step in the wrong direction?  It seems like I should put the things that change in a method or loop or something, but it also looks like this will make it harder to read what the code does, and have more potential for bugs (undesired conditions, etc) but also more expandability (if game board became larger in future version, for instance.

The larger context is this:  This is part of a method that determines the victory state of a Tic Tac Toe game.  In a 3x3 int[][], player X is represented by a 3, player O by a 30.  The code in this post adds each column, row, and diagonal, and stores them in an array.  Another method loops through that array and if any element equals 90, O wins, if it equals 9, X wins, otherwise nobody wins (yet).

Without an advanced math degree, I think this is a perfectly reasonable solution.  Here's a sample implementation.  It's not that complicated.  Basically, for every WIN_CONDITION that exists (each of which is a set of coordinates on the board), we check that sequence and see if the Marks are all the same.  If so, that player has won.

I don't think that's a step in the wrong direction.  It's perfectly logical and functional.

Now if it was a more vast game like Connect Four... looping through each variation might be a better option that explicitly listing each win condition, obviously.  But since Tic-Tac-Toe has such a small set, this is fine and makes the code pretty readable.

private static Mark[][] board = new Mark[3][3];

private static final int[][][] WIN_CONDITIONS = {
    //Rows
    {{ 0, 0 }, { 0, 1 }, { 0, 2 }},
    {{ 1, 0 }, { 1, 1 }, { 1, 2 }},
    {{ 2, 0 }, { 2, 1 }, { 2, 2 }},

    //Columns
    {{ 0, 0 }, { 1, 0 }, { 2, 0 }},
    {{ 0, 1 }, { 1, 1 }, { 2, 1 }},
    {{ 0, 2 }, { 1, 2 }, { 2, 2 }},

    //Diagonals
    {{ 0, 0 }, { 1, 1 }, { 2, 2 }},
    {{ 2, 0 }, { 1, 1 }, { 0, 2 }}
};

// other stuff, like an enum for Mark (Mark.X and Mark.O) and the GameState

private GameState checkWinConditions() {

    GameState won = null;

    for(int[][] condition : WIN_CONDITIONS) {
        Mark comparator = board[condition[0][0]][condition[0][1]];
        if(comparator == null) continue;

        won = comparator.getWinState();
        for(int[] coordinate : condition) {
            if(board[coordinate[0]][coordinate[1]] != comparator) {
                won = null;
                break;
            }
        }
        if(won != null) break;
    }
    return won;
}


Find fibonacci series upto a given maximum in javascript I'm attempting to find a fibonacci series where the last number is no greater than a given maximum. Given the start digits 1, 2

Here's my working code.

var fib = [1,2];
var max = 4000000;
var i = 2;
var loop = true

while (loop) {
    if (fib[i-1] + fib[i-2] > max) {
        loop = false;
    } else {
        fib.push(fib[i-1] + fib[i-2]);
        i++;
    }
}

console.log(fib)

Your loop can be terminated in a few different ways. You're using a boolean loop variable, but there are cleaner ways.

One is to simply move the if condition to the while condition (Malachi's answer beat me to this):

while (fib[i-1] + fib[i-2] <= max) {
  i = fib.push(fib[i-1] + fib[i-2]);
}

push helpfully returns the array's new length, so you don't need the i++.

Another is to keep the if branching, but use it to break the loop instead:

while (true) {
  var next = fib[i-1] + fib[i-2];
  if (next > max) {
    break; // exit the loop
  }
  i = fib.push(next);
}

Here we avoid calculating the new fibonacci number twice, but still: the previous code block is probably still the cleanest.

You also initialize i to 2, which is a bit redundant: It's the length of the fib array. Rather than manually initializing the array, and manually recording its length, I'd just do var i = fib.length.

Lastly, it might be good to consider "bad" max values. I.e. what if the maximum is set to zero? Or 1? Or -2324359? For zero you could return an empty array; for 1 you'd need to return a shorter array than what you start with, and for the negative max you could throw an error or return null. Not saying you need to any of this, but it's always to good to consider how you handle such cases.


Get string truncated to max length This is an extension method to get a string that is truncated to a maximum length.

Any comments?

public static class StringExtensions
{
    public static string WithMaxLength(this string value, int maxLength)
    {
        if (value == null)
        {
            return null;
        }

        return value.Substring(0, Math.Min(value.Length, maxLength));
    }
}

If you're using C# 6.0, I believe you can drop the null-check:

public static string WithMaxLength(this string value, int maxLength)
{
    return value?.Substring(0, Math.Min(value.Length, maxLength));
}

Other than that, it's like Jeroen said: that's pretty much as good as it gets.

The class and parameter naming is exactly as I'd have it, and the name of the extension method is decent, although I'd try to find a name that better indicates that truncation will occur when value is longer than maxLength... but WithMaxLength isn't a bad name.


'Reverse a number' function Problem description:

Given a 32-bit signed integer, reverse digits of an integer.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: \$[−2^{31},  2^{31} − 1]\$. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

My solution:

var reverse = function(x) {
    temp = (x < 0) ? -1 : 1;
    x = x * temp;
    let res = x % 10;
    while(x > 9) {
        x = (x - x % 10) / 10;
        res = 10 * res + x % 10;
    };
    res = ((res < 2147483648) && (res >= -2147483648)) ? res : 0;
    return res * temp;
};

console.log(reverse(-321));
console.log(reverse(1534236469));

Test:
Input #1: -321
Expected #1: -123

Input #2: 1534236469
Expected #2: 0

Test summmary:
Solution accepted
Runtime: 88ms

Question: Is there a way to make this function less complex, maybe also improving its runtime?

A simple and clear approach would be to take an array of characters of the number, and reverse the array:

const reverse = function(inputNum) {
    const result = Math.sign(inputNum) * String(Math.abs(inputNum))
      .split('')
      .reverse()
      .join('');
    return result < -2147483648 || result > 2147483647 ? 0 : result;
};
console.log(reverse(-321));
console.log(reverse(1534236469));

The runtime is a little bit higher (92ms, not sure how precisely reliable the measurements are on LeetCode, they seemed all over the place), but in the vast majority of real-world situations, to write strong and maintainable code, one should first optimize clarity and readability, and then if the whole app isn't running as fast as would be ideal, run a performance test to identify bottlenecks and work on those particular bottlenecks.
Note the use of Math.sign to determine whether the number is positive or negative - it'll return -1 if the number is negative, and 1 if the number is positive, so it's probably a bit more appropriate for the situation.
Another approach without creating an intermediate array would be
let res = '';
for (let i = inputStr.length - 1; i >= 0; i--) res += inputStr[i];

With regards to your code:
Always declare your variables You're implicitly creating a global variable temp. Implicit creation of global variables will cause odd bugs when a function gets called when it's already in the process of running. Consider using a linter or strict mode or both to avoid these sorts of mistakes. (When declaring variables, prefer const, or use let when it needs to be reassigned.) On a similar note, your reverse function should be declared with const (not var).
Give variables meaningful names An argument named x and a variable named temp aren't very informative at a glance. How about calling them inputNum and sign instead?


Cleaning address line data sent to couriers API I've developed a client library to integrate with a couriers shipping API. The courier only accepts a limited set of characters for addresses, so I've created a helper class to strip out invalid characters and optionally replace them (with for example a ?).

public static class StringCleaner
{
    private static readonly char[] ValidCharacters =
    {
        ' ', '#', '&', '\'', '(', ')', '+', ',', '-', '.', '/',
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
        ':', '?', '@',
        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
        'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
        '[', ']', '_', '`',
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
        'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
        '{', '|', '}', '~',
    };

    public static string CleanString(string stringToClean, string replacement = "")
    {
        int length = stringToClean.Length;
        var newString = new StringBuilder();
        for (var i = 0; i < length; i++)
        {
            if (ValidCharacters.Contains(stringToClean[i]))
            {
                newString.Append(stringToClean[i]);
            }
            else
            {
                newString.Append(replacement);
            }
        }

        return newString.ToString();
    }
}

First I'd think about names. Isn't Clean() enough for a method inside a class named StringCleaner? Do you need to repeat String?

Still in the prototype you should consider that you're iterating char but replacement is a string. It might be (or not) something to consider, it depends on your requirements.

More about char and string: you're iterating char (which is an UTF-16 code unit). UTF-16 is not fixed size then you're breaking for code points which are not encoded as a single code unit. More about Unicode: not every character is a single code point: you're breaking for surrogates. String might be (or not) normalized, do you need to take care about  it? One grapheme may be represented using two or more code points: think about, for example, ộ Vietnamese character. You may read How can I perform a Unicode aware character by character comparison?

For now let's assume that to iterate char is perfectly fine. If not then read an almost ready to use example in Split a string into chunks of the same length.

In .NET strings are immutable then reading String.Length in a loop is perfectly fine and compiler is capable to optimize it. You already know the maximum length of the string then you may preallocate the StringBuilder buffer to the maximum capacity:

var newString = new StringBuilder(stringToClean.Length);

foreach will help to make code shorter and easier to follow:

foreach (var c in stringToClean)
{
    if (ValidCharacters.Contains(c))
    {
        newString.Append(c);
    }
    else
    {
        newString.Append(replacement);
    }
}

If replacement can be a char it's even easier:

foreach (var c in stringToClean)
    newString.Append(ValidCharacters.Contains(c) ? c : replacement);

You may want to see a LINQ version (in case you find it more readable):

new String(stringToClean.Select(c => ValidCharacters.Contains(c) ? c : replacement));

Performance

In general you should be careful with parameters with a default value, in this case also because of performance. If you add an overload for the common case then you can write:

public static string CleanString(string stringToClean)
    =>  new String(stringToClean.Where(ValidCharacters.Contains(c)));

Searching each character inside the array is something terribly slow. First approach: HashSet<char>. Build the list and search inside the hashed collection. It's WAY faster.

We're talking about true/false values and all valid characters are inside the 7 bit ASCII range...if performance really matters you may use a BitVector. Unfortunately default implementation throws ArgumentOutOfRangeException if you ask for a value outside the assigned range; if you do not want to create a vector of 2^16/8 bytes then you may write your own implementation (see for example Count items existing in 2 Lists for a quick and dirty comparison).


C++ For Euler Problem 3 Here's my solution for Euler Problem 3:

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

I'm using the Euler problems to learn some basics of C++. Are there any C++ "conventions" I'm missing, or any languages features I could use to get a better understanding of C++?
#include <iostream>
#include <vector>
#include <algorithm>

#include "fibonacci.h"
#include <limits>

int get_prime_above(int i);

bool is_prime(int number);

bool has_decimals(float number);

int main() {

    // What number are we getting the prime factors for?
    long target_number = 600851475143;

    // Holds the prime factors.
    std::vector<int> primes;

    // No point dividing by 1, it's a useless factor in this context.
    int current_prime = get_prime_above(1);
    while (target_number > 1) {
        // Does the target divide by the prime evenly?
        long result = target_number % (long) current_prime;
        if (result != 0) {
            // If not, move on to the next prime.
            current_prime = get_prime_above(current_prime);
            continue;
        }

        // If it does, push the prime
        primes.push_back(current_prime);
        // Change the target number to what ever is left to work out
        target_number = (long) target_number / (long) current_prime;
        // And reset the prime.
        current_prime = get_prime_above(1);
    }

    // Sort and reverse the primes,
    // so the highest will be at index 0
    std::sort(primes.begin(), primes.end());
    std::reverse(primes.begin(), primes.end());

    std::cout << "Largest prime: " + std::to_string(primes[0]) << std::endl;
}

/**
 * Get the next prime number above i.
 * @param i
 * @return
 */
int get_prime_above(int i = 1) {
    // Current number we're checking.
    int current_number = 0;
    while (current_number < std::numeric_limits<int>::max()) {

        // If it's lower than what the user wants, just keep incrementing.
        if (current_number <= i) {
            current_number++;
            continue;
        }

        // If it's prime, return it.
        if (is_prime(current_number)) {
            return current_number;
        }

        current_number++;
    }
    throw std::runtime_error("Couldn't find a prime within the int maximum value");
}

/**
 * Is the given number a prime?
 * @param number
 * @return bool
 */
bool is_prime(int number) {
    // Loop all the numbers between (not inclusive of) 1 and number
    // as we know that 1 and number will always have no decimal.
    // If number is 7, it would loop 2..6
    for (int tmp = number - 1; tmp > 1; tmp--) {
        // Divide the number
        float result = ((float) number / (float) tmp);

        // If the result has decimals, it doesn't divide equally
        // so return false.
        if (!has_decimals(result)) {
            return false;
        }
    }

    // All the in between numbers had decimals, so it's a prime.
    return true;
}

/**
 * Is this number a decimal?
 * If converting the float to an int and back again changes the value,
 * then the int conversion removed some decimals.
 * @param number
 * @return bool
 */
bool has_decimals(float number) {
    return number != (float) (int) number;
}

I tried this in VS2019 and I needed to #include <string> in order to compile.

Then I get a warning for the line

long product_of_primes = 600851475143;

which says

  truncation from __int64 to long

which means that long is not enough to hold that number. Since it's positive, I changed that to unsigned long long.

For the remaining review, I'll go through your code from top to bottom, trying to understand it. Whenever I find something, I'll point it out.

If you change

  // Holds the prime factors.
  std::vector<int> primes;

to

std::vector<int> prime_factors;

you can get rid of the comment and the variable becomes self-explaining.

The method

int get_prime_above(int i = 1)

IMHO should not support a default value. As you see in your code, you're calling it with

int current_prime = get_prime_above(1);

and seeing a call with the default value

int current_prime = get_prime_above();

would not make sense to the reader.

Another open question is: which prime above i will the method return? Just any? The next? At this point of understanding and from the comment, I'd propose the name

next_prime_after(int i)

At the same time, I'd change the parameter i to minimum.

I stumbled over the line

while (target_number > 1) {

because I was expecting some other number increasing towards that target. However, your code reduces target_number to become 1. Given that target_number is a product of prime numbers, I would call it product_of_primes instead. Again, you can now remove the comment for that variable.

Again, you need a comment to explain what a variable means:

// Does the target divide by the prime evenly?
long result = product_of_primes % (long)current_prime;

Note that the comment asks a yes/no question, which is why I would expect a boolean. However, the result is a long. Also, the cast to (long) seems redundant. My proposal:

bool is_divisor = 0 == product_of_primes % current_prime;

This also changes the conditional statement to

if (!is_divisor) {

so the comment here is redundant, so it can be removed:

// If not, move on to the next prime.
current_prime = next_prime_after(current_prime);

In order to simplify the branch we have now:

if (!is_divisor) {
    current_prime = next_prime_after(current_prime);
    continue;
}

you can initialize current_prime to 1 and then call next_prime_after() at the beginning of the loop like this:

int current_prime = 1;
while (product_of_primes > 1) {
    current_prime = next_prime_after(current_prime);
    bool is_divisor = 0 == product_of_primes % current_prime;
    if (!is_divisor) continue;
    ...
    current_prime = 1

product_of_primes = (long)product_of_primes / (long)current_prime;

This IMHO has redundant casts and can be simplified to

product_of_primes = product_of_primes / current_prime;

   This, however, will change the result from 71 to the correct value expected by Project Euler to complete the challenge.

current_prime = 1;

IMHO, you don't need to restart at the beginning, since you'll not find prime factors lower than the one you already found.

However, it will not change performance significantly.

Instead of reversing

std::reverse(prime_factors.begin(), prime_factors.end());

you can simply get the last element of the vector

std::cout << "Largest prime: " + std::to_string(prime_factors.back()) << std::endl;

or (my preferred option in this case) sort in descending order

std::sort(prime_factors.begin(), prime_factors.end(), std::greater<int>());

---- Dunno, the horizonal rulers stop working in this line

Woah, this is ugly:

if (current_number <= minimum) {
  current_number++;
  continue;

This can simply be replaced by

int current_number = minimum + 1;

And in consequence the loop can be re-written as

int next_prime_after(int minimum) {
    int current_number = minimum + 1;
    while (!is_prime(current_number)) {
        current_number++;
    }
    return current_number;
}

In that same method, we probably get a performance benefit of a factor of 2 if you move to odd numbers.

int next_prime_after(int minimum) {
    int current_number = minimum + 1;
    current_number += minimum % 2; // ensure odd number
    while (!is_prime(current_number)) {
        current_number += 2;
    }
    return current_number;
}

A had a WTF moment here:

float result = ((float)number / (float)tmp);
// If the result has decimals, it doesn't divide equally
// so return false.
if (!has_decimals(result)) {

Why? Because you already did a proper divisability check somewhere else (cited from the original code):

// Does the target divide by the prime evenly?
long result = target_number % (long) current_prime;

That way, you can get rid of the whole method has_decimals().

for (int tmp = number - 1; tmp > 1; tmp--) {

When you learned dividing numbers in school, did you start by dividing an arbiotrary number like 56 by it's predecessor 55 to check if it is a prime factor? Certainly not. So let's not do it in your code as well. Go simple: check if 56 is divisable by 2.

Oh, and BTW: if you can't divide 56 by 2, you can also not divide it by anything > 28, right? Make a huge performance impact of a factor ~10.

bool is_prime(int number) {
    for (int divisor = 2; divisor < number/2; divisor++) {
        bool is_divisor = 0 == number % divisor;
        if (is_divisor) {
            return false;
        }
    }
    return true;
}

This could be reduced to sqrt(2) instead of number/2 if you think about it.

Starting at 3 and testing odd numbers only will increase by another factor of 2:

bool is_prime(int number) {
    if (number % 2 == 0) return false;
    for (int divisor = 3; divisor < number/2; divisor+=2) {
        bool is_divisor = 0 == number % divisor;
        if (is_divisor) {
            return false;
        }
    }
    return true;
}

For this Project Euler question, int prime factors see to be good enough. For general purpose factorization, you should consider at least long.

My final proposal for you

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include "fibonacci.h"
#include <limits>

int next_prime_after(long minimum);
bool is_prime(long number);

int main() {

    unsigned long long product_of_primes = 600851475143;
    std::vector<int> prime_factors;

    int current_prime = 1;
    while (product_of_primes > 1) {
        current_prime = next_prime_after(current_prime);
        bool is_divisor = 0 == product_of_primes % current_prime;
        if (!is_divisor) continue;

        prime_factors.push_back(current_prime);
        product_of_primes = product_of_primes / current_prime;
        current_prime--;
    }

    std::sort(prime_factors.begin(), prime_factors.end(), std::greater<int>());
    std::cout << "Largest prime: " + std::to_string(prime_factors[0]) << std::endl;
}

/**
 * Get the next prime number above minimum.
 * @param minimum
 * @return
 */
int next_prime_after(long minimum) {
    long current_number = minimum + 1;
    current_number += minimum % 2; // ensure odd number
    while (!is_prime(current_number)) {
        current_number += 2;
    }
    return current_number;
}

/**
 * Is the given number a prime?
 * @param number
 * @return bool
 */
bool is_prime(long number) {
    if (number % 2 == 0) return false;
    for (long divisor = 3; divisor < number/2; divisor+=2) {
        bool is_divisor = 0 == number % divisor;
        if (is_divisor) {
            return false;
        }
    }
    return true;
}

Summary

I hope you agree with my proposals and see that the resulting code is

easier to read
bug fixed
faster by a factor of ~100 (measured using QueryPerformanceCounter())


Testing whether characters of a string are unique Critiques (even pedantic ones) are welcome.

bool unique_chars(std::string &s) {
    if (s.length()>256) return false;
    std::bitset<256> bs;
    for (auto &c:s) {
        if (bs.test(c)) return false;
        bs.set(c);
    }
    return true;
}

EDIT 1:

for (auto &c:s) {         //OLD
for (unsigned char c:s) { //NEW

Reasoning:

char can be either signed or unsigned
if signed then bs[] can be out of bounds
casting to unsigned eliminates issue as negative values will wrap

EDIT 2:

This string is to be made up of characters from the standard ASCII character set, i.e. fitting into a 1 byte char.

EDIT 3:

Renamed function / added test harness with examples. Function parameter changed to const, as string not being modified.

#include <iostream>
#include <bitset>

bool areCharsUnique(const std::string &s) {
    if (s.length()>256) return false;
    std::bitset<256> bs;
    for (unsigned char c:s) {
        if (bs.test(c)) return false;
        bs.set(c);
    }
    return true;
}

int main() {
    std::string s1 = "hi there";
    std::string s2 = "hey man";
    std::cout << areCharsUnique(s1) << std::endl; //0
    std::cout << areCharsUnique(s2) << std::endl; //1
   return 0;
}

@Wayne Conrad has made some good points.  I just have a few additional ones:

I'm not sure about checking against a maximum value, but I'll address it anyway.

In case you'd like to change the default 256, consider having a template parameter.  That way, the value can be changed at just one location.  It'll also give more meaning to that value.

template <std::size_t maxChars = 256>
bool unique_chars(std::string &s) {
    if (s.length() > maxChars) return false;
    std::bitset<maxChars> bs;

    // ...
}

To slightly add on to Wayne's point about const, make sure the argument is const& so that no unnecessary copying is done.  In addition, declaring the string argument as const will allow it to be passed in while avoiding casting.
Consider renaming the function to something like areUniqueChars().  Otherwise, it may sound like it's returning the number of unique chars.
In C++, prefer to put unary operators (such as & and *) next to the type:

std::string& s;

for (auto& c : s) {}


Count Acute, Right and Obtuse triangles from n side lengths Problem Statement: We have \$N\$ sticks. The size of the \$i\$th stick is \$A_i\$. We want to know the number of different types of triangles created with each side from a single different stick. Calculate the number of acute triangles, right triangles and obtuse triangles.

Input Format: The first line contains \$N\$. The second line contains \$N\$ integers. The \$i\$th number denotes \$A_i\$.

Constraints:

For full score: \$3 \le N \le 5000\$
For 40% score: \$3 \le N \le 500\$

For all test cases:

\$1 \le A[i] \le 10^4\$
\$A[i] \lt A[i+1]\$ where \$1 \le i \lt N\$

Output Format: Print 3 integers: the number of acute triangles, right triangles and obtuse triangles, respectively.

My Solution: My code runs in the given time for small \$n\$ (~500). It will work for large \$n\$ (~5000) but I get time limit exceeded error on the Online Judge.

using System;

namespace CodeStorm
{
    class Triangles
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] A_temp = Console.ReadLine().Split(' ');
            int[] A = Array.ConvertAll(A_temp, Int32.Parse);
            int[] A_sq = new int[n];

            for (int i = 0; i < n; i++)
            {
                A_sq[i] = A[i] * A[i];
            }

            int n_m_2 = n - 2;
            int n_m_1 = n - 1;

            int acute = 0, right = 0, obtuse = 0;
            for (int i = 0; i < n_m_2; i++)
            {
                for (int j = i + 1; j < n_m_1; j++)
                {
                    int k = j + 1;
                    int AiPlusAj = A[i] + A[j];

                    while (k < n)
                    {
                        int squareSum = A_sq[i] + A_sq[j];
                        if (AiPlusAj <= A[k])
                        {
                            break;
                        }
                        else if (squareSum > A_sq[k])
                        {
                            acute++;
                        }
                        else if (squareSum < A_sq[k])
                        {
                            obtuse++;
                        }
                        else
                        {
                            right++;
                        }
                        k++;
                    }
                }
            }
            Console.WriteLine(acute + " " + right + " " + obtuse);
            Console.ReadLine();
        }
    }
}

The above code runs perfectly and finds the possible triangles.

Input:

6
2 3 9 10 12 15

Output:

2 1 4

The possible triangles are:

  Acute triangles: 10−12−15, 9−10−12

  Right triangle: 9−12−15

  Obtuse triangles: 2−9−10, 3−9−10, 3−10−12, 9−10−15

I want to know a more efficient way to approach the problem so that I can get it executed in the given time limit for \$n\$ (~5000). After I tried to find the complexity, I came up with \$O(n^3)\$. I am not good with complexities. I might be wrong. I would like a more efficient way for the problem.

Sort your sticks by length; square them when already sorted. Then replace the innermost loop with 3 binary searches. In pseudocode,

        max_obtuse = upper_bound(A[j:n], A[i] + A[j])
        max_right = upper_bound(A_sq[j:n], A_sq[i] + A_sq[j])
        max_acute = lower_bound(A_sq[j:n], A_sq[i] + A_sq[j])

        obtuse += max_obtuse - max_right
        right += max_right - max_acute
        acute += max_acute - j

That reduces the execution time from \$O(n^3)\$ to \$O(n^2\log n)\$.

EDIT:

In the sorted array below, values marked as - are strictly less, and values marked as + are strictly greater, than X:

    -----XXXXXXXXXXXXXXXXX++++++++++
         ^                ^
         |                This is upper bound of X
         This is lower bound of X


Simple RabbitMQ client wrapper After reading this question, I've realized that I can do a lot to improve the quality of my question, so I've edited this question quite a bit.

I've been teaching myself F# in my spare time off and on for the last 6 months.  I've finally started getting comfortable enough with the language to feel that a lot of my code could be much better.  The problem is, I don't know what changes to make.

Here's what I'm interested in:

I'm using higher order functions to return functions for interacting with a specific message queue.  Is this a good design.  Would another F# developer feel comfortable with this?
Does this fit the idiomatic style of F#?
If you know RabbitMQ, are there any bugs which I may be creating here.

Here's the context of the little block of code:

I'm doing a lot of experiments with messaging systems and I've been using RabbitMQ as a messaging framework.  There's a .Net library for RabbitMQ but it's written in and for C#.  I can use it in F# but it feels clunky.  I wanted a small wrapper around the RabbitMQ library which which convert it into a more functional interface.  Also, this will hopefully make it very easy to use RabbitMQ in an F# program.

My wrapper handles the following for RabbitMQ:

Connect to a RabbitMQ server
Create a function which will let you read one message from a queue
Create a function which will write a message to a queue
For both 2 and 3, if the queue doesn't exist, the queue will be created (that's the declareQueue)

module Client =
    let connectToRabbitMqServerAt address =
        let factory = new ConnectionFactory(HostName = address)
        factory.CreateConnection()

    let openChannelOn (connection:IConnection) = connection.CreateModel()

    let private declareQueue (channel:IModel) queueName =
        channel.QueueDeclare( queueName, false, false, false, null )

    let private publishToQueue (channel:IModel) queueName (message:string) =
        let body = Encoding.UTF8.GetBytes(message)
        channel.BasicPublish("", queueName, null, body)

    let createQueueReader channel queue =
        declareQueue channel queue |> ignore

        fun () ->
            let ea = channel.BasicGet(queue, true)
            if ea <> null then
                let body = ea.Body
                let message = Encoding.UTF8.GetString(body)
                Some message
            else
                None

    let createQueueWriter channel queue =
        declareQueue channel queue |> ignore
        publishToQueue channel queue

An example use case would be:

// open a connection to a RabbitMQ broker
let connection = connectToRabbitMqServerAt "localhost"
let myChannel = openChannelOn connection

// Connect to a queue for writing
let writeToHelloQueue = createQueueWriter myChannel "hello"

// write the message "Hello, World" to the queue "hello"
"Hello, World" |> writeToHelloQueue

Overall, this code looks very good.  Just two nitpicks here:

Give your function definitions lines to themselves:

let openChannelOn (connection:IConnection) = connection.CreateModel()

Use match statements unless you are checking a boolean value directly:

if ea <> null then
    let body = ea.Body
    let message = Encoding.UTF8.GetString(body)
    Some message
else
    None

Becomes:

match ea with
| null -> None
| _ ->
    let body = ea.Body
    let message = Encoding.UTF8.GetString(body)
    Some message


canonical pattern for transactional library state manipulation In golang I am finding that there is a definite pressure in the language itself and built-in libraries to do things in a canonical way.  Please can someone critically look at these two ways I am considering using to provide transactional synchronisation of state manipulation within a library and provide me with some feedback.

All state manipulation functions of the library (i.e. all but a couple helper functions) would use this pattern and there would be over a dozen non-trivial functions that require transactional operation.  Method 1 is what I would usually have done in C# but the official golang blog almost seems to be implying this is an anti-pattern.

Method 1 - C# lock pattern https://play.golang.org/p/XS14fM_XUg

gobyexample.com/mutexes

package main

import (
    "fmt"
    "sync"
)

type ILibraryState interface {
    DoSomething(arg int) error
}

type LibraryState struct {
    lock *sync.Mutex
    // Some private state
}

func (l *LibraryState) DoSomething(arg int) error {
    // Do some arg check

    // Transactional synchronisation
    l.lock.Lock()
    defer l.lock.Unlock()

    // Do something
    fmt.Println("Hello, playground")
    return nil;
}

func NewLibrary() ILibraryState {
    lib := LibraryState{}
    lib.lock = &sync.Mutex{}
    return &lib
}

func main() {
    l := NewLibrary()
    l.DoSomething(5)
}

Method 2 - Hidden goroutine and single command queue https://play.golang.org/p/3vWQJDswJm

http://gobyexample.com/stateful-goroutines
http://blog.golang.org/share-memory-by-communicating
http://blog.golang.org/advanced-go-concurrency-patterns

package main

import (
    "fmt"
)

type ILibraryState interface {
    DoSomething(arg int) error
}

type LibraryState struct {
    command  chan (interface{})
    response chan (interface{})
    // Some private state
}

type commandDoSomething struct {
    arg int
}

func (l *LibraryState) DoSomething(arg int) error {
    // Do some arg check

    // Perform operation transactionally
    l.command <- commandDoSomething{arg}
    res := <-l.response
    if res == nil {
        return nil
    }
    return res.(error)
}

func (l *LibraryState) reallyDoSomething(arg int) {
    // Do something
    fmt.Println("Hello, playground")
    var err error = nil
    l.response <- err
}

func (l *LibraryState) processCommands() {
    for {
        switch c := (<-l.command).(type) {

        case commandDoSomething:
            l.reallyDoSomething(c.arg)
        }
    }
}

func NewLibrary() ILibraryState {
    lib := LibraryState{}
    lib.command = make(chan (interface{}))
    lib.response = make(chan (interface{}))
    go lib.processCommands()
    return &lib
}

func main() {
    l := NewLibrary()
    l.DoSomething(5)
}

Go does have a strong opinion on the use of mutexes vs. channels. In fact, the sync package states: "Other than the Once and WaitGroup types, most are intended for use by low-level library routines. Higher-level synchronization is better done via channels and communication." (See https://golang.org/pkg/sync/ )

This opinion clearly implies your first implementation is suboptimal. I agree, so I'm not going to even review that implementation.

The second implementation is more intriguing, it uses channels, but it's got issues.... and it's not a "canonical" example of what I would expect with a "communication" implementation for concurrency in Go.

The "Stateful" go-routine is one which only that single go-routine accesses, or modifies the state. All interaction with the state is done by communicating with that routine, and communication happens through channels.

You have one channel to communicate the request for accessing the state, and another for returning the response. This is a problem... The request channel command is OK, but the response channel is broken. If you have multiple concurrent commands issued, you won't be able to send the right response to the right command, and things will get mixed up.

The solution to this is to dedicate a channel for each command to get the responses on. Add the channel to the commandDoSomething struct, so that your code looks something like:

func (l *LibraryState) DoSomething(arg int) error {

    // dedicated response channel for communication (of error type, not interface{})
    resp := make(chan error, 1)

    // Perform operation transactionally
    l.command <- commandDoSomething{arg, resp}
    res := <-response
    return res
}

Now your state handler would look like:

func (l *LibraryState) reallyDoSomething(arg int, respondto chan<- error) {

    defer close(respondto)

    // Do something
    fmt.Println("Hello, playground")
    var err error = nil
    respondto <- err
}

and be called like:

for {
    switch c := (<-l.command).(type) {

    case commandDoSomething:
        l.reallyDoSomething(c.arg, c.respondto)
    }
}

Note that you can remove the l.response channel completely.

Edit: Note that by dedicating a response channel for each command, you can do things like return the actual channel from the DoSomething function, like:

func (l *LibraryState) DoSomething(arg int) <-chan error {

    // dedicated response channel for communication (of error type, not interface{})
    resp := make(chan error, 1)

    // Perform operation transactionally
    l.command <- commandDoSomething{arg, resp}
    return resp
}

and as a consequence, "clients" can call the DoSomething method and then potentially do other work while the state is changing, and get the possible error condition later... like:

resp := DoSomething(input)
//... work on other activities
if err := <-resp; err != nil {
    // handle error - perhaps undo some previous optimistic code....
}


Repetitive jQuery click functions for changing multiple elements I'm using the following code to change elements text and classes when a click event is fired. My question is: Is there a better way to go about doing this that limits how repetitive the functions are? It seems extremely messy and like there would be a better way to go about structuring this.

function updateAveragesDropdown(element, text) {
    // Update text
    $("#timeframe_dropdown_container .dropdown-toggle p").text(text);

    // Remove active class
    $("#timeframe_dropdown_container #dropdown_today").parent("li").removeClass("active");
    $("#timeframe_dropdown_container #dropdown_week").parent("li").removeClass("active");
    $("#timeframe_dropdown_container #dropdown_month").parent("li").removeClass("active");

    // Update nav-tabs
    $("#timeframe_pills_container #tab_today").parent("li").removeClass("active");
    $("#timeframe_pills_container #tab_week").parent("li").removeClass("active");
    $("#timeframe_pills_container #tab_month").parent("li").removeClass("active");

    // Add active class
    $(element).parent("li").addClass("active");
}

function removeDropdownClasses() {
    $("#timeframe_dropdown_container #dropdown_today").parent("li").removeClass("active");
    $("#timeframe_dropdown_container #dropdown_week").parent("li").removeClass("active");
    $("#timeframe_dropdown_container #dropdown_month").parent("li").removeClass("active");
}

function updateDropdownElement(element, text) {
     $(element).parent("li").addClass("active");
     $("#timeframe_dropdown_container .dropdown-toggle p").text(text);
}

// Clear active labels on dropdown menu
$("#timeframe_dropdown_container #dropdown_today").click(function(e) {
    updateAveragesDropdown(this, "Today");
    $("#timeframe_pills_container #tab_today").parent("li").addClass("active");
});

$("#timeframe_dropdown_container #dropdown_week").click(function(e) {
    updateAveragesDropdown(this, "7-Day");
    $("#timeframe_pills_container #tab_week").parent("li").addClass("active");
});

$("#timeframe_dropdown_container #dropdown_month").click(function(e) {
    updateAveragesDropdown(this, "30-Day");
    $("#timeframe_pills_container #tab_month").parent("li").addClass("active");
});

$("#timeframe_pills_container #tab_today").click(function(e) {
    removeDropdownClasses();
    updateDropdownElement("#timeframe_dropdown_container #dropdown_today", "Today");
});

$("#timeframe_pills_container #tab_week").click(function(e) {
    removeDropdownClasses();
    updateDropdownElement("#timeframe_dropdown_container #dropdown_week", "7-Day");
});

$("#timeframe_pills_container #tab_month").click(function(e) {
    removeDropdownClasses();
    updateDropdownElement("#timeframe_dropdown_container #dropdown_month", "30-Day");
});

HTML

Today

7-Day

30-Day

        <button class="btn btn-default dropdown-toggle" type="button" id="timeframe_dropdown" data-toggle="dropdown" aria-haspopup="true" aria-expanded="true">

Today

        </button>

Today

7-Day

30-Day

As far as I can tell, the code simplifies as follows :

$("#timeframe_pills_container li a").click(function(e) {
  var $li = $(this).closest("li");
  var index = $li.index();
  var $dropdown = $("#timeframe_dropdown_container");
  $li.addClass("active").siblings().removeClass("active");
  $dropdown.find("li").eq(index).addClass("active").siblings().removeClass("active");
  $dropdown.find(".dropdown-toggle p").text($(this).text());
}).eq(0).click();

$("#timeframe_dropdown_container li a").click(function(e) {
  var index = $(this).closest("li").index();
  $("#timeframe_pills_container li a").eq(index).click();
});

.eq(0).click() establishes the intial state, so you don't need to set class="active" (twice) or the button text, in HTML.


Morgan and a String HackerRank challenge I am solving a HackerRank problem called 'Morgan and a String'.  Given two strings, each consisting of up to 105 uppercase characters, the task is to form the lexicographically smallest string from those letters by taking the first remaining character from either of the strings at each step.  Example, for input strings "ACA" and "BCF", the answer should be "ABCACF":

Jack    Daniel  Result
ACA     BCF
CA      BCF     A
CA      CF      AB
A       CF      ABC
A       CF      ABCA
        F       ABCAC
                ABCACF

Sample input, with one test case:

1
ACEG
BDFH

Output:

ABCDEFGH

I've solved it by writing my own code which works perfectly on smaller test cases. But when they run it against test cases which are approx 6000 characters long I get a runtime error. How can I increase the efficiency?

n=int(input())#number of pairs to input
for mn in range(n):
    a=input()# String1 in the pair
    b=input()#String2 in the pair
    la=[]
    lb=[]

    for i in range(max(len(a),len(b))):#creating lists with all possible elements by slicing off the characters
        la.append(a[i:])
        lb.append(b[i:])

    if len(a)>len(b):#removes empty elements
        lb=[x for x in lb if x!='']
    else:
        la=[x for x in la if x!='']

    while True:#Create empty list for sorting the 0th elements of 'la' nd 'lb'
        temp=[]
        temp.append(la[0])
        temp.append(lb[0])
        temp=sorted(temp)
        print(temp[0][0],end='')#print the 1st character

        if(temp[0] in la):#removing the element after printing the first character
            la.pop(0)
        else:
            lb.pop(0)

        if len(la)==0:#breaks the while loop if a list gets empty
            print(temp[1],end='')
            break
        elif len(lb)==0:
            print(temp[1],end='')
            break

This is an improvement on @Toby's answer

Instead of str += char which allocates a new string you can yield the result and "".join() it later on

Here's the problem: consider "BAB", "BAC". One would think to compare the two strings, see that BA->B is more minimal than BA->C. or you see that BA->B(end of string) is shorter than BA->(jump to other string)BA. Both of these are wrong, because we end up with BABBAC, instead of BABABC, which is more minimal (BABA < BABB).
The z fixes things because it fixes the issue where we incorrectly choose BA->B\0 over BA(first stack)->(other stack)BA. BA->BA < BA->Bz. Realistically what we should do during tiebreakers is jump to the other stack when one ends so we are comparing against BABB instead of BABz, but the z solution is faster.

Normally with the "z" fix you need to remove them from the end result, but because any uppercase char is lower then the lowercase "z" we know after len(a) + len(b) - 2 iterations only the 2 "z" strings remain in the resulting string. thus we only need to loop len(a) + len(b) - 2 times

Improved code
def morgan(a, b):
    a += "z"
    b += "z"
    for _ in range(len(a) + len(b) - 2):
        if a < b:
            yield a[0]
            a = a[1:]
        else:
            yield b[0]
            b = b[1:]

def morgan_and_string(a, b):
    """
    Return the lexicographically smallest string formed from the input strings, keeping each string
    in order in the result.

    Same length
    >>> morgan_and_string("ACEG", "BDFH")
    'ABCDEFGH'
    >>> morgan_and_string("ABCD", "ABCD")
    'AABBCCDD'

    Empty input
    >>> morgan_and_string("ABCD", "")
    'ABCD'
    >>> morgan_and_string("", "ABCD")
    'ABCD'

    Different length
    >>> morgan_and_string("Z", "ABCD")
    'ABCDZ'
    >>> morgan_and_string("ABCD", "Z")
    'ABCDZ'

    Descending strings
    >>> morgan_and_string("BA", "BA")
    'BABA'

    >>> morgan_and_string("ZAX", "ZAY")
    'ZAXZAY'
    >>> morgan_and_string("ZAY", "ZAX")
    'ZAXZAY'

    Proper prefix
    >>> morgan_and_string("BABC", "BA")
    'BABABC'
    >>> morgan_and_string("CABC", "CA")
    'CABCAC'
    >>> morgan_and_string("BAAC", "BA")
    'BAABAC'
    """
    return "".join(morgan(a, b))

if __name__ == '__main__':
    import doctest
    doctest.testmod()


C# Linq search list within list I am writing a domino draw game in C# and would like to know if there is a simpler/better way to know the player that has been dealt the highest double bone (where x equals y) and what bone it is:

public class Player
{
    public string Name { get; set; }
    public List<Bone> Bones;
    public Player(string name)
    {
        Name = name;
    }
}

public class Bone
{
    public int x { get; set; }
    public int y { get; set; }
}

Code in question (players is a list of player):

//select player with highest double and select the double
var pdb = players.SelectMany(pl => pl.Bones.Where(b => b.x == b.y)
    .Select(b => new { player = pl, doublebones = b }))
    .OrderByDescending(db => db.doublebones.x)
    .First();
Player playerWithHighestDouble = pdb.player;
Bone highestBone = pdb.doublebones;

Welcome to CodeReview.  What you are trying to do is simple enough that your LINQ implementation is okay.  Let's face it, with dominoes you are not going to have a million players with a million bones, so no need to worry about performance issues with a fairly small set.

You didn't ask explicitly for review of other parts of code, but I will offer them anyway.

Name could be a read-only property set only in the constructor.

You have Bones as a field, not a property.  It could be exposed as a public IReadOnlyList, and it probably should be a property.

Bone could be a struct or a class since it only has 2 int properties.  I do not like the names X and Y as I tend to think of Cartesian coordinates and therefore a location.  I would prefer to see names like Square1 and Square2.  I would probably keep this as a class and make the properties readonly as well.  You may consider adding extra properties such as IsDouble, and even override ToString() with $"{Square1}-{Square2}", and maybe even Pips which is a sum of both squares.

As you are new to CR, since I have posted an answer, do NOT alter your code in your question or else a moderator will roll it back.


Command line utility to output modified Markdown What this command line utility does is to take a text file and update the content a bit before turning it into Markdown. For example, the first for loop searches all the straight quotes and replace them for curly quotes. The second loop searches for hr tags and replace them for * * *, then adds the noind class to the p that follows that hr tag.

#!/usr/bin/env node

var fs = require('fs')
var program = require('commander')
var markdown = require('markdown').markdown

program
  .version('0.0.1')
  .usage('<keywords>')
  .parse(process.argv)

if (!program.args.length)
  program.help()

var filename = program.args[0]

fs.readFile(filename, 'utf8', function(err, data) {
  if (err) throw err

  var tree = markdown.parse(data)

  ;(function updateTree(jsonml) {

    // replace straight quotes for curly quotes
    for (i = 1; i < jsonml.length; i++) {
      if (typeof jsonml[i][1] === "string" && jsonml[i][1].match(/"/g)) {
        var p = jsonml[i]

        for (j = 1; j < p.length; j++) {
          if (typeof p[j] === "string" && p[j].match(/"/g)) {
            p[j] = p[j].replace(/"(?=\b)/g, "“")
                       .replace(/"(?!\b)/g, "”")
          }
        }
      }

      if (typeof jsonml[i][1] === "string" && jsonml[i][1].match(/'/g)) {
        var p = jsonml[i]

        for (j = 1; j < p.length; j++) {
          if (typeof p[j] === "string" && p[j].match(/'/g)) {
            p[j] = p[j].replace(/'(?=\b)/g, "‘")
                       .replace(/'(?!\b)/g, "’")
          }
        }
      }
    }

    // replace hr for * * * and add noind class to the p tag that follows it
    for (i = 1; i < jsonml.length; i++) {
      if (jsonml[i][0] === 'hr') {
        var hr = jsonml[i]
        var p = jsonml[i + 1]

        hr.splice(0, 1, 'para', '* * *')
        p.splice(1, 0, {'class': 'noind'})
      }
    }
  })(tree)

  var html = markdown.renderJsonML(markdown.toHTMLTree(tree))
  console.log(html)
})

So my question is, how can I reduce the indentation level?

Have you looked at https://github.com/caolan/async? It can really help with organizing your code. As the name implies, async was created to help with writing asynchronous code. While you are only calling one asynchronous function, we can still use it to help us structure our entire program.

Async aside, the general idea is to use functions to help us break down our problem. Instead of a loop within a loop, we can think about what that inner loop is doing and create a function to replace it (for example, our replaceChar function below).

With this in mind and using https://github.com/caolan/async#waterfall, we could write something like:

#!/usr/bin/env node

var fs = require('fs')
var program = require('commander')
var markdown = require('markdown').markdown
var async = require('async');

function printResult(e, r) {
    if (e) {
        throw e;
    }
    else {
        console.log(r);
    }
}

function parseMarkdown(data, cb) {
    cb(null, markdown.parse(data));
}

function replaceChar(node, search, replace) {
    var i;
    var re0 = new RegExp(search + '(?=\b)', 'g');
    var re1 = new RegExp(search + '(?!\b)', 'g');
    for (i = 1; i < node.length; ++i) {
        node[i] = node[i].replace(re0, replace).replace(re1, replace);
    }
    return node;
}

function replaceQuotes(tree, cb) {
    var i;
    for (i = 1; i < tree.length; i++) {
        tree[i] = replaceChar(tree[i], '"', '“');
        tree[i] = replaceChar(tree[i], "'", "‘");
    }
    cb(null, tree);
}

function replaceHr(tree, cb) {
    var i;
    for (i = 1; i < tree.length; i++) {
        if (tree[i][0] === 'hr') {
            var hr = tree[i]
            var p = tree[i + 1]

            hr.splice(0, 1, 'para', '* * *')
            p.splice(1, 0, {'class': 'noind'})
        }
    }
    cb(null, tree);
}

function convertToHtml(tree, cb) {
    cb(null, markdown.renderJsonML(markdown.toHTMLTree(tree)));
}

program
  .version('0.0.1')
  .usage('<keywords>')
  .parse(process.argv)

if (!program.args.length)
  program.help()

var filename = program.args[0]

async.waterfall([
    fs.readFile.bind(fs, filename, 'utf8'),
    parseMarkdown,
    replaceQuotes,
    replaceHr,
    convertToHtml
], printResult);


Laravel 5.4: Authentication System I have recently coded my own authentication system and wondered if there was any way I could make it better? I coded it with Laravel 5.4. getView is called on Route::get and onPost is called on Route::post

use Auth;
use App\User;
use App\Http\Controllers\Controller;
use Validator;
use Redirect;
use Illuminate\Http\Request;
use App\Database\Frontend\User\Player;
use App\Database\Frontend\WebsiteLogin;

class LoginController extends Controller
{
    public function getView()
    {
        return view('frontend.login');
    }

    public function onPost(Request $request)
    {
        $validator = Validator::make($request->all(), [
            'mail'     => 'required|email|exists:users',
            'password'  => 'required'
        ]);

        if ( $validator->fails()) {
            return Redirect::to('/login')->withErrors($validator->messages());
        }
        else {
            if (!Auth::attempt(['mail' => $request->input('mail'), 'password' => $request->input('password')])) {
                $this->addNewWebsiteLogin($request, Player::where('mail', $request->input('mail'))->pluck('id')->first(), "0");
                return Redirect::to('/login')->withMessage('Email and password do not match')->withColor('danger');
            }
            else {
                $this->addNewWebsiteLogin($request, Auth::user()->id, "1");

                $user = Auth::user();
                $user->last_online = time();
                $user->save();

                if (config('frontend.government_only') && (Auth::Guest() || Auth::user()->roleplay->government_id == 0)) {
                    Auth::logout();
                    return Redirect::to('/login')->withMessage(config('frontend.site_name') . ' is only open to government individuals at this moment, too bad.')->withColor('danger');
                }

                return Redirect::to('/home')->withMessage('Welcome back!');
            }
        }
    }

    private function addNewWebsiteLogin(Request $request, $userId, $status) {
        $websiteLogin                    = new WebsiteLogin;
        $websiteLogin->user_id           = $userId;
        $websiteLogin->request_ip        = $request->ip();
        $websiteLogin->request_system    = 'TODO';
        $websiteLogin->request_browser   = 'TODO';
        $websiteLogin->login_status      = $status;
        $websiteLogin->save();
    }
}

You can use Laravel's form requests to keep rules and validation logic out of controllers.


Descending selection sort in JavaScript I wrote a simple sort algorithm in JavaScript, but code climate is complaining its complexity being too high (currently sitting on 6 instead of 5, which is code climate wants).

I personally cannot see how it can be further simplified.

Can anyone help? The following algorithm sorts an array of numbers from largest to smallest.

function selectionSort(array) {
    let index = 0;
    let terminatingIndex = array.length - 1;
    let nextElementIndex = null;

    while (index < terminatingIndex) {
        nextElementIndex = index + 1;
        while (nextElementIndex <= terminatingIndex) {
            if (array[index] < array[nextElementIndex]) {
                [array[index], array[nextElementIndex]] = [array[nextElementIndex], array[index]];
            }
            nextElementIndex++;
        }
        index++;
    }
    console.log(`The sorted array is: ${array}`);
}

I think the problem could be, that your algorithm isn't exactly a selection sort but rater a bubble sort. They are very similar, but where bubble sort swaps every two elements when the left is smaller than the right (descending order), selection sort defers swapping to after the inner loop is finished and then only swaps the last found candidate with the index'th element.

To accomplish that in your algorithm, you can modify it as follows:

function selectionSort(array) {
  let index = 0;
  let length = array.length;
  let nextElementIndex = 0;

  while (index < length - 1) {
    nextElementIndex = index + 1;

    let maxIndex = index; // This will hold the index of the possible last candidate for swapping.

    while (nextElementIndex < length) {
      if (array[maxIndex ] < array[nextElementIndex]) {
        // Instead of swapping here, only the index of the candidate is saved.
        maxIndex = nextElementIndex;
      }
      nextElementIndex++;
    }

    // And finally: if any element to the right of index is greater than the element at index then swap.
    if (maxIndex != index) {
      [array[index], array[maxIndex ]] = [array[maxIndex ], array[index]];
    }

    index++;
  }
}

A suggestion that may improve readability could be to use for-loops instead of while -loops


Split list of integers at certain value efficiently I am working on a python puzzle over at codewars ( Largest Rectangle )  My solution is working for small cases but times out for the very large ones.)  I think one major hit to performance is in my subroutine splitz(arr):

The purpose of this subroutine is something like string.split('X') - but for lists of integers.  In my case, I will always be spllitting at the minimum value on the list, so splitz([3,3,5, 1, 5,5,5, 1, 6,5,4]) should return  [[3,3,5], [5,5,5], [6,5,4]]

def splitz(iterable):
    key = (min(iterable),)
    return [list(g) for k,g in itertools.groupby(iterable,lambda x:x in key) if not k]

My code is adapted from a snippet found on Stackoverflow, and I don't understand it well enough to know how efficient it really is (or not.)  It needs to efficiently deal with lists with len ~= 100,000 that could be splitting up into almost that many sublists.

Is there a better way to do this split, or do I need to find a completely different approach to solving the overall problem?

FULL CONTEXT

The overall task is to identify the largest rectangle that can be made in a grid made from stacked rows of length a[i].  So if a is [7,2,6,4,5,1] the grid looks like

0000000
00
000000
0000
00000
0

largest possible rectangle is shown in H's:

0000000
00
HHHH00
HHHH
HHHH0
0

And the routine should return 12 (=3*4)

This is my third approach.  The first one was a lambda one-liner that was quite compact, but could only handle lists up to about 1000.  My current solution works with long lists on my PC,  (150,000 in 1.5 seconds, 1.5 million in 110 seconds) but fails on codewars.  I don't know how long the longest test case is there, but the time limit is 1.2 seconds.

import itertools

def largest_rect(a):
    maxRect = 0  # This will store the result
    if len(a) == 0:
        return 0
    mina = min(a)

    # The area of a rectangle extending
    # all the way across the the current list,
    # with the maximum possible height (which is the minimum in this list)
    maxRect = len(a) * mina
    # split the current lists into sublist, dividing at the
    # value that limited the height of the previous calc
    newarrlist = splitz(a, mina)

    # Now loop through each of the lists returned when split the original
    keepTrying = True
    while keepTrying:
        tmparrlist = []
        keepTrying = False  # This will be set True if we generate a new sublist
        for thisarr in newarrlist:
            # If the enclosing dimensions of this block aren't bigger
            # than the current largest rectangle, don't bother using it.
            lenta = len(thisarr)
            if lenta * max(thisarr) > maxRect:
                minta = min(thisarr)
                maxRect = max(maxRect, minta*lenta)
                lists = splitz(thisarr, minta)
                # If splitz was given a perfect rectangle, that block is now finished.
                # Otherwise add the sublists to a temporary array.
                if len(lists) > 0:
                    tmparrlist = tmparrlist + lists
                    keepTrying = True  # We stored a sublist - we'll have to repeat

        # Once we have gone through the list of lists, reset to our temporary array
        # and try again until keepTrying = False
        newarrlist = tmparrlist
    return maxRect

# This will split a list into sublists at the minimum value on the original
def splitz(iterable, minin):  # Pass in the min value, since we already know it.
    splitters = (minin, )
    return [list(g) for k, g in itertools.groupby(iterable,lambda x:x in splitters) if not k]

I would use a generator:

def splitz(seq, smallest):
    group = []
    for num in seq:
        if num != smallest:
            group.append(num)
        elif group:
            yield group
            group = []

numbers = [1, 3, 3, 5, 1, 5, 5, 5, 1, 6, 5, 4, 1]
min_val = min(numbers)
print(list(splitz(numbers, min_val)))

It prints:

[[3, 3, 5], [5, 5, 5], [6, 5, 4]]

You could time it:

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("splitz(numbers, min_val)", setup="from __main__ import splitz, numbers, min_val", number=1000000))

On my machine, it is:

1.0186186955428558

Note the default number of times through the loop is one million.


Producing a deep-reverse procedure Exercise 2.27

  Modify your reverse
  procedure of exercise 2.18 to produce
  a deep-reverse procedure that takes a
  list as argument and returns as its
  value the list with its elements
  reversed and with all sublists
  deep-reversed as well. For example,

(define x (list (list 1 2) (list 3
4)))

x ((1 2) (3 4))

(reverse x) ((3 4) (1 2))

(deep-reverse x) ((4 3) (2 1))

I wrote the following:

(define (deep-reverse lis)
  (define (snoc elem lis)
    (if (null? lis)
        (cons elem lis)
        (cons (car lis) (snoc elem (cdr lis)))))
  (cond ((null? lis) lis)
        ((pair? (car lis)) (snoc (deep-reverse (car lis)) (deep-reverse (cdr lis))))
        (else (snoc (car lis) (deep-reverse (cdr lis))))))

(define a (list 1 2 3 4 5 (list 1 2 3 4) (list 5 6 7 8)))

What do you think?

The main problem with using snoc (or append, which your snoc effectively does) is that each call is O(n). This makes your function O(n²), which is (pun intended) deeply problematic.

Here's my O(n) implementation, which is tail-recursive along the cdrs:

(define (deep-reverse l)
  (let loop ((x l)
             (r '()))
    (cond ((null? x) r)
          ((pair? x) (loop (cdr x) (cons (deep-reverse (car x)) r)))
          (else x))))

Here's an even shorter version, using fold (also tail-recursive along the cdrs):

(define (deep-reverse l)
  (define (iter x y)
    (cons (if (pair? x) (deep-reverse x) x) y))
  (fold iter '() l))

For even more fun, an unfold-right version (also tail-recursive along the cdrs); requires compose as well:

(define (deep-reverse l)
  (define (iter x)
    (if (pair? x) (deep-reverse x) x))
  (unfold-right null? (compose iter car) cdr l))


Simulated arcade with a slot machine and number-guessing game I am creating an arcade type thing in Python. Could someone suggest ways to simplify this code, or any other tips? All help is much appreciated.

I think the higherorlower function is particularly over-complicated.

import time
import random
tokens = 10000

def main():
    menu = int(input("What would you like to play?(Enter the corresponding number for each one)\n1. Slot Machine - 20 coins per turn\n2. Higher or Lower - 10 coins per turn\n"))
    if menu == 1:
        slotmachine(tokens)
    if menu == 2:
        higherorlower(tokens)

def tokencheck(cost):
    while True:
        if tokens >= cost:
            break
        else:
            print ("You do not have enough tokens")

def game_end():
    time.sleep(2)
    retry = input("Enter the corresponding letter for each one.\nM. Menu\nQ. Quit the arcade\n")
    if retry == "m" or retry == "M":
        main()
    if retry == "q" or retry == "Q":
        print("BYE BYE!")

def slotmachine(tokens):
    tokencheck(20)
    print ("You are playing slot machine!")
    print ("To win 1000 tokens you need to get 3 of the same number on each shake!")
    while True:
        tokencheck(20)
        shake = input("Press Enter to Shake!")
        tokens -= 10
        a,b,c = [random.randint(0,9),random.randint(0,9),random.randint(0,9)]
        print(a, b, c)
        if a != b or a != c:
            pass
        else:
            print ("You win 1000 tokens!")
            tokens = tokens + 1000
            print ("You now have", tokens, "tokens!")
            break
    game_end()

def higherorlower(tokens):
    goes = 0
    tokencheck(10)
    print ("You are playing higher or lower!")
    time.sleep(2)
    print ("You have to predict whether the next number (from 1 - 10) will be higher or lower than the current number.\nYou get 100 tokens for each round which you predict correctly.\nIf you predict incorrectly you will lose all of your earnings.")
    time.sleep(4)
    print("Cashout by inputting C.\n")
    time.sleep(1)
    num = random.randint(1,10)
    while True:
            tokens+=10
            time.sleep(1)
            print (num)
            choice = input("Higher or Lower (H/L)\n")
            if (choice == "C" or choice == "c") and goes >= 100:
                break
            if (choice == "C" or choice == "c") and goes < 100:
                "Cannot checkout!"
                pass
            else:
                pass
            num1 = random.randint(1,10)
            print (num1)
            time.sleep(1)
            if (num1 >= num and (choice == "H" or choice == "h")) or (num1 <= num and (choice == "L" or choice == "l")):
                print("You are correct and have earned 100 tokens!\n")
                tokens+=100
                num = num1
                goes+=100
                pass
            else:
                print("You are incorrect and have lost all of your earnings")
                tokens -= goes
                time.sleep(1)
                print ("You now have", tokens "tokens remaining.")
                break
    game_end()

print ("Welcome to the arcade!")
time.sleep(0.5)
print("You have", tokens, "tokens remaining.")
time.sleep(1)
main()

slotmachine() and higherorlower() call gameend(). In turn, gameend() may call main(). This is considered "spaghetti code", because functions should not be used as goto labels.

Rather, if your code acts as a loop, then it should be written with a loop, like this:

def main():
    while True:
        menu = int(input("What would you like to play?(Enter the corresponding number for each one)\n1. Slot Machine - 20 coins per turn\n2. Higher or Lower - 10 coins per turn\n"))
        if menu == 1:
            slot_machine(tokens)
        elif menu == 2:
            higher_or_lower(tokens)
        if game_end():
            break

The way you pass tokens is inappropriate. In main(), you are using a global variable tokens. However, in slotmachine() and higherorlower(), there is a local variable coincidentally named tokens, due to the function parameter. Make up your mind whether you want to use a global variable or pass the state around using parameters and return values.


Merging two dictionaries together whilst adding keys but multiplying values I have two dictionaries and a merged dictionary:

dict1 = {-3: 0.3, -2: 0.1, 1: 0.8}
dict2 = {0: 0.3, 1: 0.5, -1: 0.7}
dict_merged = {}

I have code that basically merges the two together by adding keys together and multiplying values:
e.g.

for k1, v1 in dict1.items():
   for k2, v2 in dict2.items():
      new_key = k1 + k2
      if new_key in dict_merged:
          dict_merged[new_key] += v1 * v2
      else:
          dict_merged[new_key] = v1 * v2

Is there a faster way to do this, it feels like there should but dict comprehension doesn't seem helpful here. In the above example, we are going to get several contributes to the key "-3" for example.

It's standard to indent Python with 4 spaces. Not following this standard only makes your life and the life of people that have to interact with you harder.

You can just use the optional default argument to dict.get to remove the need for the if.

for k1, v1 in dict1.items():
    for k2, v2 in dict2.items():
        key = k1 + k2
        dict_merged[key] = v1 * v2 + dict_merged.get(key, 0)

Alternately you can change dict_merged to a collections.defaultdict, rather than a dict. This removes the need to use dict.get, and allows you to just us +=.
defaultdict takes a function that provides the default value to use. Since int() returns 0, we can just pass int as the function. As noted by Ilmari Karonen you can also use float as that returns 0.0 without any arguments.

import collections

dict_merged = collections.defaultdict(int)
for k1, v1 in dict1.items():
    for k2, v2 in dict2.items():
        dict_merged[k1 + k2] += v1 * v2


Encode/decode number pairs to letters My application state is represented by a string of numbers and I'm trying to encode the string so that it is as small as possible (ie. fewest number of characters). An example string would be: 133223333302302040

I realized that most of these strings consist of number pairs containing 0, 1, 2, 3 (4 and 5 also exist but are rare). I decided to replace the most common number pairs with letters, shortening my encoded string by ~50%

I have a function that returns the mapping:

function getValueMap(lettersFirst = false) {
  const map = {
    '00': 'a',
    '01': 'b',
    '02': 'c',
    '03': 'd',
    '10': 'e',
    '11': 'f',
    '12': 'g',
    '13': 'h',
    '20': 'i',
    '21': 'j',
    '22': 'k',
    '23': 'l',
    '30': 'm',
    '31': 'n',
    '32': 'o',
    '33': 'p'
  };

  if (lettersFirst) {
    return Object.fromEntries(Object.entries(map).map(([k, v]) => [v, k]));
  } else {
    return map;
  }
}

To encode, I iterate through every pair of input numbers, check if it is in the map, and if so, add the letter to the encoded output. For odd length inputs I simply remove the last digit, dont encode it, and simply append the number to the output string untouched:

encode(text) {
  const map = getValueMap();
  let values;
  let suffix = '';

  if (text.length % 2 !== 0) {
    suffix = text.charAt(text.length - 1);
    values = text.slice(0, -1);
  } else {
    values = text;
  }

  let encoded = '';
  for (let i = 0; i <= text.length - 2; i += 2) {
    if (map[values[i] + values[i + 1]]) {
      encoded += map[values[i] + values[i + 1]];
    } else {
      encoded += values[i] + values[i + 1];
    }
  }
  encoded += suffix;
  return encoded;
}

To decode, iterate through the string, if its a letter, add the corresponding number pair to the decoded output. If its already a number, simply add the number instead:

decode(encoded) {
  const map = getValueMap(true);
  let decoded = '';

  for (let i = 0; i < encoded.length; i++) {
    if (encoded[i].toLowerCase() !== encoded[i].toUpperCase()) {
      decoded += map[encoded[i]];
    } else {
      decoded += encoded[i];
    }
  }

  return decoded;
}

Some example inputs and outputs:

Encode:
13223233202200252044 -> hkopika25i44

Decode:
holppcmi40 -> 133223333302302040

Is there a more straightforward way to do this? My implementation feels unnecessarily obtuse. For example, do I actually need to create a map/reverse map when I could maybe rely on indexing the pair array or alphabet instead? Is there a more elegant way to iterate over pairs of numbers? Or to build up the final encoded/decoded form without appending to a string?

First a few suggestions to your design.
You are effectively trying to represent list of small numbers as String, with no actual meaning (at least that's how I understood it).
I'd consider:

Represent it for what it is - list of small numbers could be represented as byte array. That seems a lot more natural and convenient.
Use some simpler mapping, if it doesn't matter what kind of character is the result. If numbers really are in range between 0 and 32 and not much higher, I'd go for mapping function, that for example adds 65 (and substracts 65 in reverse). That mapping function is really simple and you don't need any kind of map. Your code would be reduced only to initial tokenization basically. 00 becomes A, 30 becomes _ according to their ASCII codes (+65).

In case you wanna keep your String representation, here are my points to your code:

getValueMap

Names getValueMap name and lettersFirst don't really say what much about what do they do.
There's no point to recalculate reverse map everytime. Flag parameters with this kind of if are typical code smell and bad practice.
I suggest creating 2 module variables codesToCharacters (original map) and charactersToCodes (once pre-calculated) instead.

decode

I'd love if this function was just mapping encoded data to decoded data based on mapping function.
Not sure, why is there that if. I think you are trying to check, if current character is letter or not and if so, map it, otherwise use the character. That took me a while to understand. If there was really need, I would extract that to function with propper name (like isLetter) to increase readability.
Anyway, why even doing that? Why not instead look into the map and if map contains key, use map value, otherwise use original character.

Function would look something like (pseudocode, not tested):

function decode(encoded) {

    return encoded.split("").map(
        c => {
            charactersToCodes.hasKey(c) ? charactersToCodes[c] : c
        }).join()

}

encode would be on same principle, only difference is, that you need to tokenize it correctly first and then map :)


Setting new lines and adding them to a list to be drawn I have a method that basically passes in a known drawn line segment in my view and then draws parallel lines n distances away from the passed in original line. This one in particular draws two parallel lines on either side.

It seems to be a lot of repeat code here, so how can I refactor it to a smaller method and avoid redundancy?

public List<Line> DrawTwoParallelLines(Line line)
   {
       List<Line> listOfParallelLines = new List<Line>();

       Line parallelLine1 = new Line();
       Line parallelLine2 = new Line();
       Line parallelLine3 = new Line();
       Line parallelLine4 = new Line();

       parallelLine1.point1.x =(float)(line.point1.x + 50 * Math.Cos(90));
       parallelLine1.point1.y = (float)(line.point1.y + 0 * Math.Cos(90));
       parallelLine1.point2.x = (float)(line.point2.x + 50 * Math.Cos(90));
       parallelLine1.point2.y = (float)(line.point2.y + 0 * Math.Cos(90));

       parallelLine2.point1.x = (float)(line.point1.x + 100 * Math.Cos(90));
       parallelLine2.point1.y = (float)(line.point1.y + 0 * Math.Cos(90));
       parallelLine2.point2.x = (float)(line.point2.x + 100 * Math.Cos(90));
       parallelLine2.point2.y = (float)(line.point2.y + 0 * Math.Cos(90));

       parallelLine3.point1.x = (float)(line.point1.x + -50 * Math.Cos(90));
       parallelLine3.point1.y = (float)(line.point1.y + 0 * Math.Cos(90));
       parallelLine3.point2.x = (float)(line.point2.x + -50 * Math.Cos(90));
       parallelLine3.point2.y = (float)(line.point2.y + 0 * Math.Cos(90));

       parallelLine4.point1.x = (float)(line.point1.x + -100 * Math.Cos(90));
       parallelLine4.point1.y = (float)(line.point1.y + 0 * Math.Cos(90));
       parallelLine4.point2.x = (float)(line.point2.x + -100 * Math.Cos(90));
       parallelLine4.point2.y = (float)(line.point2.y + 0 * Math.Cos(90));

       listOfParallelLines.Add(parallelLine1);
       listOfParallelLines.Add(parallelLine2);
       listOfParallelLines.Add(parallelLine3);
       listOfParallelLines.Add(parallelLine4);

       return listOfParallelLines;

   }

Do you know about radians?

Math.Cos (and the other trig functions in .Net) are based on radians not degrees.

Math.Cos(90) radians is roughly Math.Cos(5157) in degrees. Which is a bit odd...

There are 2π radians in a circle so 1 degree is π/180. As long as you use the same value the lines will be parallel anyway but I thought it was worth pointing out.

Why do you need the Cos at all?

You have a line from (x1, y1) to (x2, y2) with length L = Math.Sqrt((x1-x2)^2 +(y1-y2)^2).

You know that you need to offset the line by an amount (offset) orthogonal to the current line.

private Line CreateParallelLine(Line target, int offset)
{
    var parallelLine = new Line();
    var xDifference = target.point1.x - target.point2.x;
    var yDifference = target.point1.y - target.point2.y;
    var length = Math.Sqrt(Math.Pow(xDifference, 2) + Math.Pow(yDifference, 2));

    parallelLine.point1.x = target.point1.x - offset * yDifference/length;
    parallelLine.point2.x = target.point2.x - offset * yDifference/length;
    parallelLine.point1.y = target.point1.y + offset * xDifference/length;
    parallelLine.point2.y = target.point2.y + offset * xDifference/length;

    return parallelLine;
}

Edit:

I realised that I've only given you an opportunity to create a single parallel line but I think it's straightforward to call the method more times with different offsets!

You didn't show your Line class/struct but it's worth noting that point1 should be at least PascalCase (Point1) but preferably renamed to something more like: Start and point2 renamed to be End or similar.

As x and y are also public, you should PascalCase them too: X and Y.


Find Permutations of String in Scala Given a smaller strings and a bigger string b, design an algorithm to find all permutations of the shorter string within the longer one.

def findPermutations(large: String, small: String): Int =
    large.sliding(small.length).filter(_.diff(small).isEmpty).length

@ findPermutations("cbabadcbbabbcbabaabccbabc", "abbc")
res11: Int = 7

@ findPermutations("xaabx", "abb")
res12: Int = 0

Archived (faulty)
@ def findPermutations(large: String, small: String): Int =
  large.sliding(small.length)
       .toList
       .filter(_.toSet == small.toSet)
       .length
defined function findPermutations

Please evaluate it for correctness and speed.

correct - As far as I can tell, yes.
concise - A filter() followed by a .length (or .size) can be simplified:
large.sliding(small.length).count(_.diff(small).isEmpty)
fast - Could be faster, but it wouldn't be as concise.

Consider the following: findPermutations("abcxcba", "cab")
Under the current design that would be 5 invocations of _.diff(small).isEmpty, but 3 of the 5 are rather pointless. No test string containing a character not found in the target string is worth the effort.
It'd be nice if the sliding window could "jump" over non-target characters. Doable, but not trivial.


Linked list copy constructor This is a working linked list that will be used as a vector. Instead of using dynamic arrays, I am using a linked list. I would like to see a more concise solution without utilizing the STL.

SimpleVector.h

class SimpleVector
{

public:

    SimpleVector(){
        head = nullptr;
    }
    SimpleVector(const SimpleVector &);
    ~SimpleVector();

    void appendNode(const int value);
    void insertNode(const int value);
    int getElementAt(const int index);
    void displayVect();

private:

    struct Node
    {
        int value;
        Node *next;
    };

    Node *head;

};

Copy constructor implementation

SimpleVector::SimpleVector(const SimpleVector &obj)
{

    Node *oldNodePtr;
    Node *newNodePtr;

    // Initialize head to nullptr incase obj is empty
    this->head = nullptr;

    // Position oldNodePtr to the head of the list.
    oldNodePtr = obj.head;

    if (oldNodePtr != nullptr) {

        // Create new node. This is the first node in the new list
        Node *newNode = new Node;
        newNode->value = oldNodePtr->value;

        // Set head to new node address
        this->head = newNode;

        newNodePtr = newNode;

        oldNodePtr = oldNodePtr->next;

        // While oldNodePtr points to a node, traverse the list.
        while (oldNodePtr->next != nullptr) {

            Node *newNode = new Node;
            newNode->value = oldNodePtr->value;
            newNodePtr->next = newNode;
            newNodePtr = newNodePtr->next;

            oldNodePtr = oldNodePtr->next;
        }

        Node *lastNode = new Node;
        lastNode->value = oldNodePtr->value;
        newNodePtr->next = lastNode;
        lastNode = nullptr;
    }
}

A standard dummy node trick (along with appropriate Node::Node constructors) greatly simplifies the code:

    SimpleVector::SimpleVector(const SimpleVector &obj)
    {
        Node dummy;

        for (Node * o = obj.head, *n = &dummy; o; o = o->next) {
            n->next = new Node(o->value);
            n = n->next;
        }

        this->head = dummy.next;
    }

To utilize STL, you need to implement iterators.


Basic game engine: timer, FPS and logic loop I'm creating a simple Java game engine (just for fun). The idea is to create a basic framework for developing any kind of 2D game, an abstract engine that does the hard work. Would you like to review the core of it and give me some tips?

GameTimer class:

public class GameTimer {

    public static final double ONE_SECOND = java.util.concurrent.TimeUnit.SECONDS.toNanos(1);

    private long start;
    private long[] ticks = new long[1000];
    private int first, last;
    private int fps;

    public GameTimer(){}

    public void start(){
        this.start = System.nanoTime();
    }

    public void tick(){
        ticks[last] = System.nanoTime();
        while (ticks[last] - ticks[first] > ONE_SECOND){
            first = circular(first + 1);
            fps--;
        }
        last = circular(last + 1);
        fps++;
    }

    public long tock(){
        return System.nanoTime() - ticks[circular(last-1)];
    }

    public long getElapsedNanoTime(){
        long prev = ticks[circular(last-2)];
        return (prev == 0) ? 0 : ticks[circular(last-1)] - prev;
    }

    public double getElapsedTime(){
        return this.getElapsedNanoTime() / ONE_SECOND;
    }

    public long getNanoTime(){
        return System.nanoTime() - this.start;
    }

    public double getTime(){
        return this.getNanoTime() / ONE_SECOND;
    }

    public int getFPS(){
        return this.fps;
    }

    private int circular(int n){
        return Math.floorMod(n, ticks.length);
    }
}

Game loop:

double desiredFPS = 60d;
long sleep = (long) (GameTimer.ONE_SECOND / desiredFPS);
GameTimer timer = new GameTimer();
timer.start();

try {
    while(true){

        // tick and print fps
        timer.tick();
        System.out.println(timer.getFPS());

        // input, update and draw (abstract methods of my engine class)
        input();
        update();
        draw();

        // sleep
        long wake = System.nanoTime() + sleep - timer.tock();
        do {Thread.sleep(0);}
        while (System.nanoTime() < wake);
    }
} catch (InterruptedException e) {
    // oh someone paused the game
}

Notes:

For more precision, I'm using nanoseconds and a busy-waiting loop instead of just calling the Thread.sleep() method (it is incredibly inaccurate). My tests show that the engine can keep the desired frequency quite precisely.
I'm using a circular buffer to count the frames per second, I don't like that loop to count late ticks but I couldn't find a better way to do it.
The start variable and related get methods in the GameTimer it's just for game logic use, it isn't important for fps counting or tick/tock operations.

The whole tick tock mechanism is not needed for your main loop.

You've set up this elaborate contraption (it took me a while to understand) which measures how long your last "frame" took. Then, when deciding on how long you'll need to wait to get to the next frame, you retrieve that time, and subtract that from the current time plus how long you want to wait.

All this is a very elaborate mechanism for this:

long sleep = (long) (GameTimer.ONE_SECOND / desiredFPS);
try {
    while(true){

        // tick and print fps
        long lastTick = System.nanoTime();
        timer.tick();
        System.out.println(timer.getFPS());

        // input, update and draw (abstract methods of my engine class)
        input();
        update();
        draw();

        // sleep
        long wake = lastTick + sleep;
        do {Thread.sleep(0);}
        while (System.nanoTime() < wake);
    }
} catch (InterruptedException e) {
    // oh someone paused the game
}

This rewrite doesn't really help so I'll explain:

What you have made is something that keeps track of ticks. That's okay. But to then use the tick timer in the calculation makes no sense - you already HAVE the time you started the tick - it's when you entered the loop!

Your GameTimer is useful for doing things like showing debug information in graph form, or finding patterns in lagspikes. But for this usecase, just a single long will do.

And first and last are wrongly named. It's not a pointer to the first and last item in the circular buffer, it's a pointer to the first and last frame of the past second. This should be encoded in the variable name.


A Ruby string analyser I wrote this script for a code challenge on TreeHouse. I already submitted my code, but I am looking for an after the fact feedback.

The challenge was to open a file of text, remove specific words (provided in another file) and do the following:

  Output to the screen in a readable fashion
  1. total word count after filtering
  2. highest occurring word
  3. longest word(s) and its / their length
  4. sort the list from most occurring to least occurring then output that data to the screen as an unordered list
  5. Bonus: Return the word list in JSON.

I decided to split the solution into two classes:

One class to sanitise the string into words only
Another class to do the analysis

This is the sanitiser class. Given text it should return a string of words only. It should remove anything that is not a letter or an apostrophe, and compress all white space into a single space character.

I accept that this has problems. For example, I found an instance of an apostrophe as a word. Perhaps it was a leading or a trailing one. But defining the boundaries of a word is a tricky proposition.

class WordsOnlySanitizer
  # Allow for diacritics, hence p{Alpha} and not \w
  # We should not split words on apostrophes either
  WORDS_ONLY_REGEX = /[^\p{Alpha}']/i

  # We want to reduce all white space into a single space
  SPACE_ONLY_REGEX = /\s+/

  def self.to_words(text)
    text.gsub(WORDS_ONLY_REGEX, ' ').gsub(SPACE_ONLY_REGEX, ' ')
  end
end

This is the analyser class. It's self explanatory. There is duplication in the longest_words and highest_occuring_words methods. But I'm not sure how to remove this duplication without making the code less readable.

The html_list method also looks a little suspect, but I can't tell why.

require 'json'

class Analyser
  def initialize(text, filter)
    @words = text.split
    @filter = filter.split
  end

  def word_count
    filtered_words.size
  end

  def word_occurrences
    @word_occurrences ||= filtered_words.inject(Hash.new(0)) do |result, word|
      result[word] += 1
      result
    end
  end

  def highest_occurring_words
    word_occurrences.group_by { |key, value| value }.max_by { |key, value| key }.last
  end

  def longest_words
    filtered_words.inject({}) do |result, word|
      result[word] = word.length
      result
    end.group_by { |key, value| value }.max_by { |key, value| key }.last
  end

  def html_list
    list = ""
    word_occurrences.sort_by { |key, value| value }.reverse.each do |key, value|
      list << "
#{key}: #{value}
\n"
    end
    "
\n" + list + "
"
  end

  def json_list
    JSON.parse(word_occurrences.to_json)
  end

private

  def filtered_words
    @filtered_words ||= @words.reject do |word|
      # Downcase so that Hello and hello count as two occurrences
      word.downcase!
      @filter.include?(word)
    end
  end
end

Usage

Here's how you would use this:

text = WordsOnlySanitizer.to_words(File.read('words.txt'))
filter = WordsOnlySanitizer.to_words(File.read('filter_words.txt'))
analyser = Analyser.new(text, filter)

puts "Word count after filtering is: #{analyser.word_count}"
puts "\n"

puts "The most frequent words are:"
analyser.highest_occurring_words.each do |key, value|
  puts "  - #{key}: #{value} occurences"
end
puts "\n"

puts "The longest words are:"
analyser.longest_words.each do |word|
  puts "  - #{word.first}: #{word.last} characters"
end
puts "\n"

puts "Word list:"
puts analyser.html_list

puts "JSON object:"
puts analyser.json_list

Here's a gist with all the files. Warning: There are large text files.

The first thing I noticed is that you've defined methods such as word_occurrences, which do nothing but set instance variables (@word_occurrences, etc.). This is a bit redundant, and it would be better to do one of two things:

Define all of your instance variables under the initialize method. or
Take out the @word_occurrences ||= part of the method definition.

I think from a performance standpoint, it might be better to take the first approach, since you don't want to have to calculate word_occurrences every time you call it as a method. I also noticed that you only use @words and @filter once, and that's to define filtered_words, so you can make things simple by just defining @words to be what filtered_words is currently. See below:

def initialize(text, filter)
  @words = text.split.reject {|word| filter.split.include? word.downcase}
  @occurrences = @words.each_with_object(Hash.new(0)) {|word, result| result[word] += 1}
  @lengths = @words.each_with_object({}) {|word, result| result[word] ||= word.length}
end

I've made @words the new filtered_words, shortened word_occurrences to just @occurrences (and made it an instance variable so that we're only evaluating it once, upon initialization of the instance), and added another instance variable @lengths, which represents a part of your longest_words function, a hash of each word and how long it is.

Also, notice that I simplified your use of inject to create a hash of word occurrences and word lengths, by using the handy each_with_object function instead.

I also changed = to ||= for the part where you're building up a hash of word lengths. I believe this will be better for performance, as you're not re-calculating the word length for words you already have.

You mentioned duplication between longest_words and highest_occurring_words -- you could solve this by pulling out the part you reused into a private function, which I would call highest_ranking:

private

def highest_ranking(entries)
  # Takes a hashmap of the form {"foo" => 100, "bar" => 45} and returns an array
  # containing the entries (array-ified) with the highest number as a value.
  entries.group_by{|word, occs| occs}.sort.last.last
end

I simplified max_by{|key, value| key}.last to just sort.last.last -- it turns out that Enumerable#sort knows how to properly handle sorting by keys, so getting the highest one is just a matter of sorting the hash and grabbing the last item in the resulting array. (The extra last is there for the same reason the last is there in your function -- to drop the number of occurrences and just return the key/value entries in the result array)

Now that you have this useful helper function, finding the highest occurring words and longest words is simple:

public

def highest_occurring_words
  highest_ranking @occurrences
end

def longest_words
  highest_ranking @lengths
end

Finally, I would refactor your html_list function like this:

def html_list
  list = word_occurrences.sort_by {|word, occs| occs}.reverse.map do |word, occs|
    "
#{word}: #{occs}
"
  end.join("\n")
  "
\n" + list + "\n
"
end

Instead of starting with list as "" and iterating through each word/occurrences pair to add onto it a little at a time, you can take a functional approach and use map to turn each word/occurrences pair into a string like "
antibubbles: 4
", then use join to turn the resulting array into one long string with "\n" inserted in between each list item. I also inserted two spaces before each list item so that they appear indented in the HTML. :)


Parsing unknown POST Args in PHP I have an HTML form being populated by a table of customer requests.  The user reviews each request, sets an operation, and submits.  The operation gets set into a post arg as follow

$postArray = array_keys($_POST);

[1]=>Keep [2]=>Reject [3]=>Reject [4]=>Ignore ["item id"]=>"operation"

This is how I am parsing my Post args... it seems awkward, the unused $idx.  I am new to PHP, is there a smoother way to do this?

$postArray = array_keys($_POST);
foreach($postArray as $idx => $itemId) {
    $operation = $_POST[$itemId];
    echo "$itemId $operation </br>";
    ...perform operation...
}

It looks like you may want to unset the 'item id' entry in your post array before you do the processing:

unset($_POST['item id']);

Then you can use foreach to loop over the key (idx) and value (operation).

foreach ($_POST as $idx => $operation)
{
    echo $idx . ' ' . $operation . '</br>';
    // perform operation.
}

The array_keys function was unnecessary because foreach can be used with associative arrays handling both their keys and values.