Markov chain text generation in Python I'm willing to listen to any advice you have for improving it.

from collections import defaultdict

import nltk
import numpy as np

seq, freq, sample = [t for ts in [[None] + nltk.casual_tokenize(line) + [None] for line in open("file.txt").readlines()] for t in ts], defaultdict(lambda: defaultdict(int)), lambda curr: np.random.choice(list(freq[curr].keys()), p=[x/sum(freq[curr].values()) for x in freq[curr].values()])
for a, b in zip(seq[:-1], seq[1:]): freq[a][b] += 0 if a is None and b is None else 1
curr = sample(None)
while curr != None: _, curr = print(curr, end=" "), sample(curr)

Holy incomprehensible comprehensions!

There is no good justification for defining seq, freq, and sample all as one statement.  Each of them is already complex enough on its own.

There is also no good reason to write your last while loop as a one-liner.

With just those changes and some indentation…

from collections import defaultdict

import nltk
import numpy as np

seq = [
    t for ts in [
        [None] + nltk.casual_tokenize(line) + [None]
        for line in open("file.txt").readlines()
    ]
    for t in ts
]
freq = defaultdict(lambda: defaultdict(int))
sample = lambda curr: np.random.choice(
    list(freq[curr].keys()),
    p=[x / sum(freq[curr].values()) for x in freq[curr].values()]
)
for a, b in zip(seq[:-1], seq[1:]):
    freq[a][b] += 0 if a is None and b is None else 1
curr = sample(None)
while curr != None:
    print(curr, end=" ")
    curr = sample(curr)

… we might start to hope to understand the code.

What's [t for ts in [[…]] for t in ts]?  It's just flattening a list of lists.  I'd write that as list(itertools.chain(*[[…]])).

with open("file.txt") as f:
    seq = list(itertools.chain(*[
        [None] + nltk.casual_tokenize(line) + [None]
        for line in f
    ]))

However, once you flatten it, you get …, None, None, … as placeholders for the linebreaks.  You later have to do extra work to filter out if a is None and b is None when constructing the freq matrix.  So why even bother creating seq as a flattened list in the first place, if all you want is a frequency matrix?

from collections import Counter

def frequency_table(file):
    freq = defaultdict(Counter)
    for line in file:
        tokens = nltk.casual_tokenize(line)
        for a, b in zip(tokens + [None], [None] + tokens):
            freq[a][b] += 1
    return freq

sample would be clearer if written as a function.  I'd make it take a freq parameter instead of using freq as a global.

def sample(freq, curr):
    return np.random.choice(
        list(freq[curr].keys()),
        p=[x / sum(freq[curr].values()) for x in freq[curr].values()]
    )

I don't know if performance is an issue here, but you might be better off normalizing the probabilities instead of recalculating [x / sum(freq[curr].values()) for x in freq[curr].values()] with each call to sample().

It would be nice to convert your final loop into a generator:

def markov_chain(freq, word=None):
    while True:
        word = sample(freq, word)
        if word is None:
            break
        yield word

With those three function definitions in place, the rest of the code looks pretty straightforward:

with open("file.txt") as f:
    freq = frequency_table(f)
for word in markov_chain(freq):
    print(word, end=" ")


Remove a key from list of hashes Suppose my milestone is this:

milestones = [ {state: 'unavailable'}, {state: 'arrived'}, {state: 'completed'} ]

I want to remove all the unavailable state from the list of hashes except the last one. My function works pretty well but I need some help to re factor it even further, and will appreciate any comments you can give. Here my code:

def filter_milestones(milestones)
      track_unavailable = Set.new
      filtered_milestones = []
      total_length = milestones.length
      if total_length == 1
        filtered_milestones = milestones
      else
        milestones.each_with_index do |value, index|
          if value[:state] == 'unavailable' && index != total_length - 1
            track_unavailable.add index
          end
        end
        milestones.each_with_index do |value, index|
          unless track_unavailable.include? index
            filtered_milestones << value
          end
        end
      end
      filtered_milestones
    end

So if my input milestone is [ {state: 'unavailable'}, {state: 'arrived'}, {state: 'completed'} ] then the return will be [ {state: 'arrived'}, {state: 'completed'} ].

Your solution looks overly complex. If I understood it correctly, you want to filter out all unavailable states except if it's the last element. A more declarative and idiomatic Ruby approach would be:

filtered_milestones = milestones.reject.with_index do |milestone, idx|
  is_last_milestone = (idx == milestones.size - 1)
  milestone[:state] == "unavailable" && !is_last_milestone
end


Generate a dictionary of passwords I have a Python script that generates a dictionary of all possible 3 digit password combinations. It essentially works by just nesting for loops. This is fine, but say I wanted to change it so it could generate 4, 5, 6, ... digit combinations. This would require me to keep adding more nested loops and changing the print statement.

How can I make my current code more efficient and apply the DRY principle? This way, if I wanted to change it to generate 4-digit codes, I could simply change a single variable rather then add an entire for loop.

Current code:

f=open('New Text Document.txt','w')
def getCombos(digits, caps, numbers):
    if(caps == True):
        if(numbers == True):
            for x in range(33, 126):
               for y in range(33, 126):
                   for z in range(33, 126):
                       print(chr(x) + "" + chr(y) + "" + chr(z))
                       f.write(chr(x) + "" + chr(y) + "" + chr(z) + "\n")

getCombos(3, True, True)

If I wanted to add a fourth digit:

f=open('New Text Document.txt','w')
def getCombos(digits, caps, numbers):
    if(caps == True):
        if(numbers == True):
            for x in range(33, 126):
               for y in range(33, 126):
                   for z in range(33, 126):
                       for m in range(33, 126):
                       print(chr(x) + "" + chr(y) + "" + chr(z) + "" + char(m))

getCombos(3, True, True)

Please take a look at itertools.product. It will simplify your code greatly.

def getCombos(digits, caps, numbers):
    # Build set of choices appropriately based on caps and numbers
    choices = list(range(33, 126))
    for vals in itertools.product(choices, repeat=digits):
        print ''.join(map(chr, vals))

getCombos(3, True, True)


Authentication system using AJAX I'm building an authentication system using a combination of PHP, MySQL, jQuery, and AJAX. The way I'm doing it right now is I have a form that takes in a username and password. When the user clicks on the login button I pass the value of those two values along with an action to a controller file. That controller file will use an Authentication object (I wrote my own Authentication class) to determine if the user is authenticated or not. If so, it will return a string that says "authenticated" or something similar. I check for that value in the response of the AJAX request and go from there based on the response. Of course I do all sorts of server side checks so someone can't just navigate to a certain section or tamper with my jQuery to trick the system. It's all enforced behind the scenes.

Is this acceptable? Is there any major problem with doing this the way I am? Here are some snippets of my code that is responsible for handling all this:

Login section:

        <input id="username" type="text" placeholder="Username" />
        <input id="password" type="password" placeholder="Password" />

        Login

jQuery:

$(document).on("click", "#loginButton", function() {
var user = $("#username").val();
var pass = $("#password").val();

    $.post("controllers/auth.php", {"action": "authenticate", "user": user, "pass": pass}, function(data) {
        if(data == "authenticated") {
            //stuff
        }
    });
});

Controller:

if(isset($_POST['action']) && $_POST['action'] == "authenticate") {
    $credentials = array("user" => $_POST['user'], "pass" => $_POST['pass']);
    $auth = new Auth($dbh, $ldaps, $credentials);
    if($auth->authenticate()) {
        echo "authenticated";
    }
}

Do all URLs on your site use SSL? If not you'll need to setup your site to at least support the authenticate URL over HTTPS.
Currently your passing a plain text Username and Password - anyone can grab them.

On requests after the login, how are you determining whether or not the user is authenticated?
It does not look like you are persisting the login in any way, unless Auth class is doing it behind the scenes.  Typically this is done with a session variable or cookie.


Depth First Search (Adjacency List) in JavaScript I am trying to implement a DFS search and graphs. How can I make it better?

/**
 * Depth First Search iterative implementation
 * @param: graph to traverse and the starting node
 * @return
 */
let DfsSearch = function(graph,startNode){
        let stack =  [];
        stack.push(startNode);

        while(stack.length >0){
            let node = stack.pop();
             console.log('visiting node',graph[node].value);
            if(graph[node].isVisited == false){

               graph[node].isVisited = true;
                for(currentNode in graph[node].edges){
                    stack.push(graph[currentNode].value);
                }
            }

        }

}

module.exports = DfsSearch;

const  DFSSearch= require('./DFS');
/**
 * @description: outputs a new graph , in form of adjancency list
 * inspired from https://medium.freecodecamp.com/a-gentle-introduction-to-data-structures-how-graphs-work-a223d9ef8837#.4voil9gg6
 */
let makeGraphs = () => {
    let graph = {};

    //add vertex
    graph.addVertex = (node) => {
        graph[node] = { edges: {} };
        graph[node].isVisited = false;
        graph[node].value = node;
    }
    //addedges
    graph.addEdge = (startNode, endNode) => {
        if (graph.contains(startNode) && graph.contains(endNode)) {

            graph[startNode].edges[endNode] = true;
            graph[endNode].edges[startNode] = true;
        }
    }

    //check if it contains the node
    graph.contains = (node) => {
        if (graph[node]) {
            return true;
        }
        else {
            return false;
        }
    }
    graph.removeEdge = (startNode, endNode) => {
        if (graph.contains(startNode) && graph.contains(endNode)) {
            delete graph[startNode].edges[endNode];
            delete graph[endNode].edges[startNode];
        }
    }
    graph.removeVertex = (node) => {
        if (graph.contains(node)) {
            for (connectedNodes in graph[node].edges) {
                graph.removeEdge(node,connectedNodes);
            }
        }
        delete graph[node];
    }
return graph;
}

let dfsGraph = makeGraphs();
dfsGraph.addVertex(1);
dfsGraph.addVertex(2);
dfsGraph.addVertex(3);
dfsGraph.addVertex(4);
dfsGraph.addVertex(5);
dfsGraph.addEdge(1,2);
dfsGraph.addEdge(1,3);
dfsGraph.addEdge(2,4);
dfsGraph.addEdge(2,5)
DFSSearch(dfsGraph,1);
module.exports= makeGraphs();

Use object literals

Your code currently refers to the graph object about 15 times. This is unnecessary, as the graph object is simply the eventual output of makeGraphs.

So, instead of creating the empty object graph and adding properties and methods later, you can use a single object literal declaration. Using an object literal allows you to abbreviate initialization of object properties and functions.

Where you have:

    let graph = {};

Replace with:

    return {

Then, all subsequent references to graph can then be removed altogether, or, in rare cases where required, replaced with this. Object literals also clean up the look of your other objects, such as edges and nodes.

For example, your addVertex function would look like this:

    addVertex(node) {
        this[node] = {
            edges: {},
            isVisited: false,
            value: node,
        }
    }

(Note: The arrow operator is not needed because the scope is determined by the object container.)

Handle creating edges / vertices from an array:

The part at the bottom shows how cumbersome it is to add edges and vertices one-by-one. The user would either have to write a loop or a container function. Instead, addEdge and addVertex could be easily modified to take array input. For example:

    addVertex(nodes) {
        for (var node in nodes) {
            this[node]: {
                edges: {},
                isVisited: false,
                value: node,
            }
        }
    }

Then, to add vertices using addVertex:

dfsGraph.addVertex([1,2,3,4,5])


Improving many for loops, any more efficient alternative? I'm working through an introduction to computer science book, this is not homework for me but me trying to learn in my spare time, I'm not asking for homework help!

The output is below, and this is all ok, but I'm just certain there is a more efficient way of doing this. I have been trying for many hours now and this is still the best solution I can come up with, if anyone can improve upon this and possibly explain how, I would highly appreciate it.

The code:

naught = 0
one = 0
two = 0
three = 0
four = 0
five = 0
six = 0
seven = 0
eight = 0
nine = 0

for i in range (0, 10):
    print("")
    for i in range (0,1):
        print(naught, end = " ")
    for i in range (0,1):
        print(one, end = " ")
        one += 1
    for i in range (0,1):
        print(two, end = " ")
        two += 2
    for i in range (0,1):
        print(three, end = " ")
        three += 3
    for i in range (0,1):
        print(four, end = " ")
        four += 4
    for i in range (0,1):
        print(five, end = " ")
        five += 5
    for i in range (0,1):
        print(six, end = " ")
        six += 6
    for i in range (0,1):
        print(seven, end = " ")
        seven += 7
    for i in range (0,1):
        print(eight, end = " ")
        eight += 8
    for i in range (0,1):
        print(nine, end = " ")
        nine += 9

The output is below and that is all correct, that's no problem.

0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18
0 3 6 9 12 15 18 21 24 27
0 4 8 12 16 20 24 28 32 36
0 5 10 15 20 25 30 35 40 45
0 6 12 18 24 30 36 42 48 54
0 7 14 21 28 35 42 49 56 63
0 8 16 24 32 40 48 56 64 72
0 9 18 27 36 45 54 63 72 81

As I said I'm getting the right answer, just I'm not satisfied that it's in the best way.
Many thanks,
Matt.

for i in range(10):
    for j in range(10):
        print i*j,
    print ""

Something like this, perhaps?


Sum of even Fibonacci numbers So, in my first attempt I created a code that generated all fibonacci numbers and appended to a list. This list I then traversed to get the even numbers and added them up. It worked, but took like 5 complete seconds to work.
Then I decided to not create a list and add the even numbers as I'm generating them. It looked like this

a = 1
b = 1
c = 0
Sum = 0
while c<4000000:
    c = a + b
    if c%2==0:
        Sum+=c
    a = b
    b = c
print Sum

It still took quite a lot of time (didn't record it) compared to the people who got it done in like 100 milliseconds or something (I got this question on Project Euler).
Is there a way to make it faster?
Here's the link to the problem

https://projecteuler.net/problem=2

Obviously, every third Fibonacci number is even, and the rest of them are odd. Less obviously (but trivially follows from, say, Binet's formula), they satisfy another linear recurrence:

\$F_{3(n+1)} = 4 F_{3n} + F_{3(n-1)}\$

Using this fact, you may cut the execution time threefold.


clean approach to decorator that takes optional keyword arguments I write decorators a lot in my work. Sometimes you need to write "decorator that takes arguments", it usually turns out to be something like this:

def decorator(**kwargs):

    def _decorator(func):

        @wraps(func)
        def decorated(*func_args, **func_kwargs):
            # do something with kwargs here
            return func(*func_args, **func_kwargs)

        return decorated

    return _decorator

but in this case you'll always have to use your decorator like so:

@decorator()  # if you forget () here you'll get an exception
def myfunc():
    pass

So I come up with this snippet, IMO this is nicer to read/write and understand:

from functools import wraps, partial

def decorator(func=None, **kwargs):
    if func:

        @wraps(func)
        def decorated(*func_args, **func_kwargs):

            if kwargs.get("sayhi"):
                print("hi")

            return func(*func_args, **func_kwargs)

        return decorated

    else:
        return partial(decorator, **kwargs)

@decorator
def hello(name):
    print(f"hello {name}")

@decorator(sayhi=True)
def bye(name):
    print(f"bye {name}")

hello("rabbit")
# "hello rabbit"

bye("rabbit")
# hi
# bye rabbit

Nice little snippet! A couple of minor points:

It's usually better to put the shorter block first in an if else. This stops the else statement being far from the if, making it clearer how the logic flows.
When comparing to None, check if func is None or similar, rather than comparing to True/False.
Although this is just a toy example, docstrings should always be used to show what the code does and returns.
PEP8 spacing between imports, functions and code.
Argument names could be better but without knowing the application it's hard to say what they should be.

from functools import partial, wraps

def decorator(func=None, **kwargs):
    """
    Decorator which optionally takes an argument sayhi (True or False).
    prints 'hi' if True, function is then returned as normal
    """
    if func is None:
        return partial(decorator, **kwargs)
    else:
        @wraps(func)
        def decorated(*func_args, **func_kwargs):
            if kwargs.get('sayhi'):
                print('hi')
            return func(*func_args, **func_kwargs)
        return decorated


Public Function to remove empty or "" elements from a single dimension array I've written a function to remove empty or "" value elements from an array or in other words return an array consisting only of elements containing a value.

Option Explicit

Public Function RemoveBlanksFromArray(ByVal TheArray As Variant) As Variant

    Dim temp As Variant
    ReDim temp(LBound(TheArray) To LBound(TheArray))
    Dim myElement As Variant
    Dim myCount As Long
    myCount = LBound(temp)

    For Each myElement In TheArray
        If myElement <> "" Then
            ReDim Preserve temp(LBound(temp) To myCount)
            temp(myCount) = myElement
            myCount = myCount + 1
        End If
    Next myElement

    RemoveBlanksFromArray = temp

End Function

The Function is passed an Array as an argument. The Array is temp and ReDimed as a single element. It then loops each element of the passed argument and adds the value if it's not "" or Empty.

I've used ReDim Preserve temp(LBound(temp) To myCount) before each element is written to temp to dynamically set the upper bound.

I feel there may be more efficient ways to perform this task.

Are there any inefficiencies in ReDiming the upper bound the way I have done it?

Can the upper bound of the array be set in any other way dynamically?

Have I broken any sacred rules in the formatting of the function or naming conventions etc?

Option Explicit

Always nice to see.

Public Function RemoveBlanksFromArray(ByVal TheArray As Variant) As Variant

The usual convention for parameters is camelCase - i.e. theArray. Otherwise looks fine, maybe I'd call it inputArray so it's obvious to the rest of your code what it contains (more on naming).

One thing to watch out for when passing arrays byVal. Arrays are a bit like objects in VBA -you never pass actual objects around, just addresses. Similarly, byVal doesn't make a copy of the actual data in TheArray, just a copy of the pointer to the array's location in memory. With primitive types when you write something like this:

Sub Foo(ByVal bar As Long)

... only a copy of bar is passed, meaning Foo cannot do anything to alter the original variable. However in your code, you could accidentally modify the values in TheArray.

This is one reason why I'd suggest strongly typing the array - as these can only be passed ByRef; in your comparisons you treat the elements like strings:

If myElement <> "" Then

So why not explicitly declare the array as such?

Public Function RemoveBlanksFromStringArray(ByRef theArray() As String) As String()

Now the ByRef is clear, and you'll get a minor performance boost because you don't have to cast to and from Variant

Dim temp As Variant
'[...]
RemoveBlanksFromArray = temp

I tend to name variables that get assigned to the return value of a function result, just personal preference.

ReDim temp(LBound(TheArray) To LBound(TheArray))

Glad to see you've explicitly referenced both bounds, avoiding Option Base 1 or any convention (hint, there isn't one)

Dim myCount As Long

I think this name is misleading. It's not a count really is it, because depending on LBound(TheArray) it might start at 0 or 1 or 7 for all we know. You could name it something like indexOfTempArray, but I think a count is actually more useful and intuitive, so we'll make it one, but maybe more explicit:

Dim countOfNonBlanks As Long

For Each myElement In TheArray

Now there's a small optimisation to be made here; it's marginally quicker to loop over an array by index than with For-Each, so this becomes

Dim index As Long
For index = LBound(TheArray) to UBound(TheArray)
    If TheArray(index) <> "" Then
        '...

Oh and while we're here, prefer vbNullString to "" because the latter could be a non printable character or might have a space in there if you squint etc. vbNullString is unequivocal (Rubberduck would've told you that)

That all brings us to the bottle-neck of your code (I think):

ReDim Preserve temp(LBound(temp) To myCount)
temp(myCount) = myElement
myCount = myCount + 1

Your hunch is right, there's a better way. Arrays in VBA are stored as a continuous pre-allocated bit of memory. (This is why array lookups are so fast, because all you do is look up the address of the first item of the array, and offset by a fixed distance - 1 lookup operation. Collections store the address of every element of the array, so to find an element in memory, you first lookup the address associated with it, then look at that address in memory - 2 lookup operations).

However with VBA Arrays what you gain in speed you lose in flexibility. Because the memory is pre-allocated, you can't just add another element on the end, that memory may be in use for something else. So ReDim Preserve actually copies the entire array to a new (bigger) location in memory. That's slow! Here's where someone told me all that.

Anyway, what this boils down to is; imagine the largest size your temp array could ever be (i.e no blanks found, so the same size as your input array), fill it up partially, then ReDim Preserve it once back down to the actual size it has to be.

Putting all that together we get:

Public Function RemoveBlanksFromStringArray(ByRef inputArray() As String) As String()

    Dim base As Long
    base = LBound(inputArray)

    Dim result() As String
    ReDim result(base To UBound(inputArray))

    Dim countOfNonBlanks As Long
    Dim i As Long
    Dim myElement As String

    For i = base To UBound(inputArray)
        myElement = inputArray(i)
        If myElement <> vbNullString Then
            result(base + countOfNonBlanks) = myElement
            countOfNonBlanks = countOfNonBlanks + 1
        End If
    Next i
    If countOfNonBlanks = 0 Then
        ReDim result(base To base)
    Else
        ReDim Preserve result(base To base + countOfNonBlanks - 1)
    End If

    RemoveBlanksFromStringArray = result

End Function

On a test of 500,000 items

original code took 1.1481±0.0001 s,
refactored code took 0.1157±0.0001 s

or ~ 10 times faster

Addendum

Now I think about it, the original code with copying memory boils down to an \$\mathcal O (n^2)\$ algorithm, the refactored code is \$\mathcal O (n)\$ (here \$ n\$ is the size of the array, \$\mathcal O (n^a)\$ basically means you loop over the array \$ a\$ times). Using Timer for some rough results, you can see this trend:

10,000 elements
  Old 0
  New 0
100,000 elements
  Old 0.046875 (same order of magnitude as each other)
  New 0.015625
1,000,000 elements
  Old 3.171875 (1 order of magnitude slower relative to New)
  New 0.125
10,000,000 elements
  Old 321.46875 (2 orders of magnitude slower)
  New 1.3125

I.e. When you do 10x more elements, OP's O(n^2) code gets 10^2 = 100 times slower, the refactored O(n) gets 10^1 = 10 times slower. Therefore relative to the new code, the old code gets 10x slower.

Interestingly, because both algorithms are doing essentially the same operation (writing to memory), which is an O(1) operation (i.e. independent of the rest of the code), once you operate on large enough arrays, optimising the rest of the code becomes inconsequential (Early vs Late binding, For Each vs Index, re-using LBound vs re-measuring). So once you get the algorithm down to the lowest complexity possible (assuming performance is an issue), then pick whichever method is most readable and maintainable.


Turning a byte array into a C# object whose type is unknown at compile time I'm trying to turn an array of bytes into a C# object. I only the know the type of the object at runtime.

Right now, I'm using the JsonConvert.DeserializeObject<T> to do this, but the result is clunky, mostly because I don't know T at compile time.

If I knew T at compile time, I could simply do:

string json = System.Text.Encoding.UTF8.GetString(buffer);
return JsonConvert.DeserializeObject<MyType>(json);

But since I don't, I must do:

string json = System.Text.Encoding.UTF8.GetString(buffer);
var deserializeInfoMethodInfo = typeof(JsonConvert).GetMethods().Where(method => method.Name == "DeserializeObject" && method.IsGenericMethod).First();
return deserializeInfoMethodInfo.MakeGenericMethod(paramInfo.ParameterType).Invoke(null, new object[] { json });

Is there a way to make this simpler?

I have experimented with something like this:

using (MemoryStream stream = new MemoryStream(buffer, bufferIndex, paramLengths[i])) {
    using (JsonTextReader jsonReader = new JsonTextReader(new StreamReader(stream))) {
        var serializer = new JsonSerializer();
        return serializer.Deserialize(jsonReader, paramInfo.ParameterType);
    }
}

This is arguably more readable, but I don't like how I have to get the buffer (which I got from calling stream.Read(buffer, 0, length) in another place), turn it back into a stream, and then have the serializer iterate through the stream again.

Is there a way to trim down the second snippet, or should I stop whining and use the third?

I think, it can be simplified just a little bit:

static object Deserialize(byte[] buffer, Type type)
{
  using (StreamReader sr = new StreamReader(new MemoryStream(buffer)))
  {
    return JsonConvert.DeserializeObject(sr.ReadToEnd(), type);
  }
}

NB: StreamReader releases/disposes MemoryStream, so you don't have to encapsulate that in a using()

Or You could even do:

static object Deserialize(byte[] buffer, Type type)
{
  return JsonConvert.DeserializeObject(System.Text.Encoding.UTF8.GetString(buffer), type);
}

or:

static object Deserialize(byte[] buffer, Type type)
{
  return JToken.Parse(Encoding.UTF8.GetString(buffer)).ToObject(type);
}


Project Euler # 62 Cubic permutations in Python The cube, 41063625 (\$345^3\$), can be permuted to produce two other cubes: 56623104 (\$384^3\$) and 66430125 (\$405^3\$).
In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

from collections import Counter
from time import perf_counter

def get_cube_permutations(upper_bound, number_of_permutations):
    """Return minimum cube that has number_of_permutations permutations as cubes."""
    cubes = [str(number ** 3) for number in range(1, upper_bound)]
    sorted_cubes = [''.join(sorted(cube)) for cube in cubes]
    count = Counter()
    for sorted_cube in sorted_cubes:
        count[sorted_cube] += 1
    for sorted_cube, number_of_occurrences in count.items():
        if number_of_occurrences == number_of_permutations:
            return cubes[sorted_cubes.index(sorted_cube)]
    return 0

if __name__ == '__main__':
    START_TIME = perf_counter()
    UPPER_BOUND = 10 ** 4
    TARGET_PERMUTATIONS = 5
    MINIMUM_CUBE = get_cube_permutations(UPPER_BOUND, TARGET_PERMUTATIONS)
    if MINIMUM_CUBE:
        print(f'Minimum cube that has {TARGET_PERMUTATIONS} permutations of its digits as cubes: {MINIMUM_CUBE}.')
    else:
        print(f'No cube found that has {TARGET_PERMUTATIONS} of its digits for numbers within range {UPPER_BOUND}.')
    print(f'Time: {perf_counter() - START_TIME} seconds.')

Several issues with your code:

You are storing too much data.
Inefficient usage of Counter()
Is Counter() ordered?
You are needing to guess at upper bounds to the solution
Your timing code is flawed.

Storing too much data

You store the cubes of 1 to \$10^4\$:

cubes = [str(number ** 3) for number in range(1, upper_bound)]

This is then used once as input to computing sorted_cubes, and then once to look up the value at a single index.

When you get an index value from sorted.cubes.index(sorted_cube), say 1000, you look up the value of cubes[1000].  The value at that location will be the string representation of the cube of the 1000th value, which by looking at the range() limits, we can conclude is the \$1001^3\$.

So, you could instead:

return (sorted_cubes.index(sorted_cube) + 1) ** 3

Now that we've removed that pesky final lookup, cubes is only used once in the computation of sorted_cubes, so you can eliminate it entirely.

sorted_cubes = [''.join(sorted(str(number ** 3))) for number in range(1, upper_bound)]

Memory usage has been cut in half.

Inefficient usage of Counter()

As mentioned by @Tweakimp in their answer , you're using Counter() poorly:

count = Counter()
for sorted_cube in sorted_cubes:
    count[sorted_cube] += 1

can be written as:

count = Counter(sorted_cubes)

Is Counter() ordered?

Counter is a dict subclass, and as such on Python 3.6+, it maintains insertion order of the keys.  But in earlier versions, the contents is unordered.

This means, if two or more sets of cubic permutations of the required size are found, in Python 3.6+, the first cube added to the dictionary will be returned first in count.items(), and the correct sorted_cube will be used.  This cannot be relied upon in prior versions of Python.

Guessing at the upper bounds

Where do you need to stop searching for 5 permutations?  How about for 13 permutations?  How about 20?  Where did UPPER_BOUND = 10 ** 4 come from?  Did you just keep increasing it until it worked?

You know there is an answer, so why not keep searching until one is found?  Start at 1 digit cubes, and look for the required number of permutations.  Then try 2 digit cubes, then 3 digit cubes, until an answer is found.  The search space for each would be: \$\sqrt[3]{10^{n}} \le x \lt \sqrt[3]{10^{n+1}}\$, where n is the number of digits in the cube.

Your timing code is flawed.

This code:

START_TIME = perf_counter()
MINIMUM_CUBE = ...
print(f"... {MINIMUM_CUBE} ...")
print(f'Time: {perf_counter() - START_TIME} seconds.')

produces different results on my computer depending on whether the cursor is at the top of a blank terminal window, or at the bottom long scroll of previous text.  Avoid, as much as possible, including printing in timing results.

START_TIME = perf_counter()
MINIMUM_CUBE = ...
END_TIME = perf_counter()
print(f"... {MINIMUM_CUBE} ...")
print(f'Time: {END_TIME - START_TIME} seconds.')

Better implementation

Python 3.6+ only:

def cubic_permutations(required_permutations):
     min_cube = 1
     third = 1/3

     while True:
         max_cube = min_cube * 10 - 1
         lo = int(min_cube ** third)
         hi = int(max_cube ** third)

         cubes = [ "".join(sorted(str(x**3))) for x in range(lo, hi+1) ]
         count = Counter(cubes)
         digits = next((digits for digits, n in count.items()
                        if n == required_permutations), None)

         if digits:
             root = cubes.index(digits) + lo
             return root ** 3

         min_cube *= 10

This code runs over 5 times faster than @Tweakimp's code for their 13 permutation code.  No artificial upper bound is required.  Memory usage is further reduced, since smaller subsets (from lo to hi) of cubes and count are in memory at once.


Automatically select the table rows between two selected rows The code is to check the rows in a table. If in a table two non consecutive rows are checked then all the in between rows should be selected by itself. Also, after selecting two rows, on selection of third row it should throw an error.

How can I simplify this code?

onSelectionChange: function(oEvent) {
        var aIndex = [];
        var k = 0;
        var z = 0;
        var sItem;
        var sContext;
        var vMatched;
        if (oEvent.getParameters().listItems[0].getSelected() === true) {
            if (oEvent.getParameters().selectAll === true) {
                for (var a = 0; a < this.getView().byId("monTable").getItems().length; a++) {
                    aIndex.push(a);
                }
            } else {
                for (k = 0; k < this.getView().byId("monTable").getItems().length; k++) {
                    sItem = this.getView().byId("monTable").getItems()[k].getBindingContext().sPath;
                    for (z = 0; z < this.getView().byId("monTable").getSelectedContextPaths().length; z++) {
                        sContext = this.getView().byId("monTable").getSelectedContextPaths()[z];
                        if (sItem === sContext) {
                            aIndex.push(k);
                        }
                    }
                }
            }
        } else {
            for (k = 0; k < this.getView().byId("monTable").getItems().length; k++) {
                sItem = this.getView().byId("monTable").getItems()[k].getBindingContext().sPath;
                for (z = 0; z < this.getView().byId("monTable").getSelectedContextPaths().length; z++) {
                    sContext = this.getView().byId("monTable").getSelectedContextPaths()[z];
                    if (sItem) {
                        vMatched = k;
                    }
                }
            }
            if (oEvent.getParameters().selectAll === false && this.getView().byId("monTable").getSelectedContextPaths().length === 0) {
                aIndex.splice(0, aIndex.length);
            } else {
                for (var j = 0; j < aIndex.length; j++) {
                    if (aIndex[j] === vMatched) {
                        aIndex.splice(j, 1);
                    }
                }
            }
        }
        var maxValue = aIndex[0];
        var minValue = aIndex[0];
        for (var i = 0; i < aIndex.length; i++) {
            if (aIndex[i] > maxValue) {
                maxValue = aIndex[i];
            }
            if (aIndex[i] < minValue) {
                minValue = aIndex[i];
            }
        }
        if (maxValue - minValue > 1) {
            if (aIndex.length > 2 && aIndex.length !== this.getView().byId("monTable").getItems().length) {
                for (var y = minValue; y <= maxValue; y++) {
                    if (this.getView().byId("monTable").getItems()[y].getSelected() === false) {
                        var sText = this.getOwnerComponent().getModel("i18n").getResourceBundle().getText("msgTxtgapSelection");
                        var sTitle = this.getOwnerComponent().getModel("i18n").getResourceBundle().getText("msgTitleInf");
                        this.dynamicNoneMessage(sText, sTitle);
                        //MessageBox.show("Bitte wählen Sie eine Folge ohne Lücken");
                    }

                }

            } else {
                for (var m = minValue; m <= maxValue; m++) {
                    this.getView().byId("monTable").getItems()[m].setSelected(true);

                }

            }
        }
    }`

Easiest thing you can do is properly name your variables and add comments.

Seeing things like this is very frustrating:

aIndex.push(k);
vMatched = k;

It's completely meaningless except to the developer who wrote it. It's a form of hungarian notation, except nothing is preventing you from making aIndex a String instead of an Array or vMatched and array instead of a var. (I'm assuming v is for var, which is also a hint this naming style isn't going to work here).

I'd expect for-loops to start using i not k. No need to declare it at the top either. You should always declare variables in the most local scope.

Here you're adding the numbers 0-a onto a list. You don't need to do that since you already have a. If you need to store the length at that time, you can.

for (var a = 0; a < this.getView().byId("monTable").getItems().length; a++) {
    aIndex.push(a);
}

In your nested loops it looks like you are getting the indexes that match based on a criteria. You should really do this in a method, hopefully with comments to make it easier to read. You can use lambdas expressions if you're comfortable with them. However without better context I cannot provide a concrete alternative.

You should use a method for getting the min/max amounts from an array. Methods make everything easier to read & easier to refactor.

You can use Arrays.sort() then take the first / last item of the array to get the min/max.


A function for convenient string concatenation with variadic templates I wrote this function for string concatenation some time ago.

Jo() stands for "Join". The name is shortened on purpose, because this function is used very often.

It offers a stream-like functionality: Jo("i = ", i) = cout << "i = " << i
and returns a const char * to internal buffer.

const char * is used instead of std::string because I interact with C apis a lot and writing .c_str() each time is tedious.

I know that you can achieve same result by converting arguments to std::string one by one and concatenating them instead of using this function, but it would require a lot more code.

It's intended to be used in a single thread only, thus there are no mutextes or something similar.

Here is the code:

#include <cstdio>
#include <sstream>
#include <initializer_list>

namespace Internal
{
    // In real code those are declared `extern` and initialization is moved from .h into .cpp
    std::stringstream ss;
    const std::stringstream::fmtflags stdfmt = ss.flags();
}

// Jo() resets stringstream flags before performing concatenation.
// Jo_() does not.

template <typename ...P> const char *Jo_(P &&... p)
{
    // Multiple buffers to allow use of multiple Jo()'s in a single expression.
    static constexpr int ret_buffers_c = 32;
    static std::string ret_buffers[ret_buffers_c];
    static int ret_pos = 0;

    Internal::ss.clear(); // Clear the error flags.
    Internal::ss.str(""); // Clear stringstream contents.

    // Push all objects to stringstream.
    std::initializer_list<int>{(Internal::ss << p, 0)...};

    // Save to buffer and return a pointer.
    ret_buffers[ret_pos] = Internal::ss.str();
    const char *ret = ret_buffers[ret_pos].c_str();
    ret_pos = (ret_pos + 1) % ret_buffers_c;
    return ret;
}

template <typename ...P> const char *Jo(P &&... p)
{
    Internal::ss.flags(Internal::stdfmt);
    return Jo_((P &&) p...);
}

// Example usage:
int main()
{
    for (int i = 1; i <= 10; i++)
        std::puts(Jo(i, " * ", i+1, " = ", i*i+i));
    return 0;
}

Is there anything I can improve about those functions?

I'm especially concerned about this line: std::initializer_list<int>{(Internal::ss << p, 0)...};
It looks a bit dirty, but I don't know any better alternative.

I don't like the idea in any way, but it is my personal opinion. The approach may bring up problems such as occasional buffer override if your buffer happens to be smaller than needed.

If you really don't want to write c_str() all the time you can wrap std::stringstream with some kind of proxy, that would have operator const char*() as a member function. The only problem is to get all the copies of member operator << of the stringstream. I solved it using a template.

#include <sstream>
#include <string>

class sstream_proxy
{
    std::stringstream stream;
    std::string last;
public:
    template <typename T>
    sstream_proxy& operator<<(const T& value)
    {
        stream << value;
        return *this;
    }

    operator const char*()
    {
        last = stream.str();
        stream.clear();
        stream.str("");
        return last.c_str();
    }
};

The buffer will have the same content unless you call converting operator again. If you want to have multiple buffers, you can have multiple instances of sstream_proxy. The code is not bulletproof, but much easier to read and understand.

The code will be much more natural on its part.


Text adventure and global variables I'm working on this little text based game. Up to this point, I've gotten it to work, however I've heard I shouldn't be using global like I am. I have this set up to modify the global variables because I want the player to revisit a place and all the events have still been triggered.

I've just started programming, so I don't have knowledge of lots of concepts. The tutorials I've been reading include Learning Python the Hard Way.

print "You are a lone adventurer with the bounty to clear out the crypt."
print "You come with nothing but your sword and a compass."
print "You enter the crypt."
print "To the north you have a gated portaculas and rooms to the west and east."
print "What do you do?"

gate = False
lever = False
def entrance():
    global gate

    while True:
        choice = raw_input('> ')

        if choice == 'west':
            guard_shack()
        elif choice == 'east':
            lever_rm()
        elif choice == 'north' and gate == False:
            print "The gate is still closed and locked."
            entrance()
        elif choice == 'north' and gate == True:
            fountain_rm()
        else:
            entrance(gate)

def lever_rm():
    global lever
    global gate

    print "You enter the room."
    print "What do you do"

    while True:
        choice = raw_input('> ')

        if 'search' in choice:
            print "You look around the room and notice a lever on the opposite wall."
        elif "pull lever" in choice:
            print "You pull the lever."
            lever = True
            gate = True
        elif choice == 'west':
            entrance()
        else:
            print '> '

def fountain_rm():
    print "you're in the lever room!"
entrance()

It will make sense to use OOP in your implementation.
You can model the crypt as a Crypt class,
there gate and lever can be attributes,
and entrance, lever_room can be methods.

Transforming your implementation is quite easy, follow this pattern:

class Crypt(object):
    def __init__(self):
        self.gate = False
        self.lever = False

    def entrance(self):
        while True:
            choice = raw_input('> ')

            if choice == 'west':
                self.guard_shack()
            elif choice == 'east':
                self.lever_rm()
            elif choice == 'north' and not self.gate:
                print "The gate is still closed and locked."
                self.entrance()
            elif choice == 'north' and self.gate:
                self.fountain_rm()
            else:
                self.entrance()

# ...

def main():
    crypt = Crypt()
    crypt.welcome()
    crypt.entrance()

To learn more about classes and OOP in Python,
I recommend the official tutorial.

It's not a good practice to run code in the global namespace,
because if you try to import this module from another module,
all that code will be executed immediately.

The right way to do this in Python is to add this conditional:

if __name__ == '__main__':
    main()

This condition will only be true when the file is executed as a Python script.

Don't use the == operator to check the value of boolean variables and expressions like this:

elif choice == 'north' and gate == False:
    print "The gate is still closed and locked."
    entrance()
elif choice == 'north' and gate == True:
    fountain_rm()

Instead of x == True you can use the boolean variable directly,
in case of x != False you should use not x, for example:

elif choice == 'north' and not gate:
    print "The gate is still closed and locked."
    entrance()
elif choice == 'north' and gate:
    fountain_rm()

This looks like a bug:

else:
    entrance(gate)

Because in your declaration the entrance method doesn't take any parameters.


JavaScript function to categorize data by their "styles" attribute, and store the key-"unicode" pair I have a JavaScript function to categorize data by their "styles" attribute, and store the key-"unicode" pair.

Here's my current code:

function processMetadata(metadata) {
    let regular = {}, solid = {}, brands = {}
    for (let icon in metadata) {
        let styles = metadata[icon].styles
        let codePoint = metadata[icon].unicode
        if (styles.includes('regular')) {
            regular[icon] = codePoint
        }
        if (styles.includes('solid')) {
            solid[icon] = codePoint
        }
        if (styles.includes('brands')) {
            brands[icon] = codePoint
        }
    }
    return {regular, solid, brands}
}

However, CodeClimate keeps complaining about

  Function processMetadata has a Cognitive Complexity of 7 (exceeds 5 allowed). Consider refactoring.

I want to resolve this issue, but I'm not aware of any way to further reduce the complexity without reducing the performance of this code. The following snippet does reduce the cognitive complexity to under 5 but at the expense of performance (3+3 loops instead of 1) and extra dependency:

function processMetadata(metadata) {
    let regular = _.pickBy(metadata, icon => icon.styles.includes('regular'))
    regular = _.mapValues(regular, icon => icon.unicode)
    let solid = _.pickBy(metadata, icon => icon.styles.includes('solid'))
    solid = _.mapValues(solid, icon => icon.unicode)
    let brands = _.pickBy(metadata, icon => icon.styles.includes('brands'))
    brands = _.mapValues(brands, icon => icon.unicode)
    return {regular, solid, brands}
}

Is there any way I can achieve this without having a significant impact on the performance?

First off, some code review items;

Don't skip on semicolons
You are not changing a number of variables, consider const over let in those cases
The names of your styles match the names of your variables, you could use this

Given that, I would consider something like this

function processMetadata(metadata) {
    let out = {regular: {}, solid: {}, brands: {}};
    for (const icon in metadata) {
        const styles = metadata[icon].styles;
        const codePoint = metadata[icon].unicode;
        for(const style in out){
            if (styles.includes(style)) {
                out[style][icon] = codePoint;
            }
        }
    }
    return out;
}


Recreation of cat in C I have a school project to create a program that works the same as the Linux cat. The code works, but I just need find out where I can Improve it or handle errors. The program has 3 .c files and 1 header file. I'm also not allowed to use system functions; I have to use read(), close(), open() and write() and while loop only.

ft_read.c

#include "ft_read_file.h"

 int    ft_len(char *str)
 {
     int    i;

     i = 0;
     while (str[i] != '\0')
     i++;
     return (i);
  }

  void  ft_error(char *file_name)
  {
       ft_writeln(1, file_name, ft_len(file_name));
       ft_writeln(1, ": ", 2);
       ft_writeln(1, file_name, ft_len(file_name));
       ft_writeln(1, ":", 1);
       ft_writeln(1, " No such file or directory", 26);
       ft_writeln(1, ".\n", 2);
   }

   int  ft_read(int files, char **file_name)
   {
       int  fd;
       int  i;
       char buf[4096];
       int  size;

       fd = 1;
       i = 1;
       size = 0;
       while (i < files)
       {
           fd = open(file_name[i], O_RDONLY);
           if (fd == -1)
           {
               ft_error(file_name[i]);
                return (1);
            }
             size = read(fd, buf, 4095);
             buf[4095] = '\0';
             ft_writeln(1, buf, size);
             close(fd);
             i++;
          }
          return (0);
     }

main.c

#include "ft_read_file.h"

int main(int argc, char **argv)
{
    if (argc >= 1)
        ft_read(argc, argv);
    return (0);
 }

ft_writeln.c

#include "ft_read_file.h"

void    ft_writeln(int fd, void *buf, int size)
{
       write(fd, buf, size);
}

Use the C standard library

Your code could be greatly simplified if you used the C standard library functions fopen, fclose, fread, fwrite and fprintf instead of the low-level POSIX system calls. The standard libraray also provides strlen which obsoletes your ft_len function but if you use the functions mentioned earlier, you won't have to count the length of a string any more anyway. If these standard library functions are verboten in your assignment, please state this in your question.

Be prepared for read and write to return early

read and write are not guaranteed to read or write all bytes they were asked to. The proper way to use them is therefore to call them in a loop until either all bytes are read / written or an error is encountered.

Be prepared for read and write to fail

read and write may fail in which case they return a negative value and set errno. You should check this and act upon the error appropriately.

Be prepared for files larger than 4095 bytes

You only call read a single time per file. The concerns about read returning early aside, what if the file is larger than your buffer?

Get rid of useless NUL termination

You stick a '\0' byte at the end of your buffer but nothing expects this. You're already passing around an explicit length (which is good, because the buffer may contain embedded NUL bytes). And if you do it anyway, it should be buf[size] = '\0';.

Don't guess the reason for an error

If you cannot open a file, you always report “No such file or directory”. But that isn't the only reason a call to open can fail. You should inspect the value of errno to find out why the operation failed. If you cannot find out the reason, reporting a generic error like “Cannot open file … for reading” is still better than guessing a potentially wrong reason. Reporting a wrong reason is worse than reporting no reason at all because it will mislead your users.

#include all required headers

I don't see any #includes of system headers in your code. Your code depends on the following headers.

<unistd.h> for open, read, write and close
<sys/stat.h> and <fcntl.h> for the respective flags

In case you have #included them in the header file you didn't show: Don't do that. What functions are needed in the implementation is an implementation detail. You headers should only expose the public API of your module.

Use proper types

The length of an array should be measured in size_t (defined in <stddef.h>) instead of int. The return type of read and write is ssize_t.

Avoid uninitialized variables

It's not the 1980's any more where we had to write code like this.

int i;
// …
i = 1;
// …
while (i < files)
  {
    // …
    ++i;
  }

Instead, we can write this.

for (int i = 1; i < files; ++i)
  {
    // …
  }

The more you limit the scope of a variable, the lesser the risk for accidentally misusing it.

The variables size and fd could be declared only inside the body of the loop. fd could be declared const then.

const int fd = open( … );

It would avoid certain mistakes and you wouldn't be tempted to initialize it with a meaningless value.

Avoid magic numbers

Your choice for a buffer size of 4096 is reasonable but still arbitrary. One day, you might decide to chose a different size. Yet, the constant – or, even worse, constants derived from it, which you cannot search for – is repeated several times in the code. Instead of hard-coding such magic numbers, use a named constant.

#define BUFFER_SIZE 4096

char buffer[BUFFER_SIZE];

const ssize_t count = read(fd, buffer, BUFFER_SIZE - 1);

You could also use sizeof(buffer).

Since C now supports variable-length arrays, you could also use a const variable instead of a macro #define.

Subtracting 1 isn't really needed because NUL termination isn't needed as mentioned above. But when you do need to derive a size, using an expression like this automatically updates the dependent value if the value it depends on changes.

The line

ft_writeln(1, " No such file or directory", 26);

is another example that is waiting for somebody to alter the text and forgetting to update the number. It's not even clear what the 26 means immediately.

In order to further reduce the amount of magic constants, consider using the macros STDOUT_FILENO, STDERR_FILENO and STDIN_FILENO, which are #defined in <unistd.h> to 1, 2 and 0 respectively. The benefit is not so much that these constants would change any time soon or people don't know what file descriptor 1 refers to but that in a function call

print(1, "hello, world\n");

the 1 could mean almost anything whereas in

print(STDOUT_FILENO, "hello, world\n");

the meaning of the first argument is much clearer.

Print error messages to standard error output

Programs should output their results to standard output and any logging, warnings or error messages to standard error output. One reason for this is that standard output is often redirected. If I execute

$ cat bar.c baz.c > foo.c

all standard output will go to foo.c but I still want to see the error messages. (And even if I don't want to see them, I certainly don't want them to end up in foo.c.)

Separate concerns

The arguments passed to main include the program name as argv[0]. This is fine but your ft_read function really shouldn't care where its arguments came from. Instead, the call in main should only pass it the relevant arguments

ft_read(argc - 1, argv + 1);

and ft_read should consider all elements (starting with index 0) of the array as file names to operate on.

Report errors all the way back

If your program fails at any point, it should report this back via its exit status. Therefore, if you encounter an error you cannot recover from, main should return EXIT_FAILURE (which is #defined in <stdlib.h>) or a small positive integer.

Structure the code in the way that minimizes surprises

You have separated the implementation logic from the file that contains the main function. This is good because it allows unit testing and code re-use. But there isn't really a good reason to put the ft_writeln function into a separate file. Actually, why do you have this function at all?

Declare functions static when they need not be externally visible

If a function is only used in the translation unit (the *.c file) that defines it, declare it static. This will make it inaccessible from other translation units and therefore improve encapsulation and avoid name-space pollution. It might also help increase performance.

Use names that properly reflect what a function is doing

ft_writeln sounds as if the function would write a line. But it actually doesn't care about lines. It simply writes out bytes.

Don't confuse return with a function

The return statement is not a function call. You don't need parenthesis around the value that is to be returned.

Use proper indentation

Your code is formatted correctly most of the time. But at some points, you forgot to indent the body of a loop or misplaced braces. There is no point in engaging in a flame war about how many spaces are the correct choice but there can be no dispute that you should use some indentation and use the same style consistently. A good editor will take care of this for you automatically.

Read the documentation for cat

If your goal is to be compatible to POSIX cat, read its documentation to find out what it does exactly. Implementing all of its options might be too much work for now but an interesting aspect of its behavior is currently not reflected by your version. If cat is given zero arguments, it reads from standard input instead. Your program simply does nothing in this case.


Maximum product of 3 integers in an int array using Python This is an interview question from Interview Cake:

  Given a list_of_ints, find the highest_product you can get from three of the integers.
  The input list_of_ints will always have at least three integers.

I'm looking for feedback on how to improve readability, space, time complexity, using Python idiomatic code and general feedback.

import unittest

def highest_product(list_of_ints):
    pos = [0, 0, 0]
    neg = [0, 0]

    for x in list_of_ints:
        if x > 0 and x > pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x > 0 and x > pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x > 0 and x > pos[2]:
            pos[2] = x
        elif x < 0 and x < neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x < 0 and x < neg[1]:
            neg[1] = x

    if neg[1] < 0:
        max_product = max([x * neg[0] * neg[1] for x in pos])
        max_product = max(pos[0] * pos[1] * pos[2], max_product)
    else:
        max_product = pos[0] * pos[1] * pos[2]

    return max_product

class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)

if __name__ == '__main__':
    unittest.main(verbosity=2)

First, I'm not a Python guy, so please don't use anything I say to suggest style.  I'm trying to copy the style that you used with minor algorithmic differences.  I apologize if I make a mistake in doing so.

        if x > 0 and x > pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x > 0 and x > pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x > 0 and x > pos[2]:
            pos[2] = x
        elif x < 0 and x < neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x < 0 and x < neg[1]:
            neg[1] = x

The x > 0 and x < 0 will have the same result throughout.  So we can do just one of each.

        if x > 0:
            if x > pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x > pos[1]:
                pos[2], pos[1] = pos[1], x
            elif x > pos[2]:
                pos[2] = x
        elif x < 0:
            if x < neg[0]:
                neg[1], neg[0] = neg[0], x
            elif x < neg[1]:
                neg[1] = x

Now we do at most four comparisons and may do as few as two.  The original also did at least two and could do as many as eight (if greater than 0 but smaller than the three largest positive values).

We can actually reduce that and keep the same behavior

        if x > pos[2]:
            if x > pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x > pos[1]:
                pos[2], pos[1] = pos[1], x
            else:
                pos[2] = x
        elif x < neg[1]:
            if x < neg[0]:
                neg[1], neg[0] = neg[0], x
            else:
                neg[1] = x

Still the same minimum of two, but the maximum drops to three.  We get the same behavior because both values are initialized to 0 and only move in one direction from there.  So if x > pos[2], it will also be greater than 0.  And x < neg[1] means that it is less than 0.

Perhaps you've noticed a problem though.  This code does not solve the problem correctly.  But it does produce the same result as your original code, so the bug is in the original code.

Bug

You have one unit test:

class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)

But what if you add a second that says

        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

Your code will fail, returning 0 instead of -2.  This is because you initialize the arrays to 0, but you don't verify that there are non-negative members of the array.  0 is not a valid answer here.

If all the numbers are negative, then max_product is negative when

        max_product = max(pos[0] * pos[1] * pos[2], max_product)

So the first product is 0 * 0 * 0, which is 0.  0 will be greater than the product of any three negative numbers.  This incorrect answer will hide any possible correct answer.

        max_product = max([x * neg[0] * neg[1] for x in pos])

This is also wrong.  Even if you fix the other line, this may multiply the wrong three numbers.  For example, consider the input above.  The neg variable would hold -6 and -2 (the two smallest negative numbers).  So the max product would be -6 * -2 * -1 = -12.  But the actual answer should be -2 * -1 * -1 = -2, which is the product of the three largest numbers.

I'll leave it up to you to think through the ramifications of possible fixes.  You may want to consider when

        max_product = pos[0] * neg[0] * neg[1];

will give a different result than checking every x.  Also, how do you tell when pos[0] * pos[1] * pos[2] should and should not be zero?  In particular, consider if it matters if those three values are positive.

To what else could you initialize pos other than 0?


BMI Calculator using Python 3 I am creating a simple BMI Calculator to check if the user is overweight or not. I am not sure how much improvement I need but I do appreciate any comments as to whether the coding is inconsistent.

def introduction_page():
  print("Welcome to the BMI Calculator")
  to_start = str(input("Y to start. N to exit"))
  if to_start in ("Y","y"):
    print("We will calculate now")
    return main_page()
  else:
    print("exiting")

def main_page():
  found = False

  while not found:
    weight_store = float()
    height_store = float()
    user_weight = float(input("Please enter your weight(kg): "))
    weight_confirm =  str(input("Y to confirm. N to re-enter"))
    if weight_confirm in("y","Y"):
      weight_store = weight_store + user_weight
      while not found:
        user_height = float(input("Please enter your height(m): "))
        height_confirm = str(input("Y to confirm. N to re-enter"))
        if height_confirm in ("Y","y"):
          height_store = height_store + user_height
          total_height = (height_store * height_store)
          total_weight = (weight_store)
          BMI = (total_weight / total_height)
          print (int(BMI))
          if (BMI < 18.5 or BMI <25) :
            print("Normal Weight")
            found = True
          elif (BMI < 25 or BMI < 30):
            print("Over-weight")
            found = True
          elif (BMI < 30 or BMI < 40):
            print("Obesity")
            found = True
          else:
            print("Morbid Obesity")
            found = True
        else:
          print("Please re-enter")
    else:
      print("Please re-enter!")

introduction_page()

for a starter I see tree aspects which you could upgrade:

Improve code readability
Make code reusable
Improve validation / error handling.

From main_page() extract 4 functions:

get_user_height()
get_user_weight()
calculate_bmi(height, weight)
print_bmi_description(bmi)

In get_user_height() and get_user_weight() user input. What is min and max value which are correct in your model? e.g. nobody has weight of -1.0.
Make sure that you can trust this functions i.e. they return only valid values.

calculate_bmi(height, weight) - extracting calculation code to distinct function makes it easy to reuse and test (unit tests or even simpler in interactive console).

print_bmi_description(bmi) - make sure your logic covers all possible values. By covers I mean it returns correct description or throws an error (ie. for negative BMIs).

You should remove redundant code eg. BMI < 18.5 or BMI <25 -
check only for BMI <25.
Validate your logic. BMI < 30 or BMI < 40 seems incorrect. I think it should be BMI > 30 or BMI < 40 or in more pythonic way 30 < BMI < 40

I think it is enough for know. If you make this changes we could make next step :-)


Plugin system for calling methods I have a small "plugin system" (I'm not sure this is the right name). It allow you to store objects (plugins), and then call some methods from each of them. With this approach we have absolutely no overhead on iterating/object pass/callback call.

// Need this SET, because in C++11 auto can only be static const.
// And we may need to change them later.
#ifndef SET
    #define SET(NAME, VALUE) decltype(VALUE) NAME = VALUE
#endif

Plugin1 plugin1(param1, param2);
Plugin2 plugin2(param1, param2);
Plugin3 plugin3(param1, param2);

SET(plugins, std::forward_as_tuple(           // Pay attention here. We store &&, not objects
    plugin1,
    plugin2,
    plugin3
));

Then, when I need to call some function from each of plugins, or do something with each of them, I iterate through plugins at compile time (I check this with generated asm code, and it just calls or even inline do_it, without anything else) and call the callback function (I'm not showing iterate code here; it's trivial):

struct Call{
    float k=0;

    template<typename T, int Index>        // lambda function not efficient than this. Tested -O2 clang, gcc 4.8
    inline void do_it(T &&t){
        std::cout << "value = " <<t << " ; " << "id = " << Index << std::endl;
    }
};

And if I need to do something with a specific plugin, I just directly use plugin1, plugin2, and plugin3. No need to call std::get<>. Plus the IDE highlights available plugins when you type them.

Is it ok to store rvalue references on objects, or I have to store objects directly in my tuple?

Like this:

SET(plugins, std::tuple(
    Plugin1(param1, param2),
    Plugin2(param1, param2),
    Plugin3(param1, param2)
));

When I iterate, I pass a plugin as a usual reference:

struct Call{
    float k=0;

    template<typename T, int Index>        // lambda function not efficient than this. Tested -O2 clang, gcc 4.8
    inline void do_it(T &t){
        std::cout << "value = " <<t << " ; " << "id = " << Index << std::endl;
    }
};

With this approach we have additional move constructor calls for each element in the tuple. The previous version is free.

I ask about this because I previously read about data locality and now I worry about how data are placed in memory.

First, you are not storing &&, but rather &. Why? because plugin1 etc. are lvalue references, and because of the reference collapsing rules.

Second, you can use a tuple of references as you would use a reference itself. That is, everything is fine unless you return a tuple of references to local objects, in which case references are dangling.

Third, between forwarding (forward_as_tuple) and copying (make_tuple) there's another option:

template<class... A>
constexpr std::tuple<A...> auto_tuple(A&&... a)
{
    return std::tuple<A...>(std::forward<A>(a)...);
}

which keeps a reference to lvalues, and copies rvalues only. I find this most convenient.

In general, storing references or objects depends on what you want to do. Think of what you would choose if it was only one object, then keep the same choice for the tuple.

Check here for more.


Binary Search Tree insert method (map interface) This is my implementation based on Map<K,V> interface. The BST is a linked binary tree with root reference, both internal and external nodes (MyBSNode) contains (key, value) entries

What do you think? There's something to improve?

public BSPosition<E> insert(int k, E e) {
    if(isEmpty()){
        /* Sets root */
        BSPosition<E> r = new MyBSNode<E>(null);
        r.setElement(k, e);
        setRoot(r);
        size++;
        return r;
    }

    BSPosition<E> n = treeInsert(k, root);          //k-key node or last node visited
    if(k == n.getKey()){                            //tree has already a k-key node
        n.setElement(k, e);                         //only modifies e
        return n;
    }
    /* n is a external (last visited) node with different key */
    size++;
    if(k < n.getKey())
        return n.setLeftChild(k, e);
    else
        return n.setRightChild(k, e);

}

private BSPosition<E> treeInsert(int k, BSPosition<E> v){
    if(isLeaf(v))                       return v;

    if(k < v.getKey()){
        if(v.getLeftChild() == null)    return v;
        return treeInsert(k, v.getLeftChild());
    }
    else if(k == v.getKey())            return v;

    else{
        if(v.getRightChild() == null)   return v;
        return treeInsert(k, v.getRightChild());
    }
}

The algorithm looks fine. Some other notes:

I would use longer variable names than r, k, e etc. Longer names would make the code more readable since readers/maintainers don't have to decode or memorize the abbreviations.

new MyBSNode<E>(null)

Consider creating a default contructor, a named factory method or an explanatory local variable for null. Currently readers have to check the MyBSNode constructor to figure out what's that null supposed to mean.
MyBSNode does not seem to have a good name. Try to find something more descriptive.
n.setElement(k, e); // only modifies e

Creating a setValue(E value) method would make the comment unnecessary and would be cleaner.
I'd consider moving isLeaf to BSPosition since it seems data envy. I guess its only task is to check that both left and right children are nulls.
treeInsert does not do any insertion, its name is a little bit misleading, it just searches the parent of the new node or a node with the same key. I'd call it according to that. (searchInsertionPoint for example.)


Descriptor to restrict input We start off we the following Person class:

class Person:
    def __init__(self):
        self.moods = {
            "happy": 5,
            "angry": 5,
            "sad": 5
        }

    def updateStates(self, stateUpdates: {}):
        for mood, valChange in stateUpdates.items():
            self.moods[mood] += valChange

From here I implemented a restriction on what the values self.moods can be.
I have implemented the restriction using descriptors. But I find it distasteful.

The following works. But I don't think it is worth it because now I have to append .__get__(instance=self, owner=None) to self.moods[<mood>] whenever I need to access a mood, or .__set__(instance=self, value=<newVal>) whenever I want to update one. This will quickly pollute my code and make it unreadable, which is why I am not a fan of this approach.

class OneDigitNumericValue():    # descriptor class
    def __set_name__(self, owner, name):
        self.name = name

    def __init__(self, defaultVal=5):
        self.value = defaultVal

    def __get__(self, instance, owner) -> object:
        return self.value

    def __set__(self, instance, value) -> None:
        if not (0 < value < 9) or int(value) != int:
            raise AttributeError("The value is invalid")
        self.value = value

class Person:
    moods = {
        "happy": OneDigitNumericValue(),
        "angry": OneDigitNumericValue(),
        "sad": OneDigitNumericValue()
    }

    def updateStates(self, stateUpdates: {}):
        for mood, valChange in stateUpdates.items():
            oldVal = self.moods[mood].__get__(self, owner=None)
            self.moods[mood].__set__(self, value=oldVal + valChange)

Your solution just doesn't work

Your validation check always fails. Yes int(value) != int is always true. I don't think an instance of a class will ever be the class that it's an instance of.
Your mutating a class variable. The tool you're utilizing forces you to take instances, normally there's a pretty good reason.

If we remove the previous error and run your code we can easily see, there's no point in having more than one instance of a Player.

>>> a = Person()
>>> b = Person()
>>> a.moods['happy'].__set__(a, 8)
>>> b.moods['happy'].__get__(b, None)
8  # Ok, that's not right...

I don't believe you've actually tried to code you've provided. And honestly what's the point in a single-data non-singleton class? The provided code is just untested garbage.

You're using it wrong

If it's not evident enough that you're fighting a tool that is pure sugar. Then you're not doing it right. The instance has to keep the state of the instance, and the descriptor has to interact with a varying amount of instances to interact with their state correctly.

If anything of the instance's leaks out into the descriptor, or vice versa. Then you're going to have a bad, bad time.

Since descriptors are to be tied onto classes I'm making a Mood class. Since the descriptor needs to have a place to store data. We can define that in the __init__ of Mood. To note, because you may not notice this by yourself. self._values can be mutated to bypass the validator. Using self._values[mood] = value is not how you update values, use setattr(self, mood, value).

In addition to fixing OneDigitNumericValue, you should make it take an argument that is the validator for the function. If you need another validator it'd be better and simpler to make a simple hard to mess-up function. Rather than making lots of potentially broken descriptors.

def single_digit(value):
    if 0 <= value <= 9:
        return
    raise ValueError("The value is invalid")

class Validator:
    def __init__(self, validator):
        self.validator = validator
        self.name = None

    def __set_name__(self, owner, name):
        self.name = name

    def __get__(self, instance, owner) -> object:
        return instance._values[self.name]

    def __set__(self, instance, value) -> None:
        self.validator(value)
        instance._values[self.name] = value

class Mood:
    happy = Validator(single_digit)
    angry = Validator(single_digit)
    sad = Validator(single_digit)

    def __init__(self):
        self._values = {}
        self.happy = 5
        self.angry = 5
        self.sad = 5

    def update_states(self, states):
        for mood, value in states.items():
            setattr(self, mood, value + getattr(self, mood))

And it actually works:

>>> a = Mood()
>>> b = Mood()
>>> a.happy = 3
>>> a.happy
3
>>> b.happy
5
>>> a.update_states({'happy': 3})
>>> a.happy
6


Print path (leaf to root) with max sum in a binary tree I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

public class MaxSumPath {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        TreeNode (TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    private static class TreeInfo {
        TreeNode node;
        int maxCount;

        TreeInfo (TreeNode node, int maxCount) {
            this.node = node;
            this.maxCount = maxCount;
        }
    }

    public void maxSumPath () {
        final TreeInfo treeInfo = new TreeInfo(null, 0);
        fetchMaxSumPath(root, treeInfo, root.item);
        printPath (root, treeInfo);
    }

    private void fetchMaxSumPath (TreeNode node, TreeInfo treeInfo, int sumSoFar) {
        if (node == null) return;

        sumSoFar = sumSoFar + node.item;

        if (node.right == null && node.left == null) {
            if (sumSoFar > treeInfo.maxCount) {
                treeInfo.maxCount = sumSoFar;
                treeInfo.node = node;
            }
            return;
        }

        fetchMaxSumPath(node.left, treeInfo, sumSoFar);
        fetchMaxSumPath(node.right, treeInfo, sumSoFar);
    }

    private boolean printPath (TreeNode node, TreeInfo treeInfo) {
        if (node != null &&  (node == treeInfo.node || printPath(node.left, treeInfo) || printPath(node.right, treeInfo))) {
            System.out.print(node.item + ", ");
            return true;
        }
        return false;
    }
}

Also considering additional storage (TreeInfo), is it right to say that the space complexity is \$O(1)\$?

You should have a constructor MaxSumPath(TreeNode root).  Otherwise, there's no way for any other class to call the code.

The TreeNode(left, right, item) constructor is awkward.  Consider rearranging the TreeNode constructor arguments to TreeNode(left, item, right) or TreeNode(item, left, right).  I suggest creating a TreeNode(item) constructor as well.

Your TreeInfo could be eliminated by moving its variables into MaxSumPath itself.  I'd rename the variables to TreeNode maxLeaf and int maxSum.

In the maxSumPath() method, you call fetchMaxSumPath(root, treeInfo, root.item).  It should be fetchMaxSumPath(root, treeInfo, 0) if you don't want to double-count the root node.  (Fortunately, this bug happens not to affect the output.)

The space complexity is actually O(log n) when you take into account the stack used in recursion.  The time complexity is O(n), because you visit every node once when discovering the leaf for the path with the maximum sum, and every node again to find that leaf for printing.  You might want to use O(log n) space (which, remember, happens anyway due to the recursion stack) to keep track of the best path while discovering the best sum, which lets you avoid the second pass O(n) pass.


Find the sum along root-to-leaf paths of a tree Most of you already know me, please be brutal, and treat this code as if it was written at a top tech interview company.

Question:

  Given a binary tree and a sum, find all root-to-leaf paths where each
  path's sum equals the given sum.

  For example: Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

  return

[
   [5,4,11,2],
   [5,8,4,5]
]

Time taken: 26 minutes (all 110 test cases passed)

Worst case: \$O(n^2)\$?
Since when I add to resList, it copies all the elements again which can take \$O(n)\$ and I traverse \$O(n)\$ nodes.

Space complexity: \$O(n)\$

My code:

ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> curList = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    if(root==null){
        return res;
    }
    curList.add(root.val);
    if(root.left==null && root.right==null){
        if(sum - root.val==0){
            res.add(new ArrayList<Integer>(curList));
        }
    }
    if(root.left!=null){
        pathSum(root.left, sum-root.val);
    }
    if(root.right!=null){
        pathSum(root.right, sum-root.val);
    }
    curList.remove(new Integer(root.val));
    return res;
}

You are treating res and curList as if they are Globals, and, since they are globals, there is no reason to return ret in the function at all.

As a result of this, your code is not re-entrant (you can only have one method calling your pathSum at any one point in time).

The right solution to this is to pass the curList and ret values as parameters to the method, convert it to private, and create a new public method which creates the instances as you need them.....

public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> curList = new ArrayList<Integer>();
    pathSum(root, sum, curList, res);
    return res;
}

private void pathSum(TreeNode root, int sum,
            ArrayList<Integer> curList, ArrayList<ArrayList<Integer>> res) {
    ....
    ** change the methods called as part of the recursion too**
    ....
}

That is the big structural change, but I would recommend more:

methods should not return specific List implementation types unless those types have special features you need. your method should return List<List<Integer>> and not ArrayList<ArrayList<Integer>>
convert curList to an array of int[], and the return valye of the system to List
you do the calculation sum-root.val in multiple places. Firstly, it should be spaced properly: sum - root.val, and secondly, you should save it as a variable once, and re-use that variable in the places where it currently is a function

About the complexity

you ask if worst case is \$O(n^2)\$ ... no, it is not.

Worst case is \$O(n \log(n))\$. This is my reasoning:

the depth of a binary tree is about \$\log(n)\$.
The deepest a binary tree can be is depth n, but, in that case there is only one possible solution, so the complexity will be two \$O(n)\$ operations, one to scan the single deep branch, and another to copy the array.
the worst case is actually a fully-balanced tree where every leaf node matches the intended sum, in which case the number of solutions is proportional to \$O(n)\$, but the actual copy to the array will be of \$O(log(n))\$ elements

So, My assessment is \$O(n \log(n))\$

Feel free to debate this... I am not 100% certain....


Solving 'decent numbers' that follow specific division rules HackerRank Problem Statement

I have to find the largest 'decent number' having N digits. A decent number has the following properties:

3, 5, or both as its digits. No other digit is allowed.
Number of times 3 appears is divisible by 5.
Number of times 5 appears is divisible by 3.

My code works perfect, but, I am afraid it is far from efficient:

Input:

4 #number of test cases, i.e., the following 4 inputs
1
3
5
11

Output:

-1
555
33333
55555533333

My version of the solution:

T = int(input()) #number of test cases

def computePair(N):
    multiplesOf3 = [i for i in range(N+1) if i%3 == 0]
    if multiplesOf3 != [0]: #reversing a [0] results in a 'NoneType'
        multiplesOf3.reverse()
    multiplesOf5 = [i for i in range(N+1) if i%5 == 0]

    for i in multiplesOf3:
        for j in multiplesOf5:
            if (i+j) == N:
                return (i, j)
    return -1

for testCase in range(T):
    N = int(input()) #test case
    result = computePair(N)
    if result == -1:
        print(result) #If no such combination exists return '-1'
    else:
        print('5' * (result[0]) + '3' * (result[1]))

I assume my code has a time-complexity of \$O(n^2)\$; because of the two for loops. I want this to be more efficient in the order of \$O(n)\$ - linear.

This is a very generic question: also, do you have any resources to time-complexity best practices? I suck at it.

At the heart of your problem you are trying to solve a single linear Diophantine equation. Because 3 and 5 are coprime, their greatest common divisor is 1, and hence your equation, \$3a + 5b = n\$, will always have an integer solution. It is easy to check that \$a = 7n\$, \$b = -4n\$ is indeed one such solution. Of course you want both \$a\$ and \$b\$ to be positive, so if we take the more general solution to your equation, \$a = 7n - 5k\$, \$b = -4n + 3k\$, and impose \$b \ge 0\$, we get \$k = \lceil 4n / 3 \rceil\$.

Let's put this into a Python function:

def partition35(n):
    k = (4*n - 1) // 3 + 1  # rounded up int division
    a = 21*n - 15*k  # (7*n - 5*k)*3
    b = 15*k - 20*n  # (3*k - 4*n)*5
    return a, b

Notice that there is a single division performed. Division and modulo operations are among the most expensive basic operations you can do on integers, so aside from the fact that this method is constant time, that time is likely going to be pretty small.

To solve your original question:

def max_decent(digits):
    a, b = partition35(digits)
    if a < 0:
        print(-1)
    else:
        print(''.join(('5'*a, '3'*b)))


Finding integer with the most natural dividers Problem description: You are given a segment [568023; 569230]. Find integer within given range that has the most natural dividers. If 2 or more integers are found, return the lowest integer among them.
Solution:
def allnums(k):
    cnt = 0
    for i in range(2, k // 2):
        if k % i == 0:
            cnt += 1
    return cnt

MAX_NUM = 0
MAX = 0

for i in range(568023, 569231):
    cnt = allnums(i)
    if MAX < cnt:
        MAX = cnt
        MAX_NUM = i

print(MAX, ' ', MAX_NUM)

Output: 141   568260
Runtime: 17s

Question: Is there any way to make this code more concise, maybe also improving its runtime? Thank you in advance.

It's not clear what you mean with "natural dividers". Better specify that, show examples, and document allnums to say what it does. A better name would also help. For example allnums(6) returns only 1, despite having divisors 1, 2, 3 and 6. At the very least I'd expect answer 2 (for the divisors 2 and 3). So probably it's incorrect, but we can't even tell because you didn't say what exactly it's supposed to do.
Anyway, as usual it suffices to try divisors until the square root, not until half. If you find a divisor i of k, then don't just count that divisor but also count its partner divisor k/i. Unless that's the same.
And max can take an iterable and key.
So:
from math import isqrt

def divisors(k):
    """Compute the number of k's divisors 1 < divisor < k."""
    cnt = 0
    for i in range(2, isqrt(k) + 1):
        if k % i == 0:
            cnt += 2 - (k // i == i)
    return cnt

print(max(range(568023, 569231), key=divisors))

Takes about 0.1 seconds.


Minesweeper field marking I just did an interview where the last challenge was to write a function that reads a minesweeper matrix from a file and marks how many bombs there are around each cell. I had 20 min and had a < comparison that should have been <=. My main question is how I could have done it faster since it only took me 5 min to locate the bug and fix it. The other thing I would like to know is what a reviewer probably would think about it.

Here's my hacky code (the only requirement was to produce the correct output):

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

void read_matrix(char* dest, char const* file)
{
  FILE* input = fopen(file, "r");
  char temp[128];
  int d= 0;

  fread(temp, 1, sizeof temp, input);

  for(int i = 0; i < 128; ++i){
    if(' ' != temp[i] && '\n' != temp[i]){
      dest[d++] = temp[i];
    }
  }
  fclose(input);
}

char _grid_at(char const* grid, int x, int y)
{
  return grid[y * 8 + x];
}

int _surround_count(char const* grid, int x, int y)
{
  int count = 0;
  int x0 = x;
  int x1 = x;
  int y0 = y;
  int y1 = y;

  if(x > 0){
    x0 = x - 1;
  }
  if(x < 7){
    x1 = x + 1;
  }
  if(y > 0){
    y0 = y - 1;
  }
  if(y < 7){
    y1 = y + 1;
  }

  // here's where the problem was
  for(x = x0; x <= x1; ++x){
    for(y = y0; y <= y1; ++y){
      if('X' == _grid_at(grid, x, y)){
        count += 1;
      }
    }
  }

  return count;
}

void mark_field(char* dest, char const* src)
{
  for(int x = 0; x < 8; ++x){
    for(int y = 0; y < 8; ++y){
      if('X' != src[y*8+x]){
        dest[y*8 + x] = '0' + _surround_count(src, x, y);
      }
      else {
        dest[y*8 + x] = 'X';
      }
    }
  }
}

void print_field(char const* field)
{
  for(int i = 0; i < 64; ++i){
    putchar(field[i]);
    if((i & 7) == 7){
      putchar('\n');
    }
  }

}

int main(int argc, char* argv[])
{
  char matrix[64];

  read_matrix(matrix, argv[1]);
  print_field(matrix);
  puts("------------");

  char count[64];
  mark_field(count, matrix);
  print_field(count);

  return 0;
}

Input:

X O O X X X O O
O O O O X O X X
X X O X X O O O
O X O O O X X X
O O X X X X O X
X O X X X O X O
O O O X O X O X
X O X X O X O X

Output:

X 1 1 X X X 3 2
3 3 3 5 X 5 X X
X X 3 X X 5 5 4
3 X 5 5 6 X X X
2 4 X X X X 6 X
X 3 X X X 5 X 3
2 4 5 X 6 X 5 X
X 2 X X 4 X 4 X

Interview Notices

Check the result of system calls

FILE* input = fopen(file, "r");      // Can return null
fread(temp, 1, sizeof temp, input);  // returns the number read (which may not be sizeof temp
fclose(input);                       // Can fail

Style

Personally don't like:

' ' != temp[i] && '\n' != temp[i]

Reads way too much like Yoda conditionals (which went out of style ten years ago). Its not the natural way to expresses a test in your brain.

temp[i] != ' ' && temp[i] != '\n'

Reads much more naturally (at least to an English speaker). Though in an interview I would not knock points off for this. If I hired you I would re-train you to do it the other way though.

Is this the correct/good interface?

void read_matrix(char* dest, char const* file)

I don't like that dest is an array of char. Are you optimizing for space? Where you asked to optimize for space? I would change that to an array of int, as that expresses intent much more clearly.

void read_matrix(int* dest, char const* file)

I think manually checking for space is making this complex. I would have used the scanf library function to do that work for me.

  for(int i = 0; i < 128; ++i){
    if(' ' != temp[i] && '\n' != temp[i]){
       dest[d++] = temp[i];
    }
 }

// note: I would have made the `dest` array integers
for(int i = 0; i < 128; ++i){
    if (sscanf(temp, " %d", dest + i) != 1) {
        // ERROR
    }
}

Functions beginning with an underscore and a lowercase letter are reserved in the global scope.

char _grid_at(char const* grid, int x, int y)
int  _surround_count(char const* grid, int x, int y)
//   ^^^ reserved identifier.

Don't change the first letter to upper case as an underscore followed by an upper case letter is reserved in all contexts.

I can see why you had an issue (all those tests).

A simple optimization for this is to place your grid inside a grid that is one square larger vertically and horizontally. So if you have an 8×8 grid, place it inside a 10×10 grid. Then mark all the cells around the side as having zero in them.

Then when you call surround_count() you can add the cost of all the squares around the cell:

int surround_count(char const* grid, int x, int y)
{
     assert ( 1 <= x && x <= 8 && 1 <= y && y <= 8);

     int count = 0;
     for(int h = -1; h <= 1; ++h) {
         for(int v = -1; v <= 1; ++v) {
             count += isBombAt(grid, x + h, y + v);
         }
     }
     return 0;
 }


Is using defvar for a non-global variable ok? I am calling defvar in the middle of a function definition. And so far I've always seen its use, with defparameter for global variable. Like *error-output* or *standard-output*.

(defun consume-socket-reply (socket end-test-form)
  (do* ((line "" (read-line (usocket:socket-stream socket) nil))
        (text "" (concatenate 'string text line)))
       ((funcall end-test-form) text)))

(defun read-http-content (socket)
  (defvar line)
  (consume-socket-reply socket (lambda () (not line))))

Is there a better way to write what I am trying to do? That is: being able to pass the end-test-form to the final inner loop.

Defvar always creates a globally special variable (unless it already exists, of course).  It does not matter where you call it.

It is usually used as a toplevel form or directly inside of an eval-when.  The only reason to put it anywhere else that I can think of is the use of closures.

In all other cases, I would strongly suspect that the code does not mean what the author thinks it does.

Here, the globally special variable line is created on the first call of read-http-content.  This may lead to surprising effects if you use the name line in other places.  Don't do that.


Guess the number game (Python) I'm very new to coding and decided to try a mini-project in python to create a 'guess the number game'. I was just hoping for some feedback on my code-writing to prevent bad habits before they develop. This program runs smoothly but I would like to know if there are improvements I could make.
In particular:

How can I improve the efficiency and readability?
Is it okay to call a function within its own body?
Is there any ugly implementation that I should avoid?

import random

number = 0
counter = 0

def start_game():
    print("I'm thinking of a number between 1 and 10.")
    print("Can you guess it?")
    global number
    number = random.randint(1,10)
    global counter
    counter = 0
    check_valid()

def check_valid():
    global counter
    counter += 1
    guess = input()
    try:
        val = int(guess)
        if int(guess) not in range(0,11):
            print("Hmmm.. that number is not between 1 and 10! Try again!")
            check_valid()
        elif int(guess) > number:
            print("Too high, try a smaller number")
            check_valid()
        elif int(guess) < number:
            print("Too low, try a bigger number")
            check_valid()
        elif int(guess) == number:
            print("Congratulations, you guessed it! The number was " +
                  str(number) + ".\nIt took you " + str(counter) + " tries!")
            print("Do you want to play again?")
            check_replay()
    except ValueError:
        print("That's not a number, try again!")
        check_valid()

def check_replay():
    answer = input()
    valid_yes = ["yes", "ye", "y"]
    valid_no = ["no", "n"]
    if answer.lower() in valid_yes:
        start_game()
    elif answer.lower() in valid_no:
        print("Thanks for playing!")
    else:
        print("Please enter yes or no")
        check_replay()

start_game()

One thing I notice is that, you use global variables. While they are not necessarily bad and work fine in this particular case, it might be beneficial to read these answers. It would be better to define these variables in main function and pass them as parameters for other functions.

def start_game(number, counter):
  #Your code here

def main():
  number = 0
  counter = 0
  start_game(number, counter)

if __name__ == "__main__":
    main()

Calling the function within its body is called a recursion and as long as you assure that the calling sequence won't become an infinite loop, it is widely used technique in programming.

One more minor thing: you define val = int(guess) but never use it, maybe delete it?

Other than that, everything looks fine and the code is readable.


Opinions on my Command pattern design - is it extensible? I am implementing a program that takes commands from a user and based on those commands, drives a Robot on a grid. To implement this program I have used the Command pattern. I have used this pattern because, most importantly, I want to be able to add to the list of possible commands in the future.

The program takes a string of commands from the user, and executes those commands, e.g. FFRFLF (forward x 2, turn right, forward, turn left, forward).

Can anyone give me their opinion on the quality of my design?

Robot Controller class:

    public void control(){

do{
    process();
}while(tru);
}

public String process(){

    // 1. Get user input
    String cmds = get user input from console

    // 2. Populate command list
    populateCommandList(cmds);

    // 3. Execute commands
    executeCommands();

       // 4. Display current location of robot
}

public void populateCommandList(String cmds) {

    Command r = new TurnRightCommand(robot);
    Command l = new TurnLeftCommand(robot);
    Command f = new ForwardCommand(robot);

    commands = new ArrayList<Command>();

        for(int i=0; i<cmds.length(); i++){

            char cmd = cmds.charAt(i);
            switch(cmd){
                case 'F':
                    commands.add(f);
                    break;
                case 'R':
                    commands.add(r);
                    break;
                case 'L':
                    commands.add(l);
                    break;
            }
        }
}

private void executeCommands() {
    if(commands!=null && commands.size()>0){
        for(Command cmd : commands){
            cmd.execute();
        }
    }
}

Main class:

public class Main {
    public static void main(String[] args) {

        RobotController r = new RobotController();
        r.control();
    }
}

Is this a good design? I need to know if the deign is good and that I can easily add new commands with minimal rework.

I think you've added an unnecessary layer of abstraction here.

To me, populateCommandList looks completely unnecessary.  You are converting a list of commands in one format (character string) into another format (an array of Command objects).  Then, presumably, executeCommands just executes all of those command objects in order.  This wastes time and memory by creating a bunch of unnecessary objects.

Why not just have executeCommands take the string directly, and execute the appropriate command for each character that it encounters?

In other words, I would have something like this in executeCommands:

   for(int i=0; i<cmds.length(); i++){
       char cmd = cmds.charAt(i);
         switch(cmd){
            case 'F':
                robot.move(FORWARD,1);
                break;
            case 'R':
                robot.turn(RIGHT);
                break;
            case 'L':
                robot.turn(LEFT);
                break;
        }
   }

Either way looks equally extensible to me.  Either way you will have a switch statement somewhere that defines what commands are possible, and that is what you have to change in order to add a new command.


Setting zoom for layer disappearance in Leaflet I have got 2 working codes, where one is a bit longer and another a bit shorter. Is it some way to bind all these layers as a one group?

The first one is:

 map.on('zoomend', function() {
if (map.getZoom() <6){
        map.removeLayer(job);
    }else{
    map.addLayer(job);
    }
    if (map.getZoom() <7){
        map.removeLayer(job2);
    }else{
    map.addLayer(job2);
    }
    if (map.getZoom() <8){
        map.removeLayer(job3);
    }else{
    map.addLayer(job3);
    }
  });

and another one

   map.on('zoomend', function() {
     if (map.getZoom() <8){
        map.removeLayer(job);
    }
    if (map.getZoom() <8){
        map.removeLayer(job2);
    }
    if (map.getZoom() <8){
        map.removeLayer(job3);
    }
     else {
        map.addLayer(job);
        map.addLayer(job2);
        map.addLayer(job3);
    }
   });

I would like to avoid this kind of repeats, as I am going to have multitude of layers in the future.

In your case a better way is using a predefined mapping (as Map) holding the relations between zoom limits and respective jobs.Then, just iterate through the mapping and perform add/remove operation:

const zoomJobsMap = new Map([
  [6, job],
  [7, job2],
  [8, job3],
  ...
]);

map.on('zoomend', function() {
    let zoom = map.getZoom();   # get zoom value at once
    for (var [zoomLimit, jobObj] of zoomJobsMap) {
        (zoom < zoomLimit)? map.removeLayer(jobObj) : map.addLayer(jobObj);

    }
}