Find duplicate in linear time and space The task:

  You are given an array of length n + 1 whose elements belong to the
  set {1, 2, ..., n}. By the pigeonhole principle, there must be a
  duplicate. Find it in linear time and space.

const lst = [1,2,3,4,5,6,7,8,7];

My functional solution:

const findDuplicate = lst => {
  const set = new Set();
  let ret;
  lst.some(x => set.has(x) ?
           !Boolean(ret = x) :
           !Boolean(set.add(x))
  );
  return ret;
};

console.log(findDuplicate(lst));

My imperative solutions:

function findDuplicate2(lst) {
  const set = new Set();
  let i = 0;
  while(!set.has(lst[i])) { set.add(lst[i++]); }
  return lst[i];
}

console.log(findDuplicate2(lst));

function findDuplicate3(lst) {
  for (let i = 0, len = lst.length; i < len; i++) {
    if (lst[Math.abs(lst[i])] >= 0)  {
      lst[Math.abs(lst[i])] = -lst[Math.abs(lst[i])];
    } else {
      return Math.abs(lst[i]);
    }
  }
}

console.log(findDuplicate3(lst));

I'm not a big fan of the functional solution for following reasons:

the pointless use of the some() method, because its callback always returns false. This is this possibly an error? The call would short-circuit, if Boolean(ret = x) weren't negated. But even then some() would be the wrong choice, because it's just used for short-circuiting. I believe find() would be a better choice.
the conditional expression together with Boolean(...) expressions are a bit if a crutch. The conditional expression seems to be only used to be shorter that an full if, but that requires Boolean(), so that it still returns a boolean value needed for some().

Using find() I've come up with

const findDuplicate = lst => {
  const set = new Set();
  return lst.find(
    x => set.has(x) || !set.add(x)
  );
};

However I do admit it may be a bit cryptic.


Shopping cart code kata I have recently started code kata and learning for myself, as I would like to
learn test-first development. I have started doing a shopping cart as my code kata. I have included a test as well.  I would like to know what are the ways I could improve my below code.  I know I need to use dependency injection next step. If you find anything I can improve in my code, please let me know.

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;

namespace Domain.Tests.Shopping_Cart_Tests
{
    [TestFixture]
    public class ShoppingCartTest
    {
        private IShoppingCart _shoppingCart;

        [SetUp]
        public void SetUp()
        {
            _shoppingCart = new ShoppingCart();
        }

        [Test]
        public void ShouldBeAbleToAddToCart()
        {
            var item1 = new CartItem{ProductId="P1001",Name = "Logitech Mouse", Qty = 1, Price = 5.00};

            _shoppingCart.AddToCart(item1);

            Assert.AreEqual(_shoppingCart.GetCartItems().Count, 1);
        }

        [Test]
        public void ShouldBeAbleToAddToCartMultipleItems()
        {
            var item1 = new CartItem { ProductId = "P1001", Name = "Logitech Mouse", Qty = 1, Price = 5.00 };
            var item2 = new CartItem { ProductId = "P1002", Name = "Logitech Keyboard", Qty = 1, Price = 9.00 };

            _shoppingCart.AddToCart(item1);
            _shoppingCart.AddToCart(item2);

            Assert.AreEqual(_shoppingCart.GetCartItems().Count, 2);
        }

        [Test]
        public void ShouldBeAbleToIncrementWhenAddTheSameItem()
        {
            var item1 = new CartItem { ProductId = "P1001", Name = "Logitech Mouse", Qty = 1, Price = 5.00 };
            var item2 = new CartItem { ProductId = "P1001", Name = "Logitech Mouse", Qty = 2, Price = 5.00 };
            var item3 = new CartItem { ProductId = "P1001", Name = "Logitech Mouse", Qty = 3, Price = 5.00 };

            _shoppingCart.CheckItemExistThenAddToCart(item1);
            Assert.AreEqual(_shoppingCart.GetCartItems().Count, 1);
            _shoppingCart.CheckItemExistThenAddToCart(item2);
            Assert.AreEqual(_shoppingCart.GetCartItems().Count, 1);
            _shoppingCart.CheckItemExistThenAddToCart(item3);
            Assert.AreEqual(_shoppingCart.GetCartItems().Count,1);
        }
    }

    public interface IShoppingCart
    {
        void AddToCart(CartItem item);
        List<CartItem> GetCartItems();
        void CheckItemExistThenAddToCart(CartItem item);
    }

    public class ShoppingCart : IShoppingCart, IEnumerable
    {
        private static List<CartItem> CartItems = null;

        public ShoppingCart()
        {
            CartItems = new List<CartItem>();
        }

        public void AddToCart(CartItem item)
        {
            CartItems.Add(item);
        }

        public void CheckItemExistThenAddToCart(CartItem item)
        {
            var cartItem = CartItems.FirstOrDefault(ci => ci.ProductId == item.ProductId);
            if (cartItem == null)
                AddToCart(item);
            else
                cartItem.Qty += item.Qty;
        }

        public List<CartItem> GetCartItems()
        {
            return CartItems;
        }

        public IEnumerator GetEnumerator()
        {
            return (CartItems as IEnumerable).GetEnumerator();
        }
    }

    public class CartItem
    {
        public string Name { get; set; }

        public double Price { get; set; }

        public int Qty { get; set; }

        public string ProductId { get; set; }
    }
}

public double Price { get; set; } clearly should be of type Decimal. That is what Decimal for.
private static List<CartItem> CartItems = null; can be safely refactored to Dictionary<int, CartItem> with ProductId used as keys. Then CheckItemExistThenAddToCart can be refactored using Dictionary.ContainsKey method, and GetCartItems can return dictionary itself, CartItems.Values or CartItems.Values.ToList(). I think the latter option is the best, since it will copy the collection, which will restrict access to CartItems property. As of now, someone might modify it in outer code, which will result it modifying ShoppingCart state. Returning a copy will prevent that.
return (CartItems as IEnumerable).GetEnumerator(); cast can be removed.
I'm not sure i like the idea of having two methods to add items to the cart, which have different logic. It's pretty error-prone. Is it really necessary? I think you should probably stick to one.
I think your shopping cart interface misses Remove method.

Your unit tests look fine to me (except you should move them to different file), tho i'm not too experienced with them.


Converting from binary to unary I have function that convert binary number to unary number based on a Markov algorithm. In what ways can I improve the code?

The algorithm goes as follows:

Replace all 0l with 0l

  "|0" -> "0||"

Replace all l0 with 0ll

  "1" -> "0|"

Major Step 3: Remove the 0

  "0" -> ""

    public List BinaryToUnary(List value)
    {
        var temp = new List();
        var temp2 = new List();
        var temp3 = new List();
        string hold = "";
        int count = 1;

        TxtToDisPlay = "Major Step 1: replace All 1 with 0l userInput " + string.Join("", value) + "\n\n";

        foreach (var x in value)
        {
            if (x.Equals("1"))
            {
                temp.Add("0l");
                TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + x + " = " + "0l" + "\n";
            }
            else
            {
                temp.Add(x);
                TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + x + " = " + x + "\n";
            }
            count++;
        }
        TxtToDisPlay = TxtToDisPlay + "\n\nMajor Step 2: Replace all l0 with 0ll  userInput = " + string.Join("", temp) + " \n\n";

        foreach (var x in string.Join("", temp))
        {
            hold = hold + x;
            if (hold.Equals("l0"))
            {
                temp2.Add("0ll");
                TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + hold + " = " + "0ll" + "\n";
                hold = "";
            }
            if (hold.Equals("0"))
            {
                temp2.Add(hold);
                TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + hold + " = " + hold + "\n";
                hold = "";
            }
            count++;
        }
        if (hold.Equals("l"))
        {
            temp2.Add("l");
        }

        hold = "";

        foreach (var y in string.Join("", temp2))
        {
            if (temp2.Count == 1)
            {
                temp3.Add("l");
                break;
            }

            hold = hold + y;
            if (hold.Equals("l0"))
            {
                TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + hold + " = " + "0ll" + "\n";
                temp3.Add("0ll");
                hold = "";
            }
            if (hold.Equals("0") || hold.Equals("ll"))
            {
                if (hold.Equals("ll"))
                {
                    TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + hold + " = " + hold + "\n";
                    temp3.Add("l");
                    hold = "l";
                }
                else
                {
                    TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + hold + " = " + hold + "\n";
                    temp3.Add(hold);
                    hold = "";
                }

            }
        }
        if (value.Count == 3 && hold.Equals("l"))
        {
            temp3.Add("l");
            temp3.Add("l");
        }
        else if (value.Count == 3 || hold.Equals("l"))
        {
            temp3.Add("l");

        }

        TxtToDisPlay = TxtToDisPlay + "\n\nMajor Step 3 : get rid of the 0 from  userInput = " + string.Join("", temp3) + " \n\n";
        var answer = new List();
        foreach (var x in temp3)
        {
            if (x.Contains("0ll"))
            {
                foreach (var y in x.Where(y => y.Equals('l')))
                {
                    answer.Add("l");
                    TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + "x = l so " + "Add l To new Array result = " + string.Join("", answer) + "\n";
                }
            }
            else if (x.Contains("l"))
            {
                TxtToDisPlay = TxtToDisPlay + "Step " + count + ": " + "Add l To new Array result = " + string.Join("", answer) + "\n";
                answer.Add(x);
            }
            count++;
        }

        return answer;
        }

You are not supposed to replace all matches but only the first one. And then repeat the process.

Here is some javascript code that implements the markov algorithm exactly the way it is described on the wikipedia page.
Now all you have to do is translate that to C#.

function binaryToUnary(value) {
  var matchFound = false,
      rules = [["|0", "0||"],
               ["1",  "0|" ],
               ["0",  ""   ]];
  do {
    matchFound = false;
    for(var i = 0; i < rules.length; i++) {
      var rule = rules[i],
          pattern = rule[0], replacement = rule[1],
          index = value.indexOf(pattern);
      if(index >= 0) {
        value = value.substring(0, index) +
                replacement +
                value.substring(index + pattern.length);
        matchFound = true;
        break; //break because only the first pattern that matches should be replaced
      }
    }
  } while(matchFound);
  return value;
}


Python 3 class constructor I have implemented a metaclass in Python 3 that, apart from the usual instance constructor (i.e. __init__), enables you to define a class constructor (as a class method that I called __init_class__). The metaclass extends abc.ABCMeta so it supports abstract classes, i.e. the class constructor is not called if a class is abstract.

I've written up some tests for it, they pass, and the metaclass also works in practice for me, but I'd like to know:

Is this even a good approach for adding a class constructor functionality?
Are there any problematic corner-cases that I might run into with my code?
Am I testing it correctly?
Any comments about my code being (or not) pythonic?

Implementation:

import abc
import inspect

class MyType(abc.ABCMeta):
    """
        Metaclass.

        It adds extra functionality of an optional class constructor, which might by added
        to the class by adding a class method __init_class__(cls) to the class definition.

        Class constructor takes no arguments.
    """

    def __init__(cls, name, bases, nmspc):
        super().__init__(name, bases, nmspc)
        cls.__has_init_class__ = hasattr(cls, '__init_class__')
        if cls.__has_init_class__ and not inspect.isabstract(cls):
            cls.__init_class__()

Tests:

import unittest

class MyTypeTests(unittest.TestCase):
    """ Unit tests for MyType metaclass. """

    def test_class_constructor(self):
        """ Is the class constructor invoked? """

        class WithoutInit(metaclass=MyType): # pylint: disable=R0903
            """ Dummy class. """
            initialized = False

        class AbstractWithoutInit(metaclass=MyType): # pylint: disable=R0903
            """ Dummy abstract class. """
            initialized = False
            @abc.abstractmethod
            def spam(self):
                """ Dummy abstract method. """
                pass

        class WithInit(metaclass=MyType): # pylint: disable=R0903
            """ Dummy class with class constructor. """
            initialized = False
            @classmethod
            def __init_class__(cls):
                cls.initialized = True

        class AbstractWithInit(metaclass=MyType): # pylint: disable=R0903
            """ Dummy abstract class with class constructor. """
            initialized = False
            @abc.abstractmethod
            def spam(self):
                """ Dummy abstract method. """
                pass
            @classmethod
            def __init_class__(cls):
                cls.initialized = True

        self.assertFalse(WithoutInit.initialized)
        self.assertFalse(AbstractWithoutInit.initialized)
        self.assertTrue(WithInit.initialized)
        self.assertFalse(AbstractWithInit.initialized)

Any comments about my code being (or not) pythonic?

It's 100% not pythonic code. If we go to PEP8 -- Descriptive: Naming Styles we'll see:

  __double_leading_and_trailing_underscore__: "magic" objects or attributes that live in user-controlled namespaces.
  E.g. __init__, __import__ or __file__. Never invent such names; only use them as documented.

Yes never create these.
I can give you one example for why this is in place.

Say a novice to Python comes across this magic attribute and method that you have created.
They don't know what it does, they've not come across a magic method that has not been documented in the Python docs.
But they have yours.
They laboriously search the Python docs, but just can't find it.
They then don't use your code, as they don't know what it does.

Now, I maybe being a foolish hobgoblin, and so sure your new 'init' could possible be a magic method.
But I'd still argue that __has_init_class__ should defiantly not be.
Instead that could be _has_init_class.

I'd argue that _has_init_class is somewhat pointless and you should just use hasattr(cls, '__init_class__').
You also don't test this, and so it seems to me that you don't use it.
In short it may be some nice sugar, but you probably don't need or use it.

I don't think __init_class__ is a good name.
It makes me think you'll be running it near __init__,
which from your tests in definitely not the case.
You may say, you'll use __new_class__ instead.
No, __new__ works together with __init__ to construct objects, and so would shift confusion.
I would name it more closely to how you are using it.
From what I know I'd call it _nonabstract_meta_constructor.
That's a bit long for my liking so I'd just use _meta_const.

And so I'd use:

class MyType(abc.ABCMeta):
    """
        Metaclass.

        It adds extra functionality of an optional class constructor, which might by added
        to the class by adding a class method __init_class__(cls) to the class definition.

        Class constructor takes no arguments.
    """

    def __init__(cls, name, bases, nmspc):
        super().__init__(name, bases, nmspc)
        if hasattr(cls, '_meta_const') and not inspect.isabstract(cls):
            cls._meta_const()

Ok it's not "100% not pythonic code". If you remove the magic methods, your code has no glairing PEP8 errors.
You probably don't need all the docstrings on the tests, and your MyType docstring should be changed to follow PEP257.
You should have a summery line, and then your multi-line docstring as you have it.

But it's good. Apart from the magic I'd have no, non-petty, reason to complain.


Validating ISBN-10s, with or without dashes in C++11 Description
A regex-based method of validating ISBN-10 as strings. Can be digits (or 'X' at the end) only, or with dashes, according to those of English-speaking publications (which are defined by the regular expressions contained in the code below).
The last digit, a check digit (unless it is an 'X'), is calculated in the following manner. Multiply each digit, starting from the leftmost digit, by a weight, and then sum the results. The check digit should be such that this sum is divisible by 11. The weight starts at 1, and increases by 1 for each digit. For example, consider the ISBN 0-306-40615-2. The sum is calculated as follows:
sum = 0*1 + 3*2 + 0*3 + 6*4 + 4*5 + 0*6 + 6*7 + 1*8 + 5*9 + 2*10 = 165
165 mod 11 = 0 // the check digit, 2, is valid.

I am a .NET developer dabbling in C++ for fun. With this exercise, I have tried to hide certain things from anything outside the namespace, by creating an anonymous namespace inside it. Essentially, I have tried to achieve what the private keyword does in C#, in C++ semantics. I am curious if I have done anything "un C++ like" in this code. I envisage this code could be expanded to have a function that validates ISBN-13 numbers.
Code
#include <iostream>
#include <string>
#include <vector>
#include <regex>
#include <algorithm>

namespace isbn_validation
{
    namespace // anonymous namespace
    {
        // regex expressions
        // dashless
        const std::regex isbn10_no_dashes(R"((\d{9})[\d|\X])");
        // with dashes
        const std::regex isbn10_dashes1(R"((\d{1})\-(\d{5})\-(\d{3})\-[\d|\X])");
        const std::regex isbn10_dashes2(R"((\d{1})\-(\d{3})\-(\d{5})\-[\d|\X])");
        const std::regex isbn10_dashes3(R"((\d{1})\-(\d{4})\-(\d{4})\-[\d|\X])");
        const std::regex isbn10_dashes4(R"((\d{1})\-(\d{5})\-(\d{3})\-[\d|\X])");
        const std::regex isbn10_dashes5(R"((\d{2})\-(\d{5})\-(\d{2})\-[\d|\X])");
        const std::regex isbn10_dashes6(R"((\d{1})\-(\d{6})\-(\d{2})\-[\d|\X])");
        const std::regex isbn10_dashes7(R"((\d{1})\-(\d{7})\-(\d{1})\-[\d|\X])");

        bool isbn10_check_digit_valid(std::string isbn10)
        {
            auto valid = false;

            // split it
            std::vector<char> split(isbn10.begin(), isbn10.end());

            // if the very last character is an 'X', don't bother with it
            if (split[9] == 'X')
            {
                return true;
            }

            // all digits
            // validate the last digit (check digit)
            int digit_sum = 0;
            int digit_index = 1;
            for (std::vector<char>::iterator it = split.begin(); it != split.end(); ++it)
            {
                digit_sum = digit_sum + ((*it - '0')*digit_index);

                digit_index++;
            }
            valid = !(digit_sum%11);

            return valid;
        }
    }

    bool valid_isbn10(std::string isbn)
    {
        // can take ISBN-10, with or without dashes
        auto valid = false;

        // check if it is a valid ISBN-10 without dashes
        if (std::regex_match(isbn, isbn10_no_dashes))
        {
            // validate the check digit
            valid = isbn10_check_digit_valid(isbn);
        }

        // check if it is a valid ISBN-10 with dashes
        if (std::regex_match(isbn, isbn10_dashes1) || std::regex_match(isbn, isbn10_dashes2) || std::regex_match(isbn, isbn10_dashes3) ||
            std::regex_match(isbn, isbn10_dashes4) || std::regex_match(isbn, isbn10_dashes5) || std::regex_match(isbn, isbn10_dashes6) || std::regex_match(isbn, isbn10_dashes7))
        {
            // remove the dashes
            isbn.erase(std::remove(isbn.begin(), isbn.end(), '-'), isbn.end());

            // validate the check digit
            valid = isbn10_check_digit_valid(isbn);
        }

        return valid;
    }
}

When you're comparing against 8 different patterns, and then simply removing - for 7 of those validations, why not just remove - initially, and then validate against the only remaining pattern.
Another thing to note is, in the patterns, at the end; you have a character set: [\d|\X]. This actually will match one of:

a digit
literal |
literal X characters (you don't need \X though).

This should instead be:
\d{9}[\dX]

A general outline of how the code should work:

Remove all - from given string
Check if length of string is exactly \$ 10 \$
Validate against the pattern rewritten above
Check if last character is X
Validate individual digit sum and divisibility.


Determining Pythagorean triples based on the hypotenuse Below is my written code to determine if, based on the hypotenuse, a Pythagorean triple is possible, and what are the lengths. I was wondering if there is a more efficient way of doing so.

#Victor C
#Determines if a right triangle with user inputted hypotenuse is capable of being a Pythagorean Triple

import math
triplecheck = True
while True:
    hypotenuse = int(input("Please enter the hypotentuse:")) #Smallest hypotenuse which results in a pythagorean triple is 5.
    if hypotenuse > 4:
        break
c = csqr = hypotenuse**2 #sets two variables to be equivalent to c^^2. c is to be modified to shorten factoring, csqr as a reference to set a value
if c % 2 != 0:   #even, odd check of value c, to create an integer when dividing by half.
    c = (c+1)//2
else:
    c = c//2
for b in range(1,c+1):  #let b^^2 = b || b is equal to each iteration of factors of c^^2, a is set to be remainder of c^^2 minus length b.
    a = csqr-b
    if (math.sqrt(a))%1 == 0 and (math.sqrt(b))%1 == 0: #if squareroots of a and b are both equal to 0, they are integers, therefore fulfilling conditions
       tripleprompt = "You have a Pythagorean Triple, with the lengths of "+str(int(math.sqrt(b)))+", "+str(int(math.sqrt(a)))+" and "+str(hypotenuse)
       print(tripleprompt)
       triplecheck = False
if triplecheck == True:
    print("Sorry, your hypotenuse does not make a Pythagorean Triple.")

First, let's write this with a little style, and go from there:

import math

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""
    if hypotenuse < 4:
        return None

    c = hypotenuse ** 2

    for a in xrange(3, hypotenuse):
        b = math.sqrt(c - (a ** 2))
        if b == int(b):
            return a, int(b), hypotenuse

    return None

Now, I'll walk you through it, line by line, and show you how I got this.

I have no idea if this is more efficient, but it is written in better style, which is an important thing to consider.

import math

Always put your imports at the top of the module.

def is_triple(hypotenuse):

Here is say 'let's define some functionality, and encase a repeatable, reusable pattern of logic within it. The rest of my answer revolves around this, and is a major first step to programming in Python.

def is_triple(hypotenuse):
    """return (a, b, c) if Pythagrean Triple, else None"""

Note the """ triple quotes. That's your docstring, something that reminds you later what you were thinking when you wrote something. Try to keep it under 65 characters or so.

if hypotenuse < 4:
    return None

In the first line, def is_triple(hypotenuse):, I ask the user to give me something; a variable that I can use later. If I later call this function in the manner is_triple(5), I am basically telling the function that my hypotenuse is 5, and for the rest of the time here, we'll call it hypotenuse.

c = hypotenuse ** 2

That's really all you need for this calculation right now.

for a in xrange(3, hypotenuse):
        b = math.sqrt(c - (a ** 2))
        if b == int(b):
            return a, int(b), hypotenuse

for a in xrange(3, hypotenuse) basically says for each whole number between 3 and the hypotenuse, do the stuff I'm about to write.

Following the previous example,

>>> range(3, hypotenuse) #hypotenuse is == 5
[3, 4]

Nevermind that I call xrange(), it functions the same as far as we're concerned here, and importantly, is more efficient.

So now that we've made a loop, a will act as though it is each number in [3, 4], so first, it's 3:

b = math.sqrt(c -  (a ** 2))
b = math.sqrt(25 - (3 ** 2))
b = math.sqrt(25 - (9))
b = math.sqrt(16)
b = 4.0

Just like you would on pencil and paper. Notice I put a .0 after, the four. That's important here:

if b == int(b):

Basically, int puts the number b from a decimal to a whole number. We just check if they're the same.

>>> int(4.0)
4
>>> int(4.0) == 4
True

So, if the number we got for b is the same as the whole number representation of b, do the next part:

return a, int(b), hypotenuse

Which maps a value back to whatever you called as an assignment for the function call.

>>> values = is_triple(5)
>>> values
(3, 4, 5)
>>> wrong = is_triple(7)
>>> wrong
>>> #it didn't print anything, because it gave me back None

Finally, at the bottom:

return None

That's the last thing to catch, in case nothing else happens. Obviously, if you've gone through this loop and you haven't gotten an answer? Well, looks like you don't have a match. Give back a None to denote this.

To see this work in action, try this:

>>> import pprint
>>> pprint.pprint([{x: is_triple(x)} for x in xrange(101)])


C: function to read a token from stdin I recently started doing some competitive programming in C and one of my first requirements was a high-speed token reader (analogous to the java Scanner class' next() function). A few examples of input I am most likely to read are:
5
ccadd
bddcc

5 4 1
1 2 5
2 3 7
3 4 8
4 5 2
2 3

The integer/float inputs will be handled using atoi() and atof(), so all I need to develop is a function that will read words from stdin. Here's the first prototype:
#define BUF_SIZE (1 << 10) // approx 2 KiB or 1024 chars

char* next_token() {
    char* buf = malloc(BUF_SIZE * sizeof(char));
    char cc;
    // consume leading whitespaces
    while (isspace(cc=getchar())) ;
    buf[0] = cc;
    int i=1;
    int nofs = 1;
    while (!isspace(cc=getchar())) {
        if (i >= BUF_SIZE*nofs) {
            // gracefully extend buffer size
            nofs++;
            buf = realloc(buf, BUF_SIZE*nofs*sizeof(char));
        }
        buf[i] = cc;
        i++;
    }
    // trim buffer
    buf = realloc(buf, (i+1)*sizeof(char));
    buf[i] = '\0';
    return buf;
}

int main() {
    int T = atoi(next_token());
    while (T-- > 0) {
        char* word = next_token();
        // more logic here
    }
}

Two questions I had with this code are:

Is this fast enough? I think the major bottleneck lies with the realloc at the end, where I trim the length. If it's not fast enough, please suggest some optimizations.
Is this compliant with how C is generally written? I'm coming from Java and have little  experience with C code. I write some embedded C but that's closer to assembly than it is to this type of code.

Any further improvements are welcome.

Alignment
This will be an easy win - use aligned_alloc instead of malloc. This is only guaranteed to be available in the standard library as of C11, which you should be using anyway.
Exponential reallocation
This:
        // gracefully extend buffer size
        nofs++;
        buf = realloc(buf, BUF_SIZE*nofs*sizeof(char));

reallocates with linear growth. Memory is cheap and CPU time is expensive, so reallocate with exponential growth instead. Choosing a growth factor is a little more involved, but growth factors of 1.5 or 2 are not uncommon.
Inner assignment
Remove the assignment-in-condition from this:
while (isspace(cc=getchar())) ;

It does not make anything faster, and is a nasty bit of C syntax that makes code more difficult to read, maintain and debug.
Use a for
int i=1;
while (!isspace(cc=getchar())) {
    // ...
    i++;
}

can be
for (int i = 1; !isspace(cc); i++) {
   // ...
   cc = getchar();
}

noting that an initial getchar() would need to precede this loop.


Class to represent a mutable date and time What would be the best way to refactor this class - if any at all?  I'm using this class to get the current date and time and also to modify this date by being able to change its date and time.  I have a lot of functions which appear to do similar things subtractSeconds, subtractMinutes, subtractDays etc.. But I'm not sure what software design principle I should be looking into more.  My gut tells me I need to use an interface or abstract class to reduce my code and make it simpler?

class AmazonDate
{
    protected $seconds;

    protected $days;

    protected $months;

    protected $date;

    protected $minutes;

    protected $hours;

    public function __construct()
    {
        date_default_timezone_set('America/Chicago');
        $date = new DateTime(date('Y/m/d H:i:s'));
        $this->setDate($date);
    }

    public function currentDate()
    {
        date_default_timezone_set('America/Chicago');
        $date = new DateTime(date('Y/m/d H:i:s'));
        $this->setDate($date);
    }
    public function setDate($date)
    {
        $this->date = $date;
    }
    public function getDate()
    {
        return $this->date;
    }

     public function subtractSeconds($seconds)
     {
         $this->seconds = $seconds;

         $date = $this->getDate();
         $date = date_modify($date, '- ' . $this->seconds . ' second');
         $this->setDate($date);
         return $this;
     }

    public function subtractMinutes($minutes)
    {
        $this->minutes = $minutes;

        $date = $this->getDate();
        $date = date_modify($date, '- ' . $this->minutes . ' minutes');
        $this->setDate($date);
        return $this;
    }

    public function subtractHours($hours)
    {
        $this->hours = $hours;

        $date = $this->getDate();
        $date = date_modify($date, '- ' . $this->hours . ' hours');
        $this->setDate($date);
        return $this;
    }

    public function subtractDays($days)
    {
        $this->days = $days;

        $date = $this->getDate();
        $date = date_modify($date, '- ' . $this->days . ' days');
        $this->setDate($date);
        return $this;
    }

    public function subtractMonths($months)
    {
        $this->months = $months;

        $date = $this->getDate();
        $date = date_modify($date, '- ' . $this->months . ' months');
        $this->setDate($date);
        return $this;
    }
     public function printDate()
     {
         $date = $this->getDate();
         return $this->dateToString($date);
     }

    /**
     * @param $date
     * @return mixed
     */
    private function dateToString(DateTime $date)
    {
        return $date->format('c');
    }
}

I guess I am not really seeing what value this class adds above and beyond what DateTime and related classes give to you "out of the box".

If you need a method or two to perhaps format a date in some specific way to be compatible with Amazon, then perhaps you could extend the base DateTime class with these methods.

Even then, I still question the value of introducing a whole class to, in essence, do these sorts of trivial things:

$datetime = new DateTime();
$datetime->modify('-1 month');
$datetime->modify('-10 days');
$amazonFormat = $datetime->format('c');

It is odd how you are working with PHP's procedural date functions interchangeably with DateTime.

For example in your constructor you write this:

public function __construct()
{
    date_default_timezone_set('America/Chicago');
    $date = new DateTime(date('Y/m/d H:i:s'));
    $this->setDate($date);
}

Which if you truly wanted to use DateTime might look like this:

public function __construct()
{
    $datetime = new DateTime('now', new DateTimeZone('America/Chicago'));
    $this->setDate($date);
}

There is no reason to change your system's default timezone on the fly if you just need to apply a timezone to one specific DateTime object. Right now your code could actually severely break other code in your system that follows instantiation of one of these objects, in that you have munged with default setting for all code that follows in script execution.  If the default setting on the server were for a different time zone,  all code execution up to the point of instantiation would operate in that timezone, while all code after would operate in America/Chicago.

If you truly are trying to set this as your default timezone for your entire application, this function call should be made somewhere in your bootstrapping process.

If this truly is a class-level setting, should the America/Chicago (or similar) value be passed to the constructor, or be a class constant? Right now you are "hiding" this setting inside method logic, which is a bad idea.

Why even have your currentDate() method?  It exactly the same as the constructor logic.

Your method names seem odd and could potentially cause confusion.  get/setDate() are really getting/setting DateTime objects which is not clear from the method names.  Your setDate() has an additional problem in that it does not enforce that a DateTime object be passed via type hinting, so some confused developer could pass a string or some other value to this method and put your object in a bad state.

You have the general problem throughout your public methods in that you are not enforcing data types for parameters at all.  This is typically achieved either through type-hinting (if applicable) or through validation within the method if type-hinting is not available for a given data type (which will vary based on version of PHP you are designing against).


Including a file (is this safe and effective?) I'm not that experienced with PHP and I'm trying to make it so when I load a page, instead of directly browsing to the file, it will be "included" instead.

I have the code finished and it works.  I just wanted to get an opinion of if it's safe (will people be able to exploit it in anyway?) and if I'm going about this the right way.

<?php
error_reporting(0); // I'm not expecting any errors and don't want users to see any.

    $page = strtolower($_GET['page']); // File names will always be lowercase

    if (isset($page))
    {
        $page .= ".php";
        $page = basename($page); // Prevent users from entering a directory path to access other files.

        if ((file_exists($page)) && ($page != "index.php")) // Check if exists and prevent infinite include loop.
        {
            die(include($page));
        }
    }

    include("base.php");
?>

As it uses the basename function it should be safe enough.

One note though: I would personally always have a lookup table (PHP "array") for whitelisting files unless there is a very specific reason not to do so. That way I will have full control and the result should be the same for the user - as a side effect it is way way more easy to have shorter names and/or aliases for files later on.


Fetch, parse, and store JSON in PostgreSQL I was given a task to read JSON from a URL and then parse it in python. Each field will be assigned to a variable to store the value. The value will then be stored into postgres table.

Example of JSON

{
 "forecasts":
[
 {
   "class": "fod_long_range_daily",
   "expire_time_gmt": 1525126617,
   "night": {
     "fcst_valid": 1525158000,
     "fcst_valid_local": "2018-05-01T19:00:00+1200",
     "golf_category": ""
   },
   "day": {
     "uv_warning": 0,
     "uv_desc": "Moderate",
     "golf_index": 10,
     "golf_category": "Excellent"
   }
 }
]
}

I was told that this way i am able to parse JSON and read it into postgres. Is this the right way to do this? Will there be performance issues?

import urllib3
import psycopg2
import json

conn = psycopg2.connect(host="localhost", database="nzaus",
user="admin", password="123321")
print("Database Connected")
cur = conn.cursor()
rowcount = cur.rowcount

http = urllib3.PoolManager()
url = "https://api.data.com/v1/geocode/-35.228208/174.095969/forecast/daily/15day.json?language=en-US&units=m&apiKey=1234"
try:
    response = http.request('GET', url)
    data = json.loads(response.data.decode('utf-8'))

    for item in data['forecasts']:
        class = None
        time = None
        fcst_valid = None
        golf_category = None

        result = []

        class = item['class']
        time  = item['expire_time_gmt']
        fcst_valid = item['night']['fcst_valid']
        golf_category = item['morning']['golf_category']
        result = [class,time,fcst_valid,golf_category]

        cur.execute("""INSERT into datatable
                       VALUES
                       ( %s,
                         %s,
                         %s,
                         %s,
                       )""",(result))
        conn.commit()
    cur.close()
 except IOError as io:
    print("cannot open")

I would narrow down your try:except to only the statement(s) which could throw the error. Having such a large chunk of code in a try:except block could result in many exceptions thrown, none of which would be caught as you're only looking for IOError.

Also, for performance, you should build the statement and the data set from the loop, then throw the statement against cursor.executemany(statement, data) as a single database call instead.

Regarding construction, your code is just one huge blob. It's important that you refactor each operation into its own function, this saves on tracking down errors, and if you make changes in the future, your changes only affect one function. If the change is not liked by the rest of your code, it's easy to back out.
Can you imagine if you made 5 or 10 changes in your program as it is right now, and then it stops working? Which change was the breaking change? How would you find out? Why did it break? etc. Also, I'm not talking just simple syntax errors, I'm also talking about logic errors or data errors. These can be hard to track down if you don't have any tests validating your code.

Good luck!


Scraper for downloading and saving images from web page I've written some code using Python 3 to scrape movie names, links to the movie posters, and finally save the pictures on the local drive after downloading them from a web page.

I have used two functions to accomplish the whole task. I've tried my best to make the process clean. It is working great now. Any suggestion as to the betterment of this script will be very helpful for me. Thanks in advance. Here is the working code:

import requests
from lxml import html
import os

url = "https://www.yify-torrent.org/search/1080p/"

def ImageScraper(link):

    response = requests.session().get(link).text
    tree = html.fromstring(response)
    for title in tree.xpath('//div[@class="mv"]'):
        movie_title = title.findtext('.//h3/a')
        image_url = title.xpath('.//img/@src')[0]
        image_url = "https:" + image_url
        image_name = image_url.split('/')[-1]
        SavingImages(movie_title, image_name, image_url)

def SavingImages(movie_name, item_name, item_link):

    response = requests.session().get(item_link, stream = True)
    if response.status_code == 200:
        os.chdir(r"C:\Users\ar\Desktop\mth")
        with open(item_name, 'wb') as f:
            for chunk in response.iter_content(1024):
                f.write(chunk)

    print(movie_name, item_link)

ImageScraper(url)

I would focus on the following things specifically:

variable and function naming:

use lower_case_with_underscores naming convention
what if we rename title to movie and movie_title to title - I think that would be a bit more descriptive
response should probably be named page_source since it is not a Response instance but already the text of the response

use of spaces and line breaks:

according to PEP8 coding style, you should have 2 line breaks between the functions
when passing a keyword argument to a function, don't put spaces around the =

code organization:

I would use a class to share a web-scraping session and have it parameterized with a url and a download directory. I think that would be more modular.

Improved code:

import os

import requests
from lxml import html

class ImageScraper:
    def __init__(self, url, download_path):
        self.url = url
        self.download_path = download_path

        self.session = requests.Session()

    def scrape_images(self):
        response = self.session.get(self.url).text

        tree = html.fromstring(response)
        for movie in tree.xpath('//div[@class="mv"]'):
            title = movie.findtext('.//h3/a')

            image_url = "https:" + movie.xpath('.//img/@src')[0]
            image_name = image_url.split('/')[-1]

            self.save_image(title, image_name, image_url)

    def save_image(self, movie_name, file_name, item_link):
        response = self.session.get(item_link, stream=True)

        if response.status_code == 200:
            with open(os.path.join(self.download_path, file_name), 'wb') as image_file:
                for chunk in response.iter_content(1024):
                    image_file.write(chunk)

        print(movie_name, file_name)

if __name__ == '__main__':
    scraper = ImageScraper(url="https://www.yify-torrent.org/search/1080p/",
                           download_path=r"C:\Users\ar\Desktop\mth")
    scraper.scrape_images()


Golang concurrent HTTP request I wanted to test the performance of concurrent http request in Go against node.js:

package main

import (
  "fmt"
  "time"
  "strconv"
  "net/http"
)

var responseCounter = 0
var requestCounter = 0
var count=0
var ch = make(chan int)

func sendRequest(){
    go func() {
        requestCounter++
        url := "https://www.google.co.in/#q=search_" +strconv.Itoa(requestCounter)
        resp, err := http.Get(url)
        if err != nil {
            fmt.Printf("\nError",err)
        }
        defer resp.Body.Close()
        count++
        ch <- count
        sendRequest()
    }()
}

func main() {

    for i := 1; i<100; i++{
        sendRequest()
    }

    for {
        select {
            case r := <-ch:
                fmt.Printf("\nChannel ",r)
            case <-time.After(50 * time.Millisecond):
                //sendRequest()
        }
    }
}

When I run this code the CPU usage goes very high (around 90%). Is there something wrong with this code? Have I used the Goroutines correctly?

Inside SendRequst you are calling SendRequest again, which will make your stack full of recursive calls.


Is there a cleaner way to ensure I am not writing duplicate data? I have the following loop which uses Idiorm to write to a table from a PHP Slim application:

foreach($jobs->get_items() as $job) {

        echo $job->get_title().'<br />';
        $jobRow = ORM::for_table('jobs')->create();
        $jobRow->guid = $job->get_id(TRUE);
        $jobRow->url = $job->get_link();
        $jobRow->description = $job->get_description();
        $jobRow->pubdate = $job->get_date();
        echo $job->get_date();

        try {
        $jobRow->save();
        } catch (exception $e) {
            continue;
        }
    }

It feels a bit hacky to be using continue in a try/ catch block. Is there a better way to avoid a MYSQL constraint violation without having to query the table? get_id() returns an md5 hash of the guid in an rss feed which is actually a unqiue URL. I have a UNIQUE index on that field in my table.

How exceptional is this error? What do you want to do when this happens?

If it's rare and you don't want to do anything, then:

Only catch the actual exception (maybe it's PDOException).
Remove the continue which serves no purpose here and could confuse the reader.
Make sure you don't fail silently when the error is not a violation error.

Your code will look like this:

try {
    $jobRow->save();
} catch (PDOException $e) {
    if(!isAnExpectedViolation()) {
        // I still need to do something about it!
    }
}

If it's really frequent, you may want to check if it's going to violate the constraint before running the query. If it's frequent and you want to tell about it to the user, put it into an if and act accordingly.


Printing the max of groups of three random ints I'm trying to teach myself streaming and lambda expressions. Here's the scenario: I have a collection of 10 Thing objects each containing an int[] of 3 random number. I've written code to print out the largest number in each Thing.

I've already written two statements and an accompanying method that print the result I want, however the code is pretty ropey... improvements and suggestions would be greatly appreciated.

import java.util.Random;
public class Thing {
    private Random r = new Random();
    private int a = r.nextInt(), b = r.nextInt(), c = r.nextInt();

    public int[] getCollectionOfInts() {
        return collectionOfInts;
    }

    private int[] collectionOfInts = new int[]{a, b, c};

}//end of class

//main in separate driver class
public static void main(String[] args) {
        Thing[] things = new Thing[10];
        int a=0,b=0,c=0;
        for (int x =0;x<10;x++){
            things[x] = new Thing();
            for (int y=0;y<things[x].getCollectionOfInts().length;y++)
            {
                if(y==0)
                    a = things[x].getCollectionOfInts()[y];
                if(y==1)
                    b = things[x].getCollectionOfInts()[y];
                if(y==2)
                    c = things[x].getCollectionOfInts()[y];
            }
            //print 3 numbers in each Thing object
            System.out.println(x+": "+a+", "+b+", "+c);
        }
        System.out.println();

        //compare each number and print out largest... too many ternaries
        Stream.of(things).forEach(Thing->System.out.println(Stream.of(Thing.getCollectionOfInts()).mapToInt(z->z[0]>z[1]&&z[0]>z[2]?z[0]:z[1]>z[2]?z[1]:z[2]).reduce((x,y)->x+y).getAsInt()));
        System.out.println();
        //improper use of .max() or .mapToInt(...)?
        Stream.of(things).forEach(Thing->System.out.println(Stream.of(Thing.getCollectionOfInts()).mapToInt(x->maxInt(x)).max().getAsInt()));

    }
    public static int maxInt(int[] x) {
        int max=x[0];
        for (int y:x) {
            if(y>max)
                max = y;
        }
        return max;
    }

I get the expected results for both streams, but I'm still unhappy with how I get there!

The first thing about your code are the two lines inside your class Thing:

private Random r = new Random();
private int a = r.nextInt(), b = r.nextInt(), c = r.nextInt();

If Random r is used just to initialize the array and not in other methods inside the class , it is better to use it in the costructor of the class :

public Thing() {
    Random r = new Random();
    this.arr = new int[] {r.nextInt(), r.nextInt(), r.nextInt()};
}

You can check I initialize directy here the array of ints instead of defining variables a, b, c.
A good thing is also override the String method to print the internal state of a object:

@Override
public String toString() {
    return Arrays.toString(arr);
}

Now you can print the state of your Thing object in this way:

for (int i = 0;i < 10; ++i){
    things[i] = new Thing();
    //print 3 numbers in each Thing object
    System.out.println(i + ": " + things[i]);
}

Your iterations with Stream are ok, but instead of use Stream because you are working with int values you can use instead IntStream simplifyng the code:

Stream.of(things).forEach(t -> System.out.println(Arrays.stream(t.getArr()).max().getAsInt()));

Below the code of class Thing including all my modifies:

package codereview;

import java.util.Arrays;
import java.util.Random;
import java.util.stream.Stream;

public class Thing {

    private int[] arr;

    public Thing() {
        Random r = new Random();
        this.arr = new int[] {r.nextInt(), r.nextInt(), r.nextInt()};
    }

    public int[] getArr() {
        return arr;
    }

    @Override
    public String toString() {
        return Arrays.toString(arr);
    }

    public static void main(String[] args) {
        Thing[] things = new Thing[10];
        for (int i = 0;i <10; ++i){
            things[i] = new Thing();
            //print 3 numbers in each Thing object
            System.out.println(i + ": " + things[i]);
        }
        System.out.println();
        Stream.of(things).forEach(t -> System.out.println(Arrays.stream(t.getArr()).max().getAsInt()));
    }
}


Is this algorithm efficient for the 01Knapsack? This code uses recursion to solve the 01Knapsack problem. It evaluates all the item permutations that can be added to the knapsack and checks if it gives the maximum profit. What else could have been used to get a faster solution?

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

class Item {

    static int id = 0;
    int weight;
    int cost;
    double ratio;
    int itemNo = ++id;

    boolean taken = false;

    public Item(int weight, int cost) {
        this.weight = weight;
        this.cost = cost;
        this.ratio = (double) cost / weight;
    }

    public String toString() {
        return itemNo + "";
    }
}

class Store {

    List<Item> store = new ArrayList<>();

    public Store() {
        takeInput();
    }

    Item getNextHighestRatioItem() {
        int i = -1;
        double highestRatio = Double.MIN_VALUE;
        for (int j = 0; j < store.size(); ++j) {
            double thisRatio = store.get(j).ratio;
            if (thisRatio > highestRatio) {
                i = j;
                highestRatio = thisRatio;
            }
        }
        return store.get(i);
    }

    public void takeInput() {

        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of items: ");
        int nItems = scan.nextInt();

        int weight, cost, ratio;
        for (int i = 0; i < nItems; ++i) {
            System.out.println("Enter item " + (i + 1) + "'s weight and cost: ");
            weight = scan.nextInt();
            cost = scan.nextInt();

            Item item = new Item(weight, cost);
            store.add(item);
        }
    }

    public int getSize() {
        return store.size();
    }
}

class Knapsack {

    Set<Item> knapsack = new HashSet<>();
    int maxWeight = 50;
    int weight;

    public boolean addItem(Item item) {
        if (weight + item.weight > maxWeight) {
            return false;
        }
        knapsack.add(item);
        weight += item.weight;
        return true;
    }

    public void removeItem(Item item) {
        knapsack.remove(item);
        weight = weight - item.weight;
    }

    public boolean isFull() {
        return weight == maxWeight;
    }

    public int calculateTotalWorth() {
        int sum = 0;
        for (Item item : knapsack) {
            sum += item.cost;
        }
        return sum;
    }

}

public class KnapsackProblem01 {

    Store store = new Store();
    Knapsack knapsack = new Knapsack();

    int worth = 0;

    public void fillKnapsack() {

        int thisWorth = knapsack.calculateTotalWorth();
        if (thisWorth > worth) {
            worth = thisWorth;
            System.out.println("Found a better solution " + worth);
            System.out.println("Knapsack has items: ");
            for (Item i : knapsack.knapsack) {
                System.out.print(i + " ");
            }
        }

        if (knapsack.isFull()) {
            return;
        }

        for (Item i : store.store) {
            if (i.taken) {
                continue;
            }
            if (knapsack.addItem(i)) {
//                System.out.println("Added item "+i+" to the knapsack");
                i.taken = true;
                fillKnapsack();
                knapsack.removeItem(i);
//                System.out.println("Removed item "+i+" from the knapsack");
                i.taken = false;
            }
        }
    }

    public static void main(String[] args) {
        KnapsackProblem01 kp = new KnapsackProblem01();
        kp.fillKnapsack();
    }
}

It's no way optimal. Looking at the wiki, there are algorithms using dynamic programming, which are surely faster.

The other thing is fooling around with a HashSet. It's a nice and fast data structure, but all you need is a boolean[], which is an order of magnitude faster. And it also makes it all simpler.

Item#taken is not a good idea. It should a property of the knapsack, the item doesn't really care. Imagine, you'd parallelize your program, then you'd need an immutable Item.

calculateTotalWorth should be replaced by an incremented computation the way weight gets computed.

The knapsack.worth should only be checked when no item fits. Otherwise, you know that it's not optimal yet.


Providing unchecked exception "wrapper" interfaces for an API with checked exceptions I recently had a discussion in the forum of an API, because they changed an exception from checked to unchecked. I believed it needs to be checked, because it is recoverable. The arguments of "the other side" were verbosity and tediousness of try/catch or throws.

If it were purely theoretical question, I'd be right, but I agree that in practice it is sometimes tedious to write all these try/catches just for the sake of rethrowing unchecked exceptions, or logging.

So, an idea came to my mind, and I wonder whether it's viable. I'll illustrate with simple code:

public interface Foo {
    String foo() throws Exception;
}

public interface EasyFoo extends Foo {
    String foo();
}

These are two interfaces that define the same method (and this is enforced by inheritance), but the "easy" version does not define throwing checked exceptions. Then come 2 default implementations:

public class FooImpl implements Foo {

    @Override
    public String foo() throws Exception {
        return "foo";
    }
}

public class EasyFooImpl implements EasyFoo {

    Foo foo;

    public EasyFooImpl(Foo foo) {
        this.foo = foo;
    }

    @Override
    public String foo() {
        try {
            return foo.foo();
        } catch (Exception ex) {
            throw new RuntimeException(ex);
        }
    }
}

The latter delegates to the former, wrapping all exceptions in runtime exceptions.

And finally a factory:

public class FooFactory {
    public static Foo createFoo() {
        return new FooImpl();
    }

    public static EasyFoo createEasyFoo() {
        return new EasyFooImpl(new FooImpl());
    }
}

The benefits:

the user of the API can choose how he likes to use the implementation. If he doesn't intend to do anything with the checked exceptions, he can use the "easy" version
you support only one interface. The 2nd is the same, and you'll just have to add the methods that you have in the main one.
the user can use the EasyFoo in places where Foo is required:

EasyFoo foo = FooFactory.createEasyFoo();
helper.doSomething(foo); // which is public void doSomething(Foo foo);

Enough foos - the question is, is this a viable solution that can reduce verbosity while retaining the good sides of checked exceptions?

Just accept the fact that the exception is unchecked and move on.

The industry is moving away from checked exceptions: C++ never had them, C# decided not to follow Java in this place, and the latest frameworks for Java are using unchecked exceptions.

Face it, checked exceptions are a nice idea that doesn't work in practice.

As a result, the thing you try in your code, will never pass any code review I'll be part of.


Proxy test class approach to allow covering legacy code with unit tests There is huge legacy class MyService in which several new business cases need to be implemented. Unfortunately we are not allowed to touch existing legacy code within _legacyMethod and need to build a new condition on top of it. However I'd like to have a new code covered with unit tests (using NUnit)

public class MyService
{
    public bool Execute()
    {
        return _newMethod() && _legacyMethod();
    }

    protected virtual bool _newMethod()
    {
        // some business logics

        return true;
    }

    protected virtual bool _legacyMethod()
    {
        // hundreds of lines of code

        return false;
    }
}

So primarily my goals were:

Leave legacy method protected
Cover new methods with unit tests
Cover integration of new methods with legacy code

To achieve this I built a proxy within test class:

using NUnit.Framework;

[TestFixture]
public class MyServiceTests
{
    private MyServiceProxy _sut;

    [SetUp]
    public void SetUp()
    {
        _sut = new MyServiceProxy();
    }

    [TearDown]
    public void TearDown()
    {
        _sut = null;
    }

    [Test]
    [TestCase(true, true, true)]
    [TestCase(false, true, false)]
    [TestCase(true, false, false)]
    [TestCase(false, false, false)]
    public void Execute_ReturnsExpected(bool newMethodStub, bool legacyMethodStub, bool expectedResult)
    {
        _sut.LegacyMethodStub = legacyMethodStub;
        _sut.NewMethodStub = newMethodStub;

        var result = _sut.Execute();

        Assert.AreEqual(expectedResult, result);
    }

    [Test]
    public void NewMethod_ReturnsTrue()
    {
        var result = _sut.NewMethodProxy();

        Assert.That(result, Is.True);
    }

    public class MyServiceProxy : MyService
    {
        public virtual bool NewMethodProxy()
        {
            return base._newMethod();
        }

        public bool? NewMethodStub { get; set; }

        public bool? LegacyMethodStub { get; set; }

        protected override bool _newMethod()
        {
            if (NewMethodStub.HasValue)
            {
                return NewMethodStub.Value;
            }
            return base._newMethod();
        }

        protected override bool _legacyMethod()
        {
            if (LegacyMethodStub.HasValue)
            {
                return LegacyMethodStub.Value;
            }

            return base._legacyMethod();
        }
    }
}

In such a way I managed to have a separate set of tests for new method itself, and another one - for integration old-new logics within Execute method.
Could you advice please if this approach is applicable or can be simplified/improved somehow?

public class MyService
{
    public bool Execute()
    {
        return _newMethod() && _legacyMethod();
    }

    protected virtual bool _newMethod()
    {
        // some business logics

        return true;
    }

    protected virtual bool _legacyMethod()
    {
        // hundreds of lines of code

        return false;
    }
}

You abuse inheritance for testing purposes instead of splitting it up in two classes - one for each service. The current solution also violates the Open/Closed Principle. If you wanted to add another service or logic later you couldn't do it without modifying this god-service.

Virtual/abstract methods should have some purpose and be overriden in a concrete implementation and not used as workaround for testing.

You could improve it by either implementing the decorator pattern or using inheritance correctly. Here are two examples.

Decorator

I find the decorator pattern would be a better choice here. With a decorator you would define an interface like

interface IService
{
    bool Execute();
}

and implement it in two classes. One for the legacy service:

public class MyLegacyService : IService
{
    public bool Execute()
    {
        // hundreds of lines of code
    }
}

and one for the new service:

public class MyNewService : IService
{
    private readonly IService _service;
    public MyNewService(IService service)
    {
        _service = service;
    }

    public bool Execute()
    {
        return ExecuteInternal() && _service.Execute();
    }

    private bool ExecuteInternal()
    {
        ..
    }
}

This has the advantage that you can provide any IService to the decorator and test the new logic independently. You can easily create a test-service to fake the legacy one.

Inheritance

If you want to do it with inheritance then the new service should be derived from the legacy service that is derived from an abstract base service.

The overridable method should then be called ExecuteCore. The base service just calles the core method:

public abstract class MyService
{
    public bool Execute()
    {
        return ExecuteCore();
    }

    protected abstract bool ExecuteCore();
}

The legacy-service implements the core method:

public class MyLegacyService : MyService
{
    protected override bool ExecuteCore()
    {
        // hundreds of lines of code

        return false;
    }
}

and the new-service implements it in its own way and using its base class core method:

public class MyNewService : MyLegacyService
{
    protected override bool ExecuteCore()
    {
        // some new business logics

        return newResult && base.ExecuteCore();
    }
}

This will be a little bit harder to test as the new-service depends on the legacy one so you would need to stub it in tests. Nothing impossible but more work then with the decorator.


Alternate Tree implementation I am trying to implement algorithms related to trees in Scala. I have dabbled with the following implementations of a tree. Are there any pros and cons of preferring the non-Option related implementation over the one that uses Option?

Implementation with Option:

  sealed trait Node {
    val label: Int
  }
  case class LeafNode(override val label: Int) extends Node
  case class BranchNode(override val label: Int, left: Option[Node], right: Option[Node]) extends Node

  def inorderTraversal(aTree: Option[Node]): List[Int] = {
    def helper(aTree: Option[Node], acc: List[Int]): List[Int] = aTree match {
      case None => acc
      case Some(LeafNode(label)) => helper(None, label :: acc)
      case Some(BranchNode(label, left, right)) => helper(left, acc) ++ helper(None, label :: acc) ++ helper(right, acc)
    }
    helper(aTree, List.empty[Int])
  }

Implementation without Option:

  sealed trait Tree {
    def value: Int
    def left: Tree
    def right: Tree
    def isEmpty: Boolean
    def inorder(acc: List[Int]): List[Int] = {
      if (isEmpty) acc else {
        left.inorder(acc) ++ List(value) ++ right.inorder(acc)
      }
    }
  }

  case object Leaf extends Tree {
    override def value = throw new IllegalArgumentException
    override def left = throw new IllegalArgumentException
    override def right = throw new IllegalArgumentException
    override def isEmpty = true
  }

  case class Branch(override val value: Int, left: Tree=Leaf, right: Tree=Leaf) extends Tree {
    override def isEmpty = false
  }

The Option related implementation leads to a lot of pattern matching code, sometimes multiple case statements. Whereas with the non-Option method I can get by using the isEmpty check. I am biased towards the non-Option method because the code appears simpler to follow.

Which one is better and why?

I don't like either implementation, but since you asked, the first one is the least bad since it makes better use of case classes. And that brings me to my first point,

You need to make use of case classes (better)

And it all starts with the first thing you did in your code. Because you did this:

sealed trait Node {
   val label: Int
}

You just automatically eliminated the ability to create empty trees due to the fact that every tree now has to contain an item. This puts you in a bad position because as you have noticed, you now have no choice but to resort to Options. Don't get me wrong, Option monads are great but when used in such a manner it does them no justice.

Anyways, I suggest removing the val label: Int and just having an empty sealed trait.

sealed trait Node {}

Then you can also remove the override from your other classes:

case class LeafNode(label: Int) extends Node
case class BranchNode(label: Int, left: Option[Node], right: Option[Node]) extends Node

Still looks pretty bad, but we can fix that.

Case Objects are still a thing

From the above use of Option, it would seem that you are trying to say that a BranchNode can sometimes contain a node and other times, contain nothing. In that case, let's create a better representation of "Nothing" by making use of case objects:

case object EmptyNode extends Node

Aha! you say

Mhm I reply

Since we now have a case object to represent the Empty state of a tree, let's reconstruct our tree now

case object EmptyNode extends Node
case class LeafNode(label: Int) extends Node
case class BranchNode(label: Int, left: Node, right: Node) extends Node

And there you go, a perfect recipe for great pattern matching.

With this in order, we can now reconstruct the traversal method. Note you have two options with this, either create an implicit class which implements the traversal method and allows you to do tree.inorderTraversal or create a method which takes the tree as you have already done. For this demonstration, I will opt for the implicit class option:

implicit class InorderTraversable(val aTree: Node) extends AnyVal {
    def inorderTraversal: List[Int] = aTree match {
        case EmptyNode => List()
        case LeafNode(item) => List(item)
        case BranchNode(item, left, right) => (left.inorderTraversal :+ item) ++ right.inorderTraversal
    }
}

Other statements

Avoid nesting functions if you can
Try to throw less exceptions
Use pattern matching to your full advantage. Read more here

Putting it all together:

package com.codereview

sealed trait Node {}
case object EmptyNode extends Node
case class LeafNode(label: Int) extends Node
case class BranchNode(label: Int, left: Node, right: Node) extends Node

object Main extends App {
    implicit class InorderTraversable(val aTree: Node) extends AnyVal {
        def inorderTraversal: List[Int] = aTree match {
            case EmptyNode => List()
            case LeafNode(item) => List(item)
            case BranchNode(item, left, right) => (left.inorderTraversal :+ item) ++ right.inorderTraversal
        }
    }

    val tree =
    BranchNode(1,
        BranchNode(2,
            BranchNode(3,
                BranchNode(4, LeafNode(6), LeafNode(5)),
                BranchNode(7, LeafNode(8), EmptyNode)),LeafNode(9)), LeafNode(10))

    println(tree.inorderTraversal)
}


Convert Persian digits to English numbers I use the following code to convert ۱۲۳۴۵ to 12345, effectively transliterating the persian numbers into latin numbers:

String.prototype.toEnglishDigits = function () {
        var num_dic = {
            '۰': '0',
            '۱': '1',
            '۲': '2',
            '۳': '3',
            '۴': '4',
            '۵': '5',
            '۶': '6',
            '۷': '7',
            '۸': '8',
            '۹': '9',
        }

        return parseInt(this.replace(/[۰-۹]/g, function (w) {
            return num_dic[w]
        }));
    }

console.log('۱۲۳۴۵'.toEnglishDigits());

Instead of using a map,
you can get the corresponding digits directly by subtracting the character code of '۰'.
That is, since the character code of '۳' is 1779
and the character code of '۰' is 1776, you can calculate that:

'۳'.charCodeAt(0) - '۰'.charCodeAt(0) = 1779 - 1776 = 3

Using the above logic, the function can be written shorter:

String.prototype.toEnglishDigits = function () {
    var charCodeZero = '۰'.charCodeAt(0);
    return parseInt(this.replace(/[۰-۹]/g, function (w) {
        return w.charCodeAt(0) - charCodeZero;
    }));
}


Interleave data using Java protected static String[] applyInterleave(String interleave, int lengthOfSequence, int numOfPermutations){
    String[] interleavedPatterns = new String[numOfPermutations];
    char[] pattern = interleave.toCharArray();
    StringBuilder interleavedPattern = new StringBuilder("");

    for(int i = 0; i < numOfPermutations; i++){
        char[] data = designs[i].toCharArray();
        for(int j = 0; j < lengthOfSequence; j++)
            interleavedPattern.append(data[Character.getNumericValue(pattern[j])-1]);

        interleavedPatterns[i] = interleavedPattern.toString();
        interleavedPattern = new StringBuilder("");
    }
    return interleavedPatterns;
}

In this code, design is of size numOfPermutations and each element in design is a string of length lengthOfSequence. Now, I am taking each element in design and applying an interleave mapping based on the parameter interleave.

For instance, let's say the string is 1432. Then, I take each element in design and I reorder it so that the 1st char of string is still the 1st, then the 4th char becomes the 2nd, the 3rd char stays the 3rd, and the 2nd char becomes the 4th.

For example, if the first element in design, design[0] = 4321 and if the passed in parameter for interleave is 1432 then 4321 is reordered as 4123. There are very specific reasons why I am only working with String instead of int, so I am not interested in changing the variable types.

Now, if my design array is really large, say 362880 indices long, then this method takes quite a while. I have optimized to the best of my ability, but is there a way to speed this up even more?

Optimization 1
Instead of constantly doing Character.getNumericValue(pattern[j])-1 in the inner loop, you could create a precomputed integer array to hold those values.  That way, you could replace that expression with patIndex[j].
Optimization 2
Instead of using multiple instances of StringBuilder, you could use and reuse a single char array and create strings from that.
Optimization 3
Instead of creating a char array from your designs[i] string, you could just leave designs[i] as a string and use String.charAt() to read each character.
Sample rewrite
Using the above 3 optimizations, I arrived at:
static String[] applyInterleave(String interleave, int lengthOfSequence,
        int numOfPermutations)
{
    String[] interleavedPatterns = new String[numOfPermutations];
    char  [] pattern  = interleave.toCharArray();
    int   [] patIndex = new int[lengthOfSequence];

    for (int i = 0; i < lengthOfSequence; i++) {
        patIndex[i] = Character.getNumericValue(pattern[i])-1;
    }

    for(int i = 0; i < numOfPermutations; i++) {
        String s = designs[i];
        for(int j = 0; j < lengthOfSequence; j++) {
            pattern[j] = s.charAt(patIndex[j]);
        }
        interleavedPatterns[i] = new String(pattern);
    }
    return interleavedPatterns;
}

I tested this against the original function and found that it was approximately 3x faster.


JS code that search through every property in a nested object I wrote code to search by keyword, and it will check all of the values from the object property, including an array in the object.  But apparently the code is not optimized as it takes some time to execute the function, and it is subject to client PC processing power.

Here is the sample of the object:

{
    clientId: "-LFQ1ojwCF8lSRq4J9sQ",
    desc: "description lorus ipsum etc",
    document: [
      {
        doc: "photo",
        status: "ok",
        url: "https://www.google.com"
      }
    ],
    dt: "2018-06-24",
    dtactual: "2018-06-26",
    dtcreate: 1529905260612,
    dtexpected: "2018-06-25",
    dtmodify: 1529905260612,
    dtreceive: "2018-06-26",
    engineer: "engineer 001",
    equipment: [
      { brand: "ruckus", imei: 123, imsi: 312, model: "R230-1220v6HW", serialNo: 123},
      { brand: "", imei: "", imsi: "", model: "", serialNo: ""},
      { brand: "", imei: "", imsi: "", model: "", serialNo: ""},
      { brand: "", imei: "", imsi: "", model: "", serialNo: ""},
      { brand: "", imei: "", imsi: "", model: "", serialNo: ""}
    ],
    iwoNum: "iwo num 2",
    key: "-LFpT2ajia6Wgnrd8lQH",
    onSiteSupport: { isSupport: true, supportTerm: "" },
    pm: "project manager 001",
    poNum: "po no 002",
    preventMaintenance: true,
    projectType: "site installation",
    remark: "iwo remark",
  }

Imagine there are 50 or 100, or 1000 of the object in an array, and the user wishes to list the object that contains a specific keyword. So the code need to search every property to find the value.

So below is my code (written in Typescript, but almost same with JS):

iwoLit = []
objectArray = [{...},{...},{...},...]
//the details of the object in this array please refer to above object as it is too long to place at here.
//Feel free to change any value in there.
keyword = 'ruckus'

searchFunction(){
  objectArray.forEach(element => {
    let object = Object.assign({}, element);
    object['key'] = element.key;
    let keys = Object.keys(object)
    for (let i = 0; i < keys.length; i++) {
      let prop = keys[i]
      let item = object[prop]
      if (typeof item == 'string') {
        let item2 = item.toString()
        let item3 = item2.toLowerCase()

        if (item3.indexOf(this.keyword.toLowerCase()) !== -1) {
          if (this.iwoList.length == 0) {
            this.iwoList.push(object);
          }
          else {
            for (let l = 0; l < this.iwoList.length; l++) {
              if (object.key !== this.iwoList[l].key) {
                this.iwoList.push(object);
                return false
              }
            }
          }
        }

      }
      //to handle the array in the object
      let equipValue3
      if (Array.isArray(item)) {
        item.forEach(element2 => {
          let itemKeys = Object.keys(element2)
          for (let j = 0; j < itemKeys.length; j++) {
            let prop2 = itemKeys[j]
            let equipValue = element2[prop2]
            if (typeof equipValue == 'string' || typeof equipValue == 'number') {
              let equipValue2 = equipValue.toString()
              equipValue3 = equipValue2.toLowerCase()
              if (equipValue3.indexOf(this.keyword.toLowerCase()) !== -1) {
                if (this.iwoList.length == 0) {
                  this.iwoList.push(object);
                }
                else {
                  for (let k = 0; k < this.iwoList.length; k++) {
                    if (object.key !== this.iwoList[k].key) {
                      this.iwoList.push(object);
                      return false
                    }
                  }
                }
              }
            }
          }
        })
      }
    }
  });
  console.log(this.iwoList)
}

Would be appreciated if someone can help me optimize the code. It is ok to separate in few functions, as long as the performance can be increased.

Side info: Why do I want to make such a nested object? Because I am using noSQL, and this is the DB design.

Too much messing about in hyper space.

You have way too much messing about. Object.assign is slow and more so when you don't need it.

RegExp is fast

If you are going to search strings use a RegExp it is far far quicker. And if not don't convert the same value to lower (or upper) case every time you need to check it. Once is all you need to do.

I can not quite workout where you are getting element.key from.

Set and Map for lookups

Rather than search manually over an array of keys you can use a Set that will provide fast hash table lookup

// at the very start of the search create an empty set
var foundKeys = new Set();

...

// then rather than loop over iwoList check if the set already has the key
if (!foundKeys.has(object.key)) {
    foundKeys.add(object.key);  // if not add the new one
    this.iwoList.push(object);
}
// saving a mass of cycles.

Look for the quick answer

It would be better to check the foundKeys set right at the start before you search the object. No point searching for a match only to dump the result because you have that key. Make it the first thing to check before you search the object, first thing inside the loop would be the best way to avoid many cycles.

Bloat also eats cycles

Its all a little hanging out and bloated at the start.

 let object = Object.assign({}, element);  // object is copied from element
 object['key'] = element.key;  // then you copy key, but key will be in object from the line above
 let keys = Object.keys(object)   // then create a keys array and a iterator index
 for (let i = 0; i < keys.length; i++) {
   let prop = keys[i]  // another variable
   let item = object[prop]  // and another

Why not just the one line, same as the 6 above just much quicker...

for(const item of Object.values(element)){

The rewrite

Without more info, I read your code to find the first instance of the search term and add the object that it was part of from the objectArray to the result.

Checking arrays, and objects, and matching any strings or numbers found, case insensitive.

As a standalone function the following returns an array of objects that contain a property that matches keyword. I would assume that the objects come from a JSON so have ignored any cyclic references problems (which can be checked with a Set if needed)

The string matching is via a regExp

The whole thing is just an extended Array.filter call

function search(array, keyword) {
  const regExp = new RegExp(keyword,"gi");
  const check = obj => {
    if (obj !== null && typeof obj === "object") { return Object.values(obj).some(check) }
    if (Array.isArray(obj)) { return obj.some(check) }
    return (typeof obj === "string" || typeof obj === "number") && regExp.test(obj);
  }
  return array.filter(check);
}


Fetching categories and subcategories from database For a small blog with a limited count of categories, I wrote this code to fetch categories and subcategories from the database.

I used a recursive function to call all categories and sub categories , my goal since I do not have a lot of results is to get them all and display them.

So here is my code. I wish to get your feedback about it.

<?php
//mysql cat table table
/*

  CREATE TABLE `cat` (
  `id` int(255) NOT NULL,
  `id_parent` int(255) DEFAULT NULL,
  `name` varchar(255) NOT NULL,
  `descr` varchar(1000) NOT NULL
  )

 */
//preparing dsn var for PDO
$dsn = 'mysql:host=localhost;dbname=dbname';

//instantiating pdo object
$pdo = new PDO($dsn, "dbuser", 'dbpass');

//make a function take sql and pdo object
function getCats($sql, $pdo) {
    //preparing sql statment
    $stmt = $pdo->prepare($sql);
    //executing our query
    $stmt->execute();
    //saving results in array
    $array = $stmt->fetchAll();
    //checking if array siez is zero we return 1;
    if ($array == []) {
        return 1;
    }
    //var_dump($array);
    //outputting html list for all our cats
    echo "
";
    for ($i = 0; $i < count($array); $i++) {
        echo "
";
        echo $array[$i]['name'];
        echo "
";
        //calling recursive function to get sub cats
        getCats("SELECT * from cat where id_parent = {$array[$i][0]}", $pdo);
    }
    echo '
';
}

//calling the function
getCats("SELECT * from cat where id_parent is NULL", $pdo);

In no particular order:

Your id_parent field is nullable, and you use this fact to flag the category as having no parent.  This forces you to treat the field differently id_parent is NULL verse id_parent = ....  If you used a magic number, such as 0 to represent no parent, you could treat top level and child categories similarly.

You use a prepared statement, but create the SQL dynamically with "... where id_parent = {$array[$i][0]}".  This is poor design.  Use prepared statements with bound parameters to prevent SQL injection & gain efficiency.

When you query your table, you retrieve all columns of data, but you are only using the name column and the 0th column.  Use "select id, name from..." to just retrieve the data you are going to use.  Not only do you gain efficiency, you document the code with the fields you will be using, and gain resilience against table structure changes that change the column indices.

The name column and the 0th column??  Be consistent; don't mix names and column numbers.

You are querying your SQL table multiple times, once for each possible category parent.  With n categories, you query the table n+1 times!  With such a small table, it would be better to query the table once, store the data in in-memory arrays, and then print the data from the in-memory arrays.

Why return 1;?  Nothing is returned when the function exits normally.  You could just return;.  Or better, reverse the test, put the print loop in the then clause, and don’t have any embedded returns!

Your SQL table should list id as primary key and possibly id_parent as foreign key references cat(id).

Sample code:

Building up the category ($cat) array with a single SQL query:

$stmt = $pdo->prepare("select id, name, id_parent from cat");
$stmt->execute()
$result = $stmt->fetchAll();

$root_id = NULL;
$cat = [$root_id => [ 'name' => '', 'children' => []]];

# Create $cat[id] entries for each row in table, with empty children list
foreach($result as $row) {
    $cat[$row['id']] = [ 'name' => $row['name'], 'children' => [] ];
}

# Add each item to its parent's children list
foreach($result as $row) {
    $cat[$row['id_parent']]['children'][] = $row['id'];
}

Displaying the categories from in-memory array:

function showCat($cat, $id) {
    echo $cat[$id]['name'];
    $children = $cat[$id]['children'];
    if ($children) {
        echo "
";
        foreach($children as $child_id) {
            echo "
";
            showCat($cat, $child_id);
            echo "
";
        }
        echo "
";
    }
}

showCat($cat, $root_id);


Clamp a PHP variable to a 0-to-4 range I have a legacy code written as below:

if($value < 0) {
    $value = 0;
}
if($value > 4) {
    $value = 4;
}

Is there an easier and more elegant way to do this?

Selecting the "best" method in this case is likely going to come down to personal preference.

If you wish to use a condition-less one-liner, then insertusernamehere's offering is brief/elegant.  However, it is not instantly comprehensible for the next developer.

min(max($value, 0), 4)

If you want a one-liner with conditions (or without functions), then this is what Billal was mentioning:

$value < 0 ? 0 : ($value > 4 ? 4 : $value)

However, the php manual says:

  It is recommended that you avoid "stacking" ternary expressions.

I personally find switch statements to be too clunky/verbose with the breaking.  While it is nice that it only evaluates $value once, that is of very little benefit in your tiny use case.

Finally, I recommend simply changing your second if statement to elseif so that the second statement is ignored when the first is true.  This method will be fast, clean, and instantly comprehensible.

if ($value < 0) {
    $value = 0;
} elseif ($value > 4) {
    $value = 4;
}

...if > 4 occurs more often than < 0, then reverse the order of the conditionals.

Here is a demo snippet:

$input = [-1, 0, 2, 4, 7];
foreach ($input as $value) {
    echo min(max($value, 0), 4) , "\n";
    echo $value < 0 ? 0 : ($value > 4 ? 4 : $value) , "\n";
    if ($value < 0) {
        $value = 0;
    } elseif ($value > 4) {
        $value = 4;
    }
    echo $value , "\n---\n";
}


Write a function to extract a given number of randomly selected elements from a list I'm going through the 99 Haskell problems and I have a few question about the solution I implemented for Problem 23.

It asks:

  Extract a given number of randomly selected elements from a list.

This is the code I came up with:

-- Extract a given number of randomly selected elements from a list.
import System.Random

randomFromList :: StdGen -> Int -> [a] -> ([a], StdGen)

randomFromList generator 0 _ = ([], generator)
randomFromList generator toDo xs =
  let (nextInt, generator') = next generator
      index = mod nextInt (length xs)
      (otherNumbers, generator'') = randomFromList generator' (toDo -1) xs
  in  ((xs !! index) : otherNumbers, generator'')

It works, but I'm not sure this is idiomatic Haskell nor that it is the best way to address this problem.

None of the solutions in the Haskell wiki uses the let approach so I was wondering if it is discouraged for some reason.

Your solution looks good to me, no reason to discourage using let as far as I know.

Tip: if you make the type randomFromList :: Int -> [a] -> StdGen -> ([a], StdGen), then you can call it like this: main = getStdGen >>= print . randomFromList 7 ['A'..'Z']

Also, if the requirement is interpreted as selecting randomly without replacement, your version only needs slight modification (this also uses randomR rather than mod):

dropAt :: Int -> [a] -> [a]
dropAt k xs = take k xs ++ drop (k+1) xs

randomFromList :: Int -> [a] -> StdGen -> ([a], StdGen)
randomFromList 0 _ generator = ([], generator)
randomFromList _ [] generator = ([], generator)
randomFromList toDo xs generator =
  let (index, generator') = randomR (0, length xs - 1) generator
      (otherNumbers, generator'') = randomFromList  (toDo -1) (dropAt index xs) generator'
  in  ((xs !! index) : otherNumbers, generator'')

See also this shuffle implementation for some attempt at optimisation.  (You could potentially solve the random selection by something like take n . shuffle.)


Cleanest way to get list of Django objects that have same foreign key and display them in a view I am a beginner in Django and would like some advice regarding best practices.

I have the following model:

class Company(models.Model):
    name = models.CharField(max_length=200)

class Interview(models.Model):
    company = models.ForeignKey(Company, on_delete=models.CASCADE)
    position = models.CharField(max_length=200)

(I didn't include the __str__ methods for conciseness)

I have the following path:
path('<int:company_id>/', views.detail, name='detail')

Where I want the company to be displayed (let's say its company_id=1, along with all the interview objects that have company=1). So the view should look something like:

Here is my view method:

def detail(request, company_id):
    company = get_object_or_404(Company, pk=company_id)
    return render(request, 'core/detail.html', {'company': company, 'interviews': Interview.objects.filter(company_id=company_id)})

And my detail.html file:

{{ company }}

{% for interview in interviews %}

{{ interview.position }}

{% endfor %}

Which works. However, I am not sure if passing the interviews QuerySet like that is a good practice or not. Is there a way to pass only the company object and get the interviews from that? In general, is there a better way to get a list of objects that have the same foreign key? In this case for example, would it be possible to instead of doing:

Interview.objects.filter(company_id=company_id)

Doing:

company.interviews

However, I am not sure if passing the interviews QuerySet like that is a good practice or not.

This is good practice, known as dependency injection. If someone asks for your business card, you wouldn't give them your wallet and let them fish it out - you can think of passing objects to the template renderer the same way. Passing only the company object would mean there would have to be more logic in your detail.html template to fish out the interviews, which is less than ideal. The way you currently do it serves as documentation as to what objects are required by the detail.html template.

  In general, is there a better way to get a list of objects that have the same foreign key?

You can specify a related_name for the company foreign key on your Interview model like so.

class Company(models.Model):
    name = models.CharField(max_length=200)

class Interview(models.Model):
    company = models.ForeignKey(Company, related_name='interviews', on_delete=models.CASCADE)
    position = models.CharField(max_length=200)

Then you can access all interviews for a company like company.interviews.all()


FCFS with character invalid Any suggestion to improve this, they ask me to input characters that should be an invalid input and ask you again to input the number of process without crashing the program.

#include<iostream>
#include<ctype.h>
using namespace std;

int main()
{
     int bt[20],wt[20],avwt=0,i,j;
     int n;

     cout<<"Enter total number of processes(maximum 20):";
     cin>>n;
     while(char (n))
     {
          if(isalpha(n))
          {
                cout<<"Invalid Input";
          }

       cout<<"\nEnter Process Burst Time\n";
       for(i=0;i<n;i++)
       {
            cout<<"P["<<i+1<<"]:";
            cin>>bt[i];
       }

       wt[0]=0;
       for(i=1;i<n;i++)
       {
             wt[i]=0+bt[i];
             for(j=0;j<i;j++)
             wt[i]+=bt[j];
       }

        cout<<"\nProcess\t\tBurst Time\tArrival Time";

        for(i=0;i<n;i++)
        {

             avwt+=wt[i];
             cout<<"\nP["<<i+1<<"]"<<"\t\t"<<bt[i]<<"\t\t"<<wt[i];
        }

        avwt/=i;

        cout<<"\n\nAverage Waiting Time:"<<avwt;
    }
    return 0;
  }

Not sure exactly what this code is supposed to accomplish, but there are at least a few comments I think are valid regardless.

Avoid using namespace std;

This brings an extremely large number of names into scope. While perfectly reasonable with other namespaces, you usually want to avoid it with the std namespace.

Your use of isalpha

This code:

 cout<<"Enter total number of processes(maximum 20):";
 cin>>n;
 while(char (n))
 {
      if(isalpha(n))
      {
            cout<<"Invalid Input";
      }

... makes very little (if any) sense to me. You've read a number from the user, then you're trying to use isalpha on that. Since (in C and C++) char is a small integer type, it's valid (from the compiler's viewpoint) to pass that int to isalpha, but it's really not meaningful at all.

Given that you want a number less than or equal to 20, it would probably be best to check for that before using it though--as it stands now, if the user enters something like 30, the code will blithely continue trying to run, and write past the ends of the arrays it has allocated.

Use of arrays

That brings us to the next obvious problem: you're probably a lot better of using something like std::vector (or possibly std::array) rather than the arrays that are built into the language. These behave much better in general: they know their own size, don't decay to points the minute you look at them wrong, and are generally just a whole lot better.

Treat users humanely

Demanding that a user enter 20 (or even 10) process burst times interactively is inhumane. It would be much better to (for example) accept a file containing the burst times instead.

Use applicable standard algorithms

First of all, it looks to me like your computation of arrival times:

   wt[0]=0;
   for(i=1;i<n;i++)
   {
         wt[i]=0+bt[i];
         for(j=0;j<i;j++)
         wt[i]+=bt[j];
   }

...is actually broken. Since you're storing the first arrival time as 0, you have a total of one more arrival time than burst times.

I'd switch to using std::vectors as mentioned previously, and then use the standard partial_sum algorithm to do most of the work:

wt[0] = 0;

std::partial_sum(bt.begin(), bt.end(), std::back_inserter(wt));

I believe this produces the results you wanted: for N inputs, it produces 0 for the first result, and each succeeding result is the sum of the burst times up to that point.

Names

Many of the names you've used (e.g., bt, wt, avwt) are (I suppose) quick to type, but certainly hard to read. I'd prefer to see burst_time, wait_time, average_wait, so I could read them a little more easily.

Output

Since you have one more arrival time than burst time, you may want to report your results a little differently. Right now, at least as I read things you're not reporting (or actually even computing) the last arrival time. Since the sequence is really that process 0 starts at time 0, and each successive time is based on the previous process times, I think I'd arrange the columns with the arrival time on the left and the process time on the right, so the numbers read more meaningful from let to right, top to bottom (i.e., in the direction people normally read).

For formatting output into columns, I'd also advise using std::setw instead of tabs.

Putting those together, we might end up with code something like this:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <numeric>
#include <fstream>
#include <iomanip>

int main(int argc, char **argv) {

    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <filename>\n";
        return EXIT_FAILURE;
    }

    std::ifstream in(argv[1]);

    // Read the burst times from the file into our vector:
    std::vector<int> burst_times{ std::istream_iterator<int>(in), {} };

    std::vector<int> arrival_times{ 0 };
    std::partial_sum(burst_times.begin(), burst_times.end(),
                     std::back_inserter(arrival_times));

    int width = 10;
    std::cout << "\n" << std::setw(width) << "Process"
                      << std::setw(width) << "Arrival"
                      << std::setw(width) << "Duration" << "\n";

    int i;
    for (i = 0; i < burst_times.size(); i++)
        std::cout << std::setw(width) << i + 1
                  << std::setw(width) << arrival_times[i]
                  << std::setw(width) << burst_times[i] << "\n";

    std::cout << std::setw(width) << i + 1
              << std::setw(width) << arrival_times[i] << "\n";

    auto total_times = std::accumulate(arrival_times.begin(), arrival_times.end(), 0);
    auto average_time =  total_times / arrival_times.size();

    std::cout << "\n\nAverage Waiting Time: " << average_time << "\n";
}


Dynamic array implementation I would like to use code below for general purpose dynamic array implementation in my future code. How does it look?

array.h:

#include <stdlib.h>

/* This file describes structures and functions
   for general purpose dynamic array.
*/

struct array {
    void *data;       /* Points to where the data is */
    int numElements;  /* Number of elements */
    int sizeElem;     /* Size of a single elements */
    int capacity;     /* Current total space in number of elements */
};

/* macros for accessing array internals */
#define array_index(ARRAY, INDEX) (void *)((unsigned)((ARRAY)->data)+(INDEX*((ARRAY)->sizeElem)))
#define array_len(ARRAY) (ARRAY)->numElements
#define array_cap(ARRAY) (ARRAY)->capacity

static inline void array_init(struct array *arr, int capacity, int sizeElem) {
    arr->data = malloc(capacity * sizeElem);
    arr->capacity = capacity;
    arr->sizeElem = sizeElem;
    arr->numElements = 0;
}

/* Add an element to array. Expand array if necessary. */
static inline void array_add(struct array *arr, void *data) {
    if (arr->capacity <= arr->numElements) {
        int new_capacity = 2 * arr->capacity;
        arr->data = realloc(arr->data, new_capacity * arr->sizeElem);
        arr->capacity = new_capacity;
    }
    memcpy(array_index(arr,arr->numElements), data, arr->sizeElem);
    arr->numElements++;
}

/* Macro for traversing array elements. */
#define array_for_each(TYPE, ELEM, ARRAY) \
    for (TYPE *ELEM=(ARRAY)->data; (ELEM - (TYPE *)(ARRAY)->data) < (ARRAY)->numElements; ELEM++)

/* Removes the element at given index and moves other elements if necessary. */
static inline void array_delete_index(struct array *arr, int index) {
    int movables = arr->numElements - index - 1;
    memcpy(array_index(arr, index),
           (void *)((unsigned)array_index(arr, index) + arr->sizeElem),
           movables * arr->sizeElem);
    arr->numElements--;
}

/* If array capacity is too much compared to number of elements,
   reduce array capacity
*/
static inline void array_free_capacity(struct array *arr) {
    if (arr->capacity > 2*arr->numElements) {
        int new_capacity = arr->capacity / 2;
        arr->data = realloc(arr->data, new_capacity * arr->sizeElem);
        arr->capacity = new_capacity;
    }
}

/* Probably useless macro */
#define array_free(ARRAY) free((ARRAY)->data)

/* Search for an element and return an index if found. Otherwise, return -1
   Comparison function should return 0 if two items should be considered equal.
*/
static inline int array_search(struct array *arr, void *target, int (*cmp)(void *first, void *second)) {
    for(int i=0; i<arr->numElements; i++) {
        if(cmp(array_index(arr, i), target) == 0) return i;
    }
    return -1;
}

/* Returns a pointer to the element at given index, if it doesn't
    exist, return NULL
*/
static inline void *array_get_index(struct array *arr, int index) {
    if (index > (arr->numElements - 1)) return NULL;
    return array_index(arr, index);
}

How the code is used:

First you initialize the array with a data type and the initial array capacity, measured in the number of elements that the array can hold.

After that, the functions in array.h can be used to add, remove, traverse the array, and more.

Example:

struct task {
    char *task_name;
    int task_id;
};

struct array my_tasks;
/* Define an dynamic array of struct tasks */
array_init(&my_tasks, 2, sizeof(struct task));

Some good practices:

Assert on NULL parameter

Whenever you have a function passing an array you should either do a runtime check to see if it's NULL or do an assert(array). To catch bugs where a NULL array is passed to the functions.

Check return values for alloc functions

You should always make sure you get a non-NULL result from any allocation, malloc, realloc and such to fail gracefully, or at least exit(1) with a nice out of memory message. Good for catching bugs where accidentally an uninitialized count value is passed to an allocating function.

Check for negative input

Since for instance your numElements is an int instead of size_t you should either change it, or at least check for negative values.

Deleting many values

I don't know how common a use case this would be, but since on each delete, you might move a large chunk of values. Adding a function that either takes a list of indices to delete and do it in one go, by simply refilling the array with those indices excluded. Otherwise iterating over and deleting values can be a huge operation depending on the size of the array.

Destroy function

I agree with this comment:

/* Probably useless macro */
#define array_free(ARRAY) free((ARRAY)->data)

This should be a function that both resets the numElements = 0, capacity = 0 and does the free(array->data) as well as array->data = NULL.

This ensures that any reuse of the array will still result in a reallocation and hence not writing to freed memory. However please note that array_add in this case must check that capacity > 0 and at least set it to 1, otherwise the realloc will be 0.