ECS Event/Messaging implementation I am experimenting with ECS design and I am looking for a solid way to implement a message bus for use between the different systems.
Here is a stripped-down version of my current implementation:

#include <iostream>
#include <cstdlib>
#include <functional>
#include <vector>

struct BaseEvent
{
    static size_t type_count;
    virtual ~BaseEvent() {}
};

size_t BaseEvent::type_count = 0;

template <typename EventType>
struct Event : BaseEvent
{
    static size_t type()
    {
        static size_t t_type = type_count++;
        return t_type;
    }
};

struct EventManager
{
    template <class EventType>
    using call_type = std::function<void(const EventType&)>;

    template <typename EventType>
    void subscribe(call_type<EventType> callable)
    {
        if (EventType::type() >= m_subscribers.size())
            m_subscribers.resize(EventType::type()+1);
        m_subscribers[EventType::type()].push_back(
            CallbackWrapper<EventType>(callable));
    }

    template <typename EventType>
    void emit(const EventType& event)
    {
        if (EventType::type() >= m_subscribers.size())
            m_subscribers.resize(EventType::type()+1);
        for (auto& receiver : m_subscribers[EventType::type()])
            receiver(event);

    }

    template <typename EventType>
    struct CallbackWrapper
    {
        CallbackWrapper(call_type<EventType> callable) : m_callable(callable) {}
        void operator() (const BaseEvent& event) { m_callable(static_cast<const EventType&>(event)); }
        call_type<EventType> m_callable;
    };

    std::vector<std::vector<call_type<BaseEvent>>> m_subscribers;
};

The classes are then used like so:

struct PLAYER_LVL_UP : Event<PLAYER_LVL_UP>
{ int new_level; };

struct PLAYER_HIT : Event<PLAYER_HIT>
{ int damage; };

struct COLLISION : Event<COLISSION>
{ Entity entity1; Entity entity2; };

struct PLAYER_GUI
{

    PLAYER_GUI(EventManager& em, ...) : ...
    {
        using namespace std::placeholders;

        em.subscribe<PLAYER_HIT>(
            std::bind(&PLAYER_GUI::handle_hit, this, _1);
        em.subscribe<PLAYER_LVL_UP>(
            std::bind(&PLAYER_GUI::handle_lvl_up, this, _1);
        .
        .
    }

    void handle_hit(const PLAYER_HIT& event)
    {
         // change rendering of life/player in the gui
    }

    void handle_lvl_up(const PLAYER_LVL_UP& event)
    {
        // change rendering of the lvl in the gui
    }

    ...
};

struct CollisionSystem : public System<CollisionSystem>
{
     .
     .
     void update(EventManager& em, float dt)
     {
         .
         .
         if (collides(entity1, entity2))
             em.emit(COLLISION{entity1, entity2});
     }
};

Obviously, this code snippet lacks a lot of things but at the moment I am mostly concerned with the approach taken. Specifically, I am not particularly sure about using static functions to map the event types to integers. I would really appreciate some general guidance in the right direction!

My suggestions:

Move type_count from being a public member

type_count plays an important role in the event manager. Making such a crucial part of the event management system a publically accessible member variable seems risky to me.

I would make that accessible only as a protected member function.

struct BaseEvent
{
   virtual ~BaseEvent() {}
   protected:
      static size_t getNextType();
};

size_t BaseEvent::getNextType()
{
   static size_t type_count = 0;
   return type_count++;
}

Of course, change Event appropriately.

template <typename EventType>
struct Event : BaseEvent
{
   static size_t type()
   {
      static size_t t_type = BaseEvent::getNextType();
      return t_type;
   } //; You don't need this semi-colon. Remove it.
};

Change the implementation of EventManager to simply event classes

Instead of

struct PLAYER_LVL_UP : Event<PLAYER_LVL_UP>
{ int new_level; };

struct PLAYER_HIT : Event<PLAYER_HIT>
{ int damage; };

struct COLLISION : Event<COLLISION>
{ Entity entity1; Entity entity2; };

it's cleaner to have:

struct PLAYER_LVL_UP
{ int new_level; };

struct PLAYER_HIT
{ int damage; };

struct COLLISION
{ Entity entity1; Entity entity2; };

You can accomplish that by updating EventManager to:

struct EventManager
{
   template <class EventType>
      using call_type = std::function<void(const EventType&)>;

   template <typename EventType>
      void subscribe(call_type<EventType> callable)
      {
         // When events such as COLLISION don't derive
         // from Event, you have to get the type by
         // using one more level of indirection.
         size_t type = Event<EventType>::type();
         if (type >= m_subscribers.size())
            m_subscribers.resize(type+1);
         m_subscribers[type].push_back(CallbackWrapper<EventType>(callable));
      }

   template <typename EventType>
      void emit(const EventType& event)
      {
         // Same change to get the type.
         size_t type = Event<EventType>::type();
         if (type >= m_subscribers.size())
            m_subscribers.resize(type+1);

         // This a crucial change to the code.
         // You construct a temporary Event object by
         // using the EventType object and use Event.
         // This requires a change to Event, which follows below.
         Event<EventType> eventWrapper(event);
         for (auto& receiver : m_subscribers[type])
            receiver(eventWrapper);

      }

   template <typename EventType>
      struct CallbackWrapper
      {
         CallbackWrapper(call_type<EventType> callable) : m_callable(callable) {}

         void operator() (const BaseEvent& event) {
          // The event handling code requires a small change too.
          // A reference to the EventType object is stored
          // in Event. You get the EventType reference from the
          // Event and make the final call.
          m_callable(static_cast<const Event<EventType>&>(event).event_); }

         call_type<EventType> m_callable;
      };

   std::vector<std::vector<call_type<BaseEvent>>> m_subscribers;
};

The updated Event class:

template <typename EventType>
struct Event : BaseEvent
{
   static size_t type()
   {
      static size_t t_type = BaseEvent::getNextType();
      return t_type;
   }
   Event(const EventType& event) : event_(event) {}
   const EventType& event_;
};


Graph and minimum spanning tree in Python Here is my Graph class that implements a graph and has nice a method to generate its spanning tree using Kruskal's algorithm.

I want to:

Make it pythonic
Improve readability
Improve the abstraction (but not changing the use of outer and inner dicts to represent the graph)

Performance is not a concern.

Code:

class Graph(object):
    def __init__(self):
        self.g = {}

    def add(self, vertex1, vertex2, weight):
        if vertex1 not in self.g:
            self.g[vertex1] = {}

        if vertex2 not in self.g:
            self.g[vertex2] = {}

        self.g[vertex1][vertex2] = weight
        self.g[vertex2][vertex1] = weight

    def has_link(self, v1, v2):
        return v2 in self[v1] or v1 in self[v2]

    def edges(self):
        data = []

        for from_vertex, destinations in self.g.items():
            for to_vertex, weight in destinations.items():
                if (to_vertex, from_vertex, weight) not in data:
                    data.append((from_vertex, to_vertex, weight))

        return data

    def sorted_by_weight(self, desc=False):
        return sorted(self.edges(), key=lambda x: x[2], reverse=desc)

    def spanning_tree(self, minimum=True):
        mst = Graph()
        parent = {}
        rank = {}

        def find_parent(vertex):
            while parent[vertex] != vertex:
                vertex = parent[vertex]

            return vertex

        def union(root1, root2):
            if rank[root1] > rank[root2]:
                parent[root2] = root1
            else:
                parent[root2] = root1

                if rank[root2] == rank[root1]:
                    rank[root2] += 1

        for vertex in self.g:
            parent[vertex] = vertex
            rank[vertex] = 0

        for v1, v2, weight in self.sorted_by_weight(not minimum):
            parent1 = find_parent(v1)
            parent2 = find_parent(v2)

            if parent1 != parent2:
                mst.add(v1, v2, weight)
                union(parent1, parent2)

            if len(self) == len(mst):
                break

        return mst

    def __len__(self):
        return len(self.g.keys())

    def __getitem__(self, node):
        return self.g[node]

    def __iter__(self):
        for edge in self.edges():
            yield edge

    def __str__(self):
        return "\n".join('from %s to %s: %d' % edge for edge in self.edges())

graph = Graph()

graph.add('a', 'b', 2)
graph.add('a', 'd', 3)
graph.add('a', 'c', 3)

graph.add('b', 'a', 2)
graph.add('b', 'c', 4)
graph.add('b', 'e', 3)

graph.add('c', 'a', 3)
graph.add('c', 'b', 4)
graph.add('c', 'd', 5)
graph.add('c', 'e', 1)

graph.add('d', 'a', 3)
graph.add('d', 'c', 5)
graph.add('d', 'f', 7)

graph.add('f', 'd', 7)
graph.add('f', 'e', 8)
graph.add('f', 'g', 9)

print(graph.spanning_tree())
print()
print(graph.spanning_tree(False))

There are no docstrings. How do I use this class? What arguments should I pass to the methods and what do they return?
There's no way to add a vertex with no edges to a graph.
The test code shows that it is quite laborious to initialize a graph. It would make sense for the constructor to take an iterable of edges.
The attribute g is not intended for use outside the class (callers should use the public methods). It is conventional to name internal attributes with names starting with one underscore.
The code in add could be simplified by making use of collections.defaultdict:

def __init__(self, edges=()):
    """Construct a graph containing the edges from the given iterable.
    An edge between vertices v1 and v2 with weight w should be
    specified as a tuple (v1, v2, w).

    """
    self._g = defaultdict(dict)
    for edge in edges:
        self.add(*edge)

def add(self, v1, v2, w):
    """Add an edge between vertices v1 and v2 with weight w.
    If an edge already exists between these vertices, set its
    weight to w.

    """
    self._g[v1][v2] = self._g[v2][v1] = w

The has_link method uses "link", but the rest of the code uses "edge". It would be better to be consistent.
The __getitem__ method uses "node", but the rest of the code uses "vertex". It would be better to be consistent.
Since add ensures that edges are stored in both directed, it's only necessary to test one direction:

def has_edge(self, v1, v2):
    """Return True if the graph has an edge between vertices v1 and v2."""
    return v2 in self._g[v1]

The edges method accumulates a list of edges. To avoid an edge appearing twice, the code checks each edge to see if it is already in the list. But lists do not have an efficient membership test, so the runtime is quadratic in the number of edges. It would be more efficient to make a set of edges:

def edges(self):
    """Return the edges in the graph as a set of tuples (v1, v2, w)."""
    edges = set()
    for v1, destinations in self._g.items():
        for v2, w in destinations.items():
            if (v2, v1, w) not in edges:
                edges.add((v1, v2, w))
    return edges

In the sorted_by_weight method, it would be better to name the keyword argument reverse, for consistency with Python's built-in sorted.
In spanning_tree, the parent and rank dictionaries can be initialized directly:

parent = {v: v for v in self._g}
rank = {v: 0 for v in self._g}

The parent data structure is known as a disjoint-set forest. An important optimization on this data structure is path compression: that is, when you search the parent data structure for the root of the tree containing a vertex, you update the parent data structure so that future searches run quickly:

def find_root(v):
    if parent[v] != v:
        parent[v] = find_root(parent[v])
    return parent[v]

In the union function, you always attach the tree for root2 to the tree for root1:

if rank[root1] > rank[root2]:
    parent[root2] = root1
else:
    parent[root2] = root1

It's more efficient to always attach the smaller tree to the bigger tree, so that the length of the searches in find_root doesn't increase:

if rank[root1] > rank[root2]:
    parent[root2] = root1
else:
    parent[root1] = root2

The __len__ and __getitem__ methods treat the graph as a collection of vertices, but __iter__ treats it as a collection of edges. This seems likely to lead to confusion. It would be better to be consistent and have all special methods treat the graph as a collection in the same way.


Sensing when a network is available The code below just senses when the network is available and enables/disables a button on the UI. If I am registered to the NetworkAvailability event for the life of the program, will it cause a memory leak? I heard it might but didn't understand why.

System.Net.NetworkInformation.NetworkChange.NetworkAvailabilityChanged += new System.Net.NetworkInformation.NetworkAvailabilityChangedEventHandler(NetworkChange_NetworkAvailabilityChanged);

delegate void EnableCallback();

void NetworkChange_NetworkAvailabilityChanged(object sender, System.Net.NetworkInformation.NetworkAvailabilityEventArgs e)
{
    EnableSync();
    //throw new NotImplementedException();
}

private void EnableSync()
{
    if (this.btnSync.InvokeRequired)
    {
        EnableCallback methodCallback = new EnableCallback(EnableSync);
        this.Invoke(methodCallback, new object[] { });
    }
    else
    {
        if (btnSync.Enabled == true)
            btnSync.Enabled = false;
        else
            btnSync.Enabled = true;
    }
}

Well, if it's for the life of the program as you say, then no. When the program ends, all memory will be released.

Second, this all looks like one class. So root references will be removed when the class is GC'd and no memory leak will occur.

Lastly, write

        if (btnSync.Enabled == true)
            btnSync.Enabled = false;
        else
            btnSync.Enabled = true;

as

        btnSync.Enabled = !btnSync.Enabled;

Much more concise.


LeetCode 399: Evaluate Division I'm posting my C++ code for LeetCode's Evaluate Division. If you have time and would like to review, please do so. Thank you!
Problem

Equations are given in the format A / B = k, where A and B are
variables represented as strings, and k is a real number (floating
point number). Given some queries, return the answers. If the answer
does not exist, return -1.0.
Example: Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a
= ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].
The input is: vector<pair<string, string>> equations, vector&
values, vector<pair<string, string>> queries , where equations.size()
== values.size(), and the values are positive. This represents the equations. Return vector.
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries =
[ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries
will result in no division by zero and there is no contradiction.

Accepted C++
class Solution {
public:
    std::vector<double> calcEquation(std::vector<vector<string>> equations, std::vector<double> values, std::vector<vector<string>> const& queries) {
        generate_graph(equations, values);
        std::vector<double> evaluates;

        for (auto& query : queries) {
            std::set<string> visited;
            double accumulated = 1.0;
            bool evaluate = solve_equation(query[0], query[1], accumulated, visited);

            if (evaluate) {
                evaluates.push_back(accumulated);

            } else {
                evaluates.push_back(-1);
            }
        }

        return evaluates;
    }

protected:
    struct Node {
        Node(std::string const parameter, double const evaluate) {
            this -> parameter = parameter;
            this -> evaluate = evaluate;
        }

        std::string parameter;
        double evaluate;
    };

    map<string, vector<Node>> graph;

    void generate_graph(std::vector<vector<string>>& equations, std::vector<double>& values) {
        for (auto const& equation : equations) {
            vector<Node> children;
            graph[equation[0]] = children;
        }

        for (int equation = 0; equation < equations.size(); equation++) {
            Node node(equations[equation][1], values[equation]);
            graph[equations[equation][0]].push_back(node);

            Node node_reverse(equations[equation][0], 1 / values[equation]);
            graph[equations[equation][1]].push_back(node_reverse);
        }
    }

    bool solve_equation(std::string const nominator, std::string const denominator, double& accumulated, std::set<string>& visited) {
        if (nominator == denominator && graph.find(nominator) != graph.end()) {
            return true;
        }

        if (graph.find(nominator) == graph.end() || graph.find(denominator) == graph.end()) {
            return false;
        }

        visited.insert(nominator);

        for (auto& child : graph[nominator]) {
            if (visited.find(child.parameter) == visited.end()) {
                accumulated *= child.evaluate;

                if (child.parameter == denominator) {
                    return true;
                }

                if (solve_equation(child.parameter, denominator, accumulated, visited)) {
                    return true;

                } else {
                    accumulated /= child.evaluate;
                }
            }
        }

        return false;
    }

};

Reference
On LeetCode, there is an instance usually named Solution with one or more public functions which we are not allowed to rename those.

Question
Discussion

Seems basically reasonable. Some English nits: You said "nominator and denominator," when the English terms are "numerator and denominator." You also seem to be using the word "evaluate(s)" as a noun (something like "precipitate" in chemistry), when I think the word you meant was more like "value(s)."

struct Node {
    Node(std::string const parameter, double const evaluate) {
        this -> parameter = parameter;
        this -> evaluate = evaluate;
    }

    std::string parameter;
    double evaluate;
};

Write this->x, not this -> x, for the same reason you write st.x and not st . x. But in fact, this constructor would be better written as either
struct Node {
    explicit Node(const std::string& p, double v) : parameter(p), value(v) {}
    std::string parameter;
    double value;
};

or simply
struct Node {
    std::string parameter;
    double value;
};

since simple aggregates can already be initialized with e.g. Node{"a", 2}. Notice that I'm passing std::string by const reference, because it is expensive to copy.
You could actually rewrite all of the helper functions and data structures to use C++17 std::string_view instead of std::string, as long as all the stringviews referred to the original long-lived strings from equations and queries which you are appropriately careful not to modify. This would be an "advanced" idea, though, and probably wouldn't even buy you any speed in this case where all your strings seem to be 1 character long.

for (auto& query : queries) — Use for (const auto& query : queries) to indicate that the const-qualification is on purpose; or use auto&& in generic code if you just want something that always works. I don't see any reason to use specifically auto& to get a specifically const-qualified result.

        if (visited.find(child.parameter) == visited.end()) {
            accumulated *= child.evaluate;

            if (child.parameter == denominator) {
                return true;
            }

            if (solve_equation(child.parameter, denominator, accumulated, visited)) {
                return true;

            } else {
                accumulated /= child.evaluate;
            }
        }

This if-else ladder is indeed confusing. I would write it like this:
        if (visited.find(child.parameter) != visited.end()) {
            // we have already visited this node; skip it
        } else if (child.parameter == denominator) {
            // we've reached our destination node and resolved the query
            accumulated *= child.value;
            return true;
        } else if (solve_equation(child.parameter, denominator, accumulated, visited)) {
            // this node is on a path that resolves the query
            accumulated *= child.value;
            return true;
        } else {
            // this node is not involved in the solution; do nothing
        }

The most confusing part of the original ladder was
            } else {
                accumulated /= child.evaluate;
            }

That line is really just undoing the multiplication hidden at the top of the loop. But the multiplication is done one scope higher than it is undone, which violates most programmers' intuition. It would have been a simple fix to write
        if (visited.find(child.parameter) == visited.end()) {
            accumulated *= child.evaluate;
            if (child.parameter == denominator) {
                return true;
            }
            if (solve_equation(child.parameter, denominator, accumulated, visited)) {
                return true;
            }
            accumulated /= child.evaluate;
        }

thus visually indicating the symmetry between *= and /=.

bool solve_equation(std::string const nominator,
    std::string const denominator, double& accumulated,
    std::set<string>& visited)

Consider whether visited should be a data member of class Solution.
Passing by const value is always a bug; you left off the &. If you used west const style, you could use these git grep lines to find such bugs: https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/
Consider whether the return type of this function should be std::pair<bool, double>; or, in C++17, std::optional<double>.
Put it all together and you get a C++14 signature like
std::pair<bool, double> solve_equation(const std::string& numerator,
                                       const std::string& denominator);

or a C++17 signature like
std::optional<double> solve_equation(std::string_view numerator,
                                     std::string_view denominator);

You have methods named both calcEquation and solve_equation. Admittedly, the name calcEquation is just flat wrong; it should be something like solve_equations (plural). But, given that you aren't allowed to change the public name, personally I would go with calcEquation and calcSingleEquation — reusing the same verb instead of a near-synonym, and emphasizing that this function calculates for a single equation, since I don't have the option of adding an s to pluralize the public name.


Simple Cache Mechanism I have this simple cache mechanism for a repeated task in service. It uses static variable to store the information. Please suggest on how is it and if it could be better.

Premise: I need to verify transaction from stores. There can be lots of transactions happening repeatedly from multiple stores. Thus, this simple cache manager for getting the store information. I want it to be simple yet effective and fast.

StoreCacheManager.cs

public class StoreCacheManager
{
    private static List<StoreCacheInformation> _merchantStores = new List<StoreCacheInformation>();
    private DBEntities _db;
    private TimeSpan _cacheTime = new TimeSpan(1, 0, 0);//1 Hour
    public TimeSpan CacheTimeSpan { get { return _cacheTime; } }
    public StoreCacheManager(DBEntities db)
    {
        _db = db;
    }

    public async Task<StoreCacheInformation> Get(int storeId)
    {
        if (_merchantStores.Any())
        {
            var store =
                _merchantStores.FirstOrDefault(i => i.StoreID == storeId);
            if (store != null)
            {
                // Check if Cache time has expired
                if (store.CacheDateTimeUtc.Add(_cacheTime) < DateTime.UtcNow)
                {
                    lock (_merchantStores)
                    {
                        _merchantStores.Remove(store);
                    }
                }
                else
                {
                    return store;
                }
            }
        }
        return await GetAndCache(storeId);
    }

    private async Task<StoreCacheInformation> GetAndCache(int storeId)
    {
        var store = await GetStoreInfo(storeId);
        if (store != null)
        {
            lock (_merchantStores)
            {
                _merchantStores.Add(store);
            }
        }
        return store;
    }
    private async Task<StoreCacheInformation> GetStoreInfo(int storeId)
    {
        var storeInfo = await _db.Stores.Where(i => i.StoreID == storeId).Select(i => new StoreCacheInformation()
        {
            CountryCode = i.CountryObj.CountryCode,
            MerchantID = i.VendorOrgID ?? 0,
            TelephoneCode = i.CountryObj.TelephoneCountryCode,
            StoreID = storeId,
            //todo: deviceId and Token

        }).FirstOrDefaultAsync();
        if (storeInfo != null)
        {
            storeInfo.CacheDateTimeUtc = DateTime.UtcNow;
        }
        return storeInfo;
    }
}

StoreCacheInformation.cs

public class StoreCacheInformation
{
    public int MerchantID { get; set; }
    public int StoreID { get; set; }
    public string TelephoneCode { get; set; }
    public string CountryCode { get; set; }
    public DateTime CacheDateTimeUtc { get; set; }
    public string DeviceId { get; set; }
    public string AuthToken { get; set; }
}

Concurrency

If you want to implement it thread-safe, you have also lock the whole transaction. For instance: store != null assumes that there is no item in cache. Imagine that after that check another thread added one. That would result in a cache where the same item is cached twice.

Conside to use a thread-safe collection (e.g. ConcurrentDictionary) instead of using locking.

.Net Framework already provides a thread-safe cache: MemoryCache.

I am not very familiar with the entity framework, but as far as I know is the DbContext not thread-safe. Therefore it is not a good idea to use a single instance of it in multithreaded environments.

Code Style

_merchantStores, _db and _cacheTime should be read-only.
Methods that return a Task should be called xxxAsync
The property setter in StoreCacheInformation should be private or at least internal. Otherview external code may modify the state of the cached items.
For many cached items, it is better to use a dictionary instead of list.


Turning a flat nested set into a hierarchy So I have categories in my database and I've implemented the Nested set model. I'm reading the categories as a flat structure and then I'm turning it into a hierarchy in memory, mapping each entity to a DTO.

Here's my code:

public async Task<IActionResult> GetCategories()
{
    var categories = (List<Category>)await _categoryService.GetAllAsync();

    var categoryDtos = GetCategoryDtosHierarchy(categories, null);

    categoryDtos.RemoveAll(x => x.Depth > 0); // Terrible

    return Ok(categoryDtos);
}

private List<CategoryDto> GetCategoryDtosHierarchy(List<Category> categories, Category parent)
{
    var categoryDtos = new List<CategoryDto>();
    var filteredCategories = categories;

    if (parent != null)
    {
        filteredCategories = categories.Where(x => x.Depth == (parent.Depth + 1) &&
                                                   x.Left > parent.Left &&
                                                   x.Right < parent.Right).ToList();
    }

    foreach (Category filteredCategory in filteredCategories)
    {
        var categoryDto = new CategoryDto
        {
            Id = filteredCategory.Id,
            Name = filteredCategory.Name,
            Depth = filteredCategory.Depth,
            SubCategories = GetCategoryDtosHierarchy(categories, filteredCategory)
        };

        categoryDtos.Add(categoryDto);
    }

    return categoryDtos;
}

So everything works but it feels like somewhat an awkward solution. When the GetCategoryDtosHierarchy(categories, null); line returns it not only returns the categories with their subcategories but every level below like so:

[
  {
    "name": "Clothing",
    "depth": 0,
    "subcategories": [
      {
        "name": "Men's",
        "depth": 1,
        "subcategories": [
          {
            "name": "Suits",
            "depth": 2,
            "subcategories": []
          }
        ]
      },
      {
        "name": "Women's",
        "depth": 1,
        "subcategories": []
      }
    ]
  },
  {
    "name": "Men's", // Not supposed to be here
    "depth": 1,
    "subcategories": [
      {
        "name": "Suits",
        "depth": 2,
        "subcategories": []
      }
    ]
  },
  {
    "name": "Women's", // Not supposed to be here
    "depth": 1,
    "subcategories": []
  },
  {
    "name": "Suits", // Not supposed to be here
    "depth": 2,
    "subcategories": []
  }
]

And it has forced me to run the categoryDtos.RemoveAll(x => x.Depth > 0); in order to get rid of the excess. I've thought about putting both calls in a new method but I feel like there might be a better solution than this hack.

What about idea (and removing categoryDtos.RemoveAll(x => x.Depth > 0); // Terrible):

if (parent != null)
{
    filteredCategories = categories.Where(x => x.Depth == (parent.Depth + 1) &&
                                               x.Left > parent.Left &&
                                               x.Right < parent.Right).ToList();
}
else
{
    filteredCategories = categories.Where(x => x.Depth == 0).ToList();
}

Or, if the function is used somwhere else as well, maybe additional parameter to function like bool onlyTopLevel.


Adding a bulk of items in the middle of a sparse array I'd like to add a bulk of items into a sparse array, starting at a certain index.
I came along this requirement in order to accomplish client side pagination while not retrieving all data from server (assuming server returns the right data, given the required indexes).

To keep right indexes when "Skipping" and "Taking", I need to store the items in a sparse array. Besides relevant indexes, other places in array might as well be undefined.

I wrote the following snippet of code, assuming bulk is the retrieved chunk of items from Server, and index is where the first item should be placed.

    items = new Array(totalItemsPossibleCount);
    items = items.slice(-index)
                 .concat(bulk)
                 .concat(items.slice(index+bulk.length));

Is there a shorter way to do so?
Can this be achieved with underscore.js in more readable way?

You don't need to worry about sparse arrays in JavaScript and there is no need to instantiate with the Array constructor. If you insert into a random index then the rest of the array is just padded with undefined references:

var items = [];
items[5] = 'foo';
console.log(items); // [5: "foo"]
items.toString();   // ",,,,,foo"

To add new items into the middle of an array you can use the splice function:

items.splice(index, 0, bulk);

The index is where to start adding items, 0 is how many items to remove after that point, and bulk is the new items to add at that point. Splice acts on the array directly, and returns any items that were removed.


Modifying an array during a foreach loop This question is always on my mind. I usually alter the array while looping through its keys, based on my gut feelings:

foreach (array_keys($array) as $key) {
  $array[$key] = perform_changes_on($array[$key]);
}

I'm aware of other methods, though. The array item can be passed by reference on the foreach call:

foreach ($array as &$item) {
  $item = perform_changes_on($item);
}

Finally, the array can be modified directly during the loop:

foreach ($array as $key => $value) {
    $array[$key] = perform_changes_on($value);
}

What are the performance and security implications of each approach? Is there a recommended approach?

UPDATE: What I'm actually worried about is that the two last approaches modify the array while I'm looping it.

If you are worried about modifying the array while looping, don't because foreach copies the array. Try

$array = array('foo');
foreach ($array as $k => &$item) {
  $array[] = 'bar';
}
var_dump($array);

And see it terminates just fine. foreach ($array as $k => &$v) is a shorthand for foreach (array_keys($array) as $k) $v = &$array[$k] so while there still is a copy of the array (that's why I used &$item in my example so you can see, if you modify the array then it'll be modified in the reference!

$array = array('foo', 'bar');
foreach ($array as $k => $item) {
  echo "$item\n";
  if (!$k) {
    $array[1] = 'baz';
  }
}
$array = array('foo', 'bar');
foreach ($array as $k => &$item) {
  echo "$item\n";
  if (!$k) {
    $array[1] = 'baz';
  }
}

the first dump foo and bar, the second foo and baz.


FizzBuzz Problem Solution I wrote this simple solution about FizzBuzz. Is there any possible way to solve or optimize the solution, such as with bitwise tricks?

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

    for(int i = 1 ; i <= 100 ; ++i){
      if(i % (5*3) == 0){
        System.out.println("FizzBuzz");
      }else if(i % 3 == 0){
        System.out.println("Fizz");
      }else if(i % 5 == 0){
        System.out.println("Buzz");
      }else
        System.out.println(i);
    }
  }
}

That's a classic FizzBuzz solution.  I wouldn't try to do any clever optimization — it won't make any difference to performance.  One hundred iterations of anything is trivial for a computer.  Furthermore, most of the time will be dominated by the output routines, which you can't do much about.

The code formatting, on the other hand, could be improved.  The most glaring issue is the omission of the braces for the final else.  Why make your code ugly to save a couple of bytes?

Also note a de facto formatting convention: Put a space after if and for, and before any opening { brace.


Ruby on rails complex select statement...there has to be a better way! I am building a query that could end up look like this:

SELECT "patients".* FROM "patients"
INNER JOIN "users" ON "users"."id" = "patients"."user_id"
WHERE (users.username LIKE '%Bob%' AND users.last_name LIKE '%Smith%'
AND users.active = '1' AND users.disabled = '1')
ORDER BY users.first_name DESC LIMIT 10 OFFSET 0

Below is code to create a complex query such as:

conditions = []
where = ''
where_parameters = []
order = 'users.last_name ASC'
per_page = 20

if is_admin?
  if defined?(params[:username]) and !params[:username].blank?
    where += 'users.username LIKE ? AND '
    where_parameters.push("%#{params[:username]}%")
  end

  if defined?(params[:last_name]) and !params[:last_name].blank?
    where += 'users.last_name LIKE ? AND '
    where_parameters.push("%#{params[:last_name]}%")
  end

  if defined?(params[:active]) and !params[:active].blank?
    where += 'users.active = ? AND '
    where_parameters.push(params[:active])
  end

  if defined?(params[:disabled]) and !params[:disabled].blank?
    where += 'users.disabled = ? AND '
    where_parameters.push(params[:disabled])
  end

  if !where.empty?
    where = where[0, where.length - 5]
    conditions = [where, *where_parameters]
  end

  if defined?(params[:order_by]) and !params[:order_by].blank?
    order = params[:order_by] + ' '
  end

  if defined?(params[:order]) and !params[:order].blank?
    order += params[:order]
  end

  if defined?(params[:per_page]) and !params[:per_page].blank?
    per_page = params[:per_page].to_i
  end
  @patients = Patient.joins(:user).paginate(:all, :include =>:user, :conditions => conditions, :order => order, :page => params[:page], :per_page => per_page)

Is there a better way to do this, this is just ugly?

First of all be very careful when building queries from request data. When building your where string, you're using parametrized queries, so that's fine. But in your order string, you're building actual SQL code from data you directly take out of params. Do NOT do that. This is a big risk of SQL injection.

What you should do instead is take the order string apart (splitting at the comma), then check that each element is a column name optionally followed by ASC or DESC, then put the string back together accordingly.

A method for this could look something like this:

def safe_order_from_param(collection, order_string)
  tokens = order_string.split(/ *, */)
  tokens.each do |token|
    column, direction = token.match(/^(\w+)(? +(\w+))?$/).captures
    if Patient.column_names.include? column
      # if direction is nil, it will just be turned into the empty
      # string, so no problem there
      collection = collection.order("#{column} #{direction}")
    else
      raise ArgumentError, "No such column: #{column}"
    end
  end
end

Second of all defined?(params[:foo]) does is check that params is defined. It does not check that params is a hash and has the key :foo. Since params will always exist, there really is no need for the check. Checking params[:foo].blank? is entirely sufficient.

Now to the main part of your question: the ugly building of the query string:

I assume from the fact that you're using the joins method that this is rails 3. In rails 3 options like :include, :conditions and :order are deprecated in favor of the corresponding query methods. The beauty of those methods is that they're chainable. So instead of building a query string using concatenation, it is much cleaner to just chain together multiple wheres.

if is_admin?
  @patients = Patient.joins(:user).includes(:user).order('users.last_name ASC')

  unless params[:username].blank?
    @patients = @patients.where("users.username LIKE ?", params[:username])
  end

  # same for :last_name

  unless params[:active].blank?
    @patients = @patients.where("users.active" => params[:active])
  end

  # same for disabled

  unless params[:order_by].blank?
    @patients = safe_order_from_param(@patients, params[:order_by])
  end

  # same for order

  per_page = params[:per_page].blank? ? 20 : params[:per_page].to_i
  @patients = @patients.paginate(:page => params[:page], :per_page => per_page)
end


Single pass algorithm for finding the topX percent of items I'm looking for a single-pass algorithm for finding the topX percent of floats in a stream where I do not know the total number ahead of time ... but its on the order of 5-30 million floats. It needs to be single-pass since the data is generated on the fly and recreate the exact stream a second time.

The algorithm I have so far is to keep a sorted list of the topX items that I've seen so far. As the stream continues I enlarge the list as needed. Then I use bisect_left to find the insertion point if needed.

Below is the algorithm I have so far:

from bisect import bisect_left
from random import uniform
from itertools import islice

def data_gen(num):
    for _ in xrange(num):
        yield uniform(0,1)

def get_top_X_percent(iterable, percent = 0.01, min_guess = 1000):

    top_nums = sorted(list(islice(iterable, int(percent*min_guess)))) #get an initial guess

    for ind, val in enumerate(iterable, len(top_nums)):
        if int(percent*ind) > len(top_nums):
            top_nums.insert(0,None)
        newind = bisect_left(top_nums, val)
        if newind > 0:
            top_nums.insert(newind, val)
            top_nums.pop(0)

    return top_nums

if __name__ == '__main__':

    num = 1000000
    all_data = sorted(data_gen(num))
    result = get_top_X_percent(all_data)
    assert result[0] == all_data[-int(num*0.01)], 'Too far off, lowest num:%f' % result[0]
    print result[0]

In the real case the data does not come from any standard distribution (otherwise I could use some statistics knowledge).

Any suggestions would be appreciated.

top_nums = sorted(list(islice(iterable, int(percent*min_guess)))) #get an initial guess

There is no reason to make a list out of it before you sort it.

for ind, val in enumerate(iterable, len(top_nums))

I dislike abbreviations. I think it makes it harder to figure out what ind and val are doing.

   all_data = sorted(data_gen(num))

Why are you sorting your test data?

As I understand your problem, your code is wrong. It only works in your test case because you sort the incoming data.

Your algorithm regularly increases the size of the list of values. But when it does so, there have been previous numbers which have been thrown away which may greater then the value you insert at that point. As a result, you cannot be sure you've actually ended up with with the top 1%.

How should you fix it? If you can upper bound the size of your input, then you can start with a list of sufficient size and then scale back at the end. Otherwise I don't think you can do it. The problem being that you cannot throw away any values because there is no way to be sure you won't need them later.

You might consider using a heap. Python has a heapq module including a function heapq.nlargest which does pretty much what you are doing, (but uses a count rather then a percentage) A heap is pretty much a semi-sorted list and lets you do things like find/remove/replace the lowest value without the overhead of actually sorting.


Counting friends of friends of friends Can you comment, review or suggest things for this? Maybe it should be broken into two methods?

friends is a list of strings of 'T' or 'F' characters representing a friendship relation.

For example for 3 people we could have

friends = ['FTF','TFT','FTF']

This means that

person 0 is friends with person 1 (since friends[0][1] == 'T'),
person 1 is friends with both person 0 and person 2 and
person 2 is friends with person 1.

The method below finds the number of friends, friends of friends and friends of friends of friends of a person for each person as well as the person with the highest such count

def mostThreeFriends(self,friends):
    best = 0
    self.nFriends = {}
    for i in range(0,len(friends)):
        count = 0
        for j in range(0,len(friends[i])):
            if i == j:
                continue
            # direct friends
            if friends[i][j] == 'T':
                count += 1
            else:
                doneCounting3 = False
                # check whether i and j have a friend k in common
                for k in range(0, len(friends)):
                    if doneCounting3:
                        break
                    if k == i or k == j:
                        continue
                    if friends[i][k] == 'T' and friends[j][k] == 'T':
                        count += 1
                        break
                    else:
                        for p in range(0, len(friends)):
                            if p == k or p == i:
                                continue
                            if friends[i][p] == 'T' and friends[p][k] == 'T' and friends[k][j] == 'T':
                                count += 1
                                doneCounting3 = True
                                break
        self.nFriends[i] = count
        best = max(best, count)

    return best

There seems to be no reason to define self.nFriends as an instance variable. Define it instead as a function local one.

Then you have no use for the self parameter, so consider making it a stand-alone function, or at least a staticmethod.

Stick to PEP 8. No reason not to. I'll be working with a PEP 8-ified version of the code.

Instead of initializing best and doing a manual reduction with max, instead make a count_three_friends iterable and use max to reduce it:

def count_three_friends(friends):
    n_friends = {}
    for i in range(0, len(friends)):
        ...
        n_friends[i] = count
        yield count

def most_three_friends(friends):
    return max(count_three_friends(friends))

n_friends is not used. Remove it.

You can flatten this a bit by taking account of early loop exits:

def count_three_friends(friends):
    for i in range(0, len(friends)):
        count = 0
        for j in range(0, len(friends[i])):
            if i == j:
                continue
            # direct friends
            if friends[i][j] == 'T':
                count += 1
                continue

            done_counting3 = False
            # check whether i and j have a friend k in common
            for k in range(0, len(friends)):
                if done_counting3:
                    break
                if k == i or k == j:
                    continue
                if friends[i][k] == 'T' and friends[j][k] == 'T':
                    count += 1
                    break
                for p in range(0, len(friends)):
                    if p == k or p == i:
                        continue
                    if friends[i][p] == 'T' and friends[p][k] == 'T' and friends[k][j] == 'T':
                        count += 1
                        done_counting3 = True
                        break

        yield count

Change range(0, ...) to just range(...).

Try to use enumerate and replace 'T'/'F' with booleans. I'll initially use enumerate and discard the second parameter to keep the transition small.

Then consider that your structure is

for each person:
    and each other person:
        if friends, count += 1
        or indirect friends, count += 1

The "or indirect friends" bit could be a separate function to avoid the done_counting3 variable:

def indirect_friend(friends, i, j):
    for k, _ in enumerate(friends):
        if k == i or k == j:
            continue

        # If  friends[i] is friends with friends[k]
        # and friends[j] is friends with friends[k]
        if friends[i][k] and friends[j][k]:
            return True

        for p, _ in enumerate(friends):
            if p == k or p == i:
                continue

            if friends[i][p] and friends[p][k] and friends[k][j]:
                return True

def count_three_friends(friends):
    for i, _ in enumerate(friends):
        count = 0

        for j, _ in enumerate(friends):
            # Don't look at self-friending
            if i == j:
                continue

            # Direct or once-indirect friend
            if friends[i][j] or indirect_friend(friends, i, j):
                count += 1

        yield count

def most_three_friends(friends):
    return max(count_three_friends(friends))

Note that

# If  friends[i] is friends with friends[k]
# and friends[j] is friends with friends[k]

seems to be wrong; this means

most_three_friends([[0, 1, 0], [0, 0, 0], [0, 1, 0]])

gives 2 despite no person's friend having any friends. This of course will only happen if the friendship graph is non-symmetric, but you've not required that it is.

I suggest reversing the second line to

# and friends[k] is friends with friends[j]

by changing friends[j][k] to friends[k][j].

Now, instead of getting deeper into how this could be improved, I'm going to express this as a matrix transformation. Consider the matrix X.

[[X, X, X],
 [X, X, X],
 [X, X, X]]

The kth person's list of friends is the list X[k, :] - take a single of the first dimension and the first of the second.

The matrix X[k, :, newaxis] in Numpy is thus the same with another dimension:

[[a],
 [b],
 [c]]

Now, this can be multiplied with the original as

[[a],     [[X, X, X],     [[a*X, a*X, a*X],
 [b],  *   [X, X, X],  =   [b*X, b*X, b*X],
 [c]]      [X, X, X]]      [c*X, c*X, c*X]]

This operation thus filters the friend list by the person's friends. You can then do an any along the y-axis to find once-indirect friends.

(friends[k, :, newaxis] * friends).any(axis=1)

The magic of Numpy's broadcasting lets us do all k at the same time by just taking a slice.

(friends[:, :, newaxis] * friends).any(axis=1)

This is a bit cryptic, but it's also an extremely powerful way of modelling the situation. For example, to calculate the transitive closure of friendship (find the number of people you are friends through any number of indirections), such a model becomes extremely helpful.

To use this, one could do

from numpy import array, identity, newaxis

def friend_problem(friends, iterations=2):
    # Include self-friendships for transitivity
    graph = arcs = friends | identity(len(friends), dtype=bool)

    # Apply search to graph
    for _ in range(iterations):
        graph = (graph[:, :, newaxis] * arcs).any(axis=1)

    # Subtract one for the self-friendship
    return graph.sum(axis=-1).max() - 1

And call it with

friends = array([[0, 1, 0], [0, 0, 0], [0, 0, 0]], dtype=bool)
friend_problem(friends)

Note that this works for any number of iterations; one can trivially do friends-of-friends-of-friends-of-friends-of-friends. This is not optimal for full transitive closure, but it's fine for small iteration counts. It's should also be a fair bit faster.


PHP login based on a password parameter I'm learning PHP now, and I'm trying to find out whether or not the following code structure has any faults:

$loggedIn = false;
if (isset($_GET["userpass"])){
    if (strcmp($_GET["userpass"], $correctPassword) == 0) {
        $loggedIn = true;
    }
}

To me, it seems pretty bullet-proof. If the password isn't set, then the code doesn't execute. And if it is, then the user actually has to supply the correct password. Anything obvious I'm missing?

Note:
$correctPassword is defined in an external file, not accesible to the public

Update:
Can the user of this website explit the script so that he can log in to any arbitrary account? As in, this piece of code always sets $loggedIn = true;

This is not secure at all.

Apart from the GET issue (use POST) and the hashing issue (use bcrypt) already mentioned, and the fact that == is not timing safe (use hash_equals), an attacker can log in without knowing the password like this:

login.php?userpass[]=1

The reason for this is that strcmp("STRING", [ARRAY]) returns NULL, and NULL == 0 is true. You should pretty much never use ==. Always use === for type-safe checks.


Building options for input fields In the _form partial I have a rather complicated logic which builds necessary options for input fields:

- input_html_params = dynamic_settings_select_options('#service-settings', settings_aps_instance_services_path(parent))

= simple_form_for [:aps, parent, resource] do |f|
  = f.input :service_status, :as => :readonly_label
  = f.input :meta_service_meta_id, :collection => parent.meta_services, :value_method => :meta_id, :label_method => :name, :input_html => input_html_params
  = f.button :submit

The first problem which I see here is getting input_html_params to pass them into input of meta_service_meta_id because it already has a lot of parameters. Even this didn't help us to avoid long string to pass all parameters. What is best practice to avoid this complicity?

As you can see, extracting them to helper methods doesn't solve this problem, so I would like to hear something new.

You should be able to use a Simple Form Custom Input.

As I don't know Simple Form well enough, I don't know if you can access the routes from a custom input class.

If not, see the answers to these questions:

Accessing Rails RESTful routes in the model

and

Rails, get resource path in model


Calculating shortest possible route between two given nodes I recently came across this problem:

  Heroes in Indian movies are capable of superhuman feats. For example,
  they can jump between buildings, jump onto and from running trains,
  catch bullets with their hands and teeth and so on. A perceptive
  follower of such movies would have noticed that there are limits to
  what even the superheroes can do. For example, if the hero could
  directly jump to his ultimate destination, that would reduce the
  action sequence to nothing and thus make the movie quite boring. So he
  typically labours through a series of superhuman steps to reach his
  ultimate destination.

  In this problem, our hero has to save his wife/mother/child/dog/...
  held captive by the nasty villain on the top floor of a tall building
  in the centre of Bombay/Bangkok/Kuala Lumpur/.... Our hero is on top
  of a (different) building. In order to make the action "interesting"
  the director has decided that the hero can only jump between buildings
  that are "close" to each other. The director decides which pairs of
  buildings are close enough and which are not.

  Given the list of buildings, the identity of the building where the
  hero begins his search, the identity of the building where the captive
  (wife/mother/child/dog...) is held, and the set of pairs of buildings
  that the hero can jump across, your aim is determine whether it is
  possible for the hero to reach the captive. And, if he can reach the
  captive he would like to do so with minimum number of jumps.

  Here is an example. There are 5 buildings, numbered 1,2,...,5, the
  hero stands on building 1 and the captive is on building 4. The
  director has decided that buildings 1 and 3, 2 and 3, 1 and 2, 3 and 5
  and 4 and 5 are close enough for the hero to jump across. The hero can
  save the captive by jumping from 1 to 3 and then from 3 to 5 and
  finally from 5 to 4. (Note that if i and j are close then the hero can
  jump from i to j as well as from j to i.). In this example, the hero
  could have also reached 4 by jumping from 1 to 2, 2 to 3, 3 to 5 and
  finally from 5 to 4. The first route uses 3 jumps while the second one
  uses 4 jumps. You can verify that 3 jumps is the best possible.

  If the director decides that the only pairs of buildings that are
  close enough are 1 and 3, 1 and 2 and 4 and 5, then the hero would not
  be able to reach building 4 to save the captive.

That was breadth first search problem, which is easy to figure out.

#include <iostream>
#include <vector>
#include <queue>

int main (int argc, char const* argv[])
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int> >table(n,std::vector<int>(n));
    while(m--){
        int a ,b;
        std::cin >> a >> b;
        table[a-1][b-1] = 1;
        table[b-1][a-1] = 1;
    }
    int start , end;
    std::cin >> start >> end;
    start--;end--;
    std::vector<bool>visited(n);
    std::queue<int>queue_;
    visited[start] = true;
    queue_.push(start);
    std::vector<int>minDist(n);
    std::fill(minDist.begin(),minDist.end(),31000);
    minDist[start] = 0;
    while(!queue_.empty()){
        int s = queue_.front();
        queue_.pop();
        for(int i=0;i<n;i++){
            if(!visited[i] && table[s][i] == 1){
                visited[i] = true;
                minDist[i] = std::min(minDist[i],minDist[s]+1);
                queue_.push(i);
            }
        }
    }
    std::cout <<minDist[end]<< std::endl;
    return 0;
}

The code passed 9 test cases out of the 10 and got stuck at the 10th test case, which was really big. It didn't even run on my own machine.

Here is the test case of whooping 5 MBs: 10th test case in the archive

Can someone lend me some tips for optimizing the code for such a big input?

I think you choice of a data table is really bad. You should consider creating nodes similar to an trie.
struct node {
    unsigned houseID;
    unsigned firstVisited = 0;
    std::vector<node*> houseLinks;
    explicit node(unsigned id) : houseID(id) {}
};

Then your initial code would look like this:
unsigned numHouses, numLinks;
std::cin >> numHouses >> numLinks;

std::vector<std::unique_ptr<node>> houses;
for (unsigned house = 0; house < numHouses; ++house) {
    houses.push_back(std::make_unique<node>(house));
}

I have to say, that my compiler hat home complains about make_unique. In any case this should work too houses.push_back(std::unique_ptr<node>(new node (house)));

Now you have to add the links between the houses
for (unsigned link = 0; link < numLinks; ++link) {
    unsigned house1, house2;
    std::cin >> house1 >> house2;
    houses[house1-1]->houseLinks.push_back(houses[house2-1].get());
    houses[house2-1]->houseLinks.push_back(houses[house1-1].get());
}

Your checking part seems right, although i would suggest to group everything as it belongs:
unsigned start, end;
std::cin >> start >> end;
start--;end--;

std::vector<bool> visited(numHouses, false);
visited[start] = true;

EDIT: this is no longer relevant but i dont know how to cross it out. However, i would suggest, that you keep track of your jump length via the queue. So rather than haveing a queue<node*> have a queue<std::pair<node*, size_t>>
New: I would now suggest to store the first visited field in the struct itself, which simplifies the code a lot
std::queue<node*> jumpQueue;
jumpQueue.push(houses[start].get());

Now while you are adding something to the queue you just increment the jump index.

Now to your breadth first search. Obviously you can ignore any occurrence of a house that was reached before, as that would lead to an at least equally large jumping series.
size_t result = 0;
while (!jumpQueue.empty()) {
    auto oldHouse = jumpQueue.front();
    jumpQueue.pop();
    for (auto newHouse : oldHouse->houseLinks) {
        if (!visited[newHouse->houseID]) {
            visited[newHouse->houseID] = true;
            newHouse->firstVisited = oldHouse->firstVisited+1;
            jumpQueue.push(newHouse);
        }
        if (newHouse->houseID == end) {
            result = oldHouse->firstVisited+1;
            std::queue<node*> swapQueue;
            std::swap(swapQueue, jumpQueue);
        }
    }
}

Note, that one can directly terminate the traversal of the trie by swapping the current queue with an empty one.

Finally now that you have the result, or 0 if you never found the villan then print result. All together you now have:

Solution
#include <iostream>
#include <memory>
#include <queue>
#include <vector>

struct node {
    unsigned houseID;
    unsigned firstVisited = 0;
    std::vector<node*> houseLinks;
    explicit node(unsigned id) : houseID(id) {}
};

int main()
{
    unsigned numHouses, numLinks;
    std::cin >> numHouses >> numLinks;

    std::vector<std::unique_ptr<node>> houses;
    for (unsigned house = 0; house < numHouses; ++house) {
        houses.push_back(std::unique_ptr<node>(new node (house)));
    }

    for (unsigned link = 0; link < numLinks; ++link) {
        unsigned house1, house2;
        std::cin >> house1 >> house2;
        houses[house1-1]->houseLinks.push_back(houses[house2-1].get());
        houses[house2-1]->houseLinks.push_back(houses[house1-1].get());
    }

    unsigned start, end;
    std::cin >> start >> end;
    start--;end--;

    std::vector<bool> visited(numHouses, false);
    visited[start] = true;

    std::queue<node*> jumpQueue;
    jumpQueue.push(houses[start].get());

    size_t result = 0;
    while (!jumpQueue.empty()) {
        auto oldHouse = jumpQueue.front();
        jumpQueue.pop();
        for (auto newHouse : oldHouse->houseLinks) {
            if (!visited[newHouse->houseID]) {
                visited[newHouse->houseID] = true;
                newHouse->firstVisited = oldHouse->firstVisited+1;
                jumpQueue.push(newHouse);
            }
            if (newHouse->houseID == end) {
                result = oldHouse->firstVisited+1;
                std::queue<node*> swapQueue;
                std::swap(swapQueue, jumpQueue);
            }
        }
    }

    std::cout << result << "\n";
}


Execution flow diagram (call-stack) of recursive count-down I have this code:

public class RecurLoopTest {

    public static void main(String[] args) {

     printit(2);

    }

    private static int printit(int n){

        if(n>0){
            printit(--n);
        }

      System.out.print(n+",");

      return n;
   }
}

I have drawn a execution flow/memory flow diagram for above program.  Is this diagram correct or do I need some changes to make it correct?

What I have drawn looks like this:

Link to edit diagram

Link to view diagram

It would be better to add the method arguments in the diagram, for example:

printit(0) -- n=0, prints "0,", returns 0
printit(1) -- n=1, prints "0,", returns 0
printit(2) -- n=2, prints "1,", returns 1
main()

I don't think you need 4 drawings side by side for this, just one like this would be clear enough already.


Checking if a tag is on the screen This function receives an HTMLElement as an argument and returns true if the tag is on the screen and false otherwise.

function isTagVisible(tag) {
    var box;

    box = tag.getBoundingClientRect();

    if (box.left > 0) {
        if (box.left >= window.innerWidth) {
            return false;
        }
    }

    if (box.right <= 0) {
        return false;
    }

    if (box.top > 0) {
        if (box.top >= window.innerHeight) {
            return false;
        }
    }

    if (box.bottom <= 0) {
        return false;
    }

    return true;
}

if (box.left > 0) {
    if (box.left >= window.innerWidth) {
        return false;
    }
}

This seems a little redundant: the innerWidth is going to be greater than 0, so why do you need to conditionals?

Simply remove the outer one.

Your conditions are fairly short. Consider combining them:

if (box.right <= 0 || box.bottom <= 0) {
    return false;
}

if (box.left >= window.innerWidth || box.top >= window.innerHeight) {
    return false;
}

There isn't much more to say about your code, but I have an idea for future improvement: right now, your code will say true even if the element is partially hidden on the screen. How do you plan on handling this?


Return JSON array through PHP Call from my index.php to function get_data($curr_date) goes from here

case "events" :
                    $curr_date = $_POST['current_date'];
                    if ( $eid = get_data($curr_date) )
                        {

                            $result = array( "success"=>true,
                            "eid"=>$eid);

                            $json_output = json_encode( $result );
                            echo $json_output;
                        }
                        else
                            echo FAIL;

    break;

    enter code here

This is my function which returns the result

function get_data($curr_date)
{
    $events_list = mysql_query( "SELECT eid, display_date, word_of_the_day, word_of_the_day_meaning, thought_of_the_day,
    crazyFact_of_the_day, joke_of_the_day FROM eventsoftheday WHERE display_date = '$curr_date' ");
                                // get mysql result cursor
    if( mysql_num_rows( $events_list )  > 0 ) // check if the query returned any records
    {
        $mysql_record = mysql_fetch_array( $events_list );    // parse mysql result cursor
        $events = array();
         $events['e_id'] = $mysql_record['eid'];
         $events['edisplay_date'] = $mysql_record['display_date'];
         $events['eword_of_the_day'] = $mysql_record['word_of_the_day'];
         $events['eword_of_the_day_meaning'] = $mysql_record['word_of_the_day_meaning'];
         $events['ethought_of_the_day'] = $mysql_record['thought_of_the_day'];
         $events['ecrazyFact_of_the_day'] = $mysql_record['crazyFact_of_the_day'];
         $events['ejoke_of_the_day'] = $mysql_record['joke_of_the_day'];

        return $events;     // return events

    }
    else
        return false;
}

Maybe it's better to return error in JSON (if FAIL constant isn't JSON yet)

echo json_encode(array('result' => false));

instead of

echo FAIL;

or return HTTP error code

header('HTTP/1.1 500 Internal Server Error');

And we can simplifify function get_data like this:

if(mysql_num_rows( $events_list )) // check if the query returned any records
{
    $mysql_record = mysql_fetch_array( $events_list );    // parse mysql result cursor
    return array(
        'e_id'                     => $mysql_record['eid'],
        'edisplay_date'            => $mysql_record['display_date'],
        'eword_of_the_day'         => $mysql_record['word_of_the_day'],
        'eword_of_the_day_meaning' => $mysql_record['word_of_the_day_meaning'],
        'ethought_of_the_day'      => $mysql_record['thought_of_the_day'],
        'ecrazyFact_of_the_day'    => $mysql_record['crazyFact_of_the_day'],
        'ejoke_of_the_day'         => $mysql_record['joke_of_the_day'],
    );
} else return false;


Rational arithmetic from given input I'm currently working on this for my own practice. I get 4 digits and an operation.

The input is x1 y1 op x2 y2 and the fraction is x1/y1 and x2/y2. If I get the input: 1 3 + 1 2 then it's 1/3 + 1/2 and the answer should be given the minimal fractional so it's 5/6. I pass the testcases I get and I can't figure out what I'm doing wrong.

To summarize what I do:

Read input and check the operation if it's +,-,/ or *. I generate a prime array to find the biggest common divisor.
Send the input to a function depending on which operation it is.
I count the given input with simple math.
Then I find the biggest common divisor and divide both numerator and denominator with this.
After that I print out the result.

Here is the main function and how I handle if the operation is *. I handle the other operation the same but with other math.

    #include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <iterator>
#include <array>
#include <stdio.h>
#include <string.h>
#include <cstddef>
#include <string>
#include <sstream>
#include <math.h>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

       using namespace std;

long long  nwd(long long a, long long b){
    long long  c;
    while(b != 0){
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

void add(long long x1, long long y1, long long x2, long long y2){
    long long bottom = (y1) * (y2);
    long long top = ((x1) * (y2)) + ((x2) * (y1));
    //cout << bottom << " " << top << endl;
    long long frac;
    if(bottom != 0||top != 0){
        frac = nwd(top,bottom);
    }else{
        frac = 1;
    }
    string sign = "";
    if(top * bottom < 0){
        sign = "-";
    }else{
        sign = "";
    }
    printf("%s%lld / %lld\n",sign.c_str(),abs(top/frac),abs(bottom/frac) );
}

void sub(long long x1, long long y1,long long x2, long long y2){
    long long bottom = (y1) * (y2);
    long long top = ((x1) * (y2)) - ((x2) * (y1));
    long long frac;
    if(bottom != 0||top != 0){
        frac = nwd(top,bottom);
    }else{
        frac = 1;
    }
    string sign = "";
    if(top * bottom < 0){
        sign = "-";
    }else{
        sign = "";
    }
    printf("%s%lld / %lld\n",sign.c_str(),abs(top/frac),abs(bottom/frac) );
}

void divi(long long x1, long long y1, long long x2, long long y2){
    long long top = (x1) * (y2);
    long long bottom = (x2) * (y1);
    long long frac;
    if(bottom != 0||top != 0){
        frac = nwd(top,bottom);
    }else{
        frac = 1;
    }
    string sign = "";
    if(top * bottom < 0){
        sign = "-";
    }else{
        sign = "";
    }
    printf("%s%lld / %lld\n",sign.c_str(),abs(top/frac),abs(bottom/frac) );
}

void mult(long long x1, long long y1, long long x2, long long y2){
    long long top = (x1) * (x2);
    long long bottom = (y2) * (y1);
    long long frac;
    if(bottom != 0||top != 0){
        frac = nwd(top,bottom);
    }else{
        frac = 1;
    }
    string sign = "";
    if(top * bottom < 0){
        sign = "-";
    }else{
        sign = "";
    }
    printf("%s%lld / %lld\n",sign.c_str(),abs(top/frac),abs(bottom/frac) );
}

int main()
{

    int numOp;
    scanf("%d", &numOp);
    while(numOp != 0){
        long long x1,x2,y1,y2;
        char op[2];
        scanf("%lld %lld %s %lld %lld", &x1, &y1, op, &x2, &y2);
        if( op[0] == '+'){
            add(x1, y1, x2,y2);
        }
        else if(op[0] == '-'){
            sub(x1,y1,x2,y2);
        }
        else if(op[0] == '/'){
            divi(x1,y1,x2,y2);
        }
        else{
            mult(x1,y1,x2,y2);
        }
        numOp--;
    }
    return 0;
}

Here is my code with the given testcase and I get the correct result. I need some tips with either different testcases or any suggestions.

I see a number of things that may help you improve your code.

Use only required #includes

The code has a great number of #includes that are not needed.  Some files are even listed twice.  This clutters the code and makes it more difficult to read and understand.  Only include files that are actually needed.

Don't Repeat Yourself (DRY)

The mathematical operations all include large portions of repeated code.  Instead of repeating code, it's generally better to make common code into a function.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Use objects

Since you're writing in C++, what would make more sense to me would be to create a rational fraction object. Then each mathematical operation would be very naturally expressed as an operator on the object.

Use switch instead of nested if

The more appropriate control flow for your if statement in main is a switch statement.  This makes it somewhat clearer to read and understand and often provides a small improvement in performance, especially if there are many cases.

Prefer iostream to stdio.h

Using iostream style I/O makes the code easier to adapt to change.  For example, using scanf, the code has to have the appropriate matching format string for each argument, but using the >> operator, there is no such requirement and the compiler adapts automatically to whatever type is being read.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

Putting it all together

Here's an alternative implementation which uses all of these suggestions.  Note that a rational fraction is only reduced when it is being printed.  This saves some time over always maintaining that state.

#include <iostream>

class RationalFraction
{
public:
    RationalFraction(long long a=0, long long b=1)
        : num{a}, den{b}
        { }
    // unary negation
    RationalFraction& operator-() { num = -num; return *this; }
    // add the passed fraction to this one
    // The two-operand addition is built from this, and a
    // similar pattern is used for each of the other operators.
    RationalFraction& operator+=(const RationalFraction &rh) {
        num = num * rh.den + rh.num *den;
        den *= rh.den;
        return *this;
    }
    RationalFraction& operator-=(const RationalFraction &rh) {
        num = num * rh.den - rh.num *den;
        den *= rh.den;
        return *this;
    }
    RationalFraction& operator*=(const RationalFraction &rh) {
        num *= rh.num;
        den *= rh.den;
        return *this;
    }
    RationalFraction& operator/=(const RationalFraction &rh) {
        num *= rh.den;
        den *= rh.num;
        return *this;
    }
    friend std::ostream &operator<< (std::ostream& out, const RationalFraction& f) {
        RationalFraction fr=f;
        fr.reduce();
        return out << fr.num << " / " << fr.den;
    }
    friend std::istream &operator>> (std::istream& in, RationalFraction& f) {
        return in >> f.num >> f.den;
    }

private:
    void reduce() {
        if (num == 0) {
            den = 1;
            return;
        }
        long long mygcd = gcd(num, den);
        num /= mygcd;
        den /= mygcd;
        if (den < 0) {
            den = -den;
            num = -num;
        }
    }
    long long gcd(long long a, long long b) const {
        long long  c;
        while(b != 0){
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    }

    // data members
    long long num, den;
};

RationalFraction operator+(RationalFraction lh, const RationalFraction &rh)
{
    lh += rh;
    return lh;
}

RationalFraction operator-(RationalFraction lh, const RationalFraction &rh)
{
    lh -= rh;
    return lh;
}

RationalFraction operator*(RationalFraction lh, const RationalFraction &rh)
{
    lh *= rh;
    return lh;
}

RationalFraction operator/(RationalFraction lh, const RationalFraction &rh)
{
    lh /= rh;
    return lh;
}

int main()
{
    int numOp;
    for (std::cin >> numOp; numOp; --numOp) {
        RationalFraction lhs, rhs;
        char op[2];
        std::cin >> lhs >> op >> rhs;
        switch (op[0]) {
            case '+':
                std::cout << lhs+rhs << '\n';
                break;
            case '-':
                std::cout << lhs-rhs << '\n';
                break;
            case '/':
                std::cout << lhs/rhs << '\n';
                break;
            default:
                std::cout << lhs*rhs << '\n';
        }
    }
}

A bit more detail

To understand this version of the code, it's useful to look at a few individual class member functions.  First, is the constructor:

    RationalFraction(long long a=0, long long b=1)
        : num{a}, den{b}
        { }

This allows for construction in a few different ways:

RationalFraction half{1,2};   // 1/2 = one half
RationalFraction three{3};    // 3/1 = 3
RationalFraction zero;        // 0/1 = 0

The basic four mathematical functions are all built in the same way.  First, there is a member function such as +=:

    RationalFraction& operator+=(const RationalFraction &rh) {
        num = num * rh.den + rh.num *den;
        den *= rh.den;
        return *this;
    }

This version is a member function and can be used like this:

RationalFraction a{1,3};
RationalFraction b{1,2};
a += b;    // now a = 5/6 and b is unchanged

It's a common idiom to define those member functions first and then construct the two-operand versions:

RationalFraction operator+(RationalFraction lh, const RationalFraction &rh)
{
    lh += rh;
    return lh;
}

This is a bit subtle.  Note that lh is passed by value, so that means a local copy is constructed using the compiler-generated default copy.  By contrast rh is a const reference, so no additional copy is created.  Now all we need to do is apply the member function version and return lh which, remember, is a copy of whatever was originally passed in for that parameter.  It is a standalone function and not a member function so that either of these works:

RationalFraction f={-1,2};
std::cout << f+3 << std::endl;  // (-1/2) + 3 = 5/2
std::cout << 3+f << std::endl;  // 3 + (-1/2) = 5/2

In the expression 3+f first a temporary rational fraction is created from 3.  Then that rational fraction is added to f and the result displayed using the << operator.  That is, it's approximately the equivalent to this:

RationalFraction temp1{3};   // = 3/1
RationalFraction temp2 = temp1 + f;  // do addition using non-member function
std::cout << temp2 << std::endl;  // show the result = 5/2

The only other slightly tricky bit of code is in private member function reduce.  Here I've added comments to make it easier to understand:

void reduce() {
    // if it's of the form 0/x, turn it into canonical 0/1
    if (num == 0) {
        den = 1;
        return;
    }
    // reduce by dividing by the greatest common divisor of
    // numerator and denominator
    long long mygcd = gcd(num, den);
    num /= mygcd;
    den /= mygcd;
    // Only allow the numerator to be negative to simplify printing.
    // Changing sign of both numerator and denominator has no
    // mathematical effect on the value.
    if (den < 0) {
        den = -den;
        num = -num;
    }
}


Optimally allocating a resource with time-varying demand and cost I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the demand. The cost C depends on which time step I do the allocation.

I need to add quite a few more complex features, but this is the bare working version in Python 2.7:

from math import floor
import numpy as np
import time

def discretise(x,levels = 40,Hmax = 2, Hmin = 0):
    # discretise the levels of storage
    factor = levels / (Hmax-Hmin)
    return floor(x*factor)/factor

# function to track the storage evolution at the stages
def record(D,key,item):
    """Records the value of item in the dictionary d with k"""
    if key in D.keys():
        D[key].append(item)
    else:
        D[key] = [item]

    return D

# Memoization decorator i found online that works
def memoize(f):
    cache = {}

    def memoizedFunction(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    memoizedFunction.cache = cache
    return memoizedFunction

# define demands and cost (Energy)
D = [0.1, 0.1, 0.13, 0.2, 0.4, 0.3, 0.1]
Energy  = [2.0, 5.0,  9.0, 3.0, 7.0, 4.0, 6.0]

@memoize
def val(h,i=0):
    if h < 0 or h > 2: # h < Hmin or h > Hmax:
        return 1000000000
    elif i == T:  # i = T
        return -h*5 # h*m the linear value of h at i = T
    else:
        #           pump off         pump on
        record(H,i,discretise(h))

        no_pump = val(discretise(h-D[i]),i+1) # don't allocate
        pump = Energy[i] + val(discretise(h+0.2-D[i]),i+1) # allocate

        v = min(no_pump  , pump   )

        # record optimal policy
        if v == no_pump:
            pos = 0
        else:
            pos = 1

        record(X,i+1,pos)
        record(V,i+1,v)

        return v

T = 7
H = {}
V = {}
X = {}
ts = time.time()
for ii in xrange(0,20):
    print val(ii/10.0)

te = time.time()

print te - ts

How can I get this code nicer / more pythonic?

Styling

I don't think PEP8 actually says anything about this, but I prefer to have spaces after commas in just about anything.  The comma is a way of separating two items, but sometimes it just isn't enough and other times it just looks squashed without the space.  You should not, however, put spaces around the = sign in all cases.  From PEP8:

  Don't use spaces around the = sign when used to indicate a keyword argument or a default parameter value.

You break that rule in the definition of discretise().

Again from PEP8:

  Use the function naming rules: lowercase with words separated by underscores as necessary to improve readability.

That is under the title Method Names and Instance Variables.  Classes should be PascalCase, but your variables should be as defined above.  Your variables, T, H, V, and X should have more descriptive names besides the fact that they should be lowercase.  I realize that you use v in val(), but if you gave more descriptive names to your variables, there wouldn't be a clash.

v = min(no_pump  , pump   )

What are you doing with all that whitespace?  It should look like this:

v = min(no_pump, pump)

You have many cases of things such as i+1, ii/10.0, etc.  PEP8 doesn't actually say anything against that, but my opinion is that you should use whitespace around the operators unless it makes something look confusing.  For example, a*b + c*d would look confusing if there were spaces around the asterisks, but in the case of val(ii/10.0), for example, I would prefer it to be val(ii / 10.0).

The logic

def record(D,key,item):
    if key in D.keys():
        D[key].append(item)
    else:
        D[key] = [item]

That function could be simplified to this:

def record(D, key, item):
    D.setdefault(key, []).append(item)

Take a look at the docs.  If you wanted to leave it how it was, though, you could still take out the .keys() part of the if statement.  Turning a dictionary into an iterator, which in does, turns it into an iterator of its keys.

def memoize(*args):
    cache = {}

    def memoizedFunction(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    memoizedFunction.cache = cache
    return memoizedFunction

Using memoizedFunction.cache = cache isn't helping you here.  You aren't even using it.  You might be better off defining a class:

class Memoize:
    def __init__(self, function):
        self.function = function
        self.cache = {}

    def __call__(self, *args):
        if args not in self.cache:
            self.cache[args] = self.function(*args)
        return self.cache[args]

I changed the name to Memoize to comply with PEP8, but that just means that you need to change @memoize to @Memoize.

        #           pump off         pump on

It isn't clear to me what that comment is saying.  The pump on part goes beyond the end of the next line.  If you meant it to be a comment on a different line, you should move it.

v = min(no_pump  , pump   )

# record optimal policy
if v == no_pump:
    pos = 0
else:
    pos = 1

Here would be a good use of the cmp() function:

v = cmp(no_pump, pump)
if v <= 0:
    pos = 0
else:
    pos = 1

ts = time.time()
...
te = time.time()

I can tell from the last line, print te - ts that those are meant to stand for time start and time end, but why not spell it out?  In this case it's fairly easy to tell what they are for, but it's a good habit to make your variable names very clear.  I would define them as start_time and end_time.


Java-Helper library for compressing (zipping) files I'm writing a Java-Helper library. I want to include a method to zip files together, and this is what I've come up with. I'm using the java.util.zip.* library (ZipOutputStream and ZipEntry specifically).

/**
* This uses the java.util.zip library to zip the given files to the given destination.
*
* @param destination
* @param files
* @throws FileNotFoundException
* @throws IOException
*/
public static void zipFiles(File destination, File... files) throws FileNotFoundException, IOException {
  try (ZipOutputStream out = new ZipOutputStream(new FileOutputStream(destination))) {
    byte[] buffer = new byte[1024];
    for (int i = 0; i < files.length; i++) {
      try (FileInputStream in = new FileInputStream(files[i])) {
        out.putNextEntry(new ZipEntry(files[i].getName()));

        // Transfer bytes from the file to the ZIP file
        int length;
        while ((length = in.read(buffer)) > 0) {
          out.write(buffer, 0, length);
        }

        // Complete the entry
        out.closeEntry();
      }
    }
  }
}

Any pointers?

Also, from the code, is this a good buffer size?

byte[] buffer = new byte[1024];

I've seen a lot of disks with a blocksize of 512 KB. Would that be a more "optimal" size?

Well, I benchmarked it and found that a buffer size of 10485760 (10 MB) was fastest... Kind of surprised about that and I'm thinking that's not the most efficient. I think I'll leave it at 1 MB unless someone else has any thoughts.


Pig Latin Script and Runtime Wrote a basic pig latin script in python where the input is a string and it outputs the pig latin equivalent. I was just wondering what the runtime of this code would be and if there was a way to make it quicker. Off the time of my head, I would assume that the runtime would be \$O(26)\$ or just constant because all you do is look at the last letter and compare it to the list.

def pig_latin(string):
    consonants = ['b','c','d','f','g','h','j','k','l','m','n','p','q','r','s','t','v','w','x','y','z']
    if string[-1] in consonants:
        string = string[1:] + string[0] + "ay"
    else:
        string = string + "way"
    return string

I don't think speed should be your primary concern in this case. The only thing I could come up with as an improvement is to change consonants:

from string import ascii_lowercase

VOWELS = ("a", "e", "i", "u", "o", "y", "w")
CONSONANTS = tuple(char for char in ascii_lowercase if char not in VOWELS)
# These can be constants because they're always the same (at least for the latin alphabet).

Also, you don't handle the case where string is not lowercase. To account for that:

def pig_latin(string):
    string = string.lower()
    if string[-1] in CONSONANTS:
        string = string[1:] + string[0] + "ay"
    else:
        string = string + "way"
    return string

As @Ludisposed suggested, you don't actually have to convert the entire string to lowercase, if string[-1].lower() in CONSONANTS would do.


Comparing two arrays to see if they contain objects with different IDs This feels like the kind of problem that has an extremely elegant solution. But my code is mechanical and straightforward. Not bad but I'm interested if there's something nicer.

Performance is not really an issue. I'm looking for elegant/shorter, not faster.

No underscore.js please; it's not worth fighting my coworkers to get another third-party library in there, especially when it duplicates so much ES5. Speaking of which, we work in an ES5-only environment so use all the array extras you want.

function getIds(array) {
    // We have added `Array.prototype.unique`; it does what you'd expect.
    return array.map(function (x) { return x.id; }).unique().sort();
}

function areDifferentByIds(a, b) {
    var idsA = getIds(a);
    var idsB = getIds(b);

    if (idsA.length !== idsB.length) {
        return true;
    }

    for (var i = 0; i < idsA.length; ++i) {
        if (idsA[i] !== idsB[i]) {
            return true;
        }
    }

    return false;
}

function areDifferentByIds(a, b) {
    var idsA = a.map( function(x){ return x.id; } ).unique().sort();
    var idsB = b.map( function(x){ return x.id; } ).unique().sort();
    return (idsA.join(',') !== idsB.join(',') );
}

This is the simplest I could make it. I think such small functions need to be as self contained as possible, and not need other functions. This makes them more readable, maintainable, and of course reusable. I therefor removed the getIds function. If you use that elsewhere you can keep it.

You might want to store the function (x) { return x.id; } inside a variable, and reuse it on both maps

I also think it is faster, because join is quite fast, and it doesn't require a for-loop.

EDIT my next attempt

function areDifferentByIds(a, b) {
    var idsA = a.map( function(x){ return x.id; } ).unique();
    var idsB = b.map( function(x){ return x.id; } ).unique();
    var idsAB = a.concat(b).unique();
    return idsAB.length!==idsA.length
}

secondly, you could make it more generic, by adding the property you want to check to the arguments of the function. Something like:

function areDifferentByProperty(a, b, prop) {
    var idsA = a.map( function(x){ return x[prop]; } ).unique();
    var idsB = b.map( function(x){ return x[prop]; } ).unique();
    var idsAB = a.concat(b).unique();
    return idsAB.length!==idsA.length
}

thirdly, I would much rather name it areEqualBy___. Seems more intuitive to me, but that's just me.


Standard deviation from iterators I want this to be similar to the STL algorithms but I don't find it elegant nor concise at all:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using E = double;
template <typename IT>
E std_dev(IT begin, IT end){
    auto N = std::distance(begin, end);
    E average = std::accumulate(begin, end, E()) / N;
    auto sum_term = [average](E init, E value)-> E{
        return init + (value - average)*(value - average);
    };
    E variance = std::accumulate(begin,  end, E(), sum_term);
    return std::sqrt(variance * 1.0 / (N - 1));
}

int main(){
    std::vector<double> stuff {3.5, 3.4, 3.6, 3.9, 3.5, 3.5, 3.5, 3.5, 3.5};
    std::cout << std_dev(stuff.begin(), stuff.end()) << "\n";
}

Firstly, make it correct.

N is integral, you could make it E so you don't accidentally do integer arithmetic.

N-1 is wrong.

Rename average to mean.

Don't hardcode E.

You get:

template <typename It, typename E = typename std::iterator_traits<It>::value_type>
E std_dev(It begin, It end){
    E N = std::distance(begin, end);
    E const mean = std::accumulate(begin, end, E()) / N;
    auto sum_term = [mean](E init, E value)-> E { return init + (value - mean)*(value - mean); };
    E variance = std::accumulate(begin, end, E(), sum_term);
    return std::sqrt(variance / N);
}

Slightly stylized, with comparison to Boost Accumulator:

Live On Coliru

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics.hpp>

template <typename It, typename E = typename std::iterator_traits<It>::value_type, typename R = typename std::common_type<double, E>::type>
R std_dev_boost(It begin, It end){
    namespace ba = boost::accumulators;

    ba::accumulator_set<R, ba::stats<ba::tag::variance> > accu;
    std::for_each(begin, end, std::ref(accu));
    return std::sqrt(ba::variance(accu));
}

template <typename It,
    typename E = typename std::iterator_traits<It>::value_type,
    typename R = typename std::common_type<double, E>::type>
R std_dev(It b, It e)
{
    R N          = std::distance(b, e);
    R const mean = std::accumulate(b, e, R{}) / N;
    R variance   = std::accumulate(b, e, R{}, [mean](R a, E v)-> R { return a + (v-mean)*(v-mean); });
    return std::sqrt(variance / N);
}

int main(){
    std::vector<int> stuff {35, 34, 36, 39, 35, 35, 35, 35, 35};
    std::cout << std_dev_boost(stuff.begin(), stuff.end()) << "\n";
    std::cout << std_dev      (stuff.begin(), stuff.end()) << "\n";
}

Prints

1.34256
1.34256


Find a golden tile from a list of tiles I had an interview and was asked a problem. I provided a solution and wanted to make sure if this is correct.

There is a Tile class. It has a boolean variable isGoldenTile which is false for all but true for one tile.

There is a List<Tile> neighbors. These are list of its immediate neighbors which are tiles.

There is a method getNeighbors() which returns the list of neighbors.

Finally, there is a method findGoldenTile which returns a Tile object. This returns the golden tile.

In no way I could alter the class except for the method body for findGoldenTile.

Here is my solution:

public class Tile {

    private boolean isGoldenTile = false;
    private List<Tile> neighbors = null;

    public Tile(boolean isGoldenTile, List<Tile> neighbors) {
        this.isGoldenTile = isGoldenTile;
        this.neighbors = neighbors;
    }

    public boolean isGoldenTile() {
        return isGoldenTile;
    }

    public List<Tile> getNeighbors() {
        return neighbors;
    }

    public Tile findGoldenTile() {
        if(this.isGoldenTile == true){
            return this;
        } else if (this.getNeighbors().size() > 0){
            for(int i=0;i<this.getNeighbors().size();i++){
                if(this.getNeighbors().get(i).isGoldenTile == true){
                    return this.getNeighbors().get(i);
                }
            }
        } else {
            for(int i=0;i<this.getNeighbors().size();i++){
                return this.getNeighbors().get(i).findGoldenTile();
            }
        }
        return null;
    }
}

You need to keep track of visited tiles, or you risk ending in an infinite (recursive) loop. If you use recursion, and if you are not allowed to change the class, this is difficult, as you'd need to add another parameter to findGoldenTile holding the already visited tiles.

Alternatively, you could not make it recursive, but with a queue and with the set of visited tiles in the method itself. Something like this (not tested):

public Tile findGoldenTile() {
    Set<Tile> visited = new HashSet<>();
    LinkedList<Tile> queue = new LinkedList<>();
    queue.add(this);
    visited.add(this);
    while (! queue.isEmpty()) {
        Tile tile = queue.pop();
        if (tile.isGoldenTile) {
            return tile;
        }
        for (Tile x : tile.neighbors) {
            if (! visited.contains(x)) {
                queue.add(x);
                visited.add(x);
            }
        }
    }
    return null;
}


threading objects and urlrequests The code below is a good representation of my coding skills.  I've been at it for about 6 months.  What I am interested in is ways to make the following program faster.  I currently have the urlrequests threaded to pull information for 500 stocks, but it is still too slow (around 30 seconds).  What python techniques can I use to make this program more efficient?

Thanks!

from urllib.request import urlopen
from csv import reader
from threading import Thread

class StockQuote():
    """gets stock data from Yahoo Finance"""

    def __init__(self, quote):
        self.quote = quote

    def lastPrice(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=l1'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def volume(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=v0'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def yearrange(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=w0'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def PEratio(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=r0'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def bookValue(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=b4'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def EBITDA(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=j4'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def PEGRatio(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=r5'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

    def ticker(self):
        url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f=s0'.format(ticker=self.quote)
        return bytes.decode((urlopen(url).read().strip()))

class StockData(Thread):

    def __init__(self, stk, fileobj):
        Thread.__init__(self)
        self.stk = stk
        self.fileobj = fileobj

    def run(self):
        try:
            stkObj = StockQuote(self.stk)
            stkdata= {}
            stkdata['Ticker'] = stkObj.ticker()
            stkdata['Price'] = stkObj.lastPrice()
            stkdata['PE Ratio'] = stkObj.PEratio()
            stkdata['Volume'] = stkObj.volume()
            stkdata['Year Range'] = stkObj.yearrange()
            stkdata['Book Value per Share'] = stkObj.bookValue()
            stkdata['EBITDA'] = stkObj.EBITDA()
            stkdata['PEG Ratio'] = stkObj.PEGRatio()
        except Exception:
            pass
        self.fileobj.write(str(stkdata))

def openSP500file():
    SP500 = reader(open(r'C:\Users\test\Desktop\SP500.csv', 'r'), delimiter=',')
    printlist = open(r'C:\Users\test\Desktop\SP500prices.txt', 'w')
    for x in SP500:
        indStk = x[0]
        t1 = StockData(indStk, printlist)
        t1.start()

def main():
    openSP500file()

if __name__ == '__main__':
    main()

It is difficult to make the program faster because time is mostly expended in IO and url connections. It would help for checking changes if you could provide the csv stock files.

On the other hand the code could be greatly simplified. The following code has not been tested (no csv files available) but gives you the idea:

from urllib.request import urlopen
from csv import reader
from threading import Thread

class StockQuote():
    """gets stock data from Yahoo Finance"""

    names = dict(lastPrice='l1', volume='v0', yearrange='w0', PEratio='r0',
                  bookValue='b4', EBITDA='j4', PEGRatio='r5', ticker='s0')

    def __init__(self, quote):
        self.quote = quote
        self.url = 'http://finance.yahoo.com/d/quotes.csv?s={ticker}&f={par}'

    def __getattr__(self, name):
        url = self.url.format(ticker=self.quote, par=StockQuote.names[name])
        return bytes.decode((urlopen(url).read().strip()))

class StockData(Thread):

    def __init__(self, stk, fileobj):
        Thread.__init__(self)
        self.stk = stk
        self.fileobj = fileobj

    def run(self):
        stkdata = {}
        stkObj = StockQuote(self.stk)
        for prprty in StockQuote.names:
            try:
                func = getattr(stkObj, prprty)
                stkdata[prprty] = func()
            except Exception:
                pass

        self.fileobj.write(str(stkdata))

def openSP500file():
    SP500 = reader(open(r'C:\Users\test\Desktop\SP500.csv', 'r'), delimiter=',')
    printlist = open(r'C:\Users\test\Desktop\SP500prices.txt', 'w')
    for x in SP500:
        indStk = x[0]
        t1 = StockData(indStk, printlist)
        t1.start()

def main():
    openSP500file()

if __name__ == '__main__':
    main()