Checking whether two strings are isomorphic I was trying to solve a problem to determine if 2 strings are isomorphic. They are isomorphic when each character in string one can be replaced with another character in string 2. Two different characters may not map to the same value, and same character must not match to different values. Also the length of the strings must be same.

I've used exception for logic flow:

module Isomorphism

  class NotIsomorphicException < StandardError
    attr_reader :object
    def initialize(object)
      @object = object
    end
  end

  def self.isomorphic? string_a,string_b
    begin
      self.isomorphism string_a,string_b
      true
    rescue NotIsomorphicException => _
      return false
    end
  end

  protected
  def self.isomorphism string_a,string_b
    raise NotIsomorphicException.new("Unequal length") unless string_a.size == string_b.size

    isomorphism_map = {}
    associations = string_a.chars.zip string_b.chars

    associations.each do |char_one,char_two|
      if(isomorphism_map.key? char_one)
        raise NotIsomorphicException.new("Single character needs to map to multiple characters, not isomorphic") unless isomorphism_map[char_one] == char_two
      elsif(isomorphism_map.value? char_two)
        raise NotIsomorphicException.new("Two characters map to same value")
      end
      isomorphism_map[char_one] = char_two
    end
  end

end

Please let me know if it's okay to code this way and any improvements that I might be able to make this better.

Following are the specs, just in case:

describe Isomorphism do
  it "should return true for single character words" do
    expect(Isomorphism.isomorphic? "t","d").to be true
  end

  it "should return true for empty strings" do
    expect(Isomorphism.isomorphic? "","").to be true
  end

  it "should return false if strings are of unequal length" do
    expect(Isomorphism.isomorphic? "dh","dhruv").to be false
  end

  it "should return false when 2 characters need to map to same character" do
    expect(Isomorphism.isomorphic? "ab","aa").to be false
  end

  it "should return true for egg and add" do
    expect(Isomorphism.isomorphic? "egg","add").to be true
  end

  it "should return false for foo and bar" do
    expect(Isomorphism.isomorphic? "foo","bar").to be false
  end

  it "should return true for paper and title" do
    expect(Isomorphism.isomorphic? "paper","title").to be true
  end

  it "should return false for aab and aaa" do
    expect(Isomorphism.isomorphic? "aab","aaa").to be false
  end
end

Looking at your isomorphism helper function…

The flow of control is kind of nasty.  In particular, burying an unless in here…

if …
  raise Exception.new(…) unless …
elsif …
  raise
end

… is too tricky, because:

You already have an if-elsif expression, and it would be better to work it into the same chain.
It's at the end of a very long line, where it is barely visible.
unless, being a negation, is automatically less preferable to an affirmative if.

Switching the naming convention from string_a, string_b to char_one, char_two is not ideal.  Why not char_a, char_b?  Or better yet, just a, b?

Doing Hash lookups in reverse using value? is not efficient.  You would be better off making a "forward" map and an "inverse" map.  See below for an even better way to decompose the problem.

As for the use of exceptions internally, I think it's a bad idea.  It's just a cumbersome way to return false with commentary.  You could just write a comment to avoid the overhead.  Better yet, if you write the code well, I don't think there is a need for any comment.  For example, in the implementation below, b != expected_b is pretty self-explanatory.

module Isomorphism

  def self.isomorphic?(string_a, string_b)
    surjective?(string_a, string_b) && surjective?(string_b, string_a)
  end

  protected
  def self.surjective?(string_a, string_b)
    return false if string_a.size != string_b.size
    surjection = {}

    string_a.chars.zip(string_b.chars).each do |a, b|
      expected_b = surjection[a]
      if expected_b && (b != expected_b)
        return false
      end
      surjection[a] = b
    end
    true
  end

  # Alternate implementation: shorter, but won't detect failure as quickly
  def self.surjective?(string_a, string_b)
    return false if string_a.size != string_b.size
    pairs = string_a.chars.zip(string_b.chars)
    surjection = Hash[pairs]
    pairs.all? { |a, b| surjection[a] == b }
  end

end


Avoiding code repetition while handling exceptions For my application, I need to use two slightly different algorithms for persisting an entity:

def persistRandomAlias(self, alias):
    self.em.persist(alias)
    try:
        self.em.flush()
    except DBALException as e:
        if e.previous.code != 23000:
            raise e
        self.reloadEM()

        self.persistRandomAlias(alias)

def persistCustomAlias(self, alias):
    self.em.persist(alias)
    try:
        self.em.flush()
    except DBALException as e:
        if e.previous.code != 23000:
            raise e
        self.reloadEM()

        existing = self.findByNaturalKey(alias.name)
        if existing != alias:
            raise DuplicateNameException('The requested name is already taken', e)

The difference between them is in part of the code responsible for exception handling. I thought about putting the common code in one method, with remaining operations passed in a function that would accept exception object, like this:

def persistAlias(self, alias, exHandler):
    self.em.persist(alias)
    try:
        self.em.flush()
    except DBALException as e:
        if e.previous.code != 23000:
            raise e
        self.reloadEM()

        exHandler(e)

def persistRandomAlias(self, alias):
    self.persistAlias(alias, lambda e: self.persistRandomAlias(alias))

def persistCustomAlias(self, alias):
    def exHandler(e):
        existing = self.findByNaturalKey(alias.name)
        if existing != alias:
            raise DuplicateNameException('The requested name is already taken', e)

    self.persistAlias(alias, exHandler)

However, I'm not sure if it is correct to pass an unused argument to a function.

I have also thought about refactoring common code into an abstract method object class, like this:

def execute(self):
    self.em.persist(alias)
    try:
        self.em.flush()
    except DBALException as e:
        if e.previous.code != 23000:
            raise e
        self.reloadEM()
        self.e = e

        self.handleE()

handleE() would be implemented in subclasses of the class implementing execute() method, and it could access exception object, or not, depending on implementation.

Should I choose one of these ideas for dealing with code duplication? Which one is better? Do you suggest a better solution?

I was originally going to add this as a comment, but it works better as an answer.

Why don't you just have a variable among one of the method's arguments which determines whether to run the code for a custom or random alias by utilizing a single if statement?

For example:

def persistAlias(self, alias, custom_alias):
"""Please place relevant description here,
    The "custom_alias" argument determines whether to
    persist a custom or random alias."""
    try:
        self.em.persist(alias)
        self.em.flush()
    except DBALException as e:
        if e.previous.code != 23000:
            raise e
        self.reloadEM()

        if custom_alias:
            existing = self.findByNaturalKey(alias.name)
            if existing != alias:
                raise DuplicateNameException('The requested name is already taken', e)
        else:
            self.persistAlias(alias, 0)


CodeWars Solution to "Simple Elevator" I am new to programming (less than a year), and I would like to improve.

I solved a problem on CodeWars and copied both my solution and the top voted solution below. I listed specific questions after my solution.

I would like to know, what would be considered the better overall solution in a real production environment? Is abstracting the way I did better (even if I did not execute correctly)? Could someone provide advice to help me improve?

Description:

  There is a house with 4 levels. In that house there is an elevator.
  You can program this elevator to go up or down, depending on what
  button the user touches inside the elevator.

  levels can be only numbers: 0,1,2,3

  buttons can be strings: '0','1','2','3'

  possible return values are numbers: -3,-2,-1,0,1,2,3

  If the elevator is on the ground floor(0th level) and the user touches
  button '2' the elevator must go 2 levels up, so our function must
  return 2.

  If the elevator is on the 3rd level and the user touches button '0'
  the elevator must go 3 levels down, so our function must return -3.

  If the elevator is on the 2nd level, and the user touches button '2'
  the elevator must remain on the same level, so we return 0.

  We cannot endanger the lives of our passengers, so if we get erronous
  inputs, our elevator must remain on the same level.

  So for example:

  goto(2,'4') must return 0, because there is no button '4' in the    elevator.
  goto(4,'0') must return 0, because there is no level 4.
  goto(3,undefined) must return 0.
  goto(undefined,'2') must return 0.
  goto([],'2') must return 0 because the type of the input level is    array instead of a number.
  goto(3,{}) must return 0 because the type of the input button is    object instead of a number.

Top Voted Solution

def goto(level, button)
  return 0 unless (0..3).include?(level) && ('0'..'3').include?(button)
  button.to_i - level
end

My Solution

def goto(level, button)
  inputs_types_are_accepted = (level.is_a? Integer) && (button.is_a? String)
  if inputs_types_are_accepted
    current_floor, desired_floor = level.to_i, button.to_i
    if current_floor.between?(0, 3) && desired_floor.between?(0, 3)
      floor_change = desired_floor - current_floor
      return floor_change
    else
      return 0
    end
  else
    return 0
  end
end

With a method this small, is it correct to abstract the way I did?
If I change if current_floor.between?(0, 3) && desired_floor.between?(0, 3) to if (current_floor && desired_floor).between?(0, 3) then I failed some tests. Is there a clearer way to represent this?
Is there a way to remove one set of else return 0 end? I tried and failed tests.

Your solution looks correct, though it is a bit long.

One way to shorten it is to remove the elses:

def goto(level, button)
  inputs_types_are_accepted = (level.is_a? Integer) && (button.is_a? String)
  if inputs_types_are_accepted
    current_floor, desired_floor = level.to_i, button.to_i
    if current_floor.between?(0, 3) && desired_floor.between?(0, 3)
      floor_change = desired_floor - current_floor
      return floor_change
    end
  end
  # Don't move elevator if the input is wrong in any way
  0
end

You don't need to do level.to_i when you have already ascertained that level is an Integer. You can also eliminate the variables inputs_types_are_accepted and floor_change.

(current_floor && desired_floor) won't work.  In English, you can ask whether "the current floor and desired floor are both between 0 and 3", but you can't translate that literally into Ruby.  Since you want to perform two tests, you have to write it as two tests.  The way the && operator works is that it will return the left operand (current_floor) if it is considered true — and in Ruby, every integer is considered to be true.

One thing that I like about your solution and that I dislike about the "top-voted" solution is that the latter does not extend well to handle more than 10 floors.  Although the problem states that there are just 4 levels, but still, using ('0'..'3').include?(button) to validate the floor in the string domain rather than the integer domain feels like a hack to me.

Obviously, there are many possible formulations.  It's a new moon today, so I feel like writing it this way:

def goto(level, button)
  floors = (0..3)

  # Validation: don't move elevator on invalid input
  return 0 unless button.kind_of?(String) && floors === (dest = button.to_i)
  return 0 unless floors === level

  dest - level
end

The way you wrote your solution tends to lead to deeper nesting.  As a rule of thumb, it is preferable to return early on failure, since there are usually many ways to fail, but only one way to succeed.


Javascript Fibonacci with dynamic programming Trying to applying what seen on What Is Dynamic Programming and How To Use It (here: https://www.youtube.com/watch?v=vYquumk4nWw )
Obviuously this is the final code, after removing the recursion.
I thought it was a good idea to memoize just the latest two values instead of the whole sequence.
I could replace the array with two values and a temp one to make the shift but maybe it will affect readability.
What you think ?

fibonacci: function (n)
{
    if (n === 0 || n === 1) return 1;

    var array = [1, 1];

    for (var i = 2; i < n; i++) {
        array.push(array[0] + array[1]);
        array.shift();
    }

    return array[0] + array[1];
}

Your code will accomplish the task of returning the Nth Fibonacci number and will do it quite fast.   But you are not getting the point of the video, how to do Memoization.

To improve your code:

Defining your variables at the beginning of your function.
Indent your if block and surround with { }

fibonacci: function (n)  {
  var array = [1, 1]; // prevent variable  hoisting
  var i = 2;          // defining var at start of function
  if (n === 0 || n === 1) {
    return 1;  // indent if block and surround with {}
  }
  for (; i < n; i++) {
    array.push(array[0] + array[1]);
    array.shift();
  }

  return array[0] + array[1];
}

Memoization is more efficient by storing or memorizing past results to get faster future results the NEXT time you call the function.  If you call fibonacci(701) then fibonacci(700), you will calculate the results both times.  If  you memoize the function you will look up the result on the second call.  If you call fibonacci(702) you will look up the last two values to get the next result.

You have NO memoized values.

function fibonacci (n, pastResults)
{
  var memo = pastResults || [1, 1]; //if no pastResults, set default value
  var i = memo.length;
  if (i > n) { // we have result
    console.log('looking up value')
    return {  //return 2 values
        pastResults: memo,
        result: memo[n-1]
    };  // return it
  }
  for (; i < n; i++) {
    memo[i] = memo[i-1] + memo[i-2];
  }

  return {
    pastResults: memo,
    result: memo[n-1]
  };
}

var r = fibonacci(7)
console.log(r.result) //13
r = fibonacci(5, r.pastResults);  // looking up value
console.log(r.result) //5
console.log(r.pastResults) //[1, 1, 2, 3, 5, 8, 13], these will not be recalcuated
r = fibonacci(22, r.pastResults);
console.log(r.result) //17711

Here is a more eloquent, but harder to understand solution.

Note, in my 13+ years of JavaScript development, I've never used Memoization in production code.

References:

...coming soon

...Bock scope vs Function scope reference soon

https://github.com/dwyl/Javascript-the-Good-Parts-notes#memoization


Find numbers that are palindromic in consecutive number bases I want to generate numbers which are palindromic in three or more
  consecutive number bases in the most optimal, fastest way (up to some
  range). I do not count trivial one digit palindromes.

  (When I say 3 or more, I mean 3 and 4, as it is not known if a solution for 4 or more bases exists)

I'm basically generating palindromes in number base \$b\$, and then converting and checking whether it is also palindromic in \$b+1, b+2, \dots\$

Are there any ways to noticeably speed up my code?

# Converts any number n to any base b (*), Source: [1]
# https://stackoverflow.com/a/28666223/5821790
def numberToBase(n, b):
    if n == 0:
        return [0]
    digits = []
    while n:
        digits.append(int(n % b))
        n //= b
    return digits[::-1]

# Generates palindromes in base b (*), Source: [2]
# https://math.stackexchange.com/q/2494909
def palgen(b):
    i = 1
    while True:
        ii = b * i
        r = range(i, ii)
        for j in r:
            s = numberToBase(j, b)
            yield s + s[-2::-1]
        for j in r:
            s = numberToBase(j, b)
            yield s + s[::-1]
        i = ii

# Checks if the list is palindromic, Source: [3]
# https://stackoverflow.com/a/30340347/5821790
def isPalindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and isPalindrome(s[1:-1])

# converts number in base b (*) to integer
def listToInt(digitList, base):
    l = len(digitList)
    value = 0
    for i, val in enumerate(digitList):
        value += val*base**(l-i-1)
    return value

# returns current time
def getTime():
    return strftime("( %H:%M:%S )", gmtime())

###################################################################
# Searches for numbers palindromic in 3 or more consecutive bases #
###################################################################

from time import gmtime, strftime
from math import sqrt, floor

bound = 10**8                       # numbers up to
baseBound = floor(sqrt(bound))      # bases up to (bound, can be improved)
print(getTime(), "Starting with:" ,baseBound, bound)

for b in range(2, baseBound):
    for i, s in enumerate(palgen(b), 1):

        # convert palindrome s_b to integer x and check if out of bound
        x = listToInt(s, b)
        if (x > bound): break

        if (len(s) > 1): # one digit palindromes do not count (trivial)

            # checks if the palindrome x is also palindromic in more bases
            if (isPalindrome(numberToBase(x, b+1))):
                if (isPalindrome(numberToBase(x, b+2))):
                    print(getTime(), b, x, len(s))

                    if (isPalindrome(numberToBase(x, b+3))):
                        print(b, x, len(s), "*** AT LEAST FOUR IN A ROW ***")

  What are some things here that can be improved, and how, following
  good practice?

(Beside mathematical aspects which include the bound above which no more examples are found, the fact that only odd digit length palindromes form consecutive triples, and the facts that some examples follow a pattern that can be generated.)

Sources: [1] [2] [3]

Outputs: [10^9, ~ 3 hours: 1200 bases] and [10^12, ~ 3 hours: 100 bases]

A small performance improvement is possible in the listToInt function,
by using multiplications only instead of exponentiation
(which is Horner's method):

# converts number in base b list representation to integer
def listToInt(digitList, base):
    value = 0
    for val in digitList:
        value = value * base + val
    return value

On my computer this reduced the time to compute the results for
\$ b = 1270, \ldots, 1286 \$ from 130 to 101 seconds.


Middleware for sending PartialViews via email After all partial views are rendered and all styles are inlined my RESTful service is sending them via email. I implemented this feature with a MailerMiddleware.

This middleware dumps the response body and uses it as the body of the email. I pass the recipients and the subject via the HttpContext.Items property from the controller to the middleware. It uses the <system.net> element in the app.config for sending emails.

public class MailerMiddleware
{
    private readonly RequestDelegate _next;

    private readonly IEmailClient _emailClient;

    public MailerMiddleware(RequestDelegate next, IEmailClient emailClient)
    {
        _next = next;
        _emailClient = emailClient;
    }

    public async Task Invoke(HttpContext context)
    {
        if (context.Request.Method == "POST")
        {
            var bodyBackup = context.Response.Body;

            using (var memory = new MemoryStream())
            {
                context.Response.Body = memory;

                await _next(context);

                memory.Seek(0, SeekOrigin.Begin);
                using (var reader = new StreamReader(memory))
                {
                    var recipients = (string)context.Items["Recipients"];
                    var subject = (string)context.Items["Subject"];
                    var body = await reader.ReadToEndAsync();

                    memory.Seek(0, SeekOrigin.Begin);

                    var restoreBody = memory.CopyToAsync(bodyBackup);
                    var sendEmail = _emailClient.SendAsync(new Email<EmailSubject, EmailBody>
                    {
                        To = recipients,
                        Subject = new PlainTextSubject(subject),
                        Body = new ParialViewEmailBody(body),
                    });

                    await Task.WhenAll(restoreBody, sendEmail);
                }
            }
        }
        else
        {
            await _next(context);
        }
    }
}

Inside the action method:

[HttpPost("TestReport")]
[ActionName("TestReport")]
public IActionResult PostTestReport([FromBody] TestReportBody body)
{
    HttpContext.Items["Recipients"] = "example@email.com"; // todo use body
    HttpContext.Items["Subject"] = "Test email"; // todo use body
    return PartialView(body);
}

This solution is working great but is there anything that could still be done better?

Implementing Nkosi's suggestions was a great step forward. This way the client can also recieve the response. However, there was one more thing that could be greatly improved. While reading about Queued background tasks I realized that this is exactly what I need to speed up my middleware becasue sending emails made it hang for a short time. Queueing the task in a background service allows the middleware to return immediately and take its time for emails.

I adjusted the example code for my needs by not using a logger here. Instead I placed the Debug.Fail inside the catch clause (and changed a couple of names).

public interface IWorkItemQueue
{
    void Enqueue(Func<CancellationToken, Task> workItem);

    Task<Func<CancellationToken, Task>> DequeueAsync(CancellationToken cancellationToken);
}

public class WorkItemQueue : IWorkItemQueue
{
    private readonly ConcurrentQueue<Func<CancellationToken, Task>> _workItemQueue = new ConcurrentQueue<Func<CancellationToken, Task>>();

    private readonly SemaphoreSlim _signal = new SemaphoreSlim(0);

    public void Enqueue(Func<CancellationToken, Task> workItem)
    {
        if (workItem == null) { throw new ArgumentNullException(nameof(workItem)); }

        _workItemQueue.Enqueue(workItem);
        _signal.Release();
    }

    public async Task<Func<CancellationToken, Task>> DequeueAsync(CancellationToken cancellationToken)
    {
        await _signal.WaitAsync(cancellationToken);
        _workItemQueue.TryDequeue(out var workItem);

        return workItem;
    }
}

public class WorkItemQueueService : IHostedService
{
    private readonly IWorkItemQueue _workItemQueue;

    private readonly CancellationTokenSource _shutdown = new CancellationTokenSource();

    private Task _backgroundTask;

    public WorkItemQueueService(IWorkItemQueue workItemQueue)
    {
        _workItemQueue = workItemQueue;
    }

    #region IHostedService

    public Task StartAsync(CancellationToken cancellationToken)
    {
        // ReSharper disable once MethodSupportsCancellation - this task is not supposted to be cancelled until shutdown
        _backgroundTask = Task.Run(BackgroundProceessing);

        return Task.CompletedTask;
    }

    public Task StopAsync(CancellationToken cancellationToken)
    {
        _shutdown.Cancel();
        return Task.WhenAny(_backgroundTask, Task.Delay(Timeout.Infinite, cancellationToken));
    }

    #endregion

    public void Enqueue(Func<CancellationToken, Task> workItem)
    {
        _workItemQueue.Enqueue(workItem);
    }

    private async Task BackgroundProceessing()
    {
        while (!_shutdown.IsCancellationRequested)
        {
            var workItem = await _workItemQueue.DequeueAsync(_shutdown.Token);

            try
            {
                await workItem(_shutdown.Token);
            }
            catch (Exception)
            {
                Debug.Fail("Work item should handle its own exceptions.");
            }
        }
    }
}

The updated MailerMiddleware now enqueues tasks sending emails on that queue so that the service can handle them later and also handles its own exceptions.

public class MailerMiddleware
{
    private readonly RequestDelegate _next;

    private readonly ILogger _logger;

    private readonly IWorkItemQueue _workItemQueue;

    private readonly IEmailClient _emailClient;

    public MailerMiddleware(RequestDelegate next, ILoggerFactory loggerFactory, IWorkItemQueue workItemQueue, IEmailClient emailClient)
    {
        _next = next;
        _logger = loggerFactory.CreateLogger<MailerMiddleware>();
        _workItemQueue = workItemQueue;
        _emailClient = emailClient;
    }

    public async Task Invoke(HttpContext context)
    {
        var bodyBackup = context.Response.Body;

        using (var memory = new MemoryStream())
        {
            context.Response.Body = memory;

            await _next(context);

            memory.Seek(0, SeekOrigin.Begin);
            using (var reader = new StreamReader(memory))
            {
                var body = await reader.ReadToEndAsync();

                var email = context.Email();
                if (!(email.To is null || email.Subject is null))
                {
                    _workItemQueue.Enqueue(async cancellationToken =>
                    {
                        try
                        {
                            await _emailClient.SendAsync(new Email<EmailSubject, EmailBody>
                            {
                                To = email.To,
                                Subject = new PlainTextSubject(email.Subject),
                                Body = new ParialViewEmailBody(body),
                            });
                        }
                        catch (Exception ex)
                        {
                            _logger.Log(Abstraction.Layer.Network().Action().Failed(nameof(IEmailClient.SendAsync)), ex);
                        }
                    });
                }

                // Restore Response.Body
                memory.Seek(0, SeekOrigin.Begin);
                await memory.CopyToAsync(bodyBackup);
                context.Response.Body = bodyBackup;
            }
        }
    }

    private class ParialViewEmailBody : EmailBody
    {
        private readonly string _body;

        public ParialViewEmailBody(string body)
        {
            _body = body;
            IsHtml = true;
            Encoding = System.Text.Encoding.UTF8;
        }
        public override string ToString()
        {
            return _body;
        }
    }
}

ASP.NET-Core is really cool ;-)


Python program to get the longest substring of the same character Given a word the program outputs the length of the longest substring with the same letters. For example:

long_repeat('sdsffffse') == 4
long_repeat('ddvvrwwwrggg') == 3
long_repeat('abababaab') == 2
long_repeat('') == 0

The code is:

def long_repeat(line):

    substrings = []
    current_substring = ""
    for i, letter in enumerate(line):
        if i == 0:
            current_substring = letter
        else:
            if letter == current_substring[len(current_substring) - 1]:
                current_substring += letter
                if(i == len(line)- 1):
                    substrings.append(current_substring)
            else:
                substrings.append(current_substring)
                current_substring = letter

    lengths = []
    for substring in substrings:
        lengths.append(len(substring))

    if len(lengths) > 0:
        return  max(lengths)
    else:
        return 0

What could be improved?

I really like @Justin's answer, but I'm new here so I unfortunately cannot comment or upvote yet. So instead I'll take this opportunity to detail his answer in relation to your question.

The first thing to note, the methodologies of your (@enoy) solution and @Justin's is entirely different. Your solution is recreating the longest substring of the given string, then returning the length of the recreation. @Justin's solution is using simple math. To lay out the steps:

Create a beginning index, start at 0.
Traverse from the beginning index until the current letter and the previous letter are no longer the same. Record the index of the last letter that was repeating as an end index.
Subtract the two indexes
store the length in a variable, maybe called longest_length.
replace the beginning index with the end index + 1 (plus one because you want the rest of the input string and none of the previous substring)
repeat steps 2 and 3.
store the max of the longest_length and the length that was just found.
keep repeating 5 - 7 until the end of the input string
return longest_length

So with the steps lain out and clear, to answer your question:

  What could be improved?

If all you care about is the length of the longest substring, there shouldn't be a reason for you to recreate the substring in order to find its length. In terms of complexity, your space complexity is broken down like this:

substrings = [] - Since you're simply splitting the input string into substrings and storing them all into an array, this will always have a space complexity of \$n\$, where \$n\$ is the length of the input string.
current_substring = "" - If the entire input string is repeating, this can potentially be as large as \$n\$, where \$n\$ is the length of the input string.
lengths = [] - If the entire input string does not have a single repeating substring, this can potentially be as large as \$n\$, where \$n\$ is the length of the input string.

So all in all, you have a big O space complexity of \$O(3n)\$ or \$O(n)\$ (for something small like this I prefer not to simplify constants).

Where as @Justin's solution breaks down as so:

begin_index - Only stores a single value at any given time.
end_index - Only stores a single value at any given time.
longest_length - Only stores a single value at any given time.

So you can see how much smaller this is already, and in terms of big O space complexity, it's \$O(3)\$ or simplifies to \$O(1)\$.

All that was space complexity though, as for time complexity:

Let's start with your code breakdown again:

You traverse the input string once, to split each substring and record their lengths, so that time complexity is \$n\$, where \$n\$ is the length of the input string.
You then have to traverse your array lengths, and find the max using the max function, and if there's no repeating substring, that can potentially be \$n\$, where \$n\$ is the length of the input string.

So all in all, the time complexity is \$O(2n)\$

For @Justin's:

Traverse the list once, checking the max length of each substring as they're built so that's \$n\$, where \$n\$ is the length of the input string.

It's unavoidable, traversing the list at least once when doing anything involving comparisons, but you can see how work could have been combined into one loop, rather than two separate ones here.

And on closing notes, @Justin's solution can be easily adapted to store the substring simply with a variable named longest_substring = input_string[begin_index:end_index] if the longest_length variable changes. This is much smaller space than having an array of all substrings.

Here is @Justin's answer I was talking about (which got deleted) -

# Function to return the ending index for the
# largest valid subsring starting from index i
def end_of_uniform_substring(string, n, i):
    i += 1
    while (i < n):
        current = string[i]
        previous = string[i - 1]
        #if the current character in the string
        #is equal to the previous character
        if (current == previous):
            i += 1
        else:
            break
    return i - 1

# Function to return the length of the
# longest substring of consecutive
# repeating letters in string
def largest_substring(string, n):
    length = 0
    i = 0
    while (i < n):
        # Valid substring exists from
        # index i to end
        end = end_of_uniform_substring(string, n, i)
        # Update the length
        length = max(end - i + 1, length)
        i = end + 1
    return length

Hope this helps!


Formatting MMyyyy to MMyy The following is my sample code:

String month = "09";

String year = "2014";

String monthYear = "092014";

The monthYear format is MMyyyy, I wish to format it to become MMyy. Thus, I am doing it as follows:

Method 1:

final SimpleDateFormat oriMonthYear = new SimpleDateFormat( "MMyyyy" );
final SimpleDateFormat changeMonthYear = new SimpleDateFormat( "MMyy" );

String newMonthYear = changeMonthYear.format( oriMonthYear.parse( month + year) );

This give me correct output, but I am not sure am I doing it by stupid way or not. I believe it should be another best practice and smart to way to do it.

Use Java's THreadLocal type to wrap your SimpleDateFormat objects.

ThreadLocal<SimpleDateFormat> oriFormatHolder = new ThreadLocal<SimpleDateFormat>() {

    @Override
    protected SimpleDateFormat initialValue() {
        return new SimpleDateFormat("MMyyyy");
    }
};

final SimpleDateFormat oriMonthYear = oriFormatHolder.get();

The reason for this is because SimpleDateFormat is not thread safe.

  Date formats are not synchronized. It is recommended to create separate format instances for each thread. If multiple threads access a format concurrently, it must be synchronized externally.

Read more here

I actually ran into this problem.  In a multi threaded env we were sharing a SimpleDateFormat object across many threads and started getting bad results.  By wrapping it with ThreadLocal the problem went away.


Plot timings for a range of inputs When writing Code Review answers, it becomes often necessary to measure how long the modified code takes vs how long the OP's code takes. I needed a nice way to visualize this as a function of the input, so I cobbled together the following script.

The plot_time function takes a single function (of a single variable atm) and an iterable of inputs, performs multiple timings per input and finally plots it as an errorbar plot using matplotlib (although usually the errorbars are too small to be seen).

The plot_times function loops over an iterable of functions and adds some nice labels and a legend (containing the __name__ of each function tested).

from functools import partial
import timeit
import numpy as np
from matplotlib import pyplot

def plot_time(func, inputs, repeats, n_tests):
    """
    Run timer and plot time complexity of `func` using the iterable `inputs`.

    Run the function `n_tests` times per `repeats`.
    """
    x, y, yerr = [], [], []
    for i in inputs:
        timer = timeit.Timer(partial(func, i))
        t = timer.repeat(repeat=repeats, number=n_tests)
        x.append(i)
        y.append(np.mean(t))
        yerr.append(np.std(t) / np.sqrt(len(t)))
    pyplot.errorbar(x, y, yerr=yerr, fmt='-o', label=func.__name__)

def plot_times(functions, inputs, repeats=3, n_tests=1, file_name=""):
    """
    Run timer and plot time complexity of all `functions`,
    using the iterable `inputs`.

    Run the functions `n_tests` times per `repeats`.

    Adds a legend containing the labels added by `plot_time`.
    """
    for func in functions:
        plot_time(func, inputs, repeats, n_tests)
    pyplot.legend()
    pyplot.xlabel("Input")
    pyplot.ylabel("Time [s]")
    if not file_name:
        pyplot.show()
    else:
        pyplot.savefig(file_name)

if __name__ == "__main__":
    import math
    import time

    scale = 100.

    def o_n(n):
        time.sleep(n / scale)

    def o_n2(n):
        time.sleep(n**2 / scale)

    def o_log(n):
        time.sleep(math.log(n + 1) / scale)

    def o_nlog(n):
        time.sleep(n * math.log(n + 1) / scale)

    def o_exp(n):
        time.sleep((math.exp(n) - 1) / scale)

    plot_times([o_n, o_n2, o_log, o_nlog, o_exp],
               np.linspace(0, 1.1, num=10), repeats=3)

Saving the figure can either be done manually, or by passing a file name.

The test code, that defines some functions for the most common complexity classes (\$\mathcal{O}(n), \mathcal{O}(n^2), \mathcal{O}(\log n), \mathcal{O}(n \log n), \mathcal{O}(\exp n)\$), produces this graphical output:

Any thoughts or recommendations are welcome. Especially I don't think there is a nice way around (implicitly) using global variables here (when generating a new graph matplotlib automatically adds it to the current figure).

matplotlib adding stuff to the current figure is because you are not using the OO-interface. It is slightly clunkier, but allows way more freedom

In my view, you are mixing several things up. I would seperate the generation of the timings, the aggregation of these results and the plotting. In this way, if you want to change to another plotting library (bokeh, seaborn,...) you only need to adapt or add 1 method, and not refactor the whole thing.

imports

import pandas as pd
from functools import partial
import timeit
import numpy as np
import matplotlib.pyplot as plt

tying it together

def plot_times(functions, inputs, repeats=3, n_tests=1, file_name=""):
    timings = get_timings(functions, inputs, repeats=3, n_tests=1)
    results = aggregate_results(timings)
    fig, ax = plot_results(results)

    return fig, ax, results

This should be self-explanatory. first you generate the timings, then you aggregate the results and finally you plot the aggregations. In this way, you can test each part individually. This function returns the actual generated figure, the plot axes and the results-DataFrame so you can inspect them later on if needed. In your __main__ you can save or show the fig

get_timings

def get_timings(functions, inputs, repeats, n_tests):
    for func in functions:
        result = pd.DataFrame(index = inputs, columns = range(repeats),
            data=(timeit.Timer(partial(func, i)).repeat(repeat=repeats, number=n_tests) for i in inputs))
        yield func, result

The only change I made here is to save the individual data of one function in a pandas.DataFrame for easy aggregation afterwards. The yield makes sure these timings are only calculated when they are needed

aggregate_results

def aggregate_results(timings):
    empty_multiindex = pd.MultiIndex(levels=[[],[]], labels=[[],[]], names=['func', 'result'])
    aggregated_results = pd.DataFrame(columns=empty_multiindex)

    for func, timing in timings:
        for measurement in timing:
            aggregated_results[func.__name__, measurement] = timing[measurement]
        aggregated_results[func.__name__, 'avg'] = timing.mean(axis=1)
        aggregated_results[func.__name__, 'yerr'] = timing.std(axis=1)

    return aggregated_results

This method makes 1 big DataFrame with a MultiIndex in the columns whose first level is the function, the second label is the result. Each individual timing is saved in this DataFrame, and the average and standard deviation calculated

plot_results

def plot_results(results):
    fig, ax = plt.subplots()
    x = results.index
    for func in results.columns.levels[0]:
        y = results[func, 'avg']
        yerr = results[func, 'yerr']
        ax.errorbar(x, y, yerr=yerr, fmt='-o', label=func)

    ax.set_xlabel('Input')
    ax.set_ylabel('Time [s]')
    ax.legend()
    return fig, ax

This simply generates a plot for every func, adds the labels and the legend


Methods creating transform functionality on Collections I have written a few simple-to-be-used methods in Java 8, and am wondering what could be improved upon those:

public static <E, R, C extends Collection<? extends R>> C transform(final Collection<E> collection, final Function<? super E, ? extends R> mapper) {
    try {
        Objects.requireNonNull(collection);
        Objects.requireNonNull(mapper);
        Class<? extends Collection> clazz = collection.getClass();
        @SuppressWarnings("unchecked") Collection<Object> returnCollection = clazz.newInstance();
        collection.stream().map(mapper).forEach(returnCollection::add);
        @SuppressWarnings("unchecked") C genericReturnCollection = (C)returnCollection;
        return genericReturnCollection;
    } catch (InstantiationException | IllegalAccessException ex) {
        throw new RuntimeException(ex);
    }
}

public static <E, R, C extends Collection<R>> C transform(final Collection<E> collection, final Function<? super E, ? extends R> mapper, final Supplier<C> collectionSupplier) {
    Objects.requireNonNull(collection);
    Objects.requireNonNull(mapper);
    Objects.requireNonNull(collectionSupplier);
    return collection.stream().map(mapper).collect(Collectors.toCollection(collectionSupplier));
}

Their purpose is to provide similar functionality as the List.replaceAll() method, but then allowing that the mapped type differs from the original type. Hence it is something that should be in a static factory class, as it will always need to create a new collection.

Some example code:

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(5);
linkedList.add(10);
linkedList.add(15);
LinkedList<String> resultList = transform(linkedList, i -> (i + 1) + "-" + i);

and

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(5);
linkedList.add(10);
linkedList.add(15);
LinkedList<String> resultList = transform(linkedList, i -> (i + 1) + "-" + i, LinkedList::new);

Both have as output:

  6-5
  11-10
  16-15

I am aware that the transform with a Supplier<C> as argument is obviously much nicer, however for convienience the single-argument version with only a function is much better.

I see the Supplier-less option as being a very broken one. Consider the following code:

transform(linkedList.sublist(0, linkedList.size() / 2), i -> (i + 1) + "-" + i);

Or, any of the other collections that do not have a meaningful default constructor:

transform(Arrays.asList(argv), a -> a.toLowerCase());

The code will cause more headaches than the small requirement to add the supplier will require.

The Generics of the mapping are also broken when there is no supplier, because the actual type of the return list should be more specific....

Lose the first static method.

The second method looks fine, except for the ordering of the arguments. I would make the supplier the middle, not the last argument (and I would introduce some newlines to make it not-so-long-of-a-line):

public static <E, R, C extends Collection<R>> C transform(
          final Collection<E> collection,
          final Supplier<C> collectionSupplier,
          final Function<? super E, ? extends R> mapper) {
    ....
}

The logical reading of that order is better, take this collection, map to that collection, and use this function to do it..... maybe it is not such a big deal...?

The use-case seems to read better for me:

List<String> lcargs = transform(Arrays.asList(args), ArrayList::new, a -> a.toLowerCase());


Is it a good practice to use only one database instance? I want to ask whether is good practice to have single instance of database connection or declare new every times when we needed? I have this two designs shown in below:

This is database class:

<?php
class Database extends PDO {
    //Variable declaration
    private $host = "localhost";
    private $passwd = "";
    private $username = "root";
    private $dbname = "";

    //Connect to DB when the class construct
    public function __construct($host=NULL, $dbname=NULL, $username=NULL, $passwd=NULL) {
        if(isset($host) && !empty($host)) {
            $this->host = $host;
        }

        if(isset($dbname) && !empty($dbname)) {
            $this->dbname = $dbname;
        }

        if(isset($username) && !empty($username)) {
            $this->username = $username;
        }

        if(isset($passwd) && !empty($passwd)) {
            $this->passwd = $passwd;
        }

        parent::__construct("mysql:dbname=$this->dbname;host=$this->host", $this->username, $this->passwd, NULL);
        parent::setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
        parent::setAttribute(PDO::ATTR_EMULATE_PREPARES, false);
    }

}
?>

Method 1: Dependency Injection

<?php
class User {
    private $db;

    public function __construct(Database $db) {
        $this->db = $db;
    }

    //Some update and insert below here
}

class Employee {
    private $db;

    public function __construct(Database $db) {
        $this->db = $db;
    }

    //Some update and insert below here
}
?>

So, I will do this when I want to use the classes:

<?php
    $db = new Database();

    $user = new User($db);
    $user->update($id,$data);

    $emp = new Employee($db);
    $emp->delete($id);
?>

or the other ways?

Method 2:

<?php
class User {
    private $db;

    public function __construct() {
        $this->db = new Database();
    }

    //Some update and insert below here
}

class Employee {
    private $db;

    public function __construct() {
        $this->db = new Database();
    }

    //Some update and insert below here
}
?>

and when I want to use it I will:

<?php
    $user = new User();
    $user->update($id,$data);

    $emp = new Employee();
    $emp->delete($id);
?>

Which method is preferable or better?  Offer an explanation if possible.

In this situation, I would say to prefer dependency injection. The reasons being:

You may not only ever run your code against a single database. For example, if your project grows large, you may have separate databases for different regions about the world (North America, Europe, etc). You could also easily have a test database, or a stable-test and an experimental-test, etc., etc. All of this can be controlled by configuration. Of course, you could put this configuration-based logic inside your Database class, but..
You may want different types of databases. Right now you might be using MySQL; later you may use Oracle, or PostgreSQL, or an in-memory database, or a mock database that has no backing store. Using dependency injection lets you very easily switch between these, provided you adhere to the same interface for all of them. You may even start in one region where MySQL is readily available, then expand to another where you can only get Oracle hosts. Changing types is useful for easily changing technologies later, but also because..
Using dependency injection makes it easier to test. You can test against an in-memory database for your unit tests, and against an actual remote database during integration testing.

Of course, dependency injection isn't a cure-all and has its own problems, such as:

Dependency injection is infectious. Somebody somewhere has to know how to construct your object. If your object has its dependencies injected, then it has to know how to construct the dependencies. If it doesn't know that, then the next level up has to know, or the next level from there, or.. etc, etc. The result of this is that..
Your classes become more tightly coupled. Some of your classes become aware of the dependencies of their other classes, by virtue of having to inject their dependencies. A good dependency injection framework can help with this. I don't use PHP much so I'm not aware of any.

This is Code Review, of course, and I'd be remiss if I didn't comment on your code itself:

<?php
    $user = new User();
    $user->update($id,$data);

    $emp = new Employee();
    $emp->delete($id);
?>

To me (admittedly a non-PHP guy) this is an extremely strange pattern. A User and an Employee would seem to be model classes, but here you have them making database calls - you're mixing concerns for these objects. This is a great situation to use the data access object, or DAO, pattern:

<?php
    class User {
        private $data;

        public function __construct() {
            $data = "some_data";
        }
    }

    interface UserDao {
        public function saveUser(User $user);
    }

    // A DAO implementation which knows how to communicate using
    // PDO objects. Can be injected with a PDO object configured
    // to connect to any host, DBMS, etc.
    class PDOUserDao implements UserDao {
        private $pdo;

        public function __construct(PDO $pdo) {
            $this->pdo = $pdo;
        }

        public function saveUser(User $user) {
            // insert pdo insert/update logic here
        }
    }

    class InMemoryUserDao implements UserDao {
        // in-memory implementation here..
    }
?>


Improvements for a C getline implementation I wrote a function in C that reads an entire line from a stream into a dynamically allocated buffer. What would you suggest I should do to improve its performance? Also, are there any errors that could occur and are not handled?
This is the code:
#define ERRALLOC(ptr)                                        \
if (ptr == NULL) {                                           \
    printf("Unable to allocate memory for %s", #ptr);        \
    exit(1);                                                 \
}

#define PACK_SIZE 512

size_t readLine(FILE *istream, char **line_buffer, size_t *bufsize) {
    size_t line_size = 0;
    int eol_flag = 0;
    char temp_buffer[PACK_SIZE];
    while (fgets(temp_buffer, PACK_SIZE, istream) != NULL) {
        size_t temp_len = strlen(temp_buffer);
        line_size += temp_len;

        if (line_size+1 > *bufsize) {
            *bufsize = line_size+1;
            *line_buffer = realloc(*line_buffer, *bufsize * sizeof(char));
            ERRALLOC(*line_buffer)
        }

        if (temp_buffer[ temp_len - 1 ] == '\n') {
            temp_buffer[ temp_len - 1 ] = '\0';
            eol_flag = 1;
        }
        strcpy(*line_buffer + (line_size-temp_len), temp_buffer);

        if (eol_flag) break;
    }

    return line_size;
}

Overall, it's a lot of effort (perhaps not in the right place) for one line. Textual data typically has lines that are very short, on the order of 80 bytes. If you're so deeply concerned about performance, you need to back out of this function and look at the I/O pattern of the calling program for more context. You'll very likely find that it's more efficient to have a buffer much larger than your current PACK_SIZE, perhaps 4MB. Read the file into it one such chunk at a time with fread, not fgets; then iterate through to find and split on newlines. Roughly,

Allocate a large buffer
fread as much as possible
memchr your way to a newline
Set that newline to '\0'
Consume the line
Repeat 3-5 until you're at the end of the buffer
If there is a partial line segment at the end, then memcpy the segment to the beginning of the buffer and plan for the next fread to use a buffer write position that starts after the end of the segment
Repeat until end of file

The principle to heed here is that I/O (particularly disk I/O) is expensive, and frequent calls to the I/O layer are expensive even when cached at the operating system level. Doing as much in RAM as possible is strongly preferred.
If you want a convenience interface, then consider accepting a FILE* and a callback function, making the buffer locally rather than accepting it, and invoking the callback for each line when found.


Find the non repeating number in the integer array The program finds the non repeated number in a int array. I am using a count for the duplicates and making a Numcounts[] to store the count values. I am assuming the array is sorted. Then I can check the Numcounts[] for 1, and that would be the non-repeating number. The complexity is \$O(n^2)\$.

Can you tell me how to do the same thing using hashmaps? I haven't used hashmaps and I know the complexity can be reduced to \$O(n))\$ using them.

#include<stdafx.h>
#include<stdio.h>

int main()
{
    int n=6;
    int * Numcounts = new int[n];
    int count = 0;
    int a[6] = {1,1,1,2,2,3}; // sort the array before proceeding.Because in the else part count is set to zero.
    //If the array is unsorted then count will be reset in middle and will not retain the previous count.
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i]==a[j])
            {
                count = count+1;
                Numcounts[i] = count;
            }
            else{
                count = 0;
            }
        }
    }
}

If the array is sorted you do not need hashmaps to achieve O(n). If you have a random/unsorted array you can use hashmaps to achieve the purpose, see Paulo's answer for that. Note that sorting requires O(n log(n)).

If you want to know how often each integer is in the original collection you will also need hashmaps, but if you only want to know a nonduplicate number in a sorted array the following code will work:

// N is the number of ints in sorted
int nonduplicate(int sorted[], const int N){
    //To prevent segfaulting when N=1
    if(N==1){ return sorted[0]; };

    for(int i=0;i < N-1;i++){
        if(sorted[i] == sorted[i+1]){
            // Next number in collection is the same so the current number is not unique
            // Set i to the first location of the next different number
            do{
                i++;
            }while(i < N-1 && sorted[i] == sorted[i+1]);
        }else{
            // The next number is different so the current is unique
            return sorted[i];
        }
    }
    // Is the last number unique?
    if(sorted[N-1] != sorted[N-2]){
        return sorted[N-1];
    }
    // No unique numbers
    return -1;    // Or some other value you reserve for it
}

Note that this code is faster because it doesn't have the overhead of a hashmap and may stop before traversing the whole array, but does have the same big-O limit.


C++ Console Menu User Validation So I am trying to implement a menu in a program I am writing. My goal is to have zero errors when collecting user input. So I thought the best way to validate was to capture the input as a string and then test against it and prompt for input again until it is valid.

As far as I can tell, my code works as I want it to. BUT, is this the best way to go about this? Almost every example online uses char or int for the input, are there benefits to this?. I feel like I made it more complex than it needed to be. As a beginner, any suggestions would be appreciated.

#include <iostream>
#include <string>
using namespace std;

string GetInput()
{
    string s = "";

    cout << ">> ";
    getline(cin, s);

    return s;
}
void mainMenu() {

    cout << "Select an option" << endl;
    cout << "1. Add Entry" << endl;
    cout << "2. Edit Entry" << endl;
    cout << "Q. Quit" << endl;

    string input = GetInput();

    while (!(input.find_first_not_of("12qQ") == string::npos) || input.empty())
    {
        input = GetInput();
    }

    if (input == "1") {
        cout << "Add Entry" << endl;
        //AddEntry();
    }

    else if (input == "2") {
        cout << "Edit Entry" << endl;
    }

    else {
        cout << "Quit" << endl;
    }

}

int main() {

    cout << "===================================================" << endl;
    cout << "|                 Secure Database                 |" << endl;
    cout << "===================================================" << endl << endl;

    mainMenu();

    return 0;
}

Let me collect a couple of thoughts here.

When the input validation is not successful, users immediately get the ">>" prompt without any notification that their input wasn't accepted. Maybe add a hint that no action was performed?

  Almost every example online uses char or int for the input, are there benefits to this?

The input that you ask for so far is one out of 1, 2, q or Q, i.e., 4 entries from the ASCII table. Using a single char for this is a reasonable choice, but might be limiting when the program grows. Maybe you want to ask users for paths, tokens, anything with more than one character? Having setup everything with std::string in the first place might be the more pragmatic approach, as it simplifies things (e.g. one function for both the one-char-only and multi-char-input).
In GetInput(), you are doing more work than necessary:

string s = "";

You want an empty string instance to be passed to std::getline, then default-construct it with std::string s; instead of initializing it with an empty string literal (remember that the type of "" is const char[1], std::string s = ""; is not a no-op), see also Item 4 in Scott Meyer's Effective C++.
You flush the standard output a lot of time, when you actually just want a newline \n to be printed out. See this thread for more details.
This is in my opinion the most severe point: the menu logic doesn't scale well. What do you have to change when you need to add a third option? You need to adjust the initial check and you need another else if branch:

input.find_first_not_of("123qQ") // ...

/* ... */

else if (input == "3") { /* ... */ }

The number of options to make this approach unreadable and hard to maintain is quite low, so think about an alternative here. To give you an idea of how this
could be improved:

struct MenuAction {
   std::string description;
   std::function<void()> action;
};

static const std::map<std::string, MenuAction> actionTable {
   {"1", { "Add entry", [](){ std::cout << "Add entry" << "\n";  }}},
   {"2", { "Edit entry", [](){ std::cout << "Edit entry" << "\n";  }}},
   {"q", { "Quit", [](){ std::cout << "Quit" << "\n";  }}}
};

Then, you can display available options (assuming C++17 is available) via

for (const auto& [key, value] : actionTable)
   std::cout << key << ". " << value.description << "\n";

and the original if-else if-else logic boils down to

while (actionTable.count(input) == 0)
   input = GetInput();

actionTable.at(input).action();

Maintaining user options is now identical to maintaining the std::map instance.
Minor detail; you naming scheme doesn't seem to be consistent. GetInput() starts with an upper case letter, while mainMenu() with a lower case letter.
This is very rare, but you could use a do-while construct here to reduce the number of calls to GetInput():

 std::string input;

 do
    input = GetInput();
 while (actionTable.count(input) == 0);

It seems at least debatable to me whether this is worth it, but as it crossed my mind, I couldn't resist suggesting it :)


Utilities for various builtins #1 This is an iterative review. The next iteration is located here: Utilities for Various Builtins #2
This code puts several builtins (And a few non-builtins) into the base classes.

  const XtraUtils = {};
  class Utility {
    constructor(ofWhat){
      this.utils = {};
      this.aidsIn = ofWhat;
    }
    activate() {
      for (var x in this.utils) {
        window[this.aidsIn].prototype[x] = this.utils[x];
      }
    }
    addUtil(util, name) {
      this.utils[name] = util;
    }
  };
  XtraUtils.Number = new Utility("Number");
  XtraUtils.String = new Utility("String");
  XtraUtils.Array = new Utility("Array");
  XtraUtils.Number.addUtil(function(in_min, in_max, out_min, out_max) {
    return (this - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
  }, "map");
  XtraUtils.Number.addUtil(function(inputBase = 10, outputBase = 10){parseInt(this, inputBase).toString(outputBase)}, "toBaseN");
  XtraUtils.Number.addUtil(function(n){
    return Math.pow(this, n);
  }, "toTheNthPower");
  XtraUtils.Number.addUtil(function(){
    return Math.ceil(this);
  }, "ceil");
  XtraUtils.Number.addUtil(function(){
    return Math.floor(this);
  }, "floor");
  XtraUtils.Number.addUtil(function() {
    return Math.sqrt(this);
  }, "sqrt");
  XtraUtils.Array.addUtil(function() {
    const i = this.map(function(item) {
      return typeof item == "number";
    });
    const isAllNums = i.indexOf(false) == -1;
    if (!isAllNums) {
      throw "The array must be all numbers.";
      return;
    };
    let max = 0;
    let isFirst = true;
    this.forEach(function(item) {
      if (isFirst || item > max) {
        max = item;
        isFirst = false;
      };
    });
    return max;
  }, "max");
  XtraUtils.Array.addUtil(function() {
    const i = this.map(function(item) {
      return typeof item == "number";
    });
    const isAllNums = i.indexOf(false) == -1;
    if (!isAllNums) {
      throw "The array must be all numbers.";
      return;
    };
    let min = 0;
    let isFirst = true;
    this.forEach(function(item) {
      if (isFirst || item < min) {
        min = item;
        isFirst = false;
      };
    });
    return min;
  }, "min");
  XtraUtils.Array.addUtil(function() {
    let i = this.map(function(item) {
      return typeof item == "number";
    });
    const isAllNums = i.indexOf(false) == -1;
    if (!isAllNums) {
      throw "The array must be all numbers.";
      return;
    };
    let total = 0;
    var isFirst = true;
    this.forEach(function(item) {
      total += item;
    });
    const mean = total / this.length;
    return mean;
  }, "mean");

Feel free to use the utils if you like.

For the most part, this looks good to me. Your api is clear and I really like that you have to activate the utility before the prototype is modified. However, there's always room for improvement :)

You provide the Utility.activate function, it would be useful to also have a Utility.deactivate function.
addUtil taking name as the second parameter seems odd to me. On a longer utility method like min, max or mean it was not immediately obvious to me what the function did - I had to skip to the end or figure it out from the code.
Be consistent with your naming scheme. In most of the code you use camelCase, but in the parameters for Number.map you use snake_case.
Why is the inputBase the first parameter in toBaseN? Presumably, if I have a number it is already in base 10. This function will also have issues if you use 0.0000001, plug 0.0000001.toString() into your console and you will get 1e-7 instead of what you expected.
toTheNthPower is just pow on the Math object. I would use the same convention here.
Don't throw strings. Throw a new Error(str) or just Error(str). This makes it much easier for error tracking systems to give you helpful stack traces.
Returning 0 as a signal number if the array is empty is not a good idea. 0 could exist in an array. I'd recommend using the convention of Math.max and Math.min and returning -Infinity and Infinity respectively.
Mapping over the array to create an array of booleans is very inefficient. If I create an array with ['hi'].concat([1].repeat(1e9)) you still go through every single item in the array. Instead of doing this, bail out as soon as you hit a failing condition. [].every and [].some can be of help here. const isAllNums = this.every(item => typeof item == 'number')
Speaking of Math.max and Math.min, you should use them! You can use Math.max.apply(Math, this) or if your environment supports the spread operator, you can just use Math.max(...this). If desired, you can check if this returns NaN and throw an error to maintain the current API instead of returning NaN for arrays with non-numbers.
Don't use for..in loops to loop over keys of objects. Either use for (const key of Object.keys(this.utils)) or Object.keys(this.utils).forEach(. This will help you avoid problems with built in values like toString.
In this case, it is probably a better fit to use a Map instead of a plain object to hold the utils.
What happens if you want to use these utils in Node? They break - window is not defined. This might not be a consideration, but quite a lot of code runs on Node now.
What happens if you want to define utilities for an object which is not exposed on the global? Instead of passing a string into the constructor of Utility, I'd recommend passing in an object instead. new Utility(Array)
Instead of looping through the array multiple times for mean, I'd recommend checking each element of the array as you add it to the sum. Maintaining your current API, here's how I'd implement that function.

function mean(arr) {
  return arr.reduce((total, item) => {
    if (typeof item !== 'number') {
      throw new Error("The array must be all numbers.")
    }
    return total + item
  }, 0) / arr.length
}


Swift: extract string with regex and range In Swift, I have a string like this

  http://mnc-hdqp.oss-cn-shanghai.aliyuncs.com/user%2Fheat%2Fdefault.jpg?Signature=2BI%2BauSvy&Expires=1568682491&OSSAccessKeyId=LTAIQ8Lif1HHVkXd

Need to extract 2BI%2BauSvy, the value of key Signature

here is code: regex match, then use range to subtract the key ahead.

let key = "Signature"
let signatures = icon.matches(for: "\(key)[^&]+")
guard !signatures.isEmpty else{
     return
}
if let range = signatures[0].range(of: "\(key)="){
      let signature = String(signatures[0][range.upperBound...])
      print(signature)
}

Any way to implement it conveniently?

PS: func matches(for:)

extension String{

    func matches(for regex: String) -> [String] {

        do {
            let regex = try NSRegularExpression(pattern: regex)
            let results = regex.matches(in: self,
                                        range: NSRange(self.startIndex..., in: self))
            return results.map {
                String(self[Range($0.range, in: self)!])
            }
        } catch let error {
            print("invalid regex: \(error.localizedDescription)")
            return []
        }
    }

Simplify the code

The guard statement and the following if let can be combined into a single statement:

let key = "Signature"
let signatures = iconURL.matches(for: "\(key)[^&]+")
if let firstSignature = signatures.first,
    let range = firstSignature.range(of: "\(key)=") {
    let signature = String(firstSignature[range.upperBound...])
    print(signature)
}

Improve the regex pattern

Your method is fragile because the key "Signature" may occur in the host part of the URL. Here is an example where it fails:

let iconURL = "http://Signature.com/?a=b&Signature=sig&c=d"

As mentioned in the comments, you can use a positive look-behind which includes the "=" character:

let key = "Signature"
let signatures = iconURL.matches(for: "(?<=\(key)=)[^&]+")
if let signature = signatures.first {
    print(signature)
}

However, this would still fail for

let iconURL = "http://foo.com/Signature=bar?a=b&Signature=sig&c=d"

because the "=" character is valid in the path part of an URL.

You also must ensure that the key does not contain any characters which have a special meaning in a regex pattern.

And now for something completely different

The Foundation framework has a dedicated URLComponents type to parse URLs into their parts. It does exactly what you need here:

let iconURL = "http://Signature.com/Signature=foo?a=b&Signature=2BI%2BauSvy&c=d"
let key = "Signature"

if let urlComponents = URLComponents(string: iconURL),
    let queryItems = urlComponents.queryItems {
    for queryItem in queryItems where queryItem.name == key {
        if let value = queryItem.value {
            print(value) // 2BI+auSvy
        }
    }
}

In addition, the value is already percent-decoded.


Faster way to group email-date pairs by date without many nested for loops? Given list of pairs (email-date):

['ann_osman@mail.com', '2 august 1976'],
['jz_neo@mail.com', '3 august 2001'],
['keyes_signak@mail.com', '2 october 2001'],
['cassadi_algazi@hotmail.com', '2 october 2001'],
['karmen_algazi@aol.com', '2 august 2001']]

I need to turn it into dictionary grouped by dates (one date → many emails).

I can do it with for loops:

def emails_for_one_date():

        for each_entry in email_date_table:

                for each_date in each_entry:
                        current_date_as_key = each_date

                        for each_entry2 in email_date_table:
                                list_emails = []
                                if each_entry[1] == current_date_as_key:
                                        list_emails.append( each_entry[0])
                                date_for_emails_dict[current_date_as_key] = list_emails
        print("------------------- dict here")
        print(date_for_emails_dict)

But Python is such a powerful language, I want to know the 'pythonic' way of doing it!
I suspect it can be one line.

A good function will should accept the data as a parameter and return the resulting data structure.  Call print(emails_by_date(email_date_table)) to put it all together.

Two Pythonic techniques you want to use are:

dict.setdefault(key[, default]), which gets rid of the need for if, as well as the requirement for the input to be grouped chronologically
Multiple assignment in the for-loop, which removes the ugly [0] and [1] indexing:

  If the target list is a comma-separated list of targets: The object must be an iterable with the same number of items as there are targets in the target list, and the items are assigned, from left to right, to the corresponding targets.

  The function could be written as:

def emails_by_date(pairs):
    ret = {}
    for email, date in pairs:
        ret.setdefault(date, []).append(email)
    return ret


Performance for simple code that converts a RGB tuple to hex string I'm rewriting a full color Mandelbrot Set explorer in Python using tkinter. For it, I need to be able to convert a Tuple[int, int, int] into a hex string in the form #123456. Here are example uses of the two variants that I came up with:

>>>rgb_to_hex(123, 45, 6)
'#7b2d06'

>>>rgb_to_hex(99, 88, 77)
'#63584d'

>>>tup_rgb_to_hex((123, 45, 6))
'#7b2d06'

>>>tup_rgb_to_hex((99, 88, 77))
'#63584d'

>>>rgb_to_hex(*(123, 45, 6))
'#7b2d06'

>>>rgb_to_hex(*(99, 88, 77))
'#63584d'

The functions I've come up with are very simple, but intolerably slow. This code is a rare case where performance is a real concern. It will need to be called once per pixel, and my goal is to support the creation of images up to 50,000x30,000 pixels (1500000000 in total). 100 million executions take ~300 seconds:

>>>timeit.timeit(lambda: rgb_to_hex(255, 254, 253), number=int(1e8))
304.3993674000001

Which, unless my math is fubared, means this function alone will take 75 minutes in total for my extreme case.

I wrote two versions. The latter was to reduce redundancy (and since I'll be handling tuples anyways), but it was even slower, so I ended up just using unpacking on the first version:

# Takes a tuple instead
>>>timeit.timeit(lambda: tup_rgb_to_hex((255, 254, 253)), number=int(1e8))
342.8174099

# Unpacks arguments
>>>timeit.timeit(lambda: rgb_to_hex(*(255, 254, 253)), number=int(1e8))
308.64342439999973

The code:

from typing import Tuple

def _channel_to_hex(color_val: int) -> str:
    raw: str = hex(color_val)[2:]
    return raw.zfill(2)

def rgb_to_hex(red: int, green: int, blue: int) -> str:
    return "#" + _channel_to_hex(red) + _channel_to_hex(green) + _channel_to_hex(blue)

def tup_rgb_to_hex(rgb: Tuple[int, int, int]) -> str:
    return "#" + "".join([_channel_to_hex(c) for c in rgb])

I'd prefer to be able to use the tup_ variant for cleanliness, but there may not be a good way to automate the iteration with acceptable amounts of overhead.

Any performance-related tips (or anything else if you see something) are welcome.

You seem to be jumping through some unnecessary hoops. Just format a string directly:

from timeit import timeit

def _channel_to_hex(color_val: int) -> str:
    raw: str = hex(color_val)[2:]
    return raw.zfill(2)

def rgb_to_hex(red: int, green: int, blue: int) -> str:
    return "#" + _channel_to_hex(red) + _channel_to_hex(green) + _channel_to_hex(blue)

def direct_format(r, g, b):
    return f'#{r:02x}{g:02x}{b:02x}'

def one_word(r, g, b):
    rgb = r<<16 | g<<8 | b
    return f'#{rgb:06x}'

def main():
    N = 100000
    methods = (
        rgb_to_hex,
        direct_format,
        one_word,
    )
    for method in methods:
        hex = method(1, 2, 255)
        assert '#0102ff' == hex

        def run():
            return method(1, 2, 255)

        dur = timeit(run, number=N)
        print(f'{method.__name__:15} {1e6*dur/N:.2f} us')

main()

produces:

rgb_to_hex      6.75 us
direct_format   3.14 us
one_word        2.74 us

That said, the faster thing to do is almost certainly to generate an image in-memory with a different framework and then send it to tkinter.


Find minimum value in a BST: using boolean operators, and using conditionals I've been studying the BST code in Paul Graham's ANSI Common Lisp.

He provides (my comments):

(defun bst-min (bst)
  (and bst                               ; [3]
       (or (bst-min (node-l bst)) bst))) ; [4]

(defun bst-max (bst)
  (and bst                               ; [5]
       (or (bst-max (node-r bst)) bst))) ; [6]

;; [1] How do you find min and max of a bst?
;;     Recall, the core point is that all items in left subtree are lower,
;;     and all items in right subtree are higher, & this holds for the whole
;;     tree, -otherwise binary search would miss-, and not just within a
;;     single parent child relationship.
;; [2] Therefore, to find min, we just need to go left until we can go left
;;     no more, & that's the min. If the above property didn't hold, you
;;     might go left, then right, then left, and that final one there
;;     could be as low as you like; but no, it must be greater than its
;;     ancestor of which it is a right child.

;; [3] A null node has no min. The base case. Returns nil if bst is empty.
;; [4] For a non null node, the min is either the min of its left node, or
;;     if that's null, then it's this node, instead.
;; [5] A null node has no max. The base case. Returns nil if bst is empty.
;; [6] For a non null node, the max is either the max of its right node, or
;;     if that's null, then it's this node, instead.

I find this code more or less fine, but I still find it not easy to read or cognitively process.

I'm wondering whether that subjective fact is a feature of the code itself (i.e., is the code really hard to read), or whether it's something I need to stick with and then it will become very natural; remembering Hickey's advice about lisp that it is simple but not easy.

So, I produced this version by translating from a java implementation.
It's easier for me to read (currently).

(defun bst-min (bst)
  (if (null (node-l bst))
      bst
      (bst-min (node-l bst))))

(defun bst-max (bst)
  (if (null (node-r bst))
      bst
      (bst-max (node-r bst))))

Is the first version somehow a relic of former days?
Would anyone program like that now?

Question I would like to ask helpful peeps here is: which version would you favour and why?

The aspect of the code that may cause difficulty to those new to Lisp appears to be the fact that in Common Lisp, nil has two meanings.  It's the value of an empty list () and it's also false when used in boolean context.  So when we have something like (or '(1 2 3) ()) the first non-NIL list is returned.  When we use and it returns the last item if all items are true (that is, all lists are nonempty if we pass in lists).  If you keep those facts in mind, you'll see that the first code is both consistent and logical.  See also https://stackoverflow.com/questions/23826145/what-is-the-exact-difference-between-null-and-nil-in-common-lisp

I'd probably write the code the first way because it's a more compact way of expressing what you've done with if and also only evaluates node-l once instead of twice.  But then, I'd still write car instead of first, so maybe I'm a relic of former days as well.  :)


A simple gradebook using structures I have this basic question about the efficient way to sort user-defined object. It can be done in many ways, but most of sorting algorithms at best cases is \$O(N)\$. I have come up with a fair approach to get \$O(N*log(size() + N))\$ by using std::set.

Is it a good choice in such a case?

#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <set>

struct Student
{
    std::string studentName;
    int midTermScore;
    char grade;

    friend bool operator<(Student const & a, Student const & b)
    {
        return a.midTermScore > b.midTermScore;
    }
};

template<typename C>
void display(const C& c)
{
    std::cout << std::left
        << std::setw(10) << " Names"
        << std::setw(10) << "Exam"
        << std::setw(10) << "Grade";

    std::cout << std::setfill('-') << std::setw(28) << '\n';

    for (const auto& i : c)
    {
        std::cout << "\n " << std::setfill(' ') << std::left
            << std::setw(10) << i.studentName
            << std::setw(11) << i.midTermScore
            << std::setw(2) << i.grade;
    }
}

int main()
{
    std::array<Student, 4> a
    {
        {
            { "me",     60, 'D'},
            {"matt",    88, 'B'},
            { "john",   93, 'A'},
            {"jesseca", 82, 'B'}

        }
    };

    display(a);

    std::set<Student> sorted;

    for (auto&& i : a)
    {
        sorted.insert(i); // O(N*log(size() + N))
    }

    std::cout << "\n\nafter sorting\n\n";

    display(sorted);
}

i have given basic question about the efficient way to sort user-defined object

If you really care about performance, you should measure it. Experience shows that there are many subtle influences to performance, that make it hard to reliably predict it.

Instead of using a std::set, you could try sorting the array directly. It is less code, less memory and probably faster: std::set typically is implemented as a tree, and will allocate each node separately. When inserting elements not in order, the resulting nodes will most likely be scattered in memory. Iterating over such a set might be slower than iterating over a contiguous array or even over a set where the elements have been inserted in order. (Not that it would matter much with the small sample size in this program.)

std::set also provides guarantees that you don't need here: Stability of references/iterator, unique elements, "fast" insertion not just at the end, "fast" removal of elements.

Interestingly, because std::set guarantees unique elements, it might be an incorrect choice in this context. Students will not be inserted into the set if there's already a student with the same midTermScore when using your current definition of operator<. Live example You should either use a total order for the std::set or use a data structure that can contain multiple equivalent elements (equivalent with respect to the order) like std::multiset.

For example, instead of

std::set<Student> sorted;

for (auto&& i : a)
{
    sorted.insert(i); // O(N*log(size() + N))
}

you could sort the original array:

std::sort(begin(a), end(a));

(that is std::begin and std::end, but I'm using ADL because I'm lazy)

friend bool operator<(Student const & a, Student const & b)
{
    return a.midTermScore > b.midTermScore;
}

I don't think it's a good idea to define an operator< for a type that does not provide a total order. We could try to introduce equality between two students by using (a == b) <=> (!(a<b) && !(b<a))  (I'm using <=> as is equivalent to here). But this notion of equality is strange, since we expect (a == b) => (a.studentName == b.studentName).

After looking at the code again, I think it's even a worse idea to define the (canonical) operator< for a type be mean greater than.

Therefore, I'd rather use a function, function object type or lambda to introduce this order. For example, using std::sort from above:

auto const larger_midTermScore =
    [](Student const& a, Student const& b)
    { return a.midTermScore > b.midTermScore; }

std::sort(begin(a), end(a), larger_midTermScore);

I you want to use a std::set, you could impose that order on the set as follows:

class larger_midTermScore {
private:
    static auto tie_in_order(Student const& a)
    -> decltype(std::tie(a.midTermScore, a.grade, a.studentName)) {
        return std::tie(a.midTermScore, a.grade, a.studentName);
    }
public:
    bool operator() const (Student const& a, Student const& b) {
        return tie_in_order(a) < tie_in_order(b);
    }
};

// in the main function:
std::set<Student, larger_midTermScore> sorted(begin(a), end(a));

I'm being lazy again by using std::tuple to define a lexicographical comparison of the data members of Student. Include the <tuple> header.

std::string studentName;
int midTermScore;
char grade;

The type Student might have invariants that you should protect.
For example, 'A' <= grade <= 'F' etc. Also, it is unclear (because not documented nor enforced by encapsulation) if there is a maximum length for studentName. The display algorithm suggests there is one.


Lazy evaluation function decorator Suppose I have some expensive function expensive_computation which takes a long time to compute but it always returns the same value.

I want to avoid paying the cost of computing this function because it may never be called.

Here is my solution to this, is there a more obvious or clean way to do it? Or maybe even some function from the standard library?

def lazy(function):

  internal_state = None

  def lazy_evaluation():
    nonlocal internal_state
    if internal_state is None:
      internal_state = function()
    return internal_state

  return lazy_evaluation

@lazy
def expensive_computation():
  print("Working ...")
  return "that was hard"

print(expensive_computation())
print(expensive_computation())

Which prints:

Working ...
that was hard
that was hard

if internal_state is None:
      internal_state = function()

What if function() returns None?

  Or maybe even some function from the standard library?

functools.lru_cache


Format a timespan with up to two fields I'm looking to achieve a time format that looks like this: 2d 4h remaining; or 1h 36m remaining; or 35s remaining, etc. So that it only displays the two largest values of time (this is how Clash of Clans and some other mobile games format wait times.)

Currently my code is below, but I'm wondering if there might be a shorter way to format the timespan in this manner? I'm not fully sure if String.Format will work…

public string FormatRushTime ( System.TimeSpan span )
{
    string t1;
    string t2;
    if ( span.Days > 0 )
    {
        t1 = span.ToString("%d") + "d";
        t2 = span.Hours > 0 ? span.ToString("%h") + "h" : String.Empty;
    }
    else if ( span.Hours > 0 )
    {
        t1 = span.ToString("%h") + "h";
        t2 = span.Minutes > 0 ? span.ToString("%m") + "m" : String.Empty;
    }
    else if ( span.Minutes > 0 )
    {
        t1 = span.ToString("%m") + "m";
        t2 = span.Seconds > 0 ? span.ToString("%s") + "s" : String.Empty;
    }
    else if ( span.Seconds > 0 )
    {
        t1 = span.ToString("%s") + "s";
        t2 = String.Empty;
    }
    else
    {
        t1 = String.Empty;
        t2 = String.Empty;
    }

    return t1+" "+t2;
}

What you want to do, is use early-returns (FTW). Also, let the formatter do the string work for you. Right tool for the job.

Consider your code, rewritten in Ideone...:

static string FormatRushTime (TimeSpan span)
{
    if ( span.Days != 0 )
    {
        return String.Format("{0:d}d {1:d}h", span.Days, Math.Abs(span.Hours));
    }
    if ( span.Hours != 0 )
    {
        return String.Format("{0:d}h {1:d}m", span.Hours, Math.Abs(span.Minutes));
    }
    if ( span.Minutes != 0 )
    {
        return String.Format("{0:d}m {1:d}s", span.Minutes, Math.Abs(span.Seconds));
    }
    return String.Format("{0:d}s", span.Seconds);
}


Taxicab numbers algorithm check With the programming language skills that are available to me at the time, I've written this program to find the "taxicab numbers" (e.g.  a number
expressible as the sum of two cubes in two different ways.)

While this code does work, it is definitely not scalable and it already takes about a minute to solve this for the below numbers. Does anyone have any tips/advice in order to make the complexity less?
Thanks in advance.

from math import pow

POWER = 3

for outcome in range(1000, 5000):
    maxtocheck = int( pow( outcome, 1/POWER ) )
    result = 0
    for i in range(0,maxtocheck+1):
        for j in range(0,maxtocheck+1):
            for k in range(0,maxtocheck+1):
                for l in range(0,maxtocheck+1):
                    if outcome == (pow(i, 3) + pow(j, 3)) == (pow(k, 3) + pow(l, 3)):
                        if i != k and i != l and j != k and j != l:
                            if result != outcome:
                                print("{} = {}**3 + {}**3 = {}**3 + {}**3".format(outcome,i,j,k,l))
                                result = outcome

As you said in the question you don't think this is very performant.

You only need two loops. If you go through every \$i\$ and \$j\$, then you have gone through every \$k\$ and \$l\$.
And so you don't need the \$k\$ and \$l\$ loops.

After this you have the equation:

$$\text{outcome} = i^3 + j^3$$

Since you know what \$\text{outcome}\$ is, it doesn't make sense for it to be what you're finding.
Instead if you re-arrange your code so that you can find \$j\$ for each \$i\$, then you can do everything in one loop.

$$j = (\text{outcome} - i^3)^{\frac{1}{3}}$$

And so to generate a list of \$i\$ and \$j\$ you can:

def generate_products(total):
    for i in range(int(total ** (1/3))+1):
        t = total - i ** 3
        # fix floating point error
        j = round(t ** (1/3))
        if t == j**3:
            yield i, j

After this you want to then combine these. If you're ok with \$i = k,j = l\$ then you can use itertools.product, otherwise you'd want itertools.permutations.
Which can produce all the numbers from 1 to 5000 in a couple of seconds.

def generate_products(total):
    for i in range(int(total ** (1/3))+1):
        t = total - i ** 3
        # fix floating point error
        j = round(t ** (1/3))
        if t == j**3:
            yield i, j

def generate_taxicab_numbers(outcome):
    for (i, j), (k, l) in itertools.permutations(generate_products(outcome), 2):
        print("{} = {}**3 + {}**3 = {}**3 + {}**3".format(outcome, i, j, k, l))

if __name__ == '__main__':
    for outcome in range(1000, 5000):
        generate_taxicab_numbers(outcome)

The slowest part of this is the print calls, and so if you move them out of the loops the code becomes even faster.

def generate_products(total):
    for i in range(int(total ** (1/3))+1):
        t = total - i ** 3
        # fix floating point error
        j = round(t ** (1/3))
        if t == j**3:
            yield i, j

def generate_taxicab_numbers(outcome):
    for (i, j), (k, l) in itertools.permutations(generate_products(outcome), 2):
        yield i, j, k, l

if __name__ == '__main__':
    to_print = []
    for outcome in range(1000, 5000):
        for nums in generate_taxicab_numbers(outcome):
            to_print.append("{} = {}**3 + {}**3 = {}**3 + {}**3".format(outcome, *nums))
    print('\n'.join(to_print))


Basic JavaScript template engine using replace, match and RegExp To practice with regular expressions, I wrote this basic template engine in JavaScript in addition to a simple test case to make sure it works correctly.

I am wondering if there is any improvements I can do or if I am correctly following JavaScript coding style and conventions. Thanks in advance.

In short,

{{= expression}} --> evaluates expression (context is optional)
{{0}}            --> evaluates based on given array index
{{name}}         --> evaluates based on given json values

Template code (does not require any dependency):

(function() {
    this.amirTemplateEngine = function() {
        var self = this;
        var _tokensToReplace, _values, _array;

        // evaluate in-line expressions
        self.evaluateString = function(string, options) {
            _tokensToReplace = string.match(new RegExp(/({{=[^}]*}})/g)) || [];

            _tokensToReplace.map(function(token) {
                string = string.replace(token, (function() {
                    return eval(token.replace("{{=", "").replace("}}", ""));
                }).call(options && options.context ? options.context : self));
            });

            return string;
        };

        // replace given object
        self.replaceGivenObject = function(string, options) {
            _values = options && options.values ? options.values : {};
            _tokensToReplace = string.match(new RegExp(/({{[ ]*[^}.]+[ ]*}})/g)) || [];

            _tokensToReplace.map(function(token) {
                string = string.replace(token, _values[token.replace(" ", "").replace("{{", "").replace("}}", "")]);
            });

            return string;
        };

        // replace given array index
        self.replaceGivenArray = function(string, options) {
            _array = options && options.array ? options.array : {};
            _tokensToReplace = string.match(new RegExp(/({{[ ]*[0-9]+[ ]*}})/g)) || [];

            _tokensToReplace.map(function(token) {
                string = string.replace(token, _array[parseInt(token.replace(" ", "").replace("{{", "").replace("}}", ""))]);
            });

            return string;
        };

        // helper function
        self.format = function(string, options) {
            // evaluate expressions
            string = self.evaluateString(string, options);

            // if options.array is defined, then evaluate template
            string = self.replaceGivenArray(string, options);

            // if options.values is defined, then evaluate template
            string = self.replaceGivenObject(string, options);

            return string;
        };

        // for chainability
        return self;
    };
})();

Testing the code (making sure output is correct):

var template = require('./amir-template-engine');

(function() {
    var self = this;
    something = "something else!";
    var template = "\

{{0}} {{1}} {{2}}
\

{{= 4 > 0 ? 'good' : 'bad'}}
\

{{= something }}
\

{{name}}
\
                ";

    var result = "\

seyed amir hossein
\

good
\

something else!
\

amir
\
                ";

    var templateObj = new amirTemplateEngine();

    testResult = templateObj.format(template, {
        array: ["seyed", "amir", "hossein"],
        values: {
            name: "amir"
        },
        context: self
    }) == result;

    console.log("Test is" + (testResult ? "" : " NOT") + " passing!");
})();

Link to GitHub repository

RegEx

[ ]* vs \s*

[ ]* which is same as *(space followed by a star) matches zero or more occurrences of space. This is not flexible as it only allows users to use spaces. If user use tabs, this regex will fail. Use \s*, which matches all the space characters.

Quoting from http://www.regular-expressions.info/shorthand.html

  \s stands for "whitespace character". Again, which characters this actually includes, depends on the regex flavor. In all flavors discussed in this tutorial, it includes [ \t\r\n\f]. That is: \s matches a space, a tab, a line break, or a form feed. Most flavors also include the vertical tab

RegExp Constructor vs RegEx Literal

new RegExp() is used to create a new regex. This form of regex accepts a string as the first argument and returns new regex. This is used when creating regex from a variable. Since this uses string, the backslash is used to escape following character. This will produce unexpected results when regex itself contains a backslash. Example, new RegExp('\s') will return /s/. When using a backslash in this form, they need to be escaped new RegExp('\\s'). This is not necessarily difficult but requires to take care of escaping.

Passing regex literal syntax to the constructor is same as literal syntax to create regex. So, new RegExp(/({{=[^}]*}})/g) is same as /({{=[^}]*}})/g.

Mistake

The regex for object /{{\s*([^}.]*)\s*}}/g doesn't work for all cases. [^{.]* means to match anything which is not { AND .. If the key of object contains ., this regex will fail. Check this demo. Removing . solves this problem.

Not a mistake, but a validation. Using + quantifier instead of *. * says, match zero or more of the previous pattern. For example, {{=[^}]*}} will match {{=}} which you might not want to match and process.

Better use of capturing groups

The regex /({{=[^}]*}})/g will match the string starting with {{= to the }} literal and put the complete string in first captured group. Then inside replace, {{= and }} are again replaced

token.replace("{{=", "").replace("}}", "")

This can be improved by removing those characters from capture group.

/{{=([^}]*)}}/g

This regex will match only string contained in {{= and }}. Thus, removing the need of those two replace statements. The same thing can be used for the other two regexes.

With above improvements, the regex will be as below:

/{{=([^}]+)}}/g
/{{\s*([^}]+)\s*}}/g
/{{\s*(\d+)\s*}}/g

If the expressions do not contain spaces in between them, [^}]+ can be replaced by \S+(one or more non-space characters).

JavaScript

match => map => n * replace

In the three functions, you're first using match to get the matches then iterating over it and using replace inside it. This is not at all necessary. Simple replace is sufficient in this case.

Rewritten evaluateString

// Note: I've removed `call()` here
return string.replace(/{{=([^}]*)}}/g, function(m, $1) {
    return eval($1);
});

$1 is the actual expression inside delimiters here. Similarly, other two methods can be written.

Other small improvements:

Naming: something, string.
Using _ prefix when variables are not local/private to the method: _tokensToReplace, _values, _array
Missing strict mode: What does “use strict” do in JavaScript, and what is the reasoning behind it?
Really need those comments? Guessing a number, but comments concerning
Use === to compare variables. Which equals operator (== vs ===) should be used in JavaScript comparisons?
For default values, || can be used instead of ternary.
The default value for _array should be [] instead of {}.

Demo:

(function() {
  this.amirTemplateEngine = function() {
    var self = this;

    self.evaluateString = function(string, options) {
      return string.replace(/{{=([^}]*)}}/g, function(m, $1) {
        return eval($1);
      });
    };

    self.replaceGivenObject = function(string, options) {
      var _values = options && options.values || {};

      return string.replace(/{{\s*([^}]*)\s*}}/g, function(m, $1) {
        return _values[$1.trim()];
      });
    };

    self.replaceGivenArray = function(string, options) {
      var _array = options && options.array || [];

      return string.replace(/{{\s*(\d+)\s*}}/g, function(m, $1) {
        return _array[$1];
      });
    };

    self.format = function(string, options) {
      string = self.evaluateString(string, options);
      string = self.replaceGivenArray(string, options);
      string = self.replaceGivenObject(string, options);

      return string;
    };

    return self;
  };
})();

(function() {
  var self = this;
  something = "something else!";
  var template = "\

{{0}} {{1}} {{2}}
\

{{= 4 > 0 ? 'good' : 'bad'}}
\

{{= something }}
\

{{name}}
\
                ";

  var result = "\

seyed amir hossein
\

good
\

something else!
\

amir
\
                ";

  var templateObj = new amirTemplateEngine();

  testResult = templateObj.format(template, {
    array: ["seyed", "amir", "hossein"],
    values: {
      name: "amir"
    },
    context: self
  }) == result;

  console.log("Test is" + (testResult ? "" : " NOT") + " passing!");
})();

My Take I'd use constructor pattern with overridden toString method and single regex for replacement.

function MyTemplate(str, config) {
  this.str = str;
  this.config = config;
}
MyTemplate.prototype.toString = function() {
  var object = this.config && this.config.values || {};
  var array = this.config && this.config.array || [];

  return this.str
    .replace(/{{(=?.*?)}}/g, function(m, $1) {
      $1 = $1.trim();

      return $1.startsWith('=') ? eval($1.substr(1)) :
        /^\d+$/.test($1) ? array[$1] : object[$1];
    });
};

(function() {
  var self = this;
  something = "something else!";
  var template = `
{{0}} {{1}} {{2}}

{{= 4 > 0 ? 'good' : 'bad'}}

{{= something }}

{{name}}
`;

  var result = `
seyed amir hossein

good

something else!

amir
`;

  var templateObj = new MyTemplate(template, {
    array: ["seyed", "amir", "hossein"],
    values: {
      name: "amir"
    },
    context: self
  });

  var testResult = templateObj.toString() === result;
  console.log("Test is" + (testResult ? "" : " NOT") + " passing!");
})();