Calculate the sum at a level of a binary tree represented in a String Fair preface: This is an interview question I would like to improve my knowledge of. I got some rest, and re-solved the problem with a fresh/unpanicked mind.

Given input of the type (10(5(3)(12))(14(11)(17)))
which would represent the following tree

 n=0            10
 n=1       5         14
 n=2    3    12    11   17

My task is to find the summation of values at a particular tier, like \$5+14=19\$ which is the sum for \$n=1\$, or \$3+12+11+17=43\$ the sum for \$n=2\$.

Considering this is a binary tree, a recursive function seems appropriate.

My main utility functions are:

stripFirstLastParen – strips the first and last paren
getCurrentVal – retrieves the value of the current node
getChildren – retrieves the left and right nodes

var input =
"(10(5(3)(12))(14(11)(17)))";

function stripFirstLastParen(input){
  if(input[0] !== "(" || input[input.length - 1] !== ")"){
    console.error("unbalanced parens")
  }
  else{
    input = input.substr(1);
    input = input.substring(0, input.length - 1);
  }
  return input;
}

function getCurrentVal(input){
  var val = "";
  while(input[0] !== "(" && input[0] !== ")" && input.length){
    val += input[0];
    input = input.substr(1);
  }
  return {
    val,
    input
  }
}

function getChildren(input){
  var val = "";
  if(input.length == 0){
    return {
      left: "",
      right: ""
    }
  }
  if(input[0] !== "("){
    console.error("no open paren at start");
  }
  val += input[0];
  input = input.substr(1);
  var parenStack = 1;
  while(parenStack > 0){
    if(input[0] == ")"){
      parenStack--;
    }
    else if(input[0] == "("){
      parenStack++;
    }
    val += input[0];
    input = input.substr(1);
  }
  return {
    left: val,
    right: input
  }
}

function getValueForLevel(input, k){
  var totalValue = 0;
  input = stripFirstLastParen(input);
  var currentValue = getCurrentVal(input);
  var children = getChildren(currentValue.input);
  if(k > 0){
    if(children.left.length){
      totalValue += getValueForLevel(children.left, k-1);
    }
    if(children.right.length){
      totalValue += getValueForLevel(children.right, k-1);
    }
  }
  else if(k == 0){
    totalValue += JSON.parse(currentValue.val);
  }
  return totalValue;
}

var test = getValueForLevel(input, 2);
console.log(test);

My main concerns are:

String manipulation. How should I properly be passing the altered string throughout the recursive function? Callout for lines like

  var currentValue = getCurrentVal(input);
  var children = getChildren(currentValue.input);

Where the getChildren function relies on getCurrentVal removing the value from the string itself, that feels dirty.

Complexity. I'm having difficulty describing the complexity of my procedure, and would argue that it's somewhere between \$O(n)\$ and \$O(n^2)\$, so is it \$O(n^2)\$? Considering the parens and values are removed as they are parsed, that lends itself to \$O(n)\$, but I feel it's \$O(n^2)\$ because of the duplicate parsing in order to create the child nodes. Is that correct? Can it be improved?

I tried to keep the "spirit of the challenge" and re-completed this within the amount of time previously allotted (somewhere around 30-45 minutes). Suggestions and improvements need not consider this time restriction, but providing context is important.

Recursion:

  Considering this is a binary tree, a recursive function seems
  appropriate.

Recursion would be a natural choice if your input were a root tree node with tree nodes as children - a recursive data structure. However, your input is a 'flat' string representation of a tree. A simple iteration might actually be much easier to implement, read and execute.

Passing inputs:

  How should I properly be passing the altered string throughout the
  recursive function?

I think the recursive passing down of substrings representing nodes or node lists (children) is already pretty well done.

However, I would like to suggest a few improvements regarding the parsing functions and their return values:

Style:

Consider the getCurrentVal(input) function:

function getCurrentVal(input){
  var val = "";
  while(input[0] !== "(" && input[0] !== ")" && input.length){
    val += input[0];
    input = input.substr(1);
  }
  return {
    val,
    input
  }
}

The code is not very descriptive: It is not immediately obvious what this function does.

The function name getCurrentVal is misleading, as you don't just return the node value, but also the children.
The argument name input is meaningless, as all arguments are inputs.
The variable names are misleading, as you reuse input to store part of your output.

How about this alternative:

// Split node 'a(b)(c)' into value 'a' and children '(b)(c)':
function parseNode(node) {
  let split = Math.min(node.indexOf('('), node.indexOf(')'));
  if (split < 0) split = node.length;
  return {
    value: node.slice(0, split),
    children: node.slice(split)
  };
}

'Parse' hints at the input being text or some other raw content.
'Node' carries more semantics than 'input'
Math.min and String.indexOf are more descriptive than a while loop.

Destructuring the resulting object improves readability:

var {value, children} = parseNode(node);

Also, when parsing integers, you shouldn't use JSON.parse(string) but the more specialized Number.parseInt(string) or the idiomatic type conversion via +string.

Further naming suggestions:

getValueForLevel -> getSumForLevel or sumTreeLevel
Consistency: Choose either val or value when naming currentValue.val, getCurrentVal, getValueForLevel

Complexity:

  Considering the parens and values are removed as they are parsed, that
  lends itself to O(n), but I feel it's O(n^2) because of the duplicate
  parsing in order to create the child nodes. Is that correct? Can it be
  improved?

First of all, let's define n as the length of the input string.
Then, let's look at the complexity of the helper functions:

stripFirstLastParen: O(n) because of input = input.substr(1)
getCurrentVal: O(n²) for worst-case input "1(2)(3)", "11(22)(33)", "111(222)(333)" and so on because of input = input.substr(1) within while (input.length). Yes, we break the loop as soon as we encounter the first parenthesis, but this doesn't happen before parsing roughly 1/3 * n characters for above input. The best-case complexity is however O(n) when the value has constant length.
getChildren has worst and best-case time complexity of O(n²) due to input = input.substr(1) within a while loop over input.

Now, we can tackle the complexity of getValueForLevel:

The first four lines are dominated by getChildren(currentValue.input). If the length of currentValue.input - the length of the children - is proportional to n, then it has a runtime complexity of O(n ²).
Then it calls getValueForLevel(children.left, k-1). It is easy to construct inputs which maximize the length of children.left such as "4(3(2(1))))" without right children. For this input, in each iteration, the length of children.left is reduced by 3.
The final call to JSON.parse is in O(n).

Adding the complexities together gives us:

n² + (n-3)² + (n-6)² + ... + (n-3k)²

Thus, for k = 0 the runtime complexity is in O(n²) and for maximum k we have a runtime complexity of O(n³):

In general, the runtime complexity is bounded by O(kn²).

Alternative approach:

Following my introductory remarks about a possibly simpler iterative solution, here a possible implementation with linear runtime complexity:

// Sum integer tree nodes at given level:
function sumTreeLevel(tree, level) {
  let tokens = tree.match(/(\(|[0-9]+|\))/g);
  let sum = 0;
  for (let token of tokens) {
    if (token === '(') {
      level--;
    } else if (token === ')') {
      level++;
    } else if (level === -1)  {
      sum += +token;
    }
  }
  return sum;
}

// Example:
console.log(sumTreeLevel("(10(5(3)(12))(14(11)(17)))", 2)); // 43


Extend jQuery with enable/disable function I want to create an extended disable/enable function in jQuery. This is working, but is this the best solution? Is each loop necessary?

 $.fn.ariaDisabled = function (isDisabled) {
        /// <summary>
        ///     Sets the disabled state.
        /// </summary>
        return this.each(function () {

            var $item = $(this);

            if (isDisabled === true) {
                $item
                    .attr('disabled', 'disabled')
                    .attr('aria-disabled', 'true')
                    .addClass('disabled');
            }
            else {
                $item
                    .removeAttr('disabled')
                    .removeAttr('aria-disabled')
                    .removeClass('disabled');
            }
        });
    };

Overall it looks quite nice.
Just a few points:

The parameter name is asking a question about the element, not making a statement of what to do. I would rename it to disable which enables the caller to better signify their intent.
In the same vein, I would also rename the function to ariaDisable as it performs an action as opposed to asking a question

Edit
Per m90's comment the loop is per jQuery plugin conventions as noted here


Small Twitter bot made in Python I've just started to play around with Python and I've decided to create a little script that post tweets every hour (cronjob on Ubuntu) telling what time it is.

I'm not sure if I follow best practices or if I can make the code even shorter/cleaner/nicer? I'm a C# developer so I miss a few things in Python, like string.Empty and list.First().  Do these features exist in Python?

from twitter import *
from datetime import datetime
import pytz

TOKEN = "SECRET_STUFF"
TOKEN_KEY = "SECRET_STUFF"
API_KEY = "SECRET_STUFF"
API_SECRET = "SECRET_STUFF"

def init(timestamp = datetime.now(pytz.timezone('Europe/Stockholm')).time()):
    number_of_rings = get_number_of_times_to_display_alarm(timestamp)
    send_tweet(compose_tweet(number_of_rings, timestamp))

def get_number_of_times_to_display_alarm(timestamp):
    # Convert our timestamp to 12h format, split it, select first element(hours)
    # and cast to int to remove leading 0 (e.g. 09.00 will give us 9)
    return int(timestamp.strftime("%I:%M %p").split(':')[0])

def compose_tweet(number_of_rings, timestamp):
    # Creates a tweet, e.g. "BONG...BONG...BONG #03:00
    ALERT_SOUND = "BONG"
    tweet = ""
    for i in range(number_of_rings):
        tweet += "%s%s" %(ALERT_SOUND, "..." if i < (number_of_rings - 1) else "")

    tweet += " #%s:%s" %(str(timestamp.hour).zfill(2), str(timestamp.minute).zfill(2))
    return tweet

def send_tweet(tweet):
    auth = OAuth(TOKEN, TOKEN_KEY, API_KEY, API_SECRET)
    t = Twitter(auth=auth)
    t.statuses.update(status=tweet)

init()

UPDATE
Based on the great feedback I got from @LiavK I've now updated my code as follows:

from twitter import OAuth, Twitter
from datetime import datetime
import pytz

TOKEN = "SECRET_STUFF"
TOKEN_KEY = "SECRET_STUFF"
API_KEY = "SECRET_STUFF"
API_SECRET = "SECRET_STUFF"

MY_TZ = pytz.timezone('Europe/Stockholm')
now = datetime.now(MY_TZ).time()

def get_current_hour(timestamp):
    return timestamp.hour % 12

def compose_tweet(number_of_rings, timestamp):
    # Creates a tweet, e.g. "BONG...BONG...BONG #03:00
    ALERT_SOUND = "BONG..."
    tweet = (ALERT_SOUND * number_of_rings)[:-3] # Removes last ...
    tweet += " #%s:%s" %(str(timestamp.hour).zfill(2), str(timestamp.minute).zfill(2))
    return tweet

def send_tweet(tweet):
    auth = OAuth(TOKEN, TOKEN_KEY, API_KEY, API_SECRET)
    t = Twitter(auth=auth)
    t.statuses.update(status=tweet)

def main(timestamp = now):
    number_of_rings = get_current_hour(timestamp)
    send_tweet(compose_tweet(number_of_rings, timestamp))

if __name__ == "__main__":
    main()

from twitter import *

Importing * is generally considered bad practice, because you don't know what's being imported into your local namespace. For you case, I believe you can get away with just doing import twitter. In the general case, if you only need a few things from a module, you can do:

from foo import bar, baz, quux

Alternatively if you need everything from foo just do import foo and then call foo.bar(), foo.baz(), etc. If you get tired of typing long names, you can do something like import jabberwocky as foo.

def init(timestamp = datetime.now(pytz.timezone('Europe/Stockholm')).time()):

I think there's serious readability issues with this, and I also can't think of any time I've ever seen a function/method being called inside another function's signature. I'm going to go out on a limb and say this is a Bad Idea -- for one thing, I suspect that automated code documentation tools might have trouble parsing this. More fundamentally, a function/method's signature is its interface with the rest of the world. It just seems like a very bad trade off to muddy the readability of a signature in exchange for saving a couple of times of code. I would refactor to something like:

MY_TZ = pytz.timezone('Europe/Stockholm')
now = datetime.now(MY_TZ).time()
def init(timestamp = now):

You could also think about how you actually initialize this script. You mentioned you're running it as a cron job, so I think this layout makes sense, but you could also rewrite this as a class and place the init logic into the __init__ method of the class.

def get_number_of_times_to_display_alarm(timestamp):
    # Convert our timestamp to 12h format, split it, select first element(hours)
    # and cast to int to remove leading 0 (e.g. 09.00 will give us 9)
    return int(timestamp.strftime("%I:%M %p").split(':')[0])

This is not bad at all, but here are a couple of alternatives:

now = datetime.now(MY_TZ).hours
if now > 12:
    now -= 12
return now

We've already used datetime.now(), it's both simpler than timestamp.strftime and it's nice to not have to introduce new functions unless necessary. There's an even shorter alternative you could use, which trades off a little readability for space:

now = datetime.now(MY_TZ).hours % 12

This uses the modulo function to convert 24h to 12 h clock.

Also, it's better to use docstring in for your code documentation. Something like "Convert our timestamp to 12h format, split it, select first element(hours)
and cast to int to remove leading 0 (e.g. 09.00 will give us 9)" is closer to being documentation for yourself/others. It should be a docstring. You should also think about removing the implementation specific elements -- those are more appropriate to use a # comment. I would rewrite the comment as:

"""Convert our timestamp to 12h format and remove leading zeros. Returns an Int."""

That decouples the interface of the function from its implementation.

One nitpick about your above code, which I only noticed noodling around with it now in a shell session: get_number_of_times_to_display_alarm. That's a very long function name. It's generally good to be longer than shorter and more explicit than less, but also consider it can be tiring and people have to remember the names of your functions. Try to find the shortest name that accurately and specifically describes what the logic does. I would probably name that logic something like get_current_hour.

def compose_tweet(number_of_rings, timestamp):
    # Creates a tweet, e.g. "BONG...BONG...BONG #03:00
    ALERT_SOUND = "BONG"
    tweet = ""
    for i in range(number_of_rings):
        tweet += "%s%s" %(ALERT_SOUND, "..." if i < (number_of_rings - 1) else "")

This could be sweated down a bit. For example:

for i in range(hour):
    tweet += "%s%s" % (ALERT_SOUND, "..." if i < (hour - 1) else "")

I don't think you need the else clause in that. You could refactor it to something like:

def compose_tweet(hour, timestamp):
    """ Creates a tweet, e.g. "BONG...BONG...BONG #03:00. """
    ALERT_SOUND = "BONG..."
    tweet = ""
    for i in range(hour):
        tweet += ALERT_SOUND
    tweet += " #%s:%s" % (str(timestamp.hour).zfill(2), str(timestamp.minute).zfill(2))
    return tweet

An even shorter version could be built around tweet = ALERT_SOUND * hour.

init()

A common pattern for python modules is to place:

if __name__ == "__main__":
    init()

At the end of the file. This allows the file to either run as a script or to be imported into other modules. For example, if you wanted to reuse your get_current_hour function in a different project, you could then do from twitClock import get_current_hour.


cm-to-inch calculator After a few pages reading Learning Python Hard Way, I've decided to try to make a simple cm-to-inch calculator. I am very excited about this achievement, and I want someone to check my code. It works well, but i just need someone to  confirm everything is written well.

# cm to inch calculator
inch = 2.54 #centimeters
centimeters = int(input("Enter a number of centimeters"))
print "Entered number of %s centimeters is equal to %s inches" % (centimeters , centimeters / inch)

Great work so far! And good on you for seeking review. In general, your code is pretty good, and works correctly. As you've asked, though, here are some suggestions for improvement.

The assignment:

inch = 2.54 #centimeters

is potentially confusing; instead, you could make it clear that it is a ratio:

CM_PER_INCH = 2.54

Note the UPPERCASE_WITH_UNDERSCORES name for a constant, per the style guide.

centimeters = int(input("Enter a number of centimeters"))

There is no reason to limit the user to int input - why not allow float? Then they can enter and convert e.g. 4.2cm.

Also, this will fail with input that can't be converted to an integer (what if the user types seven?) - have a look at this SO community wiki if you want to add validation.

print "Entered number of %s centimeters is equal to %s inches" % (centimeters , centimeters / inch)

This line is too long (see the style guide again). Also, % formatting is a little old-fashioned, compared to str.format. I would split this into two lines:

template = '{.2f}cm is equal to {.2f}"'
print template.format(centimeters, centimeters / CM_PER_INCH)

Or use line continuation:

print '{.2f}cm is equal to {.2f}"'.format(
    centimeters,
    centimeters / CM_PER_INCH
)

In use:

>>> print template.format(float(centimeters), centimeters / CM_PER_INCH)
5.00cm is equal to 1.97"

If you want another challenge, have a go at implementing the reverse calculation, and allowing the user to choose which way to convert.


Default initialization of items using Scrapy I am writing a scraper, using Scrapy, in which I need to populate items with default values at first.

Could my method be improved?

 def sp_offer_page(self, response):
            item = MallCrawlerItem()
            for key, value in self.get_default_item_dict().iteritems():
                item[key] = value
            item['is_coupon'] = 1
            item['mall'] = 'abc'
            # some other logic
            yield item

    def get_default_item_dict(self):     # populate item with Default Values
        return {'mall': 'null', 'store': 'null', 'bonus': 'null',
                'per_action': 0, 'more_than': 0,
                'up_to': 0, 'deal_url': 'null', 'category': 'null', 'expiration': 'null', 'discount': 'null',
                'is_coupon': 0, 'code': 'null'}

You can use Field() default values as suggested.

class MalCrawlerItem(Item):
    mall = Field(default='null')
    store = Field(default='null')
    bonus= Field(default='null')
    per_action = Field(default='null')
    more_than = Field(default='null')
    up_to = Field(default='null')
    deal_url = Field(default='null')
    category = Field(default='null')
    expiration = Field(default='null')
    discount = Field(default='null')
    is_coupon = Field(default='null')
    code = Field(default='null')

You can also use Item copy in the constructor.

#initialize default item
default = MallCrawlerItem()
default['mall'] ='null'
default['store'] = 'null'
default['bonus'] = 'null'
default['per_action'] = 0
default['more_than'] = 0
default['up_to'] = 0
default['deal_url'] = 'null'
default['category'] = 'null'
default['expiration'] = 'null'
default['discount'] = 'null'
default['is_coupon'] =  0
default['code'] = 'null'

#copy to new instance
item = MallCrawlerItem(default)

The benefits of this approach are:

constructor copy is the fastest method outside of class definition
you can create specific default item for your current function. e.g. initializing fixed fields of item before entering a for loop


Kattis prime reduction challenge I am solving the Prime Reduction challenge on Kattis.

  Consider the following process, which we’ll call prime reduction. Given an input x:

  if x is prime, print x and stop
  factor x into its prime factors p1, p2, …, pk
  let x = p1 + p2 + ⋯ + pk
  go back to step 1

  Write a program that implements prime reduction.

  Input

  Input consists of a sequence of up to 20000 integers, one per line, in the range 2 to 109. The number 4 will not be included in the sequence (try it to see why it’s excluded). Input ends with a line containing only the number 4.

  Output

  For each integer, print the value produced by prime reduction executed on that input, followed by the number of times the first line of the process executed.

I have already solved it using Java. Now I am trying to solve it in python. My code did well on the sample tests, but on the second test my code fails due to time limit exceeded.

Someone could tell me what I did wrong?

My python code:

import sys
from math import sqrt, floor

def is_prime_number(number):
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    return not any(number % divisor == 0 for divisor in range(3, floor(sqrt(number)) + 1, 2))

def sum_prime_factors(number):
    factors = 0
    while number % 2 == 0:
        factors += 2
        number = floor(number / 2)
    if is_prime_number(number):
        factors += number
        return factors
    for factor in range(3, floor(sqrt(number)) + 1, 2):
        if is_prime_number(factor):
            while number % factor == 0:
                factors += factor
                number = number / factor
            if number == 1:
                return factors
    factors += number
    return factors

def print_output(x, i):
    if is_prime_number(x):
        print(x, i)
        return
    i = i + 1
    factors = sum_prime_factors(x)
    print_output(factors, i )

[print_output(item, 1) for item in map(int, sys.stdin) if item != 4]

Some ideas:

is_prime_number doesn't scale well when dealing with bigger primes - the range of odd numbers 3..sqrt(number) is going to get very big. You'd be better off implementing a more sophisticated algorithm such as Eratosthenes' Sieve, where the cost of checking primality of subsequent primes grows slower.
sum_prime_factors duplicates the implementation of primality checking from is_prime_number.
[print_output(item, 1) for item in map(int, sys.stdin) if item != 4] is awkward. I would use a main method and any of the common

if __name__ == '__main__':
    main()

patterns for making the code reusable and testable.


iterate over an array and delete elements conditionally The following logic:

Iterate over the URLs array and If the HTTP request with the given URL does not timeout, continue. If the URL times out, remove it from the array and continue with the next one until the array is exhausted.

Has been implemented in the following way:

@urls.delete_if do |url|
  begin
    doc = perform_request(some_params)
    break
  rescue TimeoutError
    Rails.logger.warn("URL #{url} times out, will be removed from list")
    true
  end
end

Anyone for a cleaner solution? Basically, I want to iterate over an array and remove elements from it if there is a timeout, but if the URL works loop should end and app should continue processing.

note : your break is useless, because if the block returns a falsey value, the url is kept.

Maybe it can just be a bit more expressive ?

def timeouts?( url )
  perform_request( url ) && false
rescue TimeoutError
  true
end

@urls.delete_if {|url| timeouts?( url ) }

You could even make timeouts? a method on your @urls objects, for extra readability :

@urls.delete_if( &:timeouts? )

if you want to keep @tokland's functionnal approach, just use :

@kept_urls = @urls.reject{|url| timeouts?( url ) }

however, it would not be fully "functionnal", because timeouts may not return the same results with the same arguments, depending on the execution environment.


Recursive function that generates the permutations of a string I am looking for a review of my recursive function that generates the permutations of a string. Are there better ways to do this?

var permutations = [];

function doPerm(str, arr) {
    if (typeof (str) == 'string') str = str.split('');
    if (str.length == 0) permutations.push(arr.join(''));
    for (var i = 0; i < str.length; i++) {
        var x = str.splice(i, 1);
        arr.push(x);
        doPerm(str, arr);
        arr.pop();
        str.splice(i, 0, x);
    }
}
doPerm('', []);
console.log(permutations);

Your code seems to be correct, and is written in a good style. However, both the interface of your code as well as the algorithm used can be improved.

You currently have a global variable permutations which also contains the output. This variable will have to be cleared every time before doPerm is invoked. Instead, wrap doPerm in another function that provides initialization and input validation:

function perms(data) {
    if (!(data instanceof Array)) {
        throw new TypeError("input data must be an Array");
    }

    data = data.slice();  // make a copy
    var permutations = [],
        stack = [];

    function doPerm() {
        if (data.length == 0) {
            permutations.push(stack.slice());
        }
        for (var i = 0; i < data.length; i++) {
            var x = data.splice(i, 1);
            stack.push(x);
            doPerm();
            stack.pop();
            data.splice(i, 0, x);
        }
    }

    doPerm();
    return permutations;
}

var input = "abcd".split('');
var result = perms(input);
for (var i = 0; i < result.length; i++) {
    result[i] = result[i].join('');
}
console.log(result);

Note that this function will operate on arrays of any type and does not special-case strings.

Your algorithm currently relies on splicing elements into and out of the input array. This is somewhat expensive on larger data sets, and it would be better to generate the permutations by swapping. Heap's Algorithm does just this.


Maximum subarray problem in JavaScript I am new to JavaScript. I've recently completed first 10 Chapters of "JavaScript: The Good Parts".

I've coded this small program to find maximum subarray of an array and would appreciate your feedback on the structure of the program (from JavaScript's point of view). I am basically looking for suggestions in following areas:

Objects being returned
Usage of Infinity
Usage of non-pure functions
Closures

Here is the code:

// Max. subarray from CLRS
var maxsubarr = function (arr) {
    var that  = {};

    var max_cross_subarr = function (low, mid, high) {
        var left_sum = -Infinity;
        var right_sum = -Infinity;
        var max_low;
        var max_high;

        var sum = 0;
        var i;
        for (i=mid; i >=low; i--) {
            sum = sum + arr[i];
            if (sum > left_sum) {
                left_sum = sum;
                max_low = i;
            }
        }
        sum = 0;
        for (i=mid+1; i <=high; i++) {
            sum = sum + arr[i];
            if (sum > right_sum) {
                right_sum = sum;
                max_high = i;
            }
        }

        return {
            low: max_low,
            high: max_high,
            sum: left_sum + right_sum
        };
    }

    var max_sub_arr = function (low, high) {
        var leftarr, rightarr, mid;
        if (low === high) {
            return {
                low: low,
                high: high,
                sum: arr[low]
            };
        }
        else {
            mid = Math.floor((high+low)/2);
            leftarr = max_sub_arr (low, mid);
            rightarr = max_sub_arr (mid+1, high);
            crossarr = max_cross_subarr (low, mid, high);

            if (leftarr.sum >= rightarr.sum && leftarr.sum >= crossarr.sum) {
                return leftarr;
            } else if (rightarr.sum >= leftarr.sum && rightarr.sum >= crossarr.sum) {
                return rightarr;
            } else {
                return crossarr;
            }
        }
    }

    that.find = function () {
        return max_sub_arr (0, arr.length - 1);
    }

    return that;
}

var mb = maxsubarr ([13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]);
console.log(mb.find());

Objects being returned.

This is fine as long as you define a convention and stick to it.

  Usage of Infinity

Your use case looks fine, you're using it as an upper and lower bound.

  Usage of non-pure functions

This one is a little subjective. For an algorithm like this, it makes sense to only write pure functions as that can make debugging easier. Your code is readable and clear, if a little contrived, but I wouldn't worry too much about this. JavaScript is sort of a weird language to ask this about since most functions won't follow this rule especially when you do DOM manipulation and frontend JavaScript.

  Closures

Very common in JavaScript. You should explore node.js if you're interested in learning more.

Nit: var that = {};. Aside from being a completely uninformative and useless variable name, this declaration isn't needed. You can rewrite the return statement as:

return {
    find: function() {
        return max_sub_arr(0, arr.length - 1);
    }
};

Or even better:

return max_sub_arr(0, arr.length - 1);

I don't see why you need to return a function to be invoked.


Can I further optimize this solution for HackerRank's “Making Candies”? My C++ solution for HackerRank's "Making Candies" problem, reproduced below, is as optimized as I can make it and appears similar to what others say are optimal solutions. However, six of the test cases still fail due to timing out. I would be interested to know if there are any significant opportunities to optimize my code that I missed.
I'm guessing that I'm either missing some way to simplify the computation (perhaps part of it can be precomputed and stored in a lookup table?), or there's some way to compute the answer without using a loop.
std::ios::sync_with_stdio(false);

long m, w, p, n;

std::cin >> m >> w >> p >> n;

for (long candies = 0, passes = 0, total = LONG_MAX; ; ++passes) {
    const auto production = __int128{m} * w;

    const long goal = n - candies;

    const long passes_needed = goal/production + !!(goal%production);

    const long subtotal = passes + passes_needed;

    if (passes_needed <= 2) {
        std::cout << subtotal;
        return 0;
    }

    if (total < subtotal) {
        std::cout << total;
        return 0;
    }

    total = subtotal;

    candies += production;

    if (candies >= p) {
        const auto d = std::div(candies, p);

        long budget = d.quot; candies = d.rem;

        const long diff = w - m;

        if (diff < 0) {
            const long w_hired = std::min(budget, -diff);

            budget -= w_hired;
            w += w_hired;
        } else if (diff > 0) {
            const long m_purchased = std::min(budget, diff);

            budget -= m_purchased;
            m += m_purchased;
        }

        const long half = budget >> 1;

        m += half + (budget & 1);
        w += half;
    }
}

Unlearn bad behavior taught by competitive coding sites
Competitive coding sites unfortunately teach some bad coding habits. You did not include your whole program, the #includes are missing for example. If you did #include <bits/stdc++.h>, don't.
The call to std::ios::sync_with_stdio() is only useful if your program is I/O bound, and it won't make a difference if you are just writing the final result to std::cout.
Use of integer types
__int128 is not a standard C++ type, and I don't think it is necessary at all to use it. The problem states that n is limited to \$10^{12}\$, so you only need 64-bit variables and some care to avoid values wrapping around.
A long is only guaranteed to be at least 32-bits in size. So reading in the initial values is already broken since they might be larger than that. Also, none of the values should ever become negative, so the appropriate type to use here is std::uint64_t.
Speeding up the algorithm
Yes, you can optimize your solution further. Consider the case where the desired number of candies n = 1000000000000, the cost is so high you can never buy/hire (p = n), and you start with m = 1 and w = 1. Then your loop will just do n iterations, adding 1 to candies each time.
What you should do is calculate how many iterations it would take to get enough money to buy/hire something new, and then advance that many iterations in one step. So:
const auto passes_needed_to_buy = candies < p ? (p - candies) / production : 0;

Of course, if this value is more than passes_needed, then you know you will never be able to buy anything before you produced enough candy.


Calculating the seconds between 2 numbers in a specific place in a string We have a

string text =
"SOME OTHER TEXT
WHITE SPACES AND NEW LINES

[HitObjects]
109,192,7241,1,0,0:0:0:0:
256,192,7413,1,0,0:0:0:0:
475,192,75865,1,0,0:0:0:0:
329,192,86524,1,0,0:0:0:0:
182,192,256242,1,0,0:0:0:0:
256,192,306521,1,2,0:0:0:0:

WHITE SPACES AND NEW LINES
"

The third number of every row is the milliseconds.
I need to know the seconds between the first time and last time.
Right now I'm doing it like this:

text = text.Substring(text.IndexOf("Objects]") + 8).Trim();
string[] lines = text.Split('\n');
string[] firstLine = lines[0].Split(',');
string[] lastLine = lines[lines.Length - 1].Split(',');
int length = Convert.ToInt32(lastLine[2]) - Convert.ToInt32(firstLine[2]);
length = length / 1000;

I need to do this with thousands of 'text's though. Any optimalization or other methodes possible?

more information on the request of @Slothario:

the string text is the full text of 1 file
file type: .osu
average file size: 25KB
average characters: 30000
SOME OTHER TEXT - HitObjects ratio: 1 - 100
average amount of files to check: 500

If you want to support an insane large file with a small hardware footprint you should use streaming. Something like

public static class Program
{
    public static void Main(string[] args)
    {
        string text =
            @"SOME OTHER TEXT
WHITE SPACES AND NEW LINES

[HitObjects]
109,192,7241,1,0,0:0:0:0:
256,192,7413,1,0,0:0:0:0:
475,192,75865,1,0,0:0:0:0:
329,192,86524,1,0,0:0:0:0:
182,192,256242,1,0,0:0:0:0:
256,192,306521,1,2,0:0:0:0:

WHITE SPACES AND NEW LINES
";

        Task.Run(async () =>
        {
            using (var reader = new StringReader(text)) //This should be streamed from a disk or network stream or similar
            {
                string line;
                var inScope = false;
                int? start = null;
                int last = 0;

                while ((line = (await reader.ReadLineAsync())) != null)
                {
                    if (inScope)
                    {
                        var values = line.Split(',');
                        if (values.Length != 6)
                            break;

                        last = int.Parse(values[2]);

                        if (!start.HasValue)
                            start = last;

                    } else if (line.StartsWith("[HitObjects]"))
                        inScope = true;
                }
                Console.WriteLine(last - start);
            }
        });

        Console.ReadLine();
    }
}


Counting the number of points that have both a larger theta and a larger radius than a given point I don't like the fact that I am selecting all the points, even though I only care about the count of them.

Which of the from parts should appear first, if it even matters?

var count = (from type in ValidTypes()
    from point in GetData(type)
    where point.Radius > referencePoint.Radius
        && point.Theta > referencePoint.Theta
    select point).Count()

ValidTypes() returns a few types, about 5.

GetData(type) may return many points, possibly 100,000.

This query is counting the number of points that have both a larger theta and a larger radius than a given point.

Is there a way to write this faster or more readable?

First, your query is written fine. Its structure is not a concern; the order of the froms is clearly correct, the select is appropriate. Where you could look for improvement that could change the query (code and possibly performance) would be in the GetData method. If, for example, GetData is getting data from an external, queryable source, then you may want to offload the filtering to it rather than getting all of the data points and filtering it inside your application, particularly since you have so many points of data (potentially). So maybe your query could instead be

(from type in ValidTypes()
 select GetData(type, referencePoint).Count())
.Sum();

// or same meaning, different phrasing

(from type in ValidTypes()
from point in GetData(type, referencePoint)
select point).Count();


App for displaying pictures to like I am making an app that shows some pictures and you can like each picture. I am sending a POST request from the Android device. In my backend I have a Python script that takes parameters category and URL of the picture, opens a JSON file, and modifies the "likes" value.

This is the Python script:

#!/usr/bin/python
# Import modules for CGI handling
import cgi, cgitb, json

# Create instance of FieldStorage
form = cgi.FieldStorage()

# Get data from fields
category= form.getvalue('category')
url= form.getvalue('url')

#Gets the file path,depending on the category
filepath='/home2/public_html/app/%s/%s.json' % (category,category)

# Open a file
with open(filepath) as data_file:
data = json.load(data_file)

# Finds the picture with the specific url and updates the likes value.
for picture in data:
    if picture ["url"] == url:
        likes = int(picture["likes"])
        picture["likes"]=str(likes+1)
        break

# Writes the json file with the new value.
with open(filepath, 'w') as data_file:
    data_file.write(json.dumps(data))

My JSON looks like this:

{"url": "http://pictures.com/app/Funny/picture.jpg", "category": "Funny", "likes": "0"}

What can go wrong with this script? Are there any potential drawbacks? I am new to backend programming, so I don't know what can go wrong here.

I'm not sure what this program is trying to do, but I can give a few suggestions for style and improvements.

Firstly, unless you're not using the python command to run this script on the command line, you don't need the #!/usr/bin/python.
Secondly, I'd separate the imports out on each separate line like so.

import cgi
import cgitb
import json

This is in case an error occurs with the imports, if thats the case, the error will be easier to find.
After that I'd separate certain things into functions and add docstrings. A few things I might want to separate into functions is opening the file, updating the like values, and writing to the JSON file. This gives your program a bit of re-usability.
My final bit of advice would be to remove or improve un-needed comments such as the following.

# Create instance of FieldStorage
# Open a file
# Import modules for CGI handling

I'd also recommend checking out Python's style guide, PEP8. Hope this helps!


Boost condition variable wrapper I would like to create a wrapper for a Boost conditional variable:

class Cond_wrap
{
private:
    boost::condition_variable cond;
    boost::mutex              mutex;
    bool work_to_do;
public:
    Cond_wrap()
    {
        work_to_do = false;
    }
    void notify_all()
    {
        boost::mutex::scoped_lock lock(mutex);
        work_to_do = true;
        cond.notify_all();
    }
    void wait()
    {
        boost::mutex::scoped_lock lock(mutex);
        while(!work_to_do)
        {
            cond.wait(lock);
            work_to_do = false;
        }
    }
    bool timed_wait(unsigned int timeout)
    {
        boost::mutex::scoped_lock lock(mutex);
        if(!work_to_do)
        {
            if(cond.timed_wait(lock, boost::chrono::milliseonds(timeout)))
            {
                work_to_do = false;
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
};

Cond_wrap condition_wrap;

void worker_func()
{
    {
        condition_wrap.notify_all();
    }
    std::cout << "After notify" << std::endl;
}

int main()
{
    boost::thread work(worker_func);
    work.detach();

    {
        boost::this_thread::sleep_for(boost::chrono::milliseonds(500));
        condition_wrap.wait();
        //there is work to do
    }
    return 0;
}

What is the main goal of that wrapper? I would like to avoid a situation in which a condition will be notified before I call waiter. Regarding this, I want to provide a help variable bool which should remember if a condition was previously set.

Small example of what I mean:

boost::condition_variable cond;
boost::mutex              mutex;

void worker_func()
{
    cond.notify_all();
    std::cout << "After notify" << std::endl;
}

void main()
{
    boost::mutex::soped_lock lock(mutex);
    boost::thread work(worker_func);
    boost::this_thread::sleep_for(boost::chrono::milliseonds(500));
    cond.wait(lock); // here is deadlock
}

The wrapper is also provides an easier way of using a Boost conditional variable.

The short answer here is: don't do this. It does not make boost::condition_variable easier to use. You're actually just limiting what you can do with it. You're not even exposing the entire interface...

But if you insist on doing such a thing, your wrapper is close. You're not handling spurious wakeup in timed_wait() - that can return true even without being signaled. You should just take advantage of the fact that the various wait() overloads also take a predicate:

void wait()
{
    boost::mutex::unique_lock lock(mutex);
    cond.wait(lock, [this]{ return work_to_do; });
    work_to_do = false;
}

bool timed_wait(unsigned int timeout)
{
    boost::mutex::unique_lock lock(mutex);
    if (cond.timed_wait(lock, boost::chrono::milliseconds(timeout),
                        [this]{ return work_to_do; })
    {
        work_to_do = false;
        return true;
    }
    else
    {
        return false;
    }
}

Really adding predicates is the way to handle calling wait() after the notify was called. The wrapper is not a good solution to this in my opinion.


Reversing k-sized sequences in a linked-list Here is my solution to this problem; please be brutally honest/strict, if I would have written this code, in a 45 minute interview, what would you think? (I am aiming for Google,Facebook).

Here is the problem I solved:

*Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.

  For example

  Given this linked list: 1->2->3->4->5

  For k = 2, you should return: 2->1->4->3->5

  For k = 3, you should return: 3->2->1->4->5

Thanks.

  public class ListNode {
     int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
     int count=1;
     ListNode cursor = head;
     ListNode current = null;
     ListNode remainingHalf = null;
     Queue linkQueue = new LinkedList();

     if(head==null){
         return null;
     }

     if(k<=1){
         return head;
     }
     if(k>findSize(head)){
         return head;
     }
     if(k==2){
         return reverse(head);
     }

     while(cursor!=null || cursor.next!=null){

         while(count!=k){
             if(cursor!=null){
                cursor = cursor.next;
             }
             count++;
         }
         if(cursor!=null){
             remainingHalf = cursor.next;
             cursor.next=null;

             ListNode partial = reverse(head);
             linkQueue.add(partial);

             cursor = remainingHalf;
             head = remainingHalf;
         }
         else{
             linkQueue.add(remainingHalf);
             break;
         }
         count=1;
         if(cursor==null || cursor.next==null){
             linkQueue.add(remainingHalf);
             break;
         }

     }
     boolean headFlag=false;
     ListNode toRet=null;
     while(!linkQueue.isEmpty()){
         ListNode first = (ListNode)linkQueue.poll();
         ListNode end=null;
         if(first!=null){
            end =  findEnd(first);
            if(headFlag==false){
                toRet = first;
                headFlag=true;
            }
         }
         else{
             break;
         }
         ListNode second = (ListNode)linkQueue.poll();
         if(second==null){
             ListNode temp = findEnd(toRet);
             temp.next=first;
             break;
         }
         end.next=second;

         if(linkQueue.size()==1 || linkQueue.size()==0){
             ListNode last = findEnd(toRet);
             last.next = (ListNode)linkQueue.poll();

         }
     }
     return toRet;

    }

    public int findSize(ListNode head){
        int count=0;
        while(head!=null){
            count++; head=head.next;
        }
        return count;
    }

    public ListNode findEnd(ListNode head){
        while(head.next!=null){
            head = head.next;
        }
        return head;
    }

    public ListNode reverse(ListNode head){
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode remaining = head.next;
        head.next = null;
        ListNode temp = reverse(remaining);
        remaining.next = head;
        return temp;
    }
}

Brutally honest?
If this is an interview, and you provide this line of code:

Queue linkQueue = new LinkedList();

Your resume gets put in the pile of 'ignore this person if they apply again'... ;-)
Genercis have been around for a decade now (introduced in 2004). You should know them, and use them.
Class Model
The ListNode should not be a public class. The information should be encapsulated within a single class, and not exposed. There should be no need for a user to have to supply a 'head' node to the public ListNode reverseKGroup(ListNode head, int k). This should be a class, say ReversingList which has a method reverseK(int k), and then provides a way to retrieve the re-ordered data (which may be in the format of a new ReversingList instance.
Algorithm
Your algorithm looks really complicated. There should be no need to scan the list before processing it. That indicates some serious inefficiencies.
Additionally, relying on the LinkedList class is a bit of a cheat... but, if you are going to use it, then you may as well go the whole hog, and use its reverse function... (descendingIterator())
How would I do it?
This was the original title of the question... well, how about:
public class SolutionList {

    private static final class ListNode {
        private final int val;
        private ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        @Override
        public String toString() {
            return "ListNode " + val;
        }
    }

    // use relatively common trick of having a dummy head node.
    private final ListNode head = new ListNode(0);

    public SolutionList() {
        // default constructor does nothing.
    }

    public void add(int v) {
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = new ListNode(v);
    }

    public void addAll(SolutionList toadd) {
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        ListNode their = toadd.head.next;
        while (their != null) {
            tail.next = new ListNode(their.val);
            tail = tail.next;
            their = their.next;
        }
    }

    public void reverseKInPlace(final int k) {
        if (k <= 1 || head.next == null) {
            return;
        }
        ListNode[] stack = new ListNode[k];
        int depth = 0;
        ListNode node = head.next;
        ListNode mark = head;
        while (node != null) {
            ListNode nxt = node.next;
            stack[depth++] = node;
            if (depth == k) {
                while (--depth >= 0) {
                    mark.next = stack[depth];
                    mark = mark.next;
                }
                depth = 0;
            }
            node = nxt;
        }
        if (depth > 0) {
            mark.next = stack[0];
        }

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("SolutionList [");
        ListNode node = head.next;
        while (node != null) {
            sb.append(node.val).append(", ");
            node = node.next;
        }
        if (head.next != null) {
            sb.setLength(sb.length() - 2);
        }
        sb.append("]");
        return sb.toString();
    }

    public SolutionList reverseK(final int k) {
        SolutionList copy = new SolutionList();
        copy.addAll(this);
        copy.reverseKInPlace(k);
        return copy;
    }

    public static void main(String[] args) {
        int[] vals = { 1, 2, 3, 4, 5 };
        SolutionList soln = new SolutionList();
        for (int v : vals) {
            soln.add(v);
        }
        System.out.println(soln);
        System.out.println("Reverse 2 " + soln.reverseK(2));
        System.out.println("Reverse 3 " + soln.reverseK(3));
    }

}


API POST to save a new item in a Database via PHP & MYSQLI Is this correct MYSQLI implementation?
IS it safe from injection?
IS the object cleanup done properly?

<?php

include_once '../../securelogin/db_connect.php';
include_once '../../securelogin/functions.php';

sec_session_start();

if (login_check($mysqli) == true)
{
    $con = new mysqli("localhost", "username", "password", "databasename_todo");

    // Check connection
    if ($con->connect_errno)
    {
        echo "Failed to connect to MySQL: (" . $con->connect_errno . ") " . $con->connect_error;
    }
    else
    {
        $jsonText = file_get_contents('php://input');
        $decodedText = html_entity_decode($jsonText);
        $myArray = json_decode('[' . $decodedText . ']', true);

        $newText = $myArray[0]['TEXT'];
        $newOwnerID = $myArray[0]['OWNER_ID'];
        $newCreateDate = date("Y-m-d");
        $newCompleted = 'N';

        $newText = mysqli_real_escape_string($con, $newText);

        if(!($sql = $con->prepare("INSERT INTO checklistitems (TEXT, OWNER_ID, COMPLETED, CREATE_DATE, CREATE_USER) VALUES (?,?,?,?,?)")))
        { echo "Prepare failed: (" . $con->errno . ") " . $con->error;}

        if(!$sql->bind_param('sissi', $newText, $newOwnerID, $newCompleted, $newCreateDate, $newOwnerID))
        {echo "Binding parameters failed: (" . $sql->errno . ") " . $sql->error;}

        if(!$sql->execute())
        {echo "Execute failed: (" . $sql->errno . ") " . $sql->error;}

        echo "SUCCESS - Affected rows ADD: " . $con->affected_rows;

        $sql->close();
    }

    $con->close();
    $con = null;
}
else
{
    echo "Error! You are not authorized to access this page. Please login.";
}
?>

What are these lines all about?

$thread = $con->thread_id;
$con->close();
$con->kill($thread);
$con = null;

it seems a bit, sorry for the pun, overkill. According to the PHP manual this should do just fine:

$con->close();

but even if you leave it out, the connection will be closed automatically when the script terminates. See:

http://php.net/manual/en/mysqli.construct.php

read the examples, and see:

http://php.net/manual/en/mysqli.close.php


Move Line across Plane I want move a  Vertical line segment across a plane or another way sweep the plane, from Left to right.

The figure illustrates how the segment is moving at the X-axis. When x1 >= X beginning and i translate it to the upper part and so on, till y2 which is the upper part of the segment reaches Y. You can think of it as how a scanner works.

Line = (x1,y1,x2,y2)

When x1 pr x2 coordinates becomes greater or equal to -rightBorder I increase y1 and y2 to the next level and so on till y2 becomes greater than Y.

Algorithm:

  #define STEP 9
  #define Y 20
  #define X 30
    void moveLine(int, int, int, int);
    int main()
    {
            moveLine(5, 0, 5, 10);
            return 0;

    }

    void moveLine(int x1, int y1, int x2, int y2)
    {
        //Reaches upper border (Y-axis)
        if (y1 >= Y)
        {
            return;
        }
       // cout << y1 <<"   "<< y2 << endl;
       // Increase y1 and y2 and Return to the beginning
        if (x1 >= X)
        {
           //startint points
            y1 += 10;
            y2 += 10;
            // Reinitialize x1 and x2
            x1 = -4;
            x2 = -4;
        }
        // sweep again
        moveLine(x1 + STEP, y1, x2  + STEP,y2);

    }

Explanation:

I start with x1 = 5, and x2 = 5, y1 = 5 and y2 = 10 then x1+=9, x2+=9 till x1 >= X, then I reinitialize the x1 and x2, and increase y1 by 5 and y2 + 5 till y2 becomes greater than Y.

I wrote the piece of Code. it worked ok, but I wanted to your advice and if the recursion function is okay.

Thank you.

Your code has a lot of magic numbers.  I can't tell what the significance of the number 20 that is being compared to y1, or the significance of the 20 that is being compared to x1, or whether the two numbers are the same or different (if I changed the number compared to y1 to 30, should I also change the number compared to x1?).  One of the comparisons uses > and the other uses >=.  I can't tell whether this is what you meant to do or a bug.

If you created named constants with descriptive names, probably all of those things would be obvious.

I think you have a misconception about how function arguments work.  Despite having the same name and the same type, the int x1 in main() and the int x1 in moveLine() are different, and the x1 in each recursive call of moveLine() are different.

The line moveLine(x1 += 9, y1, x2+=9,y2); should work, but writing it as moveLine(x1+9, y1, x2+9, y2); is less confusing and would also work.

Also, this code:

int x1 = 5;
int y1 = 0;
int x2 = 5;
int y2 = 10;
moveLine(x1, y1, x2, y2);

could be written like this:

moveLine(5, 0, 5, 10);

(I'm not suggesting you keep the 4 int style; Barry's suggestion is good.  I'm just pointing out what looks like a misconception and trying to clear it up.)


string io and parsing To learn Rust, I tried to write a function that takes string input and then converts it to integers for a time calculation for a delay.

Is this approach ok? Have I made any mistakes? I kind of struggled with needing to do two separate error checks for the string. First for the parse result and second for the limiting the unwrapped value. I was hoping to combine the is_ok call and then unwrapped value check in one condition. Ran into some borrowing error messages and type problems.

use std::io;

fn read_time(message : &str, max : u64) -> u64 {
    let mut input = String::new();

    loop {
        println!("{}", message);
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        let num = input.trim().parse::<u64>();

        if num.is_ok() {
            let n = num.unwrap();

            if n < max {
                return n;
            }
            else {
                println!("exceeded max value of {}", max - 1);
            }
        }
        else {
            println!("Need a number above 0 and less than {}", max);
        }
    }
}

fn main() {

    println!("Waiting Sample Program");

    let hours = read_time("Enter hours: ", 24);

    let minutes = read_time("Enter minutes: ", 100);

    let wait = hours * 60 + minutes;

    println!("Going to wait {} minutes", wait);

    std::thread::sleep(std::time::Duration::new(wait * 60, 0));

    println!("done.");
}

Instead of checking if the parse succeeded and then unwrapping the result in two steps, you can combine the operations by using pattern matching instead. Here, an if let expression will do the job.

if let Ok(n) = num {
    // use `n` here
}

I also have some suggestions concerning style, based on the prevailing style in the community:

Don't put a space between an identifier and the colon that precedes a type (message: &str rather than message : &str).
Put the } and the else on the same line.

Additionally, considering the way you've written the prompt messages, it looks like there shouldn't be a newline after the prompt, so I suggest you change the println! that prints the prompt to a print!.

Here's the revised code:

use std::io;

fn read_time(message: &str, max: u64) -> u64 {
    let mut input = String::new();

    loop {
        print!("{}", message);
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        let num = input.trim().parse::<u64>();

        if let Ok(n) = num {
            if n < max {
                return n;
            } else {
                println!("exceeded max value of {}", max - 1);
            }
        } else {
            println!("Need a number above 0 and less than {}", max);
        }
    }
}

fn main() {
    println!("Waiting Sample Program");

    let hours = read_time("Enter hours: ", 24);
    let minutes = read_time("Enter minutes: ", 100);
    let wait = hours * 60 + minutes;

    println!("Going to wait {} minutes", wait);

    std::thread::sleep(std::time::Duration::new(wait * 60, 0));

    println!("done.");
}

If you want to combine the result of parse with the range checking in a single operation, that's possible too. First, let's look at the "lazy" way, where both error situations will produce the same error message:

fn read_time(message: &str, max: u64) -> u64 {
    let mut input = String::new();

    loop {
        print!("{}", message);
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        let num = input.trim().parse::<u64>();

        if let Some(n) = num.ok().and_then(|n| if n < max { Some(n) } else { None }) {
            return n;
        }

        println!("Need a number above 0 and less than {}", max);
    }
}

Here, I'm using ok to convert the Result to an Option, because I'm too lazy to define an error type that unifies the parse error and our new out-of-range condition. Then I'm using and_then to perform the range validation only if the parse succeeded. The closure returns Some(n) if the value is in range, or None if the value is out of range.

Instead of using and_then, we could also use the filter method provided by the option-filter crate. It takes a closure that returns a bool, and returns None if the closures returned false, or the original value otherwise.

if let Some(n) = num.ok().filter(|n| n < max) {
    return n;
}

And now, let's not be lazy and code this up properly. We'll need to introduce a type that can represent either a parse error, or an out-of-range condition.

use std::num::ParseIntError;

enum ReadTimeError {
    ParseError(ParseIntError),
    ValueOutOfRange,
}

impl From<ParseIntError> for ReadTimeError {
    fn from(e: ParseIntError) -> Self {
        ReadTimeError::ParseError(e)
    }
}

fn read_time(message: &str, max: u64) -> u64 {
    let mut input = String::new();
    let check_in_range =
        |n| if n < max { Ok(n) } else { Err(ReadTimeError::ValueOutOfRange) };

    loop {
        print!("{}", message);
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        let num = input.trim().parse::<u64>();

        match num.map_err(ReadTimeError::from).and_then(check_in_range) {
            Ok(n) => return n,
            Err(ReadTimeError::ParseError(..)) => {
                println!("Need a number above 0 and less than {}", max);
            }
            Err(ReadTimeError::ValueOutOfRange) => {
                println!("exceeded max value of {}", max - 1);
            }
        }
    }
}

Here, we have three cases to handle, so I'm using a match expression rather than an if let expression. I'm taking advantage of the fact that patterns can match "deeply" to match on two levels of enums at the same time. Result also has an and_then method, and naturally, the closure must return a Result. I moved the closure out of line to keep the expression being matched on short enough.

Now, it's up to you to decide whether combining the two validations is worth the additional complexity or not! :)


Checking for hyperthreading I want to just write a simple function to check if my linux box has hyperthreading enabled. I want to know if there's a simpler way to produce the cpuinfo dict (would be great if I could use a dict comprehension somehow) or generally a better way to check this information:

def is_hyperthreading_enabled():
    cpuinfo = dict(map(str.strip, line.split(':'))
                   for line in open('/proc/cpuinfo')
                   if ':' in line)

    return cpuinfo['siblings'] != cpuinfo['cpu cores']

First off, you should always close a file in Python.
There are two ways to do that.

The old style way:

file_handler = open('/proc/cpuinfo')
// Your code here
file_handler.close()
The 'new' way with with.

with open('/proc/cpuinfo') as file_handler:
    // Your code here

The second is more recommended as then it's both clear when the file is open, and you don't forget to close it.

While /proc/cpuinfo is unlikely to have more than one : per line, it could happen. As it seems model name can be whatever the model is called. If a vendor were to put a : in their name, your code won't work. with the exception:

ValueError: dictionary update sequence element #1 has length 3; 2 is required

To avoid this as an issue, you can use the optional second argument to str.split(':', 1).

If you want to use a dictionary comprehension at all cost. Then it's the same as your above code, but it will have a dictionary comprehension surrounding it.

with open('/proc/cpuinfo') as file_handler:
    cpuinfo = {
        key: value
        for key, value in (
            map(str.strip, line.split(':', 1))
            for line in file_handler
            if ':' in line
        )
    }

This is in my opinion worse than your above code, as it's common knowledge that dict([['key', 'value']]) can be used to make a dict, which was added in 2.2. Where dictionary comprehensions were added in 2.7.
And your original code is a lot less verbose.

You could however use a functional approach to this. Which has the drawback of needing to define line twice, and is more verbose than the original code.

with open('/proc/cpuinfo') as file_handler:
    cpuinfo = dict(map(
        lambda line: map(str.strip, line.split(':', 1)),
        filter(lambda line: ':' in line, file_handler)
    ))

Overall I would recommend using your original code, but with with and line.split(':', 1)) added.

Just to note, ':' in line returns false every time the CPU core changes.
For example from my /proc/info. (note I removed the flags)

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 42
model name  : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
stepping    : 7
microcode   : 0x28
cpu MHz     : 1728.761
cache size  : 6144 KB
physical id : 0
siblings    : 4
core id     : 0
cpu cores   : 4
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
bugs        :
bogomips    : 6800.31
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

processor   : 1
vendor_id   : GenuineIntel
cpu family  : 6
model       : 42
model name  : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
stepping    : 7
microcode   : 0x28
cpu MHz     : 1686.609
cache size  : 6144 KB
physical id : 0
siblings    : 4
core id     : 1
cpu cores   : 4
apicid      : 2
initial apicid  : 2
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
bugs        :
bogomips    : 6800.31
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

This also shows that the information can change. E.g. cpu MHz:1728.761 and cpu MHz:1686.609. So you may not want to overwrite some of this information. Also if you have more than one CPU (say you are using a sever) then you could return false on one CPU and true on another, but as the last core overwrites all the previous data it's somewhat up to chance to know.

Due to this I would recommend that you change your function to make cpuinfo a list of dicts.

Finally as far as I know unless you read the entire file and split on \n\n then there is no way to make it a comprehension.
And so I would recommend:

def is_hyperthreading_enabled():
    with open('/proc/cpuinfo') as file_handler:
        cpuinfo = []
        temp_dict = {}
        for line in file_handler:
            try:
                key, value = map(str.strip, line.split(':', 1))
            except ValueError:
                cpuinfo.append(temp_dict)
                temp_dict = {}
            else:
                temp_dict[key] = value

    return any(map(lambda core: core['siblings'] != core['cpu cores'], cpuinfo))

Note, the above works as I make the assumption that the file always ends with an empty line. Otherwise you would be missing one of the cores. This assumption seems to be true, as I tested if /proc/cpuinfo ends with an empty line on all a single; quad-core, dual-core and single core, CPU.
If you think this is too small a test case, you can add the following after the for loop.

if temp_dict:
    cpuinfo.append(temp_dict)

So if you only care about one core, your way is best. If you want to test if any CPU can, then you would want to use the above. And if you want to know if all of them can then you should change any to all in the above.


Another Conway's Game of Life in Haskell Curious what people think about this implementation of Conway's Game of Life in Haskell.

{-# LANGUAGE QuasiQuotes #-}

module Test.Conway (
  conwayCalculateAge,
  conwayStep,
  conwayMakeRandom,
  conwayMakeRandomIO,
  conwayMakeEmpty
  ) where

import           Data.Array.Repa
import           Data.Array.Repa.Stencil
import           Data.Array.Repa.Stencil.Dim2
import           Data.Functor.Identity
import           System.Random

conwayNeighborsStencil :: Stencil DIM2 Int
conwayNeighborsStencil =
  [stencil2| 1 1 1
             1 0 1
             1 1 1 |]

conwayStep :: Array U DIM2 Int -> Array U DIM2 Int
conwayStep r =
  runIdentity . computeP . szipWith rules r .            -- Apply rules
  mapStencil2 (BoundConst 0) conwayNeighborsStencil $ r -- Find # neigbors
  where
    rules 1 2 = 1 -- Alive and has two neighbours
    rules _ 3 = 1 -- Alive or dead and has three neighbours
    rules _ _ = 0 -- All others are dead

conwayMakeRandom :: RandomGen g => g -> DIM2 -> Array U DIM2 Int
conwayMakeRandom g sh =
  fromListUnboxed sh $ take (size sh) $ randomRs (0, 1) g

Naturally, conwayMakeRandom creates the initial grid and conwayStep advances the evolution a grid.

That's a nice use of stencil2 and Repa. All in all there isn't much to review, it follows a common approach on Conway's Game of Life with Repa. No type signatures are missing, but with Repa it's more or less mandatory to add them.

Well done. But the next time, consider adding all your code, conwayCalculateAge and conwayMakeEmpty were probably interesting (I suspect conwayMakeRandomIO to be the same as conwayMakeRandom but using randomRIOs = randomRs (0, 1) <$> newStdGen).


Number Division Theory I have a JavaScript function that takes in a user number (total amount placed on a betting table in denominations of 50) and returns an Array of the optimum chips (lowest # required) to form each stack.

My function works, the correct array for each value tested is output - but since this should be running on the client browser with a fast response time for smooth UI I feel like the code is not optimised.

Is there a better, more efficient (+ mathematically solid) way of computing the same output?

Any suggestions would be appreciated.

//number will be validated before running through function to make sure it has a factor of 50.

function chipStack(number) {
    var k = 0; //1k chip
    var f = 0; //500 chip
    var t = 0; //300 chip
    var o = 0; //100 chip
    var fi = 0; // 50 chip

    k = Math.floor(number / 1000);
    var number2 = number % 1000

    if (number2 === 0) {
        return [k, f, t, o, fi];
    } else {
        f = Math.floor(number2 / 500)
        var number3 = number2 % 500
    }

    if (number3 === 0) {
        return [k, f, t, o, fi];
    } else {
        t = Math.floor(number3 / 300)
        var number4 = number3 % 300
    }

    if (number4 === 0) {
        return [k, f, t, o, fi];
    } else {
        o = Math.floor(number4 / 100)
        var number5 = number4 % 100
    }

    if (number5 === 0) {
        return [k, f, t, o, fi];
    } else {
        fi = Math.floor(number5 / 50)
        var number6 = number5 % 50
    }

    if (number6 === 0) {
        return [k, f, t, o, fi];
    } else {
        return "Something isn't right " + number6;
    }
}

You could compress the code as follows. It doesn't check for early exit conditions, but since it's running on the front-end anyway, i.e. not at high volumes, the performance won't be noticeably degraded.

function chipStack(n){
    var chipValues = [1000,500,300,100,50];
    var stack = [];
    chipValues.forEach(function(e,i){
        stack.push(Math.floor(n / e));
        n -= (stack[stack.length-1] * e);
    })
    return stack;
}


Can I make a regex array to iterate through in C++? I have to check a string to various regular expressions in C++. Up to now, I've done this using something similar to this:

regex regex_a (".."); string rewrite_a = "($1/$2)";
regex regex_b (".."); string rewrite_b = "($1)";
regex regex_c (".."); string rewrite_c = "($2)";

if (regex_match(string, regex_a)) {
    cout << regex_replace(string, regex_a, rewrite_a);
} else if (regex_match(string, regex_b)) {
    cout << regex_replace(string, regex_b, rewrite_b);
} else if (regex_match(string, regex_c)) {
    cout << regex_replace(string, regex_c, rewrite_c);
}

Is this the cleanest way to do this? Isn't there a way to make a regex array and iterate through that? It would make the code much more readable.

Probably like this:

C++11:

vector< pair<regex, string> > regex_pairs = { {regex(".."), "($1/$2)"}, {regex(".."), "($1)"}, {regex(".."), "($2)"} };
for(auto pa:regex_pairs){
    cout << regex_replace(string, pa.first, pa.second);
}

C++03:

vector< pair<regex, string> > regex_pairs;
regex_pairs.push_back(make_pair(regex(".."), "($1/$2)"));
regex_pairs.push_back(make_pair(regex(".."), "($1)"));
regex_pairs.push_back(make_pair(regex(".."), "($2)"));
for(vector< pair<regex, string> >::iterator it = regex_pairs.begin();it!=regex_pairs.end(); it++){
    cout << regex_replace(string, it->first, it->second);
}


Find value that occurs in odd number of elements I am trying to solve the following exercise using Javascript:

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9

the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.

I have written the following code.

function solution(A) {
    var pop;

    if(!A.length)
        return 0;

    while(A.length){
        pop = A.shift();
        let pos = A.indexOf(pop);
        if(pos >-1){
            A.splice(pos,1);
        } else {
            return pop
        }
    }
    return pop;
}

The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).

Any explanation why it shows exponential timing (I have not used any
nested loops)?
Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?

The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:

xor of two identical numbers is zero.
xor of any number and zero is the number.
xor is commutative.
xor is associative.

example:

A = [9, 3, 9, 3, 9, 7, 9]

the solution to this example is:

  (((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9              (4)
= 9^9^9^9^3^3^7              (3)
= (9^9)^(9^9)^(3^3)^7        (3)
= 0^0^0^7                    (1)
= 7                          (2)


Loading data in controllers I am refactoring my controllers, trying to improve the way common data is loaded for the actions. Initially, I was using before_filter methods to do this but read that helper methods were preferred.

class CategoriesController < ApplicationController
  before_filter :authenticate_user!

  helper_method :category, :categories, :organisation

  # GET /categories
  def index
  end

  # GET /categories/new
  def new
  end

  # GET /categories/1/edit
  def edit
  end

  # POST /categories
  def create
    if category.save
      redirect_to(
        categories_path(oid: organisation.id),
        notice: I18n.t("category.create.success"))
    else
      render action: :new
    end
  end

  # PUT /categories/1
  def update
    if category.update_attributes(params[:category])
      redirect_to(
        categories_path(oid: organisation.id),
        notice: I18n.t("category.update.success"))
    else
      render action: :edit
    end
  end

  # DELETE /categories/1
  def destroy
    begin
      category.destroy
      redirect_to(
        categories_path(oid: organisation.id),
        notice: I18n.t("category.delete.success"))
    rescue ActiveRecord::DeleteRestrictionError
      redirect_to(
        categories_path(oid: organisation.id),
        alert: I18n.t("category.delete.failure.foreign_key"))
    end
  end

  private
  # Gets the category being operated on.
  #
  def category
    return @category unless @category.nil?

    if params[:id]
      @category = Category.find_by_id(params[:id])
    elsif params[:category]
      @category = Category.new(params[:category])
    else
      @category = Category.new({organisation_id: organisation.id})
    end
  end

  # Gets the organisation of the Category.
  #
  # If no Category exists (e.g. in the case of actions index
  # and new) there will be a querystring parameter 'oid' indicating the
  # Organisation.
  #
  def organisation
    return @organisation unless @organisation.nil?

    if params[:oid]
      @organisation = Organisation.find_by_id(params[:oid])
    elsif params[:category]
      @organisation = Organisation.find_by_id(
        params[:category][:organisation_id])
    elsif !category.nil?
      @organisation = category.organisation
    else
      @organisation = nil
    end
  end

  # Gets the existing Categories for the organisation.
  #
  def categories
    return @categories unless @categories.nil?

    if !organisation.nil?
      @categories = Category
        .where(organisation_id: organisation.id)
        .order(:name)
        .all
    else
      @categories = nil
    end
  end
end

To load data, you can see the gem Cancan. It think it can do something like you do. I find your code very clear.

Instead of this:

if !organisation.nil?

You can do this:

if organisation.present?

Instead of this:

@categories = Category
  .where(organisation_id: organisation.id)
  .order(:name)
  .all

You can do this:

organisation.categories.order(:name)

Instead of using the method find_by_id you can use just the method find.

You did a good job!


Dijkstra's algorithm in PHP This is Dijkstra's algorithm in PHP. Regarding the data structure, I use a 2-dimensional array $_distArr[m][n]=length to store it. Are there any improvements for this?

$a and $b are the start and the end node, respectively.

<?php
/**
 *  Dijkstra's algorithm in PHP by zairwolf
 *
 *  Demo: http://www.you4be.com/dijkstra_algorithm.php
 *
 *  Source: https://github.com/zairwolf/Algorithms/blob/master/dijkstra_algorithm.php
 *
 *  Author: Hai Zheng @ https://www.linkedin.com/in/zairwolf/
 *
 */

//set the distance array
$_distArr = array();
$_distArr[1][2] = 7;
$_distArr[1][3] = 9;
$_distArr[1][6] = 14;
$_distArr[2][1] = 7;
$_distArr[2][3] = 10;
$_distArr[2][4] = 15;
$_distArr[3][1] = 9;
$_distArr[3][2] = 10;
$_distArr[3][4] = 11;
$_distArr[3][6] = 2;
$_distArr[4][2] = 15;
$_distArr[4][3] = 11;
$_distArr[4][5] = 6;
$_distArr[5][4] = 6;
$_distArr[5][6] = 9;
$_distArr[6][1] = 14;
$_distArr[6][3] = 2;
$_distArr[6][5] = 9;

//the start and the end
$a = 1;
$b = 5;

//initialize the array for storing
$S = array();//the nearest path with its parent and weight
$Q = array();//the left nodes without the nearest path
foreach(array_keys($_distArr) as $val) $Q[$val] = 99999;
$Q[$a] = 0;

//start calculating
while(!empty($Q)){
    $min = array_search(min($Q), $Q);//the most min weight
    if($min == $b) break;
    foreach($_distArr[$min] as $key=>$val) if(!empty($Q[$key]) && $Q[$min] + $val < $Q[$key]) {
        $Q[$key] = $Q[$min] + $val;
        $S[$key] = array($min, $Q[$key]);
    }
    unset($Q[$min]);
}

//list the path
$path = array();
$pos = $b;
while($pos != $a){
    $path[] = $pos;
    $pos = $S[$pos][0];
}
$path[] = $a;
$path = array_reverse($path);

//print result
echo "";
echo "
From $a to $b";
echo "
The length is ".$S[$b][1];
echo "
Path is ".implode('->', $path);

This implementation is great and works well, but you should add an "escape door" when no path is found.

For instance, remove these two lines:

$_distArr[4][5] = 6;
...
$_distArr[6][5] = 9;

If you comment both lines, you enter an infinite loop.

To avoid this problem, I think you can add these lines right before the "calculating while" loop:

if (!array_key_exists($b, $S)) {
    echo "Found no way.";
    return;
}

Then you're set; no infinite loop!


K-means algorithm very slow I'm a beginner in Python but I have tried to implement K-means algorithm in python and it's working... but it's too slow... Instead of few seconds I can spend hours to finish it and I don't know why... something it's wrong... Could anyone of you give me some advice please?
Code:
import math
from random import randint
from copy import deepcopy

from chart import chart_centroids, save_image

centroid = dict(x=0, y=0, points_x=[], points_y=[])

list_centroids = []
x = []
y = []
k = 0

def distance(x1, y1, x2, y2):
    x = (int(x1) - int(x2)) ** 2
    y = (int(y1) - int(y2)) ** 2
    sum = x + y
    sqr = math.sqrt(sum)
    return sqr

def generate_centroids(range_x, range_y):
    list_centroids.clear()
    k = 3
    for i in range(0, k):
        centroid["x"] = randint(1, range_x)
        centroid["y"] = randint(1, range_y)
        list_centroids.append(deepcopy(centroid))

def choose_points_for_centroids(x, y):
    for i in range(len(list_centroids)):
        list_centroids[i]["points_x"].clear()
        list_centroids[i]["points_y"].clear()

    distances = []
    for j in range(len(x)):
        for i in range(len(list_centroids)):
            dist = distance(x[j], y[j], list_centroids[i]["x"], list_centroids[i]["y"])
            distances.append(dist)

        minim = min(float(s) for s in distances)
        index = distances.index(minim)
        list_centroids[index]["points_x"].append(x[j])
        list_centroids[index]["points_y"].append(y[j])
        distances.clear()

def move_centroids():
    sum_x = 0
    sum_y = 0

    for cent in list_centroids:
        for j in range(len(cent["points_x"])):
            sum_x += cent["points_x"][j]
            sum_y += cent["points_y"][j]

        if len(cent["points_x"]) > 0 and len(cent["points_y"]) > 0:
            avg_x = sum_x / len(cent["points_x"])
            avg_y = sum_y / len(cent["points_y"])
            cent["x"] = avg_x
            cent["y"] = avg_y

def run():
    generate_centroids(300, 300)
    read_file("input.txt")

    tmp_x = []
    tmp_y = []

    checkers = []

    while_end = False

    while True:
        if not while_end:
            choose_points_for_centroids(x, y)
            move_centroids()

            for cent in list_centroids:
                tmp_x.append(cent["x"])
                tmp_y.append(cent["y"])

            choose_points_for_centroids(x, y)
            move_centroids()

            for i in range(len(list_centroids)):
                if tmp_x[i] == list_centroids[i]["x"] and tmp_y[i] == list_centroids[i]["y"]:
                    checkers.append(True)
                else:
                    checkers.append(False)

            for checker in checkers:
                if not checker:
                    tmp_x.clear()
                    tmp_y.clear()
                    break
                else:
                    while_end = True
        else:
            break

        for i in range(len(list_centroids)):
            chart_centroids(list_centroids[i], i)
        save_image()

def read_file(name):
    lines = [line.rstrip('\n') for line in open('../generate_file/' + name)]

    global x
    global y
    zone = []

    for index in range(5):
        x.append(int(lines[index].split()[0]))
        y.append(int(lines[index].split()[1]))
        zone.append(int(lines[index].split()[2]))

run()

The input file it's looks something like...
100 52 2
440 100 3
10 200 1
...

Note: The code works in both Python 2 and Python 3.

I see a lot of little things slowing you down, but I don't know what your chart_centroids and save_image functions do, so I have no idea if they are part of the problem or not.

Let's look at one of your two frequently-called functions:

def choose_points_for_centroids(x, y):
    for i in range(len(list_centroids)):
        list_centroids[i]["points_x"].clear()
        list_centroids[i]["points_y"].clear()

    distances = []
    for j in range(len(x)):
        for i in range(len(list_centroids)):
            dist = distance(x[j], y[j], list_centroids[i]["x"], list_centroids[i]["y"])
            distances.append(dist)

        minim = min(float(s) for s in distances)
        index = distances.index(minim)
        list_centroids[index]["points_x"].append(x[j])
        list_centroids[index]["points_y"].append(y[j])
        distances.clear()

In the first paragraph, you "clear" a bunch of data. But I'm not sure why you have your centroids structured this way. Every time you access something, there's an index, a key lookup, and maybe another index. That's way too much work for getting at something you'll be addressing frequently!

In fact, the whole idea of accessing list_centroids[i]["x"] and list_centroids[i]["y"] is kind of silly. I don't see any value to separating the x and y coordinates, here.

On the other hand, if you were to combine your x and y coordinates into a tuple, you would have a constant object that can be hashed. And hashed items can be stored in a dictionary.

Centroid = { ... }

for c in Centroid:
    Centroid[c] = []    # Reset list of points to empty

In the next section, you iterate over all your points (here you go again, segregating ordinates from abscissas!) computing a distance metric. You store the distances in a list.

After creating the distances list, you then find the min value.

After finding the min value, you then try to map back to the index of that value.

After finding the index, you use that to figure out what centroid was closest to the point, and tie the point to the centroid.

You overlook the min function's key= argument. The key is a function (or lambda-expression) that returns a value. Given the input, the min function determines what to compare by calling the key function. If the key function is not provided, then a simple identity function ( f(x) = x ) is used.

In your case, you can replace all that code by judicious use of a lambda-expression:

# This should be your global Point store, not x[] and y[]
Points = [ (_x, _y) for _x, _y in zip(x,y) ]

for p in Points:
    x,y = p
    nearoid = min(Centroid, key=lambda c: distance(x,c[0],y,c[1]))
    Centroid[nearoid].append(p)

And if you recode your distance function to take tuples, you don't need to do even that much work:

for p in Points:
    nearoid = min(Centroid, key=lambda c: distance(p, c))
    Centroid[nearoid].append(p)

This does three things for you. First, it eliminates a lot of bytecode. And that means it eliminates a lot of things that the computer was doing, which should save you time.

Second, it converts some bytecode into builtins. Using the builtins as much as possible means that your code might be running in C, instead of bytecode. This makes for better performance.

Third, it eliminates extra data structures. Which eliminates allocation, deallocation, garbage collection, data structure maintenance, etc. All that storage translates into performance, either directly (thrashing) or indirectly (code).

Now, speaking of your distance function, I see you are calling int a bunch of times. But the inputs are, if I understand correctly, already integers. So those are a bunch of name lookups, and function calls, that are entirely redundant.

Try something like this, again using the points-as-tuples approach:

def distance(a, b, sqrt=math.sqrt):
    """Return the distance between (x,y) tuples a and b"""
    return sqrt( (a[0] - b[0])**2 + (a[1] - b[1])**2)

(Putting the lookup of math.sqrt into the constants table is a bit of a cheat. But anything for speed, eh?)


Cash Register Challenge Challenge: Design a cash register program

Specifications: Your register currently has the following bills/coins within it:

  'PENNY': .01,

  'NICKEL': .05,

  'DIME': .10,

  'QUARTER': .25,

  'HALF DOLLAR': .50,

  'ONE': 1.00,

  'TWO': 2.00,

  'FIVE': 5.00,

  'TEN': 10.00,

  'TWENTY': 20.00,

  'FIFTY': 50.00,

  'ONE HUNDRED': 100.00

  Your program should accept as its first argument a path to a filename.
  The input file contains several lines. Each line is one test case.
  Each line contains two numbers which are separated by a semicolon.
  The first is the Purchase price (PP) and the second is the cash(CH).

  For each set of input produce a single line of output,
  which is the cashBack to be returned to the customer.
  In case the CH < PP, print out ERROR. If CH == PP, print out ZERO.
  For all other cases print the amount that needs to be returned,
  in terms of the currency values provided.
  The output should be sorted in highest-to-lowest order

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class CashRegister {
    public static void main(String[] args) throws FileNotFoundException {
        File file = new File(args[0]);
        Scanner fileInput = new Scanner(file);

        while (fileInput.hasNextLine()) {
            printCashChange(fileInput.nextLine());
        }
    }

    private static void printCashChange(String line) {
        float pp = Float.parseFloat(line.split(";")[0]);
        float ch = Float.parseFloat(line.split(";")[1]);

        System.out.println(getCashChange(pp, ch));
    }

    private static String getCashChange(float price, float cash) {
        if (cash < price) { return "ERROR"; }
        if (cash == price) { return "ZERO"; }
        float cashBack = cash - price;

        StringBuilder change = new StringBuilder();

        while (cashBack > 0.01f) {
            if (cashBack >= 100.0f) {
                change.append("ONE HUNDRED");
                cashBack -= 100.0f;
            } else if (cashBack >= 50.0f) {
                change.append("FIFTY");
                cashBack -= 50.0f;
            } else if (cashBack >= 20.0f) {
                change.append("TWENTY");
                cashBack -= 20.0f;
            } else if (cashBack >= 10.0f) {
                change.append("TEN");
                cashBack -= 10.0f;
            } else if (cashBack >= 5.0f) {
                change.append("FIVE");
                cashBack -= 5.0f;
            } else if (cashBack >= 2.0f) {
                change.append("TWO");
                cashBack -= 2.0f;
            } else if (cashBack >= 1.0f) {
                change.append("ONE");
                cashBack -= 1.0f;
            } else if (cashBack >= 0.5f) {
                change.append("HALF DOLLAR");
                cashBack -= 0.5f;
            } else if (cashBack >= 0.25f) {
                change.append("QUARTER");
                cashBack -= 0.25f;
            } else if (cashBack >= 0.1f) {
                change.append("DIME");
                cashBack -= 0.1f;
            } else if (cashBack >= 0.05f) {
                change.append("NICKEL");
                cashBack -= 0.05f;
            } else {
                change.append("PENNY");
                cashBack -= 0.01f;
            }
            change.append(",");
        }
        change.setLength(change.length() - 1);

        return change.toString();
    }
}

Every now and then one creates a solution that works but really comes off as sub-optimal, this is one of those times for this CRer. It really seems verbose, I'd appreciate any tips on improving performance and general structure.

For convenience, even though the challenge doesn't specify it, I suggest optionally taking input from System.in.  It's more reasonable behaviour than crashing with an ArrayIndexOutOfBoundsException.

Scanner input = (args.length > 0) ? new Scanner(new File(args[0]))
                                  : new Scanner(System.in);

In printCashChange(), avoid two calls to split().

String[] fields = line.split(";", 2);
float pp = Float.parseFloat(fields[0]);
float ch = Float.parseFloat(fields[1]);

The loop in getCashChange() should be data-driven, like this:

for (Denomination d : Denomination.values()) {
    while (cashBack >= d.getValue()) {
        cashBack -= d.getValue();
        change.append(d).append(',');
    }
}

Here's an enum to support that:

public enum Denomination {
    ONE_HUNDRED(100.00f),
          FIFTY( 50.00f),
         TWENTY( 20.00f),
            TEN( 10.00f),
           FIVE(  5.00f),
            TWO(  2.00f),
            ONE(  1.00f),
    HALF_DOLLAR(  0.50f),
        QUARTER(  0.25f),
           DIME(  0.10f),
         NICKEL(  0.05f),
          PENNY(  0.01f);

    private final float value;
    private final String description;

    Denomination(float value) {
        this.value = value;
        this.description = this.name().replace("_", " ");
    }

    public float getValue() {
        return this.value;
    }

    @Override
    public String toString() {
        return this.description;
    }
}

The performance of your program will be fine.  You aren't doing anything particularly inefficient, and the bottleneck will be I/O rather than processing.


Representation of the formula P(n) = (n!)(6^n) in C I'm trying to represent the following mathematical expression in C:

$$P(n)=(n!)(6^n)$$

The first program should compute the answer to expression when n = 20. I have attempted to create the program in C and it produces the correct answer (when compared with wolfram alpha's answer). The answer is approximately \$10^{34}\$.

Is there any way that I could improve the code?:

#include <math.h>
typedef unsigned int uint;

void main()
{
    uint n=20;
    double F=1,pwr,P;

    pwr=pow(6,n);

    while(n>0){
        F=F*n;
        n=n-1;
    }
    P=F*pwr;
}

Because the result is on the order of \$10^{34}\$, as you have correctly noted, even a double will not be able to accurately represent all digits of such a large result.  We know this because it would take
$$\frac{34}{\log_{10}2} \approx 113 \text{ bits}$$
to represent such a result, and a double isn't that large on any architecture you're likely to be using.

This then requires that we resort to multiple precision math.  Just as with multiple-digit multiplication you learned when you were very young, multiple-precision multiplication is the same principle: multiply digit by digit, adding the carry from the previous result.  In this sample code, rather than having a "digit" be 10, I've chosen 1000 which results in fewer math operations.

// calculate P(n) = (n!)(6^n)
#include <stdio.h>

typedef unsigned int uint;

const uint OVERFLOWVALUE = 1000;

void multiply(uint *a, unsigned adigits, uint b)
{
    uint carry = 0;
    for ( ; adigits; --adigits, ++a) {
        *a = *a * b + carry;
        if (*a >= OVERFLOWVALUE) {
            carry = *a / OVERFLOWVALUE;
            *a = *a % OVERFLOWVALUE;
        } else {
            carry = 0;
        }
    }
}

void print(uint *P, unsigned digits)
{
    // print results
    for (unsigned i = digits; i; --i)
        printf("%3.3u ", P[i-1]);
    putchar('\n');
}

int main()
{
    const unsigned digits = 12;
    uint P[digits];
    // initialize P
    for (unsigned i = 0; i < digits; ++i)
        P[i] = 0;

    uint n=20;

    printf("{n!*n^6, n=%u} = ", n);
    for (P[0] = 1; n; --n) {
        multiply(P, digits, n*6);
    }
    print(P, digits);
}

The result on this machine:

{n!*n^6, n=20} = 008 895 075 211 041 185 783 708 532 080 640 000

This agrees precisely with the Wolfram Alpha result.

More mathematical explanation

The multiply routine multiplies a multiple-precision result pointed to by a with adigits values by single value b.  It does not check for mathematical overflow in its calculations, so we need to be careful about the range.

For calculation purpose, suppose that a uint type has 32 bits.  If we assume that a is well-formed before the calculation, how big can b be without risking numerical overflow?  In this case, the largest number that can be in any "digit" is 1000, so overflow will happen whenever \$b * 1000 > 2^{32}\$.  This implies that to avoid overflow, $$b < \frac{2^{32}}{1000}$$ $$b <= 4294967$$.  With this maximum possible value, the carry value would be 4294, which is greater than 1000, so to be pedantic, the code should actually check each digit before each multiplication to normalize the value.

Without this precaution, however, the calculation is still free from overflow as long as \$(999+6n)6n < 2^{32}\$.  This is a simple quadratic equation, with the largest positive root being just over 10839, so as long as \$n<10839\$ this code will work correctly as is.