Solving a 7x7 maze puzzle i came across this fun puzzle while being on vacation.

It was designed by Robert Abbott and painted into the grass of a Wisconsin farm. Robert succeeded into making it seem really easy to solve. Well, it is not. I spent hours with my friends wandering the puzzle and left frustrated.

I decided to solve it using computers. chose javascript because it made it easy to visualize the process and solution.

Initially i started with a brute force algorithm, which run for hours and got me nowhere. Than i shifted to this final one (below). I just kinda came up with this recursive solution that explores all paths, and terminates any path that comes across a previously visited node, so the one that makes it to the end should be the shortest one in (my) theory. I am wondering if this is a known algorithm (and how i botched it), and if there is a better way to achieve this. Also this algo appears to find the answer in 28 steps (including entry step).. A friend of mine solved this using an algo that works its way back from the end which supposedly solved it in 20 steps.

anyways, the working solution can be seen here.

here is the recursive function:

_delay = 50;
_successfulSteps = null;
function findRecursive(params){
    var cell = params[0];
    var steps = params[1];
    var history = params[2];
    var x = getX(cell);
    var y = getY(cell);
    var steps = getCellSteps(cell);
    markCellActive(x,y);

    var h = [];
    for (var i = 0; i<history.length; i++) {
        h.push(history[i]);
    };
    h.push([getX(cell),getY(cell)]);

    if (steps == 0) {
        var sp = $('#solutionSpan')[0];
        sp.innerHTML = 'solved in ' + h.length + ' steps';
        return;
    }

    for (var i = history.length - 1; i >= 0; i--) {
        if (x == history[i][0] && y == history[i][1]) {
            // this cell already processed
            console.log('terminating recursion for: ' + y + ':' + x);
            return;
        }
    };

    var rightCell = getRightCell(x,y, steps);
    var leftCell = getLeftCell(x,y, steps);
    var upCell = getUpCell(x,y, steps);
    var downCell = getDownCell(x,y, steps);

            // add delay to visualize the process
    if (rightCell){
        setTimeout(findRecursive, _delay, [rightCell, steps, h]);
    }
    if (leftCell){
        setTimeout(findRecursive, _delay, [leftCell, steps, h]);
    }
    if (upCell){
        setTimeout(findRecursive, _delay, [upCell, steps, h]);
    }
    if (downCell){
        setTimeout(findRecursive, _delay, [downCell, steps, h]);
    }

}

(i should note that this is not the prettiest code and i'm not looking for a way to reduce # of lines or anything, just to find a better algorithm)

You're finding all solutions, but because the code overwrites the <span> for every solution found you only see the last one. Try this:

sp.innerHTML += 'solved in ' + h.length + ' steps<br/>';

You're performing a breadth-first search of all possible paths through the maze which is what I ended up going with. By scheduling timer events you're essentially queueing up cells. I did the same but with an actual queue of cells to visit.

This is the core of my Scala version.

// pathTo tracks the best path to each point
// moves(Point) returns the number in that cell

val queue = new Queue[Point]
queue enqueue new Point(0, 0)  // start from top-left
while (!queue.isEmpty) {
    val start = queue dequeue
    val path = pathTo(start)
    (UP, DOWN, LEFT, RIGHT) foreach { direction =>
        val end = start.move(direction, moves(start))
        if (end != None && !pathTo.contains(end)) {
            pathTo(end) = path + end
            queue enqueue end
        }
    }
}


Angular2 Toggling showing and hiding between two elements I have a tabs nav element that has two tabs, it needs to show a component based on what tab was clicked and hide the other component.  If the clicked tab is already "active", the component needs to remain showing.

I have this working, but it seems very inefficient to me.  Can anyone show me a better way to do this?

Here's how I have it set up now.  For the sake of not posting every file in the question, know that the project is set up correctly.

@Component({
  selector: 'my-app',
  template: `

      <button type="button" (click)="changeShowStatus(oneShowing=true,twoShowing=false)">1</button>
      <button type="button" (click)="changeShowStatus(twoShowing=true,oneShowing=false)">2</button>

some content

some content2

  `,
})
export class App {
  name:string;
  oneShowing:boolean;
  twoShowing:boolean

  constructor() {
    this.oneShowing = true;
    this.twoShowing = false
  }
}

Plunker

Separate content and logic

It is a good practice (recommended by Angular style guidelines) to separate component template and component code.

Move template to an own my-app.component.html file and refer to it via templateUrl property instead of template.

Avoid logic in your template

oneShowing=true,twoShowing=false in and twoShowing=true,oneShowing=false parts are technically logic.
It does need to be in the template, and it should not be there.

my-app.component.html

<button type="button" (click)="displayBoxWithNumber(1)">1</button>
<button type="button" (click)="displayBoxWithNumber(2)">2</button>

my-app.component.ts

displayBoxWithNumber(boxToShow: number): void {
  this.hideAllBoxes();
  this.displayBox(boxToShow);
}
private hideAllBoxes(): void {
  this.oneShowing = false;
  this.twoShowing = false;
}
private displayBox(boxToShow: number): void {
  if (boxToShow === 1)
    this.oneShowing = true;
  else if (boxToShow === 2)
    this.twoShowing = true;
  else
    throw new Error(`Invalid box number provided ${boxToShow}`);
}

Please notice that the code above is for illustrational purposes in your specific context.
Any more or less real project will use *ngFor directive to iterate over some data source to construct the boxes dynamically.
Something like the code below.
Do not worry if you don't understand it yet.
You'll get there later with a bit of practice.

<div *ngFor="let box of boxeList; boxIndex = index; trackBy: trackByBoxId">
  <button type="button" (click)="displayBox(box, boxIndex)"> {{ box.number }} </button>
  <div class="box" *ngIf="isBoxActive(box)">
    <simple-box-view [value]="box"></simple-box-view>
  </div>
</div>

Know your tool/language

In typeScript you can initialize class' properties inline (this is the same as setting the values in constructor).
You can also omit the type of the variable it is inferred.
Similarly, if your constructor does not do any work, it can be got rid of.

export class App {
  name: string;
  oneShowing = true;
  twoShowing = false;

  // Methods...
}


Adjacency list Graph representation Following is the graph I used to create adj list.

The code should follow all the best practices of C++ 14 and stl.

map is used instead of vector to keep label.

Any suggestions for better implementation are welcome.
.h

#pragma once

#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>
#include <algorithm>

using std::unordered_map;
using std::list;
using std::pair;
using std::cout;
using std::endl;
using std::make_pair;
using std::for_each;

class AdjList
{
private:

    typedef pair<int, char> edge;
    unordered_map<char , list <edge> > adjList;

public:
    void createGraph();
    void printGraph();
    void test();
};

.cpp

#include "AdjList.h"

void AdjList::createGraph()
{
    list<edge> A;
    A.push_back(make_pair(3, 'B'));
    A.push_back(make_pair(2, 'E'));

    list<edge> B; //B points nowhere

    list<edge> C;
    C.push_back(make_pair(1, 'A'));

    list<edge> D;
    D.push_back(make_pair(4, 'C'));

    list<edge> E;
    E.push_back(make_pair(4, 'D'));

    adjList['A'] = A;
    adjList['B'] = B;
    adjList['C'] = C;
    adjList['D'] = D;
    adjList['E'] = E;

}

void AdjList::printGraph()
{
    for each (auto elem in adjList)
    {
        cout << elem.first << " -> ";

        for_each(elem.second.begin(), elem.second.end(), [](auto val) {

            cout << val.second << "(" << val.first << "), ";

        });

        cout << endl;
    }
}

void AdjList::test()
{
    createGraph();
    printGraph();
}

test() is called from main to test.

Output:

  A -> B(3), E(2),

  B ->

  C -> A(1),

  D -> C(4),

  E -> D(4),

Good work!
Do not polute the global namespace in headers
using std::unordered_map;
...

Anyone who #includes your file will have these imported in their global namespace. You should should migrate these to your .cpp file, and just use std:: for the two instances in the header.
list<> vs vector<>
There is nothing in your code that suggests list<> is preferable to vector<>. Unless you need fast insertion/removal in the middle of the structure, vector<> is preferable here.
For each ( in ) is not a thing
for each (auto elem in adjList) is not standard C++, but a MSVC extension, use range-based for instead. Furthermore, by using auto instead of auto &, you are working on copies of the adjacency list, not references.
You want this:
for(auto const& elem : adjList) {

Don't use for_each when a range-based for works.
for_each is not best practice unless you are already manipulating a predicate. range-based-for is preferable:
Like so:
for(auto const& val : elem.second) {
    cout << val.second << "(" << val.first << "), ";
}

Emplace into containers
You want to use emplace_back() instead of push_back() in containers where possible:
Like So:
list<edge> C;
C.push_back(make_pair(1, 'A')); // bad
C.emplace_back(1, 'A'); // much better

Move containers if you know you are done with them.
When you do this:
adjList['A'] = A;

You create a copy of A, when you know you are done with it. You should promote A to a RValue:
adjList['A'] = std::move(A);

You are mixing your functionality with your test harness
createGraph(); and test(); have no business being members of this class, and should be free-floating functions.
Once you do this, you will realize that there is a lot of stuff missing from your class as it does not expose the interface required to implement these simple cases.


Python simple type checking decorator I'd like to know your opinions on this minimal type-checking decorator  (with @ annotations) to make type checking of a method while debugging like :

def typecheck(*tuples, **kwtuples):
    def decorator(func):
        def function_wrapper(*args, **kwargs):

            #print('tuples : ' , tuples)
            #print('kwtuples : ' , kwtuples)
            #print('args : ' , args)
            #print('kwargs : ' , kwargs)

            for index, tup in enumerate(tuples):
                arg = args[index]
                if not isinstance(arg, tup):
                    raise ValueError('in ' + str(func.__name__) + ' : wrong argument on position ,' + str(index) + ' :'  + str(arg) + ' must be of type :' + str(tup) + 'but is' + str(type(arg)) )

            for key, tup in kwtuples.items():
                arg = kwargs[key]
                if not isinstance(args[index], tup):
                    raise ValueError('in ' + str(func.__name__) + ' : wrong argument ' + str(key) + ' :'  + str(arg) + ' must be of type :' + str(tup) + 'but is' + str(type(arg)) )

        #print("arguments: ", *args, **kwargs)
            func(*args, **kwargs)
        return function_wrapper
    return decorator

@typecheck(str,(str, float))
def foo2(x,y):
    print("Hi, foo has been called with ",str(x) ,y)

foo2('2',3.4)

The benefit of it is :

Custom and detailed description about the wrong argument
Later, you can extend this for custom validation like some item is in some range or structural inspection of an argument.
Easy to write, apply and delete after testing (so it won't consume cpu time)

To amplify @200_success’s comment:

Python 3.5 introduces type hints.  Eg)

>>> def foo2(x:str, y:float) -> None:
...    print(f"Hi, foo has been called with {x} {y}")
...
>>> foo2("2", 3.4)
Hi, foo has been called with 2 3.4
>>>

These type hints (the x:str, and y:float) are not used by the standard Python interpreter, but they are recorded during the parsing of the code, so they are available to the program.

>>> foo2.__annotations__
{'return': None, 'x': <class 'str'>, 'y': <class 'float'>}
>>>

Directly accessing the foo2.__annotations__ is not that interesting, but accessing func.__annotations__ in the @typecheck decorator means you don’t have to provide the argument types to the decorator; the decorator can inspect the argument types directly.  Thus you could decorate the function with simply @typecheck, instead of @typecheck(str, float).

For a variant str or float type argument, you could use the typing module to define your own STR_OR_FLOAT = TypeVar("STR_OR_FLOAT", str, float) type (or a better name if you have one), which you could decorate the argument with.

As a bonus, using type hints to provide argument type checking information — even for your do-it-yourself via a function decorator type check system — also gives you the following benefits:

IDE type hints, as you are writing code
Can be understood by standard documentation generators
Only consumes CPU time during parsing of the code; does not affect execution speed


Could this PHP Facebook class be any more OOP-ified? I have this Facebook class and I'm wondering if the OOP nature of it could be improved at all?

(GitHub project here):

<?php

class Facebook {

    private $baseUrl = 'https://graph.facebook.com/';

    public function basicInfo($username){

        if($username !== ''){
       $url = $this->baseUrl . $username;
      }
      if($url !== ''){
            $data = $this->__apiCall($url);
      }
      return $data;

    }

    public function userProfilePicture($username, $size = 'square'){

        if($username !== ''){
       $url = $this->baseUrl . $username . '/picture?type=' . $size;
      }
      return $url;

    }

    public function searchPublicPosts($query){

        if($query !== ''){
       $url = $this->baseUrl . 'search?q=' . urlencode($query) . '&type=post';
      }
      if($url !== ''){
            $data = $this->__apiCall($url);
      }
      return $data;

    }

    public function searchPages($page){

        if($page !== ''){
       $url = $this->baseUrl . 'search?q=' . urlencode($page) . '&type=page';
        }

        if($url !== ''){
       $data = $this->__apiCall($url);
      }
      return $data;

    }

    public function searchEvents($event){

        if($event !== ''){
       $url = $this->baseUrl . 'search?q='.urlencode($event).'&type=event';
      }
      if($url !== ''){
            $data = $this->__apiCall($url);
      }
      return $data;

    }

    private function __apiCall($url){

        $raw = file_get_contents($url);
        $json = json_decode($raw, true);
        return $json;

    }

}

This answer is in two sections.  Firstly I am going to cover the Object Oriented nature of your solution and suggest possible architectural changes.  Then I am going to look at your existing Code line by line for improvements.

Object Oriented

Your OO is good, you have nothing bad in there.

Here are some of the features of OO that you have used:

Data hiding (baseUrl property is private)
Encapsulation (use of private __apiCall to minimize interface for callers)

Lets have a look to see what other features you could use.

Now, what is your class?  It seems that it is a URL builder for the Facebook API.  You could think about creating a class that helps you with this URL building.  Let me pull one out of my hat now... (untested, only syntax checked)

class UrlBuilder {
   protected $baseUrl;
       protected $domain;
   protected $scheme;

   public function __construct($scheme, $domain, $baseUrl) {
        $this->baseUrl = $baseUrl;
        $this->domain  = $domain;
        $this->scheme  = $scheme;
   }

   /** Build a URL.
    *  @param rel   @string The relative offset from the baseUrl.
    *  @param query @array Associative array of query parameters.
    *  @return @string URL string.
    */
   public function buildUrl($rel, Array $query) {
       $url = $this->scheme . "://" . $this->domain . '/' . $this->baseUrl .
           $rel;

       if (!empty($query)) {
         $url .= '?' . http_build_query($query);
       }

       return $url;
   }
}

You will see from above that I use http_build_query (which is covered in the Code section of the review).

I left parameter checking out of this class to make this answer easier to read.  However you should definitely check each scalar parameter $scheme, $domain, $baseUrl, $rel.  Here is an example of how you would check $rel:

if (!is_string($rel)) {
    throw new InvalidArgumentException(__METHOD__ . 'rel must be a string');
}

So, how do we go about using this?  The common initial thought is the fantastic OO feature inheritance!  Raise your hand if you want to use inheritance.  Luckily from here I can't see any hands raised.  What would happen if we used inheritance (class Facebook extends UrlBuilder)?  We would open up the buildUrl method allowing any URL to be built with your Facebook object. This would be bad.  Why was inheritance a bad idea?  Because the Facebook object is not a UrlBuilder.  It is something that uses URL building.

The answer is composition.  We should pass the URL builder that we want to use into our constructor (generally I would use an interface, lets call it "UrlBuilderIface" and have class UrlBuilder implements UrlBuilderIface).  Using an interface allows us to keep the class loosely coupled.  We can accept any object that fulfills the contract defined by our UrlBuilderIface.  Here is the implementation with one method defined:

class Facebook {
    protected $urlBuilder;

    public function __construct(UrlBuilderIface $urlBuilder) {
            $this->urlBuilder = $urlBuilder;
    }

    public function searchPublicPosts($query) {
            if (empty($query) || !is_string($query)) {
            throw new InvalidArgumentException('query must be a non empty string.');
        }

        return $this->__apiCall($this->urlBuilder('search', array('q' => $query)));
    }

    private function __apiCall($url) {
            $raw = file_get_contents($url);
            return json_decode($raw, true);
    }
}

Note how there is checking for the passed in parameter to the method.  The check is simple, and it makes the rest of the code easy.  It is also easy to think about it completely separately from the other code (because you know that an exception will be thrown if the guard condition is met).

Usage becomes:

$facebookGraphUrlBuilder = new UrlBuilder('https', 'graph.facebook.com', '');
    $facebook = new Facebook($facebookGraphUrlBuilder);

Code

Some minor comments:

__apiCall should be named apiCall.  __ should be reserved for magic methods.
json_decode does not produce json, so you shouldn't create a variable from it called $json.
$json should never have even been a variable (A variable is for varying).  So you should return straight away, return json_decode($raw, true);

I am going to look at a single method because you have the same problems shared across your methods.

public function basicInfo($username){

        if($username !== ''){
                $url = $this->baseUrl . $username;
            }
            if($url !== ''){
            $data = $this->__apiCall($url);
            }
            return $data;

    }

Observe what would happen if $username was '':

First if does not match, so $url is not set.
Non-existent $url is used in second if causes E_NOTICE error.
Second if matches as NULL !== ''  (This is not good).
apiCall is made using NULL.
Badness continues.

Actually, similar or worse would happen if you used NULL an array, etc.

The bad thing here is the combination of your conditional setting of variables and later expectation that the variables have been set.  I would recommend solving this using a guard condition to ensure that the parameters to your methods are sane.  Trying to continue with the processing using if statements is quite difficult.  Throwing an exception may be the easiest:

if (!empty($username) || !is_string($username)) {
    throw new InvalidArgumentException('username required as a non-empty string.');
}

Everything can then be assumed to work:

return $this->__apiCall($this->baseUrl . $username);

Finally, there is a PHP function that helps you build the query strings that you use.  Here is the manual page for it: http_build_query


Two-dimensional array allocation in Go I am creating a two-dimensional array, which I am going to process later in ways similar to image MinFilter, procedural labyrinth generation, etc. -- implying using coordinates and neighbors.

Here are two ways I came up with now:

array := make([][]byte, 0, HEIGHT)
for i := 0; i < HEIGHT; i++ {
    array = append(array, bytes.Repeat([]byte{5}, WIDTH))
}

array := make([][]byte, HEIGHT)
for i := range array {
    array[i] = bytes.Repeat([]byte{5}, WIDTH)
}

They are both less straight-forward than the original Ruby code:

array = Array.new(HEIGHT){ Array.new(WIDTH){ 5 } }

But it is the first time I tried Go, so I ask you:

Which of these solutions is better?
And which is faster?
And why?

First, let's rewrite your code in idiomatic Go.

// For loop using a for clause
func NewRectangleF(height, width int, value byte) [][]byte {
    r := make([][]byte, 0, height)
    for i := 0; i < height; i++ {
        r = append(r, bytes.Repeat([]byte{value}, width))
    }
    return r
}

// For loop using a range clause
func NewRectangleR(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        r[i] = bytes.Repeat([]byte{value}, width)
    }
    return r
}

Then write and run some tests and benchmarks using Go 1.3.

$ go version
go version go1.3rc2 linux/amd64
$ go test -v -bench=.
=== RUN TestNewRectangle
--- PASS: TestNewRectangle (0.00 seconds)
PASS
BenchmarkNewRectangleFL5          50      38272524 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5          50      38195877 ns/op     6340608 B/op       2049 allocs/op

The benchmarks are for a large rectangle ((2 * 1024) by (3 * 1024)) with an initial value of 5.

Not surprisingly, the results are the same because we are doing the same thing. The range form is clearly better because it's easier to read and easier to verify that it's correct.

Are the results fast? Here's a simple alternative basic implementation.

// Benchmark basic
func NewRectangleB(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        w := make([]byte, width)
        if value != 0 {
            for j := range w {
                w[j] = value
            }
        }
        r[i] = w
    }
    return r
}

The benchmark results:

$ go test -v -bench=. -run=!
PASS
BenchmarkNewRectangleFL5          50      38272524 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5          50      38195877 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleBL5         500       5428041 ns/op     6340608 B/op       2049 allocs/op

The basic implementation looks faster; it uses about 86% less CPU time (5428041 ns/op vs. average 38234200.5 ns/op). It doesn't use the bytes.Repeat function. In Go 1.2 and Go 1.3 the bytesRepeat function looks slow.

// bytes.Repeat returns a new byte slice consisting of count copies of b.
func Repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    bp := 0
    for i := 0; i < count; i++ {
        bp += copy(nb[bp:], b)
    }
    return nb
}

Let's see if we can write an optimal version by improving the repeat function and reducing the large number of heap allocations (2049 allocs/op). Plus, since make sets the underlying array to the zero value for the type, we can make a zero initial value a special case.

func repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    if len(b) == 1 && b[0] == 0 {
        return nb
    }
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

// Benchmark optimization
func NewRectangleO(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    a := repeat([]byte{value}, height*width)
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

The benchmark results:

$ go test -v -bench=. -run=!
PASS
BenchmarkNewRectangleFL5          50      38272524 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5          50      38195877 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleBL5         500       5428041 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleOL5        2000       1468944 ns/op     6340608 B/op          2 allocs/op
BenchmarkNewRectangleOL0       50000         34646 ns/op       55296 B/op          2 allocs/op

The optimal implementation looks faster; it uses about 96% less CPU time (1468944 ns/op vs. average 38234200.5 ns/op) and about 99.9% less heap allocations (2 allocs/op vs. 2049 allocs/op). It's even faster for a zero initial value (34646 ns/op vs. average 38234200.5 ns/op).

We should also check that small rectangles (2 by 3  with an initial value of 5) are also reasonable.

$ go test -v -bench=.
PASS
BenchmarkNewRectangleOS5    10000000           233 ns/op          57 B/op          1 allocs/op
BenchmarkNewRectangleOS0    10000000           206 ns/op          57 B/op          1 allocs/op

Go performance is continually being improved. The version at tip, which will be released as Go 1.4, incorporates some of the optimizations in bytes.Repeat. Currently, it doesn't include the special-case optimization for a zero initial value.

// bytes.Repeat returns a new byte slice consisting of count copies of b.
func Repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

For Go 1.4 and later versions, we can at least write:

func NewRectangle14(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    var a []byte
    if value == 0 {
        a = make([]byte, height*width)
    } else {
        a = bytes.Repeat([]byte{value}, height*width)
    }
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

The results at tip for Go 1.4 are:

$ go version
go version devel +7d2e78c502ab Sat Jun 14 16:47:40 2014 +1000 linux/amd64
$ go test -v -bench=. -run=!
PASS
BenchmarkNewRectangleFL5        1000       2061854 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleRL5        1000       2054323 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleBL5         500       5276701 ns/op     6340608 B/op       2049 allocs/op
BenchmarkNewRectangleOL5        1000       1496754 ns/op     6340608 B/op          2 allocs/op
BenchmarkNewRectangleOL0       50000         32721 ns/op       55296 B/op          2 allocs/op
BenchmarkNewRectangleOS5    10000000           221 ns/op          57 B/op          1 allocs/op
BenchmarkNewRectangleOS0    10000000           194 ns/op          57 B/op          1 allocs/op
BenchmarkNewRectangle14L5       1000       1497511 ns/op     6340608 B/op          2 allocs/op
BenchmarkNewRectangle14L0       2000        803754 ns/op     6340608 B/op          2 allocs/op

The optimal implementation is still faster; it uses about 29% less CPU time (1496754 ns/op vs. average 2058088.5 ns/op) and about 99.9% less heap allocations (2 allocs/op vs. 2049 allocs/op). It's even faster for a zero initial value (32721 ns/op vs. average 2058088.5 ns/op).

In addition to the benchmarks, we could have used profiling.

File rectangle.go:

package rectangle

import (
    "bytes"
)

// For loop using a for clause
func NewRectangleF(height, width int, value byte) [][]byte {
    r := make([][]byte, 0, height)
    for i := 0; i < height; i++ {
        r = append(r, bytes.Repeat([]byte{value}, width))
    }
    return r
}

// For loop using a range clause
func NewRectangleR(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        r[i] = bytes.Repeat([]byte{value}, width)
    }
    return r
}

// Benchmark basic
func NewRectangleB(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    for i := range r {
        w := make([]byte, width)
        if value != 0 {
            for j := range w {
                w[j] = value
            }
        }
        r[i] = w
    }
    return r
}

func repeat(b []byte, count int) []byte {
    nb := make([]byte, len(b)*count)
    if len(b) == 1 && b[0] == 0 {
        return nb
    }
    bp := copy(nb, b)
    for bp < len(nb) {
        copy(nb[bp:], nb[:bp])
        bp *= 2
    }
    return nb
}

// Benchmark optimization
func NewRectangleO(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    a := repeat([]byte{value}, height*width)
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

// Go version tip (go1.4)
func NewRectangle14(height, width int, value byte) [][]byte {
    r := make([][]byte, height)
    var a []byte
    if value == 0 {
        a = make([]byte, height*width)
    } else {
        a = bytes.Repeat([]byte{value}, height*width)
    }
    start, end := 0, width
    for i := range r {
        r[i] = a[start:end:end]
        start, end = end, end+width
    }
    return r
}

File rectangle_test.go:

package rectangle

import (
    "fmt"
    "testing"
)

type nrFunc func(height, width int, value byte) [][]byte

func testNewRectangle(t *testing.T, nr nrFunc) {
    /*
        #!/usr/bin/env ruby
        HEIGHT = 2
        WIDTH = 3
        array = Array.new(HEIGHT){ Array.new(WIDTH){ 5 } }
        # [[5, 5, 5], [5, 5, 5]]
        print array
        print "\n"
    */
    height, width, value := 2, 3, byte(5)
    r := nr(height, width, value)
    if len(r) != height || cap(r) != height ||
        len(r[0]) != width || cap(r[0]) != width ||
        fmt.Sprintln(r) != "[[5 5 5] [5 5 5]]\n" {
        t.Error("Invalid rectangle:", r, fmt.Sprint(r))
    }
}

func TestNewRectangle(t *testing.T) {
    var tests = []nrFunc{
        NewRectangleF, NewRectangleR,
        NewRectangleB, NewRectangleO, NewRectangle14,
    }
    for _, test := range tests {
        testNewRectangle(t, test)
    }
}

var (
    smallHeight = 2
    smallWidth  = 3
    largeHeight = smallHeight * 1024
    largeWidth  = smallWidth * 1024
    zeroValue   = byte(0)
    fiveValue   = byte(5)
)

func BenchmarkNewRectangleFL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleF(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleRL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleR(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleBL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleB(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleOL5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleOL0(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(largeHeight, smallWidth, zeroValue)
    }
    _ = r
}

func BenchmarkNewRectangleOS5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(smallHeight, smallWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangleOS0(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangleO(smallHeight, smallWidth, zeroValue)
    }
    _ = r
}

func BenchmarkNewRectangle14L5(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangle14(largeHeight, largeWidth, fiveValue)
    }
    _ = r
}

func BenchmarkNewRectangle14L0(b *testing.B) {
    b.ReportAllocs()
    var r [][]byte
    for i := 0; i < b.N; i++ {
        r = NewRectangle14(largeHeight, largeWidth, zeroValue)
    }
    _ = r
}


Do I need to use a callback function here, or is there another way? Here is the pertinent code:

index.html

<!--  DOM INITIALIZATION -->
<script type="text/javascript">
$().ready(function() {

getThemeInfo();

if (themeSelect==2) {
   ReplaceJSCSSFile("css/skin1.css", "css/skin2.css", "css");   // overwrite CSS
}

AJAX_LoadResponseIntoElement("skinContainer", "skin" + themeSelect + ".txt", function() {
    AJAX_LoadResponseIntoElement("contentdiv", "index.txt", initPage);
    });

});
</script>

funcs.js

function initPage()
{
    setContentDimensions();
    replaceCSSMenu();
    showContainer();
    setContentPositions();
}

function setContentPositions()
{
    var contentTop = findTop(document.getElementById('NavMenu')) + 4;
    var contentLeft = findLeft(document.getElementById('kwick1')) + 226;

    document.getElementById('contentdiv').style.top = (contentTop)+ "px";
}

Quick recap: It fetches the theme selection, and if it's not the default (1), then it changes the CSS file to skin2.css.  Then, it fetches the page with AJAX and initializes it, and part of initialization is setting the div dimensions and positions.

Although the theme swap works perfectly through the button (code not shown here,) it does not work in Opera if the theme setting, stored in cookies, is a non-default theme, causing the CSS to be swapped during the loading of the page (i.e. this code here.)  For whatever reason, the .top and .left of my "contentdiv," which is set in ContentPositions() function, is wrong.

I'd assumed this was happening because the CSS styles were not loaded prior to the JavaScript attempting to set contentdiv's position.  To test this theory, I put an alert() in setContentPositions() to test that contentTop & contentTop were indeed wrong (they were,) and then another alert() after the DOM init line that changes the CSS file.  With the addition of the alert() after the CSS change within DOM init, it loads perfectly.

Why is the CSS file not processed by the time it does two AJAX fetches?  Is a callback function the proper way to fix this?

Edit...

The code for some of the functions used in the above code was requested.  Here it is:

function ReplaceJSCSSFile(oldfilename, newfilename, filetype){
 var targetelement=(filetype=="js")? "script" : (filetype=="css")? "link" : "none";
 var targetattr=(filetype=="js")? "src" : (filetype=="css")? "href" : "none";
 var allElements=document.getElementsByTagName(targetelement);

 for (var i=allElements.length; i>=0; i--){
  if (allElements[i] && allElements[i].getAttribute(targetattr)!=null && allElements[i].getAttribute(targetattr).indexOf(oldfilename)!=-1){
   var newelement=CreateJSCSSFile(newfilename, filetype);
   allElements[i].parentNode.replaceChild(newelement, allElements[i]);
  }
 }
}

function CreateJSCSSFile(filename, filetype){
 if (filetype=="js"){
  var fileref=document.createElement('script');
  fileref.setAttribute("type","text/javascript");
  fileref.setAttribute("src", filename);
 }
 else if (filetype=="css"){
  var fileref=document.createElement("link");
  fileref.setAttribute("rel", "stylesheet");
  fileref.setAttribute("type", "text/css");
  fileref.setAttribute("href", filename);
 }
 return fileref;
}

function AJAX_LoadResponseIntoElement (elementId, fetchFileName, cfunc) {
  var XMLHRObj;
  if (window.XMLHttpRequest) { XMLHRObj=new XMLHttpRequest(); }
    else { XMLHRObj=new ActiveXObject("Microsoft.XMLHTTP"); }

  XMLHRObj.onreadystatechange=function()
    {
    if (XMLHRObj.readyState==4 && XMLHRObj.status==200)
      {
      document.getElementById(elementId).innerHTML=XMLHRObj.responseText;
      cfunc();
      }
    }
  XMLHRObj.open("GET",fetchFileName,true);
  XMLHRObj.send();
}

I would suggest to take a different approach. It is complicated to get a callback for the complete loading of a CSS stylesheet loaded dynamically: see this Stack Overflow question for reference:

Is there anyway to listen to the onload event for a  element?

Do not use JavaScript to set the content position: it is part of styling and should be done in CSS instead. Isn't the role of your CSS skins to modify the appearance of the page?


Combine a boolean condition with a Where clause in same query I'm trying to see if I can somehow reduce the length of this query.
I have a common part with the string.Compare(...),

is IsProperty == true I would like to take all strings where Value is property, and false do the opposite.

What I have now is:

List<KeyValuePair<int,string>> Groups =
    isProperty ? model.Groups.Where(
      m => string.Compare(m.Value, "properties", true) == 0
    ).ToList() :
    model.Groups.Where(
      m => string.Compare(m.Value, "properties", true) != 0
    ).ToList();

What I would like:

List<KeyValuePair<int,string>> Groups =
    model.Groups.Where(
      m => string.Compare(m.Value, "properties", true) == 0 || !=0 //depending on isProperty
    ).ToList();

Not sure if it is all possible. (What I really want is to add it to the .Where when I pull values from DB)

Taking @VisualMelon's advice,

I converted it to this code, also replacing the compare with equal, maybe better.

List<KeyValuePair<int,string>> Groups =
model.Groups.Where(
  m => string.Equals(m.Value,
                     "properties",
                     StringComparison.OrdinalIgnoreCase) == isProperty)
  .ToList();


Copy memory blocks of different sizes Is there a better way than this to copy the values from source to destination when the blocks of memory you want to copy to and from are different sizes? Also considering you have no control over making sure the sizes match to begin with.

while (count--) {
   memcpy(dst, src, dst_stride);
   src += src_stride;
   dst += dst_stride;
}

If it is possible that the strides match then you can add a if check to just copy it all in one go:

if(src_stride == dst_stride){
    memcpy(dst, src, count * dst_stride);
} else {
    while (count--) {
       memcpy(dst, src, dst_stride);
       src += src_stride;
       dst += dst_stride;
    }
}


Java 2d array Hourglass Sums challenge from Hackerrank This is a java solution to a Hackerrank problem.

I know it's not optimized, can anyone help me to refactor and optimize?

  Task:

  Calculate the hourglass sum for every hourglass in the 6×6 array, then print the maximum hourglass sum.

  An "hourglass sum" is defined as the sum of any 7 entries of the array that are selected by this pattern mask:

✓ ✓ ✓
  ✓
✓ ✓ ✓

  Input Format:

  There are 6 lines of input, where each line contains 6 space-separated
  integers describing 2D Array; every entry is in the inclusive range -9 to 9.

  Output Format

  Print the largest (maximum) hourglass sum found in the array.

  Sample Input

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

  Sample Output

19

Solution:

public class TestHourGlass {

        public static void main(String[] args) {
                Scanner in = new Scanner(System.in);
                int arr[][] = new int[6][6];
                int hourGlassSum[] = new int[16];
                int pos = 0;

                //Reads data from user input and store in 6*6 Array
                for (int arr_i = 0; arr_i < 6; arr_i++) {
                    for (int arr_j = 0; arr_j < 6; arr_j++) {
                        arr[arr_i][arr_j] = in.nextInt();
                    }
                }
                //Find each possible hourGlass and calculate sum of each hourGlass
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        hourGlassSum[pos] = calculateHourGlassSum(arr, i, i + 2, j, j + 2);
                        pos++;
                    }
                }
                System.out.println(findmax(hourGlassSum));

            }
            /**
             * @param arr
             * @param pos1 - Row startPoint
             * @param pos2 - Row endPoint
             * @param pos3 - column startPoint
             * @param pos4 - column endPoint
             * @return
             */
            public static int calculateHourGlassSum(int arr[][], int pos1, int pos2, int pos3, int pos4) {

                int sum = 0;
                int exclRowNum = pos1 + 1;
                int exclColNum1 = pos3;
                int exclColNum2 = pos4;
                for (int arr_i = pos1; arr_i <= pos2; arr_i++) {
                    for (int arr_j = pos3; arr_j <= pos4; arr_j++) {
                        sum = sum + arr[arr_i][arr_j];
                    }
                }
                sum = sum - (arr[exclRowNum][exclColNum1] + arr[exclRowNum][exclColNum2]);
                return sum;
            }

            /**
             * @param arr
             * @return max elem of Array
             */
            public static int findmax(int arr[]) {
                int max = arr[0];
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] >= max)
                        max = arr[i];
                }
                return max;
            }
}

Avoid magic number

6 and 16 should be replace with properly named constants... 16 is also dependant of the first number ; if I'm not mistaken the number of possible hourglasses is (6 - 2)²

public static final int GRID_SIZE = 6;
public static final int NUMBER_OF_POSSIBLE_HOURGLASSES = Math.pow(GRID_SIZE - 2, 2);

Better naming

Most of your variable have good name, however it's not useful to name indices arr_i and arr_j, name them simply i and j.

The class name is not that good IMO, HourGlassSolver or HourGlassFinder would be better.

findmax should be cased like this findMax

Parameters for calculateHourGlassSum have unclear name (pos2 ??)

Simplify your function

Your function do their jobs well but can be made shorter thanks to the new Java 8 Stream API.

For example, your findmax :

public static int findMax(final int arr[]) {
    return Arrays.stream(arr).max().get();
}

Extract part of your code into a function

for (int i = 0; i < 4; i++) {
   for (int j = 0; j < 4; j++) {
       hourGlassSum[pos] = calculateHourGlassSum(arr, i, i + 2, j, j + 2);
       pos++;
   }
}

This should probably be made into a distinct function that returns an int array or a List<Integer>.


A suicide prevention Redditbot I have written a Reddit bot in Python (code below). Open to any improvements, especially on efficiency, as I am using PythonAnywhere to run it.

The main function is to scan posts in reddit and when certain phrases are found in the text private message the reddit user. Furthermore, the reddit user shouldn't be messaged twice.

#------------------------------------------------------------------------------
def Github_text():

    print("Open textfile...")

    data = urllib.request.urlopen("####").read()
    text = re.search("<StartText>(.+?)<EndText>", str(data))

    if text:
        private_message_text = text.group(1)
        private_message_text = private_message_text.replace(r"\\n","\n")

    print("Text is ready!")

    return private_message_text

def bot_login():

    print("Login...")

    reddit = praw.Reddit(client_id="####",
                client_secret="####",
                password="####",
                user_agent="####",
                username="####")

    print("Login succesfull!")

    return reddit

def run_bot(reddit):

    now = datetime.datetime.now()
    print("Start iteration..." + now.strftime("%Y-%m-%d %H:%M:%S"))

    for submission in reddit.subreddit("all").new(limit=1000):
        if any(sentence in submission.selftext for sentence in check_sentences) \
        and submission.author not in users_messaged and not submission.stickied and submission.is_self:

          print(submission.selftext)

          if len(users_messaged) > 50:
              del users_messaged[0]
              users_messaged.append(submission.author)
          else:
              users_messaged.append(submission.author)

          reddit.redditor(str(submission.author)).message(private_message_title, private_message_text)

          print("Message send to:" + str(submission.author))

    time.sleep(120)

#------------------------------------------------------------------------------
check_sentences = ["####",
                   "####",
                   "####",
                   "####",
                   "####",
                   "####",
                   "####",
                   "####"]

users_messaged = []
private_message_title = "####"
private_message_text = Github_text()
reddit = bot_login()

print("Start loop!")

while True:
    run_bot(reddit)

Pass values as parameters for modularity
You can make your code a lot more modular if you pass values to functions as parameters instead of hardcoding values in the function itself.
Let's change the bot_login() function to this.
def bot_login(client):
    print("Login...")
    reddit = praw.Reddit(client_id=client["id"],
                client_secret=client["secret"],
                password=client["password"],
                user_agent=client["useragent"],
                username=client["username"])
    print("Login succesfull!")
    return reddit

This way you can call the function like this
client={ "id":"1",
    "secret":"supersecret",
    "password":"password123",
    "useragent":"Chrome 1.0",
    "username":"beepbot"}
bot_login(client)

Your Github_text() function should look something like this.
def github_text(github_url):

Also, notice the lowercase function definitions. You are better off following standards.
Similarly, you should never go with generic variable names such as data text even though they are better than x,y,t1 etc. You can use them if the context is very clear but even so using specific names such as website_response is better.
You can change the function definition of run_bot(reddit) to
run_bot(reddit,subreddit,limit)
This way you can maybe run your bot in other subreddits.
Code is better understood vertically
if any(sentence in submission.selftext for sentence in check_sentences) \
        and submission.author not in users_messaged and not submission.stickied and submission.is_self:

That is very hard to read.
Maybe write it like this
conditions=[any(sentence in submission.selftext for sentence in check_sentences),
            submission.author not in users_messaged,
            not submission.stickied,
            submission.is_self]
if all(conditions):

Please handle edge cases
What happens to the github_text() function if re.search() does not return anything? private_message_text is not defined! Probably won't happen but nothing is guaranteed.
Also if you are using Python3 why not use urllib2 instead of urllib. urlopen() seems to be deprecated use urllib2.urlopen() instead.
Use if __name__=='__main__'
It is better to use this format to run code.
if __name__=='__main__':
    main()

It is a good programming habit even if you are not going to import this anywhere.
  if len(users_messaged) > 50:
      del users_messaged[0]
      users_messaged.append(submission.author)
  else:
      users_messaged.append(submission.author)

I don't know what you are trying to do with this piece of code. But it probably does not do what you want. Since you don't want to message the same person again.
Perfomance
The major performance bottleneck you will face is probably in the network and not in your code. (I could be wrong). I am not familiar with the Reddit API. But if it allows you to message a bunch of users at the same time then you should probably generate the user list and message them all at once.
As a side note, you should handle exceptions if there are any. Especially, if you are going to run this code for a long time. You don't want your program to suddenly stop because of a read timeout.


Extend API of complex source-code parsing CPAN module I am working on a source line parser using PPI. After working a while, I realized that
it would be nice if the PPI API had included such and such functionality. As a very simple example, the PPI::Element contains a class method that returns the class name of the current element. This method must be called quite often and results in statements like

if ( $elem->class eq 'PPI::Token::Symbol' ) { ... }

Now all these statements contain strings with prefix PPI::, so it would be nice if there was a an alternative to the class method that would omit the prefix. For exmple a name method:

if ( $elem->name eq 'Token::Symbol' ) { ... }

How can this best be achieved? In general, the question is how to extend a complex CPAN module like PPI with user defined methods? I think sub classing the PPI::Element method would not work (see example below)  since other PPI methods like find or snext_sibling would still return PPI::Element objects (see below example) and not objects of my sub class. Here is what I came up with:

use feature qw(say);
use strict;
use warnings;

BEGIN {
    require PPI;
    require PPI::Dumper;
    require My::PPI::Extensions;

    *{PPI::Element::name} = \&My::PPI::Extensions::name;
}

my $line = 'f( $q->{key}[$var + 4] );';
my $doc = PPI::Document->new( \$line );
my $dumper = PPI::Dumper->new( $doc );
$dumper->print;
my $symbols = $doc->find('PPI::Token::Symbol');
my $elem = $symbols->[0];
say "";
say "Start elem: " . $elem->class;
$elem = $elem->snext_sibling;
say "Next elem: " . $elem->class;

# This first test is how it would be done originally,
# here I have to include the "PPI::" prefix
if ( $elem->class eq 'PPI::Token::Operator')  {
    say "First test ok..";
}
# This second test is to show how it could be done without
# modifying the `PPI::Element` API
if ( is_elem( $elem, name => 'Token::Operator') ) {
    say "Second test ok..";
}
# This last test shows the new method "name":
if ( $elem->name eq 'Token::Operator') {
    say "Third test ok..";
}

sub is_elem {
    my ( $elem, %opt ) = @_;

    my $class = $elem->class;
    $class =~ s/^PPI:://;
    return $class eq $opt{name};
}

where My/PPI/Extensions.pm is:

package My::PPI::Extensions;
use feature qw(say);
use strict;
use warnings;

sub name {
    my $self = shift;

    my $name = $self->class;
    $name =~ s/^PPI:://;
    return $name;
}

1;

Note: the code I am working on might turn into an open source project at some point. It could also become somewhat complex. So it will be important that it will be maintainable in the long run, also by others in addition to myself.

References:

Chapter 9: Modifying and Jury-Rigging Modules
of Mastering Perl.

Now all these statements contain strings with prefix PPI::

I know this is true of all things in PPI itself, and its a very popular convention.

But I suspect there are cases where things may enter the Document without actually being =~ /^PPI::/.

Also, it seems to me that what you're optimising for is a less frequent usecase than you should be optimising for:

$x->isa("PPI::Whatever")

Should be more heavily used in real code than

"PPI::Whatever" eq $x->class

Either way, you can do better than

 "Whatever" eq $x->name

You could do

 $x->is_named('Whatever');

But that's still gross because "you're not using @ISA".

 $x->is("Whatever")

This could work, but now you're in a bind:

What happens if $x does not subclass whatever class the is method was added on?

These are all, IME, big annoying problems that your desired approach simply makes more complicated to paper over a minor detail.

Which is especially silly when

$x->isa("PPI::Whatever")

Will work, on everything, both PPI and not.

That doesn't mean a "name" attribute wouldn't be useful, but it needs to be said that you should not be proposing to use it as the prime deciding mechanism, and should probably only be for diagnostics.

Given all of the above, a functional API is going to be much more to your liking.

use PPI::Naming qw( is_named is_an );
# not ISA aware
if ( is_named( $object, 'Whatever' ) ) {
         ....
}
# ISA aware
if ( is_an( $object, 'Whatever' ) ) {

}

is_named would be straight forward:

sub is_named {
  my ( $object, $name ) = @_;

  return undef unless defined blessed( $object );

  # This allows somebody to specify "=Whatever" and have it mean
  # "Whatever.pm" instead of "PPI::Whatever"
  if ( $name =~ /^=(.*$)/ ) {
     return $object->class eq "$1";
  }
  return $object->class eq 'PPI::' . $name;
}

is_an would be a little more complicated.

use MRO::Compat;
use Scalar::Util qw( blessed );
sub is_an {
  my ( $object, $name ) = @_;

  my $class = blessed($object);
  return undef unless defined $class;

  # This allows somebody to specify "=Whatever" and have it mean
  # "Whatever.pm" instead of "PPI::Whatever"
  if ( $name =~ /^=(.*$)/ ) {
    return $object->isa("$1");
  }
  for my $parent ( mro::get_linear_isa($class) ){
    return 1 if $parent eq "PPI::" . $name;
  }
}

The biggest benefit of this approach is there's almost no room for error. There's no chance that one of your objects could be missing the magic methods you require.

Related Reading

MRO::Compat
Scalar::Util


Is my design achieving Separation of Concerns in this MVC implementation? I've read lots about getters and setters being evil, unless there is good call for one, but I cannot figure out how to implement that knowledge into my Model layer.

Say in my Model layer I have a class that has services like:

findStudentsByID($searchCriteria)
findStudentsByLastName($searchCriteria)

...

Do I require a getter or a setter, say $searchCritera, here so I can maintain Separation of Concerns?

Would it be wrong to simply query the model from the view with findStudentsByID(4);?  Wouldn't that bind the two too much?

I thought I could use at least a setter so I can change the state of the class and then use a method.

For example,

API enforcement:

interrace IModel{
 public function setCriteria($searchCriteria);
 public function findStudentByID();
 public function findStudentByLastName();
}

In my model:

    class Model implements IModel{

    private $searchCriteria;

    public function setCriteria($searchCriteria){
      $this->searchCriteria = $searchCriteria;

    }

    public function findStudentByID(){
     some SQL "WHERE student_id = " $this->searchCriteria;
     return $results;
    }

    public function findStudentsByLastName(){
     some SQL "WHERE last_name = " $this->searchCriteria;
     return $results;
    }

    }

In my controller:

interface IController{
  public function someAction($searchCriteria);
}

class Controller implements IController{

    private $model;

    public function __construct(IModel $model) {
        $this->model = $model;
    }

//for argument say this is from a front controller passing the value
public function someAction($searchCriteria){

$this->model->setCriteria($searchCriteria);  //model state is changed

}

}

In my view:

interface IView{
  public function students();
}
class View implements IView{
  private $model;
  public function __construct(IModel $model){
    $this->model = $model;
  }

  public function students(){
    return $this->model->findStudentsByLastName();
    require_once("some_template_somewhere");  //get my template
  }

}

some template:

<!DOCTYPE html>

    <meta charset="utf-8">
    <title>Form Example</title>

Students

      <?php foreach($this->view->students() as $student) { ?>

            <?PHP echo $student["student_id"] ?>

            <?PHP echo $student["LAST"] ?>

    <?PHP } ?>

Implementation:

//some starting point:

$model = new Model();
$controller = new Controller($model);
$view = new View($model);

$controller->someAction($_GET['myAction']);  //changing model state;

$this->view->students();

Do I really need the view there?  Would it be better to simply use this in a view/template (yes, I know they're different)?

  <?php foreach($this->view->model->findByStudentID(4) as $student) { ?>

        <?PHP echo $student["student_id"] ?>

        <?PHP echo $student["LAST"] ?>

<?PHP } ?>

The only thing I can see that will help with future maintainability, which is why I want my separation of concerns to begin with, is that I can switch the layers/concerns without breaking the other layers/concerns.  The interface will make sure I have the setCriteria, etc.

From what I can see

I could switch out the model.
I could switch out the template.
I could switch out the controller.

But say someone makes their own Model.  If they create an additional function, won't that break everything, rippling up?  What if they implement only the stock functions in my model, but they return different information?  I didn't really want a separate layer in my model layer, I thought I had abstracted myself to death already, though I feel like I might be slightly better off with abstract classes instead of interfaces.

EDIT:  I changed the method being called to finding the students by last name so the example makes more sense.

Summary with answers below

MVC gone bad

I allready wrote an article on how MVC is abused, so I'm not going to repeat myself here.

So what is MVC?

MVC is a design pattern (or architectual pattern or even cake) that seperates our code into 3 distinct functionalities: Model, View and a Controller.

Model

The Model represents the Data. For instance a Student.

View

A view presents those Models. For instance in a table. It thus acts purely as representation layer.

Controller

The controller is the part that gets a command from the user/client and translates it to the correct internal command. e.g. "show user with id 4" => "pas the User Model with id 4 to the correct view"

Implementation

What MVC doesn't do is tell you anything about how you implement it. It also doesn't tell you how these different components interact.

MVC doesn't say anything about using other code. A lot people cram everything into MVC. So are you. Your Model is not a Model but a Repository (or Mapper or whatever you call it). Your Model acts as a layer to query your MySQL database that returns an object that represents your data.

Implementing the model:

the Student model will have method that will help you get information about the Model. For instance:

function getFullName() {
    return $this->firstName . ' ' . $this->lastName;
}

Retrieving the model

We ofcourse need a way of retrieving a Model. This could be done for instance using a Repository:

interface UserRepository
{
    public function find($id)

    public function getBy($key,$value)
}

and because we use Mysql, lets implement a repository that does all the fetching:

class MysqlUserRepository implements UserRepository
{
    public function find($id)
    {
        $result = $this->db->query('SELECT FROM users WHERE id = '.$id;
        return new User($result[0]);
    }

    public function getBy($key,$value) { ... }
}

This UserRepository could for instance be injected into the controller:

Implementing the controller

class UserController
{
    public function find($id)
    {
        $user = $this->repository->find($id);

        return ViewFactory::make('show.user', array('user'=>$user)));
    }
}

Here the UserController returns a View object. I opted for a Factory pattern approach here:

ViewFactory & view

class ViewFactory
{
    public static function make($viewName, $data) {
        $view = new View(VIEW_DIR . $viewName);
        $view->addData($data);
    }
}

And our view will look someting like this:

class View
{
    public function __construct($viewFile)
    {
        $this->viewFile = $viewFile;
    }

    public function addData($data)
    {
        $this->data = array_merge($data, $this->data);
    }

    public function render()
    {
        extract($this->data);
        include $this->viewFile;
    }
}

Implementing our view

  Because I don't like writing $this->data->.. stuff in my templates, I use the extract function in the render function.

views/dir/show.user.tpl.php

<?php echo $user->getFullName(); ?>

Age: <?php print $user->getAge(); ?>

Just an Example.

Now this is just an example - and it should be treated as one.

Summary

to answer your questions

  Do I require a getter or a setter, say $searchCritera, here so I can maintain Separation of Concerns?

No, why should searchCriteria be seperated? A searchCriteria needs context:

UserRepository::getById(4);

returns something completly different as

UserRepository::getOlderThenYears(4);

  Would it be wrong to simply query the model from the view with
  findStudentsByID(4);? Wouldn't that bind the two too much?

YES, very wrong. A view is a presentational piece of software. It is stupid an knows nothing. Only how to present a certain object to the screen. Nothing more.

Models

Instead of using getters/setters on a Model. One could simply use public variables (or emulate them using the magic methods (PHP)). Since a Model is a representation of data, you could simply change it's values. After changes are made one could pass it back to the repository:

$user = Repository::find(4);
$user->name = 'foobar';
Repository::save($user);


Counting the number of increasing sub-sequences The problem is to find the number of increasing sub-sequence of a string with only digit characters.
Answer may be very large, so output it modulo 10^9+7.

I have been able to get a O(n) solution using segment trees. However , the the code is quite inefficient owing to loops with constant but large runtime. How can I make the code more efficient ?

The link to the exact problem statement is http://www.spoj.com/problems/LARSUBP/

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

typedef struct Tree_node
{
    int M[10][10] ;
    // M[i][j] = Number of sub-sequences starting with i and ending with j in the interval low to high in which it is called .
} TN ;

//Declaration of global variables

char number[50000] ;//Stores the input string
TN Tree[100000] ;//The array Tree[] is used to store the nodes of the segment tree
long long int convert ; //Other variables
int k1 , k2, i , j;

void Build_Tree( int node , int low , int high) ;

int main()
{
    // t is the number of test cases
    // N is the length of input string
    int t , N , counter ;

    //Stores the number of increasing sub-sequences
    long long int answer ;

    //No of test cases
    scanf("%d",&t) ;

    for(counter=0;counter<t;counter++)
    {
        scanf("%s",number) ;
        N = strlen(number) ;

        // Calling the build tree function
       Build_Tree(1,0,N-1) ;

        // Calculation of increasing sub-sequences using the Tree .
        answer = 0 ;
       for(i=0;i<10;i++)
       {
           for(j=i;j<10;j++)
           {
              answer = answer + Tree[1].M[i][j] ;
              answer= answer % 1000000007 ;
           }
       }
       answer = answer %1000000007 ;
       printf("%lld\n",answer) ;

    }
    return 0 ;
}

void Build_Tree( int node , int low , int high)
{

 // node stores the index of the Tree-node to be evaluated
 // low and high define the interval which we are considering

    int mid ;

    // Initialization of M[][]
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            Tree[node].M[i][j] =0 ;

        }
    }

    if(low==high)
    {
        // Base case
        int temp = number[low]- '0' ;
        Tree[node].M[temp][temp] = 1 ;
    }
    else
    {
        mid = (low+high)/2 ;
        Build_Tree(2*node , low , mid) ; // Building the subtree of left child
        Build_Tree(2*node+1 , mid+1 , high) ; // Building the subtree of right child

    // Combining the information
    // No. of increasing sub-sequences starting with i and ending withj from low to highequal to sum of
    // 1.increasing sub sequences starting with i and ending with j from low to mid
    // 2.increasing sub sequences starting with i and ending with j mid+1 to high
    //3. all increasing sub-sequences starting with i and ending with k1 from low to mid multiplied by increasing sub sequences starting with k2 and ending with j from mid+1 to high where k1 < k2 .

        for(i=0;i<10;i++)
        {
            for(j=i;j<10;j++)
            {
                convert = Tree[2*node].M[i][j] + Tree[2*node+1].M[i][j] ;
                convert = convert % 1000000007 ;
                Tree[node].M[i][j] = convert ;

                if(i==j)
                {
                    continue ;
                }
                else
                {

                    for(k1=i;k1<j;k1++)
                    {
                        for(k2=k1+1;k2<=j;k2++)
                        {
                            convert = Tree[node].M[i][j] + Tree[2*node].M[i][k1] * Tree[2*node+1].M[k2][j] ;
                            convert = convert % 1000000007 ;
                            Tree[node].M[i][j] = convert ;

                        }
                    }
                }

            }
        }

    }

}

\$\newcommand{\sub}[1]{\text{sub}_{#1}}\$
This is more of an alternative algorithm than a review on your code (at least for now), but it seems like both could be helpful.

A good algorithm results from solving a slightly more informative version of the problem, which is simpler to decompose:

  \$\sub{s}^n\$ is the number of subsequences of \$s\$ that are ordered and end with the digit \$n\$.

\$\sub{s}\$ can be stored in a 10-long array, the sum of which solves your original problem:

$$
\left[\ \sub{s}^0;\ \text{sub}_s^1;\ \text{sub}_s^2;\ \ldots;\ \text{sub}_s^9\ \right]
$$

Clearly, for the empty string \$\varnothing\$, we have

$$
\text{sub}_\varnothing = \left[\ 0;\ 0;\ 0;\ \ldots;\ 0\ \right]
$$

The interesting trick is that extending a string \$s\$ with digit \$d\$ is a simple update

$$
\sub{sd}^n =
\begin{cases}
\sub{s}^n & \text{if}\;n \ne d\\
1 + \sum_{i=0}^{n} \sub{s}^i & \text{if}\;n = d
\end{cases}
$$

as the paths for subsequences that don't end in \$d\$ are unchanged and the subsequences that do end in \$d\$ are \$d\$ itself, \$d\$ added to the end of any prior subsequence that ends in a digit less than \$d\$, or any of the prior subsequences that did end with the digit already.


Simple load testing script in bash Here's the code

max="$1"
date
echo "url: $2
rate: $max calls / second"
START=$(date +%s);

get () {
  curl -s -v "$1" 2>&1 | tr '\r\n' '\\n' | awk -v date="$(date +'%r')" '{print $0"\n-----", date}' >> /tmp/perf-test.log
}

while true
do
  echo $(($(date +%s) - START)) | awk '{print int($1/60)":"int($1%60)}'
  sleep 1

  for i in `seq 1 $max`
  do
    get $2 &
  done
done

This can be run as

sh load-test.sh 20 "http://api.myserver.com/get_info"

Please suggest if you think there's a way to take in multiple curl options.

Arithmetics in Bash

You're doing some math in Bash, some in Awk, some in a combination of both. You can do all of that in Bash alone. Most notably, instead of this:

echo $(($(date +%s) - START)) | awk '{print int($1/60)":"int($1%60)}'

This would be equivalent, but all in Bash, without additional processes:

((delta = $(date +%s) - START))
((minutes = delta / 60))
((seconds = delta % 60))
echo $minutes:$seconds

Don't use seq

seq is not portable, I suggest to avoid it. Instead of this:

 for i in `seq 1 $max`; do ...; done

You can write:

for ((i = 1; i < max; i++)); do ...; done

Don't use `...`

This syntax is obsolete today, always use $(...) instead.

Other minor things

This would be clearer as two echo lines, or a here-document with cat <<EOF:

echo "url: $2
rate: $max calls / second"

The trailing semicolon is unnecessary:

START=$(date +%s);

The quoting is unnecessary in date +'%r', but it does no harm.


Matrix rotation algorithm - follow-up In a response to this post I wrote a solution in Python. It passed all the test cases given, so I would like help making it more pythonic and reducing the almost repeated lines.

Link to the source of the question on HackerRank.

# input
M, N, rotations = map(int, input().split())
matrix = []
for row in range(M):
    matrix.append(list(map(int, input().split())))

# flatten the rings into a list
layers = int(min(N, M)/2)
ring = [[] for layer in range(layers)]

for level in range(layers):
    top = (N-1) - 2 * level
    side = (M-1) - 2 * level
    for row in range(top):  # right
        ring[level].append(matrix[level][level + row])
    for col in range(side):  # down
        ring[level].append(matrix[level + col][level + top])
    for row in range(top):  # left
        ring[level].append(matrix[level + side][level + top - row])
    for col in range(side):  # up
        ring[level].append(matrix[level + side - col][level])

# rotate each layer
for level in range(layers):
        r = rotations % len(ring[level])
        ring[level] = ring[level][r:] + ring[level][:r]

# fill the array with the rotated elements
for level in range(layers):
    top = (N-1) - 2 * level
    side = (M-1) - 2 * level
    for row in range(top):
        matrix[level][level + row] = ring[level].pop(0)  # right
    for col in range(side):
        matrix[level + col][level + top] = ring[level].pop(0)  # down
    for row in range(top):
        matrix[level + side][level + top - row] = ring[level].pop(0)  # left
    for col in range(side):
        matrix[level + side - col][level] = ring[level].pop(0)  # up

# print the rotated matrix
for row in range(M):
    for col in range(N):
        print(matrix[row][col], "", end="")
    print()

List comprehensions

Whenever you see a list initialization to [],
later filled in by .append(...) calls in a loop,
consider rewriting with a list comprehension.
For example:

matrix = []
for row in range(M):
    matrix.append(list(map(int, input().split())))

Can be rewritten on a single line:

matrix = [list(map(int, input().split())) for _ in range(M)]

Note that I renamed row to _,
this is a common convention when then loop variable is unused.

Another example of that is this list comprehension later in your code:

ring = [[] for layer in range(layers)]

Like earlier, rename layer to _:

ring = [[] for _ in range(layers)]

Integer division with //

Instead of this:

layers = int(min(N, M)/2)

Another, a more natural way to achieve the same effect using integer division with //:

layers = min(N, M) // 2

Coding style

The body of this for-loop is overindented:

# rotate each layer
for level in range(layers):
        r = rotations % len(ring[level])
        ring[level] = ring[level][r:] + ring[level][:r]

Possibly it's a result of the copy-pasting?
Either way,
a PEP8 checker would catch this.
It's recommended to use four spaces for an indent level,
and to use only spaces and never tabs for indenting code.

Reducing duplicated code

The current implementation works like this:

put each layer into ring
rotate the values in each layer in ring
overwrite the layers in the matrix from ring

Step 1 and 3 have very similar code, as you yourself noticed.
One way to reduce that is to implement shifting in-place,
without using the additional storage ring,
by doing something like this (\$k\$ is the number of rotations):

save the first \$k\$ items in a list
overwrite the \$i\$-th values by the \$(i+k)\$-th values. The last \$k\$ values will come from the values we saved in the previous step.

Easier said than done? Yes. Calculating the \$(i + k)\$-th position will be tricky.

I'd say your original implementation with the similar lines is fine:
it's easy to understand, and it passed the tests anyway.


Will this code get cleaned up by the garbage collector? I have been working on a Backbone.js application, and I am starting to think I am making a huge mistake.

I never fully understand garbage collecting, and how exactly some closures prevent it. I just try to keep as organized as possible.

I just read an article that states that JavaScript variables that are not declared using the var keyword will not be removed from memory.

Now in my application I create everything inside an object called once. I clean this object every time I move to another page. I clean out the whole object, and remove all the elements and events associated to it.

Note: I am talking here about a single page backbone.js application. With changing pages I mean changing from one route to another using Backbone.History.navigate.

Am I making good use of the once Object inside the App object?  Will all be gone when I change routes?

////////////////////////////////////
//
// Main Object for my application
//  - once : One time models/views/etc
//  - move : Called before I move to a
//           new route
//  - clean: Called after I moved to
//           the new route
//  - close: Used internal by `clean`
//
/////////////////////////////////////
App = {
    once: {},

    move: function(){
        this.olds = this.once;
        this.once = {};
    },
    clean: function(){
        for(var Obj in this.olds){
            if(this.olds[Obj].models){
                this.olds[Obj].forEach(function(model){
                    this.close(model);
                }, this);
            }
            this.close(this.olds[Obj]);
        }

        delete this.olds;
    },
    close: function(Obj){
        if(typeof(Obj.onClose) !== 'undefined'){
            Obj.onClose();
        }
        if(typeof(Obj.off) !== 'undefined'){
            Obj.off();
        }
        if(typeof(Obj.remove) !== 'undefined'){
            Obj.remove();
        }
    }
}

///////////////////////////////////////////////
//
// My model, collection, and 2 views
//
// Note that I left out some basic steps
//
//////////////////////////////////////////////
window.User = Backbone.Model.extend({});
window.Users = Backbone.Collection.extend({
    model: User
});

window.UserView = Backbone.View.extend({
    // Init, events,  etc ...
    render: function(){
        this.collection.forEach(function(user){
            App.once.userSubView = new UserSubView({
                model: user
            });
            this.$el.append(App.once.userSubView.el);
        })
    }
});
window.UserSubView = Backbone.View.extend({});

///////////////////////////////////////////////
//
// One of the routes of my router.
//
// All my routs begin with move() and end
// with clean().
//
//////////////////////////////////////////////

App.move();

App.once.users = new Users();

// Create the views
App.once.users.fetch({
    success: function(){
        App.once.userView = new UserView({
            collection: App.once.users
        })
        $('body').append(App.once.userView.el);
    }
})

App.clean();

This code looks mostly fine to me, when the .move method gets called, .once gets moved to .old and then when .clean happens, .old gets deleted (and eventually garbage collected unless a reference to it continues to exist somewhere else).

However I think you could do better by encapsulating each route in a function that takes care of .move and .clean for you.

Something like:

route(function () {
    App.once.users = new Users();

    App.once.users.fetch({
        success: function () {
            App.once.userView = new UserView({
                collection: App.once.users
            });
            $('body').append(App.once.userView.el);
        }
    });
});

where route is:

function route(fn) {
    App.move();
    fn();
    App.clean();
}

(but you probably already have a method like this in your code where these things would belong)

A better question: Why do you need this .once property anyway? It looks like it is just holding private data for the route. Why not make it private to the route then?

route(function () {
    var users = new Users();

    users.fetch({
        success: function () {
            $('body').append(new UserView({ collection: users }).el);
        }
    });
});

Garbage collection in JavaScript

(very simplified basic design ignoring tricks/special cases)

Every variable in javascript can be thought of as a reference to an underlying system object.

That is, in JS you have:

var a, b;

to the system there is:

var all = [ {data: a, declaredScope: function()}, {data: b, declaredScope: function()}];
var scope = function();

When the garbage collector runs, it does something like this:

function markDescend(variable) {
    for (var child in variable) { //the system has the child as seen in the "all" array
        if (child !== undefined && child !== null && !child.marked) {
            child.marked = true;
            markDescend(child);
        }
    }
}
var tempscope = scope;
var tempall = all;
do {
    for (var variable in tempall) {
        if(tempscope === variable.declaredScope) {
            variable.marked = true;
            markDescend(variable);
        }
    }
    tempscope = tempscope.outer;
} while (tempscope);

all = [];
for (var variable in tempall) {
    if(variable.marked) {
        variable.marked = false;
        all.push(variable);
    } else {
        __free(variable);
    }
}

That is to say, when the garbage collector runs, all variables reachable from the current scope (and closure scopes) are marked; then a second loop runs and all variables not marked are freed from memory.

Thus, if there is no way for the system to reach an object via scope then it is going to be collected. From a user perspective, there are a few ways to create objects that the user can not reach, but are still in scope. Some examples:

window.setTimeout(function () {}, x) - this function is reachable from global scope until it finishes running; and it has access to any variables from any of its closure scopes (even though you may not be able to reach it)
$.ajax('asdg', function () {}) - same as setTimeout
Any attached DOM node is reachable from the global scope. You may attach events to these nodes and if you don't maintain the reference, you would lose access to it.

In these cases, you would need to do more than what you are currently doing in your .move method to take care of unregistering these functions (In IE7 and below).  My perspective would be just to let it leak (tell the users to get a better browser). IE6 would leak until the browser is closed, IE7 would leak until the page is out of the navigation cache. In every other browser, once the DOM is detached (or the timeout occurs, or the ajax post happens, etc.) these functions are not reachable from the global scope anymore (and so they are removed in the next garbage collection cycle).

Cleanup in IE

Essentially what you are doing in .move is move the stuff you want to delete in the previous route to .old and then in .clean you take care of deleting the old references.

Really the only things you should care about are those properties that you cannot actually get at via variable properties once set. Whenever you do a window.setTimeout() (or similar) you would want to do something like this:

function setTimeout(fn, msec, App) {
    var id = window.setTimeout(function () {
            fn();
            destructor.removeReference = null;
        }, msec),
        destructor = {
            removeReference: function () { window.clearTimeout(id); }
        };
    App.once.push(destructor);
}

function setInterval(fn, msec, App) {
    var id = window.setInterval(fn, msec);
    App.once.push({
        removeReference: function () { window.clearInterval(id); }
    });
}

and so on for attaching events, setting DOM properties, making ajax requests, etc. Then in .clean you would check if the object in .old has a removeReference function; if so run it then delete it and the object.


JFrame with four sliders I am writing a control panel with Sliders but I think my code is messy and cumbersome, what can I do to improve it?

public class Input_Window extends JFrame {
    JSlider myslideA,myslideB,myslideC,myslideD;

    Input_Window(){
        System.out.println("* Control Window");
        setBackground(Color.GRAY);
        setResizable(false);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setTitle("Controls");
        setSize(200,400);
        setLocation(1200,250);
        setLayout(new FlowLayout());
        myslideA=slider(0,10,3,1,true,true);
        add(myslideA);
        myslideB=slider(0,10,3,1,true,true);
        add(myslideB);
        myslideC=slider(0,10,3,1,true,true);
        add(myslideC);
        myslideD=slider(0,10,3,1,true,true);
        add(myslideD);
        setVisible(true);
        setFocusable(true);
        requestFocus();
    }

    public final JSlider slider(int min, int max, int def, int maj, boolean ticks, boolean labels){

        JSlider myslide=new JSlider(JSlider.HORIZONTAL,min,max,def);
        myslide.setMajorTickSpacing(maj);
        myslide.setPaintTicks(ticks);
        myslide.setPaintLabels(labels);
        return (myslide);
    }

}

Naming:
Your class is named Input_Window which violates standard Java naming conventions of PascalCase (without underscores).
Formatting:
An equal sign should be surrounded by spaces:

myslideA = slider(0,10,3,1,true,true);
//and so on...

Visibilities:

Your JSliders should most probably be private. nobody aside from
your InputWindow should have to know about them. If there's someone out there who wants to know about GUI except the GUI you're doing things wrong ...
slider should also be private. If somebody else uses it, extract it to a utility-class. Hide the information where ever you can. If you don't things may happen with your stuff when you're not watching.

Responsibilities:
Your constructor shouldn't request focus and set the window to visible himself. That's things that should be done in calling code. You don't expect a JFrame to show up on instantiation either, right?


SIMD Finding the maximum Euclidean distance to origin (c++) I am trying to find the longest Euclidean distance to the origin for each point. Their positions are stored in two float arrays, denoting each point's position on the Cartesian plane. I tried to speed up the function using SIMD (WITHOUT SVML, so no _mm256_hypot_ps), however it still seemed a little bit slow. The code loop through the array by a chunk size of 8, on each iteration updates the maximum squared Euclidean distance and finally returns the sqrt of the maximum element.
#include <immintrin.h>
#include <math.h>
#include <stdio.h>
float dist(const float* x, const float* y, unsigned int len) {
  if (len < 16) {
    float d = 0.0f, a;
    unsigned i = 0;
    for (i = 0; i < len; i++) {
      a = x[i] * x[i] + y[i] * y[i];
      if (a > d) d = a;
    }
    return sqrt(d);
  }
  __m256 a = _mm256_loadu_ps(x), b = _mm256_loadu_ps(y);
  a = _mm256_mul_ps(a, a);
  b = _mm256_mul_ps(b, b);
  __m256 max = _mm256_add_ps(a, b);  // x[i]*x[i] + y[i]*y[i]
  unsigned i;
  for (i = 8; i + 8 < len; i += 8) {
    a = _mm256_loadu_ps(x + i);
    a = _mm256_mul_ps(a, a);
    b = _mm256_loadu_ps(y + i);
    b = _mm256_mul_ps(b, b);
    max = _mm256_max_ps(
        max, _mm256_add_ps(a, b));  // max(max[i], x[i]*x[i] + y[i]*y[i])
  }
  float d = 0.0f, t;
  for (; i < len; ++i) {
    t = x[i] * x[i] + y[i] * y[i];
    if (t > d) d = t;
  }
  const __m128 hiQuad = _mm256_extractf128_ps(max, 1); // high 128 bits in max
  const __m128 loQuad = _mm256_castps256_ps128(max); // low 128 bits in max
  const __m128 maxQuad = _mm_max_ps(loQuad, hiQuad);
  const __m128 hiDual = _mm_movehl_ps(maxQuad, maxQuad);
  const __m128 loDual = maxQuad;
  const __m128 maxDual = _mm_max_ps(loDual, hiDual);
  const __m128 lo = maxDual;
  const __m128 hi = _mm_shuffle_ps(maxDual, maxDual, 0x1);
  const __m128 res = _mm_max_ss(lo, hi);
  t = _mm_cvtss_f32(res);
  if (t > d) d = t;
  return sqrt(d);
}

The function will be called many times. I would like to speed it up further.

The most important part of that code, the vector loop, is held up by the loop-carried dependency through vmaxps. vmaxps on eg Skylake takes 4 cycles (other modern Intel processors are similar, but AMD Ryzen is substantially different), limiting the loop to run one iteration per 4 cycles (in steady state), which leaves a lot of available throughput unused. Optimistically, in terms of throughput the expectation is 1 iteration every cycle, 4 times as much. Therefore, unroll the loop by 4, using multiple accumulators:
  // initialized max0, max1, max2, max3 as appropriate
  for (i = 32; i + 32 < len; i += 32) {
    a = _mm256_loadu_ps(x + i);
    a = _mm256_mul_ps(a, a);
    b = _mm256_loadu_ps(y + i);
    b = _mm256_mul_ps(b, b);
    max0 = _mm256_max_ps(max0, _mm256_add_ps(a, b));
    a = _mm256_loadu_ps(x + i + 8);
    a = _mm256_mul_ps(a, a);
    b = _mm256_loadu_ps(y + i + 8);
    b = _mm256_mul_ps(b, b);
    max1 = _mm256_max_ps(max1, _mm256_add_ps(a, b));
    a = _mm256_loadu_ps(x + i + 16);
    a = _mm256_mul_ps(a, a);
    b = _mm256_loadu_ps(y + i + 16);
    b = _mm256_mul_ps(b, b);
    max2 = _mm256_max_ps(max2, _mm256_add_ps(a, b));
    a = _mm256_loadu_ps(x + i + 24);
    a = _mm256_mul_ps(a, a);
    b = _mm256_loadu_ps(y + i + 24);
    b = _mm256_mul_ps(b, b);
    max3 = _mm256_max_ps(max3, _mm256_add_ps(a, b));
  }
  max0 = _mm256_max_ps(_mm256_max_ps(max0, max1), _mm256_max_ps(max2, max3));

Since the total unroll factor is so high, it becomes more interesting to try to eliminate the "scalar epilog" (the scalar loop after the main loop), for example by using the "step back from the end"-technique in which when i + 32 < len becomes false, i or the pointers x and y are adjusted so that an iteration of the main loop (or a duplicate of it) exactly handles the remaining part of the data, without reading beyond the end of the arrays. That last iteration will overlap somewhat with the second-to-last iteration, but that is OK in this case because the maximum of all results will be taken anyway, and having some duplicates won't affect that maximum.


Abbreviating and expanding IP v6 addresses with APL Recently I solved a challenge (problem 1 of the 3rd easy problem set of phase 2 of the '19 APL Competition) on abbreviating and expanding IP v6 addresses. For that matter, I had to write two functions, AbbreviateIPv6 and ExpandIPv6. The first function ought to take a character vector of a v6 IP address and abbreviate it like this online tool. The second function ought to undo exactly what the first one did.

I need a community review because these two were among a series of problems rated as easy and while most of them were fairly easy to solve and could be decently solved in a couple of lines, I found really hard to write the AbbreviateIPv6 function so I think I overlooked something. What is more, I failed to find a solution that didn't use regular expressions, which bothered me even more.

First, a helper function:

:Namespace ReplaceFirst
    _ReplaceFirst_ ← {
        ⍝ Operator that replaces the first occurrence of the left operand with the right operand.
        ⍝ e.g. ('ui' ReplaceFirst 'fafa') 'this ui is ui' gives 'this fafa is ui'

        startAt ← ⊃⍸⍺⍺⍷⍵
        stopAt ← startAt + (¯1+≢⍺⍺)×startAt>0
        pruned ← ⍵/⍨ ~(startAt∘<∧≤∘stopAt)⍳≢⍵
        replaceAt ← (>∘0⍴⊢) startAt
        ∊ ((⊂,⍵⍵)@replaceAt) pruned
    }
:EndNamespace

that I used in the AbbreviateIPv6 function:

AbbreviateIPv6 ← {
  ⍝ Monadic function taking character vector as input and returning character vector.
  ⍝ Abbreviates an IP v6 address.
  ⍝ e.g. '2001:0DB8:0000:0042:0000:8A2E:0370:7334' becomes '2001:DB8:0:42:0:8A2E:370:7334'
  ReplFirst←⎕fix 'file://path/to/ReplaceFirst.dyalog'

  reduced ← ('0000' ':0{1,3}' ⎕R (,¨'0' ':'))⍵
  runs ← ⌽ ⍴∘'0:'¨ 1+2×⍳7
  shortened ← {(⍵ ReplFirst._ReplaceFirst_ '') reduced}¨ runs
  ((⊃∘⍋≢¨)⊃⊢) shortened
}

I know I could've defined the _ReplaceFirst_ as a function inside AbbreviateIPv6 specialized for the case I wanted, but I figured the function was getting so long I might as well write a general operator that I might reuse later.

Finally, just for comparison, I was able to write the ExpandIPv6 in a much more compact way:

ExpandIPv6 ← {
    ⍝ Monadic function expecting and returning character vector.
    ⍝ Expands an abbreviated IP v6 address.
    ⍝ e.g. '2041:0:140F::875B:131B' gives '2041:0000:140F:0000:0000:0000:875B:131B'.

    colons ← +/':'=⍵
    intermediate ← ('::' ⎕R(':0'⍴⍨ 3+2×7-colons))⍵
    splits ← (':'∘≠⊆⊢) intermediate
    LeftZeroPadder ← (⍴∘'0')∘(4∘-)∘≢,⊢
    ⊃ {∊⍺':'⍵}/ LeftZeroPadder¨ splits
}

I think using regular expressions is a perfectly sensible approach. What you're missing is probably that Dyalog APL allows setting a Match Limit with ⍠'ML' n where a positive n limits to the first n matches and a negative n limits to the (absolute value of) nth match. With this in mind, I'd use regular expressions extensively:

AbbreviateIPv6 ← {
    collapsed0s ← '\b0{1,3}' ⎕R '' ⊢ ⍵      ⍝ remove up to 3 leading 0s
    runsOf0s ← '\b(0:)*0\b'                 ⍝ 0:0:0:…:0
    nth ← - ⊃⍒ runsOf0s ⎕S 1 ⊢ collapsed0s  ⍝ 1: lengths, ⊃⍒: index of first max
    abbreviated ← runsOf0s ⎕R ':' ⍠'ML' nth ⊢ collapsed0s
    ':::' '^:$' ⎕R '::' ⊢ abbreviated       ⍝ exactly two
}

Try it online!

Notes:

The linked online IPv6 compressor gives wrong results, as do many others. This one seems to work, even though it misses the occasional shortening opportunity. I still have not found an online tool that compresses both fully and correctly.
If runsOf0s ⎕S 1 doesn't find any runs of 0s, it returns ⍬ so nth becomes 0, which is fine even though 'ML' 0 means "no limit" because there are no matches.


Unidirectional Bootstrap 3 carousel I am working on a custom Bootstrap 3 carousel, with vertical, unidirectional, slide transitions.

I want to prevent slide transitions from overlapping when the bullets are clicked in random order and rapid succession.

I came up with this solution that relies on disabling them as long as a slide transition is in progress, then enabling them between transitions:

var carouselDuration = function() {
  $.fn.carousel.Constructor.TRANSITION_DURATION = 1000;
}

carouselDuration();
// While a transition is in progress (slide event), do this
$('#myCarousel').on('slide.bs.carousel', function (e) {
    var $indicator = $(this).find('.carousel-indicators>li');
    $indicator.css('pointer-events', 'none');
});

// While a transition has finished (slid event), do this
$('#myCarousel').on('slid.bs.carousel', function (e) {
    var $indicator = $(this).find('.carousel-indicators>li');
    $indicator.css('pointer-events', 'auto');
});
.carousel.vertical {
  position: relative;
}

.carousel.vertical .carousel-inner {
  height: 100%;
  width: auto;
}

.carousel.vertical .carousel-inner>.item {
  width: auto;
  transition: 1s ease-in-out;
  transform: translate3d(0, 100%, 0);
  top: 0;
}

.carousel.vertical .carousel-inner>.next,
.carousel.vertical .carousel-inner>.prev,
.carousel.vertical .carousel-inner>.right {
  transform: translate3d(0, 100%, 0);
  top: 0;
}

.carousel.vertical .carousel-inner>.left,
.carousel.vertical .carousel-inner>.prev.right,
.carousel.vertical .carousel-inner>.next.left,
.carousel.vertical .carousel-inner>.active {
  transform: translate3d(0, 0, 0);
  top: 0;
}

.carousel.vertical .carousel-inner>.active.right,
.carousel.vertical .carousel-inner>.active.left {
  transform: translate3d(0, -100%, 0);
  top: 0;
}

.carousel.vertical .carousel-indicators {
  display: inline-block;
  width: auto;
  padding: 0;
  margin: 0;
  left: auto;
  right: 10px;
  bottom: 2px;
  z-index: 9;
  font-size: 0;
}

.carousel.vertical .carousel-indicators li {
  border: none;
  cursor: pointer;
  display: inline-block;
  width: 18px;
  height: 18px;
  text-indent: -9999px;
  background: url("https://grgs.ro/1/i/sprite.png") no-repeat -528px -502px;
}

.carousel.vertical .carousel-indicators li.active {
  background-position: -528px -524px;
}
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">

Still, I am looking for a queuing mechanism, as it is more natural and elegant.

Feedback

The code seems fairly concise, though I do have suggestions below that can simplify it even more. I was hoping there was some class name applied to the element with class carousel during the slide transition but apparently the bootstrap code does not do that, though you could use the event callback functions to apply a class name yourself. That way the CSS style for pointer-events can be moved into the CSS.

Because the .on() method accepts multiple events separated by a space, you can use one call for both events, and a single Partially applied function to call the .toggleClass() method, which will add and then remove a class to the carousel element:

var carouselCollection = $('#myCarousel');
carouselCollection.on('slide.bs.carousel slid.bs.carousel',
    carouselCollection.toggleClass.bind(carouselCollection, 'sliding'));

Then the CSS can contain the style:

.carousel.vertical.sliding .carousel-indicators li {
  pointer-events: none;
}

See that working in the rewritten code below.

I don't see much point in creating the function carouselDuration() and calling it immediately afterwards but then never again. Why not just move that single line out where it is called? I could see a point in doing that after some condition is met (e.g. DOM ready, jQuery/carousel ready, etc).

Some of the CSS rulesets are a bit redundant. For instance, some of the top: 0 rulesets should be cascadable from .carousel.vertical .carousel-inner>.item and apply to the next three subsequent selectors.

Also, I believe I was able to remove this block without any adverse affects. Are there really elements with class .right and .left or are those for the left/right controls that aren't being used?

.carousel.vertical .carousel-inner>.next,
.carousel.vertical .carousel-inner>.prev,
.carousel.vertical .carousel-inner>.right {
  transform: translate3d(0, 100%, 0);
  top: 0;
}

Suggestions

It would likely help to define that value for the duration as a constant (and if you are using ecmascript-6 then use const) at the top of the code, so it can be easily modified in the future if necessary.

While there are only a couple redundant DOM queries (e.g. $(#myCarousel)) it would be wise to cache those in a variable.

The event handler functions are very redundant, and violate the Don't Repeat Yourself principle.  The only thing that appears to change is the value assigned to the CSS style pointer-events. If the approach mentioned above with the .toggleClass() method doesn't work, the common code in the two callback functions could be abstracted into a single function that accepts the value for that CSS style, and then Partially applied functions could be created with Function.bind() to fix the value to apply to the style.

var carouselCollection = $('#myCarousel');

function setPointerEventsOnListItems(value, e) {
  var $indicator = carouselCollection.find('.carousel-indicators>li');
  $indicator.css('pointer-events', value);
}
// While a transition is in progress (slide event), do this
carouselCollection.on('slide.bs.carousel', setPointerEventsOnListItems.bind(null, 'none'));

// While a transition has finished (slid event), do this
carouselCollection.on('slid.bs.carousel', setPointerEventsOnListItems.bind(null, 'auto'));

As you likely know, the jQuery DOM ready function would be good to use so as to avoid accidentally accessing the DOM before it is ready (though that isn't a problem as much nowdays with modern browsers and adding the script tags to the end of the ). An IIFE could also be used instead of that jQuery DOM ready callback.

Rewritten code

The code below utilizes the advice above, though utilizes the .toggleClass() method.

var DURATION = 1000; //could use const instead of var if supporting es-6
$(function() { //DOM ready callback
  $.fn.carousel.Constructor.TRANSITION_DURATION = DURATION;
  var carouselCollection = $('#myCarousel');
  // While a transition is in progress (slide event), do this
  carouselCollection.on('slide.bs.carousel slid.bs.carousel', carouselCollection.toggleClass.bind(carouselCollection, 'sliding'));
});
.carousel.vertical {
  position: relative;
}

.carousel.vertical .carousel-inner {
  height: 100%;
  width: auto;
}

.carousel.vertical .carousel-inner>.item {
  width: auto;
  transition: 1s ease-in-out;
  transform: translate3d(0, 100%, 0);
  top: 0;
}

.carousel.vertical .carousel-inner>.left,
.carousel.vertical .carousel-inner>.prev.right,
.carousel.vertical .carousel-inner>.next.left,
.carousel.vertical .carousel-inner>.active {
  transform: translate3d(0, 0, 0);
}

.carousel.vertical .carousel-inner>.active.right,
.carousel.vertical .carousel-inner>.active.left {
  transform: translate3d(0, -100%, 0);
}

.carousel.vertical .carousel-indicators {
  display: inline-block;
  width: auto;
  padding: 0;
  margin: 0;
  left: auto;
  right: 10px;
  bottom: 2px;
  z-index: 9;
  font-size: 0;
}

.carousel.vertical .carousel-indicators li {
  border: none;
  cursor: pointer;
  display: inline-block;
  width: 18px;
  height: 18px;
  text-indent: -9999px;
  background: url("https://grgs.ro/1/i/sprite.png") no-repeat -528px -502px;
}

.carousel.vertical.sliding .carousel-indicators li {
  pointer-events: none;
}
.carousel.vertical .carousel-indicators li.active {
  background-position: -528px -524px;
}
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">