Find greatest number in array that is a product of some two elements in the same array Given an array a, find the greatest number in a that is a product of two elements in a. If there are no two elements in a that can be multiplied to produce another element contained in a, return -1.

I am trying to get this to run as fast as possible.  I assume there is some math algorithm or formula to do this that I am unaware of.  This is the way I know how to find this answer.  However, I assume this would take a long time if the length of the array was huge.  Is there a faster way to do this?  I have provided the test.

using System;
using System.Linq;

namespace Exercise
{
    public static class Program
    {
        public static int maxPairProduct(int[] a)
        {
            int x = -1;

            for (int i = 0; i < a.Length; ++i)
            {
                for (int j = i + 1; j < a.Length; ++j)
                {
                    int temp = a[i] * a[j];
                    if (a.Contains(temp) && temp > x)
                    {
                        x = temp;
                    }
                }
            }
            return x;
        }
    }
}

using NUnit.Framework;

namespace Exercise
{
    public class SuccessTests
    {
        [Test]
        public static void TestOne() => Assert.That(Program.maxPairProduct(new int[] { 10, 3, 5, 30, 35 }), Is.EqualTo(30));
        public static void TestTwo() => Assert.That(Program.maxPairProduct(new int[] { 2, 5, 7, 8 }), Is.EqualTo(-1));

    }
}

Sort it
As @Peska suggested, sort the array first. But sort it descendand, or simply iterate in reverse order.
Overflow
The multiplication of integers can overflow. It would be wiser to approach the iterations from product, divide by one element and check if the division equals second element, but only if product modulo first element is zero.
Contains() checks too much
First of all.
a.Contains(temp) && temp > x

should be written as
temp > x && a.Contains(temp)

The Contains call is O(n), we want to avoid this as much as possible, as it is turning the entire algorithm to O(n^3). In sorted input, we can make some restrictions and which elements we search through. We can actually deploy a binary search, introducing another loop instead of call to Contains, but this loop will be O(log(n)). In the code I have a naive variant that is commented out and is still O(n), but still checks much less then full Contains scan.
// we will use this to skip duplicate elements in forward iterations
private static int NextDistinctElementIndex(int[] input, int i)
{
    int value = input[i];
    do
    {
        ++i;
    } while (i < input.Length && input[i] == value);
    return i;
}

public static int SlepicMaxPairProduct(int[] input)
{
    if (input.Length < 2)
    {
        // there's never product of two, if there are no two
        return -1;
    }

    Array.Sort(input);

    if (input[0] < 0)
    {
        throw new ArgumentException("Input cannot contain negative numbers.");
    }

    int result = -1;
    int imin = 0;

    if (input[0] == 0)
    {
        // if first element after sort is zero, the result will be at least zero
        result = 0;
        // and we will never have to search for zeroes
        imin = NextDistinctElementIndex(input, 0);
    }

    if (imin < input.Length - 1 && input[imin] == 1)
    {
        // if there is "1" in the input, the greatest element of input is the result
        // except if there is just one "1" and zero(es)
        return input[input.Length - 1];
    }

    // start examining the sorted input from greatest element
    // and assume the values to potentialy be the product we are looking for
    for (int pi = input.Length - 1; pi > imin; --pi)
    {
        int product = input[pi];

        // exclusive index of the greatest element that is reasonable to search for a "b" value
        int bmax = pi;

        // assume values before bmax are some "a", then look for "b"
        for (int ai = imin; ai < bmax; ++ai)
        {
            int a = input[ai];

            // if product is not divisible by a, we won't find any b
            if (product % a != 0)
            {
                continue;
            }

            int expectedB = product / a;

            /*
            // search for a "b" value in the reasonable range (bmin, ai)
            for (int bi = bmin; bi < ai; ++bi)
            {
                int b = input[bi];

                if (b == expectedB)
                {
                    return product;
                }

                if (b > expectedB)
                {
                    bmin = bi;
                    break;
                }
            }*/

            // let's turn the naive "for bi" loop into log(n)

            // searchfor a "b" value using bisection in the reasonable range (bmin, bmax)
            // and export new values of bmax to the outer loop
            // because if we will search for a greater "a" then the current one
            // we are inevitably only going to find a smaller "b"
            int bmin = ai;
            while (bmax > bmin)
            {
                // int bi = (bmin + bmax) / 2;
                // variant with no overflow of index (for very large arrays):
                int bi = (bmin / 2 + bmax / 2) + ((bmin % 2) & (bmax % 2));

                int b = input[bi];

                if (b == expectedB)
                {
                    return product;
                }

                if (b < expectedB)
                {
                    bmin = bi + 1;
                }
                else
                {
                    bmax = bi;
                }
            }
        }
    }

    return result;
}

In conclusion, we have limited the searched space to a great degree and turned the algorithm from O(n^3) to O((n^2) * log(n)).
|       Method |    N |               Mean |            Error |           StdDev |
|------------- |----- |-------------------:|-----------------:|-----------------:|
|    PeskaTest |   10 |           215.3 ns |          3.61 ns |          3.38 ns |
| MilliornTest |   10 |         4,868.0 ns |         88.16 ns |        134.64 ns |
|   SlepicTest |   10 |           264.6 ns |          3.57 ns |          3.34 ns |
|    PeskaTest |  100 |        56,954.4 ns |      1,131.18 ns |      1,548.37 ns |
| MilliornTest |  100 |     4,352,830.7 ns |     76,663.28 ns |     94,149.39 ns |
|   SlepicTest |  100 |        16,452.8 ns |         86.02 ns |         76.25 ns |
|    PeskaTest | 1000 |    27,821,365.8 ns |    349,019.38 ns |    309,396.59 ns |
| MilliornTest | 1000 | 4,193,838,300.0 ns | 43,784,319.26 ns | 40,955,879.40 ns |
|   SlepicTest | 1000 |        50,757.2 ns |        244.00 ns |        203.76 ns |

PS: Based on return value -1 meaning "not found" I assume the input cannot contain negative numbers, otherwise it cannot work like this (where I assume that if zero is present it is on index 0, ...)
PS2: It is not very nice that the implementation sorts the array for the caller. It may be wise to provide the method expecting the input already sorted and provide a wrapper that creates a sorted copy and passes it to this method that expects sorted input. It will be more expensive because of copying and allocating new array, but for big inputs, this should be neglegable (because it is O(n) which is neglegable compared to O(n^2*log(n)) while making it error safe, immutable for the caller, thus more transparent for him, and offering the method that expects sorted input makes it more flexible/efficient for callers that already sorted their input.
EDIT:
New bench results including @potato's solution (2nd snippet). Mine still seems faster although according to potato's big-O, his should be faster. Not sure what's going on yet...
|       Method |    N |               Mean |            Error |           StdDev |
|------------- |----- |-------------------:|-----------------:|-----------------:|
|    PeskaTest |   10 |           209.6 ns |          1.25 ns |          1.11 ns |
| MilliornTest |   10 |         5,168.6 ns |         58.73 ns |         54.93 ns |
|   SlepicTest |   10 |           256.8 ns |          1.12 ns |          0.99 ns |
|   PotatoTest |   10 |           539.0 ns |          1.25 ns |          1.04 ns |
|    PeskaTest |  100 |         3,567.1 ns |         45.20 ns |         37.75 ns |
| MilliornTest |  100 |     4,806,710.5 ns |     13,092.42 ns |     10,932.77 ns |
|   SlepicTest |  100 |         5,039.0 ns |         58.10 ns |         48.52 ns |
|   PotatoTest |  100 |         6,141.9 ns |        111.06 ns |         86.71 ns |
|    PeskaTest | 1000 |    26,678,273.6 ns |    502,308.33 ns |    419,450.21 ns |
| MilliornTest | 1000 | 4,798,816,196.0 ns | 29,527,973.10 ns | 39,418,995.96 ns |
|   SlepicTest | 1000 |        44,601.9 ns |        407.09 ns |        360.87 ns |
|   PotatoTest | 1000 |        84,168.8 ns |        207.99 ns |        173.69 ns |

|     Method |     N |        Mean |     Error |    StdDev |
|----------- |------ |------------:|----------:|----------:|
| SlepicTest |  1000 |    49.88 us |  0.123 us |  0.103 us |
| PotatoTest |  1000 |    86.66 us |  1.121 us |  0.994 us |
| SlepicTest |  2000 |   119.67 us |  0.628 us |  0.557 us |
| PotatoTest |  2000 |   193.52 us |  0.530 us |  0.470 us |
| SlepicTest |  4000 |   279.29 us |  4.180 us |  3.705 us |
| PotatoTest |  4000 |   409.23 us |  1.443 us |  1.127 us |
| SlepicTest |  8000 |   563.60 us |  1.117 us |  0.990 us |
| PotatoTest |  8000 |   859.76 us |  4.800 us |  4.490 us |
| SlepicTest | 16000 | 1,201.41 us | 12.686 us | 11.867 us |
| PotatoTest | 16000 | 1,659.58 us |  8.473 us |  7.511 us |

|     Method |      N |      Mean |     Error |    StdDev |
|----------- |------- |----------:|----------:|----------:|
| SlepicTest | 100000 |  8.657 ms | 0.0556 ms | 0.0464 ms |
| PotatoTest | 100000 | 10.628 ms | 0.0301 ms | 0.0266 ms |

|     Method |       N |     Mean |   Error |  StdDev |
|----------- |-------- |---------:|--------:|--------:|
| SlepicTest | 1000000 | 101.7 ms | 0.41 ms | 0.36 ms |
| PotatoTest | 1000000 | 119.1 ms | 0.30 ms | 0.25 ms |

|     Method |        N |    Mean |    Error |   StdDev |
|----------- |--------- |--------:|---------:|---------:|
| SlepicTest | 10000000 | 1.266 s | 0.0048 s | 0.0043 s |
| PotatoTest | 10000000 | 1.446 s | 0.0194 s | 0.0172 s |

Those were with random numbers r: 0 <= r < 1000.
Now 0 <= r < N:
|     Method |        N |           Mean |       Error |      StdDev |
|----------- |--------- |---------------:|------------:|------------:|
| SlepicTest |    10000 |       726.4 us |     2.90 us |     2.57 us |
| PotatoTest |    10000 |     1,055.5 us |     4.55 us |     3.80 us |
| SlepicTest |   100000 |     9,056.1 us |    33.79 us |    31.61 us |
| PotatoTest |   100000 |    11,992.9 us |    58.15 us |    48.55 us |
| SlepicTest |  1000000 |   107,084.9 us |   473.48 us |   419.73 us |
| PotatoTest |  1000000 |   139,090.3 us |   376.83 us |   352.48 us |
| SlepicTest | 10000000 | 1,306,931.0 us | 2,585.99 us | 2,018.97 us |
| PotatoTest | 10000000 | 1,648,109.2 us | 7,627.77 us | 7,135.02 us |


Make two MySQL statements & loop quicker Would a join be quicker here? I tested a join and it's almost the same time! Basically its a ray casting mechanism that finds all properties in a square on GMaps, and then there's a javascript function that finds the point in polygon. So at any time, the records fetched could be in the tens of thousands.

The first statement finds all the postcodes in the latLongs, the second one finds all the properties in that postcode.

Bear in mind I just knocked this up very quickly, as the raycasting javascript took up most of my designated time

    $latlongs = explode("), ", $_GET['bounds']);

$first = ($latlongs[0]);
$first = substr($first, 2);

$second = $latlongs[1];
$second = substr(substr($second, 1),0, -2);

$first = explode(", ", $first);
$second = explode(", ", $second);
//$result = mysql_query("SELECT * FROM `postcodeGoogle` WHERE lat");
$lat1 = $first[0];
$lat2 = $second[0];

$long1 = $first[1];
$long2 = $second[1];
$resultE = "";
$result = mysql_query("SELECT * FROM `postcode`.`postcodeGoogle` WHERE (`lat` BETWEEN '$lat1' AND '$lat2') AND (`long` BETWEEN '$long1' AND '$long2')")or die(mysql_error());

while($row = mysql_fetch_assoc($result)){

        $prop = mysql_query("SELECT * FROM `digital_hub`.`address_list` WHERE `postcode`='".$row['postcode']."'")or die(mysql_error());
        echo $row['postcode'];
        echo mysql_num_rows($prop);
        while($propRow=mysql_fetch_assoc($prop)){
            $resultE = $resultE."(".$row['lat'].", ".$row['long'].") || ";
        }
}
$resultE = substr($resultE, 0, -4);
echo $resultE;

Personally I would go with a join even if they are currently the same speed.

This way your code automatically gets upgraded when the DB gets upgraded (ie when a new index is added to the DB or they decide to partition the DB by latitude/longitude). In this situation if you are using a Join your code will automatically benefit from any improvement.


Managing several payment means in my Rails 3.2 app I'm trying to manage several means of payment in my Rails 3.2 application.

Let's say I have 2 means : Credit Cards & Bank Transfers (BIC), working with 2 different payment providers. Those means both contain a reference string that will be sent to the payment provider to trigger new payments later.
Each means also contains specific information. This is why I'm thinking about creating 2 models (a CreditCard one and a Bic one). And I would like to link both models to the User model.

A single user can have for example 2 credit cards and 1 BIC so there must be at least a have_many association.
I don't want my user model to have too many different associations, but I want it to have the same behavior for each kind of payment mean. I though about using the Single Table Inheritance but I previously had a bad experience with the combo "STI + associations" and I lost a lot of time.

So, my solution to that problem would be to make an intermediate model PaymentMean that would:

belong to User
be associated to both CreditCard and Bic with a polymorphic "belongs_to" association

as follows:

class User < ActiveRecord::Base
  has_many :payment_means
end

class PaymentMean < ActiveRecord::Base
  belongs_to :user
  belongs_to :payment, polymorphic: true
end

class CreditCard < ActiveRecord::Base
  has_one :payment_mean, as: :payment
end

class Bic < ActiveRecord::Base
  has_one :payment_mean, as: :payment
end

What do you think about it ? Should I try to use STI (if so, HOW ?) or is this model viable ? Or is there any other solution ?

First: "Means" is uncountable in English; it's always plural. So the model should be called PaymentMeans, and associations should be has_many :payment_means and has_one :payment_means. You can set that up in Rails' inflections config (or just call it "payment type" or something).

Anyway, I would definitely consider STI for this, depending on how similar the models really are. It really all depends on that. The more they have in common, the better suited an STI solution will be. As far as I can tell, there shouldn't be any major pitfalls. However, you've only said they "contain specific information" but without knowing what exactly that entails, it's hard to know if it'd overburden an STI approach.

Alternatively, if they have little in common beyond the reference string, your current solution seems fine, but it does add an extra association and thus extra complexity.

If you're adamant about avoiding STI, I'd think you can skip the PaymentMean (sic) model, and simply make the polymorphic association directly to the User model:

class User
  belongs_to :payment_means, polymorphic: true # can be CreditCard or Bic
end

You can then extract a service object to handle the things you'd currently handle with the PaymentMean model (in fact, you could consider this, regardless of how your models are otherwise set up).

Of course it seems semantically awkward to say that a "User belongs to their Payment Means" (although that's how banks probably think), so once again your current solution or STI might be better suited.

Lastly, you could reduce your payment means model to just the bare necessities, and keep everything else in a serialized attribute (i.e. a hash). Of course this would likely entail writing a custom validator or similar busywork, but it would be very flexible. It still is a "last resort" solution, though.


Should I use const in this function argument? I'm working on getting myself comfortable with C after only working in high level languages for the past 10 years.  I've done rust as well and really like the concept of notating immutability in functions.
That being said I'm confused on if I should use const wherever the compiler lets me, or just use it where it semantically makes sense (and hope no one comes behind me and does something the caller doesn't expect).
Several functions I am looking at right now are:
void kcr_scene_update(const struct KCR_Scene* scene) {
    scene->internal->cubeRotation.x += 0.01f;
    scene->internal->cubeRotation.y += 0.01f;
    scene->internal->cubeRotation.z += 0.01f;
}

void kcr_display_begin_frame(const struct KCR_Display* display) {
    for (int x = 0; x < display->windowWidth * display->windowHeight; x++) {
        display->pixelBuffer[x] = 0xFF000000;
    }
}

The compiler is allowing these, presumably because it's not changing the root pointer or direct child pointers (I guess?) but is it good practice to put const in these methods when I know there's some mutation going on?

Should I use const in this function argument?

Yes.

Better conveys to a user code's functionality. Consider the user may only see the declaration void kcr_scene_update(const struct KCR_Scene* scene); (in some header file) and not the definition.

Allows increased applicability.  Function can be called with  const struct KCR_Scene* some_pointer.  Without a const in the function signature, the caller is obliged to pass a non-const pointer.

Optimization: Some optimization will only take place when the reference data is const.  This issue applies especially to older compilers.

good practice to put const in these methods when I know there's some mutation going on?

Need to see detail of struct KCR_Scene and struct KCR_Display to know what changes are really occurring in code.

I now see OP really needs to provide more info  - making answer wiki.


Project Euler #41 - pandigital prime I've written a solution to Euler 41:

  We shall say that an n-digit number is pandigital if it makes use of
  all the digits 1 to n exactly once. For example, 2143 is a 4-digit
  pandigital and is also prime.

  What is the largest n-digit pandigital prime that exists?

But it feels like I could compress the code down instead of having 30 lines of for loops. To briefly explain how it works:

I generate all pandigital numbers through the generate function which features 9 nested for loops which continue if their value is equal to a higher loop or if they would make a number longer than what is required. The generated numbers are then prime checked. This is a bruteforce method.

var time = new Date;
var buffer = [];
var greatest = 0;

function isPrime(number) {
var s = Math.sqrt(number);
for (var b = 2; b <= s; b++) {
    if (number % b === 0) {
        return false;
    }
}
return true;
}

function push(array) {
buffer.push(array.join(''));
}

function generate(length) {
var max = length;
for (var u = 1; u <= max; u++) {
    if (max === 1) {
        push([u]);
    }
    for (var i = 1; i <= max; i++) {
        if (i === u || max < 2) {
            continue;
        }
        if (max === 2) {
            push([u, i]);
        }
        for (var o = 1; o <= max; o++) {
            if (o === i || o === u || max < 3) {
                continue;
            }
            if (max === 3) {
                push([u, i, o]);
            }
            for (var p = 1; p <= max; p++) {
                if (p === i || p === o || p === u || max < 4) {
                    continue;
                }
                if (max === 4) {
                    push([u, i, o, p]);
                }
                for (var a = 1; a <= max; a++) {
                    if (a === i || a === o || a === p || a === u || max < 5) {
                        continue;
                    }
                    if (max === 5) {
                        push([u, i, o, p, a]);
                    }
                    for (var s = 1; s <= max; s++) {
                        if (s === a || s === p || s === o || s === i || s === u || max < 6) {
                            continue;
                        }
                        if (max === 6) {
                            push([u, i, o, p, a, s]);
                        }
                        for (var d = 1; d <= max; d++) {
                            if (d === s || d === a || d === p || d === o || d === i || d === u || max < 7) {
                                continue;
                            }
                            if (max === 7) {
                                push([u, i, o, p, a, s, d]);
                            }
                            for (var f = 1; f <= max; f++) {
                                if (f === d || f === s || f === a || f === p || f === o || f === i || f === u || max < 8) {
                                    continue;
                                }
                                if (max === 8) {
                                    push([u, i, o, p, a, s, d, f]);
                                }
                                for (var g = 1; g <= max; g++) {
                                    if (g === f || g === d || g === s || g === a || g === p || g === o || g === i || g === u || max < 9) {
                                        continue;
                                    }
                                    push([u, i, o, p, a, s, d, f, g]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
}

for (var i = 1; i <= 8; i++) {
generate(i);
}

for (var i = buffer.length - 1; i >= 0; i--) {
if (isPrime(buffer[i])) {
    greatest = buffer[i];
    break;
}
}

var time1 = new Date;
console.log(greatest, 'took:', time1 - time, 'ms');

I think this is a bit over engineered. Let's talk our way through the problem.

By definition we know the highest pandigital number is 987654321.
We need to loop through each odd number between 1 and 987654321.
We need to test each number as a prime.
Here's a nice optimised isPrime function from here.

function isPrime(number) {
  var start = 2;
  while (start <= Math.sqrt(number)) {
    if (number % start++ < 1) return false;
  }
  return number > 1;
}

If it is prime we need to test each number is pandigital. We should only need to loop once. If we make a set of the digits in a number, then the length of the set will be equal to the total count of digits in the number.

function isPandigital(number) {
   var numStr = number.toString(),
     digits = [];

   for (var digit in numStr) {

     if (numStr.hasOwnProperty(digit) && digits.indexOf(digit) === -1)
        digits.push(digit);
   }

   return digits.length === numStr.length;
}

Then you just need to write the loop:

var pandigitalPrimes = [];

for (var n = 1; n <= 987654321; n+=2) {
  if (isPrime(n) && isPandigital(n)) pandigitalPrimes.push(n);
}

Now it's your job to optimise these ideas so that this process doesn't take absolutely forever.


Cross-post from SO-  Palindrome finding function I didn't know this site existed before now... awesome!

I just made a thread here:  https://stackoverflow.com/questions/8511620/c-palindrome-finder-optimization

#include <iostream>
#include <ostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

bool isPal(string);

int main()
{
    vector<string> sVec;
    vector<string> sWords;
    vector<string> sTwoWords1;
    vector<string> sTwoWords2;
    char myfile[256]="/home/Damien/Test.txt";
    ifstream fin;
    string str;
    fin.open(myfile);
    if(!fin){
        cout << "fin failed";
        return 0;
    }
    while(fin){
        fin >> str;
        sWords.push_back(str);
        if(!fin){
            break;
        }
        if(isPal(str)){
            sVec.push_back(str);
        }
        else{
            getline(fin, str);
        }
    }
    reverse(sVec.begin(), sVec.end());
    for(int i =0; i < sVec.size(); i++){
        cout << sVec[i] << " is a Palindrome " <<endl;
    }

    // Test 2
    for(int i=0; i<sWords.size(); i++)
    {
        for(int j=(i+1); j<sWords.size(); j++){
            str = sWords[i]+sWords[j];
            if(isPal(str)){
                sTwoWords1.push_back(sWords[i]);
                sTwoWords2.push_back(sWords[j]);
            }
        }
    }
    fin.close();
    for(int i=0; i<sTwoWords1.size();i++){
        cout << sTwoWords1[i] << " and " << sTwoWords2[i] << " are palindromic. \n";
    }
    return 0;
}
bool isPal(string& testing) {
    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());
}

About optimizing some code, assuming that I take the revision to my isPal function, what else can I do to optimize the hell out of my code?

Thanks a lot for any / all recommendations!

Wordfile:  http://www.filedropper.com/ospd3

Reading a file:

while(fin){

    fin >> str;
    sWords.push_back(str);
    if(!fin){
        break;
    }

You push the value str before checking it worked. It should be:

while(fin)
{
    fin >> str;
    if(!fin){
        break;
    }
    sWords.push_back(str);

Or even better would be:

while(fin >> str)
{
    sWords.push_back(str);

Why are you doing this:

    else{
        getline(fin, str);
    }

Mixing operator >> and getline() makes the code hard to read.
Either use all operator >> or use getline() to get a line at a time then parse the line internally.

Note:: operator>> will ignore the '\n' at the end of the line and work. So if your file is a list of words one per line there is no need to use getline(). If on the other hand your file is a lot of text and you only want the first word on each line then you need to use getline().

Method 1: Use operator>>

 // If your input file has one word per line (or you want to use all words)
 while(file >> word)
 {
      // Do stuff
 }

Method 1: Use getline()

 // If your input file contains lots of words
 // But you only want to use the first word on each line
 while(std::getline(file, line))
 {
     std::stringstream  linestream(line);
     linestream >> word;

     // Do stuff
 }

You seem to reversing the line just to print it:

reverse(sVec.begin(), sVec.end());
for(int i =0; i < sVec.size(); i++){
    cout << sVec[i] << " is a Palindrome " <<endl;
}

Rather than reversing the array, just iterate it in reverse order:

for(std::vector<std::string>::const_iterator& loop = sVec.rbegin(); loop != sVec.rend(); ++ loop)
{
    cout << (*loop) << " is a Palindrome " <<endl;
}

Note on efficiency:

Using push_back() on an vector can be in-effecient if you are pushing a lot of data. As evertime the vector runs out of space it must allocate more memory and copy the string to the new buffer. You help by pre-allocting space.

sVec.reserve(1000); // Guess at the size
                    // Note when the vector runs out of space it will approximately
                    // double its internal buffer.


"Tractor" Python implementation This is the Tractor problem from the Kattis problems archive.

Problem Statement

  Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a terrible driver, and can only move according to the following rules:

  Each of her movements is in the same direction as either the positive x-axis or the positive y-axis.
  Her \$\text{nth}\$ movement takes her \$2^{n−1}\$ units forward in her chosen direction. (On her first movement, \$n = 1\$, so she moves 1 unit.)
  Farmer John’s farm is on the coordinate plane, in the shape of a rectangle with corners at \$(0, 0), (A, 0), (0, B) \text{and} (A, B)\$. If Bessie starts at (0, 0), how many points inside the farm, including the boundary, could she reach?

  Input Format

  The input begins with an integer \$N (1 \le N \le 100)\$ on a line by itself, indicating the number of test cases that follow. Each of the following N lines contains two space separated integers A and B \$(1 \le A, B \le 10^8)\$, describing the upper-right corner of Farmer John’s farm.

  Output Format

  Output N lines, with the Nth line containing the number of points that Bessie could possibly reach in the Nth test case.

  In the first test case of the sample, Bessie can reach the following six points: \$(0, 0), (0, 1), (1, 0), (1, 2), (2, 1) and (3, 0)\$.

  Sample Input

2
2 3
7 7

  Sample Output

6
15

Solution

def next_steps():
    n = 1
    while True:
        yield n
        n <<= 1

def moves(a, b):
    current_positions = [(0, 0)]
    moves = []
    for step in next_steps():
        next_positions = []
        while current_positions:
            x, y = current_positions.pop(0)
            moves.append((x, y))
            if x + step <= a:
                next_positions.append((x+step, y))
            if y + step <= b:
                next_positions.append((x, y+step))
        if not next_positions:
            break
        else:
            current_positions = next_positions
    return moves

if __name__ == '__main__':
    for test_case in xrange(int(raw_input())):
        a, b = map(int, raw_input().strip().split())
        print len(moves(a, b))

It's working fine on smaller input but gets timed out on very large instances.

for loop

Use a for loop when iterating over a collection:

    for (x, y) in current_positions:
        moves.append((x, y))

for has less power than while (theoretically) and its simplicity makes it a better choice over while.

Avoid premature optimization

Just multiply by two:

n *= 2

Some tests:

>>> import timeit
>>> timeit.timeit("10 << 1")
0.029866752000089036
>>> timeit.timeit("10 * 2")
0.03209113599950797
>>> 0.029866752000089036 / 0.03209113599950797
0.9306854079751793

<< is just 7% faster than *2

And the majority of your time is spent branching if x + step <= a: and playing with lists moves.append((x, y)), so the final improvement would be tiny, not worth the loss in readability.

Optimizing the algorithm

Your algorithm has exponential time complexity:

print(step, len(current_positions))

Gives:

1 2
2 4
4 8
8 16
16 32
32 64
64 74
128 0

At each iteration, the number of current_positions is doubling, and this can get out of hand really quickly.

Arguments name

a and b are not acceptable argument names. I suggest width and height.

Some plotting always gives ideas

Following @ErikR suggestion, I made a graph of the reachable points and noticed a serious regularity, still doing graphs is a nice skill to have, so I encourage you to reproduce this graph by yourself.


Defining pipelines of functions when passing a main argument across multiple functions Discovering sk-learn pipelines (https://scikit-learn.org/stable/modules/generated/sklearn.pipeline.Pipeline.html) made me wonder why weren't I using the same idea for any set of functions applied to a single main argument.
Based on this idea I developed the following code (Using kwargs treatment from https://stackoverflow.com/a/58543357):
import inspect
def create_sequential_pipe(func_list):
    """
    Create a pipeline for a series of functions to be applied to a single main argument

    Args:
        func_list: List of functions
    """

    def sequential_pipe(main_arg, **kwargs):

        for func in sequential_pipe._func_list:

            func_args = [k for k, v in inspect.signature(func).parameters.items()]
            func_dict = {k: kwargs.pop(k) for k in dict(kwargs) if k in func_args}
            main_arg = func(main_arg, **func_dict)

        return main_arg

    sequential_pipe._func_list = func_list

    return sequential_pipe

def example_func_1(n, power=1):
    return n ** power

def example_func_2(n, sum=0):
    return n + sum

def example_func_3(n, divide=1):
    return n / divide

if __name__ == "__main__":

    example_pipe= create_sequential_pipe([example_func_1, example_func_2, example_func_3])

    out = example_pipe(2)
    print(out)  # 2.0

    out = example_pipe(2, power=2, sum=1, divide=5)
    print(out)  # 1.0

I feel I could get used to its use, but I couldn't find something similar already implemented in Python, so I feel there must be a downside I am not seeing.
I could just create a wrapper function for the pipeline of functions, but I'm not sure it would be as simple.
Is there something similar commonly used in other languages? Do you think it's obfuscates the code? Are there clear downsides to using this?

Without being familiar in use of sklearn, there are still some Python fundamentals that can be improved:
Superfluous comprehension
func_args = [k for k, v in inspect.signature(func).parameters.items()]

can probably be
func_args = inspect.signature(func).parameters.keys()

assuming that parameters has the interface of a regular dictionary. Also, since you're only using it to test membership, wrap it in a call to set().
Set intersection
If you do the above and make func_args a set, then this:
for k in dict(kwargs) if k in func_args

can be replaced by set(kwargs.keys()) & func_args.
Non-repeatable read
There's a potential issue with your use of pop(). This modifies your kwargs in a loop. Are you sure that you want a given kwarg to only apply to one function in your pipe, and not all of them?
Real tests
Convert this:
example_pipe= create_sequential_pipe([example_func_1, example_func_2, example_func_3])

out = example_pipe(2)
print(out)  # 2.0

out = example_pipe(2, power=2, sum=1, divide=5)
print(out)  # 1.0

into an actual unit test - you're already most of the way there, so you might as well.
Variadic function
create_sequential_pipe(func_list):

is a good candidate for being turned into a variadic function, i.e. accepting *func_list. This will make invocation simpler in some cases, including the one you showed at the bottom - there will be no need for an inner list literal.


Retrieving value from HTML table Currently all this does is retrieve data from specific columns, the final result will be that I will check the data to make sure that it passes the test cases, but I want to look at this foreach right now and see if I can't make it a little simpler.

A lot of what I have coded I have come back and turned into Linq statements and made things a lot simpler (shorter), and I would really like to do the same with this foreach statement, but not real sure how to do it.

I hate to admit that I am very new to using Linq, I can read it for the most part but still have a little difficulty when writing more complex statements/queries.

Is there something that I can do to make this a lot more simple before I code any more on this Scenario, I would like to simplify so that I don't write extraneous code that will be refactored out when I make this more clear.

I have also been trying to find something that imports the HTML table into a nice neat object that I can query, but everything I have found so far has been similar to what I am doing or more complex than what I am doing here.

[Then(@"see the '(.*)' of '(.*)'")]
public void ThenSeeThe(string columnHeader, string entryName)
{
    var htmlTable = Ie.FindElementByClassName("table");
    var tableHeaders = htmlTable.FindElements(By.TagName("th"));
    var rows = new List<List<string>>();

    var htmlRows = htmlTable.FindElements(By.TagName("tr"));

    foreach (var htmlRow in htmlRows)
    {
        //first row holds the table headers
        if (htmlRow.FindElements(By.TagName("th")).Count > 0)
        {
            var thList = tableHeaders.Select(th => th.Text.ToString()).ToList();
            rows.Add(thList);
            continue;
        }

        var cellsInRow = htmlRow.FindElements(By.TagName("td"));
        var cells = cellsInRow.Select(cell => cell.Text.ToString()).ToList();
        rows.Add(cells);
    }

    var columnIndex = rows.First().IndexOf(columnHeader);
    var field = rows.Where(x => x[0] == entryName).Select(x => x[columnIndex]).First();
    if (columnHeader == "Create UTC Date")
    {
        _CreateUTC = Convert.ToDateTime(field);
    }
    else if (columnHeader == "Modify UTC Date")
    {
        _ModifyUTC = Convert.ToDateTime(field);
    }

}

If I understand correctly, the role of this procedure (which is far from obvious from the name alone) is to assign either _CreateUTC or _ModifyUTC values (which should be _createUTC and _modifyUTC if they're private fields - always use camelCase for fields and locals/parameters.

You don't need that rows list of lists of strings at all, let alone iterate that monster afterward to retrieve a value.

Just loop and locate the value as you're looping, don't store anything but what you need and stop looping once you got it - I think something like this would do it:

var headerIndex = 0;
DateTime value;
foreach (var htmlRow in htmlRows)
{
    if (htmlRow.FindElements(By.TagName("th")).Count > 0)
    {
        headerIndex = tableHeaders.Select(th => th.Text.ToString()).IndexOf(columnHeader);
        continue;
    }

    var cellsInRow = htmlRow.FindElements(By.TagName("td")).ToArray();
    if (cellsInRow[0] == entryName)
    {
        value = Convert.ToDateTime(cellsInRow[headerIndex].Text.ToString());
        break;
    }
}

if (columnHeader = "Create UTC Date")
{
    _createUTC = value;
}
else if (columnHeader = "Modify UTC Date")
{
    _modifyUTC = value;
}


TypeScript Dictionary class I recently implemented a dictionary class in TypeScript. I'm still new to JavaScript so I'm curious what people think about it.

class Dictionary {
    public constructor ();
    public constructor (object: Object);
    public constructor (object?) {
        if (object != null) {
            for (let property in object) {
                if (object.hasOwnProperty(property)) {
                    this[property] = object[property];
                }
            }
        }
    }

    public clone(): Dictionary {
        let result = new Dictionary(this);
        return result;
    }

    public getKeys(): string[] {
        let result = [];
        for (let item in this) {
            if (this.hasOwnProperty(item)) {
                result.push(item);
            }
        }
        return result;
    }

    public getValues(): any[] {
        let result = [];
        for (let item in this) {
            if (this.hasOwnProperty(item)) {
                result.push(this[item]);
            }
        }
        return result;
    }

    public tryAddItem(key: string, value: any): boolean {
        let isAddItem = !this.hasOwnProperty(key) && typeof(value) !== 'undefined';
        if (isAddItem) {
            this[key] = value;
        }
        return isAddItem;
    }

    public tryUpdateItem(key: string, value: any): boolean {
        let isUpdateItem = this.hasOwnProperty(key) && typeof(value) !== 'undefined';
        if (isUpdateItem) {
            this[key] = value;
        }
        return isUpdateItem;
    }

    public tryDeleteItem(key: string): boolean {
        let isDeleteItem = this.hasOwnProperty(key);
        if (isDeleteItem) {
            delete this[key];
        }
        return isDeleteItem;
    }
}

I realized that objects in JavaScript act a lot like dictionaries so I'm basically just adding functionality to the object. I'm not sure how I would want to handle sorting. I think I would prefer to create a method that returned a sorted array or object based on some function. Similar to what a JavaScript Linq library would do.

Edit: I've updated the code and uploaded a gist that will work in the TS playground - the gist will compile with Typescript 3.1.

The primary benefit of Typescript is to provide types for Javascript. And since Typescript provides Generics - I don't think your implementation of a Dictionary provides any benefit over a plain javascript object.

In fact, as you noted in the comments, JS Objects (ie TS object) are dictionaries. You just need to provide types around them for your dictionary. (btw - I also come from a C# background, but I've also come to love the underlying functional nature of JS that TS lets us type).

Here's a code sample of the direction I would expect a Dictionary.ts class to have in a code base I work in. Now that we have Mapped Types, we can generalize dictionaries better.

export interface Dictionary<K, V> {
  getKeys(): K[];
  getValues(): V[];
  get(key: K): V | null; // the key might not exist
  put(key: K, val: V): void; // or boolean?
}

export class JSDictionary<K extends string, V> implements Dictionary<K, V> {

  private internalDict: { [key in K]?: V };

  constructor() {
    this.internalDict = {};
  }

  public getKeys() {
    let keys: K[] = [];
    for(let key in this.internalDict) {
      keys.push(key);
    }

    return keys;
  }

  // Type predicate to ensure v exists
  private exists(v: V | undefined): v is V {
    return v != null && typeof v !== "undefined";
  }

  public getValues() {
    let vals: V[] = [];

    for(let key in this.internalDict) {
      let v = this.internalDict[key];
      if(this.exists(v)) {
        vals.push(v);
      }
    }

    return vals;
  }

  public get(key: K) {
    let v = this.internalDict[key];
    return this.exists(v)
      ? v
      : null;
  }

  public put(key: K, val: V): void {
    this.internalDict[key] = val;
  }

}

Example Usage

type myKeys = 'FOX' | 'CAT' | 'DOG';

interface Animal {
  species: string;
  name: string;
  weight: number;
}

// A dictionary that hols one fox/cat/dog.
let myAnimalPen = new JSDictionary<myKeys, Animal>();

myAnimalPen.put('FOX', { name: 'Foxworth', species: 'Fox', weight: 40 });

// a dictionary that takes any string and maps it to a number
let idDict = new JSDictionary<string, number>();
idDict.put('somehas', 1204);
idDict.put('yeahaasd', 3306);

let yeaID = idDict.get('yeahaasd'); // yeaID is a number | null type
let myFox = myAnimalPen.get('FOX'); // myFox is an Animal | null type

Major points:

Code to an interface as much as you can in typescript. Affords you flexibility
Generic types
Transparent use of Plain JS object as the underlying dictionary (JS Engines optimize this very use case!)
I removed overloaded constructors, but you could add that back in with the proper types and it will work as expected
Left out clone - pretty easy to implement though
No exception handling when get returns null, like your 'try*' functions. I actually like try functions like you have, so you could mostly copy/paste, although with the stricter typings sometimes that will be taken care of by the compiler for you.


Refactor highlight matched word in string I have following method which highlight matched word in text:

# Hightlight matched term
#
# Ex(for term: some):
#   "Some CEO Event"
#
def highlight_matched(matched_word, text)
  regex = matched_word.gsub(/\*|\"|\'/, "")
                       .split(" ")
                       .map { |s| "\\b#{s}" }.join('|')

  text.gsub(/(#{regex})/i, '\1')
end

Is there a better solution for that?

I am using it here:

"%s %s" %[highlight_matched(title[0..70]), content_tag(:span, caption, class: 'search-type')]

If text may contain HTML (in that case text is a somewhat misleading variable name) you definitely should use a HTML parser. What about this? (adding a
 as wrapper, otherwise xpath won't find parent text nodes).

require 'nokogiri'

def highlight(html, word)
  Nokogiri::HTML::fragment("
" + html + "
").tap do |doc|
    doc.search('.//text()').each do |text_node|
      new_contents = text_node.text.gsub(/\b(#{word})\b/i, '\1')
      text_node.replace(new_contents)
    end
  end.xpath("p").inner_html
end

puts highlight('
Run Rabbit Run
', "run")
#
Run
# Rabbit Run


How can this functional implementation of Kadane's algorithm be improved? Some time ago I posted on Stack Overflow an imperative C# implementation of Kadane's algorithm for finding a subarray with maximum sum. Then I considered implementing the same functionally in F# and came up with the following:

let kadanes (xs: int []) =
    xs
    |> Array.mapi (fun i x -> (x, i))
    |> Array.fold (fun (partSum, partIdx, maxSum, startIdx, endIdx) (x, i) ->
                        let newPartSum, newPartIdx =
                            if partSum + x > x then (partSum + x, partIdx) else (x, i)
                        if newPartSum > maxSum then
                            (newPartSum, newPartIdx, newPartSum, newPartIdx, i)
                        else (newPartSum, newPartIdx, maxSum, startIdx, endIdx))
                        (0,0,xs.[0],0,0)
    |> fun (_, _, maxSum, startIdx, endIdx) -> (maxSum, startIdx, endIdx)

While the implementation above is functional and correct I cannot consider it easily understandable; in particular, dragging tuple of 5 elements through the fold seems rather ugly.

What can be done for improving this F# code?

Thank you.

A recursive function often works well in place of fold.

let kadanes xs =
  let rec loop (partSum, partIdx, maxSum, startIdx, endIdx) i =
    if i < Array.length xs then
      let x = xs.[i]
      let newPartSum, newPartIdx =
        if partSum + x > x then (partSum + x, partIdx) else (x, i)
      let maxSum, startIdx, endIdx =
        if newPartSum > maxSum then (newPartSum, newPartIdx, i)
        else (maxSum, startIdx, endIdx)
      loop (newPartSum, newPartIdx, maxSum, startIdx, endIdx) (i + 1)
    else (maxSum, startIdx, endIdx)
  loop (0,0,xs.[0],0,0) 0


Parsing NuGet packages.config with Parallel.ForEach Below is a file parser for old style nuget package configuration files. The Parallel.ForEach is probably overkill; in most cases its fast enough without. However, when using the parallel loop, can I avoid the need for the lock / shared list?

class Program
{
    private static readonly object _lock = new Object();
    private static readonly List<Package> _packages = new List<Package>();

    static void Main(string[] args)
    {
        string[] files = Directory.GetFiles(Directory.GetCurrentDirectory(), "packages.config", SearchOption.AllDirectories);

        Parallel.ForEach(files, GetPackagesForFile);

        IEnumerable<IGrouping<string, Package>> idGroups =
            _packages.GroupBy(p => p.Id).OrderBy(g => g.Key);

        foreach (IGrouping<string, Package> idGroup in idGroups)
        {
            IEnumerable<IGrouping<string, Package>> versionGroups = idGroup.GroupBy(p => p.Version);
            Console.WriteLine($"{idGroup.Key} ({versionGroups.Count()})");

            foreach (IGrouping<string, Package> versionGroup in versionGroups)
                Console.WriteLine($"\t{versionGroup.Key}");
        }
    }

    private static void GetPackagesForFile(string filepath)
    {
        var filePackages = XDocument.Load(filepath).Root.Elements("package").Select(GetPackageFromElement);
        lock(_lock) _packages.AddRange(filePackages);
    }

    private static Package GetPackageFromElement(XElement element) =>
        new Package(
            element.Attribute("id").Value,
            element.Attribute("version").Value,
            element.Attribute("targetFramework").Value);
}

If you want to do it this way then you need a lock but since the rest of your code is using Linq I would suggest you convert it over to PLINQ instead of using Parallel.ForEach,

Also you are iterating over the enumerable versionGroups twice. In your specific case it shouldn't cause an issue but that's not best practices with an IEnumerable.

First I'm going to change the GetPackagesForFile to return an array of Packages instead of using the static _packages field.

private static Package[] GetPackagesForFile(string filepath)
{
    return XDocument.Load(filepath).Root?.Elements("package").Select(GetPackageFromElement).ToArray() ??
           new Package[0];
}

I also changed it so to not throw a NullException if root not defined.  That's up to you if you want the exception there to tell you something was wrong or not.  So you might want to remove the ? and the ?? part if you want the exception to be thrown.

Now if you want to use PLINQ we just need to use the AsParallel() extension method. I'm going to use an anonymous class but you could create one if that's what you prefer.  Since I'm using an anonymous class I can't specify the type so going to use the var keyword, which doesn't match your coding style.

static void Main(string[] args)
{

    string[] files = Directory.GetFiles(Directory.GetCurrentDirectory(), "packages.config",
        SearchOption.AllDirectories);

    var idGroups = files.AsParallel()
        .SelectMany(GetPackagesForFile)
        .GroupBy(p => p.Id)
        .Select(g => new
        {
            Id = g.Key,
            Version = new HashSet<string>(g.Select(p => p.Version))
        }).OrderBy(p => p.Id);

    foreach (var idGroup in idGroups)
    {
        Console.WriteLine($"{idGroup.Id} ({idGroup.Version.Count})");

        foreach (string version in idGroup.Version)
            Console.WriteLine($"\t{version}");
    }
}

Since in your code all you care about is the distinct list of versions for each ID and the count I put them in a hashset instead of doing the grouping.  I could have used the g.Select(p => p.Version).Distinct().ToList() but just adding them to a hashset seems simpler code.

And in closing like you already stating making this parallel might be overkill.  If you want to test it compared to not being paralleled then you just need to remove the AsParallel() and the rest of the code can stay the same.


Monadic transformation on a list, done in three ways I am working my way through the Haskell Book and ran into the exercises at the end of the Monad chapter(18). One in particular asked to define a function with the following signature:

meh :: Monad m => [a] -> (a -> m b) -> m [b]

So I did. I found this routine difficult to implement at first, but once I understood what I was doing and what I needed to do a little better I figured it out.

I have three versions of the routine, my first attempt, a slightly refactored attempt, and a final attempt using do-notation. I was wondering if anyone can give advice on how I could potentially refactor this routine further, or how I can make my implementation better. I feel like I can make the routine far cleaner than I have it, but I am not sure how.

WARNING: If you are reading the Haskell Book and want to work through the exercises yourself, I recommend you do not read any further

Here are all three implementations

-- Attempt #1 with helper routine
meh :: Monad m => [a] -> (a -> m b) -> m [b]
meh list fn = doWork list (return $ []) fn
  where
    doWork (x:xs) base f
      | length xs == 0 = (addToMonad x base f) >>= (\x -> return $ reverse x)
      | otherwise = doWork xs (addToMonad x base f) f

addToMonad x baseMonad fn = do
  someVal <- (fn x)
  base <- baseMonad
  return $ someVal:base

-- Attempt #2 with a fold
meh' :: Monad m => [a] -> (a -> m b) -> m [b]
meh' list fn = (foldl (\acc x -> (fn x) >>= (\y -> acc >>= (\z -> return $ y:z))) (return $ []) list) >>= (\x -> return $ reverse x)

-- Attempt #3 with a fold and do-notation
mehDo :: Monad m => [a] -> (a -> m b) -> m [b]
mehDo list fn = do
  final <- (foldl (\acc x -> do
    val <- (fn x)
    mList <- acc
    return $ val:mList)
    (return $ []) list)
  return $ reverse final

I want to say my last implementation is the easiest to read (it would be easier with better names, IMO) but I don't really know that it is. I am not super experienced in the ways of Haskell, so to be frank I read the routines really slowly regardless.

Anyway, advice or tips on how to make this cleaner would be much appreciated.

I'd say that the idiomatic way to write this function in Haskell is by composing a more primitive one with a map. Indeed, given the type signature of meh, it is very tempting to "prepare" a list of all the m b actions and then combine them in order:

meh :: Monad m => [a] -> (a -> m b) -> m [b]
meh xs f = combine (f <$> xs)

Now, combine has type [m b] -> m [b]. To process that list, we can use a fold. You have used foldl in your examples but you ended up reversing the list which is a clear sign that you may have wanted a foldr instead. And we can indeed do that:

combine :: Monad m => [m b] -> m [b]
combine = foldr (\ x xs -> (:) <$> x <*> xs) (return [])

Here the functor (<$>) and applicative (<*>) combinators allow to write something that looks a bit direct style (we are basically using (:) to construct a list by giving its head and tail) but that takes care of the monadic actions.


Binary difference checker My code needs to take two ints and then check those ints to see if their binary representations have any differences. The function convertBits returns the number of differences between the two binary forms of the ints.

For example, you can change 31 to 14 by flipping the 4th and 0th bit:

31:  0 0 0 1 1 1 1 1
14:  0 0 0 0 1 1 1 0
---  ---------------
bit  7 6 5 4 3 2 1 0

Thus 31 and 14 should return 2.

My code works, but it is failing the time test. In short, it needs to be more efficient. I welcome any suggestions as to how to do this.

    import java.util.ArrayList;

    public class BinaryChecker {
        public static void main(String[] args){
             b call = new b();
             System.out.println(call.convertBits(31, 14));
        }

     public static int convertBits(int a, int b){
         int counter = 0;

         String A = Integer.toBinaryString(a);
         String B = Integer.toBinaryString(b);

         System.out.println("The binary value of " + a + " " + "is " +   A +"." + "The binary value of " + b + " " + "is " + B);
         //add to arraylist 1 and 2

         ArrayList<Character> String1 = new ArrayList<Character>();

         ArrayList<Character> String2 = new ArrayList<Character>();
         int size = 0;

         for(int i = 0; i < A.length(); i++){
             char Aa = A.charAt(i);
             String1.add(Aa);
         }
         for(int x = 0; x < B.length(); x++){
             char Bb = B.charAt(x);
             String2.add(Bb);
         }
         //check if String1 is 8 chars long and add 0 to beginning if not
         while (String1.size() != 8){
             String1.add(0, '0');
         }
         while (String2.size() != 8){
             String2.add(0, '0');
         }

         for (int i =0; i < String1.size(); i++){
             char biteA = String1.get(i);
             char biteB = String2.get(i);
             if(biteA != biteB){
                 counter++;
             }
         }

         return counter;
     }
}

There's no need to roll your own: the library support is there.

public static int convertBits(int a, int b) {
    return Integer.bitCount(a ^ b);
}

For what it's worth, I don't think convertBits is a very descriptive name for the method. I'd suggest something like countBitDifferences.


Object comparison method as an example of using the functional style I just started learning about functional programming, and thought I would have a look at writing a simple object comparer as the basis for my implementation. Below is my result.

My assumption (in writing) is that functional code is intended to not modify external state, and not have side effects. If I functional style correctly, pure functions are ones who operate only on their operands.

The link to all the source code is on GitHub in a public repo, which can be found here. The most relevant bits are below:

public class DifferenceBag
{
    public string PropertyName { get; }
    public PropertyInfo PropertyInfo { get; }
    public object LeftHandValue { get; }
    public object RightHandValue { get; }
}

The main object constructor is here:

    private const BindingFlags PublicPropertyBindingFlags = BindingFlags.Public | BindingFlags.Instance;

    private readonly ImmutableList<PropertyInfo> _properties;
    public ObjectComparer()
    {
        var propertySet = typeof(T).GetProperties(PublicPropertyBindingFlags);

        var builder = ImmutableList.CreateBuilder<PropertyInfo>();
        for (var i = 0; i < propertySet.Length; i++)
        {
            var immutable = propertySet[i].GetCustomAttribute<ImmutableAttribute>();

            if (immutable != null && immutable.IsTargetMutable)
            {
                builder.Add(propertySet[i]);
            }

            var ignore = propertySet[i].GetCustomAttribute<IgnoreCompareAttribute>();

            if (ignore != null && !ignore.SkipProperty)
            {
                builder.Add(propertySet[i]);
            }
        }

        _properties = builder.ToImmutable();
    }

And the primary method:

    public static readonly IEnumerable<T> EmptyBag = new T[0];
    public IEnumerable<DifferenceBag> Compare(T source, T target)
    {

        if (source == null)
            throw new ArgumentNullException(nameof(source));

        if (target == null)
            throw new ArgumentNullException(nameof(target));

        // If either target is null or our property bag list is empty,

        // then just bail.

        if (_properties.Count == 0)
            return EmptyBag;

        var list = new LinkedList<DifferenceBag>();
        foreach (var property in _properties)
        {

            var src = property.GetValue(source);
            var tgt = property.GetValue(target);

            // By calling object.Equals(object, object), we can avoid null-reference exceptions.
            if (!object.Equals(src, tgt))
                list.AddLast(new DifferenceBag(property.Name, src, tgt, property));
        }

        return list;
    }
}

So, ObjectComparer<T> acquires the property list during construction. This is state, but it's local to the comparer instance. That state is then used during the IEnumerable<DifferenceBag> Compare(T, T) routine.

So, my questions are:

Is this an example of functional design?
If not #1, then how could I refactor into a functional design?
Is there any benefit #2?

My interest in this topic is not constrained to the context of this object, but the context of patterns in general.

Functional and OO mix

This is kind of a mix of functional and OO programming because the class is carring a state. In a pure functional way you would provide the method with all it needs this means it would require the generic <T> parameter and it would be an extension:

public static IEnumerable<DifferenceBag> CompareTo<T>(this T source, T target)
{
    // perform the T reflection etc
}

or with pre-reflection you could have another function that takes a collection of properties that you want to compare:

public static IEnumerable<DifferenceBag> CompareTo<T>(this T source, T target, IEnumerable<PropertyInfo> properties)
{
    // perform the T reflection outside
}

this means you could later jus say:

var differences = foo.CompareTo(bar);

or

var comparableProperties = typeof(T).GetComparableProperties();
var differences = foo.CompareTo(bar, comparableProperties);

or even

var differences = foo.CompareTo(bar, GetComparableProperties);

if you designed the CompareTo method in such a way that it can take a Func for the reflection part:

public static IEnumerable<DifferenceBag> CompareTo<T>(this T source, T target, Func<T, IEnumerable<PropertyInfo>> getProperties)
{
    // perform the T reflection outside
}

where

static IEnumerable<PropertyInfo> GetComparableProperties<T>() {}

Implementation

You could improve the current implementatio to be more functional by using more LINQ. The Compare method could work like this

var differences =
    from p in _properties
    let pair = (left: p.GetValue(source), right: p.GetValue(target))
    where !pair.left.Equals(pair.right)
    select new DifferenceBag(p.Name, pair.left, pair.right, p);

if (_properties.Count == 0)
  return EmptyBag;

These lines are unnecessary because if there are not properties the resulting collection will be empty anwyway.

The extreme C# 7 solution could be implemented like this

public delegate IEnumerable<PropertyInfo> GetPropertiesCallback<T>();

public static IEnumerable<DifferenceBag> CompareTo<T>(
    this T source,
    T target,
    GetPropertiesCallback<T> getProperties)
    where T : class // required if you want to use "?? throw"
{
    var differences =
        from p in getProperties()
        let pair = (
            left: p.GetValue(source ?? throw new ArgumentNullException(nameof(source))),
            right: p.GetValue(target ?? throw new ArgumentNullException(nameof(source)))
        )
        where !pair.left.Equals(pair.right)
        select new DifferenceBag(p.Name, pair.left, pair.right, p);

    return differences;
}

Possible bug

var immutable = propertySet[i].GetCustomAttribute<ImmutableAttribute>();

if (immutable != null && immutable.IsTargetMutable)
{
    builder.Add(propertySet[i]);
}

var ignore = propertySet[i].GetCustomAttribute<IgnoreCompareAttribute>();

if (ignore != null && !ignore.SkipProperty)
{
    builder.Add(propertySet[i]);
}

If a property is decorated with both attributes you'll end up having it twice in the final list.


Article start exercise I've used encountered this exercise from a tutorial:

  Create a function that takes a string as a parameter and returns True if the initial word of the string passed is an article (“The”, “A”, “An”) and returns False if it isn't an article.

  Be careful, if the string starts with “There”, it does not start with an article.

I have written the following code for it:

def startsWithArticle(str):
    '''Return True if the first word of str is "The", "A" or "An"'''

    if(str.startswith("The") and str.find(' ')==3):
        return True
    elif(str.startswith("An") and str.find(' ')==2):
        return True
    elif(str.startswith("A") and str.find(' ')==1):
        return True

    return False

which works as expected. I tested it using:

print('"A boy" returned', startsWithArticle("A boy"))
print('"An apple" returned', startsWithArticle("An apple"))
print('"The cat" returned', startsWithArticle("The cat"))
print('"Abyss" returned', startsWithArticle("Abyss"))
print('"There" returned', startsWithArticle("There"))
print('"Ant" returned', startsWithArticle("Ant"))

and this gave the expected output:

"A boy" returned True
"An apple" returned True
"The cat" returned True
"Abyss" returned False
"There" returned False
"Ant" returned False

Is there anything to improve in the function? Do note that I'm a beginner in python. BTW, I'm using python 3.4.3

Style

Python has a style guide called PEP8 which is definitly worth a read.

A few things can be improved :

function name does not respect convention
missing whitespaces
useless parenthesis
name str hides builtin str

Then your code becomes :

def starts_with_article(string):
    '''Return True if the first word of string is "The", "A" or "An"'''

    if string.startswith("The ") and string.find(' ') == 3:
        return True
    elif string.startswith("An ") and string.find(' ') == 2:
        return True
    elif string.startswith("A ") and string.find(' ') == 1:
        return True

    return False

print('"A boy" returned', starts_with_article("A boy"))
print('"An apple" returned', starts_with_article("An apple"))
print('"The cat" returned', starts_with_article("The cat"))
print('"Abyss" returned', starts_with_article("Abyss"))
print('"There" returned', starts_with_article("There"))
print('"Ant" returned', starts_with_article("Ant"))

Don't Repeat Yourself

You are doing the same thing multiple times. You could try to see what is similar and what changes and see if you can use a relevant data structures for the changing parts.

Here I stored the articles in a list to be able to iterate over them.

def starts_with_article(string):
    '''Return True if the first word of string is "The", "A" or "An"'''
    for article in ["The ", "An ", "A "]:
        if string.startswith(article) and string.find(' ') == len(article) - 1:
            return True

    return False

Don't repeat yourself (again)

You are looking for the article followed by a space and then you check if there is a space in the wanted position. There is no need for that check.

def starts_with_article(string):
    '''Return True if the first word of string is "The", "A" or "An"'''
    for article in ["The ", "An ", "A "]:
        if string.startswith(article):
            return True

    return False

Don't repeat yourself (again again)

I have to repeat the whitespace in the different elements of the list I a using. This is easy to forget if I ever need to add an article. Let's add the space as part of the logic.

def starts_with_article(string):
    '''Return True if the first word of string is "The", "A" or "An"'''
    for article in ["The", "An", "A"]:
        if string.startswith(article + ' '):
            return True
    return False

More Python good stuff

The any builtin seems to do what you are doing. Let's use it.

def starts_with_article(string):
    '''Return True if the first word of string is "The", "A" or "An"'''
    return any(string.startswith(article + ' ')
        for article in ["The", "An", "A"])

The best option: reading the documentation

If we look at the startswith documentation, we have:

  prefix can also be a tuple of prefixes to look for.

At that point, your problem is pretty much solved :-)


Avoiding redundant code using tkinter I'm trying to devise a tkinter gui, that, among others, lets users choose a 'working folder' and a 'destination folder (and there is more coming). I stripped the code to its bare functionality hereunder.
I found myself duplicating code for the selection of both the 'working folder' and the 'destination' folder. I came up with the solution to put these variables in a dictionary (I could pass them as mutable objects along with the lambda). Although it is a working solution, I have the feeling there is more standard way of achieving this objective.
My question therefore is: how can I make my _browsefile() function work whilst changing the value of self.working_dir and self.destination_dir, without using an artificial dictionary structure, hence avoiding duplicate code? This would implicate that I can generalize the _browsefile func somehow.
I have seen very advanced reusage features in text books, but currently this is out of my league. If I can learn to tackle this 'easy' one, it would possibly help me on my journey.
Thank you for giving me advice in doing it the Pythonic way...
import tkinter as tk
from tkinter import filedialog

class View():
    def __init__(self, parent):
        self.parent = parent

        self.gui_variables = {'working dir': '',
                              'destination dir': ''}

        self.menu()

    def menu(self):
        self.folder_button1 = tk.Button(self.parent, text="Choose Working Folder",
                                       command=lambda: self._browsefile(self.gui_variables['working dir']))
        self.folder_button1.pack()

        self.folder_button2 = tk.Button(self.parent, text="Choose Dest. Folder",
                                       command=lambda: self._browsefile(self.gui_variables['destination dir']))
        self.folder_button2.pack()

    def _browsefile(self, directory):
        answer = tk.filedialog.askdirectory()
        self.gui_variables[directory] = answer

if __name__ == '__main__':
    root = tk.Tk()
    View(root)
    root.mainloop()

Don't use a dictionary. You can just refer to the attrs of a class by their name. Something like:
import tkinter as tk
from tkinter import filedialog
from typing import Optional

class View:
    def __init__(self, parent: tk.Tk):
        self.parent = parent
        self.working_dir: Optional[str] = None
        self.dest_dir: Optional[str] = None

        self.menu('Working', 'working_dir')
        self.menu('Dest.', 'dest_dir')

    def menu(self, title: str, attr: str):
        def browse():
            setattr(self, attr, tk.filedialog.askdirectory())

        button = tk.Button(
            self.parent,
            text=f'Choose {title} Folder',
            command=browse,
        )
        button.pack()

if __name__ == '__main__':
    root = tk.Tk()
    View(root)
    root.mainloop()

Notes:

Do not add a () suffix to your class
Do not assign those buttons as members on your class
Centralize the creation of the buttons and the associated command
For the command handler, use a simple closure
To target a specific member variable, accept a parameter that's used with setattr
Use type hints


Custom map on `Array` I have the following problem:

Given an Array, apply a certain method x to each Array element (yielding a new Array), with the restriction that array elements which are nil, should be mapped to some default value. Method and default element are parameters. Example:
Array: ['abc',nil,'defg']
Method: :size
Default element: -1
Expected result: [3, -1, 4]

I implemented this by adding a method map_with to the Array class:
class Array
  def map_with(accessor, default_value=nil)
    map {|e| e.nil? ? default_value : e.send(accessor) }
  end
end

['abc',nil,'defg'].map_with(:size, -1)

I'm looking for an improvement of my current solution. Can the solution be improved in the following sense?

Provide the same result with simpler code
Make the function more flexible (more generally useful) by not adding too much code

My implementation is very similar to yours, with only a few small tweaks:

module Enumerable
  def map_with(accessor, default_value: nil)
    map { |e| e.respond_to?(accessor) ? e.send(accessor) : default_value }
  end
end

Use Enumerable, not Array, so that the method can be applied to other objects such as instances of Hash, Set, etc.
Use respond_to? rather than a type-check against nil, for better duck-typing robustness.
Use a named parameter, for improved code clarity.


Rotate image 90 degree clockwise recursively Previous question:

Rotate image 90 degree clockwise

In this code I have used tail recursive, which is bad. Time complexity is still \$O(N^2)\$, which is worse-case. The only good part is memory complexity.

How can I improve the recursive part of this code?

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

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

// for debug info
static size_t numTotalSwaps = 0;

template<typename T>
matrix<T> rotateImage(matrix<T>&& image, size_t row = 0, size_t column = 0)
{
    if (row == image.size())
    {
        std::cout << "\nNumber of total swaps: " << numTotalSwaps << '\n';
        return image;
    }

    if ( ++column == image.size() )
    {
        std::reverse(image[row].begin(), image[row].end());
        ++row;
        column = 0;
    }

    if (row != column && row < column)
    {
        ++numTotalSwaps;
        std::swap(image[row][column], image[column][row]);
    }

    return rotateImage(std::move(image), row, column);
}

int main()
{
    const size_t SIZE = 7;

    matrix<int> image(SIZE, std::vector<int>(SIZE));

    std::cout << "******* original image ******\n";

    int value = 0;

    for (auto&& i : image)
    {
        for (auto&& j : i)
        {
            std::cout << std::setfill(' ') << std::setw(3) << (j = value++) << ' ';
        }

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

    std::cout << "******* rotated image ******\n";

    for (const auto& i : rotateImage(std::move(image)))
    {
        for (const auto& j : i)
        {
            std::cout << std::setfill(' ') << std::setw(3) << j << ' ';
        }

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

Nitpicks

using matrix = std::vector<std::vector<T>>;

The standard is to capitalize names of user defined types, so matrix should be Matrix.  I may have misled you in my other review, so I edited it for clarity.

// for debug info
static size_t numTotalSwaps = 0;

While I understand that it can often be helpful to define a global variable to do some quick and dirty debugging, by the time that you are sending code out for code review, this should be gone.  You should be done debugging your code, so you can leave just the actual code.

What I would actually like to see here are the results.  Given a particular input, what is the output?

if (row == image.size())

This can be fragile.

if ( row >= image.size() )

By switching to the inequality, you can avoid a class of bugs where you start incrementing by more than one row at a time but don't update your gate condition.  The check costs the same either way, so you might as well do the more expansive check.

if (row != column && row < column)

This is redundant.  If row < column, then you know that row != column.

if ( row < column )

This is sufficient, as it covers both cases.

    std::reverse(image[row].begin(), image[row].end());
    std::swap(image[row][column], image[column][row]);

I find this harder to follow than just saying

    std::swap(image[row][column], image[image.size() - 1 - column][row]);

I'm not sure which performs better.  It might be worth profiling if that matters to you.

    for (const auto& j : i)
    {
        std::cout << std::setfill(' ') << std::setw(3) << j << ' ';

I don't know what i and j are here.

    for ( const auto& element : row )
    {
        std::cout << std::setfill(' ') << std::setw(3) << element << ' ';

Now I can easily see what I'm printing.  Using i and j didn't tell me what they actually were, but row and element do.

Move Semantics

matrix<T> rotateImage(matrix<T>&& image, size_t row = 0, size_t column = 0)
        return image;
    return rotateImage(std::move(image), row, column);
    for (const auto& i : rotateImage(std::move(image)))

This seems a bad place to use move semantics.  Note that the point of move semantics is to avoid doing a copy when you don't need to do so.  However, here it may create a copy that you don't need.  Note that your algorithm passes an rvalue reference to the function but returns an lvalue.  If each recursive call triggers a full copy on return, your algorithm goes from \$O(n^2)\$ to \$O(n^4)\$.

You might be able to fix this by saying

        return std::move(image);

This will turn the named variable image back into an rvalue reference.

We shouldn't need to pass by value inside the recursive function.  We can work with the actual matrix.  We need to make one copy at most to avoid changing the variable outside the function.

const Matrix<T> & rotateImage(Matrix<T> & image, size_t row = 0, size_t column = 0)
    return rotateImage(image, row, column);

And then insist outside

    Matrix<int> rotatedImage = std::move(image);
    for ( const auto& row : rotateImage(rotatedImage, 0, 0) )

This makes a more regular use of move semantics.  If there is an assignment function that uses move semantics, this will just work.

We also enjoy the speed advantages of working with a reference when dealing with the recursive function.  We don't have to worry if move semantics get used or not, as our function always passes a reference.  We don't force the caller to use std::move, which is more commonly used with an assignment or copy constructor.

At the same time, I added the starting row and column numbers back.  I don't think that the code will work without them.  It looks like they got lost in an edit.

Recursion

The normal advantage of using recursion is that it allows for a more elegant solution.  However, in this case, I don't think that it does.  Your iterative solution traversed the grid smoothly and understandably.  The recursive solution is more complex, as you have to transform the grid into a one dimensional object.

It's also problematic in that the caller has to understand more than it should about what's happening internally.  It has to call std::move and add the initial row and column numbers.  You can sort of fix this by providing two functions.  The first function for use by the caller.  The first function then calls the second function with the right arguments for the recursion.  The second function does the actual work.  Note that it makes sense for the second function to use references.  The first function could pass by value.  Calling with std::move would trigger move semantics on the copy constructor.

The problem with recursion is that it works by making use of the stack.  For each function call, you have to push the current state onto the stack.  However, most of the state doesn't change from call to call, so saving it is redundant.  Further, since this is tail recursion, we're done with the current state by the time that we save it.  A good compiler will optimize this out, but why not go ahead and do it yourself?

Rather than relying on the compiler to fix things, just write the iterative version.  Tail recursion will have a natural transformation into an iterative solution.  In this case, we can do even better.  The recursive solution maps the grid into a vector.  An iterative solution can work with a grid directly.


Callback on AlertDialog I am using an AlertDialog in Android, asking the user for some input. I would like do run some code when the user has finished entering her input.

Since an AlertDialog is asynchronous, my code is not waiting for it. Therefore, I decided to use a callback, as in the following sample code:

This is the interface: AlertDialogCallback

public interface AlertDialogCallback<T>
{
    public void alertDialogCallback(T ret);
}

The main activity implements the interface and calls the function creating the alert dialog:

public class MainActivity extends Activity implements AlertDialogCallback<String>

...

public void alertDialogCallback(String ret)
{
    ...
}

...

askForInput(this, this);

And the function creating the dialog has a final reference to the class that implements AlertDialogCallback (here MainActivity). It has to be final because of the nested anonymous class.

public static void askForInput(Context context, final AlertDialogCallback<String> callback)
{
    AlertDialog.Builder alert = new AlertDialog.Builder(context);

    alert.setTitle("Enter input");
    alert.setMessage("Please enter some input");

    // Set an EditText view to get user input
    final EditText input = new EditText(context);
    alert.setView(input);

    alert.setPositiveButton("Ok", new DialogInterface.OnClickListener()
    {
        public void onClick(DialogInterface dialog, int whichButton)
        {
            String value = input.getText().toString();

            callback.alertDialogCallback(value);
        }
    });

    alert.setNegativeButton("Cancel", new DialogInterface.OnClickListener()
    {
        public void onClick(DialogInterface dialog, int whichButton)
        {
            // Canceled.
        }
    });

    alert.show();
}

I would like to know if this is a bad design (and why), and also if there is some kind of design pattern that is commonly used for this purpose in Android(/Java?).

Indeed the recommended approach for this (or at least what I would recommend) is to use callback interfaces.

The most important aspect though is designing this interface. In this case you should be sure that you're passing everything you need. However, I think you can rename the method to onOK or okPressed or similar. You might also consider returning a boolean to determine whether or not the dialog should really be closed (the input might need to be validated before it is accepted?) (there are ways to stop an AlertDialog from closing, you can find more information in earlier StackOverflow questions).

Other comments:

You should use String resources properly, this will separate the code from the text neatly. Use the resource id's instead.

alert.setTitle(R.string.alertInputTitle);
alert.setMessage(R.string.alertInputMessage);

Some strings are actually included in Android by default, such as android.R.string.ok and android.R.string.cancel, use them when possible.

When you want the negative button to just close the dialog, you can actually pass null as the DialogInterface.OnClickListener.

alert.setNegativeButton(android.R.string.cancel, null);


Function that assigns names to a struct using strtok I worked around using strtok function so to assign first name and last name to a struct PERSONNE from a char *names[] array. It was not possible to directly modify the *names[] using strtok since it was throwing an exception.

This code works fine but the last loop shows a lot of '\n' until it reaches 10. I am unable to set the unused data in p1 to NULL. Is it bad practice to not set unused structure data to NULL?

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

#define u_short             unsigned short
#define u_int               unsigned int

#define bool                int
#define true                1
#define false               0

#define MAX                 10

typedef struct PERSONNE
{
    int id;
    char nom[MAX];
    char prenom[MAX];
}personne, *p_personne;

char *names[]={
                "HARRY JANDU",
                "LIBNI MACTAVISH",
                "DIMPLE CHOWDARI",
                "PRIYA MOHAN",
                NULL
            };

int main(void)
{
    int i, j;
    personne p1[10];
    memset(&p1, 0, sizeof(p1));       // doesn't set to 0
    for( i=0; i<sizeof(names); i++ )
    {
        if( names[i]==NULL )break;
        char *temp=NULL, *pch=NULL;
        temp=(char*)malloc(strlen(names[i]));
        strcpy(temp, names[i]);
        pch=strtok(temp, " ");
        strcpy(p1[i].prenom, pch);
        while( pch!=NULL )
        {
            strcpy(p1[i].nom, pch);
            pch=strtok(NULL, " ");
        }
    }

    printf("FIRST NAME\tLastName\n");
//  printf("%d\n", p1[0]);
    for( i=0; i<10; i++ )
    {
        if( p1[i].nom==0 )break;
        printf("%s\t\t%s\n", p1[i].prenom, p1[i].nom);
    }

    return 0;
}

I see some things that may help you improve your code.

Use whitespace to improve readability

Lines like this:

for( i=0; i<sizeof(names); i++ )

become easier to read with a bit more whitespace:

for (i = 0; i < sizeof(names); i++)

Prefer ++i to i++ in loops

There is not a big difference for most uses, but if you don't need to save the pre-incremented value, make it simple for both the reader and the compiler and say ++i.  This also will help when you start using C++ iterators which often only implement the prefix ++ operator.

Declare the loop exit condition at the top

The code currently contains these lines:

for (i = 0; i < sizeof(names); i++) {
    if (names[i] == NULL)
        break;

So the for loop claims that the loop exits when i >= sizeof(names) but the following line says we exit when names[i] == NULL.  In this program, only latter is actually used, so the loop should be written to reflect that:

for (i = 0; names[i] != NULL; i++) {

Similarly, the printing loop can be simplified:

for (i = 0; p1[i].prenom[0]; ++i) {
    printf("%s\t\t%s\n", p1[i].prenom, p1[i].nom);
}

Eliminate unused variables

Unused variables are a sign of poor code quality, so eliminating them should be a priority.  In this code, j is defined but not used. Your compiler is probably also smart enough to tell you that, if you ask it to do so.  Also, the code includes a number of unused #defines, one unused typedef and one unused struct member, all of which just add to clutter in the code.

Use only required #includes

The code has #include <time.h> but nothing from that header is used.  This clutters the code and makes it more difficult to read and understand.  Only include files that are actually needed.

Use const where practical

The current code does not  modify the names array, and so it should be declared const:

const char const *names[] = {

Use stdbool

Instead of defining your own values for true and false, you might consider instead using #include <stdbool.h> which defines true and false.  However, in this program, neither is used.

Free memory that you allocate

This program leaks memory because you have allocated space using malloc but never released with free.  That's bad practice.

Eliminate useless code

The code currently contains this loop:

while (pch != NULL) {
    strcpy(p1[i].nom, pch);
    pch = strtok(NULL, " ");
}

This has the effect of copying each word in the name and only saving the last one which is not very efficient.  See the next suggestion for a more efficient means.

Use the appropriate library function

Instead of copying the string and using strtok, I'd recommend that the code should use strchr.

for (i = 0; names[i] != NULL; i++) {
    char *pch = strchr(names[i], ' ');
    if (pch == NULL || pch-names[i] > MAX) {
        strncpy(p1[i].prenom, names[i], MAX);
    } else {
        strncpy(p1[i].prenom, names[i], pch-names[i]);
        strncpy(p1[i].nom, pch, MAX);
    }
    p1[i].nom[MAX-1] = '\0';
    p1[i].prenom[MAX-1] = '\0';
}

Note too, that this code uses the safer strncpy and also assures that each string is properly terminated with '\0'.

Make sure your data structures are big enough

With only 10 characters allocated for both nom and prenom, many names simply won't fit. "Ludwig van Beethoven" is one such example.

Eliminate return 0 at the end of main

Since C99, the compiler automatically generates the code corresponding to return 0 at the end of main so there is no need to explicitly write it.


Select member for comparison in sort or search This code is predicated on the notion that when sorting (or using a sorted collection of items, such as with std::lower_bound) you're usually comparing a single field in each object being sorted/searched.

So a typical sort might look something like:

// Sort by age
std::sort(people.begin(), people.end(),
    [](Person const &a, Person const &b) { return a.age < b.age; });

Or:

// sort by height, descending:
std::sort(people.begin(), people.end(),
    [](Person const &a, Person const &b) { return b.height < a.height; });

Although the lambda is cleaner than C++98 code, I'd really rather be able to specify something like by(height, descending). I haven't (yet) figured out a way to (quite) get to that ideal, but I think this gets us quite a bit closer:

#ifndef SORT_MEMBERS_H_
#define SORT_MEMBERS_H_

namespace sort {
    namespace detail {
        template <class FieldType, class RecordType>
        struct Desc {
            FieldType RecordType::*fn;
        public:
            Desc(FieldType RecordType::*fn) : fn(fn) {}

            bool operator()(RecordType const &a, RecordType const &b) {
                return b.*fn < a.*fn;
            }
        };

        template <class FieldType, class RecordType>
        struct Asc {
            FieldType RecordType::*fn;
        public:
            Asc(FieldType RecordType::*fn) : fn(fn) {}

            bool operator()(RecordType const &a, RecordType const &b) {
                return a.*fn < b.*fn;
            }
        };
    }

    template <class FieldType, class RecordType>
    detail::Asc<FieldType, RecordType> ascending(FieldType RecordType::*b) {
        return detail::Asc<FieldType, RecordType>(b);
    }

    template <class FieldType, class RecordType>
    detail::Desc<FieldType, RecordType> descending(FieldType RecordType::*b) {
        return detail::Desc<FieldType, RecordType>(b);
    }
}

#endif

Example usage would be something like this:

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include "sort_members.h"

struct Person
{
    std::string first_name;
    std::string last_name;
    int age;

    friend std::ostream &operator<<(std::ostream &os, Person const &person) {
        return os << person.first_name << " " << person.last_name << ", " << person.age;
    }
};

int main() {
    std::vector<Person> people = {
        { "John", "Rambo", 42 },
        { "Joffrey", "Baratheon", 14 },
        { "Kyle", "Reese", 25 }
    };

    std::sort(people.begin(), people.end(), sort::descending(&Person::age));

    std::cout << "Sorted by age, descending:\n";
    for (const auto& person : people)
        std::cout << person << "\n";

    std::cout << "\nSorted by last name:\n";
    std::sort(people.begin(), people.end(), sort::ascending(&Person::last_name));
    for (const auto& person : people)
        std::cout << person << "\n";
}

I'd welcome any comments--but I'm mostly interested in the part in the header; the file using it is just a demo, not anything very interesting in itself, beyond the fact that it demonstrates how the preceding code is used.

This might be a bit nitpicky, but Asc and Desc aren't that good of names for classes. Granted, they are in your detail namespace, so it should be fine, but why not just write out the names Ascending and Descending?

I do find Asc more ambiguous than Desc, because I see "desc" as shorthand for "descending" more often.

Both Desc and Asc are structs, which means that your public: is redundant. You probably want to make them classes, as it seems you want to hide the fn member variable.

Why restrict the sort-by function to being by member variables? You could easily let it work for any callable object:

template <class F>
class Asc {
    F fn;
public:
    Asc(F fn) : fn(std::move(fn)) {}

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        // by separating the types like this, we gain a little bit
        // of generality. Not that it matters if we are using it
        // with std::sort only. However, really what the overall
        // utility is doing is defining a comparator, so you might
        // want to keep it more general
        return fn(std::forward<Lhs>(a)) < fn(std::forward<Rhs>(b));
    }
};

I know that, at this point, this removes the ability to use member functions at all, but we can use std::invoke to remedy that:

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return std::invoke(fn, std::forward<Lhs>(a)) < std::invoke(fn, std::forward<Rhs>(b));
    }

Although std::invoke does require C++17. If you don't want to require C++17, this Stack Overflow question discusses how to get the behavior of std::invoke in C++11. In particular, you can use std::ref:

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return std::ref(fn)(std::forward<Lhs>(a)) < std::ref(fn)(std::forward<Rhs>(b));
    }

Although you may want to wrap the std::ref(callable)(args...) into a utility function to make the code more self-documenting

There's also a small problem, where if the field we are sorting by is a pointer, you can have undefined behavior. Comparing pointers with operator< is only allowed if the pointers are from the same array. So it would be better to use std::less:

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return std::less<>()(std::ref(fn)(std::forward<Lhs>(a)), std::ref(fn)(std::forward<Rhs>(b)));
    }

But if you don't have C++14, you'd have to write something like this instead:

    template <typename T>
    bool operator()(T const& a, T const& b) {
        auto cmp = std::less<
            std::decay_t<decltype(std::ref(fn)(a))>
        >();
        return cmp(std::ref(fn)(a), std::ref(fn)(b));
    }

Also, we can actually combine both Asc and Desc. Currently, the only difference is that you call operator< with the arguments in the other order.

Instead, what we can do is take a comparator in our class:

template <class F, class Compare = std::less<>>
class SortBy {
    F fn;
    Compare cmp;
public:
    SortBy(F fn, Compare cmp = {})
        : fn(std::move(fn))
        , cmp(std::move(cmp))
    {}

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return cmp(
            std::invoke(fn, std::forward<Lhs>(a)),
            std::invoke(fn, std::forward<Rhs>(b))
        );
    }
};

Then, you can reduce your ascending and descending functions down to a single function:

template<typename F, typename Compare = std::less<>>
SortBy<F, Compare> sort_by(F fn, Compare cmp = {}) {
    // by using uniform initialization, we don't have to repeat the
    // type of SortBy<...>
    return { std::move(fn), std::move(cmp) };
}

If the user wanted to sort descending, they'd have to use sort_by(..., std::greater<>). That does require that an operator> is defined for their type, but they can always define their own comparator that defines a greater-than by using operator<

Orthogonally, splitting the Lhs and Rhs arguments for the operator() makes our SortBy a transparent comparator, so we should indicate this by adding a is_transparent typedef:

template <class F, class Compare = std::less<>>
class SortBy {
    F fn;
    Compare cmp;
public:
    using is_transparent = void;

    SortBy(F fn, Compare cmp = {})
        : fn(std::move(fn))
        , cmp(std::move(cmp))
    {}

    template <typename Lhs, typename Rhs>
    bool operator()(Lhs&& a, Rhs&& b) {
        return cmp(
            std::invoke(fn, std::forward<Lhs>(a)),
            std::invoke(fn, std::forward<Rhs>(b))
        );
    }
};


PHP MySQLI Insert Command Can you please provide a general review the following PHP code (with MySQLi)?

The query involves an INSERT INTO statement:

public function __i($table, $arr) { $c=$this->connection;
   foreach ( $arr as $name => $val):
      $param1.=$name . ",";
      $param2.="?,";
   endforeach;

   $PARAM1 = substr_replace($param1, '', -1);
   $PARAM2 = substr_replace($param2, '', -1);

   $query = 'INSERT INTO '.$table.' ('.$PARAM1.') VALUES ('.$PARAM2.')';

   echo $query;
   foreach ( $arr as $name => $val):
    if ( is_int($val)) :
         $param = 'i';
      endif;

      if ( is_string($val)) :
         $param = 's';
      endif;

      if ( is_double($val)) :
         $param = 'd';
      endif;
      $binds.=$param;
      $values.="'".$arr[$name]."',";

    endforeach;

    $values = substr_replace($values, '', -1);
    echo "BINDS ARE: ".$binds . "
";
    echo "VALUES ARE: ".$values."
";

   if ( $s = $c->prepare($query)):

      $args = $binds + $values;
      call_user_func_array(array($s, 'bind_param'), array($binds, $values));
      $s->execute();
      $s->close();
   endif;

}

Well, there's no context, so I can't be sure of exactly what you want, so I will assume a general review. In the future, please provide a little intro, even if its only to say, "please review and tell me how I can do better." Just dumping code is rather vague, for instance, this question could just as easily been about a better way to insert, of which I have no idea.

First, your method and variable names could use some work. What is __i()? A little more descriptive please. I can assume, based on the title of this post that this is an insert() method, but without any context this would be very difficult to determine. Additionally, I would avoid using double-spaced method names, those are usually reserved for PHP magic methods, such as __construct(). A single space is good enough, though that usually refers to a private or protected method.

Start your method's body on a newline, rather that the same one that the method was started on. I don't know if this was just a formatting issue with SO, or if its actually like that in your code. And, as above, what is $c? Connection can be inferred, but anyone reading this should not have to guess. $conn is a typical shortening and is widely accepted. Or you could spell it out completely, or use the root word "connect". As long as its somehow logically connected with the intent.

public function __i($table, $arr) {
    $conn = $this->connection;

Why are you using the standard template syntax for your statements and loops? In templates (Views or HTML files with PHP in them) this is fine, but it is quite odd and a little difficult to read in normal class structures. The preferred method is to use normal syntax, like so:

if() {
}
//AND
foreach() {
}

Where did $param1 and $param2 come from? They were not passed in as parameters to the method, which makes their names a little confusing. I would assume these are either globals, which are bad, or just undefined variables, which are also bad. If the later, then on the first iteration of this foreach loop those two variables will produce warnings about not being defined, or, god forbid, should there be globals assigned with those names, then you might just start appending on to them. To prevent this kind of mistake, it is best to define them before trying to use them. Also, any variable with a number after it is typically frowned upon. Use that variable's intent to better name them.

$param1 = '';
//etc...
$param1 .= $name . ",";

I know what these two substr_replace() lines are for, but they might be a little confusing to others. Perhaps a better method would be to use rtrim() to explicitly remove the last comma. This will make it more obvious what you are trying to do, and slightly decrease the size of that line. I don't know if its any faster or slower, but I don't think the difference will matter much here.

$PARAM1 = rtrim( $param1, ',' );

Your $param is not always set. This means that should $val not be an int, string, or double, then it will use the last known value of $param from the previous iteration. This can result in unforeseen results. Instead, you should either set up a default value or use an if/elseif/else structure. Here's a simple example assuming string as a default, you can always extend else in the following example to another elseif and use a final else to throw an error if you don't want to default.

if( is_int( $val ) ) {
    $param = 'i';
} elseif( is_double( $val ) ) {
    $param = 'd';
} else {
    $param = 's';
}
//which can easily be rewritten to use a default as
$param = 's';
if( is_int( $val ) {
    $param = 'i';
} elseif( is_double( $val ) ) {
    $param = 'd';
}

Don't define a variable in an if statement. It is too easy to accidentally do so when you don't mean to and will not always be obvious that you did not mean to perform a comparison instead.

$s = $c->prepare( $query ):
if( $s ) {
    //etc...
}

I'm not really sure how I feel about the call_user_func_array(), It could be a little confusing to someone who's never seen it before, but that's your call.

Finally, you might want to break up this method into multiple smaller methods. Use the Single Responsibility and "Don't Repeat Yourself" (DRY) Principles as a guideline. For example, to help you get started you can move that first foreach loop and those two substr_replace() lines into a new method called getParams() or something more aptly named. This will make it easier to reuse this code should you ever need to and make it easier to read.