Hackerrank Luck Balance solution in C++ I solved the Hackerrank Luck Balance problem the "C" way (I am much more used to C) and I wanted to know if there were any C++ features I could have used that would have made my code more concise/neater. That's it! Any other criticism is welcome, of course.

All the stuff that I wrote is in the LuckBalance() function. Pay no attention to anything else - that was provided by the challenge (which wasn't really a challenge)

  Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. She believes in "saving luck", and wants to check her theory. Each contest is described by two integers, \$L[i]\$ and \$T[i]\$. \$L[i]\$ is the amount of luck associated with a contest. If Lena wins the contest, her luck balance will decrease by \$L[i]\$; if she loses it, her luck balance will increase by \$L[i]\$.

  \$T[i]\$ denotes the contest's importance rating. It's equal to \$1\$ if the contest is important, and it's equal to \$0\$ if it's unimportant.

  If Lena loses no more than \$k\$ important contests, what is the maximum amount of luck she can have after competing in all the preliminary contests? This value may be negative.

Note that the k parameter in the luckBalance function is the maximum number of important contests Lena can lose, and the vector<vector<int>> contests input is a column vector of \$L[i]\$ along with a column vector of \$T[i]\$.

#include <bits/stdc++.h>
#include <stdlib.h>

using namespace std;

vector<string> split_string(string);

// Complete the luckBalance function below.
int luckBalance(int k, vector<vector<int>> contests) {

    int totalLostLuck = 0;
    int totalGainedLuck = 0;
    int totalRegainedLuck = 0;
    vector<int> regainedLuck(k, 0);

    for(int i = 0; i < contests.size(); i++)
    {
        if(contests[i][1] == 1)
        {
            totalLostLuck += contests[i][0];
            for(int j = 0; j < k; j++)
            {
                // Choose to win the contests that have the greatest
                // amount of luck
                if(regainedLuck[j] < contests[i][0])
                {
                    regainedLuck[j] = contests[i][0];
                    sort(regainedLuck.begin(), regainedLuck.end());
                    j = k;
                }
            }
        }
        // If it is a non-important contest, we get the luck for free!
        else
        {
            totalGainedLuck += contests[i][0];
        }
    }

    for(int i = 0; i < k; i++)
    {
        totalRegainedLuck += regainedLuck[i];
    }

    return totalGainedLuck - totalLostLuck + (2*totalRegainedLuck);
}

int main()
{
    //ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    vector<vector<int>> contests(n);
    for (int i = 0; i < n; i++) {
        contests[i].resize(2);

        for (int j = 0; j < 2; j++) {
            cin >> contests[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    int result = luckBalance(k, contests);

    cout << result << "\n";

    //fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

The algorithm should be:

Lose any unimportant contest where doing so does not lose luck.
Win any contest where doing so does not lose luck.
Lose the up to k contests where winning would cost most luck.

At the moment, you assume winning never gains luck and losing never loses luck.

You do a full sort each iteration for point 3, which with a cost of \$O(k*\log(k))\$ leads to \$O(n*k*\log(k))\$.
Using a fixed-length priority-queue instead only needs \$O(\log(k))\$ per insert / replace, resulting in \$O(n*\log(k))\$, a factor of \$k\$ better.
While C++ doesn't have exactly that, <algorithm> provides pop_heap() and push_heap() which is enough to replace the head if the new item is less expensive. A custom replace_heap() or exposed down_heap() would be slightly more efficient, but for that you have to branch out.

Now the form:

<bits/stdc++.h> is non-standard and likely far more than you actually need. Unless coupled with use of precompiled headers, it will slow down compilation at least, if not bloat the resulting executable. Replace it with the standard includes. See "How does #include <bits/stdc++.h> work in C++?".
Never import wholesale any namespace which isn't designed for it. Doing so leads to conflicts, silent changes of behaviour, and generally brittle code. See "Why is “using namespace std” considered bad practice?".
Don't use a std::vector if all you need is an array of statically-known length.
Such overkill costs. Anyway, a std::tuple<int, bool> or std::pair<int, bool> would be an even better fit.
If one can rely on anything, it's that if there is a way to screw something up, it will be done, at the most inconvenient time. Like the input. As it is under the coders control, it isn't quite a fatal defect though.
return 0; is implicit for main().
Small trivial types like char should not be passed by constant reference without good reason, but by value. Doing so avoids the pitfalls of aliasing, and is slightly more efficient. Happily, the compiler should fix that by inlining.
Getting and storing input in the loop-condition is actually idiomatic. And it avoids error-prone repetition.
This:

size_t i = 0;
size_t pos = input_string.find(delimiter);

while (pos != string::npos) {
    splits.push_back(input_string.substr(i, pos - i));

    i = pos + 1;
    pos = input_string.find(delimiter, i);
}

Could simply be:

for (size_t i = 0, pos; (pos = input_string.find(delimiter, i)) != string::npos; i = pos + 1)
    splits.push_back(input_string.substr(i, pos - i));

The final call to .substr() needlessly contains a complicated calculation for the second argument. Just leaving it out will do the right thing.

splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

As an aside, split_string() would be better off accepting a std::string_view and returning a std::vector<std::string_view>. Less allocation-overhead.
There is no reason to pass the contests by copy. Either move them, pass a constant reference, or preferably use a std::span (C++20 or GSL (Guideline Support Library)).
Yes, there's no need to forward-declare functions defined before first use, which is a good thing. But above all, please try to be consistent which option you use.

Finally your code:

There's no reason at all to keep track of parts of the result-sum separately. Just combine them already.
Using auto instead of explicit types avoids errors and reduces clutter. Thus, almost always auto. That also counts for the form.

The rest was handled in the algorithm section.

Using the better algorithm:

int luckBalance(int k, vector<vector<int>> contests) {
    // Keeping the bad interface because they force it
    auto r = 0;
    const auto heap = std::make_unique<int[]>(k);
    for (const auto& x : contests) {
        if (!x[1] || x[0] <= heap[0]) {
            r += std::abs(x[0]);
        } else {
            std::pop_heap(heap.get(), heap.get() + k, std::greater());
            r -= heap[k - 1];
            heap[k - 1] = x[0];
            std::push_heap(heap.get(), heap.get() + k, std::greater());
        }
    }
    return r;
}

Could be improved by not pre-filling the heap with zeroes, but I'm too lazy.


What is this structure called? I've been writing this data structure for a few days, and now I'm really curious about what it actually is, and to get some critique on my logic.

A branch, based on this usage, exists when a HEAD node contains at least one node of the same type referenced.

The purpose of the structure is to have branches that are arranged by type. Each node on the branch has a reference to the next node on the branch (always of the same type) and an entry point to a Subdata branch. Subdata in this case being an instance of a class that inherits from the AchievementNode. When subdata is added and it is the first of it's kind on that branch it has the HEAD tag applied to it, additionally, it also has a tag that contains the metadata of the type of data contained (to bypass the typeof calls).

Implementation:

public abstract class AchievementNode : ScriptableObject
{
    public enum NodeTypes
    {
        NONE   = 0x0,
        HEAD   = 0x1,
        TAIL   = 0x2,
        TYPE   = 0x4,
        DATA   = 0x8,
        LEVEL  = 0x16,
        GLOBAL = 0x32
    }

    public NodeTypes nodeType;

    public AchievementNode nextOfType;

    public AchievementNode headOfSubnode;

    public void OnEnable ()
    {
        hideFlags = HideFlags.HideAndDontSave;
    }

    public virtual void Init(NodeTypes type, int enumData)
    {
        nodeType = type;
    }

    protected void AddNode(NodeTypes type, AchievementNode originNode, AchievementNode newNode)
    {
        //Create SubNode branch notch when types mismatch.
        if((originNode.nodeType & type) != type)
        {
            //If Has subNode Data Run to the end and assign new node
            if(originNode.headOfSubnode!=null)
            {
                newNode.nodeType = type | NodeTypes.TAIL;
                AppendToTail(type,GetEndOfBranch(originNode.headOfSubnode),newNode);
            }//Search for proper SubNodeTypes then add. Wicked Recursion warning here...
            else if((originNode.headOfSubnode.nodeType & type) != type)
            {
                Debug.LogError("Do Gnarly Search To Find!");
                return;
            }//Doesn't have subnode... add new Subnode.
            else
            {
                newNode.nodeType = type | NodeTypes.HEAD | NodeTypes.TAIL;
                originNode.headOfSubnode = newNode;
            }
        }
        else
        {
            //Add to the current branch
            newNode.nodeType = type | NodeTypes.TAIL;
            AppendToTail(type,GetEndOfBranch(originNode),newNode);
        }
    }

    private void AppendToTail(NodeTypes type,AchievementNode tailNode, AchievementNode newNode)
    {
        if((tailNode.nodeType & NodeTypes.HEAD) == NodeTypes.HEAD)
        {
            tailNode.nodeType = tailNode.nodeType | type;
        }
        else
        {
            tailNode.nodeType = type;
        }
        tailNode.nextOfType = newNode;
    }

    protected AchievementNode GetEndOfBranch(AchievementNode currentNode)
    {
        //Special Case where Node is HEAD and TAIL.
        if((currentNode.nextOfType.nodeType & NodeTypes.TAIL) != NodeTypes.TAIL)
        {
            return GetEndOfBranch(currentNode.nextOfType);
        }
        else
        {
            return currentNode;
        }
    }

    protected void SetType(NodeTypes type)
    {
        nodeType = type;
    }

    protected virtual AchievementNode FindInHierarchy(NodeTypes nodeCheck, AchievementNode currentNode)
    {
        if(currentNode == null)
        {
            return null;
        }
        else if((currentNode.nodeType & nodeCheck) == nodeCheck)
        {
            return currentNode;
        }
        else
        {
            return FindInHierarchy(nodeCheck,currentNode.nextOfType);
        }
    }
}

Why do you have HEAD and TAIL NodeTypes? Doesn't their position on the branch tell you that?
I'm concerned that you have structure traversal code infused into AchievementNode class. Classically the structure - tree, queue, List, etc. - is independent of the objects it holds. I would think greatly upon using something like Dictionary<T>, List<T>, etc. Use that structure's inherent reference/traversal features in the context of NodeType. - wrapping (inheriting?) that structure along with your concept of NodeType into a class that is essentially a MyNodes<AcheivementNode> class. I wonder, is MyNodes<NodeType> what you are really building? In any case I suspect the separation of concerns will make the NodeType idea standout better conceptually and architecturally.
How many palaces do you have NodeType defined I wonder. Why is NodeType enum defined inside AchievementNode? That's unusual. You want it hidden from client code? I don't think so since you have method parameters of NodeType.


Simple use of mouse clicks to position a ball Here's a simple program I wrote to teach myself the basics of using a mouse for a potential HTML5/JavaScript game. The thing that tripped me up was event.clientX and event.clientY don't return the correct values as they stand. One has to get the offsets of the canvas object, which in turn may be a child object of other objects whose offsets need to be obtained...

I found this a bit counter intuitive. If anyone has more elegant solutions, I'd be interested to learn about them.

var canvas, context, ball_pos;

var BALL_RADIUS = 15;

function start() {
    'use strict';
    canvas = document.getElementById('c');
    context = canvas.getContext('2d');
    ball_pos = [canvas.width / 2, canvas.height / 2];
}

function draw() {
    'use strict';

    // draw background
    context.fillStyle = "rgb(248,248,248)"; // off white
    context.fillRect(0, 0, canvas.width, canvas.height);

    // draw ball
    context.strokeStyle = 'black';
    context.lineWidth = 1;
    context.fillStyle = 'red';
    context.beginPath();
    context.arc(ball_pos[0], ball_pos[1], BALL_RADIUS, 0, Math.PI * 2, true);
    context.closePath();
    context.fill();
    context.stroke();
}

function animate() {
    'use strict';
    window.requestAnimationFrame(animate);
    draw();
}

function click(evt) {
    'use strict';
    var offset = [0, 0],
        obj = canvas;
    while (obj.offsetParent !== null) {
        offset[0] += obj.offsetLeft;
        offset[1] += obj.offsetTop;
        obj = obj.offsetParent;
    }
    ball_pos[0] = evt.clientX - offset[0];
    ball_pos[1] = evt.clientY - offset[1];
}

// register event handlers
window.onclick = click;

start();
animate();
<html>
<head>
  <meta charset="utf-8">
</head>
<body>
  <canvas id="c" width="600" height="400"></canvas>
</body>
</html>

You can get the bounding rectangle for a canvas. Consider:

function click(evt) {
    'use strict';
    var bound = canvas.getBoundingClientRect();
    ball_pos[0] = evt.clientX - bound.left;
    ball_pos[1] = evt.clientY - bound.top;
}

This should help you to avoid walking up the stack of objects to find the relative position.

See it working here:

var canvas, context, ball_pos;

var BALL_RADIUS = 15;

function start() {
    'use strict';
    canvas = document.getElementById('c');
    context = canvas.getContext('2d');
    ball_pos = [canvas.width / 2, canvas.height / 2];
}

function draw() {
    'use strict';

    // draw background
    context.fillStyle = "rgb(248,248,248)"; // off white
    context.fillRect(0, 0, canvas.width, canvas.height);

    // draw ball
    context.strokeStyle = 'black';
    context.lineWidth = 1;
    context.fillStyle = 'red';
    context.beginPath();
    context.arc(ball_pos[0], ball_pos[1], BALL_RADIUS, 0, Math.PI * 2, true);
    context.closePath();
    context.fill();
    context.stroke();
}

function animate() {
    'use strict';
    window.requestAnimationFrame(animate);
    draw();
}

function click(evt) {
    'use strict';
    var bound = canvas.getBoundingClientRect();
    ball_pos[0] = evt.clientX - bound.left;
    ball_pos[1] = evt.clientY - bound.top;
}

// register event handlers
window.onclick = click;

start();
animate();
<html>
<head>
  <meta charset="utf-8">
</head>
<body>
  <canvas id="c" width="600" height="400"></canvas>
</body>
</html>


Write MD5 hashes to file for all files in a directory tree I'm ultimately trying to compare the MD5 hashes for files in two disparate directory trees to see if files are missing from one directory or the other.

More broadly, I'm pushing photos from my DSLR camera to Google Drive, and need to know which files need to be synced up. Pictures from my phone are automatically being synced with Google Drive, and I'd also like to detect which ones I need to sync down. I have separate scripts for getting the MD5 hashes from Google Drive and for comparing the MD5 hashes to see which files need to be synced, up or down.

#!/usr/bin/python

import os
import sys
import hashlib
import csv

src_dir = '/Volumes/Archive/Pictures'

with open('checksums_archive.tsv', 'wb') as fout:
    writer = csv.writer(fout, delimiter='\t', quotechar='\"', quoting=csv.QUOTE_MINIMAL)

    for root, subdirs, files in os.walk(src_dir):
        for file in files:
            file_path = os.path.join(root, file)
            checksum = hashlib.md5(open(file_path, 'rb').read()).hexdigest()

            writer.writerow([root, file, checksum])

Four things:

You should put global constants in CAPITAL_LETTERS, according to PEP8.
I would make the file_name for the checksums a constant
You never close the files you iterate over.
In general, doing all writes at the same time is faster.

So for 2, 3 & 4, maybe use:

for root, subdirs, files in os.walk(SRC_DIR):
    checksums = []
    for file in files:
        with open(os.path.join(root, file), 'rb') as _file:
            checksums.append([root, file, hashlib.md5(_file.read()).hexdigest()])
    writer.writerows(checksums)

This will perform one write per subdir, which should be faster than a write after every file. If you have a lot of files this will take more memory, which should be slightly mitigated by doing a write for each subdir. You can even pull the checksums list outside of the os.walk loop to have only one (possibly giant) write.

Otherwise, clear and readable code!


Wrapping a character code for a Caesar Cipher I'm writing a Caesar Cipher. To deal with characters being shifted to outside of the "normal" printable ASCII range ([32 126]), I'm having them "wrapped" to the max/min in the range.

My current solution works, but it has a couple issues:

It involves a couple repeated lines. The (- max-code (rem (- max-code char-code) code-range)) part is basically the same in both places, just with a few minor differences. If I really wanted to reduce repetition, I could bind a function that encapsulated the similar parts, and pass in the parts that vary, but I can see that being overly complicated for something so simple.
I have the "in-range" case as the last one, but in reality, since it's likely to be the most common case, it should be the first checked. Is the compiler capable of doing an optimization to account for this? Is this even something I should worry about? This only seems like an issue because this will be one of the most called functions in my program, so it has the potential to become a bottle-neck (although I haven't profiled it yet).

Since I'm still learning Clojure, any recommendations to make my code simpler or more idiomatic would be appreciated.

(defn wrap-shifted-code [^long char-code]
  (let [min-code 32
        max-code 126
        code-range (- max-code min-code)]
    (cond
      (< char-code min-code) (- max-code (rem (- min-code char-code) code-range))
      (> char-code max-code) (+ min-code (rem (- char-code max-code) code-range))
      :else char-code)))

At the request of @Sam Estep, here's a version of the code that correctly includes the outer bounds of the range when wrapping:

(defn wrap-shifted-code [^long char-code]
  (let [min-code 32
        max-code 126
        code-range (- max-code min-code)]
    (cond
      (< char-code min-code) (- max-code (rem (- min-code char-code 1) code-range))
      (> char-code max-code) (+ min-code (rem (- char-code max-code 1) code-range))
      :else char-code)))

Your solutions have subtle off-by-one errors. Your second solution partially fixes these by adding 1 to the result in some cases, but it doesn't fix the real problem, which is this:

(let [,,,
      code-range (- max-code min-code)]
  ,,,)

code-range needs to hold the number of integers from 32 to 126, inclusive. As Dijkstra famously noted, calculating this number is easy when you're using an inclusive-exclusive range, but when your range is inclusive on both ends, you need to account for that by adding 1:

(let [,,,
      code-range (- (inc max-code) min-code)]
  ,,,)

In response to your questions about repetition and performance: there's a function for that! Unlike rem, Clojure's mod function always returns a nonnegative value, so you can do this:

(defn wrap-shifted-code [char-code]
  (let [min-code 32
        max-code 126
        code-range (- (inc max-code) min-code)]
    (-> char-code (- min-code) (mod code-range) (+ min-code))))


Positioning link boxes & managing backgrounds I've managed to position the link boxes as I wanted and to apply a background to them, but I'm not sure I've done it in the most elegant or efficient way.

Is there a  better way to position the elements without mixing positioning and floats? And is there a way to remove the background between the link boxes without having to turn it off in the section and turn it on again for the boxes? Or any other suggestions?

I've only been coding for a few months, but I aspire to write nice shiny code.

jsfiddle link

Title

Lorem ipsum dolor sit amet.

Title

Lorem ipsum dolor sit amet.

Title

Lorem ipsum dolor sit amet.

section {
    width: 1000px;
    margin: 1em auto;
    background: #C3C3C3 url(images/background.png);
    overflow: hidden;
    border-radius: 5px;
}

.three, .five {
    background: none;
}

.link-box {
    position: relative;
    display: block;
    float: left;
    text-decoration: none;
    color: #333;
    border-radius: 5px;
    width: 300px;
    background: #C3C3C3 url(images/background.png);
}

.left-link {
    float: left;
}

.right-link {
    float: right;
}

.middle-link {
    left: 5%;
}

I edited your fiddle jsFIddle. Basically what I have done is removed position:relative and added float:left and then added some margin to the elements. Then with the last-child selector I removed margin from the last item.


'find' template for handling any file After growing tired of all the ways in which a file loop can be broken (find -print | while read) or unreadable (find -exec with complex commands), I think I've managed to build a find template which can handle any and all files which could possibly exist on a Linux system (not so famous last words). Can you find a way to break it, by changing either the test_ variables or the environment? For example, is it possible to mess with file descriptor 9 outside the script so that it won't work?

The only requirement is "sanity." In other words, test_file_name and test_dir_path cannot contain \0 or /, test_file_path cannot contain \0 (or be more than 1 level deep, since mkdir for the sake of the test is run without -p), and /bin/bash must be  a stable version of Bash 4.

#!/bin/bash
# Filenames can contain *any* character except only null (\0) and slash (/);
# here's some general rules to handle them:
#
# $'...' can be used to create human readable strings with escape sequences.
#
# ' -- ' in commands is necessary to separate arguments from filenames, since
# filenames can start with '--', and would therefore be handled as parameters.
# To handle parameters properly (like GNU tools) use `getopt`.
#
# `find` doesn't support this syntax, so we use `readlink` to get an absolute
# path which by definition starts with slash.
#
# The "$()" construct strips trailing newlines, so we have to add a different
# character and then strip it outside the "$()" construct.
#
# `IFS=` is necessary to avoid that any characters in IFS are stripped from
# the start and end of $path.
#
# '-r' avoids interpreting backslash in filenames specially.
#
# '-d '' splits filenames by the null character.
#
# '-print0' separates find output by null characters.
#
# Variables inside '$()' have to be quoted just like outside this construct.
#
# Use process substitution with "<(" instead of pipes to avoid broken pipes.
#
# Use file descriptor 9 for data storage instead of standard input to avoid
# greedy commands like `cat` eating all of it.

set -o errexit
set -o nounset
set -o noclobber

test_file_name=$'--$`\! *@ \a\b\e\E\f\r\t\v\\\"\' \n'
test_dir_path="$test_file_name"
test_file_path="${test_dir_path}/${test_file_name}"

mkdir -- "$test_dir_path"
touch -- "$test_file_path"

absolute_dir_path_x="$(readlink -fn -- "$test_dir_path"; echo x)"
absolute_dir_path="${absolute_dir_path_x%x}"

exec 9< <( find "$absolute_dir_path" -type f -print0 )
while IFS= read -r -d '' -u 9
do
    file_path="$(readlink -fn -- "$REPLY"; echo x)"
    file_path="${file_path%x}"
    echo "START${file_path}END"
done

rm -- "$test_file_path"
rmdir -- "$test_dir_path"

This code is vulnerable to TOCTOU. There is a tiny gap between the time that "plain files" are read from the process substitution (find -type f ...) and the time that readlink(1) is called on those filenames.

An attacker could create a program that waits for your program to run and then quickly deletes one of those files found by find(1) and replaces it with a symlink to somewhere else. readlink(1) will then dutifully return the target of that symlink and this is the path that will be output. The target could be outside $absolute_dir_path and a file of any type (directory, device node, ...).

Eg:

#!/bin/bash

set -o errexit
set -o nounset
set -o noclobber

# setup directory containing two plain files
# hardcode absolute_dir_path to /tmp/dir for simplicity
mkdir -p /tmp/dir
rm -f /tmp/dir/a /tmp/dir/b
touch /tmp/dir/a /tmp/dir/b

# emulate OP's find loop, but with inserted actions
# performed by an attacker (in real attack these would
# happen in an external program).
exec 9< <( find /tmp/dir -type f -print0 )
while IFS= read -r -d '' -u 9
do
        file_path_x="$(readlink -fn -- "$REPLY"; echo x)"
        file_path="${file_path_x%x}"
        ls -l "${file_path}"
        # attacker jumps in here and does:
        rm /tmp/dir/b
        ln -s /etc/passwd /tmp/dir/b
done

Output:

-rw-r--r-- 1 martin martin 0 2011-03-31 10:56 /tmp/dir/a
-rw-r--r-- 1 root root 2119 2011-03-28 11:35 /etc/passwd

The risk can be mitigated by only seeking files in directories beneath which untrusted users do not have write access. Directories such as /tmp and /var/tmp are problematic though and this is hard to solve. See the source of (eg) tmpreaper for some ideas.


Python gRPC shopping cart service The .proto file is as below:

syntax = "proto3";

package bamboo;

// -----------------Cart service-----------------

service CartService {
    rpc AddItem(AddItemRequest) returns (Empty) {}
    rpc GetCart(GetCartRequest) returns (Cart) {}
    rpc EmptyCart(EmptyCartRequest) returns (Empty) {}
}

message CartItem {
    string product_id = 1;
    int32  quantity = 2;
}

message AddItemRequest {
    string user_id = 1;
    CartItem item = 2;
}

message EmptyCartRequest {
    string user_id = 1;
}

message GetCartRequest {
    string user_id = 1;
}

message Cart {
    string user_id = 1;
    repeated CartItem items = 2;
}

message Empty {}

And I have a Cart service on gRPC that is as simple as below:

from grpczoo import bamboo_pb2_grpc, bamboo_pb2
from concurrent import futures
import grpc
import time

class CartService(bamboo_pb2_grpc.CartServiceServicer):
    def AddItem(self, request, context):
        print(request.user_id, request.item)
        return bamboo_pb2.Empty()

if __name__ == "__main__":
    channel = grpc.insecure_channel('127.0.0.1')
    cart_stub = bamboo_pb2_grpc.CartServiceStub(channel)

    # create gRPC server
    server = grpc.server(futures.ThreadPoolExecutor(max_workers=10))

    # add class to gRPC server
    service = CartService()
    bamboo_pb2_grpc.add_CartServiceServicer_to_server(service, server)

    # start server
    server.add_insecure_port('[::]:9000')
    server.start()

    # keep alive
    try:
        while True:
            time.sleep(10000)
    except KeyboardInterrupt:
            server.stop(0)

Let's assume that starting a service like above seems good when you have 40 services (We can create a base class for starting a service)

The most annoying part of the system is where I have to initiate a client when I need to send a RPC call to a service (here cart service):

import grpc

# set up server stub
from grpczoo import bamboo_pb2_grpc, bamboo_pb2

channel = grpc.insecure_channel('localhost:9000')
stub = bamboo_pb2_grpc.CartServiceStub(channel)
# form request
request = bamboo_pb2.AddItemRequest(user_id="123", item={'product_id': '21', 'quantity': 2})

# make call to server
response = stub.AddItem(request)
print(response)

As you can see for a simple RPC call like above I have to open channel to that service and form a request and then call the remote method AddItem. In a real world micro-service project I have to call at least 5 different methods and for each I have to create a channel and for the request and so on.

The question is how should I manage RPC calls to different methods when project gets bigger and I have 20 to 50 different services? The above code does not seems maintainable at all. How do you handle such cases?

Keep-alive
Your sleep method is curious. There are alternates here:
https://stackoverflow.com/questions/20170251/how-to-run-the-python-program-forever
but those are generic to Python; there is a better option for gRPC:

In this case, you can call server.wait_for_termination() to cleanly block the calling thread until the server terminates.

Stopping
You should not only call it on KeyboardInterrupt; you should put it in a finally:
    server.start()
    try:
        # ...
    finally:
        server.stop(0)

This way, the server will be stopped if the user breaks with Ctrl+C, or if there is any other exception. However, I doubt it's necessary to call this at all if you use wait_for_termination.


Sh script to reduce version number in opkg status file I have written a script to reduce/lower the version number stored in opkg status file using small shell script, This will enable us to force the opkg to install same version of a Debian package again.

Versions stored in the opkg files are as follows,

Version: 00.03.00a002
Version: 2013.07.001
Version: 2013.07.001
Version: 3.12.002

And my script is as shown below, This script would run on the embedded board which is having busybox based sh shell. I have put bash tag to reach more people.

Script edits either 1st version number or 2nd version number..I didn't take third because sometimes that would contain alphanumeric value and I am uncomfortable with handling hex subtraction.

#!/bin/sh

#Small script to Lower firmware version

OPKG_STATUS_FILE="/var/lib/opkg/status"
stamp=$(date +%s)
BACKUP_OPKG_STATUS_FILE="/var/lib/opkg/status_${stamp}"

#Creating backup file so that we can get back actual version if we want
cp ${OPKG_STATUS_FILE} ${BACKUP_OPKG_STATUS_FILE}
echo "${BACKUP_OPKG_STATUS_FILE} file created"

#clear original status file
:> ${OPKG_STATUS_FILE}

while IFS=' ' read -r line || [ -n "${line}" ];do
    ver_found=""
    ver_found=$(echo "${line}" | grep -i "Version")

    if [ ! -z "${ver_found}" ];then
        ver_extracted=""
        new_line=""
        for i in 1 2;do
            ver_extracted=$(echo "${line}" | grep -i "Version" | cut -d ':' -f 2 | cut -d '.' -f ${i})
            if [ ! -z "${ver_extracted}" ];then
            {
                #reduce version number
                if [ "${ver_extracted}" -gt 0 ];then
                    new_version=$(printf "%02d %02d" "${ver_extracted}" "01" | awk '{ printf "%.0f", $1 - $2 }')
                    new_line=$(echo ${line} | sed -e "s:${ver_extracted}:${new_version}:I")
                    line="${new_line}"
                else
                    continue
                fi
                break
            }
            fi
        done
    fi
    echo "${line}" >> "${OPKG_STATUS_FILE}"
done < "${BACKUP_OPKG_STATUS_FILE}"

I wanted to ask

if there is a better method for doing this.
One problem what I observed with my script is 03 is reduced and replaced with 2 instead of 02
I need to keep versions digits same, any suggestion for that ?

Since you're already using awk in there,
it would be better to rewrite all the echo - grep - sed processing with a single awk.
In particular, the entire while loop in the middle can be replaced with this:

awk -F '[:. ]' '/^Version: / {
  num1 = $3;
  num2 = $4;
  if (num1 > 0) {
    gsub(num1, num1 - 1);
    print;
  } else if (num2 > 0) {
    gsub(num2, num2 - 1);
    print;
  }
}
' "${BACKUP_OPKG_STATUS_FILE}" >> "${OPKG_STATUS_FILE}"

This produces slightly different (I think better) output than your original,
and with the number of sub-processes greatly reduced,
it's a lot more efficient.


Case class design in Scala In the Java world while writing the data access layer (for CRUD) and the model layer, I have done something like this:

public abstract class AbstractDao<N extends AbstractModel>{
        protected Class<N> persistentClass;
        public N findById(String id){

                return (N)mongoOperation.findById(id, persistentClass,persistentClass.getSimpleName());

        }
}

class FlightDao extends AbstractDao<Flight>
class AirlineDaoImpl extends AbstractMongoDao<Airline>

Where Flight extends AbstractModel and ,Airline extended AbstractModel

Now calling the findById was as trivial as

Flight flight = flightDao.findById("FlightId1");

I feel this was a decent way of doing things because it kept my code DRY. And most of the model objects needed the same CRUD methods.

Now coming to Scala, Play framework 2, anorm, I would like to know what is the right way of doing something such as this.

I read that model classes should be case classes but then that prevents us from inheritance. And moreover the data access definitions were given in the companion objects. This is what I have at the moment.

case class Airline(id:Pk[Long]=NotAssigned,name:String)
case class Flight(id:Pk[Long]=NotAssigned,code:String,airlineId:Long,date:DateTime)

object Flight{
    def getById(id:Long):Option[Flight] = {
    DB.withConnection { implicit connection =>
       SQL(
        """
          select * from flight
          where flight.id =  {id}
        """
      ).on(
        'id -> id
      ).as(Flight.simple.singleOpt)
    }

  }
}

object Airline{
    def getById(id:Long):Option[Airline] = {
    DB.withConnection { implicit connection =>
       SQL(
        """
          select * from airline
          where airline.id =  {id}
        """
      ).on(
        'id -> id
      ).as(Airline.simple.singleOpt)
    }

  }
}

I'm certain there must be a better way to do this.  I would love to know how I could write neat / clean Scala code for this. Any pointers, design patterns and feedback is much appreciated.

I believe that in addition to the stated Java -> Scala OO question, that you may also be wondering about a good way to "organize" Models/DAOs/Controllers in Play 2. So I will incorporate that in my answer.

I would have asked in a comment, but I don't seem to have the rep yet...

A few notes before we get into an answer:

fedesilvia is correct, that case classes can extend traits and/or classes.
Model classes generally should be case classes. They're a nice, easy-to-use construct that provides your "equals" method, "toString" method, and "hashcode" method. Also, many libraries have provided great mechanisms for working with case classes for a variety of purposes. Not to mention matching, immutable by default, etc...

Let's take a look at how to organize this from top to bottom.

Controllers

As you know, Play's Router sends requests in from the HTTP client to your Controller. It is my opinion that the Controllers then have 3 core responsibilities:

Deserialize the request.
Serialize the response.
Handle any errors appropriately.

Missing between responsibilities 1 and 2, is the actual "handling" of the request. For a CRUD app, this could be where your DAOs come in.

DAOs

In my application, DAOs are Objects that extend a MongoDAO trait. The trait "knows" how to interact the the database drivers (get a connection), and supplies basic utilities. For instance:

/** Basic DAO Behavior for MongoDB documents. */
trait MongoDao {
  /** Name of the MongoDB Collection. */
  protected def colName: String

  /** Returns the default database. */
  protected def db = ReactiveMongoPlugin.db

  /** The actual collection used by the DAO. */
  protected def col: JSONCollection =
    db.collection[JSONCollection](colName)

  /** Returns the first result, if any, for the given query. */
  def findOne[DOC](q: JsObject)(implicit reads: Reads[DOC]) =
    col.find(q).cursor[DOC].headOption

  ...

I also have an abstract class that extends MongoDAO called, "AssetDAO". AssetDao provides 90% to 100% of the DAO implementation for 13 of the Models in my App. Here is it's type:

/** Common DAO behavior for all Assets. */
abstract class AssetDao[A <: AssetModel]
  (override val colName: String)(implicit format: Format[A])
extends MongoDao with ModulePermissions {

The DAO implementations can look like this:

object ArchetypeDao extends AssetDao[Archetype]("archetypes")

But most of them also have a couple methods that are all their own. Usually when I need to make use of Model specific properties in a query.

Model Companion Objects

Given the libraries that I'm using (notably play.api.lib.json), I find it best to put (de-)serialization code in the Companion Objects. For instance:

object Archetype {
  /** Converts Archetype to/from its MongoDB representation */
  implicit val fmt = Json.format[Archetype]

  /** Reads that are used for both Create and Update. */
  val coreReads = (
    (__ \ "name"   ).json.pickBranch(smlReqStr) and
    (__ \ "summary").json.pickBranch(medReqStr) and

    ((__ \ "description").json.pickBranch(fullText) or emptyObj)
  ) reduce
}

As you can see, the Companion Object contains all of the information it needs to (de-)serialize the case class to/from its MongoDB representation; and to/from its "client" representation. So the DAO ends up using the Json.format and the Controller uses the JSON Transformers.

Models

In this setup, all Models are simple case classes that represent persisted data. For instance:

case class Archetype (
  _id:         BSONObjectID,
  module_id:   BSONObjectID,
  doc_meta:    DocMeta,
  name:        String,
  summary:     String,
  description: Option[String]
) extends AssetModel

And here is the AssetModel trait that Archetype implements:

/** Describes some common behavior of asset types */
trait AssetModel {
  def _id:       BSONObjectID
  def module_id: BSONObjectID
  def doc_meta:  DocMeta
}

You may have noticed earlier that Archetype.coreReads doesn't reference all the fields the model has. That's because the "AssetControllers" are taking care of the rest of the fields for every AssetModel. Implementing AssetModel here is what makes that work.

To do it again, I might have the AssetModel Companion Objects extend a trait that provides the common field (de)serialization.

Conclusion

Hopefully, this answer has provided you with:

A better understanding of using OO in Scala.
Some ideas for organizing your Play App to write DRY code.


Syntax highlighter for HTML and PHP I've created a JavaScript application to highlight the syntax of HTML and PHP. I know a lot of syntax highlighter are available nowadays, I just created to extend my knowledge in JS and regular expressions. I only wanted to know if its the right way to do this. (The code below works fine.)

js/codeHighlighter.js

function codeHighlighter(){
    var obj=document.getElementsByTagName("code");
    for(var i=0;i<obj.length;i++){
        var data=obj[i].innerHTML;
        data=data.replace(/&lt;(.*?)&gt;/g,"&lt;$1&gt;");
        data=data.replace(/"(.*?)"/g,"&quot;$1&quot;");
        data=data.replace(/&lt;\?(.*?)\s/g,"&lt;?$1");
        data=data.replace(/\s\?&gt;/g,"?&gt;");
        data=data.replace(/\/\* (.*?) \*\//g,"/* $1 */");
        data=data.replace(/(new|echo|print|while|for|foreach|class|public|function|static|protected|private|return|required|required_once|include|include_once)[^=]/g," $1 ");
        data=data.replace(/\\n/g,"
");
        data=data.replace(/\\t/g,"&nbsp;&nbsp;&nbsp;&nbsp;&nbsp");
        obj[i].innerHTML=data;
    }
}

index.html

        <title>Code Highlighter</title>
        <meta charset="UTF-8">
        <meta name="viewport" content="width=device-width, initial-scale=1.0">

This application highlights `php` and `html` code.

            /* A sample code. */\n
            &lt;div class="code" &gt;\n
            \t Hello!\n
            &lt;/div&gt;\n
            &lt;?php\n
            class Anish(){\n
            \n
            \t public function __construct(){\n
            \t\t return "Hello";\n
            \t }\n
            \n
            }\n
            $anish=new Anish();\n
            echo $anish;\n
            ?&gt;\n

Really accurate highlghting is a big challenge, and even if your implementation is not totally falsy it's very incomplete.

First some obvious points, easy to correct:

your PHP reserved words list lacks a number of words, such as (not exhaustively) global, const,  if, else, switch, case, default, do, exit, break, continue try, catch, finally, ...
you look for PHP multiline comments like /*...*/ but not for simple line ones like //..., nor for HTML comments <!--...-->.
you look for double-quoted strings "..." but not for single-quoted ones '...'.

Now some harder issues:

you currently don't take care of escaped (single or double) quotes in a quoted string: "quote \" inside quoted string" breaks the highlighting.
you don't look for numbers (integer or float)

Lastly, not a lack but might be improved: you don't distinct between HTML tags and their attributes.

Please note that this is not to criticize your work! At the opposite, since you said it is:

  to extend my knowledge in JS and regular expressions

I hope it encourages you to rise to the challenge :)

EDIT. Two points I forgot to mention above.

The first one comes from a preliminary general advice: try to follow best practices, notably in that, instead of:

for(var i=0;i<obj.length;i++){

you should write:

for (var i = 0; i < obj.length; i++) {

and so on evrywhere...

So here is the point since when looking for reserved words you wrote this:

data = data.replace(/(new|echo|...|include|include_once)[^=]/g, ...

There you added [^=] to avoid selecting something like $new=....
Right but regarding the above advice you must realize that one may have written $new = ... instead. Then you'll select new as a reserved word, while it's not!

So actually you'd better looking for a prepended $ rather than an appended =:

data = data.replace(/[^\$(new|echo|...|include|include_once)/g, ...

The other point is only for convenience: currently you force tab to be arbitrarily replaced by 4 spaces, which may sometimes be undesired. So you might merely write something like this:

function codeHighlighter(tab) {
  tab = tab ? tab : 4;
  for (var i = 0; i < obj.length; i++) {
    ...
    data=data.replace(/\\t/g, repeat("&nbsp;", tab);
    ...
  }
}


SPOJ Class Leader using circular linked list I have solved a spoj question CLASS LEADER.  For each test case there are n students and a paper will be given to student m and now the game starts, the student m will pass the paper by o positions and the person who gets the paper gets eliminated and the game will be continued until one student is left.

I actually solved the problem by first creating a linked list of size n using struct and then pointed last node to the front which made my list circular then i went to position m and then started the calling recursive call to function which moved by o positions and removed that node. I am unable to improve my code's performance and getting TLE.

#include<iostream>
using namespace std;
struct node {
    int data;
    node* next;
};
node* tail = new node();                    //Global node
void createLL(int n) {                      //adding node at end
    node* t = new node();
    t->data = n;
    t->next = NULL;
    tail->next = t;
    tail = t;
}
int func(node* p, int k) {
    if (p->next == p)return p->data;
    int f = k;
    node* q = new node();
    while (f--) {
        q = p;
        p = p->next;
    }
    q->next = p->next;
    func(q, k);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, o;
        cin >> n >> m >> o;
        if (n == 1) {
            cout << n << endl;
            continue;
        }
        node* head = new node();
        head->data = 1;
        head->next = NULL;
        tail = head;
        for (int i = 1; i<n; i++) {         //created linked list with values index+1
            createLL(i + 1);
        }
        node* r = head;
        while (r->next != NULL) {           //traverse to the end
            r = r->next;
        }
        r->next = head;                     //created a circular linked list
        m--;
        while (m--) {
            head = head->next;              //going to m'th position
        }
        int ans = func(head, o);            //iterative call
        cout << ans << endl;
    }
    return 0;
}

Don't use using namespace std

Prefer '\n' to std::endl

The reason is that std::endl flushes the stream. This can lead to performance issues when called frequently (Not your primary performance issue but still just good practice.) Furthermore many people consider good code to be explicit and would prefer a call to std::flush when you want to flush the stream.

Avoid Globals

OOP provides encapsulation so that variables that should not be accessible from outside a given scope can't be. Not only is it harder for you to make mistakes altering variables on a large scale but it also makes anyone touching your code unable to do it too.

Memory Leaks

You have many calls to new but do not have a single call to delete. Your program leaks every bit of memory it allocates. The two main problem areas are both here:

int func(node* p, int k) {
    if (p->next == p)return p->data;
    int f = k;
    node* q = new node();
    while (f--) {
        q = p;
        p = p->next;
    }
    q->next = p->next;
    func(q, k);
}

first you create a new node pointed to by q and then immediately assign q to p therefor making it impossible to ever delete the memory you just allocated.

Then you assign q->next = p->next; effectively unlinking p from the rest of the list. Once the function goes out of scope p is lost and the memory pointed to by it can never be freed.

Prefer nullptr to NULL

NULL is a C Macro that is may or may not defined as 0 and can cause ambiguity. nullptr on the otherhand is a keyword.

while (r->next != NULL)

And don't compare values to NULL (or nullptr) - pointers convert implicitly to Booleans. Prefer instead to represent the conditional as:

while (r->next)

Prefer initialization over assignment

struct node {
    int data;
    node* next;
};

Your node is not really complete. Imagine I do this:

node myNode;
std::cout << myNode.data;

What will print? We don't know. It's undefined behavior.

Even if you provided a default constructor (which is overkill and unnecessary) and assigned the variables default values there it would be suboptimal because you will essentially giving your variables garbage values only to give them the meaningful ones momentarily later.

struct node {
    int data{ 0 };
    node* next{ nullptr };
}

Here the node is constructed properly and without the potential for UB. If you don't want to assign data the default value of 0 you could create a constructor that takes an int as a parameter and initializes data to the value passed. Something like:

struct node {
    int data;
    node* next{ nullptr };
    node(int data) : data{ data } {};
}

Naming

Use better names. You will thank yourself months from now when rereading old code. Single letter variables are hard to keep track of and require you to memorize your code when more explicit naming makes that unnecessary. The exception to that are the parameters of the problem you are being given to solve. Well named functions also better help understand what is being done as well.

Take for instance your createLL function. This function doesn't create a linked list. It adds a single node to the end of the list. add_node or push_back would be more appropriate names.

And func() is the most generic possible name for a function you can come up with. I don't expect to see that name outside of pseudocode.

Prefer prefix over postfix

Your code is the perfect example of when to use both of these. In your for loop you use postfix which tells me you are incrementing with postfix as a matter of course which is a bad habit to get into. Postfix creates a copy, then increments the original and then returns the copy. This can be useful such as in you while loops. If you used prefix there you would end up with an off-by-one error. The constant copying that is done in your while loops is trivial with integral values like you use but if it was a non-trivial (perhaps a user defined class) value a simple solution would be to decrement your variable with prefix within the loop itself.

Omit return 0

The compiler will return from the end of main() without you needed to tell it to. Not only is it unnecessary but by doing so you signal to readers of your code that you may return error codes elsewhere in the program (which you don't).

int t;
cin >> t;

This is an input that you didn't provide in your description of the problem. You dealt with it correctly programmatically but it is an important requirement and thus should have been in your description. It is important to note that this is considered a reasonable exception to initializing variables. You define your variable and immediately assign it via input from the user.

int n, m, o;

Don't declare more than one variable per line. It can be misleading (with pointer assignment and initialization in particular) and can make it hard to track.

for (int i = 1; i<n; i++) {         //created linked list with values index+1
    createLL(i + 1);
}

If you start i at 2 the you don't need to add 1 when passing it as a parameter. Note the change from < to <= in the comparison.

for (int i = 2; i <= n; ++i) {
    createLL(i);
}

while (r->next != NULL) {           //traverse to the end
    r = r->next;
}
r->next = head;                     //created a circular linked list

This whole loop is unnecessary. You already know where the last element in your list is.

tail->next = head;

Put all of that together and it looks something like this:

#include <iostream>

struct node {
    int data{ 0 };
    node* next{ nullptr };
};

void add_node(node*& tail, int n) {
    node* temp = new node();
    temp->data = n;
    tail->next = temp;
    tail = temp;
}

int josephus(node*& start_node, int index_shift) {
    if (start_node->next == start_node) {
        return start_node->data;
    }

    int shift_count = index_shift;
    node* temp = start_node;

    while (shift_count--) {
        start_node = temp;
        temp = temp->next;
    }

    start_node->next = temp->next;
    delete temp;
    return josephus(start_node, index_shift);
}

int main() {
    int num_tests; // formerly T
    std::cin >> num_tests;

    node* head = new node();

    while (num_tests--) {
        int num_nodes; // formerly n
        int start_index; //formerly m
        int shift_by; //formerly o
        std::cin >> num_nodes >> start_index >> shift_by;

        if (num_nodes == 1) {
            std::cout << num_nodes << '\n';
            continue;
        }

        head->data = 1;
        node* tail = head;

        for (int i = 2; i <= num_nodes; ++i) {
            add_node(tail, i);
        }

        tail->next = head;

        while (head->data != start_index) {
            head = head->next;
        }

        std::cout << josephus(head, shift_by) << '\n';
    }
    delete head; // just noticed I never deleted this. (Sure the program
    // ends here but you always want to clean up your memory.)
}

Note the pointers passed as reference so that I didn't need a global variable. More explicit names like start_node, num_students, josephus, and temp. I'm not implying my names are the best but they are clearer and more explicit like add_node. Note the calls to delete when necessary.

But this isn't really the best solution for several reasons:

Avoid naked new/delete.

You could use smart pointers but they can be a bit unwieldy when being repointed frequently. You should use them anyway when you can but we are going to change our solution.
The data structure is poorly made.

I understand that C++ doesn't have a circular list and that a circular list seemed especially appealing for this problem but a.) implementing a full scale data structure is a much more complicated task than this b.) there are simpler workarounds. Your circular list is just a bunch of exposed nodes that you manually link together at the end. A good data structure design would not expose the nodes directly and would use templates to provide for reusability.
You should prefer standard data structures.

Years of man hours have gone into them. If you want to remake some for a learning exercise: Great! But it doesn't belong with your Josephus solution.
We are still getting TLE.

The way to use a standard std::list as a circular list would be with the use of iterators. I have the following example:

#include <iostream>
#include <iterator>
#include <list>

int main() {
    int num_tests;
    std::cin >> num_tests;

    while (num_tests--)
    {
        int num_students; // formerly n
        int start_index; //formerly m
        int steps; //formerly o
        std::cin >> num_students >> start_index >> steps;

        std::list<int> students;

        for (auto i = 1; i <= num_students; ++i)
        {
            students.push_back(i);
        }

        std::list<int>::iterator it = students.begin();
        for (auto i = 1; i < start_index; ++i)
        {
            ++it;
            if (it == students.end())
            {
                it = students.begin();
            }
        }

        auto countdown = num_students - 1;
        while (countdown--)
        {
            for (auto i = 0; i < steps; ++i)
            {
                ++it;
                if (it == students.end())
                {
                    it = students.begin();
                }
            }

            if (it != students.begin())
            {
                it = students.erase(it);
                --it;
            }
            else
            {
                students.erase(it);
                it = students.end();
                --it;
            }
        }

        std::cout << *it << '\n';
    }
}

In this example you simply use an iterator to traverse the list much like you did with your nodes. However here we have a standard memory-safe container. no leaks. No manual memory management. You have to take some care to ensure you are incrementing and wrapping correctly and that you never dereference your std::list::end() but this is much safer. (And when you break things it will shout at you and you can get to debugging faster.) You may notice that I did not implement this with recursion. Feel free to reimplement it that way as a learning experience.

(Also be aware that both of these solutions really should factor out the entire problem into one higher level function. Encapsulation is important in C++ and a decluttered main() is highly desirable.)

This still isn't the best solution. Mostly because at the end of the day programming challenges like this are not generally going to be successfully completed by brute force. This solution still gets TLE.

as @vnp noted this is the Josephus Problem. As such it can actually be expressed mathematically. The following expression was found on Geeks for Geeks:

#include <iostream>

int josephus(int num_students, int steps)
{
    if (num_students == 1)
    {
        return 1;
    }
    else
    {
        /* The position returned by josephus(n - 1, k) is adjusted because the
        recursive call josephus(n - 1, k) considers the original position
        k % n + 1 as position 1 */
        return (josephus(num_students - 1, steps) + steps - 1) % num_students + 1;
    }
}

int main() {
    int num_tests;
    std::cin >> num_tests;

    while (num_tests--)
    {
        int num_students; // formerly n
        int start_index; //formerly m
        int steps; //formerly o
        std::cin >> num_students >> start_index >> steps;

        auto answer = josephus(num_students, steps);

        answer = (answer + start_index) % num_students;

        if (answer != 0) {
            std::cout << answer << '\n';
        }
        else
        {
            std::cout << num_students << '\n';
        }
    }
}

The solution works as the size decreases recursively and k % n + 1 tracks the position and allows for skipping over otherwise removed candidates. Then the start_index is applied to shift the survivor respectively.

Now is the point I get to disappoint everyone! This still returns TLE. I suspect the excessive calls to % which are expensive to process for the performance issue. I have tried viewing the more complicated mathematical expression of the solution but it is over my head. It is available in the Wikipedia page I linked. I hate to be anti-climactic so if anyone else has the solution I encourage you to post it in an answer so I can upvote it.


Converting UK drams to ounces and pounds in PHP I have written this little function to convert UK weight drams (dr) to ounces (oz) and pounds (lbs). As far as my research goes, 1 lbs = 16 oz and 1 oz = 16 dr. I need the function to return an array of lbs, oz and dr.

Am I doing it right? Or is there a better way to do it? Has my method got any flaws?

function fromDrams($drams){

    // Nullify pounds
    $ouncesAndDrams = $drams % 256;

    $lbs = (int) ($drams / 256);
    $oz  = (int) ($ouncesAndDrams / 16);
    $dr  = $ouncesAndDrams % 16;

    return ['lbs' => $lbs, 'oz' => $oz, 'dr' => $dr];
}

It does return good values when tested:

fromDrams(273) = ['lbs' => 1, 'oz' => 1, 'dr' => 1];
fromDrams(272) = ['lbs' => 1, 'oz' => 1, 'dr' => 0];
fromDrams(271) = ['lbs' => 1, 'oz' => 0, 'dr' => 15];
fromDrams(256) = ['lbs' => 1, 'oz' => 0, 'dr' => 0];
fromDrams(32) = ['lbs' => 0, 'oz' => 2, 'dr' => 0];
fromDrams(17) = ['lbs' => 0, 'oz' => 1, 'dr' => 1];
fromDrams(15) = ['lbs' => 0, 'oz' => 0, 'dr' => 15];

There are two things that stand out to me in your code. The first is that your integer cast seems a bit premature. When creating a general function like this, you probably do not want to round the answer, since 1.5 oz is a perfectly valid weight. A user of your function can then cast the resulting values if this is required.

The second is that your conversion values are magic numbers. These should be in constants with names that express the meaning of the number.

A class would be perfect to store the logic and constants. A Weight class would probably be a well-suited name. An Weight object can then hold the amount of weight in one specific unit and provide public methods to retrieve the weight in other units.

The Weight class that I have created here provides three static "Builder/Factory" methods to create a Weight object from. The constructor has been made private to support the use of the more expressive static function. The reasoning behind this, is that $weight = Weight::fromDrams(16); is a lot easier to understand than $weight = new Weight(16);.

Furthermore, the class provides the three public methods to retrieve the given weight for a specific unit.

class Weight {
    const POUNDS_TO_OUNZES = 16;
    const OUNZES_TO_DRAMS = 16;

    /**
     * @var float
     */
    private $drams;

    public static function fromPounds ($pounds) {
        return self::fromOunzes($pounds * self::POUNDS_TO_OUNZES);
    }

    public static function fromOunzes ($ounzes) {
        return self::fromDrams($ounzes * self::OUNZES_TO_DRAMS);
    }

    public static function fromDrams ($drams) {
        return new static($drams);
    }

    private function __construct ($drams) {
        $this->drams = $drams;
    }

    public function inPounds () {
        return $this->inOunzes() / self::POUNDS_TO_OUNZES;
    }

    public function inOunzes () {
        return $this->inDrams() / self::OUNZES_TO_DRAMS;
    }

    public function inDrams () {
        return $this->drams;
    }
}

If you still require a very specific function that returns an array of 'lbs', 'oz' and 'dr' like your question says, than this Weight class can be used in conjunction with it as such:

function fromDrams ($drams) {
    $weight = Weight::fromDrams($drams));

    return [
        'lbs' => (int) $weight->inPounds(),
        'oz' => (int) $weight->inOunzes(),
        'dr' => (int) $weight->inDrams(),
    ];
}

Here you see the Weight class not performing any rounding itself and letting the user of the class perform these when required.

This Weight class is now much more versatile than your original piece of code and can be used in many other situations. For example a website that provides conversion of an amount of weight for a specific unit to the respective weights for the other three units.

if (!empty($_POST["amount_in_drams"]))
    $weight = Weight::fromDrams($_POST["amount_in_drams"]);

if (!empty($_POST["amount_in_ounzes"]))
    $weight = Weight::fromOunzes($_POST["amount_in_ounzes"]);

if (!empty($_POST["amount_in_pounds"]))
    $weight = Weight::fromPounds($_POST["amount_in_pounds"]);

echo $weight->getPounds() . " pounds, ";
echo $weight->getOunzes() . " ounzes or ";
echo $weight->getDrams() . " drams.";


Handling users connection to the application This is a simple User class that I'm using throughout the application for anything related to the users. To tell if a user is logged in or not, I check the presence of the userID in the $_SESSION. When I'm logging in the user, I simply set the $_SESSION["userID"] equal to the ID of the user.

class User{

protected $pdo;

public function __construct(PDO $pdo)
{
    $this->pdo = $pdo;
}

public function getID()
{
    if(!$this->isConnected()) return 0;
    return $_SESSION["userID"];
}

public function isConnected()
{
    return !empty($_SESSION["userID"]);
}

public function login($username, $password)
{
    $q1 = $this->pdo->prepare("SELECT * FROM users WHERE username = ?");
    $q1->execute([$username]);
    $user = $q1->fetch();

    if(empty($user)) return false;
    if(!password_verify($password, $user->password)) return false;

    $_SESSION["userID"] = $user->id;
    $_SESSION["username"] = $user->username;
    return true;
}
}

I'm putting everything in a class just so that it's organized and easily accessible, but I'm pretty sure I'm not doing this properly. I presume that the correct way to handle this is to use properties for the class (example: $isConnected, $id) and change them when the user logs in/logs out.

However, I'm not sure how I would do that and avoid overwriting the user object every time the script loads (page refresh), so at the moment I'm doing it like that.

It works fine, but I really feel like I'm missing the point of OOP here. I'm a beginner when it comes to OOP with PHP, so please don't be too harsh! I'd really like some input from experienced developers.

If your class takes care of the authentication of your application don't call it User but Auth or Authentication.

You shouldn't "putting everything in a class". Wrapping your code in a class is not OOP. See SOLID and start with the Single responsibility. Every class should have one single responsibility. Your class takes care to recover users data and handles authentication on your application. Too much responsibility for one class. Separate the user handling from the database query.

$_SESSION is an hard dependency. $_SESSION is global, and global is evil.  If at some point you choose to store session data in a different storage you will need to change the implementation of the class. If you write orthogonal code you will enables to changes isolated areas of the code without influence other areas.
You can use abstractions such as those provided by packages like Symfony2, HttpFoundation.

Although there are few who worry about it.


Comparing data in SQL using foreign keys The following is given:

CREATE TABLE City (
  city_name varchar(255),
  country varchar(255),
  primary key (city_name)
  );

insert into City(city_name, country) values('London', 'England');
insert into City(city_name, country) values('Santiago', 'Chile');
insert into City(city_name, country) values('Edinburgh', 'Scotland');
insert into City(city_name, country) values('Tallinn', 'Estonia');
insert into City(city_name, country) values('Madrid', 'Spain');
insert into City(city_name, country) values('Paris', 'France');

CREATE TABLE Airport (
  airport_code int,
  city_name varchar(255),
  primary key (airport_code)
  );

insert into Airport(airport_code, city_name) values (123, 'London');
insert into Airport(airport_code, city_name) values (431, 'London');
insert into Airport(airport_code, city_name) values (439, 'Tallinn');
insert into Airport(airport_code, city_name) values (252, 'Santiago');
insert into Airport(airport_code, city_name) values (240, 'Paris');
insert into Airport(airport_code, city_name) values (992, 'Edinburgh');
insert into Airport(airport_code, city_name) values (972, 'Tallinn');
insert into Airport(airport_code, city_name) values (754, 'Tallinn');

CREATE TABLE FlightDelays (
   flight_code varchar(255),
   origin int,
   destination int,
   average_minute_delay int,
   price int,
   primary key (flight_code),
   foreign key (origin) references Airport (airport_code),
   foreign key (destination) references Airport (airport_code)
   );

insert into FlightDelays(flight_code, origin, destination, average_minute_delay, price) values
('XQ1242', 123, 431, 10, 20);
insert into FlightDelays(flight_code, origin, destination, average_minute_delay, price) values
('PX1203', 439, 252, 2, 20);
insert into FlightDelays(flight_code, origin, destination, average_minute_delay, price) values
('OO2442', 992, 972, 9, 20);
insert into FlightDelays(flight_code, origin, destination, average_minute_delay, price) values
('XK1442', 972, 431, 15, 20);
insert into FlightDelays(flight_code, origin, destination, average_minute_delay, price) values
('PW4332', 123, 754, 40, 20);
insert into FlightDelays(flight_code, origin, destination, average_minute_delay, price) values
('QJ332', 754, 431, 4, 20);

Question:

  Express the following query in SQL:
  "What are the ﬂights whose origin airport and destination airport are in the same city?"

How can I improve my solution?

select z.flight_code, z.origin, z.destination
from (
      select a.flight_code, a.origin, a.oCity, a.destination, Airport.city_name as dCity
      from (
            select FlightDelays.flight_code, FlightDelays.origin, Airport.city_name as oCity, FlightDelays.destination
            from FlightDelays
            inner join Airport on FlightDelays.origin = Airport.airport_code) as a
      inner join Airport on a.destination = Airport.airport_code) as z
where oCity=dCity;

Just think simple:

select f.flight_code, f.origin, f.destination
  from FlightDelays f
  join Airport fo on fo.airport_code = f.origin
  join Airport fd on fd.airport_code = f.destination
 where fo.city_name = fd.city_name

You can try at SQL Fiddle


Calculate difference of two ranges given Write a method to compute the difference between two ranges. A range is defined by an integer low and an integer high. A - B (A “minus” B) is “everything in A that is not in B”.

This is an interview question and here is my code:

void findDiff(int a1,int a2, int a3, int a4)
{
   cout<<"("<<a1<<","<<a2<<") - ("<<a3<<","<<a4<<") = \n";

   if(a1 < a3)
   {
         int end = (a2<a3) ? a2: a3-1;
         for(int i=a1; i<=end; i++) cout<<i<<"\t";
   }

   if(a4 < a2)
   {
         int start = (a1>a4) ? a1 : (a4+1);
         for(int i=start; i<=a2; i++) cout<<i<<"\t";
   }
   cout<<"\n";
}

Please look at the code and tell me if it correct and if I'm missing any case. Thanks a lot in advance :)

Make sure this is the signature they want. e.g. they do not expect the function to return vector, iterator or sthg. Also make sure they do not expect you to validate input. e.g. a1 <= a2 etc... after that you can remove redundant conditionals, they are already present in the for loops. And you can replace ternary operators with std::min/max for a more idiomatic c++. otherwise I could not find any missed case or off-by-one bugs.

void findDiff(int a1,int a2, int a3, int a4)
{
   cout<<"("<<a1<<","<<a2<<") - ("<<a3<<","<<a4<<") = \n";

    for(int i=a1; i<=std::min(a2, (a3-1)); i++) cout<<i<<"\t";

    for(int i=std::max(a1, (a4+1)); i<=a2; i++) cout<<i<<"\t";

    cout<<"\n";
}


Assembly program which detects all numbers with two integral divisors For an FASM assembly course I've to do the following exercise:

"Write a program that takes the number n as input. Then it prints all the numbers x below n that have exactly 2 different integral divisors (Besides 1 and x).

For example: 15 is such a number. It is divisible by 1,3,5,15. (Here 3 and 5 are the two different divisiors, besides 1 and 15).

However, 4 is not such a number. It is divisible by 1,2,4."

Full description can be seen here: GitHub xorpd.

Here's the code I've written:

format PE console
entry start

include 'win32a.inc'

; ===========================================
; Write a program that takes the number n as
; input. Then prints all the numbers x below
; n that have exactly 2 different intergral
; divisors (Besides 1 and x).
; Example: 15 : 1, 3, 5, 15 => 3 and 5.
; ===========================================

; ------ Usage example ----------------------
; The first "f" is the number n which was entered by the user.

; C:\Users\michael\Desktop\fasmProgs>divisors
; f
; 6
; 8
; a
; e
; f
; ------------------------------------------

section '.text' code readable executable

start:
    call    read_hex            ; Provided by teacher. Reads in a hexadecimal number from stdin.

    mov     edi,    eax         ; edi becomes the upper limit.
    mov     esi,    5           ; esi becomes the control variable.

outerLoop:
    inc     esi
    mov     ebx,    2           ; ebx becomes the divisor and control variable of the inner loop.
    mov     ecx,    0           ; Counts how many division have been possible.
innerLoop:
    xor     edx,    edx
    mov     eax,    esi
    div     ebx

    cmp     edx,    0
    jne     prepareInnerIteration
    inc     ecx

prepareInnerIteration:
    inc     ebx                  ; Increment the divisor.

    cmp     ebx,    esi          ; Here the control variable acts as the upper limit.
    jl      innerLoop

prepareOuterIteration:
    cmp     ecx,    2
    jne     goToNextIteration

    cmp     esi,    6            ; In case no number was given. Just a blank.
    je      goToNextIteration

    mov     eax,    esi
    call    print_eax            ; Provided by teacher. Prints eax to stdin.

goToNextIteration:
    cmp     esi,    edi
    jl      outerLoop

    push    0
    call    [ExitProcess]

include 'training.inc'

On of the tests I've done:

I enter hexadecimal 1e (decimal 30).

It returns:

6 => Can be divided by 2 and 3. Therefore correct detected.
8 => 2, 4
10 => 2, 5
14 => 2, 7
15 => 3, 5
21 => 3, 7
22 => 2, 11
26 => 2, 13
27 => 3, 9

I would say it works. At least essentially.

Nevertheless:
There might be flaws even bugs in my program. And I guess one could improve it a lot.

So therefore:

Any hints, comments and recommendation by more experienced Assembly programmer very much appreciated.

mov ecx, 0    ; Counts how many division have

This begs for an optimization in the form xor ecx, ecx. This will clear ECX just the same, is shorter and faster.

cmp edx, 0
jne prepareInnerIteration
inc ecx

Another optimization this time on compairing. To compare with zero, you can equally test the value with itself. So writing test edx, edx. This shortens the program.

goToNextIteration:
  cmp  esi, edi
  jl   outerLoop

Your code performs 1 iteration too many! Consider EDI=30 then this code will jump back to outerLoop when ESI=29, but there it will instantely be incremented to ESI=30 and so the code will superfluously process the case where the control variable = upper limit.

cmp  esi, 6            ; In case no number was given. Just a blank.
je   goToNextIteration

I don't see how this comment relates to the control variable being 6.
It just by-passes the output, which is wrong because the number 6 fulfills the conditions.

What I miss is a test for any user input smaller than 6

  call read_hex ; Reads in a hexadecimal number from stdin.
  cmp  eax, 6
  jl   ExitProg
  ...
ExitProg:
  push 0
  call [ExitProcess]

; ------ Usage example ----------------------
; The first "f" is the number n which was entered by the user.

; C:\Users\michael\Desktop\fasmProgs>divisors
; f
; 6
; 8
; a
; e
; f
; ------------------------------------------

This is a misleading comment! Since the premise states that the results are to be below the inputted number, the line ; f conflicts in the usage example given.


ReactJs stateWrapper for nested state objects I made a simple state wrapper for a react project I am working on, so I can keep my state at the top component but reason about it at a lower class level.

The example below is very simple, but it works and provides enough of an example of what StateWrapper does, obviously i am using it in reality with a much more complex object at the top state level.

This works even when nesting StateWrapped components, the state always lives at the top level.

I'm not 100% sure that this is the right way to go to be honest, but it seems to work quite nicely so that I can keep a complex component's logic local to its class while still keeping the state at the top level and allowing components to interact with eachother at the top stateful level.

Welcome any feedback, i'm aware it might be a bit of an anti-pattern but i can follow the state down through my classes from the top level in my code easily, and the state all lives at the top component so it debugs nicely in chrome and performs well on my more complex app.

Simple working example is as follows:

import * as React from 'react';

export default class Test extends React.Component {

    constructor(...props) {
        super(...props)

        this.component1 = new WrappedComponent (
            props => this.setState({component1: props})
        )

        this.component2 = new WrappedComponent (
            props => this.setState({component2: props})
        )

        //this one passes some initial props
        this.component3 = new WrappedComponent (
            props => this.setState({component3: props}),
            {...this.props}
        )

        this.state = {
            component1: this.component1.state,
            component2: this.component2.state,
            component3: this.component3.state,
        }

    }

    render() {

        return(

                <this.component1.component
                    onClick={() => this.component2.setText("component1")} />

                <this.component2.component
                    onClick={() => this.component3.setText("component2")} />

                <this.component3.component
                    onClick={() => this.component1.setText("component3")} />

        );
    }

}

class StateWrapper {

    constructor(setState, initialProps = []) {
        this.setState = props => {
            this.state = {...this.state, ...props}
            setState(this.state)
        }
        this.props = initialProps
    }

    render() {
        return(
render() not defined
)
    }

    component = props => {
        this.props = {...this.props, ...props}
        return this.render()
    }
}

class WrappedComponent extends StateWrapper {

    constructor(...props) {
        super(...props)
        this.state = {
            text: "no text has been set"
        }
    }

    render() {
        let text = `Received text: ${this.state.text}`
        return(

{text}

        )
    }

    onClick = () => {
        this.setState({text: "i got clicked!"})
        this.props.onClick()
    }

    setText = name => this.setState({text: `${name} set my text`})
}

In general, React disapproves playing with tis internal lifecycle function such has render or setState has it may cause unexpected behavior later on in your app.

Everything that you put in a Component's state is only readable by this component, and nothing else. As the docs will also tell you, the state may only be modified by the setState function, as it will avoid unexpected behaviors in the re-rendering process.

If some components need to modify what each others are going to render, then the values determining the ouput of their render function should be stored in their first common parent component.

A working live implementation :

class Test extends React.Component {
 constructor(props) {
  super(props)
  this.state = {}
 }

 setText = (source, dest) => event => {
  this.setState({
   [dest]: `Received text: Component n°${source + 1} set my text`,
   [source]: 'I got clicked!'
   })
 }

 render() {
  return (

    {[1, 2, 0].map((dest, index) => <WrappedComponent onClick={this.setText(index, dest)} text={this.state[index]}/>)}

  );
 }

}

class WrappedComponent extends React.Component { //I left this component stateful for future modifications

 render() {
  const { text, onClick } = this.props
  return (

{text || 'No one defined my text (yet)'}

  )
 }
}

ReactDOM.render(<Test/>, document.getElementById('root'))

Here every component's text is stored in their parent component dynamically.


Binary search traversal with in/pre/post order and BFS/DFS I have the following code for the BST for the inorder, postorder, preorder, breadth first and depth first traversals. Can you review and let me know the optimisation points and issues, if any?

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BST {

    static class Node {

        int data;
        Node right, left;

        Node(int data) {
            this.data = data;
            right = left = null;
        }

        @Override
        public String toString() {
            return "Node [data=" + data + ", right=" + right + ", left=" + left + "]";
        }

    }

    public static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public static void inOrder(Node root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + " ");
            inOrder(root.right);
        }
    }

    public static void postOrder(Node root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + " ");
        }
    }

    public static void breadthFirstTraversal(Node root) {
        Queue<Node> queue = new ArrayDeque<Node>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            System.out.print(node.data + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public static void depthFirstTraversal(Node root) {
        Stack<Node> stack = new Stack<Node>();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.data + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

        }
    }

    public static Node insert(Node node, int data) {
        if (node == null) {
            return new Node(data);
        }
        Node cur;
        if (data <= node.data) {
            cur = insert(node.left, data);
            node.left = cur;
        } else {
            cur = insert(node.right, data);
            node.right = cur;
        }
        return node;
    }

    public static void main(String args[]) {
        BST bst = new BST();
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        Node root = null;
        while (t-- > 0) {
            int data = sc.nextInt();
            root = insert(root, data);
        }

        System.out.println("Preorder :");
        preOrder(root);
        System.out.println("\nInOrder ");
        inOrder(root);
        System.out.println("\nPostOrder ");
        postOrder(root);
        System.out.println("\nBreadth First Traversal ");
        breadthFirstTraversal(root);
        System.out.println("\nDepth First Traversal ");
        depthFirstTraversal(root);
    }

}

There is only one point I can state: in your constructor of Node you don't need to explicitly set left and right to null. The Java runtime system will do that for you. Also, note that DFS and preorder traversal are doing the same thing so you might want to consider removing one. Since your binary tree is not guaranteed to be balanced, I would retain the DFS as it allocates your stack on the heap, and so it is invulnerable to stack overflow as your recursive preorder traversal routine.


Using a for-loop or sleeping to wait for short intervals of time I need to wait for short intervals of time in my program, but I really don't want to include unistd.h just to use sleep, so I'm doing it this way:

int main()
{
for(int i=0; i<=100000000000; i++); // <----- note that the loop doesn't do anything
return 0;
}

I do this when I don't really have a specific interval to set for sleep.

Is there anything wrong with this?  Would this harm the program in any way?

In C I know that if I did include unistd.h, and that if I used sleep(), that the following code would also make the program wait for a short interval of time:

int main()
{
sleep(2000); //or whatever the number (in milliseconds)
return 0;
}

The biggest problem with using a for-loop to do this is that you are wasting CPU power.

When using sleep, the CPU can, in a sense, take a break (hence the name "sleep") from executing your program. This means that the CPU will be able to run other programs that have meaningful work to do while your program waits.

But in the for-loop the CPU continuously have to do work to increase a variable. For what purpose? Nothing. But the CPU doesn't know that. It's told to increase the variable, so that's what it will do. Meanwhile, other programs aren't given as much time to do their work because your program is taking up time.

Please don't waste CPU power, use the sleep approach.

As stated in a comment, additionally, the compiler may optimize out an empty loop, and the attempt to pause may be lost. So either you will waste CPU power, or you will not pause at all.


Decide if 4 lengths form a square, rectangle or neither I have a list of lists of 4 integers, each representing the length of one side of a tetragon in clockwise order (so each number is the length of the side of the right-hand-adjacent-side of the previous one). Integers can be negative or positive or 0.

My idea is that if any of the sides are less than or equal to 0 then it's not a valid tetragon. Then if the lengths of all the sides are equal then it can form a square. Then if lengths of opposing sides are equal then it can form a rectangle, otherwise it's neither.

tgons=[[1,1,1,1],[1,2,1,2],[1,2,3,4],[-1,-2,-1,-2],[1,0,1,0]]
squares=0
rects = 0
neithers = 0
for gon in tgons:
    if any(n <= 0 for n in gon): #if any integers <= 0, it's invalid
        neithers+=1
    elif len(set(gon)) == 1: #if all integers are equal, it's a square
        squares+=1
    elif gon[0] == gon[2] and gon[1] == gon[3]: #if both pairs of opposing sides have equal length, it's a rectangle
        rects+=1
    else:
        neithers+=1
print squares,rects,neithers

This code apparently fails one out of a few test cases (on a certain website). I've thrown all the test cases I could think of at it and I've not been able to get it to fail so far. Is there really a test case that it fails?

Why do we need a set to find a square?
Why is a square not a subset of rectangle?
You can do the any check in the gon[0] == gon[2].
Why no filter on length of gon? Pentagons aren't squares...
gon is a poor name... do you mean polygon?
I agree with holroy, -5 makes sense, but 0 does not.

So I would do:

for shape in tgons:
    if shape[0] == shape[2] > 0 and shape[1] == shape[3] > 0 and len(shape) == 4:
        if shape[0] == shape[1]:
            squares += 1
        else:
            rects += 1
    else:
        neithers += 1

This can also be changed to allow all 2D rects/squares. (not lines.)

if shape[0] == shape[2] != 0 and shape[1] == shape[3] != 0 and len(shape) == 4:

Also follow PEP8 a bit more, as then you'll have easier to read code.
You mostly need more spaces:

Before and after infix operators.
After but not before commas.


Dijkstra's algorithm using a dictionary for the priority queue Unrelated to code:

This is my first project in Python using classes and algorithms.
I have spent the last week self teaching myself about queues and stacks, so I am NOT trying to use any Python libraries for this as I would like to know how to implement my own priority queue

About the code:

Dictionary used for priority queue.
Priority queue should be its own class, but I dont know how to call a method from one class to another, I did research this and came across staticmethod but was unsure of its implementation.
This was all done on one single file.

What I would like from this:

A way to get the input for graph without having it already 'created'
when code is run. I had an idea to get user input for each node and
its arc length to every other node, but this is inefficient for
larger graphs.
General advice/feedback/issues with my code/logic

class Graph:

    def __init__(self):
        self.nodes = {}

    def add_node(self, key, neighbours):
        self.nodes[key] = neighbours

    def shortest_path(self, start, finish):
        distance = {}  # stores distance to start node of a vertex
        visited = {}  # stores previously visited node
        queue = {}  # PQ that gives the shortest value from start to a vertex

        for node in self.nodes:
            if node == start:
                distance[node] = 0  # as distance from start node is 0
                queue[node] = 0  # value of root node to root node is 0

            else:
                distance[node] = 1000  # set unvisited nodes arc length to large value
                queue[node] = 1000

        while len(queue) != 0:
            if start == finish:
                print("start node and end node are same so distance is 0")
                break

            # works out arc with lowest weight
            lowest = 1000
            lowest_key = None
            for key in queue:
                if queue[key] < lowest:
                    lowest = queue[key]
                    lowest_key = key
            del queue[lowest_key]

            if distance[lowest_key] == 1000:
                print("No traversable paths left")
                break

            elif lowest_key == finish:
                shortest_path = []
            while True:
                temp_val = visited[lowest_key]
                shortest_path.append(temp_val)
                lowest_key = visited[lowest_key]
                if lowest_key == start:
                     break
            print(shortest_path)

            else:
                for neighbour in self.nodes[lowest_key].keys():  # checks neighbours of node released from pq
                    # adds value of neighbour arc to distance of previous node
                    alt_path = distance[lowest_key] + self.nodes[lowest_key][neighbour]
                    # if new path is shorter than distance of node in pq , then pq should be updated
                    if alt_path < distance[neighbour]:
                        distance[neighbour] = alt_path  # changes distance
                        visited[neighbour] = lowest_key  # adds this node to visited dict
                        # now changes are made to pq
                        for node in queue.keys():
                            if node == neighbour:
                                queue[node] = alt_path

g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D',{'B': 2, 'C': 9})
g.shortest_path("A",'D')

A bug

For the shortest path from A to D, your implementation shows [B, A], which is wrong.

Indentation error

while True:
    temp_val = visited[lowest_key]
    shortest_path.append(temp_val)
    lowest_key = visited[lowest_key]
    if lowest_key == start:
        break
    print(shortest_path)

should be indented once to the right; otherwise your code does not compile.

Efficiency

Use the priority queue in order to speed up your implementation:

import heapq

class HeapEntry:
    def __init__(self, node, priority):
        self.node = node
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

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

    def add_node(self, key, neighbours):
        self.nodes[key] = neighbours

    def traceback_path(self, target, parents):
        path = []
        while target:
            path.append(target)
            target = parents[target]
        return list(reversed(path))

    def shortest_path(self, start, finish):
        OPEN = [HeapEntry(start, 0.0)]
        CLOSED = set()
        parents = {start: None}
        distance = {start: 0.0}

        while OPEN:
            current = heapq.heappop(OPEN).node

            if current is finish:
                return self.traceback_path(finish, parents)

            if current in CLOSED:
                continue

            CLOSED.add(current)

            for child in self.nodes[current].keys():
                if child in CLOSED:
                    continue
                tentative_cost = distance[current] + self.nodes[current][child]

                if child not in distance.keys() or distance[child] > tentative_cost:
                    distance[child] = tentative_cost
                    parents[child] = current
                    heap_entry = HeapEntry(child, tentative_cost)
                    heapq.heappush(OPEN, heap_entry)

g = Graph()
g.add_node('A', {'B': 5, 'C': 1})
g.add_node('B', {'D': 2, 'A': 5})
g.add_node('C', {'D': 9, 'A': 1})
g.add_node('D', {'B': 2, 'C': 9})
print(g.shortest_path("A", 'D'))

Note also that we do not need anymore

for node in self.nodes:
    if node == start:
        distance[node] = 0
        queue[node] = 0
    else:
        distance[node] = 1000
        queue[node] = 1000

Think about what happens if the graph is large but the terminal nodes are close to each other: you waste a lot of CPU cycles.

Hope that helps.


Movie search layout tweaks with cookie persistence This works as intended, but was wondering if there is a more efficient way of coding this.

if (window.location.href.indexOf('/search/') >= 0) {
    switch ($.cookie("Layout")) {
        case "Poster":
            $("link:first").attr("href", "../css/list.css");
            break;
        case "Description":
            $("link:first").attr("href", "../css/desc.css");
    }
    $(function () {
        $(".Poster").click(function () {
            $("link:first").attr("href", "../css/list.css");
            $.cookie("Movie_Layout", "Poster", {
                expires: 365,
                path: '/media/search',
                secure: true
            });
            $('.content-genre, .searchresults').hide().delay(75).fadeIn(275);
            window.scrollTo(0, 0);
        });
        $(".Description").click(function () {
            $("link:first").attr("href", "../css/desc.css");
            $.cookie("Movie_Layout", "Description", {
                expires: 365,
                path: '/media/search',
                secure: true
            });
            $('.content-genre, .searchresults').hide().delay(75).fadeIn(275);
            window.scrollTo(0, 0);
        });
    });
} else {
    switch ($.cookie("Layout")) {
        case "Poster":
            $("link:first").attr("href", "css/list.css");
            break;
        case "Description":
            $("link:first").attr("href", "css/desc.css");
    }
    $(function () {
        $(".Poster").click(function () {
            $("link:first").attr("href", "css/list.css");
            $.cookie("Movie_Layout", "Poster", {
                expires: 365,
                path: '/media',
                secure: true
            });
            $('.content-genre, .searchresults').hide().delay(75).fadeIn(275);
            window.scrollTo(0, 0);
        });
        $(".Description").click(function () {
            $("link:first").attr("href", "css/desc.css");
            $.cookie("Movie_Layout", "Description", {
                expires: 365,
                path: '/media',
                secure: true
            });
            $('.content-genre, .searchresults').hide().delay(75).fadeIn(275);
            window.scrollTo(0, 0);
        });
    });
}

This seems a bit simpler (in terms of code repeating)

var Layout = {
    'Poster': {
        href: 'css/list.css'
    },
        'Description': {
        href: 'css/desc.css'
    }
};

function setLink(file, pathFix) {
    $('link:first').attr('href', pathFix + file);
}

$(function () {
    var currentPathFix = '',
        initialLayout = $.cookie("Layout");
    if (window.location.href.indexOf('/search/') >= 0) {
        currentPathFix = '../';
    }
    setLink(Layout( initialLayout ), currentPathFix );
    $.each(Layout, function (key, item) {
        $('.' + key).click(function () {
            setLink(item.href, currentPathFix);
            $.cookie("Movie_Layout", key, {
                expires: 365,
                path: '/media/search',
                secure: true
            });
            $('.content-genre, .searchresults').hide().delay(75).fadeIn(275);
            window.scrollTo(0, 0);
        });
    });
});


Dynamic two-column list, "Vertical Wrap" I have created a very simple script that will create two columns which are populated by an array. It works, but I am certain that the way that I have gone about it is not the best way. I have been searching for simple, sample scripts which would aide me in understanding how to best approach this, but all of them have been too specific to their application.

This is what I have made:

$assets = array('Bag', 'Charger', 'Power Cable', 'Video Cable',
    'Mouse', 'Keyboard', 'Test', 'Test 2', 'Test 3');
$assets_count = count($assets);

$halfway_raw = $assets_count / 2;
$halfway = round($halfway_raw, 0) - 1;

echo '
';

for($i = 0; $i < $assets_count; $i++) {
    if($i == $halfway) {
        echo '
' . $assets[$i] . '
';
        echo '
';
        echo '
';
    } else {
        echo '
' . $assets[$i] . '
';
    }
}

echo '
';

I'm looking for something that scales easily and is obviously as small as possible, which I don't think my script is.

Well, this is more concise, and it should be easy enough to scale:

<?php
$assets = array('Bag', 'Charger', 'Power Cable', 'Video Cable', 'Mouse', 'Keyboard', 'Test', 'Test 2', 'Test 3');

$half   = ceil(count($assets)/2);

$columns = array(
  array_slice($assets, 0, $half), // first half
  array_slice($assets, $half)     // second half
);

foreach( $columns as $index => $column ) {
  $index += 1;
  echo "

" . implode("

", $column) . "

";
}
?>

Basically, it's using more built-in PHP functions and constructs (array_slice, implode, foreach) but is functionally identical to the original.