Remove duplicates from array and save it to another one So I have been tasked to make an array without duplicated values from another existing array.
So I did it, but I want to know is there some other better way to do that.
Example input/output:
Input: 10, 15, 10, 5, 1, 3
Output: 10, 15, 5, 1, 3
So here is my code.
#include <stdio.h>

int main(void) {
  const int MAX_ARRAY_SIZE = 5;

  int m[MAX_ARRAY_SIZE], p[MAX_ARRAY_SIZE];

  for(int i = 0; i < MAX_ARRAY_SIZE; i++) {
    printf("Enter number: ");
    scanf("%d",&m[i]);
  }
  int k = 0;
  int dup = 0;
  for(int i =0; i < MAX_ARRAY_SIZE; i++) {
    for(int j = i +1; j <MAX_ARRAY_SIZE; j++) {
        if(m[i] == m[j]) {
            dup = 1;
        }
    }
    if(dup != 1) {
      p[k++] = m[i];
    }
    dup = 0;
  }

  printf("The new array without repeated values\n");
  for(int i = 0; i < k; i++) {
    printf("%d\n",p[i]);
  }

  return 0;
}

I'm not sure if this is the right and simple way I do that. I want some suggestions.
Thanks in advance. :)

Early termination
After
        dup = 1;

you should break. There's no need to execute the rest of the loop.
Booleans
Consider using <stdbool.h>, making bool dup = false, later assigning it true, and writing if (!dup).
Complexity
In practical terms, an array of five values poses no computational cost. However, if your prof cares about complexity analysis, the "proper" solution to this would need to complete in linear time (rather than your current quadratic time), using something like a hash-set, with pseudocode:
Set *seen = make_set();
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
    int m;
    scanf(&m);
    if (!contains(seen, m))
        add(seen, m);
}

for (m in seen)
    printf(m);

A few comments:

Using printf/scanf is something like thirty years out of date. Use cin and cout instead. They are superior in almost every way -- easier to read, type safe, not prone to stack overflow, etc. etc.

I am sure this is controversial, since, especially among C/C++ programmers brevity seems more important than clarity, but all those single letter variable names that bear no resemblance to their purpose makes the code way harder to follow. Why not call m "withDups" and p "noDups"? It'd make it a lot clearer what you are doing. Why not call k "noDupsEnd"? I'd go so far as to change the names of i,j too since that is just confusing, but I will grant that this is standard practice in C/C++

So instead of i,j use a better form of forloop:
  for(int passOne: withDups)
  {
      for(int passTwo: withDups)
        ifpassOne == passTwo)
        {
           dup = true;
           break;
        }
     if(! dup) noDups[noDupsEnd++] = withDups[passOne];
 }
 // Or something like that. My C++ is a bit out of date, but I believe that is correct.

The advantage of this being that you are less likely to make dumb mistakes and the code is easier to understand.

You could further simplify this by making the inner loop search noDups upto notDupsEnd, meaning that it'll make less passes in general.
Finally, algorithmically, I think truthfully it depends on the actual underlying requirements. If you are dealing with arrays of five elements (or let's say up to 100 elements) then your solution is algorithmically fine. However, the complexity of this is potentially quadratic. This is a brute force approach. If you are going to have larger lists you need better data structures, such as a hash set, or a tree to maintain the values already in nodups. That is obviously rather more complex, but will reduce the performance complexity substantially, potentially to close linear with a good hash table, if you have lots of memory, or at least n.log(n) with a tree structure of some kind.

For example, if you use a simple hash table (forgive, my C++ is a bit rusty) you might do something like this. Here I am using vectors which are more flexible than fixed size arrays.
// Return a vector containing the input vector maintaining order but removing duplicates.
// Neither input or output vector can contain -1
std::vector<int> removeDups(std:vector<int> arr)
{
   // We need a bit more space in our hash table than the original table, so this
   //  multiplier gives us extra space
   const int hashTblMultiplier = 2;
   const int hashTblSize = arr.size() * hasTblMultiplier;
   // Give it a capacity to make sure it doesn't go through qaudratic copies in expansions.
   // If a vector has to auto expand then it must copy all its contents, so if the vector
   /// has too small a capacity it can drop into some nasty performance behaviors.
   const result = new std::vector<int>(size /2);
   // For this simple implementation I assume arr only has positive values. Otherwise the hash
   // table will have to be a bit more complicated.
   auto hashTable = new std:vector<int>(hashTblSize, -1);
   for(int item: arr)
   {
      // Use simple linear probing for hash collision resolution and a simple hash function
      // which assumes the input data is equally distributed.
      int hash = item % hashTblSize;
      while(hashTbl[hash] != item && hashTbl[hash] != -1)
         hash = (hash+1)%hashTblSize;
      if(hashTbl[hash] == -1)
      {
         hasTbl[hash] = item;
         result.push_back(item);
      }
   }
   return result;
}


Calculating compass direction I have a heading, which is an integer and from it I would like to figure out the compass direction (North, North-East,...) and return the appropriate icon. I feel like I'm probably already at the cleanest solution but I would love to be proven wrong.

public GetHeadingImage(string iconName, int heading){
        if (IsNorthHeading(heading))
            return iconName  + "n" + ICON_FILE_EXTENTION;
        if (IsNorthEastHeading(heading))
            return iconName + "ne" + ICON_FILE_EXTENTION;
        if (IsEastHeading(heading))
            return iconName + "e" + ICON_FILE_EXTENTION;
        /*A bunch more lines*/
}
private bool IsNorthHeading(int heading)
{
    return heading < 23 || heading > 337;
}
/* A bunch more extracted test methods*/

A simple solution is a good solution:

public GetHeadingImage(string iconName, int heading){
    var directions = new string[] {
        "n", "ne", "e", "se", "s", "sw", "w", "nw", "n"
    };

    var index = (heading + 23) / 45;
    return iconName + directions[index] + ICON_FILE_EXTENSION;
}

A formula that gives the 8-way compass directions.
Is working for any value of X and Y .For X=Y=0 the result is undefined.
I write the formula in the same way ,that i did in excel.

f(X,Y)=MOD(2*(2-SIGN(Y1)-(1+SIGN(X1))*(1-SIGN(Y1^2)))-SIGN(X1*Y1)-0.5*SIGN(Y1*X1^3-X1*Y1^3)

  *(1+SIGN(ABS(ABS(X1)-ABS(Y1))/(ABS(X1)+ABS(Y1))-2^0.5+1-2^-22)),8)

The formula gives for the East =0 and NE=1,N=2,NW=3,W=4,SW=5,S=6 and SE=7.


Can this insertion sort be optimized? Could you provide feedback for this code? For arrays of length 2, is it more efficient not to use a sorting algorithm?

package insertion.sort;

import java.util.Arrays;

public class InsertionSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int[] testArr = {-10, -5, 100, 51, 6, 50};
        insertionSort(testArr);
        System.out.println(Arrays.toString(testArr));
    }

    public static void insertionSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for(j = i; j > 0 && arr[j-1] > temp; j--)
                arr[j] = arr[j-1];
            arr[j] = temp;
        }
    }

}

By the way, I've noticed "quicksort" is spelt all as one word, but "insertion sort" is spelt as two. Is that right? Would anyone ever say "quicksort sort"?

As insertion sort is an O(n2) algorithm, there's not much point to optimizing it.  For any input that is large enough for you to care about the performance, you would want to pick a sorting algorithm with better bounds.  Quicksort, for example, is usually closer to O(n log n).

That said, I'll point out some style issues:

You should never omit optional braces, as you've done for the inner for-loop.  Think of it this way: anytime you omit braces, you're a contributing factor to a future coding accident.  (Apple learned this lesson the hard way; their new swift language requires braces.)
Variables can usually be named better than "temp".  Renaming temp to elementToInsert, for example, would make your code self-documenting.

I do not see any performance issues. Stylistically, a No Raw Loops rule mandates factoring out an inner loop into a method (shift_right or something like that).


Load fifty million integers as quickly as possible in Java I am working my way through Project Euler. Many of the problems deal with prime number calculations: this is the type of code that can be extracted into a separate class and reused.

While calculating primes can be done quickly using certain methods, I was able to speed up the process of "getting prime numbers" by using a list of primes on disk and loading them. It is an order of magnitude faster than any calculation, but still takes roughly three minutes loading from an SSD.

What I did:

I took a publicly-available list of the first fifty million primes (some problems do use a significant portion of those numbers).
I wrote a program to convert the numbers from their textual representation to binary using Java's DataOutputStream. The file is simply fifty million four-byte integers in a row.
The utility method below loads each integer into an array using DataInputStream. It produces correct results, but it slow.

Is there any way to speed up the process of loading 50,000,000 integers? If I need to preprocess the data differently I am willing to do that.

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class Test {

  public static int[] loadByQuantity(int argNumPrimes) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream("primes.bin"))) {
      for (int i = 0; i < primes.length; ++i) {
        primes[i] = in.readInt();
      }
    }
    catch (IOException ex) {
      throw new RuntimeException(ex);
    }
    return primes;
  }

}

Your code is a bit messy, and having the file name hard-coded in to your function is not great. Also, the "Hungarian Notation" (using things like arg to prefix your function parameters - note, it's a parameter, not an argument, by the way)... is not conventional.

On the other hand, I understand this is an exercise to test performance.... and it's not about the resusability (yet) of the code.

Still, I know from experience that reusability will happen, and your code will need some changes.

I also know, from experience, that memory-mapped IO is much faster in Java than other IO forms, so I figured I would have a kick at this problem.

I took my prime generator I had reveiewed here on Code Review previously ( Thread Safe Prime Generator ) and I generated the first 50,000,000 primes in to a file on my own system, then I tested your code against it (and after changing the file name to a parameter, it worked).

Out of interest, generating and writing to file of the primes took about 5 minutes on my computer - 311 seconds - much of which was probably IO time too.

Then, I converted your function to be:

public static int[] loadByQuantity(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
        for (int i = 0; i < primes.length; ++i) {
            primes[i] = in.readInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

The only difference is the file-name is now a parameter.

Then I wrote a little test system to time how long your code took for me:

public static void time(Supplier<int[]> task, String name) {
    long nanos = System.nanoTime();
    int[] primes = task.get();
    System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
    System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
    System.out.println("----");
}

public static void main(String[] args) {
    int count = 50000000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
}

I then implemented the same functionality using an NIO mechanism specifically using memory-mapped IO: http://docs.oracle.com/javase/8/docs/api/java/nio/MappedByteBuffer.html

This type of IO is designed to significantly reduce the amount of memory copies are made of the input file. It also means that Java reads the content out of the OS, without first copying it in to Java's memory space.

For the types of sequential IO this problem has, I expected the performance improvements to be significant.

Further, the MappedByteBuffer has methods getInt() which also decodes 4 bytes in to an int for you: http://docs.oracle.com/javase/8/docs/api/java/nio/ByteBuffer.html#getInt--

Here's the code I came up with. Note, I have used the same exception handling that you use, and also the same array initialization. I believe you should be throwing exceptions from these methods, and not just wrapping them in runtime exceptions:

public static int[] loadByNIO(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
        MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
        for (int i = 0; i < numPrimes; i++) {
            primes[i] = mbb.getInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

I then ran the process a couple of times in the main method, and compared the results:

public static void main(String[] args) {
    int count = 50_000_000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
}

The NIO operation is, as expected, significantly faster... 1500 times faster

Task OP took 214163.250ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 141.511ms
Count 50000000
First 2
Last 982451653
----
Task OP took 214633.128ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 159.571ms
Count 50000000
First 2
Last 982451653
----

I admit, it is far faster than I was expecting too.... but, the results are correct.

Now, I encourage you to experiment with how to put this concept behind a Java stream, instead of populating the full 50,000,000 in to an array. By streaming the results you can start your "real" computation sooner, without the latency of having to read all the primes from the file. For example, consider what you could do with logic like:

primes.stream().....

where primes was reading the values on-demand from the file.

Here's the full code I have been running:

package prperf;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;
import java.nio.file.Paths;
import java.util.function.Supplier;

public class PrimeReader {

    public static int[] loadByQuantity(int argNumPrimes, String fname) {
        int numPrimes = Math.min(argNumPrimes, 50_000_000);
        int[] primes = new int[numPrimes];
        try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
            for (int i = 0; i < primes.length; ++i) {
                primes[i] = in.readInt();
            }
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return primes;
    }

    public static int[] loadByNIO(int argNumPrimes, String fname) {
        int numPrimes = Math.min(argNumPrimes, 50_000_000);
        int[] primes = new int[numPrimes];
        try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
            MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
            for (int i = 0; i < numPrimes; i++) {
                primes[i] = mbb.getInt();
            }
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return primes;
    }

    public static void time(Supplier<int[]> task, String name) {
        long nanos = System.nanoTime();
        int[] primes = task.get();
        System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
        System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
        System.out.println("----");
    }

    public static void main(String[] args) {
        int count = 50_000_000;
        time(() -> loadByQuantity(count, "primes.dat"), "OP");
        time(() -> loadByNIO(count, "primes.dat"), "NIO");
        time(() -> loadByQuantity(count, "primes.dat"), "OP");
        time(() -> loadByNIO(count, "primes.dat"), "NIO");
    }

}

A BitSet

One bit for each odd number up to 1,000,000,000, set if prime. That's 50847533 primes, not including 2. Should take about 64MB, vs 200MB for an array of integers. For any odd number you divide by 2 and look up that index.

Incidentally, a fairly simple sieve of Eratosthenes should take much less than three minutes to sieve a billion numbers in Java, more like ten seconds. This example does just that.

public static void main(String[] args) {
    int max = 1000000000;
    BitSet sieve = new BitSet(max/2+1);
    for(int i = 1; i < max/2; i++){
        sieve.set(i,true);
    }

    //the sieve
    for(int p = 3; p*p < max; p += 2){
        if(sieve.get(p/2)){
            for(int m = p*p; m < max; m += p+p){
                sieve.set(m/2,false);
            }
        }
    }

    //count primes and optionally print them out
    int primecount = 0;
    int last = 0;

    for(int p = 3; p < max; p += 2){
        if(sieve.get(p/2)){
            //System.out.println(p);
        }
    }
    System.out.println(primecount);
}

And Primesieve is about two orders of magnitude faster still by actually optimizing.


Extracting the last component (basename) of a filesystem path fn basename<'a>(path: &'a str, sep: char) -> Cow<'a, str> {
    let pieces = path.split(sep);
    match pieces.last() {
        Some(p) => p.into(),
        None => path.into(),
    }
}

Usage:

println!("'{}'", basename("foo", '/'));    // outputs 'foo'
println!("'{}'", basename("bob/", '/'));   // outputs ''
println!("'{}'", basename("/usr/local/bin/rustc", '/')); // outputs 'rustc'

I think the split() into a match on last() is kind of elegant.
I know there is some work needed to handle both str and String, I am not sold on the use of Cow and needing to define a lifetime for the string.

I am not sold on Cow because later on I need to extract from it.

let prog = basename(&args[0], '/').into_owned();

It feels like I am working too hard.

Firstly, you should use rsplit and next rather than split and last, as it starts at the more appropriate end:

fn basename<'a>(path: &'a str, sep: char) -> Cow<'a, str> {
    let pieces = path.rsplit(sep);
    match pieces.next() {
        Some(p) => p.into(),
        None => path.into(),
    }
}

Secondly, you shouldn’t be using strings for this; you should be using paths, because that’s semantically what you’re dealing with.

The easiest way to get a path tends to be to take a &Path or a generic parameter implementing AsRef<Path> and calling .as_ref() on it; str, String, Path, PathBuf and more implement it.

You can get the base name from a &Path with file_name; this admittedly produces a Option<&OsStr>, so if you want to display the path you’d need to convert it back towards a string with e.g. .and_then(|s| s.to_str()).

Anyway, the point of this latter part is just that for something that is semantically a path, you should be handling it specially, as a rule; a path need not be Unicode. Think on it more.

pub fn basename<'a>(path: &'a str) -> Cow<'a, str> {
    let mut pieces = path.rsplitn(2, |c| c == '/' || c == '\\');
    match pieces.next() {
        Some(p) => p.into(),
        None => path.into(),
    }
}

This works for Unix or Windows path separators and does the least amount of work since it breaks the string into two pieces, the basename and the rest.


Rewriting clumsy code that gets the value of a nested property in JS object I have an API that returns JSON, where the value that I need is stored in either one of the two object properties:

data.d.GetContextWebInformation.FormDigestValue

or

data.value.GetContextWebInformation.FormDigestValue

The code that I'm using is pretty clumsy. At first, I used something like this:

if (data && data.d && data.d.GetContextWebInformation && data.d.GetContextWebInformation.FormDigestValue) {
    this.options.token = data.d.GetContextWebInformation.FormDigestValue;
} else {
// check for second one

Now I've rewritten it using try/catch, and it looks a bit cleaner, but still clumsy:

    var token;
    try {
        // If Verbosity was odata=verbose:
        token = data.d.GetContextWebInformation.FormDigestValue;
    } catch (ex) {
        try {
            // If Verbosity was odata=nometadata or odata=minimalmetadata:
            token = data.value.GetContextWebInformation.FormDigestValue;
        } catch (ex) {
            throw 'Unable to obtain authorization token.';
        }
    } finally {
        if (token) { this.options.token = token; }
    }

What would be a better way to write the same code for a cleaner, nicer look? If that matters, I need to support IE9 so probably can't use newer language features.

If you're certain the token exists in either of the objects you can do:

First check for the existence of the value in data.

var value = data.d || data.value;

then access the value to get the token

var token = value && value.GetContextWebInformation.FormDigestValue;

var value = data.d || data.value;

var token = value && value.GetContextWebInformation.FormDigestValue;

if (token) {
  this.options.token = token;
}

Otherwise, you can use getIn function:

function getIn(pathArray, obj) {
  var tmp = obj;
  for (var i = 0; i < pathArray.length; i++) {
    if (tmp.hasOwnProperty(pathArray[i])) {
      tmp = tmp[pathArray[i]];
      continue;
    }
    return undefined;
  }
  return tmp;
}

var token = getIn(['d', 'GetContextWebInformation', 'FormDigestValue'], data) ||
            getIn(['value', 'GetContextWebInformation', 'FormDigestValue'], data);

if (token) {
  this.options.token = token;
}

You can use {} fallbacks at each nesting level.

((data && (data.d || data.value) || {}).GetContextWebInformation || {}).FormDigestValue

I'm not saying it's more readable in non-trivial cases, though.
In the bright future we might be able to use optional chaining e.g. var foo = a?.b?.c?.d


Simple calculator in C I made a very simple calculator in C that allows the user to perform calculations like addition, subtraction, multiplication and division. This is my first C program that I've made outside of my University course. It would be great to get some feedback on this program so that I can avoid bad practices early on in my coding.

//Calculator program
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int menu; //Variable for the number the user inputs
    float num1, num2, result; //Float variables for the user input and output, used floats in case the user enters e.g. 14.7

    printf("Enter a number from the list below\n\n");

    printf("1. Addition\n"); //Calculator menu, user must enter a value from 1 - 4 for the program to work
    printf("2. Subtraction\n");
    printf("3. Multiplication\n");
    printf("4. Division\n\n");

    printf("Enter number: "); //User input for the calculator menu
    scanf("%d", &menu);

    printf("\n");

    switch(menu) //switch statement for menu
    {
    case 1:
        printf("You entered Addition\n\n");

        printf("Enter first number: "); //User input for first number
        scanf("%f", &num1);

        printf("Enter second number: "); //User input for second number
        scanf("%f", &num2);

        printf("\n");

        result = num1 + num2; //Addition calculation

        printf("%.2f + %.2f = %.2f\n", num1, num2, result); //Addition output
        break;
    case 2:
        printf("You entered Subtraction\n\n");

        printf("Enter first number: "); //User input for first number
        scanf("%f", &num1);

        printf("Enter second number: "); //User input for second number
        scanf("%f", &num2);

        printf("\n");

        result = num1 - num2; //Subtraction calculation

        printf("%.2f - %.2f = %.2f\n", num1, num2, result); //Subtraction output
        break;
    case 3:
        printf("You entered Multiplication\n\n");

        printf("Enter first number: "); //User input for first number
        scanf("%f", &num1);

        printf("Enter second number: "); //User input for second number
        scanf("%f", &num2);

        printf("\n");

        result = num1 * num2; //Multiplication calculation

        printf("%.2f * %.2f = %.2f\n", num1, num2, result); //Multiplication Output
        break;
    case 4:
        printf("You entered Division\n\n");

        printf("Enter first number: "); //User input for first number
        scanf("%f", &num1);

        printf("Enter second number: "); //User input for first number
        scanf("%f", &num2);

        printf("\n");

        result = num1 / num2; //Division calculation

        printf("%.2f / %.2f = %.2f\n", num1, num2, result);
        break;
    default:
        printf("Enter correct number e.g 1 - 4\n"); //Outputted if the user enters a value other than 1 - 4
        break;
    }
    return 0;
}
//End of code

I must say, I respectively disagree with @ishyfishy's  example of the addition function. Although, I do agree with the point about splitting the arithmetic functions away from the main function.

I believe that the arithmetic functions should only handle performing the arithmetic; all the I/O should be handled by main function (I have been taught that this is a good practice, although I do not have a source right now).

So, the "1" (addition) section of the switch statement in main would look something like this:

scanf("%f", &num1);
scanf("%f", &num2);

result = addition(num1, num2);

printf("...", num1, num2, result);

And the addition function simply looks like this:

float addition(float num1, float num2) {
    return num1 + num2;
}

This doesn't make a much of a difference, but it speeds up your code a little bit.

Instead of storing the result of a calculation in result, it would be faster to just pass the return value an arithmetic functions into the statement/function that you will it next in.

For example, the end of the "1" (addition) section of the switch statement would look like this:

printf("%.2f + %.2f = %.2f\n", num1, num2, addition(num1, num2));

This is faster because it reduces memory interaction(however, not by much).

In this section:

printf("Enter a number from the list below\n\n");

printf("1. Addition\n"); //Calculator menu, user must enter a value from 1 - 4 for the program to work
printf("2. Subtraction\n");
printf("3. Multiplication\n");
printf("4. Division\n\n");

You make 5 calls to the printf function when you could easily just put all the strings into one and split them up by newline in a single printf call:

printf("Enter a number from the list below\n\n"
       "1. Addition\n"
       "2. Subtraction\n"
       "3. Multiplication\n"
       "4. Division\n");

This is also faster as you don't have to call a function 5 times.

Only use printf when you are need to use the formatting feature. Other than that, you are over-complicating things.

If you merely need to output a string with a newline here or there, use the built-in puts function; it automatically outputs a string with a newline on the end (and you can add more if needed).

For example, this line:

printf("You entered Addition\n\n");

Becomes:

puts("You entered Addition\n");

First of all, create functions for the operators you use. For instance, if you are performing addition, write the function as:

int add(int a,int b)
{
return a+b;
}

Same for subtraction, multiplication and division.

Also, why do you want to get the values from the user for each case? Try to use function for it:

int get()
{int a;
  scanf("%d",&a);
  return a;
}

Call the function get() whenever you want to get the input from the user.


Advent of code #2 Haskell solution I've tried to solve AoC day 2 challenge in Haskell (here - don't worry, it's not a competition so sharing a solution here is OK).

The goal is to implement a very simple VM with opcodes 1 (add), 2 (mult) and 99 (exit).

I feel like my solution is incredibly verbose. That maybe be because I rely heavily on the state monad (my background is imperative programming, so there's that). Is there anything I could improve without rewriting the whole solution?

Here's my code, thanks for all suggestions:

import Data.Sequence
import Control.Monad.State
import Data.List.Split

data Machine = Machine {
    mState :: Seq Int,
    mPos :: Int,
    isDone :: Bool
}

opReadHead :: State Machine Int
opReadHead = do
    machine <- get
    return $ index (mState machine) (mPos machine)

opReadAt :: Int -> State Machine Int
opReadAt target = do
    machine <- get
    return $ index (mState machine) target

opForward :: State Machine ()
opForward = do
    machine <- get
    put $ machine { mPos = mPos machine + 1 }

opWrite :: Int -> Int -> State Machine ()
opWrite target what = do
    machine <- get
    put $ machine { mState = update target what (mState machine) }

opReadNext :: State Machine Int
opReadNext = do
    a <- opReadHead
    opForward
    return a

opAdd :: State Machine ()
opAdd = do
    aPtr <- opReadNext
    a <- opReadAt aPtr
    bPtr <- opReadNext
    b <- opReadAt bPtr
    target <- opReadNext
    opWrite target (a + b)

opMult :: State Machine ()
opMult = do
    aPtr <- opReadNext
    a <- opReadAt aPtr
    bPtr <- opReadNext
    b <- opReadAt bPtr
    target <- opReadNext
    opWrite target (a * b)

opExit :: State Machine ()
opExit = do
    current <- get
    put $ current { isDone = True }

isMachineDone :: State Machine Bool
isMachineDone = do
    get >>= (return . isDone)

opcode :: Int -> State Machine ()
opcode 1 = opAdd
opcode 2 = opMult
opcode 99 = opExit

opExecuteNext :: State Machine ()
opExecuteNext = do
    opValue <- opReadNext
    opcode opValue

runCode :: State Machine ()
runCode = do
    done <- isMachineDone
    if done
    then return ()
    else opExecuteNext >> runCode

evalWith :: Machine -> Int -> Int -> Int
evalWith machine noun verb = do
    fst $ runState (do
        opWrite 1 noun
        opWrite 2 verb
        runCode
        opReadAt 0
        ) machine

main :: IO()
main = do
    fileData <- readFile "input"
    let memory = map read $ splitOn "," fileData
    let machine = Machine {
        mState = fromList memory,
        mPos = 0,
        isDone = False
    }
    let outputs = [(evalWith machine x y, (x, y)) | x <- [0..99], y <- [0..99]]
    print $ snd $ head $ Prelude.filter ((== 19690720) . fst) outputs
```

Use Control.Lens for code this stateful. (Control.Lens.TH must be used to define Machine.) May as well leave out type signatures this homogenous. Control.Monad.Loops often helps against explicit monadic recursion.

opReadAt target = uses mState $ (`index` target)
opReadNext = mPos <<+= 1 >>= opReadAt
opWrite target what = mState %= update target what

opBin op = do
    a <- opReadNext >>= opReadAt
    b <- opReadNext >>= opReadAt
    target <- opReadNext
    opWrite target $ op a b

opcode 1 = opBin (+)
opcode 2 = opBin (*)
opcode 99 = isDone .= True

runCode = (opReadNext >>= opCode) `untilM_` use isDone

evalWith :: Int -> Int -> Machine -> Int
evalWith noun verb = evalState $ do
    opWrite 1 noun
    opWrite 2 verb
    runCode
    opReadAt 0

Thanks for this, I used your example to finish mine that also uses State:

import System.IO
import Data.Sequence
import Control.Monad.State
import qualified Data.Text as T
import Data.Maybe

convertToInteger :: String -> Int
convertToInteger s = read s :: Int

type CompState = (Int, Seq Int)
type CompValue = Int

data Instruction = Add | Mult | Stop deriving (Show)

instruction :: State CompState Instruction
instruction = state $ \(pointer, mem) ->
    (case (Data.Sequence.lookup pointer mem) of
        Just 1 -> Add
        Just 2 -> Mult
        Just 99 -> Stop
        _ -> Stop
    , (pointer, mem))

calcul :: (Int -> Int -> Int) -> State CompState ()
calcul operator = state $ \(pointer, mem) ->
    let addr1 = Data.Sequence.lookup (pointer+1) mem
        addr2 = Data.Sequence.lookup (pointer+2) mem
        op1 = join $ Data.Sequence.lookup <$> addr1 <*> pure mem
        op2 = join $ Data.Sequence.lookup <$> addr2 <*> pure mem
        destAddr = Data.Sequence.lookup (pointer+3) mem
        val = (operator <$> op1 <*> op2)
        newMem = Data.Sequence.update <$> destAddr <*> val <*> pure mem in
    ((), (pointer+4, fromJust newMem))

computeStep :: State CompState ()
computeStep = do
    inst <- instruction

    _ <- case inst of
        Add -> calcul (+) >> computeStep
        Mult -> calcul (*) >> computeStep
        Stop -> return ()

    return ()

a = [1,0,0,0,99]
b = [2,3,0,3,99]
c = [2,4,4,5,99,0]
d = [1,1,1,4,99,5,6,0,99]

main :: IO()
main = do
    handle <- openFile "2-input.txt" ReadMode
    contents <- hGetContents handle

    let inputData = fromList . map convertToInteger . map T.unpack $ T.splitOn (T.pack ",") (T.pack contents)
    let updatedInputData = update 2 2 (update 1 12 inputData)

    print $ snd $ snd $ runState computeStep (0, updatedInputData)

Is it shorter or does it only look like it?


Handling parsing failure in Scala without exceptions I have a Scala (Play!) application that must get and parse some data in JSON from an external service. I want to be able to gently handle failure in the response format, but it is becoming messy. What I am doing right now is, for instance,

def columnsFor(json: JsValue): Option[Map[String, String]] =
  try {
    val cols = (json \ "responseBody" \ "columns") match {
      case JsArray(xs) => xs map { col =>
        ((col \ "leafid").as[String], (col \ "name").as[String])
      }
      case _ => throw new Exception("Response unparsable")
    }
    Some(cols.toMap)
  }
  catch {
    case e: Exception => None
  }

That is, I go parsing optimistically and throw an exception whenever I find something that does not match my expected format (the methods as[String] also raise exceptions when they do not find strings). Then I recover from the exception and give back a None.

This approach is working and allows me to go from a potentially broken textual response to some type-safe data.

The problem is that having all these try..catch blocks looks ugly and messy. In theory it would be nicer to use optional types during all parsing steps. But then all my data structures become messy, as at each level you must have Options. When the data is deeply nested, I do not know how to handle failure at all levels. Moreover, I do not want to return something like an Option[Map[Option[String], Option[String]], but just an Option[Map[String, String]].

Is there some better/more idiomatic way to handle failures during parsing?

EDIT

I try to make the question more clear. Say I am expecting a response like

{
    "foo": [1, 2, 3],
    "bar": [2, 5]
}

I want to be able to parse it; taking failure into account I want to get something of type Option[Map[String, List[Int]]]. Now the problem is that parsing errors can appear at any level. Maybe I get a map with string keys, but its values are not lists. Or maybe the values are lists, but the content of the lists are strings instead of ints. And so on.

Whenever I want to parse a value, say as a string, I can choose between x.as[String] and x.asOpt[String]. The former will throw an exception when dealing with wrong input, while the latter returns a Option[String]. Similarly, when dealing with an array, I can do pattern matching like

x match {
  case JsArray(xs) => // continue parsing
  case _ => // deal with failure
}

I can deal with failure returning None or with an exception.

If I choose to use exceptions all along, then I can just wrap everything inside a try..catch and be sure to have handled all failures. Otherwise, my problem is that at any level, I have to put an option. So I have to

get something with an awful type like Option[Map[Option[String], Option[List[Option[Int]]]]]
find some way to flatten this all the way down to turn into the more manageable Option[Map[String, List[Int]]]

Of course, thing become even worse as soon as the JSON gets more nested.

Having monads in your data structures is not messy, they allow you always to flatten their content during nested calculation steps. A simple definition of them can be:

trait Monad[A] {
  def map[B](f: A => B): Monad[B]
  def flatMap[B](f: A => Monad[B]): Monad[B]
}

Because Option is a monad you do not have to work with nested types:

scala> def inc(i: Int) = Option(i+1)
inc: (i: Int)Option[Int]

scala> val opt = inc(0)
opt: Option[Int] = Some(1)

scala> val nested = opt map inc
nested: Option[Option[Int]] = Some(Some(2))

scala> val flattened = opt flatMap inc
flattened: Option[Int] = Some(2)

Thus, there should never be a reason to nest monads deeply. Scala also has the for-comprehension which automatically  decomposes monads:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val none = for {
  o1 <- inc(0)
  o2 <- inc(o1)
  o3 <- inc(o2)
} yield o3

val some = for {
  o1 <- inc(0)
  o2 <- inc(o1)
  o3 <- inc(o2-1)
} yield o3

// Exiting paste mode, now interpreting.

none: Option[Int] = None
some: Option[Int] = Some(2)

In order to work with exceptions scala.util.Try is introduced in 2.10:

scala> import scala.util.{Try, Success, Failure}
import scala.util.{Try, Success, Failure}

scala> def err: Int = throw new RuntimeException
err: Int

scala> val fail = Try{err} map (_+1)
fail: scala.util.Try[Int] = Failure(java.lang.RuntimeException)

scala> val succ = Try{0} map (_+1)
succ: scala.util.Try[Int] = Success(1)

Nevertheless, Try should only used when you have to work with exceptions. When there is no special reason, exceptions should be avoided - they are not here to control the control flow but to tell us that an error occurred which normally can not be handled. They are some runtime thing - and why to use runtime things in a statically typed language? When you use monads the compiler always enforces you to write correct code:

scala> def countLen(xs: List[String]) = Option(xs) collect { case List(str) => str } map (_.length)
countLen: (xs: List[String])Option[Int]

scala> countLen(List("hello"))
res8: Option[Int] = Some(5)

scala> countLen(Nil)
res9: Option[Int] = None

scala> countLen(null) // please, never use null in Scala
res13: Option[Int] = None

With collect you ensure that you don't throw an exception during matching the contents. After that with map one can operate on the String and doesn't care anymore if an empty or a full list is passed to countLen.

Now, look at the documentation of Option, there are more useful methods which allow safe error handling. The only thing to keep in mind is not to use method get or a pattern match on the monad during calculation:

scala> Some(3).get
res10: Int = 3

scala> None.get // this throws an exception
java.util.NoSuchElementException: None.get

// this looks ugly and does not safe you from anything because it is equal
// to a null check
anyOption match {
  case Some(e) => // no error
  case None => // error
}

Now you may ask how to get the contents of a monad? That is a good question and the answer is: you won't. When you use a monad you say something like: Hey, I'm not interested if my code threw an error or if all worked fine. I want that my code works up to end and then I will look what's happened. Pattern matching on the content of a monad (means: accessing their content explicitly) is the last thing which should be done and only if there is no other way any more to go further with control flow.

There a lot of monads available in Scala and you have the possibility to easily create your own. Option allows only to get a notification if something happened wrong. If you wanna have the exact error message you can use Try (for exceptions) or Either (for all other things). Because Either is not really a monad (it has a Left- and a RightProjection which are the monads) it is unhandy to use. Thus, if you want to effectively work with error messages or even stack them you should take a look at scalaz.Validation.

EDIT

To address your edit, it seems that you never know the type you can get. This will complicate things a lot since you have to check the type of each element explicitly. I don't think it is possible to do this in a clean way without the use of a library which can do the typechecks for you. I suggest to take a look at some Scalaz or Shapeless code.

Nevertheless is is far easier to do such type checks in the parser and not in the AST traverser. Thus, I suggest using a JSON parser which can handle a type format given by the user and returns an error if it finds some unexpected content. I don't know if Play! can parse things like the following (which can be done in lift-json):

val json = """{ "foo": [1, 2, 3], "bar": [2, 5] }"""
class Content(foo: List[Double], bar: List[Double])
parse(json).extract[Content]

You can use Try:
val cols = Try {(json \ "responseBody" \ "columns")}

you can match it:
cols match {
  case Success(value) => ???
  case Failure(exception) =>
           println(exception.getMessage)
}

You can convert it to Option to avoid exception
val cols = Try {(json \ "responseBody" \ "columns")}.toOption

It gives None or Some(value).
cols match {
case Some(value) => ???
case None => ??
}

You can use asOpt
val cols = (json \ "responseBody" \ "columns").asOpt[String].getOrElse("")

OR
val cols = (json \ "responseBody" \ "columns").asOpt[String].orNull


Dynamically adding controls to a form in a WinForms project I have created this function in my DetailsScreen.cs, but I have no idea if this is the correct file to put this kind of code in, or if coding it this way is the correct approach. I know that it works because I have tested it.

My application generates a questionnaire based on selected (cyber security) standards. I have a form DetailsScreen, which requires the user to fill in some details such as name, company, etc. They also need to select from a checkedlist (questionStandardInput), the question standard they wish to use in this interview. For each selected standard, two answer standards need to be selected from two drop down lists (maturity answer standard and compliance answers standard).

Therefore, I need to be able to dynamically add labels and comboxes for each question standard. I asked because most code concerning label font etc. is placed in .Designer.cs files instead of the .cs files. But I need certain logic from the .cs file in order to properly format the controls, which is why I put it in here.

// Load answer input according to the number of questions standards selected.
private void questionStandardInput_MouseUp(object sender, MouseEventArgs e)
{
    questionLabels.Clear();
    maturityInput.Clear();
    complianceInput.Clear();
    selectionPanel.Controls.Clear();

    foreach (var item in questionStandardInput.CheckedItems)
    {
        Label qs_label = new Label();
        qs_label.Location = new Point(0, 0 + (questionLabels.Count * 115));
        qs_label.Font = new Font("Arial", 12F, FontStyle.Regular);
        qs_label.Size = new Size(150, 18);
        qs_label.Text = item.ToString();
        questionLabels.Add(qs_label);
        this.selectionPanel.Controls.Add(qs_label);

        Label m_label = new Label();
        m_label.Location = new Point(0, 0 + (questionLabels.Count * 115 + 35));
        m_label.Font = new Font("Arial", 12F, FontStyle.Regular);
        m_label.Size = new Size(150, 18);
        m_label.Text = "Maturity standard";
        this.selectionPanel.Controls.Add(m_label);

        Label c_label = new Label();
        c_label.Location = new Point(0, 0 + (questionLabels.Count * 115 + 70));
        c_label.Font = new Font("Arial", 12F, FontStyle.Regular);
        c_label.Size = new Size(170, 18);
        c_label.Text = "Compliance standard";
        this.selectionPanel.Controls.Add(c_label);

        ComboBox m_input = new ComboBox();
        m_input.Location = new Point(170, 0 + (questionLabels.Count * 115 + 35));
        m_input.Font = new Font("Arial", 12F, FontStyle.Regular);
        m_input.Size = new Size(200, 22);
        m_input.DropDownStyle = ComboBoxStyle.DropDownList;
        maturityInput.Add(m_input);
        this.selectionPanel.Controls.Add(m_input);

        ComboBox c_input = new ComboBox();
        c_input.Location = new Point(170, 0 + (questionLabels.Count * 115 + 70));
        c_input.Font = new Font("Arial", 12F, FontStyle.Regular);
        c_input.Size = new Size(200, 22);
        c_input.DropDownStyle = ComboBoxStyle.DropDownList;
        complianceInput.Add(c_input);
        this.selectionPanel.Controls.Add(c_input);

        InitializeMaturityStandardInput(m_input);
        InitializeComplianceStandardInput(c_input);
    }
    this.saveAssessmentButton.Location = new Point(235, 0 + (questionLabels.Count * 115));
    this.selectionPanel.Controls.Add(saveAssessmentButton);
}

In my eyes it is an appropriated way to build up your form that way. The *.Designer file is for designer generated code - but if you need to add custom logic to modify your GUI the *.cs file is the correct location.

Just a few points:

There are some numbers (115, 70, 35, ...) that seems to have a special meening (e.g. row height, margin, whatever). IMHO it makes sense to store that numbers as constants with a meaningful name and use that constants instead.
I am not sure if the MouseUp event is the right place to trigger that kind of logic. If there is another event (CheckBoxChanged, SelectedItemChanged, ...) I would suggest to use that.
There is some repeating logic for creating the ComboBox / Label and so on. That logic could be extracted to a separted method. For instance:

private static ComboBox CreateComboBox()
{
    return new ComboBox()
    {
        Font = new Font("Arial", 12F, FontStyle.Regular)
        Size = new Size(200, 22)
        DropDownStyle = ComboBoxStyle.DropDownList
    }
}

I have come up with my own solution with your help and some research. I have implemented the Model View Controller Passive View so that no logic is handled in the View. I still have a few loose digits to clean up, but that was not the main focus.

In the View's MouseUp event handler just two events are fired. One for the Presenter that will get data from the Model (that gets it from the database) which is passed to the User Control through the View, and one for the User Control to initialize itsself. The User Control is then added to the View.

View MouseUp event handler

// Fires the initializing user control and initializing user control data events.
private void questionStandardInput_MouseUp(object sender, MouseEventArgs e)
{
    InitializingUserControl?.Invoke(this, EventArgs.Empty);
    InitializingUserControlData?.Invoke(this, EventArgs.Empty);
}

User Control constructor and Initializing function

    // Initialize user control with IDetailScreenView. Subscribe to necessary events.
    public DetailScreenUserControl(IDetailScreenView view)
    {
        InitializeComponent();
        _view = view;
        _view.InitializingUserControl += InitializeUserControl;
    }

    // Initializes the user control for the detail screen.
    public void InitializeUserControl(object sender, EventArgs e)
    {
        List<string> qStandards = _view.SelectedQuestionStandards;
        Controls.Clear();
        maturityInput.Clear();
        complianceInput.Clear();

        int inputSeparation = 115;
        int secondInputX = 35;
        int inputHeight = 20;
        int labelWidth = 200;
        int inputWidth = 170;

        for (int  i = 0; i < qStandards.Count; i++)
        {
            Panel inputPanel = new Panel();
            inputPanel.Location = new Point(0, i * inputSeparation);
            inputPanel.AutoSize = true;
            inputPanel.BackColor = Color.AliceBlue;
            this.Controls.Add(inputPanel);

            Label qs_label = new Label();
            qs_label.Location = new Point(0, 0);
            qs_label.Font = new Font("Arial", 12F, FontStyle.Bold);
            qs_label.Size = new Size(labelWidth, inputHeight);
            qs_label.AutoSize = true;
            qs_label.Text = qStandards[i].ToString();
            inputPanel.Controls.Add(qs_label);

            Label m_label = new Label();
            m_label.Location = new Point(0, secondInputX);
            m_label.Font = new Font("Arial", 12F, FontStyle.Regular);
            m_label.Size = new Size(labelWidth, inputHeight);
            m_label.Text = "Maturity standard";
            inputPanel.Controls.Add(m_label);

            Label c_label = new Label();
            c_label.Location = new Point(0, secondInputX * 2);
            c_label.Font = new Font("Arial", 12F, FontStyle.Regular);
            c_label.Size = new Size(labelWidth, inputHeight);
            c_label.Text = "Compliance standard";
            inputPanel.Controls.Add(c_label);

            ComboBox m_input = new ComboBox();
            m_input.Location = new Point(labelWidth, secondInputX);
            m_input.Font = new Font("Arial", 10F, FontStyle.Regular);
            m_input.Size = new Size(inputWidth, inputHeight);
            m_input.DropDownStyle = ComboBoxStyle.DropDownList;
            maturityInput.Add(m_input);
            inputPanel.Controls.Add(m_input);

            ComboBox c_input = new ComboBox();
            c_input.Location = new Point(labelWidth, secondInputX * 2);
            c_input.Font = new Font("Arial", 10F, FontStyle.Regular);
            c_input.Size = new Size(inputWidth, inputHeight);
            c_input.DropDownStyle = ComboBoxStyle.DropDownList;
            complianceInput.Add(c_input);
            inputPanel.Controls.Add(c_input);

        }

        saveAssessmentButton.Location = new Point(195, qStandards.Count * inputSeparation);
        saveAssessmentButton.Size = new Size(130, 25);
        saveAssessmentButton.Text = "Save assessment";
        saveAssessmentButton.BackColor = SystemColors.ButtonHighlight;
        this.Controls.Add(saveAssessmentButton);

        _view.AddUserControl();
    }


Calculating revenue from roller coaster rides Problem description:

  The task is to calculate the amount of money earned from roller
  coaster rides on any given day.  There is a queue in front of the
  attraction.  Visitors might be alone or in groups. All members of
  the same group will want to ride together.  The ride begins once
  the roller coaster runs out of sufficient space for the next group.
   Once a ride is over, passengers go back to the end of the queue
  in the same order.
  Each passenger pays one dirham to ride the roller coaster once.
  The roller coaster can only operate a limited number of times each day.

Here is my code:

public static class RollerCoaster
{
    private static int CountDirhamsEarnedInOneOperation(int numAvailablePlaces, LinkedList<int> numPeopleInEachGroup)
    {
        //Each passenger pays one dirham to take the ride once.
        int dirhamsEarned = 0;
        int numGroupsInQueue = numPeopleInEachGroup.Count();

        while (numPeopleInEachGroup.First() <= numAvailablePlaces && numGroupsInQueue > 0)
        {
            dirhamsEarned += numPeopleInEachGroup.First();
            numAvailablePlaces -= numPeopleInEachGroup.First();
            numPeopleInEachGroup.AddLast(numPeopleInEachGroup.First());
            numPeopleInEachGroup.RemoveFirst();
            numGroupsInQueue--;
        }

        return dirhamsEarned;
    }

    public static long CalculateDirhamsEarned(int numAvailablePlaces, int numOperationsPerDay, LinkedList<int> numPeopleInEachGroup)
    {
        long dirhamsEarned = 0;

        while (numOperationsPerDay > 0)
        {
            dirhamsEarned += (long)CountDirhamsEarnedInOneOperation(numAvailablePlaces, numPeopleInEachGroup);
            numOperationsPerDay--;
        }

        return dirhamsEarned;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("Please enter:\nThe number of places available;\nThe number of times the attraction can function per day;\nThe number of groups in the queue.");
        string[] inputs = Console.ReadLine().Split(' ');

        int numAvailablePlaces = int.Parse(inputs[0]);
        int numOperationsPerDay = int.Parse(inputs[1]);
        int numGroupsInQueue = int.Parse(inputs[2]);
        LinkedList<int> numPeopleInEachGroup = new LinkedList<int>();

        Console.WriteLine("Please enter, line by line, the number of people in each group: ");
        for (int i = 0; i < numGroupsInQueue; i++)
        {
            int numPeopleInGroup = int.Parse(Console.ReadLine());
            numPeopleInEachGroup.AddLast(numPeopleInGroup);
        }

        long dirhamsEarned = RollerCoaster.CalculateDirhamsEarned(numAvailablePlaces, numOperationsPerDay, numPeopleInEachGroup);
        Console.WriteLine(dirhamsEarned.ToString());
    }
}

I'm a C# beginner, so I'd appreciate any kind of advice, though I am specifically looking for suggestions that help me improve the time-complexity of my algorithm. My program takes way too long to run when numOperationsPerDay is, say, 10,000,000.

One of the suggestions I would make is to improve your input handling. You don't handle invalid integers well at all.

string input = "invalid int";
int numAvailablePlaces = 0;

while (!int.TryParse(input, out numAvailablePlaces))
{
    Console.WriteLine("Please enter a valid integer for the number of places available.");
    input = Console.ReadLine();
}

And similarly for the other int's you grab. (You could also do them all in one loop.)

This method:

private static int CountDirhamsEarnedInOneOperation(int numAvailablePlaces, LinkedList<int> numPeopleInEachGroup)
{
    //Each passenger pays one dirham to take the ride once.
    int dirhamsEarned = 0;
    int numGroupsInQueue = numPeopleInEachGroup.Count();

    while (numPeopleInEachGroup.First() <= numAvailablePlaces && numGroupsInQueue > 0)
    {
        dirhamsEarned += numPeopleInEachGroup.First();
        numAvailablePlaces -= numPeopleInEachGroup.First();
        numPeopleInEachGroup.AddLast(numPeopleInEachGroup.First());
        numPeopleInEachGroup.RemoveFirst();
        numGroupsInQueue--;
    }

    return dirhamsEarned;
}

Does too much. Break the inside of that while loop to a new method.

Other than that, there's little to say in my opinion.

COMMENTS!!!
Making the Roller Coaster a static class with static functions means you can only have one in your park, so I wouldn't do that.
numPeopleInEachGroup.AddLast(numPeopleInEachGroup.First());  everybody gets back on the coaster after their ride?
While loops are generally less popular than for loops, you might want to see if you can use them instead.
Try preincremnting and decrementing rather than post i.e. ++aVariable rather than aVariable++.  The reason is once you start working with things other that ints it is going to be faster.


Proxy using socket, doubts on multithreading and connection closing I'm trying to make a simple proxy server in Python using the socket library, mostly to understand how it works.  I'm a noob both at programming and networking, so please be nice if my questions are totally dumb.

At the moment I've set up a proxy server which intercepts requests from the browser, prints them and sends back an "Hello" sample response. It seems to work, so next I'm going to complete it by adding a client which forwards the request to the web server, receives the response and sends it back to the browser.

However, I have two doubts about this first (seemingly working) part of the code:

import socket, threading
serv_port = 50007
server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server.bind(('', serv_port))
server.listen(5)
while True:
    #get conn to client
    conn, addr = server.accept()
    #span thread
     conn_thread = threading.Thread(target=cthread, args=(conn,))
    conn_thread.start()

 def cthread(conn):
    #set timeout
    conn.settimeout(1)
    #receive data until null data is received or socket times out
    req = b''
    while True:
        try:
              req_pack = conn.recv(4096)
            if not req_pack:
                break
            else:
                req += req_pack
        except socket.timeout:
                      break

   print req #print request to stdout

   #send a sample response
   conn.send(b'HTTP/1.1 200 OK\n\n
Hello</h1') #QUESTION 1

   conn.close() #QUESTION 2

My first question is about threading. Should I leave everything as it is, or should I, after receiving a request, span a different thread to deal with the response part?

Sample code of what I mean:

#in function cthread
print req
#span thread
resp_thread = threading.Thread(target=respthread, args=(conn, req))
resp_thread.start()

def respthread(conn, req):
    #do everything that's to be done to get response, send it to browser
    conn.send(b'HTTP/1.1 200 OK\n\n
Hello</h1') #sample response
    conn.close()

Another question: is it correct to close the connection to the browser (conn) after each response has been sent, or does it slow connections too much and it's possible to do without?

First off, you need to do some error catching with the socket functions. All of them can possibly fail, it's better to be safe and do some error catching.

Here is what I mean:

try:
    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.bind(('', serv_port))
    server.listen(5)
except socket.msg as error:
    print("Recieved error #%d: %s\n" % (error[0], error[1]))
    sys.exit(-1)

And, with socket.accept too:

try:
    conn, addr = server.accept()
except socket.error as error:
    print("Recieved error #%d: %s\n" % (error[0], error[1]))
    sys.exit(-1)

When there is an error with a socket call, a tuple is returned containing the error code (returned from the socket syscall) and an error message to go along with it.

I added a sys.exit to the code that will close the program with exit code -1, which usually means to external that there was an error while running the program. To use this, you will have to import sys.

In this part of a line

threading.Thread(target=cthread, args=(conn,))

I don't think there should be a comma after conn in the tuple for args.

According to the python docs on socket.settimeout,

  The value argument can be a nonnegative float expressing seconds, or
  None.

You aren't passing in a float value when you call settimeout.

Also, I believe that you should allow more time before a timeout. Reading in 4096 bytes of data might take more than 1 second.

Maybe 3 seconds would work.

Indentation isn't as strict in python 2 as it is in python 3, but you still want it to be perfect.

In your while loop of cthread, your indentation is messed up:

 def cthread(conn): # extra space
    #set timeout
    conn.settimeout(1)
    #receive data until null data is received or socket times out
    req = b''
    while True:
        try:
              req_pack = conn.recv(4096) # extra 2 spaces (1/2 tab)
            if not req_pack:
                break
            else:
                req += req_pack
        except socket.timeout:
                      break # extra 10 spaces (2 1/2 tabs)

   print req #print request to stdout # missing space

   #send a sample response
   conn.send(b'HTTP/1.1 200 OK\n\n<h1>Hello</h1') # missing space

   conn.close() # missing space

Either indent lines with 1 tab or 4 spaces.

Now for your questions.

I'm a little confused by this question. Right now in your code, when you recieve a connection, you do handle the recieving and the sending in a separate thread. This is fine, and is a good idea.
After you close a connection, there is no connection to slow down. And yes; this is fine. Since your server isn't going to do anything more after it has sent it's response, then there is no point in keeping the connection. It'll just bog your server down in the long-run.

You don't get real multithreading in CPython (see more here).

In your case it is mostly IO operations, so you can get good multithreading by using green threads. Something that is provided by Tulip (included in Python 3.4), or libraries like Twisted, eventlet, or gevent. Most of the libraries specified here will have an example of code similar to what you are trying to achieve.


Given two int values, return the one closer to 10 I did the exercise below to practice. Can someone help me to shorten or improve the code in a simple way for a beginner?

The exercise is:

  Given 2 int values, return whichever value is nearest to the value 10,
  or return 0 in the event of a tie.

public int Closer(int a, int b)
{
     Console.WriteLine(Closer(8, 13));    // output: 8
     Console.WriteLine(Closer(13, 8));    // output: 8
     Console.WriteLine(Closer(13, 7));    // output: 0
}

My solution:

namespace Closer
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine(Closer(13,15));    // output : 13
                Console.WriteLine(Closer(13, 13));   // output : 0
                Console.WriteLine(Closer(3,5));      // output : 5
                Console.WriteLine(Closer(13, 7));    // output : 0
                Console.WriteLine(Closer(-3, -5));   // output : -3
                Console.WriteLine(Closer(-3, -1));   // output : -1
                Console.ReadLine();
            }
            public static int Closer(int a, int b)
            {
                int calcA = a - 10;
                int calcB = b - 10;
                if (Math.Abs(calcA) == Math.Abs(calcB))
                {
                    return 0;
                }
                else if ((a >= 10 || b >= 10) && a < b )
                {
                    return a;
                }
                else if ((a >= 10 || b >= 10) && b < a)
                {
                    return b;
                }
                else if (calcB > calcA && Math.Abs(a)!= Math.Abs(b))
                {
                    return b;
                }
                else if ((calcA < 0 || calcB < 0) && (calcA > calcB && Math.Abs(a) != Math.Abs(b)))
                {
                    return a;
                }
                else return Closer(a,b);
            }
        }
    }

You have a lot of redundant code in here:

public static int Closer(int a, int b)
{
    int calcA = a - 10;
    int calcB = b - 10;
    if (Math.Abs(calcA) == Math.Abs(calcB))
    {
        return 0;
    }
    else if ((a >= 10 || b >= 10) && a < b )
    {
        return a;
    }
    else if ((a >= 10 || b >= 10) && b < a)
    {
        return b;
    }
    else if (calcB > calcA && Math.Abs(a)!= Math.Abs(b))
    {
        return b;
    }
    else if ((calcA < 0 || calcB < 0) && (calcA > calcB && Math.Abs(a) != Math.Abs(b)))
    {
        return a;
    }
    else return Closer(a,b);
}

First of all, you can figure everything out if you know the distance between the values of a, b, and 10.

int calcA = Math.Abs(a - 10);
int calcB = Math.Abs(b - 10);

You have principle in this section right, but it can be simplified a bit if you set calcA and calcB to use the absolute difference:

if (calcA == calcB)
{
    return 0;
}

Now, you just need to apply the same principle to the other values:

if (calcA < calcB)
{
    return a;
}

return b;    // we already established that the values are not the same, and that "a" is farther from 10 than "b"

Here is our new method:

public static int Closer(int a, int b)
{
    int calcA = Math.Abs(a - 10);
    int calcB = Math.Abs(b - 10);

    if (calcA == calcB)
    {
        return 0;
    }

    if (calcA < calcB)
    {
        return a;
    }

    return b;
}

But, 10 is a magic number in there, and magic numbers are never good.  Why don't you create a const value to store the number that you are checking the passed values against?

public static int Closer(int a, int b)
{
    const int compareValue = 10;
    int calcA = Math.Abs(a - compareValue);
    int calcB = Math.Abs(b - compareValue);

    if (calcA == calcB)
    {
        return 0;
    }

    if (calcA < calcB)
    {
        return a;
    }

    return b;
}

Now, you can change your method as much as you want, and you only have the magic number 10 in one place, so it is easy to change your method to compare the values against a different number.

Edit:

Thanks to Eric Lippert, I have fixed two bugs.  Eric found the bug that int.MinValue != int.MaxValue, so calling Math.Abs(int.MinValue) crashes.  If you pass a value that equals int.MinValue + compareValue, the program will crash.  While fixing this, I found another bug in which the wrong value will be returned if you call the function with two values that are less than int.MinValue + compareValue because they wrap around in the call value - compareValue.  Both of these bugs are now fixed for the compare value of 10, still working on a generic patch:

public static int Closer(int a, int b)
{
    const int compareValue = 10;

    while (a <= int.MinValue + compareValue || b <= int.MinValue + compareValue)
    {
        if (a <= int.MinValue + compareValue)
        {
            b = AdjustVal(b, compareValue);
            a++;
        }
        if (b <= int.MinValue + compareValue)
        {
            a = AdjustVal(a, compareValue);
            b++;
        }
    }

    int calcA = Math.Abs(a - compareValue);
    int calcB = Math.Abs(b - compareValue);

    if (calcA == calcB)
    {
        return 0;
    }

    if (calcA < calcB)
    {
        return a;
    }

    return b;
}

Edit 2:

Eric Lippert says we should do the arithmetic in longs. Of course, this doesn't work when we take input as long too.

public static int Closer(int a, int b)
{
    const int compareValue = 10;

    long calcA = Math.Abs((long)a - compareValue);
    long calcB = Math.Abs((long)b - compareValue);

    if (calcA == calcB)
    {
        return 0;
    }

    if (calcA < calcB)
    {
        return a;
    }

    return b;
}

Simpler for the machine:

public int CloserTo(int a, int b, ref bool tie_flag, int referencePoint = 10)
{
    // Quick away trivial solution
    if (a == b)
    {
        tie_flag = true;
        return 0;
    }
    // Init tie flag
    tie_flag = false;
    // Case 1: {a...b...referencePoint} or {b...a...referencePoint}
    if ((a <= referencePoint) && (b <= referencePoint))
        return (a < b)? b : a;
    // Case 2: {referencePoint...a...b} or {referencePoint...b...a}
    if ((a >= referencePoint) && (b >= referencePoint))
        return (a < b)? a : b;

    long diff1, diff2;
    // Case 3: {a...referencePoint...b}
    if (a < b)
    {
        diff1 = (long) referencePoint-a;
        diff2 = (long) b-referencePoint;
        if (diff1 == diff2)
        {
           tie_flag = true;
           return 0;
        }
        return (diff1 < diff2)? a : b;
    }
    // Case 4: {b...referencePoint...a}
    diff1 = (long) referencePoint-b;
    diff2 = (long) a-referencePoint;
    if (diff1 == diff2)
    {
        tie_flag = true;
        return 0;
    }
    return (diff1 < diff2)? b : a;
}

A bit longer, but it never fails, whatever int's you feed. But if 'a' or 'b' are zero, and that zero is the nearest one to the reference point, the return value is indistinguisable from a tie, so this is why the auxiliary tie flag.


Prime factorization in Haskell I am a Haskell beginner. Here is my function to find prime factors of a number

primes = 2:takePrimes [3, 5 ..]
    where takePrimes (x:xs) = let smallPrimes = untilRoot x primes
                              in  if 0 `notElem` (map (mod x) smallPrimes)
                                  then x:takePrimes xs
                                  else takePrimes xs

untilRoot n = takeWhile (\x -> x*x < n)

firstPrimeDivisor :: Integer -> Integer
firstPrimeDivisor x = head [p | p <- primes, x `mod` p == 0]

primeFactor 1 = []
primeFactor x = let p = firstPrimeDivisor x
                in p:primeFactor (x `div` p)

How does it look?

It looks fine, but there are a few issues with it:

When we check if a number is a prime, we need to test all possible divisors up its root inclusively. If you print the primes list, you'll see that 9 is there, which is obviously a bug. untilRoot n = takeWhile (\x -> x*x < n) should be untilRoot n = takeWhile (\x -> x*x <= n). However, this bug does not affect the correctness of your factorization algorithm.
It does not scale well. In the firstPrimeDivisor function, all primess up to x are checked in the worst case. That's why it works slowly even for moderately large prime numbers(for instance, 10^9 + 7).

Here a more efficient solution which checks only O(sqrt(n)) divisors in the worst case:

factorize :: Integer -> Integer -> [Integer]
factorize _ 1 = []
factorize d n
    | d * d > n = [n]
    | n `mod` d == 0 = d : factorize d (n `div` d)
    | otherwise = factorize (d + 1) n

primeFactors :: Integer -> [Integer]
primeFactors = factorize 2

It is also much more concise. The idea behind it is to prove two statements first and then write a very simple code based on them:

The smallest divisor of any natural number greater than two is a prime. Let's assume that it is not the case and d = p * q (p, q > 1), where d is the smallest divisor of n. But then p < d and p is a divisor of n. Thus, d is not the smallest one. This statement also shows why your original solution is correct, even though the primes list is contains some composite numbers.
Any composite number has a divisor that does not exceed its square root. The proof by contradiction is very straightforward so I will omit it.

Here's a Sieve of Eratosthenes implementation from a literate Haskell page:

primes :: [Integer]
primes    = [2, 3, 5] ++ (diff [7, 9 ..] nonprimes)
  where
    nonprimes :: [Integer]
    nonprimes = foldr1 f $ map g $ tail primes
        where
            f (x:xt) ys = x : (merge xt ys)
            g p         = [ n * p | n <- [p, p + 2 ..]]

    merge :: (Ord a) => [a] -> [a] -> [a]
    merge xs@(x:xt) ys@(y:yt) =
      case compare x y of
        LT -> x : (merge xt ys)
        EQ -> x : (merge xt yt)
        GT -> y : (merge xs yt)

    diff :: (Ord a) => [a] -> [a] -> [a]
    diff xs@(x:xt) ys@(y:yt) =
      case compare x y of
        LT -> x : (diff xt ys)
        EQ -> diff xt yt
        GT -> diff xs yt


MySQLi script to print the name of a user I made my first script of MySQLi. I have just learnt it from 3rd party website. So, I am not sure I am using functions which are not deprecated or outdated. I should start to practice good scripts to access databases. So, I have posted here. Any mistake you see, please point it out.

<?php

include "functions.php";

$a = checkLogin();

if($a==1) {
    $id = $_COOKIE['id'];

    include "databaseConnector.php";

    $query = $mysqli->query("SELECT * FROM users WHERE id = '$id'") or die($mysqli->error.__LINE__);

    if($query->num_rows > 0) {
        while($row = $query->fetch_assoc()) {
?>
            <?php echo stripslashes($row['firstname'])." ".stripslashes($row['lastname']); ?>
<?php
        }
    }
    else {
        return false;
    }
}
else {
    redirectIndex();
}

?>

You are vulnerable to SQL injection. Always use prepared statements with parameterized queries.

The below example fixes these issues. In this example I am using PDO instead, which is similar to mysqli but more powerful and supports other databases than just MySQL.

<?php

include "functions.php";

$a = checkLogin();

if ($a == 1) {
    $id = $_COOKIE['id'];

    // include "databaseConnector.php";
    // --------------------------------------------------------------------------------------------------
        try {
            $handle = new PDO("mysql:host=$host_addr;dbname=$database", $username, $password);
            $handle->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
        } catch(PDOException $e) {
            echo 'ERROR: ' . $e->getMessage();
        }
    // --------------------------------------------------------------------------------------------------

    // UNBOUND PARAMETERS VERSION
        $query = "SELECT * FROM users WHERE id = '$id'";
        $statement = $handle->prepare($query);
        $statement->execute();

    // BOUND PARAMETERS VERSION
        $query = "SELECT * FROM users WHERE id = :id";
        $statement = $handle->prepare($query);
        $params = array(":id" => $id);
        $statement->execute($params);

    $row_count = $statement->rowCount();
    $result    = $statement->fetchAll(PDO::FETCH_ASSOC);

    if($row_count > 0) {
        foreach ($result as $row => $col) {
            echo $col['firstname']." ".$col['lastname'];
        }
    } else {
        return false;
    }
} else {
    redirectIndex();
}

?>

mysqli is somewhat outdated, you should see PDO that is much better both with security and database support (12 drivers vs. 1).

You can see here details of mysqli vs. PDO: http://net.tutsplus.com/tutorials/php/pdo-vs-mysqli-which-should-you-use/


Mutually exclusive properties The question is probably quite simple, but I would like to hear what drawbacks we will have with our code.

So, we had a simple implementation and interface for it:

public interface ISettings
{
    bool IsOnline { get; set; }
}

public class Settings : ISettings
{
    public bool IsOnline { get; set; }
}

The property shows the application state and used in many conditions. The interface in our case is required for implementing settings for different platforms.

My colleague insists on implementing an additional property:

public interface ISettings
{
    bool IsOnline { get; set; }
    bool IsOffline { get; set; }
}

public class Settings : ISettings
{
    public bool IsOnline { get; set; }
    public bool IsOffline
    {
        get { return !IsOnline; }
        set { IsOnline = !value; }
    }
}

Is it a good practice to have such additional properties just for convenient code-reading?

Just a quick note: a Status (or ConnectionStatus) enum with ONLINE and OFFLINE values would be more readable here.

You could sort of do it with the MixIn pattern. It will be a method instead of a property, but hopefully that isn't the end of the world for you. Add this static class somewhere in the same namespace as your ISettings interface:

public static class ISettingsExt
{
    public static bool IsOffline(this ISettings obj)
    {
        return !obj.IsOnline;
    }

    public static void IsOffline(this ISettings obj, bool isOffline)
    {
        obj.IsOnline = !isOffline;
    }
}

Then, any class that implements the ISettings interface will be able to invert the logic of "IsOnline" without personally having to implement it.


Extracting all-caps variables from string expressions I'm extracting variables from user entered mathematical expressions, so that I can enter them into the expression evaluator exprtk. For now, the condition is given that variable names will be composed of consecutive capital letters. Any mathematical constants or function names will be lowercase. Some hypothetical inputs and expected outputs:

Input: "(A + B) - 2"
Expected Output: { A, B }

Input: "pow(AC,E) * ( E * F )"
Expected Output: { AC, E, F }

The code I have right now seems to work, but I would love a critique. I add a space to the end of the string to make my algorithm catch cases at the end of the string, which seems a bit hacky(?).

template<class T>
std::vector<std::string> MapEvaluator<T>::extractVariables(std::string expression) {

    expression = expression + " ";
    std::vector<std::string> variables = {};
    std::string substring;
    size_t consecutiveCharsCaps = 0;
    bool previousCharCaps = false;

    for (size_t i = 0; i < expression.length(); i++)
    {
        if (isCapital(expression[i]))
        {
            consecutiveCharsCaps++;
            previousCharCaps = true;
        }
        else {
            if(previousCharCaps) {
                substring = expression.substr(i - consecutiveCharsCaps, consecutiveCharsCaps);
                variables.push_back(substring);
                consecutiveCharsCaps = 0;
                previousCharCaps = false;
            }
        }
    }

    unique(variables);
    return variables;
}

template <class T>
void MapEvaluator<T>::unique(std::vector<std::string> &vec)
{
    auto end = vec.end();
    for (auto it = vec.begin(); it != end; ++it) {
        end = std::remove(it + 1, end, *it);
    }
    vec.erase(end, vec.end());
}

template<class T>
bool MapEvaluator<T>::isCapital(char c) {
    return (c >='A' && c <= 'Z');
}

Some observations:

It seems that std::adjacent_find essentially already does what you want, which is extracting all continuous sub-strings consisting of uppercase letters.
Removing duplicates from a vector might be fine, but you can also avoid this completely by inserting the found elements into a std::set. I suspect that the number of unique variables is always small, so this is a cleaner approach.
There is no reason for isCapital to be a member function. Instead, it should be a free function. Remember that interfaces should be complete but minimal. But in fact, there's no reason for the function in the first place: the standard already has std::isupper that we should rather use.

So with these in mind, we can re-write your function to e.g.,:

std::vector<std::string> get_variables(const std::string& str)
{
    std::set<std::string> vars;

    for (auto first = str.cbegin(); first != str.cend(); )
    {
        auto var_end = std::adjacent_find(first, str.cend(),
            [](char a, char b)
        {
            return std::isupper(static_cast<unsighed char>(a)) !=
                std::isupper(static_cast<unsigned char>(b));
        });

        if (var_end != str.cend())
        {
            ++var_end;
        }

        if (std::isupper(static_cast<unsigned char>(*first)))
        {
            vars.insert(std::string(first, var_end));
        }

        first = var_end;
    }

    return std::vector<std::string>(vars.cbegin(), vars.cend());
}

Notice that we've cast char to unsigned char before the call to std::isupper (thanks to Deduplicator for explaining this to me). The reason is that std::isupper takes an argument of type int which must be in the range of unsigned char (or special value EOF, -1). Unfortunately, a plain char has either the range of signed char or unsigned char, so we perform a cast to confer to this common convention of character classification functions.

In the ExprTk readme.txt there is a section called: Helpers & Utils

In the sub-section called collect_variables there is a description of a helper free function named exprtk::collect_variables, which can be used to extract a list of variables used in a given expression.

The following is an example usage of the exprtk::collect_variables function:

std::string expression = "X + abs(y / Z)";

std::vector<std::string> variable_list;

if (exprtk::collect_variables(expression, variable_list))
{
   for (const auto& var : variable_list)
   {
      ...
   }
}
else
  printf("An error occurred.");

If successful the variable_list should contain the variables names "X", "y" and "Z".


Python solution to Code Jam's 'Rounding Error' The "Rounding Error" problem of Round 1B of Google Code Jam 2018 is as follows:

  Problem

  To finally settle the age-old question of which programming language is the best, you are asking a total of N people to tell you their favorite language. This is an open-ended question: each person is free to name any language, and there are infinitely many languages in the world.

  Some people have already responded, and you have gathered this information as a list of counts. For example, 1 2 means that you have asked 3 people so far, and one picked a particular language, and the other two picked some other language.

  You plan to publish the results in a table listing each language and the percentage of people who picked it. You will round each percentage to the nearest integer, rounding up any percentage with a decimal part equal to or greater than 0.5. So, for example, 12.5% would round up to 13%, 99.5% would round up to 100%, and 12.4999% would round down to 12%.

  In surveys like this, sometimes the rounded percentages do not add up to exactly 100. After you are done surveying the remaining people, what is the largest value that the rounded percentages could possibly add up to?

  Input

  The first line of the input gives the number of test cases, T. T test cases follow; each consists of two lines. The first line consists of two integers N and L: the total number of people in the survey, and the total number of different languages represented among the people who have already responded. The second line consists of L integers Ci; the ith of these is the number of people who said that the ith of the represented languages was their favorite.

  Output

  For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the largest value that the percentages could possibly add up to, as described above.

  Limits

  1 ≤ T ≤ 100.
  1 ≤ L < N.
  1 ≤ Ci, for all i.
  The sum of all Ci values < N.
  Time limit: 10 seconds per test set.
  Memory limit: 1GB.

This is my Python solution.  However, I get the 'Time Limit Exceeded' result even for the smallest test case. How can I speed up this solution?

from functools import reduce

def main():
    def gen_sums(total, freq, remaining):
        """Generate percentages' sums"""
        if not remaining:
            yield reduce(lambda x, y: x + (y*100+total//2)//total, freq, 0)
        else:
            seen = set()

            for i in range(len(freq)):
                if not freq[i] in seen:
                    yield from gen_sums(total,
                                        freq[:i] + [freq[i]+1] + freq[i+1:],
                                        remaining-1)
                    seen.add(freq[i])

            yield from gen_sums(total, freq+[1], remaining-1)

    T = int(input())

    for i in range(1, T+1):
        total_people, num_languages = map(int, input().split())
        languages_frequency = [int(x) for x in input().split()]

        if not 100 % total_people:
            print('Case #{}: {}'.format(i, 100))
            continue

        not_responded = total_people - sum(languages_frequency)

        max_percentage = max(gen_sums(total_people, languages_frequency,
                                      not_responded))

        print('Case #{}: {}'.format(i, max_percentage))

main()

1. Review

It is hard to test this code because it gets its data from standard input.

This means that in order to test it or measure its performance you have to write the test case to a file and then run the code with standard input redirected from that file. It would be easier to test if the code were refactored so that the input-reading part of the code was in a separate function from the problem-solving part, like this:

from functools import reduce

def gen_sums(total, freq, remaining):
    """Generate percentages' sums"""
    if not remaining:
        yield reduce(lambda x, y: x + (y*100+total//2)//total, freq, 0)
    else:
        seen = set()
        for i in range(len(freq)):
            if not freq[i] in seen:
                yield from gen_sums(total,
                                    freq[:i] + [freq[i]+1] + freq[i+1:],
                                    remaining-1)
                seen.add(freq[i])
        yield from gen_sums(total, freq+[1], remaining-1)

def max_percentage(total_people, languages_frequency):
    if not 100 % total_people:
        return 100
    not_responded = total_people - sum(languages_frequency)
    return max(gen_sums(total_people, languages_frequency, not_responded))

def main():
    T = int(input())
    for i in range(1, T+1):
        total_people, num_languages = map(int, input().split())
        languages_frequency = [int(x) for x in input().split()]
        result = max_percentage(total_people, languages_frequency)
        print('Case #{}: {}'.format(i, result))

Now it's easy to test the code from the interactive interpreter or from a unit test, for example:

>>> max_percentage(11, [1, 2, 3, 4])
99

and easy to measure its performance:

>>> from timeit import timeit
>>> timeit(lambda:max_percentage(14, []), number=1)
8.237278351996792

2. Performance

As demonstrated above, the code in the post takes more than 8 seconds to figure out that when there are 14 voters (and no votes cast yet), the maximum rounded percentage is 101%.

Why does the code in the post take so long to solve this problem? Well, it's because it carries out a search over all possible assignments of votes. But if there are \$n\$ voters then there are of the order of $$\exp{\pi\sqrt {2n \over 3}}$$ possible assignments of votes (see the asymptotic formula for the partition numbers) and so the runtime is exponential in the number of votes.

But in fact the problem is easy to solve by hand with a little bit of mathematics. If there are 14 voters, then each vote is worth \${100 \over 14} = 7{1\over7}\$ percent, and so four votes are worth \$28{4\over7}\$ percent, which rounds up to 29. Fewer than four votes will round down, and more than four will be wasteful since the extra votes over four could be used to contribute to another block of four votes. So the maximum rounded percentage is found when we group as many of the votes as possible into blocks of four votes. In this case there are three such blocks, leaving two votes over, giving a rounded total of \$29·3 + 14 = 101\$.

Similar analysis shows that if there are 19 voters, then each voter contributes \${100\over19} = 5{5\over19}\$ percent, and so it is most efficient to put voters in pairs, because two votes contibute \$10{10\over19}\$ percent, which rounds up to 11. So we have nine pairs of votes and one left over, giving a rounded total of \$11·9 + 5 = 104\$. But it will be a very long time before max_percentage(19, []) returns the result.

So searching over all possible assignments of votes is not going to work even for moderately large problem sizes. Instead, you need to program the kind of mathematical analysis that I carried out in the examples above. I'm not going to spoil the problem for you by giving away my solution, but I'll just show one performance measurement:

>>> timeit(lambda:max_percentage2(14, []), number=1)
0.00011452200124040246

This is more than 70,000 times faster than the code in the post.

Obviously, if you don't save the path records, you've been, it's extremely time consuming. (Use DP)


Customizing color for the navbar of my Android app I got my navigation bar to be the color I want of Blue background with white text.

Here is my code which works but this feels totally hacky. Please suggest improvements
styles.xml
<resources>
    <style name="AppTheme" parent="@android:style/Theme.Holo.Light">
        <item name="android:actionBarStyle">@style/MyActionBar</item>
    </style>

    <!-- ActionBar styles -->
    <style name="MyActionBar" parent="@android:style/Widget.Holo.Light.ActionBar">
        <item name="android:background">#6a9abd</item>
        <item name="android:titleTextStyle">@style/TitleBarTextColor</item>
    </style>

    <style name="TitleBarTextColor" parent="@android:style/Widget.Holo.Light.ActionBar">
        <item name="android:textColor">#ffffff</item>
    </style>
</resources>

You could actually name (i.e. wrap in a proper resource) the color you used there, and thus reference it easier in the future. Not only that, but properly defining resources is recommended for Android development, and depending on the tools you use, you might see them complaining if you don't.

Inside

/res/values/colors.xml

you could define yours as

<?xml version="1.0" encoding="utf-8"?>
<resources>
    <color name="my_amazing_blue">#6a9abd</color>
</resources>

and then reference it as

@color/my_amazing_blue

in the XML, or

Resources res = getResources();
int myAmazingBlue = res.getColor(R.color.my_amazing_blue);

in your Java code.

Also note that for Android, resource names are usually cased_like_this.

After accepting an answer that discussed resources, I have modified my code to this
styles.xml
<resources>

    <!-- Base application theme. -->
    <style name="AppTheme" parent="Theme.Base.AppCompat.Light.DarkActionBar">
        <!-- Customize your theme here. -->
        <item name="android:actionBarStyle">@style/MyActionBar</item>
    </style>

    <!-- ActionBar styles -->
    <style name="MyActionBar"
        parent="@android:style/Widget.Holo.Light.ActionBar">
        <item name="android:background">@color/light_blue</item>
        <item name="android:titleTextStyle">@style/MyActionBarTitleText</item>
    </style>

    <!-- ActionBar title text -->
    <style name="MyActionBarTitleText"
        parent="@android:style/Widget.Holo.Light.ActionBar">
        <item name="android:textColor">@color/actionbar_text</item>
    </style>

</resources>

And then I created a file for colors
colors.xml
<?xml version="1.0" encoding="utf-8"?>
<resources>

    <color name="light_blue">#6a9abd</color>
    <color name="actionbar_text">#eff2f5</color>

</resources>


Handling access to database connection both inside and outside of classes Is this an OK way to handle access to database connection both inside and outside of classes?

I used to include a PHP file -- database.detl.php -- at the very top of my index.php file containing the following code:

try{
    $dbh_options = array(/*...*/);
    $dbh = new PDO('mysql:host=localhost;dbname='.db_name.';charset=utf8',db_user,db_user_pw,$dbh_options);
} catch(PDOException $e) {
    /*...*/
}

Now every document that got included by index.php could use $dbh to access my database. This made it quite easy to work with.

But despite including that file before any classes got loaded, this $dbh-variable was not available from inside the classes. This was not possible to do:

class KD_sql {
    public static function get_recipes(){
        $qry = $dbh->query('SELECT * FROM recipes');
        $get = $qry->fetchAll();
        return $get;
    }
}

new KD_sql();

$recipes = sql_query::get_recipes();

This resulted in a fatal error: Call to a member function query() on a non-object....

So I guess no variables outside of a class is ever available inside unless you somehow send it there as an additional parameter to the method.

Anyway:

This is how I rewrote the code in order to still be able to have the $dbh-variable available throughout the entire site - just like before, and also have the connection available inside my KD_sql-class - without creating the connection in multiple locations:

First I changed database.detl.php into this:

try{
    $_SITE_DATABASE_details = function(){  //  <  added a function that holds the connection details
        $dbh_options = array(/*...*/);
        $dbh = new PDO('mysql:host=localhost;dbname='.db_name.';charset=utf8',db_user,db_user_pw,$dbh_options);
        return $dbh;  //  <  return connection details
    };
    new KD_db($_SITE_DATABASE_details);  //  the details is sent to a new class
    $dbh = KD_db::con();  //  <  a method, in this new class, returns the connection in order to still have $dbh available
} catch(PDOException $e) {
    /*...*/
}

This might seem a bit wierd, but let me finish.
Here's the new KD_db-class:

class KD_db {
    protected static $con = null;
#   initiate and stores the connection to the $con-variable
    public function __construct(callable $db_details){
        if (self::$con===null){
            self::$con = call_user_func($db_details);
        }
    }
//
#   the method that returns the database connection.
    public static function con(){
        return self::$con;
    }
//
}

This class is basically just a parent class that other classes can extend to in order to have the database connection available as well.

Here is the rewritten KD_sql-class:

class KD_sql extends KD_db {
    public static function get_recipes(){
        $qry = self::$con->query('SELECT * FROM recipes');  //  uses the $con -variable from parent class
        $get = $qry->fetchAll();
        return $get;
    }
}

I can now easily create quick-queries inside my KD_sql-class and just do this:

$recipes = KD_sql::get_recipes();

which quickly returns an array of all the recipes. Or, if that doesn't cut it, I can write a more complex SQL query like this:

$recipes = $dbh->prepare('
    SELECT r.columns,
        ot.columns
    FROM recipes r
        JOIN other_table ot ON r.fk_other_table_pk = ot.id
    WHERE r.some_column = :value
');

But I do have some "bugs" with the returned resultset from the class. If I only use fetch(), instead of fetchAll(), I can't do a while()-loop like this:

$recipes = KD_sql::get_recipes();
while($recipes){
    echo $recipes['id'].' '.$recipes['name'].'<br>';
}

Nothing happens, beside it looks like the loop is never ending or something. That's why I'm using fetchAll() for now. Then uses foreach() because that works.

But besides that. I would really appreciate som feedback on my way of doing this. I'm not that good with classes, oop and such. So if I'm breaking any golden rules or something - please let me know.

Use the global keyword to make globals accessible from inside of methods and functions:

class KD_sql
{
    public static function get_recipes()
    {
        global $dbh; // *** ADD THIS ***

        $qry = $dbh->query('SELECT * FROM recipes');
        $get = $qry->fetchAll();
        return $get;
    }
}

http://www.php.net/manual/en/language.variables.scope.php

Should you use globals for this?  That is another topic completely.

I think you've over-complicated this and locked yourself into using inheritance (which you should avoid until you actually need it). I'm going to suggest you use a singleton, which others will incidentally say to avoid, however database connection access is a great place to use a singleton. Since you're just passing a raw PDO object around, we'll just use a static variable for this.

class DBH {
  public static function instance() {
    static $dbh = null;
    if (!$dbh) {
      $dbh = new PDO('...');
    }
    return $dbh;
  }
}

Now you can just call DBH::instance() from anywhere to get access to the database connection. This also has the benefit that it is a shared object and you don't create a connection for each part of the code that needs to use the database.


Search a unique list and search a larger list to set dictionary with keys of binary values I would like to search a list of unique values and create a dictionary with those unique values as keys, and a binary list for whether those values occur.

I have successfully solved this, but would like a more efficient solution. This solution performs a high amount of operations for a search list of size 1000, 10000, and 1000000.

This code is fully reproducible.

import numpy as np

# Create random array, len(10), of integers 1-5

array_to_search = np.array(np.random.randint(0,5,(1,10)))
array_to_search = array_to_search.flatten()

#array_to_search = [0 3 0 0 0 2 1 3 3 0]

# Extract each unique value from array_to_search

array_of_unique_values = np.unique(array_to_search)

# array_of_unique_values = [0 1 2 3]

# Create a dictionary of unique values
output = dict.fromkeys(array_of_unique_values)

# Declare lists as values to the dictionary

output = { k : [] for k in array_of_unique_values}

# For each value in unique values, search the larger list and set the dictionary
# value to a 1 if found, 0 if not found.

for i in array_of_unique_values:
    for j in array_to_search:
        if i == j:
            output[i].append(1)
        else:
            output[i].append(0)

output = {0: [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
          1: [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
          2: [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
          3: [0, 1, 0, 0, 0, 0, 0, 1, 1, 0]}

== with broadcasting is the most straightforward solution:

array_to_search = np.array(np.random.randint(0,5,(1,10))).ravel()
array_of_unique_values = np.unique(array_to_search)

# Creates the binary vectors
matches = array_of_unique_values[:, None] == array_to_search

# Converts to dict
output = dict(zip(array_of_unique_values, matches))

You can also set return_indices flag to True in np.unique and use these to create the table:

array_to_search = np.array(np.random.randint(0,5,(1,10))).ravel()
array_of_unique_values, indices = np.unique(array_to_search, return_inverse=True)
matches = np.zeros((array_of_unique_values.size, array_to_search.size), dtype=bool)
matches[indices, np.arange(array_to_search.size)] = True
output = dict(zip(array_of_unique_values, matches))

If you put it in a Pandas Series, then you can use get_dummies to get a DataFrame containing the data you want. If you want it as a dictionary of lists, then you can just convert it with output = {col:list(df[col]) for col in df.columns}