Find the nearest coin to be collected in a game I am creating a simple bot that collects coins in-game. The code runs under a game-loop so there are 60 ticks p/s

Here is the function that I use to check for the nearest coin (Game object) to be collected:

public GameObject getNearest(ID objectID) {

    LinkedList<GameObject> object = new LinkedList<GameObject>();
    for (int i = 0; i < handler.object.size(); i++) {
        GameObject temp = handler.object.get(i);
        if (temp.getId() == objectID) {
            object.add(temp);
        }
    }

    if (object.size() == 0)
        return null;

    else {
        GameObject nearest = object.get(0);
        for (int i = 0; i < object.size(); i++) {
            if (getDistance(this, object.get(i)) < getDistance(this, nearest)) {
                nearest = object.get(i);
            }
            object.remove(i);
        }
        return nearest;
    }
}

What this function would do is check for all the game objects, and add all the once that match the parameter in a list. It then will loop through the list and check for the nearest coin to the bot.

Is my function efficient regarding performance, speed, and memory usage? By calling the object.remove after every check, does it help? (If not, please mention why)

Is it okay that it calls the method 60 times p/s or I should limit it to execute once every 20 frames maybe? The thing is that I want it to be collecting the coins safely in the shortest time possible. Is there anything that I should take into consideration or something to improve in my code??

object should be plural, and should more clearly indicate what it contains. gameObjects would be preferable.

It's a good idea to always include curly braces, even when they're not required. It removes a possible source of later bugs.

It’s easier to read isEmpty() than size() == 0. You also don’t need the else statement, since the if returns.

If handler.object is a type that has an iterator() method, it would be better to use that than a for loop.

The performance of LinkedList is often worse than ArrayList. You should consider testing their relative performances.

You should code to interfaces, not implementations, where possible. List<GameObject> objects = … is preferable to LinkedList<GameObject> objects =.

If ID has a correct implementation of equals(), you should probably be using that. == asks if it’s the ID is the same object, not just if it has the same value.

In java, it’s preferable to only capitalize the first letter of an acronym, so objectId is preferred to objectID.

There’s probably something wrong with getDistance() - it should either be an instance method or you shouldn’t need to pass in this.

You don’t need to loop twice. Every time you find an object with a matching id, compare it’s distance to the current nearest object. Only keep the nearest. This will also save you from computing the distance twice.

As far as optimizing performance, you'll have to do some testing and see if it's working fast enough for you. Cutting out the one loop will make it closer to optimal, but we can't know how that will interact with the game.

If you were to apply all my suggestions, your code might look something like:

public GameObject getNearest(final ID objectId) {
    GameObject nearestObject = null;
    int distance = Integer.MAX_VALUE;

    for (int i = 0; i < this.handler.object.size(); i++) {
        final GameObject currentObject = this.handler.object.get(i);
        if (!currentObject.getId().equals(objectId)) {
            continue;
        }

        final int currentDistance = this.getDistance(this, currentObject);
        if (currentDistance < distance) {
            nearestObject = currentObject;
            distance = currentDistance;
        }
    }

    return nearestObject;
}


Generating 3D voxel terrain with Perlin Noise I've created this simple 3D voxel terrain generator using Perlin Noise. I have a few concerns about it though.

Is there any way to make it more performant? It currently takes ~1.5 seconds to generate a 200x200 map.
Am I splitting up the different "jobs" of the generator correctly?
Is my general code style good?

using UnityEngine;

/// <summary>
/// Terrain generator.
/// </summary>
public class TerrainGenerator : MonoBehaviour
{
    public GameObject cube;
    public int worldWidthX;
    public int worldWidthZ;

    public float lowerNoiseScaleValue;
    public float upperNoiseScaleValue;

    public float lowerNoiseScaleModifierValue;
    public float upperNoiseScaleModifierValue;

    private float noiseScale;
    private float noiseScaleModifier;

    /// <summary>
    /// Generates the cubes as children of a GameObject.
    /// </summary>
    public void InitalizeCubes()
    {
        for(float x = 0; x <= this.worldWidthX; ++x)
        {
            for(float z = 0; z <= this.worldWidthZ; ++z)
            {
                GameObject cube = Instantiate(
                    this.cube,
                    new Vector3(x, 0, z),
                    this.cube.transform.rotation
                ) as GameObject;

                cube.transform.parent = this.transform;
            }
        }
    }

    /// <summary>
    /// Sets the color of the cube based on the cube's height.
    /// </summary>
    /// <param name="cube">Cube.</param>
    /// <param name="cubeHeight">Cube height.</param>
    public void SetCubeHeightColor(Transform cube, float cubeHeight)
    {
        cube.renderer.material.color = new Color(cubeHeight / 5, cubeHeight, cubeHeight / 5);
    }

    /// <summary>
    /// Applies a height value to the transform of a cube.
    /// </summary>
    /// <param name="cube">Cube.</param>
    /// <param name="cubeHeight">Cube height.</param>
    public void ApplyHeightToCube(Transform cube, float cubeHeight)
    {
        int newHeight = Mathf.RoundToInt(cubeHeight * this.noiseScaleModifier);
        Vector3 newPosition = new Vector3(cube.transform.position.x, newHeight, cube.transform.position.z);
        cube.transform.position = newPosition;
    }

    /// <summary>
    /// Updates the positions of the cubes by giving
    /// each cube a specific perlin noise value,
    /// coloring them, and finally, applying the height
    /// values to the transform.position's of the cubes.
    /// </summary>
    public void GenerateCubes()
    {
        foreach(Transform cube in transform)
        {
            float noiseScaleAddition = Random.Range(this.noiseScale / 10, this.noiseScale / 9);
            float cubeHeight = Mathf.PerlinNoise(
                (cube.transform.position.x / (this.noiseScale + noiseScaleAddition)),
                (cube.transform.position.z / (this.noiseScale + noiseScaleAddition))
            );
            SetCubeHeightColor(cube, cubeHeight);
            ApplyHeightToCube(cube, cubeHeight);
        }
    }

    /// <summary>
    /// Start this instance.
    /// </summary>
    void Start()
    {
        this.noiseScale = Random.Range(this.lowerNoiseScaleValue, this.upperNoiseScaleValue);
        this.noiseScaleModifier = Random.Range(this.lowerNoiseScaleModifierValue, this.upperNoiseScaleModifierValue);

        this.InitalizeCubes();
        this.GenerateCubes();
        Screen.lockCursor = true;
    }
}

For those who are curious, here are a few pictures of sample terrain:

If you want to critique or suggest changes to the algorithm, I'm open to them.

I don't know much about Unity, but one of the Unity operations must be the bottleneck here if it takes 1.5 seconds to process 40k cubes.  I'd focus on reducing the number of Unity operations you're doing (manipulating the game objects).  For example, you're first placing all the cubes at y=0, then moving them later.  Instead, try generating the Perlin Noise first into an array, and then place the cubes at the correct height on the Instantiate call.

Also consider this line:

cube.renderer.material.color = new Color(cubeHeight / 5, cubeHeight, cubeHeight / 5);

You have 40k cubes but only about 20 colors.  Is there some way of sharing materials (or even renderers) between the cubes?  You may be asking Unity to manage many copies of identical materials.  Look into other ways to share resources; is there some way to only create a few cubes with different colors, and render one entire height-layer with copies of it?

As for general coding style:

You have public GameObject cube; as an instance variable, but you also use the word cube all over the place for local variables.  Is there a better name you could give this, like templateCube?

This is comment is not necessary:

/// <summary>
/// Sets the color of the cube based on the cube's height.
/// </summary>
/// <param name="cube">Cube.</param>
/// <param name="cubeHeight">Cube height.</param>
public void SetCubeHeightColor(Transform cube, float cubeHeight)

This takes up a lot of lines to give me the same information as your method signature ... although when my eyes see "SetCubeHeight" I assume you're setting the cube's height, but you're actually setting the color.  Consider SetCubeColorByHeight instead.

Usually, everything that your class needs to function properly should be an argument in its constructor.  This may not be possible with a Unity MonoBehavior, but I thought I'd throw it out there.


Mixing in-class initialization and initializer lists From this question, I do know that initialization list and in-class initialization are different things.

The class in the following code has members with in-class initializers and those initialized in initialization list in constructors:

class Bamboo {
public:
    int a = {0};
    int b;

    Bamboo() :a(3), b(12) {
        std::cout << a << ", " << b;
    }
};

int main() {
    Bamboo spikey; // outputs "3, 12"
}

This code compiles, but is it okay? Is it bad practice?

The only reason I am not using the initialization list for all members is that in the class I have many other members which are never initialized by constructor arguments. Plus, it's tedious to write the entire initialization list out in the constructor:

class Bamboo {
public:
    int a;
    std::string str;
    bool b;

    int c = {1}, d = {2}, e = {3}, f = {4}, g = {5};

    // each of c, d, e, f and g is always initialized to the same values regardless of which constructor is called
    Bamboo(bool cb)                           :a(1),  str("hello"), b(cb)    {}
    Bamboo(std::string cstr, int ca)          :a(ca), str(cstr),    b(false) {}
    Bamboo(int ca, bool cb, std::string cstr) :a(ca), str(cstr),    b(cb)    {}
}

Well, the first example is bad for a simple reason: It contains code which is never used, as none of the in-class-initializers are used by any constructor.

The second one is fine, using in-class-initializers for any initializations multiple constructors share (you don't even have to decide between multiple choices).
One can argue about extracting the constant initializers for the other three members out of the single constructor having one for each respective one, but that's debatable.

There's only one more criticism of your code:
The last single-line-comment is too long, you should have split it.


Event delegation without jQuery I created event delegation like concept which is present in jQuery. AFAIK, event delegation is used to register an event for an element which is supposed to be added dynamically. So, in jQuery we do the following:

$(document.body)
    .on('click', '.main', function(){ /* code here */ });
    .on('click', 'div.main', function(){ /* code here */ });
    .on('click', 'div#main.main', function(){ /* code here */ });
    .on('click', 'div#main.main[attr="1"]', function(){ /* code here */ });

So, instead of doing this event delegation in jQuery, I am doing using pure JavaScript. Here is my code:

var sb = (function () {
    var eventObject = {};
    document.body.addEventListener('click', function(e){
        console.dir(e.currentTarget);
        var el = e.target;
        var parent = el.parentElement;
        while(parent !== document.body){
            for(var item in eventObject){
                var elements = document.querySelectorAll(item);
                for(var i = 0, ilen = elements.length; i < ilen; i++){
                    if(el === elements[i]){
                        eventObject[item].call(el, e);
                        return;
                    }
                }
            }
            el = parent;
            parent = el.parentElement;
        }
    }, false);

    return {
        on: function(event, selector, callback){
            eventObject[selector] = callback;
            return sb;
        }
    }
})();

As you can see, in the above code, I have hard coded the click event (which is fine for now)

Now, I will use the above code like this:

sb
    .on('click', '.main', function(){ /* code here */ });
    .on('click', 'div.main', function(){ /* code here */ });
    .on('click', 'div#main.main', function(){ /* code here */ });
    .on('click', 'div#main.main[attr="1"]', function(){ /* code here */ });

This is working fine but I feel like I am overdoing things here in the above created plugin.

The one thing different between your implementation and jquery.on is that jQuery allows you to bind on any element. One reason for that is performance. If on a deep tree, it would take a while for it to reach the delegate target. That's one reason jquery.live was deprecated.

Another is that your eventObject only accepts one callback per selector. If I were to register another callback under the same selector, then it would overwrite whatever was previously registered. Consider creating an array on the fly and push to it. You will need to change the way your code calls callbacks.


Pulling player records I was able to pull the records I wanted but I have a feeling it could be written better for these particular MySQL query strings.

SELECT ID,XAxis,YAxis,Player,Castle,Alliance FROM SC75
WHERE Snap = (SELECT MAX(SavedSnap) FROM DataSnap WHERE Server = 75)
AND hex(Player) IN (hex('Vandiel'))
UNION
SELECT SC.ID,XAxis,YAxis,SC.Player,Castle,Alliance FROM SC75 AS SC
INNER JOIN AltFiller AS AF ON hex(AF.Player) IN (hex('Vandiel'))
WHERE SC.Player = AF.Alts
AND Snap = (SELECT MAX(SavedSnap) FROM DataSnap WHERE Server = 75)
ORDER BY Player,Castle

The two parts to the UNION have too much in common.  I believe this query is equivalent to yours.

SELECT ID, XAxis, YAxis, Player, Castle, Alliance
    FROM SC75
    WHERE
        Snap = (SELECT MAX(SavedSnap) FROM DataSnap WHERE Server = 75)
            AND
        (
            (hex(Player) IN (hex('Vandiel'))
                OR
            Player IN
            (
                SELECT AF.Alts
                    FROM AltFiller AS AF
                    WHERE hex(AF.Player) IN (hex('Vandiel'))
            )
        )
    ORDER BY Player, Castle;


Loading content in page via jQuery I'm doing a website in CodeIgniter and I'm loading the content page via jQuery, but I don't know if this is a good practice or not. Could I improve it?

jQuery:

// Another question here: how can I group the repeated code in a function:

$(function() {

var control = '../Indoamericana/Intranet/index/Proceso/';

var loadPage = function(page){
    $(".page-content").load(page);
};

$("#gestion_directiva").click(function(event) {
    var process = 1;
    loadPage(control + process);
});

$("#gestion_calidad").click(function(event) {
    var process = 2;
    loadPage(control + process);
});

$("#gestion_academica").click(function(event) {
    var process = 3;
    loadPage(control + process);
});

Controller:

/**
* index();
*
* funcion que carga la información del proceso en la intranet
* @param String $process Identificador del proceso a cargar
* @return Vista del proceso indicado
*/

public function index($process, $idProcess){

    $data['data'] = $this->intranet_model->getProcessInfo($idProcess);
    $data['member'] = $this->intranet_model->getMembers($idProcess);
    $data['proceso'] = 'GI7';

    $route = '/Modules/Intranet/';
    $route .= $process;

    $this->load->view($route, $data);
}

View:

            <?php foreach ($data as $row): ?>
            <?php echo $row->name ?>
            <?php endforeach ?>

                Página Principal

                Intranet

                    <?php foreach ($data as $row): ?>
                    <?php echo $row->name ?>
                    <?php endforeach ?>

You might already know this but you can add a library class called 'template' it allows you to make a kind of a masterpage where you can load all different php files, for example your header - content - footer or anything else, seperately into one page.

Your controller will look like this for example:

 public function example() {
        $partials = array('header' => 'header', 'navigation' => 'navigation', 'content' => 'content');
        $this->template->load('masterpage.php', $partials);
    }

Read more at http://ellislab.com/codeigniter%20/user-guide/libraries/parser.html

It's really use to use once you know how it's done.

For example you could use for every page the same navigation but another index and header.

The masterpage looks like this:

<!DOCTYPE html>

<?php echo $navigation; ?>
<?php echo $header; ?>
<?php echo $content; ?>

The last thing you need to do is search for the library file on the net upload it and autoload the library in your configs, file: autoload or just in the constructor of your controller. I recommend autoloading the template library because you normally use it at every end of a controller to make the full view.


Finding the maximum element of a Stack I have been solving this problem of Hackerrank recently .. https://www.hackerrank.com/challenges/maximum-element
A little bit about the problem

You have an empty sequence, and you will be given N queries. Each query is one of these three types:
1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

And my code is here - which passes the first 12 test cases.
import java.util.*;

public class Stackers {

    public static Stack<Integer> stack;
    public static String output = "";

    public static void main(String[] args) {

        stack = new Stack<>();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

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

            String op = sc.nextLine();
            performOperation(op);

        }

        sc.close();
        if(!output.isEmpty()){
            System.out.println(output);

        }

    }

    public static void performOperation(String op) {

        if (op.startsWith("1")){

            String remains = op.split(" ")[1];
            int rem = Integer.valueOf(remains);
            stack.push(rem);

        }else if(op.equalsIgnoreCase("2")){

            stack.pop();

        }else if(op.equals("3")){

            int max = (int) Collections.max(stack);
            output += (max + "\n");

        }

    }

}

But fails with "timeout" from the 13th test case. Most of the times, logic will be wrong, so I ran the 13th test case locally in my computer . I got the output in 1.3- 1.6 minutes tho:)
How can I improve my code. Please guide me or if it is the wrong stack exchange community, please advise me.

This type of question actually requires a little thinking outside the box.

The idea here, since we need to store the max with each element, is to use the built-in Stack more creatively.

public class ChallengeValue {
    public int max;
    public int value;
}

I think that should tell you where we're going:

import java.util.*;

public class Stackers {
    public static Stack<ChallengeValue> stack;
    public static String output = "";

    public static void main(String[] args) {
        stack = new Stack<>();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        for(int i = 0 ; i < n + 1; i++){
            String op = sc.nextLine();
            performOperation(op);
        }

        sc.close();
        if(!output.isEmpty()){
            System.out.println(output);
        }
    }

    public static void performOperation(String op) {
        if (op.startsWith("1")) {
            String remains = op.split(" ")[1];
            int rem = Integer.valueOf(remains);

            ChallengeValue newVal = new ChallengeValue();
            newVal.value = rem;

            ChallengeValue last = stack.peek();
            newVal.max = last.max > newVal.value ? last.max : newVal.max;
            stack.push(newVal);
        } else if(op.equalsIgnoreCase("2")) {
            stack.pop();
        } else if(op.equals("3")) {
            int max = stack.peek().max;
            output += (max + "\n");
        }
    }
}

Now we are storing the max with the stack values, so when we pop one we get the new max immediately. This turns the max (3) command into an \$O(1)\$ operation. (Your version is likely \$O(n)\$.)


Converting and enriching an array of data The method below converts an array of TheatreListData objects to an array of TheatreListDataWrapper. It also loads additional attributes such as patientIdentifierNumber and requestText to enrich the converted data.

This method is called by many EJBs, and so I'm especially looking for ways to improve performance.

/**
* Converts TheatreListDatas into TheatreListDataWrappers. This also
* loads the attributes that has to be generated from client such as
* patientIdentifierNumber, requestText
*
* @param theatreListData
* @return TheatreListDataWrapper[]
*/
public TheatreListDataWrapper[] wrapData(TheatreListData[] theatreListData){

    TheatreListDataWrapper[] wrapperList = wrapDataWithoutRequestData(theatreListData);

    if (wrapperList != null && wrapperList.length > 0)
    {
      Set<String> requestIds = new HashSet<String>();

      for (TheatreListData listData : theatreListData)
      {

        // Collect request id for each List Data into a set
        String requestId = listData.getCarePlan().requestId;
        //Should check for '-1' here to avoid calls to fetch invalid requests.
        //'-1' could have been saved with registrations with 'None' requests.
        if (requestId != null && requestId.trim().length() > 0 && !requestId.equals("-1"))
        {
          //Since adding to a set no duplicates are possible.
          requestIds.add(requestId);
        }
      }

      //Load request Id, request Text map using the collected request ids.
      Map<String, String> requestMap = Collections.emptyMap();
      if (!requestIds.isEmpty())
      {
        requestMap = getRequestDelegator().getRequestPresentationStringsByIds(new ArrayList<String>(requestIds));
      }

      //Create wrappers & fill with loaded data.
      for (int i = 0; i < theatreListData.length; i++)
      {
        TheatreListDataWrapper wrapper = wrapperList[i];

        TheatreListData listData = theatreListData[i];
        String requestId = listData.getCarePlan().requestId;
        if (requestId != null && requestId.trim().length() > 0)
        {
          wrapper.requestText = requestMap.get(requestId) != null ? requestMap.get(requestId) : "";
        }

        wrapperList[i] = wrapper;
      }

    }
    return wrapperList;

  }

Depending on the constant overhead of retrieving the request presentation string for a request ID (i.e. is it considerably more efficient to get all the strings for a bunch of IDs at once than for each ID separately?), a better design might be to iterate over the theatre list only once, getting the representation strings as you go and caching the results in a Map.

Map<String, String> cache = new HashMap<>();
for (int i = 0; i < theatreListData.length; i++) {
    TheatreListDataWrapper wrapper = wrapperList[i];
    TheatreListData listData = theatreListData[i];
    String requestId = listData.getCarePlan().requestId;
    if (validRequestId(requestId)) {
        String text = cache.get(requestId);
        if (text == null) {
            text = getRequestDelegator().getRequestPresentationStringsById(requestId);
            cache.put(requestId, text);
        }
        wrapper.requestText = text;
    }
}

This is probably not a good idea of getting the request text requires, say, a database query.

Other than that, I can think of no algorithmic improvements. You should store the result of requestMap.get(requestId) in a local variable so you don't do the call twice; that's inefficient. Perhaps you can modify getRequestPresentationStringsByIds to take a Collection instead of a List so that you don't have to wrap your set in an ArrayList. Can't think of more.


Generate valid random rgb color strings I'd want to see if is possible to optimize performance even further of the following generate color method.

package generacolorrgb;

import java.util.Random;

public class GeneracolorRGB {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Random r = new Random();
        for (int i = 0; i < 100; i++) {
            System.out.println(generateColor(r));
        }

    }

    private static String generateColor(Random r) {
        StringBuilder color = new StringBuilder(Integer.toHexString(r
                .nextInt(16777215)));
        while (color.length() < 6) {
            color.append("0");
        }

        return color.append("#").reverse().toString();

    }

}

Average time it takes on my machine: 1650704.333 ns

Here are some comments related to your code:

Strange place to initialise the Random() – This should either be in within the generateColor() function, or some static initialisation. As it stands now, it looks strange that you need to include the random generator to as a parameter to your function. You are better of using a static initialization
Strange magic number, 16777215 – What is this number? It is not very clear that this is actually the 0xFFFFFF denoting the maximum color number. Also note that nextInt(n) returns a number in the range 0 up to n, but not including n. In other words, you should use 0x1000000
Tricking into being 6 characters – If you add 0x1000000 to the number before converting to hexadecimal you are ensured six digits, and don't need the trick for 6 characters, and can return a substring (instead of using a while loop)

Applying this and your code looks something like this:

package generacolorrgb;

import java.util.Random;

public class GeneracolorRGB {

    static Random randomGenerator;

    static {
        randomGenerator = new Random();
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            System.out.println(generateColor());
        }
    }

    private static String generateColor() {
        int newColor = 0x1000000 + randomGenerator.nextInt(0x1000000);
        return "#" + Integer.toHexString(newColor).substring(1, 7);
    }
}

Added: An even nicer variant would be:

    private static String generateColor() {
        int newColor = randomGenerator.nextInt(0x1000000);
        return String.format("#%06X", newColor);
    }

Here we let the Formatter handle the formatting issue, and it does indeed look nicer! And we don't need to make sure the random number is above the legal range, as the formatter handles it.


ZigZag tree travesal The question is taken for a coding interview I had, it is also in geeks for geeks,  https://www.geeksforgeeks.org/zigzag-tree-traversal/

you are given a binary tree and you need to print it in a ZigZag/Snake order
for level one from left to right and the next level from right to left and so on.

I was asked only to come up with a solution I used a queue and a stack in the real interview, when I coded it now I tried using 2 stacks.

Please review the code as if it was a real interview, complexity, coding style, assume I have 20-30 minutes to code. you can ignore the test case.

Thanks.

using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    [TestClass]
    public class PrintBinaryTreeZigZag
    {

        [TestMethod]
        public void PrintBinaryTreeZigZagTest()
        {
            BinaryTree root = new BinaryTree
            {
                Value = 1,
                Left = new BinaryTree { Value = 2 },
                Right = new BinaryTree { Value = 3 }
            };
            root.Left.Left = new BinaryTree { Value = 7 };
            root.Left.Right = new BinaryTree { Value = 6 };
            root.Right.Left = new BinaryTree { Value = 5 };
            root.Right.Right = new BinaryTree { Value = 4 };
            List<int> res = PrintBinaryZigZag(root);
            List<int> expected = new List<int> { 1, 3, 2, 7, 6, 5, 4 };
            CollectionAssert.AreEqual(expected, res);

        }

        public List<int> PrintBinaryZigZag(BinaryTree root)
        {
            if (root == null)
            {
                return null;
            }
            Stack<BinaryTree> currentLevel = new Stack<BinaryTree>();
            Stack<BinaryTree> nextLevel = new Stack<BinaryTree>();
            List<int> result = new List<int>();
            currentLevel.Push(root);
            bool leftToRight = true;
            while (currentLevel.Count > 0)
            {
                BinaryTree temp = currentLevel.Peek();
                currentLevel.Pop();
                if (temp != null)
                {
                    //same as print
                    result.Add(temp.Value);

                    if (leftToRight)
                    {
                        if (temp.Left != null)
                        {
                            nextLevel.Push(temp.Left);
                        }
                        if (temp.Right != null)
                        {
                            nextLevel.Push(temp.Right);
                        }
                    }
                    else
                    {
                        if (temp.Right != null)
                        {
                            nextLevel.Push(temp.Right);
                        }
                        if (temp.Left != null)
                        {
                            nextLevel.Push(temp.Left);
                        }
                    }
                }
                if (currentLevel.Count == 0)
                {
                    leftToRight = !leftToRight;
                    Stack<BinaryTree> tempStack = currentLevel;
                    currentLevel = nextLevel;
                    nextLevel = tempStack;
                }
            }
            return result;
        }
    }
    public class BinaryTree
    {
        public BinaryTree Left { get; set; }
        public BinaryTree Right { get; set; }
        public int Value { get; set; }
    }
}

The algorithm seems okay so I'll review the OOP aspect.
Naming

The method named PrintBinaryZigZag but it doesn't print anything.
The class named BinaryTree isn't really a binary tree, it's more of a Node.

Implementations vs interfaces
You return List<int>, but do you really need a list?
The goal of this method if to return a list that represents a binary tree.
Should you be able to add/remove objects from this list? Do you need the indexer, that is specific to the list? I don't think so. In this case, return IEnumerable<int>.
C# details
BinaryTree temp = currentLevel.Peek();
currentLevel.Pop();

You could simply do : BinaryTree temp = currentLevel.Pop();
Flow
if (leftToRight)
{
    if (temp.Left != null)
    {
        nextLevel.Push(temp.Left);
    }
    if (temp.Right != null)
    {
        nextLevel.Push(temp.Right);
    }
}
else
{
    if (temp.Right != null)
    {
        nextLevel.Push(temp.Right);
    }
    if (temp.Left != null)
    {
        nextLevel.Push(temp.Left);
    }
}

I'm sure there's a way to make this smaller. Now, this is a take to maybe give you an idea, I don't think it's perfect, it's weird to use a foreach when you only have two elements in the list. But maybe if can give you an idea to make this code smaller.
var orderedNodes = leftToRight ? new []{ temp.Left, temp.Right } : new []{ temp.Right, temp.Left };

foreach(var node in orderedNodes.Where(n => n != null))
{
    nextLevel.Push(node);
}

This :
if (currentLevel.Count == 0)
{
    leftToRight = !leftToRight;
    Stack<BinaryTree> tempStack = currentLevel;
    currentLevel = nextLevel;
    nextLevel = tempStack;
}

I think it could be outside your while loop.


C++11 merge sort implementation I've tried implementing merge sort in C++ just by looking at this Wikipedia graphic. Comparing my code to other merge sort code implementations, it doesn't look quite the same at first glance. Have I done it in an acceptable way? How can it be improved, particularly using modern C++?

#include <iostream>
#include <deque> // using deque for `pop_front`
#include <random>

std::deque<int> mergeChunks(std::deque<int> &a, std::deque<int> &b);

std::deque<int> mergeSort(const std::deque<int> &d) {
    std::deque<std::deque<int>> chunks; // in the end, the first element will be the sorted list
    for (const auto &a : d) {
        // add each element of `v` to `chunks` as its own chunk
        chunks.push_back({ a });
    }

    while (chunks.size() > 1) {
        std::deque<std::deque<int>> tmp; // this will be the new set of chunks at the end of this iteration
        for (auto i = 0; i < chunks.size() - 1; i += 2) {
            tmp.push_back(mergeChunks(chunks[i], chunks[i + 1]));
        }

        // if there is an odd number of elements, then add the one that was missed in the for loop to `tmp`
        if (chunks.size() % 2 == 1) {
            tmp.push_back(chunks[chunks.size() - 1]);
        }

        chunks = tmp;
    }

    return chunks[0];
}

std::deque<int> mergeChunks(std::deque<int> &a, std::deque<int> &b) {
    std::deque<int> ret;
    while (true) {
        // if all the elemnts of one chunk have been added to `ret` then add the remaining
        // elements of the other chunk to the end of `ret` (knowing that they're sorted)
        if (a.size() == 0) {
            ret.insert(ret.end(), b.begin(), b.end());
            return ret;
        }
        if (b.size() == 0) {
            ret.insert(ret.end(), a.begin(), a.end());
            return ret;
        }

        // always comparing the first elements of each chunk. After an element is added
        // to `ret`, pop it from the chunk
        if (a[0] < b[0]) {
            ret.push_back(a[0]);
            a.pop_front();
        }
        else {
            ret.push_back(b[0]);
            b.pop_front();
        }
    }
    return ret; // never reached
}

int main() {
    auto list = mergeSort({ 8, 7, 6, 5, 4, 3, 2, 1 });
}

Looks like a good bottom-up merge. A bit heavy on the memory at the first glance though.
if (a[0] < b[0]) loses stability. The main advantage of the merge sort is is that it retains the order of elements which compare equal (for sorting integers it is irrelevant, but think of sorting structures). Your code merges b[0] first. Consider a[0] <= b[0] instead.
Handling the unlikely conditions such as a.size() == 0 and b.size() == 0 better be done outside of the loop. Consider instead

while (a.size() > 0 && b.size() > 0) {
    do_actual_merge();
}
ret.insert(ret.end(), a.begin(), a.end());  // No-op if a.size() == 0
ret.insert(ret.end(), b.begin(), b.end());  // No-op if b.size() == 0
return ret;

I am not sure that chunks.size() % 2 == 1 is the best way to express your intentions. I'd go for i < chunks.size(), even though it lifts a declaration of i out of the loop.


Working with cached generator values I have set of values represented by a class. The class should be initialised with  a generator to limit memory use.

The class itself is the iterable, having __iter__, and the iterator, having __next__ (see below).

Since I want to be able to iterate over the set of values multiple times, I cache the generated values in a list. In __iter__, I check if I already have iterated over all values, and then return iter of the cached values, or self to continue with next, respectively.

Here's the code stripped down to the relevant parts:

class SetOfValues(object):
    def __init__(self, values):
        self._values = values
        self._values_generated = []
        self._done = False

    def __iter__(self):
        if self._done:
            return iter(self._values_generated)
        else:
            return self

    def __next__(self):
        try:
            value = next(self._values)
            self._values_generated.append(value)
            return value
        except StopIteration:
            self._done = True
            raise StopIteration("the end")

Then call it with:

x = SetOfValues((value for value in [1,2,3]))

for i in x:
    print(i)

Is this generally a good way to do it when you may need generated values more than once?
Might it be better if __iter__ yields the value?
In terms of usage of the class: might it be better to always rewind and let iter start with pos 0? Currently, iterating through the values, stopping early, then iterating again, would obviously just continue at the last index when not all values have been generated yet.

Thanks.

You have a bug. Take the following code, and output:

s = SetOfValues(iter([1, 2, 3, 4, 5, 6]))
print(list(zip(s, s)))
print(list(zip(s, s)))

[(1, 2), (3, 4), (5, 6)]
[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]

This is quite a substantial bug. As I would only use SetOfValues over a list, if I can get the correct list without consuming the iterator. Because if the iterator is consumed, by the time I loop through the list again, then I've used the most long-winded version of list known.

The way I'd resolve this is to build the list whilst consuming the iterator. This would look something like:

def cache(it, l):
    for i in it:
        l.append(i)
        yield i

However, we don't know if the iterator has been consumed if we stick with that. So I'd abuse lists a little more, so that we have a 'return' list, that returns the stored data, and whether the iterator has been consumed.

Other than that, I'd use itertools.chain so that we can change the list and the iterator together. However if the iterator has been consumed, then I'd return the list as an iterator.

Resulting in:

def cache(it, ret):
    l = ret[0]
    for i in it:
        l.append(i)
        yield i
    ret[1] = True

class SetOfValues(object):
    def __init__(self, values):
        self._info = [[], False]
        self._it = cache(values, self._info)

    def __iter__(self):
        l, finished = self._info
        if finished:
            return iter(l)
        else:
            return itertools.chain(l, self._it)

However, I'd heed the advice of itertools.tee.

  In general, if one iterator uses most or all of the data before another iterator starts, it is faster to use list() instead of tee().

And so, I'd use list instead in most cases.


TI-BASIC interpreter for Fishstacks Fishstacks is a deadfish derivative based on a stack the stack can only hold four elements when a fifth element is pushed the bottom element is kicked out and eventually printed out to the screen.

I've come up with an interpreter in TI-BASIC for my calculator. However, I fell slightly guilty about using all four variables ABCD. I wonder if there could be a better way? Maybe with lists (arrays). I've just started learning about them, so I don't feel confident switching over yet. Any guidance would be appreciated.

Also, in order not to push anything to the screen until something falls off the stack, I've had to initialize variables to -2. This is the main reason I have not converted to arrays yet; I don't see how they could address this issue. (maybe even throw a DOMAIN error).

:ClrHome
:Disp "FISHSTACKS IDSP","INTERPRETER"
:0->I
:-2->A
:A->B
:B->C
:C->D
:Input Str1
:While I<length(Str1)
:I+1->I
:sub(Str1,I,1)->Str2
:If Str2="I"
:A+1->A
:If Str2="D"
:A-1->A
:If Str2="S"
:A^2->A
:If Str2="P" and D>-1
:Then
:Disp D
:C->D
:B->C
:A->B
:0->A
:End
:If A=256 or A=-1
:0->A
:If A=-2
:Stop
:End

By convention, I've represented the STO→ character, → with ->

I was asked by @Timtech to join + post an improvement. Using arrays is a lot easier to understand, and there were so many optimizations that I decided to completely re-write the code. I'm sure it could be improved by other advanced programmers like me, as I'm using several long expressions here... note that L1 represents list #1 (2nd + 1 on the calculator) and ~ is the negative token.

:ClrHome
:Disp "FISHSTACKS IDSP","INTERPRETER
:DelVar IInput Str1
:DelVar L1~{2,2,2,2→L1
:While I<length(Str1
:I+1→I
:sub(Str1,I,1→Str2
:(Str2="I")-(Str2="D
:Ans+L1(4→L1(4
:If Str2="S
:L1(4)²→L1(4
:If Str2="P
:Then
:L1(1
:If 2+Ans
:Disp Ans
:ΔList(cumSum(L1->L1
:0->L1(4
:End
:L1(4
:If Ans=256 or Ans<0
:0->L1(4
:End

Improvements

Saved bytes by removing several unneeded ending parentheses and quotes
Used DelVar since it does not need a following colon
Used an array instead of four variables
Used a complex expression :(Str2="I")-(Str2="D saved to Ans to save space
Used ΔList(cumSum(L1->L1 to get L1 minus its first element
Several others I'm not listing due to their minisculity; mainly using Ans to save space and speed


AT&T Assembly - Basic loop & write The code loops to display "Hello, World!" ten times. I would like someone to criticize it. I know that's far from being good assembly but I only started learning it a few days ago and I would like to improve.

Would it be better to use the %rax registers and syscall instead of int $0x80 ?

.section .data
  hello: .string "Hello, world!\n"
  len = . -hello

.section .bss

  .macro write str, len
    movl $WRITE, %eax
    movl $STDOUT, %ebx
    movl \str, %ecx
    movl \len, %edx
    int $0x80
  .endm

  .macro exit code
    movl $EXIT, %eax
    movl \code, %ebx
    int $0x80
  .endm

.section .text
  .globl _start

  .equ EXIT, 1
  .equ WRITE, 4
  .equ STDOUT, 1

  _start:
    mov $1, %esi
    l:
      write $hello, $len
      inc %esi
      cmp $10, %esi
      jle l

   exit $0

Also, if someone could explain len = . -hello, that's the only thing I couldn't understand and copied online.

Let's start with the easy one:

. - hello - You need to understand that hello refers to an address. And that . refers to the "current" address. So . - hello is the distance between the current location and hello; effectively the length of hello.

Just one of those tricks you learn.  While you could manually put the length into len, there's always the chance that someday someone would change the contents of hello, and forget to change len.  Done this way, it's self-maintaining. Being able to compute this at 'assembly time' rather than counting bytes during run time is also a bonus.

As for the code itself, let me start with the main point: Comments.

Assembly can be tricky to code correctly, and sometimes is even harder to maintain.  Especially when you can't figure out what #@%! the guy who was writing it was trying to do.

I realize that this is just a beginner's project.  But you should acquire the habit of commenting early:

Comments at the top of the code telling the purpose of the file.
Comments at the top of routines (and macros) telling what they do.
Comments at the end of individual statements describing the intent.

As an example:

    exit $0 ; Exit the application with return code 0

While to a veteran assembly programmer this comment may seem obvious, to a beginner (and everyone is a beginner at some point), it makes the intent significantly clearer.  Just a few words of text can take a screen full of numbers and symbols and provide clarity.  Maintainers of your code (as well as your future self) will thank you.

Next (in no particular order) I would look at this section of code:

mov $1, %esi
l:
  write $hello, $len
  inc %esi
  cmp $10, %esi
  jle l

As I'm sure you are aware, the purpose of the cmp instruction is to set the flags so that you can use conditional instructions like jle.  However, there are other instructions that adjust those same flags.  For example, dec:

mov $10, %esi
l:
  write $hello, $len
  dec %esi
  jnz l

Nothing magical, but it does save an instruction.

Next we've got

  Wouldn't it be better to use the %rax registers and syscall instead of int $0x80?

It absolutely would be better to use syscall.  IF you were programming for 64bit.  int 0x80 is correct for 32bit.  And when I say 32/64bit, I'm referring to whether the application is 32 bit or 64bit, not the OS you are running on.

Note: The function number (and where each of the arguments go) are different between int 0x80 and syscall.


Parsing log files in Haskell I am working through the online materials for CIS 194, a upenn haskell class (not taking the class). This exercise is to parse an error log, and it gives a few function signatures to implement, ending with the very last one whatWentWrong. Please help me make the code more idiomatic, particularly whatWentWrong. My haskell level is: understood LYAH but have not written much code.

{-# OPTIONS_GHC -Wall #-}
module LogAnalysis where

import Log -- https://github.com/dustingetz/sandbox/tree/master/cis194/hw2

parseMessage :: String -> LogMessage
parseMessage s = case words s of
  -- I 5053 pci_id: con ing!
  ("I":t:msg) -> LogMessage Info (read t) (unwords msg)

  -- W 3654 e8] PGTT ASF!
  ("W":t:msg) -> LogMessage Warning (read t) (unwords msg)

  -- E 47 1034 'What a pity it
  ("E":sev:t:msg) -> LogMessage (Error $ read sev) (read t) (unwords msg)

  _ -> Unknown s

parse :: String -> [LogMessage]
parse s = map parseMessage $ lines s

insert :: LogMessage -> MessageTree -> MessageTree
insert (Unknown _) node = node
insert m Leaf = Node Leaf m Leaf
insert m@(LogMessage _ t _) (Node l' m'@(LogMessage _ t' _) r')
  | t <= t' = Node (insert m l') m' r'
  | t > t' = Node l' m' (insert m r')

build :: [LogMessage] -> MessageTree
build ms = foldl (flip insert) Leaf ms

inOrder :: MessageTree -> [LogMessage]
inOrder (Node l m r) = inOrder l ++ [m] ++ inOrder r
inOrder Leaf = []

--fmap ((take 10) . inOrder . build) $ testParse parse 100 "error.log"

whatWentWrong :: [LogMessage] -> [String]
whatWentWrong ms = map (\(LogMessage _ _ s) -> s) $
                   filter (\(LogMessage msgType _ _) ->
                            case msgType of
                             Error sev -> sev >= 50
                             _ -> False) $
                   inOrder $ build ms

Concerning whatWentWrong, the main problem is that the function isn't total. This means that for Unknown it will fail badly and unconditionally.

If you declare the functions from map and filter as named functions in a where (or let block), you will be able to check for Unknown as well in pattern matching. Also, you can combine several constructors in a pattern.

There are two options how to fix map: Either return some String for Unknown, or remove such entries. I'll show an example for the latter option using mapMaybe:

whatWentWrong :: [LogMessage] -> [String]
whatWentWrong = mapMaybe getMsg
                . filter filterExp
                . inOrder . build
  where
    filterExp (LogMessage (Error sev) _ _) = sev >= 50
    filterExp _                            = False
    getMsg (LogMessage _ _ s) = Just s
    getMsg _                  = Nothing

Also note that you can declare this function as a composition of functions, in so-called point-free style.


Matching a time interval using regex What I needed to do was check whether a given string matches a certain pattern. The pattern is this:

00:00:00,000 --> 00:00:00,000

Things to keep in mind:

The 0s can be numbers from 0 to 9.

The pattern must be alone in a single line; the line has to only consist of the pattern.

I came up with this:

"^(\\d\\d):(\\d\\d):(\\d\\d),(\\d\\d\\d) --> (\\d\\d):(\\d\\d):(\\d\\d),(\\d\\d\\d)"

I tested it a few times and strings that respect the pattern return true, the ones that don't, return false, as they should.

Here's a test case:

import java.util.regex.Pattern;

public class TestCaseRegex {

    public static void main(String[] args) {
        //will return true
        String testOne = "00:01:23,846 --> 00:01:26,212";

        //will return false, there's a letter where a number should be
        String testTwo = "00:01:23,84a --> 00:01:21,221";

        //will return true
        String testThree = "00:05:54,846 --> 00:01:16,450";

        //will return false. The string doesn't match the format.
        String testFour = "00:05:54,6 --> 00:0116,450";

        System.out.println(patternMatch(testOne));
        System.out.println(patternMatch(testTwo));
        System.out.println(patternMatch(testThree));
        System.out.println(patternMatch(testFour));
    }

    public static boolean patternMatch(String str) {
        Pattern p = Pattern.compile("^(\\d\\d):(\\d\\d):(\\d\\d),(\\d\\d\\d) "
                + "--> (\\d\\d):(\\d\\d):(\\d\\d),(\\d\\d\\d)");
        return p.matcher(str).matches();
    }

}

As I'm very new to regex, I'm wondering if this is the most efficient/correct way to accomplish this.

Rather than using \d, you might want to limit the matcher to valid ranges.

\d{2}:([0-5]\d:){2},\d{3}

would match either of the timestamps and it would prevent someone from entering

11:88:88,888 --> 12:99:99,999


Implementing multiple Producer Consumer using custom Blocking queue I am trying to implement multiple producer multiple consumer problem using a custom blocking queue. The requirement is that:

If the queue is not full, all the producers should be able to produce products independently.
If the queue is full, the producers have to wait.
If the queue is not empty, the consumer can consume products independently.
If the queue is empty, the consumers have to wait.

Here is the code I have implemented. Could you please review my code and let me know if there is any flaw?

Custom Blocking Queue

public class CustomQueue<T> {

private static final Object LOCK = new Object();
private int queueSize = 100; // default size
private List<T> queue;

public CustomQueue(int size){
    this.queueSize = size;
    this.queue = new LinkedList<>();
}

public void produce(T t){
    if(queue.size()==queueSize){ // queue is full. Producer need to wait
        synchronized(LOCK){
            while(queue.size()==queueSize){
                try {
                    LOCK.wait();
                } catch (InterruptedException e) {
                    System.out.println("Exception in produce() while waiting. Reason: "+e.getCause());
                }
            }
        }
    }else{ // queue is not full. Producer can produce items
        queue.add(t);
        LOCK.notifyAll();
    }
}

public T consume(){
    if(queue.size()==0){
        while(queue.size()==0){// queue is empty. Consumer need to wait
            try {
                LOCK.wait();
            } catch (InterruptedException e) {
                System.out.println("Exception in consume() while waiting. Reason: "+e.getCause());
            }
        }
    }else{ // queue is not empty. Consumers can consume item
        T t = queue.get(0);
        return t;
    }
    return null;
}

Producer code

public class Producer<T> implements Runnable{

private CustomQueue<T> sharedQueue;

public Producer(CustomQueue<T> sharedQueue){
    this.sharedQueue = sharedQueue;
}

@Override
public void run() {
    produceItems();
}

private void produceItems() {
    List<T> items = getItems();
    for(T t: items){
        sharedQueue.produce(t);
    }
}

private List<T> getItems() {
    //dummy method to get list of items
    return null;
}

Consumer code

public class Consumer<T> implements Runnable {

private CustomQueue<T> sharedQueue;

public Consumer(CustomQueue<T> sharedQueue){
    this.sharedQueue = sharedQueue;
}

@Override
public void run() {
    T t = consumeItem();
}

private T consumeItem() {
    T t = sharedQueue.consume();
    return t;
}

Your produce and consume methods are both buggy for the same reason: you've got a time of check/time of use bug.

Imagine a queue with size 1. Start two producer threads at the same time. They'll both see queue.size() == 0 in produce() and they'll both happily proceed to queue.add() without a lock, overflowing your queue (and causing other problems if that add() method isn't thread-safe itself).

Same thing exactly on the consumer side. If there's one item in the queue and two threads enter consume() at the same time, both will try to extract an item and at least one will fail.

You need to hold a lock that covers the check and the produce/consume actions.

You can't call notifyAll() on an object unless you own the object's monitor. You'll get a IllegalMonitorStateException if you try to run your code.


ToDo App in AngularJS I have written a todo list app. I want to understand how to improve it.

Here's what I'm trying to understand:

My problem is when user clicks on task to edit, because it passed by reference, so if user edit task, it will change directly the task object.
(see the code below).

My questions:

In my code I wrote one way to fix the above mentioned problem by cloning the object every time.
Is it a good practice ? If no, how do you recommend me to fix it?
I do not want my code to just work, I want it be efficient and improve my skills.
Can you please suggest any areas of improvement to the code?

Link to plunker: https://plnkr.co/edit/CA99iiydbD4TWaGtJZZf?p=preview

(function() {
    var Task = (function() {
        var counter = 0;
        return function(content, isDone) {
            this.id = counter++;
            this.content = content;
            this.isDone = isDone || false;
        }
    }());
    var app = angular.module('todos',[])
    .service('todosBL', function() {
        this.tasks = [];
        this.add = function(content) {
            this.tasks.push(new Task(content));
        }

        this.update = function(editedTask) {
            var i = this.tasks.findIndex(function(task){
                return task.id === editedTask.id
            });
            this.tasks[i] = editedTask;
        }

    })
    .controller('main', function($scope, todosBL) {
        $scope.todosBL = todosBL;
        $scope.add = function(task) {
            todosBL.add(task);
            $scope.task = null;
        }
        $scope.editMode = {
            task: {},
            edit: function(task) {
                this.task = task;
                //BECAUSE I PASS TASK BY REFERNCE WHEN USER EDIT TASK IT CHANGE TASK DIRECTLY ,
                // IF I CLONE OBJECT EVERY TIME, IT FIX BY REFERENCE PROBLEM.
                // MY QUESTION IF HAVE OTHER WAY TO SLOVE THIS. MABY OTHER WAY TO THINK ABOUT APP LIKE THIS.
                // for(key in task) {
                //     this.task[key] = task[key];
                // }
            },
            save: function(task) {
                todosBL.update(task);
                this.task = {};
            }
        };
    });
}());

{{ task.content}}

        <input type="text" ng-model="task">
        <input type="button" value="add task" ng-click="add(task)">

            <input type="text" ng-model="editMode.task.content">
            <input type="button" value="save task" ng-click="editMode.save(editMode.task)">

Here are a few improvements I can think of.

HTML

As the name of the angular app - todos - is not particularly good. Most developers would follow a convention such as appending 'App' behind the name of the app so that other developers would know that they are looking at a module.

Ref: https://github.com/mgechev/angularjs-style-guide#naming-conventions

As with the name of the app, you could also rename the controller to mainController.

A problem with the list is that use cannot intutively tell that they can click on a task to edit it. You can fix that easily by wrapping an  tag around it.

{{ task.content}}

Just fixing the case of characters in the button.

        <input type="text" ng-model="task">
        <input type="button" value="Add Task" ng-click="add(task)">

Here instead of saying "Save Task" it would be better to change it to "Update Task" as it would more clearly convey the purpose of the button.

            <input type="text" ng-model="editMode.task.content">
            <input type="button" value="Update Task" ng-click="editMode.save(editMode.task)">

Javascript:

(function() {
    var Task = (function() {

You could rename the counter variable to better convey its meaning. Maybe even rename the content variable to taskTitle. One more thing, return function(...){...} is a Javascript statement, and although Javascript would not enforce it, you should always append a semicolon ; at the end.

        var taskIdCounter = 0;
        return function(content, isDone) {
            this.id = taskIdCounter++;
            this.content = content;
            this.isDone = isDone || false;
        }; // <-- Semicolon!
    }());
    var app = angular.module('todos',[])
    .service('todosBL', function() {
        this.tasks = [];
        this.add = function(content) {
            this.tasks.push(new Task(content));
        };

In the controller below, I will make use of the editedTaskId to update the task object from clone.

        this.update = function(editedTask, editedTaskId) {
          var i = this.tasks.findIndex(function(task){
              return task.id === editedTaskId
          });
          this.tasks[i] = editedTask;
        }
    })

Your logic about cloning the task object to update it is fine. Here's how I'd do it if I had to implement it.

    .controller('main', function($scope, todosBL) {
        $scope.todosBL = todosBL;
        $scope.add = function(task) {
            todosBL.add(task);
            $scope.task = null;
        };
        $scope.editMode = {
            editingTaskId: '',
            task: {},
            edit: function(task) {
                this.task = new Task(task.content, task.isDone);
                this.editingTaskId = task.id;
            },
            save: function(task) {
                todosBL.update(task, this.editingTaskId);
                this.task = {};
            }
        };
    });
}());


Pointer version of itoa Rewrite appropiate programs from earlier chapters and exercises with pointers instead of array indexing. Good posibilities include getline(Chapter 1 and 4), atoi, itoa, and their variants(Chapters 2, 3, and 4), reverse(Chapter 3), and strindex and getop(Chapter 4)

Here is my solution:

static char *hidden(int n, char *s) {
    char *p;

    if(n / 10) {
        p = hidden(n / 10, s);
    }
    else {
        p = s;

    }
    *p++ = n % 10 + '0';
    *p = '\0';

    return p;
}

char *itoa(int n, char *s) {
    if(n < 0) {
        *s = '-';
        hidden(-n, s + 1);
    }
    else {
        hidden(n, s);
    }

    return s; /* pointer to first char of s*/
}

itoa is a wrapper for the function hidden. The function hidden returns a pointer to the next free slot in the array s. At the deepest level of recursion it returns a pointer to the first element (the else branch) of the array.

The standard version of itoa takes a parameter named base (which you have assumed is 10).

You probably don't need a second hidden function; this would do instead:

if (n < 0)
{
    *s++ = '-';
    n = -n;
}
// ... itoa implementation continues here ...

Recursing is clever; you could also probably do it with two loops instead (untested code ahead):

i = 1;
while ((i * 10) <= n)
    i *= 10;
for (; i != 0; i /= 10)
{
    int x = n / i;
    *p++ = (char)(x % 10 + '0');
    n -= (x * i);
}
assert(n == 0);


Insert into SQLite3 database I have a tsv file containing the mapping for two kinds of identifiers.

accession   accession.version   taxid   gi
V00184      V00184.1            44689   7184
V00185      V00185.1            44689   7186
V00187      V00187.1            44689   7190
X07806      X07806.1            7227    8179

Basically, I want to be able to get the taxid from an accession number. I though I could put this in a database with a PRIMARY KEY on the accession field.

This is what I did and It works but I have around 1.5billion lines and it takes a lot of time to do.

import sqlite3
import time

start = time.time()

connection = sqlite3.connect("test.sqlite")
cursor = connection.cursor()

cursor.execute("""
    CREATE TABLE IF NOT EXISTS map (
        accession TEXT PRIMARY KEY,
        accession_version TEXT,
        taxid TEXT, gi TEXT
    )""")

def read_large_file(f):
    """Generator for the file"""
    for l in f:
        yield l.strip().split()

with open("test_file.map", "r") as f:
    next(f)  # ignore header
    cursor.executemany("INSERT INTO map VALUES (?, ?, ?, ?)", read_large_file(f))

cursor.close()
connection.commit()
connection.close()

print(time.time() - start)

Do you have any tricks or ideas I could use to speed up the insert ? (I will do very basic SELECT on the data using the accession primary key)

First, some comments on your code:

An sqlite3 connection can be used as a context manager. This ensures that the statement is committed if it succeeds and rolled back in case of an exception. Unfortunately it does not also close the connection afterwards

with sqlite3.connect("test.sqlite") as connection, open("test_file.map") as f:
    connection.execute("""
        CREATE TABLE IF NOT EXISTS map (
            accession TEXT PRIMARY KEY,
            accession_version TEXT,
            taxid TEXT, gi TEXT
        )""")

    next(f)  # ignore header
    connection.executemany("INSERT INTO map VALUES (?, ?, ?, ?)", read_large_file(f))
connection.close()

You should separate your functions from the code calling it. The general layout for Python code is to first define your classes, then your functions and finally have a main block that is protected by a if __name__ == "__main__": guard to allow importing from the script without executing all the code.
open automatically opens a file in read-mode, if not specified otherwise.

That being said, if you have a billion lines, basically any approach is probably going to be slow. Here is an alternate approach using dask. It may or may not be faster, you will have to test it. The usage is very similar to pandas, except that the computations are only performed once committed to with the call to compute().

First, to install dask:

pip install dask[dataframe] --upgrade

Then for the actual usecase you mention, finding a specific gi in the table:

from dask import dataframe

df = dataframe.read_csv("test_file.map", sep="\t")
df[df.gi == 7184].compute()
#   accession accession.version  taxid    gi
# 0    V00184          V00184.1  44689  7184

In the call to dataframe.read_csv you can set it to read the file in blocks if needed, e.g. in 25MB chunks:

df = dataframe.read_csv("test_file.map", sep="\t", blocksize=25e6)


An argument checking library This is a ( single file ) library I wrote as an helper to check arguments validity.Here below a sample usage:

public class Demo
    {
        /// <summary>
        /// Classical not null verification
        /// </summary>
        /// <param name="arg1"></param>
        public void DoSomething(string arg1)
        {
            Contract.Expect(() => arg1).IsNotNull();
        }
        /// <summary>
        /// Asserting an argument greather than another
        /// </summary>
        /// <param name="min"></param>
        /// <param name="max"></param>
        public void DoSomething(int min,int max)
        {
            Contract.Expect(() => min)
                .IsLessThan(int.MaxValue)
                .Meet(a => a <= max);
        }
        /// <summary>
        /// Validate an integer argument in a certain range
        /// </summary>
        /// <param name="arg1"></param>
        public void DoSomething(int arg1)
        {
            Contract.Expect(() => arg1).IsGreatherThan(0)
                                       .IsLessThan(100);
                ;

        }
        /// <summary>
        /// Validate an array in length and asserts first element should be zero
        /// </summary>
        /// <param name="array"></param>
        public void DoSomething(int[] array)
        {
            Contract.Expect(() => array).Meet(a => a.Length > 0 && a.First() == 0);
        }

    }

Exception message are auto generated based on the argument names, so we don't need magic strings at all. What about it ? Improvement and suggestions? Entire code is hosted here.

EDIT
just to clarify the pourpose of the library: I'm trying to avoid code such as:

if (stringParameter == null)
    throw new ArgumentNullException("stringParameter");

in which we need to write a string to specify the parameter name. This is not refactory friendly, neither DRY since you write twice "stringParameter" instead of:

Contract.Expect(() => stringParameter).IsNotNull();

That is once, and refactor friendly ( at least in my opinion ;) ).

Felice, can you expand on what you are looking for?  Are you trying to infer constraints to be applied dynamically?  I looked at your link to the whole code base at bitbucket.

First of all, nice work.  Looks like you spent a good deal of time whipping that up.

On the surface, given your demo and not knowing what exactly your intended use case is, it appears 1) that you are trying to make constraints more visually fluent (which I appreciate) and 2) it seems "possibly" unneeded.

Once you further expand on your use case, I'm sure it will make more sense and I can revise my statements.  However, for now let me explain item #2.  1) You can add the fluency you require by refactoring your code base into helper methods.  2) I would not really recommend throwing exceptions from what I can see.  Given the code sample below (from your Contracts.cs) you are throwing an exception on something that should merely be a boolean check.  As such you are altering the behavior of what you normally come to expect out of a programming language.

public IContract<T> IsEqual<TT>(TT of) where TT : T,IEquatable<TT>
{
    TT actual = (TT)accessor();
    if (!actual.Equals(of))
    {
        throw new ArgumentOutOfRangeException(Name, "Must be equal to" + of.ToString());
    }
    return this;
}

3) I would recommend watching out for "re-inventing the language".  Sometimes it is hard to identify, but the general smell is that you try to recreate basic functionality in the toolset you already use, instead of just using what you have.  This can result in double/triple programming.  Let's use the demo example from above (focusing on the snippet I grabbed).  You have built several methods to provided the ".IsNotNull()" method for the Contract and are then encapsulating that (to make it more readable and fluent) into a method that just takes the parameter.

/// <summary>
/// Classical not null verification
/// </summary>
/// <param name="arg1"></param>
public void DoSomething(string arg1)
{
    Contract.Expect(() => arg1).IsNotNull();
}

instead of just:

if (arg1.IsNullOrEmpty())

or

if (arg1.IsNullOrWhiteSpace())

Which are already built into the .net framework.

I hope some/all of this helps.  If you would, please further explain your use case.  As for now, my recommendation would be to refactor your utility into static helper methods and not throw exceptions.  For the error message part, just create helper method(s) to get the error message needed.  So 1 method does the needed check and if it fails...and as a programmer you want to get the error message, you can choose to do that in a separate call.


String compression implementation in C I implemented basic string compression algorithm that uses the counts of repeated characters. For example: the string aabcccccaaa would become a2b1c5a3. What do you think about this, is there a better way to do this?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char* compressString(char* arr, int size);

int main() {

  char arr[] = "aabcccccaa";
  char *str;
  printf("Before compression: %s\n", arr);
  str = compressString(arr, strlen(arr));
  printf("After compression: %s\n", str);
  // free allocated memory
  free(str);
  return 0;
}

char* compressString(char* str, int len) {
  char last = str[0];
  char *buf = (char *)malloc(len * sizeof(char));
  int count = 1;
  int j = 0;

  for (int i = 1; i < len; i++) {
    if (last == str[i]) {
      count++;
    } else {
      buf[j++] = last;
      buf[j++] += count + '0';
      last = str[i];
      count = 1;
    }
  }
  buf[j++] = last;
  buf[j] += count + '0';
  buf[j] = '\0';
  return buf;
}

A couple problems

You don't allocate enough space for the return buffer.  You need to allocate 2*len + 1 bytes to handle the worst cast scenario.  The +1 is for the null terminating byte.

If the count goes above 9, you will output a non-digit character instead of a digit.  If the count goes above 256, the digit will wrap around back to '1' and your compression will have failed to encode the original string.


Maximum matching in graph I'm currently working on this problem for my own practice. It's a paintball problem where I should determine if everyone can get a unique target. The problem is as follows I get a number of pair like:

1 2
3 4
3 2
4 1

If I get 1 2 it means that 1 can see 2 and therefore 1 can target 2. It goes the other way around to so 2 can see 1 and therefore 2 can target 1.

My assignment is to determine if everyone can get an unique target. If so I should output the numbers in order so first numbers 1 target than who number 2 should target and so on.

My implementation goes as follows:

I read in the number of players and lines.
For each line I create an edge.
Then I create a bool array to keep track if a player has a target and another bool array to see if a player is a target.
Then use a recursive method to find out the path which all player gets a target.
I also have a graph class to keep track of all the edges.

I need advice on what I'm doing wrong or any tips on the implementation.

  class Graph{
      std::list<int> graph[1000];
   public:
     void addEdge(int from, int to){
        graph[from].push_back(to);
    }
    std::list<int> getEdges(int e){
      std::list<int> myList = graph[e];
      return myList;
}

};

int n;
bool res = false;
int cnt = 0;
void checkPlayers(Graph graph,bool hasTarget[],bool isTarget[],int i,std::string myRes){
std::list<int> list = graph.getEdges(i);

std::list<int>::const_iterator iterator;
for(iterator = list.begin(); iterator != list.end(); ++iterator){
     int currentplayer = (*iterator);

     if(hasTarget[i] == false && isTarget[currentplayer] == false && currentplayer <= n){
       hasTarget[i] = true;
       isTarget[currentplayer] = true;
       cnt++;
       myRes += std::to_string(currentplayer);
       checkPlayers(graph, hasTarget, isTarget,++i,myRes);
       hasTarget[i] = false;
       isTarget[currentplayer] = false;
       cnt--;
       //myRes.erase(myRes.begin()+ st)
     }
 }
    if(cnt == n && res == false ){
     res = true;
     std::cout << myRes << std::endl;
  }
}

     int main(){
     int m;
     int playerOne, playerTwo;
     Graph graph;
     for(std::cin >> n >> m; m; --m){
       std::cin >> playerOne >> playerTwo;
       graph.addEdge(playerOne,playerTwo);
       graph.addEdge(playerTwo,playerOne);
     }
     bool isTarget[1000] = {false};
     bool hasTarget[1000] = {false};
     checkPlayers(graph,hasTarget, isTarget,1,"");
  }

If you don't know the size of your array, don't estimate it

Your graph is an array of 1000 std::list<int>. Why ? If you don't know the size, just don't use a const expr to set it. Just use any dynamic table object available (vector, hashmap, etc...).
If you have only 3 edges, 997 cells of your graph will be wasted memory space, and if you have more than 1000 edges, errors will occur.

Avoid non-const global variables

n, res and cnt are declared as global. Avoid using non-const globals. Among many problems (like name conflicts or multi-threading), it greatly reduce the readability of your program, and thus it's more easy for you to make errors.

Try declaring variables in the most restrained scope as possible. In a struct for example, which is passed down to checkPlayers. Global variable are almost never required to do what you want, you can always use local variables.
Plus, you should prefix your globals' name with g_ so it is clear that they are globals.

On top of that, you only use these variables into checkPlayers() ! These really should be local variable to this function.

Don't call list.end() in the `for` loop head

In your for loop, each time list.end() is called and re-evaluated. Just declare a const iterator with this value  like that :

std::list<int>::const_iterator iterator;
std::list<int>::const_iterator iteratorEnd = list.end();
for(iterator = list.begin(); iterator != iteratorEnd ; ++iterator){
...
}

You also should consider using std::for_each or BOOST_FOREACH (I have a preference for the latest, as it is shorter than the former to implement).

use const reference to pass non-basic types

Passing objects by copy may be long (your graph contains a 1000 cells array !), so passing it by reference is way quicker. To ensure that the reference isn't modified though, make the reference const (const Graph & graph instead of Graph graph). The same goes for the std::string.

Create variables only where you need it

Besides the fact that the two arrays of bool could be move into a single array of struct containing the bools, four of the five arguments of checkPlayers are useless. Don't create them above is you don't need to, there's no use for that.

If you're doing this just in case you may need it later, well I think this is the wrong way to do it, because you may end up with tons of useless code difficult to maintain. Declare variables only when you need it, and if yo ulater may need to generalize, you'll do it then, not before.

main returns an int

Don't forget the return 0; at the end of your program. Error codes are important.


Passing parameters by reference Wouldn't it be better to always pass parameters by reference to avoid creating unnecessary copies?

#include <iostream>

void deliver(const std::string& message){
    std::cout << message;
}

void say(const std::string message){
    std::cout << message;
}

int main(){

    std::string message = "Hello World";

    deliver(message);
    /* VS */
    say(message);

    return 0;
}

If not, why not?

Because I'm really starting to think references and pointers are useless.

I've been coding in C++ for a year and a half and never even once had to use a reference or pointer.

I've made countless programs and just finished making my biggest one ever, a 5000 lines game, divided in 28 separate files without using any of them.

Generally, the "order" of what you want to pass by looks like this for user-defined classes (ignoring C++11, for the moment):

Pass by const&. This should be the default way of passing
parameters.
Pass by &. If you need to modify the parameter for whatever reason, then
you'll need to pass a reference or pointer to it. However, you should prefer references to pointers (explained below).
Pass by value. Unless you really need to make a copy of the value, there's not much reason to pass by value compared to passing by const&. However, if you're going to be making a copy of the parameter in the function body either way, then you may want to simply pass by value in the first place.

For a good example of when explicit pass by value makes sense, see the copy-and-swap idiom.

However, this is "muddied" by a number of considerations:

Is the class small? Does it only encapsulate a few (simple) data members? For example, something like a std::pair. In this case, it may actually be better to just pass by value.
For fundamental data types (int, char, double, and so on), it's better to simply pass by value. There's no performance benefit to passing by reference, and in fact, it can often be slower.

With move semantics in C++11, this advice changes considerably. We now have an extra possibility: pass by rvalue reference (&&). Passing by value and using std::move then becomes a distinct possibility, especially when we want to be explicit about ownership. You may want to read this Stackoverflow post for a bit more information. Dave Abrahms (one of the principle authors of boost) has also written about this topic.

I haven't mentioned pointers at all until now. Really, the only difference between references and pointers is that references cannot be null. Sticking to references means that you eliminate a whole host of possible bugs to do with dereferencing null pointers. In modern C++, passing by pointer is rare. In fact, it should always be wrapped up in a stack allocated class that deals with the ownership semantics and eliminates the possibility of resource leaks (say, unique_ptr or shared_ptr). These are then passed by one of the ways mentioned above.

Finally, one must use pass by reference or (smart) pointer when using dynamic dispatch - that is, when dealing with inheritance.

This post may be far more than you ever wanted to know, but the answer is effectively "it depends". Deciding how to pass a parameter requires some actual thought, but boils down to some (subset) of the following considerations:

Is it a primitive data type or a class encapsulating only a few primitive datatypes?
Does it encapsulate some resource? If so, after the call, who do I want to own the resource?
Do I need to modify it in the function I'm passing it to? If so, can I rewrite the function in some way so that I don't have to, as this often makes it more difficult to understand the program.
Is inheritance involved? Do I want to be able to pass a derived class where a base class parameter is involved?
Am I going to simply make a copy of the parameter in the function body? If so, perhaps passing by value is the best idea (again, see the copy and swap idiom).
Should I provide overloads so I can have the option of passing a const reference vs passing an rvalue reference?
What will give me the best performance? What is easiest to reason about and maintain?

(Note: I realise this isn't really a code review as such. If this is too off topic, feel free to remove it).


jQuery Toggle Between Functions Fn1 Fn2 Fn3 On Click Is there a better way of toggling between different functions, on click events ? Something maybe that use "on" "off" methods or simpler alternative ?

(function($) {
        $.fn.clickToggle = function(func1, func2, func3) {
            var funcs = [func1, func2, func3];
            this.data('toggleclicked', 0);
            this.click(function() {
                var data = $(this).data();
                var tc = data.toggleclicked;
                $.proxy(funcs[tc], this)();
                data.toggleclicked = (tc + 1) % 3;
            });
            return this;
        };
    }(jQuery));

    $('#b1').clickToggle(
        function() {alert('First handler');},
        function() {alert('Second handler');},
        function() {alert('Third handler');}
        );

Your general approach seems sound. But you shouldn't hard-code the number of handlers. Take the functions as a rest-arg, and use funcs.length in the modulo expression.

You can also use the argument to .data() to look up the named data element, rather than getting the whole data object.

$.fn.clickToggle = function(...funcs) {
    this.data('toggleclicked', 0);
    this.click(function() {
        var tc = $(this).data("toggleclicked");
        $.proxy(funcs[tc], this)();
        data.toggleclicked = (tc + 1) % funcs.length;
    });
    return this;
};

You might also want to special-case a single function and just bind it the normal way, and completely ignore the call if there are no functions.

$.fn.clickToggle = function(...funcs) {
    switch (funcs.length) {
    case 0:
        break;
    case 1:
        this.click(funcs[0]);
        break;
    default:
        this.data('toggleclicked', 0);
        this.click(function() {
            var tc = $(this).data("toggleclicked");
            $.proxy(funcs[tc], this)();
            $(this).data("toggleclicked", (tc + 1) % funcs.length);
        });
    }
    return this;
};


"Remember me" automatic login I've implemented a "remember me" automatic login if no session has been set, but a remember me cookie is on their computer. I'm concerned about security and I'm not the best. I'm relatively new to OOP (just started a learning a week ago).

$database = new db;

if (isset($_SESSION['info'])){
  $token = $_SESSION['info']['token'];
  $loggedIn = 1;
} else {
  $loggedIn = 0;
  if (isset($_COOKIE["rememberMe"])){
    $rememberId = $_COOKIE["rememberMe"][0];
    $rememberKey = $_COOKIE["rememberMe"][1];
    if ($database->rememberMe($rememberId,$rememberKey) === "verified") {
      $loggedIn = 1;
    }
  }
}

$loggedIn is for use in JavaScript.

rememberMe function in the db class:

  public function rememberMe ($userId,$rememberKey) {

    $conn = $this->connect();
    $stmt = $conn->prepare(
    "SELECT COUNT(*) as count
     FROM sessions
     WHERE remember_key = :remember_key AND user_id = :user_id"
    );
    $stmt->bindParam(":remember_key",$rememberKey);
    $stmt->bindParam(":user_id",$userId);
    $stmt->execute();
    $remember = $stmt->fetchAll();
    $rememberVerify = $remember[0]["count"];

    if ($rememberVerify > 0) {

      $stmt = $conn->prepare(
      "SELECT id,username,display_name,avatar FROM users WHERE id = :user_id"
      );
      $stmt->bindParam(":user_id",$userId,PDO::PARAM_INT);
      $stmt->execute();
      $userInfo = $stmt->fetchAll();

      $dbId = $userInfo[0]["id"];
      $dbUsername = $userInfo[0]["username"];
      $dbDisplayName = $userInfo[0]["display_name"];
      $dbAvatar = $userInfo[0]["avatar"];
      $token = hash('sha256',openssl_random_pseudo_bytes(50));

      $_SESSION['info'] = [
        'id'=>$dbId,
        'username'=>$dbUsername,
        'display_name'=>$dbDisplayName,
        'avatar'=>$dbAvatar,
        'token'=>$token
      ];
      return "verified";
    }
  }

When the user signs in with "remember me" checked:

  if ($_POST['remember'] === "true"){
    $rememberKey = hash('sha256',openssl_random_pseudo_bytes(50));
    $stmt = $db->prepare("INSERT INTO sessions (user_id,remember_key) VALUES (:user_id,:remember_key)");
    $stmt->bindParam(":user_id",$dbId);
    $stmt->bindParam(":remember_key",$rememberKey);
    $stmt->execute();
    setcookie ('rememberMe[0]', $dbId, time() + (86400 * 365), "/");
    setcookie ('rememberMe[1]', $rememberKey, time() + (86400 * 365), "/");
  }

Security

  I'm concerned about security and I'm not the best.

You use prepared statements, secure random numbers, and didn't make any other giant mistakes (from what I can tell), so that is already very good.

Still, there are two issues:

you definitely want to set these cookies as httpOnly (it may somewhat mitigate XSS attacks).
you definitely want to hash the token in the database (use proper hashing such as bcrypt). Otherwise, once your database is compromised, an attacker can login as anyone that has an active remember me token. [your sha256 doesn't count here, an attacker can still just pass the value in the db]

And two minor points:

do you need the token in the session? It doesn't seem so to me, so I wouldn't store it. It shouldn't happen, but session data may leak, eg on shared hosts, so if it's not necessary, I wouldn't store secret information in them.
the feasibility of remote timing attacks is still somewhat disputed, but it's not that far fetched. With your code, it's highly unlikely that anything may happen, but still, ideally, your code should be secure against it, and I'm pretty sure that your SELECT isn't. If you use bcrypt as suggested, you get a timing safe string compare for free. Otherwise, see eg here (it also links to some more information on proper remember me mechanisms).

Misc

rememberMe isn't named all that good. It's not a function used to remember me, but a function used to check if I am remembered. So isRemembered would be more fitting. Something like authenticateCookie or similar might also work.
two spaces indentation is not enough, it makes your code hard to read. Use at least 4 spaces. If that leads to too long lines, reduce your nesting.
you should share one connection across your code (for performance reasons).
your rememberMe function may do a bit too much. It verifies the validity of a remember me token, but it also loads user info and saves it in the session. I would probably separate the second task into its own function.


Speed up computation on lists of lists in R (scalability issues) My goal is to take a source list of vectors and apply a mapping to each vector. The mapping creates a list of lists. When the vector size in each list element is large (~20000), and the number of elements in the source list is large (~5000), my program does not seem to be efficient. How can I optimize my code?

I've tried two things: implementation in Rcpp and mclapply. The Rcpp implementation is comparable as expected, and the mclapply implementation may not be that efficient because I'm running my function in a larger function that is already parallelized over multiple cores.

Basic example

source.list = rep(list(seq(6)),3)
target.list = list(c(1,2),c(3,4),c(5,6))

result = map_partition(source.list,target.list)

> result
[[1]]
[[1]][[1]]
[1] 1 2

[[1]][[2]]
[1] 3 4

[[1]][[3]]
[1] 5 6

[[2]]
[[2]][[1]]
[1] 1 2

[[2]][[2]]
[1] 3 4

[[2]][[3]]
[1] 5 6

[[3]]
[[3]][[1]]
[1] 1 2

[[3]][[2]]
[1] 3 4

[[3]][[3]]
[1] 5 6

R implementation

map.partition.R <- function(invec, partitionlist) {
  lst <- lapply(partitionlist, function(x) invec[invec %in% x])
  return(lst)
}

result = lapply(X=source.list, FUN=map.partition,
                               partitionlist=target.list)

You have two lapply calls in there, so essentially two hidden for loops contributing to the slow execution.

Here, one way to tap into faster compiled functions is to rely on the data.table package for merging (a.k.a. a database join) your two data sets.

First, we turn your two lists into two data.tables:

idx1 <- rep(seq_along(source.list), lengths(source.list))
idx2 <- rep(seq_along(target.list), lengths(target.list))

library(data.table)
X <- data.table(id = unlist(source.list), idx1 = idx1,
                pos = seq_along(idx1), key = "id")
Y <- data.table(id = unlist(target.list), idx2 = idx2, key = "id")

where idx1 and idx2 are the variables telling us in which element of source.list and target.list a specific item (id) belongs. Also pos is just a temporary row number we will use later to sort the data back, as the next statement below (the merge) shuffles things around:

Z <- Y[X, allow.cartesian=TRUE]
Z <- Z[order(Z$pos)]

At this point, if it's possible for you, I would recommend you stop here. By that, I mean to make the next steps of your analysis use this Z data.table rather than a nested list, as to avoid further slow processing loops (for/lapply/Map/etc.). However, if you really need the nested list output, you can do:

no_name_split <- function(...) unname(split(...))
gp1 <- factor(Z$idx1, seq_along(source.list))
gp2 <- factor(Z$idx2, seq_along(target.list))

res <- Map(no_name_split, no_name_split(Z$id, gp1),
                          no_name_split(gp2,  gp1))

Below is a simulation with a larger dataset, comparing computation times and checking that the results are identical:

set.seed(632)
source.list <- replicate(500, sample(100000, 1000), simplify = FALSE)
target.list <- replicate(555, sample(100000, 1055), simplify = FALSE)

system.time({
  idx1 <- rep(seq_along(source.list), lengths(source.list))
  idx2 <- rep(seq_along(target.list), lengths(target.list))

  library(data.table)
  X <- data.table(id = unlist(source.list), idx1 = idx1,
                  pos = seq_along(idx1), key = "id")
  Y <- data.table(id = unlist(target.list), idx2 = idx2, key = "id")
  Z <- Y[X, allow.cartesian = TRUE]
  Z <- Z[order(Z$pos)]

  no_name_split <- function(...) unname(split(...))
  gp1 <- factor(Z$idx1, seq_along(source.list))
  gp2 <- factor(Z$idx2, seq_along(target.list))
  res <- Map(no_name_split, no_name_split(Z$id, gp1),
                            no_name_split(gp2,  gp1))
})
#    user  system elapsed
#   3.394   0.382   3.646

system.time({
  result <- lapply(X = source.list, FUN = map.partition.R,
                   partitionlist = target.list)
})
#    user  system elapsed
#  23.943   5.329  36.999

identical(res, result)
# [1] TRUE


Changing array values in PHP I need to change some array values in a 2-dimensional array for some cases. Sometimes the all values from an child array and sometimes only some values.
In this cases I should only change the variable $stamm which $stamm2.

This code is the statement of an if condition, where all relevant verbs for this changings  is mentioned.

$verb could be one over 25.000 french verbs. For this example you could use 'acheter'.

  $array = array(
  array('e', 'es', 'e', 'ons', 'ez', 'ent'), array('ais', 'ais', 'ait', 'ions', 'iez', 'aient'), array('ai', 'as', 'a', 'âmes', 'âtes', 'èrent'), array('erai', 'eras', 'era', 'erons', 'erez', 'eront'), array('e', 'es', 'e', 'ions', 'iez', 'ent'), array('asse', 'asses', 'ât', 'assions', 'assiez', 'assent'), array('erais', 'erais', 'erait', 'erions', 'eriez', 'eraient'), array('e', 'ons', 'ez'), array('XXX'), array('ant'));

My short old code:

$stamm = substr("$verb", 0, - 2);
$stamm2 = substr_replace($stamm, 'è', -2, 1);

$array[0][0] = $array[0][2] = $array[4][0] = $array[4][2] = $array[7][0] = $stamm2.'e';
$array[0][1] = $array[4][1] = $stamm2.'es';
$array[0][5] = $array[4][5] = $stamm2.'ent';

My new improved code:

$stamm = substr("$verb", 0, - 2);
$stamm2 = substr_replace($stamm, 'è', -2, 1);

$zeiten = array(0, 3, 4, 6, 7);
foreach($zeiten as $zeit) {
    foreach($array[$zeit] as $person => $value) {
        if ((($zeit == 0  || $zeit == 4) && !in_array($person,array(3,4))) || ($zeit == 3 || $zeit == 6) || ($zeit == 7 && $person==0))
        $array[$zeit][$person] = str_replace($stamm, $stamm2, $value);
        }
    }

Is this the the new code the best solution? Is it possible to improve the if condition?

Let me first review this from an readability point of view, then answer your question and an proposed solution.

Naming

Your variable names could be more descriptive.

$array -> (maybe) $conjugations (german: $konjugationen)
$stamm -> $word_stem (german: $wort_stamm)
$zeiten -> $tenses (german: $zeitformen)?

Structure

The most intriguing part for me is $array's structure.
As I understand it, it is a 2D table of conjugations of the $verb where rows have the same tense and columns the same person. This should be somehow reflected in the data structure because it is not obvious to the viewer.
Maybe you should even implement a class for that.

Comparison

Maybe it has to do with my lack of domain knowledge (I don't speak french) but I find both solutions unreadable.
This is enforced by the naming problems.

The second one looks slightly more general with regard to reuse but the if portion is not very flexible.

Improvement

As I said, I have no idea about french but I suppose this holds true:

Each verb can be conjugated for person and tense. There is a set of rules that defines how this happens for each person and tense depending on the verb's form and a set of exemptions from those rules.

The solution to the problem consists of:

Classifying the verb as to which rule/exemption to apply
applying the rule

To me this sounds like 1. could be solved by a factory that creates strategy instances for 2.

$conjugator = get_conjugator($verb, $tense, $person);
$conjugated_verb = $conjugator->conjugate($verb);

Maybe the exceptions/rules are even partial per tense or person. This would mean you would have to make this distinction as well and produce a separate conjugator for each tense, person, verb triple.

Now the code you have posted is pretty much the part that goes into the implementation of a conjugator. And seeing that there could be many of them it would be nice to make implementing them as simple as possible.

Their interface would probably consist of a function that detects whether they are applicable (the if condition in your case) and a function that does the actual flexion of the input (the if's then code block).


Distinct unordered pairs of an array which satisfy a condition I came across the below problem in a coding challenge:
Let's define 2 functions, \$F(i)\$ and \$Val(i,j)\$, for an array \$A\$ of size \$N\$ as follows:

$$
\begin{align}
F(i) =& \sum_{j=i+1}^{N} Val(i,j) \\
\\
Val(i, j) =& \begin{cases}
               1,\qquad & \textrm{if } A[i] < A[j] \\
               0,\qquad & \textrm{otherwise}
             \end{cases}
\end{align}
$$
I need to find the number of distinct unordered pairs of elements (a,b) in array \$A\$, such that \$F(a)+F(b) \ge K\$.

Here is my solution:

#include<iostream>
#include<cassert>
#define max 1000000000

int main()
{
    unsigned int N, K;
    std::cin >> N;
    assert((1 <= N) && (N <= 1000000));
    std::cin >> K;
    assert((0 <= K) && (K <= max));
    unsigned int a[N], F[N];
    for(unsigned int i = 0; i < N; i++)
    {
        std::cin >> a[i];
        assert((1 <= a[i]) && (a[i] <= max));
    }
    int sum = 0, val = 0;
    for(unsigned int i = 0; i < N; i++)
    {
        for(unsigned int j = i+1; j < N; j++)
        {
            if(a[i] < a[j])
            val = 1;
            else
            val = 0;

            sum = sum + val;
        }
        F[i] = sum;
        sum = 0;
    }
    int count = 0;
    for(unsigned int i = 0; i < N; i++)
    {
        for(unsigned int j = i+1; j < N; j++)
        {
            if(F[i] + F[j] >= K)
            count++;
        }
    }
    std::cout << count << std::endl;
}

While this works, I would want to know if there is a way to write optimized code which works fast even for larger inputs.

Scope

    int sum = 0, val = 0;
    for(unsigned int i = 0; i < N; i++)
    {
        for(unsigned int j = i+1; j < N; j++)
        {
            if(a[i] < a[j])
            val = 1;
            else
            val = 0;

            sum = sum + val;
        }
        F[i] = sum;
        sum = 0;
    }

This won't affect speed, but this would be more simply written

    for (unsigned int i = 0; i < N; i++)
    {
        int sum = 0;
        for (unsigned int j = i+1; j < N; j++)
        {
            int val = 0;
            if (a[i] < a[j])
            val = 1;
            else
            val = 0;

            sum += val;
        }
        F[i] = sum;
    }

Now we only declare variables in the scope in which they are used.

Don't create unnecessary variables

But we can actually do even better

    for (unsigned int i = 0; i < N; i++)
    {
        F[i] = 0;
        for (unsigned int j = i+1; j < N; j++)
        {
            if (a[i] < a[j])
            {
                F[i]++;
            }
        }
    }

We don't actually need val or sum at all.

There is the slight possibility that constantly calculating the memory location of F[i] would add time, but I would expect any decent compiler to only set it once.  The rest of the time it will work with a register.

This also saves some time in that it only adds if we're incrementing by 1.  If not, this does nothing.  That has the same effect as adding 0 but with fewer instructions.  Of course, your compiler may have already optimized that out.

Many recommend always using the block form of control structures, even when there's only a single statement.

Don't forget what you know

In this case, you are working with segments going from a point in the array to the end.  But you are looping from the beginning to the end.  What happens when you loop from the end to the beginning?

    for (int i = N - 1; i >= 0; i--)
    {
        F[i] = 0;
        for (unsigned int j = N - 1; j > i; j--)
        {
            if (a[i] == a[j])
            {
                F[i] += F[j];
                break;
            }
            else if (a[i] < a[j])
            {
                F[i]++;
            }
        }
    }

Now when we encounter two equal array entries we can stop looping.

    int count = 0;
    for(unsigned int i = 0; i < N; i++)
    {
        for(unsigned int j = i+1; j < N; j++)
        {
            if(F[i] + F[j] >= K)
            count++;
        }
    }

Same kind of insight here.

    int n = N - K / 2;
    unsigned int count = 0;
    for (unsigned int i = 0; i < n; i++)
    {
        int remainder = K - F[i];
        if (remainder <= 0)
        {
            // if F[i] >= K, every remaining entry will work
            count += N - i - 1;
            continue;
        }

        for (unsigned int j = N - remainder; j > i; j--)
        {
            if (F[j] >= remainder)
            {
                count++;
            }
        }
    }

By precalculating the remainder, we save some math in the inner loop.  And we can save some iterations of the inner loop (if remainder is too high, there is no way to add up to it at the end of the loop).  But more importantly, we can check remainder against 0.  Because if the remainder is less than or equal to zero, we can immediately say that every remaining entry will work.