Checking if a text contains N consecutive repeating characters I want to check a text for consecutive repeating characters. For example, with a minimum of 3 consecutive chars, this should match:

Okeee
OOOkee
Alsoook

This should not match:

No not okee, oh no

This is my code:

public static bool HasConsecutiveChars(string source, int sequenceLength)
        {
            if (string.IsNullOrEmpty(source))
            {
                return false;
            }

            if (source.Length == 1)
            {
                return false;
            }

            int charCount = 1;

            for (int i = 0; i < source.Length - 1; i++)
            {
                char c = source[i];
                if (c == source[i + 1])
                {
                    charCount++;

                    if (charCount >= sequenceLength)
                    {
                        return true;
                    }
                }
                else
                {
                    charCount = 1;
                }
            }

            return false;
        }

It works but I feel there should be a cleaner solution to this problem.

Edit - there is a bug with this: see my other answer

This is very easy with Regular Expressions:

public static bool HasConsecutiveChars(string source, int sequenceLength)
{
    // should check sequence length

    // just repeating letters
    return Regex.IsMatch(source,"([a-zA-Z])\\1{"+ (sequenceLength - 1) + "}");

    // any character version
    // return Regex.IsMatch(source,"(.)\\1{"+ (sequenceLength - 1) + "}");
}

The regular expression simply captures each letter into a group and then checks if it is repeated the number of times minus one. I've omitted range checking.

Talking about your code for a moment:

Great method name - would be perfect as an extension method in my opinion.

These two checks can be merged:

if (string.IsNullOrEmpty(source))
{
    return false;
}

if (source.Length == 1)
{
    return false;
}


Calculating the terminal width and height As part of the bigger problem I am trying to solve smaller problems first and hence below is the code to find the terminal width and height.

Code

'use strict';

class Terminal {
  width() {
    return process.stdout.columns || 80
  }

  height() {
    return process.stdout.rows || 60
  }
}

module.exports = Terminal

How can I make the above code testable? can I use some better abstraction?

What is the functionality of this class?
Get width and height from process.stdout,
an external resource,
or else fall back to default values.

You can make this testable by making it possible to inject process.stdout, the external resource.
Then in the test you can inject an object that you control,
and verify that Terminal uses that object correctly or else falls back to the defaults correctly.

To make process.stdout injectable, you have at least two options:

Add an optional constructor argument. By default use process.stdout, only the test method will inject a custom object.
Add a _stdout function, that will be used by width and height, and in the test override it appropriately.


Q: Project Euler #1 - C# Good day, it's my first time doing something like this so I wanted to solve some of the challenges on project Euler, however I reached a block on my code, even before I submitted I was aware that I would be unable to compile within time limits for numbers well beyond the million or close to a million, still went along with it and of course, the test cases on the million(s)? [because they are hidden and I dont exactly know the numbers] expired due to time limits constraints.

I was wondering if I could receive some feedback on how to improve my code, given that at the minimum the value received would be a million of course.

class Solution {

    private static void mathSolver(long _number){
        long _sum = 0;

        for(long x = 0; x<_number; x++){
            if((x % 3 == 0) || (x % 5 == 0)){
                _sum += x;
            }
        }
        Console.WriteLine(_sum);
    }

    static void Main(String[] args) {
        int t = Convert.ToInt32(Console.ReadLine());
        for(int a0 = 0; a0 < t; a0++){
            int n = Convert.ToInt32(Console.ReadLine());
            mathSolver(n);
        }
    }
}

I already tried of tinkering with it with some math sequences, trying to figure out a pattern that would allow me to jump between numbers, so that instead of iterating through every number on a million, I would, lets say, jump between 3's or 5s directly, however no operation that I could think of would give me the result I wanted as it was very prone to mistakes along the way.

A slight background of me if anyone is interested while reviewing, I'm not exactly new to C#, been doing it for slightly under 2 years however my first employer procured tons of bad practices and code disasters, this is why I want to expose myself to these kind of things, to improve efficiency while coding, to get better code readibility and presentation as well as trying to find solutions that aren't as forceful.

Thank you for your answers and may you have a nice day!

Hint:

$$
\sum_{i=1}^ni = \frac{n (n+1)}{2}
$$

With this you can compute the sum of 1 to n without looping. Can you figure out a way to do this for all digits with increments of 3? And 5?

The last thing to consider is that with this method, you are counting all digits divisible by 15 double, since they are both divisible by 3 and 5.


Shuffler with generics for C# This is something I am always asked by managers and clients : "make it random". More often than not, this isn't what they want.

Comments like "I had the same element twice in a row !" and "I don't see lement X often enough !" are common, even if they are part of the "true random".

I came up with the following solution using generics. It's basically a Urn with a safeguard so the last item isn't picked after a refill. I'm looking for ways to improve it. Is it readable ? Is it efficient enough ?

using System;
using System.Collections;
using System.Collections.Generic;

namespace Utils
{
    /// <summary>
    /// Implements "iTunes shuffle" that is to say, it's a random where you can't get twice the same value unless you
    /// already got all the values.
    ///
    /// To avoid having a chance to get twice the same value when refilling the pool, we store the last picked value in
    ///  `_last` and do not put it back when refilling the pool
    ///
    /// author: ray.hubert@riseup.net
    /// </summary>
    public class Shuffler<T> : IEnumerable
    {
        private readonly List<T> _allItems = new List<T>(); // All items used in the shuffler
        private readonly List<T> _pool = new List<T>(); // Remaining items for current series
        private T _last; //Last object extracted from the pool
        private Random _random = new Random();

        private int PoolCount
        {
            get { return _pool.Count; }
        }

        public Shuffler()
        {
        }

        public Shuffler(ICollection<T> allItems)
        {
            if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            _allItems.AddRange(allItems);
            PopulatePool();
        }

        public T GetNext()
        {
            if (IsPoolEmpty())
            {
                PopulatePool();
            }
            return PopRandomElement();
        }

        private T PopRandomElement()
        {
            if (PoolCount == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            int randomIndex = _random.Next(PoolCount);
            T item = _pool[randomIndex];
            _pool.RemoveAt(randomIndex);
            if (IsPoolEmpty()) _last = item;
            return item;
        }

        private void PopulatePool()
        {
            _pool.Clear();
            _pool.AddRange(_allItems);
            if (PoolCount > 1) // If _allItems is size 1 we don't remove from the pool : it would be empty
            {
                RemoveLastFromPool();
            }
        }

        private void RemoveLastFromPool()
        {
            _pool.Remove(_last);
            _last = default(T);
        }

        public List<T> GetAllPossibleValues()
        {
            return new List<T>(_allItems);
        }

        private bool IsPoolEmpty()
        {
            return PoolCount == 0;
        }

        public IEnumerator GetEnumerator()
        {
            while (PoolCount > 0)
            {
                yield return PopRandomElement();
            }
        }

        public void Add(T element)
        {
            _allItems.Add(element);
            PopulatePool();
        }
    }
}

Sample usage #1 :

// Loops on all alements and stop
Shuffler<int> shuffler = new Shuffler<int> {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
foreach (int number in shuffler)
{
    Console.Write("Random element : " + number);
}

Sample usage #2 :

// Loops on all elements for ever
Shuffler<string> shuffler = new Shuffler<string> {"Alice", "Bob", "John", "Bill", "Scrooge"};
bool gameIsPlaying = true;
while (gameIsPlaying)
{
    Console.Write("Random element : " + shuffler.GetNext());
}

Points I'm wanting to improve :

The empty constructor seems necessary for the Add() function to work properly (see usage)
Throwing an exception in two code path is suboptimal, I'd rather have a single place to throw it
Readability, "code-cleanness"

public class Shuffler<T> : IEnumerable

Why not IEnumerable<T>??!

        private readonly List<T> _allItems = new List<T>(); // All items used in the shuffler

The types in this line raise two red flags in my mind.

Code to the interface, not the implementation. The type of the field per se should be an interface: maybe IList<T>, maybe ICollection<T>, or maybe even something else.
With respect to maybe even something else: should it be ISet<T>? The explanation given for the use case suggests strongly that elements should not be repeated, because if they are repeated it's going to be complicated to avoid playing the same track twice in a row.

        private readonly List<T> _pool = new List<T>(); // Remaining items for current series

Again, code to the interface. Here IList<T> is justified because the ability to select by index is important for performance.

        private T _last; //Last object extracted from the pool

If "last" here means "most recent" then the methods further down seem buggy.

        private int PoolCount
        {
            get { return _pool.Count; }
        }

Are you deliberately avoiding the arrow syntax?

        private int PoolCount => _pool.Count;

is going to become increasingly common.

        public Shuffler(ICollection<T> allItems)
        {
            if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            _allItems.AddRange(allItems);
            PopulatePool();
        }

I concur with VisualMelon's observations on this constructor: there's no reason to prohibit empty inputs, there's no need to populate the pool yet, and there's no reason to require ICollection<T> rather than IEnumerable<T>.

        public T GetNext()
        {
            if (IsPoolEmpty())
            {
                PopulatePool();
            }
            return PopRandomElement();
        }

vs

        public IEnumerator GetEnumerator()
        {
            while (PoolCount > 0)
            {
                yield return PopRandomElement();
            }
        }

Firstly, I find this API very confusing. It would make more sense to me if both methods ran forever, repopulating the pool if it runs dry.

Secondly, IsPoolEmpty() vs PoolCount > 0 is inconsistent. IMO factoring out IsPoolEmpty() is overengineering: I would inline it.

        private T PopRandomElement()
        {
            if (PoolCount == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            int randomIndex = _random.Next(PoolCount);
            T item = _pool[randomIndex];
            _pool.RemoveAt(randomIndex);
            if (IsPoolEmpty()) _last = item;
            return item;
        }

You asked

  Is it efficient enough ?

Enough depends on your requirements, but the answer to the question "Is it as efficient as it could be?" is "No". _pool.RemoveAt has to shuffle along every later element in the list. In the worst case the random number generator will return a long string of 0. The standard solution is a swap.

        private T PopRandomElement()
        {
            System.Diagnostics.Debug.Assert(PoolCount > 0);
            int randomIndex = _random.Next(PoolCount);
            _last = _pool[randomIndex];
            _pool[randomIndex] = _pool[PoolCount - 1];
            _pool.RemoveAt(PoolCount - 1);
            return _last;
        }

This now takes constant time rather than linear time in the size of the pool.

        private void PopulatePool()
        {
            _pool.Clear();
            _pool.AddRange(_allItems);
            if (PoolCount > 1) // If _allItems is size 1 we don't remove from the pool : it would be empty
            {
                RemoveLastFromPool();
            }
        }

        private void RemoveLastFromPool()
        {
            _pool.Remove(_last);
            _last = default(T);
        }

Again, a linear removal could be replaced by a swap and a constant time removal.

But I wonder whether this actually meets the spec. Rather than removing _last from the pool entirely, didn't you just want to guarantee that it won't be the first element picked after repopulating the pool?

In fact, I'd be inclined to take this further. Suppose we refactor so that PoolCount is backed by its own field rather than _pool.Count, and that we have an additional field (or field-backed property) DelayCount.

If we replace _pool.RemoveAt(PoolCount - 1); with PoolCount--; then when PoolCount gets to 0, the pool contains the entire play list in reverse order of when they were last played. Now

PoolCount = _pool.Count;
DelayCount = N;
for (int i = 0; i < DelayCount; i++)
{
    var tmp = _pool[i];
    _pool[i] = _pool[PoolCount - DelayCount + i];
    _pool[PoolCount - DelayCount + i] = tmp;
}

swaps the first N elements up to the end. Adjust the PopRandomElement method a bit more:

        private T PopRandomElement()
        {
            System.Diagnostics.Debug.Assert(PoolCount > 0);
            System.Diagnostics.Debug.Assert(PoolCount > DelayCount);

            int randomIndex = _random.Next(PoolCount - DelayCount);
            var tmp = _pool[randomIndex];
            _pool[randomIndex] = _pool[PoolCount - 1];
            _pool[PoolCount - 1] = tmp;

            PoolCount--;
            if (DelayCount > 0) DelayCount--;

            return tmp;
        }

The effect is to guarantee that no track will repeat within N of the previous time it occurred. You can then make N settable with a public property or derive it from _pool.Count according to some hard-coded policy (e.g. a fixed percentage).

        public List<T> GetAllPossibleValues()
        {
            return new List<T>(_allItems);
        }

Why List<T>? In fact, is this method even useful?

        public void Add(T element)
        {
            _allItems.Add(element);
            PopulatePool();
        }

I don't see why it's desirable to populate the pool here. In addition to VisualMelon's observations, by populating the pool before reaching the end you lose the guarantee not to play the same track twice.


check if two elements exist in array with older browser support Currently I have this code

function foo(firstId, secondId){
    var boolOne = false;
    var boolTwo = false;

    for (var i = 0; i < arr.length; i++) {
        var current = arr[i];
        var id = current.id;

        if(firstId == id){
            boolOne = true;
        }

        if(secondId == id){
            boolTwo = true;
        }

        if(boolOne && boolTwo){
            break;
        }
    }

    if(boolOne && boolTwo){
        bar();
    } else {
        // throw error
    }
}

I want to check if two objects with the given parameter ids already exist in the array.

I put my code into one for-loop but I could also split the code into two loops and break on a match.

I know I could also use

var boolOne = arr.includes(item => item.id == firstId)

but I have to support the Internet Explorer 9+. Is there something that can be optimized?

From a short look

foo is a terrible name

If this is not the real name, then please do submit the real code

arr seems to be a global, bad practice
You don't need current, you could just go for var id = arr[i].id;
For older browsers, it is faster to cache arr.length instead of retrieving it every time
bar is a terrible name, I really hope you don't write production code like that
the call to bar should probably happen outside of that function

Given that, I would go for the below pseudo code:

function arrayHasBothObjects(list, id1, id2){
    var boolOne = false,
        boolTwo = false,
        size = list.length;

    for (var i = 0; i < size; i++) {
        var id = list[i].id;

        boolOne = boolOne || id == id1;
        boolTwo = boolTwo || id == id2;

        if(boolOne && boolTwo){
            return true;
        }
    }
    return false;
}


Validating json data for dynamic form I have a array-object which should look something like this and is used to create a form
const questions = [
  {
    condition_action: "selected",
    label: "What is your name?",
    question_type: "free_text",
    required: true,
  },
  {
    condition_action: "selected",
    label: "Where do you live?",
    question_options: [
      {
        label: "India",
      },
      {
        label: "china",
      },
      {
        label: "japan",
      },
    ],
    question_type: "single_answer",
    required: false,
  },
];

Now, When user is done creating the form, I have to validate the data and add a key name order in the above snippet (more below) to array-object (main array and question_options)
For validation, There are two conditions

Main array-object should have a label (if not throw error).
Question option should have at-least 1 item and the label inside it can't be empty

Basically, question_options is for multiple-select and single select drop down. So question_option should only contain value if question_type key in the above snippet is single_answer or multiple_answer
The backend api also require attribute order on the main question array and question_options array (yeah even though it's an array we could determine the order through index)
So this is the code I wrote
   const validateAndFormatdata = (questions) => {
    // we will change this to true if error exist and send it at return of this function
    let errorsExsist = false
    // we are formating data here, if error exist while validation, we change flag
    const formatedData = (questions || []).map((question, index) => {
      // delete all previous errors since we are iterating and we don't care about our previous errors
      if (Object.prototype.hasOwnProperty.call(question, "errors")) {
        delete question.errors
      }
      // There can be more than one thing wrong, hence using an array
      const newErrors = []
      // if label does not have value, add it it in errors array
      if (question.label === "") {
        newErrors.push(errorReasons.missingLabel)
      }
      if (
        question.question_type === "multiple_answer" ||
        question.question_type === "single_answer"
      ) {
        const questionOptions = _.filter(question.question_options, "label").map(
          (option, position) => {
            return {
              ...option,
              order: position
            }
          }
        )
        // if question optiond does not have single item, add it it in errors array
        if (questionOptions.length < 1) {
          newErrors.push(errorReasons.noOption)
        } else {
          question.question_options = [...questionOptions]
        }
      } else if (Object.prototype.hasOwnProperty.call(question, "question_options")) {
        // remove question otpions of question type isn't single or mult-text
        delete question.question_options
      }

      if (newErrors.length > 0) {
        errorsExsist = true
        question.errors = newErrors
      }
      return { ...question, order: index }
    })
    return {
      errorsExsist,
      data: formatedData
    }
  }

Question: I was wondering if someone can share review, optimisation and suggestions (including naming)?

I have made some changes and added comments for each change.
// add the default array here ------------↓
const validateAndFormatdata = (questions = []) => {
  let errorsExist = false, // <- typo in exist
      // in case you want to add new types
      optionTypes = new Set(["multiple_answer", "single_answer"]);

  // no need to check for || [] because default is added
  // remove the errors property here itself by using destructuring
  const formattedData = questions.map(({ errors, question_options, ...question }, index) => {
    // because of the destructuring, question is a new object.
    // So, will not mutate the original object
    question.order = index;

    const newErrors = []

    // checks if label exists and if it is an empty string
    if (!question.label) {
      newErrors.push(errorReasons.missingLabel)
    }

    if (optionTypes.has(question.question_type)) {
      const questionOptions = question_options
                                    .filter(q => q.label)
                                    .map((option, order) => ({ ...option, order }));

      // === 0 is much more clearer to read
      if (questionOptions.length === 0) {
        newErrors.push(errorReasons.noOption)
      } else {
        // no need for [...]. It's a new array
        question.question_options = questionOptions
      }
    }
    // no need for delete question.question_options because it is destructured

    if (newErrors.length > 0) {
      errorsExist = true
      question.errors = newErrors
    }

    return question;
  })

  return {
    errorsExist,
    data: formattedData
  }
}


Individual bit access in C Im not that good at C, so go easy on me, but I wanted to be able to have individual bit access in C without using a ton of functions to do bit manipulation on a uint8_t.  Tell me where I could improve upon it
#include <stdio.h>

#pragma pack(1)
union bit_array {
    struct {
        unsigned char b8:1, b7:1, b6:1, b5:1, b4:1, b3:1, b2:1, b1:1;
    } bits;
    unsigned char value;
};

int main() {
    // Creates char with binary value 11111111
    union bit_array test = { 1, 1, 1, 1, 1, 1, 1, 1 };

    // Displays 11111111 (255)
    printf("%u\n", test.value);

    // Sets 8th bit of binary value to 0
    // 11111111 (255) -> 11111110 (254)
    test.bits.b8 = 0;

    // Displays 11111110 (254)
    printf("%u\n", test.value);

    return 0;
}

This code is not portable.  The order of bit-fields within a word is completely compiler-dependent, so the test that appears to work on one platform may give completely different results on another.
You have avoided a common trap of using signed 1-bit fields (which can hold values 0 and -1) - these unsigned ones are much better.
I don't think there's any need for the bits member to be named - I would use an anonymous member there.
The numbering of bits is unconventional - most programmers would expect b0 to be the least-significant bit, and b7 the most significant (corresponding to 2⁰ and 2⁷ value of those bits in integers).
The test would be better if it were self-checking - return with non-zero status if any of the expectations are not met.  For example:
int main(void)
{
    int failures = 0;

    {
        /* First test */
        union bit_array test = { {1, 1, 1, 1, 1, 1, 1, 1} };
        if (test.value != 0xFF) {
            fprintf(stderr, "Test 1 expected 0xff, got %#04hhx\n", test.value);
            ++failures;
        }
    }

    {
        /* Second test */
        union bit_array test = { {1, 1, 1, 1, 1, 1, 1, 1} };
        test.bits.b8 = 0;
        if (test.value != 0xFE) {
            fprintf(stderr, "Test 2 expected 0xfe, got %#04hhx\n", test.value);
            ++failures;
        }
    }

    return failures != 0;
}

We need tests of the most-significant bit, and setting as well as resetting bits.  I'll leave that as an exercise.


Creating directory within Application Support, and preventing iCloud backup I'm using react native to build an iOS app, but have little to no experience in obj C or iOS development. The app I'm building has a bunch of content files that aren't user specific, will be downloaded from some CDN, and will (mostly) be behind a paywall. As I understand it, the best place for this would be somewhere within Application Support (the Cache dir doesn't seem to fit the bill because this is more about allowing users to download content for offline use than caching per se. Also, I think there's no guarantees about the lifetime of files in the Cache dir(?).). Also, I want to make sure that those content files aren't backed up to iCloud or anywhere else; and that they're not accessible by the user or other apps.

I have two questions:

Does that placement for the content fit with iOS recommendations/best practices?
Because I have little obj c/iOS experience, I'd be super grateful if you lovely people could cast your eyes over the code and review it?

// *** blah.h
#import <React/RCTBridgeModule.h>

@interface Blah : NSObject <RCTBridgeModule>
@end

// *** blah.m
#import "Blah.h"

@implementation Blah

RCT_EXPORT_MODULE();

RCT_EXPORT_METHOD(createAppDataPath:(NSString *)namespace findEventsWithResolver:(RCTPromiseResolveBlock)resolve rejecter:(RCTPromiseRejectBlock)reject){

    NSUInteger length = [namespace length];

    if (length < 1) {
        reject(@"namespace_invalid", @"Namespace param should be non-empty string", nil);
        return;
    }

    // ref: https://stackoverflow.com/a/17430820/1937302

    @try {

        NSString *appSupportDir = [NSSearchPathForDirectoriesInDomains(NSApplicationSupportDirectory, NSUserDomainMask, YES) lastObject];
        NSString *cacheDir = [appSupportDir stringByAppendingString: [NSString stringWithFormat:@"/%@", namespace]];

        // check for existence of directory:
        BOOL isDir;
        BOOL exists = [[NSFileManager defaultManager] fileExistsAtPath:cacheDir isDirectory:&isDir];

        if (!exists) {
            NSError *error = nil;
            // if not present, create it:
            BOOL result = [[NSFileManager defaultManager] createDirectoryAtPath:cacheDir withIntermediateDirectories:YES attributes:nil error:&error];
            if (!result) {
                reject(@"cant_create", @"Can't create directory", error);
                return;
            }
        } else if (!isDir) {
            reject(@"non_directory_path_exists", @"Path already exists as a non-directory", nil);
            return;
        }

        // now mark the directory as excluded from iCloud backups:
        NSURL *url = [NSURL fileURLWithPath:cacheDir];
        NSError *error = nil;
        BOOL result = [url setResourceValue:@YES forKey:NSURLIsExcludedFromBackupKey error:&error];

        if (!result) {
            reject(@"cant_exclude_from_backups", @"Can't exclude from backups", error);
            return;
        }

        resolve(cacheDir);

    }
    @catch(NSException *exception) {
        // TODO: capture information from exception and pass to rejection?
        // ref: https://stackoverflow.com/questions/43561531/how-to-convert-an-exception-into-an-nserror-object\
        // ref: https://stackoverflow.com/a/4654759/1937302
        // ref: https://developer.apple.com/documentation/foundation/nsexception
        reject(@"exception", @"An exception has occurred", nil);
    }
}

@end

File System Basics tells us:

  The contents of the Library directory (with the exception of the Caches subdirectory) are backed up by iTunes and iCloud.

And

  Put data cache files in the Library/Caches/ directory. Cache data can be used for any data that needs to persist longer than temporary data, but not as long as a support file. Generally speaking, the application does not require cache data to operate properly, but it can use cache data to improve performance. Examples of cache data include (but are not limited to) database cache files and transient, downloadable content. Note that the system may delete the Caches/ directory to free up disk space, so your app must be able to re-create or download these files as needed.

If this content is readily re-downloadable, Caches might actually be a reasonable idea. It makes your app a “good citizen”. If the user is running low on storage, it might be better to allow re-downloadable content to be removed rather than tempting the user, looking at their storage taken up by various apps, to contemplate removing your app because it’s taking up a lot of unreclaimable space.

If you want to ensure the content will never be deleted when the device runs low on space, then go ahead and put it in the Application Support directory, but manually exclude it from backups, like you have done.

Feel free to refer the iOS Storage Best Practices video (and that page has useful links).

You said:

  I think there's no guarantees about the lifetime of files in the Cache dir

Correct. In practice, when (a) the device runs low on space; and (b) your app is not running, the OS can purge this directory. It starts with apps that have been use less recently.

  Also, I want to make sure that those content files aren't backed up to iCloud or anywhere else; and that they're not accessible by the user or other apps.

By the way, whether it’s backed-up or not and whether it’s accessible by the user are two different questions. E.g., files in the Application Support directory are backed-up (other than, obviously, content of the Caches folder or those files explicitly designated to not be backed-up). But the contents are not visible to the user. Only user documents stored in Documents folder or iCloud Drive are visible to the end-user.

So, if your content is not readily re-downloadable, but you don’t want to expose them to the individual files, Application Support (without specifying NSURLIsExcludedFromBackupKey) might be prudent. It’s your call.


Compile-time wildcard pattern matching I was in need of a function that could check a string against a certain pattern at compile-time. The pattern can contain any of the commonly known wildcards: ?, * and +.

? - match any character.
* - match any sequence of characters, including the empty string.
+ - equal to ?*

I'm not sure how to test my code for errors, is there a set of patterns and strings that will determine (with 100% certainty) nothing is wrong with my code? If not, could any of you spare a moment and check my code for errors?

I've tested this code and it seems to work fine. Also, is this a good way of implementing compile-time functionality?

Compiled with: clang++ -std=c++11

Just as a help to more easily get into this code, I've tried to write the syntax in such a way to represent an if-elseif chain. The indentation shows the level of nesting.

constexpr int MatchPattern_Rec(const char* pattern, const char* text) {
    return *pattern == '\0' || *text == '\0' ? *pattern == *text :
            *pattern == '?' ? MatchPattern_Rec(pattern+1, text+1) :
            *pattern == '*' ?
                MatchPattern_Rec(pattern+1, text) ? 1 :
                MatchPattern_Rec(pattern, text+1) ? 1 :
                0 :
            *pattern == '+' ?
                MatchPattern_Rec(pattern+1, text+1) ? 1 :
                MatchPattern_Rec(pattern, text+1) ? 1 :
                0 :
            *pattern == *text ? MatchPattern_Rec(pattern+1, text+1) :
            0;
}

constexpr int MatchPattern(const char* pattern, const char* text) {
    return *pattern == '\0' ? 0 :
            *pattern == '*' && *(pattern+1) == '\0' && *text == '\0' ? 1 :
            MatchPattern_Rec(pattern, text);
}

Some side notes:

The code will only be run when compiling debug builds. Performance is the least of my worries.
The strings and patterns will be limited in size (max. 50 characters) and the patterns will have 5 wildcards at most. The stack should be big enough to handle that level of recursion.

I am not most experienced with C++ (java's my best language) but as far as I know, method names are supposed to be camelCase. MatchPattern_Rec should be matchPatternRec.

Also, why are you returning a 1 or a 0? Shouldn't you be returning a bool? (Again, correct me if I'm wrong)

The chain of ternary operators is very unreadable and messy, which causes easy bugs. You are also using ternary in places you can just use || and &&. Use if and switch statements to simplify:

constexpr bool matchPatternRec(const char* pattern, const char* text) {
    if (*pattern == '\0' || *text == '\0') {
        return *pattern == *text;
    }
    switch (*pattern) {
    case '?':
        return matchPatternRec(pattern + 1, text + 1);
    case '*':
        return matchPatternRec(pattern + 1, text) ||
                matchPatternRec(pattern, text + 1);
    case '+':
        return matchPatternRec(pattern + 1, text + 1) ||
                matchPatternRec(pattern, text + 1);
    default:
        return *pattern == *text && matchPatternRec(pattern + 1, text + 1);
    }
}

constexpr int matchPattern(const char* pattern, const char* text) {
    if (*pattern == '\0') {
        return false;
    }
    return (*pattern == '*' && *(pattern+1) == '\0' && *text == '\0') ||
            matchPatternRec(pattern, text);
}


Basic Brainfuck Interpreter in C I have written a small Brainfuck interpreter in C. More recent version hosted here.

I have found it very hard to test my interpreter because writing a program in Brainfuck is somewhat hard (or at least very tedious) and many snippets I found online either don't give output or do so very cryptically, so I don't know 100% sure if everything works as intended.

I have tested a few programs on it though, and that which I tested works.

Any criticism/advice would be very nice.

#include <stdio.h>

#define MEMSIZE 30000

int memory[MEMSIZE];
int instructions[MEMSIZE];

int memptr = 0;
int insptr = 0;

int isInstruction(char);
void runInstruction(char);

int main(int argc, char *argv[]) {
    // Open input file
    FILE *file = fopen(argv[1], "r");
    if (file == 0){
        printf("Error: Could not open source file\n");
        return 0;
    }

    // Read all instructions from input
    char c;
    int i = 0;
    int balance = 0; // Keeps track of `[` and `]` balance
    while ((c = fgetc(file)) != EOF && i < MEMSIZE){
        if(isInstruction(c)){
            instructions[i] = c;
            i++;
            if (c == '[')
                balance++;
            if (c == ']')
                balance--;
        }
    }

    // Close input file
    fclose(file);

    // Error if amount of instructions is more than permitted
    if (c != EOF && i >= MEMSIZE){
        printf("Error: cannot read more than 30000 instructions\n");
        return 0;
    }

    // Error if `[` and `]` aren't balanced
    if (balance != 0){
        printf("Error: `[` and `]` were not balanced\n");
        return 0;
    }

    // Run the program
    while(insptr < MEMSIZE && instructions[insptr] != 0){
        runInstruction(instructions[insptr]);
        insptr++;
    }
}

int isInstruction(char c) {
    if(c == '+' || c == '-' || c == '>' || c == '<' || c == '[' || c == ']' ||
       c == '.' || c == ','){
        return 1;
    } else {
        return 0;
    }
}

void runInstruction(char c) {
    switch(c){
    case '+':
        memory[memptr]++;
        break;
    case '-':
        memory[memptr]--;
        break;
    case '>':
        if (memptr < MEMSIZE - 1)
            memptr++;
        else
            memptr = 0;
        break;
    case '<':
        if (memptr > 0)
            memptr--;
        else
            memptr = MEMSIZE - 1;
        break;
    case '[':
        if (memory[memptr] == 0)
            // seek `]` forward
            while(instructions[insptr] != ']'){
                insptr++;
            }
        break;
    case ']':
        if (memory[memptr] != 0)
            // seek `[` backward
            while(instructions[insptr] != '['){
                insptr--;
            }
        break;
    case '.':
        putchar(memory[memptr]);
        break;
    case ',':
        memory[memptr] = getchar();
        break;
    default:
        printf("Error: Encountered unknown instruction `%c`\n",c);
    }
}

Use NULL for null pointers

NULL conveys your intention to use a pointer better than 0:

if (file == NULL) { ... }

As a bonus, in C the macro NULL typically expands to something like (void*)0; if you have warnings for potentially unsafe type conversions enabled (-Wconversion for GCC), the compiler will notify you, if you try to assign 0 to a pointer or NULL to an integer, which helps to find potential errors.

Use puts when you don't use string formatting

printf("Error: Could not open source file\n");

could just as well be

puts("Error: Could not open source file");

While printf is great for formatted output, the look for formatting specifiers carries a computational overhead that puts doesn't have. Some compilers (like GCC) will perform that optimization automatically for you, if you use a format string literal without format specifiers.

Checking whether a characters is in a set of characters

In isInstruction(char), instead of using a series of disjoint (joint with the || operator) equality comparisons, you could much better express your intent and the source character set with strchr:

return strchr("+-><[].,", c) != NULL;

A possible improvements might be:

const static char brainfuck_alphabet[] = {'+', '-', '>', '<', '[', ']', '.', ','};
return memchr(brainfuck_alphabet, c, sizeof(brainfuck_alphabet));

The improvements lies in the fact that the algorithm of memchr can make an assumption about the size of the memory region to check while strchr cannot. This could lead to a performance improvement.

Use bool for boolean values

The header <stdbool.h> declares boolean-like types. You can use them to express your intention for a boolean return value of isInstruction():

bool isInstruction(char c) { ... }

Don't repeat yourself

While you generally did will to adhere to that principle, I want to point out one small spot that could use improvement:

printf("Error: cannot read more than 30000 instructions\n");

could be

printf("Error: cannot read more than %d instructions\n", MEMSIZE);

That way the error message would reflect the actual buffer size in case MEMSIZE was redefined. Since the argument list of printf is variadic and doesn't carry type information, it would be better yet to not make assumptions on the width of the integer type of MEMSIZE. What if someone defined MEMSIZE to be larger than MAX_INT? The best course of action would be to force MEMSIZE into the type size_t (more about that later).

printf("Error: cannot read more than %zu instructions\n", (size_t)(MEMSIZE));

Data types

You only ever store chars in instructions, so its type could just as well be:

char instructions[…];

On all 32- and 64-bit platforms you just saved 3*MEMSIZE bytes (which you could use to increase MEMSIZE again if that is a concern).
memptr, insptr and i are indexes of plain arrays. Therefore they should have type size_t, which is the type meant to reflect the size or position of things in memory.

Make the code flow of branches based on mutually exclusive conditions mutually exclusive

In the above code the conditions c == '[' and c == ']' cannot both be true since c isn't altered between them. To make this obvious to the reader and the compiler (though a good one should find that optimization itself), you should use mutually exclusive if … else if … statements:

        if (c == '[')
            balance++;
        else if (c == ']')
            balance--;

Exit with an error status in case of an error

Programs may convey information in their exit status. By convention the status 0 means “no error, everything performed according to your instructions”. Every other status value usually refers to an error condition but there is no general convention on what each value means. One attempt to conventionalize them can be found in the sysexits.h header. You could use it like this in your program:

if (file == NULL) {
    // ...
    return EX_NOINPUT;
}

if (balance < 0) {
    // ...
    return EX_DATAERR;
}

if (c != EOF && i >= MEMSIZE) {
    // ...
    return EX_SOFTWARE;
}

In a similar fashion you could return an error from runInstruction(), but we already know that we didn't accept any illegal instructions.

Print error messages on stderr

printf and puts write their data to stdout, the standard output stream, but you're also writing program output to stdout via putchar. To avoid mixing program output and error messages, you should write the latter to stderr instead:

fprintf(stderr, ...);
fputs(..., stderr);

Be aware that fputs doesn't append a new-line character like puts.

Print operating system error messages to provide hints to the user

Like many library functions relying on system calls, fopen sets the global errno variable to report the type of error. You can use functions like strerror or perror to decode the value of errno into a human-readable, localized(!) error message:

if (file == NULL) {
    perror("Could not open source file");
    // ...
}

Respect the principle of locality, avoid global variables

Global variables clutter the name space and make it more difficult to follow the flow of the program. They also prevent a method or set of methods from being reentrant, a property that allows them to be executed concurrently. (This matters not just for multi-threaded programs, but also if you wanted to, say, interpret multiple Brainfuck programs one instructions at a time in a round-robin fashion to see which program terminates first.)

One way to achieve this is to move more data and logic into the method:

int main(int argc, char *argv[])
{
    // ...
    char instructions[MEMSIZE];
    // ...
    runInstructions(instructions, i);

    return EX_OK;
}

void runInstructions(const char *const instructions, size_t instruction_count)
{
    size_t memptr = 0;
    size_t insptr = 0;
    int memory[MEMSIZE];

    while (insptr < instruction_count) {
        switch(instructions[insptr]) {
            // ...
        }
    }
}

You could also use an instruction pointer instead of an instruction index:

void runInstructions(const char *const instructions, size_t instruction_count)
{
    size_t memptr = 0;
    const char *insptr = instructions;
    const char *const instructions_end = instructions + instruction_count;
    int memory[MEMSIZE];

    while (insptr < instructions_end) {
        switch(*insptr) {
        // ...
        case '[':
            if (memory[memptr] == 0)
                // seek `]` forward
                while (*insptr != ']')
                    insptr++;
            break;

        case ']':
            if (memory[memptr] != 0)
                    // seek `[` backward
                    while(*insptr != '[')
                        insptr--;
            break;
        // ...
        }
    }
}

Use library functions where possible

Library functions unburden you from writing your own code. They're (usually) less likely to contain errors than hand-rolled solutions and the library authors may have included arcane, platform-specific performance optimizations in them.

To find the next closing bracket instruction you could write:

    case '[':
        if (memory[memptr] == 0) {
            // seek `]` forward
            insptr = memchr(insptr + 1, ']', (size_t)(instructions_end - insptr - 1));
        }
        break;

To find the last opening bracket you could write:

    case ']':
        if (memory[memptr] != 0) {
            // seek `[` backward
            insptr = memrchr(instructions, '[', (size_t)(insptr - instructions - 1));
        }
        break;

Avoid undefined behaviour

You can't be sure that argv[1] is defined. If it isn't its value may have NULL or garbage content. Check the value of argc first and print an appropriate error message if it's too small:

if (argc < 2) {
    fputs("Error: No source file specified.\n", stderr);
    return EX_USAGE;
}

If the Brainfuck program happens to have a branch depth greater than INT_MAX, the balance variable would overflow. It typically overflows to the value -1, which would be caught with a subsequent balance < 0 check, but in C signed integer overflow results in undefined behaviour. That means the compiler may assume that overflow never happens and optimize the negative balance check to always be false, which would leave your program in a weird state.

If you decide to care about that (INT_MAX+1 is 2^31 which would require a program of at least 2 GiB, all [, to trigger the bug on modern architectures after all), there are basically two approaches:

Use ssize_t instead of int. ssize_t covers a branching depth of almost (half) as many levels as the address space has bytes. It's quasi-impossible to generate and load a program of that size into the memory of your interpreter anyway, so you could consider your bases covered.
Check for overflow before increasing balance:

    if (c == '[') {
        if (balance == INT_MAX) {
            fprintf(stderr, "Error: Cannot handle branches deeper than %d levels.\n", INT_MAX);
            return EX_DATAERR;
        }
        balance++;
    }

Provide some debugging info to the programmer using your interpreter

It might be helpful for the user to know where in the program a parser error occurred, so you should keep track of the amount of bytes read so far:

size_t i = 0;
while (i < MEMSIZE && (c = fgetc(file)) != EOF) {
    read++;
    if(isInstruction(c)) { ... }
}

You can now report that value in parser error messages like so:

fprintf(stderr, "Error:%zu: Cannot handle branches deeper than %d levels.\n", read, INT_MAX);
fprintf(stderr, "Error:%zu: Encountered `]` before matching `[`\n", read);
fprintf(stderr, "Error:%zu: cannot read more than %zu instructions\n", (size_t)(MEMSIZE), read + 1);


Comma Code - Automate the Boring Stuff with Python Below is my code for the Comma Code problem from Chapter 4 of Automate the Boring Stuff with Python. Is there anything I can do to make it cleaner?

Comma Code
Say you have a list value like this:
spam = ['apples', 'bananas', 'tofu', 'cats']
Write a function that takes a list of values as an argument and returns a string with all the items separated by a comma and a space, with 'and' inserted before the last item. For example, passing the previous spam list to the function would return 'apples, bananas, tofu, and cats'. But your function should be able to work with any list passed to it.
The output of this program could look something like this:
apples, bananas, tofu, and cats

import sys

spam = ['apples', 'bananas', 'tofu', 'cats']

def print_list(list):
    for item in list:
        if len(list) == 1:
           print(list[0])
        elif item != list[-1]:
            print(item + ', ', end='')
        else:
            print('and ' + list[-1])

print_list(spam)

You've got an odd bug with your code.

Given the 8th menu item from the greasy spoon café:

spam = ["Spam", "Spam", "Spam", "egg", "Spam"]

You will get:

  and Spam
  and Spam
  and Spam
  egg, and Spam

since you are not testing whether you are at the last item in your list, but rather if the current item is the same as the last item in the list.

Testing for a length 1 list should not be done inside the loop of all items; it should be done exactly once, outside the loop.  Ie (but still with the above bug):

if len(list) == 1:    # Test outside of loop
   print(list[0])
else:
    for item in list:
        if item != list[-1]:
            print(item + ', ', end='')
        else:
            print('and ' + list[-1])

Want you really want to do is print all but the last item in the list one way, and the last item a different way:

# If there are more than 1 items in the list...
if len(list) > 1:

    # Print all but the last item, with a comma & space after each
    for item in list[:-1]:
        print(item + ', ', end='')

    # with "and " printed at the very end, just before ...
    print("and ", end='')

# print the last (or only) item in the list.
print(list[-1])

although this still assumes at least one item in the list.

Alternately, you could join() all but the last item, and then add ", and " along with the final item.

msg = list[-1]
if len(list) > 1:
    msg = ", ".join(list[:-1]) + ", and " + msg
print(msg)

You are doing import sys, but not using sys anywhere.  You can remove the import.


Project Euler Problem 10 Project Euler problem 10 is to find the sum of all primes less than 2 million. I have written a program that does this, and it works, but it takes an excruciatingly long amount of time. What I'm asking is if there is any way I could optimize this to make it run much faster.

I wrote it in an app on my iPad called Pythonista.

def checkPrime(number):
    if number == 2:
        return True

    if number < 2:
        return False

    if number % 2 == 0:
        return False

    for i in range(3, (number**1/2)-1, 2):
        if number % i == 0:
            return False

    return True

primes = [i for i in range(10000) if checkPrime(i)]
print sum(primes)

This problem can be solved much faster with a Sieve of Eratosthenes algorithm, especially since you need every prime between 2 and n for you to sum them up.
However, there are a few optimizations you could make to your particular algorithm.

Dynamic Programming
Your code preforms some redundant calculations. For example, once you've checked if n % 2 is zero, you know n % 4, n % 6... are also zero. To avoid these calculations you could instead divide by only the prime numbers up to and including √n:
primes = [2] #define your array of prime numbers

def checkPrime(number):
    if number < primes[0]:
        return False

    for p in primes: #only iterate through the primes
        if p > number**0.5:
            break; #no need to keep going
        if number % p == 0:
            return False

    primes.append(number);
    return True

primes = [i for i in range(10) if checkPrime(i)]
print sum(primes)


System for tracking stock information Background: I'm designing a system (VB/WinForms) that uses a database(MS SQL Server 2008 R2) to track people, their stock account #'s, which stocks they are investing in, and the payout of those stocks.

Basically, just reading/writing to the database and some time-elapsed functionality. (One payout per year, etc.) I have forms where users are entering employees to the database, adding accounts, etc.

My issue: I never truly understood OOP, however I am getting more involved with it now, and while my program works, I want the code to be better (look better, be more flexible, utilize classes/objects more, etc.)

That being said, how can I make this code more Objected-Oriented?

Note: I am also utilizing ReSharper, however that can only do so much and I don't want to have to rely on a tool for the rest of my career.

Note: This project utilizes an encryption class.

Imports System.Data.SqlClient
Public Class EmployeeUpdateFrm
    Private _id As String
    Dim _seqId As Integer

Private Sub Load(sender As Object, e As EventArgs) Handles MyBase.Load

    Dim conn1 As New SqlConnection("Data Source=SQLTEST_HR,4000\SQLEXPRESS;Integrated Security=True")

    Dim qry As String = "SELECT CMPNY_SEQ_ID, CMPNY_NM FROM CMPNY"

    Dim ds1 As New DataSet()
    Using da As New SqlDataAdapter(qry, conn1)
        'fill data set 1 for combobox
        da.Fill(ds1)
    End Using

    With CompanyCbx
        'what the user sees
        .DisplayMember = "CMPNY_NM"
        'value behind each display member
        .ValueMember = "CMPNY_SEQ_ID"
        .DataSource = ds1.Tables(0)
        .SelectedIndex = 0
    End With
    'close connection
    conn1.Close()
    Dim index As Integer = 1
    'The vertical spacing between rows of controls relative to the textboxes.
    Dim yMargin As Integer = 10
    Dim query As String
    'Create a new instance of the encryption class.
    Dim strKey As String = "Key1"
    Dim Crypto As ClsCrypt
    Crypto = New ClsCrypt(strKey)

    Dim eID As String = Crypto.EncryptData(_id)

    query = "SELECT EMPL_SEQ_ID, EMPL_ID, EMPL_LAST_NM, EMPL_FIRST_NM, EMPL_PREFRD_NM, EMPL_BIRTH_DT, EMPL_MAIL_STN_CD,"
    query &= "                 EMPL_ADDR1_TXT, EMPL_ADDR2_TXT, EMPL_CITY_NM, EMPL_STATE_CD, EMPL_POSTL_CD, EMPL_PYRL_CD, "
    query &= "                          EMPL_FILE_NO, EMPL_SPRTN_DT, CMPNY_SEQ_ID, EMPL_ACTV_IND, BEG_DT, END_DT "
    query &= "  FROM EMPL"
    query &= "  WHERE EMPL_ID = @ID; "

    'New DataSet object to hold employee records.
    Using ds As New DataSet()
        Using conn As New SqlConnection("Data Source=SQLTEST_HR,4000\SQLEXPRESS;Integrated Security=True")
            Using da As New SqlDataAdapter()
                da.SelectCommand = New SqlCommand(query, conn)
                da.SelectCommand.Parameters.Add(New SqlParameter("@ID", eID))
                da.Fill(ds)
            End Using
        End Using

        If CompanyCbx.Items.Count > 0 Then
            CompanyCbx.SelectedIndex = ds.Tables(0).Rows(0).Item(15).ToString
        End If

        Try
            For i As Integer = 0 To ds.Tables(0).Rows.Count - 1
                For z As Integer = 0 To ds.Tables(0).Columns.Count - 1
                    If z <> 0 Then
                        'Decrypt all rows and columns
                        ds.Tables(0).Rows(i)(z) = Crypto.DecryptData(ds.Tables(0).Rows(i)(z))
                    End If
                Next
            Next
        Catch ex As Exception
            MsgBox(ex.ToString)
        End Try

I also ask (without being opinionated), with programs like this (fairly small, read/write to database with no extraordinary functionality) how flexible is the coding? By that I mean, I don't really see how I could use something like:

Dim Person as New Person()

Class Person
Public firstName as String
Public lastName as String

etc.

Especially because I utilize DataSets so heavily.

If you want to learn how to use classes, the best approach is to use them while building a small program. I suggest you do create a Person class and that you stop using dataset. This will be a great learnign experience.

Using numbers instead of const or strings can create a mantenance problem. At a glance, it's not easy to know what 15 mean.

ds.Tables(0).Rows(0).Item(15)

Remove all the database query from the UI. It'll also make the code more readable and you'll be able to reuse the functions if needed. You should have the connection string at one place.

Public Class EmployeeUpdateFrm

    Private Sub Load(sender As Object, e As EventArgs) Handles MyBase.Load

        LoadDropDown()

        ' ...

    End Sub

    Sub LoadDropDown()

        Dim companies As List(Of Company)

        companies = DAL.GetCompanies()

        With CompanyCbx
            'what the user sees
            .DisplayMember = "Name"
            'value behind each display member
            .ValueMember = "Id"
            .DataSource = companies
            .SelectedIndex = 0
        End With

    End Sub

End Class

Public Class DAL

    Private Shared _connectionString As String = "Data Source=SQLTEST_HR,4000\SQLEXPRESS;Integrated Security=True"

    Public Shared Function GetCompanies() As List(Of Company)
       ' ...
    End Function

End Class

Public Class Company

    Public Property Id As Integer
    Public Property Name As String

End Class


Largest Palindrome efficiency I have written an algorithm to find the largest palindrome under a given number, but I am sure my code loses efficiency by creating new arrays in every pass. I am currently learning about efficiency so I have the following question: Can anyone suggest a more efficient (faster) approach and explain why this approach is more efficient?

int number = 0;
int palindrome = 0;

for (int i = 1; i < 999999; i++)
{
    number = i;
    string s = number.ToString();
    char[] charArray = s.ToCharArray();
    char[] charArrayReversed = new char[charArray.Length];
    Array.Copy(charArray, charArrayReversed, charArray.Length);

    Array.Reverse(charArrayReversed);
    bool isEqual = Enumerable.SequenceEqual(charArray, charArrayReversed);
    if (isEqual)
        palindrome = number;
}

Console.Write(palindrome);
Console.ReadLine();

I'm sure there are other ways to improve it but here are a few quick points:

Start from the end and work your way back, that way once you've found one palindrome you're done!
You only have to check half of the digits for equality.
We can shave off some time by avoiding Array.Copy / Array.Reverse

Something like this:

var limit = ?
for (int i = limit; i > 0; i--)
{
    number = i;
    string s = number.ToString();
    char[] charArray = s.ToCharArray();

    bool isEqual = true;
    int halfLength = charArray.Length / 2; // will skip the middle digit
    int max = charArray.Length - 1;
    for(int j = 0; j < halfLength; j++)
    {
        if(charArray [j] != charArray[max - j])
        {
            isEqual = false;
            break;
        }
    }

    if (isEqual)
    {
        palindrome = number;
        break; // stop evaluating here
    }
}


C++ check if Palindrome Just did this simple application to check whether a string is a palindrome or not

#include <iostream>
#include <string>

using namespace std;

void main()
{
  string str;
  cout << "Enter a string: "; getline(cin, str);
  cout << "Your string is: "; cout << str << endl;
  cout << "The reverse of the string is: ";
  int counter = 0;
  for (int reverseIdx = str.size() - 1, forwardIdx = 0; reverseIdx >= 0 &&
  forwardIdx < str.size(); reverseIdx--, forwardIdx++)
  {
    cout << str[reverseIdx];
    if (str[reverseIdx] == str[forwardIdx])
    {
      counter++;
    }
  }
  cout << endl;
  if (counter == str.size())
  {
    cout << "The string is a Palindrome!" << endl;
  }
  else
  {
    cout << "The string is not a Palindrome." << endl;
  }
}

I'm getting a string from the user, then printing out the same string (I know it's not needed in such small programs). Then using a for loop to check if every character when reversed is equal to the same character when read normally.

Then using a counter variable I am checking if it's equal to the string size, if it's then it's palindrome.

Advice 1: getting the job done the C++ way

You can check whether the input string is a palindrome in one line:

bool is_palindrome(std::string& text) {
    return std::equal(text.cbegin(), text.cend(), text.rbegin());
}

For Incomputable has spoken: You can make the above run in the worst case faster by the factor of two:

bool is_palindrome(std::string& text) {
    return std::equal(text.cbegin(),
                      std::prev(text.cend(), text.length() / 2),
                      text.rbegin());
}

For Deduplicator has spoken: In is_palindrome, change std::string& to std::string const&; this will guarantee that the input string is not modified.

Advice 2

Whatever you implementation of the palindrome checker is, have a dedicated method that does not output the result to std::cout, but rather returns a boolean indicating whether the input string is a palindrome or not.

Advice 3

void main() does not compile on modern Xcode; change to int main().

Advice 4

Please avoid

using namespace std;

since it pollutes your namespace by importing quite a lot of identifiers/type names.

Advice 5

cout << "Your string is: "; cout << str << endl;

You can write:

cout << "Your string is: " << str << endl;

Alternative implementation

I had this in mind:

#include <algorithm>
#include <iostream>
#include <string>

bool is_palindrome(std::string& text) {
    return std::equal(text.cbegin(), text.cend(), text.rbegin());
}

using std::cin;
using std::cout;
using std::getline;
using std::string;

int main()
{
    string str;
    cout << "Enter a string: ";
    getline(cin, str);
    cout << "Your string is: " << str << "\n";
    cout << "Palindrome: " << std::boolalpha << is_palindrome(str) << "\n";
}


Splitting std::string based on delimiter using only find and substr I have been playing around with these two functions for a bit, dunno if this is practical though. I have only been learning C++ for a couple of days, coming from a Java background.

There we had a function that does this for us; I tried making something similar.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<string>parse(string test, string Deli);
int main()
{

vector<string> x = parse("random text to test splitting apart ", " ");
// note , the deliminator have to be after the text not before it.
for (string &e : x)
{
    cout << e << endl;
}
return 0;
}
vector<string>parse(string test, string Deli) {
    int count = 0; int token = 0;
    vector<string>parsed;
    for (size_t i = 0; i <= count; i++)
    {
        string x = (test.substr(token, test.find(Deli, token)-token));
        parsed.push_back(x);
        token += test.find(Deli, token +1) - (token-1);
        test.find(Deli, token) != std::string::npos ? count++ : count;
    }
    return parsed;
}

Bug

If the original string doesn't have trailing delimiter, the code leaves out the last token.

Unqualified calls

Unqualified call is any function call which doesn't have preceding ::. People oppose using namespace std;. In my opinion, it is not as much of a problem if done carefully (for small programs or at function/block scope). What is dangerous though, is unqualified call. It can be very evil. Anyway, my recommendation is to just type std:: unless you want to have a fallback into standard library functions at the current scope. I know this sounds confusing, but may be as time passes by it will become clearer.

Formatting

There are formatting conventions many people use to make code readable among themselves. Sometimes it helps to understand control flow, templates, pointers, etc. I don't have any strong opinions on any particular one though, as long as it is consistent. Formatting the code in question used is rather unusual. I use snake_case, for everything except template parameter names and concepts. The more common version though is CamelCase for type names and camelCase for variable names, functions. ALL_CAPS are reserved for macros, as they're quite evil.

Accepting by value

Although sometimes it makes sense, in the case shown in question, it doesn't. When something is used for read-only purposes, pass by const T&. In this case, it might even make sense to take by std::string_view. At the moment the code copies the arguments, which may be very costly if strings are big.

Peculiar way of looping

count and i are at the moment sort of a flag, either true or false (it takes many values, but squashing i and count into one would produce the flag). It would be better to loop until find returns npos.

size_t

For indexing, size_t is usually used. Some people prefer ptrdiff_t. The advantage they have over int is that they will as big as indexable memory is (though max of ptrdiff_t might be less that max of size_t). int might not be big enough in some cases.

Small stuff

Use const auto& if looping in read only mode (for (const auto& e: x)).

return 0 is redundant.

Don't use std::endl unless immediate printing is necessary. An example of immediate printing can be real-time games, where users need to see output immediately.

Don't put extra () anywhere unless compiler doesn't understand you. Most of the time they are redundant, in worst cases they produce bugs and dangling references.

My approach

I'm a lover of standard library algorithms. Here is a good  talk to give a starter if you know basic algorithms (Disclaimer: I'm not familiar with the speaker, though ACCU is a good conference).

Lets develop the algorithm first.

prev_pos <- start of the string
next_pos <- next delimiter location in string
if next_pos is end of the string, go to 7
append {prev_pos, next_pos} to results
increase prev_pos by next_pos + delimiter.size().
Go to 2.
if prev_pos is not end of the string, add the remaining portion of the string to results.

(This is a very bad parody to Knuth's style)

From the algorithm, it is already clear that the variables prev_pos and next_pos are not well named. I left it out as example, to demonstrate when variables could be given a good names. Good algorithm is complemented by good names, and sometimes staggered by bad ones.

Now the implementation. When starting out with a language, it is very hard to find direct equivalent to actions in the algorithm. Fortunately, C++ allows coming close to it, though building blocks are in the standard library already. I recommend using some good, up-to-date documentation. I use cppreference.com .

The first step is understanding iterators. I don't really have a good reference for them, but iterators are the glue that binds containers and algorithms in C++. For now, let's assume it is a pointer into the string. Every standard library container has begin() and end(). The former is iterator to the beginning of container, and the latter is one past the end iterator. In case of "word", begin would point to w, and end to whatever is after d.

The algorithm that searches for the occurrence of a sequence in a bigger sequence is std::search(). If "very long string" is std::searched for "string", it will return iterator pointing to s.

std::vector has emplace_back(), which constructs element in-place. It takes whatever element type's constructor takes (in this case std::string). In the code above, a string is created after substring, and only then copied into result. Using iterator pair will eliminate the unnecessary copies.

Code

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>
#include <string_view>

std::vector<std::string> split_string(std::string_view content, std::string_view delimeter)
{
    std::vector<std::string> result;
    auto prev_pos = content.begin();
    auto next_pos = std::search(prev_pos, content.end(),
                               delimeter.begin(), delimeter.end());
    while (next_pos != content.end())
    {
        result.emplace_back(prev_pos, next_pos);
        prev_pos = next_pos + delimeter.size();
        next_pos = std::search(prev_pos, content.end(),
                               delimeter.begin(), delimeter.end());
    }

    if (prev_pos != content.end())
    {
        result.emplace_back(prev_pos, content.end());
    }
    return result;
}

int main()
{
    auto tokens = split_string("just a bunch of words", " ");

    std::copy(tokens.begin(), tokens.end(),
             std::ostream_iterator<std::string>{std::cout, ", "});
}

Demo.

Printing is done by copying the results into std::cout. Not everybody likes this, so just looping

for (const auto& token: tokens)

will do too.

Some readers might ask a question "Why not return std::vector<std::string_view>"? The answer is that the views might dangle if the conversion is done from temporary string. A good example would be

split_string(std::string{"string to split"}, "a");

The views would point to wherever the temporary is allocated, but after the function ends, the resulting views will dangle. One way to deal with this would be to create a function which copies, and name it split_string_copy, and let the current one to return views (hoping that IDE will put both version close, so developer would see the right one).

Yet another approach

Evangelists of iostream library might come up with a solution that modifies current locale, namely std::ctype<char>. Although it is really good at parsing simple CSV files, in a place where the function gets called multiple times it might be inefficient. Maybe in stateful cases it might prove as a better alternative.


Searching in a lock-free ordered single-linked list The code below represents a lock-free ordered single-linked list, and is a modification of the algorithm proposed in this doc.

How can I improve speed of searching (lookingup) in the list maintaining lock-free capability? Any suggestions, code modifications, examples, maybe other lock-free data structures?

typedef uintptr_t               marked_ptr_t;
#define PTR_OF(x)               ((Node*)(x))
#define CONSTRUCT(ptr)          ((uintptr_t)ptr)
#define CAS(ADDR, OLDV, NEWV)   __sync_val_compare_and_swap((ADDR), (OLDV), (NEWV))
#define INCR(ADDR, INCVAL)      __sync_fetch_and_add((ADDR), (INCVAL))

typedef struct
{
    void            *value;
    uint64_t        key;
    marked_ptr_t    next;
} Node;

typedef struct
{
    marked_ptr_t    bucket;
    uint32_t        size;
} LF_List;

void *lf_list_get(LF_List*, uint64_t);

void *lf_list_put_if_absent(LF_List*, uint64_t, void*);

int lf_list_remove(LF_List*, uint64_t);

void* lf_list_find(marked_ptr_t* head, uint64_t key, marked_ptr_t** prev, marked_ptr_t* cur, marked_ptr_t* last)
{
    marked_ptr_t* tp_prev;
    marked_ptr_t tp_cur, tp_last;
    marked_ptr_t* tp_next;

    uint64_t cur_key;
    void* cur_value;

    tp_prev = head;
    tp_cur  = *head;
    tp_last = (marked_ptr_t)NULL;

    while(1)
    {
        if (PTR_OF(tp_cur) == NULL)
        {
            if(prev){*prev = tp_prev;};
            if(cur){*cur = tp_cur;};
            if(last){*last = tp_last;};

            return NULL;
        }

        tp_next = &PTR_OF(tp_cur)->next;

        cur_key = PTR_OF(tp_cur)->key;
        cur_value = PTR_OF(tp_cur)->value;

        if (key >= cur_key)
        {
            if(prev){*prev = tp_prev;};
            if(cur){*cur = tp_cur;};
            if(last){*last = tp_last;};

            return key == cur_key ? cur_value : NULL;
        }

        tp_last = tp_cur;
        tp_prev = tp_next;
        tp_cur = *tp_next;
    }
}

void* lf_list_get(LF_List* table, uint64_t key)
{
    return lf_list_find(&table->bucket, key, NULL, NULL, NULL);
}

void* lf_list_put_if_absent(LF_List* table, uint64_t key, void* value)
{
    marked_ptr_t* prev;
    marked_ptr_t cur, last;
    marked_ptr_t new_node;

    while(1)
    {
        if(lf_list_find(&table->bucket, key, &prev, &cur, &last) != NULL)
        {
            return PTR_OF(cur)->value;
        }

        new_node = CONSTRUCT(calloc(1, sizeof(Node)));

        PTR_OF(new_node)->value = value;
        PTR_OF(new_node)->key = key;

        PTR_OF(new_node)->next = *prev;

        if(CAS(prev, cur, new_node) == cur)
        {

            INCR(&table->size, 1);
            break;
        } else {
            free(PTR_OF(new_node));
            continue;
        }
    }
    return NULL;
}

int lf_list_remove(LF_List* table, uint64_t key)
{
    marked_ptr_t cur, last;
    marked_ptr_t *prev;

    while(1)
    {
        if(lf_list_find(&table->bucket, key, &prev, &cur, &last) == NULL)
        {
            return 0;
        }

        if (CAS(prev, cur, PTR_OF(cur)->next) == cur) {

            free(PTR_OF(cur));
            INCR(&table->size, -1);
            return 1;
        } else {
            continue;
        }
    }

    return 0;
}

Lockless list not threadsafe
I was able to break your list with a simple program:
LF_List list = {0};

void *threadFunc(void *arg)
{
    uint64_t key = (uintptr_t) arg;
    int i;

    for (i=0;i<100000;i++) {
        lf_list_put_if_absent(&list, key, (void *) 1);
        if (lf_list_remove(&list, key) == 0) {
            printf("ERROR\n");
            exit(1);
        }
    }
    return NULL;
}

int main(void)
{
    pthread_t t1, t2;
    pthread_create(&t1, 0, threadFunc, (void *) 9);
    pthread_create(&t2, 0, threadFunc, (void *) 8);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
}

When I ran this program, one of three things happened:

The program terminated (no errors).
The program printed ERROR, meaning that something went wrong with a put or remove.
The program never terminated, indicating a cycle in the list was created.

I was also able to cause a segmentation violation by modifying lf_list_remove() to write 0xffffffff to the next pointer of a node just before freeing it:
    if (CAS(prev, cur, PTR_OF(cur)->next) == cur) {
        // Once a pointer is freed, its memory could be trashed.
        // Simulate this by writing an invalid address to cur->next.
        PTR_OF(cur)->next = 0xffffffff;
        free(PTR_OF(cur));
        INCR(&table->size, -1);
        return 1;
    } else {
        continue;
    }

I was also able to cause the program to crash by specifically adding some strategic sleep() calls to cause two threads to perform a specific sequence of events, but that code is too lengthy to list here unless you really want to see it.
Basically, what it all boils down to is that when one thread is freeing a node, the other thread can access the freed node because there is nothing to stop it from doing so.  The original code in the research paper used marking bits to prevent this from happening, but those marking bits have been removed from this implementation.


Finding the longest Collatz sequence cycle I wrote a program to calculate Collatz sequences for initial numbers between 1 and a given integer i, then find the one with the largest cycle length.  My code is pretty fast, but I want to increase the speed more.  Please have a look at my code and if there are any changes to made in my code to make it faster.

import java.util.Scanner;
class asgn {
public static void main(String args[]){
long i,j,n,max=0, pos=0, x,y;
long count=0;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the positive integer:");
while(sc.hasNextLong())
{x=System.currentTimeMillis();
 i= sc.nextLong();
long arr[] = new long [50000000];

 for(j=1;j<=i;j++)
{
n=j;
count = 0;
while(n!=1)
{
if(n<50000000)
{if(arr[(int)(n-1)]!=0)
{ count=count+arr[(int)(n-1)];
break;
}}

if(n%2==0)
{n=n/2;
count++;
}
else
{
n = (3*n)+1;
count++;
}
}
if(j<50000000)
arr[(int)(j-1)]=count;
if(count>max)
{max=count; pos=j;}
count=0;
}
y=System.currentTimeMillis();

System.out.println("Maximum cycle length occurs at "+pos+" and the number of steps     involved     "+max+"\n Total time taken is "+(y-x)+"milliseconds");
break;}}}

Formatting
USE PROPER INDENTATION - Please!
If you're using Eclipse, press Ctrl + Shift + F.
If you're using Netbeans or IntelliJ, press Alt + Shift + F.
If you're not using any IDE, start doing so!

Braces
Once your code is properly formatted it can be seen that you're not using braces here:
if (j < 50000000)
    arr[(int) (j - 1)] = count;

It is especially important to use braces when you're code's not formatted properly, as it is easy to accidentally add an extra statement inside the if, which would cause unexpected results.
if (j < 50000000) {
    arr[(int) (j - 1)] = count;
}

Close Scanner
Scanners should be closed when they have been used. sc.close(); at the end of your program will take care of that.

Unnecessary outer while
Your outermost while "loop" is only executed once because there is a break; at the end of it. This could be an if instead and the break; at the end removed.

Use the length of the array
if (j < 50000000) {

and
if (n < 50000000) {

Should instead be:
if (j < arr.length) {

and
if (n < arr.length) {

respectively.

Slight simplification
if (n % 2 == 0) {
    n = n / 2;
    count++;
}
else {
    n = (3 * n) + 1;
    count++;
}

Can be written as:
n = (n % 2 == 0 ? n / 2 : (3 * n) + 1);
count++;

Or at least, if you don't like the conditional operator (... ? ... : ...), use the if-else for n but do count++ before or after the if/else.

Variables
Your naming leaves some things to be desired. x and y for example should be named startTime and endTime, the current names makes it sound like it is related to coordinates, which it is not.
The only variable with any meaning is max and count. It is hard to tell what kind of max max is though, naming it maxCycles would make that clearer.
As for your other variables, long i, j, n, pos, I certainly cannot tell what they're used for without looking at your code for a while. These variable names tell me absolutely nothing!
To get a better overlook of the variables, it is better to declare the variables as close to their usage as possible. y (endTime) is declared at the top, but not used until the end of the method.

Extract Method
Your main method is doing way too many things right now.
Extract parts of your code to different methods:
For example, your entire while (n != 1) loop can be extracted to a determineCycles method.

Speed Improvement
Currently you're saving the result of one calculation into your array, and while that's a good start you are missing out on some values you can use.
Let's take the example of 3. The sequence is: 3, 10, 5, 16, 8, 4, 2, 1
The only result you are storing from this operation is 3 --> 7. But you have also found out that 10 has the value 7 - 1, 5 has the value 7 - 2, 16 has the value 7 - 3 and so on... Your algorithm would increase significantly in speed if you were also storing these intermediate values.


Koch Curve algorithm in Python without using Turtle/Logo logic Inspired by the motivations expressed in this question.

I created some code to generate the point list (and also display a pretty picture) using just analytic geometry (no Logo/Turtle, no trigonometry). Also, instead of recursively inserting new points to a growing list, I calculated the final length, and then assigned values to the already initialized positions.

I would like to know if there is some obvious improvement to make it faster, cleaner, more pythonic and/or more canonical.

#!/bin/env python
# coding: utf-8

def kochenize(a,b):
    HFACTOR = (3**0.5)/6
    dx = b[0] - a[0]
    dy = b[1] - a[1]
    mid = ( (a[0]+b[0])/2, (a[1]+b[1])/2 )
    p1 = ( a[0]+dx/3, a[1]+dy/3 )
    p3 = ( b[0]-dx/3, b[1]-dy/3 )
    p2 = ( mid[0]-dy*HFACTOR, mid[1]+dx*HFACTOR )
    return p1, p2, p3

def koch(steps, width):
    arraysize = 4**steps + 1
    points = [(0.0,0.0)]*arraysize
    points[0] = (-width/2., 0.0)
    points[-1] = (width/2., 0.0)
    stepwidth = arraysize - 1
    for n in xrange(steps):
        segment = (arraysize-1)/stepwidth
        for s in xrange(segment):
            st = s*stepwidth
            a = (points[st][0], points[st][1])
            b = (points[st+stepwidth][0], points[st+stepwidth][1])
            index1 = st + (stepwidth)/4
            index2 = st + (stepwidth)/2
            index3 = st + ((stepwidth)/4)*3
            result = kochenize(a,b)
            points[index1], points[index2], points[index3] = result
        stepwidth /= 4
    return points

if __name__ == '__main__':
    TOTALWIDTH = 1000.
    points = koch(7, TOTALWIDTH)

    # If you want a pretty picture (and have Cairo and PIL modules installed)
    if True:
        import cairo, Image

        width = int(TOTALWIDTH)
        height = int(TOTALWIDTH*0.32)
        surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, width, height)
        cr = cairo.Context(surface)
        cr.set_source_rgb(1,1,1)
        cr.rectangle(0, 0, width, height)
        cr.fill()
        cr.translate(width*0.5, height*0.95)
        cr.scale(1, -1)

        cr.set_source_rgb(0,0,0)
        cr.set_line_width(0.5)
        cr.move_to(*points[0])
        for n in range(len(points)):
            cr.line_to(*points[n])
        cr.stroke()

        im = Image.frombuffer("RGBA", (width, height), surface.get_data(), "raw", "BGRA", 0,1)
        im.show()

#!/bin/env python
# coding: utf-8

def kochenize(a,b):
    HFACTOR = (3**0.5)/6

Stylistically, this would better as a global constant although there'll be some runtime cost to that.

    dx = b[0] - a[0]
    dy = b[1] - a[1]
    mid = ( (a[0]+b[0])/2, (a[1]+b[1])/2 )
    p1 = ( a[0]+dx/3, a[1]+dy/3 )
    p3 = ( b[0]-dx/3, b[1]-dy/3 )
    p2 = ( mid[0]-dy*HFACTOR, mid[1]+dx*HFACTOR )

The [0] and [1] all over the place obscures your algorithm. Checkout collections.namedtuple

    return p1, p2, p3

def koch(steps, width):
    arraysize = 4**steps + 1
    points = [(0.0,0.0)]*arraysize
    points[0] = (-width/2., 0.0)
    points[-1] = (width/2., 0.0)
    stepwidth = arraysize - 1
    for n in xrange(steps):
        segment = (arraysize-1)/stepwidth

This loop is slightly confusing to read. To understand the logic of what stepwidth, n and steps are all doing I have to look for it in several places. I'd probably write a generator which produces the decreasing values of stepwidth to encapsulate that

        for s in xrange(segment):
            st = s*stepwidth
            a = (points[st][0], points[st][1])
            b = (points[st+stepwidth][0], points[st+stepwidth][1])
            index1 = st + (stepwidth)/4
            index2 = st + (stepwidth)/2
            index3 = st + ((stepwidth)/4)*3

They way you've coded that, the symmetry between the index is non-obvious. The code would be clearer if you hand't reduce the fractions. Also, index1, index2, index3 are begging to be in a list index

            result = kochenize(a,b)
            points[index1], points[index2], points[index3] = result
        stepwidth /= 4
    return points

if __name__ == '__main__':

I recommend putting the contents of this inside a function called main which you call from here

    TOTALWIDTH = 1000.
    points = koch(7, TOTALWIDTH)

    # If you want a pretty picture (and have Cairo and PIL modules installed)
    if True:

If you want this to be optional check command line arguments or check whether the necessary modules are installed. Putting if True as anything other then a quick hack is frowned upon.

        import cairo, Image

        width = int(TOTALWIDTH)
        height = int(TOTALWIDTH*0.32)
        surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, width, height)
        cr = cairo.Context(surface)

I dislike cr, it doesn't obviously stand for anything.

        cr.set_source_rgb(1,1,1)
        cr.rectangle(0, 0, width, height)
        cr.fill()
        cr.translate(width*0.5, height*0.95)
        cr.scale(1, -1)

        cr.set_source_rgb(0,0,0)
        cr.set_line_width(0.5)
        cr.move_to(*points[0])
        for n in range(len(points)):
            cr.line_to(*points[n])
        cr.stroke()

        im = Image.frombuffer("RGBA", (width, height), surface.get_data(), "raw", "BGRA", 0,1)
        im.show()

If you want more speed, you should look into numpy. It will allow you to do vector operations which will be faster then what you can do in straight python.


Generic Tree in Java My implementation of generic Tree structure:

/**
 * Tree data structure
 */
public class Tree<T> {

    private T value;

    private Tree<T> parent;

    protected List<Tree<T>> children = Collections.emptyList();

    public Tree(T value) {
        this.value = value;
    }

    public Tree() {
    }

    /**
     * @return the value
     */
    public T getValue() {
        return value;
    }

    /**
     * @param value
     *            the value to set
     */
    public void setValue(T value) {
        this.value = value;
    }

    /**
     * Adds children
     *
     * @param children
     * @return this
     */
    public final Tree<T> addChildren(List<Tree<T>> newChildren) {

        if (children == Collections.EMPTY_LIST) {
            children = new ArrayList<>();
        }

        for (Tree<T> child : newChildren) {
            if (children.add(child)) {
                child.setParent(this);
            }
        }
        return this;
    }

    /**
     * Adds children
     *
     * @param children
     * @return this
     */
    @SafeVarargs
    public final Tree<T> addChildren(Tree<T>... children) {
        return addChildren(Arrays.asList(children));
    }

    /**
     * Removes children
     *
     * @param children
     * @return this
     */
    public final Tree<T> removeChildren(List<Tree<T>> children) {
        for (Tree<T> child : children) {
            if (this.children.remove(child)) {
                child.setParent(null);
            }
        }
        return this;
    }

    /**
     * Removes children
     *
     * @param children
     * @return this
     */
    @SafeVarargs
    public final Tree<T> removeChildren(Tree<T>... children) {
        return removeChildren(Arrays.asList(children));
    }

    /**
     * @return the parent
     */
    public Tree<T> getParent() {
        return parent;
    }

    /**
     * @param parent
     *            the parent to set
     */
    public void setParent(Tree<T> parent) {
        this.parent = parent;
    }

    /**
     * @return the tree root
     */
    public Tree<T> getRoot() {
        return parent == null ? this : parent.getRoot();
    }

    /**
     * @return children
     */
    public final List<Tree<T>> getChildren() {
        return children;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        buildString(sb, "", true);
        return sb.toString();
    }

    private void buildString(StringBuilder sb, String prefix, boolean isTail) {
        sb.append(prefix).append(isTail ? "└── " : "├── ").append(getValue()).append(System.lineSeparator());
        prefix += (isTail ? "    " : "│   ");

        for (int i = 0; i < children.size(); i++) {
            children.get(i).buildString(sb, prefix, (i == children.size() - 1));
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (!(obj instanceof Tree<?>))
            return false;

        Tree<?> other = (Tree<?>) obj;

        if (this.children.size() != other.children.size())
            return false;

        for (int i = 0; i < this.children.size(); i++) {
            if (!(children.get(i).equals(other.children.get(i))))
                return false;
        }

        return true;
    }

}

Any suggestions to make this better?

Your use of generics may be limiting. You may want to consider using the extends/super keywords to allow subtypes in the tree.
The Tree class should be final.
Perhaps TreeNode is a better name? Conceptually, it's a node, not a tree.
The children instance variable should be private. There's also no reason to use Collections.emptyList(). Just assign it to be a new ArrayList. You should really consider using a LinkedList, because you're not really doing random access on the list.
addChildren(List) should be addChildren(Collection). Sets need love, too. Whether the order is important or not should be left up to the client.
Your documentation for addChildren() and removeChildren() should make it clear that they modify the incoming children as a side effect.
It's not at all clear to me that it's desirable to return this from addChildren() and removeChildren(), but you certainly know more than I do about client needs.
setParent() needs to be private, or a client is going to change it manually and break your internals. Specifically, the node that used to be the parent will still have a reference to the node that just got its parent changed - you'll have two different one-way relationships, such that X's parent does not have X as its child.
getChildren() needs to return a (preferably immutable) copy of the children list, not the list itself. Otherwise a client can call removeAll() on the response and your internals are broken.
If you override equals(), you should also override hashCode(), or you may see strange behaviours, especially with collections. Are you sure you really need equals()?
The tree is thread-hostile. That is probably okay, given that this is most likely not production code, but it's something to be aware of.


Find longest lines from a file This is a challenge question from codeeval.com:

  Write a program which reads a file and prints to stdout the specified
  number of the longest lines that are sorted based on their length in
  descending order. Input sample:

  Your program should accept a path to a file as its first argument. The
  file contains multiple lines. The first line indicates the number of
  lines you should output, the other lines are of different length and
  are presented randomly. You may assume that the input file is
  formatted correctly and the number in the first line is a valid
  positive integer.

  For Example:

2
Hello World
CodeEval
Quick Fox
A
San Francisco

  Output sample:

  Print out the longest lines limited by specified number and sorted by
  their length in descending order.

  For example:

San Francisco
Hello World

Please let me know how I can improve this implementation.

#include<iostream>
#include<map>
#include<fstream>
#include<string>
#include<chrono>

class fixed_hash{
public:
        fixed_hash( int pSize )
        {
            size = pSize;
        }
        void push( std::string & record )
        {

            if( hash_table.size() < size )
            {
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
            else if( record.size() > hash_table.rbegin()->second.size() )
            {
                hash_table.erase( hash_table.begin() );
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
        }
        void print()
        {
            auto end = std::rend(hash_table);
            for( auto it = std::rbegin( hash_table ); it != end ; ++it )
            {
                std::cout << it->second << "\n";
            }
        }

 private:
        std::map<int,std::string> hash_table;
        int size;
};

void readInputFile( std::string fileName )
{
    std::ifstream infile( fileName );
    std::string record;
    int output_nbr = 0;
    infile >> output_nbr;
    fixed_hash output_string_list( output_nbr );
    while( std::getline( infile, record ) )
    {
        output_string_list.push( record );
    }

    output_string_list.print();
    infile.close();
}

int main( int argc, char* argv[] )
{
    auto start = std::chrono::steady_clock::now();
    if( argc < 2 )
    {
        std::cout << "Error: input file is missing " << "\n";
        exit( 0 );
    }

    std::ios_base::sync_with_stdio( false );
    readInputFile( argv[ 1 ]);

    auto end      = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    std::cout<< duration.count() << "\n";
    return 0;
}

This is a bug:

else if( record.size() > hash_table.rbegin()->second.size() )

As implemented, insertion stops once your program encounters the longest line in the file.

For example, suppose the input contains:

2
abcdefghijklmop
a
ab
abc
abcd

Your program will output:

abcdefghijklmop
a

The fix is simple: Change rbegin to begin.

Another potential issue is your use of a std::map as opposed to some other container. Your concept is fine, but not necessarily for "I'm the best hacker!" type sites that place strong emphasis on execution time. A vector-based solution could be faster. With the red-black tree-based hash, search, insertion, and delete are \$O(log n)\$ (but with large constants). With a vector-based solution, search would be \$O(log n)\$ (but potentially much faster than a red-black search), deleting the tail is \$O(1)\$ (which is a big win), but insertion is \$O(n)\$ (which is of course a big loss). However, for small enough values of n, a fast \$O(n)\$ algorithm can and will beat a slow \$O(log n)\$ algorithm.

One last remark: Rather than your void print() member, a stream insertion operator would be more C++-like:

class fixed_hash
{
    ...
    friend std::ostream& operator<<(std::ostream& os, const fixed_hash& hash);
    ...
};

std::ostream& operator<<(std::ostream& os, const fixed_hash& hash)
{
    auto end = std::rend(hash.hash_table);
    for( auto it = std::rbegin(hash.hash_table); it != end ; ++it )
    {
        os << it->second << "\n";
    }
    return os;
}


Generic merge sort in C++ using a user-defined comparison function or the < operator by default I wanted to implement a generic merge sort algorithm using the same interface as std::sort(). The interface takes first and last iterators to a range of elements in any container. The user has the option to provide a custom function that compares two elements; if none is provided, the operator < is used by default.

I handled the default case by creating a wrapper function that calls the real function using a lambda expression, but I'm wondering if there's a way to get rid of this second wrapper function.

Feedback on any aspect of the code is welcome.

template <class RandomAccessIterator, class Compare>
void mergesort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    size_t n = last - first;

    if (n <= 1)
        return;

    size_t m = n / 2;

    mergesort(first, first + m, comp);
    mergesort(first + m, last, comp);

    std::vector<RandomAccessIterator::value_type> v(last - first);
    RandomAccessIterator itResult = v.begin();

    RandomAccessIterator itLower = first;
    RandomAccessIterator itUpper = first + m;

    while (itLower != first + m && itUpper != last)
        *(itResult++) = comp(*itLower, *itUpper) ? *(itLower++) : *(itUpper++);

    if (itUpper == last)
        std::copy(itLower, first + m, itResult);
    else
        std::copy(itUpper, last, itResult);

    std::copy(v.begin(), v.end(), first);
}

template <class RandomAccessIterator>
void mergesort(RandomAccessIterator first, RandomAccessIterator last)
{
    mergesort(first, last, [](RandomAccessIterator::value_type a, RandomAccessIterator::value_type b) { return a < b; });
}

Avoid a copy by passing by const reference.

[](RandomAccessIterator::value_type const& a, RandomAccessIterator::value_type const& b) { return a < b; }
                                    ^^^^^^                                     ^^^^^^

Don't need an if statatement here:

if (itUpper == last)
    std::copy(itLower, first + m, itResult);
else
    std::copy(itUpper, last, itResult);

One of these ranges will be empty and just do nothing.

std::copy(itLower, first + m, itResult);
std::copy(itUpper, last, itResult);

To avoid a copy (which can be expensive on non POD types). Prefer to use move.

std::move(itLower, first + m, itResult);
std::move(itUpper, last, itResult);

std::move(v.begin(), v.end(), first);

You spend a lot of time creating the temporary array:

std::vector<RandomAccessIterator::value_type> v(last - first);

Basically this causes calls to new for every call to void mergesort(RandomAccessIterator first, RandomAccessIterator last, Compare comp). You can optimize this by allocating the temp space once in void mergesort(RandomAccessIterator first, RandomAccessIterator last) and pass the section of the temp array that recursive function can use.

I know you are trying to be explicit with RandomAccessIterator. But it is more traditional to use single letter for template types. Also there is no compiler validation that your iterator is random accesses (so you are giving a false sense of security to your user).

C++20 should add Concepts (finally). Single letter template types will work well with this.

 template<typename I>
 requires RandomAccessIterator<I>
 void mergesort(I begin, I end){}

For C++ pre 20 You can write:

 template<typename I>
 // requires RandomAccessIterator<I>
 void mergesort(I begin, I end){}

Which provides the same information and when concepts are added you can just remove the comment.


Evaluating π using Monte Carlo methods - Serial vs OMP I wrote this simple code for evaluating the π using Monte Carlo method. This is the serial version:

long double compute_pi_serial(const long interval) {

  srand(time(NULL));

  double x, y;
  int i, circle = 0;

  for (i = 0; i < interval; i ++) {
    x = (double)(rand() / (double) RAND_MAX);
    y = (double)(rand() / (double) RAND_MAX);

    if (pow(x,2) + pow(y, 2) <= 1.0) circle ++;
  }

  return (long double) circle / interval * 4.0;
}

After, I wrote a parallel version using OpenMP and this is the result:

long double compute_pi_omp(const long interval) {

  double x, y;
  int i, circle = 0;

  #pragma omp parallel private(x, y) num_threads(omp_get_max_threads())
  {

    srand(SEED);

    #pragma omp for reduction(+:circle)
    for ( i = 0; i < interval; i++ ) {
      x = (double)(rand() / (double) RAND_MAX);
      y = (double)(rand() / (double) RAND_MAX);

      if ( pow(x, 2) + pow(y, 2) <= 1 ) circle++;
    }
  }

  return (long double) circle / interval * 4.0;
}

This is an efficient method or there is a most efficient version always using OpenMP?

Correctness issues

Correctness merits priority over efficiency. Important to get a correct answer, not a  fast and wrong one.

Poor use of mixing types

long interval, and int i lead to undefined behavior (UB) when interval > INT_MAX.  Use same type.

Small range

long may use 32-bit.  Easy enough to run in less than 1 minute and exceed 231 - limiting how far we can test this code.  Use long long or, use unsigned long long.

Off-by-1

Using / (double) RAND_MAX  may impart a small bias.  Yet given the slow  convergence of the Monte Carlo PI, I doubt any serious miscalculation.

I'd expect the random values to be in the middle of each random range:

[0.5, 1.5, 2.5, ... RAND_MAX - 1.5, RAND_MAX - 0.5, RAND_MAX + 0.5]/(RAND_MAX + 1u)

Code has then distributed differently:

[0.0, 1.0/RAND_MAX, 2.0/RAND_MAX, ... 1.0]

A more significant bias occurs when (int)(double) RAND_MAX != RAND_MAX - select platforms with more precision in RAND_MAX than double.

Note: to convert RAND_MAX plus 1 to double, code can use (RAND_MAX/2 + 1)*2.0.  Works well when RAND_MAX is a Mersenne Number or and odd value.  This avoids losing precision that (double)RAND_MAX + 1.0 may incur.

Efficiency

pow() vs x*x

A weak compiler may use a laborious function call seeing pow(x,2) and not the certainly more efficient x*x replacement.  Of course the right answer is to use a smart  compiler.  Still, profiling a direct coding of x*x may prove worth-wild.

fp vs. integer

I'd even consider an integer only approach.  Something like the below.

// int2x twice as wide as int
int2x limit = (int2x) RAND_MAX * RAND_MAX;
...
  int2x x = rand();
  int2x y = rand();
  if (x*x + y*y <= limit) circle++;

double vs. long double

Seriously doubt any calculation run within a day will benefit using the higher precision long double.

// return (long double) circle / interval * 4.0;
return circle / interval * 4.0;

No comment on OP's major goal: Serial vs OMP - sorry.