Java converter from Arabic to Roman Numerals I am learning Java and would like to get feedback on the code I wrote.

I have written an implementation of an algorithm (found here) for converting any decimal Arabic number to Roman numeral string. My concerns are:

The code seems too long for some methods.
It is not clear what is going on in the class (unless you already know what the algorithm is doing).
Correct use of OOP
Tight coupling of methods
Are there Java 8 features that I should be using but not using.

I am looking for your input, advice and feedback so that I can get better at writing clean and maintainable code.

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Stream;

import static java.util.stream.Collectors.joining;

public class RomanNumeralsConverter {

  private final Map<Integer, String> BASE_VALUES_MAP =
    new HashMap<Integer, String>() {{
      put (1, "I");
      put (4, "IV");
      put (5, "V");
      put (9, "IX");
      put (10, "X");
      put (40, "XL");
      put (50, "L");
      put (90, "XC");
      put (100, "C");
      put (400, "CD");
      put (500, "D");
      put (900, "CM");
      put (1000, "M");
    }};

  private StringBuilder romanNumeralString;

  public RomanNumeralsConverter () {
    this.romanNumeralString = new StringBuilder();
  }

  public String convert (int arabicNumberToConvert) {
    return romanNumeral(arabicNumberToConvert);
  }

  private String romanNumeral(int arabicNumberToConvert) {
    int nearestBaseValue = findNearestBaseValue(arabicNumberToConvert);
    int numberOfBasesInTheArabicNumber = arabicNumberToConvert / nearestBaseValue;
    int numberRemainingAfterLargestBaseHasBeenDeducted =
      arabicNumberToConvert % nearestBaseValue;

    this.romanNumeralString = buildRomanNumeralString (nearestBaseValue,
      numberOfBasesInTheArabicNumber);
    return numberRemainingAfterLargestBaseHasBeenDeducted != 0 ?
      convert (numberRemainingAfterLargestBaseHasBeenDeducted) :
      this.romanNumeralString.toString();
  }

  private StringBuilder buildRomanNumeralString(int nearestBaseValue,
                                         int numberOfBasesInTheArabicNumber) {
    this.romanNumeralString.append(repeatBaseValue(nearestBaseValue,
      numberOfBasesInTheArabicNumber));
    return this.romanNumeralString;
  }

  private String repeatBaseValue (int nearestBaseValue,
                                  int numberOfBasesInTheArabicNumber) {
    return Stream.generate(() -> BASE_VALUES_MAP.get(nearestBaseValue))
      .limit(numberOfBasesInTheArabicNumber)
      .collect(joining());
  }

  private int findNearestBaseValue(int arabicNumberToConvert) {
    int nearestBaseValue = 0;
    int minimumDifference = Integer.MAX_VALUE;
    if (BASE_VALUES_MAP.get (arabicNumberToConvert) != null) {
      nearestBaseValue = arabicNumberToConvert;
    } else {
      for (Integer key : BASE_VALUES_MAP.keySet ()) {
        int differenceBetweenBaseValueMapKeyAndArabicNumber = (arabicNumberToConvert - key);
        if (differenceBetweenBaseValueMapKeyAndArabicNumber < minimumDifference
          && differenceBetweenBaseValueMapKeyAndArabicNumber > 0) {
          nearestBaseValue = key;
          minimumDifference = differenceBetweenBaseValueMapKeyAndArabicNumber;
        }
      }
    }
    return nearestBaseValue;
  }
}

private final Map<Integer, String> BASE_VALUES_MAP

This is missing static modifier

private StringBuilder romanNumeralString;

I don't think that should be a member, just pass it as argument where necessary. That way you code will be thread-safe, without any additional effort.

private int findNearestBaseValue(int arabicNumberToConvert) {

If you use TreeSet instead of HashSet you could just use ceiling()/floor() instead of manual iteration.

buildRomanNumeralString()

This method looks unnecessary, just inline it.

  Are there Java 8 features that I should be using but not using.

I would say it is the opposite - there is no real point in using Stream in repeatBaseValue(), normal for loop would be fine.


Condensing if statement in C# I have this if statement

if (dt.Month > 3 && dt.Month < 11)
{
    if (hours == 23 || (hours >= 0 && hours <= 6))
    {
        session = String.Empty;
    }
    else if (hours == 7)
    {
        session = String.Empty;
    }
    else if (hours >= 8 && hours <= 11)
    {
        session = String.Empty;
    }
    else if (hours >= 12 && hours <= 15)
    {
        session = String.Empty;
    }
    else if (hours >= 16 && hours <= 20)
    {
        session = String.Empty;
    }
    else if (hours == 22)
    {
        session = String.Empty;
    }
    else
    {
        session = String.Empty;
    }
}
else
{
    if (hours == 22)
    {
        session = String.Empty;
    }
    else if (hours == 23 || (hours >= 0 && hours <= 6))
    {
        session = String.Empty;
    }
    else if (hours == 7)
    {
        session = String.Empty;
    }
    else if (hours >= 8 && hours <= 12)
    {
        session = String.Empty;
    }
    else if (hours >= 13 && hours <= 16)
    {
        session = String.Empty;
    }
    else if (hours >= 17 && hours <= 20)
    {
        session = String.Empty;
    }
    else if (hours == 21)
    {
        session = String.Empty;
    }
    else
    {
        session = String.Empty; // I dont think this one is needed
    }
}

As you can see it's pretty long and nasty.  Is there a way to shrink it?  I was going to use a switch but in C# you can't fall through case statements.

Shouldn't you replace the whole code with session = String.Empty; ?

Let's assumme that this is just a placeholder for actual code. If you handle your different cases in order and if hours is an int, then you can make the logic a bit easier to follow :

if (hours == 23 || (hours >= 0 && hours <= 6))
{
    session = A;
}
else if (hours == 7)
{
    session = B;
}
else if (hours >= 8 && hours <= 11)
{
    session = C;
}
else if (hours >= 12 && hours <= 15)
{
    session = D;
}
else if (hours >= 16 && hours <= 20)
{
    session = E;
}
else if (hours == 22)
{
    session = F;
}
else
{
    session = G;
}

becomes

if (hours < 0 || hours > 23)
{
    session = G;
}
else if (hours <=6)
{
    session = A;
}
else if (hours <= 7)
{
    session = B;
}
else if (hours <= 11)
{
    session = C;
}
else if (hours <= 15)
{
    session = D;
}
else if (hours <= 20)
{
    session = E;
}
else if (hours <= 22)
{
    session = F;
}
else
{
    session = A;
}


Binary Search Implementation in C++ In computer science, binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array.

The code returns true if an element is present in the array else returns false.

Any suggestion in improving the code is welcome.

Binary_Search.h

#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H

bool binary_search(int ar[], int low, int high, int key);

#endif // BINARY_SEARCH_H

Binary_Search.cpp

#include <iostream>
#include "Binary_Search.h"

/* search a key in an array using binary search */
bool binary_search(int ar[], int low, int high, int key)
{
  int mid;

  while ( low <= high )
    {
      // find the middle index
      mid = low + ((high - low) >> 1);

      if ( ar[mid] == key ) // key found
        {
          return true;
        }
      else if ( ar[mid] > key ) // key may be on the left half
        {
          high = mid - 1;
        }
      else if ( ar[mid] < key ) // key may be on the right half
        {
          low = mid + 1;
        }
    }

  // key not found
  return false;
}

int main()
{
  int ar[] = {1, 7, 9, 10, 28, 28, 36, 49, 68, 99};

  for ( int i = 0; i < sizeof(ar) / sizeof(ar[0]); ++i )
    {
      if ( binary_search(ar, 0, sizeof(ar) / sizeof(ar[0]) - 1, ar[i]) )
        {
          std::cout << ar[i] << " is present" << std::endl;
        }
      else
        {
          std::cout << ar[i] << " is not present" << std::endl;
        }
    }

  int ar1[] = {-1, 2, 3, 12, 23, 50, 90, 98, 100};
  for ( int i = 0; i < sizeof(ar1) / sizeof(ar1[0]); ++i )
    {
      if ( binary_search(ar, 0, sizeof(ar) / sizeof(ar[0]) - 1, ar1[i]) )
        {
          std::cout << ar1[i] << " is present" << std::endl;
        }
      else
        {
          std::cout << ar1[i] << " is not present" << std::endl;
        }
    }
  return 0;
}

Interface
Passing an array and then two indexes is a very C style of interface. In C++ it is much more common to pass two iterators. An iterator is a generalized form of pointer.
So rather than:
bool binary_search(int ar[], int low, int high, int key);

I would use:
template<typename I>
bool binary_search(I low, I high, int key);

Also rather than pointing at the first and last elements iterator ranges use a first and one past the last. This makes calculating sizes easier.
Code Review
Don't use >> 1 to represent a divide by 2. The point of high level code is to write it so that it is easy for humans to read. That is not obvious. Also the compiler can do these micro optimizations much better than you. So don't try and confuse it. Just write code in the most readable way possible.
Don't use sizeof(ar) / sizeof(ar[0]) it is so easy to break as array collapse into pointers at the drop of a hat. Use std::size() which works for arrays/containers but will fail to compile for pointers (which is what you want).
But if you switch to using Iterator based interface then you should use std::begin() and std::end().
Style
Your bracing style is uncommon. But not so egregious that I would complain about. Normally brace style is defined by a local style guide. So if you are in a compnany or project just check that.
 // Most common C++ styles
 if ()
 {
     Statement;
 }

 // or
 if () {
     Statement;
 }


Array_Swap function in PHP In PHP/Laravel  I have the following function. Can you please review my approach?

private function array_swap_assoc($key1, $key2, $array)
    {
        $newArray = array();
        foreach ($array as $key => $value) {
            if ($key == $key1) {
                $newArray[$key2] = $array[$key2];
            } elseif ($key == $key2) {
                $newArray[$key1] = $array[$key1];
            } else {
                $newArray[$key] = $value;
            }
        }
        return $newArray;
    }

This will swap the values but is not very robust. If for instance one of the two keys is not defined this will generate notices and might cause sneaky errors further down in the code.

private function array_swap_assoc($key1, $key2, $array)

I don't see why that would be in a class. This is not realated to a specific group of activities. A simple function would do very well, and possibly be better (as in, respect the Single Responsibility Principle), as the class that contains it almost certainly is not a class containing exclusively array functions.

$newArray = array();

Creating a new array is a valid approach, but a different approach could be to pass the array as a reference to swap the values in the original array, unless you specifically need not to modify the original array. This will most of the time not do any noticeable difference, but it is more memory efficient:

private function array_swap_assoc($key1, $key2, &$array) {}

Notice the & in front of the variable. The $array local to this method will change the original one.

foreach ($array as $key => $value) {

It is a bit heavy handed to recreate the whole array. We only want to swap two values. Since we passed it by reference, we could just swap those two values without needing to reassign each and every key.

if ($key == $key1) {
    $newArray[$key2] = $array[$key2];
} elseif ($key == $key2) {
    $newArray[$key1] = $array[$key1];
} else {
    $newArray[$key] = $value;
}

The problem here is that there is no validation that both of the keys exist. We should validate that they do, and throw an exception if they don't.

if (array_key_exists($key1, $array) && array_key_exists($key2, $array) {}

Notice that I use array_key_exists and not isset, because the values could be null (which is a totally valid value) and null values will return false with isset.

So taking into account adding validation and using a passed by reference array, you could make that function more robust like this:

function array_swap_assoc($key1, $key2, &$array)
{
    if (array_key_exists($key1, $array) && array_key_exists($key2, $array)) {
        $value1 = $array[$key1];
        $value2 = $array[$key2];
        $array[$key1] = $value2;
        $array[$key2] = $value1;
    } else {
        throw new InvalidKeys;
    }
}

class InvalidKeys extends \Exception {}

array_swap_assoc('first', 'second', $array);
// no need to use the void return, the original array is modified


C++ std::vector with always valid iterator/pointer/index/key Motivation: Have std::vector<std::unique_ptr<T>> accessibility at std::vector<T> speed.

std::vector have one inconvenience - you can't store pointers nor indexes to elements if the vector grows/alters.

To overcome this problem we usually use vector of pointers / deque (if only grow) / list / etc. Having our elements in heap have significant overhead on creation, traverse, and per element access.

To store "pointer" (or key) to element in vector I have back array of indices.

Condensed version:

struct Key{
   int index;  // index of key_indices
};

struct Element {
    int key_index;   // never changes
    Value value;
};
std::vector<Element> data;       // usual continious vector, no magic here
std::vector<int> key_indices;    // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;

void emplace_back(){
   // if have no free_indices
   data.emplace_back();
   key_indices.emplace_back(data.size() - 1);
   data.back().key_index = key_indices.size() - 1;
}

Key get_key(std::vector<Element>::iterator iter){
    return {iter->key_index};
}

Value& operator[](Key key){
   return data[key_indices[key.index]].value;
}

Value& operator[](int index){
   return data[index].value;
}

void erase(std::vector<Element>::iterator iter){
    free_indices.push_back(iter->key_index);
    update_indices(iter + 1, data.end(), -1);
    data.erase(iter);
}
// same with insert, emplace_front, etc.

template<class iter>
void update_indices(iter from, iter to, int shift) {
    for (auto it = from; it != to; ++it)
    {
        key_indices[it->key_index] += shift;
    }
}

And used like:

KeyContainer<Data> list;

list.emplace_back().back().x = 100;
list.emplace_back().back().x = 200;

auto key = list.get_key(list.end()-1);

list.erase(list.begin());               // all indices invalidated
std::cout << list[key].x << std::endl;  // key still valid

In other words Key - is array index that always points to the same element, just like pointer to std::vector<std::unique_ptr<T>> element.

It is approximately 6-10 times faster than std::vector<std::unique_ptr<T>>/list on creation, 3-4 times faster than deque(at least with VS2015/clang). Same speed as vector when traverse/index access. And approx 10% slower with key access. I tried to use pointers instead of indices, but didn't see a difference.

Is there some ready library solution for container like this (vector with indices back-array (or ptr back-array))?

Full code as is (just a concept proof)

Quick review (in anticipation of more code).

The main issue I have with the code is that is not encapsulate in a class.

std::vector<Element> data;       // usual continious vector, no magic here
std::vector<int> key_indices;    // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;

These are basically global variables and anybody can access an mutate them (not just maliciously but accidently). C++ has the ability to encapsulate all the parts of a class and protect it from accidental misuse by only allowing certain functions (methods) to access the raw underlying data.

class MultiIndexToElement
{
    private:
        std::vector<Element> data;         // usual continious vector, no magic here
        std::vector<int>     key_indices;  // point to data[]. these values changes when erase/insert to data
        std::vector<int>     free_indices;
    public:
        void emplace_back();
        Key get_key(std::vector<Element>::iterator iter);

        Value& operator[](Key key);
        Value& operator[](int index);

        void erase(std::vector<Element>::iterator iter);

     private:
        template<class iter>
        void update_indices(iter from, iter to, int shift);
};

Now that we can see the interface clearly there are a couple of things you should watch for.

Const correctness.

A method that does not change the state of the object should be marked const. This tells the compiler that calling this method does not change the object.

      Key get_key(std::vector<Element>::iterator iter) const;
                                                  //   ^^^^^

This is important because objects get passed to functions by const reference a lot in C++ to avoid the cost of copying the object.

Element Access

Usually containers allow tow forms of element accesses. Mutating access and const accesses.

        Value&       operator[](int index);       // This allows mutating access.
        Value const& operator[](int index) const; // This allows const accesses.

Emplace Back.

Usually emplace back (a new form of push back). Creates the Element in place using one of Elements constructors. Your version only allows for Element to have zero parameter constructor.

It is usually written like this:

 template<Args... args>
 void emplace_back(Args&& args...) {
     data.emplace_back(std::forward<Args>(args)...);     // pass arguments to constructor
     .... /* Other stuff you need */
 }

The Args... part is a new part of C++14 so you will need to tell your compiler to use the newer version of the standard (that's not a default yet). But usually this means adding -std=c++14 to the command line.

Templatization

Your code does not allow for easy templatization. In fact you don't define Value in the code sample above. This is more easily solved using templates around a class.

template<typename Value>
class MultiIndexToElement
{
     /* STUFF */
};


Read and write data to/from Serial Port in C# I am building a console application which will be scheduled in Task Scheduler of Windows to run my code every day at a set hour. Summing up, this application will read and write through serial port. When I send something to the Arduino, I need to receive something from it to finish up what I've sent and execute the command.

In other words, I will send something so see if the door is opened, if it is the application will run a code to close it. If the door is already closed I will send a bunch of characters to be displayed into the Arduino Led Display.

So I've developed a code but I am not sure if it's totally correct, if possible help me improve it. There is any changes I could make?

static void Main(string[] args)
{
    SerialPort comport = new SerialPort("COM1", 9600, Parity.None, 8, StopBits.One);
    comport.Open();

    string start = "?";
    string carriageReturn = "\r";
    string text = string.Empty;

    string mensage = "@" + "r" + "\r";
    string mensage2 = "@" + "{" + texto + "\r";

        try
            {
                while (true)
                {
                    //Send to the Arduino
                    comport.Write(start + "*" + carriageReturn);

                    //If the serial port have bytes to read
                    if (comport.BytesToRead > 0)
                    {
                        //Buffer with data
                        byte[] data = HexStringToByteArray(mensage);

                        //Handle data
                        comport.Read(data, 0, data.Length);

                        //Send again to execute the the command
                        comport.Write(start + "*" + carriageReturn);
                    }

                    if (comport.BytesToRead > 0)
                    {
                        comport.Write(start + "*" + carriageReturn);

                        byte[] data2 = HexStringToByteArray(mensage2);

                        comport.Read(data2, 0, data2.Length);

                        comport.Write(text);
                    }
                    comport.Close();
                }
            }

        catch(Exception ex)
        {
        }
}

private static byte[] HexStringToByteArray(string s)
{
    s = s.Replace(" ", "");
    byte[] buffer = new byte[s.Length / 2];

    for (int i = 0; i < s.Length; i += 2)
        buffer[i / 2] = (byte)Convert.ToByte(s.Substring(i, 2), 16);
        return buffer;
}

There are a number of strange things going on here...

First, you have this:

//Buffer with data
byte[] data = HexStringToByteArray(mensage);

//Handle data
comport.Read(data, 0, data.Length);

The first line takes the mensage (message?) and turns it into a byte array, but then you immediately overwrite the data by reading into the same buffer. In essence, you are using HexStringToByteArray simply to create a new array of some length (3 bytes?).

Based on how you are using HexStringToByteArray, it certainly does not take a hex string and turn it into a byte array. mensage and mensage2 contain things other than valid hex characters. Maybe something more descriptive like StringToByteArray or StringToHexByteArray would be better. It does look like you are trying to convert a "hex" string input to byte data, but given the inputs I can't see how you can run this and not get an exception. The other problem with this method is that it assumes you have an input string length divisible by 2, and you are not checking that (nor are your values passed in adhering to that).

Since you are not doing anything with the data and data2 arrays, you are basically using them to flush some data out of the read buffer. I would have to assume that the code you posted is not complete, otherwise you could do something like SerialPort.Flush() instead.

Now, lets look at your variables:

string start = "?";
string carriageReturn = "\r";
string text = string.Empty;

string mensage = "@" + "r" + "\r";
string mensage2 = "@" + "{" + texto + "\r";

I would advise against using the carriageReturn and either call it something like messageDelimiter or just don't use it. It would be akin to defining something like:

int zero = 0;

Zero will always equal zero, so you shouldn't have variables for them. The name text doesn't really help here, you should give it a descriptive name like emptyMessage since it doesn't look like it ever changes. mensage and mensage2 are also not descriptive (or spelled correctly), maybe something like doorOpenQuery and doorCloseCommand. (And in addition, since texto isn't defined, I don't see this even compiling...)

The last problem I see is that you have an un-throttled while(true) loop in your program with no exit conditions other than something throwing an exception. How many times do you want to run this loop? You shouldn't have an unbounded while, you are going to have a not-responding program if you let it run for about 10 seconds.

From what I see I don't believe that this is functioning code. Have you run this through the debugger? If you have functionality problems this probably isn't the StackExchange site for that.


Selecting a specific row with a desired value I am trying to get a row if it has the desired specific value, otherwise get the first or default:

dr =
   (from avTable in DAL.DataStore.DSet.Tables["Values1"].AsEnumerable()
    join pavTable in DAL.DataStore.DSet.Tables["Values2"].AsEnumerable()
        on avTable.Field<int>("PK") equals pavTable.Field<int>("FK_Value")
    where
          pavTable.Field<int>("FKI_ProductAttribute") == Value2 &&
          avTable.Field<string>("Name") == "Specific Value"
    select avTable).FirstOrDefault() ??
    (from avTable in DAL.DataStore.DSet.Tables["Values1"].AsEnumerable()
     join pavTable in DAL.DataStore.DSet.Tables["Values2"].AsEnumerable()
     on avTable.Field<int>("PK") equals pavTable.Field<int>("FK_Value")
     where pavTable.Field<int>("FKI_ProductAttribute") == Value2
     select avTable).FirstOrDefault();

This smells. Is there a better way to do this?

I want to do something like this:

var dt =
   (from avTable in DAL.DataStore.DSet.Tables["Values1"].AsEnumerable()
    join pavTable in DAL.DataStore.DSet.Tables["Values2"].AsEnumerable()
        on avTable.Field<int>("PK") equals pavTable.Field<int>("FK_Value")
    where
          pavTable.Field<int>("FKI_ProductAttribute") == Value2 &&
          avTable.Field<string>("Name") == "Specific Value"
    select avTable)

DataRow dr = dt.Select("PK = Specified value");
If(dr==null) dr = dt.FirstOrDefault();

and then do a select based on a specified value. If that is null, then grab the first or default. This seems to be more DRY, but is it more or less efficient?. Also, I have a hard time doing a select on the dt based on the specific value (lack of Linq expertise and Google prowess to find the answer I am looking for).

Will this work?

var dr= (from avTable in DAL.DataStore.DSet.Tables["Values1"].AsEnumerable()
         join pavTable in DAL.DataStore.DSet.Tables["Values2"].AsEnumerable()
             on avTable.Field<int>("PK") equals pavTable.Field<int>("FK_Value");
         where
             (pavTable.Field<int>("FKI_ProductAttribute") == Value2 &&
              avTable.Field<string>("Name") == "Specific Value") ||
              pavTable.Field<int>("FKI_ProductAttribute") == Value2
         select avTable)
        .FirstOrDefault();

I don't really have a way to test this, but I believe if the first part of the where clause criteria is met, the part after the || is skipped. If the first part returns no record then the second part is evaluated and will return a result ...or null.


Shortest path algorithm I have a code that does applies Dijkstra's algorithm for an adjacency list.
The data are taken from a file. In the file, the first line contains the number of vertices and edges, and the remaining lines contain three elements each (the first 2 are the numbers of the vertices and 3rd are the weight of the edges).
The output is written to another file. The main problem is long reading (adding to the list) of elements - 8 seconds versus 2 according to the rules of the correct test. In a file for reading, there are 400,000 such lines. How can I speed up the reading?
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
using namespace std;
# define INF 0x3f3f3f3f
typedef pair<int, int> iPair;

class Graph
{
    int V;
    list< pair<int, int> >* adj;
public:
    Graph(int V);
    void addEdge(int u, int v, int w);
    void shortestPath(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair>[V];
}

void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}

void Graph::shortestPath(int src)
{
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
    vector<int> dist(V, INF);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    ofstream file1("C:\\Tests\\123.txt");
    for (int i = 0; i < V; ++i)
        cout << dist[i] << " ";
    file1.close();
}

int main()
{
    ifstream file("C:\\Tests\\21");
    int number_of_veretexes, edges;
    file >> number_of_veretexes >> edges;
    Graph g(number_of_veretexes);
    int _first_, _second_, _third_;
    for (int i = 0; i < edges; i++) {
        file >> _first_ >> _second_ >> _third_;
        g.addEdge( _first_ - 1, _second_ - 1, _third_);
    }
    g.shortestPath(0);
    file.close();
}

Avoid using namespace std
Avoid using namespace std, it is considered bad practice. It saves only a little bit of typing, but you can run into issues if names of local classes and variables clash with those defined in the standard library.
Use INT_MAX instead of INF
Don't #define INF to some arbitrary value, just set it to exactly the largest possible value an int can have. This is already defined as INT_MAX in <climits>.
Create a struct Edge
Using a std::pair<int, int> is convenient, especially since you can sort them, but it has some drawbacks. It is unclear from just looking at the definition of this type whether the first element is the node number and the second the weight, or the other way around. You actually use both conventions in your code: the adjacency list has the vertex number first, whereas the priority queue has the vertex number second. Create a proper struct to remove the ambiguity and increase type safety. Also, since an edge is a property of a graph, define struct Edge inside class Graph, like so:
class Graph {
    struct Edge {
        int vertex;
        int weight;
    };

    std::list<Edge>* adj;
    ...
};

Instead of calling adj[u].push_back(std::make_pair(v, w)), you should now write:
adj[u].push_back({v, w});

For the priority queue, you also want to create a separate struct for the elements. Since only Graph::shortestPath() uses this, you can define this inside that function. To make it sortable, define an operator<() in this struct, like so:
void Graph::shortestPath(int src) {
    struct VertexDistance {
         int vertex;
         int distance;
         bool operator<(const VertexDistance &other) {
             if (distance != other.distance)
                 return distance > other.distance;
             else
                 return vertex > other.vertex;
         }
    };

    std::priority_queue<VertexDistance> pq;
    ...
}

Avoid manual memory allocation
It is a bit strange to see you use STL containers like std::list and std::vector and std::priority_queue, but then use new to allocate the array adj. Why not use a std::vector for that too? For example, like so:
std::vector<std::list<Edge>> adj;

This avoids the need for new, and fixes the memory leak you have because you never call delete. It also allows you to remove the member variable V, since the vector already keeps track of its size.
You can make it a bit easier to read by creating an alias for the list of edges:
using AdjacencyList = std::list<Edge>;
std::vector<AdjacencyList> adj;

Use std::vector instead of std::list
std::vector and std::list can both store a list of elements, but they have different tradeoffs in performance, memory requirements, and other aspects. In your code, you only ever add elements to the back of an adjacency list, you never insert or remove elements from the middle. In that case, a std::vector is a much more efficient data structure, so I would just write:
using AdjacencyList = std::vector<Edge>;
std::vector<AdjacencyList> adj;

Use range-based for loops
Unless you cannot use any features from C++11 or later, I strongly recommend you start using range-based for-loops. They save typing, make the code more readable and reduce the possibility of errors. For example, when iterating over an adjacency list in Graph::shortestPath(), you can write:
for (auto &edge: adj[u]) {
     int v = edge.vertex;
     int weight = edge.weight;
     ...
}

The same goes for printing the contents of dist:
for (auto &distance: dist)
    file << distance << " ";

Check for errors when reading and writing files
A lot of things can go wrong when reading from and writing to files: the files might not exist, be corrupted, you might not have permissions to read and/or write, the disk might get full halfway writing a file, and so on. You should therefore ensure that you have completely read and written files without errors.
You don't have to check every I/O operation; the file objects will remember if an error condition has occured in the past. So the simplest way to get proper error checking is to do this after reading or writing the whole file. This can be done by checking the I/O state bits. In your case, just checking that good() returns true should be sufficient, like so for the input file:
int main() {
    ifstream file("...");
    ...
    if (!file.good()) {
        std::cerr << "An error occured while reading the input!\n";
        return 1;
    }

    g.shortestPath(0);
}

And like so for the output file:
void Graph::shortestPath(int src) {
    ...
    ofstream file("...");
    ...
    file.close();
    if (!file.good()) {
        std::cerr << "An error occured while writing the output!\n";
        // TODO: ensure the error propagates to main, or call exit(1)
    }
}

It is imporant to call close() first here, since the act of closing the stream will ensure its output buffer is completely flushed.
When you detect an error, it is important that you don't continue using any bad data you might have gotten, that you print a helpful error message to std::cerr, and that if your program returns a non-zero exit code. The latter is important in case your program is called from a script for example, so the script won't continue with bogus data.
Move file output out of Graph::shortestPath()
Following the principle of separation of concerns, you should remove the file output functionality from shortestPath(). Instead, make that function return the shortest path, and let the caller write it to disk. This can simply be done like so:
std::vector<int> Graph::shortestPath(int src)
{
    ...
    while (...) {
        ...
    }

    return dist;
}

int main()
{
    ...
    auto path = g.shortestPath(0);
    std::ofstream file1(...);

    for (auto &distance: path)
        file1 << distance < " ";

    file1.close();

    if (!file1.good()) {
        std::cerr << "An error occured while writing the output!\n";
        return 1;
    }
}

You might also consider moving the file input and output into separate functions, so that main() is simplified to something that looks like this:
int main() {
    auto graph = readGraph("C:\\Tests\\21");
    auto path = graph.shortestPath(0);
    writePath(path, "C:\\Tests\123.txt");
}


Extract specified field value from filename using positional indexing I have some filenames, and they each have data contained in them at specific locations in the string. I want a function that returns the value of the data specified by field. The doctest illustrates.

I'd like a nicer, easier-to-understand way to do this.

If possible, but secondarily, I'd like to be able to give the data in different types, according to which field they are, rather than just the string value.

def get_field_posn_list(field):
    """List containing field position indices in filename"""
    return({'place': [-11],
            'year': range(-10, -7),
            'session': [-6]}[field])

def get_field_str(fn, field):
    """Get the string value of field stored in string fn
    >>> get_field_str('/path/to/file/Z998-5.asdf', 'session')
    '5'
    """
    val = ''.join([fn[i] for i in get_field_posn_list(field)])
    return val

This task is nearly equivalent to another recent question.  My advice is that string analysis is usually best done using regular expressions.

import os
import re

def get_field_str(file_path, field):
    """
    Get the string value of field stored in file_path

    >>> get_field_str('/path/to/file/Z998-5.asdf', 'session')
    '5'
    """
    pattern = re.compile('(?P<place>.)(?P<year>.{3})-(?P<session>.)\.')
    return pattern.search(os.path.basename(file_path)).group(field)

The regex can validate the filename as it works.  Feel free to adjust it to match your expectations.


Mergesort implementation in Clojure (defn merge [pred left right]
    (loop [v [] l left r right]   ; v is a vector, so conj will append to the end
        (if (and (seq l) (seq r)) ; if both left and right are not empty
            (if (pred (first l) (first r))
                (recur (conj v (first l)) (rest l) r)
                (recur (conj v (first r)) l        (rest r)))
            (concat v l r))))     ; One of l and r is empty, so concatenate what is already sorted

(defn mergesort [pred v]
    (let [
        n (count v)
        h1 (int (/ n 2))        ; floor(n/2)
        h2 (int (/ (inc n) 2))] ; ceil(n/2)
        (if (< n 2)
            v
            (merge pred
                (mergesort pred (take h1 v))          ; take the first half of elements
                (mergesort pred (take-last h2 v)))))) ; take the last half of elements

I'd like critics on how to turn this mergesort algorithm more Clojuric, if there are any Clojure API I could use to simplify it and other issues.

Specially, I've used a vector to store elements within merge, because otherwise the conj would append to its front, thus producing a reversed sequence. Also, is take and take-last the way to go to catch two halfs of a seq?

The following test code shows it works for vectors, lists and maps. Anything else I should consider?

(def v [3 -2 4 5 -3 0 7 -8 1 -1 2])
(def m [{:x 1 :y 2} {:x 0 :y 3} {:x 2 :y 1}])
(def s (seq v))
(mergesort < v)
;=> (-8 -3 -2 -1 0 1 2 3 4 5 7)
(mergesort > v)
;=> (7 5 4 3 2 1 0 -1 -2 -3 -8)
(mergesort #(< (java.lang.Math/abs %1) (java.lang.Math/abs %2)) v)
;=> (0 -1 1 2 -2 -3 3 4 5 7 -8)
(mergesort #(< (:x %1) (:x %2)) m)
;=> ({:x 0, :y 3} {:x 1, :y 2} {:x 2, :y 1})
(mergesort > s)
;=> (7 5 4 3 2 1 0 -1 -2 -3 -8)

A few points, though I'm not a Clojure expert:

Indentation. You use four-space indentation, but two-space indentation is more common for Lisp in general and also generally preferred for Clojure. (there seems to be a Clojure community style guide)
Instead of take-last, you may want to use drop. Since you're traversing the whole list anyway, you could also just use split-at (though that's basically the same as using both take and drop).


Interactive complete Brainfuck Interpreter This is another Brainfuck interpreter in Python. I personaly think this is better than most of the other once you find online, because it keeps a bracket_map, which makes both [ and ] instant actions. The data array is a simple defaultdict(int), so it is infinite is size in both directions (which  maybe a bad decision?) I am open to all critics and hope that somebody can tell if this is realy as efficient as I think.

from collections import defaultdict
from msvcrt import getch

program = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."

def evaluate(sourcecode):
    bracket_map = {}
    stack = []
    for i, c in enumerate(sourcecode):
        if c == "[":
            stack.append(i)
        elif c == "]":
            s = stack.pop()
            bracket_map[s], bracket_map[i] = i, s
    assert not stack
    del stack
    data = defaultdict(int)
    data_index = 0
    program_index = 0
    while program_index < len(sourcecode):
        c = sourcecode[program_index]
        if c == "+":
            v = data[data_index] + 1
            if v > 255:
                v = 0
            data[data_index] = v
        elif c == "-":
            v = data[data_index] - 1
            if v < 0:
                v = 255
            data[data_index] = v
        elif c == ">":
            data_index += 1
        elif c == "<":
            data_index -= 1
        elif c == ".":
            print(chr(data[data_index]), end="")
        elif c == ",":
            data[data_index] = getch()[0]
        elif c == "[":
            if not data[data_index]:
                program_index = bracket_map[program_index]
        elif c == "]":
            if data[data_index]:
                program_index = bracket_map[program_index]
        program_index += 1

evaluate(program)

(if you are not on windows, you need an alternative for the getch function)

All in all this looks good to me. I would make 2 changes

bracket_map

The code to assemble this map can be more clear in it's own function.

+ and -

v = data[data_index] - 1
if v < 0:
    v = 255
data[data_index] = v

can be easily replaced by

data[data_index] = (data[data_index] - 1) % 256

Same goes for the + operation


Enumerating ancestors in XSLT I've been playing with some genealogical files in XML lately and wanted to create a transform that would list, for each person, the person's name, the count of ancestors, and the list of ancestors.  Here's what I came up with, but I'd like to see if there's a better way to do this.
<?xml version="1.0" encoding="iso-8859-1"?>
<xsl:stylesheet version="1.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema"
>
<xsl:output method="text"/>

<xsl:template match="/people">
    <xsl:apply-templates select="person"/>
</xsl:template>

<!-- for each person, print the name and ancestor count -->
<xsl:template match="person">
    <xsl:value-of select="@name"/>
    <xsl:text>(</xsl:text>
    <xsl:apply-templates select="." mode="count-kin"/>
    <xsl:text>): </xsl:text>
    <!-- now name all of the ancestors -->
    <xsl:apply-templates select="." mode="name-kin"/>
    <xsl:text>
</xsl:text>
</xsl:template>

<!-- recursively name the ancestors -->
<xsl:template match="parent" mode="name-kin">
    <xsl:value-of select="concat(@name,' ')"/>
    <xsl:variable name="myname" select="@name"/>
    <xsl:apply-templates select="/people/person[@name=$myname]" mode="name-kin"/>
</xsl:template>

<!-- recursively name the ancestors -->
<xsl:template match="person" mode="name-kin">
    <xsl:apply-templates select="parent" mode="name-kin"/>
</xsl:template>

<!-- recursively count the number of ancestors -->
<xsl:template match="parent" mode="count-kin">
    <xsl:variable name="myname" select="@name"/>
    <xsl:variable name="ancestor-count">
    <xsl:apply-templates select="/people/person[@name=$myname]" mode="count-kin"/>
    </xsl:variable>
    <xsl:value-of select="$ancestor-count"/>
</xsl:template>

<!-- recursively count the number of ancestors -->
<xsl:template match="person" mode="count-kin">
    <xsl:choose>
    <!-- only count ancestors if there are any -->
    <xsl:when test="count(parent)">
        <xsl:variable name="ancestor-count">
        <xsl:apply-templates select="parent" mode="count-kin"/>
        </xsl:variable>
        <xsl:value-of select="number($ancestor-count)+count(parent)"/>
    </xsl:when>
    <!-- no parents -->
    <xsl:otherwise>
        <xsl:value-of select="0"/>
    </xsl:otherwise>
    </xsl:choose>
</xsl:template>

</xsl:stylesheet>

Here's a sample input file:
<?xml version="1.0" encoding="iso-8859-1"?>
<people>
<person name="adam"/>
<person name="eve"/>
<person name="cain">
    <parent name="adam"/>
    <parent name="eve"/>
</person>
<person name="henoch">
    <parent name="cain"/>
</person>
<person name="gladys"/>
<person name="frank">
    <parent name="henoch"/>
</person>
<person name="jose">
    <parent name="gladys"/>
    <parent name="frank"/>
</person>
</people>

Here's sample output from xsltproc on Linux:
adam(0):
eve(0):
cain(2): adam eve
henoch(3): cain adam eve
gladys(0):
frank(4): henoch cain adam eve
jose(6): gladys frank henoch cain adam eve

Fun question!
Usually when I find myself doing something like this: select="/people/person[@name=$myname]", I'll use an xsl:key instead.
You could use that key to collect all of the parents based on the parent person's @name in a variable.
If you could treat that variable as a node-set (either XSLT 2.0+ or EXSLT's node-set() function) getting the count of ancestors would simply be a matter of counting the number of items in the node-set (count()).
Another option, which feels a little hacky in my opinion, is to output a separator along with the ancestor name.
To get the ancestor count you can remove all characters other than the separator character (nested translate()) and then count the number of separators (string-length()).
You'd also need to replace all of the separators with a space when you finally output the ancestor names (another translate() call).
Example...
XML Input
<people>
    <person name="adam"/>
    <person name="eve"/>
    <person name="cain">
        <parent name="adam"/>
        <parent name="eve"/>
    </person>
    <person name="henoch">
        <parent name="cain"/>
    </person>
    <person name="gladys"/>
    <person name="frank">
        <parent name="henoch"/>
    </person>
    <person name="jose">
        <parent name="gladys"/>
        <parent name="frank"/>
    </person>
</people>

XSLT 1.0
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text"/>
  <xsl:strip-space elements="*"/>

  <xsl:key name="parent" match="parent" use="../@name"/>

  <xsl:template match="person">
    <xsl:variable name="ancestors">
      <xsl:apply-templates select="key('parent',@name)"/>
    </xsl:variable>
    <xsl:variable name="ancestor_count"
      select="string-length(translate($ancestors,translate($ancestors,'|',''),''))"/>
    <xsl:value-of select="concat(@name,'(',$ancestor_count,'): ',translate($ancestors,'|',' '))"/>
    <xsl:text>&#xA;</xsl:text>
  </xsl:template>

  <xsl:template match="parent">
    <xsl:value-of select="concat(@name,'|')"/>
    <xsl:apply-templates select="key('parent',@name)"/>
  </xsl:template>

</xsl:stylesheet>

Output
adam(0):
eve(0):
cain(2): adam eve
henoch(3): cain adam eve
gladys(0):
frank(4): henoch cain adam eve
jose(6): gladys frank henoch cain adam eve

Fiddle: http://xsltfiddle.liberty-development.net/3MEdvhm


Identifying which paragraph, if any, is a superset of all words in a document Description

need to find out the paragraph number which is containing all the words in the file.

input file java.txt

  What is a JVM?

  What is the most important feature of Java?

  Are JVM's platform independent?

  What do you mean by platform independence? What is the most important
  feature of Java? What is a JVM? Are JVM's platform independent?

Output

paragraph num : 4

Solution code:

 public class WordsOfParagraphWithMap {
        public void findParagraphWithAllWords() throws IOException{

        File file = new File("C:\\Users\\VENKAT\\Documents\\javaquestions.txt");
        FileReader fileReader = new FileReader(file);
        BufferedReader bufferedReader = new BufferedReader(fileReader);
        int paraNum = 1;
        int count = 0;
        String line;
        int paragraphWithMaxWords = 0;
        int maxWords = 0;

        Map<String, Integer> map = new HashMap<String, Integer>();

        line = nextLine(bufferedReader);

        do {
            if (line != null) {

                if (line.trim().isEmpty()) {
                    if (maxWords < count) {
                        paragraphWithMaxWords = paraNum;
                        maxWords = count;
                    }
                    paraNum++;
                    count = 0;
                    line = nextLine(bufferedReader);
                }

                if(line!=null){
                    String[] words = line.split("\\s");
                    for (String word : words) {
                        if (!map.containsKey(word)) {
                            count++;
                        } else {
                            int paraNumber = map.get(word);
                            if (paraNumber != paraNum) {
                                count++;
                            }
                        }
                        map.put(word, paraNum);
                    }
                }
            }
        } while ((line = bufferedReader.readLine()) != null);

        if (maxWords < count){
            paragraphWithMaxWords = paraNum;
            maxWords = count;
        }

        if (map.size() == maxWords)
            System.out.println("paragraph num : " + paragraphWithMaxWords);
        else
            System.out.println("no such paragraph");

    }

    private String nextLine(BufferedReader bufferedReader) throws IOException{
        String line;
        while ((line = bufferedReader.readLine()) != null) {
            if (line.trim().isEmpty()) {
                continue;
            } else {
                break;
            }
        }
        return line;
    }

    public static void main(String[] args) throws IOException {
        WordsOfParagraphWithMap wordsOfParagraphWithMap = new  WordsOfParagraphWithMap ();
        wordsOfParagraphWithMap.findParagraphWithAllWords();
    }
    }

Your code is suffering from a lack of functions. Functions help to identify what core parts of your code does, and makes those parts reusable. It also makes the calling code more readable.

By using functions, and extracting core components, it's easy to see the actual logic. For example, a main method like:

public static void main(String[] args) throws IOException {
    List<Set<String>> paragraphs = composeParagraphs(Paths.get("java.txt"));
    int superIndex = superSetParagraph(paragraphs);
    System.out.println("SuperSet Paragraph is " + superIndex);
}

Well, that's simple enough... how is it done?

Given a list of paragraph sets, finding the paragraph which is a superset, is easy:

private static int superSetParagraph(List<Set<String>> paras) {
    // get all words from all paragraphs.
    Set<String> allwords = paras.stream().flatMap(p -> p.stream()).collect(Collectors.toSet());
    // which paragraph has all words.
    for (int i = 0; i < paras.size(); i++) {
        if (paras.get(i).size() == allwords.size()) {
            return i + 1;
        }
    }
    return 0;
}

How do you get all paragraphs?

private static final Pattern SPACE = Pattern.compile("\\s+");

public static Set<String>words(String input) {
    return Arrays.stream(SPACE.split(input))
          .filter(word -> !word.isEmpty())
          .collect(Collectors.toSet());
}

private static List<Set<String>> composeParagraphs(Path path) throws IOException {
    Set<String> para = new HashSet<>();
    List<Set<String>> contents = new ArrayList<>();
    for (String line : Files.readAllLines(path)) {
        if (line.trim().isEmpty()) {
            // indicates a new paragraph....
            if (!para.isEmpty()) {
                contents.add(para);
                para = new HashSet<>();
            }
        } else {
            para.addAll(words(line));
        }
    }
    if (!para.isEmpty()) {
        contents.add(para);
    }
    return contents;
}

Again, functional extraction makes a difference.


Merging two Excel sheets by matching on two columns I have 2 sheets with the exact format, 5 columns (Category1, Category2, Category3, Month, Amount) - "Temp" and "Source".

My goal is to copy the data from "Source" to a new sheet("Combined"), append the data from "Temp" but replace the rows that are matching on column C and D with the new rows from "Temp".

For now I have the following code that does the job:

Option Explicit

Sub Verify()
Dim c As Range
Application.ScreenUpdating = False
last3 = Sheets("Temp").Cells(Application.Rows.count, "A").End(xlUp).row
last4 = Sheets("Source").Cells(Application.Rows.count, "A").End(xlUp).row
last5 = Sheets("Combined").Cells(Application.Rows.count, "A").End(xlUp).row

' Clear Contents
Sheets("Combined").Range("A1:E" & last5).ClearContents

    Sheets("Temp").Range("G2").Formula = "=C2&D2"
    Sheets("Temp").Range("G2").Copy Destination:=Sheets("Temp").Range("G3:G" & last3)

    Sheets("Source").Range("G2").Formula = "=C2&D2"
    Sheets("Source").Range("G2").Copy Destination:=Sheets("Source").Range("G3:G" & last4)

    Sheets("Source").Range("H2").Formula = "=MATCH(G2,Temp!$G$2:$G$" & last3 & ",0)"
    Sheets("Source").Range("H2").Copy Destination:=Sheets("Source").Range("H3:H" & last4)

' Copy & Format Headers
Sheets("Temp").Range("A1:E1").Copy Destination:=Sheets("Combined").Range("A1")

' Copy All Data from Temp
Sheets("Temp").Range("A2:E" & last3).Copy Destination:=Sheets("Combined").Range("A2")

' Copy Selected Data from Source
    For Each c In Sheets("Source").Range("H2:H" & last4)
        If IsError(c) Then
          last5 = Sheets("Combined").Cells(Application.Rows.count, "A").End(xlUp).row
          Sheets("Source").Range("A" & c.row & ":E" & c.row).Copy Destination:=Sheets("Combined").Range("A" & last5 + 1)
        End If
    Next c

' Clean temp Columns
Sheets("Temp").Columns("G:G").Delete
Sheets("Source").Columns("G:H").Delete
Application.ScreenUpdating = True
End Sub

My problem with it is that is too slow(~15.000 rows). It freezes my excel with a white screen for a few minutes but in the end it works. I have tried using DoEvents but it is still really slow.

I am sure there a better way to achieve what I am looking for. Can someone please help me rewrite the VBA to speed it up? I would be grateful if I could at least get it not to freeze or increase the performance somehow.

If no one offered a suggestion, I have found a way to handle this. This makes it blazing fast:

Sub Verify()
Dim c As Range, last3 As Long, last4 As Long, last5 As Long
Dim wt As Worksheet, ws As Worksheet, wc As Worksheet
Set wt = Sheets("Temp"): Set ws = Sheets("Source"): Set wc = Sheets("Combined")
Application.ScreenUpdating = False

last3 = wt.Cells(Rows.Count, 1).End(xlUp).Row
last4 = ws.Cells(Rows.Count, 1).End(xlUp).Row
last5 = wc.Cells(Rows.Count, 1).End(xlUp).Row

wc.Cells.ClearContents ' Clear Contents
wt.Range("G2").Resize(last3 - 1, 1).Formula = "=C2&D2"
ws.Range("G2").Resize(last4 - 1, 1).Formula = "=C2&D2"
ws.Range("H2").Resize(last4 - 1, 1).Formula = "=MATCH(G2,Temp!$G$2:$G$" & last3 & ",0)"

' Copy & Format Headers
wt.Range("A1:E1").Copy wc.Range("A1")

' Copy All Data from Temp
wt.Range("A2:E" & last3).Copy wc.Range("A2")

' Copy Selected Data from Source
    For Each c In ws.Range("H2:H" & last4)
        If IsError(c) Then
          last5 = wc.Cells(Rows.Count, 1).End(xlUp).Row
    wc.Range("A" & last5 + 1).Resize(1, 5).Value = ws.Range("A" & c.Row).Resize(1, 5).Value
    End If
    Next c
' Clean temp Columns
Application.DisplayAlerts = False: wt.Columns("G").Delete: ws.Columns("G:H").Delete
Application.DisplayAlerts = True: Application.ScreenUpdating = True
End Sub


Calculating which direction my enemy should face when moving I have just implemented an algorithm which calculates the direction an enemy in my game should face when moving to a location.

This is a 2D game where characters can face in one of four directions: (Up, Down, Left, Right).

When navigating to a point, if the new point is further away on the X axis than the Y axis, the enemy should show it's left or right animation.  However, if the movement would take the enemy more along the Y axis than the X axis, the enemy should show it's up or down animations.

To put it visually, the center of the X in the following image illustrates the position of my enemy on an coordinate plane.  Depending on which quadrant his movement point is placed in, the respective animation for that quadrant should be shown.

Here is my implementation.  My questions are:

Does this algorithm accomplish what I am thinking it does? From watching it on my enemy, it looks good so far, however I could just be getting lucky!
Can this algorithm be improved in any way?

protected FacingDirections CalculateFacingDirection(Vector2 navPos)
{
    Vector2 curPos = transform.position;

    float xDiff = Mathf.Abs(navPos.x - curPos.x);
    float yDiff = Mathf.Abs(navPos.y - curPos.y);

    if(navPos.x > curPos.x) //we are moving left
    {
        if(navPos.y > curPos.y) //we are moving up
        {
            return xDiff > yDiff ? FacingDirections.Left : FacingDirections.Up; //are we moving more left or up?
        }

        return xDiff > yDiff ? FacingDirections.Left : FacingDirections.Down; //are we moving more left or down?
    }
    else //we are moving right
    {
        if (navPos.y > curPos.y) //we are moving up
        {
            return xDiff > yDiff ? FacingDirections.Right : FacingDirections.Up; //are we moving more left or up?
        }

        return xDiff > yDiff ? FacingDirections.Right : FacingDirections.Down; //are we moving more left or down?
    }
}

In my opinion you should first get the axis of the maximum direction via comparison of xDiff with yDiff:

protected FacingDirections CalculateFacingDirection(Vector2 navPos)
{
    Vector2 curPos = transform.position;

    float xDiff = Mathf.Abs(navPos.x - curPos.x);
    float yDiff = Mathf.Abs(navPos.y - curPos.y);

    if (xDiff > yDiff) // we are moving more along X axis
    {
        return navPos.x > curPos.x ? FacingDirections.Left : FacingDirections.Right;
    }
    // we are moving more along Y axis
    return navPos.y > curPos.y ? FacingDirections.Up : FacingDirections.Down;
}


Alone in a Couple implementation in Java In a party everyone is in couple except one. People who are in couple
  have same numbers. Find out the person who is not in couple.

  Input:

  The first line contains an integer \$T\$ denoting the total
  number of test cases. In each test cases, the first line contains an
  integer \$N\$ denoting the size of array. The second line contains \$N\$
  space-separated integers \$A_1, A_2, \ldots, A_N\$ denoting the elements of the
  array. (\$N\$ is always odd)

  Output:

  In each seperate line print number of the person not in
  couple.

  Constraints:

  \$ 1 \leq T \leq 30\$

  \$ 1 \leq N \leq 500\$

  \$ 1 \leq A[i] \leq 500\$

  \$ N \% 2 = 1\$

  Example:

  Input:

1

5

1 2 3 2 1

  Output:

3

My approach:

/*package whatever //do not write package name here */

import java.util.Scanner;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;

class GFG {

    private static int getAloneNum (int[] arr) {
        List<Integer> alone = new ArrayList<>();

        for (Integer elem : arr) {
            if (!(alone.contains(elem))) {
                alone.add(elem);
            }
            else {
                alone.remove(alone.indexOf(elem));
            }
        }

        return alone.get(0);
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner (System.in);
        int numTests = sc.nextInt();

        for (int i = 0; i < numTests; i++) {
            int size = sc.nextInt();
            int[] arr = new int[size];

            for (int j = 0; j < size; j++) {
                arr[j] = sc.nextInt();
            }

            System.out.println(getAloneNum(arr));
        }
    }
}

I have the following questions with regards to the above code:

How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?
Is my code very redundant?

Reference

You are using a pretty nice idea here. You store things you've seen once and remove them when you've seen them a second time. To do so you're using a List.

Instead of a List you should be using a Set though. Lists are not optimized for contains checks. Also ArrayList has a pretty expensive remove operation. Let's rewrite the getAloneNum with a Set:

private static int getAloneNum(int[] arr) {
    Set<Integer> alone = new HashSet<>();
    for (int elem : arr) {
        if (alone.contains(elem)) {
            alone.remove(elem);
        } else {
            alone.add(elem);
        }
    }
    return alone.iterator().next();
}

Note that this implementation avoids the following things:

Unnecessary negation in the if-condition
repeated traversal of the container (contains and indexOf traverse the full list)

I also personally prefer to not have  a space before the opening parenthesis, but YMMV :)

As a challenge for java 8 you could try to rewrite this to use as little memory as possible by using a Stream and handling the input as it comes instead of saving it into an array :)


Probability ordering by seller's tariff I have an instance method which calculates the position of an element, depending on the tariff of its seller.

If the seller is of a level3 tariff, it gets to top 100, the probability of 40%. If the tariff is level2, then 30%, etc.

TARIFFS = {level3: 0...40,
           level2: 40...70,
           level1: 70...90,
           level0: 90..100}

def update_priority
  top = 100
  priority = 0
  random = rand(0..top)
  all_count = collection.find.count
  if TARIFFS[seller.tariff] === random
    priority = rand((all_count - top).to_f..all_count.to_f)
  else
    priority = rand(1..all_count)
  end

  collection.find(_id: self._id).update('$set' => {priority: priority})
end

And I have class method which runs every 2 hours:

def recalculate_priorities
  unscoped.each(&:update_priority)
end

It does not work fast. How can I optimize it to work faster?

Note: I'm assuming collection and unscoped are some sort of Enumerable objects.

The key to improving performance is to not do any unnecessary work. You're doing quite a bit of unnecessary work in #update_priority.

all_count = collection.find.count creates an Enumerator that isn't used. Let's get rid of that.

all_count = collection.find.count calculates the size is of that enumerator inefficiently. #count iterates the collection and counts how many elements it has. It is an O(n) operation. #size on the other hand, doesn't iterate the collection. It is an O(1) operation.

If this only happened once, this wouldn't be so bad, but this happens for every element of unscoped. Suppose unscoped has 100 elements and collection has 1000 elements. We're doing the same calculation a 100 times. That's a 100,000 unnecessary iterations! We can do better: only calculate the size once in #recalculate_priorities.

collection.find(_id: self._id).update('$set' => {priority: priority}) suffers from a similar problem. For each unscoped element at least 1 database query is performed. Again, we can do better: use a single query to update many records at once (a batch query) in #recalculate_priorities.

I've written some example code below. As I don't know any MongoDB, I made up an API for it.

def new_priority(collection_size)
  top      = 100
  priority = 0
  random   = rand(top)

  if TARIFFS[seller.tariff].cover?(random)
    lower = collection_size - top
    upper = collection_size

    return rand(lower..upper) # Floats are unnecessary
  else
    return rand(1..collection_size)
  end
end

def recalculate_priorities
  new_priorities = unscoped.map { |el| el.new_priority(collection.size) }

  unscoped.update(:priority => new_priorities)
end


Sieve of Eratosthenes using a Javascript array Any feedback on my code would be greatly appreciated.

/*
   The Sieve of Eratosthenes using a javascript array as
   an associative data structure.
*/

function range(start, limit, step) {
    var rangeArray = [];
    for (var i = start; i < limit; i += step)
        rangeArray.push(i);
    return rangeArray;
}

function isNotNull(value) { // predicate for filtering
    if (value !== null)
        return true;
    else
    return false;
}

function nullMultiples(multiple, array) { // mutates array
    var step = multiple;
    while (multiple < array.length) {
        array[multiple] = null;
        multiple = multiple + step;
    }
}

function nextPrime(currentPrime, array) {
    var successor = currentPrime++;
    while (array[successor] === null)
        successor++;
    return successor;
}

function primes(below) {
   var initSet = range(0, below, 1);
   var primeSet = []; // set of numbers used as a multiple
   var currentPrime = initSet[2]; // the first multiple is 2
   while (currentPrime < Math.sqrt(initSet.length)) {
       primeSet.push(currentPrime);
       nullMultiples(currentPrime, initSet); // mutate initSet
       currentPrime = nextPrime(currentPrime, initSet);
   }
   // return the numbers that were used as multiples and all
   // inidicies that still contain a number, except 0 and 1
   return primeSet.concat(initSet.slice(2).filter(isNotNull));
}

Since you're just doing steps of 1 and starting with 0, we don't need to take account for those. Your range function can be simplified into the following.

function range(length){
  return Array.apply(null, Array(length)).map(function (_, i) {return i;});
}

Also, a comparison is already a boolean by itself. So your isNotNull could be simplified into the following. We could coerce value into a boolean by using !!, since we're working with numbers, we might encounter 0 which is falsy but technically not null. So we compare explicitly with null instead to avoid this.

function isNotNull(value) {
    return value !== null;
}

You could also inline your search for the next prime into your primes function. You can simply check your number list if the next number has been nulled, and if so, have the loop in primes skip the number.

With that (and hopefully my understanding of the algorithm isn't wrong), here's my take:

function range(length) {
  return Array.apply(null, Array(length)).map(function(_, i) { return i; });
}

function getPrimes(end) {

  // We get the numbers below the square root of the limit. The | 0 is
  // dropping the decimal info, and since range here is zero-indexed,
  // we add 1.
  return range((Math.sqrt(end) | 0) + 1).reduce(function(numbers, root, index) {

    // If the number at root is null, then its multiples may have been
    // nulled by an earlier prime. We bail out. Nothing to do here.
    if (numbers[root] === null) return numbers;

    // We null every multiple, provided it's not 0 and 1
    else if (root !== 0 && root !== 1)
      for (var i = root * root; i < numbers.length; i += root)
        numbers[i] = null;

    // If we reached here, then probably you're looking at 0 or 1
    else numbers[root] = null;

    return numbers;

    // Here's the array that generates 0-to-end. Again, range is
    // zero-indexed so the + 1 is necessary.
  }, range(end + 1)).filter(function(i) {

    // Since 0 and 1 are already nulled, they will fall off here. No
    // additional slicing needed.
    return i !== null;
  });
}

document.write(getPrimes(121).join(','));


Sorting a PHP array in a discontinuous manner I start with an array containing some 'ids' and some 'values'.

What I need is to organize the 'ids' in a new array to be, if possible, apart when the 'values' they are associated with are alike.

So I came up with a solution.  If there is too much of a value type, the spreading is uneven.  So if one of you has a different, better, solution, I'm all ears!

Here is what I came up with:

function discontinus_sort($to_sort, $order_by, $id){

    while (count(array_count_values($to_sort)) >1) {

    $order[] = [$id => key($to_sort) , $order_by => $to_sort[key($to_sort)]];

    $holder = $to_sort[key($to_sort)];

    unset($to_sort[key($to_sort)]);

    reset($to_sort);

        if (isset($to_sort[key($to_sort)])) {

            while( $holder == $to_sort[key($to_sort)] ) {
            next($to_sort);
            }
        }
    }

while ($to_sort) {

    $order[] = [$id => key($to_sort) , $order_by => $to_sort[key($to_sort)]];

    unset($to_sort[key($to_sort)]);

}

return $order;

}

And for an example:

$test[0=>'red',1=>'red',2=>'red',3=>'crimson',4=>'aqua',5=>'chartreuse',6=>'green',7=>'chartreuse',8=>'red',9=>'crimson',10=>'crimson',11=>'aqua',12=>'aqua',13=>'green',14=>'crimson'];

$test_order = discontinus_sort($test, 'couleur', 'id');

foreach ($test_order as $key) {

echo '

';
}

If you change too many values, let's say by red, you'll end up with a big stack of red at the end.

Maybe this answer is a bit late, but hopefully someone can benefit from it!

First off, very interesting concept... It was a challenge to try and figure this one out! I have come up with another implementation, whether it's truly better or not is for the author to decide. Here it is:

<?php

function discontinuous_sort($input) {
    $new = array();

    while ($input) {
        $curr = current($input);
        if (end($new) == $curr) {
            next($input);
            continue;
        } else {
            $new[] = $curr;
            unset($input[key($input)]);
            reset($input);
        }
    }
    return array_filter($new);
}

$test = array('red', 'red', 'red', 'crimson', 'aqua', 'chartreuse', 'green', 'chartreuse', 'red', 'crimson', 'crimson', 'aqua', 'aqua', 'green', 'crimson');

$test_order = discontinuous_sort($test);

foreach ($test_order as $key) {
    echo '

';
}

I'll see what I can do to explain things.

In all honesty, looking at your algorithm, I knew things could be changed. Sorry for making it so drastic!

The first thing I knew I could do was take away the manual indexing on the input array. It does us no good to do this. This also means I can take away the last two parameters in your function. We shouldn't need to name them or create a  multidimensional array.
You were onto something with the while loop, it just needed something else!
I've taken away the aspect of a "holder". At first I thought I'd need one too, but after more work it became apparent I didn't. I am just utilizing the array positioning functions in a different manner.
My snippet basically works like this:

While the original array exists, begin a check. Check if the last element of the new array is equal to the current element in the original. If it is, move onto the next element so we don't get two identical elements next to each other. If the last element isn't equal to the current, append it to the new array and delete that element from the original. Then go back to the beginning! Lastly, erase any empty values (empties are made when we have lots of reds or whatever).

And that's it! I'm sure mine could be simplified, but we're not Code Golf here! ;)


Shift part of char array to the same array after encountering a delimiter I have a char tempBuffer which stores say my!string!hello!. After every ! is encountered that token is moved to a char codeBuffer and the rest of the characters are shifted to the begiinging of tempBuffer. So after my is moved to codeBuffer, tempBuffer contains string!hello!.

I have currently implemented it as follows:

while (tempBuffer[0] != '\0') {
    /* Read input contents into tempBuffer */
    bytesReadTotal = read(fd, tempBuffer, BUFFER_SIZE);

    /* Copy contents of tempBuffer into codeBuffer till delimiter is found*/
    for (startOfBlock = 0; startOfBlock < strlen(tempBuffer); startOfBlock++){
        if (tempBuffer[startOfBlock] != opt.separator[0])
            codeBuffer[startOfBlock] = tempBuffer[startOfBlock];
        else
            break;
    }

    if (tempBuffer[startOfBlock] == '\0')
        break;

    /* Copy contents of tempBuffer into temp2Buffer from new block position*/
    for (int i = 0; i < strlen((char*) tempBuffer); i++) {
        temp2Buffer[i] = tempBuffer[startOfBlock + 1];
        startOfBlock++;
    }

    /* Copy contents of temp2Buffer to tempBuffer */
    for (startOfTB = 0; startOfTB < strlen((char*) temp2Buffer); startOfTB++) {
        tempBuffer[startOfTB] = temp2Buffer[startOfTB];
    }

    /* Reset all contents of tempBuffer after last copied position
       to '\0' to avoid overlap */
    tempBuffer[startOfTB] = '\0';
}

I would like to avoid multiple copy operations.How can I improve this code?

C's string implementation is null-terminated. Thus, as long as,

one doesn't care about the original string, (this may not be possible if you have a const char *,) and
one has at least one char that one is willing to discard per block, (usually the block delimiter,) to turn into '\0',

one can do this in place without copying. This tokenizing is very common, and string.h from the standard library has functions that will help. For example, strtok, (and thread-safe extension to the ISO C standard, strtok_r,) or non-standard, but strsep is an improvement, (possible implementation.) In this code, this takes advantage that argv is writable and uses it to come up with some strings which are separated by strchr.

#include <string.h>
#include <stdio.h>
#include <assert.h>

/** One could probably store this, but printing it is easier. */
static void print(const char *p) { printf("codeBuffer <- %s\n", p); }

/** `str0` is a string that get separated by '!'. */
static void str_sep_bang(char *str0, void (*const callback)(const char *)) {
    char *str1;
    assert(str0 && callback);
    for( ; ; ) {
        if((str1 = strchr(str0, '!'))) *str1 = '\0';
        if(*str0 != '\0') callback(str0);
        if(!str1) break;
        str0 = str1 + 1;
    }
}

int main(int argc, char **argv) {
    int i;
    for(i = 1; i < argc; i++) {
        printf("You passed: %s.\n", argv[i]);
        str_sep_bang(argv[i], &print);
    }
    return 0;
}

This prints out,

bin/stringthing foo\!bar\!baz\!qux \!\!
You passed: foo!bar!baz!qux.
codeBuffer <- foo
codeBuffer <- bar
codeBuffer <- baz
codeBuffer <- qux
You passed: !!.

However, if one needs to store these values, you need space, (an array of char *, same as is passed in argv.) Usually that involves dynamic allocation or static allocation of the maximum size. As well, accessing this list is only valid while the data from the underlying string doesn't change or go out-of-scope; this is why crossing different modules typically involves duplication of the underlying data.


Binary search for integers I've written binary search with only my own efforts  without glancing at anywhere. I stuck on finding base case. At final, I think that if last checking is less than first index or first checking is greater than last index, it stops.  But, I'm still  suspicious of its performance and righness. I could return Integer.MAX_VALUE or Integer.MIN_VALUE if the searched number is not in the array but I assumed that all numbers are positive.

In the beginning times of writing recursion, I had difficulty in thinking recursively. But, now I have difficulty in finding base case(s).

public static int binarySearch(int[] arr, int key, int low, int high) {
        if (high < 0 || low > high )
            return -1;

        int middleIndex = (low + high) / 2;

        if (arr[middleIndex] == key)
            return middleIndex;
        else if (key > arr[middleIndex])
            return binarySearch(arr, key, middleIndex + 1, high);
        else
            return binarySearch(arr, key, low, middleIndex - 1);

}

I don't immediately see something wrong with your base case. Perhaps it could be simplified, checking only for low > high. You would need to think about what happens if you pass Integer.MAX_VALUE as high then though.

That being said, the implementation contains a major bug. low + high will overflow when the sum of them is greater than Integer.MAX_VALUE. You can use some mathematical tricks to solve this. Or use some bitwise operations, like (low + high) >>> 1.

The bitshift solution works for positive low and high (which they are). Although the sum can indeed still overflow, the unsigned shift operator >>> shifts a zero in the most significant side. Mathematically, you could think of it as dividing the number interpreted as unsigned by two. As an example:

0111 1111 1111 1111 1111 1111 1111 1111 = Integer.MAX_VALUE
0111 1111 1111 1111 1111 1111 1111 1111 = Integer.MAX_VALUE
--------------------------------------- +
1111 1111 1111 1111 1111 1111 1111 1110 = -2 ((2^32)-2 if interpreted as unsigned)

This sum overflows. Now, the difference between division (which would be the same as signed shift >>) and unsigned shift:

(-2) / 2   = 1111 1111 1111 1111 1111 1111 1111 1111 = -1
(-2) >>> 2 = 0111 1111 1111 1111 1111 1111 1111 1111 = Integer.MAX_VALUE

Also note that the recursive calls may lead to a stack overflow in Java. Although it is a tail recursive implementation, this is not optimized in Java. So for a real world implementation, prefer iteration.

Final note: always try to use braces with if/else blocks.


UIButton Subclass - Overriding getters to return placeholder/default values I'm in the process of converting a custom UIButton from Objective-C to Swift which has custom properties and default values for those properties:

MyButton.h

@interface MyButton : UIButton

@property (nonatomic, strong) IBInspectable UIColor *buttonColor;
@property (nonatomic, strong) IBInspectable UIColor *buttonSelectedColor;

// ...

@end

MyButton.m

@implementation MyButton

- (instancetype)initWithCoder:(NSCoder *)aDecoder
{
    self = [super initWithCoder:aDecoder];
    if (self) {
        [self adjustButtonColor];
    }

    return self;
}

- (instancetype)initWithFrame:(CGRect)frame
{
    self = [super initWithFrame:frame];
    if (self) {
        [self adjustButtonColor];
    }

    return self;
}

- (void)setSelected:(BOOL)selected
{
    [super setSelected:selected];

    [self adjustButtonColor];
}

- (void)setHighlighted:(BOOL)highlighted
{
    [super setHighlighted:highlighted];

    [self adjustButtonColor];
}

- (void)adjustButtonColor
{
    if (self.selected || self.highlighted) {
        self.backgroundColor = [self buttonSelectedColor];
    } else {
        self.backgroundColor = [self buttonColor];
    }
}

#pragma mark - Default colors

- (UIColor *)buttonColor
{
    if (!_buttonColor) {
        _buttonColor = [UIColor grayColor];
    }
    return _buttonColor;
}

- (UIColor *)buttonSelectedColor
{
    if (!_buttonSelectedColor) {
        _buttonSelectedColor = [self.buttonColor colorWithAlphaComponent:.5];
    }
    return _buttonSelectedColor;
}

#pragma mark - Public

- (void)setButtonColor:(UIColor *)buttonColor
{
    _buttonColor = buttonColor;

    [self updateButton];
}

@end

I have attempted to replicate this pattern in Swift with public vars which return a default value, or access a private optional variable which is returned if it exists.  I have also overridden the selected and highlighted properties, updating the button colors in didSet:

class MyButton: UIButton {

    private var _buttonColor: UIColor?
    var buttonColor: UIColor {
        get {
            if let color = _buttonColor { return color }
            return UIColor.grayColor()
        } set {
            _buttonColor = newValue
        }
    }

    private var _buttonSelectedColor: UIColor?
    var buttonSelectedColor: UIColor {
        get {
            if let selectedColor = _buttonSelectedColor { return selectedColor }
            return self.buttonColor.colorWithAlphaComponent(0.5)
        } set {
            _buttonSelectedColor = newValue
        }
    }

    override var selected: Bool {
        didSet {
            adjustButtonColor()
        }
    }

    override var highlighted: Bool {
        didSet {
            adjustButtonColor()
        }
    }

    required init?(coder aDecoder: NSCoder) {
        super.init(coder: aDecoder)
        adjustButtonColor()
    }

    override init(frame: CGRect) {
        super.init(frame: frame)
        adjustButtonColor()
    }

    func adjustButtonColor() {
        if selected || highlighted {
            backgroundColor = buttonSelectedColor
        } else {
            backgroundColor = buttonColor
        }
    }
}

A few questions:

Is this an appropriate use of private variables?  Is there any way to accomplish the behavior I want with a single variable rather a second optional settable variable for each color?
Is overriding UIButton properties to call adjustButtonColor in didSet abuse of the getter/setter?
If initWithCoder is a failable initializer do I need to check if self is nil before calling adjustButtonColor()?

Is this an appropriate use of private variables? Is there any way to accomplish the behavior I want with a single variable rather a second optional settable variable for each color?

This can be much easier accomplished with a lazy stored property:

lazy var buttonColor: UIColor = UIColor.grayColor()
lazy var buttonSelectedColor: UIColor =  self.buttonColor.colorWithAlphaComponent(0.5)

The right-hand side is evaluated exactly once, when the property
is accessed the first time. This makes the private _xxx variables
obsolete. (I think that you seldom need such a "shadow copy" in Swift.)

But there seems to be no real need for buttonColor to be evaluated
lazily. If you make it an ordinary stored property then you can add
a property observer:

var buttonColor = UIColor.grayColor() {
    didSet {
        self.updateButton()
    }
}

If you want buttonSelectedColor to be computed from buttonColor then
it needs to be a lazy property, otherwise you could make it a stored
property as well:

var buttonSelectedColor = UIColor.grayColor().colorWithAlphaComponent(0.5)

  Is overriding UIButton properties to call adjustButtonColor in didSet abuse of the getter/setter?

That is fine. The Swift reference explicitly states: "You can also add property observers to any inherited property (whether stored or computed) by overriding the property within a subclass."

  If initWithCoder is a failable initializer do I need to check if self is nil before calling adjustButtonColor()?

You don't need to (and you can't). If

 super.init(coder: aDecoder)

fails then your init?(coder:) method fails immediately, and the next statement
is not reached.


Removing duplicates for both values My special case: home project, automatic downloader for podcasts.

Overall algorithm is:

Download a list of available podcasts
hash the podcasts
load metadata + hash of downloaded podcasts from sqlite db
Algorithm this questions is about -  throw out all already downloaded.
Download new podcasts
save metadata to sqlite db

Algorithm discussion

I'm hoping for comments on using std::rotate, performance, and the implementation.

For downloaded data, I currently use a vector. For data from DB, I also use a vector.

I merge both together and sort them according to the hashes (obviously).

And algorithm doubleEraser on the merged vector.

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

template <typename ForwardItr>
ForwardItr doubleEraser(ForwardItr first, ForwardItr last)
{
 auto itr = first;
 typename std::iterator_traits<ForwardItr>::value_type firstMatch = *first;
 bool hasFirstMatch(false);

 while(itr != last)
 {
  auto next = std::next(itr);
  if(next != last && *itr == *next)
  {
    if(!hasFirstMatch)
    {
     hasFirstMatch = true;
     firstMatch = *itr;
    }
    else
    {
     if(*itr == firstMatch) // again at first match
     {
       return itr;
     }
    }

    std::rotate(itr, std::next(itr, 2), last); // throw matched elements to the end of container
   }
   else
    ++itr;
  }
 return last;
}

template <typename T>
void print(T& c)
{
 for(auto & element : c)
  std::cout << element << " ";

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

template <class T>
void process(std::vector<T>& t)
{
  std::string formating(" \t");
   std::cout << "input: " << formating;
 print(t);
 std::sort(t.begin(), t.end());
 std::cout << "sorted:" << formating;
 print(t);
 auto itr_begin = doubleEraser(t.begin(), t.end());
 std::cout << "dEraser:" << formating;
 print(t);
 t.erase(itr_begin, t.end());
 std::cout << "output:" << formating;
 print(t);
}

int main()
{
 std::vector<int> vec {1,2,3,4,5,6,7,8,9,3,5,6,7,2};
 std::vector<char> vec2 {'A', 'C', 'D', 'D', 'G', 'A' };
 std::vector<std::string> vec3 {"Hello", "World", "that", "be", "that", "Hello"};

 process(vec);
 process(vec2);
 process(vec3);
}

Comment by @T.C.:

Don't merge them; sort them separately and then use std::set_difference:

#include <algorithm>
#include <vector>
#include <iostream>
template <typename T>
void print(T& c)
{
 for(auto & element : c)
  std::cout << element << " ";

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

int main()
{
 std::vector<int> vec {1,2,3,4,6,7,8};
 std::vector<int> vec4 {3,4,5,6};
 std::sort(vec.begin(), vec.end());
 std::sort(vec4.begin(), vec4.end());
std::set_difference(vec.begin(), vec.end(), vec4.begin(), vec4.end(), std::inserter(vec5, vec5.begin()));
 print(vec5);
}

Input: {1,2,3,4,6,7,8} and {3,4,5,6}
Output wanted: 1,2,5,7,8
Output real: 1,2,7,8

You cannot use std::set_difference because of the hashes used as comparison criteria. The Hash Distribution of new hashes is not sortable in a way that new items will be the last ones, which is a requirement for std::set_difference.


Making a triangle without inner stars By this method I am able to solve my problem, but is there any other way that I can make this type of triangle? Please correct my code if I am doing this the long way.

public class Pyramid{
    public static void main(String [] args){
        for (int i=0;i<= 6 ;i++) {
            for (int x=0;x < 6-i;x++) {
                System.out.print(" ");
                }
                for (int k=1;k<=i;k++) {
                        if (k <= 1) {
                            System.out.print(" *");
                        }
                        else if(k <= 2) {
                            System.out.print("  ");
                        }
                        else if(k <= 3) {
                            System.out.print("  ");
                        }
                        else if(k <= 4) {
                            System.out.print("  ");
                        }
                        else if(k <= 5) {
                            System.out.print("  ");
                        }
                        else if(k <= 6) {
                            System.out.print("  ");
                        }

                }
                for (int l=0;l<=i;l++) {
                        if (l <= 0) {
                            System.out.print(" *");
                        }

                }
                System.out.println();

    }
    System.out.print("* * * * * * * *");
}
}

Your method certainly works, but I agree that using nested/multiple loops and inner if/else blocks is inelegant, if only because it makes following the code somewhat harder. Also, as you point out in a comment, hard-coding the structure is a nightmare if you suddenly want a pyramid which is 46 stars high.

As an alternative, I've rewritten the code to break it out into separate methods which hopefully make the code easier to understand, and also to allow a variable pyramid height (any value from zero or above).

public static void main(String[] args) {
    drawStarPyramid2(8);
}

private static void drawStarPyramid2(int height) {
    if (height < 0) {
        throw new IllegalArgumentException("Height cannot be negative.");
    }
    StringBuilder sb = new StringBuilder(height * height);
    appendSides(sb, height);
    appendBaseline(sb, height);
    System.out.println(sb.toString());
}

private static void appendSides(StringBuilder sb, int height) {
    int baselineWidth = height * 2 - 1;
    int midLine = baselineWidth / 2;
    for (int rowIndex = 0; rowIndex < height - 1; ++rowIndex) {
        int leftStarOffset = midLine - rowIndex;
        appendSpacesThenStar(sb, leftStarOffset);
        if (rowIndex > 0) {
            int rightStarOffset = midLine + rowIndex - 1;
            appendSpacesThenStar(sb, rightStarOffset - leftStarOffset);
        }
        sb.append("\n");
    }
}

private static void appendSpacesThenStar(StringBuilder sb, int spaces) {
    for (int spaceIndex = 0; spaceIndex < spaces; ++spaceIndex) {
        sb.append(' ');
    }
    sb.append('*');
}

private static void appendBaseline(StringBuilder sb, int stars) {
    boolean first = true;
    for (int starIndex = 0; starIndex < stars; ++starIndex) {
        if (!first) {
            sb.append(' ');
        }
        sb.append('*');
        first = false;
    }
}

Because the sides need to be rendered differently to the baseline, each chunk of code goes into its own method, with a name which clearly describes the different purpose of each.

The appendSides method is responsible only for drawing the left and right sides of the triangle. This calculates the baseline width (the number of characters on the console counting stars and spaces) and this will be equal to height stars (because the number of stars on the baseline must equal the number of stars along the height of each side) plus height - 1 spaces, which gives 2 * height - 1. Then it calculates the mid-way point (in terms of characters on the console line) and then places the first star at this point.

For all subsequent lines, the "left" side star is simply placed at the position which is one additional character further left of the previous position (starting at the mid-way position), and the "right" side star at the position which is one additional character further right of the previous position. The rowIndex is a convenient way to calculate how many places to move away from the mid-way point on each line. The mathematics being used to calculate all of these offsets is fairly simple, but I recommend you sketch it out on a bit of paper, one line at a time, to get a feel for how the numbers work together.

The appendSpacesThenStar method simply appends the specified number of space characters to the StringBuilder and then a star. This method does not append a newline, because this method is often called twice for the same line, to write the "left" and then the "right" stars.

The appendBaseline method just appends (to the StringBuilder) the required number of stars, separated by spaces.

A StringBuilder is being used to make assembly of the final string sequence more efficient, allowing the building of each line to be split across multiple method calls, rather than trying to finish each line in a single statement.

(Also note that the initial capacity passed to the StringBuilder constructor can be improved by giving exactly the number of characters that will be needed, once spaces, stars, and newlines have been taken into consideration, but I'll leave this as an exercise for you.)


LeetCode Counting Bits in Swift I solve this problem in Swift. I am looking for a code review, thanks!

  Given a non negative integer number num. For every numbers i in the
  range 0 ≤ i ≤ num calculate the number of 1's in their binary
  representation and return them as an array.

class Solution {
    func countBits(num: Int) -> [Int] {
        var nums = [Int](count: num+1, repeatedValue: 0)
        if num == 0 { // if num is 0
            return nums
        }
        for i in 1...num {
            nums[i] = binaryOnes(i)
        }
        return nums
    }
    func binaryOnes(num: Int) -> Int {
        var num = num
        var count = 0
        repeat  {
            if num % 2 == 0 { // even numbers
                num /= 2
            } else { // all odd numbers
                num = (num-1)/2
                count += 1
            }
        } while num > 1
        if num == 1 { // when num is 1 at the end
            count += 1
        }
        return count
    }
}

Both methods don't use any state of the Solution class, so they should
be static methods of that type, or global functions.

binaryOnes() can be simplified. If you replace

repeat { ... } while num > 1

by

while num > 0 { ... }

then the additional check for num == 1 becomes obsolete:

func binaryOnes(num: Int) -> Int {
    var num = num
    var count = 0
    while num > 0 {
        if num % 2 == 0 { // even numbers
            num /= 2
        } else { // all odd numbers
            num = (num-1)/2
            count += 1
        }
    }
    return count
}

Now observe that num % 2 gives the least significant bit of
the number (0 or 1), and num /= 2 is a truncating division.
Therefore the function can be simplified to

func binaryOnes(num: Int) -> Int {
    var num = num
    var count = 0
    while num > 0 {
        count += num % 2
        num /= 2
    }
    return count
}

More sophisticated bit counting methods can be found at
https://graphics.stanford.edu/~seander/bithacks.html, they can
be more effective for large numbers.

In countBits, the check for num == 0 is not necessary,
because 1...num is the empty range in that case:

func countBits(num: Int) -> [Int] {
    var nums = [Int](count: num+1, repeatedValue: 0)
    for i in 1...num {
        nums[i] = binaryOnes(i)
    }
    return nums
}

Calling the variables num and nums could be confusing,
upTo: might be a better name for the parameter.

But what the function actually does is to map the numbers
0...upTo to their bit count. That can be done directly with
a map() method:

func countBits(upTo: Int) -> [Int] {
    return (0...upTo).map(binaryOnes)
}

An alternative approach would be to use the fact that

bitCount(n) = bitCount(n/2) + (n % 2)

for all (positive) integers n. Together with bitCount(0) = 0
this is a recursive computation method. But since you store the
bit counts in an array anyway, this can be implemented as
a simple iteration:

func countBits1(upTo: Int) -> [Int] {
    var result = [ 0 ]
    for i in 1...upTo {
        result.append(result[i/2] + (i % 2))
    }
    return result
}

Now the binaryOnes() function is not needed anymore.


Securely convert and return a user selected file I designed a Python3 webservice which gets a file name, looks for this file in a local folder, converts it using an external software, then sends the converted file to the user.

For this example, the input and output file types are respectively PNG and JPEG, but they're actually proprietary formats.

Here is my code:

#!/usr/bin/python3
# -*- coding: utf-8 -*

from http.server import BaseHTTPRequestHandler, HTTPServer
import os
import os.path as op
import subprocess as sub
from urllib.parse import parse_qs, urlparse

PORT_NUMBER = 8080
PNG_TO_JPG_CALL = '/usr/share/png-to-jpg'
PNG_FOLDER = '/home/foo/png_files'

class RequestHandler(BaseHTTPRequestHandler):
    # Display a text to the user.
    def display_msg(self, text):
        print(text)
        self.send_header('Content-type', 'text/plain; charset=utf-8')
        self.send_header('Content-Disposition', 'inline')
        self.end_headers()
        self.wfile.write(bytes(text, 'UTF-8'))

    # Send a file to the user (open the Download File dialog box).
    def send_file(self, file_path, jpg_name):
        self.send_header('Content-type', 'image/jpeg')
        self.send_header('Content-Disposition', 'attachment; filename="%s"' % jpg_name)
        self.end_headers()
        with open(file_path, 'rb') as f:
            self.wfile.write(f.read())

    # Check for GET requests
    def do_GET(self):
        self.send_response(200)

        # Get URL arguments
        url_args = parse_qs(urlparse(self.path).query, keep_blank_values=True)

        # Check for the `id` attribute
        if 'id' not in url_args:
            self.display_msg('USAGE: [...]/?id=some_file.jpg')
            return

        target = url_args['id'][0]

        # Check if the requested file have the good extension
        if target[-4:] != '.jpg':
            self.display_msg('TARGET SHOULD BE A PNG FILE')
            return

        # build the png file path (change the extension)
        png_path = op.join(PNG_FOLDER, op.splitext(target)[0] + '.png')
        print('Looking for %s' % png_path)

        # Check if the requested is present on the disk
        if not op.isfile(png_path):
            self.display_msg('PNG FILE NOT FOUND')
            return

        # call the converter with the requested file, print the output
        p = sub.Popen([PNG_TO_JPG_CALL, png_path], stdout=sub.PIPE, stderr=sub.PIPE)
        output, errors = p.communicate()
        if output:
            print('output: %s' % output.decode('utf-8'))

        # Check for errors outputs
        if errors:
            self.display_msg('CONVERSION ERROR: png-to-jpg says:\n' + errors.decode('utf-8'))
            return

        # Build the converted file path
        jpg_name = op.splitext(target)[0] + '.jpg'
        jpg_path = op.join(os.getcwd(), jpg_name)

        # Check if the converted file is present on the disk
        if not op.isfile(jpg_path):
            self.display_msg('CONVERSION ERROR: Can not locate the ouput directory.')
            return

        # returns the converted file then remove it
        self.send_file(jpg_path, jpg_name)
        os.remove(jpg_path)

# Launch the web server
try:
    server = HTTPServer(('', PORT_NUMBER), RequestHandler)
    print('Web server started. Please go to 127.0.0.1:%i.' % PORT_NUMBER)
    server.serve_forever()
except KeyboardInterrupt:
    print('Interrupted by the user - shutting down the web server.')
    server.socket.close()

Is this secure?

This script is insecure because there are a few small issues. And such issues can often be combined to produce bigger issues, so it's important to be wary about them.

First, you're not restricting the path of the image to PNG_FOLDER. An attacker can ask for ?id=../../etc/passwd. It will fail because you check that the id ends with '.jpg'. But what if the user sends ?id=../../etc/passwd,some_file.jpg? Did you check that png-to-jpg is not going to try to split on a comma? A simple fix: get a list of all possible file names first and only allow an id which is in the list.

Second, you're sending the full png-to-jpg answer. I don't know how this utility works, but an attacker can probably gain useful information just by looking at the output. He will know that he should look at png-to-jpg vulnerabilites. More generally, any information sent to an attacker is another thing that can be exploited.

Third (this is not necessarily an issue), but it's possible to list all files by simply trying all combinations and see the output. It's even possible to see what's already converted and what's not with timing attacks.

I'm not saying that fixing these issues will make your code fully secure, but it will be a step forward.