How can I modify my graph traversal algorithm to increase efficiency? I have an adjacency matrix "A" which I am using to represent a graph for a social network. Each node of the graph represents a person's name, and I am storing people's names in an 2-d array (the index of the person's name in the array is the same as the node's row index in the adjacency matrix). I wrote an algorithm to return the neighbors of node in the graph that are at most x nodes away from the node (the indices of the neighbor nodes will be stored in a binary tree and the root of the tree will be returned) but the algorithm is inefficient and takes 1-2 minutes or so to return the output, albeit a correct one. I would appreciate some advice on how to optimize this algorithm.

b_tree *get_friends(b_tree *root, int x, int y, char a_name[50] int dim) {
    /* root is root if b-tree containing pointers to the neighbors */
    /* a_name is the name of a person in the graph (want to get the neighbors of this node)*/
    /* x is maximum distance the neighbor can be from the node */
    /* y is used to keep track of x and is always 0 and dim is the length/width of matrix */
    /* M is a global variable for the matrix */
    /* name_search searches the tree and returns NULL if the index is already in the tree (to prevent duplicates) */
    /* friend_list is a global array containing the names of all the nodes in the graph (including a_name) */
    /* retrieve_ind returns the index of the user name in the the friend_list array */
    if (x == y - 1) return root;
    int r = retrieve_ind(a_name);
    for (int a = 0; a < dim; a++) {
        if (M[r][a] > 0) {
            if (name_search(root, a) == NULL) root = insert_in_tree(root, a);
            root = get_friends(root, x, y + 1, friend_list[a], dim);
        }
    }
    return root;
}

You can multiply the adjacency-matrix n times to get all paths of length n between any nodes. Therefore, if you multiply A^n * vector_with_only_your_startVertex, you can see in the resulting vector which nodes can be reached.
Make sure to also safe nodes that can be reached in less steps, because for example there may be cases where a node may be reached in 2, but not in 3 steps.
Also make sure your multyplying right-associatively, as matrix-vector multiplication is way faster than matrix-matrix multiplication.

I have no clue if this is faster though. Depends if you have a well-written matrix multiplication program that does not compute unnecessary zero-rows.

You can also always use Dijkstra's algorithm for that, in this case every edge has weight 1.
Also I don't understand why you are saving your result in a tree-structure. Unless you rely on an ordering of the elements of your result (which I guess you don't), you can use a hash-based set, which has access-time of O(1) and not O(log(N)) like trees do.


How to automatically insert HTML to a form and obtain the inputs? For a form I got the markup below, it belongs to an input category and as there can be more than one insertion at it I includded an Añadir button (Add).

I give id="posgrado1" to first div and using Java Script I increment the id's to posgrado2, posgrado3, ... posgrado#n

    Estudios de Posgrado

        <select class="form-control inputPosgradoTipo">
            <option>Especialidad</option>
            <option>Maestría</option>
            <option>Doctorado</option>
        </select>

        <input type="text" class="form-control inputPosgradoTitulo" placeholder="Título">

        <input type="text" class="form-control inputPosgradoCedula" placeholder="Cédula">

        <input type="button" class="form-control btnAñadirPosgrado" value="Añadir">

Each html within a class got a class identifying the type of input.

So far this is how I add more input instances:

numPosgrados = 1

function agregarPosgrado () {

    var markupPosgrado="";
    markupPosgrado += "
";
    markupPosgrado += "                        ";
    markupPosgrado += "                        <\/label>";
    markupPosgrado += "";
    markupPosgrado += "
";
    markupPosgrado += "                            <select class=\"form-control inputPosgradoTipo\">";
    markupPosgrado += "                                <option>Especialidad<\/option>";
    markupPosgrado += "                                <option>Maestría<\/option>";
    markupPosgrado += "                                <option>Doctorado<\/option>";
    markupPosgrado += "                            <\/select>                ";
    markupPosgrado += "                        <\/div>";
    markupPosgrado += "";
    markupPosgrado += "
";
    markupPosgrado += "                            <input type=\"text\" class=\"form-control inputPosgradoTitulo\" placeholder=\"Título\">                        ";
    markupPosgrado += "                        <\/div>";
    markupPosgrado += "";
    markupPosgrado += "
";
    markupPosgrado += "                            <input type=\"text\" class=\"form-control inputPosgradoCedula\" placeholder=\"Cédula\">";
    markupPosgrado += "                        <\/div>";
    markupPosgrado += "";
    markupPosgrado += "                    <\/div>";

    $("#posgrado"+(numPosgrados-1)).after(markupPosgrado)
}

For getting the information I'd like to return a JSON, like:

function obtenerPosgrados () {

    return {EachInstance: {eachInputTypesForEach}}
}

This is an example fiddle.

What's a better implementation of this?  Can I take more advance of jQuery or any other JavaScript library?

A better way is to use templates. Handlebars should be a good start for this.

Here's a quick demo:

HTML:

JS:

// The data.
var data = {
  people : [
    {
      id : 1,
      name : 'Alice'
    },{
      id : 2,
      name : 'Bob'
    }
  ]
};

// We get the template HTML
var template = $('#template').html();

// Compile it as a handlebars template renderer
var renderer = Handlebars.compile(template);

// and just feed in the data into the renderer to return the HTML with the data
var html = renderer(data);

// Then all we need to do is pop-in the HTML with the data to our page
$('#container').html(html);

The rest is up to you. You can use the demo as your guide. You can use the id of the data as your n. Handlebars also provides you the index if you loop through an array in the template, which you could also use as your n.


A dropdown box that toggles the textbox Is there a way to improve the Javascript that I wrote in this code? I made a dropdown box that toggles between showing and hiding the textbox. I then realize that the Jquery/Javscript code I was writing began to repeat itself.

Just want to know if there is a way to simplify the Javascript/JQuery that I wrote.

Is there a way to improve the Javascript that I wrote in this code? I made a dropdown box that toggles between showing and hiding the textbox. I then realize that the Jquery/Javscript code I was writing began to repeat itself.

Just want to know if there is a way to simplify the Javascript/JQuery that I wrote.

$(document).ready(function() {
  $("body").css("background-color", "yellow");

  $("#dropdown1").on('click', function() {
    $('#menu1').slideToggle();
    var arrow = $("div.arrow");
    arrow.toggleClass("right");
    arrow.toggleClass("down");
  });
  $("#dropdown2").on('click', function() {
    $('#menu2').slideToggle();
    var arrow = $("div.arrow2");
    arrow.toggleClass("right2");
    arrow.toggleClass("down2");
  });
});
body {
  background-color: #333;
}

.wrapper {
  max-width: 1024px;
  display: block;
  margin: 0 auto;
  background-color: #ffffff;
  padding: 5px 20px;
}

div.container {
  max-width: 90%;
}

.arrow,
.arrow2,
.arrow3 {
  /*    float: left;*/
  display: inline-block;
  border: solid black;
  border-width: 0 3px 3px 0;
  padding: 4px 4px 4px 4px;
  margin: 0 0 0 10px;
}

.down,
.down2 {
  transform: rotate(45deg);
  -webkit-transform: rotate(45deg);
  margin: 0 0 2px 10px;
}

.up {
  transform: rotate(-135deg);
  -webkit-transform: rotate(-135deg);
  margin: 0 0 -4px 10px;
}

.right,
.right2,
.right3 {
  transform: rotate(-45deg);
  -webkit-transform: rotate(-45deg);
  margin: 0 0 0px 10px;
}

#menu1,
#menu2,
#menu3 {
  display: none;
}

.title {
  padding: 5px 0 5px 10px;
  display: inline-block;
}
<!DOCTYPE html>

  <link href="style.css" rel="stylesheet" type="text/css">
  <title></title>

Dropdown 1

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
            irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Dropdown 2

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
            irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

In this case the answer is very straight-forward if you want to keep things in plain ol' jQuery.  Instead of selecting on ids, use classes and rely upon a well structured dom (which you already have):

$(document).ready(function() {
  $("body").css("background-color", "yellow");

  $(".dropdown_with_toggle").on('click', function() {
    var el = $(this);
    $('.menu', el).slideToggle();
    var arrow = $(".arrow", el);
    arrow.toggleClass("right");
    arrow.toggleClass("down");
  });
});

Then adjust your HTML slightly:

<!DOCTYPE html>

  <link href="style.css" rel="stylesheet" type="text/css">
  <title></title>

Dropdown 1

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
            irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Dropdown 2

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
            irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

They key is that the class dropdown_with_toggle is not being used for styling but rather to guide your javascript.  You listen for click events on all elements with that class, and then you take action not by finding elements by id, but by finding children of your main element by class.  That is what the $('.menu', el) syntax does: it finds the selector but only looks for descendants of a given element.  It's effectively just an alternate syntax for the jQuery .find() method, which would work equally well here.

Just because: the next step is to not attach your listeners directly to the elements but instead use deferred listeners on a mutual parent:

$('.container').on( 'click', '.dropdown_with_toggle', function(){ } )

The rest of your code doesn't change, but the advantage this notation has is that if you add or remove elements dynamically, you don't have to re-register any listeners (as long as you are only modifying elements inside your container div, and the container div isn't removed).  I used to use this trick often with dynamic pages that are loaded/reloaded via ajax.


Construct binary tree from inorder and postorder traversal The problem is taken from here.  The tree is guaranteed not to have duplicate elements.

My questions is, instead of creating new arrays leftInOrder, rightInOrder, leftPostOrder, rightPostOrder, I could simply pass the indexes to the same input arrays to the recursive function. Does that help in any way?

Basically, any way Java would pass the entire array by value to the recursive function, creating new arrays and passing them only would reduce the load on the stack. I would like to know if this is the best method.

    import java.util.Arrays;
    public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null || inorder.length<1)return null;
        int rootVal=postorder[postorder.length-1];
        TreeNode root= new TreeNode(rootVal);

        int mid=0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==rootVal){
                mid=i;
                i=inorder.length;
            }
        }

        int leftCount=mid;

        int[] leftInOrder= Arrays.copyOfRange(inorder,0,mid);
        int[] rightInOrder= Arrays.copyOfRange(inorder,mid+1,inorder.length);

        int[] leftPostOrder= Arrays.copyOfRange(postorder,0,leftCount);
        int[] rightPostOrder= Arrays.copyOfRange(postorder,leftCount,postorder.length-1);

        root.left=buildTree(leftInOrder,leftPostOrder);
        root.right=buildTree(rightInOrder,rightPostOrder);

        return root;

    }
}

Before tackling the algorithmic issues of your code, lets start with a review of your coding style.

Use proper spacing and indentation

When reviewing, or coming back to code, the readability of the code is very valuable in order to understand the code and to correctly change it. Two very important aspects of this readability is how you indent your code and where you your new lines.

Lets review the start of your code:

public class Solution {
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder==null || inorder.length<1)return null;
    int rootVal=postorder[postorder.length-1];
    TreeNode root= new TreeNode(rootVal);

    int mid=0;
    for(int i=0;i<inorder.length;i++){
        if(inorder[i]==rootVal){
            mid=i;
            i=inorder.length;
        }
        ...
}
}

I have the following issue with this segment of code:

The classes Solution and TreeNode are at same indentation – This indicates that this classes are defined side by side, which is not unnatural, but then the Solution class seems to miss its implementation. So given they are not defined side-by-side it seems like a compilation error, until you scan a lot more code and realizes that TreeNode is actually an internal class of Solution.
TreeNode seems to only have 4 members – The way it is written it seems like it has 4 members, and no constructor or methods. Yet again closer inspection reveals that the last parameter isn't a parameter, but actually a constructor with single inline code block.
The buildTree appears at same level as class definitions – This kind of seems like you have a third class, next to Solution and TreeNode, but it misses the class keyword and has parameters? Oh shoot, it's a method belonging to TreeNode? No, it belongs to Solution but returns a TreeNode.
Confusing start of buildTree – Ordinarily a method starts with some declaration of local variables, but your first variable is an if statement hiding an early return. This block uses neither braces nor newlines to indicate this block, and is disguised if you don't have a trained eye.
Inline statements are too compressed – Adding spaces around operators, and after commas can open up your statements a lot. Compare for(int i=0;i<inorder.length;i++){ to for (int i = 0; i < inorder.length; i++) {. Try to think of the statements as sentences where the different parts are words. ItIsNotVeryEasyToReadWithoutSpaces!

Correcting for all of the above you'll end up with this code:

public class Solution {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length < 1) {
            return null;
        }

        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);
        int mid=0;

        for(int i = 0; i < inorder.length; i++){
            if (inorder[i] == rootVal) {
                mid = i;
                i = inorder.length;
            }
        }
        ...
    }
}

This still has some issues, like it doesn't actually check if postorder is not null or has values. But it shows the increase of readability where the only change I've made is to add spaces, correct indentation and add one set of braces.

Algorithmic considerations

In the text of your question you state that Java would pass the entire array by value, which is not correct. If you read Is Java “pass-by-reference” or “pass-by-value”?, you'll see that when passing arrays it's actually the value of the reference to the array which is passed. This allows for the array to be internally dereferenced (and possibly have the array values changed) within the method it is passed to. (It also allows for you to overwrite the array internally, without affecting the external array, but that is another history. Read the accepted answer to the link carefully, and you'll see the difference)

In other words, your suggestion of passing indices will be a much better solution, than the current one. The current one creates loads of extra arrays which it shuffles around making the space requirement of your code grow exponentially (doubling for each recursion). If you passed indices, you would only require space for the extra tree nodes.

So I would rewrite the buildTree into two separate functions something like:

public TreeNode buildTree(int[] inorder, int[] postorder) {
    return buildTree(inorder, postorder, 0, inorder.length);
}

private TreeNode buildTree(int[] inorder, int[] postorder, int left, int right) {
    ... your revised code here ...
}

I would also strongly consider adding some documentation and comments here and there to further enhance and explain what your code is supposed to do!


Multiplying numpy arrays I have written a function to multiply two numpy arrays.
def ra(self):
    """Multiply Rotation with initial Values"""
    rva = self.r_array() * self.va_array()
    rva = np.sum(rva, axis=1)  # Sum rows of Matrix
    rva = np.array([[rva[0]],  # Transpose Matrix
                    [rva[1]],
                    [rva[2]]])

where:

r_array has 3 rows and 3 columns
va_array has 3 rows and 1 column

I feel like this should be able to be written in one line. However, self.r_array() * self.va_array() always returns a 3 x 3 array.
Any suggestions would be greatly appreciated.
Cheers

Actually the * operator does element-wise multiplication. So you need to use .dot() function to get the desired result.
Example :
import numpy as np

a = np.array([[1,2,3],
    [4,5,6],
    [7,8,9]])

b =  np.array([[1]
    ,[2],
    [3]])
print(a * b)
print(a.dot(b))

output :
[[ 1  2  3]
 [ 8 10 12]
 [21 24 27]]
[[14]
 [32]
 [50]]

Observe that when I have used * operator, every column in a is multiplied with b element-wise


Ruby on Rails - Creating many models associated with another one So I have the following models:

class Poll < ApplicationRecord
    validates :title, presence: true, allow_blank: false
    validates :options, presence: true

    has_many :options, dependent: :destroy
end

class Option < ApplicationRecord
    validates :title, presence: true, allow_blank: false

    belongs_to :poll
end

And given the following data:

{
    title: "My poll",
    options: [
        {title: "Option 1"},
        {title: "Option 2"},
        {title: "Option 3"},
    ]
}

I would like to create a poll with 3 options.

This is my solution:

    # POST /polls
    def create
        @poll = Poll.new(poll_params)

        params[:options].each do |option|
            @poll.options.new option.permit(:title)
        end

        if @poll.save
            render json: @poll, status: :created, location: @poll
        else
            render json: @poll.errors.full_messages, status: :unprocessable_entity
        end
    end

You should be able to do this with accepts_nested_attributes_for.
  see https://api.rubyonrails.org/classes/ActiveRecord/NestedAttributes/ClassMethods.html#method-i-accepts_nested_attributes_for

class Poll < ApplicationRecord
    validates :title, presence: true, allow_blank: false
    validates :options, presence: true

    has_many :options, dependent: :destroy
    accepts_nested_attributes_for :options
end

def poll_params
  params.require(:poll).permit(:title,
                               options: :title)
end

def create
    @poll = Poll.new(poll_params)

    if @poll.save
        render json: @poll, status: :created, location: @poll
    else
        render json: @poll.errors.full_messages, status: :unprocessable_entity
    end
end


Server side validations and unit testing in MVP We are following passive controller approach and when user clicks on submit, server side validations are fired. There are many other fields on the screen that needs to be validated.

I would like to get feedback about the following approach.

Is it ok to have validations in Presenter.
As there are many fields in UI, PerformServerValidations() method is getting big. Is there any way I could refactor it.
Intention behind declaring PerformServerValidations() as public and returning a IList is to be able to test it. Is it a good approach to take?

[TestMethod]
public void Presenter_PerformServerValidations_ValidateFromCustomerId_ExpectFalseForInvalidNumber()
{
    //creating presenter
    presenter.View.Stub(x=>x.FromCustomerId).Return("one two three");

    var errorCodes = presenter.PerformServerValidations();

    Assert.IsTrue(errorCodes.Contains("ERR_InvalidFromCustomerId"));
}

Presenter.cs

public void OnSubmit()
{
    var serverValidationErrors = PerformServerValidations();
    this.View.ServerErrors = serverValidationErrors ; // View.ServerErrors will loop over the list and sets validator's IsValid property to false
    if(!serverValidationErrors.Any())
    {
         BindCustomers();
    }
}

public IList<string> PerformServerValidations()
{
   var errorCodes = new List<string>();

   int parsedFromCustomerId;
   int parsedToCustomerId;

   bool isValidFromCustomerId = int.TryParse(this.View.FromCustomerId, out
parsedFromCustomerId);
   bool isValidToCustomerId = int.TryParse(this.View.ToCustomerId, out parsedToCustomerId);

   if(!string.IsNullOrWhiteSpace(this.View.FromCustomerId) && !isValidFromCustomerId)
   {
       errorCodes.Add("ERR_InvalidFromCustomerId");
   }

   if(!string.IsNullOrWhiteSpace(this.View.ToCustomerId) && !isValidToCustomerId)
   {
       errorCodes.Add("ERR_InvalidToCustomerId");
   }

   if((!string.IsNullOrWhiteSpace(this.View.FromCustomerId) && !string.IsNullOrWhiteSpace(this.View.FromCustomerId) && (isValidFromCustomerId && isValidFromCustomerId))
   {
       if(parsedFromCustomerId > parsedFromCustomerId)
       {
           errorCodes.Add("ERR_InvalidCustomerIdRange");
       }
   }

   //There are many other fields to be validated
   return errorCodes;
}

I think you have a typo in the last outside if statement, I assume you meant two different variables when you wrote this:

if((!string.IsNullOrWhiteSpace(this.View.FromCustomerId) && !string.IsNullOrWhiteSpace(this.View.FromCustomerId) && (isValidFromCustomerId && isValidFromCustomerId))
{
    if(parsedFromCustomerId > parsedFromCustomerId)
    {
        errorCodes.Add("ERR_InvalidCustomerIdRange");
    }
}

parsedFromCustomerId will never be greater than parsedFromCustomerId

and the obvious one that won't cause a bug but probably won't give you the intended results is

 (isValidFromCustomerId && isValidFromCustomerId)

I assume you mean to put a different boolean variable in there instead of the same one twice.

this code won't function, correctly.

probably a Typo but you should proofread your code again just to make sure.


Yaw (Z-rotation) angle linear interpolation without quaternions I need to write a function performing linear interpolating between two Euler angles in 2D, perfectly without the use of quaternions as conversion seems to be an overkill for such a simple task.

Here's what I came up with:

// Calculate difference on a wrapped number line
function difference(a, b, width) {
  const d = a - b;
  const ad0 = Math.abs(d);
  const ad1 = width - ad0;

  if (ad1 < ad0)
    return -Math.sign(d) * ad1;

  return d;
}

Number.prototype.mod = function(n) {
  return ((this % n) + n) % n;
};

const fullAngle = 2 * Math.PI;

// Linear interpolation
function slerp(a, b, t) {
  a = a.mod(fullAngle);
  b = b.mod(fullAngle);

  return (a + difference(b, a, fullAngle) * t).mod(fullAngle);
}

function toRadians(a) {
  return a * Math.PI / 180.0;
}

function toDegrees(a) {
  return a * 180.0 / Math.PI;
}

document.write(toDegrees(slerp(toRadians(20), toRadians(350), .25)));

The expected output is an angle linearly interpolated from one angle to another using specified t value.

In the example above the output is correct:
The smallest angle difference between 350° and 20° is 30° (-30° with a sign).

20° + (-30°) * .25 = 20° - 7.5° = 12.5°

Is the code above correct?
Could it be simplified?

Finding shortest angular distance.
I have always found the method of normalising angles with
const PI2 = Math.PI * 2;
var angle = ((angle % PI2) + PI2) % PI2;

and then finding the shortest angular distance a little bit hacky. This is even more so when the angles are originally vectors.
Cross and dot products.
Math.asin of the cross product of two vectors gives the angle left or right of first vector in the range -90 to 90 deg and the sign of the dot product will indicate if the vectors are in the same direction or not letting you get the quadrant the second vector is in and thus the shortest angular direction from one vector to the next.
The results are always relative to the direction of the first vector so you dont need to normalise the angle to 0 -Math.PI * 2
Polar to cartesian
As you want to work in angles (polar) you just need the extra step of calculating the cartesian vectors.
The function to find the shortest angular distance between any two bearings (angles).
// a and b are angles in radians
// returns direction in radians
function shortestAngle(a,b){
    const ax = Math.cos(a); // create vector a
    const ay = Math.sin(a);
    const bx = Math.cos(b); // create vector b
    const by = Math.sin(b);

    // asin cross product to find angle
    const angle = Math.asin(ax * by - ay * bx);

    // and dot to help find the quadrant
    const dot = (ax * bx + ay * by);

    // if facing in different direction dot < 0 angle will be
    // over 90 or under -90 else between  90 and -90
    return dot < 0 ? Math.sign(angle) * Math.PI - angle : angle;
}

Then to interpolate you just scale the result of the above function
// a is start angle
// angDist is angular distance
// time is time in range 0 to 1
function slerp(a, angDist, time) {
    return angDist * time + a;
}

Gives in my view, a cleaner less hacky solution.
 // using
 var angle1 = ?
 var angle2 = ?
 var angDist = shortestAngle(angle1, angle2);
 var angle = slerp(angle1, angDist, time);

Which is even better if you are already working with vectors rather than angles.


Identical jQuery autocomplete handlers for two form fields I do need to use jquery autocomplete for two inputs. But I have use same processing script for these two elements.

At this stage I am doing it like this.

    $("#suburb").autocomplete({
    source: function(request, response) {
        $.ajax({
            url: "includes/state_au_ajax.php",
            dataType: "json",
            method: "post",
            data: {
                term : request.term,
                state : $("#state").val()
            },
                        success: function( data ) {
                             response( $.map( data, function( item ) {
                                var code = item.split("|");
                                return {
                                    label: code[0],
                                    value: code[0],
                                    data : item
                                }
                            }));
                        }
        });
    },
    autoFocus: true,
    minLength: 2,
      select: function( event, ui ) {
            var output = ui.item.data.split("|");
            $('#zip_code').val(output[1]);
        },
    delay: 300
  });

    // --- Populate ZIP code according to the value of "Suburb"
    $("#p_suburb").autocomplete({
    source: function(request, response) {
        $.ajax({
            url: "includes/state_au_ajax.php",
            dataType: "json",
            method: "post",
            data: {
                term : request.term,
                state : $("#p_state").val()
            },
                        success: function( data ) {
                             response( $.map( data, function( item ) {
                                var code = item.split("|");
                                return {
                                    label: code[0],
                                    value: code[0],
                                    data : item
                                }
                            }));
                        }
        });
    },
    autoFocus: true,
    minLength: 2,
      select: function( event, ui ) {
            var output = ui.item.data.split("|");
            $('#p_zip_code').val(output[1]);
        },
    delay: 300
  });

My question is, Can I write this without any code duplication?

You can create separate function like this:

function autoComplete($obj, $valueObj, $zipValue){
        $obj.autocomplete({
            source: function(request, response) {
                $.ajax({
                    url: "includes/state_au_ajax.php",
                    dataType: "json",
                    method: "post",
                    data: {
                        term : request.term,
                        state : $valueObj.val()
                    },
                                success: function( data ) {
                                     response( $.map( data, function( item ) {
                                        var code = item.split("|");
                                        return {
                                            label: code[0],
                                            value: code[0],
                                            data : item
                                        }
                                    }));
                                }
                });
            },
            autoFocus: true,
            minLength: 2,
              select: function( event, ui ) {
                    var output = ui.item.data.split("|");
                    $zipValue.val(output[1]);
                },
            delay: 300
          });
    }

And then call it appropriately:

    autoComplete($("#suburb"), $("#state"), $('#zip_code'))
    autoComplete($("#p_suburb"), $("#p_state"), $('#p_zip_code'))


Linear Interpolation for sorted arrays I have made a linear interpolation functions as a side project of mine. It assumes everything is sorted before hand - x and f(x) are the same length.

I would like to ask for:

general recommendations
if I can improve the design (generalize it to all iterables like std::array etc...)
and for further performance optimizations.

#include <algorithm>
#include <cmath>
#include <type_traits>
#include <vector>

#if (__cplusplus < 202002L)
template <typename T,
          typename = std::enable_if_t<std::is_floating_point<T>::value>>
T lerp(T a, T b, T t) noexcept {
  return a + t * (b - a);
}
#else
using std::lerp;
#endif

template <typename T,
          typename = std::enable_if_t<std::is_floating_point<T>::value>>
class ListLerp {
 public:
  explicit ListLerp(const std::vector<T>& xp, const std::vector<T>& yp)
      : xp(xp), yp(yp) {
    b = this->xp.begin() + 1;
  }

  [[nodiscard]] T interp(const T x) noexcept {
    // No extrapolation
    if (x <= xp.front()) return yp.front();
    if (x >= xp.back()) return yp.back();

    // b = xp.begin() + 1;

    // find b position
    while (x > *b) b++;

    // Calculate a, a_y, b_y from b
    const auto a = b - 1;
    const auto a_y = yp.begin() + (a - xp.begin());
    const auto b_y = yp.begin() + (b - xp.begin());

    const auto t = (x - *a) / (*b - *a);

    return lerp(*a_y, *b_y, t);
  };

 private:
  typename std::vector<T>::const_iterator b;
  const std::vector<T>& xp;
  const std::vector<T>& yp;
};

template <typename T,
          typename = std::enable_if_t<std::is_floating_point<T>::value>>
std::vector<T> interp(const std::vector<T>& xp, const std::vector<T>& yp,
                      const std::vector<T>& x) {
  std::vector<T> out(x.size());

  auto lLerp = ListLerp(xp, yp);

  std::transform(x.begin(), x.end(), out.begin(),
                 [&lLerp](const auto& xi) { return lLerp.interp(xi); });

  return out;
}

///////////////
int main() {
  std::vector<double> xp = {1, 2, 3};
  std::vector<double> fp = {3, 2, 0};

  for (auto &i : interp(xp, fp, {1, 1.5, 2.72})){
    std::cout << " " << i;
  }
  std::cout << "\n";

}

template <typename T,
          typename = std::enable_if_t<std::is_floating_point<T>::value>>
T lerp(T a, T b, T t) noexcept;

Looks fine.  I'd prefer to see static_assert than enable_if since there's no other overloads (and if there are I'd rather fine out with a compilation error).

T lerp(T a, T b, T t) noexcept {
  return a + t * (b - a);
}

How about std::fma?

Note that GCC and Clang both do this differently...  They do b * t + a * (1-t) and have special cases for t at 0 and near 1.  Maybe it's better to just copy their code exactly so the compiler version doesn't change the output?

template <typename T,
          typename = std::enable_if_t<std::is_floating_point<T>::value>>
std::vector<T> interp(const std::vector<T>& xp, const std::vector<T>& yp,
                      const std::vector<T>& x);

There's nothing in this function that directly needs T to be a floating point type.  I think it's better to remove the enable_if and let the compiler show a traceback with the "real" reason T needs to be an FP.

This function takes vectors and returns a new vector.  That is a fine and very common pattern, but it's not optimally efficient.  If this is a hot function, you could return an iterator/some sort of range that computes the next result when it is incremented.  Boost example of this kind of thing: https://www.boost.org/doc/libs/1_66_0/libs/iterator/doc/html/iterator/specialized/transform.html.

If you want to generalize this to other iterables, then don't take std::vector... instead take a templated T const& and same for ListLerp.

[[nodiscard]] T interp(const T x) noexcept;

Suppose I want to discard the result?  Maybe I only want to store every nth item?  interp is not a const member function (one might want the mutation to happen...) and T is not an "undiscardable" type.  I don't see why this needs to be here.

I don't think you've separated your interests very well between ListLerp::interp and the free function interp.

I think there are two good options:

make ListLerp::interp a const member function and get rid of ListLerp::b.  Then the free function interp just does a "pure" transformation of a single list.
iterate all three lists in a single function (my preference).

E.g.

auto interp(vec const& a, vec const& b, vec const& t) {
    for idx = each index in a, b {
        ... Possibly emit a value corresponding to t ...
    }
}

This is very basic pseudo code, but the key idea is you iterate everything in one go rather than doing some iteration in a free function and some iteration in a class that holds potentially dangerous references.

const std::vector<T>& xp;

This (and the lines like it) is moderately dangerous since you need to ensure the vector that is passed in outlives the class.

E.g. you cannot do this:

auto fn() {
     vector<double> v;
     ListLerp ll(v); // take reference to local variable v
     return ll; // v goes out of scope; ll has dangling reference to dead v
}

Often times the best option is to take the const& and be careful about how you use it, but in this case I think it's easy enough to compute the full result in a function, not expose a class that can hold a reference to a ctor argument, and make it impossible to end up with a dangling reference.

  It assumes everything is sorted before hand - x and f(x) are the same length.

How about asserting this?

// find b position
while (x > *b) b++;

If your input is sorted, this could be a binary search.  May or may not be better.

I think your calculation at the end would be simpler if you use indices rather than iterators.  Many of the lines are basically "find the iterator in A that has the same index as this iterator in B" ... easier to say "A[i]"


Rails controller method to show an optionally scaled image using MiniMagick I've got below implementation for my controller and show action which implements MiniMagick gem. I've just wondering is there any better way to write it down? If block in a separate, private method maybe?

  def show
    identification_document = IdentificationDocument.find(params[:id])
    authorize identification_document
    return unless identification_document

    if params.has_key?(:thumbnail)
      document = identification_document.id_document
      image = MiniMagick::Image.read(document.file.read)
      image.resize("50x60")
      scaled_image_bytes = image.to_blob
      send_data(scaled_image_bytes, filename: identification_document.file_name)
    else
      send_data(identification_document.id_document.file.read, filename: identification_document.file_name)
    end
  end

Rubocop Report

Conventions

Prefer key? over has_key? (PreferredHashMethods).

if params.has_key?(:thumbnail)

if params.key?(:thumbnail)

Prefer single quoted over double quoted string literals if you don't need interpolation or special symbols (StringLiterals).

image.resize("50x60")

image.resize('50x60')

Complexity

  If block in a separate, private method maybe?

The AbcSize complexity of your method is too high. [19.65/15] So your suggestion to put the following code in a private method, is justified.

 document = identification_document.id_document
 image = MiniMagick::Image.read(document.file.read)
 image.resize("50x60")
 scaled_image_bytes = image.to_blob

Readability

Keep line sizes below 80 characters:

send_data(identification_document.id_document.file.read, filename: identification_document.file_name)


Show User that Page is Loading using dots (...) I'm trying to show to the user that the page is reading/loading by creating an animation of dots.

Here is the HTML:

Authenticating

<button id="run">
    Run It
</button>
<button id="stop">
    Stop
</button>

And here is the script:

$(document).ready(function(){

    var interval;

    function countdown(){
        counter = 1;
        interval = setInterval(function(){
            if(counter > 0 && counter < 4){
                $("#dot").append('.');
            } else {
                counter = 0;
                $("#dot").text('Authenticating');
            }
            counter += 1;
        },1000);
    }

    $("#run").click(function(){
        countdown();
    })

    $("#stop").click(function(){
        $("#dot").text('Authenticating');
        clearInterval(interval);
    })

})

Any better way to implement it?

Check fiddle here.

$(document).ready(function(){

    var interval;

    function startIndicator(){
        stopIndicator();

        dotCount = 1;

        interval = setInterval(function(){

            $("#dots").text('.'.repeat(dotCount));

            dotCount++;
            if(dotCount > 3){
                dotCount = 0;
            }

        },1000);
    }

    function stopIndicator(){
        clearInterval(interval);
        dotCount = 0;
        $("#dots").text('');
    }

    $("#run").click(startIndicator);

    $("#stop").click(stopIndicator);

});

Authenticating

<button id="run">
    Run It
</button>
<button id="stop">
    Stop
</button>

This improves:

Original code allowed multiple timers set causing issues
String "Authenticating" not repeated and confined to HTML
Slightly cleaner conditions
Renamed countdown to indicator because it's not really a countdown
WARNING: .repeat maybe only works in quite modern browsers

Note: If you want to hide the "Authentication" text as well, just add CSS to hide the .progress div where appropriate.

One alternative approach that will probably give less and simpler code, at the cost of user's CPU, is to make the dots update all the time and simply toggle the visibility of #dots or .progress.


Implementing a copy on write String class using reference counting in C++ I have tried to implement a copy on write string class with value semantics and reference counting.

I wanted to support indexing, so I have overloaded the operator[] and to differentiate between the l-value and r-value usage it is returning a proxy object.

#include <iostream>
#include <string.h>
class proxy;

//Reference counting class.Also holds the string.
class RC
{
    public:
        RC(const char * str);
        ~RC();
    private:
        char* str;
        int count;

    friend class mystring;
    friend class proxy;

};

class mystring
{
    public:
        mystring(const char*  str);
        mystring& operator=(const mystring& str);
        mystring(const mystring& str);
        ~mystring();

        void print() const;
        proxy operator[](int n);

    private:
        RC *pRC;

    friend class proxy;
};
class proxy
{
    public:
        proxy(mystring* r,int n);
        proxy& operator=(const char& c);
        proxy& operator=(const proxy& c);
        operator char() const;

    private:
        int n;
        mystring* ptr;
};

RC::RC(const char * str1)
:str(new char[strlen(str1)+1]),count(1)
{
    strcpy(str,str1);
}

RC::~RC()
{
    if(--count == 0)
        delete [] str;
}

proxy mystring::operator[](int n)
{
    return proxy(this,n);
}

mystring::mystring(const char*  str)
:pRC(new RC(str))
{
}
mystring& mystring::operator=(const mystring& rhs)
{
    if(this != &rhs)
    {
        if(--pRC->count == 0)
            delete pRC;
        pRC = rhs.pRC;
        ++pRC->count;
    }
    return *this;
}
mystring::mystring(const mystring& rhs)
{
    pRC = rhs.pRC;
    ++pRC->count;
}

mystring::~mystring()
{
    if(--pRC->count == 0)
        delete pRC;
}
void mystring::print() const
{
    std::cout << pRC->str << ":" << pRC->count << '\n';
}

proxy::operator char() const
{
    return ptr->pRC->str[n];
}

proxy::proxy(mystring* r,int n)
:ptr(r),n(n)
{}

proxy& proxy::operator=(const char& c)
{

    if(c != ptr->pRC->str[n])
    {
        char cpy[strlen(ptr->pRC->str)+1];
        strcpy(cpy,ptr->pRC->str);
        ptr->pRC->~RC();
        cpy[n] = c;
        ptr->pRC = new RC(cpy);
    }

    return *this;
}

proxy& proxy::operator=(const proxy& rhs)
{
    if(this != &rhs)
    {
        *this = (char)rhs;

    }

    return *this;
}

Can you please help me improve the code?

Code simplification

mystring acts essentially as a smart pointer. It's already implemented in the standard library. You can use the std::shared_ptr class. This way, mystring can just have an std::shared_ptr<std::string> as a member. The default copy constructor, assignment operator and the desturctor will work properly.

Use of non-standard features

char cpy[strlen(ptr->pRC->str)+1]

variable sized arrays are not a part of the standard C++. Don't use them. If you need it, you should allocate it dynamically.

If you use the std::shared_ptr<std::string> as I said above, it'll be even simpler as std::string has a proper copy constructor.

Index

It's conventional to use size_t, not int as an index type (at least that's how an std::string works).


Find last zero in infinite stream of 0's followed by 1's Given an infinite stream with the property, such that after all 0's there are only all 1's, find the index of the last 0.

I'm looking for code review, best practices, optimizations etc. Verifying complexity to be O (log n) where n is the first 1 encountered in the search (not the first 1 in the stream).

/**
 * An infinite list takes in an the number of zeros'.
 * After those many zero's only 1's are followed.
 * This is a hypothetical class to represent a inifinite stream in real world.
 * like lets assume a linkedlist shared my multiple threads which keep appending 1's
 */
class InfiniteList extends ArrayList<Integer> {

    InfiniteList(int zeroCount) {
        super(zeroCount);
        add(zeroCount);
    }

    private void add (int zeroEnd) {
        for (int  i = 0; i < zeroEnd; i++) {
            super.add(0);
        }
    }

    @Override
    public Integer get(int i) {
        return super.size() <= i ? 1 : super.get(i);
    }

    @Override
    public int size() {
        throw new UnsupportedOperationException("The array size cannot be obtained.");
    }
}

public final class FindZeroEndInInfiniteStream {

    private FindZeroEndInInfiniteStream() {}

    /**
     * Takes in a infinite list, such that after stream of all 0's we encounter only all 1's.
     * Returns the last index of zero.
     * If no zero is found then -1 is returned.
     * This code would block until a zero is found in an infinite stream.
     * If the infinite has 0's and 1's mixed randomly then output is unpredicatable/
     *
     * @param infinite      the infinite stream of 0's followed by 1's
     * @return              the last index of zero.
     */
    public static int zeroLastIndex(InfiniteList infinite) {
        if (infinite == null) throw new NullPointerException("The inifinte array was null");
        return modifiedBinarySearch(infinite);
    }

    private static int modifiedBinarySearch(InfiniteList infinite) {
        if (infinite.get(0) == 1) return -1;
        if (infinite.get(1) == 1) return 0;

        int passive = 0;  // does nothing, simply stores previous lower bound.
        int active = 1; // does the searching, toggling back and forth

        while(!(infinite.get(active) == 0 && infinite.get(active + 1) == 1)) {
            if (infinite.get(active) == 0) {
                passive = active;
                active = active * 2;
            } else {
                active = (passive + active)/2; // active has gone beyond the 38th parallel :). Now go back to south korea.
            }
        }
        return active;
    }

    public static void main(String[] args) {
       InfiniteList iList = new InfiniteList(15);
       Assert.assertEquals(14,  zeroLastIndex(iList));

       iList = new InfiniteList(27);
       Assert.assertEquals(26,  zeroLastIndex(iList));
    }
}

You might have misunderstood the program requirements: an ArrayList is not an infinite Stream.

If you don't want a stream and do instead want to assume that multiple-threads are adding to it then you shouldn't use ArrayList because it's not thread-safe; apparently, a better alternative for that purpose would be Vector.


Optimizing Divisor Sieve I have two sieves that I wrote in python and would like help optimizing them if at all possible. The divisorSieve calculates the divisors of all numbers up to n. Each index of the list contains a list of its divisors. The numDivisorSieve just counts the number of divisors each index has but doesn't store the divisors themselves. These sieves work in a similar way as you would do a Sieve of Eratosthenes to calculate all prime numbers up to n.

Note: divs[i * j].append(i) changed from divs[i * j] += [i] with speed increase thanks to a member over at stackoverflow. I updated the table below with the new times for divisorSieve. It was suggested to use this board instead so I look forward to your input.

def divisorSieve(n):
    divs = [[1] for x in xrange(0, n + 1)]
    divs[0] = [0]
    for i in xrange(2, n + 1):
        for j in xrange(1, n / i + 1):
            divs[i * j].append(i) #changed from += [i] with speed increase.
    return divs

    def numDivisorSieve(n):
        divs = [1] * (n + 1)
        divs[0] = 0
        for i in xrange(2, n + 1):
            for j in xrange(1, n / i + 1):
                divs[i * j] += 1
        return divs

#Timer test for function
if __name__=='__main__':
    from timeit import Timer
    n = ...
    t1 = Timer(lambda: divisorSieve(n))
    print n, t1.timeit(number=1)

Results:

 -----n-----|--time(divSieve)--|--time(numDivSieve)--
    100,000 |  0.333831560615  |  0.187762331281
    200,000 |  0.71700566026   |  0.362314797537
    300,000 |  1.1643773714    |  0.55124339118
    400,000 |  1.63861821235   |  0.748340797412
    500,000 |  2.06917832929   |  0.959312993718
    600,000 |  2.52753840891   |  1.17777010636
    700,000 |  3.01465945139   |  1.38268800149
    800,000 |  3.49267338434   |  1.62560614543
    900,000 |  3.98145114138   |  1.83002270324
  1,000,000 |  4.4809342539    |  2.10247496423
  2,000,000 | 9.80035361075    |  4.59150618897
  3,000,000 | 15.465184114     |  7.24799900479
  4,000,000 | 21.2197508864    |  10.1484527586
  5,000,000 | 27.1910144928    |  12.7670585308
  6,000,000 | 33.6597508864    |  15.4226118057
  7,000,000 | 39.7509513591    |  18.2902677738
  8,000,000 | 46.5065447534    |  21.1247001928
  9,000,000 | 53.2574136966    |  23.8988925173
 10,000,000 | 60.0628718044    |  26.8588813211
 11,000,000 | 66.0121182435    |  29.4509693973
 12,000,000 |   MemoryError    |  32.3228102258

 20,000,000 |   MemoryError    |  56.2527237669
 30,000,000 |   MemoryError    |  86.8917332214
 40,000,000 |   MemoryError    |  118.457179822
 50,000,000 |   MemoryError    |  149.526622815
 60,000,000 |   MemoryError    |  181.627320396
 70,000,000 |   MemoryError    |  214.17467749
 80,000,000 |   MemoryError    |  246.23677614
 90,000,000 |   MemoryError    |  279.53308422
100,000,000 |   MemoryError    |  314.813166014

Results are pretty good and I'm happy I was able to get it this far, but I'm looking to get it even faster. If at all possible, I'd like to get 100,000,000 at a reasonable speed with the divisorSieve. Although this also brings into the issue that anything over 12,000,000+ throws a MemoryError at divs = [[1] for x in xrange(0, n + 1)]) in divisorSieve. numDivisorSieve does allow the full 100,000,000 to run. If you could also help get past the memory error, that would be great.

I've tried replacing numDivisorSieve's divs = [1] * (n + 1) with both divs = array.array('i', [1] * (n + 1)) and divs = numpy.ones((n + 1), dtype='int') but both resulted in a loss of speed (slight difference for array, much larger difference for numpy). I expect that since numDivisorSieve had a loss in efficiency, then so would divisorSieve. Of course there's always the chance I'm using one or both of these incorrectly since I'm not used to either of them.

I would appreciate any help you can give me. I hope I have provided enough details. Thank you.

You can use xrange's third param to do the stepping for you to shave off a little bit of time (not huge).

Changing:

for j in xrange(1, n / i + 1):
    divs[i * j].append(i)

To:

for j in xrange(i, n + 1, i):
    divs[j].append(i)

For n=100000, I go from 0.522774934769 to 0.47496509552.  This difference is bigger when made to numDivisorSieve, but as I understand, you're looking for speedups in divisorSieve


Calculating Maclaurin series for sin(x) I'm very new to Haskell as was hoping to get some feedback on my code AND I have some specific questions. I've posted code below or you can see it here.

I'd welcome ideas on how better to calculate the Maclaurin series. Ideas on how better to do the math itself are welcome but I had in mind what Haskell ideas am I missing out on.

My specific questions are:

Are (almost) all the calculations for Factorial going to be done every time for each value of my Maclaurin series? Or is there some sort of caching going on? One can appreciate that calculating 100! from scratch seems crazy if you've just done 99!
Notice the signature at end: maclaurin :: ( Floating b) => Int-> b -> b I tried using maclaurin :: ( Integral a, Floating b) => a-> b -> b , thinking that would be best. Didn't work. I stumbled on this scheme by removing signature and typing :t maclaurin in WinGHci. I'm surprised it worked! I thought we had to declare each parameter?

--import Data.List(genericTake)

 -- MacClaurin series for Sin(x) is f(0) + f'(0)(x)/1! + f''(0)(x)^2 / 2!  +
  ... + f^n (0) x^n / n!
  -- or in the case of Sin(x):  0 + 1x + 0 + -1x^3 / 3! + 0 + 1 x^5 / 5! + 0
  + -1x^7/7! ...
   -- See Wikipedia https://en.wikipedia.org/wiki/Taylor_series

-- return list of alterating 0 and 1
    -- not needed for maclaurin or macResult
ymod2 :: Integral a =>  [a]
ymod2  = map (\y->(y `mod` 2)) [0..]

factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

powersMac :: (Integral a) => a -> a
powersMac n
    | n == 0 = 0
    | n == 1 = 1
    | ( (n `mod` 2) == 0 ) = 0
    | otherwise =  ( (-1) * powersMac (n-2) )

-- return list of 0, 1, 0, -1, 0, 1, 0, -1 ...
powersMacList :: (Integral a) => [a]
powersMacList  = map (\y->(powersMac y)) [0..]

-- return list of x^0, x^1, x^2, ... x^n
powersOfx :: (Enum b, Floating b) =>  b -> [b]
powersOfx  x = map (\y->(x^^y)) [0..]

-- return list of 0, 1, 0, -1, 0, ... to n
firstLst :: Integral a =>  [a]
firstLst   = zipWith (*) (ymod2 ) (powersMacList)

-- return list of 0x, 1x, 0x^2, -1x^3, ... to n
secondLst :: (Enum b, Floating b) =>  b -> [b]
secondLst  x = zipWith (*) (map fromIntegral(powersMacList )) (powersOfx  x)

-- return list of 0, 1x, 0 , -1x^3 / 3! , 0 , 1 x^5 / 5! , 0 ... to n
thirdLst :: ( Enum b, Floating b) =>  b -> [b]
thirdLst  x = zipWith (/) (secondLst  x) (map fromIntegral ( (map(\y->(factorial y) ) [0..])) )

-- sum the list to get result
macResult :: (  Enum b, Floating b) =>  Int -> b -> b
macResult  n x = sum (take n (thirdLst  x))

maclaurin :: (  Floating b) => Int-> b -> b
maclaurin  n x = sum ( take n (zipWith (*) (map(\y->(x^^y))[0..])(zipWith (/) (map fromIntegral (powersMacList )) (map fromIntegral (map(\y->(factorial y) )[0..]) )) ))

There's a few builtins you may have missed:

ymod2 = cycle [0,1]

If I read powersMac correctly, it basically goes along [0, 1, 0, -1] in cycles as well. So you can reformulate it as:

powersMac n = [0, 1, 0, -1] !! (n `mod` 4)

Considering that you only directly use it as powersMacList, we can again reformulate with cycle:

powersMacList = cycle [0, 1, 0, -1]

BTW: While we're on these two methods:

map (\y -> f y)

is equivalent to:

map f

Noticing that we can rewrite powersOfx as:

powersOfx = map (x^^) [0..]

firstLst does nothing. When there's a 0 in the one list, there's always a 0 in the other list as well.

The formatting in secondLst is somewhat confusing and difficult to read. Consider:

secondLst x = zipWith (*) (map fromIntegral powersMacList) (powersOfx x)

When you use factorial and run a map factorial [0..] you actually want the list of factorials. I'm stealing this excellent SO answer:

factorials = 1 : zipWith (*) factorials [1..]

which turns thirdList into:

thirdList x = zipWith (/) (secondLst x) factorials

applying everything we learned to maclaurin after discarding the fromIntegral calls (that are most likely a result of overspecific type signatures):

maclaurin n x = sum (take n (zipWith (*) (map (x^^) [0..]) (zipWith (/) powersMacList factorial)

Now putting it all together again, after giving out a bit more generous names than firstLst, secondLst and thirdLst:

factorials = 1 : zipWith (*) factorials [1..]

sinZeroDerivations = cycle [0,1,0,-1]
macRawElements x = zipWith (*) sinZeroDerivations (map (x^^) [0..])
macDiscounted x = zipWith (*) (macRawElements x) factorials

macResult n x = sum (take n (macDiscounted x))

Now if you wanted to be less maintainable you could inline the definitions again, but that's not really necessary, is it?

There's something about macDiscounted that annoys me a bit, namely that it only passes x through to macRawElements. We can fix that by swapping those two around like:

sinMacFactors = zipWith (/) sinZeroDerivations factorials

That allows us to specify a bit cleaner what we want:

macResult n x = sum (zipWith (*) (take n (map (x^^) [0..])) sinMacFactors)

notice the second argument to zipWith. That wants to be written as:

macResult n x = sum (zipWith (*) (map (x^^) [0..n]) sinMacFactors)


User form that searches a spreadsheet I have this userform that looks up into a sheet. The problem is that when there are a lot of rows to look up it takes too long to execute (for example 100 thousand rows). Is it possible to reduce the time?

Here is the userform's textbox code where I put what I am looking for, and the data is shown on a listbox ("LSTART")

Private Sub TXTBUSCAART_Change()
    Dim rowCount As Long, itemCount As Long, counter As Long, n As Long
    Dim dataSheet As Worksheet
    Dim dataIn, dataOut()

    LSTART.Clear
    LSTART.ColumnCount = 9

    Set dataSheet = Sheets("CONCAT")
    With dataSheet

        rowCount = .Cells(.Rows.Count, "A").End(xlUp).Row
        itemCount = Application.WorksheetFunction.CountIf(.Range("A2:A" & rowCount), "*" & TXTBUSCAART.Text & "*")

        If itemCount > 0 Then
            ReDim dataOut(1 To itemCount, 1 To 9)
            dataIn = .Range("A2:I" & rowCount).Value
            counter = 1

            For n = 1 To UBound(dataIn)
                M = InStr(1, dataIn(n, 1), UCase(TXTBUSCAART.Text))
                If M > 0 Then
                    dataOut(counter, 1) = dataIn(n, 1)
                    dataOut(counter, 2) = dataIn(n, 3)
                    dataOut(counter, 3) = dataIn(n, 2)
                    dataOut(counter, 4) = dataIn(n, 4)
                    dataOut(counter, 5) = dataIn(n, 6)
                    dataOut(counter, 6) = dataIn(n, 5)
                    dataOut(counter, 7) = dataIn(n, 8)
                    dataOut(counter, 8) = dataIn(n, 9)
                    dataOut(counter, 9) = dataIn(n, 7)
                    counter = counter + 1
                End If
            Next

        LSTART.List = dataOut

        End If
    End With

End Sub

Worksheet functions like CountIf are pretty well optimized, so that's a good way to find out if TXTBUSCAART.Text is in column A of your dataSheet. but so is Find.

By using Find, you could eliminate the initial step (CountIf) to determine if your search string is in the destination and you eliminate the InStr call to recheck if it's in each individual row of your data set. Unfortunately, you really need to know how many times your .Text appears to make the most efficient use of ReDim dataOut, so we'll leave that in there.

This is what I came up with for your loop using Find:

Private Sub LStart_Change()

  Dim rowCount As Long, itemCount As Long, counter As Long
  Dim dataSheet As Worksheet
  Dim dataOut() As Variant

  LStart.Clear
  LStart.ColumnCount = 9

  Set dataSheet = Sheets("sheet1")
  With dataSheet
    rowCount = .Cells(.Rows.Count, "A").End(xlUp).Row
    Dim searchString As String
    searchString = "abcde"
    itemCount = Application.WorksheetFunction.CountIf(.Range("A2:A" & rowCount), "*" & searchString & "*")
    If itemCount > 0 Then
      Dim searchRange As Range
      Set searchRange = .Range(.Cells(2, 1), .Cells(rowCount, 1))
      ReDim dataOut(1 To itemCount, 1 To 9)
      Dim foundCell As Range
      Set foundCell = searchRange.Find(What:=searchString, LookIn:=xlValues, lookat:=xlWhole, MatchCase:=False)
      counter = 1
      Dim firstCell As Range
      Do Until foundCell Is Nothing
        If firstCell Is Nothing Then
          Set firstCell = foundCell
        End If
        With foundCell
          dataOut(counter, 1) = .Cells(1, 1)
          dataOut(counter, 2) = .Cells(1, 3)
          dataOut(counter, 3) = .Cells(1, 2)
          dataOut(counter, 4) = .Cells(1, 4)
          dataOut(counter, 5) = .Cells(1, 6)
          dataOut(counter, 6) = .Cells(1, 5)
          dataOut(counter, 7) = .Cells(1, 8)
          dataOut(counter, 8) = .Cells(1, 9)
          dataOut(counter, 9) = .Cells(1, 7)
        End With
        Set foundCell = searchRange.FindNext(foundCell)
        If foundCell.Address = firstCell.Address Then
          Set foundCell = Nothing
        Else
          counter = counter + 1
        End If
      Loop
      LStart.List = dataOut
    End If
  End With

End Sub

It compiles cleanly, but you may have to fiddle with the .Find() parameters a little bit since I don't have your exact data set to work from.

Using .Find() takes you directly to each row that has your TXTBUSCAART.Text in it so you may save 100s of If InStr() comparisons in a row looking at rows that don't contain your required text. I've set MatchCase:=False to eliminate the UCase() call on each comparison since it didn't seem to matter (you don't UCase()the text in your initial CountIf(), so I didn't think you really cared - adjust as necessary).

I set the variable searchString to TXTBUSCAART.Text one time because there's no need to reference the form every time through the loop. This may well save you milliseconds in total execution time! :)

When using .Find() it will continue to loop through the search range forever, so you have to store off the first cell it finds then compare each newly found cell to that one to stop the loop when you've returned to the beginning.

One note on .Find(): it will use any parameters set in the Find dialog box that you haven't explicitly overwritten, so make sure you're including all the parameters you need. Also, any parameters you set in code will appear the next time you open the Find dialog box, so if you have a favorite group of settings, you may want to store them off before fiddling with them in your code, then reset them when you're done.


Improvement in file management system based on the file names Context:

I have a program which stores data to the disk. The data is then reprocessed during some of the iterations. Thus, it needs to store, search and load set of data.

Let's consider the following class Signal which defines a multiphasic signal:

class Signal:
    def __init__(self, amp, fq, phases):
        self.amp = amp
        self.fq = fq
        self.phases = phases

# List of signal objects:
signals = [Signal(0.2, 50, [20, 30]), Signal(10, 200, [20, 30]), Signal(20, 20, [20, 90])]

Based on the list of signals, a file_name is computed:

def file_name(signals):
    amplitudes = tuple([S.amp for S in signals])
    frequencies = tuple([S.fq for S in signals])
    phases = tuple([S.phases for S in signals])

    return "A{}_F{}_P{}.pkl".format(amplitudes, frequencies, phases)

For the example above, it would return:

 "A(0.2, 10, 20)_F(50, 200, 20)_P([20, 30], [20, 30], [20, 90]).pkl"

As you can see, I'm pickling the files (with _pickle). Let's now believe that hundreds of files have been stored to the folder: folder. To check if a specific combination of signals has been computed I'm using:

import itertools
def is_computed(files, signals):
    """
    Check if the signals are already computed
    """
    return any(file_name(elt) in files for elt in itertools.permutations(signals))

I'm using itertools since the permutations are relevant, i.e.:

signals = [Signal(0.2, 50, [20, 30]), Signal(10, 200, [20, 30]), Signal(20, 20, [20, 90])]
# IS THE SAME AS:
signals = [Signal(10, 200, [20, 30]), Signal(20, 20, [20, 90]), Signal(0.2, 50, [20, 30])]

Issue:

To get the list of files past to is_computed(), I'm using: files = os.listdir(folder) which becomes fairly inefficient as the number of files grows up.

# Folder of 26K files with the size from 1 kB to hundreds of MBs
In:  %timeit os.listdir(folder)
Out: 3.75 s ± 842 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Question:

How could I make a similar system but efficient?

Thanks for the help!

It would be better to design the system so that each collection of signals has a canonical filename, regardless of the order of the signals in the collection. This is most easily done by sorting the signals in the collection:

def canonical_filename(signals):
    "Return canonical filename for a collection of signals."
    return file_name(sorted(signals, key=lambda s: (s.amp, s.fq, s.phases)))

Since there is now only one filename for each collection of signals, there is no need to list the directory or generate the permutations:

def is_computed(signals):
    "Return True if the file for signals exists, False otherwise."
    return os.path.isfile(canonical_filename(signals))

I recommend designing the filename so that it does not contain shell meta-characters like spaces, parentheses, and brackets. This is a convenience that means we don't need to quote the filenames when manipulating them via the shell. For example:

def file_name(signals):
    "Return filename for a list of signals."
    amplitudes = ','.join(str(s.amp) for s in signals)
    frequencies = ','.join(str(s.fq) for s in signals)
    phases = ':'.join(','.join(map(str, s.phases)) for s in signals)
    return f'A{amplitudes}_F{frequencies}_P{phases}.pkl'


Improving efficiency for two sum I am trying to solve this problem:

  Given an array of integers, find two numbers such that they add up to a specific target number.

and this is my strategy:

  For each i in array num, do a binary search in numfor target - i in num.

class Solution:
    # @return a tuple, (index1, index2)

    def binary_search(self, array, target):
        def _binary_search(a, l, h, t):
            if l == h:
                return None
            elif a[(h + l) / 2] == t:
                return (h + l) / 2
            elif a[(h + l) / 2] > t:
                return _binary_search(a, l, (h + l) / 2, t)
            elif a[(h + l) / 2] < t:
                return _binary_search(a, (h + l) / 2 + 1, h, t)
            else:
                return None

        return _binary_search(array, 0, len(array) - 1, target)

    def twoSum(self, num, target):
        s_num = sorted(num)
        z_num = [(i, num.index(i)) for i in s_num]
        for tup in z_num:
            n = tup[0]
            i = tup[1]
            t = self.binary_search(s_num, target - n)
            if t != None:
                index_2 = num.index(target - n)
                if i == index_2:
                    index_2 = i + 1 + num[i:].index(target - n)
                return (i + 1, index_2 + 1)

Time complexity: \$O(n * log(n))\$

This algorithm is not accepted since the it exceeds the time limitation. How can I improve it?

You are correct that the first step is to sort the array. The second step - an actual search for solution - is also happen to be of n*log(n) complexity. What is important, they are very different n*log(n): sorting is implemented in native code, so it is virtually instantaneous comparing to the Python loops. The key to solution is to realize that the second step can be done in linear time:

Given a sorted array data you may build another sorted array target_minus_data in linear time. It is also sorted, descending. Reverse it (linear time). Now there are two sorted arrays sharing the same value. It can be found also in linear time by a merge-like algorithm.

Of course, you don't have to physically reverse target_minus_data - just iterate it backwards. If you look closely, you do not even have to build it; everything can be done in the fly. Merge data with itself, from both ends, a backward iterator returning target - data[bkwd].


Model class representing a financial calculator Here is my Model class's new header file:

@interface MMCalculator : NSObject

@property (readonly) CGFloat calculatedPay;
@property (readonly) CGFloat calculatedSavingsForStuff;
@property (readonly) CGFloat calculatedSavingsForProfitFormula;
@property (readonly) CGFloat calculatedSavingsForTaxes;

- (void)calculateValuesWithMonthlyRevenue:(CGFloat)monthlyRevenue;

@end

Here is my Model class's new implementation file:

#import "MMCalculator.h"

#pragma mark - Const Variables
static CGFloat const kPercentageToPayYourself = 0.50;
static CGFloat const kPercentageToSaveForStuff = 0.20;
static CGFloat const kPercentageToSaveForProfitFormula = 0.20;
static CGFloat const kPercentageToSaveForTaxes = 0.10;

@interface MMCalculator ()

@property (readwrite) CGFloat calculatedPay;
@property (readwrite) CGFloat calculatedSavingsForStuff;
@property (readwrite) CGFloat calculatedSavingsForProfitFormula;
@property (readwrite) CGFloat calculatedSavingsForTaxes;

@end

@implementation MMCalculator

#pragma mark - Calculator Methods
- (void)calculateValuesWithMonthlyRevenue:(float)monthlyRevenue
{
    //Call all 4 calculation methods and set calculated properties
    self.calculatedPay = [MMCalculator calculateYourPay:monthlyRevenue];
    self.calculatedSavingsForStuff = [MMCalculator calculateSavingsForStuff:monthlyRevenue];
    self.calculatedSavingsForProfitFormula = [MMCalculator calculateSavingsForProfitFormula:monthlyRevenue];
    self.calculatedSavingsForTaxes = [MMCalculator calculateSavingsForTaxes:monthlyRevenue];

}

+ (CGFloat)calculateYourPay:(CGFloat)monthlyRevenue
{
    return kPercentageToPayYourself * monthlyRevenue;
}

+ (CGFloat)calculateSavingsForStuff:(CGFloat)monthlyRevenue
{
    return kPercentageToSaveForStuff * monthlyRevenue;;
}

+ (CGFloat)calculateSavingsForProfitFormula:(CGFloat)monthlyRevenue
{
    return kPercentageToSaveForProfitFormula * monthlyRevenue;
}

+ (CGFloat)calculateSavingsForTaxes:(CGFloat)monthlyRevenue
{
    return kPercentageToSaveForTaxes * monthlyRevenue;
}

@end

Key things I am looking for advice on:

Are my constants defined in the correct location in my Model class's implementation file?
Even though the compiler does not force me to, would it be better to declare my private methods in the class extension? I want to make sure I'm following best practices.
Now that the Model's instance methods have been changed to class methods, should I change the public calculateValuesWithMonthlyRevenue: method to a class method as well?
Any other general comments are welcome.

Are my constants defined in the correct location in my Model class's implementation file?

It is impossible to tell.  Where a variable needs to be declared is entirely dependent upon its intended scope.

If a variable is used only within a single block (within an if, else, or loop, or anything else of this nature), it should be declared within that block.
If a variable is used only in a single function, it should be declared in that function.
If a variable is used in multiple functions in a file, it should be declared in the .m file so it can be seen throughout the file, but not within other files in the project.
If a variable is used in multiple files, it should be declared in a .h file so that it may be imported across the multiple files.

  Even though the compiler does not force me to, would it be better to declare my private methods in the class extension? I want to make sure I'm following best practices.

There's no particular need to declaring methods in class extensions in Objective-C.  I don't know of any real benefit to doing so.

  Now that the Model's instance methods have been changed to class methods, should I change the public calculateValuesWithMonthlyRevenue: method to a class method as well?

This one can't be changed, at least not quite as easily.  You can't refer to a class's instance variables within a class method.

Perhaps what you should do is instead change it to more of a factory method that might look a bit like this:

+ (instancetype)calculatedValuesForMonthlyRevenue:(CGFloat)monthlyRevenue {
    return [[self alloc] initWithValuesForMonthlyRevenue:monthlyRevenue];
}

- (instancetype)initWithValuesForMonthlyRevenue:(CGFloat)monthlyRevenue {
    self = [super init];

    if (self) {
        _calculatedPay = [MMCalculator calculateYourPay:monthlyRevenue];
        _calculatedSavingsForStuff = [MMCalculator calculateSavingsForStuff:monthlyRevenue];
        _calculatedSavingsForProfitFormula = [MMCalculator calculateSavingsForProfitFormula:monthlyRevenue];
        _calculatedSavingsForTaxes = [MMCalculator calculateSavingsForTaxes:monthlyRevenue];
    }

    return self;
}

  Any other general comments are welcome.

The class name, MMCalculator needs some work.  This does a more specific job then a regular calculator.  This is more like a personal finance calculator if anything.

  Any other general comments are welcome.

You really shouldn't represent money with floating point numbers.

Instead, you should probably create a class for holding money.

Money.h

@interface Money

@property (readonly) int dollars;
@property (readonly) int cents;

+ (instancetype)moneyWithDollars:(int)dollars cents:(int)cents;
- (instancetype)initWithDollars:(int)dollars cents:(int)cents;

@end

Money.m

@implementation Money {
    long long _totalCents;
}

- (int)dollars {
    return _totalCents/100;
}

- (int)cents {
    return _totalCents%100;
}

+ (instancetype)moneyWithDollars:(int)dollars cents:(int)cents {
    return [[self alloc] initWithDollars:dollars cents:cents];
}

- (instancetype)initWithDollars:(int)dollars cents:(int)cents {
    self = [super init];

    if (self) {
        _totalCents = cents + (100 * dollars);
    }

    return self;
}

@end

The class could be rounded out with various math methods as well.


Word ladders program in Python Background information: Given two different strings of equal length, the spacing between them is the number of other strings you would need to connect them on a word ladder. Alternately, this is 1 less than the number of letters that differ between the two strings.

The challenge: Given an input list of unique words and a maximum total spacing, output a list of distinct words taken from the input list. The output list's total spacing must not exceed the given maximum. The output list should be as long as possible.

My output list is 433 words long. May someone look over code proofreading/ efficiency? Much thanks.

Also, the text file used in the program can be found here: https://gist.githubusercontent.com/cosmologicon/0a4448e8fdb79ee620a68ed131eac58e/raw/a8831d08019f73e7d5a52042e2c4afe6fea70011/363-hard-words.txt

import operator

MAX = 100  # Max word ladder score I'm allowed in this program

with open("363-hard-words.txt") as f:
    data = f.read().splitlines()
    f.close()

def merge_two_dicts(x, y):
    z = x.copy()
    z.update(y)
    return z

# Returns numerical spacing between a and b on the word ladder
def spacing(a, b):
    score = 0
    for x, y in zip(a, b):
        if x != y:
            score += 1
    return score - 1

# Returns a dictionary of txt file words as key, with number of words with sp spacing as value
def space_dict(sp):
    totals = []
    for word in data:
        total = 0
        for word1 in data:
            if word == word1:
                continue
            if spacing(word, word1) == sp:
                total += 1
        totals.append(total)
    return dict(zip(data, totals))

# Given a word, returns a dictionary with every other word as the key,
# and the spacing between the word and the other word as the value
def words_dict(word):
    totals = []
    for w in data:
        if w == word:
            continue
        totals.append(spacing(word, w))
    return dict(zip(data, totals))

# Sorts a dictionary by its keys in ascending order and returns a list
def sort_dict(space):
    return sorted(space.items(), key=operator.itemgetter(1))

# Returns a list of words with number spacing to the word
def get_connections(word, number):
    output = []
    for w in data:
        if (spacing(word, w) == number) and (word != w):
            output.append(w)
    return output

# Attempts to return max list of words with a total word ladder score of 0
def method1():
    output = []
    sorted_dict = sort_dict(space_dict(0))
    output.append(sorted_dict[-1][0])
    data.remove(sorted_dict[-1][0])
    connections = get_connections(sorted_dict[-1][0], 0)

    while len(get_connections(connections[-1], 0)) != 0:
        connections = get_connections(connections[-1], 0)
        output.append(connections[-1])
        print("connections:", connections, "Output size:", str(len(output)))
        data.remove(connections[-1])
    return len(output)

# Attempts to return max length of a word ladder given first word, inspired by
# tajjet's solution
def method2_iter(wd):
    score, length = 0, 0
    output = [wd]
    sorted_dict = sort_dict(words_dict(wd))
    data.remove(wd)
    while score <= 100:
        length += 1
        word = sorted_dict[0][0]
        score += sorted_dict[0][1]
        if score > 100:
            break
        output.append(word)
        data.remove(word)
        sorted_dict = sort_dict(words_dict(word))
    print(output)
    return length

def main():
    # print(str(method1()))
    print(str(method2_iter("kats")))

main()

def spacing(a, b):
    score = 0
    for x, y in zip(a, b):
        if x != y:
            score += 1
    return score - 1

can be simplified to:

def spacing(a, b):
    """Returns numerical spacing between a and b on the word ladder"""
    return sum(1 for x, y in zip(a, b) if x != y) - 1

I suggest writing the comments as a string inside the function (a docstring) like above, then you can later write

help(spacing)

and get the documentation.  It also helps your IDE to find the documentation.


Iterative implementation of K of N variations Objective:

  Print all combinations with repetition of k elements out of a set of n elements.

using System;

namespace Chapter10Exercise2
{
    class KofNCombinationsIterative
    {
     static int[] combination;
     //-------------------------------------------------------------------------

        static void Main(string[] args)
        {
            Console.WriteLine("Type n:");
            int n = int.Parse(Console.ReadLine());

            Console.WriteLine("Type k:");
            int k = int.Parse(Console.ReadLine());

            FindCombinations(n, k);
        }
        //----------------------------------------------------------------------

        /*
            Method: FindCombinations(int n, int k)

            It prints the combinations of k elements
            in a set of n elements.

            It increments the values of an array of size k
            from 1 to n, starting from the last element.
        */
        private static void FindCombinations(int n, int k)
        {
            combination = new int[k];
            int initialValue = 1;
            InitializeArray(combination, initialValue);
            int valueAfterOverflow = 1;

            while (true)
            {
                // print current combination
                PrintCombination();

                // increase value at current index
                int index = k - 1;
                ++combination[index];

                // go to the next index
                while (combination[index] > n)
                {
                    ++valueAfterOverflow;
                    combination[index] = valueAfterOverflow;
                    --index;

                    // if current index is < 0 exit
                    if (index < 0)
                    {
                        return;
                    }
                    ++combination[index];
                }
            }
        }
        //----------------------------------------------------------------------

        /*
            Method: PrintCombination()

        */
        private static void PrintCombination()
        {
            Console.Write("(");
            for (int i = 0; i < combination.Length; ++i)
            {
                Console.Write(combination[i]);

                if (i < combination.Length - 1)
                {
                    Console.Write(", ");
                }
            }
            Console.WriteLine(")");
        }
        //----------------------------------------------------------------------

        /*
            Method: InitializeArray(int[] arr, int initialValue)

        */
        static void InitializeArray(int[] arr, int initialValue)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = initialValue;
            }
        }
    }
}

Input:

  Type n: 3
   Type к: 2

Output:

  (1 1), (1 2), (1 3), (2 2), (2 3), (3 3)

I've been trying to get rid of the variable valueAfterOverlow to no avail, is there a way to use some of the already defined variables: index, n and k to update the value after overflow?

Is the complexity: $$O(n^k)$$ ,i.e. n-incrementations of k variables (plus some additional work)?

Is there more effective iterative algorithm?

Your code is wrong: if I test it with n=3, k=3 I get

  (1 1 1), (1 1 2), (1 1 3), (1 2 2), (1 2 3), (1 3 3), (2 5 4), (3 7 6)

However, you're on the right lines. Assuming that you want (or at least don't mind) to return each combination in ascending order, the way that I find intuitive to think about it is as a set of k nested loops:

for (combination[0] = 1; combination[0] <= n; combination[0]++)
    for (combination[1] = combination[0]; combination[1] <= n; combination[1]++)
        ...
            for (combination[k] = combination[k-1]; combination[k] <= n; combination[k]++)
                PrintCombination(combination);

To turn that into an iterative approach, you count but when you overflow then instead of resetting to 0 you reset to the final value which doesn't overflow. I agree with Kore's now deleted answer that you should use Enumerable.Repeat to initialise, and I also think you should make the generation method generate rather than print, so it comes down to

    private static IEnumerable<int[]> FindCombinations(int n, int k)
    {
        var combination = Enumerable.Repeat(1, k).ToArray();
        while (true)
        {
            // generate current combination
            yield return (int[])combination.Clone();

            // find index which isn't going to overflow
            int index = k - 1;
            while (combination[index] == n)
            {
                if (--index < 0) yield break;
            }

            // increment and fill right
            for (int finalDigit = combination[index] + 1; index < n; index++)
            {
                combination[index] = finalDigit;
            }
        }
    }

The performance is O(n) per combination returned, and that is optimal (just cloning the answer to return it is already O(n), and even if we don't clone and guarantee elsewhere that we won't modify the array, we'll still surely want to use it).


Profile picture upload method in Laravel 5.2 I am a Laravel newbie so please forgive me for my code... I have a method, in a Laravel controller, that updates the current logged user profile (postProfileGeneral()).
Logged user can upload a profile picture, and I manipulate the uploaded file (i.e. remove spaces, create unique name, etc.); since I'd like to reuse the upload routine, I put it on a separate method (_upload())
The code is this:

// get a unique file name
protected function _getUniqueFilename($path, $filename, $extension)
{
    $i = 2;
    $output = $filename . '.' . $extension;
    while(File::exists($path . '/' . $output)){
        $output = $filename . '_' . $i . '.' . $extension;
        $i++;
    }
    return $output;
}

// upload method, to reuse the routine
protected function _upload(Request $request, $field, $path = '')
{
    $path = ($path != '') ? $path : public_path();
    if ($request->hasFile($field)){
        $file = $request->file($field);
        if ($file->isValid()){
            $basename = $file->getClientOriginalName(); // get the original filename + extension
            $extension = $file->getClientOriginalExtension(); // get the original extension without the dot
            $filename = basename($basename, '.' . $extension); // get the original filename only
            $slug = str_slug($filename, '-'); // slug the original filename
            $name = $this->_getUniqueFilename($path, $slug, $extension);
            $file->move($path, $name);
            $output = $path . $name;
        }
    } else {
        $output = $request->input('cur_picture');
    }
    return $output;
}

// update profile
public function postProfileGeneral(Request $request)
{
    $picture = $this->_upload($request, 'picture', config('custom.users_path'));
    dd($picture);
    // rest of method here, not relevant
}

It works fine, but I feel there is a better way of doing this
My questions are:

since the getUniqueFilename() and _upload() method can be reused in other controllers too (i.e. for uploading products pictures, or whatever) where should I put them to be generally available?
in the getUniqueFilename() method I must pass Request object as a parameter: is there a better way to do this? At last, I yet have my Request object available in the postProfileGeneral() method...

I think your program is good. I repeat, IMO, it's good.
As you said in questions, the answers are

 Move your image manipulation related methods to a TRAIT. that'll help you while using the same code in different controllers. Because, if you want it to be done like this way, you must have to declare objects, if you want to use the same code from different controllers/classes. On the other hand, if you use TRAIT, you just have to use them.

 As you're passing the Request to your method, you may pass the array instead. Otherwise, you may use check the file existence, on the previous method then pass the values to next method. You may wish to use varargs as a method parameter.


Iterating over Dungeon Map I'm working on an RPG so of course I have to have some dungeons.  I've got the dungeon generation working, with the output being a DungeonTileType[][].

Now I wanted to create the code for the player to be able to enter the dungeon.  To do so, I created a Dungeon class that will hold all of the information necessary for the game to work.

Here it is:

public class Dungeon {

    private final Player player;
    private final DungeonTileType[][] dungeonTiles;

    private MapPoint startPoint;
    private MapPoint endPoint;

    public Dungeon(Player player, DungeonTileType[][] dungeonTiles) {
        this.player = player;
        this.dungeonTiles = dungeonTiles;

        for (int x = 0; x < dungeonTiles.length; x++) {
            DungeonTileType[] row = dungeonTiles[x];
            for (int y = 0; y < row.length; y++) {
                DungeonTileType type = row[y];
                if (type == DungeonTileType.START) {
                    this.startPoint = new MapPoint(x, y);
                } else if (type == DungeonTileType.END) {
                    this.endPoint = new MapPoint(x, y);
                }
            }
        }

        this.player.setDungeonStartPosition(this.startPoint);
    }

    public DungeonTileType[][] getTiles() {
        return this.dungeonTiles;
    }

    public Player getPlayer() {
        return this.player;
    }

    public MapPoint getStartPoint() {
        return this.startPoint;
    }

    public MapPoint getEndPoint() {
        return this.endPoint;
    }
}

I'm using a maze generating algorithm as the first step for the dungeon creation, so I can make use of the start point of the maze to position the player correctly once he enters the dungeon. I could also use the end point to create stairs to another level at some point.

What I really don't like is that I cannot use for : in in this situation, because I need to have the X and Y coordinates of a given tile.  One solution would be to have a DungeonTile class that keeps track of both the type and the position, but I like the simplicity of the matrix, especially when I go to serialize things. I also thought about a list of lists, because then I could use indexOf(), but again I lose the simplicity of the matrix in that situation.

I would love to get some ideas for alternative approaches.

I'm working on an RPG so of course I have to have some dungeons. I've got the dungeon generation working, with the output being a DungeonTileType[][].

Well there's your problem. To simplify eliminate the search, you should return something like this:

class Dungeon {
    DungeonTileType[][] tiles;
    MapPoint start;
    MapPoint end;
}

Think about it, you currently have some code that generates a map that you then search through the entire map to find out where you placed that one exit and that one start tile.

When you place the start and end tiles, you should save the position that you placed them at.

As for general two dimensional looping, I wrote a Iterator for looping through 2D arrays a while ago that you can use if you'd like.


Word splitting / text parsing with consideration for quotes Is the MoveNext operation inefficient here?  I really just want to increment an index.  Originally, I had a mutable variable locally in ExtractTokens to accommodate this.  I would have to believe that a mutable variable there would have been pretty efficient, but I'm trying hard not to have them.  I can't help but feel that creating a new Record to increment an integer is bad somehow.  I guess I'm wondering what a real-world F# developer would have chosen to do here.

This starts in ExtractTokens.  It basically iterates each character in a string.  On spaces it yields the previous word, unless in a quote either single or double.

type Quote =
   | Single
   | Double
   | None

type State = {
   Start : int
   Index : int
   Quote : Quote
   }

let InitState : State =
   {Start = 0; Index = 0; Quote = None }

let MoveNext (s : State) : State =
   {s with Index = s.Index + 1}

let FlipQuote (s : State) (text : string) : State =
   match text.[s.Index], s.Quote with
   | '\'', None   -> {s with Quote = Single}
   | '"' , None   -> {s with Quote = Double}
   | '\'', Single -> {s with Quote = None}
   | '"' , Double -> {s with Quote = None}
   | _ -> s

let StartNew (s : State) : State =
   {Start = s.Index; Index = s.Index; Quote = None}

let NotEmpty (s : string) : bool =
   not (System.String.IsNullOrWhiteSpace(s))

let GetToken (s : State) (text : string) : string =
   text.Substring(s.Start, s.Index - s.Start)

let GetChar (s : State) (text : string) : string =
   text.[s.Index].ToString()

let ExtractTokens (text : string) : seq<string> =
   let rec loop state =
      seq {
         if (state.Index < text.Length) then
            match text.[state.Index], state.Quote with
            | '"' , _
            | '\'', _     -> yield! FlipQuote state text |> MoveNext |> loop
            | ' ' , None
            | '(' , None
            | ')' , None  -> yield  GetToken state text
                             yield  GetChar  state text
                             yield! MoveNext state |> StartNew |> loop
            | _   , _     -> yield! MoveNext state |> loop
         else
            yield GetToken state text
      }
   loop InitState |> Seq.where NotEmpty

Refactored

type Quote =
   | Single
   | Double
   | None

type State = {
   Start : int
   Quote : Quote
   }

let InitState : State =
   {Start = 0; Quote = None }

let FlipQuote (state : State) (index : int) (text : string) : State =
   match text.[index], state.Quote with
   | '\'', None   -> {state with Quote = Single}
   | '"' , None   -> {state with Quote = Double}
   | '\'', Single
   | '"' , Double -> {state with Quote = None}
   | _ -> state

let StartNew (state : State) (index : int) : State =
   {Start = index; Quote = None}

let NotEmpty =
   System.String.IsNullOrWhiteSpace >> not

let GetToken (state : State) (index : int) (text : string) : string =
   text.Substring(state.Start, index - state.Start)

let GetChar (index : int) (text : string) : string =
   text.[index].ToString()

let ExtractTokens (text : string) : seq<string> =
   let rec loop index state =
      seq {
         if (index < text.Length) then
            match text.[index], state.Quote with
            | '"' , _
            | '\'', _     -> yield! FlipQuote state index text |> loop (index + 1)
            | ' ' , None
            | '(' , None
            | ')' , None  -> yield  GetToken state index text
                             yield  GetChar  index text
                             yield! StartNew state (index + 1) |> loop  (index + 1)
            | _   , _     -> yield! state |> loop (index + 1)
         else
            yield GetToken state index text
      }
   loop 0 InitState |> Seq.where NotEmpty

I'm not saying the below revision is an improvement but it has eliminated the need for MoveNext. The penalty is to have the index as a separate argument to loop which violates the idea of a state object. One could argue that the index is not a part of the (splitting)state but just an iterator variable and then everything are nicely justified again :-)

module RevisedSplitting =

    type String with
        member this.charAt index =
            this.[index]

    type Quote =
       | Single
       | Double
       | None

    type State = {
       Start : int
       Quote : Quote
       }

    let InitState =
       {Start = 0; Quote = None }

    let FlipQuote s index (text : string) =
       match text.charAt index, s.Quote with
       | '\'', None   -> {s with Quote = Single}
       | '"' , None   -> {s with Quote = Double}
       | '\'', Single -> {s with Quote = None}
       | '"' , Double -> {s with Quote = None}
       | _ -> s

    let StartNew s index =
       {Start = index; Quote = None}

    let NotEmpty s =
       not (System.String.IsNullOrWhiteSpace(s))

    let GetToken s index text =
       (string text).Substring(s.Start, index - s.Start)

    let GetChar index (text : string) =
       sprintf "%c" (text.charAt index)

    let ExtractTokens (text : string) =
       let rec loop index state =
          seq {
             if index < (text |> Seq.length) then
                match text.charAt index, state.Quote with
                | '"' , _
                | '\'', _     -> yield! FlipQuote state index text |> loop (index + 1)
                | ' ' , None
                | '(' , None
                | ')' , None  -> yield  GetToken state index text
                                 yield  GetChar  index text
                                 yield! StartNew state (index + 1) |> loop (index + 1)
                | _   , _     -> yield! state |> loop (index + 1)
             else
                yield GetToken state index text
          }
       loop 0 InitState |> Seq.where NotEmpty


City class and spec for testing it I have written a class and spec for testing my class. Can anyone determine whether or not this is a correct and good spec?

Class:

module Sitemap
=begin
Class Name: Cities
Function: This class is responsible for getting the data to create the sitemap
for each country according to cities.
=end
  class City
    attr_accessor :country_version, :directory, :country_host, :locale
    def initialize(country_version, directory, country_host,locale)
      @country_version = country_version
      @directory = directory
      @country_host = country_host
      @locale = locale
    end

    def get_data
      ::City.find_each(:conditions => {:country_version_id => @country_version.id}) do |city|
        I18n.locale=(@locale)
        yield entry(city)
      end
    end

    private
    def entry(city)
      {
        :loc => ActionController::Integration::Session.new.url_for(:controller => 'cities', :action => 'show', :city_name => city.name, :host => @country_host.value),
        :changefreq => 0.8,
        :priority => 'monthly',
        :lastmod => city.updated_at
      }
    end
  end
end

Spec:

require File.join(File.dirname(__FILE__), "/../spec_helper" )
module Sitemap
  describe City do

    before :all do
    @city = City.new :country_version, :directory, :country_host, :locale
    end

    describe "#new" do
      it "takes four parameters and returns a City object" do
        @city.should be_an_instance_of City
      end
    end

    describe "#country_version" do
      it "returns the correct country version" do
        @city.country_version.should eql :country_version
      end
    end

    describe "#directory" do
      it "returns the correct filepath" do
        @city.directory.should eql :directory
      end
    end

    describe "#country_host" do
      it "returns the correct country host" do
        @city.country_host.should eql :country_host
      end
    end

    describe "#locale" do
      it "returns the correct locale for translation" do
        @city.locale.should eql :locale
      end
    end

    describe "#get_data" do
      it "returns collections for xml entries" do
        @city.get_data.should eql ::City
      end
    end

  end
end

Here are a few things I thought of:

Use let when you can, it is a pretty versatile function for testing.

before :all
  @city = City.new :country_version, :directory, :country_host, :locale
end

Can be rewritten as:

let(:city) { @city = City.new :country_version, :directory, :country_host, :locale }

This will only call city when you use it.
I don't typically test accessors/intatiation but if I did, I would probably test it with a specify block, it is also good for most tests where the description is "it should do something correctly":

This is nice for simple tests that explain themselves

specify { city.should be_an_instance_of City }
When testing, I try to think in terms of cases:
Ex:

it "should act in manner x when no cities are found"
it "should act in manner y when 1 city is found"
it "should act in manner z when n cities are found"

I find testing 0, 1, n catches a lot of potential errors
The testing gods expect you to test first, then write code.  If you don't :D, then make sure that your test fails in the way you expect it to.