Parsing characters with parsec I am trying to parse escape sequences as well as plain characters. Can this be made more succinct?

import Control.Applicative
import Data.Char
import Numeric
import Text.Parsec hiding ((<|>))

echar :: Parsec String () Char
echar = (char '\\' >>
         ((char 'b' >> return '\b')
          <|> (char 'f' >> return '\f')
          <|> (char 'n' >> return '\n')
          <|> (char 'r' >> return '\r')
          <|> (char 't' >> return '\t')
          <|> (char 'u' >> count 4 hexDigit >>= return . chr . fst . head . readHex)
          <|> (char 'v' >> return '\v')
          <|> (noneOf "u")))
        <|> noneOf "\\"

You could cut down on the repetitive elements with a local function binding.

echar =
  let
    yield :: Char -> Char -> Parsec String () Char
    yield c d = char c >> return d
  in
    (char '\\' >>
       (  yield 'b' '\b'
      <|> yield 'f' '\f'
       -- ...

Then perhaps cut out the repeated applications with a fold.

import Data.Foldable

-- ...
  in
    (char '\\' >>
       (  (asum . map (uncurry yield) $ [('b', '\b'), ('f', '\f') -- ...
      <|> (char 'u' -- ...

I'm not sure you need the Numeric import either, I would write that line as—

char 'u' >> count 4 hexDigit >>= return . chr . read . ("0x" ++)

And then to tie it all together with a bow.

import Control.Applicative        ((<|>))
import Data.Char                  (chr)
import Data.Foldable              (asum)
import Text.Parsec         hiding ((<|>))

echar :: Parsec String () Char
echar =
  let
    escapeCharacters = [('b', '\b'), ('f', '\f'), ('r', '\r'), ('t', '\t'), ('v', '\v')]

    yield :: Char -> Char -> Parsec String () Char
    yield c d = char c >> return d
  in
    (char '\\' >>
       (  (asum . map (uncurry yield) $ escapeCharacters)
      <|> (char 'u' >> count 4 hexDigit >>= return . chr . read . ("0x" ++))
      <|> (noneOf "u")
       )
    ) <|> noneOf "\\"


Create multiple divs inside a containing div The below function is used to create multiple content division elements (i.e. <div>) inside a containing <div>. The function is working correctly and is as expected, I just feel the quality of the code itself is a bit poor.

Therefore, can the following function be, in any way, simplified or improved?

generate(chartData) {
      var container = document.createElement("div");
      $(container).attr("class", "container2");

      var myNode = document.getElementById(chartData.bindto.replace("#", "")).appendChild(container);

      for(var i = 0; i < 10; i++) {
        var div = document.createElement('div');
        $(div).attr("class", "block");
        var span = document.createElement('span');
        var text = "Hello World!";
        span.append(text);
        div.append(span);
        myNode.append(div);
      }
    }

Descriptive names

As a global function name, generate is too vague: it should tell what it's generating, something like generateChart. As a method name it would be ok because the object itself would be what's being generated or doing the generation (e.g. chart.generate()).

(I'm aware that the function doesn't actually generate a chart as it currently is, but I assume that the "hello world" part is later replaced with the actual code that does it.)

Class names like "container2" and "block" aren't descriptive enough to tell what their meaning is. "Block" might be descriptive in context, but "container2" certainly isn't.

Too broad parameters

You're passing an object chartData to the function, but only use its bindto property. You could pass the property directly to the function, as it seems to only tell where to put the chart.

Mixing jQuery and native DOM methods

As a general rule when doing low-level element manipulation you should either always use jQuery or never use it, but not mix the two. In the code you're using jQuery only to add class names, which could easily be done with plain JavaScript.

Browser compatibility

.append() isn't supported by any version of Microsoft or Android browsers so if you're targeting any of those browsers you'll have to use other methods, add a polyfill, or use jQuery. Note that .append() on native DOM elements is a different method than jQuery's .append().

Miscellaneous

myNode points to container (because .appendChild() returns the child element). Having two variables for the same element is confusing, so you should only use container.

Variable declarations should be at the top of the function if possible. Variables shouldn't be declared inside a loop, unless you're using let.

The variable text should be declared outside the loop. It's always the same so re-declaring it 10 times is unnecessary.

The number 10 in the for loop is a magic number - you should replace it with a descriptive constant, especially if it's used somewhere else too to refer to the number of blocks in the chart.

Single and double quotes should be used consistently to delimit strings, so either use single quotes everywhere or double quotes everywhere.

Revised code

Putting it all together, plain JavaScript version:

var BLOCKS_PER_CHART = 10;

function generateChart(chartContainer) {
  var container = document.createElement("div");
  var text = "Hello World!";
  var blockDiv, textSpan;  // used in the for loop

  container.className = "container2";
  document.getElementById(chartContainer.replace("#", "")).appendChild(container);

  for(var i = 0; i < BLOCKS_PER_CHART; i++) {
    blockDiv = document.createElement("div");
    blockDiv.className = "block";
    textSpan = document.createElement("span");
    textSpan.append(text);  // see note about browser compatibility
    blockDiv.append(textSpan);
    container.append(blockDiv);
  }
}

jQuery version:

var BLOCKS_PER_CHART = 10;

function generateChart(chartContainer) {
  var container = $("<div>").addClass("container2").appendTo(chartContainer);
  var text = "Hello World!";
  var blockDiv;  // used in the for loop

  for(var i = 0; i < BLOCKS_PER_CHART; i++) {
    blockDiv = $("<div>").addClass("block").appendTo(container);
    $('<span>').text(text).appendTo(blockDiv);
  }
}

Both of these assume that the function is called with what used to be chartData.bindto. Also, I don't know the purpose of "container2" so I've left its name for you to change.

Note that this could be further improved if latest ECMAScript features like const can be used.


Optimizations for this user-account HTML structure? I need a valid and semantic HTML structure for the user-account (user-panel) section of the overall layout of my web application.

What I saw in other web apps include:

User title (or email, or username)
A thumbnail (on which you can click to change your picture)
A notifications icon (with the number of notifications in red)
An arrow besides the whole area (which shows a menu to have further options for your user account settings)

Here is the HTML I've come up with:

    Saeed Neamati

Current User

        2

First Notification

Second Notification

Change your password

Subscription settings

Payments

"Saeed Neamati" should probably be the heading (h1) of the section (instead of span).

Don’t forget the alt attribute for the img.

The .notifications should be a sectioning element, probably section, maybe aside. Then the notification count could be the heading.

The .menu should be enclosed by a nav, as it’s the navigation for that section.

Result:

Saeed Neamati

Current User

2

First Notification

Second Notification

Change your password

Subscription settings

Payments

Depending on your implementation, the .menu resp. the .notifications may be the main content for that section. In that case, the corresponding sectioning element should be removed.


JavaScript dropdown component How can I improve this component with using event delegation rather than doing a lookup using parentNode so that I can change the markup around without having to update the JavaScript?

HTML

          Lorem ipsum dolor sit amet, consectetuer adipiscing elit

JavaScript

(function(){

      var dropDownClosed = 'js-drop-down',
          dropDownButtonList = document.querySelectorAll('.drop-down-btn-wrapper');

      function init() {
        for(var i=0; i<dropDownButtonList.length; i++) {
          dropDownButtonList[i].addEventListener('click', initDropdown, false);
        }
      }

      function initDropdown(e) {

        var event          = e.target;
        var contentWrapper = event.parentNode.parentNode.parentNode.childNodes[3];
        var content        = event.parentNode.parentNode.parentNode.childNodes[3].childNodes[1];
        var closedButton   = event.parentNode.parentNode.parentNode.childNodes[1].childNodes[3];
        var contentHeight  = content.offsetHeight;

        if(hasClass(contentWrapper, dropDownClosed)) {
          removeClass(contentWrapper, dropDownClosed);
          contentWrapper.style.height = contentHeight+'px';
          closedButton.style.opacity = '0.0';
        } else {
          addClass(contentWrapper, dropDownClosed);
          contentWrapper.style.height = 0+'px';
          closedButton.style.opacity = '1.0';
        }
      }

      function hasClass(ele, cls) {
          return ele.className.match(new RegExp('(\\s|^)' + cls + '(\\s|$)'));
      }
      function addClass(ele, cls) {
          if (!hasClass(ele, cls)) ele.className += " " + cls;
      }
      function removeClass(ele, cls) {
          if (hasClass(ele, cls)) {
              var reg = new RegExp('(\\s|^)' + cls + '(\\s|$)');
              ele.className = ele.className.replace(reg, '');
          }
      }

      init();

    }());

CSS

.drop-down-wrapper {
  position:relative;
  border: 2px black solid;
  margin-bottom:20px;
  padding:20px 0;
}

.content-wrapper {
  padding:15px;
  margin:30px 0;
}

.drop-down-open {
  position:absolute;
  top:0;
  border: thin red solid;
}

.drop-down-closed {
  position:absolute;
  top:0;
  border: 2px solid green;
}

.drop-down-content {
  background-color:#fff;
  overflow:hidden;
  height:0;
}

DEMO

Sure, you can use event delegation for this. For the uninitiated, event delegation in JavaScript means attaching the event listener to a container element and using the target property of the event to identify which sub-element was acted upon.

You'll still need to crawl your way up the DOM tree to get to the root element, which can be done without knowing the DOM structure as long as you have a sentinel you can check, such as the root element's class name, to determine whether you've reached the root.

Once you've made it to the top, so to speak, you can use query selectors to find your way back down to specific child nodes within the root element, again allowing you to grab or modify specific elements without knowing the HTML structure--all you'll need to know is a reliably query-selectable combination of attributes (such as an element class).

Here's a working example with comments:

(function() {
  var dropDownClosed = "js-drop-down",
    dropDownButtonList = document.querySelectorAll(".drop-down-wrapper");

  function init() {
    for (var i = 0; i < dropDownButtonList.length; i++) {
      dropDownButtonList[i].addEventListener('click', initDropdown, false);
    }
  }

  function initDropdown(e) {
    e = e || window.event;
    var target = e.target || e.srcElement,
      validElement = false;
    while (!hasClass(target, "drop-down-wrapper")) { /* crawl up the DOM until reaching "root" element */
      target = target.parentNode;
      if (!validElement) { /* track whether user clicked on the open or close buttons */
        if (hasClass(target, "drop-down-open") || hasClass(target, "drop-down-closed")) {
          validElement = true;
        }
      }
    }
    if (validElement) { /* Only toggle content if open/close button was clicked. */
      /* Get the desired content based on its attributes rather than its DOM position: */
      var contentWrapper = target.querySelector(".drop-down-content");
      var content = contentWrapper.querySelector("*");
      var closedButton = target.querySelector(".drop-down-closed");
      var contentHeight = content.offsetHeight;
      if (hasClass(contentWrapper, dropDownClosed)) {
        removeClass(contentWrapper, dropDownClosed);
        contentWrapper.style.height = contentHeight + 'px';
        closedButton.style.opacity = '0.0';
      } else {
        addClass(contentWrapper, dropDownClosed);
        contentWrapper.style.height = 0 + 'px';
        closedButton.style.opacity = '1.0';
      }
    }
  }

  function hasClass(ele, cls) {
    return ele.className.match(new RegExp('(\\s|^)' + cls + '(\\s|$)'));
  }

  function addClass(ele, cls) {
    if (!hasClass(ele, cls)) ele.className += " " + cls;
  }

  function removeClass(ele, cls) {
    if (hasClass(ele, cls)) {
      var reg = new RegExp('(\\s|^)' + cls + '(\\s|$)');
      ele.className = ele.className.replace(reg, '');
    }
  }

  init();

}());
.drop-down-wrapper {
  position: relative;
  border: 2px black solid;
  margin-bottom: 20px;
  padding: 20px 0;
}
.content-wrapper {
  padding: 15px;
  margin: 30px 0;
}
.drop-down-open {
  position: absolute;
  top: 0;
  border: thin red solid;
}
.drop-down-closed {
  position: absolute;
  top: 0;
  border: 2px solid green;
}
.drop-down-content {
  background-color: #fff;
  overflow: hidden;
  height: 0;
}

        Lorem ipsum dolor sit amet, consectetuer adipiscing elit

        Lorem ipsum dolor sit amet, consectetuer adipiscing elit

I did change your variable named event to target to make it more clear that it represents an element in the DOM tree that we're climbing.

You could improve this further by executing the relevant query selectors at or before the time the event listener is being attached, caching the results so that you don't have to requery the DOM every time an event is triggered.


Pseudo Random Number Generator I recently watched this video about the random number generation in Super Mario World. The technique that is used, as seen in the image below, multiplies one of the seeds by 5 and adds 1, the other seed is multiplied by 2, and then depending on whether the 4th and 7th bits are the same, 1 is added. So as stated in the video, the sequence of numbers will repeat after 27776 successive calls.

In my implementation of a pseudo random number generator, I have used 16 bit values for the two seeds to allow for a greater range of numbers, and my get_rand() function returns the two 16 bit strings joined together, resulting in a 32 bit number. This means that the sequence of numbers repeats after 526838144 successive calls, which is far greater than that achieved with the pseudo random number generator used in Super Mario World.

I have also created a rand_int() and a random() function that allow for better use of the numbers generated, these simply divide the number returned by 2 ** 32 over the difference between the integer range.

The PRNG Test.py is there only so that I can make sure that all the functions work as expected, and it seems to provide evenly split pseudo random numbers. So I am just after a review of the PRNG.py file, as it is that which I would like to optimize and improve.

PRNG.py

#Make sure Seeds.txt exists
try:
    file = open('Seeds.txt')
except FileNotFoundError:
    file = open('Seeds.txt', 'a+')
    file.write('0\n0')

#Gets the values of the seeds from the file
values = file.readlines()
file.close()

S = int(values[0].rstrip('\n'))
T = int(values[1])

def seed(seed_value):
    '''Resets the seed for the PRNG to make values predictable'''
    global S, T

    with open('Seeds.txt', 'w') as file:
        file.write(str(seed) + '\n' + str(seed))
        file.close()

    S = seed
    T = seed

def update_seeds(S, T):
    '''Generates the next two seeds'''
    S = 5 * S + 1

    try: bit_11 = '{0:b}'.format(T)[-11]
    except IndexError: bit_11 = '0'

    try: bit_16 = '{0:b}'.format(T)[-16]
    except IndexError: bit_16 = '0'

    if bit_11 == bit_16: T = 2 * T + 1
    else:                T = 2 * T

    return S, T

def get_rand(): #Has 526838144 Possible numbers
    '''Produces a random number in the range 0 to 2 ** 32'''
    global S, T

    S, T = update_seeds(S, T)
    S = int('{0:b}'.format(S)[-16:], 2)
    T = int('{0:b}'.format(T)[-16:], 2)
    K = '{0:b}'.format(S ^ T)

    S, T = update_seeds(S, T)
    S = int('{0:b}'.format(S)[-16:], 2)
    T = int('{0:b}'.format(T)[-16:], 2)
    J = '{0:b}'.format(S ^ T)

    with open('Seeds.txt', 'w') as file:
        file.write(str(S) + '\n' + str(T))
        file.close()

    for i in range(16 - len(K)): K = '0' + K
    for i in range(16 - len(J)): J = '0' + J

    return int(K + J, 2)

def rand_int(a, b):
    '''Produces in a random integer in the range a to b'''
    difference = (b + 1) - a
    factor = 2 ** 32 / difference
    return a + int(get_rand() / factor)

def random():
    '''Returns a random float between 0 and 1'''
    return get_rand() / 2 ** 32

PRNG Test.py

import PRNG

l = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(10000):
    number = PRNG.rand_int(0, 9)
    l[number] += 1

for i in l:
    print(str(round(i / 10000 * 100, 2)) + '% :', i)

The statement bit_11 = '{0:b}'.format(T)[-11] actually extracts bit 10, because the convention is to number bits from zero, while indexing from the end of string starts at [-1].
Performing bit manipulations in string format is clunky. Use bitwise operators instead. For example, to extract bit 10: T >> 10 & 1
Opening a file by a with statement ensures it will be closed. You can omit the close calls.
Strings have a zfill method that does the same as for i in range(16 - len(K)): K = '0' + K


Switch expression function I made a bunch of functions and an enumeration, that together allow me to write something like a switch expression. It's not as powerful as Swift switch statements, since it's lacking pattern matching and I don't intend to use this in real code, it was just an experiment. Here is what I got:

enum Caze<T: ForwardIndexType where T: Equatable> {
    case RangeCaze(Range<T>)
    case ArrayCaze([T])

    func contains(elem: T) -> Bool {
        switch self {
        case let .RangeCaze(r):
            return r.contains(elem)
        case let .ArrayCaze(arr):
            return arr.contains(elem)
        }
    }
}

func caze<T: ForwardIndexType, R where T: Equatable>(vals: T..., @autoclosure(escaping) ret f: () -> R) -> (Caze<T>, () -> R) {
    return (.ArrayCaze(vals), f)
}

func caze<T: ForwardIndexType, R where T: Equatable>(vals: Range<T>, @autoclosure(escaping) ret f: () -> R) -> (Caze<T>, () -> R) {
    return (.RangeCaze(vals), f)
}

func caze<T: Equatable, R>(vals: T..., @autoclosure(escaping) ret f: () throws -> R) -> ([T], () throws -> R) {
    return (vals, f)
}

func schwitch<T: ForwardIndexType, R where T: Equatable>(value: T, _ cases: (Caze<T>, () -> R)..., @autoclosure def: () throws -> R) rethrows -> R {
    for (vals, f) in cases {
        if vals.contains(value) {
            return f()
        }
    }
    return try def()
}

func schwitch<T: Equatable, R>(value: T, _ cases: ([T], () -> R)..., @autoclosure def: () throws -> R) rethrows -> R {
    for (vals, f) in cases {
        if vals.contains(value) {
            return f()
        }
    }
    return try def()
}

This allows me to write code like:

schwitch(5, // results in "lol"
    caze(0, ret: "hello"),
    caze(1, 2, ret: "test"),
    caze(3..<7, ret: "lol"),
    def: "nop")

schwitch("helloo", //results in "nop"
    caze("hello", "Hello", ret: "test"),
    def: "nop")

I think there are a few problems with this though.

There is quite a bit of code duplication due to a few nearly identical functions being needed.
The closure sent to the caze functions are escaping, though they are intended to never actually escape beyond a very defined scope.
If code in a caze function throws, it doesn't get rethrown.
I also considered an alternative implementation for the schwitch functions but am worried that it takes brevity a bit too far:

(cases.filter{$0.contains(value)}.first ?? def)()

Are there any ways to improve on these 4 points and are there any other things that I missed or could have done better?

There is quite a bit of code duplication due to a few nearly identical functions being needed.

This is probably the biggest issue and the one I'll be addressing here.

The two schwitch functions have identical bodies, this is a major code smell. The only difference between the two is the generic constraints on T and the type T is wrapped up in (Array and Caze repectively). You don't actually care that Tconforms to ForwardIndexType in the schwitch function and the only way I was using both Caze and Array was by calling contains on them (with identical signatures). This clearly calls for a protocol. And I didn't even need to declare one myself. the contains function I was using is declared in SequenceType, a protocol both Array and Range conform to. So here's what the new (and only) schwitch function will look like:

func schwitch<S: SequenceType, R where S.Generator.Element: Equatable>(value: S.Generator.Element, _ cases: (S, () -> R)..., @autoclosure def: () -> R) -> R {
    for (vals, f) in cases {
        if vals.contains(value) {
            return f()
        }
    }
    return def()
}

You will notice that function is now missing a rethrows, the swift compiler hangs up on that due to a bug.

This also allowed me to get rid of the Caze enum and only have two caze functions, one that takes any amount of values and one that takes a range:

func caze<T: Equatable, R>(vals: T..., @autoclosure(escaping) ret f: () -> R) -> (AnySequence<T>, () -> R) {
    return (AnySequence(vals), f)
}

func caze<T, R where T: Equatable, T: ForwardIndexType>(range: Range<T>, @autoclosure(escaping) ret f: () -> R) -> (AnySequence<T>, () -> R) {
    return (AnySequence(range), f)
}

I've made both functions return an AnySequence<T> instead of more concrete type, I think that makes sense, considering how the results are used, but it's really up to you if you maybe want to return Array<T> and Range<T> instead.

I can still use my function exactly as I did before.


Yet Another, Another Prime Generator Yes, I realize there are many, many, many, many, many, prime generators on the Code Review SE. However, I have been unable to find any using this method for generating primes inside a vector, so I figure it should be covered.

Here's the C++ code:

long int primeCap = 1e10;
std::vector<long int> primes;
primes.push_back(2);
for(long int i = 2; i < primeCap; i++){
    bool isPrime = true;
    for(long int j = 0; primes[j] <= sqrt(i); j++){
        if(i % primes[j] == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime)
        primes.push_back(i);
}

This code takes a while to fill a vector with \$10^{10}\$ (or more, depending on how much is needed) primes. How can this code be improved for the generation primes?

Update: The issue described below was a nonissue, and was simply an error on my part, the part below can be ignored.

There may also be an issue where the very last item in the vector is set to \$2\$. I have not effectively verified this, but modifying the if(isPrime) statement to be:

if(isPrime){
    std::cout << i << '\n';
    primes.push_back(i);
}

Results in the last output being two. Once again, I have not effectively verified this, but it is something to note.

Here are some things that may help you improve your code.

Use the required #includes

The code uses std::vector which means that it should #include <vector>.  It was not difficult to infer, but it helps reviewers if the code is complete.

Use <cmath> instead of <math.h>

I infer that you've used <math.h> instead of <cmath> because you're invoking sqrt(i) rather than std::sqrt(i).  The difference between the two include forms is that the former defines things within the std:: namespace versus into the global namespace.  Language lawyers have lots of fun with this, but for daily use I'd recommend using <cmath>.  See this SO question for details.

Use the appropriate constructor

There's not really any reason to push the value of 2 after the stack is created when it could be done all at the same time.  In fact, I'd write this:

std::vector<int> primes{2, 3};

Seeding the vector with the first two primes for reasons that will be very clear in the next suggestion.

Use a more efficient algorithm

Of all even numbers, only 2, which is already in the vector, is prime, so thereafter all even numbers may be safely skipped.  Further, there's little reason to attempt to divide by 2 if you've skipped all other even numbers.  For that reason, I'd write it like this:

for(int i = 3; i < primeCap; i+=2) {
    bool isPrime = true;
    int lim = std::sqrt(i);
    for(int j = 1; primes[j] <= lim; j++){
        if(i % primes[j] == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime)
        primes.push_back(i);
}

Doing this reduces the time by about half.

Use const where practical

Since primeCap doesn't seem to change within this program, it would make sense to me to declare it as const or even constexpr:

constexpr long int primeCap = 1e8;

Maximize the available numerical range

Assuming we're not hunting for negative prime numbers, wouldn't unsigned numbers make more sense?  It's also logical to try to assure that primeCap and the values in the std::vector are of the same type -- either unsigned or unsigned long.

Avoid memory reallocations

It would save some reallocations and moves if the code were to preallocate the required size.  One quick and relatively accurate approximation for the number of prime numbers less than a particular number \$n\$ is \$\frac{n}{\log{n}-1}\$.  We can use that to reserve approximately the right amount of memory:

primes.reserve(primeCap / (std::log(primeCap) - 1));

Avoid breaking out of loops

It's generally better to put loop exit conditions at the top rather than forcing the reader to hunt for a break buried somewhere inside the loop.  It also often simplifies the code.  The for loop could be rewritten as:

for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
    isPrime = i % operator[](j);
}

Consider a custom class

If we need a std::vector of prime numbers, there's little use in it until it's actually created and populated.  For that reason, one way to make sure that it's useful immediately after construction is to create a class with a constructor:

Result

Here's the code with all of these suggestions.  It runs about twice as fast as the original for any given range.

#include <vector>
#include <cmath>
#include <iostream>

class Primes : public std::vector<unsigned>
{
public:
    Primes(unsigned primeCap)
        : std::vector<unsigned>{2,3}
     {
        reserve(primeCap / (std::log(primeCap) - 1));
        for(unsigned i = back()+2; i < primeCap; i+=2) {
            bool isPrime = true;
            unsigned lim = std::sqrt(i);
            for(unsigned j = 1; isPrime && operator[](j) <= lim; j++){
                isPrime = i % operator[](j);
            }
            if(isPrime)
                push_back(i);
        }
    }
};

int main() {
    Primes primes(1e8);
    std::cout << "prime[" << primes.size() << "] = " << primes.back() << "\n";
}


CodeChef - Please like me In a far away dystopian world, the measure of the quality of a person’s life is the numbers of likes he gets for an article about their life. For a person to stay alive, he has to acquire at least L number of likes before D days pass.

  People in this world employ various techniques to increase the number of likes. One of the famous ones is to dis-like and re-like their own article once per day. On doing so you can assume that the number of likes for the post increase by a constant factor C.

  So if one starts with S likes on Day-1, he would have D2 = S + C * S likes on Day-2, D3 = D2 + D2 * C on Day-3 etc. You are to answer if the person would survive at the end of Day-D or not.

  Input

  First line contains a single positive integer T denoting the number of test cases. The following T lines represent a test case each. Each test case contains 4 space-separated integers L, D, S and C.

  Output

  For each test case, print a single line containing “ALIVE AND KICKING” if the person would live, otherwise print, “DEAD AND ROTTING”.

  Constraints

  1 <= T <= 1000

  1 <= L <= 1000000000

  1 <= D <= 1000000000

  1 <= S <= 1000000000

  1 <= C <= 1000000000

  Sample cases:

  Input

  2

  5 1 5 1

  10 2 2 2

  Output

  ALIVE AND KICKING

  DEAD AND ROTTING

#include <stdio.h>

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long int l,d,s,c;
        scanf("%lld%lld%lld%lld",&l,&d,&s,&c);
        long long int i;
        long long int x=s;
        for(i=2;i<=d;i++)
            x*=(1+c);
        if(x>=l)
            printf("ALIVE AND KICKING\n");
        else
            printf("DEAD AND ROTTING\n");
    }
    return 0;
}

How do I improve efficiency so that the time limit does not get exceeded?

I think the key thing you are missing isn't a better pow function.  The problem is that you are iterating d times without checking whether you have surpassed l.  Notice that for the lowest c of 1, you are multiplying by 2 every loop.  The maximum l is 1000000000 which is less than 2^30.  Therefore the max number of loops you will ever need is 30.

If you simply checked every loop:

if (x >= l)
    break;

then you limit your loop to 30 iterations instead of 1000000000 iterations.


Selecting and inserting MySQL records using PDO This PHP class connects to and queries the database MuSKL. I am a novice, and I ask you to comment on the approach and style of code.

<?php

class MysqlAccess {

    private $dsn = 'mysql:dbname=bid;host=127.0.0.1';
    private $user = 'bid_root';
    private $password = 'e1e2e3e4e5er';
    private static $_db;
    private $_PDO;
    public $fetchQueryResult;

    private function __construct() {
        try {

            $this->_PDO = new PDO($this->dsn, $this->user, $this->password);

            $this->_PDO->exec('SET NAMES utf8');
        } catch (PDOException $e) {

            echo $e->getMessage();
        }
    }

    protected function __clone() {}

    static public function getInstance() {
        if (is_null(self::$_db)) {
            self::$_db = new self();
        }
        return self::$_db;
    }

    public function querySelect($tableName, array $arrayColum) {

        if (!is_array($arrayColum) or ! is_string($tableName)) {
            die('Неверный формат данных в запросе SELECT в запросе SQL');
        }

        $colums;

        foreach ($arrayColum as $value) {
            if (!is_string($value)) {
                die('Неверный формат данных в запросе SQL');
            }
            $colums .= SequrityData::SequrityReturnData($value) . ', ';
        }

        $colums = substr($colums, 0, -2);

        // запрос к базе данных
        $results = $this->_PDO->query('SELECT ' . $colums . ' FROM ' . SequrityData::SequrityReturnData($tableName));

        $this->fetchQueryResult($results);
    }

    public function queryInsert($tableName, array $arrayColums) {

        if (!is_array($arrayColums) or ! is_string($tableName)) {
            die('Неверный формат данных в запросе SELECT в запросе SQL');
        }

        $colums;

        foreach ($arrayColums as $key => $value) {

            if (!is_string($value) or ! is_string($key)) {

                die('Неверный формат данных в запросе SQL');
            }
            $colums .= SequrityData::SequrityReturnData($key) . ', ';
            $values .= '\'' . SequrityData::SequrityReturnData($value) . '\', ';
        }
        $colums = substr($colums, 0, -2);
        $values = substr($values, 0, -2);

        $tableName = SequrityData::SequrityReturnData($tableName);
        $insert = "INSERT INTO $tableName ($colums) VALUES ($values)";
        $this->_PDO->query($insert);
    }

    function __set($name, $value) {

        if (!is_string($name) && !is_string($value)) { // проверка на строку
            die('Неверный формат в сеттере');
        }

        $this->$name = $value;
    }

    private function fetchQueryResult($results) {

        $arrResult = $results->fetchAll(PDO::FETCH_ASSOC);

        foreach ($arrResult as $key => $value) {

            $this->$key = $value;
        }
    }
}

Manually escaping values is generally a bad thing to do, you should use prepared statements instead.

When you generate the query, instead of concatenating directly the values you should concatenate placeholders and the same time generate an array with the values and the placeholders as keys.

public function queryInsert($tableName, array $arrayColums) {

    if (!is_array($arrayColums) or ! is_string($tableName)) {
        die('Неверный формат данных в запросе SELECT в запросе SQL');
    }

    $colums = $placeholders = '';
    $values = array();

    foreach ($arrayColums as $key => $value) {

        if (!is_string($value) or ! is_string($key)) {
            die('Неверный формат данных в запросе SQL');
        }
        $colums .= SequrityData::SequrityReturnData($key) . ', ';
        $placeholders .= ':' . SequrityData::SequrityReturnData($key) . ', ';
        $values[':' . SequrityData::SequrityReturnData($key)] = $value
    }
    $colums = substr($colums, 0, -2);
    $placeholders = substr($placeholders, 0, -2);

    $tableName = SequrityData::SequrityReturnData($tableName);
    $insert = "INSERT INTO $tableName ($colums) VALUES ($placeholders)";
    $query = $this->_PDO->prepare($insert);
    $query->execute($values);

}

Also, most of the times is generally not a good idea to call die() or echoing directly from inside a class. What you should do when something unexpected happens is to throw an exception and then on the client code you can catch it, log it and display a friendly error message to the user.

Inside class:

if (!is_string($value) or ! is_string($key)) {
    throw new MysqlAccessException('Неверный формат данных в запросе SQL');
}

Client code:

try {
    $conn->queryInsert(...);
}
catch (MysqlAccessException $e) {
    $logger = new ExceptionLogger();
    $logger->error($e);
    $notifier = new Notifier();
    $notifier->error('Oops! We are sorry but there was an error, please try again later.');
}

It's also a good idea to catch any PDOExceptions inside the class, log them, and then inside the catch block throw a more generic type of exception like MysqlAccessException to catch on the client code. You don't want to catch PDOExceptions on the client code because they are very specific, and if you decide in the future to change the database class and use something else instead of PDO you will have the to update the client code as well.

try {
    $query->execute($values);
}
catch (PDOException $e) {
    $logger = new ExceptionLogger();
    $logger->error($e);
    throw new MysqlAccessException('Unable to execute insert.');
}

An other thing is that you should never hardcode database credentials in your database class. You should pass them through the constructor. A nice idea would be to have a dedicated config class that is responsible for providing the app configuration data by parsing a config file. This will also enable you to decouple the logic from the data and have different config files for production and development environments. An other reason why you don't want to hardcode this kind of data, is that if you use a versioning system like git and you are not the only person that maintains the code you don't want to commit sensitive data to the repository.


Project Euler #1 in C++ I'm learning C++ and currently doing Project Euler challenges. The first challenge is the following.

  If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

  Find the sum of all the multiples of 3 or 5 below 1000.

I did a quite simple and stupid brute-force implementation by just looping from 1 to 999, checking if its divisible by either 3 or 5 and if it is, sum it with the result variable.

Is there any faster/better/cleaner implementation, maybe without a loop or with less division?

#include <iostream>

int main(int argc, char *argv[])
{
    int result(0);
    for (int i = 1; i < 1000; ++i) {
        if (!(i % 3 && i % 5)) {
            result += i;
        }
    }
    std::cout << "Result: " << result << "\n";
    return 0;
}

The code is basically fine.
The if condition is perhaps a little complicated though. To interpret it you have to read "if not ((i is not a multiple of 3) and (i is not a multiple of 5))", which is a double negative.
Given the problem statement, we'd expect something more like "if (i is a multiple of 3) or (i is a multiple of 5)", so:
if ((i % 3 == 0) || (i % 5 == 0))

Nitpicking:

If we don't need argc and argv, we can declare main as int main() with no arguments.
The return 0; at the end of main happens automatically in C++, so we don't have to write it ourselves.

Note that there exists an arithmetic solution to the problem, which is much faster (it could even be done at compile-time in C++).

We want to sum all the multiples of 3 or 5 less than 1000. We can think about the sequence of multiples of 3 as (3, 6, 9, 12, 15, ..., 999), which is the same as 3 * (1, 2, 3, 4, 5, ..., 333). [...]
Such a sequence, where the difference between each number is constant, is called a finite arithmetic progression [and the sum is] a finite arithmetic series. The formula for the sum is 1/2 * n * (a_1 + a_n). where n is the number of terms being added, a_1 is the first element in the sequence, and a_n is the last element in the sequence.


LeetCode 76: Minimum Window Substring I'm posting an sliding window problem of LeetCode (Minimum Window Substring) with C++. If you have time and would like to review the code, please do so, I appreciate that.
On LeetCode, we are only allowed to change the variable names and brute force algorithms are discouraged, usually fail with TLE (Time Limit Error) or MLE (Memory Limit Error).
Problem

Given a string base_string and a string target, find the minimum window
in base_string which will contain all the characters in target in
complexity O(n).
Example:
Input: base_string = "ADOBECODEBANC", target = "ABC" Output: "BANC"
Note:
If there is no such window in base_string that covers all characters in
target, return the empty string "". If there is such window, you are
guaranteed that there will always be only one unique minimum window in
base_string.

C++
class Solution {
public:
    string minWindow(string base_string, string target) {
        vector<int> count_map(128, 0);

        for (auto character : target)
            count_map[character]++;

        int left = 0, right = 0;
        int min_left = 0, min_right = INT_MAX;
        int target_length = target.size();

        while (right < base_string.size()) {
            if (count_map[base_string[right++]]-- > 0)
                target_length--;

            while (target_length == 0) {
                if (right - left < min_right)
                    min_right = right - (min_left = left);

                if (count_map[base_string[left++]]++ == 0)
                    target_length++;

            }
        }

        return min_right == INT_MAX ? "" : base_string.substr(min_left, min_right);
    }
};

Reference

Question

Solution

Discussion

In the following code, I tried two modifications.

I slightly modified the way tests are performed, in order to minimize them a little bit

I used iterators, like this :auto p_str = base_string.begin() + right;

with the idea to avoid a redirection here:
count_map[*p_str++]--;

instead of
count_map[base_string[right++]]--;

At the end, we cannot be sure how much the speed has been improved. A benchmark is needed (by LeetCode?). We can only be sure that the code is more difficult to read!
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

std::string minWindow(std::string base_string, std::string target) {
    std::vector<int> count_map(128, 0);
    int n = base_string.length();

    for (auto character : target)
        count_map[character]++;

    int left = 0, right = 0;
    int min_left = 0, min_right = n+1;
    int target_length = target.size();

    while (right < n) {
        auto p_str = base_string.begin() + right;
        while (target_length > 0 && p_str != base_string.end()) {
            if (count_map[*p_str++]-- > 0)
                target_length--;
        }
        right = p_str - base_string.begin();

        if (target_length == 0 && right - left < min_right)
                min_right = right - left;

        p_str = base_string.begin() + left;
        while (target_length == 0) {
            if (count_map[*p_str++]++ == 0) {
                left = p_str - base_string.begin() - 1;
                if (right - left < min_right)
                    min_right = right - (min_left = left);
                target_length++;
            }
        }
        left = p_str - base_string.begin();
    }
    if (target_length == 0 && (right - left < min_right))
        min_right = right - (min_left = left);

    return min_right == n ? "" : base_string.substr(min_left, min_right);
}

int main() {
    std::string s = "XXXABYYCTTTABYC";
    std::string target = "CBA";
    std::cout << minWindow (s, target) << "\n";

}


ROT13 encoder/decoder This is a simple utility, intended to sit on the desktop for when needed, that does the simple ROT13 encoding and decoding.

I am used to coding in VBA, and I am interested in more .Net idiomatic coding styles.

Public Class Rot13Decoder

    Private Sub TextBox1_TextChanged(sender As Object, e As EventArgs) Handles txtRotEntry.TextChanged
        lblResult.Text = Rot13(txtRotEntry.Text)
    End Sub

    Function Rot13(Source As String) As String
        Dim i As Long
        Dim result As String = ""

        For i = 0 To Source.Length - 1
            Dim myChar As Char
            myChar = Source.Substring(i, 1)

            Select Case myChar ' originally used Asc(Source(i)), hence the integers below
                Case "a" To "m", "A" To "M" '65 To 77, 97 To 109
                    result &= Chr(Asc(myChar) + 13) 'Chr(Asc(Source(i)) + 13)
                Case "n" To "z", "N" To "Z" '78 To 90, 110 To 122
                    result &= Chr(Asc(myChar) - 13) 'Chr(Asc(Source(i)) - 13)
                Case Else
                    result &= myChar
            End Select
        Next

        Return result
    End Function

    Public Sub New()

        ' This call is required by the designer.
        InitializeComponent()

        ' Add any initialization after the InitializeComponent() call.

    End Sub
End Class

(The title of the form says decoder, and I am using it in the example to encode!)

Double clicking on the form result label copies the text to the clipboard for use.

The number one problem here is that you concatenate translated letters on to your string one at a time.  Since strings are immutable in .NET (and most right thinking languages), this means for the first translated character your program allocates space for a new string of length 1 (copying the previous 0-char string), for the second character it allocates space for a new string of length 2 (copying the previous 1-char string), for the third character it allocates space for a new string of length 3 (copying the previous 2-char string), and so on.  The end result is that for an input n characters long, your program will allocate 1 + 2 + 3 + ... + n = \$O(n^2)\$ space and, similarly, perform \$O(n^2)\$ operations!  A better structure is to use a .NET StringBuilder which is designed precisely for this piecemeal kind of string construction.  Using a StringBuilder your program will allocate \$O(n)\$ space and perform \$O(n)\$ operations -- that's a big saving when your input is of any non-trivial length.


A/B testing using chi-square to calculate the significance in an elegant way The definition of ABtest

Goal:

For input data, each pair row is a group such as 0 and 1, 2 and 3. I want to test whether each group is significant using chi-square.

If result is significant and any value in group is more than or equals 5 , it returns p-value, else it returns 'not significant'.
If any value in group is less than 5, it returns 'sample size too small'.

My question is:

My code seems so long and not so elegant and want to be more simple.

Notice: please don't use column grp as raw input to rewrite like groupby method because the raw data is not named a1 ca1, b1 cb1 . But I make sure each pair row (e.g. 0 and 1, 2 and 3) is a group.

Code:

import numpy as np
from scipy.stats import chi2_contingency
from itertools import chain, repeat

def abtest(df,tot,convert):
    df = df.copy()
    df['nonconvert'] = df[tot] - df[convert]
    grp = np.split(df.index.values,df.index.size//2)
    rst = []
    for g in grp:
        obs = df.loc[g][[convert,'nonconvert']].values
        if (obs>=5).all():
             _, p, _, _=chi2_contingency(obs)
             if p<0.05:
                rst.append(p)
             else:
                rst.append('not significant')
        else:
            rst.append('sample size too small')
    rate = tot + '_' + convert + '_'+'test'
    df[rate] = list(chain.from_iterable(zip(*repeat(rst, 2))))
    del df['nonconvert']
    return df

df = abtest(df=df,tot='tot',convert='read')
df = abtest(df=df,tot='tot',convert='lgn')
df = abtest(df=df,tot='lgn',convert='read')

Input:

   grp    tot  lgn  read
0   a1   6300  360    30
1  ca1   2300   60     7
2   b1  26300  148     6
3  cb1  10501   15     3
4   c1  74600   36     2
5  cc1  26000    6     1

Output:

   grp    tot  lgn  read          tot_read_test     tot_lgn_test  \
0   a1   6300  360    30        not significant      4.68208e-09
1  ca1   2300   60     7        not significant      4.68208e-09
2   b1  26300  148     6  sample size too small      7.01275e-08
3  cb1  10501   15     3  sample size too small      7.01275e-08
4   c1  74600   36     2  sample size too small  not significant
5  cc1  26000    6     1  sample size too small  not significant

           lgn_read_test
0        not significant
1        not significant
2  sample size too small
3  sample size too small
4  sample size too small
5  sample size too small

When you have a finite number of members in a group A and B. Instead of split into groups, hstack the DataFrame like this:

pd.concat(
    [
        df[df.index % 2 == 0].add_prefix('a_').reset_index(),
        df[df.index % 2 == 1].add_prefix('b_').reset_index()
    ], axis=1
)

    a_grp   a_tot   a_lgn   a_read  index   b_grp   b_tot   b_lgn   b_read
0   0   a1  6300    360 30  1   ca1 2300    60  7
1   2   b1  26300   148 6   3   cb1 10501   15  3
2   4   c1  74600   36  2   5   cc1 26000   6   1

Now you can replace the for-loop with 'a_' and 'b_' and df.apply() like

df.apply(apply_chi2)

def apply_chi2(df_ab):
  if df_ab['a_'+convert] > df_ab['a_'+'nonconvert']:
     return ...
  obs = df_ab.a
  return _, p, _, _=chi2_contingency(obs)


Scala implicit conversion to add methods to Int I started learning Scala, and like most functional languages, things get messy pretty quickly for a beginner.

Here I have built a wrapper class for Ints so that I can declare additional functions for the Int class. For example, I want to be able to do something like 1.isPrime, and it should call a function that tells me if the given number is prime or not.

Here is my code:

package object Arithmetic {
    trait S99Int { me =>
        var value: Int = 0
        implicit def int2S99Int(value: Int):me.type = {
            me.value = value; me
        }
    }
}

The above creates the implicit conversions that enable any class that conforms to the trait, to be able to declare additional functions for Ints. For example, I can now do this:

import Arithmetic._

object S99IntPrime extends S99Int {
    import scala.math.{sqrt, abs}

    def isPrime: Boolean = value match {
        case -1|0|1 => false
        case p      => Stream.cons(2,
        Stream.range(3, sqrt(abs(p)).toInt + 1, 2)) forall (p % _ != 0)
    }

    def main(args: Array[String]): Unit = {
        println(args.head.toInt.isPrime)
    }
}

I am mostly asking this question about the first snippet I posted. What are the advantages/disadvantages with declaring the base object like I have? Recommendations? Warnings? I just started learning Scala, so any advice will save me hours of Googling.

First of all, what Scala version are you using? If you're using 2.10 or newer versions, the language has introduced implicit classes which help you avoid the definition of implicit conversions - as a side note implicit classes are translated to implicit conversions by the compiler so let's say they are some type of syntactic sugar.

As you might now, the implicit modifier cannot be used on top-level definitions - that includes implicit classes as well, so we must wrap them in a class / trait / object. As a best practice it's best to put them in an object (or package object like you did). The other constraints of implicit classes are already explained in the first link, so I won't go through them here.

A final note before we get to the code is that you will often see that implicit classes are used as value classes. Please consult this post if you're curious to see how when you should mix them with value classes.

Enough talk, let's see the code now:

package object arithmetic {
  implicit class RichInt(val value: Int) extends AnyVal {
    def isPrime: Boolean = ???
  }
}

object ArithmeticTest extends App {
  import arithmetic._
  1.isPrime
}

That's it! Hope it helps.


Computing even huger Fibonacci numbers in Java See the next iteration.

I have that method for computing Fibonacci numbers \$F_n\$ (\$n = 0, 1, 2, \dots)\$, that relies on computing

$$
A =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n.
$$

The solution is then read from \$A_{1,2}\$. Now I can easily compute, for instance, \$F_{100000}\$.

However, in this code snippet, I need not just large integer additions, but multiplications as well, and looking at the source code of multiplication of two BigIntegers, it becomes evident that the algorithms are more smart and efficient than I could ever do.

What comes to the complexity of this approach, we need only \$\Theta(\log n)\$ matrix multiplications. Assuming that multiplying two (largest in the computation) BigIntegers takes time \$\mathcal{O}(f(n))\$, the complexity of the entire algorithm is \$\mathcal{O}(f(n) \log n)\$.

import java.math.BigInteger;

public class LargeFibonacciNumbers {

    public static String fibonacci(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                    "The (" + n + ")th Fibonacci number is not defined.");
        }

        switch (n) {
            case 0:
                return "0";

            case 1:
                return "1";
        }

        BigInteger[][] matrix = new BigInteger[2][2];

        matrix[0][0] = BigInteger.ONE;
        matrix[0][1] = BigInteger.ONE;
        matrix[1][0] = BigInteger.ONE;
        matrix[1][1] = BigInteger.ZERO;

        return fibonacciMatrix(matrix, n)[0][1].toString();
    }

    private static BigInteger[][] multiply(BigInteger[][] matrix1,
                                           BigInteger[][] matrix2) {
        BigInteger[][] ret = new BigInteger[2][2];

        ret[0][0] = matrix1[0][0].multiply(matrix2[0][0])
               .add(matrix1[0][1].multiply(matrix2[1][0]));

        ret[0][1] = matrix1[0][0].multiply(matrix2[0][1])
               .add(matrix1[0][1].multiply(matrix2[1][1]));

        ret[1][0] = matrix1[1][0].multiply(matrix2[0][0])
               .add(matrix1[1][1].multiply(matrix2[1][0]));

        ret[1][1] = matrix1[1][0].multiply(matrix2[0][1])
               .add(matrix1[1][1].multiply(matrix2[1][1]));

        return ret;
    }

    private static BigInteger[][]
        fibonacciMatrix(BigInteger[][] matrix, int n) {
        if (n == 1) {
            // End the recursion.
            return matrix;
        }

        if ((n & 1) == 1) {
            // 'n' is odd.
            return multiply(matrix, fibonacciMatrix(matrix, n - 1));
        }

        // 'n' is even.
        BigInteger[][] tmp = fibonacciMatrix(matrix, n >> 1);
        return multiply(tmp, tmp);
    }

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

        if (args.length > 0) {
            try {
                n = Integer.parseInt(args[0]);
            } catch (NumberFormatException ex) {

            }
        }

        System.out.println(fibonacci(n));
    }
}

So, what do you think?

public static String fibonacci(int n) {

Why? It makes far more sense for this method to return a BigInteger.

        if (n < 0) {
            throw new IllegalArgumentException(
                    "The (" + n + ")th Fibonacci number is not defined.");
        }

Negative-index Fibonacci numbers are perfectly well defined, so this error message is misleading. You could change the error message to something like "Negative indexes are not supported", but you might as well change the code to support them. It's just a case of negating n and using initial matrix [[0 1][1 -1]].

        switch (n) {
            case 0:
                return "0";

            case 1:
                return "1";
        }

I can understand having a special case for 0 because it saves you a special case in the matrix power code, but why the special case for 1?

    private static BigInteger[][]
        fibonacciMatrix(BigInteger[][] matrix, int n) {

The name of this method makes no sense to me. Why isn't it called pow or matrixPower?

        if ((n & 1) == 1) {
            // 'n' is odd.
            return multiply(matrix, fibonacciMatrix(matrix, n - 1));
        }

        // 'n' is even.
        BigInteger[][] tmp = fibonacciMatrix(matrix, n >> 1);
        return multiply(tmp, tmp);

Your argument in favour of recursion in the comments on an earlier answer is out by a factor of two, because you're potentially making twice as many calls as there are bits in n. Even if you don't want to do things iteratively, it makes sense to rewrite this as

        BigInteger[][] tmp = fibonacciMatrix(matrix, n >> 1);
        tmp = multiply(tmp, tmp);
        if ((n & 1) == 1) {
            tmp = multiply(matrix, tmp);
        }
        return tmp;

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

        if (args.length > 0) {
            try {
                n = Integer.parseInt(args[0]);
            } catch (NumberFormatException ex) {

            }
        }

        System.out.println(fibonacci(n));
    }

If I supply no command-line arguments, or if I supply an invalid one, the output is The (-1)th Fibonacci number is not defined. That doesn't help me at all with figuring out my mistake. I'd rather have the NumberFormatException!


HackerRank - Insertion Sort - Part 2 This is the problem statement for Insertion Sort - Part 2.

In Insertion Sort Part 1, you sorted one element into an array. Using the same approach repeatedly, can you sort an entire unsorted array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that
in the first step, when you consider an element with just the first element - that is already "sorted" since there's nothing to its left that is smaller
than it.

In this challenge, don't print every time you move an element. Instead, print the array every time an element is "inserted" into the array in (what is
currently) its correct place. Since the array composed of just the first element is already "sorted", begin printing from the second element and on.

Actually just an insertion sort implementation with ints and vector. How can I make this code faster? How can I improve this code?

#include <vector>
#include <iostream>

void print(const std::vector<int>& v) {
    for (auto x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

int main() {
    int s;
    std::cin >> s;
    std::vector<int> sorted(s);
    int i = 0;
    while (std::cin && i != s) {
        std::cin >> sorted[i++];
    }
    for (std::size_t i= 1; i < sorted.size(); ++i) {
        std::size_t j = i;
        for (std::size_t k = 0; k < j; ++k) {
            if (sorted[j] < sorted[k]) {
                std::swap(sorted[j],sorted[k]);
            }
        }
        print(sorted);
    }
}

Probably the single biggest (or most obvious, anyway) improvement would be to write an actual insertion sort. What you have right now appears to be a bubble sort rather than an insertion sort.

Rather than swapping elements that are out of order an insertion sort divides the array into a sorted part and an unsorted part. In the beginning, the sorted part is just the first element. Then it looks at the first element of the unsorted part, copies it into a temporary location, and copies elements in the sorted part "forward" a spot until it gets to an element smaller than the temporary. That makes a "hole" for the new element to go into, and it puts that element there (then repeats for the remaining unsorted elements).

Given an array v of n elements, the loops look something like this:

for (int i=1; i<n; i++) {
    tmp = v[i];
    int j;
    for (j=i; j>0 && tmp<v[j-1]; j--)
        v[j] = v[j-1];
    v[j] = tmp;
}


Yet another boring FizzBuzz I've just finished my first program written in Java. It's a simple, boring, yet well-known FizzBuzz challenge where you have to:

  Write a program that prints the numbers from 1 to 100. But for
  multiples of three print “Fizz” instead of the number and for the
  multiples of five print “Buzz”. For numbers which are multiples of
  both three and five print “FizzBuzz”."

I know there are some other FizzBuzz questions here, but I'd really like to start learning Java in the right way, which means that I'm looking for:

Naming conventions
Coding standards and best practices

Coming from Python world, I was tempted to create a separate method named fizzBuzz() which I then called in my main() method. Is this a bit overkill for such a simple task?

package fizzbuzz;

class FizzBuzz {
/*
    Write a program that prints the numbers from 1 to 100. But for multiples of
    three print “Fizz” instead of the number and for the multiples of five print
    “Buzz”. For numbers which are multiples of both three and five print
    “FizzBuzz”."
 */

    public static void fizzBuzz() {
        for(int i = 1; i <= 100; i++) {
            if (i % 3 == 0 && i % 5 == 0)
                System.out.println("FizzBuzz");
            else if (i % 3 == 0)
                System.out.println("Fizz");
            else if (i % 5 == 0)
                System.out.println("Buzz");
            else
                System.out.println(i);
        }
    }

    public static void main(String[] args) {
        fizzBuzz();
    }
}

Coming from Python world, I was tempted to create a separate method named fizzBuzz() which I then called in my main() method. Is this a bit of overkill for such a simple task ?

Well, it is a little bit too much for such a simple task, but it is a good habit to do so and if I were you I would stick to it.

Overall your fizzBuzz looks good.

Naming -> Check

but

Best Practices -> Fail

This is because you omitted braces {} although they are optional for single instruction if, else if and else branches.

Omitting the braces can lead to hidden, and therefore hard to find bugs. I would like to encourage you to always use them.

Another thing is that you have some magic numbers, like 1, 100, 3, and 5 in your code which should either be extracted to some meaningful named constants, or passed to the method as parameters.

You could add a isDivisibleBy(int value, int divider) method as well to make the responsibilities clear.


Binary search on a Bitonic array So, I have been preparing for an interview and I thought of coding up a Binary search on a Bitonic array for practice. A bitonic array has a bunch of numbers in increasing order at the beginning of the array and then a bunch of numbers in decreasing order after that. And the problem is to find out whether or not a number exists in the Bitonic array.

import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;
public class Bitonic{
    private Integer[] array;

    // This is the maximum possible number in the array.
    private int maxPossibleValue = 45645454;

    public Bitonic(int n, int inv)
    {
        // Make a n element array and initialize each position with a random value.
        array = new Integer[n];
        for(int i = 0; i < n; i++){
            array[i] = (int)Math.floor(Math.random() * maxPossibleValue);
        }

        // inv is the inversion point where the numbers stop increasing and start decreasing.
        // To make this artificially happen, I sorted one half of the array in ascending order
        // And the other half in descending.
        Arrays.sort(array, 0, inv);
        Arrays.sort(array, Math.min(inv + 1, n), n, Collections.reverseOrder());

        // Print the array.
        System.out.println(Arrays.toString(array));
    }

    private int finder(int target, int start, int end){
    System.out.printf("Processing: %d to %d\n", start, end);
    int currentPoint = (int)Math.floor(end + start)/2;
    int left = Math.max(start, currentPoint - 1);
    int right = Math.min(end, currentPoint + 1);
    int leftValue = array[left];
    int rightValue = array[right];
    int currentValue = array[currentPoint];
    if(currentValue == target){
        System.out.println("Found the value.");
        return currentPoint;
    }
    if(start == end && currentValue != target){
        return -1;
    }
    if(currentValue > leftValue && currentValue < rightValue){
        // Behind inversion point.
        if(currentValue < target){
            return finder(target, right, end);
        }
        else{
            int result = finder(target, start, left);
            if(result != -1){
                return result;
            }
            return finder(target, right, end);
        }
    }
    else if(currentValue < leftValue && currentValue > rightValue){
        // After inversion point.
        if(currentValue < target){
            return finder(target, start, left);
        }
        else{
            int result = finder(target, right, end);
            if(result != -1){
                return result;
            }
            return finder(target, start, left);
        }
    }
    else{
        // At inversion point or at one of the extreme corners or a plateau.
        int result = finder(target, right, end);
        if(result != -1){
            return result;
        }
        return finder(target, start, left);
    }
}

    public int find(int target){
        // Set up the recursion for the binary search.
        return finder(target, 0, array.length - 1);
    }

    public int get(int location){
        return array[location];
    }
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n, inv;
        n = reader.nextInt();
        inv = reader.nextInt();
        Bitonic BitonicArray = new Bitonic(n, inv);

        int targetLoc = reader.nextInt();
        int target = BitonicArray.get(targetLoc);
        System.out.printf("Value Queried: %d\n", target);
        int result = BitonicArray.find(target);
        if(result != -1)
            System.out.printf("Found it at: %d, value at that location: %d", result, BitonicArray.get(result));
        else
            System.out.println("Not found.");

    }
}

maxPossibleValue seems to be an instance-independent constant and should therefore be static and final (and, as such, should conventionally be in uppercase letters with words being separated by an underscore character, i.e. MAX_POSSIBLE_VALUE).
array[i] = (int)Math.floor(Math.random() * maxPossibleValue);

The problem with this line is that the array will never contain maxPossibleValue itself, because the value returned by Math.random() will always be less than, but never equal to 1.0. Besides, there is a simpler way of accomplishing what you want: Instead of using Math.random(), use an instance of Random:

Random randomGenerator = new Random();
for(int i = 0; i < n; i++){
    array[i] = randomGenerator.nextInt(maxPossibleValue + 1);
}

Your method of sorting the array doesn't work correctly. First of all, the integer at the index inv will never be modified, because your first sort only sorts the indexes 0 to inv - 1 and the second sort sorts the indexes inv + 1 to n - 1 (the end index passed to the sort method is exclusive).

But even if you corrected this issue, the problem remains that you still don't know which of the two adjacent indices contains the greater integer. For example, when you have the array {1,2,3,4,5} and define 2 as the inversion point index (i.e. the third number in the array), and sort the first three numbers and the last two numbers separately, then you will get {1,2,3,5,4}, meaning the inversion point will be 3 instead of 2. If you really want to ensure that the number at the inversion point will be the largest number in the array, I don't think you will get around doing that manually, i.e. finding the largest number in the array and moving it to the inversion point by swapping it with the number previously there.
The constructor Bitonic(int, int) does not check whether the passed arguments are valid. If it did, you would not need to use expressions like Math.min(inv + 1, n) when you sort the numbers on the right side of the inversion point (regardless of the fact that the sorting algorithm does not work correctly, as I previously pointed out).
int currentPoint = (int)Math.floor(end + start)/2;

There are several problems with this line. First, you probably forgot a pair of parentheses around the expression (end + start)/2. But even so, wrapping (end + start)/2 in Math.floor(double) is pointless, because (end + start)/2 already returns an integer (see here).

Finally, you are risking an integer overflow with end + start. A way to prevent this would be to write start + (end - start)/2 instead (this is only guaranteed not to overflow if end >= start).
This:

if(currentValue < target){
    return finder(target, right, end);
}
else{
    int result = finder(target, start, left);
    if(result != -1){
        return result;
    }
    return finder(target, right, end);
}

can be written more concisely as:

int result;
if (currentValue >= target
        && (result = finder(target, start, left)) != -1) {
    return result;
} else {
    return finder(target, right, end);
}

The same goes for the analogous code when currentValue lies after the inversion point.

Update

Another thing just occurred to me: You can save unnecessary recursive calls if you changed the conditions of your two if blocks for being before and after the inversion point to allow one (but not both) of the two adjacent values to be equal to the current value. For example, if you are looking for the number 5 in the array {0,5,4,4,3,2,1}, and currentPoint == 3, so that leftValue == 4, currentValue == 4 and rightValue == 3, your program would enter the final else block and pointlessly search the numbers to the right of currentPoint.

So instead, you could change the conditions to something like this:

if(leftValue <= currentValue
        && currentValue <= rightValue
        && leftValue != rightValue)


Optimization of "def do_GET(self)" This code works nicely for my purposes, but I would like to improve it exponentially.

What are some steps I can take?  I'm interested in optimization, refactoring, and clean-code.

  def do_GET(self):
    qs = {}
    path = self.path
    print path
    if path.endswith('robots.txt'):
      self.send_response(500)
      self.send_header('Connection', 'close')
      return
    if '?' in path:
      path, tmp = path.split('?', 1)
      qs = urlparse.parse_qs(tmp)
      print path, qs
    if 'youtube' in path:
     ID = qs.get('vID')
     LTV = qs.get('channelID')
     EMAIL = qs.get('uEmail')
     TIME = qs.get('Time')
     userID = qs.get('uID')
     URL = qs.get('contentUrl')
     channelID = str(LTV)[2:-2]
     print channelID
     uEmail = str(EMAIL)[2:-2]
     print uEmail
     ytID = str(ID)[2:-2]
     print ytID
     ytURL = str("https://www.youtube.com/tv#/watch?v=%s" % ytID)
     print ytURL
     uTime = str(TIME)[2:-2]
     print uTime
     uID = str(userID)[2:-2]
     print uID
     contentUrl = str(URL)[2:-2]
     print contentUrl
     if sys.platform == "darwin":
      subprocess.Popen('./killltv', shell=True)
      sleep(1)
      subprocess.Popen('./killltv', shell=True)
      sleep(1)
      subprocess.Popen('./test.py %s'%ytURL, shell=True)
     elif sys.platform == "linux2":
      subprocess.Popen('./killltv', shell=True)
      sleep(1)
      subprocess.Popen('./test.py %s'% ytURL, shell=True)
    #subprocess.Popen('chromium-browser https://www.youtube.com/tv#/watch?v=%s'% ytID, shell=True)
      sleep(2)
    #subprocess.Popen("./fullscreen", shell=True)
     elif sys.platform == "win32":
      os.system('tskill chrome')
      browser = webbrowser.open('http://youtube.com/watch?v="%s"'% ytID)
      log.warn("'%s':,video request:'%s' @ %s"% (channelID, ytID, time))
    #playyt = subprocess.Popen("/Users/Shared/ltv.ap

How about using

IS, LTV, EMAIL, TIME, userID, URL  = map(\
    qs.get, ['vID', 'channelID', 'uEmail', 'Time', 'uID', 'contentUrl'])

channelID, uEmail, ytID, uTime, uID, contentUrl = map(\
    lambda x : str(x)[2:-2], [LTV, EMAIL, ID, TIME, userID, URL])

for i in (channelID, uEmail, ytID, uTime, uID, contentUrl):
    print i

ytURL = str("https://www.youtube.com/tv#/watch?v=%s" % ytID)
print ytURL

instead of

ID = qs.get('vID')
LTV = qs.get('channelID')
EMAIL = qs.get('uEmail')
TIME = qs.get('Time')
userID = qs.get('uID')
URL = qs.get('contentUrl')
channelID = str(LTV)[2:-2]
print channelID
uEmail = str(EMAIL)[2:-2]
print uEmail
ytID = str(ID)[2:-2]
print ytID
ytURL = str("https://www.youtube.com/tv#/watch?v=%s" % ytID)
print ytURL
uTime = str(TIME)[2:-2]
print uTime
uID = str(userID)[2:-2]
print uID
contentUrl = str(URL)[2:-2]
print contentUrl

The first one just prints ytURL at the end but it can be changed easily if you really want. Other than that they do the same thing. But I am sure the first one is much easier to modify and maintain.

Other than that I can only say after I know what this program is about.

It might also be a good idea to keep os-specific functions(like you are doing after checking for the os) into separate functions. It would make maintaining and modifying the code much easier.

You should also read PEP8, particularly the part about code-layout. Your indentation is not good.

What I meant was that this can be converted into

if sys.platform == "darwin":
      subprocess.Popen('./killltv', shell=True)
      sleep(1)
      subprocess.Popen('./killltv', shell=True)
      sleep(1)
      subprocess.Popen('./test.py %s'%ytURL, shell=True)
elif sys.platform == "linux2":
      subprocess.Popen('./killltv', shell=True)
      sleep(1)
      subprocess.Popen('./test.py %s'% ytURL, shell=True)

this equivalent structure

OS_DETAIL = { 'darwin' : 2, 'linux2' : 1}
for i in xrange(OS_DETAIL[sys.platform]):
    subprocess.Popen('./killltv', shell=True)
    sleep(1)
else:
    subprocess.Popen('./test.py %s'% ytURL, shell=True)

It doesn't solve the complete problem because I am not sure whether you'll need those commented statements or not. If the sleep(2) is actually needed in case of linux2 then you can store a tuple in the OS_DETAILS dictionary. But the problem with this approach is your win32 part. It is totally different. It can be taken care of using an structure like this.

if sys.platform in ['darwin', 'linux2`]:
    #place the code I have just suggested for these 2
elif sys.platform == "win32"
    #place your code for win32

But as you can see this isn't the best way. It is better than the current solution but if the code for win32 can be refactored in some way (I don't know its functionality so don't ask) to fit the same pattern then it all comes down to a simple dictionary and a loop structure.


Parsing /proc/net/sockstat I have this very simple code which is used to parse values:

public class Connections
{
    public List<Integer> getConnections() throws IOException
    {
        byte[] fileBytes;
        File myFile = new File("/proc/net/sockstat");
        if (myFile.exists())
        {
            try
            {
                fileBytes = Files.readAllBytes(myFile.toPath());
            }
            catch (java.nio.file.AccessDeniedException e)
            {
                return null;
            }

            if (fileBytes.length > 0)
            {
                String doc = new String(fileBytes);

                Pattern p = Pattern.compile("-?\\d+");
                Matcher m = p.matcher(doc);

                List<Integer> list = new ArrayList<>();
                while (m.find())
                {
                    list.add(Integer.valueOf(m.group()));
                }

                return list;
            }
        }
        return null;
    }

}

This code works well but it's using too many slow operations to get the values. Is there a way to improve the code? I would like to use Java 8.

This code works well but it's using too many slow operations to get the values.

Not sure what really bugs you:

You read the entire file with a single Files.readAllBytes. Doesn't get faster than that. If the file is huge, I imagine this could take time, but if you want the entire file, there's just no way around it
You convert the byte[] to a String so that you can use a Pattern + Matcher. The alternative I see would be parsing the digits by yourself, but that wouldn't be as optimized as the built-in regex engine, so you won't be better off
I imagine the number parsing and Integer object creation might cost you a couple of extra cycles. But I don't see an alternative to make that significantly faster

My point is, if you want to read and parse the entire file,
and store the result in a List,
then I don't think it can get much faster than this.

  Is there a way to improve the code?

When a method is expected to return a List or other collection type,
it's good to avoid returning null values,
as that forces the caller to add null checks.
A more ergonomic solution is to return an empty list,
for example Collections.emptyList().

Code is usually easier to read when not so deeply nested.
The majority of the method is nested within a if (myFile.exists()) { ... } block.
If you flip this condition and return early, you can reduce the nesting level.

It's better to declare variables in the most limited scope where they are used.
In this example the byte[] fileBytes is only used if the file exists,
so you could declare it later.

Putting these tips together, the method body becomes:

List<Integer> list = new ArrayList<>();
File myFile = new File("/proc/net/sockstat");
if (!myFile.exists()) {
    return list;
}

byte[] fileBytes;
try {
    fileBytes = Files.readAllBytes(myFile.toPath());
} catch (java.nio.file.AccessDeniedException e) {
    return list;
}

if (fileBytes.length <= 0) {
    return list;
}

String doc = new String(fileBytes);

Pattern p = Pattern.compile("-?\\d+");
Matcher m = p.matcher(doc);

while (m.find()) {
    list.add(Integer.valueOf(m.group()));
}

return list;

Also, the convention is to put opening braces on the same line as their statement,
not on the next line as you did (C# style).

Finally, the variable names are kind of fishy.
Single letter names like p and m are considered a bad practice,
and doc doesn't seem to give a clue about what this variable is about.

Alternative approach

Although as I wrote above,
if you want to read and parse a large file it's bound to be slow,
but there's a different approach that might still help.

Instead of reading the entire file at once (time-consuming),
you could read part of the file and return results as you go.
You could do this using the iterator pattern:

Create a class that implements the Iterator interface
Use an internal buffer to store the next chunk of the file
When hasNext is called, check if there is still data left in the buffer, or read in the next chunk
When next is called, return the next integer

This approach has the following advantages over the original:

Instead of waiting for the entire file to be processed, users of the iterator can start processing sooner. That is, when you read the entire file at once, it may seem to the user that the program freezes for a couple of seconds. If you process chunk by chunk, this doesn't happen
If the user of the iterator stops in the middle, the rest of the file won't be read and parsed unnecessarily
Since the integers don't need to be stored in a list anymore, you can reduce the memory use dramatically

Potential disadvantages:

More work to implement. (Or, you could play with a Scanner)
If you always need to read in the entire file, then it will be more efficient to do it once and be done with it, like the original code


Traffic speed limit check for intervals Given 2 lists of tuples limits and speeds, both have the format of [(speed1, time1), (speed2, time2)]. My goal is to write a function to check whether the there is a period of time that the speed exceeds the limit (Return True if exceeds).
For example, Given limits = [(50,100), (30, 20)], speeds = [(30, 80), (10, 30), (40, 10)], return True.

The example inputs imply that during the first 100 miles, the speed limit is 50. In the 101-120 mile, speed limit is 30. Since in the speeds list, the last 10 miles have speed 40 > 30, so we return True.

We can assume the inputs are valid, so the limits and speeds list always start and end at the same time.

Can I have some pointers on the correctness and how the code can be refactored?

def speed_check(limits, speeds):
  i, j = 0, 0
  prev_limit_range, prev_speed_range = 0, 0
  while j < len(speeds) and i < len(limits):
    if limits[i][0] < speeds[j][0]:
      return True
    if limits[i][1] + prev_limit_range < speeds[j][1] + prev_speed_range:
      prev_limit_range += limits[i][1]
      i += 1
    elif limits[i][1] + prev_limit_range > speeds[j][1] + prev_speed_range:
      prev_speed_range += speeds[j][1]
      j += 1
    else:
      prev_limit_range += limits[i][1]
      prev_speed_range += speeds[j][1]
      i += 1
      j += 1

  return False

assert speed([(30, 15), (55, 20)], [(30, 15), (55, 20)]) == False
assert speed([(30, 15), (55, 20)], [(30, 14), (65, 20)]) == True

First, let's look at your answer with comments:

def speed_check(limits, speeds):
  # Explicit assignment of temporary variables
  i, j = 0, 0
  prev_limit_range, prev_speed_range = 0, 0
  # Assumption that speeds and limits will not change during iteration
  while j < len(speeds) and i < len(limits):
    # Multiple if statements make it so that we can't just swap lines of
    # code without breaking things.
    if limits[i][0] < speeds[j][0]: # speed > limit would be more readable
      return True
    # Operator precedence does not jump to the eye. Use parenthesis
    if limits[i][1] + prev_limit_range < speeds[j][1] + prev_speed_range:
      prev_limit_range += limits[i][1]
      i += 1
    elif limits[i][1] + prev_limit_range > speeds[j][1] + prev_speed_range:
      prev_speed_range += speeds[j][1]
      j += 1
    else:
    # Manual incrementation of local variables.
      prev_limit_range += limits[i][1]
      prev_speed_range += speeds[j][1]
      i += 1
      j += 1

  return False

Python-wise there are multiple parts of your implementation that could be tackled differently. Let's see what we could do.

If you think about this problem graphically, drawing an x-axis for distance and a y-axis for speed, then all you want is to check whether the curve for actual speed ever crosses the curve for speed limits.

You could break down your problem into subparts:

def get_graph(speedlist):
    """Generate a list of tuples into a flatten list as in:
    [(1,2), (3, 4)] -> [1, 1, 3, 3, 3, 3]
    """
    return [item for x in [y[1]*[y[0]] for y in speedlist] for item in x]

def check_exceeds(speeds, limits):
    speed_graph = get_graph(speeds)
    limits_graph = get_graph(limits)
    return any([x > y for x, y in zip(speed_graph, limits_graph)])

This approach avoids three issues I see in your implementation:  excess of if-statements, explicit indexing, and explicit iteration. Why are these issues? Well, it's easy to make mistakes when indexing and manually iterating, and it's easy to forget possible branches when using if/else clauses. Python offers a lot of tooling so that you don't have to do everything yourself, and it's considered good practice to leverage that tooling to make your code both more readable and safe.

For your assertions, there is also no need to compare to True nor False, in case your function is defined in such a way that it returns a boolean:

assert check_exceeds([(30, 15), (55, 20)], [(30, 15), (55, 20)])
assert not check_exceeds([(30, 15), (55, 20)], [(30, 14), (65, 20)])

(quick answer as I was answering the post in StackOverflow before it migrated)


Elegant Circular Buffer I would like to design an elegant yet efficient circular buffer of integers.
I have designed a FIFO type circular buffer in C++(11)- starting with the class header (declaration) as follow:

[cyclicBuffer.hpp]:

#ifndef __CyclicBuff_HPP
#define __CyclicBuff_HPP
#pragma once

class CyclicBuffer
{
public:
    CyclicBuffer(int buffSize);
    ~CyclicBuffer();
    void setChar(char c);
    char getChar();
    void clearCycBuff(int buffSize);
private:
    char *buffer;
    int bufferSize;
    int head;   // index for the top of the buffer
    int tail;   // indes for the bottom of the buffer
};

#endif

implementation of the class is as following:
[cyclicBuffer.cpp]:

#include "stdafx.h"
#include "cyclicBuffer.hpp"
#include <iostream>

//using namespace std;

CyclicBuffer::CyclicBuffer(int buffSize)
{
    head = 0;
    tail = 0;
    bufferSize = buffSize;
    buffer = new char[bufferSize];
    std::cout << "Buffer initated successfully\n";

/*
    {
        std::cout << "Buffer was not created\n driver exiting...\n";
//      return -1;
    }*/
}

CyclicBuffer::~CyclicBuffer()
{
    delete buffer;
    std::cout << "Buffer destroyed successfully\n";
}

void CyclicBuffer::clearCycBuff(int buffSize)   //not used , has no meaning to set '0'

{
    head = 0;
    tail = 0;
    for (int i = 0; i <= buffSize; i++)
        buffer[i] = '0';
}

void CyclicBuffer::setChar(char c)
{
    //std::cout << "head: " << head << '\n';
    head %= bufferSize;
    buffer[head] = c;
    head++;
}

char CyclicBuffer::getChar(void)
{
    //std::cout << " tail:" << tail<<'\n';
    tail %= bufferSize;
    return buffer[tail++];

}

Finally, testing the class by an instance as follow:

// CyclicBufferMain.cpp : Defines the entry point for the console
// application.

#include "stdafx.h"
#include <iostream>
#include "cyclicBuffer.hpp"

#define SIZE    32

int main(void)
{
    CyclicBuffer aBuffer(SIZE);

    for (int i = 0; i < SIZE*1.5; i++)
        aBuffer.setChar((char)(i+45));

    for (int i = 0; i < SIZE ; i++)
        std::cout << aBuffer.getChar() << ' ';

    std::cout << '\n';

    return 0;
}

for the given main function the result will be like this:

My question: is this class is efficient enough for low-rate uC ? (targeting to Atmel, RISC type or low performance ARM uC)

Regarding @Toby Speight: Thanks for your helpful comments and advices - few questions for you:

(1) when I did delete instead delete [], did I make a 'memory leak'? why MS VStudio (2015) didn't warn me?

(2) I would change the CyclicBuffer::clearCycBuff() member function to use buffer[i] = 0; (instead buffer[i]='0';) to clear the buffer's values.

(3) Why need to drop the commented-out code?

(4) You used uniform initializer at the constructor - is it big difference as to what I did using regular variable assignments at the constructor ?

(5) I know 'size_t' is it a specialize typedef that exists at the GNU and MS compilers but would have a problem using it when porting the code to a specific target which could not have such typedef ?

Thanks.

Improve the wrap-around logic
There's obvious inefficiency in:
head %= bufferSize;

% uses division, but because we're incrementing, we know that head / bufferSize is at most 1.  Instead, we can:
if (++head >= bufferSize)
    head -= bufferSize;

On architectures such as ARM, there's no branch here, as any decent compiler will just use a condition flag on the subtraction.

Consider checking for overrun and underrun
At the moment, this buffer has no checking for the read and write positions crossing each other.  Perhaps that's what you need, but it's quite unusual to have an unchecked circular buffer, and if you were holding (e.g.) audio data, you can imagine how it would sound, given the output you show.

Match new and delete
Since you create buffer using new[], you must use the array form delete[] in the destructor:
CyclicBuffer::~CyclicBuffer()
{
    delete[] buffer;
}

Style points
Prefer initializers to assignment
A constructor should initialize all the members of the class:
CyclicBuffer::CyclicBuffer(std::size_t buffSize)
  : buffer(new char[bufferSize]),
    bufferSize(buffSize),
    head(0),
    tail(0)
{
}

A good compiler will warn you if you have uninitialized members (e.g. g++ -Wall -Wextra).
Note that I've also changed the argument to be a size_t, as a negative size is meaningless.  The int members should all be size_t, too.
Avoid numeric character constants
What's special about the number 45?  If you care about its character value, (and if you're using an ASCII-like system), it's clearer to write '-' instead.
Drop the commented-out code
I don't want to see using std::namespace;, ever.  Not even in a comment.


Handling calculator keypresses I've added decimal (floating point) functionality to my calculator implementation; it's working but I'm having trouble making it more concise and less ugly.

I'm trying to use the same method to handle both number keys and the decimal point, and whichever way I look at it, I either have to check for the button being pressed and then whether the user is just starting a new entry, or the other way around. I've even drawn a flowchart to see how could this be condensed with nested logical operators (||, &&) but couldn't get it to work.

Obviously I could write a separate method for the decimal key, but then I'd get to repeating the isTyping verification there instead. Is there a simple way to do this or is code repetition inevitable at some point or another?

@IBAction func buttonDigit(sender: UIButton) {
    let digit = sender.currentTitle!

    if isTyping {
        if digit == "." {
            if !hasDecimal {
                display.text = display.text! + digit
                hasDecimal = true
            }
        } else {
            display.text = display.text! + digit
        }
    } else {
        if digit == "." {
            display.text = "0" + digit
        } else {
            display.text = digit
        }
        isTyping = true
    }
}

I suggest hooking up the . button to a separate IBAction.  The decimal point isn't a digit, so the function name is confusing.  Furthermore, the code to handle a decimal point has little in common with the code to handle a digit.  There's no point in mashing the code together into the same function.

@IBAction func buttonDecimalPoint(sender: UIButton) {
    if !isTyping {
        display.text = "0."
    } else if !hasDecimal {
        display.text = display.text! + "."
    }
    isTyping = true
    hasDecimal = true
}

@IBAction func buttonDigit(sender: UIButton) {
    if !isTyping {
        display.text = ""
    }
    display.text = display.text! + sender.currentTitle!
    isTyping = true
}

Note that in buttonDecimalPoint, I test if !isTyping rather than if isTyping, so that I can write else if instead of nesting the conditionals like this:

@IBAction func buttonDecimalPoint(sender: UIButton) {
    if isTyping {
        if !hasDecimal {
            display.text = display.text! + "."
        }
    } else {
        display.text = "0."
    }
    isTyping = true
    hasDecimal = true
}

Another benefit is that the not-typing state can be thought of as the "initial" state, so it's more fitting that the code to handle it should come first.

Furthermore, I've moved the = true assignments to the end of each function to make the invariants obvious.  After pressing ., you know that isTyping and hasDecimal are both true.


Draw a centered circle I've written this program that, renders a circle in the middle of the screen. It's been written in a very elementary way.

Any suggestions on principles or techniques? Or any more optimal or efficient ways of drawing circles in C?

I'm using SDL2 (Simple Direct Media Library) and GCC to compile.

#include "SDL.h"
#include <math.h>
#include <stdio.h>

#define PI  3.14159
#define SCR_WDT  1280
#define SCR_HGT  960

const int SCR_CEN_X = SCR_WDT / 2;
const int SCR_CEN_Y = SCR_HGT / 2;

struct Circle
{
    int radius;
    int h; // The X access of the center of the circle.
    int k; // The Y access of the center of the circle.
    int new_x;
    int new_y;
    int old_x;
    int old_y;
    float step;
};

int main ( int argc, char *argv[] )
{
    SDL_Init ( SDL_INIT_VIDEO );
    SDL_Window *window = SDL_CreateWindow ( "Drawing a Circle",       SDL_WINDOWPOS_UNDEFINED,
                                             SDL_WINDOWPOS_UNDEFINED, SCR_WDT, SCR_HGT, 0 );
    SDL_Renderer *renderer = SDL_CreateRenderer ( window, -1, SDL_RENDERER_SOFTWARE );

    Circle circle;
    circle.radius = 200;
    circle.h = SCR_CEN_X;
    circle.k = SCR_CEN_Y;
    circle.new_x = 0;
    circle.new_y = 0;
    circle.old_x = 0;
    circle.old_y = 0;
    circle.step = (PI * 2) / 50;

    bool is_running = true;
    while ( is_running )
    {
        SDL_Event event;
        if ( SDL_PollEvent( &event ))
        {
            if ( event.type == SDL_QUIT )
            {
                is_running = false;
            }
        }

        SDL_RenderClear ( renderer );

        SDL_SetRenderDrawColor ( renderer, 255, 255, 255, 255 );

        for ( float theta = 0; theta < (PI * 2); theta += circle.step )
        {
            circle.new_x = circle.h + (circle.radius * cos ( theta ));
            circle.new_y = circle.k - (circle.radius * sin ( theta ));

            SDL_RenderDrawLine ( renderer, circle.old_x, circle.old_y,
                                 circle.new_x, circle.new_y );

            circle.old_x = circle.new_x;
            circle.old_y = circle.new_y;

        }

        SDL_SetRenderDrawColor ( renderer, 0, 0, 0, 255 );
        SDL_RenderPresent ( renderer );
    }

    SDL_Quit ();

return 0;
}

Doesn't SDL have a function for drawing a circle, or are you just doing that as practise?

#define PI  3.14159

math.h should have M_PI.

struct Circle {
    int radius;
    int h; // The X access of the center of the circle.
    int k; // The Y access of the center of the circle.

Just call them x and y, or center_x and center_y.

int new_x; int new_y; int old_x; int old_y; float step;

These should be in the function that draws the circle, as they're part of the logic of drawing, not the circle as an object.

int main (int argc, char *argv[])
    Circle circle;
    circle.radius = 200;
    circle.h = SCR_CEN_X;

Make a function to initialize the Circle struct, esp. as you have fields that are initialized to as uninteresting a value as zero.

        if ( event.type == SDL_QUIT ) {
            is_running = false;

I would break out of the loop here, since you're going to exit soon anyway.

    for ( float theta = 0; theta < (PI * 2); theta += circle.step ) {
        circle.new_x = circle.h + (circle.radius * cos ( theta ));
        circle.new_y = circle.k - (circle.radius * sin ( theta ));
        SDL_RenderDrawLine ( renderer, circle.old_x, circle.old_y,
                             circle.new_x, circle.new_y );

Put the circle drawing in a function, and make new_x, new_y etc. locals to it. As for step, you might want to scale it based on the circle's radius. Or make it a parameter to the function.

I think you have a sort of an off-by-one error here, as (1) on the first iteration of the loop, you draw starting from (old_x, old_y), but old_x and old_y aren't set yet. And (2) when the loop ends, you probably want to draw a line from the last point (at angle 49/50*2*pi) to the very first point (at angle 0) to complete the circle.

Also, decide if you're writing C or C++. You can't define a struct Circle as just Circle foo in C, and in C++, you should make the class have a proper constructor.


Looking for performance suggestions in Noise algorithm I believe this is considered value noise or possibly gradient noise in that I simply interpolate between random values (always returning the same values per coordinate).

I am using this currently to generate a basic heightmap in a 3D game that expands outward as the player moves (being nearly infinite, only restricted by variable limitations).

I contain my game's map within chunks, 32x32 (1024) data points per chunk representing height. I call the function GetNoise2D() with the X and Z values of every data point.

This is currently my largest bottleneck. I could probably just do the 4 corners per chunk and interpolate between them to get reasonable looking terrain, but to put it simply, I'd rather not.

Does anyone see any noticeable performance issues with the algorithm or the concept after initialization? I call on the algorithm using the function GetHeight() which combines two calls to the algorithm.

private float GetHeight(int X, int Z) {
    float fNoise = Noise.GetNoise2D(X * .02f, Z * .02f) * .5f;
    fNoise += Noise.GetNoise2D(X * .04f, Z * .04f) * .5f;

    //Scale noise from 0-1 to 0-20
    return fNoise * 20f;
}

public class clsNoise2D {
    readonly byte[] Permutations = new byte[512];
    readonly float[] Values = new float[256];
    float xLerpAmount, yLerpAmount, v00, v10, v01, v11;
    //pX, pXa, dX, and dY are helper values to reduce operations
    int pX, pXa; int dX, dY;

    public Random random;

    public clsNoise2D(int iSeed) {
        random = new Random(iSeed);

        //Randomize permutations array with values 0-255
        List<byte> listByte = new List<byte>();
        for (int i = 0; i < 256; i++) listByte.Add((byte)i);
        for (int i = 256; i > 0; i--) { Permutations[256 - i] = listByte[random.Next(i)]; listByte.Remove(Permutations[256 - i]); }

        //Take permutations array up to 512 elements to reduce wrapping needs in GetNoise2D call
        for (int i = 256; i < 512; i++) { Permutations[i] = Permutations[i - 256]; }

        //Set values to be between 0 and 1 incrementally from 0/255 through 255/255.
        for (int i = 0; i < 256; i++) { Values[i] = (i / 255f); }
    }

    public float GetNoise2D(float CoordX, float CoordY) {
        //Get floor value of inputs
        dX = (int)Math.Floor(CoordX); dY = (int)Math.Floor(CoordY);

        //Get fractional value of inputs
        xLerpAmount = CoordX - dX; yLerpAmount = CoordY - dY;

        //Wrap floored values to byte values
        dX = dX & 255; dY = dY & 255;

        //Start permutation/value pulling
        pX = Permutations[dX]; pXa = Permutations[dX + 1];

        v00 = Values[Permutations[(dY + pX)]];
        v10 = Values[Permutations[(dY + pXa)]];
        v01 = Values[Permutations[(dY + 1 + pX)]];
        v11 = Values[Permutations[(dY + 1 + pXa)]];

        //Smooth lerp amounts by cosine function
        xLerpAmount = (1f - (float)Math.Cos(xLerpAmount * Math.PI)) * .5f;
        yLerpAmount = (1f - (float)Math.Cos(yLerpAmount * Math.PI)) * .5f;

        //Return 2D interpolation for v00, v01, v10, and v11
        return (v00 * (1 - xLerpAmount) * (1 - yLerpAmount) +
                v10 * xLerpAmount * (1 - yLerpAmount) +
                v01 * (1 - xLerpAmount) * yLerpAmount +
                v11 * xLerpAmount * yLerpAmount);
    }
}

Edit: To clarify the question itself, is there a very noticeable performance mistake currently being made OR is there a completely different way to achieve identical or nearly identical values that SHOULD knock the performance out of the park?

I'm not sure if Cos and Sin are efficient here, they might be a ferformance killer. Consider making a table of sin/cos values for come range of angles.


Represent a Class which holds translation Strings I have a class which represents some translations of a keyword.

public abstract class Name {

    private String name;
    private String name_de;
    private String name_it;
    private String name_fr;
    private String name_hu;
    private String name_cs;

    public Name(String name_key, String name_de, String name_it, String name_fr, String name_hu, String name_cs) {
        super();
        this.name = name_key;
        this.name_de = name_de;
        this.name_it = name_it;
        this.name_fr = name_fr;
        this.name_hu = name_hu;
        this.name_cs = name_cs;
    }

Each translation has to be an own field because of saving purpose. The problem here is that I cant make sure that for instance the german translation is really the second parameter.

I was thinking about to create an own Object for each translation, but seems a litte bit of overhead. Are there any other options to represent a translation class?

You haven't given much context about how you intend to use this class, which is always important.  In my experience (echoed in comments), there's not much use case for needing all translations of a string at one time.  The use case is more typically that you need to render the UI in a particular language, so you need a bunch of German strings but none of the other languages.  Also, you want to be able to easily add support for additional languages, ideally without any code changes.  That's what resource bundles are for, it seems like you are trying to reinvent the wheel here.  If you think that resource bundles don't solve your problem, you should give more context.