Find minimum count of items where sum of them is X from an array I recently faced an interview question where you have to find minimum needed items from an array that can added together to generate X value.
For example giving:
[1, 9, 2, 5, 3, 10] and the goal is: 13, => it should be [10, 3]

You can't use any number out side of array.

I have tried to sort items and take from the head one by one and some other stuff, but no lucks. Although, I have solved this by a not really performant solution and I will post it as an answer. I am looking for a more performant solution.
Solution:
First we have to find all subsets of the array:
extension Array {
    var allSubsets: [[Element]] {
        guard count > 0 else { return [[]] }

        let tail = Array(self[1..<endIndex])
        let head = self[0]
        let withoutHead = tail.allSubsets

        let withHead = withoutHead.map { $0 + [head] }

        return withHead + withoutHead
    }
}

Then we can filter all subsets that their sum is equal to the goal like:
subsets.filter { $0.reduce(0) { $0 + $1 } == goal }

And lastly, find the smallest subset by its count:
func minimumElements(in array: [Int], goal: Int) -> [Int] {
    let subsets = array.allSubsets

    let validSubsets = subsets.filter { subset in
        subset.reduce(0) { $0 + $1 } == goal
    }

    return validSubsets.reduce(array) { $0.count < $1.count ? $0 : $1 }
}

This question was originally asked and answered in StackOverflow but moved here as suggestion.

Naming

Your function does not return “minimum elements,” but the shortest subset of an array with a given sum. I would suggest something like

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]

Handling exceptional cases

Your code returns the entire array if no subset with the given sum exists, which seems not sensible to me.

In a comment you said that it should return an empty array in that case, but that would be ambiguous: an empty array is also the correct result for goal = 0.

The Swift way would be to make the result an optional which is nil if no subset is found:

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {
    let subsets = array.allSubsets

    let validSubsets = subsets.filter { subset in
        subset.reduce(0, +) == goal
    }

    if let firstValid = validSubsets.first {
        return validSubsets.dropFirst().reduce(firstValid) { $0.count < $1.count ? $0 : $1 }
    } else {
        return nil
    }
}

Note also that the + operator can be passed directly to the closure parameter of reduce() which reduces(!) the code slightly.

Performance: avoid creation of intermediate arrays

The first performance problem is that a list with all subsets is generated first. For an array with \$ N \$ elements that makes \$ 2^N \$ subsets.

A better approach would be to determine the shortest subset while enumerating the subsets, instead of putting all subsets into a list first. Here is a first attempt:

// Version A:

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {
    // Terminating condition:
    guard let first = array.first else {
        return goal == 0 ? [] : nil
    }

    // Recursion:
    let tail = Array(array.dropFirst())
    let subsetWithout = shortestSubset(of: tail, withSum: goal)
    let subsetWith = shortestSubset(of: tail, withSum: goal - first)

    switch (subsetWithout, subsetWith) {
    case (let s1?, let s2?): return s1.count < s2.count + 1 ? s1 : [first] + s2
    case (let s1?, nil): return s1
    case (nil, let s2?): return [first] + s2
    case (nil, nil): return nil
    }
}

In the recursion step, the shortest subsets which can be obtained by including or omitting the first array element are determined recursively. The switch-statement is used to handle the case where none, one, or both of these intermediate results are nil.

This turned to be a bit faster in my tests, but there are still many intermediate array created at

let tail = Array(array.dropFirst())

If we modify the method to take a collection of integers instead of an array then we can pass the slice array.dropFirst() directly to the recursive call. Slices are “cheap” to create and share the storage with their origin (unless mutated):

// Version B:

func shortestSubset<C: Collection>(of array: C, withSum goal: Int) -> [Int]? where C.Element == Int {
    // Terminating condition:
    guard let first = array.first else {
        return goal == 0 ? [] : nil
    }

    // Recursion:
    let subsetWithout = shortestSubset(of: array.dropFirst(), withSum: goal)
    let subsetWith = shortestSubset(of: array.dropFirst(), withSum: goal - first)
    switch (subsetWithout, subsetWith) {
    case (let s1?, let s2?):
        return s1.count < s2.count + 1 ? s1 : [first] + s2
    case (let s1?, nil):
        return s1
    case (nil, let s2?):
        return [first] + s2
    case (nil, nil):
        return nil
    }
}

This turned out to be considerably faster in my test.

Performance: prune the search tree

A possible performance improvement is to stop the recursion if the goal cannot be reached with the remaining array elements, i.e. if the target sum is smaller than the smallest possible sum or larger than the largets possible sum of the array.

Here it is useful to do the recursion in a helper function. The main function computes the smallest and largest sum once and passes it on to the helper function. The helper function can update those limits, without the need of computing them again.

The helper function takes an array slice as argument, that is another way to void the creation of intermediate arrays.

// Version C:

func shortestSubsetHelper(of array: ArraySlice<Int>, withSum goal: Int,
                          min: Int, max: Int) -> [Int]? {
    guard let first = array.first else {
        return goal == 0 ? [] : nil
    }
    if goal < min || goal > max {
        return nil
    }
    let subsetWithout = shortestSubsetHelper(of: array.dropFirst(), withSum: goal,
                                         min: min, max: max)
    let subsetWith = first < 0 ?
        shortestSubsetHelper(of: array.dropFirst(), withSum: goal - first,
                              min: min - first, max: max) :
        shortestSubsetHelper(of: array.dropFirst(), withSum: goal - first,
                              min: min, max: max - first)
    switch (subsetWithout, subsetWith) {
    case (let s1?, let s2?):
        return s1.count < s2.count + 1 ? s1 : [first] + s2
    case (let s1?, nil):
        return s1
    case (nil, let s2?):
        return [first] + s2
    case (nil, nil):
        return nil
    }
}

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {

    let smallestSum = array.filter { $0 < 0 }.reduce(0, +)
    let largestSum = array.filter { $0 > 0 }.reduce(0, +)
    return shortestSubsetHelper(of: array[...], withSum: goal,
                                min: smallestSum, max: largestSum)
}

Dynamic programming

What we have here is a variant of the “subset sum problem”, which has well-known solutions using dynamic programming. Instead of determining only if a subset with the given sum exists we also need the smallest subset with that sum.

The following is motivated by the “Pseudo-polynomial time dynamic programming solution” from the above Wikipedia article. We maintain a dictionary which for every achievable sum stores the shortest subset with that sum that has been found so far. The given array is traversed once, and the dictionary updated accordingly for each array element.

// Version D:

func shortestSubset(of array: [Int], withSum goal: Int) -> [Int]? {
    // Map each possible sum to the shortest subset found so far with that sum:
    var dp: [Int: [Int]] = [0: []]

    for elem in array {
        let upd = dp.map { (key, value) in (key + elem, value + [elem])}
        for (key, value) in upd {
            if let oldValue = dp[key] {
                if value.count < oldValue.count {
                    dp[key] = value
                }
            } else {
                dp[key] = value
            }
        }
    }
    return dp[goal]
}

This turned out to be faster for large arrays.

Benchmarks

The following (very simple) benchmark was done on a 3.5 GHz Quad-Core Intel Core i5 iMac running macOS 10.15, and

let array = [1, -2, 3, -4, 5, -6, 100, 100, 7, -8, 9, -10, 11, -12]
let goal = 20

let start = Date()
let result = shortestSubset(of: array, withSum: goal)
let end = Date()
print(result, end.timeIntervalSince(start) * 1000)

compiled with Xcode 11.3.1 in Release mode, i.e. with optimization.

Results (approximately):

Original code: 6 milliseconds.
Version A: 3 milliseconds.
Version B: 0.7 milliseconds.
Version C: 0.2 milliseconds.
Version D: 0.4 milliseconds.

With the larger array

let array = [1, -2, 3, -4, 5, -6, 100, 100, 7, -8, 9, -10, 11, -12,
             1, -2, 3, -4, 5, -6, 100, 100, 7, -8, 9, -10, 11, -12]
let goal = 20

we get the following results:

Original code: ???
Version A: 37733 milliseconds.
Version B: 6079 milliseconds.
Version C: 548 milliseconds.
Version D: 2.5 milliseconds.


Implementation of a Hash Map in C++ I created a templated Hash Map class in C++, which supports most of the basic C++ types (e.g. int, float, char...). I would like some feedback regarding my implementation and what is bad and can be improved.

#ifndef _LIB_HASHMAP
#define _LIB_HASHMAP
#include <exception>
#include <string>

namespace lib{

    namespace details{

        unsigned int generate_hash(const int& key, const size_t& hash_map_size){
            return key%hash_map_size;
        }

        unsigned int generate_hash(const std::string& key, const size_t& hash_map_size){
            return key.size()%hash_map_size;
        }

        unsigned int generate_hash(const char* key, const size_t& hash_map_size){
            size_t position = 0;
            for (size_t i=0; key[i]!='\0'; i++){
                position += key[i];
            }
            return position%hash_map_size;
        }

    }

    template <typename T, typename U>
    class hash_map{

    private:
        struct hash_entry{
            T key;
            U value;
            hash_entry(){}
            hash_entry(const T& _key, const U& _value)
                : key(_key), value(_value){}
        };
        hash_entry* hash_entries;
        unsigned int* filled_positions;
        unsigned int hash_map_size;
        unsigned int num_entries;

    public:
        typedef const hash_entry* const_iterator;
        typedef hash_entry* iterator;
        explicit hash_map(unsigned int);
        ~hash_map();
        iterator begin();
        iterator end();
        const_iterator cbegin();
        const_iterator cend();
        unsigned int size();
        void add(const T&, const U&);
        U& operator[](const T&);
    };

    template <typename T, typename U>
    hash_map<T,U>::hash_map(unsigned int _size):
        hash_entries(new hash_entry[_size]),
        filled_positions(new unsigned int[_size]()),
        hash_map_size(_size),
        num_entries(0){
    }

    template <typename T, typename U>
    hash_map<T,U>::~hash_map(){
        delete[] filled_positions;
        delete[] hash_entries;
    }

    template <typename T, typename U>
    typename hash_map<T,U>::const_iterator hash_map<T,U>::cbegin(){
        return hash_entries;
    }

    template <typename T, typename U>
    typename hash_map<T,U>::const_iterator hash_map<T,U>::cend(){
        return hash_entries+hash_map_size;
    }

    template <typename T, typename U>
    typename hash_map<T,U>::iterator hash_map<T,U>::begin(){
        return hash_entries;
    }

    template <typename T, typename U>
    typename hash_map<T,U>::iterator hash_map<T,U>::end(){
        return hash_entries+hash_map_size;
    }

    template <typename T, typename U>
    unsigned int hash_map<T,U>::size(){
        return hash_map_size;
    }

    template <typename T, typename U>
    void hash_map<T,U>::add(const T& _key, const U& _value){
        if (num_entries >= hash_map_size){
            throw std::out_of_range("std::out_of_range : hash_map full");
        }
        unsigned int position = details::generate_hash(_key,hash_map_size);
        while (filled_positions[position]){
            position = (position+1)%hash_map_size;
        }
        filled_positions[position] = 1;
        hash_entries[position] = hash_entry(_key,_value);
        num_entries += 1;
    }

    template <typename T, typename U>
    U& hash_map<T,U>::operator[](const T& _key){
        unsigned int position = details::generate_hash(_key,hash_map_size);
        unsigned int count = 0;
        while (hash_entries[position].key != _key){
            if (count > hash_map_size){
                throw std::invalid_argument("std::invalid_argument : key not in hash_map");
            }
            position = (position+1)%hash_map_size;
            count += 1;
        }
        return hash_entries[position].value;
    }

}

#endif // _LIB_HASHMAP

Although the description claims that most C++ types are supported, I see only int and two kinds of string.  The std::hash class is specialized for quite a few more types than that:

template<> struct hash<bool>;
template<> struct hash<char>;
template<> struct hash<signed char>;
template<> struct hash<unsigned char>;
template<> struct hash<char16_t>;
template<> struct hash<char32_t>;
template<> struct hash<wchar_t>;
template<> struct hash<short>;
template<> struct hash<unsigned short>;
template<> struct hash<int>;
template<> struct hash<unsigned int>;
template<> struct hash<long>;
template<> struct hash<long long>;
template<> struct hash<unsigned long>;
template<> struct hash<unsigned long long>;
template<> struct hash<float>;
template<> struct hash<double>;
template<> struct hash<long double>;
template< class T > struct hash<T*>;

In addition, the std::string hash is very collision-prone, as it uses only the length of the string (and the char* version doesn't even use std::strlen() - are you intending to even reinvent that wheel?).

std::size_t is missing its necessary include (usually <cstdlib>) and is consistently misspelt.

We need to include <stdexcept> for std::out_of_range and std::invalid_argument.

The compiler-generated copy constructor won't do what we want with hash_entries or filled_positions - that's dangerous, and will lead to multiple objects believing they own the pointers, and double deletion.

cbegin() and cend() functions ought to be usable on a const hash_map (and begin() and end() ought to be overloaded suitably, too).  Other const methods are lacking (such as find()) which make const maps much less useful than they ought to be.


Class in a DLL to extract data from a file via many accessors I'm making a class that takes a path to a text file as an argument in its constructor, and then parses the text file and pulls out a lot of data that it stores as private members. Most of these members are vectors of ints, floats, and strings.

The class will be used by different versions of VS, so my understanding is that I need to be careful about exporting templates like the STL containers (including string). I also assume I need to be careful about passing templates into the library. Therefore, everything going into or out of the public interface is kept as a primitive type.

//header
class FileLoader
{
public:
    FileLoader(const char* path);

    int GetIterationCount();
    const char* GetName();
    int GetID();

    int GetPathValue(int iteration);
    int GetAttemptsMadeCount(int iteration);
    float GetStartTime(int iteration);
    float GetEndTime(int iteration);
    const char* GetLargestContributer(int iteration);

private:
    int iterationCount;
    std::string GetName;
    int ID;

    std::vector<int> pathValue;
    std::vector<int> attemptsMadeCount;
    std::vector<float> startTime;
    std::vector<float> endTime;
    std::vector<std::string> largestContributer;
};

//associated cpp
int FileLoader::GetPathValue(int iteration)
{
    return pathValue.at(iteration);
}
const char* GetLargestContributer(int iteration)
{
    return largestContributer.at(iteration).c_str();
}
 //similar structure for other accessors

There's something like 15 data items, some are vectors and some are just single items.

This really clutters up the public interface, but I don't see a good way around it. I considered adding an enum at the top:

enum class DataTypes
{
    PathValue;
    AttemptsMadeCount;
    StartTime;
    EndTime;
    LargestContributer;
};

And then I could just have a single function for results:

int GetResults(DataTypes::PathValue, int iteration);

And grab the appropriate underlying data with a switch. However, I don't think there's any way that'll work because the return types are different for different results. The ints need to be ints because they're the type of things people will want to do comparison operations on.

Another thought was to have a results struct that contained all the different data items for a given iteration. Then the interface is just a function that takes an iteration number and spits out the struct, and the user can choose which data item they care about.

That's the most promising to me, but the normal user will probably be more interested in all the iterations for a given data item at once. As I was typing this I was concerned about memory, since getting all the iterations for one item would mean getting it for all or most of the others. This is many hundreds of megabytes of data so that might not be trivial. However, it occurs to me that my function could populate the struct with const references to the underlying data.

Is that being too inefficient just for the sake of prettiness? It does work fine now, but I figure if there's a better way to do it I'd learn something in the process.

I think you can use templates to good use to simplify the user interface and still retain the flexibility.

I would suggest declaring some structs instead of using enum class DataTypes.

struct DataType_1;
struct DataType_2;
struct DataType_3;
struct DataType_4;

You may define them to be empty structs but that is not necessary for what I am going to suggest.

// This is OK too but not necessary.
struct DataType_1 {};
struct DataType_2 {};
struct DataType_3 {};
struct DataType_4 {};

Then create template class that captures the notion of traits corresponding to the above structs.

template <typename T> struct DataTypeTrait;

template <> struct DataTypeTrait<DataType_1>
{
   using type = int;
};

template <> struct DataTypeTrait<DataType_2>
{
   using type = int;
};

template <> struct DataTypeTrait<DataType_3>
{
   using type = float;
};

template <> struct DataTypeTrait<DataType_4>
{
   using type = char const*;
};

Create a wrapper class around the traits class.

template <typename T> struct DataType
{
   using type = DataTypeTrait<T>::type;
};

I understand that you have some concerns about using containers from the standard library. However, it's OK to use of member function templates described below since they don't involve use of standard library containers in the interface of the member functions.

Here's how I see FileLoader to look like:

class FileLoader
{
   public:
      FileLoader(const char* path);

      int GetIterationCount();

      // This is all you need in the public interface.
      template <typename T>
         typename DataType<T>::type getData(int iteration) const
         {
            return getData(iteration, (T*)nullptr);
         }

   private:

      // The dummy arguments allows the function overloading to
      // work seamlessly from the member function template.

      int getData(int iteration, DataType_1* dummy) const;
      int getData(int iteration, DataType_2* dummy) const;
      float getData(int iteration, DataType_3* dummy) const;
      char const* getData(int iteration, DataType_4* dummy) const;
};

User code

char const* filepath = "some/file/path";
FileLoader loader(filepath);
int val1 = loader.getData<DataType_1>(0);
float val2 = loader.getData<DataType_3>(0);
float val3 = loader.getData<DataType_4>(0); // Error.
char const* val4 = loader.getData<DataType_4>(0);


Scanl expressed as fold Inspired by the learn you a haskell exercise to express map with fold I wrote an implementation of scanl by means of a fold.

scanl2 :: (b -> a -> b) -> b -> [a] -> [b]
scanl2 f z xs = reverse $ foldl (\a x -> (f (head a) x): a) [z] xs

I have the idea that in terms of performance it kinda is up to par with standard scanl but I am wondering whether I could improve anything both in terms of performance, idiomacy, style, etc. I am a Haskell novice with modest functional programming (Scala, some Clojure) background.

Using reverse is generally a bad idea for performance — especially since Haskell lists can be infinite!  Observe:

*Main> let triangularNumbers = scanl (+) 0 [1, 2 ..]
*Main> let triangularNumbers2 = scanl2 (+) 0 [1, 2 ..]
*Main> take 5 triangularNumbers
[0,1,3,6,10]
*Main> take 5 triangularNumbers2          -- hangs forever


Parallax animation running well on Chrome but slow on Safari This is the continuation of a previous question I posted here.

I've improved (at least I think so) the initial script from the previous question, now storing the data in an array, it runs slightly better, but still sometimes there's some lag in safari. I've tried to call requestAnimationFrame on scroll and cancelAnimationFrame on scroll end, but the animation was a little jumpy so I removed that.

This is the updated code:

var animationId,
    parallaxElements = [];

// Push elements to array
s.parallaxElements.each(function (i) {
  var i = {
    element: $(this),
    ratio: $(this).data('parallax-ratio'),
    offset: $(this).closest('.parallax-section').offset().top - 60,
    current: 0
  };

  parallaxElements.push(i);
});

// Animation
function animation() {
  var scrollPos = s.theWindow.scrollTop();

  for (var i = 0; i < parallaxElements.length; i++) {
    var self = parallaxElements[i],
        current = self.current,
        position = current - (current - (self.offset - scrollPos) * self.ratio) * 0.1;

    if (position !== current) {
      self.element.css('transform', 'translateY(' + position + 'px)');
      self.current = position;
    }
  }

  animationId = window.requestAnimationFrame(animation);
}

window.requestAnimationFrame(animation);

parallaxElements = [];

// Push elements to array
s.parallaxElements.each(function (i) {
  var i = {
    element: $(this),
    ratio: $(this).data('parallax-ratio'),
    offset: $(this).closest('.parallax-section').offset().top - 60,
    current: 0
  };

  parallaxElements.push(i);
});

This looks like transforming one array to another on a 1:1 basis. This is best done with array.map. Also, you should cache the result of $(this) so that you don't call it repeatedly. Additionally, this inside a jquery.each is the current item, which should be the same as the first argument in array.map's callback.

var parallaxElements = s.parallaxElements.get().map(element => {
  const wrappedElement = $(element);

  return {
    element: wrappedElement,
    ratio: wrappedElement.data('parallax-ratio'),
    offset: wrappedElement.closest('.parallax-section').offset().top - 60,
    current: 0
  };
});

Now for your animation, I suggest you avoid using requestAnimationFrame in this case. It will still be running even when no position changes are taking effect, eating up cycles.

Since your parallax effect only takes place only when scroll position has changed, I suggest you listen for the window's scroll event and do changes when scrolled. As for the movement animation, use CSS transitions.

$(window).scroll(event => {
  // Update element positions using transform translate
});

.parallax-element{
  transition: transform 0.2s;
}


Implementation of Radix Sort algorithm for sorting integers in c++ I wrote the following code for Radix Sort algorithm for number sorting. Any review is highly appreciated.

  You can also view and run/test the code here Radix Sort

#include<iostream>
using namespace std;

int getNumberAtPosition(int num,int position){
    return (num/position)%10;
}
void radixSort(int array[],int length){
int sizeOfEachBucket = length;
int numberOfBuckets = 10;
int buckets[10][sizeOfEachBucket];
int large = 0;
int maxPasses = 0;
//finding largest number from array
for(int i=0; i<length; i++){
    if(array[i]>large){
        large = array[i];
    }
}

//finding the number of passes
while(large != 0){
     maxPasses++;
     large = large/10;
}
cout<<"Max passes ="<<maxPasses<<endl;
int position = 1;
int bucketIndex = 0;
int newListIndex = 0;
int arrayLengths[10];
for(int i=0; i<maxPasses; i++){
    //cout<<"i ="<<i<<endl;
    for(int k=0; k<=9; k++){
         //cout<<"k ="<<k<<endl;
         bucketIndex = 0;
        for(int j=0; j<length; j++){
            if(k==getNumberAtPosition(array[j],position)){
                buckets[k][bucketIndex] = array[j];
                bucketIndex++;
            }
        }
        arrayLengths[k] = bucketIndex;
    }
    position = position*10;
    int newArrayIndex = 0;
    for(int k=0; k<=9; k++){
         //cout<<"k ="<<k<<endl;
         bucketIndex = 0;
         for(int x=0; x<arrayLengths[k];x++){
            array[newArrayIndex] = buckets[k][x];
            newArrayIndex++;
         }
    }

}
for(int i=0; i<length; i++){
    cout<<array[i]<<"\t";
}
}

First things first, don't use using namespace std in header files, where your radix sort implementation should be. Besides, convenience isn't a valid excuse when the only thing you import from std is cout: just type std::cout and you're done.
One liner functions are often useless and noisy: you need to refer to the implementation to know exactly what they do, so they don't make the code more readable, and you have to come up with a name, which is not always easy. In the case of getNumberAtPosition, for instance, it's impossible to tell from the name if the position is meant for the most or least significant digit, and both are equally likely in a radix sort algorithm.
everything that isn't meant to change should be const. The only place where it isn't idiomatic is in function signature, where you often don't tag built-in type arguments passed by value as const.
Also, don't alias variables: length is only used to define sizeOfEachBucket, that's two names to track down instead of one.
Use the standard library: there may not be many things inside compared to other languages, but what's inside is very well implemented. It will also make your code more concise and expressive. For instance, the largest element in a [first, last) sequence is the result of std::max_element(first, last) (std::max_element resides in <algorithm>). Using standard containers is also a statement: a constant size array will be a std::array, whereas a variable-size one will be a std::vector.
Avoid naked loops: by that I mean loops like for (int i = 0; i < z; ++i). The nested ones are particularly difficult to read, with all those meaningless one-letter variable names. Use either range based for loops when you iterate over the whole container (e.g: for (auto item : vector)) or named algorithm when your loop has a standardly implemented purpose (std::for_each, std::copy, etc.).
When implementing your own algorithms, try to use an stl-like interface: iterators are preferable because they abstract the concrete container-type. Your algorithm won't work on an std::list although it very well could be (radix sort doesn't rely on random access like quick sort does).

Here's an example of better-looking (though not thoroughly tested) code:

#include <algorithm>
#include <vector>
#include <array>
#include <cmath>

template <typename Iterator>
void radix_sort(Iterator first, Iterator last) {
    const int max_divisor = std::pow(10, std::log10(*std::max_element(first, last)));
    for (int divisor = 1; divisor < max_divisor; divisor *= 10) {
        std::array<std::vector<int>, 10> buckets;
        std::for_each(first, last, [&buckets, divisor](auto i) {
            buckets[(i / divisor) % 10].push_back(i);
        });
        auto out = first;
        for (const auto& bucket : buckets) {
            out = std::copy(bucket.begin(), bucket.end(), out);
        }
    }
}

EDIT: since the algorithm exposed in the question relies on decimal digits, I also formulated a base-10 based algorithm. But thinking back about this, I feel like my answer isn't complete if I don't precise that a base-two approach is more optimal (and more generally used as far as I know). Why is that?

because binary arithmetic is easier for a computer (not a very strong reason since decimal arithmetic is often optimized into binary arithmetic by the compiler);
because -and that's a much stronger reason- you can the rely on a very well-known algorithm to distribute your number between buckets, an algorithm that moreover does it in place, thus without any memory allocation;
by the way, that algorithm is std::stable_partition

And here is a sample:

template <typename Iterator>
void binary_radix_sort(Iterator first, Iterator last) {
    using integer_type = std::decay_t<decltype(*first)>;
    bool finished = false;
    for (integer_type mask = 1; !finished; mask <<= 1) {
        finished = true;
        std::stable_partition(first, last, [mask, &finished](auto i) {
            if (mask < i) finished = false;
            return !(mask & i);
        });
    }
}


Creating a dictionary of multiple results I am creating list of dictionary from two different results. I appreciate any improvement suggested.

redditFile = urllib2.urlopen("http://www.bing.com/images?q="+word)
redditHtml = redditFile.read()
redditFile.close()
soup = BeautifulSoup(redditHtml)

productDivs = soup.findAll('div', attrs={'class' : 'dg_u'})
for div in productDivs:
    #print div.find('a')['t1']
    #print div.find('img')['src2']
    img_result = {}
    img_result['link'] = div.find('img')['src2']
    img_result['title'] = div.find('a')['t1']
    image_result_final.append(img_result)

final_result['img'] = image_result_final

print "*"*25

redditFile = urllib2.urlopen("http://www.bing.com/videos?q="+word)
redditHtml = redditFile.read()
#redditHtml = open('source.txt').read()
redditFile.close()
soup = BeautifulSoup(redditHtml)
productDivs = soup.findAll('div', attrs={'class' : 'dg_u'})
for div in productDivs:
    if div.find('div', {"class":"vthumb", 'smturl': True}) is not None:
        #print div.find('div', {"class":"vthumb", 'smturl': True})['smturl']
        #print div.find("div", {"class":"tl fade"}).text
        video_result = {}
        video_result['link'] = div.find('div', {"class":"vthumb", 'smturl': True})['smturl']
        video_result['title'] = div.find("div", {"class":"tl fade"}).text
        video_result_final.append(video_result)

final_result['video'] = video_result_final
import json
print json.dumps(final_result)

Since I'm not really a web guy, this is going to be a style review, like my other reviews.

Why are you mixing camelCase and underscore_case together when naming variables? Variables and functions should be underscore_case, and classes should be PascalCase.
This seems like something that could be separated into functions, which allows for easier reusability. See if you can take parts of the code and separate them into their relevant parts.
I noticed that the 2nd-to-last line of this Python script is import json. You shouldn't be importing libraries after code has run. You should put imports/includes at the top of your script.
Why are you doing this? print "*"*25. It doesn't really seem like it's needed. Same with print json.dumps(final_result). That should be a return inside of a function.
You shouldn't be using file.close(). The reason for this is that the file isn't explicitly closed. You should be using a with..as context manager, like this.

with open("path/to/myfile.ext", "mode") as file_name:
     # Blah blah blah code goes here

Finally, if you aren't using parts of the code, don't comment them out. Just remove them completely. Commented out lines of code are an eyesore to look at.

That's about all I have. If there's anything else you might want me to cover, just mention it in the comments, and I'll see what I can do. Hope this helps!


Importing data into PostgreSQL from remote text file using ftplib class I need to read a remote file using FTP and process it and insert the processed data to a PostgreSQL database in another server.

The below code is working fine, but i want some advice to modify few things.

In this line i don't want to write the actual details, I want that to
be hidden from my script. How can i do that?

ftp = FTP('server.com','user_name','password')

The script downloads the file to my local system and process it as
it is a local file. Is there any way to read and process it without
downloading it to the source server (there might be permission issues
also)?
If there is no way rather than downloading it to the source, should I
specify a path where this file would be downloaded
rather than the way I have written it?
Is there anything which i can do to improve this code?

Any guidance will be of great help.

import psycopg2
import time
import os
#import MySQLdb
#import paramiko
from ftplib import FTP
#from utils.config import Configuration as Config
#from utils.utils import get_global_config

start_time = time.perf_counter()

cnx_psql = psycopg2.connect(host="localhost", database="postgres", user="postgres",
                        password="postgres", port="5432")

# Cursors initializations
cur_psql = cnx_psql.cursor()

def getFile(ftp, filename):
    try:
        local_filename = os.path.join(r"/Users/linu/Downloads/", filename)
        lf = open(local_filename, "wb")
        ftp.retrbinary("RETR " + filename ,lf.write)
        print("file copied")
    except:
        print ("Error")
try:

    filePath='''/Users/linu/Downloads/log'''
    #filePath='''/cmd/log/stk/log.txt'''
    table='staging.stock_dump'

    SQL="""DROP TABLE IF EXISTS """+  table + """;CREATE TABLE IF NOT EXISTS """+ table + """
    (created_date TEXT, product_sku TEXT, previous_stock TEXT, current_stock TEXT );"""

    cur_psql.execute(SQL)
    cnx_psql.commit()

    ftp = FTP('server.com','user_name','password')
    print("FTP connection succesful")
    data = []
    ftp.cwd('/stockitem/')
    getFile(ftp,'log')

    read_file = open(filePath, "r")
    my_file_data = read_file.readlines()

    for line in my_file_data:
        if 'Stock:' in line:
            fields=line.split(" ")
            date_part1=fields[0]
            date_part2=fields[1][:-1]
            sku=fields[3]
            prev_stock=fields[5]
            current_stock=fields[7]
            if prev_stock.strip()==current_stock.strip():
                continue
            else:
               cur_psql.execute("insert into " + table+"(created_date, product_sku, previous_stock , current_stock)" + " select CAST('" + date_part1+ " "+ date_part2 + "' AS TEXT)" +", CAST('"+sku+"' AS TEXT),CAST('" + prev_stock +"' AS TEXT),CAST('" +current_stock  + "' AS TEXT);")
    cnx_psql.commit()
    cur_psql.close()
    cnx_psql.close()
    print("Data loaded to DWH from text file")
    print("Data porting took %s seconds to finish---" % (time.perf_counter() - start_time))
except (Exception, psycopg2.Error) as error:
        print ("Error while fetching data from PostgreSQL", error)
        print("Error adding  information.")
        quit()
finally:
    ftp.close()

In this line i don't want to write the actual details,i want that to be hidden from my script.How can i do that? ftp = FTP('server.com','user_name','password')

You may want to declare constants, either at the beginning of your file or in a Credentials class that would be used as an enum:

SERVER = 'server.com'
USER_NAME = 'Linu'
PASSWORD = 'CR.SEisGreat'

ftp = FTP(SERVER, USER_NAME, PASSWORD)

You may also want to encrypt your password, with base64 or something alike. Storing passwords in files isn't a good idea anyway, so if you're using this file as a script you're going to call via bash or something alike, I would use a placeholder like argparse that would prompt your password when calling the script:

parser = argparse.ArgumentParser(description='Reading a file from a distant FTP server.')
parser.add_argument('--passwd', dest='password', type=str,
                   help='password required for FTP connection')

  The script downloads the file to my local system and process it as it
  is a local file, Is there anyway too read and process it without
  downloading it to the source server(there might be permission issues
  also)?

I don't know much about FTP manipulation with Python so I'm not sure there is a way to read a file without having to download it.

  If there is no way rather than downloading it to the source, shall I
  able to mention specific path where this file would be downloaded
  rather than the way i have written?

Again, you may place the path into a class constant (or in a separate class):

FILE_PATH='''/path/to/file/'''

  Is there anything which i can do to improve this code?

Imports

import psycopg2
import time
import os

I would edit this to import only the parts you need, e.g.

from psycopg2 import connect, sql
from time import perf_counter

There is no need to import the whole module if you only use a couple of functions, so whenever you can, I'd suggest you only import what you will actually use.

Raising exceptions

try:
    # ...
except:
    print ("Error")

I would raise an exception here, since it's a undesired behaviour:

 try:
    # ...
except Exception as e:
    print ("Error: {}".format(e))

You may want to do the same with your psycopg and FTP errors, I see you catch them but don't read their value. It may provide a more helpful message than the prints, which just indicate you encountered an error but don't tell more about what actually happened.

SQL placeholders

SQL="""DROP TABLE IF EXISTS """+  table + """;CREATE TABLE IF NOT EXISTS """+ table + """
(created_date TEXT, product_sku TEXT, previous_stock TEXT, current_stock TEXT );"""

Should you want to make your code more generic, you could transform the above mentioned statement into:

sql.SQL="""DROP TABLE IF EXISTS {table_name} ; CREATE TABLE IF NOT EXISTS {table_name}
 (created_date TEXT, product_sku TEXT, previous_stock TEXT,
 current_stock TEXT );""".format(
    table_name = sql.Literal(table)
)

That way you may reuse the query on other tables. You may do the same on the table attributes, i.e.

keys = ['created_date', 'product_sku', 'previous_stock', 'current_stock']
sql.SQL("""CREATE TABLE IF NOT EXISTS {} ({});""").format(
    sql.Identifier(table),
    sql.SQL('{} TEXT,').join(map(sql.Identifier, keys))
)

It alleviates the query and makes it more generic and reusable. By the way, I don't think you need to add IF NOT EXISTS after CREATE since you already deleted the table in the first part of your query.


Maximise XOR of two elements I have a number x and I need to choose another number y from the given range [l, r] such that x XOR y is maximum.

This is what I did till now:

def maxXOR(x, l, r):
    max_ = 0
    for y in range(l, r+1):
        temp = x^y
        if temp>max_:
            max_ = temp
    return max_

But it is quite slow. How can I optimise it?

As to the algorithm

The general rule here is don't search when you can calculate.

XOR is fundamentally a bitwise operation. Think about what the XOR operation is doing, on a bit by bit basis.

First, consider a simpler problem where you have to maximise the result with any number at all. (limited only to the number of bits in your input number) Suppose your input is an 8 bit number, perhaps 01100111. You want the output to be 11111111. (or 255 in decimal) So find the number that XORs with your input to give that: the first bit should be 1, the next 0, and so on until you get 10011000.

Unfortunately, you can't necessarily do that because you're restricted in the numbers you're allowed to use. Even so, to maximise the number, you need to have bits end up hot if possible, starting with the most significant bit. Work out which ranges within the provided region would leave the most significant bit hot, then look at the next bit, and repeat until there is only one candidate remaining. That way you'll have a loop running the number of bits in your number (say, 8) instead of a loop running the number of possible candidates (say, 256).

In more general commentary on the code:

Python preferred style is to words separated by underscores in function names, as in max_xor.
Although single letter variable names are probably acceptable with such narrow scope, descriptive names are better. E.g. l and r are not obviously lower and upper bounds.
Although max_ is legal, I would personally avoid being that close to a reserved word.
Speaking of that particular reserved word, I'd replace that if with running_max = max(running_max, temp)
If we're being very pythonic, and not changing your algorithm, you could use a generator comprehension expression for the whole thing. It would look like return max(x^y for y in range(l, r+1))


Go API server - request handlers becoming excessively long I'm developing a API server in Go. My route handlers are becoming excessively long, especially when the response needs a lot of information.

For the following response type:

// StateResponse is queried by the client to get the entire initial
// database state.
type StateResponse struct {
    StatusCode  int                `json:"status"`
    User        store.User         `json:"user"`
    Enrolled    []store.Enrol      `json:"enrolled"`
    Assessment  []store.Assessment `json:"assessment"`
    Submissions []store.Submission `json:"submissions"`
}

I have this handler:

func stateHandler(store *store.Store) http.HandlerFunc {
    return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        if !request.IsAuthorized(r) {
            log.Println("Unauthorized")
            unauthorizedHandler().ServeHTTP(w, r)
            return
        }
        if r.Method != http.MethodGet {
            notFoundHandler().ServeHTTP(w, r)
            return
        }
        urlParams, ok := r.URL.Query()["email"]
        if !ok || len(urlParams) != 1 {
            log.Println("Invalid email")
            badRequestHandler("invalid email").ServeHTTP(w, r)
            return
        }
        email := urlParams[0]
        user, err := store.GetUserByEmail(email)
        if user == nil || err != nil {
            log.Printf("Could not find user: %v", err)
            notFoundHandler().ServeHTTP(w, r)
            return
        }
        enrolled, err := store.GetEnrolByUser(user.UID)
        if enrolled == nil || err != nil {
            log.Printf("Could not find enrolled: %v", err)
            notFoundHandler().ServeHTTP(w, r)
            return
        }
        assessments, err := store.GetAssessmentForUser(user.UID)
        if assessments == nil || err != nil {
            log.Printf("Could not find assessment: %v", err)
            notFoundHandler().ServeHTTP(w, r)
            return
        }
        submissions, err := store.GetSubmissionsForUser(user.UID)
        if submissions == nil || err != nil {
            log.Printf("Could not find submissions: %v", err)
            notFoundHandler().ServeHTTP(w, r)
            return
        }
        // Send response
        resp := StateResponse{
            StatusCode:  200,
            User:        *user,
            Enrolled:    enrolled,
            Assessment:  assessments,
            Submissions: submissions,
        }
        respBytes, err := json.Marshal(resp)
        if err != nil {
            unauthorizedHandler().ServeHTTP(w, r)
            return
        }
        w.Write(respBytes)
    })
}

I know this is imperfect. The error handling is repetitive. I tried using the errWriter technique from Rob Pikes "errors as values" article, but I couldn't make it work since every database query (store functions, in this case) are slightly different.

Some random notes:

Your use of notFoundHandler().ServeHTTP(w, r) is weird. Why do you have a function returning this if it doesn't take any params? You'd probably be better off just having a function writeNotFound(w, r). This mirrors the approach of net.http, which already provides functions like this.
From a RESTful approach, you shouldn't be returning the StatusCode in the JSON. That should be the HTTP status code.
This is minor, but what is an Enrol? Enrollment?
if r.Method != http.MethodGet, you should be returning a 405 Method Not Allowed instead of a 404 Not Found
If json.Marshal fails, you should return a 500 Internal Server Error instead of an unauthorized
Be careful with variables shadowing a package (store *store.Store). That can have unexpected consequences. Ideally you package name and struct should form a complete thought like http.Server (instead of server.Server). Unfortunately, in some scenarios this is difficult.
Your store functions don't follow Go conventions. If you are returning (X, error) then you should only check err != nil. Either err != nil (and you ignore the first thing) or err = nil and the first thing is valid. Don't do assessments == nil || err != nil. This should just be err != nil. You may need to change how the store functions behave to conform to this pattern.

The overarching point

Repetitive error handling is an unfortunate consequence of some of the design decisions of Go (namely, a lack of parametric polymorphism). In this case however, even if you had generics (to pull out the repetitive error handling logic), you'd still need some way to bubble the return up to the http.HandlerFunc. And that would require something like:

if !tryQuery(func() (User, error) { return store.GetUserByEmail(email) }) {
    return
}

Where tryQuery returns false if store.GetUserByEmail(email) returned an error. This is certainly shorter, but it's dubious that this is an improvement. You also couldn't write such a tryQuery currently in go because the first return type User would need to be generic. Sure, you could cast through interface{}, but that's a world of ugliness that you don't want to deal with. It would require you to do lots of casts, which incur a runtime cost and are (programmer) error prone.

So what to do? Well, any refactoring you embark on will be a tradeoff. The go ethos often prefers more verbose, repetitive code because it's easier to follow. But this comes at a cost. Eventually code becomes hard to reason about and harder to test because units have many responsibilities.

That said, I think there are some patterns you could use that would really help clear this code up. In the end, the code should be easier to read and easier to test.

First, checks like "is the user authorized" is often better suited for middleware. This pattern will allow you write the authorization check once and then wrap every handler in this middleware that needs it:

func needsAuthorization(handler http.HandlerFunc) http.HandlerFunc {
    return http.HandlerFunc(func (w http.ResponseWriter, r *http.Request) {
        if !request.IsAuthorized(r) {
            log.Println("Unauthorized")
            writeUnauthorized(w, r)
        } else {
            handler(w, r)
        }
    })
}

Then you can use it like so:

func stateHandler(store *store.Store) http.HandlerFunc {
    return needsAuthorization(func(w http.ResponseWriter, r *http.Request) {
        // This is only called if user is authorized
        // Check email, get assessments, etc.
    })
}

This is appropriate for checks like authorization (and maybe checking the request method), but shouldn't be used for everything.

Another option here (although sometimes frowned upon by the purists) is to use an existing HTTP framework that handles routing (including method) and maybe already has utilities for injecting middleware. This is somewhat in conflict with Go's obvious philosophy as there is some magic introduced. As with refactoring , there are tradeoffs here. Frameworks abstract away some common patterns to enable more succinct business logic. For example, with a buffalo router you can do:

a.GET("/state", stateHandler(store))

The meat of your problem still exists. All of the interaction with your models and constructing the response still is a lot of repetitive error handling. The ideal approach here would be an Applicative pattern which is capable of constructing data up until the point of an error. In Haskell, this would look something like:

user <- getUserByEmail =<< getParam "email"
return $ StateResponse <$> user <*> getEnrollments user <*> getAssessments user
                       <*> getSubmissions user

The beauty here is that all of these steps (user, getEnrollments user, etc.) can fail. And when they do, the error is returned instead. But until one occurs, we just continue to construct the data. Note that this looks almost like how you build the StateResponse struct in Go, except it also does error handling.

In Go, you'd have to duplicate some (trivial) code to achieve something like this. And I'm not sure it would be worth it. You'd end up with something like:

state := StateResponseBuilder{}

state.SetEmail(func() (string, bool) { return  r.Url.Query()["email"] })
state.SetUser(func() (store.User, error) { return store.GetUserByEmail(state.Email) })
state.SetEnrollments(func() ([]store.Enrollment, error) { return store.GetEnrollmentsByUser(state.User.UID) })
state.SetAssessments(func() ([]store.Assessment, error) { return store.GetAssessmentForUser(state.User.UID) })
state.SetSubmissions(func() ([]store.Submission, error) { return store.GetSubmissionsForUser(state.User.UID) })

respBytes, err := state.Build()
if err != nil {
    // return error
} else {
    w.Write(respBytes)
}

The idea here is that StateResponseBuilder somewhat follows the Pike technique. Each SetX looks like this:

type StateResponseBuilder struct {
    Err error
    X X
}

func (s *StateResponseBuilder) SetX(f func() (X, error)) {
    if s.Err != nil {
        return
    }

    if x, err := f(); err != nil {
        self.Err = err
    } else {
        self.X = x
    }
}

Your error short circuiting is handled by checking if s.Err != nil before running f(). s.Err is the first error we encountered or nil if everything so far as succeeded.

You'll note this requires a lot of code repetition in the SetX methods. Furthermore, the resulting code is probably less obvious even though it lacks all the error checking.

That said, such a pattern can be useful in certain contexts.

A better approach

A more suitable pattern, in my opinion, would be to separate concerns and use some indirection to make errors responsible for reporting themselves (instead of making your handler responsible for knowing how to report them). The big idea here is that currently your handler has many jobs. This is what is making it slightly unwieldy. You can separate its main jobs into two categories:

HTTP related (specifically, translating errors/data to the appropriate constructs in HTTP)
Interacting with store

If you separated these two, you could de-duplicate some of your repetitive HTTP error handling code. Further, this would abstract your controller logic away from HTTP so if you wanted to provide another kind of API (maybe some sort of custom protocol over TCP), you could do this fairly easily. Doing something like this would make your handler look like:

func stateHandler(store *store.Store) http.HandlerFunc {
    return needsAuthorization(onlyGet((http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        var email string

        emails := r.URL.Query()["email"]
        if len(emails) == 1 {
            email = emails[0]
        }

        response, err := buildStateResponse(store, email)
        if err != nil {
            err.WriteHTTP(w)
        } else {
            w.Write(response)
        }
    })))
}

We've done several things here. First, all the HTTP error handling has been reduced to one location. This should make logging much easier. All HTTP-related things are located just in the handler. Note that we did push some of this into the errors themselves. This kind of indirection allows us to not have to handle every case in the HTTP handler. The advantage here is if another error condition arises when you're working on store, you don't have to go through all of your HTTP handlers and handle outputting the error each place a store function is used. Doing this would require you to create a custom error interface that has WriteHTTP, but you could just as easily make this a function that takes an error as its first parameter. The simplicity of the pure controller logic speaks for itself:

// You may want to return the `StateResponse` here and handle serialization in the HTTP handler
func buildStateRespones(store *store.Store, email string) ([]byte, error) {
    user, err := store.GetUserByEmail(email)
    if err != nil {
        return nil, err
    }

    enrolled, err := store.GetUserEnrollments(user.UID)
    if err != nil {
        return nil, err
    }

    assessments, err := store.GetUserAssessments(user.UID)
    if err != nil {
        return nil, err
    }

    submissions, err := store.GetUserSubmissions(user.UID)
    if err != nil {
        return nil, err
    }

    return json.Marshal(StateResponse{
        User: *user,
        Enrolled: enrollments,
        Assessment: assessments,
        Submissions: submissions,
    })
}

You still need the error checks, but now you aren't trying to do so much inside them. This code should be much easier to follow. What's more, if the new error check proposal lands, this code will immediately be convertible to this much more readable form:

func buildStateRespones(store *store.Store, email string) (*StateResponse, error) {
    user := check store.GetUserByEmail(email)
    enrolled := check store.GetUserEnrollments(user.UID)
    assessments := check store.GetUserAssessments(user.UID)
    submissions := check store.GetUserSubmissions(user.UID)

    return &StateResponse{
        User: *user,
        Enrolled: enrollments,
        Assessment: assessments,
        Submissions: submissions,
    }, nil
}

Here we've separated business logic from protocol specific "presentation" logic. The result is that each separated part is now easier to reason about (and easier to unit test!).


Generic linked-list library in C I'm pretty new to C so I decided to implement SRFI-1 (linked-list library) to help me learn.

What I have so far is working, but only handles integers.

typedef struct pair {
  int car;
  struct pair *cdr;
} pair;

From what I've read I can use a void * for the car:

typedef struct pair {
  void *car;
  struct pair *cdr;
} pair;

This works but I get lots of these...

llist.c:262:3: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘void *’
llist.c:27:7: note: expected ‘void *’ but argument is of type ‘int’

I've found some workarounds but before diving in and fixing everything I want to be sure this is the appropriate way to go.

The only other way I can think of is using some sort of generic object type:

typedef struct object {
  union {
    int fixnum;
    double flonum;
  }
}

typedef struct pair {
  object *car;
  struct pair *cdr;
} pair;

Or something similar.

Is there a best practice for generic functions/data types?

The full source is here.

void* is the standard to implement such generics in C. The trouble with union is that the end-user cannot put their own types/structs in it. With void * a pointer to a user-defined struct can be used. However, be careful about memory leaks!

The warnings you are getting is because you haven't consistently used void*.

llist.c:262:3: warning: format ‘%d’ expects type ‘int’, but argument 2 has type ‘void *’

This indicates that you are printf'ing the data as if it were an int. But you don't what it is so you can't do that. Either don't provide printing options or provide a way to control how the object prints.

llist.c:27:7: note: expected ‘void *’ but argument is of type ‘int’

You have a void * and you are passing it to a function that takes int. Everything inside your library should be using void * not int. Only the actual code using your library should conver the void * into int or whatever they are using.


Stack Implementation in C++ This is my first template implementation. I'm trying to learn C++ and Algorithms. Any constructive criticism on code quality, readability is welcome. Everyone has their own style, but there are certain rules which all good programmers should follow. Kindly remark as to if I have followed those and what rules are missing.

#include <iostream>
#include <new>
using std::cout; using std::cin; using std::endl;
using std::nothrow; using std::size_t;

template<typename T> class Stack {
 public:
  // constructor for class
  Stack() { count = 0;
            last = NULL; }
  // destructor for class
  ~Stack() {  if (count > 0) Clr(); }
  // push item at last of stack
  void Push(T item);
  // pop item from last of stack
  T Pop();
  // get size of stack
  size_t Size();
  void Clr();       // delete all the elements
  // print all the elements
  void Print();
 private:
  // the stack will store elements in the form of a linked list
  struct Node {
    T value;
    Node* next;
  };
  Node* last;   // last points to the last item of the stack
  size_t count;    // number of elements in stack
};
/*
Check for memory allocation first. If memory allocated, then Push element in
the stack.
 */
template<typename T> void Stack<T>::Push(T item) {
  Node* node = new (nothrow) Node;
  if (node == NULL) {
    cout << "Memory allocation failed " << endl;
    return;
  } else {
    node->value = item;
    if (count == 0) {
      node->next = NULL;
      last = node;
      ++count;
    } else {
      node->next = last;
      last = node;
      ++count;
    }
  }
}
/*
Delete the elements
 */
template<typename T> void Stack<T>::Clr() {
  Node* node = last;
  while (count != 0) {
    Node* tempnode = node;
    node = node->next;
    delete tempnode;
    --count;
  }
}
/*
Pop the last element of the stack and return it
 */
template<typename T> T Stack<T>::Pop() {
  if (count == 0) {
    cout << "No element to delete" << endl;
    return (T)0;
  } else {
    Node* node = last;
    T tempval = node->value;
    last = node->next;
    delete(node);
    --count;
    return tempval;
  }
}
/*
Print all the elements
 */
template<typename T> void Stack<T>::Print() {
  if (count == 0) {
    cout << "No elements to print" << endl;
    return;
  } else {
    cout << "Printing from top of the Stack to Bottom" << endl;
    Node* node = last;
    while (node != NULL) {
      cout << node->value << "->";
      node = node->next;
    }
    cout << endl;
  }
}
/*
Get the size of the Stack
 */
template<typename T> size_t Stack<T>::Size() {
  return count;
}
/*
Main function
 */
int main() {
  Stack<int> s;
  s.Push(12);
  s.Push(10);
  s.Push(23);
  s.Push(34);
  cout << "The value Popped from the Stack: " << s.Pop() << endl;
  s.Print();
  return 0;
}

NULL versus nullptr

You shouldn't be using NULL, as you did in various places, like here:

node->next = NULL;

NULL is deprecated, and you should be using nullptr, like this:

node->next = nullptr;

If this is legacy code, and you need to support users running old compilers that date to before C++11, you should keep using NULL.

std::endl versus "\n"

Rather than using std::endl, you should just suffix this onto the end of any std::cout statements:

<< "\n";

You should be doing this unless you're very sure that you want to flush the output buffer each time you run std::cout. If you do need to flush the output buffer, then you should keep using std::endl.

Nitpicks

There are a fair amount of things that I want to pick at here, so bear with me.

You should remove all the using statements at the top of your code. By removing the prefix of std:: on some of it's members, your code loses clarity. The only time it's really appropriate to use a namespace, or namespace members is when you have a really deep nested namespace, like foo::bar::baz::barbaz::blah.
Secondly, there are a lot of useless comments. For example, the comment by the function signature for Clr, is not really needed. If you give Clr a better name, like removeAll, the need for the comment vanishes. This applies to many other comments as well.
Finally, the Stack class should have a toString method, which should return a std::string-representation of the stack.


Perl script to print multi line log entries which has a match for given pattern I am a Java programmer and very new to Perl. I decided to work on a simple script that could solve a problem I encounter in my day to day work. This script will search the log file for a pattern and print the complete potentially multi line log statement that has a match for this pattern. Additionally, the matched pattern should be displayed in color for highlighting purpose.

I've used very basic features of Perl and as you can see, the code very verbose (like Java some might say ;) ) and there are two main areas I'm aiming to improve:

I want to see Perl's idiomatic ways to make the program less verbose without sacrificing too much readability.
Any poor practice is that I have used. I purpose fully left out "strict" and "warnings" as I want to use Perl for loose and less verbose features.

I'd be really grateful for some feedback to make this more elegant. I'll only be using Perl 5.8 as that is what available on most systems at my place.

#!/usr/bin/env perl

use Term::ANSIColor;

my $pattern = qr"[.a-zA-Z0-9]*Exception";
my $hilight = 'black on_yellow';
my $timestamp = qr"\d\d:\d\d"; #To identify beginning of new log entry.

my $begin = qr/^$timestamp/;

open(my $fn, '<', $ARGV[0]) or die "Could not open file '$ARGV[0]' $!";
while (<$fn>) {
    if ( $_ =~ m/($begin)/ ) {
        if($found) {
            foreach(@fh) {
                if ( $_ =~ m/($pattern)/ ) {
                    $matched = $1;
                    @parts = split /($pattern)/, $_;
                    foreach(@parts) {
                        if ($_ eq $matched) {
                            print colored($matched, $hilight);
                        } else {
                            print $_;
                        }
                    }
                } else {
                    print $_
                }
            }
        }

        if(defined @fh) {
            undef @fh;
        }
        $found = 0;
    }
    if ( $_ =~ m/($pattern)/ ) {
        $found = 1;
    }
    push (@fh, $_);
}

close $fn;

The code definitely isn't bad. I'd still use strict and warnings, though. Minor remarks:

Why do you use " for qr? / or {} are canonical.
$_ is good for short loops, and its advantage is you don't have to type it. So, I'd name the main loop's variable, as its scope is rather wide.
Avoid deep indentation. Use subroutines.
defined @fh is deprecated.

My version:

#!/usr/bin/env perl
use warnings;
use strict;

use Term::ANSIColor;

my $pattern = qr/[.a-zA-Z0-9]*Exception/;

sub output {
    my @buffer = @_;
    my $hilight = 'black on_yellow';
    for (@buffer) {
        if (my ($matched) = /($pattern)/) {
            for (split /($pattern)/) {
                print $_ eq $matched ? colored($matched, $hilight) : $_;
            }
        } else {
            print;
        }
    }
}

my $begin   = qr/^\d\d:\d\d/;

my ($found, @buffer);
open my $fh, '<', $ARGV[0] or die "Could not open file '$ARGV[0]' $!";
while (my $line = <$fh>) {
    if ($line =~ /($begin)/) {
        output(@buffer) if @buffer && $found;
        @buffer = ();
        undef $found;
    }
    push @buffer, $line;
    $found = 1 if $line =~ /$pattern/;
}

# Output the last match if it ends with an EOF instead of a timestamp.
output(@buffer) if @buffer && $found;


Passing arguments to a SendMail function referenced by addressOf operator I am trying to send daily mail alert to users based on some timer values. For that I've used Addhandler to call the sendmail() function on timer Tick. In this scenario I faced a problem and I am unable to pass arguments to the function through AddressOf.

What I wanted was to use my function, which took these parameters…

 Public Sub SendMail(ByVal UserMailId As String,
                     ByVal UserPassword As String,
                     ByVal HostName As String,
                     ByVal HostPort As String)

by calling it using AddHandler mailTimer.Elapsed, AddressOf userDetails.SendMail(parameters), but that failed with an error:

  'AddressOf' Operand name must be the name of the method without
  parenthesis

After some research, here's my solution for this problem:

Dim userDetails As New Details
' These values are from database that will changed based on some conditions given
' now it is hardcoded for an example
userDetails.HostName = "smtp.gmail.com"
userDetails.HostPort = "587"
userDetails.UserMailId = "mailuser@gmail.com"
userDetails.UserPassword = "mymailPasswo6d"
Dim mailTimer As System.Timers.Timer
mailTimer.Interval = 18000
AddHandler mailTimer.Elapsed, AddressOf userDetails.SendMail
mailTimer.Start()

Where Details is the class which is defined as follows:

Class Details
        Public UserMailId As String
        Public UserPassword As String
        Public HostName As String
        Public HostPort As String
        Public Sub SendMail()
            Try
                Dim smtpServer As New SmtpClient
                Dim eMail As New MailMessage()
                smtpServer.UseDefaultCredentials = False
                smtpServer.Credentials = New Net.NetworkCredential(UserMailId, UserPassword)
                smtpServer.Port = HostPort
                smtpServer.EnableSsl = True
                smtpServer.Host = HostName
                eMail = New MailMessage()
                eMail.From = New MailAddress(UserMailId)
                eMail.To.Add(txtemailTo.Text)
                eMail.Subject = "Test Mail"
                eMail.IsBodyHtml = False
                eMail.Body = txtMessage.Text
                smtpServer.Send(eMail)
                MsgBox("Mail Sent")
            Catch errorT As Exception
                MsgBox(errorT.ToString)
            End Try
        End Sub
    End Class

Now what my question is:

Is the method I was using the correct one? Is there any simple or alternate solution for this?
Can anyone please review the code to improve it? It gives me better results but I think some modification is required.

The System.Timers.Timer.Elapsed event needs a handling method with the signature sender As Object, e As ElapsedEventArgs. This means that any method which you want to assign this event to, by using the AddressOf operator has to have exactly this signature by the meaning of the type and order of the parameters.

Public Sub MailTimerElapsed(sender As Object, e As ElapsedEventArgs)
    ' the code which should be processed if the timer is elapsed
    ' should be either called here or be placed here
End Sub

If you plan to use the System.Timers.Timer without setting the SynchronizingObject property, you need to know that the event is raised on a ThreadPool thread, so interaction with a UI (at least with setting any value like assigning a value to a Text property of a TextBox) needs to be synchronized by your code.

Also, if the time needed to finish the codeexecution from the eventhandler exceeds the set Interval it will reentrant if the mentioned property is not set.

Read more: Timer class

These fields

Public UserMailId As String
Public UserPassword As String
Public HostName As String
Public HostPort As String

should better be properties instead of public variables. You could also consider to pass these values at calling the constructor, and make the fields Private.

You should get used to the NET style. This means calling methods which has been kept for downward compatibility like MsgBox should be avoided and replaced by the MessageBox.Show() method

Instead of placing the eventhandler for the Timer.Elapsed event inside the Details class you should place it in the calss where you create the timer object and call from inside the handler your desired mail sending method.


Constructing Unique String Sequence I am brushing up on my Java skills by trying to solve the below assignment problem I found on the internet:

Write a Java method that accepts two strings as parameters and returns
a string that contains all unique two-character strings whose first
character comes from the first string and second character comes from
the second string. All two-character strings in your returned string
should be separated by a space. Use ordinary string concatenation in
your solution. Look at the examples below for a "hint" on how to
proceed and look at the String API for methods you can use to simplify
your solution.
Example
First string = ABCD
Second string = EFGH
Returned string > AE AF AG AH BE BF BG BH CE CF CG CH DE DF DG DH

How can I improve this code?
package com.assignments.java;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * This is an Assignment Program for Java
 *
 * @author SaiUpadhyayula
 *
 */

public class JavaAssignmentOne {
    public static void main(String[] args) throws IOException {
        BufferedReader bReader = new BufferedReader(new InputStreamReader(
                System.in));

        System.out.println("Enter First String");
        String firstString = bReader.readLine();

        System.out.println("Enter Second String");
        String secondString = bReader.readLine();

        String returnedString = constructCharSequence(firstString, secondString);
        System.out.println("Returned String : " + returnedString.trim());
    }

    public static String constructCharSequence(String firstString,
            String secondString) throws IOException {

        String biggerString = firstString;
        String smallerString = secondString;
        String returnedString = "";

        // Determine the smaller and bigger Strings from
        // the given two input strings
        if (firstString.length() <= secondString.length()) {
            biggerString = firstString;
            smallerString = secondString;
        } else {
            biggerString = secondString;
            smallerString = firstString;
        }

        // Construct the given required character sequence
        // by iterating over the two input strings

        for (int i = 0; i < biggerString.length(); i++) {
            for (int j = 0; j < smallerString.length(); j++) {

                // As we require unique two-character string
                // check whether the string sequence already exists
                // in the returnedString
                if (!returnedString.contains("" + biggerString.charAt(i)
                        + smallerString.charAt(j) + "")) {
                    returnedString = returnedString + biggerString.charAt(i)
                            + smallerString.charAt(j) + " ";
                }
            }
        }
        return returnedString;
    }
}

Don't declare to throw if you don't throw

The constructCharSequence declares throws IOException but it will never throw that.

Pay attention to the specs

It's extremely important to pay attention to the spec,
so you implement what is required,
and you don't miss your target,
or even, shoot for the wrong target.

In this example:

  [...] return a string that contains all unique two-character strings whose first character comes from the first string and second character comes from the second string

For the input strings "ABCD", "EFG" your method returns
"EA EB EC ED FA FB FC FD GA GB GC GD",
which fails the specs.
A passing string would be for example: "AE AF AG BE BF BG CE CF CG DE DF DG"

Watch out for logical errors

Read this:

    if (firstString.length() <= secondString.length()) {
        biggerString = firstString;
        smallerString = secondString;

The code paraphrased:
if the first string is shorter, then the bigger string is the first string.
Shouldn't that be the other way around?
This way would have made more sense:

    if (firstString.length() < secondString.length()) {
        biggerString = secondString;
        smallerString = firstString;

Duplicated code

In these lines,
the code for combining the two characters is duplicated:

if (!returnedString.contains("" + firstString.charAt(i) + secondString.charAt(j) + "")) {
    returnedString = returnedString + firstString.charAt(i) + secondString.charAt(j) + " ";

It would be better to put firstString.charAt(i) + secondString.charAt(j) into a local variable and use that in the two expressions.

Half-baked constructCharSequence

The constructCharSequence method is poorly named.
Since it's defined to return a String,
we already know that it constructs some sort of character sequence,
so the name says nothing new.
createUniqueCharPairs would be better.

And it doesn't finish the job.
It returns a string with an extra space at the end.
Callers of this method need extra knowledge of this,
and trim if necessary.
It would have been better to trim the string before returning.

Inefficient implementation

!returnedString.contains is inefficient.
For example,
when both strings contain unique characters,
the (growing) returnedString will be traversed from start to end in every iteration.
You could use a Set or a boolean[] to track the characters that were already used.

Suggested implementation

With the above suggestions applied:

public String createUniqueCharPairs(String firstString, String secondString) {
    Set<Character> seenFirst = new HashSet<>();
    StringBuilder builder = new StringBuilder();

    for (int i = 0; i < firstString.length(); ++i) {
        char first = firstString.charAt(i);
        if (seenFirst.contains(first)) {
            continue;
        }
        seenFirst.add(first);

        Set<Character> seenSecond = new HashSet<>();

        for (int j = 0; j < secondString.length(); ++j) {
            char second = secondString.charAt(j);
            if (seenSecond.contains(second)) {
                continue;
            }
            seenSecond.add(second);

            builder.append(" ").append(first).append(second);
        }
    }
    return builder.substring(1);
}

Although the assignment explicitly said to use string concatenation,
the use of a StringBuilder instead is trivially easy to understand,
and it's good to adopt good practices like this one early.

I also changed the trimming logic,
opting to append space + char1 + char2,
and at the end return the result without the first space char.
This is slightly more efficient than trimming.

And here are some JUnit tests to verify it actually works as expected:

@Test
public void test_ABCD_EFGH() {
    assertEquals("AE AF AG AH BE BF BG BH CE CF CG CH DE DF DG DH", createUniqueCharPairs("ABCD", "EFGH"));
}

@Test
public void test_ABCD_EFG() {
    assertEquals("AE AF AG BE BF BG CE CF CG DE DF DG", createUniqueCharPairs("ABCD", "EFG"));
}

@Test
public void test_ABAB_EFG() {
    assertEquals("AE AF AG BE BF BG", createUniqueCharPairs("ABAB", "EFG"));
}

@Test
public void test_ABAB_EFEF() {
    assertEquals("AE AF BE BF", createUniqueCharPairs("ABAB", "EFEF"));
}


Get sum of an array in 3 ways, for, while and recursive So i was trying to find sum of an array using 3 ways in perl6

for
while
recursive

(I know there are inbuilt perl6 functions for this)

I want to know if there is a better way to do this or is this it?

sub sumFor(@list)
{
   my $sum = 0;
   for (@list)
   {
      $sum += $_;
   }
   return $sum;
}

sub sumWhile(@list)
{
   my $sum = 0;
   my $index = 0;
   while ($index < @list.elems)
   {
      $sum += @list[$index++];
   }
   return $sum;
}

sub sumRec(@list, $index = 0)
{
   my $sum = 0;
   if ($index < @list.elems)
   {
      $sum = @list[$index] + sumRec(@list,$index+1);
   }
   return $sum;
}

my @list = 1,2,3,4;

say sumFor(@list);
say sumWhile(@list);
say sumRec(@list);

You may already know the following Perl 6 tidbits, but for others reading along:

The ordinary OO way to express the sum of a list of numbers in a variable list is list.sum;
The ordinary functional way to express the same thing is sum list;
A less common functional idiom that produces the same result is [+] list which is a reduction.

Imo your code is fine. That said:

Parentheses are frequently optional

Larry often pipes up about what he calls "superstitious parens". More generally I think there's a rough consensus among Perl 6 folk that readability for most folk is best served by omitting optional parentheses when the meaning remains clear without them. This is almost always true around conditional expressions. I generally omit them around argument lists too. If I were writing the code you've written I'd likely have dropped seven pairs of "superstitious parens" thus:

sub sumFor(@list)
{
   my $sum = 0;
   for @list
   {
      $sum += $_;
   }
   return $sum;
}

sub sumWhile(@list)
{
   my $sum = 0;
   my $index = 0;
   while $index < @list.elems
   {
      $sum += @list[$index++];
   }
   return $sum;
}

sub sumRec(@list, $index = 0)
{
   my $sum = 0;
   if $index < @list.elems
   {
      $sum = @list[$index] + sumRec @list,$index+1;
   }
   return $sum;
}

my @list = 1,2,3,4;

say sumFor @list;
say sumWhile @list;
say sumRec @list;

Sigils are frequently optional

I don't know of any emerging consensus about use of sigil'd variables vs non-sigil'd variables but you can slash sigils like this:

sub sumRec(\list, \index = 0)
{
   my $sum = 0;
   if index < list.elems
   {
      $sum = list[index] + sumRec(list,index+1);
   }
   return $sum;
}

Stronger typing

Most built in operations accept arguments of a wide range of types and automatically coerce them to fit the operation. This highly generic approach is considered a strength. Thus, for example:

say sum '21', '21'; # 42

This genericity is the default in Perl 6 code. But sometimes you may prefer to explicitly specify types. Thus, perhaps:

subset NumericList of List where .all ~~ Numeric;

sub sumFor(NumericList \list )
{
   my $sum = 0;
   for list
   {
      $sum += $_;
   }
   return $sum;
}

my \list = 1,2,3,4,'a';
say sumFor list; # "Constraint type check failed..."


Using Dalli to connect to memcached I always seem to struggle refactoring my code. I can look at any other code and know exactly what is going on, but when it comes to cleaning up my code, I get writers block.

The following code works, but I know if can be done much nicer, and with few lines of code. I just wanted to wrap a memcache client to use one server for testing and another for dev/prod or just fetch the value if it cannot connect to the server.

Any tips on refactoring, etc. are much appreciated.

require 'dalli'
class Cache
    def self.fetch(key, ttl, &block)
        if memcache
            memcache.fetch(key, ttl, &block)
        else
            block.call
        end
    end

    def self.memcache
        begin
        if(ENV['RACK_ENV'] == :production or ENV['RACK_ENV'] == :development)
            @memcache ||= Dalli::Client.new('cache.amazonaws.com:11211')
        else
            @memcache ||= Dalli::Client.new('localhost:11211')
        end
        rescue Exception => e
            false
        end
    end
end

This DRY's the code in self.memcache and simply uses a ternary operator for self.fetch.

require 'dalli'
class Cache
  def self.fetch(key, ttl, &block)
    memcache ? memcache.fetch(key, ttl, &block) : block.call
  end

  def self.memcache
    @memcache ||= Dalli::Client.new((ENV['RACK_ENV'] == :production or ENV['RACK_ENV'] == :development) ?
                                    'cache.amazonaws.com:11211' :
                                    'localhost:11211')
  rescue Exception
    false
  end
end


10-faced dice-rolling game My code is for a 10-faced dice-rolling game. There are 2 players who start off with 50 points, then they both roll a dice and get a random score between 1-10. The player with the highest roll gets the difference between the rolls deducted from their score (50 points), but the loser gets the difference between the rolls added to their score. To win the game you must reach the score 0, or below.

#Imported to help flow, and random to simulate dice rolls

print("Welcome to the dice rolling game.")
#Printed to make it more friendly to the user :)
time.sleep(1)

playernames=[]
#Add player's names to a list
playernames.append(input("\nWhat is player 1's name?"))#.append is used to add multiple names to list
playernames.append(input("\nWhat is player 2's name?"))
time.sleep(1)
#Prints players names from the list

print("\nPlayer 1:",playernames[0])
print("Player 2:",playernames[1])
input("\nPress enter to begin: ")

dicelist=[0,0]

dicelist[0]=random.randint(1,10)
dicelist[1]=random.randint(1,10)

for i in range(0,2):
    print(playernames[i],"rolls a",dicelist[i])
diceDifference=abs(dicelist[0]-dicelist[1])

score0=20
score1=20
while True:
    if dicelist[0]>dicelist[1]:
            print("\nPlayer 1 wins")
            time.sleep(1)
            print("\nPlayer 2 loses",diceDifference,"points")
            print("Player 2 gains",diceDifference,"points")

            print("player 1:",score0-diceDifference)
            print("player 2:",score1+diceDifference)
score0==0
exit

elif dicelist[1]>dicelist[2]:
print("\nPlayer 2 wins")
time.sleep(1)
print("\nPlayer 2 loses",diceDifference,"points")
print("\nPlayer 1 gains",diceDifference,"points")
print("player 1:",score0+diceDifference)
print("player 2:",score1-diceDifference)
score1==0
exit

else:
print("It's a draw")
time.sleep(1)
print("No change in score")

print("The score is: ","\nPlayer 1:",score0,"\nPlayer 2:",score1)
time.sleep(1)

You have quite a lot of duplication in your code - everything is written out twice, once for each player. This means that you have to change everything in two places if you want to alter the logic, and that adding more players is a huge pain.

Instead, I would suggest the use of lists to hold multiple items, allowing you to have an arbitrary number of players (you start this with the playernames and dicelist, then seem to give up!)

You should also factor out the "magic numbers" like the number of players, number of faces on the die and the starting score. For example:

import random

# Configuration
PLAYERS = 2  # could be another input at the start
FACES = 10
START_SCORE = 20  # or 50?

# Initialisation
names = [input("\nWhat is player {}'s name?".format(x+1))
         for x in range(PLAYERS)]
scores = [START_SCORE for _ in range(PLAYERS)]

# Main game loop
while all(score > 0 for score in scores):
    print()

    # Calculate rolls
    rolls = [random.randint(1, FACES) for _ in range(PLAYERS)]
    for name, roll in zip(names, rolls):
        print("{} rolled {}".format(name, roll))

    # Determine winning roll
    winning_roll = max(rolls)
    diffs = [winning_roll - roll for roll in rolls]

    # Update scores
    for index, name in enumerate(names):
        scores[index] += diffs[index]
        if diffs[index] == 0:
            print("{} won!".format(name))
            scores[index] -= sum(diffs)

    # Report progress
    for name, score in zip(names, scores):
        print("{} now has {} points".format(name, score))

# Who won?
print()
winning_score = min(scores)
for name, score in zip(names, scores):
    if score == winning_score:
        print("{} is the winner!".format(name))

Note the use of zip, enumerate and list comprehensions to deal effectively with the various lists.

The rules have been adapted slightly to accommodate multiple players - those with the highest score get the sum of all differences subtracted from their score, whereas the others get only their difference added. This is the same for two players, but you could tweak this logic according to how the game should work.

One significant improvement over the current structure would be to implement as a set of short, self-contained functions rather than one long script.


cat program in Prolog In order to learn Prolog, I have implemented the cat command in Prolog. I want to know if the code is idiomatic and what could be improved.

File args.pl:

:- module(args, [withFilesOrUserInput/2]).

withFilesOrUserInput(StreamFunction, []) :-
    call(StreamFunction, user_input).

withFilesOrUserInput(StreamFunction, [Filename]) :-
    withFile(StreamFunction, Filename).

withFilesOrUserInput(StreamFunction, [Head|Tail]) :-
    withFile(StreamFunction, Head),
    withFilesOrUserInput(StreamFunction, Tail).

withFile(StreamFunction, Filename) :-
    open(Filename, read, StreamIn),
    call(StreamFunction, StreamIn),
    close(StreamIn).

File cat.pl:

:- use_module(args).

main(Argv) :-
    prompt(_, ''),
    withFilesOrUserInput(catStream, Argv).

catStream(Stream) :-
    copy_stream_data(Stream, user_output),
    flush_output(user_output).

Note: I'm using SWI-Prolog.

+1, good question.

The Prolog convention is to use underscores for readability. Why? because_it_is_easy_to_read_even_long_names_with_underscores, butItIsExtremelyHardToReadEvenShorterNamesWithMixedCaps!

A good naming convention is to use one noun per argument, declaratively describing what the argument stands for.

In SWI-Prolog, check out library(pio): The pure way to do what you want is to use a DCG to describe a list, and then to use phrase_from_file/2 to apply the DCG to a file.

The advantage is clear: You can then readily test your predicates on the toplevel alone, without even requiring a file, just by stating the input as a regular Prolog term.

This helps a lot also when writing test cases.

EDIT: I give you one example how DCGs can help you here. It is not yet completely pure, because this DCG contains output itself. However, it is much simpler than your code, and you can test this predicate without even needing a file, and then transparently apply the same code to a file too:

:- use_module(library(pio)).
:- set_prolog_flag(double_quotes, codes).

cat --> [].
cat --> [C], { put_char(C) }, cat.

This DCG describes a list of character codes, and outputs each code.

Sample use:

?- phrase(cat, "test").
test
true.

Now, with phrase_from_file/2 from Ulrich Neumerkel's library(pio), we can transparently apply the same DCG to a file too:

?- once(phrase_from_file(cat, 'cat.pl')).

With output:

:- use_module(library(pio)).
:- set_prolog_flag(double_quotes, codes).

cat --> [].
cat --> [C], { put_char(C) }, cat.

i.e., the same program as above, which I had saved it cat.pl.

I am using once/1 to commit to the first solution found (there is no further solution, but a choice-point left).


Matryoshka Doll Recursion I was tasked with writing a Matryoshka doll program that manages the following:

howManyDolls : returns an integer based on how many dolls are inside the stack
howManyWearingBabushkas : returns an integer based on how many dolls are wearing a Babushka. The boolean variable babushka determines this.
totalWeight : returns a double based on the weight of all the dolls in the stack

I would appreciate feedback on the recursion part of the code, if it's the most efficient/proper way to use recursion in this context. I am very new to recursion, so I want to make sure I am doing the best I can going forward.

public class Matryoshka {

    private String name;
    private double weight;
    private boolean babushka;

    private Matryoshka innerDoll;

    public Matryoshka(String name, double weight, boolean babushka) {
        this.name = name;
        this.weight = weight;
        this.babushka = babushka;

        this.innerDoll = null;
    }

    public Matryoshka(String name, double weight, boolean babushka, Matryoshka doll) {
        this.name = name;
        this.weight = weight;
        this.babushka = babushka;

        this.innerDoll = doll;
    }

    public String getName() { return this.name; }
    public double getWeight() { return this.weight; }
    public boolean getBabushka() { return this.babushka; }

    public boolean hasInnerDoll() {
        return this.innerDoll != null;
    }

    public Matryoshka getInnerDoll() {
        return this.innerDoll;
    }

    public int howManyDolls() {
        if(this.innerDoll == null) { return 1; }
        return 1 + this.innerDoll.howManyDolls();
    }

    public int howManyWearingBabushkas() {
        if(!this.hasInnerDoll()) { return 0; }
        if(!this.getBabushka()) { return 0 + this.getInnerDoll().howManyWearingBabushkas(); }
        return 1 + this.getInnerDoll().howManyWearingBabushkas();
    }

    public double totalWeight() {
        if(!this.hasInnerDoll()) { return this.getWeight(); }
        return this.getWeight() + this.getInnerDoll().totalWeight();
    }

}

Naming

Field babushka should be named wearingBabushka, since that is what the field describes. The method accessing it becomes isWearingBabushka(). For some reason Java-people like exceptions in naming standards and are adamant that it's vital to have a non-standard getter name for boolean typed methods (yes I'm bitter about this, no need to go into it any deeper).

Final modifiers

The fields should be final, as they are not meant to be changed. Non-final fields always increase the cognitive load on the reader as they have to figure out where the fields are modified.

Constructors vs. static factory methods

In this application it could be useful to instantiate the objects with static factory methods.

public abstract class Matryoshka {

    public static Matryoshka of(String name, ...) {
        return new RootMatryoshka(name, ...);
    }

    public static Matryoshka of(String name, ..., Matryoshka innerMatryoshka) {
        Objects.requireNonNull(innerMatryoshka);
        return new OuterMatryoshka(name, ..., innerMatryoshka);
    }
}

Static factory methods allow you to return a different implementations when needed. The root matryoshka would return static values from the methods that calculate weight etc. The outer matryoshkas would simply perform recursion and addition with no need for null checks (as the factory method prevents null values). There are rules on how classe that use static factory methods should be written, I won't replicate them here.

But that's pretty much a matter of taste. The current implementation is just fine too.

Bugs

If the root matryoshka wears a babushka, the calculation returns an incorrect answer.

Style

I find the unnecessary use of this distracting. In my opinion it should be used only when there is a naming conflict. When done so, the number of references to this can be used as a metric for bad naming or problematic structure.

Tail recursion

Since you asked about efficiency, I have to talk about tail recursion. But be aware that this all is total and complete premature optimization. Each of the recursive methods could be replaced with a loop, which would eliminate the need for populating the stack on each recursion:

public int howManyDolls() {
    int dollCount = 0;

    Matryoshka currentDoll = this;
    while (currentDoll != null) {
        dollCount++;
        currentDoll = getInnerDoll();
    }
    return count;
}

It probably won't affect running time, but at least you're not limited by the stack size. You can have millions of matryoshkas! But you will fail the recursion task, since now this has none.


A method that calculates win streaks Right now, I have the following:

A win_streak column on the User table.
This method in game.rb

I'm interpreting win_streak as follows:

The number if the number games in the streak
The value (positive or negative) specifies whether those games were wins (positive) or losses (negative)

game.rb:

def adjust_streak
  u = self.user
  case self.result
    when 'Win'
      u.win_streak > 0 ? u.win_streak += 1 : u.win_streak = 1
    when 'Loss'
      u.win_streak > 0 ? u.win_streak = -1 : u.win_streak -= 1
    end
  u.save
end

I'm looking for a cleaner, and more succinct way to do this (e.g. keep track of win/loss streaks).

You can use Array#min and Array#max to calculate the win/lose streak;
You don't need to use self on getters;
And you can use user.update instead of assigning and calling .save;
I would also rename the win_streak column to streak;

def adjust_streak
  streak = case result
           when 'Win'  then [user.streak, 0].max + 1
           when 'Loss' then [user.streak, 0].min - 1
           end

  user.update streak: streak
end


Rock-Paper-Scissors with the revealing module pattern In my ongoing effort in learning advanced JavaScript I tried to develop the traditional rock paper scissors game by using the famous revealing module pattern. I'm not comfortable yet with what has to be Private/Public. In my solution, I decided to have a single public function: Game. It uses a lot of private stuff and organizes the global game behavior. Everything else is private and not available to the caller. I'm not sure if it's a correct use of that pattern ?

Anyway I commented my code a lot I hope it will explain my intent correctly. I'm looking for any advices I can get, even if not directly related to the pattern I used.

var roshambo = (function() {

  // We will add +1 for each human victory
  var privateGameDB = 0;
  // We will add +1 for each human or robot victory
  var privateGameCount = 0;

  // Get human input with validation, returns a number between 1 and 3
  function privateGetInput() {
    var choice = prompt('Rock: 1, Paper: 2, Scissors: 3');

    // Input validation
    while (parseInt(choice) <= 0 || parseInt(choice) >= 4 || isNaN(parseInt(choice))) {
      choice = prompt('Rock: 1, Paper: 2, Scissors:3 (your choice vas not valid)');
    }

    return parseInt(choice);
  }

  // Generate robot's play, randomize a number between 1 and 3
  // Also includes a display box alerting the robot's play
  function privateGetRobotPlay() {
    var play = Math.floor(Math.random() * 3) + 1;

    switch (play) {
      case 1:
        alert('Robot played Rock');
        break;
      case 2:
        alert('Robot played Paper');
        break;
      case 3:
        alert('Robot played Scissors');
        break;
    }

    return play;
  }

  // Check who wins the round, by comparing the two numbers.
  // Returns 0 on draw, 1 on loss and 2 on win
  function privateComparePlays(human, robot) {
    var humanPlay = human;
    var robotPlay = robot;

    // Tie
    if (robotPlay == humanPlay) {
      return 0;
    }

    // Robot wins
    if (robotPlay == 1 && humanPlay == 3 || robotPlay == 2 && humanPlay == 1 || robotPlay == 3 && humanPlay == 2) {
      return 1;
    }

    // Defaults to player's victory
    return 2;
  }

  // Update game database and game counter, do nothing if the round is a tie
  function privateUpdateDB(check) {
    switch (check) {
      case 1:
        privateGameCount++;
        break;
      case 2:
        privateGameDB++;
        privateGameCount++;
        break;
    }
  }

  // Display a message depending on round result
  function privateAlertRoundResults(results) {
    switch (results) {
      case 0:
        alert('Draw !');
        break;
      case 1:
        alert('You lose !');
        break;
      case 2:
        alert('You win !');
        break;
    }
  }

  // Display a message with total winrate from 0 to 100% (rounded)
  function privateAlertTotalResults() {
    var results = Math.floor((privateGameDB / privateGameCount) * 100);
    alert('You won ' + results + '% of total games !');
  }

  // Check if the player wants to play again
  function privatePlayAgain() {
    var choice = confirm('Play again ?');
    return choice;
  }

  // Manage the whole game
  function publicGame() {
    // First we check who wins the round
    var humanPlay = privateGetInput();
    var robotPlay = privateGetRobotPlay();
    var roundResults = privateComparePlays(humanPlay, robotPlay);

    // Then display result to the user
    privateAlertRoundResults(roundResults);

    // If it's a tie, we do nothing.
    // If it's not : update database, display total winrate
    if (roundResults != 0) {
      privateUpdateDB(roundResults)
      privateAlertTotalResults();
    }

    // We end by asking the user if he wants to play again
    // If he does, we use a recursion to start the game again
    if (privatePlayAgain() == true) {
      publicGame();
    }
  }

  // The only function available to the user is the whole game
  return {
    play: publicGame
  };

})();

// Init a game
roshambo.play();

I like your question,

I think if you are going to export one function, and then immediately execute it, then you are better served with a self executing query.
You are writing a game, I would use a revealing pattern for the model, the controller, and the view.

View would export

An alert function
An input function

Controller would export a

init or start function
It would have a lot of internal functions calling view and model

Model would export a

Getter/setter for victories
comparePlays function

Always consider if you can replace control structures with data structures:

// Display a message depending on round result
function privateAlertRoundResults(results) {
  var resultsMessages = [ 'Draw !', 'You lose !','You win !'];
  alert( resultsMessages[ results ];
}

instead of

// Display a message depending on round result
function privateAlertRoundResults(results) {
  switch (results) {
    case 0:
      alert('Draw !');
      break;
    case 1:
      alert('You lose !');
      break;
    case 2:
      alert('You win !');
      break;
  }
}

For extra points, consider how you can convert this into a data structure:

    if (robotPlay == 1 && humanPlay == 3 || robotPlay == 2 && humanPlay == 1 || robotPlay == 3 && humanPlay == 2) {

Consider wellnamed variables or constants instead of magic numbers, your code would be so much more readable if you had upfront

var DRAW = 0,
    LOSE = 1,
    WIN  = 2;

and then later

function privateUpdateDB(check) {
  switch (check) {
    case LOSE:
      privateGameCount++;
      break;
    case WIN:
      privateGameDB++;
      privateGameCount++;
      break;
  }
}

of course in this particular case, I would not have gone for a case but an if:

function privateUpdateDB(check) {
  if( check == LOSE ){
      privateGameCount++;
  } else if ( check == WIN ){
      privateGameDB++;
      privateGameCount++;
  }
  //We don't increase privateGameCount for Draws (?)
}

I like your adjusting prompt in case the user provides a bad number
On the whole, prefixing your private functions with private is not a great idea because it interrupts the reading flow. I would not prefix at all, but if you insist on prefixing I would prefix with _, most developers will know what you mean (and frown because they also don't like prefixing ;)