Implementing a queue using a circular buffer I'm working on implementing a queue using a circular buffer problem. Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated.

class QueueOnCirciularBuffer:
    def __init__(self, max_size):
        self.buffer = [0]*max_size
        self.index = 0 # element to write
        self.size = 0
        self.max_size = max_size
    def push_element(self, value):
        if self.size == self.max_size:
            raise Exception('queue full')
        self.buffer[self.index] = value
        self.index += 1
        self.size += 1
        self.index = self.index % self.max_size
    def pop_element(self):
        if self.size > 0:
            value = self.buffer[(self.index - self.size+self.max_size)%self.max_size]
            self.size -= 1
            return value
        else:
            raise Exception('empty queue')
    def peak_element(self):
        if self.size > 0:
            return self.buffer[(self.index-1+self.max_size)%self.max_size]
        else:
            raise Exception('empty queue')
if __name__ == "__main__":
    q = QueueOnCirciularBuffer(16)
    q.push_element(1)
    q.push_element(2)
    print q.peak_element() # output 2
    q.pop_element()
    print q.peak_element() # output 2

    q2 = QueueOnCirciularBuffer(3)
    for i in range(3):
        print i
        q2.push_element(i)
    for i in range(10):
        print q2.pop_element()
        q2.push_element(i)

Advice 1

QueueOnCirciularBuffer: you misspelled Circular

Advice 2

Wikipedia gives more canonic names for the data structure. Why not choose, say, CircularBuffer?

Advice 3

Instead of having a single index self.index, why not take two: self.head_index is the index in the underlying storage array holding the head element of the buffer; self.tail_index points into the array location at which next element is inserted. If not efficiency, this adds to maintainability in my opinion.

Advice 4

value = self.buffer[(self.index - self.size+self.max_size)%self.max_size]
self.buffer[(self.index-1+self.max_size)%self.max_size]

Adding self.max_size has not effect since you take the modulo of it.

Advice 5

PEP 8 complains about some aspects of your code layout. Consider using a Python IDE (I use PyCharm); it gives you instant feedback if your code does not adhere to rules in PEP 8.

Advice 6

Its funny that your peak_element returns the tail element of the queue; why not rename it to, say, peak_tail. (And possibly provide peak_head.)

Summa summarum

All in all, I had this in mind:

class CircularBuffer:
    def __init__(self, capacity):
        self.buffer = [0] * capacity
        self.size = 0
        self.capacity = capacity
        self.head_index = 0
        self.tail_index = 0

    def push_element(self, value):
        if self.size == self.capacity:
            raise Exception('The circular buffer is full.')
        self.buffer[self.tail_index] = value
        self.tail_index = (self.tail_index + 1) % self.capacity
        self.size += 1

    def pop_element(self):
        if self.size == 0:
            raise Exception('Popping from an empty circular buffer.')
        ret = self.buffer[self.head_index]
        self.head_index = (self.head_index + 1) % self.capacity
        self.size -= 1
        return ret

    def peek_head(self):
        if self.size == 0:
            raise Exception('Peeking into an empty circular buffer.')
        return self.buffer[self.head_index]

Hope that helps.


Avoid calling init method on each return method I'm implementing a module system into one of mine ASP.NET MVC applications and I am currently writing a module helper which all the modules can use to get some basic information about itself.

I'm using the namespace of the caller to identify the module and search it up in the database and retrieve the information.

Now I want to make everything static, so I don't have to instantiate it each time.

   public static class ModuleHelper
{
     private static  ModuleInstallations _module;

     static ModuleHelper()
     {
         Init();
     }

    private static void Init()
    {
         var stackTrace = new StackTrace();
         MethodBase method = stackTrace.GetFrame(2).GetMethod();
         var calledNamespace = method.ReflectedType.Assembly.GetName().Name;

        if (_module == null || calledNamespace != _module.Namespace)
        {
            LoadModuleInfo(calledNamespace);
        }
    }

    private static void LoadModuleInfo(string moduleNamespace)
    {
        var moduleService = new ModulesService();
        _module = moduleService.GetByNameSpace(moduleNamespace);
    }

    public static string GetPathModule(this Controller controller, string pathFile)
    {
        Init();

        return string.Format("/Modules/{0}/{1}", _module.AreaName, pathFile);
    }

    public static string GetModuleAreaName(this Controller controller)
    {
        Init();

        return _module.AreaName;
    }

    public static int GetModuleId(this Controller controller)
    {
        Init();

        return _module.Id;
    }
}

The problem is that a previous module could get stored into the class and I have to check on each method if it's another module. If it's another module I have to retrieve the information of it.

What would be a good solution for this problem?

The first thing I don't like much is that you walk the callstack to find the caller. It's faster and more robust to find the assembly via a type that's part of that assembly. Since your methods are called on a controller, you could use controller.GetType().Assembly to find it.

The next issue is that you only store a single value and you do so in a non threadsafe fashion. I'd use a threadsafe dictionary that maps an assembly to the data instead.

Omitting details like argument validation, my code would look similar to the following:

public class ModuleInformation
{
    private static readonly ConditionalWeakTable<Assembly, ModuleInformation> _dict = new ConditionalWeakTable<Assembly, ModuleInformation>();

    private static ModuleInformation LoadInfo(Assembly assembly)
    {
        // replace with code to load the module information
        return new ModuleInformation();
    }

    public static ModuleInformation Get(Assembly assembly)
    {
        return _dict.GetValue(assembly, LoadInfo);
    }

    public string Id { get; private set; }
}

public static class ModuleInformationExtensions
{
    public static ModuleInformation GetModuleInformation(this Controller controller)
    {
        return ModuleInformation.Get(controller.GetType().Assembly);
    }

    public static string GetAreaName(this Controller controller)
    {
        return controller.GetModuleInformation().Id;
    }
}

Another dubious part of your code is:

var moduleService = new ModulesService();
_module = moduleService.GetByNameSpace(moduleNamespace);

Depending on the implementation of the ModulesService it might be a good idea to pass it in via dependency injection. Database access from static methods is usually a bad idea since the database should be injected. This is incompatible with your static design, so you might want to switch to instances which are then injected into the controllers.


Extending Sieve of Eratosthenes beyond a billion For MAX value of 1000000000 (\$10^9\$), it takes about 45 seconds to reach the line where it prints "done". How can I speed this up?

Is printing to screen always going to take so much time? I know it's hardware.

On increasing the size of MAX beyond \$10^9\$ gives me an exception on the line memset(a, true, MAX);. Is there any limit to this function? I should be able to use all of the RAM. Running this program uses around 954 MB of memory.

void sieve_of_eratosthenes(){
    bool* a;
    a = (bool*)malloc(MAX * sizeof(bool));
    memset(a, true, MAX);
    unsigned long int i = 1;
    while (i < MAX){

        while (((++i)<MAX)&&(!a[i]));

        if (2 * i >= MAX)
            break;

        for (unsigned long int k = 2 * i; k < MAX; k += i)
            if (a[k])
                a[k] = false;
    }
    std::cout << "done\n";
    for (unsigned long int i = 2; i < MAX; i++)
        if (a[i])
            std::cout << i << "\n";
    getchar(); getchar();
}

A few things you can do:

Use a bit vector (with bit manipulation) instead of a bool array. This gives you 8 times more memory. If you use C++ vector< bool> you get this optimization for free.
Store only odd numbers in the array. This will save additional factor of 2 in memory. You need to adapt the logic of the program a little bit, but this is not extremely difficult. This saves also some time because in the first iteration the algorithms just marks half of the numbers.
The outer loop (the while (i < MAX)) only needs to run from 0 to ceil(sqrt(MAX)).
The inner loop can start at i*i not just 2*i.

Summarizing the first two will give you factor of 16 more memory (or factor of 16 more numbers to sieve with given memory) and the last two will significantly improve the run-time (not sure by how much exactly).

The segfault is most likely due to the fact that a == NULL, i.e. the malloc routine fails to allocate the memory. You need to check for NULL after the malloc call and before memset.


Simple BST implementation using C++ Struct I am trying to implement DSs in C++ and this is BST insert and search functions. I tried in two different ways, please review and see if one is advantageous over other.
With pointer to pointer

#include <stdio.h>
#include <iostream>

struct BstNode{
 int data;
 BstNode* left;
 BstNode* right;
};

BstNode* NewNode(int data)
{
 BstNode* newNode = new BstNode();
 newNode->data = data;
 newNode->left = NULL;
 newNode->right = NULL;
 return newNode;
}
void Insert(BstNode** root,int data)
{
 if(*root == NULL)
 {
     *root= NewNode(data);
 }
 else if(data <= (*root)->data)
 {
     (*root)->left = NewNode(data);
 }
 else
 {
     (*root)->right = NewNode(data);
 }
}
bool SearchBST(BstNode* root, int data)
{
 if(root == NULL)
 {
     return false;
 }
 else if(root->data == data)
 {
     return true;
 }
 else if(data <= root->data)
 {
     return SearchBST(root->left, data);
 }
     else
     {
         return SearchBST(root->right, data);
     }
 }
 int main()
 {
     BstNode* ptr_root = NULL;
     Insert(&ptr_root,15);
     Insert(&ptr_root,10);
     Insert(&ptr_root,16);
     int num;
     std::cout<<"Enter the number: \n";
     std::cin>> num;
     if (SearchBST(ptr_root,num))
         std::cout<<"Found\n";
     else
         std::cout<<"Not Found\n";

     return 0;
 }

Without pointer to a pointer:

#include <stdio.h>
#include <iostream>

struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};
BstNode* NewNode(int data)
{
    BstNode* newNode = new BstNode();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
BstNode* Insert(BstNode* root,int data)
{
    if(root == NULL)
    {
        root= NewNode(data);
    }
    else if(data <= root->data)
    {
        root->left = NewNode(data);
    }
    else
    {
        root->right = NewNode(data);
    }
    return root;
}
bool SearchBST(BstNode* root, int data)
{
    if(root == NULL)
    {
        return false;
    }
    else if(root->data == data)
    {
        return true;
    }
    else if(data <= root->data)
    {
        return SearchBST(root->left, data);
    }
    else
    {
        return SearchBST(root->right, data);
    }
}
int main()
{
    BstNode* ptr_root = NULL;
    ptr_root=Insert(ptr_root,15);
    ptr_root=Insert(ptr_root,10);
    ptr_root=Insert(ptr_root,16);
    int num;
    std::cout<<"Enter the number: \n";
    std::cin>> num;
    if (SearchBST(ptr_root,num))
        std::cout<<"Found\n";
    else
        std::cout<<"Not Found\n";

    return 0;
}

Neither of your implementations is "advantageous" over other because both of them are C-style, unidiomatic C++ code — they are really C code with a handful of C++ additions.  Moreover, they share many errors.  This review will (hopefully) help you convert your code to C++ style and fix these errors.

Formatting

The indentation of the first implementation is a nightmare.  Fix it by consistently indenting everything by 4 spaces and make sure lines on the same indentation level align with each other.  Also, comma tokens should generally be followed by a space.

General design

You code does not provide a suitable interface because "BST Node" is an implementation detail.  Users do not want to work directly with nodes most of the time; they want to work with the trees.  Therefore, you should provide a class to encapsulate the tree.  The insert and search functions should be member functions of the tree, not free functions.

Memory management

You use new to allocate nodes, but never delete them.  In other words, you are constantly leaking memory.  This makes your code not reusable.  You should use a smart pointer (e.g., std::unique_ptr) instead of raw pointers in order to solve this problem.

Miscellaneous

#include <stdio.h> is redundant and should be removed.

Instead of the type-unsafe NULL, use nullptr.

Here's how I'd put the whole thing together (minimal version):

#include <initializer_list>
#include <iostream>
#include <memory>

class Binary_search_tree {
    struct Node {
        int value{};
        std::unique_ptr<Node> left{};
        std::unique_ptr<Node> right{};
    };
public:
    Binary_search_tree() = default;
    Binary_search_tree(std::initializer_list<int> init)
    {
        for (auto elem : init) {
            insert(elem);
        }
    }
    void insert(int value)
    {
        insert_at(root, value);
    }
    bool contains(int value) const
    {
        return contains_at(root, value);
    }
private:
    void insert_at(std::unique_ptr<Node>& node, int value)
    {
        if (!node) {
            node.reset(new Node{value});
        } else if (value < node->value) {
            insert_at(node->left, value);
        } else {
            insert_at(node->right, value);
        }
    }
    bool contains_at(const std::unique_ptr<Node>& node, int value) const
    {
        if (!node) {
            return false;
        } else if (value < node->value) {
            return contains_at(node->left, value);
        } else if (node->value < value) {
            return contains_at(node->right, value);
        } else {
            return true;
        }
    }
    std::unique_ptr<Node> root{};
};

int main()
{
    Binary_search_tree tree{31, 41, 59, 26, 53, 59};

    int num;
    std::cout << "Enter the number: \n";
    std::cin >> num;

    if (tree.contains(num)) {
        std::cout << "Found\n";
    } else {
        std::cout << "Not Found\n";
    }

    return 0;
}

(live demo)


Markers on Google Maps I am using PHP to get data from a MySQL database, and use the data to drop multiple markers into Google Maps. Please give me some suggestions for my code.

<?php
require_once 'Common/system_start.php';
$sql="select * from tab_mem order by sn desc ";
$result=  mysql_query($sql);
$data=mysql_fetch_assoc($result);
$row=mysql_num_rows($result);

header("Content-type: text/xml");

// Iterate through the rows, adding XML nodes for each

while ($row = @mysql_fetch_assoc($result)){
// ADD TO XML DOCUMENT NODE
$node = $dom->createElement("marker");
$newnode = $parnode->appendChild($node);

$newnode->setAttribute("address", $row['address']);

}

 echo $dom->saveXML();
?>

HTML5

PHP

The commonly accepted approach to SQL statements is to make commands all caps, so I would convert my SQL statements to look like so...

$sql="SELECT * FROM tab_mem ORDER BY sn DESC ";

In other words, only the information from your tables should be lower case. This makes it easier to read.

You really should never use error suppression. Sure if it isn't a fatal error its nice to ignore those errors and let the program continue running, but you should never, no matter how minor, let an error go unresolved. It doesn't help your program and could potentially cause more problems rather than less.

You just declared $data and $row then turn around name a new $row that you just set $data to, never having used the old ones. Why? If you aren't going to use that information, don't set it. I'd just remove the $data and first $row variables. This is one of the few times I think its ok to set variables in an expression, otherwise I'd point this out too.

Don't know if it is just stackoverflow messing with your code or not, but ensure that your code is indented! If it is you can ignore this line, but judging from later bits of code, I have to assume that its not just stackoverflow. Examples given in JavaScript section.

Where in the world did $dom and $parnode come from? Does this even work?

JavaScript

I'll admit to not being well versed in JavaScript myself, only enough to write minor scripts for myself. However a lot of what I know from PHP can be trasferred over to JavaScript, and my first problem here is that you have JavaScript functions within your JavaScript functions. Move those! I can't imagine when that would be necessary. All functions should be within the same scope. Minor exceptions would be lamda functions, though I hold that if you can make it into a function to be reused, do so.

Your code indentation here is really lacking. If I did not have a text editor with matching-brace highlighting there is no way in the world I could read this. An I'm still having trouble anyways. Here's a couple of examples of good indentation:

var gmap = new google.maps.Map(
    map_div, {
        zoom:16,
        center: latlng,
        mapTypeId: google.maps.MapTypeId.ROADMAP
    }
);
//etc...
while (markers.length){
    var address="";
    geocoder=new google.maps.Geocoder();
    alert("...");
}

Proper indentation would also show you that you have an extra closing brace } on the end of your onSuccess() function. Which probably causes errors.

I'm going to stop here. I've already pointed out quite a bit for you to look at. If after you have corrected these things you want me to look over it again you can update your question with the new code and drop me a comment and I'll try to come back to it. Good Luck!


Find minimum number of coins (count and list of coins too) For a given set of denominations, you are asked to find the minimum number of coins with which a given amount of money can be paid. Assume that you can use as many coins of a particular denomination as necessary.
For example, given the denominations 1, 3, 4, and the target amount 6,
the algorithm should find the optimal 2 coins required: 3 + 3.

As an exercise while learning Scala,
I implemented two versions.
One to find just the number of coins,
and one to find the list of coins.
I'm looking for a review of all aspects of this code.
import org.junit.runner.RunWith
import org.scalatest.FunSuite
import org.scalatest.junit.JUnitRunner

@RunWith(classOf[JUnitRunner])
class FindMinCoinsTest extends FunSuite {

  def findMinCoins(amount: Int, coins: Set[Int]): Int = {
    def findMinCoins(amount: Int, count: Int): Int = {
      if (amount == 0) count
      else if (amount < 0) Integer.MAX_VALUE
      else coins.map(coin => findMinCoins(amount - coin, count + 1)).min
    }

    val count = findMinCoins(amount, 0)
    if (count == Integer.MAX_VALUE) 0
    else count
  }

  test("find 10 with 1, 5, 7") {
    assert(2 == findMinCoins(10, Set(1, 5, 7)))
  }

  test("find 10 with 1, 5, 10") {
    assert(1 == findMinCoins(10, Set(1, 5, 10)))
  }

  test("find 7 with 3, 5") {
    assert(0 == findMinCoins(7, Set(3, 5)))
  }

  test("find 6 with 1, 3, 4") {
    assert(2 == findMinCoins(6, Set(1, 3, 4)))
  }

  def findMinCoinsList(amount: Int, coins: Set[Int]): List[Int] = {
    def findMinCoinsList(amount: Int, list: List[Int]): (Boolean, List[Int]) = {
      if (amount == 0) (true, list)
      else if (amount < 0) (false, Nil)
      else {
        val solutions = coins.map(coin => findMinCoinsList(amount - coin, coin :: list)).filter(_._1)
        if (solutions.nonEmpty) solutions.minBy(_._2.size)
        else (false, Nil)
      }
    }

    findMinCoinsList(amount, Nil)._2.sorted
  }

  test("find sorted list, for 10 with 1, 5, 7") {
    assert(List(5, 5) == findMinCoinsList(10, Set(1, 5, 7)))
  }

  test("find sorted list, for 10 with 1, 5, 10") {
    assert(List(10) == findMinCoinsList(10, Set(1, 5, 10)))
  }

  test("find sorted list, for 7 with 3, 5") {
    assert(Nil == findMinCoinsList(7, Set(3, 5)))
  }

  test("find sorted list, for 6 with 1, 3, 4") {
    assert(List(3, 3) == findMinCoinsList(6, Set(1, 3, 4)))
  }

  test("find list 7 with 1, 3, 4") {
    assert(List(3, 4) == findMinCoinsList(7, Set(1, 3, 4)))
  }

}

Here are some things that I would maybe do in another way:

replace Integer.MAX_VALUE by Int.MaxValue
replace cascade if-else statements by pattern matching
return value of Int.MaxValue replaced by throwing an IllegalArgumentException
try to make recursive functions tail-recursive and use the @tailrec annotation
maybe use Seq instead of List. IMHO you can use List as a concrete implementation for Seq. I am not 100% sure in this case that there won't be additional overhead (e.g. by creating unnecessary collection objects). Read about scala's collection API.
Maybe you would like to simplify the whole thing by writing just on top-level function def minimumCoins(amount: Int, availibleCoins: Seq[Int]): Seq[Int]. It returns the coins as solution. An empty Seq means you need no coins. You can easily get the number of coins by the size of the Seq. There can be cases where no solution exists! What should happen in those cases? Maybe an ecxeption should be thrown again. Or was that the sense of the boolean return value? Maybe you wrap the returned Seq with an Option like Option[Seq[Int]].
I did not really spend time understanding your algorithm. If that is what you want you should tell it explicitly. Anyway some collections have combinatorical functions like mySeq.combinations(5) and mySeq.permutations which can be useful for such problems. If you have an specific analytic algorithm (from your brain or from anywhere else) it is probably better and more efficient than those based on those functions. Those functions tend to solve problems by something like brute-force. So the code used for this may be of little amount and you get something useful quickly and with less analytics. You can be more productive and let the computer do the work. On the other side, processing all combinations or permutations can be very inefficient especially on large parameters their number gets quickly very very high. Those functions are alluring.


Celestial age calculator Our solar system has 8 planets, including earth. Our calendar has some very confusing concepts such as leap years, which I still don't fully understand. In fact, since where I live, we use a different solar calendar that is different from the Gregorian reforms of the Julian Western calendar, I think I'm born in March but I should be born in February! Anyways, I attempted to create a simple program that calculates any given age, subtracting the leap days of each four years, in any planet of our solar system except Pluto which I believe is not a planet. I'm not sure about it.
def calculate_days(age):
    leap_days = 0 #holds number of leap days
    leap_years_list = [i for i in range(age) if i % 4 == 0] #holds the essence of leap years

    for j in leap_years_list:
        if j % 4 == 0 or j % 400 == 0 and j % 100 != 0:
            leap_days += 1 #if leap years are divisible by four and not divisible by a hundred, add to leap days

    return (age * 365) - leap_days

def calculate_celestial_age(planet, age):
    number_of_days = calculate_days(age) #calculate the days in age

    assert str.islower(planet), "Planet name must be entered in lower case e.g. 'mercury'" #if planet name is in lowercase, give error

    days_in_year = {"mercury": 88, "venus": 224, "earth": 365, "mars": 687, "jupiter": 4332, "saturn": 10759, "uranus": 30688,
                    "neptune": 60182} #days in each planet's year

    if planet == "mercury":
        return number_of_days / days_in_year["mercury"]
    elif planet == "venus":
        return number_of_days / days_in_year["venus"]
    elif planet == "earth":
        return number_of_days / days_in_year["earth"]
    elif planet == "mars":
        return number_of_days / days_in_year["mars"]
    elif planet == "jupiter":
        return number_of_days / days_in_year["jupiter"]
    elif planet == "saturn":
        return number_of_days / days_in_year["saturn"]
    elif planet == "uranus":
        return number_of_days / days_in_year["uranus"]
    elif planet == "neptune":
        return number_of_days / days_in_year["neptune"]
    else:
        raise Exception("Unknown Planet! Are you sure you've enter a planet?")

age = 23

planets = ["mercury", "venus", "earth", "mars", "jupiter", "saturn", "uranus", "neptune"]

for planet in planets:
    print("{0}: {1}".format(planet, calculate_celestial_age(planet, age)))

For my age, 23, I got these results:

mercury: 95.3409090909091
venus: 37.455357142857146
earth: 22.986301369863014
mars: 12.212518195050945
jupiter: 1.9367497691597415
saturn: 0.7798122502091273
uranus: 0.2733967674661105
neptune: 0.1394104549533083

According to this, my results are accurate.

Simplify the logic

It seems like:

if planet == "mercury":
    return number_of_days / days_in_year["mercury"]
elif planet == "venus":
    return number_of_days / days_in_year["venus"]
elif planet == "earth":
    return number_of_days / days_in_year["earth"]
elif planet == "mars":
    return number_of_days / days_in_year["mars"]
elif planet == "jupiter":
    return number_of_days / days_in_year["jupiter"]
elif planet == "saturn":
    return number_of_days / days_in_year["saturn"]
elif planet == "uranus":
    return number_of_days / days_in_year["uranus"]
elif planet == "neptune":
    return number_of_days / days_in_year["neptune"]

can be easily rewritten:

if planet in days_in_year:
    return number_of_days / days_in_year[planet]
raise Exception("Unknown Planet! Are you sure you've enter a planet?")

Also, one could consider keeping it even more simple and use the fact that:

return number_of_days / days_in_year[planet]

will throw the relevant exception for an invalid value.

Do not repeat yourself

You can try to avoid duplicated values and have a single source of information. In your case, the list of planet is indirectly hardcoded twice :

days_in_year = {"mercury": 88, "venus": 224, "earth": 365, "mars": 687, "jupiter": 4332, "saturn": 10759, "uranus": 30688,
                "neptune": 60182} #days in each planet's year

and

planets = ["mercury", "venus", "earth", "mars", "jupiter", "saturn", "uranus", "neptune"]

Maybe you could define a constant like DAYS_IN_YEAR_PER_PLANET (corresponding to your actual days_in_year dictionnary) and use it where you are using the list of the planets (for planet in DAYS_IN_YEAR_PER_PLANET: for instance).

Do not perform more operations than required

number_of_days = calculate_days(age) is computed for every planet in the list. It would be better from a performance point of view to feed the function a number of days.

Useless list (or useless test)

You are creating a list with values divisible by 4. Then you iterate over it and check if the value is divisible by 4. It seems like a waste of effort. Let's get rid of the list creation. Code is based on the initial version of your code.

def calculate_days(age):
    leap_days = 0 #holds number of leap days

    for j in range(age):
        if j % 4 == 0 and j % 100 != 0:
            leap_days += 1 #if leap years are divisible by four and not divisible by a hundred, add to leap days

    return (age * 365) - leap_days

Also, this can somehow be written by abusing the generator expression and the sum builtin:

def calculate_days(age):
    leap_days = sum(1
                    for j in range(age)
                    if j % 4 == 0 and j % 100 != 0)
    return (age * 365) - leap_days

Also, you could find mathematical expressions to compute the number of leap days in a more efficient way (constant time instead of linear time) but I'll keep this out of the review.


A Python Snake Game Using Pygame My attempt at creating a snake game, in pygame. I tried to make it as simple as possible, but i feel it could be better in terms of best practice, and efficiency, along the idea of avoiding redundant code.
It would be appreciated, if anyone can give me advice in that regard.
import pygame
import time
import random
pygame.init()
pygame.font.init()

WINDOW = pygame.display.set_mode((500, 500))

pygame.display.set_caption('snake')

FOOD_COORS = []

TICK = 15

RUN = True
SNAKE_COMP = [[50, 50, 2], [40, 50, 2], [30, 50, 2], [20, 50, 2], [10, 50, 2]]
f = [random.randint(0, 50)*10, random.randint(0, 50)*10]
d = 2
CLOCK = pygame.time.Clock()

def hit():
    time.sleep(3)
    pygame.quit()

class snake():
    def __init__(self, SNAKE_COMP):
        self.x, self.y = SNAKE_COMP[0][0:2]
    def draw(self, SNAKE_COMP):
        self.SNAKE_COMP = SNAKE_COMP
        for i in range(0, len(SNAKE_COMP)):
            pygame.draw.rect(WINDOW, (255, 255, 255), (SNAKE_COMP[i][0], SNAKE_COMP[i][1], 10, 10))

    def hit_check(self, SNAKE_COMP):
        self.SNAKE_COMP = SNAKE_COMP
        if SNAKE_COMP[0][0] >= 500 or SNAKE_COMP[0][0] < 0:
            hit()
        if SNAKE_COMP[0][1] >= 500 or SNAKE_COMP[0][1] < 0:
            hit()
        test_l = [[]]
        for i in range(0, len(SNAKE_COMP)):
            test_l.append(tuple(SNAKE_COMP[i][0:2]))
        for i in range(0, len(test_l)):
            if test_l.count(test_l[i]) > 1:
                hit()

class food():
    global FOOD_COORS
    def draw(self):
        x, y = self.x, self.y
        pygame.draw.rect(WINDOW, (255, 0, 0), (x, y, 10, 10))
    def spawn(self, SNAKE_COMP):
        global FOOD_COORS
        self.SNAKE_COMP = SNAKE_COMP
        test_l = [[]]
        for i in range(0, len(SNAKE_COMP)):
            test_l.append(SNAKE_COMP[i][0:2])
        g = True
        while g:
            x = random.randint(0, 49)*10
            y = random.randint(0, 49)*10
            if [x, y] not in test_l:
                g = False
        FOOD_COORS = [x, y]
        self.x, self.y = x, y
snek = snake(SNAKE_COMP)
apple = food()
apple.spawn(SNAKE_COMP)
s = False
g = False
while RUN:
    CLOCK.tick(TICK)

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            RUN = False

    keys = pygame.key.get_pressed()
    if keys[pygame.K_UP] and d != 3:
        d = 1
    elif keys[pygame.K_RIGHT] and d != 4:
        d = 2
    elif keys[pygame.K_DOWN] and d != 1:
        d = 3
    elif keys[pygame.K_LEFT] and d != 2:
        d = 4
    if g != True and SNAKE_COMP[0][0:2] != FOOD_COORS:
        last = len(SNAKE_COMP) - 1
        for i in range(1, len(SNAKE_COMP)):
            SNAKE_COMP[len(SNAKE_COMP)-i][2] = SNAKE_COMP[len(SNAKE_COMP)-i-1][2]
        SNAKE_COMP[0][2] = d
        for i in range(0, len(SNAKE_COMP)):
            if SNAKE_COMP[i][2] == 1:
                SNAKE_COMP[i][1] -= 10
            elif SNAKE_COMP[i][2] == 2:
                SNAKE_COMP[i][0] += 10
            elif SNAKE_COMP[i][2] == 3:
                SNAKE_COMP[i][1] += 10
            elif SNAKE_COMP[i][2] == 4:
                SNAKE_COMP[i][0] -= 10
    else:
        k = SNAKE_COMP[0][2]
        FOOD_COORS.append(k)
        if k == 1:
            FOOD_COORS[1] -= 10
        elif k == 2:
            FOOD_COORS[0] += 10
        elif k == 3:
            FOOD_COORS[1] += 10
        elif k == 4:
            FOOD_COORS[0] -= 10
        SNAKE_COMP.insert(0, FOOD_COORS)
        apple.spawn(SNAKE_COMP)
    snek.hit_check(SNAKE_COMP)
    apple.draw()
    snek.draw(SNAKE_COMP)
    pygame.display.update()
    WINDOW.fill((0, 0, 0))

pygame.quit()

On the whole, the game works and has a solid UI that you've correctly kept basic and mostly out of play as you focus on the game engine logic. It looks like you've gone for a partially-OOP approach by putting focus on the two entities that are drawable and their necessary data but leaving the main game logic outside of a class. I think that's a reasonable fundamental design. I do have a variety of suggestions for tightening up this design and improving code style though.
Tight coupling
Although your classes are potentially useful abstractions, the snake's movement update is done outside of the snake class, breaking encapsulation. A snake.move or snake.change_direction function is the correct delegation of responsibility for this rather than reaching into the class from main and messing with its internals.
The state of code with classes and functions that rely on and mutate global state is difficult to predict. For example, I'd reasonably expect a snake or food class to be able to create multiple instances with separate positions. But in this design, instances are tightly coupled to a single global FOOD_COOR or SNAKE_COMP variable. Creating more than a single instance of either class breaks it.
There are other more subtle violations of modularity, like calling global hit inside of snake.hit_check. This function should return true or false if a hit occurred and let the calling code invoke hit how, when and if they please rather than creating a dependency between the class and exterior code. pygame could be removed or at least injected into the object so the same snake logic could hook to any visual interface.
High cyclomatic complexity
The main while loop that runs the game has very high cyclomatic complexity with over 18 branches and 3 layers of nesting. These giant blocks of conditionals and loops make the code very hard to understand (and by extension, maintain and debug) and should be broken out into functions or otherwise refactored.
Abusing literals
The code abuses hard-coded literal values throughout. If you want to change the size of the grid, for example, you'd need to walk the whole file hunting for all the 10s that happen to be related to the grid size to make them a different number. This is tedious and error-prone even in a tiny program.
Same applies to window size and a few other things. Storing these values as variables in one place and referencing them means everything just works when you need to change a value, helping to eliminate typo bugs and ease refactoring. If classes or functions need to know the window size, this information should be injected in a parameter to the initializer or appropriate method.
d (really direction) has 4 possible values: 1, 2, 3 and 4. The problem is that "1" has no semantic meaning here. It's not obvious whether a "1" entails up, down, left or sideways. The classical way to handle this is an enumeration, but even direction = "up" would increase the expressiveness of the code and reduce bugs (did you type in 2 when you meant 1 somewhere?).
Magical boolean flags
Variables like
s = False
g = False

are unclear. Pick descriptive names and avoid boolean flags in favor of functions that can return true/false to handle control flow. The reason functions are cleaner than flags is because they result in less state for the caller to keep track of and support modularity. Less state means the code is easier to understand. Modularity means it's easier to isolate problems if they occur and handle refactors locally without causing a domino effect throughout the code base.
Complex logic
Much of the logic can be simplified considerably. To pick one example, code that checks whether the head segment is colliding with the tail,
test_l = [[]]
for i in range(0, len(SNAKE_COMP)):
    test_l.append(tuple(SNAKE_COMP[i][0:2]))
for i in range(0, len(test_l)):
    if test_l.count(test_l[i]) > 1:
        hit()

could be something like
if any(SNAKE_COMP[0][:2] == x[:2] for x in SNAKE_COMP[1:]):
    hit()

Even here, it's unusual that SNAKE_COMP needs 3 elements in its coordinates. The slice is a code smell because it's non-obvious. If the third element is direction, it's not necessary. Only the head needs an explicit direction.
Style and naming

Classes should be UpperCamelCase. You don't need the () after the class name unless you're inheriting. Making the class Snake as it should be means you can call the instance snake instead of the awkward intentional typo snek to avoid the alias.

Use ALL_CAPS variable names sparingly, if at all, and only to designate program constants.

Never use single-letter variables unless the purpose is overwhelmingly obvious from context.
f = [random.randint(0, 50)*10, random.randint(0, 50)*10]
d = 2

are not obvious. f is never used in the program which an editor with static analysis should warn you of and d should be called direction.

Alphabetize imports.

Use vertical whitespace more liberally, particularly around functions and blocks.

In addition to confusing single-letter boolean flags, names like SNAKE_COMP are unclear. What's COMP? Something like snake_coordinates, snake_body or snake_tail seems a bit clearer here. Even better in a class like snake.tail.

Follow PEP-8 and your style will sparkle.
UX
After a collision, the game freezes for 3 seconds and dies. As a player, I might feel like the game crashed or is buggy. A message or visual indication of the collision would communicate the snake's death better. Even just exiting instantly feels like a smoother experience.
Efficiency
This is totally premature, but it's worth keeping in mind that nearly all of your snake and apple operations that are O(n) like SNAKE_COMP.insert(0, FOOD_COORS) can be made O(1) using a deque and set. When you move the snake forward, you can rotate the deque. When you check for collision between the head and the body, you can use a set lookup.
Rewrite suggestion, round 1
This requires Python 3.8 because of the whisker assignments, but you can easily move those outside of the blocks.
I'm using __iter__ in both classes. Since I'm doing all of the drawing and pygame interaction in the main (the point is to keep UI and game logic separate), making the snake iterable is a nice way to get all of its body segments, but I cast to a tuple to avoid the caller mutating its position accidentally.
On the other hand, I trust that the caller will abide by the vector input for the turn function since we're all consenting adults. If you don't trust the client to behave, you can validate this coordinate pair and raise an error.
There's still lots of room for improvement: the main code is a bit bloated so this refactor is mostly an exercise in class organization and trying to keep everything loosely coupled. Docstrings are pretty cursory and could better explain the parameters and return values.
I don't really know Pygame so I may have gaffed--I find the key handlers pretty awkward, but I notice you can slice out the arrow keys and make a nice, indexable list of flags that hopefully doesn't break anything.
import pygame
from random import randrange

class Snake:
    def __init__(self, size, direction, body):
        self.size = size
        self.direction = direction
        self.body = list(map(tuple, body))

    def __iter__(self):
        return map(tuple, self.body)

    def in_bounds(self, width, height):
        """ Returns whether the snake's head is in the height/width bounds """
        x, y = self.body[0]
        return x >= 0 and y >= 0 and x < width and y < height

    def move(self):
        """ Moves the snake in the direction it's facing """
        self.body.insert(0, (self.body[0][0] + self.direction[0] * self.size,
                             self.body[0][1] + self.direction[1] * self.size))

    def remove_tail(self):
        """ Destroys the snake's last tail segment """
        del self.body[-1]

    def touching_point(self, point):
        """ Returns whether point is somewhere in the snake's body """
        return point in self.body

    def touching_tail(self):
        """ Returns whether the snake's head point is in the snake's body """
        return self.body[0] in self.body[1:]

    def set_direction(self, x, y):
        """ Sets the snake's direction given a cardinal unit-vector facing
            in a non-opposite direction from the snake's current direction
        """
        if (-x, -y) != self.direction:
            self.direction = x, y

class Food:
    def __init__(self, x=0, y=0):
        self.x, self.y = x, y

    def __iter__(self):
        yield self.x, self.y

    def reposition(self, size, width, height, used_squares):
        """ Repositions the apple on the size grid within the bounds avoiding
            certain used squares. Infinitely loops if no squares are available.
        """
        while point := (randrange(0, width, size), randrange(0, height, size)):
            if point not in used_squares:
                self.x, self.y = point
                break

if __name__ == "__main__":
    class Color:
        white = 255, 255, 255
        red = 255, 0, 0
        black = 0, 0, 0

    width = height = 500
    game_speed = 15
    cell_size = 10
    directions = (0, -1), (0, 1), (1, 0), (-1, 0)
    initial_body = (50, 50), (40, 50), (30, 50), (20, 50), (10, 50)
    initial_direction = (1, 0)
    pyg_arrow_key_loc = slice(273, 277)
    pygame.init()
    pygame.display.set_caption("snake")
    pyg_window = pygame.display.set_mode((width, height))
    pyg_clock = pygame.time.Clock()
    snake = Snake(cell_size, initial_direction, initial_body)
    apple = Food()
    apple.reposition(cell_size, width, height, snake)

    while not any(event.type == pygame.QUIT for event in pygame.event.get()):
        if any(arrows := pygame.key.get_pressed()[pyg_arrow_key_loc]):
            snake.set_direction(*directions[arrows.index(1)])

        snake.move()

        if snake.touching_point(*apple):
            apple.reposition(cell_size, width, height, snake)
        else:
            snake.remove_tail()

        if snake.touching_tail() or not snake.in_bounds(width, height):
            pygame.quit()

        pygame.draw.rect(pyg_window, Color.black, (0, 0, width, height))
        apple_rect = (apple.x, apple.y, cell_size, cell_size)
        pygame.draw.rect(pyg_window, Color.red, apple_rect)

        for x, y in snake:
            pygame.draw.rect(pyg_window, Color.white, (x, y, cell_size, cell_size))

        pyg_clock.tick(game_speed)
        pygame.display.update()

Rewrite suggestion, round 2
I wasn't entirely happy with main in the above rewrite so I gave a shot at cleaning it up a bit. It's still not perfect and adds code but it'd be a likely next step if you wanted to scale up the app. Breaking render into entity-specific functions is a potential next step as the app grows.
Notice that the Snake and Food classes don't need to be touched thanks to the earlier refactor and we can treat them as black boxes. After this refactor, the main function can treat SnakeGame as a black box as well and just specify its configuration. You can see how the abstractions build up: we can tuck these classes into another file like snake.py and use it as a library.
import pygame
from snake import Food, Snake

class SnakeGame:
    class Color:
        white = 255, 255, 255
        red = 255, 0, 0
        black = 0, 0, 0

    def __init__(self, width, height, cell_size,
                 initial_body, initial_direction, game_speed):
        pygame.init()
        pygame.display.set_caption("snake")
        self.pyg_window = pygame.display.set_mode((width, height))
        self.pyg_clock = pygame.time.Clock()
        self.snake = Snake(cell_size, initial_direction, initial_body)
        self.apple = Food()
        self.cell_size = cell_size
        self.width = width
        self.height = height
        self.game_speed = game_speed
        self.apple.reposition(cell_size, width, height, self.snake)

    def run(self):
        pyg_arrow_key_loc = slice(273, 277)
        directions = (0, -1), (0, 1), (1, 0), (-1, 0)

        while not any(event.type == pygame.QUIT for event in pygame.event.get()):
            if any(arrows := pygame.key.get_pressed()[pyg_arrow_key_loc]):
                self.snake.set_direction(*directions[arrows.index(1)])

            self.snake.move()

            if self.snake.touching_point(*self.apple):
                self.apple.reposition(self.cell_size, self.width,
                                      self.height, self.snake)
            else:
                self.snake.remove_tail()

            if (self.snake.touching_tail() or
                not self.snake.in_bounds(self.width, self.height)):
                pygame.quit()

            self.render()

    def render(self):
        pygame.draw.rect(self.pyg_window, SnakeGame.Color.black,
                              (0, 0, self.width, self.height))
        apple_rect = (self.apple.x, self.apple.y, self.cell_size, self.cell_size)
        pygame.draw.rect(self.pyg_window, SnakeGame.Color.red, apple_rect)

        for x, y in self.snake:
            pygame.draw.rect(self.pyg_window, SnakeGame.Color.white,
                                  (x, y, self.cell_size, self.cell_size))

        self.pyg_clock.tick(self.game_speed)
        pygame.display.update()

if __name__ == "__main__":
    SnakeGame(width=500,
              height=500,
              cell_size=10,
              initial_body=((50, 50), (40, 50), (30, 50), (20, 50), (10, 50)),
              initial_direction=(1, 0),
              game_speed=15).run()

Suggested exercises

Add a score.
Improve graphics/UI/messaging/text.
Try making multiple apples.
Make the snake periodically "poop", creating an obstacle that it cannot touch but fades away over time.
Add walls.
Add levels.
Try adding a second snake that uses the wasd keys on the same keyboard.
Use Flask SocketIO to make a real time network game.
Try writing a snake AI.


Find All Numbers Disappeared in an Array The task
is taken from leetcode

  Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array),
  some elements appear twice and others appear once.

  Find all the elements of [1, n] inclusive that do not appear in this
  array.

  Could you do it without extra space and in O(n) runtime? You may
  assume the returned list does not count as extra space.

  Example:

  Input:

  [4,3,2,7,8,2,3,1]

  Output:

  [5,6]

My solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
  return nums
    .reduce((arr, x) => {
      arr[x - 1] = null;
      return arr;
    }, Array.from({length: nums.length}, (v, k) => k+1))
    .filter(Boolean);
};

There has to be a more elegant solution to that.

You have created a good solution, just a few style points that can reduce code size.

Why null rather than false or even 0 in arr[x - 1] = null;

Why not use commas to remove need for return. Eg .reduce((arr, x) => {arr[x - 1] = null; return arr; } becomes .reduce((arr, x) => (arr[x - 1] = null, arr))

To create an array of indexes you could have used the shorter forms, Array.from(nums, (item, i) => i + 1)) or nums.map((item,i) => i + 1)

Rewrites
function findMissing(arr) {
  return arr
    .reduce((a, i) => (a[i - 1] = 0, a), arr.map((item, i) => i + 1))
    .filter(Boolean);
}

or
const findMissing = arr => arr
  .reduce((a, i) => (a[i - 1] = 0, a), arr.map((item, i) => i + 1))
  .filter(Boolean);

You could also have solved it with a set as follows
function findMissing(arr) {
    const s = new Set(arr), res = [];
    var i = arr.length;
    while (i) { s.has(i--) || res.push(i + 1) }
    return res;
}


Javascript - Replace lots of if statements I have a a couple of different radio buttons which return an ethnicity and a gender. The script runs inside an internal application so rather than returning "boy", "girl" or "both" I get back 7707330, 7707333, and 7707336. Similar from the ethnicity radio button.

I then need to validate data based on the combonation of ethnicity and gender. This was a pretty simple task but I have ended up with 15 if statements! It all works as it should, but there must be a cleaner solution?

    function test(radioResults) {

    var1 = radioResults[0].toString();
    var2 = radioResults[1].toString();
    roll = parseFloat(parent.roll);

    if (var2 == '7707330') {
        gender = 'boy';
    }
    if (var2 == '7707333') {
        gender = 'girl';
    }
    if (var2 == '7707336') {
        gender = 'both';
    }

    if (var1 == '7707341') {
        maori(gender);
    }
    if (var1 == '7707344') {
        pasifika(gender);
    }
    if (var1 == '7707347') {
        all(gender);
    }
}

function maori(gender) {
    //Maori
    if (gender == 'boy') {
        ethnicity = parseFloat(parent.getMBoys);
        validation(ethnicity);
    }
    if (gender == 'girl') {
        ethnicity = parseFloat(parent.getMGirls);
        validation(ethnicity);
    }
    if (gender == 'both') {
        ethnicity = parseFloat(parent.getTotalM);
        validation(ethnicity);
    }
}

function pasifika(gender) {
    //Pasifika
    if (gender == 'boy') {
        ethnicity = parseFloat(parent.getPBoys);
        validation(ethnicity);
    }
    if (gender == 'girl') {
        ethnicity = parseFloat(parent.getPGirls);
        validation(ethnicity);
    }
    if (gender == 'both') {
        ethnicity = parseFloat(parent.getTotalP);
        validation(ethnicity);
    }
}

function all(gender) {
    //All
    if (gender == 'boy') {
        ethnicity = parseFloat(parent.getBoys);
        validation(ethnicity);
    }
    if (gender == 'girl') {
        ethnicity = parseFloat(parent.getGirls);
        validation(ethnicity);
    }
    if (gender == 'both') {
        ethnicity = parseFloat(parent.getTotalRoll);
        validation(ethnicity);
    }
}

function validation(ethnicity) {

    percent = ethnicity * 5 / 100;

    if (ethnicity - percent > roll || (ethnicity + percent < roll)) {
        parent.document.getElementById('CF_7784443').value = "FAIL";
    } else {
        parent.document.getElementById('CF_7784443').value = "PASS";
    }
}

One option is to have a map from key -> value

for example:

var var2 = radioResults[1].toString();
var gender = {'7707330': 'boy',
               '7707333': 'girl',
               '7707336': 'both'}[var2];

You could even put functions as the values. For example:

var var1 = radioResults[0].toString()
{'7707341': maori,
 '7707344': pasifika,
 '7707347': all}[var1](gender);


Basic binary Tree in JavaScript I wrote a basic binary tree in JS. Can anyone give me some feedback about my code?

I just want to know if this is the right approach, and how I can improve the tree. I am new to JavaScript and data structures.

function bst() {
    this.root = null;
}

bst.prototype.insert = function( obj ){

    if ( this.root == null ){
        this.root = new node(obj);
    }
    else if (this.root.value > obj){
         if (this.root.left != null ){
            this.root.left.insert( obj );
        }
        else {
            this.root.left = new node(obj);
        }
    }
    else if (this.root.value < obj){
        if (this.root.right != null ){
            this.root.right.insert( obj );
        }
        else {
            this.root.right = new node(obj);
        }
    }
}

    function node( obj ){

   this.left = null;
    this.right = null;
    this.value = obj;

    }

node.prototype.insert = function( obj ){

if (this.value > obj){

    if (this.left != null){
        this.left.insert( obj )
    }
    else{
        this.left = new node(obj);
    }
}

else if (this.value < obj){

    if (this.right != null){
        this.right.insert( obj )
    }
    else{
        this.right = new node(obj);
    }
}
//elase duplicated key value
else{
    console.log("duplicated bst key")
}

}

var bst = new bst();
bst.insert(25);
bst.insert(75);
bst.insert(12);
bst.insert(37);
bst.insert(87);
bst.insert(63);

console.log(bst.root.value);
console.log(bst.root.left.value);
console.log(bst.root.right.value);
console.log(bst.root.right.left.value);
console.log(bst.root.right.right.value);
console.log(bst.root.right.left.right.value);

I can see two obvious points:

Constructor names are usually capitalized, to indicate that they should be invoked with new
You've got some code duplication between bst::insert and node::insert. This even leads to the bug that you don't recognise/handle duplicate values in the root node.

So, I'd suggest:

function Bst() {
    this.root = null;
}
Bst.prototype.insert = function(obj) {
    if (this.root == null) {
        this.root = new Node(obj);
    } else {
        this.root.insert(obj);
    }
};

  I am new to data structures.

Binary trees are a wide field :-) First, I'm missing some other basic operations like searching, traversing, and deleting. If you have mastered these, you can go on with optimizing your tree, e.g. making it a balanced one.


Using Comprehensions to Handle a Large Dataset in Python 2.7 I have a Python 2.7.6 script parsing large files (~60MB to ~2GB) containing lines of the following format:

  componentA componentB < floating point value >

My goal is to sum the floating point values for duplicate pairs of components and reflected pairs, reducing each pair to a single entry in the output file. For example, if I have the following three lines in the input file:

  componentA componentB 1.5
  componentB componentA 2.0
  componentA componentB 0.5

The output file should combine them into one entry:

  componentA componentB 4.0

Other notes:

The output also needs to be sorted by the lesser of each component pair.
I am not very concerned about the memory footprint of the routine because it will be run on a server with substantial amounts of RAM available. I am optimizing for speed and code maintainability.

The code I currently have accomplishes this by storing component names in nested dictionaries. The top-level dictionary maps component names to a second dictionary. The second-level dictionary maps the second half of each component pair to the floating-point value corresponding to the pair.

Example:

base_dict = {componentA: {componentB: 1.2,
                          componentC: 0.7}}

Output from this example would look like this:

  componentA componentB 1.2
  componentA componentC 0.7

Here is my code:

base_dict = {}

with open(input_file_name, 'r') as fi:
    for line in fi:
        component1, component2, value = line.split()
        (min, max) = (component1, component2) if (component1 < component2) else (component2, component1)

        if not min in base_dict:
            base_dict[min] = {max:float(value)}

        elif not max in base_dict[min]:
            base_dict[min][max] = float(value)

        else:
            base_dict[min][max] += float(value)

out_list = []
for component1, nested_dict in base_dict.iteritems():
    for component2, value in nested_dict.iteritems():
        out_list.append("{0}\t{1}\t{2}\n".format(component1, component2, value))

with open(output_file_name), 'w') as fo:
    fo.writelines(sorted(out_list))

In addition to a general code review for this snippet, there are two sections that I would like to convert to comprehensions if possible:

Constructing the nested dictionaries - I may be dealing with close to 10 million lines in the input file, and I would like to utilize implicit loops to do this.
Constructing the output list for sorting

If anyone has any completely different approaches to the problem of summing duplicate and reflected pairs, I'm all ears.

As requested:

Sort the list according to the component names. To achieve a correct order, either swap component names when necessary, or supply the custom comparator (which will account for (componentA, componentB) being the same thing as (componentB, componentA)).

Once the list is sorted, the entries to be tallied are adjacent, and an actual tallies could be computed in a single pass over the list.


Rails Way for dynamic link_to I have a drop-down that users can choose what template they are about to receive. I'm pretty novice to Rails but I kind of go the logic Front-end = JavaScript and that's what I did, but this use of JavaScript seems like Rails should be able to handles it.

        <%= form_tag %>
            <%= select_tag :statement_type, options_for_select(Statement.statement_types.keys.to_a), :class => 'id_select', :id => 'secret_id'  %>

    <button type="button" class="btn btn-default" data-dismiss="modal">Cancel</button>
        <%= link_to "New Form", new_statement_template_path(:statement_type => 'SoW'), :id => "secret_submit", method: :post %>

The -only- purpose of the form_tag is because I couldn't get the link_to to successfully launch other-wise.

I make the link dynamic by using this function

$('#secret_id').on('change', function(){
    $('#secret_submit').attr('href', '/statements/new/statement_type='+ $('#secret_id').val());
});

I of course now have a pretty ugly URL, and in addition had to create a custom route, so I am wondering about the 'Rails Way' of doing this. Or at the least, making the URL prettier.

Your link_to is set to POST but you are adding the statement_type on the url like if it were a GET request? Sounds like you are mixing things and you can resolve this using just a single form element without JS if I understand you right.

<%= form_tag new_statement_template_path, method: :post %>

    <%= select_tag :statement_type, options_for_select(Statement.statement_types.keys.to_a) %>

    <button type="button" class="btn btn-default" data-dismiss="modal">Cancel</button>
    <%= submit_tag "New Form" %>

<% end %>

Now your controller action will have a the selected option at params[:statement_type].


Determine if one string is a rotation of the other Python After thinking for a long hard time, learning about algorithms to find substrings, and coming to really long and tedious code I decided against my solution and to look for help. The solution was much simpler and elegant. After determining that my code was too much for a simple task I came across an explanation of a simple way to find if one string was a rotation of the other. Man I feel dumb for falling down a long rabbit hole however I learned much about many different things and also how to keep it simple stupid. Previous post of this problem here.

#rotated list

def is_rotated(lst1, lst2):
    ''' Is lst2 a rotation of lst1'''
    str1, str2 = ''.join(map(str,lst1)), ''.join(map(str,lst2))
    if not len(str1) == len(str2):
        raise ValueError("Lengths not equal")

    if str2 in (str1 + str1):
        return True
    return False

# rotation
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,7,1,2,3,4]
assert is_rotated(lst1, lst2)

# rotation with repeated numbers
lst1, lst2 = [1,2,3,4,6,4,7,1], [6,4,7,1,1,2,3,4]
assert is_rotated(lst1, lst2)

# different set
lst1, lst2 = [1,2,3,4,6,4,6], [6,4,7,1,2,3,4]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1,2,3,4,6,4,7], [6,4,6,1,2,3,4]
assert not is_rotated(lst1, lst2)

# equal
lst2 = lst1
assert is_rotated(lst1, lst2)

# empty
lst1, lst2 = [], []
assert is_rotated(lst1, lst2)

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)

Good work! This is certainly primarily an improvement from your previous implementation. However, there are still a few problems.

Don't raise an error when passed two lists of differing length. Not only is this unexpected by users, it breaks some of your tests.

# 1 empty, 1 not empty
lst1, lst2 = [], [1]
assert not is_rotated(lst1, lst2)
lst1, lst2 = [1], []
assert not is_rotated(lst1, lst2)

The pattern of if condition return True else return False should be replaced with return condition. This is easier to read and reduces the amount of code you have to write!
Joining the lists of integers with the empty string as a separator is dangerous. If I pass in [1, 23] and [12, 3] the function will incorrectly return True. If the function only has to handle integers, you can easily fix this by using a comma (or any other character) as a separator. (Just remember to include it when checking if the string is contained in the other string str1 + ',' + str1)

I would prefer a more general solution that works for lists containing any type of element. Using Nas Banov's answer from Stack Overflow to handle the sub list check, this is a really simple function to write.

def contains_sublist(lst, sublst):
  n = len(sublst)
  return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))

def is_rotated(lst1, lst2):
  if not len(lst1) == len(lst2):
    return False
  return len(lst1) == 0 or contains_sublist(lst2 * 2, lst1)


Implementing Haskell#words Learn You a Haskell shows the words function.

  words and unwords are for splitting a line of text into words or
  joining a list of words into a text

Example:

ghci> words "hey these are the words in this sentence"
["hey","these","are","the","words","in","this","sentence"]
ghci> words "hey these           are    the words in this\nsentence"
["hey","these","are","the","words","in","this","sentence"]

Please critique my implementation.

words' :: String -> [String]
words' []  = []
words' xxs@(x:xs)
  | x == ' '  = words' xs
  | otherwise = ys : words' rest
                  where (ys, rest) = break (== ' ') xxs

words treats any whitespace as a separator, not just spaces. Use Data.Char.isSpace.

It's fine otherwise.

When reimplementing the standard library, you can exploit the standard version as a reference implementation to compare your version to:

map (\x -> words x == words' x) ["", "  ", "a", "a ", " a", "a  b", "aa bb", "aa\nbb", "a b\nc\td"]


Simple spec testing DSL I wrote a very small little DSL for spec testing:

(ns funky-spec.core)

(def described-entity (ref nil))

(defn it [fun & v]
  (assert (apply fun (cons (deref described-entity) v))))

(def it-is it)
(def it-is-the it)

(defmacro describe [value nest]
  `(dosync (ref-set described-entity ~value)
           ~nest))

(defmacro when-applied [nest]
  `(dosync (ref-set described-entity ((deref described-entity)))
           ~nest))

(defmacro when-applied-to [& args-and-nest]
  `(dosync (ref-set described-entity (apply (deref described-entity) (take (dec (count (quote ~args-and-nest))) (quote ~args-and-nest))))
           (eval (last (quote ~args-and-nest)))))

This turned out to be very nice, for writing some simple, concise specs:

(ns funky-spec.core-test
  (:require [clojure.test :refer :all]
            [funky-spec.core :refer :all]))

(describe 42
  (it = 42))

(describe 99
  (it not= 42))

(describe 0
  (it-is zero?))

(describe 99
  (it-is-the (complement zero?)))

(defn answer [] 42)

(describe answer
  (when-applied
    (it = 42)))

(describe identity
  (when-applied-to 99
    (it = 99)))

(describe +
  (when-applied-to 42 35
    (it = 77)))

(describe +
  (when-applied-to 42 35 9 10
    (it = 96)))

I'm new to Clojure and macros so any thoughts on this code would be appreciated. I have a few concerns that you could start with:

when-applied could (I believe) be an alias for when-applied-to. I can't get this to work with def, is there something I am missing?
Is there a better pattern I could use other than a "global" ref for the described-entity? I tried using let and shadowing, but couldn't get it to work with macros
In when-applied-to , there's a lot of quoting and an eval, I did this to keep it from pre-maturely executing. Is there a cleaner way to thunk it?

This is a case where a dynamic variable is the ideal solution:

(def ^:dynamic *described-entity*)

(defn it [fun & v]
    (assert (apply fun *described-entity* v)))

(def it-is it)
(def it-is-the it)

(defmacro describe [value nest]
  `(binding [*described-entity* ~value]
     ~nest))

(defmacro when-applied-to [& args-and-nest]
  (let [args (butlast args-and-nest)
        nest (last args-and-nest)]
    `(binding [*described-entity* (*described-entity* ~@args)]
       ~nest)))

(defmacro when-applied [nest]
  `(when-applied-to
    ~nest))

Online resources can probably explain dynamic vars better than I can here.  For the purposes here, think of it like your atom except that it's thread local and will restore the original value when the binding context exits.

To use a macro from another macro, you'll want to do it as shown here rather than trying to literally def it in terms of another macro.  The reasons why should probably be saved for when you get a little more macro experience.

And of course, butlast.

In when-applied-to you can do your argument wrangling outside of the macro.  Note though, I'd probably consider passing args in a vector like (when-applied-to [42 35] (it = 77)) to make the arguments more explicit and require less pre-processing.


Binary Search Feedback I have written a binary search algorithm, but it seems to be a bit different than other peoples that I've seen. I was hoping that the community could give me some feedback as to whether or not I'm missing something, or doing something the wrong way.

Binary Search:

import java.util.Arrays;

public class BinarySearch {

    public int[] numbers = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

    /**
     * @param num
     * @param key
     *
     * Function recursively searches sorted array of integers, finding the specific number (key).
     * Search looks at the midpoint of array, checking to see if midpoint is number being sought,
     * if not, depending of whether the sought number is greater than, or less than, the midpoint
     * the function copies the upper, or lower, half of the array and passes it into a recursive
     * function call.
     *
     */
    public int performSearch(int[] num, int key){
        if(num.length == 0){
            System.out.println("Array empty");
            return 0;
        }else{
            int mid;
            int number=0;
            mid = (num.length)/2;
            if(key == num[mid]){
                number =  num[mid];
                System.out.println("Found the number " + number);
                return number;
            }else if((key < num[mid]) && num.length > 1){
                num = Arrays.copyOfRange(num, 0, mid);
                System.out.println("Low Range: " + Arrays.toString(num));
                return performSearch(num, key);
            }else if((key > num[mid]) && num.length > 1){
                num = Arrays.copyOfRange(num, mid, num.length);
                System.out.println("High Range: " + Arrays.toString(num));
                return performSearch(num, key);
            }else{
                System.out.println("Number does not exist in array.");
                return 0;
            }
            //return number;
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int key = 22;
        BinarySearch bs = new BinarySearch();
        int index = bs.performSearch(bs.numbers, key);
        System.out.println("Number " + index);
    }

}

I see 1 bug, 1 problem and 1 minor thing:

as listed in the comment above: You are returning the number instead of the index. That's not very helpful for a binary search algorithm ;)
when the array does not contain the item you are returning 0. 0 is a valid array index, by convention you'd return -1 in that case.
not much of a problem but unnecessary: local variable number in first else block is obsolete.


Multiview for inserting and editing users I have a multiview to insert and edit users. Users are listed in a gridview. In selectedindexchanged event of gridview I've placed this code:

protected void GrvList_SelectedIndexChanged(object sender, EventArgs e)
{
    // EditView
    FrmaddEditUsers.ActiveViewIndex = 1;
    // Get Username
    UserName.Text = GrvList.DataKeys[GrvList.SelectedIndex].Value.ToString();
}

I wonder if it's necessary to change it as below, being afraid of values are changed by bad users:

protected void GrvList_SelectedIndexChanged(object sender, EventArgs e)
{
    // change to EditView
    FrmaddEditUsers.ActiveViewIndex = 1;
    // Get Username from gridview and display in txtbox
    string ToBeEditedUser = GrvList.DataKeys[GrvList.SelectedIndex].Value.ToString();
    UserName.Text = HttpUtility.HtmlEncode(ToBeEditedUser);
}

It certainly wouldn't do any harm and if you users have a backend that does not do something like encode when the user's name goes into the database then this will prevent any nasties.


Pontone styled card game below is a code to play a game of a popular card game, Pontone. you play your game against the dealer. your hand is randomly made and so is the dealers from the set of cards. you play through the normal game of pontone either "hitting" or "sticking". When you finish your play the dealer plays his and the winner is decided at the end.

import random

unused_cards = ['AS','2S','3S','4S','5S','6S','7S','8S','9S','10S','JS','QS','KS','AC','2C','3C','4C','5C','6C','7C','8C','9C','10C','JC','QC','KC','AH','2H','3H','4H','5H','6H','7H','8H','9H','10H','JH','QH','KH','AD','2D','3D','4D','5D','6D','7D','8D','9D','10D','JD','QD','KD']
used_cards = []
player_1_hand = []
dealer_hand = []

this calculates the total of each players hands

def calculate_hand(player):
    global total
    total = 0
    for i in range(len(player)):
        card = player[i]
        if len(card) == 2:
            value = card[0]
        else:
            value = card[:2]

        if value == "A":
            total+=1
        elif value == "J" or value == "Q" or value == "K":
            total += 10
        else:
            total += int(value)

    return total

this part of the code is the dealer playing his hand

def dealer(j):
    global dealer_total
    for i in range(2):
        drawn_card = random.choice(j)
        used_cards.append(drawn_card)
        unused_cards = [f for f in j if f not in used_cards]
        dealer_hand.append(drawn_card)

    dealer_total = calculate_hand(dealer_hand)
    dealer_play = True

    while dealer_play:
        if dealer_total<12:
            drawn_card = random.choice(j)
            used_cards.append(drawn_card)
            unused_cards = [f for f in j if f not in used_cards]
            dealer_hand.append(drawn_card)

        elif dealer_total<=12 and dealer_total<16:
            determine_hit = random.randrange(2)
            if determine_hit == 1:
                drawn_card = random.choice(j)
                used_cards.append(drawn_card)
                unused_cards = [f for f in j if f not in used_cards]
                dealer_hand.append(drawn_card)

            else:
                dealer_play = False

        dealer_play = False

        dealer_total = calculate_hand(dealer_hand)

    if dealer_total > 21:
        dealer_win = False
    else:
        dealer_win = True

    print(dealer_hand)
    return dealer_win

this part draws the original hand for the player

def drawhand(j, player):
    global stick

    for i in range(2):
        drawn_card = random.choice(j)
        used_cards.append(drawn_card)
        unused_cards = [f for f in j if f not in used_cards]
        player.append(drawn_card)

    stick = False

    print(player)
    player_total = calculate_hand(player)

this is the main game loop where you play the game.

def gameloop(j):
    global stick
    global dealer_total

    win = True
    drawhand(j, player_1_hand)
    while not stick:
        play = input("stick or hit")

        if total == 21:
            print("pontone")
            stick = True

        if play == "stick":
            stick = True

        elif play == "hit":
            draw_card = random.choice(j)
            used_cards.append(draw_card)
            unused_cards = [j for j in j if j not in used_cards]
            player_1_hand.append(draw_card)
            player_total = calculate_hand(player_1_hand)
            print(player_1_hand)

            if total == 21:
                print("pontone")
                stick = True
            elif total>21:
                print("bust")
                win = False
                stick = True

    player_total = calculate_hand(player_1_hand)

    dealer_win = dealer(j)

    if (dealer_total <= player_total and win != False) or dealer_win == False:
        print("you win")
    else:
        print("you lose")

gameloop(unused_cards)

If you have any ways on how to improve this please share.

The improvement I would like to suggest you deals with the big picture of your program rather than its details: the functions dealer() and gameloop() (which is far from being a good function name) are long. This makes them difficult to test and they certainly, among other things (as explained briefly here), violate the single responsibility principle.


Searching for bad Minecraft questions on Gaming.SE To preface this post a little bit, I'll explain a little bit of the "backstory" here. The Stack Exchange site, Gaming.SE, also known as Arqade, often has a large influx of bad questions about the popular video game, Minecraft. Many of these questions are either easy to find on a search engine, horribly unclear, have been asked before, are treating Arqade like a forum, or are asking for things like account support, which only the company that produces the game can provide. A few examples might include:

  what is the best biome to spawn in minecraft
  Can't Log In To Minecraft Account After 1.9
  No .Minecraft folder at school
  What I need to make TNT?
  How to Spawn Herobrine without Mods?

The query essentially searches in a manner like this:

It looks for questions with tags that are like %minecraft% or %minecraft-%%.
It checks to see if it has a score below -1.
It checks to make sure that the post hasn't already been deleted.
It checks to see if it's either been closed, or not closed.

I'd like to know the following things:

Is there a way to make this shorter and less repetitive?
Are there any redundant checks that aren't needed?
Are there any checks that could cause problems?
Anything else?

Here's the code, and the query link:

SELECT
    Id AS [Post Link]
  , OwnerUserId AS [User Link]
  , Score
FROM Posts WHERE
  DeletionDate IS NULL
  AND Score <= -1
  AND (
    Tags LIKE '%minecraft-%%'
    OR Tags LIKE '%minecraft%'
  )
  AND (
    ClosedDate IS NULL
    OR ClosedDate IS NOT NULL
  );

SELECT
  COUNT(*)
FROM Posts WHERE
  DeletionDate IS NULL
  AND Score <= -1
  AND (
    Tags LIKE '%minecraft-%%'
    OR Tags LIKE '%minecraft%'
  )
  AND (
    ClosedDate IS NULL
    OR ClosedDate IS NOT NULL
  );

The use of the Tags field on the Post is a poor choice for the query. It relies on a table scan, which is slow, because it has to check each question. Note, you can use the < and > characters to identify tag start and end values in the Tags column, but, as I say, don't use that column.

Instead, you should do a join with the PostTags and Tags tables. Using a CTE to simplify that query makes sense.

I really dislike the all-caps style of SQL, but realize that there is no standard. If you can change standards, please use lower-case for keywords... it makes the column and table names much easier to see (and those are the important parts). Still, you get +1 for being consistent in your capitalization. Consistency is really important, and you nailed it.

Note that the Posts table has no deleted posts, none. There's no need to check the DeletedDate at all.

So, joining Tags to PostTags gets you minecraft-tagged posts. Joining that to Posts gets you the ones you can test scores and closures on.

Here are unclosed, low-scoring, minecraft-related posts....:

WITH mctags AS (
  SELECT Id AS tid
  FROM Tags
  WHERE TagName LIKE 'minecraft%'
), mcqs AS (
  SELECT DISTINCT PostId
  FROM PostTags INNER JOIN mctags ON TagId = tid
)
SELECT
    Id AS [Post Link],
    OwnerUserId AS [User Link],
    Tags,
    Score
FROM Posts
INNER JOIN mcqs ON Id = PostId
WHERE Score <= -1
  AND ClosedDate IS NULL
  AND PostTypeId = 1

Note, I have tried to continue using your all-caps keywords.... despite myself ;-)

Hmmm, some aditional notes:

your text says you check for questions "below -1", but your code checks for questions "below 0" ... there is a difference between < and <=.
it does not check the closed-status of the post. If you want to see if a currently-open post was closed in the past, you need to check the PostHistory table.


Is checking for null redundant while using Contract Annotator from JetBrains? I'm curious whether checking for null is redundant in this concrete example.

 public LoginJob(@NotNull String login, @NotNull String password) {
        super(new Params(Priority.NORMAL).requireNetwork().persist());
        Preconditions.checkNotNull(login, "login is null or empty");
        Preconditions.checkNotNull(password, "password is null or empty");

        this.login = login;
        this.password = password;
    }

Please notice I'm using Contract Annotator from JetBrains, so the User of a Class warned the LoginJob constructor can't take null values, it can't prevent him/her of doing so though.

You said it yourself in your question :

  it can't prevent him/her of doing so though.

That settle it for me. You still have the responsibility to prevent that null value are pass to your classes. The annotation seems to be about preventing NullPointerException. So you should be checking for null values even if you use @NotNull.

    Preconditions.checkNotNull(login, "login is null or empty");
    Preconditions.checkNotNull(password, "password is null or empty");

Your message or the method you use is lying. The method is called checkNotNull but you warn about empty String, this is two very different things. Either you should modify you message to inform that you're only checking null values or you could change/rename the method checkNotNull to better represent the empty check.


sorting vector of pair in efficient way I'm trying to solve the sorting problem but I always get TLE(Time Limit Exceeded/ 1s) so... can you guys suggest a more efficient way to solve this problem?
(i can't link the exercise because it is on the closed server)
code reads test count t , <int, string>   pairs then sorts by integer in ascending order and prints median
#include <bits/stdc++.h>
using namespace std;
 int main(int argc, char *argv[]) {
   vector< pair <int,string> > median;
   int t;  cin >> t;
   int num; string name;
   for(int i=0;i<t;i++) {
     cin>>name; cin>>num;
     median.push_back( make_pair(num,name));
   }
  sort(median.begin(), median.end());

    if(t%2!=0){
      cout << median[t/2].second << " " << median[t/2+1].first << endl;
    }else{
      cout << median[t/2-1].second << " " << median[t/2+1].first << endl;
      cout << median[t/2].second << " " << median[t/2+1].first << endl;

        }
 }

input:
Gilbert 35
Anna 35
Anna 15
Mary 15
Joseph 40

output:
Anna 35

I don’t do programming challenges, so my review will be more from the point of view of actually writing decent C++ rather than the programming challenge mindset (which, in my humble opinion, encourages terrible coding practices). Nevertheless, if it’s performance you want, I can give you some tips on how to get some huge speed increases.
So let’s dive in.
#include <bits/stdc++.h>

I’ve heard this is standard practice in programming challenge circles. Nevertheless, it is terrible practice in real life. Instead, look at all the standard library components you use, and include the headers for them. In your case, you use cin/cout, vectors, strings, pairs, and the sort function, so you’ll need their headers. Including only those headers should speed up compilation measurably, but I don’t know if compilation time is counted in total time, so I don’t know how much that will help.
using namespace std;

Never do this, even in a programming challenge. It’s just a terrible habit that will eventually bite you in the ass. Just put std:: where needed. Just get used to it.
int main(int argc, char *argv[]) {

Since you don’t actually read the command line, you can just use the simpler form of main().
Now you’ve packed your entire program into main(). That’s okay for this very trivial program, but you should really get in the habit of writing better code. Isn’t that what programming challenges are for, after all?
Break the program into logical steps, and put each major step into its own function. It costs nothing; even the most basic level of optimization will eliminate all the overhead (and anything it doesn’t isn’t worth eliminating).
The first step is to read the number of pairs in the data set… so it should be a function  called read_dataset_size(), or something like that. It could look something like this:
auto read_dataset_size() -> int;

Or, even better, take the input stream as a parameter:
auto read_dataset_size(std::istream&) -> int;

Why would you do that? Because it makes the function easier to test. You should always program with testing in mind, even for off-the-cuff code like this. Because if something doesn’t work—and we all make stupid mistakes—you want to be able to do tests to figure out what the problem is. With the function written like above, you can read the input from a file, or even directly from memory, and see whether you get the expected result.
So, refactored that way, the read_dataset_size() function looks like this:
auto read_dataset_size(std::istream& in) -> int
{
    int t;  in >> t;

    return t;
}

(This is just your code exactly as you’ve written it, except I replaced cin with in. And of course, added the return statement.)
Now, you should never write two statements on a single line. Space costs nothing, but being able to read code clearly is the difference between having silly hidden bugs or not. So:
auto read_dataset_size(std::istream& in) -> int
{
    int t;
    in >> t;

    return t;
}

Even better would be to give clear names to the variables:
auto read_dataset_size(std::istream& in) -> int
{
    int size;
    in >> size;

    return size;
}

Normally you’d do error checking to make sure you actually read a proper number and all… but okay, I get this is just challenge code. So we’ll skip the error checking.
That’ll do for this bit.
Your next function should be something like read_data_pairs() or something. It should look something like this:
auto read_data_pairs(std::istream&, int) -> std::vector<std::pair<int, std::string>>;

And with your code refactored into it:
auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
    std::vector< std::pair <int,std::string> > median;

    int num; std::string name;
    for(int i=0;i<size;i++) {
        in>>name; in>>num;
        median.push_back( std::make_pair(num,name));
    }

    return median;
}

(Note this is exactly your code with the std::s added, cin replaced with in, and t replaced with size, and of course the return statement added.)
Alright, now let’s talk performance.
Here’s the problem: vector automatically resizes to accommodate more data. When it does, it has to allocate a new chunk of memory (usually twice the size of the existing capacity), and then copy all the old data into the new memory. If there are 1,000 pairs in the vector, then the vector would have to allocate space for 2,000 pairs, and then do 1,000 copies (technically, moves). In modern C++, that all happens very quickly… but it’s still not free; there’s still a cost. And if you’ve got millions of pairs….
Even worse, it will probably happen many, many times as you read in the data. Your vector will start empty, and then have to allocate space for a couple elements. You’ll read in a couple elements, then run out of space again… so the vector will have to allocate a new block of memory, and copy everything over. Now you’ll read in a few more elements… but soon run out of space again. So the vector will have to reallocate and copy again. And it will have to do it over and over and over. And as the number of elements becomes huge, all that allocating and copying will add up quickly.
Here’s the key to fixing that problem. You already know the size of the input data. So you can just pre-allocate all the space you need, and avoid the need for all that reallocation and copying. The technically correct way would be to do this:
auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
    std::vector< std::pair <int,std::string> > median;  // median probably
                                                        // isn't a great name
                                                        // for this variable,
                                                        // because it isn't
                                                        // the median... it's
                                                        // all the input data
                                                        //
                                                        // maybe call it
                                                        // "pairs" instead?

    median.reserve(size); // this is the magical line that will probably fix
                          // all your performance problems

    int num;
    std::string name;
    for(int i=0; i < size; ++i)
    {
        in >> name;
        in >> num;

        median.push_back( std::make_pair(num,name));
    }

    return median;
}

That one line alone will probably fix your timeout errors.
But we can do even better.
Although we’re reserving all the memory we’re going to need, we’re still pushing elements on to the vector. Now it is going be very quick… but, again, still not free.
So instead of just reserving space and then pushing elements in to the vector over and over… why not create the elements right away, and then read the data directly into them? No extra copies needed.
This is technically not good practice in general… but it is a valid hack for efficiency. And efficiency is what you’re gunning for.
So:
auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
    std::vector<std::pair<int,std::string>> median;

    median.resize(size);    // note: reSIZE, not reSERVE
                            // this will fill the entire vector with the
                            // right number of pairs in a single shot

    // note: no more need for temporaries to read input!
    // we'll be reading *directly* into the proper place

    // note: we can use the much safer range-for loop now
    for (auto&& element : median)
    {
        in >> element.first;
        in >> element.second;
    }

    return median;
}

That’s about as fast as that can be, I think.
The sorting is just a call to std::sort()… not much we can do to improve that, or speed that up.
Now, the way the output is printed is a bit weird. Why do you do median[t/2].second and then median[t/2+1].first? Are you sure that’s correct? Have you tested it with more data than what is shown? (Seriously, TEST YOUR CODE!!! That’s the biggest thing that separates the shitty coders from the good ones. You should test your code with multiple data sets, including edge cases likely to cause problems (like a 1-element data set, for example).)
I have a hunch you have a bug, but can’t be sure because you haven’t given the actual program requirements. So I’m just going to assume your code isn’t broken (but I think it is!).
Now, the output could be slightly faster. Instead of:
cout << median[t/2].second << " " << median[t/2+1].first << endl;

You could do:
std::cout << median[t / 2].second << ' ' << median[(t / 2) + 1].first << '\n';

There are two things I changed (other than the spacing to make it more readable, and adding the std::):

The space is now a single character, rather than a string. In theory, this should be much faster, because a single character is a single character… while a string requires reading multiple characters with a loop and a conditional (to search for the NUL). (In reality, the compiler probably optimizes this for you anyway.)
Don’t use std::endl. std::endl prints a newline… and then flushes the stream, which is expensive. The stream is going to be flushed automatically anyway, so there’s no sense paying for it multiple times.

There’s one final trick I can think of that might gain you a bit more speed: std::ios::sync_with_stdio(false);. This is a high-level trick, but with a cost: if you do this, you cannot use any of the C stdio library. That means no printf(), no fopen(), none of that. What’s going on is that, by default, the C++ I/O streams will synchronize with the C stdio streams. This is a handy convenience that allows you to mix std::cout and printf(). BUT! That comes with a heavy cost. It slows down std::cin and std::cout a LOT. If you never use any C stdio stuff, then you can turn that synchronization off, and get a huge performance boost. It might make a difference for you, or it might not. Either way, just stick std::ios::sync_with_stdio(false); right after the beginning of main().
Okay, in summary, I think the reason you’re getting timeouts is all due to the way you’re reading the input. By not pre-allocating the vector, it is forced to constantly re-allocate and copy (move) all of its contents, over and over and over. Just be pre-allocating the vector with reserve(), you will spare yourself all that wastage by doing one single allocation, and avoiding all the copying (moving) entirely. Even better, you can just size the vector one time up front, and then read the data directly into its elements, so now you don’t even need to read into temporaries then copy into the vector.
Adding std::ios::sync_with_stdio(false); may help, too.
But most importantly: TEST YOUR CODE!!! I think you have a bug. You say your code works, so I assume you know what you’re doing… but I’m still skeptical. TEST YOUR CODE!!! See for yourself whether it really works the way you think it does. You just need simple tests, like this (using the Catch2 test framework):
TEST_CASE("dataset size is read correctly")
{
    auto const test_data = R"(
3
1 Alice
2 Bob
3 Carol
)";

    auto iss = std::istringstream{test_data};

    CHECK(read_dataset_size(iss) == 3);
}

TEST_CASE("simple data is read correctly")
{
    auto const test_data = R"(
3
1 Alice
2 Bob
3 Carol
)";

    auto iss = std::istringstream{test_data};

    // just assume this works and throw the result away, because it is tested
    // in the other test case
    [[maybe_unusued]] auto const data_size = read_dataset_size(iss);

    auto const data = read_data_pairs(iss, 3);

    CHECK(data.size() == 3);

    CHECK(data.at(0) == "Alice");
    CHECK(data.at(1) == "Bob");
    CHECK(data.at(2) == "Carol");
}

Then you just need a couple more tests to make sure sorting produces the right result, and that you print the right output for the median. After that, you could add more tests with different test data to test different potential problems. Get in the habit of testing your code. You may even find benefits with this very program….


Reading a CSV file containing a dataset of 8×8 images I am trying to implement a machine learning algorithm (k-nn for example).  But before I attempt to do that I was hoping for some feedback on my current Main class, which essentially builds 8×8-pixel matrices into an array to be manipulated later. (See the data description and sample dataset.)

import java.util.*;
import java.io.*;

public class Main {

    static class Data {

        int[] dataSet;
        int classCode;

        public Data(int[] dataSet, int label) {
            this.dataSet = dataSet;
            this.classCode = label;
        }

        @Override
        public String toString() {
            return "Class Code: " + classCode + " DataSet:" + Arrays.toString(dataSet) + "\n";
        }

    }

    ArrayList<Data> dataSetList;
    int[][] dataArray = new int[2810][65];

    private void readFile(String csvFile) {
        int instances = 0;
        dataSetList = new ArrayList<>();
        try {
            Scanner scan = new Scanner(new BufferedReader(new FileReader(csvFile)));
            while (scan.hasNext()) {
                String line = scan.next();
                String[] extractedDataFromFile = line.split(",");
                for (int i = 0; i < extractedDataFromFile.length; i++) {
                    dataArray[instances][i] = Integer.parseInt(extractedDataFromFile[i]);
                }
                dataSetList.add(new Data(dataArray[instances], dataArray[instances][extractedDataFromFile.length - 1]));
                instances++;
            }
            System.out.println(dataSetList.toString());
        } catch (FileNotFoundException ex) {
            System.out.println(ex.getMessage());
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.readFile("dataset1.csv");
    }

}

This is my first time experimenting with machine learning and any feedback on my current approach as well as an algorithm to look at beyond this would be hugely appreciated.

Outline

Data and Main aren't exactly helpful class names.  I suggest ImageMatrix and ImageMatrixDB.

In some sense, your code is incomplete, because it just prints the data that it read.  To make this code useful, you would have to offer a way to retrieve the data — and not just by directly accessing dataSetList and dataArray, which should have been private.  I suggest the an outline like this:

ImageMatrix.java

public class ImageMatrix {
    public ImageMatrix(int[] data, int classCode) {
        assert data.length == 64;
        …
    }

    public int[] getData() {
        …
    }

    public int getClassCode() {
        …
    }
}

ImageMatrixDB.java

public class ImageMatrixDB implements Iterable<ImageMatrix> {
    private List<ImageMatrix> list = new ArrayList<>;

    public static ImageMatrixDB load(File f) throws IOException {
        …
    }

    public Iterator<ImageMatrix> iterator() {
        return this.list.iterator();
    }
}

Why are you storing the same data twice, in both dataSetList and dataArray?  You should drop the dataArray, which relies on the magic number 2810.

The file parameter should be a File rather than a String, so as not to give the impression that you it accepts the contents of the file rather than the name of the file.

The parsing routine needs a way to report failure to its caller.  No, printing an error message doesn't count, as the caller would still proceed obliviously.

Implementation

Why are you using a Scanner?  The BufferedReader already has a readLine() method that does what you want.  Note that you fail to close the FileReader, BufferedReader, and the Scanner.

In the Data object, the dataSet array has 65 elements: the 64 data points and the class code.  The class code has no business being part of that array.

public static ImageMatrixDB load(File f) throws IOException {
    ImageMatrixDB result = new ImageMatrixDB();
    try (FileReader fr = new FileReader(f);
         BufferedReader br = new BufferedReader(fr)) {
        for (String line; null != (line = br.readLine()); ) {
            int lastComma = line.lastIndexOf(',');
            int classCode = Integer.parseInt(line.substring(1 + lastComma));
            int[] data = Arrays.stream(line.substring(0, lastComma).split(","))
                               .mapToInt(Integer::parseInt)
                               .toArray();
            result.list.add(new ImageMatrix(data, classCode));
        }
    }
    return result;
}


Structuring a JSON array with objects I have a JSON array or literal (passes through JSON.parse).

Requirement: an array of tasks which contains operations which are key/value pairs.

Array of tasks > Array of operations (array of operations at times will contain duplicate key/value pairs)

[
    [
          {
            resize: [1200, 1200]
          }, {
            moveTo: "dest/nick"
          }, {
            rename: "{base}-12.{ext}"
          }, {
            toWeb: true
          }, {
            rename: "{base}.{ext}"
          }
        ], [
          {
            resize: [1000, 1000]
          }, {
            rename: "{base}-10.{ext}"
          }
        ]
      ]

The code works and I simply want to know if there is a better way of doing this. I had to wrap the individual operations with {} so that the duplicate keys wouldn't overwrite each other.

I think I would replace { resize: [1200, 1200] } with { operation: 'resize', parameters: [1200, 1200] }. This is more verbose, but easier to maintain/read. This way it's eligible for extension (maybe you want to add identifiers later?). The same can be done for the tasks.

Other than that there's not a lot to say. I find the indentation not easily readable, but that's just style. I'd prefer:

[
    {
        name: "I'm task one",
        operations: [
            {
                operation: "resize",
                parameters: [1200, 1200]
            },
            {
                operation: "moveTo",
                parameters: ["dest/nick"]
            },
            {
                operation: "rename"
                parameters: ["{base}-12.{ext}"]
            },
            {
                operation: "toWeb",
                parameters: [true]
            },
            {
                operation: "rename",
                parameters: ["{base}.{ext}"]
            }
        ]
    },
    {
        name: "I'm task two",
        operations: [
            {
                operation: "resize",
                parameters: [1000, 1000]
            },
            {
                operation: "rename",
                parameters: ["{base}-10.{ext}"]
            }
        ]
    }
]

Also note that the value of the parameters is an array, even if it has one value.