Find the single smallest IP network with the given IP addresses I have a bunch of IP addresses. I want one IP network that has them all. ipaddr.collapse_address_list already exists, but that gives you a list of all the IP networks that identify your IP addresses, no more, no less, whereas I only need one IP network.

I tried at first using XOR, but that fails on some situations (say, 10.0.0.1, 10.0.0.2, 10.0.0.255, 10.0.0.251: bin(1 ^ 2 ^ 255 ^ 251) = 0b111). And'ing has similar problems. This is what I ended up writing.

#http://stackoverflow.com/a/3789000/13992
def _AllSame(items):
  it = iter(items)
  first = next(it, None)
  return all(x == first for x in it)

def _GetOneNetmaskForAllTheseIPs(ips):
  """Get the one IP network that covers all IPs in input.

  ipaddr.collapse_address_list is a little bit TOO smart and gives you the LIST
  of networks that describe a number of IP addreses. Ceph just wants one
  netmask. This function tries to get that one netmask.

  >>> _GetOneNetmaskForAllTheseIPs(("10.0.0.1", "10.0.0.2",
  ...   "10.0.0.251", "10.0.0.255"))
  10.0.0.0/24
  """

  #Turn each IP address in its binary representation, without 0b header
  num_ip_addresses = [int(ipaddr.IPAddress(ip)) for ip in ips]
  lowest_ip = ipaddr.IPAddress(min(num_ip_addresses))
  bin_ip_addresses = [bin(ip)[2:] for ip in num_ip_addresses]

  #"Transpose" the list (abc),(def) → (ad),(be),(cf)
  bit_comparison = zip(*bin_ip_addresses)

  differing_bits = len(bit_comparison)
  #Find the first different bit
  while _AllSame(bit_comparison[-differing_bits]):
    differing_bits -= 1

  #That's the no. of bits that differ. The mask is the number of bits that DON'T
  mask_length = lowest_ip.max_prefixlen - differing_bits

  #Return the network
  network_ip = ipaddr.IPNetwork("%s/%d" % (lowest_ip, mask_length)).network
  network = ipaddr.IPNetwork("%s/%d" % (network_ip, mask_length), strict = True)
  return str(network)

I tried to be as IP-version agnostic as possible here, but chances are I've overlooked a few more-or-less obvious things here — or, even more likely, there's already a better inbuilt solution somewhere in the python libraries or even ipaddr itself.

You don't have to look at all the IPs to catch 'em all. Just looking at the lowest and highest does the trick. This realisation comes in handy when you consider that ipaddr does have a (private) function that gives you the common prefix length between two IP addresses. The code can then be simplified to:

#with many thanks to gfalcon
def _GetOneNetmaskForAllTheseIPs(ips):
  """Get the one IP network that covers all IPs in input.

  ipaddr.collapse_address_list is a little bit TOO smart and gives you the LIST
  of networks that describe a number of IP addreses. Ceph just wants one
  netmask. This function tries to get that one netmask.

  >>> _GetOneNetmaskForAllTheseIPs(("10.0.0.1", "10.0.0.2",
  ...   "10.0.0.251","10.0.0.255"))
  10.0.0.0/24
  """

  #Look at larger and smaller IP addresses
  ips = [ipaddr.IPAddress(ip) for ip in ips]
  lowest_ip, highest_ip = min(ips), max(ips)

  mask_length = ipaddr._get_prefix_length(
    int(lowest_ip), int(highest_ip), lowest_ip.max_prefixlen)

  #Return the network
  network_ip = ipaddr.IPNetwork("%s/%d" % (lowest_ip, mask_length)).network
  network = ipaddr.IPNetwork("%s/%d" % (network_ip, mask_length), strict = True)
  return str(network)

You still can't use public functions like ipaddr.summarize_address_range, because the library will still painstakingly try to avoid any IP address ever so slightly off range.

>>> ipaddr.summarize_address_range(IPv4Address('10.0.0.1'), IPv4Address('10.0.0.255'))
[IPv4Network('10.0.0.1/32'),
 IPv4Network('10.0.0.2/31'),
 IPv4Network('10.0.0.4/30'),
 IPv4Network('10.0.0.8/29'),
 IPv4Network('10.0.0.16/28'),
 IPv4Network('10.0.0.32/27'),
 IPv4Network('10.0.0.64/26'),
 IPv4Network('10.0.0.128/25')]


Linear shooting method to solve a B.V.P I have wrote a code to approximate the solution of a boundary value problem:

  x'' = p(t)x'(t)+q(t)x(t)+r(t)
  x(b) = beta in [a,b]

by using Runge-Kutta method of order N = 4.

Do you have any idea to make it short? I don't know how to call a subroutine as an argument in another subroutine. I had to copy the rk4 subroutine for each equation of U and V.

program test_linsht
!
! Linear Shooting method
! To approximate the solution of boundary value problem
!           x'' = p(t)x'(t)+q(t)x(t)+r(t)
!'          x(b) = beta in [a,b]
! and using Runge-Kutta method of order N = 4
!
!
!
implicit none
integer,parameter :: n = 2
integer,parameter :: nstep = 20
real(8) :: U(nstep)             ! U contains the solutions at each step
real(8) :: V(nstep),out(nstep)  ! V just like U for another equation
real(8) :: a,b,h,alph,beta,w
real(8) :: x(0:n)
integer :: i
a = 0.d0
b = 4.0
alph = 125.d-2
beta  = -95.d-2
h = (b-a)/nstep
! x = t0 x0 x'0
x = (/0.d0, alph, 0.d0/)

call rks4U(n,h,x,nstep,U)
a = 0.d0
b = 4.0
x = (/0.d0, 0.d0, 1.d0 /)
h = (b-a)/nstep

call rks4V(n,h,x,nstep,V)

! calculate the solution to the boundary value broblem
w = (beta - U(nstep))/V(nstep)
write (*,*) w,U(nstep),V(nstep)
!w = 0.485884
out = U + w * V
do i = 1,nstep
    write(*,100) i,i*h,U(i), w*V(i), out(i)
enddo
100 format (1x,I5,f10.2,f15.6,f15.6,f15.6)
end program

subroutine xprsysU(n,x,f)
! x prime of system of equations

    real(8), dimension(0:n) :: x,f
    integer :: n
    ! time is introduced as a new differential equation
    f(0) = 1.d0
    f(1) = x(2)
    f(2) = 2.*x(0)/(1+x(0)*x(0))*x(2)- 2./(1.+x(0)*x(0))*x(1) + 1.0
end subroutine

subroutine xprsysV(n,x,f)
! x prime of system of equations

    real(8), dimension(0:n) :: x,f
    integer :: n
    ! time is introduced as a new differential equation
    f(0) = 1.d0
    f(1) = x(2)
    f(2) = 2.*x(0)/(1+x(0)*x(0))*x(2)- 2./(1.+x(0)*x(0))*x(1)
end subroutine

subroutine rks4U(n,h,x,nstep,xout)

implicit none
      real(8) :: x(0:n)
      real(8) :: y(0:n), f(0:n,4)
      real(8) :: xout(nstep)
      integer :: i,k,n,nstep
      real(8) :: h
      !write(*,200) "k","t","x","y"
      !write(*,100) 0,x
      f = 0.
out:  do k = 1,nstep
          call xprsysU(n,x,f(0,1))
in1:      do i = 0,n
              y(i) = x(i) + 0.5*h*f(i,1)
              !print *, f(i,1)
          end do in1
          call xprsysU(n,y,f(0:n,2))
in2:      do i = 0,n
              y(i) = x(i) + 0.5*h*f(i,2)
          end do in2
          call xprsysU(n,y,f(0:n,3))
in3:      do i = 0,n
              y(i) = x(i) + h*f(i,3)
          end do in3
          call xprsysU(n,y,f(0:n,4))
in4:      do i = 0,n
              x(i) = x(i) + (h/6.0)* (f(i,1) + 2.0*(f(i,2) + f(i,3)) + f(i,4))
          end do in4
          xout(k) = x(1)
      end do out
      !100 format (1x,I5,f10.2,f15.8,f15.8)
      !200 format (1x,A4,2A10,A16)
end subroutine rks4U

subroutine rks4V(n,h,x,nstep,xout)

implicit none
      real(8) :: x(0:n)
      real(8) :: y(0:n), f(0:n,4)
      real(8) :: xout(nstep)
      integer :: i,k,n,nstep
      real(8) :: h
      !write(*,200) "k","t","x","y"
      !write(*,100) 0,x
      f = 0.
out:  do k = 1,nstep
          call xprsysV(n,x,f(0,1))
in1:      do i = 0,n
              y(i) = x(i) + 0.5*h*f(i,1)
              !print *, f(i,1)
          end do in1
          call xprsysV(n,y,f(0:n,2))
in2:      do i = 0,n
              y(i) = x(i) + 0.5*h*f(i,2)
          end do in2
          call xprsysV(n,y,f(0:n,3))
in3:      do i = 0,n
              y(i) = x(i) + h*f(i,3)
          end do in3
          call xprsysV(n,y,f(0:n,4))
in4:      do i = 0,n
              x(i) = x(i) + (h/6.0)* (f(i,1) + 2.0*(f(i,2) + f(i,3)) + f(i,4))
          end do in4
          xout(k) = x(1)
      end do out
      !100 format (1x,I5,f10.2,f15.8,f15.8)
      !200 format (1x,A4,2A10,A16)
end subroutine rks4V

To pass a function or subroutine to another, you need to declare it with an interface block. The compiler also needs to be aware of the function/subroutine you are calling, which means either using a module to hold the RK4 subroutines or, with small enough code, a contains block.

I'm going to go with the latter since it's easier here due to code size, but the strategy really isn't that different with using a module. I'm also going to snip out most of the code, as I don't think much is needed to show how to do it.

program test_linsht
   implicit none
   ...
   call rk4(n, h, x, nstep, xprsysU, U)
   call rk4(n, h, x, nstep, xprsysV, V)
   ...
contains

subroutine xprsysU(n,x,f)
! x prime of system of equations
   real(8), dimension(0:n) :: x,f
   integer :: n
   ! time is introduced as a new differential equation
   f(0) = 1.d0
   f(1) = x(2)
   f(2) = 2.*x(0)/(1+x(0)*x(0))*x(2)- 2./(1.+x(0)*x(0))*x(1) + 1.0
end subroutine

subroutine rk4(n, h, x, nstep, sub, xout)
   real(8) :: x(0:n)
   real(8) :: y(0:n), f(0:n,4)
   interface
      subroutine sub(n, x, f)
         real(8), dimension(0:n) :: x,f
         integer :: n
      end subroutine sub
   end interface
   ...
   do k=1,nstep
      call sub(n, x, f)
   end do
   ...
end subroutine
end program test_linsht

Note that the interface block has the same structure as the declaration part of the subroutine, so it should be obvious that it is necessary for the inputs of the different functions to be the same, otherwise we'd have a compiler error.

Other odds and ends:

Fortran is 1-indexed, so it's more natural in the language to use dimension(1:n) (or even dimension(n), which is the same thing as the other), instead of defining it as dimension(0:n). Obviously it can handle an index of 0, but it's just not typical of Fortran programs.
I don't think the labels in# and out on the do loops are needed in this case. Typically, I'd only recommend them for the cases where an inner loop requires you to increment the outer loop, but that doesn't happen here, it's just clutter.
It's possibly due to copy-and-paste, but indentation matters for reading purposes. You've got some parts indented and others not, some indented further than others.
Fortran allows array math, use it. You can turn those do loops in the RK4 routine into y(:) = x(:) + h*f(:,1) etc.
It is not generally recommended to use real(8) syntax, it's possibly not what you think it is. The Fortran 90 standard introduced kind notation to give you portable definition of arbitrary precision numbers.
With a contains statement, the parameters are global, so you would not need to pass them to the subroutines. With a module, you would have to declare those parameters in the module as global variables.
I'd recommend declaring variables as intent(in) and intent(out) whenever and wherever possible, as it helps keep you straight with regards to variables usage (and possibly help optimize the code).


Hashing passwords for a website I have spent about 2 weeks reading about hashing passwords and website security. As there seems to be many different ways to achieve this, I'm a bit confused as to whether my code is secure.

Can anyone please have a look through and let me know what they think and what needs to be changed?

I have not added any error trapping yet, as to allow me to concentrate on just the hashing.

The steps I have took are as follows:

Create random salt
Add random salt and email together to create salt for password (email will be encrypted in database)
Hash password and salt and store in database

public const int HashBytes = 128;
public const int DefaultIterations = 10000;

    //Create random bytes for salt
    public static string SaltSHA256()
    {
        const int minSaltSize = 8;
        const int maxSaltSize = 16;
        var random = new Random();
        int saltSize = random.Next(minSaltSize, maxSaltSize);
        byte[] saltBytes = new byte[saltSize];
        var rng = new RNGCryptoServiceProvider();
        rng.GetNonZeroBytes(saltBytes);
        HashAlgorithm hash = new SHA256Managed();
        byte[] bytes = hash.ComputeHash(saltBytes);
        return Convert.ToBase64String(bytes);
    }

    //Create salt using email and public static string SaltSHA256()
    //Store email and public static string SaltSHA256() in database
    public static string SaltRfc2898(string email,string hashedSalt)
    {
        var salt = new Rfc2898DeriveBytes(email, Encoding.UTF8.GetBytes(hashedSalt), DefaultIterations);
        return Convert.ToBase64String(salt.GetBytes(HashBytes));
    }

    //Hash password and salt
    public static string PasswordHashRfc2898(string password,string salt)
    {
        var hashedPassword = new Rfc2898DeriveBytes(password, Encoding.UTF8.GetBytes(salt), DefaultIterations);
        return Convert.ToBase64String(hashedPassword.GetBytes(HashBytes));
    }
    //Get salt and password from database based on username
    //Salt in from data created by public static string SaltSHA256()

    public static bool DoPasswordsMatch(string password,string salt)
    {
        //Password would be pulled from db based on username
        byte[] testPassword = Convert.FromBase64String("basestring");

        //Salt would be pulled from database based on username
        var saltFromDatabase = salt;

        //Hash password and salt
        var hashUserInputAndSalt = PasswordHashRfc2898(password, saltFromDatabase);

        //Convert to byte[] ready for comparison
        byte[] convertUserInputFromBase64 = Convert.FromBase64String(hashUserInputAndSalt);

        //Compare and return true or false
        return convertUserInputFromBase64.SequenceEqual(testPassword);

    }

As CodesInChaos pointed out in the comments, a far more secure way to hash passwords is to use a deliberately expensive hash. This will all but eliminate any hope of a successful brute-force attack.

The "best" algorithm I know of for this purpose would be BCrypt. For .NET, you can use BCrypt.Net. Disclaimer: I don't know who, if anyone, has verified the integrity of this particular port.

See this StackOverflow question for a full discussion regarding the use of BCrypt as a password hashing algorithm.

Original answer

So long as the salt is sufficiently unpredictable, the hashing function sufficiently secure, and the user's password is never stored in plain-text, emailed, or logged, then your implementation should be adequate.

While your salt is unpredictable, 8 bytes may be short for extremely sensitive information. A salt is stored in plain-text along with the hashed password, so we're not worried about keeping it a secret. What we're worried about is that someone may have already pre-computed SHA-256 hashes for common passwords and salts up to 8 bytes salt (though unlikely). Having a random length salt really doesn't add much except computational complexity and potentially wasted storage space. I would settle for a consistent-width salt of 16 bytes.

SHA-256 is a suitable hashing algorithm for most purposes at this time.
Edit: But BCrypt is better for passwords (see above).


Fastest sum of absolute values of 32 differences A long should be treated as a list of 32 unsigned numbers, each of them just two bit long. So 0x1234F... represents

{0, 1, 0, 2, 0, 3, 1, 0, 3, 3, ...}

and 0x55AA0... represents

{1, 1, 1, 1, 2, 2, 2, 2, 0, 0, ...}

Given two such lists, I need to compute the absolute values of the pairwise differences and sum them up. To continue the example, the difference list would be

{-1, 0, -1, 1, -2, 1, -1, -2, 3, 3, ...}

Now just drop the sign and sum it up. What I did is

static int funnySum(long x, long y) {
    int result = 0;
    for (int i=0; i<32; ++i) {
        int xNum = (int) (x & 3);
        int yNum = (int) (y & 3);
        result += Math.abs(xNum - yNum);

        x >>= 2;
        y >>= 2;
    }
    return result;
}

It's the taxicab-distance computing algorithm used in this question of mine. It occurred to me that it can be done without any loop, however I haven't figured the details out yet.

We can try to optimize the subtraction by looking at the result table and finding a bit level hack that gives us the right result after which a modified bitcount will produce the result.

The table when viewed for each bit pair is:

        00 01 10 11
        0  1  2  3

00 0    0  1  2  3
01 1    1  0  1  2
10 2    2  1  0  1
11 3    3  2  1  0

a^b is almost the right result, only for a=1 and b=2 does this give the wrong result (3 instead of 1).

So that need to be detected and dealt with.

That means that if a&b == 0 and a^b == 3 and both a and b are not 0 then the result should be 1 which we can do by xoring the high bit of the result.

long result = a^b;
long is3 = result & result << 1; //high bit per pair will contain whether the pair is 3
is3 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long is0 = a&b;
is0 = ~(is0 | is0 << 1);//high bit per pair will contain whether the pair is 0
is0 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long notBoth0 = (a|a<<1) & (b|b<<1);
notBoth0 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
result ^= is3 & is0 & notBoth0; // only invert the bits set in is3, is0 and notBoth0

The other selection possibility is when the bits in a are not equal:

long result = a^b;
long is3 = result & result << 1; //high bit per pair will contain whether the pair is 3
is3 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long isEq = a^(a<<1);
isEq &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
result ^= is3 & isEq0; // only invert the bits set in is3 and isEq0

The modified bitcount would be something like:

result = (result & 0x3333_3333_3333_3333l) + ((result >>  2) & 0x3333_3333_3333_3333l);
result = (result & 0x0f0f_0f0f_0f0f_0f0fl) + ((result >>  4) & 0x0f0f_0f0f_0f0f_0f0fl);
result = (result & 0x00ff_00ff_00ff_00ffl) + ((result >>  8) & 0x00ff_00ff_00ff_00ffl);
result = (result & 0x0000_ffff_0000_ffffl) + ((result >> 16) & 0x0000_ffff_0000_ffffl);
result = (result & 0x0000_0000_ffff_ffffl) + ((result >> 32) & 0x0000_0000_ffff_ffffl);

note: I use underscores in the hexadecimal literals to make it clearer (they are legal in java 7 I believe) however in java 6 you will need to remove them.


Processing keyboard input for player movement in a game The following code is part of a game I am making using the Phaser framework; the game is in the style of a top-down RPG, with the player moving their character in four possible directions using the arrow keys. This code appears in my update() method.

I like the user experience provided by this code a lot: the character moves on the screen exactly how I intend. However, I can't help but notice that there's a lot of repetition here and I'd like to explore ways of writing this more efficiently and avoiding repetition. I have already investigated case statements vs if/else statements and have found that a lot of repetition still occurs. I tend to encounter these same repetition issues whenever I need to process keyboard input, regardless of the programming language.

NB. I've come across this Code Review question which seems to be close to what I am looking for, but haven't been able to successfully apply the concept to my own project (ie. my version of that code isn't 'working', so isn't appropriate for Code Review).

   if(!this.inputBlocked) {
        if(this.cursors.left.isDown) {
            this.playerInputDirection = 'W';
            this.player.body.velocity.x = -this.PLAYER_SPEED;
        }
        if(this.cursors.right.isDown) {
            this.playerInputDirection = 'E';
            this.player.body.velocity.x = this.PLAYER_SPEED;
        }
        if(this.cursors.up.isDown) {
            this.playerInputDirection = 'N';
            this.player.body.velocity.y = -this.PLAYER_SPEED;
        }
        if(this.cursors.down.isDown) {
            this.playerInputDirection = 'S';
            this.player.body.velocity.y = this.PLAYER_SPEED;
        }
    }

    //control player walking animation
    if(this.player.body.velocity.x != 0 || this.player.body.velocity.y != 0) {
        // check for direction, play appropriate animation
        if (this.playerInputDirection == 'W'){
            this.player.play('walkLeft');
        }
        if (this.playerInputDirection == 'E'){
            this.player.play('walkRight');
        }
        if (this.playerInputDirection == 'N'){
            this.player.play('walkUp');
        }
        if (this.playerInputDirection == 'S'){
            this.player.play('walkDown');
        }
    } else {
    // stop all animation
        this.player.animations.stop();

    // determine the correct sprite frame,
    // so player stops while facing appropriate direction
        if (this.playerInputDirection == 'W'){
            this.player.frame = 4;
        }
        if (this.playerInputDirection == 'E'){
            this.player.frame = 12;
        }
        if (this.playerInputDirection == 'N'){
            this.player.frame = 8;
        }
        if (this.playerInputDirection == 'S'){
            this.player.frame = 0;
        }
    }

Assuming you've used an associative array as discussed, you'll have some sort of walkingData object containing the velocity and animation information for each direction, keyed by the same keys as the Phaser cursors object (left/right/up/down).

In an event-driven system, you would go directly from the key that was pressed to the relevant data, however since you're doing this in Phaser's main loop, you need to list the keys you're checking (which is what your if statements are doing). The dry way of doing this is to loop over walkingData:

for (var direction in walkingData) {
    var directionData = walkingData[direction];
    // update player velocity etc. using direction data
}

The slight wrinkle here is that you also need to update the animations, which happens outside your inputBlocked conditional (and depends on the velocities set).

To get around this, you'll also need to declare an animationDirection variable outside the loop and store which direction to use for animation, then use that data in your second if to set the animations.

The end result will be along the lines of:

var walkingData = {
    left: { /* velocity and animation info */ },
    ...
};

var animationData;
if (!this.inputBlocked) {
    for (var direction in walkingData) {
        if (this.cursors[direction].isDown) {
            var directionData = walkingData[direction];
            /* configure velocities */
            animationData = directionData;
        }
    }
}

//control player walking animation
if (this.player.body.velocity.x || this.player.body.velocity.y) {
    // check for direction, play appropriate animation
    this.player.play(animationData.animation);
} else {
    // stop all animation
    this.player.animations.stop();

    // determine the correct sprite frame,
    // so player stops while facing appropriate direction
    this.player.frame = animationData.stopFrame;
}

(I've removed the != 0 since it is equivalent, assuming velocity.x/velocity.y are defined.)


Sampling to collect data I am working on some sampling to collect data for my research on SOLID Principles. One of my sample consists proceeding code snippet:

public abstract class Notify
{
    public abstract void NotifyClient();
}

public class OnPremisesClient : Notify
{
    public override void NotifyClient()
    {
        Console.WriteLine("You're getting these notifications because you opted....");
    }
}

public class CloudClient : Notify
{
    public override void NotifyClient()
    {
        Console.WriteLine("You're getting these notifications because you opted....");

        if (IsOnPremisesToo)
            NotifyClientAsOnPremisesClient();
    }

    public void NotifyClientAsOnPremisesClient()
    {
        Console.WriteLine("Awesome! You are also using On premises services...");
    }

    public bool IsOnPremisesToo { get; set; }
}

Calling class is:

public  class Program
    {
         public static void Main(string[] args)
          {
              var premisesClient = new OnPremisesClient();
              var cloudClient = new CloudClient();

              ProcessNotifications(new List<Notify> { premisesClient, cloudClient });
          }

          private static void ProcessNotifications(List<Notify> list)
          {
               HandleItems(list);
          }

          static void HandleItems(IEnumerable<Notify> notifications)
          {
              foreach (var notification in notifications)
              {
                 if (notification is CloudClient)
                 {
                     var cloudClient = notification as CloudClient;
                     cloudClient.IsOnPremisesToo = true;
                 }
                 notification.NotifyClient();
              }
          }
    }

In the preceding code snippet, I am trying to notify the client as per the type of Notify client could be a OnPremisesClient or CloudClient.

This code-snippet looks neat and clean, but I would like to discuss which SOLID principle it violates. After going through few SOLID resources, I thought it violates SRP as it uses if. In the future, if there will be new client like GalaxyClient, then this code need a new condition. There might be more violations.

Are SOLID principles really violate in the give code-snippet or just I am thinking it violates SOLID? I would appreciate it if someone tells the which principles are violating with reasoning. What would be the new code or what are changes should made to this code so, it'd follow SOLID Principles?

The code in example is violating following principles:

Single Responsibility Principle(SRP):
The responsibility of Notifying is spread thin across Clients and the classes are not clear with their intentions and it is also not reflecting through the behaviours. Now, it is not clear whether the client is also supposed to do other jobs.
Liscov Substitute Principle(LSP):
'Is-A' Relationship should be replaced with 'Is-Substitue-for' relationship. notification is CloudClient is violating LSP.
Dependency Inversion Principle(DIP): is violated since program class is dependent on client implementations and Notify class.

IMO, code can be restructured as follows. Please note, it can be also improved with better DI Implementation. By judging the code listing, I am not clear what is intended output of this program. Whether it is sending two different notifications or three notifications. Still,trying to provide the answer as per my understanding and assumptions below. Please let me know in comments the intent of the program so that I can modify the program as per the intent.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeSmellQuestion
{
    public class Notification
    {
        private readonly List<INotify> _providerList;
        public Notification(List<INotify> providerList)
        {
            _providerList = providerList;
        }

        public void SendAll()
        {
            foreach (var notificationProvider in _providerList)
            {
                notificationProvider.Notify();
            }
        }
    }

    public interface INotify
    {
        void Notify();
    }

    public class OnPremiseNotifier : INotify
    {
        public void Notify()
        {
            Console.WriteLine("You're getting these notifications because you opted for OnPremise Notifications....");
        }

    }

    public class CloudNotifier : INotify
    {
        public void Notify()
        {
            Console.WriteLine("You're getting these notifications because you opted for Cloud Notifications....");
         }
    }
}


Implementing timeout of a resource (in this case a database connection) I am currently having a problem with too many database connections. Therefore, I am trying to implement a database connection timeout. In the code below the changing of value of the shared resource will be replaced with connecting and disconnecting to the database. I am new to programming with threads and I kindly wonder if I have made any logical errors or if there are any better approaches to this problem? There is no built-in timeout in OCCI which I use.

#include <thread>
#include <chrono>
#include <iostream>
#include <mutex>
#include <atomic>

namespace chrono = std::chrono;

class scoped_thread{
  std::thread t;
public:
  explicit scoped_thread(std::thread t_): t(std::move(t_)){
    if ( !t.joinable()) throw std::logic_error("No thread");
  }
  ~scoped_thread(){
    t.join();
    std::cout << "Thread " << std::this_thread::get_id() << " joined.\n";
  }
  scoped_thread(scoped_thread&)= delete;
  scoped_thread& operator=(scoped_thread const &)= delete;
};

template<typename T>
class LockWrapper {
    T* t;
    std::mutex mut;

public:
    class Proxy {
        T* t;
        std::unique_lock<std::mutex> lock;
        Proxy(LockWrapper& wr) : t(wr.t), lock(wr.mut) { }
        friend LockWrapper;
    public:
        T& operator*() { return *t; }
        T* operator->() { return t; }
    };
    LockWrapper(T* t) : t(t) {}

    Proxy aquire() { return {*this}; }
};

using clock_type = chrono::system_clock;
using shared_deadline = std::atomic<clock_type::time_point>;
constexpr auto tlim=100;
template<typename T> void timeout(T& shared_resource,const shared_deadline& deadline) {
    while(clock_type::now()<deadline.load())
    {
        constexpr auto sleeping_time=1;
        std::cout << "Sleeping for another  " << 1 << " seconds\n";
        std::this_thread::sleep_until(clock_type::now()+chrono::seconds(1));
    }
    *shared_resource.aquire()=0; // will replace by database disconnect
    std::cout << "Setting resource to " << (*shared_resource.aquire()) << " after timeout occurred in thread " << std::this_thread::get_id() << ".\n";
}
int main()
{
    int int_value=1;
    LockWrapper<int> shared_resource(&int_value);
    constexpr auto timeout_length=10;
    auto get_new_deadline=[timeout_length](){return clock_type::now()+chrono::seconds(timeout_length);};
    shared_deadline deadline(get_new_deadline());
    auto th = std::make_unique<scoped_thread>(std::thread(timeout<LockWrapper<int>>, std::ref(shared_resource),std::cref(deadline)));
    constexpr int sleeping_time=20;
    for(auto t=0;t<tlim;t+=sleeping_time) // This loop simulates repeated database access
    {
        std::cout << "Slept for " << t << " seconds. Sleeping for another " << sleeping_time << " seconds\n";
        std::this_thread::sleep_for(chrono::seconds(sleeping_time));
        if((*shared_resource.aquire())==0)
        {
            *shared_resource.aquire()=1; // will replace by database connect
            std::cout << "Setting resource to " << (*shared_resource.aquire()) << "\n";
            deadline=get_new_deadline();
            th = std::make_unique<scoped_thread>(std::thread(timeout<LockWrapper<int>>, std::ref(shared_resource),std::cref(deadline)));
        }
        else
        {
            deadline=get_new_deadline();
        }
    }
}

Code

Acquire not aquire.
The scoped_thread move constructor is missing a &, and should have the signature scoped_thread(scoped_thread&&) = delete.
system_clock is the wrong clock type to use, as it's not monotonic (the user can adjust it whenever they choose). steady_clock would probably be the right choice here.
Since scoped_thread stores the thread object as a member, the scoped_thread constructor could use variable template arguments and perfect forwarding, rather than passing in a std::thread object. This makes the user code slightly shorter.
When declaring time constants (tlim, sleeping_time), it would be better to use std::chrono types at the point of declaration, rather than later on in the code, so that the constant has units associated with it directly.
(Style/Opinion:) Vertical spacing makes code easier to read:

using clock_type = chrono::system_clock;
using shared_deadline = std::atomic<clock_type::time_point>;

constexpr auto tlim=100;

template<typename T> void timeout(T& shared_resource,const shared_deadline& deadline)

With a little extra spacing, it's a lot easier to parse this visually as two using declarations, a constant and the start of a function.

Design - locking

There are a couple of places where the resource is locked and then unlocked again rapidly, e.g.:

    if((*shared_resource.aquire())==0)
    {
        *shared_resource.aquire()=1; // will replace by database connect
        std::cout << "Setting resource to " << (*shared_resource.aquire()) << "\n";

Maintaining the lock would be better, otherwise what's printed to std::cout may not be what you expect:

    auto proxy = shared_resource.aquire();

    if (*proxy == 0)
    {
        *proxy = 1; // will replace by database connect
        std::cout << "Setting resource to " << *proxy << "\n";

Design - cancelling / timeout behaviour

If you comment out every line after creating the timeout object:

auto th = std::make_unique<scoped_thread>(std::thread(timeout<LockWrapper<int>>, std::ref(shared_resource), std::cref(deadline)));

main() won't complete until the timeout finishes. This is probably not desirable behaviour.
There is no way to cancel the timeout without manually setting a deadline zero seconds in the future (i.e. dodgy hacks). Furthermore, the fixed sleep of 1 second inside timeout() means you may have to wait up to a second anyway.
Sleeping for one second in a loop seems like strange behaviour, since we know exactly how long we actually need to sleep for before waking up.
It is error-prone to manually increase the deadline every time an operation that requires the connection is used.

Changes

Some of the problems above can be solved by encapsulating the timeout functionality in a class, and using a std::condition_variable to do the timed waiting. This also allows the callback to be cancelled (or called immediately) if desired.

class ThreadedCallback
{
public:

    using clock_t = chrono::steady_clock;
    using duration_t = clock_t::duration;
    using action_t = std::function<void()>;

    ThreadedCallback(duration_t timeout, action_t const& action)
    {
        start(timeout, action);
    }

    ~ThreadedCallback()
    {
        cancel();
    }

    ThreadedCallback(ThreadedCallback&&) = delete;
    ThreadedCallback(ThreadedCallback const&) = delete;

    void restart(duration_t timeout, action_t const& action)
    {
        cancel();

        start(timeout, action);
    }

    void cancel()
    {
        {
            std::lock_guard<std::mutex> lock(m_mutex);

            if (!m_cancelled)
            {
                m_cancelled = true;
                m_cv.notify_one();
            }
        }

        assert(m_thread.joinable());
        m_thread.join();
    }

private:

    void start(duration_t timeout, action_t const& action)
    {
        assert(!m_thread.joinable());
        m_thread = std::thread([=] () { run(timeout, action); });
    }

    void run(duration_t timeout, action_t const& action)
    {
        std::unique_lock<std::mutex> lock(m_mutex);

        m_cancelled = false;
        m_cv.wait_for(lock, timeout, [&] () { return m_cancelled; });

        // note: this check can be removed (and cancel() renamed to call_now())
        // or a boolean flag added to cancel() to indicate whether the action should still be called anyway
        if (!m_cancelled)
            action();
    }

    std::thread m_thread;
    std::mutex m_mutex;
    std::condition_variable m_cv;
    bool m_cancelled;
};

int main()
{
    int int_value = 1;
    LockWrapper<int> shared_resource(&int_value);

    auto disconnect = [&] ()
    {
        auto proxy = shared_resource.acquire();
        *proxy = 0; // will replace by database disconnect
        std::cout << "Setting resource to " << *proxy << " after timeout occurred in thread " << std::this_thread::get_id() << ".\n";
    };

    auto timeout = std::chrono::seconds(5);
    ThreadedCallback callback(timeout, disconnect);

    constexpr auto tlim = std::chrono::seconds(50);
    constexpr auto sleeping_time = std::chrono::seconds(2);
    for (auto t = std::chrono::seconds(0); t < tlim; t += sleeping_time) // This loop simulates repeated database access
    {
        std::cout << "Slept for " << t.count() << " seconds. Sleeping for another " << sleeping_time.count() << " seconds\n";
        std::this_thread::sleep_for(sleeping_time);

        auto proxy = shared_resource.acquire();

        if (*proxy == 0)
        {
            *proxy = 1; // will replace by database connect
            std::cout << "Setting resource to " << *proxy << "\n";

            callback.restart(timeout, disconnect);
        }
        else
        {
            callback.restart(timeout, disconnect);
        }
    }

    std::cout << "done!" << std::endl;
}

This still doesn't solve the issue of manually restarting the timer with every access operation. Perhaps a timeout class like this would be better kept in the resource (or LockWrapper) itself.

For example, since we want the time after the last access, the Proxy class destructor could start the timeout (e.g. call a function in the LockWrapper to create a ThreadedCallback in a unique_pointer), and the Proxy constructor could call a function to clear that pointer (cancelling the disconnect operation).

Then the timeout would be directly tied to the access itself, and not have to be reset manually by user code.


Choose random instants in a day with a low memory footprint I'm looking for a way to plan a list of X events at the start of the day...
What I did before:
At 02:00 every day, choose X timestamps from "now" to 01:59 the next day.
That worked well but I had to "remember" X timestamps
What I did to optimize:
Each day, create a counter events_planned = X
Each second, in the loop, make the event if random(0, seconds_left_before_0200) <= events_planned
If the event was made, remove 1 from events_planned
It seems to be working well, but when you graph the number of events in a day, you get

As you can see, each time we approch 02:00, more events are created (And that's not a single occurence)
Minimal exemple:
import time
import random

def planifie():
    now = int(time.time())
    this_day = now - (now % 86400)
    seconds_left = 86400 - (now - this_day)
    multiplicator = round(seconds_left / 86400, 5) # In case we restarted, and it's not 02:00. That's not used in the graph before
    return round(getPref("events_per_day") * multiplicator)

def mainloop():
    planday = 0
    is_closed = False
    while not is_closed:
        now = int(time.time())
        this_day = now - (now % 86400)
        seconds_left = int(86400 - (now - this_day))
        if int(now / 86400) != planday:
            planday = int(now / 86400)
            events_planned = planifie()

        if random.randrange(0, seconds_left) < events_planned:
            events_planned -= 1
            do_event()
        time.sleep(1)

def do_event(): #Dummy def for do_event()
     print("Ping")

def getPref(_): # Dummy def for getpref, as it is only used in planifie(). We will assume 20 000 events a day
     return 20000
mainloop()

(The code is much more complicated than that, so if you might need it in full, here is planifie() and here is mainloop())

1. Review

There's a lot of repetition, especially of the number 86400. This can be avoided by defining a global constant, for example:

_DAY_SECONDS = 24 * 60 * 60  # Seconds in a day.

or alternatively:

import datetime
_DAY_SECONDS = datetime.timedelta(1).total_seconds()

and then in mainloop:

day, partday = divmod(int(time.time()), _DAY_SECONDS)
seconds_left = _DAY_SECONDS - partday
if day != planday:
    planday = day
    events_planned = round(getPref('events_per_day') * seconds_left
                           / _DAY_SECONDS)

(This avoids the need for the function planifie.)
If time.time happens to return a number less than 86,400 (perhaps because the computer's clock has not been set correctly) then events_planned will not get set on the first loop. It's better to ensure that the initial value of planday can never equal day, for example by initializing planday to None.

2. The problem

The chance of emitting an event on each loop is events_planned / seconds_left. This would be correct if there each loop iteration took exactly one second. But that's not the case — each loop iteration takes more than a second. That's because (i) some time is taken by do_event (on the iterations where there is an event); (ii) sleep(1) generally takes a little more than 1 second because of the granularity of operating system scheduler, and (iii) as it says in the specification of the sleep function,

  The suspension time may be longer than requested due to the scheduling of other activity by the system.

So each loop takes more than a second, but emits events based on the probability of an event occurring in a period of exactly one second. So there is a small but systematic deficit in the number of emitted events, leading to a rush to catch up at the end.

To have a fair schedule, you need to measure the time actually taken by each iteration of the loop, and adjust the probability accordingly, something like this:

planday = None
prev = time.time()
while not is_closed:
    now = time.time()
    time_passed = now - prev
    day, partday = divmod(now, _DAY_SECONDS)
    seconds_left = _DAY_SECONDS - partday
    if day != planday:
        planday = day
        events_planned = round(getPref('events_per_day') * seconds_left
                               / _DAY_SECONDS)
    if random.random() < events_planned * time_passed / seconds_left:
        events_planned -= 1
        do_event()
    time.sleep(1)

(Note that this doesn't actually ensure that the exact number of events occur in each day — an unlucky scheduling of the last sleep of the day could cause some events to be dropped. But the code in the post has the same problem, and I'm guessing that you don't mind if the number of events per day is short by one or two.)

3. Worked example

You expressed some skepticism about this in the comments, so let's take a simple worked example. Suppose we start out with \$20\$ seconds remaining and \$10\$ events remaining. Then there should be on average one event every 2 seconds. But let's also suppose that the sleep(1) actually takes 2 seconds.

On the first iteration we emit an event with probability \$1\over 2\$, and so after 2 seconds we have emitted on average \$1\over 2\$ an event, so we are 0.5 events behind schedule.

On the second iteration we emit an event with probability \$1\over2\$ if we emitted an event in the first iteration, or \$5\over9\$ if we didn't. So after two iterations we have emitted on average $$ {1\over2}\left(1 + {1\over2}\right) + {1\over2}{5\over9} = {37 \over 36} $$ events, and so we are on average almost 1 event behind schedule.

You can see that in this example, the deficit goes up to start with because although the probability goes up, it doesn't go up fast enough to compensate. Towards the end, the probability catches up, hence the rush to finish.

4. Alternative approach

If the number of events is substantially less than the number of seconds in a day, then most of the loop iterations will be pointless — no event happens and the program just goes to sleep again.

An alternative approach is to emit exactly one event in each loop, and then choose how long to sleep until the next event. If events are distributed uniformly at random, then the time to the next event is given by the exponential distribution and this can be sampled by calling random.expovariate.

(The same problem with over-sleeping will arise here, so you would have to compensate for it, for example by measuring the actual time taken by the loop iteration, subtracting the intended iteration time, and holding over any surplus and subtracting it from the time for the next iteration.)


Counting number of 'if' statements in SAS I am writing a C# script to count all the 'if...then' statements present in 4000 lines of SAS code. I am taking the SAS code as a text file and then performing my operation. Here's my C# code:

class Program
{

static void Main(string[] args)
{

    List<String> list = new List<string>();
    list = File.ReadAllLines(@"C:\Users\Dey\Documents\Trucks\file.doc").ToList();
    int count = CountIfs(list);
    Console.ReadKey();
}

static int CountIfs(List<String> list)
{
    int count = 0;
    var index = new List<int>();
    var value = new List<String>();

    for (int i = 0; i < list.Count; i++)
    {
        if (list[i].Contains("if"))
        {
            if (list[i].Contains("then") || list[i + 1].Contains("then"))
            {
                count++;
                index.Add(i);
                String temp = null;

                if(list[i].Contains(";"))
                temp = list[i].Substring(0, list[i].IndexOf(";"));

                if (temp != null)
                {
                    value.Add(temp);
                }
            }

        }
    }
    return count;
}
}

I'm essentially checking for "if" per line and if that is found, i'm checking for "then". And finally I'm also making sure its one line of code by checking for ";" . My logic is that if all these conditions satisfy, then I am indeed able to extract all the if-statements from the code. The list "value" would contain all the "if" statements found in the code. Now I've output "value" to a textfile in notepad and have manually cross-checked about 20 entries. And so far it seems to be working alright. I was hoping someone can proof-read my code and tell me if I can improve it somewhere perhaps? Or is this logic sufficiently accurate?

The code in question has some flaws which I will address here:

var index = new List<int>(); isn't really used and should be removed
var value = new List<String>(); isn't really used and should be removed
The method parameter List<String> list isn't used as a List<T> but rather like an array hence it should be an array.

Fixing these points leads to
private static int CountIfs(string[] linesOfCode)
{
    var count = 0;

    for (int i = 0; i < linesOfCode.Length; i++)
    {
        var line = linesOfCode[i];
        if (line.Contains("if"))
        {
            if (line.Contains("then") || line[i + 1].Contains("then"))
            {
                count++;
            }
        }
    }
    return count;
}

Now the code looks much cleaner and smaller.

An if will always be the first statement in a line of code after removing any leading whitespace and will have a trailing whitespace. Using Contains() can lead to many false positives. Assume a line of code contains the following text:
"I received the tif-file of this invoice from my partner in athen."

A then will always have a leading whitespace and either have a trailing whitespace or will be the first part of a line of code after removing leading whitespace.

Like mentioned in @Paparazzi's answer you could run into an IndexOutOfRangeException by accessing list[i + 1].

Let us introduce a new method which just handles the check for the if statement.
private static bool HasIfStatement(string line)
{
    return line.Trim().StartsWith("if ");
}

No we need a method to check for a then.
private static string[] spaceArray = new string[] { " " };
private static bool HasThenStatement(string line)
{
    return line.Split(spaceArray , StringSplitOptions.RemoveEmptyEntries).Any(w => w == "then");
}

Well this method is some kind of quick & dirty because it will create a lot of strings. I will leave it to you to make it better.
By adding a flag for the case that the line had an if and doesn't had an then we can't get an IndexOutOfRangeException anymore. As a sideeffect we could now use a foreach loop and have an IEnumerable<string> as the methods parameter type.
Putting all together could look like so
private static int CountIfs(IEnumerable<string> linesOfCode)
{
    var count = 0;
    var lastLineHadIf = false;
    foreach (var line in linesOfCode)
    {
        if (lastLineHadIf)
        {
            lastLineHadIf = false;
            if (HasThenStatement(line))
            {
                count++;
            }
        }
        else if (HasIfStatement(line))
        {
            if (HasThenStatement(line))
            {
                count++;
            }
            else
            {
                lastLineHadIf = true;
            }
        }
    }
    return count;
}

private static bool HasIfStatement(string line)
{
    return line.Trim().StartsWith("if ");
}

private static string[] spaceArray = new string[] { " " };
private static bool HasThenStatement(string line)
{
    return line.Split(spaceArray , StringSplitOptions.RemoveEmptyEntries).Any(w => w == "then");
}

I don't know about case-sensitivity of if and then so you may adjust the code to take this into account.
This code doesn't take comments into account, so you should adjust the code for comments as well.


Safety of contact form I have made slight edits to a simple PHP contact form that I have found online. Can you see anything else that I could do to ensure that I am protected from email injections and spam? I have used trim, stripslashes and htmlspecialchars and made a simple question to act as spam prevention.

<?php

$myemail = "YOUR EMAIL ADDRESS";

$name = check_input($_POST['name'], "Enter your name");
$email = check_input($_POST['email']);
$message = check_input($_POST['message'], "Write your message");
$captcha = check_input($_POST['captcha']);

if (!preg_match("/([\w\-]+\@[\w\-]+\.[\w\-]+)/", $email))
{
show_error("E-mail address not valid");
}

if (!preg_match("/5/", $captcha))
{
show_error("Check your math");
}

$message = "

Name: $name
E-mail: $email

Message:
$message

";

mail($myemail, $subject, $message);

header('Location: thanks.html');
exit();

function check_input($data, $problem='')
{
$data = trim($data);
$data = stripslashes($data);
$data = htmlspecialchars($data);

if ($problem && strlen($data) == 0)
{
show_error($problem);
}
return $data;
}

function show_error($myError)
{
?>

Please correct the following error:

<?php echo $myError; ?>

Hit the back button and try again

<?php
exit();
}
?>

Most of my comments are unrelated to security.  A few down at the bottom.

$myemail = "YOUR EMAIL ADDRESS";

Elsewhere you use snake_case names.  If you did that here, you'd have $my_email.  I'm assuming that you removed the read email address for privacy reasons.

if (!preg_match("/([\w\-]+\@[\w\-]+\.[\w\-]+)/", $email))
{
show_error("E-mail address not valid");
}

The indenting here is not standard.  Usually it would have been written

if ( ! preg_match('{([\w\-]+\@[\w\-]+\.[\w\-]+)}', $email) )
{
    show_error("E-mail address not valid");
}

I also added some whitespace in the if because I find it easier to read.

I changed to a single quoted string and used a different regular expression delimiting pair.

Another problem is that this will match some invalid emails.  For example, -@-.- is valid in this pattern.  So if those five characters appear in the field, it will be recognized as valid.  Note that you don't restrict characters that appear before and after that sequence.

if (!preg_match("/5/", $captcha))

This would match 15, 51, etc. as well as 5.  You don't need to use preg_match here.  You can just say something like

if ( '5' != $captcha )

or

if ( 5 != (int)$captcha )

Note that if you want the exact original functionality (match any string that contains the number 5), you could say

if ( false === strpos($captcha, '5') )

That would be much faster than the regular expression version.

$message = "

Name: $name
E-mail: $email

Message:
$message

";

This would more commonly be written with a heredoc rather than a multiline double quoted string.

$message = <<<EOM

Name: $name
E-mail: $email

Message:
$message

EOM;

You don't need a final

?>

The usual convention is to leave it off if your script is not supposed to produce output.  Technically speaking show_error does produce output, but it's not supposed to be called by the script.  I'd leave off the final ?>.

Security

You don't show how the $subject is set, so it's unclear if it's safe or not.  If this is the whole script, it will send with a blank subject.

Note that trim and stripslashes do not add security.  They help fix the input to make it display properly.  The normal use of stripslashes is to undo a PHP security protection that didn't quite work right.  The htmlspecialchars is the security function.  I'm not sure that email is vulnerable to HTML characters.  Perhaps your email client is though.


Implemented heapsort algorithm in Java I am learning algorithms by using Java. Here is an implementation of heapsort. Let me know if anything is wrong and and suggestion to improve the algorithm.

public class HeapSort {
    public int arr[];

    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    // to make a heap
    public void makeHeap() {
        for (int i = 0; i < arr.length; i++) {
            // index of child element
            int index = i;
            while (index != 0) {
                int parent = (index - 1) / 2;
                if (arr[index] <= arr[parent]) break;
                // swap child element to its parent one
                int temp = arr[index];
                arr[index] = arr[parent];
                arr[parent] = temp;
                index = parent;
            }
        }
    }

    // to remove item from the top of the binary tree -> arr[0]
    public void removeTopItem(int count) {
        int a = arr[0];
        arr[0] = arr[count];
        arr[count] = a;
        int index = 0;
        count--;
        // to remake binary tree
        while (true) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;

            // check the boundary
            if (rightChild > count) break;
            if (arr[index] > arr[leftChild] && arr[index] > arr[rightChild]) break;

            // to get greater parent
            int parentGreat = arr[rightChild] > arr[leftChild] ? rightChild : leftChild;

            // swap current item to its parent one
            int temp = arr[index];
            arr[index] = arr[parentGreat];
            arr[parentGreat] = temp;
            index = parentGreat;
        }
    }

    // sort using by heap
    public int[] heapSort() {
        // make a heap
        makeHeap();
        // sorting
        for (int i = arr.length - 1; i >= 0; i--) {
            removeTopItem(i);
        }
        return arr;
    }
}

I did test it, it is working well. Well,

    System.out.println(Arrays.toString(
        new HeapSort(new int[] {3, 2, 1}).heapSort()));

isn't working.

document/comment your code.
You commented (all public method) members, see above for standard tool support.
For every non-trivial piece of code, what is the reason it is there, in the first place?
Starting at the class-, if not package-level:

/** HeapSort as a java.util.function.UnaryOperator<T>.
 * Java & coding beginner's exercise
 *  in type design and algorithm implementation.
 * The general idea is to turn the array into a max-heap
 *  and repeatedly move the max item
 *  from the shrinking heap to its current end.
 */
class HeapSort<T> implements In_placeSorter<T> {
    @Override
    public T sort(T toBeSorted) {
        if (!(toBeSorted instanceof int[]))
            throw new IllegalArgumentException("int[] only, for now");
        comparables = (int[]) toBeSorted;
        return (T) sort();
    } …

(note sort() not (doc)commented here: inherits from In_placeSorter<T>)
name things for what use they are. arr is horribly unspecific (used comparables instead).
don't make things more visible than they need to be. When in doubt, start with default/not specifying visibility:
int comparables[];
pay attention to boundaries:
neither the loop in makeHeap() nor the one in heapSort() need to handle index 0.
More importantly, while it is true that a right child needs to exist to be handled: what about left?
trying to implement "the general idea" without looking what&how others have done is a great step in learning —
please precede it by considering how do I know/check the specification is met?
asking how to improve the procedure is another great step in programming
(professionals prefix a when and). Start with algorithm;
Just don't try to force it - if nothing suggests itself, turn to something else temporarily, sleep on it, or now look what others have done and how, for heap-sort:

why do heapify()s start at the middle of the array?
what is to be gained from not comparing the item to be (re-)inserted while there are two children?

Continue with coding: e.g., there are several instances where you exchange/swap elements: "factor out" a method/procedure
handle petty concerns last, if at all:
Java arrays & java.util.Arrays don't come with a swap()? Use java.util.Collections.swap(java.util.List, int, int) as a template
using a for-loop:
for (int index = i, parent ; index != 0 ; index = parent) {…

Just in case:

/** Rearranges items in ascending "natural" order. */
interface In_placeSorter<T> extends java.util.function.UnaryOperator<T> {
    /** Rearranges items in ascending "natural" order.
     * @param toBeSorted items to be sorted
     * @return toBeSorted */
    T sort(T toBeSorted);
    @Override
    default T apply(T t) { return sort(t); }
}


Simple text parser using regexes I'm trying to write simple parser using regexes. This is what I currently have, it looks really messy. Any tips what can I change?
from re import compile
from typing import Dict, Iterator, List, NamedTuple, TextIO

# PATTERNS
registers_pattern = list(map(compile, [
  r'(rax=[0-9a-f]{16}) (rbx=[0-9a-f]{16}) (rcx=[0-9a-f]{16})\n',
  r'(rdx=[0-9a-f]{16}) (rsi=[0-9a-f]{16}) (rdi=[0-9a-f]{16})\n',
  r'(rip=[0-9a-f]{16}) (rsp=[0-9a-f]{16}) (rbp=[0-9a-f]{16})\n',
  r' (r8=[0-9a-f]{16})  (r9=[0-9a-f]{16}) (r10=[0-9a-f]{16})\n',
  r'(r11=[0-9a-f]{16}) (r12=[0-9a-f]{16}) (r13=[0-9a-f]{16})\n',
  r'(r14=[0-9a-f]{16}) (r15=[0-9a-f]{16})\n',
]))

flags_pattern = compile(r'iopl=[0-9a-f]+(?:\s+[a-z]{2}){8}\n')
segments_pattern = compile(r'(?:[a-z]{2}=[0-9a-f]{4}\s+){6}efl=[0-9a-f]{8}\n')
label_pattern = compile(r'[\w\+]+:\n')

instruction_pattern = compile(
  r'[0-9a-f]{8}`[0-9a-f]{8}\s+(?P<ENCODING>[0-9a-f]+)\s+(?P<INSTRUCTION>.+?)\n?'
)

class Instruction(NamedTuple):
  instruction: str
  encoding: str
  registers: Dict[str, str]

def parse_trace(stream: TextIO) -> Iterator[Instruction]:
  """ TODO: some description
  """

  iterator = iter(enumerate(stream, start=1))
  for index, line in iterator:
    # Parse general-purpose registers
    registers: Dict[str, str] = {}

    for pattern in registers_pattern:
      if match := pattern.fullmatch(line):
        # Extract register values from regex match and go to the next line
        registers.update(group.split('=') for group in match.groups())
        index, line = next(iterator)
      else:
        raise RuntimeError(f'Failed to parse line: {index}')

    if flags_pattern.fullmatch(line) is None:
      raise RuntimeError(f'Failed to parse line: {index}')

    if segments_pattern.fullmatch(next(iterator)[1]) is None:
      # TODO: here will be something
      raise RuntimeError(f'Failed to parse line: {index}')

    if label_pattern.fullmatch(next(iterator)[1]) is None:
      raise RuntimeError(f'Failed to parse line: {index}')

    if (match := instruction_pattern.fullmatch(next(iterator)[1])) is None:
      raise RuntimeError(f'Failed to parse line: {index}')

    yield Instruction(match.group('INSTRUCTION'), match.group('ENCODING'), registers)

# Example of usage:
from io import StringIO

trace = StringIO("""rax=0000000000000000 rbx=0000000000000000 rcx=0000000000000000
rdx=0000000000000000 rsi=0000000000000000 rdi=0000000000000000
rip=000000000040100a rsp=0000000000000000 rbp=0000000000000000
 r8=0000000000000000  r9=0000000000000000 r10=0000000000000000
r11=0000000000000000 r12=0000000000000000 r13=0000000000000000
r14=0000000000000000 r15=0000000000000000
iopl=0         nv up ei pl zr na po nc
cs=0033  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000246
lol+0x1000:
00000000`00401000 48bba47868302035e80c mov rbx,0CE83520306878A4h
rax=0000000000000000 rbx=0000000000000000 rcx=0000000000000000
rdx=0000000000000000 rsi=0000000000000000 rdi=0000000000000000
rip=000000000040100a rsp=0000000000000000 rbp=0000000000000000
 r8=0000000000000000  r9=0000000000000000 r10=0000000000000000
r11=0000000000000000 r12=0000000000000000 r13=0000000000000000
r14=0000000000000000 r15=0000000000000000
iopl=0         nv up ei pl zr na po nc
cs=0033  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00000246
lol+0x1000:
00000000`00401000 48bba47868302035e80c mov rbx,0CE83520306878A4h""")

for each in parse_trace(trace):
  print(each.instruction)
```

Instead of trying to match whole lines, it would be simpler to match smaller chunks of the input and the combine the smaller regexes.  For example, one regex could match any of the registers, a different one could match the segment registers, etc.  Order of the patterns may be important if one regex is be a prefix of another, but that doesn't seem to apply in this case.
Use capture groups to get the important information, and MatchObject.lastgroup to see which part of the regex matched.
The flags pattern probably needs to have other codes added.
The (?x) in the pattern is for verbose mode, which lets you add whitespace and comments to the regex pattern.
pattern = r"""(?x)
     (?P<REG>r\w{1,2})=(?P<RVAL>[0-9a-f]{16})            # registers
    |iopl=(?P<IOPL>[0-9a-f]+)                            # iopl
    |(?P<FLAGS>(\s+(?:nv|up|ei|pl|zr|na|po|nc))+)        # flags
    |(?P<SREG>[csdefg]s|efl)=(?P<SVAL>[0-9a-f]+)         # segments
    |(?P<LABEL>^[\w\+]+:)                                # label
    |[0-9a-f]{8}`[0-9a-f]{8}\s+(?P<ENCODING>[0-9a-f]+)\s+(?P<INSTRUCTION>.+)
    |(?P<NL>\n)
    """
regex = re.compile(pattern)

registers = {}

lineno = 1

for line in trace:
    print(f"line = {lineno}")

    for mo in regex.finditer(line):
        group_name = mo.lastgroup

        if group_name == 'NL':
            lineno += 1

        else:
            if group_name == "RVAL":
                registers[mo['REG']] = mo['RVAL']
                print(f"   {mo['REG']} = {mo['RVAL']}")

            elif group_name == "IOPL":
                print(f"   iopl = {mo['IOPL']}")

            elif group_name == "FLAGS":
                print(f"   FLAGS = {mo['FLAGS'].strip().split()}")

            elif group_name == "SVAL":
                print(f"   {mo['SREG']} = {mo['SVAL']}")

            elif group_name == "LABEL":
                print(f"   LABEL = {mo['LABEL']}")

            elif group_name == "INSTRUCTION":
                print(f"   {mo['INSTRUCTION']} = {mo['ENCODING']}")

For the sample input, the code outputs:
line = 1
   rax = 0000000000000000
   rbx = 0000000000000000
   rcx = 0000000000000000
line = 2
   rdx = 0000000000000000
   rsi = 0000000000000000
   rdi = 0000000000000000
line = 3
   rip = 000000000040100a
   rsp = 0000000000000000
   rbp = 0000000000000000
line = 4
   r8 = 0000000000000000
   r9 = 0000000000000000
   r10 = 0000000000000000
line = 5
   r11 = 0000000000000000
   r12 = 0000000000000000
   r13 = 0000000000000000
line = 6
   r14 = 0000000000000000
   r15 = 0000000000000000
line = 7
   iopl = 0
   FLAGS = ['nv', 'up', 'ei', 'pl', 'zr', 'na', 'po', 'nc']
line = 8
   cs = 0033
   ss = 002b
   ds = 002b
   es = 002b
   fs = 0053
   gs = 002b
   efl = 00000246
line = 9
   LABEL = lol+0x1000:
line = 10
   mov rbx,0CE83520306878A4h = 48bba47868302035e80c
line = 11
   rax = 0000000000000000
   rbx = 0000000000000000
   rcx = 0000000000000000
line = 12
   rdx = 0000000000000000
   rsi = 0000000000000000
   rdi = 0000000000000000
line = 13
   rip = 000000000040100a
   rsp = 0000000000000000
   rbp = 0000000000000000
line = 14
   r8 = 0000000000000000
   r9 = 0000000000000000
   r10 = 0000000000000000
line = 15
   r11 = 0000000000000000
   r12 = 0000000000000000
   r13 = 0000000000000000
line = 16
   r14 = 0000000000000000
   r15 = 0000000000000000
line = 17
   iopl = 0
   FLAGS = ['nv', 'up', 'ei', 'pl', 'zr', 'na', 'po', 'nc']
line = 18
   cs = 0033
   ss = 002b
   ds = 002b
   es = 002b
   fs = 0053
   gs = 002b
   efl = 00000246
line = 19
   LABEL = lol+0x1000:
line = 20
   mov rbx,0CE83520306878A4h = 48bba47868302035e80c

Obviously, do something useful instead of just printing the information.


What is a good way to structure mark-up generating code and avoid the example mess? Here are two methods of code that only vary in one place. Specifically, the first method calls GetReleaseYear(), and the second calls GetReleaseDate().

This is one example of a one-line difference in multiple methods, and each time the difference might be on a different line or couple of lines. One possible design I've considered is passing in a list of strings to a function, but this is cumbersome because the lists would still need to be prepared, and the generated HTML still has to be somewhat content-aware.

private string A()
    {
        string title = GetTitle();
        string mediaType = GetMediaType();
        string description = GetDescription();
        string releaseYear = GetReleaseYear();
        string contributors = GetContributors();
        string image = GetImage();
        string genres = GetGenres();
        string ratings = GetRatings();

        string top = string.Format("{0}This is a {1}{2}.

",
                title, mediaType, string.IsNullOrEmpty(releaseYear) ? string.Empty
                : " released in " + releaseYear);

        StringBuilder metadata = new StringBuilder();
        metadata.AppendLine(contributors + "
");
        metadata.AppendLine(genres + "

");
        metadata.AppendLine(ratings + "

");
        metadata.AppendLine(description);

        return string.Format("{0}

{1}	{2}

", top, metadata.ToString(), image);
    }

 private string B()
    {
        string title = GetTitle();
        string mediaType = GetMediaType();
        string description = GetDescription();
        string releaseDate = GetReleaseDate();
        string contributors = GetContributors();
        string image = GetImage();
        string genres = GetGenres();
        string ratings = GetRatings();

        string top = string.Format("{0}This is a {1}{2}.

",
                title, mediaType, string.IsNullOrEmpty(releaseDate) ? string.Empty
                : " released in " + releaseDate);

        StringBuilder metadata = new StringBuilder();
        metadata.AppendLine(contributors + "
");
        metadata.AppendLine(genres + "

");
        metadata.AppendLine(ratings + "

");
        metadata.AppendLine(description);

        return string.Format("{0}

{1}	{2}

", top, metadata.ToString(), image);
    }

A good practice is Observe which part of the code does not change Extract that keep it in a separate method.  Pass the variable Which changes as an input to that method.

    public string CommonMethod(string formattedString)
    {
        string title = GetTitle();
        string mediaType = GetMediaType();
        string description = GetDescription();
        /***string releaseYear = GetReleaseYear();***/ this is not required.
        string contributors = GetContributors();
        string image = GetImage();
        string genres = GetGenres();
        string ratings = GetRatings();

        string top = **formattedString**;

        StringBuilder metadata = new StringBuilder();
        metadata.AppendLine(contributors + "
");
        metadata.AppendLine(genres + "

");
        metadata.AppendLine(ratings + "

");
        metadata.AppendLine(description);

        return string.Format("{0}

{1}	{2}

", top, metadata.ToString(), image);
    }

each time the difference might be on a different line or couple of lines.

This part is difficult to answer. Even in that scenario, omit the one or two lines which may change, pass the things which may change as input.


Molybdenum2019 challenge efficient implementation I'm working on a solution that is correct but inefficient.
https://app.codility.com/programmers/task/leader_slice_inc/
This is my code :
public static void main(String[] args) {
    int[] A = { 2, 1, 3, 1, 2, 2, 3 };
    int[] B = null;
    int M = 5, K = 3;
    int array_lengh = A.length;
    Map<Integer, Integer> counter = null;
    Set<Integer> listaLideres = new LinkedHashSet<Integer>();

    // valor minimo =0 ; valor maximo = Longitud del array - k;
    // el lider sera aquel que ocurra mas de longitud/2

    for (int i = 0; i < array_lengh - K + 1; i++) {
        B = Arrays.copyOf(A, array_lengh);
        counter = new HashMap<Integer, Integer>();

        for (int j = i; j < i + K; j++) {
            B[j] = B[j] + 1;
        }

        for (int n = 0; n < array_lengh; n++) {
            int repeticones = counter.get(B[n]) == null ? 0 : counter.get(B[n]);
            counter.put(B[n], repeticones + 1);
        }

        int liderProvisional = 0;
        for (Map.Entry<Integer, Integer> valorRepeticion : counter.entrySet()) {
            liderProvisional = valorRepeticion.getValue();
            if (liderProvisional > array_lengh / 2) {
                listaLideres.add(valorRepeticion.getKey());
            }
        }
    }

    List<Integer> listaLideresOrdenada = new ArrayList<Integer>();
    listaLideresOrdenada.addAll(listaLideres);

    listaLideresOrdenada.sort(Comparator.naturalOrder());

    for (Integer integer : listaLideresOrdenada) {
        System.out.println(integer);
    }
}

Nice solution, find below my suggestions.

Creating a list from a set:
List<Integer> listaLideresOrdenada = new ArrayList<Integer>();
listaLideresOrdenada.addAll(listaLideres);

The set can be passed directly to the constructor of ArrayList:
List<Integer> listaLideresOrdenada = new ArrayList<Integer>(listaLideres);

Copying the input array A to B:
B = Arrays.copyOf(A, array_lengh);

This can be avoided since A can be modified in place in this problem.

Getting a value of a map or a default:
int repeticones = counter.get(B[n]) == null ? 0 : counter.get(B[n]);

Since Java 8 Map offers getOrDefault:
int repeticones = counter.getOrDefault(B[n], 0);

Optimization
The current solution uses this approach:

For each sliding window in A
Increment all elements of the sliding window by 1
Calculate the frequencies of all elements in A
Update the result if a leader is found

It can be considered a \$O(n^2)\$ brute force approach, typically not enough to solve a HARD problem on Codility.
Consider this approach: every time the sliding window moves to the right, the element on the left leaves the window, and the element on the right enters the windows. Therefore it is enough to update the frequencies of only these two numbers.
This approach improves the complexity to \$O(n*log(n))\$. The sorting operation is now the bottleneck.
A trick to avoid sorting is to use an array (for example, leaders) of size M (which is the value of the biggest element in A). Every time a leader x is found add it to leaders like leaders[x] = true. Finally, iterate on leaders and collect the results in order.
Getting rid of the sorting operation improves the complexity to \$O(m)\$, but it's still too slow! The solution needs to run in less than 0.1 seconds for an input array A of 100K elements.
So as a last optimization we can get rid of the map for counting the frequencies and use a simple array freq. Although updating a map is a very quick operation, updating an array is faster.
Reworked code
public static int[] solution(int K, int M, int[] A) {
    boolean[] leaders = new boolean[M + 2];
    int[] freq = new int[M + 2];
    int threshold = A.length / 2;

    // Increment initial sliding window by 1
    for (int i = 0; i < K; A[i]++, i++);

    // Calculate frequencies of all elements in A
    for (int i = 0; i < A.length; freq[A[i]]++, i++);

    // If there are leaders save them
    for (int i = 0; i < freq.length; i++) {
        leaders[i] = freq[i] > threshold || leaders[i];
    }

    for (int i = 1; i < A.length - K + 1; i++) {
        // Update frequency of element (on the left) leaving the sliding window
        int left = i - 1;
        freq[A[left]]--;
        A[left]--;
        freq[A[left]]++;

        // Update frequency of element (on the right) entering the sliding window
        int right = i + K - 1;
        freq[A[right]]--;
        A[right]++;
        freq[A[right]]++;

        // If there are new leaders save them
        leaders[A[right]] = freq[A[right]] > threshold || leaders[A[right]];
        leaders[A[left]] = freq[A[left]] > threshold || leaders[A[left]];
    }
    // Collect the leaders (in order)
    return IntStream.range(0, leaders.length)
            .filter(i -> leaders[i])
            .toArray();
}


Simple parallel_for_each in C++ I need to parallelise a for loop that does quite a lot of processing over thousands of items. I came up with this basic loop that seems to work quite effectively on a small test.

template<class T, class C>
void parallel_for_each(std::vector<T>* ts, C callable, uint poolsize = (std::thread::hardware_concurrency()+1)*2) {

    atomic<size_t> index(0);
    std::vector<thread> threads;

    for (uint i = 0; i < poolsize; i++) {
        threads.emplace_back([&]() {
            while(index < ts->size()) {
                callable(ts->at(index++));
            }
        });
    }
    for (auto&& thread : threads) {
        thread.join();
    }
}

//use like:
std::vector<int> is= { 4,5, 6,7,8,3,2,25,44,34,562,356,235,66,3,45,66};
parallel_for_each(&is, print);

Is there any serious problem I've overlooked, or anything else I can improve?

If you are not going to create a long running thread pool (and manage the threads over many jobs), then I would let the system do it for you; the async() function potentially runs stuff in parallel and manages a thread pool for you.

// Not tested.
// You may need to play with it.
template<class T, class C>
void parallel_for_each(std::vector<T>& ts, C callable)
{
    size_t index =;
    std::vector<std::future> results;

    for(auto const& value: ts)
    {
        results.emplace_back(async(callable, value));
    }
    for (auto& result : results)
    {
        result.wait();
    }
}

Other notes

Don't pass pointers around.

One of your parameters is:

std::vector<T>* ts
          //  ^  Pointer

Passing by pointer is very rare in C++ (very common in bad C++ written by old C programmers). The reason for this is there are no ownership semantics associated with the pointer and thus potential for misunderstanding the interface and thus leading to memory leaks.

In C++ we want to very clearly define the ownership of pointers as it is the owner of the pointer (and nobody else) that is responsible for deleting the pointer. The language has introduced smart pointers that allow us to specify ownership so that when the pointer is passed we are explicit in passing ownership with the pointer. In other situations were ownership is not passed we use references.

If I was using your function for the first time I could not tell if I need to dynamically create the vector or not. Is your function going to delete the passed pointer? I can't tell from reading the interface because raw pointers have no ownership semantics.

If you change your interface to pass by reference then it works just as well and there will be no confusion. If you want to pass ownership, you need to use smart pointers to indicate the type of ownership that is being transferred.

Prefer prefix increment.

ts->at(index++)

It makes no difference for integer types. But when using other types (including iterators) the default implementation for increment usually makes the prefix version more efficient. So when it makes no difference to your code, prefer the prefix version. This allows the types of your objects to be changed without having to update the code and it will still be the most efficient version.

Prefer operator[]() to at()

If you know that your access to an array will always be in bounds then prefer operator[] as it performs no accesses checks and is thus quicker.

Note: throwing an exception that is not caught inside a thread will cause the application to terminate. Throwing an exception inside an async will catch the exception and transfer it to the future object allowing the main thread to detect it.

Don't know why you are using r-value reference here

for (auto&& thread : threads)
         ^^

Don't know what that gives you. Note: an named r-value reference is treated liked an r-value when passed as a parameter (because it is named). You would still need to call std::move() on it to make it bind to the r-value reference function.

  Sorry I don't know the X/R/L/V value naming scheme very well yet so I am using an older terminology. Please have a look at appropriate documentation.

Personally I would just use a reference:

for (auto& thread : threads)


Avoiding use of .encode() in rss2html My concern with this code is the excessive use of .encode('utf-8').  Any advice on refining these functions would be very helpful.

rss2html GitHub repo

#!/usr/bin/env python

""" Simple rss to html converter """

__version__ = "0.0.1"
__author__ = "Ricky L Wilson"

from feedparser import parse as parsefeed
import StringIO

def entry2html(**kwargs):
    """ Format feedparser entry """
    title = kwargs['title'].encode('utf-8')
    link = kwargs['link'].encode('utf-8')
    description = kwargs['description'].encode('utf-8')
    template = """

{title}

    {title}
    {description}
    """
    return template.format(title=title, link=link, description=description)

def convert_feed(**kwargs):
    """ Main loop """
    out = StringIO.StringIO("")
    for entry in parsefeed(kwargs['url']).entries:
        title = entry['title']
        link = entry['link']
        description = entry['description']
        print >>out, entry2html(title=title, link=link,
                                description=description)
    return out.getvalue()

print convert_feed(url='http://stackoverflow.com/feeds')

Work in Unicode and encode at the last moment:

def entry2html(**kwargs):
    """ Format feedparser entry """
    template = u"""

{title}

    {title}
    {description}
    """
    return template.format(**kwargs)

def convert_feed(**kwargs):
    """ Main loop """
    out = u'\n'.join(entry2html(**entry)
                    for entry in parsefeed(kwargs['url']).entries)
    return out.encode('utf-8')

You can pass entry directly as format does not mind extra keyword arguments. StringIO is not necessary for simple concatenation of strings.


Regex to match phone numbers, with comments Regular expressions are one of the worst aspects of debugging hell. Since they are contained in string literals, It's hard to comment how they work when the expressions are fairly long.

I have the following regular expression:

\b\d{3}[-.]?\d{3}[-.]?\d{4}\b

Source: RegExr.com

I commented it like this:

import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) {
        String regexStr = "";

        regexStr += "\\b";     //Begin match at the word boundary(whitespace boundary)
        regexStr += "\\d{3}";  //Match three digits
        regexStr += "[-.]?";   //Optional - Match dash or dot
        regexStr += "\\d{3}";  //Match three digits
        regexStr += "[-.]?";   //Optional - Match dash or dot
        regexStr += "\\d{4}";  //Match four digits
        regexStr += "\\b";     //End match at the word boundary(whitespace boundary)

        if (args[0].matches(regexStr)) {
            System.out.println("Match!");
        } else {
            System.out.println("No match.");
        }
    }
}

What would be the best way to go about commenting regular expressions to make them readable for beginners? Is there a better way than what I have shown?

Whatever you do, don't append strings like that!  If you look at the generated bytecode, you'll see that the compiler does exactly what you told it to do:

$ javap -c Main
Compiled from "Main.java"
public class Main {
  public Main();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: ldc           #2                  // String
       2: astore_1
       3: new           #3                  // class java/lang/StringBuilder
       6: dup
       7: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      10: aload_1
      11: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      14: ldc           #6                  // String \b
      16: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      19: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      22: astore_1
      23: new           #3                  // class java/lang/StringBuilder
      26: dup
      27: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      30: aload_1
      31: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      34: ldc           #8                  // String \d{3}
      36: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      39: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      42: astore_1
      43: new           #3                  // class java/lang/StringBuilder
      46: dup
      47: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      50: aload_1
      51: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      54: ldc           #9                  // String [-.]?
      56: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      59: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      62: astore_1
      63: new           #3                  // class java/lang/StringBuilder
      66: dup
      67: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      70: aload_1
      71: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      74: ldc           #8                  // String \d{3}
      76: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      79: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      82: astore_1
      83: new           #3                  // class java/lang/StringBuilder
      86: dup
      87: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      90: aload_1
      91: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      94: ldc           #9                  // String [-.]?
      96: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      99: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
     102: astore_1
     103: new           #3                  // class java/lang/StringBuilder
     106: dup
     107: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
     110: aload_1
     111: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
     114: ldc           #10                 // String \d{4}
     116: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
     119: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
     122: astore_1
     123: new           #3                  // class java/lang/StringBuilder
     126: dup
     127: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
     130: aload_1
     131: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
     134: ldc           #6                  // String \b
     136: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
     139: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
     142: astore_1
     143: aload_0
     144: iconst_0
     145: aaload
     146: aload_1
     147: invokevirtual #11                 // Method java/lang/String.matches:(Ljava/lang/String;)Z
     150: ifeq          164
     153: getstatic     #12                 // Field java/lang/System.out:Ljava/io/PrintStream;
     156: ldc           #13                 // String Match!
     158: invokevirtual #14                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
     161: goto          172
     164: getstatic     #12                 // Field java/lang/System.out:Ljava/io/PrintStream;
     167: ldc           #15                 // String No match.
     169: invokevirtual #14                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
     172: return
}

If you change it to concatenate all the string literals in one statement…

public class Main {
    public static void main(String[] args) {
        String regexStr =
            "\\b" +      //Begin match at the word boundary(whitespace boundary)
            "\\d{3}" +   //Match three digits
            "[-.]?" +    //Optional - Match dash or dot
            "\\d{3}" +   //Match three digits
            "[-.]?" +    //Optional - Match dash or dot
            "\\d{4}" +   //Match four digits
            "\\b";       //End match at the word boundary(whitespace boundary)

        if (args[0].matches(regexStr)) {
            System.out.println("Match!");
        } else {
            System.out.println("No match.");
        }
    }
}

Then the bytecode is much saner (one literal string at offset 0):

$ javap -c Main
Compiled from "Main.java"
public class Main {
  public Main();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: ldc           #2                  // String \b\d{3}[-.]?\d{3}[-.]?\d{4}\b
       2: astore_1
       3: aload_0
       4: iconst_0
       5: aaload
       6: aload_1
       7: invokevirtual #3                  // Method java/lang/String.matches:(Ljava/lang/String;)Z
      10: ifeq          24
      13: getstatic     #4                  // Field java/lang/System.out:Ljava/io/PrintStream;
      16: ldc           #5                  // String Match!
      18: invokevirtual #6                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      21: goto          32
      24: getstatic     #4                  // Field java/lang/System.out:Ljava/io/PrintStream;
      27: ldc           #7                  // String No match.
      29: invokevirtual #6                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      32: return
}


Searching for a binary tree for a vehicle with a given name I'm searching my binary search tree of Vehicle objects and I'm just wondering whether there would be much point, if it's best practice to search to see if a node has a left/right child first like so:

return n.hasLeft() ? find(name, n.left()) : null;

Or just go with the following, since it will return null if it doesn't exist anyway:

return find(name, n.left());

Here's the code for the whole method:

protected Vehicle find(String name, Node n)
{
    if (n == null) return null;

    int order = name.compareTo(n.getVehicleName());

    if (order == 0)
        return n.getVehicle();
    else if (order < 0)
        return n.hasLeft() ? find(name, n.left()) : null;
    else
        return n.hasRight() ? find(name, n.right()) : null;
}

Would checking first be more efficient since it saves an extra recursive call being made?

The if (n == null) return null;statement in find() is the only base case that you need. Checking for n.hasLeft() is redundant, and it doesn't even reduce the total number of function calls, since n.hasLeft() is itself a function call.


Copying one array to the end of another array I wrote a program that places values in one array to the end of another array. It keeps the order of the values. If the second array is bigger, then there will be leading zeroes.

Is there anything I can improve? How do I simplify this program?

#include <iostream>

    int main()
    {
        int fromArray[10] = {11,22,33,44,55,66,77,88,99,100};
        int toArray[15] = {};

        int size = sizeof(fromArray)/sizeof(fromArray[0]);

        int * first = fromArray;
        int * last = first + size; //One past end of array
        int * toLast = toArray + sizeof(toArray)/sizeof(toArray[0]); //One past end of array

        for(first; first != last;)
            *(--toLast) = *(--last);

        for(int i=0; i<sizeof(toArray)/sizeof(toArray[0]); i++)
            std::cout << toArray[i] << " ";

    }

Be aware that sizeof is actually an operator, not a function.  It also returns std::size_t, which is an unsigned integer type.  You currently have size as an int, which is a signed type.  If you had your compiler warnings up high (and they should be), then you probably would've been warned about this.

std::size_t size = sizeof(fromArray)/sizeof(fromArray[0]);


Getting current time with milliseconds I am looking for a more efficient or shorter way to achieve the following output using the following code:

timeval curTime;
gettimeofday(&curTime, NULL);
int milli = curTime.tv_usec / 1000;

time_t rawtime;
struct tm * timeinfo;
char buffer [80];

time(&rawtime);
timeinfo = localtime(&rawtime);

strftime(buffer, 80, "%Y-%m-%d %H:%M:%S", timeinfo);

char currentTime[84] = "";
sprintf(currentTime, "%s:%d", buffer, milli);
printf("current time: %s \n", currentTime);

Sample output:

  current time: 2012-05-16 13:36:56:396

I would prefer not to use any third-party library like Boost.

When you call gettimeofday it gives you the number of seconds since EPOCH too, so you don't need to call time again. And when you use output of localtime as input of strftime, you may omit the intermediate variable (not a very useful point though). So your code could be written like:

timeval curTime;
gettimeofday(&curTime, NULL);
int milli = curTime.tv_usec / 1000;

char buffer [80];
strftime(buffer, 80, "%Y-%m-%d %H:%M:%S", localtime(&curTime.tv_sec));

char currentTime[84] = "";
sprintf(currentTime, "%s:%03d", buffer, milli);
printf("current time: %s \n", currentTime);

an important note to be considered is that functions like localtime are not thread-safe, and you'd better use localtime_r instead.


Efficient LC3 assembly code to print the numbers leading up to any digit I'm using an LC3 microarchitecture simulator to write assembly code. I've only been writing assembly for about three weeks, so I am still very new.

My goal is to print all the numbers leading up to a set value, so for example, if the user selects '6' the console prints 012345. My code works, but the unit test says my code is inefficient or has an infinite loop.

I set the value by manually setting R1 in my simulator to any value. The rest is automated with the code, starting at 0x3000.

LD, R0, X3001 ;Load R0 with 0
0 ;I did this b/c I don't know how to load a register with ascii values
AND R2, R2, #0 ; Set R2=0
NOT R3, R1 ;invert R1, store in R3
ADD R3, R3, #1 ;Add 1 to R3, now R3=-R1
ADD R4, R0, R3 ; better way to perform loop? added these to maintain loop
BRz X300b ; if previous math ever produces 0, skip to halt
OUT ; print single char
ADD R0, R0, #1 ; R0++
ADD R1, R1 #-1 ; R1--
BRnzp X3006 ;Always branch back to the above BR instruction
HALT

Hex:

3000
2000
0030
54a0
967f
16e1
1803
0404
f021
1021
127f
0ffb
f025

So my question is, is there any way to make this more efficient?

Points about your program.

The 2 instructions at the top don't match the 3 dumped values! There are 12 lines of source but there are 13 values in the dump. .ORIG X3000 is not an instruction. It's rather a directive and you should not find any value from it in the dump.
Why don't you place the data below the HLT instruction? A much safer place than within the instructions that get executed. Your trick works because of how the BR instruction is encoded.
On an architecture with limited registers available, it's best to try to use as few as possible to get the work done. Your code uses 5 registers where you can easily do it with 2 registers.
You don't need to use the extra register R4 to find out if the input was 0. AND-ing R1 to itself will not destroy it and will set the flags for inspecting:

AND R1, R1, R1
BRz X300B      ;Skip if input was 0

It's inefficient to branch always to just another branch instruction. See how I solved the same branching.

An improved version.

  My goal is to print all the numbers leading up to a set value

Let's presume the user selects a value from 0 to 9.

For now you've manually set the user's value in R1. You can use it as a (down)counter. You stop the program as soon as a negative value appears.

.ORIG X3000
LEA   R0, X3030     ;Loads "0" in R0[7:0]
BRnzp X3004         ;Go test for 0 input
OUT                 ;Display R0[7:0]
ADD   R0, R0, #1    ;R0++
ADD   R1, R1, #-1   ;R1--
BRzp  X3002         ;Continue with zero or positive
HLT                 ;Stop (R1 = #-1)

OUT only depends on bits [7:0]. The high bits loaded with LEA don't matter.
If you don't like this trick, then go with the usual way of loading a constant from memory:

.ORIG X3000
LD    R0, X3007     ;Loads "0" in R0
BRnzp X3004         ;Go test for 0 input
OUT                 ;Display R0[7:0]
ADD   R0, R0, #1    ;R0++
ADD   R1, R1, #-1   ;R1--
BRzp  X3002         ;Continue with zero or positive
HLT                 ;Stop (R1 = #-1)
.FILL X0030         ;Character "0"


Searching for pairs of integers that satisfy primality and divisibility conditions I wrote a program in Python 3 to check all tuples of the form (s,t) where s and t are positive integers satisfying three conditions:

The inequalities s <= t^2 and t <= s^2 hold, and the value s+t divides st(s+1)(t+1);
The value of s+1 is prime;
The inequalities both s * [math.ceil( math.ceil( (t^2)/(s+1) ) * ((s+1)/t) )] > s(s+t) and s > t hold.

I'm interested in how often a tuple (s,t) satisfies each of these conditions in turn; that is, how often a tuple meets condition (1), versus meeting both (1) and (2), versus meeting (1) - (3).

import math

def IsPrime(n):
# This returns True if a number is prime, and False if the number is composite.
    if n % 2 == 0 and n > 2:
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))

def IsGQ(s,t):
# This checks the divisibility condition.
    return (s*t*(s+1)*(t+1)) % (s+t) == 0 and s <= t**2 and t <= s**2

def IsNotTransitive(s,t):
    n = math.ceil((t**2)/(s+1))
    k = math.ceil(n*((s+1)/t))
    return (s*k) > t*(t+s) and s > t

rng = 1000 # The upper limit that `t` will iterate up to
quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) and (2)
prime_quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) - (3)
intransitive_quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) - (4)

# The next 5 lines place all prime numbers up to rng^2 into a list.
# Ideally, this cuts down on how many times s+1 has to be checked to be a prime.
primes = []
for i in range(1, rng**2):
    if IsPrime(i):
        primes.append(i)

for t in range(4, rng + 1): # Due to project details, I don't care about t<4.
    if t % 50 == 0:
        print("We have reached t = " + str(t) + ".")
    for s in range(2, t**2 + 1): # To satisfy condition (1), I don't want s to iterate above t^2
        if IsGQ(s,t): # Condition (1) and (2)?
            quads += 1
            if s+1 in primes:            # Condition (3)?
                prime_quads += 1
                if IsNotTransitive(s,t): # Condition (4)?
                    intransitive_quads += 1

print(str(quads))
print(str(prime_quads))
print(str(intransitive_quads))

Currently, this runs to completion in over 10 minutes for rng = 1000. Ideally, running this for rng = 10000 in a reasonable amount of time is my current goal; computing these numbers for the value rng = 100000 is my most optimistic goal.

Is there any way to reorder my iteration or change my method of checking for primeness that could be more efficient? It seems that the time for s+1 in primes to complete grows quadratically with rng. Since, after a certain point, s+1 will be less than every value in primes that hasn't been checked yet, would it be better to write my own "in" function along the lines of

def CheckPrime(s, primes):
    for n in primes:
        if s+1 == n:
            return True
        elif s+1 < n:
            return False

or would this still be slower than the current code?

Note: IsPrime comes from this Stack Overflow answer.

You are running into several performance problems.

First: if you want to generate a list of primes, you should use a sieve which is much more efficient.

Second: you are checking s+1 in primes, which is inefficient for a list. Instead you should make primes be a set, so that your lookup time is constant.
Third: Instead of for s in range(2, t**2 + 1):, you should use for s in range(floor(t**.5), t**2 + 1):, as this prevents wasting time checking values where s^2<t.

Between these two changes you should see a pretty large speed boost.