Project Euler 21: Sum of amicable numbers optimisation Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
  If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

  For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

  Evaluate the sum of all the amicable numbers under 10000.

I have the following code which I know works, but is very slow for large numbers.

import time
start = time.time()

n = int(input("Enter a number"))

def factor(c):
    factors = []
    for d in range(1, int(c / 2) + 1):
        if c % d == 0:
            factors.append(d)
    return sum(factors)

def sum_ammicable(x):
    ammicable = set()
    for a in range(1, x):
        for b in range(1, x):
            if a != b:
                if factor(a) == b and factor(b) == a:
                    ammicable.update([a,b])
    return sum(ammicable)

print(sum_ammicable(n))

end = time.time()
print(end -start)

How can I optimise this code

Integer Division

Python comes with a built-in integer division operator.  So instead of writing int(c / 2) + 1, you could simply write c // 2 + 1.  It is slightly faster.

Unnecessary List Creation

Creating a list of factors just to sum(factors) afterwards is unnecessary busy work, which takes time.  Simply add up the factors as you find them:

def factor(c):
    total = 0
    for d in range(1, c // 2 + 1):
        if c % d == 0:
            total += d
    return total

Or, use a generator expression with sum():

def factor(c):
    return sum(d for d in range(1, c // 2 + 1) if c % d == 0)

There is no need to store the factors you found.

Move Invariants out of Loops

Consider:

def sum_ammicable(x):
    ...
    for a in range(1, x):
        for b in range(1, x):
            if a != b:
                if factor(a) == b and ...:
                    ...
    ...

How many times is factor(a) computed when a==1?  If x == 10000, it gets computed 10000 times ... once for each b value.  How many times when a==2?  It'll get computed 10000 times as well.  But does factor(a) depend on the value of b?  No.  Each time you compute factor(a), for the same value of a, the same result is produced.

Can you calculate this value once per a loop?  Sure!  Move it out of the b loop!

def sum_ammicable(x):
    ...
    for a in range(1, x):
        factor_a = factor(a)
        for b in range(1, x):
            if a != b:
                if factor_a == b and ...:
                    ...
    ...

Instead of computing factor(a) 100,000,000 times, you now only compute it 10,000 times, which should be a significant improvement in speed.

Finally, considering that:

        for b in range(1, x):
            ...
                if factor_a == b and ...:
                    ...

will only execute the rest of the if statement (and perhaps the body of the if) for exactly one value of b, do you really need to loop over all 10,000 possible b values?  With a little thought, and a little reworking of the code, you can remove the b loop altogether!

Group Related Code Together

You start with

start = time.time()

n = int(input("Enter a number"))

then 2 function definitions, and then you continue with mainline code:

print(sum_ammicable(n))

end = time.time()
print(end -start)

Move the code together, after the function declarations.  Even better, place it inside a if __name__ == '__main__': guard, so you can import factor(c) and sum_ammicable(x) functions into other code:

if __name__ == '__main__':

    start = time.time()

    n = int(input("Enter a number"))

    print(sum_ammicable(n))

    end = time.time()
    print(end - start)

Now that this code isn't separated by 2 functions, it becomes apparent you are timing how long the user takes to "Enter a number" in addition to the time it takes to compute sum_ammicable(n).  Is the user's reaction & typing speed really being profiled here?  Perhaps you want to move start = time.time() after the input statement.

Pro tip: use time.perf_counter() instead of time.time() for higher accuracy profiling.

Algorithmic improvements are covered on the Project Euler site itself.  Read the problem overview after successfully completing the problem for some additional dramatic improvements.  There is no need to reproduce their analysis here.

The following is an updated version of my code:

import time
import math

# finds the sum of the proper divisors of a number c

def factor(c):
    sum_of_factors = 1
    if type(math.sqrt(c)) is int:
        sum_of_factors += math.sqrt(c)
    for d in range(2, int(math.sqrt(c)) + 1):
        if c % d == 0:
            sum_of_factors += d + (c / d)
    return sum_of_factors

# finds sum of amicable numbers

def sum_amicable(x):
    amicable = 0
    for a in range(1, x):
        b = factor(a)
        if a != b and factor(a) == b and factor(b) == a:
            amicable += (a + b) / 2
    return amicable

n = int(input("Enter a number"))

start = time.time()

print(sum_amicable(n))

end = time.time()
print(end - start)

I found the answer in 0.16054987907409668 seconds


Sieve of Eratosthenes For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation.

I would like to hear some suggestions for improvements, especially how to make it more efficient and readable (sometimes there are trade offs) and how to follow good Java conventions. Also, suggestions on issues from naming conventions to proper javadoc are welcome as well. I'm just trying to improve my programming skills.

Incidently, the sieveOfEratosthenes method below is big O(?).

/**
 * returns a boolean array for prime numbers
 * @param max the maximum value to search for primes
 * @return boolean array of integers with primes true
 */
public boolean[] sieveOfEratosthenes(int max){

    boolean[] primeCandidates = new boolean[max]; //defaults to false
    for(int i=2; i<max; i++ ){primeCandidates[i]=true;}

    for(int i=2; i<Math.sqrt(max);i++){
        if(primeCandidates[i] == true){
            //all multiples of i*i, except i, are not primeCandidates
            for(int j = i + i; j<max; j=j+i){
                primeCandidates[j]=false;
            }
        }

    }
    return primeCandidates;
}

/**
 * print the index number for all true in given array
 * @param a boolean array
 */
public void printTrue(boolean[] arr){
    for(int i=0; i<arr.length; i++){
        if(arr[i]==true){
            System.out.print(i + ", ");
        }
    }
}

Input checking is missing. You should throw an IllegalArgumentException if max is less than zero instead of the NegativeArraySizeException.

Result of Math.sqrt(max) doesn't change, so maybe it's would worth to extract out to a local variable but maybe the JVM already optimize this for you.

Anyway, it's fine. I made some renaming and formatting, here is the result:

public boolean[] sieveOfEratosthenes(final int max) {
    if (max < 0) {
        throw new IllegalArgumentException("max cannot be less than zero: " + max);
    }
    final boolean[] primeCandidates = new boolean[max]; // defaults to false
    for (int i = 2; i < max; i++) {
        primeCandidates[i] = true;
    }

    final double maxRoot = Math.sqrt(max);
    for (int candidate = 2; candidate < maxRoot; candidate++) {
        if (primeCandidates[candidate]) {
            for (int j = 2 * candidate; j < max; j += candidate) {
                primeCandidates[j] = false;
            }
        }

    }
    return primeCandidates;
}

Since there are fewer primes, you could use a list of some kind to hold the prime numbers.

For every prime number n greater than 3,

n mod 6 = 1 or n mod 6 = 5.

If you could somehow not check other numbers for prime, you might save on some primeness checking.


Check whether address criteria contain only certain fields or more I have a method that checks whether an addressCriteria contains only certain fields or more.  If it contains more fields, it should return false, otherwise true.

I'm uncertain what the best way to write my if statement is. As far as I can tell, I see 2 options:

Write them in 1 if statement
Write each check in a different if statement

Single if statement:

private boolean isShortAddress(AddressCriteria addressCriteria) {
  if((null != addressCriteria.getCity() && !addressCriteria.getCity().isEmpty()) ||
      (null != addressCriteria.getNumber() && !addressCriteria.getNumber().isEmpty()) ||
      (null != addressCriteria.getState() && !addressCriteria.getState().isEmpty()) ||
      (null != addressCriteria.getZipCode() && !addressCriteria.getZipCode().isEmpty())) {
    return false;
  }

  return true;
}

Multiple if statements:

private boolean isShortAddress(AddressCriteria addressCriteria) {
  if(null != addressCriteria.getCity() && !addressCriteria.getCity().isEmpty()) {
    return false;
  }

  if(null != addressCriteria.getNumber() && !addressCriteria.getNumber().isEmpty()) {
    return false;
  }

  if(null != addressCriteria.getState() && !addressCriteria.getState().isEmpty()) {
    return false;
  }

  if(null != addressCriteria.getZipCode() && !addressCriteria.getZipCode().isEmpty()) {
    return false;
  }

  return true;
}

Maybe there's a 3rd or 4th option that I am unaware of?

I would be compelled to write a helper that accepts a variable number of address fields and and returns true if all of the address fields are not null and not empty.

private boolean isShortAddress(AddressCriteria addressCriteria) {

  return hasFields( addressCriteria.getCity(),
                    addressCriteria.getNumber(),
                    addressCriteria.getState(),
                    addressCriteria.getZipCode() );
}

private boolean hasFields( addressField... args )
{
  for( addressField arg:args)
  {
    if( null == arg || arg.isEmpty() )
      return false;
  }
  return true;
}

I did not test this code, but you should catch the drift.

First, if (null != thing) can and should always be simplified to if (thing).
(Similarly, if (null == thing) can and should always be simplified to if (!thing).) EDIT: Apparently you can't do that in Java, OK (bleah).  You should still know that this is preferred style in several closely-related languages where you can do that.

Second, as several other people have pointed out, you have a repeated condition that should be factored into an isNullOrEmpty helper function.

Third, the construction

if (condition)
    return true;
return false;

is usually better written

return condition;

Putting it all together, we get

boolean isNullOrEmpty(String s)
{
    return s == null || s.isEmpty();
}

// ...

return (isNullOrEmpty(addressCriteria.getCity())   ||
        isNullOrEmpty(addressCriteria.getNumber()) ||
        isNullOrEmpty(addressCriteria.getState())  ||
        isNullOrEmpty(addressCriteria.getZipCode()));

Editorial aside: It is a bad code smell that the addressCriteria getters can return either null or an empty string.  They should consistently pick one or the other to represent the absence of that field.  However, you say that class can't be modified, so file that under "technical debt" and move on.


Disproving Euler proposition by brute force in C I wrote a little bit of code to brute force disprove the Euler proposition that states:

  $$a^4 + b^4 + c^4 = d^4$$

  has no solution when \$a\$, \$b\$, \$c\$, \$d\$ are positive integers.

I'm no mathematician, but reading around this, at least one solution was found by Noam Elkies in 1987 (a = 95800; b = 217519; c = 414560; d = 422481). I wanted to get an idea of how much firepower it would take to solve by brute force, so I wrote the following in C:

#include <stdio.h>
#include <time.h>
#include <math.h>

int prop(long int A, long int B, long int C, long int D) {
    return (pow(A, 4) + pow(B, 4) + pow(C, 4) == pow(D, 4));
}

int main() {
    long int a, b, c, d;
    clock_t t;
    t = clock();

    for (a = 1; a < 100000; a++) {
        for (b = 1; b < 300000; b++) {
            for (c = 1; c < 500000; c++) {
                for (d = 1; d < 500000; d++) {
                    if (prop(a, b, c, d))
                        printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd = %ld\n", a, b, c, d);
                }
                if (!(c%1000))
                    printf("a = %ld, b = %ld, c = %ld, time = %fs\n", a, b, c, ((double)(clock() - t))/CLOCKS_PER_SEC);
            }
            printf("a = %ld, b = %ld, time = %fs\n", a, b, ((double)(clock() - t))/CLOCKS_PER_SEC);
        }
        printf("a = %ld, time = %fs\n", a, ((double)(clock() - t))/CLOCKS_PER_SEC);
    }

}

I ran it for a while, and worked out that it would take roughly \$85 \times 10^6\$ years for it to get to the answer above on my current machine.

I mean, maybe if I waited a few thousand years, I'd have a slightly better machine, but my question is (and I am new to C and computer science in general - so please be gentle); what strategies could I take to make the above code run faster? I thought about threading, and using some sort of bit shifting in place of the pow() calls.

Would there be any way (on my current machine) to get this to run in my lifetime?

Note: At some point, this review drifted into the realm of assembler and GMP. An actual review is at the end of this post, whereas the first section discusses the runtime-problems concerning pow, wrong data types and arbitrary large integers.

No life time for run time

  Would there be any way (on my current machine) to get this to run in my lifetime?

There's a great saying in carpentry: measure twice, cut once. It concerns cutting wood or other material, where you have to throw away your resources if you accidentally cut at the wrong place.

A similar saying is there for software engineers: you can't optimize what you can't measure. There are several ways to measure your code, e.g. benchmarking, profiling, or looking at the generated assembler to see how many instructions a certain part of your code will take.

Here, we will take the latter route, start with the assembler, take considerations step by step and see where we end up.

A study in assembly

Lets have a look at your code. Well, not yours, but the assembler the compiler generates. You can use gcc -S -O3. On my platform, this results in the following "hot" section in main:

.L6:
        add     rbx, 1
        cmp     rbx, 500000
        je      .L18
.L8:
        mov     rax, QWORD PTR .LC0[rip]
        movsd   xmm0, QWORD PTR [rsp+40]
        movq    xmm1, rax
        call    pow                        ; (1)
        mov     rax, QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+8], xmm0
        movsd   xmm0, QWORD PTR [rsp+48]
        movq    xmm1, rax
        call    pow                        ; (2)
        mov     rax, QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+16], xmm0
        movsd   xmm0, QWORD PTR [rsp+32]
        movq    xmm1, rax
        call    pow                        ; (3)
        mov     rax, QWORD PTR .LC0[rip]
        movsd   QWORD PTR [rsp+24], xmm0
        pxor    xmm0, xmm0
        cvtsi2sd        xmm0, rbx
        movq    xmm1, rax
        call    pow                        ; (4)
        movsd   xmm2, QWORD PTR [rsp+8]
        addsd   xmm2, QWORD PTR [rsp+16]
        movapd  xmm1, xmm0
        movsd   xmm0, QWORD PTR [rsp+24]
        addsd   xmm0, xmm2
        ucomisd xmm0, xmm1
        jp      .L6
        jne     .L6

Even though you might not know assembler, you can see those four calls to pow. The first thing you need to know is that call is slow compared to those other operations. Those four calls happen in the innermost loop. The compiler removed the call to prop and instead replaced it by its code (that's faster).

mov* assigns values to registers, add* adds values, and so on. The registers with xmm* are double precision registers, meant for double variables. So we're basically calling pow with the right values and then add, subtract and modify our small little double values.

Double trouble

But wait a second. We're trying to solve a completely integral problem! Why does our generated program use those registers at all?

This should raise a red flag. And indeed, if we remember pow's signature, it should be clear that it's not the right tool. It takes a double base and exponent, which indicates that it's suitable for terms like \$15.12151^{3.1415926}\$. This is a total overkill for your problem.

Using proper functions

So let's use another pow version instead:

long int pow4(long int x){
    return x * x * x * x;
}

Note that your compiler should create something like this from that:

movq    %rdi, %rax
imulq   %rdi, %rax
imulq   %rax, %rax
ret

but if your compiler doesn't recognize this potential (micro) optimization, you can use

long int pow4(long int x){
    const long int t = x * x;
    return t * t;
}

instead.

We also need to change prop:

int prop(long int A, long int B, long int C, long int D) {
  return (pow4(A) + pow4(B) + pow4(C) == pow4(D));
}

Allright. Now, before I show the times of the new program, let's check the output of your old one:

a = 1, b = 1, c = 1000, time = 114.156000s

That's when I hit ^C. How does the one using pow4 hold up?

a = 1, b = 1, c = 1000, time = 0.296000s
a = 1, b = 1, c = 2000, time = 0.578000s
a = 1, b = 1, c = 3000, time = 0.859000s
a = 1, b = 1, c = 4000, time = 1.140000s
a = 1, b = 1, c = 5000, time = 1.421000s
a = 1, b = 1, c = 6000, time = 1.703000s
a = 1, b = 1, c = 7000, time = 1.984000s
a = 1, b = 1, c = 8000, time = 2.265000s
a = 1, b = 1, c = 9000, time = 2.546000s
a = 1, b = 1, c = 10000, time = 2.828000s
a = 1, b = 1, c = 11000, time = 3.109000s
a = 1, b = 1, c = 12000, time = 3.390000s
a = 1, b = 1, c = 13000, time = 3.687000s
a = 1, b = 1, c = 14000, time = 3.968000s
a = 1, b = 1, c = 15000, time = 4.250000s
a = 1, b = 1, c = 16000, time = 4.531000s

Which is 0,2% of your original time, or a 500x speedup.

However, this comes at a cost: pow4(500000) is too large for a int64_t, since \$\log_2(500000^4) \approx 76\$. The greatest number you could check with a uint64_t is 65535, \$2^{16}-1\$, which shouldn't be very surprising. As the standard does not provide int128_t or similar, you should make sure that your numbers don't exceed those bounds.

You can either write your own large integer logic for this, or use GMP.

Proper bounds and parameter estimation

Next up, you can increase the lower bounds of b and c, so that \$a \le b \le c\$. And for d, well, if we have a, b, c, then there is only one solution for d. We can directly search for that solution with binary search.

The binary search makes a \$\mathcal O (n^3 \log n)\$ algorithm from your current \$\mathcal O (n^4)\$ one, which should provide a lot more speed than the previous speedup.

Even better, if you used the appropriate bounds for a, b and c, we can bound d by

$$d^4 = a^4 + b^4 + c^4 \le c^4 + c^4 + c^4 = 3c^4$$

and therefore get

$$c \le d \le \sqrt[4]{3}\,c.$$

With the proper binary algorithm,you can finish the first a=1,b=1 case quickly:

…
a = 1, b = 1, c = 481000, time = 0.031000s
a = 1, b = 1, c = 482000, time = 0.031000s
a = 1, b = 1, c = 483000, time = 0.031000s
a = 1, b = 1, c = 484000, time = 0.031000s
a = 1, b = 1, c = 485000, time = 0.031000s
a = 1, b = 1, c = 486000, time = 0.031000s
a = 1, b = 1, c = 487000, time = 0.031000s
a = 1, b = 1, c = 488000, time = 0.031000s
a = 1, b = 1, c = 489000, time = 0.031000s
a = 1, b = 1, c = 490000, time = 0.031000s
a = 1, b = 1, c = 491000, time = 0.031000s
a = 1, b = 1, c = 492000, time = 0.031000s
a = 1, b = 1, c = 493000, time = 0.031000s
a = 1, b = 1, c = 494000, time = 0.031000s
a = 1, b = 1, c = 495000, time = 0.031000s
a = 1, b = 1, c = 496000, time = 0.031000s
a = 1, b = 1, c = 497000, time = 0.031000s
a = 1, b = 1, c = 498000, time = 0.031000s
a = 1, b = 1, c = 499000, time = 0.031000s
a = 1, b = 1, time = 0.031000s

Which brings us back into the realm of your lifetime.

Exercise

Write a function, that given a, b and c checks whether there exist a d, such that your property holds. It should return -1 if there does not exist such a d, and the d otherwise.

Use that function in your code. Make sure that you need roughly \$\log d_{\text{max}}\$ iterations in that function.

Important remark about integer sizes

Keep in mind that long int is usually just a 64 bit integer, which means that the largest integer you can store is \$2^{63}-1\$. Integer types with more bits have greater bounds, but are platform specific. Also, multiplication can be a tad slower, since multiplying 128bit numbers isn't as easy as multiplying 64bit numbers.

See the next section how to get multiplications down.

An actual review

Our pow4 is now essentially two multiplications. However, we're still using pow4 too often. After all, we don't need to recalculate \$a^4\$ in every iteration. The compiler happily does, since it doesn't optimize aggressively enough.

Which brings us to the actual review: your code is cleanly written, easy to read and to understand. Unfortunately, well-written, modular code often doesn't squeeze the last bit (heh) out of your hardware, unless your compiler/runtime is very smart (and thus often expensive).

So let's get back to the drawing board for a final review of your code:

Includes

#include <stdio.h>
#include <time.h>
#include <math.h>

I would sort them by name, but that's fine. You don't include anything that's not necessary, nor did you forget something (and got saved by a non-standard compliant compiler).

Declaration

int main() {
    long int a, b, c, d;
    clock_t t;
    t = clock();

Depending on whether you write ANSI-C or C99, I would defer declaration of variables as long as possible. For example, at the moment it's easy to accidentally change c to some bogus value, or forget a { and accidentally check the prop after the loops or similar:

for (a = 1; a < 100000; a++)
    for (b = 1; b < 300000; b++)
        for (c = 1; c < 500000; c++)
            for (d = 1; d < 500000; d++)
                printf("inner loop");
                if (prop(a,b,c,d))
                    printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd = %ld\n", a, b, c, d);

Whoops. The if doesn't get checked, and you don't get a warning (in older compiler versions; new ones do warn about possible whitespace issues). If you declare your variables later (e.g. C99-style), errors like that cannot happen (although it introduces possible shadowing):

for (long int a = 1; a < 100000; a++)
    for (long int b = 1; b < 300000; b++)
        for (long int c = 1; c < 500000; c++)
            for (long int d = 1; d < 500000; d++)
                printf("inner loop");
                if (prop(a,b,c,d))
                    printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd %ld\n", a, b, c, d);

This will now lead to a compiler error, since a, b and so on are out of scope. Either way, that depends on the language standard you want to use. Some people prefer one way, others the other one. Choose yours.

Types

Given that all values should be strictly greater than zero, long int is not the appropriate type, as it can be negative. We should accommodate that. However, instead of using long unsigned int throughout our code, let's use a type synonym in case we want to change it later to a type with a greater range:

 typedef long unsigned int Number;

You can probably come up with a better name.

Cache results (by hand)

One thing that strikes me most is that you recalculate \$a^4\$ and so on every time. We can easily treat this with more variables (using your declaration style):

int main() {
    long int a, b, c, d;
    long int a4, b4, c4, d4; // new variables
    clock_t t;
    t = clock();

    for (a = 1; a < 100000; a++) {
        a4 = pow4(a);                             // remember
        for (b = a; b < 300000; b++) {
            b4 = pow4(b);                         // remember
            for (c = b; c < 500000; c++) {
                c4 = pow4(c);                     // the fourth power
                for (d = c; d < 500000; d++) {
                    d4 = pow4(d);                 // of this member
                    if (a4 + b4 + c4 == d4)
                        printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd = %ld\n", a, b, c, d);
…

Remember how I said that nicely written, modular code isn't often optimal? This is one of those unfortunate examples where you have to help the compiler (unless you know exactly what optimization flags you have to use or your compiler is overly aggressive). The prop is gone, the calls to pow4 are now in your loop.

But the compiler cannot make a mistake here anymore: it's now very clear that a4 doesn't need to be recalculated 300000*500000*500000 times.

That being said, we should apply the other suggestions like the type synonym and the late declaration:

typedef long unsigned int Number;

int main() {
    clock_t t;
    t = clock();

    for (Number a = 1; a < 100000; a++) {
        const Number a4 = pow4(a);                         // remember
        for (Number b = a; b < 300000; b++) {
            const Number b4 = pow4(b);                     // remember
            for (Number c = b; c < 500000; c++) {
                const Number c4 = pow4(c);                 // the fourth power
                for (Number d = c; d < 500000; d++) {
                    const Number d4 = pow4(d);             // of this member
                    if (a4 + b4 + c4 == d4)
                        printf("FOUND IT!\na = %ld\nb = %ld\nc = %ld\nd = %ld\n", a, b, c, d);
…

While const isn't necessary here, it will make sure that we don't change our cached results accidentally.

The time has come

Although our code is now more verbose, there is one small piece of code that repeats itself three times throughout your main:

((double)(clock() - t))/CLOCKS_PER_SEC)

That's quite hard to read, isn't it? It's a perfect candidate for a function:

static inline seconds_since(clock_t t){
    return ((double)(clock() - t))/CLOCKS_PER_SEC;
}

This changes your printf from

printf("a = %ld, b = %ld, c = %ld, time = %fs\n", a, b, c, ((double)(clock() - t))/CLOCKS_PER_SEC);

to

printf("a = %ld, b = %ld, c = %ld, time = %fs\n", a, b, c, seconds_since(t));

Ah. Much easier to read. That's what inline functions are for. Note that any sophisticated compiler should inline that function anyway, so you may also drop inline if you don't want to use C99.

How about finding the powers first and then computing the equivalency? This will eliminate the recomputation of the fourth power of the same number (due to  space considerations).

Something like this can be programmed:

%from numbers 1 to 500000
for k=1:50000:500000
%for indexing
i=0;
%compute the forth powers from k to k+49999 and store the powers in a
for j=k:k+50000-1
a[i++]=j*j*j*j;
end
for x=1:50000
for y=1:50000
for z=1:50000
for t=1:50000
  if (a[x]+a[y]+a[z]==a[t])
   return;
end
end
end
end

Other optimization methods can also be used.


Print the sum of corresponding elements in two arrays In this exercise, I'm supposed to sum up elements from 2 arrays, then display the answer on one line with spaces in between. I did it and my answer got accepted as correct, but I'm wondering if there is a better way to do this since I feel my way was more complicated than it needed to be.

import java.util.ArrayList;
import java.util.List;

public class Main {

public static void main(String[] args) {
    int n = 11;

    int[] firstArray = {811594, 993574, 299729,559604,161945,969851,588210,
            692459, 28350,43017,797855};
    int[] secondArray = {725888, 233750,191700,944750,380402,319860,766872,764921,
            330218,906679, 65309};

    List<Object> total = new ArrayList<>();

    for(int i = 0; i < n; i++){
        int sum = firstArray[i] + secondArray[i];
        total.add(sum);
    }

    Integer[] sumArray = total.toArray(new Integer[total.size()]);
    for(int i = 0; i < n; i++) {
        System.out.print(sumArray[i] + " ");
    }

}
}

You don't need to store the intermediate result.
You don't need to give the length of the arrays.
This assumes that the arrays are allways of equal length.

for(int i = 0; i < firstArray.length; i++){
    System.out.print((firstArray[i] + secondArray[i]) + " ");
}

The "modern" java solution puts newlines, not spaces between the elements, of course.  Adding the trailing space, and using print instead of println will fix that.  Inserting a join (Java has join, right?) might also work.

And, whats' wrong with APL's
      ⎕←firstArray+secondArray


Nested loop to transform MongoDB results I have the following structure returned from MongoDB:

[Class]
    0:Class // -> this.data.userInfo as seen below in the code
        _id: "ksihHTAjdhsA9"
        createdAt:Tue Mar 29 2016 13:03:45 GMT-0400 (EDT)
        weightData: Array[3]
            0: Class
                name: "my name 1"
                value: "myval1"
                weight: 154
            1: Class
                name: "my name 2"
                value: "myval2"
                weight: 191
            2: Class
                name: "my name 3"
                value: "myval3"
                weight: 210

I need to loop through the weightData nested array and store the name and value in a dictionary variable to be used in a dropdown later. I have it working, however, I feel like this could be more efficient.

var dict = [];
_.each(this.data.userInfo, info => {
  if (info) {
    _.each(info.weightData, weightInfo => {
      dict.push({
          "name": weightInfo.name,
          "value": weightInfo.value,
          "weight": weightInfo.weight
      });
    });
  }
});

console.log(dict);

/*
[Object, Object, Object]
    0:Object
        name: "my name 1"
        value: "myval1"
        weight: 154
    1:Object
        name: "my name 2"
        value: "myval2"
        weight: 191
    2:Object
        name: "my name 3"
        value: "myval3"
        weight: 210
*/

It looks like you are basically doing a filter + flatMap. You can also use destructing:

var dict = _(this.data.userinfo).filter(Boolean).flatMap(info => {
  return info.weightdata.map(({name, value, weight}) => {
    return {name, value, weight};
  });
}).value();


Computing the integer square root of large numbers The "integer square root" of a
non-negative integer \$ n \$ is defined as the largest integer not greater than
 \$ \sqrt{n} \$:
$$
 \operatorname{isqrt}(n) = \lfloor \sqrt{n} \rfloor
 = \max \{ k \in \Bbb N_0 \mid k^2 \le n \}
$$
It is for example needed in prime factorization, as an upper bound for the possible
factors.

A simple approach is to compute the floating point square root and truncate the result to an integer. In Swift that would be

func isqrt_simple(_ n: Int) -> Int {
    return Int(Double(n).squareRoot())
}

As observed in
Computing the square root of a 64-bit integer,
this can produce wrong results for large numbers, because an IEEE 64-bit floating point
number with its 53 bit significand cannot represent large integers exactly.
Here is an example:

let n = 9223371982334239233
let r = isqrt_simple(n)

print(r)           // 3037000491
print(r * r <= n)  // false

The correct result would be 3037000490, since
$$
  \sqrt{9223371982334239233} \approx 3037000490.9999996957524364127605120353
$$
(computed with PARI/GP).

The following implementation uses the ideas from
DarthGizka's answer
to the above mentioned question to implement a "correct" integer square root function in Swift 4:

func isqrt(_ n: Int) -> Int {
    precondition(n >= 0, "argument of isqrt() must be non-negative")

    var r = Int(Double(n).squareRoot()) // Initial approximation
    // Try to increase:
    while case let prod = r.multipliedReportingOverflow(by: r),
        !prod.overflow && prod.partialValue < n  {
            r += 1
    }
    // Decrease if necessary:
    while case let prod = r.multipliedReportingOverflow(by: r),
        prod.overflow || prod.partialValue > n  {
            r -= 1
    }
    return r
}

Example:

let n = 9223371982334239233
let r = isqrt(n)

print(r)                 // 3037000490
print(r * r <= n)        // true
print((r+1) * (r+1) > n) // true

Remarks:

I have chosen Int as argument and result type even if the square root is defined
only for non-negative integers. The reason is that Int is the prevalent integer
type in Swift and already used for quantities that can not be negative (e.g.
the count of an array, or the MemoryLayout<T>.size of a type).
Int can be a 32-bit or 64-bit quantity, therefore I cannot check against
a constant for overflow (as r < UINT32_MAX in
DarthGizka's C++ solution).
multipliedReportingOverflow() is used instead to check if squaring a candidate causes an overflow.

The code worked correctly in all my tests. Here are some tests which all succeed

func testSqrt(_ n: Int) {
    let r = isqrt(n)
    if r * r > n {
        print("Too large:", n, r)
    } else if (r+1) * (r+1) <= n {
        print("Too small:", n, r)
    }
}

testSqrt(4503599761588224)
testSqrt(4503599895805955)
testSqrt(4503600030023688)
testSqrt(4503600164241423)

testSqrt(9223371982334241080)
testSqrt(9223371982334239233)
testSqrt(9223372024852248003)
testSqrt(9223372024852247041)
testSqrt(9223372030926249000)
testSqrt(9223372030926247424)

These tests fail if isqrt_simple() is used instead.

All feedback is welcome, in particular suggestions how to improve the performance.

Your function is rather unnecessary. When converted to double, all 64-bit integers retain 1 sign bit and at least 52 precision bits. So the error is at most 11 bit; which means for any number N, the error $$dN<=\frac{2^{11}}{2^{63}}N=2^{-52}N$$
With simple calculus, the error of sqrt() is $$d(\sqrt{N})=\frac{dN}{2\sqrt{N}}<=\frac{2^{-52}N}{2\sqrt{N}}=2^{-53}\sqrt{N}<2^{-53}*2^{32}=2^{-21}<<1$$
In any case the error must be smaller than 1. With rounding/truncation, it can only be -1, 0, or 1.

So your code can be

func isqrt(_ n: Int) -> Int {
    var r = Int(Double(n).squareRoot()) // Initial approximation
    if r * r > n { r -= 1 }
    else if (r + 1) * (r + 1) <= n { r += 1}
    return r
}

edit:
There will be time that (r + 1) * (r + 1) be larger than Int.max and causes error. Instead of using multipliedReportingOverflow, I would do it this way

func isqrt(_ n: Int) -> Int {
    if n >= 3037000499 * 3037000499 {return 3037000499}
    var r = Int(Double(n).squareRoot()) // Initial approximation
    if r * r > n { r -= 1 }
    else if (r + 1) * (r + 1) <= n { r += 1}
    return r
}

edit 2:
To deal with different possible Int sizes:

func isqrt(_ n: Int) -> Int {
  #if arch(i386) || arch(arm)
    if n >= 46340 * 46340 {return 46340}
  #else
    if n >= 3037000499 * 3037000499 {return 3037000499}
  #endif

  var r = Int(Double(n).squareRoot()) // Initial approximation
  if r * r > n { r -= 1 }
  else if (r + 1) * (r + 1) <= n { r += 1}
  return r
}

don't want to be an ass here, but in your case all the heavy lifting is actually done by Int(Double(n).squareRoot()) which is implemented in Swift standard library (I suppose, not a swift programmer my self). All your code does is actually +-1, so there's not much field for performance improvement I suppose.
Generally in order to improve performance, you need to optimize the most time consuming operation, so in this case you'd have to reimplement Double(n).squareRoot() or implement custom sqr root method for integer, maybe based on some integer numerical approximation methods.
Last but not least - this forum is IMHO rather for code style / quality review, your question rather belongs to stackoverflow.com, it's more popular so you might expect more feedback there.


Determining what functions should be implemented in this user-authentication class Long story short, I would like to use OOP for my new PHP project. It has a "login" requirement (i.e. user will first need to enter the username and password (login.php), if it's correct, it will be redirected to index.php and then fetch some products information). Also there will be a settings page that allows user to change the password, and email if necessary.

In summary:

When user attempts to login, the program will check if the username, password entered is correct or not. If it's correct, username (or maybe the whole User object) will be saved in the $_SESSION.
When the user settings page is loaded, it will display all user related fields on screen (i.e. by using $_SESSION).
The user can make changes in the user settings pages and data should be saved to the database.

I have this User class:

class User {
     private $username;
     private $email;
     private $hashed_password;
     private $dob;
...

     public __construct($user) {
          $this->username = $user;
     }

     public function isPasswordCorrect($userenteredpassword) {
           $this->loadFromDatabase();
           //hashed userenteredpassword, compare it against $this->hashed_password
           //if it matches, return true, otherwise return false.
     }

     public function saveToDatabase() {
          //save info to database
     }

     public function loadFromDatabase() {
         $row = select fields from user table where username = $this->username limit 1
         if ($row is found) {
              $this->hashed_password = $row['hashed_password'];
              $this->dob = $row['dob'];
              ...
         }
     }
}//class

However, I was told that the function isPasswordCorrect shouldn't be implemented inside class User, as it is not its job to determine whether the login is valid or not.  Instead, I should create an authService helper and use it to determine whether the login is good or not.

Now, this makes me wonder if the rest of my User class design is okay or not. If I shouldn't put the password checking function in the User class, then is it okay to implement the database related functions in User?  How do I determine which function should be implemented in the class?  Should I follow Single Responsibility principle? Wouldn't it be too extreme?

The Single Responsibility Principle is a good thing to aim for, for many classes. It doesn't always mean that each class only does one thing (though it can), but that it is responsible for a small amount of tightly-related functionality.

That said, the job of some classes is to collect together a number of responsibilities. User may well be one of these, but the individual responsibilities can still be delegated to other classes - e.g. you could always give User an instance of a Credentials class that deals with the password checking.

You almost certainly don't want your database-related functions in User as if you write any tests for User, many of them are likely to have a need to hit the database when they run.

When situations like this come up, it's a good idea to step away from the code and think about how the real-world operates.  Objects in programming mimic those in the real-world, so it can be useful to just look at a use case you see elsewhere.

For example, let's say you're a US Citizen, and you went to another country for vacation.  On your way back into the US, you must prove who you are so that they know you're not on some black list somewhere.  You, the user, provide your credentials: primarily your passport, but you might also be asked for your drivers license or any other identifying documents.  You hand those documents over, and then it's someone else who determines whether your papers are a forgery or not.  It is not your responsibility to tell the officers that you're not a threat.  It is their responsibility to determine that.

Taking this back to computer authentication: The user provides their username and password, and then someone else(the system) determines if they are authorized to access the system or not.

Taking this to the coding level: it doesn't make much sense to have a user authenticate themselves.  The code can be written to do that, but it really isn't the user's job to say he's authorized to have access.  Someone else in the system needs to determine that - like the authService your colleague mentioned.

On the topic of database access...like others have said: that's somewhat up to you.  I always like to have one object that provides access to data resources(not necessarily to mean one thread, but one object that determines which operations are allowed concurrently and when to lock the resource for writes/updates).  Alternatively, many objects can access a data resource but they're synchronized in some way(mutex, semaphore, etc).

This way, the concurrency issues will be located within that object(s) instead of scattered in mysterious locations that make debugging harder.  So, if my program is running and I'm noticing wonky things going to/from the database, it's pretty straight forward to drill down to where the problem exists.  If I had a bunch of users who were in their own thread and doing whatever they wanted with the database, it might not be immediately obvious that the users are the problem.  The symptom is the database looks wrong, and the reason it's wrong is because users are changing the database without respecting the changes the others are making.

An example of that case would be source control, which is a tool used to allow multiple developers to work on the same project at the same time without worrying about who is writing in which file.  Now, take away the source control.  If two developers write to the same file without knowledge of the other, one of the developer's code is going to get erased completely, and when that developer tries to watch his functionality work...it simply won't be there because someone wrote over it.  Then the question becomes...who wrote over it, when, and is there a copy of the feature that was implemented, or does it need to be done again?  These kinds of things happen on the order of minutes, hours, or even days...but in a program that uses a database...this will be happening hundreds of times a second.  It's better to give control of a resource like that to someone who can safely manage it(source control, database handler, etc).


App that sets configuration data I've been writing my code like this for a really long time now, I am wondering if there is a more efficient way to do this. This is especially after a senior developer said my code was very amateurish.

App Purpose: I need to set some data for new employees when they join our organisation. This is a simple command app written in .net that takes an argument, splits it and then assigns the variables. A command might look like this:

Setdata.exe -Marcus -true -true -false -false.

The output is a file that we install on one of our sql servers.

The example below is a small one, but it is not common for the settings to hit 40-50 lines.

Code:

  internal static void ExportSolution(SqlService service, string parms)
    {
        try
        {
            parms = parms.Replace(" ", "");
            string[] args = parms.Split('-');

            string solutionName = args[1];
            bool managed = Convert.ToBoolean(args[2]);
            bool prefix= Convert.ToBoolean(args[3]);
            bool profile= Convert.ToBoolean(args[4]);
            bool email= Convert.ToBoolean(args[5]);
            bool calendar= Convert.ToBoolean(args[6]);
            bool appSettings= Convert.ToBoolean(args[7]);

            AppSettingsRequestAppSettingsRequest= new AppSettingsRequest();

            AppSettingsRequest.SolutionName = solutionName;

            AppSettingsRequest.Managed = (managed == true) ? true : false;

            AppSettingsRequest.prefix= (prefix== true) ? true : false;

            AppSettingsRequest.Managed profile= (profile== true) ? true : false;

            AppSettingsRequest.email= (email== true) ? true : false;

            AppSettingsRequest.calendar= (calendar== true) ? true : false;

            AppSettingsRequest.appSettings= (appSettings== true) ? true : false;

            byte[] exportXml = exportSolutionResponse.ExportSolutionFile;
            string filename = solutionName + ".zip";
            File.WriteAllBytes(filename, exportXml);

            Console.WriteLine("Solution exported to {0}.", filename);
        }
        catch (Exception ex)
        {
            Console.WriteLine(ex);
        }

Initial thoughts are that I could create a new class and then instantiate a new object with these variables, but is there anything to gain from doing this?

Ignored code

From the code sample provided, you're not actually doing anything with the AppSettingsRequest object after you've created it. Why? What is the purpose of this object?

Global variables

byte[] exportXml = exportSolutionResponse.ExportSolutionFile;

What is exportSolutionResponse? It comes out of nowhere, without being defined anywhere. This seems to be a global variable (I can't otherwise explain its existence).

Global variables are generally a bad idea. They create shortcuts in code that is one of the straws that will eventually break the camel's back (in this case, unmaintainable spaghetti code).

Stringly typing

As you seem to be using a console application, the parameters can be parsed an an array of values, not as a single string. Why are you concatenating these values into a string, only to then split the string again?

This can be improved by using explicit method parameters:

internal static void ExportSolution(SqlService service, string name, params bool[] values)

This means you no longer have to do the conversion in this method; which is a good separation of concerns.

Given that you are expect a fixed amount of booleans, it's better to explicitly name these booleans instead of allowing any array of arbitrary length:

internal static void ExportSolution(SqlService service, string name, bool managed, bool prefix, bool managedprofile, bool email, bool calendar, bool appsettings)

Vague names

Your variable names leave something to be desired. I can only guess at what these variables mean. Rename them to something clearer. I've guessed at what these booleans are used for:

internal static void ExportSolution(SqlService service, string userName, bool isManaged, bool hasPrefix, bool useManagedProfile, bool importEmail, bool importCalendar, bool overrideAppSettings)

Don't get caught up on the names, my interpretations are only a guess. But these examples are much clearer on what the impact of these booleans is.

No null checking

This ties into the earlier point. In your original code, you are taking in any string and splitting it into an array, and then assuming that this array will contain at least 8 values.

What happens when the array contains less than 8 values? You're going to end up with an IndexOutOfRangeException. While you do catch and display exceptions, it's still better to avoid exceptions where possible. It's not that hard to validate the length of the array before you try to access its elements.

if(args.Length < 8)
{
    Console.WriteLine("Insufficient parameters provided");
    return;
}

Pokémon exception handling (link)

catch (Exception ex)
{
    Console.WriteLine(ex);
}

Instead of catching all exceptions, catch the exceptions you're interested in. For example:

catch (IndexOutOfRangeException ex)
{
    Console.WriteLine("Insufficient parameters provided");
}

Note: as mentioned before, it is better to prevent the exception when possible, instead of just catching it afterwards. This only serves as a simple example of how you catch specific exceptions instead of all possible exception types.

Needlessly verbose code

AppSettingsRequest.Managed = (managed == true) ? true : false;

this can immediately be refactored to:

AppSettingsRequest.Managed = managed;

For two reasons:

== true is redundant. If the variable is already a boolean, its "trueness" doesn't need to be checked. managed == true will always equal managed.
? true : false is redundant. The evaluation (left of the ?) is already a boolean, and what you're doing here is saying "if this evaluation is true, set this to true; if this evalutation is false, set it to false". It's much short to just say "set this to the evaluation's value". managed ? true : false will always equal managed.

Note: if you were using nullable booleans, bullet point 1 wouldn't necessarily be correct (as you're also checking for non-null in that case), but you're not using nullable booleans here.

Saving some lines of code

bool managed = Convert.ToBoolean(args[2]);
AppSettingsRequest.Managed = managed;

Can be shortened to

AppSettingsRequest.Managed = Convert.ToBoolean(args[2]);

In general, I wouldn't advise this. The added clarity from separating the steps makes things easier. However, given that one of your main issues is the amount of settings, combining the two steps will halve your line count. At the same time, the combined line is not unreadable by any stretch of the imagination so it's perfectly okay to combine them here.

Separating your concerns

In general, your method is taking on too many tasks. It manipulates the input string, converts the values, handles them, writes to storage and updates the UI (console output). This is too many responsibilities for a single method.

However, this seems to be a very small and simple console application, and the overhead cost of implementing some separations may end up costing more effort than it's worth. I would still suggest a basic separation between the following tasks:

Parsing the input values (to their correct string/bool types)
Instantiating the settings object and settings its properties
Writing your data to disk

The code looks good, but I think the code could look more structured, like maybe in the appsetings you could give them one more indentation. This way the code won't just be one long line and it would be much easier to differentiate the code structure.


BingWallpapers: Fetches and applies the image of the day from Bing as the wallpaper I have written a small desktop program nabeelomer/BingWallpapers in Haskell. This is my first time writing Haskell.

I was wondering how I can make the code use more functional programming features/idioms/patterns.

Any other suggestions on how to improve the code are also welcome.

-- Copyright (C) Nabeel Omer 2017
-- See the LICENSE file for the license
--

import Network.HTTP.Conduit
import System.Process
import qualified Data.ByteString.Lazy.Char8 as L8
import GHC.IO.Exception

main :: IO ()
main = do
    -- using http://muzzammil.xyz/git/bing/
    metadata <- get "http://cdn.muzzammil.xyz/bing/bing.php?format=text&cc=IN"

    -- Guaranteed by the API
    putStrLn $ (split '>' $ (lines $ L8.unpack metadata)!!1)!!1
    let url = (lines $ L8.unpack metadata)!!0
    picture <- get $ (split '>' url)!!1

    L8.writeFile "/dev/shm/Bing-Wallpaper" picture
    exitcode <- setWallpaper "/dev/shm/Bing-Wallpaper"

    print exitcode
    return ()

-- From StackOverflow
split :: Eq a => a -> [a] -> [[a]]
split d [] = []
split d s = x : split d (drop 1 y) where (x,y) = span (/= d) s

get :: String -> IO L8.ByteString
get url = simpleHttp url

setWallpaper :: String -> IO GHC.IO.Exception.ExitCode
setWallpaper uri = system $ "gsettings set org.gnome.desktop.background picture-uri file://" ++ uri

Pattern matching instead of !!, inlining of single-use names where straightforward.

import Data.List.Split

main = do
  (_:picurl:_):(_:title:_):_ <- map (wordsBy (=='>')) . lines . L8.unpack
    <$> get "http://cdn.muzzammil.xyz/bing/bing.php?format=text&cc=IN"
  putStrLn title
  L8.writeFile "/dev/shm/Bing-Wallpaper" =<< get picurl
  print =<< setWallpaper "/dev/shm/Bing-Wallpaper"


Shortest prime number generator we could come up with? I worked with a friend on the following prime number generator. Our goal was to make it as short and as fast as possible. This is what we came up with:

def p(n): # will print out primes between 0 and n
  s=[True]*(n/2)
  for i in range(int((n/2-1)/2) >> 1):
    for j in range((i*(i+3)<<1)+3,n/2,(i<<1)+3): s[j]=False
  return [2] + [((i<<1)+3) for i in range(n/2) if (s[i])]
print p(input()) # input number for n

Can it be made any faster? Also, it crashes due to memory errors if numbers larger than 1010 are inputted. Can this be fixed to make it more memory efficient?

0. Quick comments on your code

Clearer function names and
variables in your code. What does p mean, and what is s? I can
guess, but please.
Include a docstring or some indication of what your code does
Use the  if __name__ == "__main__": module.

I did some quick speed comparisons of your function which you can see below.

magic1            21.9095528103 ms
magic2            26.5589244423 ms
Joseph Farah    1030.95786404   ms

I did 10 runs with primes up to \$2\$ million. Now note the big gap between the optimized functions and yours. Even if you were to speed up your code tenfold you would still be 10 times slower than the other functions.

  You can add as many horses you want to your cart, but it will never beat a ferrari.

With this in mind i propose three solutions

Implement a better algorithm
Use Import
Give up

1. New algorithm

Wikipedia can shed some light on how to find larger primes.

  For the large primes used in cryptography, it is usual to use a
  modified form of sieving: a randomly chosen range of odd numbers of
  the desired size is sieved against a number of relatively small primes
  (typically all primes less than \$65,000\$). The remaining candidate
  primes are tested in random order with a standard probabilistic
  primality test such as the Baillie-PSW primality test or the
  Miller-Rabin primality test for probable primes.

So in short you use for an example Wheel factorization to find possible primes, then use the Rabin_primality_test to test whether the candidates are primes. Without going too technical the Rabin_primality_test is a probabilistic test. If the function returns True p might be prime, if False we are guaranteed it is not. If n is composite then the Miller–Rabin primality test declares n probably prime with a probability at most \$4^{−k}\$. A friend told me banks used tested primes 80 times. The chances of a composite number passing \$80\$ tests is \$4^{-80}\$ which is in incredibly low number.

A comparison of many different sieves and ways to find primes can be found here https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n. I used the fastest one on my machine primesfrom2to to generate the results above

import numpy as np
def magic1(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)/3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False
    return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]

2. Use Import

Python is magical in the sense that you can find libaries which pretty much do anything. The best part is that installing new packages is easy as \$\pi\$. There are many libaries for primes, I will mention a few below

primesieve
primefac
pyprimesieve

primesieve] is Python bindings for the primesieve C++ library. It can generate list of primes at an incredible speed, and also has fast nthprime implementation. primefac is incredibly good at factoring primes, it can also generate primes, but is rather slow. pyprimesieve
has functions such as prime_sum and has many nifty specialized functions.

So if you want a golfed answer the best you can get in terms of speed is

from primesieve import generate_primes

if __name__ == '__main__':

    print generate_primes(2*10**6)

3. Give up

Even if you are in your prime finding and generating large primes are incredibly hard. However this is a good thing as primes are incredibly important in internet security. If by some miracle you were to find an incredibly, incredibly fast prime generator it would break all the large banks and make payments over the net unsafe.

So perhaps it is a good thing your code is slow ;)

If your primary goal is the shortest program. Then you can use regular expressions for a much shorter program to find primes.

So in python it looks like:

def is_prime(n):
    import re
    for i in range(n):
       if re.match(r'1?$|(11+?)\1+$', '1' * i) is None:
           print i


Pascal Triangle calculation with BigIntegers On a well known programming challenges website(CW) there is a Kyu2 eggs height problem that can be solved utilizing a variation of Pascals Triangles properties.

The problem asks to solve f(n, m) and the solution is the sum of Pascal's Triangle row m up to cell/column n, so the sum of
f(i) = (m + 1 - i) * f(i-1) / i for i = 1 to n.

On the second variation of that problem (Kyu1) it is asked that you solve the same challenge linearly with the f(n, m) output being orders of magnitude bigger.

I've tried to solve the challenge with the code below, but it exceed the allowed time constrains to solve the challenge.

using System.Numerics;
public class EggChallenge
{
    private static BigInteger mo = new BigInteger(998244353);
    public static BigInteger Height(BigInteger n, BigInteger m)
    {
        return n == 0 || m == 0 ? 0 : BigInteger.Remainder(SumHeight(n+1, m), mo);
    }

    public static BigInteger SumHeight(BigInteger n, BigInteger m)
    {
        BigInteger BigInt = new BigInteger(1);
        BigInteger BigIntegerSum = new BigInteger(0);

        for(int i = 1; i < n; i++)
        {
            BigInt = BigInteger.Divide(BigInteger.Multiply(m + 1 - i, BigInt), (BigInteger)i);
            BigIntegerSum = BigInteger.Add(BigIntegerSum, BigInt);
        }

        return BigIntegerSum;
    }
}

The above code solves test cases such as:

EggChallenge.Height(10000,100000);
EggChallenge.Height(80000,100000);
EggChallenge.Height(3000,BigInteger.Pow(2,200));

But it's not able to beat the actual challenge time constrains.

I don't think the algorithm is what to improve has it seems to run at O(n), but I could be very wrong.

So far I've tried memorization in a BigInteger[] to release the cost of the constant addition, but it performed worst then the current code.

My question is how would this code be improved performance wise, which techniques could be applied to improve code performance?, and if possible why are those the best to apply?

initial challenge details
linear challenge details

using System.Numerics;
public class EggChallenge
{
    private static BigInteger mo = new BigInteger(998244353);
    public static BigInteger Height(BigInteger n, BigInteger m)
    {
        return n == 0 || m == 0 ? 0 : BigInteger.Remainder(SumHeight(n+1, m), mo);
    }

    public static BigInteger SumHeight(BigInteger n, BigInteger m)
    {
        BigInteger BigInt = new BigInteger(1);
        BigInteger BigIntegerSum = new BigInteger(0);

        for(int i = 1; i < n; i++)
        {
            BigInt = BigInteger.Divide(BigInteger.Multiply(m + 1 - i, BigInt), (BigInteger)i);
            BigIntegerSum = BigInteger.Add(BigIntegerSum, BigInt);
        }

        return BigIntegerSum;
    }
}

C# supports operator overloading subject to some constraints, and BigInteger has all of the arithmetical operators implemented. So you can improve legibility a lot by using standard operators rather than BigInteger.OperatorName(foo, bar).

Local variables in C# normally begin with a lower case letter, so using upper case is not very helpful. In addition, BigInt doesn't tell me anything useful: I know that the type is BigInteger because I can see the declaration, but what does the variable mean?

Renaming and using overloaded operators I get rewritten code which IMO is easier to read:

    BigInteger Height(BigInteger n, BigInteger m)
    {
        return n == 0 || m == 0 ? 0 : SumHeight(n + 1, m) % mo;
    }

    BigInteger SumHeight(BigInteger n, BigInteger m)
    {
        BigInteger term = 1;
        BigInteger sum = 0;

        for (int i = 1; i < n; i++)
        {
            term = (m + 1 - i) * term / i;
            sum += term;
        }

        return sum;
    }

  I don't think the algorithm is what to improve has it seems to run at
  O(n), but I could be very wrong.

I'm afraid that you are very wrong. The code is performing \$O(n)\$ arithmetical operations on BigIntegers, but an arithmetical operation on a BigInteger is not \$O(1)\$. The fundamental problem is this:

        ... SumHeight(n + 1, m) % mo;

It should instead be

        ... SumHeight(n + 1, m, mo);

with the % being applied regularly inside the loop:

        for (int i = 1; i < n; i++)
        {
            term = (m + 1 - i) * term % mo;
            term = ModDiv(term, i, mo); // I'll come back to this
            sum += term;
        }

        return sum % mo;

The massive advantage is that you no longer need BigInteger: it suffices to use long (or maybe ulong: it's a matter of taste because 998244353 was chosen such that long would work in languages like Java which don't have ulong).

I infer from your comment on an earlier answer that you haven't studied modular arithmetic. This is quite understandable: I think it's safe to say that 99% of programmers will never use it in their careers. But although it is irrelevant for most line-of-business programming, it is quite important in code contests/challenges (interpreted broadly to include katas, Project Euler, etc.) because they frequently use modular arithmetic to make large test cases feasible. If you find katas either enjoyable or useful for your CV, it's probably worth your time to study.

The properties I'm relying on are (treating % as an operator on arbitrary-width integers and assuming that we're avoiding overflow, which is % Pow(2, IntegerTypeWidth)):

((a % m) + (b % m)) % m == (a + b) % m
((a % m) * (b % m)) % m == (a * b) % m

Now I can come back to modular division. Essentially ModDiv(term, i, mo) needs to calculate a modular reciprocal of i (i.e. j such that i * j % mo == 1) and then return term * j % mo. There is always such a j as long as it is coprime with mo, and 998244353 is deliberately chosen to be a prime number, deliberately chosen so that you can divide by any number which isn't a multiple of it. The standard approach to calculate a modular reciprocal is the extended Euclidean algorithm, and is described in so many millions of web pages that I won't try to give my own explanation here.

To wrap up the explanation, I must address a point raised by Rick Davin. If you rewrite SumHeight so that n and m are both long, how to handle the test case m = BigInteger.Pow(2, 200)? If we look at how m is used, it takes part in addition and multiplication. So the way to do this is to do the modulo in BigInteger and then cast to long:

    long Height(BigInteger n, BigInteger m)
    {
        return n == 0 || m == 0 ? 0 : SumHeight((long)n + 1, (long)(m % mo), mo);
    }

If n is BigInteger then i needs to be BigInteger also.

Taking the modus of 998244353 in the loop will prevent BigInteger from having to expand.

Don't need BigInteger for 998244353.  That will fit in Int64;

Kind of hard for me to believe n is BigInteger is the requirement.  According to the links n in just integer.  You are wasting CPU by not being exact.

for(int i = 1; i < n; i++)

This is not iterating i = 1 to n

Shorter syntax but not sure it is any better.
Because of integer rounding these are not same.

term = (m + 1 - i) * term / i;
term *= (m + 1) / i - 1;

Just looking at I don't see a way to short circuit anything

for (BigInteger i = 1; i < n; i++)
{
    term *= (m + 1) / i - 1;
    sum += term;
}


Calculating entropy of a string We're calculating entropy of a string a few places in Stack Overflow as a signifier of low quality.

I whipped up this simple method which counts unique characters in a string, but it is quite literally the first thing that popped into my head. It's the "dumbest thing that works".

/// <summary>
/// returns the # of unique characters in a string as a rough
/// measurement of entropy
/// </summary>
public static int Entropy(this string s)
{
  var d = new Dictionary<char, bool>();
  foreach (char c in s)
      if (!d.ContainsKey(c)) d.Add(c, true);
  return d.Count();
}

Is there a better / more elegant / more accurate way to calculate the entropy of a string?

Efficiency is also good, though we never call this on large strings so it is not a huge concern.

Won't this work too?

string name = "lltt";
int uniqueCharacterCount = name.Distinct().Count();

will return 2

I have seen many answers that suggest counting the number of distinct characters. But beware that this only works for 16-bit characters!

A character in C# is a UTF-16 code unit. Extended unicode characters are stored in multiple C# characters. CharUnicodeInfo.GetUnicodeCategory allows us to detect whether a C# character represents a real character or whether it is part of an extended unicode character or combined character (UnicodeCategory.Surrogate).

Test (fake) entropy:

 public static void Main()
 {
     var value = "\U00020B20";

     // yields 2, even though \U00020B20 represents a single unicode-character ''
     var entropyTest = value.Distinct().Count();
 }

In order to count the characters (not the C# characters), we need to augment our algorithm. I am using a class called Grapheme to do the trick. This class is able to detect extended unicode characters and diacritics.

Test entropy:

 public static void Main()
 {
     var grapheme = Grapheme.Parse("\U00020B20");

     // yields 1, as \U00020B20 represents a single unicode-character ''.
     var entropyTest = grapheme.Select(x => x.Glyph).Distinct().Count();

     // yields 2, as \U00020B20 is stored in 2 C# characters.
     var codeUnits = grapheme.Single().CodeUnits.Length;
 }

Final note:

Testing entropy on a string is not context-free. Some characters or combined characters result in the same glyph, depending on the Font used. So entropy can only be calculated in the context of a font. The Grapheme class does not take this into account, since different fonts would render different entropies. The Grapheme class is said to be context-free.

(A) two different characters might have the exact same glyph (homoglyph)
(B) combined characters might have the same glyph as another character

Examples:

A: \u0061 and \u0430 represent both the letter 'a' in certain fonts
B:  Å is both the character \u00C5 and the combined character A with an overdot character

Appendix: Grapheme

public class Grapheme
{
    private char[] _codeUnits;
    private Grapheme[] _diacritics;
    private string _glyph;

    public Grapheme(string glyph) {

        Guard.NotNull(glyph, "glyph");
        _glyph = StringInfo.GetNextTextElement(glyph);
        Guard.Condition(_glyph.Length != glyph.Length, "glyph", "Invalid glyph specified");

        var codeUnits = new List<char>();
        var diacritics = new List<Grapheme>();
        var buffer = _glyph;

        if (buffer.Length > 0) {
            var cu0 = CharUnicodeInfo.GetUnicodeCategory(buffer[0]);
            switch (cu0) {
                case UnicodeCategory.Surrogate:
                    codeUnits.AddRange(buffer.Take(2));
                    buffer = buffer.Substring(2);
                    break;
                default:
                    codeUnits.Add(buffer[0]);
                    buffer = buffer.Substring(1);
                    break;
            }
            diacritics.AddRange(Parse(buffer));
        }

        _codeUnits = codeUnits.ToArray();
        _diacritics = diacritics.ToArray();

        if (_codeUnits.Length == 2) {
            Guard.Condition(!char.IsSurrogatePair(new string(_codeUnits), 0),
                "glyph", "Invalid surrogate pair specified");
        }
    }

    public static Grapheme[] Parse(string value) {
        Guard.NotNull(value, "value");
        return StringInfo.ParseCombiningCharacters(value).Select(i
                        => new Grapheme(StringInfo.GetNextTextElement(value, i))).ToArray();
    }

    public static int[] ParseIndices(string value) {
        Guard.NotNull(value, "value");
        return StringInfo.ParseCombiningCharacters(value).ToArray();
    }

    public static Grapheme ParseNext(string value, int index) {
        return new Grapheme(StringInfo.GetNextTextElement(value, index));
    }

    public static Grapheme ParseNext(string value) {
        return ParseNext(value, 0);
    }

    public char[] CodeUnits {
        get {
            return _codeUnits;
        }
    }

    public Grapheme[] Diacritics {
        get {
            return _diacritics;
        }
    }

    public string Glyph {
        get {
            return _glyph;
        }
    }

    public Grapheme[] Flatten() {
        return new[] { this }.Concat(_diacritics.SelectMany(x => x.Flatten())).ToArray();
    }

    public Grapheme Normalize() {
        return new Grapheme(_glyph.Normalize());
    }

    public Grapheme Normalize(NormalizationForm form) {
        return new Grapheme(_glyph.Normalize(form));
    }

    public override bool Equals(object obj) {
        if (obj is Grapheme) {
            return string.Equals(((Grapheme)obj)._glyph, _glyph);
        }
        return false;
    }

    public override int GetHashCode() {
        return _glyph.GetHashCode();
    }

    public override string ToString() {
        return _glyph;
    }
}


Implementation of Prim's algorithm in C++ Could anyone comment on what could be done better and if I made any mistakes?

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

using namespace std;

typedef pair<pair<int, int>, int> Edge; //a, b, length
// A---------B
//   length

vector<Edge> prims_algo(vector<vector<int>> graph, int number_of_nodes){
    vector<int> unvisited;
    vector<int> visited;
    vector<Edge> result;

    //mark first as visited and mark the rest as unvisited
    for (int i = 1; i < number_of_nodes; i++)
        unvisited.push_back(i);
    visited.push_back(0);

    while (!unvisited.empty()) {

        vector<Edge> edges_with_lengths;
        //put all edges (with their lengths) from nodes that are in visited
        for(auto node : visited) {
            for (int sec_node = 0; sec_node < number_of_nodes; sec_node++) {
                if (graph[node][sec_node] > 0 && find(unvisited.begin(), unvisited.end(), sec_node) != unvisited.end()) {
                    //add if there is connection and second node is not visited yet
                    Edge e = make_pair(make_pair(node, sec_node), graph[node][sec_node]);
                    edges_with_lengths.push_back(e);
                }
            }
        }

        //find the shortest edge
        pair<pair<int, int>, int> the_shortest;
        the_shortest = edges_with_lengths.front();
        for(auto i: edges_with_lengths){
            if(the_shortest.second > i.second)
                the_shortest = i;
        }

        //add the shortest path to the result
        result.push_back(the_shortest);

        //remove a node that the shortest edge leads to
        unvisited.erase(remove(unvisited.begin(), unvisited.end(), the_shortest.first.second), unvisited.end());

        //mark this node as visited
        visited.push_back(the_shortest.first.second);
    };
    return result;
}

int main() {
    /*
       2    3
   (0)--(1)--(2)
    |   / \   |
   6| 8/   \5 |7
    | /     \ |
   (3)-------(4)
         9          */
    vector<vector<int>> graph =
                     {{{0, 2, 0, 6, 0},
                       {2, 0, 3, 8, 5},
                       {0, 3, 0, 0, 7},
                       {6, 8, 0, 0, 9},
                       {0, 5, 7, 9, 0},
    }};

    vector<Edge> result = prims_algo(graph, 5);
    for(auto i:result){
        cout<<"EDGE [ " <<i.first.first<<", "<<i.first.second<<"], length: "<<i.second<<endl;
    }

    return 0;
}

Code looks OK.

I would suggest you to do some class instead of Edge:

//typedef pair<pair<int, int>, int> Edge; //a, b, length
struct Edge{
   int a;
   int b;
   int length;
};

Also I suggest to have some predefined type for vector<Edge>

using EdgeContainer = vector<Edge>;

You have duplication near //find the shortest edge, you probably need Edge there

Here the_shortest is probably not initialized. Also you probably might use something from <algorithm> (but I will do it in same way as you).

    //find the shortest edge
    pair<pair<int, int>, int> the_shortest;
    the_shortest = edges_with_lengths.front();
    for(auto i: edges_with_lengths){
        if(the_shortest.second > i.second)
            the_shortest = i;
    }

Another probably micro optimization would be to write ++i in loops:

//for (int i = 1; i < number_of_nodes; i++)
for (int i = 1; i < number_of_nodes; ++i){
   // ...
}

Also in C++11 main() does not need to return 0;.

You have not used a priority queue, so performance is not good.


How would you better organize/code this basic HTML and CSS? I'm curious to see what any of the more experienced programmers would do instead of methods I took as a learning tool. Any tips/tricks/fixes and reasoning is appreciated!!

http://www.jacobweyer.com

This is the result of the code so far:

<!DOCTYPE html>

<title>Alpha Tau Omega | Theta Omega</title>
<link rel="stylesheet" type="text/css" href="ATOStyle.css" />

Home

Rush

History

Alumni

Calendar

Media

CSS

html, body, div, span, object, iframe,
h1, h2, h3, h4, h5, h6, p, blockquote, pre,
abbr, address, cite, code,
del, dfn, em, img, ins, kbd, q, samp,
small, strong, sub, sup, var,
b, i,
dl, dt, dd, ol, ul, li,
fieldset, form, label, legend,
table, caption, tbody, tfoot, thead, tr, th, td,
article, aside, figure, footer, header,&nbsp;hgroup, menu, nav, section, menu,
time, mark, audio, video {
margin:0px;
padding:0px;
border:0px;
outline:0px;
font-size:100%;
vertical-align:baseline;
background:transparent;
}

#navbar ul {
list-style-type: none;
margin: 0px;
padding: 0px;
}

#navbar ul li a {
text-decoration: none;
color: black;
}
#navbar ul li a:hover {
color: white;
}

#navbar ul li {
font-family: Arial, Helvetica, sans-serif;
text-decoration: none;
color: #000000;
display: inline-block;
width: 70px;
height: 40px;
margin: 10px;
}

#banner {
background:url(./pieces/banner.png);
position: absolute;
margin-left: 0px;
min-height: 193px;
min-width: 183px;
background-repeat: no-repeat
}

#title {
position: absolute;
background: url(./pieces/name.png);
margin-left: 190px;
min-height: 75px;
min-width: 285px;
}

#navbar {
position: relative;
top: 80px;
left: 210px;
margin-left: inherit;
}
#social ul li{
display: inline-block;
width: 35px;
height: 35px;
margin: 5px;
}
#social {
position: absolute;
float: left;
right: 180px;
top: -5px;
}
#social ul {
list-style-type: none;
}

#innerheader {
height: 139px;
width: 750px;
margin-right: auto;
margin-left: auto;
position: relative;
}

#header {
background:url(./pieces/headerBar.png);
position: static;
width:100%;
height:139px;
padding:0;
border:0;
z-index: 10000;
}

#pagecenter {
position: static;
margin-right: auto;
margin-left: auto;
height: 50px;
width: 750px;
min-height: 1000px;
background:url(./pieces/mainBG.png);
background-position: center;
background-repeat: no-repeat;
background-attachment: fixed;
margin-top: -19px;
z-index:50
}
body {
width: 100%;
margin: 0px 0px 0px 0px;
background-color: #808080
}
#footer {
margin-top: 20px;
padding-top: 30px;
background: url(./pieces/footerbar.png);
height: 77px;
width: 100%;
margin-right: auto;
margin-left: auto;
clear: both;
bottom: 0px;
position: static;
}

#footerbanner {
background: url(./pieces/footerbanner.png);
position: absolute;
min-height: 95px;
min-width: 90px;
background-repeat: no-repeat;
margin-top: -30px;
}

A lot of this type of stuff is just personal style, or if you're working on a team, the layout is defined ahead of the project.

The use of classes vs id's is also personal. I've seen people say that they ALWAYS use classes. I've tried both classes and id's on many pages, and I find that I get into fewer problems with mostly classes, reserving id's for truly individual elements.

I've read that the stuff at the top of your CSS can slow things down quite a bit and may not be necessary in many cases.

I formatted the last two parts of your CSS a bit differently. I do that a lot with PHP, but have seen in recently in CSS, and I think it might work nicely in some situations.

But for fun...

<!DOCTYPE html>

  <title>Alpha Tau Omega | Theta Omega</title>
  <link rel="stylesheet" type="text/css" href="ATOStyle.css" />

Home

Rush

History

Alumni

Calendar

Media

CSS

html, body, div, span, object, iframe,
h1, h2, h3, h4, h5, h6, p, blockquote, pre,
abbr, address, cite, code,
del, dfn, em, img, ins, kbd, q, samp,
small, strong, sub, sup, var,
b, i, dl, dt, dd, ol, ul, li,
fieldset, form, label, legend,
table, caption, tbody, tfoot, thead, tr, th, td,
article, aside, figure, footer, header,&nbsp;hgroup, menu, nav, section, menu,
time, mark, audio, video {
  margin: 0px;
  padding: 0px;
  border: 0px;
  outline: 0px;
  font-size: 100%;
  vertical-align: baseline;
  background: transparent;
}
#navbar ul {
  list-style-type: none;
  margin: 0px;
  padding: 0px;
}
#navbar ul li a {
  text-decoration: none;
  color: black;
}
#navbar ul li a:hover {
  color: white;
}
#navbar ul li {
  font-family: Arial, Helvetica, sans-serif;
  text-decoration: none;
  color: #000000;
  display: inline-block;
  width: 70px;
  height: 40px;
  margin: 10px;
}
#banner {
  background:url(./pieces/banner.png);
  position: absolute;
  margin-left: 0px;
  min-height: 193px;
  min-width: 183px;
  background-repeat: no-repeat
}

#title {
  position: absolute;
  background: url(./pieces/name.png);
  margin-left: 190px;
  min-height: 75px;
  min-width: 285px;
}
#navbar {
  position: relative;
  top: 80px;
  left: 210px;
  margin-left: inherit;
}
#social ul li{
  display: inline-block;
  width: 35px;
  height: 35px;
  margin: 5px;
}
#social {
  position: absolute;
  float: left;
  right: 180px;
  top: -5px;
}
#social ul {
  list-style-type: none;
}

#innerheader {
  height: 139px;
  width: 750px;
  margin-right: auto;
  margin-left: auto;
  position: relative;
}

#header {
  background:url(./pieces/headerBar.png);
  position: static;
  width:100%;
  height:139px;
  z-index: 10000;
}

#pagecenter {
  position: static;
  margin-right: auto;
  margin-left: auto;
  height: 50px;
  width: 750px;
  min-height: 1000px;
  background: url(./pieces/mainBG.png);
  background-position: center;
  background-repeat: no-repeat;
  background-attachment: fixed;
  margin-top: -19px;
  z-index:50
}
body {
  width: 100%;
  margin: 0px 0px 0px 0px;
  background-color: #808080
}
#footer {
  margin-top:   20px;
  padding-top:  30px;
  background:   url(./pieces/footerbar.png);
  height:       77px;
  width:        100%;
  margin-right: auto;
  margin-left:  auto;
  clear:        both;
  bottom:       0px;
  position:     static;
}
#footerbanner {
  background:        url(./pieces/footerbanner.png);
  position:          absolute;
  min-height:        95px;
  min-width:         90px;
  background-repeat: no-repeat;
  margin-top:        -30px;
}

I see no problems with it. However, at the HTML section, try adding maybe 2 lines of blank space in between the all of the divs. An example lies below.

This could help your code look more clean, separate, and easier to maintain over time. I hope I helped!


Find duplicated text for tasks in MS Project My code in MS project VBA, in theory, doesn't do anything major.
It compares the tasks with each other, but it runs super slow.

One run through Temp lasts 15 secs. Try that with 1500-2000 tasks and the macro takes hours.

Sub Laczona()

Application.Calculation = xlManual
Application.ScreenUpdating = False

Dim Temp, Temp2 As Integer

For Temp = 1 To ActiveProject.Tasks.Count

For Temp2 = 1 To ActiveProject.Tasks.Count

If ActiveProject.Tasks(Temp).Text30 = ActiveProject.Tasks(Temp2).Text30 Then
If Temp <> Temp2 Then
ActiveProject.Tasks(Temp).Flag5 = 1
End If
End If

Next Temp2
MsgBox "Praca: " & Temp
Next Temp

MsgBox "Prace Laczone Uzupelnione"
Application.ScreenUpdating = True
Application.Calculation = xlAutomatic

End Sub

Addidional explanation:
The code runs in MS Project 2013. Its purpose is to check whether two tasks have the same text in field Text30. If that is the case, the code sets flag5 to 1.

If I understand correctly, you are testing to see if there are any duplicate entries in Text30 and if you find a duplicate setting flag 5 to 1.

In this case you are duplicating at least half of the tests that you are conducting because Task(1).Text(30) = Task(2).Text30 is the same comparison as Tasks(2).Text30 = Task(1).Text30.

So you can cut down on the number of tests that you do by eliminating tests that you have already performed.  This is done by starting the inner loop at the current value of the outer loop.

e.g.

For Temp2 = 1 To ActiveProject.Tasks.Count

should be revised to

For Temp2 = Temp To ActiveProject.Tasks.Count

However an even quicker way would be to use a Scripting.Dictionary. I don't have project installed on my PC but even so if the code below doesn't work it should at least point you in the right direction

Sub Lacunza()

    Dim myUniqueText30 As Scripting.Dictionary
    Set myUniqueText30 = New Scripting.Dictionary

    Dim myTask As Long
    For myTask = 1 To ActiveProject.Tasks.Count

        With ActiveDocument.Tasks(myTask)

            If myUniqueText30.Exists(.Text30) Then

                .Flag5 = 1

            Else

                myUniqueText30.Add Key:=.Text30, Item:=myTask

            End If

    Next

    ' As this point you have a scripting dictionary which will return the task id
    ' where the first occurence of a particular Text30 value was found.

End Sub

I would like to refresh the topic a little bit.
The problem is that using Visual Basic inside my MSProject I constantly get 91 Run-time error.
I've even copied the solutions above to check if the exactly same code also doesn't work and I've got also the 91 Run-time error.
I've marked that it happens always when I want to use a task number from For loop like:
     With ActiveProject
        For i = 1 To ActiveProject.Tasks.Count
         If .Tasks(i).Text13 <> "" Then
            If text13values.Exists(ActiveProject.Tasks(i).Text13) Then
                taskList = text13values(ActiveProject.Tasks(i).Text13) & "," & i
                text13values(ActiveProject.Tasks(i).Text13) = taskList
            Else
                text13values.Add Key:=ActiveProject.Tasks(i).Text13, Item:=i
            End If
        End If
        Next i

    End With

"If .Tasks(i).Text13 <> "" Then" is highlited and gives "Object variable or With block variable not set". No matter how simple is the code, it doesn't work with this kind of For loop.
PS. MSProject is in version 2016.
Many thanks for any advise!


Is this a proper way of "loading" views in PHP? As a learning exercise, I'm developing my own PHP framework. I'm looking for a way to "load views" (kinda like CodeIgniter does it), without polluting my general scope.

I came up with the following, basic, example:

$data['test'] = 'Hello world';

$str = load_view($data, true);
echo $str;

function load_view($data, $store = false) {
    extract($data);

    ob_start();
    include('view.php');

    if($store)  return ob_get_clean();
    else        ob_end_flush();
}

// End of file

view.php

<?php echo $test; ?>

I could also use load_view($data), which would output the contents of view.php immediately.

Edit: I'm mostly worried about performance. As Peter pointed out, I'm aware that the function should be a class method that's seperate from the logic.

I agree that its a better pattern to wrap your view logic in a class.

Here is some code I whipped together tonight - It represents the simplest class I could devise that contains the minimum logic that I require in a view:

Includes - Ability to include other views
Captures - Ability to easily capture content within your view
Layouts - Ability to inject data into a re-usable layout template
Fetching - Ability to fetch view output instead of sending it to output buffer
data - Ability to access the resulting data once the view is finished

[edit] Refactored per conversation in comments regarding passing $data by reference.

View.php

<?php
/**
 * Simple view class that supports includes, capturing, and layouts, as well
 * as retrieving rendered view content and resulting data.
 *
 * *NOTE* When a view uses a layout, the output of the view is ignored, as
 *        as the view is expected to use capture() to send data to the layout.
 *
 * @author David Farrell <DavidPFarrell@gmail.com>
 */
class View implements ArrayAccess
{
    /**
     * View file to include
     * @var string
     */
    private $file;

    /**
     * View data
     * @var array
     */
    private $data;

    /**
     * Layout to include (optional)
     * @var string
     */
    private $layout;

    /**
     * Constructor
     *
     * @param string $file file to include
     */
    public function __construct($file)
    {
        $this->file = $file;
    }

    /**
     * render Renders the view using the given data
     *
     * @param array $data
     * @return void
     */
    public function render($data)
    {
        $this->data = $data;
        $this->layout = null;

        ob_start();

        include ($this->file);

        // If we did not set a layout
        if (null === $this->layout)
        {
            // flush view output
            ob_end_flush();
        }
        // We set a layout
        else
        {
            // Ignore view output
            ob_end_clean();

            // Include the layout
            $this->include_file($this->layout);
        }
    }

    /**
     * fetch Fetches the view result intead of sending it to the output buffer
     *
     * @param array $data
     * @return string The rendered view content
     */
    public function fetch($data)
    {
        ob_start();
        $this->render($data);
        return ob_get_clean();
    }

    /**
     * get_data Returns the view data
     *
     * @return array
     */
    public function get_data()
    {
        return $this->data;
    }

    /**
     * include_file Used by view to include sub-views
     *
     * @param string $file
     * @return void
     */
    protected function include_file($file)
    {
        $v = new View($file);
        $v->render($this->data);
        $this->data = $v->get_data();
    }

    /**
     * set_layout Used by view to indicate the use of a layout.
     *
     * If a layout is selected, the normal output of the view wil be
     * discarded.  The only way to send data to the layout is via
     * capture()
     *
     * @param string $file
     * @return void
     */
    protected function set_layout($file)
    {
        $this->layout = $file;
    }

    /**
     * capture Used by view to capture output.
     *
     * When a view is using a layout (via set_layout()), the only way to pass
     * data to the layout is via capture(), but the view can use capture()
     * to capture text any time, for any reason, even if the view is not using
     * a layout
     *
     * @return void
     */
    protected function capture()
    {
        ob_start();
    }

    /**
     * end_capture Used by view to signal end of a capture().
     *
     * The content of the capture is stored under $name
     *
     * @param string $name
     * @return void
     */
    protected function end_capture($name)
    {
        $this->data[$name] = ob_get_clean();
    }

    /* ArrayAccess methods */
    public function offsetExists($offset)      { return isset($this->data[$offset]); }
    public function offsetGet($offset)         { return $this->data[$offset]; }
    public function offsetSet($offset, $value) { $this->data[$offset] = $value; }
    public function offsetUnset($offset)       { unset($this->data[$offset]); }

}

run.php

<?php
require "View.php";

$v = new View('view_main_simple.php');
$fetch = $v->fetch(array('message' => 'Hello, world'));
print("Fetch result: {$fetch}\n");

$v = new View('view_main_complex.php');
$v->render(array('one' => 1, 'two' => 2, 'rows' => array('a','b','c')));

$data = $v->get_data();

print("\n");
var_export($data);

view_main_simple.php

The message is: <?php echo $this['message'] ?>

view_main_complex.php

<?php $this->set_layout('view_layout.php') ?>
<?php $this->capture() ?>
    one=<?php echo $this['one'] ?>

    <?php $this->include_file('view_include.php') ?>
    three=<?php echo $this['three'] ?>

<?php $this->end_capture('body') ?>

view_include.php

two=<?php echo $this['two'] ?>

<?php $this['three'] = 3 ?>

    <?php foreach($this['rows'] as $row) { ?>

<?php echo $row ?>

    <?php } ?>

view_layout.php

<?php echo $this['body'] ?>

Program Output

Fetch result: The message is: Hello, world

    one=1

    two=2

a

b

c

    three=3

array (
  'one' => 1,
  'two' => 2,
  'rows' =>
  array (
    0 => 'a',
    1 => 'b',
    2 => 'c',
  ),
  'three' => 3,
  'body' => '   one=1

    two=2

a

b

c

    three=3

',
)

No this is an ugly way to do it.

extract() (PHP4 stuff in 2012/2013?)

The problem with exract() is that it's creating variables ionto the global hyperspace (oh God, why) where can exist (in localy also!) any other variable and can have name collisions  and can overwrite the old values. Beside this you are losing the control over your code and it will be hard to maintain (debug, fix also) and to extend.

load_view()

Not always returns a value: in PHP this is okay but in general programming it's a bad habit. I do one thing in a case and in another one i do a complete different stuff in same function? And why am i in a function? How about a non-static class method where i know everything in my small environment?

Here is a small example of an idea:

View class

<?php
class View {

    private $_file;
    public $Data;

    public function __construct($viewFile, array $data) {
        $this->_file = $viewFile();
        $this->Data = $data;
    }

    public function Render()
    {
        require $this->_file;
    }

}

Usage

In the view file:

<?php
foreach ($this->Data["rows"] as $object) {
    echo "
";
    echo $object->Name;
    echo "
";}
?>

The output buffer handling is never part of the view it self. There have to be some kind of ViewEngine which can handle this thing. One thing one responsibility.

The problem with the example is that is's missing a whole lat infrastucture! In my MVC expiriment i have Controller, ControllerBuilder, ActionInvoker, abstract ActionResult, ViewResult a lot of other stuff what is necessary to get thing done. In my default IView implementation i have a Model "property" beside the ViewData, i can map a lot helper like Html or Url and any other and just then comes the others: RenderPartial(), RenderSection(), Section(), SectionStart(), SectionEnd(), Layout(); these are pointing to my current IViewEngine implementation which is handling all these stuff.


Calculating total size of player data I am writing a function to calculate the total size of a "player appearance".

There are various "item slots" the player has, and if they are empty then 1 byte will be sent, otherwise there will be 2.

const getAppearanceBlockSize = (appearance: PlayerAppearance) => {
    const headObscured = isCoveringHead(appearance.outfit.head);

    return (
        40
        + (appearance.outfit.head ? 2 : 1)
        + (appearance.outfit.cape ? 2 : 1)
        + (appearance.outfit.amulet ? 2 : 1)
        + (appearance.outfit.weapon ? 2 : 1)
        + (appearance.outfit.shield ? 2 : 1)
        + (appearance.outfit.head ? 2 : 1)
        + (headObscured ? 2 : 4)
    );
};

The code seems fairly clear to me, but Code Climate has given it a high "cognitive complexity" score - indicating that the code is complex and should be broken up.

I can't think of any ways to break the code up, however, that wouldn't result in it being more complex than it currently is.

I don't know anything about CodeClimate or how it determines complexity, but this is the likely culprit right here:

return (
    40
    + (appearance.outfit.head ? 2 : 1)
    + (appearance.outfit.cape ? 2 : 1)
    + (appearance.outfit.amulet ? 2 : 1)
    + (appearance.outfit.weapon ? 2 : 1)
    + (appearance.outfit.shield ? 2 : 1)
    + (appearance.outfit.head ? 2 : 1)
    + (headObscured ? 2 : 4)
);

This is pretty hard to read and understand at a glance, and all of the ternary operators certainly don't help. Without knowing more about your object it is hard to review, but to me it would make more sense to have a method like this on your outfit object

function getSlotSize(slot) {
    let size = 0;
    if (this.slots.includes(slot)) {
        size = slotIsEmpty(slot) ? 2 : 1;
        if (slot === "head") {
            size += 2 * isCoveringHead(this.head);
        }
    }

    return size;
}

function slotIsEmpty(slot) {
    return this.[slot] === null || this.[slot] === undefined;
}

Now you've separated out your logic for determining the size of everything instead of having to jam it into one function.

An even better approach may be to OOP this, and create objects representing a slot (or a specific kind of slot) and then each one should have a getSize method. Without knowing more about your code it is hard to say whether or not that would be overkill.

You may loose the benefit of TS here, but you could do something like this

const getAppearanceBlockSize = (appearance: PlayerAppearance) => {
   let score = isCoveringHead(appearance.outfit.head)? 4 :2;

    ['head', 'cape', 'amulet', 'weapon', 'shield']
     .forEach(p => score+= (appearance.outfit[p]? 2 : 1));

   return score + 40;
}


"Human" interfaces with two implementation classes The Helloworld class executes all of the methods. Human is the interface, and Nate & Ryan are two classes that implement the Human interface. Are there any deficiencies or faults that my code contains that could help me in the long run?

public class Helloworld{

    public static void main(String[] args) {

        Human ryan = new Ryan();
        ryan.setHeight(12);
        System.out.println("Ryan's height is " + ryan.getHeight());

        Human nate = new Nate();
        nate.setHeight(32);
        System.out.println("Nate's height is " + nate.getHeight());

        nate.hit(ryan);

        /*
         * OUTPUT --------------------------------------
         *
         * Ryan's height is 12
         * Nate's height is 32
         * Nate has hit Ryan
         *
         */

    }

}

interface Human{

    public void sleep();
    public void eat();
    public void wakeUp();
    public void walk();
    public void hit(Human name);
    public void setHeight(int height);
    public int getHeight();
    public String getName();

}

class Nate implements Human{

    int height = 0;
    final String name = "Nate";

    public String getName() {
        return this.name;
    }

    public void setHeight(int height) {
        if(height > 0) {
            this.height = height;
        }else {
            System.out.println("You can't set Nate's height to less than 0.");
        }
    }
    public int getHeight() {
        return this.height;
    }
    public void sleep() {
        System.out.println("Nate has fallen asleep");
    }
    public void eat() {
        System.out.println("Nate has eaten");
    }
    public void wakeUp() {
        System.out.println("Nate has woken up");
    }
    public void walk() {
        System.out.println("Nate is walking");
    }
    public void hit(Human name) {
        System.out.println("Nate has hit " + name.getName());
    }

}

class Ryan implements Human{

    int height = 0;
    final String name = "Ryan";

    public String getName() {
        return this.name;
    }

    public void setHeight(int height) {
        if(height > 0) {
            this.height = height;
        }else {
            System.out.println("You can't set Ryan's height to less than 0.");
        }
    }
    public int getHeight() {
        return this.height;
    }
    public void sleep() {
        System.out.println("Ryan has fallen asleep");
    }
    public void eat() {
        System.out.println("Ryan has eaten");
    }
    public void wakeUp() {
        System.out.println("Ryan has woken up");
    }
    public void walk() {
        System.out.println("Ryan is walking");
    }
    public void hit(Human name) {
        System.out.println("Ryan has hit " + name.getName());
    }

}

A class is a blueprint or template or set of instructions to build a specific type of object. Every object is built from a class.
  An instance is a specific object built from a specific class. It is assigned to a reference variable that is used to access all of the instance's properties and methods.

Ryan and nate should both be an instance. They have the same properties. From the 2 classes you can extract one template and make it a Human class.

What you are doing now is hard coding their properties into the methods. Try to make it more dynamic by creating one class.

public void eat() {
    System.out.println("Nate has eaten");
}

Can then be tranformed into:

public void eat() {
    System.out.println(this.name + " has eaten");
}

To get started you can use this as reference.
class Human {
    private int height;
    private String name;

    public Human(String name, int height) {
        this.name = name;
        this.height = height;
    }

    public Human(String name) {
        this(name, 0);
    }

    public String getName() {
        return name;
    }

    public void setHeight(int height) {
        if (height > 0) {
            this.height = height;
        } else {
            System.out.println("You can't set " + this.getName() + "'s height to less than 0.");
        }
    }

    public int getHeight() {
        return this.height;
    }
    public void sleep() {
        System.out.println(this.getName() + " has fallen asleep");
    }
    public void eat() {
        System.out.println(this.getName() + " has eaten");
    }
    public void wakeUp() {
        System.out.println(this.getName() + " has woken up");
    }
    public void walk() {
        System.out.println(this.getName() + " is walking");
    }
    public void hit(Human name) {
        System.out.println(this.getName() + " has hit " + name.getName());
    }
}

You can construct objects like this.

Human Ryan = new Human("Ryan");
Humane Nate = new Human("Nate");

PS: Solution may not be exact, but hope you got the idea.