Project Euler #18 in Python: Maximum sum down a triangle of numbers I've solved Project Euler #18 in Python but think my code and algorithm can be improved. Here is the problem:

  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

  That is, 3 + 7 + 4 + 9 = 23.

  Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

  NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method!

And I want with an bottom-up calculation to find the best path down. Here is my code:

import time

num_pyr = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''

def break_pyramid(num_pyr):
    '''
    Breaks the number string into an array
    '''
    pyramid = []
    rows = num_pyr.split('\n')
    for row in rows:
        pyramid.append([int(i) for i in row.split(' ')])
    return pyramid

def add_from_under(upper_row, lower_row):
    '''
    Takes the maximum of the legs under upper row to each index to add up from bottom
    Parameters
    ----------
    upper_row : len n
    lower_row : len n + 1

    Returns
    -------
    new_upper_row
    '''
    greater_vals = [max(lower_row[i:i+2]) for i in range(len(upper_row))]
    return [x + y for x, y in zip(upper_row, greater_vals)]

def main():
    pyramid = break_pyramid(num_pyr)[::-1]
    for i in range(len(pyramid)-1):
        new_upper = add_from_under(pyramid[1], pyramid[0])
        pyramid[1] = new_upper
        del pyramid[0]
    return pyramid[0][0]

if __name__ == '__main__':
    t1 = time.time()
    best_path = main()
    op_time = 1000000 * (time.time() - t1)  # us
    print("Calculated {} in {:.1f} us".format(best_path, op_time))

I think improvements can be made in my main() since I am using del. Should del be avoided for any reason?

In break_pyramid you use list comprehension to split a row into
numbers – why not use list comprehension as well to split the input
into rows?

def break_pyramid(num_pyr):
    '''
    Breaks the number string into an array
    '''
    pyramid = [[int(col) for col in row.split(' ')] for row in num_pyr.split('\n')]
    return pyramid

In add_from_under, this

greater_vals = [max(lower_row[i:i+2]) for i in range(len(upper_row))]

creates many intermediate slices. The alternative

greater_vals = [max(l, r) for l, r in zip(lower_row, lower_row[1:])]

seems to be slightly faster. You can even combine both zip operations
into a single one:

def add_from_under(upper_row, lower_row):
    return [upper + max(lower_left, lower_right)
         for upper, lower_left, lower_right in zip(upper_row, lower_row, lower_row[1:])]

so that no intermediate list is created.

The main loop applies add_from_under cumulatively to the pyramid
rows (in reverse order). That is a "reduce" operation and can be done
with functools.reduce:

from functools import reduce

def main():
    pyramid = break_pyramid(num_pyr)
    final_row = reduce(add_from_under, reversed(pyramid))
    return final_row[0]

if we exchange the parameter order in add_from_under to

def add_from_under(lower_row, upper_row):
    return [upper + max(lower_left, lower_right)
         for upper, lower_left, lower_right in zip(upper_row, lower_row, lower_row[1:])]

Now the pyramid variable is just iterated over, but not modified
anymore.


C++ Prime Factorization I just picked up C++ today and I wonder if this is c++-like. I have a bit of experience with Java.

This is a program that takes a number as input and outputs its prime factorization in no particular order.

Specific questions:

Am I using std::vector correctly? With all the insert, maybe there is a better way? Similarly, am I using std::map correctly?
I've never understood what uint_32 is. I understand that it forces the compiler to make the number 32 bits instead of whatever the system decides. Do I need it here?
Is there anything that a C++ programmer wouldn't do that screams "That only happens in Java/other languages" to you?

Note that I am not worried about efficiency, although if there are improvements, those suggestions are definitely welcome.

#include <iostream>
#include <vector>
#include <map>

std::vector<int> primeFactorize(int n) {
    std::vector<int> result;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            auto f1 = primeFactorize(i), f2 = primeFactorize(n / i);
            result.insert(result.begin(), f1.begin(), f1.end());
            result.insert(result.begin(), f2.begin(), f2.end());
            return result;
        }
    }
    result.push_back(n);
    return result;
}

int main(int argc, char** argv) {
    int n;
    std::cin >> n;
    auto factors = primeFactorize(n);
    // Map is designed <factor, exponent>
    std::map<int, int> factorMap;
    for (int factor : factors) {
        if (factorMap.count(factor) == 0) {
            factorMap[factor] = 1;
        } else {
            ++factorMap[factor];
        }
    }
    bool isFirst = true;
    for (auto keyValuePair : factorMap) {
        if (isFirst) {
            isFirst = false;
        } else {
            std::cout << "*";
        }
        std::cout << keyValuePair.first << "^" << keyValuePair.second;
    }
    return 0;
}

I'll first comment on only C++ usage.

vector -- Not exactly sure what you're trying to do by inserting into the front of an array (basically the worst case usage); if you're trying to append, the best way is
result.insert(result.end(), f1.begin(), f1.end());
Vectors are inserted at their end, not front.
map -- std::map is usually implemented as a tree offering O(lgn) queries, not O(1) as you might expect. If you're looking for a hashtable, use std::unordered_map. (however for small use cases and depending on the complexity of the type to hash, map might be faster).
uint32_t is an unsigned 32 bit integer. Use it if you want a guarantee on its size, as unsigned int, unsigned long, and the like depends on architecture and compiler. It is not necessary here (more on that later). This might be helpful:
On the contrary, you are doing it right by returning a std::vector by value. If it's not copy elisioned out entirely, standard library containers come with move constructors (C++11) that make them more efficient to pass out by value than by reference or pointer as some people are in the habit of doing.

OK onto the comments on style and algorithm

I personally find it easier to build programs using templates. For example,
template <typename Num>
std::vector<Num> primeFactorize(Num n)
is more intuitive for me than a function that's forced to take an int.
Avoid needless recursion (especially when it splits into 2 subproblems). Prime factorization can be done iteratively (and I'd argue more intuitively).
Avoid unbalanced divide and conquer algorithms. Here you're dividing the problem by primeFactorize(i), primeFactorize(n / i), which creates a tiny subproblem and a slightly smaller subproblem, which makes O(lgn) algorithms into O(n).
Write comments for yourself to read explaining the algorithm to ensure its correctness and function. For example, when n % i == 0, that means i is a divisor of n. If you wrote that down, you might come to the logical conclusion that you could safely result.push_back(i) and n /= i here instead of the relatively expensive recursion and inserts.
Design algorithms that have nice properties, for example that the factors come in sorted order. This prevents you from having to create the map, which seems terribly redundant (apart from perhaps educational uses). The alternative is the sort the factors, then iterate and count consecutive ones, which results in O(nlgn) operations, just as your map solution uses (as it loops through all n factors, and does a lookup in O(lgn) operations).

Here is my example implementation which gives the factors in sorted order using relatively cheap operations.

template <typename T>
std::vector<T> factorize(T num) {   // works great for smooth numbers
    vector<T> v;
    if (num < 4) { v.push_back(num); return v; }
    T d {2};
    while (num >= d * d) {
        while (num % d == 0) {  // remove all repeats of this divisor
            v.push_back(d);
            num /= d;
        }
        ++d;
        if (d * d > num && num > 1) { v.push_back(num); return v; }
    }
    return v;
}

Possible optimization suggested by Goswin with removing factors of 2

template <typename T>
vector<T> factorize(T num) {    // works great for small prime factors
    vector<T> v;
    if (num < 4) { v.push_back(num); return v; }
    while ((num & 1) == 0) { v.push_back(2); num >>= 1; }   // remove all factors of 2
    T d {3};
    while (num >= d * d) {
        while (num % d == 0) {  // remove all repeats of this divisor
            v.push_back(d);
            num /= d;
        }
        d += 2;
        if (d * d > num && num > 1) { v.push_back(num); return v; }
    }
    return v;
}

Note that you no longer need to use a std::map to find out how many of each factor there are since this algorithms gives them in sorted order. Using a std::map on top of this would just be an unnecessary layer.

For more straightforward(mostly) implementation of various algorithms (they could be quite educational), check out my simple algorithms library


Translate from C to C# I have been working on translating some code from C to C# but since I haven't been coding in C / C++ for many years now plus I do not want to resort to the unsafe keyword. I have made an attempt and would like some verification & optimisation suggestions.

Here is the code in C/C++.

#ifdef __cplusplus /* C++ cannot assign void* from malloc to *data */
#define APPEND_DATA(/* T */ value, /* T** */ data, /* size_t* */ size) {\
  if (!((*size) & ((*size) - 1))) {\
    /*double alloc size if it's a power of two*/\
    void** data_void = reinterpret_cast<void**>(data);\
    *data_void = (*size) == 0 ? malloc(sizeof(**data))\
                              : realloc((*data), (*size) * 2 * sizeof(**data));\
  }\
  (*data)[(*size)] = (value);\
  (*size)++;\
}
#else /* C gives problems with strict-aliasing rules for (void**) cast */
#define APPEND_DATA(/* T */ value, /* T** */ data, /* size_t* */ size) {\
  if (!((*size) & ((*size) - 1))) {\
    /*double alloc size if it's a power of two*/\
    (*data) = (*size) == 0 ? malloc(sizeof(**data))\
                           : realloc((*data), (*size) * 2 * sizeof(**data));\
  }\
  (*data)[(*size)] = (value);\
  (*size)++;\
}
#endif

Here is the code in C#:

public static T[] AppendData<T>(T value, T[] data, ref uint size)
{
    if ((size & (size - 1)) != 0)
    {
        /* Double alloc size if it's a power of two */
        var tsize = size == 0 ? data.Length : size*2*data.Length;
        var tdata = new T[tsize];
        Array.Copy(data, tdata, data.Length);
        tdata[size] = value;
        data = tdata;
    }
    else
    {
        data[size] = value;
    }

    size++;
    return data;
}

One more thing to note is that performance is paramount for this code as the overall algorithm it fits in to is quite slow.

From a micro-optimization perspective I have found that C# and the JIT tend to like things from left to right (post).
Ex: (((size - 1) & size) != 0) and data.Length*size*2

With a macro and readability (verification) perspective I would be curious to see the performance difference between this method and just using List<T>.Add.

When it comes to performance you need to just measure it. On different machines if you can.


Passing a true/false value to a model used in a controller This passes the value of true/false to model which I can use in my controller.

How can this be cleaned up?

        Auto :
        <select name="IsAuto" class="togglehidden" id="IsAuto" data-role="slider" data-hidden-id="#autohidden">
            <option value="false">No</option>
            <option value="true">Yes</option>
        </select>
        @Html.HiddenFor(m => m.IsAuto, new { id = "#IsAuto", value="#IsAuto" })
        <input type ="hidden" name ="autorel" id="autorel" value="@(Model.IsAuto = "#IsAuto".AsBool())" />

None. However, it has several issues. Here it is, indented differently to avoid horizontal scroll:

    Auto

        :

    <select name="IsAuto"
            class="togglehidden"
            id="IsAuto"
            data-role="slider"
            data-hidden-id="#autohidden">
        <option value="false">No</option>
        <option value="true">Yes</option>
    </select>
    @Html.HiddenFor(m => m.IsAuto, new { id = "#IsAuto", value="#IsAuto" })
    <input
        type ="hidden"
        name ="autorel"
        id="autorel"
        value="@(Model.IsAuto = "#IsAuto".AsBool())" />

Where is the closing tag for div?
What do you use, XHTML or HTML5? In the first case, you should close img. In the second case, you shouldn't close the last input.
"#IsAuto".AsBool() always returns false, since "#IsAuto" is never equal to "true".
Why are you assigning a value to a property of your model in a view in the last line? Maybe you expected Model.IsAuto == ...?
An id of the hidden field which starts by # is weird.
If you care about naming conventions, m is a poor name for a variable. Basically, any person who have never used ASP.NET MVC before wouldn't be able to know that it refers to a model.
Given the actual syntax for the hidden field, wouldn't it be easier to simply write it in plain HTML?


Moving an element in a linked list Given I have a linked list, and I want to move a given node to the end of the list, is there a more elegant way of doing this, than what I've done here?

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int val;
  struct node *next;
} node_t;

void insert(node_t **head, int val)
{
  node_t *new_node = malloc(sizeof(node_t));
  node_t *tmp;

  new_node->val = val;
  new_node->next = NULL;

  // Empty list?
  if(*head == NULL) {
    *head = new_node;
    return;
  }

  tmp = *head;

  while(tmp->next != NULL)
    tmp = tmp->next;

  tmp->next = new_node;
}

void movetoend(node_t **head, int val)
{
  node_t *curr;
  node_t *tmp = NULL;
  node_t *old = NULL;

  // Find val in list
  for(curr = *head; curr != NULL; old = curr, curr = curr->next) {
    if(curr->val == val) {
      // Matched node is the only one in the list, don't do anything
      if(curr->next == NULL)
        return;

      // Matched node is first, set next to jump over
      if(old == NULL)
        *head = curr->next;

      // Matched node is in the middle, set next to jump over
      else
        old->next = curr->next;

      // Set a pointer to matched node for later use
      tmp = curr;

      // Loop through the rest of the list
      // "old" will have the pointer to last node
    }
  }

  // No matches?
  if(tmp == NULL)
    return;

  // Terminate list
  tmp->next = NULL;

  // Append matched node
  old->next = tmp;
}

void print(node_t *head)
{
  while(head) {
    printf("%d\n", head->val);
    head = head->next;
  }
}

int main()
{
  node_t *head = NULL;

  insert(&head, 10);
  insert(&head, 20);
  insert(&head, 30);
  movetoend(&head, 10);
  print(head);

  return 0;
}

EDIT: Added comments, modified movetoend function a bit slimmer.

There's more elegant ways, although not necessarily more efficient. The common idiom for fiddling with this kind of linked list in C is to add one more layer of indirection and fiddle with pointers-to-node-pointers, like this:

void insert(node_t **head, int val)
{
    node_t *new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = NULL;

    node_t **ptmp = head;
    while (*ptmp != NULL) {
        ptmp = &(*ptmp)->next;
    }
    *ptmp = new_node;
}

Given that example, I think you can figure out how to rewrite movetoend in just a few additional lines: much shorter than the page of code you have now.

However, whether this will be equally fast depends on your compiler and optimization levels. When in doubt, check the assembly code! If you see a lot of additional memory loads in the inner loop, that's a bad sign.

In C++, but I think not in C yet, you could eliminate even the appearance of extra memory loads by doing

void insert(node_t **head, int val)
{
    node_t *new_node = malloc(sizeof(node_t));
    new_node->val = val;
    new_node->next = NULL;

    node_t **ptmp = head;
    while (node_t tmp = *ptmp) {
        ptmp = &tmp->next;
    }
    *ptmp = new_node;
}


Unit tests for the SquishIt framework For a little background, I'm a contributor to SquishIt and decided that I should start cleaning up the mess of unit tests (my updated version of one set of tests vs. original set of tests). After tackling only part of the "rewrite", I figured it would be a good opportunity to learn, try, and understand BDD style testing to hopefully help improve the unit tests being written and ran. I decided to go with NSpec after taking a look at some of the choices out there.

My problem is simply trying to break the tests down into the appropriate "groupings" that logically make sense and "conform" to xSpec. Here is what I've done so far and passes all tests as expected:

using NSpec;
using SquishIt.Framework;
using SquishIt.Framework.JavaScript;

namespace SquishIt.Tests
{
    class describe_JavaScriptBundle : nspec
    {
        public JavaScriptBundle bundle;

        public void AddTest1JS()
        {
            bundle.Add("test.js");
        }
    }

    class when_I_create_a_bundle : describe_JavaScriptBundle
    {
        void before_each()
        {
            if (bundle == null)
            {
                bundle = Bundle.JavaScript();
            }
        }

        void and_add_no_files()
        {
            it["GroupBundles containskey default"] = () => bundle.GroupBundles.ContainsKey("default").is_true();
            it["has no Assets"] = () => bundle.GroupBundles["default"].Assets.Count.Is(0);
        }
    }

    class then_I_add_a_file : when_I_create_a_bundle
    {
        void before_each()
        {
            AddTest1JS();
        }

        void it_should_contain_only_one_file()
        {
            bundle.GroupBundles["default"].Assets.Count.Is(1);
        }
    }

    class then_I_add_the_same_file : then_I_add_a_file
    {
        void it_should_still_contain_only_one_file()
        {
            bundle.GroupBundles["default"].Assets.Count.Is(1);
        }
    }
}

How can I improve this or am I already on the right track?

Here is how I've written most of my NSpec tests, I usually start a context out with an act.  This dry's up the specification.  If I find myself doing too many "acts", I end up breaking it up into separate specifications.

class describe_JavaScriptBundle : nspec
{
    JavaScriptBundle bundle;

    void AddTest1JS()
    {
        bundle.Add("test.js");
    }

    void before_each()
    {
        bundle = Bundle.JavaScript();
    }

    void adding_a_bundle()
    {
        context["no files added"] = () =>
        {
            it["GroupBundle contains default key"] = () =>
                bundle.GroupBundles.ContainsKey("default").is_true();

            it["has no Assets"] () =>
                bundle.GroupBundles["default"].Assets.Count.Is(0);
        };

        context["adding one file"] = () =>
        {
            act = () => AddTest1JS();

            it["contains the file"] = () =>
                bundle.GroupBundles["default"].Assets.Count.Is(1);

            context["adding the same file again"] = () =>
            {
                act = () => AddTest1JS();

                it["should still only contain one file"] = () =>
                    bundle.GroupBundles["default"].Assets.Count.Is(1);
            };
        };
    }
}


Skiena's Programming Challenge [UVa ID 10137]- Getting WA Question from Skiena's Programming Challenges.
Getting WA (wrong answer) in Online Judge even though it's working for sample test cases. Can somebody find a case where it fails?

I tried the tricky case from this link and it gave the right answer-

"The Trip" challenge from Programming Challenges

Input

Standard input will contain the information for several trips. Each trip consists of a
line containing a positive integer n denoting the number of students on the trip. This is
followed by n lines of input, each containing the amount spent by a student in dollars
and cents. There are no more than 1000 students and no student spent more than
$10,000.00. A single line containing 0 follows the information for the last trip.

Output

For each trip, output a line stating the total amount of money, in dollars and cents,
that must be exchanged to equalize the students’ costs.

Sample Input
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

Sample Output
$10.00
$11.99

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

int main()
{   vector <float> nums;
    int numStudents,loopVar1,pos;
    float amount,sum=0,roundAmt,ans;
    string strAns;
    stringstream ss;
    while(cin>>numStudents) {
        if(numStudents==0)
            break;
        ans=sum=0;
        nums.erase(nums.begin(),nums.end());
        for(loopVar1=0;loopVar1<numStudents;loopVar1++) {
            cin>>amount;
            nums.push_back(amount);
            sum+=amount;
        }
        sum/=numStudents;
        roundAmt=(int)(sum*100);
        roundAmt/=100.0f;
        //cout<<roundAmt<<"\n";
        for(loopVar1=0;loopVar1<numStudents;loopVar1++)
            if(nums[loopVar1]<roundAmt)
                ans+=(roundAmt-nums[loopVar1]);
        strAns="";
        ss.str("");
        ss<<ans;
        strAns=ss.str();
        pos=strAns.find('.');
        if(pos==-1)
            strAns+=".00";
        else
            strAns.erase(pos+3);
        cout<<'$'<<strAns<<"\n";
    }
    return 0;
}

I did not run it (and I do not like to read it, too much abbreviations, wrong variable names, too less formatting), but what about this case:

  3
  1.01
  0.99
  0.99

sum will be 2.99 / 3 = 0.9966666...
roundAmt will be 0.99
ans will be 0
Obviously, it should be 0.01 to fulfill the requirement "so that the net cost to each is the same, to within one cent"

Beside this, please consider the things I mentioned in the beginning. Some concrete examples:

  sum/=numStudents;

This is not a sum anymore, it is the average.

  loopVar1

Take i, this is expected for a loop variable

  numStudents

Could be: number_of_students or numberOfStudents

for(loopVar1=0;loopVar1<numStudents;loopVar1++)

Could be: for (i = 0; i < number_of_students; ++i)

for(loopVar1=0;loopVar1<numStudents;loopVar1++)
            if(nums[loopVar1]<roundAmt)
                ans+=(roundAmt-nums[loopVar1]);

One could discuss if using the short form without brackets is ok for one line statements, but if it spans over multiple lines, please use brackets, even if it is syntactically ok.

what does roundAmt mean?

and so forth.


Query to find instances of two types of events occurring more than one second apart I have 3 tables on my database: BusinessObject and CustomEvent, and EventType. BusinessObject having a lot of columns, CustomEvent having the following:

Id
EventTypeId
DateEvent
CommentEvent
UserId
BusinessObjectId

I want to get all the BusinessObject having two CustomEvent with EventTypeId in (10, 11) such has the difference between the two DateEvent are more than 1 second. From the 6 first month of this year.

I came up with the following query but it's quite slow (~40 seconds). I assume there's a (lot of) ways to speed this up, but my SQL level is not good enough.

Here's the query:

select bo.Id
from BusinessObject bo
where
(
    select top 1 DATEDIFF(second,
                (select top 1 DateEvent from CustomEvent where EventTypeId = 11 and BusinessObjectid = bo.BusinessObjectId),
                (select top 1 DateEvent from CustomEvent where EventTypeId = 10 and BusinessObjectid = bo.BusinessObjectId))
    from CustomEvent ce inner join BusinessObject innerBO on ce.BusinessObjectId = bo.BusinessObjectId
    where EventTypeId = 11
        and innerBO.CreationDate < '20180701'
        and innerBO.CreationDate > '20180101'
        and innerBO.BusinessObjectId = bo.BusinessObjectId
) > 1

FYI, the query returns 4.138 rows. Here's the tables volumes:

BusinessObject  => 302k lines

CustomEvent => 4.326k lines

How could I speed this up?

I don't think your code is correct.

select top 1, without any kind of order by clause selects an essentially random record from a table, so unless you know that there can be only one event with the right EventTypeId you may be missing event combinations that are relevant.

If I understand the problem correctly, I think you need something more like this:

select A.BusinessObjectId from
( select BusinessObjectId, min(DateEvent) as min, max(DateEvent) as max
  from CustomEvent where EventTypeId = 11
  group by BusinessObjectId
) as A
inner join
( select BusinessObjectId, min(DateEvent) as min, max(DateEvent) as max
  from CustomEvent where EventTypeId = 10
  group by BusinessObjectId
) as B on A.BusinessObjectId = B.BusinessObjectId
where datediff( second, A.min, B.max ) > 1 or datediff( second, B.min, A.max ) > 1
group by A.BusinessObjectId

I have not included the six month restriction.


Exception handling calculate power I've to create a class MyCalculator which consists of a single method long power(int, int). This method takes two integers,  and, as parameters and finds Math.pow(n,p).
- If either n or p is negative, then the method must throw an exception which says "n or p should not be negative.".
- If both n and p are zero, then the method must throw an exception which says "n and p should not be zero."

class MyCalculator {
    /*
    * Create the method long power(int, int) here.
    */
    long power(int n, int p) throws Exception {
        if(n==0 && p==0) {
            throw new Exception("n and p should not be zero.");
        } else if(n<0 || p<0) {
            throw new Exception("n or p should not be negative.");
        } else {
            return (long)Math.pow(n, p);
        }
    }
}

Is there any way to use Exception handling in a better way in such questions? We have to perform this check in most of the questions. So I need to understand it clearly.

Is there any way to use Exception handling in a better way in such questions?

What you have is a very good start.

I would suggest refining your exception type where possible. In your case, I would suggest using IllegalArgumentException. Using a specific subtype helps with diagnosing/debugging.

Additionally, since IllegalArgumentException is a type of RuntimeException, you can then remove the throws Exception from your method signature.

long power(int n, int p) {
    if (n == 0 && p == 0) {
        throw new IllegalArgumentException("n and p should not be zero.");
    } else if (n < 0 || p < 0) {
        throw new IllegalArgumentException("n or p should not be negative.");
    }

    return (long) Math.pow(n, p);
}


Haskell: downpair :: (Monad m) => m (a, b) -> (m a, m b) implementation I'm trying to implement function downpairs which takes monad of pairs and transform it into pair of monad

My current implementation is

import Control.Monad
import Control.Arrow
import Data.Maybe

downpair :: (Monad m) => m (a, b) -> (m a, m b)
downpair = ((return . fst =<<) &&& (return . snd =<<))

main = do
    print $ downpair $ Just ("Hello", "World")

Is there way to implement downpair in more compact maner?

PS Sorry for my poor English

(return . fst =<<) can be replaced by fmap fst. Your definition then becomes

downpair = fmap fst &&& fmap snd


Bubble Sort in Objective-C Following is Objective-C method implementation I did for one of the most simplest sorting algorithms, Bubble Sort to sort an array of integers.

Note:- I have defined it as a static method in the SimpleAlgorithms class.

/**
 * When given jumbled or discending ordered array of integers, following bubble sort method will give you
 * an array ordered in ascending order.
 */
+ (NSArray *) bubbleSort:(NSArray *) arrayToBeSorted {
    // As we can't swap integers in a static array, make a mutable array out of the given static array.
    NSMutableArray *muArrRaw = [[NSMutableArray alloc] initWithArray:arrayToBeSorted];

    // iterate through the array as rounds
    for (int i = 0; i < [muArrRaw count]; i++) {
        // iterate through each element of the array with the given range
        for (int j = 0; j < [muArrRaw count] - i; j++) {
            // comparison
            if (j < ([muArrRaw count] - 1) && [[muArrRaw objectAtIndex:j] intValue] > [[muArrRaw objectAtIndex:(j + 1)] intValue]) {
                int temp = [[muArrRaw objectAtIndex:j] intValue];   // taken the value to be swapped first

                // then do the swapping
                [muArrRaw replaceObjectAtIndex:j withObject:[muArrRaw objectAtIndex:(j + 1)]];
                [muArrRaw replaceObjectAtIndex:(j + 1) withObject:[NSNumber numberWithInt:temp]];
            }
        }
    }

    // return the sorted array
    return [muArrRaw mutableCopy];
}

I call this method as follows:

NSArray *array = [[NSArray alloc] initWithObjects:[NSNumber numberWithInt:5], [NSNumber numberWithInt:3], [NSNumber numberWithInt:4], [NSNumber numberWithInt:1], [NSNumber numberWithInt:2], nil];
NSArray *sortedArray = [SimpleAlgorithms bubbleSort:array];

I know this seems to be silly for asking for improvements for something like this. But I like to find out even smallest improvements that we can made to this kind of things also because sometimes I might have done something stupid in the above implementation also. That's where we can embed power and value to the implementation.

So please give your suggestions and improvements to this Algorithm implementation.

I would be grateful if you can point out the improvements in the following areas:

Objective-C Language oriented improvements, reasoning and suggestions
Algorithm implementation techniques, simplifiable code lines.

Returning a mutable copy of the temporary array makes no sense to me,
perhaps you meant

return [muArrRaw copy];

to return an immutable array (as the return type of the method indicates).

The "proper" data type for array indices is NSUInteger, not int.

In

if (j < ([muArrRaw count] - 1) && [[muArrRaw objectAtIndex:j] intValue] > [[muArrRaw objectAtIndex:(j + 1)] intValue]) {

you can get rid of the extra check j < ([muArrRaw count] - 1) if the
outer loop starts with i = 1.

Also [muArrRaw objectAtIndex:j] can be shortened to muArrRaw[i],

for (NSUInteger i = 1; i < [muArrRaw count]; i++) {
    for (NSUInteger j = 0; j < [muArrRaw count] - i; j++) {
        if ([muArrRaw[j] intValue] > [muArrRaw[j + 1] intValue]) {
            // ...
        }
    }
}

Swapping two elements in the array can be simplified by using
the existing method:

[muArrRaw exchangeObjectAtIndex:j withObjectAtIndex:j+1];

If no elements were swapped at all in some pass then the array is
already sorted and there is no need to continue:

BOOL swapped;
NSUInteger n = [muArrRaw count];
do {
    swapped = NO;
    for (NSUInteger j = 0; j + 1 < n; j++) {
        if ([muArrRaw[j] intValue] > [muArrRaw[j + 1] intValue]) {
            [muArrRaw exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            swapped = YES;
        }
    }
    n--;
} while (swapped);

Your method is limited to arrays of integers. If you compare two
array elements with

if ([muArrRaw[j] compare:muArrRaw[j+1]] == NSOrderedDescending) { ... }

instead then it applies to all element types which have a compare:
method (e.g. NSNumber, NSString, NSDate ...).

Even more general, you can add a comparator argument, as suggested in this
answer:

My own method for sorting numbers in array


Method to draw an open or closed polyline I'm writing a simple 2D rendering class.

Below is the method that creates a polyline. A polyline can be closed or not according to a parameter closed.

void Polyline(IList<Point> points, bool closed)
{
    var pointsCount = points.Count;
    if (pointsCount < 2)
        return;

    int count = pointsCount;
    if (!closed)
        count = pointsCount - 1;

    for (int i1 = 0; i1 < count; i1++)
    {
        int i2 = (i1 + 1) == pointsCount ? 0 : i1 + 1;
        Point p1 = points[i1];
        Point p2 = points[i2];
        AddLineSegment(p1, p2);
    }
}

But I think the parameter name closed is a little confusing. It may have two different meanings:

points have already closed the polyline: points[0] == point[points.Count-1]
points doesn't close the polyline and we will add the first point to rendered polyline in the method

I want to make it clear to users that the second is the right meaning. So what kind of name should I use?

I think closesIt or something similar should be better but it still sounds ambiguous. What's your opinion?

A closed polyline is really a polygon. For clarity, why not just call it a polygon?  There is no point in trying to do too much in the same function. Not only would the calling code be clearer, the implementations would be simpler too, without the special cases.

void Polyline(IList<Point> points)
{
    var n = points.Count - 1;
    for (int i = 0; i < n; i++)
    {
        AddLineSegment(points[i], points[i + 1]);
    }
}

void Polygon(IList<Point> points)
{
    Polyline(points);
    if (points.Count >= 3)
    {
        AddLineSegment(points[points.Count - 1], points[0]);
    }
}


Player Rotation script This is my player rotation script. I just want to make sure my naming conventions are right. If there is any way to make this code more readable I'm open to suggestions. This is also my 3rd post about along the same line so please be brutal.

public class ShipRotation : MonoBehaviour
{
    [SerializeField] Canvas canvas;
    ShipManager shipControls;
    GameObject ship;
    DebugController debugController;
    Camera shortHandCamera;
    [SerializeField] GameObject mainCamera;
    float distFromCamera;

    void Start()
    {
        shortHandCamera = Camera.main;
        shipControls = GetComponent<ShipManager>();
        debugController = canvas.GetComponent<DebugController>();
        ship = GameObject.Find("Player");
        distFromCamera = Mathf.Abs(mainCamera.transform.position.z);
        target = new Vector3(0f, 2f, ship.transform.position.z);
    }

    enum StateOfRotation
    {
        waiting,
        rotating
    }

    public LayerMask touchInputMask;
    Vector3 target;
    void Update()
    {
        foreach (Touch touch in Input.touches)
        {
            Ray ray = Camera.main.ScreenPointToRay(touch.position);
            RaycastHit hit;
            if (!Physics.Raycast(ray, out hit, touchInputMask)) { continue; }

            GameObject recipient = hit.transform.gameObject;
            if (recipient.tag != "Player")
            {
                target = Camera.main.ScreenToWorldPoint(new Vector3(touch.position.x, touch.position.y, ship.transform.position.z + distFromCamera));
            }
        }
        ship.transform.LookAt(target);
        debugController.ChangeText(6, target.ToString());
    }
}

A couple of quick minor points:

Try not to abbreviate names, characters cost you nothing.

float distFromCamera

should be renamed to:

float distanceFromCamera

Names should relate to what they are ShipManager shipControls is it a "Manager" or a set of controls? The type name doesn't match the variable name in my opinion. As an aside, I generally dislike ***Manager as a name (and I'm not the only one);

Enum members should be PascalCase:

enum StateOfRotation
{
    Waiting,
    Rotating
}

It is nicer to put all of your fields at the top of your file. You have some mixed in between method definitions.

I prefer explicit access modifiers on everything. e.g. private float distanceFromCamera. In Unity, with the whole public field thing, it can make the class easier to skim as well.


Error Trapping for dialog box reply How can I improve upon this code to apply logic based on the user's response to a SaveAs Dialog Box 'do you want to overwrite existing file' question:

Sub SaveFile(fName As String)

cancelSave = False
Retry:
saveAsFileName = Application.GetSaveAsFilename(InitialFileName:=fName, FileFilter:="Excel Files (*.xlsx), *.xlsx")
If saveAsFileName <> False Then
    If Not Dir(saveAsFileName) <> vbNullString Then
        ActiveWorkbook.SaveAs fileName:=saveAsFileName
    Else
        On Error Resume Next
        ActiveWorkbook.SaveAs fileName:=saveAsFileName, FileFormat:=xlWorkbook, ConflictResolution:=xlLocalSessionChanges
        If Err.Number = 1004 Then
            On Error GoTo 0
            GoTo Retry
        Else
            On Error GoTo 0
        End If
    End If
Else
    cancelSave = True
End If

End Sub

It might be a personal preference, but I find indenting the entire procedure body massively helps making a module easier to read - the only thing that's left in column 1 is module-level declarations, procedure signatures, and line labels. Conversely, not indenting the entire procedure body makes it harder to tell which procedure starts/ends where in a module.

Sub SaveFile(fName As String)

The procedure is implicitly Public, which makes it hard to tell whether it's meant to be used in the same module, or if it's meant to be called by code outside the module. If it's meant to be used in the same module, make it Private. If not, make it explicitly Public.

The fName parameter is implicitly passed ByRef, which means if SaveFile reassigns the parameter, the new value will be visible at the call site. If that's intentional, an explicit ByRef modifier should be there. Given the parameter isn't reassigned in the body of the procedure, it should be passed ByVal.

It's not clear how the procedure is used, but it seems cancelSave is declared outside the procedure. If it's in the same module, it should be Private. If it's in another module, then it's Public and you have a global variable... and in all likelihood (assuming SaveFile is called from some BeforeSave event handler) it could be avoided by making the procedure a Function that returns a Boolean:

Public Function SaveFile(ByVal fName As String) As Boolean

I strongly doubt you actually need a global variable for this.

The procedure feels wrong, because error-handling logic is intertwined with the actual procedure logic; these On Error and GoTo statements obscure the intent of the code.

Typically, error-handling is done in a dedicated subroutine, and no GoTo statement is needed - you want to run some logic in a loop until the user cancels out; it's much clearer if you use one of VBA's many loop structures instead of implementing that GoTo-loop.

Let's take a moment to consider this alternative implementation:

Public Function SaveFile(Optional ByVal initialPath As String = vbNullString) As Boolean
    On Error GoTo CleanFail
    Dim cancelSaveHandler As Boolean

    Dim completed As Boolean
    While Not completed

        Dim result As Variant
        result = Application.GetSaveAsFileName(InitialFileName:=initialPath, FileFilter:="Excel Files (*.xlsx), *.xlsx")

        If VarType(result) = vbBoolean Then
            'cancelling GetSaveAsFileName dialog returns False:
            cancelSaveHandler = True
            completed = Not result
        'ElseIf Dir(result) = vbNullString Then
        '    'selected file doesn't exist, try saving:
        '    ActiveWorkbook.SaveAs FileName:=result, FileFormat:=xlWorkbook, ConflictResolution:=xlLocalSessionChanges
        Else
            ActiveWorkbook.SaveAs result
        End If

    Wend

    SaveFile = cancelSaveHandler
    Exit Function

CleanFail:
    completed = (MsgBox("An unexpected error has occurred while saving. Try again?", vbYesNo + vbExclamation) = vbNo)
    Resume Next
End Function

Notice:

The parameter is Optional, because it's not really required; it's also named in a way that doesn't suggest that that's the name we're saving the file with.
The loop is explicit; there's no GoTo jump.
The error-handling logic is completely separated from the procedure's actual logic.
Error handling doesn't leave unexpected errors dangling unhandled, and only ever runs when a runtime error happens.
No implicit conversion from Variant/String or Variant/Boolean when evaluating whether the GetSaveAsFileName dialog was cancelled.
No more double-negative when checking if the file exists.
Checking if the file exists is redundant if we're going to save either way; xlWorkbook is the default format anyway, and what's wrong with prompting for conflict resultion (the default behavior) if/when applicable?
User knows what's happening and why, at all times.
We're returning a value to the caller instead of assigning a global variable: there are no side-effects to global state.

In an ideal world, there would also be a VB_Description attribute, to describe what the function does:

Attribute SaveFile.VB_Description = "Prompts user for a non-existing file name and saves the active workbook. Returns True if 'BeforeSave' handler should be cancelled."

You can set this procedure attribute via the Object Browser, by browsing to the function, right-clicking, selecting "Properties" in the context menu, and entering a value in the "Description" box. That description will then be visible in the Object Browser:

Ideally all public members should have a description.


Implementation of resizable array (Vector or ArrayList) in C I've implemented a very simple resizable integer array in C, only including functionality to add and remove elements at various indexes.

I haven't looked at using void pointers to handle any type of data yet. I'm mainly wondering if my structure of the code is okay, with the header file containing external API details and the source file hiding away implementation detail.

vector.h

#ifndef VECTOR_H
#define VECTOR_H

typedef struct vector_struct* Vector;

extern Vector vector_create();
extern void vector_destroy(Vector vector);
extern void vector_add(Vector vector, int* element);
extern void vector_add_index(Vector vector, int* element, int index);
extern void vector_remove(Vector vector, int index);
extern void vector_pop(Vector vector);
extern void vector_print(Vector vector);

#endif

vector.c file:

#include "vector.h"
#include <stdlib.h>
#include <stdio.h>

struct vector_struct {
  int capacity;
  int number_of_elements;
  int* elements;
};

/*
Private function to allocate memory for vector creation
*/
static void* get_memory(size_t size) {
  void* memory;
  if ((memory = malloc(size)) == NULL) {
    exit(EXIT_FAILURE);
  }
  return memory;
}

/*
Private function to resize the amount of memory allocated for the given vector
*/
static void resize_vector(Vector vector, size_t size) {
  if ((vector->elements = realloc(vector->elements, size)) == NULL) {
    exit(EXIT_FAILURE);
  }
  vector->capacity = size / sizeof(int);
}

/*
Create and initialize a vector for use
*/
extern Vector vector_create() {
  Vector vector = get_memory(sizeof(Vector));

  vector->capacity = 10;
  vector->number_of_elements = 0;
  vector->elements = get_memory(sizeof(int) * 10);

  return vector;
}

/*
Free memory allocated for vector
*/
extern void vector_destroy(Vector vector) {
  free(vector->elements);
  free(vector);
}

/*
Add given element to the end of the vector
*/
extern void vector_add(Vector vector, int* element) {
  if (vector->number_of_elements+1 > vector->capacity) {
    resize_vector(vector, (vector->capacity * 2) * sizeof(int));
  }

  vector->elements[vector->number_of_elements] = *element;
  vector->number_of_elements++;
}

/*
Add given element at the given index in the vector
*/
extern void vector_add_index(Vector vector, int* element, int index) {
  if (index < 0 || index >= vector->number_of_elements) {
    exit(EXIT_FAILURE);
  }

  if (vector->number_of_elements+1 > vector->capacity) {
    resize_vector(vector, (vector->capacity * 2) * sizeof(int));
  }

  for(int i=vector->number_of_elements; i>index; i--) {
    vector->elements[i] = vector->elements[i-1];
  }

  vector->elements[index] = *element;
  vector->number_of_elements++;
}

/*
Removes element at given index, shifting all elements after that index
to the left once in order to fill in the empty index
*/
extern void vector_remove(Vector vector, int index) {
  if (index < 0 || index >= vector->number_of_elements) {
    exit(EXIT_FAILURE);
  }

  for(int i=index; i<vector->number_of_elements-1; i++) {
    vector->elements[i] = vector->elements[i+1];
  }
  vector->number_of_elements--;

  if (vector->number_of_elements < (vector->capacity / 2)) {
    resize_vector(vector, (vector->capacity / 2) * sizeof(int));
  }
}

/*
Removes the last element in the vector
*/
extern void vector_pop(Vector vector) {
  if (vector->number_of_elements < 1) {
    exit(EXIT_FAILURE);
  }

  vector->number_of_elements--;
}

/*
Prints the vector's contents
*/
extern void vector_print(Vector vector) {
  printf("Capacity of vector: %d\nContents:\n", vector->capacity);
  printf("[");
  for (int i=0; i<vector->number_of_elements; i++) {
    printf((i == vector->number_of_elements-1) ? " %d " : " %d,", vector->elements[i]);
  }
  printf("]\n");
}

Do not typedef a pointer.
exit on a bad index is a bit too harsh. Consider returning a success/failure indication instead.
vector->capacity *= 2 and vector->capacity /= 2 embody the reallocation policy. It doesn't feel right that this policy is spread across many functions. I recommend to consolidate it in a single function (resize_vector is a good candidate), and call it unconditionally with the desired new size.
number_of_elements is not exposed to the client. It means that the client cannot iterate over the vector elements, which severely limits the utility of the array. Either expose it, or provide a mapping interface, along the lines of

typedef (*op)(int, void *);
.... map(Vector vector, op, int, void *);

(the void * argument to share a state across the op invocations).


Self-mutating C (x86_64) As a learning exercise I wrote a short C program that changes the instructions of a function at runtime in order to execute a shell. It's obviously dependent on x86_64 architecture and Linux (for the syscall number). Indeed, it does start a shell when I run it. I was told to post it here by someone on StackOverflow so what I'm wondering is if there is anything that I'm overlooking in the overall concept or if anything can be improved?

For the sake of brevity, below is only the final product. I wrote up a much longer explanation of the whole process on my blog, but I'm only concerned about the code below, not my long explanation of it.

#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <sys/mman.h>

void foo(void);
int change_page_permissions_of_address(void *addr);

int main(void) {
    void *foo_addr = (void*)foo;

    // Change the permissions of the page that contains foo() to read, write, and execute
    // This assumes that foo() is fully contained by a single page
    if(change_page_permissions_of_address(foo_addr) == -1) {
        fprintf(stderr, "Error while changing page permissions of foo(): %s\n", strerror(errno));
        return 1;
    }

    puts("Calling foo");
    foo();

    char shellcode[] =
        "\x48\x31\xd2"                              // xor    %rdx, %rdx
        "\x48\x31\xc0"                              // xor    %rax, %rax
        "\x48\xbb\x2f\x62\x69\x6e\x2f\x73\x68\x00"  // mov    $0x68732f6e69622f2f, %rbx
        "\x53"                                      // push   %rbx
        "\x48\x89\xe7"                              // mov    %rsp, %rdi
        "\x50"                                      // push   %rax
        "\x57"                                      // push   %rdi
        "\x48\x89\xe6"                              // mov    %rsp, %rsi
        "\xb0\x3b"                                  // mov    $0x3b, %al
        "\x0f\x05";                                 // syscall

    // Careful with the length of the shellcode here depending on what is after foo
    memcpy(foo_addr, shellcode, sizeof(shellcode));

    puts("Calling foo");
    foo();

    return 0;
}

void foo(void) {
    int i=0;
    i++;
    printf("i: %d\n", i);
}

int change_page_permissions_of_address(void *addr) {
    // Move the pointer to the page boundary
    int page_size = getpagesize();
    addr -= (unsigned long)addr % page_size;

    if(mprotect(addr, page_size, PROT_READ | PROT_WRITE | PROT_EXEC) == -1) {
        return -1;
    }

    return 0;
}

There's one small bug in your code here:

memcpy(foo_addr, shellcode, sizeof(shellcode));

This copies the contents of shellcode, but being a string literal, shellcode includes a null terminator and sizeof(shellcode) is equal to 30, not 29. You should replace this line with:

memcpy(foo_addr, shellcode, sizeof(shellcode) - 1);


Very slow Python Combination Generator I have the following function:

from collections import Counter

import itertools

def combinationsWithMaximumCombinedIntervals(data, windowWidth, maximumCombinedIntervals):

    for indices in itertools.combinations(range(len(data)),windowWidth):
        previous = indices[0]
        combinedIntervals = 0
        for i in indices[1:]:
            combinedIntervals = combinedIntervals + i-previous-1
            if combinedIntervals > maximumCombinedIntervals:
                break
            previous = i
        else:
            yield(tuple(data[i] for i in indices))

test = ["a","b","c","d","e","f","g","h","i","j","k","l"]
combinations = combinationsWithMaximumCombinedIntervals(test, 5, 2)

for i in combinations:
    pass

The function is associated with a set of combinations for the data supplied to it. Each element in the list represents a combination with the length of each of these combinations equal to windowLength.

If we take the flowing combination ("a","b","c","d","f"), then the combined interval is 1 since "d" to "f" is a hop of 1. If we take the flowing combination ("a","b","c","e","g"), then the combined interval is 2 since "c" to "e" and "e" to "g" are hops of 1 each. Finally, combination ("a","b","c","d","g") has a combined interval of 2 since "d" to "g" is a hop of 2. The maximumCombinedIntervals argument limits the number of combinations based on the combined interval. In other words, this combination is not available when maximumCombinedIntervals is 2: ("a","c","e","f","h") since the combination of hops is now greater than 2.

I wish to run this function on data with a length of many thousands, a windowWidth in the order of 10 and a maximumCombinedIntervals under 10. However this takes forever to execute.

Can anyone suggest how I might refactor this function so that it will run much more quickly in Python. itertools.combinations is implemented in C.

Here is a similar function which I'm also interested in using:

def combinationsWithMaximumIntervalSize(data, windowWidth, maximumIntervalSize):
    maximumIntervalSizePlusOne = maximumIntervalSize+1

    for indices in itertools.combinations(range(len(data)),windowWidth):
        previous = indices[0]
        for i in indices[1:]:
            if i-previous>maximumIntervalSizePlusOne:
                break
            previous = i
        else:
            yield(tuple(data[i] for i in indices))

I'm working in python 3.

Edit: Here's my latest attempt. Any comments?

def combinationsWithMaximumCombinedIntervals2(data, combinationWidth, maximumCombinedIntervals):

    windowWidth = combinationWidth + maximumCombinedIntervals

    combinations = []

    for startingIndex in range(len(data)-windowWidth+1):
        for indices in itertools.combinations(range(startingIndex, startingIndex+windowWidth), combinationWidth):
            if not indices in combinations:
                yield(tuple(data[j] for j in indices))
                combinations.append(indices)

As for your actual algorithm, you need to change it. Filtering down python's generating makes things relatively simple. However, in this case you are going throw away way more items then you keep. As a result, this isn't going to be an efficient method.

What I'd try is iterating over all possible starting positions. For each starting position I'd take the next windowWidth+maximumIntervalSize items. Then I'd use itertools.combinations to grab each possible set of maximumIntervalSize items to remove from the list.

EDIT

Review of new code:

def combinationsWithMaximumCombinedIntervals2(data, combinationWidth, maximumCombinedIntervals):

The python style guide recommends lowercase_with_underscores for function and parameter names. The name are also just a bit on the longish side. (Which is way better then being too short or cryptic)

    windowWidth = combinationWidth + maximumCombinedIntervals

    combinations = []

    for startingIndex in range(len(data)-windowWidth+1):
        for indices in itertools.combinations(range(startingIndex, startingIndex+windowWidth), combinationWidth):

If possible, try to avoid looping over indexes. Code is cleaner if it loops over the data elements.

            if not indices in combinations:

You use if indices not in combinations for a slightly cleaner expression

                yield(tuple(data[j] for j in indices))

You don't need the parenthesis for yield, it is a statement not a function.

                combinations.append(indices)

Combinations would be faster to check if it were a set rather then a list.

But the real question here is how to avoid the duplicates being generated in the first place. We simple restrict the combinations generated to include the startingIndex. This prevents duplicates because no later window can produce the same combinations. (They don't have the startingIndex in them). But it still produces all values because all combinations without the startingIndex will still be contained in the next window. (The next window is the current window except without startingIndex and with an additional value) The only tricky part is the end, when there are no more windows. This is most easily handled by continuing to generate just with a smaller window size for as long as possible.

My solution (tested to make sure it produces the same results as yours, so I don't make any more silly mistakes):

def combinationsWithMaximumCombinedIntervals3(data, combinationWidth, maximumCombinedIntervals):
    windowWidth = combinationWidth + maximumCombinedIntervals

    for startingIndex in range(len(data)-combinationWidth+1):
        window = data[startingIndex + 1: startingIndex + windowWidth]
        for indices in itertools.combinations(window, combinationWidth - 1):
            yield (data[startingIndex],) + indices


Shortest distance for points in a plane I was wondering how I can make this code more pythonic. More professonal-looking and more readable. The code runs perfectly fine.

# Uses Python 3
"""
Finds the closest pair of point from a set of points on a plane
by brute-force (O(n^2)) and divide-and-conquer algorithms (O(nlog(n))).
Input: x,y coordinates (float)
Output: minimum distance (float)& closest pair (complex number)
@ Author: RA
"""

import sys

# Brute force algorithm.

def brute_force(xpoints):  # px will be passed to the function
    n = len(xpoints)
    if n < 2:
        return float('inf'), (None, None)
    else:
        sep = float('inf')  # set the initial minimum to infinity
        pair = ()
        for i in range(n - 1):
            for j in range(i + 1, n):
                if abs(xpoints[i] - xpoints[j]) < sep:
                    sep = abs(xpoints[i] - xpoints[j])
                    pair = (xpoints[i], xpoints[j])

    return sep, pair

# Divide and Conquer

def divide_n_conquer(xpoints, ypoints):
    n = len(xpoints)
    if n <= 3:
        return brute_force(xpoints)

    xmedian = int(n / 2)

    yl, yr = [], []
    for p in ypoints:
        if p.real < xpoints[xmedian].real:
            yl.append(p)
        else:
            yr.append(p)

    (l_sep, l_pair) = divide_n_conquer(xpoints[:xmedian], yl)
    (r_sep, r_pair) = divide_n_conquer(xpoints[xmedian:], yr)

    (sep, pair) = (l_sep, l_pair) if l_sep < r_sep else (r_sep, r_pair)

    sep_strip, pair_strip = split(xpoints, ypoints, sep)

    if sep_strip < sep:
        sep = sep_strip
        pair = pair_strip

    return sep, pair

def split(xpoints, ypoints, sep):
    xdivider = xpoints[int(len(xpoints)/2)].real
    ystrip = [item for item in ypoints if
              abs(item.real - xdivider).real < sep]

    ns = len(ystrip)  # Number of points in the strip
    sep = float('inf')
    pair = ()
    if ns > 1:

        for i in range(ns - 1):
            for j in range(i + 1, min(i + 8, ns)):
                if abs(ystrip[i] - ystrip[j]) < sep:
                    sep, pair = abs(ystrip[i] - ystrip[j]), (ystrip[i], ystrip[j])

    return sep, pair

if __name__ == '__main__':
    _input = sys.stdin.read()
    data = list(map(int, _input.split()))
    n = data[0]
    x = data[1::2]
    y = data[2::2]
    p = [complex(x, y) for x, y in zip(x, y)]
    px = sorted(p, key=lambda p: p.real)  # points sorted by x
    py = sorted(p, key=lambda p: p.imag)  # points sorted by y
    print("{0:.9f}".format(divide_n_conquer(px, py)[0]))

Just reviewing brute_force.

There's no docstring.
There's no need to write comments if they just repeat what it says in the code:

sep = float('inf')  # set the initial minimum to infinity

Use comments to explain things that are hard to deduce from reading the code.
The special case for n < 2 is unnecessary. If n is less than 2, then the loop over i will be empty and no pairs will be tested.
There are some superfluous parentheses. In Python the comma operator has higher precedence than assignment, and so, instead of:

pair = (xpoints[i], xpoints[j])

you can write:

pair = xpoints[i], xpoints[j]

The expression abs(xpoints[i] - xpoints[j]) gets computed twice in some cases: this could be avoided by storing the result in a local variable.
When looping over the distinct pairs of a sequence, use itertools.combinations, like this:

from itertools import combinations

def brute_force(points):
    """Find the pair (p, q) in the sequence points with the closest
    separation. Return the tuple (separation, (p, q)).

    """
    sep = float('inf')
    pair = None, None
    for p, q in combinations(points, 2):
        pq_sep = abs(p - q)
        if pq_sep < sep:
            sep = pq_sep
            pair = p, q
    return sep, pair

This could be turned into a single expression using min and operator.itemgetter:

from itertools import combinations
from operator import itemgetter

def brute_force(points):
    """Find the pair (p, q) in the sequence points with the closest
    separation. Return the tuple (separation, (p, q)).

    """
    return min(((abs(p - q), (p, q)) for p, q in combinations(points, 2)),
               key=itemgetter(0), default=(float('inf'), (None, None)))

(This needs to be Python 3.4 or later since it uses the default keyword argument.)

Not everyone finds this style of programming readable, so it would be totally reasonable to stop with the version in §6 above and not try to squash everything into a single expression.


Display resources for each factory in the Rocket Valley Tycoon I'm new here. I'm trying to teach myself programming by learning Python. I have assigned myself the following task.

There's a game I'm playing (Rocket Valley Tycoon) where the goal is to basically place an Extractor to gather resources, then use Factories to transform the resource into a good, which then usually gets processed again by another Factory into a processed good.

The point of the program I'm trying to write is to be able to see the resources needed for any Factory. So, for example, Copper plates need 10 carbon and 20 copper ore, and at the same time, the carbon needs 2 coal and 4 water, so I would like the final output to be something like:

Copper plates need 20 copper ore, 20 coal, and 40 water. I have a working prototype, that works with just this, but if I know it can be simplified somehow. (Especially in the print_total function)

Also, this only works with a Factory that has just one "child" Factory and not with n "child" Factories. This is the first tech tree:

Can someone please point me in the right direction?

class Factory:

    def __init__(self, name, ing1, amount1, ing2=None, amount2=None):
        self.name = name
        self.ing1 = ing1
        self.amount1 = amount1
        self.ing2 = ing2
        self.amount2 = amount2
        self.total_amount1_1 = None
        self.total_amount1_2 = None
        self.total_amount2_1 = None
        self.total_amount2_2 = None
        self.total_ing1_ing1 = None
        self.total_ing1_ing2 = None
        self.total_ing2_ing1 = None
        self.total_ing2_ing2 = None

    def print_ing(self):
        print(self.name + ' needs: ')
        print(self.amount1, self.ing1.name, self.amount2, self.ing2.name)

    def print_total(self):
        if isinstance(self.ing1, Factory):
            print('Ing1 is Factory')
            self.total_ing1_ing1 = self.ing1.ing1
            self.total_ing1_ing2 = self.ing1.ing2
            self.total_amount1_1 = self.amount1 * self.ing1.amount1
            self.total_amount1_2 = self.amount1 * self.ing1.amount2
        elif isinstance(self.ing2, Factory):
            print('Ing2 is Factory')
            self.total_ing2_ing1 = self.ing2.ing1
            self.total_ing2_ing2 = self.ing2.ing2
            self.total_amount2_1 = self.amount2 * self.ing2.amount1
            self.total_amount2_2 = self.amount2 * self.ing2.amount2
        print(self.name + ' needs: ')
        print(self.amount1, self.ing1.name, self.total_amount2_1,
              self.total_ing2_ing1.name, self.total_amount2_2,\
              self.total_ing2_ing2.name)

class Extractor:
    def __init__(self, name):
        self.name = name

coal = Extractor('Coal')
water = Extractor('Water')
copper_ore = Extractor('Copper Ore')
carbon = Factory('Carbon', coal, 2, water, 4)
copper_plates = Factory('Copper Plates', copper_ore, 20, carbon, 10)

I would turn this into one class that takes a list of ingredients and cost tuples. The resulting object can be added with another of its instance or multiplied with a number.

from collections import defaultdict

class Ingredient:

    def __init__(self, *ingredients):
        self.d = defaultdict(int)
        if len(ingredients) == 1 and isinstance(ingredients[0], str):
            # special case for base ingredients
            self.d[ingredients[0]] = 1
        else:
            for ingredient, amount in ingredients:
                self.d[ingredient] += amount

    @property
    def ingredients(self):
        return list(self.d.keys())

    @property
    def amounts(self):
        return list(self.d.values())

    def __rmul__(self, other):
         # allows doing other * self, where other is a number
        return Ingredient(*zip(self.ingredients, [other * x for x in self.amounts]))

    def __add__(self, other):
        # allows self + other, where other is another Ingredient
        return Ingredient(*zip(self.ingredients + other.ingredients,
                               self.amounts + other.amounts))

    def __str__(self):
        return str(list(self.d.items()))

Then you can define the base items and any derived item is just algebraic manipulations:

coal = Ingredient("Coal")
water = Ingredient("Water")
copper_ore = Ingredient("Copper Ore")
carbon = 2 * water + 4 * coal
copper_plates = 20 * copper_ore + 10 * carbon
print(copper_plates)
# [('Copper Ore', 20), ('Water', 20), ('Coal', 40)]


Processor that would process an Object (say a message you received) Sorry for being a little abstract but I have attempted to concoct something simple but it seems to spiral out of control. So I was thinking maybe I am taking the wrong approach.

Here's what I am trying to do:

  When I get a message it gets de-serialized into its own class. I would like to use a strategy pattern to choose a message processor that would be able to process the message

How would you do it?

Here are my attempts at this that got very convoluted the closer I got to the goal. I mean, it works but I would have thought it would be cleaner than this so just thinking I must be going about this wrong:

https://stackoverflow.com/questions/35801156/cant-seem-to-get-generic-covariance-contravariance-to-work
https://stackoverflow.com/questions/35784981/why-is-thisinterfacet-not-of-type-interfacet-using-an-is-keyword-comparison
https://stackoverflow.com/questions/35777762/cant-convert-from-abstractgeneric-to-concreteabstractconcretegeneric

Here's my code (but I am looking for ideas to avoid the MessageProcessorWrapper). How would you re-write it?:

public interface IBaseMessage {
   public int ID() { get; set; }
}

public interface IMessageProcessor<in T> where T : IBaseMessage {
            void Process(T msg);
        }

public class RRMessage : IBaseMessage {
          public string Text {get; set;}
          public DateTime RRProcessDate {get; set; }
        }

public class BaseMessageProcessor {
         public int MessageProcID{ get; set; }
         public BaseMessageProcessor(int mid) {
            MessageProcID = mid;
         }
      }

public class RRMessageProcessor : BaseMessageProcessor, IMessageProcessor<RRMessage> {
            public void Process(RRMessage msg) {
                WriteToDatabase(msg);
                UpdateInternalTrackers(msg);
                Console.WriteLine("Processed RRMessage");
            }
        }

public class ProcessorWrapper<T> : IMessageProcessor<IBaseMessage> {
    private readonly IMessageProcessor<T> inner;
    public ProcessorWrapper(IMessageProcessor<T> inner) { this.inner = inner; }

    public void Process(IBaseMessage msg)
    {
        if(msg is T) { inner.Process((T)msg); }
        else throw new ArgumentException("Invalid message type");
    }
}

[TestFixture]
public class MyTestFixture {
    public Dictionary<Type, IMessageProcessor<IBaseMessage>> MessageProcessors = new Dictionary<Type, IMessageProcessor<IBaseMessage>>();

    [Test]
    public void Test1() {
         var msgProcessor = new RRMessageProcessor();
         MessageProcessors.Add(typeof(RRMessage), new ProcessorWrapper<RRMessage>(msgProcessor);
         }
   }

Not the answer you're looking for, but this bit of code casts msg twice: if(msg is T) { inner.Process((T)msg); }. You can cast it once by using as, e.g. var m = msg as T; if (m != null) inner.Process(m); Also if you're actually writing the if bit on one line (as I love to do for one-liners) then I don't see the point of using curly braces on that line, though I guess that's just a style issue. You didn't use it for the else part after all.

And I'm sure in "real life" you won't have a test called "Test1", so I won't say anything about that...


Uploading an input file to a web server I have a long-running task that processes an input file and then uploads it to a web server. The processing part can be interrupted (with cleanup) but the upload shouldn't be interruptable so that we know whether the server received the file correctly.

My thread looks like this (I'm using PyQt but I imagine this problem occurs in other threading modules too):

class ImportThread(QtCore.QThread):
    def __init__(self, path):
        super(ImportThread, self).__init__()

        self.path = path
        self.stopped = False

    @property
    def stopped(self):
        return self._stopped

    @stopped.setter
    def stopped(self, stopped):
        self._stopped = stopped

    def run(self):
        self.emit(QtCore.SIGNAL("processing()"))

        # Do the processing task unless the thread has already been stopped
        if not self.stopped:
            do_processing_task()

            # Don't move on to the next step if the thread has been stopped
            if not self.stopped:
                self.emit(QtCore.SIGNAL("uploading()"))
            else:
                cleanup_processed_file()
                return   # Exit thread

        do_upload_task()
        self.emit(QtCore.SIGNAL("completed()"))

I don't think the nested ifs are very readable and am looking for a way to clean this up. Any suggestions?

Usage looks a little like this:

# triggering thread
self.thread = ImportThread(path)
# ... connects() to thread signals that update the progress dialog ...
self.thread.start()

# Create a progress dialog to monitor the thread
self.progress = QtGui.QProgressDialog("Starting...", "Cancel", 0, 2, self)
self.progress.setValue(0)
self.progress.show()

# Connect cancellation signal from progress dialog to method to stop the thread
self.connect(self.progress, QtCore.SIGNAL("canceled()"), self.notify_cancelled)

def notify_cancelled(self):
    self.progress.setLabelText("Cancelling...")
    self.thread.stopped = True
    self.thread.exit()    # Not sure this is correct?
    self.progress.close()

The code itself is readable: it makes sense to check if the thread is still running before doing extra work. It's not the usual if spaghetti, and is, I think, a common threading idiom. But it's hard to understand the logic behind the code and I'm not sure it works as intended.

The first issue is that you're emitting the uploading signal only when processing has been done, but it's theoretically possible that upload happens even without processing, if the first if not self.stopped is false. If you don't want this to happen, I suggest that you move the do_upload_task() call in the second if not self.stopped.

The second issue is that it's very unlikely that self.stopped would be false just after run() has started, so this does not make much sense and suggests you don't really have a valid mental model for threads.

Now, concerning notify_cancelled, you have two (invalid) options:

either you simply set stopped to True, which can only have an effect when the thread goes through your if not self.stopped statements, so it won't interrupt the processing: you don't want that.
either you also self.thread.exit(), but this is can interrupt both the processing and the upload... and you don't want that either.

What I would do is having a processing thread and an uploading thread: you could exit() the first one, but not the other one.


DBSCAN in C++ for general and Android use I've implemented a templated DBSCAN for general use. At the moment, it's going to be used on Android through the JNI. I used Wikipedia's pseudocode and a little bit of the DBSCAN paper for reference. It's pretty naive, so I'm wondering how I can speed it up, and what I can do to make it perform reasonably well on a phone. How can I improve my code?

template <typename T>
    struct node {
        T val;
        bool visited;
        bool clustered;
        node() : visited(false), clustered(false) {}
    };

    template <typename T>
    using cluster = std::vector<T>;

    template <typename T>
    using adj_list = std::list<node<T>*>;

    template <typename T>
    using graph = std::map<node<T>*, adj_list<T>>;

    template <typename T>
    std::vector<cluster<T>> DBSCAN(T* const& dataset, size_t const& dataset_size, double const& eps, size_t const& min_pts, double(*distance_function)(T const& lhs, T const& rhs)) {

        std::vector<node<T>> node_list(dataset_size);
        for (auto i = 0; i < dataset_size; ++i) {
            node_list[i].val = dataset[i];
        }

        graph<T> g;
        for (auto i = 0; i < node_list.size(); ++i) {
            for (auto j = 0; j < i; ++j) {
                if (distance_function(node_list[i].val, node_list[j].val) < eps) {
                    g[&node_list[i]].push_back(&node_list[j]);
                    g[&node_list[j]].push_back(&node_list[i]);
                }
            }
        }

        std::vector<cluster<T>> clusters;
        cluster<T> C;
        for (node<T>& n : node_list) {
            if (n.visited) continue;
            n.visited = true;
            adj_list<T> neighbour_pts = g[&n];
            if (neighbour_pts.size() >= min_pts) {
                expandCluster(n, neighbour_pts, C, g, min_pts);
                clusters.push_back(C);
                C = cluster<T>();
            }
        }

        return clusters;
    }

    template <typename T>
    void expandCluster(node<T>& point, adj_list<T>& neighbourhood, cluster<T>& C, graph<T>& g, unsigned const& min_pts) {
        C.push_back(point.val);
        point.clustered = true;
        for (node<T>*& n : neighbourhood) {
            if (!n->visited) {
                n->visited = true;
                adj_list<T> next_neighbourhood = g[n];
                if (next_neighbourhood.size() >= min_pts) neighbourhood.splice(neighbourhood.end(), next_neighbourhood);
            }
            if (!n->clustered) {
                C.push_back(n->val);
                n->clustered = true;
            }
        }
    }

Naming things

Why you have all caps function name?

Why you have variable with capital letter in expandCluster()?
At first I thought it is template parameter i miss.

Use auto more often:

// looks ugly
for (node<T>*& n : neighbourhood) {
}

// looks better
for (auto & n : neighbourhood) {
     // adjust for * here
}

// or you can do with using
using mynode = node<T>;

// still looks better
for (mynode* & n : neighbourhood) {
}

DBSCAN()

Make this a type:

template<class T>
using something = std::vector<cluster<T>>

Why you pass dataset_size by reference?

size_t is as big as the pointer, but there will be additional hidden dereference that will slow down the execution.
keep the const, remove &

size_t const dataset_size

Do the same for all non class parameters.

dataset

probably I am wrong, but if you type this:

T* const& dataset

like this:

const T* dataset

will be same, but more readable? Not sure what T is. If T is a container or array, why not just:

const CONTAINER dataset

Why you pass C like function pointers?

Do it with functor class. Or with std::function.

I am not very experienced with this, so I will do it with functor, but will add it into template parameters.

expandCluster()

more or less similar comments.


Foreach loop to generate HTML table with title in first cell of each row in PHP I've used quite a lot of foreach loops to achieve this type of HTML table that has titles in the first cell of each row:

         	Product 1	Product 2

          Width	50mm	90mm
          Material	Plastic	Gold
          Diameter	60 mm	70mm
          Battery Hours	60 hours	50 hours

Is it necessary to use so many foreach loops? Do you have any other better way of getting this output?

  $sql = "SELECT * FROM product WHERE name IN ('Product 1','Product 2') ";
  if ($wpdb->query($sql))
  {
    $rows = $wpdb->last_result;
    $similar_com = "";
    $similar_com .= "

	";

    foreach($rows as $row)
    {
       $similar_com .= "image_url."' alt='".$row->model_no."'>";
    }
    $similar_com .= "

Width	";
    foreach($rows as $row)
    {
       $similar_com .= "$row->width mm	";
    }
    $similar_com .= "
Material	";
    foreach($rows as $row)
    {
       $similar_com .= "$row->material	";
    }
    $similar_com .= "
Case diameter	";
    foreach($rows as $row)
    {
       $similar_com .= "$row->case_diameter (".plus($product->case_diameter - $row->case_diameter)." mm)	";
    }
    $similar_com .= "
Case thickness	";

    foreach($rows as $row)
    {
       $similar_com .= "$row->case_thickness (".plus($product->case_thickness - $row->case_thickness)." mm)	";
    }
    $similar_com .= "
Case Material	";
    foreach($rows as $row)
    {
       $similar_com .= "$row->case_material	";
    }
    $similar_com .= "
Battery Hours	";
    foreach($rows as $row)
    {
       $similar_com .= "$row->battery_hours hours	";
    }
    $similar_com .= "
Special Functions	";
    foreach($rows as $row)
    {
       $similar_com .= "$row->special_functions	";
    }

    $similar_com .= "

";
   }

Is it critical that your product be the top row? It seems like you would benefit tremendously if your table was structured like this:

            Product
            Width
            Material

            50mm
            Plastic

because that way, you can just use a single foreach loop:

foreach ($rows as $row) {
    $similar_com .= "
";
    $similar_com .= "image_url' alt='$row->model_no' />
$row->name	";
    $similar_com .= "$row->width mm	";
    ...
}

You're doing a SELECT *. Avoid that; it's considered better to explicitly state the columns you're using.
I would rather rename your $rows variable to $products, but I notice that you already have a $product variable. I don't know what this variable is, but you should consider renaming some things... $similar_com is an especially useless name; I can't tell what it's supposed to mean.
I noticed you're using WordPress. The $wpdb->query(); $wpdb->last_result pattern is not as good as simply doing:

if ($rows = $wpdb->get_results($sql) {

If you have to keep your table structure the same, you could have separate variables for each row, then do it all in one foreach:

$widthRow = "
Width	";
$materialRow = "
Material	";
...
foreach ($rows as $row) {
    $widthRow .= "$row->width mm	";
    $materialRow .= "$row->material	";
    ...
}
$widthRow .= "
";
$materialRow .= "
";


Shorter way to write multiple if-then-else-if if($row['best']){
    $id = $row['best'];
} elseif($row['average']){
    $id = $row['average'];
} elseif($row['bad']){
    $id = $row['bad'];
}

If row['best'] is null, I need $id to equal the 2nd best.  If 2nd best is null, $id is equal to the next best.

Simon has already answered while I was writing something similar:

foreach(array('best', 'average', 'bad') as $rank) {
  if($row[$rank]) {
    $id = $row[$rank];
    break;
  }
}

Note however, that in both this and Simon's answer, there is a possibility of $id never being assigned a value. Konijn's answer avoids that (although $id might still end up false'y)


Settings class in C# application I made a settings class for my own C# application. My main goal was to reach this class from every other class (this is why I choose the Singleton pattern). I also wanted to distinguish the different type of settings, so I added GeneralSettings and made it public. Do you know any other ways which I can tell apart the different type of settings? I thought about namespaces, but those are not allowed in classes.

I also wanted to make sure that I can restore its state if the user don't want to save the changes made in the settings dialog. What is your opinion about my implementation? Now I need to call SetRestorePoint and if I want to discard changes Restore.

public class Settings : ISerializable
{
    private Settings ()
    {
    }
    static private Settings _instance = null;
    static private Settings _restoreInstance = null;
    static public  Settings Get //Singleton
    {
        get
        {
            if (_instance == null)
                _instance = new Settings ();

            return _instance;
        }
        private set { }
    }

    public void SetRestorePoint ()
    {
        _restoreInstance = DeepClone (_instance);
    }
    public Settings Restore ()
    {
        _instance = _restoreInstance;
        return _instance;
    }

    public GeneralSettings General = new GeneralSettings ();

    [Serializable]
    public class GeneralSettings
    {
        public bool isAutomaticSave = false;
    }

    private static T DeepClone<T>(T obj)
    {
        using (var ms = new System.IO.MemoryStream ())
        {
        var formatter = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter ();
        formatter.Serialize (ms, obj);
        ms.Position = 0;

        return (T) formatter.Deserialize (ms);
        }
    }
    //serialization...
}

How have people implemented Settings in bigger software?

The indentation isn't always consistent, e.g. the using scope in DeepClone should be indented a level.

Get property should probably be named Instance (a noun), or remain Get (a verb) and be turned into a method. The private and not implemented setter is sloppy, and the = null initialization of the backing private field is redundant.

Seems the restore mechanics are written with a specific UI in mind, where the UI immediately saves changes - typically a settings dialog would do something when the user confirms or applies modifications; seems your model is the other way around - the changes are saved unless they're cancelled, so cancelling changes requires work... seems backwards.

I'd remove that cloning and restore functionality, and make the UI work differently, off a ViewModel - not directly with the settings; when the dialog is cancelled, you have nothing to revert or restore (no changes were made), and when the dialog is okayed and/or changes are applied, then you persist the changes using your settings service.

I think a Singleton isn't needed for this, provided that the rest of the code isn't responsible for newing up anything; if you make that responsibility the job of an IoC container, then it's child's play to configure it in such a way that any class with an ISettingsService constructor parameter will always receive the same instance of whatever concrete type implements that interface - that's OOP with Dependency Injection at play, and static members don't play very well with OOP (static members belong to the type, not to an object), so the more of it you have in your code base, the more coupling you have everywhere between unrelated classes...


Javascript extend object I'm looking for a review of the Javascript code which has this specifications:

  Given two objects, the function "extend" adds properties from the 2nd object to the 1st object.

Notes:

Add any keys that are not in the 1st object.
If the 1st object already has a given key, ignore it (do not overwrite the property value).
Do not modify the 2nd object at all.

A runnable version can be found on repl.it.

function extend(obj1, obj2) {
  for (var key in obj2) {
    if (!obj1.hasOwnProperty(key)) {
      obj1[key] = obj2[key];
    }
  }
}
var obj1 = {
  a: 1,
  b: 2
};
var obj2 = {
  b: 4,
  c: 3
};

extend(obj1, obj2);

console.log(obj1); // --> {a: 1, b: 2, c: 3}
console.log(obj2); // --> {b: 4, c: 3}

Assuming that if the first object has a property set to undefined and the rule states no change then your code is almost spot on.

Some minor changes

The variable key into a const.
Return the extended object.
Vet the arguments.

Thus

function extend(obj1, obj2) {
    if (obj1 !== null && typeof obj1 === "object") {
        if (obj2 !== null && typeof obj2 === "object") {
            for (const key in obj2) {
                if (!obj1.hasOwnProperty(key)) {
                    obj1[key] = obj2[key];
                }
            }
        }
    }
    return obj1;
}
extend({a: 1, b: undefined}, {b: 1, c: 2}); // returns {a: 1, b: undefined, c: 2}


Sorting almost sorted array with a minimum heap I'm currently looking into the quickest way to sort an almost sorted array:

  Given an array of \$n\$ elements, where each element is at most \$k\$ away
  from its target position, devise an algorithm that sorts in \$O(n \log k)\$
  time.

I've implemented a sorting function which "slides" through an input list, pushes the element from a sliding window into a min heap (using the heapq built-in module), pops the minimum element which is collected in the result list:

from typing import List
from heapq import heappush, heappop

def sort_almost_sorted(a: List[int], k: int) -> List[int]:
    if not a:
        return []

    length = len(a)
    if k >= length:
        return sorted(a)  # apply built-in "timsort", designed to be quick on almost sorted lists

    result = []
    min_heap = []  # maintain a min heap for a sliding window
    for slice_start in range(0, length, k + 1):  # sliding window
        # push the next slice to min heap
        for index in range(slice_start, min(slice_start + k + 1, length)):
            heappush(min_heap, a[index])

        result.append(heappop(min_heap))

    # put the rest of the heap into the result
    for _ in range(len(min_heap)):
        result.append(heappop(min_heap))

    return result

It works on my sample inputs.

Do you think I'm using the minimum heap appropriately and this implementation is \$O(n \log k)\$? What would you improve code-quality or code-organization wise?

Algorithm complexity

I am not 100% sure, but it looks like a fancy heapsort which runs (after all) in \$O(n \log n)\$. In order to get this intuition, consider

for slice_start in range(0, length, k + 1):  # sliding window
        # push the next slice to min heap
        for index in range(slice_start, min(slice_start + k + 1, length)):
            heappush(min_heap, a[index])

        result.append(heappop(min_heap))

You operate in chunks of length k + 1 array components (save for the very last chunk that may be shorter). For each chunk, you load it entirely to the heap, and then pop only one element from it to the result array. Finally, in

for _ in range(len(min_heap)):
        result.append(heappop(min_heap))

you handle the majority of elements via heap sort, and that's linearithmic worst case running time.

Perhaps this one?

# This sort runs in O(n log k + k log k),
# which simplifies to O(n log k) whenever k = o(n)
# (k is sublinear in n).
def window_heapsort(a, k):
    if k > len(a):
        return sorted(a)

    window_width = k + 1
    window_heap = []
    result_array = []
    index = 0

    # Initialize the window heap:
    # Runs in O(k log k)
    for i in range(window_width):
        heappush(window_heap, a[i])

    # Keep sliding the window over the array:
    # Here, the size of the heap alternates between
    # 'window_width' and 'window_width - 1', which is
    # O(k), and thus pops and pushes run in O(log k).
    # Since we march over (at most) n elements, the
    # complexity of this loop is O(n log k).
    while index + window_width < len(a):
        result_array.append(heappop(window_heap))
        heappush(window_heap, a[window_width + index])
        index += 1

    # Dump the leftovers to the end of the result array:
    # Runs in O(k log k)
    while window_heap:
        result_array.append(heappop(window_heap))

    return result_array

You can find the entire test snippet here. Hope that helps.


Checking brackets nesting in a string I took a training challenge on Codility that checks for the proper nesting of brackets in a string. The brackets to be checked are {,},(,),[,]. I have written the following Java program which passes in O(n) time and space, but I have a feeling that the extra space I use can be reduced. Also I think that there must be a data structure that can handle this scenario more efficiently. Using an ArrayList instead of an array might help. What I need here is a critique of my code.

import java.util.HashMap;
class Solution {
    public int solution(String S) {
        char[] stack = new char[S.length()];
        int last = -1;
        HashMap hm = new HashMap();
        hm.put('}', '{');
        hm.put(')', '(');
        hm.put(']', '[');
        for(int i=0; i<S.length(); i++){
            char next = S.charAt(i);
            if(next == '}' || next == '{' || next == ')' || next == '(' ||
            next == ']' || next == '[')
            {
                if(last!=-1 && hm.containsKey(next) && stack[last] == hm.get(next)){
                    last--;
                }
                else{
                    last++;
                    stack[last] = S.charAt(i);
                }
            }
        }
        if(last == -1){
            return 1;
        }
        return 0;
    }
}

Naming

Class name: Solution A solution for what?
Method name: solution - again I ask: Solution for what?
Parameter name: S - And what on earth is S? Parameter names are by convention named beginning with a lowercase letter.

None of these three names are descriptive names. It is easier to read and understand code when the names tell a bit about what it is that the code does. Now, naming things are hard, and something that programmers do a lot. For this case, consider names such as BracketNestingVerifier, verify and input. You might even be able to come up with better names.

General things

Use Generics for your HashMap. Since Java 1.5, it's been possible to define which kind of HashMap it is. Is it a HashMap of <Integer, String>? <String, Byte>? No, in your case; it's HashMap<Character, Character>
Why do the method return an int when it would make much more sense to return a true/false boolean? Returning a boolean allows you to simplify the end of your method

if (last == -1) { // note the fixed spacing ;)
    return 1;
}
return 0;

To simply return (last == -1);

Spacing

I find that code like this:

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

Is much more readable if you use spacing (and a better variable name for S of course)

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

Algorithm

Now, about that algorithm... You have a variable called stack and yet it isn't a stack structure, it's only an array. Using a somewhat real stack structure can be helpful. In the code below, I have used the LinkedList class to provide this structure (Even though there is also a Stack class, I like the Deque interface and wanted to go with LinkedList).

In this code, I have improved the variable names, the return type, and I am using a HashSet to store all "special" characters in. The contains method of a HashSet is performing in constant speed, so you should not experience any significant lack of performance. I noticed that in your if-statement, you had hard-coded the values that were put into your HashMap, this is what made me want to add the HashSet.

To make this work, I had to flip the key/values of your HashMap. The key is now the starting character, and the target is the expected ending character.

The loop through the string here is pretty simple and straight-forward:

Have we waited for this character? If so, remove it from the list of expected characters we are waiting for (The "stack")
If the above is not true, does this character have a matching ending character? If it does, add it to the stack
Again, if the above also is not true, is this character regarded as a special character? If it is, then we know here already that we have failed so we can return from the method.

public boolean simonsVerify(String input) {
    HashMap<Character, Character> matches = new HashMap<Character, Character>();
    matches.put('{', '}');
    matches.put('(', ')');
    matches.put('[', ']');

    Set<Character> specialChars = new HashSet<Character>();
    Deque<Character> expected = new LinkedList<Character>();
    for (Entry<Character, Character> ee : matches.entrySet()) {
        specialChars.add(ee.getKey());
        specialChars.add(ee.getValue());
    }

    for (int i = 0; i < input.length(); i++) {
        char next = input.charAt(i);
        Character expect = expected.peekLast();
        if (expect != null && expect == next) {
            expected.removeLast();
        }
        else if (matches.containsKey(next)) {
            expected.addLast(matches.get(next));
        }
        else if (specialChars.contains(next)) {
            return false;
        }
    }
    return true;
}

Here is the testing (with JUnit) I used, for both your original code and also for my method:

@Test
public void testVerifying() {
    assertTrue(verify("{,},({,}),[,]"));

    assertFalse(verify("{(,},({,}),[,]"));
    assertFalse(verify("{,)},({gfdgfd}),[,]"));
    assertFalse(verify("{(,}),({,}),[,]"));

    assertTrue(verify("{,},(,),[[,]]"));
    assertTrue(verify("{,},(,),[,]"));
    assertTrue(verify("{{,}},(,),[,]"));
    assertTrue(verify("{,},((,)),[,]"));
    assertTrue(verify("{,},(,),[,]"));
    assertTrue(verify("(), {{{,}}},(,),[,]"));
}

There might even be a better way to do this algorithm, this is just my way.


Select a specific line after matching a pattern I just recently started using AWK and I'm still learning about it. I have solved the problem I'm about to show but I feel it's not the best solution and I'm trying to find a solution to fit within an AWK command rather than keep piping.

I have a bunch of .txt files ending for which I read the header (1st line only).

head -1 *.txt

Outputs:

==> anglia.txt <==
String - Anglian

==> carr.txt <==
String - Carr
etc..

From here I have a case switch where a user inputs 1-9. It's sorted so first line is always Anglian and second is always Carr.. etc
So if a user inputs 1 I know they want to select anglian. But for further process my code I need to extract the String "Anglian".

head -1 *.txt | awk '/[a-z]/&&!/.txt/'

Outputs:

String - Anglian
String - Carr

Here I got rid of the first line that had the filename.

head -1 *.txt | awk '/[a-z]/&&!/.txt/' | awk '{print $3}'

Outputs:

Anglian
Carr

Here I selected column 3 which contains the String that I need!

head -1 *.txt | awk '/[a-z]/&&!/.txt/' | awk 'NR==1{print $3}'

Outputs:

Anglian

Here I selected the first row which is exactly the output that I want! However I had to use an extra pipe. All I want is a awk command that does all of this in a single command somethings around the lines of:

head -1 *.txt | awk '/[a-z]/&&/.txt/{if(NR==1)print $3}'

Outputs:

EMPTY LINE

This is the problem I'm having. Since I'm having the pattern and NR in 1 command it's selecting the 1st line but the first line is a line that is being hidden by my pattern and it's the ==> anglian.txt <== hence

head -1 *.txt | awk '/[a-z]/&&/.txt/{if(NR==2)print $3}'

Outputs:

Anglian

However this is of no use because only matches Anglian where it is NR==2 and due to my case switch that I have I want it to be NR==1 otherwise the code does not work.

Is this possible? I hope I made myself clear here :)

You can replace this pipeline

head -1 *.txt | awk '/[a-z]/&&!/.txt/' | awk '{print $3}'

with this one awk command

awk 'FNR == 1 {print $3}' *.txt

FNR is the file record (i.e. line) number. NR is the cumulative record number of all records seen from all files.

Now, you can select the user's numeric choice with

awk 'FNR == 1 {print $3}' *.txt | awk -v n="$user_selection" 'NR == n'

or, with a single awk:

awk -v n="$user_selection" 'FNR == 1 && ++filenum == n {print $3; exit}' *.txt

If you're looking for a way to get your users to select a name from one of the files, perhaps some more advanced bash:

# read the 3rd word from the 1st line of all txt files into an array
readarray -t names < <(awk 'FNR == 1 {print $3}' *.txt)

# get the user to select one of them
PS3="Choose a name: "
select name in "${names[@]}"; do
    [ "$name" ] && break
done

echo "$name"

This really isn't a code review. Since you're asking "how can I do this", you should have asked on Stack Overflow.