Grid walk problem and solving it recursively On CodeEval, there's a Grid Walk challenge:

  There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).

  Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

The first solution that came to my mind, intuitively, is to walk possible points recursively, breadth-first. Like this:

var monkey = function (x, y) {
    if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
        visited.push({x: x, y: y});
        return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
    } else {
        return 0;
    }
};

So I return the count of current point and all adjacent points recursively, checking each point that it's allowed by game rules and hasn't been visited before. First is that the sum of the digits of x and y is less or equal 19; second is that the point isn't in visited array. The complete code is like:

var visited = [];

var isPointAllowed = function (x, y) {
    var o = 0;
    for (var i = 0, x = Math.abs(x), s = x.toString(), l = s.length; i < l; o += +s[i++]);
    for (var i = 0, y = Math.abs(y), s = y.toString(), l = s.length; i < l; o += +s[i++]);
    return o <= 19;
};

var isPointVisited = function (x, y) {
    for (var i = 0; i < visited.length; i++) {
        if (visited[i].x == x && visited[i].y == y)
            return true;
    }

    return false;
};

var monkey = function (x, y) {
    if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
        visited.push({x: x, y: y});
        return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
    } else {
        return 0;
    }
};

console.log(monkey(0, 0));

The problem is that, on CodeEval's environment, my code executes more than 10 seconds, thus is always being terminated, and the challenge failed.

I tried to optimize the search and modified it to search only one (first) quadrant:

var monkey = function (x, y) {
    if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
        visited.push({x: x, y: y});
        return 1 + monkey(x + 1, y) + monkey(x, y + 1);
    } else {
        return 0;
    }
};

console.log(monkey(0, 0)*4 - 299*4 + 1);

It outputs correct value but is still too slow.

Am I doing it wrong with recursion? Should I abandon this idea and implement simple nested cycle search?

What are most inefficient fragments of my code, like searching exhaustively for each point within visited array?

P.S. The problem itself is duplicate here but I believe my question is unique.

Profiling the code has shown that iterative search in sequential array (integer keys 0, 1, ...) is far slower that simply accessing a value by string key in an associative array of non-sequential keys represented by strings (like '-1,1' or similar). So I modified isPointVisited function:

var isPointVisited = function (x, y) {
    // console.log('isPointVisited, x = %s, y = %s', x, y);
    if (visited[[x, y]])
        return true;

    return false;
};

and monkey function:

var monkey = function (x, y) {
    if (isPointAllowed(x, y) && !isPointVisited(x, y)) {
        visited[[x, y]] = true;
        return 1 + monkey(x - 1, y) + monkey(x + 1, y) + monkey(x, y - 1) + monkey(x, y + 1);
    } else {
        return 0;
    }
};

This code still executes for a bit longer than 10 seconds (11800 ms on CodeEval) but it's at least 8 times faster than before.


SQL report of subscribers and their associated revenue A user can have many subscriptions, and a subscription belongs to one plan.  The plans table tells us a subscription's cost.  Is the query below the correct one for figuring out the number of subscriptions purchased by a user with an "ongoing" status and the total revenue brought in each day  between Jan 1 and Mar 4, 2016?

Essentially, I'm creating a business report via SQL.  Each "day" bucket should contain the number of ongoing subscriptions created that day and the the total revenue brought in by those subscriptions that day.

select
    extract(MONTH from subscriptions.created_at) as mth,
    extract(DAY from subscriptions.created_at) as dy,
    count(subscriptions.id) as subs,
    round(sum(plans.cost)::numeric, 2) as revenue
from users
JOIN subscriptions ON subscriptions.user_id = users.id
JOIN plans ON subscriptions.plan_id = plans.id
where subscriptions.subscription_status = 'ongoing'
and subscriptions.created_at >= '01/01/16'
and subscriptions.created_at <= '03/04/16'
group by MTH, DY order by MTH, DY

I think this looks very good, but I would make a few small changes:

Instead of getting separate columns for month and day, use one column with date_trunc('day', subscriptions.created_at). Then you still have a timestamp that you can format, sort by, etc. Also you will avoid problems when someone reports on a range crossing New Years.
Be aware that binning timestamps into days involves time zones. Right now you're cutting days using UTC, which may be fine, but just be aware of it if you want to do something else.
You don't seem to be using the users table at all, so you could just leave that out completely.
Watch out for your edge conditions. Your query will include all of 1/1 but only the first instant of 3/4. It is more common and probably better to do >= and <. Otherwise if something happens in that first instant it will be double-counted with the next range (e.g. 3/4 to 6/1).


Translating Objective-C use of static and +(void)initialize to Swift I am converting an old Objective-C class into Swift. My actual question is at the very end after all of the code.

Here is a cut-down version of the Objective-C class:

DateInfo.h:

#import <Foundation/Foundation.h>

@interface RMYearInfo : NSObject

// There are also some instance properties but those aren't relevant to the question

+ (NSInteger)numberOfMonths;
+ (NSArray *)shortMonthNames;
+ (NSArray *)longMonthNames;
// several other class methods

@end

DateInfo.m:

#import "DateInfo.h"

static NSArray *shortMonthNames = nil;
static NSArray *longMonthNames = nil;
// there are several other statics as well

@implementation DateInfo

+ (void)reinitialize {
    NSCalendar *cal = [NSCalendar currentCalendar];

    NSDateFormatter *yearFormatter = [[NSDateFormatter alloc] init];

    shortMonthNames = [yearFormatter shortStandaloneMonthSymbols];
    longMonthNames = [yearFormatter standaloneMonthSymbols];

    // lots of other processing for the other statics
}

+ (void)initialize {
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(reinitialize) name:NSCurrentLocaleDidChangeNotification object:nil];

    [self reinitialize];
}

+ (NSInteger)numberOfMonths {
    return shortMonthNames.count;
}

+ (NSArray *)shortMonthNames {
    return shortMonthNames;
}

+ (NSArray *)longMonthNames {
    return longMonthNames;
}

// Lots of other instance and class methods

As you can see, the initialize method sets up a notification handler so all of the static variables can be reinitialized if the locale is changed while the app is running.

Here is my Swift code. Since there is no initialize in Swift (any more), my solution is to use private backing variables for the public static variables.

import Foundation

public struct DateInfo {
    // some normal instance properties irrelevant to the question

    private static var _formatter: DateFormatter!
    private static var formatter: DateFormatter {
        if _formatter == nil {
            _formatter = DateFormatter()
            NotificationCenter.default.addObserver(forName: NSLocale.currentLocaleDidChangeNotification, object: nil, queue: nil) { (notification) in
                _formatter = DateFormatter()
                _shortMonthNames = nil
                _longMonthNames = nil
                // reset all of the other statics as well
            }
        }

        return _formatter
    }

    private static var _shortMonthNames: [String]!
    public static var shortMonthNames: [String] {
        if _shortMonthNames == nil {
            _shortMonthNames = formatter.shortStandaloneMonthSymbols
        }

        return _shortMonthNames
    }

    private static var _longMonthNames: [String]!
    public static var longMonthNames: [String] {
        if _longMonthNames == nil {
            _longMonthNames = formatter.standaloneMonthSymbols
        }

        return _longMonthNames
    }

    public static var numberOfMonths: Int {
        return shortMonthNames.count
    }

    // lots of other similar private/public pairs of statics
}

Is this an appropriate way to translate the functionality given the need to be able to reinitialize the statics? I don't like having a private static backing each public static property.

Some thoughts:

Make formatter a static stored property (which are guaranteed to be lazily initialized only once). This  allows to get rid of the backing property _formatter.
For more clarity, move the reinitialization code to a separate method, as in your Objective-C version.
Do not cache the other static properties. For example, returning formatter.shortStandaloneMonthSymbols is only one indirection more than returning _shortMonthNames, but is simpler and allows to get rid of the remaining backing properties.
A minor point: The notification closure does not access the (notification) argument, which can therefore be replaced by _.

Putting it together, we have the following implementation:

public struct DateInfo {

    private static func reinitialize() {
        formatter = DateFormatter()
    }

    private static var formatter: DateFormatter = {
        // This closure is executed exactly once, on the first accesss of the `formatter` property.
        NotificationCenter.default.addObserver(forName: NSLocale.currentLocaleDidChangeNotification, object: nil, queue: nil) { _ in
            reinitialize()
        }
        return DateFormatter()
    }()

    public static var shortMonthNames: [String] {
        return formatter.shortStandaloneMonthSymbols
    }

    public static var longMonthNames: [String] {
        return formatter.standaloneMonthSymbols
    }

    public static var numberOfMonths: Int {
        return shortMonthNames.count
    }
}

Another option would be to use the typical Singleton pattern:

public class DateInfo {
    static let shared = DateInfo()

    private var formatter: DateFormatter

    private init() {
        formatter = DateFormatter()
        NotificationCenter.default.addObserver(forName: NSLocale.currentLocaleDidChangeNotification, object: nil, queue: nil) { _ in
            self.formatter = DateFormatter()
        }
    }

    public var shortMonthNames: [String] {
        return formatter.shortStandaloneMonthSymbols
    }

    public var longMonthNames: [String] {
        return formatter.standaloneMonthSymbols
    }

    public var numberOfMonths: Int {
        return shortMonthNames.count
    }
}

The advantage is that all initialization is clearly done in the init method. A small disadvantage might be that more typing is needed to access the properties (e.g. DateInfo.shared.shortMonthNames).


A beautiful and easy way of permutation with recursion I want to share a better version of permutation with you.

Yesterday, when I was reading Horowitz's Fundamentals of Data Structures In C++, and I noticed that the result of the code, at page 32, in the book is not what I want.

For example, if I have an array of {'a', 'b', 'c'}, then the result it provides is:

abc
acb
bac
bca
cba
cab

Notice that the last two cases don't fit what I want: when 'c' is fixed, all the other letters at its right should start from a, with relative order, \$a \lt b \lt c \lt \ldots \lt z\$, so the result should be:

...
cab
cba

Here is my code, which corrects the order with two modified swaps:

#include <iostream>
using namespace std;

void printPermutation(char *a, const int k, const int m);
void swap2(char *a, const int l, const int r);
void swap3(char *a, const int l, const int r);

int main() {
    char str[] = {'a', 'b', 'c', 'd', 'e'};
    printPermutation(&str[0], 0, sizeof(str)-1);
    return 0;
}

void printPermutation(char *a, const int k, const int m) {
    if (k == m) {
        for (int i = 0; i <= m; i++) {
            cout << a[i];
        }
        cout << endl;
    }
    else {
        for (int i = k; i <= m; i++) {
            // the code in the book just use swap, but I change them.
            swap2(a, k, i); // here
            printPermutation(a, k+1, m);
            swap3(a, k, i); // and here
        }
    }
}

// swap2 will move the element at index r to l,
// by continuously swap with element at its left
void swap2(char *a, const int l, const int r) {
    for (int i = r; l < i; i--) {
        swap(a[i], a[i-1]);
    }
}

// The same concept with swap2, but from left to right
void swap3(char *a, const int l, const int r) {
    for (int i = l; i < r; i++) {
        swap(a[i], a[i+1]);
    }
}

How can I further simplify the code?

I like the idea that the author used recursion to make things beautifully simple. But to achieve the result I want as described above, I have to add two additional, a little bit similar, functions.

The simpler code would look something like this:

#include <string>
#include <algorithm>
#include <iostream>

int main() {
    std::string s = "abcde";

    while (std::next_permutation(s.begin(), s.end()))
        std::cout << s << "\n";
}

If you wanted to do something on the same general order as a Python generator, you'd use C++'s new coroutine support. What's currently included is (by intent) very low-level, so you need a fair amount of infrastructure on top of it before it's easy to write a Python-like generator.

To keep from getting buried in details you probably don't care a lot about (right now) I'll use Kenny Kerr's Generator class (the first 173 lines, transplanted into a header). Using it, we get something like this:

#include "generator.hpp"
#include <iostream>
#include <string>
#include <algorithm>

template <class T>
generator<T> perm(T initial) {
    while (std::next_permutation(initial.begin(), initial.end()))
        co_yield initial;
}

int main() {
    using namespace std::literals;
    for (auto const &i : perm("abcde"s))
        std::cout << i << "\n";
}

As to your code, a few points jump out:

Don't use std::endl. It flushes the stream, which you almost never want. Just use '\n'. On the rare occasion that you do want to flush the stream, use std::flush.
The C library reserves most names that start with str, so it's probably better to avoid using that as a name.
using namespace std; is widely considered a problem except under a small number of rather unusual circumstances.
If you really want to do this (more) on your own, you might want to take a look at std::rotate, which can replace both your swap2 and swap3. std::rotate will also typically be more efficient than your implementation.
swap2 and swap3 strike me as poor names. At first glance, it seems like rotate_left and rotate_right would probably be better names (but also see above).


Using Linq syntax, how can I remove the select n+1 issue in this method? I have the following code in a validation module. It works the way I want it to, but it has an obvious select n+1 problem. I would like to refactor this code to make a single call to the db to perform this validation.

Is there a way I can do it using linq or do I need to perform more major surgery? I am trying to avoid sprocs at this point, but am willing to listen to arguments for it.

private void EnsureIdentifiersAreNotInUse(AddOrEditClientCommand request)
        {
            var identifiers = request.Editor.Identifiers;

            for (var i = 0; i < identifiers.Count; i++)
            {
                var identifier = identifiers[i];
                var exists = dbContext.ClientIdentifers
                    .Any(x => x.Client.Id != request.Editor.ClientId
                        && x.ClientIdentifierType.Id == identifier.TypeId
                        && x.Value.Equals(identifier.Value, StringComparison.InvariantCultureIgnoreCase));
                if(exists)
                    request.ModelState.AddModelError("Identifiers[{0}].Value".FormatWith(i), "System Id ({0}) is already in use".FormatWith(identifier.Value));
            }
        }

I think this might work for you

void EnsureIdentifiersAreNotInUse(AddOrEditClientCommand request)
{
    var identifiers = request.Editor.Identifiers;

    var errors =
        dbContext.ClientIdentifers
            .Where(ci => ci.Client.Id != request.Editor.ClientId
                   && identifiers.Any(i => ci.ClientIdentifierType.Id == i.TypeId
                                      && ci.Value.Equals(i.Value, StringComparison.InvariantCultureIgnoreCase)));
}

UPD
Ok, your identifier type is not presented at db, so the query cannot be converted to a db query.

Let's try this:

void EnsureIdentifiersAreNotInUse(AddOrEditClientCommand request)
{
    var identifiers = request.Editor.Identifiers;
    var identifiersIds = identifiers.Select(i => i.TypeId).ToList();
    var identifiersValues = identifiers.Select(i => i.Value).ToList();

    var errors =
        dbContext.ClientIdentifers
            .Where(ci =>
                   {
                       if (ci.Client.Id == request.Editor.ClientId)
                       {
                           return false;
                       }
                       var indexOfId = identifiersIds.IndexOf(ci.ClientIdentifierType.Id);
                       if (indexOfId == -1)
                       {
                           return false;
                       }
                       return indexOfId == identifiersValues.IndexOf(ci.Value);
                   });
}


Monoalphabetic Cipher in Java With GUI An easy, terribly written but working, Caeasar (Monoalphabetic) cipher implementation, with a GUI (Graphical User Interface).

Cipher.java

class Cipher {

    static final String alphabet = "abcdefghijklmnopqrstuvwxyz";

    public static char shift(char ch, int amount) {
        return alphabet.charAt((alphabet.indexOf(ch) + amount) % alphabet.length());
    }

    public static String caesarCipher(String text, int amount) {
        String result = "";
        for (char ch : text.toCharArray()) {
            if (alphabet.indexOf(ch) >= 0) {
                result += shift(ch, amount);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        assert shift('a', 1) == 'b';
        assert shift('z', 2) == 'b';
        assert caesarCipher("abc", 2).equals("cde");
    }
}

Gui.java

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Gui {

    private static void createAndShowGUI() {
        //Create and set up the window.
        JFrame frame = new JFrame("HelloWorldSwing");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        JPanel body = new JPanel();

        final JTextField label = new JTextField("aaaaaaaaaaaaaaaaaaaaaaa");
        body.add(label);

        final JTextField key = new JTextField("1");
        body.add(key);

        final JTextField result = new JTextField("bbbbbbbbbbbbbbbbbbbbbb");

        JButton activationButton = new JButton("Encrypt");
        activationButton.addActionListener(new ActionListener()
        {
            @Override
            public void actionPerformed(ActionEvent ae)
            {
                String plainText = label.getText();
                String keyval = key.getText();
                result.setText(Cipher.caesarCipher(plainText, Integer.parseInt(keyval)));
            }
        });

        body.add(activationButton);

        body.add(result);

        frame.add(body);

        //Display the window.
        frame.pack();
        frame.setVisible(true);
    }

    public static void main(String[] args) {
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }
}

Input validation

It would be good to validate user input.
If I enter "hello" as the key value,
The UI won't like it very much.

Shifting

An idea to simplify the shifting.
Instead of taking modulo for each character,
double the alphabet (concatenate the original alphabet twice), and normalize the key value.
The solution will use twice the space for the alphabet,
but the shifting will be much faster without the modulo.

Skipping unknown characters

The current algorithm checks if a character is in the alphabet, skipping without translation if it's not. So if you convert an English sentence with space characters, the word boundaries will be lost, which will be a problem when reversing the process.

Finding the index twice

The current algorithm checks is in the alphabet, if yes it calls another to perform the shift. That method finds the index again for the second time, to calculate the shifted index. This second lookup could be eliminated if you rename "shift" to "translate" and change its behavior to lookup the index once and reuse it.

Dummy data

Instead of hardcoding the dummy result it would be better to compute it using the cipher.

Naming constants

The convention is to use SHOUTCASE for constants like the alphabet.

Testing

A bunch of assertions in a main method are no substitute for proper unit testing.


Item-based collaborative filtering I wrote the following code using Ruby to compute item-based collaborative filtering (using Jaccard coefficient of similarity).

I would appreciate feedback about any potential issues with the code and tips to make the code better comply with the best practices.

require 'json'
require 'set'

def compute_jaccard_coefficients(users_for_activities)
    jaccard_coefficient_hash = {}
    all_activities = Set.new
    users_for_activities.each do |key1, array1|
        users_for_activities.each do |key2, array2|
            if key1 != key2
                all_activities.add key1
                all_activities.add key2
                intersected_users = array1 & array2
                unioned_users = array1 | array2
                if unioned_users.length > 0
                    jaccard_coefficient_hash[[key1, key2]] = intersected_users.length.fdiv(unioned_users.length)
                    else
                    jaccard_coefficient_hash[[key1, key2]] = 0
                end
            end
        end
    end
    return [jaccard_coefficient_hash, all_activities]
end

data = '[
{"user": "1", "activities": ["running", "swimming", "rowing"]},
{"user": "2", "activities": ["tennis", "rowing"]},
{"user": "3", "activities": ["swimming", "running"]},
{"user": "4", "activities": ["tennis", "swimming"]}
]'

parsed_data = JSON.parse(data)

users_for_activities = Hash.new{|h,k| h[k] = []}

parsed_data.each do |child|
    child["activities"].each do |activity|
        users_for_activities[activity] << child["user"]
    end
end

all_activities = Set.new
jaccard_coefficient_hash, all_activities = compute_jaccard_coefficients(users_for_activities)

parsed_data.each do |child|
    activities_to_recommend = {}
    child["activities"].each do |user_activity|
        all_activities.each do |generic_activity|
            if user_activity != generic_activity
                if activities_to_recommend.has_key?(generic_activity)
                    if jaccard_coefficient_hash[[user_activity, generic_activity]] > activities_to_recommend[generic_activity]
                        unless child["activities"].include?(generic_activity)
                            activities_to_recommend[generic_activity] = jaccard_coefficient_hash[[user_activity, generic_activity]]
                        end
                    end
                    else
                    unless child["activities"].include?(generic_activity)
                        activities_to_recommend[generic_activity] = jaccard_coefficient_hash[[user_activity, generic_activity]]
                    end
                end
            end
        end
    end
    print "User " + child["user"] + ": "
    print activities_to_recommend.sort_by {|k,v| v}.reverse
    print "\n"
end

Output:

User 1: [["tennis", 0.3333333333333333]]
User 2: [["running", 0.3333333333333333], ["swimming", 0.25]]
User 3: [["rowing", 0.3333333333333333], ["tennis", 0.25]]
User 4: [["running", 0.6666666666666666], ["rowing", 0.3333333333333333]]

Stuff I noticed:

Use next to skip an each-iteration instead of wrapping everything in an if statement
No need for Set. A hash's keys are already a set, so in your compute_jaccard_coefficients method you could just call all_activties = users_for_activities.keys and done. From the raw data, you could do all_activities = parsed_data.map { |user| user['activities'] }.flatten.uniq
I'd absolutely avoid returning a tuple from the compute_jaccard_coefficients method. As illustrated above, getting all the activities isn't difficult; you can do that anywhere. And the method itself doesn't use the set for anything; creating the set is just something it also does, even though it shouldn't be its responsibility. Your code definitely shouldn't rely on a method just randomly doing something
Since your method is checking combinations of activities, you might as well use Array#combination. Give it an argument of 2 and it'll give you an array of pairs activities. Note that it'll also give only unique combinations - i.e. you'll get a pair like ["tennis", "swimming"], but it'll skip ["swimming", "tennis"] since that's the same combination.
Favor methods like any? (or better - as Naklion points out in the comments - empty?) over checking an array's length with arr.count > 0

With the above in mind, the method can be written as

def compute_jaccard_coefficients(hash)
  coefficients = hash.keys.combination(2).map do |a, b|
    union = hash[a] | hash[b]
    weight = union.empty? ? 0 : (hash[a] & hash[b]).count / union.count.to_f
    [[a, b], weight]
  end
  Hash[coefficients]
end

Note that this implementation also gives you a cleaner result (no duplicate combinations) in fewer iterations.

I'm out of time right now, but I'll take a look at the rest of the code later.

Update: It's now "later", and Naklion has provided a very nice answer. Still, I'll give it a go too.

I used combination above, whereas Naklion used permutation. The latter gives an identical result to the original code (i.e. the coefficients hash will have keys for both tennis/rowing and rowing/tennis). Using combination you'll only get unique combinations, and thus fewer coefficient calculations, but lookup gets a bit more complex (which I wasn't considering when just looking at the Jaccard method). Still, since Naklion used permutations, I'll stick to combinations.

One addition, though, is to use Set (after all) to create the keys of the Jaccard hash:

def compute_jaccard_coefficients(hash)
  coefficients = hash.keys.combination(2).map do |a, b|
    union = hash[a] | hash[b]
    weight = union.empty? ? 0 : (hash[a] & hash[b]).count / union.count.to_f
    [Set[a, b], weight]
  end
  Hash[coefficients]
end

This allows us to look up weights without worrying bout the order of the key's elements, since Set[a, b] == Set[b, a].

Naklion provided a nice way (#9 on the list) to transpose the parsed_data from user-indexed activities to activity-indexed users, so I'll skip over that.

So starting with this (and the method above)

all_activities = users_for_activities.keys
coefficients = compute_jaccard_coefficients(users_for_activities)

you can do this

parsed_data.each do |user|
  possibles = all_activities - user['activities'] # activities the user doesn't have already
  recommendations = user['activities'].product(possibles).map do |a, b|
    # a is the user's existing activity, b is the recommended activity
    key = Set[a, b]
    [b, coefficients[key]] if coefficients[key] > 0
  end.compact.sort_by(&:last).reverse

  puts "User #{user[:user]}: #{recommendations}"
end


Using a variable in a for loop: is it proper practice or is there a better approach The goal of this code was to create a table from an associative array.

I need to create horizontal rows where  the keys need to be used as "headers" while the values are posted below each header.
I need to be able to reuse the code with associative arrays of unknown lengths and varying number of columns allowed in the tables.

I realize this is not set up as a function. I'm just playing with the code for now.

The code that I have actually does work. I'm not sure if it's "proper" form especially here - $startIndex = $index in the for loop.

I create two rows at a time - one for the header, one for the values. After the end of these two rows, I'm re-setting the index on the for loop so it runs through the next group in the array. I'm trying to get better at coding and would like some input on what I've done.

Print out a horizontal table with a capability to vary the number of  cells across

<table class="<?php echo $tableClass; ?>">

Horizontal

<?php
$array = array(
    "A" => 1,
    "B" => 2,
    "C" => 3,
    "D" => 4,
    "E" => 5,
    "F" => 6,
    "G" => 7,
    "H" => 8,
    "I" => 9,
    "J" => 10,
    "K" => 11,
    "L" => 12,
    "M" => 13
);

$maxColumns = 8;//set the number of columns allowed in the table
$arrayOfKeys = array_keys($array);//grab the keys from the initial array
$count = count($arrayOfKeys);//gets a count of the number of items in  the array
$maxRows = ceil($count/$maxColumns) * 2;//takes the count and determines the number of rows based on the number of items and the maxColumns * 2 for total rows  (need a "header" and value for each set of keys/values in the array
$endIndex = $maxColumns-1;//initialize the endIndex on the loop that runs the
$startIndex = 0;//initialize the start index for the second loop which will loop through the array assigning keys to first row - value to second

for ($row=1; $row<=$maxRows; $row++){//loops based on the number of rows required to generate the table for the number of cells required

    echo '
';//start the row
    $rowEvenOdd = ($row % 2); //figures whether an even or odd row

    for ($index=$startIndex; $index<=$endIndex; $index++){//creates the rows
            if($rowEvenOdd == 1) {//if the row is odd, grab and display the key
                if(array_key_exists($index, $arrayOfKeys))
                    {$thiskey = $arrayOfKeys[$index];}
                    else {$thiskey ="&nbsp;";}
                echo "$thiskey	";
                }//end of odd rows
            if($rowEvenOdd == 0) {//if the row is even, grab and display the value
                if(array_key_exists($index, $arrayOfKeys))
                    {$thisvalue = $array[$arrayOfKeys[$index]];}
                    else {$thisvalue ="&nbsp;";}
                echo "". $thisvalue ."	";
                }//end of odd rows
    }//end of loop to generate content for the cells
    echo '
';//end the row
    if($rowEvenOdd == 0) {$startIndex = $index; $endIndex = $index + $maxColumns-1;/* reset the index begin and end  to loop through next group of rows */                           }
    }//end loops that creates the rows

?>

Use array_chunk() to split $rows into rows. Each row will be double high $doubleRows, so store the values in a small multi-dimension array $tablerows before echoing the rows.

// One single row.
$rows = array(
    "A" => 1,
    "B" => 2,
    "C" => 3,
    "D" => 4,
    "E" => 5,
    "F" => 6,
    "G" => 7,
    "H" => 8,
    "I" => 9,
    "J" => 10,
    "K" => 11,
    "L" => 12,
    "M" => 13
);

// Split into 1 or more rows of 8 columns each.
$doubleRows = array_chunk( $rows, 8, true );

// Rows are now double high.
// Keys on the first row and values on the second.
foreach ( $doubleRows as $columns ) {

    // Reset rows.
    $tableRows = array();
    foreach ( $columns as $key => $value ) {
        $tableRows['keys'][] = "$key	";
        $tableRows['values'][]  = "$value	";
    }

    echo "
", join( '', $tableRows['keys'] ), "
";
    echo "
", join( '', $tableRows['values'] ), "
";
}

Style

You used a lot of end comments. I try to avoid them and I try to avoid obvious comments like, // Start the row. To me, the
 tag is pretty self explanatory, but if it is not to you, then I understand why you did it.

Wrap long comments and use proper punctuation and capitalization. Comments are for humans. PHP strips them out. If you are the only person who ever sees your code, write your comments for the (different) person you will be in six months. The future you may appreciate comments that look like sentences and paragraphs.

Be consistent with your indentation and white space. Always indent the same number of characters. This foreach is indented 4 spaces (or 1 tab). The conditional statement is indented 12 spaces (or 3 tabs).

    for ($index=$startIndex; $index<=$endIndex; $index++){//creates the rows
            if($rowEvenOdd == 1) {//if the row is odd, grab and display the key

I would write it like this:

    // Create table rows.
    for ( $index = $startIndex; $index <= $endIndex; $index++ ) {
        if ( $rowEvenOdd == 1 ) {
            // Row is odd. Grab and display the key.

I added some white space so it wouldn't look all scrunch up. I find it easier to read like that. The comment after the conditional tells you what the condition is instead of what the conditional does.

If this is your style for writing one line conditionals, I guess it is fine, but it looks scrunch up and harder to read.

if(array_key_exists($index, $arrayOfKeys))
    {$thisvalue = $array[$arrayOfKeys[$index]];}
    else {$thisvalue ="&nbsp;";}

I prefer this:

if ( array_key_exists( $index, $arrayOfKeys ) ) {
    $thisvalue = $array[$arrayOfKeys[$index]];
} else {
    $thisvalue ="&nbsp;";
}

Or this:

if ( array_key_exists( $index, $arrayOfKeys ) )
    $thisvalue = $array[$arrayOfKeys[$index]];
else
    $thisvalue ="&nbsp;";

I tend to not add white space near brackets [] and to add it in parenthesis ().

Except for $thisvalue and $thiskey all your variable name use camel case. $thisValue and $thisKey would be more consistent.


Concurrent Stack with blocking and non-blocking methods I wrote it this just for learning. Is there holes at this code?

public interface ConcurrentStack<T> {
    //blocking
    void put(T t) throws InterruptedException;

    //blocking
    T poll() throws InterruptedException;

    //non-blocking put
    boolean offer(T t);

    //non-blocking get
    T take();
}

class ConcurrentStackImpl<T> implements ConcurrentStack<T> {
    private volatile AtomicBoolean locked = new AtomicBoolean(false);
    private List<T> internalList = new ArrayList<T>();
    private final int maxSize; // this final mandatory? I am afraid about visibility

    public ConcurrentStackImpl(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException();
        }
        this.maxSize = maxSize;
    }

    @Override //blocking
    public void put(T t) throws InterruptedException {
        while (!locked.compareAndSet(false, true)) ;//busy waiting
        internalList.add(t);
        locked.set(false);
    }

    @Override // non-blocking
    public T poll() throws InterruptedException {
        while (!locked.compareAndSet(false, true)) ;//busy waiting
        T value = internalList.get(internalList.size() - 1);
        locked.set(false);
        return value;
    }

    @Override
    public boolean offer(T t) {
        if (locked.compareAndSet(false, true)) {

            if (internalList.size() >= maxSize) {
                return false;
            }
            boolean addResult = internalList.add(t);
            locked.set(false);
            return addResult;
        }
        return false;
    }

    @Override
    public T take() {
        if (locked.compareAndSet(false, true)) {
            T t = internalList.get(internalList.size() - 1);
            locked.set(false);
            return t;
        }
        return null;
    }

}

I see that you made improvements to your code since here.

Synchronizing

You decided to use internal locking what is technically ok. The way you did it is a variant that I never used. I prefer to use following pattern:

Define an object local Lock-Object:

Object lock = new Object();

And synchronize with the synchronized-block construct:

public void anyMethod() {
    synchronized (this.lock) {
        // do stuff in monitor here
    }
}

Even if your approach is comparable to this you should go with less statements as you are always have aquire the lock with locked.compareAndSet(false, true) and release the lock with locked.set(false). You have no compiler and language support for this locking mechanism. You can easily forget to release the lock or you may find yourself in situations that will compromise your locking like: If your list is empty and you call the poll-method, it aquires the lock, failing afterwards with an ArrayIndexOutOfBoundsException that causes the lock never to be released. That is also true for the take-method().

Missing maxSize constraint (?)

I do not know if there should be any other assertion in the put-method. But there you do not check for maxSize.

Handle empty list

Your take()-method and your poll-method are vulnerable if the internalList is empty. They both fail with an ArrayIndexOutOfBoundsException. Either you return null or what I think is the better way to check for emptyness and throw an "EmptyStackException". This is the standard behaviour from the Java Stack implementation:

java.util.Stack<Object> stack = new java.util.Stack<>();
stack.pop(); // throws EmptyStackException

Avoiding the ArrayIndexOutOfBoundsException has semantical reasons. This Exception is published from different abstraction layer. So using an EmptyStackException is an interpretation of the underlying state of the internalList from the stack'S point of view.

You may say that you catch the ArrayOutOfBoundsException and map it to the EmptyStackException which would be the correct semantic. But you should avoid it to be thrown as throwing exceptions is very expensive.

Busy waiting

Currently you use a while-loop to wait for new elements if no element is present.

Busy waiting should be replaced by a non cpu killing concept. I doubt that in your case busy waiting or equivalent functionality should be done as mentioned in the comments there is a possibility never to recover from it. Providing a timeout mechanism would be an approach. Your busy waiting solution could easily extended to evaluate a given timout but it keeps very cpu expensive.

On the other side a non cpu killing way is complicated. The only chance to do so is to instantiate a Timeout-thread sleeping n seconds, before put the current thread to wait and notify it if the timout is reached with a timout marker. You have to consider that a notification should also be made when new elements become available. Furthermore your timeout thread has to be killed. You have to decide what to do if a timeout happens (returning null oor throwing an exception). Equivalent Java classes return null.

A personal note: In productive environments I would not implement such a timeout mechanism by myself if there is a chance to use existing well tested solutions. For the sake of education this is something where you certainly learn a lot but it also can be very frustrating as this goal is miles away in contrast to centimeters to the implementation so far. But I encourage you at least to go some meters to experience the burden you put on your shoulders.


Noughts and Crosses game in Python I wrote a two player Noughts and Crosses game in Python 3, and came here to ask how I can improve this code.

import random
cell = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
board = '\n\t ' + cell[0] + ' | ' + cell[1] + ' | ' + cell[2] + '\n\t-----------\n\t ' + cell[3] + ' | ' + cell[4] + ' | ' + cell[5] + '\n\t-----------\n\t ' + cell[6] + ' | ' + cell[7] + ' | ' + cell[8]
def owin(cell):
    return cell[0] == cell[1] == cell[2] == 'O' or cell[3] == cell[4] == cell[5] == 'O' or cell[6] == cell[7] == cell[8] == 'O' or cell[0] == cell[3] == cell[6] == 'O' or cell[1] == cell[4] == cell[7] == 'O' or cell[2] == cell[5] == cell[8] == 'O' or cell[0] == cell[4] == cell[8] == 'O' or cell[2] == cell[4] == cell[6] == 'O'
def xwin(cell):
    return cell[0] == cell[1] == cell[2] == 'X' or cell[3] == cell[4] == cell[5] == 'X' or cell[6] == cell[7] == cell[8] == 'X' or cell[0] == cell[3] == cell[6] == 'X' or cell[1] == cell[4] == cell[7] == 'X' or cell[2] == cell[5] == cell[8] == 'X' or cell[0] == cell[4] == cell[8] == 'X' or cell[2] == cell[4] == cell[6] == 'X'
def tie(cell):
    return cell[0] in ('O', 'X') and cell[1] in ('O', 'X') and cell[2] in ('O', 'X') and cell[3] in ('O', 'X') and cell[4] in ('O', 'X') and cell[5] in ('O', 'X') and cell[6] in ('O', 'X') and cell[7] in ('O', 'X') and cell[8] in ('O', 'X')
print('\tNOUGHTS AND CROSSES\n\t\tBy Lewis Cornwall')
instructions = input('Would you like to read the instructions? (y/n)')
if instructions == 'y':
    print('\nEach player takes turns to place a peice on the following grid:\n\n\t 1 | 2 | 3\n\t-----------\n\t 4 | 5 | 6\n\t-----------\n\t 7 | 8 | 9\n\nBy inputing a vaule when prompted. The first to 3 peices in a row wins.')
player1 = input('Enter player 1\'s name: ')
player2 = input('Enter player 2\'s name: ')
print(player1 + ', you are O and ' + player2 + ', you are X.')
nextPlayer = player1
while not(owin(cell) or xwin(cell)) and not tie(cell):
    print('This is the board:\n' + board)
    if nextPlayer == player1:
        move = input('\n' + player1 + ', select a number (1 - 9) to place your peice: ')
        cell[int(move) - 1] = 'O'
        board = '\n\t ' + cell[0] + ' | ' + cell[1] + ' | ' + cell[2] + '\n\t-----------\n\t ' + cell[3] + ' | ' + cell[4] + ' | ' + cell[5] + '\n\t-----------\n\t ' + cell[6] + ' | ' + cell[7] + ' | ' + cell[8]
        nextPlayer = player2
    else:
        move = input('\n' + player2 + ', select a number (1 - 9) to place your peice: ')
        cell[int(move) - 1] = 'X'
        board = '\n\t ' + cell[0] + ' | ' + cell[1] + ' | ' + cell[2] + '\n\t-----------\n\t ' + cell[3] + ' | ' + cell[4] + ' | ' + cell[5] + '\n\t-----------\n\t ' + cell[6] + ' | ' + cell[7] + ' | ' + cell[8]
        nextPlayer = player1
if owin(cell):
    print('Well done, ' + player1 + ', you won!')
elif xwin(cell):
    print('Well done, ' + player2 + ', you won!')
else:
    print('Unfortunately, neither of you were able to win today.')
input('Press <enter> to quit.')

Some notes:

  cell = ['1', '2', '3', '4', '5', '6', '7', '8', '9']

Try to be less verbose: cell = "123456789".split() or cell = [str(n) for n in range(1, 10)]. Anyway, conceptually it's very dubious you initialize the board with its number instead of its state. Also, cell is not a good name, it's a collection, so cells.

board = '\n\t ' + cell[0] + ...

Don't write such a long lines, split them to fit a sound max width (80/100/...). Anyway, here the problem is that you shouldn't do that manually, do it programmatically (grouped from itertools):

board = "\n\t-----------\n\t".join(" | ".join(xs) for xs in grouped(cell, 3))

  return cell[0] == cell1 == cell[2] == 'O' or cell[3] == cell[4] == cell[5] == 'O' or cell[6] == cell[7] == cell[8] == 'O' or cell[0] == cell[3] == cell[6] == 'O' or cell1 == cell[4] == cell[7] == 'O' or cell[2] == cell[5] == cell[8]== 'O

Ditto, use code:

groups = grouped(cell, 3)
any(all(x == 'O' for x in xs) for xs in [groups, zip(*groups)])

Note that you are not checking if a cell has already a piece.


Changing a sprite depending on variables I have code here which will change a sprite depending on the variables called gunUpgrade and moveUpgrade. Any way to make the code simpler or shorter? I'm using Unity 3D.

if (gunUpgrade > 0 && moveUpgrade > 0)
    {
        if (gunUpgrade == 1)
        {
            // For every moveupgrade, set the sprite to array number
            if (moveUpgrade == 1) { currentSprite = playerSprites[8]; }
            else if (moveUpgrade == 2) { currentSprite = playerSprites[9]; }
            else if (moveUpgrade == 3) { currentSprite = playerSprites[10]; }
            else if (moveUpgrade == 4) { currentSprite = playerSprites[11]; }
        }
        if (gunUpgrade == 2)
        {
            if (moveUpgrade == 1) { currentSprite = playerSprites[12]; }
            else if (moveUpgrade == 2) { currentSprite = playerSprites[13]; }
            else if (moveUpgrade == 3) { currentSprite = playerSprites[14]; }
            else if (moveUpgrade == 4) { currentSprite = playerSprites[15]; }
        }
        if (gunUpgrade == 3)
        {
            if (moveUpgrade == 1) { currentSprite = playerSprites[16]; }
            else if (moveUpgrade == 2) { currentSprite = playerSprites[17]; }
            else if (moveUpgrade == 3) { currentSprite = playerSprites[18]; }
            else if (moveUpgrade == 4) { currentSprite = playerSprites[19]; }
        }
    }

I suggest writing it as

currentSprite = playerSprites[4 * (gunUpgrade + 1) + (moveUpgrade - 1)];

Consider laying out the elements of playerSprites so as to require fewer ±1 operations.

Note that you must ensure that gunUpgrade never exceeds 3, and moveUpgrade never exceeds 4.


Function to prompt and check user input I'm trying to make a function that asks for a string input and then validates it. If the answer is not correct, the function asks them again for valid input with a while loop.

In order to validate the string input, I'm using a string array with all the possible answers to the question.

Because I'm using a string array I need to pass it into the function as a pointer.

The problem I'm running into is that to call the function properly currently I have to type this:

std::string possibleAnswers[3] = { "0","1","2" };
//find the length of the possibleAnswers array
int length = sizeof(possibleAnswers) / sizeof(possibleAnswers[0]);
//create a pointer that points at the string array
std::string* pointerPossibleAnswers = possibleAnswers;

//call function to validate input
std::string response = checkInput(pointerPossibleAnswers, length);

You'll also notice that I used
sizeof(possibleAnswers)/sizeof(possibleAnswers[0] to find the length which I can't call within the function, because the pointer in the function points to an element in the array, not the entire array.
My function implementation is here:

std::string checkInput(std::string* pointerPossibleAnswers, int length)
{
    std::string input;
    //input = toLowerCase(input);
    //create a boolean to continue to ask for input
    bool isAsking = true;
    while (isAsking)
    {
        std::getline(std::cin, input);

        //for loop checks against possibleAnswer array
        for(int i = 0; i< length; i++)
        {
            // dereference possibleAnswers pointer to the
            //ith position of the array
            if (input == *pointerPossibleAnswers)
            {
                isAsking = false;
                //stop checking if a possible response is found
                //break from the loop on next iteration
                i = length;
            }
            //make the pointer point to the next spot
            pointerPossibleAnswers++;
        }
        if (isAsking == true)
        {
            std::cout << "Invalid response, please enter a valid response." << std::endl;
            //reset the pointer to point at original memory
            //location
            for (int i = 0; i < length; i++)
            {
                pointerPossibleAnswers--;
            }
        }
    }
    return input;
}

I was just wondering if there is an easier way to call the function, which is one or two lines something like:

std::string possibleAnswers[3] = { "0","1","2" };
std::string response = checkInput(pointerPossibleAnswers, length);

within two lines that's more efficient, because I have noticed that I'm copying and pasting a lot of code each time. I feel like there is a much more efficient way to do this with a class or a vector, given they have some built in methods for calling

Use std::vector<std::string> instead C-style array for possibleAnswers and then pass a reference to the vector into the checkInput function.
If you will use std::vector you can use just std::find to check if the input appears in the possibleAnswers.
Consider making possibleAnswers constant1. It is never change, is not it?
The sizeof operator returns a value of type std::size_t but you use int length to hold it. You should use std::size_t instead of int for the loop counters i inside the checkInput fucntion as well. Note that int is not guaranted to be large enough to hold a size of any object type (an array of std::string in your case).
It is a good habit to prefer pre-increment over post-increment all things being equal in C++ since the first usually is faster.
Do not comment your code too much. Anyone perfectly knows that * means dereference:

// dereference possibleAnswers pointer to the
//ith position of the array
if (input == *pointerPossibleAnswers)

Make it a rule: "Comments shouldn't say what happens in code, they should say why this is happens".
You can easily restructure your code to get rid of the isAsking flag variable. All you have to do is explicitly return input when it equals to one of the possible answer.

1 As mentioned @πάντα ῥεῖ in the comments if you'll decide to use to make possibleAnswers constant you may want to use std::array. But in this case you have to use templates to pass different sized arrays to the possibleAnswers function.