RadixSet - a growing-only radix/patricia tree I'm looking for a structure to store large amounts of strings (5k to 100k) and then test for existence of new strings against the previous inserted data, in the least possible amount of time (memory is mostly irrelevant). The structure would first be fully loaded at the program start, without any queries. After the building process, it would receive many many queries (about 200 million), then the program exists (no mid-execution destruction). Also, there are about 150-200 simultaneous independent structures in-memory.

Initially I though about a HashSet of string keys. This approach is amortized \$O(1)\$ with the data set size and \$O(K)\$ with the the query string size. However, the cost includes some collision handling and bucketing. I learned about Radix Trees, which perform the insert and query operations in the same time complexity as a hash set of strings, but with less overhead.

When I went to search the web for a good implementation, most implementations offer more functionality than needed, bringing some additional overhead. Some build the structure as a map instead of a set, or have operations like removing items and checking for prefixes, that are not needed at all and may incur some performance penalty on the two needed operations. Or worse, they do not deal with non-ASCII strings.

Since there are only two operations and the Radix Tree is not that complex, I thought I could roll it on my own. Even though I'm not proficient in C++, the project runs it (not to mention the performance needs).

Here is my current implementation:

#ifndef radixset_hpp
#define radixset_hpp

#include <string>

class radixset {
public:

   radixset() : isword(false), children(nullptr) { }

   ~radixset() {
      if (children != nullptr) {
         for(auto i = 0; i < 256; i++) {
            delete children[i];
         }
         delete children;
      }
   }

   void insert(std::string str) {
      radixset* node = this;
      for (unsigned char c : str) {
         if (node->children == nullptr) {
            node->children = new radixset*[256];
         }
         node->children[c] = new radixset;
         node = node->children[c];
      }
      node->isword = true;
   }

   bool contains(std::string str) {
      radixset* node = this;
      for (unsigned char c : str) {
         if (node == nullptr || node->children == nullptr) {
            return false;
         }
         node = node->children[c];
      }
      return node->isword;
   }

private:
   bool isword;
   radixset** children;
};

#endif

And a basic set of tests:

#include "radixset.hpp"
#include <cassert>

int main() {
   radixset r = radixset{};

   assert(!r.contains(""));
   assert(!r.contains("abc"));
   assert(!r.contains("def"));

   r.insert("abc");
   r.insert("def");
   r.insert("");

   assert(r.contains("abc"));
   assert(r.contains("def"));
   assert(r.contains(""));
   assert(!r.contains("ab"));
   assert(!r.contains("defg"));

   assert(!r.contains("áý"));
   r.insert("áý");
   assert(r.contains("áý"));
}

The assertions all work as intended. Although every critic is welcome, I'm mostly looking for 1) performance increase, 2) the pointers here are really ugly (radixset** children, really?), a less headache-y/more modern version would be nice.

If it matters, my make runs the line:

g++ -Wall -std=c++11 radixset.hpp test.cpp -o output/test`

I'm on a Linux/Debian 8 system. I haven't yet spent time choosing compiler flags, don't bother with that. Also, I know the documentation is missing.

Side question: is the contains operation thread-safe? Since it only reads (not writing) members I'm inclined to guess so, but I find the C++ world so confusing...

As Olzhas Zhumabek mentioned in the comments, the allocation and de-allocation is poorly done and cause undefined behavior, which will most likely cause a segmentation fault.

First, the allocation in the insert function: every time you insert, you're overwriting the previous node with the line node->children[c] = new radixset;, and it's a bug that your tests do not cover (happens in the case of inserting two words with the same prefix), so you haven't noticed it. Also, it would be better to allocate all the children upfront to avoid pointing to garbage; so, the insert function becomes:

void insert(std::string str) {
   radixset* node = this;
   for (unsigned char c : str) {
      if (node->children == nullptr) {
         node->children = new radixset*[256];
         for (auto i = 0; i < 256; i++) {
            node->children[i] = new radixset;
         }
      }
      node = node->children[c];
   }
   node->isword = true;
}

Then, the de-allocation. Whenever you allocate using new[] you must de-allocate using delete[], and not just delete. The allocations to the recursive radixset structure do not use the subscript allocation, so their delete also do not use the subscript.

~radixset() {
   if (children != nullptr) {
      for (auto i = 0; i < 256; i++) {
         delete children[i];
      }
      delete[] children;
   }
}

And don't forget to add the non-tested case to the test cases! (Note: I have changed the tests from cassert to GoogleTest).

TEST (RadixSetInsert, MatchingPrefixLongerFirst) {
   radixset r = radixset{};
   r.insert("abc");
   r.insert("ab");
   ASSERT_TRUE(r.contains("ab"));
   ASSERT_TRUE(r.contains("abc"));
}

TEST (RadixSetInsert, MatchingPrefixShorterFirst) {
   radixset r = radixset{};
   r.insert("ab");
   r.insert("abc");
   ASSERT_TRUE(r.contains("ab"));
   ASSERT_TRUE(r.contains("abc"));
}

Actually, the memory usage for sparse data sets is way too much in this implementation. To avoid allocating too much and still not pointing to garbage, point to nullptr and allocate as needed:

if (node->children == nullptr) {
    node->children = new radixset*[256];
    for (auto i = 0; i < 256; i++) {
        node->children[i] = nullptr;
    }
}
if (node->children[c] == nullptr) {
    node->children[c] = new radixset;
}

And check for nullptr properly when deleting the children members.


Sum of all multiples of 3 or 5 below 1000 (Project Euler #1 - typical) I'm learning LISP and am starting with Project Euler. I would love some initial feedback on my LISP code for this simple task.

I know it spits out the correct answer, but what I'm not sure about is if I'm using LISP the way it is intended (and the way to strive for in the future in order to achieve success with LISP).

(defun sum (L)
  "sum a list"
  (apply '+ L)
)

(defun range (max &key (min 0) (step 1))
  "range of numbers from min to max by jumps of step"
  (loop for n from min below max by step
    collect n)
)

; take a range that steps by 3's and a list that steps by 5's and take the union of them (union removes duplicates)
(setq answer (sum (union (range 1000 :step 3) (range 1000 :step 5))))
(print answer)

Minor

Paren placement

Hanging parens are an eyesore.

Global var

Use defvar instead of setq to create global variables.

Sharp-quote for functions

You should do (apply #'+ ...) instead of (apply '+ ...).

Unnecessary allocation

Since your range returns a fresh list, you can use nunion instead of union.

Major

Sum

Your sum function is broken - it will not work on long lists, see CALL-ARGUMENTS-LIMIT.

Here are better ways to do this:

(defun sum (list)
  (reduce #'+ list))

(defun sum (list)
  (loop for x in list sum x))

Performance

union is probably quadratic in your implementation, so you might want to consider another approach for larger values of 1000 :-)


Checking for certain values in a range of numbers Is there any chance to make this script run faster?The script goes through each number from a to b, and checks if it holds 1, if it holds 2, if it holds 3, if it holds 1 and 2, if it holds 1 and 3 and if it holds 1, 2 and 3. Then it saves all results.

unsigned long long a, b, f;

    a = 1;
    b = 100000000;
    int f1 = 0, f2 = 0, f3 = 0, x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0, x6 = 0, x7 = 0;
    for(int i = a; i <= b; i++) {
            f = i;
            while(f / 10 != 0) {
                if(f % 10 == 1) {
                    f1++;
                }
                if(f % 10 == 2) {
                    f2++;
                }
                if(f % 10 == 3) {
                    f3++;
                }
                f = f / 10;
            }
            if(f1 == 0) {
                if(f % 10 == 1) {
                    f1++;
                }
            }
            if(f2 == 0) {
                if(f % 10 == 2) {
                    f2++;
                }
            }
            if(f3 == 0) {
                if(f % 10 == 3) {
                    f3++;
                }
            }
            if(f1 > 0) {
                x1++;
            }
            if(f2 > 0) {
                x2++;
            }
            if(f3 > 0) {
                x3++;
            }
            if(f1 > 0 && f2 > 0) {
                x4++;
            }
            if(f1 > 0 && f3 > 0) {
                x5++;
            }
            if(f2 > 0 && f3 > 0) {
                x6++;
            }
            if(f1 > 0 && f2 > 0 && f3 > 0) {
                x7++;
            }
            f1 = 0;
            f2 = 0;
            f3 = 0;
        }

First, I would tell you to restructure the while into a do-while. This will allow you to run at least one iteration of your loop (for one-digit numbers), THEN see if you need to repeat. That will in turn allow you to avoid the additional double-checks to make sure you weren't ignoring one-digit numbers (which are currently performed unnecessarily on any number > 10 that honestly doesn't have a 1, 2, or 3 in it).

Other than that, I would suggest you break early. Use booleans instead of ints: once you know you have a 1, 2, or 3, don't keep checking digits for those values (meaning if you have all three you can exit the loop entirely; for 1000000000000000123, you're done looping through the divide/modulo loop after checking just the first three digits).

Lastly, you're making checks you already know are false. You're first checking if f1 > 0, then regardless of that result you're checking if f1 and f2 are > 0. Instead, try nesting ifs; once you know f1 > 0 you can check if f2 is also > 0, while if f1==0 you don't have to check if f1 > 0 and f2 > 0 because you already know it can't be true. Similarly, if any digit of f is 1, then the same digit cannot be 2 or 3, so as soon as you know what a digit is, continue to the next digit.

Try this (you may have to define bool; older C++ specs do not have it built-in):

unsigned long long a, b, f;

a = 1;
b = 100000000;
bool[] z = new bool[3];
int[] x = new int[7];
for(int i = a; i <= b; i++) {
        f = i;
        do{
            var c = f % 10;
            // test the most likely thing first; most digits are NOT 1-3
            if(c > 3 || c==0) { }
            //once you know the value (or know the value exists), stop testing
            else if(!z[0] && c == 1) {
                z[0] = true;
            }
            else if(!z[1] && c == 2) {
                z[1] = true;
            }
            else if(!z[2] && c == 3) {
                z[2] = true;
            }

            //this MAY be faster depending on proc architecture and compiler;
            //some CPUs have "arithmetic-in-place" instructions.
            f /= 10;
        } while(f != 0 && !(!z[0] && !z[1] && !z[2]));

        if(z[0]) {
            x[0]++;
            if(z[1]) { //1&2
               x[3]++;
               if(z[2]) //1&2&3
                  x[6]++;
            }
            else if(z[2]) x[4]++; //1&3
        }
        if(z[1]) {
            x[1]++;
            //we have already checked 1&2 and 1&2&3
            if(z[2]) x[5]++; //2&3
        }
        if(z[2] > 0) {
            x[2]++;
            //we have already checked 1&3, 2&3 & 1&2&3
        }

        //this is for conciseness and may not work depending on your C++ spec
        z[0] = z[1] = z[2] = false;
    }


Calculate all the prime numbers between two given numbers I've made an application that calculates all the prime numbers between two given numbers and prints then into a .txt document... anything I can improve?
use std::io;
use std::fs::{OpenOptions};
use std::io::{Write, BufWriter};

fn main() {

    loop{

        let mut format = 1;

        let mut input = String::new();
        println!("Say a start for the prime loop! ");

        io::stdin().read_line(&mut input).unwrap();
        let start: u128 = input.trim().parse().unwrap();

        let mut input = String::new();
        println!("Say an end for the prime loop! ");

        io::stdin().read_line(&mut input).unwrap();
        let end: u128 = input.trim().parse().unwrap();

        let path = "path/to/file.txt";

        let f = OpenOptions::new()
            .write(true)
            .open(path)
            .expect("Could not open file");

        let mut f = BufWriter::new(f);

        for i in start..end{
            if prime(i) == true{
                f.write_all(i.to_string().as_bytes()).expect("unable to write to file");
                f.write_all(b"\t").expect("unable to write to file");
                format += 1;
            }

            if format == 10{
                f.write_all(b"\n").expect("unable to write to file");
                format = 0;
            }

        }
    }
}

fn prime(x: u128) -> bool {

    if x == 4 || x == 6 || x == 8 || x == 9{ //The loop doesnt quite work for numbers below 10 so this is for those numbers
        return false;
    }
    for i in 2..((x as f64).sqrt() as u128){
        if x % i == 0 { return false; }  //modulo to see if the number is dividable by variable i
    }
    true
}
```

The efficiency of the prime function is probably the most interesting aspect of this exercise. You're limiting the search space to up to the square root of the number, which is good, but the fact that you're looking for all primes in a range would make many other prime searching algorithms usable, such as the Sieve of Eratosthenes, which fairly efficiently gets you the primes from 2 through N. The issue is that which algorithm to use in your case depends on runtime inputs: if the user asks for prime numbers between 2 and a large N there are heaps of efficient algorithms. If they instead ask for primes between a large N and N+1 it probably makes much more sense to just look at those two numbers. I'm not a mathematician, but choosing which algorithm to use depending on the range seems like a subject worth studying.
I don't see why the algorithm would not work for numbers 4, 6, 8 and 9 - that seems like either a subtle bug in the loop or just a misunderstanding. I would add some test cases to prime and verify it with lots of different inputs.
prime takes a u128, but then drops precision when converting it to f64 before taking the square root. Since Integer -> Float -> Integer conversion can succeed while changing what the value is, I suspect there are corner cases where the range is miscalculated. See also this discussion.


Select comparison function for sorting based on type information So I'm working on a patch for the python interpreter where you go through the list and look at the types of the elements and try to use optimized special-case comparison functions that are much cheaper than the default comparison function. This is the code that goes through and checks the list elements and then assigns the comparison function. I put a lot of thought into the design, refactoring it many times; I really want this to be readable. Is it? How can I improve the form of this? I'm not looking for performance fixes, this just executes once per sort so performance isn't a big deal... I'm looking more for style/refactoring feedback.

/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = (lo.keys[0]->ob_type == &PyTuple_Type &&
                          Py_SIZE(lo.keys[0]) > 0);

PyTypeObject* key_type = (keys_are_in_tuples ?
                          PyTuple_GET_ITEM(lo.keys[0],0)->ob_type :
                          lo.keys[0]->ob_type);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples &&
      (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  PyObject* key = (keys_are_in_tuples ?
                   PyTuple_GET_ITEM(lo.keys[i],0) :
                   lo.keys[i]);

  if (key->ob_type != key_type) {
      keys_are_all_same_type = 0;
      break;
  }

  else if (key_type == &PyLong_Type && ints_are_bounded &&
             Py_ABS(Py_SIZE(key)) > 1)
    ints_are_bounded = 0;

  else if (key_type == &PyUnicode_Type && strings_are_latin &&
             PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND)
    strings_are_latin = 0;
}

/* Set compare_function appropriately based on values of the above bools */
if (keys_are_all_same_type) {

  if (key_type == &PyUnicode_Type && strings_are_latin)
    compare_function = unsafe_unicode_compare;

  else if (key_type == &PyLong_Type && ints_are_bounded)
    compare_function = unsafe_long_compare;

  else if (key_type == &PyFloat_Type)
    compare_function = unsafe_float_compare;

  else if ((richcompare_function = key_type->tp_richcompare) != NULL)
    compare_function = unsafe_object_compare;

} else {
  compare_function = safe_object_compare;
}

if (keys_are_in_tuples) {
  tuple_elem_compare = compare_function;
  compare_function = unsafe_tuple_compare;
}
/* End of type-checking stuff! */

Bug
I don't know anything about the python interpreter, but this if statement:

if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[0]) == 0)){

should be:
if (keys_are_in_tuples &&
    (lo.keys[i]->ob_type != &PyTuple_Type || Py_SIZE(lo.keys[i]) == 0)){

where keys[0] was changed to keys[i] in the size check.  Otherwise the size check will always be false, since Py_SIZE(lo.keys[0]) was already determined to be nonzero if keys_are_in_tuples is true.
Suggestion for simplification
If you created static inline functions like these:
static inline bool key_is_in_tuple(PyObject *obj)
{
    return obj->ob_type == &PyTuple_Type && Py_SIZE(obj) > 0;
}

static inline PyTypeObject *get_key_type(PyObject *obj)
{
    return key_is_in_tuple(obj) ?
               PyTuple_GET_ITEM(obj,0)->ob_type :
               obj->ob_type);
}

Then your code would read easier:
/* Turn off type checking if all keys are same type,
 * by replacing PyObject_RichCompare with lo.keys[0]->ob_type->tp_richcompare,
 * and possibly also use optimized comparison functions if keys are strings or ints.
 */
/* Get information about the first element of the list */
int keys_are_in_tuples = key_is_in_tuple(lo.keys[0]);

PyTypeObject* key_type = get_key_type(lo.keys[0]);

int keys_are_all_same_type = 1;
int strings_are_latin = 1;
int ints_are_bounded = 1;

/* Test that the above bools hold for the entire list */
for (i=0; i< saved_ob_size; i++) {

  if (keys_are_in_tuples && !key_is_in_tuple(lo.keys[i]) {
    keys_are_in_tuples = 0;
    keys_are_all_same_type = 0;
    break;
  }

  if (get_key_type(lo.keys[i]) != key_type) {
      keys_are_all_same_type = 0;
      break;
  }
  // ...


Add multiple instances of a property to a list I'm a novice programmer asking first question here although I've gotten tons of help from previous questions.
The following code is abstracted from what I currently have working.

List<decimal> teamAverage1 = new List<decimal>();
List<decimal> teamAverage2 = new List<decimal>();
List<decimal> teamAverage3 = new List<decimal>();

foreach (int id in TeamIds)
{
    foreach (Player player in Players.Where(p => p.teamId == id && p.a == 'x'))
    {
        teamAverage1.Add(player.Average1);
    }
    foreach (Player player in Players.Where(p => p.teamId == id && p.b == 'y'))
    {
        teamAverage2.Add(player.Average2);
    }
    foreach (Player player in Players.Where(p => p.teamId == id && p.c == 'z'))
    {
        teamAverage3.Add(player.Average3);
    }
}

Is there a way to get rid of the nested foreach loop and do something like:

foreach (int id in TeamIds)
{
    List<decimal> teamAverage1 = Players.Where(p => p.teamId == id && p.a == 'x').Average1
    List<decimal> teamAverage2 = Players.Where(p => p.teamId == id && p.b == 'y').Average2
    List<decimal> teamAverage3 = Players.Where(p => p.teamId == id && p.c == 'z').Average3
}

Is there a way to do this and if there is - is it a better solution than the original code?  I have a long list of properties to average and this would be much cleaner than many foreach loops.

More info: TeamIds identify each team.  Each player has teamId to relate it to a team.  Code should iterate every team id, find different subsets of players that belong to that team and add the stats of those players to lists for the team.  Thank you for your help, let me know if still not clear or if I have something wrong.

The linq statements can and will return more than one record.

You can shorten the first part to 3x this:

var teamAverage1 = Players
    .Where(p => p.teamId == id && p.a == 'x')
    .Select(x => x.Average1)
    .ToList();

I don't like the p.a properties. They look like a bad design. But it's hard to say more from the snippet you've showed.


Get nested type name without namespace Suppose I have a nested class structure like this:

namespace My.Namespace {
    public class Foo {
        public class Bar {
            public class Baz {
                public string Test { get; set; }
            }
        }
    }
}

I need to get the nested type name of Baz without the namespace, i.e. Foo+Bar+Baz in a generic method. Unfortunately, .Name will just return Baz and .FullName will give me the namespace as well. Right now I'm using this:

protected T LoadSample<T>(string fileName)
{
    var t = typeof(T);
    var nestedTypeName = t.Namespace == null
        ? t.FullName                                 // T is declared outside of a namespace
        : t.FullName.Substring(t.Namespace.Length + 1);
    ...
}

But this just looks ugly. Is there a more standard method for getting just Foo+Bar+Baz in this situation?

To clarify what's going on inside this method, this is part of a unit test for an XML serialization class. LoadSample will load an XML file, wrap it in a little more XML to create an 'envelope', attempt to parse it, and return the result if it succeeds. The problem is that the 'envelope' that the XML serialization class expects the XML to specify the type name in a particular format. For example:

<baz>
    <test>Testing</test>
</baz>

Will be wrapped in an evelope like this:

<evelope>
    <messageType>urn:My.Namespace:Foo+Bar+Baz</messageType>
    <message>
        <test>Testing</test>
    </message>
</evelope>

Well, one brute force way of doing it is to recurse over the type's DeclaringType property:

public static string TypeName (Type type)
{
   if(type.DeclaringType == null)
      return type.Name;

   return TypeName(type.DeclaringType) + "." + type.Name;
}

Running the following program:

static void Main(string[] args)
{
   var type = typeof(My.Namespace.Foo.Bar.Baz);
   var name = TypeName(type);
}

returns the name Foo.Bar.Baz as you would expect.


Convert number from one radix to another I am relatively new to coding and could use some help figuring out how I could improve my coding technique and habits. Here's an example of a working Java program I wrote that converts a number of some radix (from 2 to 36) to another radix (from 2 to 36).

Any tips or criticisms?

class RadixConverter {
    // command line arguments: (number) (radix of number) (radix to be converted to)
    public static void main(String[] args) {
        String n = args[0];                                   // n kept as String to support alphabetic representations of numerals for larger radixes
        int startRadix = Integer.parseInt(args[1]);
        int endRadix = Integer.parseInt(args[2]);
        int decimal = convertToDecimal(n, startRadix);
        String result = convertToBase(decimal, endRadix);
        System.out.printf("%s (%d) = %s (%d)%n", n, startRadix, result, endRadix);
    }

    public static int convertToDecimal(String n, int startRadix) {
        int sum = 0;
        for (int i = 0; i < n.length(); i++) {                                                 // begins at first digit and ends at last digit
            char digit = n.charAt(i);
            int placeValue = (int) Math.pow(startRadix, n.length() - i - 1);                   // place value of digit's column
            if ((digit >= 48) && (digit <= 57) && (digit - 48 < startRadix)) {                 // if digit is numerical and is within specified radix
                sum += (digit - 48) * placeValue;
            } else if ((digit >= 65) && (digit <= 90) && (digit - 65 + 10 < startRadix)) {     // if digit is alphabetic and within specified radix
                sum += (digit - 55) * placeValue;
            } else {
                throw new IllegalArgumentException("\n\nThe input number is invalid or contains digits outside of its specified radix.\n");
            }
        }
        return sum;
    }

    public static String convertToBase(int decimal, int endRadix) {
        StringBuilder sb = new StringBuilder("");
        do {
            int rem = decimal % endRadix;
            if ((rem <= 9) && (endRadix <= 36) && (endRadix >= 2)) {
                sb.append(Integer.toString(rem));
            } else if ((rem <= 35) && (endRadix <= 36) && (endRadix >= 2)) {
                sb.append((char) (rem + 55));
            } else {
                throw new IllegalArgumentException("\n\nThe output radix must be from 2 to 36.\n");
            }
            decimal /= endRadix;
        } while (decimal != 0);
        return reverseOrder(sb.toString());
    }

    public static String reverseOrder(String s) {
        StringBuilder sb = new StringBuilder("");
        for (int i = s.length() - 1; i >= 0; i--) {    // executes each character in reverse order
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

You're re-inventing the wheel. In the Integer class, there are methods for converting numbers to and from Strings with a radix parameter. So the following class does the job:

package test;

public class Test {

    public static void main(String[] args) {
        int inRadix = Integer.parseInt(args[1]);
        int outRadix = Integer.parseInt(args[2]);
        int value = Integer.parseInt(args[0], inRadix);
        String result = Integer.toString(value, outRadix);
        System.out.printf("%s (%d) = %s (%d)%n", value, inRadix, result, outRadix);
    }
}

But let's for a moment suppose the methods weren't there and look at your solution.

First, the method name convertToDecimal shows a (quite common, I have to say) mis-understanding. An int is internally represented in binary (radix 2), not decimal (radix 10). So convertToInt would be a better name.

I'd extract the character-versus-digit-value logic into methods int digitValueOf(char ch) and char digitCharFor(int digit) (By the way, the Character class has these methods).

I'd replace the numbers like 48 by the characters they represent (e.g. '0'). Not every reader knows the Unicode table by heart.

I'd replace the Math.pow() by consecutive integer multiplication. Turn the loop the other way round, starting from the last digit with placeValue = 1. In every iteration, multiply placeValue by radix. Math.pow() is slower and less exact than integer arithmetic.

I'd get into the habit of adding Javadoc even to trivial methods. After a year or so, you'll be happy.

Personally, I'm lazy with comments inside methods. A good method name, a Javadoc explaining what the method does (not how), and a straightforward implementation within the method are typically enough for a reader to understand what's going on.

Good is the usage of StringBuilder instead of concatenating Strings (quite common performance killer).

Good is throwing an exception in case of illegal characters.

Good is following the standard Java naming conventions.


Haskell's intersperse in D I am learning D. I'm trying to implement Haskell's intersperse in D.  I want to use ranges. I feel that the intermediate "interspersed" value is wrong. Additionally, I suspect the concatenation character by character is inefficient. What is a more idiomatic way to implement this function, please?
string translateToSwedish(immutable string english) pure
{
    string interspersed;
    foreach(char c; english)
        interspersed = interspersed ~ c ~ 'f';
    return interspersed;
}

void main()
{
    assert(translateToSwedish("Hello") == "Hfeflflfof");
}

My initial thought was to try std.range.roundRobin with repeat:
string translateToSwedish(immutable string english) pure
{
    import std.range;
    return roundRobin("f".repeat(), english);
}

This however is wrong for at least two reasons:

roundRobin is eager and will evaluate the full range even if another range finishes first. Repeat constructs an infinite range, thus my translateToSwedish function is also infinite.

This code doesn't typecheck:

main.d(6): Error: cannot implicitly convert expression (roundRobin(repeat("f"), english)) of type Result to string

Its unfortunate that roundRobin doesn't work here, as it sounds just right for the task. Some functions (e.g. std.range.zip) have a StoppingStrategy that allows you to determine whether to stop at the shortest or longest range, and I'm not sure why roundRobin doesn't support this.

As @sigod pointed out, the issue with roundRobin was just a simple typo (I missed it too!).
It is probably the best option, but I'll leave my alternative anyways:

import std.range, std.algorithm;

auto translateToSwedish(immutable string english) pure
{
    return english.map!(c => only(c, 'f')).joiner;
}

void main()
{
    assert(translateToSwedish("Hello").equal("Hfeflflfof"));
}

map replaces each character c with the sequence c'f'.
joiner links these pairs of character into a single range.

Note the use of the auto return type. Returning a string would imply eagerly committing the result within translateToSwedish. However, we don't know what the user of translateToSwedish will do with the result; if they are just passing it to another range-manipulating-function, they'd much rather we give them a range.

You'll notice many D functions are written like this. You generally want to keep passing around ranges until it is absolutely necessary to evaluate the result.

With that in mind, lets allow translateToSwedish to operate on a range as well:

import std.traits, std.range, std.algorithm;

auto translateToSwedish(R)(R english) pure if (isSomeString!R)
{
    return english.map!(c => only(c, 'f')).joiner;
}

void main()
{
    assert(translateToSwedish("Hello").equal("Hfeflflfof"));
}

Now translateToSwedish is well equipped to be used in a lazily evaluated function chain:

auto result = "Hello"
    .translateToSwedish
    .translateToGerman
    .translateToPigLatin
    // and so on


How to find the next sequence of integers? I was thinking of the following problem: List all sequences \$ a_1, a_2, a_3, a_4, a_5, a_6, a_7 \$ of positive integers where \$ 1 \le a_1 < a_2 < \ldots < a_7 \le 39 \$. For any sequence with this property, my code computes the next sequence in lexicographic order. Starting with the initial sequence \$ [1,2,3,4,5,6,7] \$, calling next_row(a) repeatedly  produces all such sequences.
Is there more elegant way to code the function that returns the next row than this?
def next_row(a):
    if a[-1]<39:
             a[-1]+=1
             return a
    elif a[-2]<38:
            a[-2]+=1
            a[-1]=a[-2]+1
            return a
    elif a[-3]<38:
            a[-3]+=1
            a[-2]=a[-3]+1
            a[-1]=a[-2]+1
            return a
    elif a[-4]<37:
            a[-4]+=1
            a[-3]=a[-4]+1
            a[-2]=a[-3]+1
            a[-1]=a[-2]+1
            return a
    elif a[-5]<36:
            a[-5]+=1
            a[-4]=a[-5]+1
            a[-3]=a[-4]+1
            a[-2]=a[-3]+1
            a[-1]=a[-2]+1
            return a
    elif a[-6]<35:
            a[-6]+=1
            a[-5]=a[-6]+1
            a[-4]=a[-5]+1
            a[-3]=a[-4]+1
            a[-2]=a[-3]+1
            a[-1]=a[-2]+1
            return a
    elif a[-7]<34:
            a[-7]+=1
            a[-6]=a[-7]+1
            a[-5]=a[-6]+1
            a[-4]=a[-5]+1
            a[-3]=a[-4]+1
            a[-2]=a[-3]+1
            a[-1]=a[-2]+1
            return a

There is a lot of repetition in your code, which makes it unnecessarily long, difficult to read, difficult to maintain, and error-prone. And in fact you have an apparent copy-paste error, can you spot it?
if a[-1]<39:
    ...
elif a[-2]<38:
    ...
elif a[-3]<38:
    ...
elif a[-4]<37:
    ...

The outer if/elif chain is to find the rightmost position in the list which can be increased, and that can be done with a loop:
for i in range(len(a)):
    if a[-1-i] < 39 - i:
       ...

The inner repeated assignments can be replaced by a loop as well. Then your function would look like this:
def next_row(a):
    for i in range(len(a)):
        if a[-1-i] < 39 - i:
            a[-1-i] += 1
            for j in range(0, i):
                a[-1-j] = a[-1-i] + i - j
            return a

Here i and j are positions from the end of the array as in your code, other choices are possible.
The new function is shorter, more general (it works with lists of arbitrary lists, not only lists of length 7), and can easily be generalized to arbitrary upper bounds (just replace the constant 39 by a function parameter).
If the intention is to enumerate all 7-element subsets of the first 39 integers then you can also use existing functions from the itertools module, in this case itertools.combinations():
import itertools

rows = itertools.combinations(range(1, 40), 7)

This creates an iterator which you can access one-by-one:
next_row = next(rows)
print(next_row)
# (1, 2, 3, 4, 5, 6, 7)

next_row = next(rows)
print(next_row)
# (1, 2, 3, 4, 5, 6, 8)

...

or enumerate:
for row in rows:
    print(row)

As a general remark, I suggest to check your code against the PEP8 coding style, for example at PEP8 online. It will report mainly missing whitespace around operators, and wrong indentation.


Summing up students by the topics they studied and the marks they got I wrote scripts that sums up the students and their grades. It uses four csv files.

students
marks
tests
courses

.

# main
import pandas
from statistics import mean

if __name__ == "__main__":
    students_df = pandas.read_csv("students.csv")
    marks_df = pandas.read_csv("marks.csv")
    tests_df = pandas.read_csv("tests.csv")
    courses_df = pandas.read_csv("courses.csv")

    marks_tests = pandas.merge(marks_df, tests_df, left_on="test_id", right_on="id")
    student_courses = marks_tests.groupby(by="student_id")['course_id'].apply(set)

    students_dict = students_df.set_index("id").to_dict(orient="index")
    courses_dict = courses_df.set_index("id").to_dict(orient="index")

    for student_id, course_ids in student_courses.iteritems():
        print("Student id: {}, name: {name}".format(student_id, **students_dict[student_id]))
        final_grades = []
        for course_id in course_ids:
            marks = marks_tests.loc[(marks_tests['course_id'] == course_id) & (marks_tests['student_id'] == student_id)]
            final_grades.append(sum(marks['mark']*(marks['weight']/100.0)))

        print("Total Average: {:.2f}%".format(mean(final_grades)))
        for course_id in course_ids:
            print("  Course: {name}, Teacher: {teacher}".format(**courses_dict[course_id]))
            marks = marks_tests.loc[(marks_tests['course_id'] == course_id) & (marks_tests['student_id'] == student_id)]
            final_grade = sum(marks['mark']*(marks['weight']/100.0))
            print("  Final Grade: {:.2f}%".format(final_grade))

It works very well but I don't know if it is optimized. For instance I have two loops that do almost the same thing : the first one to get the total Average which is mean of the final grades for each topic and the second one to get the final grade for each topics.

Furthermore it would have been better if I added some testing to it such has

if the sum of the weights of the tests a student has taken in a topic are equal to 0 (the student took every tests)
or go over 100.

The main part of programming is writing code so that it makes sense to others, and the biggest part of that is slicing your code into functions (Single Responsibility) which do only one thing.
If I was changing your code, the first thing I would do is move everything under your entry point (if __name__... - good BTW, always have an entry point) into functions, and have the main communicate what the code is doing. For instance:

if __name__ == "__main__":
    load_student_files_into_data_frames()
    merge_test_marks()
    group_students()
    print_students_and_course_results()

Now I understand the purpose of your code without having to look for a README.txt or spending 5-10 minutes reading or stepping through your code. This is also a good technique for understanding program flow before you actually write code inside the functions (and lends itself to TDD, but that's another topic for another day).

Of course, doing that with your code as it currently is, breaks all operations.
Even if we update the load process to return each data frame, it starts to look messy:

def load_student_files_into_data_frames():
    students_df = pandas.read_csv("students.csv")
    marks_df = pandas.read_csv("marks.csv")
    tests_df = pandas.read_csv("tests.csv")
    courses_df = pandas.read_csv("courses.csv")
    return students_df, marks_df, tests_df, courses_df

if __name__ == "__main__":
    students_df, marks_df, tests_df, courses_df = load_student_files_into_data_frames()

Now we've encountered the DRY (Don't Repeat Yourself) code smell - performing the same operation multiple times. Let's extract out the CSV read into a separate function like this:

def read_csv(filename):
    return pandas.read_csv(filename)

def load_student_files_into_data_frames():
    file_names = ["students.csv", "marks.csv", "tests.csv", "courses.csv"]
    return map(read_csv, file_names)

However, now we violated the Open/Close Principle - which is that code should be closed for modification but open for enhancement. For example, if you need to add another CSV, you'd have to open the code up, edit it and put the new CSV in, correct? Or if the CSV comes from an external company, and they change its name (for whatever reason), you'd need to edit the code to make it work again, yes? This is true for magic numbers and anything else which can change.
So, the best method is to have the file names in an external .ini file, and use ConfigParser to load the names - but this is a small script, so we'll just define them in the __main__.

def load_student_files_into_data_frames(filename_list):
    return map(read_csv, filename_list)

if __name__ == "__main__":
    filename_list = ["students.csv", "marks.csv", "tests.csv", "courses.csv"]
    students_df, marks_df, tests_df, courses_df = load_student_files_into_data_frames(filename_list)

That's much cleaner, and now we're starting to write our functions in a functional programming style - which is we pass data in, get it modified, and get it passed out again. Nice and clean, and we know exactly what happens to the data where, making it very easy to narrow down bugs.

For instance, the merge_test_marks() function becomes:

def merge_test_marks(marks_df, tests_df):
    return pandas.merge(marks_df, tests_df, left_on="test_id", right_on="id")

and if there were any issues with the merging of those two data frames, you know exactly which function was responsible for the bug (rather than having to laboriously step through the code with a debugger to understand where the variable's data state changed wrongly).

So here would be the final version, and whilst I haven't done anything to clean up the print_students_and_course_results function - as we have two internal loops that should be shuffled off to a separate function - I'll leave that as an exercise for you to attempt. Hope this was helpful, here is the final code (PEP8 formatted except I removed the extra line between functions to make it visually shorter):

import pandas
from statistics import mean

def read_csv(filename):
    return pandas.read_csv(filename)

def load_student_files_into_data_frames(filename_list):
    return map(read_csv, filename_list)

def merge_test_marks(marks_df, tests_df):
    return pandas.merge(marks_df, tests_df, left_on="test_id", right_on="id")

def group_students(marks_tests, students_df, courses_df):
    student_courses = marks_tests.groupby(by="student_id")['course_id'].apply(set)
    students_dict = students_df.set_index("id").to_dict(orient="index")
    courses_dict = courses_df.set_index("id").to_dict(orient="index")
    return student_courses, students_dict, courses_dict

def print_students_and_course_results(student_courses, students_dict, marks_tests, courses_dict):
    for student_id, course_ids in student_courses.iteritems():
        print("Student id: {}, name: {name}".format(student_id, **students_dict[student_id]))
        final_grades = []
        for course_id in course_ids:
            marks = marks_tests.loc[(marks_tests['course_id'] == course_id) & (marks_tests['student_id'] == student_id)]
            final_grades.append(sum(marks['mark'] * (marks['weight'] / 100.0)))

        print("Total Average: {:.2f}%".format(mean(final_grades)))
        for course_id in course_ids:
            print("  Course: {name}, Teacher: {teacher}".format(**courses_dict[course_id]))
            marks = marks_tests.loc[(marks_tests['course_id'] == course_id) & (marks_tests['student_id'] == student_id)]
            final_grade = sum(marks['mark'] * (marks['weight'] / 100.0))
            print("  Final Grade: {:.2f}%".format(final_grade))

if __name__ == "__main__":
    filename_list = ["students.csv", "marks.csv", "tests.csv", "courses.csv"]
    students_df, marks_df, tests_df, courses_df = load_student_files_into_data_frames(filename_list)
    marks_tests = merge_test_marks(marks_df, tests_df)
    student_courses, students_dict, courses_dict = group_students(marks_tests, students_df, courses_df)
    print_students_and_course_results(student_courses, students_dict, marks_tests, courses_dict)

Keep up the coding and Good Luck!


Thread safety and performance when multiple threads write into same Writer Multiple threads write data to a file. When maxLines is reached, the file is closed and a new file is created:

public synchronized void writeLine(String data) throws IOException {
  writer.write(data + "\n");
  lineCounter++;

  if(maxLines != 0 && lineCounter == maxLines) {
    close();

    lineCounter = 0;
    fileCounter++;

    addFile();
    open();
  }
}

As you can see I currently solved this with a synchronized method. This ensures that thread 1 won't write when thread 2 just closed the writer.

I think that's pretty slow. Is there a better solution for this? Maybe with lineCounter as volatile?

Making the lineCounter volatile will not help here. If synchronized is not used, the following sequence of actions is possible:

Thread A writes something to a file.
Thread B writes something to a file.

If the lineCounter was equal to maxLines - 1 before the first step, the behavior of the program is obviously incorrect.

As you have said, you need to synchronize a group of actions(write, close, addFile, open). That's why you need to use synchronized(or a Lock).

About performance: are you sure that synchronization is really an issue? Did you profile your code or are you just making guesses? Before making things more complicated, you should make sure that it will actually solve the problem.


FreeDNS update script I tried to write a script which takes a list of URLs, checks if their FreeDNS record points to the current IP, and updates the record if not.

Intended use is that the script will be run periodically to keep FreeDNS always pointing to the dynamic IP.

Also, a log is kept so the user may later inspect what the script did.

# List of domains that should point to the current IP
freedns_domains = set(["foo.example.com"])

# FreeDNS API endpoint, accessible from https://freedns.afraid.org/api/ (use the ASCII one)
freedns_check_url = "https://freedns.afraid.org/api/?action=getdyndns&sha=REDACTED"

# It is assumed that this address responds with a page containing only the IP address
ip_check_url = "https://ident.me/"

def log(message):
    """
    Appends a string to the logfile (hardcoded as log.txt).
    :param message: The message to be appended. Linebreaks are your responsibility.
    """
    with open("log.txt", "a") as f:
        f.write(message)

import datetime
now = datetime.datetime.now()
log("\n\n" + str(now) + ": Script executing,")
import urllib.request
current_ip = urllib.request.urlopen(ip_check_url).read().decode("utf-8")
log(" IP: " + current_ip)

log("\n\tGetting FreeDNS records...")
import urllib.request
records_raw = urllib.request.urlopen(freedns_check_url).read().decode("utf-8").split("\n")
log(" Found " + str(len(records_raw)) + ".")

for raw_record in records_raw:
    parts = raw_record.split("|")

    domain = parts[0]
    current_freedns_ip = parts[1]
    freedns_update_url = parts[2]

    if domain not in freedns_domains:
        log("\n\t\t" + domain + " is not on the watch list, skipping.")
    else:
        log("\n\t\t" + domain + " (" + current_freedns_ip + ") is on the watch list...")

        if current_ip == current_freedns_ip:
            log(" IPs already match, moving on.")
        else:
            log(" IPs don't match, updating...")
            urllib.request.urlopen(freedns_update_url)
            log(" done.")

log("\n\tScript exited gracefully.")

I know that instead of hard coding freedns_domains, it would be more user-friendly to read them from a text file. I haven't done that since I didn't want to deal with the extra complexity of checking if the input file is full of garbage.

Besides this, in what ways can this script be improved?

Python includes logging in the standard library; rather than write your own, why not use it? You can specify an output file, and handle different levels of logging according to the situation.

Per the style guide, the identifiers of constants like freedns_domains should be UPPERCASE_WITH_UNDERSCORES. Also, any import statements should be at the top of the script.

Your docstring isn't quite formatted correctly, it should look like:

def log(message):
    """Appends a string to the logfile (hardcoded as log.txt).

    :param message: The message to be appended. Linebreaks are your responsibility.

    """

Also, I think that the Google style with sphinx-napoleon is much more readable, but YMMV.

Rather than have virtually the whole script running at the top level of the file, it is conventional to encapsulate it into a single entry point function (sometimes called main) then call it like:

if __name__ == '__main__':
    main()

This makes it much easier to reuse the functionality you've developed by importing it elsewhere without actually running anything.

Rather than using + to concatenate strings, I would generally use str.format, e.g.:

"\n\n" + str(now) + ": Script executing,"

would become:

"\n\n{!s}: Script executing,".format(now)

Improvements are a bit outside the usual scope of CR.SE, but as you've asked:

Yes, reading in the appropriate domains from a file would be a good idea. You could use e.g. a regular expression to validate them, or just try: to access them and deal with any exceptions.
Adding a command line interface (see e.g. argparse) would potentially make this more useful.


Multicriteria sort array I have an array of objects that I must sort based on two criteria. I've come up with a solution but I'd like to know if there is a better way to do it.

Assume a list of devices:

[
    {"battery_level": 0.45, "network_status": "ok"},
    {"battery_level": 0.45, "network_status": "ok"},
    {"battery_level": 0.50, "network_status": "lost"},
    {"battery_level": 0.35, "network_status": "lost"},
    {"battery_level": 0.75, "network_status": "ok"},
    {"battery_level": 0.05, "network_status": "lost"},
    {"battery_level": 0.75, "network_status": "lost"}
]

All lost devices must be on top and sorted by battery status ascending, so that it looks like this once sorted:

[
    {"battery_level":0.05,"network_status":"lost"},
    {"battery_level":0.35,"network_status":"lost"},
    {"battery_level":0.5,"network_status":"lost"},
    {"battery_level":0.75,"network_status":"lost"},
    {"battery_level":0.75,"network_status":"ok"},
    {"battery_level":0.45,"network_status":"ok"},
    {"battery_level":0.45,"network_status":"ok"}
]

Demo here

var devices = JSON.parse(document.getElementById('devices').innerHTML),
    lostDevices,
    sortBatteryLevelAsc,
    sortNetworkStatusLostAsc,
    i;

devices.sort(function (dev0, dev1) {
    return dev0.network_status === 'lost' ? -1 : 1;
});

lostDevices = devices.filter(function (dev) {
    return dev.network_status === 'lost';
});

lostDevices.sort(function (dev0, dev1) {
    return dev0.battery_level <= dev1.battery_level ? -1 : 1;
});

console.clear();
console.log(devices);

Array.prototype.splice.apply(devices, [0, lostDevices.length].concat(lostDevices));

console.log(devices);

Is it smart enough, or is there a smarter way to do it?

There is a better way, use a single sort function where you check on both values. If network status is different, sort on that, otherwise sort on battery power:

var devices = JSON.parse(document.getElementById('devices').innerHTML);

function sortDevicesByStatusAndPower(a, b) {
    var aStatus = a.network_status,
        bStatus = b.network_status;
    if( aStatus != b.network_status )
      return aStatus < bStatus ? -1 : 1;
    else
     return a.battery_level - b.battery_level;
}

console.clear();

console.log(devices.sort( sortDevicesByStatusAndPower ));

I built a jsbin for this: http://jsbin.com/gesoq/1/edit

Finally, storing the JSON iside a script tag is .. novel, not sure it is the best approach.


Are heavy selectors in CSS readable? Take the below code that I recently wrote:

.navbar-inverse .emphasis-text, .navbar-inverse:hover .emphasis-text, .emphasis-text {
    color: #1caa98; /* Teal */
}

While this may be a dryer way of placing teal on all these link items, would you consider this readable? It seems to me like there is a lot to read, and it's not entirely clear what these are for. It's okay if this is fine, but it would be nice to hear some opinions from outside my own eyeballs.

Not really
I think that's about as succinct as it will get. You could improve readability somewhat with some line breaks though, like this:
.navbar-inverse .emphasis-text,
.navbar-inverse:hover .emphasis-text,
.emphasis-text {
    color: #1caa98; /* Teal */
}


RESTful APIs (Create, Read) with flask-restful I wrote this simple API to be able to send logs from the client to MongoDB. Even though this works and fits my need, I would like to point out some concerns that I have regarding the following:

Is it efficient to be calling the instance of MongoClient for every request?
Do I need to close the instance of MongoClient after the request is successful?
A more Pythonic way to return responses?

from flask import Flask, jsonify, request, Response
from flask_restful import Resource, Api
from pymongo import MongoClient
import json

app = Flask(__name__)
api = Api(app)

USER = "user"
PASS = "pw"
MONGO_URI = 'mongodb://%s:%s@test.mlab.com/test' % (USER, PASS)
PORT = 19788

def db_conn():
    client = MongoClient(MONGO_URI, PORT)
    return client

def insert_record(args):
    client = db_conn()
    replycode = 0
    try:
        db = client['test']
        posts = db.users
        posts.insert(args)
    except:
        replycode = 1

    return replycode

def select_record(args={}):

    client = db_conn()
    db = client['test']
    result = db.users.find(args)
    return result

class CreatUser(Resource):

    def post(self):
        try:
            content = request.get_json()
            if "Vehicle" not in content:
                return jsonify({"Result": "Vehicle number not in passed arguments"}), 400

            else:
                vehicle = content['Vehicle']

            reply = insert_record(content)
            if reply == 0:
                return jsonify({"Result" : "Successfully inserted user: " + vehicle}), 201
            else:
                return jsonify({"Result" : "Failed to insert data. Check logs for more details"}), 400

        except Exception as e:
            return jsonify({'Error' : str(e)}), 500

class ViewUser(Resource):
    def get(self):
        from bson import json_util

        results = select_record()
        final = []
        for result in results:
            result.pop("_id")
            final.append(result)

        return jsonify(results=final), 200

api.add_resource(CreatUser, "/api/create")
api.add_resource(ViewUser, "/api/view")

if __name__ == "__main__":
    app.run(debug=True)

The MongoClient was designed to be instantiated once per app life cycle, so this is redundant. You should try to reuse MongoClient instances as much as possible. Basically the only reason to create a new instance is if you want to configure it in a different way.

Also you've mentioned your API is supposed to be RESTful, so a few notes here:

1) To deal with user resource you should include it in the uri in pluralize form and distinguish actions you are performing by standard http codes, like the following:

/api/users POST - to create a new user

/api/users/{userId} GET - to fetch an existing one by userId

2) when you a new user is created it is a good practise to return 201 (Created) http code together with the full url to fetch the user which has been just created, like: http://yourdomain.com/api/users/{userId}

3) "Failed to insert data. Check logs for more details" - it doesn't look like a 400 Bad Request, as the user didn't make any mistake with input params. I suppose it must be either 500 (if the issue is related to something like a database error for example) or 403 Forbidden if any of implicit domain rules has been violated

Hope this helps


Lazy look and say sequence I have been solving a set of online Clojure problems.  One of them involves the look and say sequence.

(defn look-and-say [s]
   (let [las (loop [item (first s) coll s counts [] count 0]
      (cond
         (nil? (seq coll)) (conj counts count item)
         (= item (first coll)) (recur item (rest coll) counts (inc count))
         :else  (recur (first coll)  coll (conj counts count item) 0)))]
      (lazy-seq (cons las (look-and-say las)))))

I would like know what I did right and what I could do better. Any feedback is welcome.

one of the great things about Clojure is the ability to seperate code into concerns and then compose them. This really helps spot reusable parts and lets you build code in smaller independently testable parts.

the parts I see are:

given a sequence of number produce the next one

partition-all the seq into groups of consecutive numbers
for each group of consecutive numbers say how many there are (map say list-o-groups)
flatten the result into one list. but really you should use mapcat in the previous step and skip this step.

apply the the result to the same function (the iterate function)
take as many of these as you need


Creating a list using a struct in C I just got into structs and I decided to create a list using them:

#include<stdio.h>
#include<stdlib.h>
int main(void)
{
    char counter;

    struct list
    {

        int x;
        struct list *pointer1;

    };

    struct list test;
    struct list *pointer2;

    pointer2=&test;

    for(counter=0;counter<5;counter++)
    {

        pointer2->pointer1=malloc(sizeof(struct list));
        pointer2=pointer2->pointer1;

    }
}

I was wondering if there is another way to do the exact same thing.  Is the use of one pointer only possible? By the way, I am pretty sure I could do the same thing using an array of structs too.  Any advice would be really helpful!

This is actually rather unconventional code.  The head node of this list, test, resides on the stack.  All of the subsequent nodes are allocated from the heap using malloc().  Since you never call free() on the memory returned by malloc(), you have a memory leak.  When you eventually try to fix your memory leak, you're very likely to get confused: you need to free() all the nodes except test.

Furthermore, linked lists are usually terminated by a NULL pointer.  After this program finishes, though, the tail of the list is an uninitialized chunk of memory from malloc(), which you should consider to return random garbage.  (In practice, you are likely to get lucky and receive pre-zeroed memory since your program is running on a virgin heap, but you should not count on that behaviour.)

I suggest that you build the linked list all on the heap.  Also, build it backwards, starting from the tail, so that your pointer is always pointing to the head.  When you're done, you'll be holding a pointer to the head, which is useful.

#include <stdlib.h>

int main(void)
{
    struct list
    {
        int x;
        struct list *next;
    };

    /* Create the list */
    struct list *head = NULL;
    /* Just use an int for the counter. A char is just weird. */
    for (int counter = 0; counter < 6; counter++)
    {
        struct list *node = malloc(sizeof(*node));
        node->next = head;
        head = node;
    }

    /* Destroy the list */
    while (head) {
        struct list *node = head;
        head = head->next;
        free(node);
    }
    return 0;
}


ConcurrentHashQueue in C# The ConcurrentHashQueue data structure is a FIFO queue that at the same time allows look-ups of items based on a key in O(1) like a dictionary. It can be used as a cache when the number of cached items is a constant and the eviction strategy is FIFO. This makes sense when the cost of computing/creating an evicted item is not so high to justify the book-keeping costs of a LRU cache.

This implementation is also intended to be thread-safe.

internal class ConcurrentHashQueue<TKey, TValue>
{
    private readonly object _syncRoot = new object();
    private readonly int _capacity;
    private readonly Dictionary<TKey, TValue> _map;
    private readonly Queue<TKey> _queue;

    public ConcurrentHashQueue(int capacity)
    {
        _capacity = capacity;
        _map = new Dictionary<TKey, TValue>(capacity);
        _queue = new Queue<TKey>(capacity);
    }

    public TValue GetOrAdd(TKey key, Func<TValue> createValue)
    {
        TValue value;
        // first try to get the value without locking
        // ReSharper disable once InconsistentlySynchronizedField
        if (_map.TryGetValue(key, out value))
        {
            return value;
        }

        // the value needs to be created and added
        lock (_syncRoot)
        {
            // recheck existence within critical section to avoid racing conditions
            if (_map.TryGetValue(key, out value))
            {
                return value;
            }
            value = createValue();
            Add(key, value);
        }
        return value;
    }

    private void Add(TKey key, TValue value)
    {
        if (_map.Count == _capacity) // capacity reached
        {
            RemoveFirst();
        }
        _map.Add(key, value);
        _queue.Enqueue(key);
        Debug.Assert(_map.Count == _queue.Count, "The count of the queue should always equal to the count of the map.");
        Debug.Assert(_map.Count <= _capacity, "The count of items should never exceed the capacity.");
    }

    private void RemoveFirst()
    {
        TKey first = _queue.Dequeue();
        _map.Remove(first);
    }
}

When you create a List, are you forced to provide a capacity? No you're not. I think it should be the same concerning your data structure. There are several occasions where you just don't know how many objects you'll have. Since the underlying Queue and Dictionary can very well adapt to increase your capacity, your data structure has nothing to fear by offering a default empty constructor.

I'm wondering why GetOrAdd exists. When you Get an object from a Queue, you should remove that object, IMO. So you should implement some kind of Exists method, and the client of your object will deal with the scenario where you could want to add an object if it doesn't exist already.

Finally, there is one terrible side effect in your code :

if (_map.Count == _capacity) // capacity reached
{
    RemoveFirst();
}

If you reach capacity, you should either expand your capacity, or throw an exception. Removing the first object is just a way to hide the problem. But if I use your class, I would never expect this situation if the queue was full.


Rhezo and divisibility by 7 challenge There is a big number with N digits and Q questions.

  In each question, find if the number formed by the string between
  indices Li and Ri is divisible by 7 or not.

  Input: First line contains the number consisting of N digits. Next line contains Q, denoting the number of questions. Each of the next Q
  lines contains 2 integers a and b.

  Output: For each question, print "YES" or "NO", if the number formed by the string between indices a and b is divisible by 7.

  Constraints: 1≤N≤105, 1≤Q≤105, 1≤a,b≤N

Full question

def is_divisible_by_7(num):

    if num - num / 7 * 7 == 0:

        return True
    else:

        return False

N = raw_input()

Q = int(raw_input())

for x in xrange(Q):

    a, b = map(int, raw_input().split())

    if is_divisible_by_7(int(N[a - 1:b])):
        print "YES"
    else:
        print "NO"

First regarding style. Python has an official style-guide, PEP8, which recommends having no unnecessary whitespace. It improves readability a lot if you avoid having a blank line between every line. Use them sparingly to set apart larger logical blocks.

The standard way, which is the most efficient, to test for divisibility is the modulus operator, %. This way you don't have to rely on integer division to always be around (which it will not be, it has been removed by full division in python 3.x). You can also directly return the result of the comparison:

def is_divisible_by_7(num):
    return num % 7 == 0

You should put your code in a f __name__ == "__main__" guard and into functions to allow re-usability of your code:

def main():
    N = raw_input()
    Q = int(raw_input())

    for _ in xrange(Q):
        a, b = map(int, raw_input().split())
        num = int(N[a - 1:b])
        print "YES" if num % 7 == 0 else "NO"

if __name__ == "__main__":
    main()

Here I inlined the function is_divisible_by_7, used _ as a place-holder variable which is not used in the loop as customary in Python and used a ternary expression to print the result. You also don't need to use split, in python 2.x map returns a list which can directly be used in tuple-assignment.

Alternatively, if a and b appear repeatedly, caching might help:

def memodict(f):
    """ Memoization decorator for a function taking a single argument"""
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__

@memodict
def is_divisible_by_7(indices):
    a, b = map(int, indices.split())
    return "NO" if int(N[a - 1:b]) % 7 else "YES"

N = raw_input()
Q = int(raw_input())
for _ in xrange(Q):
     print is_divisible_by_7(raw_input())

As a third alternative, we could not cache the indices, but the numbers for which we do the divisibility test. This is worthwhile if they repeat and are big.

@memodict
def is_divisible_by_7(n):
    return int(n) % 7 == 0

N = raw_input()
Q = int(raw_input())
for _ in xrange(Q):
     a, b = map(int, raw_input().split())
     print "YES" if is_divisible_by_7(N[a - 1:b]) else "NO"

with the same memodict class as above.

This could be made slightly faster by not printing every line, but aggregating the results first:

N = raw_input()
Q = int(raw_input())
out = []
for _ in xrange(Q):
     a, b = map(int, raw_input().split())
     out.append("YES" if is_divisible_by_7(N[a - 1:b]) else "NO")
print "\n".join(out)

A fourth possibility is to try to exploit a divisibility rule for 7. There are not very nice ones, but I did find this one:

  Double the last digit and subtract it from a number made by the other
  digits. The result must be divisible by 7. (We can apply this rule to
  that answer again) (source)

So we want to recursively test the number. But since it can have up to 10**5 digits, we have to hope that it tires small numbers first, otherwise we run into python's recursion limit. However, we can increase that limit to the number of digits, N.

import sys

MAX_INT = 2**31 - 1

@memodict
def is_divisible_by_7(n_str):
    if n <= MAX_INT:  # mod should be fast enough below this limit
        return int(n_str) % 7 == 0
    return is_divisible_by_7(str(int(n_str[:-1]) - 2*int(n_str[-1])))

N = raw_input()
sys.setrecursionlimit(MAX_INT)  # to allow processing the number
Q = int(raw_input())
for _ in xrange(Q):
     a, b = map(int, raw_input().split())
     print "YES" if is_divisible_by_7(N[a - 1:b]) else "NO"

This does a lot more processing, especially conversions between str and int. But maybe combined with the caching it might do some good.


Calculate next working day I have tried to tackle this question as follows:

The program Calculates the next Working day, taking into account:
   - weekends (Saturdays and Sundays)
   - holidays happening in the middle of the week

param name="OrderDate" the date on which the order is placed
param name="workingDays" the number of workingdays to process the order
returns the date on which the Order is Requested to Ship

    public static DateTime getNextWorkingDay(DateTime OrderDate, int workingDays)
    {
        DateTime Holiday = new DateTime();
        List<DateTime> SelectedHolidays = new List<DateTime>();
        List<HolidayList> HolidayList = new List<HolidayList>();

        int calculatedWorkingDays=0;
        if (workingDays <= 5)
            calculatedWorkingDays = workingDays;
        else if (workingDays % 6 == 0)
        {
            calculatedWorkingDays = workingDays + workingDays / 6 * 2;
        }
        else
        {
            calculatedWorkingDays = workingDays + workingDays / 7 * 2;
        }

        HolidayList =  "Read the list from Json file";

        foreach (var holiday in HolidayList)
        {
            string year = DateTime.Today.Year.ToString();
            Holiday = DateTime.Parse(holiday.MonthAndDayValue + "-" + year);

            if (Holiday.Day == 1 && Holiday.Month == 1)
            {
                year = (DateTime.Today.Year + 1).ToString();
                Holiday = DateTime.Parse(holiday.MonthAndDayValue + "-" + year);
            }

            SelectedHolidays.Add(Holiday.Date);

            if (Holiday.DayOfWeek == DayOfWeek.Sunday || Holiday.DayOfWeek == DayOfWeek.Saturday)
            {
                //do nothing
            }
            else
            {
                if (Holiday.Date == OrderDate.Date)
                    OrderDate.AddDays(1);
                if (Holiday.Date > OrderDate.Date)
                {
                    int K = (int)(Holiday.Date - OrderDate.Date).TotalDays;
                    if (K <= calculatedWorkingDays)
                    {
                        calculatedWorkingDays++;
                    }
                }
            }
        }
        if (OrderDate.DayOfWeek == DayOfWeek.Sunday)
        {
            calculatedWorkingDays++;
        }
        else if (OrderDate.DayOfWeek == DayOfWeek.Saturday || OrderDate.DayOfWeek == DayOfWeek.Friday)
        {
            calculatedWorkingDays += 2;
        }

        // this is required date
        DateTime date_OrderRequestedToShip = OrderDate.AddDays(calculatedWorkingDays);

        //check if the last date fall on a non working day(holiday  or weekend)
        calculatedWorkingDays = 0;
        foreach (DateTime d in SelectedHolidays)
            if (d.Date == date_OrderRequestedToShip.Date)
                calculatedWorkingDays++;
        date_OrderRequestedToShip = date_OrderRequestedToShip.AddDays(calculatedWorkingDays);
        if (date_OrderRequestedToShip.DayOfWeek == DayOfWeek.Sunday)
        {
            calculatedWorkingDays = 1;
        }
        else if (date_OrderRequestedToShip.DayOfWeek == DayOfWeek.Saturday)
        {
            calculatedWorkingDays = 2;
        }

        return date_OrderRequestedToShip.AddDays(calculatedWorkingDays);
    }

The holiday list contains the month and day (MM/dd) part only with out the year part:

{
    "holidayName": "Memorial Day",
    "MonthAndDayValue": "05-30"
}

Can anyone help to tune up or suggest changes to make the code more efficient?

First, you should separate a process of parsing your input from your business logic. So, your first step is to convert your holidays input to a structure you'll be working with. So, let's say you have a List<Holiday> where

public struct Holiday
{
    public readonly int Month;
    public readonly int Day;

    public Holiday(int month, int day)
    {
        Month = month;
        Day = day;
    }
}

Now, in your place I'd start with implementation of something that enumerates working days like so:

static IEnumerable<DateTime> GetWorkingDays(DateTime startDate, List<Holiday> holidays)
{
    var date = startDate;

    for (;;date = date.AddDays(1))
    {
        if (date.DayOfWeek != DayOfWeek.Saturday &&
            date.DayOfWeek != DayOfWeek.Sunday &&
            holidays.All(holiday => holiday.Day != date.Day ||
                                    holiday.Month != date.Month))
        {
            yield return date;
        }
    }
}

Note that this iterator is endless, so you should be cautious enumerating it.

Now, your problem can be solved with just one line

var result = GetWorkingDays(orderDate, holidays).Skip(workingDays).First();

Complete example here: https://dotnetfiddle.net/W3dalr


Rewriting dispatch method Is it possible to rewrite this piece of code any better when it comes to efficiency and/or readability?

public function dispatch()
{
    $key = array_search($this->reqUri, $this->routes);

    if ($key !== false) {
        if (isset($this->methods[$key])) {
            if ($this->methods[$key] === $this->reqMethod) {
                call_user_func($this->callables[$key]);

                return;
            } else {
                $this->defaultCallable();

                return;
            }
        }

        call_user_func($this->callables[$key]);

        return;
    }

    $this->defaultCallable();
}

The array_search will iterate over every element in $this->routes. That's not scalable. It would be better to reorganize $this->routes so that you can lookup keys more directly, so that your code will work like this:

if (isset($this->routes[$this->reqUri])) {
    $key = $this->routes[$this->reqUri];
    // ...
}

In this arrangement, the lookup should be in \$O(1)\$ time or close, even with large number of routes.

Do you really need the !== false here?

if ($key !== false) {

Can't it be simply:

if ($key) {

In the innermost if, since you return in both the if and the else, you could move the return statement outside:

if (isset($this->methods[$key])) {
    if ($this->methods[$key] === $this->reqMethod) {
        call_user_func($this->callables[$key]);
    } else {
        $this->defaultCallable();
    }
    return;
}

In terms of readability, I find it slightly better this way:

if ($key) {
    if (isset($this->methods[$key])) {
        if ($this->methods[$key] === $this->reqMethod) {
            call_user_func($this->callables[$key]);
            return;
        }
    } else {
        call_user_func($this->callables[$key]);
        return;
    }
}

$this->defaultCallable();

That is, the $this->defaultCallable() call appears only once instead of twice, everything else still being the same.


FAMILY.PY | OOPython Simple code where family and person instances can be created. There is a method where any instance of Person can be added to any instance of Family.

class Family:
    def __init__(self):
        self.names, self.birthplaces, self.dobs, self.deaths = [], [], [], []

class Person:
    def __init__(self, name, birthplace, dob, death=None):
        self.name, self.birthplace, self.dob, self.death = name, birthplace, dob, death

    def add_member_to(self, family_tree):
        family_tree.names.append(self.name)
        family_tree.birthplaces.append(self.birthplace)
        family_tree.dobs.append(self.dob)

        if self.death is None:
            family_tree.deaths.append('N/A')
        else:
            family_tree.deaths.append(self.death)

family = Family()
mike = Person('Michael', 'Nigeria', '06-07-2004')
esther = Person('Esther', 'KC', '03-25-2009')
mike.add_member_to(family)
esther.add_member_to(family)
print(family.dobs)
print(family.names)
print(family.birthplaces)
print(family.deaths)

My one improvement would be this line of code

if self.death is None:
    family_tree.deaths.append('N/A')
else:
    family_tree.deaths.append(self.death)

can be reduced to one line:

family_tree.deaths.append('N/A' if self.death is None else self.death)

Also, I would recommend keeping all code not in these classes in a main guard, so you can import these classes without also running the code in the module.


Generating a password to save to a .txt file Here is my basic password generator which saves your password to a .txt file which you can choose the name of etc.

import random
import string
import os.path
#random numbers section
num1 = random.randrange(100,999)
number_section =  num1
#random letters section
string.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()'
let1 = random.choice(string.letters)
let2 = random.choice(string.letters)
let3 = random.choice(string.letters)
let4 = random.choice(string.letters)
let5 = random.choice(string.letters)
let6 = random.choice(string.letters)
let7 = random.choice(string.letters)
let8 = random.choice(string.letters)
letters_section = let1 + let2 + let3 + let4 + let5 + let6 + let7 + let8
#letters and numbers combination
password = str(number_section) + letters_section
#input section
password_for = raw_input('This password is for: ')
your_pass =  'Your password for' + ' ' + password_for + ' ' + 'is:' + ' ' + password
print your_pass
#save section
save_path = 'C:\Users\Charles\Desktop\Passes'
name_of_file = raw_input("What is the name of the file: ")
completeName = os.path.join(save_path, name_of_file+".txt")
file1 = open(completeName, "w")
toFile = your_pass
file1.write(toFile)
file1.close()

This will make a .txt file with a line such as:

  Your password for IBM bluemix is: 451juoxQYky

How can I make it 'stronger'? Are there any major holes in it? How can I make it more compact?

This is just a personal project I'm doing to improve my python knowledge.

By making it more Pythonic for one:

string.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()'
let1 = random.choice(string.letters)
let2 = random.choice(string.letters)
let3 = random.choice(string.letters)
let4 = random.choice(string.letters)
let5 = random.choice(string.letters)
let6 = random.choice(string.letters)
let7 = random.choice(string.letters)
let8 = random.choice(string.letters)
letters_section = let1 + let2 + let3 + let4 + let5 + let6 + let7 + let8

should be:

''.join(random.choice(string.letters) for _ in range(length))

Now instead of a hard coded length you can ask the user for a length or easily change it by changing one variable instead of adding or deleting lines.

Instead of this:

file1 = open(completeName, "w")
toFile = your_pass
file1.write(toFile)
file1.close()

You want:

with open(completeName, "w") as file1:
    file1.write(your_pass)  # no need to assign a new variable

The with context manager will automatically handle closing the file for you.

This seems to be a pattern in your code but its wholly unnecessary:

num1 = random.randrange(100,999)
number_section =  num1

Just use num1 or save the output of randrange() to number_section directly there is no need for an intermediate variable.

So in the end you can simplify to:

import random
import string
import os.path

num1 = random.randrange(100,999)
string.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()'

letters_section = ''.join(random.choice(string.letters) for _ in range(8))  # change 8 to a variable if you want to ask the user for a length or have it passed as an argument
password = str(number_section) + letters_section

password_for = raw_input('This password is for: ')
your_pass =  'Your password for {} is: {}'.format(password_for, password)
print(your_pass)

save_path = 'C:\Users\Charles\Desktop\Passes'
name_of_file = raw_input("What is the name of the file: ")
completeName = os.path.join(save_path, name_of_file+".txt")
with open(completeName, "w") as file1:
    file1.write(your_pass)

Or even more simply:

def gen_password(length):
    choices = string.digits + string.punctuation + string.ascii_letters
    return ''.join(random.choice(choices) for _ in range(length))

>>> gen_password(13)
'7P~R6dSy<T)+Z'
>>> gen_password(20)
"Q{qHs6ahwj^EaT_'t,.7"
>>> gen_password(11)
'XDi49z+;^?='


T-SQL query Choose name of clients, concluded more than one loan agreement in 2010 QUESTION: Choose the name of clients,
concluded more than one loan agreement in 2010,
as the numbers and dates of issue of these contracts.
Sort by name of the client and date of issue of the loan.

My question: Is it the correct way of solving this task?
Sqlfiddle: http://www.sqlfiddle.com/#!18/c140c/1

DDL:

create table client(
    cl_id int primary key identity (1,1),
    cl_full_name nvarchar(100) not null,
);

create table deal(
    dl_id int primary key identity (1,1),
    dl_client_id int not null,
    dl_code nvarchar(100) not null,
    dl_valutation_date datetime not null,
    foreign key(dl_client_id) references client(cl_id)
);

QUERY:

SELECT  c.cl_full_name                      AS "ФИО Клиента",
        d2.dl_code                          AS "Номер договора",
        Cast(d2.dl_valutation_date AS DATE) AS "Дата выдачи"
FROM (
        SELECT d.dl_client_id
        FROM   deal AS d
        WHERE  Year(d.dl_valutation_date) = 2010
        GROUP  BY d.dl_client_id
        HAVING Count(*) > 1
) AS t1
INNER JOIN deal AS d2
        ON d2.dl_client_id = t1.dl_client_id
INNER JOIN client AS c
        ON c.cl_id = d2.dl_client_id
ORDER  BY c.cl_full_name,
        d2.dl_valutation_date

I believe your code will work based on what you provided.  However, I would recommend a couple of changes.

T1 does not need to be part of the result set as you do not retrieve anything from it.  Since it is only used to filter, I've moved it to an exists clause.
Avoid expressions on the data field when comparing to a static or known value.  It takes a bit more typing, but can provide performance benefits in your code.

SELECT  c.cl_full_name AS "ФИО Клиента",
        d2.dl_code AS "Номер договора",
        CAST(d2.dl_valutation_date AS DATE) AS "Дата выдачи"
FROM  deal AS d2
  INNER JOIN client AS c ON c.cl_id = d2.dl_client_id
WHERE EXISTS ( SELECT 1
       FROM deal AS d
       WHERE d.dl_valutation_date >= '20100101'
         AND d.dl_valutation_date < '20110101'
         AND c.cl_id = d.dl_client_id
       GROUP BY d.dl_client_id
       HAVING COUNT(*) > 1)
ORDER BY c.cl_full_name,
 d2.dl_valutation_date ;

UPDATE to respond to comment

Leveraging good performance practices builds a foundation that makes good performance possible.  If there is another part of your query that has a greater impact to performance, the first recommendation may or may not affect performance by itself.  However, it can help to reveal other performance bottlenecks.


Determining if a sentence is a palindrome The biggest problem I see in checking palindromes on the Internet is when the user inputs a palindrome sentence or phrase and the program returns a wrong output. So for me, I tried to optimize palindrome checking by accepting sentences as input.

import java.io.*;

public class PalindromeCheck{

  public static void main(String[] args){

    BufferedReader dataIn = new BufferedReader(new InputStreamReader(System.in));
      try{

        System.out.print("Enter a sentence: ");
          String sentence = dataIn.readLine();
          PalCheck(sentence);

      }catch(IOException e){

        e.printStackTrace();
        System.err.println(e);

      }
    }

  public static void PalCheck(String s){

    String end = "";
    String result = s.replaceAll(" ", "");
     for ( int i = result.length() - 1; i >= 0; i-- )
       end = end + result.charAt(i);

        if (result.equalsIgnoreCase(end))
           System.out.println( result + " is a palindrome.");
        else
           System.out.println(result + " is not a palindrome.");

  }

}

The implementation given by @janos is a good one, but it is possible to improve it further. Specifically, most of the inefficiency arises from the single line:
char[] chars = string.replaceAll(" ", "").toLowerCase().toCharArray();

The replaceAll() method creates another copy of the string. Then, toLowerCase() creates another copy of the string. Finally, toCharArray() creates yet another copy in a character array of the resulting string. Of course, with the exception of the final result, the rest will get garbage collected. But each of the copies in an additional O(n) time.
Here is a suggestion:
private static boolean isPalindrome(String s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j) {
        if (Character.isWhitespace(s.charAt(i))) {
            i++;
            continue;
        }

        if (Character.isWhitespace(s.charAt(j))) {
            j--;
            continue;
        }

        if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
            return false;
        } else {
            i++;
            j--;
        }
    }
    return true;
}

I used the following test code to compare the performances of the two methods:
public class Main {

public static void main(String[] args) {

    String palindrome = "a b c de f g h x x xa b   a xxx     hg f e d c b  a";
    String nonPalindrome = "abcd e f g h  xxxabcxxx hgfe  d c ba";

    long start = System.currentTimeMillis();

    for (int i = 0; i < 1000000; i++) {
        Main.checkPalindrome(palindrome);
        Main.checkPalindrome(nonPalindrome);
    }

    long elapsed = System.currentTimeMillis() - start;

    System.out.println("checkPalindrome: time elapsed: " + elapsed + " milliseconds.");

    start = System.currentTimeMillis();

    for (int i = 0; i < 1000000; i++) {
        Main.isPalindrome(palindrome);
        Main.isPalindrome(nonPalindrome);
    }

    elapsed = System.currentTimeMillis() - start;

    System.out.println("isPalindrome: time elapsed: " + elapsed + " milliseconds.");

}

private static boolean isPalindrome(String s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j) {
        if (Character.isWhitespace(s.charAt(i))) {
            i++;
            continue;
        }

        if (Character.isWhitespace(s.charAt(j))) {
            j--;
            continue;
        }

        if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
            return false;
        } else {
            i++;
            j--;
        }

    }

    return true;
}

private static boolean checkPalindrome(String string) {
    char[] chars = string.replaceAll(" ", "").toLowerCase().toCharArray();
    for (int i = 0; i < chars.length / 2; ++i) {
        if (chars[i] != chars[chars.length - 1 - i]) {
            return false;
        }
    }
    return true;
}

}

Running on my computer produced the following result:

checkPalindrome: time elapsed: 7373 milliseconds.
isPalindrome: time elapsed: 421 milliseconds.


Applying limit and offset to an array I'm refactoring an old gateway and came across the following method:

def apply_limit_and_offset(options)
  limit  = options[:limit]
  offset = options[:offset]

  @result = if offset
    @result.drop offset
  else
    @result
  end

  @result = if limit
    @result.first limit
  else
    @result
  end

  @result
end

@result is an Array of objects.

Any suggestions on how to refactor this?  It works just fine, but multiple if statements make me feel gross.

Some notes:

Be consistent with the use of parens.
Use ternary expressions (?) to reduce short conditionals.
If you are using Ruby >= 2.0, check named keywords.
The resulting expression of an assignment is its value, so you can remove the last @result
What looks gross to me are those in-place updates of @result, but this goes beyond the scope of the question.

With Ruby >= 2.0, I'd write:

def apply_limit_and_offset(limit: nil, offset: nil)
  @result = offset ? @result.drop(offset) : @result
  @result = limit ? @result.first(limit) : @result
end


Initializing a tile-like map such that the edges are marked with an 'X' I've been messing around with arrays as I'm learning them currently in my book and they gave the idea of a chess board using for loops alongside multidimensional arrays to give them individual values which you can therefore print out.

However, I thought of the old console RPG games from way back and wanted to simply add a border around the array so it prints any 0 || 19 value as an X. The code does work however, is there a way of making it more efficient by using if statements or by created a switch statement that reads the current loop variable and change that array value to a 1 for fill or leave it 0 to blank the "tile".

#include <iostream>

using namespace std;

int main()
{
    int rpgLevelGrid[20][20];

    //Co-od decleration
    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            switch (i)
            {
            case 0: case 19:
                rpgLevelGrid[i][j] = 1;
                break;
            default:
                rpgLevelGrid[i][j] = 0;
                break;
            }

            switch (j)
            {
            case 0:
                rpgLevelGrid[i][j] = 1;
                break;
            case 19:
                rpgLevelGrid[i][j] = 1;
                break;
            }
        }
    }

    for (int i = 0; i < 20; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            switch (rpgLevelGrid[i][j])
            {
            case 1:
                cout << "X";
                break;
            default:
                cout << "-";
            }
        }
        cout << endl;
    }
}

switch vs. if

In

        switch (rpgLevelGrid[i][j])
        {
        case 1:
            cout << "X";
            break;
        default:
            cout << "-";
        }

do not use switch when all you need is a regular if. Instead do

        if (rpgLevelGrid[i][j])
        {
            cout << "X";
        }
        else
        {
            cout << "-";
        }

or even better do

        cout << (rpgLevelGrid[i][j] ? "X" : "-");

You could also fill the grid with the characters to print unless there is reason not to do so. Then you only do

        cout << rpgLevelGrid[i][j];

A third option for the output is to define a symbol table like

const char symbols[] = "-X";

and use it like

        cout << symbols[rpgLevelGrid[i][j]];

Initialisation

Also our inner init loop is not consistent. you conditionally init with 1 on i but conditionally overwrite the previously initialized 0 with 1 on j. Wwhy not init all with 0 and overwrite the borders? That is less complex. So

        switch (i)
        {
        case 0: case 19:
            rpgLevelGrid[i][j] = 1;
            break;
        default:
            rpgLevelGrid[i][j] = 0;
            break;
        }

        switch (j)
        {
        case 0:
            rpgLevelGrid[i][j] = 1;
            break;
        case 19:
            rpgLevelGrid[i][j] = 1;
            break;
        }

becomes

        rpgLevelGrid[i][j] = 0;
        if (i==0 || i==19 || j==0 || j==19)
        {
            rpgLevelGrid[i][j] = 1;
        }

Number literals

Still there are some magic numbers. We now define

const int dim = 20;

and replace all literals in the code like

int rpgLevelGrid[dim][dim];

for (int i = 0; i < dim; i++)

case dim-1:

or

        if (i==0 || i==dim-1 || j==0 || j==dim-1)

Functions

Finally we pull out some code from main and provide two functions for init and print and end up in

#include <iostream>

using namespace std;

const int dim = 20;

void init(int grid[dim][dim])
{
    for (int i = 0; i < dim; i++)
    {
        for (int j = 0; j < dim; j++)
        {
            grid[i][j] = 0;
            if (i==0 || i==dim-1 || j==0 || j==dim-1)
            {
                grid[i][j] = 1;
            }
        }
    }
}

void print(int grid[dim][dim])
{
    const char symbols[] = "-X";
    for (int i = 0; i < dim; i++)
    {
        for (int j = 0; j < dim; j++)
        {
            cout << symbols[grid[i][j]];
        }
        cout << endl;
    }
}

int main()
{
    int rpgLevelGrid[dim][dim];

    init(rpgLevelGrid);
    print(rpgLevelGrid);
}

That is a resonable result for a beginner.


Finding unpaired number in an odd length Array of integers codility OddOccurrencesInArray:

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7  A[6] = 9
    • the elements at indexes 0 and 2 have value 9,
    • the elements at indexes 1 and 3 have value 3,
    • the elements at indexes 4 and 6 have value 9,
    • the element at index 5 has value 7 and is unpaired.
Write a function:
     class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers fulfilling the above conditions,
returns the value of the unpaired element.

class Solution {

    public int solution(int[] A) {

        final int len = A.length;

        Arrays.sort(A);

        for (int i = 0; i < len ;) {
            int counter = 1;
            int current = A[i];

            while ((i < len - 1) && (current == A[++i])) {
                counter++;
            }

            if (counter % 2 == 1) {
                return current;
            }
        }
        return -1;
    }
}

Could this code be bettered in terms of time complexity or code quality?

Sorting of the array will take O(n (log n)) in the average case. You can do it in linear time using bitwise operation

public class Test {
    public static void main(){
        int a = 0;
        int[] arr = {9,3,9,3,9,7,9};

        for (int i = 0; i < arr.length; i++ ){
            a = a ^ arr[i];
        }

        System.out.println(a);
    }
}

Any number which will XOR with 0 will be the number itself. But if it will XOR with itself, it will be 0. In the end, we'll get the non paired number.