Find Minimum Number of coins Please be brutal, and treat this as a top 5 technical interview. I am trying to follow Google's way of writing Java code, as per their .pdf file online of code review. (Side note: do any of you see any improvement in me?)

Suppose I am asked to find the minimum number of coins you can find for a particular sum.  That is, say, coins are 1, 3, 5, the sum is 10, so the answer should be 2, since I can use the coin 5 twice.

Time Complexity = \$O(n^2)\$
Space Complexity = \$O(n)\$

private static int findMinCoins(final int[]coins, final int sum){
    int[] calculationsCache = new int[sum+1];
    for(int i = 0; i <= sum; i++){
        calculationsCache[i] = Integer.MAX_VALUE;
    }
    calculationsCache[0]=0;/*sum 0 , can be made with 0 coins*/
    for(int i = 1; i <= sum; i++){
        for(int j = 0; j < coins.length; j++){
            if(i >= coins[j] && i - coins[j] >= 0 && calculationsCache[i-coins[j]]+1 < calculationsCache[i]){
                calculationsCache[i] = calculationsCache[i-coins[j]]+1;
            }
        }
    }
    return calculationsCache[sum];
}

You could change the innermost loop to foreach-style to make it slightly more readable:

for (int coin : coins) {
    if (i >= coin && i - coin >= 0 && calculationsCache[i - coin] + 1 < calculationsCache[i]) {
        calculationsCache[i] = calculationsCache[i - coin] + 1;
    }
}

Considering you do:

for (int i = 0; i <= sum; i++) {
    calculationsCache[i] = Integer.MAX_VALUE;
}
calculationsCache[0] = 0;

You could start the count in the loop from 1, since you're overwriting the first element right after anyway.

If coins[] doesn't contain a coin with value 1, then your function will return incorrect result:

// actual: -2147483646 (Integer.MAX_VALUE)
Assert.assertEquals(2, findMinCoins(new int[]{2, 5}, 7));

As you yourself found, the cause of this was the integer overflow in calculationsCache[i] = Integer.MAX_VALUE;, and you correctly fixed it by changing to calculationsCache[i] = Integer.MAX_VALUE - 1;.

For reference, an alternative implementation with unit tests:

private int findMinCoins(int[] coins, int sum, int index, int count) {
    if (sum == 0) {
        return count;
    }
    if (index == coins.length) {
        return 0;
    }
    if (sum < 0) {
        return 0;
    }
    int countUsingIndex = findMinCoins(coins, sum - coins[index], index, count + 1);
    int countWithoutUsingIndex = findMinCoins(coins, sum, index + 1, count);
    if (countUsingIndex == 0) {
        return countWithoutUsingIndex;
    }
    if (countWithoutUsingIndex == 0) {
        return countUsingIndex;
    }
    return Math.min(countUsingIndex, countWithoutUsingIndex);
}

private int findMinCoins(int[] coins, int sum) {
    return findMinCoins(coins, sum, 0, 0);
}

@Test
public void testExample() {
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 10));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 11));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 4));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 7));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 8));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 2, 5}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{1, 5, 2}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 1, 2}, 9));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 2, 1}, 9));
    Assert.assertEquals(2, findMinCoins(new int[]{1, 2, 5}, 3));
    Assert.assertEquals(2, findMinCoins(new int[]{2, 5}, 7));
    Assert.assertEquals(3, findMinCoins(new int[]{5, 7}, 15));
}


Parsing very simple CSS into selector and declarations (as as single piece) The last part of my HTML genrator requries a few styles. Because all styles are inline and the styling is for emails there won't be any fancy selectors, just by element, id or class.

The most complex css might look like this:

var css = @"
h1 {
    font-family: Sans-Serif; color: green; font-weight: normal; margin-top: 1.5em;
}
h2 {
    font-family: Sans-Serif; color: green; font-weight: normal; margin-top: 1.5em;
}
#foo, p {
    font-family: Sans-Serif; color: green;
}
hr, .foo {
    border: 0; border-bottom: 1px solid #ccc; background: #ccc;
}";

I read it into a dictionary that the StyleVisitor will consume and applay.

static class Css
{
    public static IDictionary<string, string> Parse(string css)
    {
        return
            Regex
                // Match "selector { declarations }"
                .Matches(css.Minify(), @"(?<selectors>[a-z0-9_\-\.,\s#]+)\s*{(?<declarations>.+?)}", RegexOptions.IgnoreCase)
                .Cast<Match>()
                .Select(m => Regex
                    // Split selectors separated by ",".
                    .Split(m.Groups["selectors"].Value, @",")
                    // Skip empty results.
                    .Where(s => !string.IsNullOrEmpty(s))
                    .Select(selector => new KeyValuePair<string, string>(
                        key: selector.Trim().ToLowerInvariant(),
                        value: m.Groups["declarations"].Value.Trim())))
                .SelectMany(x => x)
                .ToDictionary(x => x.Key, x => x.Value);
    }

    private static string Minify(this string css) => Regex.Replace(css, @"(\r\n|\r|\n)", string.Empty);
}

I'm assuming the css does not require any vaidation because it's been created and validated with an editor like jsfiddle etc.

The result of Css.Parse(css) is

h1    font-family: Sans-Serif; color: green; font-weight: normal; margin-top: 1.5em;
h2    font-family: Sans-Serif; color: green; font-weight: normal; margin-top: 1.5em;
#foo  font-family: Sans-Serif; color: green;
p     font-family: Sans-Serif; color: green;
hr    border: 0; border-bottom: 1px solid #ccc; background: #ccc
.foo  border: 0; border-bottom: 1px solid #ccc; background: #ccc

Some helper functions can make the query look a lot cleaner. LINQ is quite readable on it's own but in your case it has gotten a bit more complex and it's not exactly easy to modify something.

Example of how the main method can look:

public static IDictionary<string, string> Parse(string css)
{
    return GetSelectorMatches(css.Minify())
        .Select(match => new {match, selectors = ExtractSelectorsByPattern(match, ",")})
        .SelectMany(t => SelectorToDeclarationValue(t.selectors, t.match))
        .ToDictionary(pair => pair.Key, pair => pair.Value);
}

Where the methods have similar implementation to this one.

private static IEnumerable<Match> GetSelectorMatches(string css)
{
    return Regex.Matches(css, @"(?<selectors>[a-z0-9_\-\.,\s#]+)\s*{(?<declarations>.+?)}",
        RegexOptions.IgnoreCase).Cast<Match>();
}

private static IEnumerable<string> ExtractSelectorsByPattern(Match match, string pattern)
{
    return Regex.Split(match.Groups["selectors"].Value, pattern).Where(s => !string.IsNullOrEmpty(s));
}

private static IEnumerable<KeyValuePair<string, string>> SelectorToDeclarationValue(
    IEnumerable<string> selectors, Match match)
{
    return selectors.Select(selector => new KeyValuePair<string, string>(
        selector.Trim().ToLowerInvariant(),
        match.Groups["declarations"].Value.Trim()));
}

I'm not sure if it makes sense to have .Where(s => !string.IsNullOrEmpty(s)) in the method like this maybe additional bool parameter removeEmpty can decide that.

Besides that you can use some Dependency Injection to modify the delegates passed in most of the methods as they're quite specific I really cant provide an example of that as I'm not aware what makes sense to your project to be modifiable and what not.

You can even go one step further and implement some sort of class hierarchy and pass interfaces instead.


Implementing a c++ Kafka producer based on librdkafka To practice my c++ I decided to implement a simple Kafka producer to wrap the producer in c in librdkafka library. I just want to get your opinion on the way I have implemented teh default, copy and move constructors and make sure what I'm doing is safe.

Default constructor:

kafka_publisher::kafka_publisher(const std::string &brokers,
                                 const std::string &topic)
{
    m_errstr = new char[512];
    m_config = rd_kafka_conf_new();

    if (rd_kafka_conf_set(m_config,
                          "bootstrap.servers",
                          brokers.c_str(),
                          m_errstr,
                          sizeof(m_errstr)) != RD_KAFKA_CONF_OK) {
        std::string msg = "Failed to initialize Kafka configuration. Caused by ";
        throw std::invalid_argument(msg.append(m_errstr));
    }

    m_publisher = rd_kafka_new(RD_KAFKA_PRODUCER,
                               m_config,
                               m_errstr,
                               sizeof(m_errstr));

    if (!m_publisher) {
        std::string msg = "Failed to initialize Kafka publisher. Caused by ";
        throw std::runtime_error(msg.append(m_errstr));
    }

    m_topic = rd_kafka_topic_new(m_publisher, topic.c_str(), nullptr);

    if (!m_topic) {
        std::string msg = "Failed to initialize Kafka topic. Caused by ";
        throw std::runtime_error(msg.append(rd_kafka_err2str(rd_kafka_last_error())));
    }
}

Copy constructor:

kafka_publisher::kafka_publisher(const kafka_publisher &p)
: m_run(p.m_run),
  m_config(p.m_config),
  m_publisher(p.m_publisher),
  m_topic(p.m_topic)
{
    strcpy(m_errstr, p.m_errstr);
}

Move constructor:

kafka_publisher::kafka_publisher(kafka_publisher &&m)
: m_run(m.m_run),
  m_errstr(m.m_errstr),
  m_config(m.m_config),
  m_publisher(m.m_publisher),
  m_topic(m.m_topic)
{
    m.m_run = 0;
    m.m_errstr = nullptr;
    m.m_config = nullptr;
    m.m_publisher = nullptr;
    m.m_topic = nullptr;
}

In case if it's helpful, the declaration for this class is:

class kafka_publisher {
public:
    kafka_publisher(const std::string &brokers,
                    const std::string &topic);
    kafka_publisher(const kafka_publisher &p);
    kafka_publisher(kafka_publisher &&m);

    kafka_publisher &operator=(const kafka_publisher &p);
    kafka_publisher &operator=(kafka_publisher &&m);

    ~kafka_publisher();

    void publish(std::string &message);
    void stop() { m_run = 0; };

private:
    int m_run = 1;
    char *m_errstr;

    rd_kafka_conf_t *m_config;
    rd_kafka_t *m_publisher;
    rd_kafka_topic_t *m_topic;
};

Really appreciate your time and effort and helping me improve my c++. Thank you.

It would be more useful (and typical) for CodeReview if you'd post the entire code for the class, starting with the class definition and then the method definitions, rather than starting with one of the methods and then two more and then the class definition.

For example, your declaration for

void publish(std::string &message);

looks wrong. If you mean to take message by reference for efficiency, it should be const std::string& message. On the other hand, if it is semantically important that publish is going to modify its argument (an "out-parameter"), it would be traditional to pass the argument by pointer, or (better) return it by value.

std::string s;
kp.publish(s);  // confusing — is `s` modified?
kp.publish(&s);  // OK, informs the caller that something wacky is going on
s = kp.publish();  // best way to return a value

However, I strongly suspect from context that what's going on here is actually that publish wants to take ownership of s's heap-allocated buffer of chars. Ownership transfer is represented in C++ by plain old pass-by-value:

void publish(std::string s);

std::string s;
kp.publish(s);  // publish a copy of `s`, don't modify the original
kp.publish(std::move(s));  // publish `s` and let the original be trashed

The parts of the code you posted don't use m_run at all, so theoretically you could eliminate it.

At least, you should explain why it's an int. We only ever see it assigned the values 0 and 1, which strongly implies to me that m_run ought to be a bool.

Without seeing the code of your destructor, we can't tell whether your copy-constructor and move-constructor are doing the right thing or not.

But from what I know about librdkafka, I am reasonably confident that your copy-constructor is incorrect. Your destructor should be calling rd_kafka_topic_destroy to balance out the call to rd_kafka_topic_new in your constructor; so, if I write

kafka_publisher kp1(brokers, topicname);
kafka_publisher kp2 = kp1;
// destroy kp2
// destroy kp1

the two destructors will each call rd_kafka_topic_destroy, meaning you'll destroy the topic twice; but you only created it once! So you've got a double-free bug here.

My understanding is that librdkafka objects should be handled by unique_ptr in C++. "Copying" a pointer to a librdkafka object (such as a topic) is not generally possible. (Alternatively, you could use shared_ptr; but that seems like overkill.)

kafka_publisher(const std::string &brokers,
                const std::string &topic);

should be marked explicit.

std::string msg = "Failed to initialize Kafka configuration. Caused by ";
throw std::invalid_argument(msg.append(m_errstr));

strikes me as unnecessarily confusing. Try to avoid having multiple side-effects on the same line of C++ code. Either add lines until you have one side-effect per line:

std::string msg = "Failed to initialize Kafka configuration. Caused by ";
msg += m_errstr;
throw std::invalid_argument(msg);

or eliminate side-effects until you have one side-effect per line:

throw std::invalid_argument("Failed to initialize Kafka configuration. Caused by " + m_errstr);

I would also caution that rd_kafka_conf_set can probably fail for plenty of reasons that would not be best described as "invalid argument." In production code you'd probably just wrap up the return value in a custom exception type (throw KafkaException(return_code)) and let the higher-level code deal with it if it wanted to.


Should I treat direct CFC Calls differently than Page Requests? Should I leave in <cfif reFindNoCase( "\.cfc$" , targetPage ) eq 0> or not?

Direct CFC calls are flushed when the method returns. Either way, onRequestEnd will stop debug output from being returned for AJAX requests.

Keep If Statement

Additional regular expression search on every AJAX call. Direct CFC calls return quicker. Direct CFC call may not be trimmed.

Remove If Statement (inner code executes for all AJAX requests)

Direct CFC calls' value is stored in a variable. AJAX calls to pages return quicker. All AJAX responses are trimmed.

I'm using ColdFusion 8.

<cfcomponent output=    "false">

<cfset this.name=   "AJAX Debug Output" />

<cffunction name=   "onRequestEnd"
        returnType= "void"
        hint=       "I run on the end of requests (how clever).">

    <cfargument name=   "targetPage"
                hint=   "Path from the web root to the requested page." />

    <cfif isAJAXRequest()>
        <cfsetting  showDebugOutput=    "false"
                    enableCFOutputOnly= "true" />

        <!--- Response from CFC is already flushed to browser. Skip output. --->
        <cfif reFindNoCase( "\.cfc$" , targetPage ) eq 0>

            <!--- If AJAXResponse is not set, then generated content is response. --->
            <cfparam    name=       "request.AJAXResponse"
                        default=    "#getPageContext().getOut().getString()#" />

            <cfcontent  reset= "true" />
            <cfoutput>#trim( request.AJAXResponse )#</cfoutput>
            <cfabort />

        </cfif>

    </cfif>

</cffunction>

<cffunction name=   "isAJAXRequest"
            output= "false"
            access= "private"
            hint=   "I check to see if the request came across with ajax headers">

    <cfif structKeyExists( getHTTPRequestData().headers , "X-Requested-With" )>
        <cfreturn true />

    </cfif>

    <cfreturn false />

</cffunction>

</cfcomponent>

If you're using ColdFusion 9, you can use onCFCRequest to deal with this type of issue. Which version of CF are you using?


Determining average of integers using quicksort I was attempting an online problem given on a programming website which asked us to tell us the number of integers in a given list which can be obtained as an average of any two other integers in that list, where one of them can be equal to the average (so the other is obviously equal too).

The server tells me that my program exceeded the time limit for the last two test cases. So I would like to make my algorithm faster.

I've tried both the inbuilt Java sort function as well as my own implementation of quicksort.  I tried the test data on my own computer and it gives the output within a second.

My program basically sorts the array first, and then searches for a pair in linear time.

import java.util.*;

public class Average {

public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int[] a = new int[n];

        for (int i = 0; i < n; i++){
            a[i] = in.nextInt();

        }

        quickSort(a, 0, n - 1);

         int z = 0;

         for (int k = 0; k < n; k++){
             int s = 2 * a[k];
             int l = 0;
             int r = n-1;
             while (l < r){
                if (a[l] + a[r] == s){

                        z++;
                        break;

                }
                if (a[l] + a[r] < s){
                    l++;
                }else{
                    r--;
                }
             }

         }

         System.out.println(z);
         System.exit(0);
}

//QUICKSORT FUNCTION

private static void swap(int[] a, int i, int j) {
    // TODO Auto-generated method stub
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p-1 ;
    int j = r+1 ;

    while (true) {
        i++;
        while ( i< r && a[i] < x){
            i++;}
        j--;
        while (j>p && a[j] > x){
            j--;}

        if (i < j)
            swap(a, i, j);
        else
            return j;
    }
}

}

Just a few comments:

You can't really hope that your quicksort will be faster than what Java provides. I'm not saying, it can't be done, but it'd take an excellent programmer a few days at best.

So let's forget this part... and now to your algorithm. After some reformatting, I might understand it:

int result = 0;

for (int k = 0; k < n; k++) {
    int desired = 2 * a[k];
    int l = 0;
    int r = n-1;
    while (l < r) {
        int diff = a[l] + a[r] - desired;
        // made symmetric
        if (diff < 0) {
            l++;
        } else if (diff > 0) {
            r--;
        } else {
            result++;
            break;
        }
    }
}

You really seem to be doing what you stated. The total time is quadratic, so let's forget the sorting once again.

Some better variable naming would surely do no harm.

I'll come back when I get an idea concerning the speed.


The multithreading model to clean ConcurrentQueue in C# I have some code that populate EventfulConcurrentQueue which is ConcurrentQueue. So I need to save all data from  EventfulConcurrentQueue to a database.
I think to use sort of multithreading model in order to dequeue items.
So EventfulConcurrentQueue  should be depopulated from different threads that grab the part of items of EventfulConcurrentQueue and that items will insert to a database.
So far I have following code.
Usage of EventfulConcurrentQueue
public partial class FormMain: Form {

  private EventfulConcurrentQueue < PacketItem > PacketQueue {
    get;
    set;
  } = new EventfulConcurrentQueue < PacketItem > ();

  private void FormMain_Load(object sender, EventArgs e) {
    StartPersistingTask();
  }

  private async Task StartPersistingTask() {
    var chunkOfPacketsToInsert = 100;

    try {
      while (true) {
        if (PacketQueue.Count > chunkOfPacketsToInsert) {
          int counter = 0;
          var chunkToBulkInsert = DataHelper.CreateBulkCopyDataTable();

          while (counter <= chunkOfPacketsToInsert) {
            PacketItem packetItem = null;
            PacketQueue.TryDequeue(out packetItem);
            if (packetItem != null) {
              chunkToBulkInsert.Rows.Add(Guid.NewGuid(), packetItem.AtTime, packetItem.GPSTrackerID, packetItem.PacketBytes);
              counter++;
            } else {
              break;
            }
          };

          //create object of SqlBulkCopy which help to insert
          using
          var bulkCopy = new SqlBulkCopy(ConfigurationManager.ConnectionStrings["MyDB"].ConnectionString, SqlBulkCopyOptions.Default);
          bulkCopy.DestinationTableName = "MyTable";
          try {
            bulkCopy.WriteToServer(chunkToBulkInsert);
          } catch (Exception ex) {
            Log(ex, LogErrorEnums.Fatal);
          } finally {
            Log(LogErrorEnums.Info, $ "Items: {counter}");
          }
        } else {
          await Task.Delay(100);
        }
      }
    } catch (Exception ex) {
      Log(ex, LogErrorEnums.Error);
    }
  }

}

Definition of EventfulConcurrentQueue
public sealed class EventfulConcurrentQueue < T > {
  private readonly ConcurrentQueue < T > _queue;

  public EventfulConcurrentQueue() {
    _queue = new ConcurrentQueue < T > ();
  }

  public int Count {
    get {
      return _queue.Count;
    }
  }

  public bool IsEmpty {
    get {
      return _queue.IsEmpty;
    }
  }

  public void Enqueue(T item) {
    _queue.Enqueue(item);
    OnItemEnqueued();
  }

  public bool TryDequeue(out T result) {
    var success = _queue.TryDequeue(out result);

    if (success) {
      OnItemDequeued(result);
    }
    return success;
  }

  public event EventHandler ItemEnqueued;
  public event EventHandler < ItemDequeuedEventArgs < T >> ItemDequeued;

  void OnItemEnqueued() {
    ItemEnqueued?.Invoke(this, EventArgs.Empty);
  }

  void OnItemDequeued(T item) {
    ItemDequeued?.Invoke(this, new ItemDequeuedEventArgs < T > {
      Item = item
    });
  }
}

public sealed class ItemDequeuedEventArgs < T >: EventArgs {
  public T Item {
    get;
    set;
  }
}

public sealed class PacketItem {
  public int GPSTrackerID {
    get;
    set;
  }
  public DateTime AtTime {
    get;
    set;
  }

  public byte[] PacketBytes {
    get;
    set;
  }

  public int GPSTrackerTypeID {
    get;
    set;
  }

  /// <summary>
  /// Parsed by device's protocol packet
  /// </summary>
  public object ParsedPacket {
    get;
    set;
  }
}

I think the EventfulConcurrentQueue was not designed for this use case.
From the consumer perspective:

Things that are not in use

IsEmpty
Enqueue
ItemEnqueued
ItemDequeued

Things that are missing

DequeueAtMostNItems
WaitUntilThereAreEnoughItems

After I removed the not used things and added the missing ones the class would look like this:
public sealed class EventfulConcurrentQueue<T>
{
    private readonly ConcurrentQueue<T> _queue = new ConcurrentQueue<T>();

    public List<T> DequeueAtMostNItems(int n)
    {
        List<T> result = new();
        T current;
        do
        {
            if(_queue.TryDequeue(out current))
                result.Add(current);
        } while (current != null && result.Count <= n);

        return result;
    }

    public async Task WaitUntilThereAreEnoughItems(int numberOfItems)
    {
        while (_queue.Count < numberOfItems)
        {
            await Task.Delay(100);
        }
        return;
    }
}

With these methods you are embracing encapsulation. The operation and data are next to each other. And with this approach you don't have to expose anything internal, so the information hiding aspect is covered as well.
If you stick with this implementation then I would suggest a renaming, because the ConcurrentQueue now becomes an implementation detail.
The usage could be simplified like this:
while (true)
{
    await PacketQueue.WaitUntilThereAreEnoughItems(chunkSize);

    var chunk = PacketQueue.DequeueAtMostNItems(chunkSize);
    DataTable toBeInserted = DataHelper.CreateBulkCopyDataTable();
    chunk.ForEach(row => toBeInserted.Rows.Add(Guid.NewGuid(), row.AtTime, row.GPSTrackerID, row.PacketBytes));

    using var bulkCopy = ...
}


Refactoring away from exceptions What do you use for refactoring away from exceptions while programming functional in C#? I defined this class to hold function outcome:

public class Result
{
    public static readonly Result OK = new Result();
    public static implicit operator Result(Exception error) => new Result(error);

    protected Result(Exception error = null)
    {
        Error = error;
    }

    public Exception Error { get; }
    public bool Succeeded => Error == null;
    public bool Failed => !Succeeded;

    public override string ToString() =>
        Succeeded ? "OK" : Error.Message;
}

And its subclass to hold return value where necessary:

public class Result<T> : Result, IEnumerable<T>
{
    public static implicit operator Result<T>(Exception error) => new Result<T>(error);
    public static implicit operator Result<T>(T value) => new Result<T>(value);
    public static implicit operator T(Result<T> result)
    {
        if (result.Failed)
            throw result.Error;

        return result.Value;
    }

    protected Result(T value)
        : base(error: null)
    {
        Value = value;
    }

    protected Result(Exception error)
        : base(error)
    {
    }

    T Value { get; }

    IEnumerable<T> Values =>
        Failed ? new T[0] : new[] { Value };

    public IEnumerator<T> GetEnumerator() =>
        Values.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() =>
        GetEnumerator();
}

It is enumerable, exposing 0..1 elements, so amount of if-statements can be reduced.

Usage:

        var r1 = Div(
            Div(100, 10),
            Div(10, 2));

        var r2 = Div(
            Div(100, 10),
            Div(0, 0));

        Console.WriteLine(r1.Succeeded); // True
        Console.WriteLine(r1.Count()); // 1
        Console.WriteLine(r1); // 2

        Console.WriteLine(r2.Succeeded); // False
        Console.WriteLine(r2.Count()); // 0
        // Console.WriteLine(r2); // throws DivideByZeroException

Where:

    static Result<int> Div(Result<int> a, Result<int> b)
    {
        try
        {
            return a / b;
        }
        catch (DivideByZeroException ex)
        {
            return ex;
        }
    }

Idea comes from: Refactoring away from exceptions

I don't know what to think of the entire thing yet but...

public bool Succeeded => Error == null;
public bool Failed => !Succeeded;

I find this should be only one property bool Success.

I've watched video series and generally I think it's a new and interesting idea that I need to try out. Your solution is a good start especially with the implicit operators but I'm missing a few features.

I'm not so fond of using the Result as a parameter. It has another implicit operator for converting it into a value so using actual types for parameters is sufficient and it's easier to work with pure parameters rather than dealing with Results everywhere (but maybe it's just an example). It's also safer because I'm going to throw an exception if a result is in an invalid state so implicit casting it for the parameter would fail when a method is called and not later when a parameter is used. I find this is better because it indicates a bug before the call and not inside the method that uses a result.

public static implicit operator T(Result<T> result)
{
    if (result.Failed)
        throw result.Error;

    return result.Value;
}

I don't think this is a good implementation for this operator and I prefer getting the Value would throw like this

T Value => Success ? _value : throw new InvalidOperationException("Value isn't set because the result is in error state.");

informing me that I cannot use it because the Result is in an invalid state for it. This is the behaviour that I expect from this property and not some default value that I might use in case I forgot to check the Success flag.

After all I think I could also live with two flags for the result that I'd call

public bool Success => string.IsNullOrEmpty(Message) && Exception == null;

and

public bool Failure => !Success;

whether it should be Success or Succeeded or Failure or Failed is probably an entire new question for the English Language community but to me the former sounds better as it tells me whether the operation was a Success or a Failure and not if the Result succeeded. Well, tometo tomato ;-)

The current solution is prepared to work only with exceptions and to be used only in methods that can throw but if we wanted to make our API consistent then it should also be possible to use the Result for other methods that not necessarily throw but cannot continue because of some other reason so implementing factory methods like Ok and Fail and a custom message is not such a bad idea.

To me the perfect solution would go like this:

The non-generic Result can be created in a similar way as an exception this is with a message and an exception or with either one only. In case of a failure it returns either the exception's message or the custom one and could be used for methods that return void. For consistency reasons I turned the OK property into a Ok method.

public class Result
{
    protected Result(string message, Exception exception) { Message = message; Exception = exception; }
    protected Result(string message) : this(message, null) { }
    protected Result(Exception Exception) : this(null, Exception) { }

    public Exception Exception { get; }
    public string Message { get; }

    public bool Success => string.IsNullOrEmpty(Message) && Exception == null;
    public bool Failure => !Success;

    public static Result Ok() => new Result(nameof(Ok));

    public static Result Fail(string message, Exception exception) => new Result(message, exception);
    public static Result Fail(string message) => Fail(message, null);
    public static Result Fail(Exception exception) => Fail(null, exception);

    public override string ToString() => Success ? Message : (Exception?.Message ?? Message);

    public static implicit operator Result(Exception exception) => Fail(exception);
    public static implicit operator Result(string message) => Fail(message);
    public static implicit operator bool(Result result) => result.Success;
}

The generic implementation could provide a value:

public class Result<T> : Result, IEnumerable<T>
{
    private readonly T _value;

    protected Result(T value) : base(Exception: null) => _value = value;
    protected Result(string message, Exception exception) : base(message, exception) { }
    protected Result(string message) : base(message, null) { }
    protected Result(Exception exception) : this(null, exception) { }

    public T Value => Success ? _value : throw new InvalidOperationException("Value isn't set because the result is in error state.");

    public static Result<T> Ok(T value) => new Result<T>(value);

    public static new Result<T> Fail(string message, Exception exception) => new Result<T>(message, exception);
    public static new Result<T> Fail(string message) => Fail(message, null);
    public static new Result<T> Fail(Exception exception) => Fail(null, exception);

    public IEnumerator<T> GetEnumerator() => Enumerable.Repeat(Value, Success ? 1 : 0).GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public static implicit operator Result<T>(string message) => Fail(message);
    public static implicit operator Result<T>(Exception exception) => Fail(exception);
    public static implicit operator Result<T>(T value) => Ok(value);
    public static implicit operator Result<T>((string Message, Exception Exception) t) => Fail(t.Message, t.Exception);
    public static implicit operator T(Result<T> result) => result.Value;

    public void Deconstruct(out string message, out Exception exception)
    {
        message = Message;
        exception = Exception;
    }
}

and it can also be use with methods that do not have to throw. Consider another version of the Div method:

static Result<int> Div(int a, int b)
{
    if (b == 0) return "Cannot divide by zero" ; else return a / b;
}

I have also added an implicit cast to bool so you can use the result in a boolean expression:

var n = Div(4, 0);
if (n)
{
    Console.WriteLine("Hooray, divided!");
}
else
{
    Console.WriteLine("This time it didn't work.");
}

and with the new anonymous tuples in C# 7 we can even do this:

public static Result<int> Div(int a, int b)
{
    try
    {
        return a / b;
    }
    catch (DivideByZeroException ex)
    {
        return ("Are you nuts?!", ex);
    }
}

or how about deconstructing it?

var result = Div(4, 0);
if (!result)
{
    var (message, exception) = result;
}


How would you refactor this case statement? I've got this code in my ApplicationHelper file:

def new_button
  case controller_name
  when 'cars'
    "
New Car
".html_safe
  when 'trucks'
    "
New Truck
".html_safe
  when 'mopeds'
    "
New Moped
".html_safe
  else
    nil
  end
end

So I can just put <%= new_button %> in the view, to display the appropriate button based on the controller_name being accessed.

I have about 10 different controllers to select from (and I'm sure that collection will grow), so the code is getting a bit lengthy.

Is there a better way to accomplish this?

I haven't run this code, but maybe something along these lines:

def new_button
  content_tag(:li, class: "has-form") do
    text = "New #{controller_name.singularize.titleize}"
    path = { controller: controller_name, action: "new" }
    link_to(text, path, class: "button")
  end
end

Using content_tag and link_to is arguably cleaner, and they handle escaping automatically.

Letting the router generate the URL for you from a hash is preferable to doing string manipulation.

The text generation is perhaps inelegant, but simple. If you're using I18n elsewhere in this app I'd consider using that:

model_slug = controller_name.singularize
text = t("new_x", x: t("activerecord.models.#{model_slug}"))

But it's overkill if you're not using it for anything else.


Read binary serial data and parse integers I'm reading serial data in binary format from a stream, and I'm not happy with how I extract the data because it takes so much operations to extract the binary data from a simple line of binary data.

Each line starts with a character indicating the type of data, and afterwards follow a few 16 bit integers (big endian), followed by a checksum character and a newline.

Here's a sample of what line would be after reading:

line = "F{3x 16 bit int big endian}{checksum character}\n"

This is the simplified code in question:

  byte[] b = new byte[2];
  System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();

  // Check that the port is open. If not skip and do nothing
    if (SerialPort.IsOpen)
    {
        while(SerialPort.BytesToRead > 50){

            // read line and turn string in byte array
            string line = SerialPort.ReadLine();
            byte[] encoded = enc.GetBytes(line);

            if (line[0]=='F'){

                // copy 16 bit int into byte-array
                Array.Copy(encoded, 1, b, 0, 2);
                // -> big endian
                Array.Reverse(b);

                // turn into integer
                short value1 = BitConverter.ToInt16(b, 0);

                Array.Copy(encoded, 3, b, 0, 2);
                Array.Reverse(b);
                short value1 = BitConverter.ToInt16(b, 0);

                Array.Copy(encoded, 5, b, 0, 2);
                Array.Reverse(b);
                short value3 = BitConverter.ToInt16(b, 0);
            }

        }
        this.bytesAvailable = SerialPort.BytesToRead;

Is there a smarter way to accomplish the result of my code above?

Data Acquisition

You asked:

  Is there a smarter way to accomplish the result of my code above?

So, I have another suggestion, to work on top of the suggestions by Heslacher:

Eliminate the BitConverter work. This is easily done with boolean operators (most specifically the shift operators).

short value1 = (short)((short)encoded[1] << 8 | encoded[2]);
short value2 = (short)((short)encoded[3] << 8 | encoded[4]);
short value3 = (short)((short)encoded[5] << 8 | encoded[6]);

Why? It's fast as hell. And this tends to make it more clear what position each value represents. There's no need to place them backwards as you have to with the BitConverter. Looking at this code, it's extremely easy to determine that each pair consists of the high-byte, followed by the low-byte. With the BitConverter, the lowest byte must be followed by the subsequently higher bytes.

Can it really be faster, with all those casts, shifting (<<) and or's (|), and the fact that Microsoft themselves wrote the BitConverter?

You're damn right it can. Run the following programme:

byte[] encoded = new byte[7];
encoded[0] = 0xF0;
encoded[1] = 0xF1;
encoded[2] = 0xF2;
encoded[3] = 0xF3;
encoded[4] = 0xF4;
encoded[5] = 0xF5;
encoded[6] = 0xF6;

Stopwatch sw1 = new Stopwatch();

short value1 = 0, value2 = 0, value3 = 0;

sw1.Start();
for (int i = 0; i < 100000000; i++)
{
    value1 = BitConverter.ToInt16(new byte[] { encoded[2], encoded[1] }, 0);
    value2 = BitConverter.ToInt16(new byte[] { encoded[4], encoded[3] }, 0);
    value3 = BitConverter.ToInt16(new byte[] { encoded[6], encoded[5] }, 0);
}
sw1.Stop();
Console.WriteLine(sw1.ElapsedTicks.ToString());
sw1.Reset();

Console.WriteLine(value1.ToString("X"));
Console.WriteLine(value2.ToString("X"));
Console.WriteLine(value3.ToString("X"));

sw1.Start();
for (int i = 0; i < 100000000; i++)
{
    value1 = (short)((short)encoded[1] << 8 | encoded[2]);
    value2 = (short)((short)encoded[3] << 8 | encoded[4]);
    value3 = (short)((short)encoded[5] << 8 | encoded[6]);
}
sw1.Stop();
Console.WriteLine(sw1.ElapsedTicks.ToString());
sw1.Reset();

Console.WriteLine(value1.ToString("X"));
Console.WriteLine(value2.ToString("X"));
Console.WriteLine(value3.ToString("X"));

Results:

12956403
F1F2
F3F4
F5F6
1505318
F1F2
F3F4
F5F6

You'll notice that the bitwise-operator method takes 12% of the time the BitConverter method does. And in this situation it makes a great deal of sense. It's easier to reason how the value1, value2 and value3 variables are being filled with the bitwise-operators. It's not so obvious with the BitConverter.

Yes, this is obviously a worst-case environment, you will likely have other bottlenecks and JITer that will influence it, but this at least goes to show that there are other just as good solutions to the same problem. Personally, I've never touched the BitConverter, I always do my own bitwise-arithmetic. To me, it's easier to read and more obvious. To you, it may not be.

I wouldn't suggest going so far as to make a loop. I did just that, and it's actually slower.

short[] myValues = new short[3];

sw1.Start();
for (int i = 0; i < 100000000; i++)
{
    for (int t = 0; t < myValues.Length; t++)
        myValues[t] = (short)((short)encoded[1 + t * 2] << 8 | encoded[2 + t * 2]);
}
sw1.Stop();
Console.WriteLine(sw1.ElapsedTicks.ToString());
sw1.Reset();

for (int t = 0; t < myValues.Length; t++)
    Console.WriteLine(myValues[t].ToString("X"));

Results:

3759655
F1F2
F3F4
F5F6

Twice the time the non-loop method took. With a dynamic List you can expect that it will be even slower. (Haven't done any experiments with that method, but one can estimate it would take longer.)

Commenting // when is too much and not enough

Another suggestion, based on his answer: put a comment on the while(SerialPort.BytesToRead > 50){ line describing why we only want it if there are more than 50 bytes left to read. From your current code it's impossible to reason why.

Comments are very powerful; and though I am very liberal with my comments (placing one every 2-10 lines), you don't have to be. But they should be often enough that you don't have to examine a 200+ line file to get the relevant bits. Add minor information on where these values are used, what are they for, if you are using indices like this, then markup what each index represents. You don't have to go ape-s*** on them. Just describe what it is you are doing, and why.


What constructor implementaton follows best practice in Java I am looking for best practices as they apply to constructor usage in common Java class construction.

Example 1

import javax.swing.*;
import java.awt.*;

public class Painter extends JPanel{

  public Painter(){
     buildGUI();
  }

  private void buildGUI(){
    JFrame frame = new JFrame();
    frame.setLayout(new BorderLayout());
    frame.setTitle("Paint drawing demonstration");
    new Center_frame(frame);

    JPanel headerPanel = new JPanel();
    headerPanel.add(new JLabel("The drawing panel is below"));

    Drawing_panel dp = new Drawing_panel();

    frame.add(BorderLayout.NORTH,headerPanel);
    frame.add(BorderLayout.SOUTH,dp);

    frame.pack();
    frame.setVisible(true);
  }

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

}//end class Painter

Example2

import javax.swing.*;
import java.awt.*;

public class Painter extends JPanel{

  public Painter(){
       JFrame frame = new JFrame();
       frame.setLayout(new BorderLayout());
       frame.setTitle("Paint drawing demonstration");
       new Center_frame(frame);

       JPanel headerPanel = new JPanel();
       headerPanel.add(new JLabel("The drawing panel is below"));

       Drawing_panel dp = new Drawing_panel();

       frame.add(BorderLayout.NORTH,headerPanel);
       frame.add(BorderLayout.SOUTH,dp);

       frame.pack();
       frame.setVisible(true);
  }

public static void main(String args[]){
    //create a Painter object
    new Painter();
}

}//end class Painter

no one from them, this should be standard or base

EDIT: added DefaultCloseOperation for Top-Level Container

import javax.swing.*;
import java.awt.*;

public class Painter {

    private JFrame frame;
    private JPanel headerPanel;
    private Drawing_panel ;

    public Painter() {
        frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLayout(new BorderLayout());
        frame.setTitle("Paint drawing demonstration");

        //new Center_frame(frame);
        //no reason for create another new JFrame look for
        //JDialog instead of JFrame, if you needed multiplayed
        //view then check CardLayout, is very easy for use

        headerPanel = new JPanel();
        headerPanel.add(new JLabel("The drawing panel is below"));

        dp = new Drawing_panel();

        frame.add(headerPanel, BorderLayout.NORTH);
        frame.add(dp, BorderLayout.SOUTH);

        frame.pack();
        frame.setVisible(true);
    }

    public static void main(String args[]) {
        SwingUtilities.invokeLater(new Runnable() {

            @Override
            public void run() {
                Painter p = new Painter();
            }
        });
    }
}


Prime factors and perfect square I want to convert an integer to a perfect square by multiplying it by some number. That number is the product of all the prime factors of the number which not appear an even number of times. Example 12 = 2 x 2 x 3; 2 appears twice (even number of times) but 3 just once (odd number of times), so the number I need to multiply 12 by to get a perfect square is 3. And in fact 12 x 3 = 36 = 6 * 6.

I converted my code to Haskell and would like to know what suggestions you have.

import Data.List (group)

toPerfectSquare :: Int -> Int
toPerfectSquare n = product . map (\(x:_) -> x) . filter (not . even . length) . group $ primefactors n

primefactors :: Int -> [Int]
primefactors n = prmfctrs' n 2 [3,5..]
  where
    prmfctrs' m d ds | m < 2     = [1]
                     | m < d^2   = [m]
                     | r == 0    = d : prmfctrs' q d ds
                     | otherwise = prmfctrs' m (head ds) (tail ds)
      where (q, r) = quotRem m d

Sorry about the naming, I'm bad at giving names.

One particular doubt I have is in the use of $ in toPerfectSquare, that I first used . but it didn't work and I needed to use parenthesis. Why? And is it usual to have that many compositions in one line?

We can replace some custom functions or constructs by standard library ones:

\(x:_) -> x is called head
not . even is called odd

Next, 1 is not a prime, and 1 does not have a prime factorization. Since product [] yields 1, we can use [] instead in prmfctrs'.

The worker prmfctrs' is a mouthful. Workers are usually called the same as their context (but with an apostrophe, so primefactors') or short names like go.

And last but not least, we can use @ bindings to pattern match on the head, tail and the whole list at once.

If we apply those suggestions, we get

import Data.List (group)

toPerfectSquare :: Int -> Int
toPerfectSquare n = product . map head . filter (odd . length) . group $ primefactors n

primefactors :: Int -> [Int]
primefactors n = go n 2 [3,5..]
  where
    go m d ds@(p:ps) | m < 2     = []
                     | m < d^2   = [m]
                     | r == 0    = d : go q d ds
                     | otherwise = go m p ps
      where (q, r) = quotRem m d

In theory, we can even get rid of a parameter in go, namely the d, so that we always just look at the list of the divisors:

import Data.List (group)

toPerfectSquare :: Int -> Int
toPerfectSquare n = product . map head . filter (odd . length) . group $ primefactors n

primefactors :: Int -> [Int]
primefactors n = go n $ 2 : [3,5..]
  where
    go m dss@(d:ds) | m < 2     = []
                    | m < d^2   = [m]
                    | r == 0    = d : go q dss
                    | otherwise = go m ds
      where (q, r) = m `quotRem` d

We could also introduce another function \$f\$, so that for any \$a,b \in \mathbb N\$ we get a pair \$(n,y) \in \mathbb N^2\$ such that

$$
a^n y = b
$$
If we had that function, we could write use it to check easily whether the power of a given factor is even or odd. However, that function and its use in toPerfectSquare are left as an exercise.


PHP: Overuse of date manipulation leading to convoluted code I despise playing with dates in PHP so no doubt the below is too convoluted for what is needed. What I am looking for is a general tidy/reduction.

Everything but the wednesday and friday arrays are in a loop. The loop is from a ROQL statement. Oracle SQL for it's RightNow product, which is a very very stripped down version of MySQL from what I understand, meaning we are limited to basic SELECT statements i.e. we can't do anything worthwhile there.

$inc['order_date'] is a string representing a date in the format yyyymmdd
$inc['order_dispatch_date'] is a string representing a date in the format yyyymmdd
$inc['order_address'] is a string representing an address

So the basics of the code is:

Loop through each row in the database
Convert some dates
If the order address in the database is in the wednesday array, set the collection date to the Thursday after
If the order address in the database is in the friday array, set the collection date to the Saturday after
Do some more date conversion/manipulation
END GOAL: Get the difference in days between the order_date and the collection_date

CODE

$wednesday = array("Paris","London","New York");
$friday = array("Munich", "Cardiff", "Sydney");

$res = RNCPHP\ROQL::query( "SQL QUERY HERE")->next();
while($inc = $res->next()) {

    $order_date = DateTime::createFromFormat('Ymd', $inc['order_date']);
    $order_date = $order_date->format('Ymd');

    $order_dispatch_date = DateTime::createFromFormat('Ymd', $inc['order_dispatch_date']);
    $order_dispatch_date = $order_dispatch_date->format('Ymd');

    if (in_array($inc['order_address'], $wednesday)) {
        $order_collection = date('Ymd', strtotime('next thursday', strtotime($order_dispatch_date)));
    }
    if (in_array($inc['order_address'], $friday)) {
        $order_collection = date('Ymd', strtotime('next saturday', strtotime($order_dispatch_date)));
    }

    $order_collection = new DateTime($order_collection);
    $order_date   = new DateTime($order_date);

    $interval = $order_date->diff($order_collection);
    $interval = $interval->d;
}

FIRST REVISION

if (in_array($inc['order_address'], $wednesday)) {
    $order_collection = new DateTime(date('Ymd', strtotime('next thursday', strtotime($inc['order_dispatch_date']))));
}
if (in_array($inc['order_address'], $friday)) {
    $order_collection = new DateTime(date('Ymd', strtotime('next saturday', strtotime($inc['order_dispatch_date']))));
}

$order_date = new DateTime(date('Ymd', strtotime($inc['order_date'])));
$interval = $order_date->diff($order_collection)->d;

I'll provide a snippet with some sample data to demonstrate a few of my suggested techniques.

Code: (Demo)

$incs=[
    ['order_date'=>'20171128','order_dispatch_date'=>'20171129','order_address'=>'Paris'],
    ['order_date'=>'20171128','order_dispatch_date'=>'20171129','order_address'=>'Munich'],
    ['order_date'=>'20171129','order_dispatch_date'=>'20171130','order_address'=>'London'],
    ['order_date'=>'20171129','order_dispatch_date'=>'20171130','order_address'=>'Cardiff'],
    ['order_date'=>'20171130','order_dispatch_date'=>'20171201','order_address'=>'New York'],
    ['order_date'=>'20171130','order_dispatch_date'=>'20171201','order_address'=>'Sydney']
];

$wednesday = array("Paris","London","New York");

foreach($incs as $inc){
    $order_date = DateTime::createFromFormat('Ymdhis', $inc['order_date'].'000000');
    $day_name = in_array($inc['order_address'], $wednesday) ? 'Thursday' : 'Saturday';
    $order_collection = new DateTime($adj_date=date('Y-m-d 00:00:00', strtotime("next $day_name {$inc['order_dispatch_date']}")));

    $interval = $order_date->diff($order_collection)->d;
    echo "\n{$inc['order_date']} - $adj_date = $interval";
}

Output:

20171128 - 2017-11-30 00:00:00 = 2
20171128 - 2017-12-02 00:00:00 = 4
20171129 - 2017-12-07 00:00:00 = 8
20171129 - 2017-12-02 00:00:00 = 3
20171130 - 2017-12-07 00:00:00 = 7
20171130 - 2017-12-02 00:00:00 = 2

Now for the fine points:

Because you state that every order_address is in the $wednesday or $friday array, then you should only be checking one of them for best efficiency.  This check will determine the day name that will be fed to strtotime() later.
When generating your DateTime objects, assign them zero-ed times.  This way php will not default them to the "current time" for the given date.  Performing this declaration will avoid getting deviations in the diff() value later.
strtotime() will correctly interpret your Ymd format, so no additional string preparation is necessary.
The syntax for your strtotime() call is a single parameter with next $day_nameand$inc['order_dispatch_date']` all in a single string.
You can sensibly save a line of code by chaining ->d to your $interval declaration.

Here is how I think your new code should look:

$wednesday = array("Paris","London","New York");

$res = RNCPHP\ROQL::query( "SQL QUERY HERE")->next();
while($inc = $res->next()) {

    $order_date = DateTime::createFromFormat('Ymdhis', $inc['order_date'].'000000');
    $day_name = in_array($inc['order_address'], $wednesday) ? 'Thursday' : 'Saturday';
    $order_collection = new DateTime(date('Y-m-d 00:00:00', strtotime("next $day_name {$inc['order_dispatch_date']}")));

    $interval = $order_date->diff($order_collection)->d;
}


4 distinct integers, whose reciprocals sum up to 1 I wrote the following short python program to solve a math puzzle, which asked for all the 4-tuples of distinct natural numbers whose reciprocals sum up to 1.

from fractions import Fraction

results = []

def solve(length, terms):
  previous = terms[-1] if len(terms) > 0 else 0
  sum_needed = 1 - sum([Fraction(1,x) for x in terms])
  if length == len(terms) + 1:
    rest = int(Fraction(1,sum_needed))
    if Fraction(1,rest) == sum_needed and rest >= previous + 1:
      results.append(terms + [rest])
  else:
    next_min = max(previous, int(Fraction(1,sum_needed))) + 1
    next_max = int(Fraction(length,sum_needed))
    for next in range(next_min, next_max+1):
      solve(length, terms + [next])

solve(4,[])
print results

The basic idea is to go through the possible range of the smallest number first, and then based on its value, find the other three numbers.
It all works fine, the output is as desired:

[[2, 3, 7, 42], [2, 3, 8, 24], [2, 3, 9, 18], [2, 3, 10, 15], [2, 4, 5, 20], [2, 4, 6, 12]]

This was a 10-minute project, and not production code, so I don't really worry about readability or maintainability, but still there are a few things which I don't like in my implementation, mostly originating from the recursive approach used.

I've used the itertools module in other tiny hobby-projects, mostly to answer combinatorics-related questions, but I'm not really experienced with other uses of it.
I wonder if changing the approach from recursion to iteration is possible for a problem of this kind, and if itertools has some functions which could help me achieving that.

Any other comments on bad practises in the code above and some pythonic ideas that could have been used in it are also very welcome. Thanks in advance!

I also include an iterative solution:

from fractions import Fraction

result = []

a_min = max(1, int(Fraction(1,(1-sum([Fraction(1,i) for i in []])))+1))
a_max = int(Fraction(4,1-sum([Fraction(1,i) for i in []])))
for a in range(a_min,a_max+1):
  b_min = max(a+1, int(Fraction(1,(1-sum([Fraction(1,i) for i in [a]])))+1))
  b_max = int(Fraction(3,1-sum([Fraction(1,i) for i in [a]])))
  for b in range(b_min,b_max+1):
    c_min = max(b+1, int(Fraction(1,(1-sum([Fraction(1,i) for i in [a,b]])))+1))
    c_max = int(Fraction(2,1-sum([Fraction(1,i) for i in [a,b]])))
    for c in range(c_min,c_max+1):
      d = int(Fraction(1,1-sum([Fraction(1,i) for i in [a,b,c]])))
      if d>c and 1-sum([Fraction(1,i) for i in [a,b,c,d]])==0:
        result.append([a,b,c,d])

print result

Of course this has the big disadvantage of being non-generic: unlike the recursive solution, this (without modification) cannot be used to find 5-tuples with the same reciprocal sum of 1.
I tried to write it in a way that emphasizes the repetitive pattern in it: the loop for a and b variables are very similar, so maybe that's the part which can be replaced by a well-chosen function from itertools.
Any ideas?

Fraction has numerator and denominator, which are cleaner than the mucking around with int().

Appending to an external accumulator is quick and easy, but yield may give more readable code. If you combine that with passing the minimum next denominator and the remaining fraction (rather than respectively extracting them and recalculating them on each call) you get

from fractions import Fraction

def solve(num_terms, min_denom, sum_needed):
  if num_terms == 1:
    if sum_needed.numerator == 1 and sum_needed.denominator >= min_denom:
      yield [sum_needed.denominator]
  else:
    next_min = max(min_denom, int(Fraction(1,sum_needed)) + 1)
    next_max = int(Fraction(num_terms,sum_needed))
    for next in range(next_min, next_max+1):
      yield from [[next] + tail for tail in
                  solve(num_terms - 1, next + 1, sum_needed - Fraction(1, next))]

print (list(solve(4, 1, Fraction(1,1))))

Obviously readability is subjective to some degree, but I prefer the version with yield.

I should note that it would be more Pythonic to use a double comprehension instead of a comprehension inside a loop, but I don't find double comprehensions very readable.

itertools can be used, but I don't think there's any way to do so really efficiently - i.e. with early aborts. I think you would have to bound the maximum possible denominator:

# The largest denominator will be the last term when the previous terms are
# as large as possible
recip_max_denom = 1 - sum([Fraction(1,x) for x in range(1, num_terms)]
max_denom = recip_max_denom.denominator // recip_max_denom.numerator

Then you can use

itertools.combinations(range(1, max_denom + 1), num_terms)

and filter to those which give the correct sum.


Simple password encryption / decryption I'm working on a simple data storing program for my senior year (Secondary School / Grade 12), and there is a user sign-in functionality I've decided to implement. The way I've done this is by storing the usernames and passwords in a text file. They are stored as follows:

userName password
userName password
...

The usernames, I've decided to leave as plain text, as is decided by the user upon registration. The passwords however, I've decided to encrypt by inserting a special character ( '/' , '?' , ':', ...) between each of the characters entered by the user. This is simple to code as I've done:

// password is passed to the function as a string parameter
fstream writer;
writer.open("database.txt", ios::app);

int separators[16];

for (int i = 0; i < 16; i++)
{
    int randomi = rand() % (47 - 33 + 1) + 33;
    separators[i] = randomi;
}

for (int j = 0; j < password.length(); j++)
{
    int randomIndex = rand() % 6;
    writer << (int)password[j] << separators[randomIndex];
}

writer << "\n";

For the time being, I've decided to only use on of the special characters to figure out the decryption mechanism. So, using '/' as the special character, the following is my decryption code:

...
__int64 l=0;
...

for (int i = 0; i < a.length(); i = i + 2) //a is the password read from the file as a string.
{
    if (a[i] - 48 > 4)   //greater than 4 as the ASCII values of alphabets are above 50
    {
        l = l * 10;
        l = l + (a[i] - 48);  //yields the int value from the ASCII number.
        l = l * 10;
        l = l + (a[i + 1] - 48);
    }
}

The above code, takes in the password from the file, and scans for the number 4 (explained in the comment above); if the current number is not 4, it stores its int value in a variable called l. (Pardon the insignificant naming please), and does the same for the next letter, before incrementing i by 2, as the special character's ASCII value is 2 numbers.

There are drawbacks of this, mentioned at the bottom.

The verification mechanism for this system is as:

...
__int64 dy=0;
...
for (int i = 0; i < c.length(); i++) //password passed to decrypt function as string
{
    dy = dy * 100;
    dy = dy + (toupper(c[i])); //toupper so that the alphabet's ASCII value is only 2 digits
}

if (dy == l) // `l` from the decryption mechanism
{
    cout << "VALID";
}
else
{
    cout << "INVALID";
}

This works on the basis that it takes every character's ASCII value and converts it into an int for the entire word.

Example:

User entered password : Mayur
Stored password (in file after encryption) : 77476547894785478247       //while using only the special character `/`
Password converted into `int` format : 7765898582 //each 2 digits corresponds to a character in the user entered password
Decrypted password : 7765898582
Passwords match! Valid!

Major drawbacks:

At the moment, I have difficulties with decrypting for lower case alphabets due to triple digit ASCII values
Password size small due to overflow conditions of the integer format the decryted password is stored to verify.
At the moment, uses same special character to separate alphabets of actual password

I'd like you to pretty much to judge the system, and maybe if someone will post an estimate as to how hard this system would be to crack (given that the special characters will be random), and if there are more efficient ways to go about making this system more secure. (I might decided to encrypt usernames as well).

What I'd like from you guys, is pretty much to judge the system, and maybe if someone will, post an estimate as to how hard this system would be to crack

For a professional cryptographer (which I am not), it would be very easy to crack, due to the following factors:

the system relies on rand (rand is not really safe for cryptographic code; consider using a mersene twister, like mt19937).
the algorithm has low entropy, meaning it is easy to brute-force it, using a password dictionary.
considering your decryption algorithm is deducing the key from the data itself, a hacker could do the same.

There are probably other factors making the code easy to crack, but as I said, I am not a crptographer.

  (given that the special characters will be random), and if there are more efficient ways to go about making this system more secure. (I might decided to encrypt usernames as well).

You are looking at a problem with a "yes/no" answer (i.e. you need to check that the data is the same, not use decrpyted data in more complex computations), you should consider a one-way hash.

The idea is to construct an ireversible function, (irreversible = "given x, f(x) is easy to compute, but given f(x) it is difficult/impossible to compute x").

Using a one-way function in your case:

To encode the password, you apply the function.

To check the password, you ask for user input, you apply the function on the input, then compare the result with the already computed value (the one you need to verify).

This will (theoretically) allow you to make an algorithm that is not required to be reversible for checking the data.

As a rule of thumb though, security code is notoriously hard to get right. Consider:

using third party solutions (like CryptoPP or OpenSSL)
using known solutions (OpenSSL, PGP/GPG)
implementing known cryptographic algorithms (look up symetric encryption, asymetric encryption, commercial hash functions and algorithms)


Monte Carlo estimation of π My C program uses the Monte Carlo method to approximate the mathematical constant π, the ratio of a circle's circumference to its diameter (and, importantly for this code, 4 times the ratio of a circle's area to that of its bounding square).

This estimation executes more slowly when parallelised using OpenMP than it does when executed in a single thread.

I think that my random generator function is not thread safe, and that may be the cause of the slowdown.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <omp.h>

#define DART 1000000    // Number of darts each player throws
                        // Number of random dots in the square[-1,+1]

#define MAXPLAYER 8     // Maximume number of participant players
                    // Number of threads
/**
Generates a random number between two params given

@param: random number scope
@return: desired random number
*/
long double fRand(long double fMin, long double fMax)
{
    long double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

/**
    Generates random dots on the board

    @param: playerDarts, total number of darts to throw
    @return: score, number of darts thrown in the circle
*/
int player(int playersDarts)
{
    srand(time(NULL));
    long double pi, x, y;
    int score = 0;

    for (int i = 0; i < playersDarts; i++)
    {
        x = fRand(-1.0, 1.0);
        y = fRand(-1.0, 1.0);

        if (x*x + y*y < 1.0)
            score++;
    }
    return score;
}

void main()
{
long double pi;
long const double REAL_PI = 3.141592653589;
int score = 0, playersDarts;

////////////////////////////////////////////////////
//  Parallel                                      //
////////////////////////////////////////////////////

// devide the total number of DARTS between players
playersDarts = DART / MAXPLAYER;
double beginParallel = omp_get_wtime();

#pragma omp parallel for
for (int i = 1; i <= MAXPLAYER; i++)
    score += player(playersDarts);

double endParallel = omp_get_wtime();
pi = 4.0 * ((long double)score / (long double)DART);

double time_spent_parallel = endParallel - beginParallel;
printf("\n\t Calculated pi : %.12Lf\n", pi);
printf(  "\t       Real pi : %.12Lf\n", REAL_PI);
printf("\n\t Parallel Execution Time: %f\n", time_spent_parallel);

////////////////////////////////////////////////////
//  Serial                                        //
////////////////////////////////////////////////////

double beginSerial = omp_get_wtime();
pi = 4.0 * ((long double) player(DART) / (long double)DART);
double endSerial = omp_get_wtime();

double time_spent_serial = endSerial - beginSerial;

printf("\n\t Calculated pi : %.12Lf\n", pi);
printf(  "\t       Real pi : %.12Lf\n", REAL_PI);
printf("\n\t Serial Execution Time: %f\n", time_spent_serial);
}

In the code below you must realise that score is a variable that is shared between the threads. Which means that it requires synchronization, as you have omitted this synchornisation you will have undefined behaviour (incorrect result most likely).

for (int i = 1; i <= MAXPLAYER; i++)
    score += player(playersDarts);

OpenMP is not a magic box that will automatically make everything faster. You still need to think about synchronisation and proper algorithms. Also starting a thread does have some overhead and if the work done by the thread is small in comparison to the overhead, then you're slowing the program down.

There are plenty of resources on parallel programming on the internet, I recommend starting with doing your threading manually until you know how it works and then start using tools like OpenMP.


Writing a large file of numbers Basically, I want to write a huge file of numbers. Each line in that file should contain one number. This program below is extremely slow (obviously) but it works. It writes one line after line and always one number until the limit of an unsigned long has been reached.

#include <iostream>
#include <limits>
#include <fstream>

int main() {

    unsigned long max = std::numeric_limits<unsigned long>::max();
    unsigned long i = 0;
    std::ofstream myFile;
    myFile.open( "/home/awesome/Desktop/large_numbers.txt" );
    while( i < max ) {

        myFile << i << "\n";
        i++;

    }
    myFile.flush();
    myFile.close();
}

This program wrote in 2 minutes on my desktop computer 12GB. On my laptop only 117 MB in 10 minutes. On both computers I had to stop the program because it was making my computer slow and still wasn't done. Any way to optimize it so it'll be faster and maybe run more smooth so my other programs will still run perfectly fine?

Few things.

This number:

unsigned long max = std::numeric_limits<unsigned long>::max();

Is

18446744073709551615

If we assume that the average size of a number is half this length (so 10 characters). Then the size of the file is:

   184467440737095516150 bytes.
=> 180143985094819830 Kbytes
=> 175921860444150 MBytes
=> 171798691830 GBytes
=> 167772150 TBytes
=> 163830 PBytes
=> 150 XBytes

Unless you have some sort of massive raid. I don't think you have storage space foe all those numbers.

Even if your system uses a smaller number of bits for an unsigned long than mine (say 32 bit). This is still a large file (though doable on modern systems).

=> 15 GBytes (approx)

But the problem is not the speed of the program. Its is the speed that the OS can copy data to the disk. That will be your limiting factor. If you want to see how fast it could write to an optimal disk then use the special file "/dev/null". You can write to this and it uses no disk space.

12G in 2 min is a write rate of:

107374182 bytes a sec or
104857 K/s
102 M/s

A quick Google reveals that 500 M/s is achievable for SSD drives while normal HD achieve approx 100 M/s. So it looks like your desk top has normal spinning platter hard disk and it was going at the top speed.

Laptops are known to slower. Especially when they get hot. The hardware is designed to physically throttle the system to make sure it does not overheat.

Why not create and open the file in one line?

std::ofstream myFile;
myFile.open( "/home/awesome/Desktop/large_numbers.txt" );

I would do this:

std::ofstream myFile( "/home/awesome/Desktop/large_numbers.txt" );

Simpler to use a for(;;) loop than a while().

for(unsigned long i = 0;i <= max; ++i)
    myFile << i << "\n";               // Note because you opened the file in
                                       // text mode. The '\n' character will
                                       // translated into the platform end of
                                       // of line sequence.
}

No need to flush or close the stream manually.

myFile.flush();
myFile.close();

When the object goes out of scope the destructor is called. This will close the file which will flush the content of the buffers first.

#include <iostream>
#include <limits>
#include <fstream>

int main() {

    unsigned long max = std::numeric_limits<unsigned long>::max();

    std::ofstream myFile( "/home/awesome/Desktop/large_numbers.txt" );
    for(unsigned long i = 0; i < max; ++i) {
        myFile << i << "\n";
    }
}


Leetcode: Detecting duplicate elements in an array within a k-element window Upon solving the problem 'contain duplicates` in leetcode:

  Given an array of integers and an integer k , find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k .

  Example 1:

Input: nums = [1,2,3,1] , k = 3

Output: true

  Example 2:

Input: nums = [1,0,1,1] , k = 1

Output: true

  Example 3:

Input: nums = [1,2,3,1,2,3] , k = 2

Output: false

I tried best  to write a Pythonic style solution and improve the performance.

class Solution2:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        lookup = dict()  #{value:index}

        for cur, val in enumerate(nums):
            prev = lookup.get(val)

            if prev != None and cur - prev <= k:
                #logging.debug(f"{cur - prev}")
                return True
            lookup[val] = cur #add it to lookup

        return False

  Runtime: 68 ms, faster than 12.21% of Python3 online submissions for Contains Duplicate II.
  Memory Usage: 20.4 MB, less than 13.64% of Python3 online submissions for Contains Duplicate II.

I am confused about the score. I was 100% assure that it was the best possible solution.

What's the problem with my solution?

The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an \$(O(n))\$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with \$O(k))\$.

It makes no difference if \$k \approx n\$, but boosts the performance for \$k \ll n\$ (which I presume is so for the bulk of test cases).

To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev <= k anymore.


Codility binary gap solution This is how I solved the binary gap problem: Find longest sequence of zeros, bounded by ones, in binary representation of an integer

I wonder how does it fare against solutions such as ones appeared here?  Codility binary gap solution using regex

function solution(N) {
    const bin = N.toString(2);

    let currentGap = 0;
    let gaps = [];

    for (i=0; i<bin.length; i++){

      if (bin[i]==="0"){
        currentGap++;

        if (bin[i+1]==="1"){
          gaps.push(currentGap);
          currentGap = 0;
        }
      }
    }

    if (gaps.length===1){
      return gaps[0];
    } else if (gaps.length>1){
      return Math.max(...gaps)
    } else {
      return 0
    }
}

Here's my approach:

function solution(n) {
    var maxZeros = 0;
    while(n !== 0 && n % 2 === 0) {
        n >>>= 1;
    }
    for(var curr=0; n !== 0; n>>>=1) {
        if(n % 2 === 0) {
            curr++;
        } else {
            curr = 0;
        }
        maxZeros = Math.max(maxZeros, curr);
    }
    return maxZeros;
}

Some notable differences from your solution:

Number isn't converted to binary string.  This is half for optimization purposes and half for lack of necessity.
Approach to handling the "zero gap must be bound by 1s" requisite.  The first 1 is automatically handled because it wouldn't be zero if there were still a 1 to handle.  However the lower 1 bound is simply handled by shifting until the first 1 is in the lowest digit, eliminating the need to add flags or extra handling.
Notice that no memory is required to hold gap information.  It is irrelevant as you can save only the information required as you move along.
Value n is checked against being 0 as opposed to being greater than zero just because a negative number should not be disregarded just because it is negative.

Hope that helps!  If you have any questions, just ask!


Given time intervals, find the minimum number of conference rooms required The task is taken from LeetCode

  Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of
  conference rooms required.

  Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

  Example 2:

Input: [[7,10],[2,4]]
Output: 1

  NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

My solution

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function(intervals) {
  if (intervals.length <= 1) { return intervals.length; }

  const startTimes = [];
  const endTimes = [];
  intervals.forEach(x => {
    startTimes.push(x[0]);
    endTimes.push(x[1]);
  });
  startTimes.sort((a, b) => a - b);
  endTimes.sort((a, b) => a - b);

  let startPointer = 0;
  let endPointer = 0;
  let rooms = 0;
  while(startPointer < intervals.length) {
    if (startTimes[startPointer++] >= endTimes[endPointer]) {
      ++endPointer;
    } else {
      ++rooms
    }
  }
  return rooms;
};

The code looks much simpler than I would expect for this task. I tried several examples but could neither make it fail, nor did I understand why and how this algorithm works, I was only delighted that it seems to work. Therefore I have only a few remarks.

The early return for length <= 1 is not necessary.

The ++rooms is missing the semicolon.

Apart from that, it looks perfect.


Suggested refactorings of this Ruby time-to-string method? I have the following code that gets the difference in time between now and when an alarm is supposed to go off (i.e. "alarm goes off in 23 minutes, 56 seconds").

def time_to_alarm_in_words
  #AN EMPTY STRING WE WILL BE ADDING TO
  time_in_words = ''

  #THE TIME TO THE ALARM IN SECONDS
  total_seconds = (time - Time.now).to_i

  #SOME BASIC TIME UNIT VARIABLES
   days = total_seconds / 86400
   hours = (total_seconds / 3600) - (days * 24)
   minutes = (total_seconds / 60) - (hours * 60) - (days * 1440)
   seconds = total_seconds % 60

  #ONLY PROCEED IF THE TIME TO THE ALARM IS POSITIVE(I.E. IN THE FUTURE)
  unless total_seconds <= 0
    #BUILD A HASH WITH THE TIME UNTIL THE ALARM
    time_hash = {"days" => (total_seconds / 86400),
               "hours" => ((total_seconds / 3600) - (days * 24)),
               "minutes" => ((total_seconds / 60) - (hours * 60) - (days * 1440)),
               "seconds" => (total_seconds % 60)}

  #IF THE TIME SEGMENT IS POSITIVE, ADD IT TO THE STRING
  time_hash.each_pair do |time_segment,length|
    if value > 0

      #i.e. add "22 hours," to the empty string
      time_in_words << "#{length} #{time_segment},"
    end
  end

  #CHOP OFF THE TRAILING ','
  time_in_words.chop!

  #RETURN THE RESULT
  return time_in_words + " ago"
end

I have a feeling I could cut this down by half. Any suggestions?!

Courtesy of the clever helper method from this link:
https://stackoverflow.com/questions/4136248/how-to-generate-a-human-readable-time-range-using-ruby-on-rails

def humanize secs
  [[60, :seconds], [60, :minutes], [24, :hours], [1000, :days]].map{ |count, name|
    if secs > 0
      secs, n = secs.divmod(count)
      "#{n.to_i} #{name}"
    end
  }.compact.reverse.join(' ')
end

def time_to_alarm_in_words time
  #AN EMPTY STRING WE WILL BE ADDING TO
  time_in_words = ''

  #THE TIME TO THE ALARM IN SECONDS
  total_seconds = (time - Time.now).to_i

  time_in_words = humanize total_seconds

  #RETURN THE RESULT
  return time_in_words + " in the future"
end


Represent pairs of nonnegative integers using 2^a * 3^b Given the following exercise:

  Exercise 2.5

  Show that we can
  represent pairs of nonnegative
  integers using only numbers and
  arithmetic operations if we represent
  the pair a and b as the integer that
  is the product 2^a * 3^b. Give the
  corresponding definitions of the
  procedures cons, car, and cdr.

I wrote the following:

(define (cons a b) (* (expt 2 a)
                      (expt 3 b)))
(define (car x)
  (if (= 0 (remainder x 3))
      (car (/ x 3))
      (/ (log x)
         (log 2))))

(define (cdr x)
  (if (= 0 (remainder x 2))
      (cdr (/ x 2))
      (/ (log x)
         (log 3))))

What do you think?

Your definition of cons is perfect.

Your definitions of car and cdr contain the log operation, which is a floating-point operation.  Not only are its results imprecise, it is not needed to solve this problem.  Furthermore, notice that the two definitions look very similar to each other.  Whenever one sees a repeated pattern, one ought to consider factoring it out.

To address the above two concerns, one may write a helper function, log-x, which is a specialized log function that takes integer parameters x and n and returns integer p such that x ^ p * y = n, where x does not divide y.  Then, car and cdr may call log-x, with x being 2 and 3 respectively.

In the following implementation, I have renamed the definitions so they do not conflict with primitives.

(define (cons-np a b)
  (* (expt 2 a) (expt 3 b)))

(define (log-x x n)
  (if (= (remainder n x) 0)
      (+ 1 (log-x x (/ n x)))
      0))

(define (car-np np)
  (log-x 2 np))

(define (cdr-np np)
  (log-x 3 np))


Is it possible to condense this code? I have three functions, each assigned to an anchor tag which gets called onclick.

Is there a way to condense this code? It seems redundant to have three function calls which do the same thing except the value is different for each.

var winnings = 0;

function add20() {
    winnings += 20;
    document.getElementById("winnings").innerHTML = winnings;
}

function add40() {
    winnings += 40;
    document.getElementById("winnings").innerHTML = winnings;
}

function add60() {
    winnings += 60;
    document.getElementById("winnings").innerHTML = winnings;
}

You could just create one function, like this:

function add(x) {
    winnings += x;
    document.getElementById("winnings").innerHTML = winnings;
}

But if you need three different versions, you could always do this:

var winnings = 0;
function addX(x) {
    return function() {
        winnings += x;
        document.getElementById("winnings").innerHTML = winnings;
    }
}

var add20 = addX(20);
var add40 = addX(40);
var add60 = addX(60);

Or even more simply:

function add(x) {
    winnings += x;
    document.getElementById("winnings").innerHTML = winnings;
}
function add20() { add(20); }
function add40() { add(40); }
function add60() { add(60); }


Testing whether a matrix contains a submatrix As part 2 of my other question concerning this long running project I've been inquiring about on CR, I reimplemented my generic function for determining if an array of arrays is a sub-array or submatrix of a larger array of arrays.
I'm looking for advice on better implementation, ways to improve code clarity, advice on best practices and anything else that might be useful. This is my new implementation:

namespace MathAlgorithms

module ArrayFunctions =
    // Generic because it makes testing easier, yay math
    let IsSubMatrix (smallArray:'a[][]) (largeArray:'a[][]) (startCoordinate:(int * int)) =
        let searchHeight , searchWidth = smallArray.Length - 1 , smallArray.[0].Length - 1
        let startHeight  , startWidth  = startCoordinate

        try
            let WidthLoop heightIndex =
                let rec WidthLoopRec heightIndex widthIndex =
                    let largeValue = largeArray.[startHeight + heightIndex].[startWidth + widthIndex]
                    let smallValue = smallArray.[heightIndex].[widthIndex]

                    match ( smallValue = largeValue , widthIndex < searchWidth ) with
                    | ( true  , true  ) -> WidthLoopRec heightIndex (widthIndex + 1)
                    | ( true  , false ) -> true
                    | ( false , _     ) -> false
                WidthLoopRec heightIndex 0

            let HeightLoop () =
                let rec HeightLoopRec heightIndex =
                    let isMatch = WidthLoop heightIndex

                    match ( isMatch , heightIndex < searchHeight) with
                    | ( true  , true  ) -> HeightLoopRec ( heightIndex + 1 )
                    | ( true  , false ) -> true
                    | ( false , _     ) -> false
                HeightLoopRec 0

            HeightLoop ()

        with // Not really sure what I want to do with error handling atm
            | :? System.ArgumentOutOfRangeException -> false
            | :? System.ArgumentNullException       -> false
            | :? System.ArgumentException           -> false

I ran this code through my tests, and it's functionally the same as the old while-do version which I'm including for comparison's sake:

namespace MathAlgorithms

module ArrayFunctions =
    // Generic because it makes testing easier, yay math
    let SearchSubset (tSmallArray:'a[][]) (tLargeArray:'a[][]) (pCoordinate:(int * int)) =
        let tSmallHeight = tSmallArray.Length
        let tSmallWidth = tSmallArray.[0].Length

        let tHeightIndex = fst pCoordinate
        let tWidthIndex = snd pCoordinate
        let mutable tSmallHeightIndex = 0
        let mutable tSmallWidthIndex = 0
        let mutable tMatch = true

        try
            while ( tSmallHeightIndex < tSmallHeight - 1 ) && tMatch do
                while ( tSmallWidthIndex < tSmallWidth - 1 ) && tMatch do
                    let tLargeCurrentValue = tLargeArray.[tHeightIndex + tSmallHeightIndex].[tWidthIndex + tSmallWidthIndex]
                    let tSmallCurrentValue = tSmallArray.[tSmallHeightIndex].[tSmallWidthIndex]

                    if tSmallCurrentValue = tLargeCurrentValue then
                        tSmallWidthIndex <- tSmallWidthIndex + 1
                    else
                        tMatch <- false

                tSmallWidthIndex  <- 0
                tSmallHeightIndex <- tSmallHeightIndex + 1

            tMatch
        with
            | _ -> false

Github for further info:
https://github.com/Kenneth-Posey/LearningFsharp/tree/master/FsharpTutorial/YeFsharpLibrary
The use of the function is in the module FsharpImaging.fs, it's tested by UnitTest.fs and it's located in ArrayFunctions.fs.

A few suggestions regarding the style:

There's no need for parentheses in the pattern matching blocks. Those are evaluated as tuples by the very fact that they are comma separated:

match smallValue = largeValue, widthIndex < searchWidth with
| true, true  -> WidthLoopRec heightIndex (widthIndex + 1)
| true, false -> true
| false, _    -> false

and:

 match isMatch , heightIndex < searchHeight with
 | true, true  -> HeightLoopRec (heightIndex + 1)
 | true, false -> true
 | false, _    -> false

In HeightLoopRec, there's no need for isMatch. You can use the result of calling WidthLoop directly inside the pattern matching (maybe with parentheses to make it more legible):

match (WidthLoop heightIndex), heightIndex < searchHeight with

The function HeightLoop is not needed and can be removed and replaced by its contents, making HeightLoopRec the top level function. This is obvious by its signature (unit -> bool). It doesn't take anything as input, unlike its internal tail-recursive function whose signature is int -> bool.
WidthLoop can be inlined (let inline WidthLoop heightIndex =).
I think it would be better to handle the exceptions before getting into the actual computation. In fact, if the code base is done in F#, there should be no null values (as those would be replaced by option types). Within your code domain, illegal values should be made unrepresentable, as the famous motto goes.

This should also account for out-of-range indexing. If a mathematical operation makes no sense, the typing itself should not allow it to be made.

You could use FsCheck to test your code with random values to see that your code never raises exceptions. Logically, "no answer" should not be represented as false. If a function may return no value at all or a bool, then its return type should be bool option, where None would represent the lack of a valid result.
Your function name should probably reflect more clearly their intention. I'm not a mathematician, but I guess you would mean something like isRowContained (instead of WidthLoop), or whatever makes sense.


Selection Sort Algorithm (Node.js) I wanted to implement a selection sort and wanted to make sure that I'm doing it correctly. I wanted to do it in a way that's efficient and use recursion. Please let me know if I am doing this correctly or if there is a better way for me to do it.

 /**
 * selectionSort
 * @param toSort
 * @param sorted
 * @returns {Array}
 */
function selectionSort(toSort, sorted=[]) {
    if (!toSort.length) {
        return sorted;
    }
    let minIndex = findMinimum(toSort);
    sorted.push(...toSort.splice(minIndex, 1))
    return selectionSort(toSort, sorted);
}

function findMinimum(arr) {
    let minIndex=0;
    arr.forEach(function (item, index) {
        if(item < arr[minIndex]) {
            minIndex = index;
        }
    })
    return minIndex;
}

const testCase = [64, 25, 12, 22, 11]
const answer = selectionSort(testCase);

Review

findMinimum means to me that you find the minimum value in an array of items. Since your function returns the index instead, call it indexOfMinimum.
Prefer the use of const over let if you only assign a variable once: let minIndex = findMinimum(toSort); -> const minIndex = findMinimum(toSort);.
Use arrow notation to write more compact functions: function (item, index) -> (item, index) =>.
Your documentation seems like wasted space. If you document a public function (which is a good thing), put in some effort to write a clear description of the function, not just the name of the method copied.
Use whitespace to write more idiomatic javascript:

let minIndex=0; ->  let minIndex = 0;
if(item < arr[minIndex]) -> if (item < arr[minIndex])

Rewritten:

function selectionSort(toSort, sorted=[]) {
    if (!toSort.length) {
        return sorted;
    }
    const minIndex = indexOfMinimum(toSort);
    sorted.push(...toSort.splice(minIndex, 1))
    return selectionSort(toSort, sorted);
}

function indexOfMinimum(arr) {
    let minIndex = 0;
    arr.forEach((item, index) => {
        if (item < arr[minIndex]) {
            minIndex = index;
        }
    })
    return minIndex;
}


R function to generate predictions from ratings I am trying to improve the run time of a program I wrote in R. Generally, what I am doing is feeding a function a data frame of values and generating a prediction off of operations on specific columns. The function is a custom function that is being used with sapply (code below). What I'm doing is much too large to provide any meaningful example, so instead I will try to describe the inputs to the process. I know this will restrict how helpful answers can be, but I am interested in any ideas for optimizing the time it takes me to compute a prediction. Currently it is taking me about 10 seconds to generate one prediction (running the sapply for one line of a dataframe).

mean_rating <- function(df){
  user<-df$user
  movie<-df$movie
  u_row<-which(U_lookup == user)[1]
  m_row<-which(M_lookup==movie)[1]

  knn_match<- knn_txt[u_row,1:100]

  knn_match1<-as.numeric(unlist(knn_match))

  dfm_test<- dfm[knn_match1,]

  dfm_mov<- dfm_test[,m_row] # row number from DFM associated with the query_movie
  C<-mean(dfm_mov)

}

test<-sapply(1:nrow(probe_test),function(x) mean_rating(probe_test[x,]))

Inputs: dfm is my main data matrix, users in the rows and movies in the columns. Very sparse.

> str(dfm)
Formal class 'dgTMatrix' [package "Matrix"] with 6 slots
  ..@ i       : int [1:99072112] 378 1137 1755 1893 2359 3156 3423 4380 5103 6762 ...
  ..@ j       : int [1:99072112] 0 0 0 0 0 0 0 0 0 0 ...
  ..@ Dim     : int [1:2] 480189 17770
  ..@ Dimnames:List of 2
  .. ..$ : NULL
  .. ..$ : NULL
  ..@ x       : num [1:99072112] 4 5 4 1 4 5 4 5 3 3 ...
  ..@ factors : list()

probe_test is my test set, the set I'm trying to predict for. The actual probe test contains approximately 1.4 million rows but I am trying it on a subset first to optimize the time. It is being fed into my function.

> str(probe_test)
'data.frame':   6 obs. of  6 variables:
 $ X          : int  1 2 3 4 5 6
 $ movie      : int  1 1 1 1 1 1
 $ user       : int  1027056 1059319 1149588 1283744 1394012 1406595
 $ Rating     : int  3 3 4 3 5 4
 $ Rating_Date: Factor w/ 1929 levels "2000-01-06","2000-01-08",..: 1901 1847 1911 1312 1917 1803
 $ Indicator  : int  1 1 1 1 1 1

U_lookup is the lookup I use to convert between user id and the line of the matrix a user is in since we lose user id's when they are converted to a sparse matrix.

> str(U_lookup)
'data.frame':   480189 obs. of  1 variable:
 $ x: int  10 100000 1000004 1000027 1000033 1000035 1000038 1000051 1000053 1000057 ...

M_lookup is the lookup I use to convert between movie id and the column of a matrix a movie is in for similar reasons as above.

> str(M_lookup)
'data.frame':   17770 obs. of  1 variable:
 $ x: int  1 10 100 1000 10000 10001 10002 10003 10004 10005 ...

knn_text contains the 100 nearest neighbors for all the lines of dfm

> str(knn_txt)
'data.frame':   480189 obs. of  200 variables:

Does anyone have suggestions on how I could improve performance within R? Does anyone have other language suggestions? I am slightly familiar with Python so I've been looking into that one, but if anyone has specific tips on redoing this in Python I would be grateful as I'm very inexperienced with it.

Without exact your data I could think of some improvements.
Trying to avoid redundant operations.

# order data.frame by users and movies
probe_test <- probe_test[with(probe_test, order(user, move)), ]
# initialize resulting column
probe_test$res <- rep(as.numeric(NA), nrow(probe_test))

knn_txt_red <- knn_txt[, 1:100] # reduce outside of the loop
for (user in unique(probe_test$user)) { # for each unique user
  u_row <- which(U_lookup == user)[1] # get your id
  knn_match <- knn_txt_red[u_row, ]
  knn_match1 <- as.numeric(unlist(knn_match))
  userI <- probe_test$user == user
  movies <- probe_test$movie[userI] #get all user movies
  m_row <- which(M_lookup %in% movies) # get indexes
  dfm_mov <- dfm[knn_match1, m_row] #select all cols of those movies for user
  x <- colMeans(dfm_mov) # calculate mean for each row
  probe_test[userI, 'res'] <- x # add the results to data.frame
}

As I do not have your data, there are probably/maybe some errors in code.

There are probably better ways to do this, but as I mentioned, it is hard to think of any without any example data.


Composing CPU instructions by merging four short hex strings My code shares some values with its neighbor. The names "Instructions, Registers" can be ignored in the comments; just see them as "names". What's important is how they are shared, which can be seen in the calculations.

What I want is to improve this code, because it looks awful and one can barely understand what's going on.

hexShared = {"80","3E","14"}; //lwz r31, -0x0018(r20)

    //Merge Hex Values that are shared (Basically every other is shared with the next one except the Address)
    private static string mergeHex(string[] hexShared)
    {

        //[ ][ ][ ][ ]
        //[0  1][2  3]
        string s1 = hexShared[0]; //Instruction
        string s2 = hexShared[1]; //Register 1
        string s3 = hexShared[2]; //Register 2

        char c1 = s1[1]; //Instruction Shared with Register 1
        char c2 = s2[0]; //Register 1 Shared with Instruction
        char c3 = s2[1]; //Register 1 Shared with Register 2
        char c4 = s3[0]; //Register 2 Shared with Register 1
        char c5 = s3[1]; //Register 2

        string hex = AddHex(c1, c2);

        string hex2 = AddHex(c3, c4);

        hex = s1[0] + hex + hex2 + c5;

        return hex;
    }

I will try explain with an example (though I barely get it myself).

We have a Hexdecimal of 8 characters (that's the structure always).

83340247

Now we can split it up, the last 4 are the "Address" and it can be taken out.
So what remains are Hexdecimals that share values.

8334

Now for example the code:

lwz r0, 0x0000(r0)

will translate to: 80000000
So lwz == "8" here.

lwz r1, 0x0000(r0) == 80200000

So the first "r1" equals "2" right?

lwz r1, 0x0000(r1) == 80210000

It all looks fine, everything is separated, the other "r1" is simply "1".

Now here is the dilemma, when they reach values higher than one Hexdecimal can represent.

lwz r1, 0x0000(r31) == 803F0000
lwz r31, 0x0000(r31) == 83FF0000

So as you can see, when they increase size, they will Add into the place "Left" of their starting point.
So r1 (which is 2) will become "3" when the second "r31" becomes large enough so it needs to use that space.

I suck at explaining but i hope this Examples helps a bit at least:)

    //Convert Hex in String to Integer
    public static int HexToInt(string Hex)
    {
        return int.Parse(Hex, NumberStyles.AllowHexSpecifier);
    }

//Sum Two Hex Chars and return it as Hex String (1 character)
        public static string AddHex(char hex1, char hex2)
        {
            int i1 = HexToInt(hex1.ToString());
            int i2 = HexToInt(hex2.ToString());
            int sum = i1 + i2;
            return sum.ToString("X1");
        }

Assembly opcodes are not constructed with string manipulations. They are very carefully designed with bit positioning, so a simple add operation between two integers might not be the best way to describe it.

So your mergeHex method that god-knows-what does with strings should become a method that might do some bit shifting, masks, ...

I sampled the behavior of your mergeHex with two calls (which is not enough to know what it does for all your possible scenarios), but anyway I reached the following conclusion:

The output is a 16bits (word) hex string.
The first 8 bits are given by hexShared[0] | ((hexshared[1] & 0xF0) >> 4)
The last 8 bits are given by  ((hexshared[1] & 0x0F) << 4) | values[2]

Turning this into an algorithm becomes now trivial, let me suggest an implementation with some simplifications:

private static string ToWord(string[] hexTokens){
    var values = hexTokens
        .Select(t => HexToInt(t))
        .ToArray();

    var result = values[0] << 8 | values[1] << 4 | values[2];
    return result.ToString("X1");
}


Javascript Parallax Scrolling Text I built a 404 page which involves parallax scrolling text. The program updates the position of 100-200 text nodes at each animation frame called with window.requestAnimationFrame. It runs decently well on my MacBook (although it occupies significant CPU), but on weaker computers like my phone, it runs very sluggishly.

How can I optimize my code to achieve better performance?

var scene;

function randint(low, high) { // Return a random integer between low and high
  return Math.floor(( Math.random()*(high-low) ))+low;
}

// Add a layer to the scene

function addLayer() {
  // Make  a "layer" in the parallax animation
  var layer = document.createElement("div");
  // Give it a random Z value (0 to 1)
  layer.setAttribute("class", "layer");
  layer.setAttribute("data-z", Math.random().toFixed(2));

  // Make a div inside that says "404"
  layer.appendChild(document.createTextNode("404"));
  // Random X position
  layer.style.left = randint(-10, window.innerWidth) + "px";
  // Below bottom of screen
  layer.style.top = window.innerHeight + "px";
  // Font size and weight based on Z value
  var z = parseFloat(layer.getAttribute("data-z"));
  layer.style.fontSize = Math.floor(z * 150) + "px";
  layer.style.fontWeight = Math.ceil(z * 4) * 100;
  // Random opacity
  layer.style.opacity = (Math.random() / 10).toFixed(2);

  // Add nodes to appropriate parents
  scene.appendChild(layer);
}

function updatePositions() {
  var layers = scene.getElementsByTagName("div");
  var layer, div, z;
  for (var i = 0; i < layers.length; i++) {
    layer = layers[i];
    z = parseFloat(layer.getAttribute("data-z"));
    y = parseInt(layer.style.top.slice(0, layer.style.top.length - 2));
    layer.style.top = (y - Math.ceil(z * 10)).toFixed(2) + "px";

    if (y < (-150)) { // Max fontsize is 150px
      scene.removeChild(layer);
    }
  }
}

function updateColor() {
  var hue = (parseFloat(document.body.getAttribute("data-hue")) + 0.25) % 360;
  document.body.setAttribute("data-hue", hue.toString());
  var hex = chroma(hue, 1, 1, "hsv").brighten().hex();
  document.body.style.color = hex;
  document.getElementsByTagName("a")[0].style.backgroundColor = hex;
}

function update() {
  addLayer();
  updatePositions();
  updateColor();
  window.requestAnimationFrame(update); // Recur
}

scene = document.getElementById("scene");
window.requestAnimationFrame(update);
body {
  background-color: #222;
  margin: 0;
  width: 100vw;
  height: 100vh;

  /* Global font settings */
  color: #fff;
  font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
}

#scene {
  position: fixed;
  top: 0;
  left: 0;
  padding: 0;
  margin: 0;
  width: 100%;
  height: 100%;
  overflow: hidden;
}

.layer {
  position: absolute;
}

.main {
  position: fixed;
  top: 0;
  left: 0;
  width: 100%;

  text-align: center;

  opacity: 0.5;
}

h1 {
  font-size: 200px;
  margin-bottom: 0;
}

.main p {
  font-size: 150%;
  margin-top: 0;
}

.main a {

  color: #222;
  background-color: #fff;
  padding: 10px;

  text-decoration: none;
  font-size: 150%;
  font-weight: 600;
}

404

That page couldn't be found.

    Home

Running this snippet in full window will more accurately emulate how it will appear on my website.

Here's a JSFiddle if it's preferred.

According to my experience, web animations don't use CPU as such, but rather prefer the GPU at times for rendering. On phones, custom animations like yours will run without any moderation of fps, and so a lag is kinda expected. On top of it, js doesn't use parallel threads of course, so it won't even use the remaining core if they are available.

What I'd suggest is use some good library to run these. I remember using Three.js and it ran on my Lumia 520 at 8FPS but still without lag, as the animation was optimized for low FPS. The same ran on my PC at 60FPS smoothly just the same.

Hope this helps.