CHROMABITS

1 minute

Laravel 5 in its current state does not have a fully working pagination. It only seems to return simple paginators (they are not aware of the total number of items). This will most likely change in the future, but if you really need pagination working on Laravel 5 right now you can try the following:

<?php

namespace App\Support;

use Illuminate\Database\Eloquent\Builder;
use Illuminate\Pagination\LengthAwarePaginator;
use Illuminate\Pagination\Paginator;

/**
 * Class PaginationFactory
 *
 * @package App\Support
 */
class PaginationFactory
{
    public static function makeLengthAware(Builder $builder, $perPage = null, $columns = ['*'])
    {
        $page = Paginator::resolveCurrentPage();

        $builder->skip(($page - 1) * $perPage)->take($perPage + 1);

        $queryClone = clone ($builder->getQuery());

        $total = $queryClone->skip(0)->take($perPage + 1)->count($columns);

        return new LengthAwarePaginator($builder->get($columns), $total, $perPage, $page, [
            'path' => Paginator::resolveCurrentPath()
        ]);
    }
}

This will build a LengthAwarePaginator from a Builder. It seems to work fine but I’m still waiting for an official solution.


3 minutes

Laravel 5 and Foundation Pagination

Laravel 5 is not out yet, but I’ve already began working on some projects with it. A problem of working on the edge is that many libraries have not been adapted to work with the new version yet.

I use ZURB’s Foundation (an alternative to Bootstrap) for most of my projects. However, Laravel doesn’t come with pagination for Foundation.

For Laravel 4 projects, I used: https://github.com/binarix/Laravel-Foundation-Pagination which worked pretty well, however, the package hasn’t been updated for 5 yet.

So in the meantime I forked it and modified it so that it will work with Laravel 5, so now you can have ZURB Foundation pagination on Laravel 5 projects:

To add it to your project, add the following to your composer.json:

"require": {
    "eduard44/foundation-pagination": "1.0.*"
}

and the following provider to your app.php:

'Chromabits\FoundationPagination\FoundationPaginationServiceProvider',

Snake-in-the-box problem

As described in a previous blog post, the snake-in-the-box problem was introduced in one of my classes, and as part of a class assignment I’ve been building algorithms that attempt to find the best snake path inside an hypercube.

I added a new algorithm to the problem solver that executes significantly faster than the previous randomized versions I’ve worked on. This is achieved by using a more complex data structure to keep statistics about nodes and path lengths.

You can try it out be cloning the repo and running:

php run.php snakes:guided -d 7 -i 100000

This will run the algorithm in dimension 7 for 100000 iterations, which should get to a best path length of around 40-44 in just a few minutes. In comparison, the pure random version was not able to get near this number even after running for a few hours.

GitHub Project

Vertex

Vertex is my base Docker image that I use for most of my Docker projects. It comes with most tools you need for PHP and Node.js deployment.

I’ve released a new build with more up-to-date packages:

  • HHVM and Nginx are now pre-configured for a single PHP project on the default host. You may add more through custom config files, however, this should make it easier to start using Vertex since most people will probably only run a single server in it
  • Startup scripts are now provided to launch Nginx and HHVM on port 80
  • The Laravel installer is now installed through composer instead of manually downloaded
  • PHP 5.5 is now included too, although it requires manual setup since HHVM is the default
  • curl is now included too
  • Fix: Install libgmp10 manually since the HHVM package does not seem to download it automatically

The one liner:

Get an HHVM/Nginx server running on port 80 with a single command (assuming you have Docker installed):

docker run -t -i -p 80:80 eduard44/vertex

You can also run it on different ports by modifying the -p argument

GitHub Project Docker Hub Page


6 minutes

These are two problems I’ve worked on from my Artificial Intelligence class this semester. These are problems which can take a really long time if done naively, hence the goal is to come up with solutions that use some heuristic to come up with the answer faster.

Snake-in-the-box

The Snake-in-the-box problem begins with a n dimensional hypercube. It consists of finding a path (the “snake”) in this cube, in which every node has exactly two neighbors that are also in the path. The only exception is the head and tail, which can be connected to each other in other to create a continuous path.

Example 4-dimensional hypercube:

hypercube

A nice property about each node in a n-dimension cube is that they can be represented in n-digit binary numbers, and the difference between neighbors is one bit flip (In a 4-dimension hypercube, 0000 and 0001 are neighbors).

This property allows us to easily compute the neighbors of each node, regardless of the dimension of the cube, which means that if we write a program to compute the solution we don’t necessarily have to compute and store every node in the cube.

While computing a 3 or 4 dimensional hypercube is very trivial, as we move up to higher dimensions, the space needed grows exponentially.

A almost-naive solution

The following is an almost-naive (a.k.a partially brute-force) solution to this problem. It takes advantage of the bit-flip property, but it lacks any other heuristic or optimization.

The problem with this implementation lies on the fact that it still has to do a full search.

It’s written in PHP, and it’s very object-oriented, so it’s not super fast, but it does get the correct solution if you let it run for long enough:

https://github.com/eduard44/snakes

So far I’ve been able to get solutions for dimensions 3 to 6: 4, 7, 13, 26. Dimension 6 took a really long time to process on my cheap VPS, so I’m not expecting dimension 7 to finish any time soon.

Possible future steps are: Rewrite the whole thing in a more efficient language like C++ or implement some heuristic or algorithm that accelerates the execution runtime.

Sample output

$ hhvm run.php snakes -d 3
> Largest path found was: 4

$ hhvm run.php snakes -d 4
> Largest path found was: 7

Update 1: Randomized version

Another approach to this problem is to randomly select the path every time. This means that the search algorithm can return anywhere between the actual longest snake and 1.

To compensate for this, we can run the algorithm for multiple iterations, and keep track of the longest result.

This does not necessarily yield the correct solution, but it allows us to take a look at paths that at least get closer to the longest solution on higher dimensions.

As a nice added extra, I was able to use a Symfony component for displaying information about the progress of the program, including an estimate of how much time it will take to go through all the iterations:

snake3

Find the zebra

The find the zebra problem is much simpler. It consists of a group of five houses, which are next to each other in a neighborhood. Each house has 5 properties:

  • A color
  • The nationality of the owner
  • A pet/animal
  • The favorite drink of the owner
  • The favorite cigar/smoke brand of the owner (It’s an old problem, on 2014 you could replace it with something like favorite smartphone brand)

To find the solution, you must derivate rules from other rules recursively. The rules provided are (via Wikipedia):

  • There are five houses
  • The Englishman lives in the red house
  • The Spaniard owns the dog
  • Coffee is drunk in the green house
  • The Ukrainian drinks tea
  • The green house is immediately to the right of the ivory house
  • The Old Gold smoker owns snails
  • Kools are smoked in the yellow house
  • Milk is drunk in the middle house
  • The Norwegian lives in the first house
  • The man who smokes Chesterfields lives in the house next to the man with the fox
  • Kools are smoked in the house next to the house where the horse is kept
  • The Lucky Strike smoker drinks orange juice
  • The Japanese smokes Parliaments
  • The Norwegian lives next to the blue house

The two questions asked are: Who drinks water? and who owns the zebra?

Solution by elimination

To approach I took to this problem, revolves around coming up with all possible permutations and eliminating possible solutions by applying each rule one by one.

How do we represent the problem?

I chose to store the problem in a two-dimensional array (a matrix), in which each row is a category and each column is a house. This means that we have a matrix of 5 x 5.

On each row, we have 5! = 120 possible permutations (Permutation formula). On the whole table, we have (5!) * 5 = 600 possible arrangements.

It is simple to compute each of these arrangements and store them in memory, but individually checking that they meet the ruleset might take a really long time.

Reducing the initial size

The good news is that we don’t have to check every single arrangement. How? You may have noticed that three of the rules above are marked in bold. These rules are special because they are the only rules that give us a hint on where to start. From them we know that:

  • The Norwegian lives in the first house
  • The blue house is the second house
  • Milk is drank in the third (middle) house

So, when we are generating our array of all possible combinations, we can safely discard combinations that do not meet these conditions, greatly reducing our search space.

Applying rules

For all the other rules, we apply a similar strategy. We take the array of possible combinations, check which combinations match the rule and discard those that don’t. At the end, every rule we apply, reduces the size of the search to a smaller subset, meaning that each subsequent rule will execute faster. This will lead to better execution time than if we checked each combination individually against all rules.

The code:

I used NodeJS (JavaScript) to implement this solution, which ran pretty fast (about 1-2 mins, depending on the CPU). At the end, it actually found two solutions!

Please note that some of the nouns might be different from the rules above since our class used a different problem, but it’s essentially the same ruleset.

You can check the code here:

https://github.com/etcinit/ai-zebra1

Sample output

$ node zebra.js
[{
    nationalities:
    [ 'Norwegian', 'Ukrainian', 'Englishman', 'Spaniard', 'Japanese' ],
    colors: [ 'Yellow', 'Blue', 'Red', 'White', 'Green' ],
    drinks: [ 'Water', 'Tea', 'Milk', 'Juice', 'Coffee' ],
    pets: [ 'Fox', 'Horse', 'Serpent', 'Dog', 'Zebra' ],
    smokes:
    [ 'Kool', 'Chesterfield', 'Winston', 'Lucky Strike', 'Kent' ]
}, {
    nationalities:
    [ 'Norwegian', 'Ukrainian', 'Englishman', 'Japanese', 'Spaniard' ],
    colors: [ 'Yellow', 'Blue', 'Red', 'Green', 'White' ],
    drinks: [ 'Water', 'Tea', 'Milk', 'Coffee', 'Juice' ],
    pets: [ 'Fox', 'Horse', 'Serpent', 'Zebra', 'Dog' ],
    smokes:
    [ 'Kool', 'Chesterfield', 'Winston', 'Kent', 'Lucky Strike' ]
}]

…or you can find more in the archives.

CHROMABITS
Copyright © 2015-2021 - Eduardo Trujillo
Except where otherwise noted, content on this site is licensed under a Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) license.
Site generated using Gatsby.