Filtering a large (50gb+) JSON lines file matching CIDR's I'm trying to speed up a Python script that reads a large log file (JSON lines, 50gb+) and filter out results that match 1 of 2000 CIDR ranges.

Logfile

20 million lines

{"ip":"xxx.xxx.xxx.xxx","timestamp":"2017-05-27T04:00:35-04:00","data":{},"error":"EOF","error_component":"banner"}
{"ip":"xxx.xxx.xxx.xxx","timestamp":"2017-05-27T04:00:35-04:00","data":{"banner":"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx","ehlo":"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx","starttls":"500 Unknown command\r\n"},"error":"Bad return code for STARTTLS","error_component":"starttls"}
{"ip":"xxx.xxx.xxx.xxx","timestamp":"2017-05-27T04:00:35-04:00","data":{},"error":"EOF","error_component":"banner"}
{"ip":"xxx.xxx.xxx.xxx","timestamp":"2017-05-27T04:00:35-04:00","data":{"banner":"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx","ehlo":"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx","starttls":"502 No such command\r\n"},"error":"Bad return code for STARTTLS","error_component":"starttls"}

CIDR file

2,000 lines

86.80.0.0/12
77.160.0.0/12
188.200.0.0/13
178.224.0.0/13
84.24.0.0/13

Script

import sys
import json
from netaddr import *

reload(sys)
sys.setdefaultencoding('utf-8')

filename = 'results.json'
filename = unicode(filename, 'utf-8')
cidr_filename = 'cidr.txt'

rowcount = 0
count = 0

# Load CIDR ranges
with open(cidr_filename, 'r') as f:
    cidr = [line.strip() for line in f]

# Load JSON line by line
with open(filename) as f:
    for line in f:
        output = json.loads(line)
        rowcount += 1

        # Match if IP is in CIDR ranges
        if all_matching_cidrs(output['ip'], cidr):
            if 'banner' in output['data']:
                print(output['ip'] + '\t' + output['data']['banner'])
                count += 1

print('---------------------------------------')
print('LINES:   {rowcount}')
print('RESULTS: {count}')
print('---------------------------------------')

Current results

Parsing an example set of 100,000 rows takes now 8 minutes using:

Pypy
MacBook Pro with 2.8 GHz Intel Core i7, 16Gb RAM, SSD

Parsing the complete set of 20,000,000 rows would take a staggering 26 hours.

---------------------------------------
LINES:   100000
RESULTS: 1243
---------------------------------------

real    7m57.739s
user    7m52.127s
sys     0m4.177s

The bottleneck is the number of CIDR ranges to search within, when I run an example set of 100,000 row against 1 CIDR range it takes only 1.2 seconds.

---------------------------------------
LINES:   100000
RESULTS: 4
---------------------------------------

real    0m1.201s
user    0m1.095s
sys     0m0.090s

Is there a faster way of accomplishing this? Would Multithreading/Multiprocessing speed things up? Any help or other feedback would be much appreciated!

Things I've done:

Using Pypy, this is 9x(!) faster than Python 2.7 for this job.
Tried using Tim Bray's Widefinder but couldn't make it work as it focuses on regex searches IMHO.

UPDATE

rolfl's solution brought my times to parse 20,344,457 rows from ±26 hours to 4.5 minutes!

---------------------------------------
LINES:   20344457
RESULTS: 130863
---------------------------------------

real    4m27.661s
user    3m55.171s
sys     0m26.793s

TemporalWolf's advice to cProfile my code showed that indeed json.loads() was a bottleneck:

ncalls    tottime  percall  cumtime  percall filename:lineno(function)
16607394  131.960    0.000  131.960    0.000 {_pypyjson.loads}

Following his advice to slice the IP address natively instead of loading each line as JSON it was 2.5x times faster!

---------------------------------------
LINES:   20344457
RESULTS: 130863
---------------------------------------

real    1m40.548s
user    1m13.885s
sys     0m22.664s

Is there a faster way of accomplishing this? Would Multithreading/Multiprocessing speed things up? Any help or other feedback would be much appreciated!

No, for the most part, multi-threading will make no difference for you. At some point the bottleneck should be the IO speed of reading 50GB of file content, and not the speed of the processing. You also need to read the file sequentially (I presume) to get the output in the same order as the input.

But, fundamentally, the solution should not need to have multi-threaded execution in order to improve the performance.

Learning how to measure performance of various parts of your code is an important skill. For the moment, it may be as simple as timing this code:

# Load JSON line by line
with open(filename) as f:
    for line in f:
        output = json.loads(line)
        rowcount+=1

i.e. convert each line from JSON, and count the lines.... how fast is that? I would expect that the whole program should be just as fast when the IP CIDR lookups work fast too.

Your performance issue is almost certainly related to this line here:

if all_matching_cidrs(output['ip'], cidr):

Your timings already support this.... it takes 1 second to search all records in 1 CIRD, but significantly longer for 2000 CIDRs...

So, you have a performance problem in the order of \$O(mn)\$ where \$m\$ is the number of rows in the file, and \$n\$ is the number of CIDRs.

You can't improve the performance related to the number of rows in the files, but you can improve the cost of the CIDR lookups. What if it was a fixed-cost to check all CIDR matches? Then your overall performance becomes \$O(m)\$ and does not depend on the number of CIDR records.

You can do this by preprocessing the CIDR data in to a structure that allows a fixed-cost lookup.

The structure I would use is a binary tree consisting of nodes representing each bit in the CIDR specs. Each leaf node represents a CIDR to include. I.e. you preprocess the CIDRs in to the tree that at most has 32 levels (for a /32 CIDR).

Then, for the lookup, you take your IP from the JSON, convert it in to an integer, and start shifting bits from the most significant. For each bit, you start descending the CIDR tree, and if you can descend the tree until you hit a leaf node, then you have found a matching CIDR. At most, this will be 32 iterations down the tree, but for the most part, CIDR's seldom are that specific. So, let's assume at most a /24 CIDR, meaning that you reduce your lookups to at most 24 descents, instead of as many as 2000 complete checks.

It comes down to the algorithm.

Update - example lookup

Note, I hacked together this tree for supporting faster lookups of IPs in a number of CIDR ranges. Python is not my primary language, so inspect it carefully, and adjust as needed. Specifically, I have used some naive mecheanisms for parsing IP addresses in to integers. Use dedicated libraries to do that instead.

You can see it running on ideone: https://ideone.com/cd0O2I

def parseIPPart(ipx, shift):
    try:
        return int(ipx) << shift
    except TypeError:
        return 0

def parseIP(ipString):
    ips_shifts = zip(ipString.split("."), range(24, -1, -8))

    addr = [parseIPPart(ip, shift) for ip, shift in ips_shifts]
    return sum(addr)

def parseCIDR(cidr):
    addrString, bitsString = cidr.split('/')
    try:
        bits = int(bitsString)
    except TypeError:
        bits = 32
    addr = parseIP(addrString)
    return addr, bits

class CIDRTree:
    class CIDRNode:
        def __init__(self, depth):
            self.depth = depth
            self.isset = None
            self.unset = None
            self.leaf = False

    def __init__(self):
        self.root = CIDRTree.CIDRNode(-1)

    def addCIDR(self, cidr):
        ip, bits = parseCIDR(cidr)
        node = self.root
        for b in range(bits):
            if node.leaf:
                # Previous bigger CIDR Covers this subnet
                return
            mask = 1 << (31 - b)

            if (ip & mask) != 0:
                if node.isset is None:
                    node.isset = CIDRTree.CIDRNode(b)
                kid = node.isset
            else:
                if node.unset is None:
                    node.unset = CIDRTree.CIDRNode(b)
                kid = node.unset
            node = kid
        # node is now a representation of the leaf that comes from this CIDR.
        # Clear out any more specific CIDRs that are no longer relevant (this CIDR includes a previous CIDR)
        node.isset = None
        node.unset = None
        node.leaf = True
        #print("Added CIDR ", ip, " and bits ", bits)

    def matches(self, ipString):

        ip = parseIP(ipString)
        node = self.root
        shift = 0
        while node is not None and not node.leaf:
            shift += 1
            mask = 1 << (32 - shift)
            val = (ip & mask) != 0
            node = node.isset if val else node.unset

        return node is not None and node.leaf

if __name__ == "__main__":
    cidrTree = CIDRTree()
    cidrTree.addCIDR("8.0.0.0/8")
    cidrTree.addCIDR("9.8.7.0/24")

    print ("Tree matches 8.8.8.8:", cidrTree.matches("8.8.8.8"))
    print ("Tree matches 9.9.9.9:", cidrTree.matches("9.9.9.9"))
    print ("Tree matches 9.8.7.6:", cidrTree.matches("9.8.7.6"))


Cursor module for a text-editor A few weeks ago, I had started to write a text-editor in C++ using SFML library. The work is now paused pretty much because I am a lazy freak. So, I thought I might use this passive time to get reviews on what I have done so far.

As of now, I want to get reviews on the cursor module (for displaying a blinking cursor), I wrote for the text-editor. I am posting the code as it was written and it was written without many comments. (I am not sure if I am supposed to add comments before putting it up for review on the site.)

Cursor.h:

#ifndef CURSOR_H_INCLUDED
#define CURSOR_H_INCLUDED

#include<iostream>
#include<SFML/Graphics.hpp>

class Cursor{
    private:
    sf::Color color;
    sf::RectangleShape cursorLine;
    sf::Clock clock;
    int col, line;
    int txtX, txtY;
    int maxCol;
    float thickness, length;
    int blinkPeriod, lastTime;
    bool visible;

    public:
    float getCol();
    float getLine();
    float getLength();
    float getThickness();
    void move(int, int);
    void setPosition(int,int);
    void setDefaultValues();
    Cursor();
    Cursor(float, float, float, float, int, int, int);
    void draw(sf::RenderWindow *);
    void update();
};

#endif // CURSOR_H_INCLUDED

Cursor.cpp:

#include "Cursor.h"

void Cursor::setDefaultValues(){
    col = 1;
    line = 1;
    lastTime = 0;
    thickness = 2;
    length = 20;
    blinkPeriod = 400;
    visible = true;
    color = sf::Color(0,255,0);
}

Cursor::Cursor(){
    setDefaultValues();
}

Cursor::Cursor(float x, float y, float len, float thick, int txX, int txY, int maxCol){
    setDefaultValues();
    this->maxCol = maxCol;
    txtX = txX;
    txtY = txY;
    col = x;
    line = y;
    length = len;
    thickness = thick;
}

float Cursor::getCol(){
    return col;
}

float Cursor::getLine(){
    return line;
}

float Cursor::getLength(){
    return length;
}

float Cursor::getThickness(){
    return thickness;
}

void Cursor::move(int dx, int dy){
    if(dx>0){
        if(col+dx<=maxCol)col += dx;
        else{
            col = 2;
            line += 1;
        }
    }
    else{
        if(col+dx>0) col +=dx;
        else{
            if(line>1){
                line -= 1;
                col = maxCol-1;
            }
        }
    }
    if(line+dy>0)line+= dy;
}

void Cursor::setPosition(int dx, int dy){
    col = dx;
    line= dy;
}

void Cursor::update(){
    cursorLine.setFillColor(color);
    cursorLine.setSize(sf::Vector2f(thickness, length));
    if((clock.getElapsedTime().asMilliseconds()-lastTime)>blinkPeriod){ visible = !visible;
    lastTime = clock.getElapsedTime().asMilliseconds();
    }
    cursorLine.setPosition((col-1)*(length*0.6)+txtX, (line-1)*(length*1.2)+txtY);
}

void Cursor::draw(sf::RenderWindow *screen){
    if(visible) screen->draw(cursorLine);
}

The names 'txtX' and 'txtY' don't say anything about the domain as 'line', or 'length' do. Someone would need to see how are you using that variable to figure out what it is.

If you want to make the code more readable, make explanatory variables and helper descriptive methods for example

bool fitsInCurrentLine = col+dx<=maxCol;
if( fitsInCurrentLine ) col += dx;
else moveToNextLine();

instead of

if(col+dx<=maxCol)col += dx;
else{
    col = 2;
    line += 1;
}

When I read the last one, I had to figure out "how" you were doing the thing to know "what" you were doing.

Note that I did not write the moveToNextLine method but you get the Idea of what is happening. Considering col = 2; line += 1;. Is it necessary to know that the initial col is 2? or Should I only know that you are moving to the next line if the line wraps?

It reads more like "well written prose" (as Uncle Bob in his book 'CleanCode' says)

You can do similar with the else block.

In the method setPosition, I think the correct name for the parameters is x and y instead of dx or dy given that they are not changes but just absolute values.

This if statement in the update method could be its own method

void Cursor::blink(){
    bool isTimeToChangeState = (clock.getElapsedTime().asMilliseconds()-lastTime)>blinkPeriod;
    if( isTimeToChangeState ){
        visible = !visible;
        lastTime = clock.getElapsedTime().asMilliseconds();
    }
}

void Cursor::update(){
    cursorLine.setFillColor(color);
    cursorLine.setSize(sf::Vector2f(thickness, length));
    blink();
    cursorLine.setPosition((col-1)*(length*0.6)+txtX, (line-1)*(length*1.2)+txtY);
}

Finally, by reading

cursorLine.setPosition((col-1)*(length*0.6)+txtX, (line-1)*(length*1.2)+txtY);

you can sort of guess what is txtX. Is it the position of the text area? why just don't just put textAreaX and textAreaY, not perfect (I mean, for sure there should be a better name) but at least it improves a little the readability. In the book "clean code" you can find "A name that makes you go into the code to see that it tries to identify, is a bad name"

That's all I would recommend based on the book and experiences I've got as a developer. Happy coding!


When one property is calculated from another I've got a class with a property TotalCost, which is calculated by some simple math of two other properties, CostOfFood and NumberOfPeople.  The code works the way I want it to, but I was wondering if this is a satisfactory method in the long run of application development, a bad idea to have one property that depends on another all together (I'm pretty sure this is the case, but sometimes it makes sense to), or if the informed reader would deem it acceptable.  Helpful hints are in the comments.

class DinnerParty
{
    private int numberOfPeople;
    public int NumberOfPeople
    {
        get { return numberOfPeople; }
        set
        {
            numberOfPeople = value;
            //TotalCost property is updated when more people are added to the party
            TotalCost =CalculateFoodCost(value);
        }
    }
    private decimal totalCost;

    public decimal TotalCost
    {

        get { return totalCost; }
        private set
        {
            totalCost = value;
        }
    }

    private decimal costOfFood;
    public decimal CostOfFood
    {
        get { return costOfFood; }
        set
        {
            costOfFood = value;
            //TotalCost property is updated when CostOfFood changes
            //directly below line was my initial idea
            //TotalCost = value * NumberOfPeople was my initial thought
            //before overloading the CalculateFoodCost method

            //this calls the CalculateFoodCost version that takes a decimal
            TotalCost = CalculateFoodCost(value);
        }
    }
    private decimal CalculateFoodCost(int costOfFood)
    {
        //the int coming in as a parameter is the 'value' of the NumberOfPeople property
        return this.costOfFood * NumberOfPeople;

    }
    private decimal CalculateFoodCost(decimal costOfFood)
    {
        return this.costOfFood * NumberOfPeople;
    }

    public DinnerParty()
    {
        //so food cost is never 0
        CostOfFood = 10;
    }
}

Testing

DinnerParty d = new DinnerParty();
d.NumberOfPeople = 1;
Console.WriteLine(d.TotalCost);//output = 10
d.CostOfFood = 2;
Console.WriteLine(d.TotalCost);//CostOfFood changed, output =2
d.NumberOfPeople = 2;
Console.WriteLine(d.TotalCost);//output=4;
d.CostOfFood = 3;
Console.WriteLine(d.TotalCost); //output =6

The C# property model allows external classes to inspect (or set) a given member as though it were a public 'field', and the implementation details are left to the property's accessor and mutator.  In your case, you want to expose TotalCost and hide the implementation details about how it is derived.  And your code reflects best practices.

Following the comment from Clockwork-Muse, your implementation can be made more elegant by...

    public decimal TotalCost
    {
        get { return CostOfFood * NumberOfPeople; }
    }

This avoids the calculation penalty for setting either of the calculation ingredients and performs the calculation only when called upon to do so.  It's also a bit more readable and transparent.  In this particular case, there's no need for an asymmetric mutator, so it's been removed.


Counting Hamiltonian triangulations (OEIS 3122) I'm trying to translate formulas from the 3122th sequence in OEIS database, in particular this one:

B(s, m) = sum((m! / m_1! ... m_s!) * r(1)^{m_1} ... r(s)^{m_s})
where the sum is over all partitions of s such that
s = m_1 + 2*m_2 + ... + s*m_s and m = m_1 + m_2 + ... + m_s.

My complete solution is available at GitHub.
First question.  What the b(s,m) function really does isn't important, all that matters here is that I would like to store already computed values. Can one perform the memoisation in an elegant and smarter way (like Haskell here achieves)? It speeds up the computation a lot.

memoB = [[-1 for x in range(100)] for y in range(100)]

def b(s, m):
    if memoB[s][m] == -1:
        # some calculations
        memoB[s][m] = total
    return memoB[s][m]

Second (algorithmic) question.
The slowest part of my code generates all integer partitions m = m_1 + m_2 + ... + m_s such that s = m_1 + 2*m_2 + ... + s*m_s. For example, if s = 10, m = 5, these are:

[4, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[3, 1, 0, 0, 1, 0, 0, 0, 0, 0]
[3, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[2, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[2, 1, 2, 0, 0, 0, 0, 0, 0, 0]
[1, 3, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 5, 0, 0, 0, 0, 0, 0, 0, 0]

The current algorithm (coded below) finds the partitions that I am looking for, but is inefficient. Can it be improved? If yes, how?

def partitions(s, m):
    stack = [] # contains partial partitions
    matches = [] # stores good partitions
    for i in range(1 + min(s, m)):
        stack.append(([i], s - i, m - i))

    while len(stack) > 0:
        seq, s_sum, m_sum = stack.pop()
        # seq - initial section of a partition
        # s_sum - difference between s and partial sum of seq
        # m_sum - difference between m and partial sum of seq

        # if seq has already s summands and both partial sums agree,
        # it is marked as a good partition
        if len(seq) == s:
            if s_sum == 0 and m_sum == 0:
                matches.append(seq)
            continue

        # if one of the partial sums drops below zero,
        # the seq can't be continued
        if min(s_sum, m_sum) < 0 and max(s_sum, m_sum) > 0:
            continue

        # we extend the stack by all "one step continuations" of seq
        factor = len(seq) + 1
        bound = max(1, 1 + min(s_sum // factor, m_sum))
        stack.extend([(seq + [i], s_sum - i * factor, m_sum - i) for i in range(bound)])
    return matches

I know that one shouldn't name functions with single letters, but these are taken from the OEIS description directly.

To start with, the spec is badly phrased. I know it's not your fault, but it might help you (and would almost certainly help reviewers) to clarify it. It talks about partitions of s but since m = m_1 + m_2 + ... + m_s the m_i are actually a partition of m, and it requires unpicking of the definition. I suggest the following rephrasing:

  $$B(s, m) = \sum_{\lambda \vdash s,\, |\lambda| = m} \binom{m}{a_1, \ldots, a_k} r(1)^{a_1} \ldots r(k)^{a_k}$$
  where the sum is over all partitions of \$s\$ into exactly \$m\$ parts, \$\lambda = 1^{a_1} 2^{a_2} \ldots k^{a_k}\$ in the frequency representation.

Memoisation support in Python

30 seconds with Google turned up https://docs.python.org/3/library/functools.html#functools.lru_cache . If you know that you're only going to want 10000 different arguments memoised then

@lru_cache(maxsize=10000)
def b(s, m):
    ...

Optimising the integer partition search

How do you form a partition of \$s\$ into \$m\$ parts? You take a part \$p\$ and add it to a partition of \$s - p\$ into \$m - 1\$ parts. To avoid duplication you enforce that the parts are decreasing.

def partitions(s, m):
    return partitions_inner(s, m, s)

def partitions_inner(total, num_parts, max_part):
    # Each of the parts must be between 1 and max_part
    if total < num_parts or num_parts * max_part < total:
        return []
    if num_parts == 1:
        return [[total]]

    results = []
    for part in range(1, max_part + 1):
        for subpartition in partitions_inner(total - part, num_parts - 1, part):
            results.append([part] + subpartition)
    return results

This should be about as efficient as your code, but has the great advantage that partitions_inner can be memoised. Converting to frequency representation is quite simple, and in fact you could refactor this to produce output directly in frequency representation.

But that's irrelevant

If you look at how the \$B(s, m)\$ are used, you see that it's only in \$A(n, s) = \sum_{m=1}^{s} \binom{n}{m} B(s, m)\$. So \$B\$ sums over all partitions with a given number of parts, and then is summed over all numbers of parts. If you cut out the middle-man you get just $$A(n, s) = \sum_{\lambda\vdash s} \binom{n}{a_1, \ldots, a_k} r(1)^{a_1} \ldots r(k)^{a_k}$$ where the sum is over all partitions of \$s\$, \$\lambda = 1^{a_1} 2^{a_2} \ldots k^{a_k}\$ in the frequency representation.

Generating all partitions is (obviously) simpler than generating all partitions with a given number of parts.

def partitions_inner(total, max_part):
    if total == 0:
        return [[]]

    results = []
    for part in range(1, min(max_part, total) + 1):
        for subpartition in partitions_inner(total - part, part):
            results.append([part] + subpartition)
    return results

Again, this can be memoised. It's also possible to trade off memory for speed by splitting up the multinomial as $$\begin{eqnarray}T(\lambda) & = & \binom{m}{a_1, \ldots, a_k} r(1)^{a_1} \ldots r(k)^{a_k} \\
A(n, s) & = & \sum_{\lambda\vdash s} \binom{n}{m} T(\lambda)\end{eqnarray}$$ where the sum is over all partitions of \$s\$, \$\lambda = 1^{a_1} 2^{a_2} \ldots k^{a_k}\$ in the frequency representation, and \$m = \sum_i a_i\$. \$T(\lambda)\$ can be memoised, but also it can be calculated incrementally by using a more complicated object to store the partitions instead of just an array of the parts:

class Partition:
    def __init__(self, maxPart, tail = None):
        self.part = maxPart
        self.tail = tail
        if tail is None:
            self.partFreq = 1
            self.numParts = 1
            tailTerm = 1
        else:
            self.partFreq = tail.partFreq + 1 if tail.part == self.part else 1
            self.numParts = tail.numParts + 1
            tailTerm = tail.term
        self.term = tailTerm * r(self.part) * self.numParts // self.partFreq

@lru_cache(maxsize=100)
def partition(n):
    accum = []
    for maxPart in range(1, n):
        for tail in partition(n - maxPart):
            if tail.part > maxPart:
                break

            accum.append(Partition(maxPart, tail))
    accum.append(Partition(n))
    return accum

(Note that I'm not a Pythonista and I haven't checked the above code against PEP8).


Reversal of a singly-linked list in Rust I was trying to write some simple data structures to practice ownership concepts in Rust:

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

struct List<T> {
    head: Link<T>,
}

pub struct Iter<'a, T: 'a> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push_front(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn reverse(&mut self) {
        if self.head.is_none() || self.head.as_ref().unwrap().next.is_none() {
            return;
        }

        let mut prev = None;
        let mut current_node = self.head.take();
        while current_node.is_some() {
            let next = current_node.as_mut().unwrap().next.take();
            current_node.as_mut().unwrap().next = prev.take();
            prev = current_node.take();
            current_node = next;
        }

        self.head = prev.take();
    }

    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

fn main() {
    let mut l = List::new();
    l.push_front(3);
    l.push_front(2);
    l.push_front(1);
    l.push_front(12);

    for item in l.iter() {
        print!("{} ", item);
    }
    println!();
    l.reverse();
    for item in l.iter() {
        print!("{} ", item);
    }
    println!();
}

Link to Rust Playground

Before I begin, I recommend reading Learning Rust With Entirely Too Many Linked Lists.

Avoid unwraps, especially those after checking is_some. Use pattern matching instead.
The first test in reverse is redundant with the rest of the logic.
Implement Debug or Display to DRY up the printing of the list.
You should have some tests, especially for edge cases: 0, 1, and 2 items.
I'm not a fan of side effects inside of a map - it should err more on the side of purely functional. I'd use a match, even though it's more lines of code.
I'd simplify the iterator by just keeping a &Link
You could choose to remove the temporary variable from push_front.
for item in foo.iter() is usually written as for item in &foo, which implies that you need to implement IntoIterator for a reference to your type.

use std::fmt;

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

struct List<T> {
    head: Link<T>,
}

pub struct Iter<'a, T: 'a> {
    next: &'a Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push_front(&mut self, elem: T) {
        self.head = Some(Box::new(Node {
            elem: elem,
            next: self.head.take(),
        }));
    }

    pub fn reverse(&mut self) {
        let mut prev = None;
        let mut current_node = self.head.take();

        while let Some(mut current_node_inner) = current_node.take() {
            let next = current_node_inner.next.take();
            current_node_inner.next = prev.take();
            prev = Some(current_node_inner);
            current_node = next;
        }

        self.head = prev.take();
    }

    pub fn iter(&self) -> Iter<T> {
        Iter { next: &self.head }
    }
}

impl<'a, T> IntoIterator for &'a List<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.next.as_ref() {
            Some(next) => {
                self.next = &next.next;
                Some(&next.elem)
            }
            None => None,
        }
    }
}

impl<T> fmt::Debug for List<T>
    where T: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for item in self {
            write!(f, "{:?} ", item)?;
        }
        Ok(())
    }
}


Fetching counties and localities using JSON API calls I'm using the below code to call different methods from an API:

import requests
import json
from unidecode import unidecode
from datetime import datetime

temp_county = 'County'
temp_locality = 'Locality'

# Function - login

session = requests.Session()

def login():
    # Application header
    header = {
        'Content-Type': 'application/json',
        'Ocp-Apim-Subscription-Key': '{KEY}'
    }

    # User's credentials
    body_login = {
        'username': 'user',
        'password': 'pass'
    }

    # Make the login request and return the token
    request_url = session.post(
        'https://urgentcargus.azure-api.net/api/LoginUser', json=body_login, headers=header)

    # Parse the token and remove double quotes
    token = 'Bearer ' + request_url.text.strip('"')

    return token

# Get country code. Since it's a local product, the request will return only the code for RO

def countries():
    # Application header
    header = {
        'Authorization': login(),
        'Ocp-Apim-Subscription-Key': '{KEY}'
    }
    # Make the request and return the country code
    request_url = session.get(
        'https://urgentcargus.azure-api.net/api/Countries', headers=header
    )

    countries_dictionary = request_url.json()

    for country in countries_dictionary:
        if country['Abbreviation'] == 'RO':
            countryId = str(country['CountryId'])

    return countryId

def counties():
    # Application header
    header = {
        'Authorization': login(),
        'Ocp-Apim-Subscription-Key': '{KEY}'
    }
    # Load the country id
    params = {
        'countryId': countries()
    }

    # Make the request and return the county code based on the city
    request_url = session.get(
        'https://urgentcargus.azure-api.net/api/Counties', params=params, headers=header
    )

    counties_dictionary = request_url.json()

    # Parse the city description and transliterate it to ASCII

    county = unidecode(temp_county)

   # print(county)

    # Return the county code
    for countyName in counties_dictionary:
        if countyName['Name'] == county:
            countyId = str(countyName['CountyId'])

    return countyId

def localities():
    # Application header
    header = {
        'Authorization': login(),
        'Ocp-Apim-Subscription-Key': '{KEY}'
    }
    # Load the country id and county id
    params = {
        'countryId': countries(),
        'countyId': counties()
    }

    # Make the request and return the county code based on the city
    request_url = session.get(
        'https://urgentcargus.azure-api.net/api/Localities', params=params, headers=header, stream=True
    )

    localities_dictionary = request_url.json()

    # Parse the city description and transliterate it to ASCII

    locality = unidecode(temp_locality)

    # print(county)

    # Return the locality code
    for localityName in localities_dictionary:
        if localityName['Name'] == locality:
            localityId = str(localityName['LocalityId'])

    return localityId

#
print(login())
print(countries())
print(counties())
print(localities())

The functions are working well, with no errors or something. Problem is that it require (in my opinion) lot of time to complete all functions and return what it has to return.

I have used requests.Session() in order to create one persistent session in order to save time but somehow is the same behavior.

I've monitored how much time is required and for instance, it takes about 5 - 6 seconds to complete:

print('Process start! ' + str(datetime.now()))

# here are all the functions

print('Process ended! ' + str(datetime.now()))

Terminal response:

Process start! 2019-10-18 13:26:09.796132
Bearer 8JCAOoSSevSpcNDydLHSAmZORL0RGgDXV110IUhxIRWABX0TNj
1
26
163
Process ended! 2019-10-18 13:26:14.663092

Is there any way to improve it?

Basically you need to reuse your session variable on the code, for example:

print(login(session))
print(countries(session))
print(counties(session))
print(localities(session))

And inside that functions change the calls that referrers to "requests" to the "session" variable like:

request_url = session.get(
    'https://urgentcargus.azure-api.net/api/Localities',...


Hours of operation display I'm working on an hours of operation display, which list the hours out:

Monday - Friday / 8 - 4
Saturday / 8 - 2
Sunday / Closed

I have my script add a class to highlight the lines depending on which day of the week it is, but I wonder another way to complete the task. I would like it if I was able to define monday-friday as one instead of the entire list of them in classes.

var now = new Date();
var weekday = new Array(7);
weekday[0] = "Sunday";
weekday[1] = "Monday";
weekday[2] = "Tuesday";
weekday[3] = "Wednesday";
weekday[4] = "Thursday";
weekday[5] = "Friday";
weekday[6] = "Saturday";

var checkTime = function() {
  var today = weekday[now.getDay()];
  var timeDiv = document.getElementById('timeDiv');
  var dayOfWeek = now.getDay();
  var hour = now.getHours();
  var minutes = now.getMinutes();

  //add AM or PM
  var suffix = hour >= 12 ? "PM" : "AM";

  // add 0 to one digit minutes
  if (minutes < 10) {
    minutes = "0" + minutes
  };

  if ((dayOfWeek == 6) && hour >= 8 && hour <= 14) {
    hour = ((hour + 11) % 12 + 1); //i.e. show 1:15 instead of 13:15
    timeDiv.innerHTML = '' + today + ' ' + hour + ':' + minutes + suffix + ' - we\'re open!';
    timeDiv.className = 'open';
  }

  else if ((dayOfWeek == 1 || dayOfWeek == 2 || dayOfWeek == 3 || dayOfWeek == 4  || dayOfWeek == 5) && hour >= 8 && hour <= 16) {
    hour = ((hour + 11) % 12 + 1);
    timeDiv.innerHTML = 'Hi!! ' + today + ' ' + hour + ':' + minutes + suffix + ' - we\'re open!';
    timeDiv.className = 'open';
  }

  else {
    if (hour == 0 || hour > 12) {
      hour = ((hour + 11) % 12 + 1); //i.e. show 1:15 instead of 13:15
    }
    timeDiv.innerHTML = ' Sorry—we\'re closed!';
    timeDiv.className = 'closed';
  }
};

    var currentDay = weekday[now.getDay()];
    var currentDayCLASS = "." + currentDay; //gets todays weekday and turns it into     class
    $(currentDayCLASS).toggleClass("today"); //hightlights today in the view hours

    setInterval(checkTime, 1000);
    checkTime();

Hours

Monday - Friday

8:00am - 4:00pm

Saturday

8:00am - 2:00pm

Sunday

Closed

You can try something like this:

Create a list of utility function that you might want to use. You can export them to a utility file. This will keep code clean and maintainable.

isWorkingDay: Monday - Friday
isWorkingHours: Start at 8am and for working day end at 4pm. On Saturday, end at 2pm.
getDoubleDigitNumber: This will be helpful for both hours and minutes.
getHoursIn12HrFormat: To get hours in 12 hour format.
getDayText: To get name of day.

Now, in you main file, you can write a formatter function that would give you date time in specific format.
In your checkTime function, you do not want to write much logic. Use your utility functions and add any specific logic to mutate DOM.
Since you are dealing with classes, you should avoid className. This will replace all existing classes. Instead, use .classList. It provides many useful utilities.

Following is a sample:

function getDoubleDigit(value) {
  return ("00" + value).slice(-2);
}

function getHourIn12HrFormat(hour) {
  hour = hour || new Date().getHours();
  // This can be written as:
  // return hour % 12 || 12;
  return ((hour + 11) % 12 + 1);
}

function isWorkingDay(day) {
  return day !== 0 && day !== 6;
  // This can also be weitten as
  // return day > 0 && day < 6;
}

function isWorkingHours(hour) {
  hour = hour || new Date().getHours();
  return hour >= 8 && (isWorkingDay() && hour <= 16 || !isWorkingDay() && hour <= 14);
}

function getDayText(day) {
  var weekday = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday'];
  day = day || new Date().getDay();
  return weekday[day]
}

function getDateTimeString(date) {
  var now = date || new Date();
  var today = getDayText();
  var minutes = now.getMinutes();
  var hour = now.getHours();
  //add AM or PM
  var suffix = ["PM", "AM"][hour % 12];
  return today + ' ' + getHourIn12HrFormat() + ':' + minutes + suffix

  // If you are ok to use moment.js, all the above code can be converted to:
  // return moment().format('dddd hh:mm A')
}

var checkTime = function() {
  var now = new Date();
  var timeDiv = document.getElementById('timeDiv');
  var dayOfWeek = now.getDay();

  // reset classes and only add necessary class.
  timeDiv.classList.remove('open,close');
  if (isWorkingHours() && dayOfWeek !== 0) {
    timeDiv.innerHTML = ((isWorkingDay() ? 'Hi!! ' : '') + getDateTimeString() + ' - we\'re open!');
    timeDiv.classList.add('open');
  } else {
    timeDiv.innerHTML = ' Sorry—we\'re closed!';
    timeDiv.classList.add('closed');
  }
};

var currentDay = getDayText();
var currentDayCLASS = "." + currentDay; //gets todays weekday and turns it into     class
$(currentDayCLASS).toggleClass("today"); //hightlights today in the view hours

setInterval(checkTime, 1000);
checkTime();
#timeDiv {
  padding: 4px;
  border: 1px solid cyan;
  background: #ddd;
}

Hours

Monday - Friday

8:00am - 4:00pm

Saturday

8:00am - 2:00pm

Sunday

Closed

As suggested by @Nitin Dhomse, you can use moment.js.

This is how your formatting code would look like with moment:

return moment().format('dddd hh:mm A')


List splitting for RLE compression algorithm I try to implement a simple RLE compression algorithm as a learning task. In the first step, i need to split my source list to sequences of repeating and non-repeating elements. I've done it, but code seems to be so ugly. Can I simplify it?

src = [1,1,2,3,3,4,2,1,3,3,4,3,3,3,3,3,4,5]

from itertools import izip

isRepeat = False
sequence = []

def out(sequence):
    if sequence:
        print sequence

def testRepeate(a, b, pr):
    global isRepeat
    global sequence
    if a == b:
        if isRepeat:
            sequence.append(pr)
        else:
            out(sequence)
            sequence = []
            sequence.append(pr)
            isRepeat = True
    else:
        if isRepeat:
            sequence.append(pr)
            out(sequence)
            sequence = []
            isRepeat = False
        else:
            sequence.append(pr)

for a, b in izip(src[:-1], src[1:]):
    testRepeate(a, b, a)
testRepeate(src[-2], src[-1], src[-1])
out(sequence)

First of all I must tell you that Python makes astonishing easy to write a Run-length encoding:

>>> src = [1,1,2,3,3,4,2,1,3,3,4,3,3,3,3,3,4,5]
>>> from itertools import groupby
>>>
>>> [(k, sum(1 for _ in g)) for k,g in groupby(src)]
[(1, 2), (2, 1), (3, 2), (4, 1), (2, 1), (1, 1), (3, 2), (4, 1), (3, 5), (4, 1), (5, 1)]

Take a look at how itertools.groupby() to see how a generator will be a good choice for this kind of task

But that doesn't mean that it wasn't a bad idea try to implement it yourself. So let's take a deeper look at your code :)

The best use of global is usually the one that doesn't use global at all

The use of the global keyword among beginners is almost always a sign of trying to program using some other language's mindset. Usually, if a function need to know the value of somthing, pass that something along as an argument.

In your case, what you need, is a function that loops through your list holding the value of isRepeat.

Something like this:

def parse(seq):
    is_repeat = False
    old = None
    for num in seq:
        is_repeat = num == old    # will be True or False
        if is_repeat:
            # ...

I didn't go too far since, as you may have already noticed, the is_repeat flag is a bit useless now, so we'll get rid of that later.

You may have also noted that I called isReapeat is_repeat, I did that to follow some naming style guide (see PEP8 for more info).

Cleared this, let's get at your statement:

  In the first step, I need to split my source list to sequences of repeating and non-repeating elements.

Ok, to split a sequence we'll have to parse it item by item, so while we'll be at it why don't already count how many times an item occurs?

The wrong step was to build a testRepeat function, such function should act on 2 items at the time, but that will lose the "view" of the whole sequence one item after the other. Well ok, a recursive solution could also be found, but I can't go through all the possible solutions.

So, to do achive our goal one could:

parse the list item by item.
see if an item is the same as the previous one.
if it is count += 1.
else store that item with its count.

This might be the code:

def rle(seq):
    result = []
    old = seq[0]
    count = 1
    for num in seq[1:]:
        if num == old:
            count += 1
        else:
            result.append((old, count))   # appending a tuple
            count = 1      # resetting the counting
            old = num
    result.append((old, count))    # appending the last counting
    return result

There could still be room for improvement (also it doesn't handle empty list like hdima noticed), but I just wanted to show an easy example and premature optimization is the root of (most) evil. (Also, there's groupby waiting to be used.)

Notes

It's very common to fall in some of the mistakes you did. Keep trying and you'll get better. Keep also in mind some of the following:

Think hard about the your design.
Do you really need an out function? Couldn't you just place the code there?
Do you really want to not print at all, if you get an empty list? I would really like to see what my code is returning, so I wouldn't block its output.
Don't write cryptic code, write readable one.
What are a, b and pr. A variable name should be something that reflect what it holds.
The same could be said for sequence, if sequece is the resulting sequence call it result or something like that.
Whorship The Zen of Python as an almighty guide!


Implementation of Euclidean algorithm I have made an implementation of the Euclidean algorithm in Java, following the pseudocode shown below.

As far as my knowledge goes, I can't find a way of making this more efficient.

I have looked into other peoples implementations of this algorithm and there are a few which are slightly shorter, and some that use recursion.

The pseudocode:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

My implementation:

import java.util.Scanner;
public class EuclideanAlgorithm {
    public static void main (String [] args) {
        int a, b;
        try(Scanner sc = new Scanner(System.in);) {
            System.out.print("Enter integer a: ");
            a = sc.nextInt();
            System.out.print("Enter integer b: ");
            b = sc.nextInt();
        }
        long start = System.nanoTime();
        int answer = EuclideanAlgorithm(a, b);
        long stop = System.nanoTime();
        System.out.println("gcd = " + answer);
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms.");

    }

    public EuclideanAlgorithm() {}; //Suppress default constructor

    private static int EuclideanAlgorithm(int a, int b) {
        int t;
        while (b != 0) {
            t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

Is there a way to make this implementation more efficient, and would it have been more efficient to use recursion?

I believe this is as efficient as it gets, save for quickly detecting edge cases (a == 0 or a == b), which I think would be negligible anyway.

Recursion wouldn't be more efficient than iterative version. Functional languages can optimize recursion to the point where there's no difference, but I don't think Java excels at that and there's a performance penalty of adding new frames to the stack.

Recursion can make code clearer and more readable sometimes, but that's another story.

As a side note:

public EuclideanAlgorithm() {}; //Suppress default constructor

What's the purpose of this "suppression"?


Safely using console.* in browser I come from a Java background so my desire for proper unambiguous logging is strong. I prefer using the console to using some other gui widget however, in the browser I know that I can't always count on the console to exist or for it to have all the levels I might like. To remedy this I worked up the following console sanitizer and I was curious what drawbacks it might have.

function configureConsoleLog() {
    "use strict";
    var logMethods = [ 'trace', 'debug', 'log', 'info', 'warn', 'error' ], i;

    if (!window.console) {
        window.console = {log: function (args) {}}; //noop
    }

    for (i = 0; i < logMethods.length; i += 1) {
        if (!window.console[logMethods[i]]) {
            window.console[logMethods[i]] = window.console.log;
        }
    }
}

The idea is to find out if console exists and if it does try to find out which of the supported levels I need are available. The first level of fallback is to map unsupported methods to console.log. The second level is to create my own console variable and make a noop log function since I have nowhere to send the output. This approach leaves open the possibility of coming up with a different strategy if console doesn't exist but for now I'm content to ignore logging if there is no console.

As a side note I looked at several JS logging packages but all of them have the fatal drawback of obscuring original line numbers, usually by delegating to a console method which only reports the line number of the delegating statement.

Thoughts?

I don't see any problems with that. It's similar to this answer on SO.

Just a couple minor things:

You don't need args in the empty log function
You should make the entire function anonymous and execute it immediately (as it's being done in the answer I linked to); I don't think there's any usecase for calling it otherwise
Don't forget var in front of the i variable, otherwise it becomes global


Extension of PHP `round()` for PHP_ROUND_UP and PHP_ROUND_DOWN While looking at PHP.net this afternoon, I saw a comment in round() for two functions for rounding UP and DOWN (as opposed to just HALF_UP and DOWN).  I liked the suggestion, but wanted a solution that was one function instead of 3, so I came up with the following:

define('PHP_ROUND_UP',   11);
define('PHP_ROUND_DOWN', 12);

function fround($number, $precision = 0, $mode = PHP_ROUND_HALF_UP) {
    if(is_string($number)) {
        $number = preg_replace('/,/','',$number);
    }
    if (is_numeric($number) && !empty($number)) {
        switch($mode) {
            case PHP_ROUND_UP:
            case PHP_ROUND_DOWN:
                $invert = (bool) ($number < 0);
                if($invert) {
                    $number *= -1;
                }
                if (!empty($precision)) {
                    $precision = pow(10, (int) $precision);
                    $number *= $precision;
                }
                if ($mode == PHP_ROUND_UP) {
                    $number = ceil($number);
                } else {
                    $number = floor($number);
                }
                if (!empty($precision) && !empty($number)) {
                    $number /= $precision;
                }
                if($invert) {
                    $number *= -1;
                }
                break;
            default:
                $number = round($number, $precision, $mode);
                break;
        }
    }
    return (float) $number;
}

My questions are about overhead/performance, and really anything else you may have to say.  For options other than PHP_ROUND_UP or PHP_ROUND_DOWN it adds minimal overhead, save for stripping commas if the input number is a string (I realize this is additional to what PHP's round() does), so I guess I am asking about the internal logic for PHP_ROUND_UP and PHP_ROUND_DOWN.

The comment that sparked this for me is here.

REVISION

General

Instead of having your function convert string values to numbers, throw an error if, for example !is_float($number). round() only accepts a float value, so I think you should follow their convention.

Also, this will allow you to remove is_numeric() (or, above, you could check for is_numeric() only).

This if-condition doesn't have an else, so when poor input is entered, the user could potentially not get any response at all -- terrible for debugging!

Performance

empty($number) is checked two times, you can reduce that to none since is_float() will automatically return false if there is nothing (or throw an error is there's no argument).


Check if two types are the same without template instantiations Below is my attempt to check if two types are the same without template instantiations.
#include <cstddef>
template<class, class> struct twoTypes;
template<class T> std::size_t isSame(twoTypes<T,T>*);
bool isSame(void*);

template<class T, class U>
using checkIfSame = decltype(isSame(static_cast<twoTypes<T,U>*>(0)));

And to check if they're the same, checkIfSame's size will be compared to std::size_t's size:
static_assert(sizeof(checkIfSame<int,int>) == sizeof(std::size_t)); //They're the same
static_assert(sizeof(checkIfSame<const int,int>) == sizeof(bool)); //Not the same

Are there any cases where my code will give the wrong result? My benchmarks show my version compiling faster than std::is_same, but are there any ways to make it faster?

If you're using clang or GCC ≥10, you can use the __is_same(type1, type2) intrinsic.
For portability:
#if !defined(__is_same) && (!defined(__clang__) || !defined(__GNUC__) || __GNUC__ < 10)
#define IS_SAME(T1, T2) std::is_same_v<T1, T2>
#else
#define IS_SAME(T1, T2) __is_same(T1, T2)
#endif


Matasano Cryptopals Challenge 1: convert hex to base64 Cryptopals challenge 1

Using binary strings to convert from hex to binary felt kinda hacky. I'd like to hear if there are better ways to do that.

I used memcpy() and pointer to the end of the string instead of strcat() to avoid the Shlemiel the Painter problem.

EDIT: follow up question

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

char* hex_2_base64(char *_hex)
{
  char *hex_2_bin[16] = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" };
  char *dec_2_base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

  //allocating memory for binary string
  int bin_size = strlen(_hex) * 4;
  while (bin_size % 6 != 0) //add space for zero padding
    bin_size += 8;
  char *bin = malloc(bin_size + 1);
  memset(bin, 0, bin_size + 1);

  //these are for strtol, its arguments need the zero terminator
  char buf[2] = { 0 };
  char b64buf[6 + 1] = { 0 };

  //converting hex input to binary
  char *bin_end = bin;
  for (int i = 0; i < strlen(_hex); i++)
  {
    buf[0] = _hex[i];
    memcpy(bin_end, hex_2_bin[strtol(buf, NULL, 16)], 4);
    bin_end += 4;
  }

  //pad binary string w/ zeroes
  while (strlen(bin) < bin_size)
    strcat(bin, "00000000");

  //allocating memory for b64 output
  int b64size = (strlen(bin) / 6) + 1;
  char *out = malloc(b64size);
  memset(out, 0, b64size);

  //walk through binary string, converting chunks of 6 bytes into base64 chars
  char *bin_ptr = bin;
  char *out_end = out;
  int index_b64;
  while (*bin_ptr)
  {
    strncpy(b64buf, bin_ptr, 6);
    index_b64 = strtol(b64buf, NULL, 2);
    if (index_b64 == 0)
      buf[0] = '=';
    else
      buf[0] = dec_2_base64[index_b64];
    memcpy(out_end, buf, 1);
    out_end += 1;
    bin_ptr += 6;
  }

  free(bin);
  return out;
}

int main(void) {
  char *out = NULL;

  out = hex_2_base64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d");
  assert(strcmp(out, "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t") == 0);
  free(out);

  //Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.
  out = hex_2_base64("4d616e2069732064697374696e677569736865642c206e6f74206f6e6c792062792068697320726561736f6e2c2062757420627920746869732073696e67756c61722070617373696f6e2066726f6d206f7468657220616e696d616c732c2077686963682069732061206c757374206f6620746865206d696e642c20746861742062792061207065727365766572616e6365206f662064656c6967687420696e2074686520636f6e74696e75656420616e6420696e6465666174696761626c652067656e65726174696f6e206f66206b6e6f776c656467652c2065786365656473207468652073686f727420766568656d656e6365206f6620616e79206361726e616c20706c6561737572652e");
  assert(strcmp(out, "TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlzIHNpbmd1bGFyIHBhc3Npb24gZnJvbSBvdGhlciBhbmltYWxzLCB3aGljaCBpcyBhIGx1c3Qgb2YgdGhlIG1pbmQsIHRoYXQgYnkgYSBwZXJzZXZlcmFuY2Ugb2YgZGVsaWdodCBpbiB0aGUgY29udGludWVkIGFuZCBpbmRlZmF0aWdhYmxlIGdlbmVyYXRpb24gb2Yga25vd2xlZGdlLCBleGNlZWRzIHRoZSBzaG9ydCB2ZWhlbWVuY2Ugb2YgYW55IGNhcm5hbCBwbGVhc3VyZS4=") == 0);
  free(out);

  //f
  out = hex_2_base64("66");
  assert(strcmp(out, "Zg==") == 0);
  free(out);

  //fo
  out = hex_2_base64("666f");
  assert(strcmp(out, "Zm8=") == 0);
  free(out);

  //foo
  out = hex_2_base64("666f6f");
  assert(strcmp(out, "Zm9v") == 0);
  free(out);

  //foob
  out = hex_2_base64("666f6f62");
  assert(strcmp(out, "Zm9vYg==") == 0);
  free(out);

  //fooba
  out = hex_2_base64("666f6f6261");
  assert(strcmp(out, "Zm9vYmE=") == 0);
  free(out);

  //foobar
  out = hex_2_base64("666f6f626172");
  assert(strcmp(out, "Zm9vYmFy") == 0);
  free(out);

  printf("OK!");

  return 0;
}

Base 16 -> Base 2 -> Base 64: Cut out the middleman
You are currently converting each hex digit to 4 binary digits, then converting 6 binary digits into one Base64 digit.  Instead of doing two conversions, how about if you took each three hex digits (= 12 binary digits) and converted that into two Base64 digits?  You can do this up until the end of your hex string, where you might have 1 or 2 leftover hex digits.  You can handle those leftover digits by padding with extra zero bits and outputting extra Base64 digits, including the special '=' digit.
Bug
Your code doesn't convert zeros correctly.  The problem is here:

if (index_b64 == 0)
  buf[0] = '=';
else
  buf[0] = dec_2_base64[index_b64];

As you can see, you output '=' for each Base64 zero digit.  However, the correct digit to output is 'A'.  The special '=' digit is only used to indicate zero bits for padding.  Therefore, if I try to convert the hex string "0000", your program returns "====" when the correct answer is "AAA=".


Re-writing rough JS code with loads of jQuery plugins I want to include about 10 jQuery plugins in a project but do so in a better way than just pasting them into a JS file.

I want to capture various device data and other data passed from the server-side (in a HTML meta tag) and I want some of this to decide which jQuery scripts to run - or none in the case of some devices.

I also want to be able to extend jQuery plugins, globally control events, globally control setTimeout() and basically write the code in a much better way to maintain.

I have been learning from various tutorials and would like to gauge my understanding.

I have written the code below form various tutorials and advice and it should be a better way to extend and implement jQuery and feedback would be great. I haven't actually ran the code, I'm just trying to understand how the best way to design this would be.

Am I on the right track for how to structure this?

/* all the original jQuery plugins */
(function ($) {
    $.slider = function () {
        //etc
    };
}(jQuery));

/* jQuery wrappers - one for each jQuery script */
function JquerySlider($) {
    var extensionMethods = {
        showId: (function () {
            return this.element[0].id;
        }())
    };

    $.extend(true, $.slider.prototype, extensionMethods);
}

/* execute all the jQuery scripts */
function InitJquery($) {
    this.slider = new JquerySlider($);
}

/* get various device data */
function Device() {
    // get meta data from HTML
    // holds a value 1-3 for the quality of the device (detected server-side)
    this.quality = Number(document.getElementById('device-quality').content);

    // get viewport width
    this.viewportWidth = window.innerWidth || document.documentElement.clientWidth || document.body.clientWidth;
}

/* standard JS */
function InitStandard(jQuery) {
    //get device information
    this.device = new Device();

    // initialise jQuery, if device is capable
    if (this.device.quality === 1) {
        this.jqueryPlugins = new InitJquery(jQuery);
    }
}

/* cross-browser add event function */
if (window.addEventListener) {
    var addEvent = function (ob, type, fn) {
        if (typeof ob != 'undefined') {
            ob.addEventListener(type, fn, false);
        }
    };
} else if (document.attachEvent) {
    var addEvent = function (ob, type, fn) {
        if (typeof ob != 'undefined') {
            var eProp = type + fn;
            ob['e' + eProp] = fn;
            ob[eProp] = function () {
                ob['e' + eProp](window.event);
            };
            ob.attachEvent('on' + type, ob[eProp]);
        }
    };
}

/* initialise standard JS on load and pass in the jQuery object */
(function init(jQuery) {
    var js = new InitStandard(jQuery);
}(jQuery));

addEvent(window, 'load', init);

On the whole, I think you need to work on keeping it simple.

I would not write my own cross-browser event handling function if I use jQuery, I would leverage what jQuery provides.
This:

/* standard JS */
function InitStandard(jQuery) {
    //get device information
    this.device = new Device();

    // initialise jQuery, if device is capable
    if (this.device.quality === 1) {
        this.jqueryPlugins = new InitJquery(jQuery);
    }
}

/* initialise standard JS on load and pass in the jQuery object */
(function init(jQuery) {
    var js = new InitStandard(jQuery);
}(jQuery));

could be

(function InitStandard(jQuery) {
    //get device information
    this.device = new Device();

    // initialise jQuery, if device is capable
    if (this.device.quality === 1) {
        this.jqueryPlugins = new InitJquery(jQuery);
    }
}(jQuery));

Because you are not using var js anywhere.
Also, 1 should be assigned to a properly named constant like ADVANCED_DEVICE
addEvent(window, 'load', init); could be $( init )


Find median of two sorted ranges Given two sorted ranges of elements, compute a median of all the elements in O(log(n+m)) time.

This solution contains only one call to std::lower_bound

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

template <typename It1, typename It2>
auto max_end(It1 begin1, It1 end1, It2 begin2, It2 end2) {
    if (begin1 != end1 && begin2 != end2) {
        return std::max(*std::prev(end1), *std::prev(end2));
    }
    if (begin1 != end1) {
        return *std::prev(end1);
    }
    if (begin2 != end2) {
        return *std::prev(end2);
    }
    // both ranges should never be empty
    __builtin_unreachable();
}

template <typename It1, typename It2>
auto min_begin(It1 begin1, It1 end1, It2 begin2, It2 end2) {
    if (begin1 != end1 && begin2 != end2) {
        return std::min(*begin1, *begin2);
    }
    if (begin1 != end1) {
        return *begin1;
    }
    if (begin2 != end2) {
        return *begin2;
    }
    // both ranges should never be empty
    __builtin_unreachable();
}

template<typename RandomAccessIterator1, typename RandomAccessIterator2>
auto median2(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
              RandomAccessIterator2 begin2, RandomAccessIterator2 end2) {
    static_assert(std::is_same<typename std::iterator_traits<RandomAccessIterator1>::value_type,
                  typename std::iterator_traits<RandomAccessIterator2>::value_type>::value,
                  "Value types of two ranges must be the same");
    ssize_t n1 = std::distance(begin1, end1);
    ssize_t n2 = std::distance(begin2, end2);
    ssize_t mid = (n1 + n2) / 2;
    auto it = std::lower_bound(begin1, end1, 42, [&](const auto & item, int){
        ssize_t i1 = &item - &*begin1;
        ssize_t i2 = mid - i1;
        // make sure i2 is a valid index
        if (i2 < 0) {return false;}
        if (i2 > n2) {return true;}

        return max_end(begin1, begin1+i1, begin2, begin2+i2)
                >= min_begin(begin1+i1, end1, begin2+i2, end2);
    });

    ssize_t i1 = &*it - &*begin1;
    ssize_t i2 = mid - i1;

    if ((n1 + n2) % 2) {
        return min_begin(begin1+i1, end1, begin2+i2, end2);
    }

    return (max_end(begin1, begin1+i1, begin2, begin2+i2) +
            min_begin(begin1+i1, end1, begin2+i2, end2)) / 2;
}

template<typename Rng1, typename Rng2>
auto median2(Rng1 &&rng1, Rng2 &&rng2) {
    using std::begin;
    using std::end;
    return median2(begin(rng1), end(rng1), begin(rng2), end(rng2));
}

int main() {
    std::cout << median2(std::vector<float>{1, 2, 3, 4}, std::vector<float>{}) << '\n';
    std::cout << median2(std::vector<float>{}, std::vector<float>{1, 2, 3, 4}) << '\n';
    std::cout << median2(std::vector<float>{1, 2, 3, 4, 5}, std::vector<float>{}) << '\n';
    std::cout << median2(std::vector<float>{}, std::vector<float>{1, 2, 3, 4, 5}) << '\n';
    std::cout << median2(std::vector<float>{1, 2}, std::vector<float>{3}) << '\n';
    std::cout << median2(std::vector<float>{1, 3}, std::vector<float>{2}) << '\n';
    std::cout << median2(std::vector<float>{1, 2, 3, 4, 5}, std::vector<float>{6, 7, 8, 9, 10}) << '\n';
    std::cout << median2(std::vector<float>{1, 2, 3, 4, 5}, std::vector<float>{6, 7, 8, 9}) << '\n';
    std::cout << median2(std::vector<float>{1, 2, 3}, std::vector<float>{6, 7, 8, 9}) << '\n';
}

Live on Coliru

Solution to the same problem in Python on codereview

While this is not a thorough code review, here are some things you could improve or should pay attention to:

median2 is dangerous for containers which offer RandomAccessIterators, but aren't contiguous. In particular, ssize_t i1 = &item - &*begin1; invokes undefined behavior if item and begin1 do not belong to the same memory area, which they might if the underlying container is not contiguous (also, sometimes operator& is overwritten, which can cause a lot of problems on its own). To prepare against this, I would advise you to rename RandomAccessIterator[12] to ContiguousRandomAccessIterator[12] or something in that line of wording.
You are probably aware of this already, but your code is not really portable. For one, there is __builtin_unreachable, which is a gcc builtin. Also, ssize_t is a type from unistd.h, which is a posix header and might not be available on non-posix-conformant operating systems (also, you do currently not include this header, which is a bug). ssize_t is easily replaceable by std::ptrdiff_t in most cases, but if you care for that much of correctness, you could also write something like using difference_t = typename std::iterator_traits<RandomAccessIterator1>::difference_type; and use that instead. For __builtin_unreachable(), if the optimization value you get by using it is really that important for you, you should wrap it in some compiler identifying macro. If it is not important (which is probably the case), you could do a variety of things, for example replace it with a throw expression or just return a default value.
Rng[12] is a very confusing template parameter name, at least to me. I would expect it to stand for "random number generator", which is not fitting here. Choosing a different name would likely be beneficial here.
You should consider passing std::pairs instead of separate iterators. This makes clear that one begin- and one end-iterator always belong together, and helps cleaning up the parameters of your functions.
std::vector<float>{1, 2, 3, 4}. Please don't. This code is just ugly. The reason is that 1) you are relying on implicit conversion for all your values (why not write std::vector<float>{1.0f, 2.0f, 3.0f, 4.0f} instead?) and 2) there is no reason here to use float at all. Stick to integer types unless you do something that actually requires floating point features.


JSON AsyncTask refactoring to improve quality? I'm new to Android. I was wondering if anyone had any suggestions. It's basically an AsyncTask to get a remote JSON array and put it into a native array.

Would be very grateful for suggestions.

package com.example.test2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.HttpURLConnection;
import java.net.URL;
import java.util.Arrays;
import java.util.Hashtable;

import org.json.JSONArray;
import org.json.JSONException;
import org.json.JSONObject;

import android.app.Activity;
import android.os.AsyncTask;
import android.os.Bundle;
import android.widget.TextView;

public class MainActivity extends Activity {

private String                  strCategoryJsonUrl      = "http://www.mydomain.com/categories.json";
getCategories                   myCategories;

@Override
protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_main);

    myCategories            = new getCategories();
    myCategories.execute();
}//onCreate

private class getCategories extends AsyncTask<Integer, Integer, String>{

    @Override
    protected String doInBackground(Integer... intMyGuessLevel) {
        String strJson  = "";

        try {
            URL url = new URL(strCategoryJsonUrl);
            HttpURLConnection con = (HttpURLConnection) url.openConnection();
            strJson = readStream(con.getInputStream());
        } catch (Exception e) {
            e.printStackTrace();
        }

        return strJson;
    } //doInBackground

    private String readStream(InputStream in) {
        BufferedReader  reader      = null;
        String          strContent  = "";

        try {
            reader = new BufferedReader(new InputStreamReader(in));
            String line = "";
            while ((line = reader.readLine()) != null) {
                strContent  = strContent + line;
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        } //finally

        return strContent;
    } //readStream

    protected void onPostExecute(String strResult) {
        int i                   = 0;
        String strValue         = "";
        TextView txtDebug       = (TextView) findViewById(R.id.txtdebug);
        String arrCategories[]  = new String[1];

        //parse JSON data
        try{
            JSONArray   jArray  = new JSONArray(strResult);
            //JSONObject  menu = jObject.getJSONObject("menu");
            arrCategories       =   new String[jArray.length()];

            for(i=0; i < jArray.length(); i++) {
                JSONObject jObject  = new JSONObject(jArray.get(i).toString());

                strValue            = jObject.getString("name");

                //put value into array
                arrCategories[i]    = strValue;
            }

            //debug output the array
            txtDebug.setText(Arrays.toString(arrCategories));

        } catch (JSONException e) {
            e.printStackTrace();
            txtDebug.append("Error in categories json file \n");
            txtDebug.append(String.valueOf(e));
        } // catch

    } //onPostExecute
} //getJsonContent

}

Don't open a resource in one place and close it in another. Keep the opening and closing of a resource localized to the same function (if you open it, you close it). This makes it easier to spot potential resource leaks.

For example, an InputStream is being opened in doInBackground(), but it is being closed in readStream(). Since doInBackground() opened the resource, it should be responsible for closing it.

HttpURLConnection con = (HttpURLConnection)url.openConnection();

You are not using anything specific to HttpURLConnection, so there is no reason to cast it. This works just fine:

URLConnection con = url.openConnection();

try {
    ...
} catch (Exception e) {
    e.printStackTrace();
}

Don't ignore exceptions. Either let them continue up to the caller, or handle them appropriately. The readStream() function is a good example of where the exception should continue to the caller. Declare it as throwing IOException and remove the exception handling:

private String readStream(InputStream in) throws IOException {
    String content = "";
    BufferedReader reader = new BufferedReader(new InputStreamReader(in));
    String line = null;
    while ((line = reader.readLine()) != null) {
        content += line;
    }
    return content;
}

JSONObject jObject = new JSONObject(jArray.get(i).toString());

This can be simplified to this:

JSONObject jObject = jArray.getJSONObject(i);

Declare variables closer to there they are used. For example, in onPostExecute(): i, strValue and arrCategories are all declared at the top of the function, but are only ever used inside the try block.

protected void onPostExecute(String strResult) {
    TextView txtDebug = (TextView)findViewById(R.id.txtdebug);
    try {
        JSONArray jArray = new JSONArray(strResult);
        String[] arrCategories = new String[jArray.length()];
        for (int i = 0; i < jArray.length(); i++) {
            JSONObject jObject = jArray.getJSONObject(i);
            arrCategories[i] = jObject.getString("name");
        }
        txtDebug.setText(Arrays.toString(arrCategories));
    } catch (JSONException e) {
        e.printStackTrace();
        txtDebug.append("Error in categories json file \n");
        txtDebug.append(String.valueOf(e));
    }
}

I would also like to see onPostExecute() broken down further. It is currently doing two things: parsing the JSON array and updating the UI. Move those into their own functions.

I am not a big fan of the comments in this code. I do not believe they add any value, and are only a distraction while reading.


Loading and parsing WinForms menus using LINQ I'm refactoring a WinForms utility program for building and testing regular expressions. The program has a menu item which lists the RegexOptions enumeration, allows the user to checkmark the items they want, and then those settings are applied during regex testing.

I'm rather new to LINQ, and I'd like to learn the best way to do this.  At present the differences between .Cast<> and .OfType<>, .Where() and .Any() and .All() are rather ambiguous to me.

This is the code I'm using to load the menu-

menuRegexOptions.MenuItems.AddRange(
    Enum
    .GetValues(typeof(RegexOptions))
    .Cast<RegexOptions>()
    .Where(
        s => s != RegexOptions.None
    )
    .Select(
        p => new MenuItem(null, option_Click)
        {
            Text = p.ToString(),
            Tag = p
        })
    .ToArray()
    );

It works and is readable, but I'm keen to know if I've missed any fundamentals or can make it more efficient.

To determine the current Regex setting, the checkmarked menu items must be combined using a bitwise OR operation.  The best solution I could come up with is-

public RegexOptions SelectedRegexOptions
{
    get
    {
        RegexOptions options = RegexOptions.None;

        mnuRegexOptions.MenuItems
            .Cast<MenuItem>()
            .Where(
                x => x.Checked
            )
            .ToList()
            .ForEach(
                s => {
                    options |= (RegexOptions)s.Tag;
                }
            );

        return options;
    }
}

It works, but it feels like I should be able to do the != operation internally to the LINQ and then simply return the result, without the need for the external options variable.

Is there a better way?

Try this:

public RegexOptions SelectedRegexOptions
{
    get
    {
       RegexOptions options = mnuRegexOptions.MenuItems
            .Cast<MenuItem>()
            .Where(
                x => x.Checked
            )
            .Select(s => (RegexOptions)s.Tag)
            .Aggregate(RegexOptions.None, (x, y) => x | y);

        return options;
    }
}

The Aggregate call will take care of the bitwise ORs.


Calculating a postfix expression I've got the following code in my calculator project:

private ITerm CalculatePostfixExpression(IEnumerable<ITerm> input)
{
    var tempResult = new Stack<ITerm>();
    foreach (var term in input)
    {
        if (term is IOperand)
        {
            tempResult.Push(term as IOperand);
        }
        if (term is IOperator)
        {
            tempResult.Push(ProceedOperation(term as IOperator, tempResult));
        }
    }
    return tempResult.Peek();
}

Now it's violating the open-closed principle, so I'm asking for a help to improve my code.

It's kinda like a "Replace Conditional with Polymorphism" but I can't understand how to use it in my case.

First, note that with code like this that has to read in external input, and convert it into objects, you typically end up with some sort of factory class that's kind of the border where you often have difficulty applying the open-closed principle very well. That is, it often needs at least a little tweaking when the rest of the system changes--about the best you normally hope for is to restrict your changes to this one area.

So, what I'd probably do in this case is have a single "stack manipulator" interface, and have both an operand and operators that implement that interface.

// Note: this isn't intended to be compilable code, just pseudo code with
// syntax similar to Java/C#/C++/etc.
//
interface stack_manipulator {
    void execute(stack);
};

class operand : implements stack_manipulator {
    void execute(stack s) {
        s.push(this);
    }
};

class add : implements stack_manipulator {
     void execute(Stack s) {
         // skipping error checking and such for clarity
         var a = s.pop();
         var b = s.pop();
         s.push(a + b);
     }
};

class sub : implements stack_manipulator {
    void execute(Stack s) {
        var a = s.pop();
        var b = s.pop();
        s.push(a - b);
    }
};

// ... and so on for other operators

Then your ITerm CalculatePostfixExpression would look something like this:

    var tempResult = new Stack<ITerm>();
    foreach (var term in input) {
        term.execute(tempResult);
    }
    return tempResult.Peek();

...and modifications to the other code won't require changes to this (as long as the other code adheres to the stack_manipulator interface. As hinted at above, however, somewhere you'll need a factory class that knows how to map from input characters to the individual types that implement the stack_manipulator interface.


Class for finding the median of a two-dimensional space I have a simple static class that it's purpose is given an RDD of Point to find the median of each dimension and return that as a new Point using Spark's reduce functions.

This is the class:

public class MedianPointFinder {

    public static Point findMedianPoint(JavaRDD<Point> points) {
        Point biggestPointByXDimension = points.reduce((a, b) -> getBiggestPointByXDimension(a, b));
        Point biggestPointByYDimension = points.reduce((a, b) -> getBiggestPointByYDimension(a, b));

        double xDimensionMedian = biggestPointByXDimension.getX() / 2.0;
        double yDimensionMedian = biggestPointByYDimension.getY() / 2.0;

        return new Point(xDimensionMedian, yDimensionMedian);
    }

    private static Point getBiggestPointByXDimension(Point first, Point second) {
        return first.getX() > second.getX() ? first : second;
    }

    private static Point getBiggestPointByYDimension(Point first, Point second) {
        return first.getY() > second.getY() ? first : second;
    }
}

Point class is a simple class for storing an (x, y) point.

I guess your Point is not a java.awt.Point since that holds x and y as int and you're using double.

Why not getting rid of your Point class by making the "Finder" class itself a MedianPoint?

import java.awt.geom.Point2D;

public class MedianPoint extends Point2D.Double {

  public MedianPoint(JavaRDD<Point> points) {
    super(
      /* your x calculation */,
      /* your y calculation */
      );
  }

  private static Point2D.Double greaterByXOf(Point2D.Double p1, Point2D.Double p2) {
    // ...
  }

  private static Point2D.Double greaterByYOf(Point2D.Double p1, Point2D.Double p2) {
    // ...
  }

} // MedianPoint


Basic python dice simulator with log function I had created a dice simulator using nothing but functions, but I wanted to attempt one using a class for the dice just to help get a better understanding of classes.  I'm still a little in the dark on OOP and I feel like it was poorly implemented here, but I achieved what I was going for and I feel like that's at least something.  Any tips on improvement would be appreciated.

#!/usr/bin/env python
import time
from sys import exit
from random import randint

class Die(object):
    """
    Creates a die class for use with a dice rolling utility

    """
    d_sides = None
    def __init__(self, sides = 6):
        self._sides = sides
        self._value = None
        self.roll()

    def roll(self):
        """
        Generate a random integer based off the number of sides
        """
        self._value = randint(1, self._sides)
        return self._value

    def __str__(self):
        """
        Return string containing dice sides and result
        """
        return "Die with {} sides.  Result : {}".format(self._sides, self._value)

def banner():
    """
    Print out in console upon running script
    """
    print "-" * 10
    print "Snake Eyes"
    print "-" * 10

def dice_cup():
    """
    Takes user input for number of sides and number of dice then creates
    dice objects respectively
    """
    global d_sides

    # Asks for a number of dice and verifies that it's a number
    while True:
        try:
            number = int(raw_input("How many dice?\n>"))
            break
        except(TypeError, ValueError):
            print "Please enter a number\n"

    # Asks for a number of sides and verifies that it's a number
    while True:
        try:
            sides = int(raw_input("How many sides?\n>"))
            d_sides = sides
            break
        except (TypeError, ValueError):
            print "Please enter a number\n"
    # Generates dice objects

    dice_roll = [Die(sides).roll() for _ in range(int(number))]
    return dice_roll

def print_dice(d):
    """
    Converts list of dice results into string and prints results and total
    """

    # Converts list of dice results into a string
    dice_str = ','.join(map(str, d))
    # Adds total from dice roll
    total = sum(d)
    print "You rolled: {}\nTotal: {}".format(dice_str, total)

def dice_log(sides, number, roll):
    dash = '-' * 4
    f = open("dice_log.txt","a")
    f.write('\n')
    f.write(time.strftime('%I:%M:%S'))
    f.write('\n')
    f.write(dash)
    f.write('\n{}d{}\n'.format(number, sides))
    f.write(dash)
    f.write('\n{}\n'.format(','.join(map(str, roll))))
    f.write(dash)
    f.write('\nTotal\n')
    f.write(dash)
    f.write('\n{}\n'.format(sum(roll)))
    f.close

def engine():
    global d_sides
    banner()
    raw_input("Press enter to begin.")
    while True:
        roll = dice_cup()
        print_dice(roll)
        dice_log(d_sides, len(roll) , roll)
        cont = raw_input("Return to roll again or quit to exit\n>")
        if cont.lower() == "quit":
            print "\nGoodbye."
            exit(0)

def main():
    engine()

if __name__ == "__main__":
    main()

There's some things I really like about your code. For one, you used str.format, which is in many ways superior to '%'-formatting. You also included docstrings, which help others better understand your code.

The other answers already covered most major problems. I'll be answering mostly in terms of design choice.

Object oriented programming (and why it doesn't apply here)

Classes should be thought of as containers that capture 'state'. Methods can act on that state and properties can be used to query it. A die, however, doesn't have any sense of state. A good rule of thumb is that if a class has only two methods, one of which is the constructor, then it shouldn't be a class.

I'd go further and say that you shouldn't consider creating a class if you are not confident that there is a sense of state in your program that could be grouped together. If you want to know more, there's this well known talk on when not to use classes.

Python 3!

Python 3 rocks, and you should definitely start using it right now. Python 2 only has so much time left, and switching to Python 3 isn't that hard. The only changes that affect this code:

Python 3 got rid of raw_input and replaced it with input.
print is now a function, not a statement.

If you absolutely, positively feel like you need to maintain backwards compatibility with Python 2:

try:
    input = raw_input
except NameError:
    # Python 3; `raw_input` is not defined
    pass


Reading tokenized numbers from a file int *getUserInput(FILE *fpin, int *elementCount) {
  int *userInput;
  // Load file into buffer
  int length = fileLength(fpin);
  char *buffer = (char *) malloc(length * sizeof(char));
  int written = fread(buffer, sizeof(char), length, fpin);
  // Number of int's allocated in userInput
  int allocated = 10;
  *elementCount = 0;
  // Allocate space for the numbers
  userInput = (int *) malloc(allocated * sizeof(int));
  // "tokenize" the buffer with " " and "\n" as delimiters
  char *tokenized = strtok(buffer, " \n");
  while (tokenized != NULL) {
   if (allocated == *elementCount) {
      allocated *= 2;
      // Reallocate space based on need
      realloc(userInput, allocated * sizeof(int));
    }
    // Store the number in the array
    userInput[(*elementCount)++] = atoi(tokenized);
    tokenized = strtok(NULL, " \n");
  }
  realloc(userInput, *elementCount * sizeof(int));
  free(buffer);
  return userInput;
}

It's a function I wrote for reading in numbers from a file, delimited by a space. Curious to hear any thoughts/possible improvements.

Check that malloc didn't return NULL; in general, use defensive programming; That means always assume things went wrong, and check all return values. It helps with debugging too.

You should be aware that strtok and atoi are not safe functions for arbitrary user input. That means you are vulnerable to stack/buffer overflows. Read the man pages of the two functions carefully. Consider using \0-safe functions instead, or at least put a \0 at the end of the input strings.


Refactoring string incrementing and duplicating function I wrote this script and got what I wanted from it. However I'm looking for input on ways I can improve the function.

My goal was to scrape a bunch of image links from a website I'd like to rebuild. I wanted to use webscraper but the image links were coded into the CSS instead of the HTML mark up.

Hence I had difficulty getting the web scrapper to find and collect said links.
Luckily while looking at them, I was able to discern their structure and pattern into 4 formats and came up with the following script to duplicate and iterate through each format to get my links.

Beside the 1st group (which is comprised of 40 images), each image (n) is part of a group (x) of 12 and there are 170 groups in total. Something I had to consider while writing the script is that each image number starts with a "00" prefix and "000" for the group number. So they had to be removed as you increment through the tens(for images) and hundreds(for groups).

let loop = 0;
for (; loop < 155; loop++) {
let n = 00;
let x = 000;
str1 = "https://site.com/content/2018/02/"; /* groups 1-155*/
str2 = "https://site.com/content/2019/07/"; /* groups 156-167*/
str3 = "https://site.com/content/2019/11/"; /* group 168*/
str4 = "https://site.com/content/2020/03/"; /* groups 169-171*/
ext = ".jpg"
z = "0";
zz ="00";
        if (loop > 0 ) {
        x+=loop;
    console.log('one loop ' + loop );
    if(x >= 9){
        var zz = "00".replace('00','0');
    }
    if(x >= 99){
        var zz = "00".replace('00','');
    }
  }
      while (n <= 11) {
        if(n >= 9){
        var z = "0".replace('0','');
        }
        n++;
    console.log(str1 + zz + x + "_" + z + n + ext);
  }
}

You should consider using consistent indentation when writing code - it makes it much easier for people to read (not only for other maintainers, but for you as well). For example

let loop = 0;
for (; loop < 155; loop++) {
let n = 00;
// ...
zz ="00";
        if (loop > 0 ) {
        x+=loop;
    console.log('one loop ' + loop );

should be something like

let loop = 0;
for (; loop < 155; loop++) {
  let n = 00;
  // ...
  zz ="00";
  if (loop > 0 ) {
    x+=loop;
    console.log('one loop ' + loop );

Lots of IDEs provide an automatic tidying function.

In this section, since you aren't using str2, str3, or str4, you may as well remove those assignments from the inside of the loop here, since they aren't used and only add to cognitive overhead.

Best to always declare variables before you use them - you have a number of variables which are not declared, which will either assign to properties of the global object (in sloppy mode), or will throw an error (in strict mode). (Consider always using strict mode so that these sorts of potential bugs can be fixed early.) Specifically, lines like:

str1 = "https://site.com/content/2018/02/"; /* groups 1-155*/

where you use a variable for the first time should be prefixed with const, let, or var:

const str1 = "https://site.com/content/2018/02/"; /* groups 1-155*/

If you're going to use ES2015 syntax to declare some variables like let (which is great, you should), don't use var anywhere; var has numerous potential gotchas which can cause bugs, and doesn't really have anything positive going for it (other than compatibility with ancient browsers - but if you need that sort of compatibility, use Babel to transpile to ES5 automatically - best to keep source code in readable, pretty, modern syntax).

When you have a for loop, if you need to declare a variable at the beginning that's then used inside that loop, you should put the declaration inside the for loop declaration. That is:

let loop = 0;
for (; loop < 155; loop++) {

should be

for (let loop = 0; loop < 155; loop++) {

You have

let n = 00;
let x = 000;

Leading zeros have no effect in numeric literals. Those are equal to

let n = 0;
let x = 0;

You declare the zz variable 3 times, but you only have one binding for it - duplicate variable declarations with var are ignored. If you just want assignment, then only use the assignment operator with =.

The x variable starts at 0 and gets loop assigned to it once, on every iteration:

let x = 0;
// ...
if (loop > 0) {
  x += loop;

So, it's equivalent to loop. Best to just remove that variable completely, since it isn't doing anything useful - use the one loop variable completely. The if (loop > 0) { test is superfluous too, since the tests inside that block if(x >= 9){ if(x >= 99){ are only fulfilled if loop is greater than 0 anyway.

Use meaningful variable names. It is very difficult to tell at a glance what loop, n, x, z, or zz are meant to represent. Maybe call them group (the number that goes from 1 to 155) and subgroup (the number that goes from 1 to 11) instead.

The main block there is meant to ensure that the zz variable for padding the string has the right number of zeros. But there's a much easier way to do that, without creating extra variables: just use String.prototype.padStart. When you need to construct

000_01
154_12

from variables 0 and 1, and from variables 154 and 12, add the leading zeros by calling padStart(length, '0') on them:

`${String(group).padStart(3, '0')}_${String(subgroup).padStart(2, '0')}`

Or, without a template literal:

String(group).padStart(3, '0') + '_' + String(subgroup).padStart(2, '0')

The loop over subgroups (or n in your original code) assigns a variable and increments it every iteration, breaking after a condition. This is a prime spot to be refactored into a for loop instead:

for (let subgroup = 1; subgroup <= 12; subgroup++) {

Since the str1 never changes, and nor does the ext, you may as well declare them outside of the loop, rather than re-declare them every time there's another iteration:

In full:

'use strict';

const str1 = "https://site.com/content/2018/02/"; /* groups 1-155*/
const ext = ".jpg"
for (let group = 0; group < 155; group++) {
  console.log('one loop ' + group);
  for (let subgroup = 1; subgroup <= 12; subgroup++) {
    console.log(`${str1}${String(group).padStart(3, '0')}_${String(subgroup).padStart(2, '0')}${ext}`);
  }
}


Support static typing / analysis with dependency injection I am working on creating a test library, and I found DI to be pretty convenient, maybe even to create more functional coding patterns.

Normally we can have an awkward before-hook setup in Node.js testing libraries, and it's always a little unclear when things actually get initialized and refactoring can be harder than it should be:

let client;

before(function(){
    return client = ...     // client requires asynchronous initalization
});

it('tests client', function(){
   assert(client.isConnected);   // client is declared / initialized...right?
});

I've always hated that pattern, sometimes just for ergonomic reasons. It just seems awkward to me. Because client will be in scope in places where it is not yet initialized.

I thought about avoiding this pattern and finally devised a way around it, it basically looks like this:

describe('parent', function(){

    inject(() => {
        return {
            client: new Client({port: 7033}).ensure()  // returns a promise
        }
    });

    describe('child',  (client) => {

       // client has been initialized, and is injected here

        it('tests client', function(){
          // ok we know for sure client is defined
          assert(client.isConnected);
        });

    });

});

as you can see in any child block, we can inject parameters from the parent block.

This is simply a nicety, and makes things easier to grok and less error prone. Maybe even more functional programming style, not sure.

My real concern is supporting static typing, with TypeScript and allowing for at least some static analysis for correctness.

My question is - does anyone know if there is some ES7 or ES8 feature (maybe annotations/decorators?) that can somehow allow for some name checking or type checking in this kind of scenario?

I don't want to create some crazy feature that is so dynamic that it's hard to use.

Basically the way it works currently is that Promise.resolve is called for key/value returned from the inject hook, then this value is injected into the child blocks, by name. So the parameter to the child block callback function will have to match the key of the returned object from the inject hook. This is an API feature in progress and looking for constructive criticism.

To clarify, this would be an alternative API design option:

   inject('client', () => {
        return new Client({port: 7033}).ensure()
    });

then we could use the string 'client' as the matching value to determine where to inject the client variable. Of course, you would only be able to return a single value from this, and not a tuple.

I am also looking for a good way to implement this with callbacks instead of promises. I am not going to reinvent the wheel, so somewhere along the way we should use the async library or similar, here is what I think is the best option:

   inject.cb(j => {
        async.parallel({a: foo(), b: bar()}, j);
    });

    describe('child',  (a, b) => {

       // a and b have been initialized, and are injected here

    });

this way my library could work with any other library that fired a final callback with this signature:

function complete(err, results){}

where results is a simple key-value map; j would be the library callback which accepts the above arguments.

Another issue of course, is handling immutability, because the same object(s) will get injected into multiple places:

    inject('client', () => {
        return new Client({port: 7033}).ensure()
    });

    describe('child1',  (client) => {

       // client is the same object as the below child block

    });

    describe('child2',  (client) => {

       // client is the same object as the above child block

    });

So should make client immutable somehow.

As far as I can tell, the use case you are targeting is already supported by the completion callback, even when you are using promises.  I have had good luck using the following pattern to ensure that asynchronously initialized, promise based libraries are fully initialized before testing begins:

let client;

// Note the function now accepts argument `done`
before(function(done){
    client = new Client({port: 7033}).ensure().then(done)
                                     .catch(function (reason) {
                                         console.error(reason);
                                     });
});

it('tests client', function(){
    assert(client.isConnected);   // we know client is initialized
});

As you correctly pointed out this is similar to returning the promise.

let client;

before(function(){
    client = new Client({port: 7033}).ensure()
                                     .catch(function (reason) {
                                         console.error(reason);
                                         throw reason;
                                     });
    return client;
});

it('tests client', function(){
    assert(client.isConnected);   // we know client is initialized
});

In either case, the initialization should be guaranteed complete before testing continues.  So unless I am missing something, there should not be any ambiguity about the initialization state.

If you wish to initialize before each test, it works just as well with beforeEach(...).  Also, note that there is a timeout that will cause test failure if done is not called quickly enough.  Reference the docs if you need to extend the timeout as there are a variety of patterns.

While I think the existing pattern fully addresses your use case, you might prefer the argument injection for stylistic reasons.  In that case I propose you can create a wrapper that calls the test function in the context of the client's then handler.

function provide_client(testFunc) {
    return function (done) {
        // Here I assume that the initialized client is passed through `then`.
        // If not fetch it from where ever appropriate.
        new Client({port: 7033}).ensure().then(function (client) {
            testFunc(client);
            done();
        }).catch(function (reason) {
            console.error(reason);
        });
    };
}

// Application
it('tests client', provide_client(function (client) {
    assert(client.isConnected);
}));


Can you make this Key-interable view of a List of Maps better? I have a list of map entries, and I need an iterable that returns the keys.

Of course, we could be naive and copy over into a new collection of the desired type, but that's inefficient.

So let's see if we can provide a view of the existing structure using generics.  Yes, I was able to do that, but it's not perfect: it gives unchecked conversions when it's passed to a function expecting Iterable<K>.  Could it be improved to avoid these warnings?

Perhaps it could implement Iterable<K> similar to the commented out line which is the path I attempted but couldn't complete.  Can you figure out the similar but correct (no warnings on usage) generic implementation?

This should help demonstrate how the ListKeyIterable is used:

List&LT; Map.Entry &LT; Long,String &GT; &GT; list;

void traverse( Iterable&LT;Long&GT; ) {}

traverse( new ListKeyIterable&LT;List&LT;Map.Entry&LT;Long,String&GT;&GT;&GT;( list );

Here is the working code, but it gives unchecked conversion warning on the call to traverse().

class ListKeyIterable&LT;T extends List&LT;? extends Map.Entry&LT;?,?&GT;&GT;&GT; implements Iterable
//class ListKeyIterable&LT;T extends List&LT;? extends Map.Entry&LT;K,?&GT;&GT;&GT; implements Iterable&LT;K&GT;
{
    T list;

    public ListKeyIterable( T list ) { this.list = list; }

    class ListKeyIterator&LT;K&GT; implements Iterator&LT;K&GT; {
        Iterator&LT;Map.Entry&LT;K,?&GT;&GT; iterator;

        public ListKeyIterator( Iterator&LT;Map.Entry&LT;K,?&GT;&GT; iterator ) { this.iterator = iterator; }
        @Override public boolean hasNext() { return iterator.hasNext(); }
        @Override public K next() { return iterator.next().getKey(); }
        @Override public void remove() { throw new RuntimeException( "ValueListIterator remove() not implemented." ); }
    }

    @Override public Iterator iterator() { return new ListKeyIterator( list.iterator() ); }
    //@Override public &LT;K&GT; Iterator&LT;K&GT; iterator() { return new ListKeyIterator( list.iterator() ); }
}

Just parameterize with both types:

class ListKeyIterable<K,T extends List<? extends Map.Entry<K,?>>> implements Iterable<K>;